之前浏览Coursera上机器学习方面的课程，Andrew Ng的《Machine Learning》课程评分一直很高，于是添加在了自己的收藏列表，但一直没学。今年本科毕业季时注册了课程开始学习，基本上按照课程大纲看视频，完成练习，最后终于在课程结束前一周多顺利结业。线上教育作为教育的一个大趋势，这门课程作为自己圆满完成的第一个线上课程，自己在完成提交的时候感受到满满的成就感。因为自己以前也注册过很多线上课程，但圆满完成所有课程视频和课后练习的，这个第一个。这是写这篇博文的第一个原因。人生中很多重要的时刻都值得记忆并记录，而大脑的记忆很多时候是短暂且不可靠的。写这篇博文的第二个原因是想对自己学过的内容作一个梳理和复习，加深理解和记忆。不得不说，作为机器学习领域国际公认的大牛和Coursera的联合创始人，Andrew的这门课程的视频通俗易懂，练习也不难，是一门非常好的机器学习入门课程。由于本人刚刚进入这个领域开始学习，所以这篇文章如果有什么表述不准确的地方，还请大家多多指正。

介绍

什么是机器学习

在学习具体的机器学习算法之前，对机器学习的基本概念有一个清晰的认识很重要。目前对机器学习有两种比较流行的定义。一个是美国人工智能和机器学习方面的先驱Arthur_Samuel给出的：

the Field of study that gives computers the ability to learn without being explicitly programmed

也就是说机器学习研究的是赋予计算机在没有被明确编程的情况下一种学习的能力。这是Arthur_Samuel在1959年提出来的。另一个更正式和更现代的定义是由Tom M. Mitchell提出来的：

A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P if its performance at tasks in T, as measured by P, improves with experience E.

也就是说对于某类任务T和性能度量P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么称这个计算机程序从经验E中学习，这种学习就是机器学习。还是有点抽象。举个手写识别系统的例子，手写识别系统的任务就是要识别和分类图像中的手写文字，该系统性能好坏的评判标准就是识别的准确率，一些已分类的手写文字数据库就是训练经验。手写识别系统内的程序就是利用已分类的手写文字数据库来训练，来提高对手写文字的识别率。

机器学习的分类

根据输入的训练集的特征和要解决的问题的类型，机器学习主要分成两大类：监督学习和非监督学习。

• 监督学习：给定有特定输入和对应的正确的（或者说想要的）输出的数据集，监督学习就是要学习出输入和输出之间的一种映射，找到输入和输出之间的关系。根据输出值的不同监督学习问题又可分为分类问题和回归问题。如果输出值是一个离散的有限集合，要解决的就是分类问题，如果输出值是连续的，那么就是回归问题。举个例子，把机器学习应用到股票分析上，给定一个上市公司以往的各种数据，预测该公司的未来的股价。如果是想要预测公司股价未来具体的价格，这就是一个回归问题，如果想要预测该公司股价在未来是涨还是跌，这就是一个分类问题。
• 非监督学习：给定的数据集只有特定的输入，没有期望的输出。非监督学习的任务就是要去发现这些数据集之间隐藏的结构关系。一个典型的学习是聚类，就是发现数据集中类似的东西。

为了更清楚和形象地说明监督学习和非监督学习，举个简单的例子。一位老师拿了一堆苹果和香蕉的图片给小朋友们，这堆图片中包含不同场景下的苹果和香蕉，把这堆图片叫作“训练集”。如果老师事先不告诉小朋友们这堆图片是什么东西，只是让他们自己去看，然后归类，之后老师再单独拿出另外一堆图片（称之为“测试集”）让他们去判断这些图片是不是属于刚刚看过的图片中的某一类。小朋友们这种学习的过程其实就是一种非监督学习。如果老师事先告诉小朋友们训练集中的图片哪些是苹果，哪些是香蕉，然后再拿出测试集，让小朋友辨认哪些是苹果，哪些是香蕉，这个过程就是监督学习。

监督学习

线性回归

最简单的线性回归模型是单变量线性回归，也就是从单个特征变量X的输入去预测单个输出值。构建一个假设函数h(x)，再构建一个代价函数J(θ)去衡量假设函数拟合的准确度，这个代价函数一般也叫作“平方误差函数”。拟合的最好的情况是所有点到拟合直线的垂直方向的距离的平方和的平均值最小，也就是说拟合直线尽可能穿过所有点。在这种情况下J(θ)的值等于0。当输入的特征变量不是一个，而是多个时，就是多元线性回归问题。假设函数和代价函数的构建和单变量线性回归相同，只是变量个数不同而已。

有了假设函数和代价函数，就需要估计假设函数中的θ参数，找出使代价函数最小的θ值。这里就用到了梯度下降算法。为了便于直观地理解梯度下降算法，我们画出代价函数J(θ)关于θ参数的图，单变量回归的情况下就是曲线图，多元回归的情况下就是曲面图。找出使代价函数最小时的θ值就是图中最低点对应的θ值。梯度下降算法的基本思想是先确定一个初始的θ值和学习速率α，然后对代价函数J(θ)求梯度，θ值在求出的梯度的方向的指引下，以学习速率和梯度大小的乘积为步长进行迭代，直至收敛。

如果不同输入特征变量之间的值域相差过大，就会导致梯度下降算法的运行速度很慢。为了解决这个问题，常用的一种方法是特征规整，通过特征规整把输入变量变成大致相同的范围，一般变成（-1,1）或者（-0.5,0.5），但也没有一个明确的要求。常用的特征规整的方法又有特征缩放和均值归一化。特征缩放就是用输入变量值分别除以输入值的值域区间长度。而均值归一化就是用每个输入值减去输入值的均值后，除以输入值的值域区间长度或者输入值的标准差。调试梯度下降算法时，找到一个合适的学习速率很重要。可以绘出J(θ)关于迭代次数的曲线，正常情况下曲线应该是下降的，如果观察到曲线J(θ)随着迭代次数在上升，那么可能需要减小学习速率的值。也可以做自动收敛测试，也就说如果J(θ)在迭代中下降的值小于某个阈值就认为收敛，但是这个阈值一般不好确定。

在特征的选取和假设函数的形式上有多种方法。比如可以把多个特征通过相乘的方式结合成一个特征，假设函数的形式也不必一定是线性的，比如可以是特征的平方项、三次项等，这就构成了多项式回归。

在寻找最优θ参数时，也可以利用标准方程来直接求得θ的值，不需要通过梯度下降算法中的多次迭代，但由于需要求矩阵的逆，如果特征过多的话，方程的求解过程也会很慢。

逻辑回归

虽然这类问题名字叫逻辑回归，这是由于历史命名的原因，但其实这类问题是分类问题。先从简单的二分类问题开始，也就是说输出值是0或者1。逻辑回归的基本思想就是将线性回归假设函数通过Sigmoid函数映射到(0,1)区间，这样就得到了逻辑回归的假设函数，为了得到离散的0,1分类，再将假设函数值不低于0.5的映射为1，小于0.5的映射为0。对于代价函数的表示，就利用了log函数，代价函数由两项组成——输出为1和输出为0，当期望输出为1时，假设函数的预测输出越接近1，整个代价函数的值就越小；当期望输出为0时，假设函数的预测输出越接近0，整个代价函数的值就越小。对于逻辑回归问题的θ值的优化求解问题，仍然可以用梯度下降算法，但为了更高的算法效率，可以采用更高级的算法像“共轭梯度”，“BFGS”，“L-BFGS”等。

对于多分类问题，也就是输出值是(0,1,...,n)。基本思想是把多分类问题转化为(n+1)个二分类问题，在每个二分类问题中，我们选择一个类，然后把所有其他类都归为第二类，这样重复(n+1)次后，就得到了(n+1)个不同类的假设函数，使用这(n+1)个假设函数，返回最大的预测值概率的就是我们该预测的结果。

神经网络（NN）

当特征个数比较少时，用回归模型假设可能还不是很复杂，但随着特征数增多，如果还用回归模型的话，假设函数会变得非常复杂。神经网络应运而生。神经网络的工作原理就是模仿我们的大脑的工作方式。研究发现，大脑内部其实只用一个学习模块来学习不同的功能。科学家做过这样一个实验：他们切断了动物的耳朵和他们大脑中听觉皮层之间的神经连接，然后把听觉皮层嫁接到视神经上，结果听觉皮层也学会了看。

基本的神经网络主要由三层组成：输入层、输出层和隐藏层。输入层就是不同的特征输入，输出层就是假设函数的预测结果输出，根据神经网络复杂度的不同，可以有多个隐藏层。每层可以由多个节点组成。在神经网络中0参数称之为“权重”，每层都有各自的0参数，在计算下一层的输出时，都要加上偏置单元。在处理逻辑回归问题时，也使用Sigmoid函数进行映射。神经网络的代价函数的大体结构和一般的逻辑回归的代价函数一致，只是加和项更复杂。

在优化神经网络的代价函数的过程中会用到反向传播算法。算法本身有点复杂，不在本文中展开。在训练神经网络的过程中，为了保证反向传播算法按照预想的方式工作，需要进行“梯度检查”。另外，θ参数不能全部初始化为0，否则在执行反向传播时，所有的节点都将更新到同一个值，为了避免这种情况，θ要进行随机初始化。

总结一下训练神经网络的步骤：

1. 随机初始化θ参数；
2. 执行前向传播算法计算假设函数；
3. 计算代价函数；
4. 执行反向传播算法计算偏导数；
5. 执行梯度检查，确保反向传播算法工作正常，然后关闭梯度检查算法；
6. 运用梯度下降或者其他内置的高级优化算法来最小化代价函数，得到对应的θ参数。

支持向量机（SVM）

课程中支持向量机的引入是通过将逻辑回归的代价函数中的log函数换成max函数再进行一些形式的变换后得到的。与逻辑回归的假设函数输出概率值不同，支持向量机的假设函数直接输出类别，比如0或1。支持向量机的代价函数的非正则项有一个系数C（C=1/λ）,C值的作用和λ的作用正好相反。当想避免过拟合时，减小C的值。支持向量机是一种大间距分类器（Large Margin Classifiers）。也就是说支持向量机产生的决策边界尽可能地远离正样本和负样本。决策边界和最近的样本之间的距离叫作margin。

课程中还提到了核函数，支持向量机可以利用不同的核函数进行分类。课程中就举了高斯函数作为核函数的例子。

在支持向量机的使用中，需要考虑以下的问题：

1. 选择一个参数C
2. 选择核函数（相似度函数）：

• 不用核函数（线性核函数），得到的是标准的线性分类器，这种情况适用于特征数很多而训练样本数很少；
• 使用高斯核函数，在使用高斯核函数之前需要进行特征缩放，同时需要确定标准差的大小，这种情况适用于特征数很少而训练样本很多

3. 逻辑回归与支持向量机的比较（n代表特征数，m代表训练样本数）：

• 如果n相对于m来说很大，使用逻辑回归或者不带核函数的SVM；
• 如果n很小，m中等大小，使用带高斯核函数的SVM；
• 如果n很小，m很大，那么就手动创建一些其他的特征，再使用逻辑回归或者不带核函数的SVM

非监督学习

非监督学习仅仅给了无标签的数据集，由非监督学习算法去找出数据集内部的机构，非监督学习中一个主要的类别就是聚类分析。聚类分析在市场划分、社交网络分析，组织计算集群和天文数据分析中都扮演了重要的角色。

K均值算法

K均值算法的思想如下：

1. 在数据集中随机初始化K个点（K代表类的个数），这些点叫作聚类中心；
2. 把数据集中所有点分配到离它最近的聚类中心；
3. 计算属于每个聚类中心的点的平均值，将聚类中心移到这些平均值处；
4. 重复步骤2和3，直到聚类中心稳定。

K均值算法有时候会卡在局部最优解上，为了防止这种情况发生，聚类中心的随机初始化可以使用下面的算法实现，即进行多次随机初始化：

for i = 1 to 100:
   randomly initialize k-means
   run k-means to get 'c' and 'm'
   compute the cost function (distortion) J(c,m)
pick the clustering that gave us the lowest cost

主成分分析（PCA）

数据降维：数据降维可以用于数据的压缩，占用较少的存储空间，同时可以加快算法的速度。另外数据降维后便于数据的可视化，因为对于超过三维的数据，数据就不便于可视化。值得注意的是，数据降维，降的是数据的特征数，而不是数据集中样本的数量。很流行的数据降维算法就是主成分分析算法。

PCA的目标是将每个特征往一条直线或一个平面上投影，使得投影误差的平均值最小。比如说，把数据从n维降到k维，就是找k个向量，使得数据在这些向量上的投影误差最小。在这里需要说明一下，PCA不是线性回归，线性回归是最小化平方误差，是垂直（vertical）距离，而PCA是最小化最短间距，或者说正交（orthogonal）距离。

主成分分析算法的主要步骤如下：

1. 进行数据预处理：进行特征缩放或者均值归一化
2. 计算特征向量的协方差矩阵；
3. 计算协方差矩阵的特征向量；
4. 取求得的U矩阵的前K列，再计算降维后的特征向量。

算法在matlab中的实现代码如下：

Sigma = (1/m) * X' * X;  % compute the covariance matrix
[U,S,V] = svd(Sigma);    % compute our projected directions
Ureduce = U(:,1:k);      % take the first k directions
Z = X * Ureduce;         % compute the projected data points

降维后的维度K的选取：
在上面的代码中的第二行计算特征向量时，返回了一个S矩阵，S矩阵是一个对角矩阵，选取的K值应该满足S矩阵对角上的前K个值的和与对角上所有值的和的商大于0.99，满足这一条件的K值都是可以的。

异常检测

给定一个数据集，然后再给定一个测试样本，判断这个样本是否异常，这类问题就是异常检测问题。

算法

1. 计算各个特征的平均值和方差，假设各个特征之间相互独立，并且遵从高斯分布，建立概率预测函数P(x)；
2. 对于给定的样本，计算P(x)的值；
3. 若P(x)<ε，则为异常。

异常检测系统的开发和评估

为了评估异常检测算法的有效性，我们取一些带标签的数据，分为正常样本和异常样本两类，正常样本占大多数，将这个数据集分为三个子数据集：训练集（60%，全是正常的），交叉验证集（20%，其中0.1%属于异常数据，其余为正常数据），测试集（20%，其中0.1%属于异常数据，其余为正常数据）。从训练集中训练出模型P(x)，应用在交叉验证集上来确定决策阈值ε，在测试集上进行测试。误差评估可以采用前面讨论过的准确率、召回率或者F值。另外说明一下，特征的选取对于异常检测系统的表现有很大影响，我们可以通过画一个直方图来看看数据集的分布是不是大致符合高斯分布，如果不符合，可以先对数据做一个变换，像log函数，平方根函数等，处理后的数据一般都会符合高斯分布。此外，我们还可以使用多变量高斯分布来描述P(x)。

一些应用

机器学习的一个很重要的应用就是推荐系统。推荐系统分为两大类：基于内容的推荐系统和协同过滤。

基于内容的推荐系统的主要思想是已知电影的特征成分表达，比如说一部电影的爱情成分占多少，动作成分占多少等，将用户对电影的评分用一个线性模型进行拟合，对于每个用户学习出一个对应的参数θ。和前面讨论的线性回归模型基本一致。

协同过滤算法考虑到对一部电影中的特征成分进行标定是一件比较难的事，所以协同过滤算法从用户处收集他们对不同类别的电影的评分，从这些评分中去学习电影的特征成分。协同过滤算法又可以分为两类：基于用户的协同过滤和基于物品的协同过滤。

搭建系统时的评估与建议

正则化

在讲正则化之前，我们先弄清楚高偏差或者欠拟合和高方差或者过拟合的概念。高偏差或者欠拟合是指假设函数对数据的拟合程度很低，不能很好地描述数据的趋势，通常是假设函数太简单，利用的特征太少造成的。高方差或者过拟合是指假设函数对训练集中的数据能有很好的拟合，但是预测新数据的准确性就太差，这通常是由于选择的特征太多，假设函数太复杂造成的。对于过拟合的问题，通常有两种解决方案，一种是减少特征的数量，另一种就是正则化。

简单地说，正则化的思想就是减小特征前的θ参数来惩罚该特征项，而这种惩罚又是通过增加他们在代价函数的代价来实现的。通常是在原本的代价函数的基础上额外加上一项，该项是由一个正则参数λ和θ项的平方和的乘积构成，当选择一个较大的λ值时，为了使代价函数值最小，θ项的平方和必须很小，也就说通过λ值来惩罚θ参数。λ值也不能太大，太大就会惩罚过度，造成欠拟合。另外，在执行梯度下降的迭代时，也要加入正则项。

模型选择与系统诊断

模型选择

首先必须明确，一个假设函数对训练集的拟合程度很好并不代表这是一个好的假设，用从训练集得到的假设函数在训练集上进行误差分析，得到的误差会比把这个假设函数用在其它数据集上得到的误差要小。模型选择要解决的问题是：如何选择假设函数中的多项式的阶数，哪些特征应该放进假设函数中，如何选择正则参数λ。

为了解决这个问题，我们可以把数据集分为三个部分：60%作为训练集，20%作为交叉验证集，20%作为测试集。对于多项式阶数的选择问题，大致的步骤如下：

1. 使用训练集得到不同阶数下的假设函数的θ参数；
2. 计算1中得到的假设函数用在交叉验证集上的误差，选择误差最小时对应阶数的模型；
3. 将选择的模型应用在测试集上，估计通用误差。

系统诊断

系统诊断需要确定是偏差还是方差导致不好的预测结果，确定原因后再确定采取什么样的解决办法。

先来研究一下多项式的阶数与偏差和方差之间的联系。随着多项式阶数的增加，训练集的误差会一直减小，同时交叉验证集的误差也会随之减小，但当阶数增加到一定程度，交叉验证集的误差会转而增加。所以最优的阶数应该是在交叉验证集的误差的转折点对应的阶数。总结一下就是，出现高偏差（欠拟合）时，训练集和交叉验证集的误差都很大，并且近似相等；出现高方差（过拟合）时，训练集误差依然很小，但是交叉验证集的误差会比训练集误差大很多。

现在来研究一下正则参数λ与偏差和方差之间的联系。λ越大，对θ参数的惩罚就越大，假设函数就会被大大简化，从而出现高偏差（欠拟合），此时训练集误差和交叉验证集误差都会很大；λ较小时，训练集的误差会较小，交叉验证集的误差会较大，出现高方差（过拟合）的问题。所以一个最优的λ值是使训练误差和交叉验证集误差都相对较小，并且近似相等。

为了选择一个合适的模型和正则参数λ，我们可以依照下面的步骤来做：

1. 创建一个λ的集合；
2. 选择一个λ进行计算；
3. 创建一个不同阶数或者其他的模型集合；
4. 选择一个模型去学习参数θ；
5. 利用选择的模型，使用带有选择的λ参数的代价函数去学习得到参数θ；
6. 在训练集上，利用学习得到的θ参数，使用不带λ参数的代价函数（即误差函数）计算训练集误差；
7. 在交叉验证集上，利用学习得到的θ参数，使用不带λ参数的代价函数（即误差函数）计算交叉验证误差；
8. 在所有的模型和λ参数的组合上重复以上步骤，选择使得交叉验证集误差最小的组合；
9. 使用最佳组合的λ和θ参数，在测试集上计算测试集误差。

接着再来研究一下误差和训练集的大小的关系，也叫作学习曲线。当一个系统遭受高偏差问题时，训练集很小时，训练集误差会很小，但是交叉验证集误差会较大，随着训练集的增大，训练集误差会逐渐增大，交叉验证集误差会逐渐减小，训练集增大到一定程度时，训练集误差和交叉验证集误差会趋于相等，但误差都很大。所以，当系统遭受高偏差问题时，增大训练集的大小帮助不大。当一个系统遭受高方差问题时，训练集很小时，训练集误差较小，交叉验证集误差较大，随着训练集的增大，训练集误差和交叉验证集的变化趋势和高偏差问题一样，但是当训练集增大到一定程度，交叉验证集误差会大于训练集误差。所以，当系统遭受高方差问题时，增大训练集的大小会有帮助。

总结一下在系统诊断时应该了解的一些原则：

• 增大训练集的大小可以修复高方差的问题而不是高偏差；
• 减少特征可以修复高方差而不是高偏差；增加特征可以修复高偏差而不是高方差；
• 增加多项式项可以修复高偏差而不是高方差；
• 在使用梯度下降算法时，减小λ可以修复高偏差，增大λ可以修复高方差；
• 在使用神经网络时，简单的神经网络更倾向于会产生欠拟合，复杂的神经网络更倾向于产生过拟合。

系统设计

Andrew在课程中推荐的解决一个机器学习问题的步骤如下：

1. 先从简单的假设函数开始，快速实现它，并作早期测试；
2. 画出学习曲线，根据学习曲线来确定是否更多的数据或者更多的特征会对模型的改善有帮助；
3. 在交叉验证集上进行误差分析。

说到误差分析，有时候很难确定误差数据的减小是否代表系统的改进。这种情况在偏斜类问题上很突出。所谓偏斜类，就是说我们要预测的类在整个数据集中数量很少。对于偏斜类的误差分析，我们采用准确率/召回率进行衡量。也可以把这两种度量变为一种度量：F值。

参考

Tom Mitchell: 《机器学习》

wikipedia：Machine Learning

ML Wiki Page: Machine Learning Lecture Notes