Lecture 3: Weighted Least Squares. Logistic Regression. Newton’s Method

目录 · ← l2 · l4 →

Lecture 3: Weighted Least Squares. Logistic Regression. Newton’s Method

概述

本讲做两件事：其一，介绍局部加权线性回归 (LWR)——一种“非参数”地让线性回归更灵活的方法；其二，进入分类问题，引入逻辑回归 (Logistic Regression)——用 Sigmoid 函数把线性输出压缩到 $(0,1)$ 作为概率，并用梯度上升与牛顿法 (Newton’s Method) 两种优化器求解。本讲是“线性模型 → 分类”的关键转折。

核心概念与数学直觉

• 局部加权线性回归 (Locally Weighted Linear Regression, LWR)：
  • 问题定义：普通线性回归对全局数据拟合一条直线，欠拟合非线性数据。
  • 直观解释：预测点 $x$ 时，只在乎它附近的点——给附近的训练样本更大权重，远处的权重趋近 0。相当于“为每个查询点拟合一条局部直线”。
  • 数学形式：最小化加权代价 $J(\theta) = \frac{1}{2} \sum_{i=1}^{m} w^{(i)} (y^{(i)} - \theta^T x^{(i)})^2, \qquad w^{(i)} = \exp\left(-\frac{(x^{(i)} - x)^2}{2\tau^2}\right)$
    • $w^{(i)}$：第 $i$ 个样本的权重，随其与查询点 $x$ 的距离指数衰减。
    • $\tau$（bandwidth）：带宽参数，控制“局部”的范围——$\tau$ 小则只看极近邻，$\tau$ 大则接近全局线性回归。
  • 关键性质：LWR 是非参数方法——训练阶段不保存参数，每次预测都要重新拟合（存储全部数据、预测代价高）；对比参数方法（线性回归）训练后只需 $\theta$。
• 逻辑回归 (Logistic Regression)：
  • 问题定义：二分类，$y \in \{0, 1\}$。要求输出“属于类别 1 的概率”。
  • 直观解释：线性回归的 $h_\theta(x) = \theta^T x$ 可能输出任意实数（如 3.2 或 -5），不适合当概率。用 Sigmoid 函数把它“压”进 $(0,1)$：$\theta^T x$ 越大，概率越接近 1。
  • 数学形式： $h_\theta(x) = g(\theta^T x) = \frac{1}{1 + e^{-\theta^T x}}, \qquad P(y=1\|x;\theta) = h_\theta(x), \quad P(y=0\|x;\theta) = 1 - h_\theta(x)$
    • $g(z) = 1/(1+e^{-z})$：Sigmoid/逻辑函数。$z \to +\infty$ 时 $g \to 1$；$z \to -\infty$ 时 $g \to 0$；$g(0) = 0.5$。
    • 直觉：决策边界是 $\theta^T x = 0$（此时概率 0.5）。Sigmoid 的导数有优美性质：$g^{\prime}(z) = g(z)(1 - g(z))$——这使梯度推导极其简洁。
  • 为什么不继续用 MSE？：把 $h_\theta(x)$ 换成 Sigmoid 后 MSE 不再是凸函数，梯度下降可能陷于局部最优；且概率建模天然指向交叉熵。
  • 损失函数（交叉熵，由 MLE 导出）：假设 $y \sim \text{Bernoulli}(h_\theta(x))$，最大化对数似然等价于最小化负对数似然： $\ell(\theta) = \sum_{i=1}^{m} \left[ y^{(i)} \log h_\theta(x^{(i)}) + (1 - y^{(i)}) \log(1 - h_\theta(x^{(i)})) \right]$
    • 直觉：当 $y^{(i)}=1$ 时只有第一项起作用——若模型预测 $h \to 1$（正确），该项 $\to 0$（无惩罚）；若 $h \to 0$（严重错误），$\log$ 爆炸（重罚）。交叉熵对“过度自信的错误”惩罚极重。
  • 梯度上升更新（对 $\ell$ 最大化）： $\theta_j := \theta_j + \alpha \sum_{i=1}^{m} (y^{(i)} - h_\theta(x^{(i)})) x_j^{(i)}$
    • 惊人的巧合：形式与线性回归的 LMS 更新完全一样（只是 $h$ 换成了 Sigmoid）。这不是偶然，而是广义线性模型（GLM, L4）统一理论的第一个证据。
• 牛顿法 (Newton’s Method)：
  • 问题定义：梯度上升（一阶方法）收敛慢；牛顿法利用二阶信息（曲率）加速收敛。
  • 直观解释：梯度下降像“沿坡走固定步长”；牛顿法用二次函数局部逼近目标函数，直接跳到这个二次近似的顶点——更聪明、通常更快（二次收敛）。
  • 数学形式（最大化 $\ell(\theta)$）： $\theta := \theta - H^{-1} \nabla_\theta \ell(\theta), \qquad H_{jk} = \frac{\partial^2 \ell}{\partial \theta_j \partial \theta_k}$
    • $\nabla_\theta \ell$：梯度（一阶信息，上升方向）。
    • $H$：Hessian 矩阵（二阶信息，曲率），$n \times n$。
    • $H^{-1} \nabla \ell$：用曲率校正步长——曲率大的方向步长小（避免越过），曲率小的方向步长大（快速前进）。
  • 代价：每步需计算并求逆 $H$，$O(n^3)$。当 $n$ 不大（如 $<10^3$）且需要高精度解时，牛顿法只需很少迭代（二次收敛：误差每步平方级缩小）；$n$ 大时用（拟）牛顿或一阶方法。
  • 逻辑回归中的特殊性质：$\ell$ 是凹函数，牛顿法保证收敛到全局最优。实践中逻辑回归常用 IRLS (Iteratively Reweighted Least Squares)——即牛顿法在该问题的特例。

算法伪代码与逻辑解说：逻辑回归 + 牛顿法

伪代码

输入:
    - 训练数据 (X, y)，y ∈ {0,1}
    - 收敛阈值 epsilon，最大迭代 max_iters

输出:
    - 最优参数 theta

1. 初始化 theta = 0
2. 循环 iter = 1..max_iters:
    2.1 预测概率: h = sigmoid(X * theta)            // 向量化，m 维
    2.2 梯度: grad = X^T * (y - h)                   // 一阶信息
    2.3 Hessian: H = X^T * diag(h .* (1 - h)) * X    // 二阶信息，diag 对角矩阵
    2.4 更新: theta = theta - inv(H) * grad          // 牛顿步
    2.5 若 ||grad|| < epsilon: 终止
3. 返回 theta

【算法逻辑解说】

1. Step 2.1：sigmoid(X*theta) 一次算出所有样本的预测概率 $h_i = g(\theta^T x^{(i)})$。这是模型的前向计算。
2. Step 2.2 梯度：$\nabla_\theta \ell = \sum_i (y^{(i)} - h_i) x^{(i)}$——误差向量 $(y - h)$ 与设计矩阵的乘积。直觉：若样本 $i$ 被低估（$h_i < y_i$），则误差为正，梯度把 $\theta$ 往“增加该样本预测”的方向推。注意这里是对数似然的梯度（上升方向），牛顿法里减去 $H^{-1}grad$ 即朝上升方向走。
3. Step 2.3 Hessian：$h_i(1-h_i)$ 是 Sigmoid 在 $h_i$ 处的导数（斜率）——它衡量预测的“不确定性”：$h_i \approx 0.5$ 时 $h_i(1-h_i) \approx 0.25$（最不确定，曲率最大）；$h_i \approx 0$ 或 $1$ 时接近 0（已确定，曲率小）。$H$ 把每个样本的曲率按特征加权累积。
4. Step 2.4 牛顿步：$H^{-1} grad$ 同时考虑了方向和曲率。相比梯度上升 $\theta + \alpha \cdot grad$，牛顿法没有学习率超参数（曲率自动定步长）且收敛极快（通常 <15 次迭代）。
5. 何时用梯度上升 vs 牛顿法：$n$ 小、精度要求高 → 牛顿法；$n$ 大（>10³）→ 梯度上升（Hessian 求逆不可行）。

关键要点

1. 逻辑回归解决分类：Sigmoid 把线性得分映射为概率，决策边界仍是线性的（$\theta^T x = 0$）。
2. 交叉熵损失源自 Bernoulli 假设下的 MLE；它对“过度自信的错误”惩罚极重。
3. 逻辑回归的梯度更新与线性回归 LMS 形式相同——背后是 GLM 的统一理论（L4）。
4. 牛顿法是二阶优化：利用曲率信息，无学习率、二次收敛，但每步 $O(n^3)$。
5. 参数方法（逻辑回归）vs 非参数方法（LWR）：前者训练后丢弃数据、预测快；后者每次预测都需全部数据。

常见误区与注意事项

• 把逻辑回归的输出当“置信度”过度解读：$h_\theta(x)$ 是条件概率 $P(y=1\vert x)$ 的估计，但对类别不平衡或分布漂移的数据，校准性（calibration）可能很差。
• 决策边界一定是线性的：逻辑回归本质是线性分类器；非线性需要特征工程（多项式特征、核方法，见 L7）。
• 用梯度下降最大化 $\ell$ 时误用“减”梯度：$\ell$ 是似然，应加梯度（上升）；若在最小化负对数似然，则减梯度。符号搞反是常见 bug。
• 牛顿法 Hessian 不可逆：特征线性相关时 $H$ 奇异；加 $\lambda I$ 正则化（即岭式修正）可解。
• 类别不平衡下盲目用准确率：$y=1$ 只占 1% 时，全预测 0 也有 99% 准确率；应看 Precision/Recall/PR 曲线（TA Lecture: Evaluation Metrics）。

思考题

1. 问题：为什么 Sigmoid 函数满足 $g^{\prime}(z) = g(z)(1-g(z))$，这个性质如何简化逻辑回归梯度推导？
   • 答案：$g^{\prime}(z) = \frac{e^{-z}}{(1+e^{-z})^2} = g(z) \cdot \frac{e^{-z}}{1+e^{-z}} = g(z)(1-g(z))$。推导梯度时会出现 $\frac{\partial h}{\partial \theta_j} = h(1-h)x_j$，与交叉熵的 $\frac{y}{h} - \frac{1-y}{1-h}$ 相乘后恰好抵消分母，得到干净的 $(y - h)x_j$。
2. 问题：牛顿法为什么不需要学习率？它在什么条件下会失败？
   • 答案：牛顿步 $H^{-1}\nabla$ 已按局部曲率缩放了步长（曲率大→步长小），故无 $\alpha$。失败条件：$H$ 奇异（不可逆）或目标函数非凹/非凸（可能跳到鞍点或极大点而非所需极值）；对凹的 $\ell$ 则安全。
3. 问题：LWR 的带宽 $\tau$ 太大或太小时会发生什么？
   • 答案：$\tau \to \infty$ 时所有权重 $\approx 1$，退化为普通线性回归（高偏差/欠拟合）；$\tau \to 0$ 时只有查询点自身权重非零，拟合穿过每个点（高方差/过拟合）。$\tau$ 是偏差-方差权衡的旋钮（呼应 L5）。