CS 159: Advanced Topics in Machine Learning: Structured Prediction

Course Description

This course will cover a mixture of the following topics:

• Graphical Models
• Inference Methods
  • Message Passing, Integer Programs, Dynamic Programming, Variational Methods
• Classical Discriminative Learning
  • Structured SVM, Structured Perceptron, Conditional Random Fields
• Non-Linear Approaches
  • Structured Random Forests, Deep Structured Prediction
• More Complex Structures
  • Hierarchical Classification, Sequence Prediction/Generation
• Applications to Computer Vision, Speech Recognition, Natural Language Processing, etc

Course Details

• Lectures on Tu/Th at 1pm-2:30pm in Annenberg 105
• This is a paper reading course, where we read and discuss research papers in class
• Student participation is required, including presenting papers in class (20% of total grade)
• Mini-quiz on papers for every lecture, given after lecture/discussion (10% of total grade)
• Final project that explores some topic covered in class (70% of final grade)
• Piazza Forum: link

Instructors

Taehwan Kim           taehwan@caltech.edu
Yisong Yue               yyue@caltech.edu

Teaching Assistants

Hoang Le                 hmle@caltech.edu
Jialin Song               jssong@caltech.edu
Stephan Zheng        stzheng@caltech.edu

Office Hours

Datasets and Codes

Could be useful for final project.

• Make3D: Convert your still image into 3D model
• The Graphical Models Toolkit
• Keras: Deep Learning library for Theano and TensorFlow
• SCARF: A Segmental CRF Speech-Recognition Tool Kit
• HTK Speech Recognition Toolkit
• KITTI Vision Benchmark Suite (for Autonomous Driving)
• The Extreme Classification Repository: Multi-label Datasets & Code

Presentation Schedule

Note: schedule is subject to change.

Topic and Reading List

Presentation Signup Sheet

• Inference Methods
  • Graph Cuts
  • Boykov et al, Fast Approximate Energy Minimization via Graph Cuts, TPAMI 2001.
  • Boykov et al, Markov Random Fields with Efficient Approximations, CVPR 1998
  • Linear Programing
  • Chapter 8.2 and 8.4 in Graphical Models, Exponential Families, and Variational Inference by Wainwright and Jordan
  • Globerson and Jaakkola, Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations, NIPS 2008
  • Variational Inference
  • Chapter 5 in Graphical Models, Exponential Families, and Variational Inference by Wainwright and Jordan
  • Variational Inference: A Review for Statisticians by Blei
  • Sampling Methods
  • Andrieu et al, An Introduction to MCMC for Machine Learning, Machine Learning 2003
  • Khan et al, An MCMC-based Particle Filter for Tracking Multiple Interacting Targets, ECCV 2004
• Graphical Models
• Hidden Markov Models (HMM)
• Sha and Saul, Large margin hidden Markov models for automatic speech recognition, NIPS 2007
• Altun et al, Hidden Markov Support Vector Machines, ICML 2003
• Dahl et al, Context-Dependent Pre-Trained Deep Neural Networks for Large-Vocabulary Speech Recognition, TASLP 2012
• Conditional Random Fields (CRF)
• Lafferty et al, Conditional random fields: Probabilistic models for segmenting and labeling sequence data, ICML 2001
• Quattoni et al, Conditional Random Fields for Object Recognition, NIPS 2004
• Zheng et al, Conditional Random Fields as Recurrent Neural Networks, ICCV 2015
• Sutton and McCallumAn, Introduction to Conditional Random Fields
• Topic Model
• Blei et al, Latent Dirichlet Allocation, JMLR 2003
• Topic models by Blei and Lafferty
• Structured Support Vector Machines (SVM)
• Tsochantaridis et al, Large Margin Methods for Structured and Interdependent Output Variables, JMLR 2005
• Yu and Joachims Learning structural SVMs with latent variables, ICML 2009
• Yue and Joachims Predicting Diverse Subsets Using Structural SVMs, ICML 2008
• Hierarchical / Extreme Classification
• Cai and Hofmann, Hierarchical document categorization with support vector machines, CIKM 2004
• Yen et al, A Primal and Dual Sparse Approach to Extreme Classification, ICML 2016
• Structured Perceptron
• Collins, Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms, ACL 2002
• McDonald et al, Distributed Training Strategies for the Structured Perceptron, NAACL 2010
• Structured Random Forests
• Dollar and Zitnick, Structured Forests for Fast Edge Detection, ICCV 2013
• Kontschieder et al, Structured Class-Labels in Random Forests for Semantic Image Labelling, ICCV 2011
• Deep Structured Models
• Graphical Model + Deep Learning
• Chen et al, Learning Deep Structured Models, ICML 2015
• Schwing and Urtasun, Fully Connected Deep Structured Networks, arxiv 2015
• Johnson et al, Composing graphical models with neural networks for structured representations and fast inference, NIPS 2016
• Chen et al, Semantic Image Segmentation with Deep Convolutional Nets and Fully Connected CRFs, ICLR 2015
• Kim et al, Structured Attention Networks, arxiv 2017
• Deep (Convolutional) Neural Networks
• Sohn et al, Learning Structured Output Representation using Deep Conditional Generative Models, NIPS 2015
• Dosovitskiy et al, Learning to Generate Chairs with Convolutional Neural Networks, CVPR 2015
• Stewart and Ermon, Label-Free Supervision of Neural Networks with Physics and Domain Knowledge, arxiv 2016
• Recurrent Neural Networks
• Ranzatto et al, Sequence Level Training with Recurrent Neural Networks, arxiv 2015
• Alvarez-Melis and Jaakkola, TREE-STRUCTURED DECODING WITH DOUBLYRECURRENT NEURAL NETWORKS, ICLR 2017
• Deng et al, Structure Inference Machines: Recurrent Neural Networks for Analyzing Relations in Group Activity Recognition, CVPR 2016
• Sequence-to-sequence Model
• Kim et al, A Decision Tree Framework for Spatiotemporal Sequence Prediction, KDD 2015
• Sutskever et al, Sequence to Sequence Learning with Neural Networks, NIPS 2014
• Image Captioning and Generation From Text
• Xu et al, Attend and Tell: Neural Image Caption Generation with Visual Attention, ICML 2015
• Mansimov et al, Generating images from captions with attention, ICLR 2016
• Optimization
• Weiss and Taskar, Structured Prediction Cascades, AISTATS 2010
• Shi et al, Learning Where to Sample in Structured Prediction, AISTATS 2015
• Active Learning
• Shivaswamy and Joachims, Online Structured Prediction via Coactive Learning, ICML 2012
• Luo et al, Latent Structured Active Learning, NIPS 2013

Extended Reference Material (could be useful for picking final project)

Note: some papers belong to multiple categories.

• Inference Methods
  • Graph Cuts
  • Kolmogorov and Zabih, What Energy Functions can be Minimized via Graph Cuts?, TPAMI 2004
  • Kolmogorov and Rother, Minimizing Nonsubmodular Functions with Graph Cuts—A Review, TPAMI 2007
  • Message Passing
  • Chapter 2.5 in Graphical Models, Exponential Families, and Variational Inference by Wainwright and Jordan
  • Sampling Methods
  • Sampling-Based Inference, Univ. of Washington lecture note
  • Markov Chain Monte Carlo for Computer Vision
  • Monte Carlo Inference Methods, NIPS 2015 tutorial
  • Andrieu et al, An Introduction to MCMC for Machine Learning, Machine Learning 2003
  • Variational Inference
  • A Tutorial on Variational Bayesian Inference by Fox and Roberts
  • Blei and Jordan, Variational Inference for Dirichlet Process Mixtures, Bayesian Analysis 2006
• Graphical Models
• Markov Random Fields (MRF)
• Taskar et al, Max-margin Markov networks, NIPS 2003
• Djolonga et al, Cooperative Graphical Models, NIPS 2016
• Conditional Random Fields (CRF)
• Sarawagi and Cohen, Semi-Markov Conditional Random Fields for Information Extraction, NIPS 2004
• Ammar et al, Conditional Random Field Autoencoders for Unsupervised Structured Prediction, NIPS 2014
• Topic Model
• Wang and McCallum, Topics over Time: A Non-Markov Continuous-Time Model of Topical Trends, KDD 2006
• Doshi-Velez et al, Graph-Sparse LDA: A Topic Model with Structured Sparsity, AAAI 2015
• Hierarchical / Extreme Classification
• Keerthi et al, A sequential dual method for large scale multi-class linear SVMs, KDD 2008
• Liang et al, Learning Programs: A Hierarchical Bayesian Approach, ICML 2010
• Prabhu and Varma, Fastxml: a fast, accurate and stable tree-classifier for extreme multi-label learning, KDD 2014
• Structured Perceptron
• Huang et al, Forest Reranking: Discriminative Parsing with Non-Local Features, ACL 2008
• Liang et al, An End-to-End Discriminative Approach to Machine Translation, ACL 2006
• Neubig et al, Inducing a Discriminative Parser for Machine Translation Reordering, EMNLP 2012
• Roark et al , Discriminative Language Modeling with Conditional Random Fields and the Perceptron Algorithm, ACL 2004
• McDonald et al, Distributed Training Strategies for the Structured Perceptron, NAACL 2010
• Structured Random Forests
• Tang et al, Latent Regression Forest: Structured Estimation of 3D Articulated Hand Posture, CVPR 2014
• Decision Forests: A Unified Framework for Classification, Regression, Density Estimation, Manifold Learning and Semi-Supervised Learning by Criminisi et al
• Deep Structured Models
• Deep (Convolutional) Neural Networks
• Dong et al, Learning a Deep Convolutional Network for Image Super‐Resolution, ECCV 2014
• Ren et al, Faster r-cnn: Towards real-time object detection with region proposal networks, NIPS 2015
• Machine Translation
• Auli et al, Joint Language and Translation Modeling with Recurrent Neural Networks, EMNLP 2013
• Cho et al, Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation, arxiv 2014
• Bahdanau et al, Neural machine translation by jointly learning to align and translate, ICLR 2015
• Image Captioning and Generation From Text
• Kuznetsova et al, Collective Generation of Natural Image Descriptions, ACL 2012
• Vinyals et al, Show and tell: A neural image caption generator, CVPR 2015
• Gregor et al, DRAW: A Recurrent Neural Network For Image Generation, arxiv 2015
• Optimization
• He and Taskar, Learning to Search in Branch-and-Bound Algorithms, NIPS 2014
• Song et al, Training Deep Neural Networks via Direct Loss Minimization, ICML 2016
• Kuleshov and Liang, Calibrated Structured Prediction, NIPS 2015
• Steinhardt and Liang, Learning Fast-Mixing Models for Structured Prediction, ICML 2015
• Others
• Richardson and Domingos, Markov Logic Networks, MLJ 2005
• Krishnan et al, Deep Kalman Filters, arxiv 2015
• Low et al, GraphLab: A New Framework For Parallel Machine Learning, arxiv 2014
• Prasad et al, Submodular meets Structured: Finding Diverse Subsets in Exponentially-Large Structured Item Sets, NIPS 2014
• Irsoy et al, Deep Recursive Neural Networks for Compositionality in Language, NIPS 2014
• Belanger and McCallum, Structured Prediction Energy Networks, ICML 2016

Related Courses, Tutorials and Textbooks

• Probabilistic Graphical Models: Principles and Techniques by Koller and Friedman
• Structured Learning and Prediction in Computer Vision by Nowozin and Lampert
• Graphical Models, Exponential Families, and Variational Inference by Wainwright and Jordan
• CS 228: Probabilistic Graphical Models, Winter 2016/2017 by Stefano Ermon