前言

本机器学习笔记是跟着原斯坦福大学吴恩达老师cs229课程学习后做的课后笔记。每次课程都会涉及到很多数学知识，我在记录课程核心内容的同时，会把数学基础知识在其它博文中单独记下，并在《机器学习笔记》系列博文中用到时给出链接。
笔记都是按照本人的理解去写的，给出的数学基础知识也只是本人薄弱的地方，并不适合所有人。如有问题欢迎给我留言。
数学公式使用Letex编辑，原文博客http://blog.csdn.net/rosetta

笔记主要内容

本课程主要涉及四方面内容：监督学习、学习理论、无监督学习和强化学习，所以笔记主要也是记录这四块内容，当然还有相关的数学知识。

监督学习（supervised learning）
回归问题（regression problem）连续的
分类问题（classification problem）离散的
无限维空间的问题，使用支持向量机（support vector）算法，可以把数据映射到无限维空间中。
学习理论
如何保证学习算法是有效的？训练数据集要达到多少才可以？
无监督学习（unsupervised learning）
给定一组数据，能发现这些数据的特点，能把相同特点的归类。也就是聚类（clustering）问题。
聚类可以做图像识别，可以使用一张照片建议3D场景，可以从杂吵声中提取出感兴趣的人的声音。
强化学习（Reinforcemnet Learning）
回报函数，
视频中举了个使用强化学习算法控制小型直升机的例子。做的好就奖励它，做的不好就惩罚它，但是如何去定义一个好的形为和坏的形为？
还可以用在网页爬取方面。

最后再提出一个关键问题，如何使用机器学习一个工具就解决实际问题？我想这也是我为什么选择去学机器学习的原因之一。

基本概念

一个关于房价的例子，目前是使用现有的数据来预测房子的价格，首先约定一些数学符号及其表示的含义。
如下是房子面积和房价的关系。
机器学习笔记(1)---监督学习之梯度下降
在坐标平面画出相应的点的：

使用 $x^{(i)}$ 表示输入，其中 $i$ 表示第几个样本，使用 $y^{(i)}$ 表示输出。 ${(x^{(i)}, y^{(i)}), i = 1, 2, \dots, m}$ 表示训练集。或者使用 $X$ 表示输入数据空间， $Y$ 表示输出数据空间，本次例子中 $X = Y = R$ 。
给定训练集，学习函数 $h : X \mapsto Y$ ， $h (x)$ 为 $y$ 的预测函数,其处理过程如下图显示：
机器学习笔记(1)---监督学习之梯度下降

线性回归

在本次课程中线性回归主要讲两种方法：梯度下降和正规方程。本篇笔记主要写梯度下降法，正规方程见下次笔记。

梯度下降法

在刚才房子的例子上增加一个屋子数量的特征。
机器学习笔记(1)---监督学习之梯度下降
此时 $x$ 变成了二维的向量， $x_{1}^{(i)}$ 表示面积， $x_{2}^{(i)}$ 表示屋子数量， $i$ 表示第 $i$ 条房子的数据.
为了完成监督学习（supervised learning），需要决定预测函数 $h$ ，可以给定一个关于 $x$ 的线性函数：

\begin{matrix} (1) & h_{θ} (x) = θ_{0} + θ_{1} x_{1} + θ_{2} x_{2} \end{matrix}

其中

θ_{i}

称为参数，或者权重，它用于确认从

X

映射到

Y

的参数，得到合适的参数

θ

是学习算法的任务。当不会发生混淆的时候可以把

h_{θ} (x)

中的

θ

去掉，简写成

h (x)

。为了简化符号，可令

x_{0} = 1

，这样公式就变成:

\begin{matrix} (2) & h (x) = \sum_{i = 0}^{m} θ_{i} x_{i} = θ^{T} x \end{matrix}

那么 $θ$ 如何确定呢？一种可行的方法是选择一组 $θ$ 和训练数据 $X$ 一起算出 $h_{θ} (x)$ （此时由于 $x$ 是已知的，所以可以把 $h$ 看成是关于 $θ$ 的函数，一旦后续把 $θ$ 学到后， $x$ 是将要预测的数据，那么那时 $h$ 就要看成是关于 $x$ 的函数），让 $h_{θ} (x)$ 尽可能的接近 $y$ ，那么如何描述这个接近呢？数学中描述接近常用的方法是求两者差的绝对值，课程中给出的公式稍稍有点不同。

\begin{matrix} (3) & J (θ) = \frac{1}{2} \sum_{i = 1}^{m} {(h_{θ} (x^{(i)}) - y^{(i)})}^{2} \end{matrix}

其中的

\frac{1}{2}

是为了后续的求导简便加上去的，此公式目前只有

θ

是未知的，所以此时的任务就是去找一组

θ

，使得

J (θ)

最小，这样就学到了参数

θ

，参数

θ

定了以后，等要预测一套未在训练集中的房子数据时（即知道了

x^{(i)}

的各项参数

x_{1} ， x_{2}

)，我们就可以用上面的公式

h_{θ} (x) = θ_{0} + θ_{1} x_{1} + θ_{2} x_{2}

，求出

h_{θ} (x)

，这个

h_{θ} (x)

即这套房子的价格。
下面的问题是如何求出

θ

，能使得

J (θ)

最小。这类问题称为无约束最优化问题。梯度下降法就是其中的一种方法。

\begin{matrix} (4) & θ_{i} := θ_{i} - α \frac{\partial}{\partial θ_{i}} J (θ) \end{matrix}

其中

α

为学习速度，它决定每次迭代的步长，此值需要手动调整。

i

表示某条数据的第

i

个属性。
当只有一组训练数据时

\begin{array}{rcl} (5) & \frac{\partial}{\partial θ_{i}} J (θ) & = & \frac{1}{2} \frac{\partial}{\partial θ_{i}} {(h_{θ} (x) - y)}^{2} \\ (6) & = & \frac{1}{2} \cdot 2 (h_{θ} (x) - y) \cdot \frac{\partial}{\partial θ_{i}} (h_{θ} (x) - y) \\ (7) & = & (h_{θ} (x) - y) \cdot x_{i} \end{array}

带入

4

式得：

\begin{matrix} (8) & θ_{i} := θ_{i} - α (h_{θ} (x) - y) \cdot x_{i} \end{matrix}

8

式这表示一条数据的某个属性前的权重

θ

求法。其中

(h_{θ} (x) - y)

中的

h_{θ} (x)

是使用指定的

θ

算出的预测值，

y

为样本中已经知道的房子的价格。
当考虑

m

组训练数据时：

\begin{matrix} (9) & θ_{i} := θ_{i} - α \sum_{j = 0}^{m} (h_{θ} (x^{(j)}) - y^{(j)}) \cdot x_{i}^{(j)} \end{matrix}

其中

j

表示第几条数据，

i

表示每条数据中的第几个属性。
运用此式迭代直到收敛，这就是批梯度下降（Batch Gradient Descent）算法。梯度下降法很容易被局部最小值影响，而我们要求得的全局最优解，也就是说应该收敛于全局最小值。由于此次函数J实际上是凸二次函数，它只有一个全局最小值（视频中展示像一个碗状的图），所以不需要考虑那么复杂。
以下是梯度下降的一个例子，它对二次函数求最小值。
机器学习笔记(1)---监督学习之梯度下降

这个椭圆是二次函数

J

函数的轮廓图（contours of a quadratic function），图中那条蓝线是梯度下降法生成的轨迹，它的初始值是（48,30）。图中的

x

标记了梯度下降过程中所经过的

θ

可用值。
用之前的训练集使用批梯度下降法来拟合

θ

,把面积作为学习和预测房屋的价格的函数，学得

θ_{0} = 71.27, θ_{1} = 0.1345

。假如把

h_{θ} (x)

看作是面积

x

的函数，并使用房屋数据集，可得到如下图形:
机器学习笔记(1)---监督学习之梯度下降

假如把屋子数量也作为一个输入特征的话，可以学得

θ_{0} = 89.60, θ_{1} = 0.1392 ， θ_{2} = - 8.738

。上述结果就是使用批梯度下降算法得到的。但是上面的算法每一次迭代都要使用所有

m

个样本，如果样本成千上万甚至上亿，那么效率就很低。
下面使用随机梯度下降算法（或叫增量梯度下降法），算每个θ时不需要对所有的样本就和，其公式如下：
机器学习笔记(1)---监督学习之梯度下降

正文部分公式推导

公式2推导

\sum_{i = 0}^{m} θ_{i} x_{i} = θ_{0} x_{0} + θ_{1} x_{1} + \dots + θ_{i} x_{i}

θ^{T} x

是向量表示方法，把向量展开成矩阵，则其表示的含义如下：

\begin{array}{rcl} (1) & θ^{T} x & = & {⟮ \begin{array}{ccc} θ_{0} \\ θ_{1} \\ ⋮ \\ θ_{i} \end{array} ⟯}^{T} ⟮ \begin{array}{ccc} x_{0} \\ x_{1} \\ ⋮ \\ x_{i} \end{array} ⟯ \\ (2) & = & ⟮ \begin{array}{ccc} θ_{0}, & θ_{1}, & \dots, θ_{i} \end{array} ⟯ ⟮ \begin{array}{ccc} x_{0} \\ x_{1} \\ ⋮ \\ x_{i} \end{array} ⟯ \\ (3) & = & θ_{0} x_{0} + θ_{1} x_{1} + \dots + θ_{i} x_{i} \\ (4) & = & \sum_{i = 0}^{m} θ_{i} x_{i} \end{array}

所以

\begin{matrix} (2) & \sum_{i = 0}^{m} θ_{i} x_{i} = θ^{T} x \end{matrix}

公式7推导

\begin{array}{rcl} (5) & \frac{\partial}{\partial θ_{i}} J (θ) & = & \frac{1}{2} \frac{\partial}{\partial θ_{i}} {(h_{θ} (x) - y)}^{2} \\ (6) & = & \frac{1}{2} \cdot 2 (h_{θ} (x) - y) \cdot \frac{\partial}{\partial θ_{i}} (h_{θ} (x) - y) \\ (7) & = & (h_{θ} (x) - y) \cdot x_{i} \end{array}

这里主要用到高等数学里的导数、偏导数和复合函数求导，
5到6式，主要是复合函数求偏导。
6到7式，主要是红色部分的计算，这里是对

θ_{i}

求偏导，偏导数和导数其实是类似的，只不过在多个自变量的情况下有一个偏向，当对其中一个变量做偏导时，其它变量看作常数即可。比如上述公式自变量有

x, y, θ

三个,如果对

θ

做偏导，那么把

x ， y

看成常量即可。
因为

6

式中的

h_{θ} (x)

由公式

1

知

h_{θ} (x) = θ_{0} + θ_{1} x_{1} + θ_{2} x_{2}

，所以如果对

θ i

做编导的话，只对

θ i x_{i}

做即可，其它不带

θ i

的项看成常数，常数求导为

0

，所以求导结果就是

x_{i}

。

机器学习笔记(1)---监督学习之梯度下降

前言