这一讲主要介绍了第一个二类分类算法——感知学习算法(Perceptron)。感知学习最早是Rosenblatt于1957年提出的，这个算法可以算是开创了机器学习的先河。1962年，Novikoff证明了感知学习算法在线性可分数据集上可以在有限步内达到收敛。这一讲主要介绍了感知学习算法及其收敛性，感知学习算法在不可分数据集上的变异算法——口袋算法(pocket algorithm).

1、A Simple Hypothesis Set

上一讲中，我们虽然得到了机器学习的整体框架，但是并没有确定假设集(Hypothesis Set)并没有规定。因此，对于机器学习问题来说，我们应该怎么去选取什么样的假设集$H$？是取有限元素的集合还是无限多的元素？

对感知假设来说，假如存在一个数据样本$x=(x_1,cdots,x_d)$,二类分类算法的目的是求取一个权向量$w$，使得$left{begin{array}{cc} textrm{ y = 1 (corrct)} & textrm{if} sum_i^d w_i x_i > textrm{threshold} \  textrm{y = -1 (wrong)} & textrm{if} sum_i^d w_i x_i < textrm{threshold}end{array}right..$

由此，可以得到二类分类问题的判别函数$h(x)=textrm{sign}(w^T x -b) = textrm{sign}(hat{w}^T hat{x})$。

2、Perceptron Learning Algorithm

一旦确定了假设集$H$，剩下的问题就是如何选择一个$gin H$，使得$g approx f$。对于这个问题，通常的做法是使得在训练数据$D$上使得$g approx f$，这就是经验最小化原则，因为机器学习需要从数据中获取技能，而训练集是目前唯一可以利用的现实数据。但是，这个问题很难，尤其是在$H$元素很多的时候。

感知学习算法假设集$H$是$d$维的平面，其通过在训练集$D$上的错误来逐步修正和完善自己，这是典型的从错误中学习的例子。

其算法的主要过程如下：

 for $t=1,2,3,cdots$

• find a mistake of $w_t$ called $(x_n,y_n)$    sign$(w_t x) neq y_n$

• (try to) correct the mistake by

       $w_{t+1}leftarrow w_t + y_n x_n$

    until no more mistakes

 return last $w$ (called $w_{PLA}$) as $g$.

3、Guarantee of PLA

 假设$w_f$是最佳的权值向量，上述算法没迭代一次，$w_t$就与$w_f$更接近一点。1962年，Novikoff证明了感知学习算法在线性可分数据集上的收敛次数$k$满足：$k leq frac{R^2}{rho^2}$，其中$R=max |x_i|, rho = min |w^T x_i|, i=1,cdots, n$, $n$是数据样本的个数。

4、Non-Separable Data

当数据被噪声污染了之后，变得不是线性可分了，此时感知学习算法就不能保证会停止了，因为总是存在错误。此时，如果假设噪声水平很低，我们仍然可以认为$y_n = f(x_n)$在绝大多数情况下成立，于是，我们要找的一个$g approx f$使得在大多数情况下成立。我们希望找的一个$w_g$使得下式成立：

$w_g leftarrow argmin_w sum_{i=1}^{n}[y_n neq textrm{sign}(w^T x_n)]$   (NP-hard to solve, unfortunately).

Pocket Algorithm

for $t=1,2,3,cdots$

• find a mistake of $w_t$ called $(x_n,y_n)$    sign$(w_t x) neq y_n$

• (try to) correct the mistake by

       $w_{t+1}leftarrow w_t + y_n x_n$

• if $w_{t+1}$ makes fewer mistakes than $hat{w}$, replace $hat{w}$ by $w_{t+1}$
  

    until enough iterations

 return $hat{w}$ (called $w_{POCKET}$) as $g$.

----------------------------------------------------------------------------

我个人认为，感知学习算法可以算是机器学习的第一个算法，无论是后来的神经网络(NN)模型还是支持向量机(SVM)中都可以看成是它的扩展。若想对该算法有一个全面的了解，可以参考Widrow等1990年的文献[1]。

[1]   Widrow B, Lehr M A. 30 years of adaptive neural networks: perceptron, madaline, and backpropagation[J]. Proceedings of the IEEE, 1990, 78(9): 1415-1442.