Greedy Inference Algorithms for Structured and Neural Models

A number of problems in Computer Vision, Natural Language Processing, and Machine Learning produce structured outputs in high-dimensional space, which makes searching for the global optimal solution extremely expensive. Thus, greedy algorithms, making trade-offs between precision and efficiency, are widely used. Unfortunately, they in general lack theoretical guarantees. In this thesis, we prove that greedy algorithms are effective and efficient to search for multiple top-scoring hypotheses from structured (neural) models: 1) Entropy estimation. We aim to find deterministic samples that are representative of Gibbs distribution via a greedy strategy. 2) Searching for a set of diverse and high-quality bounding boxes. We formulate this problem as the constrained maximization of a monotonic sub-modular function such that there exists a greedy algorithm having near-optimal guarantee. 3) Fill-in-the-blank. The goal is to generate missing words conditioned on context given an image. We extend Beam Search, a greedy algorithm applicable on unidirectional expansion, to bidirectional neural models when both past and future information have to be considered. We test our proposed approaches on a series of Computer Vision and Natural Language Processing benchmarks and show that they are effective and efficient.

Name thesis:degree_name

Ph. D.

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Electrical Engineering

Department dc:contributor.department

Electrical Engineering

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2018

Author dc:creator

• Sun, Qing

Chairs dc:contributor.committeechair

• Batra, Dhruv
• Huang, Jia-Bin

Committee members dc:contributor.committeemember

• Abbott, A. Lynn
• Parikh, Devi
• Prakash, B. Aditya
• Dhillon, Harpreet Singh

• greedy algorithm
• natural language processing
• graph models
• recurrent neural networks
• beam search

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

vt_gsexam:13673

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/81860