Ising图模型的区间传播推理方法

摘要

本发明公开了一种基于Ising图模型的区间传播推理方法，该方法的主要步骤：首先基于Ising图模型建立Ising均值场截枝计算树；然后基于Ising均值场截枝计算树运用均值场区间传播算法，给出根节点变量期望界。本发明该推理方法具有较低的计算复杂性，并通过变量期望界给出了有效的推理精度。

主权项

1.一种Ising图模型的区间传播推理方法，通过定义Ising均值场计算树，并在计算树上实现期望区间传播推理过程，其特征在于，包括下列步骤：(1)定义Ising均值场计算树：在Ising均值场推理下，变量簇c_γ的计算树模型为一四元组T(D_γ，R，M，Q)，其中：1)D_γ：以c_γ为根节点的变量簇节点集D_γ＝{c_γ}∪Ch(c_γ)∪Ch(Ch(c_γ))∪…，其中，Ch(c_γ)表示c_γ的子节点集，Ch(c_γ)＝{c_β|x_i∈c_γ，x_j∈c_β，(i，j)∈E，γ≠β}，Ch(Ch(c_γ))表示变量集Ch(c_γ)的子节点集合：$\mathrm{Ch}\left(\mathrm{Ch}\left(c_{\gamma }\right)\right)={\cup }_{c_{\beta }\in \mathrm{Ch}\left(c_{\gamma }\right)}\mathrm{Ch}\left(c_{\beta }\right),$2)R：关系集R＝{<c_α，c_β>|c_α∈D_γ，c_β∈Ch(c_α)}，其中，关系<c_α，c_β>表示c_β是c_α的子节点，3)M：计算树上的消息自底向上单向传播，记$M_{\alpha -\mathrm{out}}=\left\{{\mu }_i\right|i\in V_{c_{\alpha }}\}$表示c_α输出消息集，$M_{\alpha -\mathrm{in}}={\cup }_{c_{\beta }\in \mathrm{Ch}\left(c_{\alpha }\right)}{M}_{\beta -\mathrm{out}}$表示c_α输入消息集，则M＝{M_α-out|c_α∈D_γ}，4)Q：概率分布集Q＝{q_α(c_α；θ′_α)|c_α∈D_γ}，且${\theta }_{\mathrm{ij}}{x}_i{x}_j\propto \exp \{\underset{i\in V_{c_{\alpha }}}{\Sigma }{{\theta }^{\prime }}_i{x}_i+\underset{(i,j)\in E_{c_{\alpha }}}{\Sigma }{\theta }_{\mathrm{ij}}{x}_i{x}_j\},$其中，${{\theta }^{\prime }}_i={\theta }_i+\underset{{\mu }_t\in M_{\alpha -\mathrm{in}}}{\Sigma }{\theta }_{\mathrm{it}}{\mu }_t,$(2)定义Ising均值场截枝计算树：Ising均值场推理下，变量簇c_γ的剪枝计算树模型是一四元组T_c(D_γ，R，M，Q)，其中：1)D_γ：以c_γ为根节点的变量簇节点集D_γ＝{c_γ}∪CCh(c_γ)∪CCh(CCh(c_γ))∪…，其中，CCh(c_γ)表示c_γ的子节点集，CCh(c_γ)＝Ch(c_γ)/An(c_γ)，CCh(CCh(c_γ))表示变量集CCh(c_γ)的截枝子节点集：$\mathrm{CCh}\left(\mathrm{CCh}\left(c_{\gamma }\right)\right)={\cup }_{c_{\beta }\in \mathrm{CCh}\left(c_{\gamma }\right)}\mathrm{CCh}\left(c_{\beta }\right),$2)R：关系集R＝{<c_α，c_β>|c_α∈D_γ，c_β∈CCh(c_α)}，其中，关系<c_α，c_β>表示c_β是c_α的子节点，3)M：计算树上的消息自底向上单向传播，记$M_{\alpha -\mathrm{out}}=\left\{{\mu }_i\right|i\in V_{c_{\alpha }}\}$表示c_α输出消息集，$M_{\alpha -\mathrm{in}}={\cup }_{c_{\beta }\in \mathrm{Ch}\left(c_{\alpha }\right)}{M}_{\beta -\mathrm{out}}$表示c_α输入消息集，则M＝{M_α-out|c_α∈D_γ}，4)Q：概率分布集Q＝{q_α(c_α；θ′_α)|c_α∈D_γ}，且${\theta }_{\mathrm{ij}}{x}_i{x}_j\propto \exp \{\underset{i\in V_{c_{\alpha }}}{\Sigma }{{\theta }^{\prime }}_i{x}_i+\underset{(i,j)\in E_{c_{\alpha }}}{\Sigma }{\theta }_{\mathrm{ij}}{x}_i{x}_j\},$其中，${{\theta }^{\prime }}_i={\theta }_i+\underset{{\mu }_t\in M_{\alpha -\mathrm{in}}}{\Sigma }{\theta }_{\mathrm{it}}{\mu }_t;$(3)在截枝计算树上，根据c_α的输入消息区间计算该变量簇的概率分布区间，令M_α-in^int.表示变量簇c_α输入消息区间的集合，即$M_{\alpha -\mathrm{in}}^{\mathrm{int}.}=\left\{\right[{\mu }_t^l,{\mu }_t^u\left]\right|t\in V_{c_{\beta }},$c_β∈Ch(c_α)}，变量簇c_α概率分布的参数区间为${{\theta }_i}^{\prime l}=\min \{{\theta }_i+\underset{{\mu }_t\in M_{\alpha -\mathrm{in}}}{\Sigma }{\theta }_{\mathrm{it}}{\mu }_t|{\mu }_t^l\le {\mu }_t\le {\mu }_t^u\},$${{\theta }_i}^{\prime u}=\max \{{\theta }_i+\underset{{\mu }_t\in M_{\alpha -\mathrm{in}}}{\Sigma }{\theta }_{\mathrm{it}}{\mu }_t|{\mu }_t^l\le {\mu }_t\le {\mu }_t^u\},$${{\theta }_{\alpha }}^{\prime l}=\{{{\theta }_i}^{\prime l},{\theta }_{\mathrm{ij}}|i,j\in V_{c_{\alpha }},(i,j)\in E_{c_{\alpha }}\},$${{\theta }_{\alpha }}^{\prime u}=\{{{\theta }_i}^{\prime u},{\theta }_{\mathrm{ij}}|i,j\in V_{c_{\alpha }},(i,j)\in E_{c_{\alpha }}\}.$令A＝{a₁，a₂，…}，B＝{b₁，b₂，…}表示元素一一对应的等势集合，且A≤B＝{a_i≤b_i|i＝1，2，…}，则变量簇节点c_α的概率分布区间为$\left\{q_{\alpha }(c_{\alpha };{{\theta }^{\prime }}_{\alpha })\right|{{\theta }_{\alpha }}^{\prime l}\le {{\theta }^{\prime }}_{\alpha }\le {{\theta }_{\alpha }}^{\prime u}\};$(4)基于变量簇的概率分布区间，利用和积算法计算变量簇c_α的输出消息区间：在概率分布q_α(c_α；θ′_α)上运行和积算法计算变量x_i∈c_α的期望μ_i，即μ_i＝Sum-Prod(q_α(c_α；θ′_α))，当给定参数θ′_i取值区间时，μ_i的极值取在参数区间的端点处，即：${\mu }_i^l=\min \{\mathrm{Sum}-\mathrm{Prod}\left(q_{\alpha }(c_{\alpha };{{\theta }^{\prime }}_{\alpha })\right)|({{\theta }^{\prime }}_1,{{\theta }^{\prime }}_2,···)\in \{{{\theta }_1}^{\prime l},{{\theta }_1}^{\prime u}\}\times \{{{\theta }_2}^{\prime l},{{\theta }_2}^{\prime u}\}\times ···\},$${\mu }_i^u=\max \{\mathrm{Sum}-\mathrm{Prod}\left(q_{\alpha }(c_{\alpha };{{\theta }^{\prime }}_{\alpha })\right)|({{\theta }^{\prime }}_1,{{\theta }^{\prime }}_2,···)\in \{{{\theta }_1}^{\prime l},{{\theta }_1}^{\prime u}\}\times \{{{\theta }_2}^{\prime l},{{\theta }_2}^{\prime u}\}\times ···\},$则变量簇节点c_α输出消息区间集合为$M_{\alpha -\mathrm{out}}^{\mathrm{int}.}=\left\{\right[{\mu }_i^l,{\mu }_i^u]i\in V_{c_{\alpha }}\},$计算时，根据底层变量簇节点输入消息的取值区间，自底向上逐层进行消息区间传播计算出根变量簇变量期望区间。