Lec2-4 是非题（二分类）——非线性可分
在有噪声的数据中学习
机器学习的输入数据并不一定完全是按照完美目标函数来的，在收集数据的过程中可能会有噪声，例如顾客提供假资料，业务人员出错等等。
现在在原来机器学习流程的基础上，给数据加上噪声：
噪声容忍的分割线
数据是否线性可分是未知的，那么能不能证明说，在不确定数据是否有噪声，是否线性可分的情况下，仍然能够保证 g 和 f 很接近呢？
可以假设噪声相对于正常数据很小（否则学习噪声比学习 f 更有效），既然不知道能否找到不犯错误的线，那么退而求其次，可以找一条在能够承受的迭代次数中，犯错误最少的线。
在所有可能的W中，找到一个犯错误总和最小的W。这是一个np hard问题，目前没有很有效率的演算法能完美解决这个问题。
PLA变型——Pocket Algorithm口袋算法
不过，前人设计了一些还不错的演算法，可以看作PLA的变型，来找到一个“差不多很好”的线（'approximately good‘ g）。
Pocket Algorithm口袋算法 保持把一条目前最好的线放在口袋里，然后不断迭代，遇到更好的线就更新口袋中的线。
Pocket Algorithm和PLA过程非常类似：
Pocket Algorithm V.S. PLA
1. PLA是遇到有错的点时进行修正迭代；
Pocket Algorithm是在选取有错的点时加入了随机，力求看全数据找到更好的线。
2. Pocket Algorithm 得到一条新的分割线时，会去算总的错误数，然后与口袋中已有的“目前最好”的线比较，保证口袋里的线始终是目前犯错误最少的。
3. PLA是找到一条不犯错误的线即停下；
Pocket Algorithm假设资料可能并非线性可分，有两种停止机制：
①当前犯错足够小；
②迭代次数足够大。
算法退化
如果数据真的线性可分，Pocket Algorithm则损失了时空上的性能：
①存pocket中的最优解；
②每轮更新后，对于所有点都去算分割线是否分对。
而PLA只找出一个犯错误的点即可修正。
