转载

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

摘要： 本文主要讲的是近几个月来的一些研究成果，通过构建增强式的快速迭代logistics判别分类器，就是通过组合随机梯度（SGD），提升算法（adaboost），logistics模型。

具体地：通过利用SGD估计每个logistics弱分类器参数，同时基于每个弱分类器，通过adaboost更新样本的权重以及计算每个分类器权重，最后组合多个弱分类器，构成一个强分类输出判别。

理论概述

1. 随机梯度算法概述；

梯度算法在机器学习常被用于参数的迭代估计，当维度与样本数大幅上升时，其表现出的估计性能与速度也十分可观。

假设如下方程 hθ(x) ：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

其中 θi(0⩽i⩽n，n为样本维度) 为变量 xi 对应参数，为简化上述式子，通过将 x0=1 加入 hθ(x) ，可以得到：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

其中 θT和X

为系数和变量对应向量表达式。

再定义如下损失函数

J(θ) ：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

其中 hθ(x(j)) 为对应第j个样本 x(j) 代入 hθ(x) 得到的结果，m为样本个数，需要注意的是，梯度算法一般用于有监督或半监督式机器学习，而常量 y(j) 的存在是为了训练样本得到更加准确的 θ 参数。另外，系数0.5是为了求导方便而乘上的，对结果并无影响。

据此，为最小化上述 J(θ) 损失函数，我们通过 θ 自适迭代，达到一个理想的估计值，使得：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

其中 ϵ 为误差率，为方便理解，我们从Batch gradient descent(批梯度下降说起)，有如下式子：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

其中 α 为梯度步长，也称为学习因子，其大小决定了梯度下降的速度，越大的步长则学习速度也越快，但同时振荡往返也会加剧，有时反而使得速度变慢，同时若梯度步长太小，也会使得速度变慢，而容易陷入局部极小。

结合(2)式和(3)式，假设只有一个样本，则可以得到：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

其中i表示样本维度i，当样本数为m时，则：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

其中j表示样本j。

可以看出，每次迭代都要遍历m个样本，当样本数量太大时，其复杂度 O(m) 也成线性上升，这在一定程度上制约了迭代的速度，所以，基于此，Stochastic gradient desent（随机梯度）应运而生，其在一定程度降低了批梯度的遍历量，复杂度从 O(m) 降为 O(1) ，但同时也带来了其他问题–迭代次数和局部最小值，由于随机性的存在，随机梯度将在随机样本点的周围四处扩散，并最终步入“谷底”，但是过程会稍微曲则，且改“谷底”可能是局部而不是全局。

其表达式如下：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

需要说明的是，当用于判别分类算法中时，其中 x(j)i 表示误判点的第i维。

其中如上文所述，由于随机路径梯度下降，所以容易陷入局部最优，一个较好的解决办法是赋予多次不同的初始值，同时结合判别误差率作为跳出条件。

为更形象理解批梯度和随机梯度，下图3、4为批梯度下降路径和随机梯度下降路径：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

可以看出，批梯度下降在每次迭代时都会朝最优方向前进，而随机梯度通常经过多次“峰回路转”最终达到“谷底”，所以随机梯度算法对初始值要求比较高，通常一个好的初始值能尽最大程度优化过程，而对于初始值取法将在下文实证部分进一步说明。

2. logistic判别算法概述；

为更好阐述logistic算法细节，有必要先引入OLS模型（最小二乘回归法），假设二分类回归方程 y ：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

其中 e 为残差项，其分布满足均值为0，且相互之间相互独立， y 为二分类变量，如下：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

由于 y 的取值只有0和1，则其均值为：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

可以看出， y 的均值即其取值1时的概率，则 y=a 的概率为：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

上述式（7）和（8），通常还成为LPM（线性概率模型），而关于该模型的探讨，将直接体现出logistic算法的优势，以及为什么使用logistic作为进一步的判别算法。

那么首先，针对上述式（6），其残差 e 的均值表达式为：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

其中：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

f() 为残差项 e 的概率密度函数。

则令式（9）为0，得到：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

由此我们得到一个重要的性质，方差的齐性，而上述 e 的方差明显非齐性，即方差随着样本的不同而改变，由此带来的参数估计是有偏的，且t检验F检验都是无效的。

同时，LPM模型对于概率的上下界没有限定，存在溢出[0,1]的情况，最后，由于其线性的关系，无法满足式（6）二分类性质，基于此，logistic算法的提出，在一定程度上很好地解决了上述问题，其一般形式如下：

假设残差 e 服从logistic分布，则结合式（6）和式（7），可以得到：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

式（10）即为logistic算法的核心表达式，其分布呈S形，如下图（5）所示：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

可以看出：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

同时，由式（10），可以进一步得到：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

两边取对数可以得到：

算法篇：SGD+logistic+Adaboost构建快速迭代增强式LR模型（一）

如此一来，把logistic模型化为线性形式，其各种性质可以借用上文对LPM模型的分析，但是又不局限于LPM，其不存在概率溢出问题，同时表达式更加契合二分类问题结构形式。

关于logistic算法参数的进一步估计推导，将在第4部分结合随机梯度算法进一步阐述。

3. Adaboost算法概述；

Adaboost是一种增强式学习算法，它能在普通算法产生的弱分类器的基础上通过集成多个分类器，进而学习得到一种强分类器。对于adaboost的概述，要从Valiant提出的PAC（Probably Approximately Correct）学习模型入手，其定义了强弱两种学习过程。

对于强学习而言，假设存在N个数据点的样本集 (x1,y1),⋅⋅⋅,(xN,yN) ，其中 xi 为参数的属性向量， yi 为 0或1，学习算法通生成一个符号函数h，使得对于从 (x1,y1),⋅⋅⋅,(xN,yN) 中随机抽取的子集都有 Pr[h(xi)≠yi]⩽ϵ ，且h的估计概率大于 1−δ ，其中 0⩽ϵ,δ⩽12 。弱学习则只要求存在某个子集满足即可。