线性可分支持向量机学习笔记

假设一个特征空间上的训练数据集$T={(x_1, y_1), (x_2, y_2), …, (x_N, y_N)}$T=(x1​,y1​),(x2​,y2​),…,(xN​,yN​)，其中$x_i∈\R^n, y_i∈\{+1, -1\}, i = 1,2,…, N$xi​∈Rn,yi​∈{+1,−1},i=1,2,…,N。$x_i$xi​为第$i$i个特征向量，也称为实例，$y_i$yi​为$x_i$xi​的类标记。学习目标是在特征空间中赵找到一个分离超平面，能将实例分到不同的类。

线性可分支持向量机的定义：

给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为$w^*·x + b^* =0$w∗⋅x+b∗=0以及相应的分类决策函数$f(x)=sign(w^*·x + b^*)$f(x)=sign(w∗⋅x+b∗)称为线性可分支持向量机

函数间隔定义如下：
对于给定的训练数据集T和超平面$(w, b)$(w,b)，定义超平面$(w, b)$(w,b)关于样本点$(x_i, y_i)$(xi​,yi​)的函数间隔为$\hat\gamma_i = y_i(w·x_i + b)$γ^​i​=yi​(w⋅xi​+b)定义超平面$(w, b)$(w,b)关于训练数据集T的函数间隔为超平面$(w, b)$(w,b)关于$T$T中所有样本点$(x_i, y_i)$(xi​,yi​)的函数间隔最小值，即$\hat\gamma = \min_{i=1,…, N} \hat\gamma_i$γ^​=i=1,…,Nmin​γ^​i​

几何间隔定义

对于给定的训练数据集T和超平面$(w, b)$(w,b)，定义超平面$(w, b)$(w,b)关于样本点$(x_i, y_i)$(xi​,yi​)的几何间隔为$\hat\gamma_i = y_i(\frac{w}{||w||}·x_i + \frac{b}{||w||})$γ^​i​=yi​(∣∣w∣∣w​⋅xi​+∣∣w∣∣b​)，定义超平面$(w, b)$(w,b)关于训练数据集T的几何间隔为超平面$(w, b)$(w,b)关于$T$T中所有样本点$(x_i, y_i)$(xi​,yi​)的函数间隔最小值，即$\hat\gamma = \min_{i=1,…, N} \hat\gamma_i$γ^​=i=1,…,Nmin​γ^​i​。
当$||w||=1$∣∣w∣∣=1，函数间隔和几何间隔相等。

间隔最大化

输入：线性可分训练数据集$T={(x_1, y_1), (x_2, y_2), …, (x_N, y_N)}$T=(x1​,y1​),(x2​,y2​),…,(xN​,yN​)，其中$x_i∈\R^n, y_i∈\{+1, -1\}, i = 1,2,…, N$xi​∈Rn,yi​∈{+1,−1},i=1,2,…,N，
输出：最大间隔分离超平面和分类决策函数

• 构造并求解约束最优化问题：$\min_{w,b} \ \ \ \frac{1}{2}||w||^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$w,bmin​   21​∣∣w∣∣2                                                   $s.t. \ \ \ y_i(w`x_i+b)-1≥0, \ i=1,2,…,N$s.t.   yi​(w‘xi​+b)−1≥0, i=1,2,…,N
• 得到分离超平面：$w^*·x + b^* =0$w∗⋅x+b∗=0分类决策函数$f(x)=sign(w^*·x + b^*)$f(x)=sign(w∗⋅x+b∗)

最大间隔分离超平面的存在唯一性

训练数据集线性可分，这是有许多的分离超平面能将数据正确划分，但是最大间隔分离超平面则是唯一的

待补充

……

参考文献

李航 统计学习方法
Sebastian Raschka，Python Machine Learning Second Edition