Structure as simplification : transportation tools for understanding data

Abstract

The typical machine learning algorithms looks for a pattern in data, and makes an assumption that the signal to noise ratio of the pattern is high. This approach depends strongly on the quality of the datasets these algorithms operate on, and many complex algorithms fail in spectacular fashion on simple tasks by overfitting noise or outlier examples. These algorithms have training procedures that scale poorly in the size of the dataset, and their out-puts are difficult to intepret. This thesis proposes solutions to both problems by leveraging the theory of optimal transport and proposing efficient algorithms to solve problems in: (1) quantization, with extensions to the Wasserstein barycenter problem, and a link to the classical coreset problem; (2) natural language processing where the hierarchical structure of text allows us to compare documents efficiently;(3) Bayesian inference where we can impose a hierarchy on the label switching problem to resolve ambiguities.