2. Learning-to-answer-yes-no

When can machines learn? (illustrative + technical)

机器学习的过程就是 learning algorithm A 从两个输入:数据 data 以及算法集合 hypothesis set 中找到一个 hypothesis g,使得 g 与真实的 target function f 最接近,这节课的重点就是学习一个具体的 hypothesis H。

Perceptron hypothesis set

一个简单的 Hypothesis Set: Perceptron: 如果决定授权信用卡,则 h(x) = +1, 如果不授权信用卡,则 h(x) = -1.

从上图中可以明显看出,一个具体的 h,与各个权重 w 以及设定的阈值 threshold 有关。这样的 h 在历史上被称作感知器 perceptron。这些字的来源由早期研究类神经网络而来。

其向量的表示为:

以2维的向量为例,h 的具体样子为:

从几何的角度讲,感知器 perceptron 实际上就是平面上的一条条线,因此又被称作 linear classifiers。即:

perceptron <=> linear classifiers

perceptron learning algorithm (PLA)

上一节,我们了解了一个可能的 H 的样子,也就是平面上所有的线(或者是高维空间里面的一个平面)。现在的问题是,如何设计一个算法,从所有的线 H 里面选出一条最好的线出来。

一条最好的线 g 的定义就是让 g ≈ f,但是难点在于 f 是未知的。唯一可以确定的是 data 是从 f 中产生的。所以,可以先让 g 在看过的 data 里面与 f 越接近越好,或者最好是一模一样(个人注释:over fitting)。

接下来就是在已经看过的数据 data 里面找一条线,这条线要能够正确的将 data 分开。难点在于 H 是无限的。

所以解决的方式是,任意找一条线,然后再依次去修正它(稍微移动一下)。

下面使用线的权重 w 来表示一条线,具体的算法过程为:

从 w0 开始,找到在数据 D 中分类错误的点(xn, yn),即:

For t = 0,1,2…:

  1. 找到一个 wt 分类错误的点 (xn(t), yn(t)): sign(wTt) ≠ yn(t)

  2. 修正这个错误通过:wt+1 <– wt + yn(t)Xn(t)

  3. 一直修正到所以的数据都分类正确了。

修正的方法有两种:

  • 一种是想要的符号是正的,结果是负的:这种情况表明, W 与 X 的角度过大(超过90度了),因此修正方法为将 W 转到 W 与 X 的中间位置上来。
  • 另一种是想要的符号是负的,结果为正的:这种情况表明,W 与 X 的角度过小(小于90度了),因此修正方法为将 W 转到远离 X 的位置上去。

本质上, W 为分类器(直线) 的法向量:

修正的过程为:






两个问题:

  • 修正的过程一定停下来吗?
  • 停下来的线是 g ≈ f 吗?

Guarantee of PLA

PLA 停下来的条件:数据线性可分。

思考:假设数据D线性可分(linear separable),PLA一定会停下来吗?

Wf:表示真实的线
Wt:表示调整的线

衡量Wt和Wf很接近,可以对两条线做内积。内积越大,两条线越接近。

即:linear separable D <=> 存在 Wf 使得:yn = sign(wTfxn)

还要处理向量长度的问题:

Non-Separable data

  • 线性可分表明:Wt 和 Wf会越来越接近。
  • 用错误修正表明:Wt 的长度会缓慢成长。

如果数据D并不是线性可分怎么办?

最好的分割线:在数据 D 上,犯错误最小的线。

贪心算法:新的线与旧的线进行对比。

Why can machines learn? (theoretical +illustrative)

How can machines learn? (technical +practical)

How can machines learn better? (practical + theoretical)