multiclass_svm.md

基本的支持向量机时一个两类分类器。然而在实际应用中，我们经常要处理涉及到$$ K > 2 $$个类别的问题。于是，将多个两类SVM组合构造多类分类器的方法被提出来。

一种常用的方法(Vapnik, 1998)是构建$$ K $$个独立的SVM，其中第$$ k $$个模型$$ y_k(x) $$在训练时，使用来自类别$$ C_k $$的数据作为正例，使用来自剩余的$$ K − 1 $$个类别的数据作为负例。这被称为“1对剩余”(one-versus-the-rest)方法。然而，在图4.2中，我们看到使用独立的分类器进行决策会产生不相容的结果，其中一个输入会同时被分配到多个类别中。这个问题有时可以通过：对于新的输入$$ x $$，使用

$$ y(x) = \max_ky_k(x) \tag{7.49} $$

做预测，来解决。不幸的是，这种启发式的方法会产生：不同的分类器是在不同的任务上进行训练的，无法保证不同分类器产生的实数值$$ y_k(x) $$具有恰当的标度的问题。

“1对剩余”方法的另一个问题是训练集合不平衡。例如，如果我们有$$ 10 $$个类别，每个类别的训练数据点的数量相同，那么用于训练各个独立的分类器的训练数据由$$ 90% $$的负例和仅仅$$ 10% $$的正例组成，从而原始问题的对称性就消失了。Lee et al.(2001)提出了“1对剩余”方法的一种变体。这种变体修改了目标值，使得正例类别的目标值为$$ +1 $$，负例类别的目标值为$$ − 1 / (K - 1) $$。

Weston and Watkins(1999)定义了一个单一目标函数用来同时训练所有的$$ K $$个SVM，基于的是最大化每个类别与其余剩余类别的边缘。然而，这会导致训练过程变慢，因为这种方法需要求解的不是N个数据点上的$$ K $$个独立的最优化问题（整体代价为$$ O(KN^2) $$），而是要求解一个规模为$$ (K − 1)N $$的单一的最优化问题，整体代价为$$ O(K^2N^2) $$。

另一种方法是在所有可能的类别对之间训练$$ K(K−1) / 2 $$个不同的二分类SVM，然后将测试数据点分到具有最高“投票数”的类别中去。这种方法有时被称为“1对1”（one-versus-one）。同样的，我们从图4.2可以看到这会导致最终分类的歧义性。且对于较大的$$ K $$，这种方法要比“1对剩余”的方法花费更多的训练时间。类似地，为了计算数据点，这种方法需要更多的计算。

后一个问题可以通过将每对分类器组织成有向无环图（不要与概率图模型弄混淆）的方式解决，这就产生了DAGSVM（Platt et al., 2000）。对于$$ K $$个类别，DAGSVM共有$$ K(K−1) / 2 $$个分类器。每次对新的测试点分类时，只需要$$ K − 1 $$对分类器进行计算。选定的分类器是根据遍历图的路径确定的。

Dietterich and Bakiri(1995)提出了一种不同的方法解决多分类问题。这种方法基于的是误差-修正输出编码，并且被Allwein et al.(2000)用到支持向量机中。这种方法可以被看做“1对1”投票方法的一个推广。这种方法中，用来训练各个分类器的类别划分的方式更加一般。$$ K $$个类别本身被表示为选定的两类分类器产生的响应的集合。结合一套合适的解码方法，这种方法对于错误以及各个分类器的输出的歧义性具有鲁棒性。虽然将SVM用于多分类问题仍然是一个没有标准答案的问题，但是在实际应用中，“1对剩余”是被最广泛使用的方法，尽管它有特定的形式，并且有着实际应用的局限性。

也存在单一类别（single-class）支持向量机，它解决与概率密度估计相关的无监督学习问题。但是，这种方法不是用来对数据的概率密度建模，而是想找到一个光滑的边界将高密度的区域包围起来。边界用来表示概率密度的等分点，即从概率密度分布中抽取的一个数据点落在某个区域的概率由一个0到1之间的固定的数给出，这个数事先指定好。与进行整体的密度估计相比，这个问题更加受限，但是对于某些具体的应用已经足够了。关于使用支持向量机解决这个问题，已经有两种方法被提出来。Scholkopf et al.(2001)的算法尝试找到一个超平面，将训练数据中的固定比例$$ v $$的数据从原始数据集中分离，同时最大化超平面与原点之间的距离（边缘）。Tax and Duin(1999)寻找特征空间中包含数据集的ν比例数据的最小球体。对于只是$$ x − x' $$的函数的核$$ k(x, x') $$，这两种算法等价。