Browse Prior Art Database

Finding the Top K Most Relevant Explanation in Bayesian Networks

IP.com Disclosure Number: IPCOM000196872D
Publication Date: 2010-Jun-18

Publishing Venue

The IP.com Prior Art Database

Abstract

Maximum a Posteriori (MAP) or Most Probable Explanation (MPE) are popular approaches of finding explanations for given evidence in Bayesian networks. One of their limitations is that they have to find a complete assignment to a set of target variables. However, it is often the case that only a few of the target variables are most relevant in explaining the evidence. In [17], the problem of finding the most relevant variables is formulated as explanatory MAP (eMAP), which considers all subsets of the target variables and finds a partial assignment that maximizes a chosen quality measure. Quality measures such as likelihood function and Bayes Factor are compared. It was shown that Bayes Factor is preferable for sequential decision making where prior and posterior probabilities are properly taken into account.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 20

SEND COMPLETED DISCLOSURE TO: TECHNOLOGY INFORMATION OFFICE ATTN: Chris Harrison, MS RL55
HRL LABORATORIES, LLC Telephone No - 5459

8. SUMMARY OF THE INVENTION

A. GIVE A BRIEF DESCRIPTION OF YOUR INVENTION, PARTICULARLY POINTING OUT WHAT IS BELIEVED TO BE NOVEL (THE "HEART" OF WHAT IS NEW).

Maximum a Posteriori (MAP) or Most Probable Explanation (MPE) are popular approaches of finding explanations for given evidence in Bayesian networks. One of their limitations is that they have to find a complete assignment to a set of target variables. However, it is often the case that only a few of the target variables are most relevant in explaining the evidence. In [17], the problem of finding the most relevant variables is formulated as explanatory MAP (eMAP), which considers all subsets of the target variables and finds a partial assignment that maximizes a chosen quality measure. Quality measures such as likelihood function and Bayes Factor are compared. It was shown that Bayes Factor is preferable for sequential decision making where prior and posterior probabilities are properly taken into account.

In [18], we reformulate the explanatory MAP problem into the problem of Most Relevant Explanation (MRE) which finds concise multivariate explanations for given evidence in Bayesian networks. We focus on developing approximate methods for MRE, because the similar problem of MAP has been shown to be NPPP

complete [13]. In particular, due to the need of finding solutions in the trans-dimensional space of variables and their configurations, we propose a Reversible Jump MCMC algorithm based on simulated annealing for solving MRE.

In this invention, we further study the theoretical properties of MRE and develop a method for finding top MRE solutions. We show that MRE not only can automatically prune (conditionally) independent variables from an explanation but also defines a soft relevance measure that allows pruning less relevant variables. The soft measure also enables MRE to capture the intuitive phenomenon of explaining away encoded in Bayesian networks. Furthermore, we show that the solution space of MRE has a special lattice structure which yields interesting dominance relations among the solutions. We develop a K-MRE algorithm based on these dominance relations for generating a much more representative set of top solutions. Our empirical results show that MRE and K-MRE are promising and effective explanation methods.

HRL PROPRIETARY AND SENSITIVE (when completed)

THIS DOCUMENT CONTAINS PROPRIETARY INFORMATION, AND EXCEPT WITH WRITTEN PERMISSION OF HRL LABORATORIES, LLC, SUCH INFORMATION SHALL NOT BE PUBLISHED, OR DISCLOSED TO OTHERS, OR USED FOR ANY PURPOSE, AND THE DOCUMENT SHALL NOT BE DUPLICATED IN WHOLE OR IN PART. THIS

LEGEND SHALL BE APPLIED TO ALL DOCUMENTS CONTAINING THIS INFORMATION.

INVENTION DOCKET NO.

READ AND UNDERSTOOD BY:

David Allen Wojtek Przytula

  WITNESS NAME (TYPE) SIGNATURE DATE WITNESS NAME (TYPE) SIGNATURE DATE
(EACH PA...