机器学习基石第二节 学习笔记

Learning to Answer Yes_No

第一个算法 PLA（Perceptron Learning Algorithm）



1、算法讲解

```

h(x) = sign(E(i=1 -> d)WX - threshold)

w 权重 x 向量的元素，即特征， E替代求和符号（矩阵内积）， threshold 门槛值，yes no 的判断标准

h 即假说

perceptron 感知机，识别机

h(x) = sign(E(i=1 -> d)WX + （-threshold）+（+1）)

h(x) = sign(E(i=1 -> d)WX + （w0）+（x0）)

h(x) = sign(E(i=0 -> d)WX) 降门槛值吸收到前面的运算中

h(x) = sign(WX) 此时w 和 x 均为向量，此时运算即简化为向量内积了

```





可以看到在二维图中表示时，h(x) 实际上是一条直线，含义即为隔开不同y（yes or no）的直线

perceptrons（感知机）《=》linear



资料x->y 由目标函数f 产生，首先要保证在这些看到的资料x->y中，假设函数g可以预测的很好，这个并不容易，因为假设集H 是无限大的，所以就可以在原有线上做修正





WTX就是向量的内积，大于0表示向量夹角为锐角

修正过程即 wt+1 = wt + yn(t)xn(t)

修正直到所有数据集在假说中成立





2、心得总结



在感知机里，w的定义是超平面的法向量，感知机的公式w*x+b=0表示的就是那个超平面。wt是法向量的第t次修正的结果，wt最终确定，作为法向量形成分割面的时候，wt和所有正确的点乘积为正，与错误的点乘积为负。



3、练习题：





解法：wt+1 （ynxn） = wt （ynxn）+ ynxn * ynxn，左右同乘ynxn



4、PLA终止条件





PLA在能够符合所有资料时会停下来，必要条件D使得w能够不犯错从而停下来，这样的D叫线性可分



5、收敛性证明，也即PLA会停







这两页PPT比较复杂，其实就是在利用条件证明：





6、PLA找出一条较好的线

优缺点：



不知道何时会停，不一定能停，即数据并非线性可分。



为了应对Noisy，我们不可能得到完美的直线（可能是一个NP问题），那么怎么衡量当前得到的直线能够满足要求呢？凭直觉，我们知道如果当前直线犯错越少越好（对所有data），于是有了下面的改进算法，Pocket PLA，本质上就是在改错的时候多做一步 -- 判断当前改正犯的错是否比之前更小，也就是贪心选择