支持向量机 KKT条件

### 支持向量机中的KKT条件解释

#### KKT条件概述
在优化理论中，Karush-Kuhn-Tucker(KKT)条件是用于求解带有不等式约束的非线性规划问题的一组必要条件。当目标函数和约束均为凸时，这些条件也是充分条件[^3]。

对于支持向量机(SVM)，其核心在于通过拉格朗日乘子法将原始的带约束最小化问题转化为无约束的最大化对偶问题。具体来说，在构建SVM模型过程中引入了松弛变量ξi以及对应的惩罚参数C来处理软间隔情况下的分类问题。此时所形成的最优化问题是：

\[
\min_{w,b,\xi} \frac{1}{2}\|w\|^2+C\sum_i^n\xi_i \\
s.t.\quad y^{(i)}(\langle w,x^{(i)}\rangle+b)\geq 1-\xi_i,\\
\quad \xi_i\geq0,
\]

这里\(y^{(i)}\)代表样本标签，而\(x^{(i)}\)则是相应的特征向量。为了简化表达并利用核技巧扩展至非线性场景，可以进一步转换成仅含α作为未知数的形式:

\[
L_D=\sum_i^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^ny^{(i)}y^{(j)}\alpha_i\alpha_j<x^{(i)},x^{(j)}>
\]

其中，α即为拉格朗日乘子数组的一部分；<.,.>表示两个向量之间的内积运算符。最终得到的支持向量机决策规则如下所示：

\[
f(x)=sign[\sum_{SV}s_y^{(i)}\alpha_i<K(x_s,x)>+b],
\]

这里的\(K(x_s,x)\)便是所谓的核函数，它能够有效地计算任意两点间经过映射后的相似度得分而不必显式地知道具体的φ()形式[^5]。

#### KKT条件的具体应用
针对上述提到的标准型二次规划(QP)问题及其对偶版本，满足KKT条件意味着存在一组最优解使得下列关系成立：

- 对于所有的训练样例而言，如果该点位于最大间隔之外，则对应的α应等于零；
- 若某一样品正好处于边界上成为支撑向量的一员，则它的α介于[0,C]之间；
- 当某个数据点被错误划分从而落入另一侧区域之内时，那么相应位置处的α应当严格大于零直至达到上限值C为止。

以上性质可以通过下面几个公式更加精确地描述出来：

\[
\begin{aligned}
&\text{(a)} &&\alpha_i[y^{(i)}g(x^{(i)})-1+\xi_i]=0, &\forall i\\
&\text{(b)}&& C-\alpha_i-\mu_i=0, &\forall i\\
&\text{(c)}&& g(x^{(i)})=(w^\top x^{(i)}+b), &\forall i\\
&\text{(d)}&& \xi_i\geqslant0, &\forall i\\
&\text{(e)}&& \alpha_i\in[0,C],&\forall i.
\end{aligned}
\]

特别值得注意的是第一条方程式(a)，这实际上体现了互补松弛定理的精神——只有那些恰好落在超平面两侧边缘上的点才会贡献非零权重给总的判别函数；其余大部分内部或外部的数据都将因为乘上了因子α而自然消失不见。

def check_kkt_conditions(alpha, y, X, b, C):
    """
    Check whether the given parameters satisfy the KKT conditions of an SVM.

    Parameters:
        alpha (numpy.ndarray): The Lagrange multipliers array.
        y (numpy.ndarray): Labels for each training example (+/- 1).
        X (numpy.ndarray): Feature vectors for all examples.
        b (float): Bias term from the decision function.
        C (float): Regularization parameter controlling trade-off between margin size and classification error.

    Returns:
        bool: True if KKT conditions are satisfied within numerical tolerance; False otherwise.
    """

    n_samples = len(y)

    # Compute predictions using current model parameters
    pred = np.dot(X, (alpha * y).T) + b
    
    residuals = y * pred - 1 

    condition_a = ((residuals >= 0) | (np.isclose(residuals, 0)) & (alpha > 0)).all()
    
    condition_b = (((alpha <= C) & (alpha >= 0))).all()

    return condition_a and condition_b