1. 背景介绍
在许多实际应用中,我们需要解决的关键问题是如何对多个彼此关联 的变量进行预测。譬如自然语言处理中的词性标注问题,或者机器视觉里的图像标注任务,抑或是对DNA链上基因的分割。1 在这些应用中,我们希望通过观测到的特征向量 x \mathbf x x 来预测由随机变量组成的输出向量y = ( y 0 , y 1 , … , y T ) \mathbf y=(y_0,y_1,\ldots,y_T) y = ( y 0 , y 1 , … , y T ) 。图模型很自然地建立了实体之间的结构化关系,因而被用于表示联合概率分布p ( y , x ) p(\mathbf y,\mathbf x) p ( y , x ) 。
本文的研究背景是像素级的图像标注任务,这里x = ( x 0 , x 1 , … , x T ) \mathbf x=(x_0,x_1,\ldots,x_T) x = ( x 0 , x 1 , … , x T ) 表示一张大小为T × T \sqrt T \times \sqrt T T × T 的图片,每个x i x
_i x i 都代表一个像素。为使问题简化,这里考虑黑白图片,则x i x
_i x i 为取值范围0~255的实数。每个y i y
_i y i 就代表该像素的标签(label),比如我正在做的路面裂缝识别任务中,标签就只有两种:+ 1 +1 + 1 代表裂缝,0 0 0 代表正常路面。
假设图G = ( V , E ) G=(V,E) G = ( V , E ) ,其中V = X 1 , X 2 , … , X N V={X_1,X_2,\ldots,X_N} V = X 1 , X 2 , … , X N ,全局观测为I I I 。使用Gibbs分布,( I , X ) (I,X) ( I , X ) 可被建模为CRF
P ( X = x ∣ I ) = 1 Z ( I ) e x p ( − E ( x ∣ I ) )
P(X=x|I)=\frac 1{Z(I)}exp(-E(x|I))
P ( X = x ∣ I ) = Z ( I ) 1 e x p ( − E ( x ∣ I ) )
E ( x ) = ∑ i φ ( x i ) + ∑ i < j φ p ( x i . x j )
E(x)=\sum _i \varphi(x_i)+\sum _{i < j} \varphi_p(x_i.x_j)
E ( x ) = ∑ i φ ( x i ) + ∑ i < j φ p ( x i . x j )
φ p ( x i . x j ) \varphi_p(x_i.x_j) φ p ( x i . x j ) 是对 i i i 、j j j 同时分类成x i x_i x i 、x j x_j x j 的能量。
接下来的内容安排为:第二章首先引入条件随机场的概念,之后举例说明其与其他模型的区别,最后从原理上介绍它在图像标注中的应用;第三章则是近年来相关工作的简要阐述。
1.1. 二、条件随机场
1.1.1. 2.1 概念引入
Y Y Y :一系列随机变量的集合;
概率图模型:无向图G = ( V , E ) G=(V,E) G = ( V , E ) 表示概率分布P ( Y ) P(Y) P ( Y ) ,节点v ∈ V v\in V v ∈ V 表示一个随机变量Y s Y_s Y s ,s ∈ 1 , 2 , … ∣ Y ∣ s\in1,2,\ldots|Y| s ∈ 1 , 2 , … ∣ Y ∣ ;边e ∈ E e\in E e ∈ E 表示随机变量之间的概率依存关系;
概率无向图模型:如果联合概率p ( Y ) p(Y) p ( Y ) 满足成对、局部或者全局马尔科夫性,就称该联合概率分布为无向图模型,或者马尔科夫随机场。最大特点:易于因子分解。这里的随机场 指的就是由无向图定义的特定分布。
indicator function
:
1 { y = y ′ } = { 1 , y = y ′ 0 , e l s e w h e r e
\mathbf 1_{\{y=y'\}}=
\begin{cases}
1, &y=y'\cr
0, &elsewhere
\end{cases}
1 { y = y ′ } = { 1 , 0 , y = y ′ e l s e w h e r e
条件随机场(conditional random field,以下简称CRF ):假定我们关心的概率分布p p p 可以通过A A A 个形如Ψ a ( y a ) \Psi_a(\mathbf y_a) Ψ a ( y a ) 的因子(factor)的乘积来表示。
p ( y ) = 1 Z ∏ a = 1 A Ψ a ( y a )
p(\mathbf y)=\frac 1Z \prod_{a=1}^A\Psi_a(\mathbf y_a)
p ( y ) = Z 1 a = 1 ∏ A Ψ a ( y a )
其中Z Z Z 为规一化因子,使得p ( y ) p(\mathbf y) p ( y ) 在0~1。
这些factor也称做local function
或compatibility function
。而在图中,与因子节点(factor node)Ψ a \Psi_a Ψ a 相连的所有变量节点(variable node)Y s Y_s Y s 都是Ψ a \Psi_a Ψ a 的参数之一。所以factor graph描述的是分布p p p 分解为一系列local function
的方式。
1.1.2. 2.2 判别式模型和产生式模型
通常看到一个新的模型,我们总习惯和已知的进行比较。朴素贝叶斯和逻辑回归模型之间的一个重要区别是,朴素贝叶斯是产生式模型(generative model ),它基于联合分布p ( x , y ) p(\mathbf x,\mathbf y) p ( x , y ) 建模,而逻辑回归是判别式模型(discriminative model ),它直接对条件分布p ( y ∣ x ) p(\mathbf y|\mathbf x) p ( y ∣ x ) 建模。
对条件分布p ( y ∣ x ) p(\mathbf y|\mathbf x) p ( y ∣ x ) 建模,不包括对p ( x ) p(\mathbf x) p ( x ) 建模(p ( x ) p(\mathbf x) p ( x ) 对分类来说无关紧要)。对p ( x ) p(\mathbf x) p ( x ) 建模非常困难,因为p ( x ) p(\mathbf x) p ( x ) 包含很多相互依赖的特征。比如在命名实体识别(Named- Entity Recognition,NER )应用中,HMM只依赖一个特征,即这个词本身,但是很多词,特别是一些特定的名字可能没有出现在训练集合中,因此词本身这个特征是未知的,为了标注未登陆词,我们需要利用词的其他的特征,如词性、相邻词、前缀和后缀等。
这里以HMM和Linear-chain CRF为例说明这两种模型的区别。
除了上面说的NER,在做词性标注任务(Part-of-Speech tagging, POS )的时候我们也常使用HMM模型,y \mathbf y y 就是 word对应的词性(label),x \mathbf x x 的是它的观测(word)。
p ( y , x ) = ∏ t = 1 T p ( y t ∣ y t − 1 ) p ( x t ∣ y t )
p(\mathbf y,\mathbf x)=\prod_{t=1}^T p(y_t|y_{t-1})p(x_t|y_t)
p ( y , x ) = t = 1 ∏ T p ( y t ∣ y t − 1 ) p ( x t ∣ y t )
transition probability :p ( y t ∣ y t − 1 ) p(y_t|y_{t-1}) p ( y t ∣ y t − 1 ) 不同状态(label)之间的转移概率
emission probability:p ( x t ∣ y t ) p(x_t|y_t) p ( x t ∣ y t ) 由状态到观测(word)的发射概率
首先,我们可以将HMM重写为更一般化的形式:
p ( y , x ) = 1 Z ∏ t = 1 T exp { ∑ i , j ∈ S θ i j 1 { y t = i } 1 { y t − 1 = j } + ∑ i ∈ S ∑ o ∈ O μ o i 1 { y t = i } 1 { x t = o } }
p(\mathbf y,\mathbf x)=\frac 1Z \prod_{t=1}^T \exp\{\sum_{i,j \in S} \theta_{ij}\mathbf 1_{\{y_t=i\}} \mathbf 1_{\{y_{t-1}=j\}}+\sum_{i\in S}\sum_{o\in O}\mu_{oi}\mathbf 1_{\{y_t=i\}}\mathbf 1_{\{x_t=o\}}\}
p ( y , x ) = Z 1 t = 1 ∏ T exp { i , j ∈ S ∑ θ i j 1 { y t = i } 1 { y t − 1 = j } + i ∈ S ∑ o ∈ O ∑ μ o i 1 { y t = i } 1 { x t = o } }
其中θ = { θ i j , μ o i } \theta=\{\theta_{ij},\mu_{oi}\} θ = { θ i j , μ o i } 是分布的实值参数。只需要设定:
θ i j = log p ( y ′ = i ∣ y = j ) μ o i = log p ( x = o ∣ y = i ) Z = 1
\begin{aligned}
\theta_{ij}=\log p(y'=i|y=j)\\
\mu_{oi}=\log p(x=o|y=i)\\
Z=1
\end{aligned}
θ i j = log p ( y ′ = i ∣ y = j ) μ o i = log p ( x = o ∣ y = i ) Z = 1
则与上述HMM等价。通过引入特征函数的概念:
对每一个转移( i , j ) (i,j) ( i , j ) 有f i j ( y , y ′ , x ) = 1 { y = i } 1 { y ′ = j } f_{ij}(y,y',x)=\mathbf 1_{\{y=i\}} \mathbf 1_{\{y'=j\}} f i j ( y , y ′ , x ) = 1 { y = i } 1 { y ′ = j } ;
对每一个发射( i , o ) (i,o) ( i , o ) 有f i o ( y , y ′ , x ) = 1 { y = i } 1 { x = o } f_{io}(y,y',x)=\mathbf 1_{\{y=i\}} \mathbf 1_{\{x=o\}} f i o ( y , y ′ , x ) = 1 { y = i } 1 { x = o } ;
特征函数f k f_k f k 遍历所有f i j f_{ij} f i j 和f i o f_{io} f i o 。
这就得到了满足因子分解形式的Linear-chain CRF:
p ( y , x ) = 1 Z ∏ t = 1 T exp { ∑ θ k f k ( y t , y t − 1 , x t ) }
p(\mathbf y,\mathbf x)=\frac 1Z \prod_{t=1}^T \exp\{\sum \theta_k f_k(y_t,y_{t-1},x_t)\}
p ( y , x ) = Z 1 t = 1 ∏ T exp { ∑ θ k f k ( y t , y t − 1 , x t ) }
我们已经看到当联合分布为HMM的形式时,相应的条件概率分布为线性链式的CRF,在HMM中状态i i i 到状态j j j 的转移概率总是相同的,和当前的输入无关,但是在CRF中,我们可以通过加入特征:
1 { y t = j } 1 { y t − 1 = i } 1 { x t = o }
\mathbf 1_{\left \{ {y_t} = j \right \} } \mathbf 1_{\left \{ { y_{t - 1} = i} \right \}} \mathbf 1_{\left\{ {x_t} = o \right\}}
1 { y t = j } 1 { y t − 1 = i } 1 { x t = o }
来使得状态i i i 到状态j j j 的转移概率和当前输入有关 。实际上,这也是CRF应用于图像标注的优势所在。
1.1.3. 2.2 在图像标注中的应用
图像的一个重要特性是:相邻像素的标注趋向于一致 。因此,我们可以通过设置一个y \mathbf y y 的先验(prior)分布p ( y ) p(\mathbf y) p ( y ) 来融入该特性,使得预测趋向于“平滑 ”。目前最常用的prior是马尔可夫随机场 (Markov random field,以下简称MRF ),它是一个无向图,且有两种因子(factor):
关联标签y i y_i y i 和对应的像素x i x_i x i :
鼓励相邻标签y i y_i y i 和y j y_j y j 保持一致
这里用N \mathscr N N 表示像素的相邻关系,则( i , j ) ∈ N (i,j)\in \mathscr N ( i , j ) ∈ N 意味着x i x_i x i x j x_j x j 相邻。通常N \mathscr N N 是一个T × T \sqrt T \times \sqrt T T × T 的网格。
p ( y ) = 1 Z ∏ ( i , j ) ∈ N Ψ ( y i , y j )
p(\mathbf y)=\frac 1Z \prod_{(i,j)\in \mathscr N} \Psi(y_i,y_j)
p ( y ) = Z 1 ( i , j ) ∈ N ∏ Ψ ( y i , y j )
这里的Ψ \Psi Ψ 是鼓励平滑性的因子,比较通用的设置是:
Ψ ( y i , y j ) = { 1 , y i = y j α , e l s e w h e r e
\Psi(y_i,y_j)=
\begin{cases}
1,&y_i=y_j \cr
\alpha,& elsewhere
\end{cases}
Ψ ( y i , y j ) = { 1 , α , y i = y j e l s e w h e r e
通常α < 1 \alpha<1 α < 1 ,可理解为对差异的惩罚。
p ( y , x ) = p ( y ) ∏ i = 1 T p ( x i ∣ y i )
p(\mathbf y,\mathbf x) = p(\mathbf y)\prod_{i=1}^Tp(x_i|y_i)
p ( y , x ) = p ( y ) i = 1 ∏ T p ( x i ∣ y i )
MRF的一个不足之处在于难引入关系数据中的局部特征 ,因为这时p ( x ∣ y ) p(\mathbf x|\mathbf y) p ( x ∣ y ) 结构会很复杂。
CRF和MRF很相似。假定q ( x i ) q(x_i) q ( x i ) 表示基于x i x_i x i 周围区域的特征向量,例如颜色直方图或图像梯度。此外,ν ( x i , x j ) \nu(x_i,x_j) ν ( x i , x j ) 描述x i x_i x i 与x j x_j x j 之间的关系,从而考虑x i x_i x i 与x j x_j x j 的异同。 这里就可以定义ν ( x i , x j ) \nu(x_i,x_j) ν ( x i , x j ) 为q ( x i ) q(x_i) q ( x i ) 和q ( x j ) q(x_j) q ( x j ) 中特征的叉积。
f m ( y i , x i ) = 1 { y i = m } q ( x i ) ∀ m ∈ { 0 , 1 } f ( y i , x i ) = ( f 0 ( y i , x i ) f 1 ( y i , x i ) )
\begin{aligned}
f_m(y_i,x_i)=\mathbf 1_{\{y_i=m\}}q(x_i) \forall m\in\{0,1\}\\
f(y_i,x_i)=
\left(
\begin{matrix}
f_0(y_i,x_i)\\
f_1(y_i,x_i)
\end{matrix}
\right)
\end{aligned}
f m ( y i , x i ) = 1 { y i = m } q ( x i ) ∀ m ∈ { 0 , 1 } f ( y i , x i ) = ( f 0 ( y i , x i ) f 1 ( y i , x i ) )
为了让问题更加清楚,考虑MRF中的Ψ ( y i , y j ) \Psi(y_i,y_j) Ψ ( y i , y j ) ,尽管它鼓励一致性,但方式不灵活。如果x i x_i x i x j x_j x j 的 标签不同,我们会预期它们的灰度也不同,因为不同物体总是色调不同。所以相比于标签边界出现在灰度悬殊的像素之间,出现在灰度相似的像素之间更“不合常理”。然而,MRF中的Ψ \Psi Ψ 对这两种情况的惩罚相同,使得能量计算和像素值无关 。为了解决这个问题,人们提出了下面的特征选择方法:
ν ( x i , x j ) = exp { − β ( x i − x j ) 2 } g ( y i . y j , x i , x j ) = 1 { y i ≠ y j } ν ( x i , x j )
\begin{aligned}
\nu(x_i,x_j)=\exp \{-\beta(x_i-x_j)^2\}\\
g(y_i.y_j,x_i,x_j)=\mathbf 1_{\{y_i\neq y_j\}}\nu(x_i,x_j)
\end{aligned}
ν ( x i , x j ) = exp { − β ( x i − x j ) 2 } g ( y i . y j , x i , x j ) = 1 { y i = y j } ν ( x i , x j )
把上述所有加起来,就得到了CRF模型:
p ( y ∣ x ) = 1 Z ( x ) exp { ∑ i = 1 T θ ⊤ f ( y i , x i ) + ∑ ( i , j ) ∈ N λ ⊤ g ( y i . y j , x i , x j ) }
p(\mathbf y|\mathbf x)=\frac 1{Z(\mathbf x)}\exp\{\sum_{i=1}^T\theta^\top f(y_i,x_i)+\sum_{(i,j)\in \mathscr N} \lambda^\top g(y_i.y_j,x_i,x_j)\}
p ( y ∣ x ) = Z ( x ) 1 exp { i = 1 ∑ T θ ⊤ f ( y i , x i ) + ( i , j ) ∈ N ∑ λ ⊤ g ( y i . y j , x i , x j ) }
这种简单的CRF模型可通过多种方式改进:
特征函数q q q 和ν \nu ν 可以设计得更加复杂,例如考虑图片的形状和纹理,或者依赖于图像的全局特征而不是局部区域;
可以使用标签之间更加复杂的图结构而不是网格(grid),譬如可以根据标签区域定义因子(factor)。
1.2. 三、相关工作
近年来已有许多研究者将CRF 应用于 pixel-wise 的图像标记(其实就是图像分割),从而实现分割边界的平滑化,进而提升正确率。例如Koltun等人使用全连接CRF、高斯核线性组合来定义边界能量实现的像素级图片标注任务,实验结果大幅改进了图像分割和标注的正确率3 。接着,S Zheng等人通过将CRF实现为RNN,在模型优化过程进行端到端训练进一步提高了标注效果。2 他们主要是利用条件随机场构造图像分割能量函数:
E ( x ) = ∑ i φ u ( x i ) + ∑ i < j φ p ( x i . x j )
E(x)=\sum _i \varphi_u(x_i)+\sum _{i < j} \varphi_p(x_i . x_j)
E ( x ) = ∑ i φ u ( x i ) + ∑ i < j φ p ( x i . x j )
这里的E E E 可以理解为能量,也就是cost。其中φ u ( x i ) \varphi_u(x_i) φ u ( x i ) 是将像素i i i 标记为x i x_i x i 的inverse likelihood,也就是2.3 中的特征函数f ( y i , x i ) f(y_i,x_i) f ( y i , x i ) ,φ p ( x i . x j ) \varphi_p(x_i.x_j) φ p ( x i . x j ) 是将i i i 、j j j 同时标记为x i x_i x i 、x j x_j x j 的能量,即2.3 中的特征函数g ( y i . y j , x i , x j ) g(y_i.y_j,x_i,x_j) g ( y i . y j , x i , x j ) 。对于CRF在计算机视觉中的应用,相信未来还会有更多探索。
1.3. 四、参考文献
1 . Sutton, Charles, and Andrew McCallum. "An introduction to conditional random fields ." arXiv preprint arXiv:1011.4088 (2010). ↩
2 . Zheng, Shuai, et al. "Conditional random fields as recurrent neural networks ." Proceedings of the IEEE International Conference on Computer Vision. 2015. ↩
3 . Koltun, Vladlen. "Efficient inference in fully connected crfs with gaussian edge potentials ." Adv. Neural Inf. Process. Syst (2011). ↩