为什么支持向量机会有对偶算法?

一句话答案就是,通过对偶算法(Dual Problem)来计算支持向量机(Support Vector Machines,缩写为 SVM )的决策边界会比较简单。

1 原算法与对偶算法
对于支持向量机而言,对偶算法是借助拉格朗日对偶性从原算法(Primal Problem)推出的,两者完全等价,只是求解了不同的条件极值(下面是硬间隔支持向量机的原算法和对偶算法):

从上面的对比可以看出,对偶算法主要有三点改进使得决策边界的求解不再困难:

  • 对偶算法中没有   和  ,这样求解比较简单

  • 对偶算法限制条件中的   很容易消去,在后面的例子中可以看到

  • 更重要的是,原算法的限制条件为较为复杂的线性不等式  ,而消去   的对偶算法,其限制条件只为简单的  ,这会极大地降低求解的难度

这么说可能不太直观,下面会用例子来进一步说明。

2 例子
假设数据集   为:

下面会通过原算法、对偶算法来分别计算硬间隔支持向量机的决策边界。

3 原算法求解
很多资料都没介绍原算法怎么计算,主要是因为原算法中的限制条件为较为复杂的线性不等式  ,要正儿八经地去计算涉及到二次规划中较为复杂的理论。本文也没有打算正面去计算,下面的计算过程会用到一些技巧。

(1)改写条件极值。原算法要求解的条件极值为:

根据该条件极值,首先写出拉格朗日函数:

然后根据拉格朗日乘数法以及KKT 条件,从上述条件极值可以得到下面的方程组:

(2)下面来求解(1)中得到的方程组。改写   可得:

因此:

据此可得: 又: 所以可得: 综合下即有: 代入数据可得: 下面需要分情况讨论。

(3)如果  ,那么意味着  ,又因为决策边界为  ,所以推出  ,那么此时有: 即不满足方程组的条件,所以   不是解。

(4)根据(3),   不能全为 0,所以:

进而可以推出:          (5)因为  ,所以   和   中至少还有一个不为 0 ,假设  ,  ,那么有: 进而可以推出: 因为有  、  ,所以:

解上述线性方程组可得   ,所以最终可得: 进而得到决策边界为: 可以图示如下:

(6)如果假设  ,或所有的  ,是无法求解的,这里就不再赘述。

4 对偶算法求解
对偶算法的限制条件比较简单,所以下面的解法虽然看上去过程也较多,但只要按部就班就可以解出。

(1)消去条件中的  。根据数据集  ,我们要求解的对偶算法的条件极值如下: 由第一个条件可得  ,将其代入要求最小值的目标函数,就得到了新的函数,记作: 这个函数融合了第一个条件,所以要优化的条件极值可以改写为: 实际上这就消去了条件中的  。

(2)通过数据集找到支持向量。根据拉格朗日乘数法以及KKT 条件,从修改后的条件极值可以得到下面的方程组: 根据前两个方程可以算出: 因为:所以最小值没有办法在   取得,此时该怎么办呢?为了说明下面要使用的方法,我们先来考虑简单点的一元凸函数: 该函数的最小值点本来在   的地方,但由于条件   的限制,最终只能在条件的边界处即   处取得最小值:

我们感兴趣的二元凸函数   也是一样的,最小值只能在   的边界处取得,即或者在   或者在   处取得。在三维空间中,  是一个平面,其上的最小值在下面的点处取得: 同样的道理,   也是一个平面,其上的最小值在下面的点处取得: 即分别在   和   处取得,比较两处的函数值:  即条件极值在   处取得,因此有:          (3)根据支持向量求出决策边界。根据对偶算法的结论(这里不再赘述,在网上可以查到,或者在我们课程中可以看到),如果   则说明该点为支持向量,据此可以得到所有支持向量的集合   。根据集合   可求出: 再在支持向量中随便挑选一个点   ,可求出: 所以在本题中有:  进而得到决策边界为: 与原算法得到的结果一样。
(0)

相关推荐