Transformations, Equivalences and Comparisons of Learning Problems

Abstract

While artificial intelligence (AI) has achieved striking practical success across diverse applications, the theoretical foundations of many modern methods remain incomplete. In particular, a rigorous account of how the individual components of an AI system influence the outcome of its (machine) learning process is yet to be established. These components are numerous and heterogeneous, contributing to the high complexity of AI models; consequently, there is no reason to expect a single approach to fully resolve this gap. Thus, the present thesis abstracts away from the particular data points, optimization algorithms, and other technical aspects of AI systems. Paying a price in specificity, we gain a significant advantage: a framework for theoretically characterizing the interplay between the core components of a machine learning problem — loss function, model class, and data-generating probability distribution. In particular, we pay specific attention to the latter, as it is an often overlooked component in many modern works.

We prove two main types of results, namely Bayes risk equalities and inequalities, obtaining equivalences and comparisons of learning problems, respectively. As a preliminary analysis, we provide an exhaustive taxonomy of stochastic transformations of a problem’s data distribution by leveraging properties of Markov kernels, i.e., the objects used to model the transformations. Studying equalities, we then learn how different Markov kernel types lead to distinct consequences. For example, applying label noise to the data distribution yields a learning problem equivalent to one that retains the original data-generating probability but with a modified loss function. By contrast, attribute noise will jointly affect both loss and model class in the equivalent problem. These findings suggest that classical loss correction techniques for noisy data are only effective in the case of label noise, not for general attribute noise. We then compute what a generalized loss correction approach would entail for attribute noise. However, focusing solely on equivalences only partially explains how tweaking one component affects the learning outcome. Studying the inequalities, we explore when one learning problem can be considered superior to another. This challenge can be addressed in multiple ways, as problems can be compared by varying the probability distribution, model class, or loss. Previous work explored comparing conditional probabilities for every loss and model class, arriving at interesting characterization results nowadays grouped under the Blackwell-Sherman-Stein theorem. This work has found application in economics as well as learning theory, and nicely relates to classical results in information theory. Our contribution frames the existing results into the larger perspective of comparing learning problems instead of conditional probabilities. We then focus on comparing couples of model classes and losses for every probability, introducing a theory complementary to Blackwell’s work, revolving around establishing when a decision maker is better than another. We study this question by means of Bayes risk orderings, which are proved to be equivalent to the inclusion ordering on certain sets, called superprediction sets. These sets are defined starting from fixing a loss and model class, and therefore provide geometrical understanding to the question of comparing decision makers. We additionally prove sufficient conditions for the ordering to hold on certain types of loss and model classes, which are decided by the type of noisy data considered. Hence, these results additionally show the central role of knowing what are the data at hand so to be able to understand the related learning problem.

This work advances theoretical understanding of machine learning systems as highly entangled entities. Its first set of results underscores the critical importance of choosing your data carefully, as they demonstrate that changing the distribution is equivalent to changing the loss and model class. This can cause strong mismatches between what one expects the machine to learn and what the machine actually learns. In particular, the equalities proved offer guidance for designing corrections that aim to achieve accurate learning in the presence of noisy data. The second set of contributions introduces a novel theory for comparison of models and losses, and in particular for comparing them before and after a transformation is applied to the learning problem. This is relevant in the field of model complexity, as it introduces a decision-theoretic inspired framework to assess whether a certain decision maker is more reliable (in terms of risk) than another under a certain type of noise.