ICML 2009 Tutorial Schedule, Sunday June 14
Note for participants: ICML will not provide hard copies of the tutorial syllabi (slides) to conference participants. The slides are available in PDF format from the individual tutorial websites and can be easily downloaded and printed prior to the conference.
9:00AM - 11:30AM | T1: Reductions in Machine Learning | Leacock 26 |
Alina Beygelzimer, John Langford, and Bianca Zadrozny | [webpage] | |
T2: Convergence of Natural Dynamics to Equilibria | Leacock 219 | |
Eyal Even-Dar and Vahab Mirrokni | [webpage] | |
T3: Learning with Dependencies between Several Response Variables | Leacock 232 | |
Volker Tresp and Kai Yu | [webpage] | |
11:30AM - 1:00PM | Lunch break (on your own) | |
1:00PM - 3:30PM | T4: Survey of Boosting from an Optimization Perspective | Leacock 219 |
Manfred K. Warmuth and S.V.N. Vishwanathan | [webpage] | |
T5: The Neuroscience of Reinforcement Learning | Leacock 232 | |
Yael Niv | [webpage] | |
T6: Machine Learning in IR: Recent Successes and New Opportunities | Leacock 26 | |
Paul Bennett, Misha Bilenko, and Kevyn Collins-Thompson | [webpage] | |
3:30PM - 4:00PM | Coffee break | Leacock Lobby |
4:00PM-6:30PM | T7: Active Learning | Leacock 219 |
Sanjoy Dasgupta and John Langford | [webpage] | |
T8: Large Social and Information Networks: Opportunities for ML | Leacock 219 | |
Jure Leskovec | [webpage] | |
T9: Structured Prediction for Natural Language Processing | Leacock 219 | |
Noah Smith | [webpage] |
Abstracts
T1 Reductions in Machine Learning [tutorial webpage]
Alina Beygelzimer, John Langford, and Bianca Zadrozny
Machine learning reductions are about reusing solutions to simple,
core problems in order to solve more complex problems. A basic
difficulty in applying machine learning in practice is that we often
need to solve problems that don't quite match the problems solved by
standard machine learning algorithms. Reductions are techniques that
transform such practical problems into core machine learning problems.
These can then be solved using any existing learning algorithm whose
solution can, in turn, be used to solve the original problem. The
material that we plan to cover is both algorithmic and analytic: We
will discuss existing and new algorithms along with the methodology
for analyzing and creating new reductions. In our experience, this
approach is an effective tool for designing empirically successful,
automated solutions to learning problems.
T2 Convergence of Natural Dynamics to Equilibria [tutorial webpage]
Eyal Even-Dar and Vahab Mirrokni
Recently, a lot of effort has been devoted to analyzing response
dynamics in various games. Questions
about the dynamics themselves and their convergence properties
attracted a great deal of attention. This
includes, for example, questions like "How long do uncoordinated
agents need to reach an equilibrium?"
and "Do uncoordinated agents quickly reach a state with low social
cost?". An important aspect in
studying such dynamics is the learning model employed by
self-interested agents in these models. Studying
the effect of learning algorithms on the convergence rate of players is
crucial for developing a solid
understanding of the corresponding games.
In this tutorial, we first describe an overview of the required
terminology from game theory. Then, we
survey results about the convergence of myopic and learning-based best
responses of players to equilibria
and approximately optimal solutions, and study the effect of various
learning algorithms in convergence
(rate). Throughout the tutorial, we describe fundamental connections
between local search algorithms
and learning algorithms with the convergence of best-response dynamics
in multi-agent games.
T3 Learning with Dependencies between Several Response Variables [tutorial webpage]
Volker Tresp and Kai Yu
We analyze situations where modeling several response variables for a given input improves the prediction accuracy for each individual response variable. Interestingly, this setting has appeared in different context and a number of different but related approaches have been proposed. In all these approaches some assumptions about the dependency structure between the response variables is made. Here is a small selection of labels describing relevant work:
multitask learning, multi-class classification, multi-label prediction, hierarchical Bayes, inductive transfer learning, hierarchical linear models, mixed effect models, partial least squares, canonical correlation analysis, maximal covariance regression, multivariate regression, structured prediction, relational learning,...The large number of approaches is confusing for the novice, and often even for the expert. In this tutorial we systematically introduce some of the major approaches and describe them from a common viewpoint.
T4 Survey of Boosting from
an Optimization Perspective [tutorial webpage]
Manfred K. Warmuth and S.V.N. Vishwanathan
Boosting has become a well known ensemble method.
The algorithm maintains a distribution on the binary labeled examples
and a new base learner is added in a greedy fashion.
The goal is to obtain a small linear combination
of base learners that clearly separates the examples.
We focus on a recent view of Boosting where
the update algorithm for distribution on the examples
is characterized by a minimization problem that uses a relative entropy
as a regularization.
The most well known boosting algorithms is AdaBoost.
This algorithm approximately
maximizes the hard margin, when the data is separable.
We focus on recent algorithms
that provably maximize the soft margin
when the data is noisy.
We will teach the new algorithms,
give a unified and versatile view of Boosting in terms
of relative entropy regularization, and show how
to solve large scale problems based on state of the art
optimization techniques.
T5 The Neuroscience of Reinforcement Learning [tutorial webpage]
Yael Niv
One of the most influential contributions of machine learning to
understanding the human brain is the (fairly recent) formulation of learning in real
world tasks in terms of the computational framework of reinforcement learning.
This confluence of ideas is not limited to abstract ideas about how trial and error
learning should proceed, but rather, current views regarding the computational
roles of extremely important brain substances (such as dopamine) and brain areas
(such as the basal ganglia) draw heavily from reinforcement learning. The results of
this growing line of research stand to contribute not only to neuroscience and
psychology, but also to machine learning: human and animal brains are remarkably
adept at learning new tasks in an uncertain, dynamic and extremely complex world.
Understanding how the brain implements reinforcement learning efficiently may
suggest similar solutions to engineering and artificial intelligent problems. This
tutorial will present the current state of the study of neural reinforcement learning,
with an emphasis on both what it teaches us about the brain, and what it teaches us
about reinforcement learning.
T6 Machine Learning in IR: Recent Successes and New Opportunities [tutorial webpage]
Paul Bennett, Misha Bilenko, and Kevyn Collins-Thompson
This tutorial will focus on the interplay between information retrieval (IR) and machine learning. The intersection of these research areas has seen tremendous growth and progress in recent years, much of it fueled by incorporating machine learning techniques into the core of information retrieval technologies, including Web search engines, e-mail and news filtering systems, music and movie recommendations, online advertising systems, and many others. As the complexity, scale, and user expectations for retrieval technology increase, it is becoming increasingly important for each field to keep pace with and inform the other.
With that goal in mind, this tutorial covers: the nature of the challenging learning problems faced at many levels by search technology systems today; successful applications of machine learning methods to key IR tasks; and opportunities for joint future progress and emerging research problems which will benefit both machine learning and information retrieval.
T7 Active Learning [tutorial webpage]
Sanjoy Dasgupta and John Langford
Active learning is defined by contrast to the passive model of
supervised learning where all the labels for learning are obtained
without reference to the learning algorithm, while in active learning
the learner interactively chooses which data points to label. The hope
of active learning is that interaction can substantially reduce the
number of labels required, making solving problems via machine learning
more practical. This hope is known to be valid in certain special cases,
both empirically and theoretically. Variants of active learning has
been investigated over several decades and fields. The focus of this
tutorial is on general techniques which are applicable to many problems.
At a mathematical level, this corresponds to approaches with provable
guarantees under weakest-possible assumptions since real problems are
more likely to fit algorithms which work under weak assumptions. We
believe this tutorial should be of broad interest. People working on or
using supervised learning are often confronted with the need for more
labels, where active learning can help. Similarly, in reinforcement
learning, generalizing while interacting in more complex ways is an
active research topic.
T8 Large Social and Information Networks: Opportunities for ML [tutorial webpage]
Jure Leskovec
Emergence of the web, social media and online social networking websites gave rise to detailed traces of human social activity. This offers many opportunities to analyze and model behaviors of millions of people. For example, we can now study ''planetary scale'' dynamics of a full Microsoft Instant Messenger network of 240 million people, with more than 255 billion exchanged messages per month.
Many types of data, especially web and "social" data, come in a form of a network or a graph. This tutorial will cover several aspects of such network data: macroscopic properties of network datasets; statistical models for modeling large scale network structure of static and dynamic networks; properties and models of network structure and evolution at the level of groups of nodes and algorithms for extracting such structures. I will also present several applications and case studies of blogs, instant messaging, Wikipedia and web search.
Machine learning as a topic will be present throughout the tutorial. The idea of the tutorial is to introduce the machine learning community to recent developments in the area of social and information networks that underpin the Web and other on-line media.
T9 Structured Prediction for Natural Language Processing [tutorial webpage]
Noah Smith
This tutorial will discuss the use of structured prediction methods from machine learning in natural language processing. The field of NLP has, in the past two decades, come to simultaneously rely on and challenge the field of machine learning. Statistical methods now dominate NLP, and have moved the field forward substantially, opening up new possibilities for the exploitation of data in developing NLP components and applications. However, formulations of NLP problems are often simplified for computational or practical convenience, at the expense of system performance. This tutorial aims to introduce several structured prediction problems from NLP, current solutions, and challenges that lie ahead. Applications in NLP are a mainstay at ICML conferences; many ML researchers view NLP as a primary or secondary application area of interest. This tutorial will help the broader ML community understand this important application area, how progress is measured, and the trade-offs that make it a challenge.