An Introduction to Conditional Random Fields

结构化预测方法本质上是将分类和图模型结合一起，结合了图模型对多元数据进行紧凑建模的能力，以及分类方法使用大量的输入特征的预测能力。

Introduction

对于多变量预测的问题，一种方法是把每个位置的输出看成是独立的，但是问题是输出之间其实是有着复杂的依赖关系。例如，临近的文档和区域更倾向于有着相同的labels.

一种自然的方法用来表示输出变量相互依赖的方式是使用图模型。概率图模型，包括贝叶斯网络，神经网络，因子图，马尔科夫随机场等模型族在内的图形模型代表了许多变量的复杂分布。然后可以得到对于给定的概率密度因子分解，得到一组满足分布的特定的条件独立关系。

已经有很多使用概率图模型的工作，尤其是在统计自然语言处理上，一直都在聚焦于generative模型，能够明确的从输入中得到一个联合概率密度$p(y, x)$.生成模型也有限制，如果x的维度非常大，或者特征之间有着复杂的依赖关系，那么生成模型会很难得到联合概率密度。建模输入之间的依赖关系可能会导致难以处理的模型，但忽略它们会导致性能下降。

一种解决的方法是直接对条件概率$p(y|x)$建模，这是分类任务需要的。这就是条件随机场（CRF）。

CRFs本质上将分类和图模型的优点结合起来，将图模型的多元数据紧凑建模的能力和利用大量输入特征进行预测的能力结合起来。

条件模型（判别模型）的优点是仅仅设计x中变量的依赖关系在条件概率中补气作用，因此精确得到条件概率要比联合概率简单得多。因此，生成模型和CRFs的差异和朴素贝叶斯网络和逻辑回归之间的差异完全一样。实际上，多项的Logistics回归模型可以被看作是最简单的一种CRF，其中只有一个输出变量。

这个教程主要是使用CRF描述建模，推断和参数估计。首先是描述crf的建模问题，包括线性链的CRF，具有一般图结构的CRF以及包含潜在变量的隐藏CRF。
我们描述CRF如何看做是逻辑回归过程的一般化，以及和马尔科夫模型的区别。

在第三章，描述推断，第四章描述学习。最后，讨论CRFs和其他的模型，包括其他结构预测方法，神经网络和最大熵马尔科夫模型。

Modeling

从建模的角度上描述CRF，解释CRF如何将结构化输出表示为一个具有高维输入向量的函数。CRFs可以理解为逻辑回归分类器对任意图结构的拓展，也可以理解为结构化数据生成模型的判别模拟

图模型

图模型在多变量概率分布的表示和推断上是一个强大的框架。
多变量分布的表示的代价会非常大。比如一个n个二元变量的联合概率需要$O(2^n)$浮点数存储。
图模型的解决方法是，在很多变量的表示可以看作是局部函数的乘积，每个局部函数都依赖于更小的变量子集。这种分解结果和变量之间的条件独立关系密切相关——这两种信息都可以很容易的被图表示出来。
实际上，因式分解，条件独立性和图结构之间的这种关系包含了图模型框架的许多功能：条件独立观点对设计模型游泳，分解观点对设计推理算法有用。

无向图

待续。。