机器学习基石 第二讲

感知机

感知器假设集（Perceptron Hypothesis Set）

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

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

$$h(x)=sign(W^{T}X)$$

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

PLA 感知器学习算法

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

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

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

1. 随机初始化 $$w_0$$;

2. 将样本 $$(x_{n(t)},y_{n(t)})$$ 带入PLA学习机， 如果：

$$sign(w_t^T{x}_{n(t)})\ne y_{n(t)}$$

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

3. 修正错误：

   $$$$ $$\text{\$\$w\$\$: 代表分类线的法向量 \$\$x\_n\$\$: 是原点到 \$\$x\_n\$\$ 的向量 }$$

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

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

$$w_t$$ 越来越接近 $$w_f$$

• $$w_f\$\$:\mathrm{目}\mathrm{标}\mathrm{函}\mathrm{数}f\mathrm{对}\mathrm{应}\mathrm{的}\mathrm{参}\mathrm{数}，\mathrm{因}\mathrm{此}\mathrm{对}\mathrm{于}\mathrm{任}\mathrm{意}\mathrm{一}\mathrm{个}\mathrm{样}\mathrm{本}，\mathrm{它}\mathrm{都}\mathrm{能}\mathrm{正}\mathrm{确}\mathrm{的}\mathrm{分}\mathrm{类}：$$

  y_{n(t)}w^T_fx_{n(t)} \ge \min_ny_nw^T_fx_n \gt 0

  $$$$ $$\begin{array}{r}\begin{array}{rl}{w}_f^T{w}_{t+1}& =w_f^T(w_t+y_{n(t)}{x}_{n(t)})\\ & \ge w_f^T{w}_t+\underset{n}{min}{y}_n{w}_f^T{x}_n\\ & >w_f^T{w}_t+0\end{array}\end{array}$$

$$w_t$$ 的增长速率不快

$$w_t\$\$\mathrm{每}\mathrm{次}\mathrm{的}\mathrm{更}\mathrm{新}\mathrm{不}\mathrm{超}\mathrm{过}\mathrm{离}\mathrm{分}\mathrm{割}\mathrm{线}\mathrm{最}\mathrm{远}\mathrm{的}\mathrm{样}\mathrm{本}\mathrm{的}\mathrm{距}\mathrm{离}\ast \$\$w_t\$\$\mathrm{的}\mathrm{每}\mathrm{次}\mathrm{更}\mathrm{新}\mathrm{发}\mathrm{生}\mathrm{在}\mathrm{有}\mathrm{错}\mathrm{误}\mathrm{的}\mathrm{时}\mathrm{候}：$$

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

$$\ast \mathrm{对}\mathrm{于}\mathrm{每}\mathrm{一}\mathrm{次}\mathrm{更}\mathrm{新}\mathrm{后}\mathrm{的}\mathrm{结}\mathrm{果}：$$

\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}

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

\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}

$$\text{\$\$w\_f^Tw\_{t+1}\$\$ 的内积是小于等于1的，再根据上面的式子，知道T不可能为无穷大，所以运算会终止。 \#\# Pocket 算法 **算法步骤** 1. 随机初始化 w 2. 进行 t 轮的学习， t = 0, 1, ... 3. 如果发生错误，按照 PLA 算法对 w进行纠正：\$\$ w\_{t+1} leftarrow w\_t + y\_{n(t)}x\_{n(t)}}$$

4. 判断对比纠正后的算法与之前算法的错误率，如果更好，者保留新的w_t+1, 否者保留之前的w。
5. 运算足够多次之后停止运算。

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