关键词: Ising图模型，概率推理，Icing均值场，参数化复杂性，固定参数可处理

Abstract: 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 arc 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.

Key words: Ising graphical model, Probabilistic inference, Ising mean field, Parameterized complexity, Fixed parameter tractable