多元分类

在分类问题中，二元分类器比较特别，因为很多例子都可以在特征空间上画出一个超平面来分离两个类别。并且针对二元分类的结果，有很多方法可以对其分类的准确性进行衡量。

假设我们可以使用的唯一一个合适的统计分类器是二元分类器，我们如何才能将其泛化到超过两个类别的分类问题中呢？现在我们使用概率论来推导出答案。

假设我们通过多次将类别分成两个集合来设计二元分类器集合。编码矩阵 A 代表分割方式：矩阵第 i 行代表在第 j 列使用-1/+1 来分隔第 i 个二元分类器，也就是说第 j 个类别标签被转换成用于训练的-1/+1 和代表完全被排除的 0。

多类别问题的条件概率与二元分类器条件概率之间的关系如下：

重新排列之后，我们可以将其转换成线性系统：

其中，Ri 代表第 i 个二元分类器的条件概率的差分。

例如，使用「一对多」方法进行多类别分类。这里，我们比较每个类别和其他类别。编码矩阵如下（与狄拉克δ函数类似）：

前面假设二元分类器的条件概率得到正确评估。否则，我们需要给得到的多类别概率加上约束条件。忽视第二个参数，条件概率与单变量概率具有同样的属性。首先，它们的总和都应该为 1：

其次，它们都是正值：

[描述来源：从概率论到多分类问题：综述贝叶斯统计分类|机器之心]

一般来说，将多元分类问题化简为多个二元分类问题的策略可以分为one-vs.-rest或one-vs.-one。

one-vs.-rest:（或one-vs.-all，OvA或OvR）策略需要为每一个类建立一个唯一的分类器，属于此类的所有样例均为正例，其余的全部为负例。这一策略需要基础分类器去产生一个实值置信度以供决策，而不仅仅是一个类标签；单独产生的类标签可能会导致归类的不明确，以致于一个样例会被预测属于多个类。

用伪代码表示，一个OvA学习者的训练算法从一个二元分类学习者L中建立，具体如下：

输入：

• L，一个学习者（二元分类器的训练策略）
• 样例集X
• 标签集y 使y_i ∈ {1, … K} 是样例X_i的标签

输出：

• 一个分类器的序列f_k ， k ∈ {1, …, K}

程序：

• For each k in {1, …, K}:
• • 构建一个新标签向量 y_i = 1 where y_i = k_i, 0 (or −1) elsewhere
  • 将L 应用于X，y 以获得f_k

做出决策意味着要将所有的分类器应用于一个未知样例x ，并且预测出产生最大置信度的分类器所对应的标签k：

尽管这一策略很流行，但它是一个受些许问题困扰的启发法。首先，分类器之间置信值的范围可能不同。其次，即使一个训练集的类是均衡分布的，二元分类器学习者所看到的类分布也是不均衡的，因为它们所看到的负例集通常比正例集来的大。

one-vs-one: 在one-vs-one （OvO） 化简中，对于一个K类多元问题，训练 K (K − 1) / 2 个二元分类器；每一个从初始训练集中收到一对类样例，并且必须学习去区分这两个类。在预测时间内，会有一个投票：所有 K (K − 1) / 2 个解释器被应用于一个未知样例，并且那个得到最多"+1" 预测的类会成为组合分类器的预测结果。

像OvR一样, OvO也受些许问题困扰：在它输入空间的一些区域会收到相同数目的投票。

[描述来源：维基百科 URL：https://en.wikipedia.org/wiki/Multiclass_classification]

发展历史

K-nearest neighbor（KNN）算法是一种常用于多元分类的算法，在其思想被提出后，1967年，Cover 和 Hart 在论文《Nearest neighbor pattern classification》中正式介绍了 KNN，也是KNN的首次正式的提出。在2006年，Zhang, M. L., & Zhou, Z. H.在有限的数据中设计了对多标签数据的KNNs算法《ML-KNN: A lazy learning approach to multi-label learning》。

另一类用于分类问题的经典算法是决策树（Decision tree），其最早可以追溯到1948年左右，当时克劳德·香农介绍了信息论，这是决策树学习的理论基础之一。从Quinlan于1986年发明了ID3算法后，决策树算法一直都很流行，它们训练很快并且可扩展。几年后，Quinlan提出了C4.5算法。根据谷歌趋势和谷歌学术的数据，C4.5 仍然是各种决策树学习算法中最受关注和相关论文数量最多的。因此我们可以将其看作是单决策树学习应用中最流行的算法。

支持向量机（SVM）的早期应用也是分类问题，1992年，Bernhard E. Boser, Isabelle M. Guyon和Vladimir N. Vapnik提出了一种方法，通过将内核技巧应用到最大限度的超平面上，来创建非线性分类器。他们在光学字符识别问题上检测了他们的算法，实验结果表明，与当时其他学习算法相比，该算法有很好的泛化能力。他们还提出该技术适用于各种分类函数，包括感知器，多项式和径向基函数（Radial Basis Functions）。

朴素贝叶斯（Naive Bayes）也能够自然扩展到具有两个以上类别的分类问题，但该算法的起源难以确定。

当然，适用于多元分类问题的算法还有神经网络。作为反向传播算法的首个实际应用，Yann LeCun于1989年提出LeNet时即是使用神经网络进行读取“手写”数字。1998年，Yann LeCun，Leon Bottou，Yoshua Bengio和Patrick Haffner在发表的论文中回顾了应用于手写字符识别的各种方法，并用标准手写数字识别基准任务对这些模型进行了比较，结果显示卷积神经网络的表现超过了其他所有模型。他们同时还提供了许多神经网络实际应用的例子，如两种用于在线识别手写字符的系统和能每天读取数百万张支票的模型。在其后的发展中，神经网络也一直与多元分类问题有着紧密的联系，如ImageNet的图像分类比赛。2016年，Gao Huang等学者从 ResNet 的恒等／跳跃连接（identity/skip connections）中直接获取灵感，提出了DenseNet，它们可以缓解消失梯度问题，加强特征传播，鼓励特征重用以及大幅减少参数数量，在ImageNet上实现了错误率的明显下降。

主要事件

发展分析

瓶颈

多元分类的算法有很多，但不同的问题往往需要使用不同的算法，缺乏易于使用、表现稳定的通用算法；此外，神经网络虽然在众多分类任务中表现出色，但也有比较严重的过拟合问题。

未来发展方向

多元分类研究有比较高的商业价值，因此开发AutoML（自动化机器学习）应用是一个可能的方向，它能够帮助没有机器学习背景的人快速解决多元分类问题，实现产品化。

Contributor：Yuanyuan Li