本章将学习如下内容：
- 直观理解支持向量机的工作原理
理论基础
线性可分数据
观察下图中的两类数据（红色与蓝色）。在使用kNN算法时，需要计算测试数据与所有训练样本的距离，并选择最近邻样本。 这种方法既需要存储全部训练样本（内存消耗大），又需计算所有距离（时间成本高）。 但针对图示的线性可分数据，真的需要如此复杂的处理吗？
考虑另一种思路。寻找一条直线 $f(x)=ax_1+bx_2+c$，将两类数据划分到不同区域。对于新测试数据 $X$，只需代入 $f(x)$： 若 $f(X) > 0$，则属于蓝色组，否则属于红色组。
这条直线称为决策边界（Decision Boundary）。该方法计算简单且内存高效。 能够通过直线（或高维空间中的超平面）完全分割的数据，称为线性可分数据（Linear Separable）。
观察上图可发现，存在多条可能的划分直线。我们应如何选择？直观而言，最优直线应当尽可能远离所有数据点。原因在于： 抗噪声需求：实际数据可能存在噪声干扰；泛化能力：最大化边界距离可提升分类器鲁棒性； 支持向量机(SVM)的核心思想正是寻找与所有训练样本具有最大最小距离的直线（或高维超平面）。 如下图所示，加粗的中央直线即为最优决策边界。
在确定决策边界时， 训练数据需求：不需要全部样本。 关键样本仅需靠近异类边界的样本（如图中1个蓝色实心圆和2个红色实心方块）。 这些关键样本称为支持向量(Support Vectors)，穿过它们的边界线称为支持平面(Support Planes)。 仅凭这些向量即可确定最优决策边界，实现数据量精简、计算效率提升。
支持向量机的核心原理是：首先找到两个最优超平面来划分数据， 其中蓝色数据满足 $w^Tx+b_0 > 1$，红色数据满足 $w^Tx+b_0 < -1$，这里 $w$ 是权重向量 （$w=[w_1, w_2,..., w_n]$），$x$ 是特征向量 ($x = [x_1,x_2,..., x_n]$) 为偏置项。权重向量决定决策边界的朝向，偏置项决定其位置。 决策边界被定义为这两个超平面的中线，表达式为 $w^Tx+b_0 = 0$。 支持向量到决策边界的最小距离公式为 $distance_{support \, vectors}=\frac{1}{||w||}$，而分类间隔是该距离的两倍，我们需要最大化这个间隔，即通过某些约束条件来最小化一个新的函数 ($L(w, b_0)$)。
$$\min_{w, b_0} L(w, b_0) = \frac{1}{2}||w||^2 \; \text{subject to} \; t_i(w^Tx+b_0) \geq 1 \; \forall i$$
其中，$t_i$ 表示每个类别的标签，且 $t_i$ 的取值范围为 $t_i \in [-1,1]$。
非线性可分数据
当数据无法用直线分割时（例如一维空间中"X"位于-3和+3处，"O"位于-1和+1处的数据显然不是线性可分的）， 可以通过函数映射（如使用 $f(x) = x^2$ 将"X"映射到9、"O"映射到1）使其变为线性可分。
也可以将这一维数据转换为二维数据，通过映射函数 ($f(x)=(x,x^2)$)，使"X"变为(-3,9)和(3,9)，"O"变为(-1,1)和(1,1)，这样数据就变得线性可分了。 简而言之，在低维空间中非线性可分的数据，在高维空间中更有可能变为线性可分。
一般来说，我们可以将d维空间中的点映射到更高维的D维空间 $(D>d)$ 来检验其线性可分的可能性。核心思想是通过在低维特征空间中的计算，来间接求解高维核空间中的点积运算。
以二维空间中的两个点 ($p=(p_1,p_2)$ 和 $q=(q_1,q_2)$)为例，设 $\phi$ 为将二维点映射到三维空间的映射函数，具体形式如下：
$$\phi (p) = (p_{1}^2,p_{2}^2,\sqrt{2} p_1 p_2) \phi (q) = (q_{1}^2,q_{2}^2,\sqrt{2} q_1 q_2)$$
定义核函数 $K(p,q)$ 用于计算两点间的点积，其表达式如下：
$$\begin{aligned} K(p,q) = \phi(p).\phi(q) &= \phi(p)^T , \phi(q) \\ &= (p_{1}^2,p_{2}^2,\sqrt{2} p_1 p_2).(q_{1}^2,q_{2}^2,\sqrt{2} q_1 q_2) \\ &= p_{1}^2 q_{1}^2 + p_{2}^2 q_{2}^2 + 2 p_1 q_1 p_2 q_2 \\ &= (p_1 q_1 + p_2 q_2)^2 \\ \phi(p).\phi(q) &= (p.q)^2 \end{aligned}$$
这意味着，三维空间中的点积运算可以通过二维空间中的平方点积来实现，这种方法可推广到更高维空间，使我们能够直接从低维特征计算高维特征。 经过映射后，我们就获得了高维特征空间。
但除了这些概念外，还存在分类错误的问题——仅找到具有最大边界的决策边界是不够的，还需考虑误分类误差。 有时，选择较小边界但能减少误分类的决策边界可能更优。 因此需要调整模型，使其在最小化误分类的同时找到具有最大边界的决策边界，此时最小化准则修改为：
$$min \; ||w||^2 + C(distance \; of \; misclassified \; samples \; to \; their \; correct \; regions)$$
下图展示了这一核心概念：为每个训练样本定义一个松弛变量 $\xi_i$（代表该样本到其正确决策区域边界的距离）。 当样本被正确分类时，$\xi_i$=0（此时样本位于其所属类别的支持平面上）； 而误分类样本的$\xi_i$>0，表示其偏离正确区域的程度。
因此，新的最优化问题表述为：
$$\min_{w, b_{0}} L(w,b_0) = ||w||^{2} + C \sum_{i} {\xi_{i}} \text{ subject to } y_{i}(w^{T} x_{i} + b_{0}) \geq 1 - \xi_{i} \text{ and } \xi_{i} \geq 0 \text{ } \forall i$$
参数C的选择取决于训练数据的分布特性，虽然没有通用准则，但可参考以下原则：
- 较大C值会减少误分类但缩小间隔（此时误分类代价较高，优化目标会优先最小化分类错误）；
- 较小C值则增大间隔但容忍更多分类错误（此时优化过程更关注寻找大间隔超平面而非严格限制误分类项）。