L1 regularization

arg⁡minf(x)+∥x∥p\arg min f(x) + {\lVert x \rVert}_p

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

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

范数(norm)

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

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

  1. 非负性∥x∥>0\lVert x \rVert \gt 0

  2. 齐次性∥cx∥=∥c∥∥x∥\lVert cx \rVert = \|c\| \lVert x \rVert

  3. 三角不等式∥x+y∥<∥x∥+∥y∥\lVert x+y \rVert \lt \lVert x \rVert + \lVert y \rVert

Lp范数：∥x∥\lVert x \rVert为x向量各个元素绝对值p次方和的1/p次方，∥x∥p=(∑iN∣xi∣p)1p{\lVert x \rVert}_p=(\sum_i^N |x_i|^p) ^ {\frac {1} {p}}

等价于优化：(∑iN∣xi∣p)<rp(\sum_i^N |x_i|^p) \lt r^p，以2维及2范数举例，这相当于一个圆。这就是Lp球的。

向量範數

先验分布

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

β^=arg⁡max⁡βp(β∣D)=arg⁡max⁡βp(D∣β)p(β)p(D)≈arg⁡max⁡βp(D∣β)p(β)\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）的真实作用是什么？

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

假设先验为高斯分布：

p(β)=∏c∏i<dNorm(0,σi2)(βc,i)=1σi2πexp⁡(−βc,i22σi2)err=−log⁡p(D∣β)p(β)=−log⁡p(D∣β)−log⁡p(β)=−log⁡p(D∣β)−cβ2p(\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

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

p(β)=∏c∏i<dLaplace(0,σi2)(βc,i)=22σiexp⁡(−2∣βc,i∣σi)err=−log⁡p(D∣β)p(β)=−log⁡p(D∣β)−log⁡p(β)=−log⁡p(D∣β)−c∣βc,i∣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正则形式：

1N∑n=1Nlog⁡(1+exp⁡(−ynWTXn))+λ∥W∥1\frac {1} {N} \sum_{n=1}^N \log (1+\exp(-y_n W^T X_n)) + \lambda \left \| W \right \|_1

训练求解

L1-ADMM

1N∑n=1Nlog⁡(1+exp⁡(−ynWTXn))+λ∥W∥1⇔1N∑n=1Nlog⁡(1+exp⁡(−ynWTXn))+λ∥Z∥1s.t.W=Z\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

并行化

Online Learning

a bayesian view

拿之前数据的后验，作为先验,递归下去：p(θ∣D1:k)∝p(Dk∣θ)p(θ∣D1:k−1)p(\theta|D_{1:k}) \propto p(D_k|\theta)p(\theta|D_{1:k-1})

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

  2. 比SGD快得多。

出处：MLaPP page266 8.5.5 节

参考佳文

详解并行逻辑回归

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

PreviousLogistic RegressionNextL2 regularization

Last updated