Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Equivalences between maximum a posteriori inference in Bayesian networks and maximum expected utility computation in influence diagrams

Full text
Author(s):
Maua, Denis Deratani
Total Authors: 1
Document type: Journal article
Source: INTERNATIONAL JOURNAL OF APPROXIMATE REASONING; v. 68, p. 211-229, JAN 2016.
Web of Science Citations: 3
Abstract

Two important tasks in probabilistic reasoning are the computation of the maximum posterior probability of a given subset of the variables in a Bayesian network (MAP), and the computation of the maximum expected utility of a strategy in an influence diagram (MEU). Both problems are NPPP-hard to solve, and NP-hard to approximate when the treewidth of the underlying graph is bounded. Despite the similarities, researches on both problems have largely been conducted independently, with algorithmic solutions and insights designed for one problem not (trivially) transferable to the other one. In this work, we show constructively that these two problems are equivalent in the sense that any algorithm designed for one problem can be used to solve the other with small overhead. Moreover, the reductions preserve the boundedness of treewidth. Building on the known complexity of MAP on networks whose parameters are imprecisely specified, we show how to use the reductions to characterize the complexity of MEU when the parameters are set-valued. These equivalences extend the toolbox of either problem, and shall foster new insights into their solution. (C) 2015 Elsevier Inc. All rights reserved. (AU)

FAPESP's process: 13/23197-4 - Efficient algorithms for graph-based decision making under uncertainty
Grantee:Denis Deratani Mauá
Support type: Scholarships in Brazil - Post-Doctorate