# Model-Driven Engineering for Formal Verification and Security Testing of
Authentication Protocols

Mariapia Raimondo  Dip. di Matematica e Fisica
Università della Campania “L. Vanvitelli”
Caserta, Italy
<EMAIL_ADDRESS>Stefano Marrone  Dip. di Matematica e Fisica
Università della Campania “L. Vanvitelli”
Caserta, Italy
<EMAIL_ADDRESS>Angelo Palladino  Aerospace Business Unit
Kineton srl
Napoli, Italy
<EMAIL_ADDRESS>
###### Abstract

Even if the verification of authentication protocols can be achieved by means
of formal analysis, the modelling of such an activity is an error-prone task
due to the lack of automated and integrated processes. This paper proposes a
comprehensive approach, based on the Unified Modeling Language (UML) profiling
technique and on model-transformation, to enable automatic analysis of
authentication protocols starting from high-level models. In particular, a
UML-based approach is able to generate an annotated model of communication
protocols from which formal notations (e.g., AnBx, Tamarin) can be generated.
Such models in lower-level languages can be analysed with existing solvers
and/or with traditional testing techniques by means of test case generation
approaches. The industrial impact of the research is high due to the growing
need of security and the necessity to connect industrial processes and
equipment to virtualised computing infrastructures. The research is conducted
on two case studies: railway signalling systems and blockchain based
applications.

###### Index Terms:

Formal verification of security protocols, Model Driven Engineering,
Verification and Validation, Railway signalling, blockchain technology

##  I Introduction

Critical systems are now connected to the Internet due to an increase in the
complexity of their functionalities. This growth of complexity goes not only
in the direction of increasing the level of automation but also in opening
such systems to remote control. Security becomes a prime factor in such a
context: its lack could lead not only to economic loss or privacy leaks, but
also to damage to people and goods. This is the case of the railway signalling
systems, which is considered in this paper.

Another emerging domain where security plays an important role is the one
constituted by the emerging Distributed Ledger Technologies (DLTs) and,
despite its relatively recent adoption, a lack of security in DLT would have a
strong social impact. In fact, the blockchain technology, which is a
particular case of DLT, has received widespread support and acclamation. It
provides an infrastructure to manage transactions within a community without
the need of a trusted third party that supervises. Suffice to say,
cryptocurrencies are based on blockchain technology and they are one of the
main strategies of long-term investment adopted nowadays. Moreover, the
European Community has started writing down regulations111https://eur-
lex.europa.eu/legal-content/EN/TXT/?uri=CELEX%3A32022R0858&qid=1656931726550
to use them and proposals to prevent the usage of this technology for illicit
purposes222https://eur-lex.europa.eu/legal-
content/EN/TXT/?uri=CELEX%3A52021PC0422&qid=1656931726550.

Formal verification can be very useful both to check the correctness of the
behaviour of Industrial Control Systems (ICSs) and the achievement of the
security levels required by the new technologies such as the blockchain ones.
Unlike simulation and testing, this complementary technique is able to find
very specific conditions that could bring to a security flaw that has not been
considered in security test plans. Furthermore, formal methods are recommended
for certification purposes, especially in critical systems. Nonetheless, it is
worth underlining that: simulation and testing are still the most effective
methods to demonstrate the presence of a security issue in a specific
scenario; formal modelling and analysis often require specialised skilled
people, whose effort is devoted to low-level details error-prone activities.
The work presented in this paper deals with the problem of easing the work of
the modeller and unifying the approach to check security and behavioural
properties. The main objective is to provide a comprehensive approach,
supporting formal analysis and testing, based on Model-Driven Engineering
(MDE) techniques.

The approach presented in the paper is based on a traditional model-driven
process schema with the following elements. First, a UML Profile able to
capture the authentication related features of the modelled system is defined.
Then, a model transformation is provided to derive a formal notation from an
annotated UML model of the system. Finally, the produced model is analysed
with a set of techniques to verify security properties by formal analysis
and/or to generate test scripts to support the verification. Where possible,
the approach involves the use of existing and assessed solvers and toolchains.
More in particular, the UML Profile is used to enrich behavioural models with
cryptoprimitives and security properties. The model transformation is used to
derive an Alice & Bob (AnB) model which is then checked over security
properties. At the best of our knowledge, there is no unifying description
framework for the different tools that could be used in the formal
verification approach. This work will be also driven by two case studies: the
European Railway Traffic Management System (ERTMS)/European Train Control
System (ETCS) Key Management System (KMS) and the Tweetchain protocol.

The paper is structured as follows: Section II gives a quick revision of
related works, Section III describes the proposed approach, while Section IV
discusses about specific technical concerns. Finally, Section V resumes the
current developmental state of the approach.

##  II Related works

As mentioned in Section I, one of the adopted methodologies is the UML
profiling technique. In particular, up to now, there is no UML standard
profile — i.e., a UML profile defined by the Object Management Group — devoted
to the security analysis of blockchain-based protocols and applications, which
we aim to propose. However, regarding UML profiles for security analysis, the
QoS&FT profile [1] provides general support for the specification of Quality
of Service (QoS) characteristics and for risk assessment. Moreover, many
researchers contributed by proposing UML profiles useful for the modelling and
analysis of security properties of software systems, such as UML Sec [2] and
SecAM [3].

From a model-driven perspective, the scientific community has traditionally
proposed many model-based approaches that are specific to one simulation
platform per time (e.g., [4]). Moreover, a set of contributions regarding the
test case generation from high level models is present (e.g., [5]). The
combination of both formal modelling and test case generation is present in a
series of works that use, as an example, the model checking technique, as in
[6].

Regarding the railway domain, security is rarely approached in scientific
studies, which more frequently focus on other non-functional features as
safety, availability, performance and signalling. In [7] the authors provide
an approach to model and analyse the railway signalling system in Event-B.
Similarly, in [8] a process is presented to generate Generalized Stochastic
Petri Net (GSPN) and Promela models for analysis and test case generation
purposes. In [9], instead, a model-based approach is provided that is aimed at
improving the development of proprietary railway interlocking systems.

On the other side, security analysis in blockchain environments by means of
formal methods mainly focuses on smart contracts. The survey [10] discusses 35
papers from 2015 to 2019 just focusing on formalization of smart-contracts.

##  III Overview of the approach

Figure 1 describes the approach presented in the paper. The aim of the
approach is to facilitate the verification of security properties of
communication protocols. This goal is achieved by allowing the definition of
the protocol, and of the related security properties to be verified, in a
high-level language (Model level). Moreover, we leverage model-driven
techniques to automatically generate low-level artefacts and run verification
activities. The latter can be carried out using formal and simulation
techniques (Solver level and Simulation Framework). A key feature of this
approach is the possibility of using different platforms to analyse protocols,
that range from formal verification tools to test scripts generation ones.

Figure 1: Overview of the approach

The chosen high-level modelling language is the well-known UML, which provides
a set of different diagrams that can be used to model a given system. In
particular, dealing with communication protocols, good options are the
Sequence Diagrams and the protocol State Machine Diagrams. The first capture
the interactions between parties, whilst the second focus more on the state
changes of participants in reaction to message exchanges.

Since our aim is to ease the work of the modeller, a way to fill the gap that
arises from the creation of a UML model of a protocol is to provide more
protocol-related concepts at UML level. This can be done by applying the UML
Profiling technique to capture and define as a Profile the authentication
related features of the modeled systems.

In Fig. 1, UML and the AP Profile — Authentication Protocol Profile —
constitute the high-level language that can be used to model both the protocol
specification and the security properties to be verified (e.g., by means of
UML constraints or other annotated UML constructs). Then, thanks to a model
transformation, both the protocol and the security properties are translated
in a Low-level model. The latter is a tool-independent notation, for example
AnB. Finally, further model transformations are used to obtain formal models
and a set of specific solvers can be used:

  1. 1.

To formally check the model against the translated security properties;

  2. 2.

To get counterexamples of the unmatched properties to extract Abstract Test
Cases (ATCs) from such counterexamples;

  3. 3.

To transform, according to the presence of a system simulator framework, the
ATCs into an intruder model;

  4. 4.

To simulate such model (i.e., intruder and protocol participants) to get a
practical demonstration of the presence of the security flaw.

##  IV Towards an implementation of the approach

This section discusses three technical concerns to match in order to realize
the approach.

###  IV-A Reusabilty

One of the key goals of the proposed research is to define a methodology that
can be easily adapted in different domains. The sequence of the exchanged
messages, and the type of information they carry, can differ a lot among the
various authentication protocols. This difference is already present in
classical protocol descriptions (i.e., standards, white papers, technical
reports, etc.). The separation of these descriptions boosts the flexibility of
the approach. The concrete solution in this work considers two sub-languages.

The first is represented by a classical UML Profile: an example of the
concepts represented at this level are the message, that can be captured in
the UML Profile by a stereotype to annotate Sequence Diagram’s messages. At
the second level, there are instead specific textual notations, formalised by
Backus-Naur Form (BNF) grammars. These notations can be used to detail which
are the data exchanged (both in plain and cypher-texts) between communication
parties.

The UML Profile is separated from the specific notation and, thus, it can be
reused in different specific domains. When a modeller specifies a protocol,
he/she can use the stereotypes considered in the UML Profile to model and
annotate the UML diagrams accordingly. Moreover, as tagged values of UML
stereotypes give the possibility to add textual information, they are used
with the Transaction stereotype. By doing so, the text can be formatted
according to the specific grammar defined for the specific domain. A
preliminary design of this mechanism is published in [11].

###  IV-B Choice of the solution toolchain

One of the most valuable benefits coming from the adoption of MDE is that it
firmly separates the level of abstraction of the different artefacts.

Part of the implementation of the toolchain presented in this paper can be
clearly achieved reusing existing tools and integrating part of existing
project in ours. In particular, the work of Modesti [12] caught our attention,
since it provides the generation of analysable formal models starting from
semi-formal language models. The authors in a first phase of their work
developed a on-the-fly model checker called OFMC (Open-Source Fixed-Point
Model-Checker). It is a model checker naturally devoted to the analysis of
security protocols and it requires as input a model written in AnB/AnBx
language. This makes it an adequate component to be used as partial back-end
of our proposal.

In detail, the AnBx language is a formalized version of the well-known semi-
formal AnB notation. It provides a higher level of abstraction by providing a
easier way to model cryptographic primitives in the shape of a channel. In
fact, the mode of a channel allows the modeller to enforce or weaken the
security guarantees of messages exchange in a convenient style, decoupling the
protocol from the specific encryption method adopted.

It is valuable to underline that the Modesti’s toolchain does not represent
the only possible choice. In [13] and in [11], the Tamarin Prover model
checker has been used. In particular, in [13], Tamarin has been used as a
single language (i.e., detached by a MDE approach), while in [11] a model-
driven toolchain is proposed using a generic AnB notation and Tamarin as a
solving back-end.

###  IV-C Integrating formal analysis and testing

The community of security testing is wide and it considers finding
vulnerabilities and errors in low-level code and operating systems as well as
finding high-level protocol flaws. The formal methods and model-driven bodies
of knowledge are more prone to support the second kind of activity and, thus,
talking about the possibility of implementing security testing features in our
approach could seem strange.

As Fig. 1 reports, the testing “branch” of the approach (from Abstract Test
Cases) relies on the presence of a Simulation Framework whose purpose is to
define an executable abstraction of the behaviours of protocol parties. At
this point of the research, there is no specific requirement for such
frameworks: they could span from simple event based simulation to complex
hardware/system-in-the-loop environments.

A possible architecture for the Simulation Framework is here discussed. The
core of the architecture is a simulation engine executing the participant
models, which mainly exchange messages, and the intruder, which attempts to
intercepts such messages injecting malicious ones. The engine is supported by
these components: (1) a translator from the ATCs and security property to the
concrete notation for the test script; (2) a security monitor, which is in
charge of monitoring the security properties, raising exceptions in case of
property violations. The Simulation Framework is based on the presence of a
language for test scripting to express the models of the actors and of the
security properties.

##  V State of progress

We plan to prototype and apply the approach here presented to two different
case studies: one is the Tweetchain protocol, the other one is the Key
Management System of the ERTMS/ETCS.

The Tweetchain protocol, described in [14], is a lightweight version of the
blockchain paradigm. It mainly consists in a reinvention of the consensus
protocol to make the protocol applicable to Internet of the Things (IoT)
devices, which do not own the necessary computing power and memory to perform
one of the full consensus protocols available. In fact, the authors leveraged
the feature of IoT devices of being connected to the Internet to base the
consensus protocol on the famous social network Twitter, by using tweets, to
encode transactions, and meshed replications, to substitute the proof of work.
Currently, foundations were laid for the creation of a blockchain-specific UML
Profile, which could be a first version of the AP Profile. Moreover, a
specific textual notation for the Tweetchain data exchange has been provided,
that is expressed by a BNF grammar.

Furthermore, a transformation from a UML Sequence Diagram annotated with such
a profile to the AnB notation is designed. Finally, thanks to the already
available automatic translation provided by [15], it has been possible to
translate the AnB protocol into a Tamarin model [16]. Only formal analysis is
conducted up to now on this protocol. Previous published papers describing the
preliminary results on this case study are [13, 11].

To guarantee the security of signalling systems in modern railway, Key
Management System regulates the exchanges of the keys between trackside and
onboard controllers. The ETCS-KMS protocol is devoted to guarantee the
security of this exchange in an on-line environment [17].

In [18], a preliminary study on the application of the techniques here
presented is reported, focusing on a compositional approach of Tamarin
specification.

Fig. 2 wants to summarise the status of the development of the entire
approach. It recalls Fig. 1. The blue circles represent the part of the
research covered by the works about the Tweetchain protocol [13, 11], while
the pink ones are related to the ETCS-KMS case study [18].

Figure 2: Roadmap of the work

The next steps in this research will be: (1) the migration of the case studies
to the toolchain based on the work of Modesti, to exploit the translator from
AnBx to OFMC and related tools (in green in the figure); (2) to define the
blockchain-specific Profile and extend it to the AP Profile, to include also
the ETCS-KMS specific features (in red); (3) the automation of the approach by
means of the prototyping of key components (in yellow).

In particular, the original contributions of this work will be: (1) the
definition of a UML Profile for blockchain-based applications and
authentication protocols; (2) the integration of an intruder model in the
Simulation Framework, which is not present in any of the considered tools; (3)
the provision of a framework giving the evidence of attacks arisen from formal
analysis.

## Acknowledgment

The work of Mariapia Raimondo is granted by INPS — Istituto Nazionale di
Previdenza Sociale (Italy) — with the PhD program XXXVI cycle.

## References

  * [1] “UMLTM Profile for Modeling Quality of Service and Fault Tolerance Characteristics and Mechanisms Specification,” Object Management Group, Tech. Rep., 2005, formal-08-04-05.
  * [2] J. Jürjens, _Secure systems development with UML_. Berlin, Heidelberg: Springer, 2005.
  * [3] R. J. Rodríguez, J. Merseguer, and S. Bernardi, “Modelling security of critical infrastructures: A survivability assessment,” _Comput. J._ , vol. 58, no. 10, pp. 2313–2327, 2015.
  * [4] K. Anastasakis, B. Bordbar, G. Georg, and I. Ray, “UML2Alloy: A challenging model transformation,” _LNCS_ , vol. 4735, pp. 436–450, 2007.
  * [5] M. Utting and B. Legeard, _Practical Model-Based Testing_ , 2007.
  * [6] A. Gargantini and C. Heitmeyer, “Using model checking to generate tests from requirements specifications,” _SIGSOFT Softw. Eng. Notes_ , vol. 24, no. 6, p. 146–162, oct 1999.
  * [7] R. Bougacha, A. Ait Wakrime, S. Kallel, R. Ben Ayed, and S. Collart-Dutilleul, “A model-based approach for the modeling and the verification of railway signaling system,” 01 2019, pp. 367–376.
  * [8] S. Marrone, F. Flammini, N. Mazzocca, R. Nardone, and V. Vittorini, “Towards model-driven V&V assessment of railway control systems,” _International Journal on Software Tools for Technology Transfer_ , vol. 16, no. 6, pp. 669–683, 2014.
  * [9] F. Scippacercola, A. Zentai, and S. Russo, “Experiencing model-driven engineering for railway interlocking systems,” pp. 31–64, 2017.
  * [10] A. Singh, R. M. Parizi, Q. Zhang, K.-K. R. Choo, and A. Dehghantanha, “Blockchain smart contracts formalization: Approaches and challenges to address vulnerabilities,” _Computers & Security_, vol. 88, 2020.
  * [11] M. Raimondo, S. Bernardi, S. Marrone, and J. Merseguer, “An approach for the automatic verification of blockchain protocols: The tweetchain case study,” _Journal of Computer Virology and Hacking Techniques_ , to appear.
  * [12] M. Bugliesi, S. Calzavara, S. Mödersheim, and P. Modesti, “Security protocol specification and verification with AnBx,” _Journal of Information Security and Applications_ , vol. 30, pp. 46–63, 2016.
  * [13] M. Raimondo, S. Bernardi, and S. Marrone, “On formalising and analysing the tweetchain protocol,” in _ICISSP 2021 - Proceedings of the 7th International Conference on Information Systems Security and Privacy_ , 2021, pp. 781–791.
  * [14] F. Buccafurri, G. Lax, S. Nicolazzo, and A. Nocera, “Overcoming limits of blockchain for iot applications,” in _ACM International Conference Proceeding Series_ , vol. Part F130521, 2017.
  * [15] M. Keller, “Converting Alice&Bob Protocol Specifications to Tamarin,” ETH Zurich, 2014, Bachelor’s Thesis.
  * [16] S. Meier, B. Schmidt, C. Cremers, and D. Basin, “The TAMARIN prover for the symbolic analysis of security protocols,” in _proc. of CAV 13_ , vol. LNCS 8044, 2013.
  * [17] UNISIG, “On-line Key Management FFFIS - Subset 137.”
  * [18] M. Raimondo, “Formal modeling and analysis of cryptographic schemes in railway systems.” 2020, Master’s Thesis.


# Discovering Multiple Truths with a Hybrid Model

Furong Li† Xin Luna Dong‡ Anno Langen‡ Yang Li‡

†National University of Singapore ‡Google Inc., Mountain View, CA, USA
<EMAIL_ADDRESS>{lunadong, arl<EMAIL_ADDRESS>
###### Abstract

Many data management applications require integrating information from
multiple sources. The sources may not be accurate and provide erroneous
values. We thus have to identify the true values from conflicting observations
made by the sources. The problem is further complicated when there may exist
multiple truths (e.g., a book written by several authors). In this paper we
propose a model called Hybrid that jointly makes two decisions: how many
truths there are, and what they are. It considers the conflicts between values
as important evidence for ruling out wrong values, while keeps the flexibility
of allowing multiple truths. In this way, Hybrid is able to achieve both high
precision and high recall.

##  1 Introduction

When consolidating information from different sources, we may observe
different values provided for the same entity. Consequently, we need to
identify the correct values from conflicting observations made by multiple
sources, which is known as the data fusion (or truth discovery) problem [2,
5]. We illustrate the problem using the example below.

###### Example 1.1

Table 1 shows the information collected from three sources regarding
equipments of two winter sports: ice hockey and snowboarding. We can see that
four different values are provided for the entity ice hockey (helmet, stick,
boots and skis), while only the first two are correct. The goal of the truth
discovery problem is to identify the correct values from Table 1.

The simplest solution to the truth discovery problem is majority vote:
consider the value provided by the largest number of sources as the truth. For
example, for the entity snowboarding, we select board as the truth since it is
provided by two sources while neck guard is only provided by one source.
However oftentimes different sources have different qualities, and one may
want to distinguish them. The authors of [8, 1] measure the quality of a
source $s$ by its accuracy, which is the probability that a value provided by
$s$ is correct. Then the truth can be decided through a weighted vote, where a
source with higher accuracy is assigned to a higher weight; the value with the
highest vote is selected as the truth. The intuition behind this approach is
that values provided by more accurate sources are more likely to be true.

Table 1: Information collected from different sources regarding equipments of various winter sports. $\surd/\times$ indicates the correctness. | entity | attribute | value | sources
---|---|---|---|---
$\surd~{}o_{1}$ | ice hockey | equipments | helmet | $s_{1},s_{3}$
$\surd~{}o_{2}$ | ice hockey | equipments | stick | $s_{1},s_{2}$
$\times~{}o_{3}$ | ice hockey | equipments | boots | $s_{2}$
$\times~{}o_{4}$ | ice hockey | equipments | skis | $s_{3}$
$\surd~{}o_{5}$ | snowboarding | equipments | board | $s_{2},s_{3}$
$\times~{}o_{6}$ | snowboarding | equipments | neck guard | $s_{1}$

The limitation of the above methods is that when multiple truths exist, they
at best find one of them while missing the rest. We thus refer to them as
single-truth approaches. While truth discovery algorithms usually compute a
probability $p(v)$ of each value $v$ being true, in single-truth approaches,
the probabilities of all values sum up to 1 since they assume there is only
one true value.

###### Example 1.2

We use Accu [1] as a representative of single-truth approaches, and then
compute the probabilities of the values provided from ice hockey equipments.
Assuming all sources have the same accuracy 0.6, we obtain the probabilities
in Table 2 (see the first line). We observe that the probabilities of the four
values add up to 1, so even the true values (helmet and stick) have rather low
probabilities.

Table 2: Value probabilities computed by different approaches for (ice hockey, equipments). | helmet | stick | boots | skis
---|---|---|---|---
Single-truth [1] | 0.47 | 0.47 | 0.03 | 0.03
Multi-truth [7] | 0.63 | 0.63 | 0.54 | 0.54
Hybrid | 0.92 | 0.92 | 0.08 | 0.08

To address the above problem, multi-truth approaches [9, 7] have been proposed
recently. They compute the probability for each value separately, and thus do
not require the probabilities of all values sum up to 1. Instead, they compute
both the probability $p(v)$ of $v$ being true, and the probability $p(\neg v)$
of $v$ being false, where $p(v)+p(\neg v)=1$. Then a value $v$ is consider
true if $p(v)>p(\neg v)$, that is, $p(v)>0.5$.

An unknown semantics is used to capture the nature of multi-truth: if a source
$s$ does not provide the value $v$, $s$ means that it does not know whether or
not $v$ is correct (instead of saying $v$ is incorrect). Thus, apart from
accuracy (also called precision in some methods), multi-truth approaches also
measure the quality of a source $s$ by its recall, the probability that a
truth is provided by $s$. Intuitively, values provided by high-precision
sources are likely to be true (i.e., a higher $p(v)$), and values not provided
by high-recall sources are likely to be false (i.e., a higher $p(\neg v)$). In
this way, they derive $p(v)$ and $p(\neg v)$ from the precision and recall of
the sources, and then normalize with the equation $p(v)+p(\neg v)=1$.

###### Example 1.3

Table 2 also shows the value probabilities computed by the multi-truth
approach PrecRec [7]. Assuming a precision of 0.6 and recall of 0.5 for each
source, PrecRec will decide that all provided values are true, resulting in
false positives (i.e., boots and board).

In practice, even multi-truth items often have only a few true values instead
of infinite number of truths. Existing methods [9, 7] cannot capture this
because they decide the truthfulness of each value independently, without
considering other values provided for the entity and thus lack a global view
of the entity. As a result, they suffer from low precision when the sources
have low coverage or noisy observations (as shown later in Section 5).

In this paper we introduce a new solution to the truth discovery problem,
called Hybrid, which works for multi-truth applications. Based on the values
provided for an entity, Hybrid makes two decisions: (i) how many truths there
are, and (ii) what they are. Essentially it interleaves the two decisions and
finds the truths one by one. Conditioning on a sequence of true values that
have been selected previously, it computes (1) the probability of a value $v$
being the next truth, and (2) the probability that there is no more truth. In
this way, Hybrid combines the flexibility of the multi-truth approaches of
allowing multiple truths for an entity, and the inherent strength of the
single-truth approaches of considering conflicts between values as important
evidence for ruling out wrong values. Therefore, it obtains both high
precision and high recall.

Note that the multi-truth setting should be considered more general than the
single-truth setting, since it allows for the existence of multiple truths
(but not necessarily). Our proposed method also works for entities with a
single-truth because it can automatically decide the number of truths.
Although one can easily extend a single-truth approach to handle multi-truth
applications by setting a threshold (i.e., consider all values with predicted
probabilities over $\lambda$ as true), it is hard to find a threshold that
works for all entities. We discuss a slightly more sophisticated extension in
Section 3.

##  2 Definitions and Notations

Data item, value, source, observation. We call an (entity, attribute) pair a
data item, denoted by $d$. Then we have a set $\cal S$ of sources provide
values on $d$. Let $v$ be a value provided by a source $s\in{\cal S}$ for the
data item $d$, the pair $(d,v)$ is then called an observation of $s$. For
instance, there are two data items in Table 1: $d_{1}=$ (ice hockey,
equipments) and $d_{2}=$ (snowboarding, equipments); there are 4 values
provided for $d_{1}$ and 2 values provided for $d_{2}$. In total we have 6
observations made by 3 sources $\\{s_{1},s_{2},s_{3}\\}$.

Given a data item $d$, we use $\Psi$ to denote the set of observations made on
$d$ (we dismiss $d$ in the notation for simplicity); then $\Psi(s)$ denotes
the values from $s$. For example in Table 1, for the item (ice hockey,
equipments), $\Psi(s_{1})=\\{{\rm helmet,stick}\\}$. Table 3 summarizes the
notations we use in this chapter.

Table 3: Table of notations. Notation | Description
---|---
$d$ | a data item
$v$ | a value
$s$ | a source that provides values
${\cal S}_{v}$ | the set of sources that provide the value $v$
$\Psi$ | the mapping between sources and their provided values
$\Psi(s)$ | the set of values provided by $s$ on a data item
$n$ | the number of wrong values in the domain
${\cal O}$ | a sequence of values that have been selected as truths
$\perp$ | “there is no more truth”

Problem definition. Given a data item $d$ and a set ${\cal S}$ of sources, let
$\cal V$ denote the set of values provided by $\cal S$ on $d$. Our goal is to
compute a probability $p(v|\Psi)$ for each value $v\in\cal V$ being true based
on the source observations.

In this chapter we focus on the case where the sources are independent of each
other; we can extend our model with techniques from [1, 7] to address
correlations between sources.

##  3 A Hybrid Model

This section presents a truth discovery model, called Hybrid, which allows for
the existence of multiple truths. Essentially, Hybrid makes two decisions for
a data item $d$: (i) how many truths there are, and (ii) what they are.

One can imagine a natural solution that processes in two steps: (1) decide the
number of truths $k$ with a single-truth method, treating “the number of
truths for $d$” as a data item and $|\Psi(s)|$ as the value provided by $s$;
(2) apply the single-truth method on $\cal V$ and select the values with
top-$k$ probabilities as the truths. Although this approach often outperforms
both the existing single-truth and multi-truth approaches (as we shall show
later in Section 5), it has two problems. First, it does not update the value
probabilities according to its belief of the number of truths (all
probabilities still sum up to 1). Second, separating the decisions into two
steps may hurt precision when many sources provide more values than the
truths: once the first step decides the number of truths $k$, the second step
will fill in $k$ values, possibly with values lacking strong support from the
sources.

Different from the above baseline approach, Hybrid combines the two steps and
finds the truths one by one. Conditioning on a sequence ${\cal O}$ of true
values that have been selected previously, it decides (1) the probability of a
value $v$ being the next truth, denoted by $p(v|{\cal O},\Psi)$, and (2) the
probability that there is no more truth, denoted by $p({\perp}|{\cal
O},\Psi)$. These are disjoint decisions so their probabilities sum up to 1.
Thus, when selecting the next truth, Hybrid basically applies a single-truth
method.

However, when deciding whether there is any more truth (i.e., $p({\perp}|{\cal
O},\Psi)$), Hybrid incorporates the unknown semantics used in multi-truth
approaches: if a source provides 2 values for an item $d$, it claims that it
knows 2 values of $d$, instead of claiming that $d$ has only 2 values.

In this way, Hybrid combines the flexibility of the multi-truth methods of
allowing multiple truths for a data item, and the inherent strength of the
single-truth methods of considering conflicts between values as important
evidence for ruling out wrong values. Therefore, it obtains both high
precision and high recall.

Moreover, Hybrid leverages the typical number of truths for each type of data
items; for example, a person typically has 2 parents and 1-5 children. Hybrid
allows incorporating such knowledge as the a priori probability of
$p({\perp}|{\cal O},\Psi)$, which further improves performance. Bear in mind
that a priori probabilities have much less effect than observations on
computing a posteriori probabilities, so Hybrid applies a soft constraint
rather than a hard one.

We next describe the Hybrid model in more details, and answer the following
question: since there should not exist any ordering between the truths, how
would Hybrid avoid the consequence of finding the truths one by one?

###  3.1 Overall Probability of a Value

Consider computing $p(v|\Psi)$ for a value $v\in{\cal V}$. As we select truths
one by one, there can be various sequences of truths (of any length below
$|{\cal V}|$) that are selected before $v$. We call each sequence ${\cal O}$ a
possible world and denote by $\Omega$ all possible worlds. Then the
probability of $v$ is the weighted sum of its probability in each possible
world:

$p(v|\Psi)=\sum_{{\cal O}\in\Omega}p(v|{\cal O},\Psi)\cdot p({\cal O}|\Psi).$
(1)

where $p({\cal O}|\Psi)$ is the probability of entering the possible world
${\cal O}$.

Let ${\cal O}=v_{1}v_{2}\dots v_{|{\cal O}|}$, $v\notin{\cal O}$, denote a
possible world with the sequence $v_{1},v_{2},\dots,v_{|{\cal O}|}$ of values
selected as truths. Let ${\cal O}_{j}$ denote a prefix of ${\cal O}$ with
length $j$ and ${\cal O}_{0}=\varnothing$. Applying the chain rule leads us
to:

$p({\cal O}|\Psi)=\prod_{j=1}^{|{\cal O}|}p(v_{j}|{\cal O}_{j-1},\Psi).$ (2)

Now the only piece missing from Eq.s (1)-(2) is the conditional probability
$p(v|{\cal O},\Psi)$, which we describe in the next subsection.

Back to the question we asked previously, even though Hybrid finds truths one
by one, it is order-independent as it considers all possible ways to select a
value and computes an overall probability. Apparently enumerating all possible
worlds is prohibitively expensive; we describe a polynomial-time approximation
in Section 4.

###  3.2 Conditional Probability of a Value

Now consider computing $p(v|{\cal O},\Psi)$. Under a possible world ${\cal
O}$, we either choose one of the remaining values as the next truth or decide
that there is no more truth, thus $\sum_{v^{\prime}\in{\cal V}\setminus{\cal
O}}p(v^{\prime}|{\cal O},\Psi)+p({\perp}|{\cal O},\Psi)=1$; this is similar to
what we have in single-truth approaches. Then according to the Bayes Rule, we
have

$p(v|{\cal O},\Psi){=}{p(\Psi|{\cal O},v)p(v|{\cal
O})\over\sum\limits_{v^{\prime}\in{\cal V}\setminus{\cal O}}p(\Psi|{\cal
O},v^{\prime})p(v^{\prime}|{\cal O})+p(\Psi|{\cal O},\perp)p({\perp}|{\cal
O})}.$ (3)

Here the inverse probability $p(\Psi|{\cal O},v)$ is the probability of
observing $\Psi$ if $v$ is the next truth. The a priori probability $p(v|{\cal
O})$ is the probability of $v$ being the next truth regardless of the
observations $\Psi$. The same applies to $p(\Psi|{\cal O},\perp)$ and
$p({\perp}|{\cal O})$.

Before we can compute these two sets of probabilities, we first define the
metrics that are used to measure the quality of a source.

####  3.2.1 Source-quality metrics

Imagine that there are $m$ latent slots for truths of a data item, and a
source $s$ is asked to fill the slots. The number of slots is unknown to $s$,
so it iteratively performs two tasks: predict whether there exists another
slot (i.e., another truth), and if so, fill the slot with a value. We thus
capture the quality of a source with two sets of metrics: that for deciding
whether there exists a truth, and that for deciding the true values.

The first set of metrics enables the unknown semantics for multi-truth, and it
includes two measures:

  * •

Precision $P(s)$, the probability that when $s$ provides a value, there indeed
exists a truth;

  * •

Recall $R(s)$, the probability that when there exists a truth, $s$ provides a
value.

Note that our $P(s)$ and $R(s)$ are different from the same notions in [7]: we
only measure how well $s$ predicts whether or not there exists a truth, but
not how well $s$ predicts what the truth is; in other words, we do not require
the value provided by $s$ to be the same as the truth. To facilitate later
computations, we next derive the false positive rate of $s$, denoted by
$Q(s)$, from $P(s)$ and $R(s)$ by applying the Bayes Rule (see [7] for
details):

$Q(s)={\alpha\over 1-\alpha}\cdot{1-P(s)\over P(s)}\cdot R(s),$ (4)

where $\alpha$ is the a priori probability111Previous work [7] has shown that
a priori probabilities play a minor role on final results comparing with the
source observations. that a provided value corresponds to a truth slot.
Intuitively, $Q(s)$ is the probability that $s$ still provides a value when
there is no truth slot.

The second set of metrics follows single-truth models to address the conflicts
between values. It contains one measure: accuracy $A(s)$, the probability that
a value provided by $s$ for a “real” truth slot is true (i.e., $s$ provides a
true value after it has correctly predicted the existence of a truth slot).
Note that values provided for non-existing truth slots, which are absolutely
false, are not counted here, as they have been captured by $P(s)$.

We describe how we compute these metrics in the next subsection, and
demonstrate the basic idea of them in the example below.

###### Example 3.1

Consider the source $s_{2}$ and the data item $d_{1}=$ (ice hockey,
equipments) in Table 1. Suppose ice hockey requires 3 equipments . We observe
that $s_{2}$ provides 2 values on $d_{1}$, meaning that it predicts that there
are 2 slots for truths; among the provided values one is true. Therefore for
this particular data item, $s_{2}$ has precision $2/2=1$, recall $2/3=0.67$,
and accuracy $1/2=0.5$.

Now consider data item $d_{2}=$ (snowboarding, equipments), which has 1 truth.
As $s_{2}$ provides 1 correct value, its precision, recall, and accuracy for
this item are all 1.

If $s_{2}$ provides only these 2 data items, on average, we have
$P(s_{2})=\frac{1+1}{2}=1,R(s_{2})=\frac{0.67+1}{2}=0.83$, and
$A(s_{2})=\frac{0.5+1}{2}=0.75$.

####  3.2.2 Inverse probabilities

We are now ready to derive the inverse probabilities $p(\Psi|{\cal O},v)$ and
$p(\Psi|{\cal O},\perp)$ in Eq. (3). Assuming that the set of sources are
independent, we have

$p(\Psi|{\cal O},v)=\prod_{s\in{{\cal S}}}p(\Psi(s)|{\cal O},v),$ (5)

and similar for $p(\Psi|{\cal O},\perp)$. In the following computations, when
conditioning on $({\cal O},v)$, we think that ${\cal O}\cup\\{v\\}$ are the
only set of truths; similarly, when conditioning on $({\cal O},\perp)$, we
think ${\cal O}$ is the only set of truths. This is known as the closed-world
assumption, and according to [6], it should give the same results as the open-
world assumption where the truths form a superset of ${\cal O}\cup\\{v\\}$.

Let $\bar{T}$ be the truths of the item $d$, that is, $\bar{T}={\cal O}$ (when
computing $p(\Psi|{\cal O},\perp)$) or $\bar{T}={\cal O}\cup\\{v\\}$ (when
computing $p(\Psi|{\cal O},v)$). Accordingly, we can partition $\Psi(s)$,
values provided by $s$ on $d$, into four categories: consistent values,
inconsistent values, extra values and missing values. We denote respectively
the size of each category as $N_{c},N_{w},N_{e},N_{m}$, and the probability
that a value falls into each category as $P_{c},P_{w},P_{e},P_{m}$. Then
$p(\Psi(s)|{\cal O},v)$ is given by:

$p(\Psi(s)|{\cal O},v)=P_{c}^{N_{c}}\cdot P_{w}^{N_{w}}\cdot
P_{e}^{N_{e}}\cdot P_{m}^{N_{m}}.$ (6)

When deriving $p(\Psi(s)|{\cal O},{\perp})$, the only difference is that we
will award a source $s$ if it does not provide any extra value ; otherwise, we
re-use Eq. (6). The probability of not providing extra values is $P_{\neg
e}=1-Q(s)$, and recall that ${\cal O}$ is the (estimated) set of truths for
the data item. Thus we have:

$p(\Psi(s)|{\cal O},{\perp})=\begin{cases}P_{c}^{N_{c}}\cdot
P_{w}^{N_{w}}\cdot P_{e}^{N_{e}}\cdot P_{m}^{N_{m}}&|\Psi(s)|>|{\cal O}|;\\\
P_{c}^{N_{c}}\cdot P_{w}^{N_{w}}\cdot P_{e}^{N_{e}}\cdot P_{m}^{N_{m}}\cdot
P_{\neg e}&|\Psi(s)|\leq|{\cal O}|.\end{cases}$ (7)

We next define each category and describe how we compute their sizes and
probabilities. Following [1], we assume that there are $n$ false values in the
domain of $d$ and they are uniformly distributed (note that the false values
may not appear in $\cal V$).

  * •

Consistent value: A consistent value is a value in $\bar{T}\cap\Psi(s)$; thus,
$N_{c}=|\bar{T}\cap\Psi(s)|$. To provide a consistent value, $s$ needs to
correctly predict that there exists a slot for truth, and fills the slot with
a true value, so $P_{c}=R(s)\cdot A(s)$.

  * •

Inconsistent value: An inconsistent value is a value that is provided for a
truth slot, but differs from any true value. At most we have $|\bar{T}|$
values provided for truth slots; except the consistent values, others are
inconsistent. Thus $N_{w}=\min(|\bar{T}|,|\Psi(s)|)-N_{c}$. When $s$ provides
an inconsistent value, it correctly predicts the existence of a truth slot,
but fills in a particular false value, so $P_{w}=R(s){\cdot}{1-A(s)\over n}$.

  * •

Extra value: If $s$ provides more than $|\bar{T}|$ values, the rest of the
values are extra values; thus, $N_{e}=\max(|\Psi(s)|-|\bar{T}|,0)$. When $s$
provides an extra value, it incorrectly predicts a non-existing slot, and
fills in a particular (false) value, so $P_{e}={Q(s)\over n}$.

  * •

Missing value: Alternatively when $\Psi(s)$ contains fewer values than
$\bar{T}$, $s$ misses some truth slots (i.e., $s$ thinks they do not exist).
We have $N_{m}=\max(|\bar{T}|-|\Psi(s)|,0)$ and $P_{m}=1-R(s)$.

###### Example 3.2

Consider the data item $d_{1}$ and we now compute
$p(\Psi(s_{2})|o_{1},o_{2})$, the probability of observing the values in
$\Psi(s_{2})$ if $o_{2}$ is the next truth after $o_{1}$ has been selected. We
have ${\cal O}=o_{1}$, $\Psi(s_{2})=\\{o_{2},o_{3}\\}$ and
$\bar{T}=\\{o_{1},o_{2}\\}$. So $\Psi(s_{2})$ contains one consistent value,
and one inconsistent value; there is no extra value or missing value. In other
words, we have $N_{c}=N_{w}=1$ and $N_{e}=N_{m}=0$.

Supposing $n=10$ and $A(s_{2})=0.6,R(s_{2})=0.9,Q(s_{2})=0.1$, we have
$P_{c}=0.9\cdot 0.6=0.54$, $P_{w}=0.9\cdot\frac{1-0.6}{10}=0.036$,
$P_{e}=\frac{0.1}{10}=0.01$, $P_{m}=0.1$.

Then according to Eq. (6) we compute:
$p(\Psi(s_{2})|o_{1},o_{2})=0.54^{1}\cdot 0.036^{1}\cdot 0.01^{0}\cdot
0.1^{0}=0.019$.

We repeat the above process for the other sources and obtain:
$p(\Psi(s_{1})|o_{1},o_{2})=0.292$, $p(\Psi(s_{3})|o_{1},o_{2})=0.019$.

With the source-independence assumption, we have:
$p(\Psi|o_{1},o_{2})=0.019\cdot 0.292\cdot 0.019=1.05\times 10^{-4}$.

####  3.2.3 A priori probabilities

We then compute the probabilities $p({\perp}|{\cal O})$ and $p(v|{\cal O})$ in
Eq. (3). Intuitively, the chance of $\perp$ increases when more truths are
found. Let $\beta_{i}$ be the a priori probability of $\perp$ when we are
looking for the $i$-th truth (i.e., $|{\cal O}|=i-1$). So there are $|{\cal
V}|-i+1$ unselected values in $\cal V$; assuming they have the same a priori
probability, the a priori probability $p(v|{\cal O})$ of each value $v$ would
be:

$p(v|{\cal O})=\frac{1-\beta_{i}}{|{\cal V}|-i+1}.$ (8)

We can derive $\beta_{i}$ from the distribution of the number of truths for a
data item. For example, among people who have children, if $30\%$ of them have
1 child, $40\%$ have 2 children, and so on, then $\beta_{2}=0.3$ (with
probability $30\%$ there is not a second truth), and $\beta_{3}=0.7$ (with
probability $30\%$+$40\%$ there is not a third truth).

####  3.2.4 Summary

By putting the derived inverse probabilities and a priori probabilities into
Eq. (3), we are able to obtain $p(v|{\cal O},\Psi)$, and this completes the
computation of Eq. (1). As the following proposition shows, Hybrid computes
higher probabilities for values provided by more accurate sources; it finds
more truths when high-precision sources provide more values; and it finds
fewer truths when high-recall sources provide fewer values. These all conform
to our intuition.

###### Proposition 3.3

Consider a value $v$ and a source $s\in{{\cal S}}$ where $v\in\Psi(s)$; we fix
all sources in ${{\cal S}}$ except $s$.

  * •

If $A(s)>\frac{1}{u+1}$, $p(v|\Psi)$ increases when $A(s)$ increases.

  * •

If $Q(s)<\frac{R(s)-R(s)A(s)}{1-R(s)A(s)}$, $p({\perp}|\Psi)$ decreases when
$s$ provides more values.

  * •

If $R(s)>\frac{Q(s)}{1-A(s)+A(s)Q(s)}$, $p({\perp}|\Psi)$ increases when $s$
provides fewer values. $\Box$

###### Example 3.4

Continuing with Example 3.2, we proceed to compute $p(o_{2}|o_{1},\Psi)$ using
Eq. (3). This requires the inverse probability $p(\Psi|o_{1},v)$ and the a
priori probability $p(v|o_{1})$ for every remaining value in ${\cal
V}\setminus{\cal O}=\\{o_{2},o_{3},o_{4}\\}$ as well as $\perp$.

We have obtained the inverse probability $p(\Psi|o_{1},o_{2})$ in Example 3.2;
we now repeat the process on $o_{3}$, $o_{4}$ and $\perp$ to compute:
$p(\Psi|o_{1},o_{3})=p(\Psi|o_{1},o_{4})=6.8\times 10^{-6}$;
$p(\Psi|o_{1},\perp)=1.05\times 10^{-8}$.
Then assuming $\beta_{1}=p({\perp}|o_{1})=0.3$, from Eq. (8) we have
$p(o_{2}|o_{1})=p(o_{3}|o_{1})=p(o_{4}|o_{1})=\frac{1-\beta_{1}}{|{\cal
V}|-1+1}=0.175$.
We can thus obtain $p(o_{2}|o_{1},\Psi)$ via Eq. (3):
$p(o_{2}|o_{1},\Psi)=\frac{p(\Psi|o_{1},o_{2})p(o_{2}|o_{1})}{\sum_{v\in\\{o_{2},o_{3},o_{4}\\}}p(\Psi|o_{1},v)p(v|o_{1})+p(\Psi|o_{1},\perp)p({\perp}|o_{1})}\\\
=0.88$.

Table 2 shows the probabilities obtained by enumerating all possible worlds
${\cal O}$ for each value $v$. We can see that Hybrid gives very high
probabilities (0.92) for the two true values (helmet and stick) and meanwhile
very low probabilities for the false ones.

###  3.3 Evaluating Source Quality

The previous subsection explains how to compute value probabilities based on
the quality of sources. We do not always have such prior knowledge on source
qualities, and in this case we start by assuming each source has the same
quality, and then iteratively compute value probabilities and source qualities
until convergence. This subsection describes how to update source quality
based on the estimated truths of a set of data items.

For each source $s$, we compute $P(s),R(s)$ and $A(s)$ as defined, except that
we adopt the probabilistic decisions made on the truthfulness of values. We
emphasize again that the computation of precision and recall do not consider
the truthfulness of the values, but only the cardinality of the provided
values (i.e., how many truth slots $s$ thinks there are).

  * •

The precision of $s$ is the average of its precision on each data item $s$
provides values for. Let $\Psi_{d}(s)$ be the set of values provided by $s$ on
$d$ and ${\cal V}_{d}$ be the domain of $d$. Then $\sum_{v{\in}{\cal
V}_{d}}p(v)$ is the (probabilistic) number of truths for $d$, and we have

$P(s)=\operatorname*{Avg}_{d}~{}\min(\frac{\sum_{v{\in}{\cal
V}_{d}}p(v|\Psi)}{|\Psi_{d}(s)|},1).$ (9)

  * •

Similarly, the recall of $s$ is the average of its recall on each data item.

$R(s)=\operatorname*{Avg}_{d}~{}\min(\frac{|\Psi_{d}(s)|}{\sum_{v{\in}{\cal
V}_{d}}p(v|\Psi)},1).$ (10)

  * •

The accuracy of $s$ can be estimated as the average probability of its values,
divided by its precision, so it accounts for values provided for “real” truth
slots only.

$A(s)={\operatorname*{Avg}_{d,v\in\Psi_{d}(s)}p(v|\Psi)\over P(s)}.$ (11)

##  4 Approximation for HYBRID

Computing value probabilities by enumerating all possible worlds takes
exponential time. We conjecture that the value probability computation in
Hybrid is #P-complete; the proof of the conjecture remains an open problem.
This section describes an approximation for probabilities under Hybrid. We
start with simplifying the computation of $p(v|{\cal O},\Psi)$ in Eq. (3), and
then present our approximation algorithm.

###  4.1 Simplification of $p(v|{\cal O},\Psi)$

We can simplify the computations in Section 3.2 to a much simpler form. We
start from Eq. (6) and Eq. (7).

Given a particular source $s$, suppose $N_{c}=c$, $N_{w}=w$, $N_{e}=e$ and
$N_{m}=m$ when computing $p(\Psi(s)|{\cal O},{\perp})$ with Eq. (7). Then we
have four cases when deciding the $N_{c}$, $N_{w}$, $N_{e}$ and $N_{m}$ for
$p(\Psi(s)|{\cal O},v)$ in Eq. (6), depending on whether $|\Psi(s)|>|{\cal
O}|$ and whether $v\in\Psi(s)$; we illustrate them in Table 4.

Table 4: Numbers used in Eq. (6) when $N_{c}=c,N_{w}=w,N_{e}=e$ and $N_{m}=m$ in Eq. (7). The case that $s$ belongs to | $N_{c}$ | $N_{w}$ | $N_{e}$ | $N_{m}$
---|---|---|---|---
case 1: $|\Psi(s)|>|{\cal O}|$ and $v\in\Psi(s)$ | $c+1$ | $w$ | $e-1$ | $m$
case 2: $|\Psi(s)|>|{\cal O}|$ and $v\notin\Psi(s)$ | $c$ | $w+1$ | $e-1$ | $m$
case 3: $|\Psi(s)|\leq|{\cal O}|$ and $v\in\Psi(s)$ | $c+1$ | $w-1$ | $e$ | $m+1$
case 4: $|\Psi(s)|\leq|{\cal O}|$ and $v\notin\Psi(s)$ | $c$ | $w$ | $e$ | $m+1$

Let ${\cal S}_{1}$, ${\cal S}_{2}$, ${\cal S}_{3}$, ${\cal S}_{4}$ denote the
set of sources in ${\cal S}$ that fall into each of the above cases
respectively. We can then write $p(\Psi|{\cal O},v)$ and $p(\Psi|{\cal
O},{\perp})$ into the following formats:

$\displaystyle p(\Psi|{\cal O},v)$ $\displaystyle=\prod_{\bar{\cal
S}_{1}\cup\bar{\cal S}_{3}}(P_{c})^{c+1}\cdot\prod_{\bar{\cal
S}_{2}\cup\bar{\cal S}_{4}}(P_{c})^{c}\cdot$ (12)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\prod_{\bar{\cal
S}_{1}}(P_{w})^{w}\cdot\prod_{\bar{\cal
S}_{2}}(P_{w})^{w+1}\cdot\prod_{\bar{\cal S}_{3}}(P_{w})^{w-1}\prod_{\bar{\cal
S}_{4}}(P_{w})^{w}\cdot$ $\displaystyle~{}~{}~{}~{}\prod_{\bar{\cal
S}_{1}\cup\bar{\cal S}_{2}}(P_{e})^{e-1}(P_{m})^{m}\cdot\prod_{\bar{\cal
S}_{3}\cup\bar{\cal S}_{4}}(P_{e})^{e}(P_{m})^{m+1};$ $\displaystyle
p(\Psi|{\cal O},{\perp})$ $\displaystyle=\prod_{\bar{\cal
S}}(P_{c})^{c}(P_{w})^{w}(P_{e})^{e}(P_{m})^{m}\cdot\prod_{\bar{\cal
S}_{3}\cup\bar{\cal S}_{4}}P_{\neg e}.$ (13)

Next let

$\displaystyle C$ $\displaystyle=\prod\limits_{\bar{\cal
S}}(P_{c})^{c}\cdot\prod\limits_{\bar{\cal S}_{1}\cup\bar{\cal
S}_{2}}(P_{w})^{w+1}(P_{e})^{e-1}(P_{m})^{m}\cdot$
$\displaystyle~{}~{}\prod\limits_{\bar{\cal S}_{3}\cup\bar{\cal
S}_{4}}(P_{w})^{w}(P_{e})^{e}(P_{m})^{m+1};$

we can simplify Eq. (12) and Eq. (13) as follows:

$\displaystyle p(\Psi|{\cal O},v)=C\cdot\prod_{\bar{\cal S}_{1}\cup\bar{\cal
S}_{3}}\frac{P_{c}}{P_{w}};$ (14) $\displaystyle p(\Psi|{\cal
O},{\perp})=C\cdot\prod_{\bar{\cal S}_{1}\cup\bar{\cal
S}_{2}}\frac{P_{e}}{P_{w}}\cdot\prod_{\bar{\cal S}_{3}\cup\bar{\cal
S}_{4}}\frac{P_{\neg e}}{P_{m}}.$ (15)

Next, we define the vote count of a value $v$ based on the accuracy of its
providers:

$\displaystyle L(v)$ $\displaystyle=\prod_{\bar{\cal S}_{1}\cup\bar{\cal
S}_{3}}\frac{P_{c}}{P_{w}}=\prod_{\bar{\cal S}_{1}\cup\bar{\cal
S}_{3}}\frac{R(s)A(s)}{R(s)\frac{1-A(s)}{n}}$
$\displaystyle=\prod_{S\in{\bar{\cal S}}_{v}}\frac{nA(s)}{1-A(s)};$ (16)

The vote count of $\perp$ at the $i$-th step (i.e., $i-1$ truths have been
selected) combines the a priori probability and the votes from all sources:

$\displaystyle L_{|{\cal O}|+1}(\perp)$ $\displaystyle=\frac{p({\perp}|{\cal
O})}{p(v|{\cal O})}\cdot\prod_{\bar{\cal S}_{1}\cup\bar{\cal
S}_{2}}\frac{P_{e}}{P_{w}}\cdot\prod_{\bar{\cal S}_{3}\cup\bar{\cal
S}_{4}}\frac{P_{\neg e}}{P_{m}}$ $\displaystyle={\beta_{i}(|{\cal
V}|{-}i{+}1)\over 1-\beta_{i}}\cdot\prod_{|\Psi(s)|>|{\cal O}|}{Q(s)\over
R(s)(1-A(s))}\cdot$ (17) $\displaystyle~{}~{}~{}~{}\prod_{|\Psi(s)|\leq|{\cal
O}|}{1-Q(s)\over 1-R(s)}.$

We can then transform Eq. (3) into the following format:

$p(v|{\cal O},\Psi)={L(v)\over\sum_{v^{\prime}\in{\cal V}\setminus{\cal
O}}L(v^{\prime})+L_{|{\cal O}|+1}(\perp)}.$ (18)

###  4.2 Approximation

Our approximation leverages three observations. First, equivalent to computing
$p(v|\Psi)$ conditioning on all possible worlds, we compute
$p(v|\Psi)=\sum_{i}p_{i}(v|\Psi)$, where $p_{i}(v|\Psi)$ denotes the
probability of $v$ being the $i$-th truth, computed by considering possible
worlds ${\cal O}$ with $i-1$ values. Second, although there are multiple
possible worlds with size $i-1$, the nature of Bayesian analysis determines
that one of them would have a much higher probability than the others, so we
can use it for approximation. Third, once the probability of $\perp$ is above
that of the $i$-th truth, it quickly increases to $1$ in the following steps.
Therefore if we terminate at the $i$-th step, we would not lose much. Recall
that the confidence of a value $v$ does not change with $i$, but only that of
$\perp$ changes, thus we can easily decide the number of steps we need before
termination.

Algorithm 1 gives the details of the approximation.

  * •

Without losing generality, let $L(v_{1}),L(v_{2}),\dots$ be a sorted list in
decreasing order, that is, $L(v_{i-1})\geq L(v_{i})$ for $\forall i>1$ (Lines
1-1). Let $k$ be an integer where $L(v_{k-1})\geq L_{k-1}(\perp)$ and
$L(v_{k})<L_{k}(\perp)$; we thus terminate after $k$ steps, and the first
$k-1$ values are considered as truths (Lines 1-1).

  * •

We first initialize $p(v|\Psi)$ to $0$ for each $v\in{\cal V}$. Then at each
step $i$, we update $p(v|\Psi)$ by adding the probability $p_{i}(v|\Psi)$ for
$v$ to be the $i$-th truth (Line 1). To compute $p_{i}(v|\Psi)$, we consider
possible worlds where $v$ is not present yet (their probabilities sum up to
$1-p(v|\Psi)$). Assuming $v$ has the same conditional probability in all these
possible worlds, denoted by $p(v|\Gamma_{i},\Psi)$, we have:

$p_{i}(v|\Psi)=(1-p(v|\Psi))\cdot p(v|\Gamma_{i},\Psi).$ (19)

  * •

We obtain $p(v|\Gamma_{i},\Psi)$ from the possible world with the largest
probability, which must have selected the $i{-}1$ values with the highest
confidence as truths; that is, $\Gamma_{i}=v_{1}v_{2}\dots v_{i-1}$. We thus
compute $p(v|\Gamma_{i},\Psi)$ by normalizing the subsequence of confidence
starting with $L(v_{i})$ (Line 1). Note that for any possible world ${\cal O}$
with length $i-1$, we have $p(v|{\cal O},\Psi)\leq p(v|\Gamma_{i},\Psi)$.

input : Observations $\Psi$ containing a set $\cal V$ of values provided by a
set ${\cal S}$ of sources on data item $d$; prior probability $\beta$

output : Probability $p(v|\Psi)$ for each $v\in{\cal V}$

1 foreach $v\in{\cal V}$ do

2 $p(v|\Psi)\leftarrow 0$;

3 Compute $L(v)$ using Eq. (LABEL:multi:eq:confv);

4

5Let $L(v_{1}),L(v_{2}),\dots$ be a sorted list in decreasing order;

6

7foreach $i\in[1,|{\cal V}|]$ do

8 Compute $L_{i}(\perp)$ using Eq. (LABEL:multi:eq:confempty);

9 foreach $v\in{\cal V}$ do

10 $p(v|\Gamma_{i},\Psi)=\min(\frac{L(v)}{\sum_{j=i}^{j=|\cal
V|}L(v_{j})+L_{i}(\perp)},1)$;

11 $p(v|\Psi)\leftarrow p(v|\Psi)+(1-p(v|\Psi))\cdot p(v|\Gamma_{i},\Psi)$;

12

13 if $L_{i}(\perp)>L(v_{i})$ then

14 break;

15

16

Algorithm 1 Approximation for Hybrid

###### Example 4.1

Consider again computing $p(o_{2}|\Psi)$. The sorted list of the value
confidences is $\\{225,225,15,15\\}$, given by $o_{1}$, $o_{2}$, $o_{3}$ and
$o_{4}$; the confidences of $\perp$ in different steps are
$\\{0.1,0.24,18033,\\\ 18033\\}$. We thus terminate after the third step (when
$i=3$).

When $i{=}1$, we compute $p_{1}(o_{2}|\Psi)=0.47$.

When $i{=}2$, we compute $p(o_{2}|\Gamma_{2},\Psi)=p(o_{2}|o_{1},\Psi)=0.88$,
thus $p_{2}(o_{2}|\Psi)=(1-0.47)\times 0.88=0.47$.

When $i{=}3$, we compute
$p(o_{2}|\Gamma_{3},\Psi)=\frac{225}{15+15+18033}=0.01$, thus
$p_{3}(o_{2}|\Psi)=(1-0.47-0.47){\times}0.01=0.0006$.

The final probability for $o_{2}$ is
$p(o_{2}|\Psi)=p_{1}(o_{2}|\Psi)+p_{2}(o_{2}|\Psi)+p_{3}(o_{2}|\Psi)=0.9406$,
very close to the probability $0.92$ obtained by Hybrid.

The next theorem shows that Algorithm 1 approximates the value probabilities
both efficiently and effectively.

###### Theorem 4.2

Let $d$ be a data item and $n$ be the number of values provided for $d$.

  * •

Algorithm 1 estimates the probability of each provided value in time
$O(n^{2})$.

  * •

For each value $v$ on $d$, we have $|p(v)-\hat{p}(v)|<\frac{1}{6}$, where
$\hat{p}(v)$ is the exact probability computed by Hybrid, and $p(v)$ is the
probability obtained by Algorithm 1. $\Box$

######  Proof 4.1.

See Appendix A.

##  5 Experimental Study

We now present experimental results to evaluate the proposed approach. Section
5.1 describes experimental settings. Then Section 5.2 gives a comprehensive
comparison of various fusion models on a widely used real dataset as well as
synthetic data, showing that Hybrid outperforms others in general and is the
most robust.

###  5.1 Experimental Settings

Methods to compare. We compared the following fusion algorithms.

  * •

Accu [1], the single-truth model reviewed in Section 1. For each data item, it
considers the value with the highest predicted probability as the truth.

  * •

PrecRec [7], the multi-truth model reviewed in Section 1. It considers a value
correct if its predicted probability is above 0.5.

  * •

LTM [9], a multi-truth model using directed graphical model. It also considers
a value correct if its predicated probability is above 0.5.

  * •

TwoStep, the baseline method described in Section 3. It first decides the
number of truths $k$, and then returns the $k$ values with top probabilities
according to Accu.

  * •

Hybrid, Algorithm 1 described in Section 4. It considers the values obtained
before the termination step as the truths.

Implementations. Whenever applicable, we set $n=10,\alpha=0.25$, and consider
only “good” sources (e.g., sources on which the conditions in Proposition 3.3
hold). We initialize the source quality metrics as $A=0.8,R=0.8,Q=0.2$, and
then iteratively compute value probabilities and source qualities for up to 5
iterations. We implemented all methods in Java on a MapReduce-based framework.

Metrics. We report precision and recall for each method. Precision measures
among all observations predicted as correct, the percentage that are true.
Recall measures among all true observations, the percentage that are predicted
as correct. F-measure is computed as ${2\cdot prec\cdot rec\over prec+rec}$.
(Note that they are different from precision and recall of individual sources
as defined in Section 3.2).

###  5.2 Experiment Results

####  5.2.1 Results on Book data

We first use the Book data from [8], which has been widely used for knowledge-
fusion experiments. As shown in Table 5, it contains 6,139 book-author triples
on 1,263 books from 876 retailers. The gold standard consists of authors for
100 randomly sampled books, where the authors were manually identified from
book covers. According to the gold standard, 62% of the provided authors are
correct, and 98% of the true values are provided by some source. There are 57%
of the books that have multiple authors.

Table 5: Statics of the Book data. #entities | #triples | #sources | precision | recall | %multi-truth
---|---|---|---|---|---
1,263 | 6,139 | 876 | 0.62 | 0.98 | 57%

In addition to the five fusion methods we listed before, we also compared with
Accu_list, which applies Accu but considers the full list of authors as a
whole [1, 8].

Table 6: Results on Book data. Hybrid obtains the highest recall and F-measure. | Precision | Recall | F1
---|---|---|---
Accu | 0.990 | 0.532 | 0.692
Accu_list | 0.974 | 0.801 | 0.879
LTM | 0.911 | 0.973 | 0.941
PrecRec | 0.965 | 0.931 | 0.947
Hybrid | 0.941 | 0.973 | 0.957

Table 6 shows the results, and we can see that Hybrid obtains a higher
F-measure than existing single-truth and multi-truth models. By considering
both conflicts between values and the possibility of having multiple truths,
it is able to identify more true values without sacrificing much of precision.
Not surprisingly, Accu has the highest precision but the lowest recall as it
only finds one author for a book. LTM has a lower precision as it lacks a
global view of the values provided for the same data item. Instead, PrecRec
has a lower recall but a higher precision: in this dataset many sources only
provide the first author of a book and this explains the low recall; the high
precision is because the sources provide few wrong values. TwoStep separates
the decisions of how many truths there are and what they are, so may return
authors that do not have strong support, leading to a low precision.

####  5.2.2 Results on Synthetic Data

To better understand the performance of different approaches in various
situations, we compare them on synthetic data where we vary the number of
truths and the quality of sources.

We generated 10 data sources providing values on 100 data items, where wrong
values were randomly selected from a domain of 100 values. We varied the
following parameters when generating the data.

  * •

Number of truths for each data item: ranges from 1 to 10, and by default
follows a Gaussian distribution with mean=6 and std=1.

  * •

Source accuracy: ranges from 0.2 to 1, and 0.7 by default.

  * •

Source recall: ranges from 0.2 to 1, and 0.7 by default.

  * •

Extra ratio: equals to $\frac{N_{e}}{N_{c}+N_{w}}$ (see Eq. (6)); ranges from
0.2 to 1, and 0.2 by default.

All experiments were repeated 100 times and we report the average.

Figure 1: Varying the number of truths on synthetic data. Hybrid improves over
other models when the number of truths is large.

Figure 2: Varying source accuracy. Hybrid obtains a significantly higher
precision when source accuracy is low.

Figure 3: Varying source recall. Hybrid gives the highest precision and F1
when the sources have medium recall.

Figure 4: Varying extra ratio. Hybrid is the most robust and outperforms the
others.

Figure 1 shows the results when we vary the number of truths in data
generation. Hybrid can fairly well “guess” the number of truths and
consistently outperforms the others. As the number of truths increases, the
precision of Hybrid remains high, while the precision of PrecRec drops. This
is because the extra ratio is fixed; when there are more truths, there will be
more wrong values and PrecRec is more sensitive to noise. Not surprisingly,
Accu always has the highest precision. LTM and TwoStep have low precision: the
former lacks a global view of values for the same data item, while the latter
may return false values with weak support.

Figures 2-4 plot the results of different methods when we vary source
qualities. As expected, as the quality of the sources drops, the quality of
the fusion results drops as well. However, we observe that Hybrid has the
highest F-measure in general and it is the most robust. It usually gives
significantly higher precision than PrecRec since it considers the conflicts
between provided values as evidence to eliminate wrong values. While most
methods perform better when the source quality increases, PrecRec obtains the
worst results when the source quality is medium (0.4-0.6). This is because,
when the sources have similar probability of providing a true value and
providing a false value, PrecRec is unable to distinguish them.

##  6 Related Work

Data fusion [2, 4] refers to the problem of identifying the truths from
different values provided by various sources. We have provided a high-level
review of different approaches in Section 1 and presented a comprehensive
experimental study in Section 5.

A model called TEM [10] considers in addition whether the truth for a date
item exists at all (i.e., date-of-death does not exist for an alive person).
It is mainly designed for single-truth scenario. The method in [3] considers
the case where most sources provide only a few triples, thus source quality
cannot be reliably estimated. The Hybrid model can be enhanced by these
approaches.

##  7 Conclusion

In this paper we present an approach to find true values for an entity from
information provided by different sources. It jointly makes two decisions on
an entity: how many truths there are, and what they are. In this way, it
allows the existence of multiple truths, while considering the conflicts
between different values as important evidence for ruling out wrong values.
Extensive experiments on both real-world and synthetic data show that the
proposed outperforms the state-of-the-art techniques, and it is able to obtain
a high precision without sacrificing the recall much.

## References

  * [1] X. L. Dong, L. Berti-Equille, and D. Srivastava.  Integrating conflicting data: the role of source dependence.  PVLDB, 2009.
  * [2] M. Gupta and J. Han.  Heterogeneous network-based trust analysis: a survey.  ACM SIGKDD Explorations Newsletter, 2011.
  * [3] Q. Li, Y. Li, J. Gao, L. Su, B. Zhao, M. Demirbas, W. Fan, and J. Han.  A confidence-aware approach for truth discovery on long-tail data.  PVLDB, 2014.
  * [4] X. Li, X. L. Dong, K. Lyons, W. Meng, , and D. Srivastava.  Truth finding on the deep web: Is the problem solved?  PVLDB, 2013.
  * [5] Y. Li, J. Gao, C. Meng, Q. Li, L. Su, B. Zhao, W. Fan, and J. Han.  A survey on truth discovery.  arXiv preprint arXiv:1505.02463, 2015.
  * [6] X. Liu, X. L. Dong, B. C. Ooi, and D. Srivastava.  Online data fusion.  PVLDB, 2011.
  * [7] R. Pochampally, A. Das Sarma, X. L. Dong, A. Meliou, and D. Srivastava.  Fusing data with correlations.  In SIGMOD, 2014.
  * [8] X. Yin, J. Han, and P. S. Yu.  Truth discovery with multiple conflicting information providers on the web.  In KDD, 2007.
  * [9] B. Zhao, B. I. P. Rubinstein, J. Gemmell, and J. Han.  A bayesian approach to discovering truth from conflicting sources for data integration.  PVLDB, 2012.
  * [10] S. Zhi, B. Zhao, W. Tong, J. Gao, D. Yu, H. Ji, and J. Han.  Modeling truth existence in truth discovery.  In KDD, 2015.

##  Appendix A Proof of Theorem 4.2

Theorem 4.2. Let $d$ be a data item and $n$ be the number of values provided
for $d$.

  * •

Algorithm 1 estimates the probability of each provided value in time
$O(n^{2})$.

  * •

For each value $v$ on $d$, we have $|p(v)-\hat{p}(v)|<\frac{1}{6}$, where
$\hat{p}(v)$ is the exact probability computed by Hybrid, and $p(v)$ is the
probability obtained by Algorithm 1. $\Box$

######  Proof A.1.

We first consider the time complexity of Algorithm 1. Lines 1-1 have a
complexity of $O(n\log n)$. The loops in Lines 1 and 1 take $O(n^{2})$ time.
Therefore the overall complexity is $O(n^{2})$.

Next we prove the approximation bound of Algorithm 1. In this proof, we use a
tree structure to illustrate the computations made by the full Hybrid model;
see Figure 5 as an example. The root of the tree represents having not
selected any value. A path from the root to a node $v$ represents a possible
way of selecting $v$; for instance, the path $v_{1}$-$v_{2}$-$v_{3}$
corresponds to the case where we select $v_{3}$ after selecting $v_{1}$ and
$v_{2}$ sequentially (i.e., ${\cal O}=v_{1}v_{2}$). The children of a node
represent candidates for the next truth. The number under each node $v$ is the
conditional probability $p(v|{\cal O},\Psi)$. By multiplying the numbers along
a path, we obtain the probability of the path. The overall $p(v|\Psi)$ is thus
the sum of the probabilities of all paths ending with $v$.

Figure 5: A tree structure to illustrate the full Hybrid model.

Algorithm 1 differs from the full Hybrid model in two places: (1) it
terminates early when $L_{i}(\perp)>L(v_{i})$ without enumerating all possible
worlds (Line 1), and (2) it assumes that $v$ has the same conditional
probability $p(v|\varGamma_{i},\Psi)$ under all possible worlds with size
$i-1$ (Line 1). The first one will make the approximated probability $p(v)$
lower than the exact probability $\hat{p}(v)$ under the full model, while the
second one will lead to a higher $p(v)$. We next prove by constructing the
worst case for each of them.

Case I: Algorithm 1 terminates early such that $p(v)<\hat{p}(v)$.
In this case the approximation error is due to the early termination:
Algorithm 1 terminates at step $i{-}1$ without increasing $p(v)$ by $p_{j}(v)$
($j\geq i$) in future steps. It is easy to check that Algorithm 1 outputs the
same probabilities as the full model if the number of provided values is less
than 3. So we require at least three values in the domain. The earliest
possible termination is at step 2 (i.e., $i=3$).

Next we construct a case with three values and Algorithm 1 terminates at step
2, such that the approximation error is reflected in one step (which is
$p_{3}(v)$). By definition we have $L(v_{3})\leq L(v_{2})$ and
$L_{3}(\perp)\geq L_{2}({\perp})$; to terminate at step 2, we need
$L(v_{2})<L_{2}({\perp})$. It is easy to see that among the tree values,
$v_{3}$ has the largest probability at step 3. To maximize the approximation
error cased by $p_{3}(v_{3})$, we need $L(v_{3})$ to be maximized and
$L_{2}({\perp})$ as well as $L_{3}({\perp})$ to be minimized.

Suppose $L(v_{2})=a$, we then have $L(v_{3})=L(v_{2})=a$; let $\gamma$ be a
real number where $\gamma\geq 1$, we have $L(v_{1})=\gamma{\cdot}a$. Further,
let $L_{2}(\perp)=L_{3}(\perp)=a+\epsilon$ where $\epsilon$ is a very small
constant. As usual, we have $L_{1}(\perp)=0$. With the above setting, we
compute all conditional probabilities following Section 3.2 and illustrate in
Figure 5 (we omit $\epsilon$).

Next we compute the overall probability for $v_{3}$ using the full Hybrid
model and Algorithm 1 respectively.

For the full Hybrid model, we find all paths ending with $v_{3}$ at each level
of the tree:

Level 1: $\hat{p}_{1}(v_{3})=\frac{1}{\gamma+2}$;

Level 2:
$\hat{p}_{2}(v_{3})=\frac{\gamma}{\gamma+2}\cdot\frac{1}{3}+\frac{1}{\gamma+2}\cdot\frac{1}{\gamma+2}$;

Level 3:
$\hat{p}_{3}(v_{3})=\frac{\gamma}{\gamma+2}\cdot\frac{1}{3}\cdot\frac{1}{2}+\frac{1}{\gamma+2}\cdot\frac{\gamma}{\gamma+2}\cdot\frac{1}{2}$;

Finally,
$\hat{p}(v_{3})=\hat{p}_{1}(v_{3})+\hat{p}_{2}(v_{3})+\hat{p}_{3}(v_{3})=\frac{1}{\gamma+2}+\frac{\gamma+1}{2(\gamma+2)}$.

For Algorithm 1, it terminates after 2 steps:

When $i=1$: $p_{1}(v_{3})=\frac{1}{\gamma+2}$;

When $i=2$:
$p_{2}(v_{3})=(1-\frac{1}{\gamma+2})\times\frac{1}{3}=\frac{\gamma+1}{3(\gamma+2)}$;

Finally,
$p(v_{3})=p_{1}(v_{3})+p_{2}(v_{3})=\frac{1}{\gamma+2}+\frac{\gamma+1}{3(\gamma+2)}$.

Therefore
$\hat{p}(v_{3})-p(v_{3})=\frac{1}{6}\cdot\frac{\gamma+1}{\gamma+2}<\frac{1}{6}$.

Case II: We assume the same conditional probability under all possible worlds
such that $p(v)>\hat{p}(v)$.

Recall that Eq. (19) assumes that in each step $i$, $v$ has the same
conditional probability $p(v|\Gamma_{i},\Psi)$ under all possible worlds where
$v$ is not present yet. This $p(v|\Gamma_{i},\Psi)$ is an upper bound of the
real conditional probability; we obtain the largest difference between
$p(v|\Gamma_{i},\Psi)$ and the real conditional probability when the possible
worlds end with $\perp$ (the real probability is 0). We thus construct a case
where $p_{2}(\perp)p(v_{3}|\Gamma_{3},\Psi)$ is maximized, leading to an over-
estimation of $p_{3}(v_{3})$.

Similar to the previous case, we assume $L(v_{1})=\gamma{\cdot}a$ and
$L(v_{2})=a$. In this case we want Algorithm 1 to continue when $i=3$, so that
$p_{3}(v_{3})$ is added to the overall probability of $v_{3}$. Therefore we
require $L_{2}(\perp)\leq L(v_{2})$; to make $p_{2}(\perp)$ larger, we have
$L_{2}(\perp)=L(v_{2})=a$. Given that $L(v_{3})\geq L(v_{2})$, to maximize
$p(v_{3}|\Gamma_{3},\Psi)$, we need $L(v_{3})=L(v_{2})=a$.

With the above setting, the probabilities computed by the full model remain
the same, but Algorithm 1 continues when $i=3$:

$p_{3}(v_{3})=(1-\frac{1}{\gamma+2}-(1-\frac{1}{\gamma+2})\times\frac{1}{3})\times\frac{1}{2}=\frac{\gamma+1}{3(\gamma+2)}$;

$p(v_{3})=p_{1}(v_{3})+p_{2}(v_{3})+p_{3}(v_{3})=\frac{1}{\gamma+2}+\frac{\gamma+1}{3(\gamma+2)}+\frac{\gamma+1}{3(\gamma+2)}=\frac{1}{\gamma+2}+\frac{2(\gamma+1)}{3(\gamma+2)}$.

Therefore
$p(v_{3})-\hat{p}(v_{3})=\frac{1}{6}\cdot\frac{\gamma+1}{\gamma+2}<\frac{1}{6}$.

Combining the two cases, we have $|p(v)-\hat{p}(v)|<\frac{1}{6}$.