分类模型1-SVM

简介
基础准备
硬间隔 SVM
3. Kernel SVM
QA

简介

https://zhuanlan.zhihu.com/p/77750026

SVM 三宝： 间隔，对偶，核技巧。它属于判别模型。Support Vector Machine

支持向量：在求解的过程中，会发现只根据部分数据就可以确定分类器，这些数据称为支持向量。
支持向量机（SVM）：其含义是通过支持向量运算的分类器。

SVM 是一种二分类模型，它的目的是寻找一个超平面来对样本进行分割，分割的依据是间隔最大化，最终转化为一个凸二次规划问题来求解。

基础准备

1. 线性可分

$D_{0}$ 和 $D_{1}$ 是 n 维空间中的两个点集，如果存在 n 维向量 $w$ 和实数 $b$ ，使得：

w x_{i} + b > 0; x_{i} \in D_{0} w x_{j} + b < 0; x_{j} \in D_{1}

则称 $D_{0}$ 与 $D_{1}$ 线性可分。

2. 最大间隔超平面

能够将 $D_{0}$ 与 $D_{1}$ 完全正确分开的 $w x + b = 0$ 就成了一个超平面。

为了使得这个超平面更具鲁棒性，我们会去找最佳超平面，以最大间隔把两类样本分开的超平面，也称之为最大间隔超平面。

两类样本分别分割在该超平面的两侧
两侧距离超平面最近的样本点到超平面的距离被最大化了

3. 什么是支持向量？

训练数据集中与分离超平面距离最近的样本点成为支持向量

4. SVM 能解决哪些问题？

线性分类：对于 n 维数据，SVM 的目标是找到一个 n-1 维的最佳超平面来将数据分成两部分。

通过增加一个约束条件： 要求这个超平面到每边最近数据点的距离是最大的。
非线性分类： SVM 通过结合使用拉格朗日乘子法和 KTT 条件，以及核函数可以生产线性分类器

5. 支持向量机的分类

硬间隔 SVM（线性可分 SVM)：当训练数据可分时，通过间隔最大化，学习一个线性表分类器。
软间隔 SVM (线性 SVM)：当训练数据接近线性可分时，通过软间隔最大化，学习一个线性分类器。
Kernel SVM：当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性 SVM。

必会：硬间隔最大化 —> 学习的对偶问题 —> 软间隔最大化 —> 非线性支持向量机（核技巧）

硬间隔 SVM

0. 几何间隔与函数间隔

1. SVM 最优化问题

任意分离超平面可定义为：

w^{T} x + b = 0

二维空间中点 $(x, y)$ 到直线 $A x + B y + C = 0$ 的距离公式为：

\frac{| A x + B y + C}{\sqrt{A^{2} + B^{2}}}

扩展到 n 维空间中，任意点 $x$ 到超平面 $w^{T} x + b = 0$ 的距离为：

\frac{| w^{T} x + b |}{| | w | |} | | w | | = \sqrt{w_{1}^{2} + . . . + w_{n}^{2}}

假设，支持向量到超平面的距离为 $d$ ，那么就有：

{\begin{cases} \frac{w^{T} x_{i} + b}{| | w | |} \geq d, & y_{i} = + 1 \\ \frac{w^{T} x_{i} + b}{| | w | |} \leq - d, & y_{i} = - 1 \end{cases}

稍作转化可得到：

{\begin{cases} \frac{w^{T} x_{i} + b}{| | w | | d} \geq 1, & y_{i} = + 1 \\ \frac{w^{T} x_{i} + b}{| | w | | d} \leq - 1, & y_{i} = - 1 \end{cases}

考虑到 $| | w | | d$ 为正数，我们暂且令它为 1（之所以令它等于 1，是为了方便推导和优化，且这样做对目标函数的优化没有影响）：

{\begin{cases} w^{T} x_{i} + b >= + 1, & y_{i} = + 1 \\ w^{T} x_{i} + b <= - 1, & y_{i} = - 1 \end{cases}

两个方程合并，则有：

y_{i} (w^{T} x_{i} + b) \geq 1

那么我们就得到了最大间隔超平面的上下两个超平面：

两个异类超平面的公式分别为：

{\begin{cases} w^{T} x_{i} + b = + 1, & y_{i} = + 1 \\ w^{T} x_{i} + b = - 1, & y_{i} = - 1 \end{cases}

那么两个异类超平面之间的间隔为：

\frac{2}{| | w | |}

我们的目的是最大化这种间隔：

\begin{aligned} (1) & m a x \frac{2}{| | w | |} & := m i n \frac{1}{2} | | w | | \\ (2) & := m i n \frac{1}{2} | | w | |^{2} \end{aligned}

那么我们的最优化问题为：

m i n \frac{1}{2} | | w | |^{2} s t . y_{i} (w^{T} x_{i} + b) \geq 1

2. 对偶问题

1. 拉格朗日乘数法 - 等式约束优化问题

高等数学中，其等式约束优化问题为：

m i n f (x_{1}, . . ., x_{n}) s t . h_{k} (x_{1}, . . ., x_{n}) = 0

那么令：

L (x, λ) = f (x) + \sum_{k = 1}^{l} λ_{k} h_{k} (x)

$L (x, λ)$ ： Lagrange 函数
$λ$ ： Lagrange 乘子，没有非负要求

利用必要条件找到可能的极值点，我们得到如下的方程组：

{\begin{cases} \frac{δ L}{δ x_{i}} = 0, & i = 1, 2, . . ., n \\ \frac{δ L}{δ λ_{k}} = 0, & k = 1, 2, . . ., l \end{cases}

等式约束下的 Lagrange 乘数法引入了 $l$ 个 Lagrange 乘子，我们将 $x_{i}$ 与 $λ_{k}$ 一视同仁，将 $λ_{k}$ 也看做优化变量，那么共有 $(n + l)$ 个优化变量。

2. 拉格朗日乘数法 - 不等式约束优化问题

对于不等式约束优化问题，其主要思想在于将不等式约束条件转变为等式约束条件，引入松弛变量，将松弛变量也是为优化变量。

对于我们的问题：

m i n \frac{1}{2} | | w | |^{2} s t . g_{i} (w) = 1 - y_{i} (w^{T} x_{i} + b) \leq 0

引入松弛变量 $a_{i}^{2}$ 得到：

f (w) = \frac{1}{2} | | w | |^{2} g_{i} (w) = 1 - y_{i} (w^{T} x_{i} + b) h_{i} (w, a_{i}) = g_{i} (w) + a_{i}^{2} = 0

这里加平方主要为了不再引入新的约束条件，如果只引入 $a_{i}$ 那我们必须要保证 $a_{i} \geq 0$ 才能保证 $h_{i} (w, a_{i})$ ，这不符合我们的意愿。

此时，我们就将不等式约束转化为等式约束，并得到 Lagrange 函数：

\begin{aligned} (3) & L (w, λ, a) & = \frac{1}{2} f (w) + \sum_{i = 1}^{n} λ_{i} h_{i} (w) \\ (4) & = \frac{1}{2} f (w) + \sum_{i = 1}^{n} λ_{i} [g_{i} (w) + a_{i}^{2}] λ_{i} \geq 0 \end{aligned}

那么我们得到方程组有：

{\begin{cases} \frac{δ L}{δ w_{i}} = \frac{δ f}{δ w_{i}} + \sum_{i = 1}^{n} λ_{i} \frac{δ g_{i}}{δ w_{i}} = 0 \\ \frac{δ L}{δ a_{i}} = 2 λ_{i} a_{i} = 0 \\ \frac{δ L}{δ λ_{i}} = g_{i} (w) + a_{i}^{2} = 0 \\ λ_{i} \geq 0 ？ 需 要 看 一 看 \end{cases}

针对 $λ_{i} a_{i} = 0$ 有两种情况：

$λ_{i} = 0, a_{i} \neq 0$ ：此时约束条件 $g_{i} (w)$ 不起作用且 $g_{i} (w) < 0$
$λ_{i} \neq 0, a_{i} = 0$ ：此时 $g_{i} (w) = 0, λ_{i} > 0$ ，可以理解为约束条件 $g_{i} (w)$ 起作用了，且 $g_{i} (w) = 0$

综合可得： $λ_{i} g_{i} (w) = 0$ ，且在约束条件起作用时 $λ_{i} > 0, g_{i} (w) = 0$ ；约束不起作用时， $λ_{i} = 0, g_{i} (w) < 0$ 。

此时，方程组转化为：

{\begin{cases} \frac{δ L}{δ w_{i}} = \frac{δ f}{δ w_{i}} + \sum_{i = j}^{n} λ_{j} \frac{δ g_{i}}{δ w_{i}} = 0 \\ λ_{i} g_{i} (w) = 0 \\ g_{i} (w) \leq 0 \\ λ_{i} \geq 0 \end{cases}

以上便是不等式约束优化优化问题的 KKT (Karush-Kuhn-Tucker) 条件， $λ_{i}$ 称为 KKT 乘子。

KTT 条件中，对于不同样本点来说

支持向量 $g_{i} (w) = 0$ ，此时 $λ_{i} > 0$ 即可
其余向量 $g_{i} (w) < 0$ ，此时 $λ_{i} = 0$

回到原优化问题中：

\begin{aligned} (5) & L (w, λ, a) & = \frac{1}{2} f (w) + \sum_{i = 1}^{n} λ_{i} h_{i} (w) \\ (6) & = \frac{1}{2} f (w) + \sum_{i = 1}^{n} λ_{i} [g_{i} (w) + a_{i}^{2}] \\ (7) & = \frac{1}{2} f (w) + \sum_{i = 1}^{n} λ_{i} g_{i} (w) + \sum_{i = 1}^{n} λ_{i} a_{i}^{2} \end{aligned}

由于 $\sum_{i = 1}^{n} λ_{i} a_{i}^{2} \geq 0$ ，那么问题可以转化为：

\begin{aligned} (8) & L (w, λ) & = \frac{1}{2} f (w) + \sum_{i = 1}^{n} λ_{i} g_{i} (w) \\ (9) & = \frac{1}{2} | | w | |^{2} + \sum_{i = 1}^{n} λ_{i} (1 - y_{i} (w^{T} x_{i} + b)) \end{aligned}

假设我们找到了最佳的参数 $w$ 使得 $\frac{1}{2} | | w | |^{2} = p$ ，又因为 $\sum_{i = 1}^{n} λ_{i} (1 - y_{i} (w^{T} x + b)) \leq 0$ ，因此有 $L (w, λ) \leq p$ ，我们需要找到最佳的参数 $λ$ ，使得 $L (w, λ)$ 接近 p，此时问题转化为：

m i n_{w} m a x_{λ} L (w, λ) s . t . λ_{i} \geq 0

3. 引入对偶问题 — TODO

弱对偶性：最大的里面挑出来的最小的也要比最小的里面挑出来的最大的要大
$m i n m a x f \geq m a x m i n f$
强对偶性：KKT 条件是强对偶性的充要条件。

4. SVM 优化

SVM 的优化问题为： $m i n \frac{1}{2} | | w | |^{2} s t . g_{i} (w) = 1 - y_{i} (w^{T} x_{i} + b) \leq 0$

构造拉格朗日函数：
$m i n_{w, b} m a x_{λ} L (w, b, λ) = \frac{1}{2} | | w | |^{2} + \sum_{i = 1}^{n} λ_{i} (1 - y_{i} (w^{T} x_{i} + b)) s . t . λ_{i} \geq 0$
利用强对偶性转化：
$m a x_{λ} m i n_{w, b} L (w, b, λ)$
对参数 $w, b$ 求偏导有：
$\frac{δ L}{δ w} = w - \sum_{i = 1}^{n} λ_{i} x_{i} y_{i} = 0 \frac{δ L}{δ b} = \sum_{i = 1}^{n} λ_{i} y_{i} = 0$
得到：
$w = \sum_{i = 1}^{n} λ_{i} x_{i} y_{i} \sum_{i = 1}^{n} λ_{i} y_{i} = 0$
将两式带入到 $L (w, b, λ)$ 中有：
$\begin{aligned} (10) & m i n_{w, b} L (w, b, λ) & = \sum_{j = 1}^{n} λ_{i} - \frac{1}{2} \sum_{i = 1}^{n} \sum_{j = 1}^{n} λ_{i} λ_{j} y_{i} y_{j} x_{i}^{T} x_{j} \end{aligned}$
求解模型：

2. 软间隔 SVM

软间隔允许部分样本点不满足约束条件：

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

3. Kernel SVM

1. 思想

对于在有限维度向量空间中线性不可分的样本，我们将其映射到更高维度的向量空间里，再通过间隔最大化的方式，学习得到支持向量机，就是非线性 SVM。

用 x 表示原来的样本点，用 $ϕ (x)$ 表示 x 映射到新特征空间后的新向量。那么分割超平面可以表示为：

f (x) = w ϕ (x) + b

此时，非线性 SVM 的对偶问题转化为：

m i n_{λ} [\frac{1}{2} \sum_{i = 1}^{n} \sum_{j = 1}^{n}]

2. 核函数的作用

目的：将原坐标系中线性不可分数据通过核函数映射到另一空间，尽量使数据在新的空间里线性可分。

2. 常见核函数

线性核函数： $K (x_{i}, x_{j})$

QA

1. SVM 中的支持向量是什么意思？

10.svm

如上图所示，我们在获得分离超平面时，并非所有的点都对分离超平面的位置起决定作用。

其实在特别远的区域，哪怕你增加 10000 个样本点，对于超平面的位置，也是没有作用的，因为分割线是由几个关键点决定的（图上三个），这几个关键点支撑起了一个分离超平面，所以这些关键点，就是支持向量。

2. 什么是 SVM ？

SVM 是一种二类分类模型。它的基本思想是在特征空间中寻找间隔最大的分离超平面使数据得到高效的二分类，主要分三种情况：

当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；
当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机
当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

3. SVM 为何采用间隔最大化？

当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。

感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。
线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。

SVM 求得的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。

4. 为何要讲求解 SVM 的原始问题转换为其对偶问题？

对偶问题往往更易求解

当我们寻找约束存在时的最优点的时候，约束的存在虽然减小了需要搜寻的范围，但是却使问题变得更加复杂。为了使问题变得易于处理，我们的方法是把目标函数和约束全部融入一个新的函数，即拉格朗日函数，再通过这个函数来寻找最优点。
自然引入核函数，进而推广到非线性分类问题

5. SVM 与 LR 的区别

LR 是参数模型，SVM 为非参数模型。
LR 采用的损失函数为 logisticalloss，而 SVM 采用的是 hingeloss。
在学习分类器的时候，SVM 只考虑与分类最相关的少数支持向量点。
LR 的模型相对简单，在进行大规模线性分类时比较方便。

6. SVM 如何处理多分类问题？

直接法：直接在目标函数上修改，将多个分类面的参数求解合并到一个最优化问题里面。看似简单但是计算量却非常的大。
间接法：对训练器进行组合。其中比较典型的有一对一，和一对多。

一对多：对每个类都训练出一个分类器，由 svm 是二分类，所以将此而分类器的两类设定为目标类为一类，其余类为另外一类。这样针对 k 个类可以训练出 k 个分类器，当有一个新的样本来的时候，用这 k 个分类器来测试，那个分类器的概率高，那么这个样本就属于哪一类。这种方法效果不太好，bias 比较高。

一对一：针对任意两个类训练出一个分类器，如果有 k 类，一共训练出 $C_{k}^{2}$ 个分类器，这样当有一个新的样本要来的时候，用这 $C_{k}^{2}$ 个分类器来测试，每当被判定属于某一类的时候，该类就加一，最后票数最多的类别被认定为该样本的类。

5. SVM 软间隔与硬间隔表达式

硬间隔：
$m i n_{w, b} \frac{1}{2} | | w | |^{2} s t . y^{(i)} (w^{T} x^{(i)} + b) \geq 1$
软间隔：
$m i n_{w, b} \frac{1}{2} | | w | |^{2} + C \sum_{i = 1}^{m} ξ_{i} s t . y^{(i)} (w^{T} x^{(i)} + b) \geq 1 ξ_{i} \geq 0$

11. 核函数的种类和应用场景

线性核函数：主要用于线性可分的情形。参数少，速度快。
多项式核函数：
高斯核函数：主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。
sigmoid 核函数：
拉普拉斯核函数：

如果 feature 数量很大，跟样本数量差不多，建议使用 LR 或者 Linear kernel 的 SVM。
如果 feature 数量较少，样本数量一般，建议使用 Gaussian Kernel 的 SVM。

12. SVM 损失函数是什么？

J (θ) = \frac{1}{2} | | θ | |^{2} + C \sum_{i} m a x (0, 1 - y_{i} (θ^{T} x_{i} + b))

13. 核函数的作用是啥？

核函数能够将特征从低维空间映射到高维空间，这个映射可以把低维空间中不可分的两类点变成线性可分的。

14. SVM 为何能用对偶函数求解？

对偶将原始问题中的约束转为了对偶问题中的等式约束，而且更加方便了核函数的引入，同时也改变了问题的复杂度，在原始问题下，求解问题的复杂度只与样本的维度有关，在对偶问题下，只与样本的数量有关。

15. SVM 和全部数据有关还是和局部数据有关？

SVM 只和分类界限上的支持向量点有关，换而言之只和局部数据有关。

16. 为什么高斯核能够拟合无穷维度？

因为将泰勒展开式代入高斯核，将会得到一个无穷维度的映射。

17. LR 与 SVM 的区别？

LR 是参数模型，SVM 是非参数模型
从目标函数来看，区别在于逻辑回归采用的是 logistical loss，SVM 采用的是 hinge loss。这两个损失函数的目的都是增加对分类影响较大的数据点的权重，减少与分类关系较小的数据点的权重。
SVM 的处理方法是只考虑支持向量，也就是和分类最相关的少数点，去学习分类器。而逻辑回归通过非线性映射，大大减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重。
逻辑回归相对来说模型更简单，好理解，特别是大规模线性分类时比较方便。而 SVM 的理解和优化相对来说复杂一些，SVM 转化为对偶问题后，分类只需要计算与少数几个支持向量的距离，这个在进行复杂核函数计算时优势很明显，能够大大简化模型和计算。
logic 能做的 svm 能做，但可能在准确率上有问题，svm 能做的 logic 有的做不了。

Earyant 的技术博客

分类模型 1-SVM

简介