神刀安全网

算法篇: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 。弱学习则只要求存在某个子集满足即可。

下面更详细阐述Adaboost算法框架:

假设样本集 T={(x1,y1),⋅⋅⋅,(xN,yN)} ,其中 xi 为参数的属性向量, yi 为 0或1,首先初始化数据权值:

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

其中 w1,i 下标1表示第一次弱分类迭代,i表示第i个样本。

假设弱分类器 hm(x),m=1,2,⋅⋅⋅,M ,其在原始样本迭代学习下可得到相应的符号性输出:

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

据此进一步计算该分类误差 εm

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

上述误差率是利用样本权重加权的误差,通俗可理解为样本的平均误差。得到分类器 hm(x) 的误差率,进一步可以衡量该分类器的权重 am

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

如此我们进入迭代循环,重新分配样本的权重: 

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

其中:

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

当分类结果与实际结果一致时, e的指数部分为负,结果不同时, e的指数部分为正,如此通过重新更新权重,对于分类错误的点将赋予更高的权重,对于分类正确的点,将降低其权重。这样在下一轮迭代中,对于正确分类上一轮误判点的分类器,将更容易通过设定的条件阈值。

如此重复式(12)-(16),直至 m=M ,构建最终分类器 H(X) : 

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

通过此,通过迭代M个弱分类器,集成产生一个强分类器。

4. SGD + logistics + Adaboost;

上文简述了三个理论算法,同时也简单涉及到体系,下面将更加系统地将上述三个理论融合在一起,形成一套科学完善的体系。

一般在开展理论算法之前,理解需求和业务背景是首要,由于业务背景因平台而异,所以这里不多说,其次是模型的特征工程,一般特征工程包括缺失值处理,数据规约,降维等,实证部分对此将会介绍一些方法和手段,完成上述两步,就可以开始算法的构建,下面系统阐述本文的理论:

首先将特征工程一步的结果输入算法,为样本赋予初始权重:

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

其次构建一个logistics弱分类器:

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

通过梯度下降估计参数:

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

每次迭代估计利用式(21)分类错误率进行判断选择,其中为简化表达式,令偏执项 a=βo ,此外上标j表示样本索引编号,下标i表示样本维度索引编号,其中 j=1,2,⋅⋅⋅,N,i=0,1,2,⋅⋅⋅,K

计算分类错误率:

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

计算分类器权重 a1

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

更新样本权重,重新训练分类器:

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

其中:

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

重复式(17)-式(22)M次后,构建最终强学习模型:

算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

如此,一套较为完整的理论体系初步构建完成,下面通过实证部分经一部评估解析该理论。

(未完待续)… …

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 算法篇:SGD+logistic+Adaboost构建快速迭代增强式LR模型(一)

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址