书摘：《统计学习方法》-李航
第1章 统计学习方法概论
首先叙述统计学习的定义、研究对象与方法；然后叙述监督学习，这是本书的主要内容；接着提出统计学习方法的三要素：模型、策略和算法；介绍模型选择，包括正则化、交叉验证与学习的泛化能力；介绍生成模型与判别模型；最后介绍监督学习方法的应用：分类问题、标注问题与回归问题。
1.1 统计学习
统计学习（learning）是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科。统计学习也称为统计机器学习（machinelearning）。
统计学习的对象是数据（data）。它从数据出发，提取数据的特征，抽象出数据的模型，发现数据中的知识，又回到对数据的分析与预测中去。
统计学习关于数据的基本假设是同类数据具有一定的统计规律性，这是统计学习的前提。这里的同类数据是指具有某种共同性质的数据，例如英文文章、互联网网页、数据库中的数据等
统计学习用于对数据进行预测与分析，特别是对未知新数据进行预测与分析。
对数据的预测与分析是通过构建概率统计模型实现的。统计学习总的目标就是考虑学习什么样的模型和如何学习模型，以使模型能对数据进行准确的预测与分析，同时也要考虑尽可能地提高学习效率。
统计学习的方法是基于数据构建统计模型从而对数据进行预测与分析。统计学习由监督学习（learning）、非监督学习（learning）、半监督学习（learning）和强化学习（learning）等组成。
data）集合出发，假设数据是独立同分布产生的；并且假设要学习的模型属于某个函数的集合，称为假设空间（space）；应用某个评价准则（criterion），从假设空间中选取一个最优的模型，使它对已知训练数据及未知测试数据（data）在给定的评价准则下有最优的预测；最优模型的选取由算法实现。这样，统计学习方法包括模型的假设空间、模型选择的准则以及模型学习的算法，称其为统计学习方法的三要素，简称为模型（model）、策略（strategy）和算法（algorithm）。实现统计学习方法的步骤如下：（1）得到一个有限的训练数据集合；（2）确定包含所有可能的模型的假设空间，即学习模型的集合；（3）确定模型选择的准则，即学习的策略；（4）实现求解最优模型的算法，即学习的算法；（5）通过学习方法选择最优模型；（6）利用学习的最优模型对新数据进行预测或分析。
统计学习研究一般包括统计学习方法（learningmethod）、统计学习理论（learningtheory）及统计学习应用（ofstatisticallearning）三个方面。统计学习方法的研究旨在开发新的学习方法；统计学习理论的研究在于探求统计学习方法的有效性与效率，以及统计学习的基本理论问题；统计学习应用的研究主要考虑将统计学习方法应用到实际问题中去，解决实际问题。
1.2.1 基本概念
在监督学习中，将输入与输出所有可能取值的集合分别称为输入空间（space）与输出空间（space）。输入与输出空间可以是有限元素的集合，也可以是整个欧氏空间。输入空间与输出空间可以是同一个空间，也可以是不同的空间；但通常输出空间远远小于输入空间。每个具体的输入是一个实例（instance），通常由特征向量（vector）表示。这时，所有特征向量存在的空间称为特征空间（space）。
监督学习从训练数据（data）集合中学习模型，对测试数据（data）进行预测。训练数据由输入（或特征向量）与输出对组成
输入与输出对又称为样本（sample）或样本点。
根据输入、输出变量的不同类型，对预测任务给予不同的名称：输入变量与输出变量均为连续变量的预测问题称为回归问题；输出变量为有限个离散变量的预测问题称为分类问题；输入变量与输出变量均为变量序列的预测问题称为标注问题。
监督学习假设输入与输出的随机变量X和Y遵循联合概率分布P(X,Y)。P(X,Y)表示分布函数，或分布密度函数。注意，在学习过程中，假定这一联合概率分布存在，但对学习系统来说，联合概率分布的具体定义是未知的。训练数据与测试数据被看作是依联合概率分布P(X,Y)独立同分布产生的。统计学习假设数据存在一定的统计规律，X和Y具有联合概率分布的假设就是监督学习关于数据的基本假设。
监督学习的目的在于学习一个由输入到输出的映射，这一映射由模型来表示。
1.2.2 问题的形式化
监督学习利用训练数据集学习一个模型，再用模型对测试样本集进行预测（prediction）。
1.3.1 模型
统计学习首要考虑的问题是学习什么样的模型。在监督学习过程中，模型就是所要学习的条件概率分布或决策函数。模型的假设空间（space）包含所有可能的条件概率分布或决策函数。
由决策函数表示的模型为非概率模型，由条件概率表示的模型为概率模型。
1.3.2 策略
有了模型的假设空间，统计学习接着需要考虑的是按照什么样的准则学习或选择最优的模型。
理论上模型f(X)关于联合分布P(X,Y)的平均意义下的损失，称为风险函数（riskfunction）或期望损失（expectedloss）。
模型f(X)关于训练数据集的平均损失称为经验风险（risk）或经验损失（loss）
期望风险exp(f)是模型关于联合分布的期望损失，经验风险emp(f)是模型关于训练样本集的平均损失。根据大数定律，当样本容量N趋于无穷时，经验风险emp(f)趋于期望风险exp(f)。所以一个很自然的想法是用经验风险估计期望风险。但是，由于现实中训练样本数目有限，甚至很小，所以用经验风险估计期望风险常常并不理想，要对经验风险进行一定的矫正。
结构风险最小化（riskminimization，SRM）是为了防止过拟合而提出来的策略。结构风险最小化等价于正则化（regularization）。结构风险在经验风险上加上表示模型复杂度的正则化项（regularizer）或罚项（term）。
1.3.3 算法
算法是指学习模型的具体计算方法。
1.4.1 训练误差与测试误差
通常将学习方法对未知数据的预测能力称为泛化能力（generalizationability）
1.4.2 过拟合与模型选择
如果一味追求提高对训练数据的预测能力，所选模型的复杂度则往往会比真模型更高。这种现象称为过拟合（over-fitting）
1.5.1 正则化
模型选择的典型方法是正则化（regularization）。正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项（regularizer）或罚项term)。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大。
在所有可能选择的模型中，能够很好地解释已知数据并且十分简单才是最好的模型，也就是应该选择的模型。
1.6.1 泛化误差
学习方法的泛化能力（ability）是指由该方法学习到的模型对未知数据的预测能力，是学习方法本质上重要的性质。
1.7 生成模型与判别模型
监督学习方法又可以分为生成方法（approach）和判别方法（approach）。所学到的模型分别称为生成模型（model）和判别模型（model）。生成方法由数据学习联合概率分布P(X,Y)，然后求出条件概率分布P(Y|X)作为预测的模型，即生成模型
这样的方法之所以称为生成方法，是因为模型表示了给定输入X产生输出Y的生成关系。典型的生成模型有：朴素贝叶斯法和隐马尔可夫模型
判别方法由数据直接学习决策函数f(X)或者条件概率分布P(Y|X)作为预测的模型，即判别模型。判别方法关心的是对给定的输入X，应该预测什么样的输出Y。典型的判别模型包括：k近邻法、感知机、决策树、逻辑斯谛回归模型、最大熵模型、支持向量机、提升方法和条件随机场等
生成方法的特点：生成方法可以还原出联合概率分布P(X,Y)，而判别方法则不能；生成方法的学习收敛速度更快，即当样本容量增加的时候，学到的模型可以更快地收敛于真实模型；当存在隐变量时，仍可以用生成方法学习，此时判别方法就不能用。判别方法的特点：判别方法直接学习的是条件概率P(Y|X)或决策函数f(X)，直接面对预测，往往学习的准确率更高；由于直接学习P(Y|X)或f(X)，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。
1.8 分类问题
评价分类器性能的指标一般是分类准确率（accuracy），其定义是：对于给定的测试数据集，分类器正确分类的样本数与总样本数之比。
对于二类分类问题常用的评价指标是精确率（precision）与召回率（recall）。通常以关注的类为正类，其他类为负类，
1.9 标注问题
标注问题的输入是一个观测序列，输出是一个标记序列或状态序列。标注问题的目标在于学习一个模型，使它能够对观测序列给出标记序列作为预测。
评价标注模型的指标与评价分类模型的指标一样，常用的有标注准确率、精确率和召回率。
标注常用的统计学习方法有：隐马尔可夫模型、条件随机场。
1.10 回归问题
回归问题的学习等价于函数拟合：选择一条函数曲线使其很好地拟合已知数据且很好地预测未知数据（
回归问题按照输入变量的个数，分为一元回归和多元回归；按照输入变量和输出变量之间关系的类型即模型的类型，分为线性回归和非线性回归。
本章概要
分类问题、标注问题和回归问题都是监督学习的重要问题。
第2章 感知机
感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和–1二值
2.1 感知机模型
感知机模型的假设空间是定义在特征空间中的所有线性分类模型（linearclassificationmodel）或线性分类器(linearclassifier)，即函数集合{f|f(x)＝w·x+b}。
2.2.2 感知机学习策略
假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面。为了找出这样的超平面，即确定感知机模型参数w,b，需要确定一个学习策略，即定义（经验）损失函数并将损失函数极小化。
感知机学习的策略是在假设空间中选取使损失函数式（2.4）最小的模型参数w,b，即感知机模型。
2.3.1 感知机学习算法的原始形式
感知机学习算法是误分类驱动的，具体采用随机梯度下降法（gradientdescent）。首先，任意选取一个超平面0,b0，然后用梯度下降法不断地极小化目标函数（2.5）。极小化过程中不是一次使M中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。
感知机学习算法由于采用不同的初值或选取不同的误分类点，解可以不同。
2.3.2 算法的收敛性
训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。
感知机学习算法存在许多解，这些解既依赖于初值的选择，也依赖于迭代过程中误分类点的选择顺序。为了得到唯一的超平面，需要对分离超平面增加约束条件。
训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。
第3章 k近邻法
近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。
3.2.3 k值的选择
如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差（error）会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差（error）会增大，预测结果会对近邻的实例点非常敏感[2]。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合。如果选择较大的k值，就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。k值的增大就意味着整体的模型变得简单。
3.3.1 构造kd树
kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分（partition）。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。
第4章 朴素贝叶斯法
朴素贝叶斯（Bayes）法是基于贝叶斯定理与特征条件独立假设的分类方法[1]。对于给定的训练数据集，首先基于特征条件独立假设学习输入/输出的联合概率分布；然后基于此模型，对给定的输入x，利用贝叶斯定理求出后验概率最大的输出y。
4.1.2 后验概率最大化的含义
朴素贝叶斯法将实例分到后验概率最大的类中。这等价于期望风险最小化。
5.1.3 决策树与条件概率分布
决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分（partition）上。将特征空间划分为互不相交的单元（cell）或区域（region），并在每个单元定义一个类的概率分布就构成了一个条件概率分布。
5.2.2 信息增益
在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。
熵越大，随机变量的不确定性就越大。
特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差
5.2.3 信息增益比
特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D的经验熵H(D)之比
5.5.2 CART剪枝
剪枝算法由两步组成：首先从生成算法产生的决策树T0底端开始不断剪枝，直到T0的根结点，形成一个子树序列{T0，T1,…,Tn}；然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
第6章 逻辑斯谛回归与最大熵模型
逻辑斯谛回归（regression）是统计学习中的经典分类方法。最大熵是概率模型学习的一个准则，将其推广到分类问题得到最大熵模型（entropymodel）。逻辑斯谛回归模型与最大熵模型都属于对数线性模型。
6.1.2 二项逻辑斯谛回归模型
二项逻辑斯谛回归模型（logisticregressionmodel）是一种分类模型，由条件概率分布P(Y|X)表示，形式为参数化的逻辑斯谛分布。这里，随机变量X取值为实数，随机变量Y取值为1或0。我们通过监督学习的方法来估计模型参数。
6.2.1 最大熵原理
最大熵原理是概率模型学习的一个准则。最大熵原理认为，学习概率模型时，在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。通常用约束条件来确定概率模型的集合，所以，最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型。
6.3 模型学习的最优化算法
逻辑斯谛回归模型、最大熵模型学习归结为以似然函数为目标函数的最优化问题，通常通过迭代算法求解。从最优化的观点看，这时的目标函数具有很好的性质。它是光滑的凸函数，因此多种最优化的方法都适用，保证能找到全局最优解。常用的方法有改进的迭代尺度法、梯度下降法、牛顿法或拟牛顿法。牛顿法或拟牛顿法一般收敛速度更快。
第7章 支持向量机
支持向量机（vectormachines，SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机
支持向量机还包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划（convexquadraticprogramming）的问题，也等价于正则化的合页损失函数的最小化问题
支持向量机学习方法包含构建由简至繁的模型：线性可分支持向量机（supportvectormachineinlinearlyseparablecase）、线性支持向量机（supportvectormachine）及非线性支持向量机（supportvectormachine）。
当训练数据线性可分时，通过硬间隔最大化（hardmarginmaximization），学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机
当训练数据近似线性可分时，通过软间隔最大化（softmarginmaximization），也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机
当训练数据线性不可分时，通过使用核技巧（kerneltrick）及软间隔最大化，学习非线性支持向量机。
通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。这样的方法称为核技巧。核方法（kernelmethod）是比支持向量机更为一般的机器学习方法。
7.1.1 线性可分支持向量机
线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量。
输入都由输入空间转换到特征空间，支持向量机的学习是在特征空间进行的。
学习的目标是在特征空间中找到一个分离超平面，能将实例分到不同的类。分
一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开。感知机利用误分类最小的策略，求得分离超平面，不过这时的解有无穷多个。线性可分支持向量机利用间隔最大化求最优分离超平面，这时，解是唯一的。
7.1.2 函数间隔和几何间隔
一致能够表示分类是否正确。所以可用量y(w·x+b)来表示分类的正确性及确信度，这就是函数间隔（functionalmargin）的概念。
对于给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点(xi，yi)的函数间隔为
定义超平面(w,b)关于训练数据集T的函数间隔为超平面(w,b)关于T中所有样本点i，yi)的函数间隔之最小值
定义超平面(w,b)关于训练数据集T的几何间隔为超平面(w,b)关于T中所有样本点i，yi)的几何间隔之最小值
超平面(w,b)关于样本点i，yi)的几何间隔一般是实例点到超平面的带符号的距离（distance），当样本点被超平面正确分类时就是实例点到超平面的距离。
如果||w||＝1，那么函数间隔和几何间隔相等。如果超平面参数w和b成比例地改变（超平面没有改变），函数间隔也按此比例改变，而几何间隔不变。
7.1.3 间隔最大化
支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言，线性可分分离超平面有无穷多个（等价于感知机），但是几何间隔最大的分离超平面是唯一的。这里的间隔最大化又称为硬间隔最大化
间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。
若训练数据集T线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。
在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（vector）
在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解；但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。由于支持向量在确定分离超平面中起着决定性作用，所以将这种分类模型称为支持向量机。支持向量的个数一般很少，所以支持向量机由很少的“重要的”训练样本确定。
7.1.4 学习的对偶算法
通过求解对偶问题（dualproblem）得到原始问题（primalproblem）的最优解，这就是线性可分支持向量机的对偶算法（dualalgorithm）。这样做的优点，一是对偶问题往往更容易求解；二是自然引入核函数，进而推广到非线性分类问题。
对于线性可分问题，上述线性可分支持向量机的学习（硬间隔最大化）算法是完美的。但是，训练数据集线性可分是理想的情形。在现实问题中，训练数据集往往是线性不可分的，即在样本中出现噪声或特异点。
7.3 非线性支持向量机与核函数
对解线性分类问题，线性分类支持向量机是一种非常有效的方法。但是，有时分类问题是非线性的，这时可以使用非线性支持向量机。
7.3.1 核技巧
非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。
核技巧应用到支持向量机，其基本想法就是通过一个非线性变换将输入空间（欧氏空间n或离散集合）对应于一个特征空间（希尔伯特空间），使得在输入空间n中的超曲面模型对应于特征空间中的超平面模型（支持向量机）。这样，分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。
在核函数K(x,z)给定的条件下，可以利用解线性分类问题的方法求解非线性分类问题的支持向量机。学习是隐式地在特征空间进行的，不需要显式地定义特征空间和映射函数。这样的技巧称为核技巧，
7.4 序列最小最优化算法
支持向量机的学习问题可以形式化为求解凸二次规划问题。这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。
8.1.1 提升方法的基本思路
在概率近似正确（probablyapproximatelycorrect，PAC）学习的框架中，一个概念（一个类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的
一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。
在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。
对于分类问题而言，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确的分类规则（强分类器）容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器（又称为基本分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。
对提升方法来说，有两个问题需要回答：一是在每一轮如何改变训练数据的权值或概率分布；二是如何将弱分类器组合成一个强分类器。关于第1个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器“分而治之”。至于第2个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。
8.3 AdaBoost算法的解释
AdaBoost算法还有另一个解释，即可以认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二类分类学习方法。
8.4 提升树
提升树是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学习中性能最好的方法之一。
8.4.1 提升树模型
提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法。以决策树为基函数的提升方法称为提升树（tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。
第10章 隐马尔可夫模型
隐马尔可夫模型（Markovmodel,HMM）是可用于标注问题的统计学习模型，描述由隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型。
10.1.1 隐马尔可夫模型的定义
隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程
隐藏的马尔可夫链随机生成的状态的序列，称为状态序列（statesequence）；每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列（observationsequence）。序列的每一个位置又可以看作是一个时刻。
10.1.3 隐马尔可夫模型的3个基本问题
隐马尔可夫模型有3个基本问题：（1）概率计算问题。
（2）学习问题。
（3）预测问题，
10.3 学习算法
隐马尔可夫模型的学习，根据训练数据是包括观测序列和对应的状态序列还是只有观测序列，可以分别由监督学习与非监督学习实现。本节首先介绍监督学习算法，而后介绍非监督学习算法——Baum-Welch算法（也就是EM算法）。
10.4 预测算法
隐马尔可夫模型预测的两种算法：近似算法与维特比算法（Viterbialgorithm）。
10.4.2 维特比算法
维特比算法实际是用动态规划解隐马尔可夫模型预测问题，即用动态规划（programming）求概率最大路径（最优路径）。这时一条路径对应着一个状态序列。
第11章 条件随机场
条件随机场（randomfield,CRF）是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔可夫随机场。
11.1 概率无向图模型
概率无向图模型（undirectedgraphicalmodel），又称为马尔可夫随机场（randomfield），是一个可以由无向图表示的联合概率分布。
11.1.1 模型定义
设有联合概率分布P(Y)，由无向图G＝(V,E)表示，在图G中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布P(Y)满足成对、局部或全局马尔可夫性，就称此联合概率分布为概率无向图模型（probabilityundirectedgraphicalmodel），或马尔可夫随机场（Markovrandomfield）。
事实上，概率无向图模型的最大特点就是易于因子分解。下
11.1.2 概率无向图模型的因子分解
将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作，称为概率无向图模型的因子分解
11.2.1 条件随机场的定义
条件随机场（randomfield）是给定随机变量X条件下，随机变量Y的马尔可夫随机场。这里主要介绍定义在线性链上的特殊的条件随机场，称为线性链条件随机场（chainconditionalrandomfield）。线性链条件随机场可以用于标注等问题。
本章概要
概率无向图模型或马尔可夫随机场的联合概率分布可以分解为无向图最大团上的正值函数的乘积的形式。
条件随机场是给定输入随机变量X条件下，输出随机变量Y的条件概率分布模型，其形式为参数化的对数线性模型。条件随机场的最大特点是假设输出变量之间的联合概率分布构成概率无向图模型，即马尔可夫随机场。条件随机场是判别模型。
线性链条件随机场是定义在观测序列与标记序列上的条件随机场。线性链条件随机场一般表示为给定观测序列条件下的标记序列的条件概率分布，由参数化的对数线性模型表示。模型包含特征及相应的权值，特征是定义在线性链的边与结点上的。
第12章 统计学习方法总结
感知机、k近邻法、朴素贝叶斯法、决策树、逻辑斯谛回归与最大熵模型、支持向量机、提升方法是分类方法。原始的感知机、支持向量机以及提升方法是针对二类分类的，可以将它们扩展到多类分类
感知机、k近邻法、朴素贝叶斯法、决策树是简单的分类方法，具有模型直观、方法简单、实现容易等特点。逻辑斯谛回归与最大熵模型、支持向量机、提升方法是更复杂但更有效的分类方法，往往分类准确率更高
隐马尔可夫模型、条件随机场是主要的标注方法。通常条件随机场的标注准确率更高。
分类问题与标注问题的预测模型都可以认为是表示从输入空间到输出空间的映射。它们可以写成条件概率分布P(Y|X)或决策函数Y＝f(X)的形式。前者表示给定输入条件下输出的概率模型，后者表示输入到输出的非概率模型。有时，模型更直接地表示为概率模型，或者非概率模型
朴素贝叶斯法、隐马尔可夫模型是概率模型。感知机、k近邻法、支持向量机、提升方法是非概率模型。而决策树、逻辑斯谛回归与最大熵模型、条件随机场既可以看作是概率模型，又可以看作是非概率模型。直接学习条件概率分布P(Y|X)或决策函数Y＝f(X)的方法为判别方法，对应的模型是判别模型。感知机、k近邻法、决策树、逻辑斯谛回归与最大熵模型、支持向量机、提升方法、条件随机场是判别方法
首先学习联合概率分布P(X,Y)，从而求得条件概率分布P(Y|X)的方法是生成方法，对应的模型是生成模型。朴素贝叶斯法、隐马尔可夫模型是生成方法。
决策树是定义在一般的特征空间上的，可以含有连续变量或离散变量。感知机、支持向量机、k近邻法的特征空间是欧氏空间（更一般地，是希尔伯特空间）
提升方法的模型是弱分类器的线性组合，弱分类器的特征空间就是提升方法模型的特征空间。感知机模型是线性模型，而逻辑斯谛回归与最大熵模型、条件随机场是对数线性模型。k近邻法、决策树、支持向量机（包含核函数）、提升方法使用的是非线性模型。
在二类分类的监督学习中，支持向量机、逻辑斯谛回归与最大熵模型、提升方法各自使用合页损失函数、逻辑斯谛损失函数、指数损失函数。
概率模型的学习可以形式化为极大似然估计或贝叶斯估计的极大后验概率估计。这时，学习的策略是极小化对数似然损失或极小化正则化的对数似然损失。
决策树学习的策略是正则化的极大似然估计，损失函数是对数似然损失，正则化项是决策树的复杂度。逻辑斯谛回归与最大熵模型、条件随机场的学习策略既可以看成是极大似然估计（或正则化的极大似然估计），又可以看成是极小化逻辑斯谛损失（或正则化的逻辑斯谛损失）。朴素贝叶斯模型、隐马尔可夫模型的非监督学习也是极大似然估计或极大后验概率估计，但这时模型含有隐变量。
朴素贝叶斯法与隐马尔可夫模型的监督学习，最优解即极大似然估计值，可以由概率计算公式直接计算。感知机、逻辑斯谛回归与最大熵模型、条件随机场的学习利用梯度下降法、拟牛顿法等。这些都是一般的无约束最优化问题的解法。支持向量机学习，可以解凸二次规划的对偶问题。有序列最小最优化算法等方法。决策树学习是基于启发式算法的典型例子。可以认为特征选择、生成、剪枝是启发式地进行正则化的极大似然估计。提升方法利用学习的模型是加法模型、损失函数是指数损失函数的特点，启发式地从前向后逐步学习模型，以达到逼近优化目标函数的目的。EM算法是一种迭代的求解含隐变量概率模型参数的方法，它的收敛性可以保证，但是不能保证收敛到全局最优。支持向量机学习、逻辑斯谛回归与最大熵模型学习、条件随机场学习是凸优化问题，全局最优解保证存在。而其他学习问题则不是凸优化问题。
附录A 梯度下降法
梯度下降法（descent）或最速下降法（descent）是求解无约束最优化问题的一种最常用的方法，有实现简单的优点。梯度下降法是迭代算法，每一步需要求解目标函数的梯度向量。
附录B 牛顿法和拟牛顿法
牛顿法（method）和拟牛顿法（Newtonmethod）也是求解无约束最优化问题的常用方法，有收敛速度快的优点。牛顿法是迭代算法，每一步需要求解目标函数的海赛矩阵的逆矩阵，计算比较复杂