Logistic Regression

Logistic Regression

目录

• Logistic Regression
  • 模型介绍
    • 优化方法
      • Steepest descent
      • 牛顿方法
      • Iteratively reweighted least square
      • Quasi-Newton methods
      • L2正则
    • 多类别
  • 贝叶斯角度的逻辑回归
    • Gaussian approximate
      • Guassion approximate for Logistic Regression
      • Approximatting the posterior predictive
  • Online Learning and stochastic optimization
  • 生成方法和判别方法的对比
    • Fisher线性判别分析
      • 二分类问题
    • 拓展至多维

模型介绍

​ 逻辑回归作为一个判别模型，其形式如下：

[p(y=1vert mathbf x)=Berleft(yvert ext{sigm}left(mathbf w^Tmathbf x ight) ight) ]

参数为(mathbf{w})，假设(yin left {0,1 ight })，得到NLL

[NLL=-sum_{i=1}^Ny_ilog^{u_i}+(1-y_i)log^{1-u_i} ag{1}label{1} ]

​ 与Linear Regression不同，极大化NLL得不到解析解，对上式求导得到梯度和Hessian矩阵

[egin{align*} mathbf{g}&=sum_i^Nleft(u_i-y_i ight)mathbf x_i =X^Tleft(mathbf u -mathbf y ight)\ mathbf{H}&=sum_i^N u_ileft(1-u_i ight)mathbf x_imathbf x_i^T=X^TSX end{align*} ]

式中(S= ext{diag}left(u_ileft(1-u_i ight) ight))，可以看出H为正定矩阵

优化方法

​ 对于无约束的凸优化问题(eqref{1})，可以采用Steepest descent、Newton's method、Iteratively reweighted least square、Quasi-Newton's methods等方法求解

Steepest descent

​ 在二范数下，Steepest descent的下降方向为负梯度方向，即(-mathbf g)（可查阅之前的凸优化章节）

[mathbf w^{t+1} = mathbf w^{t}-etamathbf g ]

(eta)为学习率

牛顿方法

​ 牛顿方法是二阶方法，其求解步骤如下

• 设定初始点(mathbf x_0)以及收敛条件(epsilon)
• 计算(lambda(mathbf x))，并与收敛条件进行比较，但尚未收敛时执行以下步骤
• 计算(Deltamathbf x_{st}=-mathbf H^{-1}mathbf g)，根据计算的步长(eta)，对参数(mathbf w)进行更新

​ 可以看出牛顿方法需要对矩阵进行求逆，因此即使(mathbf H)可逆，当遇到大规模问题时，逆计算开销很大。后续的Quasi-Newton methods会对这方面进行优化，用一些方法得到近似的(mathbf H)。

Iteratively reweighted least square

​ 当使用牛顿法解(eqref{1})时，得到参数(mathbf w)的迭代过程如下

[egin{align*} mathbf w^{t+1} &=mathbf w^{t}-mathbf H^{-1}mathbf g\ &= mathbf w^{t}-left(X^TSX ight)^{-1}X^Tleft(mathbf u - mathbf g ight)\ &=left(X^TSX ight)^{-1}left[left(X^TSX ight)mathbf w-X^Tleft(mathbf u -mathbf g ight) ight ]\ & = left(X^TSX ight)^{-1}X^Tleft(SXmathbf w-(mathbf u -mathbf y) ight)\ & =left(X^TSX ight)^{-1}X^TS z ag{2}label{2} end{align*} ]

式中(z=Xw-S^{-1}(mathbf u-mathbf y))，结合线性回归的Normal Equation，可以发现上述(mathbf w^{t+1})的解析式是(sum_limits{i}^NS_ileft(z_i-mathbf w^Tmathbf x_i ight)^2)的极小值。(S_i)可以被看为权重，在迭代(mathbf w)时其会发生变化，这也是Iteratively reweignted least square名字的由来。算法流程如下：

1. 初始化(mathbf w)
2. 根据(eqref{2})计算更新(mathbf w)
3. 迭代至收敛

Quasi-Newton methods

​ 为了避免牛顿方法中的矩阵逆运算，Quasi-Newton methods使用近似的(mathbf H)来进行运算。这里介绍两种方法：BFGS和L-BFGS。两方法有相似之处，都是基于(eqref{3})展开的。

​ 根据泰勒展开可以得到

[f(mathbf x^{t})=f(mathbf x^{t+1})+ abla f(mathbf x^{t+1})^TDelta mathbf x+frac 1 2 Delta mathbf x^T abla^2 f(mathbf x^{t+1})Delta mathbf x ]

在上式中对(mathbf x^{t})求导

[ abla f(mathbf x^{t})= abla f(mathbf x^{t+1})+ abla^2 f(mathbf x^{t+1})(mathbf x^{t}-mathbf x^{t+1}) ag{3}label{3} ]

​ 令

[egin{align*} B^{t}&= abla^2 f(mathbf x)\ Delta s^{t}&=mathbf x^{t+1}-mathbf x^t\ Delta y^{t} &= abla f(mathbf x^{t+1})- abla f(mathbf x^{t}) end{align*} ]

BFGS方法认为

[B^{t+1}=B^{t}+mVV^T+nUU^T ]

带入(eqref{3})中得到

[mVV^TDelta s^t+nUU^TDelta s^t = Delta y ^t-B^tDelta s^t ]

假设一种特殊情况

[egin{align*} mVV^TDelta s^t &= Delta y^t\ nUU^T Delta s^t &= -B^t\ mV^TDelta s^t&=1\ nU^T Delta s^t&=-1 end{align*} ]

可以解得(U,V,m,n)，得到(B)的迭代关系如下

[B^{t+1}=B^{t}+frac{Delta y^{t}{Delta y^t}^T}{Delta y^T Delta s}-frac{Delta B^tDelta s^t Delta s^TB^t}{Delta s^T B^t Delta s^t} ]

由于(mathbf d = -mathbf H^{-1}mathbf g)，在求下降方向时经常会使用(mathbf H^{-1})，下面对其进行近似。

对上述关系应用两次Sherman-Morrion公式

[(A+uv^T)^{-1}=A^{-1}-frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u} ]

得到（这部分推导比较繁琐，参阅zhirom博客）

[C^{t+1}=(I-frac{Delta s^{t}Delta y^T}{Delta s^TDelta y^t})C^{t}(I-frac{Delta y^tDelta s^T}{Delta s^T Delta y^t}) ag{4}label{4} ]

整体的BFGS算法流程如下

1. 初始化(mathbf x_0)，令(B_{0}=I)
2. 确定搜索方向(mathbf d = -B_k^{-1}mathbf g_k)
3. 利用exact line search或者backtracting line search确定搜索步长，得到(mathbf x_{k+1}=mathbf x_k-lambda_k mathbf d_k)
4. 计算(mathbf g_{k+1})，若不收敛时继续执行
5. 利用(eqref{4})得到(C_{k+1})，返回第二步

L-BFGS方法是在BFGS基础上舍弃了对矩阵的保存，仅保留了最近的m个(s_k\,y_k)结果，节约了内存空间。在计算(mathbf H^{-1}mathbf g)时使用了two-loop recursion，暂时不清楚这个计算方法的原理，在这里不写出，可参阅星环科技-知乎回答一文。

L2正则

​ 如果给定的数据集是线性可分的，那么(mathbf w)进要满足一定比例即可，那么(Vert mathbf wVert o +infin)也是可以的，这样得到的图形就格外陡峭，容易过拟合。

​ 如果在NLL中添加(L_2)正则项，那么获得的即为MAP估计，相比于之前的MLE估计，梯度和Hessian矩阵迭代关系如下

[egin{align*} mathbf g &= X^T(mathbf u -mathbf y)+lambda mathbf w\ mathbf H &= X^T mathbf S X+lambda mathbf I end{align*} ]

多类别

​ 当考虑的类别数量多余2时，其形式如下

[p(y=cvert mathbf x, mathbf W)=frac{e^{mathbf W_c^Tmathbf x}}{sum olimits_i^C e^{mathbf W_i^Tmathbf x}} ]

令

[egin{align*} u_{ic} &= p(y=cvert mathbf x, mathbf w_c)\ mathbf eta_i &= mathbf W^T mathbf x\ y_{ic} &= ext{Ⅱ}(y_i =c) end{align*} ]

令系数矩阵(mathbf W)的最后一列为0，即不对最后一类的系数进行估计（在分子和分母同除非零数并不影响结果）。得到NLL

[l(mathbf W)=-sum_i^Nleft((sum_c^C y_{ic} eta_{ic})-log^{sum olimits_{c'}u_{ic'}} ight) ]

得到

[egin{align*} mathbf g &= sum_i^N (mathbf u_i-mathbf y_i)otimes mathbf x_i=X^T(mathbf u-mathbf y) \ mathbf H &= sum_i^N (diag(u_i)-mathbf u_imathbf u_i^T) otimes(mathbf x_imathbf x_i^T) end{align*} ]

假设(mathbf W)先验为(p(mathbf W)=Pi_c^C N(mathbf w_cvert0,mathbf V_0))，得到

[egin{align*} mathbf g &= sum_i^N(mathbf u_i-mathbf y_i)otimes mathbf x_i+lambdamathbf V_0^{-1}sum mathbf w_c\ mathbf H &=sum_i^N(diag(mathbf u_i)-mathbf u_i mathbf u_i^T) otimes mathbf x_i mathbf x_i^T+lambda mathbf I_Cmathbf V_0^{-1} end{align*} ]

贝叶斯角度的逻辑回归

Gaussian approximate

​ 不同于之前的线性回归，很难找到逻辑回归的共轭先验。

[p( hetavert D)=frac {1}{ ext{Z}}e^{-E( heta)} ag{5}label{5} ]

式中Z为规整系数的常数项，可以理解为(p(D))，(E( heta))应具有(-log ^{p(D, heta)})的形式。

对(E( heta))进行泰勒展开

[egin{align*} E( heta)&=E( heta^*)+ abla E( heta)^T( heta - heta^*)+frac 1 2 ( heta - heta^*)^T abla^2 E( heta^*)( heta - heta^*)\ &= E( heta^*)+frac 1 2 ( heta - heta^*)^T abla^2 E( heta^*)( heta - heta^*) end{align*} ]

可以得到(eqref{5})的形式近似于高斯分布

[egin{align*} p( hetavert D)&sim N( hetavert heta^*, abla^2Eleft( heta^* ight)^{-1})\ p(D)&=(2pi)^{frac D 2}vert abla^2 E( heta^*) vert^{-frac 1 2}e^{-E( heta^*)} end{align*} ]

当对(p(D))进行变换时可以得到BIC的形式

[egin{align*} log^{p(D)}&approx log^{p(Dvert heta^*)}+log^{p( heta^*)}-frac{1}{2}log^{vert abla^2 E( heta^*)vert }\ &approxlog^{p(Dvert hat heta)}-frac D 2log^N end{align*} ]

上式中忽略了常数项，且默认(p( heta)propto1)，由于(vert abla^2E(hat heta)vert=sum olimitsleftvert H_i ightvert)（参考(eqref{1})），假设所有的Hessian矩阵相同。

Guassion approximate for Logistic Regression

​ 假设(p( heta)sim N( heta vert mathbf 0, mathbf V))，根据上述公式可以得到

[egin{align*} mathbf heta &= argmin log^{E( heta)}\ &= argmin log^{p( heta)}+log^{p(Dvert heta)} end{align*} ]

上述的式子和[L2正则](# L2正则)类似。在得到(hat heta)后就得到了Laplace approximation后验分布。

MAP和Laplace approximateion比较

Approximatting the posterior predictive

​ 在得到参数的后验分布后，对(p(yvert D, heta))进行估计

[p(yvert D, heta)=int p(yvert heta) p( hetavert D)d heta ]

当然可以采用插值法，比如(hat heta, E( heta))等，但是这样的方法会导致误差较大。可以采用Monte Carlo approximation的方法对( heta)取样，计算平均的(p(y))

Online Learning and stochastic optimization

​ 与离线训练确定参数不同，线上学习是不断应用于新数据、调整参数。

[mathbf heta_k = mathbf heta_{k-1}-eta_{k-1}mathbf g_{k1} ]

上述的Online gradient descent可以用来对参数进行更新。

​ stochastic optimization是说在目标函数中有随机变量，如

[ heta^* = argmin Eleft(f( heta, D) ight) ]

可以利用online gradient descent 对stochastic optimization进行计算，

在设置学习率(eta)时需要满足Robbins-Monro条件，以保证收敛。

[egin{align*} sum eta &= +infin\ sum eta^2 & < +infin end{align*} ]

如：

• (eta_k=frac 1 k)
• (eta_k=( au_0+k)^{-kappa})

生成方法和判别方法的对比

生成方法和判别方法的根本区别是判别方法通常极大化(p(yvert mathbf x, mathbf w))，而生成方法则为(p(y, mathbf xvert mathbf w))。两个方法的优缺点对比如下：

1. 生成方法计算通常更简单，如朴素贝叶斯，通过参数的加减即可得到参数的分布；
2. 判别模型对特征的处理更方便，生成模型通常对特征假设了分布，如果进行特征的变换，则很可能与假设产生矛盾。

Fisher线性判别分析

高斯判别分析时（注意这是一个生成模型）在高维数据时时常会遇到一些问题。一个自然的降维方法是进行低维的线性变换(mathbf z = mathbf W mathbf x)。

Fisher linear discriminant analysis假设变换后的低位数据可以用高斯判别分析很好的分离，其是生成模型和判别模型的混合。其最大的缺点为变换后的维度要小于(C-1)。这样对于二分类问题，就意味着要找出一个向量(mathbf w)可以很好的分离数据点。

二分类问题

在二分类情况下，(mathbf w)是单一向量，其应该满足这样的条件

[max frac{(m_1-m_2)^2}{s_1^2+s_2^2} ]

即两个类别的均值映射之差的平方应该尽量大，每个类别方差应该尽量小。

拓展至多维

待添加