tutorial

University of Toronto Technical Report PSI-2003-22, April, 2003.To appear in IEEE Transactions on Pattern Analysis and Machine Intelligence.A Comparison of Algorithms for Inference and Learningin Probabilistic Graphical ModelsBrendan J. Frey and Nebojsa JojicAbstractResearch into methods for reasoning under uncertainty is currently one of the most excit-ing areas of artificial intelligence, largely because it has recently become possible to record,store and process large amounts of data. While impressive achievements have been madein pattern classification problems such as handwritten character recognition, face detection,speaker identification and prediction of gene function, it is even more exciting that researchersare on the verge of introducing systems that can perform large-scale combinatorial analyzesof data, decomposing the data into interacting components. For example, computationalmethods for automatic scene analysis are now emerging in the computer vision community.These methods decompose an input image into its constituent objects, lighting conditions,motion patterns, and so on. Two of the main challenges are finding effective representationsand models in specific applications, and finding efficient algorithms for inference and learningin these models. In this paper, we advocate the use of graph-based probability models andtheir associated inference and learning algorithms. We review exact techniques and variousapproximate, computationally efficient ...