INDIGO Home University of Illinois at Urbana-Champaign logo uic building uic pavilion uic student center

Adversarial Prediction Framework for Information Retrieval and Natural Language Processing Metrics

Show full item record

Bookmark or cite this item:

Files in this item

File Description Format
PDF WANG-DISSERTATION-2017.pdf (1MB) (no description provided) PDF
Title: Adversarial Prediction Framework for Information Retrieval and Natural Language Processing Metrics
Author(s): Wang, Hong
Advisor(s): Ziebart, Brian D.
Contributor(s): Zhang, Xinhua; Di Eugenio, Barbara; Liu, Bing; Roth, Dan; Ziebart, Brian D.
Department / Program: Computer Science
Degree Granting Institution: University of Illinois at Chicago
Degree: PhD, Doctor of Philosophy
Genre: Doctoral
Subject(s): Adversarial classification structure prediction Information Retrieval and Natural Language Processing application
Abstract: Many Information Retrieval (IR) and Natural Language Processing (NLP) tasks require predicting structured objects (e.g., sequences, rankings, matchings, parse trees) that are evaluated using F-score (i.e., the harmonic mean of precision and recall), precision at k (P@k, which limits the number of positive predictions to k), discounted cumulative gain (DCG), alignment error rate (AER), Hamming loss (i.e., accuracy) or other multivariate performance measures. Due to the non-convexity of most of the multivariate performance metrics, and the computational intractability of optimizing empirical risk over those metrics, traditional Machine Learning algorithms use convex surrogates (e.g., log-loss for Logistic Regression, hinge-loss for Support Vector Machine) as the approximations for empirical risk optimization. However, these approximations introduce a mismatch between the learner's objective and the desired application performance. How can Machine Learning algorithms' predictions be more closely aligned with application performance measures in Information Retrieval and Natural Language Processing? In this thesis, we focus on answering this question by building an adversarial prediction framework - Multivariate Prediction Game (MPG) - for the metrics that are widely used in Information Retrieval and Natural Language Processing areas. MPG treats the multivariate prediction as an adversarial zero-sum game between a loss-minimizing prediction player and a loss-maximizing evaluation player constrained to match specified properties of training data. By solving the problem of effectively finding the best responses to the opponent's strategies, and applying the double oracle constraint generation method, the framework avoids the non-convexity of empirical risk minimization, and hence directly optimizes the metrics. In this thesis, we first introduce the background of our research with its related works. Then, the Multivariate Prediction Game framework is explained in detail. For each metric of predicting structure, we give the corresponding algorithm for effectively finding the best responses. Finally, the MPGs are evaluated on several widely used data sets in Information Retrieval and Natural Language Processing areas to demonstrate their effectiveness.
Issue Date: 2017-01-30
Type: Thesis
Date Available in INDIGO: 2017-10-27
Date Deposited: May 2017

This item appears in the following Collection(s)

Show full item record


Country Code Views
United States of America 25
China 11
Ukraine 4
Germany 3
Russian Federation 1


My Account


Access Key