直接用概率求和规则消去 R R R显然不行每个变量仅有两种取值的,复杂度至少 O ( 2 ∣ Y ∣ + ∣ R ∣ ) O(2^{|Y|+|R|}) O(2∣Y∣+∣R∣).另一面,属性变量间存在复杂联系因此概率模型的学习,即基于训练样本来估计变量分布的参数往往很难需有一套能简洁紧凑地表达变量间关系的工具
probabilistic graphical model 用一个结点表示一个或一组随机变量边表示变量间的概率相关关系,即“变量关系图”. 概率图模型分两 有向无环图：有向图模型或贝叶斯网无向图：无向图模型或马尔可夫网
HMM是结构最简单的动态贝叶斯网著名的有向图模型,用于时序数据建模,语音识别、自然语言处理
如图14.1 HMM中变量分两状态 y 1 , y 2 , ⋯ , y n {y_1,y_2,\cdots,y_n} y1,y2,⋯,yn, y i ∈ Y y_i\in\mathcal{Y} yi∈Y 隐藏的、不可观测的 观测 x 1 , x 2 , ⋯ , x n {x_1,x_2,\cdots,x_n} x1,x2,⋯,xn, x ∈ X x\in\mathcal{X} x∈X系统在状态 s 1 , s 2 , ⋯ , s N {s_1,s_2,\cdots,s_N} s1,s2,⋯,sN间转换 y i y_i yi的取值范围 Y \mathcal{Y} Y(状态空间)通常有 N N N个取值 x i x_i xi可离散也可连续 为便论,仅考虑离散,范围为 { o 1 , o 2 , ⋯ , o M } \{o_1,o_2,\cdots,o_M\} {o1,o2,⋯,oM}
x t x_t xt由 y t y_t yt确定,与其他状态变、观测的取值无关 t t t时刻的状态 y t y_t yt仅依赖 t − 1 t-1 t−1时刻的状态 y t − 1 y_{t-1} yt−1此即Markov chain所有变量的联概为 P ( x 1 , y 1 , ⋯ , x n , y n ) = P ( y 1 ) P ( x 1 ∣ y 1 ) ∏ i = 2 n P ( y i ∣ y i − 1 ) P ( x i ∣ y i ) (14.1) P(x_1,y_1,\cdots,x_n,y_n)=P(y_1)P(x_1|y_1)\prod _{i=2}^nP(y_i|y_{i-1})P(x_i|y_i)\tag{14.1} P(x1,y1,⋯,xn,yn)=P(y1)P(x1∣y1)i=2∏nP(yi∣yi−1)P(xi∣yi)(14.1)
除结构信息,欲确定一个HMM还需下三状转概:在各个状态间转换的概率,记为 A = [ A i j ] N × N A=[A_{ij}]_{N\times N} A=[Aij]N×N a i j a_{ij} aij 在任意时刻 t t t,若状态为 s i s_i si;则下一时刻状态为 s j s_j sj的概率 输出观概:当前状态获得各个观测值的概率,记为 B = [ B i j ] N × M B=[B_{ij}]_{N\times M} B=[Bij]N×M b i j b_{ij} bij: 任意时刻 t t t,若状态为 s i s_i si,则观测值 o j o_j oj被获取的概率 初态概:记 π = ( π 1 , . . . π N ) \pi=(\pi_1,...\pi_N) π=(π1,...πN) π i : \pi_i: πi:模型的初始状态为 s i s_i si的概率.
通过指定状态空间、观测空间和上述三组参数,就能确定一个隐马尔可夫模型,用其参数 λ = [ A , B , π ] \lambda=[A,B,\pi] λ=[A,B,π]来指代给定隐马尔可夫模型 λ \lambda λ, 它按如下过程产生观测序列 { x 1 , . . . , x n } \{x_1,...,x_n\} {x1,...,xn}
这儿的东西我觉得比较简单，再吵就浪费了
上述问题在现实应用中非常重要.许多任务需根据以往的观测序列 { x 1 , x 2 , x n − 1 } \{x_1,x_2,x_{n-1}\} {x1,x2,xn−1} 推测当前时刻最有可能的观测值 x n x_n xn,这显然可转化为求取概率 P ( x ∣ λ ) P(x|\lambda) P(x∣λ) 语音识别等中, 观测值为语音信号隐藏状态为文字目标就是根据观测信号来推断最有可能的状态序列(即对应的文字) 人工指定模型参数已变得越来越不可行,如何根据训练样本学得最优的模型参数,基于式(14.1)的条件独立性,隐马尔可夫模型的这三个问题均能被高效求解.
{1,2},{1,3},{2,4},{2,5},{2,6},{3,5},{5,6}和{2,5,6}都是团, 除{2,5},{2,6}和{5,6}外都极大团
MRF中多个变量之间的联合概率分布能基于团分解为多个因子的乘积,每个因子仅与一个团相关对n个变量 x = { x 1 , x 2 , . . . , x n } x=\{x_1,x_2,...,x_n\} x={x1,x2,...,xn},所有团构成的集合为 C C C,与团 Q ∈ C Q\in C Q∈C对应的变量集合记为 x Q x_Q xQ,则联合概率 P ( x ) = 1 Z ∏ Q ∈ C ψ Q ( x Q ) (14.2) P(x)=\frac 1Z\prod_{Q\in C}\psi_Q(x_Q)\tag{14.2} P(x)=Z1Q∈C∏ψQ(xQ)(14.2) 与团 Q Q Q对应的势函数, 用于对团 Q Q Q中的变量关系进行建模 实际中,精确算Z难,许多任务不需Z精确值
P ( x ) P(x) P(x)可基于极大团定义.假定所有极大团构成的集合为 C ∗ C^* C∗:,则 P ( x ) = 1 Z ∗ ∏ Q ∈ C ∗ ψ Q ( x Q ) (14.3) P(x)=\frac {1}{Z^*}\prod_{Q\in C^*}\psi_Q(x_Q)\tag{14.3} P(x)=Z∗1Q∈C∗∏ψQ(xQ)(14.3)图14.2联合概率分布
P ( x ) = 1 Z ψ 12 ψ 13 ψ 24 ψ 35 ψ 256 P(x)=\frac 1Z \psi_{12}\psi_{13}\psi_{24}\psi_{35}\psi_{256} P(x)=Z1ψ12ψ13ψ24ψ35ψ256
势函数256定义在极大团2,5,6上,由于它的存在,不需为团{2,5},{2,6}和{5,6}构建势函数MRF中如何得到“条件独立性”图14.3,若从A中的结点到B中的结点都必须经过C中的结点, 则称A和B被C分离,C称为“分离集” 对马尔可夫随机场,有“全局马尔可夫性” 给定两个变量子集的分离集则这两个变量子集条件独立A,B和C对应的变量集分别为 x A x_A xA, x B x_B xB和 x c x_c xc则 x A x_A xA和 x B x_B xB在给定 x C x_C xC的条件下独立, 记为 x A ⊥ x B ∣ x C x_A⊥x_B|x_C xA⊥xB∣xC
验证图14.3中的A,B和C分别对应单变量 x A x_A xA, x B x_B xB和 x C x_C xC简化为图14.4
对图14.4
由全局马尔可夫性得两推论局部马尔可夫性: V V V为图的结点集 n ( v ) n(v) n(v)为结点 v v v在图上的邻接结点 n ∗ ( v ) = n ( v ) { v } n^*(v)=n(v)\{v\} n∗(v)=n(v){v}有 成对马尔可夫性: 令图的结点集和边集分别为 V V V和 E E E,对图中的两个结点 u u u和 v v v
ψ Q ( x Q ) \psi_Q(x_Q) ψQ(xQ) 定量刻画变量集 x Q x_Q xQ中变量之间的相关关系,非负且在所偏好的变量取值上有较大值 假定图14.4中的变量均为二值变量,若势函数为 则说明该模型偏好变量 x A x_A xA与 x C x_C xC拥有相同的取值, x B x_B xB与 x C x_C xC拥有不同取值 该模型中 x A x_A xA与 x B x_B xB正相关, x B x_B xB与 x C x_C xC负相关.结合式(14.2),令 x A x_A xA与 x C x_C xC相同且 x B x_B xB与 x C x_C xC不同的变量值 指派将取得较高的联合概率
为满足非负性,指数函数常被用于定义势函数,即 H Q ( x Q ) H_Q(x_Q) HQ(xQ)是一个定义在变量 x Q x_Q xQ上的实值函数, 常见形式为 谁和谁是参数.第二项仅考虑单结点第一项考虑每一对结点
CRF试图对多个变量在给定观测值后的条件概率建模令 x = { x 1 , x 2 , ⋯ , x n } x=\{x_1,x_2,\cdots,x_n\} x={x1,x2,⋯,xn}为观测序列 y = { y 1 , y 2 , ⋯ , y n } y=\{y_1,y_2,\cdots,y_n\} y={y1,y2,⋯,yn}为与之相应的标记序列,则CRF目标是构建条件概率 P ( y ∣ x ) P(y|x) P(y∣x) 标记变量 y y y可以是结构型变量,即其分量之间有某种相关性如自然语言处理的词性标注中 观测数据为语句(即单词序列)标记为相应的词性序列,具有线性序列结构,如图14.5(a) 语法分析中,输出标记是语法树,具有树形结构,如图14.5(b)
G = < V , E > G=<V,E> G=<V,E>表示结点与标记変量 y y y中元素一一对应的无向图 y v y_v yv:与结点 v v v对应的标记变量, n ( v ) n(v) n(v)表示结点 v v v的邻接结点,若图 G G G的每个变量 y v y_v yv都满足马尔可夫性 则 ( y , x ) (y,x) (y,x)构成一个条件随机场
图 G G G可有任意结构,只要能表示标记变量之间的条件独立性即可但现实中,尤其是对标记序列建模时,常用图14.6的链式结构,即“链式条件随机场”( chain-structured CRF)下面主要讨论这
与MRF定义联合概率方式类似CRF用势函数和图结构上的团来定义条件概率 P ( y ∣ x ) P(y|x) P(y∣x)给定观测序列 x x x, 图14.6的链式条件随机场含两种关于标记变量的团,单个标记变量 { y i } \{y_i\} {yi}及相邻的标记变量 { y i − 1 , y i } \{y_{i-1},y_i\} {yi−1,yi}选择合适的势函数,即可得到形如式(14.2)的条件概率定义 CRF中,通过选用指数势函数并引入特征函数,条件概率被定义为 t j ( y i + 1 , y i , x , i ) t_j(y_{i+1},y_i,x,i) tj(yi+1,yi,x,i)是定义在观测序列的两个相邻标记位置上的转移特征函数, 刻画相邻标记变量间的相关关系及观测序列对它们的影响 s k ( y i , x , i ) s_k(y_i,x,i) sk(yi,x,i)定义在观测序列的标记位置 i i i上的状态特征函数 刻画观测序列对标记变量的影响 谁俩为参数
要用CRF,还需定义合适的特征函数特征函数常是实值,以刻画数据的一些很可能成立 或期望成立的经验特性 图14.5(a)的词性标注若用转移特征函数 表示第 i i i个观测值 x i x_i xi为单词“knock”时, 相应的标记 y i y_i yi和 y i + 1 y_{i+1} yi+1很可能分别为[V]和[P] 若用状态特征函数 表示观测值 x i x_i xi为单词 knock”时,它所对应的标记很可能为[V]
对比(14.1)和(14.2),CRF和MRF均用团上的势函数定义概率两者在形式上没区别但CRF是条件概率 MRF是联合概率
对概率图模型,还需确定具体分布的参数,这称参数估计或参数学习问 题,常用极大似然估计或最大后验概率估计求解若将参数视为待推测变量,则参数估计过程和推断十分相似,可以“吸收”到推断问题下面只讨论概率图模型的推断方法
图模型对应的变量集 x = { x 1 , x 2 , ⋯ , x N } x=\{x_1,x_2,\cdots,x_N\} x={x1,x2,⋯,xN}分 x E x_E xE和 x F x_F xF两个不相交的,推断问题的目标是计算边际概率 P ( x F ) P(x_F) P(xF)或 P ( x F ∣ x E ) P(x_F|x_E) P(xF∣xE) 联合概率可基于概率图模型获得,因此,推断问题的关键就是如何高效地计算边际分布
概率图模型推断方法分两类.精确推断,希望能计算出目标变量的边际分布或条件分布的精确值; 复杂度随着极大团规模增长呈指数增长,适用范围有限 近似推断方法,希望较低时间复杂度下获得原问题近似解; 此类方法在现实中更常用 本节两种代表性的精确推断,下一节近似推断
图14.7(a)的有向图模型来介绍工作流程
假定推断目标是计算 P ( x 5 ) P(x_5) P(x5)只需通过加法消去变量 { x 1 , x 2 , x 3 , x 4 } \{x_1,x_2,x_3,x_4\} {x1,x2,x3,x4},即
