590 A - Research Seminar in Artificial Intelligence

Spring Quarter 2006

Faculty organizer: Henry Kautz <kautz@cs.washington.edu>

NEW DAY / TIME: Wednesdays 3:30-4:20


Mailing List

We will not use the cse590a mailing list. Instead, announcements about the seminar will go to uw-ai. If you do not already subscribe to uw-ai, then join by sending mail to uw-ai-request@cs.washington.edu, with the line "subscribe listname" in the body of the message.


  Speaker or Paper Primary Host or Discussion Leader (name & email) Secondary Host or Discussion Leader (name & email)
April 5 Speaker: Ronen Brafman, Ben-Gurion University    
April 12 Compiling Relational Bayesian Networks for Exact Inference. Mark Chavira, Adnan Darwiche, and Manfred Jaeger. To appear in special issue of International Journal of Approximate Reasoning, 2006. Bill Pentney <bill@cs.washington.edu> Cafarella, Michael
April 19

Speaker: Kevin Leyton-Brown, UBC

Action-Graph Games and n-Body Games: Compact Representations for Game Theory

This talk will describe two game theoretic representations for compactly
specifying and reasoning about single-shot, finite-action games.  Although
the work is primarily theoretical, it is motivated by environments in which
a large number of agents contend for scarce resources.

First, action-graph games (AGGs) are a fully expressive game representation which can compactly express both strict and context-specific independence between players' utility functions. We provide a polynomial-time algorithm for computing a player’s expected utility under a given mixed-strategy profile. (More precisely, this algorithm is polytime when the game’s action graph’s in-degree is bounded by a constant.) We show that this technique can be used to provide exponential speedup in the computation of Nash equilibria, best response, and correlated equilibria, as compared to standard techniques. We also describe function nodes, a new representational idea which makes AGGs compact for a broader class of games.

Second, n-body games compactly represent interactions in which players
choose actions from a metric space (e.g., points in space) and payoffs are
computed as a function of distances between players' action choices. We show that the n-body game representation allows a wide variety of game-theoretic quantities to be efficiently computed both exactly and approximately.

This talk is based on joint work with Albert Xin Jiang and Navin A.R. Bhat. It draws on material presented in the following papers:

Action-Graph Games:
http://www.cs.ubc.ca/~kevinlb/papers/AGG.pdf (main paper for this talk)
http://www.cs.ubc.ca/~kevinlb/papers/continuation.pdf (older work)

N-body Games:

Stephen Friedman <sfriedman@cs.washington.edu>  
April 26 Speaker: Ashish Kapoor

Learning Discriminative Models with Incomplete Data

Many practical problems in pattern recognition require making inferences
using multiple modalities, e.g. sensor data from video, audio,
physiological changes etc. Often in real-world scenarios there can be
incompleteness in the training data. There can be missing channels due
to sensor failures in multi-sensory data and many data points in the
training set might be unlabeled. Further, instead of having exact labels
we might have easy to obtain auxiliary labels that correlate with the
task. Also, there can be labeling errors, for example human annotation
can lead to incorrect labels in the training data.

The discriminative paradigm of classification aims to model the
classification boundary directly by conditioning on the data points;
however, discriminative models cannot easily handle incompleteness since
the distribution of the observations is never explicitly modeled. We
present a unified Bayesian framework that extends the discriminative
paradigm to handle four different kinds of incompleteness. The proposed
extensions are built on top of Gaussian process classification and
result in a modular framework where each component is capable of
handling different kinds of incompleteness. These modules can be
combined in many different ways, resulting in many different algorithms
within one unified framework. We demonstrate the effectiveness of the
framework on a variety of problems such as multi-sensor affect
recognition, image classification and object detection and segmentation.

Bio: Ashish Kapoor recieved a PhD from the MIT Media Laboratory. His
research focuses on Bayesian methods in machine learning, computer
vision and their applications to Affective Computing, Social Networks
and HCI.

Tian Sang <sang@cs.washington.edu> Fei Wu
May 3 Speaker: Bart Selman, Cornell University Danny Wyatt <danny@cs.washignton.edu> Jonah Cohen
May 10

Speaker: Craig Boutilier, University of Toronto

Leith Caldwell <leith@cs.washington.edu> Rapael Hoffmann
May 17 Speaker: Michael Littman, Rutgers University Alex Yates Parag
May 24 Speaker: David McAllester, TTI, University of Chicago Hoifung Poon Sang Yun
May 31 Speaker: David Parkes, Harvard University   Krzysztof Gajos

Duties of visitor hosts (share these jobs between the two of you however you like; the buck stops with the primary host!):

Duties of discussion leaders: