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
NEW PLACE: CSE 609 (AI Lab)

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:
http://www.cs.ubc.ca/~kevinlb/papers/nbody.pdf

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.

Speaker: Craig Boutilier, University of Toronto