已经正式完成Coursera机器学习第1周的课程，感觉一切还算在掌握之中。由于不少东西都是念本科的时候学过的，所以没有什么痛楚。
这里简要记录一些我个人认为比较重要的东西、学习心得。
另外，需要声明一点，由于课程本身有“不得抄袭”的要求，我除了尽力做到不抄袭外，还得做到不被人抄袭，所以课程的总结是不会有任何课堂习题、课后作业、考试题的答案的，即便涉及到习题本身，可能也是分享一些自己的心得或者小发现。
引言：什么是机器学习
定义
这么多年从事软件开发，其实都没认真地去弄清楚机器学习到底是什么。在描述它是什么之前，吴恩达教授先介绍了它的应用领域，例如搜索引擎、垃圾邮件过滤、自然语言处理、手写文字识别、计算机视觉、推荐系统等等，都是日常使用的各种软件、网络产品。
最早提出机器学习概念的是Arthur Samuel（美国人、MIT）。他喜欢玩西洋跳棋，但吴教授说他很菜，所以在想有没有一种办法，能够在只了解棋类的基本规则的前提下写出一种能战胜自己的程序。于是他在1959年，提出了机器学习的概念，代表这种程序能够学习人类的下棋方式，他给机器学习下了如下定义：
Field of study that gives computers the ability to learn without being explicitly programmed.
一个能够不必显式编程便可以使得计算机带有学习能力的研究领域。
这个定义虽然不是很规范，但是它在计算机领域是有开创性意义的——一种可以不必显式编程、通过学习来获得新功能的程序。但吴教授没有解释什么是显式/非显式编程。这个概念对计算机、软件的学生来说不陌生，但是也未必全部人明白。举例现在有红蓝两色的球递给你，给红色球就说“红”、给蓝色球就说“蓝”。显式编程重现这种行为就是直接if ... else ...就可以了。而非显式编程就是通过观察、记录这一系列行为，从而让计算机记住【给红色球就说“红”、给蓝色球就说“蓝”】这个规则。
非显式的编程方式有什么好处？虽然看起来程序代码变得不那么直观，但是现实世界中要处理的情况并非红蓝球那么简单，遇到组合爆炸的情况下，人类要一下子写出1万条分支的程序代码，且不说耗费大量编写和测试时间，如果组合存在嵌套或者模糊匹配，那么程序分支数量更是指数式上升。非显式编程是通过观察、统计的方式学习得到一种规则，它虽然无法能够被人类语言详细阐述，但对于计算机来说是实实在在的规律性，而程序却保持简单，维护便不会那么困难。非显式编程还有一个好处，以西洋跳棋为例，在只有基本走棋规则的前提下，通过不断和程序进行博弈、训练，程序便会慢慢累积更多能胜棋的经验，然后棋力便会慢慢变得强大，甚至编写程序的人完全不是一个西洋跳棋大师，也不妨碍他的机器学习程序慢慢成为大师级棋手。甚至有人宣称利用机器学习可以完全没有特定领域的知识也可以使机器学习程序达到该领域的专家水平——这个我倒是持保留意见的。
当然，在没有机器学习的规范定义和数学模型前，一切感觉都在说玄学。
于是发展到后来，在1998年，Tom Mitchell（美国人、Stanford）对机器学习下了更规范的定义：
A computer is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.
若执行一类任务T以效能P作为量度，一个计算机程序如能被称为可以学习关于任务T的经验E，则经过经验E改进后，这个程序可以提升效能P。
这个定义我个人觉得其实没多么重要，感觉更多在卖弄语言技巧，因为英文原文是押韵的。这个定义要求量化量度效能P，且经验E是能够信息化、数字化的。这在大多数情况下都是能满足的。
机器学习算法分类
通常来说机器学习算法分两大类，监督学习和无监督学习。但其实这样分类是不完整的，只是在字面意思上前面【有/无】感觉上就是全部类型都涵盖了。现在至少还有强化学习类的算法，但是这个课程貌似不打算详细介绍。（这叫学无止境……）
监督学习
监督学习最大的特征就是训练数据中包含着正确的结果。假设现在房价（果变量）只和房子的面积（因变量）有关，那么社会上现在房子成交的真实房价，不论它有多高，都是正确的结果。当通过大量的【因变量->果变量】数据训练后，便可以得到一个接近真实情况的估计，通过这个估计我们便可以估算（或预测）出一个从来没遇到过的面积的房子的房价。
回归
回归类的监督学习，它的果变量通常是带有连续性的。然而真实世界的数据其实都是零散的，所以要判断果变量是不是带有连续性，需要一定的前提假设，例如前面我们要预测房价那么假设房价与面积正相关，也就是说房子即使多出1平方毫米也应该贵一点。而另一些情况即使数据是零散的，但是我们可以通过常识知道它肯定是连续数据，例如大气温度，99.9%的情况都是连续平滑变化的。
回归类的算法，最简单的情况就是线性回归，当然也存在其他类型的曲线回归，这也是需要对数据本身作一定的假设才可以。例如下图明显蓝色的二次曲线就比杨红色的直线对数据拟合得更好，选择哪种方式做回归，是需要对数据先做一定的剖析和假设的：
分类
相对地，分类监督学习的果变量就是离散性的。可以是果变量的值本身具有离散性，例如原子能级就是跃迁式、离散式的，也可是果变量的值本身是一些人为给予的标签，例如【是/否】、【喜欢/无感/厌恶】，将这些标签数值化，例如改成【1/0】、【1/2/3】，便可作为训练数据的果变量，这些转换可以用一些特定的数学技巧用以放大/缩小数值，以便后续处理。
分类在几何上就是画线（二维）或者超平面（N维）将数据点分隔开：
上图表示将【是/否】这种特殊的二值离散映射到单个维度的因变量上，利用数据点的颜色作为【是/否】的区分。
然后便可以通过前面的方式推广至有二维因变量的情况上。
N维如此类推。
无监督学习
相对地，无监督学习指的就是训练数据中没有所谓的正确的结果。可以想象为一批数据点，每个数据点自身并没有表明哪些特征是因变量、哪些是果变量。但可以通过数据自身的几何结构或其它方式对数据进行聚类分类或者求值。
聚类
聚类是典型的无监督学习算法，例如Google的新闻聚合，它不是通过人工的方式进行整理的，而是通过计算每篇新闻的内容特征得出这篇文章应该归为什么类型。
聚类应用很广泛，还可以用于人类基因组测算、计算机集群、社交网络分类、市场分析定位、宇宙星际数据分析。
鸡尾酒派对问题
在鸡尾酒派对上，这个嘈杂的环境中，人类可以基本听到身边人的说话声音，人们称这叫做鸡尾酒派对效应。要计算机实现类似这种机制的声音分离，需要用到机器学习无监督算法，课程直接给出了算法 ：
[W, s, v] = svd((repmat(sum(x .* x, 1), size(x, 1), 1) .* x) * x');好吧我承认我是看不懂的……😥其实吴教授的意思是叫我们安心用Octave或者Matlab作为学习机器学习的工具，并意图用这段程序说明用它们可以有多简洁，并说湾区那些大牛们其实也是用它们做原型，然后再改写为通用编程语言的版本以便整合系统。
单变量线性回归
数学模型表示
继续使用前文所述的房价作为例子，假设面积为x、房价为y、收集到的数据量为m、即有m个\((x^{(i)}, y^{(i)})\)这样的数据，i为第i个数据，不是指幂。
* 为什么使用容易混淆的上标而不是下标？因为在多因变量（后面第2周的课程便会遇到）和多果变量的时候，需要用到下标，而幂在这里用不着，所以用上标。
假设它们是线性关系，而根据线性方程的一般式\(y = ax + b\)，我们可以将a换成\(θ_1\)、将b换成\(θ_0\)，那么对于任意的\(θ_0\)和\(θ_1\)，我们可以将它们组成的线性方程当作一个假设函数（Hypothesis）：\(h_θ(x)= θ_0 + θ_1 x\)，所有的\(θ_i\)们便是某个假设的参数。
代价函数
有了假设函数，便需要检验不同假设之间离真实数据的距离（代价）有多大。对于线性关系，要量度假设与实际之间差距，则计算第i项假设的果变量与第i项实际数据的果变量的差：\(h_θ(x^{(i)}) – y^{(i)}\)。由于我们只需要这个差值的绝对大小，所以便对这个差进行平方运算去除负值：\([h_θ(x^{(i)}) – y^{(i)}]^2\)，然后m个数据的差值累加起来，便是某个假设与真实之间的总体距离（代价）：\(\sum\limits_{i=1}^m[h_θ(x^{(i)}) – y^{(i)}]^2\)。
* 为什么使用平方而不是绝对值？从课程的论坛中找到的答案，说是因为求平方数的速度比求绝对值快（我怀疑），然后使用平方还可以方便后面求导数（我承认）。
对于这个总体代价，我们让它除以m，便相当于求得一个假设与所有数据点之间的平均平方误差，再让它除以一个常数2，不会改变它的性质，只为方面后面求导数（平方式求导会带有一个2作为系数，2/2=1便消除系数），便得到完整的代价函数：\(J(θ_0, θ_1) = \frac{1}{2m}\sum\limits_{i=1}^m[h_θ(x^{(i)}) – y^{(i)}]^2 = \frac{1}{2m}\sum\limits_{i=1}^m[θ_0 + θ_1 x^{(i)} – y^{(i)}]^2\)。
有了代价函数\(J(θ_0, θ_1)\)，我们只需要找到哪个\(θ_0\)和\(θ_1\)的值可以使得代价函数的值最小，即要找到\(min(J(θ_0, θ_1))\)。
两个因变量，一个果变量，眼看代价函数的值的分布图肯定要用三维图才可以表达出来：
但其实可以使用轮廓（Contour）图对上图进行描述，下左蓝线为\(θ_0 = 800, θ_1 = -0.15\)的时候的假设直线、右图为轮廓图、同色的一圈代表J值等高线：
所以寻找\(min(J(θ_0, θ_1))\)实际上就是在这样值空间中寻找J值的最低点。人类一眼就看到哪里就是最低点，但是计算机眼瞎，没有“一眼就可以看到”这个操作。
梯度下降算法
为了寻找最小的J值，于是梯度下降算法诞生了。它在计算机领域经常出现。它的伪代码如下：
重复 至 收敛 {
\(θ_j := θ_j – α \frac{\partial}{\partial θ_j} J(θ_0, θ_1) \) （同步更新 j=0 和 j=1）
}
所谓“重复至收敛”是指重复到\(θ_j\)的值不再有变化，换句话说就是重复到\(α \frac{\partial}{\partial θ_j} J(θ_0, θ_1) = 0\)。以\(θ_0\)和\(θ_1\)为例，梯度下降算法要求每次迭代同步更新\(θ_0\)和\(θ_1\)的值，即：
- \(temp0 := θ_0 – α \frac{\partial}{\partial θ_0} J(θ_0, θ_1)\)
- \(temp1 := θ_1 – α \frac{\partial}{\partial θ_1} J(θ_0, θ_1)\)
- \(θ_0 := temp0\)
- \(θ_1 := temp1\)
求值顺序是有要求的、不能乱的。因为一乱了就会使得\(\frac{\partial}{\partial θ_j} J(θ_0, θ_1)\)的值有变化。其实这是在提示我们在编写程序实现时，不要使用-=进行赋值，因为顺序会乱。
\(α \gt 0\)代表每次迭代的基准步长，又可以理解为每次学习的基准学习速率，它乘以偏导数项便是每次能下降的梯度。
所以要重复至收敛，必有偏导数项：\(\frac{\partial}{\partial θ_j} J(θ_0, θ_1) = 0\)，这意味着这个收敛位置其切面平行于\(θ_0\)和\(θ_1\)轴平面。
由于每次迭代就像在一级一级下楼梯，所以翻译成梯度下降还是挺传神的：
由于\(θ_0\)和\(θ_1\)的初始值是随机确定的，所以对于有局部最小值的情况下，在不同的起始位置可能会错误地把局部最小值当成全局最小值：
算法灵感
梯度下降算法最精致的地方就是偏导数项\(\frac{\partial}{\partial θ_j} J(θ_0, θ_1)\)。θ为二维的情况还不算直观，如果改成一维的情况就十分明了。代价函数变成\(J(θ_1)\)，J值与\(θ_1\)的关系便会变成二维曲线之间的关系，偏导数便变成导数\(\frac{\partial}{\partial θ_1} J(θ_1)\)。不论\(θ_1\)的初值如何，最终都会收敛到导数\(\frac{\partial}{\partial θ_1} J(θ_1) = 0\)的地方，即曲线的切线平行于\(θ_1\)轴的地方：
不过，所谓的收敛性是有可能会被\(α\)值影响的，因为它作为基准步长，每次迭代都会参与运算。如果它太小，整个过程就会很慢；相反，如果它太大，则有可能因为错过最小值而无法收敛，甚至变得发散：
而在收敛的过程中，导数\(\frac{\partial}{\partial θ_1} J(θ_1)\)的值其实就是切线的斜率，由于收敛的过程中切线的斜率越来越小，所以是无需变小\(α\)值也能正常运作的：
线性回归中的梯度下降
将前文所述的假设函数\(h_θ(x) = θ_0 + θ_1 x\)和代价函数\(J(θ_0, θ_1) = \frac{1}{2m} \sum\limits_{i=1}^m [h_θ(x^{(i)}) – y^{(i)}]^2\)代入梯度下降算法中，其中偏导数项为：
\(\begin{aligned}
\frac{\partial}{\partial θ_j} J(θ_0, θ_1) &= \frac{\partial}{\partial θ_j} \frac{1}{2m} \sum\limits_{i=1}^m [h_θ(x^{(i)}) – y^{(i)}]^2 \\
&= \frac{\partial}{\partial θ_j} \frac{1}{2m} \sum\limits_{i=1}^m [θ_0 + θ_1 x^{(i)} – y^{(i)}]^2 \\
&= \frac{\partial}{\partial θ_j} \frac{1}{2m} \sum\limits_{i=1}^m (θ_0^2 + 2 θ_0 θ_1 x^{(i)} – 2 θ_0 y^{(i)} + θ_1^2 x^{(i)2} – 2 θ_1 x^{(i)} y^{(i)} + y^{(i)2})
\end{aligned}
\)
当j=0时：
\(
\begin{aligned}
\frac{\partial}{\partial θ_0} J(θ_0, θ_1) &= \frac{1}{2m} \sum\limits_{i=1}^m (2 θ_0 + 2 θ_1 x^{(i)} – 2 y^{(i)}) \\
&= \frac{1}{2m} \sum\limits_{i=1}^m [2(θ_0 + θ_1 x^{(i)} – y^{(i)})] \\
&= \frac{1}{m} \sum\limits_{i=1}^m (θ_0 + θ_1 x^{(i)} – y^{(i)}) \\
&= \frac{1}{m} \sum\limits_{i=1}^m [h_θ(x^{(i)}) – y^{(i)}]
\end{aligned}
\)
当j=1时：
\(
\begin{aligned}
\frac{\partial}{\partial θ_1} J(θ_0, θ_1) &= \frac{1}{2m} \sum\limits_{i=1}^m (2 θ_0 x^{(i)} + 2 θ_1 x^{(i)2} – 2 x^{(i)} y^{(i)}) \\
&= \frac{1}{2m} \sum\limits_{i=1}^m [2(θ_0 + θ_1 x^{(i)} – y^{(i)})x^{(i)}] \\
&= \frac{1}{m} \sum\limits_{i=1}^m (θ_0 + θ_1 x^{(i)} – y^{(i)}) \cdot x^{(i)} \\
&= \frac{1}{m} \sum\limits_{i=1}^m [h_θ(x^{(i)}) – y^{(i)}] \cdot x^{(i)}
\end{aligned}
\)
所以线性回归的梯度下降算法伪代码为：
重复 至 收敛 {
\(temp0 := θ_0 – \frac{α}{m} \sum\limits_{i=1}^m [h_θ(x^{(i)}) – y^{(i)}]\)
\(temp1 := θ_1 – \frac{α}{m} \sum\limits_{i=1}^m [h_θ(x^{(i)}) – y^{(i)}] \cdot x^{(i)}\)
\(θ_0 := temp0\)
\(θ_1 := temp1\)
}
而关于梯度下降至局部最小值的情况，由于线性回归的代价函数是一个凸函数（Convex Function，从全局最低点向四周发散时斜率递增或不减），它的形状不论如何都会是碗形的，没有别的起伏位置，所以不必担心这个问题：
最后，线性回归中的梯度下降又称为“批量式”梯度下降，因为梯度下降的每一步都使用了所有的训练数据（\(\sum\limits_{i=1}^m [h_θ(x^{(i)}) – y^{(i)}]\)），此乃为批量。
线性代数回顾
这个是课程的可选内容。大学学过《线性代数》的可以完全跳过，没学过的就赶紧去学学矩阵、向量的基本运算和操作吧。
打赏作者
由 bruce 于 2017-11-2 14:07 更新
