SVM从入门到代码实现

本学期选修了数据挖掘课程,发现课本很多内容和李航博士的《统计学习方法》相同,所以我还是从复习《统计学习方法》开始,再结合老师课堂讲的,尽量做到温故而知新。 这篇博文主要记录我对SVM的理解,逐渐深入,到代码实现三个过程。 相信大多数人和我一样,觉得SVM (support vector machine,支持向量机)很高大上,是一个牛逼的算法。但是当看到有关SVM的讲解,推导时,相信大多数人也和我一样,草草略过,抱着:“会用就行了,原理之后再说吧”的思想,因为乍一看SVM真的挺复杂的。由于课程需要,不得不狠下心来去啃这块骨头。

本文主要从讲解SVM的两种求解方式:

  • 二次规划求解
  • Hingle Loss + 梯度下降(略讲)

SVM的简单理解

对SVM的理解,我是看了知乎一篇文章才对SVM有了初步的理解,原文章地址,在这里我简述一下文章主要内容。 文章是以一个故事来讲述SVM的: 在很久以前的情人节,大侠要去救他的爱人,但魔鬼和他玩了一个游戏。 魔鬼在桌子上似乎有规律放了两种颜色的球,说:“你用一根棍分开它们?要求:尽量在放更多球之后,仍然适用。”

于是大侠这样放,没问题,棍子确实分开了两种颜色的球。

接着魔鬼,又在桌上放了更多的球,这下麻烦了,按照大侠的分法有一个球分错了。

SVM就是试图把棍放在最佳位置,好让在棍的两边有尽可能大的间隙。

现在即使魔鬼放了更多的球,棍仍然是一个好的分界线。

刚刚的问题可以用一条棍(线性的)来划分,而且通过学习,大侠已经找到了最佳分界线,魔鬼开始加大了难度,给大侠新的挑战。

大侠没有棍可以很好帮他分开两种球了,现在怎么办呢?当然像所有武侠片中一样大侠桌子一拍,球飞到空中。然后,凭借大侠的轻功,大侠抓起一张纸,插到了两种球的中间。

从魔鬼的角度看这些球,这些球看起来像是被一条曲线(非线性)分开了。

把这些球叫做 「data」,把棍子叫做 「classifier」, 最大间隙叫做「optimization」, 拍桌子叫做「kernelling」, 那张纸叫做「hyperplane」。 好了,简单的说SVM就是这样了,再加之有libsvm,sklearn等优秀的工具包已经封装好了SVM,使用已经不是问题了。

如果你想更加理解svm的原理,可继续看下文。

二次规划思想求解

知识储备

凸集凸函数

凸优化、凸集、凸函数等本身就是一个体系,在机器学习,以及深度学习的优化函数部分很有作用,为了帮助理解SVM,我尝试学习了些皮毛,首先推荐斯坦佛大学的教程Convex Optimization Overview(链接是pdf文件),以及博文凸优化-凸集和凸函数,在这里仅简单介绍一下。

凸集为\((C \subseteq \mathbb{R}^n)\),使得\((x,y \in C \rightarrow tx+(1-t)y \in C)\),其中\((0 \leq t \leq 1)\)

如上图,左边第一个为凸集,第二个则不是凸集。 可知空集、点、线、球体、超平面均为凸集。且任何凸集的线性组合仍为凸集

凸集的性质

凸集有两个重要的性质,这对SVM的算法理论起着重要的支撑作用。 1. Separating hyperplane理论:两个不相交的凸集之间必然存在一个分割超平面,使得两个凸集可以分开。即如果\(C\)\(D\)都是非空凸集,且\((C \cap D =\emptyset)\),则必然存在\((a,b)\)使得\((C \subseteq {x:a^T \leq b})\)\((D \subseteq {x:a^Tx \geq b})\) 如下图: 2. Supporting hyperplane理论:凸集边界上的一点必然存在一个支撑超平面穿过该点,即如果\((C)\)都是非空凸集,\((x_0 \in bd(C))\),那么必然存在一个超平面\((a)\),使得\((C \subseteq {x:a^Tx \leq a^Tx_0})\) 如下图:

凸函数

若函数\((f)\)为凸函数,如果满足\((f: \mathbb{R} \rightarrow \mathbb{R})\),使得函数\((f)\)的定义域为凸集,\((dom(f) \subseteq \mathbb{R}^n)\),且\((f(tx+(1-t)y) \leq tf(x)+(1-t)f(y))\), 其中\((0 \leq t \leq 1)\)。 也就是说凸函数上任意两点的连线都在两点区间的函数之上。如图:

拉格朗日乘子法

这部分知识,主要来源于百度百科 基本的拉格朗日乘子法就是求函数 \(f(x_1,x_2,...)\) 在约束条件\(g(x_1,x_2,...)=0\) 下的极值的方法。其主要思想是将约束条件函数与原函数联立,从而求出使原函数取得极值的各个变量的解。 也就是说拉格朗日乘子法将约束最优化问题转为了无约束问题

定义

对于具有\(l\)个等式约束的\(n\)维优化问题

\[\begin{cases} min f(x_1, x_2, ..., x_n) \\\\ s.t.\ h_k(x_1, x_2, ..., x_n) & k=1, 2, ..., l \end{cases}\]

把原目标函数 \(f(x)\) 变成的新的目标函数 \(F(x)\)

\[F(x, \lambda) = f(x) + \sum_{k=1}^{l} \lambda_k h_k(x)\]

式中的 \(h_k(x)\) 就是原目标函数 \(f(x)\) 的等式约束条件,待定系数 \(\lambda_k\) 称为拉格朗日乘子。这种方法称为拉格朗日乘子法。 在极值点处有:\(\frac{\partial F}{\partial x_i} = 0\ ,\ (i=1, 2, ..., n)\)\(\frac{\partial F}{\partial \lambda_k} = 0\ ,\ (k=1, 2, ..., l)\) 共有 \(n+l\) 个方程,联立可以算出这 \(n+l\) 个变量,求出了这些变量代入即可得到目标函数的极值。

二次规划

二次规划是非线性规划中的一类特殊数学规划问题,在很多方面都有应用,如投资组合、约束最小二乘问题的求解、序列二次规划在非线性优化问题中应用等。 这部分内容涉及的体系庞大,而且已经是超纲内容,没有足够的能力去涉猎了。所以就简单的介绍一下大致思路以及介绍一下 pythoncvxopt库(这个库会用在SVM代码实现上)。

二次规划问题的标准形式

\[\begin{cases} min\ \frac{1}{2}x^{T}Px + q^{T}x \\\\ s.t.\ Gx \leqslant h \\\\ \ \ \ \ \ \ \ Ax = b \end{cases}\]

上式中,\(x\) 为所要求解的列向量, \(x^{T}\) 表示 \(x\) 的转置。

  • 上式表明,任何二次规划问题都可以转化为上式的结构,用cvxopt的第一步就是将实际的二次规划问题转换为上式的结构,找出对应的\(P、q、G、h、A、b\),然后使用封装好的函数即可求出最优解
  • 目标函数若为求 \(max\),可以通过乘以 −1,将最大化问题转换为最小化问题
  • \(Gx\leqslant h\) 表示的是所有的不等式约束,同样,若存在诸如 \(x\geqslant 0\) 的限制条件,也可以通过乘以−1转换为 \(\leqslant\) 的形式
  • \(Ax=b\) 表示所有的等式约束

SVM原理

支持向量机

SVM (support vector machine, 支持向量机)是一种二元分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器,支持向量机的学习策略就是间隔最大化。 看了上文SVM简单理解部分,我们已经知道了什么是间隔最大化。间隔最大的好处是比较小间隔的决策边界具有更好的泛化误差。

从线性可分开始

分析应该从简单情况开始,我们先考虑线性可分条件。 假设一个包含N个训练样本的二元分类问题。每个样本可以表示成 \((X_i, y_i)\ (i=1, 2, ..., N)\) , \(X_i = (x_{i1}, x_{i2}, ..., x_{id}) ^{T}\)\(y_i \in {-1, +1}\) 表示类别,一个线性分类器的决策边界可以写成:

\[W \cdot X + b = 0\]

\(W\)\(b\) 是模型的参数。 假设 \(X^{+}\)\(X^{-}\) 是两个位于决策边界上的点,如图: 可知有:

\[\begin{cases} W \cdot X^{+} + b = +1 \\\\ W \cdot X^{-} + b = -1 \end{cases}\]

联立两式有

\[W \cdot (X^{+} - X^{-}) = 2\]

又有:

\[X^{+} = X^{-} + \lambda W \ \Rightarrow \ \lambda = \frac{2}{W \cdot W}\]

所以间距和为:

\[ d = \left | X^{+} - X^{-} \right | = \left | \lambda W \right | = \frac{2}{W \cdot W} \left \| W \right \| = \frac{2}{\left \| W \right \|} \tag{1}\]

我们要做的就是最大化 \(d\) 了。 为什么叫支持向量这个奇怪的名字呢?这个图可以直观的反应了最大间隔分离超平面完全由离该超平面最近的点定义,其它点可以从数据集中删除掉,因为它们对最优超平面的选择没有影响。这些决定最大间隔分离超平面的点通常被称为支持向量,因此SVM的意思就是使用这些支持向量来学习出最优的超平面,也即是SVM使用了训练实例的一个子集来表示决策边界,这个子集就称作支持向量。 SVM的训练阶段包括从训练数据中估计决策边界的参数 \(W\)\(b\)。选择的参数必须满足:

\[\begin{cases} W \cdot X_i + b \geqslant 1 & \text{ if } y_i=1 \\\\ W \cdot X_i + b \leqslant -1 & \text{ if } y_i = -1 \end{cases} \tag{2}\]

也即是:

\[y_i (W \cdot x + b) \geqslant 1\ ,\ i=1, 2, ..., N \tag{3}\]

我们换个思路,最大间隔 \(d\) 等价于最优化下面的目标函数:

\[f (W) = \frac{\left \| W ^{2} \right \|}{2} \tag{4}\] 加上受限条件得到优化问题: \[\begin{cases} \underset{W}{min} \frac{\left \| W ^{2} \right \|}{2} \\\\ s.t.\ y_i(W \cdot X + b) \geqslant 1 \end{cases} \tag{5}\]

可知目标函数是二次的,而约束是线性的,因此这个问题是凸优化问题。 看到这个形式是不是觉得有点熟悉?好了接下来我们要用拉格朗日乘子法了。 通过拉格朗日乘子法可得到新的目标函数

\[L_P = \frac{1}{2}\ {\left \| W \right \|}^{2} - \sum_{i=1}^{N}\lambda_i(y_i(W \cdot X + b) - 1) \tag{6}\]

看到\(L_p\) 我是很惊喜的,SVM太强大了,它竟然自带L2正则 \(\frac{1}{2}\ {\left \| W \right \|}^{2}\),这也在一方面说明了SVM为什么能最小化结构化风险吧?我们都知道正则化手段是抑制过拟合的一种方法,因为发生过拟合时参数 \(W\) 一般是较大的值,而正则化主要是对 \(W\) 进行惩罚,从而降低模型的复杂性。

接下来要做得工作是最小化新目标函数,我们对 \(L_p\) 关于 \(W\)\(b\) 求偏导,并令它们等于零,即

\[\frac{\partial L_P}{\partial W} = 0 \Rightarrow W = \sum_{i=1}^{N}\lambda_i y_i X_i \tag{7}\]

\[\frac{\partial L_P}{\partial b} = 0 \Rightarrow \sum_{i=1}^{N}\lambda_i y_i = 0 \tag{8}\]

处理不等式约束的一种方法就是将其变为一组等式约束。只要限制拉格朗日乘子非负这种变换就可行。这种变换导致如下拉格朗日乘子约束,称作KTT条件。

\[\lambda_{i} \geqslant 0\]

\[ \lambda_{i} [y_{i}(W \cdot X_i+b)-1] = 0 \]

该约束表明,除非 \(y_{i}(W \cdot X_i+b)-1=0\) 否则 \(\lambda_i\) 必须为0,那些 \(\lambda_i > 0\) 称为支持向量,而 \(W\)\(b\) 的确定仅依赖这些支持向量。因此KTT条件解释了为什么SVM仅由支持向量决定。

拉格朗日乘子 \(\lambda_i\) 现在是未知的,我们无法直接求得 \(W\)\(b\),为了减少变量将 (7) (8) 式代入(6)得到

\[L_D = \sum_{i=1}^{N} \lambda_i - \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \lambda_i \lambda_j y_i y_j X_i X_j \tag{9}\]

根据拉格朗日对偶性,原始问题的对偶问题是极大化极小化原始问题,原始问题为

\[\underset{W,b }{min}\ \underset{\lambda }{max}\ L(W, b, \lambda )\]

故可得到对偶问题为

\[\underset{\lambda }{max}\ \underset{W,b }{min}L(W, b, \lambda )\]

\(L_D\)\(L_P\) 的对偶问题, 所以最小化 \(L_P\) 等价于最大化 \(L_D\)

二次规划一般求最小值,我们改一下 \(L_D\) 得到

\[{L_D}' = \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \lambda_i \lambda_j y_i y_j X_i X_j - \sum_{i=1}^{N} \lambda_i \tag{10}\]

现在问题变成了最小化 \({L_D}'\) 也就是现在的优化问题是

\[\begin{cases} \underset{\lambda }{min} \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \lambda_i \lambda_j y_i y_j X_i X_j - \sum_{i=1}^{N} \lambda_i \\\\ s.t.\ \sum_{i=1}^{N} \lambda_iy_i = 0, \lambda_i \geq 0 \end{cases} \tag{11}\]

接下来我们可以用二次规划去优化

线性不可分的情况

线性可分是一种理想的情况,现实数据集不可能没有噪声,如下图

就是线性不可分的例子,通俗的说不能用一根棍子完全分开红点和蓝点。 为此我们需要用一种软边缘的方式去学习允许一定训练错误的决策边界,加入松弛因子是一种方法,再加入松弛因子后(2)式就变为了

\[\begin{cases} W \cdot X_i + b \geqslant 1 - \S_i & \text{ if } y_i=1 \\\\ W \cdot X_i + b \leqslant -1 + \S_i & \text{ if } y_i = -1 \end{cases} \tag{12}\]

用式子(12)替换(2)再走一遍上述过程,可以得到目标函数,但是如果仅仅加入松弛因子,由于在决策边界误分类样本的数量上没有限制,学习算法可能会找到边缘很宽的边界,但是却分错了很多的训练实例,为了避免这个问题,必须修改目标函数用来惩罚那些松弛因子很大的决策边界。加入了惩罚因子后想要优化的式子变为

\[\begin{align*} & min \frac{\left \| w \right \|^2}{2} + C\sum_{i=1}^{N}\xi _{i} \\\\ & s.t.\ y_{i}(W\cdot X + b) \geqslant 1 - \xi_{i},\ \xi_{i} \geqslant 0 \end{align*} \tag{13}\]

C就是惩罚因子了,C和k都是超参,为了简化运算令k=1,加入了惩罚因子和松弛因子后得到的拉格朗日函数为

\[L = \frac{1}{2}\ {\left \| W \right \| }^{2} + C \sum_{i=1}^{N} \S_i - \sum_{i=1}^{N}\lambda_i(y_i(W \cdot X + b) - 1 + \S_i) \tag{14}\]

利用如下KTT条件可以将不等式约束转为等式约束

\[\S_i \geqslant 0,\ \lambda_i \geqslant 0,\ \mu_i \geqslant 0\]

\[\lambda_i \{ y_i(W \cdot X_i + b) - 1 + \S_i \} = 0\]

\[\mu_i \S_i = 0\]

\(L\) 关于 \(W\)\(b\)\(\S_i\)的一阶导数为0得

\[\begin{align*} & \frac{\partial L}{\partial W_j} = 0 \Rightarrow W_j = \sum_{i=1}^{N}\lambda_i y_i X_{ij} \\\\ & \frac{\partial L}{\partial b} = 0 \Rightarrow \sum_{i=1}^{N}\lambda_i y_i = 0 \\\\ & \frac{\partial L}{\partial \S_i} = 0 \Rightarrow \lambda_i + \mu_i = C \end{align*}\]

和之前的步骤一样,最后得到的最终目标函数为

\[{L_D}^{''} = \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \lambda_i \lambda_j y_i y_j X_i X_j - \sum_{i=1}^{N} \lambda_i \ \tag{15}\]

可以看到目标函数和线性可分的一样,但是约束条件已经不一样了,现在优化问题为

\[\begin{cases} \underset{\lambda }{min} \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \lambda_i \lambda_j y_i y_j X_i X_j - \sum_{i=1}^{N} \lambda_i \\\\ s.t.\ \sum_{i=1}^{N} \lambda_iy_i = 0, \lambda_i \geq 0, 0 \leqslant \lambda_i \leqslant C \end{cases} \tag{16}\]

还是用二次规划求解

非线性

开头已经叙述了非线性下往往要把当前空间映射到高维空间上,高维空间下按照线性的方式去处理当前问题。既然要映射就要有映射函数(核函数),我们假设核函数为 \(\phi (X)\) , 现在决策边界就变成了:\(W\phi (X) + b\),接下来就和上述的步骤一样求解目标函数了 当然核函数不是随便来的,必须要满足Mercer定理,大致要求如下:必须存在一个相应的变化,使得计算一对向量的核函数等价于在变换后的空间中计算这对向量的点积(空间中计算点积的意义是可以理解为求相似度)。

核函数

核函数就是为了解决上述的非线性问题,什么是非线性呢?举个例子

\[\begin{align*} & w = y\cdot a \\\\ & f(x) = w^{T}x = a^{T}y^{T}\cdot x = a^{T} K(y^{T}, x) \end{align*}\]

\(f(x)\) 就是非线性的,而\(K(y^{T}, x)\)就是一个核函数,把它当成一个整体来看\(f(x)\)就变成线性的了

常见的核函数

  • 线性核: \(K(x, y) = x^{t}y\)
  • 多项式核: \(K(x, y) = (ax^{t}y + c)^{d}\)
  • 高斯核: \(K(x, y) = e^{\frac{\left \| x-y \right \|^2}{2 \sigma ^{2}}}\)

SVM的优点

  • 凸优化问题,可以找到全局最优
  • 自带正则

代码实现

这里仅截取部分代码片段,完整项目可查看我的Github:simple_svm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
# -*- coding: utf-8 -*-

import numpy as np
import cvxopt
import cvxopt.solvers

class SVC(object):
def __init__(self, kernel='linear', C=1.0, sigma=1.0, **kwargs):
if kernel not in ['linear', 'gaussian']:
raise ValueError("Now only support linear and gaussian kernel")
elif kernel == 'linear':
kernel_fn = Kernel.linear()
else:
kernel_fn = Kernel.gaussian(sigma)

self.kernel = kernel_fn # kernel func
self.C = C
self._predictor = None

# 训练
def fit(self, X, y):
lagr = self._lagr_multiplier(X, y) # 获取拉格朗日乘子
self._predictor = self._fit(X, y, lagr)
# 预测
def predict(self, X):
return self._predictor.predict(X)

def _fit(self, X, y, lagr, support_vector_threhold=1e-5):
# 计算支持向量
support_vectors_id = lagr > support_vector_threhold
support_lagr = lagr[support_vectors_id]
support_vectors = X[support_vectors_id]
support_vector_tags = y[support_vectors_id]

# 计算偏差
bias = np.mean([y_k - Predictor(kernel=self.kernel,
bias=0.0,
W=support_lagr,
support_vectors=support_vectors,
support_vector_tags=support_vector_tags).predict(x_k) for (y_k, x_k) in zip(support_vector_tags, support_vectors)])

return Predictor(kernel=self.kernel,
bias=bias,
W=support_lagr,
support_vectors=support_vectors,
support_vector_tags=support_vector_tags)

def _lagr_multiplier(self, X, y):
samples, features = X.shape

k = self._mapping(X)
# 二次规划求最优解
P = cvxopt.matrix(np.outer(y, y)*k)
q = cvxopt.matrix(-1 * np.ones(samples))

G_std = cvxopt.matrix(np.diag(np.ones(samples)*-1))
h_std = cvxopt.matrix(np.zeros(samples))

# a_i \leq C
G_slack = cvxopt.matrix(np.diag(np.ones(samples)))
h_slack = cvxopt.matrix(np.ones(samples) * self.C)

G = cvxopt.matrix(np.vstack((G_std, G_slack)))
h = cvxopt.matrix(np.vstack((h_std, h_slack)))

#y = y.reshape((1, y.shape[0]))
A = cvxopt.matrix(y, (1, samples))
b = cvxopt.matrix(0.0)

solution = cvxopt.solvers.qp(P, q, G, h, A, b)
# lagr multiplier
return np.ravel(solution['x'])

def _mapping(self, X):
samples, features = X.shape
k = np.zeros((samples, samples))
# 空间映射
for i, xi in enumerate(X):
for j, xj in enumerate(X):
k[i, j] = self.kernel(xi, xj)
return k

class Predictor(object):
def __init__(self,
kernel,
bias,
W,
support_vectors,
support_vector_tags):
self._kernel = kernel
self._bias = bias
self._W = W
self._support_vectors = support_vectors
self._support_vector_tags = support_vector_tags
assert len(support_vectors) == len(support_vector_tags)
assert len(W) == len(support_vector_tags)

def softmax(self, x):
"""Compute softmax values for each sets of scores in x."""
x = np.array(x)
x = np.exp(x)
x.astype('float32')
if x.ndim == 1:
sumcol = sum(x)
for i in range(x.size):
x[i] = x[i]/float(sumcol)
if x.ndim > 1:
sumcol = x.sum(axis = 0)
for row in x:
for i in range(row.size):
row[i] = row[i]/float(sumcol[i])
return x

def predict(self, x):
result = self._bias
for z_i, x_i, y_i in zip(self._W,
self._support_vectors,
self._support_vector_tags):
result += z_i * y_i * self._kernel(x_i, x)
return np.sign(result).item()

class Kernel(object):
# 线性核
@staticmethod
def linear():
return lambda X, y: np.inner(X, y)

# 高斯核
@staticmethod
def gaussian(sigma):
return lambda X, y: np.exp(-np.sqrt(np.linalg.norm(X-y) ** 2 / (2 * sigma ** 2)))

代码仅支持二分类,以下是玩具样例

1
2
3
4
5
6
7
8
9
10
from svm import SVC
samples = 10
features = 2

X = np.matrix(np.random.normal(size=samples * features).reshape(samples, features)) # gausian distributed
y = 2 * (X.sum(axis=1) > 0) - 1.0
clf = SVC(kernel="linear", C=1.0)
clf.fit(X, y)
pred = clf.predict(np.array([-2.76 ,-3.05]).reshape(1, 2))
print(pred)

Hingle Loss 求解

上面已经讲了二次规划求解SVM的一些步骤,但由于知识储备原因,并没有讲太多二次规划的知识,只是利用了工具包求解。这部分主要补充一下Hingle Loss 求解的思路

Hingle Loss

hingle loss中文译名铰链损失函数 ,由于函数图像很像一本要合上的书故也称做合页损失函数,它的函数图像为

乍一看觉得也很像ReLU的函数图像,在二分类下它的损失函数为:

\[\begin{align*} & L(\widehat{y}, y) = max(0, 1-y \cdot \widehat{y}) \\\\ & y \in \{-1, 1\} \\\\ & \widehat{y} \in [-1, 1] \end{align*}\]

\(y\)是正确的标签(值为\(\pm 1\)),\(\widehat{y}\) 是预测值(-1到1之间)

如果被正确分类即 \(\widehat{y} == y \Rightarrow \widehat{y}\cdot y = 1\) 故损失是0,否则损失就是 \(1-\widehat{y}\cdot y\)

Hingle Loss 的特点

可知 \(\widehat{y}\) 的值在 \([-1, 1]\) 即可,并不鼓励 \(|y| > 1\) 即不鼓励分类器过度自信,从而使得分类器可以专注于整体的分类误差

Hingle Loss 的变种

如果有正负样本,我们往往希望损失函数能使得正样本的分数得分较高,使得负样本的分数越低越好,此时可以通过合页函数来构造

\[L(\widehat{y}, y) = max(0, m-y+\widehat{y})\]

m为设置的最大边界(max margin),上述二分类的最大边界为1

Hingle Loss 与SVM

有了先前SVM的介绍,现在应该有所了解了,对于\((13)\)

\[\begin{align*} & min \frac{\left \| w \right \|^2}{2} + C\sum_{i=1}^{N}\xi _{i} \\\\ & s.t.\ y_{i}(w^{T}\cdot x_{i} + b) \geqslant 1 - \xi_{i},\ \xi_{i} \geqslant 0 \end{align*}\]

对约束项进行变形有

\[\xi_{i} \geqslant 1 - y_{i}(w^{T}\cdot x_{i} + b)\]

则损失函数可写为

\[J(w) = \frac{\left \| w \right \|^{2}}{2} + C\sum_{i=1}^{N} max(0, 1-(w^{T}x_{i} + b)) \tag{17}\]

因此SVM的损失函数可以看作是L2正则+Hingle Loss

Hinge Loss在 \(\widehat{y}*y=1\) 的时候是不可微的

梯度下降求解

\((17)\)进行梯度下降有

\[\begin{align*} & w := w - \eta \frac{\alpha (J(w))}{\alpha(w)} \\\\ & \frac{\alpha (J(w))}{\alpha(w)} = w + \sum y_{i} x_{i} \\\\ & s.t. y_{i}w^{T}x_{i} < 1, i = 1, 2...n \end{align*}\]

\(\eta\) 为学习速率

后记

好了,终于写完了,就当做个记录,虽然以后还是会直接用第三方封装好的库函数,但是从原理上终于对SVM有了一定的理解。欢迎指正!

Reference

  • [0] https://www.zhihu.com/question/21094489
  • [1] https://www.52ml.net/20845.html
  • [2] 《统计学习方法》
  • [3] 《数据挖掘导论》
  • [4] https://github.com/ajtulloch/svmpy
  • [5] https://www.cnblogs.com/yymn/p/8336979.html
sean lee wechat
欢迎关注我的公众号!
感谢支持!