[斯坦福大学公开课：机器学习（一）] 监督学习应用.梯度下降
最近在看斯坦福大学的机器学习公开课，发现看完总是很容易忘记知识点。于是，准备将上课的讲义做一份整理，一来加深学习记忆，二来自己也可以经常翻阅。也希望喜欢机器学习的朋友可以共同交流~
监督式学习(Supervised learning)
先来看一个例子，我们有一个关于居住面积和房价的数据集。
我们可以在平面直角坐标系中画出这些数据：
那么，给定这些数据，我们是否可以使用一个函数来描述居住面积和房价之间的关系，从而来预测房价呢？
在开始之前，我们首先建立一套符合，我们用x(i)来表示输入变量（在刚才的例子中就是居住面积），也叫做输入特征。y(i)叫做目标变量（刚才的例子中就是需要预测的房价）。我们将一对(x(i), y(i))称为一个训练样本，并且将m个训练样本{(x(i), y(i));i = 1, ...,m}称为训练集。同时，X代表输入空间，Y代表输出空间。在这个例子中，X=Y=R。
为了更加正式地描述什么是监督式学习，我们的目标是给定一个训练集，来学习一个函数h：X->Y，此时我们认为h(x)是一个好的预测函数。因为历史原因，我们也常常将函数h称为hypothesis。这个过程应该是像这样的：
当我们需要预测的目标变量是连续的，就像刚才的房价例子一样，我们将此类问题称为回归问题。当y仅仅代表几个离散的值，我们将它成为分类问题。
线性回归(Linear Regression)
为了让之前房屋的例子更加有趣，我们在之前的基础上又增加了一个特征，除了知道房屋的居住面积外，我们还知道房屋的卧室数量：
在这里，输入变量x是一个二维的向量，比如说x(i)1代表居住面积，其中下标表示x(i)的第几个特征。作为一个监督式学习，我们需要决定如何选择一个hypotheses。在这里，我们先粗略得认为y是一个关于x的线性函数：
公式中，θi称之为参数(parameters)，也叫做权重。我们令x0 = 1(intercept term)。这样，我们得到如下公式：
上式中，n表示输入变量的个数。现在给定一个训练集，我们如何来学习参数θ？一个看起来比较合理的方法是使得h(x)接近于y，至少在我们给定的训练集上是这样的。
我们首先定义一个度量来定义，对于每一个θ，h(x(i))与y(i)的接近程度。我们将它称为代价函数(cost function)：
最小二乘法(LMS algorithm)
我们希望选择一个θ使得J(θ)能取到最小值。为了达到这个目的，我们将使用一个搜索算法，首先为θ取一个初始值，然后不断地更新θ来使得J(θ)变得更小，直到J(θ)收敛到一个期望的值。在这里我们使用梯度下降算法(gradient descent)，一开始给定一个初始的θ，然后不断地执行如下更新：
每次迭代的过程中，对于θj, j= 0,...n，都需要更新。上式中，α称为学习率(learning rate)。算法每次沿着最陡峭的方向不断地减少J。我们来对上式右边进行求导，并且先假设只有一个训练样本(x, y)，这样我们得到：
对于单个训练样本，只需要做如下更新：
刚刚我们得到了在只有一个训练样本情况下的最小二乘法。在这里，有两种方法可以将它修改为应用于多个样本。第一种方法按照如下的方式更新：
这个方法在每次迭代的过程中使用了整个训练集，我们将它叫做批量梯度下降。注意，梯度下降法可能收到局部最优解的影响，而在我们的线性回归中，J是一个凸二次函数，只存在一个全局的最优解，因此在这个例子中，梯度下降法总能够收敛。但要注意学习率不能过大，否则将出现左右摇摆的情况。我们用一副图来形象得描绘梯度下降的过程：
上图中的椭圆描绘了二次函数的轮廓，一开始位于(48, 30)，然后沿着等高线下降最快的地方移动，直到算法收敛得到一个全局的最小值，最终根据得到的θ，我们可以在图中描绘hθ(x)：
除了上述提到的梯度下降以外，还有一种叫做随机梯度下降(stochastic gradient descent)，同样它也能工作得很好：
在这个算法中，对于每一次迭代，我们只使用了一个训练样本，而批量梯度下降需要使用整个训练集来计算误差。当m非常大时，随机梯度下降运行效率更高。注意：随机梯度下降可能无法收敛到最小值，但在实际实际使用过程中，最终都会得到一个最小的合理近似值。因此当训练集非常大时，随机梯度下降往往比批量梯度下降优先考虑。
The normal equations
梯度下降给出了一种可以最小化代价函数的方法。下面我们来讨论第二种方法。该方法不需要做任何的迭代运算，在开始之前，我们首先引入一些关于矩阵运算的符号。
对于一个函数f : Rmxn -> R，即从一个m乘n的矩阵映射到一个实数。我们定义f关于A的导数：
举个例子，A是一个2x2的矩阵，f : R2x2 -> R：
Aij代表矩阵A的(i, j)个元素，我们用A对f求导，得到：
同时，我们也引入了“迹”，简写为“tr”。对于一个nxn的矩阵A，A的“迹”定义为它对角线元素的和：
如果a是一个实数，那么tr a = a。迹操作有一个特性，给定两个矩阵A和B，那么trAB = trBA。以这个推论，我们得到：
介绍完上述的内容后，我们使用矩阵来定义最小二乘法。给定一个训练集，我们可以定义一个mxn的矩阵X：
同样，y代表一个m维的向量，包含所有的目标变量：
因为h�θ���(x(i)) = (x(i))Tθ，我们可以很容易得到：
然后我们使用公式，对于向量z，zTz = ∑iz2i得到：
最后，根据公式：
我们可以得到最终的结果：
为了最小化J，我们将导数设为0，得到normal equations:：
将θ移到最左端，得到：
概率解释
比较会思考的朋友可能会想，关于代价函数J为什么必须要这么写？在这一节，我们将给出最小二乘法的概率解释。
我们首先假设目标变量和输入变量的关系如下：
上式中， ε(i)是一个误差项。比如说，我们在预测房价的时候，只考虑了面积和卧室数量，可能还与地理位置有关，但是我们没有为它进行建模。或者它也可以是一个随机的噪声。我们假设ε(i)独立同分布，且服从高斯分布： “ε(i) ~ N(0, σ2)”。ε(i)的概率密度函数就为：
这意味着：
注意，上式中θ并不是一个随机变量。我们同样可以写出y(i)的概率分布：y(i) | xx(i);θ ~ N(θTx(i), σ2)。当把它看作是一个关于θ的函数，我们将它称为似然函数：
因为ε(i)是独立同分布的，因此，对于m个训练样本：
根据最大似然精神，我们需要选择一个θ来使得目标变量相对于当前数据的概率是最大的。为了让推导过程更简单，我们使用log似然函数：
因此，最大化L(θ)就相当于最小化：
也就是我们之前使用的代价函数J(θ)。因此，我们可以得出结论：当数据处于前面假设的概率分布前提下，使用最小二乘法解决回归问题就相当于找出最大似然的解。
