Adversarial Prediction Framework for Information Retrieval and Natural Language Processing Metrics

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.