《机器学习基石》是国立台湾大学林轩田讲授的一门课程，课程的续集是《机器学习技法》。《机器学习基石》是网上热荐的一门机器学习课程，相关资源可以在youtube找到，也可在评论区索要云盘链接。本文主要是我学完一遍基石&技法后的笔记梳理，如果存疑请以原课程讲授内容为准，欢迎讨论~[注]本文仅适用于帮助复习，不适用于代替视频课程。

基石分为4个部分，分别为什么时候机器能够学为什么机器能够学习，机器是如何学习的，怎样让机器学得更好，什么时候机器能够学习？本文主要梳理前两部分。

一、什么时候机器能够学习？

1 关于机器学习

1.1 不严格定义

人通过观察习得技能，机器模仿人，通过观察(数据)来获得技能(某种表现的增进)，例如说，机器通过观察股票数据来提高投资的收益。

1.2 PK传统方法

识别一棵树，传统方法是找到树的定义，但没人能讲出它的具体定义。而机器学习方法则比较简单，只需喂给机器足量的树，让它自己找出其中的规律学会识别，这个规律是抽象的难以描述的，否则直接用传统方法就好了。

1.3 机器学习的必要条件

有规则（预测下一个婴儿是否在奇数分钟哭是没有意义的），但不明确（判断一张图里面是不是有一个圆直接用传统方法来做就可以了）。有相关资料（预测地球会不会在核战争中毁灭是不可行的，因为我们没有”核战争-地球是否毁灭”的资料）。

1.4 机器学习的应用

食衣住行育乐，生活中的方方面面。例如电影推荐系统(详见技法)。

1.5 机器学习的符号化图示(5个元素)

机器学习符号为数据集D，蕴含了未知的目标函数f。演算法A从所有假说集H中选一个最好的假说函数g，希望g和f的表现能尽可能的相似。(假说集长什么样子马上会见到) 

1.6 机器学习和人工智能、统计学的关系

人工智能如”下棋”，可以用传统方法(定义规则树)也可以用机器学习让机器自己从资料找到规律，所以说机器学习是人工智能的一种实现方式。

统计学也是用资料推断未知，它更注重证明，为机器学习提供了非常多的工具，下面会见到的。

2 二元分类

2.1 一种简单的假说集:Perceptron感知器

可以看到这是一个输出为+1或-1的二元分类函数

2.1.1 Perceptron的向量形式(更简洁)

我们将阈值收入W向量从而使向量形式更加简洁

2.1.2 Perceptron的图形表达

这里取X只有2个维度(x,y)或（x1,x2），这样一来的假说函数刚好是条直线所以这样的感知器又称线性分类器。图中的点是一个个数据点((x1,x2),z)，其中y以o或×的形式画出。图中的底色则表示感知器的预测(eg.将蓝色区域的任意一个点代入感知器将得到+1的结果)，可以看到左图的分类是存在问题的（部分x在蓝底区域，部分o在红底区域），而右图的感知器则正确。这两个感知器的w不同，构成了假说集中的两个假说，显然，我们的演算法应该选择第二个感知器当作g，因为这个g与f长的最像。

2.2 PLA算法(Perceptron Learning Algorithm)

上面我们提到最好的一条线g，事实上在这张图上我们能做出无数条线出来，我们怎么找到这个最好的线出来呢？如果最好太难，那我们就用迭代法，不断地改善使它越来越好从而做到最好，这个思想产生的就是PLA算法(2步)。

从2.1我们已经知道线的不同是w的不同造成的，PLA算法每次选一个错误点，然后往正确的方向更新w。它的图像表达如下所示：

上图wx=|w||x|cosα，α＞90°，故x的预测是-1与y=+1不符，故修正(将w向x旋转一半)，下图同理。

2.1 Cyclic PLA

顾名思义，Cyclic PLA绕一圈把所有点都查一遍。[注]t=0时找的任意点都满足错误点的定义

2.2 PLA真的有效吗？

2.3 PLA能停下来吗，最后一定无错吗？

如果PLA能够停下来，那一定存在一个w在D不犯错，我们称这样的D是线性可分的。

那如果D线性可分，PLA就能够停下来吗？

这里设wf是完美直线的权重，即任何一个点都是正确的点(yn与wtxn同号，乘积>0)而任何一个”错误”点都是正确点。第二个式子证明了wt在不断逼近wf，PLA能够停下来！不过还要排除向量变长的影响。

这里证明了wt的长度最多增长离远点最远的数据点的距离的平方，不会增长太快。故wt真的在不断逼近wf，PLA能够停下来！事实上，wt和wf的距离（两个矢量之间的角度）的余弦如下所示，随着T的增大不断接近1：

关于constant的计算：

2.4 PLA的优缺点

优点是容易实现，适用于任意维度。缺点是我们无法确定D是不是线性可分的，也不确定到底要多久才能停下来，因为ρ的计算依赖于wf，wf是我们的目标权重这在一开始是不知道多少的。

2.5.带杂讯的资料

左图蓝底中的x可以认为是杂讯，解这类问题最直观的想法是找一条犯错最少的线，但这是一个NP-hard问题，几乎不可能解出来。

2.6.口袋演算法Pocket Algorithm

实际上是PLA+判断是否接受更新(放入口袋)(这一步比较花时间)

3.机器学习的种类

二元分类，多元分类，回归(逻辑回归/线性回归)，结构化学习(输出句子结构/蛋白质结构等)

监督，无监督（分群，密度估计），半监督(少量标注)，增强式(隐式标注,奖惩制,eg广告系统)

批学习，线上学习(eg.垃圾邮件分类器来一封学一封)，主动学习(主动挑出最具价值的样本)

具体特征，生特征(简单的物理意义eg.手写数字需转”对称性-密度”图)，抽象特征(几乎没有物理意义,如”学号”,需提取出它的偏好等才有意义)

4.机器学习的可行性（训练出来的模型真的可以用于预测吗？）

根据Hoeffding不等式，随机独立大量抽样的预测结果大概差不多是对的(PAC)

把橙球当作Perceptron中的x，绿球当作o，得机器学习如果能对sample正确分类，大概差不多也可以对整个bin正确分类

实际ML会评估多个假说函数h

然后从中选一个最好的。[注]抽样只负责选球，颜色是h染上去的

如果抽样不符合坚持独立随机原则，就有可能人为选到”magic coin”，那样无法保证大概差不多是对的(PAC)，这种样本称为“BAD”样本，可以证明抽到BAD样本地概率很低。

5.所以什么时候机器能够学习呢？

只要随机独立抽样，我们就可以选一个在sample犯错最少的h当作g

训练出来的模型真的可以用于预测，机器学习是可行的。

二、为什么机器能够学习？

1.上式M能bound住吗？

上述公式中，如果M是无限大就又不行了。

假设M是无限大的，那么，

式子右边就是无限大，而左边是个小于1的概率。这说明右边明显过度估计了坏事情发生的概率，这是因为右边把所有h都当作独立事件，而实际上h之间很可能是有交集的。所以更准确的做法是用样本量为N时h的种类数effective(N)代替h的个数M。

如上图，3个点的二分类问题，effective(N)最大=8，当3点共线的时候则=6。

记这个最大的数为成长函数值mH(N)，即mH(3)=8。对于二维二分类问题mH(N)≤2N

当上式不能取”=”时，我们称这时的N为break point，打破了mH(N)的指数增长

对于二维二分类问题，它的最小break point是4，H无法shatter N=4这种情况：

 N=4时，Dichotomy H的成长函数mH(N)=14<16)

对于其它H有以下结论：

对于1D perceptrons和positive intervals，它们的k都是3

对于相同k不同H，记最大的mH(N)为界限函数B(N,K)，则B(N,K)一定=2N-1

可以得到下表

其中B(4,3)是枚举法列出来的

取其三维，则为

可见无法shatter任何三点，故，橙区则无法shatter任何两点，故，

化简可得

可以证明其实是=，如B(5,4)=26=1+3+7+15。

所以2D perceptron可以进一步被bound住为B(N,4)，即

现在考虑用mH(N)去取代下式中的M

对于左边，由于Eout有无限种可能，我们将Eout改写成对于测试集的E’in，

如图，如果Ein很糟糕，有大于1/2的概率抽到对于Ein很糟糕的E’in

(抽中离Eout很近的E’in并选中h使Eout隔ε的Ein)的概率≤(选中h使E’in隔ε/2的Ein)的概率

整理并用mH(N)进行放缩，

2N=在D中的N个点+在D’中的N个点

进一步用hoeffding进行放缩则为：

综上我们得到了VC bound

当存在break point时，

可以进一步放缩为

说明M能够被bound住，只要数据量N够大，存在break point，我们还是能机器学习

2. VC Dimension

将上式k-1定义为dvc，物理意义：整个D中能被H shatter的最大点数

则有

2.1高维perceptrons的dvc

故高维perceptrons的dvc=d+1

2.2 dvc的形象化解释(机械学科中的自由度)

2.3 dvc对模型复杂度的惩罚

Ω称为对模型复杂度的惩罚，dvc越大，模型越复杂，Eout上限越大

dvc应该适可而止，使Eout做到最小

2.4 dvc对样本(量)复杂度的影响

导致理论和实际采用的样本量差距悬殊的原因时VC bound一路的推导都在放缩

dvc越大，需要的样本量就越大。

综合2.3 2.4可以知道dvc不是越大越好，不要一昧追求最强的H

3.杂讯与误差

3.1杂讯

之前证明VC bound时，同理可证当杂讯服从某分布的时候，VC bound仍然有效，即

所以即使存在某分布的杂讯，机器仍然能够学习，能够保证Ein接近Eout

其中P(y|x)称为”目标分布”，区别于没有杂讯时的f(x)目标函数，

图中最理想的预测是o(0/1误差)，杂讯等级是0.3

3.2误差

误差函数的选择对演算法A会选出一条怎样的h作为g很重要

上图采用0/1误差时会选最大目标分布作为最理想预测，

采用平方误差则会计算出所有分布的加权平均值作为最理想预测

3.2.1误差成本

对于CIA，如果错误的指纹被识别为正确则要付出1000的成本。

对于加权分类问题，之前的PLA算法任然有效，因为PLA跑完Ein=0，和成本无关

而口袋算法需要考虑成本对误差的影响，x的成本是1000=做错1个x就认为做错1000个x，故只需将点x复制1000倍即可，

或者不复制，只需令口袋算法的第一步(查改错)时以1000倍的概率检查x点。

3.2.2不平衡样本

上例样本极其不平衡，x极少，o极多，导致h(x)≡+1被认为是个不错的结果

对于不平衡样本，需要更加小心地设置误差成本。

4 所以为什么机器能够学习呢？

这是因为并不是任意数量的资料都能被shatter，M能够被替换掉。无论资料有没有杂讯，P(BAD)都能被VC bound住。即使资料有杂讯，我们也能够用加权口袋演算法进行分类。