《机器学习基石》—感知机算法

基本思想是，把特征的线性加权值作为一个分数，根据这个分数与一个门限值的关系来进行分类：

我们加一个特征x0等于1，门限值就可以放到w里面去，得到更简单的形式：

这就是感知机模型，对应一个分离超平面。

 

2 如何来学习感知机

“知错能改”原则：找到一个误分类点，就尝试去修正它。具体的修正过程如下：

当找到一个误分类点时，如果y本来是+1，则说明现在的w与x的内积为负，w与x的夹角太大，应该这样更新：

如果y本来是-1，则说明现在的w与x的内积为正，w与x的夹角太小，应该这样更新：

总结起来，就是对于误分类点：

因此，标准的感知机学习算法可以总结如下：

直到不包含误分类点，算法停止。

 

3 证明PLA算法在线性可分的数据集D上一定能收敛

（证明过程暂时没看懂）

4 pocket 算法

上面的PLA算法往往不能用于实际的数据集，因为实际数据集是包含噪声，往往不满足线性可分，那么上面的算法就不会停止。因此我们应该允许PLA犯一些错，但是应该把犯错最小化，问题表述为：

不幸的是，上面的问题是一个NP-Hard问题，因此我们用一个简单的贪心算法来求解它的近似解：

 即每次只有当wt+1犯错更少时才用它来代替wt。

 5 pocket与PLA的对比

pocket更慢，因为每次都要对整个数据集来检查是不是犯错更少：