七月算法-12月机器学习在线班--第十八次课笔记-条件随机场CRF
七月算法（julyedu.com）12月机器学习在线班学习笔记http://www.julyedu.com
1，对数线性模型
一个事件的几率odds，是指该事件发生的概率与该事件不发生的概率的比值。
1.1对数线性模型的一般形式
令x为某样本，y是x的可能标记，将Logistic/ Softmax回归的特征 记做
特征函数的选择：eg: 自然语言处理
1, 特征函数几乎可任意选择，甚至特征函数间重叠；
2, 每个特征之和当前的词性有关，最多只和相邻词的词性有关
3，但是特征可以所有词有关（这样做可以把模型变成链状的）
词性标注
1，结构化预测。
2，相邻单词的标记相互影响，非独立
2，线性链条件随机场
2.1 线性条件随机场可以使用对数线性模型。
给了参数，如何估计概率
使用 
表示n个词的序列；
表示相应的词性
是由若干个次特征组成的
2.2 参数训练
参数推断的两个难点
1，如果给定x和w，如何计算哪个标记序列y的概率最大
2，如果给定x和w， p(y|x,w)本身如何计算？
2.3 状态关系矩阵
特征可以换成此特征的加和
2.3.1 利用前向得分选择最大标记序列
为前向得分，表示第k个词的标记为v的最大得分值(该得分值归一化后即为概率)，即：
2.3.2 状态关系矩阵推导
时间复杂度O(
n)
3 参数训练
给定一组训练样本(x,y)，找出权向量w，找出参数，使得下式成立：
方法：求对数目标函数的驻点。
目标函数：
其中
，不是求导，只是一个记号，j和
不同的值，y和
，表示两个不同的y值
最后使用梯度上升，学习参数
和
不是相互独立的，而是有联系的
4, 无向图模型（UGM）马尔科夫随机场/马尔科夫网络
有向图模型，又称作贝叶斯网络(Directed Graphical Models, DGM, Bayesian Network)
概率有向图模型/概率无向图模型
4.1 条件随机场
从贝叶斯网络到马尔科夫随机场
直接将一个孩子的公共父亲相连接，将所有的箭头去掉
并不是完全信息不丢失（约定俗成的方法），条件独立的破坏
4.2 MRF的性质
1，成对马尔科夫性
2，局部马尔科夫性
3，全局马尔科夫性
以上的这三个性质等价的
4.3 团和最大的团
定义：无向图G中的某个子图S，若S中任何两个结点均有边，则S称作G的团(Clique)。
最大团：若C是G的一个团，并且不能再加入任何一个G的结点使其称为团，则C称作G的最大团(Maximal Clique)。
图中的最大团{1,2,3}，{2,3,4}，{3,5}，最大团跟数目没有关系，
只要是不能再加入任何一个G的结点使其称为团
4.4 Hammersley-Clifford定理
UGM的联合分布：最大团上的随机变量的函数的乘积的形式；
这个操作叫做UGM的因子分解(Factorization)。
线性链条件随机场可用于标注等问题
CRF总结
条件随机场可以使用对数线性模型表达。
不严格的说，线性链条件随机场可看成是隐马尔科夫模型的推广，隐马尔科夫模型可看成是线性链条件随机场的特殊情况。
缺点：有监督学习计算参数，参数学习的速度慢