← 全部论文 / 1995

Support-vector networks

1995 2012 年前 CPU 与统计基础 被引用 40k 次
下载 PDF

Support-Vector Networks - 中文验证版

英文原始依据卡片：support_vector_networks_1995.md

状态：已翻译。

元数据

  • Slug： support_vector_networks_1995
  • 年份： 1995
  • 期刊： Machine Learning
  • 作者： Corinna Cortes, Vladimir Vapnik
  • 阅读状态： read complete
  • 计算范式： 2012 年前 CPU 与统计基础
  • 主要来源： PDF、抽取文本

计算设置

论文未列出具体机器、CPU 型号、内存大小或运行环境。按项目规则，设备上下文从 1994-1995 年研究时期推断：CPU 工作站或服务器，在数千到数万样本上求解二次规划。实验数据为 OCR 规模而非 web 规模：7,300 个 USPS 训练样本和 2,000 个测试样本，分辨率 16x16；以及更大的 NIST mixture，包含 60,000 个训练样本和 10,000 个测试样本，分辨率 28x28。

计算结构是核技巧加上支持向量稀疏性。论文明确将技术问题界定为如何处理高维空间：在 200 维输入上的 4 次或 5 次多项式可能需要十亿维特征空间中的超平面。支持向量网络通过首先通过点积或距离比较输入向量、然后对该标量施加非线性函数，避免了显式特征物化。论文强调，构造复杂度不取决于特征空间的维度，而取决于支持向量的数量。这正是适合 CPU 时代内存限制的方法类型。

瓶颈

瓶颈是在有限内存、有限 CPU 优化时间和有限可靠的神经网络训练配方下进行非线性分类。显式多项式特征在高次下不可行：论文指出特征空间维度可能变得极大，而并非每个分离超平面都能良好泛化。该时期的神经网络可以实现分段线性决策函数，但引言强调早期感知器缺乏通过调整所有权重来最小化训练误差的算法，而后来的神经学习系统需要为 OCR 手工设计架构。

SVM 将问题转化为对偶变量中的间隔控制凸优化问题。昂贵的对象不是显式的十亿维权向量，而是训练样本相似度矩阵和活跃的支持向量集合。这使得 CPU 时代的瓶颈成为二次规划和支持向量数量的问题，而非密集张量吞吐。

方法适配

支持向量网络通过几个相互强化的方式适配 CPU 时代约束。首先，决策函数在支持向量上展开，因此分类将未知样本与训练向量的子集进行比较，而非存储显式的特征空间超平面。其次，多项式决策面使用如 (u · v + 1)^d 的核函数，在不构造坐标的情况下给出高次非线性边界。第三，最大间隔选择通过选取具有最大分离度的超平面来控制泛化；论文的界将期望测试误差与期望支持向量数除以训练集大小相关联，不显式包含特征空间维度。

软间隔将方法适配到真实的不可分数据。论文通过凸或对偶二次规划形式扩展了可分的最大间隔结果，允许训练误差同时最大化间隔。它还描述了增量构造：在一部分数据上求解，保留支持向量和违反样本，加入更多数据，重复。这是面向更大训练集的优化计算-内存策略。最后，OCR 设置使用十个一对多分离器，每个数字一个，因此多类识别被分解为重复的二分类问题，匹配算法的两分组形式。

证据

USPS 实验展示了为什么计算结构重要。输入维度为 256，多项式次数从 1 到 7。表 2 报告了每个分类器的平均支持向量数和特征空间维度。正文指出，7 次多项式特征空间比 3 次特征空间大 10^10 倍，但性能几乎不随维度增加而改变，表明在该设置下未出现过拟合。它还指出，多项式分类器训练时间不依赖于多项式次数，只依赖于支持向量数量。二次及以上多项式优于对比中引用的专门构造的 LeNet1（原始错误率 5.1%）。

NIST 基准提供了更大规模数据的结果。论文使用 4 次多项式，无预处理，在 60,000 个训练样本和 10,000 个测试样本上评估。它指出，在显式视角下 4 次多项式有超过 10^8 个自由参数，但分类器仍然通过支持向量和核来处理。十个分类器在测试集上的组合性能为 1.1% 错误率。基准比较包括线性分类器、k=3 近邻（60,000 个原型）、LeNet1、LeNet4 和支持向量网络；论文引用基准作者的话，称支持向量网络虽未包含其他高性能分类器所使用的专门先验知识，却具有出色的准确率。

历史影响

SVM 在前深度学习时期占据主导地位，因为它们匹配了当时的计算结构：CPU 优化、人工整理的数据集、手工设计或轻度预处理的输入，以及隐式高维表示。它们将注意力从设计神经架构转向选择核和间隔权衡。在这部历史中，SVM 是后来 GPU 训练深度网络必须取代的统计学习基线：来自凸优化和核的强大准确率，但没有由密集加速器吞吐驱动的学习层级结构。

局限

论文的优势也定义了其局限。训练仍需要在训练样本上求解优化问题；随着数据规模增长，核矩阵和支持向量搜索可能变得昂贵。方法依赖核和预处理选择，而非端到端学习层级特征。多类识别被分解为十个二分类分离器，而非单一共享表示。最后，论文没有 GPU 式密集张量计算路径：该方法在 CPU 时代数据集上对隐式多项式空间是高效的，但并非为利用后来的加速器硬件而设计——后者以密集矩阵乘法和学习特征为主导。

链接