前言

机器学习是人工智能的核心领域之一。它关心的是量化模型的研究和开发,使得计算机能够在不对其显式编程的情况下完成某项任务。在这种情形下,学习指的是识别某种复杂的模式和做出智能化的决策。在考虑了所有已有的输入数据后,完成这项任务的困难在于,所有可能决策的集合在一般情况下是非常复杂且难以枚举的。为了绕开这个困难,机器学习的算法在设计时就定下原则:基于问题给出的有限数据来获得待处理问题的知识。

研究概念

为说明这个原则,让我们先看将在本书讨论的监督学习框架。根据这个框架,一个基于输入数据的决策将由一个预测函数的输出来给出,这个预测函数是从一系列有标注数据(或训练数据库)推断出的。这些数据的每个样本是一个数据对,由一个给定向量空间中代表观测值的向量和与该样本对应的响应变量(也称为预期输出或实际输出)组成。在估计或学习阶段之后,算法返回的函数需要能够预测新观测值的响应值。这种情形的潜在假设是,一般情况下,样本对预测问题具有代表性。在实践中,我们用误差函数来度量模型对给定样本的预测和预期输出之间的差值。于是对于给定的训练集,机器学习算法会在预先定义的函数集合里面选择一个对训练集样本而言平均误差最小的函数。一般而言,这个误差对算法在新样本上的表现并没有代表性。因此,应当设置第二个有标注的数据集或者说测试集。我们的算法在估计阶段不能访问这个数据集,而在其上计算所得的平均误差将代表算法的泛化误差。我们期待的是一个能够找出具有良好泛化表现的函数的学习算法,而不是一个只能完美复制训练集样本的响应数据的算法。图 I 展示了这个原理。经验风险最小化法学习能力的理论保证主要是由 Vapnik (1999) 开创的。这些理论保证依赖于训练集的大小,以及我们所要进行搜索的预测函数所在函数类的复杂度。

一直以来,监督学习框架的两个主要任务是分类和回归。这两个任务是类似的,区别在于样本的预期输出空间不同。在分类问题中,输出空间是离散的;而在回归问题中,这个空间则是连续的。

20 世纪 90 年代末,在新技术尤其是和互联网发展相关的新技术的冲击下,新的机器学习框架开始显现。其中一个框架便是对部分标注数据的学习,或称半监督学习。由于需要尝试整合有标注的数据库,获得有标注数据通常又代价昂贵,而无标注数据则数量丰富且包含我们寻求解决的问题的信息,这些都推动了半监督学习的发展。借此,许多同时使用少量有标注数据和大量无标注数据来学习预测函数的工作得以开展。

图像说明文字

自 2000 年以来,另一个在机器学习社区广受关注并引发大量研究的框架则是排序模型。这个框架最开始应用在信息检索问题上,后来扩展到更一般的其他问题。

多年以来,在这些框架下发展出来的机器学习算法已被成功应用于大量多样的问题中,包括语音和手写识别、机器视觉、蛋白质结构预测、推荐系统、文本分类和搜索引擎等。

本书架构

这本书介绍了监督学习理论的科学基础、在这个框架下发展起来的最流行的算法,以及前面提到的另外两种学习框架,难度水平面向的是研究生及工程类学生。我们希望阐述本领域发展起来的各种算法理论。此外,本书并不局限于论述基础理论,还呈现了书中提到的各种经典算法程序,这些程序均使用简单而流行的 C 语言 ①写成,读者可借此理解有时被称为“黑匣子”的模型是怎样运作的。本书由 6 章 2 个附录组成。

• 在第 1 章,我们介绍 Vapnik (1999) 的统计学习理论的基本概念。我们会阐述经验风险最小化原理的一致性概念,通过它,大部分监督学习算法得以发展起来。对一致性的研究引出了机器学习的第二个基本原理,即结构风险最小化原理,它打开了发展机器学习新模型的视野。特别地,我们还会在这一章介绍泛化误差界的概念,并描述其相关假设和获得它的必要工具。

①  http://www.tiobe.com/tiobe-index/

• 在第 2 章,我们介绍来自最优化领域的凸风险函数最小化的基本算法,这里的凸风险函数是经验风险的上界。这些算法被用于寻找大量机器学习模型的参数值。尤其是,我们会介绍验证无约束凸问题的优化算法收敛到最小化子的必要条件,并描述一些简单而有效的传统优化算法。

• 第 3 章介绍经典的二类分类问题的模型,它们是发展更复杂的学习算法的先驱。我们讨论的大部分模型都是早于 Vapnik (1999) 的理论框架发展出来的。特别地,我们会构建每个模型发展出的机器学习问题与由 Vapnik (1999) 提出的经验风险最小化原理之间的联系。此外,我们还会详细地阐述源于结构风险最小化从而使得间隔最大化的分隔器。

• 在第 4 章,我们分析多类分类问题,并阐述不同框架。此外,我们会讨论一些多类分类算法,并对两类非集结模型和基于二类分类算法的混合模型进行区分。

• 在第 5 章,我们介绍半监督学习框架。我们从介绍无监督学习框架中发展出的 EM 和CEM 算法开始,详细讨论一些特殊情况,直至无监督模型中著名的 K-均值算法。然后,我们讨论半监督学习的基本假设,以及在这个框架下发展出的生成、判别、图像三种方法。

• 在第 6 章,我们讨论排序学习函数(learning to rank)。我们着重于两种特殊的排序情况,即备择排序和样例排序。之后阐述一些使用经典排序学习函数的算法,最后展示一些排序问题归结为成对观测值的二类分类问题。这种归结开启了使用互相关的样本来学习分类器的途径,我们会使用 Janson (2004) 的结果来进行分析。

• 在附录 A,我们回顾了本书中使用到的概率论的基本工具。

• 在附录 B,我们详细列出了程序的数据结构,将程序与对应章节联系起来,给出了本书展示的 15 种算法的程序代码。

目录