Trust is a broad concept which, in many systems, is reduced to reputation estimation. However, reputation is just one way of determining trust. The estimation of trust can be tackled from other perspectives as well, including by looking at provenance. In this work, we look at the combination of reputation and provenance to determine trust values. Concretely, the first contribution of this paper is a standard procedure for computing reputation-based trust assessments. The second is a procedure for computing trust values based on provenance information, represented by means of the W3C standard model PROV. Finally, we demonstrate how merging the results of these two procedures can be beneficial for the reliability of the estimated trust value. We evaluate our procedures and hypothesis by estimating and verifying the trustworthiness of the tags created within the Waisda? video tagging game, launched by the Netherlands Institute for Sound and Vision. Within Waisda?, tag trustworthiness is estimated on the basis of user consensus. Hence, we first provide a means to represent user consensus in terms of trust values, and then we predict the trustworthiness of tags based on reputation, provenance and a combination of the two. Through a quantitative analysis of the results, we demonstrate that using provenance information is beneficial for the accuracy of trust assessments.
From deciding the next book to read to selecting the best movie review, we
often use the reputation of the author to ascertain the trust in the thing itself.
Reputation is an important mechanism in our set of strategies to determine
trust. However, we may base our assessment on a variety of other factors as well,
including prior performance, a guarantee, or knowledge of how something was
produced. Nevertheless, many systems, especially on the Web, choose to reduce
trust to reputation estimation and analysis alone. In this work, we take a
multifaceted approach. We look at trust assessment of Web data based on reputation,
provenance (i.e., how data has been produced), and the combination of the two.
We use the term “trust” for the trust in information resources and “reputation”
for the trust in agents (see the work of Artz and Gil [
We know that over the Web “anyone can say anything about any topic” [
We first propose a procedure for computing reputation that uses basic
evidential reasoning principles and is implemented by means of subjective logic
opinions [
The rest of the paper is organized as follows: Section 2 describes related work, Section 3 describes the dataset used for our evaluations, Section 4, 5, 6 introduce respectively the trust assessment procedures based on reputation, provenance and their combination, including example associated experiments. Section 7 provides final conclusions. 1 A zip file containing the R and Python procedures used, together with the dataset, is retrievable at http://d.pr/f/YXoS
Trust is a widely explored topic within a variety of computer science areas. Here,
we focus on those works directly touching upon the intersection of trust,
provenance, Semantic Web and Web. We refer the reader to the work of Sabater and
Sierra [
Waisda? is a video tagging gaming platform launched by the Netherlands Institute for Sound and Vision in collaboration with the public Dutch broadcaster KRO. The game’s logic is simple: users watch video and tag the content. Whenever two or more players insert the same tag about the same video in the same time frame (10 sec., relative to the video), they are both rewarded. The number of matches for a tag is used as an estimate of its trustworthiness. When a tag which is not matched by others is not considered to be untrustworthy, because, for instance, it can refer to an element of the video not noticed so far by any user, or it can belong to a niche vocabulary, so it is not necessarily wrong. In the game, when counting matching tags, typos or synonymity are not taken into consideration.
We validate our procedures by using them to estimate the trustworthiness
of tag entries produced within the game. Our total corpus contains 37850 tag
entries corresponding to 115 tags randomly chosen. These tag entries correspond
to about 9% of the total population. We have checked their representativity of the
entire dataset. First, we compared the distribution of each relevant feature that
we will use in Section 5 in our sample with the distribution of the same feature
in the entire dataset. A 95% confidence level Chi-squared test [
Reputation is an abstraction of a user identity that quantifies his reliability as artifact author. Here, we use it to estimate the trustworthiness of the artifact. 4.1
We present a generic procedure for computing the reputation of a user with respect to a given artifact produced by him or her. proc reputation(user ; artifact ) evidence := evidence_selection(user ; artifact ) weighted _evidence := weigh_evidence(user ; artifact ; evidence) reputation := aggregate_evidence(weighted _evidence) Evidence Selection Reputation is based on historical evidence, hence the first step is to gather all pieces of evidence regarding a given person and select those relevant for trust computation. Typical constraints include temporal (evidence is only considered within a particular time-frame) or semantics based (evidence is only considered when is semantically related to the given artifact). evidence is the set of all evidence regarding user about artifact. proc evidence_selection(user ; artifact ) for i :=1 to length(observations ) do
if observations [i ]:user = user then evidence:add (observation[i ]) fi Evidence Weighing Given the set of evidence considered, we can decide if and how to weigh its elements, that is, whether to count all the pieces of evidence as equally important, or whether to consider some of them as more relevant. This step might be considered as overlapping with the previous one since they are both about weighing evidence: evidence selection gives a boolean weight, while here a fuzzy or probabilistic weight is given. However, keeping this division produces an efficiency gain, since it allows computation to be performed only on relevant items. proc weigh_evidence(user ; artifact ; evidence) for i := 1 to length(evidence) do
weighted _evidence:add (weigh(evidence[i ]; artifact ))
Aggregate evidence Once the pieces of evidence (or observations) have been
selected and weighed, these are aggregated to provide a value for the user
reputation that can be used for evaluation. We can apply several
different aggregation functions, depending on the domain. Typical functions are:
count, sum, average. Subjective logic [
p p + n + 2 d =
n p + n + 2 u =
2 p + n + 2 where b, d and u indicate respectively how much we believe that the artifact is trustworthy, non-trustworthy, and how uncertain our opinion is. p and n are the amounts of positive and negative evidence respectively. Subjective opinions are equivalent to Beta probability distributions (Fig. 1), which range over the trust levels interval [0 : : : 1] and are shaped by the available evidence.
Reputation Trust First, we convert the number of matches that each tag entry has into trust values: tag selection For each tag inserted by the user, we select all the matching tags belonging to the same video. In other contexts, the number of matching tags can be substituted by the number of “likes”, “retweets”, etc.. tag entries weighing For each matching entry, we weigh the entry contribution on the time distance between the evaluated entry and the matched entry. The weight is determined from an exponential probability distribution, which is a “memory-less” probability distribution used to describe the time between events. If two entries are close in time, we consider it highly likely that they match. If they match but appear in distant temporal moments, then we presume they refer to different elements of the same video. Instead of choosing a threshold, we give a probabilistic weight to the matching entry. 85% of probability mass is assigned to tags inserted in a 10 sec. range. tag entries aggregation In this step, we determine the trustworthiness of every tag. We aggregate the weighed evidence in a subjective opinion about the tag trustworthiness. We have at our disposal only positive evidence (the number of matching entries). The more evidence we have at disposal for the same tag entry, the less uncertain our estimate of its trustworthiness will be.
Non-matched tag entries have equal probability to be correct or not; We repeat this for each entry created by the user to compute his reputation. user tag entries selection Select all the tag entries inserted by user. user tag entries weighing Tag entries are weighed by the corresponding trust value previously computed. If an entry is not matched, it is considered as half positive (trust value 0.5) and half negative (1-0.5 = 0.5) evidence (it has 50% probability to be incorrect), as computed by means of subjective opinions. The other entries are also weighed according to their trust value.
So, user reputation can either rise or decrease as we collect evidence. user tag entries aggregation In turn, to compute the reputation of a user with respect to a given tag, we use all the previously computed evidence to build a subjective opinion about the user. This opinion represents the user reputation and can be summarized even more by the corresponding expected value or trust value (a particular average over the evidence count). 4.3
We implement the abstract procedure for reputation computation and we
evaluate its performance by measuring its ability to make use of the available evidence
to compute the best possible trust assessment. Our evaluation does not focus
on the ability to predict the exact trust value of the artifact by computing the
user reputation, because these two values belong to a continuous space, and they
are computed on a different basis. What we expect is that these two values hint
at trustworthiness in a similar fashion: when a tag is trustworthy, then both
trust value and reputation should be higher than a certain threshold and
viceversa. The validation, then, depends upon the choice of the threshold. We run
the procedure with different thresholds as presented in Fig.3. Low thresholds
correspond to low accuracy in our predictions. However, as the threshold
increases, the accuracy of the prediction rises. Moreover, we should consider that:
(1) It is preferable to obtain “false negatives” (reject correct tags) rather than
“false positives” (accept wrong tags), so high thresholds are more likely to be
chosen (e.g., see [
We previously adopted this same procedure to compute the trustworthiness
of tags on the Steve.Museum artifacts [
We focus on the “how” part of provenance, i.e., the modality of production of an artifact. (For simplicity, in the rest of the paper, we will use the word “provenance” to refer to the “how” part of it). We learn the relationships between PROV and trust values through machine learning algorithms. This procedure allows to process PROV data and, on the basis of previous trust evaluations, predict the trust level of artifacts. PROV is suitable for modeling the user behavior and provenance information in general. 5.1
We present the procedure for computing trust estimates based on provenance. proc provenance_prediction(artifact _provenance; artifact ) attribute_set := attribute_selection(artifact _provenance) attributes := attribute_extraction(attribute_set ) trust _levels_aggregation classi ed _testset := classify (testset ; trainingset ) attribute_selection Among all the provenance information, the first step of our procedure chooses the most significant ones: agent, processes, temporal annotations and input artifacts can all hint at the trustworthiness of the output artifact. This selection can lead to an optimization of the computation. attribute_extraction Some attributes need to be manipulated to be used for our classifications, e.g., temporal attributes may be useful for our estimates because one particular date may be particularly prolific for the trustworthiness of artifacts. However, to ease the recognition of patterns within these provenance data, we extract the day of the week or the hour of the day of production, rather than the precise timestamp. In this way we can distinguish, e.g., between day and night hours (when the user might be less reliable). Similarly, we might refer to process types or patterns instead of specific process instances. trust_level_aggregation To ease the learning process, we aggregate trust levels in n classes. Hence we apply classification algorithms operating on a nominal scale without compromising accuracy. classification Machine learning algorithms (or any other kind of classification algorithm) can be adopted at this stage. The choice can be constrained either from the data or by other limitations. 5.2
We apply the procedure to the tag entries from the Waisda? game as follows. attribute selection and extraction The provenance information available in Waisda? is represented in Fig. 2, using the W3C PROV ontology. First, for prov:Activity
rdf:type timeStamp
prov:startedAtTime rdf:type xmls:dateTime rdf:type
Game Tag Tydpci:npgaArtcOtifvity prov:upsreodv:used Video
prov:wasGeneratedBy prov:endedAtTime prov:wasAssociatedWith timeStamp + typingDuration User rdf:type rdf:type prov:Entity rdf:type
TagEntry rdf:type prov:Agent each tag entry we extract: typing duration, day of the week, hour of the day, game_id (to which the tag entry belongs), video_id. This the “how” provenance information at our disposal. Here we want to determine the trustworthiness of a tag given the modality with which it was produced, rather than the author reputation. Some videos may be easier to annotate than others, or, as we mentioned earlier, user reliability can decrease during the night.
For similar reasons we use all the other available features.
trust level classes computation In our procedure we are not interested in
predicting the exact trust value of a tag entry. Rather we want to predict the
range of trust within which the entry locates. Given the range of trust values
[0 : : : 1], we split it into 20 classes of length 0.5: from [0 : : : 0:5] to [9:5 : : : 10].
This allows us to increase the accuracy of our classification algorithm without
compromising the accuracy of the predicted value or the computation cost.
The values in each class were approximated by the middle value of the class
itself. For instance, the class [0:5 : : : 0:55] are approximated as 0.525.
regression/classification algorithm We use a regression algorithm to
predict the trustworthiness of the tags. Having at our disposal five different
features (in principle, we might have more), and given that we are not
interested in predicting the “right” trust value, but the class of trustworthiness,
we adopt the “regression-by-discretization” approach [
If we apply the “regression-by-discretization” approach for making provenance-based assessments, then we approximate our trust values. This is not necessary with the reputation approach. Had we applied the same approximation to the reputations as well, then provenance-based trust would have performed better, as proven with a 95% confidence level Wilcoxon signed-ranked test, because reputation can rely only on evidence regarding the user, while provenance-based models can rely on larger data sets. Anyway, we have no need to discretize the reputation and, in general, we prefer it for its lightweight computational burden. 6
We combine reputation- and provenance-based estimates to improve our predictions. If a certain user has been reliable so far, we can reasonably expect him/her to behave similarly in the near future. So we use reputation and we also constantly update it, to reduce the risk on relying on over-optimistic assumptions (if a user that showed to be reliable once, will maintain his/her status forever). However, reputation has an important limitation. To be reliable, a reputation has to be based on a large amount of evidence, which is not always possible. So, both in case the reputation is uncertain, or in case the user is anonymous, other sources of information should be used in order to correctly predict a trust value. The trust estimate based on provenance information, as described in Section 5, is based on behavioral patterns which have a high probability to be shared among several users. Hence, if a reputation is not reliable enough, we substitute it with the provenance-based prediction. 6.1
The algorithm looks like the following: proc provenance_prediction(user ; artifact ) q _ev = evaluate_user _evidence(user ; artifact ) if q _ev > min_evidence then predict _reputation else predict _provenance fi evaluate_user_evidence This function quantifies the evidence. Some implementation examples: (1) count ; (2) compute a subjective opinion and check if the uncertainty is low enough. As future work we plan to investigate how to automatically determine q_ev and evaluate_user_evidence. 6.2
We adopted the predictions obtained with each of the two previous procedures. The results are combined as follows: if the reputation is based on a minimum number of observations, then we use it, otherwise we substitute it with the prediction based on provenance. We run this procedure with different values for both the threshold and the minimum number of observations per reputation. We instantiate the evaluate_user_evidence(user,artifact) function as a count function of the evidence of user with respect to a given tag.
Reputation combined with Provenance−based Trust Accuracy difference 6.3
Results
The performance of this algorithm depends both on the choice of the threshold for the decision and on the number of pieces of evidence that make a reputation reliable, so we ran the algorithm with several combinations of these two parameters (Fig. 3). The results converge immediately, after having set the minimum number of observations at two. We compared these results with those obtained before. Two Wilcoxon signed-rank tests (at 90% and 95% confidence level with respect to respectively reputation and provenance-based assessments) showed that the procedure which combines reputation and provenance evaluations in this case performs better than each of them applied alone. The improvement is, on average, about 5%. Despite the fact that most of the improvement regards the lower thresholds, which are less likely to be chosen (as we saw in Section 4), even at 0.85 threshold there is a 0.5% improvement. Moreover, we would like to stress how the combination of the two procedures performs better than (in a few cases, equal to) each of them applied alone, regardless of the threshold chosen.
Combining the two procedures allows us to go beyond the limitation of
reputation-based approaches. Substituting estimates based on poorly reliable
reputations with provenance-based ones improves our results without
significantly increasing our risks, since we have previously proven that the two
estimates are (on average) equivalent. Hence, when a user is new in a system (and so
his/her history is limited) or anonymous, we can refer to the provenance-based
estimate to determine the trustworthiness of his/her work, without running higher
risks. This improvement is at least partly due to the existing correlation between
the reputation and provenance-based trust assessments. A little positive
correlation (0.16) has been proved by a Pearson’s correlation test [
This paper explores two important components of trust assessments: reputation and provenance information. We propose and evaluate a procedure for computing reputation and one for computing trust assessments based on provenance information represented with the W3C standard PROV. We show that it is important to use reputation estimation for trust assessment, because it is simple, computationally light and accurate. We also show the potential of provenancebased trust assessments: these can be at least as accurate as reputation-based ones and can be used to overcome the limitations of a reputation based approach. In Waisda? the combination of the two methods revealed to be more powerful than each of the two alone. In the future we will investigate the possibility of automatically extracting provenance patterns usable for trust assessment, to automate, optimize and adapt the process to other case studies. We will also focus on the use of trust assessments as a basis for information retrieval. Acknowledgements We thank the Netherlands Institute for Sound and Vision for launching and guiding the Waisda? project, and our colleagues Michiel, Riste and Valentina for their support. This research was partially supported by the PrestoPRIME project, in the EC ICT FP7 program, and by the Data2Semantics and SEALINC Media projects in the Dutch national program COMMIT.