Reading group: Learning to Search

Motivation

We want to study the various algorithms that combine both search and learning. This paradigm has a long history and has applications in lot of fields like Structured Prediction - inference(given a scoring function, the problem of finding highest scoring output y for a given input x) is intractable due to the large space of possible output labels. More recently, search-based structured prediction(Hal Daume, Daniel Marcu and John Langford) algorithms like LaSo and Searn tried to address this problem by combining search and learning. Planning - learning ranking functions for beam search(Yehua Xu and Alan Fern) and learning control knowledge for forward search planning(Sungwook Yoon and Alan Fern). Scheduling - Applying RL for Job shop scheduling(Wei-Zhang and Tom Dietterich).

Meeting time

Schedule

• (4/23) Hal Daume III, Daniel Marcu: Learning as search optimization: approximate large margin methods for structured prediction. ICML 2005 (PDF)
• (4/30) Yehua Xu, Alan Fern and Sungwook Yoon: Discriminative Learning of Beam-Search Heuristics for Planning. IJCAI 2007 (PDF)
• (4/30) Yehua Xu, Alan Fern: On Learning Linear Ranking Functions for Beam Search. ICML 2007 (PDF)
• (5/7) Sungwook Yoon, Alan Fern and Robert Givan: Learning Control Knowledge for Forward Search Planning. JMLR 2008 (PDF)
• (5/14) Hal Daume III, John Langford: Search-based Structured Prediction. Machine Learning Journal 2009 (PDF)
• (6/4) No meeting, NIPS deadline is on June 5.
• (7/6) Patrick Gallinari et al.: RL for Structured Prediction. unpublished Manuscript 2009 (PDF)
• (7/6) Wang, Q., Lin, D. and Schuurmans, D. : Simple training of dependency parsers via structured boosting. IJCAI 2007 (PDF)
• (7/13) No meeting, IJCAI conference from July 11-17.
• (7/20) Nathan Ratliff, Drew Bagnell : Learning to Search: Functional Gradient techniques for imitation learning.  (PDF)
• (9/14) SampleRank algorithm - Chapter 5 of Aron Culotta's Ph.D Thesis: Learning and inference in weighted logic with application to natural language processing. (PDF)
• (9/21) G. Neu and Cs. Szepesvári: Training Parsers by Inverse Reinforcement Learning.  Machine Learning Journal (accepted) (PDF)
• (10/7) continue reading the MLJ paper
• (?) Dan Roth, Kevin Small, Ivan Titov: Sequential Learning of Classifiers for Structured Prediction Problems. AISTATS 2009 (PDF)
• (?) P.K.Shivaswamy, Tony Jabera: Structured Prediction with Relative Margin. ICMLA 2009 (PDF)
• (?) Thomas Finley, Thorsten Joachims: Training Structural SVMs when Exact Inference is Intractable. ICML 2008 (PDF)
• (?) Alex Kulesza, Fernando Periera: Structured Learning with Approximate Inference. NIPS 2007 (PDF)
• (?) More recent work from Andrew McCallum's group on Proof of convergence of SampleRank method. Papers will be emailed to the seminar participants.
• (?) Choon Hui Teo, S. V. N. Vishwanathan, Alex J. Smola, and Quoc V. Le. Bundle Methods for Regularized Risk Minimization. under submission to JMLR 2009. (PDF)
• (?) Ankan Saha, Xinhua Zhang, S. V. N. Vishwanathan: Lower Bounds for BMRM and Faster Rates for Training SVMs CoRR abs/0909.1334: 2009 (PDF)
• (?) Jascha Sohl-Dickstein, Peter Battaglino, Michael R. DeWeese: Minimum Probability Flow Learning. submitted to arXiv on June 25 (PDF) 
• (?) Dan Roth, Kevin Small: Margin based Active Learning for Structured Output Spaces. ECML 2006 (PDF)
• rest will be decided based on the interests of the seminar participants

Please email me if you want to add something to this list.