当前位置：网站首页>Chapter8 Support Vector Machines

Chapter8 Support Vector Machines

2022-07-30 04:29:00 【Sang Zhiwei 0208】

1 理解支持向量机SVM的原理和目标（what）

1.1 原理

SVMThe rationale is to find a linear classifier that maximizes the separation hyperplane in the feature space.

When the training samples are linearly separable,通过硬间隔最大化,学习一个线性分类器,即线性可分支持向量机.
When the training data is approximately linearly separable,Slack variables can be introduced,通过软间隔最大化,学习一个线性分类器,即线性支持向量机.
When the training data is linearly inseparable,通过核函数以及软间隔最大化,Learn about fractional linear support vector machines.

1.2 目标

Find infinite linear functions of all sample distancesf(x,w,b)最小的距离,Find the line with the largest distance among these distances,即求取w,b的值

如图所示： $f(x,w,b)=sign(w\cdot x-b)$ ,其中 w,x 代表向量.

The sample distance is the distance between this function： $\frac{(w_{j}x^{(i)}+b_{j})y^{i}}{||w||}$

所以目标为： $w^{*},b^{*}=arg max(\underset{i=1,2...n}{min}\frac{(w_{j}x^{(i)}+b_{j})y^{i}}{||w||})$

2 掌握支持向量机的计算过程和算法步骤（how）

2.1 计算过程

假设给定一个特征空间上的训练数据集 $T={(x_{1},y_{1}),(x_{2},y_{2})...(x_{N},y_{N})}$ ,其中 $x_{i}\epsilon R^{n},y_{i}\epsilon (+1,-1),i=1,2...N$ ;

$x_{i}$ 表示为第i个实例（若n大于1,则 $x_{i}$ 为向量）;

$y_{i}$ 为 $x_{i}$ 的类标记,即当 $y_{i}=+1$ 时, $x_{i}$ 为正例,当 $y_{i}=-1$ 时 $x_{i}$ 为负例.

$(x_{i},y_{i})$ 称为样本点.

给定线性可分训练数据集,The separating hyperplane obtained by maximizing the interval is $y(x)=w^{T}\Phi (x)+b$ ,相应的分类决策函数 $f(x)=sign(w^{T}\Phi (x)+b)$ ,该决策函数称为线性可分支持向量机.

$\varphi (x)$ 是某个确定的特征空间转换函数,它的作用是将x映射到（最高的）维度.

Solve the separating hyperplane problem=Solve the corresponding convex quadratic programming problem.

（1）根据题设 $y(x)=w^{T}\Phi (x)+b$ ,有当 $y(x_{i})>0\Leftrightarrow y_{i}=+1$ , $y(x_{i})<0\Leftrightarrow y_{i}=-1$

从而 $y_{i}\cdot y(x_{i})> 0$ .【 $y(x_{i})$ 为预测值 $y_{i}$ 为真实值】

change by a certain percentagew,b（The position of the hyperplane does not change at this time,But the function interval can be changed）,则t*yThe value also changes,从而：

$\frac{y_{i}\cdot y(x_{i})}{||w||}=\frac{y_{i}(w^{T}\cdot \Phi (x_{i})+b)}{||w||}$ ,其中 ||w|| 为的 $L_{2}$ 范数.

目标函数： $\underset{w,b}{argmax}\left \{ \frac{1}{||w||}\underset{i}{min} [y_{i}\cdot (w^{T}\cdot \Phi (x_{i})+b)]\right \}$

(2)(If the geometric distance is B,即 $\frac{y_{i}(w^{T}\cdot \Phi (x_{i})+b)}{||w||}=B$ （B为常数）

Divide both sides of the equation byB：

$\frac{1}{B}\cdot \frac{y_{i}(w^{T}\cdot \Phi (x_{i})+b)}{||w||}=1$ ,At this point the geometric distance becomes 1.

通过等比例缩放w的方法,The function values of these two types of points are satisfied $|y| \geq 1$ ,即约束条件.

(3)So the original problem can be transformed into the following problem:

约束条件—— $y_{i}\cdot (w^{T}\cdot \Phi (x_{i})+b)\geq 1,i=1,2,...,n$

原目标函数—— $\underset{w,b}{argmax}\left \{ \frac{1}{||w||}\underset{i}{min} [y_{i}\cdot (w^{T}\cdot \Phi (x_{i})+b)]\right \}$

新目标函数—— $\underset{w,b}{argmax}\frac{1}{||w||}$ ,即 $\underset{w,b}{max}\frac{1}{||w||}$ ,即 $\underset{w,b}{min}\frac{1}{2}||w||^{2}$

（4）所用方法：拉格朗日乘子法

设函数 $L(w,b,\alpha )=\frac{1}{2}||w||^{2}-\sum_{i=1}^{n}\alpha _{i}(y_{i}(w^{T}\cdot \Phi (x_{i})+b)-1)$

原问题是极小极大问题： $\underset{w,b}{min}\underset{\alpha }{max}L(w,b,\alpha )$

The dual problem of the primal problem is the minimax problem： $\underset{\alpha }{max}\underset{w,b}{min}L(w,b,\alpha )$

然后分别对 w,b 求偏导,令其为0：

$\frac{\partial L}{\partial w}=0 \Rightarrow w=\sum_{i=1}^{n}\alpha _{i}y_{i}\Phi (x_{n})$

$\frac{\partial L}{\partial b }=0\Rightarrow 0=\sum_{i=1}^{n}\alpha _{i}y_{i}$

即在 $0=\sum_{i=1}^{n}\alpha _{i}y_{i}$ Solve under constraints：

Add a minus sign to solve：

2.2 举例说明

我们可以看到 $\alpha _{2}=0$ ,则 $x_{2}$ is a non-support vector.

2.3 拉格朗日乘子法

约束条件： $f_{i}(x)\leq 0,i=1,2,...,n$ , $h_{j}(x)=0,j=1,2,...,m$

目标： min f(x)

构造函数： $G(x,\mu ,\lambda )=f(x)+\sum_{i=1}^{n}\mu _{i}f_{i}(x)+\sum_{i=1}^{m}\lambda _{j}h_{j}(x)$ ,其中 $\mu _{i}\geq 0,\lambda _{j}$ 任意值.

所以

$minf(x)=\underset{x}{min}(\underset{\mu _{i}\geq 0,\lambda \epsilon R}{max}G(x,\mu ,\lambda ))$ (原始问题)

对偶函数为 $\underset{\mu _{i}\geq 0,\lambda \epsilon R}{max}\underset{x}{min}G(x,\mu ,\lambda )$

所以接下来对 $\lambda$ 求导,使其为0.

3 Understand what it means to maximize soft spacing

When the training data is approximately linearly separable,The slack variable can be increased $\xi _{i}\geq 0$ ,通过软间隔最大化,Make the sinicization interval plus the slack variable greater than or equal to1,Thus the constraints become $y_{i}\cdot (w^{T}\cdot x_{i}+b)\geq 1-\xi _{i}$ ,And the objective function becomes $\underset{w,b}{min}\frac{1}{2}||w||^{2} + C\sum_{i=1}^{N}\xi _{i}$

CThe smaller the transition band, the wider,So it has generalization ability.C大时,to minimize the objective function,Actually need to make $\xi _{i}=0$ ,becomes linearly separable.