Lecture 2：Learning to Yes/No

Perceptron Learning Algorithm (PLA)

现在我们把看作是所有可能的感知机(Perceptron),把看作其中的一个感知机假设。
那么，我们想要做的就是让尽可能的接近target function，理论上讲在数据集上，是成立的，也是必要的。
但是（感知机假设）是无限的，那要怎么做呢？

idea: start from some (represent by its weight vector ),and 'correct' its mistakes on

以下是PLA流程：
For t = 0，1，...

1. 找到被划分错误的一个错误点，使得
2. 令 ，尝试去修正这个错误。
   
   ... 直到没有分错的点为止。此时令
   举例说明：
   

---

Guarantee of PLA

首先讲一下线性可分(Linear Separability)的概念：

• if PLA halts(意味着没有错误点了，这是必要条件)，allows some to make no mistakes
• call such Linear Separability
  也就是说，Linear Separable exits perfect such that
  假设总是线性可分，但是PLA一定会停下来吗？
  实际上，Gets More Aligned with
  我们可以简单证明一下：
• perfect hence every correctly away from line:
    
• update by any
    
         
         

并且， does not grow too fast
Because changed only when mistake
mistakes 'limits' growth,even when updating which 'longest'

     
     
     

Note:start from ,after T mistake corrections：

---

Non-Separable Data

上面讲述了PLA基于线性可分数据的过程，而在现实生活中，并不总是separable的。那么，我们要怎么做才能使得成立呢？
如果数据集如下图所示，我们永远不可能画一条直线完全分开和样本。

但是，显然，noise数据不会太多（太多了就没意义了，对这份数据集而言），那么我们可以假设 在一般情况下是成立的，即忽略噪点。那么，在这份数据集 上， 也是成立的。
所以，现在我们要做的，就是找一条线，使得错误点数量尽可能少。
即
不幸的是，这是一个NP难题。我们只能去找一个近似的符合条件的g。
这里我们引入Pocket算法 modify PLA by keep best weights in Pocket。
initialize pocket weights in ,
For t = 0，1，...

1. 找到被划分错误的一个错误点，使得
2. 令 ，尝试去修正这个错误。
3. 如果划分的错误点比少，那么replace by
   ... 直到迭代到足够次数为止。
   此时令