University of Illinois Urbana-Champaign

Evaluating exact and approximate algorithms for integer linear programming formulations of MAP inference

Mangipudi, Bhargav

Content Files
MANGIPUDI-THESIS-2017.pdf

Permalink

https://hdl.handle.net/2142/99111

Description

Title
Evaluating exact and approximate algorithms for integer linear programming formulations of MAP inference
Author(s)
Mangipudi, Bhargav
Issue Date
2017-07-17
Director of Research (if dissertation) or Advisor (if thesis)
Roth, Dan
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Date of Ingest
2018-03-02T19:59:42Z
Keyword(s)
  • Structured inference
  • Constrained conditional models
  • Graphical models
Abstract
Structured prediction tasks involve an inference step which allows for producing coherent label assignments to the output structure. This can be achieved by constraining the output using prior knowledge about the domain. This paradigm is called Constrained Conditional Models; and it involves augmenting the learning of conditional models with declarative constraints. The MAP inference problem in CCM framework can be solved by formulating an Integer Linear Programming problem. This ILP formulation is generally relaxed to an Linear Programming problem by dropping the integrality constraints and making it tractable. In this work, we evaluate other approximate inference algorithms for the MAP estimate for structured prediction task in the CCM framework. We model the constrained structured prediction problem as a factor graph and use different graphical models based algorithms. We evaluate these methods for the quality of their solution and the computation time over some NLP tasks with varying complexity. For large-scale problems, the tradeoff between inference time and the approximateness of the solution is a crucial aspect. Furthermore, these inference solvers are provided as black-box implementations in Saul, which is a declarative programming language for structured prediction tasks.
Graduation Semester
2017-08
Type of Resource
text
Permalink
http://hdl.handle.net/2142/99111
Copyright and License Information
Copyright 2017 Bhargav Mangipudi

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Siebel School of Computer Science