MLF Lecture 2 Perceptron Learning Algorithm

機器學習基石(Machine Learning Foundations)笔记第一弹

PLA 定义

用来解决线性可划分问题。 通过比较给定数据向量 X 与其权重向量 W 的加权和 \(\sum_{i=1}^d{w_ix_i}\) 与给定的阀值 therhold,决定是否同意某事(Y=1 or Y=-1) 即,\(h(x)=sign(\sum_{i=1}^d{w_{i}x_i} - threshold)\) 将上式中的(-threshold)看做 w0 ,附上(+1)的因子 x0 ,进一步变化:

\begin{aligned} h(x) &=sign ( _{i=1}d{w_ix_i}+{w_0}(+1)) \ &=sign({i=0}dw_ix_i) \ &=sign(W^TX) \end{aligned}

其中 WTX 为两个一维向量的内积。

PLA 过程

以二维向量为例,可以将\(h(x)=sign(w_0+w_1x_1+w_2x_2)\)括号内的部分看做一条关于 x 的直线。对每一个数据点\((x_1,x_2,\dots,x_n)\),不断修正当前直线的位置,直到所有点都满足 h(x)=yn(t)

解释

  • y = +1 时,\(\vec{W}\cdot\vec{X}<0\),需要减少\(\vec{W}\)\(\vec{X}\)的夹角
  • y = -1 时,\(\vec{W}\cdot\vec{X}>0\),需要增大\(\vec{W}\)\(\vec{X}\)的夹角

算法

For \(t=0,1,\dots\)

  1. find a \(\color{blue}{mistake}\) of \(\color{red}{W_t}\) called \(\color{blue}{\left(x_{n(t)},y_{n(t)}\right)}\)

    \begin{aligned} sign(w_t^Tx_{n(t)}) y_{n(t)} \end{aligned}

  2. (try to) correct the mistake by

    \begin{aligned} W_{t+1}W_t + y_{n(t)}x_{n(t)} \end{aligned}

… until \(\color{blue}{\text{no more mistakes}}\)

return \(\color{purple}{\text{last w (called }W_{PLA}\text{) as g}}\)

PLA 运行次数上限证明

仅当给定数据集线性可分时 PLA,PLA 可收敛。

线性可分(Linear Separability)

  • \(\color{darkorange}{if}\) PLA halts (i.e no more mistakes),
    \(\color{darkorange}{\text{(necessary condition) }} D\) allows some w to make no mistake
  • call such \(D\color{darkorange}{\text{ linear separable}}\)

此时,可以假设存在我们需要的那个函数代表的向量\(W_f\)满足:

\begin{aligned} y_n(t)=sign(W_f^TX_n) \end{aligned}

证明铺垫 1

\begin{aligned} y_{n(t)}W_f^TX_{(t)} _{n}y_nW_f^TX_n > 0 \end{aligned}

可以看出,当前向量 Wt 不断向理想向量 Wf 接近,因为两者的内积不断增大(但内积增大可能是由于向量长度的变化) \(\color{darkorange}{w_f^Tw_t\uparrow}\) by updating with any \(\color{purple}{\left(x_{n(t)},y_{n(t)}\right)}\)

\begin{aligned} w_t^Tw_{t+1} &= w_f^T(w_t + y_{n(t)}x_{n(t)}) \ & w_f^Tw_t + \ & w_f^Tw_t + \end{aligned}

证明铺垫 2

Wt 的模的增长速度受导致每个修正的错误点的限制 (\(\color{chocolate}{w_t \text{ changed only when mistake}}\))

\begin{aligned} sign( t) y_{n(t)} \end{aligned}

证明运行次数 T 的上限

先定义\(R^2=\mathop{max}\limits_{n}||x_n||^2\) \(\rho = \mathop{min}\limits_n y_n \dfrac{W_f^T}{||W_f||}X_n\)

由证明步骤 1 中结论:

\begin{aligned} W_f^TW_T &= W_f^T(W_{T-1} + y_{(T-1)}X_{(T-1)}) = W_f^T + y{(T-1)}W_f^TX_{(T-1)} \ &W_f^TW_{(T-1)} + miny W_f^TX W_F^TW_0 + TminyW_F^TX = TminyW_f^TX \end{aligned}

由证明步骤 2 中结论:

\begin{aligned} ||W_T||^2 ||W_{T-1}|| + max ||x||^2 ||W_0||^2 + T max||x||^2 = Tmax||x||^2 \end{aligned}

用 R 和ρ 对以上两条不等式进行代换可得:

\[\begin{aligned} \dfrac{W_f^TW_T}{\left||W_f|\right|\left||W_T|\right|} \geq \sqrt T \dfrac\rho R \end{aligned}\]

再由两个单位向量的内积 < 1,得到

\[\begin{aligned} T \leq \frac {R^2} {\rho^2} \end{aligned}\]

算法收敛性得证

Pocket Algorithm

对 PLA 稍加改造:遍历结束时返回当前最优 Wt

用来应对无法确定 PLA 上界的问题。但由于每次更新 Wt 都要检查 Wt+1和 Wt 对所有点的正确数,所以相对 PLA 花费额外时间。

PLA
PLA