支持向量机--线性可分支持向量机

支持向量机(support vector machines, SVM)是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题，支持向量机的学习算法是求解凸二次规划的最优化算法。

支持向量机学习方法包含由构建由简至繁的模型：线性可分支持向量机，线性支持向量机及非线性支持向量机。给定线性可分线性训练数据集，通过间隔最大化或等价的求解相应的凸二次规划问题学习得到的分离超平面为 $w^{*} \cdot x + b^{*} = 0$ 以及相应的分类决策函数 $f(x) = sign(w^{*} \cdot x + b^{*})$ 称为线性可分支持向量机。

(函数间隔) 对于给定的训练数据集T和超平面(w,b),定义超平面(w,b)关于样本点$ (x{i},y{i}) $的函数间隔为 $ \hat{\gamma}{i} = y{i}(w \cdot x{i} + b) $ 定义超平面(w, b)关于训练数据集T的函数间隔为超平面(w,b)关于T中所有样本点$ (x{i},y{i}) $的函数间隔之最小值，即 $ \hat{\gamma} = \min{i=1,\cdot \cdot \cdot,N} \hat{\gamma}_{i} $

(几何间隔) 对于给定的训练数据集T和超平面(w,b),定义超平面(w,b)关于样本点$ (x{i},y{i}) $的几何间隔为 $ \gamma{i} = y{i}\bigg(\frac{w}{||w||} \cdot x{i} + \frac{b}{||w||}\bigg) $ 定义超平面(w, b)关于训练数据集T的函数间隔为超平面(w,b)关于T中所有样本点$ (x{i},y{i}) $的几何间隔之最小值，即 $ \gamma = \min{i=1,\cdot \cdot \cdot,N} \gamma_{i} $

函数间隔和几何间隔有如下关系： $ \gamma{i} = \frac{\hat{\gamma}{i}}{||w||} $
$ \gamma = \frac{\hat{\gamma}}{||w||} $

间隔最大化支持向量机的基本思想是求解能够正确划分训练数据集并且几何间隔最在的分离超平面. 对线性可分的训练数据集而言，线性可分分离超平面有无穷多个(等价于感知机),但是几何间隔最大化的分离超平面是唯一的。这里的间隔最大化又称为硬间隔最大化(与训练数据集近似线性可分时的软间隔最大化相对应)

凸优化问题是指约束最优化问题： $ \min{w} f(w) $ s.t. $ g{i}(w) \le 0, i=1,2,\cdot \cdot \cdot,k $
$ h{i}(w) = 0, i=1,2,\cdot \cdot \cdot,l $ 其中，目标函数f(w)和约束函数$ g{i}(w) $都是$ R^{n} $上的连续可微的凸函数，约束函数$ h{i}(w) $是$ R^{n} $上的仿射函数。
当目标函数f(w)是二次函数且约束函数$ g{i}(w) $是仿射函数时，上述凸最优化问题成为凸二次规划问题。

线性可分支持向量机学习算法—-最大间隔法

输入：线性可分训练数据集$ T = {(x{1},y{1}),(x{2},y{2}),\cdot \cdot \cdot, (x{N},y{N})} $,其中，$ x{i} \in \mathcal=R^{n},y{i}={-1,+1}, i=1,2,\cdot \cdot \cdot,N $;
输出：最大间隔分离超平面和分类决策函数
(1)构造并求解约束最优化问题：
$ \min{w,b}^{} \frac{||w||^2}{2} $
s.t.
$ y{i}(w \cdot x_{i}+b)-1 \ge 0, i=1,2,\cdot \cdot \cdot,N $ 求得最优解 $w^{*},b^{*}$

(2)由此得到的分离超平面：

$w^* \cdot x + b^* = 0$

分类决策函数：

$f(x) = sign(w^* \cdot x + b^*)$

(定理) (最大间隔分离超平面的存在唯一性)若训练数据集T线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

例：已知一个如下图所示的训练数据集，其正例点是$ x{1}=(3,3)^T,x{2}=(4,3)^T $,负实例点是$ x{3}=(1, 1)^T $,试求最大间隔分离超平面。图片代码按照最大间隔法，根据训练数据集构造约束最优化问题：
$ \min{w,b} \frac{1}{2}(w{1}^2+w{2}^2) $
s.t.
$ 3w{1} + 3w{2}+b \ge 1 $
$ 4w{1} + 3w{2}+b \ge 1 $
$ -w{1} - w{2}-b \ge 1 $

import cvxpy as cvx

w1 = cvx.Variable()
w2 = cvx.Variable()
b  = cvx.Variable()

#约束条件
constraints = [3*w1+3*w2+b>=1,4*w1+3*w2+b>=1,-w1-w2-b>=1]
#目标函数
obj = cvx.Minimize((w1**2+w2**2)/2)


prob = cvx.Problem(obj, constraints)
prob.solve()


print("w1=",w1.value)
print("w2=",w2.value)
print("b=",b.value)

求解得最优化解为$ w{1}=w{2}=\frac{1}{2}, b=-2 $,最大间隔分离超平面为$ \frac{1}{2}x^{(1)} +\frac{1}{2}x^{(1)}-1=0 $，其中 $ x{1}=(3,3)^T,x{3}=(1,1)^T $为支持向量。

学习的对偶算法

未完待续

Ref：
1.统计学习方法
2.cvxpy