问题描述
大多数分类器主要是解决二分类问题，对只有两个类别标签的数据集分类，比如logistic回归和支持向量机。多分类是对两个以上类别标签的数据集分类。
解决多分类问题的主要思路包括：
- 直接采用具备多分类能力的多分类器；
- 从数据集和使用方法入手，采用二分类器解决多分类问题；
- 扩展二分类器，使其成为能够解决多分类问题多分类器。
多分类器
k最近邻分类器是最简单的多分类器。决策树解决多分类问题几乎和二分类问题一样容易实现。
神经网络是天生的多分类器，上图展示了神经网络的多分类策略，其中的输出是0和1组成的向量，而非类别标签。类别数$K(K \geq 3)$时，输出层需$K$个神经元；$K＝2$时，输出层只需一个神经元[1, P. 2]。预测时，输入样本属于输出“概率”最大的类别。
二分类器解决多分类问题
二分类器解决多分类问题，基本思想是将数据集分割为多个二分类数据集，组合应用二分类器，典型的方法有：一对多（OVA，one-vs-all）、一对一（OVO，one-vs-one）和多对多（AVA，all-to-all）。
Ryan Rifkin等人指出，如果基本的二分类器调整和正则化做得好，简单的one-vs-all策略也可和其它方法一样好[2]1。
基本方法
一对多的方法是针对每一类训练一个二分类器，将它与其余所有数据进行二分类，若有$K(K > 2)$个类别，就需要训练$K$个分类器，这种方法也叫one-vs-rest。
一对一的方法是任意两类之间都训练一个二分类器，若有$K$个类别，就需要训练${K(K-1)\over 2}$个分类器。
logistic回归通过“概率”最大化判断类别[3, Pp. 30-31]。
支持向量机将$\mathbf x^T\boldsymbol\theta^{(i)}$值最大的作为输入样本的类别$i$[4, P. 30]。
实现技术
若采用投票机制，one-vs-all和one-vs-one都存在如上图绿色所示的争议区域（$\mathcal R_i$表示类别$\mathcal C_i$所属的区域）[5, Pp. 182-183]。上图左的争议区域表示既可能属于$\mathcal C_1$又可能属于$\mathcal C_2$；上图右的争议区域表示不属于任何一个类别。
对于one-vs-all的$K$个线性分类器，输入对象属于输出值最大分类器对应的类别，在这种情况下类别所属的区域是单联通的凸区域（singly connected and convex）2。
二分类器扩展为多分类器
采用hinge损失函数，可以直接将支持向量机推广到多分类支持向量机，理论上该方法数据损失项可达0，常规的one-vs-all方法则不行。
采用交叉熵损失和softmax函数，可以推导出用于多分类的softmax分类器，可视为logistic回归在多分类问题上的推广。
结构化支持向量机（structured SVM）也可以解决多分类问题[6]3。
参考资料
- [1]A. Ng, “Neural Networks: Learning.” Coursera, 2014. [Online]
- [2]R. Rifkin and A. Klautau, “In defense of one-vs-all classification,” Journal of Machine Learning Research, vol. 5, pp. 101–141, 2004.
- [3]A. Ng, “Logistic Regression.” Coursera, 2014. [Online]
- [4]A. Ng, “Support Vector Machines.” Coursera, 2014. [Online]
- [5]C. M. Bishop, Pattern Recognition and Machine Learning. New York: Springer-Verlag, 2006.
- [6]I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun, “Support Vector Machine Learning for Interdependent and Structured Output Spaces,” in Proceedings of the Twenty-first International Conference on Machine Learning, New York, 2004, pp. 104–111. [Online]
