Sébastien Destercke
email: destercke@cirad.fr

Patrice Buche

Brigitte Charnomordic

Data reliability assessment in a data warehouse opened on the Web

This paper presents an ontology-driven workflow that feeds and queries a data warehouse opened on the Web. Data are extracted from data tables in Web documents. As web documents are very heterogeneous in nature, a key issue in this workflow is the ability to assess the reliability of retrieved data. We first recall the main steps of our method to annotate and query Web data tables driven by a domain ontology. Then we propose an original method to assess Web data table reliability from a set of criteria by the means of evidence theory. Finally, we show how we extend the workflow to integrate the reliability assessment step.

Introduction

The huge amount of technical and scientific documents available on the Web include many data tables. In addition to local data sources, they represent big potential external data sources for the data warehouse of a company dedicated to a given domain of application. To lighten the burden laid upon domain experts when selecting data from the data warehouse for a particular application, it is necessary to give them indicative reliability evaluations. In this paper, we present a framework to estimate the reliability of data tables collected from the Web. Compared to more ad-hoc estimation, the presented generic method can give insights to the expert as to why a particular data table is tagged as reliable or not reliable. Due to its generic nature, this method can be reused in other data warehouses using the semantic web recommended languages.

Reliability estimation is an essential part of the Semantic Web architecture, and many research works [START_REF] Gil | Towards content trust of web resources[END_REF] focus on issues such as source authentification, reputation, etc. For example, [START_REF] Quinn | An analysis of accuracy experiments carried out over a multi-faceted model of trust[END_REF] advocates a multi-faceted approach to trust models. They propose an OWL based ontology of trust related concepts. The idea is to provide systems using the annotation power of a user community to collect information about reliability. Our approach is different, as we do not rely on users but rather on information about the Web data table origins to compute a reliability estimations. Among methods proposing solutions to evaluate trust or data quality in web applications, the method presented in [START_REF] Denguir-Rekik | A possibilistic-valued multi-criteria decisionmaking support for marketing activities in e-commerce: Feedback based diagnosis system[END_REF] is close to the method presented in the paper. It uses possibility theory evidence theory, whereas we base our method on evidence theory. Another difference is that in our approach global information is obtained by a fusion of multiple uncertainty models, while in [START_REF] Denguir-Rekik | A possibilistic-valued multi-criteria decisionmaking support for marketing activities in e-commerce: Feedback based diagnosis system[END_REF] global information results from the propagation of uncertainty models through a aggregation function. Each method has its pro and cons: it is easier to integrate interactions between criteria in aggregation functions, while it is easier to retrieve explanations of the final result in our approach.

In this paper, we details our method and its integration in @Web, along with the whole workflow used in @Web. The current version of @Web (see [START_REF] Buche | Flexible sparql querying of web data tables driven by an ontology[END_REF][START_REF] Hignette | Fuzzy annotation of web data tables driven by a domain ontology[END_REF]), a Webenabled data warehouse, has been implemented using the W3C recommended languages (see [START_REF] Antoniou | A semantic Web primer[END_REF] for details about these languages): OWL to represent the domain ontology, RDF to annotate Web tables and SPARQL to query annotated Web tables.

We first recall in Section 2 the purpose and architecture of the data warehouse. Section 3 details the proposed method to assess Web data table reliability. In Section 4, we show how this reliability assessment is presented and explained to the user. Finally, in Section 5, we explain how @Web is extended to implement the reliability management.

@Web presentation

Fig. 1. Main steps of the document workflow in @Web @Web is a data warehouse opened on the Web [START_REF] Buche | Flexible sparql querying of web data tables driven by an ontology[END_REF][START_REF] Hignette | Fuzzy annotation of web data tables driven by a domain ontology[END_REF] centered (in its current version) on the integration of heterogeneous data tables extracted from Web documents. The focus has been put on Web tables for two reasons: (i) experimental data are often summarized in tables, (ii) table structured data are easier to integrate than, e.g., in text or plots. The main steps of Web table integration are summarised in Fig. 1. A central role in data integration in @Web is played by the domain ontology. This ontology describes the concepts, their relations and the associated terminology of a given application domain. @Web can therefore be instantiated for any application domains (e.g., food predictive microbiology, food chemical risks, aeronautics [START_REF] Hignette | Fuzzy annotation of web data tables driven by a domain ontology[END_REF]), provided a proper domain ontology is defined.

Once the ontology is built, @Web workflow includes the different steps shown in Fig. 1 to integrate new data in the warehouse. Concepts found in a data table and semantic relations linking these concepts are automatically identified. Data tables are then annotated with the identified concepts, allowing users to interrogate and query the data warehouse in an homogeneous way.

Our case study uses the @Web instance implemented in the Sym'Previus [START_REF] Buche | Flexible querying of web data to simulate bacterial growth in food[END_REF] decision support system whose aim is to simulate the growth of a pathogenic microorganism in a food product. Semantic relations in this system include for instance the GrowthRate that links a given microorganism within a given food product to a specific growth rate and its associated parameters. Data retrieved from tables can then be used to define the parameters of numerical growth oriented simulated models.

@Web generic ontology

The current OWL ontology representation used in the @Web system is composed of two main parts: a generic part, called core ontology, which contains the structuring concepts of the Web table integration task, and a specific part, commonly called domain ontology, which contains the concepts specific to the considered domain. The core ontology is composed of symbolic concepts, numeric concepts and relations between these concepts. It is separated from the definition of the concepts and relations specific to a given domain, i.e., the domain ontology. All the ontology concepts are materialized by OWL classes. For example, in the microbiological ontology, the respectively symbolic and numeric concepts Microorganism and pH are represented by OWL classes, respectively subclass of the generic classes SymbolicConcept and NumericConcept. An excerpt of an OWL class organization for symbolic concepts is given in Figure 2.

@Web workflow

The first three steps of @Web workflow (see Fig. 1) are as follows. The first task consists in retrieving relevant Web documents for the application domain, using key-words extracted from the domain ontology. It does so by defining queries executed by different crawlers. In the second task, data tables are extracted from the retrieved documents and are semi-automatically translated into a generic XML format. The Web tables are then represented in a classical and generic way -i.e., a set of lines, each line being a set of cells. In the third task, the Web tables are semantically annotated according to the domain ontology. The semantic annotation process of a Web table consists in identifying which semantic relations of the domain ontology can be recognized in each row of the Web table (see [START_REF] Hignette | Fuzzy annotation of web data tables driven by a domain ontology[END_REF] for details). This process generates RDF descriptions.

SPARQL querying of RDF graphs

In the XML/RDF data warehouse, the querying is done through MIEL++ queries. We briefly recall how MIEL++ queries are executed in the current version of @Web (For details, see [START_REF] Buche | Flexible sparql querying of web data tables driven by an ontology[END_REF]). A MIEL++ query is asked in a view that corresponds to a relation of the ontology (e.g., the relation GrowthParameterAwMin). A MIEL++ query is an instanciation of a view by the end-user, who specify among the set of querryable attributes of the view what are the selection attributes and their searched values, and what are the projection attributes (with the meaning of the relational model). An important specificity of a MIEL++ query is that searched values may be expressed as fuzzy sets (see [START_REF] Zadeh | Fuzzy sets[END_REF][START_REF] Buche | Towards a unified querying system of both structured and semistructured imprecise data using fuzzy views[END_REF][START_REF] Thomopoulos | Different kinds of comparison between fuzzy conceptual graphs[END_REF]), which use allows end-users to represent their preferences in a gradual way.

Definition 1 A fuzzy set µ defined on a space A is a function µ : A → [0, 1] with µ(x) the membership degree of x. The support S(µ) and the kernel K(µ) of a fuzzy sets are the sets

S(µ) = {x ∈ A |µ(x) > 0} and K(µ) = {x ∈ A |µ(x) = 1}.
Example 3. Let us define a MIEL++ query Q expressed in the view GrowthParameter-AwMin as follows:

Q ={Microorganism, aw |(GrowthParameterAwMin(Microorganism, aw)∧ (Microorganism ≈ MicroPreferences) ∧ (aw ≈ awPreferences)}.
The discrete fuzzy set MicroPreferences, which is equal to {(Gram+,1.0), (Gram-,0.5)}, means that the end-user is firstly interested in microorganisms which are Gram+ and secondly Gram-. The trapezoidal fuzzy set awPreferences that has the characteristic points [0.9, 0.94, 0.97, 0.99], means that the end-user is first interested in aw values in the interval [0.94, 0.97] (the kernel of the fuzzy set), but that he/she accepts to enlarge the querying till the interval [0.9, 0.99] (the support of the fuzzy set).

Since fuzzy sets are not supported in a standard SPARQL query, a complete solution to translate a MIEL++ query into a standard SPARQL query is presented in detail in [START_REF] Buche | Flexible sparql querying of web data tables driven by an ontology[END_REF]. In this paper, we only recall how is measured the satisfaction of a MIEL++ query. The satisfaction of a selection criterion att ≈ attPre f is measured by the membership degree µ attPre f (x) of the corresponding value x expressed in the RDF graph (x is supposed to be a crisp value in this paper). As selection criteria are considered to be conjunctive, a global adequation degree, denoted ad, is computed using the t-norm min.

Reliability evaluation

This section describes the method we propose to evaluate the reliability of Web tables.

A model for reliability evaluation

We assume that reliability takes its value on a finite ordered space Θ = θ 1 , . . . , θ N such that θ i < θ j iff i < j. θ 1 corresponds to total unreliability, while θ N corresponds to total reliability. We denote by

I a,b = {θ a , . . . , θ b } a set such that a ≤ b and ∀ c s.t. a ≤ c ≤ b, θ c ∈ I a,b .
Such sets include all values between their minimum value θ a and maximum value θ b , and using a slight stretch of language we call them intervals. The evaluation will be based on the values taken by S groups A 1 , . . . , A S of criteria. Note that a group may be composed of multiple criteria, e.g., number of citation × publication date.The group constitution ensures that the impact of each group A i on the reliability evaluation can be judged (almost) independent of the impact of any other group A j . Each group A i can assume C i distinct values on spaces A i = {a i1 , . . . , a iC i }.

For each possible value of each criteria group A 1 , . . . , A S , a domain expert is asked to give its opinion about the corresponding data reliability. To facilitate expert elicitation, a linguistic scale with a reasonable number of terms is used, for instance the five terms very unreliable, slightly unreliable, neutral, slightly reliable and very reliable. These opinions are modeled as fuzzy sets that describes some ill-known value of reliability. Denote by F (Θ ) the set of all fuzzy sets defined over a domain Θ . For each group A i , we define a mapping Γ A i : A i → F (Θ ) according to the expert opinions, such that Γ A i (a) with a ∈ A i is the interpretation on Θ of the information provided by A i = a about the reliability. We denote by µ a the fuzzy set Γ A i (a).

The expert may select from a limited number of linguistic terms as well as combination of them, using "or" disjunctions 1 . An additional term allows to express total ignorance. A fuzzy set on Θ is then associated to each term. Fig. 5 provides an illustration of a fuzzy set corresponding to the term very reliable. The expert then provides his opinion about the reliability value for the different values of these two criteria. These opinions are summarised below µ a 11 = very reliable, µ a 12 = slightly reliable, µ a 13 = neutral, µ a 14 = slightly unreliable; µ a 21 = very reliable, µ a 22 = slightly unreliable.

Global reliability information through merging

For a given data table each group A i takes a particular value, hence S different fuzzy sets are provided as pieces of information. We propose to use evidence theory [START_REF] Shafer | A mathematical Theory of Evidence[END_REF] to merge these information in a global reliability assessment. Indeed, this theory comes with a rich choice of merging rules [START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF], together with a good compromise between expressiveness and tractability. It encompasses fuzzy sets and probability distributions as special cases. We recall here the basics of the theory and its links with fuzzy sets.

A basic belief assignment (bba) m on a space Θ is a mapping from the power set 2 |Θ | of Θ onto the unit interval [0, 1], such that ∑ E⊆Θ m(E) = 1 and m( / 0) = 0. Sets E such that m(E) > 0 are called focal elements. We denote by F m the set of focal elements of m. The mass m(E) can be interpreted as the probability that the most precise description of what is known about a particular situation is of the form "x ∈ E". From this mass assignment, Shafer [START_REF] Shafer | A mathematical Theory of Evidence[END_REF] defines two set functions, called belief and plausibility functions, for any event A ⊆ Θ :

Bel(A) = ∑ E,E⊆A m(E); Pl(A) = 1 -Bel(A c ) = ∑ E,E∩A = / 0 m(E),
where the belief function measures the certainty of A (i.e., sums all masses that cannot be distributed outside A) and the plausibility function measures the plausibility of A (i.e., sums all masses that it is possible to distribute inside A).

A fuzzy set µ with M distinct membership degrees 1 = α 1 > . . . > α M > α M+1 = 0 defines a bba m having, for i = 1, . . . , M, the focal elements E i with masses m(E i ) [START_REF] Dubois | On several representations of an uncertain body of evidence[END_REF]:

E i = {θ ∈ Θ |µ(θ ) ≥ α i } = A α i , m(E i ) = α i -α i+1 . (1)
Therefore, each fuzzy set provided by experts during information collection can be mapped into an equivalent bba.

Example 6. Consider the fuzzy set depicted in Fig. 5. Its equivalent bba m is such that

m(E 1 = {θ 5 }) = 0.5, m(E 2 = {θ 4 , θ 5 }) = 0.4, m(E 3 = {θ 3 , θ 4 , θ 5 }) = 0.1.
When S groups of criteria (called sources in the sequel) provide pieces of information modelled as bbas m 1 , . . . , m S over a same space Θ , it is necessary to merge them into a global model. Two main issues related to merging rules are the handling of (i) dependence [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF] and of (ii) conflict [START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF] between sources.

Here, sources are selected to remain as independent as possible, therefore tackling the first issue. We are thus left with the problem of properly handling conflicting information. Given the fact that sources are independent, the merging of bbas m 1 , . . . , m S can be written,

∀E ⊆ Θ m(E) = ⊕ S i=1 (E i )=E ∑ E i ∈F i S ∏ i=1 m i (E i ), (2)
with F i the focal elements of m i , and ⊕ S i=1 (E i ) = E an aggregation operator on sets. Note that TBM conjunctive rule and the disjunctive rule [START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF] are retrieved when ⊕ = ∩ and ⊕ = ∪, respectively. However, the former is not adapted to the case of conflicting information, while the latter often results in a very imprecise model.

To deal with the problem of conflicting information, we propose a merging strategy based on maximal coherent subsets (MCS). Given a set of conflicting sources, MCS consists in applying a conjunctive operator within each non-conflicting subset of sources, and then using a disjunctive operator between the partial results [START_REF] Dubois | Multi-source information fusion: a way to cope with incoherences[END_REF]. Consider N = {I a 1 ,b 1 , . . . , I a k ,b k } a set of k intervals. Using the MCS method on such intervals consists in taking the intersection over subsets K j ⊂ N s.t. ∩ i∈K j I a i ,b i = / 0 that are maximal with this property, and then in considering the union of these intersections as the final result (i.e. ∪ j ∩ i∈K j I a i ,b i ). We denote by ⊕ MCS the MCS aggregation operator. In general, detecting MCS is NP-hard, however in the case of intervals over an ordered space (our case here), the algorithm proposed in [START_REF] Dubois | Multi-source information fusion: a way to cope with incoherences[END_REF] reduce this complexity drastically.

An application of MCS on four (real valued) intervals I 1 , I 2 , I 3 , I 4 is shown in Fig. 6. The two MCS are (I 1 , I 2 ) and (I 2 , I 3 , I 4 ) and the final result is

(I 1 ∩ I 2 ) ∪ (I 2 ∩ I 3 ∩ I 4 ).
Note that, if all intervals are consistent, conjunctive merging is retrieved, while disjunction is retrieved when every pair of intervals conflicts. As we shall see, the groups of intervals forming maximal coherent subsets may be used as elements explaining the result. Applying MCS in our case comes down to apply Eq. ( 2) with ⊕ = ⊕ MCS to the fuzzy sets µ a i j , a i j ∈ A i once they have been transformed into bbas (thanks to Eq. ( 1)).

I 1 I 2 I 3 I 4 (I 1 ∩ I 2 ) (I 2 ∩ I 3 ∩ I 4 )
Fig. 6. Illustration of maximal coherent subsets merging.

Example 7. Consider the two groups of Example 5. Now, assume that the retrieved data come from a journal paper (A 1 = a 11 ) but that the experiment has not been repeated (A 2 = a 22 ). Value a 11 corresponds to "very reliable", while a 22 corresponds to "slightly unreliable". Each group A i thus provides an individual bba corresponding to the criterion value. These bbas are given in the following table:

E 11 = {θ 3 , θ 4 , θ 5 } E 12 = {θ 4 , θ 5 } E 13 = {θ 5 } m a 11 0.1 0.4 0.5 E 21= {θ 1 , θ 2 , θ 3 } E 22 = {θ 2 , θ 3 } E 23 = {θ 2 } m a 22 0.1 0.4 0.5
We denote by j i the index of the criterion value for a given data item, and m g the bba obtained by merging m a 1 j 1 , . . . , m a S j S through Equation ( 2) with ⊕ = ⊕ MCS . The merging result of the bbas given in Example 7 is summarised in Table 1.

Reliability presentation and explanation

A look at Table 1 tells us that the merging result is hard to read, and that it is necessary to provide tools that summarize this information in a digestible representation. Given a set

Criteria in MCS MCS focal sets

Focal set Mass of focal set

{A 1 , A 2 } E 11 ∩ E 21 + E 11 ∩ E 22 {θ 3 } 0.05 {A 1 } and {A 2 } E 11 ∪ E 23 + E 12 ∪ E 22 {θ 2 , . . . , θ 5 } 0.21 {A 1 } and {A 2 } E 12 ∪ E 21 {θ 1 , . . . , θ 5 } 0.04 {A 1 } and {A 2 } E 12 ∪ E 23 {θ 2 , θ 4 , θ 5 } 0.20 {A 1 } and {A 2 } E 13 ∪ E 21 {θ 1 , θ 2 , θ 3 , θ 5 } 0.05 {A 1 } and {A 2 } E 13 ∪ E 23 {θ 2 , θ 5 } 0.25 {A 1 } and {A 2 } E 13 ∪ E 22 {θ 2 , θ 3 , θ 5 } 0.2
Table 1. Example of merging independent information using MCS D = {e 1 , . . . , e d } of d data, we propose three complementary means to summarise their reliability evaluations: by ordering them, by providing a summarising (quantitative) interval and by explaining the main reasons for the reliability evaluation.

In this section, we use the notion of lower and upper expectations of a function f : Θ → R induced by a bba m g . These lower and upper expectations are defined as

E g ( f ) = ∑ A⊆Θ m(A) min θ ∈A f (θ ) and E g ( f ) = ∑ A⊆Θ m(A) max θ ∈A f (θ ). (3)
They correspond to the infimum and supremum values of all expectations of f w.r.t. probability measures dominating the belief function induced by m g .

Comparing, evaluating and ordering data

Let m g 1 , . . . , m g d be the global bbas representing our knowledge about the reliability of e 1 , . . . , e d . We propose to induce an order between them by using numerical comparison of interval-valued estimations, using a particular function in Eq. ( 3). We propose to consider f Θ : Θ → R such that f Θ (θ i ) = i (each θ i receives its rank as value), and to summarize the reliability of data item e i by the interval [E g i ( f Θ ), E g i ( f Θ )] (obtained by using Eq. ( 3)).

Example 8. Consider the three bbas m g 1 , m g 2 , m g 3 respectively representing the reliability of e 1 , e 2 , e 3 (e.g. resulting from the merging process illustrated in Example 7), defined over Θ = {θ 1 , . . . , θ 5 } such that

m g 1 ({θ 1 , θ 2 , θ 3 }) = 0.3, m g 1 ({θ 2 , θ 3 }) = 0.7; m g 2 ({θ 3 , θ 4 }) = 0.5, m g 2 ({θ 4 , θ 5 }) = 0.5; m g 3 ({θ 1 }) = 0.4, m g 3 ({θ 5 }) = 0.4, m g 3 ({Θ }) = 0.2.
Corresponding reliability intervals are:

[E g 1 ( f Θ ), E g 1 ( f Θ )] = [1.7, 3]; [E g 2 ( f Θ ), E g 2 ( f Θ )] = [3.5, 4.5]
;

[E g 3 ( f Θ ), E g 3 ( f Θ )] = [2.6, 3.4].
Partial order: We propose to order the bbas according to the (partial) order

≤ E s.t. m g ≤ E m g iff E g ( f Θ ) ≤ E g ( f Θ ) and E g ( f Θ ) ≤ E g ( f Θ ).
In Example 8, we have e 1 < E e 3 < E e 2 (further on, we make no difference between a datum e i and its bba m g i ), obtaining in this case a complete order among the objects. However, as ≤ E is in general a partial order, we propose an algorithm allowing to build from it a complete (pre-)order, so that users are provided with an ordered list, easier to understand and interpret.

Building groups: The next step is to order data by groups of decreasing reliability according to the order ≤ E , i.e., to build an ordered partition {D 1 , . . . , D O } of D, where D 1 corresponds to the most reliable data. Given a subset F ⊆ {e 1 , . . . , e d }, denote by opt(E, F) the set of optimal data in the sense of reliability, i.e. not dominated w.r.t. ≤ E opt(E, F) = {e i ∈ F| ∃e j ∈ F, such as e i ≤ E e j }.

The partition {D 1 , . . . , D O } can now be defined recursively as follows:

D i = opt(E, ({e 1 , . . . , e d } \ i-1 j=0 D j )) with D 0 = / 0. ( 4
)

Explaining the results

Another interest of MCS is that they give insights about the reasons that have led to a particular reliability assessment, providing the user with some possibly useful explanations. Indeed, according to our method, the more often a subgroup F of MCS appears in ⊕ S i=1 (E i ) = E (see Eq. ( 2)), the more important its impact is on the global reliability score m g . Therefore, we propose to measure the importance w(F) of a MCS F in m g by summing all the masses of m g for which it has been a maximal coherent subset, that is

w(F) = { ∑ S ∏ i=1 m i (E i )|F is an MCS of ⊕ S i=1 (E i )}
Example 9. In Table 1, the impact w of the different encountered MCS is evaluated as follows: w({A 1 }) = 0.95, w({A 2 }) = 0.95, w({A 1 , A 2 }) = 0.05, from which it can be inferred that the two criteria {A 1 } and {A 2 } appear often alone and do not agree with each other. This means that the imprecision in the final reliability representation can be explained by the conflict between criteria A 1 and A 2 .

In this example, the analysis is straigthforward. However, when dealing with thousands of data and half a dozen of criteria groups, such tools may help users to perform a quick analysis and retain the data that best serve their purposes.

Extending @Web for data reliability management

This section describes the change made to @Web to add a reliability estimation to each Web table and to use them in the display of a user query result. As data from a same table often come from a same experiment, table level has been retained to model reliability.

Extending the ontology to include reliability criteria

Some criteria retained for reliability estimation are part of the domain knowledge. For example, measurements methods to count micro-organisms all roughly have the same precision, while the accuracy of methods to appreciate wheat grain size greatly varies. Therefore, it is natural to include criteria in the domain ontology. This solution allows designers to adapt the choice of the criteria associated with each domain of application, preserving the @Web generic approach at the same time.

In the extended version of the ontology integrating reliability criteria, the core ontology is enriched with corresponding symbolic and numeric criteria. The domain ontology is completed by the definition of the criteria selected to evaluate the reliability, together with their possible values. For example, the respectively symbolic and numeric criteria SourceType and CitationNumber are represented by OWL classes and belong to the domain ontology. They are subclasses of the generic classes SymbolicCriterion and NumericCriterion, respectively, which belong to the core ontology. As for symbolic concepts, the possible values associated with a symbolic criterion are represented by OWL classes that are subclasses of the OWL class representing the criterion.

Storing data reliability criteria in RDF graphs

In extended @Web, an additional fourth task concerns the reliability management (see Figure 1). Users manually enter the values associated with the reliability criteria for each Web table. This information is stored in a RDF graph associated with the table. The fourth task output of the extended @Web system is an XML/RDF data warehouse composed of a set of XML documents which represent Web tables, together with the RDF annotations corresponding to the recognized semantic relations and the reliability criteria values.

SPARQL queries and data reliability

To evaluate the reliability of the answers associated with a MIEL++ query, the following post-processing is executed. Reliability criteria associated to a Web table are retrieved thanks to SPARQL queries (generated by using the ontology). Each answer associated with a given row of a Web table is then associated to its reliability interval thanks to its URI which links it to its original table. Answers are then compared and ordered according to methods of Sec. 4.

In this paper, we have proposed a method that evaluates reliability of Web data tables by using sets of criteria concerning the data origins. This method, based on evidence theory, is generic and can be applied to any domain once proper criteria have been defined. Special attention has been given to tractability and ease of use. A first possible perspective of this work should be to take account of possible uncertainty in the criteria values. In the present paper, we have considered that criteria were known. It would be desirable to consider the case where some criteria are ill-known (using bbas to describe this uncertainty). A second possible perspective would be to extend our approach to cope with multiple experts providing (possibly) different opinions about the same criteria.

Fig. 2 .

 2 Fig. 2. Excerpt of OWL class hierarchy for symbolic concepts in the microbial domain

Example 2 .

 2 Figure 4 presents the main part of the RDF descriptions corresponding to the recognition of the relation GrowthParameterAwMin in the first row (denoted uriRow1) of the Web table given by Fig. 3. Starting from the left part of the figure, we see that the row is annotated by the relation GrowthParameterAwMin, abbreviated as GPaw1. The domain of the relation GrowthParameterAwMin is an instance of the symbolic concept Clostridium. The range of the relation is an instance of the numerical concept Aw and has for value 0.943.

Fig. 4 .

 4 Fig. 4. Example of RDF annotations generated from the Web table ofFigure 3

Example 4 .

 4 The answers to the SPARQL query associated with the MIEL++ query of Example 3 compared with the Web table presented in Figure3is given below:ad µ MicroPre f (x) µ AwPre f (x)

θ 1 θ 2 θ 3 θ 4 θ 5 Fig. 5 .

 55 Fig. 5. Fuzzy set corresponding to the term very reliable defined on Θ with N = 5.

Example 5 .

 5 Consider the two groups A 1 = source type and A 2 = experience repetition such that A 1 = {a 11 = journal paper, a 12 = governmental report, a 13 = project report, a 14 = other} A 2 = {a 21 = repetitions, a 22 = no repetition}

Example 10 .

 10 Fig. 7 presents the RDF descriptions representing the reliability criteria and values associated with the Web table of

Fig. 3 .

 3 They express that the table (having the uriTable1 identifier within the XML document) has for associated criteria the same values than in Example 7: journal paper and no repetitions of experiments.

Fig. 7 .

 7 Fig. 7. Example of RDF annotations associated with the Web table ofFigure 3

Figure 3

 3 Fig. 7. Example of RDF annotations associated with the Web table ofFigure 3

  Fig.3presents an example of a Web table in which the semantic relation GrowthParameterAwMin has been identified. The domain of this relation is a kind of Microorganism and its range is food product water activity (a w ). The first row indicates that Clostridium requires a minimal food product a w of 0.943 to be able to grow.

	Organism a w minimum a w optimum a w maximum
	Clostridium	0.943	0.95-0.96	0.97
	Staphylococcus	0.88	0.98	0.99
	Salmonella	0.94	0.99	0.991
	Fig. 3. Example of a Web table
	Example 1.

In this case, fuzzy sets are combined by the classical t-conorm max


Sébastien Destercke
email: sdestercke@gmail.com

Benjamin Quost
email: quostben@hds.utc.fr

Combining binary classifiers with imprecise probabilities

This paper proposes a simple framework to combine binary classifiers whose outputs are imprecise probabilities (or are transformed into some imprecise probabilities, e.g., by using confidence intervals). This combination comes down to solve linear programs describing constraints over events (here, subsets of classes). The number of constraints grows linearly with the number of classifiers, making the proposed framework tractable even for problems involving a relatively large number of classes.

Introduction

In complex multi-class classification problems, it often makes sense to decompose the initial problem into several simpler ones, training simple classifiers on each of these problems and then combining their results. This is the central idea of technics such as Boosting or classifiers combinations [START_REF] Bishop | Pattern Recognition and Machine Learning (Information Science and Statistics)[END_REF]Ch.14].

In this paper, we deal with the case where each simple problem is a binary one, and where each classifier task is to tell two subsets of classes apart. When those classifiers return conditional probabilities estimating whether an instance belong to a given class subset, these conditional probabilities are seldom consistent, due to the fact that they are only approximations of the (admittedly) true but unknown conditional probabilities.

Usually, this inconsistency problem is tackled by considering some optimisation problem whose solution is a consistent probability whose conditional probabilities are close to each of the estimated ones [START_REF] Hastie | Classification by pairwise coupling[END_REF][START_REF] Wu | Probability estimates for multi-class classification by pairwise coupling[END_REF]. This consistent probability is then considered as the final predictive model.

In this paper, we address the problem from a slightly different viewpoint, that is the one of imprecise probabilities. Imprecise probabilities [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF] are concerned with the cases where the available information is not sufficient (or too conflicting) to identify a single probability distribution as our model of uncertainty. They are therefore fit to deal with the problem of combining inconsistent (precise or imprecise) conditional probabilities. Instead of searching for a close (w.r.t. some objective function) consistent solution, we suggest to weaken the given conditional assessments to make them consistent, and to consider the resulting set of probabilities as our final predictive model. Due to their robustness, imprecise probabilistic models appear particularly interesting in those cases where some classes are difficult to separate, where some classes are poorly represented in the training set or when the data are very noisy.

In this paper, after a brief reminder about imprecise probabilities (Section 2), we first describe (Section 3) how binary classifiers returning imprecise probabilities (precise probabilities then becoming a special case) as their conditional assessments can be combined. As this combination can still lead to inconsistent results (i.e., non-feasible linear programs), we then propose a discounting strategy ensuring that a consistent (but possibly non-informative) result will be reached (Section 4). Finally, we make some first experiments for the special case of one-vs-one classifiers on simulated and well-known data sets, considering both the case of precise and imprecise classifiers (Section 5).

Imprecise probability: a short introduction

Let X = {x 1 , . . . , x M } be a finite space of M elements describing the possible values of (ill-known) variables (here, X consists in the classes of an instance). In imprecise probability, the uncertainty about a variable X true value is described by a convex set of probablities P, often called credal set [START_REF] Levi | The Enterprise of Knowledge[END_REF]. A classical way to describe this set is by giving a set of linear constraints restricting the set of possible probabilities in P (Walley's lower previsions [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF] correspond to bounds of such constraints).

Credal sets have been proposed as models of uncertainty when available information does not allow one to identify a unique probability of interest. In this paper, we propose to apply the imprecise probabilistic framework to the combination of binary classifiers.

From a credal set P, one can compute lower and upper probabilities P , P such that, for any event A ⊆ X , P (A) = inf P ∈P P (A) and P (A) = sup

P ∈P P (A).
They are dual, in the sense that P (A) = 1 -P (A c ), with A c the complement of A. More generally, given a real-valued and bounded function f on X , one can compute lower and upper expectation bounds E, E such that

E(f ) = sup p∈P E(f ) and E(f ) = inf p∈P E(f ).
with E the expected value of f w.r.t. p. They are also dual, in the sense that E(f ) = -E(-f ). Note that lower and upper probabilities of an event A equal the lower and upper expectations of its indicator function. Alternatively, one can start from constraints on expected or probability values and take the set of probabilities satisfying these constraints.

Combining binary classifiers with imprecise probabilities

The basic task of classification is to predict the class or output value x of an object knowing some of its characteristics or input values y assuming their value in some space Y. Usually, it is assumed that to a given input y correspond a probability mass p(x|y) modelling the class distribution under input y. Classification then amounts to estimate as accurately as possible p(x|y) from a limited set of training samples.

A binary classifier on a set of classes X aims at predicting whether an instance class belongs to a subset A ⊆ X or to a (disjoint) subset B ⊆ X (i.e., A ∩ B = ∅). Its prediction is then an estimation of the conditional probability P (A|A ∪ B, y) that the instance belongs to A (P (B|A ∪ B, y) = 1 -P (A|A ∪ B, y) by duality). 3 Combining binary classifier then consists in finding p from a set of such conditional assessments.

To model a set of binary classifiers, we will use the language of code correction matrices. A code correction matrix is a matrix C with general element c ij ∈ {+1, 0, -1}, i ∈ 1, . . . , M with M the number of classes, and j ∈ 1, . . . , N with N the number of binary classifiers to combine. For a given column j, the sets A j = {x i |c ij = 1, i = 1, . . . , M } and B j = {x i |c ij = -1, i = 1, . . . , M } are the positive and negative classes that classifier j separates. We now recall the combination problem in a precise setting and then extend it to an imprecise setting.

The precise case

In the precise case, classifier j returns a precise evaluation P (A j |A j ∪ B j ) = α j . Using the fact that P (A j |A j ∪ B j ) = P (Aj ) /P (Aj ∪Bj ) and P (B j |A j ∪ B j ) = P (Bj ) /P (Aj ∪Bj ) = 1 -P (A j |A j ∪ B j ), we obtain from these two equations the following equality4

P (A j ) = α j 1 -α j P (B j ).
This gives N equalities that describe partial knowledge about the true but unknown probabilities. As the number of equalities will be usually much higher than the number M of elements of X , the problem will often be over-constrained and without solutions, as shows the next example.

Example 1. Consider a 3 classes problem X = {x 1 , x 2 , x 3 }. Assuming we are working with a one-against-one framework (each A j , B j is reduced to a singleton), consider the following output of classical probabilistic classifiers:

P ({{x 1 }|{x 1 , x 2 }}) = 0.2, P ({{x 1 }|{x 1 , x 3 }}) = 1 /3, P ({{x 2 }|{x 2 , x 3 }}) = 0.8.
These statements, once transformed to express unconditional constraints, respectively give the equalities (using the notation p i = p(x i ) = P ({x i }))

p 1 = 1 /4p 2 , p 1 = 1 /2p 3 , p 2 = 4p 3 ,
which lead (together with the consistency constraints xi∈X p i = 1, p i ≥ 0) to a system with no solutions.

The imprecise case

Let us now consider imprecise binary classifiers. The output of classifier j (or the transformation into imprecise probabilities of its precise output) will be a pair of values bounding the conditional probabilities on A j , B j . We will denote by α j , β j the bounds of P (A j |A j ∪ B j ), that is

α j ≤ P (A j |A j ∪ B j ) ≤ β j (1)
and, by complementation, we have

1 -β j ≤ P (B j |A j ∪ B j ) ≤ 1 -α j . (2)
To get a joint credal set from these constraints, we will turn them into linear constraints over unconditional probabilities. To get such constraints, we first transform equations ( 1) and ( 2) into (again assuming that P (A j ∪ B j ) > 0)

α j ≤ P (A j ) P (A j ∪ B j ) ≤ β j and 1 -β j ≤ P (B j ) P (A j ∪ B j ) ≤ 1 -α j .
By dividing these two equations, we reach the following inequality

α j 1 -α j ≤ P (A j ) P (B j ) ≤ β j 1 -β j ,
which can be transformed into two linear constraints

α j 1 -α j P (B j ) ≤ P (A j ) and P (A i ) ≤ β j 1 -β j P (B j ).
These equations can be restated as

α j 1 -α j xi∈Bj p i ≤ xi∈Aj p i and xi∈Aj p i ≤ β j 1 -β j xi∈Bj p i (3)
with p i := p(x i ). Such constraints correspond to a linear program inducing a credal set P of possible probabilities. If N classifiers are trained, then there are 2N such equations. This means that the number of constraints grows linearly with the number of classifiers, while the number of variables remains constant (= M ). As the quantity of classifiers will remain limited (usually between M and M 2 ), induced linear programs can be efficiently handled by modern optimisation techniques.

Example 2. Consider the same situation as in Example 1, but that classifiers provide the (slightly) relaxed system such that

1 /9p 2 ≤ p 1 ≤ 1 /2p 2 , 1 /5p 3 ≤ p 1 ≤ 2 /3p 3 , 2p 3 ≤ p 2 ≤ 4p 3 ,
corresponding to the classifier outputs

P ({{x 1 }|{x 1 , x 2 }}) ∈ [0.1, 1 /3], P ({{x 1 }|{x 1 , x 3 }}) ∈ [ 1 /6, 0.4] and P ({{x 2 }|{x 2 , x 3 }}) ∈ [ 2 /3, 0.8].
Note that the constraints of Example 1 are included in these ones. The above system is no longer without solution, e.g., p 1 = 0.1, p 2 = 0.6 and p 3 = 0.3 is an admissible solution. Getting the minimal/maximal probabilities for each class then comes down to solve 6 optimization problems (i.e., minimising and maximising the probabilities p i , that give

p 1 ∈ [0.067, 0.182] p 2 ∈ [0.545, 0.735] p 3 ∈ [0.176, 0.31].
Hence, we can safely choose x 2 as the right class in this case.

Admitting imprecision in the classifier output will not always result in a feasible problem. Such a situation corresponds to the case P = ∅. In the next section, we suggest a relaxation strategy to ensure that a given set of classifier outputs will end up in a feasible system (possibly providing a vacuous, i.e. noninformative, solution).

Handling inconsistent output: a discounting strategy

Here, we assume again that binary classifiers provide imprecise probabilistic outputs in the form of bounds [α j , β j ], j = 1, . . . , N (precise classifiers correspond to the case α j = β j ).

When the induced linear problem is not feasible, we propose to consider a discounting factor ∈ [0, 1] and to increase this factor up to the point where the linear problem becomes feasible (i.e. the associated credal set is no longer empty). For a given value , the -discounted problem corresponds, for j = 1, . . . , N , to the constraints

(1 -)α j ≤ P (A j |A j ∪ B j ) ≤ + (1 -)β j . (4)
Discounted constraints on P (B j |A j ∪ B j ) are obtained by complementation. Note that this discounting strategy is common in robust Bayesian literature as well as in other imprecise probabilistic approaches, since it corresponds to the -contamination model [START_REF] Berger | An overview of robust Bayesian analysis[END_REF] and to the basic discounting operation in evidence theory [START_REF] Mercier | Refined modeling of sensor reliability in the belief function framework using contextual discounting[END_REF]. We denote by P the credal set obtained by discounting the initial problem with a value . Such a strategy ensures that there will be at least one value of for which the problem will be feasible, as = 1 corresponds to trivial constraints P (A j |A j ∪ B j ) ∈ [0, 1], meaning that the set P 1 corresponds to the set of all probability measures on X . This alone is sufficient to ensure that the linear problem given by Eq. ( 4) will be feasible for some value . For a given instance, let us denote * the lowest value such that * = min ∈[0,1] P = ∅. * gives an indication of the global level of conflict of the various classifiers. Indeed, if * = 0 this means that all classifiers are consistent and no discounting is needed. On the contrary, if * 1 this means that at least one classifier gives a conditional information that is strongly conflicting with the others, and that a closer look should be taken to understand why such a conflict happens.

Also note that the obtained credal sets for different values of are nested in each others (i.e., P ⊆ P for any ≤ . This makes the current approach close to other similar models proposed in the imprecise probabilistic literature [START_REF] Cattaneo | Likelihood-based statistical decisions[END_REF][START_REF] Baudrit | Joint propagation of probability and possibility in risk analysis: towards a formal framework[END_REF][START_REF] De Cooman | A behavioural model for vague probability assessments[END_REF]. In the present work, the value should not be interpreted as having any statistical meaning in terms of confidence value. Indeed, linking to some statistical confidence value is the matter of further work.

Experiments

In this section, we perform some experiments on some classical and simulated data sets. In order to assess the results of Imprecise classifiers, we need at least two elements: how decision are taken, and how to evaluate performances when decisions are allowed to be imprecise (since imprecise probabilistic approaches allow for imprecise decisions. We first describe how this is done in the current study, before the detailing the experiment results.

Decision rules

Consider the set of classes X , and the knowledge we have about the class of an object given by the Constraints (3) (or a discounted problem). Imprecise probability theory offers many ways to make a decision about the possible class of an object [START_REF] Troffaes | Decision making under uncertainty using imprecise probabilities[END_REF]. Roughly speaking, classical decision based on maximal expected value can be extended in two ways: by a decision rule whose result is a unique class, or by a decision rule whose result is a set of possible optimal classes. We will retain a rule of each type: the maximin and interval dominance rules.

For a class x i ∈ X , its lower and upper probabilities P ({x i }), P ({x i }) are given by the solutions of the constrained optimisation P ({x i }) = min p i and P ({x i }) = max p i under the Constraints (3) and the additional constraints xi∈X p i = 1, p i > 0.

The maximin decision rule amounts to choose as the object class x such that

x := arg min xi∈X P ({x i }).

Using this rule requires to solve M linear systems with 2N + M + 1 constraints and to achieve M comparisons.

The interval dominance rule amounts to select as the possible optimal classes the set X such that

X := {x i ∈ X | ∃x j s.t. P ({x i }) ≤ P ({x j })}.
Using this rule requires to solve 2M linear systems with 2N + M + 1 constraints and to make M (M -1) comparisons at most. Its complexity is thus only slightly higher than the maximin rule. Also note that we have x ∈ X.

Evaluating classifiers performances.

Combined classifiers used with a maximin rule can be directly compared to classical classifiers or to more classical combinations, as both return a single class as output. In this case, accuracy is simply measured as a classical accuracy (acc) However, one of the main assets of imprecise probabilistic approaches is the (natural) ability to return sets of classes when information is ambiguous or not precise enough to return a single class. In this case, it can be hard to compare the IP classification output with a more classical one.

A solution is to use a discounted accuracy. Assume we have T observations whose classes x i , i = 1, . . . , T are known and for which T predictions X 1 , . . . , X T have been made. The discounted accuracy d -acc of the classifier is then

d -acc = 1 T T i=1 ∆ i f (| X i |) ,
with ∆ i = 1 if x i ∈ X i , zero otherwise and f an increasing function such that f (1) = 1. Although f (x) = x is a usual choice for the discounted accuracy, it has recently been shown [START_REF] Zaffalon | Utility-based accuracy measures to empirically evaluate credal classifiers[END_REF] that this choice leads to consider imprecise classification as being equivalent to make a random choice inside the set optimal classes. This comes down to consider that a Decision Maker is risk neutral, i.e., does not consider that having imprecise classification in case of ambiguity is an advantage. This means that to reward the robustness of imprecise classification, one should take a concave (i.e., risk-averse) function f . Since we think that returning an imprecise classification is an interesting feature and that classification robustness should be rewarded, we take here f (x) = (x).

In addition, when using the interval dominance rule, we have computed the set-accuracy s -acc = 1 /T T i=1 ∆ i as well as the average number of retained optimal classes on the instances that were well classed with the precise criterion and on those that were badly classed with the same criterion. This gives complementary information, as it allows to check whether imprecise classification mostly reject those cases that are difficult to classify.

Data-sets and set-up

In this case study, we performed the experiments on data sets issued from the UCI repository, whose details are recalled in Table 1, along with those of a synthetic data set Synth. Synth is a simulated data set consisting of four (partially overlapping) classes sampled according to 2-dimensional Gaussian mixtures. Since the optimisation problem to find the discounting factor * is not easy to solve, we have adopted the following strategy in our first experiments: for each test data, we start with a low = 0.001 and increment it gradually and linearly by steps of 0.05 (note that we are certain to reach a feasible solution).

Precise case In the precise case, the classifiers used to perform the experiment were obtained by logistic regression [START_REF] Hastie | The elements of statistical learning: data mining, inference, and prediction[END_REF]. Logistic regression being a linear classifier, it is well adapted to the combination of binary classifiers (it is easy to train but can only provide simple decision bounds).

For the Synthetic data set, Figures and respectively pictures the discounting level and the number of optimal decisions on the 2 dimensional input space. Roughly speaking, the behaviour of the combination methods corresponds to what can be expected: discounting (or, equivalently, conflict) increase on regions where multiple classes significantly overlap, and the number of optimal decisions increases along the decision boundaries of the different binary classifiers.

Table 2 summarises the results obtained by our method for the precise classifier. Among the results, we can distinguish two kinds of data sets: those for which interval dominance often gives precise results (waveform, pageblocks, synth), and those for which interval dominance often gives imprecise results. In the former sets, results are relatively stable in terms of all accuracy, meaning that binary classifiers gives relatively consistent results most of the time. In the latter sets, imprecision can be important, and s is the difference between d-acc and s-acc. In such data sets, conflict among classifiers is likely to be important, and instances difficult to classify. In most of them, imprecision brings robustness (low s -acc), but at the price of important imprecision (high mean number of optimal classes). In all problems, imprecise classifications seem evenly distributed among well and wrongly classified items. That is not so surprising, since difficult to classify items will sometimes be well, sometimes be wrongly classified by a precise classifier.

It should also be noted that interval dominance is one of the most "cautious" imprecise probabilistic decision rule, in the sense that it results in the largest possible sets of optimal classes. Other more precise, i.e. resulting in narrower sets, decision rules could have been used. Devising a method to pick the "best" decision rule is the matter of future work. Imprecise case In the imprecise case, we used the evidential k-nn algorithm [START_REF] Denoeux | A k-nearest neighbor classification rule based on dempstershafer theory[END_REF] as a binary classifier. A first remark is that results are quite different from the ones obtained for the precise model. In particular, imprecision resulting from the use of interval dominance is here quite limited, as the mean value of optimal classes is always below two (for well and wrongly classed items). This means that in many cases, results are both precise and fairly consistent. We see two main reasons for this: k-nn classification method has more complex and non-linear decision boundaries than logistic regression, and return imprecise probabilistic estimations that are usually not as close as 1 or 0 than the precise estimations returned by logistic regression models. We can therefore expect less conflict in the final assessment, whence more precise decisions. These results clearly show that the choice of the algorithm (and of its parameters) is important, and that this matter should be treated in further works.

Finally, Table compares the accuracy obtained with the multi-class equivalent of the binary classifiers with the accuracy obtained with our binary approach. For the logistic approach, results are either comparable or significantly better for the binary case (this is especially true for the segment data sets). For the knn approach, results are roughly comparable. In summary, the proposed binary decomposition either give better or comparable results. It is also worthwhile to note that, in the case of the k-nn approach, allowing imprecision systematically gives a better accuracy (in terms of s-acc) while not giving too imprecise results (mean number of optimal classes below 2). In this paper, we have introduced a method to combine binary classifiers based on an imprecise probabilistic approach. It handles classifiers with both precise and imprecise probabilistic outputs (including possibilistic, evidential [START_REF] Denoeux | A k-nearest neighbor classification rule based on dempstershafer theory[END_REF] and credal classifiers [START_REF] Zaffalon | The naive credal classifier[END_REF]). We have also proposed a method that allows to always reach a solution, possibly leading to non-informative predictive model if classifiers outputs are too conflicting. We also use imprecise decision rule, so that conflicting classifiers output points out to sets of possible optimal classes, and no longer to single classes, therefore producing more robust and trustable results.

First results on precise classifier (i.e. logistic regression) look very promising, while conclusions on the imprecise classifier are more mitigated, as they give good results but make poor use of imprecision. However, we think that this may be due both to the choice of the classification algorithm (as there are better choice for binary decomposition) and to the chosen parameters.

Future works therefore include the design of optimisation methods fitted to the imprecise framework, the use of the method on other well-known imprecise classification algorithms (such as credal networks or classification trees), and the design of optimisation mehods for the discounting value

Fig. 1 .

 1 Fig. 1. Discounting levels for Synth test data set

Table 1 .

 1 UCI data sets used in experiments

	Data set	#classes	#input	#samples
	name	M	features	training set	test set
	glass	6	9	139	75
	pageblocks	5	10	3284	2189
	satimage	6	36	2921	2573
	segment	7	19	1400	910
	Synth	4	2	2250	750
	vowel	11	10	528	462
	waveform	3	8	1491	3509
	yeast	10	8	890	594

Table 2 .

 2 Results of binary combination with logistic regression

	data	acc	d -acc	s -acc		mean # optimal classes
	set				all data	well classed	wrongly classed
	Synth	4.80	4.98	4.00	1.04	1.04	1.00
	glass	41.3	44.69	28.00	2.16	2.50	3.05
	pageblocks	3.79	5.80	2.10	1.23	1.21	1.20
	satimage	14.54	24.66	8.05	2.05	2.12	2.08
	segment	4.18	20.12	2.53	2.57	2.59	1.00
	vowel	50.43	61.24	7.14	8.47	8.33	6.91
	waveform	13.85	12.26	9.09	1.11	1.11	1.12
	yeast	41.98	47.40	9.60	4.08	4.18	4.89

Fig. 2. Number of optimal classes for Synth test data set

Table 3 .

 3 Results of binary combination with evidential k-nn

	data	acc	d -acc	s -acc			mean # optimal classes
	set				all data	well classed	wrongly classed
	Synth	4.80	4.76	4.67	1.00			1.00	1.00
	glass	44.0	45.42	42.67	1.19			1.07	1.06
	pageblocks	5.39	9.87	4.75	1.36			1.38	1.31
	satimage	10.57	10.20	9.72	1.02			1.02	1.00
	segment	9.12	14.96	8.24	1.55			1.59	1.03
	vowel	39.18	36.74	33.77	1.14			1.15	1.06
	waveform	16.47	18.85	8.44	1.36			1.38	1.49
	yeast	37.88	38.30	35.52	1.23			1.23	1.38
		Data set	#multiclass		#binary (acc)
			name	logistic	k-nn	logistic	k-nn
			Synth	4.80	4.67		4.80	4.80
			glass	44.0	48.0		41.30	44.0
		pageblocks	4.02	5.16		3.79	5.39
		satimage	14.26	10.53		14.54	10.57
		segment	18.02	8.57		4.18	9.12
			vowel	51.30	39.39		50.43	39.18
		waveform	13.94	16.44		13.85	16.47
			yeast	46.30	37.37		41.98	37.88

Table 4 .

 4 Accuracy comparison of multiclass and binary methods

From now on, we will drop the y in the conditional statements, as the combination always concern a unique instance whose input features remain the same.

We assume here that p({x}) is strictly positive for any x ∈ X . In a practical setting, this does not appear as a restrictive assumption, as p({x}) can be as small as possible.