概率图模型第十六章

1、的键入文字键入文字概率图模型作者:Daphne Koller2014/10/15Nir FrieMan如果某个想要反映现实，那么这个公理一定不是确定的公式；而如果这个公理是确定的公式，那么它一定没有完全反映现实情况。，1956当我们想从某些事物中发现规律时，会有无数看不见又争脱不掉的绳索将我们，宇宙万物2皆是如此。，1869如今的逻辑科学认为某个只能是确定的，不可能的或者完全不确定的，这使得推理失去了价值。真正的逻辑科学应该是对概率的有理性的人。，而这些将逻辑与概率在一起的是真正具，1850概率实际上就是常识抽象为了微；现实中人们也许都对某些有些直觉的，却无法精确的计算，概率使得我们可以对这些

2、的精确性做出评价。拉，1819对概率的误解可能是提高科学素养过程中最大的。··的键入文字键入文字学习16 图模型的学习：综述2序言1.1我们目前所有的讨论都假设给定了一个图模型。比如，在中，我们假设模型（图结构和参数）是已知的。条件性质和推断的过程有两种方式可以得到一个完整的模型。第一种是在box3.C 中所说的通过人工构建的，通常需要领域事。如果使用这种的版主。，我们可以看出，从领域那里获取知识是一件非常麻烦的的话，即便是该领域经验丰富的工程师也需要好几个小时才能构建。此外，这个过程还需要出一个中等大小的模型。而更大的模型则需要几个进试才能确定模式是否合理。甚至是几这种人

3、工构建方式有几个。在某些领域中，构建模型所需的知识超出了所能花费的时间。而在其他领域中，根本就没有一个能够完全理解该领域的本质。而且在许多系统中，概率分布的特性会随着时间发生变化，所以我们也不能让这些隔几个就重新设计一下图模型。在许多情况下，我们能够获得从模型中生成的样本。事实上在这个信息，电子数据要比人类的数据更容易获取。比如，在医疗里包含了不同的属性，比如中（box3.D），我们可能会难道大量的，每个的病龄，是否抽烟，之前的并发症），报告症状，不同的体检报告结果，医生的初始和处方，以及治疗的结果。我们可以根据这些数据来学习在我们的人群中该概率分布的模型。对于家谱图分析（box3.B），我们

4、可能会得到一些频繁出现某疾病（比如乳）的家谱。根据这些家谱图，我们可以学习到该疾病的遗传参数：转移模型，它描述了某个疾病从父母传递给孩子的概率；穿透模型，它描述了给定型的条件下，外显的概率。对于图像分割（box4.B），我们可能会得到一些由人分割好的图，根据这些数据我们要学习图像分割数，或者说两个相邻像素属于同一个分割区域的概率有多大。的的参显然，我们可以利用这些数据为真实的概率分布构建一个好的模型，不论是仅利用这些数据还是与人类的先验知识相结合。根据样本构建模型的过程通常叫做模型学习。本书的这部分内容主要了不同模型学习的不同。在本章接下来的部分，我们不同类型的模型学习任务，以及这些模型学习中

5、会出现的。由一个潜在的概率分布P为了我们的内容更具体，我们假设系统的，并且这个概率分布与某个（有向或无向的） = (𝒦, )是对应的。我们可以得到一个数据集D = 𝐝1, . . , 𝐝M，该数据集是从概率分布P中生成的M个样本。附录 A.2了这个假设的意义，它假设所有的数据样本是从P中抽样出来的；如附录 A.2 所述，这些数据样本叫做同分布样本（IID）。此外，我们还给定了一族模型，所以我们的任务就是从这族模型中学习出一个模型 ，该模型对应的概率分布为P （如果 是已知的话，我们可以用P来表示 这个概率分布）。如果图模型的结构是固定的，那么我们

6、就只需要学习出参数即可，否则的话我们要把整个模型都学习出来。在某些情况下，我们希望得到多个不同的假设，这时我们的任务就不是仅得到一个模型了，而是要给出不同模型的概率分布或者给出我们学习得到的模型的置信度。下面我们首先评价测度。然后我们一下我们在学习模型时的不同目的，以及不同学习目的得到模型的一下如何将模型学习。最后我给出不同学习视为一个最优化，以及将学习看作不同最优化。时会出现的的分类，以及这些学习对应的计算学习的目的1.2在评价不同学习优缺点之前，我们首先要明白我们的目的是从数据中学习出一个概率模型。这么笼统的说的话，我们还是不清楚为什么学习目的的定义很重要。毕竟，最理想的情况下，我们希望得

7、到一个能够完全正确表示数据抽样的概率分布P的模型 。，由于计算复杂度和（更重要的是）数据的有限性只能给出真实潜在概率分布的一个粗略近似， 因此这个理想情况通常是无法达到的。在实际应用中，我们拥有的数据远不足以得到一个包含多个变量的概率分布。因此，我们只好是选择一个模型 ，使得该模型是的“最佳”近似。这个“最佳”就与我们的学习目的是相关的了。不同的模型通常会从各个角度做折中。3一个近似模型可能从一个角度来看是好的，而从另一个角度来看就未必了。因此，为了大体上理解不同的学习（译者注：，我们首先要定义模型学习的不同目的以及如何评价达到这个目的的程度。1.2.1密度估计学习一个模型的最常见理由是利用该

8、模型进行一些推断。显然，根据目前的内容，我们可以利用概率图模型回答各种各样的概率推断。这时，我们可以将我们模型学习的目的形式化为密度估计：构建一个模型 ，使得P与生成概率分布P非常相近。那么我们如何评价一个近似 的好坏呢？最常见的选择是使用定义 A.5 中的相对熵距离测度：当P = P时，这个测度的值为 0，否则的话为正。直观上来看，该测度说明了使用P近似P时会造成的压缩损失（以比特为）。为了评价这个测度我们必须要知道P。在某些情况下，我们根据综合生成的数据来评价不同学习的好坏，这时P可能是已知的。，在实际应用中，P是未知的。（如果已知的话，我们就不需要从数据中学习出一个模型来了）。不过，我们

9、可以将这个测度进行简化，从而得到一个更简单的评价。引理 16.1假设有两个关于𝒳的任意两个概率分布𝑃, 𝑃，那么证明：将这个推导过程应用与P, P的话，我们可以看出第一P的熵；该项的值与P无关，因此它 影响不同近似模型之间的比较。因此，我们可以只根据第二项EPlogP()的取值来评价不同近似模型之间的好坏，并希望我们得到的近似模型时的该项的值尽可能的大。该项叫做期望 log-似然。它表示我们希望我们的近似模型能够给从P中抽取出的样本高的概率。直观上来说， 给从P中样本的概率越多，那么P与P就越能反映概率分布P。需要注意的是，当我们放弃相对熵测度，

10、而选用期望 log 似然作为评价模型的标准时，我们就丢失了基本项EP logP，当然这是不可避免的，因为我们压根儿就不知道P。因此，尽管我们可以利用期望 log 似然来比较不同近似模型之间的好坏，但是我们却无法 某个近似模型 与真实概率分布到底有多近似。一般情况下，我们在讨论学习时会对给定模型条件下，数据集的似然概率感，也即是P(D: )；而为了方便，我们同样会使用 log-似然(D: ) = logP(D: )。4负 log 似然叫做 log 损失。Log 损失反应了使用P近同样，我们习惯分析负 log 似然，似真实概率分布时，每个样本的代价（以比特为）。Log-损失是我们要的第一个损失函数

11、，其中损失函数是统计学习框架中的一个部分。损失函数loss(: )描述了模型在某个具体样本上造成的损失。如果样本是从某个概率分布P中抽样得到的，那么我们密度估计的目的就是要找到一个模型使得期望损失或风险最小化：当然，通常情况下P是未知的。我们可以用经验平均来近似计算这个期望值，从而得到该近似模型相对真实概率分布P造成的风险，其中我们根据从P抽取的数据集D来计算这个经验风险：对于 log 损失函数来说，这个表有一个非常直观的解释。假设我们有同分布的数据集D = 1, . , M。那么模型认为数据集D的概率为：取 log 之后我们可得：这就是公式 16.1 中经验 log 损失的求和部分。这个风险

12、损失既可以作为评价具体某个模型好坏的测度，也可以作为给定数据集D和一类模型族之后，选择模型的一句。我们在 16.3.1 节和 box16.A 中会继续讨论这个。1.2.2特殊的目的在上一小节，我们假设学习模型的目的是用于概率推断的。根据这个假设，我们的形式化结论是希望我们的近似尽可能的与模型的整个概率分布P保持一致我们选择模型测度仅仅评价了我们的模型对完全样本概率的好坏程度。而事实上，该模型还可用于P(𝐘|𝐗)形式的概率。一般来说，我们可以为得到的模型设计一个某类的测试集合来评价该模型对该类集𝐘的取值进行的好坏。，大多时候我们是希望给定某变量子集

13、𝐗取值条件下，对变量子最简单的情况下，我们可能希望解决一个简单的分类，这也是学习的大部分。比如，对于文本分类，其中我们有一个描述文本的单词集合𝐗和其他特征，还有一个变量Y用来标注该文章的个像素的类别。在图像分割中，我们希望在给定图像特征𝐗的情况下，图像𝐘中每训练的模型要能够给出每个取值𝐱对应的概率分布P(Y|𝐱)。然后，我们会根据为这个条件概率分布选择最可能取值从而生成一个具体的：那么对于，在模型学习的过程中，我们应该用什么样的损失函数来评价模型的好坏呢？比如，我们可以用分类误差来评价，分类误差有叫

14、做 0/1 损失：5这个损失函数实际上就是从P生成的所有样本(𝐱, 𝐲)中，通过最可能取值分类器得到错误类别的概率。尽管这个测度很适用于只有一个类别变量的情况，但是对于诸如图像分割之类的应用就不是用了，因为我们要同时给出许多类别变量的值。这时，如果我们只标错了几个分类变量的值的话，那么我们令惩罚值为 1。因此，我们可以使用汉明损失来作为评价测度，该损失函数并不是指示函数IhP(𝐱) 𝐲，而对hP(𝐱)中变量集合𝐘与真实取值𝐲不一致的变量个数。此外，我们可能希望将每次的置信程度也考虑在

15、内。评价置信程度的测度是条件似然或条件似然的 log 对数（有时又叫做条件 log 似然）：与 log 似然的评价标准类似，这个测度评价了我们学习得到的模型能够从P生成样本的程度，我们学习得到模型只能是在给定𝐗取值条件下才能𝐘，而不能给出𝐗的概率分布。与之前一样，我们可以将这个表计算经验估计。取负来定义一个损失函数，然后通过对数据集D去平均来如果我们事先确定了我们要学习的模型只会用于执行某个具体的任务，那么我们就可以 做一些折中来使得学习算法更适合这个具体的任务。具体来说，如果我们要学习的模型从来对变量𝐗进行，那么我们就可以使得我

16、们模型学习的算法只优化对𝐘结果好坏的测度。我们会在 16.3.2 节继续讨论这个。1.2.3知识发现学习P概率模型的最后一类截然不同目的是用于P本身的知识发现。我们可能希望通过对学习到的模型进行分析就可以揭示该系统的某些重要特性：系统中变量之间哪些直接或间接的依赖，这些依赖之间到底有什么本质（比如，正相关或负相关）等等。比如，在遗传推断中，我们希望发现掌控某个特性遗传的参数，因为这些参数可能会使得我们深入理解掌控疾病等位的遗传机制。在医疗领域，我们可能希望了学习到模型的图结构，从而发现那些先导因素会导致某些疾病，以及那些症状与不同的疾病之间的。当然，我们可以使用更简单的统计模型

17、来发现数据中的规律，比如找出成对变量之间的最重要的关联。然而，根据学习到的模型参数可以给出直接因果解释，此外我们还可以通过区分有向依赖和无向依赖来解释更细粒度的结构。知识发现的需要一种与之前任务截然不同的评价标准和不同的折中方案。这时我们最关心的是重构正确的图模型，而不是学习出一个导出分布与的导出分布相似的其他模型 。因此，与密度估计不同的是，对于密度估计来说我们的评价测度是关于模型对应的概率分布的（比如D(P, P)），而对于知识发现，我们评价学习与否的测度是关于模型的，也即是说与 结构上的是否有差别。的。首先，即便我们拥有大量的数据，真实的模型结构也可能不是唯一的。比如，我们要重构，要得到

18、真实结构的这个目的通常是无法实现的真实结构为𝒦。我们知道一个给定的结构通常有多个 I-等价的结构。如果目标结构𝒦就是这种情况的话，那么我们最多指望返回其中一个 I-等价的结构。不过当数据有限时，这个就麻烦了。比如，如果X和Y在𝒦中是直接相关的，但是它们之间参数说明这个相关非常弱的话，那么很难从数据中出这不是个随机的扰动。不过这个限制对于密度估计来说就小一点了，因为忽视掉这个弱的关联通常对学习到的密度函数产生重大的影响；，如果我们的目的是重构正确的结构的话，那么这种情况就会使我们的结果不精确。相反，如果训练数据相对于变量个数非常多的话，那么就可能由

19、于偶然因素使得本来关联很弱的一对变量关联很强。因此，我们可能会得出原来中不的边。如果我们的目的是为了发现潜在概率分布的真实结构，那么模型的唯一性是一个非常重要的。比如，如果我们要推断那个着那个（box21.D），并且我们想将这些分析结果应用与实验的话，那么我们就要给出我们得到的这些的置信度。因此，在知识发现的应用中的置信度相当重要，也即是说我们要知道给定假设空间和训练数据的条件下，我们分析结果在多大程度上正确的。我们会在接下来的章节中继续讨论这个。6从最优化的角度看学习1.3我们了评价学习得到模型的不同。许多情况下，我们会定义一个希望最优化的数值评价标准（损失函数）。这说明，学习应该视为是一个

20、最优化：我们有一个假设空间（也即是候选模型集合）和目标函数（用来评价不同模型好坏的标准）。因此，学习可以形式化为在假设空间中寻找一个得分很好的模型。将学习视为最优化是目的学习的主流（不仅仅是概率模型的学习）。本节我们一下不同目标函数的选择以及该目标函数对学习算法的影响。本节的会是习部分的基础。需要注意的，相应的形式化描述会在之后的章节中，但是本节会给出一些重要的概念。1.3.1经验风险与过拟合假设我们要构建模型，我们的学习算法是最优化某个损失函数的期望𝐄Ploss(: )。当然，通常情况下我并不知道P，但是我们可以根据从P中抽取的样本集D对该期望做经验估 计。形式化的说，我们可

21、以根据数据集D定义一个经验概率分布PD：这也即是说，在经验概率分布中A的概率就是在训练样本中与A一致的样本所占的比重。显然PD(A)确实是一个归一化的概率分布。而且，随着训练样本个数的增加，经验分布会趋于真实的概率分布。定理 16.1令𝜉1, 𝜉2, 是一个从𝑃(𝒳)中抽取的么同分布样本序列，数据集𝐷𝑀 = 𝜉1, . 𝜉𝑀，那成立的概率趋近于 1。因此，如果给定足够大的训练集，那么PD就会以非常高的概率（当𝑀 时，这个概率值趋近于 1

22、）与原概率分布𝑃接近。因为我们通常无法得到真实的概率分布𝑃，所以我们可以用PD作为𝑃的最佳，然后最小化关于概率分布PD的期望损失。如果简单的应用这个最优化目标的话就会得到非常差的结果。比如，如果我们用经验 log 损失作为目标函数的话。那么不难证明（见 17.1 节），使得数据集D的似然概率最大的概率分布就是PD。现在，假设我们有一个由 100 个二值变量定义的概率空间，也即是总共有2100个取值。如果我们的数据集值有 1000 个样本的话（这时极有可能是这 1000 个样本各不相同），那么根据经验概率分布，数据集D中出现的每个取值的概率为 0.

23、001，而概率空间中其他2100 1000个取值的概率都是 0。尽管这个例子很，但是其表示的却很常见。比如，假设M是一个，其中某些变量（比如 Fever）会有非常多的父节点X1, , Xk。如果用表格表示条件概率分布的话，那么参数的个数会与父节点个数 k 成指数取值，也即是。如果 k 非常大的话，那么在D中就几乎不可能会出现父节点的所有可能的出现与所有综合疾病X1, , Xk都相关的样本。因此，如果我们没有足够多的数据的话，那么条件概率分布中的项就会与训练集扯不上，从而就会出现在某些疾病条件下症状 Fever 的条件概率的估计很差。一般来说，参数估计所需的样本数与参数的个数成线性，所以样本数会

24、与连接的稠密程度成指数。从上述例子中我们可以看出，用经验风险（训练集中的损失）来代替真实风险会出现很大的。具体来说，目标函数的学习算倾向于对训练数据集过拟合。，我们学习模型的真正目的不仅仅是训练集的，而是用来对训练集之外的取值进行的。因此，在医疗的例子中，我们学习得到的要能适用于新的，而不是训练集中的。对于图7像分割，我们学习得到的模型最终要应用到新的未分割图像中去，而不是在训练模型时已经分割好的图像。因此，我们学习得到的模型要具有很强的推广性，从而适用于未知的数据。模型的推广性和过拟合是学习部分讨论的关键点，根据不同的目的，我们会在这两方面做不同的折中。一方面来说，如果我们的假设空间非常有限

25、的话（也即是候选模型很少），那么在这个假设空间中可能就不 真实的概率分布P。因此，这时即便我们有无限多的数据也无法学习到真实的概率分布P，从而我们最终得到的是一个次优的模型。这类假设空间的局限性会对学习的结果引入固有的误差（又叫做偏置），因为这时学习的结果与目标概率分布的近似程度有一个极限。相反，如果我们选择的假设空间的表示能力很强（也即是候选模型很多），那么我们就有可能表示正确的目标概率分布P。，如果只给定有限的数据集的话，那么我们就无法从假设空间的众多候选模型中选择出一个正确的模型，所以通常我们也只能得到训练集D的一个好一点的损失。直观上来说，如果我们的假设空间很大，而样本数量有限的话，

26、那么在选择训练集D时小的随机扰动也会导致最终的结果与P有很多的出入。因此，学习的过受到高方差的影响也即是我们的学习过程在从P抽取的不同数据集上进行训练会得到非常不同的结果。相反，如果我们的假设空间非常小，那么我们就很难从假设空间中发现有一个模型与数据集D拟合的很好。因此，在受限假设空间中找到的高分模型更有可能是与P拟合很好的，因此也就更有可能推广到未知的数据。偏倚方差之间的折中贯穿了我们整个学习算法的设计过程。如果我们要选择一个包 含不同模型的假设空间，那么我们必须要注意不能使得假设空间中的模型太多。事实上，在 有限数据的情况下，由方差引入的误差要比偏置引入的误差大很多，因此我们可能会限制我

27、们要学习的模型，尽管我们的限制可能太简单而无法正确表示𝐏。虽然，这时我们学习到的 模型一定是错误的，但是由于这时我们的数据足以训练出可靠的参数，所以可以弥补模型本 书的错误假设结构带来的误差。此外，在知识发现中，如果我们要学习模型结构的话，那么虽然根据我们的受限假设无法学习到所有的边，但是这个限制可能会让我们更准确的学习到真实结构中最重要的一些边。换句话说，在受限的假设空间中得到的模型 可能会在训练集的目标函数上表现很差，但是P 与P的距离却可能是更小了。限制假设空间中候选模型的结构是一种减小过拟合的。从效果上来说，这种就是对候选模型施加了一个硬约束，从而我们选择一个正好表示训

28、练集经验概率分布的模型。另一种减小过拟合的是调整我们的训练目标函数，从而使得目标函数软倾向于简单的模型。因此，这时我们通常会有一个包含正则项的目标函数：其中一些让我们的模型尽可能的去的拟合这个具体的数据集。拟合训练数据；另一些作为调整项，来防止我们的模型仅仅许多情况下我们会结合这两种方式进行学习，我们用硬约束来限制模型的类别，并使用一个 能够防止过拟合的优化目标函数。以上了过拟合现象以及模型推广性的重要性。，我们并没有如何学习才能保了一些设计证模型的推广性，以及如何设计假设空间或目标函数来减少过拟合。Box16.A和评价学习算法的经验。Box16.B了关于模型复杂的理论框架。Box16.A技巧

29、：设计和评价学习算法。模型学习过程中的一个基本是评价学习算法的性能。评价的第一种情况是为了比较两个或多个学习算法的好坏（比如，不同的假设空间和不同的训练目标函数），而第二种情况下我们则是为了评价一下我们学习到的模型是否表示了真实的概率分布。要回答这两个并不是件简单的事，人们为此提出了如何回答这些的理论。这里我们简单总结一下其中的一些主要思想。在这两种评价，我们的理想目的是为了比较学习到的模型与产生数据的真实潜在概率分布之间的区别。如果我们是根据人造数据对学习算法进行评测的话，概率分布是已知的， 故而我们的目的就是比较学习到的模型与真实概率分布之间的差别（见 box17.C）。，如果我们是从实际

30、的数据中学习模型的话，那么我们就无法进行这种比较，因为这的概率分布是未知的。尽管人造数据可以帮助我们理解不同学习算法的特性，但是它们无法与现实中的数据相比。推广性的评价 我们首先来讨论一下给定一个从训练集中得到的模型之后，如何评价它对未知数据的推广性。法是使用争议测试。这时，数据集分为两个不相交的集合：训8练集Dtrain和测试集Dtest。为了避免分组对测试的影响，我们通常会用随机的进行划分。然后我们利用Dtrain学习出一个模型（使用恰当的目标函数），然后我们观察一下该模型在Dtest 中的表现（使用恰当的损失函数）。因为Dtest也是从P中抽取的样本，所以我们可以根据测试集来对风险进行经

31、验估计。，由于Dtest与Dtrain是不相交的，所以是根据训练过程中没有出现的样本来计算损失的。因此该能够给出模型在新样本上推广性的无偏估计。争议测试可以用于比较不同学习算法的推广性。它也可用于研究某一个学习算法的推广性。具体来说，我们可以比较该算法得到的模型在训练集和测试集上的表现（比如说每个样本的经 验 log 损失，或分类误差）。一般来来说，模型在训练集上的效果要更好一些，但是如果在训练集和测试集上的差别非常大的话，那么我们就可能对训练集过拟合了，因此我们可以考虑使用更简单的一类模型作为假设空间，或者使用其它避免过拟合的。争议测试实际上是一个权衡的过程。为了更好的估计模型的推广性，我们

32、希望增大测试集的大侠。，增大测试集的话就意味着要加少训练集的大小，从而又会导致我们学习到的模型的质量变差。如果我们有非常多的训练集的话，那么我们可以在这两者之间找到合理的折中方案。而如果我们的训练样本很少的话，那么就没有折中的方案了，因为减小训练集或减小测试集都会对学习得到模型的质量或着评价该模型的推广性造成影响。另式是将数据集既用于训练也拥有测试。当然，我们不能使用训练集进试；这里的技巧是重复进行争议测试。也即是说，在每次迭代过程中，我们在一个样本子集上进行训练，而在另一个样本子集上进试。如果我们进行多次迭代，那么我们就每次只用少量的测试集对模型的推广性进行评价，然后将所有的结果综合起来得到

33、最终的评价结果。现在的是如何划分训练集和测试集。最常用的是 k 折交叉，其中每个样本都会作为测试集一次。我们可以将原始数据集划分为 k 个相同大小的子集，然后在每一轮迭代中，取其中的一个子集用于测试，而其它的子集用于训练；见算法 16.A.1。交叉的一个情况是留一交叉，其中我们令k = M，这也即是说在每一轮迭代过程中，我们取一个样本作为测试。这两种交叉 策略都 我们既可以估计学习算法的平均性能，又能估计该模型在不同数据集上的性能。争议测试和交叉是评价学习算法的主流。具体来说，交叉过构建出 k个不同的模型，每个模型对应于不同的训练集与分割集，因此交叉只得到一个模型。如果我们希望写一篇关于新学习

34、的，那么交叉的结果可以作为评价新学习算法和与其他算法比较的标准。如果我们最终想得到一个能用于实际的模型，那么我们可以用交叉验证或争议的来选择一个算法来保证其运行效果令我们满意，然后在整个数据集D上训练我们的模型，从而利用所有的数据来学习一个模型。学习的选择 这些评价策略的最常见用处是为某个具体应用选择一个好的学习算法。这也即是说，我们通常希望从一个学习算法集合中选择出一个好的算法：不同的学习算法，或同一种学习算法不同的算法参数（比如，我们对所络结构复杂度的不同限制）。乍一看，使用争议测试或交叉就可以达到这个目的：我们使用这两个评价每个学习算法LearnProcj的性能，然后选择一个损失估计值最

35、小的算法。尽管这种方式看起来合情合理，并且我们得到的结果似乎也可以作为该学习算法对未知数据推广性的评价标准。，这种方式很容易得到错误的结论，并且对算法推广性过于乐观，因为我们是从学习算法集合中选择了一个最优化相同评价测度的学习。因此，如果我们用交叉或争议测试进行学习选择，并且我们还希望得到我们选择出的算法在未知数据上的推广性，那么我们就必须留出一个在模型训练中没有用过的的测试集，最后我们在这个测试集上评价我们学习算法的最终推广性。这时，我们需要有一个训练集（用来学习模型）；一个集，用来评价不同学习算法结果的的测试集，用来对选择出的模型做推推广性，并最终选择出一个来；此外还需有一个广性的最终评测

36、。当然，这种方式实际上加剧了训练集划分的，所以我们可以用嵌套的交叉策略来达到这个目的。拟合优度交叉和争议测试能够评价不同学习算法在未知数据上的推广性。，如果没有一个“好标准”进行比较的话，那么我们就无法评价我们学习得到的模型是否表示了目标概率分布。这是一个很难的。在统计学中，解决这个的属于拟合优度测试。其主9要思路如下。在学习到模型的参数之后，我们实际上是对产生这些数据集的概率分布做了一个假设。现在，我们可以一下我们的数据集是否像是从我们学习到的概率分布中生成的。为此，我们根据学习到的概率分布生成与训练集大小相同的一个样本集，然后比较一下这个模拟数据集与训练集的某个性质是否相似。如果我们得到的

37、模拟数据集的性质与训练集的性质非常不同，那么我们就有理由相信训练集不是从我们学习到的模型中抽取的样本。具体来说，我们以数据集的某个性质f作为比较标准，首先计算训练集的性质f(Dtrain)。然后我们从学习到的模型中生成多个新的数据集D，然后计算这些新数据集的性质f(D)。如果f(Dtrain)与f(D)的概率分布非常不符合，那么我们就认为Dtrain不是从中生成的样本。当然，数据集性质f的选择有很多中。法是令f为数据集的经验 log 损失EDloss(: )。然后我们计算从抽取出的样本集D的期望经验损失，并这两者之间是否有出入。需要注意的熵很容易的的是，最后一个表的期望值就是的熵，我们在 8.

38、4 节极少过，计算。为了使得这个比较更有意义，我们还需考虑 log 损失的断尾分布，这个要更复杂一些。，我们可以用 M 的函数计算 log 损失的方差来近似这个结果。此外，由于从中抽取样本非常简单，所以我们可以生成多个大小为 M 的数据集 D 来估计EDloss(: )的概率分布。Box16.B概念：PAC-界。 如上所述，给定一个目标损失函数的话，我们可以估计在训练集Dtrain上的经验风险。，由于过拟合的，我们学习到的模型在训练集上的表现可能并不能代表其在未知数据集上的表现。，从理论上来说这两者之间还是有的，所以如果一个模型的训练损失很小的话，那么期望损失也应该很小。在证明这个结论之前，我

39、们首先要明确：根据得到的数据集，我们无法保证所学习到的模型的质量。因为数据集D是从P中随机抽取的，所以就有可能在“点儿背”的时候抽取到一个不具代表性的数据集，也即是说该数据集不像是正常情况下从P抽取出来的。比如，我们可能会抽取出一个所有取值都一样的样本的。显然，根据这个样本集我们学习不出有用的参数来（当然，假设P并不是的）。得到这样数据集的概率非常低，但却不是不可能。因此，我们的分析过程必须要将代表性极不强的数据集考虑在内，这时根据这个数据集我们学习到的模型就 比我们对模型的期望表现不好了（当然，我们学习到的模型可能在训练集上的表现还是很好的）。现在我们要证明的是，我们的学习过程是依概率近似正

40、确的：也即是说，对于大部分训练集D，学习算法得到的模型的误差都是很低的。具体一点来说，假设我们用学习所得模型与真实概率分布的相对熵来作为损失函数。令P 是从P抽取出的 M 个同分布的数据集D的概M率分布。现在假设给定一个数据集D之后，我们的学习明：L返回了一个模型L(D) 。我们要证令 > 0为近似参数， > 0为置信参数。那么如果M足够大的话，我们可得这也即是说，如果M足够大的话，对于从P抽取出的大多数大小为M数据集D，根据这个数据集使用我们学习 得到的模型可以与P很相近。到达这个界所需的样本个数M叫做样本复杂度。这个结论叫做 PAC 界。需要注意的是，仅当我们的假设空间中包含一

41、个模型能够正确表示P的情况下，这个界才。 ，大多数情况下，我们不能保证我们学习的假设空间能够正确表示P。这时，我们就不能指望学习到的模型与P的相对熵很低。因此我们最多指望从我们的学习假设空间中找到一个模型的误差比该假设空间所能达到最小误差再差。与假设空间所能达到的最小误差之间的差距叫做溢出风险。17.6.2.2 节了这个广义节的例子。101.3.2判别式学习与产生式学习在上一小节的讨论中，我们实际上隐含的假设我们的学习目的是使得学习到的模型 是对P的一个好的近似。，如 16.2.2 节所述，我们通常事先就知道我们的模型是用于特殊𝐘。上一小节的训练策略旨在使得 与整个任务的，比如

42、根据𝐗概率分布P(𝐗, 𝐘)是相似的。这类训练目标叫做产生式学习，因为我们训练出来的模型可以产生所有变量的样本，既变量，也用于的特征。另式是判别式的训练模型，这时我们的目的是令P(𝐘|𝐗)与P(𝐘|𝐗)足够接近。同一个系统中产生的同样的数据，我们可以按照这两种不同的方式进行训练，最终会得到不同的结果。案例 16.1我们举一个最简单的例子，假设有一个“星”型的结构，其中有一个目标变量𝑌，该变量与特征集𝑋1, . , 𝑋𝑛中

43、的每个特征都有边相连。如果我们产生式的训练这个模型，那么我们实际上就是在学习一个朴素模型，又由于这个是单连通的，所以他与朴素模型是等价的。相反，如果我们判别式的训练同样的结构的话，那么我们就能得到𝑃(𝑌|𝑋1, . , 𝑋𝑛)的一个很好的近似。这时，如案例 4.20，我们实际上学习的是给定𝑌父节点取值条件下𝑌的 logistic 回归模型。需要注意的是，用产生式训练出的模型也可用于具体的任务。比如，我们通常产生式的训练朴素模型，最后使用这个模型进行分类，如果我们任务P(⻏

44、2;|𝐗)判别式的训练模型的话，那么我们并不能得到关于𝐗的概率分布，因此这种训练方式得到的模型不能对𝐗进行推断，下结论。判别式训练可用于任意模型的训练。它却不太适用于的训练，因为这种训练实际上改变了参数在最终模型中的含义。比如，如果我们对（有向）朴素模型应用判别式学习的话，我们就会像案例 16.1 一样得到一个同样的 logistic 回归模型，只不过Y与每个Xi之间的势函数被局部归一化为一个看起来像条件概率分布的因子。而且判别式学习无法利用的结构进行学习。因此，判别式学习通常适用于无向模型。这时，我们实际上是在训练一个条件随机场，如 4.6.1

45、 节：表示条件概率分布P(𝐘|𝐗)的模型。产生式训练与判别式训练在统计和计算复杂度上各有千秋，到底使用哪一种训练方式人们也是各执一词。现在我们就列举一些这两种的优缺点。一般来说，产生式模型的偏差要更高一些因为它对概率分布的形式做了的假设。首先，这种学习对特征变量𝐗的做了假设，而判别式学习只对𝐘的概率分布做了假设。从一方面来说，产生式模型定义了P(𝐘, 𝐗)的形式，因此它实际上是对P(𝐘|𝐗)和P(𝐘) 都做了假设。为了与P的拟合度很好，我们必须要调整我

46、们的模型即对P(𝐘|𝐗)拟合的很好， 还要对P(𝐗)拟合的很好。相反，判别式模型的目的只对P(𝐘|𝐗)拟合的很好即可，而不用习的模型必须对P(𝐘)拟合的很好。产生式这个额外的偏差既好也不好。一方面来说，它能够帮助学习算法正则和约束最终学习到的模型，从而减少对数据的过拟合。因此，对于有限的数据，产生式训练的效果通常要更好一些。，如果对假设空间施加的约束是错误的话，那么实际上就了学习算法找到正确的模型（或更好的模型）。在实际应用中，我们对模型假设空间所作的约束通常是不适用于真实的概率分布P的。对于有的数

47、据，这些约束可能会减少过拟合的发生，从而使得模型有更好的推广性。，随着训练数据的增加，由于这个约束而引入的偏差实际上盖过了我们学习得到模型的误差。而由于判别式模型做的假设要更少一些，因此它受到不正确模型假设的影响要更小一些，因此在大数据集上的表现要比产生式要好一些。案例 16.2以字符识别为例从手写图像中识别出字符来。这里目标变量是字符（比如 A）。显然，我们可以使用单个像素作为特征变量𝑋1, . , 𝑋𝑛。然后我们既可以使用产生式训练得到一个朴素模型或使用判别式学习得到一个 logistic 回归模型。朴素（夫）模型要分别训练在给定 26 个类

48、别情况下的，256 个像素值的概率分布；由于每的维数还是很低的。相反，判别式模型要同时个概率分布都是训练的，所以这个估计11最优化多项式 logit 概率分布中的 26×256 个参数，这是一个维数相对高很多的估计。因此，如果训练数据很少的话，那么朴素的效果通常会更好一些。，即便对于这个简单的，朴素模型做出的假设（给定图像类别条件下像算成了之间是间是的）也显然是错误的。因此，朴素模型可能将实际上相关的特征计的特征，从而就使得最终得到的估计是错误的。而判别式模型却没有假设这些特征的；它同时拟合所有的参数，从就可以弥补特征之间的冗余和其他管理。因此，如果我们有足够多的数据的话，那么判别式

49、学习的效果会更好一些。判别式模型的一个优点在于它可以利用丰富的特征集合，而且这些特征之间显然是不的。这些丰富的特征通常能够提高分类的准确度。案例 16.3继续分析上一个例子，像素值并不是用于图像分类的好特征。计算机视觉和图像处理的研究工作者做了大量工作，得到了关于图像的许多特征集合，比如给第像素的梯度，某一块图像经过滤器计算之后的值，以及其他许多更细小的特征。一般来说，利用这些特征要比比仅使用像素值的分类效果要好，这些特征都与多个像素的值相关，并且同一个像素的值可能会用于不同特征的计算。因此这些特征之间不可能是的，因此如果将这些特征应用于朴素分类器的话就可能得到很差的结果。在 logistic

50、 模型或其他判别式分类其中则不需要考虑这些特征之间的相关。，产生式模型有它本身的优势。产生式模型通常可以给出一个系统更自然的解释。并且，产生式模型能够处理整数据或未标注数据。因此，具体选择产生式模型还是判别式模型与我们的具体应用相关，通常情况下将不同训练策略结合起来可能是最好的选择。1.4学习任务现在我们详细一下不同的学习。抽象的说，一个学习算法的输入为：一些先验知识或对 的约束训练集D = 𝐝1, , 𝐝M，这些数据是从P抽取的ll同分布样本。学习算法的输出是一个模型 ，该模型包含图结构、参数、或既包含图结构又包含参数。这个抽象的学习有许多不同的具体变种；大体

51、上来说，这些变种主要在面有差别，其中两方面是关于算法的输入，另一方面是关于算法的输出。首先，学习最终的输出肯定是相关的（也即是我们要学习的图模型的类型）：是的形式化与我们还是。另两方面是关于学习算法的输入。其中关于算法输入的第一方面区别是我们给 的约束程度有多大，另一方面是我们的训练集是否是完全可观测的。下面我们分别这些不同之的计算复杂处。然后我们从这度。面对不同的学习进行分类，并且分析一下这些学习1.4.1模型约束第一个是学习算法的输入对假设空间做了多么大的约束，所谓假设空间就是我们运行算法考虑可以作为学习算法输出的模型。这个假设空间有无穷多个，因为我们可以对模型的结构或参数做各种各样的限制

52、。下面列举出一些关键点：l一种情况是，我们限定一个图结构；学习算法只需要学习（某些）参数即可；需要注意的是，我们通常并不假设我们限定的这个图结构就是正确的图模型𝒦我们可能不知道图结构，所以我们要根据训练数据将图结构和参数都学习出来更糟糕的情况是，我们甚至不知道真实概率分布P涉及到了那些变量。换句话说，我ll们只能观测到系统中一部分变量的取值，而其它变量是否却不知道。我们已知的先验知识越少，假设空间就越大，因此我们在选择模型时就要格外注意。如16.3.1 节所述，根据假设空间的复杂度可以做一些重要的权衡。首先，从统计学上来说，12如果我们对假设空间的限制太多，那么我们就无法表示真正的概率分布P。相反，如果我们对假设空间不做限制，那么就可能得到一个偶然在训练集上得分很高却对P拟合很差的模型。其次，从计算复杂度上来说：许多情况下（尽管不是绝对），假设空间越大，那么搜索高分模型的难度也就越大。1.4.2数据的可观测性算法输入的第二方面区别是训练集的可观测程度。这里有多种情况：l数据是完整的，或完全可观测的，因此我们训练集中的每个样本dm都是所有变量𝒳的一个取值。l数据是整的，或部分可观测的，因此训练集中的每个样本中，某些变量的取值是未知的数据中包含隐变量，这些隐变量的取值l出现在任意一个样本中。这种情况与𝒳内有哪些