NESCAI08: The Third North East Student Colloquium on Artificial Intelligence
2-4 May 2008, Ithaca, NY
We will be offering three tutorials.
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
Part A: Dynamic Programming on Lattices/Graphs
A.1 Motivations and Examples
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.
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.
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.