Mainstream Truth Discovery Papers¶

Summary:

• Another optimisation-based truth discovery algorithm. The authors find motivation from a student/question situation: students of varying ability levels answer questions.

• As usual, the goal is to jointly estimate the ability of students and the true answers to questions. I do not fully understand this setting: presumably whoever set the questions already knows the true answers…

• Sources are split into two groups: authoritative and ordinary. The idea is that authoritative sources are better than ordinary ones, so it’s leaning closer to semi-supervised truth discovery (where claims for authoritative sources act as ground truths).

Framework:

• Terminology: objects (questions), sources (students) and observations (answers given by students)

• Notation: \(N\) objects, \(P\) ‘ordinary’ sources and \(Q\) ‘authoritative’ sources.

  • The observation from the \(p\)-th ordinary source on the \(n\)-th object is \(o_n^p\); the observation from the \(q\)-th authoritative source is \(a_n^q\). Source weights are denoted \(w_p\) and \(r_q\). Estimated truths are denoted \(t_n\).

• Optimisation model: basically the same as [LLG+16] and many other papers… A difference is that a factor \(\lambda > 0\) is applied to the sum of weighted distances of observations from ordinary sources. This controls the importance of the authoritative sources.

Experimental evaluation:

• An education dataset (online multiple-choice Japanese exam from the university of the authors), and a crowdsourced dataset from a “Who Wants to be a Millionaire” Android app. Doesn’t seem that these datasets are available anywhere (no mention in the paper, at least).

• Authors show that their algorithm has lowest error rate on these datasets compared to a number of baselines.

Criticisms:

• Very similar to other work I have seen…

• How did the authors split the sources into ‘authoritative’ and ‘ordinary’ in their experiments? Seems to rely on some prior knowledge of the dataset.

• More generally, the splitting of sources seems to only amount to multiplying the weights of authoritative sources by \(\lambda\). It’s not clear to me how this differs at all from CRH from Li et. al…

(Doesn’t describe itself as Truth Discovery, but in terms of the categorisation on this page I consider it close enough…)

Summary:

• System does the following: given a textual claim, determine its credibility and give explanation for this verdict

• Credibility is affected by

  • Language used

  • Reliability of sources which support/refute the claim

  • Temporal aspects of how claims spread across the web

Preliminaries

• Set \(C\) of claims

• Set \(WS\) of (web) sources

• Set of articles \(A^t\) for each timestamp \(t\)

• \(a_{ij}^t\) is the article from \(ws_j\) at time \(t\) which supports/refutes claim \(c_i\)

• Binary random variables \(y_i^t, y_{ij}^t \in \{T,F\}\) represent the credibility of claim \(c_i\) and the credibility of \(a_{ij}\) at the \(t\), respectively. \(y_i^t\) is supposed to be aggregation of the \(y_{ij}^t\)

• Problem statement:

  • Given the values of a subset of the \(y_{i}^t\), predict \(y_1^t\) for each timestep \(t\) (wlog I’m assuming that \(c_1\) is the claim being assessed)

Credibility assessment

• Lists some linguistic features and how they affect credibility assessment (e.g. “may” softens the degree of commitment to a proposition)

• Authors introduce an algorithm to calculate support and refutation scores for each article and claim:

  • Generate ‘snippets’ of the article: all subsequences of up to four consecutive sentences long

  • For each snippet \(s\), compute the ‘unigram and bigram overlap’ score \(o_s\) (this is not explained in any detail); discard snippets whose percentage snippet is below a fixed threshold

  • Calculate the stance of each snippet using logistic regression, trained on data from popular fact-checking sites (I don’t have the background to really understand this step). This gives support and refute probabilities \(p_s^+, p_s^-\)

  • Order the snippets according to \(\max\{p_s^+ \cdot o_s, p_s^- \cdot o_s\}\)

  • Select the top \(k\) snippets (these will later be used for the evidence) and return the averages of \(p_s^+\) and \(p_s^-\)

• Source reliability is computed wrt a labelling of the credibility of claims:

  • Take number of articles from \(ws_j\) which supports a true claim

  • Add the number of articles which refute a false claim

  • Divide by total number of articles from \(ws_j\)

  • C.f. ‘proportion’ operator in question-answering with abstentions…

  • I don’t quite understand what the authors do here: in the previous section an article has support and refutation scores, not an absolute status

Summary:

• FaitCrowd: Fine Grained Crowdsourced data aggregation

• Challenges the widespread TD assumption that source reliability is uniform across objects (‘tasks’ in the crowdsourcing parlance)

  • A source might be an expert (high reliability) in one area, but useless in another (low reliability)

  • (I seem to recall this issue also being discussed in Pasternack’s thesis)

  • Instead, need topic-aware reliability measures

• Automatically learns topics, reliability levels and true answers

Formulation:

• Input:

  • Set of questions \(\mathcal{Q}\)

  • Sources \(\mathcal{U}\)

  • Answers \(\mathcal{A} = \{a_{qu} : q \in \mathcal{Q}, u \in \mathcal{U}\}\)

  • Each question \(q\) has \(M_q\) words

  • The number of topics \(K\) (note: questions are not assigned a topic in the input)

• Output:

  • Estimated truth \(t_q\) for each question \(q\) (note: they use the term trustworthy answers)

  • Topic \(z_q\) for each question \(q\)

  • Topical expertise matrix \(e \in \R^{K \times U}\), i.e. reliability score for each source for each topic

• Model:

  • Complex statistical model which I do not understand

  • Iterative algorithm

Summary:

• Widely cited MLE-based TD method. I think it is actually the first MLE TD paper

• Reliability of a source is the probability that they report correct observations

• Just looks at binary measurements

• Provides optimal procedure (in the MLE sense) for truth discovery

Preliminaries:

• \(M\) sources \(S_1,\ldots,S_M\) and \(N\) variables \(C_1,\ldots,C_N\) each with two possible values: true or false

• \(S_iC_j\) denotes that source \(i\) claims \(C_j\) is true. Note that sources never claim variables are false: this is the default position in the absence of \(S_iC_j\)

• \(P(C^t_j)\) and \(P(C^f_j)\) denote the probability that \(C_j\) is true or false respectively [isn’t it the case that \(P(C^f_j)=1-P(C^t_j)\)?]

• \(s_i\) is the probability that \(S_i\) will claim a variable is true. The reliability \(t_i\) is the probability that \(S_i\) makes the correct observation: \(t_i = P(C^t_j \mid S_iC_j)\)

• Some other notions defined…

Expectation maximisation

• Rough outline is as follows…

• We have an observed dataset \(X\), latent variables \(Z\) and parameters \(\theta\)

• The likelihood function is \(L(\theta; X, Z) = P(X, Z \mid \theta) = \sum_{Z}P(X \mid \theta, Z)\)

• That is, the probability the we would observe \(X\) and latent variables \(Z\) if the parameters of the model were \(\theta\)

• In the TD case \(X\) is the TD dataset, represented as a binary source-claims matrix. The latent variable \(Z\) consists of the truth status of each variable. The parameters \(\theta\) include reliability of sources and background bias \(d\) (i.e. \(d\) is the probability that a variable is true generally).

• EM algorithm is iterative:

  • Initialise an estimate for \(\theta^{(1)}\)

  • While convergence criteria not satisfied:

    • (E step): Define \(Q(\theta \mid \theta^{(t)}) = E_{Z \mid X, \theta^{(t)}}[\log{L(\theta; X, Z)}]\). That is, we look at the expected value of the log-likelihood, taken with respect to the probability distribution over \(Z\) conditioned on the observed data \(X\) and the current estimated parameters \(\theta^{(t)}\).

    • (M step): Set \(\theta^{(t+1)} = \text{argmax}_{\theta}{Q(\theta \mid \theta^{(t)})}\).

• Applied to this TD model, the authors obtain an explicit form for \(Q\) and the argmax, leading to a simple iterative algorithm

Evaluation:

• The algorithm is compared against others in the literature on simulated data with respect to various metrics

• Also runs the algorithm on a real world dataset from Twitter

Source claims are given as vectors \(\{p_1,\ldots,p_n\}\subseteq \R^d\) (i.e. there are \(n\) sources, \(d\) objects and facts are real-valued).

• This seems to require that a source makes a claim for every object, which seems weird…

Formulates truth discovery as an optimisation problem: find source reliability weights \(w_1,\ldots,w_n\) and the truth vector \(p^*\) which minimise \(\sum_{i=1}^n{w_i \|p_i - p^*\|^2}\) subject to the normalisation constraint \(\sum_{i=1}^n{e^{-w_i}} = 1\).

• Some justification is given for the exponential normalisation function. Firstly, it prevents one from taking \(w_1=1\), say, and \(w_i=0\) for \(i > 1\). I do not understand the other reasons, but it is linked with entropy…

Finds an equivalent formulation of the optimisation problem, which is non-convex in general

Provides (pretty complicated) approximate algorithms for the optimisation problem

Very opinionated view of truth discovery. They define truth discovery as their particular optimisation problem, and for this problem there is a fixed link between the source weights and truth vector, so that it is enough to find just one of them (I think)..

Seems to assume the optimal vector \(p^*\) exists without justification, unless I’m reading it wrong… Furthermore there are two algorithms presented for two different cases, but knowing which case to apply seems to rely on already knowing \(p^*\).

Seems to be very much an extension of the above paper

TODO: finish reading

Addresses a crowdsourcing quality problem

• Closely related to TD, but the references are in crowdsourcing and seems disjoint from the TD literature

Goal is to identify characteristics of crowdsourcing workers (e.g. education level), and, for a given task, identify groups of workers whose characteristics mean they are likely to provide high-quality data. These groups are then targeted for future tasks.

Three stages…

Probing stage:

• Worker characteristics are gather from the workers’ profile (e.g. age, location – the available data is platform-specific) or by a questionnaire

• Part of the task is sent to all workers

Discovery stage:

• From the probing stage, work out if there are groups of workers whose data is of high ‘quality’

• This is the step related to TD

Targeting stage:

• Send the rest of the task to the high-quality workers

Talks about EM for the ‘TD’ part, but I don’t think TD plays a role in their algorithms

Uses statistics beyond my level, so I have not read the technical parts in detail

A note on terminology: speaks of reliability of sources and trustworthiness of information

• “Trust” is referring to the data, rather than sources! This is the other way around to our framework

Deals with the “long-tail phenomenon”:

• Most sources only provide a few claims (“small sources”) and only a few sources make plenty of claims

• Number of claims per source roughly follows a power law distribution in example datasets: something like \(y(x)=ax^{-b}\) where \(y(x)\) is the number of sources making \(x\) claims. That is, a small number of sources make a large number of claims

• Aims to discount the effect of small sources while still taking them into consideration (ignoring them is not possible since the claims from small sources can form a significant portion of the dataset)

Gives confidence interval of reliability estimation, not just number

Formalism:

• We have a set of entities \(\mathcal{N}\) (i.e. objects), sources \(\mathcal{S}\), and claims \(\mathcal{C}\)

• Each claim is of the form \((n, s, x_n^s)\) for \(n \in \mathcal{N}\), \(s \in \mathcal{S}\). That is, source \(s\) claims that \(x_n^s\) is the true value for entity \(n\)

• Output of TD is an estimated truth for each entity: \(\mathcal{X}=\{(n, x_n^*) : n \in \mathcal{N}\}\)

• Note that sources weights are not considered to be part of the output, and are only used ‘internally’ to calculate the \(x_n^*\)

TD model:

• Each source has an error distribution \(\epsilon_s\). The idea is that when making a claim, a source draws an error level \(e\) from this distribution and makes a claim \(e\) away from the truth

• Error distributions are assumed to be normal with mean 0 (this means that sources do not have a tendency to be wrong on purpose, an assumption which may not always hold!)

• Source reliability is inversely proportional to the variance of the error distribution \(\sigma_s^2\)

• Combined error is \(\epsilon_{\text{combined}} = \sum_{s \in \mathcal{S}}{w_s \epsilon_s}\) for some weights \(w_s \in [0, 1]\) with all weights summing to 1

• Aim is to choose weights to minimise the variance of the combined error. This can be expressed in terms of the \(\sigma_s^2\) (which are unknown)

• Problem is formulated as an optimisation problem: find weights, estimate variances to minimise (estimated) variance of \(\epsilon_\text{combined}\)

• (The objective function is modified a bit as they go into details, but above is the gist of it…)

Algorithm:

• A closed-form solution for the optimisation problem is found

• “Initial truths” are calculated through averaging or voting

• Initial source weights are calculated (according to the optimisation problem solution) from initial truths and some probabilistic component relating to the number of claims made

• Truths are updated as a weighted sum of claims

• Repeat until stopping criterion

Experiments:

• Authors obtained datasets with ground truths

• For continuous data, they confirm experimentally that source errors follow a normal distribution

• They show improvement over other TD methods

Aims to develop a TD algorithm for unstructured raw text data

Model (note: I have modified some notation to make it a bit more sane):

• Set of questions \(\mathcal{Q}\)

• Set of users \(\mathcal{U}\)

• Set of answers \(\mathcal{A} = \{a_q^u : q \in \mathcal{Q}, u \in \mathcal{U}\}\)

• Answers take the form of unstructured text

  • I guess users can abstain from a question by providing an empty string…

Approach:

• Preprocessing: split answers into keywords, remove stopwords, and canonicalise synonyms

• For each question \(q\), let \(\mathscr{V}_q\) be set of all such keywords across all users

• Finding the truth amounts to finding a subset \(V_q^* \subseteq \mathscr{V}_q\) of ‘true’ keywords

• An optimisation problem is formed, which seems similar to CRH.

• They aim to solve the optimisation problem using ant colony optimisation.

  • An ant network is formed for each question. The keywords in \(\mathscr{V}_q\) form the edges (?). What the nodes represent is not explained very clearly.

  • This section is not laid out very well, considering it’s the main contribution of the approach

Summary:

• The paper is very poorly written

• The ‘unstructured text’ contribution is just a preprocessing step which converts text into a bag of keywords… from then on it’s just a standard optimisation TD problem solved using

• I only read it because it mentioned any colony, expecting something cool…

The original TD paper

See notes on TD formulation page: Truth Discovery with Multiple Conflicting Information Providers on the Web (2008).

Truth discovery where a subset of facts are ground truths which are known to be true.

See notes on TD formulation page: Semi-supervised Truth Discovery (2011).

Summary:

• True information often changes over time (contact details, addresses, restaurants and close over time…)

• Data sources make copy from one another

• Copying form unreliable sources results in the propagation of misinformation

• To copy or not to copy is not a dichotomy: sources may copy at times and act independently at others

• All together, this papers aims to look at source claims over time and determine:

  • The evolving truths

  • The evolving copying relationship between sources

Problem formulation

• Set of objects \(\mathcal{O}\), sources \(\mathcal{S}\)

• An object \(O\) has an associated life span \(\langle (t_1,v_1),\ldots,(t_l, v_l)\rangle\) which describes the true value \(v_i\) at transition time \(t_i\) as this true value evolves

• \(\bar{U}(S, t_i)\) denotes the updates source \(S\) provides in the time period \((t_{i-1}, t_i]\)

Slices:

• Consider an object \(O\) and source \(S\). Look at all the time points where either the true value for \(O\) changes, or where \(S\) provides an update on \(O\); the disjoint time intervals formed from these points are called slices

• A slice is captured if it ends with \(S\) updating to the true value; it is capturable if \(S\) provided an incorrect value at the start of the slice

• Similarly, a slice is miscaptured if it ends with \(S\) updating to the wrong value; it is miscapturable if it is possible for \(S\) to update to the wrong value (always possible when there are more than two possible values for \(O\))

Source quality measures:

• Coverage: The coverage of \(S\) is the proportion of capturable slices which \(S\) captures (across all objects)

• Exactness: \(E(S)\) is 1 minus the proportion of miscapturable slices which are miscaptured.

• Freshsness: For \(\Delta \ge 0\), \(F(S, \Delta)\) is the proportion of captured slices which have length no greater than \(\Delta\) (i.e. instances where \(S\) updated to the correctly value less than \(\Delta\) time after the true value changed)

Copying model:

• Uses a Hidden Markov Model

• Fix two sources \(S_1\), \(S_2\). The Markov states are

  • \(I\): represents that the sources are indepenent

  • \(C1_c\): represents that \(S_1\) is a copier of \(S_2\), and is actively copying at the current time

  • \(C1_{\neg c}\): represents that \(S_1\) is a copier of \(S_2\) but is not actively copying

  • \(C2_c, C2_{\neg c}\) defined similarly

• Transition probabilities are detailed; they depend on three parameters

  • \(f\): probability that a copier actively copies at any particular time

  • \(t_c\): probability that a copier remains a copier

  • \(t_i\): probability that independent sources remain independent

• Later on this model is extended to consider copying relations over time by adding states for each timestamp…

Summary of the rest (skimmed):

• The whole model is very large and complex

• Final algorithm is iterative:

  • Compute CEF measure of sources based on estimated object lifespans

  • Use HMM somehow to work out copying relationships (?)

  • Use this to work out estimated object lifespans

  • Repeat until lifespans converge

Summary:

• Statistical method

• Can make use of ground truth

• Can make use of “domain-specific features”: additional properties of sources (unrelated to their reports) which may provide a signal of their reliability

• “True” source accuracy is modelled as the log odds of the probability the source provides a correct value (look like this is constant for all objects)

• Parameters to optimise over are a vector of source weights \({\langle}w_s{\rangle}_{s \in S}\) and feature weights \({\langle}w_k{\rangle}_{k \in K}\); these are combined to give an estimate of the source accuracy.

• If enough ground truth is available, parameters are learned by empirical risk minimisation: maximise likelihood by looking just at ground truth objects, then take most likely value for non-ground-truth objects

• Otherwise, EM is used

• Authors give theoretical results giving guarantees on the algorithm’s accuracy wrt finding true values and finding true source accuracies

• Theoretical results require quite strong assumptions on source accuracies, but authors (claim to) show empirically that the method performs well without these assumptions