为什么支持向量机会有对偶算法?
一句话答案就是,通过对偶算法(Dual Problem)来计算支持向量机(Support Vector Machines,缩写为 SVM )的决策边界会比较简单。
从上面的对比可以看出,对偶算法主要有三点改进使得决策边界的求解不再困难:
对偶算法中没有 和 ,这样求解比较简单
对偶算法限制条件中的 很容易消去,在后面的例子中可以看到
更重要的是,原算法的限制条件为较为复杂的线性不等式 ,而消去 的对偶算法,其限制条件只为简单的 ,这会极大地降低求解的难度
这么说可能不太直观,下面会用例子来进一步说明。
下面会通过原算法、对偶算法来分别计算硬间隔支持向量机的决策边界。
(1)改写条件极值。原算法要求解的条件极值为:
根据该条件极值,首先写出拉格朗日函数:
然后根据拉格朗日乘数法以及KKT 条件,从上述条件极值可以得到下面的方程组:
(2)下面来求解(1)中得到的方程组。改写 可得:
因此:
据此可得: 又: 所以可得: 综合下即有: 代入数据可得: 下面需要分情况讨论。
(3)如果 ,那么意味着 ,又因为决策边界为 ,所以推出 ,那么此时有: 即不满足方程组的条件,所以 不是解。
(4)根据(3), 不能全为 0,所以:
进而可以推出: (5)因为 ,所以 和 中至少还有一个不为 0 ,假设 , ,那么有: 进而可以推出: 因为有 、 ,所以:
解上述线性方程组可得 ,所以最终可得: 进而得到决策边界为: 可以图示如下:
(6)如果假设 ,或所有的 ,是无法求解的,这里就不再赘述。
(1)消去条件中的 。根据数据集 ,我们要求解的对偶算法的条件极值如下: 由第一个条件可得 ,将其代入要求最小值的目标函数,就得到了新的函数,记作: 这个函数融合了第一个条件,所以要优化的条件极值可以改写为: 实际上这就消去了条件中的 。
(2)通过数据集找到支持向量。根据拉格朗日乘数法以及KKT 条件,从修改后的条件极值可以得到下面的方程组: 根据前两个方程可以算出: 因为:所以最小值没有办法在 取得,此时该怎么办呢?为了说明下面要使用的方法,我们先来考虑简单点的一元凸函数: 该函数的最小值点本来在 的地方,但由于条件 的限制,最终只能在条件的边界处即 处取得最小值: