机器学习004-Markov Property

Markov property:

在一连串随机事件中，事件的概率只和当前状态有关，而与前面的事件无关。

Markov chain:

满足Markov property的随机模型

条件随机场

条件随机场（conditional random field,CRF）是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔可夫随机场。

概率无向图模型（马尔科夫随机场）

模型定义

成对、局部、全局马尔科夫特性：

成对：

u，v是无向图中没有边连接的两个结点，o是其他结点。Y是对应的随机变量。
局部：

式（11.3）说明：Yw和Yo相互独立

全局：

定义11.1（概率无向图模型/马尔科夫随机场）　设有联合概率分布P(Y)，由无向图G＝(V,E)表示，在图G中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布P(Y)满足成对、局部或全局马尔可夫性，就称此联合概率分布为概率无向图模型（probability undirected graphical model），或马尔可夫随机场（Markov random field）。

【个人理解】马尔科夫性即 当前事件的概率只与相邻的事件有关系，且其他事件相互独立。

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

概率无向图的因子分解

定义11.2（团与最大团）　无向图G中任何两个结点均有边连接的结点子集称为团（clique）。若C是无向图G的一个团，并且不能再加进任何一个G的结点使其成为一个更大的团，则称此C为最大团（maximal clique）。

将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作，称为概率无向图模型的因子分解（factorization）。

给定概率无向图模型，设其无向图为G，C为G上的最大团，YC表示C对应的随机变量。那么概率无向图模型的联合概率分布P(Y)可写作图中所有最大团C上的函数ΨC(YC)的乘积形式，即

其中，Z是规范化因子（normalization factor），由式

给出。规范化因子保证P(Y)构成一个概率分布。函数ΨC(YC)称为势函数（potentialfunction）。这里要求势函数ΨC(YC)是严格正的，通常定义为指数函数：

条件随机场的定义与形式

条件随机场的定义

条件随机场（conditional random field）是给定随机变量X条件下，随机变量Y的马尔可夫随机场。 若随机变量Y构成一个由无向图G＝(V,E)表示的马尔可夫随机场，即

对任意结点v成立，则称条件概率分布P(Y|X)为条件随机场。式中w～v表示在图G＝(V,E)中与结点v有边连接的所有结点w，w≠v表示结点v以外的所有结点，Yv，Yu与Yw为结点v，u与w对应的随机变量。

条件随机场的参数化形式

对 P(y|x) 进行因子分解，若只考虑线性链条件随机场的情况，则只要考虑该事件的前后位置：

式（11.10）和式（11.11）是线性链条件随机场模型的基本形式，表示给定输入序列x，对输出序列y预测的条件概率。式（11.10）和式（11.11）中tk是定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置，sl是定义在结点上的特征函数，称为状态特征，依赖于当前位置。tk和sl都依赖于位置，是局部特征函数。通常，特征函数tk和sl取值为1或0；当满足特征条件时取值为1，否则为0。条件随机场完全由特征函数tk，sl和对应的权值λk， μl确定。

【个人理解】所谓“满足特征条件”，tk(yi-1,yi,x,i)特征函数中的参数若满足给定的特征条件，则特征函数赋值为1。

例题：

【解】根据标记序列y=(y1,y2,y3)=(1,2,3)可以得出特征函数的值，t1=t5=1,s1=s2=s4=1,其余为0。

推算：根据标记序列y=(y1,y2,y3)=(1,2,3)，t1=1是因为：i=2,y1=1,y2=2满足特征条件，t1=1。

【注】这里的i=2,3是或的关系，不是且，即只要满足其中一个i就可以赋值为1。

exp(3.2)是这样得出来的：3.2=1+0.2+1+0.5+0.5