本文共 913 字，大约阅读时间需要 3 分钟。

首先理解KKT条件：

若一个优化问题转成对偶问题后，表达式如下：

L(x,a,b) = f(x) + Sum{ ai * gi(x) } + Sum{ bi * hi(x) }

其中，g是不等式约束(将大于号都转化成小于号约束)，h是等式约束。

那KKT条件是函数最优值必须满足三个条件：

• (1) L对各个x求导为0；
• (2) h(x) = 0;
• (3) Sum{ ai * gi(x) } = 0, ai >= 0;

式子(1)和(2)好理解，但式子(3)可以进一步理解为ai取0或者gi(x)取0；

详细理解见

对于SVM对偶问题：

原凸优化表达式为：

min(W,b) max(a) L(W,a,b) = 1/2 * ||W||^2 + Sum{ ai * (1 - yi * (WT * Xi + b)) }

将极值点偏导为0带入后，消去W得到了一个新的需要约束规划的方程：

Max{ L(a) } = Sum{ ai } - 1/2 * Sum{ Sum{ ai * aj * yi * yj * XiT * Xj } }

其中，对于一个样本(Xi,yi)，有一个ai。

解出ai，带回可以计算得到W，b。

即得到支持向量模型:

f(x) = WT * X + b = Sum{ ai * yi * XiT * X } + b

如何计算ai，解法采用使用KKT条件(具体算法细节见SMO算法)：

拉格朗日乘子有约束 ai >= 0;

凸优化极值点有 Sum{ ai * yi } = 0;

综合上述条件发现，新的约束规划方程正好可以满足KKT条件，即：

• ai >= 0;
• yi * f(Xi) - 1 >= 0;
• ai * (yi * f(xi) - 1) = 0;

当满足KKT条件时，对于任意样本(Xi,yi)，总有ai = 0或yi * f(Xi) = 1.

所以，支持向量机的特点在于，训练完成后，大部分训练样本都不保留，最终模型仅与支持向量有关。

转载地址：http://tuwji.baihongyu.com/