When Can Machines Learn? ——part2
这部分让机器学会回答判断题，是非题(即yes/no)
主要内容：
1.Porceptron Hypothesis Set
把收集的资料换一个角度看待，用向量来表示，并且每一个维度都有对应的权重，以此来给每个客户'评分'，通过计算分数与门槛的差值来判断要不要给信用卡。
之前提到y是我们想要的结果，用-1,1来代表
wi是权重
为了方便书写，将式子简化（要记住它的等价关系）
如果在二维平面上理解：
x：平面上各个点
y : 标签(-1,1)
h : 想要得到的线（在多维下就是平面）
perceptrons 就是线性的二元分类器
2.Porceptron Learning Algorithm (PLA)
第一个模型PLA
之前提到机器学习，喂给机器D，经过ML(A on H)得到g(越接近f越好),所以我们的目标是g,而机器在运行时可能会得到很多种线（把它们放在一个集合H）,我们要做的就是在H中选最好的线
那么问题来了，H是无限大的，不可能遍历所有线然后慢慢选解决思路 :
先随意选个g,然后只要不断修正错误（x不对应我们想要的y),就可以慢慢修正到一条最好的线
现在用g0的权重向量w0来代表g0,从g0开始，不断修正犯错的点，最后找到一条最好的线
步骤:
1>每一轮都找一个错误wt (wt代表了一个g)
1>修正错误通过wt+yn(t)xn(t) (这个公式可以理解为，yn(t)=1或者-1,所以
如果原本yt=1,而现在却等于-1,只要在原来的基础上修正wt+yn(t)xn(t)就可以到1的那一边了）
want +1,but 1 =>w与x离太远了,wt+yn(t)xn(t)让w靠近x
反之亦然
直到没有错误了
推导过程如图:
3.Gruarante of PLA
这部分证明PLA算法是可行的。
第一个不等式是yn的等式两边乘以yn,也就是等价于yn的平方，自然min也会>0
证明两个向量是不是越来越接近在数学上可以做内积，内积越大越接近，可以看出，wt和wf是越来越接近的
虽然，内积是越来越大没错，可以还有可能是长度关系，导致的增长，接下来就证明是不是和长度有关
可以看出wt增长是很慢的，最大不过增加了xn
还有一点要考虑，PLA会停下来吗？
上面证明了，wt增长很慢，所以长度不怎么影响，那么就看角度变化
看两个正规化的内积，最后一个式子代表了wt与wf之间的余弦值，最大是1，所以一定会停下
式子推导过程:
4.Non-Separable Data
总结PLA的优缺点：
优点:简单易懂，在很多地方都可以用
缺点:假设PLA是可以停止的，其实某种程度来说并不知道会不会停下起来，因为不知道f未知，也就是说，不知道假设对不对；以及不知道什么时候会停下来。
如果遇到线性不可分的问题怎么解决？
既然无法找到错误为0的线，那就找错误最少的线
然而这是个NP-hard问题，无法求解
对于非线性的问题，把PLA做下修改，用一个口袋装目前最好的线w,先初始化w0,然后修改错误，如果现在wt+1比wt的错误更少，那就取wt+1放到口袋里，得到新的线，可以发现口袋里的w一定是最优秀的线，最后取这个线作为g
与PLA的区别是：原来是追求0错误的完美线，现在很无奈，非线性可分，那就找错误最少的优秀线，用了贪心算法思想，跑了足够多次，看了足够多的线，选一个最优秀的线。
5.Summary
这个章节介绍了一个简单的算法PLA,现在机器能回答判断题了:p
以上:D
注明:以上图片都来自Cousera台大林轩田老师的《机器学习基石》哦 QwQ
