J. A. Gamez, S. Moral, A. Salmeron (Eds.) Advances in Bayesian Networks Springer-Verlag Berlin Heidelberg GmbH St'udies in Fuzziness and Soft Computing, Volume 146 Editor-in-chief Prof. Janusz Kacprzyk Systems Research Institute Polish Academy of Sciences ul. Ne welska 6 01-447 Warsaw Poland E-mail: [email protected] Further volumes of this series Vol. 136. L. Wang (Ed.) Soft Computing in Communications, 2004 can be found on our homepage: ISBN 3-540-40575-5 springeronline.com Vol. 137. V. Loia, M. Nikravesh, L.A. Zadeh (Eds.) Fuzzy Logic and the Internet, 2004 Vol127. L. Reznik, V. Kreinovich (Eds.) ISBN 3-540-20180-7 Soft Computing in Measurement and Information Acquisition, 2003 Vol. 138. S. Sirmakessis {Ed.) ISBN 3-540-00246-4 Text Mining and its Applications, 2004 ISBN 3-540-20238-2 Vol128. J. Casillas, 0. Cord6n, F. Herrera, L. Magdalena (Eds.) Vol. 139. M. Nikravesh, B. Azvine, I. Yager, L.A. Interpretability Issues in Fuzzy Modeling, 2003 Zadeh (Eds.) ISBN 3-540-02932-X Enhancing the Power of the Internet, 2004 ISBN 3-540-20237-4 Vol129. J. Casillas, 0. Cord6n, F. Herrera, L. Magdalena (Eds.) Vol. 140. A. Abraham, L.C. Jain, B.J. van der Accuracy Improvements in Linguistic Fuzzy Zwaag (Eds.) Modeling, 2003 Innovations in Intelligent Systems, 2004 ISBN 3-540-02933-8 ISBN 3-540-20265-X Vol130. P.S. Nair Vol. 141. G. C. Onwubolu, B.V. Babu Uncertainty in Multi-Source Databases, 2003 New Optimzation Techniques in Engineering, ISBN 3-540-03242-8 2004 ISBN 3-540-20167-X Vol131. J.N. Mordeson, D.S. Malik, N. Kuroki Fuzzy Semigroups, 2003 Vol. 142. M. Nikravesh, L.A. Zadeh, V. Korotkikh ISBN 3-540-03243-6 (Eds.) Fuzzy Partial Differential Equations and Vol132. Y. Xu, D. Ruan, K. Qin, J. Liu Relational Equations, 2004 Lattice-Valued Logic, 2003 ISBN 3-540-20322-2 ISBN 3-540-40175-X Vol. 143. L. Rutkowski Vol. 133. Z.-Q. Liu, J. Cai, R. Buse New Soft Computing Techniques for System Handwriting Recognition, 2003 Modelling, Pattern Classification and Image ISBN 3-540-40177-6 Processing, 2004 ISBN 3-540-20584-5 Vol134. V.A. Niskanen Soft Computing Methods in Human Sciences, 2004 Vol. 144. Z. Sun, G.R. Finnie ISBN 3-540-00466-1 Intelligent Techniques in E-Commerce, 2004 ISBN 3-540-20518-7 Vol. 135. J.J. Buckley Vol. 145. J. Gil-Aluja Fuzzy Probabilities and Fuzzy Sets for Web Fuzzy Sets in the Management of Uncertainty, Planning, 2004 2004 ISBN 3-540-00473-4 ISBN 3-540-20341-9 Jose A. Gamez Serafin Moral Antonio Salmeron (Eds.) Advances in Bayesian Networks ~ Springer Dr. Jose A. Gamez Dr. Antonio Salmeron Universidad de Castilla-La Mancha Universidad de Almeria Escuela Politecnica Superior ETS Ingenieria Informatica Depto. Informatica Depto. Estadistica y Campus Universitario s/n Matematica Aplicada 02071 Albacete La Canada de San Urbano s/n Spain 04120 Almeria E-mail: [email protected] Spain E-mail: [email protected] Professor Serafin Moral Universidad de Granada ETS Ingenieria Informatica Depto. Ciencias Computacion Campus Universitario Fuentenueva 18071 Granada Spain E-mail: [email protected] ISBN 978-3-642-05885-1 ISBN 978-3-540-39879-0 (eBook) DOI 10.1007/978-3-540-39879-0 Library of Congress Cataloging-in-Publication-Data A catalog record for this book is available from the Library of Congress. Bibliographic information published by Die Deutsche Bibliothek. Die Deutsche Bibliothek lists this publication in the Deutsche Nationalbibliographie; detailed bibliographic data is available in the Internet at http://dnb.ddb.de This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitations, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. springeronline.com ©Springer-Verlag Berlin Heidelberg 2004 Originally published by Springer-Verlag Berlin Heidelberg New York in 2004 Softcover reprint of the hardcover I st edition 2004 The use of general descriptive names, registered names trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typesetting: Camera-ready by editors Cover design: E. Kirchner, Springer-Verlag, Heidelberg Printed on acid free paper 62/3020/M -5 4 3 2 1 0 Preface In the last years, probabilistic graphical models, specially Bayesian networks and decision graphs, have faced a significant theoretical development within areas such as Artificial Intelligence and Statistics. The sound theoretical foun dation of these models as well as their powerful semantics have allowed their application to a wide range of practical problems which involve tasks such as data mining, information retrieval, diagnosis or classification. But sev eral other applications based on Bayesian networks can be found, mainly in situations that require the modelisation of multivariate problems under uncertainty. A Bayesian network is actually a representation of a multivariate proba bility distribution by means of a graph, where each node represents a random variable and the arcs indicate probabilistic dependencies between neighbour nodes. Associated with each node there is a conditional distribution for the variable in that node given its parents in the graph, so that the joint dis tribution factorises as the product of all the conditional distribution in the network. The induced factorisation allows to deal with models involving a large amount of variables, since there is no need to represent the joint distri bution explicitly. One of the most common tasks carried out over Bayesian networks is the inference or probability propagation, which consists in collecting the updated information over some variables of interest given that some other variables have been observed. Probability propagation is known to be an NP-hard prob lem. It means that it is always possible to find problems in which preforming the inference may become unfeasible. This fact motivates the development of sophisticated algorithms with the aim of expanding the class of tractable problems. When the response time or the available hardware resources are limited, inference must be carried out by means of approximate methods, which trade accuracy for economy of resources. Influence Diagrams are graphical models in which apart from nodes rep resenting random variables, we have decisions and utilities. In general, we may have several decisions that are made in a given sequence. The objective is to compute the optimal policy for them. Bayesian network models can be constructed directly from an expert by means of Knowledge Engineering techniques, but when databases are avail able it is more usual to apply machine learning methods to construct the model without human intervention. The learning process involves two main aspects: deciding the network structure and estimating the parameters (the conditional distributions). The latest algorithms for structural learning are based on search strategies over the space of structures compatible with the problem variables, whose size is super-exponential. Regarding the parame- VI ters, they are usually estimated by maximum likelihood or by procedures of Bayesian Statistics. This book is a compendium with three main types of chapters: • Papers presenting some of the most recent advances in the area of prob abilistic graphical models. There are chapters devoted to foundations (Daneshkhah and Smith; Xiang and Chen), decision graphs (Lu and Druzdzel), learning from data (Blanco, Inza, and Larraiiaga; de Cam pos, Gamez and Puerta; Lucas; Kersting and Landwehr; Castelo and Perlman) and inference (Allen and Darwiche; Puch, Smith, and Bielza). • Applications to different fields, as speech recognition (Deviren and Khalid Daoudi), Meteorology (Carro, Sordo, and Gutierrez) and information re trieval (de Campos, Fermindez-Luna and Huete). • Survey papers describing the state of the art in some specific topics, as approximate propagation in Bayesian networks (Carro, Moral, and Salmeron), abductive inference (Gamez), decision graphs (Nielsen and Jensen), and applications of influence diagrams (Gomez). Some of the contributions to this book (those from the two first groups above) have been selected from the papers presented at the First Euro pean Workshop on Probabilistic Graphical models (PGM'02), held in Cuenca (Spain) in November 2002. Albacete, Jose A. Gamez Granada, Serafin Moral Almeria, Antonio Salmeron September, 2003 Contents Foundations Hypercausality, Randomisation Local and Global Independence............................... 1 Alireza Daneshkhah, Jim. Q.Smith 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Relationships Between Causality And Parameter Independence . . . . 4 3 The Multicausal Essential Graph.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4 Discussion ...... , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 7 Interface Verification for Multiagent Probabilistic Inference . . 19 Y. Xiang, X. Chen 1 Introduction... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2 Overview of MAMSBNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3 The Issue of Cooperative Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4 Checking Private Parents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5 Processing Public Parents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 6 Cooperative Verification in a General Hypertree . . . . . . . . . . . . . . . . . 33 7 Complexity ................... ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 8 Alternative Methods of Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Propagation Optimal Time-Space Tradeoff In Probabilistic Inference . . . . . . 39 David Allen, Adnan Darwiche 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2 Any-Space Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3 The Cache Allocation Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4 Time-Space Tradeoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Hierarchical Junction Trees................................... 57 Roberto 0. Puch, Jim Q. Smith, Concha Bielza 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2 Bayesian Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3 Junction Trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 VIII 4 Forecasting in the Dynamic Setting Using Junction Trees . . . . . . . . . 62 5 Hierarchical Junction Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Algorithms for Approximate Probability Propagation in Bayesian Networks............................ 77 Andres Cano, Serafin Moral, Antonio Salmeron 1 Approximate Probability Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . 77 2 The Complexity of Probability Propagation . . . . . . . . . . . . . . . . . . . . . 78 3 The Variable Elimination Algorithm............................ 79 4 Shenoy-Shafer Propagation.................................... 81 5 Monte Carlo Algorithms for Probability Propagation . . . . . . . . . . . . . 88 6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Abductive Inference in Bayesian Networks: A Review ........ 101 Jose A. Gamez 1 Introduction ................................................. 101 2 Abductive Inference in Probabilistic Reasoning .................. 102 3 Solving Total Abduction (MPE) in BNs ........................ 105 4 Solving Partial Abduction (MAP) in BNs ....................... 109 5 Complexity Results .......................................... 115 6 Conclusions ................................................. 116 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Influence Diagrams Causal Models, Value of Intervention, and Search for Opportunities ............................................. 121 Tsai-Ching Lu, Marek J. Druzdzel 1 Introduction ................................................. 121 2 Causal Models ............................................... 123 3 Augmented Models ........................................... 126 4 Value of Intervention ......................................... 128 5 Search for Opportunities ...................................... 130 6 Non-intervening Action ....................................... 133 7 Discussion .................................................. 133 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 Advances in Decision Graphs ................................. 137 Thomas D. Nielsen, Finn V. Jensen 1 Introduction ................................................. 137 2 Influence Diagrams ........................................... 138 3 Modeling Decision Problems ................................... 142 IX 4 Evaluating Decision Problems ................................. 150 5 Model Analysis .............................................. 154 References ..................................................... 156 Real-World Applications of Influence Diagrams ............... 161 Manuel Gomez 1 Decision Making Under Uncertainty ............................ 161 2 Artificial Intelligence, Expert Systems and Decision Support Systems162 3 Techniques to Build Complex DSSs ............................ 163 4 Real World Applications ...................................... 167 5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3 Learning Learning Bayesian Networks by Floating Search Methods ..... 181 Rosa Blanco, Iiiaki Inza, Pedro Larraiiaga 1 Introduction ................................................. 181 2 Learning Bayesian Networks by a Score+search Approach ......... 182 3 Floating Methods to Learn Bayesian Networks Structures ......... 187 4 Experimental Results ......................................... 191 5 Conclusions ................................................. 195 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 A Graphical Meta-Model for Reasoning about Bayesian Network Structure ............................................ 201 Luis M. de Campos, Jose A. Gamez, J. Miguel Puerta 1 Introduction ................................................. 201 2 Learning Bayesian Networks ................................... 202 3 Learning a Graphical Meta-Model .............................. 206 4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 5 Concluding Remarks ......................................... 212 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 Restricted Bayesian Network Structure Learning ............. 217 Peter J.F. Lucas 1 Introduction ................................................. 217 2 Background ................................................. 219 3 FANs: Forest-Augmented Bayesian Networks .................... 222 4 Evaluation .................................................. 225 5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232