logistic回归

本节的主要参考资料是机器学习基石[1]和机器学习[2]网络课程。

soft二分类

soft二分类感兴趣的不仅仅是$\{-1,+1\}$类别的判断，而是属于某个类别的可能性，比如 \begin{equation} f(\mathbf x)=P(+1|\mathbf x)\in [0,1]。 \label{eq:f-vs-probility} \end{equation} 但是在实际应用中，难以获取属于某个类别的概率，只能得到是否属于某个类别，也就是与二分类一样的数据集。

不妨将$\{-1,+1\}$类别标签的数据，看作是概率标签数据被噪声污染的结果，e.g. $(\mathbf x_1,y’_1=0.9=P(+1|\mathbf x_1))+{noise}\rightarrow(\mathbf x_1,y_1=\circ\sim P(+1|\mathbf x_1))$。

logistic回归解决的问题，就是在$\{-1,+1\}$类别标签的训练集上，通过soft二分类产生概率标签的输出。

logistic回归模型

图 1: logistic函数 [PNG]

对于特征$\mathbf x=(x_0, x_1,\ldots,x_d)$，先计算加权的risk score，$s=\mathbf w^T\mathbf x$，然后再将此得分代入如上图所示的logistic函数¹ \begin{equation} \theta(s)={1\over 1 + e^{-s}} \label{eq:sigmoid-function} \end{equation} 转化为概率的形式。logistic函数也称为sigmoid函数，单调、光滑。也就是可用logistic回归模型 \begin{equation} h(\mathbf x)={1\over 1+\exp(-\mathbf w^T\mathbf x)}， \end{equation} 作为目标函数$f(\mathbf x)=P(y|\mathbf x)$的近似。

建立logistic回归模型的基本思路是，找到最可能产生数据集$\mathcal D$的假设$h$。考虑数据集$\mathcal D=\{(\mathbf x_1,\circ),(\mathbf x_2,\times),\ldots,(\mathbf x_N,\times)\}$，根据\eqref{eq:f-vs-probility}可得² \[ P(y|\mathbf x)= \left\{ \begin{aligned} &f(\mathbf x)&\mbox{for }y=+1&\\ &1-f(\mathbf x)&\mbox{for }y=-1&， \end{aligned} \right. \] 那么得到这个数据集的概率为 \[ \begin{aligned} &P(\mathbf x_1)P(\circ|\mathbf x_1)\times P(\mathbf x_2)P(\times|\mathbf x_2)\times\ldots P(\mathbf x_N)P(\times|\mathbf x_N)\\ =&P(\mathbf x_1)f(\mathbf x_1)\times P(\mathbf x_2)(1-f(\mathbf x_2))\times\ldots P(\mathbf x_N)(1-f(\mathbf x_N))\Rightarrow\mbox{probability using }f\\ \approx &P(\mathbf x_1)h(\mathbf x_1)\times P(\mathbf x_2)(1-h(\mathbf x_2))\times\ldots P(\mathbf x_N)(1-h(\mathbf x_N))\Rightarrow\mbox{likelihood}(h)， \end{aligned} \] $h$产生这笔数据的可能性（likelihood）和$f$产生这笔数据的概率（probability）差不多，最终得到了$h$产生这笔数据的可能性。期望$f$产生这笔数据的概率相当大³，因此有 \[ \mbox{likelihood}(h)\approx\mbox{probability using }f\approx\mbox{large}， \] 选择可能性最高的那个$h$ \[ g=\arg\max_h\mbox{likelihood}(h)。 \] 根据logistic函数的性质$\theta(-s)=1-\theta(s)$，可进一步得到 \[ \mbox{likelihood}(h)=P(\mathbf x_1)h(+\mathbf x_1)\times P(\mathbf x_2)(-h(\mathbf x_2))\times\ldots P(\mathbf x_N)(-h(\mathbf x_N))， \] 对所有$h$，$P(\mathbf x_i)$都不变，那么可得 \[ \mbox{likelihood}(\mbox{logistic }h)\varpropto\prod_{n=1}^Nh(y_n\mathbf x_n)， \] 最佳$\mathbf w$应满足条件 \[ \max_{\mathbf w}\mbox{likelihood}(\mathbf w)\varpropto\prod_{n=1}^N\theta(y_n\mathbf w^T\mathbf x_n)。 \] 利用$\ln$将乘法化为加法，得到等价的优化问题 \begin{equation} \min_\mathbf wE_{in}(\mathbf w)={1\over N}\sum_{n=1}^N\ln\left(1+\exp\left(-y_n\mathbf w^T\mathbf x_n\right)\right)， \end{equation} 其中$err(\mathbf w,\mathbf x,y)=\ln\left(1+\exp\left(-y\mathbf w^T\mathbf x\right)\right)$称为交叉熵误差（cross-entropy error）。

图 2: ［左］：平方误差代价函数；［右］交叉熵误差代价函数 [PNG]

上图展示了用不同误差度量方式的代价函数，上图左采用了线性回归基于平方误差的代价函数，非凸不利于优化。

梯度下降法

$E_{in}(\mathbf w)$是连续、可微、二次可微的凸函数，理论上取得最小值时$\mathbf w$满足$\nabla E_{in}(\mathbf w)=0$，其中 \begin{equation} \nabla E_{in}(\mathbf w)={1\over N}\sum_{n=1}^N\theta(-y_n\mathbf w^T\mathbf x_n)(-y_n\mathbf x_n)。 \label{eq:gradient-logistic-object-function} \end{equation} 由于$\nabla E_{in}(\mathbf w)=0$是非线性方程，并且$\theta(-y_n\mathbf w^T\mathbf x_n)＝0$的条件$y_n\mathbf w^T\mathbf x_n\gg 0$也难以满足，因此不存在类似线性回归的闭式解。

回顾感知器算法的权值更新，稍微修改其表现形式 \[ \mathbf w_{t+1}\leftarrow\mathbf w_{t}+1\cdot\left(\left[\left[\mbox{sign}\left(\mathbf w_t^T\mathbf x_n\right)\neq y_n\right]\right]y_n\mathbf x_n\right)， \] 简记为 \[ \mathbf w_{t+1}\leftarrow\mathbf w_{t}+\eta\mathbf v， \] 其中$\eta=1$表示步长，$\mathbf v=\left[\left[\mbox{sign}\left(\mathbf w_t^T\mathbf x_n\right)\neq y_n\right]\right]y_n\mathbf x_n$表示方向。对$(\eta,\mathbf v)$和终止条件的不同定义，就会得到不同的迭代优化算法。考察梯度计算公式\eqref{eq:gradient-logistic-object-function}，$\theta(-y_n\mathbf w^T\mathbf x_n)$相当于梯度方向的加权值，当$y_n\mathbf w^T\mathbf x_n$越小的时候，权值越大，负值越大表示犯错越厉害。如果按照梯度方向更新，这和PLA有相同的含义，犯错越厉害的对更新贡献越大。

对于logistic回归的$E_{in}$，令$\eta>0$， \[ \min_{\lVert\mathbf v\rVert=1}E_{in}(\mathbf w_t+\eta\mathbf v) \] 利用贪婪法找$\mathbf w_t$附近最好的一个方向，让$E_{in}$下降最多。上式仍然是非线性，且带约束条件，难以求解。当$\eta$足够小时，利用Taylor展式可得 \begin{equation} E_{in}(\mathbf w_t+\eta\mathbf v)\approx E_{in}(\mathbf w_t)+\eta\mathbf v^T\nabla E_{in}(\mathbf w_t) \label{eq:taylor-expansion-Ein} \end{equation} 若要实现 \[ \min_{\lVert\mathbf v\rVert=1}\left(E_{in}(\mathbf w_t)+\eta\mathbf v^T\nabla E_{in}(\mathbf w_t)\right)， \] 就要使得$\eta\mathbf v^T\nabla E_{in}(\mathbf w_t)$最小，此时$\eta>0$是常数，因此$\mathbf v$和$\nabla E_{in}(\mathbf w_t)$反向时得到的值最小， \[ \mathbf v=-\frac{\nabla E_{in}(\mathbf w_t)}{\lVert\nabla E_{in}(\mathbf w_t)\rVert}， \] 那么参数的更新规则为 \begin{equation} \mathbf w_{t+1}\leftarrow\mathbf w_{t}-\eta\frac{\nabla E_{in}(\mathbf w_t)}{\lVert\nabla E_{in}(\mathbf w_t)\rVert}。 \label{eq:gd-iterate} \end{equation} 这种参数更新方法就是梯度下降法，是一种简单且应用广泛的优化算法。

图 3: 不同步长的迭代效果 [PNG]

上图展示了利用\eqref{eq:gd-iterate}迭代的效果，$\eta$过小导致收敛太慢，过大导致不稳定，动态调整可以得到不错的效果。对于动态调整的$\eta$，坡度$\lVert\nabla E_{in}(\mathbf w_t)\rVert$大的时候采用大的$\eta$，小的时候采用小的$\eta$。当$\eta\leftarrow{\eta\over\lVert\nabla E_{in}(\mathbf w_t)\rVert}$时，固定住新的$\eta$就会达到动态调整的效果，因此可以采用固定$\eta$的自适应步长更新方式

\begin{equation} \mathbf w_{t+1}\leftarrow\mathbf w_{t}-\eta\nabla E_{in}(\mathbf w_t)。 \label{eq:gd-iterate-2} \end{equation}

####梯度下降法求解logistic回归参数

初始化$\mathbf w_0$和$\eta$；

对$t=0,1,\ldots$循环以下步骤，直到$\nabla E_{in}(\mathbf w_{t+1})=0$或达到设定迭代次数：

1. 利用公式\eqref{eq:gradient-logistic-object-function}计算$\nabla E_{in}(\mathbf w_{t})$；
2. 利用公式\eqref{eq:gd-iterate-2}更新参数$\mathbf w_{t+1}$。

梯度下降法的注意事项可以参考线性回归梯度法的注意事项。

参考文献

1. [1]H.-T. Lin, “Lecture 10: Logistic Regression.” Coursera, 2014. [Online]
2. [2]A. Ng, “Logistic Regression.” Coursera, 2014. [Online]

脚注