线性回归

首先展示了一段视频，介绍了Dean Pomerleau利用监督学习让一辆汽车可以自动行驶。

使用的符号

符号代表的含义
m训练样本的数目
X输入变量，通常也可以称为特征
y输出变量，有时也称为目标变量
(X, y)表示一个样本
($X^{(i)}$, $y^{(i)}$)表示第i个样本
h假设（hypothesis）函数
n特征的个数

推导过程

首先是单个特征的线性假设函数 $h(x)=\theta_0 + \theta_1x$

多个特征的线性假设函数

$h(X)=h_\Theta(X)=\theta_0+\theta_1X_1+\theta_2X_2$

为了便利，定义

$X_0=1$

则有

$h\Theta(X) = \sum_{i=0} ^n \Theta_i X_i = \Theta^TX$

$\Theta$被称为学习算法的参数，利用训练集合选择或学习得到合适的参数值是学习算法的任务。

为了进行预测，一件可以做的事是尝试让学习算法的预测在训练数据上尽可能准确。

那么就得到了线性回归算法里的成本函数。

$J(\Theta) = \frac 1 2 \sum_{i=1}^m(h_\Theta(X^{(i)})-y^{(i)})^2$

我们要做的是要使上述函数的值最小化。

下面有两个方法可以帮助选取$\Theta$以使上述函数的值最小化。

梯度下降（Gradient Descent Algorithm）

这是一个搜索算法，基本的想法是先给参数向量一个初始值，然后不断地改变参数向量使得不断减小，直到我们找到了一个使得取到了最小值，这个算法称之为梯度下降。

算法推导

$\frac \partial {\partial\Theta_i}J(\Theta)$ 这个导数即为梯度在$\theta_i$上下降最陡的方向。

因此更新$\Theta$的过程可以总结为以下公式：

$\Theta_i := \Theta_i - \alpha \frac \partial {\partial\Theta_i}J(\Theta)$

其中$\alpha$为学习速度参数，它控制了算法朝着最陡峭的方向下降的时候迈的步子有多大。$\alpha$值设的过小，算法向着最陡峭方向下降时，每次迈很小的一步，这样它会花很长时间去收敛。值设的过大，算法可能会越过最小值，因为步子迈的太大了。

$$ \begin{align} \frac \partial {\partial\Theta_i}J(\Theta) & = \frac \partial {\partial\Theta_i} \frac 1 2 (h_\Theta(X) - y)^2 \\ & = 2 \ast \frac 1 2 (h_\Theta(X) - y) \frac \partial {\partial\Theta_i}(h_\Theta(X) - y) \\ & = (h_\Theta(X) - y) \frac \partial {\partial\Theta_i}(\Theta_0X_0 + … + \Theta_nX_n -y) \\ & = (h_\Theta(X) -y ) X_i \end{align} $$ 最后得到更新$\Theta$的过程可以总结为以下公式：

$\Theta_i := \Theta_i - \alpha(h_\Theta(X) -y) * X_i$

批梯度下降

算法的过程就是重复以下过程，直接最后收敛。

$\Theta_i := \Theta_i - \alpha \sum_{j=1}^m(h_\Theta(X^{(j)}) -y^{(j)}) * X_i^{(j)}=\Theta_i - \alpha \frac \partial {\partial\Theta_i} J(\Theta)$

在批梯度下降算法中每一次迭代都需要遍历整个训练集合。当训练数据集过大时，就不太适合了，而应该使用随机梯度下降算法

随机梯度下降（增量梯度下降）

伪代码示意：

for j=1 to m {

​ $\Theta_i := \Theta_i - \alpha(h_\Theta(X^{(j)}) - y^{(j)}) \ast X_i^{(j)}$ for all i

}

一直重复上述过程，直至最后收敛。

这个算法可能会在全局最小值附近一直徘徊，通常得到的参数值能够很接近全局最小值，这已经足够了。这个算法通常比批梯度下降算法快得多，尤其是当你有一个大规模训练集合的时候。

正规方程组

对于最小二乘回归问题或者普通的最小二乘问题，实际上存在着方法可以直接给出参数向量的解析表达式，这样为了求参数的值就不需要进行迭代了，这个就是正规方程组。

定义一些符号

符号代表的含义
$\nabla_\Theta J=\begin{bmatrix}\frac {\partial J} {\partial \Theta_0} \\ \vdots \\ \frac {\partial J} {\partial \Theta_n} \\ \end{bmatrix} \in \mathbb R^{n+1}$J是一个关于参数数组的函数，定义J的梯度关于的导数
$\Theta := \Theta - \alpha \nabla_\Theta J \quad \Theta \in \mathbb R^{n+1},\nabla_\Theta J \in \mathbb R^{n+1}$梯度下降更新过程
$f(A) \in \mathbb R \quad A \in \mathbb R^{m*n}$f是一个将m*n的矩阵映射为实数的函数
$\nabla_Af(A) =\begin{bmatrix}\frac {\partial f} {\partial A_{11}} & \cdots & \frac {\partial f} {\partial A_{1n}} \\ \vdots & \cdots & \vdots \\ \frac {\partial f} {\partial A_{m1}} & \cdots & \frac {\partial f} {\partial A_{mn}} \\ \end{bmatrix}$f对于A的导数
$trA=\sum_{i=0}^nA_{ii} \quad if \quad A \in \mathbb R^{n*n}$方阵的迹

一些事实

  1. $trAB = trBA$
  2. $trABC = trCAB = trBCA$
  3. $f(A) = trAB \quad then \quad \nabla_AtrAB=B^T$
  4. $trA = trA^T$
  5. $tr\alpha = \alpha \quad if \quad a \in \mathbb R$
  6. $\nabla_AtrABA^TC = CAB + C^TAB^T$

证明正规方程过程中将用到上面所述的事实。

推导过程

定义 $$ X = \begin{bmatrix} (X^{(1)})^T \\ \vdots \\ (X^{(m)})^T \end{bmatrix} $$ 则

$$ X\Theta = \begin{bmatrix}(X^{(i)})^T\Theta \\ \vdots \\ (X^{(m)})^T\Theta \end{bmatrix} = \begin{bmatrix}h_\Theta(X^{(1)} \\ \vdots \\ h_\Theta(X^{(m)} \end{bmatrix} $$ 再定义 $$ Y = \begin{bmatrix} y^{(1)} \\ \vdots \\ y^{(m)}\end{bmatrix} $$ 然后得到 $$ X\Theta \ast y = \begin{bmatrix} h(X^{(1)} - y^{(1)}) \\ \vdots \\ h(X^{(m)} - y^{(m)}) \end{bmatrix} $$ 又因为

$$ Z^TZ=\sum_iZ_i^2 \quad if \quad Z \in \mathbb R^{m*1} $$ 所以

$$ \frac 1 2 (X\Theta - y) ^ T (X\Theta - y) = \frac 1 2 \sum_{i=1}^m(h(X^{(i)}) - y)^2 = J(\Theta) $$ 然后算法的目标(算法尽量收敛)是

$$ \nabla_\Theta J(\Theta) \approx \overrightarrow 0 $$ 所以有

$$ \begin {align} \nabla_\Theta \frac 1 2 (X\Theta - y )^T(X\Theta - y ) & = \frac 1 2 \nabla_\Theta tr ( \Theta^T X^T X \Theta - \Theta^T X^T y - y^T X \Theta + y^T y) \\ & = \frac 1 2 \left[ \nabla_\Theta tr \Theta \Theta^TX^TX - \nabla_\Theta tr y^T X \Theta - \nabla_\Theta y^T X \Theta \right] \\ & = \frac 1 2 \left[ X^T X \Theta + X^T X \Theta - X^Ty - X^Ty \right] \\ & = X^TX\Theta - X^Ty \\ & = 0 \end {align} $$ 最后就有 $$ X^TX\Theta = X^Ty $$ 上述公式被称为正规方程组。我们现在可以给出这个关于的方程组解的解析表达式了： $$ \Theta = (X^TX)^{-1}X^Ty $$ 上述公式要求$X^TX$可逆，如果$X^TX$不可逆，可以用伪逆最小化的方法来解决这个问题。