When can machines learn? (illustrative + technical)
机器学习的过程就是 learning algorithm A 从两个输入：数据 data 以及算法集合 hypothesis set 中找到一个 hypothesis g，使得 g 与真实的 target function f 最接近，这节课的重点就是学习一个具体的 hypothesis H。
Perceptron hypothesis set
一个简单的 Hypothesis Set: Perceptron: 如果决定授权信用卡，则 h(x) = +1， 如果不授权信用卡，则 h(x) = -1.
从上图中可以明显看出，一个具体的 h，与各个权重 w 以及设定的阈值 threshold 有关。这样的 h 在历史上被称作感知器 perceptron。这些字的来源由早期研究类神经网络而来。
其向量的表示为：
以2维的向量为例，h 的具体样子为:
从几何的角度讲，感知器 perceptron 实际上就是平面上的一条条线，因此又被称作 linear classifiers。即：
perceptron <=> linear classifiers
perceptron learning algorithm (PLA)
上一节，我们了解了一个可能的 H 的样子，也就是平面上所有的线(或者是高维空间里面的一个平面)。现在的问题是，如何设计一个算法，从所有的线 H 里面选出一条最好的线出来。
一条最好的线 g 的定义就是让 g ≈ f，但是难点在于 f 是未知的。唯一可以确定的是 data 是从 f 中产生的。所以，可以先让 g 在看过的 data 里面与 f 越接近越好，或者最好是一模一样(个人注释：over fitting)。
接下来就是在已经看过的数据 data 里面找一条线，这条线要能够正确的将 data 分开。难点在于 H 是无限的。
所以解决的方式是，任意找一条线，然后再依次去修正它(稍微移动一下)。
下面使用线的权重 w 来表示一条线，具体的算法过程为：
从 w0 开始，找到在数据 D 中分类错误的点(xn, yn)，即：
For t = 0,1,2…：
找到一个 wt 分类错误的点 (xn(t), yn(t)): sign(wTt) ≠ yn(t)
修正这个错误通过：wt+1 <– wt + yn(t)Xn(t)
一直修正到所以的数据都分类正确了。
修正的方法有两种：
- 一种是想要的符号是正的，结果是负的：这种情况表明， W 与 X 的角度过大(超过90度了)，因此修正方法为将 W 转到 W 与 X 的中间位置上来。
- 另一种是想要的符号是负的，结果为正的：这种情况表明，W 与 X 的角度过小(小于90度了)，因此修正方法为将 W 转到远离 X 的位置上去。
本质上， W 为分类器(直线) 的法向量：
修正的过程为：
两个问题：
- 修正的过程一定停下来吗?
- 停下来的线是 g ≈ f 吗？
Guarantee of PLA
PLA 停下来的条件：数据线性可分。
思考：假设数据D线性可分(linear separable)，PLA一定会停下来吗？
Wf：表示真实的线
Wt：表示调整的线
衡量Wt和Wf很接近，可以对两条线做内积。内积越大，两条线越接近。
即：linear separable D <=> 存在 Wf 使得：yn = sign(wTfxn)
还要处理向量长度的问题：
Non-Separable data
- 线性可分表明：Wt 和 Wf会越来越接近。
- 用错误修正表明：Wt 的长度会缓慢成长。
如果数据D并不是线性可分怎么办？
最好的分割线：在数据 D 上，犯错误最小的线。
贪心算法：新的线与旧的线进行对比。
