CMSC 5724 Data Mining and Knowledge Discovery - Lecture 06

• Review
• SVM problem
• Optimal Plane
• Approximate Plane

Review

用基于VC-dimension 来限定 generalization error，所以任何分割平面都有很小的 generalization error
definition plane 不够好，所以需要第二个theorem。第二个 theorem 表示，如果能够增加 margin，可以更好地限制 generalization error。

SVM problem

找到一个有着最大 margin 的分割平面。一个用来解决这个问题的算法叫做 “support vector machine”(SVM)

Optimal Plane

将过原点的分割平面复制两份，两个有相同的移动速度，一个向上平移，一个向下平移。一旦碰到一个 S 中的点就会停止。

distance between π- and π+

因此，分割平面的 margin w · x = 0 是 1 / |w|

Approximate Plane

一个分割平面是由 w · x = 0 定义的，目标是去找到一个好的 w。我们仍然是使用 Perceptron，但是我们不仅是当点落在分割平面错误的一侧时会调整 w，也会在点过于靠近平面时进行调整。

现在，我们假设给定一个任意的值

点 p 导致 violation 的几种情况如下所示：

• 它与平面 w · x = 0 的距离小于 ，无论它的 label 如何
• p 的 label 是 1，但是 w · p < 0
• p 的 label 是 -1，但是 w · p > 0

Margin Perceptron

以 w = 0 开始迭代，在每次迭代中，找 violation porin p ∈ S。如果找到，那么算法会如下方式调整 w

• 如果 p 的 label 为1，则 w = w + p
• 否则，w = w - p

What if γguess > γ*？

有可能会停止，甚至2倍于 γ*，也有可能，不过概率会再低50%，如果3倍，那么几乎不可能。

Theorem

如果 γguess ≤ γ*，margin Perceptron 会终止在最多次迭代，并且返回一个 margin 至少为 的平面。

Corollary

如果算法进行了 1 + R^2/γguess^2 次调整，那么 γguess > γ*

Proof

• 假设 γguess ≤ γ*

• 根据 theorem，算法应该调整次数 ≤ R^2 / γ*^2。

  

根据推论，就算你做了一些错误的做法，算法也不会永远迭代下去。因为如果一直迭代下去，会违反假设 γguess ≤ γ*

halving-technique

How to supply a guess value？

从一个很大的 γguess 开始，然后逐渐降低

Proof

Incremental Algorithm

然后重复这个过程。

Theorem

• incremental algorithm 返回一个 margin 至少为 γ*/4 的分割平面。
• 它总共会进行 O(R^2/γ*^2) 次迭代

Proof