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

摘要：

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

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

所属期刊栏目：37

分类号：TPL81

资助基金：国家自然科学基金60678049;天津市应用基础研究计划基金07JCYBJC14600

在线出版日期：2011-01-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：207-210,245