# 支持向量机-SVM

## 1.线性可分支持向量

考虑二分类，正例样本标签为1，负例为-1

输入：

$$
\begin{aligned}
\&T={(x\_1,y\_1),(x\_2,y\_2),...,(x\_N,y\_N)}\\
\&y\_i \in { +1,-1}
\end{aligned}
$$

学习目标：在特征空间找到分离超平面，能将实例分到不同类，和感知机部分相同，希望得到一个划分超平面：

$$
w^Tx+b=0
$$

通常这个划分超平面无穷多个，但是间隔最大的只有一个，这时解是唯一的。

使得正样本被划分到空间：

$$
w^Tx+b>=1
$$

负样本划分到空间：

$$
w^Tx+b<=-1
$$

## 2.函数间隔、几何间隔

点x和超平面的相对距离可以表示为：

$$
|w^T.x+b|
$$

分类正确时函数结果和y值同号，因此：

$$
y(w^T.x+b)
$$

可以表示正确性/确信度。

**函数间隔：**

样本的：

$$
\hat{\gamma\_i}=y\_i(w^T.x\_i+b)
$$

训练数据集T关于超平面的函数间隔，为所有样本函数间隔的最小值：

$$
\hat{\gamma}=min\_{i=1,...,N}\hat{\gamma\_i}
$$

但是等比例的改变w、b超平面不变，但是函数间隔却放大那么多倍了，因此需要固定住这个距离，变成几何距离，比如固定||w||=1，这样就不能随便缩放了，距离会变。（固定为2，666....也行，除以这个固定数，还是等价于固定为1）

因此引出几何距离，使得样本和超平面之间的距离不是相对的

**几何距离：**

样本的：

$$
\gamma\_i=\frac{y\_i(w^T.x\_i+b)}{||w||}=\frac{\hat{\gamma\_i}}{||w||}
$$

训练数据集T关于超平面的几何间隔，为所有样本几何间隔的最小值：

$$
\gamma=min\_{i=1,...,N}\gamma\_i
$$

### 3.间隔最大化

几何间隔最大化可以保证分离超平面是唯一的，

因此优化问题为：

$$
\begin{aligned}
\&max\_{w,b}\gamma\\
\&s.t...y\_i(\frac{w}{||w||}.x\_i+\frac{b}{||w||})\ge\gamma,i=1,2,...,N
\end{aligned}
$$

下面s.t.是约束，要求最少是几何间隔距离以上

因为几何间隔和函数间隔有关系：

$$
\begin{aligned}
\gamma\_i=\frac{\hat{\gamma\_i}}{||w||}\\
\gamma=\frac{\hat{\gamma}}{||w||}
\end{aligned}
$$

因此优化问题可变为：

$$
\begin{aligned}
& max\_{w,b}\frac{\hat{\gamma}}{||w||}\\
& s.t...y\_i(\frac{w^T}{||w||}.x\_i+\frac{b}{||w||})\ge\gamma=\frac{\hat{\gamma}}{||w||},i=1,2,...,N
\end{aligned}
$$

也就是：

$$
\begin{aligned}
\&max\_{w,b}\frac{\hat{\gamma}}{||w||}\\
\&s.t...y\_i(w^T.x+b)\ge\hat{\gamma},i=1,2,...,N
\end{aligned}
$$

因为函数间隔只是相对的，函数间隔改变约束也改变，因此对问题无影响，因此可以简化为函数间隔是1：

$$
\begin{aligned}
\&max\_{w,b}\frac{1}{||w||}\\
\&s.t...y\_i(w^T.x+b)\ge 1,i=1,2,...,N
\end{aligned}
$$

后面又为了求导方便，把：$$\frac{1}{||w||}$$变成了最小化$$\frac{1}{2}||w||^2$$，（二者等价）

**然后就得到了经典的这个关系式啦：**

$$
\begin{aligned}
\&min\_{w,b}\frac{1}{2}||w||^2\\
\&s.t...y\_i(w^T.x+b)-1 \ge 0,i=1,2,...,N
\end{aligned}
$$

### 4.拉格朗日对偶转换

将一个最优化问题转换为另外一个更容易的问题，对于如下带不等式、等式约束的优化问题：

$$
\begin{aligned}
\&min f(x)\\
\&g\_i(x) \le 0,i=1,2,...,m\\
\&h\_i(x)=0,i=1,2,...,p
\end{aligned}
$$

可以构造如下拉格朗日函数：

$$
L(x,\lambda,v)=f(x)+\sum\_{i=1}^{m}\lambda\_ig\_i(x)+\sum\_{i=1}^{p}v\_ih\_i(x)
$$

其中$$\lambda,v$$称为拉格朗日乘子，需要满足大于等于0；对上面问题进行转换：

$$
\begin{aligned}
&\*p=min\_xmax\_{\lambda,v,\lambda\_i\ge0}L(x,\lambda,v)\\
&=min\_x\theta\_p(x)
\end{aligned}
$$

就是，先固定x（看成常数），在拉格朗日乘子$\lambda,v$下求函数最大值，消掉这两个变量，然后再求新的函数下的最小值的x（此时未知数）；

换个说法就是：计算最坏（$$maxL(x,\lambda,v)$$最坏结果就是f(x)，因为另外两个项<=0，而原来的问题本来就是f(x)）情况下的极小值$$min f(x)$$

也就是原来问题无法求，我们原来问题最坏情（极大值）L=f(x)况下也无法之间求，但是根据对偶，极大下再求极小可以转换为先极小后极大，转换后的问题不大于原问题，在取得极值的时候两个问题等价

这个转换不影响解，因此问题为：

$$
\begin{aligned}
max\_{\alpha}min\_{w,b}L(w,b,a) =max\_{\alpha}min\_{w,b}\frac{1}{2}||w||^2+\sum\_{i=1}^{N}a\_i(1-y\_i(w^T.x\_i+b))
\end{aligned}
$$

**1）先解里面的min函数，对L函数求导取极值即可：**

$$
\begin{aligned}
&\frac{\partial L(w,b,\alpha)}{\partial w}=w-\sum\_{i=1}^{N}\alpha\_i y\_i x\_i=0\\
&\frac{\partial L(w,b,\alpha)}{\partial b}=\sum\_{i=1}^{N}\alpha\_i y\_i=0
\end{aligned}
$$

得出极小值需满足如上这些关系

代入L求导关系式，求关于a的极大值：

$$
\begin{aligned}
max\_{\alpha}min\_{w,b}L(w,b,a) &= max\_\alpha \frac{1}{2}w^Tw+\sum\_{i=1}^{N}(\alpha\_i-\alpha\_i y\_i(\sum\_{j=1}^{N}\alpha\_j y\_j x\_j)^T x\_i-\alpha\_i y\_i b)\\
&= max\_\alpha \frac{1}{2}(\sum\_{i=1}^{N}\alpha\_i y\_i x\_i)^T(\sum\_{j=1}^{N}\alpha\_j y\_j x\_j)+\sum\_{i=1}^{N}(\alpha\_i-\alpha\_i y\_i(\sum\_{j=1}^{N}\alpha\_j y\_j x\_j)^T x\_i-\alpha\_i y\_i b)\\
&= max\_\alpha \frac{1}{2}\sum\_{i=1}^{N}\sum\_{j=1}^{N}\alpha\_i\alpha\_jy\_iy\_jx\_i^Tx\_j+\sum\_{i=1}^{N}\alpha\_i-\sum\_{i=1}^{N}\alpha\_i y\_i\sum\_{j=1}^{N}\alpha\_j y\_j x\_j^T x\_i-\sum\_{i=1}^{N}\alpha\_i y\_i b\\
&= max\_\alpha \frac{1}{2}\sum\_{i=1}^{N}\sum\_{j=1}^{N}\alpha\_i\alpha\_jy\_iy\_jx\_i^Tx\_j+\sum\_{i=1}^{N}\alpha\_i-\sum\_{i=1}^{N}\alpha\_i y\_i\sum\_{j=1}^{N}\alpha\_j y\_j x\_j^T x\_i-0\\
&= max\_\alpha \sum\_{i=1}^{N}\alpha\_i-\frac{1}{2}\sum\_{i=1}^{N}\sum\_{j=1}^{N}\alpha\_i\alpha\_jy\_iy\_jx\_i^Tx\_j

\end{aligned}
$$

**约束条件为**：

$$
\begin{aligned}
\&s.t.
\begin{cases}
\alpha\_i \ge 0 \\
y\_i(w^Tx\_i+b)-1 \ge 0 \\
\alpha\_i(y\_i(w^Tx\_i+b)-1) =0
\end{cases}
\end{aligned}
$$

PS:不等式$$1-y\_i(w^Tx\_i+b) \le 0$$ 因此有KKT条件：$$\alpha\_i(y\_i(w^Tx\_i+b)-1) =0$$

**w**

所以关键是对这个函数求极大值时的a，**假设通过后面的SMO找到了，记为a\***，那么显然得到了w的解析式：

$$
w=\sum\_{i=1}^{N}\alpha\_i^\* y\_i x\_i
$$

**b**

因为对于所有支持向量点（正例上支持向量点位于$$W^Tx+b = 1$$超平面上，反例$$W^Tx+b= -1$$）记作$$(x\_s,y\_s)$$，均有:

$$
y\_s(w^T.x\_s+b)=1=y\_s(\sum\_{i=1}^{N}\alpha\_i y\_i x\_i^Tx\_s+b)
$$

根据KKT条件：ai>0时，yi(WTxi+b)-1=0：（必定：WTxi+b = 1 或WTxi+b= -1）即xi必须是支持向量点，而ai=0时:

$$
\alpha\_iy\_ix\_i^T=0
$$

也就是说对w无影响，因此上式中w还可以简化成**只考虑支持向量点计算（实际上这就是SVM称为支持向量机的原因，因为模型真正起作用的，就只是这些支持向量点）**，假设我们有S个支持向量（位于WTx+b = 1，WTx+b= -1超平面上的点集）：

$$
y\_s(w^T.x\_s+b)=1=y\_s(\sum\_{i=1}^{N}\alpha\_i y\_i x\_i^Tx\_s+b)=y\_s(\sum\_{i \in S}\alpha\_i y\_i x\_i^Tx\_s+b)
$$

**则对应我们求出S个b∗,理论上这些b∗都可以作为最终的结果， 但是我们一般采用一种更健壮的办法，即求出所有支持向量所对应的b∗，然后将其平均值作为最后的结果：**

$$
\begin{aligned}
& b^*=\frac{1}{y\_s}-\sum\_{i \in S}\alpha\_iy\_ix\_i^Tx\_s=y\_s-\sum\_{i \in S}\alpha\_iy\_ix\_i^Tx\_s\\
& b=\frac{1}{|S|}\sum\_{s \in S}b^*
\end{aligned}
$$

### 得出模型

前面假设参数已经得到，ai参数求出之后，就相当于求出了w,b了，就可以得到模型，进行预测了：

$$
\begin{aligned}
f(x) &=w^Tx+b=\sum\_{i=1}^{N}(\alpha\_i y\_i x\_i)^Tx+b \\
&= \sum\_{i \in S}\alpha\_i y\_i x\_i^Tx+b \\
&=\sum\_{i \in S}\alpha\_i y\_i x\_i^Tx+\frac{1}{|S|}(\sum\_{s \in S}(y\_s-\sum\_{i \in S}\alpha\_iy\_ix\_i^Tx\_s))\\
&=
\begin{cases}
\ge 0,+1\\
\le 0,-1
\end{cases}
\end{aligned}
$$

```python
def _f(self, i):
        r = self.b
    for j in range(self.m):
      r += self.alpha[j] * self.Y[j] * self.kernel(self.X[i], self.X[j])
    return r
```

### SMO

但是这里还有最重要的参数求解没有介绍，下一节专门讲


---

# 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.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.