Valentina Beretta
email: valentina.beretta@mines-ales.fr

S Ébastien Harispe

Sylvie Ranwez
email: sylvie.ranwez@mines-ales.fr

Isabelle Mougenot
email: isabelle.mougenot@umontpellier.fr

Sébastien Harispe
email: sebastien.harispe@mines-ales.fr

Truth Selection for Truth Discovery Models Exploiting Ordering Relationship Among Values

Keywords: Truth Identification, Truth Discovery, Conflicting values, Value Relationships, Ontology

Truth selection for truth discovery models exploiting ordering relationship among values

A C C E P T E D M

A N U S C R I P T

Introduction

Developing systems able to automatically evaluate the veracity of the avalanche of data produced by modern information society is of critical importance. Data veracity can be determined comparing information provided by multiple sources on the same subject [START_REF] Bleiholder | Data fusion[END_REF][START_REF] Li | Noise filtering to improve data and model quality for crowdsourcing[END_REF][START_REF] Li | A survey on truth discovery[END_REF]. Numerous scientific communities contribute to studying this complex issue, most notably with respect to (w.r.t.) data integration in information systems and databases.Among the several difficult tasks that data integration addresses and the different approaches that can be used to solve them [START_REF] Knap | Linked open data aggregation: Conflict resolution and aggregate quality[END_REF][START_REF] Guzman-Arenas | The centroid or consensus of a set of objects with qualitative attributes[END_REF][START_REF] Berti-Equille | Veracity of data: From truth discovery computation algorithms to models of misinformation dynamics[END_REF][START_REF] Wang | Social sensing: building reliable systems on unreliable data[END_REF], this paper focuses on automatic truth discovery for solving situations in which different sources provide potentially conflicting data about a specific property of an entity of interest, e.g. on the place of birth of a person. Truth Discovery (TD) consider the accuracy associated with the data sources as an important factor to discriminate data veracity [START_REF] Berti-Equille | Veracity of data: From truth discovery computation algorithms to models of misinformation dynamics[END_REF][START_REF] Wang | Social sensing: building reliable systems on unreliable data[END_REF]. The main aim of the TD models is to identify true information. They intend to automatically solve, in an unsupervised manner, conflicts that may occur among claims. They leverage both the redundancy of the data and the information that is possible to derive from sources (particularly their reliability). More precisely, the backbone of TD is based on the postulate that reliable sources provide true information and that, conversely, true information is given by reliable sources [START_REF] Li | A survey on truth discovery[END_REF]. To identify reliable sources and true information, TD approaches estimate both source trustworthiness and value confidence; the true value is then considered to be the one with the highest confidence. Note that approaches that leverage information about data sources to check data veracity are currently the focus of a lot of attention in several domains such as social sensing [START_REF] Wang | Social sensing: building reliable systems on unreliable data[END_REF] and question-answering [START_REF] Zhou | An empirical study of topicsensitive probabilistic model for expert finding in question answer communities[END_REF].

Here we address the problem of selecting the truth for functional predicates when a priori knowledge in the form of a partial order of values (e.g. subsumption relationship in an ontology) is considered to improve value confidence and source trustworthiness estimations. A partial order highlights when different values are not conflicting, but they represent the same concepts with different levels of granularity. Indeed, conflict and granularity are two different aspects to consider when identifying the most reliable information. While conflict values produce inconsistency, different granularities only indicate imperfection in data [START_REF] Khaleghi | Multisensor data fusion: A review of the state-of-the-art[END_REF]. In formal logic, a predicate p is consid-

A C C E P T E D M

A N U S C R I P T ered functional if for any subject there is a unique value v ∈ V for which p(subject, v) is true1 -birthplace is an example of a functional predicate. Note that this definition does not take subsumption relationships among values into account. This is in accordance to the fact that, for instance, everyone was born in a specific location, but it does not consider that this place can be described using different levels of precision, e.g. district or region. In this case, multiple values can be true given the same subject. Thus, considering partial order of values and closed world assumption (our knowledge of the world is complete), a predicate is functional if for any subject there is a unique value v ∈ V , for which p(subject, v) is true, such that there is not another value v ∈ V subsumed by v for which p(subject, v ) is true. As far as we know, we are the first to propose to take ontologies (as a priori knowledge) into account [START_REF] Beretta | How can ontologies give you clue for truth-discovery? an exploratory study[END_REF]. In this situation, the traditional final value selection step in the majority of TD approaches cannot be applied. Indeed, in this case, since more abstract values will de facto be associated with a higher confidence value in accordance with the partial ordering of values modeling implications among them, the true value cannot be defined as that with the highest confidence. This is due to the hypotheses used by approaches that leverage information related to the structure that may exist among values. Briefly, sources that explicitly claim a value implicitly support all of its generalizations. Therefore, if a source claims that "Pablo Picasso was born in Malaga", it also implicitly supports the assertion that he was born in Spain, Europe, etc (considering that it is in agreement with the ontology). Thus the most general value is implicitly supported by all the others. Hence, its confidence will always be the highest. However, considering the most general value to be the only truth is not trustworthy (since it is a tautology), e.g. stating that Pablo Picasso was born in a Location is not meaningful. This paper proposes to overcome this problem by studying a solution able to identify more specific true answers (than the most general one) that may exist. Our contribution consists of:

• proposing a post-processing approach able to identify the truth given the confidence estimations returned by any TD model that considers structured values;

A C C E P T E D M A N U S C R I P T

• performing empirical experiments on synthetic datasets -this evaluation uses estimations returned by an adaptation of Sums able to take prior knowledge in the form of a partial order among values into account [START_REF] Beretta | How can ontologies give you clue for truth-discovery? an exploratory study[END_REF] -and comparing the proposed approach with existing ones evaluating identified true values.

The rest of the paper is structured as follows. Section 2 presents an overview of TD approaches taking advantage of potential relationships among sources or claims. This section ends with a discussion about the consequences of using a partial order among values as relationship information. In Section 3, notations are introduced and the problem is formalized. The solution strategy we propose is detailed in Section 4. The model is assessed via several experiments reported in Section 5 and discussed in Section 6. Section 7 summarizes the main findings of the study and the results that have been obtained; while the perspectives opened by our contribution are finally discussed.

Related work

Truth discovery aims to solve conflicts among data provided by several sources. The data treated in this domain consists of claims specifying the values that sources associate with certain data items (i.e. a data item represents a particular aspect of a real-world entity). Values can be numerical or categorical/strings. The main assumption of TD is that true information is provided by reliable sources and reliable sources provide true information ( [START_REF] Li | A survey on truth discovery[END_REF][START_REF] Yin | Truth discovery with multiple conflicting information providers on the web[END_REF]). This rationale can be modeled by defining the value confidence and source trustworthiness. Many studies have been proposed in this field [START_REF] Li | A survey on truth discovery[END_REF]. The baseline model consists of a voting strategy. For each data item it regards the value which is the most frequently claimed as truth. All sources are therefore implicitly considered similarly in this model. Otherwise TD estimates for each source a different trustworthiness level based on the claims it provides. Some models deal with numerical values [START_REF] Ouyang | Aggregating crowdsourced quantitative claims: Additive and multiplicative models[END_REF], others with categorical claims [START_REF] Wang | Social sensing: building reliable systems on unreliable data[END_REF][START_REF] Ouyang | Truth discovery in crowdsourced detection of spatial events[END_REF][START_REF] Pasternack | Latent credibility analysis[END_REF][START_REF] Zhao | A bayesian approach to discovering truth from conflicting sources for data integration[END_REF] and others with both [START_REF] Yin | Truth discovery with multiple conflicting information providers on the web[END_REF][START_REF] Yin | Semi-supervised truth discovery[END_REF][START_REF] Pochampally | Fusing data with correlations[END_REF]. While basic TD models limit their complexity to correctly estimate confidence and trustworthiness with different formulas, other approaches incorporate additional information to improve the overall performances. The latter group of approaches is the most relevant for our study and is detailed hereafter.

A C C E P T E D M

A N U S C R I P T Among all of these methods, we focus our attention on those that use, as additional knowledge, correlations2 that may exist among sources ( [START_REF] Pochampally | Fusing data with correlations[END_REF][START_REF] Qi | Mining collective intelligence in diverse groups[END_REF][START_REF] Wang | An integrated bayesian approach for effective multi-truth discovery[END_REF]), data items ( [START_REF] Wang | Social sensing: building reliable systems on unreliable data[END_REF][START_REF] Meng | Truth discovery on crowd sensing of correlated entities[END_REF][START_REF] Wang | Scalable social sensing of interdependent phenomena[END_REF]) or values ( [START_REF] Yin | Truth discovery with multiple conflicting information providers on the web[END_REF][START_REF] Dong | Integrating conflicting data: the role of source dependence[END_REF]). The first class is related to source interdependences. These models consider source relationships mainly by analyzing the pattern of similar claims with correlated accuracy estimations. They also usually assume that sources sharing common false values are more likely to be dependent than sources sharing common true values. Indeed, it is difficult to identify dependencies between sources stating different false values [START_REF] Berti-Equille | Sailing the Information Ocean with Awareness of Currents: Discovery and Application of Source Dependence[END_REF]. Most of these studies only analyze static correlations. To the best of our knowledge, time-course dependency relationship patterns has been only considered in [START_REF] Dong | Truth Discovery and Copying Detection in a Dynamic World[END_REF]. In this case, dependency among sources is captured by studying the similarity between patterns of updates associated with sources [START_REF] Berti-Equille | Sailing the Information Ocean with Awareness of Currents: Discovery and Application of Source Dependence[END_REF]. Several methods take advantage of dependency in terms of the copying relationship [START_REF] Pochampally | Fusing data with correlations[END_REF][START_REF] Qi | Mining collective intelligence in diverse groups[END_REF][START_REF] Wang | An integrated bayesian approach for effective multi-truth discovery[END_REF][START_REF] Dong | Integrating conflicting data: the role of source dependence[END_REF]. Other correlations among sources may also occur, such as the common errors made by different extractors that use the same extraction rules or the common values identified by the extractor that use different rules, and so on [START_REF] Pochampally | Fusing data with correlations[END_REF]. Moreover, the dependence relationship is often considered between source pairs, but dependencies may also occur at the group level [START_REF] Qi | Mining collective intelligence in diverse groups[END_REF]. The second correlation class is related to data items. The first body of works in this context proposed to deal with the social sensing problem. In crowd sensing, humans coupled with their smartphones become sensors that explicitly or implicitly provide observations about their physical environment. Then it becomes necessary to understand the validity of data sent by sensors. TD models applied to this domain take advantage of both physical [START_REF] Wang | Exploitation of physical constraints for reliable social sensing[END_REF] and temporal [START_REF] Wang | Towards cyberphysical systems in social spaces: The data reliability challenge[END_REF] correlations as well as causal relationships [START_REF] Wang | Scalable social sensing of interdependent phenomena[END_REF]. For physical correlations, they assume that co-located data items should have similar values. For instance, gas stations located in the same area should have similar gas prices. For temporal correlations, the assumption is that two temporally close observations cannot have very different values. This kind of correlation is especially useful when analyzed data has a long-tail characteristic, i.e. many data items observed by few sources and few data items observed by many sources. Indeed, in this case the estimations can easily deteriorate if the few sources that provide claims for a data item are also unreliable. Using

A C C E P T E D M

A N U S C R I P T correlations, information associated with data items having a high number of observations provided by reliable sources can be propagated to data items having only a few claims associated with them. The findings of the two studies [START_REF] Wang | Exploitation of physical constraints for reliable social sensing[END_REF] and [START_REF] Wang | Towards cyberphysical systems in social spaces: The data reliability challenge[END_REF] permit to partition data items into small groups without considering any dependency among groups, but the complexity of their solutions is exponential w.r.t. the maximum group size. Alternative models have been proposed to overcome this limitation to be able to deal with a large number of dependencies, e.g. [START_REF] Meng | Truth discovery on crowd sensing of correlated entities[END_REF] [START_REF] Wang | Scalable social sensing of interdependent phenomena[END_REF]. The former classifies the problem as an optimization problem, and the latter, modelling the problem as a Bayesian network, leverages potential conditional independences among data items. Moreover, in this study they also take into account a second kind of correlation related to the data items: i.e. the category. In this case, a trustworthiness level may be attributed to each source w.r.t. the category a data item belongs to. The main limitation of this approach is that the Bayesian network has to be known or empirically learned from historical data by specific algorithms. The third type of correlation regards the values. The basic idea is that two correlated values support each other. If one of them is considered true, then the other has a high probability to be true. In order to evaluate value correlations, previous studies such as [START_REF] Yin | Truth discovery with multiple conflicting information providers on the web[END_REF], [START_REF] Dong | Integrating conflicting data: the role of source dependence[END_REF], and [START_REF] Yin | Semi-supervised truth discovery[END_REF] use value similarity. For instance, they compute the edit distance of strings, similarity among sets, and difference among numerical values. Otherwise, in our previous study we took advantage of value correlations in the form of partial ordering that may exist among the provided values [START_REF] Beretta | How can ontologies give you clue for truth-discovery? an exploratory study[END_REF]. An example of partial order is shown in Fig. 1. Given this partial order, we adapted the Sums approach to incorporate this new information. The rationale is that if a source associates the value Spain to an aspect of a real-world entity, then it also implicitly supports all more general values, e.g. Europe. Thus we modified the formula to estimate the confidence of a value changing the set of sources used for the calculus. In Sums, confidence is computed by considering all sources that provide an analyzed value, while in the adapted model (AdaptedSums) sources that explicitly claim a more specific value than the one being analyzed are also taken into account as well. Indeed, these sources implicitly support all more general values than the one they provide. Using the adapted approach, at the end of the iterative procedure, the value confidence estimations monotonically decrease w.r.t. the partial order among values. In other words, for each value more specific than another, the confidence of the former is lower than or equal to the confidence of the latter. As a result, when considering the partial order of values, the highest confidence score will be always assigned to the most general value. In this context, using the usual strategy adopted by the existing models is not worthy. Indeed, selecting as truth the value having the highest confidence, they will always return as true value the most general one. In the rest of the paper, we describe a refined postprocessing strategy able to select the true value leveraging these monotonic estimations.

A C C E P T E D M A N U S C R I P T

Problem Formulation

Let's consider a set of data items D such that each d ∈ D is composed of a pair (subject, predicate) where the subject represents a real-world entity and the predicate represents its aspect of interest, e.g. (picasso, bornIn). S denotes the set of sources, V the set of values, V s ⊆ V the set of values provided by s ∈ S (for each data item for which s provided values), and V d ⊆ V the set of values associated with data item d ∈ D. Formally, TD models first aim to identify the set of true values V * d ⊆ V for each data item d ∈ D. In the case of a data item d characterized by a functional predicate, we have

|V * d | = 1 if elements from V are disjoint, i.e. ∀(v, v ) ∈ V 2 , ¬(v =⇒ v ) ∧ ¬(v =⇒ v). Note that a value v implies A C C E P T E D M A N U S C R I P T
( =⇒ ) a value v when v is subsumed by v . To ease the formal introduction, and in accordance with the literature, we will as often as possible consider the special case of data items associated with the functional predicate. Dealing with data items composed of functional predicates TD identifies the true values v * d ∈ V for each data item d estimating value confidences c : V → [0, 1] -how an information is likely to be true -and source trustworthiness t : S → [0, 1] -how reliable is a source. This is done through an iterative procedure that alternatively estimates them. The execution of the model finishes when the stopping criteria is verified, e.g. convergence of estimations, maximum number of iterations, and so on. Hence, each value v d ∈ V (w.r.t. a data item) is associated with a confidence level c(v d ) and each source s ∈ S with a trustworthiness level t(s). Existing approaches usually assume that for a specific data item d, elements of V d are disjoint/independent and they therefore recognize the true value of d is that with the highest confidence score. This straightforward procedure cannot be applied using adapted models that consider ordering among values. Incorporating this information into the model, each value more general than a true value can only be considered as true as well 3 . Therefore, considering all values associated with a data item, the estimated confidence scores monotonically increase w.r.t. the partial ordering of values, i.e. ∀v, v ∈ V : if (v =⇒ v ), then c(v) ≤ c(v ). Consequently, the highest confidence score is always assigned to the most general value (that is implicitly supported by all provided claims). To solve this problem, we propose a post-processing procedure able to select the true value for each data item given the estimated confidence scores and the relationships that may exist among values. We assume that the value dependencies are known a priori in the form of a partial order modelled by an ontology O = ( , V ). Note that even if the domain knowledge is not available, partial order can be automatically constructed [START_REF] Bronselaer | Dynamical order construction in data fusion[END_REF]. The partial order can be represented by a Directed Acyclic Graph (DAG),

G O = (V, E), where V = {v 0 , v 1 , • • • , v m }
is the set of values representing our vocabulary according to our knowledge of the world (all possible values that can be claimed by sources), and E = {(x, y) ∈ V ×V |x y} is the set of edges specifying the partial ordering that exists between values. Specifically x y when there is a directed path from x to y in the DAG; i.e. when y is reachable from x [START_REF] Kozen | The Design and Analysis of Algorithms[END_REF]. Note that a path from x to y is defined

A C C E P T E D M A N U S C R I P T as a non-empty sequence of n different nodes v 0 , v 1 , • • • , v n-1 with x = v 0 , y = v n-1 and for which ∀i ∈ [0, n -2] (v i , v i+1 ) ∈ E. An important charac- teristic of the graph G O is
that it has to be transitively reduced. This is not a problem because by considering any DAG its transitive reduction can be obtained [START_REF] Aho | The transitive reduction of a directed graph[END_REF].

Here we introduce several functions that will be useful for manipulating the graphs (with G a set of graphs):

• ancestors: G × V → P(V ) such that ancestors(G O , x) = {y|x y}. • children : G ×V → P(V ) designed as children(G O , x) = {z|(z, x) ∈ E} • root : G → V such that as root(G O ) = {x|∀y ∈ V, y x}
These properties enable us to easily explain our procedure to traverse the partial value ordering graph in the next section. Further important information that can be derived from any ontology is the Information Contents (IC) of its concepts (e.g. [START_REF] Seco | An intrinsic information content metric for semantic similarity in wordnet[END_REF]). This quantity, related to the concept specificity (see Section 3.3 in [START_REF] Harispe | Semantic similarity from natural language and ontology analysis[END_REF]) represents the degree of abstraction/concreteness of a concept w.r.t an ontology. One of main IC property is that the IC score monotonically decreases from the root to the leaves, i.e. if x y, then IC(x) ≥ IC(y) (IC(root) = 0). This score will help us to discriminate between different values w.r.t. their granularity. All of the elements presented in this section will help define the approach used to select the true values that is described in Section 4.

Proposed Approach

The entire truth-discovery procedure, from the input consisting of a set of claims to the output consisting of the true values and the degree of reliability associated with each source, is presented in Fig. 2. In this section, we propose a post-processing procedure that selects the true values given the estimations obtained by TD models that relax the assumption related to the disjointness of values. It involves three steps: (i) selection of the best true value candidates; (ii) ranking of selected values; and (iii) filtering of ranked values w.r.t. defined desirable properties. For instance it may be useful to return a set of solutions that share an ordering relationship or, on the contrary, to return a value set composed only of "alternatives" that are not ordered. The choice related to

A C C E P T E D M A N U S C R I P T

the appropriate features of the solution set depends mainly on the application scenario. The first step of the process: (i) permits to retrieve the most specific possible true value(s) and all of its ancestors using available information, such as confidence scores and partial ordering of values. The second step: (ii) orders the selected values based on predefined criteria. The third step: (iii) is required to filter the top k results. For TD, the final aim k should be equal to 1, but in cases where there is uncertainty it may be useful to return a set of values, even if the predicate is functional. Moreover, answers that do not have defined desirable properties (see Section 4.3 for further details) are removed from the result list. Those three steps are detailed hereafter.

True value selection

The first part of the post-processing procedure concerns the selection of the promising candidate(s) as the most expected value(s) for each data item. We have defined a selection strategy that takes advantage of the partial order of values and step by step refines the granularity of the correct value associated with each data item. Now we will give an overview of the approach followed by Algorithm 1.

A C C E P T E D M A N U S C R I P T

Starting from the most general value (implicitly supported by all provided values and surely true), the process aims to detect the most specific expected value(s). A traversing procedure was thus applied on the graph that represents the partial order of values. It starts from the root, it selects the best alternatives among the children of the considered node and moves forward through the selected values. Our assumption is that values with the highest confidence locally should be the most likely to be true. Therefore the choice of the best alternative(s) is done by comparing the confidence scores associated with the children of the previously selected node.

In the case of functional predicate, the values can be partially ordered by their granularity, see Fig. 1. Therefore the selection procedure refines, at each step, the level of precision used to describe the single true value associated with a data item. The semantics of each selected node expresses the fact that the node subsumes the correct solution (i.e. the expected true value). The last selected nodes should correspond to the most specific answers that can be identified through the selection process. The selection process has to handle two main undesirable situations that may occur: (1) selection of values with a confidence score too low to be considered as true, and (2) difficulty in discriminating the best alternative(s) among the children of a node since their confidence scores are not significantly different. As a solution, two thresholds have been defined: θ and δ. The threshold θ ∈ (0, 1] enables us to specify the confidence lower bound required for a value to be part of the set of true values. Note that the value 0 is not included in the θ interval. Indeed, considering claims with confidence scores equal to 0 makes no sense because it would mean considering, as truth, values provided by totally unreliable sources (all with trustworthiness equal to 0). The confidence score that is compared to θ has to be previously normalized w.r.t. each data item, i.e. the confidence score associated with the most general value of each data item always has to be equal to 1. This normalization step is required to avoid the definition of an inconsistent threshold w.r.t. the different data items. The threshold δ ∈ [0, 1] represents the minimum difference that has to exist among values with the highest confidence and all the others so that one prevails over the others. In particular, if the difference between the confidences of two values is less than or equal to δ, then it is hard to make a choice among them. This comparison is done among values that are children of the same father to select the best alternatives. The definition of different parameter settings produces different behaviours Config θ δ Selection procedure behaviour 1 α 0 Naive greedy procedure that maximizes the confidence score at each step. 2 α 1 Greedy procedure that selects all values greater than α.

A C C E P T E D M A N U S C R I P T
Since δ is equal to 1, all values with confidence higher than α are selected. 3 α β At each iteration a value is collected only if the difference of its confidence and the highest confidence at the current step is lower or equal to β. All values in the returned set have confidence that is greater than α.

of the selection phase ending in the possibility of obtaining different kinds of solution sets. The main parameter settings are summarized in Table 1. Configuration 1 (θ = α, δ = 0) reproduces a naive greedy algorithm that, at each step, selects values with the highest confidence greater than α without performing any other control. Configuration 2 (θ = α, δ = 1) is able to return all claimed values with confidence higher than α. It may seem useless, but it is a selection configuration necessary to obtain a particular set of values at the end of the post-processing procedure. A set composed of "promising" alternatives that allow to report values that are, as much as possible, fine-grained and semantically different.

In this way, we increase the probability of finding the correct value since we increase the number of different concepts that are considered. Therefore this strategy is useful to deal with cases in which there is a lot of uncertainty. The idea is to return all claimed values and their ancestors and then, using the ranking phase to position in the first places, the most promising alternatives with the properties we have just explained. Configuration 3 (θ = α, δ = β) is a generalization of the two previous configurations. It selects the set of values that are greater than a threshold θ and they differ, at each step, more than δ from the confidence of the other alternatives. Algorithm 1 reports the pseudo-code of the selection procedure. The algorithm starts performing a transitive reduction of the graph representation of the partial ordering (line 2). We thus ensure that the choice of the best alternative is done among a set of children that do not share ordered relations. Moreover, this avoids useless comparison of a large number of confidence G ← transitive reduction(G O )

3:

V * visited ← { } 4:
queue ← list(root(G))

5:

while !(queue.isEmpty()) do 6:

v ← queue.pop()

7: V * visited ← V * visited ∪ {v} 8: V ch ← children(G, v) 9: conf max ← max child∈V ch (c(child))
10:

V ch * = {v ∈ V ch : c(v ) ≥ θ ∧ (conf max -c(v )) ≤ δ} 11: queue.addAll(V ch * \ V * visited ) 12: return v∈V * visited ancestors(G, v)
scores. Then, at each iteration, the algorithm applies a greedy search by maximizing the confidence of the values (lines 5 -9). It selects all values having confidence higher than or equal to θ whose scores are not significantly different from the highest confidence (line 10). Then, it adds them to the queue (line 11). Note that the the confidence scores were computed applying AdaptedSums. This model computes the value confidences summing up all trustworthiness of those sources providing the considered value or one of its possible specializations. The procedure stops when the last selected value has no more specific values to be visited. In order to be in accordance with our assumption and problem settings, all values that are more general than that selected will compose the set of true values -due to multiple inheritances some of those values may not have been visited by the greedy procedure (line 12). The fact that confidence score monotonically increases w.r.t. the partial order ensures that the scores related to ancestors of the visited values are higher than or equal to θ. The termination of Algorithm 1 is ensured by line 6 and line 11. The complexity of the selection of the true value algorithm is related to the number of comparisons required to find the maximum value confidence traversing graph G O . Therefore, the complexity of the algorithm is O(E) which in turn

A C C E P T E D M A N U S C R I P T is O(V 2
). At each step, a number of comparisons equal to the number of node children is required. The worst case scenario is verified when the following conditions holds at the same time: (i) graph G O has depth 2, (ii) its nodes are uniformly distributed between level 2 and 3, (iii) nodes at the same level have the same fathers and the same children and, moreover, (iv) they have equal or not significantly different confidence scores. The conditions related to the morphology of the DAG ensure that the number of comparisons is maximum, and the condition on the confidence score guarantees that the procedure traverses all nodes.

All of the configurations of the algorithm input parameters enable us to select a set of possible true values. Since the aim of TD is to find the most expected solution, a method able to choose it is required. The ranking phase described in the next section is devoted to this.

True value ranking

Given the true value set selected in the previous step, we have to define a ranking method in order to select the k ∈ N + most expected values where k is a fixed number. In our investigations, k is experimentally set, at the most, at 5. The solution set of most expected true values is indicated as V * ⊆ P(V * candidates ), where V * candidates is the value set returned by the selection phase. Now we propose to rank the values based on rather:

• their IC. This method is useful for situations in which specific answers are expected and when there is not much uncertainty on the data item under consideration. Note that in the following experiments IC is a measure computed according to the definition provided by Seco based on the analysis of the partial ordering topology [START_REF] Seco | An intrinsic information content metric for semantic similarity in wordnet[END_REF]. In particular, it takes advantage of the number of descendants of a value:

IC Seco (v) = 1 - log(|descendants(v)| + 1) log(|V |) (1)
where |V | is a non-empty set since an ontology is considered to have at least one concept, i.e. the root value. IC has been proposed because the user generally expects very precise answers. Often general true values for a data item are well known a priori, i.e. it is well known that a person is born in a place. If two or more true values have the same IC, then random selection can be

A C C E P T E D M A N U S C R I P T
done or, alternatively, another criterion can be used to rank this value subset.

• their source average trustworthiness, denoted W A trust (v). The rationale is that if a lot of unreliable sources support a false value A (increasing its confidence score -Sums does not normalize based on the number of sources claiming a value, therefore its confidence estimation is biased), and there are only a few reliable sources that support a true value B, then sources providing B should have higher average trustworthiness scores. This measure is obtained by computing the average trustworthinesses associated with sources that explicitly or implicitly claim to have a particular value v and by weighting it by a normalization factor:

W A trust (v) = (1 - 1 η + |S v + | ) * avg trust (v) (2)
where the average of source trustworthiness is represented by avg trust (v), S v d + is the set of sources that implicitly or explicitly provide the value v d and η is a small number used to avoid that W A trust (v) = 0 when v is provided by only one source. The first factor, i.e. normalization, was introduced in order to tune the average w.r.t. the number of sources providing the value. Indeed, inspired by the study presented in [START_REF] Jean | Uncertainty detection in natural language: a probabilistic model[END_REF], the higher the number of sources providing a value, the higher our confidence in the computed average should be. Moreover in this case, if two values have the same W A trust , then another criterion can be used to rank them.

Once the values are ranked, the next and final step of the post-processing procedure can be performed.

Filtering of top-k true values

The filtering phase collects the top k values in the rank and returns them to end-users. Before performing selection of the top k values, all the ranked ones have to be controlled. This is necessary because truth discovery models can be applied to different scenarios: high or low uncertainty situations, high or low risky cases in which making an error is, respectively, very dangerous or not. For instance, if truth discovery models are used to populate a medical knowledge base containing, for each symptom, all possible correlated diseases,

A C C E P T E D M A N U S C R I P T

then the end-users want to be really careful in accepting a value as true. Therefore, based on the possible application contexts, different properties that the solution set V * has to respect can be defined. In this way various true value sets with different characteristics can be identified:

• the solution set V * ord contains only values sharing partial ordering relationships; formally ∀(x, y) ∈ V * ord × V * ord , x y ∨ y x. The procedure to create a set containing values that respect this property is as follows: it iteratively selects and removes the first element in the ranked list. Then it adds this value to the solution set only if it is an ancestor or descendant of all elements that are already present in it.

• the solution set V * disj is composed of values that do not share any partial ordering relationships; formally ∀(x, y) ∈ V * disj ×V * disj , ¬(x y)∧¬(y x) ∧ w, z ∈ V * candidates w x ∨ z y. This means that all values in the solution set are the most specific among those returned by the selection phase. Indeed, only values that do not have descendants in the returned true value set belong to the solution. The procedure used returns a set of alternatives that are as much as possible very specific and different. In other words, this set of values consists of elements that do not have any of their exclusive descendants in the sorted list. For example, if the values returned by the previous step are Europe, Continent, Country, City, Location, then, in accordance with the partial order in Fig. 1, the V * disj is composed only of Europe, Country and City. The first kind of solution can be desirable when there is not much uncertainty (end-users expect to easily find the true answers) or the end-users do not want to deal with potentially different values in a domain where they are not experts. The second property can be adopted when there is a lot of uncertainty and especially when the application context could result in making errors without dangerous consequences. Indeed, when there is uncertainty, to postpone the selection of true values to the end-users, avoiding to automatically select only a specific value and its ancestor, may be useful. In order to support the end-users final choice, returning a set of values composed of the most promising alternatives is important. Obtaining V * ord is suitable when δ = 0. Indeed, taking the value with the highest confidence at each step, the process ends with the selection of only one specific true value (and its ancestors). Considering this set of returned values, the first property is often verified without filtering any value out. In

A C C E P T E D M A N U S C R I P T

any case, very general values often are not returned since only the top-k values are selected after the verification of the property. Otherwise, the second property, i.e. V * disj , is not useful considering δ = 0. Only the single most specific value contained in the set of returned values is selected when this property must hold. Indeed, all of the others share partial ordering relationships. This corresponds to consider that δ = 0, k = 1 and a solution set V * ord . Obtaining V * disj is preferable when δ = 1. Indeed, in those cases all values having confidence higher than θ are returned by the selection phase, but for the final aim of truth discovery (finding the truth) it is suitable to only keep the set of "promising" alternatives that correspond to a set of values that are different and specific as much as possible.

Experiments

In this section we describe all experiments performed on synthetic datasets to confirm the validity of our approach. First, we focus on the synthetic datasets: how we generated them and what are the parameter settings we tested. Then, we present the evaluation methodology we used to evaluate the approach and to compare it with existing models.

Datasets

In order to assess the behaviour of our approach w.r.t. the ontology used to derive the relationship among values, we integrate preliminary experiments carried out using the synthetic birthPlace datasets (see [START_REF] Beretta | How can ontologies give you clue for truth-discovery? an exploratory study[END_REF] for further details related to their generation) with additional ones performed using different partial ordering structures. Each synthetic dataset contains a set of claims concerning a specific predicate, a set of sources and the subset of claims provided by each source. We generate 5 different datasets considering the predicates birthPlace and genre from DBpedia [START_REF] Auer | Dbpedia: A nucleus for a web of open data[END_REF], and the predicates Cellular Component(CC ), Molecular Function (MF ) and Biological Process (BP ) from Gene Ontology [START_REF] Ashburner | Gene ontology: tool for the unification of biology[END_REF]. All the datasets are randomly generated based on a ground truth (containing a set of true claims, for each predicate), a partial order among the values contained in the ground truth (an example is shown in Fig. 1) and a set of factitious sources. Note that Table 2 reports the features associated to the different partial ordering structures that we use. Given these elements the generation process can start.

First, a trustworthiness level is associated with each source. We assume that the majority of sources are sufficiently reliable and only a few of them are always or never correct. A Gaussian distribution with an average and standard deviation equal to, respectively, 0.6 and 0.4 was used to model the described behaviour.

Second, we reproduce the long-tail phenomena [START_REF] Li | A confidence-aware approach for truth discovery on long-tail data[END_REF] for which many sources provide values for a few data items and a few sources provide values for many data items. This is modelled using a simple exponential distribution. It associates, with each source, the number of data items on which it has to provide a value. The statistic that confirm that this behaviour is respected by the datasets that were generated are reported in Fig. 3. In Fig. 3a we observe that approximatively 80% of data items are claimed by less than 500 sources. Fig. 3b shows that most of sources have provided at least 1000 data items. Third, each source claims a true or false value for a specific data item w.r.t.

A C C E P T E D M

A N U S C R I P T its trustworthiness. In case of true claims, the value is selected among the inclusive ancestors of the value contained in the data item. In the case of false claims, it is selected from the set of values that are neither inclusive ancestors nor descendants of the true one denoted v * d . In both cases the values are selected w.r.t. a similarity measure between the values and v * d . For the selection of the true values, three different strategies were adopted: EXP, LOW E, UNI (Fig. 4). EXP simulates cases in which sources are quite sure about the true values, so they tend to claim values similar to the expected one (contained in the ground truth) when they have to provide a true value. UNI reproduces a world where there is a lot of uncertainty, then the sources tend to indiscriminately select the value from the entire set of possible true values. LOW E is a trade-off between the previous two types. Sources uniformly select the value from the set of possibilities, but there is a slightly higher probability of choosing values similar to the expected one. For instance, Fig. 4 For each predicate, 20 datasets were produced w.r.t. the different laws that can be used to select the true values provided by sources. Further details on the generation of the ground truth and how the partial order of values has been derived are provided with the datasets at www.github.com/lgi2p/TDSelection.

Experiment settings

In order to provide robust results, considering each predicate, we generated 60 synthetic datasets (20 for each different distribution used to select the true values). Several experiments were conducted on them. Table 3 reports all of the experimental settings in which the datasets were tested. The name associated with each configuration indicates the delta setting. When δ = 0 the approach is called TSbC (Truth Selection of the Best Child). Indeed, the selection algorithm chooses, at each step, the value with the highest confidence. In other words, it selects the best node among the children of the considered one. Otherwise, when δ = 1 the approach is called TSaC (Truth Selection of all Children). Indeed, using this configuration the algorithm selects, at each step, all the children of the considered nodes. Moreover, the subscript specifies the first ranking criteria used, i.e. TSbC IC means that IC is used for the ranking phase as first criteria to order the values. For all the experiments, different threshold θ values were used: 0, 0.1, 0.2, 0.3, 0.4, 0.5. Note that when δ is equal to 0, we test only the property of the solution set indicating that its values share ordering relationships. Indeed, the selection procedure in this case chooses, at each step, only values having the highest confidence and therefore only a single most specific value and its ancestors

A C C E P T E D M

A N U S C R I P T can be returned. No alternatives to the most specific value can be selected. When δ is equal to 1, we test only the property indicating that the values in the solution set do not share a partial order. The procedure may select more than one branch. In this situation, if we force the returned true values to share an ordering relationship, we oblige the algorithm to select only one path. Thus, the main advantage of this configuration, i.e. to propose a set of alternatives, is wasted. For the confidence and trustworthiness estimations, we initialize the confidence value at 0.5 in order to start the iterative procedure, i.e. Adapted-Sums. The stopping criteria used for the iterative procedure is the same as that used in the original paper of Sums [START_REF] Pasternack | Knowing what to believe (when you already know something[END_REF]: the procedure was stopped after 20 iterations. The algorithms were implemented in Python 3.4. The experiments were performed on a PC with an Intel Core 2 Duo processor (2.93GHz×8GB). To give an idea, using the codebase developed for these experiments 4 , memory consumption varies from 1.6 to 4.3 GB depending on the number of values composing the partial order. Using TSbC and TSaC, running times were, respectively, around 0.24 and 1.7 milliseconds per data item. Note that running times may increase significantly when partial orders have specific topological properties. In particular, optimizations have to be studied when dealing with partial orders having values with numerous children (hubs). For instance, the partial order used for the birthPlace predicate contains the value "Settlement" with 160 thousands children; running times using this partial order were 0.02 and 0.8 seconds per data item for TSbC and TSaC respectively. The source code and datasets associated with this study are open-sourced and published on the Web at the following link www.github.com/lgi2p/TDSelection. Note that for Sums and AdaptedSums, we used the code developed by [START_REF] Beretta | How can ontologies give you clue for truth-discovery? an exploratory study[END_REF]. Otherwise, for the experiments related to the other existing models, we used the DAFNA-EA5 implementation [START_REF] Waguih | Truth discovery algorithms: An experimental evaluation[END_REF]. This API provides the source code for the main existing models.

Evaluation

The evaluation of the model we proposed to select the true values was carried out using both traditional and hierarchical performance measures of classification problems.

A C C E P T E D M A N U S C R I P T

Among traditional metrics, precision and recall were mainly used to compare our approach with the existing models that do not consider the partial order. Our positive class consists of all pairs (d ∈ D, v * d ∈ V d ) where v * d is the value contained in the ground truth for the data item d, and the negative class is composed of all pairs

(d ∈ D, v d ∈ V d -v * d ).
Therefore, the precision is the proportion of pairs (d, v * d ) returned by the approach among all the pairs it returns. The recall is the proportion of pairs (d, v * d ) returned by the approach among all pairs contained in the ground truth. The hierarchical evaluation measures (HEM) were used to analyse the behaviour obtained by different parameter settings of our approach. Indeed, hierarchical metrics distinguish the severity of different errors taking the hierarchy of classes into account. Reasonably if Malaga is the true value, then an approach that returns Portugal should be less penalized than another that returns Brazil. Indeed Portugal is in the same continent than Malaga, i.e. Europe, while Brasil is in a different continent, i.e. America. A detailed study related to hierarchical measures was presented in [START_REF] Kosmopoulos | Evaluation measures for hierarchical classification: a unified view and novel approaches[END_REF]. They distinguish the main dimensions that characterize hierarchical classification problems and suggest, for each possible combination, which are the best evaluation metrics to use. They recommend F LCA , P LCA , R LCA and M GIA when dealing with single-label problem and DAG hierarchy. This situation corresponds to our initial problem settings: for each data item there is a single expected true value and our partial order among values is represented using a DAG. F LCA , P LCA and R LCA are set-based measures. They use hierarchical relations to augment the sets of returned and true values and to compute precision and recall. Since adding ancestors over-penalize errors that occur to nodes with many of them, F LCA , P LCA , R LCA use the notion of the Lowest Common Ancestor to limit this undesirable effect. M GIA is a pair-based metric that uses graph distance measures to compare returned and true values. Its limitation is that it does not change with depth. For further details related to the computation of these measure please refer to [START_REF] Kosmopoulos | Evaluation measures for hierarchical classification: a unified view and novel approaches[END_REF]. Now, we briefly describe the main characteristics of these hierarchical measures through an illustrative example. This enable the reader to better understand the result discussion in the next section. Considering the DAG in Fig. 1 and Malaga as the true value, the HEMs related to several returned values are reported in Table 4. As shown, if the returned value is more general than the expected one, then P LCA is not affected, while R LCA decreases when increasing the distance from the expected value. Otherwise, if the returned value is an error (neither the expected value nor more general one),

A C C E P T E D M

A N U S C R I P T

Results

All of the experimental settings presented in Section 5 were tested. Here, the results are presented and discussed. Note that a robust analysis were conducted given the artificial nature of the synthetic datasets. Results show that our approach enables successfully addressing the problem of selecting true values. Recall that our study considers a setting where value confidence estimations w.r.t. the partial order of values monotonically increases. The most effective configuration settings of our selection procedure were TSaC trust and TSbC IC as shown in Fig. 6. These settings coupled with the AdaptedSums model were able to outperform, in terms of recall, existing truth discovery methods on the different datasets and predicates that were used for the experiments, see Fig. 5. Note that in these experiments we compared our post-processing strategies considering k = 1 with the other models. Indeed, the general aim of TD is to return a single answer for each data item. In the rest of this section we detail the comparison of the proposed approach with existing truth discovery models and we study different configuration settings of the post-processing procedure analysing its behaviour considering different k, δ and θ values. Both TSaC trust and TSbC IC obtained good performance, but TSaC trust was the most robust approach independently of the predicate and dataset type, as shown in Fig. 5. It resulted to be only slightly influenced by source disagreement increase (UNI dataset case). Indeed, TSaC trust aimed to analyse and compare the trustworthiness of sources providing the most specific values that do not share partial order relationships. This was done selecting and returning all provided values higher than θ, i.e. δ = 1. Then ranking the values according to the weighted average trustworthiness of sources claiming them. Finally, filtering the first k values that did not share ordering relationships. Following this post-processing procedure, TSaC trust performance was not affected when the number of sources providing true general values increased (UNI dataset). Precisely, analysing the recall obtained by the different models from EXP to UNI dataset types, we observed that, when increasing sources that provided general true values, TSaC trust had a recall drop equal to 0.073 against a recall drop around 0.528 obtained by existing truth discovery models. Indeed, the average recall, over the different predicates, obtained by TSaC trust was 0.954, 0.912 and 0.881 respectively for EXP, LOW E and UNI dataset types. The average recall achieved by

A C C E P T E D M

A N U S C R I P T existing truth discovery models was 0.595, 0.243 and 0.067 respectively for EXP, LOW E and UNI dataset types. On the contrary TSbC IC performance was more influenced by source disagreement increase than TSaC trust performance. It is the post-processing strategy that employed the greedy algorithm to select the true value, i.e. at each step the selection phase chooses the values with the highest confidence. Then it ordered them w.r.t. their IC. Finally, it kept only values that shared a partial order. Therefore, it used as selection criterion, at each step, the value confidence. When sources provided more general true values the information associated to these claims were propagated to less values. Thus the confidence estimations were less informative in the last steps of the procedure. Anyway, also TSbC IC outperformed existing methods obtaining recall levels that were equal to 0.889, 0.670 and 0.531 for EXP, LOW E and UNI dataset respectively (thus with a recall drop of 0.358). Observing Fig. 5 we analysed for which predicates our approaches, TSaC trust and TSbC IC , obtained slightly lower performances. Even in these cases our models stills outperformed existing ones. Considering TSaC trust , the worst recall performance were achieved for birth-Place and BP predicate. Analysing the features shown in Table 2 related to the different predicate partial order, it is clear that this configuration setting was influenced by the average number of children in the partial order. Indeed birthPlace and BP were the two predicates with the highest children average number. Moreover, the ranking of predicates w.r.t. their recall corresponded to the predicate ranking w.r.t. the children average number in decreasing order. Otherwise, when considering TSbC IC approach the worst performance in terms of recall were obtained considering genre and BP predicate. We found out that TSbC IC performance depended both on the children average number and the average depth of expected solutions w.r.t. the maximum depth. Indeed, at each step of TSbC IC the probability of error is related to the number of alternatives among which the procedure can select a value. Moreover, it also related to the percentage of the partial order that the selection procedure has to traverse in order to reach the expected solutions w.r.t. the maximum depth. The probability of error increased when the part of the graph to traverse augmented. For instance genre predicate had the lowest children average number, but it obtained performance lower than MF, CC and birthPlace predicate. This because its expected values had a depth that required to traverse a bigger part of the partial order than in the other cases.

A C C E P T E D M A N U S C R I P T

To better understand the best parametrization for the post-processing procedure several experiments were conducted w.r.t. the different settings reported in Table 3. First of all, we compared the different post-processing strategies we proposed, evaluating the recall at different levels of k. The results are reported in Fig. 6. Note that we show the results for the predicates genre and MF, but a similar behaviour was obtained with all the others. We observe that the best results were obtained by the TSaC trust for any k value. It took advantage of the fact that it returned a set of alternatives as different as possible from each other and, at the same time, as specific as possible. Usually TSbC IC also outperformed the baseline model (Sums), but for higher values of k it was worse than Sums. This is because we forced the result of TSbC IC to share ordered relationships, while in the case of Sums, k values with the highest confidence were returned (no additional filter was applied on these values). Note that the recall of TSbC IC did not improve when increasing the value of k. This means that a situation in which a returned value is more specific than the expected one never occurs. This is in accordance with the policy we adopted to generate the synthetic datasets. Given the expected value, we cannot say anything about its descendants. Each of them may be a true specification of the expected truth or not. Consequently, we removed all of the descendants from the set of possible true and false values. In other words, no sources provide a claim that contains one of the descendants of the expected value associated with the considered data item. Otherwise, in all the other configurations, increasing the number of values returned (k) enhanced the recall. The TSaC IC and TSbC trust configurations were for the majority of cases worse than those of the baseline approaches. TSaC IC consists of the selection strategy with δ = 1, i.e. all provided values having confidence higher than θ are selected, and the use of IC as first ranking criterion. It obtained low performance because IC Seco was not a good discriminator among values that did not share ordering relationships. Indeed it is based on the number of descendant values and it may happen in situations in which x is the expected value and y has the same father as x. If x has descendants, while y has none, y will be preferred by the ranking based on the IC Seco even if it is not a true value. Thus, the W A trust ranking is more suitable in these cases. Otherwise TSbC trust is a post-processing strategy with δ = 0, i.e. at each step of the selection process only one value is selected, with the use of source average as ranking criterion. Obtaining low recall for this model means that

A C C E P T E D M A N U S C R I P T

A C C E P T E D M A N U S C R I P T

W A trust was not a good discriminator to rank the values sharing partial order relationships returned by the selection phase. Moreover, Fig. 6 shows that when disagreement among sources providing true values increased these two latter approaches (TSaC IC and TSbC trust ) could be useful anyway. The recall they obtained for k = 1 was higher than the recall of Sums model. Therefore in case of high level of disagreement also a not optimal procedure can be advantageous. As expected, in all the cases, the precision always decrease when increasing k. Moreover, comparing the different settings of the proposed approach, we observed that the ranking based on their precision performances was the same that the one obtained w.r.t. their recall. Therefore, we omit these repetitive results. Our further analysis focused on models TSaC trust and TSbC IC since they were the models among the proposed ones that achieved the best performances. We examined the impact of different threshold values, setting k = 1, w.r.t. the hierarchical evaluation metrics: F LCA , P LCA , R LCA and M GIA. The results are reported in Table 5. Considering TSbC IC , we noticed that, when slightly increasing θ, M GIA increased in the majority of the cases. This occurred because there are expected values (supported by few reliable sources) with a confidence lower than false ones (supported by many unreliable sources), even though the former have a higher W A trust than the latter. Thus, using TSbC IC and θ = 0, these values were selected as true values. Increasing θ allows the procedure to avoid a part of these errors. Indeed, eliminating the values with confidence score very low enables the procedure to return, with high probability, the father of the expected value. Anyway, further increasing the threshold caused a loss of M GIA because the returned values result to be very general. This does not happen with TSaC trust since this kind of errors are already overcome considering W A trust as first ranking criterion. Moreover, we observed that, in the majority of cases, when increasing θ the R LCA always decreased, while the P LCA always increased. Precisely, the highest R LCA for both TSaC trust and TSbC IC was obtained with θ = 0. The highest P LCA was obtained for both approaches with different θ values depending on the predicate as shown in Table 5. Summarising, the most effective configuration settings were TSaC trust and TSbC IC . They were both able to obtain better performance than existing truth discovery models. We noted that increasing the number of values returned for each data item allow increasing the performance. Nevertheless

A C C E P T E D M A N U S C R I P T

this can be applied only in the case where a group of experts can select the true values among the ones proposed by the proposed approach for each data item. Otherwise, we have to force the parametrization k = 1. Regarding the threshold θ, a high θ value is recommended when the application scenario does not permit to assume many risks. In this case it is important to have a high precision. In other words, obtaining a general true value than the specific false one is preferred. Therefore, the different parameter settings of the proposed post-processing procedure allow dealing with different application scenarios taking their requirements into account.

Conclusion

In this paper, we have presented a post-processing procedure able to select true values after estimation of the value confidences using the Adapt-edSums approach we proposed in our previous work. This general procedure can be used with any TD approach when partial order of values is taken into account as a priori knowledge. The post-processing process involves three main steps. The first one consists of the selection procedure. It aims to identify the set of possible true values using relationships among them and includes two parameters (δ and θ). Based on their tuning, different behaviours of the selection process can be obtained. The second step ranks the returned values of the selection phase. Finally, the third step permits to filter the top k values and ensure desirable properties (values that share or not relationships). The results confirmed our preliminary finding: using partial ordering of values helps to improve both source trustworthiness estimation, as already demonstrated by our preliminary study [START_REF] Beretta | How can ontologies give you clue for truth-discovery? an exploratory study[END_REF], and the true value identification. More precisely, the best results are obtained with the configuration of the algorithm that selects a set of alternatives, not sharing ordering relationships, and ranks them through the average trustworthiness of sources claiming those values. The results showed a similar behaviour on the datasets obtained by the two different ontologies (DBpedia and Gene Ontology). As prospects, we envisage to incorporate our framework by adapting it to another existing model. Indeed we would like to show the flexibility of our approach and further enhance the results. Moreover, we intend to explore other kinds of additional information such as correlations among data items and values. For instance, usually the birth location of people is correlated with the language they speak. Therefore, if we know that a person speaks

A C C E P T E D M A N U S C R I P T

Italian, we can increase the confidence in those claims that contain Italy as value for the bornIn predicate. More precisely, we plan to design a model that integrates, into existing approaches, information extracted from external knowledge bases in the form of rules. The idea is to add, in the confidence formula, a boosting factor indicating the confidence level of each claim according to the external knowledge base.

Figure 1 :

 1 Figure 1: Example of a partial order that may exist among values.

Figure 2 :

 2 Figure 2: Diagram of the overall TD procedure.

Algorithm 1

 1 True value set computation for any d ∈ D considering a partial order of values represented as a DAG G O = (V, E), a threshold θ ∈ (0, 1], a threshold δ ∈ [0, 1], and a function c : V → [0, 1], i.e. confidence of each value 1: procedure SelectionTrueValues(d, G O , c, θ, δ) 2:

  S C R I P T (a) # of sources per data item (b) # of dataitems per source

Figure 3 :

 3 Figure 3: Statistics of sources-data items for the CC datasets.

  reports, on the x axis, the values of Fig. 1 ordered according to their similarity measures w.r.t. the true value Malaga. Considering that v * d is Malaga and the EXP law, sources will more often provide values such as Malaga, Spain and City than values like Continent or Location. Otherwise, considering the UNI distribution, the probability of claiming these values will be the same. For the selection of the false values, only a single strategy was considered. A source that has to provide a false claim tends to provide a false value that is

Figure 4 :

 4 Figure 4: Distributions used to select true values.

Table 4 :Figure 5 :

 45 Figure 5: Recall obtained by applying our approaches TSbC IC (dotted line) and TSaC trust (dashed line), both with k = 1 and θ = 0, and the models provided by DAFNA API (solid lines) on the synthetic datasets.

Figure 6 :

 6 Figure 6: Recall obtained by applying our approach and the proposed models (with θ = 0) on the synthetic datasets w.r.t. the dataset type and number of returned values.

Table 1 :

 1 Interesting settings for the selection procedure.

Table 2 :

 2 Features of the different partial order structures.

	Features	CC	MF	BP	genre birthPlace
	Values	3984 10243 28822 1838	682658
	depth (max depth)	12	15	16	8	14
	Average depth	5,223 5,610 6,906	3,93	5,424
	Average # of children	1,451 1,196 1,898 1,041	1,535
	Max # of children	466	291	451	824	160194
	Leaves	3016	8192 14797 1563	663373

Table 3 :

 3 Set of experiments performed for each predicate. expected true value. For instance, if the true value is Malaga, then a source provides the value Portugal with an higher probability than the value Brazil. Moreover, sources tend to claim the same false values. Therefore, the probability of a value to be selected as false one increases w.r.t. the number of sources that previously claimed it.

	Conf.	θ	δ	Rank	Filter
	Name		1 st		2 nd
	TSbC trust 0,..., 0.5 0 W A trust TSbC IC 0,..., 0.5 0 IC Seco TSaC trust 0,..., 0.5 1 W A trust TSaC IC 0,..., 0.5 1 IC Seco	IC Seco W A trust IC Seco W A trust	V * ord V * ord V * disj V * disj
	similar to the

Table 5 :

 5 HEM obtained for the different predicates w.r.t. the model and the threshold θ considered.

	Model	TSbC IC TSaC T RU ST	Predicate HEM θ θ 0 0.1 0.2 0.3 0.4 0.5 0 0.1 0.2 0.3 0.4 0.5	F LCA 0.836 0.826 0.770 0.694 0.617 0.561 0.958 0.890 0.783 0.690 0.613 0.560	CC P LCA 0.824 0.874 0.943 0.986 0.991 0.988 0.959 0.954 0.967 0.985 0.989 0.989 R LCA 0.862 0.812 0.693 0.568 0.469 0.407 0.959 0.861 0.701 0.563 0.465 0.406	MGIA 0.879 0.910 0.907 0.890 0.855 0.818 0.963 0.945 0.917 0.887 0.851 0.816	F LCA 0.878 0.865 0.800 0.697 0.637 0.572 0.962 0.914 0.807 0.695 0.636 0.572	MF P LCA 0.870 0.907 0.960 0.990 0.994 0.994 0.964 0.965 0.971 0.989 0.994 0.994 R LCA 0.898 0.850 0.729 0.568 0.492 0.414 0.963 0.893 0.734 0.567 0.491 0.414	MGIA 0.909 0.937 0.926 0.892 0.862 0.824 0.966 0.958 0.928 0.890 0.860 0.824	F LCA 0.745 0.689 0.620 0.540 0.484 0.438 0.881 0.725 0.607 0.527 0.477 0.436	BP P LCA 0.732 0.859 0.957 0.979 0.976 0.968 0.886 0.935 0.963 0.976 0.974 0.967 R LCA 0.783 0.624 0.494 0.391 0.335 0.293 0.882 0.642 0.481 0.379 0.329 0.291	MGIA 0.792 0.853 0.836 0.774 0.707 0.641 0.881 0.865 0.815 0.754 0.696 0.635	F LCA 0.791 0.773 0.709 0.640 0.587 0.532 0.946 0.855 0.713 0.627 0.576 0.530	birthPlace P LCA 0.788 0.841 0.936 0.988 0.993 0.990 0.948 0.941 0.953 0.988 0.991 0.989 R LCA 0.800 0.744 0.601 0.483 0.424 0.372 0.946 0.813 0.602 0.469 0.414 0.369	MGIA 0.909 0.912 0.897 0.877 0.845 0.807 0.968 0.948 0.900 0.869 0.838 0.805	F LCA 0.784 0.775 0.708 0.657 0.617 0.571 0.963 0.930 0.729 0.657 0.617 0.571	genre P LCA R LCA 0.793 0.774 0.641 0.505 0.454 0.409 0.781 0.791 0.855 0.979 0.995 0.997 0.966 0.952 0.878 0.980 0.994 0.997 0.962 0.920 0.660 0.505 0.454 0.409	MGIA 0.903 0.904 0.889 0.887 0.867 0.833 0.974 0.967 0.897 0.887 0.867 0.833

Elements of V are here considered to be independent.

We mean by correlation the interdependences between entities, the relationships that may influence them.

Assuming that the value ordering is consensual.

Note that this codebase has been developed for experimental purpose and was not optimized to lower memory consumption and running time.

www.github.com/daqcri/DAFNA-EA


Eugénie Avril
email: eugenie.avril@univ-jfc.fr

Jordan Navarro
email: jordan.navarro@univ-lyon2.fr

Liên Wioland
email: lien.wioland@inrs.fr

Benoît Valery

Virginie Govaere
email: virginie.govaere@inrs.fr

Didier Gourc
email: didier.gourc@mines-albi.fr

Koosha Khademi
email: koosha.khademi@univ-jfc.fr

Christos Dimopoulos
email: c.dimopoulos@euc.ac.cy

Elisabeth Dargent
email: elisabeth.dargent@main-forte.fr

Nathalie Renaudeau
email: nrenaudeau@deret.com

Benoit Valery
email: benoit.valery@univ-jfc.fr

Julien Cegarra
email: julien.cegarra@univ-jfc.fr

Automation and Complacency: Insights from a Planning Task in the Transportation Domain

Keywords: Automation, Reliability, Complacency, Detection Failures, Trust

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Automation might provide large differences in functioning when comparing dynamic situation such as aircraft piloting to static situation as the planning of delivery in the transportation domain. Since the 1970s, different decompositions of degrees of automation have been proposed in the literature [START_REF] Sheridan | Human and computer control of undersea teleoperators[END_REF][START_REF] Endsley | Level of automation effects on performance, situation awareness and workload in a dynamic control task[END_REF]. It also has been proposed to include human-human model of cooperation to human-machine activities [START_REF] Hoc | From human-machine interaction to human-machine cooperation[END_REF]. According to Parasuraman [START_REF] Parasuraman | Humans and automation: Use, misuse, disuse, abuse[END_REF], different failures in the cooperation between the human operator and the automated system can occur such as the complacency phenomenon. This phenomenon occurs when the human operator is not questioning the actions of the automated systems even if these were wrong. Automation is often considering in the ergonomic literature as an action execution intervening in a dynamic situation. The ecological interface design (EID) [START_REF] Vicente | Ecological interface design: Theoretical foundations[END_REF], allow extending this point of view by focusing on the importance of problem representation. Thus, the design of external representations has become central in this new type of automation [START_REF] Vicente | Ecological interface design: Progress and challenges[END_REF][START_REF] Zhang | Representations in distributed cognitive tasks[END_REF]. That is the case in the planning of delivery in the transportation domain where the human operator faces a large set of information. The automation is present through an interface where data is pre-processed, thus facilitating information seeking and finally decision making. The objective of the study is to demonstrate that the failures of the cooperation between the human operator and the automation can relate to "action execution" (automation of command) but also to "data simplification" (automation of signaling). We hypothesized an effect of the degree of reliability of the signaling automation and of the degree of reliability of the command automation on the error detection rate

Related Work

Many studies showed the emergence of complacency between human and automation [START_REF] Bagheri | Considering subjective trust and monitoring behavior in assessing automation-induced "complacency[END_REF][START_REF] Parasuraman | Performance consequences of automation-induced'complacency[END_REF][START_REF] Bagheri | The impact of context-related reliability on automation failure detection and scanning behaviour[END_REF]. This is particularly present in studies where the reliability of automation is modulated. Unability to detect automation failures is used to demonstrate the evidence of this phenomenon [START_REF] Bagheri | Considering subjective trust and monitoring behavior in assessing automation-induced "complacency[END_REF][START_REF] Parasuraman | Performance consequences of automation-induced'complacency[END_REF][START_REF] Bagheri | The impact of context-related reliability on automation failure detection and scanning behaviour[END_REF]. The study of eye movements also supports the hypothesis of the complacency through the attention allocation of the participant [START_REF] Parasuraman | Complacency and bias in human use of automation: An attentional integration[END_REF]. Bagheri and Jamieson [START_REF] Bagheri | Considering subjective trust and monitoring behavior in assessing automation-induced "complacency[END_REF] did compare different levels of automation reliability. They showed that when the reliability was constant and high, the mean time between fixations in the automated task was higher compared than the other reliability levels. These authors explained the importance of eye movement analysis to better understand the participant's allocation strategies, in addition to the failure detection performance.

Trust of the human operator towards the system is also related to this phenomenon. Here the trust in the system is related to the automation performance [START_REF] Lee | Trust, control strategies and allocation of function in humanmachine systems[END_REF]. All of these studies have in common to use the Multi Attribute Task Battery, a micro world of aircraft piloting that can present both "action execution" and "data simplification" automation [START_REF] Comstock | The multi-attribute task battery for human operator workload and strategic behavior research[END_REF].

In our study, we hypothesize that when automation reliability is high, the participant will tend to be "complacent" with the automated system and therefore will not neces-sarily detect and react correctly to automation failures. Contrary, with a highly unreliable automated system, the participant will regain control (ie. a lower confidence) and will more easily detect errors (ie. a lower complacency). Indeed, when automation fails in the task, the participant does the task instead of automation and thus regain control.

3

Research Methodology

Design

We confronted 96 participants to 4 conditions of reliability of automation (24 in each condition). The 4 levels of reliability of the automation were 0%; 56.25%; 87.5% and 100%. Two types of automation were used: an automation of command and an automation of signaling. The reliability of the command automation was an intra-subject variable; the participants performed the 4 levels of reliability. Conversely, the reliability of signaling automation was inter-subject; each condition corresponding to a level of reliability (and therefore the 4 levels of reliability "execution").

As the experiment is currently underway, only two conditions could be performed by the participants at the moment (0% and 56.25% of signaling automation).

3.2

The Multi Attribute Task Battery Fig. 1. The Multi Attribute Task Battery.

Each participant has to perform three tasks in parallel. The first task was a monitoring task (Fig 1 . Top left). This task consisted of four columns. In a normal situation, the cursor fluctuated around the center of the column. In case of failure, the cursor freezed in the lower part or the upper part of the column (and not in the center) and the "failure" light changed to red. When there was a failure, the participant had to press F1 (if the cursor was blocked in column 1), F2 (column 2), F3 (column 3) and F4 (column 4).

In our study, this task was automated. The cursor was automatically unblocked after 10 seconds when there was a failure. However, the automated system might dysfunction: sometimes, the cursor could not be unblocked (command automation) and the light did not change to red (signaling automation) while there was a failure. In these cases, the participant had to regain control by pressing the corresponding key. The participant was warned of "possible automation failures, in the release of cursor to nominal state or in the color signalling."

The resource management task consisted of several tanks (Figure 1 bottom). The goal is to maintain tanks A and B at 2500 units each (optimal value). However, the fuel emptied into these two tanks and the participant had to activate pumps to use the safety tanks and to keep the values in these tanks. The reserve tanks E and F were unlimited unlike other tanks whose liquid level was displayed under them. The different tanks did not have the same rate of fluctuation of the liquid. Thus, the pumps 1 and 2 had a flow rate of 800; pumps 3, 4, 5 and 6 had a flow rate of 600; pumps 7 and 8 had a flow rate of 400. When the participant activated a pump, the flow rate appeared on the right. To fill the main tanks, participants had to use the number located on their keyboard.

The last task is a compensatory tracking task and the subject's task is to keep the target in the center of the window with a Joystick (Figure 1 top right).

We used an SMI Eye Tracker to measure eye movements (at a 120Hz sampling rate).

Results

The results are not final because the experiment is still underway. Therefore only the first results on two conditions are described below (0% and 56.25% of signaling automation).

The effect of reliability of the automation signaling on the performance was analyzed. Condition 4 of reliability (100%) was excluded in calculating the performance of the monitoring task because there was no detection of automation failures and therefore no performance to measure. No overall effect of the command reliability was found (Figure 2). Concerning the signal reliability, participants perform better in the resource task than in the monitoring task and the tracking task.

The performance in the monitoring task is also better with a high reliability. More precisely, we can note an effect of the signal reliability on performance in the system monitoring task F(1, 30) = 4.64, p<.05. Fig. 2. Performance in each task and the four levels of command reliability. The higher the index the better is the performance. Fig. 3. Performance in each task and the two levels of signal reliability. The higher the index the better is the performance.

The analysis of eye movements showed no effect for the command reliability (Figure 4). However concerning the signal reliability (Figure 5) the dwell time proportion is more important in the tracking task than in the resource management task and last in the tracking task F(2, 60) = 32.84, p <.05. Therefore, reliability of the automation signaling impacts the performance of the participants and their eye movements (task sampling). Full results (87.5% and 100%) are however necessary to confirm (or not) our hypothesis about a complacent behaviour. They will be discussed at the light of Bagheri and Jamieson's study on automation reliability [START_REF] Bagheri | Considering subjective trust and monitoring behavior in assessing automation-induced "complacency[END_REF][START_REF] Bagheri | The impact of context-related reliability on automation failure detection and scanning behaviour[END_REF].

Fig. 4 .

 4 Fig. 4. Dwell time proportion for each task and the four levels of command reliability.

Fig. 5 .

 5 Fig. 5. Dwell time proportion for each task and the two levels of signal reliability.