# Crowdsourced Truth Discovery in the Presence of Hierarchies for Knowledge
Fusion

Woohwan Jung  Seoul National University<EMAIL_ADDRESS>,  Younghoon Kim
Hanyang University<EMAIL_ADDRESS>and  Kyuseok Shim  Seoul National
University<EMAIL_ADDRESS>
###### Abstract.

Existing works for truth discovery in categorical data usually assume that
claimed values are mutually exclusive and only one among them is correct.
However, many claimed values are not mutually exclusive even for functional
predicates due to their hierarchical structures. Thus, we need to consider the
hierarchical structure to effectively estimate the trustworthiness of the
sources and infer the truths. We propose a probabilistic model to utilize the
hierarchical structures and an inference algorithm to find the truths. In
addition, in the knowledge fusion, the step of automatically extracting
information from unstructured data (e.g., text) generates a lot of false
claims. To take advantages of the human cognitive abilities in understanding
unstructured data, we utilize crowdsourcing to refine the result of the truth
discovery. We propose a task assignment algorithm to maximize the accuracy of
the inferred truths. The performance study with real-life datasets confirms
the effectiveness of our truth inference and task assignment algorithms.

††copyright: rightsretained††doi: ††isbn: 978-3-89318-081-3††conference: 22nd
International Conference on Extending Database Technology (EDBT); March 26-29,
2019; Lisbon, Portugal††journalyear: 2019

##  1\. Introduction

Automatic construction of large-scale knowledge bases is very important for
the communities of database and knowledge management. Knowledge fusion (KF)
(Dong et al., 2014b) is one of the methods used to automatically construct
knowledge bases (a.k.a. knowledge harvesting). It collects the possibly
conflicting values of objects from data sources and applies _truth discovery_
techniques for resolving the conflicts in the collected values. Since the
values are extracted from unstructured or semi-structured data, the collected
information exhibits error-prone behavior. The goal of the _truth discovery_
used in knowledge fusion is to infer the true value of each object from the
noisy observed values retrieved from multiple information sources while
simultaneously estimating the reliabilities of the sources. Two potential
applications of knowledge fusion are web source trustworthiness estimation and
data cleaning (Dong and Srivastava, 2015). By utilizing truth discovery
algorithms, we can evaluate the quality of web sources and find systematic
errors in data curation by analyzing the identified wrong values.

Truth discovery with hierarchies: As pointed out in (Dong et al., 2014a, b; Li
et al., 2016a), the extracted values can be hierarchically structured. In this
case, there may be multiple correct values in the hierarchy for an object even
for functional predicates and we can utilize them to find the most specific
correct value among the candidate values. For example, consider the three
claimed values of ‘NY’, ‘Liberty Island’ and ‘LA’ about the location of the
Statue of Liberty in Table 1. Because Liberty Island is an island in NY, ‘NY’
and ‘Liberty Island’ do not conflict with each other. Thus, we can conclude
that the Statue of Liberty stands on Liberty Island in NY.

We also observed that many sources provide generalized values in the real-
life. Figure 1 shows the graph of the generalized accuracy against the
accuracy of the sources in the real-life datasets _BirthPlaces_ and
_Heritages_ used for experiments in Section 5. The accuracy and the
generalized accuracy of a source are the proportions of the exactly correct
values and hierarchically-correct values among all claimed values,
respectively. If a source claims exactly correct values without
generalization, it is located at the dotted diagonal line in the graph. This
graph shows that many sources in real-life datasets claim with generalized
values and each source has its own tendency of generalization when claiming
values.

Most of the existing methods (Zhao et al., 2012; Pasternack and Roth, 2013;
Zheng et al., 2016; Dong et al., 2009, 2012) simply regard the generalized
values of a correct value as incorrect. Thus, it causes a problem in
estimating the reliabilities of sources. According to (Dong et al., 2014b),
35% of the false negatives in the data fusion task are produced by ignoring
such hierarchical structures. Note that there are many publicly available
hierarchies such as WordNet (University, 2010) and DBpedia (Auer et al.,
2007). Thus, a truth discovery algorithm to incorporate hierarchies is
proposed in (Beretta et al., 2016). However, it does not consider the
different tendencies of generalization and may lead to the degradation of the
accuracy. Another drawback is that it needs a threshold to control the
granularity of the estimated truth.

Table 1. Locations of tourist attractions Object | Source | Claimed value
---|---|---
Statue of Liberty | UNESCO | NY
Statue of Liberty | Wikipedia | Liberty Island
Statue of Liberty | Arrangy | LA
Big Ben | Quora | Manchester
Big Ben | tripadvisor | London
Figure 1. Generalization tendencies of the sources

We propose a novel probabilistic model to capture the different generalization
tendencies shown in Figure 1. Existing probabilistic models (Pasternack and
Roth, 2013; Zheng et al., 2016; Dong et al., 2009, 2012) basically assume two
interpretations of a claimed value (i.e., correct and incorrect). By
introducing three interpretations of a claimed value (i.e., exactly correct,
hierarchically correct, and incorrect), our proposed model represents the
generalization tendency and reliability of the sources.

Crowdsourced truth discovery: It is reported in (Dong et al., 2014b) that upto
96% of the false claims are made by extraction errors rather than by the
sources themselves. Since crowdsourcing is an efficient way to utilize human
intelligence with low cost, it has been successfully applied in various areas
of data integration such as schema matching (Fan et al., 2014), entity
resolution (Wang et al., 2012), graph alignment (Kim et al., 2017a) and truth
discovery (Zheng et al., 2015, 2016). Thus, we utilize crowdsourcing to
improve the accuracy of the truth discovery.

It is essential in practice to minimize the cost of crowdsourcing by assigning
proper tasks to workers. A popular approach for selecting queries in active
learning is _uncertainty sampling_ (Lewis and Gale, 1994; Boim et al., 2012;
Kim et al., 2017b; Zheng et al., 2016). It asks a query to reduce the
uncertainty of the confidences on the candidate values the most. However, it
considers only the uncertainty regardless of the accuracy improvement. QASCA
algorithm (Zheng et al., 2015) asks a query with the highest accuracy
improvement, but measures the improvement without considering the number of
collected claimed values. It can be inaccurate since an additional answer may
be less informative for an object which already has many records and answers.

Assume that there are two candidate values of an object with equal
confidences. If only a few sources provide the claimed values for the object,
an additional answer from a crowd worker will significantly change the
confidence distribution. Meanwhile, if hundreds of sources already provide the
claimed values for the object, the influence of an additional answer is likely
to be very little. Thus, we need to consider the number of collected answers
as well as the current confidence distribution. Based on the observation, we
develop a new method to estimate the increase of accuracy more precisely by
considering the number of collected records and answers. We also present an
incremental EM algorithm to quickly measure the accuracy improvement and
propose a pruning technique to efficiently assign the tasks to workers.

An overview of our truth discovery algorithm: By combining the proposed task
assignment and truth inference algorithms, we develop a novel _crowdsourced
truth discovery algorithm using hierarchies_. As illustrated in Figure 2, our
algorithm consists of two components: _hierarchical truth inference_ and _task
assignment_. The hierarchical truth inference algorithm finds the correct
values from the conflicting values, which are collected from different sources
and crowd workers, using hierarchies. The task assignment algorithm
distributes objects to the workers who are likely to increase the accuracy of
the truth discovery the most. The proposed _crowdsourced truth discovery
algorithm_ repeatedly alternates the truth inference and task assignment until
the budget of crowdsourcing runs out. As discussed in (Li et al., 2016b), some
workers answer slower than others and increase the latency. However, we do not
investigate how to reduce the latency in this work since we can utilize the
techniques proposed in (Haas et al., 2015).

Figure 2. Crowdsourced truth discovery in KF

Our contributions: The contributions of this paper are summarized below.

  * •

We propose a truth inference algorithm utilizing the hierarchical structures
in claimed values. To the best of our knowledge, it is the first work which
considers both the reliabilities and the generalization tendencies of the
sources.

  * •

To assign a task which will most improve the accuracy, we develop an
incremental EM algorithm to estimate the accuracy improvement for a task by
considering the number of claimed values as well as the confidence
distribution. We also devise an efficient task assignment algorithm for
multiple crowd workers based on the quality measure.

  * •

We empirically show that the proposed algorithm outperforms the existing works
with extensive experiments on real-life datasets.

##  2\. Preliminaries

In this section, we provide the definitions and the problem formulation of
_crowdsourced truth discovery in the presence of hierarchy_.

###  2.1. Definitions

For the ease of presentation, we assume that we are interested in a single
attribute of objects although our algorithms can be easily generalized to find
the truths of multiple attributes. Thus, we use ‘the target attribute value of
an object’ and ‘the value of an object’ interchangeably.

A _source_ is a structured or unstructured database which contains the
information on target attribute values for a set of objects. In this paper, a
_source_ is a certain web page or website and a _worker_ represents a human
worker in crowdsourcing platforms. The information of an object provided by a
source or a worker is called a _claimed value_.

###### Definition 2.1.

A _record_ is a data describing the information about an object from a source.
A record on an object $o$ from a source $s$ is represented as a triple
$(o,s,v_{o}^{s})$ where $v_{o}^{s}$ is the claimed value of an object $o$
collected from $s$. Similarly, if a worker $w$ answers that the truth on an
object $o$ is $v_{o}^{w}$, the _answer_ is represented as $(o,w,v_{o}^{w})$.

Let $S_{o}$ be the set of the sources which claimed a value on the object $o$
and $V_{o}$ be the set of candidate values collected from $S_{o}$. Each worker
in $W_{o}$ answers a question about the object $o$ by selecting a value from
$V_{o}$.

In our problem setting, we assume that we have a hierarchy tree $H$ of the
claimed values. If we are interested in an attribute related to locations
(e.g., birthplace), $H$ would be a geographical hierarchy with different
levels of granularity (e.g., continent, country, city, etc.). We also assume
that there is no answer with the value of the root in the hierarchy since it
provides no information at all (e.g., Earth as a birthplace). We summarize the
notations to be used in the paper in Table 2.

###### Example 2.2.

Consider the records in Table 1. Since the source Wikipedia claims that the
location of the Statue of Liberty is Liberty Island, it is represented by
$v_{o}^{s}=$‘Liberty Island’ where $o=$‘Statue of Liberty’ and
$s=$‘Wikipedia’. If a human worker ‘Emma Stone’ answered Big Ben is in London,
it is represented by $v_{o}^{w}=$‘London’ where $o=$‘Big Ben’ and $w=$‘Emma
Stone’.

###  2.2. Problem Definition

Given a set of objects $O$ and a hierarchy tree $H$, we define the two
subproblems of the crowdsourced truth discovery.

###### Definition 2.3 (Hierarchical truth inference problem).

For a set of records $R$ collected from the sources and a set of answers $A$
from the workers, we find the most specific true value ${v_{o}^{*}}$ of each
object $o\in O$ among the candidate values in $V_{o}$ by using the hierarchy
$H$.

###### Definition 2.4 (Task assignment problem).

For each worker $w$ in a set of workers $W$, we select the top-$k$ objects
from $O$ which are likely to increase the overall accuracy of the inferred
truths the most by using the hierarchy $H$.

We present a hierarchical truth inference algorithm in Section 3 and a task
assignment algorithm in Section 4.

Table 2. Notations Symbol | Description
---|---
$s$ | A data source
$w$ | A crowd worker
$v_{o}^{s}$ |  Claimed value from $s$ about $o$
$v_{o}^{w}$ |  Claimed value from $w$ about $o$
$R$ |  Set of all records collected from the set of sources $S$
$A$ |  Set of all answers collected from the set of workers $W$
$V_{o}$ |  Set of candidate values about $o$
$S_{o}$ |  Set of sources which post information about $o$
$W_{o}$ |  Set of workers who answered about $o$
$O_{s}$ |  Set of objects that source $s$ provided a value
$O_{w}$ |  Set of objects that worker $w$ answered to
$G_{o}(v)$ |  Set of values in $V_{o}$ which are ancestors of a value $v$ except the root in the hierarchy $H$
$D_{o}(v)$ |  Set of values in $V_{o}$ which are descendants of $v$

##  3\. Hierarchical Truth Inference

For the hierarchical truth inference, we first model the trustworthiness of
sources and workers for a given hierarchy. Then, we propose a probabilistic
model to describe the process of generating the set of records and the set of
answers based on the trustworthiness modeling. We next develop an inference
algorithm to estimate the model parameters and determine the truths.

###  3.1. Our Generative Model

Figure 3. A graphical model for truth inference

Our probabilistic graphical model in Figure 3 expresses the conditional
dependence (represented by edges) between random variables (represented by
nodes). While the previous works (Demartini et al., 2012; Whitehill et al.,
2009; Karger et al., 2011; Raykar et al., 2010) assume that all sources and
workers have their own reliabilities only, we assume that each source or
worker has its generalization tendency as well as reliability. We first
describe how sources and workers generate the claimed values based on their
trustworthiness. We next present the model for generating the true value.
Finally, we provide the detailed generative process of our probabilistic
model.

Model for source trustworthiness: For an object $o$, let $v_{o}^{*}$ be the
truth and $v_{o}^{s}$ be the claimed value reported by a source $s$. Recall
that $V_{o}$ is the set of candidate values for an object $o$. Furthermore, we
let $G_{o}(v)$ denote the set of candidate values which are ancestors of a
value $v$ except for the root in the hierarchy $H$.

There are three relationships between a claimed value $v_{o}^{s}$ and the
truth $v_{o}^{*}$: (1) $v_{o}^{s}=v_{o}^{*}$, (2) $v_{o}^{s}\in
G_{o}(v_{o}^{*})$ and (3) otherwise. Let
$\phi_{s}=(\phi_{s,1},\phi_{s,2},\phi_{s,3})$ be the _trustworthiness
distribution_ of a source $s$ where $\phi_{s,i}$ is the probability that a
claimed value of the source $s$ corresponds to the $i$-th relationship. In
each relationship, a claimed value is generated as follows:

  * •

Case 1 ($v_{o}^{s}=v_{o}^{*}$): The source $s$ provides the exact true value
with a probability $\phi_{s,1}$.

  * •

Case 2 ($v_{o}^{s}\in G_{o}(v_{o}^{*})$): The source $s$ provides a
_generalized true value_ $v_{o}^{s}$ with a probability $\phi_{s,2}$. In this
case, the claimed value is an ancestor of the truth $v_{o}^{*}$ in $H$. We
assume that the claimed value is uniformly selected from $G_{o}(v_{o}^{*})$.

  * •

Case 3 ($otherwise$): The source $s$ provides a wrong value $v_{o}^{s}$ not
even in $G_{o}(v_{o}^{*})$. The claimed value is uniformly selected among the
rest of the candidate values in $V_{o}$.

The probability distribution $\phi_{s}$ is an initially-unknown model
parameter to be estimated in our inference algorithm. Accordingly, the
probability of selecting an answer $v_{o}^{s}$ among the values in $V_{o}$ for
an object $o$ is represented by

(1) $P(v_{o}^{s}|v_{o}^{*},\phi_{s})=\begin{cases}\phi_{s,1}&\mbox{if
$v_{o}^{s}=v_{o}^{*}$,}\\\ \phi_{s,2}/|G_{o}(v_{o}^{*})|&\mbox{if
$v_{o}^{s}\in G_{o}(v_{o}^{*})$,}\\\
\phi_{s,3}/(|V_{o}|-|G_{o}(v_{o}^{*})|-1)&\mbox{otherwise.}\end{cases}\vspace{-0.02in}$

For the prior of the distribution $\phi_{s}$, we assume that it follows a
Dirichlet distribution $Dir(\alpha)$, with a hyperparameter
$\alpha=(\alpha_{1},\alpha_{2},$ $\alpha_{3})$, which is the conjugate prior
of categorical distributions.

Let $O_{H}$ be the set of objects who have an ancestor-descendant relationship
in their candidate set. In practice, there may exist some objects whose
candidate values do not have an ancestor-descendant relationship. In this
case, the probability of the second case (i.e., $\phi_{s,2}$) may be
underestimated. Thus, if there is no ancestor-descendant relationship between
the claimed values about $o$ (i.e., $o\notin O_{H}$), we assume that a source
generates its claimed value $v_{o}^{s}$ with the following probability

(2)
$P(v_{o}^{s}|v_{o}^{*},\phi_{s})=\begin{cases}\phi_{s,1}+\phi_{s,2}&\mbox{if
$v_{o}^{s}=v_{o}^{*}$,}\\\
\phi_{s,3}/(|V_{o}|-1)&\mbox{otherwise.}\end{cases}\vspace{-0.03in}$

$\displaystyle
f_{o,s}^{v}\\!=\\!\frac{P(v_{o}^{s}|v_{o}^{*}\\!=\\!v,\phi_{s})\\!\cdot\\!\mu_{o,v}}{\sum_{v^{\prime}\\!\in\\!V_{o}}{P(v_{o}^{s}|v_{o}^{*}\\!=\\!v^{\prime},\phi_{s})\\!\cdot\\!\mu_{o,v^{\prime}}}}$
$\displaystyle
f_{o,w}^{v}\\!=\\!\frac{P(v_{o}^{w}|v_{o}^{*}\\!=\\!v,\psi_{w})\\!\cdot\\!\mu_{o,v}}{\sum_{v^{\prime}\\!\in\\!V_{o}}{P(v_{o}^{w}|v_{o}^{*}\\!=\\!v^{\prime},\psi_{w})\\!\cdot\\!\mu_{o,v^{\prime}}}}$

(a)

$\displaystyle g_{o,s}^{1}\\!=\\!$
$\displaystyle\frac{\phi_{s,1}\\!\cdot\\!\mu_{o,v_{o}^{s}}}{\sum_{v\\!\in\\!V_{o}}{P(v_{o}^{s}|v_{o}^{*}\\!=\\!v,\phi_{s})\\!\cdot\\!\mu_{o,v}}}$
$\displaystyle g_{o,s}^{2}\\!=\\!$ $\displaystyle\begin{cases}\frac{\sum_{v\in
D_{o}(v_{o}^{s})}{\frac{\phi_{s,2}}{|G_{o}(v)|}\cdot\mu_{o,v}}}{\sum_{v\in
V_{o}}{P(v_{o}^{s}|v_{o}^{*}\\!=\\!v,\phi_{s})\cdot\mu_{o,v}}}&\mbox{\scriptsize
if $o\in O_{H}$}\\\\[5.0pt]
\frac{\phi_{s,2}\cdot\mu_{o,v_{o}^{s}}}{\sum_{v\\!\in\\!V_{o}}{P(v_{o}^{s}|v_{o}^{*}\\!=\\!v,\phi_{s})\cdot\mu_{o,v}}}&\mbox{\scriptsize
otherwise}\end{cases}$ $\displaystyle g_{o,s}^{3}\\!=\\!$
$\displaystyle\frac{\sum_{v\in\neg
D_{o}(v_{o}^{s})}{\frac{\phi_{s,3}}{|V_{o}-G_{o}(v)|-1}\cdot\mu_{o,v}}}{\sum_{v\in
V_{o}}{P(v_{o}^{s}|v_{o}^{*}\\!=\\!v,\phi_{s})\cdot\mu_{o,v}}}$

(b)

$\displaystyle g_{o,w}^{1}\\!=\\!$
$\displaystyle\frac{\psi_{w,1}\cdot\mu_{o,v_{o}^{w}}}{\sum_{v\in
V_{o}}{P(v_{o}^{w}|v_{o}^{*}\\!=\\!v,\psi_{w})\cdot\mu_{o,v}}}$ $\displaystyle
g_{o,w}^{2}\\!=\\!$
$\displaystyle\begin{cases}\frac{\sum_{v\\!\in\\!D_{o}(v_{o}^{w})}{\psi_{w,2}\cdot
Pop_{2}(v_{o}^{w}|v_{o}^{*}\\!=\\!v)\cdot\mu_{o,v}}}{\sum_{v\in
V_{o}}{P(v_{o}^{w}|v_{o}^{*}\\!=\\!v,\psi_{w})\cdot\mu_{o,v}}}&\mbox{\scriptsize
if $o\in O_{H}$}\\\\[5.0pt] \frac{\psi_{w,2}\cdot\mu_{o,v_{o}^{w}}}{\sum_{v\in
V_{o}}{P(v_{o}^{w}|v_{o}^{*}\\!=\\!v,\psi_{w})\cdot\mu_{o,v}}}&\mbox{\scriptsize
otherwise}\end{cases}$ $\displaystyle g_{o,w}^{3}\\!=\\!$
$\displaystyle\frac{\sum_{v\in\neg D_{o}(v_{o}^{w})}{\psi_{w,3}\cdot
Pop_{3}(v_{o}^{w}|v_{o}^{*}\\!=\\!v)\cdot\mu_{o,v}}}{\sum_{v\in
V_{o}}{P(v_{o}^{w}|v_{o}^{*}\\!=\\!v,\psi_{w})\cdot\mu_{o,v}}}$

(c)

Figure 4. E-step for the proposed truth inference algorithm

Model for worker trustworthiness: Let $v_{o}^{w}$ be the claimed value chosen
by a worker $w$ among the candidates in $V_{o}$ for an object $o$. Similar to
the model for source trustworthiness, we also assume the three relationships
between a claimed value $v_{o}^{w}$ and the truth $v_{o}^{*}$: (1)
$v_{o}^{w}=v_{o}^{*}$, (2) $v_{o}^{w}\in G_{o}(v_{o}^{*})$ and (3) otherwise.
Each worker $w$ has its _trustworthiness distribution_
$\psi_{w}\\!=\\!(\psi_{w,1},\psi_{w,2},\psi_{w,3})$ where $\psi_{w,i}$ is the
probability that an answer of the worker $w$ corresponds to the $i$-th
relationship. We assume that the trustworthiness distribution is generated
from $Dir(\beta)$ with a hyperparameter
$\beta=(\beta_{1},\beta_{2},\beta_{3})$.

Since it is difficult for the workers to be aware of the correct answer for
every object, a worker can refer to web sites to answer the question. In such
a case, if there is a widespread misinformation across multiple sources, the
worker is also likely to respond with the incorrect information. Similar to
(Dong et al., 2012; Pasternack and Roth, 2013), we thus exploit the
_popularity_ of a value in Cases 2 and 3 to consider such dependency between
sources and workers.

  * •

Case 1 ($v_{o}^{w}=v_{o}^{*}$): The worker $w$ provides the exact true value
with a probability $\psi_{w,1}$.

  * •

Case 2 ($v_{o}^{w}\in G_{o}(v_{o}^{*})$): The worker $w$ provides a
generalized true value with a probability $\psi_{w,2}$. We assume that the
claimed value $v_{o}^{w}$ is selected according to the popularity
$Pop_{2}(v_{o}^{w}|v_{o}^{*})=\frac{|\\{s|s\in
S_{o},v_{o}^{s}=v\\}|}{|\\{s|s\in S_{o},v_{o}^{s}\in G_{o}(v_{o}^{*})\\}|}$
which is the proportion of the records whose claimed value is $v_{o}^{w}$ out
of the records with generalized values of $v_{o}^{*}$.

  * •

Case 3 ($otherwise$): The claimed value is selected from the wrong values
according to the popularity $Pop_{3}(v_{o}^{w}|v_{o}^{*})=\frac{|\\{s|s\in
S_{o},v_{o}^{s}=v\\}|}{|\\{s|s\in S_{o},v_{o}^{s}\notin
G_{o}(v_{o}^{*}),v_{o}^{s}\neq v_{o}^{*}\\}|}$.

By the above model, the probability of selecting an answer $v_{o}^{w}$ for the
truth $v_{o}^{*}$ of an object $o$ is formulated as

(3) $P(v_{o}^{w}|v_{o}^{*},\psi_{w})\\!=\\!\begin{cases}\psi_{w,1}&\mbox{if
$v_{o}^{w}=v_{o}^{*}$,}\\\ \psi_{w,2}\cdot
Pop_{2}(v_{o}^{w}|v_{o}^{*})&\mbox{if $v_{o}^{w}\in G_{o}(v_{o}^{*})$,}\\\
\psi_{w,3}\cdot Pop_{3}(v_{o}^{w}|v_{o}^{*})&\mbox{otherwise.}\end{cases}$

Similar to the model for source trustworthiness, if there is no ancestor-
descendant relationship in the candidate values of an object $o$, the
probability of selecting a claimed value $v_{o}^{w}$ is

(4)
$P(v_{o}^{w}|v_{o}^{*},\psi_{w})=\begin{cases}\psi_{w,1}+\psi_{w,2}&\mbox{if
$v_{o}^{w}=v_{o}^{*}$,}\\\ \psi_{w,3}\cdot
Pop_{3}(v_{o}^{w}|v_{o}^{*})&\mbox{otherwise.}\end{cases}$

Model for truth: We introduce the probability distribution over the candidate
answers to determine the truth, called _confidence distribution_. Each object
$o$ has a confidence distribution $\mu_{o}=\\{\mu_{o,v}\\}_{v\in V_{o}}$ where
$\mu_{o,v}$ is the probability that the value $v\in V_{o}$ is the true answer
for $o$. We also use a dirichlet prior $Dir(\gamma_{o})$ for the confidence
distribution $\mu_{o}$ where $\gamma_{o}=\\{\gamma_{o,v}\\}_{v\in V_{o}}$ is a
hyperparameter.

Based on the above three models, the generative process of our model works as
follows.

Generative process: Given a set of objects $O$, a set of sources $S$ and a set
of workers $W$, our proposed model assumes the following generative process
for the set of records $R$ and the set of answers $A$:

  1. (1)

Draw $\phi_{s}\sim Dir(\alpha)$ for each source $s\in S$

  2. (2)

Draw $\psi_{w}\sim Dir(\beta)$ for each worker $w\in W$

  3. (3)

For each object $o\in O$

    1. (a)

Draw $\mu_{o}\sim Dir(\gamma_{o})$

    2. (b)

Draw a true value $v_{o}^{*}\sim Categorical(\mu_{o})$

    3. (c)

For each source $s\in S_{o}$

      1. (i)

Draw a value $v_{o}^{s}$ following $P(v_{o}^{s}|v_{o}^{*},\phi_{s})$

    4. (d)

For each worker $w\in W_{o}$

      1. (i)

Draw a value $v_{o}^{w}$ following $P(v_{o}^{w}|v_{o}^{*},\psi_{w})$

###  3.2. Estimation of Model Parameters

We now develop an inference algorithm for the generative model. Let
$\Theta=\boldsymbol{\phi}\cup\boldsymbol{\psi}\cup\boldsymbol{\mu}$ be the set
of all model parameters where
$\boldsymbol{\phi}\\!=\\!\\{\phi_{s}|s\\!\in\\!S\\}$,
$\boldsymbol{\psi}\\!=\\!\\{\psi_{w}|w\\!\in\\!W\\}$ and
$\boldsymbol{\mu}\\!=\\!\\{\mu_{o}|o\\!\in\\!O\\}$. We propose an EM algorithm
to find the maximum a posteriori (MAP) estimate of the parameters in our
model.

The maximum a posteriori (MAP) estimator: Recall that
$R=\\{(o,s,v_{o}^{s})\\}$ is the set of records from the sources and
$A\\!=\\!\\{(o,w,v_{o}^{w})\\}$ is the set of answers from the workers. For
every object $o$, each source $s\in S_{o}$ and each worker $w\in W_{o}$
generates its claimed values independently. Then, the likelihood of $R$ and
$A$ based on our generative model is

$\vspace{-0.02in}P(R,A|\Theta)\\!=\\!\prod_{o\in O}{\prod_{s\in
S_{o}}P(v_{o}^{s}|\phi_{s},\mu_{o})}\\!\cdot\\!\prod_{o\in O}{\prod_{w\in
W_{o}}P(v_{o}^{w}|\psi_{w},\mu_{o})}\vspace{-0.02in}$

where the probability of generating a claimed value by a source or a worker
becomes

(5) $\displaystyle P(v_{o}^{s}|\phi_{s},\mu_{o})$ $\displaystyle=\sum_{v\in
V_{o}}{P(v_{o}^{s}|\phi_{s},v_{o}^{*}=v)\cdot\mu_{o,v}}$ (6) $\displaystyle
P(v_{o}^{w}|\psi_{w},\mu_{o})$ $\displaystyle=\sum_{v\in
V_{o}}{P(v_{o}^{w}|\psi_{w},v_{o}^{*}=v)\cdot\mu_{o,v}}.$

Consequently, the MAP point estimator is obtained by maximizing the log-
posterior as

(7)
$\hat{\Theta}=\operatorname*{arg\,max}_{\Theta}{\\{\log{P(R,A|\Theta)}+\log{P(\Theta)}\\}}=\operatorname*{arg\,max}_{\Theta}{\mathbb{F}}$

where the objective function $\mathbb{F}$ is

$\displaystyle\vspace{-0.02in}\mathbb{F}$ $\displaystyle=\sum_{o\in
O}{\sum_{s\in S_{o}}\log{\sum_{v\in
V_{o}}{P(v_{o}^{s}|\phi_{s},v_{o}^{*}=v)\cdot\mu_{o,v}}}}$ (8)
$\displaystyle+\sum_{o\in O}{\sum_{w\in W_{o}}\log{\sum_{v\in
V_{o}}{P(v_{o}^{w}|\psi_{w},v_{o}^{*}=v)\cdot\mu_{o,v}}}}$
$\displaystyle+\sum_{s\in S}{\log{p(\phi_{s}|\alpha)}}\\!+\\!\sum_{w\in
W}{\log{p(\psi_{w}|\beta)}}\\!+\\!\sum_{o\in
O}{\log{p(\mu_{o}|\gamma_{o})}}.\vspace{-0.02in}$

Note that although we assumed that each claimed value is generated
independently according to its probability distribution defined in Eq. (5) and
(6), the dependencies between sources and workers are already considered in
$Pop_{2}(v_{o}^{w}|v_{o}^{*})$ and $Pop_{3}(v_{o}^{w}|v_{o}^{*})$.

The EM algorithm: We introduce a random variable $C_{v}$ to represent the type
of the relationship between the claimed value $v$ and the truth $v_{o}^{*}$.
It is defined as follows:

$\vspace{-0.03in}C_{v}=\begin{cases}1&\mbox{if $v=v_{o}^{*}$,}\\\ 2&\mbox{if
$v\in G_{o}(v_{o}^{*})$,}\\\ 3&\mbox{otherwise.}\end{cases}\vspace{-0.02in}$

In the _E-step_ , we compute the conditional distributions of the hidden
variables $C_{v_{o}^{s}}$, $C_{v_{o}^{w}}$ and $v_{o}^{*}$ under our current
estimate of the parameters $\Theta$. Let $f_{o,s}^{v}$, $f_{o,w}^{v}$,
$g_{o,s}^{t}$ and $g_{o,w}^{t}$ denote the conditional probabilities
$P(v_{o}^{*}\\!=\\!v|v_{o}^{s},\mu_{o},\phi_{s})$,
$P(v_{o}^{*}\\!=\\!v|v_{o}^{w},\mu_{o},\psi_{w})$,
$P(C_{v_{o}^{s}}\\!=\\!t|\mu_{o},\phi_{s})$ and $P(C_{v_{o}^{w}}\\!=\\!t|$
$\mu_{o},\psi_{w})$, respectively. Using Bayes’ rule, we can update the
conditional probabilities as shown in Figure 4 where
$D_{o}(v)=\\{v^{\prime}|v\in G_{o}(v^{\prime})\wedge v^{\prime}\in V_{o}\\}$
is the set of descendants of $v$ among the candidate values and $\neg
D_{o}(v)=V_{o}\\!-\\!D_{o}(v)\\!-\\!\\{v\\}$ is the set of candidate values
each of which is neither a descendant of the value $v$ nor the $v$ itself.

In the _M-step_ , we find the model parameters $\Theta$ that maximize our
objective function $\mathbb{F}$. We first add Lagrange multipliers to enforce
the constraints of model parameters.

$\mathbb{L}=\mathbb{F}\\!+\\!\sum_{s\in
S}{\lambda_{\phi,s}\left(1\\!-\\!\sum_{t=1}^{3}{\phi_{s,t}}\right)}\\!+\\!\sum_{w\in
W}{\lambda_{\psi,w}\left(1\\!-\\!\sum_{t=1}^{3}{\psi_{w,t}}\right)}\\!+\\!\sum_{o\in
O}{\lambda_{\mu,o}\left(1\\!-\\!\sum_{v\in V_{o}}{\mu_{o,v}}\right)}$

We obtain the following equations for updating the model parameters $\Theta$
by taking the partial derivative of the Lagrangian $\mathbb{L}$ with respect
to each model parameter and setting it to zero:

(9) $\mu_{o,v}=\frac{\sum_{s\in S_{o}}{f_{o,s}^{v}}+\sum_{w\in
W_{o}}{f_{o,w}^{v}}+\gamma_{o,v}-1}{|S_{o}|+|W_{o}|+\sum_{v^{\prime}\in
V_{o}}{\left(\gamma_{o,v^{\prime}}-1\right)}}$ (10)
$\phi_{s,t}=\frac{\sum_{o\in
O_{s}}{g_{o,s}^{t}}+\alpha_{t}-1}{|O_{s}|+\sum_{t^{\prime}=1}^{3}{(\alpha_{t^{\prime}}-1)}}$
(11) $\psi_{w,t}=\frac{\sum_{o\in
O_{w}}{g_{o,w}^{t}}+\beta_{t}-1}{|O_{w}|+\sum_{t^{\prime}=1}^{3}{(\beta_{t^{\prime}}-1)}}$

where $O_{s}$ and $O_{w}$ are the sets of objects claimed by $s$ and $w$,
respectively. We infer the truth by choosing the value with the maximum
confidence among the candidate values as

(12) $v_{o}^{*}=\operatorname*{arg\,max}_{v\in V_{o}}\mu_{o,v}.$

Extension to numerical data: In the world wide web, numerical data also have
an implicit hierarchy due to the significant digits which carry meaning
contributing to its measurement resolution. For example, even though the area
of Seoul is $605.196km^{2}$, different websites may represent the area in
various forms depending on the significant figures (e.g., $605.2km^{2}$,
$605km^{2}$). An existing algorithm (Li et al., 2014a) to handle numerical
data utilizes a weighted sum of the claimed values to consider the
distribution of the claimed values. However, such method is sensitive to
outliers and thus need a proper preprocessing to remove the outliers. To
overcome the drawbacks, we generate the underlying hierarchy in the numerical
data by assuming that $v_{d}$ is a descendant of $v_{a}$ if a value $v_{a}$
can be obtained by rounding off a value $v_{d}$. Then, we can use our TDH
algorithm to find the truths in numerical data by taking into account the
relationship between the values in the implicit hierarchy. Our algorithm is
also robust to the outliers with extremely small or large value since we
estimate the truth by selecting the most probable value from the candidate
values rather than computing a weighted average of the claimed values.

##  4\. Task Assignment to Workers

In this section, we propose a task assignment method to select the best
objects to be assigned to the workers in crowdsourcing systems. We first
define a quality measure of tasks called _Expected Accuracy Increase (EAI)_
and develop an incremental EM algorithm to quickly estimate the quality
measure. Finally, we present an efficient algorithm for assigning the $k$
questions to each worker $w$ in a set of workers $W$ based on the measure.

###  4.1. The Quality Measure

Given a worker $w$, our goal is to choose an object to be assigned to the
worker $w$ which is likely to increase the accuracy of the estimated truths
the most. Thus, we define a quality measure for a pair of worker and an object
based on the improvement of the accuracy. As discussed in (Zheng et al.,
2015), the improvement of the accuracy by a task can be estimated by using the
difference between the highest confidence as follows:

(13)
$(Accuracy~{}improvement)=\\{\max_{v}{\mu_{o,v|w}}-\max_{v}{\mu_{o,v}}\\}/|O|$

where $\mu_{o,v|w}$ is the estimated confidence on $v$ if the worker $w$
answers about an object $o$.

The quality measure used by QASCA: The QASCA(Zheng et al., 2015) algorithm
calculates the estimated confidence by using the current confidence
distribution and the likelihood of the answer $v_{o}^{w}$ given the truth
$v_{o}^{*}=v$ as

$\mu_{o,v|w}\propto\mu_{o,v}\cdot p(v_{o}^{w}=v^{\prime}|v_{o}^{*}=v)$

where $v^{\prime}$ is a sampled claimed value. There are two drawbacks in the
quality measure of QASCA. First, since it computes the estimated confidence
$\mu_{o,v|w}$ based on a sampled answer $v_{o}^{w}=v$, the value of the
quality measure is very sensitive to the sampled answer. In addition, QASCA
does not consider the number of claimed values collected so far and the
estimated confidence $\mu_{o,v|w}$ may not be accurate. For instance, assume
that there exist two objects which have identical confidence distributions. If
one of the objects already has many collected claimed values, an additional
answer is not likely to change the confidence significantly. Thus, task
assignment algorithms should select another object who has a smaller number of
collected records and answers.

Our quality measure: To avoid the sensitiveness caused by sampling answers, we
develop a new quality measure _Expected Accuracy Improvement (EAI)_ which is
obtained by taking the expectation to Eq. (13). That is,

(14) $EAI(w,o)=\\{E[\max_{v}{\mu_{o,v|w}}]-\max_{v}{\mu_{o,v}}\\}/|O|.$

By the definition of expectation, $E[\max_{v}{\mu_{o,v|w}}]$ becomes

(15) $\begin{split}&E[\max_{v}{\mu_{o,v|w}}]\\!=\\!\sum_{v^{\prime}\in
V_{o}}{P(v_{o}^{w}\\!=\\!v^{\prime}|\psi_{w},\mu_{o})\\!\cdot\\!\max_{v}{\mu_{o,v|v_{o}^{w}\\!=\\!v^{\prime}}}}.\end{split}$

where $\mu_{o,v|v_{o}^{w}=v^{\prime}}$ is the conditional confidence when a
worker $w$ answers with $v^{\prime}$ about the object $o$.

Since $P(v_{o}^{w}=v^{\prime}|\psi_{w},\mu_{o})$ can be computed by Eq. (6),
to compute $E[\max_{v}{\mu_{o,v|w}}]$ by Eq. (15), we need the estimation of
the conditional confidence $\mu_{o,v|v_{o}^{w}=v^{\prime}}$ with an additional
answer $v_{o}^{w}=v^{\prime}$. Recall that the estimated confidence computed
by QASCA may not be accurate because it does not consider the collected
records and answers so far. To reduce the error, we use them to compute the
conditional confidence $\mu_{o,v|v_{o}^{w}=v^{\prime}}$. We can compute the
conditional confidence $\mu_{o,v|v_{o}^{w}=v^{\prime}}$ by applying the EM
algorithm in Section 3.2 with the collected records and answers including
$v_{o}^{w}=v^{\prime}$. However, since it is computationally expensive, we
next develop an _incremental EM algorithm_.

###  4.2. The Incremental EM Algorithm

Let $\mathbb{F}_{v_{o}^{w}=v^{\prime}}$ be the objective function in Eq. (7)
after obtaining an additional answer $(o,w,v^{\prime})$. Then, we have

$\mathbb{F}_{v_{o}^{w}=v^{\prime}}=\mathbb{F}+\log{\sum_{v\in
V_{o}}{P(v_{o}^{w}=v^{\prime}|\psi_{w},v_{o}^{*}=v)\cdot\mu_{o,v}}}$

by adding the related term of the additional answer (log likelihood of the
additional answer) to Eq. (8). Instead of running the iterative EM algorithm
in Section 3.2, we incrementally perform a _single EM-step_ to speed up for
only the additional answer with the current model parameters and the above
objective function.

E-step: Since we use the current model parameters, the probabilities of the
hidden variables for collected records and answers are not changed. Thus, we
only need to compute the conditional probabilities of the hidden variable
given the additional answer as

(16)
$f_{o,w|v_{o}^{w}=v^{\prime}}^{v}\mspace{2.0mu}\mathsf{=}\mspace{2.0mu}\frac{P(v_{o}^{w}\\!=\\!v^{\prime}|v_{o}^{*}\\!\mspace{2.0mu}\mathsf{=}\mspace{2.0mu}v,\psi_{w})\cdot\mu_{o,v}}{\sum_{v^{\prime\prime}\in
V_{o}}{P(v_{o}^{w}\\!=\\!v^{\prime}|v_{o}^{*}\mspace{2.0mu}\mathsf{=}\mspace{2.0mu}v^{\prime\prime},\psi_{w})\cdot\mu_{o,v^{\prime\prime}}}}$

based on the equation for $f_{o,w}^{v}$ used at the E-step in Figure 4.

M-step: For the objective function $\mathbb{F}_{v_{o}^{w}=v^{\prime}}$, we
obtain the following equation of the M-step for the confidence distribution
$\mu_{o}$ with the additional answer $v_{o}^{w}=v^{\prime}$

$\mu_{o,v|v_{o}^{w}=v^{\prime}}\mspace{2.0mu}\mathsf{=}\mspace{2.0mu}\frac{\sum_{s\in
S_{o}}{f_{o,s}^{v}}\\!+\\!\sum_{w^{\prime}\in
W_{o}}{f_{o,w^{\prime}}^{v}}\\!+\\!f_{o,w|v_{o}^{w}\\!=\\!v^{\prime}}^{v}\\!+\\!\gamma_{o,v}\\!-\\!1}{|S_{o}|\\!+\\!|W_{o}|\\!+\\!1\\!+\\!\sum_{v^{\prime\prime}\in
V_{o}}{\left(\gamma_{o,v^{\prime\prime}}-1\right)}}$

by adding the related terms $f_{o,w|v_{o}^{w}=v^{\prime}}^{v}$ and $1$ to the
numerator and the denominator of the update equation in Eq. (9), respectively.
Let $N_{o,v}$ and ${D_{o}}$ be the numerator and the denominator in Eq. (9),
respectively. Then, the above equation can be rewritten as

(17)
$\vspace{-0.02in}\mu_{o,v|v_{o}^{w}=v^{\prime}}=\frac{N_{o,v}+f_{o,w|v_{o}^{w}=v^{\prime}}^{v}}{D_{o}+1}.$

By substituting $f_{o,w|v_{o}^{w}=v^{\prime}}^{v}$ in Eq. (17) with Eq. (16),
the conditional confidence becomes

(18)
$\mu_{o,v|v_{o}^{w}=v^{\prime}}=\frac{N_{o,v}+\frac{P(v_{o}^{w}=v^{\prime}|v_{o}^{*}=v,\psi_{w})\cdot\mu_{o,v}}{\sum_{v^{\prime\prime}\in
V_{o}}{P(v_{o}^{w}=v^{\prime}|v_{o}^{*}=v^{\prime\prime},\psi_{w})\cdot\mu_{o,v^{\prime\prime}}}}}{D_{o}+1}.$

Since $N_{o,v}$ and $D_{o}$ are proportional to the number of the existing
claimed values, the confidence will be changed very little if there are many
claimed values already. Thus, we can overcome the second drawback of QASCA.
Since $N_{o,v}$s and ${D_{o}}$s are repeatedly used to compute
$\mu_{o,v|v_{o}^{w}=v^{\prime}}$, our truth inference algorithm keeps
$N_{o,v}$s and ${D_{o}}$s in main memory to reduce the computation time.

Time complexity analysis: To calculate $E[\max_{v}{\mu_{o,v|w}}]$ by Eq. (15),
$P(v_{o}^{w}=v^{\prime}|\psi_{w},\mu_{o})$ is computed $|V_{o}|$ times and
$\mu_{o,v|v_{o}^{w}=v^{\prime}}$ is calculated for every pair of $v$ and
$v^{\prime}$ (i.e., $O(|V_{o}|^{2})$ times). Moreover, computing
$P(v_{o}^{w}=v^{\prime}|\psi_{w},\mu_{o})$ and
$\mu_{o,v|v_{o}^{w}=v^{\prime}}$ take $O(|V_{o}|)$ time. Thus, it takes
$O(|V_{o}|^{3})$ time to compute $EAI(w,o)$ by Eq. (14). In reality, $|V_{o}|$
is very small compared to $|O|$,$|S|$ and $|W|$. In addition, by utilizing the
pruning technique in the next section, we can significantly reduce the
computation time. Therefore, the task assignment step can be performed within
a short time compared to the truth inference. The execution time for each step
will be presented in the experiment section.

###  4.3. The Task Assignment Algorithm

To find the $k$ objects to be assigned to each worker, we need to compute
$EAI(w,o)$ for all pairs of $w$ and $o$. To reduce the number of computing
$EAI(w,o)$, we develop a pruning technique by utilizing an upper bound of
$EAI(w,o)$.

An upper bound of EAI: We provide the following lemma which allows us to
compute an upper bound $U_{EAI}(o)$.

###### Lemma 4.1.

_(Upper Bound of Expected Accuracy Increase)_ For an object $o$ and a worker
$w$, we have

(19) $EAI(w,o)\leq
U_{EAI}(o)=\frac{1-\max_{v}{\mu_{o,v}}}{|O|\cdot(D_{o}+1)}.$

###### Proof.

From Eq. (18), since
$\sum_{v^{\prime}}{P(v_{o}^{w}\\!=\\!v^{\prime}|\psi_{w},\mu_{o})}\\!=\\!1$,
we get

$\displaystyle E[\max_{v}{\mu_{o,v|w}}]$ $\displaystyle=\sum_{v^{\prime}\in
V_{o}}{P(v_{o}^{w}{\\!=\\!}v^{\prime}|\psi_{w},\mu_{o})\cdot\max_{v}{\mu_{o,v|v_{o}^{w}=v^{\prime}}}}$
$\displaystyle\leq\max_{v,v^{\prime}}{\mu_{o,v|v_{o}^{w}=v^{\prime}}\cdot\sum_{v^{\prime}\in
V_{o}}{P(v_{o}^{w}{\\!=\\!}v^{\prime}|\psi_{w},\mu_{o})}}$ (20)
$\displaystyle=\max_{v,v^{\prime}}{\mu_{o,v|v_{o}^{w}=v^{\prime}}}.\mspace{10.0mu}\mbox{}$

Moreover, from Eq. (17), we obtain

(21) $\displaystyle\mu_{o,v|v_{o}^{w}=v^{\prime}}$
$\displaystyle=\frac{N_{o,v}+f_{o,w|v_{o}^{w}=v^{\prime}}^{v}}{D_{o}+1}\leq\frac{N_{o,v}+1}{D_{o}+1}.$

By substituting Eq. (21) for $\mu_{o,v|v_{o}^{w}=v^{\prime}}$ in Eq. (20), we
derive

(22)
$\begin{split}E[\max_{v}{\mu_{o,v|w}}]&\leq\max_{v,v^{\prime}}{\mu_{o,v|v_{o}^{w}\\!=\\!v^{\prime}}}\leq\frac{\max_{v}N_{o,v}+1}{D_{o}+1}.\end{split}$

In addition, by applying Eq. (22) to Eq. (14), we get

$\begin{array}[]{lr}EAI(w,o)\leq(\frac{\max_{v}{N_{o,v}}+1}{D_{o}+1}-\max_{v}{\mu_{o,v}})/|O|.\end{array}$

Since $\mu_{o,v}=\frac{N_{o,v}}{D_{o}}$, we finally obtain the upper bound of
$EAI(w,o)$.

$\begin{array}[]{ll}EAI(w,o)&\leq(\frac{\max_{v}{N_{o,v}}+1}{D_{o}+1}-\frac{\max_{v}{N_{o,v}}}{D_{o}})/|O|\\\
&=\frac{1-\frac{\max_{v}{N_{o,v}}}{D_{o}}}{|O|\cdot(D_{o}+1)}=\frac{1-\max_{v}{\mu_{o,v}}}{|O|\cdot(D_{o}+1)}=U_{EAI}(o).\end{array}$

∎

Algorithm 1 Task Assignment

0: set of workers $W$, number of questions $k$

1: Compute the upper bound $U_{EMCI}(o)$ for $o\in O$

2: $h_{UB}$ $\leftarrow$ BuildMaxHeap({$\langle U_{EAI}(o),o\rangle$|$o\in
O$})

3: Sort workers in the decreasing order of $\psi_{w,1}$ (i.e.,
$\psi_{1,1}\\!\geq\\!\psi_{2,1}\\!\geq\\!\cdots\\!\geq\\!\psi_{|W|,1}$).

4: for $w=1$ to $|W|$ do

5: $h_{EAI}[w]$ $\leftarrow$ BuildMinHeap({})

6: while True do

7: $\langle U_{EAI}(o),o\rangle\leftarrow h_{UB}$.extractMax()

8: if $h_{EAI}[|W|].size\\!=\\!k$ and $h_{EAI}[w].min\\!>\\!U_{EAI}(o)$ for
all $w$ then

9: break

10: for $w=1$ to $|W|$ do

11: if $w$ already answered on $o$ or $h_{EAI}[w].min\\!>\\!U_{EAI}(o)$ then

12: continue

13: Compute $EAI(w,o)$

14: $h_{EAI}[w]$.insert($\langle EAI(w,o),o\rangle$)

15: if $h_{EAI}[w].size\leq k$ then

16: break

17: $o\leftarrow h_{EAI}[w]$.extractMin().value()

We devise an algorithm to assign the best $k$ objects to each available worker
in crowdsourcing systems. Since a single answer is sufficient to find the
correct value for some objects, we assign an object to only a single worker in
each round. If the answer is not sufficient to find the correct value of the
object, we assign the object to another worker in the next round.

Our task assignment algorithm sequentially assigns each object to a worker by
scanning the objects $o$ with non-increasing order of the upper bound
$U_{EAI}(o)$. To allocate an object to a worker, since $\psi_{w,1}$ is the
probability of answering the truth, we consider the workers $w$ with non-
increasing order of $\psi_{w,1}$. After assigning an object to a worker $w$,
if the number of assigned objects to the worker $w$ exceeds $k$, we remove the
object $o$ with the minimum $EAI(w,o)$ and assign the deleted object to the
next worker and perform the same step. While scanning the objects, we stop the
assignment if the upperbound $U_{EAI}(o)$ is smaller than the minimum
$EAI(w,o^{\prime})$ among the $EAI(w,o^{\prime})$s of all assigned objects and
each worker has $k$ assigned objects. The reason is that the $EAI(w,o)$ of the
remaining objects $o$ can be larger than that of any assigned object.

The pseudocode: It is shown in Algorithm 1. We first compute the upper bound
$U_{EAI}(o)$ for every object $o\in O$ by Lemma 4.1 and build a maxheap
$h_{UB}$ of all objects by using $U_{EAI}(o)$ as the key to assign the objects
to workers in the decreasing order of $U_{EAI}(o)$ (in lines 1-2). The workers
are sorted in the decreasing order of $\psi_{w,1}$ to give a higher priority
to reliable workers (in line 3). We next initialize a minheap $h_{EAI}[w]$ for
each worker $w$ to contain the $k$ assigned objects (in lines 4-6). Then, we
repeatedly extract an object from $h_{UB}$ and assign the object to a worker
in the sorted order of $\psi_{w,1}$ (in lines 12-18). Before assigning an
object $o$, if the heaps $h_{EAI}[w]$s of all workers are full and the minimum
value of $EAI(w,o^{\prime})$ of the objects $o^{\prime}$ in all $h_{EAI}[w]$s
is larger than the upper bound $U_{EAI}(o)$, we stop immediately.

##  5\. Experiments

The experiments are conducted on a computer with Intel i5-7500 CPU and 16GB of
main memory.

Datasets: We collected the two real-life datasets publicly available at
http://kdd.snu.ac.kr/home/datasets/tdh.php.

_BirthPlaces_ : We crawled 13,510 records about the birthplaces of 6,005
celebrities from 7 websites (sources). For the gold standard data to evaluate
the correctness of discovered birthplaces, we used IMDb biography which is
available at http://www.imdb.com. Moreover, the geographical hierarchy was
created by using the IMDb data. For example, if there is a person who was born
in ‘LA, California, USA’, we assigned ‘LA’ as a child of ‘California’ and
‘California’ as a child of ‘USA’. The hierarchy contains 4,999 nodes (e.g.,
countries, cities and etc.) and its height is 5.

_Heritages_ : This is a dataset of the locations of World Heritage Sites
provided by UNESCO World Heritage Centre, available at http://whc.unesco.org.
We queried about the locations of 785 World Heritage Sites with Bing Search
API and obtained 4,424 claimed values from 1,577 distinct websites. The
hierarchy was created in the same way as we did for _BirthPlaces_ and it has
1,027 nodes. The height of this hierarchy tree is 6.

Quality Measures: We use _Accuracy_ , _GenAccuracy_ and _AvgDistance_ to
evaluate the truth discovery algorithms. Let $t_{o}$ be the truth of the
object $o$ in the gold standard and $v_{o}^{*}$ be the estimated truth by an
algorithm. Note that $t_{o}$ may not exist in the set of candidate values. In
this case, the most specific candidate value among the ancestors of the truth
is assumed to be $t_{o}$. _Accuracy_ is the proportion of objects that the
algorithm discovers the truth exactly. It is actually used in (Zheng et al.,
2016; Dong and Srivastava, 2015; Zheng et al., 2015, 2017) to evaluate truth
discovery algorithms.

$(\emph{Accuracy})={\Sigma_{o\in O}{I(v_{o}^{*}=t_{o})}}/{|O|}$

The ancestors of $t_{o}$ are less informative but still correct values. Thus,
we develop an evaluation measure named _GenAccuracy_ which is the proportion
of objects $o$ whose estimated truth $v_{o}^{*}$ is either the truth $t_{o}$
or an ancestor of the truth.

$(\emph{GenAccuracy})={\Sigma_{o\in
O}{I(v_{o}^{*}\\!\in\\!G_{H}(t_{o})\\!\cup\\!\\{t_{o}\\})}}/{|O|}$

Ancestors of the truth have a different level of informativeness depending on
the distance to the truth. For example, ‘New York’ is more informative than
‘USA’ as the location of the Statue of Liberty. Thus, we utilize another
evaluation measure named _AvgDistance_ which weights the estimated truth based
on the distance from the ground truth. More specifically, it is the average
number of edges $d(v_{o}^{*},t_{o})$ between the truth $t_{o}$ and the
estimated truth $v_{o}^{*}$ in the hierarchy $H$.

$(\emph{AvgDistance})={\Sigma_{o\in O}{d(v_{o}^{*},t_{o})}}/{|O|}$

_AvgDistance_ is robust to the case where the ground truth is less specific
than the estimated truth. The estimated truth is regarded as a wrong value
when we compute _Accuracy_ and _GenAccuracy_ even though the estimate truth is
correct and more specific. Since the distance between the less specific ground
truth and the estimated truth is generally small, _AvgDistance_ compensates
the drawback of _Accuracy_ and _GenAccuracy_.

Table 3. Performance of truth inference algorithms | Dataset
---|---
| _BirthPlaces_ | _Heritages_
Algorithm | _Accuracy_ | _GenAccuracy_ | _AvgDistance_ | _Accuracy_ | _GenAccuracy_ | _AvgDistance_
TDH | 0.8913 | 0.8988 | 0.3151 | 0.7414 | 0.8726 | 0.5210
VOTE | 0.7900 | 0.8924 | 0.4961 | 0.6892 | 0.8994 | 0.6382
LCA | 0.8834 | 0.8923 | 0.3414 | 0.6930 | 0.8866 | 0.6611
DOCS | 0.8828 | 0.8916 | 0.3409 | 0.6904 | 0.8866 | 0.6599
ASUMS | 0.8543 | 0.8571 | 0.4573 | 0.6229 | 0.7414 | 1.2000
MDC | 0.8263 | 0.8432 | 0.5320 | 0.7254 | 0.8087 | 0.6869
ACCU | 0.8137 | 0.8296 | 0.6063 | 0.5834 | 0.7656 | 1.0637
POPACCU | 0.8133 | 0.8300 | 0.6070 | 0.6561 | 0.8586 | 0.7554
LFC | 0.8085 | 0.8743 | 0.4669 | 0.6803 | 0.8076 | 0.8076
CRH | 0.8083 | 0.8271 | 0.6120 | 0.6841 | 0.8828 | 0.6688

Settings for simulated crowdsourcing: To evaluate the truth discovery
algorithms with varying the quality of the answers from workers, we conducted
experiments with simulated crowd workers. In our simulation, we assumed that
each simulated worker answers a question correctly with its own probability
$p_{w}$ and randomly selects an answer from the candidate values with
probability $1$$-$$p_{w}$. We sampled the probability $p_{w}$ from a uniform
distribution ranging from $\pi_{p}$$-$$0.05$ to $\pi_{p}$$+$$0.05$ where the
default value of $\pi_{p}$ is 0.75. In the experiments, each of 10 worker
answers 5 questions for each round.

###  5.1. Implemented Algorithms

We implemented 10 truth inference algorithms and 4 task assignment algorithms
in Python for comparative experiments. The truth inference algorithms are
referred to as follows:

  * •

TDH: This is our algorithm proposed in Section 3. For the prior distribution
$Dir(\alpha)$, we set the hyperparameter $\alpha=(3,3,2)$ since correct values
are more frequent than wrong values for most of the sources. For the other
hyperparameters $\beta$ and $\gamma$, we set every dimension of $\beta$ and
$\gamma$ to 2.

  * •

ACCU: It is the algorithm proposed in (Dong et al., 2009) which considers the
dependencies between sources to find the truths. The algorithm exploits
Bayesian analysis to find the dependencies.

  * •

POPACCU: This denotes the algorithm in (Dong et al., 2012) which extends ACCU.
It computes the distribution of the false values from the records while ACCU
assumes that it is uniform.

  * •

LFC: This algorithm is proposed in (Raykar et al., 2010) and utilizes a
confusion matrix to model a source’s quality.

  * •

CRH: It is proposed in (Li et al., 2014b) to resolve conflicts in
heterogeneous data containing categorical and numerical attributes.

  * •

LCA: It is a probabilistic model proposed in (Pasternack and Roth, 2013). We
select GuessLCA to be compared in this paper which is one of the best
performers among the 7 algorithms proposed in (Pasternack and Roth, 2013).

  * •

ASUMS: This is proposed in (Beretta et al., 2016) by adapting an existing
method SUMS (Pasternack and Roth, 2010) to hierarchical truth discovery.

  * •

MDC: This denotes the truth discovery method designed for medical diagnose
from non-expert crowdsourcing in (Li et al., 2017).

  * •

DOCS: This is the state-of-the-art technique presented in (Zheng et al., 2016)
that suggests the domain-sensitive worker model.

  * •

VOTE: This is a baseline that selects a value with the highest frequency in
the claimed values.

We implemented the following task assignment algorithms.

  * •

_EAI_ : This is our proposed algorithm in Section 4.

  * •

_MB_ : It is the task assignment algorithm used by DOCS (Zheng et al., 2016).

  * •

_QASCA_ : It is a task assignment algorithm proposed in (Zheng et al., 2015).

  * •

_ME_ : This is our baseline algorithm which utilizes an uncertainty sampling.
It selects an object $o^{*}$ whose confidence distribution has the maximum
entropy. (i.e., $o^{*}=argmax_{o\in O}$ ${(-\sum_{v\in
V_{o}}{\mu_{o,v}\cdot\log{\mu_{o,v}}})}$)

Note that _EAI_ and _MB_ are the task assignment algorithms specially designed
to work with _TDH_ and _DOCS_ , respectively. _QASCA_ can work with truth
inference algorithms based on probabilistic models such as _TDH_ , _DOCS_ ,
_LCA_ , _ACCU_ and _POPACCU_. All the truth inference algorithms can be
combined with _ME_.

Figure 5. Source reliability distribution in _BirthPlaces_

###  5.2. Truth Inference

We first provide the performances of the truth inference algorithms without
using crowdsourcing in Table. 3.

_BirthPlaces_ : Our TDH outperforms all other algorithms in terms of all
quality measures since TDH finds the exact truths by utilizing the
hierarchical relationships. Since TDH estimates the reliabilities of the
sources and workers by considering the hierarchies, it does not underestimate
the reliabilities of the sources and workers. Thus, TDH also finds more
correct values including the generalized truths. We will discuss the
reliability estimation in detail at the end of this section by comparing TDH
with ASUMS. LCA is the second-best performer and VOTE shows the lowest
_Accuracy_ among all compared algorithms. However, in terms of _GenAccuracy_ ,
VOTE performs the second-best. It is because many websites claim the
generalized values rather than the most specific value.

_Heritages_ : In terms of _AvgDistance_ and _Accuracy_ , TDH performs the best
among those of the compared algorithms. VOTE shows the highest _GenAccuracy_
because many sources provide the generalized truths. In fact, a high
_GenAccuracy_ with low _Accuracy_ and _AvgDistance_ can be easily obtained by
providing the most general values for the truths. However, such values usually
are not informative. Since our algorithm shows much higher _Accuracy_ and much
lower _AvgDistance_ than VOTE, we can see that the estimated truth by TDH is
more accurate and precise than the result from VOTE. _Heritages_ contains many
sources and most of the sources have a few claims. Thus, it is very hard to
estimate the reliability of each source accurately. Therefore, most of the
compared algorithms show worse performance than VOTE in terms of
_AvgDistance_. In particular, ACCU has the lowest _Accuracy_. The reason is
that ACCU requires many shared objects between two sources in order to
accurately determine the dependency between the sources. The average accuracy
of the sources in _Heritages_ is 58.0% while that of the sources in
_BirthPlaces_ is 72.1%. Thus, every algorithm shows a lower _Accuracy_ in this
dataset than in _BirthPlaces_.

(a) _BirthPlaces_

(b) _Heritages_

Figure 6. Evaluation of task assignment algorithms

(a) _BirthPlaces_ -EAI

(b) _BirthPlaces_ -QASCA

(c) _Heritages_ -EAI

(d) _Heritages_ -QASCA

Figure 7. Actual and estimated accuracy improvement by EAI and QASCA

(a) _BirthPlaces_

(b) _Heritages_

Figure 8. _Accuracy_ with crowdsourced truth discovery

(a) _BirthPlaces_

(b) _Heritages_

Figure 9. _GenAccuracy_ with crowdsourced truth discovery

(a) _BirthPlaces_

(b) _Heritages_

Figure 10. _AvgDistance_ with crowdsourced truth discovery

Comparison with ASUMS: Since ASUMS (Beretta et al., 2016) is the only existing
algorithm which utilizes hierarchies for truth inference, we show the
statistics related to the reliability distributions estimated by TDH and ASUMS
for _BirthPlaces_ dataset in Figure 5. _Accuracy_ and _GenAccuracy_ represent
the actual reliabilities of each source computed from the ground truths.
Recall that $\phi_{s,1}$ and $\phi_{s,2}$ are the estimated probabilities of
providing a correct value and a generalized correct value respectively for a
source $s$ by our TDH, as defined in Section 3. In addition, $t(s)$ is the
estimated reliability of a source $s$ by ASUMS which ignores the
generalization level of each source. The reliabilities of the sources 4, 5 and
7 computed by ASUMS (i.e. $t(s)$) are quite different from the actual
reliabilities (i.e., _Accuracy_). As we discussed in Section 1, for a pair of
sources that provide different claimed values with an ancestor-descendant
relationship in a hierarchy, existing methods may assume that one of the
claimed values is incorrect. Thus, the reliability of the source with the
assumed wrong value tends to become lower by the existing methods. ASUMS
suffers from the same problem and underestimates the reliabilities of the
sources 4, 5 and 7 which provide a small number of claimed values. Meanwhile,
our proposed algorithm TDH accurately estimates the reliabilities of the
sources by introducing another class of the claimed values (generalized
truth).

Table 4. _Accuracy_ of the algorithms after the 50th round | _BirthPlaces_ | _Heritages_
---|---|---
| EAI | MB | QASCA | ME | EAI | MB | QASCA | ME
TDH | 0.9601 | - | 0.9500 | 0.9109 | 0.9304 | - | 0.8999 | 0.8884
DOCS | - | 0.9052 | 0.9341 | 0.8842 | - | 0.7546 | 0.7661 | 0.7631
LCA | - | - | 0.8823 | 0.9089 | - | - | 0.7136 | 0.8507
POPACCU | - | - | 0.9295 | 0.8987 | - | - | 0.7512 | 0.8336
ACCU | - | - | 0.8468 | 0.8257 | - | - | 0.5796 | 0.5896
ASUMS | - | - | - | 0.8700 | - | - | - | 0.7427
CRH | - | - | - | 0.9000 | - | - | - | 0.8459
MDC | - | - | - | 0.8254 | - | - | - | 0.7241
LFC | - | - | - | 0.8287 | - | - | - | 0.7327
VOTE | - | - | - | 0.8261 | - | - | - | 0.8634

###  5.3. Task Assignment

Before providing the full comparison of all possible combinations of truth
inference algorithms and task assignment algorithms, we first evaluate the
task assignment algorithms with our proposed truth inference algorithm. We
plotted the average _Accuracy_ of the truth discovery algorithms with
different task assignment algorithms for every 5 round in Figure 6. The points
at the 0-th round represent the _Accuracy_ of the algorithms without
crowdsourcing. All algorithms show the same _Accuracy_ at the beginning since
they use the same truth inference algorithm TDH. As the round progresses, the
_Accuracy_ of TDH+EAI increases faster than those of all other algorithms. The
_Accuracy_ of TDH+ME is the lowest since ME selects a task based only on the
uncertainty without estimating the accuracy improvement by the task.

As discussed in Section 4.1, our task assignment algorithm EAI estimates the
accuracy improvement by considering the number of existing claimed values and
the confidence distribution whereas QASCA considers the confidence
distribution only. We plotted the actual and estimated accuracy improvements
by EAI and QASCA in Figure 7. The graphs show that the estimated accuracy
improvement by EAI is similar to the actual accuracy improvement while QASCA
overestimates the accuracy improvement at every round. On average, the
absolute estimation errors from EAI are 0.08 and 0.26 percentage points (pps)
while those errors from QASCA are 0.28 and 2.66 pps in _BirthPlaces_ and
_Heritages_ datasets, respectively. This result confirms that EAI outperforms
QASCA by effectively estimating the accuracy improvement. In terms of the
other quality measures _GenAccuracy_ and _AvgDistance_ , our proposed EAI also
outperforms the other task assignment algorithms in both datasets. Due to the
lack of space, we omit the results with the other quality measures.

###  5.4. Simulated Crowdsourcing

We evaluate the performance of crowdsourced truth discovery algorithms with
the simulated crowdsourcing.

For all possible combinations of the implemented truth inference and task
assignment algorithms, we show the _Accuracy_ after 50 rounds of crowdsourcing
in Table 4 where the impossible combinations are denoted by ‘-’. As expected,
TDH+EAI has the highest _Accuracy_ in both datasets for all possible
combinations. The result also shows that both TDH and EAI contribute to
increasing _Accuracy_. The improvement obtained by EAI can be estimated by
comparing the result of TDH+EAI to that of the second performer TDH+QASCA. The
accuracies of TDH+EAI in _BirthPlaces_ and _Heritages_ datasets are 1 and 3
percentage points (pps) higher than those of TDH+QASCA, respectively. In
addition, for each combined task assignment algorithm, the improvement by TDH
can be inferred by comparing the results with those of other truth inference
algorithms. In both datasets, TDH shows the highest _Accuracy_ among the
applicable truth inference algorithms for each task assignment algorithm. For
example, TDH+QASCA shows 2.6 and 13 pps higher _Accuracy_ in _BirthPlaces_ and
_Heritages_ datasets, respectively, than the second performer DOCS+QASCA among
the combinations with QASCA. In the rest of the paper, we report _Accuracy_ ,
_GenAccuracy_ and _AvgDistance_ of TDH+EAI, DOCS+MB, DOCS+QASCA, LCA+ME and
VOTE+ME only since these combinations are the best or the second-best for each
task assignment algorithm.

Cost efficiency: We plotted the average _Accuracy_ of the tested algorithms
for every 5 rounds in Figure 8. TDH+EAI shows the highest _Accuracy_ for every
round in both datasets. For the _BirthPlaces_ dataset, DOCS+QASCA was the next
best performer which achieved 0.9341 of _Accuracy_ at the 50-th round.
Meanwhile, TDH+EAI only needs 17 rounds of crowdsourcing to achieve the same
_Accuracy_. Thus, TDH+EAI saved 66% of crowdsourcing cost compared to the
second-best performer DOCS+ QASCA. Likewise, TDH+EAI reduced the crowdsourcing
cost 74% in _Heritages_ dataset compared to the next performer. In terms of
_GenAccuracy_ and _AvgDistance_ , TDH+EAI also outperforms all the other
algorithms as plotted in Figure 9 and Figure 10. The results confirm that
TDH+EAI is the most efficient as it achieves the best qualities in terms of
both _Accuracy_ and _GenAccuracy_.

Varying $\pi_{p}$: We plotted the average _Accuracy_ of all algorithms with
varying the probability of correct answer $\pi_{p}$ of simulated workers for
_BirthPlaces_ and _Heritages_ datasets in Figure 11(a) and Figure 11(b),
respectively. As we can easily expect, the accuracies increase with growing
$\pi_{p}$ for most of the algorithms. For both datasets, TDH+EAI achieves the
best accuracy with all values of $\pi_{p}$. In Heritages dataset, a source
provided less than 10 claims on average and it makes difficult for truth
discovery algorithms to estimate the reliabilities of sources. Therefore, the
baseline VOTE+ME shows good performance on Heritages dataset. Meanwhile, the
performance of the state-of-the-art DOCS is significantly degraded on the
Heritages dataset.

(a) _BirthPlaces_

(b) _Heritages_

Figure 11. Varying $\pi_{p}$

(a) _BirthPlaces_

(b) _Heritages_

Figure 12. Execution time per round

(a) _BirthPlaces_

(b) _Heritages_

Figure 13. Execution time for task assignment per round

Execution times: We plotted the average execution times of the tested
algorithms over every round in Figure 12. VOTE, CRH+ME, DOCS+MB and TDH+EAI
run in less than 2.0 seconds per round on average for both datasets. Other
algorithms except for ACCU+ME, POPACCU+ME and LFC+ME also take less than 5
seconds, which is acceptable for crowdsourcing. Since LFC builds the confusion
matrix whose size is the square of the number of candidate values, LFC is the
slowest with _BirthPlaces_ data. On the other hand, for _Heritages_ dataset
which is collected from much more sources than _BirthPlaces_ dataset, ACCU and
POPACCU take longer time for truth inference to calculate the dependencies
between sources.

Effects of the filtering for task assignments: To test the scalability of our
algorithm, we increase the size of both datasets by duplicating the data by
upto 15 times. In Figure 13, with increasing data size, we plotted the
execution times of our task assignment algorithm EAI with and without
exploiting the upper bound proposed in Section 4.3. The filtering technique
saved 78% and 94% of the computation time for the task assignment at the scale
factor 15. The graphs show that the proposed upper bound enables us to scale
for large data effectively. For the total execution time, including the truth
inference, the filtering reduced 21% and 6% of the execution time on
_BirthPlaces_ and _Heritages_ respectively at the scale factor 15.

###  5.5. Crowdsourcing with Human Annotators

We evaluated the performance of the truth discovery algorithm by crowdsourcing
real human annotations. For this experiment, we selected DOCS+QASCA, DOCS+MB
and LCA+ME for comparison with the proposed algorithm TDH+EAI. This is because
they are the best existing algorithms for each task assignment algorithm. We
conducted this experiment with 10 human annotators for 20 rounds on our own
crowdsourcing system. For each worker, we assigned 5 tasks in each round.
Figure 14,15 and 16 show the performances of the algorithms against the
rounds. For both of the datasets, the results confirm that the proposed
TDH+EAI algorithm outperforms the compared algorithms as in the previous
simulations. Without crowdsourcing, the other algorithms show a higher
_GenAccuracy_ than TDH for _Heritages_ dataset, because these algorithms tend
to estimate the truths with more generalized form than TDH does. However,
TDH+EAI shows the highest _GenAccuracy_ after the 3rd round because it
correctly estimates the reliabilities and the generalization levels of the
sources by using the hierarchy. For _BirthPlaces_ dataset, _Accuracies_ of the
algorithms increase a little bit faster than those in the experiment with
simulated crowdsourcing. However, for _Heritages_ dataset, _Accuracies_ of the
algorithms increase much slower than in the experiment with simulated
crowdsourcing. It seems that finding the locations of a world heritages is a
quite harder task than finding the birthplaces of celebrities because the
birthplaces are often big cities (such as LA), which are familiar to workers,
but World Cultural Heritages and World Natural Heritages are often located in
unfamiliar regions.

(a) _BirthPlaces_

(b) _Heritages_

Figure 14. _Accuracy_ with human annotations

(a) _BirthPlaces_

(b) _Heritages_

Figure 15. _GenAccuracy_ with human annotations

(a) _BirthPlaces_

(b) _Heritages_

Figure 16. _AvgDistance_ with human annotations

###  5.6. Crowdsourcing with AMT

We evaluate the performances of TDH+EAI, DOCS+QASCA, DOCS+MB and LCA+ME based
on the answers collected from Amazon Mechanical Turk (AMT). We collected
answers for all objects in _Heritages_ dataset from 20 workers in AMT. We made
the collected answers available at http://kdd.snu.ac.kr/home/datasets/tdh.php.
To evaluate the algorithms based on the collected answers, we assign 5 tasks
for each worker in a round. We plotted the performance of the algorithms in
Figure 17. Since we use more workers than we did in Section 5.5, the
performances improve a little bit faster, but the trends are very similar to
those with 10 human annotators in the previous section. We observe that our
TDH+EAI outperforms all compared algorithms even with a commercial
crowdsourcing platform.

Figure 17. Crowdsourced truth discovery in _Heritages_ Table 5. Performance of truth discovery algorithms |  | Dataset
---|---|---
|  | _BirthPlaces_ | _Heritages_
Algorithm | Precision | Recall | F1 | Precision | Recall | F1
Single truth | TDH | 0.899 | 0.921 | 0.910 | 0.873 | 0.795 | 0.832
VOTE | 0.892 | 0.804 | 0.846 | 0.899 | 0.717 | 0.798
LCA | 0.892 | 0.913 | 0.903 | 0.878 | 0.711 | 0.786
DOCS | 0.892 | 0.913 | 0.902 | 0.887 | 0.722 | 0.796
ASUMS | 0.857 | 0.888 | 0.872 | 0.741 | 0.660 | 0.698
POPACCU | 0.847 | 0.858 | 0.852 | 0.859 | 0.694 | 0.768
LFC | 0.874 | 0.838 | 0.856 | 0.808 | 0.727 | 0.765
MDC | 0.844 | 0.853 | 0.848 | 0.807 | 0.792 | 0.800
ACCU | 0.830 | 0.842 | 0.836 | 0.766 | 0.631 | 0.692
CRH | 0.827 | 0.833 | 0.830 | 0.883 | 0.716 | 0.791
Multi -truths | LFC-MT | 0.763 | 0.723 | 0.742 | 0.898 | 0.684 | 0.777
DART | 0.590 | 0.855 | 0.698 | 0.357 | 0.994 | 0.525
LTM | 0.780 | 0.472 | 0.588 | 0.871 | 0.672 | 0.759
Table 6. Performance evaluation for numerical data | Change rate | Open price | EPS
---|---|---|---
Algorithm | MAE | R/E | MAE | R/E | MAE | R/E
TDH |  0.0006 |  0.1011 |  0.0195 |  0.0354 |  0.0352 |  1.9513
LCA |  0.0006 |  0.1011 |  0.0195 |  0.0354 | 0.3831 | 16.2212
CRH | 0.0020 | 1.6339 |  0.0195 |  0.0354 | 0.0610 | 1.9882
CATD | 0.0104 | 2.3529 | 0.0211 | 0.0395 | 0.0803 | 3.2059
VOTE |  0.0006 |  0.1011 |  0.0195 |  0.0354 | 0.0765 | 2.8402
MEAN | 0.2837 | 30.8747 | 0.4047 | 0.5782 | 0.1762 | 7.3937

###  5.7. Multi-truths Discovery Algorithms

Since there are multiple correct values including generalized values, we also
implement multi-truth discovery algorithms such as DART(Lin and Chen, 2018),
LFC(Raykar et al., 2010) and LTM(Zhao et al., 2012) to compare with our TDH
algorithm. Since the multi-truths discovery algorithms independently generate
the correct values, they may output the true values where there exist a pair
of true values without ancestor-descendant relationship in the hierarchy. For
example, from the given claimed values in Table 1, the multi-truth algorithms
can answer that the ‘Statue of Liberty‘ is located in LA and Liberty island.
In this case, we cannot evaluate the result by our evaluation measures
_Accuracy_ , _GenAccuracy_ and _AvgDistance_. Thus, to evaluate the
performance of the tested algorithms, we utilize precision, recall and
F1-score which are the evaluation measures typically used for multi-truths
discovery. To use the multi-truths algorithms and the evaluation measures, we
treat the ancestors of $v$ and $v$ itself as the multi-truths of $v$. LFC can
work as either a single truth algorithm or a multi-truths algorithm. We refer
to the multi-truth version of LFC as LFC-MT to avoid the confusion.

Table 5 shows the performance of the truth discovery algorithms in terms of
precision, recall and F1-score. For both datasets, the TDH algorithm is the
best in terms of F1-score. Recall that the VOTE algorithm tends to find a
generalized value of the exact truth. Since a generalized truth generates a
small number of multi-truths, the VOTE algorithm shows the highest precision
in _Heritages_ dataset. However, since its recall is much lower than that of
our TDH algorithm, the F1-score of the VOTE algorithm is lower than that of
the TDH algorithm. Similarly, although the DART algorithm has the highest
recall in _Heritages_ dataset, the precision of the DART algorithm is the
smallest among the precisions of all compared algorithms.

###  5.8. Performance on a Numerical Dataset

To evaluate the extension to numerical data, we conducted an experiment on the
stock datatset (Li et al., 2012) which is trading data of 1000 stock symbols
from 55 sources on every work day in July 2011. The detailed description of
the data can be found in (Li et al., 2012). As we discussed at the end of
Section 3.2, we can utilize our TDH algorithm for numeric dataset with implied
hierarchy. We select three attributes ‘change rate’, ‘open price’ and ‘EPS’ of
the dataset, and compared our TDH algorithm with the LCA, CRH, CATD(Li et al.,
2014a), VOTE and MEAN algorithms. Among the second best performers DOCS and
LCA in Table 4, we use only LCA for this experiment since DOCS requires the
domain information while it is not available for this dataset. In addition to
LCA, we implemented and tested the two algorithms CRH(Li et al., 2014b) and
CATD(Li et al., 2014a) which are designed to find the truth in numerical data.
Recall that VOTE is a baseline algorithm which selects the candidate value
collected from majority sources. We also implemented a baseline algorithm,
called MEAN, which estimates the correct value as the average of the claimed
numeric values.

Table 6 shows the mean squared error (MAE) and the relative error (R/E) of the
tested algorithms. The TDH algorithm performs the best for every attribute.
The MEAN and CATD algorithms show worse performance than the other algorithms.
Since they utilize an average or a weighted average of the claimed values,
they are sensitive to outliers. The result confirms that our TDH algorithm is
effective even for numerical data.

##  6\. Related Work

The problem of resolving conflicts from multiple sources (i.e., truth
discovery) has been extensively studied (Demartini et al., 2012; Dong et al.,
2009, 2012; Wan et al., 2016; Raykar et al., 2010; Li et al., 2014b, 2017,
2015; Yin et al., 2008; Zhao and Han, 2012; Zheng et al., 2016; Zhao et al.,
2012; Lin and Chen, 2018; Demartini et al., 2012; Whitehill et al., 2009;
Dawid and Skene, 1979; Zhou et al., 2012; Kim and Ghahramani, 2012). Truth
discovery for categorical data has been addressed in (Demartini et al., 2012;
Dong et al., 2009, 2012; Raykar et al., 2010; Li et al., 2014b; Zheng et al.,
2016; Li et al., 2017; Yin et al., 2008). According to a recent survey (Zheng
et al., 2017), LFC(Raykar et al., 2010) and CRH(Li et al., 2014b) perform the
best in an extensive experiment with the truth discovery algorithms (Zheng et
al., 2017; Li et al., 2014a; Demartini et al., 2012; Whitehill et al., 2009;
Dawid and Skene, 1979; Zhou et al., 2012; Kim and Ghahramani, 2012). There
exist other interesting algorithms (Dong et al., 2009, 2012; Li et al., 2017;
Zheng et al., 2016) which are not evaluated together in (Zheng et al., 2017).
Accu(Dong et al., 2009) and PopAccu(Dong et al., 2012) combine the conflicting
values extracted from different sources for the knowledge fusion (Dong et al.,
2014b). They consider the dependencies between data sources to penalize the
copiers’ claims. DOCS(Zheng et al., 2016) utilizes the domain information to
consider the different levels of worker expertises on various domains. MDC(Li
et al., 2017) is a truth discovery algorithm devised for crowdsourcing-based
medical diagnosis. The works in (Li et al., 2015; Wan et al., 2016; Zhao and
Han, 2012) studied how to resolve conflicts in numerical data from multiple
sources.

The truth discovery algorithms in (Zhao and Han, 2012; Zhao et al., 2012;
Pasternack and Roth, 2013; Zheng et al., 2016) are based on probabilistic
models. Resolving the conflicts in numerical data is addressed in (Zhao and
Han, 2012) and discovering multiple truths for an object is studied in (Zhao
et al., 2012). Probabilistic models for finding a single truth for each object
is proposed in (Pasternack and Roth, 2013; Zheng et al., 2016). However, none
of those algorithms exploit the hierarchical relationships of claimed values
for truth discovery. The work in (Beretta et al., 2016) adopts an existing
algorithm to consider hierarchical relationships.

Task assignment algorithms(Boim et al., 2012; Ho et al., 2013; Zheng et al.,
2015; Mavridis et al., 2016; Zheng et al., 2016; Fan et al., 2015) in
crowdsourcing have been studied widely in recent years. The works in (Boim et
al., 2012; Zheng et al., 2015, 2016) can be applied to our crowdsourced truth
discovery. For task assignment, AskIt(Boim et al., 2012) selects the most
uncertain object for a worker. Meanwhile, the task assignment algorithm in
(Zheng et al., 2016) selects the object which is expected to decrease the
entropy of the confidence the most. QASCA (Zheng et al., 2015) chooses an
object which is likely to most increase the accuracy. Since QASCA outperforms
AskIt in the experiments presented in (Zheng et al., 2015, 2016), we do not
consider AskIt in our experiments. In (Ho et al., 2013), task assignment for
binary classification was investigated but it is not applicable to our problem
to find the correct value among multiple conflicting values. Meanwhile, the
task assignment algorithm is proposed in (Mavridis et al., 2016) for the case
when the required skills for each task and the skill set of every worker is
available. However, it is not applicable to our problem. A task assignment
algorithm proposed in (Fan et al., 2015) assigns every object to a fixed
number of workers. However, since we already have claimed values from sources,
we do not have to assign all objects to workers.

##  7\. Conclusion

In this paper, we first proposed a probabilistic model for truth inference to
utilize the hierarchical structures in claimed values and an inference
algorithm for the model. Furthermore, we proposed an efficient algorithm to
assign the tasks in crowdsourcing platforms. The performance study with real-
life datasets confirms the effectiveness of the proposed algorithms.

###### Acknowledgements.

We appreciate the reviewers for providing their insightful comments. This
research was supported by Next-Generation Information Computing Development
Program through the National Research Foundation of Korea(NRF) funded by the
Ministry of Science, ICT (NRF-2017M3C4A7063570). This research was also
supported by Basic Science Research Program through the National Research
Foundation of Korea(NRF) funded by the Ministry of
Education(NRF-2016R1D1A1A02937186).

## References

  * (1)
  * Auer et al. (2007) Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. 2007\.  Dbpedia: A nucleus for a web of open data.  In _The semantic web_. Springer, 722–735.
  * Beretta et al. (2016) Valentina Beretta, Sébastien Harispe, Sylvie Ranwez, and Isabelle Mougenot. 2016.  How Can Ontologies Give You Clue for Truth-Discovery? An Exploratory Study. In _WIMS_. 15\.
  * Boim et al. (2012) Rubi Boim, Ohad Greenshpan, Tova Milo, Slava Novgorodov, Neoklis Polyzotis, and Wang-Chiew Tan. 2012\.  Asking the right questions in crowd data sourcing. In _ICDE_. 1261–1264.
  * Dawid and Skene (1979) Alexander Philip Dawid and Allan M Skene. 1979.  Maximum likelihood estimation of observer error-rates using the EM algorithm.  _Applied statistics_ (1979), 20–28.
  * Demartini et al. (2012) Gianluca Demartini, Djellel Eddine Difallah, and Philippe Cudré-Mauroux. 2012.  ZenCrowd: leveraging probabilistic reasoning and crowdsourcing techniques for large-scale entity linking. In _WWW_. 469–478.
  * Dong et al. (2014a) Xin Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao, Kevin Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang. 2014a.  Knowledge Vault: A Web-scale Approach to Probabilistic Knowledge Fusion. In _SIGKDD_. 601–610.
  * Dong et al. (2009) Xin Luna Dong, Laure Berti-Equille, and Divesh Srivastava. 2009\.  Integrating conflicting data: the role of source dependence.  _PVLDB_ 2, 1 (2009), 550–561.
  * Dong et al. (2014b) Xin Luna Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Kevin Murphy, Shaohua Sun, and Wei Zhang. 2014b.  From data fusion to knowledge fusion.  _PVLDB_ 7, 10 (2014), 881–892.
  * Dong et al. (2012) Xin Luna Dong, Barna Saha, and Divesh Srivastava. 2012\.  Less is more: Selecting sources wisely for integration. In _PVLDB_ , Vol. 6. 37–48.
  * Dong and Srivastava (2015) Xin Luna Dong and Divesh Srivastava. 2015.  Knowledge curation and knowledge fusion: challenges, models and applications. In _SIGMOD_. 2063–2066.
  * Fan et al. (2015) Ju Fan, Guoliang Li, Beng Chin Ooi, Kian-lee Tan, and Jianhua Feng. 2015.  icrowd: An adaptive crowdsourcing framework. In _SIGMOD_. 1015–1030.
  * Fan et al. (2014) Ju Fan, Meiyu Lu, Beng Chin Ooi, Wang-Chiew Tan, and Meihui Zhang. 2014.  A hybrid machine-crowdsourcing system for matching web tables. In _ICDE_. 976–987.
  * Haas et al. (2015) Daniel Haas, Jiannan Wang, Eugene Wu, and Michael J Franklin. 2015.  Clamshell: Speeding up crowds for low-latency data labeling.  _PVLDB_ 9, 4 (2015), 372–383.
  * Ho et al. (2013) Chien-Ju Ho, Shahin Jabbari, and Jennifer Wortman Vaughan. 2013\.  Adaptive task assignment for crowdsourced classification. In _ICML_. 534–542.
  * Karger et al. (2011) David R Karger, Sewoong Oh, and Devavrat Shah. 2011.  Iterative learning for reliable crowdsourcing systems. In _NIPS_. 1953–1961.
  * Kim and Ghahramani (2012) Hyun-Chul Kim and Zoubin Ghahramani. 2012.  Bayesian classifier combination. In _AISTATS_. 619–627.
  * Kim et al. (2017a) Younghoon Kim, Woohwan Jung, and Kyuseok Shim. 2017a.  Integration of graphs from different data sources using crowdsourcing.  _Information Sciences_ 385 (2017), 438–456.
  * Kim et al. (2017b) Younghoon Kim, Wooyeol Kim, and Kyuseok Shim. 2017b.  Latent ranking analysis using pairwise comparisons in crowdsourcing platforms.  _Inf. Syst._ 65 (2017), 7–21.
  * Lewis and Gale (1994) David D Lewis and William A Gale. 1994.  A sequential algorithm for training text classifiers. In _SIGIR_. 3–12.
  * Li et al. (2016b) Guoliang Li, Jiannan Wang, Yudian Zheng, and Michael J Franklin. 2016b.  Crowdsourced data management: A survey.  _TKDE_ 28, 9 (2016), 2296–2319.
  * Li et al. (2014a) Qi Li, Yaliang Li, Jing Gao, Lu Su, Bo Zhao, Murat Demirbas, Wei Fan, and Jiawei Han. 2014a.  A confidence-aware approach for truth discovery on long-tail data.  _PVLDB_ 8, 4 (2014), 425–436.
  * Li et al. (2014b) Qi Li, Yaliang Li, Jing Gao, Bo Zhao, Wei Fan, and Jiawei Han. 2014b.  Resolving conflicts in heterogeneous data by truth discovery and source reliability estimation. In _SIGMOD_. 1187–1198.
  * Li et al. (2012) Xian Li, Xin Luna Dong, Kenneth Lyons, Weiyi Meng, and Divesh Srivastava. 2012.  Truth finding on the deep web: Is the problem solved?. In _PVLDB_ , Vol. 6. 97–108.
  * Li et al. (2017) Yaliang Li, Nan Du, Chaochun Liu, Yusheng Xie, Wei Fan, Qi Li, Jing Gao, and Huan Sun. 2017.  Reliable Medical Diagnosis from Crowdsourcing: Discover Trustworthy Answers from Non-Experts. In _WSDM_. 253–261.
  * Li et al. (2016a) Yaliang Li, Jing Gao, Chuishi Meng, Qi Li, Lu Su, Bo Zhao, Wei Fan, and Jiawei Han. 2016a.  A Survey on Truth Discovery.  _SIGKDD Explor. Newsl._ 17, 2 (Feb. 2016), 1–16.
  * Li et al. (2015) Yaliang Li, Qi Li, Jing Gao, Lu Su, Bo Zhao, Wei Fan, and Jiawei Han. 2015\.  On the discovery of evolving truth. In _SIGKDD_. 675–684.
  * Lin and Chen (2018) Xueling Lin and Lei Chen. 2018.  Domain-aware multi-truth discovery from conflicting sources.  _PVLDB_ 11, 5 (2018), 635–647.
  * Mavridis et al. (2016) Panagiotis Mavridis, David Gross-Amblard, and Zoltán Miklós. 2016\.  Using hierarchical skills for optimized task assignment in knowledge-intensive crowdsourcing. In _WWW_. 843–853.
  * Pasternack and Roth (2010) Jeff Pasternack and Dan Roth. 2010.  Knowing what to believe (when you already know something). In _COLING_. 877–885.
  * Pasternack and Roth (2013) Jeff Pasternack and Dan Roth. 2013.  Latent Credibility Analysis. In _WWW_. 1009–1020.
  * Raykar et al. (2010) Vikas C Raykar, Shipeng Yu, Linda H Zhao, Gerardo Hermosillo Valadez, Charles Florin, Luca Bogoni, and Linda Moy. 2010.  Learning from crowds.  _JMLR_ 11, Apr (2010), 1297–1322.
  * University (2010) Princeton University. 2010\.  About WordNet.  https://wordnet.princeton.edu/
  * Wan et al. (2016) Mengting Wan, Xiangyu Chen, Lance Kaplan, Jiawei Han, Jing Gao, and Bo Zhao. 2016\.  From Truth Discovery to Trustworthy Opinion Discovery: An Uncertainty-Aware Quantitative Modeling Approach. In _SIGKDD_. 1885–1894.
  * Wang et al. (2012) Jiannan Wang, Tim Kraska, Michael J Franklin, and Jianhua Feng. 2012\.  Crowder: Crowdsourcing entity resolution.  _PVLDB_ 5, 11 (2012), 1483–1494.
  * Whitehill et al. (2009) Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier R Movellan, and Paul L Ruvolo. 2009.  Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. In _NIPS_. 2035–2043.
  * Yin et al. (2008) Xiaoxin Yin, Jiawei Han, and S Yu Philip. 2008.  Truth discovery with multiple conflicting information providers on the web.  _TKDE_ 20, 6 (2008), 796–808.
  * Zhao and Han (2012) Bo Zhao and Jiawei Han. 2012.  A probabilistic model for estimating real-valued truth from conflicting sources. In _QDB_.
  * Zhao et al. (2012) Bo Zhao, Benjamin IP Rubinstein, Jim Gemmell, and Jiawei Han. 2012.  A bayesian approach to discovering truth from conflicting sources for data integration.  _PVLDB_ 5, 6 (2012), 550–561.
  * Zheng et al. (2016) Yudian Zheng, Guoliang Li, and Reynold Cheng. 2016.  DOCS: a domain-aware crowdsourcing system using knowledge bases.  _PVLDB_ 10, 4 (2016), 361–372.
  * Zheng et al. (2017) Yudian Zheng, Guoliang Li, Yuanbing Li, Caihua Shan, and Reynold Cheng. 2017.  Truth inference in crowdsourcing: is the problem solved?  _PVLDB_ 10, 5 (2017), 541–552.
  * Zheng et al. (2015) Yudian Zheng, Jiannan Wang, Guoliang Li, Reynold Cheng, and Jianhua Feng. 2015.  QASCA: A quality-aware task assignment system for crowdsourcing applications. In _SIGMOD_. 1031–1046.
  * Zhou et al. (2012) Denny Zhou, Sumit Basu, Yi Mao, and John C Platt. 2012\.  Learning from the wisdom of crowds by minimax entropy. In _NIPS_. 2195–2203.