Week02. Learning to Answer Yes/No

Course_Lin_MLF

---

Roadmap

Learning to Answer

1. A simple Hypothesis Set ： the Perceptron

• $x=\{x_1,x_2, \dots, x_d\}$
  $y:\{+1,-1\}$
  linear formula $h \in \mathcal{H}$ are
  

  $$\begin{align*} h(x) = sign\Big( \big( \sum\limits_{i=1}^d w_ix_i \big) - thrershold \Big) \end{align*}$$

• Vector Form
  $-threshold \to w_0$
  $1 \to x_0$
  

  $$h(x) = sign( \mathbf{w^Tx})$$

• Perceptron in ${ \mathbb{R}^2 }$
  

  $$h(x) = sign(w_0 + w_1x_1 + w_2x_2)$$
  平面上的一条线
  linear classifier

2. Perceptron Learning Algorithm(PLA)

• Select $g$ from $\mathcal{H}$
  $\mathcal{H}$ is of infinite szie

  • find a mistake of $w_t$ called $(x_{n(t)},y_{n(t)})$
    $$sign(w_t^T) \ne y_{n(t )}$$
  • (try to) correct the mistake by
    $$w_{t+1 } \leftarrow w_t + y_{n(t)}x_{n(t)}$$
    增大或减小内积，增大或减小与样本点之间的夹角。
    loop until no nore mistakes

• Some Remaining ISsues of PLA

  • Algotithmic: halt(with no mistake)?
  • Learning: $g \approx f$?

3. Guarantee of PLA

• Linear Separability

• PLA Fact: $w_t$ Gets More Aligned with $w_f$
  如果样本线性可分，则存在一个$w_f$使得
  

  $$y_n=sign(w_f^Tx_n)$$
  存在
  $$y_{n(t)}w_f^Tx_{n(t)} \ge \min\limits_n y_nw_f^Tx_n>0$$

两个向量越来越接近，(长度不变的情况下)内积越来越大

$$\begin{align*} w_f^Tw_{t+1} &= w_f^T(w_t + y_{n(t)}x_{n(t)}) \\ &\ge w_f^Tw_t + \min\limits_ny_nw_f^tx_n \\ &>w_f^Tw_t + 0 \end{align*}$$

• PLA Fact： $w_t$ Does Not Grow Too Fast

  PLA:有错才更新
  

  $$y_{n(t)}w_t^Tx_{n(t)} \le 0$$
  限制了$w_t$的增长，即使是使用最远的点$x_{n(t)}$来进行更新
  $$\begin{align*} \parallel w_{t+1} \parallel ^2 &= \parallel w_t + y_{n(t)}x_{n(t)}\parallel ^2 \\ &=\parallel w_t\parallel ^2 + 2y_{n(t)}w_t^Tx_{n(t)} + \parallel y_{n(t)}x_{n(t)}\parallel ^2 \\ &\le \parallel w_t\parallel ^2 + \parallel y_{n(t)}x_{n(t)}\parallel ^2 \\ &\le \parallel w_t\parallel ^2 + \max\limits_n \parallel x_{n(t)}\parallel ^2 \end{align*}$$

  假设从$w_0=0$开始计算，经过$T$次迭代更新之后，有
  

  $$1 \ge \frac{w_f^T \ w_t}{ \parallel w_f^T\parallel \parallel w_t\parallel} \ge \sqrt {T} \cdot constant$$
  上面两个不等式取等号，可以得出最大的迭代次数。

  说明在线性可分的情况下，经过一定次数的迭代之后，算法一定会停止(收敛)。