无向图模型(马尔科夫随机场).docx

19 无向图模型（马尔科夫随机场）19.1 介绍在第十章,我们讨论了图形化模型(dgms),通常称为贝叶斯网。然而,对于某些域,需要选择一个方向的边即(dgm), 例如,考虑建模一个图像。我们可能会假设相邻像素的强度值是相关的。我们可以创建一个dag模型的2d拓扑如图19.1所示。这就是所谓的因果mrf或马尔可夫网。然而,它的条件独立性通常不好。 另一种方法是使用anundirected图形化模型(ugm),也称为马尔可夫随机场(mrf)或马尔可夫网络。这些不需要我们指定边缘方向,在处理一些问题,如图像分析和空间统计数据时显得更自然。例如,一个无向二维点阵显示（如图19.1(b)）；现在每个节点的马尔科夫blanket只是最近邻节点,正如我们在19.2节所示的那样。粗略地讲,在建立在dgms上的ugms的主要优点是:(1)它们是对称的,因此对某些领域更“自然”,如空间或关系数据；(2)discriminativel ugms(又名条件随机域,或crfs),它定义了条件概率密度p(y|x),要比discriminativel ugms更好，我们在19.6.1节中解释原因。相比于dgms，ugms的主要缺点是:(1)参数是可很难解释及模块化程度较差,我们在19.3节解释原因;(2)参数估计计算代价更高,原因我们在19.5节解释。19.2 ugms的条件独立性19.2.1ugms通过简单的图分离定义ci关系如下：对于节点集的a,b,c,我们说xag xb | xc,如果从在图g中把a从b中分离出来。这意味着，当我们删除所有c中的节,如果在a上没有任何连接的路径到b，那么ci 属性holds。这就是所谓的ugms的全局马尔可夫性质。例如,在图19.2(b),有 1,2 6、7 | 3、4、5 。图19.1节点的节点集呈现t有条件地独立于所有其他节点图为t的马尔科夫blanket;我们将表示通过mb(t)。正式,马尔可夫全面满足以下属性节点的集合呈现一个节点t条件独立于所有图中的其他节点被称为t的马尔可夫blanket;我们将通过mb（t）表示这一点。从形式上看，马尔科夫blanket满足以下的特性：其中是结点t的闭节点。可以证明，在一个ugm中，一个节点的马尔科夫blanket是其集近邻的节点。这就是所谓的无向本地马尔科夫属性。例如，在图19.2（b）中，有。从局部马尔可夫属性，我们可以很容易地看到，两个节点是条件独立给出的其余部分，如果它们之间没有直接相连。这就是所谓的马氏pairwise属性。符号上表示为: 使用三马尔可夫特性我们已经讨论过，我们可以从ugm得出以下的ci特性（其中包括）很明显，全局马尔可夫给出了局部成对的这些马氏节点。这是不太明显的，但尽管如此真实（假定对于所有的x ，p（x） 0，即，p是一个正密度），pairwise意味着全局性的，因此，所有这些马尔可夫性质是相同的，如图图19.3（参考koller and friedman 2009, p119的证明）。这一结果的重要性在于，它通常更容易根据经验评估pairwise条件独立性; 这种成对的ci声明可以用来构建一个从全局ci中提取出来的图。 19.2.2 从无向到d-separation我们已经看到，检查 ci关系，在ugms中要比dgms容易得多，因为我们不必担心边的方向性。在本节中，我们将展示如何在有向图中使用ugm检查ci关系。人们很容易通过删除边简单地将有向图转化为无向图，但是这显然是不正确的，因为v型结构abc相比于无向图中v型结构a-b-c有很不同的ci属性。后者不正确地给出了ac | b。为了避免这种不正确的形式，我们可以在未连接的a和c之间添加边，然后从边上画箭头，成形无向全连通图。这个过程被称为规范化(moralization)。图19.2（b）给出了例子。我们互连2和3，因为它们具有共同的子节点5，我们互连4，5和6，因为它们具有共同的子节点7。不幸的是，教化失去了一些ci信息，因此我们不能使用规范化的ugm去检测dgm的ci属性。例如，在图19.2（a）中，使用 d-分离，我们看到45|2添加标准化弧4 - 5将失去这一性质（见图19.2（b）。但是，请注意4-5的边，这表明可以用以下的方法来确定，如果ab | c。首先，我们形成dag图u= abc。这意味着我们删除图中不在u中的所有节点或者不是u的祖先节点。那么我们这个标准化原图，并应用了简单的分离规则ugms。例如，在图19.4（a）中，我们显示了原始图，图19.2（a）使用u=2，4,5。在图19.4（b）中，我们将展示这个图表的moralization版本。很明显我们现在可以正确地得出结论，45|2。19.2.3 比较有向和无向图模型哪种图有更强的“表现力”，有向图或无向图？正式搞清这个问题，回忆 我们说g是一个i-map，概率分布为p，如果有i（g）i（p）的话。如果i（g）= i（p），则g是i-map的一个完美的映射，换言之，该图可以代表所有的（也是唯一的）的ci 分布的特性。事实证明，dgms和ugms是不同分布集上完美的map（见图19.5）。在这个意义上，两者都不是比谁更有强大的表示能力。 作为能够由dgm完美地模拟一些ci的关系的一个例子，考虑v结构a c b，预示着a b , 且a b | c，去掉箭头有a c b , a b | c 且 a b。事实上，没有一种ugm可以精确代表所有只由一个v型结构编码的两个ci statement。在一般情况下，ci的属性在ugms是单调的，如果a b | c , 则 a b | ( c d )，但在dgms，ci的属性可以是非单调的，通过变量调节可以消除条件独立。作为能够完美地模拟由一个ugm ci的关系的一个例子，考虑图19.6所示的4个周期，正确表示了a c | b,d，然而b d | a又是不正确的，图19.6（c）是a c | b,d另外一种错误情况， b d。一些分布可以由dgm或ugm完美模拟;产生的图形被称为decomposable 或者叫弦。粗略的说，这意味着：如每个最大团所有的变量坍塌，使“mega变量”，由此产生的图形将是一棵树。当然，如果图形已经是一个树（包括比较特殊的“链”），这将是弦。参见20.4.1节的细节。19.3 mrfs参数化19.3.1 hammersley-cliford理论由于是无向图没有相关的拓扑排序，我们不能用链式法则来表示p（y）。所以，联想势函数sor因子s与图中的每一个极大团。我们给出势函数。一个潜在的函数是一个参数为非负的函数。可以证明任何正向分布，其ci的属性可以通过一个ugm表示。定理 19.3.1（hammersley-clifford），一个正向分布p(y) 0满足无向图g的ci属性，如果p能被一个最大团因子所表示。其中c是图中所有最大团的集合，z ( )是分割函数，分割函数确保所有分布和为1（证明未给）如果p满足ci属性，于是p可以写作如下形式：其中，ugms和统计物理之间的深刻联系。特别是，有一个被称为吉布斯分布的模型，该模型可以写成如下：是与团块c中的变量相关的能量，通过定义一下公式能够转换为ugms图：我们看到，高概率状态对应于低能量配置。这种形式的模型被称为以能量为基础的模型，并且通常用在物理学和生物化学以及机器学习的一些分支上。注意，我们可以自由地参数化到图形的边，而不是最大小集团。这就是所谓的成对mrf。19.3.2 势函数的表示如果变量是离散的，我们能够用一张表格（非负值）来表示势函数，然而，这并不是概率，通过以下例子来看一下.通常用log函数来定义势函数：是的特征向量，log概率如下的形式：这就是著名的最大熵或者叫线性log模型例如，考虑mrf对，我们关联一个长度为k2的特征向量：每一个特征值都有一个权重，我们将其转化为k x k的势函数形式：所以我们看到，我们可以用对数线性形式很容易地表格化表示势。为了说明为什么这是有用的，假设我们有兴趣做英文的概率模型拼写。由于某些字母组合在一起会发生相当频繁（比如，“ing”），我们将需要更高阶的因子捕捉到这一点。假设我们限制自己的trigrams。一张表格潜力仍然有个参数。另一种方法是定义一个寻找某些“特殊”的三元组指示器的功能， 如“ing”，“qu- ”等，那么我们可以在每个trigrams下定义势：定义任意长度一个单词的概率：由此产生的一个问题是特征函数来自哪里，在许多应用中，它们是由手工创建，以反映领域知识（我们会看到后面的例子），但它也可以从数据学习他们，正如我们在19.5.6节讨论的那样。19.4 mrfs的一些例子一些通过ugms表示的例子19.4.1伊辛模型伊辛模型是mrf在统计物理学上的一个例子，通常用在描述磁力性质的模型上，给定ys 1, +1，代表一个原子的自旋，这可以被旋转向下或向上。在一些磁铁，称为铁磁体，相邻的自旋倾向排列在相同的方向，而在其他类型的磁体上，称为反铁磁体，自旋和周围原子不同。 我们可以按如下这个模型作为磁流变。在一个二维或三维晶格的形式创建的曲线图，并连接相邻的变量，如在图19.1（b）所示。然后，我们定义以下两两团块的势：这里是节点s和t之间的耦合强度。如果两个节点不连接图中，我们设置。我们假设权重矩阵w是对称的，所以。 通常我们假设所有的边有相同的强度，所以的（假设）。如果权值是正的，相邻原子的旋转貌似有相同的状态，这可以被用来建模铁磁体，并且是一个关联马尔可夫网络的一个例子。如果权重是非常大，相应的概率分布将有两种模式，相应于所有的+1状态和全1的状态。这些被称为系统的基态。如果所有的权重为负，j0相邻节点有相同的标签。从图19.8中可以看到对于j 1.44，很多大的聚集产生，j及ing，其中 表示单词的结束，并用于各种正则表达式，如0-9等。一些模型中的样本有1000个特征，通过gibbs采样，结果如下：特征学习的这种方法可以被认为是作为图模型结构的学习形式，它具有更细粒度：我们添加的特征是有用的，不管所得到的图形结构。然而，所得到的曲线可以成为稠密的连接，参数估计更加顽固。19.5.7迭代比例拟合(ipf)如下log形式的公式与相似，特征向量只指示了功能属性。从公式可以看到最大似然估计实证期望的特征等于该模型的期望其中pemp是实证期望，对于一般的图，必须保持在最佳的条件是对于图的一个特殊的部分称为分解图，用表示。然而，即使该图是不可分解，就可以想象试图执行这个条件。这表明了一个迭代的坐标上升方案。迭代的每一步是我们计算给出的。这被称为迭代比例拟合或ipf，算法原理如下： 示例一个简单的例子/wiki/iterative_proportional_fitting，有两个二进制变量y1和y2，如果一个男人n为左撇子，yn1=1，否则yn1=0，如果一个女人n是左撇子yn2=1否则yn2=0假设我们要以拟合一个包含的节点y1和y2的断开连接的图模型，它们之间没有边，需要找到向量和 ，其中m是模型期望数，c是实证数，通过矩匹配，我们发现，该模型的行和列的总和必须完全匹配数据的行和列。一个可行的方案是使以及，下表显示了模型的预测，这些方法可以推广到任意图中。 ipf的速度ipf是一个固定点算法，执行可以保证收敛到全局最优，迭代次数取决于模型，如果图形是可分解的，然后ipf收敛于单次迭代，但在一般情况下，ipf可能需要多次迭代，很显然，ipf的主要计算代价是模型的边界，eicient和连接树算法都可以使用，因此有一种叫eicient ipf。然而，坐标下降可能会很慢。另一种方法是更新所有的参数后，通过以下简单的可能的梯度，这种方法拥有适用于模型的显著优势。所在团块的势可以不完全参数化，即功能可能不包括所有可能的指标。从而产生被称为迭代缩放的方法。在实践中的梯度法更快。 ipf功能概括我们可以用ipf适应高斯图模型，也可以创建 贝叶斯算法的ipf。 ipf可分解的图模型有一个无向图模型的簇系称为可分解的图模型，在后面章节中有定义，其基本的思想是像树一样的图，这样的图可以通过ugms或dgms无损表示，不会丢失信息。在分解图模型的情况下，ipf通过迭代收敛。高斯势，有通过利用共轭先验，我们也可以很容易地计算分解后的参数后验估计。就像在dgm中的情况一样。19.6 条件随机场（crfs）条件随机场有时是一个可以区分的场：crfs可以被看作是逻辑回归的结构化输出扩展。我们通常会设的势函数的对数线性表示形式：其中是特征向量，从全局输入x中分离出来，yc是标签集合，我们将举一些例子使得这个符号更清晰。建立在mrf上的crf类似于一个分类器，我们将精力放在模型本身上，关心的是给定数据的标签的分布crfs另外的一个重要的优势是能够构建基于数据的势，例如在图像处理应用中，我们可能会“turn off”两个相邻节点s和t之间的平滑标签是否存在于所观察到的不连续像素s和t之间的图像强度。在自然语言处理的问题上，我们可以使潜伏的标签取决于句子的全局属性。crfs的缺点是训练数据必须要有标签，而且训练过程非常慢。19.6.1 crfs的链式结构，memms及其标签偏置问题使用最广泛的一种crfs用链式结构图来表示相邻节点间的关系，如下图所示：传统的隐马尔可夫模型用来解决这类问题，对于所有的t，如果观察到xt和yt，可以非常容易的去训练这样的模型，一个hmm模型需要指定一个生成观测模型，这非常困难，进一步而言，每一个xt需要局部化，因为它是难以定义为观测值的整个流的生成模型。使用“reverse the arrows”从yt到xt可以使得hmm模型可分，通过下列公式定义有向可分模型其中，是全局特征值xt是指派给节点t的特征，这称之为最大熵马尔科夫模型，或memms，一个memm仅仅是一个马尔可夫链中在输入特征上的状态转移概率，这似乎是logistic回归在结构化输出设置上的自然推广。但是有一个微妙的标签偏置问题，问题是，在时间t的局部特征不影响状态之前的时间t，在此之前，通过检查dag，这表明xt是从yt-1中d-separated的，这是一个隐节点，从而阻断信息流。要理解在实践中是什么意思，考虑词性（pos）标注任务。假设我们看到“bank”这个词，这可能是一个动词（如在“他把钱存入boa银行”）或名词（如在“河岸被溢出”）。单词的词性是模糊的。假设在句子后面，我们看到“fishing”这个词,这给了我们足够的上下文来推断“bank”的意义是“河岸”, 然而，在一个memm中，“fishing”的证据不会倒流，所以我们将无法消除歧义。现在考虑，crf链式模型，如下：从图如图19.14（c）中，我们看到，在标签的偏置问题不再存在，由于yt没有阻断信息从xt流到yt中。发生在memms标签偏差问题，因为有向模型局部归一化，这意味着每个cpd总和为1。相比之下mrfs 和 crfs是全局归一化，这表示局部因素不需要总和为1，因为该分区函数z，它总结了所有的连接结构，将确保该模型定义了一个有效的分布。19.6.2 crfs应用crfs可以被用来解决很多有趣的问题，我们在下面提供具有代表性的示例，技术细节在第20章讨论。 手写识别对如图19.15手写数字字符串进行分类，关键观察到的本地字符可能是模糊的，但通过取决于相邻（未知）标签，它有可能使用上下文来降低错误率。该节点一个势函数是,通常扮演一个基于概率的分类器。名词组一个普通的nlp任务是名词短语分块，指分割的任务是将句子翻译成其独特的名词短语，这样一个简单的技术称为浅层分析，更详细地说，我们在句子中使用b标记的每个单词的开始，i表示np内部，o表示np的外部，称为bio标注，如下示例：一个标准的方法对这个问题会先转换文字的字符串到另一个pos标注的字符串再将pos标签的字符串转换为词性标记的bios字符串。然而，这样的管道的方法可以传播错误。更可靠的方法是建立的联合概率模型，使用图19.16的crf来完成，相邻的标签之间的连接进行编码的bi之间的转移概率，并能强制约束，b必须处理i。特点是通常开头的字母为大写。特征值的数量对推断时间的影响最小，因为该特征是观察到的，不需要进行求和。评价多个特征值的势函数，但是这通常是可以忽略不计;如果不是，人们可以规范化不相关的特征，但是，图结构在推理时有戏剧性的效果。图19.16的模型是易于处理的。因为它本质上是一个“胖链”，所以我们可以使用向前向后算法，其中| pos|是pos标签的数量，并且| np |是np标签的数量。如图19.17，下面将要说明的是其难以计算。命名实体识别关系到np组块任务被命名实体提取。而不是仅仅的分割出名词短语，我们可以分割出的短语做与人的位置。类似技术用于自动从您的电子邮件填充你的日历;这是所谓的信息提取。一个简单的方法是使用一个链状结构的crf，但是扩大状态空间bio to b-per, i-per, b-loc, i-loc, 和其它情况，然而，有时一个词是一个字是一个人，位置，还是其他什么东西是模糊的，专用名词特别难处理，而且往往这类词数量巨大，考虑单词之间的长程关联的性能。例如，我们可能会添加相同的字的所有匹配之间的链接，并迫使字具有相同的标记发生。我们可以看到，图中结构本身的变化取决于输入，这是crfs另外的一个优点，不幸的是，推断在该模型一般比简单的链和本地链代价更高。理由见20.5节。 自然语言处理链结构模型在语言处理上的推广是利用概率语法。具体而言，概率上下文无关文法或pcfg是一套重新编写或产生的形式规则。其中 是非终止词，是终止词，举例，每一个这样的规则都有一个关联的可能性。由此产生的模型定义了一个概率分布字数序列。我们可以计算观察的特定序列的概率通过计算所有生成树的总和。时间复杂度是o(t3)。pcfgs是生成模型。它有可能使判别版本。给定一个序列，使用条件随机域，例如，定义用来统计每个生成规则的数量。 层次分类假设我们正在执行多类分类，在这里我们有一个标签分类，这组类成层次结构，我们可以通过这个层次结构中的编码和y的位置定义一个二元向量，在这里我们打开位分量y和其所有的孩子。这可以通过输入特征组合，利用张量积。这个方法被广泛地用于文本分类，其中手动构造taxnomies （如开放式目录项目）相当普遍。的好处是信息可以在参数为附近的类别之间共享，从而实现泛化跨类。 蛋白质side-chain 预测一个有趣的模拟预测蛋白质侧链结构的分析（实验）。其中的每个残基侧链有4个二面角角度,通常离散成3值称为rotamers。 我们的目标是预测这种离散序列的角度,y,离散序列的氨基酸,x。定义能量函数e(x,y)，这种能量通常定义为各部分能量的加权和，。模型中，我们可以计算最可能的侧链配置使用，总的来说，这是一个np难的问题，因为变量之间大范围关联。然而,一些特殊情况可以有效获得处理,方法在22.6节讨论。 立体视觉low-level视觉问题的输入是一幅图像(或一组图像)，输出是一个特定的图像处理。在这种情况下,通常使用二维网格结构模型。这个模型和图19.9相似，只不过特征是全局的，我们将假设一个crf pairwise。经典的low-level视觉问题是“密集的立体重建”,我们的目标是估计每个像素的深度，一个简单的crf骨架模型可以用来解决这个任务。通过一些基本的处理技术，在左边这幅图像素位置以及右方图位置，深度估计转化为估算问题。我们通常假设相应的像素强度相似,所以我们定义一个本地节点形式：其中，xl是左图，xr是右图。该等式可以对一个小窗口上每个位置的密度经行建模。在高纹理区，通过交叉相关性可以找到对应的斑点，但在低纹理区的正确性通常是模糊的。在mrf边上加入高斯先验，假设相邻节点的差异不大，有如下式子：一个更好的高斯势函数形式是：为期望的平滑度，为最大惩罚系数。这将增加差异的显著性。称为不联系保留势。注意这样的惩罚不是凸的。图19.20展示了两种不同先验形式。在左上角是一幅产生自middlebury stereo benchmark数据集的图像，左下方是相应的差异值。其余列代表估计视差（见22.2节），其中的“infinite”指的是收敛结果。最上面一行显示使用高斯边缘潜在的结果，下面一行显示结果截断的势。后者显然更好。不幸的是，执行推理与实际值的变量的计算非常困难，除非是联合高斯模型。它是常见的离散变量（图19.20 使用了50个状态）。边际势函数按照19.69的公式给出，由此产生的模型被称为一个metric crf。在metric crfs中更有效，在crfs中离散的标签无序，更多细节请参考计算视觉相关内容。19.6.3 训练crfs我们可以修改基于mrfs优化模型的梯度像19.5.1节描述的那样，对于crfs使用前向算法，特别是大规模的对数似然变成如下形式：梯度变为请注意，我们现在必须为特定训练下每个梯度步进进行推断，时间复杂度为o(n)，低于mrf，这是因为分类函数基于输入xi。 在大多数crfs应用场合和某些mrfs场合下，图的结构尺寸可以改变。因此，我们需要使用参数将确保我们可以定义一个任意分布的大小。在pairwise的情况下，我们可以写如下模型其中是节点边缘参数该式为总节点和边缘特征。梯度表达式很容易修改以处理此种情况。在实践中，它是利用先验/正规化，防止过拟合很重要。如果我们用一个高斯先验，新的目标函数是成为修正梯度表达式很简单另外，我们使用规则化，例如：在边界权值上使用学习稀疏图结构，权值为的节点上使用，目标函数变为：不幸的是，该优化算法比较复杂时，我们使用，尽管问题仍然比较复杂。为了处理大型数据集，我们可以使用随机梯度下降，在8.5.2中有描述。定义具有隐变量的crfs是可以的也是非常有用的，例如：对齐隐藏标签的一系列可见特征值。这种情况下目标函数不再复杂。然而，我们可以找到一个局部最优的ml或map的估计参数，使用em或梯度算法。19.7 结构化支持向量机我们已经看到，训练crf需要推理，为了计算统计期望需要评估梯度。对于某些模型，计算一个联合的map估计状态比计算边缘简单，在22.6中我们将讨论一种方法来训练输出分类器。这种方法就是我们所知道的结构化支持向量机ssvms。19.7.1 ssvms：概率视图在这本书里面，我们最关注的是使用map参数估计的拟合模型，最小化函数形式如下：我们选择的标签，以减少后的损失期望其中是引入的损失，是估计值和真是值的差值，因此，参数估计时使用损失函数似乎是合理的，因此，下面我们在训练集上替换最小化先验损失期望。特殊情况下0-1损失，这减少到假设能够通过下面的式子描述模型其中，同时定义，重写目标函数如下：我们现在将为了简化这个目标函数考虑各种边界，第一，注意任何边界函数有举例，假设，有我们忽略，它独立于y，作为上下边界，我们看到其中，意思是对于相同常量c1c2有，目标函数在w上并不复杂，我们通过下面的式子约束上下边界：对于任何，在我们早期的例子中应用这个等式及，有如果让有：像我们在ssvm中所使用的方法，与此具有相同的目标。特别地及在下严格递减这是基本的而分类svm我们看到，ssvm准则可以视为优化的一个上界贝叶斯目标，当很大时，边界将会很紧，尽管在y上取最大，不幸的是，过大的像是过拟合，所以这是不可能的，我们将为此努力（通过调整正则化来避免这种情况）。用svm替代的理由，它专注于拟合参数和影响决策边界。这是一个更好的工具，尤其是模型发生错误的时候。19.7.2非概率视图现在给出一个更传统的ssvms（非概率）方法，结果和上面的论述是一样的，下面讨论算法。令，这是预测函数，在训练集上使用这个式子没有损失如果：每一个非线性不等式能用线性不等式替换，总的线性约束如下：注解重写约束条件为了实现零损失，乘以一个解决向量w，最大化边界定义为：通过调整w边界可以任意大，归一化后式子如下：可以写成下无法实现零损失情况下，引入释放限制在结构化输出的情况下，我们不希望平等对待所有约束条件。例如，分割问题上，得到一个位置的错误应该受到惩罚小于得到许多位置错误所受到的惩罚。我们可以定义的边缘是损失比例代替部分通过下式给出下降约束得到一下等价问题经验风险最小化考虑一下上述目标是合理的，回忆6.5中的学习方法，目标是最小化经验风险，通过下式定义注解计算问题以上的目标函数是简单的二次方程，有，这个问题很棘手，因为通常指数级的，这种情况下调整边界方程，有可能减少约束指数数量的一个多项式的数量，根据一个图模型提供的损失函数和特征向量分解，用在m3nets上的方法（taskar et al. 2003）另一种方法是直接使用指数级的qp。这允许使用更一般的损失函数。有几种可能的方法使之可行。一种是利用割平面方法，另一种是利用随机梯度方法。下面分别讨论。19.7.3 割平面方法拟合ssvms这种方法能够处理大多数损失函数，已经在ssvms的结构包里面实现了，这个方法基于割平面凸优化。基本的思路是：我们初始化w且没有约束。在每次迭代中，我们做了以下工作：为每一个例子中我，我们找出“最大违反约束”，如果增广损失边界超过当前值，增加到workset里面，然后找出新的,如图19.21的骨架系统，算法ii给出了伪代码。这个方法之所以有效的关键在于，不仅是多项式限制被添加，指数限制也能满足公差范围。增广损失解码之所以高效的其它原因是能找出“最大约束违反”（算法第5行），计算我们找到一个新的参数集，使用基本的解码算法，如维特比算法(viterbi)对于比较特殊的0-1损失，是最优化最好的解决方案，是次优的解决方案。为了实现整体值在上，对于链式结构的crfs，使用维特比算法解码，第二最优路径不同于第一最优路径，可以通