回归问题

• 54 min read • 10724 words
Tags: Ma-Le
Categories: Machine Learning

回归问题

1. 概述

与前面讨论的分类问题不同，在回归问题中，对于数据 XX，我们需要预测一个具体的数值（通常是连续的，比如房价、气温）。

我们之前讨论的 QDA 和 LDA 其实也包含了回归的思想，因为它们不仅给出了分类结果，还给出了这个预测正确的概率。

回归问题包含如下三个部分：

  1. 选择一个回归函数的形式 h(x;w)h(x; w)
  2. 选择一个损失函数 L(y^,y)L(\hat{y}, y)
  3. 选择一个成本函数 J(h)J(h)

这一部分在之前 “机器学习基础” 的文章中详细讲过，这里就略过了。

2. 最小二乘线性回归

在最小二乘线性回归中，我们需要找到参数 ww 和 αα，使得所有样本点的残差平方和 (Residual Sum of Squares, RSS) 最小：

min⁡∑(Xi⋅w+α−yi)2。\min \sum(X_i \cdot w + α - y_i)^2。

我们将 Xi cdotw+αX_i \ cdot w + \alpha 写成矩阵形式，转换成最小化：

∥Xw−y∥2\| Xw-y \| ^ 2

对这个式子对 ww 求梯度，令其为0：

∇RSS=2XTXw−2XTy=0⇒XTXw=XTy\nabla \text{RSS}=2X^TXw - 2X^Ty = 0 \Rightarrow X^TXw = X^Ty

这个方程被称为正规方程组 (Normal Equations)。如果 XTXX^TX 这个矩阵是可逆的，那么 ww 的解就是 w=(XTX)−1XTyw = (X^TX)^{-1}X^Ty。如果 XTXX^TX 不可逆，则该方法失效，这通常意味着数据点共线或共面（比如样本点数量少于特征数量），导致问题有无穷多解（欠定的）。

3. 逻辑回归

逻辑回归是另一种非常重要的回归方法。它的回归函数是逻辑函数 s(w⋅x+α)s(w\cdot x + \alpha)，损失函数为交叉熵损失。我们希望使下面的式子最小：

J=∑i=1nL(s(Xi⋅w), yi)=−∑i=1n(yiln⁡s(Xi⋅w)+(1−yi)ln⁡(1−s(Xi⋅w)))J=\sum_{i=1}^{n}L\bigl(s(X_i\cdot w),\,y_i\bigr) =-\sum_{i=1}^{n}\bigl(y_i\ln s(X_i\cdot w)+(1-y_i)\ln(1-s(X_i\cdot w))\bigr)

需要注意这个函数是凸函数，这意味着它只有一个全局最小值，没有局部最小值。因此，我们可以使用梯度下降 (gradient descent) 法来求解，并且保证能找到最优解。

下面我们进行一下逻辑函数的梯度下降推导。首先，逻辑函数具有如下性质：

s′(x)=s(x)(1−s(x))s'(x) = s(x) (1 - s(x))

于是有：

∇wJ=−∑i=1n(yisi−1−yi1−si)∇wsi,si=s(Xi⋅w)=−∑i=1n(yisi−1−yi1−si)s′(Xi⋅w)Xi=−∑i=1n(yisi−1−yi1−si)si(1−si)Xi=−∑i=1n(yi−si)Xi\begin{aligned} \nabla_w J &= -\sum_{i=1}^n\left(\frac{y_i}{s_i}-\frac{1-y_i}{1-s_i}\right)\nabla_w s_i,\quad s_i=s(X_i\cdot w)\\ &= -\sum_{i=1}^n\left(\frac{y_i}{s_i}-\frac{1-y_i}{1-s_i}\right)s'(X_i\cdot w)X_i\\ &= -\sum_{i=1}^n\left(\frac{y_i}{s_i}-\frac{1-y_i}{1-s_i}\right)s_i(1-s_i)X_i\\ &= -\sum_{i=1}^n (y_i-s_i)X_i \end{aligned}

也即：

∇wJ=−XT(y−s(Xw))\nabla_w J = -X^{T}\bigl(y - s(Xw)\bigr)

有了梯度计算式，我们就可以使用梯度下降与随机梯度下降方法了：

w←w+ϵ XT(y−s(Xw))w \leftarrow w + \epsilon\, X^{T}\bigl(y - s(Xw)\bigr) w←w+ϵ (yi−s(Xi⋅w)) Xiw \leftarrow w + \epsilon\,\bigl(y_i - s(X_i\cdot w)\bigr)\,X_i

这个更新规则和感知机算法 w←w+ϵ XT(y−y^)w \leftarrow w + \epsilon\, X^{T}\bigl(y - \hat{y}\bigr) 非常相似。区别在于，感知机的 y^\hat{y} 是一个硬性的 0 或 1 的预测，而逻辑回归中的 sis_i 是一个软性的、介于 0 和 1 之间的概率。可以把逻辑回归看作是感知机的一个 “平滑”或“概率化”的版本。

4. 加权最小二乘回归

在实际的回归问题中，某些数据点可能比其他点更可信，或者我们希望模型能更精确地拟合某些特定的点。于是我们可以使用加权最小二乘回归：

min⁡w(Xw−y)TΩ(Xw−y)=∑i=1nωi(Xi⋅w−yi)2\min_w (Xw - y)^T \Omega (Xw - y) = \sum_{i=1}^n \omega_i \bigl(X_i\cdot w - y_i\bigr)^2

这个式子的正规方程为：

XTΩXw=XTΩyX^T \Omega Xw = X^T \Omega y

5. 牛顿法

牛顿法是一种用于寻找函数（例如成本函数 J(w)J(w)）极值的迭代优化算法。它通常比梯度下降法收敛得快得多。

我们对目标函数 J(w)J(w) 的梯度 ∇J(w)\nabla J(w) 在当前点 vv 附近进行泰勒展开，并忽略高阶项：

∇J(w)≈∇J(v)+H(v)(w−v)\nabla J(w) \approx \nabla J(v) + H(v)(w - v)

其中 H(x)H(x) 是 JJ 在 vv 点的海森矩阵，可以把它理解为多变量函数的二阶导数：

H(f)=[∂2f∂x12∂2f∂x1∂x2⋯∂2f∂x1∂xn∂2f∂x2∂x1∂2f∂x22⋯∂2f∂x2∂xn⋮⋮⋱⋮∂2f∂xn∂x1∂2f∂xn∂x2⋯∂2f∂xn2]H(f)=\begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1\partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1\partial x_n} \\ \frac{\partial^2 f}{\partial x_2\partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_n\partial x_1} & \frac{\partial^2 f}{\partial x_n\partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{bmatrix}

我们令这个梯度为0，更新 ww 参数：

w=v−H−1(v)∇J(v)w = v - H^{-1}(v) \nabla J(v)

重复这个过程直到 ww 收敛。整个流程如下：

  1. 我们选择一个初始点 ww。
  2. 计算该点的梯度 ∇J(w)\nabla J(w) 和海森矩阵 H(w)=∇2J(w)H(w)=\nabla^2J(w)。
  3. 求解线性方程组 H(w)e=−∇J(w)H(w)e=-\nabla J(w)，得到更新步长。
  4. 更新 ww： w←w+ew \leftarrow w + e

牛顿法利用了二阶导数（曲率）信息，能更准地找到下降方向和步长，因此收敛速度远快于只使用一阶导数的梯度下降。但是计算成本很高，并且每次迭代都要重新计算梯度、海森矩阵和求解线性方程组。

6.使用牛顿法的逻辑回归

a.a. 理论推导

在学习了牛顿法后，我们试着用这一收敛更快的算法来计算逻辑回归。

我们已知：

∇wJ=−∑i=1n(yi−si)Xi\nabla_w J= -\sum_{i=1}^n (y_i-s_i)X_i

对其求梯度得：

∇w2J(w)=−∑i=1n∇w((yi−si)Xi)=−∑i=1nXi(∇w(yi−si))T=−∑i=1nXi(−∇wsi)T=∑i=1nXi(∇wsi)T=∑i=1nXi(si(1−si)Xi)T=∑i=1nsi(1−si) XiXiT\begin{aligned} \nabla_w^2 J(w) &= -\sum_{i=1}^n \nabla_w\big((y_i - s_i) X_i\big)\\ &= -\sum_{i=1}^n X_i\big(\nabla_w (y_i - s_i)\big)^T\\ &= -\sum_{i=1}^n X_i\big(-\nabla_w s_i\big)^T\\ &= \sum_{i=1}^n X_i\big(\nabla_w s_i\big)^T\\ &= \sum_{i=1}^n X_i\big(s_i(1-s_i)X_i\big)^T\\ &= \sum_{i=1}^n s_i(1-s_i)\,X_i X_i^T \end{aligned}

向量微积分法则：∇w(fv)=v(∇wf)T,  v is constant\nabla_w\big(fv\big)=v\big(\nabla_w f\big)^T,\; v\ \text{is constant}。这是为了确保维度的正确。

将其写成矩阵形式，即得：

∇w2J(w)=XΩXT\nabla_w^2 J(w) = X\Omega X^T

其中 Ω=diag⁡(s1(1−s1), s2(1−s2), …, sn(1−sn))\Omega=\operatorname{diag}\big(s_1(1-s_1),\,s_2(1-s_2),\,\ldots,\,s_n(1-s_n)\big)

因为 Ω\Omega 是一个对角线上元素全为正的对角矩阵，所以 Ω\Omega 是正定的，这进一步保证了海森矩阵 H=XTΩXH = X^T\Omega X 是半正定的。而如果一个函数的海森矩阵在定义域内处处都是半正定的，那么这个函数就是凸函数。这意味着只要牛顿法能够收敛，我们就一定能够得到全局最小值。

我们将梯度和海森矩阵 H(w)=∇w2J(w)H(w)=\nabla_w^2 J(w) 带入，得到如下的牛顿法的线性方程组：

(XTΩX)e=XT(y−s)(X^{T}\Omega X)e = X^{T}(y - s)

观察这个式子，和我们先前的加权最小二乘回归的规范方程：

XTΩXw=XTΩyX^T \Omega Xw = X^T \Omega y

非常类似。这个计算逻辑回归的方法也被称为迭代重加权最小二乘 (Iteratively Reweighted Least Squares, IRLS)。它和加权最小二乘的计算方法类似，但是 IRLS 的权重矩阵 Ω\Omega 并不是固定的，每一次我们更新 ww 后，Ω\Omega 都要被重新计算。这个过程就像是每一轮迭代都在用新的权重，去解一个加权最小二乘问题。

不同的点在 IRLS 中的影响权重如下：

  1. 被正确分类，且离边界很远的点：这些点的 sis_i 接近 1，因此权重 si(1−si)s_i(1-s_i) 很小，这说明模型已经很好地处理了它们，所以不需要再关注了。
  2. 被错误分类，且离边界很远的点：这些点的 sis_i 接近 0，因此权重 si(1−si)s_i(1-s_i) 同样很小，但是右侧的误差项 (y−si)(y - s_i) 很大，牛顿法会集中修正这些点。
  3. 离决策边界很近的点：这些点的 sis_i 接近 0.5，权重 si(1−si)s_i(1-s_i) 达到最大值，这些点有中等影响 。

IRLS 优先关注那些被模型以高置信度搞错了的样本，这非常符合直觉。

b.b. 算法加速

如果数据集 nn 非常大，每次迭代都用全部数据来计算 XTΩXX^T\Omega X 和 XT(y−s)X^T(y-s) 会非常慢。一个加速的技巧是：在每次迭代时，不使用全部样本，而是随机抽取一小部分样本（一个子集或 minibatch） 来近似计算梯度和海森矩阵。这一做法的原理如下：

  • 在优化的早期阶段，我们离最优点还很远，没必要进行精确到毫米的计算，只需要一个大致正确的方向就足够了。用一小部分数据算出的方向已经足够好。
  • 随着迭代的进行，当我们越来越接近最优点时，可以逐渐增多每次迭代使用的样本数量，以获得更精确的更新方向，进行最后的“精调”。

这个思想是现代大规模机器学习优化的基石，著名的随机梯度下降（SGD）便是基于此思想。

c.c. 逻辑回归与 LDA 的优劣

LDA 的优势

  1. 对于类别区分良好的数据，LDA更稳定
    • 当两个类别的数据点可以被完美地分开时，逻辑回归的参数（权重ww）会趋向于无穷大，试图让预测概率无限接近0或1，从而使成本函数降为 0。这会导致数值上的不稳定。
    • 而LDA是通过计算每个类别的均值和方差来确定模型的，这些统计量是稳定的，不会无限增大。因此，即使数据分得再开，LDA的模型参数也是稳定的。
  2. 处理多于 2个的类别时，更简单优雅
    • LDA的框架天然支持多个类别。它为每个类别都拟合一个高斯分布，然后看新来的数据点更符合哪个类别的分布。
    • 标准的逻辑回归是为二分类设计的。要处理多分类，就需要做一些修改，比如训练多个“一对多”的分类器，或者使用更复杂的Softmax回归。
  3. 当数据分布接近正态分布时，LDA更准确（尤其在样本少时）

逻辑回归的优势

  1. 更专注于决策边界，总能分开线性可分的数据
    • 逻辑回归的唯一目标就是找到一个决策边界来最小化分类错误。只要数据是线性可分的，它就一定能找到一条线把它们分开。
  2. 在某些非高斯分布的数据上更稳健
    • 这是LDA劣势的反面。正因为逻辑回归不对数据的分布做任何假设，所以当数据不符合高斯分布时（例如，数据有很长的“尾巴”或严重的偏斜），逻辑回归的表现通常会比LDA更好。
  3. 天然输出0到1之间的概率值
    • 逻辑回归通过Sigmoid函数，其输出结果天然就是0到1之间的值，这可以很直观地被解释为分类的概率。

两者最根本的区别在于对数据点的处理上。逻辑回归更关注那些被错误分类或离决策边界很近的“问题”数据点。它在优化时，会给这些点更大的“权重”，努力把它们分对。对于那些已经被正确分类且离边界很远的点，它就不怎么关心了。而 LDA 对所有数据点一视同仁。在为每个类别计算均值和协方差时，每个点都贡献了相同的权重。这带来了下面的权衡：

  • 逻辑回归的做法有利于降低训练误差，但如果数据中有一些“坏点”或“异常值”，模型就容易被这些坏点带偏，因为它太想把所有点都分对了。
  • LDA的做法对异常值不那么敏感，模型更稳定，但代价是如果它的高斯分布假设是错的，它可能无法得到最低的训练误差。

Comments

Total words: 10724