Abstract
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 real-world data.
Original language | English |
---|---|
Title of host publication | Proceedings of The 33rd Conference on Uncertainty in Artificial Intelligence |
Publisher | AUAI |
Number of pages | 10 |
Publication status | Published - 01 Aug 2017 |
Event | The 33rd Conference on Uncertainty in Artificial Intelligence (UAI) - ICC, Sydney, Australia Duration: 12 Aug 2017 → 14 Aug 2017 http://auai.org/uai2017 http://www.auai.org |
Conference
Conference | The 33rd Conference on Uncertainty in Artificial Intelligence (UAI) |
---|---|
Abbreviated title | UAI |
Country/Territory | Australia |
City | Sydney |
Period | 12/08/2017 → 14/08/2017 |
Internet address |