做蛋糕的企业网站,北斗手表官方网站,图片搜索识图入口,网站建设开发费会计处理文章目录1 条件随机场定义1.1 马尔科夫随机场1.1.1 用图模型表示概率1.1.3 三个马尔科夫性1.1.3 重点再看局部马尔科夫性1.2 马尔科夫随机场的因子分解1.3 条件随机场1.4 线性链条件随机场2线性链条件随机场的表示形式2.1 参数化形式2.2 简化形式2.3 矩阵形式3 条件随机场的概率…
文章目录1 条件随机场定义1.1 马尔科夫随机场1.1.1 用图模型表示概率1.1.3 三个马尔科夫性1.1.3 重点再看局部马尔科夫性1.2 马尔科夫随机场的因子分解1.3 条件随机场1.4 线性链条件随机场2线性链条件随机场的表示形式2.1 参数化形式2.2 简化形式2.3 矩阵形式3 条件随机场的概率计算4 条件随机场的学习算法4.1 最大熵模型4.1.1最大熵模型定义4.1.2 最大熵模型学习4.2 条件随机场的学习算法5 条件随机场的预测算法1 条件随机场定义
1.1 马尔科夫随机场
1.1.1 用图模型表示概率
图G(V,E)V表示顶点集合E表示边的集合。
概率图模型表示用图表示概率的分布。
可以用无向图G表示联合概率分布P(Y)。Y一定是一个矢量。 顶点v∈Vv \in Vv∈V表示一个随机变量YvY_vYvY(Yv)v∈VY (Y_v)_{v \in V}Y(Yv)v∈V。 边e∈Ee \in Ee∈E表示随机变量之间的概率依赖关系。
这样对联合概率分布的计算转为对无向图的计算。联合概率分布P(Y)需要满足三个马尔科夫性。
1.1.3 三个马尔科夫性
1 成对马尔科夫性 讲的是两个没有边连接的节点联合概率等于概率的乘积。 假设无向图G中u和v是两个没有边连接的结点分别对应随机变量YuY_uYuYvY_vYv。其他所有节点为O对应随机变量组YOY_OYO。那么 P(Yu,Yv∣YO)P(Yu∣YO)P(Yv∣YO)P(Y_u,Y_v|Y_O)P(Y_u|Y_O)P(Y_v|Y_O)P(Yu,Yv∣YO)P(Yu∣YO)P(Yv∣YO)
2 局部马尔科夫性 讲的是一个节点和与它没有任何边连接的节点的集合联合概率等于概率的乘积。 假设无向图G中v是任意一个结点对应随机变量YvY_vYv。W是与v有边连接的所有节点的集合对应随机变量组YWY_WYW。O是v和W之外的所有节点对应随机变量组YOY_OYO。那么 P(Yv,YO∣YW)P(Yv∣YW)P(YO∣YW)P(Y_v,Y_O|Y_W)P(Y_v|Y_W)P(Y_O|Y_W)P(Yv,YO∣YW)P(Yv∣YW)P(YO∣YW)
3 全局马尔科夫性 讲的是两个集合一个集合中的任意一个点与另外一个集合中的任意一个点没有边连接 那两个集合的联合概率等于概率的乘积。 假设节点集合A、B是在无向图G中被集合C分开的任意节点的集合分别对应随机变量组YAY_AYA,YBY_BYB,YCY_CYC。那么 P(YA,YB∣YC)P(YA∣YC)P(YB∣YC)P(Y_A,Y_B|Y_C)P(Y_A|Y_C)P(Y_B|Y_C)P(YA,YB∣YC)P(YA∣YC)P(YB∣YC)
1.1.3 重点再看局部马尔科夫性
成对马尔科夫性局部马尔科夫性以及全局马尔科夫性是等价的。
v是无向图G中任意一个结点对应随机变量YvY_vYv。 W是与v有边链接的所有结点对应随机变量组是YWY_WYW。 O是vW以外的所有结点对应随机变量组是YOY_OYO。 那么 P(Yv,YO∣YW)P(Yv∣YW)P(YO∣YW)P(Y_v,Y_O|Y_W) P(Y_v|Y_W)P(Y_O|Y_W)P(Yv,YO∣YW)P(Yv∣YW)P(YO∣YW)说明给定YWY_WYW条件下YvY_vYv和YOY_OYO是条件独立的。也就是说v只与W有关系。 如图所示W表示所有与v相连的点。O表示除v和W之外的所有点。
我们再看P(Yv,YO∣YW)P(Yv∣YO,YW)P(YO∣YW)P(Y_v,Y_O|Y_W) P(Y_v|Y_O,Y_W)P(Y_O|Y_W)P(Yv,YO∣YW)P(Yv∣YO,YW)P(YO∣YW)(根据条件概率公式)
两个公式联合起来得到结论P(Yv∣YW)P(Yv∣YO,YW)P(Y_v|Y_W) P(Y_v|Y_O,Y_W)P(Yv∣YW)P(Yv∣YO,YW)记为公式1
1.2 马尔科夫随机场的因子分解
团无向图中任意两个结点均有边相连的节点子集。 最⼤团⽆向图 中的⼀个团并且不能再加进任何⼀个结点使其成为⼀个更⼤的团。 这个图中的最大团是(v1,v2,v3)或者(v1,v3,v4) 概率无向图的联合概率分布P(Y)1Z∏CΦC(YC)P(Y) \dfrac{1}{Z}\prod_C \Phi_C(Y_C)P(Y)Z1∏CΦC(YC) 概率无向图的联合概率分布就等于所有最大团的一个累乘所有最大团上势函数的累乘 其中C是无向图的最大团YCY_CYC是C的节点对应的随机变量 势函数ΦC(YC)exp{−E(YC)}\Phi_C(Y_C)exp\{-E(Y_C)\}ΦC(YC)exp{−E(YC)} Z是规范化因子是一个全概率分布Z∑Y∏CΦC(YC)Z\sum_Y\prod_C\Phi_C(Y_C)Z∑Y∏CΦC(YC) 乘积是在无向图所有的最大图上进行的。 势函数会根据模型的不同而不同。
1.3 条件随机场
设X与Y是随机变量P(Y|X)是在给定X的条件下Y的条件概率分布。如果Y构成一个由无向图G表示的马尔科夫随机场则称条件概率分布P(Y|X)为条件随机场。 对于任意v都有P(Yv∣X,Yw,w≠v)P(Yv∣X,Yw,w−v)P(Y_v|X,Y_w,w\ne v) P(Y_v|X,Y_w,w-v)P(Yv∣X,Yw,wv)P(Yv∣X,Yw,w−v) w-v表示w是与v相连的所有点。也就是说v事件发生的概率只与与它相连的点有关系。 说明X是Y的条件X是输入Y是输出。 这个公式的由来是从公式1对比得到的。增加了条件X。 这个公式可以描述为任意一个节点v的在与它有边相连的条件下的概率等于非v条件下的概率。
1.4 线性链条件随机场
再进一步约束我们用无向图G表示事件Y的概率Y中包含Y1,Y2,Y3…Yn。这些事件之间具有线性关系。 再假设条件XX包含X1,X2,X3…Xn。X和Y之间具有线性关系。如下图所示。
也就是说加上条件Y是具有线性关系的X和Y具有相同的线性结构。上面的公式可以写为P(Yi∣X,Y1,Y2...Yi−1,Yi1,...Yn)P(Yi∣X,Yi−1,Yi1)P(Y_i|X,Y_1,Y_2...Y_{i-1},Y_{i1},...Y_n) P(Y_i|X,Y_{i-1},Y_{i1})P(Yi∣X,Y1,Y2...Yi−1,Yi1,...Yn)P(Yi∣X,Yi−1,Yi1)。这个公式称为线性链条件随机场。记为公式2。 与节点i有边相连的节点时候i−1i-1i−1和i1i1i1。 不等于i的节点有12…i-1,i1,…n X是条件
2线性链条件随机场的表示形式 可以看到在图中是有7个最大团。计算P(Y|X)就是所有最大团的势函数的累乘。
2.1 参数化形式
定义了每个节点和每条边的特征函数用特征函数表示概率。 P(Y)s1t1s2t2...tn−1snP(Y)s_1t_1s_2t_2...t_{n-1}s_nP(Y)s1t1s2t2...tn−1sn 设P(Y|X)为线性链条件随机场则在随机变量X取值为x的条件下随机变量Y取值为y的条件概率
其中 tkt_ktk是定义在边上的特征函数。依赖于当前和前一个位置。 sls_lsl是定义在结点上的特征函数称为状态特征依赖于当前位置。 tkt_ktk和sls_lsl值为1或者0。 λk\lambda_kλk和μl\mu_lμl是对应的权值。 Z(x)是规范化因子求和是在所有可能的输出序列上。
注意这两句话没理解明白暂时记录在这里。 sls_lsl的个数应该等于边的个数 x 每个顶点可能的取值集合个数 tkt_ktk个数边的个数 x第一个顶点取值个数 x 第二个顶点取值个数
这是按照上面最大团的定义来确定的。
2.2 简化形式
用fkf_kfk表示边的特征函数和节点的特征函数。 设有K1K_1K1个边的特征函数有K2K_2K2个节点的特征函数KK1K2KK_1K_2KK1K2
用wkw_kwk表示边的权重和节点的权重。
则条件随机场表示为
用向量化表示为 P(y∣x)exp(w.F(y,x))Zw(x)P(y|x)\dfrac{exp(w.F(y,x))}{Z_w(x)}P(y∣x)Zw(x)exp(w.F(y,x))其中 Zw(x)∑yexpw.F(y,x)Z_w(x) \sum_y expw.F(y,x)Zw(x)∑yexpw.F(y,x)
2.3 矩阵形式
引入一个特殊的起点标记y0starty_0starty0start表示开始状态yn1stopy_{n1}stopyn1stop表示终止状态。定义一个m阶矩阵。 m是yiy_iyi取值的个数。 如果yiy_iyi表示骰子出现的某一面那么m6如果yiy_iyi表示一枚硬件哪面朝上那么m2。
P(y∣x)1Zw(x)∏i1n1Mi(yi−1,yi∣x)P(y|x) \dfrac{1}{Z_w(x)}\prod^{n1}_{i1}M_i(y_{i-1},y_i|x)P(y∣x)Zw(x)1∏i1n1Mi(yi−1,yi∣x)
其中Zw(x)(M1(x),M2(x),...Mn1(x))start,stopZ_w(x)(M_1(x),M_2(x),...M_{n1}(x))_{start,stop}Zw(x)(M1(x),M2(x),...Mn1(x))start,stop
矩阵最关注矩阵的形状。
3 条件随机场的概率计算
条件随机场的概率计算问题是计算条件概率P(Yiyi∣x)P(Y_iy_i|x)P(Yiyi∣x),P(Yi−1yi−1,Yiyi∣x)P(Y_{i-1}y_{i-1},Y_{i}y_i|x)P(Yi−1yi−1,Yiyi∣x) 以及它们的希望。
前向计算 后向计算 计算特征函数fk(x,y)f_k(x,y)fk(x,y)关于条件分布P(Y|X)的数学期望
计算特征函数fk(x,y)f_k(x,y)fk(x,y)关于联合分布P(X,Y)的数学期望
这里的结果是中间量
4 条件随机场的学习算法
4.1 最大熵模型
4.1.1最大熵模型定义
模型就是一个从输入到输出的一个映射可以是一个f(x)也可以是一个P(y|x)。当在所有条件都满足的时候这个函数不唯一的时候就使用最大熵策略来选择模型。所以最大熵模型是一种选择策略是一种世界观。
熵最大变量几乎可以均匀分布
假设分类模型是条件概率分布P(Y|X)。给定条件X以条件概率P(Y|X)输出Y。 给定训练集可以确定联合分布P(X,Y)的经验分布和边缘分布P(X)的经验分布分别以P^(X,Y)\hat{P}(X,Y)P^(X,Y)和P^(X)\hat{P}(X)P^(X)。这里 P^(Xx,Yy)v(Xx,Yy)N\hat{P}(Xx,Yy)\dfrac{v(Xx,Yy)}{N}P^(Xx,Yy)Nv(Xx,Yy) P^(Xx)v(Xx)N\hat{P}(Xx)\dfrac{v(Xx)}{N}P^(Xx)Nv(Xx)
其中v(Xx,Yy)v(Xx,Yy)v(Xx,Yy)表示训练样本中(x,y)出现的频率v(Xx)v(Xx)v(Xx)表示训练样本中x出现的频率。N表示样本容量。
特征函数f(x,y)描述输入x和y之间的某一事实。 特征函数f(x,y)关于经验分布P^(X,Y)\hat{P}(X,Y)P^(X,Y)的期望: EP^(f)∑x,yP^(x,y)f(x,y)∑x,yP^(x)P^(y∣x)f(x,y)E_{\hat{P}}(f)\sum_{x,y}\hat{P}(x,y)f(x,y)\sum_{x,y}\hat{P}(x)\hat{P}(y|x)f(x,y)EP^(f)∑x,yP^(x,y)f(x,y)∑x,yP^(x)P^(y∣x)f(x,y)(公式1)
特征函数f(x,y)关于模型P(Y|X)与经验分布P^(X)\hat{P}(X)P^(X)的期望 EP(f)∑x,yP^(x)P(y∣x)f(x,y)E_{P}(f)\sum_{x,y}\hat{P}(x)P(y|x)f(x,y)EP(f)∑x,yP^(x)P(y∣x)f(x,y)(公式2)
假设特征函数f(x,y)关于经验分布P^(X,Y)\hat{P}(X,Y)P^(X,Y)的期望应该等于关于模型P(Y|X)与经验分布P^(X)\hat{P}(X)P^(X)的期望。那么P(y∣x)P^(y∣x)P(y|x)\hat{P}(y|x)P(y∣x)P^(y∣x)对比公式1和公式2也就是说数据集的条件概率分布可以反映出模型的条件概率分布。这就可以达到我们的目的了。
最⼤熵模型假设满⾜所有约束条件的模型集合为
定义在条件概率分布P(Y|X)上的条件熵为 H(P)−∑x,yP^(x)P(y∣x)logP(y∣x)H(P)-\sum_{x,y}\hat{P}(x)P(y|x)logP(y|x)H(P)−∑x,yP^(x)P(y∣x)logP(y∣x)
4.1.2 最大熵模型学习
优化函数
拉格朗日乘子法 1 构建拉格朗日乘子
2 求min 3 求max 最⼤熵模型的极⼤似然估计等价于对偶函数极⼤化。 对偶函数如下
4 模型学习迭代尺度法
这部分的学习跳过了。直接用结论。
4.2 条件随机场的学习算法
由训练数集计算经验概率分布P^(X,Y)\hat{P}(X,Y)P^(X,Y)。 目标函数是对数似然函数。计算其中的参数W
5 条件随机场的预测算法
给定条件随机场P(Y|X)和输入观测序列x求条件概率最大的标记序列y*。 维特比算法。 公式太多没有记录。
