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

# [白话解析] 用水浒传为例学习条件随机场 ## 0x00 摘要 本文将尽量使用易懂的方式，尽可能不涉及数学公式，而是从整体的思路上来看，运用感性直觉的思考来解释条件随机场。并且用水浒传为例学习。并且从名著中找了具体应用场景来帮助大家深入这个概念。 在机器学习过程中，会遇到很多晦涩的概念，相关数学公式很多，大家理解起来很有困难。遇到类似情况，我们应该多从直觉角度入手思考，用类别或者举例来**附会**，这样往往会有更好的效果。 我在讲解论述过程中给自己的要求是：在生活中或者名著中找一个例子，然后用自己的话语阐述出来。 ## 0x01 HMM 隐马尔可夫 首先还是需要大概介绍下HMM和MEMM，这样才能知道为什么要引入CRF。 其中HMM在前文[[白话解析\]以水浒传为例学习隐马尔可夫模型](https://www.cnblogs.com/rossiXYZ/p/12430955.html)中也详细介绍。这里主要讲讲其推导过程和其缺点。 ### 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_1^n)来求解条件概率P(y_1^n|x_1^n)，这种方法不适合处理很多特征描述观测序列的情况。为此MEMM直接采用条件概率模型P(y_1^n|x_1^n)。 ## 0x02 MEMM ### 1. 最大熵模型 其中最大熵模型在前文 [[白话解析\] 深入浅出最大熵模型](https://www.cnblogs.com/rossiXYZ/p/12244760.html) 以及 [[白话解析\]用水浒传为例学习最大熵马尔科夫模型](https://www.cnblogs.com/rossiXYZ/p/12435815.html) 中也有介绍。 假设离散随机变量 x 的分布是P(x)，则关于分布P的熵定义为： $$ H(P) = -\sum_xP(x)logP(x) $$ 可以看出当 x 服从均匀分布时对应的熵最大，也就是不确定性最高。 给定离散随机变量 ![[公式]](https://www.zhihu.com/equation?tex=x) 和 ![[公式]](https://www.zhihu.com/equation?tex=y) 上的条件概率分布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。 针对这个论断，我们可以写代码实验下 (*如果哪位兄弟知道如何数学论证，还请告诉我，谢谢*) 。 ```python # 以下就是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(-beta*E)成正比，-beta和温度的倒数有关，E是体系每个部分的势能之和，和系统所有可能构型的这个因子之和成反比，这个和就是配分函数，而势函数就是用来计算体系每个部分间不同位置关系下可能的势能的理论假设的函数形式。机器学习就是借用这种模型来产生概率罢了，或者说它是我们要考察的物理量的一个因子，而且这个被考察物理量不仅取值和这个因子有关，其变化规律也和这个因子有关。这是借用的物理里的概念。理论物理里提出用蒙特卡罗算法求解体系可能结构的方法，每个结构出现的概率和exp(-beta*E)成正比，-beta和温度的倒数有关，E是体系每个部分的势能之和，和系统所有可能构型的这个因子之和成反比，这个和就是配分函数，而势函数就是用来计算体系每个部分间不同位置关系下可能的势能的理论假设的函数形式。机器学习就是借用这种模型来产生概率罢了，或者说它是我们要考察的物理量的一个因子，而且这个被考察物理量不仅取值和这个因子有关，其变化规律也和这个因子有关。 ### 2. 随机场 随机场是由若干个位置组成的整体，当给每一个位置中按照某种分布随机赋予一个值之后，其全体就叫做随机场。举词性标注的例子：假如我们有一个十个词形成的句子需要做词性标注。这十个词每个词的词性可以在我们已知的词性集合（名词，动词...) 中去选择。当我们为每个词选择完词性后，这就形成了一个随机场。 ```java 举梁山为例子： 比如梁山好汉一起去聚义厅开会。 每把椅子是一个位置。给每个椅子赋予一个好汉。这个好汉如何分配? 每次从梁山上各个小团体(三山派，浔阳帮，宋江嫡系......)中随机取出一人安排到椅子上。 ``` ### 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）。所以我们要学习最大团。 马尔可夫随机场中，对于图中结点一个子集，若其中任意两结点间都有边连接，则称该结点子集为一个团，若在一个团中，加入另外任何一个结点都不再形成团，则称该团为极大团，换言之，极大团就是不能被其他团所包含的团。 ```java 比如梁山好汉一起去聚义厅开会。你就会发现，同一个小集团的人会主动聚在一起。 比如打虎将李忠就必然在三山帮这一个小集团中。而九尾龟陶宗旺则必然在黄门山（摩云金翅欧鹏、神算子蒋敬、铁笛仙马麟、九尾龟陶宗旺）小集团中。 李忠和陶宗旺两个人在私下不会有什么交集。而黄门山这四人，每个人和每个人之间都是全联接，都互相熟悉。 如果往黄门山四人中加入其他任何一个梁山好汉之后变成五人团体，则这个五人团体就不再算是黄门山这个小集团了。所以黄门山四人就是极大团。 ``` 显然，最简单的团就是两个节点以及一条边，而我们最开始就针对两节点之间的相关关系（每条边）定义了势函数。 ### 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要做的就是最小化这些能量，以达到稳定的结果。均匀分布就是最稳定的，熵就达到了最大值。即，用能量最小化表示整个系统达到稳态时各个变量的状态满足的条件。 ```java 比如梁山上，有各种小团体。每一个团体对应一个势函数。 比如 生辰纲七人组，登州帮，三山帮，揭阳帮，降将帮，大名府帮，黄门山帮，清风山.... 那么梁山就可以理解为一个能力的集合，他的值就等于各个小团体能量的和。 CRF就是要最小化这些能量，这样梁山才能稳定，最好能均匀分布，这样熵就达到了最大值。 ``` ### 6. 特征函数 特征函数是一些经验的特性，我们使用特征函数来表示约束条件。特征函数在前文[[白话解析]用水浒传为例学习最大熵马尔科夫模型](https://www.cnblogs.com/rossiXYZ/p/12435815.html)也有详述。 势函数是定义场里面所有变量关系的的一个函数，而因子是为了或者描述简化场里面变量关系所限定的一个假设，例如同时考虑两个相邻的因子或者所有相邻的因子。 特征函数用来表示因子内的变量的关系，例如构成因子的变量的某些特征是相似的。比如在词性标注中，特征函数可能是：前一个词是动词，当前词的观察状态[是不是句首，是不是句尾，是不是数字] CRF中，特征（feature）是一系列把我们观测到的 d 和我们想要预测的类别 c 联系到一起的证据(evidence)。特征是在实数范围内一个函数 f。这些特征是怎么表达的呢？有两种特征： - 一种是转移特征，就是涉及到两个状态之间的特征。 - 另一种就是简单的状态特征，就是只涉及到当前状态的特征。 特征表达形式比较简单，就是你是否满足我特征所说的这个配置，是就是1，不是就是0。 模型会给每个特征分配一个权重，我们最后要学的就是这些权重： - 正权重说明这种结构很可能是正确的 - 正权重说明这种结构很可能是不正确的 我们通过引入两类特征函数便可以定义出目标条件概率： - 表示定义在观测序列的两个相邻标记位置上的转移特征函数，用于刻画相邻标记变量之间的相关关系以及观测序列对他们的影响， - 表示在观测序列的标记位置i上的状态特征函数，用于刻画观测序列对标记变量的影响。 例如词性标注，如何判断给出的标注序列靠谱不靠谱，转移特征函数主要判定两个相邻的标注是否合理，例如，动词+动词语法不通。状态特征函数判定观测值与对应的标注是否合理，例如：ly结尾的词-->副词较合理。 因此我们可以定义一个特征函数集合，用这个特征函数集合来为一个标准序列打分，根据此选出靠谱的标注序列。每一个特征函数都可以用来为一个标准序列评分，把集合中所有特征函数对同一个标注序列的评分综合起来，就是这个标注序列最终的评分值。条件*随机场*完全由*特征函数*和对应的权值确定。 和HMM不同的是，CRF并没有做出HMM的假设，CRF使用feature function来更抽象地表达特征，使得他不再局限于HMM的两类特征。特征函数可以表示当前的state与任意一个observation或者 state甚至future state的关系。也就是说，特征方程的存在允许CRF有十分自由的特征表达。这也就是条件随机场中场所代表的意义。举例如下： ```python 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. 从水浒传角度看 从水浒传角度看，可以这么定义特征函数和势函数。对了，**这里的势函数就可以看成是势力** ```java 三山帮指的是二龙山、桃花山和少华山。这个派系一共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. 条件随机场 当随机变量之间有依赖关系的时候就是条件随机场。比如： ```java 三山派的好汉不能和宋江嫡系挨着坐。 ``` 条件随机场接收一个输入序列 (观察序列)如 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有相同的结构，即: $$