线性回归

作者: c4b95022557e | 来源:发表于2018-11-21 15:41 被阅读0次

线性回归模型

概述

给定数据集 $D=\{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\cdots(x^{(m)},y^{(m)})\}，x^{(i)}\in\mathcal{X}\subseteq\mathbb{R}^m,y^{(i)}\in\mathcal{Y}\subseteq\mathbb{R},i=1,2,\cdots,m,$ 其中 $x^{(i)}=(x_1^{(i)},x_2^{(i)},\cdots,x_n^{(i)})^T,m$ 为样本的数量， $n$ 为特征的数量。

线性模型试图学得一个通过属性的线性组合来进行预测的函数，即
$f(x)=w_1x_1+w_2x_2+...+w_nx_n+b,$
其中 $w$ 为权重， $b$ 为截距，写成向量形式为
$f(x)=w^Tx+b$

为了简化公式，设 $x^{(i)}=(x_1^{(i)},x_2^{(i)},...x_n^{(i)},1)^T，w=(w_1,w_2,...,w_n,b)^T$ ，简化之后为
$f(x)=\sum_{i=0}^nw_ix_i=w^Tx$
我们的目标便是通过给定的数据集 $D$ 来学习参数 $w$ ，对于给定的样本 $x^{(i)}$ ，其预测值 $\hat{y}^{(i)}=w^Tx^{(i)}$ ，与真实值 $y^{(i)}$ 越接近越好。这里我们采用平方损失函数，则在训练集D上，模型的损失函数为
$L(w)=\sum_{i=1}^m(f(x^{(i)})-y^{(i)})^2 \\\quad\quad=\sum_{i=1}^m(w^Tx^{(i)}-y^{(i)})^2$
这样，我们的目标便变为损失函数最小化。为了之后求导方便，在损失函数前乘以 $1/2$ ，即：
$w^*=\mathop{\arg\min}_{w}\frac{1}{2}\sum_{i=1}^m(w^Tx^{(i)}-y^{(i)})^2$
为了求出使 $L(w)$ 最小的 $w$ 值，我们可以使用梯度下降法和正规方程两种方法。

梯度下降法

梯度下降的思想是：开始时随机选择一个参数的组合 $(w_0,w_1,w_2,...,w_n)$ ，计算损失函数，然后寻找下一个能让损失函数下降最多的参数组合，持续这么做直到一个局部最小值。通常选择不同的初始参数组合，可能会找到不同的局部最小值。

梯度下降算法公式为：

重复直到收敛{

$w_j:=w_j-\alpha\frac{\partial}{\partial w_j}L(w)$

}

要实现这个算法，关键在于求出损失函数关于 $w$ 的导数

$\begin{equation} \begin{split}\frac{\partial}{\partial w_j}L(w)&=\frac{\partial}{w_j}\frac{1}{2}\sum_{i=1}^m(w^Tx^{(i)}-y^{(i)})^2 \\&=\frac{\partial}{\partial w_j}\frac{1}{2}\sum_{i=1}^m(w_0x_0^{(i)}+w_1x_1^{(i)}+...+w_jx_j^{(i)}+...+w_nx_n^{(i)}-y^{(i)})^2 \\&=2·\frac{1}{2}\sum_{i=1}^m(w_0x_0^{(i)}+w_1x_1^{(i)}+...+w_nx_n^{(i)}-y^{(i)})·x_j^{(i)} \\&=\sum_{i=1}^m(w^Tx^{(i)}-y^{(i)})x_j^{(i)}\end{split} \end{equation}$

重复直到收敛{

$w_j:=w_j+\alpha\sum_{i=1}^m(y^{(i)}-w^Tx^{(i)})x_j^{(i)}$ (for every j)

}

正规方程

正规方程通过求解下面的方程来找出使损失函数最小的参数： $\frac{\partial}{\partial w}L(w)=0$

矩阵导数

假设函数 $f:R^{m×n}\to R$ ，从 $m*n$ 大小的矩阵映射到实数域，那么当矩阵为 $A$ 时导函数定义如下所示：
$\frac{\partial f(A)}{\partial A}=\begin{bmatrix}\frac{\partial f}{\partial A_{11}} & \cdots & \frac{\partial f}{\partial A_{1n}}\\\vdots &\ddots&\vdots\\\frac{\partial f}{\partial A_{m1}}&\cdots&\frac{\partial f}{\partial A_{mn}} \end{bmatrix}$
例如A= $\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22} \end{bmatrix}$ 是 $2*2$ 矩阵，给定函数 $f:R^{2×2} \to R$ 为：
$f(A)=\frac{3}{2}A_{11}+5A_{12}^2+A_{21}A_{22}$
那么 $\frac{\partial f(A)}{\partial A}=\begin{bmatrix}\frac{3}{2}&10A_{12}\\A_{22}&A_{21} \end{bmatrix}$ ，我们还要引入矩阵的迹(trace)，简写为 $tr$ 。对于一个给定的 $n*n$ 的方阵 $A$ ，它的迹定义为对角线元素之和：
$tr\ A=\sum_{i=1}^nA_{ii}$
如果有两矩阵 $A$ 和 $B$ ，满足 $AB$ 为方阵，则迹运算有以下性质：
$trAB=trBA\\trABC=trCAB=trBCA\\trA=trA^T\\tr(A+B)=trA+trB\\tr\ aA=atrA$
接下来提出一些矩阵导数：
$\frac{\partial(trAB)}{\partial A}=B^T\\\frac{\partial f(A)}{\partial A^T}=(\frac{\partial f(A)}{\partial A})^T\\\frac{\partial(trABA^TC)}{\partial A}=CAB+C^TAB^T\\\frac{\partial |A|}{\partial A}=|A|(A^{-1})^T$

下面把损失函数 $L(w)$ 用向量的形式表述。令
$X=\begin{bmatrix}(x^{(1)})^T\\(x^{(2)})^T\\\vdots\\(x^{(m)})^T\end{bmatrix}=\begin{bmatrix}x_1^{(1)}&x_2^{(1)}&\cdots& x_n^{(1)}&1\\x_1^{(2)}&x_2^{(2)}&\cdots&x_n^{(2)}&1\\\vdots&\vdots&\ddots&\vdots&1\\x_1^{(m)}&x_2^{(m)}&\cdots&x_n^{(m)}&1\end{bmatrix}\\y=\begin{bmatrix}y^{(1)}\\y^{(2)}\\\vdots\\y^{(m)}\end{bmatrix},w=\begin{bmatrix}w_1\\w_2\\\vdots\\w_n\\b\end{bmatrix}$
则有
$Xw-y=\begin{bmatrix}f(x^{(1)})-y^{(1)}\\f(x^{(2)})-y^{(2)}\\\vdots\\f(x^{(m)})-y^{(m)}\end{bmatrix}\\\frac{1}{2}(Xw-y)^T(Xw-y)=\frac{1}{2}\sum_{i=1}^m(f(x^{(i)})-y^{(i)})^2=L(w)$

$\begin{equation} \begin{split} \frac{\partial L(w)}{\partial w}&=\frac{\partial }{\partial w}\frac{1}{2}(Xw-y)^T(Xw-y)\\ &=\frac{1}{2}\frac{\partial}{\partial w}(w^TX^TXw-w^TX^Ty-y^TXw+y^Ty)\\ &=\frac{1}{2}\frac{\partial}{\partial w}tr(w^TX^TXw-w^TX^Ty-y^TXw+y^Ty)\\ &=\frac{1}{2}\frac{\partial}{\partial w}(tr(w^TX^TXw)-2tr(y^TXw))\\ &=\frac{1}{2}(X^TXw+X^TXw-2X^Ty)\\ &=X^TXw-X^Ty \end{split} \end{equation}$