Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networks
Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networks
复制标题
DOI：
--
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
Diarmaid Conaty;Cassio Polpo de Campos-;D. Mauá
中科院分区：
文献类型：
--
作者：
Diarmaid Conaty;Cassio Polpo de Campos-;D. Mauá
讨论了和积网络中近似最大后验推理的计算复杂度。我们首先通过最大独立集的约简证明了高度为2的树的np -硬度；这意味着在次线性因子内的非近似性。我们证明这是一个紧界，因为我们可以在高度为2的网络中找到一个线性因子的近似值。然后我们证明，在高度为3的树中，对于输入大小为n的任何次线性函数f，在因子2^{f(n)}$内逼近问题是np困难的。同样，这个界是紧的，因为我们证明了通常的最大积算法（在任何网络中）在因子$2^{c \cdot n}$内找到某些常数$c < 1$的近似值。最后，我们提出了一个简单的算法，并证明了它产生的解至少与最大积算法一样好，甚至可能比最大积算法更好。我们利用合成网络和真实网络对该算法进行了实证分析。
We discuss the computational complexity of approximating maximum a posteriori inference in sum-product networks. We first show NP-hardness in trees of height two by a reduction from maximum independent set; this implies non-approximability within a sublinear factor. We show that this is a tight bound, as we can find an approximation within a linear factor in networks of height two. We then show that, in trees of height three, it is NP-hard to approximate the problem within a factor $2^{f(n)}$ for any sublinear function $f$ of the size of the input $n$. Again, this bound is tight, as we prove that the usual max-product algorithm finds (in any network) approximations within factor $2^{c \cdot n}$ for some constant $c < 1$. Last, we present a simple algorithm, and show that it provably produces solutions at least as good as, and potentially much better than, the max-product algorithm. We empirically analyze the proposed algorithm against max-product using synthetic and realistic networks.