QxRed

发信人: qxred (独行者的阔步), 信区: AI
标  题: 看了篇paper,加深了我对svm几何解释的理解
发信站: 日月光华 (2007年07月26日15:16:50 星期四), 站内信件

svm在几何上的解释，一直以来书上都是用最大化margin解释的。直到看了
Koby Crammer, Yoram Singer
On the algorithmic implementation of multiclass kernel-based vector machines
之后，才对svm的几何解释有了新的认识。用margin最大化来解释svm，一个不足之处在
于无法解释多类的情况，而用参考文献的解释就很easy了
假设空间有n个m维点t_1,...,t_n，分为k类，1<=y_i<=k为t_i的类标记。
记x_i=(t_i,1)'，即一个m+1维的向量，在t的最后追加一个1。
svm试图找到k个投影方向，w_1...w_k，使得
(1)数据x_i在w_{y_i}上的投影最大，即w_{y_i}'x_i > w_{j!=y_i}'x_i。
(2)在满足(1)的w中选择||w_1||^2+...+||w_k||^2最小的那个
第一个条件保证了所有类别分类正确: x_i在y_i对应的方向w_{y_i}上的投影是最大的
第二个条件是找泛化错误最小的w。因为泛化错误与w的l_2范式有关。

现在我们从这个解释出发，推导出两类svm的最大化margin的解释。

假设只有两类，y=1,2，根据上面的定义，svm试图找到两个方向w_1,w_2满足(1)(2)
我们记w_i=(v_i,b_i)'，即v_i是去掉w_i最后一个元素得到的方向。注意x_i=(t_i,1)'
这样，(1)(2)可以变为找到这样的v_i,b_i使得
(3)v_{y_i}'t_i + b_i > v_j't_i + b_j, j!=y_i
回顾一下大化margin解释中svm试图找到的是一个v,和b，而这里需要找两个。下面我们
要证明只有v_1=-v_2,b_1=-b_2时(4)才能满足
假设v_1,v_2,b_1,b_2满足了(3)(4)
于是，对于所有y_i=1的t_i
v_1't_i+b_1>v_2't_i+b_2
=> (v_1-v_2) t_i + (b_1-b_2) > 0
同理可知，对所有y_i=2的t_i
(v_2-v_1) t_i + (b_2-b_1) > 0
因此，v_1'=(v_1-v_2)/2 ,b_1'=(b_1-b_2)/2, v_2'=-v_1', b_2'=-b_1'满足(3)
且
||v_1'||+b_1'^2+ ||v_2'||+b_2'^2 <= ||v_1||+b_1^2+ ||v_2||+b_2^2
因此，要使得(4)成立，v_1必须=-v_2, b_1=-b_2
所以在两类问题中，svm总是找两个相反的投影方向，这就和最大化margin的解释一致了
--
机器与数据，有这些就足够了
※ 来源:·日月光华 bbs.fudan.edu.cn·[FROM: 10.11.3.132]                                                               
※ 修改:·qxred 於 07月26日15:19:19 修改本文·[FROM: 10.11.3.132]