高效机器学习方法：SVM解决搜索算法选择问题

在构建BestSF时，使用支持向量机作为训练算法。与其他机器学习方法相比，如Kotthoff等人所说，SVM被大家广泛认为是解决搜索算法选择问题的一种高效机器学习方法。并且，当不同类之间的决策边界是高度非线性时，SVM能够取得更高的准确率，稀疏格式选择就是此类情况。SVM通常被认为是一个二值分类器，目前有如下两种方法可以将其扩展以进行多类分类。

（1）一对多方法：这种方法在学习阶段构建了p个SVM模型，其中p是分类数。第n个模型使用第n个类中所有的正面标签样例和负面标签样例进行训练。为了找到新样例的预测类，该方法需要对先前模型的决策函数进行评估，决策函数值最高的类别即为该新样例的预测类。

（2）一对一方法：在学习阶段，该方法通过构建p（p−1）/2个分类器实现成对分类，其中每个分类器使用两个类中的数据训练。给定一个新样例，先前训练的模型的预测结果中出现最频繁的类即为该样例的预测类。Hsu等人表明，一对一方法比一对多方法更适合真实样例，且在之前的工作中也使用了该方法。

之前基于标准SVMs的方法的主要缺点，是在训练阶段每个训练点被赋予了相同的重要性，而不允许考虑训练点的相对重要性。为了解决该问题，下面使用二值WSVM构建了p×（p−1）/2个WSVM成对模型（p是稀疏格式的数量）。(www.xing528.com)

为了训练模型（fi，fj），根据相应的每对稀疏格式的性能差异，给每个训练点（s）赋予了一个权重ws，如式（7−1）所示。其中P（As，fi）和P（As，fj）表示稀疏矩阵As分别在稀疏格式fi、fj编码下其SpMV内核的性能。ws（fi，fj）线性依赖于两种稀疏格式fi和fj之间的性能提升。给定一个新样例（本章中即稀疏矩阵），使用了与标准“一对一”方法中类似的投票策略：如果模型（fi，fj）选择了fi，则fi的分数加一；否则，fj的分数加一。对所有的p×（p−1）/2个成对模型重复该过程。那么新样例就倾向于分数最高的类。

本章使用了开源LibSVM库中的WSVM的实现，且使用标准C−SVM算法，采用高斯径向基函数内核。使用Hsu等人提出的交叉验证技术来选择两个参数C和gamma。式（7−1）中的参数α设置为100.0（因为本章在该值下得到了最佳结果）。一个非常重要的步骤是在训练/测试之前缩放数据点。LibSVM带有默认的线性缩放方案，该方案将每个属性线性缩放为范围［−1，1］或［0，1］。但是，本次实验中使用对数转换（Log10（x））代替线性缩放可同时提高分类的准确性和BestSF的性能。