逻辑回归

本篇文章为讲述经典监督学习算法的第二篇文章,其它相关文章请参见 经典监督学习算法系列文章

逻辑回归

逻辑回归(logistic regression)模型是一种非常简单、但又非常具有启发性的线性分类算法。所谓线性分类算法,是指经过训练产出特征空间中的超平面,并将超平面分隔出来的不同的子空间归于不同的类别的一类分类算法。逻辑回归模型在产出用于分类的超平面上又多了一层概率解释,其给出的并不只是简单的非此即彼的分类信息,而是某个样本属于某一类的置信度,这也是其在经典分类算法中具有代表性的原因。

我们先从生成模型的角度来推导逻辑回归模型。考虑二类分类问题,类别分别用 $ {\cal C}_1 $ 和 $ {\cal C}_2 $ 表示。假设输入的样本为 $ {\bf x} $,类别的先验概率为 $ p({\cal C}_k) $,指定类别下产生 $ {\bf x} $ 的概率为 $ p({\bf x} | {\cal C}_k) $。则我们可根据贝叶斯公式计算出类别 $ {\cal C}_1 $ 的后验概率为

其中 $ a $ 被定义为

它衡量的是给定样本 $ {\bf x} $ 下类 $ {\cal C}_1 $ 的后验概率相对于类 $ {\cal C}_2 $ 的后验概率的增益。另外,式(1)中的函数 $ \sigma(a) $ 被称为 sigmoid 函数,定义为

sigmoid 函数有具有以下非常好的计算性质:

sigmoid 函数的图像如下所示

sigmoid 函数图像

从上图中可以看出,sigmoid 函数将自变量压缩在了 $ [0, 1] $ 区间,因而很适合作为产出概率的函数;另外,由于其非线性特性以及易于计算等特点,sigmoid 函数及其变种也经常被用于神经网络(neural networks)的激活层(activation layer)。

再回到我们求解类别 $ {\cal C}_1 $ 的后验概率的问题。由式(1)可知,问题可以转换为将 $ a $ 表征为含有参数的表达式,然后再在某个最优准则下求解这些参数。

当我们假设在给定类别下的样本 $ {\bf x } $ 的条件概率分布为具有相同协方差矩阵(这一假设很重要,正是由于假设不同类别的条件概率分布具有相同的协方差矩阵才使得不同高斯密度函数中的二次项能够抵消)的高斯分布时,$ a $ 正好是 $ {\bf x} $ 的线性函数。具体地,假设

将上式代入式(2)中,可得

其中

由于我们要求解的是各个类别的后验概率 $ p({\cal C}_k | {\bf x}) $,而它具有以下形式(以二分类模型中的类别 $ {\cal C}_1 $ 为例):

因此假设中的与高斯分布有关的参数都对我们来说都不重要,此后我们专注于求解 $ {\bf w} $ 和 $ w_0 $ 就行了。公式(10)即是逻辑回归模型的核心假设,而求解参数 $ {\bf w} $ 和 $ w_0 $ 则是逻辑回归模型的核心问题。


最大似然参数估计

线性回归问题一样,我们仍然会预先将样本 $ {\bf x} $ 做特征变换得到 $ \phi = \phi({\bf x}) $;另外为便于处理,我们还假设二类分类中的类别分别为 $ {\cal C}_1 = +1 $,$ {\cal C}_2 = -1 $。那么对于某对样本 $ ({\phi}_n, t_n) $,我们可以写出其在逻辑回归模型下关于参数 $ {\bf w} $ (这里的 $ {\bf w} $ 已经涵盖了偏置量 $ w_0 $ )的似然函数

将上述似然函数求对数再取负,便可得到交叉熵(cross entropy)

式(12)也被称作 logistic 损失函数,它与 0-1 损失函数的对比如下图所示(其中自变量为估计量 $ a $ 与实际量 $ t $ 的乘积)。

logistic 损失函数

0-1 损失函数是对于二分类问题最优的一个衡量准则,在该准则下,只要估计量与实际量符号相同就认为估计器估计正确,从而没有损失;反之则认为估计器估计失败,给出一个常量损失值。虽然 0-1 损失函数是最优的,但实际场景中一般都不采用该损失函数,一是因为它不可导,不方便计算;二是它对所有错误情形一视同仁,不利于算法学习到有用且详尽的关于样本集的信息。

而 logistic 损失函数则是对 0-1 损失函数的一个近似,它不仅希望估计量与实际量符号相同,它还希望估计量与实际量的乘积 $ ta $ 越大越好,这一点也是逻辑回归模型容易对线性可分(linear separable)的数据集造成严重的过拟合现象的主要原因:对于线性可分的数据集,采用最大似然方法求解参数的逻辑回归模型会产出一个分割不同类别的超平面 $ {\bf w}^{\text T} \phi = 0 $,且会将 $ {\bf w} $ 的幅度设为无穷大,从而使得训练集里面的每一个样本点所属类别的后验概率 $ p({\cal C}_k | {\bf x}) $ 都为 1;而这样的超平面不止一个,但最大似然方法没有机制来选取一个合理的超平面,最终产出的超平面完全取决于优化方法和初始值的选取。不过该过拟合问题仍然可以通过采用 Bayesian 的方法或正则化得到缓解。

给定数据集 $ \lbrace \phi_n, t_n \rbrace $, 其中 $ t_n \in \lbrace -1, +1 \rbrace $,$ \phi_n = \phi({\bf x}_n) $,$ n = 1, …, N $。可以写出该数据集关于 $ {\bf w} $ 的交叉熵(或损失函数)为

下面讲述对参数 $ {\bf w} $ 的求解方法。

梯度下降法

由于逻辑回归模型中的 sigmoid 函数的非线性特性,导致最大似然方法得不到关于参数 $ {\bf w} $ 的一个闭式解。梯度下降法可以提供对参数 $ {\bf w}$ 的一个简单的迭代求解过程。损失函数 $ E({\bf w}) $ 的一阶导数为

上式用到了式(5)。梯度下降法会将 $ {\bf w} $ 朝着 $ E({\bf w}) $ 下降最快的方向逼近,其迭代公式为

其中 $ \eta $ 为学习率(learning rate),是一个超参数。从式(14)与(15)中可以看出,每一个训练样本都会对 $ {\bf w}$ 的更新有所贡献,具体来说,某样本计算出的输出类别后验概率值 $ y $ 与 1 的差距越大,其贡献越大。

牛顿法

牛顿法是一种比梯度下降法更高效、且更容易求得最优解的迭代方法。该方法用到了对于参数 $ {\bf w} $ 的二阶导数。其迭代公式(推导放在下一小节)为

其中 $ {\bf H} $ 为 Hessian 矩阵,其元素由函数 $ E({\bf w}) $ 对 $ {\bf w} $ 的二阶导数构成,具体地,

现在我们来推导牛顿法对于参数 $ {\bf w} $ 的更新。首先将 $ \nabla E({\bf w}) $ 以矩阵的形式表示

其中 $ {\bf \Phi}^{\text T} = [\phi_1, \cdots, \phi_N ] $,$ {\bf y} = (y_1, \cdots, y_N) $,$ {\bf t} = (t_1, \cdots, t_N) $,$ {\bf 1} = (1, \cdots, 1) $,$ \circ $ 为元素层面(element-wise)的乘法。

然后可以求得 Hessian 矩阵

其中 $ {\bf R} $ 为一 $ N \times N $ 的对角矩阵,其对角元素为

可以看出,该 Hessian 矩阵依赖于参数 $ {\bf w} $,根本原因是损失函数(13)不是一个二次函数,而牛顿法的本质是将目标函数近似为二次函数,这就导致近似值与真实值之间存在差距,需要通过多次迭代来逼近。另一方面,由于 $ y_{n} \in (0, 1) $,从而使得 $ {\bf H} $ 为一个正定(positive-definite)矩阵(对任意非零向量 $ {\bf u} $,都有 $ {\bf u}^{\text T} {\bf H} {\bf u} > 0 $ )。$ {\bf H} $ 为正定矩阵则意味着损失函数(13)是一个凸函数,存在一个极小值(或一片连续的极小值区域),且该极小值就是全局最优解。

我们将式(18)与式(19)代入式(16)中,可以得到 $ {\bf w} $ 在牛顿法下的更新方程为

其中 $ {\bf z} $ 为一 $ N $ 维的列向量

式(21)的形式和线性回归中求解 $ {\bf w} $ 的正规方程的形式很像,只是多了一个权值矩阵 $ {\bf R} $,因此该方法又被称为 iterative reweighted least squares (IRLS)。可以理解为该方法对每一个样本点进行了加权,加权值的大小与 $ R_{nn} $ 成比例,而 $ R_{nn} $ 的大小又与 $ t_n $ 在逻辑回归模型假设中的输出分布情况下的方差 $ {\text {var} } [t_n] $ 成正比;从直觉上来讲,IRLS 方法是对当前参数下变数更大(对给定输入的输出类别的不确定性很大)的训练样本赋予更重的权重,以提高模型对这些样本的预测能力。

梯度下降法与牛顿法比较

梯度下降法与牛顿法均为可以用来求解最优化问题的迭代算法。二者有一些共同点:1)都为贪心算法;2)都只能获得局部最优解(若证明目标函数是凸函数,例如 logistic 损失函数(13),则可获得全局最优解)。假设目标函数为 $ f({\bf x}) $,下面分别给出梯度下降法和牛顿法的推导。

梯度下降法的推导

对函数值 $ f({\bf x} + {\bf v}) $ 在 $ {\bf x} $ 处作一阶泰勒级数展开得

假设 $ || {\bf v} || = 1 $(固定更新步长),想要 $ f({\bf x} + {\bf v}) $ 相比 $ f({\bf x}) $ 下降最多,则要使 $ (\nabla f({\bf x}))^{\text T} {\bf v} $ 最小,即 $ {\bf v} $ 的方向要与 $ \nabla f({\bf x}) $ 的方向相反,即有

又由于我们希望更新的步长与梯度的大小成正比(因为梯度越小,越接近最优点,更新的步长要减小),可以写出 $ {\bf x} $ 的更新公式为

其中 $ \eta $ 即为学习率,需要根据情况调整,既不可设置的太大(容易跳出最佳区域),也不可设置的太小(迭代次数变多,降低算法效率)。

牛顿法的推导

对函数值 $ f({\bf x} + {\bf v}) $ 在 $ {\bf x} $ 处作二阶泰勒级数展开得

要想使 $ f({\bf x} + {\bf v}) $ 最小(给定 $ {\bf x} $),即要求使 $ (\nabla f({\bf x}))^{\text T} {\bf v} + \frac{1}{2} {\bf v}^{\text T} \nabla^{2} f({\bf x}) {\bf v} $ 最小的 $ {\bf v}_s $,很容易求得

因而 $ {\bf x} $ 的更新公式为

上式与式(15)一致。

完成上面的推导之后,我们很容易看到牛顿法与梯度下降法之间的一些显著的差异。

首先,梯度下降法需要设置一个超参数——学习率;而牛顿法则不需要。避免设置超参数可以省掉很多事。

其次,牛顿法一般比梯度下降法更快获得收敛,但其需要更多的计算开销和内存开销(需计算和保存 Hessian 矩阵)。牛顿法是二阶近似,而梯度下降法是一阶近似。通俗来讲,假如你想找一条最短的路径走到一个盆地的最底部,梯度下降法每次只从你当前所选的位置选一个坡度最大的方向走一步;而牛顿法会在选择方向时,不仅会考虑坡度是否足够大,还会考虑你走了一步之后坡度是否会变得更大。所以,牛顿法比梯度下降法利用的信息更多一些,看得更远一些,从而能更快地到达盆地底部。从几何上来讲,牛顿法就是用一个二次曲面去拟合当前所处位置的局部曲面,而梯度下降法则是用一个平面去拟合当前的局部曲面,很显然,二次曲面要比平面更接近于当前的局部曲面,因而牛顿法会比梯度下降法收敛得更快。


softmax 回归

将逻辑回归模型被拓展到多类别的情形时的模型被称为 softmax 回归模型。具体地,softmax 回归假定类别 $ {\cal C}_k $ 的后验概率为

其中 $ a_k $ 被定义为

softmax 回归的核心问题即是估计参数 $ \lbrace {\bf w}_k \rbrace $,$ k = 1, …, K $。为方便推导,假设输出类别由一个 $ K $ 维向量 $ {\bf t} $ 表征,该向量有且仅有一个元素的值为 1,其他元素的值均为 0,非零元素的序位代表输出的类别(例如,输出类别 $ {\cal C}_k $ 对应的向量的第 $ k $ 个元素为非零)。则可以写出给定数据集 $ \lbrace \phi_n, {\bf t}_n \rbrace $ 下参数 $ \lbrace {\bf w}_k \rbrace $ 的似然函数为

其中 $ y_{nk} = y_k(\phi_n) $,$ {\bf T} \in \lbrace 0, 1 \rbrace^{N \times K } $ 由输出的类别向量所组成。对似然函数求对数再取负可得交叉熵为

对 $ E({\bf w}_1, \cdots, {\bf w}_K) $ 求一阶导数可得

上式用到了以下导数公式

其中 $ I_{kj} $ 是单位矩阵 $ {\bf I}_{KK} $ 中位置为 $ (k, j) $ 的元素。

有了式(33)之后,我们就可以对参数 $ \lbrace {\bf w}_k \rbrace $ 按照梯度下降方法进行更新了。利用牛顿法更新参数的方法和前面类似,只需求出交叉熵关于参数 $ \lbrace {\bf w}_k \rbrace $ 的 Hessian 矩阵即可,这里不加赘述。