线性回归

一、算法原理

给定数据集 $D=\{(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),\dots,(\boldsymbol{x}_m,y_m)\}$，其中 $\boldsymbol{x}_i=(x_{i1};x_{i2};\dots;x_{id}),y_{i}\in\mathbb{R}$。”线性回归“（linear regression）试图学得一个线性模型以尽可能准确地预测实值输出标记。

下面以一个房价预测的例子进行说明，为了方便讨论，此时忽略关于属性的下标。我们先考虑一种最简单的情形，输入属性的数目只有一个，如房屋的面积 $x_1$，其为连续数值，此时的回归方程为

$f\left(\boldsymbol{x}_{i}\right)=w_{1}x_{1}+b$

下面再增加一个有序的多值离散特征：房屋与市中心的距离，取值为“较远”、“始终”、“较近”，可转化为 $\{1.0,0.5,0.0\}$，此时回归方程为

$f\left(\boldsymbol{x}_{i}\right)=w_{1}x_{1}+w_{2}x_{2}+b$

若属性值间不存在序关系，假定有 $k$ 个属性值，则通常转化为 $k$ 维向量，如房屋的颜色，取值为 “红色”、“灰色”、“白色”，可转化为 $(1,0,0),(0,1,0),(0,0,1)$，此时回归方程为

$f\left(\boldsymbol{x}_{i}\right)=w_{1}x_{1}+w_{2}x_{2}+w_{3}x_{3}+w_{4}x_{4}+w_{5}x_{5}+b$

综上，线性回归试图学得

$f\left(\boldsymbol{x}_{i}\right)=\boldsymbol{w}^{\rm{T}}\boldsymbol{x}_{i}+b, \text { 使得 } f\left(\boldsymbol{x}_{i}\right) \simeq y_{i}.$

以上就是线性回归的算法原理。

注意

若将无序属性连续化，则会不恰当地引入序关系，对后续处理，如距离计算等造成误导。

二、参数估计方法

2.1 最小二乘估计

基于均方误差最小化来进行模型求解的方法称为“最小二乘法”，均方误差的计算公式如下所示：

$\begin{aligned} E_{(w, b)} &=\sum_{i=1}^{m}\left(y_{i}-f\left(x_{i}\right)\right)^{2} \\ &=\sum_{i=1}^{m}\left(y_{i}-\left(w x_{i}+b\right)\right)^{2} \\ &=\sum_{i=1}^{m}\left(y_{i}-w x_{i}-b\right)^{2} \\ \end{aligned}$

要使均方误差最小化，则 $w$ 和 $b$ 的解的计算公式为：

$\begin{aligned} \left(w^{*}, b^{*}\right) &=\underset{(w, b)}{\arg \min } \sum_{i=1}^{m}\left(f\left(x_{i}\right)-y_{i}\right)^{2} \\ &=\underset{(w, b)}{\arg \min } \sum_{i=1}^{m}\left(y_{i}-w x_{i}-b\right)^{2} \end{aligned}$

2.2 极大似然估计

对于线性回归来说，也可以假设其为以下模型

$y=wx+b+\epsilon$

其中 $\epsilon$ 为不受控制的随机误差，通常假设其服从均值为 0 的正态分布 $\epsilon \sim N\left(0, \sigma^{2}\right)$（高斯提出的，也可以用中心极限定理解释），所以 $\epsilon$ 的概率密度函数为

$p(\epsilon)=\frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\epsilon^{2}}{2 \sigma^{2}}\right)$

若将 $\epsilon$ 用 $y-(wx+b)$ 等价替换可得

$p(y)=\frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{(y-(w x+b))^{2}}{2 \sigma^{2}}\right)$

上式显然可以看作 $y \sim N\left(w x+b, \sigma^{2}\right)$，下面便可用极大似然估计来估计 $w$ 和 $b$ 的值，似然函数为

$L(w, b)=\prod_{i=1}^{m} p\left(y_{i}\right)=\prod_{i=1}^{m} \frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\left(y_{i}-\left(w x_{i}+b\right)\right)^{2}}{2 \sigma^{2}}\right)$

为了方便求解，将其转换为对数似然函数为

$\begin{aligned} \ln L(w, b) &=\sum_{i=1}^{m} \ln \frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\left(y_{i}-w x_{i}-b\right)^{2}}{2 \sigma^{2}}\right) \\ &=\sum_{i=1}^{m} \ln \frac{1}{\sqrt{2 \pi} \sigma}+\sum_{i=1}^{m} \ln \exp \left(-\frac{\left(y_{i}-w x_{i}-b\right)^{2}}{2 \sigma^{2}}\right) \\ &=m \ln \frac{1}{\sqrt{2 \pi} \sigma}-\frac{1}{2 \sigma^{2}} \sum_{i=1}^{m}\left(y_{i}-w x_{i}-b\right)^{2} \end{aligned}$

其中 $m,\sigma$ 均为常数，所以最大化 $\ln L(w, b)$ 等价于最小化 $\sum_{i=1}^{m}\left(y_{i}-w x_{i}-b\right)^{2}$，即

$\left(w^{*}, b^{*}\right)=\underset{(w, b)}{\arg \max } \ln L(\boldsymbol{w}, b)=\underset{(w, b)}{\arg \min } \sum_{i=1}^{m}\left(y_{i}-w x_{i}-b\right)^{2}$

由此可知，极大似然估计与最小二乘估计的结果相同。

三、求解 w 和 b

$\left(w^{*}, b^{*}\right)=\underset{(w, b)}{\arg \min } \sum_{i=1}^{m}\left(y_{i}-w x_{i}-b\right)^{2}$

求解 $w$ 和 $b$ 其本质上是一个多元函数求最值（点）的问题，更具体点是凸函数求最值的问题，推导思路分为以下两个步骤：

1. 证明 $E_{(w, b)}=\sum_{i=1}^{m}\left(y_{i}-w x_{i}-b\right)^{2}$ 是关于 $w$ 和 $b$ 的凸函数；
2. 用凸函数求最值的思路求解出 $w$ 和 $b$。

3.1 凸集和凸函数

3.2 梯度

3.3 Hessian 矩阵

3.4 凸函数证明

3.5 求解 w 和 b