Logistic Regression, L1, L2 regularization, Gradient/Coordinate descent

Generative model v.s. Discriminative model：

Examples:

• Generative model: Naive Bayes, HMM, VAE, GAN.
• Discriminative model：Logistic Regression, CRF.

Objective function:

• Generative model: $maxp(x,y)$
• Discriminative model：$maxp(y|x)$

Difference:

• Generative model: We first assume a distribution of the data in the consideration of computation efficiency and features of the data. Next, the model will learn the parameters of distribution of the data. Then, we can use the model to generate new data. (e.g. generate new data from a normal distribution.)
• Discriminative model: The only purpose is to classify, that is, to tell the difference. As long as it can find a way to tell the difference, it doesn’t need to learn anything else.

Relation:

• Generative model: $p(x,y)=p(y|x)p(y)$, it has a prior term $p(y)$.
• Discriminative model：$p(y|x)$
• Both models can do classification problems, but discriminative model can do classification problems only. Usually, for classification problems, discriminative model performs better. On the other hand, if we have limited data, generative model might perform better (since it has a prior term, which plays the role of a regularization).

Logistic regression

Formula:

$$\sigma (x)=\frac{1}{1+e^{-w^{T}x}}$$

Derivative formula:

• ${\sigma }^{\prime }(x)=\sigma (x)(1-\sigma (x))$

Logistic Regression does not have analytic solutions and we need to use iterative optimization to find a solution recursively.

It spends a lot of computational power to calculate $e^x$ because of floating points. In most code implementation, people will pre-calculate values and then do approximate with a new $x$ comes.

Derivation of Logistic Regression

$$\begin{array}{rl}p(y|x,w,b)& =p(y=1|x,w,b{)}^y[1-p(y=1|x,w,b){]}^{1-y}\\ {\hat{w}}_{MLE},{\hat{b}}_{MLE}& ={\text{argmax}}_{w,b}\prod _{i=1}^{n}p(y_i|x_i,w,b)\\ & ={\text{argmax}}_{w,b}\sum _{i=1}^n\log p(y_i|x_i,w,b)\\ & ={\text{argmin}}_{w,b}-\sum _{i=1}^n\log p(y_i|x_i,w,b)\\ & ={\text{argmin}}_{w,b}-\sum _{i=1}^n\log {[p\left(y_i\right)|x_i,w,b)}^{y_i}[1-p{(y_i=1|x_2,w,b)}^{-y_i}]\\ & ={\text{argmin}}_{w,b}-\sum _{i=1}^n{y}_i\log p(y_i=1|x_i,w,b)+(1-y_i)\log [1-p(y_i=1|x_{i}w,b)]\\ & ={\text{argmin}}_{w,b}L\frac{\partial L}{\partial b}& =-\sum _{i=1}^n(y_i\cdot \frac{\sigma (w^T{x}_i+b)\cdot [1-\sigma (w^T{x}_i+b)]}{\sigma (w^T{x}_i+b)}-(1-y_i)\cdot \frac{-\sigma (w^T{x}_i+b)[1-\sigma (w^T{x}_i+b)]}{1-\sigma (w^T{x}_i+b)}]& \\ & =-\sum _{i=1}^n(y_i[1-\sigma (w^T{x}_i+b)]-(1-y_i)\sigma (w^T{x}_i+b))\\ & =\sum _{i=1}^n(\sigma (w^T{x}_i+b)-y_i)\frac{\partial L}{\partial w}& =\sum _{i=1}^n(\sigma (w^T{x}_i+b)-y_i)\cdot x_i\end{array}$$

Gradient:

True gradient: The true gradient of the population.

Empirical gradient: Use sample gradient to approximate true gradient.

• SGD, approximate bad. Asymptotically converge to true gradient.
• GD, approximate good.
• mini-batch DG, middle.

For smooth optimization, we can use gradient descent.

For non-smooth optimization, we can use coordinate descent (e.g. L1).

Mini-Batch Gradient Descent for Logistic Regression

Way to prevent overfitting:

• More data.
• Regularization.
• Ensemble models.
• Less complicate models.
• Less Feature.
• Add noise (e.g. Dropout)

L1 regularization

L1: Feature Selection, PCA: Features changed.

Why prefer sparsity:

1. reduce dimension, then less computation.
2. Higher interpretability.

Problem of L1:

• Group Effect: If there is collinearity in features, L1 will randomly choose one from each group. Therefore, the best feature in each group might not be selected.

Coordinate Descent for Lasso

• Intuition: If we are at a point $x$ such that $f(x)$ is minimized along each coordinate axis, then we find a global minimizer.

• step of Coordinate Descent: Note that we don’t need a learning rate here since we are finding the optimum values.

Large eigenvalue by co-linear columns

If a matrix 𝐴 has an eigenvalue $\lambda$, then $A^{-1}$ have an eigenvalue $\frac{1}{\lambda }$

$$A\mathbf{v}=\lambda \mathbf{v}⟹A^{-1}A\mathbf{v}=\lambda A^{-1}\mathbf{v}⟹A^{-1}\mathbf{v}=\frac{1}{\lambda }\mathbf{v}$$

If a matrix $A=X^{T}X$ has a very small eigenvalue, then its inverse $(X^{T}X{)}^{-1}$ has a very big eigenvalue. We know that the formula for $\beta$ is $$\hat{\beta }=(X^{T}X{)}^{-1}{X}^{T}y$$

If we plug in $y = X\beta^{} + \epsilon$,then$$\hat \beta = \beta^{} + (X^{T}X)^{-1}X^{T}\epsilon$$

Multiplying the noise by $(X^{T}X{)}^{-1}$ has the potential to blow up the noise. This is called “noise amplification”. If we set the error term $ϵ$ to zero, then there is no noise to amplify. Hence there are no problems with the huge eigenvalues of $(X^{T}X{)}^{-1}$, and we still recover the correct answer. But even a little bit of error, and this goes out the window.

If we now add some regularization (aka weight decay), then $$\hat{\beta }=(X^{T}X+\lambda I{)}^{-1}{X}^{T}y$$

Adding a small multiple of the identity to $X^{T}X$ barely changes the large eigenvalues, but it drastically changes the smallest eigenvalue – it increases it to $\lambda$. Thus in the inverse, the largest eigenvalue will be at most $\frac{1}{\lambda }$.

Building Models with prior knowledge (put relation into models via regularization):

• model + $\lambda \cdot$ Regularization
• Constraint optimization
• Probabilistic model (e.g. Probabilistic Graph Model (PGM))