机器学习方法整理-线性回归 #
Date: 2015/6/12
看机器学习的视频头都大了，回头还不太清楚怎么用。在师兄的启发下，说可以整理一下思路，给人多讲一讲，就能够基本理清了。于是有了这些文章，至少给自己讲懂吧，不是么？
根据不同的机器学习类型，拟一拟我对课堂中介绍的一些概念的看法，看看是否能够屏蔽掉复杂的公式推导，使思路变得简单？
ok, 本章是线性回归。more线性回归
线性回归的前提是：将样本空间量化为线性向量，第$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$的方法：
- 遍历所有的$\vec{x}^{(i)}$后，才能得到新的$\vec{\theta}$，进行下一次迭代；
- 每计算一个$\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$取值无关。
Categories:
机器学习