[白话解析] 用水浒传为例学习条件随机场

2024-02-17 10:11:28

本文将尽量使用易懂的方式，尽可能不涉及数学公式，而是从整体的思路上来看，运用感性直觉的思考来解释条件随机场。并且用水浒传为例学习。并且从名著中找了具体应用场景来帮助大家深入这个概念。

[白话解析] 用水浒传为例学习条件随机场

0x00 摘要

在机器学习过程中，会遇到很多晦涩的概念，相关数学公式很多，大家理解起来很有困难。遇到类似情况，我们应该多从直觉角度入手思考，用类别或者举例来附会，这样往往会有更好的效果。

我在讲解论述过程中给自己的要求是：在生活中或者名著中找一个例子，然后用自己的话语阐述出来。

0x01 HMM 隐马尔可夫

首先还是需要大概介绍下HMM和MEMM，这样才能知道为什么要引入CRF。

其中HMM在前文[白话解析]以水浒传为例学习隐马尔可夫模型中也详细介绍。这里主要讲讲其推导过程和其缺点。

1. HMM 模型

HMM模型中存在两个假设：一是输出观察值之间严格独立，二是状态的转移过程中当前状态只与前一状态有关(一阶马尔可夫模型)。下面我们就讲讲这两个假设是如何应用在推导过程中的。

单样本朴素贝叶斯分类任务中 (其中 x 是观测值，y 是隐藏状态) ：

\[P(y|x)=\frac{P(x|y)*P(y)}{P(x)} \]

扩展到序列化样本分类问题任务中为：

\[P(y_1^n ∣x_1^n)= \frac{P(x_1^n∣y_1^n)∗P(y_1^n)}{P(x_1^n)} \]

其中n表示的是序列的长度，这就是我们计算某个标签序列在序列分类中的概率得分。

我们以词性标注这一序列化分类问题进行后面的讲解。对于一个给定的句子x_i^n=(x_1,x_2,...,x_n)，我们的目的是为其找到一个得分最高的标签序列 (yˆ1,yˆ2,...,yˆn )，则该问题转化为:

\[\hat y_1^n = arg_{y_1^n} \ max \frac{P(x_1^n∣y_1^n)∗P(y_1^n)}{P(x_1^n)} \]

对于同一个句子的标注，分母是相同的，所以该问题可以转化为:

\[\hat y_1^n = arg_{y_1^n} \ max P(x_1^n∣y_1^n)∗P(y_1^n) \]

回忆下联合分布的公式

\[P(X = x \ and \ Y = y) = \ P(Y=y|X=x)P(X=x) = \ P(X=x|Y=y)P(Y=y) \]

所以上述问题转化后的公式就是 P(X,Y)。即 HMM 试图去拟合 X,Y 的联合分布 P(X,Y)，所以它是一种生成式模型。

现在我们需要引入HMM的两个基本假设，才能计算 P：

齐次马尔可夫性假设。即假设隐藏的马尔科夫链在任意时刻 t 的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻t观测无关。
观测独立性假设。即假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他观测及状态无关。

以上这两个假设是 HMM 的核心，之后的公式推导都是依赖这两个假设成立的基础上进行的。

这两个假设分别可以用于计算上。

\[假设1 \ 用于求解 \ 当前状态 \ P(y_1^n) \\ 假设2 \ 用于求解 \ 当前观测值 \ P(x_1^n∣y_1^n) \]

原始情况下，根据有向图模型计算方式：

\[P(y_1^n)=P(y_1)∗P(y_2∣y_1)∗P(y_3∣y_1,y_2)∗...∗P(y_n∣y_1,y_2,...,y_{n−1}) \]

我们先把 假设1 用于求解，则其计算方式变为:

\[P(y_1^n)=P(y_1)∗P(y_2∣y_1)∗P(y_3∣y_2)∗...∗P(y_n∣y_{n−1}) \]

根据 假设2 ，当前观测值仅仅与当前状态有关，与其他时刻状态和观测值无关，所以

\[P(x_1^n∣y_1^n)=P(x_1∣y_1)∗P(x_2∣y_2)∗...∗P(x_n∣y_n) \]

即

假设1 使用bi-gram近似得到转移概率 Transition probability。
假设2 就得到发射概率 emission probability。

最后合并起来：

\[\hat y_1^n = arg \ max_{y_1^n} ∏_{t=1}^nP(x_t∣y_t)∗P(y_t∣y_{t−1}) \]

HMM的学习过程就是在训练集中学习这两个概率矩阵 (大小为 (y, y)，(x, y) )

2. HMM有哪些缺点

HMM 拥有以下几个缺陷：

在很多序列化标注任务中，尤其当不能枚举观测值时，需要用大量的特征来刻画观察序列。如在文本识别中识别一个未见的公司名字时，除了传统的单词识别方法以外，还需要用到很多特征信息，如大写字母、结尾词、词性等信息。也就是，我们需要用特征对观测值进行参数化，而HMM中直接利用观测值本身。
在命名实体识别的任务中，由于实体本身结构所具有的复杂性，利用简单的特征函数往往无法涵盖所有的特性，这时HMM的假设前提使得它无法使用复杂特征(它无法使用多于一个标记的特征)。
在很多自然语言处理任务中，需要解决的问题是在已知观测序列的情况下求解状态序列，HMM采用的生成式的联合概率分布P(x_1^n,y_1n)来求解条件概率P(y_1^n|x_1n)，这种方法不适合处理很多特征描述观测序列的情况。为此MEMM直接采用条件概率模型P(y_1^n|x_1n)。

0x02 MEMM

1. 最大熵模型

其中最大熵模型在前文 [白话解析] 深入浅出最大熵模型以及 [白话解析]用水浒传为例学习最大熵马尔科夫模型中也有介绍。

假设离散随机变量 x 的分布是P(x)，则关于分布P的熵定义为：

\[H(P) = -\sum_xP(x)logP(x) \]

可以看出当 x 服从均匀分布时对应的熵最大，也就是不确定性最高。

给定离散随机变量和上的条件概率分布P(y|x)，定义在条件概率分布上的条件熵为：

\[H(P) = -\sum_{x,y}\hat{P}(x)P(y|x)logP(y|x) \]

其中，p̃(x) 是样本在训练集熵的经验分布，也就是 x 的各个取值在样本中出现的频率统计。

最大熵模型就是，在 "满足事先已约束" 的条件下，学习适合的 P(y|x) ，使得条件熵 H(P) 的取值最大。

我们使用特征函数来表示约束条件，即特征函数也就是用来指示元素是否属于某一个子集。

2. 最大熵马尔科夫模型

最大熵马尔科夫模型把HMM模型和maximum-entropy模型的优点集合成一个产生式模型，这个模型允许状态转移概率依赖于序列中彼此之间非独立的特征上，MEMM是这样的一个概率模型，即在给定的观察状态和前一状态的条件下，出现当前状态的概率。

最大熵马尔科夫模型利用判别式模型的特点，直接对每一个时刻的状态建立一个分类器，然后将所有的分类器的概率值连乘起来。为了实现是对整个序列进行的分类。在每个时刻t时，它的特征不仅来自当前观测值x_t，而且还来自前一状态值y_{t−1} 。所以MEMM中，给定观测序列 i1,...in 后，某个状态序列 in 的条件概率是可以直接学习的。就是

HMM下一个隐藏状态 Y + 1 只是由目前隐藏标签状态 Y 决定。
MEMM下一个隐藏状态 Y + 1 只是由目前隐藏标签状态 Y 和观察状态 X 共同决定。

MEMM的序列标注问题定义为，给定观测序列 x_1^n，求解某个状态序列 y_1^n ，并且使得条件概率最大，而且该条件概率满足马尔科夫假设，也就是条件概率依赖于当前时刻的观察状态和前一时刻的标签状态：

\[P(y_1^n|x_1^n) = \prod_{t=1}^n P(y_t|y_{t-1},x_t) \]

MEMM贪心地取当前时刻概率分布中最大对应的标签作为当前时刻的解码标签。

其中对于前一时刻可能的状态取值y_{t−1} 和当前观测值x_t，当前状态取值y_t 的概率通过最大熵分类器建模为：

\[P(y_t|y_{t-1},x_t) = \frac{1}{Z(x_t,y^t)}exp(\sum_aλ_af_a(x_t,y_{t-1})) \]

其中a, λ_a, f_a 分别表示特征函数数量，特征函数权重和第 a个特征函数，Z() 这部分是归一化。

3. MEMM有哪些缺点

通过上面的公式，你会发现最大熵模型在每一个时刻，针对不同的前一状态y′ 进行归一化操作，这是一种局部的归一化操作，会存在标签偏置问题。即，最大熵马尔科夫模型虽然结合了隐马尔科夫模型和最大熵模型的最大特点，但是仍然忽略了标签之间的约束关系，只求在当前时刻的最大条件概率。

这里有个网上常见的论断：

当前状态是 S1，假设下一个状态 S2 有两个选择，一个是p, 一个是c。经过局部归一化之后，因为p的转出状态比较少，导致 p 的转移概率*发射概率相对于转出状态多的c而言是比较大的，这会使模型更倾向选择状态p。

针对这个论断，我们可以写代码实验下 (如果哪位兄弟知道如何数学论证，还请告诉我，谢谢) 。

# 以下就是MEMM的viterbi算法

def predict_viterbi(x, f_map, tags_s, word_t_map, lib_model):
    """
    For each word in vector x predict his tag. Prediction is done by viterbi algorithm. Check all tags options/globally.
    :param x: X vector of all words to be tagged.
    :param f_map: Features map.
    :param tags_s: Tags set.
    :param word_t_map: Word to tags map.
    :param lib_model: Liblinear model.
    :return: Return best predicted list of tags for each word in x respectively.
    """
    for ind, word in enumerate(x):
        # Calculate for each word best scores/probabilities and best tags for each word.
        for pp_t, p_t in v[ind]:
            for curr_tag in available_tags:
                word_features = extract.generate_word_features(is_rare, p_t, pp_t, word, ind, x)
                features_vec = features_to_vec(word_features, f_map)
                scores = lib_model.predict(features_vec)
                score = np.amax(scores)
                if (p_t, curr_tag) not in max_score or score > max_score[(p_t, curr_tag)]:
                    max_score[(p_t, curr_tag)] = score
                    max_tags[(p_t, curr_tag)] = pp_t

# 预测代码，可以修改这个以测试  
def predict(self, feature_ids):
    weights = self.weights
    scores = np.zeros(len(self.labels))
    for f in feature_ids:
        if f in weights:
            scores += weights[f]
    scores = 1/(1+np.exp(-scores))
    scores = scores/np.sum(scores)
    return scores

#把上述代码修改下，自己传入feature或者直接传入weight就知道了。
#比如分别传入weight 
#[1, 2, 6, 1, 2]
#[1, 2, 9]
#就会发现，如果传入的列表中item的个数越少，则np.amax(scores)越大。

#所以这就与之前的论断相一致：
#经过局部归一化之后，因为 状态 p 的转出状态比较少，导致 “转移概率 x 发射概率” 相对于转出状态多的 状态 c 而言是比较大的，这会使模型倾向于更多的选择 状态 p 。

#其实 S2 选择 p 节点还是 c 节点只取决于 P(p|S1)、P(c|S1)，即只与 “S1” 的上下文有关，与 “S2” 的上下文无关，这就是MEMM产生偏置的一种情况。

因为MEMM有缺点，所以人们引入了CRF。CRFs与最大熵模型的本质区别是：最大熵模型在每个状态都有一个概率模型，在每个状态转移时都要进行归一化。如果某个状态只有一个后续状态，那么该状态到后续状态的跳转概率即为1。这样，不管输入为任何内容，它都向该后续状态跳转。而CRFs是在所有的状态上建立一个统一的概率模型，这样在进行归一化时，即使某个状态只有一个后续状态，它到该后续状态的跳转概率也不会为1，从而解决了“label bias”问题。

0x03 CRF相关知识

1. 什么是场

看到这个概念，估计很多同学会懵圈。这不是物理学概念嘛，我们都学过电场，磁场。怎么这里也出来了一个场。

其实这是从物理学借鉴来的概念，这也不奇怪。比如熵这个概念就是物理学借鉴过来的。这说明数学物理是自然科学的基础。

下面是我从网上或者其他地方找到的关于“场”的解释。希望能对大家理解有帮助。

阐释1

这个论断是一个传媒学者讲艺术表演创作时候提到的。你可以认为她说的不精确，但是不能否认从其他行业的角度来看，反而更容易理解场这个概念。

场就是互相影响。电影表演不需要场。戏剧表演需要场，因为戏剧需要和大量观众互动必须对观众产生影响。

阐释2

这是借用的物理里的概念。理论物理里提出用蒙特卡罗算法求解体系可能结构的方法，每个结构出现的概率和exp(-betaE)成正比，-beta和温度的倒数有关，E是体系每个部分的势能之和，和系统所有可能构型的这个因子之和成反比，这个和就是配分函数，而势函数就是用来计算体系每个部分间不同位置关系下可能的势能的理论假设的函数形式。机器学习就是借用这种模型来产生概率罢了，或者说它是我们要考察的物理量的一个因子，而且这个被考察物理量不仅取值和这个因子有关，其变化规律也和这个因子有关。这是借用的物理里的概念。理论物理里提出用蒙特卡罗算法求解体系可能结构的方法，每个结构出现的概率和exp(-betaE)成正比，-beta和温度的倒数有关，E是体系每个部分的势能之和，和系统所有可能构型的这个因子之和成反比，这个和就是配分函数，而势函数就是用来计算体系每个部分间不同位置关系下可能的势能的理论假设的函数形式。机器学习就是借用这种模型来产生概率罢了，或者说它是我们要考察的物理量的一个因子，而且这个被考察物理量不仅取值和这个因子有关，其变化规律也和这个因子有关。

2. 随机场

随机场是由若干个位置组成的整体，当给每一个位置中按照某种分布随机赋予一个值之后，其全体就叫做随机场。举词性标注的例子：假如我们有一个十个词形成的句子需要做词性标注。这十个词每个词的词性可以在我们已知的词性集合（名词，动词...) 中去选择。当我们为每个词选择完词性后，这就形成了一个随机场。

举梁山为例子：
  
比如梁山好汉一起去聚义厅开会。
每把椅子是一个位置。给每个椅子赋予一个好汉。这个好汉如何分配? 
每次从梁山上各个小团体(三山派，浔阳帮，宋江嫡系......)中随机取出一人安排到椅子上。

3. 马尔可夫随机场

马尔可夫随机场（Markov random field)又称为概率无向图模型，是一个可以由无向图表示的联合概率分布。

概率无向图模型: 设有联合概率分布 P(Y) ，由无向图 G=(V,E) 表示，在图 G 中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布 P(Y) 满足成对、局部或全局马尔可夫性，就称此联合概率分布为概率无向图模型或马尔可夫随机场。分别介绍一下三个概念：

成对马尔可夫性：给定所有其他变量，两个非邻接变量条件独立。这是因为两个节点没有直接路径，并且所有其他路径上都有确定的观测节点，因此这些路径也将被阻隔。其实意思就是说没有直连边的任意两个节点是独立的。
局部马尔可夫性：给定变量 v 的所有邻接变量 w，则该变量 v 条件独立于其他变量 o。即在给定某个变量的邻接变量的取值条件下，该变量的取值将于其他变量无关。就是说，v 的取值只和它所有邻接变量w相关。
全局马尔可夫性：设节点集合A，B是在无向图G中被节点集C分开的任意节点集合，如下图所示。全局马尔可夫性是指在给定x_C的条件下，x_A和x_B条件独立。也就是说，在A和B被C分开时候，A和B条件独立，这时候才说是满足全局马尔可夫。

\[A ------ C ------- B \]

总的说来，马尔可夫随机场假设随机场中某一个位置的赋值仅仅与和它相邻的位置的赋值有关，和与其不相邻的位置的赋值无关。

因此，联合概率分布的分解一定要让 xi 和 xj 不出现在同一个划分中，从而让属于这个图的所有可能概率分布都满足条件独立性质。让非邻接变量不出现在同一个划分中，即每一个划分中节点都是全连接的。这将我们引向了图的一个概念，团（clique）。

4. 最大团

CRF是通过团以及势函数的概念来定义条件概率P（y|x）。所以我们要学习最大团。

马尔可夫随机场中，对于图中结点一个子集，若其中任意两结点间都有边连接，则称该结点子集为一个团，若在一个团中，加入另外任何一个结点都不再形成团，则称该团为极大团，换言之，极大团就是不能被其他团所包含的团。

比如梁山好汉一起去聚义厅开会。你就会发现，同一个小集团的人会主动聚在一起。

比如打虎将李忠就必然在三山帮这一个小集团中。而九尾龟陶宗旺则必然在黄门山（摩云金翅欧鹏、神算子蒋敬、铁笛仙马麟、九尾龟陶宗旺）小集团中。

李忠和陶宗旺两个人在私下不会有什么交集。而黄门山这四人，每个人和每个人之间都是全联接，都互相熟悉。

如果往黄门山四人中加入其他任何一个梁山好汉之后变成五人团体，则这个五人团体就不再算是黄门山这个小集团了。所以黄门山四人就是极大团。

显然，最简单的团就是两个节点以及一条边，而我们最开始就针对两节点之间的相关关系（每条边）定义了势函数。

5. 势函数

势函数的作用是定量刻画变量集 Q 中变量之间的相关关系。比如句首几个字的关系。

数学定义

给定概率无向图模型，设其无向图为G，C为G上的最大团，Y_C表示C对应的随机变量（是最大团的所有结点）。

φ(Y_C)是一个最大团 C 上随机变量们的联合概率，是用于对团C中的变量之间的关系进行建模，是定义概率分布的函数。

φ(Y_C)被称为与团C对应的「势函数（potential function）」。一般而言，你要为图中的每个极大团（maximal clique）定义一个势函数。

具体形式

无向图模型中势函数的具体形式通常定义为特征函数的带权加和, 也即这些方法通常将条件随机字段中的势函数定义为某些人工设计的特征函数的线性组合，这些函数是启发式的。

势函数是一个表示其对应的团(clique)状态的非负实值函数，表征的是该clique的状态。对于一个图中的每一个clique来讲，它有一个状态，用势函数表示，状态则是由多个feature的加权和构成，因为一个clique是包含多个节点的，每个节点其对应的随机变量，都会对应一个feature。

因此，马尔可夫随机场中，多个变量的联合概率分布能基于团分解为多个势函数的乘积，每一个团对应一个势函数。所以可以将联合概率分布分解为其极大团上的势函数的乘积。

从最大熵的角度来看势函数

熵用来表示任何一种能量在空间中分布的均匀程度，能量分布得越均匀，熵就越大。

对于势函数，我们换一种理解方式，定义将potential function表示成指数函数

\[φ_C(Y_C) = exp \{-E(Y_C)\} \]

这样p(x)就可以表示成一系列E(Yc)的和的指数形式。E(Yc)叫做能力函数。

这样转化之后，可以将图理解为一个能力的集合，他的值等于各个最大团的能量的和。CRF要做的就是最小化这些能量，以达到稳定的结果。均匀分布就是最稳定的，熵就达到了最大值。即，用能量最小化表示整个系统达到稳态时各个变量的状态满足的条件。

比如梁山上，有各种小团体。每一个团体对应一个势函数。
比如 生辰纲七人组，登州帮，三山帮，揭阳帮，降将帮，大名府帮，黄门山帮，清风山....
  
那么梁山就可以理解为一个能力的集合，他的值就等于各个小团体能量的和。
CRF就是要最小化这些能量，这样梁山才能稳定，最好能均匀分布，这样熵就达到了最大值。

6. 特征函数

特征函数是一些经验的特性，我们使用特征函数来表示约束条件。特征函数在前文[白话解析]用水浒传为例学习最大熵马尔科夫模型也有详述。

势函数是定义场里面所有变量关系的的一个函数，而因子是为了或者描述简化场里面变量关系所限定的一个假设，例如同时考虑两个相邻的因子或者所有相邻的因子。

特征函数用来表示因子内的变量的关系，例如构成因子的变量的某些特征是相似的。比如在词性标注中，特征函数可能是：前一个词是动词，当前词的观察状态[是不是句首，是不是句尾，是不是数字]

CRF中，特征（feature）是一系列把我们观测到的 d 和我们想要预测的类别 c 联系到一起的证据(evidence)。特征是在实数范围内一个函数 f。这些特征是怎么表达的呢？有两种特征：

一种是转移特征，就是涉及到两个状态之间的特征。
另一种就是简单的状态特征，就是只涉及到当前状态的特征。

特征表达形式比较简单，就是你是否满足我特征所说的这个配置，是就是1，不是就是0。

模型会给每个特征分配一个权重，我们最后要学的就是这些权重：

正权重说明这种结构很可能是正确的
正权重说明这种结构很可能是不正确的

我们通过引入两类特征函数便可以定义出目标条件概率：

表示定义在观测序列的两个相邻标记位置上的转移特征函数，用于刻画相邻标记变量之间的相关关系以及观测序列对他们的影响，
表示在观测序列的标记位置i上的状态特征函数，用于刻画观测序列对标记变量的影响。

例如词性标注，如何判断给出的标注序列靠谱不靠谱，转移特征函数主要判定两个相邻的标注是否合理，例如，动词+动词语法不通。状态特征函数判定观测值与对应的标注是否合理，例如：ly结尾的词-->副词较合理。

因此我们可以定义一个特征函数集合，用这个特征函数集合来为一个标准序列打分，根据此选出靠谱的标注序列。每一个特征函数都可以用来为一个标准序列评分，把集合中所有特征函数对同一个标注序列的评分综合起来，就是这个标注序列最终的评分值。条件随机场完全由特征函数和对应的权值确定。

和HMM不同的是，CRF并没有做出HMM的假设，CRF使用feature function来更抽象地表达特征，使得他不再局限于HMM的两类特征。特征函数可以表示当前的state与任意一个observation或者 state甚至future state的关系。也就是说，特征方程的存在允许CRF有十分*的特征表达。这也就是条件随机场中场所代表的意义。举例如下：

func1 = if (output = B-NP and feature="U01:DT") return 1 else return 0
func2 = if (output = I-NP and feature="U01:DT") return 1 else return 0
func3 = if (output = O and feature="U01:DT") return 1 else return 0
...
funcXX = if (output = B-NP and feature="U01:NN") return 1 else return 0
funcXY = if (output = O and feature="U01:NN") return 1 else return 0

一个特征函数模板会生成 L x N 个特征函数, 其中 L 输出类别的情况数目，N 是expanded feature的所有可能的情况数目。

7. 概率无向图模型联合概率分布

实际上，我们更关心的是如何求概率无向图模型联合概率分布。对给定的概率无向图模型，我们希望将整体的联合概率写成若干子联合概率的乘积的形式，也就是将联合概率进行因子分解，这样便于模型的学习与计算。事实上，概率无向图模型的最大特点就是易于因子分解。所以我们将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作，称为概率无向图模型的因子分解。

对于概率分布函数而言，我们也希望能够这样做，即给定概率无向图模型，设无向图为 G ， C 为 G 上的最大团， YC 表示 C 对应的随机变量。那么概率无向图模型的联合概率分布 P(Y) 可分解为图中所有最大团 C 上的函数 ΨC(YC) 的乘积形式。

总结一下,便得到 Hammersley-Clifford定理，那么整个概率无向图模型的联合概率分布P(Y)可写作图中所有最大团C上的势函数φ(Y_C)的乘积形式。即

\[P(Y) = \frac{1}{Z}\prod_Cφ_C(Y_C) 　\\Z = \sum_Y\prod_Cφ_C(Y_C) \]

其中，C 是无向图的最大团， YC 是 C 的结点对应的随机变量， ΨC(YC) 是 C 上定义的严格正函数，乘积是在无向图所有的最大团上进行的。Z表示规范化因子，以确保P(x)是被正确定义的概率。

另外一种考虑最大团的思路

尽管在给定每个节点的条件下，分配给某节点一个条件概率是可能的，但条件随机场的无向性很难保证每个节点在给定它的邻接点条件下得到的条件概率和以图中其它节点为条件得到的条件概率一致。因此导致我们不能用条件概率参数化表示联合概率，而要从一组条件独立的原则中找出一系列局部函数的乘积来表示联合概率。

个人理解就是：因为crf希望过计算整个标记序列 Y 的联合概率分布，而不是在给定当前状态条件下定义下一个状态的分布。但是从每个节点角度讲，很难保持条件概率一致。所以选取最大团这个具有独立性的小群体。

选择局部函数时，必须保证能够通过分解联合概率使没有边的两个节点不出现在同一局部函数中。最简单的局部函数是定义在图结构中的最大团(clique)上的势函数(Potential function)，并且是严格正实值的函数形式。

但是一组正实数函数的乘积并不能满足概率公理，则必须引入一个归一化因子 Z ，这样可以确保势函数的乘积满足概率公理，且是无向图中节点所表示的随机变量的联合概率分布。

这样出来的图是等价于吉布斯分布的，就是说，你可以只在每个最大子团上定义一个联合分布（而不需要对每个边定义一个联合分布），整个图的联合概率分布就是这些最大子团的联合概率分布的乘积。当然这里最大子团的联合概率并不是标准的联合概率形式，是没归一化的联合概率，叫factor（因子），整个图的联合概率乘完之后下面再除一个归一化因子和就归一化了，最终是一个联合概率，每个子团记载的都是因子，是没归一化的概率，严格大于零，可以大于一。但关键是依赖关系、这些相关关系已经encode在里面了。

8. 从水浒传角度看

从水浒传角度看，可以这么定义特征函数和势函数。对了，这里的势函数就可以看成是*

三山帮指的是二龙山、桃花山和少华山。这个派系一共13人，头领是鲁智深。下面人是：二龙山的鲁智深、杨志、武松、施恩、曹正、张青和孙二娘；桃花山的周通、李忠；少华山的史进、朱武、陈达，杨春。
  
定义特征函数如下  
*********************** 特征函数 之 节点属性
s_1 = 是不是倒拔垂杨柳的僧人
s_2 = 是不是打虎英雄
s_3 = 是不是黑旋风  
s_4 = 是不是五虎将  
s_5 = 是不是八骠骑
s_6 = 是不是小彪将  
s_7 = 是不是一同参赞军务头领  
s_8 = 是不是步军将校一十七员
s_9 = ......

  
*********************** 特征函数 之 边属性  
t_1 = 是不是亲兄弟
t_2 = 是不是叔侄
t_3 = 是不是夫妻
t_4 = 是不是表亲  
t_5 = 是不是师徒
t_6 = 是不是主仆  
t_7 = 是不是曾经共过生死
t_8 = 是不是一起经历过尴尬事
t_9 = 是不是同乡
t_10 = 是不是 "聚会之前就是结拜兄弟" 
t_11 = 是不是同僚  
t_12 = 是不是有同地工作经历    
t_13 = ...... 

定义势函数如下：
*********************** 势函数  
φ = λ1t1 + λ2t2 + λ3t3 + λ4t4 + λ5f5 + ...... + w1t1 + w2t2 + w3t3 + w4t4 + w5t5 + ...... 
  
计算结果如下：
*********************** 计算结果  
s_1 = 鲁智深 ————————————— 倒拔垂杨柳的僧人
s_2 = 武松 ——————————————— 打虎英雄
s_3 = 0
s_4 = 0  
s_5 = 杨志 史进 ——————————— 八骠骑
s_6 = 陈达，杨春，周通 ——————  小彪将
s_7 = 朱武 ————————————————   一同参赞军务头领
s_8 = 李忠，施恩———————————— 步军将校一十七员
......
  
t_1 = 0
t_2 = 0
t_3 = 张青&孙二娘 —————————— 夫妻
t_4 = 0  
t_5 = 0
t_6 = 0  
t_7 = 武松&施恩, 鲁智深&史进, 史进&朱武&陈达&杨春, 武松&张青&孙二娘, 杨志&鲁智深&曹正 ———— 共生死
t_8 = 鲁智深&李忠&周通 ———— 共尴尬
t_9 = 张青&孙二娘&施恩&曹正(河南)，杨志&杨春(山西)，周通&武松(山东)，朱武&李忠(定远县) ———— 老乡
t_10 = 武松&施恩, 鲁智深&史进, 史进&朱武&陈达&杨春, 武松&张青&孙二娘, 周通&李忠  ———— 老兄弟
t_11 = 0  
t_12 = 鲁智深&杨志&史进 (都有延安府相关履历)     
t_13 = ......    
  
  
这里如果按照影响力计算，则 s_1 ~ s_7，t_3，t_7 的权重都相当大。
由此可见三山帮的势函数有多大，有猛人，有帮闲，有主将，有副将，有马军，有步兵，甚至还有军师。他们彼此之间关系则是盘根错节。
其在梁山内部绝对是第二大*。

0x04 条件随机场 (conditional random field，CRF)

1. 条件随机场

当随机变量之间有依赖关系的时候就是条件随机场。比如：

三山派的好汉不能和宋江嫡系挨着坐。

条件随机场接收一个输入序列 (观察序列)如 X = (x1 ,x2, ..., xn)，

给出一个输出目标序列( 隐藏状态序列 ) Y = (y1 ,y2, ..., yn)，这里使用大写 X,Y 表示序列。

一般地，输入序列 X 被称为 observations (观测值) , 输出序列 Y 叫作 states (隐藏状态)。Random 指的是随机变量 X and Y。 Conditional 指的是条件概率 Conditional probability。

HMM、MEMM属于有向图模型，贝叶斯网络一般属于有向图。而CRF属于马尔科夫网络属于无向图。

CRF是马尔科夫随机场的特例，条件随机场没有隐马尔可夫模型那样严格的独立性假设条件，因而可以容纳任意的上下文信息，可以灵活地设计特征。同时，条件随机场具有表达长距离依赖性和交叠性特征的能力，而且所有特征可以进行全局归一化，能够求得全局的最优解，还克服了最大熵马尔可夫模型标记偏置的缺点。

2. 数学定义

条件随机场准确的数学语言描述是：设X与Y是随机变量，P(Y|X)是给定X时Y的条件概率分布，若随机变量Y构成的是一个马尔科夫随机场，则称条件概率分布P(Y|X)是条件随机场。

条件随机场是在给定需要标记的观察序列 X 的条件下计算整个标记序列 Y 的联合概率分布，而不是在给定当前状态条件下定义下一个状态的分布。

\[P(Y|X) = \frac{exp (w.φ(x,y))}{Z_x} \]

注意Z(x)是遍历所有 y 的全局归一化，如果Z(x)写在乘积符号里面的则就是local归一化，那样得到的是MEMM。

CRF本质上就是一个softmax，只是它不是在单样本上面做的，而是序列化样本；为了保证是整个序列做的分类，在CRF中考虑了相邻状态之间的转换特征函数。

CRF损失函数由两部分组成，真实路径的分数和所有路径的总分数。真实路径的分数应该是所有路径中分数最高的。

3. linear-CRF

在CRF的定义中，我们并没有要求X和Y有相同的结构。而实现中，我们一般都假设X和Y有相同的结构，即:

\[????=(????1,????2,...????????), ????=(????1,????2,...????????) \]

线性的CRF，每个Y都只和前一个或后一个随机变量相连，如 Y1——Y2——Y3——...Yn。每个最大团都是邻近的两个随机变量，如(Y1, Y2)、(Y2、Y3)等

CRF也和MEMM一样做了一阶马尔科夫假设，即当前状态只与上一状态有关，但是区别在于CRF的特征采用了全局特征，它把观测序列当做整体来看所以它的特征函数是全局的。

线性Linear-CRF对比HMM把箭头（转移方向）变成了直线。最直白的感官体验是每个圆圈（向量）都可以肆无忌惮畅通无阻的相邻的圆圈相连了，交互多了，模型也变复杂了，每个圆圈之间的关系从“局部”也变成“全局”。线性Linear-CRF是CRF很多结构中比较常用的一种，只要保证状态序列满足马尔科夫性都是CRF。

4. 例子

网上关于CRF有两个比较好的例子，摘录如下：

例子1

假设你有许多小明同学一天内不同时段的照片，从小明提裤子起床到***子睡觉各个时间段都有（小明是照片控！）。现在的任务是对这些照片进行分类。比如有的照片是吃饭，那就给它打上吃饭的标签；有的照片是跑步时拍的，那就打上跑步的标签；有的照片是开会时拍的，那就打上开会的标签。问题来了，你准备怎么干？

一个简单直观的办法就是，不管这些照片之间的时间顺序，想办法训练出一个多元分类器。就是用一些打好标签的照片作为训练数据，训练出一个模型，直接根据照片的特征来分类。例如，如果照片是早上6:00拍的，且画面是黑暗的，那就给它打上睡觉的标签;如果照片上有车，那就给它打上开车的标签。

这样可行吗？

乍一看可以！但实际上，由于我们忽略了这些照片之间的时间顺序这一重要信息，我们的分类器会有缺陷的。举个例子，假如有一张小明闭着嘴的照片，怎么分类？显然难以直接判断，需要参考闭嘴之前的照片，如果之前的照片显示小明在吃饭，那这个闭嘴的照片很可能是小明在咀嚼食物准备下咽，可以给它打上吃饭的标签；如果之前的照片显示小明在唱歌，那这个闭嘴的照片很可能是小明唱歌瞬间的抓拍，可以给它打上唱歌的标签。

所以，为了让我们的分类器能够有更好的表现，在为一张照片分类时，我们必须将与它相邻的照片的标签信息考虑进来。这——就是条件随机场(CRF)大显身手的地方！

例子2

RF是随机场，MRF是马尔可夫随机场，又称概率图模型，CRF是条件随机场，Linear Chain CRF是线性链CRF

拿“一个群体中人的性格，群体中一个人的性格可能会影响另一个的性格”举例：
定义“我从小到大所有认识的人+我女朋友从小到大所有认识的人”就是这个空间，“空间里每个人的性格”都是一个变量，那么：

RF ：这个空间里每个人的性格变量都是随机的，所有人的性格变量的集合就是一个RF

MRF ：假设现在有这么个条件，我不认识的人根本不影响我的性格（成对马尔可夫性），那么就是MRF了。

CRF：刚才只说了性格变量互相影响，说的很虚，因为你需要有一些东西衡量性格呀，所以我又假设了一个条件，假设我能观测到“所有人在认识的人和她接触时她的笑的时间”，那么这时候的性格影响就不是那么不可描述了，我说她天生笑的多就是天生就是性格乐观，这个人和这个人一起跟她说话他笑得比平均高，那就是这两个人对他性格乐观的影响大，这时候你把笑声考虑进去研究性格，出现了条件概率，那就是CRF了。

线性链CRF：上面说的每个人可能认识很多人，这个情况就很复杂，你现在在假设一种情况，每个人都有编号，你只认识比你大一号或者比你小一号的那两个人，于是你的性格就只受那两个人的性格影响，而不管什么人，他们发出笑声还是能或多或少影响你，那就是线性链CRF

如果再严格一点，不是所有人的笑声影响你，就你自己真的笑了才影响你，那就是X和Y结构相同的线性链CRF，这样的好处在于最大团的定义的话就是任意被连接两个点都是最大团，比较好计算图概率

M就是马尔可夫的意思，代表具有三种马尔可夫性（等价的，满足一个另外两个自然满足），就是和我没关系的点根本不影响我的概率分布（成对马尔可夫性）；只有和我有关系的才能影响我的概率分布，整个群体对我的概率分布就是周围人影响下的我的概率分布（局部马尔可夫性），我的高中同学和大学同学，这两拨同学之间互不认识，那么我对这两拨同学的概率分布的影响是独立的（全局马尔可夫性）
C就是条件，没有C就是意味着探讨P(Y)的分布，有了C就是探讨P(Y|X)，所以这个C是条件概率下的那个条件的意思。`

5. HMM vs MEMM vs CRF

假设

HMM模型中存在两个假设：一是输出观察值之间严格独立，二是状态的转移过程中当前状态只与前一状态有关(一阶马尔可夫模型)。其中，输出独立性假设要求序列数据严格相互独立才能保证推导的正确性，而事实上大多数序列数据不能被表示成一系列独立事件。
MEMM模型克服了观察值之间严格独立产生的问题，但是由于状态之间的假设理论，使得该模型存在标注偏置问题。
CRF模型使用一种概率图模型，解决了标注偏置问题，去除了HMM中两个不合理的假设。因而可以容纳任意的上下文信息，可以灵活地设计特征。同时，条件随机场具有表达长距离依赖性和交叠性特征的能力，而且所有特征可以进行全局归一化，能够求得全局的最优解，还克服了最大熵马尔可夫模型标记偏置的缺点。

预测输出

其中HMM中，Yi只与Yi-1有关，而Xi输出只与Yi有关。在MEMM中，Yi 是由Xi和Yi-1确定的，在CRF中，确定某个Yi，它会考虑整个Y及Xi的。

序列标注模型

这三个模型都可以用来做序列标注模型。但是其各自有自身的特点。

HMM模型：假设出变量间的概率分布，建模一切观察到的变量的联合分布。在Y变量间做了markov假设。对转移概率和表现概率直接建模，统计共现概率。
MEMM模型：是对转移概率和表现概率建立联合概率，统计时统计的是条件概率。MEMM容易陷入局部最优，是因为MEMM只在局部做归一化，
CRF模型：最大熵准则建模条件概率p(Y|X)。 统计了全局概率，在做归一化时，考虑了数据在全局的分布，而不是仅仅在局部归一化，这样就解决了MEMM中的标记偏置的问题。要先把CRF约束成linear chain CRF，然后linear chain CRF和HMM的区别：是判别式模型和生成模型的区别，是函数拟合和概率模型的区别。

HMM是建立generative model ，即p(x,y) ，转化为建立noisy-channel model，即求arg max p(y) p(x|y) ，继而转化为状态转移概率p(yi|yi-1) 和发射概率p(xi|yi) 之积，注意这个发射概率，与crf的发射概率不一样。建模是对状态转移概率和发射概率进行参数估计，从大量的文档数据中根据统计学来统计。decode过程是使用vertibe算法，利用状态转移概率和发射概率计算最优解答，这是一个生成模型。

MEMM是建立conditional model，即 p(y|x) ，转化为状态转移概率p(yi|x1, ..., xi, yi-1) 。利用这个依赖关系建立Log-Linear Tagging Model，和HMM相比这样可以捕捉到更多的feature，而在log linear的过程中使用局部归一化，就是针对每一个yi, 都要求 exp(θ . f(hi, yi)) / ∑ exp(θ . f(hi, yi)) 。注意归一化式子的分母对于不同的 yi 是不一样的，因为不同的yi 依赖的 hi 不一样。hi 是 yi 的依赖关系，即x1, ..., xi, yi-1。这也就代表在使用vertibe算法decode过程中，每一时步求的 yi 多多少少有点局部最优的味道，并不一定是全局最优。建模过程是对 θ 进行参数估计，即求结构化的最大似然估计。

crf是建立conditional model，即 p(y|x) ，crf也是Log-Linear Tagging Model，但是依赖关系变成了整个 y 序列依赖整个 x 序列，也就是全局归一化，优点就是在decode过程中，那个归一化式子的分母是一样的，最后求得的一定是全局最优，所以decode时只需要求各种状态转移概率和发射概率之和就好了，在decode过程中HMM和MEMM都是求积，为什么crf是各种求和呢，因为它不用求分母，log 分子其实就是各种状态转移概率和发射概率之和。

6. 源码阅读

以下源码出自 CRF++: Yet Another CRF toolkit ，分析主要摘录 CRF++代码分析

计算代价

计算每个节点和每条边的代价（也就是特征函数乘以相应的权值，简称代价），就是势函数。

其中fvector是当前命中特征函数的起始id集合，对于每个起始id，都有连续标签个数种y值；n->y是当前时刻的标签，由于每个特征函数都必须同时接受x和y才能决定输出1或0，所以要把两者加起来才能确定最终特征函数的id。用此id就能在alpha向量中取到最终的权值，将权值累加起来，乘以一个倍率（也就是所谓的代价参数cost_factor），得到最终的代价cost。

对于边来说，也是类似的，只不过对每个起始id，都有连续标签个数平方种y值组合。

struct Node {
  unsigned int         x;
  unsigned short int   y;
  double               alpha;
  double               beta;
  double               cost;
  double               bestCost;
  Node                *prev;
  const int           *fvector;
  std::vectorlpath;
  std::vectorrpath;
}

struct Path {
  Node      *rnode;
  Node      *lnode;
  const int *fvector;
  double     cost;
}

//计算节点的特征函数的代价
void FeatureIndex::calcCost(Node *n) const {
  n->cost = 0.0;

  // 遍历节点对应的所有特征函数，因为一个特征函数可能会对应多个输出类别，所以要将目前节点的 y 代入，得到 *f + n->y，就是当前 y 在 f 输出类别中对应的位置。然后就可以从alpha向量中取到最终的权值, 再将权值累加。
#define ADD_COST(T, A)                                                        \
  do { T c = 0;                                                               \
    for (const int *f = n->fvector; *f != -1; ++f) { c += (A)[*f + n->y];  }  \
    n->cost =cost_factor_ *(T)c; } while (0)

  if (alpha_float_) {
    ADD_COST(float,  alpha_float_);
  } else {
    ADD_COST(double, alpha_);
  }
#undef ADD_COST
}

//计算每条边的状态特征函数的代价
void FeatureIndex::calcCost(Path *p) const {
  p->cost = 0.0;

#define ADD_COST(T, A)                                          \
  { T c = 0.0;                                                  \
    for (const int *f = p->fvector; *f != -1; ++f) {            \
      c += (A)[*f + p->lnode->y * y_.size() + p->rnode->y];     \
    }                                                           \
    p->cost =cost_factor_*(T)c; }

  if (alpha_float_) {
    ADD_COST(float,  alpha_float_);
  } else {
    ADD_COST(double, alpha_);
  }
}
#undef ADD_COST
}

前向后向算法

void TaggerImpl::forwardbackward() {
  if (x_.empty()) {
    return;
  }

  //计算所有节点的前向概率
  for (int i = 0; i < static_cast(x_.size()); ++i) {
    for (size_t j = 0; j < ysize_; ++j) {
      node_[i][j]->calcAlpha();
    }
  }

  //计算所有节点的后向概率
  for (int i = static_cast(x_.size() - 1); i >= 0;  --i) {
    for (size_t j = 0; j < ysize_; ++j) {
      node_[i][j]->calcBeta();
    }
  }

  //计算规范化因子
  Z_ = 0.0;
  for (size_t j = 0; j < ysize_; ++j) {
    Z_ = logsumexp(Z_, node_[0][j]->beta, j == 0);
  }

  return;
}

//其中cost是我们刚刚计算的当前节点的M_i(x)，而alpha则是当前节点的前向概率。lpath是入边，一个顶点可能有多个入边。
void Node::calcAlpha() {
  alpha = 0.0;
  for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) {
    alpha = logsumexp(alpha,
                      (*it)->cost +(*it)->lnode->alpha,
                      (it == lpath.begin()));
  }
  alpha += cost;
}

void Node::calcBeta() {
  beta = 0.0;
  for (const_Path_iterator it = rpath.begin(); it != rpath.end(); ++it) {
    beta = logsumexp(beta,
                     (*it)->cost +(*it)->rnode->beta,
                     (it == rpath.begin()));
  }
  beta += cost;
}

void Node::calcExpectation(double *expected, double Z, size_t size) const {
  const double c = std::exp(alpha + beta - cost - Z);
  for (const int *f = fvector; *f != -1; ++f) {
    expected[*f + y] += c;
  }
  for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) {
    (*it)->calcExpectation(expected, Z, size);
  }
}

#define MINUS_LOG_EPSILON  50
// log(exp(x) + exp(y));
//    this can be used recursivly
// e.g., log(exp(log(exp(x) + exp(y))) + exp(z)) =
// log(exp (x) + exp(y) + exp(z))
inline double logsumexp(double x, double y, bool flg)
{
    if (flg)
        return y;  // init mode
    const double vmin = std::min(x, y);
    const double vmax = std::max(x, y);
    if (vmax > vmin + MINUS_LOG_EPSILON)
    {
        return vmax;
    }
    else
    {
        return vmax + std::log(std::exp(vmin - vmax) + 1.0);
    }
}

全局归一化

其中前后向概率都有了之后，计算规范化因子，此处能看出来是进行全局归一化：

Z_ = 0.0;
for (size_t j = 0; j < ysize_; ++j) {
  // 注意，这里是用 node_[0] 位置的 beta 数值，就是说，这个已经是用后向概率的最终结果来计算 Z，这个就已经是考虑了全局情况，如果是用 alpha 计算，也得取最终数值，那就需要取 node_[n][j]->alpha 了
	Z_ = logsumexp(Z_, node_[0][j]->beta, j == 0); 
}

推导过程如下：

我们定义βi(yi|x)表示序列位置i的标记是yi时，在位置i之后的从i+1到n的部分标记序列的非规范化概率。

这样，我们很容易得到序列位置i+1的标记是yi+1时，在位置????i之后的部分标记序列的非规范化概率βi(yi|x)的递推公式：

\[????_????(????_????|????)=????_{????+1}(????_????,????_{????+1}|????)????_{????+1}(????_{????+1}|????) \]

在终点处，我们定义：

\[????_{????+1}(????_{????+1}|????)= \begin{cases} 1 \ ????_{????+1}=????????????????\\ 0 \ ???????????????? \end{cases} \]

如果用向量表示，则有：

\[????_????(????)=????_{????+1}(????)????_{????+1}(????) \]

对应着规范化因子Z(x)的表达式是：

\[????(????)=∑_{????=1}^????????_????(????????_|????)=∑_{????=1}^????????_1(????_????|????) \]

也可以用向量来表示Z(x):

\[\\Z(x) = \alpha_n^T(x) . 1 = 1^T . \beta_1(x) \]

其中，1是 m维全1向量。

期望值的计算

所谓的节点期望值指的是节点对应的状态特征函数关于条件分布P(y|x)的数学期望。

/**
 * 计算节点期望
 * @param expected 输出期望
 * @param Z 规范化因子
 * @param size 标签个数
 */
void Node::calcExpectation(double *expected, double Z, size_t size) const {

  const double c = std::exp(alpha + beta - cost - Z);

  // 概率求和意味着得到期望
  for (const int *f = fvector; *f != -1; ++f) {
    expected[*f + y] += c;
  }

  // 对应边的期望值
  for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) {
    (*it)->calcExpectation(expected, Z, size);
  }
}

所谓边的期望指的是边对应的转移特征函数关于条件分布P(y|x)的数学期望。

/**
 * 计算边的期望
 * @param expected 输出期望
 * @param Z 规范化因子
 * @param size 标签个数
 */
void Path::calcExpectation(double *expected, double Z, size_t size) const
{
    const double c = std::exp(lnode->alpha + cost + rnode->beta - Z);
    for (const int *f = fvector; *f != -1; ++f)
    {
        expected[*f + lnode->y * size + rnode->y] += c;
    }
}

viterbi算法

void TaggerImpl::viterbi() {
  for (size_t i = 0;   i < x_.size(); ++i) {
    for (size_t j = 0; j < ysize_; ++j) {
      double bestc = -1e37;
      Node *best = 0;
      const std::vector&lpath = node_[i][j]->lpath;
      for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) {
        double cost = (*it)->lnode->bestCost +(*it)->cost +
            node_[i][j]->cost;
        if (cost > bestc) {
          bestc = cost;
          best  = (*it)->lnode;
        }
      }
      node_[i][j]->prev     = best;
      node_[i][j]->bestCost = best ? bestc : node_[i][j]->cost;
    }
  }

  double bestc = -1e37;
  Node *best = 0;
  size_t s = x_.size()-1;
  for (size_t j = 0; j < ysize_; ++j) {
    if (bestc < node_[s][j]->bestCost) {
      best  = node_[s][j];
      bestc = node_[s][j]->bestCost;
    }
  }

  for (Node *n = best; n; n = n->prev) {
    result_[n->x] = n->y;
  }

  cost_ = -node_[x_.size()-1][result_[x_.size()-1]]->bestCost;
}

0x05 水浒传例子

还是扩展之前的例子

梁山好汉在聚义厅开会，大家共聚一堂，讨论招安事宜。但是群体中好汉会彼此影响投票的选择。

随机场 ：假定不是按照座次排序，而是随意坐，这样大家座位分布是随机的。

最大团 ：虽然是随机场，但是好汉们会自动按照小团体站在一起，比如黄门山四人站在一起，三山帮站在一起。这就形成了很多最大团。

马尔可夫随机场 ：假设现在有这么个条件，彼此不挨着的好汉不能影响彼此的投票决定（成对马尔可夫性），这就是MRF。

条件随机场：假设有一些其他条件需要考虑，比如如果铁笛仙马麟虽然属于黄门山这个最大团，但是他的位置不小心挨着李逵，那么他在投票时候，势必得考虑铁牛兄弟的意见，不然铁牛的拳头不是吃素的。比如曹正虽然属于三山帮，但是林冲是他师傅，所以他投票也得考虑豹子头的意见，这就构成了条件场.....