机器算法验证 - SVM：为什么非支持向量的 alpha 为零，为什么大多数向量的 alpha 为零？ - 吾爱随笔录

机器算法验证支持向量机监督学习拉格朗日乘数

2022-03-28 14:29:07

在 SVM 计算边际的优化问题中，我们使用拉格朗日乘子来插入约束：现在我们要计算。据说为 0。这个陈述是如何从上述等式推导出来的？那怎么证明呢？

L (w, b, α) = \frac{1}{λ} | w | - \sum α (y_{i} (w * x_{i} + b) - 1)

$L(w,b,\alpha)= \frac{1}{\lambda}|w| - \sum \alpha (y_i(w*x_i+b) -1)$

α

$\alpha$

α

$\alpha$

更新：
如果我们使用 KKT 条件求解 SVM 的对偶，我们有：使用的主要目标之一对偶，是可以更有效地计算，因为上面的方程和事实，大多数，，因此我们只需要关注，这是一小部分。

w_{i} = \frac{1}{λ} Σ_{i = 1}^{N} α_{i} y_{i} x_{i}

$w_i = \frac{1}{\lambda} \Sigma_{i=1}^{N}\alpha_i y_i x_i$

w

$w$

i \in [N]

$i\in[N]$

α_{i} = 0

$\alpha_i = 0$

{x_{i}, y_{i} : α_{i} \neq 0}

$\{x_i,y_i:\alpha_i \neq 0\}$

我的问题是：为什么大多数 = 0？ $\alpha_i, i\in [N]$

在几何上，据说正好位于超平面或上的数据点。我不确定这是不是真的。如果是这样，那如何证明呢？ $\alpha_i\neq 0$ $\{x:w^Tx - b = 1 \}$ $\{x:w^Tx - b = -1 \}$

3个回答

我找到了我的问题的答案，可以很好地解释几何。
我们知道 KKT 条件的互补条件是：因此，在一个 KKT 点中，至少会发生以下一种情况：

α \geq 0, α (y_{i} (w^{T} x_{i} + b) - 1) = 0

$\alpha\geq0, \alpha(y_i(w^Tx_i + b) - 1) = 0$

情况 1：情况 2： $\alpha_i=0$
$y_i(w^Tx_i +b) - 1 =0$

此外，我们知道 SVM 边缘的超平面具有以下方程：

使用边距创建以下半空间：

因此，对于任何被正确分类并且确实位于正确半空间内部的和因此，对于这些点“案例 2”被违反，因此“案例 1”，即 $x_i:y_i=1$ $x_i:y_i=-1$

y_{i} (w^{T} x_{i} + b) - 1 > 0

$y_i(w^Tx_i +b) -1 > 0$ $\alpha_i = 0$ 必须为真，这意味着

α_{i} = 0

$\alpha_i = 0$ 对于所有正确分类并位于其半空间内部的点。
因此，

α_{i}

$\alpha_i$ 只能不等于

0

$0$ ，如果“案例2”为真，即

y_{i} (w^{T} x_{i} + b) - 1 = 0

$y_i(w^Tx_i+b) - 1 = 0$ . 这对

x \in H_{1}

$x \in H_1$ 或者

x \in H_{- 1}

$x \in H_{-1}$ 这是位于边缘超平面上的点。而这一点是有限的。

因此，对于大多数点 $\alpha_i = 0$ ，除了位于边缘的点是有限的。

支持实际上是一个向量，其 $\alpha$ 非零。这是一个定义，从这里的等式没有什么可以证明的。

支持向量可以定义为位于正或负超平面上的那些向量，即那些 $y_i (w^Tx_i + b) -1=0$ . 对于非支持向量， $y_i (w^Tx_i + b) -1$ 非零。

拉格朗日乘数的对偶形式由下式给出：

$L_p = min_{w,b}max_{\alpha\geq 0} \left(\quad\dfrac{1}{2}||(w)||^2 - \sum_i \alpha_i(y_i (w^Tx_i + b) -1)\right)$

因此，对于非支持向量， $\alpha_i = 0$ ，否则内部优化将“炸毁”

其它你可能感兴趣的问题