条件随机场笔记

本文主要整理自 Charles Sutton 的《An Introduction to Conditional Random Fields》。该文从 Graphical Models 讲起,介绍了条件随机场如何表述、推断以及进行参数,非常适合入门。


图模型


通常,我们要根据观察到的随机变量 $x$ 组成的特征向量 $\{x_{0},...,x_{T}\}$ 来预测输出向量 $\{y_{0},...,y_{T}\}$。

一种处理该问题的方式是,对于 $\forall s$,找到一个函数 $X \to y_{s}$。这种处理方法不足之处在于,$y$ 之间可能存在着复杂的依赖关系。

此时,一种自然的做法是采用图模型去描述输出变量之间的关系。简单讲,图模型是一种可以将关系复杂的大量变量的分布表示为更小的结构的乘积的模型。


在图模型领域中,有一类被成为生成式模型,即试图直接描述出输入和输出的联合分布 $p(y, x)$。生成式模型的难点在于,$x$ 的维度往往特别大,且其特征直接的关系十分复杂。这导致了如果对输入之间的关系建模会十分困难,而简化处理将导致模型能力的下降。

一种解决办法是直接对条件分布 $p(y|x)$ 直接建模。这就是条件随机场,即CRF。条件随机场结合了分类器和图模型的优点,能对大量输入特征的数据的结果进行分类预测。

由上述描述可知,生成式模型和条件随机场的差异很像朴素贝叶斯和逻辑回归的差异。事实上,多元逻辑回归就是最简单的条件随机场,即只有一个输出变量的条件随机场。


条件随机场


本节将逐步讨论链式条件随机场,生成式模型与条件随机场和包含隐变量的条件随机场。


无向图

首先,考虑随机变量集合 $V=X \cup Y$,其中 $X$ 是我们观测到的输入随机变量,$Y$ 是我们希望预测的输出随机变量,有如下定义:

  • $\forall s \in V$,其取值来自集合 $\mathbb{V}$。随机变量 $X$ 的任一取值记为向量 $x$
  • $\forall s \in X$,记 $x_{s}$ 为 $s$ 的取值
  • $\forall a \subset X$, 记 $x_{a}$ 为 $a$ 的取值
  • 记 $1_{\{x={x}'\}}$ 为 $x$ 的函数,当 $x={x}'$ 时取1,其它情况取0
  • 记 $\sum_{y\setminus y_{s}}$ 为对一固定的变量取值 $y_{s}$,所有与变量 $s$ 的取值 $y_{s}$ 相等的 $y$ 的取值的加和

假设概率分布 $p$ 可被表示为:

$p(x, y)=\frac{1}{Z} \prod_{a \in \mathbb{F}} \Psi_{a}(x_{a}, y_{a})$

其中

$\mathbb{F} = a \subset V, \Psi_{a}: \mathbb{V}^{|a|} \to \mathbb{R}^{+}, Z=\sum_{x,y}\prod_{a \in \mathbb{F}} \Psi_{a}(x_{a}, y_{a})$

我们称 $\Psi_{a}$ 为局部函数,$Z$ 为配分函数。通常来讲,配分函数是很难计算的,所有常常采用近似地方式去计算 $Z$。

进一步,我们假设对于每一个局部函数,有如下表达式:

$\Psi_{a}(x_{a},y_{a})=exp \{ \sum_{k}\theta_{ak}f_{ak}(x_{a},y_{a}) \}$

其中,$\theta_{a}$ 为实值参数向量,记 $\{f_{ak}\}$ 为特征函数。当 $x,y$ 为离散值时,通常可令特征函数为 $f_{ak}(x_{a},y_{a})=1_{\{x_{a}=x_{a}^{\ast}\}}1_{\{y_{a}=y_{a}^{\ast}\}}$。

上述这种紧凑的概率分布表达式可以由一种称为马尔可夫网络的无向图 $G$ 表达。我们记 $N(s)$ 表示 $s$ 相邻节点的集合,对于 $\forall s \in V$。那么,当满足如下条件时,又称局部马尔可夫性质

$\forall s,t \in V$,有 $s \perp t|N(s)$。直觉上,可以理解为 $N(s)$ 已经包含了用来预测 $s$ 取值的所有信息。

我们称分布 $p$ 是 $G$ 的马尔可夫表示。


有向图

考虑有向图,记 $\pi(v), v \in V$ 为 $v$ 的父节点,则概率分布可表示为:

$p(y,x)=\prod_{v \in V}p(y_{v}|y_{\pi(v)})$

对比无向图的分解,有向图的分解可以理解为其 $Z=1$。


朴素贝叶斯

考虑朴素贝叶斯公式:

$p(y,x)=p(y)\prod_{k=1}^{K}p(x_{k}|y)$

结合无向图和有向图概率表达公式,为了统一公式,我们可以定义:

$\Psi(y)=p(y), \Psi_{k}(y,x_{k})=p(x_{k}|y)$


逻辑回归(最大熵分类器)

逻辑回归的假设是每一类的 $logp(y|x)$ 是由 $x$ 的线性函数加一个归一化常数组成的。其公式如下:

$p(y|x)=\frac{1}{Z(x)}exp\{\theta_{y}+\sum_{j=1}^{K}\theta_{y,j}x_{j}\},Z(x)=\sum_{y}exp\{\theta_{y}+\sum_{j=1}^{K}\theta_{y,j}x_{j}\}$

对比朴素贝叶斯,我们可以把偏重 $\theta_{y}$ 看作朴素贝叶斯中的 $logp(y)$。同样,为了统一公式,可以将特征函数定义为:

$f_{y'}(y,x)=1_{\{y'=y\}}, f_{y',j}(y,x)=1_{\{y'=y\}}x_{j}$

再令 $f_{k}$ 代表 $f_{y',j}$,$\theta_{k}$ 代表 $\theta_{y',j}$,则统一后的表达式为:

$p(y|x)=\frac{1}{Z(x)}exp\{\sum_{k=1}^{K}\theta_{k}f_{k}(y,x)\}$


隐马尔可夫模型

在隐马尔可夫模型中,有三种分布:

  • 初始分布:$p(y_{1})=p(y_{1}|y_{0})$
  • 转移分布:$p(y_{t}|y_{t-1})$
  • 观测分布:$p(x_{t}|y_{t})$

其概率分布公式为:

$p(x,y)=\prod_{t=1}^{T}p(y_{t}|y_{t-1})p(x_{t}|y_{t})$

同样,统一公式为:

$p(y,x)=\frac{1}{Z}\prod_{t=1}^{T}exp\{\sum_{i,j \in S}\theta_{ij}1_{\{y_{t}=i\}}1_{\{y_{t-1}=j\}}+\sum_{i \in S}\sum_{o \in O}\mu_{oi}1_{\{y_{t}=i\}}1_{\{x_{t}=o\}}\}$

其中,参数 $\theta = \{\theta_{ij},\mu_{oi}\}$。进一步,定义:

$f_{ij}(y_{i},y_{j},x)=1_{\{y_{t}=i\}}1_{\{y_{t-1}=j\}},f_{io}(y_{i},y_{i-1},x)=1_{\{y_{t}=i\}}1_{\{x_{t}=o\}}$

并用 $f_{k}$ 依次标定所有的 $f_{ij},f_{io}$,则最终公式统一为:

$p(y,x)=\frac{1}{Z}\prod_{t=1}^{T}exp\{\sum_{k=1}^{K}\theta_{k}f_{k}(y_{t},y_{t-1},x_{t})\}$


线性链条件随机场

由隐马尔可夫模型的公式可知,线性链条件随机场的公式为:

$p(y|x)=\frac{1}{Z(x)}\prod_{t=1}^{T}exp\{\sum_{k=1}^{K}\theta_{k}f_{k}(y_{t},y_{t-1},x_{t})\}$

其中

$Z(x)=\sum_{y}\prod_{t=1}^{T}exp\{\sum_{k=1}^{K}\theta_{k}f_{k}(y_{t},y_{t-1},X_{t})\}$


条件随机场

从线性条件随机场推广到一般条件随机场,我们有

$p(y|x)=\frac{1}{Z(x)}\prod_{\Psi_{A} \in G}^{T}exp\{\sum_{k=1}^{K(A)}\theta_{ak}f_{ak}(Y_{a},X_{t})\}$

xiehao

Read more posts by this author.