Duxy's

a digged hole

机器学习方法整理-线性回归

看机器学习的视频头都大了,回头还不太清楚怎么用。在师兄的启发下,说可以整理一下思路,给人多讲一讲,就能够基本理清了。于是有了这些文章,至少给自己讲懂吧,不是么?
根据不同的机器学习类型,拟一拟我对课堂中介绍的一些概念的看法,看看是否能够屏蔽掉复杂的公式推导,使思路变得简单?
ok, 本章是线性回归。

线性回归

线性回归的前提是:将样本空间量化为线性向量,第\(i\)个样本的参数为\(\vec{x}^{(i)}\),其结果为\(y^{(i)}\)。

线性回归的目标是:找到一个回归函数 \(h_{\theta}(\vec{x}) = \theta^Tx\),能够尽可能的逼近给定的样本点。
在上述公式中,由于函数取决于一个向量\(\theta\),因此被称作是线性回归,而通常使用下列公式作为逼近程度的判断标准:
\(J(\theta) = \frac{1}{2}\sum_{i=1}^{m}{(h_{\theta}(\vec{x}^{(i)}) - y^{(i)})^2}\)
当公式取得最小值时,该回归函数就可以被认为是吸收了样本信息。
该公式的定义,利用平方使距离成为了非负数,前面添加\(\frac{1}{2}\)不影响求最小值的结果,但可以使求导的过程和结果更加漂亮。

梯度下降法

求解\(J(\theta)\)的方法很多,最为经典的就是梯度下降法(gradient descent),现在有大量的研究人员使用该方法。方法思想非常简单:向着切面的负方向跨一小步,就离极值点更近了一步,不断的跨出这一小步,最终就能到达极值点附近。

该方法仅能用于求解局部最优问题,但通常情况下,回归问题都是凸函数,所以利用梯度下降能够获得最优解。

梯度下降法迭代过程中的每一小步,可看作向几个正交方向上分别跨出一小步,被定义为:

\(\theta_j := \theta_j - \alpha\frac{\partial}{\partial\theta_j}J(\theta) \)。

其中\(\alpha\)为步幅大小。如果设置\(\alpha\)较大,则会更快的收敛,但是最终精度不高,而如果\(\alpha\)较小,收敛会比较慢。因此,师兄说:可在每跨一步时,令\(\alpha = \frac{\partial}{\partial\alpha}\theta_i(\alpha)\)????,可令\(\alpha\)取得更合适的值。???

对于上述公式,经过求偏导化简,可得出结果:
\(\theta_j := \theta_j - \alpha(h_{\theta}(x^{(i)}) - y^{(i)}) x^{(i)}_j \)

对多组样本数据来说,有两种迭代方案,其不同体现在计算\(\theta_j\)的方法:
1. 遍历所有的\(\vec{x}^{(i)}\)后,才能得到新的\(\vec{\theta}\),进行下一次迭代;
1. 每计算一个\(\vec{x}^{(i)}\),就计算出新的\(\vec{\theta}\),进行下一次迭代,下一次迭代将选择一个新的样本。

最小二乘法(least square)

最小二乘法利用了矩阵的一些运算和性质进行推导。把全部样本的参数定义为m行n+1列的矩阵\(X\):
\[
\left[\begin{matrix}
{\vec{x}^{(1)}}^T \\
{\vec{x}^{(2)}}^T \\
… \\
{\vec{x}^{(m)}}^T\\
\end{matrix}\right]
\]
把样本的参数集定义为m行1列的向量\(\vec{Y}\):
\[
\left[\begin{matrix}
{y^{(1)}} \\
{y^{(2)}} \\
…\\
{y^{(m)}} \\
\end{matrix}\right]
\]

由于回归函数是:\(h_{\theta}(x) = \theta^Tx = x^T\theta \),因此得到新的向量:
\[
X\theta - \vec{Y} =
\left[\begin{matrix}
{\vec{x^{(1)}}^T\theta} \\
{\vec{x^{(2)}}^T\theta} \\
…\\
{\vec{x^{(m)}}^T\theta} \\
\end{matrix}\right] -
\left[\begin{matrix}
{y^{(1)}} \\
{y^{(2)}} \\
…\\
{y^{(m)}} \\
\end{matrix}\right] \\ =
\left[\begin{matrix}
{h_{\theta}(x^{(1)}) - y^{(1)}} \\
{h_{\theta}(x^{(2)}) - y^{(2)}} \\
…\\
{h_{\theta}(x^{(m)}) - y^{(m)}} \\
\end{matrix}\right]
\]

因而问题变成了:如何使新向量的模\(|\vec{X}\theta - \vec{Y}| \)最小。
该问题等价于如何使\(\frac{1}{2} (\vec{X}\theta - \vec{Y})^T(\vec{X}\theta - \vec{Y}) = J(\theta) \)最小,因此与梯充下降法解决了相同的问题。

但是,上述推导中给出的\(J(\theta)\)公式给了我们一个求导的可能性,即当\(\nabla_{\theta}J(\theta) = 0\)时,所取的\(\theta\)为最优解。利用高大上的矩阵的导数(Matrix Derivatives): \(\nabla_A f(A) \),不明觉厉的矩阵对角线\(tr\)运算,以及它们结合的一堆牛B性质。得到了一个式子:
\(\theta = {(X^TX)}^{-1}X^T\vec{Y} \)
利用这个式子可以直接解出\(\theta\)。当然,求解式子其实并不一定简单,这也是为什么还有不少人继续用梯度下降法的原因。

把推导用到的式子摘录一下吧:
\[
\begin{aligned}
\nabla_AtrAB = B^T\\
\nabla_{A^T}f(A) = (\nabla_Af(A))^T\\
\nabla_AtrABA^TC = CAB + C^TAB^T\\
\nabla_A|A| = |A|(A^{-1})^T\\
\nabla_{A^T}trABA^TC = B^TA^TC^T + BA^TC
\end{aligned}
\]

概率模型分析

概率模型分析其实就是为了给\(J(\theta)\)找到一个更符合思考习惯的理论依据。

为每个分析加上一个误差项\(\epsilon\),可得到线性回归的表达式:\(y^{(i)} = \theta^Tx^{(i)} + \epsilon^{(i)}\)。
而回归分析的目标是:使\(\sum_{i=1}^{m}{\epsilon^{(i)}}\)最小。

而误差的概率分布在多变元情况下,通常服从高斯分布(Gaussian Distribution),所以假定\(\epsilon^{(i)} ~ N(0,\delta^2\),就得到了公式:
\(p(y^{(i)}|x^{(i)};\theta) = \frac{1}{\sqrt{2\pi}\delta}exp(-\frac{{(\epsilon^{(i)})}^2}{2\delta^2}) \)

通常情况下,老师都会特别强调,这里的\(\theta\)不是随机变量,而是求随机函数的一个可变参数,所以必须用分号不能用逗号。

由此引出最大似然估计(Maximun likelihood)
\(L(\theta) = \prod_{i=1}^{m}{p(y^{(i)}|x^{(i)};\theta)}\)

由前面的公式可以看出,最大似然估计中,包含一个指数函数\(exp\),并且是连乘积。而只要是使用递增函数处理\(L(\theta)\)得到的函数最大值对应的\(\theta\)值,都完全相同,所以一般对最大似然估计取对数,方便求到极值。
所以得到下面的式子
\(l(\theta) = m log\frac{1}{\sqrt{2\pi}\delta} - \frac{1}{\delta^2}*\frac{1}{2}\sum_{i=1}^{m}{{(y^{(i)} - \theta^Tx^{(i)})}^2} \)
式子中可变元就x与y,所以等价于求\(\frac{1}{2}\sum_{i=1}^{m}{(h_{\theta}(\vec{x}^{(i)}) - y^{(i)})^2} = J(\theta) \)的最大值。且与高斯分布中的\(\delta\)取值无关。