感知机

感知机

感知器假设集（Perceptron Hypothesis Set）

感知器算法: $h(x)=sign((\sum_{i=1}^dw_ix_i)-threshold)$

对上面的公示进行变形，将threshold作为偏置，纳入 x 中， $x_0=+1$ ;

$h(x)=sign(W^TX)$

每一个不同的W代表了算法中的一个hypothesis.

PLA 感知器学习算法

要从 hypothesis set 中找到一个合适的 hypothesis g, 让 g 与目标函数 f 尽可能的相近。

PLA算法通过试错的方法实现模型的训练：

总共进行t轮的训练， t=0, 1, …

随机初始化 $w_0$ ;
将样本 $(x_{n(t)},y_{n(t)})$ 带入PLA学习机，如果：

$sign(w^T_tx_{n(t)})\neq y_{n(t)}$

那么，表示发生错误，需要对错误进行纠正。

修正错误：
$w_{t+1} \leftarrow w_t + y_{n(t)}x_{n(t)}$
$w$ : 代表分类线的法向量 $x_n$ : 是原点到 $x_n$ 的向量

当 $y_n = +1$ , 将 $w$ 的方向向样本 $(x_n, y_n)$ 的方向转动。
当 $y_n = -1$ , 将 $w$ 的方向向样本 $(x_n, y_n)$ 的反方向转动。
当不再出现错误的时候，训练结束。

PLA算法要能终止，要求训练数据集必须是线性可分的

$w_t$ 越来越接近 $w_f$

$w_f$ : 目标函数 f 对应的参数，因此对于任意一个样本，它都能正确的分类：
$y_{n(t)}w^T_fx_{n(t)} \ge \min_ny_nw^T_fx_n \gt 0$
衡量两个向量是否接近，可以用它们的内积，如果内积越小代表它们越不接近，相互垂直时为 0
$\begin{align} \begin{split} w_f^Tw_{t+1} &= w_f^T(w_t+y_{n(t)}x_{n(t)}) \\ &\ge w_f^Tw_t + \min_ny_nw_f^Tx_n \\ &\gt w_f^Tw_t + 0 \end{split} \end{align}$

$w_t$ 的增长速率不快

$w_t$ 每次的更新不超过离分割线最远的样本的距离

$w_t$ 的每次更新发生在有错误的时候：

$sign(w_t^fx_{n(t)}) \neq y_{n(t)} \Leftrightarrow y_{n(t)}w_t^Tx_{n(t)} \leq 0$

对于每一次更新后的结果：

$\begin{equation}\begin{split} ||w_{t+1}||^2 &= ||w_t + y_{n(t)}x_{n(t)}||^2\\\\ &= ||w_t||^2 + 2y_{n(t)}w_t^Tx_{n(t)} + ||y_{n(t)}x_{n(t)}||^2\\\\ &\le ||w_t||^2 + 0 + ||y_{n(t)x_{n(t)}}||^2\\\\ &\le ||w_t||^2 + \max_n||y_{n(t)}x_{n(t)}||^2\end{split}\end{equation}$

其中 $\max_n \Vert y_{n(t)}x_{n(t)} \Vert ^2$ 就代表了距离到分隔线最远的点的距离。

$\begin{equation}\begin{split} \text{start from w_0 = 0, after T mistake corrections,} \\ \frac{w_f^T}{\Vert w_f \Vert} \frac{w_T}{\Vert w_T \Vert} \ge \sqrt T * \text{constant} \end{split}\end{equation}$

$w_f^Tw_{t+1}$ 的内积是小于等于1的，再根据上面的式子，知道T不可能为无穷大，所以运算会终止。

Pocket 算法

算法步骤

随机初始化 w
进行 t 轮的学习， t = 0, 1, …
如果发生错误，按照 PLA 算法对 w进行纠正： $w_{t+1} \leftarrow w_t + y_{n(t)}x_{n(t)}$
判断对比纠正后的算法与之前算法的错误率，如果更好，者保留新的w_t+1, 否者保留之前的w。
运算足够多次之后停止运算。

Pocket算法是PLA的改进算法，用于解决线性不可分的数据集。 Pocket算法的运算量大：对于比PLA，在得到新的w_t+1，需要将所有数据集运算一遍，来获得错误率。