机器学习 —— 概率图模型(Homework: CRF Learning)

  概率图模型的作业越往后变得越来越有趣了。当然,难度也是指数级别的上涨啊,以至于我用了两个周末才完成秋名山神秘车牌的寻找,啊不,CRF模型的训练。

  条件随机场是一种强大的PGM,其可以对各种特征进行建模,同时可以使用随机梯度下降算法进行训练,训练的结果就是PGM中那些定义变量交互方式的参数。

1、LR模型的训练

  LR模型可以看作是CRF模型的低配版,在完全不定义随机变量交互,只考虑P(Y|X)的情况下,得到的就是LR模型。其数学表达如下:

机器学习 —— 概率图模型(Homework: CRF Learning)

  这里theta是参数,X是特征也是像素值,该形式成为Logistic Regression。训练的本质是针对theta在训练集上进行优化,使得 P_trainSet 的概率达到最大,P_trainSet = P_data1*P_data2.......*P_datan,用公式表达可以写作:

  机器学习 —— 概率图模型(Homework: CRF Learning)

  这里连乘的形式并不利于我们分析,所以可以对目标方程取负对数——nll。同时将最大化问题转为最小化问题。

  机器学习 —— 概率图模型(Homework: CRF Learning)

  函数求最小值只要沿起梯度方向改变自变量即可,所以这里使用梯度下降法来求取目标函数的最小值。所以,使用梯度下降法来训练核心有就是——找到梯度的表达式

  对于LR模型来说,其梯度有着非常优雅的解析解,见之前博客

  解决了梯度表达式之后,还有一个核心问题就是过拟合,这里可以用L2-norm来强迫参数趋近于0.参数趋近于0就代表弱化特征作用。特征被弱化了模型就无法贴近YLabel了。L2-norm的参数Lamda是诗出來的。此时使用的是矫正集,不能使用训练集。

  LR模型只是小小的热身。关键是CRF的建模与训练。

2、CRF的训练

  拿到CRF的训练对象的时候我是一脸濛逼的。既没有概率图,也没有团树图。只有模型参数和训练集。CRF的数学表达见之前博客。从程序设计的角度,要做的是由CRF模型参数生成FeatureSet.模型参数如下:

  机器学习 —— 概率图模型(Homework: CRF Learning)

  1、隐性节点的状态card;2、观测节点的状态card。 除了模型参数之外,还需要定义模型交互方式(PGM factors),以OCR为例,模型有三种交互方式:1、Yi-Yi:表达了每个标签本身的概率。2、Yi-xi:对于给定像素位置Yi的概率。3、Yi-Yi+1:相邻标签各取某值的概率。由此可针对训练集中的每个数据生成CRF模型。虽然不同数据的模型是相似的(共享theta),但是其本身结构存在差异(单词长度不同)。

  实际上,每个feature的本质是 最终的table CPD 里的一个assignment. 而每个exp( fi*theta ),则是其中的val。所以   feature -- theta 和 table CPD 是联系在一起的。 所以这里也很好理解为什么一个theta可以对应多个feature. 因为CPD在概率图节点之间是复制的!(回忆一下遗传模型,遗传模式就是CPD,遗传模式在所有变量(人)之间不断复制....)CPD的复制就相当与feature的theta share.

  这里假设L2-norm的lamda是已知的。并且模型采用L2-norm。所以,核心的任务就是针对训练集中的每对数据,找到grad,然后整个模型按照grad下降寻找最合适的一组theta.求grad的理论分析不赘述,这里只从算法实现的角度来研究。为获得grad和cost,我们一共有5个量需要求:

机器学习 —— 概率图模型(Homework: CRF Learning)

2.1 LogZ

  LogZ的计算是全局最难的。其数学表达如下:

  机器学习 —— 概率图模型(Homework: CRF Learning)

  其需要对所有Y的取值求和。这代表要对 x 对应的所有可能的标签求和。换言之,要对最终联合分布CPD的val进行求和。如果是一个长度为7的单词,那就是26^7个数据求和。这显然是不现实的此数目多过太阳系里所有的星球。。。这里的第一个trick是利用团树标定算法求取Z.

  exp(XXXX)求的是整体概率(每个exp(fi*theta)是一个val),连乘是联合分布。团树算法中,每个消息 u 都是对之前变量进行边际化之后得到的。假设有一个3节点的团树链,团中分别有变量x1x2 ,x2x3, x3x4. 那么消息传递可以有以下形式:

  u12 = Σ1Φ

  u23 = Σ2Φ2 *  u12   =  Σ2Φ2 * Σ1Φ1  = Σ12  Φ2 Φ

  u32 = Σ4Φ3 

  重点在于 Σ3 u32*u23 = Σ1234 Φ2 Φ2 Φ = Z

  从定性上而言,消息携带了两边全部的信息,所以一条边上两个方向的消息携带了整个概率图中的信息。注意,这里的消息不能归一化,而团树标定中,消息必须归一化才能传递。

2.2 Model Expected feature Count

  第二个难点在于模型feature count的计算。

  对于每次梯度计算,我们手上都有一套完整的模型。模型的特征是一个指示函数,只要模型里有该特征,f取值都是1。ΣP*f 表达了当前模型对这些特征的肯定程度。f 是 table CPD的一个assignment,所以其 var , assignment 会对应一个特定的概率,也就是P。这里要算概率,似乎又要求那个26^7的联合分布了,然而并不是。由于特征本质是一个factor的assignment,而之前我们已经得到了标定好的团树模型,只需要在单个团树里求取Y'assignment对应的概率即可。因为clqiue的scope肯定要比feature大!!!

  这里比较trick的是,形式上,一个特征不止出现一次(意义不同)。比如说相邻的两个Y,取值分别为ab,这本质上是一个特征,只对应一个theta。但是这里的theta是share的。所以计算时必须把所有对应相同theta的f 都算进来。其数学表达式应该修正为:

机器学习 —— 概率图模型(Homework: CRF Learning)

2.3 Data Count

  Data Count 则是一个和数据有关的量了,表达了特征(shared)在当前数据中是否出现,是则置1,否则置0.

 

3、总结

  条件随机场的训练中真的充满了trick,通过此次作业,我加深了对Representation, Inference, Learning 的理解。

  最后,今天是母亲节~~亲爱的老妈节日快乐~ 

  

上一篇:Android 如何切换到 Transform API?


下一篇:RabbitMQ工作模式