NESCAI08: The Third North East Student Colloquium on Artificial Intelligence

2-4 May 2008, Ithaca, NY


We will be offering three tutorials.

Advanced Dynamic Programming in NLP/AI:
Theory, Algorithms, and Applications

Liang Huang (University of Pennsylvania)


Dynamic Programming (DP) is an important class of algorithms widely used in many areas of speech and language processing. It provides efficient solutions to seemingly intractable inference over exponentially-large spaces by sharing overlapping subproblems. Notable instances of DP include the well-known Viterbi and Forward-Backward Algorithms for finite-state models, and the CKY Algorithm for context-free parsing. The Dijkstra and A* Algorithms, although less obvious, can also be viewed as DP instances. In fact, almost all inference algorithms in the NLP literature involve some sort of DP.

With this overwhelming popularity, a unified view of various DP algorithms would not only provide a better understanding for NLP/AI researchers but also help them design new DP algorithms in practice. This tutorial, therefore, surveys two such theoretical frameworks: the semiring framework in the context of finite-state methods, and the hypergraph framework in the context of parsing and machine translation. Under each of these two paradigms, we review two most important types of DP algorithms, namely the Viterbi-style topological algorithms and the Dijkstra-style best-first algorithms. Wherever relevant, we will discuss typical instances of these algorithms in practice, which include applications in tagging and chunking, word alignment, phrase-based translation, syntactic parsing, and syntax-based translation. We will also discuss applications of DP in general AI, for instance, the famous constraint-satisfaction problem.


Part A: Dynamic Programming on Lattices/Graphs

A.1 Motivations and Examples
A.2 Semirings
A.3 Viterbi Algorithm
A.4 Dijkstra and A* Algorithms
A.5 Comparison between Viterbi and Dijkstra/A* Algorithms

--- [ short break ] ---

Part B: Dynamic in Programming on Hypergraphs and AND-OR Graphs

B.1 Hypergraphs, AND-OR Graphs, and Related Formalisms
B.2 Examples in Parsing and Machine Translation
B.3 Generalized Viterbi Algorithm; CKY Parsing
B.4 Knuth and A* Algorithms
B.5 Applications: Constraint Satisfaction Problem


Liang Huang is a final-year PhD student at the University of Pennsylvania, co-supervised by Aravind Joshi and Kevin Knight (USC/ISI). He is mainly interested in the intersection of computational linguistics and theoretical computer science, and in particular, efficient algorithms for parsing and machine translation, generic dynamic programming, and formal properties of synchronous grammars. His thesis work develops a set of "forest-based methods" that have been applied to many problems in NLP including k-best parsing, forest rescoring and reranking, and forest-based translation. He has given invited talks at many places including Stanford University, UC Berkeley, MIT, Google Research and Microsoft Research. In 2005 he received the University Prize for Excellence in Teaching at Penn, and had designed and lectured one of the first Python Programming courses for CS undergraduates in the US.

Graph Mining Techniques for Social Network Analysis

Mary McGlohon (Carnegie Mellon University)


How do structures in social networks form and appear? How does information propagate through these networks? What tools can we use to analyze network structures? This tutorial will give a concise overview of the important conceptual and software tools for characterizing, modeling, and analyzing graph structures common in networks such as weblogs and social media, with pointers to active research areas, latest publications, and available software. We review fundamental tools and surprising patterns that recur in social networks, including applications toward ranking influence of blogs, identifying communities and expertise, and detecting anomalies.

We first focus on patterns, as we review the 'six-degrees of separation', the ideas behind power-law graphs, and more recent patterns on time-evolving graphs, like the 'densification' power law. Next, we turn our attention to tools, as we cover singular- and eigen-value decomposition, which are the engines behinds HITS and PageRank; a brief overview of tensors for time-evolving graphs; co-clustering for community detection; and results on virus-propagation and epidemic thresholds. The emphasis is on the intuition behind all these tools and their practical impact for the analysis of large, real datasets from social media. Finally, we report on recent discoveries on the timing and shape of blog cascades and influence propagation, as well as other active research areas in online social networks.

Mary McGlohon is a Ph.D. student in the Machine Learning Department at Carnegie Mellon University. She has received a National Science Foundation Graduate Research Fellowship and a Yahoo! Key Technical Challenges Grant. Prior to beginning her graduate work, she received B.S. degrees in Computer Science and Mathematics from the University of Tulsa in Tulsa, Oklahoma. Her research focuses on graph mining, particularly with respect to properties of evolving graphs, information diffusion in networks, and link analysis.

Learning to Rank

Yisong Yue and Filip Radlinski (Cornell University)


Learning to rank is increasingly popular due to its many real world applications, from web search and advertisement selection to predicting the outcome of sports tournaments. This area has also recently seen a number of exciting advances that extend core ideas within machine learning while also having high practical impact. In particular, learning to rank deals with issues such as how to best collect useful training data, interactive and semi-interactive learning methods (e.g., online learning), optimizing for a wide range of exotic objective functions (such as those defined over rankings instead of individual elements), as well as structured output prediction.

In this tutorial, we will present some of the many formulations of the learning to rank problem, and modern approaches used to address them with a particular focus on learning to rank for web search. The tutorial will also detail some of the challenges in optimizing appropriate performance metrics and obtaining training data. Throughout, we will touch on a number of current open problems in this area.


Yisong Yue is a PhD candidate at Cornell University. He is a recipient of a Microsoft Research Graduate Fellowship and a Yahoo! Key Technical Challenge Grant. His research interests include machine learning and information retrieval.

Filip Radlinski is a PhD candidate at Cornell University. He is a recipient of a Microsoft Research Graduate Fellowship, a Fulbright Fellowship and the KDD 2005 Best Student Paper award. His research interests include machine learning, information retrieval and online learning.