线性回归

Posted on | In

回归问题与分类问题

回归问题与分类问题都是典型的监督学习。不同的是，分类的问题的输出是一个离散变量，而回归问题的输出则是一个连续变量。
回归问题是通过对训练样本的学习，得到样本特征到样本标签之间的映射。

基本线性回归

对于线性回归问题，我们可以从训练数据中学习到线性回归方程：
\begin{equation}
y = b + \sum_{i = 1}^{n} w_i \cdot x_i
\tag{1}
\end{equation}
其中，$b$为偏置，$w_i$为回归系数。为将(1)式的两个加和项统一，我们令$x_0=b$，则：
\begin{equation}
y = \sum_{i = 0}^{n}w_ix_i
\tag{2}
\end{equation}
在线性回归问题中，目标是要解出$w_i$，以最终求出线性回归方程。为评价预测值（prediction）与标签（label）之间的接近程度，我们采用绝对损失（absolute loss）和平方损失（squared loss）来度量这种近似性。
绝对损失函数为：
\begin{equation}
l = \left| y - \hat{y} \right|
\tag{3}
\end{equation}
其中，$\hat{y}$为预测值，且$\hat{y} = \sum_{i = 0}^{n}w_i x_i$。
平方损失为：
\begin{equation}
l = (y - \hat{y})^2
\tag{4}
\end{equation}

由于平方损失处处可导，通常使用平方误差作为线性回归模型的损失函数。假设有$m$个训练样本，每个样本有$n$个特征，则平方损失可进一步表示为：
\begin{equation}
l = \frac{1}{2}\sum_{i = 1}^{m} \left( y^{(i)} - \sum_{j = 0}^{n}w_jx_j^{(i)} \right)^2
\tag{5}
\end{equation}

于是，线性回归则可归结为求（5）式的最小值问题。

线性回归的最小二乘解法

我们首先将预测函数矩阵化，则：
\begin{equation}
Y = XW \quad X\in\mathbb{R}^{m \times n}, Y\in\mathbb{R}^{n \times 1}, W\in\mathbb{R}^{m\times 1}
\tag{6}
\end{equation}

其中$m$表示数据集有$m$个样本，$n$表示每个样本的特征数。
平方损失函数矩阵你化：
\begin{equation}
\left( Y - XW \right)^T\left( Y - XW \right)
\tag{7}
\end{equation}
此时对$W$进行求导，则：
\begin{equation}
\begin{aligned}
& \frac{d}{dW} \left( Y - XW \right)^T\left( Y - XW \right) \\
&= \frac{d}{dW} \left( Y^T - W^TX^T \right) \left( Y - XW \right) \\
&= -X^T(Y - XW) + (Y^T - W^TX^T)(-X) \\
&= -X^TY + X^TY + X^T(XW - Y) \\
&= X^T(XW - Y)
\end{aligned}
\tag{8}
\end{equation}
令（8）式等于$0$，则：
\begin{equation}
\begin{aligned}
& X^T(XW - Y) = 0 \\
&\Rightarrow X^TXW = X^TY \\
&\Rightarrow \hat{W} = (X^TX)^{-1}X^TY
\end{aligned}
\tag{9}
\end{equation}

牛顿法

牛顿法也是机器学习中常用的一种优化算法。牛顿法的基本思想是利用迭代点$x_k$处的一阶导数和二阶导数对目标函数进行二次函数近似，然后把二次函数的极小点作为新的迭代点，并不断重复这一过程，直至求得满足精度的近似极小值。
牛顿法下降的速度比梯度下降的快，而且能高度逼近最优值。牛顿法分为基本牛顿法和全局牛顿法。

基本牛顿法的原理

基本牛顿法是基于导数的算法，它每一步的迭代方向都是沿着当前点函数值的下降方向。对于一维情形，对于目标函数$f(x)$，我们将其用泰勒展开式展开的2阶，则：
\begin{equation}
f(x) = f(x_k) + f^\prime(x_k)(x - x_k) + \frac{1}{2}f^{\prime\prime}(x_k)(x - x_k)^2
\tag{10}
\end{equation}
在对（10）式求一阶导并令其等于0：
\begin{equation}
f\prime(x_k) + f^{\prime\prime}(x_k)(x - x_k) = 0
\tag{11}
\end{equation}
则可得到：
\begin{equation}
x = x_k - \frac{f^\prime(x_k)}{f^{\prime\prime}(x_k)}
\tag{12}
\end{equation}
于是，便得到了牛顿法的更新公式。

基本牛顿法的流程

  • 1 给定终止误差值$0\le\varepsilon\ll1$，初始点$x_0 \in \mathbb{R}^n$，令$k=0$；
  • 2 计算$g_k = \nabla f(x_k)$，若$\left|\left| g_k \right|\right|$，输出$x^* \approx x_k$；
  • 3 计算$G_k = \nabla^2 f(x_k)$，并求解线性方程组$G_kd = -g_k$得解$d_k$；
  • 4 令$x_{k+1} = x_k + d_k, k = k+1$，并转2。

全局牛顿法

牛顿法的优点是收敛速度快，具有局部二阶收敛性。然而，基本牛顿法初始点需要足够靠近极小点，否则，可能导致算法不收敛，此时引入全局牛顿法。

  • 1 给定终止误差值$0\le\varepsilon\ll1, \delta\in(0, 1), \sigma\in(0, 0.5)$，初始点$x_0 \in \mathbb{R}^n$，令$k=0$;
  • 2 计算$g_k = \nabla f(x_k)$，若$\left|\left| g_k \right|\right|$，输出$x^* \approx x_k$；
  • 3 计算$G_k = \nabla^2 f(x_k)$，并求解线性方程组$G_kd = -g_k$得解$d_k$；
  • 4 设$m_k$是不满足下列不等式的最小非负整数$m$：
    \begin{equation}
    f(x_k + \delta^m d_k) \le f(x_k) + \sigma \delta^m g_k^Td_k
    \tag{13}
    \end{equation}
  • 5 令$\alpha_k = \delta^m, x_{k+1} = x_k + \alpha_k d_k, k = k + 1$, 并转2。

Armijo搜索

全局牛顿法是基于Armijo的搜索，满足Armijo准则：
给定$\beta\in(0,2), \sigma\in(0, 0.5)$，令步长因子$\alpha_k = \beta^{m_k}$，其中$m_k$是满足下列不等式的最小非负整数：
\begin{equation}
f(x_k + \delta^md_k) \le f(x_k) + \sigma\delta^mg_k^Td_k
\tag{14}
\end{equation}