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

一、概率无向图模型

概率无向图模型又称马尔可夫随机场，是一个可以由无向图表示的联合概率分布。

1、模型定义

图graph 是由结点（node）及连接结点的边（edge）组成的集合。结点和边分别记作v和e，结点和边的集合分别记作 V和E，图记作G=（V,E）。
无向图是指边没有方向的图

概率图模型：
由图表示的概率分布。
给定一个联合概率分布P(Y)和表示它的无向图G。
定义无向图表示的随机变量之间存在的：

• 成对马尔可夫性
• 局部马尔可夫性
• 全局马尔可夫性

image.png

概率无向图模型

image.png

问题关键：求联合概率，引申为对联合概率进行因子分解

2、概率无向图模型的因子分解

团与最大团

image.png
image.png

概率无向图模型的因子分解：

将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作

image.png

Hammersley-Clifford定理

image.png

二、条件随机场的定义与形式

1、条件随机场的定义

给定随机变量X条件下，随机变量Y的马尔可夫随机场。

定义在线性链上的特殊的条件随机场（称为线性链条件随机场）

• 线性链条件随机场可以用标注等问题
• 在条件概率模型P(Y|X)中，Y是输出遍历，表示标记序列，X是输入变量，表示需要标注的观测序列，也把标记序列称为状态序列

条件随机场三个主要问题：

• 概率计算
• 模型学习
• 推测状态

条件随机场

image.png

线性链情况

image.png

最大团是相邻两个结点的集合，线性链条件随机场：

image.png

线性链条件随机场

image.png

2、条件随机场的参数化形式

image.png

3、条件随机场的简化形式

注意到条件随机场中同一特征在各个位置都有定义，可以对同一个特征在各个位置求和，将局部特征函数转化为一个全局特征函数，这样就可以将条件随机场写成权值向量和特征向量的内积形式，即条件随机场的简化形式

image.png

4、条件随机场的矩阵形式

image.png

三、条件随机场的概率计算问题

给定条件随机场P(Y|X)，输入序列x和输出序列y
计算条件概率：

image.png

以及相应的属性期望问题。

1、前向-后向算法

image.png

2、概率计算

image.png

3、期望值的计算

image.png

四、条件随机场的学习算法

1、改进的迭代尺度法

image.png

不断优化对数似然函数改变量的下界：

image.png

关于转移特征的更新方程

image.png

关于状态特征的更新方程

image.png

T(x,y)是在数据(x,y)中出现所有特征数的总和

image.png

条件随机场模型学习的改进的迭代尺度法

image.png

对转移特征的更新方程：

image.png

对状态特征的更新方程：

image.png image.png

转移特征参数的更新方程可以写成：

image.png

关于状态特征的参数更新方程可以写成：

image.png

2、拟牛顿法

拟牛顿法

image.png

学习的优化目标函数：

image.png

梯度函数：

image.png

条件随机场模型学习的BFGS算法

image.png

五、条件随机场的预测算法

给定条件随机场P(Y|X)和输入序列（观察序列）x,
求：条件概率最大的输出序列（标记序列）y*,

image.png

路径表示标记序列

image.png

只需计算非规范化概率

image.png

维特比算法：

image.png

条件随机场预测的维特比算法

image.png