Google 代码之夏，Multiclass Learning

虽然各种大小事情和死线依旧是蜂拥而来，但是我想这个假期我“Officially”应该是主要在做 Google Summer of Code 。因为难得的很长的假期，以后又更少有机会回家了，所以理所当然的要呆在家里，但是为了避免一个假期过后荒废得最后连数字都不会数了，我又一直苦恼在家里应该做些什么事情——必须要是有外力来强制进度的事情，否则毫无疑问地会慢慢荒废掉，因为家里本就是一个适合休息堕落的环境呀。最后想到 GSoC 的时候突然眼睛一亮：这不就是为我这种情况量身定做的吗？！

将军 (Shogun) 是众多项目中我比较感兴趣的一个。因为肯定是希望做跟机器学习相关的项目呀，所以实际上 shogun 是项目列表里最相关的一个了。简单地来说就是用 C++ 写的一个机器学习算法库，里面实现了各种常用的算法，并且把许多著名的算法（像 LibSVM、LibLinear、Vowpal Wabbit 等）也都统一的包装起来，然后再提供了各种语言像 Matlab、Python、R 等下面的接口供方便调用。

不过虽然我以前也见到过 Shogun ，但是却并没有实际用过。以前见到这个名字的时候还以为是日本人写的库（因为 Shogun 是日语单词“将军”呀），后来了解了一下才发现实际上是有德国的 Max Planck Institute (MPI) 里的一个组发起的项目（这个 MPI 里有好多机器学习非常强的组呢！），而这个略奇怪的名字实际上是由最初的两个作者 Soeren Sonnenburg 和 Gunnar Raetsch 的名字的开头 So 和 Gun 拼起来再变化得到的。但是究竟是如何查到这个日语单词的呢？嗯，也许是 Google 了一下看到 wikipedia 的页面了吧……不过，Soeren 说你可以给 Shogun 画个好看点的 logo 的……许多年前参加 GSoC 的时候也被叫给当时的项目画了个 Logo ，不过这次就真的完全没有想法了啊，其实我觉得就这样用汉字做 logo 也挺不错的。

总的来说感觉 GSoC 的申请难度也变得比以前大了一些。特别是发现现在有一条虽然没有由 Google 提出来，但是在大部分 organization 的 requirements 里都以不同的形式提到：提交项目 proposal 的同时，需要把项目的代码下载下来，把开发环境搭建好，并提交一个小 patch 证明你有在这个项目上工作的能力。不得不说这是一个非常有效的筛选方法，至少可以把一大半 unqualified 的人直接刷掉了，但是另一方面也是让人觉得比较“狡猾”的一个条款：因为如果提交的代码最后又被刷掉的话，岂不是白干活了？ :p 这样的情况是完全有可能发生的，因为不同的 organization 下的项目难度很不一样，申请者的背景不同也造成竞争激烈程度不一样；而每个 organization 的 slot 数目又是有限的，如果碰到竞争很激烈的情况，即使非常强的 candidate 也有可能被刷呀。其实对于自己这次申请也是直到结果出来之前都没有把我的，虽然自己在机器学习、开源和编程这三个方面的背景都不弱，但是其他的 candidate 也很强，而且也都很积极。

所以一般都是会申请多个 organization 以求保险的，我本来也是这么打算的，和机器学习相关的项目也都查了一遍列出来，但是最终也只提交了 Shogun 的 proposal ，因为实在是没有时间去把其他项目也这么细致的了解，然后提交 patch 什么的了。实际上 GSoC 这样的策略非常成功，虽然说是提交简单的 patch 就可以了，但是大家也都很努力，为了不被刷掉的话，也就不能拘泥于过于 trivial 的 patch 了，我自己在结果公布之前也已经提交了 30+ 个 patch ，实现了好几个 non-trivial 的模块和一次比较大规模的重构，所以到 GSoC 开始的时候实际上已经对整个项目有相当的了解了。对于最后能选上的同学来说，这当然是件好事；不过大概也有挺多白干了许多活的人吧。虽然说对开源做贡献是值得鼓励的事，但是以这种方式来说，总觉得有些“上当受骗”的怪怪的感觉哈哈…… =.=bb

Shogun 这次拿到 9 个 slots ，由于准备的 mentor 数目不够，而负责人又坚持一个 mentor 只带一个学生，最后把 slot 退了一个给 Google 。最终组成的队伍真是来自世界各地呀，有俄国、西班牙、捷克、德国……当然还有中国。总而言之虽然大家都在 IRC 上用英语交流，但是似乎很少有 native English speaker 出现在那里，一开始我还不太习惯，跟不上大家聊天的速度，有时候还要查查词典什么的，不过后来渐渐地也习惯起来了。但基本上大家都在用一些简化的网络聊天室用语再加上 broken 的 illegal 的语法之类的，反正大家都不是 native …… ^_^bb 估计最后这个也不会对我英语有太大帮助吧，或者我应该祈祷不要养成坏习惯？

IRC 也算是一种不错的交流方式。因为有时候 Email 的延迟太大了，虽然和面对面交流还是有一定差距的，但是有时候在 IRC 上讨论问题还是比较有效率的。有时候也会在上面开玩笑，比如大家一直都说要给 Soeren 送一本 STL 的书作为礼物。一开始我没明白背后的深意，后来随着我提交更多的代码，才渐渐发现端倪，然后去确认了一下，果然 Soeren 他对 STL 恨之入骨……哈哈。我还是第一次见到 C++ 用户本身痛恨 STL 的，不过也没有办法呀，因为现在整个项目基本上是由 Soeren 把关……我也有碰到提交的 patch 用了太多了 STL 被打回来改了用 Shogun 里自己的相应类的情况，真是让人伤心欲绝呀，STL 这么好用的东西，而且弱弱地说我们 Shogun 里自己提供的那些等价的接口很难用呀…… >_< 。 不过我们都是一有机会就尝试说服他的……当然他也不是完全不讲道理的人，比如 Shogun 里用了一套很引用计数系统，我猜可能是为了和各种其他语言的接口共同工作，为适应 SWIG 而设计出来的，要命的是这个引用计数完全是人肉的，到处都要 SG_REF 呀，SG_UNREF 的，我基本上就彻底崩溃了，对于像我这样不熟悉这套系统和相应的 convention 的人来说，一开始写代码的时候基本上是每一个函数返回的一个指针我都必须得再打开那个函数的代码看看这个指针究竟是哪里来的，要不要人肉 SG_UNREF 之类的，相当地累。结果在我的苦口婆心之下，趁在准备 GSoC 的 codebase 前期重构的机会，Soeren 把其中的矩阵和向量等几个类改成了用 C++ 的 RAII 机制来把引用计数做成了 automatically ，他用了一个好玩的词：说现在的引用计数能 automagically 工作了！ 😀 哎，既然都开始吐槽了，当然就不得不吐槽一下 Blas 和 Lapack 了，嗯嗯，没错，（应该还是为了追求效率吧，）Shogun 里并没有用什么 Armadillo 之类的看起来很酷的库，而是裸用 Blas 和 Lapack 的，这两个家伙的大名我是早有耳闻，但是并没有真正接触过，结果在实现 Least Angle Regression 的时候狠狠的用了一下，真的是有种想自杀的冲动，比如写个矩阵求逆都要花上半个小时来 figure out ，写完了还不知道自己写得对不对，还要单独拿出来写个小程序来测试一下这段代码到底是不是实现了对应的功能——这种大概就是属于学习曲线超级陡峭的库了吧。

好了，吐槽完毕，当然 Shogun 并不是一无是处的，要不然我干嘛来做这个东西。如果是作为用户来说，是感觉不到这些东西的，而且我们大家也会努力让它变得更加 developer-friendly 一些的。 😀 我这次参与的 topic 是 Multiclass Learning ，接下我就简单介绍一下这个话题吧。

实际上，在生活中遇到的分类问题，绝大部分都是 multiclass 的，比如，handwritten digit 识别，就是 0~9 这十个类别的分类。然而，和现实相反的是，我们的机器学习研究领域，不管是学习理论方面还是具体的算法方面，都主要集中在回归 (Regression) 和二分类 (Binary Classification) 上。其实在理论或者数学研究里这是很常见的，有时候选择某些方法或者模型，纯粹就是因为这样易于推导/计算，或者甚至就是其他的方式压根推导/计算不出来，只能这样简化。这当然是无可厚非的，理论要一步一步地发展呀，先从最基本的开始。

所以说，到现阶段，其实 Regression 和 Binary Classification 问题不管是从理论还是算法方面都已经相对成熟了，人们也就渐渐的越来越多的关注起诸如 Multiclass 问题、Structured Output 问题等更加复杂的情况起来。Multiclass 的问题在 vision 里好像出现得比较多，而 Structured Output 也是在 Bioinformatics 、NLP 还有 vision 里都渐渐受到越来越多的关注。比如 vision 里的 object detection ，这个问题的输出算是一个矩形框，这是一个有“structure”的输出，而不是平凡的一个数字；再比如 NLP 中预测一个句子的语法结构，它的输出则是一棵语法树；而 Bioinformatics 里有可能问题的输出是一个基因序列 (Sequence) 等等。

总而言之 Structured Output Learning 一般用来指问题的输出是具有复杂结构的情况，上面举的例子都是在说输出对象本身的结构（比如一棵树的结构），不过我更倾向于考虑输出空间这整个空间的结构，例如所有语法树构成的空间，可以在这个空间上定义一个度量，来衡量两棵语法树之间的距离等等。事实上很多 Structured Output Learning 算法就是这么做的——利用输出空间里的特殊的结构来设计算法，实现在输出空间中找到最优的结果。

虽然这里扯到 Structured Output Learning 看起来有些跑题，不过我这里其实主要想提一下的是，在我看来这几个问题都是可以统一来看待的。对于 general 的 machine learning 问题，我们是去估计一个 $f:\mathcal{X}\rightarrow\mathcal{Y}$ ，对于回归问题，$\mathcal{Y}=\mathbb{R}$ ，而对于普通的 Multiclass 问题，则 $\mathcal{Y}=\{1,\ldots,K\}$ ，这里 $K$ 是类别数。

在一个极端上，回归问题是比较“简单”的，不论是从算法上还是从理论上的工作都已经很成熟了。我觉得，之所以如此，是因为这里的输出空间 $\mathcal{Y}=\mathbb{R}$ 实在是结构异常良好了。我们都知道，基本上再找不到比欧氏空间性质更好的了，内积、度量、范数应有尽有，而且还是线性的，并且在这里的一维欧氏空间里还有全序，并且是个 field ，可做加减乘除各种运算……简直犹如天堂一般。

而另一个极端呢？在普通的多分类问题中，$\mathcal{Y}$ 是一个离散的集合，啥结构都没有，或者最多只能有一个 trivial 的 discrete metric

\[
d(x,y) = \begin{cases}1 & x\neq y\\ 0 & x=y\end{cases}
\]

所以在这种集合上做计算呀、搜索呀、优化呀什么的，简直是寸步难行。不过这里有一个特例就是二分类问题，由于它可以很容易与回归问题建立起联系，所以相对来说办法也更多一些。由于在一点结构也没有的普通集合上比较难有所作为，于是现在的 multiclass 分类问题其实有很大一部分算法是将问题转化为 binary classification 问题来解决的（具体我们后面会在讲）。

比如我们可以看一下最简单的 Linear Regression 算法，它的目标函数是

\[
\min_{w\in\mathbb{R}^m}\sum_{i=1}^n \ell(w^Tx_i,y_i) = \min_{w\in\mathbb{R}^m}\sum_{i=1}^n (w^Tx_i – y_i)^2
\]

这里的 loss function $\ell(y,y’) = (y-y’)^2$ 要求在 $\mathbb{R}$ 上能做减法和平方运算，并且这样能得到一个合理的度量。在多维线性回归中，$\mathcal{Y}=\mathbb{R}^p$ 没法直接算平方，可以改用这样的 loss function

\[
\ell(y,y’) = \|y-y’\|^2
\]

这在一维情况下和刚才是等价的。但是如果在普通的啥结构都没有的空间中就没法进行了，首先减法运算就没有。

不过在这两个极端中间呢，大体就可以算是 Structured Output Learning 了，这里的 $\mathcal{Y}$ （比如所有语法树的集合）当然没有 $\mathbb{R}$ 那么优良（比如任意拿两棵树来，是不太好定义他们之前的顺序关系的），但是却又不像平凡的集合那么贫瘠（比如不同的树之间的距离远近通常是可以区分开来的）。所以说，在 $\mathcal{Y}$ 上有了一定的结构，于是就可以干点事情了，取决于具体的 $\mathcal{Y}$ 以及不同的结构，也就可以设计出不同的算法。

比如在 Structured Output Learning 中最经典的算法之一：SVM^light 的作者所提的算法 SO-SVM （见论文 Support Vector Machine Learning for Interdependent and Structured Output Spaces, ICML 2004 ），就是将 SVM 的 margin constraints 在整个 $\mathcal{Y}$ 上展开，然而同通常碰到的 general multiclass learning 不一样的是，常见的 Structured Output Learning 问题中 $\mathcal{Y}$ 都是非常大的，例如，在一个大小为 $N$ 的字母表上的长度为 $M$ 的所有 sequence ，这个空间里会有 $N^M$ 个元素。这样造成的后果就是目标函数的 constraints 超级超级多，更本没法优化。于是作者设计了一个算法，大意就是将违反得最厉害的 constraint 依次加进来，迭代地逼近原问题的解。为了求得“违反得最厉害的 constraint”，需要在空间 $\mathcal{Y}$ 中求解一个 argmax 的优化问题（原论文 Algorithm 1 中第 6 步）。

如果 $\mathcal{Y}$ 上没有任何结构的话，这个 argmax 问题的求解只能是把 $\mathcal{Y}$ 中所有元素全部遍历一遍进行搜索，但是这样完全没有解决 $\mathcal{Y}$ 空间过大的问题，计算量还是非常大。但是呢，如果 $\mathcal{Y}$ 有具体的结构的话，就不一样了。在 SO-SVM 的实验中，对于 Label Sequence Learning 问题，作者用 Viterbi Algorithm 来实现在 Sequence 空间中的 argmax 优化，而用一种改良的 CYK Algorithm 来做语法树空间中的 argmax 优化。这些算法都可以通过动态规划来实现，利用了 $\mathcal{Y}$ 的结构来避免了暴力搜索。

嗯，关于 Structured Output Learning ，具体的算法我了解得也比较少，而且这里是要讲 Multiclass Learning :p ，所以就先就此打住。Generic 的 multiclass 问题一般 $\mathcal{Y}$ 都是个没有什么结构的离散集合，似乎在某些方面来说就没有 Structured Output learning 里那么多变化了。除了像 Logistic Regression 这种一开始就能处理多类别数据的算法之外，对于普通的 binary classification 算法（例如 SVM），大家一般使用将多类问题转化为一堆二类问题的方法。其中最常用的两种转化方法称为 One-vs-Rest 和 One-vs-One 。

One-vs-Rest 的方法是为每个类训练一个 binary classifier ，这个 classifier 的作用是区分该类和其他所有的类。这样一来，有 K 类就有 K 个 classifier 。分类的时候，会得到 K 个二分类的结果。由于一般的 binary classifier 通常除了得到类别之外，还会得到一个 decision value ，可以表示这个分类的“可信程度”，例如 SVM 可以得到数据点离分类面的距离，距离越大说明分类越准确。于是可以根据这个 decision value 对 K 个二分类器的结果进行排序，decision value 最大的那个分类器对应的类别即是多类分类的结果。

One-vs-Rest 的方法有可能出现的问题是如果类别数目比较多的话，每个二分类器训练的时候正例和负例的数目相差会很大。当然这个问题也是可以通过对负例进行 sampling 来解决的。另外一种 One-vs-One 的方法则是对于所有的不同类别的 pair ，都训练一个二分类器。这样有 $K$ 个类的话，就会需要 $C_K^2$ 个二分类器。分类的时候将所有的二分类结果拿来进行投票，票数最多的那个类别获胜。这种方法不会出现 One-vs-Rest 里面的那种不平衡（除非数据本身就不平衡），不过缺点是需要的分类器的数目很多。

除了这两种最基本的方式之外，下次有机会的话，我还会介绍一下 Error Correcting Output Codes (ECOC) 来将多分类转化为二分类的问题的方法，这里的 One-vs-Rest 和 One-vs-One 都可以作为 ECOC 的特例出现。当然除了转化之外，还有许多研究如果直接扩展现有的算法或者设计全新的算法来处理 multiclass 的情况。Fei-fei Li 在 ECCV 2010 有一篇文章 What does classifying more than 10,000 image categories tell us? ，做了一系列的实验，发现了一些在类别数目达到一定量级的时候问题会变得和小数目的多类分类问题的一些有趣的差异。类似的发现似乎也更激励大家将 multiclass learning 看成一个“严肃”的问题来认真对待，而不是只是简单的转化为一堆二分类问题了事。

不过在 2004 年的 JMLR 上，还有一篇“劲爆”的论文，叫做 In Defense of One-Vs-All Classification ，文章给了 extensive 的实验，比较了各种 fancy 的多类处理算法，得到的结论是：以前的论文里说自己方法好的实验其实都做得有各种各样的问题，本文的实验证明，One-vs-Rest 才是最好的：实现最方便，理解最容易，并且性能上也不明显输于其他任何方法——当然前提是你要用足够好的二分类器，并且足够努力的去调最好的参数（当然调参数不能作弊的，比如不能在 test data 上调）。实验完了之后还做了相当多的算法分析。

嗯嗯，这样劲爆的论文发表出来，是不是意味着关于 multiclass learning 的其他研究都可以洗洗睡了呢？对于这个问题，我现在只能说：“呵呵”了！ :p 感兴趣的同学可以自己去找那篇论文来看哦！ 🙂