SUNMONTUEWEDTHUFRISAT
Events for March 06, 2008
-
CS Colloq: Synthesis of Strategies for Noisy and Non-Noisy Multi-Agent Environments
Thu, Mar 06, 2008 @ 01:00 PM - 02:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Title: Synthesis of Strategies for Noisy and Non-Noisy Multi-Agent EnvironmentsSpeaker: Tsz-Chiu Au (UMD)ABSTRACT:
To create new and better agents in multi-agent environments, we may want to
examine the strategies of several existing agents, in order to combine their
best skills. One problem is that in general, we won¡¦t know what those
strategies are; instead, we¡¦ll only have observations of the agents¡¦
interactions with other agents. In this talk, I describe how to take a set of
interaction traces produced by different pairs of players in a two-player
repeated game, and then find the best way to combine them into a composite
strategy. I also describe how to incorporate the composite strategy into an
existing agent, as an enhancement of the agent¡¦s original strategy. In
cross-validated experiments involving 126 agents (most of which written by
students as class projects) for the Iterated Prisoner¡¦s Dilemma, Iterated
Chicken Game, and Iterated Battle of the Sexes, composite strategies produced
from these agents were able to make improvement to the performance of nearly
all of the agents.The speaker will also talk about a technique, Symbolic Noise Detection (SND),
for detecting noise (i.e., mistakes or miscommunications) among agents in
repeated games. The idea behind SND is that if we can build a model of the
other agent's behavior, we can use this model to detect and correct actions
that have been affected by noise. In the 20th Anniversary Iterated Prisoner's
Dilemma competition, the SND agent placed third in the ¡§noise¡¨ category, and
was the best performer among programs that had no ¡§slave¡¨ programs feeding
points to them. I'll discuss how to combine SND with the strategy synthesis
technique in order to produce agents that perform well in noisy, cooperative
environments.BIO:
Tsz Chiu Au is a graduate student at Dept. at Comp. Sci, Univ. of Maryland.
(expected PhD in 2008). He received his B. Eng. degree from Hong Kong Univ. of
Science and Technology.
His research interests lie in AI planning, multi-agent systems and problem
solving by searching. His research accomplishments include his work on coping
with noise in non zero-sum games, synthesis of strategies from interaction
traces and managing volatile data for planning processes in semantic web
service composition.Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Colloquia
-
CS Colloq: A Theory of Similarity Functions for Learning and Clustering
Thu, Mar 06, 2008 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Title: A Theory of Similarity Functions for Learning and ClusteringSpeaker: Maria-Florina Balcan (CMU)Abstract:
Machine Learning has become a highly successful discipline with applications in many different areas of Computer Science. A critical advance that has spurred this success has been the development of learning methods using a special type of similarity functions known as kernel functions. These methods have proven very useful in practice for dealing with many different kinds of data and they also have a solid theoretical foundation. However, it was not previously known whether the benefits of kernels can be realized by more general similarity functions. In our work, we develop a theory of learning with similarity functions that positively answers this question. Furthermore, our theory provides a new and much simpler explanation for the effectiveness of kernel methods.Technically speaking, the existing theory of kernel functions requires viewing them as implicit (and often difficult to characterize) mappings in high dimensional spaces. Our alternative framework instead views kernels directly as measures of similarity and it also generalizes the standard theory in important ways. Specifically, our notions of good similarity functions can be described in terms of natural direct properties of the data, with no reference to implicit spaces, and no requirement that the similarity function be positive semi-definite (as in the standard theory).We also show how our framework can be applied to Clustering: i.e., multi-way classification from purely unlabeled data. In particular, using this perspective, we develop a new model that directly addresses the fundamental question of what kind of information a clustering algorithm needs in order to produce a highly accurate partition of the data. Our work provides the first framework for analyzing clustering accuracy without any strong probabilistic assumptions.Biography:
Maria-Florina Balcan is a Ph.D. candidate at Carnegie Mellon University under the supervision of Avrim Blum. She received B.S. and M.S. degrees from the Faculty of Mathematics, University of Bucharest, Romania. Her main research interests are Computational and Statistical Machine Learning, Computational Aspects in Economics and Game Theory, and Algorithms. She is a recipient of the IBM PhD Fellowship.Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Colloquia
