Lecture 2：Learning to Yes/No

2018-08-24 本文已影响0人薛家掌柜的

Perceptron Learning Algorithm (PLA)

现在我们把 $H$ 看作是所有可能的感知机(Perceptron),把 $g$ 看作其中的一个感知机假设。
那么，我们想要做的就是让 $g$ 尽可能的接近target function $f$ ，理论上讲在数据集 $D$ 上， $g(x_n) = f(x_n) = y_n$ 是成立的，也是必要的。
但是 $H$ （感知机假设）是无限的，那要怎么做呢？

idea: start from some $g_0$ (represent by its weight vector $w_0$ ),and 'correct' its mistakes on $D$

以下是PLA流程：
For t = 0，1，...

找到被 $w_t^T$ 划分错误的一个错误点 $(x_{n(t)} ,y_{n(t)})$ ，使得 $sign(w_t^T x_{n(t)}) \neq y_{n(t)}$
令 $w_{t+1} \leftarrow w_t + y_{n(t)}x_{n(t)}$ ，尝试去修正这个错误。

... 直到没有分错的点为止。此时令 $g = w( w_{PLA})$
举例说明：

Guarantee of PLA

首先讲一下线性可分(Linear Separability)的概念：

if PLA halts(意味着没有错误点了，这是必要条件)， $D$ allows some $w$ to make no mistakes
call such $D$ Linear Separability
也就是说，Linear Separable $D \Leftrightarrow$ exits perfect $w_f$ such that $y_n = sign(w_f^T x_n)$
假设 $D$ 总是线性可分，但是PLA一定会停下来吗？
实际上， $w_t$ Gets More Aligned with $w_f$
我们可以简单证明一下：
$w_f$ perfect hence every $x_n$ correctly away from line:
$y_{n(t)}w_f^T x_{n(t)} \geq min y_n w_f^Tx_n > 0$
$w_f^Tw_t \uparrow$ update by any $(x_{n(t)},y_{n(t)})$
$w_f^T w_{t+1} = w_f^T(w_t + y_{n(t)}x_{n(t)})$
$\geq w_f^Tw_t + miny_nw_f^Tx_n$
$>w_f^T w_t+0$

并且， $w_t$ does not grow too fast
Because $w_t$ changed only when mistake $\Leftrightarrow sign(w_t^Tx_{n(t)}) \neq y_{n(t)} \Leftrightarrow y_{n(t)}w_f^T x_{n(t)} \leq0$
mistakes 'limits' $||w_t||^2$ growth,even when updating which 'longest' $x_n$
$||w_{t+1}||^2 = ||w_t+y_{n(t)}x_{n(t)}||^2$
$=||w_t||^2+2w_ty_{n(t)}x_{n(t)}+||y_{n(t)}x_{n(t)}||^2$
$\leq||w_t||^2+0+||y_{n(t)}x_{n(t)}||^2$
$<||w_t||^2+max||y_nx_n||^2$

Note:start from $w_0 = 0$ ,after T mistake corrections： $\frac{w_f^T}{||w_f||}\frac {w_t}{||w_t||} \leq \sqrt{T} \cdot constant$

Non-Separable Data

上面讲述了PLA基于线性可分数据的过程，而在现实生活中， $D$ 并不总是separable的。那么，我们要怎么做才能使得 $g \approx f$ 成立呢？
如果数据集如下图所示，我们永远不可能画一条直线完全分开 $\circ$ 和 $\times$ 样本。

但是，显然，noise数据不会太多（太多了就没意义了，对这份数据集而言），那么我们可以假设

y_n = f(x_n)

在一般情况下是成立的，即忽略噪点。那么，在这份数据集

D

上，

g\approx f \Leftrightarrow y_n = g

也是成立的。
所以，现在我们要做的，就是找一条线，使得错误点数量尽可能少。
即

w_g \leftarrow argmin \sum_{n=1}^{N}[|y_n \neq sign(w_n^T x_n)|]

不幸的是，这是一个NP难题。我们只能去找一个近似的符合条件的g。
这里我们引入Pocket算法

\Rightarrow

modify PLA by keep best weights in Pocket。
initialize pocket weights in

\hat{w}

,
For t = 0，1，...

找到被 $w_t^T$ 划分错误的一个错误点 $(x_{n(t)} ,y_{n(t)})$ ，使得 $sign(w_t^T x_{n(t)}) \neq y_{n(t)}$
令 $w_{t+1} \leftarrow w_t + y_{n(t)}x_{n(t)}$ ，尝试去修正这个错误。
如果 $w_{t+1}$ 划分的错误点比 $\hat{w}$ 少，那么replace $\hat{w}$ by $w_{t+1}$
... 直到迭代到足够次数为止。
此时令 $g = \hat{w}( w_{POCKET})$

Lecture 2：Learning to Yes/No

Perceptron Learning Algorithm (PLA)

Guarantee of PLA

Non-Separable Data

猜你喜欢

热点阅读