CMSC 5724 Data Mining and Knowledge Discovery - Lecture 04

• Linear classification
• Perceptron
• Theorem
• Proof

Linear classification

训练集 S 是线性可分离的，那么就存在一个 d 维的向量 w，x · w > 0 表示 label 1，x · w < 1 表示 label 2，x · w = 0 是 S 的分割平面。

God ：

• 选择了一个 linear classifier h*
• 选择了一个 X 上的数据集 D

我们：

• 从 D 中取一些样本集

• 从 D 取 x

• y = h*(x)

  那么 God 会返回 (x, y)

errD(h) = Pr[h(x) ≠ h*(x)]

Note: errD(h*) = 0

linear classification 的目标是训练集中学习一个 classifier h，它在 D 上的错误尽可能小

Perceptron

问题：给定一个线性分割的数据集 S，找一个分割平面，该分割平面由权重向量 w 定义，给定一个 linear classifier h，并且 errS(h) = 0。

引理：S （有限的）一定包含一个分割平面。

该算法从 w = (0, 0, … , 0) 开始，以迭代的方式进行。在每次迭代中，寻找一个 violation point p ∈ S

• 如果 p 为 label 1，那么如果 w · p ≤ 0，p 是一个 violation point
• 如果 p 为 label -1，那么如果 w · p ≥ 0，p 是一个 violation point

如果 p 存在，算法会按如下方式调整 w

• 如果 p 是 label 1，那么 w = w + p
• 如果 p 是 label -1，那么 w = w - p

当没有 violation point 的时候，算法会停止

现在我们分析 Perceptron 的迭代次数，给定一个向量 v = (v1, … , vd)，我们定义它的长度为

对于任意 v1，v2，有

定义一个单位向量 u，|u| = 1。

可见 p · u 为 p 距离分割平面的距离。

定义：

S ：样本集

π*：有最大边界的分割平面

γ：π* 的边界

u*：π* 的法向

R：S 的半径，也就是距离分割平面最远的点的距离

w0 = 0

wi：第 i 次调整以后的 w

分割平面的边界由 w 决定

Theorem

Perceptron 会在 w 最多 (R / γ)² 次调整后停止。

Proof

证明最终结论

我们先假定下面两个引理是正确的，后面再证明

我们令 k 为最大调整次数，由引理1我们可以得到，

由引理2我们可以得到，

于是可以推得，

证明引理1

证明引理2