(16.1.1)--第16讲_条件随机场.pdf
大数据机器学习第十六讲：条件随机场隐目录1.预备知识2.概率无向图模型3.条件随机场的定义与形式4.条件随机场的概率计算问题5.条件随机场的学习算法6.条件随机场的预测算法一、预备知识 词性标注和语法分析HMM到条件随机场 HMM CRFHMM和CRF 共性：都常用来对观测序列和输出序列建模，CRF的优势：HMM最大的缺点就是由于其输出独立性假设，导致其不能考虑上下文的特征，限制了特征的选择；在每一节点都要进行归一化，所以只能找到局部的最优值，同时也带来了标记偏见的问题（label bias）；CRF：选择上下文相关特性；不在每一个节点进行归一化，而是所有特征进行全局归一化，可以求得全局的最优值。二维CRF 随机场 随机场（Random Filed）中，利用邻域系统可以分析空间上的马尔科夫性。一个像素点的特性，更可能受它周围像素的影响，与它距离越远的像素，对它的特性的影响越小。二维CRF在图像分割 的应用二、概率无向图模型 概念：概率无向图模型(probabilistic undirected graphical model)马尔可夫随机场(Markov random field)可以由无向图表示的联合概率分布。概率图模型Probabilistic graphical model变量关系图有向无环图 directed acyclic graph贝叶斯网络bayesian network动态贝叶斯网络dynamic bayesian network无向图 undirected graph马尔科夫网络Markov network模型定义 Graph Node Edge v,集合V e，集合E G=（V，E）结点v，随机变量Yv；边e，随机变量间的概率依赖关系 概率图模型(Probabilistic graphical model):用图表示的概率分布。模型定义 定义：给定一个联合概率分布P(Y)和表示它的无向图G，定义无向图表示的随机变量之间存在的 成对马尔可夫性(pairwise Markov property)局部马尔可夫性(local Markov properly)全局马尔可夫性(global Markov property)模型定义 成对马尔可夫性(Pairwise Markov property)设u和v是无向图G中任意两个没有边连接的结点，结点u和v分别对应随机变量Yu和Yv，其它所有结点为O，对应的随机变量组是Y0 给定随机变量组Y0的条件下随机变量Yu和Yv是条件独立的模型定义 局部马尔可夫性(Local Markov properly)v：任意结点 w：与v有边相连的结点 O：其它结点 在时，等价于模型定义 全局马尔可夫性(Global Markov property)结点集合A,B是在无向图G中被结点集合C分开的任意结点集合，模型定义 概率无向图模型（马尔可夫随机场(Markov random field)）设有联合概率分布P(Y),由无向图G=(V,E)表示，在图G中，结点表示随机变量，边表示随机变量之间的依赖关系,如果联合概率分布P(Y)满足成对、局部或全局马尔可夫性，就称此联合概率分布为概率无向图模型(probability undirected graphical model)，或马尔可夫随机场(Markov random field).问题关键：求联合概率，引申为对联合概率进行因子分解。概率无向图模型的因子分解 定义：团、最大团 无向图G中任何两个结点均有边连接的结点子集称为团(clique)。若C是无向图G的一个团，井且不能再加进任何一个c的结点使其成为一个更大的团，则称此C为最大团(maximal clique).两个结点的团？三个结点的团？概率无向图模型的因子分解 将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作，称为概率无向图模型的因子分解(Factorization).给定概率无向图模型，设其无向图为G，C为G上的最大团，Yc表示C对应的随机变量，那么概率无向图模型的联合概率分布P(Y)可写作图中所有最大团C上的函数的乘积形式，即 Z是规范化因子(normalization factor)概率无向图模型的因子分解 势函数：定理(Hammersley-Clifford定理)：概率无向图模型的联合概率分布P(Y)可以表示为如下形式:三、条件随机场的定义与形式 条件随机场(conditional random field)的定义：给定随机变量X条件下，随机变量Y的马尔可夫随机场。定义在线性链上的特殊的条件随机场：线性链条件随机场(linear chain conditional random field)线性链条件随机场可以用于标注等问题；在条件概率模型P(Y|X)中，Y是输出变量，表示标记序列，X是输入变量，表示需要标注的观测序列，也把标记序列称为状态序列。条件随机场的定义与形式 条件随机场：设X与Y是随机变量，P(Y|X)是在给定X的条件下Y的条件概率分布，若随机变量Y构成一个由无向图G=(V,E)表示的马尔可夫随机场，即满足马尔科夫性 对任意结点v成立，则称条件概率分布P(Y|X)为条件随机场，式中wv表示在图G=(V,E)中与结点v有边连接的所有结点w，wv表示结点v以外的所有结点。条件随机场的定义与形式 线性链情况：最大团是相邻两个结点的集合,线性链条件随机场:条件随机场的定义与形式 定义(线性链条件随机场)设均为线性链表示的随机变量序列，若在给定随机变量序列X的条件下，随机变量序列Y的条件概率分布P(Y|X)构成条件随机场。即满足马尔可夫性 则称P(Y|X)为线性链条件随机场。在标注问题中，X表示输入观测序列，Y表示对应的输出标记序列或状态序列.条件随机场的参数化形式 定理：(线性链条件随机场的参数化形式)：设P(Y|X)为线性链条件随机场，则在随机变量X取值为x的条件下，随机变量Y取值为y的条件概率具有如下形式:其中：tk定义在边上的特征函数，转移特征，依赖于前一个和当前位置，sl定义在结点上的特征函数，状态特征，依赖于当前位置条件随机场的参数化形式 例：词性标注问题：输入观测为 X=(X1,X2,X3),输出标记为Y=(Y1,Y2,Y3),Y1,Y2,Y3 取值于1,2假设转移特征和状态特征对应的权值，只注明特征取值为1，为0省略条件随机场的参数化形式 对给定的观测序列x，标记序列Y=(1,2,2)的非规范化条件概率为条件随机场的简化形式 注意到条件随机场中同一特征在各个位置都有定义，可以对同一个特征在各个位置求和，将局部特征函数转化为一个全局特征函数，这样就可以将条件随机场写成权值向量和特征向量的内积形式，即条件随机场的简化形式。首先将转移特征和状态特征及其权值用统一的符号表示，设有k1个转移特征，k2个状态特征，K=k1+k2,记条件随机场的简化形式 然后，对转移与状态特征在各个位置i求和，记作 权值：条件随机场可表示为：条件随机场的简化形式 若w表示权值向量：以F(y,x)表示全局特征向量，即 条件随机场写成内积：条件随机场的矩阵形式 线性链条件随机场，引进特殊的起点和终点状态标记Yo=start，Yn+1=stop，这时Pw(y|x)可以通过矩阵形式表示。对观测序列x的每一个位置i=1,2,.n+1，定义一个m阶矩阵(m是标记Yi取值的个数)条件随机场的矩阵形式 给定观测序列x，标记序列y的非规范化概率可以通过n+l个矩阵的乘积表示：条件概率Pw(y|x)：Zw(x)为规范化因子，是n+1个矩阵的乘积的(start,stop)元素条件随机场的矩阵形式 例：线性链条件随机场，观测序列x，状态序列y,i=1,2,3 n=3,标记yi属于1，2，假设 yo=start=1，y4=stop=1，各个位置的随机矩阵：试求状态序列y以start为起点stop为终点所有路径的非规范化概率及规范化因子。条件随机场的矩阵形式 解：首先计算从start到stop对应与y=(1,1,1),y=(1,1,2),.y=(2,2,2）各路径的非规范化概率分别是：求规范化因子，通过计算矩阵乘积，第1行第1列的元素为：恰好等于从start到stop的所有路径的非规范化概率之和，及规范化因子。四、条件随机场的概率计算问题 条件随机场的概率计算问题 给定条件随机场P(Y|X),输入序列x和输出序列y，计算条件概率：以及相应的数学期望问题。引进前向-后向向量，递归计算。条件随机场的概率计算问题 前向-后向算法：对每个指标i=0,1,n+1,定义前向向量 递推公式：又可表示为：即表示在位置i的标记是yi，且到位置i的前部分标记序列的非规范化概率，yi可取的值m个，所以是m维列向量。条件随机场的概率计算问题 前向-后向算法：同样，对每个指标i=0,1,n+1,定义后向向量 又可表示为：即表示在位置i的标记是yi，且从位置i+1到n的后部分标记序列的非规范化概率 前向-后向得：条件随机场的概率计算问题 概率计算 按照前向-后向向量的定义，可计算标记序列在位置i是标记yi的条件概率 和在位置i-1与i是标记yi-1和yi的条件概率：其中：条件随机场的概率计算问题 期望值的计算 利用前向-后向向量，可以计算特征函数关于联合分布P(X,Y)和条件分布P(Y|X)的数学期望。特征函数fk关于条件分布P(Y|X)的数学期望是：其中：条件随机场的概率计算问题 假设经验分布为：特征函数fk关于联合分布P(X,Y)的数学期望是：五、条件随机场的学习算法 改进的迭代尺度法：已知训练数据集，可知经验分布：可通过极大化训练数据的对数似然函数来求模型参数：似然函数：当P为条件随机场模型时：条件随机场的学习算法 改进的迭代尺度法：不断优化对数似然函数改变量的下界：假设模型当前参数向量：向量增量：更新向量：关于转移特征tk的更新方程：条件随机场的学习算法 改进的迭代尺度法：关于转移特征sl的更新方程：T(x,y)是在数据(x,y)中出现所有特征数的总和条件随机场的学习算法 条件随机场模型学习的改进的迭代尺度法：条件随机场的学习算法 条件随机场模型学习的改进的迭代尺度法：条件随机场的学习算法 算法S T(x,y)表示数据(x,y)中的特征总数，对不同的数据(x,y)取值可能不同，定义松弛特征：S为大的常数，使得对训练数据集所有(x,y)条件随机场的学习算法 算法S 对于转移特征：的更新方程为：其中：条件随机场的学习算法 算法S 对于状态特征：的更新方程为：其中：因担心S过大，每个观测序列x计算其特征最大值利用前向-后向公式计算T(x)=t条件随机场的学习算法 算法T 因担心S过大，每个观测序列x计算其特征最大值利用前向-后向公式计算 T(x)=t条件随机场的学习算法 算法T 关于转移特征参数的更新方程可以写成：条件随机场的学习算法 算法T 关于状态特征的参数更新方程可以写成：拟牛顿法：拟牛顿法：学习的优化目标函数：梯度函数：拟牛顿法：条件随机场模型学习的BFGS算法拟牛顿法：条件随机场模型学习的BFGS算法六、条件随机场的预测算法 预测算法：给定条件随机场P(Y|X)和输入序列(观测序列)x,求：条件概率最大的输出序列(标记序列)y*,维特比算法：由：非规范化概率最大的最优路径条件随机场的预测算法 路径表示标记序列：只计算非规范化概率：为局部特征向量条件随机场的预测算法 维特比算法：首先求出位置1的各个标记j=1,2.m的非规范化概率：由递推公式，求出到位置i的各个标记l=1,2m的非规范化概率的最大值，同时记录最大值路径：条件随机场的预测算法 维特比算法：直到i=n时终止，这时求得非规范化概率的最大值为：及最优路径的终点：由此最优路径终点返回：得最优路径：条件随机场的预测算法 条件随机场预测的维特比算法：条件随机场的预测算法 条件随机场预测的维特比算法：条件随机场的预测算法 例：用维特比算法求给定输入序列（观测序列）x对应的最优输出序列（标记序列）利用维特比法求最优路径问题：条件随机场的预测算法ENDQ&R
