逻辑回归是一种广义线性模型,通过对数概率函数,将线性函数的结果进行映射,从而将目标函数的取值空间从((- infty ,+infty ))映射到了((0,1)),从而可以处理分类问题。注意:逻辑回归是一种分类算法。
又称
对数几率函数,
sigmoid函数等。函数表达式:[ g(z)=frac{1}{1+e^{-z}} ]s形曲线,值域:((0,1))
且其导数满足:[ g'(z)=g(z)(1-g(z)) ]
梯度的本质是一个向量(矢量),表示某一函数在该点处的方向导数沿着该方向能够取得最大值,即函数在该点处沿着梯度的方向变化最快,变化率最大。
参见:梯度-百度百科
二项逻辑回归模型的条件概率分布:[ P(Y=1|X)=frac{1}{1+e^{-theta ^Tx}}\ P(Y=0|X)=1-frac{1}{1+e^{-theta ^Tx}} ]其中,(xin R^n)是输入,(Yin {0,1})是输出,(theta ^T)是待学习参数。对于给定的输入实例(X),将样本(X)输入到上述公式中求得(P(Y=1|X))和(P(Y=0|X)),比较两个条件概率值,将样本归到条件概率值较大的那一类。
sigmoid函数
构造对应的最大似然:[ L(theta)=prod{i=1}^mP(yi|xi;theta)=prod{i=1}^{m}(h{theta}(xi))^{yi}(1-h{theta}(xi))^{1-yi} ]两端取对数:[ l(theta)=logL(theta)=sum{i=1}^{m}(yilogh{theta}(xi)+(1-yi)log(1-h{theta}(x_i))) ]为简化问题,现在以只有一个训练样本的情况为例(实际这种情形就是随机梯度下降):[ l(theta)=ylogh{theta}(x)+(1-y)log(1-htheta(x))\ ]对参数(theta)求偏导:[ frac{partial}{partial thetaj} l(theta)=(yfrac{1}{g(theta^Tx)}-(1-y)frac{1}{1-g(theta^Tx)})frac{partial}{partial thetaj}g(theta^Tx)\ frac{partial}{partial thetaj} l(theta)=(yfrac{1}{g(theta^Tx)}-(1-y)frac{1}{1-g(theta^Tx)})g(theta^Tx)(1-g(theta^Tx))frac{partial}{partialthetaj}theta^Tx\ 该步使用g'(z)=g(z)(1-g(z))\ frac{partial}{partial thetaj} l(theta)=(y(1-g(theta^Tx))-(1-y)g(theta^Tx))xj\ 注意:frac{partial}{partial thetaj}theta^Tx=xj,xj为样本x的第j个特征\ frac{partial}{partial thetaj} l(theta)=(y-h{theta}(x))xjqquad 整理结果 ]求得参数梯度,现在希望最大化似然函数,因此梯度上升,迭代参数。参数(theta)的迭代公式:[ theta{j+1}:=thetaj+alpha(y-h{theta}(x))xj ]其中,(alpha)为学习率,((y-h{theta}(x))xj)为上述所求得的梯度
推广至m个样本:[ theta{j+1}:=thetaj+alphafrac{1}{m}sum{i=1}^m(y^i-h{theta}(x^i))x^{i}_j ]
输入:训练数据集$T={(x1,y1),(x2,y2),...,(xm,ym)},x1in X subseteq R^n,y1in Y subseteq R^n $
输出:逻辑回归模型(hat f(x))
在实际应用中,为了提高算法收敛速度和节省内存,在迭代求解时往往采用高效的优化算法如LBFGS、信赖域算法,这些算法是基于批量处理的,无法高效处理超大规模数据集,也无法对线上模型进行快速实时更新。随机梯度下降是相对批处理的另一种优化算法,每次只用一个样本更新模型权重。谷歌的FTRL就是基于随机梯度下降的一种逻辑回归优化算法。
FTRL算法参见:各大公司广泛使用的在线学习算法FTRL详解1.逻辑回归应用
逻辑回归适合用来学习需要大规模训练的样本和特征,对于计算广告等有天然优势。其缺点是:1.模型表达能力弱,需要大量的特征组合提高特征的表达;2.模型简单,容易欠拟合。
对逻辑回归的求解有很多优化方法,如
BFGS、
LBFGS、共轭梯度法、信赖域法,其中前两种是牛顿法的变种,
LBFGS算法是
BFGS在内存受限情况下的近似优化;针对逻辑回归在线学习的稀疏性和准确性,逻辑回归又有
FOBOS、
RDA和
FTRL等变种。
逻辑回归需要注意正则化问题,(L_1)正则(又称
LASSO)假设模型参数满足拉普拉斯分布,(L_2)正则(又称
RIDGE)假设模型参数满足高斯分布。参见:变量的选择——Lasso&Ridge&ElasticNet,线性回归中的抗过拟1.逻辑回归练习题,参见:10道题带你了解逻辑回归模型
答:可以,神经网络是一个通用的逼近算法,所以它可以实现逻辑回归。
答:逻辑回归使用最大似然估计来训练回归模型。
答:AIC最小的逻辑回归模型最佳。
答:非必须,特征标准化的主要目的是实现模型的最优化。
答:LASSO,RIDGE等。
逻辑回归无法学习到特征间的组合关系,而特征组合关系在推荐中是比较常见的。例如,同一个用户在不同时间或地点感兴趣的广告是不同的,在这里就需要对表征用户的特征,表征时间的特征,表征地点的特征进行组合,以获得较好的预测。利用模型做特征组合,可以使用支持向量机的核函数来实现特征之间的交叉,但是多项式核函数的问题在于二次参数过多,设特征维数为(n),则二次项的参数数目为(frac{n(n+1)}{2}),增加模型复杂度并且获得的特征矩阵十分稀疏,降低模型表现。因子分解机及场感知因子分解机能够自动做特征组合,并且算法效率较高。
向量点乘输出标量,运算的数学表示:(<·,·>)[
此时,二次项组合参数就可以被分解为:[ W=VV^T=begin{pmatrix} v1\ v2\ ...\ vn end{pmatrix}begin{pmatrix} v1^T ,v2^T, ..., vn^T end{pmatrix} ]将组合参数进行分解的优势:
参数因子化使得组合特征(xhxi)和(xixj)不再相互独立,(xhxi)和(xixj)的系数分别为(
上述因子分子机公式是一个通用的拟合方程,可以采用不同的损失函数解决分类、回归问题,如采用均方差损失函数,就可以使用该拟合方程求解回归问题。
因子分解机的计算复杂度,考虑计算量最大的二次项:[ sum{i=1}^nsum{j=i+1}^n
可以先把标量(xi)和对应的隐向量(vi)相乘,并存储下来,即:[ ui=xiv_i ]则上式变为:[ sum{i=1}^nsum{j=i+1}^n
因此二次项可变为:[ begin{split} sum{f=1}^k(sum{i=1}^nsum{j=i+1}^nu{i,f}u{j,f})&=frac{1}{2}sum{f=1}^{k}(sum{i=1}^nsum{j=1}^nu{i,f}u{j,f}-sum{i=1}^nu{i,f}^2)\ &=frac{1}{2}sum{f=1}^k((sum{i=1}^nu{i,f}^2)-sum{i=1}^nu_{i,f}^2) end{split} ]完整的变换:[ begin{split} sum{i=1}^nsum{j=i+1}^n
因子分解机任意两组特征交叉的隐向量都是相关的,这实际上限制了模型的复杂度。但如果任意两组特征组合是完全独立的,这与支持向量机核函数来计算特征交叉类似,有着极高的复杂性和自由度,模型计算过于复杂。场感知因子分解机是两者的折中。
场感知因子分解机把具有相同性质的特征都归于同一个“场”,按照场级别分别计算当前特征与其它场里特征组合时的特征向量。即认为不同场的特征是相互独立的,同一场内的特征是不独立的。
在场感知因子分解机中,每一维的特征(xixj),针对其它特征的每一种场(fifj)组合,都会学习一个隐变量(v{i,fj}v{j,fi}),每个特征属于某个特定的场。每个特征将映射出多个隐向量,每个隐向量对应一个场,这也就是说,一个特征在不同场中对应的隐向量是不同的。当两个特征组合时,它们分别使用这两个特征对应场的隐向量做内积。场感知因子分解机的模型方程为:[ phi {FFM}(w,x)=sum{i=1}^{n}sum{j=i+1}^n
在因子分解机中,每一维特征的隐向量只有一个,因此因子分解机可以看作是场感知因子分解机的特例,即因子分解机是把所有特征都归属到一个场时的场感知因子分解机。
场感知因子分解机可以自动做特征组合和处理高维稀疏特征,因此它在处理大量离散特征的问题上往往有比较好的效果。使用场感知因子分解机时要注意对连续特征做归一化或离散化。
因子分解机、场感知因子分解机和其它模型的对比关系:
因子分解机由于计算复杂度的限制,只用到了二阶特征组合。对于高阶特征组合,可以通过多层的神经网络即DNN解决。但对于稀疏高维特征,直接输入DNN中,将导致网络参数过多:

类似于场感知因子分解机的思想,将特征分为不同的“场”:

然后再加两层全连接层,那么就可以把特征组合出来了。但是这样,低阶特征和高阶特征的组合隐含地体现在隐层中,将低阶特征组合单独建模,然后融合高阶特征组合,能够更为充分的保留信息。也就是说,将DNN和因子分解机进行合理的融合:

这里有一个子问题:传统的机器学习算法和深度学习的结合。二者的融合总的来说有两种方式:一是并行结构,二是串行结构:


而DeepFM是并行结构的典型代表。
对照上述的网络融合中的并行结构,DeepFM的模型结构:
DeepFM包含两个部分:神经网络和因子分解机,这两部分共享同样的输入。
神经网络部分是一个前馈神经网络,可以学习高阶特征组合。注意:输入是高维稀疏数据,如onehot处理后的数据,因此需要引入embedding layer将输入向量压缩到低维稠密向量:
其中,(k)即是embedding size。这里神经网络做嵌入的过程,和因子分解机中二阶特征组合的过程是一致的,因此在因子分解机中得到的隐向量(v_{ij})现在作为了嵌入层的权重,参见[论文精读-DeepFM](https://blog.csdn.net/zynash2/article/details/79348540)。另外,尽管不同“场”的输入维度不同,经过嵌入后,向量长度均为(k)。
在嵌入层,因子分解机和神经网络的参数是共享的。因子分解机中的参数会参与到梯度下降中,可以理解为直接用神经网络做嵌入,无疑比因子分解机本身的嵌入能力更强。
共享嵌入带来两个好处:
和上述的因子分解机相同,可以观察到上图FM Layer中黑线表示的一阶特征组合,红线表示的二阶特征组合。
DeepFM的预测结果由神经网络和因子分解机共同决定:[ y=sigmoid(y{FM}+y{DNN}) ]
另外,出现了DeepFM的升级版xDeepFM,参见:推荐系统遇上深度学习(二十二)--DeepFM升级版XDeepFM模型强势来袭!
本部分代码示例参见:CTR预估算法之FM, FFM, DeepFM及实践
梯度提升树是一种基于回归树的集成学习方法,通过构造多个弱的回归树作为基学习器,并将这些树的结果累加起来作为最终的预测输出。
二阶泰勒展开:[ f(x+Delta x)=f(x)+frac{partial f}{partial x}Delta x+frac{1}{2}frac{partial ^2f}{partial x^2}Delta x^2+o(Delta x) ]
示例:对(L(y,hm(x)+beta f(x)))进行一阶泰勒展开,令((y,hm(x)))为(x),(beta f(x))为(Delta x),则:[ L(y,hm(x)+beta f(x))approx L(y,hm(x))+beta f(x)frac{partial L(y,hm(x))}{partial hm(x)} ]
梯度提升树是集成学习Boosting家族的一员,在训练时采用前向分步算法,首先确定第一棵树拟合的值,然后基于之前所有树的误差来更新并训练下一棵树,一步一步迭代下去直到梯度提升树构建完毕。
简单起见,首先介绍与梯度提升树相近的提升树(
Boosting Tree)。
输入:训练数据集(T={(x1,y1),(x2,y2),...,(xN,yN)},x_iin Xsubseteq mathbb{R}^n,yin Ysubseteq{R})
输出:提升树(f_M(x))
1.初始化(f_0(x)=0)1.对(m=1,2,...,M):
a. 计算残差:(r{mi}=yi-f{m-1}(xi),quad i=1,2,...,N)
其中,(f_{m-1}(x))为第(m-1)步时回归树加和的模型
b. 拟合残差(r{mi})学习一个回归树,获得(T(x;Thetam))
其中,(T(x;Theta_m))是第(m)步的训练获得的基学习器,通过*经验风险最小化*确定这棵树的参数:[ Thetam=mathop{argmin}sum{i=1}^NL(yi,f{m-1}(xi)+T(x;Thetam)) ]对于回归问题而言,(L(y,hat{y}))可采用平方损失误差
c. 更新(fm(x)=f{m-1}(x)+T(x;Theta_m))1.获得回归问题的提升树:[ fM(x)=sum{m=1}^MT(x;Theta_m) ]
在提升树中,每一棵树的生成采用的训练数据都是上次预测结果与真实值的残差,这个残差会不断减小。
这实际就是前置知识中
加法模型的典型应用。注意:由于这里基学习器是回归树,叶子节点的值是实数值,因此基学习器前的系数可省略。1.梯度提升树GBDT
梯度提升树的算法流程与提升树类似,只是不再使用残差作为一棵树的拟合目标,而是使用损失函数的梯度作为拟合目标。梯度提升算法利用最速下降法的近似方法,考虑经验损失函数:[ sum{i=1}^NL(yi,f{m-1}(xi)+beta f(x_i)) ]其中,(N)为样本数,(f{m-1}(xi))为第(m-1)步时所有树的累加,(beta)为基学习器的系数,(f(x_i))为本次要训练的树,即:[ f(x)=sum{j=1}^JcjI(xin R_j) ]简单起见,考虑一个样本,对损失函数进行一阶泰勒展开:[ L(yi,f{m-1}(xi)+beta f(xi))=L(yi,f{m-1}(xi))+beta f(xi)frac{partial L(yi,f{m-1}(xi))}{partial f{m-1}(x_i)} ]由于(beta)是大于0的,要使(L(yi,f{m-1}(xi)+beta f(xi))leq L(yi,f{m-1}(x_i))),令[ f(xi)=-frac{partial L(yi,f{m-1}(xi))}{partial f{m-1}(xi)} ]每一个样本点上,上式尽可能成立的(f(x_i))就是我们本次要构建的树。
简言之,对损失函数(L(y,hat{y}))求关于(f(x))的偏导,然后带入(f_{m-1}(x)):[ r{mi}=-[frac{partial L(yi,f(xi))}{partial f(xi)}]{f(x)=f{m-1}(x)} ]就是每一步上,一棵树需要拟合的目标。
梯度提升树算法流程
输入:训练数据集(T={(x1,y1),(x2,y2),...,(xN,yN)},xiin X subseteq mathbb{R}^n,yiin Y subseteq mathbb{R});损失函数(L(y,f(x)))
输出:回归树(hat{f(x)})
1.初始化[ f0(x)=mathop{argmin}csum{i=1}^NL(yi,c) ]1.对(m=1,2,...,M):a. 对(i=1,2,...,N),计算[ r{mi}=-[frac{partial L(yi,f(xi))}{partial f(xi)}]{f(x)=f{m-1}(x)} ]
b. 对(r{mi})拟合一个回归树,得到第(m)棵树的叶节点区域(R{mj},j=1,2,...,J)
c. 对(j=1,2,...,J),计算[ c{mj}=mathop{argmin}csum{xin R{mj}}L(yi,f{m-1}(x_i)+c) ]
d. 更新(fm(x)=f{m-1}(x)+sum{j=1}^Jc{mj}I(xin R_{mj}))1.获得回归树:[ hat{f(x)}=fM(x)=sum{m=1}^Msum{j=1}^Jc{mj}I(xin R_{mj}) ]
同样,梯度提升树的基学习器是回归树,加法模型中每个基学习器前的系数会内化到回归树内部,因此可省略。
注意到当使用(r_{mi})拟合出一个回归树后,2-c进一步使用整体损失函数对这棵回归树的值进行了优化。这就是”先局部,后整体“的思想,就是先通过逐步的局部优化获得一个结果,然后从全局的角度优化结果。决策树的生成和剪枝也是这样,先通过局部优化,如信息增益等指标选择特征,得出一个决策树;再从降低整体损失的角度,进行剪枝。
梯度提升树和提升树的关系:
提升树每一次提升都是用上次的预测结果和训练数据真实值的误差作为新的训练数据进行进一步学习,而梯度提升树把对误差的拟合替换为对损失函数梯度的拟合。提升树主要缺点有:在回归问题中,提升树的平方损失目标函数对于异常值特别敏感;对于一些损失函数,不易优化,如绝对值损失函数等。1.XGBoost
XGBoost是Boosting Tree的一种实现,相比于梯度提升树,XGBoost对损失函数进行了二阶泰勒展开,同时用到了一阶和二阶导数;并且引入了适用于树模型的正则化项用于控制模型的复杂度,正则化项包含树的叶子节点个数、叶子节点分数的(L_2)正则。
目标函数:[ Obj(Theta)=L(Theta)+Omega (Theta)\ Obj=sum{i=1}^nl(yi,hat{yi})+sum{k=1}^KOmega(f_k) ]可以看到,目标函数包含两个部分:训练误差和树的复杂度。其中,树的复杂度包括:a.树的深度;b.内部节点个数;c.叶子节点个数(T);d.叶子节点分数(w)
和梯度提升树的思路一致,[ begin{split} Obj^{(t)}&=sum{i=1}^nl(yi,hat{y{i}}^{(t)})+Omega(ft(x))\ &=sum{i=1}^nl(yi,hat{y{i}}^{(t-1)}+ft(xi))+Omega(ft)+constant end{split} ]思考如何寻找一个(f_t)来优化这个目标函数。
这里和梯度提升树不同,XGBoost进行了二阶泰勒展开,令(x=(yi,hat{yi}^{(t-1)}),Delta x=ft(xi)):[ Obj^{(t)}approx sum{i=1}^n(l(yi,hat{yi}^{(t-1)})+gift(x)+frac{1}{2}hift^2(xi))+Omega(f_t)+constant ]其中,(gi)为一阶导,(hi)为二阶导[ gi=frac{partial l(yi,hat{y}^{(t-1)})}{partial hat{y}^{(t-1)}},\ hi=frac{partial ^2 l(yi,hat{y}^{(t-1)})}{{partial hat{y}^{(t-1)}}^2} ](l(yi,hat{yi}^{(t-1)}))为常数项;(ft(x)=W{q{(x)}})为决策树表征的函数,(win mathbb{R}^T)表示树的叶子权重,(q(x))表示树结构,这是上述对决策树(f(x)=sum{j=1}^JcjI(xin Rj))的另一种记法。
去除目标函数中的常数项:[ Obj=sum{i=1}^n(gift(xi)+frac{1}{2}hift^2(xi))+Omega(ft) ]
定义叶子(j):[ Ij={i|q(xi)=j} ]表示第(j)个叶子中的样本,其中(q(xi))表示样本(xi)所属的叶节点[ begin{split} Obj^{(t-1)}&approx sum{i=1}^n(gift(xi)+frac{1}{2}hif^2t(xi))+Omega(ft)\ &=sum{i=1}^n(giw{q(xi)}+frac{1}{2}hiw^2{q(xi)})+gamma T+lambda frac{1}{2}sum{j=1}^Twj^2\ &=sum{j=1}^T((sum{iin Ij}gi)wj+frac{1}{2}(sum{iin Ij}hi+lambda)wj^2)+gamma T end{split} ]现在希望将(n)个样本组成的目标损失,转化为(T)个叶子节点的目标损失,令:[ Gj=sum{iin Ij}gi\ Hj=sum{iin Ij}hi ]目标损失变为:[ begin{split} Obj^{(t)}&=sum{j=1}^T((sum{iin Ij}gi)wj+frac{1}{2}(sum{iin Ij}hi+lambda)wj^2)+lambda T\ &=sum{j=1}^T(Gjwj+frac{1}{2}(Hj+lambda)wj^2)+lambda T end{split} ]求一个树结构下能够获得的目标函数的最小值
求目标函数关于(wj)的偏导,并令该偏导(frac{partial Obj}{partial wj}=0),可得:[ wj^/*=-frac{Gj}{H_j+lambda} ]因此,对一个树结构而言,能够得到的目标函数的最小值:[ Obj^/*=-frac{1}{2}sum_{j=1}^Tfrac{G_j^2}{H_j+lambda}+gamma T ]其中,(Gj)为叶子节点(j)中样本的一阶导,(Hj)为叶子节点(j)中样本的二阶导,(T)为叶子节点数,(lambda)为正则化系数。
在所有可能的树结构中,(Obj^/*)越小,该树结构越好。因此,现在考虑如何寻找这个最优的树结构。

求最优树结构
最直白的方法就是列举所有的树结构,在其中选择(Obj^/)最小的作为最佳树结构,但是这实际是一个(NP)难问题。在实践中,通常使用树的精确贪婪学习*:
类似于ID3的信息增益、C4.5的增益率、CART的基尼指数,定义XGBoost选择最优特征的准则:[ Gain=frac{GL^2}{HL^2+lambda}+frac{GR^2}{HR^2+lambda}-frac{(GL+GR)^2}{HL+HR+lambda}-gamma ]遍历所有的特征,计算
Gain值,选择最大的特征进行分割[ begin{split} &for k: 0to K: quad /# 对每个节点\ &quad for d:0to D:quad /# 对每个特征\ &qquad for n:0to N:quad /# 对每个实例\ &qquadquad 在0to N中,实例排序的时间复杂度为O(nlog(n)) end{split} ]因此,深度为(k)的树,总的时间复杂度为(O(ndklog(n)))
注意到,对于每个节点,也就是每一步构建子树时,寻找最佳分裂点有两层含义:a.寻找特征中最优的分裂值;b.寻找最优的特征
为了降低时间复杂度,可以采用一些近似算法:对于每个特征,只考虑分位点,
就是把一些样本捆绑在一起,形成
bin,这样就能降低最终要排序的样本数量。实际上,XGBoost不是简单的按照上图那样,按照样本个数进行分位,而是以二阶导数值作为权重:
之所以使用(h_i)加权,是因为目标函数可以被整理成下式:[ Obj=sum{i=1}^nfrac{1}{2}hi(ft(xi)-frac{gi}{hi})^2+Omega(f_t)+constant ]可以看到,(h_i)对loss有加权的作用。
另外,观察XGBoost的最优特征准则:[ Gain=frac{GL^2}{HL^2+lambda}+frac{GR^2}{HR^2+lambda}-frac{(GL+GR)^2}{HL+HR+lambda}-gamma ]其中,等式右侧前半部分表示训练
loss的减少,(gamma)为
正则化。上式有可能是负的,也就是说,
loss的减少比正则化力度还要小时,分裂的增益会是负的。因此类似于
预剪枝和
后剪枝,有两种训练策略:
XGBoost的其它特性:
XGBoost论文地址:XGBoost: A Scalable Tree Boosting System
XGBoost官网:XGBoost Documentation1.LightGBM
与XGBoost的不同:
把连续的浮点特征值离散化为k个整数,同时构造一个宽度为k的直方图。在遍历数据时,根据离散化后的值作为索引,在直方图中计算统计量。当遍历一次数据后,直方图计算了需要的统计量,然后根据直方图的离散值,遍历寻找最优分割点。
优势:减少了内存占用;减少了分裂点计算增益时的计算量
一个叶子的直方图可以由它的父节点的直方图与它的兄弟节点的直方图,做差而得,提升一倍速度。

XGBoost是
Level-wise,LightGBM是
Leaf-wise

总而言之,LightGBM特性:
LightGBM论文地址:Lightgbm: A highly efficient gradient boosting decision tree
LightGBM官网:LightGBM Documentation