前言
支持向量机（Support Vector Machine，SVM）在70年代由苏联人 Vladimir Vapnik 提出，主要用于处理二分类问题，也就是研究如何区分两类事物。
本文主要介绍支持向量机如何解决线性可分和非线性可分问题，最后还会对 SMO 算法进行推导以及对 SMO 算法的收敛性进行简要分析，但受限于篇幅，本文不会对最优化问题、核函数、原问题和对偶问题等前置知识做过于深入的介绍，需要了解相关知识的读者朋友请移步其它文章、资料。
SVM 推导过程主要参考自胡浩基教授的机器学习公开课程；SMO 算法相关则主要来自于 Platt 的论文以及网上公开资料，相关链接见文章末尾。
快速理解
举一个粗糙的例子。
科学家收集到一批天体的观测数据，现在需要按行星和恒星两种类型对这些未知天体进行分类。显然这是一项费时费力的工作，我们希望通过机器学习算法，让计算机自动帮我们做区分。
我们拿到了往年一批已经分类好的天体数据样本，将这些样本绘制到一个二维坐标系上，如下：
这是一个简单的二维特征空间，通过肉眼观察这些数据我们发现，恒星和行星这两种天体，根据他们的辐射强度和质量的不同，分别聚集在坐标系的左下角和右上角两个区域。
于是我们根据自己的判断作了这样一条直线：
这时，我们就拥有了一条可以区分恒星和行星的直线，当点落在直线左侧的可判断为行星，如果落在右侧则为恒星。
但是上面这条直线是我们凭借经验所作，显然在坐标系中能够划分这两类天体的直线有无数条，如下图：
这种情况下，如何定义一个性能指标去找到一条最合适的直线就是支持向量机要解决的首要问题。
Vapnik 提出了使用如下一对平行线的 间隔（Margin）来作为这个性能指标，间隔越大，意味着最终获得的直线更具普适性，如下图：
上面坐标系中，首先是在两种样本中间找一对平行线，我们从 0 开始扩大平行线的间隔 d，直到两条线分别经过两种样本的一个或多个点为止，这些点被称为 支持向量（Support Vector），当间隔 d 最大时，两条平行线的正中间我们可以取到第三条平行线，如下图红色虚线所示：
在众多的分界线当中，这条红色直线被认为是一个最优解，称为 决策边界（Decision Boundary）。
上面的例子中，两种样本各自会有一片聚集密度较高的区域，而远离这片区域，样本逐渐变得稀疏，样本越稀疏意味着落到该区域的概率越低。决策边界直线在兼顾划分不同样本的同时，还需要放置在两种样本之间最不可能出现的区域，那么，当间隔 d 取最大时即为最理想的状态。
目前为止我们可以得到一些初期结论：
1）支持向量机用于解决二分类问题，目的是求出一条直线尽可能地划分两种不同的样本；2）支持向量到决策边界的距离都相等；3）在所有向量中，支持向量到决策边界的距离最短。
实际应用场景中，我们经常会遇到比上面例子复杂得多的问题。例如通过图像区分月季和玫瑰，我们需要从颜色、花瓣形状、叶子形状等等多个特征进行综合判断，训练样本最终会落到一个多维特征空间中，此时划分两种训练样本的边界将会是一个超平面，称为 分离超平面（Separating Hyperplane）。
支持向量机本质是用线性方程去解决二分类问题，而在实际问题中，不同的样本在特征空间中往往“犬牙交错”，SVM 这种“一刀切”的方式似乎将变得不再奏效。别担心，后面笔者将会花大篇幅着墨如何处理这种线性不可分的样本。
支持向量机的两种模型
支持向量机有两种模型：线性模型、非线性模型
一个线性不可分的例子，无论如何作直线都无法区分两种样本
线性可分的例子
为了方便推导，接下来对样本做一些定义。
训练样本的定义
比如现在有 class1 和 class2 两种训练样本，分布在这样一个二维特征空间中：
那么，对于第 i 个训练样本可以用 向量 和 标签 去定义它：
(向量,标签)⇔(Xi,yi)
Xi=[xi1xi2]，yi∈{1,−1}
标签 yi 可以理解为第 i 个样本所属的类别，SVM 用于处理二分类问题，那么我们可以使用 +1、−1 分别表示 class1 和 class2 两种训练样本。
从上面二维特征空间的例子，进一步推广到 m 维特征空间中的 N 个训练样本：
(X1,y1),(X2,y2),⋯,(XN,yN)
可以记作：
{(Xi,yi)}Ni=1
Xi=⎡⎣⎢⎢⎢⎢xi1xi2⋮xim⎤⎦⎥⎥⎥⎥，yi∈{1,−1}
现在我们已经知道了训练样本的定义，那么接下来将对 SVM 线性、非线性两种模型分别进行讨论。
线性模型
如果训练样本 线性可分（Linear Separable），可以用这样一个方程来表示分离超平面：
ωTX+b=0
这里的 X 即上一小节提到的样本的向量，ω 和 X 是维度相同的向量，ωT 是向量 ω 的转置，b 是某个实数：
ω=⎡⎣⎢⎢⎢⎢ω1ω2⋮ωm⎤⎦⎥⎥⎥⎥,X=⎡⎣⎢⎢⎢⎢x1x2⋮xm⎤⎦⎥⎥⎥⎥,b∈R
X 是已知的向量，最终我们是要求出 ω 和 b，使得分离超平面正确分割开两种样本。