Lecture 2: Learning to Answer Yes/No

Lecture 2: Learning to Answer Yes/No

（二分类问题）

一切截图均来源于课程讲义

内容小结：

1. 线性可分的二分类问题中，构造假设集（Hypothesis Set)，使用PLA（感知器学习算法），寻找final hypothesis函数g;
2. 证明PLA在线性可分时，会最终停止，找到最优划分线（即final hypothesis）
3. 在不知是否线性可分的情况下，改进PLA，采用Pocket Algorithm(口袋演算法)，找到一条犯错误最少的线，但该方法速度比PLA慢

2.1 Perceptron Hypothesis Set

在银行要不要给信用卡的实例中：

把customer用向量表示，用加权总分来决定要不要给信用卡

判定结果仅为+1或者-1：通过sign函数实现
此处h(x) : 感知器perceptron<->线性分类器，由w和门槛threshold决定

暂不考虑恰好在门槛上的情况（不重要）

把门槛值threshold作为特殊的w：可以把h(x)表示为向量乘积

2.2 Practical Implement of PLA

PLA：Perceptron Learning Algorithm 感知器学习算法 “知错能改”
从g0开始，不断进行修正权重w，直到没有错误才停下

小问题：
formula2: 错误被修正，而不是完全改正！所以修正后不一定等于yn
formula3: 体现出经过每次修正后，h(x)都要比之前更加正确

2.3 Guarantee of PLA

linear Separability （线性可分）：只有在这种情况下，PLA才会停下来

（PLA会停下的证明详见课件）
ps：两个向量内积越大->两个向量越相似接近

2.4 More about PLA

优点：PLA实现简单快速，可以在任意维度使用
麻烦：需要先假设线性可分，使PLA可以停止；不知道PLA多久才能停

Noisy Data

找一条“犯错误最少的”线（不能找到完美的线） --NP难

解决办法->Pocket Algorithm(口袋演算法)
随机寻找错误，得到心弦，如果新线犯错误更少，就用新线代替旧线
Pocket Algorithm ：比PLA更加缓慢
- 要记忆以前的线
- 要把所有数据全都遍历一次，才能做一次取舍