【林轩田】机器学习基石（二）—

本文主要是介绍【林轩田】机器学习基石（二）——PLA，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Lecture 2 Learning to Answer Yes or No

ppt

2.1 Perceptron Hypothesis Set 感知假说集

感知假说集这部分，林老师主要是举了个线性回归的例子，来帮我们感性地认识了 h 这个东西到底是什么。
比如说线性回归：

h = s i g n (w T x)

$h = sign(w^Tx)$
当

x = x 0, x 1, x 2

$x={x_0,x_1,x_2}$ 时,

h = s i g n (w 0 x 0 + w 1 x 1 + w 2 x 2) = s i g n (w 0 + w 1 x 1 + w 2 x 2)

$h = sign(w_0x_0+w_1x_1+w_2x_2) = sign(w_0+w_1x_1+w_2x_2)$
slide中h就相当于图片中圈和叉的分界线，找一条分割最好的分界线

2.2 Perceptron Learning Algorithm 感知演算法

这部分开始推导了。

2.1节说明了h是一个假设空间集，我们希望在h里面能找到一个g，使它最接近f。

这里f是指存在的一种理想化的规律或模式，是我们不知道的，但是我们的data都是依照这种模式产生的；因为f我们不知道，但是我们有data，所以我们可以根据data来找一个g，使g这个函数在我们已知的data上表现的尽可能像f这个理想化的函数。

林老师举了一个简单的演算法的例子并说明了它的可行性。
还是考虑线性回归，

h = s i g n (w T x)

$h = sign(w^Tx)$
我们已知

(xn,yn) ( x n , y n ) $(x_n,y_n)$ 对，求的是在无数个可能的

w w $w$ 的假设空间中最可能的

w

$w$ ，也就是我们的 g。

首先从候选集随机中随机选择一个 $w$ ，作为 $w_0$ ，然后开始迭代，
迭代次数设置为 $t(times)，t\in{1,2,3,...,m}$
从 $t =1$ 开始，
如果

s i g n (w T t x n (t)) \neq y n (t)

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

w w $w$ 的值进行更新，

w_{t + 1} = w_{t} + y_{n (t)} x_{n (t)}

$w_{t+1} = w_t + y_{n(t)}x_{n(t)}$
如此迭代，直到没有错误。

返回最后的

w w $w$ ，记为

w_{P L A}

$w_{PLA}$ ，为 g。

那么如何用几何的方式来描述上述过程呢？
我们知道w，x都可以描述成向量形式，尽管他们可能不是二维的，我们为了方便起见，假设它们都是二维的。
当实际的 $y$ 为+1，而预测的 $y$ 为-1时，我们更新 $w$ ,

可以看到，这里的向量加法， $w+yx$ 是让，更新后的 $w$ ，更偏向x这条向量线（ $x$ 与更新后的 $w$ 的夹角变小）。
当实际的 $y$ 为-1，而预测的 $y$ 为+1时，我们更新 $w$ ,

可以看到，这里的向量加法， $w+yx$ 是让，更新后的 $w$ ，更远离x这条向量线（ $x$ 与更新后的 $w$ 的夹角变大）。
为了让我们更直观地看到每一步迭代时分类的变化，林老师举了个例子。

……

注意到这里 $w$ 使我们划分圈圈叉叉那条线的法向量。

2.3 Guarantee of PLA 感知器演算法的证明

这一小节的目标是证明PLA的正确性。
首先PLA可以收敛的一个重要的先决条件是数据是线性可分的。也就是说，存在某个完美的 $w_f$ 使得 $sign(w^{T}_{f}x_n) = y_n$ 。
这个完美的 $w_f$ ，在几何意义上，就是有一条线，使得每一个 $x_n$ 都被正确地划分在线的两边。
即对于任意n：

y n w T n x n > 0

$y_nw^T_nx_n > 0$ ，

y n w T f x n \geq min n y n w T f x n > 0

$y_{n}w_{f}^{T}x_n \ge \min_{n}y_{n}w_{f}^{T}x_n > 0$

wTfwt w f T w t $w_{f}^Tw_{t}$ 随着错误的不断被更新不断地增大，

w T f w t + 1 = w T f (w t + y n x n) \geq w T f w t + m i n n y n w T f x n > w T f w t （ 公 式 1 ）

$w_{f}^Tw_{t+1} = w_{f}^T(w_t + y_nx_n) \\ \ge w_{f}^Tw_t + min_{n}y_{n}w_{f}^{T}x_n\\ > w_{f}^Tw_t （公式1）$
上述公式说明的是向量

wTf w f T $w_{f}^T$ 和

wt w t $w_{t}$ 的内积在不断地增大，这种结果有两种可能的原因，一是两个向量的夹角余弦值越来越大，二是

wt w t $w_{t}$ 的模越来越大。
首先原因一是肯定的，因为我们的目标就是让

wt w t $w_{t}$ 越来越接近

wTf w f T $w_{f}^T$ ，然后我们来看看原因二。

| | w t + 1 | | 2 = | | w t + y n x n | | 2 = | | w t | | 2 + 2 y n x n w t + | | y n x n | | 2 (公 式 2 - 1)

$||w_{t+1}||^2 = ||w_t + y_nx_n||^2 \\ =||w_t||^2+2y_nx_nw_t + ||y_nx_n||^2\\ (公式2-1)$
由于

wt w t $w_t$ 是遇到错误才开始更新，所以

2ynxnwt 2 y n x n w t $2y_nx_nw_t$ 是小于0的
即，

| | w t | | 2 + 2 y n x n w t + | | y n x n | | 2 < | | w t | | 2 + | | y n x n | | 2 \leq | | w t | | 2 + max n | | y n x n | | 2 (公 式 2 - 2)

$||w_t||^2+2y_nx_nw_t + ||y_nx_n||^2 < ||w_t||^2 + ||y_nx_n||^2\\ \le ||w_t||^2 + \max_n||y_nx_n||^2 (公式2-2)$
接下来林老师提出了一个小的练习，

求constant的值。
推导过程如下：
由公式1

w T f w t + 1 \geq w T f w t + m i n n y n w T f x n

$w_{f}^Tw_{t+1} \ge w_{f}^Tw_t + min_{n}y_{n}w_{f}^{T}x_n$

w T f w t \geq w T f w t - 1 + m i n n y n w T f x n

$w_{f}^Tw_{t} \ge w_{f}^Tw_{t-1} + min_{n}y_{n}w_{f}^{T}x_n$
叠加起来

w T f w t + 1 \geq w T f w t - 1 + 2 * m i n n y n w T f x n

$w_{f}^Tw_{t+1} \ge w_{f}^Tw_{t-1} + 2*min_{n}y_{n}w_{f}^{T}x_n$

w T f w t + 1 \geq w T f w 0 + (T + 1) * m i n n y n w T f x n \geq (T + 1) * m i n n y n w T f x n （ 公 式 3 ）

$w_{f}^Tw_{t+1} \ge w_{f}^Tw_0 + (T+1)*min_{n}y_{n}w_{f}^{T}x_n \\ \ge (T+1)*min_{n}y_{n}w_{f}^{T}x_n （公式3）$
由公式2

| | w t + 1 | | 2 \leq | | w t | | 2 + max n | | y n x n | | 2

$||w_{t+1}||^2 \le ||w_t||^2 + \max_n||y_nx_n||^2$
即

| | w t | | 2 \leq | | w t - 1 | | 2 + max n | | y n x n | | 2

$||w_{t}||^2 \le ||w_{t-1}||^2 + \max_n||y_nx_n||^2$
叠加，得

| | w t + 1 | | 2 \leq | | w t - 1 | | 2 + 2 * max n | | y n x n | | 2

$||w_{t+1}||^2 \le ||w_{t-1}||^2 +2* \max_n||y_nx_n||^2$

| | w t + 1 | | 2 \leq | | w 0 | | 2 + (T + 1) * max n | | y n x n | | 2 \leq (T + 1) * max n | | y n x n | | 2 （ 公 式 4 ）

$||w_{t+1}||^2 \le ||w_0||^2 +(T+1)* \max_n||y_nx_n||^2 \\ \le (T+1)* \max_n||y_nx_n||^2 （公式4）$
结合公式3，公式4，图片中左式

w T f w T | | w T f | | * | | w T | | \geq T * m i n n y n w T f x n | | w T f | | * | | w T | | \geq T * m i n n y n w T f x n | | w T f | | * T - - \sqrt * max n | | y n x n | |

$\frac{w_{f}^Tw_{T}}{||w_{f}^T||*||w_{T}||} \ge \frac{T*min_{n}y_{n}w_{f}^{T}x_n}{||w_{f}^T||*||w_{T}||} \ge \frac{T*min_{n}y_{n}w_{f}^{T}x_n}{||w_{f}^T||*\sqrt{T}* \max_n||y_nx_n||}$
也就是说这个constant为

c o n s t a n t = m i n n y n w T f x n | | w T f | | max n | | y n x n | |

$constant = \frac{min_{n}y_{n}w_{f}^{T}x_n}{||w_{f}^T|| \max_n||y_nx_n||}$
由于

yn∈−1,+1 y n ∈ − 1 , + 1 $y_n \in {-1,+1}$ ，所以上述等式可以简化为

c o n s t a n t = m i n n y n w T f x n | | w T f | | * max n | | x n | |

$constant = \frac{min_{n}y_{n}w_{f}^{T}x_n}{||w_{f}^T|| *\max_n||x_n||}$
在Fun-Time里面林老师让我们计算T的上界，其实很简单，因为图片中的左式的集合意义就是向量

wTf w f T $w_{f}^T$ 和

wt w t $w_t$ 的余弦值，余弦值的范围是

[0,1] [ 0 , 1 ] $[0,1]$ ，所以

0 \leq T - - \sqrt * c o n s t a n t \leq 1

$0 \le \sqrt{T} *constant \le 1$
也就是

T \leq 1 c o n s t a n t 2 \leq | | w T f | | 2 * max n | | x n | | 2 | | m i n n y n w T f x n | | 2

$T \le \frac{1}{constant^2} \\ \le \frac{||w_{f}^T||^2 *\max_n||x_n||^2}{||min_{n}y_{n}w_{f}^{T}x_n||^2}$

所以

T \leq R 2 ρ 2

$T \le \frac{R^2}{\rho ^2}$

2.4 Non-Separable Data 不可分割的（线性）数据、

上面的内容告诉我们，PLA有两个重要的点

Data要线性可分 —-> 这是 $w_f^T$ 和 $w_t$ 越来越接近的理论前提。
PLA是从错误中学习—->这个点使得 $w_t$ 越来越大。

PLA的优点是：快速、容易实现，且在任意维度下都可使用。
PLA的缺点是：

只适用于线性可分数据（但是现实情况下，我们哪里会知道Data的确定分布呢？要是事先知道了Data的确定分布，还要机器学习干啥？），所以PLA还是比较理想化的。

在现实生活中，我们的数据是存在噪声的。

那么，如何学习到具有噪声容忍度的 $w$ 呢？

解决办法是，找到一条线，它在我们遇到的所有线中，误分类最小。
即

上述公式是个NP难的问题，我们使用PLA的贪心算法变体解决。

这里和2.2节最大的区别在于，贪心算法面对的数据（存在噪声）永远也没有办法停止。所以需要提前设定迭代阈值。

林老师在这节给出的Fun Time问题还挺值得思考的，反正我是想错了。

这个问题的意思是，在已知数据线性可分的前提下，我们还是用PLA的贪心算法变体来计算那条分割线，这样的计算方法和直接用PLA有什么不同？
答案是1，原因是PLA的贪心算法针对的是存在噪声的数据，所以在每次迭代时，都会对每个点进行计算，看看找到的这条 $w$ 整体上是不是比上次好了；而本体PLA针对的是数据线性可分，肯定能终止的情况，它每次迭代只需要找一个错误点就行。
所以这道Fun Time题中，PLA的贪心变体执行的时间会长于PLA本体。