Graphical Model Research in Audio, Speech, and Language Processing (pdf)

Jeff A. Bilmes, University of Washington

Graphical models (GMs) are a general statistical abstraction that can describe and help solve tasks in a variety of domains. Recently, much attention has been devoted to their application to audio, speech, and language. These time series have structure that creates unique and interesting research problems, most of which are still open. GMs offer a general and mathematically principled way to move beyond the ubiquitously used hidden Markov model for such signals.

In this tutorial, we will survey the various ways in which GMs are being used to represent and solve problems associated with these signals. After briefly reviewing relevant GM concepts and notation, we will discuss several representational frameworks at different levels, including: 1) representing and learning GMs over vector observation sequences, serialized and switched by hidden chains; 2) representing mid-level hidden aspects of speech, such as articulatory and pronunciation networks, where the goal is to provide anatomically inspired sequences of vocal-tract configurations; and 3) language representations, including those where words are factored into feature bundles, switching mixture-based language models, and graphs that themselves represent smoothing.

In each case, it will be emphasized how only the graph and its associated inferential machinery can portray quite dissimilar sets of models and operations. It will also be emphasized how "deterministic dependencies" and the concept of a "switching" network (or a multi-net), greatly simplifies the specification of these representations. It will further be stressed that the structure learning problem should be tailored to the particular task --- i.e., a discriminative task should effect a discriminatively structured network. Building real-world systems, however, necessitates a software system whose description language is that of dynamic graphs. Therefore, this tutorial will also present and use for descriptive purposes the Graphical Models Toolkit (GMTK), a publicly available toolkit for developing GM-based audio, speech, and language systems. The tutorial will cover many of GMTK's novel features, particularly those that facilitate the use of the GM framework for these signal types. Moreover, many of these features are likely to be applicable to most time series and dynamic problems.

Lastly, the tutorial will include an overview of current challenges, including that of exact inference complexity. It will therefore describe recent work on the triangulation of dynamic models, and how such problems differ from standard (non-dynamic) triangulation.

Probabilistic Models for Relational Domains

Daphne Koller, Stanford University

Probabilistic graphical models are typically based on an attribute-based representation, where the state of the world is specified simply as an assignment to some set of attributes. However, many domains are more naturally modeled using a relational representation, in which instances of multiple types are related to each other in complex ways. In this tutorial, I will describe the framework of probabilistic relational models (PRMs), a probabilistic modeling language suitable for relational domains. PRMs extend the language of probabilistic graphical models with the expressive power of object-relational languages. They model the uncertainty over the attributes of objects in the domain as well as uncertainty over the existence of relations between objects. The tutorial will cover the language and the semantics of both directed and undirected PRMs, and the special-case framework of object-oriented Bayesian networks. I will briefly discuss implications of various language features on the complexity of the inference task, and survey some appropriate inference methods. I will describe methods for automatically learning PRMs directly from a relational data set, and describe applications of these techniques to various tasks, such as collective classification and clustering in a relational setting. The methods will be motivated and illustrated through a variety of real-world applications, including the analysis of web data and biomedical data.

Bayesian Networks for Forensic Identification Problems (pdf)

Steffen L. Lauritzen, Aalborg University

Bayesian networks have recently (Dawid et al. 2002) proved valuable for formulating and solving forensic identification problems using DNA evidence. Such problems could be associates with simple paternity cases, identification of bodies, the establishing of specific family relationships, or proving the presence of individuals in criminal cases, where mixed stains of blood or other substances are found on the scene of the crime. The Bayesian networks reflect the genetic relationships among involved individuals but express also logical constraints between items of evidence and uncertainties in measurement processes. Classical calculations can be illuminated through a BN representation and more complex calculations can easily be performed using probability propagation and exploiting the natural modularity of Bayesian networks. The tutorial will give an introduction to the genetic theory behind DNA identification as well as introduce the different types of network associated with the various identification problems, illustrated with case examples. Difficult and unsolved problems, for example related to structural learning, will be described and briefly discussed.

Uncertainty and Computational Markets

Michael P. Wellman, University of Michigan

Trading in computational markets presents agents with interesting problems of reasoning under uncertainty. For example, bidding in an auction may require reasoning about the actions of other agents, and dealing in one market may depend on expected outcomes in others. More generally, iterative market mechanisms introduce dynamics, essentially posing a stochastic game. Markets also present opportunities for allocating risk and disseminating uncertain information, particularly through financial securities. This tutorial presents some general economic background, with several examples of results and research issues concerning both uncertainty in markets and markets in uncertainty.