MLE, MAP

1. \begin{align} \theta_{MLE} &= \mathop{\rm arg\,max}\limits_{\theta} P(D \vert \theta) \\[10pt] &= \mathop{\rm arg\,max}\limits_{\theta} \prod_i P(x_i \vert \theta) \end{align} To avoid underflow, we will instead work in the log space, as logarithm is monotonically increasing, so maximizing a function is equal to maximizing the log of that function. \begin{align} \theta_{MLE} &= \mathop{\rm arg\,max}\limits_{\theta} \log P(X \vert \theta) \\[10pt] &= \mathop{\rm arg\,max}\limits_{\theta} \log \prod_i P(x_i \vert \theta) \\[10pt] &= \mathop{\rm arg\,max}\limits_{\theta} \sum_i \log P(x_i \vert \theta) \end{align} MAP \begin{align} P(\theta \vert X) &= \frac{P(X \vert \theta) P(\theta)}{P(X)} \\[10pt] &\propto P(X \vert \theta) P(\theta) \end{align} \begin{align} \theta_{MAP} &= \mathop{\rm arg\,max}\limits_{\theta} P(X \vert \theta) P(\theta) \\[10pt] &= \mathop{\rm arg\,max}\limits_{\theta} \log P(X \vert \theta) + \log P(\theta) \\[10pt] &= \mathop{\rm arg\,max}\limits_{\theta} \log \prod_i P(x_i \vert \theta) + \log P(\theta) \\[10pt] &= \mathop{\rm arg\,max}\limits_{\theta} \sum_i \log P(x_i \vert \theta) + \log P(\theta) \end{align}
2. Example: $n$ random variables $x_i$ drawn from Gaussian $\mu, \sigma$: $$log(\prod_{i=1}^{n}\frac{1}{\sqrt{2\pi}\sigma} exp\{ \frac{-(x_i - \mu)^2}{2\sigma^2}\} = -n log(\sqrt{2\pi}\sigma) - \frac{1}{2\sigma^2}\sum_{i=1}^{n}{(x_i - \mu)^2}$$ MLE for variance: $$\nabla_{\sigma}l (x_1, x_2, \cdots, x_n | \mu, \sigma^2) = 0 $$ $$ \frac{1}{n}\sum_{i=1}^{n}{(x_i - \mu)^2} = \sigma^2$$
3. Example: $n$ random variables $x_i$ drawn from Bernoulli $\theta$: $$(\sum_{i=1}^{n}x_i)log(\theta)+(n - \sum_{i=1}^{n}x_i)log(1-\theta)$$ MLE for variance: $$\nabla_{\theta}l (x_1, x_2, \cdots, x_n | \theta) = 0 $$ $$ \hat{\theta} = \frac{1}{n}\sum_{i=1}^{n}{X_i}$$

Logistic Regression

1. $$\frac{\exp{w^Tx}}{1+\exp{w^Tx}} = \frac{1}{1+\exp{(-w^Tx)}}$$ this can also be viewed as a special case of softmax with only 2-classes: $$\frac{1}{1+\exp{(-w^Tx)}} \geq \frac{1}{2} \rightarrow w^Tx \geq 0 $$ hence the decision boundary is linear in the binary case
2. LR gives us an unconstrained, smooth objective. LR gives calibrated probabilities that can be interpreted as confidence in a decision
3. LR is a linear classifier: decision rule is a hyperplane. When feature is quadratic, could be ellipse, regularization will enlarge such ellipse.
4. As an optimization problem, binary class $\ell_2$ penalized logistic regression minimizes the following cost function: $\min_{w, c} \frac{1}{2}w^T w + C \sum_{i=1}^n \log(\exp(- y_i (X_i^T w + c)) + 1)$ Similarly, $\ell_1$ regularized logistic regression solves the following optimization problem: $\min_{w, c} \|w\|_1 + C \sum_{i=1}^n \log(\exp(- y_i (X_i^T w + c)) + 1).$ Elastic-Net regularization is a combination of and, and minimizes the following cost function: $\min_{w, c} \frac{1 - \rho}{2}w^T w + \rho \|w\|_1 + C \sum_{i=1}^n \log(\exp(- y_i (X_i^T w + c)) + 1),$ where $\rho$ controls the strength of $\ell_1$ regularization vs. $\ell_2$ regularization (it corresponds to the l1_ratio parameter). No regularization amounts to setting C to a very high value. Maximum conditional a posteriori corresponds to regularization.

SVM

1. TL;DR: SVM is about find a soft margin (supporting hyper plane) that best separates the data. If we cannot find such separatable instance, we can move to higher dimension by using Kernels.
2. Understanding RKHS is the basis of understanding Kernels.
3. SVM Primal and Dual derivation.
4. SVC solves the following primal problem:

\begin{align}\begin{aligned}\min_ {w, b, \zeta} \frac{1}{2} w^T w + C \sum_{i=1}^{n} \zeta_i\\\begin{split}\textrm {subject to } & y_i (w^T \phi (x_i) + b) \geq 1 - \zeta_i,\\ & \zeta_i \geq 0, i=1, ..., n\end{split}\end{aligned}\end{align} Intuitively, we’re trying to maximize the margin (by minimizing $||w||^2 = w^Tw$), while incurring a penalty when a sample is misclassified or within the margin boundary. Ideally, the value $y_i (w^T \phi (x_i) + b) $would be $\geq 1 $for all samples, which indicates a perfect prediction. But problems are usually not always perfectly separable with a hyperplane, so we allow some samples to be at a distance $\zeta_i$ (Slack Variable) from their correct margin boundary. The penalty term $C$ controls the strength of this penalty, and as a result, acts as an inverse regularization parameter. Basically, the smaller $C$ is, the more SVM can tolerate slack variable, and thus allowing more misclassification. For very tiny values of $C$, you should get misclassified examples, often even if your training data is linearly separable.(also see note below).
The dual problem to the primal is: \begin{align}\begin{aligned}\min_{\alpha} \frac{1}{2} \alpha^T Q \alpha - e^T \alpha\\\begin{split} \textrm {subject to } & y^T \alpha = 0 \\ & 0 \leq \alpha_i \leq C, i=1, ..., n\end{split}\end{aligned}\end{align} where $e$ is the vector of all ones, and $Q$ is an n by n positive semidefinite matrix, $Q_{ij} \equiv y_i y_j K(x_i, x_j)$, where $K(x_i, x_j) = \phi (x_i)^T \phi (x_j)$ is the kernel. The terms $\alpha_i$ are called the dual coefficients, and they are upper-bounded by $C$. This dual representation highlights the fact that training vectors are implicitly mapped into a higher (maybe infinite) dimensional space by the Kernel Function e.g. The The RBF kernel.
Once the optimization problem is solved, the output of decision_function for a given sample x: $\sum_{i\in SV} y_i \alpha_i K(x_i, x) + b$ and the predicted class correspond to its sign.
The primal problem can be equivalently formulated as $\min_ {w, b} \frac{1}{2} w^T w + C \sum_{i=1}\max(0, 1 - y_i (w^T \phi(x_i) + b)),$ where we make use of the hinge loss. This is the form that is directly optimized by LinearSVC, but unlike the dual form, this one does not involve inner products between samples, so the famous kernel trick cannot be applied.

Fully Connected Networks

1. Example: $N$ layer neural network that takes in a scalar input $x$, where each layer consists of a single neuron. $x = o_0$, $$s_i = w_i o_{i-1} + b_i$$ $$o_i = \sigma(s_i)$$ $$\frac{\partial{o_N}}{\partial{w_1}} = \frac{\partial{o_N}}{\partial{o_{N-1}}}\frac{\partial{o_{N-1}}}{\partial{o_{N-2}}} \cdots \frac{\partial{o_1}}{\partial{w_1}} = \frac{\partial{o_1}}{\partial{w_1}} \prod_{i=2}^{N}\frac{\partial{o_{i}}}{\partial{o_{i-1}}} = \sigma'(s_1)x \prod_{i=2}^{N}\sigma'(s_i)w_i \leq x(\frac{1}{4})^N$$