Lecture 2 Learning to Answer Yes or No

2.1 Perceptron Hypothesis Set 感知假说集

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

h = s i g n (w^{T} x)

当

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

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)

我们已知

(x_{n}, y_{n})

对，求的是在无数个可能的

w

的假设空间中最可能的

w

，也就是我们的g。

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

s i g n (w_{t}^{T} x_{n (t)}) \neq y_{n (t)}

把

w

的值进行更新，

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

如此迭代，直到没有错误。
【林轩田】机器学习基石（二）——PLA

返回最后的

w

，记为

w_{P L A}

，为g。

那么如何用几何的方式来描述上述过程呢？
我们知道w，x都可以描述成向量形式，尽管他们可能不是二维的，我们为了方便起见，假设它们都是二维的。
当实际的 $y$ 为+1，而预测的 $y$ 为-1时，我们更新 $w$ ,
【林轩田】机器学习基石（二）——PLA
可以看到，这里的向量加法， $w + y x$ 是让，更新后的 $w$ ，更偏向x这条向量线（ $x$ 与更新后的 $w$ 的夹角变小）。
当实际的 $y$ 为-1，而预测的 $y$ 为+1时，我们更新 $w$ ,

可以看到，这里的向量加法， $w + y x$ 是让，更新后的 $w$ ，更远离x这条向量线（ $x$ 与更新后的 $w$ 的夹角变大）。
为了让我们更直观地看到每一步迭代时分类的变化，林老师举了个例子。
【林轩田】机器学习基石（二）——PLA

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

……

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

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

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

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

y_{n} w_{n}^{T} x_{n} > 0

，

y_{n} w_{f}^{T} x_{n} \geq min_{n} y_{n} w_{f}^{T} x_{n} > 0

w_{f}^{T} w_{t}

随着错误的不断被更新不断地增大，

w_{f}^{T} w_{t + 1} = w_{f}^{T} (w_{t} + y_{n} x_{n}) \geq w_{f}^{T} w_{t} + m i n_{n} y_{n} w_{f}^{T} x_{n} > w_{f}^{T} w_{t} （ 公 式 1 ）

上述公式说明的是向量

w_{f}^{T}

和

w_{t}

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

w_{t}

的模越来越大。
首先原因一是肯定的，因为我们的目标就是让

w_{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}

是遇到错误才开始更新，所以

2 y_{n} x_{n} w_{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)

接下来林老师提出了一个小的练习，
【林轩田】机器学习基石（二）——PLA

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

w_{f}^{T} w_{t + 1} \geq w_{f}^{T} w_{t} + m i n_{n} y_{n} w_{f}^{T} x_{n}

w_{f}^{T} w_{t} \geq w_{f}^{T} w_{t - 1} + m i n_{n} y_{n} w_{f}^{T} x_{n}

叠加起来

w_{f}^{T} w_{t + 1} \geq w_{f}^{T} w_{t - 1} + 2 * m i n_{n} y_{n} w_{f}^{T} x_{n}

w_{f}^{T} w_{t + 1} \geq w_{f}^{T} w_{0} + (T + 1) * m i n_{n} y_{n} w_{f}^{T} x_{n} \geq (T + 1) * m i n_{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} | |^{2} \leq | | w_{t - 1} | |^{2} + max_{n} | | y_{n} x_{n} | |^{2}

叠加，得

| | w_{t + 1} | |^{2} \leq | | w_{t - 1} | |^{2} + 2 * max_{n} | | y_{n} x_{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 ）

结合公式3，公式4，图片中左式

\frac{w_{f}^{T} w_{T}}{| | w_{f}^{T} | | * | | w_{T} | |} \geq \frac{T * m i n_{n} y_{n} w_{f}^{T} x_{n}}{| | w_{f}^{T} | | * | | w_{T} | |} \geq \frac{T * m i n_{n} y_{n} w_{f}^{T} x_{n}}{| | w_{f}^{T} | | * \sqrt{T} * max_{n} | | y_{n} x_{n} | |}

也就是说这个constant为

c o n s t a n t = \frac{m i n_{n} y_{n} w_{f}^{T} x_{n}}{| | w_{f}^{T} | | max_{n} | | y_{n} x_{n} | |}

由于

y_{n} \in - 1, + 1

，所以上述等式可以简化为

c o n s t a n t = \frac{m i n_{n} y_{n} w_{f}^{T} x_{n}}{| | w_{f}^{T} | | * max_{n} | | x_{n} | |}

在Fun-Time里面林老师让我们计算T的上界，其实很简单，因为图片中的左式的集合意义就是向量

w_{f}^{T}

和

w_{t}

的余弦值，余弦值的范围是

[0, 1]

，所以

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

也就是

T \leq \frac{1}{c o n s t a n t^{2}} \leq \frac{| | w_{f}^{T} | |^{2} * max_{n} | | x_{n} | |^{2}}{| | m i n_{n} y_{n} w_{f}^{T} x_{n} | |^{2}}

所以

T \leq \frac{R^{2}}{ρ^{2}}

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

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

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

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

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

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

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

解决办法是，找到一条线，它在我们遇到的所有线中，误分类最小。
即
【林轩田】机器学习基石（二）——PLA
上述公式是个NP难的问题，我们使用PLA的贪心算法变体解决。

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

林老师在这节给出的Fun Time问题还挺值得思考的，反正我是想错了。
【林轩田】机器学习基石（二）——PLA
这个问题的意思是，在已知数据线性可分的前提下，我们还是用PLA的贪心算法变体来计算那条分割线，这样的计算方法和直接用PLA有什么不同？
答案是1，原因是PLA的贪心算法针对的是存在噪声的数据，所以在每次迭代时，都会对每个点进行计算，看看找到的这条 $w$ 整体上是不是比上次好了；而本体PLA针对的是数据线性可分，肯定能终止的情况，它每次迭代只需要找一个错误点就行。
所以这道Fun Time题中，PLA的贪心变体执行的时间会长于PLA本体。

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

Lecture 2 Learning to Answer Yes or No

2.1 Perceptron Hypothesis Set 感知假说集

2.2 Perceptron Learning Algorithm 感知演算法

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

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

相关推荐