第 1章统计学习方法概论 

本章简要叙述统计学习方法的一些基本概念．这是对全书内容的概括，也是全书内容的基础．首先叙述统计学习的定义、研究对象与方法；然后叙述监督学习，这是本书的主要内容；接着提出统计学习方法的三要素：模型、策略和算法；介绍模型选择，包括正则化、交叉验证与学习的泛化能力；介绍生成模型与判别模型；最后介绍监督学习方法的应用：分类问题、标注问题与回归问题． 
1.1 统 计 学 习 
1．统计学习的特点
统计学习（ statistical learning）是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科．统计学习也称为统计机器学习 (statistical machine learning）．
统计学习的主要特点是：（1）统计学习以计算机及网络为平台，是建立在计算机及网络之上的；（2）统计学习以数据为研究对象，是数据驱动的学科；（3）统计学习的目的是对数据进行预测与分析；（4）统计学习以方法为中心，统计学习方法构建模型并应用模型进行预测与分析；（5）统计学习是概率论、统计学、信息论、计算理论、最优化理论及计算机科学等多个领域的交叉学科，并且在发展中逐步形成独自的理论体系与方法论．
赫尔伯特 .西蒙（ Herbert A. Simon）曾对“学习”给出以下定义：“如果一个系统能够通过执行某个过程改进它的性能，这就是学习．”按照这一观点，统计学习就是计算机系统通过运用数据及统计方法提高系统性能的机器学习 . 现在，当人们提及机器学习时，往往是指统计机器学习．
2．统计学习的对象
统计学习的对象是数据（ data）．它从数据出发，提取数据的特征，抽象出数据的模型，发现数据中的知识，又回到对数据的分析与预测中去．作为统计学习的对象，数据是多样的，包括存在于计算机及网络上的各种数字、文字、图像、视频、音频数据以及它们的组合．
统计学习关于数据的基本假设是同类数据具有一定的统计规律性，这是统计学习的前提．这里的同类数据是指具有某种共同性质的数据，例如英文文章、互联网网页、数据库中的数据等．由于它们具有统计规律性，所以可以用概率统计
方法来加以处理．比如，可以用随机变量描述数据中的特征，用概率分布描述数据的统计规律．
在统计学习过程中，以变量或变量组表示数据．数据分为由连续变量和离散变量表示的类型．本书以讨论离散变量的方法为主．另外，本书只涉及利用数据构建模型及利用模型对数据进行分析与预测，对数据的观测和收集等问题不作讨论．
3．统计学习的目的
统计学习用于对数据进行预测与分析，特别是对未知新数据进行预测与分析．对数据的预测可以使计算机更加智能化，或者说使计算机的某些性能得到提高；对数据的分析可以让人们获取新的知识，给人们带来新的发现．
对数据的预测与分析是通过构建概率统计模型实现的．统计学习总的目标就是考虑学习什么样的模型和如何学习模型，以使模型能对数据进行准确的预测与分析，同时也要考虑尽可能地提高学习效率．
4．统计学习的方法
统计学习的方法是基于数据构建统计模型从而对数据进行预测与分析．统计学习由监督学习（ supervised learning）、非监督学习（ unsupervised learning）、半监督学习（ semi-supervised learning）和强化学习（ reinforcement learning）等组成．
本书主要讨论监督学习，这种情况下统计学习的方法可以概括如下：从给定的、有限的、用于学习的训练数据（ training data）集合出发，假设数据是独立同分布产生的；并且假设要学习的模型属于某个函数的集合，称为假设空间（hypothesis space）；应用某个评价准则（ evaluation criterion），从假设空间中选取一个最优的模型，使它对已知训练数据及未知测试数据（ test data）在给定的评价准则下有最优的预测；最优模型的选取由算法实现．这样，统计学习方法包括模型的假设空间、模型选择的准则以及模型学习的算法，称其为统计学习方法的三要素，简称为模型（model）、策略（strategy）和算法（algorithm）．
实现统计学习方法的步骤如下：
（1）得到一个有限的训练数据集合；

（2）确定包含所有可能的模型的假设空间，即学习模型的集合；

（3）确定模型选择的准则，即学习的策略；

（4）实现求解最优模型的算法，即学习的算法；

（5）通过学习方法选择最优模型；

（6）利用学习的最优模型对新数据进行预测或分析．


本书以介绍统计学习方法为主，特别是监督学习方法，主要包括用于分类、标注与回归问题的方法．这些方法在自然语言处理、信息检索、文本数据挖掘等领
1.2 监督学习 3 
域中有着极其广泛的应用．
5．统计学习的研究
统计学习研究一般包括统计学习方法（ statistical learning method）、统计学习理论（ statistical learning theory）及统计学习应用（ application of statistical learning）三个方面．统计学习方法的研究旨在开发新的学习方法；统计学习理论的研究在于探求统计学习方法的有效性与效率，以及统计学习的基本理论问题；统计学习应用的研究主要考虑将统计学习方法应用到实际问题中去，解决实际问题．
6．统计学习的重要性
近 20年来，统计学习无论是在理论还是在应用方面都得到了巨大的发展，有许多重大突破，统计学习已被成功地应用到人工智能、模式识别、数据挖掘、自然语言处理、语音识别、图像识别、信息检索和生物信息等许多计算机应用领域中，并且成为这些领域的核心技术．人们确信，统计学习将会在今后的科学发展和技术应用中发挥越来越大的作用．
统计学习学科在科学技术中的重要性主要体现在以下几个方面：
（1）统计学习是处理海量数据的有效方法．我们处于一个信息爆炸的时代，海量数据的处理与利用是人们必然的需求．现实中的数据不但规模大，而且常常具有不确定性，统计学习往往是处理这类数据最强有力的工具．

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

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




1.2  监 督 学 习
统计学习包括监督学习、非监督学习、半监督学习及强化学习．本书主要讨论监督学习问题．
监督学习（supervised learning）的任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出做出一个好的预测（注意，这里的输入、输出是指某个系统的输入与输出，与学习的输入与输出不同）．计算机的基本操作就是给定一个输入产生一个输出，所以监督学习是极其重要的统计学习分支，也是统计学习中内容最丰富、应用最广泛的部分．
1.2.1 基本概念 
1．输入空间、特征空间与输出空间 
在监督学习中，将输入与输出所有可能取值的集合分别称为输入空间（ input space）与输出空间（ output space）．输入与输出空间可以是有限元素的集合，也可以是整个欧氏空间．输入空间与输出空间可以是同一个空间，也可以是不同的空间；但通常输出空间远远小于输入空间．
每个具体的输入是一个实例（ instance），通常由特征向量（ feature vector）表示．这时，所有特征向量存在的空间称为特征空间（feature space）．特征空间的每一维对应于一个特征．有时假设输入空间与特征空间为相同的空间，对它们不予区分；有时假设输入空间与特征空间为不同的空间，将实例从输入空间映射到特征空间．模型实际上都是定义在特征空间上的．
在监督学习过程中，将输入与输出看作是定义在输入（特征）空间与输出空间上的随机变量的取值．输入、输出变量用大写字母表示，习惯上输入变量写作 X，输出变量写作 Y．输入、输出变量所取的值用小写字母表示，输入变量的取值写作 x，输出变量的取值写作 y．变量可以是标量或向量，都用相同类型字母表示．除特别声明外，本书中向量均为列向量，输入实例 x的特征向量记作 
(1) (2) () i () 
x = (x , x " x ,, n T 
,, " x ) 
x()i 表示 x的第 i个特征．注意， x()i 与 xi不同，本书通常用 xi表示多个输入变量中的第 i个，即 
(1) (2) n T
x = (x , x ,", x( ) )
iii i 
监督学习从训练数据（ training data）集合中学习模型，对测试数据（ test data）进行预测．训练数据由输入（或特征向量）与输出对组成，训练集通常表示为 
T = {(x , y ),( x , y ), ",( x , y )} 
11 22 NN 
测试数据也由相应的输入与输出对组成．输入与输出对又称为样本（sample）或样本点．
输入变量 X和输出变量 Y有不同的类型，可以是连续的，也可以是离散的．人们根据输入、输出变量的不同类型，对预测任务给予不同的名称：输入变量与输出变量均为连续变量的预测问题称为回归问题；输出变量为有限个离散变量的预测问题称为分类问题；输入变量与输出变量均为变量序列的预测问题称为标注问题．


1.2 监督学习 5 
2．联合概率分布
监督学习假设输入与输出的随机变量 X和 Y遵循联合概率分布 (,) 
PXY. (,) 
PXY表示分布函数，或分布密度函数．注意，在学习过程中，假定这一联合概率分布存在，但对学习系统来说，联合概率分布的具体定义是未知的．训练数据与测试数据被看作是依联合概率分布 (,) 
PXY独立同分布产生的．统计学习假设数据存在一定的统计规律，X和 Y具有联合概率分布的假设就是监督学习关于数据的基本假设．
3．假设空间 
监督学习的目的在于学习一个由输入到输出的映射，这一映射由模型来表
示．换句话说，学习的目的就在于找到最好的这样的模型．模型属于由输入空间
到输出空间的映射的集合，这个集合就是假设空间（ hypothesis space）．假设空间
的确定意味着学习范围的确定．
监督学习的模型可以是概率模型或非概率模型，由条件概率分布 P(|YX) 或
决策函数（ decision function）Y=()
fX 表示，随具体学习方法而定．对具体的输入进行相应的输出预测时，写作 (|) y=() ．
Pyx或 fx 
1.2.2 问题的形式化 
监督学习利用训练数据集学习一个模型，再用模型对测试样本集进行预测（prediction）．由于在这个过程中需要训练数据集，而训练数据集往往是人工给出
的，所以称为监督学习．监督学习分为学习和预测两个过程，由学习系统与预测系
统完成，可用图 1.1来描述．

图 1.1监督学习问题
首先给定一个训练数据集 
{(xy , ),( , ), ",( x, y )}
T= xy 
11 22 NN 
其中 (, ) i=1, 2, ", N，称为样本或样本点． x∈.Rn是输入的观测值，
xi yi ， iX
也称为输入或实例， yi∈ Y是输出的观测值，也称为输出．监督学习中，假设训练数据与测试数据是依联合概率分布 (,) 
PXY独立同分布产生的．在学习过程中，学习系统利用给定的训练数据集，通过学习（或训练）得到一个模型，表示为条件概率分布 P.(| ) =.()．条件概率分布 
YX或决策函数 Y fXPYfX
.(|YX) 或决策函数 =.()描述输入与输出随机变量之间的映射关系．在预测过程中，预测系统对于给定的测试样本集中的输入 xN+1 ，由模型 
.(
Py + | x1) 或 y+ fx 1 给出相应的输出 y．
yN+1 =argmax .( N1 N+ N1 =N+ ) n+1 
y
N+1 
在学习过程中，学习系统（也就是学习算法）试图通过训练数据集中的样本 (,i) x，一个具体的模型 y fx可
xyi带来的信息学习模型．具体地说，对输入 =()以产生一个输出 () 输i出是 y，如果这个模型有很好
fxi，而训练数据集中对应的i的预测能力，训练样本输出 y()
i和模型输出 fxi 之间的差就应该足够小．学习系统通过不断的尝试，选取最好的模型，以便对训练数据集有足够好的预测，同时对未知的测试数据集的预测也有尽可能好的推广． 


1.3 统计学习三要素 
统计学习方法都是由模型、策略和算法构成的，即统计学习方法由三要素构成，可以简单地表示为方法＝模型＋策略＋算法下面论述监督学习中的统计学习三要素．非监督学习、强化学习也同样拥有这三要素．可以说构建一种统计学习方法就是确定具体的统计学习三要素． 
1.3.1 模型
统计学习首要考虑的问题是学习什么样的模型．在监督学习过程中，模型就是所要学习的条件概率分布或决策函数．模型的假设空间（hypothesis space）包含所有可能的条件概率分布或决策函数．例如，假设决策函数是输入变量的线性函数，那么模型的假设空间就是所有这些线性函数构成的函数集合．假设空间中的模型一般有无穷多个．
假设空间用 F表示．假设空间可以定义为决策函数的集合
F= {|fY fX = ( )} (1.1) 其中， X和 Y是定义在输入空间 X和输出空间 Y上的变量．这时 F通常是由一个参数向量决定的函数族： 
= fYfXn (1.2)
F{| =θ ( ), θ∈ R } 参数向量θ取值于 n维欧氏空间 Rn，称为参数空间（parameter space）．
1.3 统计学习三要素 7 
假设空间也可以定义为条件概率的集合
F ={|PPY X (| )} (1.3) 
其中， X和 Y是定义在输入空间 X和输出空间 Y上的随机变量．这时 F通常是由一个参数向量决定的条件概率分布族： 
F={|PPY X(| ), θ∈Rn} (1.4)
θ 
参数向量θ取值于 n维欧氏空间 Rn，也称为参数空间．
本书中称由决策函数表示的模型为非概率模型，由条件概率表示的模型为概率模型．为了简便起见，当论及模型时，有时只用其中一种模型． 
1.3.2 策略
有了模型的假设空间，统计学习接着需要考虑的是按照什么样的准则学习或选择最优的模型．统计学习的目标在于从假设空间中选取最优模型．
首先引入损失函数与风险函数的概念．损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏．
1．损失函数和风险函数 
监督学习问题是在假设空间 F中选取模型 f作为决策函数，对于给定的输入 X，由 f()X给出相应的输出 Y，这个输出的预测值 f()X与真实值 Y可能一致也可能不一致，用一个损失函数（ loss function）或代价函数（ cost function）来度量预测错误的程度．损失函数是 f()X和 Y的非负实值函数，记作 (, (．
LY f X))
统计学习常用的损失函数有以下几种：
（1）0-1损失函数（ 0-1 loss function） 
fX )
.1, Y≠ (
LY f X (,( )) =. (1.5)
fX )
.0, Y= ( 
（2）平方损失函数（ quadratic loss function） 
(,( )) =( .fX)) 2 (1.6)
LYfX Y ( 
（3）绝对损失函数（ absolute loss function） (,( )) =| Y.fX ) | (1.7)

LY f X ( 

（4）对数损失函数（ logarithmic loss function）或对数似然损失函数（ log- 


likelihood loss function） (,( | )) =.log PY X |
LYPY X ( ) (1.8) 
损失函数值越小，模型就越好．由于模型的输入、输出 (,)XY是随机变量，遵
循联合分布 (,) PXY，所以损失函数的期望是 
Rexp ( ) = P[(, ( ))] × Lyfx Pxy xy ,
f E LYfX ( ()) (, )dd (1.9)
= ∫XY
这是理论上模型 f()X关于联合分布 PXY的平均意义下的损失，
(,) 称为风险函数（risk function）或期望损失（expected loss）．学习的目标就是选择期望风险最小的模型．由于联合分布 (,) 
PXY是未知的， 
Rexp()f不能直接计算．实际上，如果知道联合分布 (,) 
PXY，可以从联合分布直接求出条件概率分布 P(|YX) ，也就不需要学习了．正因为不知道联合概率分布，
所以才需要进行学习．这样一来，一方面根据期望风险最小学习模型要用到联合分布，另一方面联合分布又是未知的，所以监督学习就成为一个病态问题（ill-formed problem）．给定一个训练数据集 
{(xy , ),( , ), ",( x, y )}T= xy 
11 22 NN 
模型 f()X关于训练数据集的平均损失称为经验风险（ empirical risk）或经验损失
（empirical loss），记作 Remp： 
N 
() = Ly fx ( ( )) 	(1.10)
Remp f 	1 ∑i, iNi=1 
期望风险 R ()	R ()f是模型关于联合分布的期望损失，经验风险 f是模型
关于训练样本集的exp平均损失．根据大数定律，当样本容量 N趋于无穷时emp，经验风
险 Remp()Rexp()
f趋于期望风险 f．所以一个很自然的想法是用经验风险估计期望风险．但是，由于现实中训练样本数目有限，甚至很小，所以用经验风险估计期望风险常常并不理想，要对经验风险进行一定的矫正．这就关系到监督学习的两个基本策略：经验风险最小化和结构风险最小化．
2．经验风险最小化与结构风险最小化
在假设空间、损失函数以及训练数据集确定的情况下，经验风险函数式 (1.10)就可以确定．经验风险最小化（empirical risk minimization，ERM）的策略认为，经验风险最小的模型是最优的模型．根据这一策略，按照经验风险最小化求最优
模型就是求解最优化问题： 
 min f∈F  1 1 (, ( )) N i i i Ly f x N = ∑  (1.11)  
其中，F是假设空间． 

当样本容量足够大时，经验风险最小化能保证有很好的学习效果，在现实中

1.3 统计学习三要素 9 
被广泛采用．比如，极大似然估计（maximum likelihood estimation）就是经验风
险最小化的一个例子．当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计．
但是，当样本容量很小时，经验风险最小化学习的效果就未必很好，会产生后面将要叙述的“过拟合(over-fitting)”现象．
结构风险最小化（ structural risk minimization，SRM）是为了防止过拟合而提出来的策略．结构风险最小化等价于正则化（ regularization）．结构风险在经验风险上加上表示模型复杂度的正则化项（ regularizer）或罚项（ penalty term）．在假设空间、损失函数以及训练数据集确定的情况下，结构风险的定义是 
1 N 
R () = ( ,()) +λJf 
f Ly fx ( ) (1.12)
srm ∑iiNi=1 
其中 ()Jf为模型的复杂度，是定义在假设空间 F上的泛函．模型 f越复杂，复
杂度 ()()
Jf就越大；反之，模型 f越简单，复杂度 Jf就越小．也就是说，复杂度表示了对复杂模型的惩罚．λ ≥0 是系数，用以权衡经验风险和模型复杂度．结构风险小需要经验风险与模型复杂度同时小．结构风险小的模型往往对训练数据以及未知的测试数据都有较好的预测．
比如，贝叶斯估计中的最大后验概率估计（maximum posterior probability estimation，MAP）就是结构风险最小化的一个例子．当模型是条件概率分布、损失函数是对数损失函数、模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大后验概率估计．
结构风险最小化的策略认为结构风险最小的模型是最优的模型．所以求最优
模型，就是求解最优化问题： 
 min f∈F  1 1 (, ( )) ( ) N i i i Ly fx Jf N λ = +∑  (1.13)  

这样，监督学习问题就变成了经验风险或结构风险函数的最优化问题 (1.11)和(1.13)．这时经验或结构风险函数是最优化的目标函数． 
1.3.3 算法
算法是指学习模型的具体计算方法．统计学习基于训练数据集，根据学习策略，从假设空间中选择最优模型，最后需要考虑用什么样的计算方法求解最优模型．
这时，统计学习问题归结为最优化问题，统计学习的算法成为求解最优化问题的算法．如果最优化问题有显式的解析解，这个最优化问题就比较简单．但通常解析解不存在，这就需要用数值计算的方法求解．如何保证找到全局最优解，并使求解的过程非常高效，就成为一个重要问题．统计学习可以利用已有的最优
化算法，有时也需要开发独自的最优化算法．
统计学习方法之间的不同，主要来自其模型、策略、算法的不同．确定了模型、策略、算法，统计学习的方法也就确定了．这也就是将其称为统计学习三要素的原因． 


1.4 模型评估与模型选择 
1.4.1 训练误差与测试误差 
统计学习的目的是使学到的模型不仅对已知数据而且对未知数据都能有很好的预测能力．不同的学习方法会给出不同的模型．当损失函数给定时，基于损失函数的模型的训练误差（ training error）和模型的测试误差（ test error）就自然成为学习方法评估的标准．注意，统计学习方法具体采用的损失函数未必是评估时使用的损失函数．当然，让两者一致是比较理想的．
fX ，训练误差是模型 fX 
假设学习到的模型是 Y =.() Y =.() 关于训练数据集的平均损失： 
1 N 
emp . ∑i . xi (1.14)
R ()f = Ly (, f ( )) 
Ni=1 其中 N是训练样本容量．测试误差是模型 Y =.()test N′ ∑′=ii 
fX 关于测试数据集的平均损失： 
= 1 N Ly (, f.( )) (1.15)
ex 
i 1 
其中 N′是测试样本容量．例如，当损失函数是 0-1损失时，测试误差就变成了常见的测试数据集上的误差率（error rate） 1 N 
test = ∑Iy ( i ≠ f. xi (1.16)
e ( )) 
i 1
N′ ′=.() 时为 1，否则为 0.
这里 I是指示函数（indicator function），即 y ≠fx 相应地，常见的测试数据集上的准确率（accuracy）为 1 N 
rtest =′ ∑( i = f.( i
Iy x )) (1.17)
N ′=
i 1 
显然， 
r + e =1
test test 
训练误差的大小，对判断给定的问题是不是一个容易学习的问题是有意义的，但本质上不重要．测试误差反映了学习方法对未知的测试数据集的预测能力，是学习中的重要概念．显然，给定两种学习方法，测试误差小的方法具有更好的