问题引入

考虑一个实际问题，房子相关信息（大小、位置、户型、房龄等）和房价的关系。假设已经收集到了一批数据，当再次给出房子信息时，请预测对应的房价。

问题建模-线性回归

将上述房子信息抽象成 n 个变量（维度）的向量 X，房价抽象为 Y，构成了一组数据集合：

\{X^{(i)}, Y^{(i)}\}, i = 1, 2, ..., m，共 m 个样本，其中 X^{(i)} \in \R^n, Y^{(i)} \in \R。

线性回归构建假设（或预测）函数 (hypothesis function)：

h_\theta(x) = \theta^TX = \sum\limits_{i=0}^{n}\theta_iX_i \\
其中参数 \theta \in \R^{n+1}, 为方便处理，这里 X 扩充一维，并假设 X_0 = 1

误差函数-最小二乘

现在要做的事情是像让述预测函数 h_\theta(x) 做到：当输入训练集中的一个样本 X^i 时，输出的预测值 h_\theta(X^{(i)}) 能接近训练集中的真实值 Y^{(i)}，这就是 误差 的概念。
训练的过程就是：通过不断地调整预测函数的参数 \theta，使得整个训练集的所有样本误差总和最小。因而这里要给定一个训练集误差总和的定量公式。最小二乘法假设总体误差函数为每个样本的误差平方和，也即为：

J(\theta) = \frac{1}{2}\sum\limits_{i=1}^m(h_\theta(X^{(i)}) - Y^{(i)})^2

所以问题转化为，通过优化参数 \theta 让误差函数 J(\theta) 的取值最小。

梯度下降法

求一个函数的最小值，可以通过梯度下降法(Gradient Descend)，给定一个步长，让参数从梯度最大的反方向更新，直到一定精度（误差变化很小或不再变化）为止：

\begin{aligned}
\theta_i &= \theta_i - \alpha\frac{\partial J(\theta)}{\partial \theta_i} \\
        &= \theta_i - \alpha\sum\limits_{j=1}^m(h_\theta(X^{(j)}) - Y^{(j)})X_i^{(j)}
\end{aligned} \\
其中 i = 0, 1, 2, ..., n；\alpha 为步长；\vec{\theta} 初始值从零向量 \vec{0} 开始迭代。

这里每一步迭代的复杂度为\theta 维度 * 样本数 m，如果样本数m很大（比如 > 10^5）时，计算量会很高。因而可引入随机梯度下降法 SGD (Stochastic Gradient Descent)

随机梯度下降法

SGD 对参数 \theta 的每一步迭代只用部分样本，算法伪代码如下：

Repeat {
        for j = 1, ..., m {
            只用第 j 个样本更新参数
        }
}

也即为：
\theta_i = \theta_i - \alpha(h_\theta(X^{(j)}) - Y^{(j)})X_i^{(j)}
由于样本的随机性，SGD 可能会不收敛，当样本足够大并随机时，总体趋于收敛。