南大报告：Large-scale classification: Status and challenges

报告人：Chih-Jen Lin教授

12月25日，南京大学计算机系李武军老师邀请台湾大学的Chih-Jen Lin教授来南京大学计算机系做报告，报告题目是“Large-scale classification: Status and challenges”。林智仁(Lin Chih-Jen)教授等开发设计的一个简单、易于使用和快速有效的SVM模式识别与回归的软件包LIBSVM，他不但提供了编译好的可在Windows系列系统的执行文件，还提供了源代码，方便改进、修改以及在其它操作系统上应用；该软件对SVM所涉及的参数调节相对比较少，提供了很多的默认参数，利用这些默认参数可以解决很多问题；并提供了交叉验证(Cross Validation)的功能。

报告的Outline如下，Big-datalinear classification部分由于时间关系林智仁教授没有进行展开。

首先，林智仁教授简单介绍了一下机器学习，以及比较传统的机器学习任务：分类与聚类的差别。我理解就是，分类是我们针对事先定义好类别（label）的一批数据，建立分类器（model）把不同标签的数据分开。聚类是本身没有类别定义的数据，我们把他们聚集成为不同的组。

数据分类就是给了不同类别的训练数据（打好标签的），然后来预测测试数据（未知标签的）。

本次汇报主要关注的是分类（Classification）。分类里面又分为线性分类和非线性分类。例子如图所示，比如线性分类的数据是（身高，体重），现在非线性分类的的数据是（身高，体重，体重/身高²），Kernel是非线性分类算法中的一种，将原始数据的特征值映射到另一个维度中，具体的信息可以参见维基百科的介绍：http://en.wikipedia.org/wiki/Kernel_method。Kernel有很多种，Fisherkernel，Graph kernels，Polynomial kernel，RBF kernel，String kernels等等。

和许多其他的算法相比，线性分类器由于其简便性而一直被人们利用。对于二分类问题，他的decision函数就是sgn(w^T,x)，sgn表示符号函数。举个例子，也就是说二分类最后得出来的数值不是+1就是-1。

对于SVM和logistic回归我们一般使用的两种方法就是Kernel方法（虽然计算简便，但是无法控制fearure），或者是Linear classification加上feature engineering（feature是人们选出来的，不需要再映射到其他维度中）。这次的报告主要关注的是后一种方法。

那我们为什么要选择线性分类呢？当训练集的数据维度很高的时候，Kernel函数并不适用，因为函数计算的成本很高。

线性分类对于文本分类（大又稀疏的数据集）有一定优势。

针对二分类问题的线性分类：l个数据样本，n个特征值。

一些被人们使用的损失函数：（损失函数最简单的理解就是，给定一个实例，训练的模型对它的预测结果错了，就要受到惩罚，因此需要定义一个量度量预测错误的程度，而损失函数就是用来衡量错误的程度。）

不同的损失函数效果类似。

优化的方法：Kernel和linear的不同，对于Kernel我们不能求出最小值，因为W可能有无限个，我们没有选定有限个特征。而Linear相反。

求最值的方法就是求导，我们可以只求一次导数或者两次导数，也可以求多次导数。High-order得到的模型更加具有鲁棒性（robust）

这里林智仁教授简单讲了利用求二次导数来优化得到最终函数的方法，Hessian Free方法。它可以不用预训练网络的权值，效果也还不错，且其适用范围更广。HF的主要思想类似于牛顿迭代法，只是并没有显示的去计算误差曲面函数某点的Hessian矩阵，而是通过某种技巧（Hessian的特殊表达方式）直接算出矩阵和任意向量的乘积，因此叫做”Hessian Free”。

X是data matrix，D是一个对角矩阵。

然后是coordinate descent。坐标下降优化方法是一种非梯度优化算法。为了找到一个函数的局部极小值，在每次迭代中可以在当前点处沿一个坐标方向进行一维搜索。在整个过程中循环使用不同的坐标方向。一个周期的一维搜索迭代过程相当于一个梯度迭代。

然后针对这几种方法，做了比较试验。针对news20，rcv1，yahoo-Japan，yahoo-korea这几个数据集，从图中可以看出，DCDL2和DCDL2-S不仅速度快而且效果也很好。

但是高阶方法用于少特征多样本数的情况时效果会更好。

然后教授介绍了两个例子。

一个是在自然语言处理的案例中，Kernel和Linear方法的比较，线性的方法训练以及测试速度都远远高于Kernel，而且准确率也还不错。

如果做映射feature=O(n²)，而linear的话是O(nl)，由于数据稀疏，很多都是0，因此很多相乘后的x_n-1x_n，也是0。

然后是一个需要做一个在一个小容量的装置上做分类器的案例。特征值只有五个，只能使用16KB的RAM。因此考虑了3层的多项式映射，采用一对一的决策来判别分类。

最后是他们研究的一些概况。这些在网站上都能看到，这个是他的个人主页http://www.csie.ntu.edu.tw/~cjlin/。

线性分类这个话题虽然很老，但是还是有新的研究内容产生，并且可以应用于很多情况。

对于刚刚接触机器学习的我，见到大牛甚是兴奋，还一起留影了。机器学习好好学！嗯！