最优间隔分类器训练算法

问题与背景

《最优间隔分类器训练算法》由 Bernhard E. Boser、Isabelle M. Guyon 和 Vladimir N. Vapnik 撰写。ACM 数字图书馆把它记录为 1992 年 7 月 1 日发表。^[1] 该文收录于 COLT 1992 会议录第 144 至 152 页；COLT 1992 是第五届计算学习理论年度研讨会。^[1] 论文讨论分类器的训练：面对训练样本和决策边界（decision boundary），训练算法应如何确定边界。摘要给出的核心目标是最大化训练样本与决策边界之间的间隔（margin）。^[1] 在间隔视角下，分类器不只关心是否把训练样本分开，也关心边界周围留出多大空间；这篇论文把间隔最大化直接放进训练算法。^[1]

训练方法

摘要说，这种技术适用于多种分类函数，包括感知机（Perceptrons）、多项式（polynomials）和径向基函数（Radial Basis Functions）。^[1] 这说明算法不是只针对单一函数族提出的。摘要还指出，有效参数数量（effective number of parameters）会自动调整，以匹配问题的复杂度。^[1] 也就是说，训练过程被描述为根据问题复杂度调节解的有效容量，而不是要求使用者直接设定这个数量。解的形式也被明确写出：它表示为支持模式（supporting patterns）的线性组合，而支持模式是训练样本中距离决策边界最近的子集。^[1] 因此，最终解围绕这些最靠近边界的样本组织起来，而不是用一段与样本无关的固定公式来描述。

摘要还给出基于留一法（leave-one-out method）和 VC 维（VC-dimension）的泛化性能界。^[1] 留一法和 VC 维都是讨论泛化性能的工具：前者通过逐一留出训练样本来考察稳定性，后者刻画函数类的容量。论文把训练规则与这类泛化界放在一起讨论。^[1]

实验与结果

摘要报告了在光学字符识别（optical character recognition）问题上的实验。在这些实验中，该方法与其他学习算法相比表现出良好的泛化能力。^[1] 这里强调的是泛化表现，而不只是训练集上的表现。结合前面的泛化界，论文从两个角度讨论泛化：一是基于留一法和 VC 维的理论界，二是在字符识别数据上的实验比较。^[1]

为什么重要

论文的几项表述可以连成一个整体：最大化间隔说明训练算法追求什么；用支持模式的线性组合表示解，说明学到的分类器依赖哪些训练样本；有效参数数量自动匹配问题复杂度，说明复杂度如何被处理；基于留一法和 VC 维的界，说明泛化性能如何被分析。^[1] 同时，摘要说该方法适用于感知机、多项式和径向基函数等多种分类函数，使讨论不局限于单一模型族。^[1] 因此，这篇论文呈现的不只是一个训练算法，也是一套把训练目标、解的形式和泛化分析联系起来的框架。

文献记录

ACM 数字图书馆的记录把这篇论文列为 1992 年 7 月 1 日发表，并把它放在 COLT 1992 会议录第 144 至 152 页；该会议是第五届计算学习理论年度研讨会。^[1] 论文标题明确称其为一种最优间隔分类器的训练算法。^[1]