优化算法——截断梯度法(TG)

一、L1正则的表达形式

   在机器学习中，几乎无人不知无人不晓L1正则与L2正则，L1正则与L2正则都有参数控制的作用，对模型起到约束的作用，防止过拟合。但是L1正则与L2正则也有区别，L1正则更容易产生稀疏解，使得某些参数等于0，而L2正则却没有这样的优势，只能使得参数趋近于0。利用这样的优势可以使得L1具有特征选择的作用，若某些特征的系数为0表示该维特征对于模型没什么作用，故此可以丢弃。

L1正则与L2正则相比具有了更多的优点，同时，L1正则的优化相对L2正则来讲，也变得更加难。对于L2正则，由于正则项是可导的，因此博客中的基于梯度的优化算法，如梯度下降法，牛顿法，拟牛顿法(DFP算法，BFGS算法，L-BFGS算法)都可以直接用于求解带有L2正则的优化问题。L1正则项是不可导的，因此前面的这些算法无法直接对其进行求解，因此需要对其进行修改才能用来求解带有L1约束的优化问题。带有L1正则的表达式主要有以下两种：

1、convex-constraint formulation

二、处理大数据的方法

    由于数据量比较大，可能已经超出了内存的大小，此时无法将数据全部装入到内存中参与计算，主要有两种方法处理大数据问题

1. 在很多机器上并行批学习
2. 利用流式的在线学习

1、流式在线学习的流程

2、随机梯度下降法  

三、截断梯度法(Truncated Gradient)

正如上面所讲，L1正则可以使得某些特征的系数为0，具有特征选择的能力，这便称为稀疏性(Sparsity)。L1正则能够产生稀疏的解。为了能够在利用在线学习的同时产生稀疏解，最直接的想法是采用截断的方法，截断，即通过某个阈值来控制系数的大小，若系数小于某个阈值便将该系数设置为0，这便是简单截断的含义。

1、简单截断(Simple coefficient Rounding)

2、L1-Regularized Subgradient(次梯度)

有关次梯度的概念将会在另一篇文章中涉及，L1-Regularized Subgradient形式也比较直观，具体的形式如下：

其中，函数

是一个符号函数，其具体形式如下：

这样的次梯度的方法的主要缺点是在很少的情况下能够产生稀疏的解，主要的原因是前后两部分做加减法能够等于0的概率很小。

3、截断梯度法(Truncated Gradient)