Ising图模型概率推理的计算复杂性

• 作者: 陈亚瑞
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: Ising图模型 概率推理 计算复杂性 难解性 不可近似性
• 年，卷（期）: 2013,（2）
• 所属期刊栏目: 人工智能
• 页码范围: 253-256,288
• 页数: 5页
• 分类号: TP181
• 字数: 6360字
• 语种: 中文

摘要

图模型概率推理的主要任务是通过对联合概率分布进行变量求和来计算配分函数、变量边缘概率分布、条件概率分布等.图模型概率推理计算复杂性及近似概率推理的计算复杂性是一重要的理论问题,也是设计概率推理算法和近似概率推理算法的理论基础.研究了Ising图模型概率推理的计算复杂性,包括概率推理的难解性及不可近似性.具体地,通过构建#2 SAT问题到Ising图模型概率推理问题的多项式时间计数归约,证明在一般Ising图模型上计算配分函数、变量边缘概率分布、条件概率分布的概率推理问题是#P难的,同时证明Ising图模型近似概率推理问题是NP难的,即一般Ising图模型上的概率推理问题是难解且不可近似的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈亚瑞	天津科技大学计算机科学与信息工程学院	10	31	3.0	5.0