Etienne Côme
email: come@inrets.fr

Latifa Oukhellou

Thierry Denoeux

Patrice Aknin

Learning from partially supervised data using mixture models and belief functions

Keywords: Dempster-Shafer theory, Transferable Belief Model, Mixture models, EM algorithm, Classification, Clustering, Partially supervised learning, Semi-supervised learning

Learning from partially supervised data using mixture models and belief functions.

Introduction

Machine learning classically deals with two different problems: supervised learning (classification) and unsupervised learning (clustering). However, in recent years, new paradigms have emerged to mix these two approaches in order to extend the applicability of machine learning algorithms.

The paradigm that emerged first is semi-supervised learning [START_REF] Hosmer | A comparison of iterative maximum likelihood estimates of the parameters of a mixture of two normal distributions under three different types of sample[END_REF][START_REF] Mclachlan | Estimating the linear discriminant function from initial samples containing a small number of unclassified observations[END_REF], where the learning set X ss = {(x 1 , y 1 ), . . . , (x M , y M ), x M+1 , . . . , x N } is composed of two different parts. In the first part, the true class labels y i are specified, whereas in the second part only the feature vectors x i are given. The importance for such problems comes from the fact that labelled data are often difficult to obtain, while unlabelled ones are easily available. Using unlabelled data may thus be a means to enhance the performances of supervised algorithms with low additional cost. The recent publication of a collected volume [START_REF]Semi-Supervised Learning[END_REF] shows the important activity around this issue in the Machine Learning field.

Recent approaches to semi-supervised learning fall into two main categories:

-An important class of methods is based on the hypothesis that the decision boundary should be located in low density areas. Methods in this category aim at deriving a regularizer of the conditional log-likelihood, taking into account the unlabelled data to bias the decision boundary towards low density areas [START_REF] Bengio | Semi-supervised learning by entropy minimization[END_REF][START_REF] Corduneanu | On information regularization[END_REF]. The Transductive Support Vector Machine [START_REF] Joachims | Transductive inference for text classification using support vector machine[END_REF] uses a marginbased criterion to achieve a similar goal. All these methods suffer from the problem of local maxima, although some relaxation schemes lead to a convex optimization problem in the case of the Transductive Support Vector Machine [START_REF] Bie | Semi-supervised learning based on kernel methods and graph cut algorithms[END_REF].

-Other methods are based on the assumption that the high-dimensional input data lie near a low dimensional manifold. Unlabelled data are then useful as they help in estimating this manifold.

Methods relying on the manifold assumption are typically based on unsupervised dimensionality reduction techniques such as PCA or Kernel-PCA, or on label propagation in a graph [START_REF] Zhou | Learning with local and global consistency[END_REF][START_REF] Zhu | Learning from labelled and unlabelled data with label propagation[END_REF]. Other paradigms have also been proposed to take into account more sophisticated information on class labels. For example, partially supervised learning [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF][START_REF] Ambroise | EM algorithm for partially known labels[END_REF][START_REF] Ambroise | Learning from an imprecise teacher: probabilistic and evidential approaches[END_REF][START_REF] Grandvallet | Logistic regression for partial labels[END_REF][START_REF] Hüllermeier | Learning from ambiguously labeled examples[END_REF]] deals with constraints on the possible classes of samples. In this case, the learning set has the following form X ps = {(x 1 , C 1 ), . . . , (x N , C N )}, where C i is a set of possible classes for learning example i. If all classes are possible, the example is not labelled. Conversely, the example is perfectly labelled if only one class is specified (|C i | = 1). Between these two extreme cases, this approach may also handle situations where some examples are known to belong to any subset of classes. In this case, they are considered as partially or imprecisely labeled. This framework is thus more general than the semi-supervised learning problem.

A completely different paradigm is based on the notion of label noise and assumes that the class labels may be pervated by random errors. In this case, class labels are thus precise, but uncertain.

Recent contributions along these lines can by found in References [START_REF] Lawrence | Estimating a kernel fisher discriminant in the presence of label noise[END_REF][START_REF] Amini | Semi-supervised learning with an imperfect supervisor[END_REF][START_REF] Karmaker | A boosting approach to remove class label noise[END_REF]. In the first two papers, a generative model of label noise is assumed. It is then proposed to model the label noise process by conditional distributions specifying the probabilities that samples labelled as belonging to one class, were in fact drawn from from another class. The parameters of such model are then learnt by maximizing the likelihood of the observations knowing the labels [START_REF] Lawrence | Estimating a kernel fisher discriminant in the presence of label noise[END_REF] or are optimized using a Classification Maximum Likelihood approach [START_REF] Amini | Semi-supervised learning with an imperfect supervisor[END_REF]. A kernelized version of this kind of approach has been proposed in [START_REF] Lawrence | Estimating a kernel fisher discriminant in the presence of label noise[END_REF][START_REF] Li | Classification in the presence of class noise using a probabilistic kernel fisher method[END_REF].

The investigations reported in this paper provide a solution to deal with imprecise and/or uncertain class labels, and can therefore be seen as addressing a more general issue than in the above paradigms. Our approach is based on the theory of belief functions [START_REF] Shafer | A mathematical theory of evidence[END_REF][START_REF] Smets | The Transferable Belief Model[END_REF], a framework known to be well suited to represent imprecise and uncertain information. In this paper, we explore its use to represent knowledge on class membership of learning examples, in order to extend the partially supervised framework. In this way, both the uncertainty and the imprecision of class labels may be handled. The considered training sets are of the form X iu = {(x 1 , m 1 ), . . . , (x N , m N )}, where m i is a basic belief assignment, or Dempster-Shafer mass function [START_REF] Shafer | A mathematical theory of evidence[END_REF] encoding our knowledge about the class of example i. The m i s (hereafter referred to as "soft labels") may represent different kinds of knowledge, from precise to imprecise and from certain to uncertain. Thus, previous problems are special cases of this general formulation. Other studies have already proposed solutions in which class labels are expressed by possibility distributions or belief functions [START_REF] Denoeux | Handling possibilistic labels in pattern classification using evidential reasoning[END_REF][START_REF] Elouedi | Belief decision trees: Theoretical foundations[END_REF][START_REF] Trabelsi | Pruning belief decision tree methods in averaging and conjunctive approaches[END_REF][START_REF] Jenhani | Decision trees as possibilistic classifiers[END_REF]. These labels are interesting when they are supplied by one or several experts and when crisp assignments are hard to obtain. In such cases, the elicitation of experts' opinions regarding the class membership of objects under consideration, in term of possibility or belief functions, can be of interest [START_REF] Denoeux | Handling possibilistic labels in pattern classification using evidential reasoning[END_REF][START_REF] Ben Yaghlane | Elicitation of expert opinions for constructing belief functions[END_REF].

In this article, we present a new approach to solve learning problems of this type, based on a preliminary study by Vannoorenberghe and Smets [START_REF] Vannoorenberghe | Partially supervised learning by a credal EM approach[END_REF][START_REF] Vannoorenberghe | Estimation de modèles de mélanges finis par un algorithm EM crédibiliste[END_REF]. This solution is based on mixture models, and therefore assumes a generative model for the data. Generative models have already proved their efficiency in a lot of applications [START_REF] Mclachlan | Finite Mixture Models[END_REF]. Their flexibility offers also a good way to benefit from domain specific knowledge, as shown, for example, in text classification [START_REF] Nigam | Text classification from labelled and unlabelled documents using EM[END_REF]. Finally, the adaptability of the Expectation Maximization (EM) algorithm, which may easily handle specific constraints, is an advantage of generative models. Note that the approach introduced in [START_REF] Vannoorenberghe | Partially supervised learning by a credal EM approach[END_REF] and [START_REF] Jraidi | Belief classification approach based on generalized credal EM[END_REF] to apply the EM algorithm to data with soft labels, although based on strong intuitions, was only imperfectly formalized. It was not clear, in particular, what was the equivalent of the loglikelihood function in this case, and if the proposed extension of the EM algorithm converged at all. Precise answers to these questions are provided here. This article is organized as follows. Background material on belief functions and on the estimation of parameters in mixture models using the EM algorithm will first be recalled in Sections 2 and 3, respectively. The problem of learning from data with soft labels will then be addressed in Section 4, which constitutes the core of the paper. A criterion extending the usual likelihood criterion will first be derived in Section 4.1, and a version of the EM algorithm that optimizes this criterion will be introduced in Section 4.2. Practical considerations and a general discussion will be presented in Sections 4.3 and 4.4, respectively. Finally, simulation results illustrating the advantages of this approach will be reported in Section 5, and Section 6 will conclude the paper.

Background on Belief Functions

Belief Functions on a Finite Frame

The theory of belief functions was introduced by Dempster [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] and Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF]. The interpretation adopted throughout this paper will be that of the Transferable Belief Model (TBM) introduced by Smets [START_REF] Smets | The Transferable Belief Model[END_REF]. The first building block of belief function theory is the basic belief assignment (bba), which models the beliefs held by an agent regarding the actual value of a given variable taking values in a finite domain (or frame of discernment ) Ω, based on some body of evidence. A bba m Ω is a mapping from 2 Ω to [0, 1] verifying:

ω⊆Ω m Ω (ω) = 1.
(

) 1
Each mass m Ω (ω) is interpreted as the part of the agent's belief allocated to the hypothesis that the variable takes some value in ω [START_REF] Shafer | A mathematical theory of evidence[END_REF][START_REF] Smets | The Transferable Belief Model[END_REF]. The subsets ω for which m Ω (ω) > 0 are called the focal sets. A categorical bba has only one focal set. A simple bba has at most two focal sets, including Ω. A Bayesian bba is a bba whose focal sets are singletons. A bba is said to be consonant if its focal sets are nested.

A bba is in one to one correspondence with other representations of the agent's belief, including the plausibility function defined as:

pl Ω (ω)

△ = α∩ω =∅ m Ω (α), ∀ω ⊆ Ω. ( 2
)
The quantity pl Ω (ω) is thus equal to the sum of the basic belief masses assigned to propositions that are not in contradiction with ω; it corresponds to the maximum degree of support that could be given to ω, if further evidence became available. The plausibility function associated to a Bayesian bba is a probability measure. If m Ω is consonant, then pl Ω is a possibility measure: it verifies pl Ω (α ∪ β) = max(pl Ω (α), pl Ω (β)), for all α, β ⊆ Ω.

Conditioning and Combination

Given two bbas m Ω 1 , m Ω 2 supported by two distinct bodies of evidence, we may build a new bba

m Ω 1 ∩ 2 = m Ω 1 ∩ m Ω
2 that corresponds to the conjunction of these two bodies of evidence:

m Ω 1 ∩ 2 (ω) △ = α1∩α2=ω m Ω 1 (α 1 )m Ω 2 (α 2 ), ∀ω ⊆ Ω. ( 3
)
This operation is usually referred to as the unnormalized Dempster's rule, or the TBM conjunctive rule. Any positive mass assigned to the empty set during the combination process is interpreted as indicating partial conflict between the two bodies of evidence. If the frame of discernment is supposed to be exhaustive, this mass is usually reallocated to other subsets, leading to the definition of the normalized Demspter's rule ⊕ defined as:

m Ω 1⊕2 (ω) =          0 if ω = ∅ m Ω 1 ∩ 2 (ω) 1-m Ω 1 ∩ 2 (∅) if ω ⊆ Ω, ω = ∅, (4) which is well defined provided m Ω 1 ∩ 2 (∅) = 1. Note that, if m Ω 1 (or m Ω 2 ) is Bayesian, then m Ω 1⊕2 (ω) is also Bayesian.
The combination of a bba m Ω with a categorical bba focused on α ⊆ Ω using the TBM conjunctive rule is called (unnormalized) conditioning. The resulting bba is denoted m Ω (ω|α). Probabilistic conditioning is recovered when m Ω is Bayesian, and normalization is performed. Using this definition, we may rewrite the conjunctive combination rule:

m Ω 1 ∩ 2 (ω) = α⊆Ω m Ω 1 (α)m Ω 2 (ω|α), ∀ω ⊆ Ω, (5)
which is a counterpart of the total probability theorem in probability theory [START_REF] Dubois | On the unicity of Dempster's rule of combination[END_REF][START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF]. This expression shows more clearly the link with probability calculus and provides a shortcut to perform marginal calculations on a product space when conditional bbas are available [START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF]. Consider two frames Ω and Θ, and a set of conditional belief functions m Θ|Ω (•|ω) for all ω ⊆ Ω. Each conditional bba m Θ|Ω (•|ω) represents the agent's belief on Θ in a context where ω holds. The combination of these conditional bbas with a bba m Ω on Ω yields the following bba on Θ:

m Θ (θ) = ω⊆Ω m Ω (ω)m Θ|Ω (θ|ω), ∀θ ⊆ Θ. (6)
A similar formula holds for the plausibility function:

pl Θ (θ) = ω⊆Ω m Ω (ω)pl Θ|Ω (θ|ω), ∀θ ⊆ Θ. (7)
This property bears some resemblance with the total probability theorem, except that the sum is taken over the power set of Ω and not over Ω. We will name it the total plausibility theorem.

Independence

The usual independence concept of probability theory does not easily find a counterpart in belief function theory, where different notions must be used instead. The simplest form of independence defined in the context of belief functions is cognitive independence [19, p. 149]. Frames Ω and Θ are said to be cognitively independent with respect to pl Ω×Θ iff we have

pl Ω×Θ (ω × θ) = pl Ω (ω) pl Θ (θ), ∀ω ⊆ Ω, ∀θ ⊆ Θ. ( 8
)
Cognitive independence boils down to probabilistic independence when pl Ω×Θ is a probability measure. However, the concept of cognitive independence does not inherit all of the properties of the probabilistic notion of independence and may be seen as a weak form of independence. See [START_REF] Ben Yaghlane | Belief function independence: I. the marginal case[END_REF][START_REF] Ben Yaghlane | Belief function independence: II. the conditional case[END_REF] for an in-depth analysis of independence concepts in the belief function theory.

Belief Functions on the Real Line

The theory presented in the previous section can easily be extended to continuous belief functions on the real line, assuming focal sets to be real intervals [START_REF] Smets | Belief functions on real numbers[END_REF]. In this context, the concept of bba is replaced by that of basic belief density (bbd), defined as a mapping m R from the set of closed real intervals to [0, +∞) such that

+∞ -∞ +∞ x m R ([x, y])dydx ≤ 1. ( 9
)
By convention, the one's complement of the integral in the left-hand side of ( 9) is allocated to ∅.

As in the discrete case, pl R ([a, b]) is defined as a sum over all intervals whose intersection with [a, b] is non-empty:

pl R ([a, b]) △ = [x,y]∩[a,b] =∅ m R ([x, y])dydx. ( 10
)
Further extension of these definitions to R d , d > 1 is possible [START_REF] Caron | Least committed basic belief density induced by a multivariate gaussian: Formulation with applications[END_REF]. It is also possible to define belief functions on mixed product spaces involving discrete and continuous frames (see, e.g., [START_REF] Aregui | Novelty detection in the belief functions framework[END_REF]).

The last tool from belief function theory which is of interest here is the Generalized Bayesian Theorem (GBT), introduced by Smets [START_REF] Smets | Un modèle mathématico-statistique simulant le processus du diagnostic médical[END_REF][START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF].

Generalized Bayesian Theorem

The Bayes' theorem of probability theory is replaced in the framework of belief function by the Generalized Bayesian Theorem (GBT), [START_REF] Smets | Un modèle mathématico-statistique simulant le processus du diagnostic médical[END_REF][START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF][START_REF] Delmotte | Target identification based on the Transferable Belief Model interpretation of Dempster-Shafer model[END_REF][START_REF] Denoeux | Classification using belief functions: the relationship between the casebased and model-based approaches[END_REF]. This theorem provides a way to reverse conditional belief functions without any prior knowledge. Let us consider two spaces, X the observation space and Θ the parameter space. Assume that our knowledge is encoded by a set of conditional bbas m X |Θ (.|θ i ), θ i ∈ Θ, which express our belief in future observations conditionally on each θ i , and we observe a realization x ⊆ X . The question is: given this observation and the set of conditional bbas, what is our belief on the value of Θ? The answer is given by the GBT and states that the resulting plausibility function on Θ has the following form:

pl Θ|X (θ|x) = pl X |Θ (x|θ) = 1 - θi∈θ (1 -pl X |Θ (x|θ i )). ( 11
)
When a prior bba m Θ 0 on Θ is available, it should be combined conjunctively with the bba defined by [START_REF] Ambroise | EM algorithm for partially known labels[END_REF]. The classical Bayes' theorem is recovered when the conditional bbas m X |Θ (.|θ i ) and the prior bba m Θ 0 are Bayesian. After this review of some tools from belief functions theory, the next part is dedicated to the probabilistic formulation of the clustering and classification problems in terms of mixture model.

Mixture Models and the EM Algorithm

The Expectation Maximization (EM) algorithm provides a general solution to problems involving missing data [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. Here, we are interested in its most classical application, which concerns mixture

P(Y = c k ) = π k , ∀k ∈ {1, . . . , K}. (12)
The π k are thus the class proportions; they verify

K k=1 π k = 1.
-The observed values {x 1 , . . . , x N } are drawn using the class conditional density in relation with the class label. More formally, X 1 , . . . , X N ∼ X are continuous random variables taking values in X , with conditional probability density functions:

f (x|Y = c k ) = f (x; θ k ), ∀k ∈ {1, . . . , K}. (13)
The parameters of this generative model are therefore the proportions π = (π 1 , . . . , π K ) and the parameters of the class conditional densities θ 1 , . . . , θ K . To simplify the notations, the vector of all model parameters is denoted:

Ψ = (π 1 , . . . , π K , θ 1 , . . . , θ K ).
This generative model can be represented by an oriented graph, as shown in Figure 1.

The simplest case corresponds to the supervised learning problem where both the observations and their classes are known. The learning set is then:

X s = {(x 1 , y 1 ), . . . , (x N , y N )}. ( 14
)
It may be noted, equivalently, X s = {(x 1 , z 1 ), . . . , (x N , z N )}, where z i ∈ {0, 1} K are binary variables encoding the class membership of each data point, such that z ik = 1 if y i = c k , and z ik = 0 otherwise. In this case, the complete data log-likelihood can be written:

L(Ψ; X s ) = N i=1 K k=1 z ik ln(π k f (x i ; θ k )). (15)
In this case, the Maximum Likelihood Estimator is generally easy to compute because optimization problems are decoupled for each class.

In unsupervised learning problems, however, the available data are only the i.i.d realizations of X, X u = {x 1 , . . . , x N }, provided by the generative model. To learn the parameters and the associated partition of the data, the log-likelihood must be computed according to the marginal

density K k=1 π k f (x i ; θ k ) of X i . We then have L(Ψ; X u ) = N i=1 ln K k=1 π k f (x i ; θ k ) . (16)

EM Algorithm

The log-likelihood function defined by ( 16) is difficult to optimize and may lead to a set of different local maxima. The EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF][START_REF] Mclachlan | The EM Algorithm and Extensions[END_REF] is nowadays the classical solution to this problem. The missing data of the clustering problem are the true class labels y i of learning examples. The EM algorithm brings them back in the optimization problem defined by ( 16), and uses them to build an iterative ascent strategy which, given an initial parameter estimate Ψ (0) , alternates two steps:

expectation (E) and maximization (M), until a local maximum is found.

The basis of the EM algorithm can be found in the link between the log-likelihood L(Ψ; X u ) and the complete log-likelihood L(Ψ; X s ). The following relations hold:

L(Ψ; X u ) = L(Ψ; X s ) - N i=1 ln(P(z i |x i )) (17) = N i=1 K k=1 z ik ln(π k f (x i ; θ k )) - N i=1 K k=1 z ik ln π k f (x i ; θ k ) K k ′ =1 π k ′ f (x i ; θ k ′ ) . ( 18
)
The observation labels z ik are unknown, but they can be replaced by their expectation given the current parameters estimates Ψ (q) at iteration q and the observed values x 1 , . . . , x N . Relation [START_REF] Li | Classification in the presence of class noise using a probabilistic kernel fisher method[END_REF] remains valid and we obtain:

L(Ψ; X u ) = N i=1 K k=1 t (q) ik ln (π k f (x i ; θ k )) Q(Ψ,Ψ (q) ) - N i=1 K k=1 t (q) ik ln π k f (x i ; θ k ) K k ′ =1 π k ′ f (x i ; θ k ′ ) H(Ψ,Ψ (q) ) , (19)
with:

t (q) ik = E Ψ (q) [z ik |x i ] = P(z ik = 1|Ψ (q) , x i ) = π (q) k f (x i ; θ (q) k ) K k ′ =1 π (q) k ′ f (x i ; θ (q) k ′ ) . ( 20
)
Such a decomposition is useful to define an iterative ascent strategy. The difference between the log-likelihood evaluated at iterations q + 1 and q is:

L(Ψ (q+1) ; X u ) -L(Ψ (q) ; X u ) = Q(Ψ (q+1) , Ψ (q) ) -Q(Ψ (q) , Ψ (q) ) + H(Ψ (q) , Ψ (q) ) -H(Ψ (q+1) , Ψ (q) ) . ( 21
)
The second term in the right-hand side of ( 21) is:

H(Ψ (q) , Ψ (q) ) -H(Ψ (q+1) , Ψ (q) ) = N i=1 K k=1 t (q) ik ln(t (q) ik ) - N i=1 K k=1 t (q)
ik ln(t

(q+1) ik ) (22) = - N i=1 K k=1 t (q) ik ln t (q+1) ik t (q) ik . ( 23
)
We thus have H(Ψ (q) , Ψ (q) )-H(Ψ (q+1) , Ψ (q) ) ≥ 0, as a consequence Jensen's inequality. Therefore, the log-likelihood will increase between iterations q and q + 1 if we find new parameter estimates

Ψ (q+1) such that: Q(Ψ (q+1) , Ψ (q) ) -Q(Ψ (q) , Ψ (q) ) > 0. ( 24
)
Consequently, the maximization of the auxiliary function Q is sufficient to improve the likelihood.

Furthermore, because the sum over the classes is outside the logarithm, the optimization problems are decoupled and the maximization is simpler. The EM algorithm starts with initial estimates

Ψ (0)
and alternates two steps (called the E and M steps) to define a sequence of parameters estimates with increasing likelihood values. These steps are recalled in more detail below.

E

Step: During this step, the expectation of the complete data log-likelihood according to the current value of the parameter is computed. This expectation defines the auxiliary function Q(Ψ, Ψ (q) ):

Q(Ψ, Ψ (q) ) = E Ψ (q) [L(Ψ; X s )|x 1 , . . . , x N ] = N i=1 K k=1 t (q) ik ln (π k f (x i ; θ k )) . (25)
For this, the posterior probabilities t

(q)
ik are computed from the current estimates of the parameters using [START_REF] Smets | The Transferable Belief Model[END_REF]. When these posterior probabilities have been computed, we can optimize the auxiliary function to find the new parameters estimates.

M

Step: During this step, the parameters are updated. The maximization of the auxiliary function with respect to Ψ provides the new estimate:

Ψ (q+1) = arg max Ψ Q(Ψ, Ψ (q) ). ( 26
)
As mentioned previously, this estimate has a higher likelihood than the previous one. This maximization problem has an analytic solution for the mixing proportions: the maximum of

N i=1 K k=1 t (q) ik ln(π k ) under the constraint K k=1 π k = 1 yields π (q+1) k = 1 N N i=1 t (q) ik . (27)
Moreover, if classical parametric models are assumed for the conditional densities (Multivariate normal, Exponential, ...), the optimization problem solution often has a closed form. For example, if multivariate normal densities functions are considered, f (x; θ k ) = φ(x; µ k , Σ k ), all the parameters are updated using the following formulas:

µ (q+1) k = 1 N i=1 t (q) ik N i=1 t (q) ik x i (28)
Σ (q+1) k = 1 N i=1 t (q) ik N i=1 t (q) ik (x i -µ (q+1) k )(x i -µ (q+1) k ) ′ . ( 29
)
The Expectation and the Maximization steps are repeated until convergence, which can be detected when the increase of the log-likelihood does not exceed a given threshold.

The mixture model setting and the EM algorithm can be adapted to handle specific learning problems such as the semi-supervised and the partially supervised cases, as we will see in the next subsection.

Semi-supervised and Partially Supervised Learning of Mixture Models

In semi-supervised learning, the component origins of the samples are known only for the M first observations. Consequently the log-likelihood can be decomposed in two parts corresponding, respectively, to the supervised and unsupervised learning examples:

L(Ψ, X ss ) = M i=1 K k=1 z ik ln(π k f (x i ; θ k )) + N i=M+1 ln( K k=1 π k f (x i ; θ k )), (30)
It is easy to see that an EM algorithm can be adapted to optimize this function. Function Q can be rewritten as:

Q(Ψ, Ψ (q) ) = M i=1 K k=1 z ik ln(π k f (x i ; θ k )) + N i=M+1 K k=1 t (q) ik ln(π k f (x i ; θ k )). ( 31
)
This form of Q leads to a new version of the EM algorithm dedicated to semi-supervised learning problems. In fact, the modification affects only the E step, where the t ik are only computed for unlabelled observations. During the M step, the z ik are used instead of the t ik for labelled data.

In the context of partially known labels, the available information on y i is a subset of pos-

sible classes C i ⊆ Y. The dataset X ps = {(x 1 , C 1 ), . . . , (x N , C N )} under consideration contains independent realizations (x i , Y i ∈ C i ).
The likelihood must therefore be computed from the joint distribution of (x i , Y i ∈ C i ):

P(x i , Y i ∈ C i ) = {k:c k ∈Ci} P(x i , Y i = c k ) = K k=1 P(Y i ∈ C i ∩ {c k })f (x i |Y i = c k ) (32)
where:

P(Y i ∈ C i ∩ {c k }) =      0 if c k / ∈ C i , π k if c k ∈ C i . (33)
Introducing the notation l i = (l i1 , . . . , l iK ) ∈ {0, 1} K which is simply an indicator of the subset

C i ⊆ Y corresponding to the partial label (l ik = 1 if c k ∈ C i , l ik = 0
otherwise), we may write: [START_REF] Dubois | On the unicity of Dempster's rule of combination[END_REF], we have:

P(Y i ∈ C i ∩ {c k }) = l ik π k . ( 34
) Substituting P(Y i ∈ {C i ∩ c k }) by l ik π k in
P(x i , Y i ∈ C i ) = K k=1 l ik π k f (x i ; θ k ) (35)
The log-likelihood becomes:

L(Ψ, X ps ) = N i=1 ln K k=1 l ik π k f (x i , θ k ) . (36)
The EM algorithm may also be used in this context, with few modifications to produce parameter estimates [START_REF] Ambroise | EM algorithm for partially known labels[END_REF]. The modifications affect only the E step where the posterior probabilities of each class are computed according to:

t (q) ik = l ik π (q) k f (x i ; θ (q) k ) K k ′ =1 l ik π (q) k ′ f (x i ; θ (q) k ′ ) . ( 37
)
The M step is not affected by taking into account the additional information and is computed as usually.

Extension to Imprecise and Uncertain Labels

Our method extends the approach described above to handle imprecise and uncertain class labels defined by belief functions.

Derivation of a Generalized Likelihood Criterion

In this section, we shall assume the learning set under consideration to be of the form:

X iu = {(x 1 , m Y 1 ), . . . , (x N , m Y N )}, (38)
where each m Y i is a bba on the set Y of classes, encoding all available information about the class of example i. As before, the x i will be assumed to have been generated according to the mixture model defined in Section 3.1. Our goal is to extend the previous method to estimate the model parameters from dataset [START_REF] Aregui | Novelty detection in the belief functions framework[END_REF]. For that purpose, an objective function generalizing the likelihood function needs to be defined.

The concept of likelihood function has strong relations with that of possibility and, more generally, plausibility, as already noted by several authors [START_REF] Smets | Possibilistic inference from statistical data[END_REF][START_REF] Walley | Upper probabilities based on the likelihood function[END_REF][START_REF] Shenoy | Decision making on the sole basis of statistical likelihood[END_REF][START_REF] Smets | Numerical representation of uncertainty[END_REF][START_REF] Monney | A Mathematical Theory of Arguments for Statistical Evidence[END_REF]. Furthermore, selecting the simple hypothesis with highest plausibility given the observations X iu is a natural decision strategy in the belief function framework [START_REF] Cobb | On the plausibility transformation method for translating belief function models to probability models[END_REF]. We thus propose as an estimation principle to search for the value of parameter ψ with maximal conditional plausibility given the data:

ψ = arg max ψ pl Ψ ({ψ}|X iu ). ( 39
)
To avoid cumbersome notations, we shall not distinguish between the singleton {ψ} and the value ψ; the notation pl Ψ ({ψ}|X iu ) will thus be simplified to pl Ψ (ψ|X iu ).

The correctness of the intuition leading to this choice of (39) as an estimation principle seems to be confirmed by the fact that the logarithm of pl Ψ (ψ|X iu ) is an immediate generalization of criteria ( 16), ( 30) and [START_REF] Smets | Belief functions on real numbers[END_REF], as shown by the following proposition.

Proposition 4.1 The logarithm of the conditional plausibility of Ψ given X iu is given by

ln pl Ψ (ψ|X iu ) = N i=1 ln K k=1 pl ik .π k f (x i ; θ k ) + ν, (40)
where the pl ik are the plausibilities of each class k for each sample i according to soft labels m i and ν is a constant independent of ψ.

Proof. Using the GBT [START_REF] Ambroise | EM algorithm for partially known labels[END_REF], the plausibility of parameters can be expressed from the plausibility of the observed values:

pl Ψ (ψ|X iu ) = pl X1×...×XN (x 1 , . . . , x N |ψ). (41)
By making the conditional cognitive independence assumption [START_REF] Zhou | Learning with local and global consistency[END_REF], this plausibility can be decomposed as:

pl Ψ (ψ|X iu ) = N i=1 pl Xi (x i |ψ). (42)
Using the Total Plausibility Theorem (7), we may express the plausibility pl Xi (x i |ψ) of an observation x i knowing the parameter value as:

pl Xi (x i |ψ) = C⊆Y m Yi (C|ψ)pl Xi|Yi (x i |C, ψ), (43)
where m Yi (.|ψ) is a bba representing our beliefs regarding the class Z i of example i. This bba comes from the combination of two information sources: the "soft" label m Y i and the proportions π, which induce a Bayesian bba m Y (•|π) with m Y ({c k }|π) = π k for all c k ∈ Y. As these two sources are supposed to be distinct, they can be combined using the conjunctive rule (3):

m Yi (•|ψ) = m Y i ∩ m Y (•|π).
As m Y (•|π) is Bayesian, the same property holds for m Yi (•|ψ). We have:

m Yi ({c k }|ψ) = C∩c k =∅ m Y i (C)m Y ({c k }|π) = pl ik π k , ∀k ∈ {1, . . . , K} (44)
m Yi (C|ψ) = 0, ∀C ⊆ Y such that |C| > 1. (45)
In the right-hand side of (43), the only terms in the sum that need to be considered are those corresponding to subsets C of Y such that |C| = 1. Consequently, we only need to express pl Xi|Yi (x i |c k , ψ) for all k ∈ {1, ..., K}. There is a difficulty at this stage, since

pl Xi|Yi (•|c k , ψ)
is the continuous probability measure with density function f (x; θ k ): consequently, the plausibility of any single value would be null if observations x i had an infinite precision. However, observations always have a finite precision, so that what we denote by pl Xi|Yi (x i |c k , ψ) is in fact the plausibility of a infinitesimal region around x i with volume dx i1 . . . dx ip (where p is the feature space dimension). We thus have

pl Xi|Yi (x i |c k , ψ) = f (x i ; θ k )dx i1 . . . dx ip . (46)
Using ( 44) and ( 46), ( 43) can be expressed as:

pl Xi (x i |ψ) = K k=1 pl ik π k f (x i ; θ k ) dx i1 . . . dx ip . (47)
Substituting this expression in [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF], we obtain:

pl Ψ (ψ|X iu ) = N i=1 K k=1 pl ik π k f (x i ; θ k ) dx i1 . . . dx ip . (48)
The terms dx ij can be considered as multiplicative constants that do not affect the optimization problem. By taking the logarithm of (48), we get [START_REF] Delmotte | Target identification based on the Transferable Belief Model interpretation of Dempster-Shafer model[END_REF], which completes the proof.

Remark 4.1 The bba m i defining the label of sample i does not appear in its bba form in [START_REF] Delmotte | Target identification based on the Transferable Belief Model interpretation of Dempster-Shafer model[END_REF], but through the plausibilities pl ik . Therefore, labels sharing the same plausibility profile (i.e., the same plausibilities of the singletons) are handled identically. This invariance comes from the probabilistic nature of the generative model. The full expressive power of belief functions is not used, but only

|Y| parameters (to be compared to 2 Y ) are needed to define a label, which is an advantage when the number of components is high.

Remark 4.2 Our estimation principle can be expressed as:

ψ = arg max ψ L(Ψ; X iu ), (49)
with

L(Ψ; X iu ) = N i=1 ln K k=1 pl ik π k f (x i ; θ k ) . (50)
This choice of this notation is justified by the fact that (50) extends the maximum likelihood criteria ( 16), ( 30) and ( 36):

-When the m i are all vacuous, we have pl ik = 1, ∀i, k, and the unsupervised criterion ( 16) is recovered;

-In the semi-supervised case, we have

pl ik =      z ik , ∀i ∈ {1, . . . , M }, ∀k 1, ∀i ∈ {M + 1, . . . , N }, ∀k.
In that case (50) is equivalent to (30); -Finally, the partially supervised criterion [START_REF] Smets | Belief functions on real numbers[END_REF] is recovered when labels are categorical bbas, in which case we have pl ik = l ik , ∀i, k.

Once the criterion is defined, the remaining work concerns its optimization. The next section presents a variant of the EM algorithm dedicated to this task.

EM algorithm for Imprecise and Uncertain Labels

To build an EM algorithm able to optimize L(Ψ; X iu ), we follow a path that parallels the one recalled in Section 3.2.

At iteration q, our knowledge of the class of example i given the current parameter estimates comes from three sources:

(i) the class label m Y i of example i; (ii) the current estimates π (q) of the proportions, which induce a Bayesian bba m Y (•|π (q) ) such that m Y ({c k }|π (q) ) = π (q) k ;

(iii) vector x i and the current parameter estimate Ψ (q) . Using [START_REF] Shenoy | Decision making on the sole basis of statistical likelihood[END_REF] and the GBT (11), we have

pl Yi|Xi ({c k }|x i , ψ) = pl Xi|Yi (x i |c k , ψ) = f (x i ; θ k )dx i1 . . . dx ip .
By combining these three items of evidence using Dempster's rule (4), we get a Bayesian bba (since m Y (•|π (q) ) is Bayesian). Let us denote by t (q) ik the mass assigned to {c k } after combination. We have

t (q) ik = pl ik π (q) k f (x i ; θ (q) k ) K k ′ =1 pl ik ′ π (q) k ′ f (x i ; θ (q) k ′ ) , (51)
which is quite similar to [START_REF] Smets | The Transferable Belief Model[END_REF] and [START_REF] Caron | Least committed basic belief density induced by a multivariate gaussian: Formulation with applications[END_REF].

Using this expression, we may decompose the log-likelihood in two parts, as in [START_REF] Karmaker | A boosting approach to remove class label noise[END_REF]. This is expressed by the following proposition.

Proposition 4.2 L(Ψ; X iu ) = Q(Ψ, Ψ (q) ) -H(Ψ, Ψ (q) ), (52)
with:

Q(Ψ, Ψ (q) ) = N i=1 K k=1 t (q) ik ln (pl ik π k f (x i ; θ k )) H(Ψ, Ψ (q) ) = N i=1 K k=1 t (q)
ik ln(t ik ).

Proof: We have

Q(Ψ, Ψ (q) ) -H(Ψ, Ψ (q) ) = N i=1 K k=1 t (q) ik ln (pl ik π k f (x i ; θ k )) - N i=1 K k=1 t (q) ik . ln(t ik ) = N i=1 K k=1 t (q)
ik ln

pl ik π k f (x i ; θ k ) pl ik π k f (x i ; θ k ) K k ′ =1 pl ik ′ π k ′ f (x i ; θ k ′ ) = N i=1 K k=1 t (q) ik ln K k ′ =1 pl ik ′ π k ′ f (x i ; θ k ′ ) = N i=1 ln    K k=1 K k ′ =1 pl ik ′ π k ′ f (x i ; θ k ′ ) t (q) ik    = N i=1 ln    K k ′ =1 pl ik ′ π k ′ f (x i ; θ k ′ ) K k=1 t (q) ik    = N i=1 ln K k ′ =1 pl ik ′ π k ′ f (x i ; θ k ′ ) = L(Ψ; X iu ).
Therefore, using the same argument as for the classical EM algorithm (Section 3.2), an algorithm which alternates between computing t ik using (51) and maximization of Q will increase the log likelihood. The EM algorithm that performs the optimization of our criterion ( 49) is therefore the classical EM algorithm, except for the E step, where the posterior distributions t ik are weighted by the plausibility of each class pl ik = C∩c k =∅ m i (C). Note that the impact of the soft labels in the EM algorithm has a natural interpretation.

Practical Considerations

The theoretical algorithm presented in the previous section can easily be implemented, with the usual precautions to prevent numerical problems such as storage and manipulations of posterior probabilities t ik on log-scale. The algorithm can readily be adapted to deal with different class conditional distributions. As an example, the pseudo-code for the implementation of our algorithm in the classical case of multidimensional Gaussian mixture is given in Algorithm 1.

Algorithm 1 EM algorithm, pseudo-code for Gaussian mixture models with partial labels. The notation φ(., µ, Σ) stands for the multivariate Gaussian probability density with parameters (µ, Σ).

Inputs: {x i } i=1...N , {pl ik } k=1...K i=1...N Initialize: µ (0) 1 , . . . , µ (0)
K ; Σ (0) 1 , . . . , Σ (0)
K ; π (0) 1 , . . . , π (0) K while Increment in log likelihood > precision threshold do //E step t (q) ik = pl ik π (q) k φ(x i ; µ (q) k , Σ (q) k ) K k ′ =1 pl ik ′ π (q) k ′ φ(x i ; µ (q) k ′ , Σ (q) k ′ ) //M Step π (q+1) k = 1 N N i=1 t (q) ik µ (q+1) k = 1 N i=1 t (q) ik N i=1 t (q) ik x i Σ (q+1) k = 1 N i=1 t (q) ik N i=1 t (q) ik (x i -µ (q+1) k )(x i -µ (q+1) k ) ′ q ← q + 1 end while Outputs: μk = µ (q) k , Σk = Σ (q) k , πk = π (q)
k , ∀k ∈ {1, . . . , K} Some issues related to the practical implementation of this algorithm are briefly addressed below.

Initialization

A practical advantage of soft labels can be found in their ability to provide an interesting starting point for the algorithm. For this, we can simply compute the pignistic transform [START_REF] Smets | The Transferable Belief Model[END_REF] of each label m i to supply the initial values of the posterior probabilities:

t (0) ik = C:c k ∈C m Y i (C) |C| .

Convergence test

The convergence of the algorithm can be checked in different ways. As proposed in the pseudocode of Algorithm 1, the increment in log likelihood can be monitored and a test such as:

L(Ψ (q) ; X iu ) -L(Ψ (q-1) ; X iu ) |L(Ψ (q-1) ; X iu )| < ǫ, ( 53
)
where ǫ is a precision threshold set to a small value (10 -6 ), can be used to check the convergence. Another convergence test can be based on differences between successive estimates of the parameters or latent variables (t (q) ik and t (q+1) ik

).

Discussion

To conclude this section, the problem of data dimensionality and the time complexity of our method will now be discussed. The improvement over previous work will also be stressed.

Curse of Dimensionality

In real applications, it is crucial to take care of data dimensionality. It is well known that Gaussian Mixture Models may perform poorly in high dimensional feature spaces: consequently, similar problems can be expected with our method. Limiting the number of free parameters is a classical way to cope with this problem. In Ref. [START_REF] Banfield | Model-based gaussian and non-gaussian clustering[END_REF][START_REF] Celeux | Gaussian parsimonious clustering models[END_REF], different parametrizations of the covariance matrix with varying numbers of free parameters are proposed. Another solution to the dimensionality problem was recently introduced in [START_REF] Bouveyron | High-dimensional data clustering[END_REF][START_REF] Bouveyron | High dimensional discriminant analysis[END_REF], assuming each class to lie in a low dimensional manifold; constraints are then imposed on the spectral decomposition of the covariances matrix.

Finally, Bayesian regularization techniques can also be used to circumvent problems encountered by Gaussian Mixture Models in high dimensional feature spaces [START_REF] Fraley | Bayesian regularization for normal mixture estimation and model-based clustering[END_REF]. Since all of these solutions affect the M step of the EM algorithm, whereas our integration of soft label information impacts the E step, they can easily be used in conjunction with our method.

Time Complexity

The complexity of one iteration of our algorithm is exactly the same as in the classical EM algorithm for mixture model. Differences that may arise come from label imprecision, which influences the number of iterations needed to converge and the problem of local maxima. The experimental study presented in Section 5.1.3 investigates the influence of soft label imprecision on these two aspects. In the practical application of our algorithm, the key problem will certainly be the existence of local maxima. The algorithm must therefore be initialized with different starting points in order to find different local maxima and select the best one. Other solutions developed to cope with this problem in unsupervised learning of mixture model such as the Deterministic Annealing EM Algorithm [START_REF] Ueda | Deterministic annealing variant of the EM algorithm[END_REF] can also be interesting.

Comparison with Previous Work

As outlined in Section 1, the idea of adapting the EM algorithm to handle soft labels can be traced back to the work of Vannoorenberghe and Smets [START_REF] Vannoorenberghe | Partially supervised learning by a credal EM approach[END_REF][START_REF] Vannoorenberghe | Estimation de modèles de mélanges finis par un algorithm EM crédibiliste[END_REF], which was recently extended to categorical data by Jraidi et al. [START_REF] Jraidi | Belief classification approach based on generalized credal EM[END_REF]. These authors proposed a variant of the EM algorithm called CrEM (Credal EM), based on a modification of the auxiliary function Q(Ψ, Ψ (q) ) defined in [START_REF] Shafer | A mathematical theory of evidence[END_REF].

However, our method differs from this previous approach in several respects:

-First, the CrEM algorithm was not derived as optimizing a generalized likelihood criterion such as [START_REF] Banfield | Model-based gaussian and non-gaussian clustering[END_REF]; consequently, its interpretation was unclear, the relationship with related work (see Remark 4.2) could not be highlighted and, most importantly, the convergence of the algorithm was not proven.

-In our approach, the soft labels m Y i appear in the criterion and in the update formulas for posterior probabilities [START_REF] Celeux | Gaussian parsimonious clustering models[END_REF] only in the form of the plausibilities pl ik of the singletons (plausibility profiles). In constrast, the CrEM algorithm uses the 2 |Y| values in each bba m Y i . This fact has an important consequence, as the computations involved in the E step of the CrEM algorithm have a complexity in O(2 |Y| ) whereas our solution only involves calculations which scale with the cardinality of the set of classes, that is in O(|Y|). For large numbers of classes, this can be expected to have a major influence on running time.

-Finally, no experimental study demonstrating the interest of soft labels was presented in Ref. [START_REF] Vannoorenberghe | Partially supervised learning by a credal EM approach[END_REF][START_REF] Vannoorenberghe | Estimation de modèles de mélanges finis par un algorithm EM crédibiliste[END_REF], since only two simulated examples were used to illustrate the approach. The set of experiments presented in the next section will provide a more complete demonstration of the interest of soft labels.

Simulations

To better understand the behaviour of our algorithm in the presence of imprecise and uncertain labels, two sets of experiments were carried out. The first one aimed at giving some clues on the influence of soft labels on the complexity of the optimization problem and on estimation accuracy, as compared to unsupervised clustering. We studied the influence of label imprecision on these two aspects. The second set of experiments was designed to show the benefits of soft labels when labels are uncertain. We will show that information on label reliability encoded in soft labels can be exploited to obtain a significant reduction of classification error rates.

Influence of Label Imprecision

The aim of this section is to show the influence of label precision on the accuracy of parameter estimation. During the next experiments, the assumption that the true class has the highest plausibility is made. This assumption will be abandoned in Subsection 5.2, where a solution to deal with label uncertainty will be presented.

Imprecise and Uncertain Label Generation

First of all, we must determine how to quantify the amount of information on the true class encoded by a soft label. This question is related to the quantification of label imprecision. Several uncertainty measures have been proposed to quantify the uncertainty in a belief function [START_REF] Klir | Uncertainty-Based Information. Elements of Generalized Information Theory[END_REF].

Among them, nonspecificity (NS) is related to imprecision and has interesting properties [START_REF] Ramer | Uniqueness of information measure in the theory of evidence[END_REF]. It is defined as:

N S(m Y ) = C⊆Y m Y (C) ln(|C|). ( 54
)
To obtain learning sets with specific properties, we varied the mean nonspecificity ns of label sets from a quasi-supervised setting (ns = 0.05) to a quasi unsupervised setting (ns = 0.95) in a two class problem, and we compared the results obtained with these different training sets. To generate a training set with fixed mean nonspecificity, we drew randomly, for each learning sample, a nonspecificity value from a uniform distribution in [ns -0.05, ns + 0.05] and we computed class plausibilities using this value.

As an example, let us assume that we drew a nonspecificity value equal to N S = 0.3, and that the true class of the sample is k * . As we are only interested in the plausibility of singletons we can constrain belief functions to be consonant; therefore, we have to find the masses assigned to focal sets c k * and Y, as there are only two elements in the frame. From ( 54) we find m Y ({c difficult: when the class overlap is important (δ = 1 or 2) and when the learning set is not too large (N = 1000) we can see a significant improvement of supplying partial information on class label. In contrast, when the problem is simple (well separated classes and large number of training samples), we do not gain much from supplying more precise labels. These findings are natural and consistent with theoretical studies on asymptotic efficiency of labelled samples with respect to unlabelled samples [START_REF] O'neill | Normal discrimination with unclassified observations[END_REF]. These results show that our solution is able to take advantage of partial information on class labels to enhance estimation accuracy, provided the soft labels are not wrong (in these experiments, the true class always has a plausibility equal to one). We will now see that partial label information also has an effect on the complexity of the optimization problem.

k * }) × 0 + m Y (Y) × 1 = 0.3, hence m Y (Y) = 0.

Influence of Label Precision on the Likelihood Landscape

The following experiment was designed to show the potential benefit of soft labels in terms of simplification of the optimization problem. Two indicators of optimization problem complexity were investigated: the number of iterations before convergence and the number of different local maxima found.

The behaviour of these two indicators was analyzed with respect to the average nonspecificity of the learning set labels. For that purpose, we drew N = 1000 samples from the same mixture distribution as previously with δ = 2, and we simulated different sets of labels with average nonspecificity ranging from 0.1 to 0.9. For all of these learning sets, we ran the EM algorithm from two hundred different random starting points and we counted the number of different local maxima that were found1 , as well as the average number of iterations until convergence. This experiment was repeated ten times with different randomly generated soft labels, and the results were averaged over these ten independent sets. Figure 3 displays these two indicators of optimization problem complexity.

As expected, information on the true class of samples has a great impact on the complexity of the optimization problem. The increase of the number of local maxima seems to be roughly exponential as a function of the nonspecificity of class labels. Furthermore, for ns < 0.25 we noted that no switching problem appeared whatever the chosen starting point (the predicted class of any learning sample does not change across the successive runs the EM algorithm). When enough information is available, the problem can be considered as convex since only one maximum is found, as in the limit situation of supervised learning. This consideration has high practical interest as the problem of local maxima is very important in the unsupervised learning context.

Simulations with Label Noise

We present here simulation results that highlight the practical interest of soft labels when labelling errors are present. The experiment aimed at using information on class labels simulating expert opinions. As a reasonable setting, we assumed that the expert supplies, for each sample i, his/her more likely label c k and a measure of doubt p i . This doubt is represented by a number in [0, 1], which can be seen as the probability that the expert knows nothing about the true label.

To handle this additional information in the belief function framework, it is natural to discount the categorical bba associated to the guessed label with a discount rate p i [19, Page 251]. Thus, the imperfect labels built from expert opinions are simple bbas such that m Y i ({c k * }) = 1p i for some k * , and m Y i (Y) = p i . The corresponding plausibilities are pl ik * = 1 and pl ik = p i for all k = k * . Such labelling can easily be handled by our method.

Label Simulation

Simulated and real datasets with known class labels were corrupted as follows: for each training sample i, a number p i was drawn from a specific probability distribution to define the doubt expressed by a hypothetical expert on the class of that sample. With probability p i , the label of sample i was changed (to any other class with equal probabilities).

The probability distribution used to draw the p i specifies the expert's labelling error rate. The expected value of p i is equal to the asymptotic labelling error rate. For our experiments we used Beta distributions with expected value equal to {0.1, 0.15, . . . , 0.4} and variance kept equal to 0.2.

Simulated Datasets

The first results concern simulated data. In that case, there is no modeling bias in these exper-Gaussian mixture with the same parameters as in Section 5.1.2, and with a distance δ = 2 between the two centers. Finally, the labels were corrupted by noise as described previously. The results of our approach with soft labels were compared to: (i) supervised learning of the Gaussian Mixture Model, using the potentially wrong expert's labels;

(ii) unsupervised learning of the Gaussian Mixture Model, which does not use any information on class label coming from experts;

(iii) a strategy based on semi-supervised learning of the Gaussian Mixture Model, which takes into account the reliability of labels supplied by the p i 's. This strategy considers each sample as labeled if the doubt expressed by the expert is moderate (p i ≤ 0.5) and as unlabelled otherwise (p i > 0.5). This strategy will be called "adaptive semi-supervised learning";

(iv) the generative probabilistic label noise model introduced in [START_REF] Lawrence | Estimating a kernel fisher discriminant in the presence of label noise[END_REF][START_REF] Li | Classification in the presence of class noise using a probabilistic kernel fisher method[END_REF], which learns the probabilities of label flipping. This solution to deal with label noise addresses a problem close to this one but did not use information on label reliability coming from the expert. The implementation used was the one proposed in [START_REF] Li | Classification in the presence of class noise using a probabilistic kernel fisher method[END_REF], and the mixture model postulated was the same as for all methods, one cluster per class and full covariance matrix.

It should be noted that methods (i)-(iii) above are based on the same EM algorithm as our method, with different class labels. Method (iv) is based on the same generative model, but a specific EM algorithm, as explained in [START_REF] Li | Classification in the presence of class noise using a probabilistic kernel fisher method[END_REF]. Table 1 and Figure 4 show the performances of the different classifiers trained with these learning sets. The error rates of the different classifiers were estimated on a test set of 5000 observations according to their real classes, the results were averaged over one hundred randomly chosen independent training sets. For all methods, the EM algorithm was initialized with the true parameter values. A set of paired, two-sided sign test were performed between the best method (according to empirical classification error) and all other methods. If the null hypothesis (zero median for the difference between the two input distributions) was rejected for all the tests at the 5% significance level, this method was considered to perform significantly better than the others. The corresponding error rates are printed in bold in Table 1.

As expected, when the expert's labelling error rate increases, the error rate of supervised learning also increases. Our solution based on soft labels does not suffer as much as supervised learning and adaptive semi-supervised learning from label noise. Whatever the dataset size, our solution takes advantage of additional information on the reliability of labels to keep good performances. We can notice that, for N ∈ {1000, 2000, 4000}, the results are almost stable even if the expert's labelling error rate increases. Finally, our approach clearly outperforms unsupervised learning, except when the number of samples is high (N = 4000). The comparison with the generative label noise model is also in favor of soft labels when the number of training patterns is low and the results are similar for N ∈ {2000, 4000}. To conclude about this experiment, our solution outperforms both supervised learning, which is an hazardous approach in this context as some labels are wrong, and unsupervised learning that is a conservative approach because information coming from experts is discarded as it is potentially wrong. It also outperforms semi-supervised learning which makes some errors when choosing between considering points as labelled or not. Finally, for small sample size, our approach yields better results than the probabilistic label noise model. This experiment has also proved the ability of belief function based labels to carry useful information even if some labels are partially wrong (the real class does not have a plausibility equal to one).

Real datasets

We also investigated the interest of our approach with real datasets. In that case, modeling bias may arise. We used well known datasets available on-line2 [START_REF] Murphy | UCI Repository of machine learning databases[END_REF], with the characteristics summarized in Table 2. The first dataset is the well known Fisher's Iris data. The Crabs dataset concerns the recognition of crabs species and sexes in a population of crabs using different morphological measurements. The Wine dataset contains the results of a chemical analysis of wines grown in a specific area of Italy. Lastly, the Breast Cancer Wisconsin dataset deals with the recognition of breast tumor from 30 features extracted from digitized images of fine needle aspirate (FNA) of breast mass. The features describe the characteristics of the cell nuclei present in the image and the task is to determine if the tumor is malignant or benign.

No preprocessing was performed except the classical centering and variance normalization. The same process for soft label generation as above was used as for simulated data. The classification error was estimated by ten-fold cross-validation, therefore 9/10 of the samples were used for training with noisy labels and the remaining samples were used to estimate classification error using their real classes. Finally, we sampled thirty independent label sets and computed the mean classification error rate over these sets. To place the different strategies in a realistic context, we used for the each variant of the EM algorithm an initialization procedure compatible with the information available by this method. As no class information is available for unsupervised learning, we started from one hundred different random initializations3 . To solve the label switching problem resulting from these random initializations, we computed the classification error according to the best class permutations. For soft labels and semi-supervised learning the initialization was based on the pignistic transformation of soft labels as explained in Section 4.3. Therefore, only one starting point was used for semi-supervised learning and for soft labels. For these real datasets we also compared our approach with a non parametric approach that can also deal with soft labels, the evidential k nearest neighbor rule proposed in [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF][START_REF] Denoeux | Handling possibilistic labels in pattern classification using evidential reasoning[END_REF]. The results of this method are supplied using the crisp labels given by the virtual expert and the discounted labels. The number of neighbors was fixed a priori to 10.

As for simulated data, the ability of soft labels to adequately account for label noise is visible in Table 3 and Figure 5. For all the problems, results are quite stable even if the expert error rate increases, which means that information on label reliability is correctly exploited to retain good performances. We can also notice that, as with simulated data, the solution based on soft labels significantly outperforms both supervised learning and adaptive semi-supervised learning when the expert error rate increases. It also outperforms unsupervised learning, which is probably affected in some cases by the problem of local maxima. Results of our method are similar to those of label noise model for low label noise level but important differences in favor of soft labels appeared for higher error rates. The k nearest neighbor approach gives also interesting results, except for the dataset Crabs, where this method fails. It yields the best results for the Breast Cancer Wisconsin dataset for low label noise level and gives good results for the Wine and Iris datasets even if mixture models with soft labels perform better. Finally we may note that the solution based on mixture modesl outperforms all the other methods in 14 experiments over 28.

In the different experiments, the solution based on discounting expert labels according to their reliability to produce soft labels has demonstrated its ability to yield good parameter estimates even if the expert's labelling error rate is high. We may conclude that information on label reliability is useful in the context of label noise, and that imprecise and uncertain labels are suitable to deal with such additional information.

Conclusions

The approach presented in this paper, based on concepts coming from maximum likelihood estimation and belief function theory, offers an interesting way to deal with imperfect and imprecise labels. It assumes that the data are generated by a mixture model and that the class labels are belief functions. In this context, a likelihood criterion was defined and an EM algorithm dedicated to its optimization was presented. Simulations have shown that, even if the information on class labels is partial, its exploitation with our approach may significantly improve the estimation accuracy and simplify the optimization problem. Moreover, the practical interest of imprecise and imperfect labels, as a solution to deal with label noise, has been highlighted by an experimental study using both real and experimental data.

The proposed criterion has a natural expression that is closely related to previous solutions found in the context of probabilistic models, and also has a clear and justified origin in the context of belief functions. Therefore, we hope that the link established by this study between probabilistic methods and belief function-based approaches will be extended to other problems. Furthermore, the long history of mixture models is an important advantage for our approach since a lot of tools developed in the context of probabilistic models, such as the Bayesian Information Criterion or other criteria for model selection, can easily be adapted to our approach.

We are working now on the application of such approach for the diagnosis of a railway signalling system [START_REF] Côme | Diagnosis of complex system by combined use of RKCCA and graphical model[END_REF]. Soft labels seem to be appropriate to deal with the imprecise knowledge that experts of this area have on the monitoring data of this complex system.

Fig. 1 .

 1 Fig. 1. Graphical model representation of the mixture model (unsupervised learning) estimation problems.

3 . 5 . 1 . 2 .

 3512 Using the fact that masses should sum to one, we find the mass of the true class m Y ({c k * }) = 1 -0.3 = 0.7. Thus, the corresponding plausibilities used as label are equal to pl ik * = 1 and pl ik = 0.3 for k = k * . Influence of Label Imprecision on Estimation Accuracy First, we investigated with such principle the influence of labels on estimation accuracy. The following simulations were performed. For each learning set size N ∈ {1000, 2000}, N samples in a ten-dimensional feature space were drawn from a two component normal mixture with common identity covariance matrix and balanced proportions. The distance between the two centers δ = ||µ 1µ 2 || was varied in {1, 2, 4}, in order to study different cases from strongly overlapping to well separated classes.For each generated sample, a nonspecificity value N S was drawn randomly from a uniform distribution in [ns -0.05, ns + 0.05] with ns ∈ {0.05, 0.1, 0.15, . . . , 0.95} and a soft label with that nonspecificity value was built as explained above. For each learning set size N , mean nonspecificity ns and distance δ between centers, two hundred learning sets were generated. The accuracy measure was the empirical classification error rate of the trained classifier estimated on a test set of 5000 samples. As there is no model bias, differences in empirical classification error are only due to differences in estimation accuracy. Finally, to avoid the problem of local maxima, the EM algorithm was initialized with the parameters of the true distributions: in this way, it is guaranteed to pick among all local maxima of the log-likelihood function the one which is in the basin of attraction of the optimal value.

Figure 2

 2 Figure2shows blox-plots of estimated error rates for the 200 learning sets in each configuration (N, ns, δ). It clearly shows the influence of label imprecision when the estimation problem is

(f) δ = 4 , N = 2000 Fig. 2 .

 420002 Fig. 2. Boxplots (over 200 independent learning sets) of empirical classification error rates (%) as a function of average nonspecificity of learning set labels ns ∈ {0.5, . . . 0.95}, (results of supervised learning ns = 0 and unsupervised learning, ns = 1 are also shown), for two learning set sizes (N = 1000 or N = 2000) and different distances between the two centers of the components (δ ∈ {1, 2, 4}).

  Non-specificity Mean # iterations before convergence (b) Number of iterations before convergence

Fig. 3 .

 3 Fig. 3. (a) Number of local maxima detected over 200 random initializations for the EM algorithm, (b) number of iterations until convergence, as a function of average label nonspecificity.

Fig. 4 .

 4 Fig. 4. Empirical classification error rates estimated by ten-fold cross validation (%) averaged over 100 independent label sets, as a function of the asymptotic error rate of the training labels (%), and for different sample sizes. The results were obtained using soft labels with discounting (-.+), supervised learning (- * ), unsupervised learning (--o), adaptive semi-supervised learning (..•) and the probabilistic label noise model (-£).

Fig. 5 .

 5 Fig. 5. Empirical classification error rates estimated by ten-fold cross validation (%) averaged over thirty independent label sets, as a function of the asymptotic error rate of the training labels (%), and for different real datasets. The results were obtained using soft labels with discounting (-.+), supervised learning (- * ), unsupervised learning (--o), adaptive semi-supervised learning (..•) and probabilistic label noise model (-£).

Table 1

 1 Empirical classification error rates (%) averaged over one hundred independent datasets, for different asymptotic labelling error rates (%) and learning set sizes. Error rates in bold are significantly lower than other error rates at the 5 % level according to paired two-sided sign tests.

		Expert asymptotic error rate (%)
	10	15	20	25	30	35	40

Table 2 Characteristics

 2

	of real datasets.
	name	# dimensions # samples # classes
	Iris	4	150	3
	Crabs	5	200	4
	Wine	13	178	3
	Breast Cancer Wisconsin	30	569	2

Table 3

 3 Empirical classification error rates estimated by ten-fold cross validation (%) over thirty independent label sets, with respect to expert's asymptotic error rate on training labels, and for different real problem. Error rates in bold are significantly lower than other error rates at the 5 % level according to paired two-sided sign tests.

		Expert asymptotic error rate (%)
	10	15	20	25	30	35	40

hal-00446583, version 1 -13 Jan 2010

Two local maxima were supposed to be distinct if the distance between the vectors containing all the parameters was larger than 0.001.

http://mlearn.ics.uci.edu/MLRepository.html and http://rweb.stat.umn.edu/R/library/MASS/html/crabs.html.

The centers were drawn according to a Gaussian distribution estimated on the whole population, the covariance matrix were all initialized with the one estimated on the whole dataset and the proportions were set to be equal.