您的位置: 首页  >  文章  >  2. 机器学习基石-When can Machine Learn? - Learning to Answer Yes or No

2. 机器学习基石-When can Machine Learn? - Learning to Answer Yes or No

分类: 文章 • 2023-12-01 19:54:22

When can Machine Learn? - Learning to Answer Yes or No

1. Perceptron Hypothesis Set

举例银行发信用卡进行解释

1) Perceptron Hypothesis Set

假设空间Hypothesis Set可以用感知器（Perceptron）表示。这种假设空间的思想就类似考试给的成绩，对每一题给一个特定的分数，即加权值(权重);
然后再设计一个及格线，即所谓的阈值或门槛值（threshold），如果加权求和的值大于这个阈值就叫符合条件了，即输出1，小于对应的输出-1。
表示为公式（1）：

h(x)∈Hh(x)=sign(∑i=1dwixi)(1)

其中 sign函数表示为取符号，即 sign(正数) = 1， sign（负数） = -1，如公式（2）所示。

sign(x)={+1x>0−1x<0(2)

最后将h(x) 与阈值作比较，得到公式（3）。

h(x)=sign(∑i=1dwixi−threshold)(3)

2) Perceptron Hypothesis Set公式化简

为了表达方便，可以对h(x)做数学上的讲话，如公式（4）所示。

h(x)=sign(∑i=1dwixi−threshold)=sign(∑i=1dwixi−threshold−1)=sign(∑i=1dwixi−w0−x0)=sign(∑i=0dwixi)=sign(wT⋅x)(4)

如上所示，将负阈值表示为权值向量中的一项(w0)，而对应输入分量则被默认为1，用x0 最终将公式简化为两个向量内积的形式，其中T表示转置。


2. Peceptron Learning algorithm(PLA)

1) Introduction

① Question

Hypothesis Set H包含所有可能的Perceptron，那么具体选用哪一组Perceptron来组合成g(x) 呢?

② Analyze

  • g(x) 和目标函数f越接近越好，但问题是我们不知道f（如果知道了就不需要学习了）
  • 但是我们知道的是样本输入x在f(x) 作用下得到的标记y。

所以如果我们能使得g(x) 在所有的样本输入中都能够得到跟函数f(x) 作用过输入得到的输出一样的话，我们认为这时的gg(x) 是不错的。（在后面的章节还会在这种思想的基础上更深入的讨论这一问题）

③ Solution

我们想到一个简单的方式，就是一步一步的修正错误的分类，在二维平面中可以想象成一条初始的直线，在经过不断的纠正它的错误（就是旋转平移之类的）使得最终的结果可以达到希望的效果。

还要在重复上一节中已经得到的一个结论，在感知器模型中，每一个假设函数g(x) 都对应一个权值向量。因此我们要做的就是不断修正这个权值向量使得最接近目标函数f(x) 。即PLA算法


2) PLA

① PLA步骤

首先我们在设置初始w0（注意此处是向量不是向量的分量！），比如设置为0向量，然后使用训练样本来将权值向量修正的更接近目标函数f(x)。

通过公式（5）来判断什么时候需要进行修正:

sign(wTt⋅xn(t)≠y(n))(5)

通过公式（6）来进行修正：
wt+1=wt+yn(t)⋅xn(t)(6)

② 图示说明

2. 机器学习基石-When can Machine Learn? - Learning to Answer Yes or No

图一 PLA[1]

在本身标记为+1时，权值向量和输入向量的内积为负数，对权值向量略作修改，加上一个标记y和输入向量的乘积，得到一个新的权值向量，可以看出新的权值向量和输入向量的相乘之后符合了标记的要求。

在本身标记为-1时，权值向量和输入向量的内积为正数，对权值向量略作修改，加上一个标记y和输入向量的乘积，得到一个新的权值向量，可以看出新的权值向量和输入向量的相乘之后符合了标记的要求。

重复查找错误样本和修改加权向量，直到再也找不到可以使公式(5)成立的样本为止，此时得到的加权向量，即为我们想要的最终g(x)

具体流程如下图：
2. 机器学习基石-When can Machine Learn? - Learning to Answer Yes or No

图二 PLA Procedure[1]

疑问:如何查找错误样本点，如何确定没有错误的点了?

一个简单的方式就是将训练样本编号，从1到n，以按从1到n的顺序不断查找错误点，如果没有错就自动的用下一个样本点继续查找，当从1到n这n个样本点都没有产生错误时，算法即结束得到g(x) 。将这种方式的算法叫做Cyclic PLA。

新的疑问:

1.这个算法一定会找到一个能使所有的样本都不符合的情况吗(即是否会停下来)？

2.算法找到的真的是最好的g(x)吗？

3.应用到测试集中，结果还会一样吗？

详见 ③ PLA的理论保证

③ PLA的理论保证

i) 前提条件

首先很明显，要用一条直线做Binary Classification必须要求数据线性可分，否则不可以分开（想象一刀切）
如图三：
2. 机器学习基石-When can Machine Learn? - Learning to Answer Yes or No

图三 Linear Seperable [1]

ii) 理论推导

首先PLA的核心是每次修正都让权值的向量WT（T代表在第T次停下）更接近于理想的权值向量Wf,如何衡量两个向量的相似程度呢？内积，即对向量WT和Wf做内积。

内积的大小与2个向量的方向与大小都有关，所以如果我们直接做内积的话，会受到向量长度的影响，所以要做归一化处理，如公式7

wTf⋅wT∣∣wTf∣∣⋅∣∣wT∣∣(7)

公式用于衡量两个向量的方向的差别程度，但是怎么处理这个公式呢？

先看分子,有之前的公式（6）我们可以得到公式（8）:

wTf⋅wT≥wTf⋅(wT−1+yn(T−1)⋅xn(T−1))(8)

如果PLA都会让权值越来越接近理想值，那么由之前的公式（5），我们其实可以推出公式（9）<–(因为wf是最理想的值，那时候应该所有的预测值都和实际相等）和公式（10）<–(因为只有再犯错误的时候才改变，所以WTt与实际值会不一样):

yn(t)wTfxn(t)≥minn ynwTfxn>0(9)

yn(t)wTfxn(t)≤0(10)

所以由公式（9），我们可以对公式（8）进一步限制他的范围：

wTf⋅wT(w0=0)(minn ynwTfxn>0)≥wTf⋅(wT−1+yn(T−1)⋅xn(T−1))≥wTfwT−1+minnwTf⋅yn(T−1)⋅xn(T−1))≥wTfwT−2+2−minnwTf⋅yn(T−1)⋅xn(T−1))...≥wTfw0+T−minnwTf⋅yn(T−1)⋅xn(T−1))≥0+T−minnwTf⋅yn(T−1)⋅xn(T−1))≥T−minnwTf⋅yn(T−1)>0(11)

公式（10）中，我们关键是要得到

wTf⋅wT>T−minnwTf⋅yn(T−1)
。

接着，我们来研究分母:除了wT不容易确定之外，wT的L1范式也不容易得出,但是我们可以转换一下，结合公式（8）(10)来进行处理，即公式（12）。

∣∣wT∣∣2=∣∣wT−1+yn(T−1)xn(T−1)∣∣2=∣∣wT−1∣∣2+∣∣yn(T−1)xn(T−1)∣∣2+2yn(T−1)wT−1xn(T−1)≤∣∣wT−1∣∣2+∣∣yn(T−1)xn(T−1)∣∣2+0≤∣∣wT−1∣∣2+maxn∣∣xn∣∣2≤∣∣wT−2∣∣2+2−maxn∣∣xn∣∣2...≤∣∣w0∣∣2+T−maxn∣∣xn∣∣2=T⋅maxn∣∣xn∣∣2(12)

到此为止，我们已经把分子的下限和分母的上限都找到了，这时候总体的值就应该大于等于某个值。有公式（11）（12），我们可以推论到公式（13）。

wTf⋅wT∣∣wTf∣∣⋅∣∣wT∣∣≥T⋅minnynwTfxnwTfTmaxn∣∣wn∣∣−−−−−−−−−−√=T−−√minnynwTf∣∣wTf∣∣xnmaxn∣∣wn∣∣2−−−−−−−−−√=(√T)⋅C(其中C=minnynwTf∣∣wTf∣∣xnmaxn∣∣wn∣∣2−−−−−−−−−√)(13)

再有归一化之后的内积不可以大于1，所以公式（13）可以加以限制为公式（14)

1≥wTf⋅wT∣∣wTf∣∣⋅∣∣wT∣∣≥T⋅minnynwTfxnwTfTmaxn∣∣wn∣∣−−−−−−−−−−√(14)

求解公式（14）可以得到公式（15）

T≤maxn∣∣wn∣∣2(minnynwTf∣∣wTf∣∣xn)2=R2ρ2（其中：R2=maxn∣∣wn∣∣2,ρ2=⎛⎝minnynwTf∣∣wTf∣∣xn⎞⎠2(15)

从公式（15）可以看出，T是有上限的，所以可以说明在线性可分的情况下PLA算法最终会停止于T点，找到一个最接近目标函数的target function g(x)


3. Non-Separable Data

1) PLA的缺陷

上面提到的PLA算法是基于线性可分的数据集的，这种算法不实用，有2个原因。
1. 在机器学习的时候，我们是不知道数据是否可分的，如果不可分，那样PLA不停止怎么办？
2. 还是与PLA不停止有关，这个时候如果数据集真的线性可分，但是因为数据量太大，跑了很久都没有跑完，怎么办？我们不知道究竟是数据问题，还是数据量太大还没跑完的问题。

所以这时候要求我们改进PLA算法。

2）实际应用中线性可分多还是线性不可分的数据多？

线性不可分的数据多：因为实际应用中存在很多噪音（Noise）。而出现噪音的原因有很多种，如：
- 录入数据的时候出错
- 采集数据的设备存在误差
- …

所以存在噪音的时候，数据集会变成图四那样。

2. 机器学习基石-When can Machine Learn? - Learning to Answer Yes or No

图四 Noise

因为噪音占的比例不会很大，所以最终我们还是可以找到犯错率最少的权值向量wg，如公式（16）所示。

wg=argminw∑n=1Nsign(wT⋅xn)≠yn(16)

但是这个公式在数学上是NP难问题，我们无法直接求解，于是我们需要找出一种近似的算法来求解这个问题：pocket 算法。

3) Pocket 算法

① Pocket算法原理

Pocket 算法属于贪心算法，即如果找到原来的权值更好的权值，才去做修改，否则停止。

流程如下：
1. 也是随机的初始化一个权值向量
2. 随机的使用n个点中的一个点去发现是否有错误（此处与cyclic PLA使用的循环方式有所不同，不是按顺序一个一个的查看是否符合条件，而是在n个点中随机的抽取，这种方式可以增加其寻找最优解的速度）
3. 和PLA一样使用公式2-5进行修正.
4. 如果有了修正，则计算出刚刚修正过的权值向量和上一个权值向量到底谁犯的错误比较少，将少的保留重复第2步到第4步的动作。
5. 假如很长时间都没有新的权值向量比当前的权值向量犯错更少，则返回该向量作为函数g。

流程图如下：
2. 机器学习基石-When can Machine Learn? - Learning to Answer Yes or No

图五 Pocket Algorithm Procedure

②优缺点分析

优点：Pocket算法不需要考虑数据集是否线性可分，都可以进行

缺点：每有一个错误点，都要遍历整个数据集来获得该店的错误率e，所以计算量会很大


Summary

  1. 首先介绍了Binary Classification中最简单的PLA算法
  2. 然后讨论了PLA算法能在某一步之后停下来。
  3. 最后讨论了PLA算法有缺陷：数据必须线性可分。所以根据这个缺点，引用了Pocket算法


Reference

[1]机器学习基石(台湾大学-林轩田)\2\2 - 2 - Perceptron Learning Algorithm (PLA) (19-46)

相关推荐