Ugo Louche
email: ugo.louche@lif.univ-mrs.fr

Liva Ralaivola
email: liva.ralaivola@lif.univ-mrs.fr

Unconfused ultraconservative multiclass algorithms

Keywords: Multiclass classification, Perceptron, Noisy labels, Confusion Matrix, Ultraconservative algorithms U. Louche Qarma, Lab

Introduction

Context. This paper deals with linear multiclass classification problems defined on an input space X (e.g., X = R d ) and a set of classes Q .

= {1, . . . , Q}.

In particular, we are interested in establishing the robustness of ultraconservative additive algorithms [START_REF] Crammer | Ultraconservative online algorithms for multiclass problems[END_REF] to label noise classification in the multiclass setting-in order to lighten notation, we will now refer to these algorithms as ultraconservative algorithms. We study whether it is possible to learn a linear predictor from a training set made of independent realizations of a pair (X, Y ) of random variables:

S . = {(x i , y i )} n i=1
where y i ∈ Q is a corrupted version of a true label, i.e. deterministically computed class, t(x i ) ∈ Q associated with x i , according to some concept t. The random noise process Y that corrupts the label to provide the y i 's given the x i 's is supposed uniform within each pair of classes, thus it is fully described by a confusion matrix C = (Cpq)p,q ∈ R Q×Q so that ∀x, C pt(x) = P Y (Y = p|x).

The goal that we would like to achieve is to provide a learning procedure able to deal with the confusion noise present in the training set S to give rise to a classifier h with small risk R(h) .

= P X∼D (h(X) = t(X)), D being the distribution according to which the x i 's are obtained. As we want to recover from the confusion noise, i.e., we want to achieve low risk on uncorrupted/nonnoisy data, we use the term unconfused to characterize the procedures we propose. Ultraconservative learning procedures are online learning algorithms that output linear classifiers. They display nice theoretical properties regarding their convergence in the case of linearly separable datasets, provided a sufficient separation margin is guaranteed (as formalized in Assumption 1 below). In turn, these convergence-related properties yield generalization guarantees about the quality of the predictor learned. We build upon these nice convergence properties to show that ultraconservative algorithms are robust to a confusion noise process, provided that: i) C is invertible and can be accessed, ii) the original dataset {(x i , t(x i ))} n i=1 is linearly separable. This paper is essentially devoted to proving how/why ultraconservative multiclass algorithms are indeed robust to such situations. To some extent, the results provided in the present contribution may be viewed as a generalization of the contributions on learning binary perceptrons under misclassification noise [START_REF] Blum | A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions[END_REF][START_REF] Bylander | Learning Linear Threshold Functions in the Presence of Classification Noise[END_REF].

Beside the theoretical questions raised by the learning setting considered, we may depict the following example of an actual learning scenario where learning from noisy data is relevant. This learning scenario will be further investigated from an empirical standpoint in the section devoted to numerical simulations (Section 4).

Example 1 One situation where coping with mislabelled data is required arises in (partially supervised) scenarios where labelling data is very expensive. Imagine a task of text categorization from a training set S = S ∪ Su, where S = {(x i , y i )} n i=1 is a set of n labelled training examples and Su = {x n+i } m i=1 is a set of m unlabelled vectors; in order to fall back to realistic training scenarios where more labelled data cannot be acquired, we may assume that n m. A possible three-stage strategy to learn a predictor is as follows: first learn a predictor f on S and estimate its confusion error C via a cross-validation procedure-f is assumed to make mistakes evenly over the class regions-, second, use the learned predictor to label all the data in Su to produce the labelled traning set S = {(x n+i , t n+i := f (x n+i ))} m i=1 and finally, learn a classifier f from S and the confusion information C.

This introductory example pertains to semi-supervised learning and this is only one possible learning scenario where the contribution we propose, UMA, might be of some use. Still, it is essential to understand right away that one key feature of UMA, which sets it apart from many contributions encountered in the realm of semi-supervised learning, is that we do provide theoretical bounds on the sample complexity and running time required by our algorithm to output an effective predictor.

The present paper is an extended version of [START_REF] Louche | Unconfused ultraconservative multiclass algorithms[END_REF]. Compared with the original paper, it provides a more detailed introduction of the tools used in the paper, a more thorough discussion on related work as well as more extensive numerical results (which confirm the relevance of our findings). A strategy to make use of kernels for nonlinear classification has also been added.

Contributions. Our main contribution is to show that it is both practically and theoretically possible to learn a multiclass classifier on noisy data if some information on the noise process is available. We propose a way to generate new points for which the true class is known. Hence we can iteratively populate a new unconfused dataset to learn from. This allows us to handle a massive amount of mislabelled data with only a very slight loss of accuracy. We embed our method into ultraconservative algorithms and provide a thorough analysis of it, in which we show that the strong theoretical guarantees that characterize the family of ultraconservative algorithms carry over to the noisy scenario.

Related Work. Learning from mislabelled data in an iterative manner has a longstanding history in the machine learning community. The first contributions on this topic, based on the Perceptron algorithm [START_REF] Minsky | Perceptrons: an Introduction to Computational Geometry[END_REF], are those of [START_REF] Bylander | Learning Linear Threshold Functions in the Presence of Classification Noise[END_REF][START_REF] Blum | A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions[END_REF][START_REF] Cohen | Learning Noisy Perceptrons by a Perceptron in Polynomial Time[END_REF], which promoted the idea utilized here that a sample average may be used to construct update vectors relevant to a Perceptron learning procedure. These first contributions were focused on the binary classification case and, for [START_REF] Blum | A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions[END_REF][START_REF] Cohen | Learning Noisy Perceptrons by a Perceptron in Polynomial Time[END_REF], tackled the specific problem of strong-polynomiality of the learning procedure in the probably approximately correct (PAC) framework [START_REF] Kearns | An Introduction to Computational Learning Theory[END_REF]. Later, [START_REF] Stempfel | Learning kernel perceptron on noisy data and random projections[END_REF] proposed a binary learning procedure making it possible to learn a kernel Perceptron in a noisy setting; an interesting feature of this work is the recourse to random projections in order to lower the capacity of the class of kernel-based classifiers. Meanwhile, many advances were witnessed in the realm of online multiclass learning procedures. In particular, [START_REF] Crammer | Ultraconservative online algorithms for multiclass problems[END_REF] proposed families of learning procedures subsuming the Perceptron algorithm, dedicated to tackle multiclass prediction problems. A sibling family of algorithms, the passive-aggressive online learning algorithms [START_REF] Crammer | Online passiveaggressive algorithms[END_REF], inspired both by the previous family and the idea of minimizing instantaneous losses, were designed to tackle various problems, among which multiclass linear classification. Sometimes, learning with partially labelled data might be viewed as a problem of learning with corrupted data (if, for example, all the unlabelled data are randomly or arbitrarily labelled) and it makes sense to mention the works [START_REF] Kakade | Efficient bandit algorithms for online multiclass prediction[END_REF] and [START_REF] Ralaivola | Applying multiclass bandit algorithms to call-type classification[END_REF] as distant relatives to the present work.

Organization of the paper. Section 2 formally states the setting we consider throughout this paper. Section 3 provides the details of our main contribution: the UMA algorithm and its detailed theoretical analysis. Section 4 presents numerical simulations that support the soundness of our approach.

2 Setting and Problem

Noisy Labels with Underlying Linear Concept

The probabilistic setting we consider hinges on the existence of two components. On the one hand, we assume an unknown (but fixed) probability distribution D on the input space X . = R d . On the other hand, we also assume the existence of a deterministic labelling function t : X → Q, where Q . = {1, . . . Q}, which associates a label t(x) to any input example x; in the Probably Approximately Correct (PAC) literature, t is sometimes referred to as a concept [START_REF] Kearns | An Introduction to Computational Learning Theory[END_REF][START_REF] Valiant | A theory of the learnable[END_REF].

In the present paper, we focus on learning linear classifiers, defined as follows.

Definition 1 (Linear classifiers) The linear classifier

f W : X → Q is a classifier that is associated with a set of vectors W = [w 1 • • • w Q ] ∈ R d×Q , which predicts the label f W (x) of any vector x ∈ X as f W (x) = argmax q∈Q wq, x . (1)
Additionally, without loss of generality, we suppose that

P X∼D ( X = 1) = 1,
where • is the Euclidean norm. This allows us to introduce the notion of margin.

Definition 2 (Margin of a linear classifier) Let c : S → Q be some fixed concept.

Let W = [w 1 • • • w Q ] ∈ R d×Q be a set of Q weight vectors.
Linear classifier f W is said to have margin θ > 0 with respect to c (and distribution D) if the following holds:

P X∼D ∃p = c(X) : w c(X) -wp, X ≤ θ = 0.
Note that if f W has margin θ > 0 with respect to c then

P X∼D (f W (X) = c(X)) = 0.
Equipped with this definition, we shall consider that the following assumption of linear separability with margin θ of concept t holds throughout.

Assumption 1 (Linear Separability of t with Margin θ.) There exist θ ≥ 0 and

W * = [w * 1 • • • w * Q ] ∈ R d×Q , with W * 2 F = 1 ( • F denotes the Frobenius norm) such
that f W * has margin θ with respect to the concept t.

In a conventional setting, one would be asked to learn a classifier f from a training set

Strue . = {(x i , t(x i ))} n i=1
made of n labelled pairs from X × Q such that the x i 's are independent realizations of a random variable X distributed according to D, with the objective of minimizing the true risk or misclassification error Rerror(f ) of f given by

Rerror(f ) . = P X∼D (f (X) = t(X)). (2)
In other words, the objective is for f to have a prediction behavior as close as possible to that of t. As announced in the introduction, there is however a little twist in the problem that we are going to tackle. Instead of having direct access to Strue, we assume that we only have access to a corrupted version

S . = {(x i , y i )} n i=1 (3)
where each y i is the realization of a random variable Y whose distribution agrees with the following assumption:

Assumption 2
The law D Y |X of Y is the same for all x ∈ X and its conditional distribution

P Y ∼D Y |X=x (Y |X = x) is fully summarized into a known confusion matrix C given by ∀x, C pt(x) . = P Y ∼D Y |X=x (Y = p|X = x) = P Y ∼D Y |X=x (Y = p|t(x) = q). (4)
Alternatively put, the noise process that corrupts the data is uniform within each class and its level does not depend on the precise location of x within the region that corresponds to class t(x). The noise process Y is both a) aggressive, as it does not only apply, as we may expect, to regions close to the class boundaries between classes and b) regular, as the mislabelling rate is piecewise constant. Nonetheless, this setting can account for many real-world problems as numerous noisy phenomena can be summarized by a simple confusion matrix. Moreover it has been proved [START_REF] Blum | A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions[END_REF] that robustness to classification noise generalizes robustness to monotonic noise where, for each class, the noise rate is a monotonically decreasing function of the distance to the class boundaries.

Remark 1 The confusion matrix C should not be mistaken with the matrix C of general term: Cij . = P X∼D X|Y =j (t(X) = i|Y = j) which is the class-conditional distribution of t(X) given Y . The problem of learning from a noisy training set and C is a different problem than the one we aim to solve. In particular, C can be used to define cost-sensitive losses rather directly whereas doing so with C is far less obvious. Anyhow, this second problem of learning from C is far from trivial and very interesting, and it falls way beyond the scope of the present work.

Finally, we assume the following from here on:

Assumption 3 C is invertible.
Note that this assumption is not as restrictive as it may appear. For instance, if we consider the learning setting depicted in Example 1 and implemented in the numerical simulations, then the confusion matrix obtained from the first predictor f is often diagonally dominant, i.e. the magnitudes of the diagonal entries are larger than the sum of the magnitudes of the entries in their corresponding rows, and C is therefore invertible. Generally speaking, the problems that we are interested in (i.e. problems where the true classes seems to be recoverable) tend to have invertible confusion matrix. It is most likely that invertibility is merely a sufficient condition on C that allows us to establish learnability in the sequel. Identifying less stringent conditions on C, or conditions termed in a different way-which would for instance be based on the condition number of C-for learnability to remain, is a research issue of its own that we leave for future investigations.

The setting we have just presented allows us to view S = {(x i , y i )} n i=1 as the realization of a random sample {(X i , Y i )} n i=1 , where each pair (X i , Y i ) is an independent copy of the random pair (X, Y ) of law D XY . = D X D X|Y .

Problem: Learning a Linear Classifier from Noisy Data

The problem we address is the learning of a classifier f from S and C so that the error rate

Rerror(f ) = P X∼D (f (X) = t(X))
of f is as small as possible: the usual goal of learning a classifier f with small risk is preserved, while now the training data is only made of corrupted labelled pairs. Building on Assumption 1, we may refine our learning objective by restricting ourselves to linear classifiers f W , for Definition 1). Our goal is thus to learn a relevant matrix W from S and the confusion matrix C. More precisely, we achieve risk minimization through classic additive methods and the core of this work is focused on computing noise-free update points such that the properties of said methods are unchanged.

W = [w 1 • • • w Q ] ∈ R d×Q (see
3 Uma: Unconfused Ultraconservative Multiclass Algorithm This section presents the main result of the paper, that is, the UMA procedure, which is a response to the problem posed above: UMA makes it possible to learn a multiclass linear predictor from S and the confusion information C. In addition to the algorithm itself, this section provides theoretical results regarding the convergence and sample complexity of UMA.

As UMA is a generalization of the ultraconservative additive online algorithms proposed in [START_REF] Crammer | Ultraconservative online algorithms for multiclass problems[END_REF] to the case of noisy labels, we first and foremost recall the essential features of this family of algorithms. The rest of the section is then devoted to the presentation and analysis of UMA.

A Brief Reminder on Ultraconservative Additive Algorithms

Ultraconservative additive online algorithms were introduced by Crammer et al. in [START_REF] Crammer | Ultraconservative online algorithms for multiclass problems[END_REF]. As already stated, these algorithms output multiclass linear predictors f W as in Definition 1 and their purpose is therefore to compute a set

W = [w 1 • • • w Q ] ∈ R d×Q of Q weight vectors from some training sample Strue = {(x i , t(x i ))} n i=1 .
To do so, they implement the procedure depicted in Algorithm 1, which centrally revolves around the identification of an error set and its simple update: when processing a training pair (x, y), they perform updates of the form wq ← wq + τqx, q = 1, . . . Q, whenever the error set E(x, y) defined as E(x,y) .

= {r ∈ Q\{y} : wr, xwy, x ≥ 0}

is not empty, with the constraint for the family {τq} q∈Q of step sizes to fulfill

   τy = 1 τr ≤ 0, if r ∈ E(x, y) τr = 0, otherwise and Q r=1 τr = 0. ( 6
)
Algorithm 1 Ultraconservative Additive algorithms [START_REF] Crammer | Ultraconservative online algorithms for multiclass problems[END_REF]. The term ultraconservative refers to the fact that only those prototype vectors wr which achieve a larger inner product wr, x than wy, x , that is, the vectors that can entail a prediction mistake when decision rule ( 1) is applied, may be affected by the update procedure. The term additive conveys the fact that the updates consist in modifying the weight vectors wr's by adding a portion of x to them (which is to be opposed to multiplicative update schemes). Again, as we only consider these additive types of updates in what follows, it will have to be implicitly understood even when not explicitly mentioned.

Input: Strue Output: W = w 1 , . . . , w Q and associated classifier f W (•) = argmax q wq, • Initialization: wq ← 0,
One of the main results regarding ultraconservative algorithms, which we extend in our learning scenario is the following.

Theorem 1 (Mistake bound for ultraconservative algorithms [START_REF] Crammer | Ultraconservative online algorithms for multiclass problems[END_REF].) Suppose that concept t is in accordance with Assumption 1. The number of mistakes/updates made by one pass over S by any ultraconservative procedure is upper-bounded by 2/θ 2 .

This result is essentially a generalization of the well-known Block-Novikoff theorem [START_REF] Block | The perceptron: a model for brain functioning[END_REF][START_REF] Novikoff | On convergence proofs for perceptrons[END_REF], which establishes a mistake bound for the Perceptron algorithm (an ultraconservative algorithm itself).

Main Result and High Level Justification

This section presents our main contribution, UMA, a theoretically grounded noisetolerant multiclass algorithm depicted in Algorithm 2. UMA learns and outputs a matrix

W = [w 1 • • • w Q ] ∈ R d×Q from a noisy training set S to produce the associated linear classifier f W (•) = argmax q wq, • (7)
by iteratively updating the wq's, whilst maintaining q wq = 0 throughout the learning process. As a new member of multiclass additive algorithms, we may readily recognize in step 8 through step 10 of Algorithm 2 the generic step sizes {τq} q∈Q promoted by ultraconservative algorithms (see Algorithm 1). An important feature of UMA is that it only uses information provided by S and does not make assumption on the accessibility to the noise-free dataset Strue: the incurred pivotal difference with regular ultraconservative algorithms is that the update points used are now Algorithm 2 UMA: Unconfused Ultraconservative Multiclass Algorithm.

Input: S = {(x i , y i )} n i=1 , confusion matrix C ∈ R Q×Q , and α > 0 Output: W = [w 1 , . . . , w K ] and classifier f W (•) = argmax q wq, • 1: w k ← 0, ∀k ∈ Q 2: repeat 3:
select p and q 4: compute set A α p as

A α p ← {x|x ∈ S, wp, x -w k , x ≥ α, ∀k = p} 5: for k = 1, . . . , Q, compute γ p k as γ p k ← 1 n n i=1 I{y i = k}I x i ∈ A α p x i , ∀k ∈ Q 6: form Γ p ∈ R Q×d as Γ p ← γ p 1 • • • γ p Q , 7:
compute the update vector zpq according to ([M ]q refers to the qth row of matrix M )

zpq ← ([C -1 Γ p ]q) , 8:
compute the error set E α (zpq, q) as E α (zpq, q) ← {r ∈ Q\{q} : wr, zpqwq, zpq ≥ α}

9: if E α (zpq, q) = ∅ then 10:
compute some ultraconservative update steps τ 1 , . . . , τ Q such that: end if 13: until zpq is too small the computed (line 4 through line 7) zpq vectors instead of the x i 's. Establishing that under some conditions UMA stops and provides a classifier with small risk when those update points are used is the purpose of the following subsections; we will also discuss the unspecified step 3, dealing with the selection step.

   τq = 1 τr ≤ 0, ∀r ∈ E α (zpq, q) τr = 0,
For the impatient reader, we may already leak some of the ingredients we use to prove the relevance of our procedure. Theorem 1, which shows the convergence of ultraconservative algorithms, rests on the analysis of the updates made when training examples are misclassified by the current classifier. The conveyed message is therefore that examples that are erred upon are central to the convergence analysis. It turns out that steps 4 through 7 of UMA (cf. Algorithm 2) construct a point zpq that is, with high probabilty, mistaken on. More precisely, the true class t(zpq) of zpq is q and it is predicted to be of class p by the current classifier; at the same time, these update vectors are guaranteed to realize a positive margin condition with respect to W * : w * q , zpq > w * k , zpq for all k = q. The ultraconservative feature of the algorithm is carried by step 8 and step 10, which make it possible to update any prototype vector wr with r = q having an inner product wr, zpq with zpq larger than wq, zpq (which should be the largest if a correct prediction were made). The reason why we have results 'with high probability' is because the zpq's are sample-based estimates of update vectors known to be of class q but predicted as being of class p, with p = q; computing the accuracy of the sample estimates is one of the important exercises of what follows. A control on the accuracy makes it possible for us to then establish the convergence of the proposed algorithm.

With High Probability, zpq is a Mistake with Positive Margin

Here, we prove that the update vector zpq given in step 7 is, with high probability, a point on which the current classifier errs.

Proposition 1 Let W = [w 1 • • • w Q ] ∈ R d×Q
and α > 0 be fixed. Let A α p be defined as in step 4 of Algorithm 2, i.e:

A α p . = {x|x ∈ S, wp, x -w k , x ≥ α, ∀k = p} . ( 8
)
For k ∈ Q, p = k, consider the random variable γ p k (γ p k in step 5 of Algorithm 2 is a realization of this variable, hence the overloading of notation γ p k ):

γ p k . = 1 n i I{Y i = k}I X i ∈ A α p X i .
The following holds, for all k ∈ Q:

E S γ p k = E {(Xi,Yi)} n i=1 γ p k = Q q=1 C kq µ p q , (9)
where

µ p q . = E D X I{t(X) = q}I X ∈ A α p X . ( 10
) Proof Let us compute E D XY {I{Y = k}I X ∈ A α p X }: E D XY {I{Y = k}I X ∈ A α p X } = X Q q=1 I{q = k}I x ∈ A α p x P Y (Y = q|X = x)dD X (x) = X I x ∈ A α p x P Y (Y = k|X = x)dD X (x) = X I x ∈ A α p x C kt(x) dD X (x) (cf. (4)) = X Q q=1 I{t(x) = q}I x ∈ A α p x C kq dD X (x) = Q q=1 C kq X I{t(x) = q}I x ∈ A α p x dD X (x) = Q q=1 C kq µ p q ,
where the last line comes from the fact that the classes are non-overlapping. The n pairs (X i , Y i ) being identically and independently distributed gives the result.

Intuitively, µ p q must be seen as an example of class p which is erroneously predicted as being of class q. Such an example is precisely what we are looking for to update the current classifier; as expecations cannot be computed, the estimate zpq of µ p q is used instead of µ p q .

Proposition 2

Let W = [w 1 • • • w Q ] ∈ R d×Q and α ≥ 0 be fixed. For p, q ∈ Q, p = q, zpq ∈ R d is such that E D XY zpq = µ p q (11) w * q , µ p q -w * k , µ p q ≥ θ, ∀k = q, ( 12
)
wp, µ p q -w k , µ p q ≥ α, ∀k = p. ( 13
)
(Normally, we should consider the transpose of µ p q , but since we deal with vectors of R d -and not matrices-we abuse the notation and omit the transpose.)

This means that i) t(µ p q ) = q, i.e. the 'true' class of µ p q is q;

ii) and f W (µ p q ) = p; µ p q is therefore misclassified by the current classifier f W .

Proof According to Proposition 1,

E D XY Γ p = E D XY            γ p 1 . . . γ p Q            =     E D XY γ p 1 . . . E D XY γ p Q     =     Q q=1 C 1q µ p 1 . . . Q q=1 C Qq µ p Q     = C     µ p 1 . . . µ p Q     .
Hence, inverting C and extracting the qth of the resulting matrix equality gives that E {zpq} = µ p q . Equation ( 12) is obtained thanks to Assumption 1 combined with [START_REF] Crammer | Ultraconservative online algorithms for multiclass problems[END_REF] and the linearity of the expectation. Equation ( 13) is obtained thanks to the definition (8) of A α p (made of points that are predicted to be of class p) and the linearity of the expectation.

The attentive reader may notice that Proposition 2 or, equivalently, step 7, is precisely the reason for requiring C to be invertible, as the computation of zpq hinges on the resolution of a system of equations based on C. Proposition 3 Let ε > 0 and δ ∈ (0; 1]. There exists a number

n 0 (ε, δ, d, Q) = O 1 ε 2 ln 1 δ + ln Q + d ln 1
ε such that if the number of training samples is greater than n 0 then, with high probability

w * q , zpq -w * k , zpq ≥ θ -ε (14) wp, zpq -w k , zpq ≥ 0, ∀k = p. ( 15
)
Proof The existence of n 0 relies on pseudo-dimension arguments. We defer this part of the proof to Appendix A and we will directly assume here that if n ≥ n 0 , then, with probability 1 -δ for any W , zpq.

wpwq, zpqwpwq, µ p q ≤ ε. [START_REF] Drineas | On the Nyström method for approximating a gram matrix for improved kernel-based learning[END_REF] Proving ( 14) then proceeds by observing that

w * q -w * k , zpq = w * q -w * k , µ p q + w * q -w * k , zpq -µ p q
bounding the first part using Proposition 2:

w * q -w * k , µ p q ≥ θ
and the second one with [START_REF] Drineas | On the Nyström method for approximating a gram matrix for improved kernel-based learning[END_REF]. A similar reasoning allows us to get (15) by setting

α . = ε in A α p .
This last proposition essentially says that the update vectors zpq that we compute are, with high probability, erred upon and realize a margin condition θ -ε.

Note that α is needed to cope with the imprecision incurred by the use of empirical estimates. Indeed, we can only approximate wp, zpqw k , zpq in [START_REF] Drineas | Fast Monte Carlo algorithms for matrices ii: computing a low rank approximation to a matrix[END_REF] up to a precision of ε. Thus for the result to hold we need to have wp, µ p qw k , µ p q ≥ ε which is obtained from ( 13) when α = ε. In practice, this just says that the points used in the computation of zpq are at a distance at least α from any decision boundaries.

Remark 2 It is important to understand that the parameter α helps us derive sample complexity results by allowing us to retrieve a linearly separable training dataset with positive margin from the noisy dataset. The theoretical results we prove hold for any such α > 0 parameter and the smaller this parameter, the larger the sample complexity, i.e., the harder it is for the algorithm to take advantage of a training samples that meets the sample complexity requirements. In other words, the smaller α, the less likely it is for UMA to succeed; yet, as shown in the experiments, where we use α = 0, UMA continues to perform quite well.

Convergence and Stopping Criterion

We arrive at our main result, which provides both convergence and a stopping criterion.

Proposition 4 Under Assumptions 1, 2 and 3 there exists a number n, polynomial in d, 1/θ, Q, 1/δ, such that if the training sample is of size at least n, then, with high probability (1 -δ), UMA makes at most O(1/θ 2 ) updates.

Proof Let Sz the set of all the update vectors zpq generated during the execution of UMA and labeled with their true class q. Observe that, in this context, UMA (Alg.

2) behaves like a regular ultraconservative algorithm run on Sz . Namely: a) lines 4 through 7 compute a new point in Sz , and b) lines 8 through 10 perform an ultraconservative update step.

From Proposition 3, we know that with high probability, w * is a classifier with positive margin θ -ε on Sz and it comes from Theorem 1 that UMA does not make more than O(1/θ 2 ) mistakes on such dataset.

Because, by construction, we have that with high probability each element of Sz is erred upon then |Sz | ∈ O(1/θ 2 ); that means that, with high probability, UMA does not make more than O(1/θ 2 ) updates.

All in all, after O(1/θ 2 ) updates, there is a high probability that we are not able to construct examples on which UMA makes a mistake or, equivalently, the conditional misclassification errors P(f W (X) = p|Y = q) are all small. Even though UMA operates in a batch setting, it 'internally' simulates the execution of an online algorithm that encounters a new training point (zpq ∈ Sz ) at each time step. To more precisely see how UMA can be seen as an online algorithm, it suffices to imagine it be run in a way where each vector update is made after a chunk of n (where n is as in Proposition 4) training data has been encountered and used to compute the next element of Sz . Repeating this process O(1/θ 2 ) times then guarantees convergence with high probability. Note that, in this scenario, UMA requires n = O(n/θ 2 ) data to converge which might be far more than the sample complexity exhibited in Proposition 4. Nonetheless, n still remains polynomial in d, 1/θ, Q and 1/δ. For more detail on this (online to batch conversion) approach, we refer the interested readers to [START_REF] Blum | A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions[END_REF].

Selecting p and q

So far, the question of selecting good pairs of values p and q to perform updates has been left unanswered. Indeed, our results hold for any pair (p, q) and convergence is guaranteed even when p and q are arbitrarily selected as long as zpq is not 0. Nonetheless, it is reasonable to use heuristics for selecting p and q with the hope that it might improve the practical convergence speed.

On the one hand, we may focus on the pairs (p, q) for which the empirical misclassification rate

PX∼S {f W (X) = t(X)} . = 1 n n i=1 I f W (x i ) = t(x j ) (17)
is the highest (X ∼ S means that X is randomly drawn from the uniform distribution of law x → n -1 n i=1 I{x = x i } defined with respect to training set S = {(x i , y i )} n i=1 ). We want to favor those pairs (p, q) because, i) the induced update may lead to a greater reduction of the error and ii) more importantly, because zpq may be more reliable, as A α p will be bigger. On the other hand, recent advances in the passive aggressive literature [START_REF] Ralaivola | Confusion-based online learning and a passive-aggressive scheme[END_REF] have emphasized the importance of minimizing the empirical confusion rate, given for a pair (p, q) by the quantity

PX∼S {f W (X) = p|t(X) = q} . = 1 nq n i=1 I{t(x i ) = q, f W (x i ) = p}, (18)
where

nq . = n i=1 I{t(x i ) = q}.
This approach is especially worthy when dealing with imbalanced classes and one might want to optimize the selection of (p, q) with respect to the confusion rate.

Obviously, since the true labels in the training data cannot be accessed, neither of the quantities defined in ( 17) and ( 18) can be computed. Using a result provided in [START_REF] Blum | A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions[END_REF], which states that the norm of an update vector computed as zpq directly provides an estimate of (17), we devise two possible strategies for selecting (p, q): (p, q)error .

= argmax

(p,q) zpq (19) (p, q) conf . = argmax (p,q) zpq πq , ( 20
)
where πq is the estimated proportion of examples of true class q in the training sample. In a way similar to the computation of zpq in Algorithm 2, πq may be estimated as follows: πq = 1

n [C -1 ŷ]q,
where ŷ ∈ R Q is the vector containing the number of examples from S having noisy labels 1, . . . , Q, respectively.

The second selection criterion is intended to normalize the number of errors with respect to the proportions of different classes and aims at being robust to imbalanced data. Our goal here is to provide a way to take into account the class distribution for the selection of (p, q). Note that this might be a first step towards transforming UMA into an algorithm for minimizing the confusion risk, even though additional (and significant) work is required to provably provide UMA with this feature.

On a final note, we remark that (p, q) conf requires additional precautions when used: when (p, q)error is implemented, zpq is guaranteed to be the update vector of maximum norm among all possible update vectors, whereas this no longer holds true when (p, q) conf is used and if zpq is close to 0 then there may exist another possibly more informative-from the standpoint of convergence speed-update vector z p q for some (p , q ) = (p, q).

UMA and Kernels

Thus far, we have only considered the situation where linear classifiers are learned. There are however many learning problems that cannot be handled effectively without going beyond linear classification. A popular strategy to deal with such a situation is obviously to make use of kernels [START_REF] Schölkopf | Learning with Kernels, Support Vector Machines, Regularization, Optimization and Beyond[END_REF]. In this direction, there are (at least) two paths that can be taken. The first one is to revisit UMA and provide a kernelized algorithm based on a dual representation of the weight vectors, as is done with the kernel Perceptron (see [START_REF] Cristianini | An Introduction to Support Vector Machines and other Kernel-Based Learning Methods[END_REF]) or its close cousins (see, e.g. [START_REF] Friess | The Kernel-Adatron Algorithm: a Fast and Simple Learning Procedure for Support Vector Machines[END_REF][START_REF] Dekel | The forgetron: A kernel-based perceptron on a fixed budget[END_REF][START_REF] Freund | Large Margin Classification Using the Perceptron Algorithm[END_REF]). Doing so would entail the question of finding sparse expansions of the weight vectors with respect to the training data in order to contain the prediction time and to derive generalization guarantees based on such sparsity: this is an interesting and ambitious research program on its own. A second strategy, which we make use of in the numerical simulations, is simply to build upon the idea of Kernel Projection Machines [START_REF] Blanchard | Finite-dimensional projection for classification and statistical learning[END_REF][START_REF] Takerkart | MKPM: a multiclass extension to the kernel projection machine[END_REF]: first, perform a Kernel Principal Component Analysis (shorthanded as kernel-PCA afterwards) with D principal axes, second, project the data onto the principal D-dimensional subspace and, finally, run UMA on the obtained data. The availability of numerous methods to efficiently extract the principal subspaces (or approximation thereof) [START_REF] Bach | Kernel Independent Component Analysis[END_REF][START_REF] Drineas | Fast Monte Carlo algorithms for matrices ii: computing a low rank approximation to a matrix[END_REF][START_REF] Drineas | On the Nyström method for approximating a gram matrix for improved kernel-based learning[END_REF][START_REF] Stempfel | Learning kernel perceptron on noisy data and random projections[END_REF][START_REF] Williams | Using the Nyström Method to Speed Up Kernel Machines[END_REF] makes this path a viable strategy to render UMA usable for nonlinearly separable concepts. This explains why we decided to use this strategy in the present paper.

Experiments

In this section, we present results from numerical simulations of our approach and we discuss different practical aspects of UMA. The ultraconservative step sizes retained are those corresponding to a regular Perceptron: τp = -1 and τq = +1, the other values of τr being equal to 0. Section 4.1 discusses robustness results, based on simulations conducted on synthetic data while Section 4.2 takes it a step further and evaluates our algorithm on real data, with a realistic noise process related to Example 1 (cf. Section 1).

We essentially use what we call the confusion rate as a performance measure, which is : 1

√ Q C F
Where C F is the Frobenius norm of the confusion matrix C computed on a test set Stest (independent from the training set), i.e.:

C 2 F = i,j C 2 ij , with Cpq . =    0 if p = q, xi∈Stest I{ y i = p and t i = q} xi∈Stest I{t i = q} otherwise,
with y i the label predicted for the test instance x i by the learned predictor. C is much akin to a recall matrix, and the 1/ √ Q factor ensure that the confusion rate is comprised within 0 and 1.

Toy dataset

We use a 10-class dataset with a total of roughly 1, 000 2-dimensional examples uniformly distributed according to U, which is the uniform distribution over the unit circle centered at the origin. Labelling is achieved according to (1) given a set of 10 weight vectors w 1 , . . . , w 10 , which are also randomly generated according to U; all these weight vectors have therefore norm 1. A margin θ = 0.025 is enforced in the generated data by removing examples that are too close to the decision boundaries-practically, with this value of θ, the case where three classes are so close to each other that no training example from one of the classes remained after enforcing the margin never occurred.

The learned classifiers are tested against a dataset of 10, 000 points that are distributed according to the training distribution. The results reported in the tables and graphics are averaged over 10 runs.

The noise is generated from the sole confusion matrix. This situation can be tough to handle and is rarely met with real data but we stick with it as it is a good example of a worst-case scenario.

Robustness to noise. We first (Fig. 1(a)) evaluate the robustness to noise of UMA by running our algorithm with various confusion matrices. We uniformly draw a reference nonnegative square matrix M , the rows of M are then normalized, i.e. each entry of M is divided by the sum of the elements of its row, so M is a stochastic matrix. If M is not invertible it is rejected and we draw a new matrix until we have an invertible one. Then, we define N such that N = (M -I)/10, where I is the identity matrix of order Q; typically N has nonpositive diagonal entries and nonnegative off-diagonal coefficients. We will use N to parametrize a family of confusion matrices that have their most dominant coefficient to move from their diagonal to their off-diagonal parts. Namely, we run UMA 20 times with confusion matrices C ∈ {C i .

= Ω(I + iN )} 20 i=1 , where Ω is a matrix operator which outputs a (row-)stochastic matrix: when applied on matrix A, Ω replaces the negative elements of A by zeros and it normalizes the rows of the obtained matrix; note that i = 10 corresponds to the case where C = M . Equivalently, one can think of C i as the weighted average between I and Ω(N ) where I has a constant weight of 1 and Ω(N ) is weighted by i. Note that, after some point, further increasing i has little effect on C i as it eventually converges to Ω(N ). Figure 1(a) plots our results against the Frobenius norm of the diagonal-free confusion matrix C, that is: Cdiag(C) F where diag(C) denotes the diagonal matrix with the same diagonal values as C. For the sake of comparison, we also have run UMA with a fixed confusion matrix C = I on the same data. This amounts to running a Perceptron through the data multiple times and it allows us to have a baseline for measuring the improvement induced by the use of the confusion matrix.

Robustness to the incorrect estimation of the confusion matrix. The second experiment (Fig. 1(b)) evaluates the robustness of UMA to the use of a confusion matrix that is not exactly the confusion matrix that describes the noise process corrupting the data; this will allow us to measure the extent to which a confusion matrix (inaccurately) estimated from the training data can be dealt with by UMA. Using the same notation as before, and the same idea of generating a random stochastic reference matrix M , we proceed as follows: we use the given matrix M to corrupt the noise-free dataset and then, each confusion matrix from the family {C i } 20 i=1 is fed to UMA as if it were the confusion matrix governing the noise process. We introduce the notion of approximation factor ρ as ρ(i) .

= 1 -i/10, so that ρ takes values in the set {-1, -0.9, . . . , 0.9}. As reference, the limit case where ρ = 1-that is, i = 0-corresponds to the case where UMA is fed with the identity matrix I, effectively being oblivious of any noise in the training set. More generally, the values of C are being shifted away from the diagonal as ρ decreases, the equilibrium point being ρ = 0 where C is equal to the true confusion matrix M . Consequently, a positive (resp. negative) approximation factor means that the noise is underestimated (resp. overestimated), in the sense that the noise process described by C would corrupt a lower (resp. higher) fraction of labels from each class than the true noise process applied on the training set, and corresponding to M . Figure 1(b) plots the confusion rate against this approximation factor.

On Figure 1(a) we observe that UMA clearly provides improvement over the Perceptron algorithm for every noise level tested, as it achieves lower confusion rates. Nonetheless, its performance degrades as the noise level increases, going from a confusion rate of 0.5 for small noise levels-that is, when Cdiag(C) F is small-to roughly 2.25 when the noise is the strongest. Comparatively, the Per- ceptron algorithm follows the same trend, but with higher confusion rate, ranging from 1.7 to 2.75.

The second simulation (Fig. 1(b)) points out that, in addition to being robust to the noise process itself, UMA is also robust to underestimated (approximation factor ρ > 0) noise levels, but not to overestimated (approximation factor ρ < 0) noise levels. Unsurprisingly, the best confusion rate corresponds to an approximation factor of 0, which means that UMA is using the true confusion matrix and can achieve a confusion rate as low as 1.8. There is a clear gap between positive and negative approximation factors, the former yielding confusion rates around 2.6 while the latter's are slightly lower, around 2.15. From these observations, it is clear that the approximation factor has a major influence on the performances of UMA.

Real data

Experimental Protocol

In addition to the results on synthetic data, we also perform simulations in a realistic learning scenario. In this section we are going to assume that labelling examples is very expensive and we implement the strategy evoked in Example 1. More precisely, for a given dataset S, proceed as follows:

1. Ask for a small number m of examples for each of the Q classes. 2. Learn a rough classifier1 g from these Q × m points. 3. Estimate the confusion C of g on a small labelled subset S conf of S. 4. Predict the missing labels y of S using g; thus, y is a sequence of noisy labels. 5. Learn the final classifier f UMA from S, y, C and measure its error rate.

One might wonder why we do not simply sample a very small portion of S in the first step. The reason is that in the case of very uneven classes proportions some of the classes may be missing in this first sampling. This is problematic when estimating C as it leads to a non-invertible confusion matrix. Moreover, the purpose of g is only to provide a baseline for the computation of y, hence tweaking the class (im)balance in this step is not a problem.

In order to put our results into perspective, we compare them with results obtained from various algorithms. This allows us to give a precise idea of the benefits and limitations of UMA. Namely, we learn four additional classifiers: fy is a regular Perceptron learned on S labelled with noisy labels y, f conf and f full are trained with the correctly labelled training sets S conf and S respectively and, lastly, f S3VM is a classifier produced by a multiclass semi-supervised SVM algorithm (S3VM, [START_REF] Bennett | Semi-supervised support vector machines[END_REF]) run on S where only the labels of S conf are provided. The performances achieved by fy and f full provide bounds for UMA's error rates: on the one hand, fy corresponds to a worst-case situation, as we simply ignore the confusion matrix and use the regular Perceptron instead-arguably, UMA should perform better than this-; on the other hand, f full represents the best-case scenario for learning, when all the correct labels are available-the performance of f full should always top that of UMA (and the performances of other classifiers). The last two classifiers, f conf and f S3VM , provide us with objective comparison measures. They are learned from the same data as UMA but use them differently: f conf is learned from the reduced training set S conf and f S3VM is output by a semi-supervised learning strategy that infers both f S3VM and the missing labels of S and it totally ignores the predictions y made by g. Note that according to the learning scenario we implement, we assume C to be estimated from raw data. This might not always be the case with real-world problems and C might be easier and/or less expensive to get than raw data; for instance, it might be deduced from expert knowledge on the studied domain. In that case, f conf and f S3VM may suffer from not taking full advantage of the accurate information about the confusion.

Datasets

Our simulations are conducted on three different datasets. Each one with different features. For the sake of reproducibility, we used datasets that can be easily found on the UCI Machine learning repository [START_REF] Bache | UCI machine learning repository[END_REF]. Moreover, these datasets correspond to tasks for which generating a complete, labelled, training set is typically costly because of the necessity of human supervision and subject to classification noise. The datasets used and their main features are as follows.

Optical Recognition of Handwritten Digits. This well-known dataset is composed of 8 × 8 grey-level images of handwritten digits, ranging from 0 to 9. The dataset is composed of 3, 823 images of 64 features for training, and 1, 797 for the test phase. We set m to 10 for this dataset, which means that g is learned from 100 examples only. S conf is a sampling of 5% of S. The classes are evenly distributed (see Figure 2(a)). We handle the nonlinearity through the use of a Gaussian kernel-PCA (see section 3.6) to project the data onto a feature space of dimension 640.

Letter Recognition. The Letter Recognition dataset is another well-known pattern recognition dataset. The images of the letters are summarized into a vector of 16 attributes, which correspond to various primitives computed on the raw data. With 20, 000 examples, this dataset is much larger than the previous one. As for the Handwritten Digits dataset, the examples are evenly spread across the 26 classes (see Figure 2(b)). We uniformly select 15, 000 examples for training and the remaining 5, 000 are used for test. We set m to 50 as it seems that smaller values do not yield usable confusion matrices. We again sample 5% of the dataset to form S conf and use, as before, a Gaussian kernel-based Kernel-PCA to (nonlinearly) expand the dimension of the data to 1, 600.

Reuters. The Reuters dataset is a nearly linearly-separable document categorization dataset of more than 300, 000 instances of nearly 47, 000 features each. For size reasons we restrict ourselves to roughly 15, 000 examples for training, and 15, 000 other for test. It occurs that some classes are so underrepresented that they are flooded by the noise process and/or do not appear in S conf , which may lead to a non-invertible confusion matrix. We therefore restrict the dataset to the 9 largest classes. One might wonder whether doing so erases class imbalance. This is not the case as, even this way, the least represented class accounts for roughly 500 examples while this number reaches nearly 4, 000 for the most represented one (see Figure 2(c)). Actually, these 9 classes represent more than 70 percent of the dataset, reducing the training and test sets to approximately 11, 000 examples each. We do not use any kernel for this dataset, the data being already near to linearly-separable. Also, we sample S conf on 5% of the training set and we set m = 20.

Results

Table 1 presents the misclassification error rates averaged on 10 runs. Keep in mind that we have not conducted a very thorough optimization of the hyper-parameters as the point here is essentially to compare UMA with the other algorithms. Additionally, we also report the error rates of f S3VM when trained on the kernelized data with all dimensions, that is the kernelized data before we project them onto their D principal components. Because the projection step is indeed unbecessary with S3VM, this will give us insights on the error due to the Kernel-PCA step. Comparing the first and the last columns of Table 1, it appears that UMA always induces a slight performance gain, i.e. a decrease of the misclassification rate, with respect to fy. From the second and third columns of Table 1, it is clear that the reduced number of examples available to f conf induces a drastic increase in the misclassification rate with respect to f full which is allowed to use the totality of the dataset during the training phase.

Comparing UMA and f conf in Table 1 (fifth and second columns), we observe that UMA achieves lower misclassification rates on the Handwritten Digits and Letter Recognition datasets but a higher misclassification rate on Reuters. Although this is likely related to the strong class imbalance in the dataset. Indeed, some classes are overly represented, accounting for the vast majority of the whole dataset (see Fig. 2(c)). Because S conf is uniformly sampled from the main dataset, f conf is trained with a lot of examples from the overrepresented classes and therefore it is very effective, in the sense that it achieves a low misclassification rate, for these overrepresented classes; this, in turn, induces a (global) low misclassification rate, as possibly high misclassification rates on underrepresented classes are countervailed by theirs accounting for a small portion of the data. On the other hand, because of this disparity in class representation, the slightest error in the confusion matrix, granted it involves one of these overrepresented classes, may lead to a significant increase of the misclassification rate. In this regard, UMA is strongly disadvantaged with respect to f conf on the Reuters dataset and it is the cause of the reported results.

The error rates for the S3VM and UMA classifiers are close for the Reuters and Handwritten Digits datasets whereas UMA has a clear advantage on the Letter Recognition problem. On the other hand, note that we used the S3VM method in conjunction with a Kernel-PCA for the sake of comparison with UMA in its kernelized form. The last column of Table 1 tends to confirm that this projection strategy increase the error rate of f S3VM . Also, reminds that the value of m does not impact the performances of f S3VM but has a significant effect on UMA, even though UMA never uses these labelled data. For instance, on the Reuters datasets, increasing m from 20 to 70 reduces UMA's error rate by nearly 0.1 (see the error rates of Fig. 3 (m = 70) when the size of labelled data is close to 550, that is 5% of the whole dataset). Despite our efforts to keep m as small as possible, we could not go under m = 50 for the Letter Recognition dataset without compromising the invertibility of the confusion matrix. The simple fact that an unusually high number of examples are required to simply learn a rough classifier asserts the complexity of this dataset. Moreover, the fact that fy also outperforms f S3VM implies that the labels fed to UMA are already mostly correct, and, according to our working assumptions, this is the most favorable setting for UMA.

Nonetheless, the disparities between UMA and f conf deserve more attention. Indeed, the same data are being used by both algorithms, and one could expect more closeness in the results. To get a better insight on what is occurring, we have reported the evolution of the error rate of these two algorithms with respect to the sampling size of S conf in Figure 3. We can see that UMA is unaffected by the size of the sample, essentially ignoring the possible errors in the confusion matrix on small samples. This reinforces our previous results showing that UMA is robust to errors in the confusion matrix. On the other hand, with the addition of more samples, the refinement of the confusion matrix does not allow UMA to compete with the value of additional (correctly) labelled data and eventually, when the size of S conf grows, f conf performs better than UMA. This points towards the idea that the aggregated nature of the confusion matrix incurs some loss of relevant information for the classification task at hand, and that a more accurate estimate of the confusion matrix, as induced by, e.g., the use of larger S conf , may not compensate for the information provided by additional raw data. Building on this observation, we go a step further and replicate this experiment for all of the three datasets; only this time we track the performances of f S3VM instead. The results are plotted on Figure 4. For the three datasets, we observe the same behavior as before. Namely, UMA is able to maintain a low error rate even with a very small size of S conf . On the other hand, UMA does not benefit as much as other methods from a large pool of labelled examples. In this case, UMA quickly stabilizes while, to the contrary, the S3VM method starts at a fairly high error rate and keeps improving as more labelled examples are available.

Beyond this, it is important to recall that UMA never uses the labels of S conf (those are only used to estimate the confusion matrix, not the classifier-refer to Section 4.2.1 for the detailed learning protocol). While refining the estimation of C is undoubtedly useful, a direction toward substantial performance gains should revolve around the combination of both this refined estimation of C and the use of the correctly labelled training set S conf . This is a research subject on its own that we leave for future work.

As one might expect, the confusion-based strategy performs better than the error-based strategy when the confusion rate is retained as a performance measure, while the converse holds when using the error rate. This observation motivates us to thoroughly study the confusion-based strategy in a near future as being able to propose methods robust to class imbalance is a particularly interesting challenge of multiclass classification.

The plateau reached around the 30th iteration may be puzzling, since the studied dataset presents no positive margin and convergence is therefore not guaranteed. One possible explanation for this is to see the Reuters dataset as linearly separable problem corrupted by the effect of a noise process, which we call the intrinsic noise process that has structural features 'compatible' with the classification noise. By this, we mean that there must be features of the intrinsic noise such that, when additional classification noise is added, the resulting noise that characterizes the data is similar to a classification noise, or at least, to a noise that can be naturally handled by UMA. Finding out the family of noise processes that can be combined with the classification noise-or, more generally, the family of noise processes themselves-without hindering the effectiveness of UMA is one research direction that we aim to explore in a near future.

Conclusion

In this paper, we have proposed a new algorithm, UMA-for Unconfused Multiclass Additive algorithm-to cope with noisy training examples in multiclass linear problems. As its name indicates, it is a learning procedure that extends the (ultraconservative) additive multiclass algorithms proposed by [START_REF] Crammer | Ultraconservative online algorithms for multiclass problems[END_REF]; to handle the noisy datasets, it only requires the information about the confusion matrix that characterizes the mislabelling process. This is, to the best of our knowledge, the first time the confusion matrix is used as a way to handle noisy label in multiclass problems.

One of the core ideas behind UMA, namely, the computation of the update vector zpq, is not tied to the additive update scheme. Thus, as long as the assumption of linear separability holds, the very same idea can be used to render a wide variety of algorithms robust to noise by iteratively generating a noise-free training set with the consecutive values of zpq. Although, every computation of a new zpq requires learning a new classifier to start with. This may eventually incur prohibitive computational costs when applied to batch methods (as opposed to online methods) which are designed to process the entirety of the dataset at once. 2 UMA takes advantage of the online scheme of additive algorithms and avoids this problem completely. Moreover, additive algorithms are designed to directly handle multiclass problem rather than having recourse to a bi-class mapping. The end-results of this are tightened theoretical guarantees and a convergence rate that does not depend of Q, the number of classes. Besides, UMA can be directly used with any additive algorithms, allowing to handle noise with multiple methods without further computational burden.

2 Nonetheless, from a purely theoretical point of view, UMA makes at most O(1/θ 2 ) mistakes (see proposition 4) and computing zpq can be done in O(n) time. Therefore, polynomial batch methods do not suffer much from this as their overall execution time is still polynomial.

While we provide sample complexity analysis, it should be noted that a tighter bound can be derived with specific multiclass tools, such as the Natarajan's dimension (see [START_REF] Daniely | Multiclass learnability and the ERM principle[END_REF] for example), which allow to better specify the expressiveness of a multiclass classifier. However, this is not the main focus of this paper and our results are based on simpler tools.

To complement this work, we want to investigate a way to properly tackle near-linear problems (such as Reuters). As for now the algorithm already does a very good jobs due to its noise robustness. However more work has to be done to derive a proper way to handle cases where a perfect classifier does not exist. We think there are great avenues for interesting research in this domain with an algorithm like UMA and we are curious to see how this present work may carry over to more general problems.

A Double sample theorem

Proof (Proposition 3)

For a fixed pair (p, q) ∈ Y 2 , we consider the family of functions Strictly speaking, l f (x) is not a loss as it does not take y into account, nonetheless it does play the same role in the following proof than a regular loss in the regular double-sampling proof. One way to think of it is as the loss of a problem for which we do not care about the observed labels but instead we want to classify points into a predetermined class-in this case q.

Clearly, Fpq is a subspace of affine functions, thus Pdim(Fpq) ≤ (d + 1), where Pdim(Fpq) is the pseudo-dimension of Swapping Permutations. Let define Γm the set of all permutations that swap one or more elements of T with the corresponding element of T (i.e. the ith element of T is swapped with the ith element of T ). It is quite immediate that |Γm| = 2 m . For each permutation σ ∈ Γm we note σ(T ) (resp. σ(T )) the set originating from T (resp. T ) from which the elements have been swapped with T (resp. T ) according to σ.

Thanks to Γm we will be able to provide an upper bound on [START_REF] Minsky | Perceptrons: an Introduction to Computational Geometry[END_REF] The last part of the proof comes from the observation that, for any fixed (p, q), we had never used any other specific information about Fpq other than the upper bound of d + 1 over its pseudo dimension. In other words, equation ( 21) holds for slightly modified definition of Fpq as long as the pseudo dimension does not exceed d + 1.

Let us now consider :

Fpq . Clearly for each function in Fpq there is at most one corresponding affine function, thus Fpq and Fpq share the same upper bound of d + 1 on their pseudodimension.

Consequently, any covering number of Fpq is also a covering number of Fpq. More precisely, this proof holds true for any wp and wq, independently of A α p which may itself be defined with respect to wp and wq.

It comes naturally that, fixing S as the training set, the following holds true: We can generalize this result for any couple (p, q) by a simple union bound, giving the desired inequality:

P (X

  for r = 1, . . . , Q: wr ← wr + τrzpq 12:

Fig. 1 :

 1 Fig. 1: (a) evolution of the confusion rate (y-axis) for different noise levels (x-axis); (b) evolution of the same quantity with respect to errors in the confusion matrix C (x-axis) measured by the approximation factor (see text).

Fig. 2 :

 2 Fig. 2: Class distribution for the three datasets.

Fig. 3 :

 3 Fig. 3: Error rate of UMA and f conf with respect to the sampling size. Reuters dataset with m = 70 for the sake of figure's readability.

Fpq .=

  {f : f (x) . = wqwp, x : wp, wq ∈ B d }where B d is a d-dimensional unit ball. For each f ∈ Fpq define the corresponding "loss" functionl f (x) . = l(f (x)) . = 2 -f (x).

= 1 . 1 m

 11 Fpq. Additionally, l is Lipschitz in its first argument with a Lipschitz factor of L . Indeed ∀y, y 1 , y 2 , ∈ Y : |l(y 1 , y)l(y 2 , y)| = |y 1 -y 2 |. Let Dpq be any distribution over X × Y and T ∈ (X × Y) m such that T ∼ D m pq , then define the empirical loss err l T [f ] . = xi∈T l(x i , y i ) and the expected loss err l D [f ].= E D [l(x, y)] The goal here is to prove that P

( 21 ) 2 ≥ 1 2 , 2 ≥T

 212122 Proof (Proof of[START_REF] Louche | Unconfused ultraconservative multiclass algorithms[END_REF]) We start by noting that l(y 1 , y 2 ) ∈ [0, 2] and then proceed with a classic 4-step double sampling proof. Namely:Symmetrization. We introduce a ghost sample T ∈ (X × Y) m , T ∼ D m pq and show that for f bad T such that |err l Dpq [f bad T ] -err l T [f bad T ]| ≥ then P T |T err l T [f bad T ] -err l Dpq [f bad T ] ≤as long as m 2 ≥ 32. It follows thatP (T,T )∼D m pq ×D m pq sup f ∈Fpq |err l T [f ] -err l T [f ]| ≥ P T ∼D m pq |err l T [f bad T ] -err l Dpq [f bad T ]| ≥ × P T |T err l T [f bad T ] -err l Dpq [f bad T ] [f ] -err l Dpq [f ]| ≥ (By definition of f bad T )Thus upper bounding the desired probability by2 × P (T,T )∼D m pq ×D m pq sup f ∈Fpq |err l T [f ] -err l T [f ]| ≥ 2(22)

  Our starting point is that (T, T ) ∼ D m pq × D m pq then for any σ ∈ Γm, the random variable sup f ∈Fpq |err l T [f ] -err l T [f ]| follows the same distribution as sup f ∈Fpq |err l σ(T ) [f ]err l σ(T ) [f ]|.

==

  {f : f (x) . I{t(x) = q}I x ∈ A α p wpwq, x : wp, wq ∈ B d }

  I{t(x) = q}I x ∈ A α p x = zpq.Thuserr l T [f ] -err l D [f ] =wpwq wpwq , zpqwpwq wpwq , µ q p .

Table 1 :

 1 Misclassification rates of different algorithms.

	Dataset	fy	fconf	ffull	fS3VM	UMA fS3VM (no K-PCA)
	Handwritten Digits 0.25	0.21	0.04	0.15	0.16	0.07
	Letter Recognition	0.35	0.36	0.23	0.49	0.33	0.18
	Reuters	0.30	0.17	0.01	0.22	0.21	0.22

  ×Y)∼D sup

	W ∈R d×Q		wp -wq wp -wq	, zpq -	wp -wq wp -wq	, µ q p	≥
	≤ O Q 2 8	(n+1)	e m 2 /128
	Equivalently, we have that
	wp -wq wp -wq	, zpq -		wp -wq wp -wq	, µ q p	≥
	with probability 1 -δ for
	m ∈ O	1 2 ln	1

δ + ln(Q) + d ln 1

.

For the sake of self-containedness, we use UMA for this task (with C being the identity matrix). Remind that, when used this way, UMA acts as a regular Perceptron algorithm

Note that in some references the right-hand side of (24) might viewed as a probability measure over m independent Rademacher variables.

Acknowledgments. The authors would like to thank the reviewers for their feedback and invaluable comments. This work is partially supported by the Agence Nationale de la Recherche (ANR), project GRETA 12-BS02-004-01. We would like to thank the anonymous reviewers for their insightful and extremely valuable feedback on earlier versions of this paper.

All in all, the reported results advise us to prefer UMA over other available methods when the amount of labelled data is particularly small, in addition, obviously, to the motivating case of the present work where the training data are corrupted and the confusion matrix is known. Also, another interesting finding we get is that even a rough estimation of the confusion matrix is sufficient for UMA to behave well.

Finally, we investigate the impact of the selection strategy of (p, q) on the convergence speed of UMA (see Section 3.5). We use three variations of UMA with different strategies for selecting (p, q) (error, confusion, and random) and monitor each one along the learning process on the Reuters dataset. The error and confusion strategies are described in Section 3.5 and the random strategy simply selects p and q at random.

From Figure 5, which reports the misclassification rate and the confusion rate along the iterations, we observe that both performance measures evolve similarly, attaining a stable state around the 30th iteration. The best strategy depends on the performance measure used, even though regardless of the performance measure used, we observe that the random selection strategy leads to a predictor that does not achieve the best performance measure (there is always a curve beneath that of the random selection procedure), which shows that it not an optimal selection strategy.

Therefore:

which concludes the second step.

Reduction to a finite class. The idea is to reduce Fpq in ( 23) to a finite class of functions. For the sake of conciseness, we will not enter into the details of the theory of covering numbers. Please refer to the corresponding literature for further details (e.g. [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF]).

In the following, N ( / 8 , Fpq, 2m) will denote the uniform / 8 convering number of Fpq over a sample of size 2m.

Let define Gpq ⊂ Fpq such that (l Gpq ) |(T,T ) is an / 8 -cover of (l Fpq ) |(T,T ) . Thus,

Putting everything together yields the result w.r.t. N ( / 8 , l Fpq , 2m) for m 2 ≥ 32. For m 2 < 32 it holds trivially.

Recall that l Fpq is Lipschitz in its first argument with a Lipschitz constant L = 1 thus N ( / 8 , l Fpq , 2m) ≤ N ( / 8 , Fpq, 2m) = O 8 Pdim (Fpq )