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球的。

向量範數

先验分布

从贝叶斯角度看，正则化可以理解为对模型加了先验。（正则化可以从其他角度去理解吗？） 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。

为了将置信区间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范数约束的形式。

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

$$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

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 节

参考佳文

详解并行逻辑回归

史上最全面的正则化技术总结与分析