NESCAI: North East Student Colloquium on Artificial Intelligence

28-29 April 2006, Ithaca, NY


We will be offering three two hour tutorials in parallel on the first day. You may attend whichever tutorial you like (irrespective of what you indicated at registration).

Learning to Predict Trees, Sequences, and other Structured Outputs, Thorsten Joachims (Cornell University)

Mechanism Design for Computer Scientists, Vincent Conitzer (CMU)

Introduction to Inductive Transfer, Learning-to-Learn, Multi-Task Learning and all that stuff, Rich Caruana (Cornell University)

Learning to Predict Trees, Sequences, and other Structured Outputs,
Thorsten Joachims (Cornell University)

Location: Upson B17


Over the last decade, much of the research on discriminative learning has focused on problems like classification and regression, where the prediction is a single univariate variable. But what if we need to predict complex objects like trees, orderings, or alignments? Such problems arise, for example, when a natural language parser needs to predict the correct parse tree for a given sentence, when one needs to optimize a multivariate performance measure like the F1-score, or when predicting the alignment between two proteins.

This tutorial discusses recent advances in discriminative training methods for such structured prediction problems like Conditional Random Fields (CRF), Maximum Margin Markov Networks, and Structural Support Vector Machines. In particular, the tutorial focuses on large-margin approaches to predicting structured outputs, and how the idea of margins can be generalized to complex prediction problems and a large range of loss functions. While the resulting training problems have exponential size, there are tractable algorithms that allow training in polynomial time. The methods will be illustrated with examples from application problems.

Speaker Biography

Thorsten Joachims is an Assistant Professor in the Department of Computer Science at Cornell University. In 2001, he finished his dissertation with the title "The Maximum-Margin Approach to Learning Text Classifiers: Methods, Theory, and Algorithms", advised by Prof. Katharina Morik at the University of Dortmund. From there he also received his Diplom in Computer Science in 1997 with a thesis on WebWatcher, a browsing assistant for the Web. His research interests center on a synthesis of theory and system building in the field of machine learning, with a focus on Support Vector Machines and machine learning with text. He authored the SVM-Light algorithm and software for support vector learning. From 1994 to 1996 he was a visiting scientist at Carnegie Mellon University with Prof. Tom Mitchell.



Mechanism Design for Computer Scientists,
Vincent Conitzer (CMU)

Location: Upson 5126


In settings such as auctions and elections, an outcome must be chosen based on the preferences of multiple parties (agents). Typically, each agent (initially) only knows its own preferences, and will not disclose its true preferences unless it feels that doing so is in its own interest. The challenge is to design the outcome-choosing mechanism in such a way that a good result is obtained nevertheless -- for example, by making it optimal for each agent to reveal its true preferences. Mechanism design has traditionally been studied by game theorists, economists, and political scientists; but new applications such as combinatorial auctions, job scheduling, and webpage ranking have drawn many computer scientists to the field.

The tutorial is designed for computer scientists with no background in game theory or mechanism design. It will cover:

I. The basics of "classical" mechanism design, including basic definitions, the revelation principle, Vickrey-Clarke-Groves mechanisms, and impossibility results.

II. Computational aspects of mechanism design, including whether and how mechanisms' outcomes can be efficiently computed; algorithms for automatically designing the entire mechanism; and limitations of classical results in the face of computationally bounded agents.

Example applications will be provided throughout.

Speaker Biography

Vincent Conitzer is a Ph.D. candidate at Carnegie Mellon University, advised by Tuomas Sandholm. He holds an M.S. in Computer Science from CMU (2003) and a B.A. in Applied Mathematics from Harvard (2001). He has published over 30 distinct technical papers on computational issues in game theory, mechanism design, auctions, elections, and other negotiation settings. He is supported by an IBM Ph.D. Fellowship.


Introduction to Inductive Transfer, Learning-to-Learn, Multi-Task Learning and all that stuff,
Rich Caruana (Cornell University)

Location: Upson 5130


Inductive Transfer (a.k.a. learning-to-learn, life-long learning, multitask learning, representation learning, ...) is the process of transfering what has been learned for one problem to other problems so that they can be learned better (more accurately, or with less data). In this tutorial we'll show how to perform inductive transfer with supervised learning methods such as neural nets, k-nearest neighbor, SVMs, naive bayes, and bayes nets. We'll also briefly review the history of inductive transfer, discuss what kinds of applications will benefit from inductive transfer, and give a few heuristics for getting the most benefit when using transfer on real problems.

Speaker Biography

Rich Caruana is an Assistant Professor of Computer Science at Cornell University. He recieved his Ph.D. from CMU in 1997 where he worked with Tom Mitchell and Herb Simon. Before joining the faculty at Cornell in 2001 he was affiliated with the Medical School at UCLA, CMU's Center for Learning and Discovery (CALD), and Just Research. Most of Rich's research is in machine learning and data mining, and applications of these to problems in medical decision making, bioinformatics, and environmental science. He is best known for his work in inductive transfer, semi-supervised learning, and optimizing learning for different performance criteria. Rich likes to mix algorithm development with applications work to insure that the methods he developes really work in practice.