支持向量机SVM

支持向量机要解决什么问题

• 要解决的问题:

1. 什么样的决策边界才是最好的呢?
2. 特征数据本身如果就很难分，怎么办呢?
3. 计算复杂度怎么样?能实际应用吗 ?

决策边界（Decision Boundary）

决策边界是一个假想的边界，用来区分不同类别的数据点。在特征空间中，决策边界定义了一个分界线或分界面，用于决定新的输入数据点应该被分类为哪一类。

特征与决策边界

在二维特征空间中，决策边界通常是一条线。
在三维特征空间中，决策边界可能是一个平面。
在更高维度的特征空间中，决策边界可以是一个超平面。

距离计算公式

需要计算数据点到决策边界（超平面）的距离。对于一个超平面，可以用公式 $wx+b=0$ 来表示，其中 $w$ 是权重向量，$x$ 是数据点，$b$ 是偏置项。

• 点到超平面的距离：

  数据点 $x$ 到超平面的距离 $d$ 可以通过以下公式计算：

  $$d=\frac{|wx+b|}{||w||}$$

  其中，$||w||$ 是权重向量的范数（即长度）。这个公式衡量了点 $x$ 到超平面的“垂直”距离。

数据标签定义

• 数据集：(X1,Y1)(X2,Y2)…(Xn,Yn)

• 二分类问题：

  在二分类问题中，Y为样本的类别通常定义为 $+1$ 和 $?1$。$+1$ 表示一个类别，$?1$ 表示另一个类别。SVM 的目标是找到一个超平面，使得两个类别的数据点被正确地分开。

• 多分类问题：

  对于多分类问题，可以使用一对一（One-vs-One）或一对多（One-vs-All）的策略，将多分类问题转化为多个二分类问题。

• 决策方程
  在 SVM 中，决策方程基于支持向量和分离超平面定义。给定一个训练数据集 $\{({\mathbf{x}}_1,y_1),({\mathbf{x}}_2,y_2),...,({\mathbf{x}}_n,y_n)\}$，其中 ${\mathbf{x}}_i$ 是特征向量，$y_i$ 是类别标签（通常为 +1 或 -1），决策方程为：

$$f(\mathbf{x})=\text{sign}(\mathbf{w}?\mathbf{x}+b)$$

其中，

• $\mathbf{w}$ 是超平面的法向量。
• $b$ 是超平面的偏置项。
• $\text{sign}$ 函数是符号函数，它根据 $\mathbf{w}?\mathbf{x}+b$ 的正负返回 +1 或 -1。

优化的目标

• 通俗解释: 找到一个条线($\mathbf{w}$ 和 $b$)，使得离该线最近的点能够最远
• 优化问题可以表示为：

$$\underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$$
$$\text{subject?to?}{y}_i(\mathbf{w}?{\mathbf{x}}_i+b)\ge 1,\text{?for?all?}i$$

这个优化问题通常通过拉格朗日乘子法转换为对偶问题来求解。

目标函数

• 放缩变换:对于决策方程（$\mathbf{w}$ 和 $b$）可以通过放缩使得其结果值Y>=1=>(w .D()+b)21(之前我们认为恒大于0，现在严格了些)hmin(.(,)+6)优化目标:argmax1.6由于y·(wr.D()+b)21，只需要考虑 argmax目标函数搞定
  16

优化目标

通过引入拉格朗日乘子 ${\alpha }_i$，优化问题变为：

$$\underset{\alpha }{\max }\left[\sum _{i=1}^n{\alpha }_i?\frac{1}{2}\sum _{i,j=1}^n{y}_i{y}_j{\alpha }_i{\alpha }_j({\mathbf{x}}_i?{\mathbf{x}}_j)\right]$$

受制于：

$$\sum _{i=1}^n{\alpha }_i{y}_i=0$$

和

$${\alpha }_i\ge 0,?i$$

在这个对偶问题中，我们寻求最大化拉格朗日乘子的和，同时考虑到数据点之间的内积。这种方法能够处理线性不可分的情况，通过引入核函数，SVM 可以被扩展到非线性分类问题。

SVM求解

1. 对拉格朗日函数分别对 $w$ 和 $b$ 求偏导数

我们需要求解支持向量机（SVM）的拉格朗日乘子时，首先对拉格朗日函数分别对 $w$ 和 $b$ 求偏导数，然后令其等于零，从而找到最优解。

2. 对 $w$ 的偏导数

对拉格朗日函数：

$$L(w,b,\mathbf{\alpha })=\frac{1}{2}\Vert w{\Vert }^2?\sum _{i=1}^n{\alpha }_i\left[y_i(w?x_i+b)?1\right]$$

其中，$w$ 是超平面的法向量，$\mathbf{\alpha }$ 是拉格朗日乘子向量。

我们对 $w$ 求偏导数：

$$\frac{?L}{?w}=w?\sum _{i=1}^n{\alpha }_i{y}_i{x}_i=0$$

将这个结果令为零，得到了 $w$ 的表达式。

3. 对 $b$ 的偏导数

同样，我们对拉格朗日函数求关于 $b$ 的偏导数：

$$\frac{?L}{?b}=?\sum _{i=1}^n{\alpha }_i{y}_i=0$$

4. 代入结果：

将上述方程组的解代入拉格朗日函数 $L$ 中，得到最小化问题只关于拉格朗日乘子 $\mathbf{\alpha }$ 的表达式：

$$\underset{\mathbf{\alpha }}{\min }\left[\sum _{i=1}^n{\alpha }_i?\frac{1}{2}\sum _{i,j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i?{\mathbf{x}}_j)\right]$$

一旦找到最优的拉格朗日乘子 $\mathbf{\alpha }$，我们可以使用以下公式计算最终的超平面参数 $\mathbf{w}$ 和 $b$：

• 超平面法向量 $\mathbf{w}$：

  $$\mathbf{w}=\sum _{i=1}^n{\alpha }_i{y}_i{\mathbf{x}}_i$$

• 偏置项 $b$：

  选择任意一个支持向量点 ${\mathbf{x}}_j$，然后使用以下公式计算 $b$：

  $$b=y_j?\sum _{i=1}^n{\alpha }_i{y}_i({\mathbf{x}}_i?{\mathbf{x}}_j)$$

然而，在实际问题中，数据通常不是线性可分的，或者数据中可能存在噪声。硬间隔 SVM 对于这些情况可能过于严格，容易导致过拟合。这时就引入了 soft-margin SVM。

Soft-Margin SVM 的目标

Soft-margin SVM 的目标是找到一个超平面，最大化间隔，同时允许一些训练样本分类错误。为了实现这一目标，引入了松弛变量（slack variables） ${\xi }_i$，用来度量每个样本允许的分类错误程度。

Soft-margin SVM 的目标函数可以表示为：

$$\underset{w,b,\xi }{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^N{\xi }_i$$

其中，$w$ 是超平面的法向量，$b$ 是偏置项，$C$ 是一个正则化参数，$N$ 是训练样本的数量。

• 第一项 $\frac{1}{2}\Vert w{\Vert }^2$ 是间隔的最大化部分，它与硬间隔 SVM 的目标相同。
• 第二项 ${\sum }_{i=1}^N{\xi }_i$ 表示对每个样本的分类错误程度的惩罚，通过 ${\xi }_i$ 来度量。$C$ 控制了分类错误和最大化间隔之间的权衡。
• 当C趋近于很大时：意味着分类严格不能有错误
• 当C趋近于很小时：意味着可以有更大的错误容忍
• C是我们需要指定的一个参数!

Soft-Margin SVM 的工作原理

Soft-margin SVM 的工作原理是最小化目标函数，找到合适的超平面，以最大化间隔并容忍一定程度的分类错误。通过调整正则化参数 $C$ 的值，可以控制容忍错误的程度。当 $C$ 较小时，模型更容忍分类错误，可能导致更大的间隔但分类错误更多；当 $C$ 较大时，模型更严格，容忍分类错误较少，但可能导致较小的间隔。

核函数

在支持向量机中，核函数的主要作用是将原始的输入数据映射到一个更高维的特征空间，从而改变数据在特征空间中的表现形式。这个转换的目的是使得原本在低维空间中线性不可分的数据在高维特征空间中变得线性可分。

核函数的公式

核函数通常表示为 $K(x,x^{\prime })$，其中 $x$ 和 $x^{\prime }$ 是输入数据的向量。不同的核函数有不同的形式，常见的核函数包括：

1. 线性核函数：

   $$K(x,x^{\prime })=x^T{x}^{\prime }$$

   线性核函数不进行特征变换，直接在原始特征空间中进行内积操作。

2. 多项式核函数：

   $$K(x,x^{\prime })=(x^T{x}^{\prime }+c{)}^d$$

   多项式核函数将数据映射到高维空间，并进行多项式特征的组合。

3. 高斯径向基函数（RBF）核函数：

   $$K(x,x^{\prime })=\exp \left(?\frac{||x?x^{\prime }|{|}^2}{2{\sigma }^2}\right)$$

   高斯核函数通过计算数据点之间的相似度来进行非线性映射，其中 $\sigma$ 是高斯核的宽度参数。