林轩田机器学习基石(2)：Learning to Answer Yes/No

欢迎关注公众号-AI圈终身学习。
公众号首页回复“机器学习”查看所有系列文章。

---

上节林老师讲了机器学习的定义与流程：

总结就是：训练数据D在演算法A的观察学习下，从假设集合H中，选择出最好的一个假设h得到最终的模型函数g。

本节笔记Lecture 2-Learning to Answer Yes/No包含内容如下：

• When Can Machines Learn?(什么时候用机器学习)
  • 感知器假设集(Perceptron Hypothesis Set)
  • 感知器演算法(Perceptron Learning Algorithm(PLA))
  • PLA保证(Guarantee of PLA)
  • 线性不可分数据(Non-Separable Data)

一、感知器假设集(Perceptron Hypothesis Set)

1.1 例子

本节依旧使用上文的信用卡例子，即银行需要根据用户数据来判断是否给其发信用卡。假设用户有性别、年龄、薪水、负债、工龄等属性：

我们有许多人这样的数据，这些数据组成数据集，记为D。现在的问题就变成根据D，用演算法A从假设集合H取选出最好的一个假设h，得到h对应的模型函数g，如下图：

那么什么假设集我们可以用呢？本文讲解一个简单但是重要的假设集：感知器(Perceptron)。

1.2 感知器假设集

我们记用户数据的属性集合为$X=(x_1,x_2,...,x_d)$X=(x1​,x2​,...,xd​)，他有对应的权重集合$W=(w_1,w_2,...,w_d)$W=(w1​,w2​,...,wd​)(这就是一个假设集)表示属性的重要程度，越重要的属性x，其对应的权重w越大。通过特征的加权求和得分结果$W^TX$WTX，比较得分结果与阈值大小：

• 得分结果>阈值，发信用卡。
• 得分结果<阈值，不发信用卡。

最终的感知器假设集就是h(x)，公式如下：

通常我们不会专门写一个门槛值，为了表述方便，通常会用$w_0=-threshold$w0​=−threshold表示阈值，引入$x_0=1$x0​=1与$w_0$w0​相乘，最终可以简化成如下写法：

1.3 感知器的形状

在二维平面上，感知器公式展开为$h(x)=sign(w_0+w_1x_1+w_2x_2)$h(x)=sign(w0​+w1​x1​+w2​x2​)，可以看到下面的图有圈(表示+1)和叉(表示-1)，中间将他们分开的线就是感知器划分线，这条线为$w_0+w_1x_1+w_2x_2=0$w0​+w1​x1​+w2​x2​=0：

感知器又将线性分类器(linear classifiers)，它不一定局限于二维平面，所有满足$W^TX=0$WTX=0形式的模型，都可以叫线性分类器。

我们的假设集合H就表示二维平面所有的线，那么我们的演算法A就需要从所有的H中选择出最好的一个假设。如果我们细心会发现上图中经过演算法更新后，右边的线分类效果明显优于左边的线。

二、感知器演算法(Perceptron Learning Algorithm(PLA))

2.1 PLA原理

我们已经知道，在二维平面里，感知器演算法的核心目的就是从无数条线中找出最合适的一条线，把数据分开。一开始我们随机初始化一条分割线，演算法的步骤只有两步：

1. 遍历找出犯错的点
2. 用犯错的点做修正

找出犯错的点比较容易，如果感知机计算出来的值和标签不一致即为犯错点。

修正过程林老师用图进行了讲解：

• 若正例识别成负，此时$y_{n}w^{T}x_{n} \leq 0$yn​wTxn​≤0，推出$W^{T}x_{n} \leq 0$WTxn​≤0。根据高中数学可知，向量W和向量$x_n$xn​的夹角大于90°，我们通过$W=W+x_n$W=W+xn​旋转修正这个W，使得$W和x_n$W和xn​夹角小于90°，如下图，紫色线表示修正后的结果:

• 若负例识别成正，此时$y_{n}W^{T}x_{n} \leq 0$yn​WTxn​≤0，推出$W^{T}x_{n} \geq 0$WTxn​≥0。根据高中数学可知，向量W和向量$x_n$xn​的夹角小于90°，我们通过$W=W-x_n$W=W−xn​旋转修正W，使得$W和x_n$W和xn​夹角大于90°，如下图，紫色线表示修正后的结果:

这里需要注意W表示感知器分割线$W^TX=0$WTX=0的法向量，法向量所指的方向即为正。

通常我们要遍历所有的点进行修正，所以具体实现的算法又叫Cyclic PLA(Perceptron Learning Algorithm)算法，记不住我也觉得不重要。

2.2 PLA过程可视化

林老师讲解了一个动态更新的过程，假设初始化$W=0$W=0，这个时候感知器就在原点:

这个时候它看哪个点都是错的，所以根据图中第一个黑点$x_1$x1​更新W，紫色的线为法向量W，当前时刻为t，t+1就表示更新后的权重:

根据法向量W可以画出一条垂直于W的分割线$W^TX=0$WTX=0，发现第九个点正类分到了负类，旋转更新红色的W(t)为紫色的W(t+1)：

然后不断循环：

…

最后更新完成，这是一条完美的分割线。

2.3 思考为什么PLA有效

根据PLA的更新规则:

请思考下面哪条公式一定是对的：

答案是第③条，我们只要在更新公式$W_{t+1}=W_{t}+y_nx_n$Wt+1​=Wt​+yn​xn​两边同时乘以$y_nx_n$yn​xn​即可得到③式。这个式子一定程度上说明了PLA的有效性。下面给出两个例子:

假设我们一条正例被识别成了负例，此时有:

• $y_n = 1$yn​=1

所以有:

• $w^T_{t}x_n$wtT​xn​ < 0
• $w^T_{t+1}x_n \geq w^T_{t}x_n$wt+1T​xn​≥wtT​xn​

也就是它每次更新尝试把感知器的得分和，从负修改为正，说明它在努力修改错误。

同理假设我们一条负例被识别成了正例，此时有:

• $y_n = -1$yn​=−1

所以有:

• $w^T_{t}x_n$wtT​xn​ > 0
• $w^T_{t+1}x_n \leq w^T_{t}x_n$wt+1T​xn​≤wtT​xn​

也就是它每次更新尝试把感知器的得分和，从正修改为负，说明它也在努力修改错误。

三、PLA数学保证(Guarantee of PLA)

现在我们关心两个问题：

• PLA总是可停的吗？
• PLA何时才停？

3.1 PLA总是可停的吗？

PLA可停需要对数据集有要求。

如果PLA停止了，则对于感知器来说，所有点都没有错误了，这样的数据集我们叫线性可分的，比如下图:

对于左边的图是线性可分的。但是中间的图有一个圆圈在红叉的区域，右边的图是一个圆，PLA都没法停止。

3.2 PLA何时才停？

本节主要讲PLA的两点：收敛性和有效性。

对于线性可分的数据集，一定存在一个完美但是我们不可知的$W_f$Wf​，使得这条线完美的划分所有数据
$y_n=sign(W_f^Tx_n)$yn​=sign(WfT​xn​)

那么对于所有的点一定满足：

• 所有的点被划分在正确的区域
• 到这点线的距离一定是大于0的

因此有:

PLA每次是通过错误的点$(x_n, y_n)$(xn​,yn​)来修正$W_t$Wt​，如果$W_t离W_f$Wt​离Wf​越来越接近，那么就证明了PLA的有效性，数学上可以用内积表示两个向量的相似性：

通过推导可以发现每一次更新他们的内积越来越大，但是并不一定他们越来越相近，因为这可能有两种情况：

• 向量夹角变小
• 向量模长变大

实际上，每次PLA修正都是因为出现了错误的点，可以证明$W_t$Wt​的模长增长不会太快。对于错误的点有：

根据PLA的增长公式$W_{t+1}=W_t+y_nx_n$Wt+1​=Wt​+yn​xn​，两边平方有：

也就是说$||W_t||$∣∣Wt​∣∣的增长项只有$\underset{n}{\operatorname{max}}||x_n||$nmax​∣∣xn​∣∣，每次变化有所限制。

作业：初始化$W_0=0$W0​=0，PLA修正T次后，可以证明：

$\cfrac{w_f^T}{||w_f||}\cfrac{w_T^T}{||w_T||}\geq \sqrt{T}constant$∣∣wf​∣∣wfT​​∣∣wT​∣∣wTT​​≥T​constant

请计算constant是什么。

证明如下：

所以$constant=\cfrac{\underset{n}{\operatorname{min}}y_nw^T_fx_n}{||w_f||\underset{n}{\operatorname{max}}||x_n||}$constant=∣∣wf​∣∣nmax​∣∣xn​∣∣nmin​yn​wfT​xn​​
又因为$1 \geq \cfrac{w_f^T}{||w_f||}\cfrac{w_T^T}{||w_T||}\geq \sqrt{T}constant$1≥∣∣wf​∣∣wfT​​∣∣wT​∣∣wTT​​≥T​constant

故$T\leq \cfrac{1}{constant^2}$T≤constant21​

因此我们知道PLA一定会在$\cfrac{1}{constant^2}$constant21​次内收敛，且随着PLA修改次数t的增加，$W_t越来越接近W_f$Wt​越来越接近Wf​，证明了PLA有效性和收敛性。

四、线性不可分数据(Non-Separable Data)

现在我们有两个问题：

• 虽然我们证明了PLA会收敛，但是它取决于我们不知道的参数$W_f$Wf​，因此我们不知道它何时会收敛。
• 如果数据并不完全的线性可分，$W_f$Wf​根本不存在，此时该怎么办？

在现实中，几乎不可能出现理想的线性可分数据，比如对于这样的数据：

我们可以把它看成线性可分数据中混入了一些噪音数据。我们知道PLA最终的划分完全无误，因此解决这个问题一个很好的思路就是通过演算法获得错误点最少的一条线，如上图所示，公式表示如下：

但是这是一个NP-hard问题，现在的技术无法求解。因此引出了一种PLA的贪心算法Pocket PLA：每次更新确保错误点更少

模型保存的假设参数我们放在口袋(Pocket)里，记为$\widehat{w}$w，其对应的错误点个数为$n_t$nt​；如果更新后的线$w_{t+1}$wt+1​划分的错误点个数小于$n_t$nt​，则更新$\widehat{w}=w_{t+1}$w=wt+1​。

五、总结

本节主要介绍了感知器的假设集、演算法和收敛性有效性相关的数学知识；针对非线性可分数据，可以使用PLA修正算法Pocket Algorithm进行处理。