台湾大学林轩田老师的《机器学习基石》课程由浅入深、内容全面，基本涵盖了机器学习领域的很多方面，作为机器学习的入门资料非常适合。很久之前看过这门课，但是有些地方还是不太明白，二刷这门课，把重要的知识总结起来，算是做一个复习，加深理解，也方便之后查阅。这篇文章介绍了第一部分When Can Machine Learn？

When Can Machine Learn?

什么是“学习”？学习就是人类通过观察、积累经验，掌握某项技能或能力。就好像我们从小学习识别字母、认识汉字，就是学习的过程。而机器学习（Machine Learning），顾名思义，就是让机器（计算机）也能向人类一样，通过观察大量的数据和训练，发现事物规律，获得某种分析问题、解决问题的能力。

The Learning Problem

本系列的课程对机器学习问题有一些基本的术语需要注意一下：

• 输入$x$
• 输出$y$
• 目标函数$f$，即最接近实际样本分布的规律
• 训练样本$data$
• 假设$hypothesis$，一个机器学习模型对应了很多不同的hypothesis，通过演算法A，选择一个最佳的hypothesis对应的函数称为矩g，g能最好地表示事物的内在规律，也是我们最终想要得到的模型表达式。

实际中，机器学习的流程图可以表示为：

对于理想的目标函数f，我们是不知道的，我们手上拿到的是一些训练样本D，假设是监督式学习，其中有输入x，也有输出y。机器学习的过程，就是根据先验知识选择模型，该模型对应的hypothesis set（用H表示），H中包含了许多不同的hypothesis，通过演算法A，在训练样本D上进行训练，选择出一个最好的hypothesis，对应的函数表达式g就是我们最终要求的。一般情况下，g能最接近目标函数f，这样，机器学习的整个流程就完成了。

Learning to Answer Yes/No

在这一节课程里介绍了一个机器学习算法：Perceptron Learning Algorithm (PLA)，为了更清晰地说明PLA，假设Perceptron在二维平面上，即$h(x)=sign(w_0+w_1x_1+w_2x_2)$。其中，$w_0+w_1x_1+w_2x_2=0$是平面上一条分类直线，直线一侧是正类（+1），直线另一侧是负类（-1）。权重w不同，对应于平面上不同的直线。

那么，我们所说的Perceptron，在这个模型上就是一条直线，称之为linear(binary) classifiers。注意一下，感知器线性分类不限定在二维空间中，在3D中，线性分类用平面表示，在更高维度中，线性分类用超平面表示，即只要是形如$w^Tx$的线性模型就都属于linear(binary) classifiers。

我们的目的就是如何设计一个演算法A，来选择一个最好的直线，能将平面上所有的正类和负类完全分开，也就是找到最好的$g$，使$g\approx f$。

如何找到这样一条最好的直线呢？我们可以使用逐点修正的思想，首先在平面上随意取一条直线，看看哪些点分类错误。然后开始对第一个错误点就行修正，即变换直线的位置，使这个错误点变成分类正确的点。接着，再对第二个、第三个等所有的错误分类点就行直线纠正，直到所有的点都完全分类正确了，就得到了最好的直线。这种“逐步修正”，就是PLA思想所在。

下面介绍一下PLA是怎么做的。首先随机选择一条直线进行分类。然后找到第一个分类错误的点，如果这个点表示正类，被误分为负类，即$w^{T}_{t}x_{n(t)}<0$，那表示$w$和$x$夹角大于90度，其中$w$是直线的法向量。所以，$x$被误分在直线的下侧（相对于法向量，法向量的方向即为正类所在的一侧），修正的方法就是使$w$和$x$夹角小于90度。通常做法是$w\gets w+yx, y=1$，如上图右上角所示，一次或多次更新后的$w+yx$与$x$夹角小于90度，能保证$x$位于直线的上侧，则对误分为负类的错误点完成了直线修正。

同理，如果是误分为正类的点，即$w^{T}_{t}x_{n(t)}>0$，那表示$w$和$x$夹角小于90度，其中$w$是直线的法向量。所以，$x$被误分在直线的上侧，修正的方法就是使$w$和$x$夹角大于90度。通常做法是$w\gets w+yx, y=-1$，如上图右下角所示，一次或多次更新后的$w+yx$与$x$夹角大于90度，能保证x位于直线的下侧，则对误分为正类的错误点也完成了直线修正。

按照这种思想，遇到个错误点就进行修正，不断迭代。要注意一点：每次修正直线，可能使之前分类正确的点变成错误点，这是可能发生的。但是没关系，不断迭代，不断修正，最终会将所有点完全正确分类（PLA前提是线性可分的）。这种做法的思想是“知错能改”，有句话形容它：A fault confessed is half redressed。

对PLA，我们需要考虑以下两个问题：

• PLA迭代一定会停下来吗？如果线性不可分怎么办？
• PLA停下来的时候，是否能保证$f\approx g$？如果没有停下来，是否有$f\approx g$？

对于第一个问题，在数据线性可分的情况下，PLA是可以停下来并正确分类的，但对于非线性可分的情况，$w_f$实际上并不存在，那么之前的推导并不成立，PLA不一定会停下来。对于非线性可分的情况，我们可以把它当成是数据集D中掺杂了一下noise，事实上，大多数情况下我们遇到的D，都或多或少地掺杂了noise。这时，机器学习流程是这样的：

在非线性情况下，我们可以把条件放松，即不苛求每个点都分类正确，而是容忍有错误点，取错误点的个数最少时的权重$w$。事实证明，含有noise的PLA是NP-hard问题，难以求解。然而，我们可以对在线性可分类型中表现很好的PLA做个修改，把它应用到非线性可分类型中，获得近似最好的$g$。

修改后的PLA称为Packet Algorithm。它的算法流程与PLA基本类似，首先初始化权重$w_0$，计算出在这条初始化的直线中，分类错误点的个数。然后对错误点进行修正，更新$w$，得到一条新的直线，在计算其对应的分类错误的点的个数，并与之前错误点个数比较，取个数较小的直线作为我们当前选择的分类直线。之后，再经过$n$次迭代，不断比较当前分类错误点个数与之前最少的错误点个数比较，选择最小的值保存。直到迭代次数完成后，选取个数最少的直线对应的$w$，即为我们最终想要得到的权重值。

Types of Learning

机器学习按照输出空间划分的话，包括二元分类、多元分类、回归、结构化学习等不同的类型。其中二元分类和回归是最基础、最核心的两个类型。

机器学习按照数据输出标签$y_n$划分的话，包括监督式学习、非监督式学习、半监督式学习和增强学习等。其中，监督式学习应用最为广泛。

按照数据处理的不同策略，机器学习可以分为batch,online, active。这三种学习类型分别可以类比为：填鸭式，老师教学以及主动问问题。

根据输入空间$X$类型不同，可以分为concetet, raw, abstract。将一些抽象的特征转换为具体的特征，是机器学习过程中非常重要的一个环节。

Feasibility of Learning

举一个例子，如果有一个装有很多（数量很大数不过来）橙色球和绿色球的罐子，我们能不能推断橙色球的比例$u$？统计学上的做法是，从罐子中随机取出$N$个球，作为样本，计算这$N$个球中橙色球的比例$v$，那么就估计出罐子中橙色球的比例约为$v$。

这种随机抽取的做法能否说明罐子里橙色球的比例一定是$v$呢？答案是否定的。但是从概率的角度来说，样本中的$v$很有可能接近我们未知的$u$。下面从数学推导的角度来看$v$与$u$是否相近。

已知$u$是罐子里橙色球的比例，$v$是$N$个抽取的样本中橙色球的比例。当$N$足够大的时候，$v$接近于$u$。这就是Hoeffding’s inequality：

$P\lbrack \vert v-u \vert >\epsilon \rbrack \le 2exp(-2\epsilon^2N)$

Hoeffding不等式说明当$N$很大的时候，$v$与$u$相差不会很大，它们之间的差值被限定在$\epsilon$之内。我们把结论$v=u$称为Probably Approximately Correct (PAC)。

下面，我们将罐子的内容对应到机器学习的概念上来。机器学习中hypothesis与目标函数相等的可能性，类比于罐子中橙色球的概率问题；罐子里的一颗颗弹珠类比于机器学习样本空间的$x$；橙色的弹珠类比于$h(x)$与$f$不相等；绿色的弹珠类比于$h(x)$与$f$相等；从罐子中抽取的$N$个球类比于机器学习的训练样本$D$，且这两种抽样的样本与总体样本之间都是独立同分布的。所以呢，如果样本$N$够大，且是独立同分布的，那么，从样本中$h(x)\ne f(x)$的概率就能推导在抽样样本外的所有样本中$h(x)\ne f(x)$的概率是多少。

映射中最关键的点是讲抽样中橙球的概率理解为样本数据集$D$上$h(x)$错误的概率，以此推算出在所有数据上$h(x)$错误的概率，这也是机器学习能够工作的本质，即我们为啥在采样数据上得到了一个假设，就可以推到全局呢？因为两者的错误率是PAC的，只要我们保证前者小，后者也就小了。

这里我们引入两个值$E_{in}(h)$和$E_{out}(h)$。$E_{in}(h)$已知，表示在抽样样本中，$h(x)$与$y_n$不相等的概率；$E_{out}(h)$未知，表示实际所有样本中，$h(x)$与$f(x)$不相等的概率是多少。同样，它的Hoeffding’s inequality可以表示为：

$P\lbrack \vert E_{in}(h)-E_{out}(h) \vert >\epsilon \rbrack \le 2exp(-2\epsilon^2N)$

该不等式表明，$E_{in}(h)=E_{out}(h)$也是PAC的。如果$E_{in}(h)\approx E_{out}(h)$，$E_{in}(h)$很小，那么就能推断出$E_{out}(h)$很小，也就是说在该数据分布$P$下，$h$与$f$非常接近，机器学习的模型比较准确。

一般地，$h$如果是固定的，$N$很大的时候，$E_{in}(h)\approx E_{out}(h)$，但是并不意味着$g\approx f$。因为$h$是固定的，不能保证$E_{in}(h)$足够小，即使$E_{in}(h)\approx E_{out}(h)$，也可能使$E_{out}(h)$偏大。所以，一般会通过演算法A，选择最好的$h$，使$E_{in}(h)$足够小，从而保证$E_{out}(h)$很小。固定的$h$，使用新数据进行测试，验证其错误率是多少。