单变量线性回归

单变量线性回归(Linear Regression with One Variable)

模型表示(Model Representation)

房价预测训练集

Size in $feet^2$ ($x$)	Price ($) in 1000’s($y$)
2104	460
1416	232
1534	315
852	178
…	…

房价预测训练集中，同时给出了输入 $x$ 和输出结果 $y$，即给出了人为标注的”正确结果”，且预测的量是连续的，属于监督学习中的回归问题。

问题解决模型

其中 $h$ 代表结果函数，也称为假设(hypothesis) 。假设函数根据输入(房屋的面积)，给出预测结果输出(房屋的价格)，即是一个 $X\to Y$ 的映射。

$h_\theta(x)=\theta_0+\theta_1x$，为解决房价问题的一种可行表达式。

$x$: 特征/输入变量。

上式中，$\theta$ 为参数，$\theta$ 的变化才决定了输出结果，不同以往，这里的 $x$ 被我们视作已知(不论是数据集还是预测时的输入)，所以怎样解得 $\theta$ 以更好地拟合数据，成了求解该问题的最终问题。

单变量，即只有一个特征(如例子中房屋的面积这个特征)。

代价函数(Cost Function)

我们的目的在于求解预测结果 $h$ 最接近于实际结果 $y$ 时 $\theta$ 的取值，则问题可表达为求解 $\sum\limits_{i=0}^{m}(h_\theta(x^{(i)})-y^{(i)})$ 的最小值。

$m$: 训练集中的样本总数

$y$: 目标变量/输出变量

$\left(x, y\right)$: 训练集中的实例

$\left(x^{\left(i\right)},y^{\left(i\right)}\right)$: 训练集中的第 $i$ 个样本实例

假设函数(Hypothesis): $h_\theta(x)=\theta_0+\theta_1x$

参数(Parameters): $\theta_0, \theta_1$

代价函数(Cost Function): $J\left( \theta_0, \theta_1 \right)=\frac{1}{2m}\sum\limits_{i=1}^{m}{{{\left( {{h}_{\theta }}\left( {{x}^{(i)}} \right)-{{y}^{(i)}} \right)}^{2}}}$

目标(Goal): $\underset{\theta_0, \theta_1}{\text{minimize}} J \left(\theta_0, \theta_1 \right)$

为了直观理解代价函数到底是在做什么，先假设 $\theta_1 = 0$，并假设训练集有三个数据，分别为$\left(1, 1\right), \left(2, 2\right), \left(3, 3\right)$，这样在平面坐标系中绘制出 $h_\theta\left(x\right)$ ，并分析 $J\left(\theta_0, \theta_1\right)$ 的变化。

右图 $J\left(\theta_0, \theta_1\right)$ 随着 $\theta_1$ 的变化而变化，可见当 $\theta_1 = 1$ 时，$J\left(\theta_0, \theta_1 \right) = 0$，取得最小值对应于左图青色直线，即函数 $h$ 拟合程度最好的情况。

参数在 $\theta_0$ 不恒为 $0$ 时代价函数 $J\left(\theta\right)$ 关于 $\theta_0, \theta_1$ 的**轮廓图(contour plot)**如下图所示，其中相同颜色的一个圈代表着同一高度（同一 $J\left(\theta\right)$ 值）。

$\theta_0 = 360, \theta_1 =0$ 时：

大概在 $\theta_0 = 250, \theta_1 =0.12$ 时：

上图中最中心的点（红点），近乎为图像中的最低点，也即代价函数的最小值，此时对应 $h_\theta\left(x\right)$ 对数据的拟合情况如左图所示。

为了求解最小值，引入了代价函数(Cost Function)概念，用于度量建模误差。考虑到要计算最小值，应用二次函数对求和式建模，即应用统计学中的平方损失函数（最小二乘法）：

$$
J(\theta_0,\theta_1)=\dfrac{1}{2m}\displaystyle\sum_{i=1}^m\left(\hat{y}{i}-y{i} \right)^2=\dfrac{1}{2m}\displaystyle\sum_{i=1}^m\left(h_\theta(x_{i})-y_{i}\right)^2
$$

$\hat{y}$: $y$ 的预测值

系数 $\frac{1}{2}$ 存在与否都不会影响结果，这里是为了在应用梯度下降时便于求解，平方的导数会抵消掉 $\frac{1}{2}$ 。

讨论到这里，我们的问题就转化成了求解 $J\left( \theta_0, \theta_1 \right)$ 的最小值。

最小二乘法（least square method）就是基于均方误差最小化来进行模型求解的一种方法，寻找可使损失函数值最小的参数 $w$ 和 $b$ 的过程称为最小二乘参数估计（parameter estimation）。

通过对损失函数分别求参数 $w$ 和 $b$ 的偏导，并且令导数为 0，可以得到这两个参数的闭式（closed-form）解（也即解析解）：

$$
w = \frac{\sum_{i=1}^m y_i(x_i - \bar{x})}{\sum_{i=1}^m x_i^2 - \frac{1}{m}(\sum_{i=1}^m x_i)^2} \
b = \frac{1}{m} \sum_{i=1}^m (y_i-wx_i)
$$

在实际任务中，只要我们把自变量（x, y, m）的值代入就可以求出数值解了。

为什么可以这样求解呢？因为损失函数是一个凸函数（记住是向下凸，类似 U 型曲线），导数为 0 表示该函数曲线最低的一点，此时对应的参数值就是能使均方误差最小的参数值。特别地，要判断一个函数是否凸函数，可以求其二阶导数，若二阶导数在区间上非负则称其为凸函数，若在区间上恒大于零则称其为严格凸函数。

凸函数： $f(\frac{x_1+x_2}{2}) \leq \frac{f(x_1)+f(x_2)}{2}$

梯度下降(Gradient Descent)

在特征量很大的情况下，即便是借用计算机来生成图像，人工的方法也很难读出 $J\left(\theta\right)$ 的最小值，并且大多数情况无法进行可视化，故引入梯度下降(Gradient Descent)方法，让计算机自动找出最小化代价函数时对应的 $\theta$ 值。

梯度下降背后的思想是：开始时，我们随机选择一个参数组合$\left( {\theta_{0}},{\theta_{1}},……,{\theta_{n}} \right)$ 起始点，计算代价函数，然后寻找下一个能使得代价函数下降最多的参数组合。不断迭代，直到找到一个局部最小值(local minimum)，由于下降的情况只考虑当前参数组合周围的情况，所以无法确定当前的局部最小值是否就是全局最小值(global minimum)，不同的初始参数组合，可能会产生不同的局部最小值。

下图根据不同的起始点，产生了两个不同的局部最小值。

视频中举了下山的例子，即我们在山顶上的某个位置，为了下山，就不断地看一下周围下一步往哪走下山比较快，然后就迈出那一步，一直重复，直到我们到达山下的某一处陆地。

梯度下降公式：

$$
\begin{align*}
& \text{Repeat until convergence:} ; \lbrace \
&{{\theta }{j}}:={{\theta }{j}}-\alpha \frac{\partial }{\partial {{\theta }{j}}}J\left( {\theta{0}},{\theta_{1}} \right) \
\rbrace
\end{align*}
$$

${\theta }_{j}$: 第 $j$ 个特征参数

”:=“: 赋值操作符

$\alpha$: 学习速率(learning rate), $\alpha > 0$

$\frac{\partial }{\partial {{\theta }_{j}}}J\left( \theta_0, \theta_1 \right)$: $J\left( \theta_0, \theta_1 \right)$ 的偏导

公式中，学习速率决定了参数值变化的速率即”走多少距离“，而偏导这部分决定了下降的方向即”下一步往哪里“走（当然实际上的走多少距离是由偏导值给出的，学习速率起到调整后决定的作用），收敛处的局部最小值又叫做极小值，即”陆地“。

注意，在计算时要批量更新 $\theta$ 值，即如上图中的左图所示，否则结果上会有所出入，原因不做细究。

梯度下降直观理解(Gradient Descent Intuition)

该节探讨 $\theta_1$ 的梯度下降更新过程，即 $\theta_1 := \theta_1 - \alpha\frac{d}{d\theta_1}J\left(\theta_1\right)$，此处为了数学定义上的精确性，用的是 $\frac{d}{d\theta_1}J\left(\theta_1\right)$，如果不熟悉微积分学，就把它视作之前的 $\frac{\partial}{\partial\theta}$ 即可。

把红点定为初始点，切于初始点的红色直线的斜率，表示了函数 $J\left(\theta\right)$ 在初始点处有正斜率，也就是说它有正导数，则根据梯度下降公式，${{\theta }{j}}:={{\theta }{j}}-\alpha \frac{\partial }{\partial {{\theta }_{j}}}J\left( \theta_0, \theta_1 \right)$ 右边的结果是一个正值，即 $\theta_1$ 会向左边移动。这样不断重复，直到收敛（达到局部最小值，即斜率为 0）。

初始 $\theta$ 值（初始点）是任意的，若初始点恰好就在极小值点处，梯度下降算法将什么也不做（$\theta_1 := \theta_1 - \alpha*0$）。

不熟悉斜率的话，就当斜率的值等于图中三角形的高度除以水平长度好啦，精确地求斜率的方法是求导。

对于学习速率 $\alpha$，需要选取一个合适的值才能使得梯度下降算法运行良好。

学习速率过小图示：

收敛的太慢，需要更多次的迭代。
学习速率过大图示：

可能越过最低点，甚至导致无法收敛。

学习速率只需选定即可，不需要在运行梯度下降算法的时候进行动态改变，随着斜率越来越接近于 0，代价函数的变化幅度会越来越小，直到收敛到局部极小值。

如图，品红色点为初始点，代价函数随着迭代的进行，变化的幅度越来越小。

最后，梯度下降不止可以用于线性回归中的代价函数，还通用于最小化其他的代价函数。

线性回归中的梯度下降(Gradient Descent For Linear Regression)

线性回归模型

$h_\theta(x)=\theta_0+\theta_1x$
$J\left( \theta_0, \theta_1 \right)=\frac{1}{2m}\sum\limits_{i=1}^{m}{{{\left( {{h}_{\theta }}\left( {{x}^{(i)}} \right)-{{y}^{(i)}} \right)}^{2}}}$

梯度下降算法

直接将线性回归模型公式代入梯度下降公式可得出公式

当 $j = 0, j = 1$ 时，线性回归中代价函数求导的推导过程：

$$
\begin{align*}
\frac{\partial}{\partial\theta_j} J(\theta_1, \theta_2)&=\frac{\partial}{\partial\theta_j} \left(\frac{1}{2m}\sum\limits_{i=1}^{m}{{\left( {{h}{\theta }}\left( {{x}^{(i)}} \right)-{{y}^{(i)}} \right)}^{2}} \right)\
&=\left(\frac{1}{2m}*2\sum\limits{i=1}^{m}{{\left( {{h}{\theta }}\left( {{x}^{(i)}} \right)-{{y}^{(i)}} \right)}} \right)*\frac{\partial}{\partial\theta_j}{{\left( {{h}{\theta }}\left( {{x}^{(i)}} \right)-{{y}^{(i)}} \right)}}\
&=\left(\frac{1}{m}\sum\limits_{i=1}^{m}{{\left( {{h}_{\theta }}\left( {{x}^{(i)}} \right)-{{y}^{(i)}} \right)}} \right)\frac{\partial}{\partial\theta_j}{{\left(\theta_0{x_0^{(i)}} + \theta_1{x_1^{(i)}}-{{y}^{(i)}} \right)}}
\end{align}
$$

所以当 $j = 0$ 时：

$$
\frac{\partial}{\partial\theta_0} J(\theta)=\frac{1}{m}\sum\limits_{i=1}^{m}{{\left( {{h}_{\theta }}\left( {{x}^{(i)}} \right)-{{y}^{(i)}} \right)}} *x_0^{(i)}
$$

所以当 $j = 1$ 时：

$$
\frac{\partial}{\partial\theta_1} J(\theta)=\frac{1}{m}\sum\limits_{i=1}^{m}{{\left( {{h}_{\theta }}\left( {{x}^{(i)}} \right)-{{y}^{(i)}} \right)}} *x_1^{(i)}
$$

上文中所提到的梯度下降，都为批量梯度下降(Batch Gradient Descent)，即每次计算都使用所有的数据集 $\left(\sum\limits_{i=1}^{m}\right)$ 更新。

由于线性回归函数呈现碗状，且只有一个全局的最优值，所以函数一定总会收敛到全局最小值（学习速率不可过大）。同时，函数 $J$ 被称为凸二次函数，而线性回归函数求解最小值问题属于凸函数优化问题。