# L1 regularization

$$\arg min f(x) + {\lVert x \rVert}\_p$$

> 经验风险最小化 + 正则化项 = 结构风险最小化

训练时，希望经验风险最小化，还希望结构风险也小，加上正则项，则可以tradeoff。

#### 范数(norm)

范数是具有“长度”概念的函数。向量的范数可以简单形象的理解为向量的长度，或者向量到零点的距离。

向量的范数定义：向量的范数是一个函数$$\lVert x \rVert$$,满足

1. 非负性$$\lVert x \rVert \gt 0$$
2. 齐次性$$\lVert cx \rVert = |c| \lVert x \rVert$$
3. 三角不等式$$\lVert x+y \rVert \lt \lVert x \rVert + \lVert y \rVert$$

Lp范数：$$\lVert x \rVert$$为x向量各个元素绝对值p次方和的1/p次方，$${\lVert x \rVert}\_p=(\sum\_i^N |x\_i|^p) ^ {\frac {1} {p}}$$

等价于优化：$$(\sum\_i^N |x\_i|^p) \lt r^p$$，以2维及2范数举例，这相当于一个圆。这就是Lp球的。

[向量範數](https://ccjou.wordpress.com/2013/08/13/%E5%90%91%E9%87%8F%E7%AF%84%E6%95%B8/)

### 先验分布

**从贝叶斯角度看，正则化可以理解为对模型加了先验。**（正则化可以从其他角度去理解吗？）\
lr估计是采用maximum likelihood估计，加了先验就变成了 MAP了。

$$
\begin{align}
\hat \beta &= \arg \max\_{\beta} p(\beta | D) \\
&= \arg \max\_{\beta} \frac {p(D|\beta)p(\beta)}{p(D)} \\
&\approx  \arg \max\_{\beta} p(D|\beta)p(\beta) \\
\end{align}
$$

> 看到这里，会不会又扯到共轭先验。 先记下来，以后梳理下 “共轭先验正则化”。\
> 另外，为毛不直接MAP？，然后用变分贝叶斯

<https://www.zhihu.com/question/31464378/answer/52068253> 贝叶斯（bayesian）防止过拟合的确切机理？边缘化（marginalizing）的真实作用是什么？

额，还真有bayesian logistic regression这说法。MLaPP page 254。\
![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fe20391cd0f173aa707e1701fcb141938eb4d05ef.png?generation=1589383924647988\&alt=media)

为了将置信区间confidence intervals 和 预测prediction联系起来，加入先验。但是比较困难，有MCMC和variational inference等近似方法。

**假设先验为高斯分布：**

$$
p(\beta) = \prod\_{c} \prod\_{i \lt d} Norm(0,\sigma\_i^2)(\beta\_{c,i}) \\
\= \frac {1}{\sigma\_i \sqrt{2\pi}} \exp(- \frac {\beta\_{c,i}^2}{2 \sigma\_i^2}) \\

err = - \log p(D|\beta)p(\beta) = - \log p(D|\beta) - \log p(\beta) =  - \log p(D|\beta) - c \beta^2
$$

这就是L2范数约束的形式。\
![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fd69ef8e891323b65f338e8e5d872bdab084050a0.jpg?generation=1589383925045373\&alt=media)

**假设先验为拉普拉斯分布：**

$$
p(\beta) = \prod\_{c} \prod\_{i \lt d} Laplace(0,\sigma\_i^2)(\beta\_{c,i}) \\
\= \frac {\sqrt{2}}{2 \sigma\_i } \exp(- \sqrt{2} \frac {\left | \beta\_{c,i} \right |}{\sigma\_i}) \\

err = - \log p(D|\beta)p(\beta) = - \log p(D|\beta) - \log p(\beta) =  - \log p(D|\beta) - c {\left | \beta\_{c,i} \right | }
$$

这就是L1范数约束的形式。

> 先验分布还有其他形式，见 《 Lazy sparse stochastic gradient descent for regularized multinomial logistic regression》

正则化符合**奥卡姆剃刀原理（Occam's razor）**：在所有可能选择的模型中，能够很好地解释已知数据且十分简单的模型才是最好的模型。从贝叶斯估计的角度来看，就是正则化项对应于模型的先验概率，复杂的模型具有较小的先验概率，而简答的模型具有较大的先验概率。

**简化后的L1正则形式：**

$$
\frac {1} {N} \sum\_{n=1}^N \log (1+\exp(-y\_n W^T X\_n)) + \lambda \left | W \right |\_1
$$

## 训练求解

#### L1-ADMM

$$
\frac {1} {N} \sum\_{n=1}^N \log (1+\exp(-y\_n W^T X\_n)) + \lambda \left | W \right |*1 \\
\Leftrightarrow \\
\frac {1} {N} \sum*{n=1}^N \log (1+\exp(-y\_n W^T X\_n)) + \lambda \left | Z \right |\_1 \qquad s.t. \quad W=Z
$$

#### 并行化

batch learning\
![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F06ca215f6c26cb9fcc19cccea38ed3d92af51a64.jpg?generation=1589383924791632\&alt=media)

### Online Learning

**a bayesian view**

拿之前数据的后验，作为先验,递归下去：$$p(\theta|D\_{1:k}) \propto p(D\_k|\theta)p(\theta|D\_{1:k-1})$$

1. 返回一个后验而不是一个点估计，有明显的好处。这可以在线适应超参，这也很重要，因为无法在线做交叉验证。
2. 比SGD快得多。

出处：MLaPP page266 8.5.5 节

### 参考佳文

[详解并行逻辑回归](http://blog.csdn.net/zhoubl668/article/details/19612215\)%20%20%0A\[%E5%A4%A7%E8%A7%84%E6%A8%A1%E9%80%BB%E8%BE%91%E5%9B%9E%E5%BD%92%E5%B9%B6%E8%A1%8C%E5%8C%96]\(http:/wenku.baidu.com/link?url=rh2SJz6yNNonDNS0T41GRBv86j95rqajhrxiYLh59u_q2sPtE66o7ujI_wfunnFmDPLPclV39NJA7F7vXfJiM3Zo2nlqVNd6VysNJ2ZWxMO%29%20%20%0A\[Stochastic%20Gradient%20Descent]%28http://www.cnblogs.com/vivounicorn/archive/2012/02/24/2365328.html%29%20%20%0A\[%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E4%B8%AD%E5%B8%B8%E5%B8%B8%E6%8F%90%E5%88%B0%E7%9A%84%E6%AD%A3%E5%88%99%E5%8C%96%E5%88%B0%E5%BA%95%E6%98%AF%E4%BB%80%E4%B9%88%E6%84%8F%E6%80%9D]%28https://www.zhihu.com/question/20924039%29%20%20%0A\[%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E4%B8%AD%E4%BD%BF%E7%94%A8%E3%80%8C%E6%AD%A3%E5%88%99%E5%8C%96%E6%9D%A5%E9%98%B2%E6%AD%A2%E8%BF%87%E6%8B%9F%E5%90%88%E3%80%8D%E5%88%B0%E5%BA%95%E6%98%AF%E4%B8%80%E4%B8%AA%E4%BB%80%E4%B9%88%E5%8E%9F%E7%90%86]%28https://www.zhihu.com/question/20700829)

[史上最全面的正则化技术总结与分析](https://zhuanlan.zhihu.com/p/35429054)