回归（Regression）模型是指机器学习方法学到的函数的输出是连续实数值，回归模型可以用于预测或者分类，这篇博客中主要整理用于预测的线性回归模型和多项式回归模型。

线性回归

按照机器学习建模的三个步骤，首先需要确定选用的模型，这里就是线性回归（Linear regression）模型，然后将其形式化表达：

h (x) = w_{1} x_{1} + w_{2} x_{2} + \dots + w_{n} x_{n} + b

其中， $x_{1}, x_{2}, \dots, x_{n}$ 是样本数据的n维属性描述，每一组 $w$ 和 $b$ 能确定一个不一样的 $h (x)$ ， $w$ 和 $b$ 的所有取值组合就构成了可选函数集合，我们的任务就是要从这个函数集合中选出“最好”的那个函数。
对于训练数据集D描述如下： $D = {(x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \dots, (x^{(m)}, y^{(m)})}$ ，其中 $x^{(i)} = (x_{1}^{(i)}; x_{2}^{(i)}; \dots; x_{n}^{(i)})$ 是样本的n维特征向量表示， $y^{(i)} \in R$ 是样本标记。线性回归的目标是学得一个线性函数以尽可能准确的预测实值输出标记。
因此我们需要确定一个衡量标准用以度量一个函数的好坏，也就是选择合适的损失函数（Loss Function）。根据线性回归的目标，我们只需要度量 $h (x)$ 与 $y$ 之间的差距，均方误差（Mean Square Error，MSE）是回归任务中最常用的损失函数。

L (h) = \sum_{i = 1}^{m} (y^{(i)} - h (x^{(i)}))^{2}

因为 $h$ 是关于 $w, b$ 的函数，所以上式也可以写成

L (w, b) = \sum_{i = 1}^{m} (y^{(i)} - (w^{T} x^{(i)} + b))^{2}

能够让 $L$ 最小的 $w, b$ 所确定的函数就是我们要找的最好的那个函数，记为 $w^{*}, b^{*}$

\begin{array}{rcl} w^{*}, b^{*} & = & a r g min_{w, b} L (w, b) \\ = & a r g min_{w, b} \sum_{i = 1}^{m} (y^{(i)} - (w^{T} x^{(i)} + b))^{2} \end{array}

现在需要选择一种优化算法从众多 $w, b$ 中找出 $w^{*}, b^{*}$ ，常用的方法有梯度下降算法（Gradient Descent）和最小二乘法（Least Square Method，LSM）。

梯度下降法

对多元函数的每一个变量分别求 $\partial$ 偏导数，并将结果写成向量形式，就是梯度。比如函数 $f (x, y)$ ，分别对 $x, y$ 求偏导数， $(\partial f / \partial x, \partial f / \partial y)^{T}$ 就是梯度。从几何意义上讲，梯度是函数在该点变化最快的方向，因此沿着梯度的反方向，会更加容易找到函数的最小值点。下图是梯度下降的一个直观解释

比如我们在一座大山的某个位置想要到达山脚下，由于我们不知道怎么下山，于是决定走一步算一步，每次走到一个位置后，求解当前位置的梯度，沿着梯度的负方向，也就是当前最陡峭的方向向下走，直到走到梯度为零的位置。当然这样走下去，有可能不能走到山脚，而是到了某一个局部山峰低处。
因此梯度下降不一定能够找到全局最优解，有可能是一个局部最优解，如果损失函数是凸函数，梯度下降算法就一定能找到全局最优解。
梯度下降算法步骤如下：

随机选取一个初始值 $w^{0}$
计算 $\frac{d L}{d w} |_{w = w^{0}}$ ， $w^{1} = w^{0} - η \frac{d L}{d w} |_{w = w^{0}}$ ，其中 $η$ 是学习速率，决定了每一次调整的步长

\frac{\partial L}{\partial w} = \sum_{i = 1}^{m} 2 (y^{(i)} - (b + w^{T} x^{(i)})) (- x^{(i)}) \frac{\partial L}{\partial b} = \sum_{i = 1}^{m} 2 (y^{(i)} - (b + w^{T} x^{(i)})) (- 1)

迭代第二步多次直至梯度为零，或者损失达到允许范围，或者达到迭代次数。

最小二乘法

同样可以采用最小二乘法来对 $w, b$ 进行估计，最小二乘法直接求解得到解析解。为了方便讨论，我们把 $w, b$ 合并组成一个向量 $\hat{w} = (w; b)$ ，同时给每一个样本增加一个恒定属性值1。同时，把数据集D表示成一个 $m * (n + 1)$ 大小的矩阵 $X$

X = (\begin{matrix} x_{1}^{(1)} & x_{2}^{(1)} & \dots & x_{n}^{(1)} & 1 \\ x_{1}^{(2)} & x_{2}^{(2)} & \dots & x_{n}^{(2)} & 1 \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ x_{1}^{(m)} & x_{2}^{(m)} & \dots & x_{n}^{(m)} & 1 \end{matrix})

再把标记也写成向量形式 $y = (y_{1}; y_{2}; \dots; y_{m})$ ，则类似的有

h = X \hat{w}

损失函数

L = \frac{1}{2} (y - X \hat{w})^{T} (y - X \hat{w})

对 $\hat{w}$ 求导得到

\frac{\partial L}{\partial \hat{w}} = X^{T} (y - X \hat{w})

令上式等于零，可得 $\hat{w}$ 最优解的闭式解

X^{T} (y - X \hat{w}) = 0 \Rightarrow X^{T} y - X^{T} X \hat{w} = 0 \Rightarrow X^{T} X \hat{w} = X^{T} y \hat{w} = (X^{T} X)^{- 1} X^{T} y

其中， $(X^{T} X)^{- 1}$ 是 $(X^{T} X)$ 的逆矩阵，可能存在 $(X^{T} X)$ 不是满秩矩阵，常见的作法是引入正则化（regularization）项。（正则化将专门放在一篇博客记录）

梯度下降和最小二乘法优缺点

1、梯度下降算法适用于所有的最优化问题，但是最小二乘法只适用于线性问题，当回归模型不是线性模型时，需要通过一些技巧转化为线性才能使用最小二乘法。
2、最小二乘法需要求解 $(X^{T} X)^{- 1}$ ，可能存在矩阵 $(X^{T} X)$ 没有逆矩阵的情况，这时需要加入正则化项，或者删除一些冗余特征，让 $(X^{T} X)$ 的行列式不为0，然后继续使用最小二乘法。另外，当样本量很大时，求解逆矩阵将是一个非常耗时的过程，使用梯度下降算法将比较有优势。
3、当样本数据不是很大，且存在解析解时，最小二乘法比起梯度下降算法计算速度更快。

多项式回归

有些样本数据用线性回归拟合时可能不是特别恰当，这时候可以尝试采用多项式回归，如下图所示，是一个房屋价格与房屋面积的样本数据集，可以明显发现所有数据点并不分布在某一条直线附近，这时候可以考虑尝试二次函数或者三次函数

对于多项式回归，可以将 $x^{2}, x^{3}$ 也看作是一个新的属性，这时多项式回归就和线性回归一样了，因此多项式回归的训练方法依旧和线性回归一样。
需要注意的是，能够选择简单的线性模型时就不要选择相对复杂的多项式模型。

参考文献

李宏毅主页

机器学习系列（二）——回归模型