Machine Learning Reading Group (MLRG): Integrating
Learning
and Search for Solving Complex Tasks
We want to study the various algorithms that combine the two
fundamental sub-areas of AI namely, search
and learning for solving complex tasks including structured prediction,
planning, combinatorial optimization.
Meeting time
Every wednesday 4-5 PM in KEC 2057.
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
- (10/14) Dan Roth, Kevin Small, Ivan Titov: Sequential
Learning
of Classifiers for Structured Prediction Problems. AISTATS 2009 (PDF)
- (10/21) Thomas Finley, Thorsten Joachims: Training
Structural
SVMs when Exact Inference is Intractable. ICML 2008 (PDF)
- (10/28) 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.
- (?)
Jascha Sohl-Dickstein, Peter Battaglino, Michael R. DeWeese: Minimum
Probability Flow Learning. submitted to arXiv on June 25 (PDF)
- Wei Zhang, Thomas G. Dietterich: A Reinforcement Learning Approach to job-shop Scheduling. IJCAI 1995 (PDF)
- Justin Boyan and Andrew Moore: Learning Evaluation Functions to Improve Optimization by Local Search. JMLR 2000 (PDF)
This
reading group ended long ago, but there is a lot of recent work in this
area including some of my own work. I'm listing them below so that others can benefit. (Please email me if I missed something
relevant):
- David Weiss, Ben Sapp and Ben Taskar: Structured Prediction Cascades. JMLR paper (PDF)
- Michael
Wick, Khashayar Rohanimanesh, Kedare Bellare, Aron Culotta, Andrew
McCallum: SampleRank: Training Factor Graphs with Atomic Gradients.
ICML 2011 (PDF)
- M. Chang and L. Ratinov and D. Roth: Structured Learning with Constrained Conditional Models. Machine Learning Journal 2012 (PDF)
- Rajhans Samdani and Dan Roth: Efficient Decomposed Learning for Structured Prediction. ICML 2012 (PDF) -- David Sontag's Pseudo-Max approach is a special case of their framework.
- Alexander Rush and Michael Collins: A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing. JAIR (PDF)
- Janardhan Rao Doppa, Alan Fern and Prasad Tadepalli: Output Space Search for Structured Prediction. ICML 2012 (PDF)
- Janardhan
Rao Doppa, Alan Fern and Prasad Tadepalli: HC-Search: Learning
Heuristics and Cost Functions for Structured Prediction. AAAI 2013 (PDF)
- Jiarong Jiang, Adam Teichert, Hal Daumé III, Jason Eisner: Learned Prioritization for Trading Off Accuracy and Speed. NIPS 2012 (PDF)
- Belanger, D., A. Passos, S. Riedel, A. McCallum: MAP Inference in Chains using Column Generation. NIPS 2012 (PDF)
- He He, Hal Daume III, Jason Eisner: Imitation Learning by Coaching. NIPS 2012 (PDF)
- He He, Hal Daume III, Jason Eisner: Dynamic Feature Selection for Dependency Parsing. EMNLP 2013 (PDF)
- David Weiss and Ben Taskar: Learning Adaptive Value of Information for Structured Prediction. NIPS 2013 (PDF)
- Papers on Easy-First framework: Dependency Parsing, Co-reference Resolution, Dynamic Oracles for Training Deterministic Parsers (similar to SEARN algorithm, but a very well-written paper).
- Liang Huang, Suphan Fayong, and Yang Guo: Structured Perceptron with Inexact Search. NAACL 2012 (PDF)
- Heng
Yu, Liang Huang, Haitao Mi, and Kai Zhao: Max-Violation
Perceptron and Forced Decoding for Scalable MT Training. EMNLP 2013 (PDF)
- Veselin Stoyanov, Alexander Ropson, and Jason Eisner: Empirical risk minimization of graphical model parameters given
approximate inference, decoding, and model structure. AISTATS 2011 (PDF)
- Veselin Stoyanov and Jason Eisner: Minimum-risk training of approximate CRF-based NLP systems. NAACL 2012 (PDF)