机器学习基石 2 Learning to Answer Yes/No

Perceptron Hypothesis Set

对于一个线性可分的二分类问题，我们可以采用感知器 （Perceptron）这种假设集。

这种模型可以用下面的表达式表示出来：

其中不同的向量 \(w\) 代表了不同的假设函数 \(h(x)\)，我们的目标是使用一些算法调整 \(w\) 的值，使得假设函数 \(h(x)\) 与我们要预测的函数 \(f(x)\) 尽可能的接近。

我们的想法是：如果 \(h(x)\) 与 \(f(x)\) 足够接近，那么它们作用在训练集 \(D\) 上的结果会是一样的，即对训练集中的 \(x\)，有 \(f(x) = h(x)\)。反过来说，如果对所有训练集中的 \(x\)，有 \(f(x) = h(x)\)，那么在一定程度上，我们可以认为 \(h(x)\) 与 \(f(x)\) 是接近的。

Perceptron Learning Algorithm (PLA)

这个模型中训练 \(w\) 的算法称为感知器算法（Perceptron Learning Algorithm），算法描述如下图：

思想是对预测错误的样本进行修正：

当 \(f(x)=y=+1\) 而预测结果 \(h(x)=sign(w^Tx)=-1\) 时，说明此时 \(w\) 与 \(x\) 的内积过小，夹角过大，需要让 \(w\) 靠近 \(x\)，因此将 \(w\) 改为 \(w+x=w+yx\);

当 \(f(x)=y=-1\) 而预测结果 \(h(x)=sign(w^Tx)=+1\) 时，说明此时 \(w\) 与 \(x\) 的内积过大，夹角过小，需要让 \(w\) 远离 \(x\)，因此将 \(w\) 改为 \(w-x=w+yx\);

反复修正预测错误的样本点直到所有训练样本都预测正确。

一种可行的算法如下：

Guarantee of PLA

能使用PLA算法的重要前提是样本是线性可分的，即存在 \(w_f\) 使得 \(y_n = sign(w_f^Tx_n)\)，下面证明PLA算法是收敛的，即 \(w\) 能收敛到 \(w_f\)，即算法能停止下来。

1. \(w_f\) 与 \(w_t\) 的内积会单调递增
   
   
2. \(w_t\) 增长速度有限
   
   

以上两点可以推出：

算法更新次数\(T \leq \frac{R^2}{\rho^2}\)

其中\(R^2 = \max \limits_{n}\{f(x)\}, \quad \rho = \min \limits_{n} y_n \frac{w_f^T}{||w_f^T||} x_n\)

总结以下PLA算法

Non-Separable Data

对于数据有噪声时，学习的过程发生了一点改变：

对感知器模型来说，此时可能无法使所有样本都正确分类，因此学习的目标从 \(\arg \limits_{w} y_n = sign(w^Tx_n)\) 变成了 \(\arg \min \limits_{w}\sum {[[y_n \neq sign(w^Tx_n)]]}\) (NP-hard 问题)

于是PLA算法可以改进成Pocket算法：