手写识别重访：核支持向量机

César de Souza

4.91/5 (94投票s)

2010年9月1日

CPOL

14分钟阅读

405894

21629

使用核支持向量机进行手写数字识别的技术

要获取最新版本的代码，其中可能包含最新的增强功能和更正，请下载最新版本的 Accord.NET 框架。

引言

在上一篇文章中，我曾想展示如何使用核判别分析来解决手写识别问题。然而，我觉得我对这个手写识别问题做得不够充分，因为我的主要关注点是 KDA，而不是识别本身。在这篇文章中，我将展示一种可能更好的方法来解决这个问题。

核判别分析有其自身的问题。它在扩展到样本数量时性能会急剧下降，复杂度为 O(n³)，尽管在处理高维数据方面没有问题。另一个严重的问题是，它在模型评估期间需要整个训练集都可用，这使得它在许多场景下不适用（例如在嵌入式系统中）。

在上一篇文章的结尾，我曾提到支持向量机 (SVM) 是执行手写数字识别的更好选择。SVM 的一个优点是其解决方案是稀疏的，因此，与 KDA 不同，它们在评估期间不需要始终可用整个训练集。只需要一个（通常很小的）子集。这个子集通常被称为“支持向量”。

支持向量机

支持向量机 (SVM) 是一组相关的监督学习方法，可用于分类和回归。简单来说，给定一组标记为属于两个类别之一的训练样本，SVM 分类训练算法会尝试构建一个决策模型，该模型能够预测新样本属于哪个类别。如果样本在空间中表示为点，则线性 SVM 模型可以解释为对该空间进行划分，以便属于不同类别的样本由一个尽可能宽的清晰间隔分隔开。然后根据新样本落在间隔的哪一侧来预测其所属类别。

Maximum margin classification by a hyperplane using a linear support vector machine.

支持向量机作为最大间隔分类器。最左边的图显示了蓝色和绿色两类的决策问题。中间的图显示了与每个类别的最近训练数据点距离最大的超平面。最右边的图显示了定义该超平面只需要两个数据点。这两个点将作为支持向量，并用于指导决策过程。

一个线性支持向量机由一组给定的支持向量 z 和一组权重 w 组成。对于具有 N 个支持向量 z₁, z₂, ... , z_N 和权重 w₁, w₂, ... , w_N 的给定 SVM 的输出计算如下：

$F(x) = \sum_{i=1}^N w_i \, \left \langle z_i,x \right \rangle + b$

然后应用决策函数将此输出转换为二元决策。通常使用 sign(.)，以便将大于零的输出视为一个类，小于零的输出视为另一个类。

核支持向量机

如上所述，原始 SVM 最优超平面算法是一个线性分类器。然而，自 1963 年首次提出以来，近 30 年后，一些研究人员（包括原始作者本人）提出了一种方法，通过将核技巧应用于这些最大间隔超平面来创建非线性分类器。其结果是核机器研究的“爆发”，它成为迄今为止最强大和最流行的分类方法之一。

这并非没有原因。核技巧是一个非常强大的工具，能够为那些仅依赖于两个向量之间点积的算法提供从线性和非线性之间的桥梁。它源于这样一个事实：如果我们首先将输入数据映射到高维空间，那么在这个空间中操作的线性算法将在原始输入空间中表现出非线性行为。

这里的“技巧”在于，实际上并不需要计算这个映射：我们只需要用合适的核函数替换所有的点积。核函数表示特征空间中的内积，通常表示为

The kernel trick.

核函数（其中 φ 表示一个可能的非线性映射函数）。

使用核函数，算法就可以进入更高维空间，而无需显式地将输入点映射到该空间。这是非常可取的，因为有时我们更高维的特征空间甚至可能是无限维的，因此无法计算。由于 SVM 的原始表述主要由点积组成，因此应用核技巧非常直接。即使最终的分类器仍然是高维特征空间中的超平面，它在原始输入空间中也可能是非线性的。与具有不同灵感来源（如生物学）的方法相比，使用核技巧还为底层分类器提供了更强的理论支持。

Applying the Kernel trick to the original SVM formulation.

示意图，展示了如何将核技巧应用于原始支持向量机表述。

使用线性核（形式为 K(z,x) = <z,x> = z^Tx），我们可以恢复线性 SVM 的原始表述。关于核技巧的更多细节以及现成可用核函数的示例，您可以查阅上一篇关于核判别分析的文章或 “面向机器学习应用的核函数” 页面。

多类支持向量机

不幸的是，与 KDA 不同，支持向量机无法自然地泛化到多类分类问题。SVM 是二元分类器，因此，在其原始形式下，它们一次只能区分两个类别。然而，已经提出了许多使用 SVM 进行多类分类的方法，其中一种将在下面进行示例。

假设我们需要在三个类别 A、B 和 C 之间做出决定。现在，假设我们只有二元分类器，即只能自动区分两个类别的自动方法。为了在多类分类问题中使用我们的二元分类器，一种可能的方法是尝试将我们的多类问题分解为一系列二元问题。下方的左矩阵显示了通过选取我们的三个类别可以形成的所有可能的二元决策问题组合。

Subdivision of a N-class classification problem into NxN binary problems.

Subdivision of a N-class classification problem into N(N-1)/2 binary problems.

然而，请注意，左矩阵包含一些冗余情况。例如，计算 A 和 A 之间的决策是没有意义的。同时计算 B x A 和 A x B 也是低效的，因为只计算一个并取反就足够了。丢弃冗余选项后，我们得到右侧的矩阵。可以看出，一个典型的 n 类决策问题总是可以分解为 n(n-1)/2 个二元问题的子集。

现在我们只剩下三个二元问题，因此很容易看出，为了实现使用 SVM 的多类分类，我们只需要创建三个 SVM 来运行，每个 SVM 处理一个子问题。

Three binary classification problems represented by three support vector machines.

为了决定一个类别，我们可以使用投票机制，其中获得最多决策的类别被宣布为决策过程的获胜者。例如，假设类别 A 在第一个机器中获胜，而 C 在第二个和第三个机器中都获胜。

Results from the application of support vector machines to the three classification problems.

如果我们取获得最多票数的类别作为获胜者，那么我们的多类机器显然应该决定 C。这种方法通常被描述为多类分类的一对一策略。

Results of the classification as a voting chart.

一对一决策过程的投票结果。

另一种可能的方法是使用一对所有策略，其中输入模式会被呈现给所有 SVM，并选择产生最高输出的 SVM。不幸的是，没有什么可以保证一个机器的较高正输出比另一个机器的较低但仍然为正的输出更好，因此仅仅选择产生最高输出的机器作为决策过程的获胜者可能会导致糟糕的结果。也就是说，除非您使用的是相关向量机，在这种情况下，该策略才会奏效，因为输出实际上是概率。然而，RVM 有其自身的问题，超出了本文的范围。

出于上述原因，在本文的其余部分，我们将只关注一对一的多类分类。

这里提供的 (核) 支持向量机代码也是 Accord.NET 的一部分，这是一个我多年来一直在构建的框架。它建立在 AForge.NET 之上，后者是一个流行的计算机视觉和机器学习框架，汇集了我过去研究中需要的各种主题。目前，它实现了 PCA、KPCA、LDA、KDA、LR、PLS、SVM、HMM、LM-ANN 以及许多其他缩写。该项目托管在 GitHub 上，网址为 https://github.com/accord-net/framework/。

要获取最新版本的此代码，其中可能包含最新的 bug 修复、更正、增强功能和特性，我强烈建议直接从项目站点下载最新版本的 Accord.NET。

机器

源代码中包含的机器类如下所示。

KernelSupportVectorMachine 类扩展了 SupportVectorMachine 并加入了核。MulticlassSupportVectorMachine 使用一组 KernelSupportVectorMachine，通过一对一投票方案执行多类分类。本文提供的代码和框架提供了广泛的机器学习核函数列表供选择。

训练算法

训练算法可以执行分类和回归。它们是 Platt 的序列最小优化 (SMO) 算法的直接实现。MulticlassSupportVectorLearning 提供了一个委托函数 Configure，可用于选择和配置任何学习算法。这种方法不限制使用哪种算法，并且允许用户指定自己的算法来执行训练。

由于 MulticlassSupportVectorLearning 算法通过同时训练一组独立的机器来工作，因此它很容易并行化。事实上，可用实现可以充分利用单台机器上的额外核心。

/// <summary>
///   Runs the one-against-one learning algorithm.
/// </summary>
public double Run(bool computeError)
{
    // For each class i
    AForge.Parallel.For(0, msvm.Classes, delegate(int i)
    {
        // For each class j
        for (int j = 0; j < i; j++)
        {
            // Retrieve the associated machine
            var machine = msvm[i,j];

            // Retrieve the associated classes
            int[] idx = outputs.Find(x => x == i || x == j);
            double[][] subInputs = inputs.Submatrix(idx);
            int[] subOutputs = outputs.Submatrix(idx);
   
            // Transform in a two-class problem
            subOutputs.ApplyInPlace(x => x = (x == i) ? -1 : 1);
            
            // Train the machine on the two-class problem.
            configure(machine, subInputs, subOutputs).Run(false);
        }
    });
}

上述代码使用了 AForge.NET Parallel 构造以及 Accord.NET 矩阵扩展。我决定不使用新添加的 .NET 4.0 Parallel Extensions，以便框架仍能与 .NET 3.5 应用程序兼容。

数字识别

UCI 的 Optdigits 数据集

如果您已经阅读了关于用于手写数字识别的核判别分析的上一篇文章，请跳过本节。这是对 UCI 机器学习存储库中的 Optdigits 数据集的一个介绍。

UCI 机器学习存储库是机器学习社区用于对机器学习算法进行经验分析的数据库、领域理论和数据生成器的集合。可用的数据集之一是光学手写数字识别数据集（又称 Optdigits 数据集）。

在原始 Optdigits 数据中，数字表示为 32x32 的矩阵。它们也以预处理后的形式提供，其中数字被划分为 4x4 的非重叠块，并统计了每个块中的“on”像素数量。这生成了 8x8 的输入矩阵，其中每个元素都是一个 0..16 范围内的整数。

从原始 Optdigits 数据集中提取的数字样本。

通过多类支持向量机对数字进行分类

核方法之所以吸引人，是因为它们可以直接应用于需要大量数据预处理（如降维）和对所建模数据结构有广泛了解的问题。即使我们对数据了解不多，直接应用核方法（进行较少的预处理）通常也能找到有趣的结果。然而，使用核方法实现最优可能是一项非常艰巨的任务，因为我们有无限的核函数可供选择——并且对于每个核，都有无限的参数空间可供调整。

以下代码显示了如何实例化一个多类 (核) 支持向量机。请注意，输入是如何作为 1024 个位置的完整向量给出的。如果我们打算使用神经网络，例如，这将是不切实际的。然而，核方法通常不会遇到处理高维问题的困难，因为它们不受维度灾难的影响。

// Extract inputs and outputs
int samples = 500;
double[][] input = new double[samples][];
int[] output = new int[samples];
for (int i = 0; i < samples; i++)
{
   ...
}

// Create the chosen Kernel with given parameters
IKernel kernel = new Polynomial((int)numDegree.Value, (double)numConstant.Value);

// Create the Multi-class Support Vector Machine using the selected Kernel
ksvm = new MulticlassSupportVectorMachine(1024, kernel, 10);

// Create the learning algorithm using the machine and the training data
var ml = new MulticlassSupportVectorLearning(ksvm, input, output);

// Extract training parameters from the interface
double complexity = (double)numComplexity.Value;
double epsilon = (double)numEpsilon.Value;
double tolerance = (double)numTolerance.Value;

// Configure the learning algorithm
ml.Configure = delegate(KernelSupportVectorMachine svm, 
                        double[][] cinput, int[] coutput)
{
    var smo = new SequentialMinimalOptimization(svm, cinput, coutput);
    smo.Complexity = complexity;
    smo.Epsilon    = epsilon;
    smo.Tolerance  = tolerance;
    return smo;
};

// Train the machines. It should take a while.
double error = ml.Run();

示例应用

学习

与源代码配套的示例应用程序可以执行使用多类核支持向量机进行手写数字识别。要执行此操作，请打开应用程序（最好在 Visual Studio 之外打开，以获得更好的性能），单击 文件菜单，然后选择打开。这将从 Optdigits 数据集中加载一些条目到应用程序中。

要开始学习过程，请单击“开始训练”按钮。使用默认设置，这不应该花费太长时间。由于代码使用了 AForge.NET 的并行扩展，核心数量越多，训练速度就越快。

使用 Accord.NET 框架的并行化学习算法训练多类支持向量机。

训练完成后，单击“分类”以开始对测试集进行分类。使用默认值，它应该可以达到高达 95% 的准确率，正确识别出约 500 个可用实例中的 475 个。测试集的识别率可能会略有波动，具体取决于学习算法的运行。

核支持向量机学习算法的结果。

为了进行比较，使用了与上一篇核判别分析文章相同的训练和测试样本集以及相同数量的样本。由于 SVM 在处理时间和内存需求方面都更有效，因此使用更多数据集样本可能会实现更高的准确率。

训练完成后，可以在“机器”选项卡中看到创建的 SVM。通过选择第一个 DataGridView 中的一个条目，可以看到每个机器的支持向量和偏差（阈值）。向量越暗，它在决策过程中所占的权重越大。

关于支持向量机的详细信息，包括其支持向量。

结果

尽管识别率的提升仅略高于 3%，但与 KDA 相比，识别的准确性已大大提高。通过单击“分类”选项卡，我们可以手动测试多类支持向量机对用户绘制的数字。

我们可以看到 SVM 方法产生了更加稳健的结果，即使是绘制不佳的数字也能被准确识别。

手写数字识别。

最后，这里有一个手写识别示例应用程序的视频演示 [^]，包含在最新版本的 Accord.NET 框架中。

结论

在本文中，我们详细探讨了如何将 (核) 支持向量机应用于手写数字识别问题并取得了令人满意的结果。所提出的方法没有 KDA 的限制，并且识别率也得到了提高。与 KDA 不同，SVM 的解决方案是稀疏的，这意味着在模型评估期间只需要训练集的一个（通常很小的）子集。这也意味着评估阶段的复杂性将大大降低，因为它仅取决于训练期间保留的向量数量。

然而，支持向量机的一个缺点是存在多种执行多类分类的方法，因为它们无法直接应用于此类问题。尽管如此，我们在本文中讨论并举例说明了如何采用一对一策略来产生准确的结果，即使您的数据集不平衡。

与 KDA 一样，核方法带来的另一个问题是核函数的正确选择（及其参数的调整）。这个问题通常可以通过网格搜索和交叉验证来解决，而这些操作本身在处理能力和可用训练数据方面都非常昂贵。尽管如此，这些方法可以轻松地并行化，并且 Accord.NET 框架中也提供了网格搜索的并行实现。

另请参阅

参考文献

Wikipedia 贡献者，“序列最小优化”，维基百科，自由的百科全书，http://en.wikipedia.org/wiki/Sequential_Minimal_Optimization (访问于 2010 年 4 月 24 日)。
Wikipedia 贡献者，“支持向量机”，维基百科，自由的百科全书，http://en.wikipedia.org/wiki/Support_vector_machine (访问于 2010 年 4 月 24 日)。
John C. Platt，序列最小优化：训练支持向量机的快速算法，Microsoft Research，1998。
J. P. Lewis，SVM（支持向量机）简明教程。CGIT Lab / IMSC，南加州大学。
A. J. Smola 和 B. Scholkopf，支持向量回归教程。NeuroCOLT2 技术报告系列，1998。
S. K. Shevade 等人。SMO 算法用于 SVM 回归的改进，1999。
G. W. Flake，S. Lawrence，使用 SMO 进行高效 SVM 回归训练。
A. Asuncion & D.J. Newman，UCI 机器学习存储库。Irvine，CA：加州大学信息与计算机科学学院 (2007)。
Andrew Kirillov，AForge.NET 框架。AForge.NET 计算机视觉、人工智能和机器人网站，2010。
C. R. Souza，面向机器学习应用的核函数。2010 年 3 月 17 日。网络。

历史

2010 年 9 月 1 日：初始版本

手写识别重访：核支持向量机

目录