线性回归与梯度下降

线性回归基础

基本术语与符号

以一个波特兰市的房价预测模型作为例子，假设我们有如下数据：

• 输入特征 (x⁽ⁱ⁾)：例如房子的建筑面积。
• 输出/目标变量 (y⁽ⁱ⁾)：我们要预测的值，例如房价。
• 训练示例 ((x⁽ⁱ⁾, y⁽ⁱ⁾))：一组输入和输出的配对。
• 训练集：包含 n 个训练示例的数据集。
• 假设 (h)：我们要学习的预测函数，输入 x 并输出预测值。
• 回归问题：当预测的目标变量是连续值（如价格）时。
• 分类问题：当预测目标是离散值（如判断是“住宅”还是“公寓”）时。

概念	常见维度符号	在 d 个特征、n 个样本下的具体维度
单条输入特征x	x ∈ ℝd + 1	(d + 1) × 1(列向量)
单条输出变量y	y ∈ ℝ	1 × 1(标量)
参数θ	θ ∈ ℝd + 1	(d + 1) × 1(列向量)
设计矩阵X	X ∈ ℝn × (d + 1)	n × (d + 1)(矩阵)
目标向量y⃗	y⃗ ∈ ℝn	n × 1(向量)

x⁽ⁱ⁾ 表示第 i 个训练样本的输入特征向量，y⁽ⁱ⁾ 表示对应的输出变量。 x_i 表示输入特征向量中的第 i 个特征值。

线性回归模型

假设预测函数是线性的：

$$ h_{\theta}(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 = \sum_{i=0}^{d} \theta_i x_i = \theta^T x $$

其中，θ是参数（或称为权重），x₀ = 1 是截距项 。

成本函数

为了评估参数 θ 的优劣，定义了最小二乘法成本函数：

$$ J(\theta) = \frac{1}{2} \sum_{i=1}^{n} (h_{\theta}(x^{(i)}) - y^{(i)})^2 $$

目标是找到使 J(θ) 最小的 θ 值 。

优化算法

梯度下降算法

θ_j := θ_j + α(y⁽ⁱ⁾ − h_θ(x⁽ⁱ⁾))x_j⁽ⁱ⁾

• SGD 随机梯度下降算法：每遇到一个示例就立即更新参数 。它在处理大数据集时速度更快，但参数会在最小值附近震荡 。
• 批量梯度下降（Batch Gradient Descent） ：每走一步都要扫描整个训练集的所有示例 。由于 J 是凸二次函数，它总是能收敛到全局最小值 。

α 是学习率，控制每次更新的步长大小。选择合适的学习率对于算法的收敛速度和稳定性至关重要。

证明梯度下降算法公式

梯度下降规则：

$$ \theta_{j}:=\theta_{j}-\alpha\frac{\partial}{\partial\theta_{j}}J(\theta) $$

我们针对单个训练样本 (x, y) 来计算偏导数：

$$ \frac{\partial}{\partial\theta_{j}}J(\theta) = \frac{\partial}{\partial\theta_{j}}\frac{1}{2}(h_{\theta}(x)-y)^{2} $$

$$ = 2\cdot\frac{1}{2}(h_{\theta}(x)-y)\cdot\frac{\partial}{\partial\theta_{j}}(h_{\theta}(x)-y) $$

$$ = (h_{\theta}(x)-y)\cdot\frac{\partial}{\partial\theta_{j}}(\sum_{i=0}^{d}\theta_{i}x_{i}-y) $$

 = (h_θ(x) − y)x_j

当完成单个样本的求导并得到结果 (h_θ(x) − y)x_j 后，在实际应用到整个训练集时，再根据不同的梯度下降算法进行更新

• 批量梯度下降 (Batch Gradient Descent)：在更新参数时，会把所有样本的梯度累加起来：

$$ \theta_j := \theta_j + \alpha \sum_{i=1}^{n} (y^{(i)} - h_{\theta}(x^{(i)})) x_j^{(i)} $$

• 随机梯度下降 (Stochastic Gradient Descent)：则不需要求和，它直接使用推导出的单个样本的梯度来更新参数，每次只看一个例子 。

正规方程

除了迭代算法，还可以通过矩阵运算直接求得 θ 的闭式解：

θ = (X^TX)⁻¹X^Ty⃗

这种方法不需要迭代，直接一步到位。

推导过程

成本函数的矩阵表示

为了简化计算，我们将预测值与真实值之间的差异表示为向量形式：

$$ X\theta - \vec{y} = \begin{bmatrix} (x^{(1)})^T \theta \\ \vdots \\ (x^{(n)})^T \theta \end{bmatrix} - \begin{bmatrix} y^{(1)} \\ \vdots \\ y^{(n)} \end{bmatrix} = \begin{bmatrix} h_{\theta}(x^{(1)}) - y^{(1)} \\ \vdots \\ h_{\theta}(x^{(n)}) - y^{(n)} \end{bmatrix} $$

利用向量恒等式 z^Tz = ∑_iz_i²，我们可以将成本函数 J(θ) 重写为矩阵-向量符号 ：

$$ \frac{1}{2}(X\theta - \vec{y})^T (X\theta - \vec{y}) = \frac{1}{2} \sum_{i=1}^n (h_{\theta}(x^{(i)}) - y^{(i)})^2 = J(\theta) $$

梯度推导（矩阵形式）

为了最小化 J，我们需要找到它对 θ 的导数 。推导过程如下 ：

$$ \begin{aligned} \nabla_{\theta} J(\theta) &= \nabla_{\theta} \frac{1}{2}(X\theta - \vec{y})^T (X\theta - \vec{y}) \\ &= \frac{1}{2} \nabla_{\theta} ((X\theta)^T X\theta - (X\theta)^T \vec{y} - \vec{y}^T (X\theta) + \vec{y}^T \vec{y}) \\ &= \frac{1}{2} \nabla_{\theta} (\theta^T (X^T X) \theta - \vec{y}^T (X\theta) - \vec{y}^T (X\theta)) \\ &= \frac{1}{2} \nabla_{\theta} (\theta^T (X^T X) \theta - 2(X^T \vec{y})^T \theta) \\ &= \frac{1}{2} (2 X^T X \theta - 2 X^T \vec{y}) \\ &= X^T X \theta - X^T \vec{y} \end{aligned} $$

∇_x(x^TAx) = 2Ax

∇_x(b^Tx) = b

变量/表达式	形状 (Shape)	含义
X	n × (d + 1)	数据矩阵（样本×特征）
θ	(d + 1) × 1	权重参数列向量
Xθ	n × 1	对所有样本的预测值
J(θ)	1 × 1(标量)	总误差（损失）
XTX	(d + 1) × (d + 1)	特征间的协方差相关矩阵
∇θJ(θ)	(d + 1) × 1	误差对每个参数的下降方向

最小二乘法证明

1.误差假设：假设目标变量 y 与输入 x 的关系为 y⁽ⁱ⁾ = θ^Tx⁽ⁱ⁾ + ϵ⁽ⁱ⁾，其中 ϵ⁽ⁱ⁾ 是捕捉未建模效应或随机噪声的误差项 。

2.高斯噪声假设：假设误差 ϵ⁽ⁱ⁾ 服从独立同分布 (IID) 的高斯分布（正态分布），$^{(i)} (0,^2) $ 均值为0，方差为 σ² 。这意味着给定 x，y 的条件分布也服从高斯分布 ：

p(y⁽ⁱ⁾|x⁽ⁱ⁾; θ) ∼ 𝒩(θ^Tx⁽ⁱ⁾, σ²)

3.写出似然函数（likelihood）

因为每个样本独立：

$$ L(\theta)=\prod_{i=1}^n p(y^{(i)}|x^{(i)};\theta) $$

代入高斯密度函数后得到一个指数形式的乘积。

使用分号是为了区分条件变量和 模型参数 。在频率派观点下，参数 θ 是确定的常数，不是随机变量，所以我们不能像对待 x 那样‘条件化’它（即不能写成 p(y|x, θ)）。如果是贝叶斯派，我们会认为 θ 也是随机变量，那时候就会用逗号了。

4.最大化对数似然（log-likelihood）

取 log（因为 log 单调递增且能把乘积变加法）：

$$ \ell(\theta) = -\frac{1}{2\sigma^2}\sum_{i=1}^n (y^{(i)} - \theta^T x^{(i)})^2 + \text{常数} $$

最大化 log-likelihood 等价于最小化：

$$ \begin{aligned} l(\theta) &= \log L(\theta) \\ &= \log \prod_{i=1}^{n} \frac{1}{\sqrt{2\pi}\sigma} \exp\left(-\frac{(y^{(i)}-\theta^T x^{(i)})^2}{2\sigma^2}\right) \\ &= \sum_{i=1}^{n} \log \frac{1}{\sqrt{2\pi}\sigma} \exp\left(-\frac{(y^{(i)}-\theta^T x^{(i)})^2}{2\sigma^2}\right) \\ &= n \log \frac{1}{\sqrt{2\pi}\sigma} - \frac{1}{\sigma^2} \cdot \frac{1}{2} \sum_{i=1}^{n} (y^{(i)}-\theta^T x^{(i)})^2 \end{aligned} $$

$$ \sum_{i=1}^n (y^{(i)} - \theta^T x^{(i)})^2 $$

这正是线性回归的平方误差代价函数 (J(θ))。

局部加权线性回归 LWR

线性回归的一种扩展方法，区别于普通的线性回归，它在拟合时对训练样本赋予不同的权重，通常是根据样本点与预测点的距离来决定权重大小。这样，模型在预测某一点时，更关注该点附近的训练样本，从而实现局部线性拟合，适合处理非线性或局部变化明显的数据。

在原始的线性回归算法中，为了在查询点 x 处进行预测（即计算 h(x)），我们会：

1. 拟合 θ 以最小化 ∑_i(y⁽ⁱ⁾ − θ^Tx⁽ⁱ⁾)²。
2. 输出 θ^Tx。

相比之下，局部加权线性回归算法执行以下操作：

1. 拟合 θ 以最小化 ∑_iw⁽ⁱ⁾(y⁽ⁱ⁾ − θ^Tx⁽ⁱ⁾)²。
2. 输出 θ^Tx。

这里的 w⁽ⁱ⁾ 是非负值的权重。直观上，如果对于某个特定的 i，权重 w⁽ⁱ⁾ 很大，那么在选择 θ 时，我们会努力使 (y⁽ⁱ⁾ − θ^Tx⁽ⁱ⁾)² 变小。如果 w⁽ⁱ⁾ 很小，那么在拟合过程中该项误差几乎会被忽略。

权重的标准选择通常是：

$$ w^{(i)} = \exp\left(-\frac{(x^{(i)} - x)^2}{2\tau^2}\right) $$

请注意，权重取决于我们试图求值的特定点 x。此外，如果 |x⁽ⁱ⁾ − x| 很小，那么 w⁽ⁱ⁾ 接近 1；如果 |x⁽ⁱ⁾ − x| 很大，则 w⁽ⁱ⁾ 也很小。因此，在选择 θ 时，离查询点 x 较近的训练样本会被赋予更高的“权重”（其误差影响更大）。（还要注意，虽然权重的公式在形式上与高斯分布的密度函数相似，但 w⁽ⁱ⁾ 与高斯分布并没有直接关系；特别是 w⁽ⁱ⁾ 不是随机变量，无论是否服从正态分布。）参数 τ 控制了训练样本的权重随其 x⁽ⁱ⁾ 与查询点 x 的距离增加而下降的速度；τ 被称为 带宽参数（bandwidth parameter） 。可以表示选择多大的范围。

LWR是一种非参数化算法：

• 它的逻辑： 这种算法不总结全局规律。它认为：“我不预测未来的总趋势，我只针对你现在问我的这个特定点 x，看看它周围的邻居长什么样，再做决定。”
• 训练完之后： 你不能扔掉训练数据。
• 预测时： 当你问：“如果输入是 x，输出是多少？”算法必须立刻翻开“记录本”，找到离 x 最近的那些点 x⁽ⁱ⁾，给它们计算权重 w⁽ⁱ⁾，然后现场拟合一条局部的直线。
• 为什么叫“非参数化”？ 这里的“非参数”并不是指没有参数，而是指 为了准确描述这个模型（即假设 h），你需要保留的信息量会随着训练集的大小线性增长 。
  • 如果你有 1000 个训练点，你就得存 1000 个点；如果你有 100 万个点，你就得存 100 万个点。
• 总结： 模型存储的“负担”随数据量 线性增长 。