02 Learning to Answer Yes/No

从最简单最基础的二分类问题出发，演示一个简单机器学习算法PLA的完整过程，见详细课件。

回顾

The Learning Problem:

takes

and

to get

that approximate target function

.

这节课foucus在Hypothesis Set，用Perceptron(linear binary classifiers)演示如何解决二分类问题。如根据用户age/salary/等特征判定是否发放信用卡。

PLA算法

算法形式极其简洁，权重x特征，大于零正例；小于零负例。

算法迭代步骤，关键点是有错才改：

• 初始化

• 找一个误分类点

• 更新权重

• 直到没有误分类点，返回

最重要的是当发现误分类点时，更新权重：

Intuition

ml-foundations-pla-intuition

最直观的Intutiton，每一步更新如何使结果更好？

: 误分则

和

夹角大于90度，更新

后使其往

靠近，夹角变小

: 误分则

和

夹角小于90度，更新

后使其离

更远，夹角变大

收敛性证明

PLA算法有前提是数据集线性可分。

线性可分: Exists perfect

such that

如果数据集线性可分，能保证算法收敛吗？如何证明？思路是

• 假设目标

完美分开数据集

• 证明每一轮

至少线性增加

• 证明每一轮

长度无法达到线性增加

• 其夹角会递减，有限迭代后，

会收敛到

Inner product of

and

grows fast; length of

grows slowly. PLA ‘lines’ are more and more aligned with

then halts.

因为

将每个数据都正确分类，所以：

利用归纳法容易得到：

证明每次迭代，其內积至少是线性增长。內积大一定程度上反映两个向量夹角更接近，当然还需要考虑其长度。

考虑向量长度：

其中：

可以看到，向量长度增加速度为

，达不到线性。且

长度固定，综合上面两个结论：

最后推论出

存在上界：

PLA改进

PLA只能处理线性可分数据集，Pocket PLA稍微改进：

If

makes fewer mistakes than

, replace

by

.

数据集不可分情况下也能保证找到较优的解。