# Decontamination of Mutually Contaminated Models

Gilles Blanchard, Clayton Scott

► To cite this version:

Gilles Blanchard, Clayton Scott. Decontamination of Mutually Contaminated Models. Seventeenth International Conference on Artificial Intelligence and Statistics (AISTATS 2014), 2014, Reykjavik, Iceland. pp.1-9. hal-03371264

HAL Id: hal-03371264

https://hal.science/hal-03371264

Submitted on 8 Oct 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Decontamination of Mutually Contaminated Models

Gilles Blanchard

Universität Potsdam

Clayton Scott

University of Michigan

## Abstract

A variety of machine learning problems are characterized by data sets that are drawn from multiple different convex combinations of a fixed set of base distributions. We call this a mutual contamination model. In such problems, it is often of interest to recover these base distributions, or otherwise discern their properties. This work focuses on the problem of classification with multiclass label noise, in a general setting where the noise proportions are unknown and the true class distributions are nonseparable and potentially quite complex. We develop a procedure for decontamination of the contaminated models from data, which then facilitates the design of a consistent discrimination rule. Our approach relies on a novel method for estimating the error when projecting one distribution onto a convex combination of others, where the projection is with respect to a statistical distance known as the separation distance. Under sufficient conditions on the amount of noise and purity of the base distributions, this projection procedure successfully recovers the underlying class distributions. Connections to novelty detection, topic modeling, and other learning problems are also discussed.

## 1 Introduction

This paper considers a general framework for multi-class classification with label noise. As we develop later, this framework encompasses or relates to several other machine learning problems, including novelty detection, crowdsourcing, topic modeling, and learning

from partial labels. Each of these applications involves mutual contamination models, meaning that observed data are drawn from mixtures of the underlying probability distributions of interest, and therefore may be viewed as being contaminated.

We begin by stating the problem of multiclass classification with label noise in a general setting. There are L classes, each governed by a class-conditional distribution $P_i$. The learner observes training random samples drawn from the contaminated distributions

$$ \tilde{P}_i = \sum_{j=1}^{L} \pi_{ij} P_j, \qquad (1) $$

$i = 1, \dots, L$, where $\pi_{ij} \ge 0$ and $\sum_j \pi_{ij} = 1$ for each $i$. Here $\pi_{ij}$ is the probability that an instance with observed label $i$ is actually a realization of $P_j$. We consider a quite general setting where the $\pi_{ij}$ are unknown, and the distributions $P_i$ are not amenable to parametric modeling. We want to stress that the issue of contamination of training data comes in addition to, and is different from, the usual source of uncertainty about the labels in “noisy classification”, which traditionally simply means that the supports of the true $P_i$ can overlap (which we also allow here). In the contamination setting, training a conventional classifier directly on the contaminated training data will in general lead to a biased classifier at test time (Scott et al., 2013), and in particular be asymptotically inconsistent.

Our contribution is to establish general sufficient conditions on the true class-conditional distributions and label noise mixing proportions for recovery of the true distributions, which then enables the design of a consistent discrimination rule. The sufficient conditions essentially state that the examples drawn from $\tilde{P}_i$ come “mostly” from $P_i$, and that the distributions $\{P_i\}$ are “pure” with respect to each other. Both of these notions are made precise below.

At the heart of our approach is a novel technique for “decontamination” of the contaminated models. In particular, we show that under the sufficient conditions, if we project the contaminated distribution $\tilde{P}_i$

<footnote>Appearing in Proceedings of the 17th International Conference on Artificial Intelligence and Statistics (AISTATS) 2014, Reykjavik, Iceland. JMLR: W&CP volume 33. Copyright 2014 by the authors.</footnote>
onto the convex hull of the other contaminated distributions, the “residual” distribution is the true class-conditional distribution $P_i$. The projection is with respect to a statistical distance known as the separation distance, and a key part of our contribution is the development of a universally consistent estimator of the error of this projection. This estimator is valid regardless of whether the sufficient conditions for label noise recovery hold, and is therefore of independent interest.

## 1.1 Motivation

The label noise model (1) is relevant in a number of applications. For example, Scott et al. (2013) describe a problem in nuclear particle classification. Each class corresponds to a different type of nuclear particle, and label noise comes from the fact that it is impossible to eliminate different particle types from the background, so that every training sample for a given particle type is always contaminated with particles of other types.

Another potential application of the label noise model is crowdsourcing, where the labels of training data sets are provided by a mixture of expert and non-expert sources. One approach to crowdsourcing is to assume each annotator makes mistakes according to model (1), where the contamination probabilities are specific to each annotator. Then there is a label noise problem for each annotator. The “two-coin” model of Raykar et al. (2010) studies this setup in the two-class setting.

As a second formulation of crowdsourcing, consider unlabeled data representing some mixture of the true class-conditional distributions $P_i$, and suppose the data is labeled by crowdsourcing. One simple labelling model is as follows: with probability $1 - \alpha$, an example is labeled by an expert, in which case the correct label is always assigned. With probability $\alpha$, a random guesser assigns the label according to some predetermined distribution over class that is independent of the actual example. This fits the contamination model (1), and furthermore, as we argue in Sec. 5, satisfies our sufficient conditions on the noise.

A third relevant application is novelty detection. Suppose that for $i < L$ and $j \neq i$, we have $\pi_{ij} = 0$. In other words, the first $L-1$ data samples are uncontaminated. The last data sample, on the other hand, is drawn from a mixture of all classes. We may think of this as a semi-supervised learning problem, where the first $L-1$ random samples represent training data, while the last sample is an unlabeled testing sample. Then $P_L$ corresponds to a novel class that is not represented among the $L-1$ training classes. We argue in Sec. 5 that this setting also satisfies our sufficient conditions on the noise, thus yielding a consistent discrimination rule for multiclass novelty detection.

Several previous works on classification with label noise also adopt (1) or an equivalent model, and we refer the reader to these works for additional applications of the label noise setting (Lawrence and Schölkopf, 2001; Bouveyron and Girard, 2009; Long and Servido, 2010; Manwani and Sastry, 2011; Stempfel and Ralaivola, 2009; Natarajan et al., 2013). Significantly, our works provide estimates of the proportions $\pi_{ij}$, which are assumed known in several of these earlier works.

Topic modeling is another problem that is closely related to multiclass label noise. In topic modeling, the base distributions $P_i$ correspond to topics, and each $\tilde{P}_i$ corresponds to a document, viewed as a mixture of topics. An important difference between topic modeling and classification with label noise is that in topic modeling, typically far more documents are observed than topics. Nonetheless, as we discuss in Sec. 5, our sufficient conditions on the purity of the base distributions, when specialized to the discrete setting of topic modeling, coincide with the “separability” condition that has been widely adopted in that area.

Finally, we note that multiclass label noise has strong similarities to the problem of learning from partial labels (Cour et al., 2011). In this problem, every training data point is labeled by a subset $S \subset \{1, \dots, L\}$ of possible labels, as opposed to a single label as in standard classification. The true label is one of the elements of the subset, but it is not known which one. Therefore, collecting all training examples sharing a common $S$ gives a contamination model $\tilde{P}_S = \sum_{j \in S} \pi_{S,j} P_j$, and there is a contamination model (with associated data) for every observed $S$. We conjecture that this problem can be converted to a multiclass label noise problem, satisfying our sufficient conditions on the noise, through appropriate resampling of the data. Some insight is given in Sec. 5, although a full development is deferred to future work.

## 1.2 Related Work

Our work extends the recent work of Scott et al. (2013), reviewed in the next section, which studies label noise for binary classification ($L = 2$). We find there to be some significant differences between the multiclass and binary cases. Indeed the decontamination procedure is considerably more complex, as are the sufficient conditions for recovery. Multiclass label noise has received little attention in the literature. Existing theoretical work on label noise (of which we are aware) focuses on the binary case; we refer the reader to Scott et al. (2013) for a recent review.

The aforementioned projection in distribution space is accomplished by means of a problem we call multi-
sample mixture proportion estimation, which is apparently new. It generalizes a two-sample version developed by Blanchard et al. (2010). It is also similar to the problem of semi-supervised class proportion estimation; the latter problem essentially assumes that the projection error is zero, and is only concerned with estimating the mixing weights giving the projection (Hall, 1981; Titterington, 1983; Latinne et al., 2001; Du Plessis and Sugiyama, 2012). When the projection error is nonzero, as in our work, such methods are inconsistent.

## 1.3 Outline

In the next section we review the work of Scott et al. (2013) on label noise in the binary setting. Section 3 presents the aforementioned mixture proportion estimation problem and our universally consistent estimator. Section 4 introduces sufficient conditions under which this estimator successfully decontaminates the noisy distributions in the multiclass label noise setting. The final section connects our results more concretely to the other learning problems mentioned above. Proofs are contained in the supplemental file.

# 2 Label Noise in the Binary Case

Scott et al. (2013) study label noise in the binary case, $L = 2$. Their work hinges on the following result, which appears originally in Blanchard et al. (2010).

**Proposition 1.** Given probability distributions $F_0, F_1$ on a measurable space $(\mathcal{X}, \mathcal{C})$, define

$$ \kappa^*(F_0|F_1) = \max \left\{ \begin{array}{l} \kappa \in [0,1] \mid \exists \text{ a distribution } G \\ \text{s.t. } F_0 = (1-\kappa)G + \kappa F_1 \end{array} \right\}; \quad (2) $$

If $F_0 \neq F_1$, then $\kappa^*(F_0|F_1) < 1$ and the above supremum is attained for a unique distribution $G$ (which we refer to as the residue of $F_0$ w.r.t. $F_1$). Furthermore, the following equivalent characterization holds:

$$ \kappa^*(F_0|F_1) = \inf_{C \in \mathcal{C}, F_1(C)>0} \frac{F_0(C)}{F_1(C)}. \quad (3) $$

The number $\kappa^*(F_0|F_1)$ can be understood at the maximum possible proportion of $F_1$ present in $F_0$. The result implies that the function $1 - \kappa^*(F_0|F_1)$ is a statistical distance, i.e., a functional that is nonnegative and equal to zero iff $F_0 = F_1$. This quantity has been called the separation distance, and has arisen previously in studies of Markov chain convergence (Aldous and Diaconis, 1987).

For the label noise/contamination model (1), the following two conditions are shown by Scott et al. (2013) to be sufficient for decontamination:

* $\pi_{12} + \pi_{21} < 1$,

* $\kappa^*(P_1|P_2) = \kappa^*(P_2|P_1) = 0$.

The former condition bounds the total amount of label noise, while the latter condition is referred to as mutual irreducibility, and says that it is not possible to write $P_1$ as a nontrivial mixture of $P_2$ and some other distribution, and vice versa.

In particular, by a simple algebraic manipulation of (1), it is shown that under the first condition

$$ \tilde{P}_1 = (1 - \kappa_1)P_1 + \kappa_1 \tilde{P}_2 \quad (4) $$

$$ \tilde{P}_2 = (1 - \kappa_2)P_2 + \kappa_2 \tilde{P}_1, \quad (5) $$

for unique $\kappa_1, \kappa_2 < 1$. It is then shown that if $P_1$ and $P_2$ are mutually irreducible, then $\kappa_1 = \kappa^*(\tilde{P}_1|\tilde{P}_2)$ and $\kappa_2 = \kappa^*(\tilde{P}_2|\tilde{P}_1)$ and therefore $P_1$ and $P_2$ are the respective residues of $\tilde{P}_1$ w.r.t. $\tilde{P}_2$ and $\tilde{P}_2$ w.r.t. $\tilde{P}_1$. This establishes decontamination in the population case.

In the sample case, the problem of estimating $\kappa^*$ is referred to as mixture proportion estimation. The universally consistent estimator $\hat{\kappa}$ of Blanchard et al. (2010) for $\kappa^*$ is applied to estimate $\kappa_1$ and $\kappa_2$. Now all terms in (4) and (5) can be estimated except for $P_1$ in (4) and $P_2$ in (5). Therefore (4) and (5) can be solved for (estimates of) $P_1$ and $P_2$, which are then available for the design of a consistent discrimination rule.

Multiclass label noise can be treated analogously, although the generalization is far from trivial.

# 3 Multi-Sample Mixture Proportion Estimation

Let $(\mathcal{X}, \mathcal{C})$ be a measurable space, and let $F_i$ be probability distributions on this space, $i = 0, 1, \dots, M$.

Let $S_M$ denote the $(M-1)$-dimensional simplex $\{\mu = (\mu_1, \dots, \mu_M) \in \mathbb{R}^M \mid \forall i \mu_i \ge 0 \text{ and } \sum_i \mu_i = 1\}$.

For $\mu \in S_M$, denote the probability distribution $F_\mu := \sum_{i=1}^M \mu_i F_i$. We first define the maximum collective contaminating proportion of distributions $(F_i)_{1 \le i \le M}$ in $F_0$ by the following generalization of the binary case:

**Definition 1.** Given probability distributions $F_i$, $i = 0, \dots, M$, define

$$ \kappa^*(F_0|F_1, \dots, F_M) = \max_{\mu \in S_M} \kappa^*(F_0|F_\mu). \quad (6) $$

If there is a unique $F_\mu$ achieving the maximum in this definition, it may be thought of as the projection of $F_0$ onto the convex hull of $F_1, \dots, F_M$ with respect to the separation distance. However, there exist simple examples for which $F_\mu$ attaining $\kappa^*$ is not unique; for example, suppose $M = 2$. Let $F_0$ be uniform on $\{0, 1, 2\}$,
$F_1$ uniform on $\{0, 1\}$, and $F_2$ uniform on $\{1, 2\}$. Then $\kappa^* = \frac{2}{3}$ and any $\boldsymbol{\mu}$ is optimal. Later, when we return to the label noise problem, we give sufficient conditions, analogous to those in the binary case, for the unicity of $\boldsymbol{\mu}$, so that the projection is well defined.

Observe that the following equivalent characterizations for $\kappa^*$ hold:

$$ \begin{aligned} \kappa^*(F_0|F_1, \dots, F_M) &= \max_{\boldsymbol{\mu} \in S_M} \inf_{C \in \mathcal{C}: F_{\boldsymbol{\mu}}(C) > 0} \frac{F_0(C)}{F_{\boldsymbol{\mu}}(C)} & (7) \\ &= \max \left\{ \kappa \in [0, 1] \middle| \exists \boldsymbol{\mu} \in S_M \text{ and a distribution } G \right. \end{aligned} $$

$$ \text{s.t. } F_0 = (1 - \kappa)G + \kappa F_{\boldsymbol{\mu}} \} \quad (8) $$

$$ = \max \left\{ \sum_{i=1}^{M} \nu_i \middle| \begin{array}{l} \nu_i \ge 0, \sum_{i=1}^{M} \nu_i \le 1, \text{ and} \\ \exists \text{ a distribution } G \text{ s.t.} \end{array} \right. $$

$$ F_0 = \left( 1 - \sum_{i=1}^{M} \nu_i \right) G + \sum_{i=1}^{M} \nu_i F_i. \quad (9) $$

The equivalence of (6), (7) and (8) is a straightforward consequence of the equivalent definitions (2) and (3) in the 2-class case. The equivalence of (8) and (9) is also clear from the representation $\kappa = \sum_i \nu_i$ and $\boldsymbol{\mu} = (\nu_1, \dots, \nu_M)/\kappa$. The fact that the maxima are well-defined is justified formally in the supplemental material. Finally, if the maximum is attained for a unique $G$ in (8)-(9), we refer to $G$ as the residue of $F_0$ w.r.t. $F_1, \dots, F_M$.

Suppose that for $m = 0, 1, \dots, M$, we observe

$$ X_1^m, \dots, X_{n_m}^m \stackrel{iid}{\sim} F_m $$

The random samples need not be independent of each other. Let $\hat{F}_i$ denote the corresponding empirical distributions. By way of notation, set $\boldsymbol{n} := (n_0, n_1, \dots, n_M)$ and write $\boldsymbol{n} \to \infty$ to indicate $\min_i \{n_i\} \to \infty$.

To define the estimator, let $C_k \subset C$, $k \ge 1$ be VC classes with VC dimensions $V_k < \infty$. For each $0 \le m \le M, k \ge 1$ and $\delta > 0$, define

$$ \epsilon_m^k(\delta) := 3\sqrt{\frac{V_k \log(n+1) - \log \delta/2}{n_m}}. $$

By the VC inequality (Devroye et al., 1996), the following property holds:

**P1** For each value of $k, m$, and $\delta > 0$, the following holds with probability at least $1 - \delta$:

$$ \sup_{C \in \mathcal{C}_k} \left| F_m(C) - \hat{F}_m(C) \right| \le \epsilon_m^k(\delta), $$

where the probability is with respect to the draw of $X_1^m, \dots, X_{n_m}^m \stackrel{iid}{\sim} F_m$.

We also require that $(C_k)_{k \ge 1}$ possess the following universal approximation property:

**P2** For any probability distribution $Q$, any $C^* \in C$:

$$ \liminf_{k \to \infty} \inf_{C \in \mathcal{C}_k} Q(C \Delta C^*) = 0, $$

where $C_1 \Delta C_2 := (C_1 \setminus C_2) \cup (C_2 \setminus C_1)$ is the symmetric difference.

Examples of such classes include histograms, decision trees, neural networks, and generalized linear classifiers (Devroye et al., 1996).

Given $\delta := (\delta_0, \dots, \delta_M)$, a vector with positive components, we define the estimator

$$ \begin{aligned} \hat{\kappa}(\hat{F}_0|\hat{F}_1, \dots, \hat{F}_M; \delta) &= \max_{\boldsymbol{\mu} \in S_M} \inf_{k \in \mathcal{C}_k} \inf \frac{\hat{F}_0(C) + \epsilon_0^k(c\delta_0k^{-2})}{(\hat{F}_{\boldsymbol{\mu}}(C) - \sum_i \mu_i \epsilon_i^k(c\delta_i k^{-2}))_+}, \end{aligned} \quad (10) $$

where $c := 6/\pi^2$, and the ratio is defined as $+\infty$ if the denominator is zero. Also, denote $\hat{\boldsymbol{\mu}}$ an arbitrary point where the above maximum is attained; and finally $\hat{\boldsymbol{\nu}} = \hat{\kappa}\hat{\boldsymbol{\mu}}$ (where the explicit dependence on $\hat{F}_0$, etc., has been omitted to simplify notation). $\hat{\boldsymbol{\nu}}$ is an estimate of the contaminating proportions $(\nu_1, \dots, \nu_M)$ achieving the maximum in (9).

**Proposition 2.** Let $(C_k)_{k \ge 1}$ be a sequence of classes of sets with finite VC dimension and having the universal approximation property **P2**.

* (a) It holds that $\hat{\kappa} \ge \kappa^*$ with probability at least $1 - \sum_{i=0}^M \delta_i$.

* (b) If for all $i$, $\delta_i(\boldsymbol{n}) = 1/n_i$, then $\hat{\kappa}$ converges in probability to $\kappa^*$ as $\boldsymbol{n} \to \infty$, for any family of generating distributions $(F_i, i = 0, \dots, M)$.

* (c) Let $\mathcal{B}_* := \text{Arg Max}_{\boldsymbol{\mu} \in S_M} \kappa^*(F_0|F_{\boldsymbol{\mu}})$, i.e., $\mathcal{B}_*$ is the set of all mixture weights $\boldsymbol{\mu}$ attaining the max. in (6). Then under the assumptions of point (b), $d(\hat{\boldsymbol{\mu}}, \mathcal{B}_*)$ converges to zero in probability as $\boldsymbol{n} \to \infty$ (where $d$ is any continuous distance function on the simplex). A similar result holds for the convergence in probability of $\hat{\boldsymbol{\nu}}$ to the set of weight vectors attaining $\kappa^*$ in (9).

The definition of the estimator (10) is an intuitive generalization of the consistent estimator $\hat{\kappa}(\hat{F}_0|\hat{F}_1)$ of
Blanchard et al. (2010), with an added maximum operation over $\mu \in S_M$. The proof of the above result, however, does not follow trivially from the pointwise consistency of $\hat{\kappa}(\hat{F}_0|\hat{F}_\mu)$ to $\kappa^*(F_0|F_\mu)$ for all fixed $\mu \in S_M$, and requires a careful compactness argument. Furthermore, point (c) entails that the weights defining the residue are estimated consistently if they are unique (i.e., when $B_*$ contains a single element), which they are in the label noise setting under the sufficient conditions given below.

**Practical feasibility.** The focus of this work is on identifiability and existence of a consistent estimator. While a suitable practical implementation is left for future work, we observe that there exist a priori reasonable strategies to compute $\hat{\kappa}$. Because the $\epsilon^k(\dots)$ terms become eventually larger than 1 for large $k$, the infimum over $k$ can be limited to $k \le k_{max}(n)$. The inner infimum loop can then be computed exactly if the classes $C_k$ are finite (for instance, this is the case for the pieces of dyadic regular partitions of order $k$). The outer maximum loop can in turn be solved by gradient ascent (in alternating steps with the infimum solving step), which will converge to the global maximum since the inverse of the objective function is a linear function of $\mu$.

Henceforth $\delta$ will be omitted from the notation for $\hat{\kappa}$, and $\delta_i$ taken to equal $1/n_i$.

# 4 Multiclass Label Noise

The model in (1) may be concisely expressed as $\tilde{P} = \Pi P$, where

$$P = \begin{bmatrix} P_1 \\ \vdots \\ P_L \end{bmatrix}, \quad \tilde{P} = \begin{bmatrix} \tilde{P}_1 \\ \vdots \\ \tilde{P}_L \end{bmatrix},$$

and $\Pi = [\pi_{ij}]$ is an $L \times L$ matrix with nonnegative entries and rows summing to one. We begin with identifiability assumptions that enable decontamination.

## 4.1 Assumptions

We start with a generalization of mutual irreducibility: **Lemma 1.** The following conditions on the family of distributions $P_1, \dots, P_L$ are equivalent:

* It is not possible to write

$$\sum_{i \in I} \epsilon_i P_i = \alpha \left( \sum_{i \notin I} \epsilon_i P_i \right) + (1 - \alpha) H,$$

where $I \subset \{1, \dots, L\}$ such that $1 \le |I| < L$, $\epsilon_i$ are such that $\epsilon_i \ge 0$ and $\sum_{i \in I} \epsilon_i = \sum_{i \notin I} \epsilon_i = 1$, $\alpha \in (0, 1]$, and $H$ is a distribution.

* If $\sum_{i=1}^L \gamma_i P_i$ is a distribution, then $\gamma_i \ge 0 \forall i$.

**Definition 2.** We say the distributions $\{P_i\}_{1 \le i \le L}$ are jointly irreducible iff the conditions in Lemma 1 hold.

Joint irreducibility says that every convex combination of some portion of the $P_i$s is irreducible w.r.t. every convex combination of the remaining $P_i$s. It generalizes the notion of mutual irreducibility from the two-class case (see Sec. 2). One case where it holds is when the support of each $P_i$ contains some region with positive probability that does not intersect the supports of the other $P_j, j \ne i$. If each $P_i$ is a class-conditional distribution, this means that every class has some exemplars that could not possibly arise from another class. This assumption is not unreasonable in many, and perhaps most, applications of interest. Joint irreducibility can still hold even when all $P_i$ have the same support, as in the case of Gaussian densities with a common variance (Scott et al., 2013).

We will also make assumptions on the contamination weight matrix $\Pi$. Let $\pi_i$ be the transpose of the $i$-th row of $\Pi$, which is a discrete probability distribution on $\{1, \dots, L\}$. Let $e_i$ denote the length $L$ vector with $1$ in the $i$th position and zeros elsewhere.

**Lemma 2.** The following conditions on $\pi_1, \dots, \pi_L$ are equivalent:

(a) For each $\ell$, the residue of $\pi_\ell$ with respect to $\{\pi_j, j \ne \ell\}$ is $e_\ell$.

(b) For every $\ell$ there exists a decomposition $\pi_\ell = \kappa_\ell e_\ell + (1 - \kappa_\ell) \pi'_\ell$ where $\kappa_\ell > 0$ and $\pi'_\ell$ is a convex combination of $\pi_j$ for $j \ne \ell$.

(c) $\Pi$ is invertible and $\Pi^{-1}$ is a matrix with strictly positive diagonal entries and nonpositive off-diagonal entries.

**Definition 3.** We say that $\Pi$ is recoverable iff the conditions in Lemma 2 hold.

This assumption ensures that the amount of contamination is not too high. Some intuition is given by condition (b). Fig. 1 depicts the case $L = 3$. In panel (i), condition (b) is satisfied, while in panel (ii), condition (b) is not satisfied. Clearly, in panel (i), the diagonal entries $\pi_{\ell\ell}$ are much larger than they are in panel (ii), and consequently the off-diagonal entries of $\Pi$ will be smaller. Note that for $L = 2$ classes, from condition (c), recoverability is equivalent to $\pi_{12} + \pi_{21} < 1$, the condition developed by Scott et al. (2013).

We exhibit a setting where $\Pi$ is guaranteed to be recoverable. Assume $c := \sum_{i=1}^M c_i e_i$ is a contaminating “background noise” which is common to all observed classes, albeit in possibly different proportions, i.e.,
$\pi_i = \kappa_i c + (1 - \kappa_i)e_i$, with $\kappa_i \in [0, 1)$. Geometrically, this means we shift by various amounts the vertices $e_i$ of the simplex towards a common point $c$, or equivalently that each $\pi_\ell$ belongs to the segment ($ce_\ell$]. Panel (iii) illustrates this situation.

Then we have

$$ \sum_i \frac{c_i}{1 - \kappa_i} \pi_i = \left( 1 + \sum_i \frac{c_i \kappa_i}{1 - \kappa_i} \right) c, $$

so that for instance for $\ell = 1$ and $\kappa_1 > 0$,

$$ \frac{c_1}{1 - \kappa_1} \pi_1 + \sum_{i \ge 2} \frac{c_i}{1 - \kappa_i} \pi_i = \left( 1 + \sum_i \frac{c_i \kappa_i}{1 - \kappa_i} \right) \left( \frac{1}{\kappa_1} \pi_1 - \frac{1 - \kappa_1}{\kappa_1} e_1 \right), $$

and finally

$$ \left( 1 + \sum_i \frac{c_i \kappa_i}{1 - \kappa_i} \right) (1 - \kappa_1) e_1 + \kappa_1 \sum_{i \ge 2} \frac{c_i}{1 - \kappa_i} \pi_i = \pi_1 \left( 1 + \sum_{i \ge 2} \frac{c_i \kappa_i}{1 - \kappa_i} \right), $$

which is also valid when $\kappa_1 = 0$. Since all of the above coefficients are positive, this implies condition (b) (or (c)) of Lemma 2 after normalization.

In Sec. 5 we consider various applications where the recoverability assumption is satisfied.

## 4.2 Decontamination

The following result shows that the recoverability and joint irreducibility conditions ensure decontamination in the population (infinite sample) case. This result is applied in the next subsection, in conjunction with the estimator of Section 3, to establish a consistent discrimination rule.

**Proposition 3.** If $\Pi$ is recoverable and $P_1, \dots, P_L$ are jointly irreducible, then for each $\ell$, $P_\ell$ is the residue of $\tilde{P}_\ell$ w.r.t. $\{\tilde{P}_j, j \neq \ell\}$. Furthermore, in the representation

$$ \tilde{P}_{\ell} = (1 - \kappa_{\ell})P_{\ell} + \sum_{j \neq \ell} \nu_{\ell j} \tilde{P}_{j}, \quad (11) $$

where $\kappa_\ell = \kappa^*(\tilde{P}_\ell | \{\tilde{P}_j, j \neq \ell\})$, $\kappa_\ell < 1$ and the $\nu_{\ell j}$ are unique.

The proof of this result shows that under the joint irreducibility assumption, decontamination of the $\tilde{P}_\ell$ is equivalent to decontamination of the discrete distributions $\pi_\ell$, which may be viewed as contaminated versions of the $e_i$. In other words, the same weights

$\kappa_\ell$ and $\nu_{\ell j}$ uniquely give the solutions of both approximation problems. The desired solution of the discrete problem is guaranteed by the recoverability assumption on $\Pi$ (so that $e_\ell$ is the residue of $\pi_\ell$ w.r.t. $\{\pi_j\}_{j \neq \ell}$), and this ensures, by the equivalence of the decontamination problems, that $P_\ell$ is the residue of $\tilde{P}_\ell$ w.r.t. $\{\tilde{P}_j, j \neq \ell\}$.

This equivalence leads to a second insight: By a construction in the proof of Lemma 2, $\Pi^{-1}$ can be expressed explicitly in terms of the optimal weights $\kappa_\ell$ and $\nu_{\ell j}$. Therefore, under the assumptions of Proposition 3, $\Pi^{-1}$ can be consistently estimated (i.e., recovered) via the estimator in Section 3.

## 4.3 A Consistent Discrimination Rule

The decontamination result gives a way to accurately estimate the true class-conditional error probabilities, which can then be converted into a consistent discrimination rule. These details now follow. For any classifier, that is, any measurable function $f: \mathcal{X} \to \{1, \dots, L\}$, denote $R_i(f) := P_i(f(X) \neq i)$, where $X$ follows $P_i$. As a performance measure we adopt the minmax criterion, which seeks to minimize

$$ R(f) := \max_{1 \le i \le L} R_i(f). $$

The optimal performance is the minmax error, $R^* := \inf_f R(f)$, where the inf is over all classifiers. Note that other performance measures could also be analyzed; we focus on the minmax criterion for concreteness.

The crux of classifier design is accurate error estimation. Denote $\tilde{R}_{j\ell}(f) := \tilde{P}_j(f(X) \neq \ell)$. To motivate an estimator for $R_\ell(f)$, the expression in (11) implies

$$ R_{\ell}(f) = \frac{\tilde{R}_{\ell\ell}(f) - \sum_{j \neq \ell} \nu_{\ell j} \tilde{R}_{j\ell}(f)}{1 - \kappa_{\ell}}. $$

If $X_1^j, \dots, X_{n_j}^j \stackrel{iid}{\sim} \tilde{P}_j$ are the observed data from class $j$, then

$$ \hat{R}_{j\ell}(f) := \frac{1}{n_j} \sum_{i=1}^{n_j} \mathbf{1}_{\{f(X_i^j) \neq \ell\}} $$

estimates $\tilde{R}_{j\ell}(f)$. Now let $(\hat{\nu}_{\ell j})_{j \neq \ell}$ be any vector achieving the maximum in the definition of $\hat{\kappa}_\ell := \hat{\kappa}(\hat{P}_\ell | \{\hat{P}_j, j \neq \ell\})$, so that $\hat{\kappa}_\ell = \sum_{j \neq \ell} \hat{\nu}_{\ell j}$. By Proposition 2, this vector converges to the unique weights $\nu_{\ell j}$ in Proposition 3, motivating the following estimator:

$$ \hat{R}_{\ell}(f) := \frac{\hat{R}_{\ell\ell}(f) - \sum_{j \neq \ell} \hat{\nu}_{\ell j} \hat{R}_{j\ell}(f)}{1 - \hat{\kappa}_{\ell}}. $$

It is well known in statistical learning theory that consistency of a learning algorithm follows from uniform
<figure><img src="image_2.png" /><figcaption>Figure 1: Illustration of the recoverability condition when $L = 3$. Panel (i): Low noise, Π recoverable. Each $\pi_\ell$ can be written as a convex combination of $e_\ell$ and the other two $\pi_j$ (with a positive weight on $e_\ell$), depicted here for $\ell = 1$. Panel (ii): High noise, Π not recoverable. Panel (iii): The setting of “common background noise.”</figcaption></figure>

control of error estimates over a class of classifiers $\mathcal{F}$, whose complexity may grow with sample size. Thus we introduce a sequence $(\mathcal{F}_k)_{k \ge 1}$ of sets of classifiers with VC dimension $V_k < \infty$. Since we are in a multiclass setting, we adopt the following generalization of VC dimension to multiclass, namely, define the VC dimension of class $\mathcal{F}$ to be the maximum (conventional) VC dimension of the family of sets $\{x : f(x) \ne \ell\}_{\ell \in \mathcal{F}}$, over $\ell = 1, \dots, L$. This particular multiclass generalization of VC dimension allows our analysis to proceed using only the standard VC inequality for binary classifiers (or equivalently, for sets, as in Section 3). Indeed, the VC inequality (Devroye et al., 1996) gives uniform convergence of $\tilde{R}_{j\ell}(f)$ to $\tilde{R}_{j\ell}(f)$ over $f$ in $\mathcal{F}_k$, and together with consistency of $\hat{\kappa}_\ell$ and $(\hat{\nu}_{\ell j})$ implies the following result. Similar to Section 3, set $\mathbf{n} := (n_1, \dots, n_L)$ and write $\mathbf{n} \to \infty$ to indicate $\min\{n_\ell\} \to \infty$.

**Proposition 4.** Let $k(\mathbf{n})$ take positive integer values and be such that as $\mathbf{n} \to \infty$,

$$ \frac{V_{k(\mathbf{n})} \log n_{\ell}}{n_{\ell}} \to 0, $$

1 $\le \ell \le L$. Then under the assumptions of Proposition 3, $\sup_{f \in \mathcal{F}_{k(\mathbf{n})}} |R_{\ell}(f) - \hat{R}_{\ell}(f)| \xrightarrow{i.p.} 0$ as $\mathbf{n} \to \infty$.

This result allows us to analyze the estimation error of a learning algorithm based on $\hat{R}_\ell$. To control the approximation error, we choose $(\mathcal{F}_k)$ such that

**P3** For any $P_1, \dots, P_L$, $\lim_{k \to \infty} \inf_{f \in \mathcal{F}_k} R(f) = R^*$.

This condition is analogous to the condition for our family of sets $(C_k)$ in Section 3.

Let us now define a discrimination rule based on the above error estimates. Define $\hat{R}(f) := \max_{\ell} \hat{R}_{\ell}(f)$. Let $\tau_k$ be any sequence of positive numbers tending to

zero. Let $\hat{f}_k$ denote any classifier

$$ \hat{f}_k \in \{f \in \mathcal{F}_k : \hat{R}(f) \le \inf_{f \in \mathcal{F}_k} \hat{R}(f) + \tau_k\}. $$

The introduction of $\tau_k$ lets us avoid assuming the existence of an empirical risk minimizer. Finally, define the discrimination rule $\hat{f} := \hat{f}_k(\mathbf{n})$.

**Theorem 1.** Let $k(\mathbf{n})$ take positive integer values and be such that as $\mathbf{n} \to \infty$, $k(\mathbf{n}) \to \infty$ and

$$ \frac{V_{k(\mathbf{n})} \log n_{\ell}}{n_{\ell}} \to 0, \quad (12) $$

1 $\le \ell \le L$. Then under **P3** and the assumptions of Proposition 3, $R(\hat{f}) \xrightarrow{i.p.} R^*$ as $\mathbf{n} \to \infty$.

Thus, if the noise is recoverable and the distributions jointly irreducible, consistent classification is possible in the multiclass label noise setting.

## 5 Discussion

We now develop connections between the above theoretical framework for multiclass label noise and various applications mentioned in the introduction.

Consider the second crowdsourcing formulation, and suppose that unlabeled data are drawn according to $\sum_{j=1}^L \theta_j P_j$. Further suppose that with probability $1 - \alpha$, the label is assigned correctly, while with probability $\alpha$, the label is assigned according to some fixed distribution, say the uniform distribution $[\frac{1}{L}, \dots, \frac{1}{L}]^T$. Let $Y$ denote the true label of an example, and $\tilde{Y}$ the crowdsourced label. By Bayes' rule,

$$ \begin{aligned} \pi_{ij} &= \mathrm{Pr}(Y = j | \tilde{Y} = i) \\ &\propto \mathrm{Pr}(\tilde{Y} = i | Y = j) \mathrm{Pr}(Y = j) \\ &= ((1 - \alpha) \mathbf{1}_{\{i=j\}} + \frac{\alpha}{L}) \theta_j. \end{aligned} $$
In vector form, this means $\pi_i \propto (1 - \alpha)\theta_i e_i + \frac{\alpha}{L}\theta$, where $\theta = [\theta_1, \dots, \theta_L]^T$. This clearly satisfies the common background noise model described previously, and therefore our noise condition is satisfied.

Next, consider the semi-supervised novelty detection problem described in the introduction. In this case

$$ \Pi = \begin{bmatrix} 1 & & & \\ & 1 & & \\ & & \ddots & \\ & & & \pi_{LL} \end{bmatrix} $$

because the first $L-1$ data samples are uncontaminated, while the last sample is an unlabeled testing sample where $P_L$ governs the novelty class. It is easy to see that $\Pi$ is recoverable if and only if $\pi_{LL} > 0$, using condition (c) of Lemma 2. Therefore, as long as there are at least some novel exemplars in the unlabeled data, the noise condition is satisfied, and under joint irreducibility we have a consistent discrimination rule for multiclass, semi-supervised novelty detection. We also note that the above is not the only approach to novelty detection using mixture proportion estimation (Sanderson and Scott, 2014).

Our work has an interesting connection to the problem of topic modeling, itself linked to nonnegative matrix factorization. In that problem, one also observes random samples from several contaminated distributions ("documents") $\tilde{P}_i$, but in the equation $\tilde{P} = \Pi P$, the matrix $\Pi$ is no longer square but now has far more rows than columns. The distributions $P_i$ are "topics," and the proportion $\pi_{ij}$ reflects the prevalence of topic $j$ in document $i$. Existing work on topic modeling typically represents the topics and documents as discrete distributions on a finite vocabulary. One interesting connection to our work is that in this discrete setting, our joint irreducibility condition is equivalent to a condition that has been previously shown to be sufficient for identifiability of the topics. In particular, in the discrete setting, this assumption states that for each topic, there exists at least one word occurring with a positive probability in the given topic, and with a probability of zero in the other topics (Donoho and Stodden, 2004; Arora et al., 2012).

Finally, we return to the problem of learning from partial labels (Cour et al., 2011). For the sake of argument we consider a simple form of the problem. Suppose there are $L = 3$ classes, and that each observed data point is labeled $A = \{1, 2\}, B = \{1, 3\}$, or $C = \{2, 3\}$. The true label of each example is one of the labels in the associated subset. Grouping together observations according to the three "partial labels" ($A, B$, or $C$), these three data samples are described by the contamination models $\tilde{P}_S = \sum_{j \in S} \pi_{S,j} P_j$, where

<figure><img src="image_3.png" /><figcaption>Figure 2: Learning from partial labels reduces to multiclass label noise in some cases.</figcaption></figure>

$S \in \{A, B, C\}$. Each data sample arises from a convex combination of two of the three base distributions, as depicted in Fig. 2. Since these contaminated models lie on the boundary of the probability simplex, they do not satisfy the recoverability assumption on the noise. However, by resampling the data, we may obtain random samples from distributions that do satisfy the noise assumption. For simplicity, let's assume $\pi_{S,j} = 1/2$ for each $j \in S$, i.e., each contaminated model is an equal mixture of the two associated base distributions. For every pair of contaminated models, corresponding to subsets $S$ and $T$, form a new random sample by resampling from the two observed samples, such that the new random samples are realizations of $\frac{1}{2}\tilde{P}_S + \frac{1}{2}\tilde{P}_T$. If $\Pi$ and $\tilde{\Pi}$ denote the contamination proportions before and after resampling, then

$$ \Pi = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & \frac{1}{2} & \frac{1}{2} \end{bmatrix}, \quad \tilde{\Pi} = \begin{bmatrix} \frac{1}{2} & \frac{1}{4} & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{2} \end{bmatrix}. $$

The situation is depicted in Fig. 2. The rows $(\tilde{\pi}_i)^T$ of $\tilde{\Pi}$ satisfy $\tilde{\pi}_i = \frac{1}{4}e_i + \frac{3}{4}c$, where $c = [\frac{1}{3}, \frac{1}{3}, \frac{1}{3}]^T$, which is in the form of the common background noise model, implying our noise condition. Our framework can now be applied to the resampled data, assuming joint irreducibility, to give a consistent discrimination rule for learning from partial labels. If $\Pi$ is perturbed slightly, our noise assumption still holds, and we further conjecture that this kind of resampling strategy may be applied when $L > 3$ and when the pattern of observed subsets is more general.

## Acknowledgements

G. Blanchard was supported in part by the European Community's 7th Framework Programme under the E.U. grant agreement 247022 (MASH Project). C. Scott was supported in part by NSF Grants 0953135, 1047871, and 1217880.
## References

D. Aldous and P. Diaconis. Strong uniform times and finite random walks. *Adv. Appl. Math.*, 8(1):69–97, 1987.

S. Arora, R. Ge, and A. Moitra. Learning topic models – going beyond SVD. In *FOCS*. 2012.

G. Blanchard, G. Lee, and C. Scott. Semi-supervised novelty detection. *Journal of Machine Learning Research*, 11:2973–3009, 2010.

C. Bouveyron and S. Girard. Robust supervised classification with mixture models: Learning from data with uncertain labels. *Journal of Pattern Recognition*, 42:2649–2658, 2009.

T. Cour, B. Sapp, and B. Taskar. Learning from partial labels. *J. Machine Learning Research*, 12:1501–1536, 2011.

L. Devroye, L. Györfi, and G. Lugosi. *A Probabilistic Theory of Pattern Recognition*. Springer, 1996.

D. Donoho and V. Stodden. When does non-negative matrix factorization give a correct decomposition into parts? In Sebastian Thrun, Lawrence Saul, and Bernhard Schölkopf, editors, *Advances in Neural Information Processing Systems 16*. MIT Press, Cambridge, MA, 2004.

M. C. Du Plessis and M. Sugiyama. Semi-supervised learning of class balance under class-prior change by distribution matching. In J. Langford and J. Pineau, editors, *Proc. 29th Int. Conf. on Machine Learning*, pages 823–830, 2012.

P. Hall. On the non-parametric estimation of mixture proportions. *Journal of the Royal Statistical Society*, 43(2):147–156, 1981.

P. Latinne, M. Saerens, and C. Decaestecker. Adjusting the outputs of a classier to new a priori probabilities may signicantly improve classication accuracy: Evidence from a multi-class problem in remote sensing. In C. Sammut and A. H. Hoffmann, editors, *Proc. 18th Int. Conf. on Machine Learning*, pages 298–305, 2001.

N. Lawrence and B. Schölkopf. Estimating a kernel Fisher discriminant in the presence of label noise. *Proceedings of the International Conference in Machine Learning*, 2001.

P. Long and R. Servido. Random classification noise defeats all convex potential boosters. *Machine Learning*, 78:287–304, 2010.

N. Manwani and P. S. Sastry. Noise tolerance under risk minimization. Technical Report arXiv:1109.5231, 2011.

N. Natarajan, I. S. Dhillon, P. Ravikumar, and A. Tewari. Learning with noisy labels. In *Advances in Neural Information Processing Systems 26*, 2013.

V. C. Raykar, S. Yu, L. H. Zhao, G. H. Valadez, C. Florin, L. Bogoni, and L. Moy. Learning from crowds. *The Journal of Machine Learning Research*, 99:1297–1322, 2010.

T. Sanderson and C. Scott. Class proportion estimation with application to multiclass anomaly rejection. In *Proceedings of the 17th International Conference on Artificial Intelligence and Statistics (AIS-TATS)*, 2014.

C. Scott, G. Blanchard, and G. Handy. Classification with asymmetric label noise: Consistency and maximal denoising. In *Proc. Conf. on Learning Theory*, JMLR W&CP, volume 30, pages 489–511. 2013.

G. Stempfel and L. Ralaivola. Learning SVMs from sloppily labeled data. In *Proc. 19th Int. Conf. on Artificial Neural Networks: Part I*, pages 884–893, 2009.

D. M. Titterington. Minimum distance non-parametric estimation of mixture proportions. *Journal of the Royal Statistical Society*, 45(1):37–46, 1983.
# Supplemental Material for the AISTATS 2014 paper

## “Decontamination of Mutually Contaminated Models”

Gilles Blanchard and Clayton Scott

## A Proofs for Section 3

### A.1 $\kappa^*$ and $\hat{\kappa}$ are well-defined

**Lemma A.1.** The maximum operation in the definition of $\kappa^*$ and $\hat{\kappa}$ is well-defined, that is, the outside supremum is attained at at least one point.

We prove the statement for

$$ \kappa^* = \max_{\mu} \inf_{C \in \mathcal{C}: F_{\mu}(C) > 0} \frac{F_0(C)}{F_{\mu}(C)}. $$

The argument for $\hat{\kappa}$ is similar. Denote $G(\mu) = \kappa^*(F_0|F_\mu) = \inf_{C \in \mathcal{C}: F_{\mu}(C) > 0} \frac{F_0(C)}{F_{\mu}(C)}$ the maximum proportion of the mixture $F_\mu$ in the distribution $F_0$.

We argue that $G$ is an upper semicontinuous function. To see this, define for each $C \in \mathcal{C}$ the function $g_C: S_M \to [0, \infty)$ as

$$ g_C(\mu) := \begin{cases} \frac{F_0(C)}{F_{\mu}(C)} & \text{if } F_{\mu}(C) > 0; \\ +\infty & \text{if } F_{\mu}(C) = 0. \end{cases} $$

Then $f_C$ is an upper semicontinuous function: if $\mu \in S_M$ is such that $F_\mu(C) > 0$, then $f_C$ is continuous at point $\mu$. Otherwise, $f_C(\mu) = \infty$ and $f_C$ is trivially upper semicontinuous at point $\mu$. Clearly, one has $G(\mu) = \inf_{C \in \mathcal{C}} f_C(\mu)$; as an infimum of upper semicontinuous functions, it is itself upper semicontinuous, and therefore attains its maximum on the compact set $S_M$.

### A.2 Proof of Proposition 2

Point (a): We apply condition P1 for all $k, i$ with $\delta_{k,i} = c\delta_i/k^2$. By the union bound, with probability at least $1 - \sum_{i=0}^M \delta_i$, it holds simultaneously for all $k \ge 1$ and $i = 0, \dots, M$ that

$$ \forall k \ge 1, \quad \forall i \in \{0, \dots, M\} : \quad \sup_{C \in \mathcal{C}_k} \left| F_i(C) - \hat{F}_i(C) \right| \le \epsilon_i^k (c\delta_i k^{-2}) \quad (S.1) $$
Recall the notation (from the proof of Lemma A.1) $G(\mu) = \inf_{C \in \mathcal{C}: F_\mu(C) > 0} \frac{F_0(C)}{F_\mu(C)}$ and introduce

$$ \hat{G}(\boldsymbol{\mu}) := \inf_k \inf_{C \in \mathcal{C}_k} \frac{\hat{F}_0(C) + \epsilon_0^k (c\delta_0 k^{-2})}{(\hat{F}_\mu(C) - \sum_i \nu_i \epsilon_i^k (c\delta_i k^{-2}))_+} $$

Observe that when (S.1) is satisfied, this implies that for all $\mu \in S_M$, one has $G(\mu) \le \hat{G}(\mu)$. Taking the maximum over $\mu$ yields the first point.

Point (b): let $\epsilon > 0$ be an arbitrary positive constant. For any $\mu \in S_M$, let $C_\mu \in \mathcal{C}$ with $F_\mu(C_\mu) > 0$ be such that $\frac{F_0(C_\mu)}{F_\mu(C_\mu)} \le \kappa^* + \epsilon/4$.

By continuity of the function $\mu \mapsto F_\mu(C)$ for any fixed $C$, there exists for each $\mu \in S_M$ an open neighborhood $N_\mu$ of $\mu$ for which both of the following conditions are realized for all $\mu' \in N_\mu$:

$$ \frac{F_0(C_\mu)}{F_{\mu'}(C_\mu)} \le \kappa^* + \frac{\epsilon}{2}, \qquad (S.2) $$

$$ \text{and } F_{\mu'}(C_{\mu}) \ge \frac{1}{2} F_{\mu}(C_{\mu}). \qquad (S.3) $$

(For the second condition, we have used the fact that $F_\mu(C_\mu) > 0$). By compactness of $S_M$, there exists a finite subset $S_M^\epsilon$ of $S_M$ such that $(N_\mu)_{\mu \in S_M^\epsilon}$ covers $S_M$.

Denote $F_{\min}^\epsilon := \frac{1}{2} \min_{\mu \in S_M^\epsilon} F_\mu(C_\mu)$; it is a positive quantity since $F_\mu(C_\mu) > 0$ for any $\mu$, and $S_M^\epsilon$ is finite. For each $\mu \in S_M$, denote $\zeta(\mu)$ an arbitrary element of the finite net $S_M^\epsilon$ such that $\mu \in N_\zeta(\mu)$. By property (S.2), we have

$$ \sup_{\mu \in S_M} \frac{F_0(C_\zeta(\mu))}{F_\mu(C_\zeta(\mu))} \le \max_{\mu \in S_M^\epsilon} \sup_{\mu' \in N_\mu} \frac{F_0(C_\mu)}{F_{\mu'}(C_\mu)} \le \kappa^* + \frac{\epsilon}{2}, \qquad (S.4) $$

and by property (S.3):

$$ \inf_{\mu \in S_M} F_\mu(C_\zeta(\mu)) \ge \min_{\mu \in S_M^\epsilon} \inf_{\mu' \in N_\mu} F_{\mu'}(C_\mu) \ge F_{\min}^\epsilon. \qquad (S.5) $$

Denote $C_\epsilon := \{C_\mu, \mu \in S_M^\epsilon\}$. Let $\eta \in (0, F_{\min}^\epsilon/2)$ be another arbitrary positive constant. Consider the distribution $Q = \frac{1}{M+1} \sum_{i=0}^M F_i$, to which we apply condition (P2). This entails that for each individual $C \in \mathcal{C}$ there exists a $k_C$ and $\tilde{C} \in C_{k_C}$ with

$$ Q(C\Delta\tilde{C}) \le \frac{\eta}{M+1}, $$

implying for all $i \in \{0, \dots, M\}$:

$$ |F_i(C) - F_i(\tilde{C})| \le F_i(C\Delta\tilde{C}) \le (M+1)Q(C\Delta\tilde{C}) \le \eta, $$

and then also for all $\mu \in S_M$:

$$ |F_\mu(\tilde{C}) - F_\mu(C)| \le \sum_{i=1}^{M} \mu_i |F_i(C) - F_i(\tilde{C})| \le \eta. $$
In what follows we use the shortened notation $\varepsilon_i^k \equiv \epsilon_i^k(c\delta_i k^{-2})$, and further define $\varepsilon(\epsilon, \eta) := \max_i \max_{C \in C_\epsilon} \varepsilon_i^{kC}$. For fixed $(\epsilon, \eta)$, the quantity $\varepsilon(\epsilon, \eta)$ is defined as a maximum of a finite number of functions decreasing to 0 as $n \to \infty$, and therefore $\varepsilon$ also decreases to zero. Below, we assume that all components of $n$ are chosen big enough so that $F_{\min}^\epsilon - \eta - 2\varepsilon(\epsilon, \eta) > 0$. It holds with probability $1 - \sum_{i=0}^M \delta_i$ that

$$
\begin{align*}
\hat{\kappa} &\le \sup_{\mu \in S_M} \inf_{k \in C_k} \frac{F_0(C) + 2\varepsilon_0^k}{(F_\mu(C) - 2\sum_i \mu_i \varepsilon_i^k)_+} \\
&\le \sup_{\mu \in S_M} \inf_{C \in C} \frac{F_0(\tilde{C}) + 2\varepsilon_0^{kC}}{(F_\mu(\tilde{C}) - 2\sum_i \mu_i \varepsilon_i^{kC})_+} \\
&\le \sup_{\mu \in S_M} \inf_{C \in C} \frac{F_0(C) + \eta + 2\varepsilon_0^{kC}}{(F_\mu(C) - \eta - 2\sum_i \mu_i \varepsilon_i^{kC})_+} \\
&\le \sup_{\mu \in S_M} \frac{F_0(C_\zeta(\mu)) + \eta + 2\varepsilon_0^{kC_\zeta(\mu)}}{(F_\mu(C_\zeta(\mu)) - \eta - 2\sum_i \mu_i \varepsilon_i^{kC_\zeta(\mu)})_+} \\
&\le \sup_{\mu \in S_M} \frac{F_0(C_\zeta(\mu)) + \eta + 2\varepsilon(\epsilon, \eta)}{(F_\mu(C_\zeta(\mu)) - \eta - 2\varepsilon(\epsilon, \eta))_+} \\
&\le \left( \sup_{\mu \in S_M} \frac{F_\mu(C_\zeta(\mu))}{(F_\mu(C_\zeta(\mu)) - \eta - 2\varepsilon(\epsilon, \eta))_+} \right) \sup_{\mu \in S_M} \frac{F_0(C_\zeta(\mu)) + \eta + 2\varepsilon(\epsilon, \eta)}{F_\mu(C_\zeta(\mu))} \\
&\le \left( \frac{F_{\min}^\epsilon}{(F_{\min}^\epsilon - \eta - 2\varepsilon(\epsilon, \eta))_+} \right) \left( \sup_{\mu \in S_M} \frac{F_0(C_\zeta(\mu))}{F_\mu(C_\zeta(\mu))} + \sup_{\mu \in S_M} \frac{\eta + 2\varepsilon(\epsilon, \eta)}{F_\mu(C_\zeta(\mu))} \right) \\
&\le \left( \frac{F_{\min}^\epsilon}{(F_{\min}^\epsilon - \eta - 2\varepsilon(\epsilon, \eta))_+} \right) \left( \kappa^* + \frac{\epsilon}{2} \right) + \frac{\eta + 2\varepsilon(\epsilon, \eta)}{(F_{\min}^\epsilon - \eta - 2\varepsilon(\epsilon, \eta))_+},
\end{align*}
$$

where we have used (S.4) and (S.5) for the last inequality. By choosing first $\eta$ small enough, then all components of $n_0$ big enough, the r.h.s. of the above inequality can be made smaller than $\kappa^* + \epsilon$, for all $n > n_0$ ($>$ indicates the inequality holds for all components). Since $\sum_{i=0}^M \delta_i \to 0$ as $\mu \to 0$, this implies the second part of the proposition.

For the last point of the proposition, consider an arbitrary open set $\Omega$ containing the set $B^*$. Then $\Omega^c := S_M \setminus \Omega$ is a compact set; therefore, the function $G(\mu) := \inf_{C \in C, F_\mu(C) > 0} \frac{F_0(C)}{F_\mu(C)}$, being upper semicontinuous (see proof of Lemma A.1), attains its supremum $\tilde{\kappa}$ on $\Omega^c$. Observe that $\tilde{\kappa} > \kappa^*$ must hold, otherwise we would have a contradiction with the definition of $B^*$. Finally, we have:

$$
\begin{align*}
\mathbb{P}[\hat{\mu} \notin \Omega] &\le \mathbb{P}[\hat{\mu} \notin \Omega; G(\hat{\mu}) \le \hat{G}(\hat{\mu})] + \mathbb{P}[G(\hat{\mu}) > \hat{G}(\hat{\mu})] \\
&\le \mathbb{P}[\hat{\kappa} \ge \tilde{\kappa}] + \sum_{i=1}^{M} \delta_i,
\end{align*}
$$
where we have used that $\hat{\kappa} = \hat{G}(\hat{\mu})$ by definition, and the argument used in the proof of point (a). By point (b), the first probability converges to 0 as $\mu \to \infty$. Thus, the probability that $\hat{\mu} \in \Omega$ must converge to 1 as $n \to \infty$. This applies in particular to any open set of the form $\Omega_{\epsilon} := \{\mu : d(\mu, \mathcal{B}^*) < \epsilon\}$, hence the conclusion.

# B Proofs for Section 4

## B.1 Proof of Lemma 1

Suppose the first condition does not hold, so that

$$ \sum_{i \in I} \epsilon_i P_i = \alpha \left( \sum_{i \notin I} \epsilon_i P_i \right) + (1 - \alpha)H. $$

Then $\sum_i \gamma_i P_i = H$, where $\gamma_i = \frac{\epsilon_i}{1-\alpha}$ for $i \in I$, and $\gamma_i = -\frac{\alpha \epsilon_i}{1-\alpha}$ for $i \notin I$. Since $\sum_{i \notin I} \epsilon_i = 1$, at least one $\gamma_i < 0$, so the second condition is violated.

Now suppose the second condition is violated, say $\sum_i \gamma_i P_i = H$. Let $I = \{i | \gamma_i \ge 0\}$, which has fewer than $K$ elements by assumption. Since $\sum_i \gamma_i = 1$, we also know $1 \le |I|$ and further that $\Gamma := \sum_{i \in I} \gamma_i > 1$. A violation of the first condition is obtained by $\epsilon_i = \gamma_i/\Gamma$ for $i \in I$, $\epsilon_i = -\gamma_i/(\Gamma - 1)$ for $i \notin I$ (noting that $\sum_{i \notin I} (-\gamma_i) = \Gamma - 1$), and $\alpha = (\Gamma - 1)/\Gamma$.

## B.2 Proof of Lemma 2

(a) ⇒ (b): Follows immediately from the definition of the residue.

(b) ⇒ (c): By assumption, there exists $\kappa > 0$ such that $\pi_1 = \kappa e_1 + (1 - \kappa)\eta_1$, where $\eta_1 = \sum_{i=2}^L \mu_i \pi_i$, with $\mu_i \ge 0$, for all $2 \le i \le L$. Thus,

$$ e_1 = \kappa^{-1} \pi_1 - \sum_{i=2}^{L} \frac{(1 - \kappa)}{\kappa} \mu_i \pi_i; $$

a similar relation holds for all rows. This implies that $\Pi$ is invertible and allows to identify (for instance) the first row of $\Pi^{-1}$ as $(\kappa^{-1}, -\frac{(1-\kappa)}{\kappa}\mu_2, \dots, -\frac{(1-\kappa)}{\kappa}\mu_L)$. This implies (c).

(c) ⇒ (a): Without loss of generality, consider $\ell = 1$ and the problem of identifying $\kappa^*(\pi_1|(\pi_i)_{2 \le i \le L})$, and the associated residue (if it exists). According to characterization (9), this corresponds to the optimization problem

$$ \max_{\nu, \gamma} \sum_{i=2}^{L} \nu_i \quad \text{s.t.} \quad \pi_1 = (1 - \sum_{i \ge 2} \nu_i)\gamma + \sum_{i \ge 2} \nu_i \pi_i, $$

over $\gamma \in S_L$ and $\nu = (\nu_2, \dots, \nu_L) \in \Delta_{L-1} = \{(\nu_2, \dots, \nu_L) | \nu_i \ge 0; \sum_{i=2}^L \nu_i \le 1\}$.
We now reformulate this problem. First, note that the constraint implies that admissible $\nu$ are such that $\sum_{i \ge 2} \nu_i < 1$, otherwise we would have a linear relation between the $\pi_i$, contradicting invertibility of $\Pi$.

Then for an admissible $\nu$, denote $\eta(\nu) := (1 - \sum_{i \ge 2} \nu_i)^{-1}(1, -\nu_2, \dots, -\nu_L)$. Observe that the constraint of the optimization problem is equivalent to $\Pi^T \eta = \gamma$, or $\eta = (\Pi^T)^{-1}\gamma$. The inverse mapping of $\eta$ to $\nu$ is $\nu(\eta) = \eta_1^{-1}(-\eta_2, \dots, -\eta_L)$, so that the objective of the optimization can be rewritten as

$$-\frac{\sum_{i=2}^{L} \eta_i}{e_1^T \eta} = -\frac{1^T \eta}{e_1^T \eta} + 1 = 1 - \frac{1}{e_1^T \eta} = 1 - \frac{1}{e_1^T (\Pi^T)^{-1} \gamma},$$

where 1 denotes a $L$-dimensional vector with all coordinates equal to 1. So finding the point of maximum of the above problem is equivalent to the program

$$\max_{\gamma \in S_L} e_1^T (\Pi^T)^{-1} \gamma \quad \text{s.t.} \quad \nu((\Pi^T)^{-1} \gamma) \in \Delta_{L-1}$$

The above objective function has the form $a^T \gamma$, where $a$ is the first column of $\Pi^{-1}$ which, by assumption, has its first coordinate positive and the others nonpositive. Therefore, the unconstrained maximum over $\gamma \in S_M$ is attained uniquely for $\gamma = e_1$. We now check that this value also satisfies the required constraint. Observe that $(\Pi^T)^{-1} e_1$ is the (transpose of) the first row of $\Pi^{-1}$, denote this vector as $b = (b_1, \dots, b_L)$. We want to ensure that $\nu(b) = b_1^{-1}(-b_2, \dots, -b_L) \in \Delta_{L-1}$. By assumption, $b$ has its first coordinate positive and the others nonpositive, ensuring all components of $\nu(b)$ are nonnegative. Furthermore, the sum of the components of $\nu(b)$ is

$$\sum_{i=2}^{L} -\frac{b_i}{b_1} = 1 - \frac{\sum_{i=1}^{L} b_i}{b_1} = 1 - \frac{1}{b_1} \le 1;$$

the last equality is because the rows of $\Pi^{-1}$ sum to 1 (since $\Pi$ is a stochastic matrix, so is its inverse). It follows that $\nu((\Pi^T)^{-1}e_1) \in \Delta_{L-1}$. Thus, the unique maximum of the optimization problem is attained for $\gamma = e_1$, establishing (a).

## B.3 Proof of Proposition 3

We start with the following Lemma:

**Lemma B.1.** If $\Pi$ is recoverable, then $\pi_1, \dots, \pi_L$ are linearly independent. If $P_1, \dots, P_L$ are jointly irreducible, then they are linearly independent. If $\pi_1, \dots, \pi_L$ are linearly independent and $P_1, \dots, P_L$ are linearly independent, then $\tilde{P}_1, \dots, \tilde{P}_L$ are linearly independent.

*Proof of the lemma:* The first statement follows from characterization (c) of Lemma 2: if $\Pi$ is recoverable, it is invertible and thus has full rank.

For the second statement, suppose $\sum_i \beta_i P_i = 0$ is a nontrivial linear relation. Let $j$ be any index such that $\beta_j \ge 0$. Then $\sum_i \gamma_i P_i = P_j$, where $\gamma_i = \beta_i$ if $i \ne j$, and $\gamma_j = \beta_j + 1$. Since at least one $\beta_i < 0$, $i \ne j$, joint irreducibility is violated.
For the third part, suppose $\sum_i \alpha_i \tilde{P}_i = 0$. Since $\tilde{P}_i = \pi_i^T P$, this implies $\sum_i \alpha_i \pi_i^T P = 0$, which implies $\sum_i \alpha_i \pi_i = 0$, which implies $\alpha_i = 0$.

*Proof of Proposition 3:* Consider $\ell = 1$, the other cases being similar. Suppose $G$ is such that

$$ \tilde{P}_1 = (1 - \sum_{j \ge 2} \nu_j)G + \sum_{j \ge 2} \nu_j \tilde{P}_j. \qquad (S.6) $$

Note that $\tilde{P}_1, \dots, \tilde{P}_L$ are linearly independent by Lemma B.1. This implies $\sum_{j \ge 2} \nu_j < 1$, because otherwise $\tilde{P}_1 = \sum_{j \ge 2} \nu_j \tilde{P}_j$.

Therefore, any $G$ satisfying (S.6) has the form $\sum_{i=1}^L \gamma_i P_i$. The weights $\gamma_i$ clearly sum to one, and by joint irreducibility, they are nonnegative. That is, $\gamma := [\gamma_1, \dots, \gamma_L]^T$ is a discrete distribution. Thus, Eqn. (S.6) is equivalent to

$$ \pi_1^T P = (1 - \sum_{j \ge 2} \nu_j) \gamma^T P + \sum_{j \ge 2} \nu_j \pi_j^T P. $$

By linear independence of $P_1, \dots, P_L$ (see Lemma B.1) and taking the transpose, this gives

$$ \pi_1 = (1 - \sum_{j \ge 2} \nu_j)\gamma + \sum_{j \ge 2} \nu_j \pi_j. $$

Therefore $\kappa^*(\tilde{P}_1|\{\tilde{P}_j, j \ne 1\}) = \kappa^*(\pi_1|\{\pi_j, j \ne 1\}) < 1$, and there is a one-to-one correspondence between feasible $G$ in the definition of $\kappa^*(\tilde{P}_1|\{\tilde{P}_j, j \ne 1\})$ and feasible $\gamma$ in the definition of $\kappa^*(\pi_1|\{\pi_j, j \ne 1\})$. Since $\Pi$ is recoverable, the residue of $\pi_1$ w.r.t. $\{\pi_j, j \ne 1\}$ is $\gamma = e_1$, and so the residue of $\tilde{P}_1$ w.r.t. $\{\tilde{P}_j, j \ne 1\}$ is $G = e_1^T P = P_1$.

To see uniqueness of the maximizing $\nu_j$, suppose

$$ \tilde{P}_1 = (1 - \kappa^*)G + \sum_{j \ge 2} \nu_j \tilde{P}_j = (1 - \kappa^*)G + \sum_{j \ge 2} \nu'_j \tilde{P}_j. $$

Lemma B.1 implies $\nu_j = \nu'_j$.

## B.4 Proof of Proposition 4

For brevity we at times omit the dependence of the errors and their estimates on $f$. For any $f$,

$$ \begin{aligned} |R_{\ell}(f) - \hat{R}_{\ell}(f)| &= \left| \frac{\tilde{R}_{\ell\ell} - \sum_{j \ne \ell} \nu_{\ell j} \tilde{R}_{j\ell}}{1 - \kappa_{\ell}} - \frac{\hat{\tilde{R}}_{\ell\ell} - \sum_{j \ne \ell} \hat{\nu}_{\ell j} \hat{\tilde{R}}_{j\ell}}{1 - \hat{\kappa}_{\ell}} \right| \\ &\le \left| \frac{\tilde{R}_{\ell\ell} - \sum_{j \ne \ell} \nu_{\ell j} \tilde{R}_{j\ell}}{1 - \kappa_{\ell}} - \frac{\hat{\tilde{R}}_{\ell\ell} - \sum_{j \ne \ell} \hat{\nu}_{\ell j} \hat{\tilde{R}}_{j\ell}}{1 - \kappa_{\ell}} \right| \\ &\quad + \left| \frac{\hat{\tilde{R}}_{\ell\ell} - \sum_{j \ne \ell} \hat{\nu}_{\ell j} \hat{\tilde{R}}_{j\ell}}{1 - \kappa_{\ell}} - \frac{\hat{\tilde{R}}_{\ell\ell} - \sum_{j \ne \ell} \hat{\nu}_{\ell j} \hat{\tilde{R}}_{j\ell}}{1 - \hat{\kappa}_{\ell}} \right| \end{aligned} $$
$$
\begin{align*}
&\le \frac{|\tilde{R}_{\ell\ell} - \hat{\tilde{R}}_{\ell\ell}| + \sum_{j \ne \ell} |\nu_{\ell j} \tilde{R}_{j\ell} - \hat{\nu}_{\ell j} \hat{\tilde{R}}_{j\ell}|}{1 - \kappa_{\ell}} + \left| \frac{1}{1 - \kappa_{\ell}} - \frac{1}{1 - \hat{\kappa}_{\ell}} \right| \\
&= \frac{|\tilde{R}_{\ell\ell} - \hat{\tilde{R}}_{\ell\ell}| + \sum_{j \ne \ell} \left( |\nu_{\ell j} \tilde{R}_{j\ell} - \hat{\nu}_{\ell j} \hat{\tilde{R}}_{j\ell} + \hat{\nu}_{\ell j} \tilde{R}_{j\ell} - \hat{\nu}_{\ell j} \hat{\tilde{R}}_{j\ell}| \right)}{1 - \kappa_{\ell}} \\
&\qquad + \left| \frac{1}{1 - \kappa_{\ell}} - \frac{1}{1 - \hat{\kappa}_{\ell}} \right| \\
&\le \frac{|\tilde{R}_{\ell\ell} - \hat{\tilde{R}}_{\ell\ell}| + \sum_{j \ne \ell} \left( |\nu_{\ell j} - \hat{\nu}_{\ell j}| + |\tilde{R}_{j\ell} - \hat{\tilde{R}}_{j\ell}| \right)}{1 - \kappa_{\ell}} + \left| \frac{1}{1 - \kappa_{\ell}} - \frac{1}{1 - \hat{\kappa}_{\ell}} \right|.
\end{align*}
$$

The VC inequality [1] implies that for any $\epsilon > 0$, $\sup_{f \in \mathcal{F}_{k(n)}} |R_{il}(f) - \hat{R}_{il}(f)| \le \epsilon$
with probability tending to 1, since (12) holds, and by our convention for multiclass
VC dimension. Noting that $\kappa_{\ell} < 1$ by Proposition 3, the other terms tend to zero in
probability by consistency of $\hat{\kappa}_{\ell}$ and the $\hat{\nu}_{\ell j}$. This completes the proof.

B.5 Proof of Theorem 1

Consider the decomposition into estimation and approximation errors,

$$
R(\hat{f}) - R^* = R(\hat{f}) - \inf_{f \in \mathcal{F}_{k(n)}} R(f) + \inf_{f \in \mathcal{F}_{k(n)}} R(f) - R^*.
$$

The approximation error converges to zero by **P3** and since $k(n) \to \infty$. To analyze
the estimation error, let $\epsilon > 0$. For each positive integer $k$, let $f_k^* \in \mathcal{F}_k$ such that
$R(f_k^*) \le \inf_{f \in \mathcal{F}_k} R(f) + \frac{\epsilon}{4}$. Then

$$
\begin{align*}
R(\hat{f}) - \inf_{f \in \mathcal{F}_{k(n)}} R(f) &= R(\hat{f}_{k(n)}) - \inf_{f \in \mathcal{F}_{k(n)}} R(f) \\
&\le R(\hat{f}_{k(n)}) - R(f_{k(n)}^*) + \frac{\epsilon}{4} \\
&\le \hat{R}(\hat{f}_{k(n)}) - \hat{R}(f_{k(n)}^*) + \frac{\epsilon}{2} \\
&\qquad \text{(with probability tending to 0, by Proposition 4)} \\
&\le \tau_{k(n)} + \frac{\epsilon}{2} \\
&\le \epsilon
\end{align*}
$$

where the last step holds for *n* sufficiently large. The result now follows.

References

[1] L. Devroye, L. Györfi, and G. Lugosi. *A Probabilistic Theory of Pattern Recognition*. Springer, 1996.