「CS229」Lecture2：线性回归和梯度下降

发布日期: 2023-06-23

文章字数: 1.1k

阅读时长: 5 分

线性回归

线性回归是最简单的监督学习回归问题。监督学习的基本流程：
1. 测试数据集，包含一系列 $(x, y)$ 对
2. 数据输入到学习算法
3. 输出一个函数 $h$ ，使得该函数可以很好地为输入的 x 生成对应的 y
4. 使用函数 $h$ 对其他数据进行预测
函数的表示
$h = θ_{1} x_{1} + θ_{2} x_{2} + . . . + θ_{n} x_{n} + b = \sum_{j = 0}^{n} θ_{i} x_{i}$
其中， $x_{0}$ 始终为1。如果写成矩阵形式，即 $θ = [\begin{matrix} θ_{0} \\ θ_{2} \\ ⋮ \end{matrix}], x = [\begin{matrix} x_{0} \\ x_{1} \\ ⋮ \end{matrix}]$ , 则上述公式可以写成:
$h_{θ} (x) = θ^{T} x$

常用符号

符号	含义
$θ$	参数
$m$	训练集的大小
$x$	输入 / 特征
$y$	输出 / 目标变量
$(x^{(i)}, y^{(i)})$	训练集中第 i 个训练样本
$(x, y)$	训练集中某一个训练样本
$x_{j}^{(i)}$	第 i 个训练样例的第 j 个特征
$n$	特征数量

参数的选择
$c h o o s e θ s t . h (x) \approx y f o r e v e r y t r a i n i n g e x a m p l e$
对于线性回归问题，目标参数可以形式化的表示为
$J (θ) = \frac{1}{2} \sum_{i = 1}^{m} (h_{θ} (x^{(i)}) - y^{(i)})^{2} θ = \underset{θ}{\arg min} J (θ)$
$J (x)$ 通常被称为成本函数，即 cost function.

批量梯度下降和随机梯度下降

批量梯度下降

批量梯度下降形式化表示：
$θ_{j} := θ_{j} - α \frac{\partial J (θ)}{\partial θ_{j}} (r e p e a t u n t i l c o n v e r g e n c e)$

其中， $α$ 表示学习率。对于线性回归来说， $\frac{\partial J (θ)}{\partial θ_{j}}$ 的计算如下所示：
$\frac{\partial J (θ)}{\partial θ_{j}} = \sum_{i = 1}^{m} (h_{θ} (x^{(i)}) - y^{(i)}) x_{j}^{(i)}$
因此，线性回归的梯度下降公式就可以表示为：
$θ_{j} := θ_{j} - α \sum_{i = 1}^{m} (h_{θ} (x^{(i)}) - y^{(i)}) x_{j}^{(i)} (r e p e a t u n t i l c o n v e r g e n c e)$

这里的“批“的意思是：每一次进行梯度下降更新参数时，都用到了一批数据参与运算。在上面的例子中，我们将训练集中所有的数据作为“一批”。每一次参数更新时，计算该批中每一条数据对应的“损失”，最终将所有的损失求和，其实也就是 $J (θ)$ 。然后根据 $J (θ)$ 和公式$_j := _j - \ $ 对每个参数进行“一次“更新。

随机梯度下降

对于每一条数据，即 $(x^{(i)}, y^{(i)})$ ，都进行一次梯度下降。此时梯度下降的过程就变为
$\begin{aligned} r e p e a t u n t i l c o n v e r g e n c e { \\ f o r i = 0 t o m { \\ θ_{j} := θ_{j} - α \frac{(h_{θ} (x^{(i)}) - y^{(i)})^{2}}{θ_{j}} \\ } \\ } \end{aligned}$
批量梯度下降法在进行一次迭代之前必须扫描整个训练集，如果m很大的话，计算开销非常高。而随机梯度下降法每次只针对一条数据进行梯度下降，因此能够更快地使 $θ$ “接近”最小值。但是需要注意的是，随机梯度下降可能永远不会“收敛”到最小值，并且参数 $θ$ 将在 $θ$ 的最小值周围振荡；但在实践中，大多数“接近最小值的值”就是对真实最小值的合理近似。

因此，通常更推荐使用随机梯度下降，尤其是数据集合规模较大的时候。

正规方程

基本形式

正规方程其实就是对上述的 $J (θ)$ 求偏导、并令偏导数等于0得到的。因此他只适用于线性回归。
$θ = (X^{T} X)^{- 1} X^{T} Y X = [\begin{matrix} — (x^{(1)})^{T} — \\ — (x^{(2)})^{T} — \\ ⋮ \\ — (x^{(m)})^{T} — \end{matrix}], Y = [\begin{matrix} y^{(1)} \\ y^{(2)} \\ ⋮ \\ y^{(m)} \end{matrix}]$

推导

在推导之前我们需要用到以下公式：
$\begin{aligned} \nabla_{A} t r A B & = B^{T} \\ \nabla_{A^{T}} f (A) & = (\nabla_{A} f (A))^{T} \\ \nabla_{A} t r A B A^{T} C & = C A B + C^{T} A B^{T} \\ \nabla_{A} | A | & = | A | (A^{- 1})^{T} \end{aligned}$
下面就可以开始推导啦
$\begin{aligned} \nabla_{θ} J (θ) & = \nabla_{θ} \frac{1}{2} (X θ - Y)^{T} (X θ - Y) \\ = \frac{1}{2} \nabla_{θ} (θ^{T} X^{T} - Y^{T}) (X θ - Y) \\ = \frac{1}{2} \nabla_{θ} (θ^{T} X^{T} X θ - θ^{T} X^{T} Y - Y^{T} X θ + Y^{T} Y) \\ = \frac{1}{2} \nabla_{θ} t r (θ^{T} X^{T} X θ - θ^{T} X^{T} Y - Y^{T} X θ + Y^{T} Y) \\ = \frac{1}{2} \nabla_{θ} (t r θ^{T} X^{T} X θ - 2 t r Y^{T} X θ) \\ = \frac{1}{2} (\nabla_{θ} t r θ^{T} X^{T} X θ - 2 \nabla_{θ} t r Y^{T} X θ) \\ = \frac{1}{2} ((\nabla_{θ^{T}} t r θ^{T} (X^{T} X) θ I)^{T} - 2 \nabla_{θ} t r Y^{T} X θ) \\ = \frac{1}{2} (X^{T} X θ + X^{T} X θ - 2 \nabla_{θ} t r Y^{T} X θ) \\ = X^{T} X θ - X^{T} Y \end{aligned}$
令 $\nabla_{θ} J (θ) = 0$ 即可得到正规方程：
$θ = (X^{T} X)^{- 1} X^{T} Y$