SVM（支持向量机）- 基本思想(一)

Reference:

Pluskid系列博客
《Pattern recognition and machine learning》CM Bishop - 2006

《convex optimization》SP Boyd, L Vandenberghe – 2004

说明：本系列纯粹是pluskid博客的狗尾续貂之作，写下了只是想让自己踏踏实实学点东西，如果看懂了pluskid的博客，那就直接Pass,如果有不清楚的地方，说不定我的博客里面会给你一些启发。

1 Basic idear

Figure 1

Question :

假设样本为二维的情况，图中有红蓝两种点，代表已经有的两类样本数据，我们需要在红、蓝之间找一个分界面，使得分界面的一边是一类，另一边是另一类。很明显，会有很多个满足条件的平面，比如图中的紫色和深红色的两条直线，我们要找的是一个最优的超平面，使得对后续要分类的测试点，也能取得比较准确的分类，即泛化能力要强。例如，现在我们要对黑色和黄色两个测试点进行分类，我们仅有的信息就是蓝方和红方的分布，观察这两方的分布，直观上我们认为，黑色该属于蓝方，而棕色该属于红方。然而，紫色直线把黑色测试点分类为红方，黄色点分为蓝方，因此，相对深红色直线泛化能力略微逊色了点。那怎样的一条直线才是泛化能力最好的呢？这就是技术活了，直观上我们觉得紫色直线靠，两点太近了将紫色直线顺时针旋转一点点会效果更好，比如转到红色直线的位置。那红色直线具有什么样的属性呢？一般这种问题都会转化成为一个最优化问题，让数学来回答这个问题，SVM也不例外。

Answer :

既然很多直线都能满足，那我们就找这里面最特殊的一条，特殊在于距离。在能正确区分训练集的直线集中，计算它门到最近样本点的距离，我们选择使得此距离最大的那条直线。

Formulation:

（1）点到直线的距离：

Figure 2

直线方程为，求点到该直线的距离

取直线上任意一点，则将向量往法向量投影得到

同时满足代入上式得

但是求出来的距离在直线下方为负，在直线上方为正，而我们一般的类别标号就是取因此，就都统一为正的了。不过实际上每类样本取正还是负都没关系。假设为直线上方的样本点标号为时的解，现在将其变为负，即取为，要满足，显然此时的解。即法向量变换方向，也取反。直接决定了分界直线相对原点的偏移。易得原点到分界直线的距离。