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.