Ising图模型概率推理的参数化复杂性

Parameterized Complexity of Probabilistic Inference in Ising Graphical Model

Ising图模型概率推理的主要工作是通过变量求和来计算配分函数和边缘概率分布。传统计算复杂性理论证明Ising图模型精确概率推理是#P难的,并且Ising图模型近似概率推理是NP难的。研究了Ising图模型精确概率推理和Ising均值场近似概率推理的参数化复杂性。首先证明了不同参数的Ising图模型概率推理的参数化复杂性定理,指出基于变量个数或图模型树宽的参数化概率推理问题是固定参数可处理的。然后证明了Ising均值场的参数化复杂性定理,指出基于自由分布树宽、迭代次数和变量个数的参数化Ising均值场是固定参数可处理的;进一步,当Ising图模型参数满足Ising均值场迭代式压缩条件时,基于自由分布树宽和迭代次数的参数化Ising均值场是固定参数可处理的。

Probabilistic inference of the Ising graphical model is to compute the partition function and the marginal probabilistic distribution through summing variables.Traditional computational complexity theory shows that the exact probabilistic inference of the Ising graphical model is # P-hard,and the approximate probabilistic inference is NP-hard.We analyzed the parameterized complexities of exact probabilistic inference of the Ising graphical model and the Ising mean field approximate inference.First,we proved the parameterized complexity theorems of probabilistic inference of the Ising graphical model with different parameters,which show that parameterized probabilistic inferences are fixed parameter tractable with the variable number and the graphical model treewidth as parameters respectively.Then,we proved the parameterized complexity theorems of the Ising mean field,which demonstrate that the parameterized Ising mean field is fixed parameter tractable with the combination of the free distribution treewidth,the number of iteration steps and the number of variables as parameter;furthermore,when the Ising graphical model parameters satisfy the contraction condition of the Ising mean field iteration formula,the parameterized Ising mean field is fixed parameter tractable with the combination of the free distribution treewidth and the number of iteration steps as parameter.