Udacity Machine Learning Support Vector Machine
会选择中间的那条线,为什么没有选择平行的另外两条线,因为它们属于 Overfitting ,过度相信了 training data,
注意此时的 y 是分类用的 label,要么是 +1,要么是 -1 。
需要思考一个问题是,在沿着这条线上的点,它们的 Label 是什么呢?是0。
所以这个 Boundary Line 会有3个可能值,同时想要两条灰色线之间的距离最大。
可以在两条灰色线各取一个点,然后计算它们之间的距离,也就是在 +1 和 -1 的两条线上取点。
x1-x2 和这条线的方向是一样的,我们想要这条线达到最大,那就需要 norm(W) 越小,等式左边的部分叫做 Margin。
这样就可以很好地分类。而这个问题就转化到了等式右边,也就是要最大化 2/norm(W),并且可以正确地分类 。 把这个问题转化为数学问题是:
而最大化 2/norm(W) 这个问题,可以进一步转化为更简单的问题,这是个 Quadratic Programming Problem:
关于上面这个问题,有一些特质: 1.如果知道了 alpha,就可以得到 w,知道了 w,就可以知道 b
2.通常情况下,大多数 alpha=0,意味着这些点对w没有影响 也就是说,为了找到这个解,有些 vector 是没有贡献的,你只需要从少数的 vector 就可以获得找到最优 W 的 support。
直观上看,0-alpha 就是离 Decision Boundary 比较远的那些点,它们很难对这条线做贡献。
有点像 KNN,因为只有 local points 起作用,但是前提是你已经知道哪些 points matter。 求解这个问题,其实是在找到底哪些点可以 throw away。
Xi transpose Xj,意义是,一个向量在另一个向量的投影,如果垂直则为0,如果方向相同,则为正,如果相反,则为负,所以这是一个 similarity 的表示。
有时并不能完全地分出两类,但是可以让误差最小。
一类在圈内,一类在圈外,用 phi 这个三维的函数就可以分开,而不需要事先知道谁是正是负。但是却不需要用 phi,因为它可以用 (X‘T)^2 来表示。
意义就是 向更高维度的空间投影,在高维空间里就可以被 linearly seperated。
下面这几种形式都可以作为 kernel。 第三个是多项式。 第四个是 radial basis kernel,如果 x和y 很近,那么 k 就趋近于 1,如果 x和y 很远,那么 k 就趋近于 0,而且加上平方之后,这个还是对称的。 第五个更像是 sigmoid。 kernel function 可以有很多,而且它的应用也很广,可以用于 string 和 figure。 这些都属于 Mercer Condition,是一种用距离去衡量的方法,而不是随意地构造。
1.Margin 很重要,它关系着 Generalization 还是 Overfitting 2.目标是 Margin 的最大化 3.Margin 最大化的方法:Quadratic Problem 4.在QP中知道了什么是 Support Vector,只需要一个子集就可以建立 Classifier 5.Kernel Trick:通过向高维空间投影,把低维的非线性 Boundary 转化为高维空间的线性 classifier。
另外关于SVM,July有一篇非常详细的博文: http://blog.csdn.net/v_july_v/article/details/7624837