Preview

PDF, English Download (2MB) | Terms of use

Abstract

Structured prediction is the task of jointly predicting realizations of multiple coupled random variables. This statistical problem is central to many advanced applications of deep learning, including image segmentation and graph node classification. This thesis presents a two-pronged study of predicting structured discrete data, exploring geometric aspects and statistical learning. On the geometric side, we first interpret distributions of independent discrete random variables as points on a product manifold of probability simplices. We find that this manifold is isometrically embedded into the meta-simplex of joint probability distributions. This finding illuminates the relationship between inference dynamics on the product manifold, called assignment flows, and replicator dynamics on the meta-simplex. The former can be seen as the replicator dynamics of multi-population games and the constructed embedding formally reduces them to high-dimensional single-population game dynamics. Based on these geometric insights, we propose two types of generative models for discrete data by facilitating measure transport through randomized assignment flows. The first approximates a given energy-based model, while the second is learned directly from data. Experiments on image segmentation data illustrate the viability of the proposed method. With regard to statistical learning, we explore current methods in PAC-Bayesian risk certification and propose a classification approach with favorable computational properties. Further, we develop a novel PAC-Bayesian risk bound for structured prediction, which can account for generalization even from a single structured datum. The lack of independent data is addressed by distilling the coupling structure of the joint data distribution, given as a Knothe-Rosenblatt rearrangement of a reference measure, allowing for the use of modern concentration of measure results.