Support Vector Machines

TOC

SVM 模型 1. 函数间隔和几何间隔 2. 线性可分支持向量机 2. 线性支持向量 3. 非线性支持向量机 4. SMO 算法 5. Sk-learn 接口 SVM 应用 1. 多分类问题 2. 示例：文本分类

SVM 模型

🔥

支持向量机是一种二分类模型。它由感知机演化而来，提供了对非线性问题的一种解决方案。通过不同的间隔最大化策略，支持向量机可分为线性可分支持向量机、近似线性可分支持向量机和线性不可分支持向量机。三种模型都可以形式化为求解一个凸二次规划问题。

1. 函数间隔和几何间隔

函数间隔

对于给定的训练数据集 T 和超平面 , 定义该超平面关于样本点 的函数间隔为：

定义该超平面关于训练数据集 T 的函数间隔为：

几何间隔

定义超平面与样本点 的几何间隔为：

定义该超平面与 T 之间的几何间隔为：

2. 线性可分支持向量机

假设数据是线性可分的

间隔最大化：对训练数据集找到几何间隔最大的超平面，这意味着以充分大的确信度对训练数据进行分类。即：

考虑到函数间隔与集合间隔的关系，可转化为：

由于的缩放对问题求解无影响，取其为1，同时将最大化等效成最小化，问题转化为：

使用拉格朗日算法求解该优化问题，定义拉格朗日函数：

第二项约束项小于等于0，我们的目标是求解 (即满足约束条件时 ||w|| 最小) 由于：

当KKT条件成立时，上式等号成立。因此可通过求解对偶问题来找出超平面，而满足KKT条件的点，亦即位于间隔边界上的点即为支持向量。

对 w, b 求偏导并令其为0求解并带入，得到

在两边同时乘以*（-1），因此对偶问题等价为：

求出后，依据KKT条件，可得：

线性可分支持向量机学习算法：

输入：线性可分训练集 , 其中 .

输出：分离超平面和分类决策函数.

构建并求解约束最优化问题：

求得最优解

计算

选择下标j，满足，计算：

求得超平面：

分类决策函数：

🔍

在线性可分支持向量机中，只依赖于训练数据中对应于的样本点 , 而其他样本点对无影响。其中的实例点为支持向量。

2. 线性支持向量

假设数据不是线性可分的

这意味着某些样本点不能满足函数间隔大于等于1的约束条件，为了解决这个问题，可以对每个样本点引进一个松弛变量 , 使得函数间隔加上松弛变量后大于等于1。原始问题因此变为：

其中是惩罚项，C是超参数。

对偶问题变为：

与线性可分支持向量机相比，仅是的取值范围发生改变。同样依据KKT条件，可得

线性支持向量机学习算法：

输入：线性可分训练集 , 其中 .

输出：分离超平面和分类决策函数.

选择惩罚参数 , 构造并求解凸二次规划问题：

求得最优解

计算

选择下标j，满足，计算：

求得超平面：

分类决策函数：

🔍

线性支持向量机的解唯一但不一定唯一。

在线性不可分的情况下，中对应于的样本点称为支持向量（软间隔的支持向量）。支持向量可以在间隔边界上（），可以在间隔边界与分离超平面之间（），或者在分离超平面误分一侧（）。

3. 非线性支持向量机

输入无法用线性模型分开，而可以用非线性模型分开

核函数

欧式空间到西伯尔特空间的映射。

设函数可将对偶问题中，内积项里的两项映射后，变为线性可分的 . 由于直接求解过于复杂，可以直接用转而求解核函数 . 一些常用的核函数有多项式核函数，高斯核函数，字符串核函数。

多项式核函数：

对应的支持向量机是一个 p 次多项式分类器。此时，分类决策函数成为：

高斯核函数：

对应的支持向量机是高斯径向基函数分类器。此时，分类决策函数成为：

非线性支持向量机学习算法：

选择惩罚参数 , 构造并求解凸二次规划问题：

求得最优解

选择下标j，满足，计算：

分类决策函数：

4. SMO 算法

是一种启发式算法，适用于训练样本容量很大时求解凸二次规划问题的全局最优解。

基本思路为：不断地将原二次规划问题分解为只有两个变量的子二次规划问题，并对孩子问题进行解析和求解，直到所有变量都满足KKT条件为之。

🔨

svm代码实现时可使用高效的凸优化求解库 cvxopt

5. Sk-learn 接口

线性可分支持向量机


from sklearn.svm import LinearSVC
clf = LinearSVC(random_state=0, tol=1e-5)
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
acc = accuracy_score(y_test, y_pred)

线性支持向量机


from sklearn import svm
clf = svm.SVC(kernel = 'linear')
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
acc = accuracy_score(y_test, y_pred)

非线性支持向量机


from sklearn import svm
clf = svm.SVC(kernel = 'rbf')
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
acc = accuracy_score(y_test, y_pred)

SVM 应用

1. 多分类问题

SVM 是经典的二分类模型，对于多分类问题，可以有以下解决方案：

一对多：指定某一类为正例，其余类为负例。分类时将未知样本分类为具有最大分类函数值的那类。这种方式可能会使得样本分布很不均衡，使训练出的模型有较大的偏差。


sk-learn 中参数指定
clf = svm.SVC(decision_function_shape='ovr')

一对一：任意两类构造一个 SVM, 分类时采取投票法决定类别。这种方式可能存在的问题是所需的基分类器太多。


sk-learn 中参数指定
clf = svm.SVC(decision_function_shape='ovo')

层次法：逐层分类，先将所有类分成两类，每类再分成两类… 这种方式可能存在的问题是一步错则步步错。

2. 示例：文本分类

任务：将不同话题的文本进行分类

将文本表达成一个向量

词项频率 权重

，表示第 i 个词项在第 j 个文档中的词频

tf-idf权重

文档频率： = 出现词项 i 的文档数 / N

N 为训练集的文档总数
出现的越多，说明其越不具有特性，对分类也越不重要

逆文档频率：