>By joey周琦

正则化

假设目标函数为$J$,比如$J$可以是对数似然函数的负数形式，特征$i$的系数为$w_i$,系数向量 w=[@H_502_126@w1,...,wK] $w = [w_1,...,w_K]$,假设一共有$K$个备选类。 机器学习（分类为例）的目标就是要解决一个优化问题

$$w = \arg \min \limits_w L(w)$$

而为了避免模型的过拟合(overfitting),所以需要在这里进行正则化（regularization）[2]。正则化的主要思想就是控制系数$|w|$的大小，从而控制模型的复杂度，减小过拟合，提高泛化能力，常见的正则化选择有一阶和二阶，如下
二阶(L2)：

$$w =\arg \min \limits_w L(w) + \alpha/2 \sum \limits_{k=1}^K w_k^2$$

一阶(L1)：

$$w =\arg \min \limits_w L(w) + \alpha \sum \limits_{k=1}^K |w_k|$$

那么在迭代优化时：
L2的更新公式为:

$$w_k^{t+1} = w_k^t - \lambda \frac{\partial L}{\partial w_k}- \lambda \alpha w_k$$

L1的更新公式为:

$$w_k^{t+1} = w_k^t - \lambda \frac{\partial L}{\partial w_k}- \lambda \alpha \text{sgn}(w_k)$$

L1 正则化在0处不可导，但是可以采用“次梯度”替代。在batch(批量数据）模式下，L1更容易产生稀疏的解，即很多不重要的特征的系数会比较接近0，所以在从而可以达到特征选择的作用。在梯度下降优化中一般偏导数的公式是一个包含所有样本的加和形式如下

$$\frac{\partial L}{\partial w_k} = \sum_{n=1}^{N} Q_n$$

可以看出梯度下降法的一次迭代即要用到所有的训练数据，这样的迭代速度过慢。为了提高更新速度，随机梯度下降法将上述的全量加和梯度，近似为了单样本的梯度如下:

$$\frac{\partial L}{\partial w_k} \approx Q_n$$

对于凸优化问题，相对于梯度下降法，在学习率适当的收敛和一些温和的假设下，随机梯度下降法更快速接近全局最优解[3]。
在线(online)模式，即以增量的形式更新，数据一条一条过来的时候，梯度下降法的batch模式无法应用 ，而应该使用随机梯度下降法。对于随机梯度下降法，L1正则化也得不到比较稀疏的解。所以在线模式中想要产生稀疏特征，则要利用下面讲的一些在线优化的方法。

在线优化

简单截断法

以$k$为窗口，当$t/k$不为整数时，进行标准的SGD迭代$w_k^{t+1} = w_k^t - \lambda \frac{\partial L}{\partial w_k}$（不包含L1 or L2)，当$t/k$为整数时

$$w_k^{t+1} = T_0(w_k^t - \lambda \frac{\partial L}{\partial w_k})$$
其中
$$T_0(v_i) = \begin{cases} 0,& |v_i| \le \theta \\ v_i,& otherwise \end{cases}$$
其中 $\theta$是控制截断的阈值。

截断梯度法(Truncated Gradient,TG)

为了避免上述too aggressive的截断方法，TG采用了一种比较温和的截断方法
以$k$为窗口，当$t/k$不为整数时，进行标准的SGD迭代$w_k^{t+1} = w_k^t - \lambda \frac{\partial L}{\partial w_k}$，当$t/k$为整数时

$$w_k^{t+1} = T_1(w_k^t - \lambda \frac{\partial L}{\partial w_k})$$
其中
$$T_1(v_i) = \begin{cases} \max (0,v_i - \alpha),& |v_i| \in [0,\theta] \\ \min (0,v_i + \alpha),&|v_i| \in [-\theta,0] \\ v_i,& otherwise \end{cases}$$

可以看出TG方法又增加了一个参数$\alpha$来温和截断，原论文中有一个图可以形象的对比两种截断方法。

参考 1 在线最优化求解，冯扬 2 wiki,Regularization (mathematics) 3 Stochastic gradient descent - Wikipedia