BriefGPT.xyz
Jun, 2012
图形模型推理的复杂度
Complexity of Inference in Graphical Models
HTML
PDF
Venkat Chandrasekaran, Nathan Srebro, Prahladh Harsha
TL;DR
本文研究图形单元中结构的限制及其与推理难度之间的关系，发现较低的树宽是确保推理可行性的唯一结构限制，即使是最优情况下的图结构，也不存在多项式时间复杂度的推理算法。
Abstract
It is well-known that
inference
in
graphical models
is hard in the worst case, but tractable for models with bounded
treewidth
. We ask whe
→