# SMO

## 对偶问题上，上面已知对偶形式：

$$
\begin{aligned}
& argmax\_{\alpha}\sum\_{i=1}^{N}\alpha\_i-\frac{1}{2}\sum\_{i=1}^{N}\sum\_{j=1}^{N}y\_iy\_j\alpha\_i\alpha\_jk(x\_i,x\_j)\\
\&s.t.
\begin{cases}
\sum\_{i=1}^{N}\alpha\_iy\_i=0\\
0 \le\alpha\_i \le C,i=1,2,...,N
\end{cases}
\end{aligned}
$$

## SMO算法求解

在SMO算法中的思想是，每次选择一对变量$$(\alpha\_i,\alpha\_j)$$进行优化，其余$$N-2$$个固定看作是常量, 因为在SVM中，$$\alpha$$并不是完全独立的，而是具有约束的:

$$
\sum\_{i=1}^{N}\alpha\_iy\_i=0
$$

因此一个只选一个ai，那么ai可以被其它表示，就没意义了，所以选两个。

假设我们选取的两个需要优化的参数为$$\alpha\_1,\alpha\_2$$, 剩下的$$\alpha\_3,\alpha\_4,....,\alpha\_m$$则固定作为常数处理，

将SVM优化问题进行展开，把与$$\alpha\_1,\alpha\_2$$无关的项合并成常数项C，这里省略了$$\alpha\_3+\alpha\_4+...+\alpha\_m=C$$，因为其对max函数无意义，变成：

$$
\begin{aligned}
\&max\_{\alpha\_1,\alpha\_2}W(\alpha\_1,\alpha\_2)=\alpha\_1+\alpha\_2-\frac{1}{2}k\_{11}\alpha\_1^2-\frac{1}{2}k\_{22}\alpha\_2^2-y\_1y\_2k\_{12}\alpha\_1\alpha\_2-y\_1\alpha\_1\sum\_{i=3}^{N}y\_i\alpha\_ik\_{i1}-y\_2\alpha\_2\sum\_{i=3}^{N}y\_i\alpha\_ik\_{i2}\\
\&s.t.
\begin{cases}
\alpha\_1 y\_1+\alpha\_2 y\_2=0-\sum\_{i=3}^{N}y\_i\alpha\_i=\xi\\
0 \le \alpha\_i \le C,i=1,2
\end{cases}
\end{aligned}
$$

### 先假设求出来更新关系了

**考虑剪辑问题**

* 因为$$y\_1,y\_2$$只能是1或-1，因此$$\alpha\_1,\alpha\_2$$的关系被限制在盒子里的一条线段上（只能是a1-a2/a1+a2两种情况，既$$y\_1,y\_2$$要么相一致要么不一致）
* 所以两变量的优化问题实际上仅仅是一个变量的优化问题（一个能由另一个得出），我们假设是对$$\alpha\_2$$的优化问题,所以只存在2幅图的情况：

1）**y1!=y2（二者不一致）**，则根据上面的约束$$\alpha\_1y\_1+\alpha\_2y\_2=k$$，这里的k是上面的$$\xi$$，有$$\alpha\_1-\alpha\_2=k$$，L，H为约束下的最小$$\alpha\_2$$，最大值。有下图关系

![](/files/-LpJXFR1kk_F3w7YIKgM)

2）**y1=y2**

![](/files/-LpJXFR4T5eV5vcwRjzl)

```python
if self.Y[i1] == self.Y[i2]:
      L = max(0, self.alpha[i1] + self.alpha[i2] - self.C)
      H = min(self.C, self.alpha[i1] + self.alpha[i2])
 else:
      L = max(0, self.alpha[i2] - self.alpha[i1])
      H = min(self.C, self.C + self.alpha[i2] - self.alpha[i1])
```

则考虑剪辑，也就是现在通过迭代得到一个新的数，这个数该如何替换原来的那个数：

设上面那两个要求的$$\alpha\_1,\alpha\_2$$，当前为$$\alpha\_1^{old},\alpha\_2^{old}$$，现在通过SMO迭代得到这两个数的新的数为$$\alpha\_1^{new},\alpha\_2^{new}$$,考虑上面的约束：

$$
\begin{cases}
L \le \alpha\_2^{new} \le H\\
y\_1 \ne y\_2:L=max(0,\alpha\_2^{old}-\alpha\_1^{old}),H=min(C,C+\alpha\_2^{old}-\alpha\_1^{old})\\
y\_1 = y\_2:L=max(0,\alpha\_2^{old}+\alpha\_1^{old}-C),H=min(C,\alpha\_2^{old}+\alpha\_1^{old})
\end{cases}
$$

记输入xi预测值与真实值之差：

$$
E(x\_i)=f(x\_i)-y\_i=(\sum\_{j=1}^{N}\alpha\_jy\_jk(x\_j,x\_i)+b)-y\_i
$$

```python
def _E(self, i):
    return self._f(i) - self.Y[i]
```

**后面通过SMO会得到这样一个参数更新方式，此时还未剪辑参数范围：**

$$
\begin{aligned}
&\alpha\_2^{new,uncut}=\alpha\_2^{old}+\frac{y\_2(E\_1-E\_2)}{\eta}\\
&\eta=k\_{11}+k\_{22}-2k\_{12}=||\phi(x\_1)-\phi(x\_2)||
\end{aligned}
$$

则考虑上剪辑，上面两个参数**最终更新**方式为：

$$
\alpha\_2^{new}=
\begin{cases}
H,\alpha\_2^{new,uncut} >H\\
\alpha\_2^{new,uncut} , L \le \alpha\_2^{new,uncut} \le H\\
L,\alpha\_2^{new,uncut} < L
\end{cases}
$$

得到$$\alpha\_2$$后，$$\alpha\_1$$则比较简单，直接求得：

$$
\alpha\_1^{new}=\alpha\_1^{old}+y\_1y\_2(\alpha\_2^{old}-\alpha\_2^{new})
$$

为什么？因为：

$$
\begin{aligned}
&\alpha\_1^{old}y\_1+\alpha\_2^{old}y\_2=\xi \to \alpha\_1^{old}+\alpha\_2^{old}y\_2 y\_1 =\xi y\_1\\
&\alpha\_1^{new}+\alpha\_2^{new}y\_2y\_1=\xi y\_1\\
&\alpha\_1^{new}-\alpha\_1^{old}+(\alpha\_2^{new}-\alpha\_2^{old})y\_2y\_1=0 \to \alpha\_1^{new}-\alpha\_1^{old}=y\_1y\_2(\alpha\_2^{old}-\alpha\_2^{new})
\end{aligned}
$$

也就是1）每次通过SMO得到（未剪辑的）更新值，2）然后依据之前的约束得到的剪辑关系，进行剪辑，3）得到最终本轮这个参数的更新值。

```python
   def _compare(self, _alpha, L, H):
        # 剪辑操作
        if _alpha > H:
            return H
        elif _alpha < L:
            return L
        else:
            return _alpha
```

a1,a2更新：

```python
# 边界约束
if self.Y[i1] == self.Y[i2]:
    L = max(0, self.alpha[i1] + self.alpha[i2] - self.C)
    H = min(self.C, self.alpha[i1] + self.alpha[i2])
else:
    L = max(0, self.alpha[i2] - self.alpha[i1])
    H = min(self.C, self.C + self.alpha[i2] - self.alpha[i1])

# 预测与实际误差
E1 = self.E[i1]
E2 = self.E[i2]

# 后面分母那个 =k11+k22-2k12的值
eta = self.kernel(self.X[i1], self.X[i1]) + self.kernel(self.X[i2], self.X[i2]) - 2 * self.kernel(self.X[i1], self.X[i2])

if eta <= 0:
   # print('eta <= 0')
   continue
# 未剪辑a2
alpha2_new_unc = self.alpha[i2] + self.Y[i2] * (E1 - E2) / eta
#剪辑后a2
alpha2_new = self._compare(alpha2_new_unc, L, H)
#由a2得到a1
alpha1_new = self.alpha[i1] + self.Y[i1] * self.Y[i2] * (self.alpha[i2] - alpha2_new)
#更新最终值
self.alpha[i1] = alpha1_new
self.alpha[i2] = alpha2_new
```

## 证明假设

证明上面的公式为什么这样更新$$\alpha$$：

$$
\begin{aligned}
&\alpha\_2^{new,uncut}=\alpha\_2^{old}+\frac{y\_2(E\_1-E\_2)}{\eta}\\
&\eta=k\_{11}+k\_{22}-2k\_{12}=||\phi(x\_1)-\phi(x\_2)||
\end{aligned}
$$

根据：

$$
\alpha\_1 y\_1+\alpha\_2 y\_2=0-\sum\_{i=3}^{N}y\_i\alpha\_i=\xi
$$

得：

$$
\alpha\_1=(\xi-\alpha\_2y\_2)y\_1
$$

记：

$$
\begin{aligned}
v\_i &=\sum\_{j=3}^{N}\alpha\_j y\_j(x\_j,x\_i)\\
&=\sum\_{j=1}^{N}\alpha\_j y\_j(x\_j,x\_i)+b-\sum\_{j=1}^{2}\alpha\_j y\_j(x\_j,x\_i)-b\\
&=f(x\_i)-\sum\_{j=1}^{2}\alpha\_j y\_jk(x\_j,x\_i)-b
\end{aligned}
$$

带入以上关系这个式子里面：

$$
\begin{aligned}
\&max\_{\alpha\_1,\alpha\_2}W(\alpha\_1,\alpha\_2)=\alpha\_1+\alpha\_2-\frac{1}{2}k\_{11}\alpha\_1^2-\frac{1}{2}k\_{22}\alpha\_2^2-y\_1y\_2k\_{12}\alpha\_1\alpha\_2-y\_1\alpha\_1\sum\_{i=3}^{N}y\_i\alpha\_ik\_{i1}-y\_2\alpha\_2\sum\_{i=3}^{N}y\_i\alpha\_ik\_{i2}
\end{aligned}
$$

得到：

$$
\begin{aligned}
max\_{\alpha\_2}W(\alpha\_2)&=(\xi-\alpha\_2y\_2)y\_1+\alpha\_2-\frac{1}{2}k\_{11}\[(\xi-\alpha\_2y\_2)y\_1]^2- \frac{1}{2}k\_{22}\alpha\_2^2-y\_1y\_2k\_{12}\[(\xi-\alpha\_2y\_2)y\_1]\alpha\_2- \ & y\_1\[(\xi-\alpha\_2y\_2)y\_1]v\_1- y\_2\alpha\_2 v\_2\\
&=(\xi-\alpha\_2y\_2)y\_1+\alpha\_2-\frac{1}{2}k\_{11}(\xi-\alpha\_2y\_2)^2- \frac{1}{2}k\_{22}\alpha\_2^2-y\_2k\_{12}(\xi-\alpha\_2y\_2)\alpha\_2- \ & (\xi-\alpha\_2y\_2)v\_1- y\_2\alpha\_2 v\_2
\end{aligned}
$$

对这个求偏导：

$$
\begin{aligned}
\frac{\partial W(\alpha\_2)}{\partial \alpha\_2} &=-y\_2y\_1+1+k\_{11}y\_2(\xi-\alpha\_2y\_2)-k\_{22}\alpha\_2-y\_2k\_{12}\xi+2k\_{12}\alpha\_2+y\_2v\_1-y\_2v\_2\\
&=0

\end{aligned}
$$

上面的合并得：

$$
\begin{aligned}
&(k\_{11}+k\_{22}-2k\_{12})\alpha\_2=y\_2(y\_2-y\_1+\xi k\_{11}-\xi k\_{12}+v\_1+v\_2)\\
& =y\_2(y\_2-y\_1+\xi k\_{11}-\xi k\_{12}+\[f(x\_1)-\sum\_{j=1}^{2}\alpha\_j y\_jk(x\_j,x\_1)-b]-\[f(x\_2)-\sum\_{j=1}^{2}\alpha\_j y\_j k(x\_j,x\_2)-b)
\end{aligned}
$$

代入关系式，**添加新旧标记方便迭代更新：**

$$
\xi=\alpha\_1^{old}y\_1+\alpha\_2^{old}y\_2
$$

得：

$$
\begin{aligned}
&(k\_{11}+k\_{22}-2k\_{12})\alpha\_2^{new,nucut} \\&=y\_2(y\_2-y\_1+\xi k\_{11}-\xi k\_{12}+\[f(x\_1)-\sum\_{j=1}^{2}\alpha\_j^{old} y\_j k(x\_j,x\_1)-b]-\[f(x\_2)-\sum\_{j=1}^{2}\alpha\_j^{old} y\_jk(x\_j,x\_2)-b)\\
&=y\_2(y\_2-y\_1+\xi k\_{11}-\xi k\_{12}+f(x\_1)-f(x\_2)-\sum\_{j=1}^{2}\alpha\_j^{old} y\_j k\_{j1}+\sum\_{j=1}^{2}\alpha\_j^{old} y\_j k\_{j2})\\
&=y\_2(y\_2-y\_1+(\alpha\_1^{old}y\_1+\alpha\_2^{old}y\_2) k\_{11}-(\alpha\_1^{old}y\_1+\alpha\_2^{old}y\_2) k\_{12}+f(x\_1)-f(x\_2)- \\
& \alpha\_1^{old} y\_1 k\_{11}-\alpha\_2^{old} y\_2 k\_{21}+\alpha\_1^{old} y\_1 k\_{12}+\alpha\_2^{old} y\_2 k\_{22})\\
&=y\_2(y\_2-y\_1+\alpha\_2^{old}y\_2k\_{11}-\alpha\_2^{old}y\_2k\_{12}+f(x\_1)-f(x\_2)-\alpha\_2^{old}y\_2k\_{21}+\alpha\_2^{old}y\_2k\_{22})\\
&=y\_2(y\_2-y\_1+(k\_{11}+k\_{22}-2k\_{12})\alpha\_2^{old}y\_2+f(x\_1)-f(x\_2)) \\
&=(k\_{11}+k\_{22}-2k\_{12})\alpha\_2^{old}+y\_2y\_2-y\_2y\_1+y\_2 f(x\_1)-y\_2 f(x\_2)\\
&=(k\_{11}+k\_{22}-2k\_{12})\alpha\_2^{old}+y\_2(\[f(x\_1)-y\_1] -\[f(x\_2)-y\_2])\\
&=(k\_{11}+k\_{22}-2k\_{12})\alpha\_2^{old}+y\_2(E(x\_1) -E(x\_2))
\end{aligned}
$$

也就是：

$$
\begin{aligned}
&(k\_{11}+k\_{22}-2k\_{12})\alpha\_2^{new,nucut} \\
&=(k\_{11}+k\_{22}-2k\_{12})\alpha\_2^{old}+y\_2(E(x\_1) -E(x\_2))
\end{aligned}
$$

除过来变为：

$$
\begin{aligned}
\alpha\_2^{new,nucut} =\alpha\_2^{old}+\frac{y\_2(E(x\_1) -E(x\_2))}{(k\_{11}+k\_{22}-2k\_{12})}
\end{aligned}
$$

也就上面假设得到的公式，至此证明。

## 两个点的选择

前面已经知道固定两个点，然后进行更新了，问题是支持向量SVM有样本数量那么多个点（虽然最终取决定性的是几何间隔上的点），现在的问题是如何选择点去更新？

SMO每个子问题选择两个变量优化，其中**至少一个变量是违法KKT条件的**，也就是说，违反的优先更新。

**第1个变量a1的选择**

SMO称选择第一个变量的过程为**外层循环，外层循环选取违反KKT条件最严重的样本点(xi,yi)对应的ai值作为第一个变量a1**；检测是否满足KKT条件：

一般，外层循环先遍历所有满足0\<ai\<C的样本点（这些点就是支持向量点），如果都满足再遍历整个训练集点，检验是否满足KKT条件。

**第2个变量a2的选择**

SMO算法称选择第二个变量为内层循环，假设我们在外层循环已经找到了α1, 第二个变量α2的选择标准是&#x8BA9;**|E1−E2|有足够大的变化**。E(预测值与真实值之差)。由于α1定了的时候,E1也确定了，所以要想|E1−E2|最大，只需要在E1为正时，选择最小的Ei作为E2，在E1为负时，选择最大的Ei作为E2，可以将所有的Ei保存为列表，加快迭代。

如果内循环找到的点不能让目标函数有足够的下降，可以采用遍历支持向量点来做α2,直到目标函数有足够的下降， 如果所有的支持向量做α2都不能让目标函数有足够的下降，可以跳出循环，重新选择α1。

```python
    def _init_alpha(self):
        # 外层循环首先遍历所有满足0<a<C的样本点，检验是否满足KKT
        index_list = [i for i in range(self.m) if 0 < self.alpha[i] < self.C]
        # 否则遍历整个训练集
        non_satisfy_list = [i for i in range(self.m) if i not in index_list]
        index_list.extend(non_satisfy_list)

        for i in index_list:
            if self._KKT(i):#满足KKT条件就不做下一步计算
                continue

            E1 = self.E[i]
            # 如果E2是+，选择最小的；如果E2是负的，选择最大的
            if E1 >= 0:
                j = min(range(self.m), key=lambda x: self.E[x])
            else:
                j = max(range(self.m), key=lambda x: self.E[x])
            #   找到一对就返回，没找到再循环
            return i, j
```

## 更新完后还需要更新b，因为此时参数变了

当

$$
0 \le \alpha\_1^{new} \le C
$$

时：

$$
y\_1-\sum\_{i=1}^{N}\alpha\_iy\_ik\_{i1}-b\_1=0
$$

于是新的b可更新：

$$
b\_1^{new}=y\_1-\sum\_{i=3}^{N}\alpha\_iy\_ik\_{i1}-\alpha\_1^{new}y\_1k\_{11}-\alpha\_2^{new}y\_2k\_{21}
$$

因为

$$
\begin{aligned}
E(x\_1)=f(x\_1)-y\_1
\=\sum\_{i=3}^{N}\alpha\_iy\_ik\_{i1}+\alpha\_1^{new}y\_1k\_{11}+\alpha\_2^{new}y\_2k\_{21}+b^{old}-y\_1
\end{aligned}
$$

所以可以把b写成有E的式子：

$$
b\_1^{new}=-E(x\_1)-y\_1k\_{11}(\alpha\_1^{new}-\alpha\_1^{old})-y\_2k\_{21}(\alpha\_2^{new}-\alpha\_2^{old})+b^{old}
$$

同样的，如果

$$
0 \le \alpha\_2^{new} \le C
$$

有：

$$
b\_2^{new}=-E(x\_1)-y\_1k\_{11}(\alpha\_1^{new}-\alpha\_1^{old})-y\_2k\_{21}(\alpha\_2^{new}-\alpha\_2^{old})+b^{old}
$$

因此SMO里面本轮b采用更加鲁棒的更新策略，为：

$$
b^{new}=\frac{b\_1^{new}+b\_2^{new}}{2}
$$


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/ml/7-zhi-chi-xiang-liang/svm-smo.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.