Bayesian Reasoning with Graphical Models

ECTS: 4 (2S)

Instructors:             Concha Bielza, D-2110 (mcbielza@fi.upm.es)

                                    Pedro Larrañaga, D-2208 (pedro.larranaga@fi.upm.es)

Prerequisites:

• Familiarity with basic concepts of probability theory (including Bayes’ rule, multinomial and normal distributions).

Specific objectives:

• To understand the meaning and chances of probabilistic graphical models as a leading technology for reasoning with knowledge under uncertainty.
• To provide skills in different kinds of reasoning with these models: deductive, diagnostic, intercausal, or any combination of them.
• To construct a Bayesian network both with the aid of an expert or learning it from a data set.
• To address tasks as decision making, classification and data mining.
• To know existent salient applications and discover/suggest new ones.
• To use standard software (academic and commercial).

Course overview:

This course motivates and introduces graphical models (with special attention to Bayesian networks) as well consolidated and popular tools with the ability to represent knowledge under uncertainty and reason with it, one of the main challenges in building intelligent systems in Artificial Intelligence. Uncertainty is modelled with probability theory and reasoning is based on Bayes’ rule. Bayesian networks represent factorizations of joint probability distributions.  Nodes represent the variables of the domain and links represent the properties of conditional dependences and independences among the variables. The course will provide an in-depth exposition of theoretical and practical underpinnings.

The course starts explaining the meaning of these networks to model both causal and non-causal knowledge under uncertainty, and both from a structural viewpoint (qualitative) and from a parametric viewpoint (quantitative). The following step is to query the network about different issues of interest, i.e. to make inferences from evidence that is being gathered. For example, we can ask for the diagnosis of a disease or for the most probable explanation of the observed evidence. The inference algorithms can obtain an exact or an approximate answer, the latter being computed via e.g. Monte Carlo simulation. The network is built with the aid of a domain expert, but it can also be induced from a database. This calls modern learning algorithms including parameter learning and structure learning techniques. Well-known models for decision making under uncertainty and classification tasks will also be covered. Finally, additional topics include a number of successful real-world applications in different areas.

Topics discussed include:

1. BASICS OF BAYESIAN NETWORKS.

Reasoning with uncertainty. Conditional independence. Correspondence between graph and model: D-separation. Probabilistic directed and undirected graphical models. The Markov property of Bayesian networks.

2. INFERENCE IN BAYESIAN NETWORKS.

Different queries in Bayesian networks: deductive, diagnostic and intercausal reasoning. Exact inference: Brute-force approach, variable elimination and propagation algorithms: message-passing. Searching for explanations: Abduction (MAP). Approximate inference.

3. LEARNING BAYESIAN NETWORKS FROM DATA.

Learning general Bayesian networks: Methods based on testing conditional independence, methods based on score + search, hybrid methods. Methods with incomplete data. Learning Bayesian classifiers: Naive Bayes, Seminaive Bayes, Tree augmented naïve Bayes, K-dependence network, Markov Blanket, Bayesian multinets. Clustering: The EM algorithm, the structural EM algorithm. Model assessment with cross-validation and bootstrap.

4. NETWORKS FOR DECISION MAKING.

Decision trees. Influence diagrams. Value of information. Explanation of results.

5. SUCCESSFUL APPLICATIONS OF BAYESIAN NETWORKS.

Real-world applications in different domains: bioinformatics, medicine, computer vision, astrophysics, natural language processing (voice, text), consumer behaviour, credit assessment, computer network diagnosis, technical support troubleshooters, on-line help systems, etc. Practical exercises with free software to gain confidence on the use of Bayesian networks: Hugin, Bayesia, Weka, GeNIe, Elvira…

Texts and readings:

• Borgelt, C., Kruse, R. (2002) Graphical Models. Methods for Data Analysis and Mining, Wiley.
• Castillo, E., Gutiérrez, J.M., Hadi, A.S. (1997) Expert Systems and Probabilistic Network Models. Springer, New York. Spanish version available in Internet: Sistemas Expertos y Modelos de Redes Probabilísticas, Academia de Ingeniería, Madrid, ISBN: 84-600-9395-6.
• Cowell, R.G., Dawid, A.P., Lauritzen, S.L., Spiegelhalter, D.J. (1999) Probabilistic Networks and Expert Systems, Springer.
• Friedman, N, Geiger, D., Goldszmidt, M. (1997) Bayesian Networks Classifiers, Machine Learning 29, 131-163.
• Gámez, J.A., Puerta, J.M. (eds.) (1998) Sistemas Expertos Probabilísticos, Colección Ciencia y Técnica, Eds. de la Univ. de Castilla-La Mancha.
• Jensen, F.V. (2001) Bayesian Networks and Decision Graphs, Springer.

• Kjaerulff, U.B., Madsen, A.L. (2005) Probabilistic Networks –An Introduction to Bayesian Networks and Influence Diagrams. Available at: http://www.cs.aau.dk/~uk/papers/pgm-book-I-05.pdf
• Korb, K.B., Nicholson, A.E. (2004) Bayesian Artificial Intelligence, Chapman and Hall.
• Neapolitan, R.E. (2004) Learning Bayesian Networks. Prentice Hall.

• Pearl, J. (1988) Probabilistic Reasoning in Intelligent Systems, Morgan Kaufmann.

• Proceedings of the most important related conference: Uncertainty in Artificial Intelligence. http://www.auai.org

Free Software:

• Bayesia: http://ww.bayesia.com
• Elvira: http://leo.ugr.es/~elvira/

• GeNIe: http://www2.sis.pitt.edu/~genie

• Hugin: http://www.hugin.com
• Weka: http://www.cs.waikato.ac.nz/ml/weka/

Organization:

Most of the classes will be devoted to the presentation of background material, and others will be centered around the discussion of a particular research article. All participants are expected to have read (at some reasonable level of detail) the readings before class and contribute to the discussion. Lectures will be given with a slide show with summaries, formulas, pictures, schemes, diagrams.

Practice will be done with the computer. Data will be provided by the instructors, or by the students themselves if they are interested in some specific topic.

Grading Policy:

Homeworks, project (40%), oral student presentation (30%), quiz with background material (30%).

Participation in classroom and attendance will be valued.