统计学习方法即机器学习方法,是计算机及其应用领域的一门重要学科。 本书分为监督学 习和无监督学习两篇,全面系统地介绍了统计学习的主要方法。 包括感知机、k 近邻法、朴素贝 叶斯法、决策树、逻辑斯谛回归与*熵模型、 支持向量机、提升方法、EM 算法、隐马尔可夫 模型和条件随机场,以及聚类方法、 奇异值分解、主成分分析、潜在语义分析、概率潜在语义分 析、马尔可夫链蒙特卡罗法、 潜在狄利克雷分配和 PageRank 算法等。除有关统计学习、监督学 习和无监督学习的概 论和总结的四章外,每章介绍一种方法。叙述力求从具体问题或实例入手, 由浅入深, 阐明思路,给出必要的数学推导,便于读者掌握统计学习方法的实质,学会运用。 为满足读者进一步学习的需要,书中还介绍了一些相关研究,给出了少量习题, 列出了主要参 考文献。 本书是统计机器学习及相关课程的教学参考书, 适用于高等院校文本数据挖掘、信 息检索及自然语言处理等专业的大学生、 研究生,也可供从事计算机应用相关专业的研发人员 参考。

第
1篇
监
督
学
习

第 1章统计学习及监督学习概论
本书第 1篇讲述监督学习方法。监督学习是从标注数据中学习模型的机器学习问题,是统计学习或机器学习的重要组成部分。
本章简要叙述统计学习及监督学习的一些基本概念。使读者对统计学习及监督学习有初步了解。
本章 1.1节叙述统计学习或机器学习的定义、研究对象与方法; 1.2节叙述统计学习的分类,基本分类是监督学习、无监督学习、强化学习; 1.3节叙述统计学习方法的三要素:模型、策略和算法; 1.4节至 1.7节相继介绍监督学习的几个重要概念,包括模型评估与模型选择、正则化与交叉验证、学习的泛化能力、生成模型与判别模型;*后 1.8节介绍监督学习的应用:分类问题,标注问题与回归问题。
1.1统计学习
1.统计学习的特点
统计学习( statistical learning)是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科。统计学习也称为统计机器学习 (statistical machine learning)。
统计学习的主要特点是:(1)统计学习以计算机及网络为平台,是建立在计算机及网络上的;(2)统计学习以数据为研究对象,是数据驱动的学科;(3)统计学习的目的是对数据进行预测与分析;(4)统计学习以方法为**,统计学习方法构建模型并应用模型进行预测与分析;(5)统计学习是概率论、统计学、信息论、计算理论、*优化理论及计算机科学等多个领域的交叉学科,并且在发展中逐步形成独自的理论体系与方法论。
赫尔伯特·西蒙( Herbert A. Simon)曾对“学习”给出以下定义:“如果一个系统能够通过执行某个过程改进它的性能,这就是学习。 ”按照这一观点,统计学习就是计算机系统通过运用数据及统计方法提高系统性能的机器学习。现在,当人们提及机器学习时,往往是指统计机器学习。所以可以认为本书介绍的是机器学习方法。

2.统计学习的对象
统计学习研究的对象是数据( data)。它从数据出发,提取数据的特征,抽象出数据的模型,发现数据中的知识,又回到对数据的分析与预测中去。作为统计学习的对象,数据是多样的,包括存在于计算机及网络上的各种数字、文字、图像、视频、音频数据以及它们的组合。
统计学习关于数据的基本假设是同类数据具有一定的统计规律性,这是统计学习的前提。这里的同类数据是指具有某种共同性质的数据,例如英文文章、互联网网页、数据库中的数据等。由于它们具有统计规律性,所以可以用概率统计方法处理��们。比如,可以用随机变量描述数据中的特征,用概率分布描述数据的统计规律。在统计学习中,以变量或变量组表示数据。数据分为由连续变量和离散变量表示的类型。本书以讨论离散变量的方法为主。另外,本书只涉及利用数据构建模型及利用模型对数据进行分析与预测,对数据的观测和收集等问题不作讨论。

3.统计学习的目的
统计学习用于对数据的预测与分析,特别是对未知新数据的预测与分析。对数据的预测可以使计算机更加智能化,或者说使计算机的某些性能得到提高;对数据的分析可以让人们获取新的知识,给人们带来新的发现。
对数据的预测与分析是通过构建概率统计模型实现的。统计学习总的目标就是考虑学习什么样的模型和如何学习模型,以使模型能对数据进行准确的预测与分析,同时也要考虑尽可能地提高学习效率。

4.统计学习的方法
统计学习的方法是基于数据构建概率统计模型从而对数据进行预测与分析。统计学习由监督学习( supervised learning)、无监督学习( unsupervised learning)和强化学习( reinforcement learning)等组成。
本书第 1篇讲述监督学习,第 2篇讲述无监督学习。可以说监督学习、无监督学习方法是*主要的统计学习方法。
统计学习方法可以概括如下:从给定的、有限的、用于学习的训练数据( training data)集合出发,假设数据是独立同分布产生的;并且假设要学习的模型属于某个函数的集合,称为假设空间( hypothesis space);应用某个评价准则( evaluation criterion),从假设空间中选取一个*优模型,使它对已知的训练数据及未知的测试数据( test data)在给定的评价准则下有*优的预测;*优模型的选取由算法实现。这样,统计学习方法包括模型的假设空间、模型选择的准则以及模型学习的算法。称其为统计学习方法的三要素,简称为模型( model)、策略( strategy)和算法( algorithm)。
实现统计学习方法的步骤如下:
(1)得到一个有限的训练数据集合;
1.2统计学习的分类 5
(2)确定包含所有可能的模型的假设空间,即学习模型的集合;

(3)确定模型选择的准则,即学习的策略;

(4)实现求解*优模型的算法,即学习的算法;

(5)通过学习方法选择*优模型;

(6)利用学习的*优模型对新数据进行预测或分析。


本书第 1篇介绍监督学习方法,主要包括用于分类、标注与回归问题的方法。这些方法在自然语言处理、信息检索、文本数据挖掘等领域中有着极其广泛的应用。

5.统计学习的研究
统计学习研究一般包括统计学习方法、统计学习理论及统计学习应用三个方面。统计学习方法的研究旨在开发新的学习方法;统计学习理论的研究在于探求统计学习方法的有效性与效率,以及统计学习的基本理论问题;统计学习应用的研究主要考虑将统计学习方法应用到实际问题中去,解决实际问题。

6.统计学习的重要性
近二十年来,统计学习无论是在理论还是在应用方面都得到了巨大的发展,有许多重大突破,统计学习已被成功地应用到人工智能、模式识别、数据挖掘、自然语言处理、语音处理、计算视觉、信息检索、生物信息等许多计算机应用领域中,并且成为这些领域的核心技术。人们确信,统计学习将会在今后的科学发展和技术应用中发挥越来越大的作用。
统计学习学科在科学技术中的重要性主要体现在以下几个方面:
(1)统计学习是处理海量数据的有效方法。我们处于一个信息爆炸的时代,海量数据的处理与利用是人们必然的需求。现实中的数据不但规模大,而且常常具有不确定性,统计学习往往是处理这类数据*强有力的工具。

(2)统计学习是计算机智能化的有效手段。智能化是计算机发展的必然趋势,也是计算机技术研究与开发的主要目标。近几十年来,人工智能等领域的研究证明,利用统计学习模仿人类智能的方法,虽有一定的局限性,还是实现这一目标的*有效手段。

(3)统计学习是计算机科学发展的一个重要组成部分。可以认为计算机科学由三维组成:系统、计算、信息。统计学习主要属于信息这一维,并在其中起着核心作用。




1.2统计学习的分类
统计学习或机器学习是一个范围宽阔、内容繁多、应用广泛的领域,并不存在(至少现在不存在)一个统一的理论体系涵盖所有内容。下面从几个角度对统计学习方法进行分类。
1.2.1基本分类
统计学习或机器学习一般包括监督学习、无监督学习、强化学习。有时还包括半监督学习、主动学习。
1.监督学习
监督学习( supervised learning)是指从标注数据中学习预测模型的机器学习问题。标注数据表示输入输出的对应关系,预测模型对给定的输入产生相应的输出。监督学习的本质是学习输入到输出的映射的统计规律。
(1)输入空间、特征空间和输出空间在监督学习中,将输入与输出所有可能取值的集合分别称为输入空间( input space)与输出空间( output space)。输入与输出空间可以是有限元素的集合,也可以是整个欧氏空间。输入空间与输出空间可以是同一个空间,也可以是不同的空间;但通常输出空间远远小于输入空间。每个具体的输入是一个实例( instance),通常由特征向量( feature vector)表示。这时,所有特征向量存在的空间称为特征空间( feature space)。特征空间的每一维对应于一个特征。有时假设输入空间与特征空间为相同的空间,对它们不予区分;有时假设输入空间与特征空间为不同的空间,将实例从输入空间映射到特征空间。模型实际上都是定义在特征空间上的。在监督学习中,将输入与输出看作是定义在输入(特征)空间与输出空间上的随机变量的取值。输入输出变量用大写字母表示,习惯上输入变量写作 X,输出变量写作 Y。输入输出变量的取值用小写字母表示,输入变量的取值写作 x,输出变量的取
值写作 y。变量可以是标量或向量,都用相同类型字母表示。除特别声明外,本书中向量均为列向量。输入实例 x的特征向量记作
x =(x(1),x(2), ··· ,x(i), ··· ,x(n))T
x(i)表示 x的第 i个特征。注意 x(i)与 xi不同,本书通常用 xi表示多个输入变量中的第 i个变量,即
(1) (2) (n))T
xi =(xi ,xi , ··· ,xi
监督学习从训练数据( training data)集合中学习模型,对测试数据( test data)进行预测。训练数据由输入(或特征向量)与输出对组成,训练集通常表示为
T = {(x1,y1), (x2,y2), ··· , (xN ,yN )}
测试数据也由输入与输出对组成。输入与输出对又称为样本( sample)或样本点。

1.2统计学习的分类 7
输入变量 X和输出变量 Y有不同的类型,可以是连续的,也可以是离散的。人们根据输入输出变量的不同类型,对预测任务给予不同的名称:输入变量与输出变量均为连续变量的预测问题称为回归问题;输出变量为有限个离散变量的预测问题称为分类问题;输入变量与输出变量均为变量序列的预测问题称为标注问题。
(2)联合概率分布监督学习假设输入与输出的随机变量 X和 Y遵循联合概率分布 P (X, Y )。 P (X, Y )表示分布函数,或分布密度函数。注意在学习过程中,假定这一联合概率分布存在,但对学习系统来说,联合概率分布的具体定义是未知的。训练数据与测试数

据被看作是依联合概率分布 P (X, Y )独立同分布产生的。统计学习假设数据存在一定的统计规律,X和 Y具有联合概率分布就是监督学习关于数据的基本假设。

(3)假设空间监督学习的目的在于学习一个由输入到输出的映射,这一映射由模型来表示。换句话说,学习的目的就在于找到*好的这样的模型。模型属于由输入空间到输出空间的映射的集合,这个集合就是假设空间( hypothesis space)。假设空间的确定意味着学习的范围的确定。

监督学习的模型可以是概率模型或非概率模型,由条件概率分布 P (Y |X)或决策函数( decision function)Y = f(X)表示,随具体学习方法而定。对具体的输入进行相应的输出预测时,写作 P (y|x)或 y = f(x)。

(4)问题的形式化监督学习利用训练数据集学习一个模型,再用模型对测试样本集进行预测。由于在这个过程中需要标注的训练数据集,而标注的训练数据集往往是人工给出的,所以


称为监督学习。监督学习分为学习和预测两个过程,由学习系统与预测系统完成,可用图 1.1来描述。
图 1.1监督学习
首先给定一个训练数据集
T = {(x1,y1), (x2,y2), ··· , (xN ,yN )}
其中 (xi,yi),i =1, 2, ··· ,N,称为样本或样本点。 xi ∈X ? Rn是输入的观测值,也称为输入或实例,yi ∈Y是输出的观测值,也称为输出。
监督学习分为学习和预测两个过程,由学习系统与预测系统完成。在学习过程中,学习系统利用给定的训练数据集,通过学习(或训练)得到一个模型,表示为条件概率分布 P?(Y |X)或决策函数 Y = f?(X)。条件概率分布 P?(Y |X)或决策函数 Y = f?(X)描述输入与输出随机变量之间的映射关系。在预测过程中,预测系统对于给定的测试样本集中的输入 xN 1,由模型 yN 1 = arg max P?(y|xN 1)或 yN 1 = f?(xN 1)给出
y
相应的输出 yN 1。
在监督学习中,假设训练数据与测试数据是依联合概率分布 P (X, Y )独立同分布产生的。
学习系统(也就是学习算法)试图通过训练数据集中的样本 (xi,yi)带来的信息学习模型。具体地说,对输入 xi,一个具体的模型 y = f(x)可以产生一个输出 f(xi),而训练数据集中对应的输出是 yi。如果这个模型有很好的预测能力,训练样本输出 yi和模型输出 f(xi)之间的差就应该足够小。学习系统通过不断地尝试,选取*好的模型,以便对训练数据集有足够好的预测,同时对未知的测试数据集的预测也有尽可能好的推广。
2.无监督学习
无监督学习①(unsupervised learning)是指从无标注数据中学习预测模型的机器学习问题。无标注数据是自然得到的数据,预测模型表示数据的类别、转换或概率。无监督学习的本质是学习数据中的统计规律或潜在结构。
模型的输入与输出的所有可能取值的集合分别称为输入空间与输出空间。输入空间与输出空间可以是有限元素集合,也可以是欧氏空间。每个输入是一个实例,由特征向量表示。每一个输出是对输入的分析结果,由输入的类别、转换或概率表示。模型可以实现对数据的聚类、降维或概率估计。
假设 X是输入空间,Z是隐式结构空间。要学习的模型可以表示为函数 z = g(x),条件概率分布 P (z|x),或者条件概率分布 P (x|z)的形式,其中 x ∈X是输入, z ∈Z是输出。包含所有可能的模型的集合称为假设空间。无监督学习旨在从假设空间中选出在给定评价标准下的*优模型。
无监督学习通常使用大量的无标注数据学习或训练,每一个样本是一个实例。训练数据表示为 U = {x1,x2, ··· ,xN },其中 xi,i =1, 2, ··· ,N,是样本。
无监督学习可以用于对已有数据的分析,也可以用于对未来数据的预测。分析时使用学习得到的模型,即函数 z = g?(x),条件概率分布 P?(z|x),或者条件概率分布 P?(x|z)。预测时,和监督学习有类似的流程。由学习系统与预测系统完成,如
①也译作非监督学习。

1.2统计学习的分类 9
图 1.2所示。在学习过程中,学习系统从训练数据集学习,得到一个*优模型,表示为函数 z =?g(x),条件概率分布 P?(z|x)或者条件概率分布 P?(x|z)。在预测过程中,预测系统对于给定的输入 xN 1,由模型 zN 1 = g?(xN 1)或 zN 1 = arg max P?(z|xN 1)
z
给出相应的输出 zN 1,进行聚类或降维,或者由模型 P?(x|z)给出输入的概率 P?(xN 1|zN 1),进行概率估计。
图 1.2无监督学习


3.强化学习
强化学习( reinforcement learning)是指智能系统在与环境的连续互动中学习*优行为策略的机器学习问题。假设智能系统与环境的互动基于马尔可夫决策过程( Markov decision process),智能系统能观测到的是与环境互动得到的数据序列。强化学习的本质是学习*优的序贯决策。
智能系统与环境的互动如图 1.3所示。在每一步 t,智能系统从环境中观测到一个状态( state)st与一个奖励( reward)rt,采取一个动作( action)at。环境根据智能系统选择的动作,决定下一步 t 1的状态 st 1与奖励 rt 1。要学习的策略表示为给定的状态下采取的动作。智能系统的目标不是短期奖励的*大化,而是长期累积奖励的*大化。强化学习过程中,系统不断地试错( trial and error),以达到学习*优策略的目的。
图 1.3智能系统与环境的互动
强化学习的马尔可夫决策过程是状态、奖励、动作序列上的随机过程,由五元组 (S, A, P, r, γ)组成。
? S是有限状态( state)的集合

? A是有限动作( action)的集合

? P是状态转移概率( transition probability)函数 :

P (s'|s, a)= P (st 1 = s'|st = s, at = a)

? r是奖励函数( reward function): r(s, a)= E(rt 1|st = s, at = a)


? γ是衰减系数( discount factor): γ ∈ [0, 1]马尔可夫决策过程具有马尔可夫性,下一个状态只依赖于前一个状态与动作,由状态转移概率函数 P (s'|s, a)表示。下一个奖励依赖于前一个状态与动作,由奖励函数 r(s, a)表示。策略 π定义为给定状态下动作的函数 a = f(s)或者条件概率分布 P (a|s)。给定一个策略 π,智能系统与环境互动的行为就已确定(或者是确定性的或者是随机性的)。
价值函数( value function)或状态价值函数( state value function)定义为策略 π从某一个状态 s开始的长期累积奖励的数学期望:
vπ(s)= Eπ[rt 1 γrt 2 γ2 rt 3 ···|st = s] (1.1)
动作价值函数( action value function)定义为策略 π的从某一个状态 s和动作 a开始的长期累积奖励的数学期望:
qπ(s, a)= Eπ[rt 1 γrt 2 γ2 rt 3 ···|st = s, at = a] (1.2)
强化学习的目标就是在所有可能的策略中选出价值函数*大的策略 π?,而在实际学习中往往从具体的策略出发,不断优化已有策略。这里 γ表示未来的奖励会有衰减。
强化学习方法中有基于策略的( policy-based)、基于价值的( value-based),这两者属于无模型的( model-free)方法,还有有模型的( model-based)方法。
有模型的方法试图直接学习马尔可夫决策过程的模型,包括转移概率函数 P (s'|s, a)和奖励函数 r(s, a)。这样可以通过模型对环境的反馈进行预测,求出价值函数*大的策略 π?。
无模型的、基于策略的方法不直接学习模型,而是试图求解*优策略 π?,表示为函数 a = f?(s)或者是条件概率分布 P ?(a|s),这样也能达到在环境中做出*优决策的

目录 **篇 监督学习 第二篇 无监督学习 第13章 无监督学习概论 13.1.1 无监督学习基本原理 13.1.2 基本问题 13.1.3 机器学习三要素 13.1.4 无监督学习方法 第14章 聚类方法 14.1 聚类的基本概念 14.1.1 相似度或距离 14.1.2 类或簇 14.1.3 类与类之间的距离 14.2 层次聚类 14.3 k均值聚类 14.3.1 模型 14.3.2 策略 14.3.3 算法 14.3.4 算法特点 本章概要 继续阅读 习题 参考文献 第15章 奇异值分解 15.1 奇异值分解的定义与性质 15.1.1 定义与定理 15.1.2 紧奇异值分解与截断奇异值分解 15.1.3 几何解释 15.1.4 主要性质 15.2 奇异值分解的计算 15.3 奇异值分解与矩阵近似 15.3.1 弗罗贝尼乌斯范数 15.3.2 矩阵的*优近似 15.3.3 矩阵的外积展开式 本章概要 继续阅读 习题 参考文献 第16章 主成分分析 16.1 总体主成分分析 16.1.1 基本想法 16.1.2 定义和导出 16.1.3 主要性质 16.1.4 主成分的个数 16.1.5 规范化变量的总体主成分 16.2 样本主成分分析 16.2.1 样本主成分的定义和性质 16.2.2 相关矩阵的特征值分解算法 16.2.3 数据局正的奇异值分解算法 本章概要 继续阅读 习题 参考文献 第17章 潜在语义分析 17.1 单词向量空间与话题向量空间 17.1.1 单词向量空间 17.1.2 话题向量空间 17.2 潜在语义分析算法 17.2.1 矩阵奇异值分解算法 17.2.2 例子 17.3 非负矩阵分解算法 17.3.1 非负矩阵分解 17.3.2 潜在语义分析模型 17.3.3 非负矩阵分解的形式化 17.3.4 算法 本章概要 继续阅读 习题 参考文献 第18章 概率潜在语义分析 18.1 概率潜在语义分析模型 18.1.1 基本想法 18.1.2 生成模型 18.1.3 共现模型 18.1.4 模型性质 18.2 概率潜在语义分析的算法 本章概要 继续阅读 习题 参考文献 第19章 马尔可夫链蒙特卡罗法 19.1 蒙特卡罗法 19.1.1 随机抽样 19.1.2 数学期望估计 19.1.3 积分计算 19.2 马尔可夫链 19.2.1 基本定义 19.2.2 离散状态马尔可夫链 19.2.3 连续状态马尔可夫链 19.2.4 马尔可夫链的性质 19.3 马尔可夫链蒙特卡罗法 19.3.1 基本想法 19.3.2 基本步骤 19.3.3 马尔可夫链蒙特卡罗法与统计学习 19.4 Metropolis-Hastings算法 19.4.1 基本原理 19.4.2 Metropolis-Hastings算法 19.4.3 单分量Metropolis-Hastings算法 19.5 吉布斯抽样 19.5.1 基本原理 19.5.2 吉布斯抽样算法 19.5.3 抽样计算 本章概要 继续阅读 习题 参考文献 第20章 潜在狄利克雷分配 20.1 狄利克雷分布 20.1.1 分布定义 20.1.2 共轭先验 20.2 潜在狄利克雷分配模型 20.2.1 基本想法 20.2.2 模型定义 20.2.3 概率图模型 20.2.4 随机变量序列的可交换性 20.2.5 概率公式 20.3 LDA的吉布斯抽样算法 20.3.1 基本想法 20.3.2 算法的主要部分 20.3.3 算法的后处理 20.3.4 算法 20.4 LDA的变分EM算法 20.4.1 变分推理 20.4.2 变分EM算法 20.4.3 算法推导 20.4.4 算法总结 本章概要 继续阅读 习题 参考文献 第21章 PageRank算法 21.1 PageRank的定义 21.1.1 基本想法 21.1.2 有向图和随机游走模型 21.1.3 PageRank的基本定义 21.1.4 PageRank的一般定义 21.2 PageRank的计算 21.2.1 迭代算法 21.2.2 幂法 21.3.3 代数算法 本章概要 继续阅读 习题 参考文献 第22章 无监督学习方法总结 22.1 无监督学习方法的关系和特点 22.1.1 各种方法之间的关系 22.1.2 无监督学习方法 22.1.3 基础及其学习方法 22.2 话题模型之间的关系和特点 参考文献 附录A 梯度下降法 附录B 牛顿法和拟牛顿法 附录C 拉格朗日对偶性 附录D 矩阵的基本子空间 附录E KL散度的定义和狄利克雷分布的性质 索引