Tsai-Ching Lu

UAI Conference 2009 Conference Paper

Most Relevant Explanation: Properties, Algorithms, and Evaluations

• Changhe Yuan
• Xiaolu Liu
• Tsai-Ching Lu
• Heejin Lim

nostic system. Given that so many variables are involved, even the best solution by MAP or MPE may have an ex- −6 Most Relevant Explanation (MRE) is a method for nding multivariate explanations for given evidence in Bayesian networks [12]. tremely low probability, say in the order of 10. It is hard to make any decision based on such hypotheses. This pa- In real-world problems, it is observed that usually only a per studies the theoretical properties of MRE few target variables are most relevant in explaining any and develops an algorithm for nding multiple given evidence. For example, there are many possible dis- top MRE solutions. Our study shows that MRE eases in a medical domain, but a patient can have at most relies on an implicit soft relevance measure in a few diseases at one time, as long as he or she does not automatically identifying the most relevant tar- delay treatments for too long. It is desirable to nd diag- get variables and pruning less relevant variables nostic hypotheses containing only those relevant diseases. from an explanation. The soft measure also en- Other diseases should be excluded from further tests or ables MRE to capture the intuitive phenomenon treatments. In a recent work, Yuan and Lu [12] propose of explaining away encoded in Bayesian net- an approach called Most Relevant Explanation (MRE) to works. Furthermore, our study shows that the generate explanations containing only the most relevant tar- solution space of MRE has a special lattice struc- get variables for given evidence in Bayesian networks. Its ture which yields interesting dominance relations main idea is to traverse a trans-dimensional space contain- among the solutions. A K-MRE algorithm based ing all the partial instantiations of the target variables and on these dominance relations is developed for nd one instantiation that maximizes a relevance measure generating a set of top solutions that are more called generalized Bayes factor [3]. representative. Our empirical results show that shown in [12] to be able to nd precise and concise ex- MRE methods are promising approaches for ex- planations. This paper provides a study of the theoretical planation in Bayesian networks. properties of MRE and offers further evidence for its valid- The approach was ity. The study shows that MRE relies on an implicit soft relevance measure that enables the automatic identi cation

UAI Conference 2004 Conference Paper

Annealed MAP

• Changhe Yuan
• Tsai-Ching Lu
• Marek J. Druzdzel

Maximum a Posteriori assignment (MAP) is the problem of finding the most probable instantiation of a set of variables given the partial evidence on the other variables in a Bayesian network. MAP has been shown to be a NP-hard problem [22], even for constrained networks, such as polytrees [18]. Hence, previous approaches often fail to yield any results for MAP problems in large complex Bayesian networks. To address this problem, we propose AnnealedMAP algorithm, a simulated annealing-based MAP algorithm. The AnnealedMAP algorithm simulates a non-homogeneous Markov chain whose invariant function is a probability density that concentrates itself on the modes of the target density. We tested this algorithm on several real Bayesian networks. The results show that, while maintaining good quality of the MAP solutions, the AnnealedMAP algorithm is also able to solve many problems that are beyond the reach of previous approaches.

UAI Conference 2000 Conference Paper

Causal Mechanism-based Model Constructions

• Tsai-Ching Lu
• Marek J. Druzdzel
• Tze-Yun Leong