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

线性回归

• 线性回归是最简单的监督学习回归问题。监督学习的基本流程：

  1. 测试数据集，包含一系列\((x, y)\)对
  2. 数据输入到学习算法
  3. 输出一个函数\(h\)，使得该函数可以很好地为输入的 x 生成对应的 y
  4. 使用函数\(h\)对其他数据进行预测

  

• 函数的表示
  \[ h = \theta_{1}x_1 + \theta_{2}x_2 + ... + \theta_nx_n + b = \sum_{j=0}^{n}\theta_i x_i \]
  其中，\(x_0\)始终为1。如果写成矩阵形式，即 \(\theta = \begin{bmatrix}\theta_0 \\ \theta_2 \\ \vdots\end{bmatrix}, \ x = \begin{bmatrix}x_0 \\ x_1 \\ \vdots \end{bmatrix}\) , 则上述公式可以写成:
  \[ h_\theta(x) = \theta^T x \]

• 常用符号

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

• 参数的选择
  \[ \tt{choose} \ \theta \\ st. h(x) \approx y \ \ \ \tt{for \ every \ training \ example} \]
  对于线性回归问题，目标参数可以形式化的表示为
  \[ J(\theta) = \frac{1}{2} \sum_{i=1}^{m}(h_{\theta}(x^{(i)}) - y^{(i)})^2 \\ \\ \theta = \mathop{\arg\min}\limits_{\theta} \ J(\theta) \]
  \(J(x)\) 通常被称为成本函数，即 cost function.

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

批量梯度下降

• 批量梯度下降形式化表示：
  \[ \theta_j := \theta_j - \alpha \frac{\partial \ J(\theta)}{\partial\ \theta_j} \ \\ \tt{(repeat \ until \ convergence)} \]

​ 其中，\(\alpha\)表示学习率。对于线性回归来说，\(\frac{\partial \ J(\theta)}{\partial\ \theta_j}\)的计算如下所示：
\[ \frac{\partial \ J(\theta)}{\partial\ \theta_j} = \sum_{i = 1}^m (h_\theta(x^{(i)}) - y^{(i)}) \ x_j^{(i)} \]
​因此，线性回归的梯度下降公式就可以表示为：
\[ \theta_j := \theta_j - \alpha \sum_{i = 1}^m (h_\theta(x^{(i)}) - y^{(i)}) \ x_j^{(i)} \\ \tt{(repeat \ until \ convergence)} \]

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

随机梯度下降

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

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

正规方程

基本形式

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

推导

在推导之前我们需要用到以下公式：
\[ \begin{aligned} \nabla_Atr AB &= B^T \\ \nabla_{A^T} f(A)&= (\nabla_A f(A))^T \\ \nabla_A tr ABA^TC &= CAB + C^TAB^T \\ \nabla_A |A| &= |A|(A^{-1})^T \end{aligned} \]
下面就可以开始推导啦
\[ \begin{aligned} \nabla_\theta J(\theta) &= \nabla_\theta \frac{1}{2}(X\theta-Y)^T(X\theta-Y) \\ &= \frac{1}{2} \nabla_\theta(\theta^TX^T - Y^T)(X\theta - Y) \\ &= \frac{1}{2} \nabla_\theta(\theta^TX^TX\theta - \theta^TX^TY - Y^TX\theta + Y^TY) \\ &= \frac{1}{2} \nabla_\theta tr(\theta^TX^TX\theta - \theta^TX^TY - Y^TX\theta + Y^TY) \\ &= \frac{1}{2} \nabla_\theta (tr \theta^TX^TX\theta - 2 tr Y^TX\theta) \\ &= \frac{1}{2} (\nabla_\theta tr \theta^TX^TX\theta - 2 \nabla_\theta tr Y^TX\theta) \\ &= \frac{1}{2} ((\nabla_{\theta^T} tr \theta^T(X^TX)\theta I)^T - 2 \nabla_\theta tr Y^TX\theta) \\ &= \frac{1}{2} (X^TX\theta + X^TX\theta - 2 \nabla_\theta tr Y^TX\theta) \\ &= X^TX\theta - X^TY \end{aligned} \]
令 \(\nabla_\theta J(\theta) = 0\) 即可得到正规方程：
\[ \theta = (X^TX)^{-1}X^TY \]