Incremental Structured Prediction Using a Global Learning and Beam-Search Framework

Yue Zhang (SUTD), Meishan Zhang (HIT-SCIR), Ting Liu (HIT-SCIR)

We discuss a learning and search framework for structured prediction, which processes the input incrementally, from left to right. Global discriminative learning and beam-search are combined to give high accuracies with typical linear time complexity. The framework has been effectively applied to a range of NLP tasks in recent years, such as syntactic processing and machine translation. It can be used for any structured prediction tasks that can be modeled as a sequence of incremental steps.

The tutorial will begin with an introduction of global discriminative learning algorithms and their efficient implementations, and combination with beam-search. Then case by case, it shows how the framework can be applied to NLP tasks, including word segmentation, POS-tagging and parsing. The theory behind high accuracies will be analyzed, and a software tool that contains the implementations of all discussed topics will be demonstrated.


  1. Introduction (0.5 hours)
    • An overview of the syntactic processing framework and its applications
    • An introduction to the beam-search framework and comparison to dynamic programming
    • Algorithm in details
      • Online discriminative learning using the perceptron
      • Beam-search decoding
      • The integrated framework

  2. Applications (1.25 hours)
    • Overview
    • Word segmentation
    • Joint segmentation and POS-tagging
    • Dependency parsing
    • Context free grammar parsing
    • Combinatory categorial grammar parsing
    • Joint segmentation, POS-tagging and parsing

  3. Analysis of the framework (0.75 hours)
    • The influence of global learning
    • The influence of beam-search
    • Benefits from the combination
    • Related discussions

  4. The ZPar software tool (0.5 hours)


Yue Zhang is an Assistant Professor at Singapore University of Technology and Design (SUTD). Before joining SUTD in 2012, he worked as a postdoctoral research associate at University of Cambridge. He received his PhD and MSc degrees from University of Oxford, and undergraduate degree from Tsinghua University, China. Dr Zhang’s research interest includes natural language parsing, natural language generation, machine translation and machine learning.

Meishan Zhang is a fifth-year PHD candidate at Research Center for Social Computing and Information Retrieval, Harbin Institute of Technology, China (HIT-SCIR). His research interest includes Chinese morphological and syntactic parsing, semantic representation and parsing, joint modeling and machine learning.

Ting Liu is a professor at HIT-SCIR. His research interest includes social computing, information retrieval and natural language processing.