问题:如何对对下图的线性可分数据集和线性不可分数据集进行分类？
思路:
(1)对线性可分数据集找到最优分割超平面
(2)将线性不可分数据集通过某种方法转换为线性可分数据集
下面将带着这两个问题对支持向量机相关问题进行总结
2. 如何找到最优分割超平面一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开，比如感知机求得的分离超平面就有无穷多个，为了求得唯一的最优分离超平面，就需要使用间隔最大化的支持向量机
2.1 分类预测确信度上图中，有A,B,C三个点，表示三个示例，均在分离超平面的正类一侧，点A距分离超平面较远，若预测点为正类，就比较确信预测是正确的；点C距离超平面较近，若预测该点为正类，就不那么确信；点B介于点A与C之间，预测其为正类的确信度也在A与C之间
通过上面的描述，当训练集中的所有数据点都距离分隔平面足够远时，确信度就越大。在超平面\(w^T X + b = 0\)确定的情况下，可以通过函数间隔和几何间隔来确定数据点离分割超平面的距离
2.2 函数间隔对于给定的训练数据集T和超平面（w,b）,定义超平面（w,b）关于样本\(（x_i,y_i）\)的函数间隔为：\[\overline{\gamma{_i}} = y_i(w\bullet{x_i} + b)\]
定义超平面（w,b）关于训练数据集T的函数间隔为超平面（w,b）关于T中所有样本点\(（x_i,y_i）\)的函数间隔之最小值：\[\overline{\gamma} = \min\limits_{i=1,...,N}\overline{y_i}\]
函数间隔可以表示分类预测的正确性及确信度，但是选择分离超平面时，只有函数间隔却是不够的
2.3 几何间隔对于给定的训练数据集T和超平面（w,b）,定义超平面（w,b）关于样本点\(（x_i,y_i）\)的几何间隔为：\[\gamma{_i} = \frac{y_i(w\bullet{x_i} + b)}{||w||}\]
定义超平面（w,b）关于训练数据集T的集合间隔为超平面（w,b）关于T中所有样本点\(（x_i,y_i）\)的集合间隔之最小值：\[\gamma = \min\limits_{i=1,...,N}\gamma_i\]
2.4 函数间隔和集合间隔之间的关系从上面函数间隔和几何间隔的定义，可以得到函数间隔和集合间隔之间的关系：\[\gamma_i = \frac{\overline{\gamma_i}}{||w||}\]
\[\gamma = \frac{\overline{\gamma}}{||w||}\]
2.5 硬间隔最大化分离超平面支持向量机学习的基本想法是找到能够正确划分训练数据集并且几何间隔最大的分离超平面，换句话说也就是不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开,硬间隔是与后面说明的软间隔相对应的
如何求得一个几何间隔最大化的分离超平面，可以表示为下面的约束优化问题：\[\max\limits_{w,b}\quad\gamma\]
\[s_.t.\quad\frac{y_i(w\bullet{x_i}+b)}{||w||}\geq\gamma,\quad{i=1,2,...,N}\]
根据上面函数间隔和几何间隔之间的关系，转换成下面的同等约束问题：\[\max\limits_{w,b}\quad\frac{\overline{\gamma}}{||w||}\]
\[s_.t.\quad\ y_i(w\bullet{x_i}+b)\geq\overline{\gamma},\quad{i=1,2,...,N}\]
由于当w,b按比例变换的的时候函数间隔\(\overline\gamma\)也会呈比例变化，先取\(\overline\gamma= 1\),再由于\(\frac{1}{||w||}\)最大化和最小化\(\frac{1}{2}{||w||}^2\)是等价的，于是得到：\[\min\limits_{w,b}\quad\frac{1}{2}{||w||^2}\]
\[s_.t.\quad\ y_i(w\bullet{x_i}+b)\geq 1,\quad{i=1,2,...,N}\]
由此得到分离超平面：\[w^{*} \bullet x + b^{*} = 0\]
分类决策函数：\[f(x) = sign(w^{*} \bullet x + b^{*})\]
求解拉格朗日对偶函数：\[L(w,b,a) = \frac{1}{2}{||w||}^2 - \sum_{i=1}^na_i[(y_i(x_iw+b)-1)]----(1)\]
对w求偏导:\[\frac{\partial L}{\partial w} = w - \sum_{i=1}^na_iy_ix_i = 0-----(2)\]
对b求偏导:\[\frac{\partial L}{\partial b} = \sum_{i=1}^na_iy_i = 0-------(3)\]
将（2）（3）带入（1）得到：\[maxL(a) = -\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^na_ia_jy_iy_jx_ix_j + \sum_{i=1}^na_i\]
s.t.
\[\sum_{i=1}^na_iy_i = 0\]
\[a_i >= 0\]
对于线性可分的数据集可以直接使用硬间隔最大化超平面进行划分，但对于线性不可分的某些样本点不能满足函数间隔大于等于1的约束条件，为了解决这个问题，可以对每个样本点\((x_i,y_i)\)引进一个松弛变量\(\xi >= 0\),使函数间隔加上松弛变量大于等于1，这样约束条件变为：\[yi(w\bullet x_i + b) >= 1- \xi_{i}\]