机器学习笔记之高斯网络——高斯马尔可夫随机场
引言
上一节介绍了高斯贝叶斯网络(Gaussian Bayesian Network,GBN)，本节将介绍基于高斯网络的无向图模型——高斯马尔可夫随机场。
回顾：马尔可夫随机场——团、势函数
不同于贝叶斯网络，马尔可夫随机场中结点之间的边没有方向性，这使得没有办法直接通过概率图结构描述因子分解式。
因而通过团(Clique)、势函数(Potential Functions)对无向图结点的 进行描述：
已知一个马尔可夫随机场 表示如下：
为什么说是泛型呢~在描述马尔可夫随机场的结构时，为了突出某个具体结构，没有将所有结点之间的关联关系进行描述，从而仅通过一个结点对某一部分子图进行整体概括。相关视频传送门——信念传播
其中 X A , X B , X C , X D \mathcal X_{\mathcal A},\mathcal X_{\mathcal B},\mathcal X_{\mathcal C},\mathcal X_{\mathcal D} XA,XB,XC,XD分别表示四个子图。该图中更需要突出的是这四个子图之间的关联关系。
观察，图中一共包含 3 3 3个最大团： { X A , X B } , { X A , X C } , { X A , X D } \{\mathcal X_{\mathcal A},\mathcal X_{\mathcal B}\},\{\mathcal X_{\mathcal A},\mathcal X_{\mathcal C}\},\{\mathcal X_{\mathcal A},\mathcal X_{\mathcal D}\} {XA,XB},{XA,XC},{XA,XD}
对应该图结点的联合概率分布 P ( X ) \mathcal P(\mathcal X) P(X)表示如下：
P ( X ) = 1 Z [ ψ A B ( X A , X B ) ⋅ ψ A C ( X A , X C ) ⋅ ψ A D ( X A , X D ) ⋅ ψ A ( X A ) ⋅ ψ B ( X B ) ⋅ ψ C ( X C ) ⋅ ψ D ( X D ) ] \mathcal P(\mathcal X) = \frac{1}{\mathcal Z}[\psi_{\mathcal A\mathcal B}(\mathcal X_{\mathcal A},\mathcal X_{\mathcal B}) \cdot \psi_{\mathcal A\mathcal C}(\mathcal X_{\mathcal A},\mathcal X_{\mathcal C}) \cdot \psi_{\mathcal A\mathcal D}(\mathcal X_{\mathcal A},\mathcal X_{\mathcal D}) \cdot \psi_{\mathcal A}(\mathcal X_{\mathcal A}) \cdot \psi_{\mathcal B}(\mathcal X_{\mathcal B}) \cdot \psi_{\mathcal C}(\mathcal X_{\mathcal C}) \cdot \psi_{\mathcal D}(\mathcal X_{\mathcal D})] P(X)=Z1[ψAB(XA,XB)⋅ψAC(XA,XC)⋅ψAD(XA,XD)⋅ψA(XA)⋅ψB(XB)⋅ψC(XC)⋅ψD(XD)]
因而基于随机变量集合 X = ( x 1 , x 2 , ⋯ , x p ) T ， \mathcal X = (x_1,x_2,\cdots,x_p)^T， X=(x1,x2,⋯,xp)T，可以将无向图的 P ( X ) \mathcal P(\mathcal X) P(X)表示为如下形式：
这里假设每个结点中仅包含一个随机变量。
P ( X ) = 1 Z ∏ i = 1 p ψ i ( x i ) ⋅ ∏ x i , x j ∈ X ψ i j ( x i , x j ) \mathcal P(\mathcal X) = \frac{1}{\mathcal Z} \prod_{i=1}^p \psi_i(x_i) \cdot \prod_{x_i,x_j \in \mathcal X} \psi_{ij}(x_i,x_j) P(X)=Z1i=1∏pψi(xi)⋅xi,xj∈X∏ψij(xi,xj)
称 ψ i ( x i ) \psi_{i}(x_i) ψi(xi)为点势函数(Node Potential)，称 ψ i j ( x i , x j ) \psi_{ij}(x_i,x_j) ψij(xi,xj)为边势函数(Edge Potential)。
高斯马尔可夫随机场
即便是无向图模型，随机变量集合 X \mathcal X X的联合概率分布 P ( X ) \mathcal P(\mathcal X) P(X)依然服从多元高斯分布：
P ( X ) = 1 ( 2 π ) p 2 ∣ Σ ∣ 1 2 exp [ − 1 2 ( X − μ ) T Σ − 1 ( X − μ ) ] \mathcal P(\mathcal X) = \frac{1}{(2\pi)^{\frac{p}{2}}|\Sigma|^{\frac{1}{2}}} \exp \left[ -\frac{1}{2} (\mathcal X - \mu)^T \Sigma^{-1} (\mathcal X - \mu)\right] P(X)=(2π)2p∣Σ∣211exp[−21(X−μ)TΣ−1(X−μ)]
目标是将多元高斯分布和势函数联系在一起：
- 观察多元高斯分布 P ( X ) \mathcal P(\mathcal X) P(X)，其中 1 ( 2 π ) p 2 ∣ Σ ∣ 1 2 \frac{1}{(2\pi)^{\frac{p}{2}}|\Sigma|^{\frac{1}{2}}} (2π)2p∣Σ∣211中的 Σ \Sigma Σ是模型自身参数，和 X \mathcal X X无关。因此对 P ( X ) \mathcal P(\mathcal X) P(X)进行如下表示：
对Σ − 1 \Sigma^{-1} Σ−1使用‘精度矩阵’Λ \Lambda Λ进行表示。
P ( X ) ∝ exp [ − 1 2 ( X − μ ) T Σ − 1 ( X − μ ) ] = exp [ − 1 2 ( X − μ ) T Λ ( X − μ ) ] \begin{aligned} \mathcal P(\mathcal X) & \propto \exp \left[ -\frac{1}{2} (\mathcal X - \mu)^T \Sigma^{-1} (\mathcal X - \mu)\right] \\ & = \exp \left[ -\frac{1}{2} (\mathcal X - \mu)^T \Lambda (\mathcal X - \mu)\right] \end{aligned} P(X)∝exp[−21(X−μ)TΣ−1(X−μ)]=exp[−21(X−μ)TΛ(X−μ)] - 将中括号内部元素展开，有：
Δ \Delta Δ表示原式。
Δ = exp [ − 1 2 ( X T Λ − μ T Λ ) ( X − μ ) ] = exp [ − 1 2 ( X T Λ X − X T Λ μ − μ T Λ X + μ T Λ μ ) ] \begin{aligned} \Delta & = \exp \left[ - \frac{1}{2}(\mathcal X^T \Lambda - \mu^{T} \Lambda)(\mathcal X - \mu)\right] \\ & = \exp \left[-\frac{1}{2}\left(\mathcal X^T \Lambda \mathcal X - \mathcal X^T \Lambda \mu - \mu^T\Lambda \mathcal X + \mu^T \Lambda \mu\right)\right] \end{aligned} Δ=exp[−21(XTΛ−μTΛ)(X−μ)]=exp[−21(XTΛX−XTΛμ−μTΛX+μTΛμ)]
此时观察小括号中的 X T Λ μ \mathcal X^T \Lambda\mu XTΛμ和 μ T Λ X \mu^T\Lambda \mathcal X μTΛX，其中 X , μ \mathcal X,\mu X,μ都是 p × 1 p \times 1 p×1的， Λ \Lambda Λ 是一个 p × p p \times p p×p的矩阵。因而有：
它们结果均是实数，根据‘乘法交换律’，结果是相等的~
X T Λ μ = μ T Λ X = ( x 1 , ⋯ , x p ) ( λ 11 , λ 12 , ⋯ , λ 1 p λ 21 , λ 22 , ⋯ , λ 2 p ⋮ λ p 1 , λ p 2 , ⋯ , λ p p ) ( μ 1 μ 2 ⋮ μ p ) = [ ∑ i = 1 p x i λ i 1 , ⋯ , ∑ i = 1 p x i λ i p ] ( μ 1 μ 2 ⋮ μ p ) = ∑ j = 1 p ∑ i = 1 p x i ⋅ λ i j ⋅ μ j \begin{aligned} \mathcal X^T\Lambda\mu = \mu^T \Lambda \mathcal X & = (x_1,\cdots,x_p) \begin{pmatrix} \lambda_{11},\lambda_{12},\cdots,\lambda_{1p} \\ \lambda_{21},\lambda_{22},\cdots,\lambda_{2p} \\ \vdots \\ \lambda_{p1},\lambda_{p2},\cdots,\lambda_{pp} \\ \end{pmatrix} \begin{pmatrix} \mu_1\\ \mu_2 \\ \vdots \\ \mu_p \end{pmatrix}\\ & = \left[\sum_{i=1}^p x_i \lambda_{i1},\cdots,\sum_{i=1}^p x_i\lambda_{ip} \right] \begin{pmatrix} \mu_1\\ \mu_2 \\ \vdots \\ \mu_p \end{pmatrix} \\ & = \sum_{j=1}^p \sum_{i=1}^p x_i \cdot \lambda_{ij} \cdot \mu_j \end{aligned} XTΛμ=μTΛX=(x1,⋯,xp)⎝⎜⎜⎜⎛λ11,λ12,⋯,λ1pλ21,λ22,⋯,λ2p⋮λp1,λp2,⋯,λpp⎠⎟⎟⎟⎞⎝⎜⎜⎜⎛μ1μ2⋮μp⎠⎟⎟⎟⎞=[i=1∑pxiλi1,⋯,i=1∑pxiλip]⎝⎜⎜⎜⎛μ1μ2⋮μp⎠⎟⎟⎟⎞=j=1∑pi=1∑pxi⋅λij⋅μj
将这两项合并，有：
Δ = exp [ − 1 2 ( X T Λ X − 2 μ T Λ X + μ T Λ μ ) ] \Delta = \exp \left[-\frac{1}{2}\left(\mathcal X^T\Lambda\mathcal X - 2 \mu^T \Lambda \mathcal X + \mu^T \Lambda \mu\right)\right] Δ=exp[−21(XTΛX−2μTΛX+μTΛμ)] - 继续观察，其中 μ T Λ μ \mu^T \Lambda \mu μTΛμ依然是模型参数表示的量，和 X \mathcal X X无关。因此原式可表示为：
精度矩阵Λ \Lambda Λ本身是‘实对称矩阵’，因而有Λ T = Λ \Lambda^T = \Lambda ΛT=Λ,从而有μ T Λ T = ( Λ μ ) T . \mu^T\Lambda^T = (\Lambda \mu)^T. μTΛT=(Λμ)T.
Δ ∝ exp [ − 1 2 X T Λ X + μ T Λ X ] = exp [ − 1 2 X T Λ X + ( Λ μ ) T X ] \begin{aligned} \Delta & \propto \exp \left[-\frac{1}{2} \mathcal X^T \Lambda \mathcal X + \mu^T \Lambda \mathcal X\right] \\ & = \exp \left[-\frac{1}{2} \mathcal X^T \Lambda \mathcal X + \left(\Lambda\mu \right)^T \mathcal X\right] \end{aligned} Δ∝exp[−21XTΛX+μTΛX]=exp[−21XTΛX+(Λμ)TX]
观察中括号中的项，其中 − 1 2 X T Λ X -\frac{1}{2} \mathcal X^T \Lambda \mathcal X −21XTΛX是； ( μ Λ ) T X \left(\mu \Lambda\right)^T \mathcal X (μΛ)TX是。
称 Λ μ \Lambda \mu Λμ为势向量(Potential Vector)。
点势函数关联的项
关于某一维特征 x i x_i xi，观察哪些项？
- 首先观察 − 1 2 X T Λ X -\frac{1}{2} \mathcal X^T \Lambda \mathcal X −21XTΛX，将它展开：
− 1 2 X T Λ X = − 1 2 [ ( x 1 , ⋯ , x p ) ( λ 11 , λ 12 , ⋯ , λ 1 p λ 21 , λ 22 , ⋯ , λ 2 p ⋮ λ p 1 , λ p 2 , ⋯ , λ p p ) ( x 1 ⋮ x p ) ] = − 1 2 [ ∑ i = 1 p x i λ i 1 , ⋯ , ∑ i = 1 p x i λ i p ] ( x 1 ⋮ x p ) = − 1 2 ∑ j = 1 p ∑ i = 1 p x i ⋅ x j ⋅ λ i j \begin{aligned} -\frac{1}{2} \mathcal X^T \Lambda \mathcal X & = -\frac{1}{2} \left[ (x_1,\cdots,x_p) \begin{pmatrix} \lambda_{11},\lambda_{12},\cdots,\lambda_{1p} \\ \lambda_{21},\lambda_{22},\cdots,\lambda_{2p} \\ \vdots \\ \lambda_{p1},\lambda_{p2},\cdots,\lambda_{pp} \\ \end{pmatrix}\begin{pmatrix} x_1 \\ \vdots \\ x_p \end{pmatrix}\right] \\ & = - \frac{1}{2}\left[\sum_{i=1}^p x_i \lambda_{i1},\cdots,\sum_{i=1}^p x_i \lambda_{ip}\right]\begin{pmatrix} x_1 \\ \vdots \\ x_p \end{pmatrix} \\ & = -\frac{1}{2} \sum_{j=1}^p \sum_{i=1}^p x_i \cdot x_j \cdot \lambda_{ij} \end{aligned} −21XTΛX=−21⎣⎢⎢⎢⎡(x1,⋯,xp)⎝⎜⎜⎜⎛λ11,λ12,⋯,λ1pλ21,λ22,⋯,λ2p⋮λp1,λp2,⋯,λpp⎠⎟⎟⎟⎞⎝⎜⎛x1⋮xp⎠⎟⎞⎦⎥⎥⎥⎤=−21[i=1∑pxiλi1,⋯,i=1∑pxiλip]⎝⎜⎛x1⋮xp⎠⎟⎞=−21j=1∑pi=1∑pxi⋅xj⋅λij
该展开式中仅和 x i x_i xi相关的项只有：
− 1 2 x i ⋅ x i ⋅ λ i i -\frac{1}{2} x_i \cdot x_i \cdot \lambda_{ii} −21xi⋅xi⋅λii - 然后观察 ( μ Λ ) T X \left(\mu \Lambda\right)^T \mathcal X (μΛ)TX，展开结果如下：
( μ Λ ) T X = [ ( λ 11 , λ 12 , ⋯ , λ 1 p λ 21 , λ 22 , ⋯ , λ 2 p ⋮ λ p 1 , λ p 2 , ⋯ , λ p p ) ( μ 1 ⋮ μ p ) ] T ( x 1 ⋮ x p ) = [ ∑ i = 1 p λ 1 i ⋅ μ i , ⋯ , ∑ i = 1 p λ p i ⋅ μ i ] ( x 1 ⋮ x p ) = ∑ j = 1 p ∑ i = 1 p λ j i ⋅ μ i ⋅ x j \begin{aligned} \left(\mu \Lambda\right)^T \mathcal X & = \left[\begin{pmatrix} \lambda_{11},\lambda_{12},\cdots,\lambda_{1p} \\ \lambda_{21},\lambda_{22},\cdots,\lambda_{2p} \\ \vdots \\ \lambda_{p1},\lambda_{p2},\cdots,\lambda_{pp} \\ \end{pmatrix}\begin{pmatrix}\mu_1 \\ \vdots \\ \mu_p \end{pmatrix}\right]^T \begin{pmatrix} x_1 \\ \vdots \\ x_p \end{pmatrix} \\ & = \left[\sum_{i=1}^p \lambda_{1i} \cdot \mu_i,\cdots,\sum_{i=1}^p \lambda_{pi} \cdot \mu_i\right]\begin{pmatrix} x_1 \\ \vdots \\ x_p \end{pmatrix} \\ & = \sum_{j=1}^p \sum_{i=1}^p \lambda_{ji} \cdot \mu_i \cdot x_j \end{aligned} (μΛ)TX=⎣⎢⎢⎢⎡⎝⎜⎜⎜⎛λ11,λ12,⋯,λ1pλ21,λ22,⋯,λ2p⋮λp1,λp2,⋯,λpp⎠⎟⎟⎟⎞⎝⎜⎛μ1⋮μp⎠⎟⎞⎦⎥⎥⎥⎤T⎝⎜⎛x1⋮xp⎠⎟⎞=[i=1∑pλ1i⋅μi,⋯,i=1∑pλpi⋅μi]⎝⎜⎛x1⋮xp⎠⎟⎞=j=1∑pi=1∑pλji⋅μi⋅xj
其中和 x i x_i xi有关的项一共有 p p p项：
λ i 1 ⋅ μ 1 ⋅ x i , ⋯ , λ i p ⋅ μ p ⋅ x i ⏟ p 项 \underbrace{\lambda_{i1} \cdot \mu_1 \cdot x_i ,\cdots,\lambda_{ip} \cdot \mu_p \cdot x_i}_{p项} p项 λi1⋅μ1⋅xi,⋯,λip⋅μp⋅xi
如果令 H = ( h 1 , ⋯ , h p ) = Λ μ \mathcal H = (h_1,\cdots,h_p) = \Lambda \mu H=(h1,⋯,hp)=Λμ，对应的 h i h_i hi项就是只与 x i x_i xi有关的项：
h i = ∑ k = 1 p λ i k ⋅ μ k h_i = \sum_{k=1}^p \lambda_{ik} \cdot \mu_k hi=k=1∑pλik⋅μk
至此，仅和 x i x_i xi相关的项表示如下：
− 1 2 x i ⋅ x i ⋅ λ i i + h i ⋅ x i -\frac{1}{2} x_i \cdot x_i \cdot \lambda_{ii} + h_i \cdot x_i −21xi⋅xi⋅λii+hi⋅xi
边势函数相关的项
同理，观察哪些项？
这里就不重新展开了，感兴趣的小伙伴可以自行找一下~
- 二次项中和 x i , x j x_i,x_j xi,xj同时相关的项：
因为精度矩阵Λ \Lambda Λ是实对称矩阵，因而有λ i j = λ j i \lambda_{ij} = \lambda_{ji} λij=λji.
− 1 2 [ x i ⋅ x j ⋅ λ i j + x j ⋅ x i ⋅ λ j i ] = − λ i j ⋅ x i ⋅ x j -\frac{1}{2}[x_i \cdot x_j \cdot \lambda_{ij} + x_j \cdot x_i \cdot \lambda_{ji}] = - \lambda_{ij} \cdot x_i \cdot x_j −21[xi⋅xj⋅λij+xj⋅xi⋅λji]=−λij⋅xi⋅xj - 一次项不可能同时与 x i , x j x_i,x_j xi,xj相关，因此自然是没有的~
至此，可以将仅关于单个点 x i ( i = 1 , 2 , ⋯ , p ) x_i(i=1,2,\cdots,p) xi(i=1,2,⋯,p)的项看作；将关于两个结点 x i , x j ( i , j ∈ { 1 , 2 , ⋯ , p } ; i ≠ j ) x_i,x_j(i,j \in \{1,2,\cdots,p\};i \neq j) xi,xj(i,j∈{1,2,⋯,p};i=j)的项看作。
关于多元高斯分布学习任务的核心思想
通过上述描述可以发现，如果 λ i j = 0 \lambda_{ij} = 0 λij=0，意味着结点 x i , x j x_i,x_j xi,xj之间的，因而 x i , x j x_i,x_j xi,xj两结点之间：
该推导过程本质上就是‘精度矩阵与条件独立性’的证明。如果两结点之间不存在直接相连的边，根据成对马尔可夫性,这两个结点就是相互独立的。
x i ⊥ x j ∣ x − i − j ⇔ λ i j = 0 x_i \perp x_j \mid x_{-i-j} \Leftrightarrow \lambda_{ij} = 0 xi⊥xj∣x−i−j⇔λij=0
从高斯网络的角度去观察 (Learning)，发现它不仅仅学习了参数，还学习了(精度矩阵 Λ = [ λ i j ] p × p \Lambda = [\lambda_{ij}]_{p \times p} Λ=[λij]p×p)。
关于条件独立性的总结
从特征之间独立性的角度观察：
-
边缘相互独立/绝对相互独立(Marginal Independent)：
x i ⊥ x j ; Σ = [ σ i j ] p × p ⇔ σ i j = 0 x_i \perp x_j ;\Sigma = [\sigma_{ij}]_{p \times p} \Leftrightarrow \sigma_{ij} = 0 xi⊥xj;Σ=[σij]p×p⇔σij=0 -
条件独立性(Conditional Independence)：
x i ⊥ x j ∣ x − i − j ; Λ = Σ − 1 = [ λ i j ] p × p ⇔ λ i j = 0 x_i \perp x_j \mid x_{-i-j} ;\Lambda = \Sigma^{-1} = [\lambda_{ij}]_{p \times p} \Leftrightarrow \lambda_{ij} = 0 xi⊥xj∣x−i−j;Λ=Σ−1=[λij]p×p⇔λij=0 -
对于任意一个高斯马尔可夫随机场，关于 x i x_i xi的条件概率分布 P ( x i ∣ x − i ) \mathcal P(x_i \mid x_{-i}) P(xi∣x−i)同样服从高斯分布，对应高斯分布表示如下：
x − i x_{-i} x−i表示随机变量集合X \mathcal X X中除去x i x_i xi之外的其他随机变量。
∀ x i , P ( x i ∣ x − i ) ∼ N ( ∑ j ≠ i λ i j λ i i x j , λ i i − 1 ) \forall x_i,\mathcal P(x_i \mid x_{-i}) \sim \mathcal N(\sum_{j \neq i} \frac{\lambda_{ij}}{\lambda_{ii}} x_j,\lambda_{ii}^{-1}) ∀xi,P(xi∣x−i)∼N(j=i∑λiiλijxj,λii−1)
这个思想和高斯分布推断任务中的已知联合概率分布 P ( X ) = P ( x A , x B ) \mathcal P(\mathcal X) = \mathcal P(x_{\mathcal A},x_{\mathcal B}) P(X)=P(xA,xB)，求解条件概率分布 P ( x A ∣ x B ) \mathcal P(x_{\mathcal A} \mid x_{\mathcal B}) P(xA∣xB)完全一致。只不过这里将随机变量集合划分成两部分：- x i x_i xi单独一部分；
- 除去 x i x_i xi之外的其他随机变量为一部分。
这里不推导了~
观察上式的均值部分：如果 λ i j = 0 \lambda_{ij} = 0 λij=0，对应均值结果针对 x j x_j xj的项为0。至此，剩余的结果如：
这里只是举个例子，至少有一个特征x k x_k xk的对应结果不为0，这意味着x k x_k xk和x i x_i xi之间存在边。
∑ j ≠ i λ i j λ i i x j = 0 + ⋯ + λ i k λ i i x k + 0 + ⋯ + 0 \sum_{j\neq i} \frac{\lambda_{ij}}{\lambda_{ii}} x_j = 0 + \cdots + \frac{ \lambda_{ik}}{\lambda_{ii}}x_k + 0 + \cdots + 0 j=i∑λiiλijxj=0+⋯+λiiλikxk+0+⋯+0
因此，可以将 x i x_i xi看作与其相连的 x j x_j xj的线性组合，这些结点在马尔可夫随机场结构表示中介绍过，被称作马尔可夫毯(Markov Blanket)。
至此，高斯网络部分介绍结束。
相关参考：
机器学习-高斯网络(3)-高斯马尔可夫随机场