Truth-Tracking TD¶

TODO in this document¶

• Review what approaches to truth-tracking have been looked at in JA, belief revision (and argumentation?)

• Write out the goals and research questions for this piece of work, based on the ideas in existing work

  • A key question, not tackled so far to my knowledge, is whether truth-tracking can be achieved in the presence of unreliable sources.

• Develop epistemic framework for TD and a truth-tracking axiom

• Investigate examples of where truth-tracking does and doesn’t hold

Social Choice¶

In binary voting, Condorcet’s Jury Theorem gives an epistemic account of majority voting. 1

The conditions of the theorem are quite strong (certainly for our purposes, assuming each source has reliability greater than 0.5 is unacceptable). Extensions of the theorem with weaker conditions exist; see the discussion and references in [EKM+10] for further reading. A relevant excerpt from that paper is the following:

Interestingly, some extensions of Condorcet’s Jury Theorem show that these strong assumptions can be relaxed without questioning the conclusion. Thus, the theorem still holds when the opinions of the individuals are not independent [8]. And as far as reliability is concerned, it is enough to assume that the mean reliability of the individuals is above 0.5 [10]

Condorcet’s model is generalised in the voting context to \(m > 2\) alternatives by Mallows’s model. In [CPS16] the authors consider two aspects of truth-tracking in Mallows’s model and more general noise models.

Firstly, the authors claim that many voting rules find the correct ranking as the number of voters \(n\) goes to infinity and votes are drawn from Mallows’s model (presumably this is because \(p > 1/2\)). The question of whether a particular rule has this property is therefore uninteresting. They instead look at how quickly the rule finds the truth: how many voters are required to find the true ranking with probability \(1 - \epsilon\), for some small \(\epsilon > 0\). 2 For example, Kemeny’s rule requires the fewest amongst all other rules, and the plurality rule requires a number of voters exponential in the number of alternatives \(m\). Another class of rules generalising Condorcet consistency requires a number of voters logarithmic in \(m / \epsilon\) (this is an asymptotic upper and lower bound).

Secondly, they consider when a voting rule finds the truth in the limit for more general families of noise models, which are parametrised by a metric on the set of rankings. In particular, they look at two classes of voting rule and characterise the metrics for which the rules are guaranteed to find the truth in the limit.

Maybe something along these lines could be helpful for truth-tracking truth discovery. We could generalise the probabilistic model to account for untrustworthy or adversarial sources (i.e. allow different reliability rates \(p_s \in [0,1]\) for each source in Mallows’s model), and instead of ‘how many voters?’, ask ‘how much trustworthiness?’ is required to find the truth within some margin of error. Maybe this could be the number or proportion of untrustworthy sources, or some aggregation of error rates across sources. Maybe this idea could be developed for a fixed number of sources. Alternatively, we could ask which conditions must be placed on the \(p_s\) values in order for it to be possible to find the truth in the limit.

Judgment Aggregation¶

In [HS12] a very demanding truth-tracking postulate is given for JA: for a profile of judgment sets \(x\), if \(w\) is the true world, then \(f(x) = w\). This seems to be of little use practically; there can be no hope of \(f(x)=w\) without requiring some conditions on \(x\) at the very least (e.g. the agents should be reliable).

For a more reasonable goal, the authors introduce a relative notion of truth-tracking: in the context of some probabilistic model and given a profile \(x\), \(f\) tracks the truth better than \(f'\) if

for each possible world \(w\), and with inequality for at least one \(w\).

The authors go on to define a suitable probabilistic model. This amounts to defining the prior probability \(P(w)\) that \(w\) is the true world, and the probabilities \(P(x_i^{(j)} = \top \mid w)\), \(P(x_i^{(j)} = \perp \mid w)\) for the individual judgements from agents. 3

Results include the fact that the truth-tracking abilities of a certain class of aggregation procedures are independent of the prior probabilities \(P(w)\), and that procedures of this class are optimal with respect to the relative measure of truth-tracking if it is assumed each agent has reliability \(p > 0.5\) (c.f. Condorcet).

Belief Revision and Belief Merging¶

[BGS19] looks at truth-tracking by iterated belief revision. The idea is that iterated belief revision applied to a sequence of incoming information can be seen as an agent learning about the world; this learning is successful if the agent’s beliefs converge to the truth.

For this, the authors consider sound and complete information streams, where each piece of information is true (soundness) and every truth is included in the stream (completeness). This is quite a strict condition, which is relaxed a bit later in the paper. Note that soundness and completeness are with respect to a ‘true’ state of the world.

A method learns the truth if for any state of the world \(w\) and any stream which is sound and complete for \(w\), the method outputs \(\{w\}\) as the possible worlds after finitely many steps. The authors focus on methods which can learn any world which is learnable (meaning there is some method which can learn it).

[EKM+10] looks at truth tracking for belief merging. They adopt a probabilistic framework, where different reliability measures for agents are proposed based on the probability of an agent being ‘correct’ (see the paper for the specifics). They have an extension of the Jury Theorem for belief merging, which shows that voting on worlds singles out the true world with probability 1 in the limit as the number of agents increases (under some conditions on the agents).

The truth-tracking postulate is similar to the theorem: a merging operator \(\Delta\) is truth-tracking if, under the conditions on the agents, the probability that the true world is singled out as the unique model of \(\Delta(E_n)\) is 1 in the limit.

Note that for the belief revision case, the input data is assumed to be absolutely correct (the sound and completeness properties) for the true world, i.e. no probabilities are involved. In the belief merging case, the probabilistic conditions on the reliability of agents ensures (with limiting probability 1) that the input data is correct for the true world. These are different approaches but basically achieve the same thing: if the revision/merging operator receives input which looks like the real world, it should be able to (uniquely) find the real world.

A problem with this for the TD case is that there might be input data which looks like multiple distinct worlds. For example, consider two worlds in which all sources are completely unreliable (i.e. choose facts randomly) but which have different true facts; then any network with source claims sampled randomly looks like both worlds.

Another merging-based account is [Cev14]. This paper makes the distinction between truth-tracking and truth-approximation: truth-tracking aims to find when an operator can eventually identify the whole true state of the world (under some assumptions on agent reliability), whereas truth approximation asks whether the merged beliefs of agents is closer to the truth than each agent’s individual beliefs. Note that TT involves some kind of limit (usually number of agents going to infinity), whereas TA just involves an isolated set of inputs from finitely many agents.

In the TD case it might be unreasonable to expect that TA is achieved, since we may have unreliable sources. Indeed, we can expect that the uncertainty coming from unreliable sources will ‘drag down’ the quality of the input data, and the merged beliefs may be further from the truth than some of the reliable sources. However, the idea of looking at the distance of merged beliefs to the true world is interesting and can be applied to TD.

Mainstream TD¶

Broadly speaking, the popular data mining TD methods of today are MLE and optimisation. Optimisation-based methods (e.g. [DGX16][LLG+16]) may be particularly susceptible to ‘consensus discovery’ rather than truth discovery. For example, the algorithm in [LLG+16] keeps track of source weights and estimated truths; weights are assigned so as to minimise the weighted sum of the differences between source claims and estimated truths. The incentive here is to find cliques of sources who agree with each other, and assign these sources high weight (and low weight to others). Thus it may be the case that such algorithms find the ‘maximal’ consensus among sources and facts.

It would be interesting to look at such algorithms in a truth-tracking framework for truth discovery, to see whether the non-consideration of truth is really an issue. Maybe consensus finding is actually the best one can do in the fully unsupervised case?

The MLE-based approaches (e.g. [WKLA12][XGW+16]) are more promising from the truth-tracking point of view. Roughly, they construct a probability distribution over worlds \(w\) and TD networks \(N\), where source reliability scores form the parameters \(\theta\) of the model. The aim is to find, given a TD network \(N\), the parameters and world which maximise \(P(N \mid w, \theta)\). That is, they maximise the probability that we would observe network \(N\) given the true world is \(w\) and true parameters are \(\theta\).

In [XGW+16] the similarity with truth-tracking is even stronger. They give some theoretical results which show that for sufficiently many sources (and under some conditions on the input) the distance between their algorithm’s output and the truth is ‘small’ with high probability. This is very similar to the truth-tracking postulate in [EKM+10]. However their result is very technical and limited to their (highly specific) model of truth discovery.

Formulation 1¶

Idea: If in the limit the input data matches the real world \(w\), the operator finds \(w\) (c.f. [BGS19]).

The question of when input ‘matches’ a world is not trivial in our TD model (compared to propositional logic formulations in belief revision/merging), since in general we do not label sources strictly trustworthy or untrustworthy, but allow a continuum of trust values. This means that i) most worlds will not have any networks perfectly matching them (e.g. consider all sources are unreliable and choose facts at random), and ii) a network may equally well match several similar worlds.

The first point suggests we should have a measure of compatibility between worlds and networks which takes a continuum of values, not just true vs false. This is addressed in the following definition.

Now we address the issue of when a world matches a sequence of inputs in the limit.

That is, \(X\) approximating \(w\) means that (in the limit) the network \(N_k\) is maximally compatible with the true world being \(w\). Note that \(X\) may approximate multiple distinct worlds; in this case the worlds are indistinguishable from the point of view of \(X\) given the compatibility measure \(\varphi\).

The truth-tracking postulate can now be stated: an operator should, in the limit, find the world which the input sequence \(X=(N_k)_{k \in \Nat}\) approximates (if such a world is unique).

Note that this axiom says nothing in cases where \(|\mathcal{A}_\varphi(X)|>1\).

Formulation 2¶

Idea: \(T(N)\) is closer to the true world than each source’s beliefs are. That is, \(T\) provides an improvement over the individual source inputs (either absolutely or on average). C.f. [Cev14]. According to their terminology, this is more like truth approximation than truth tracking. For this formulation, we assume \(\S, \F\) and \(\O\) are finite.

The missing ingredients are:

• A distance measure \(d\) between \(T(N)\) and worlds \(w\).

• A distance measure \(d'_N\) between source and worlds \(w\), with respect to a network \(N\).

Options for \(d\) include:

• \(\ell_p\) distance: for \(p>0\), writing \(g = T(N)\),

  \[d(g, w) = \left(\sum_{z \in \S \cup \F}{\left|g(z) - w(z)\right|^p} \right)^{\frac{1}{p}}\]

  This assumes \(\V \subseteq \R\).

• The number of objects which \(T\) selects a false fact. Specifically, enumerate \(\O=\{o_1,\ldots,o_n\}\) and for a function \(g: \S \cup \F \to \V\), write \(v_g = (f_1,\ldots,f_n)\) where \(f_i = \text{argmax}_{f \in \obj^{-1}(o_i)}{g(f)}\). Then we can set \(d(g, w) = d_H(v_g, v_w)\) where \(d_H\) denotes Hamming distance.

For \(d'_N\), we could apply a similar Hamming distance idea: look at the number of objects where \(s\) claims a fact in \(f \in \obj^{-1}(o)\) which has \(w(f) = 0\).

The truth tracking/approximation axiom will put an upper bound on \(d(T(N), w)\) in terms of the \(d'_N(s, w)\).

Examples for \(G\) include taking the minimum (\(T(N)\) must be at least as close to the truth as each source’s claims) or mean (\(T(N)\) must be at least as good as the ‘average source’).

Formulation 3¶

Idea: if \(N\) is more compatible with \(w'\) than \(w\), then \(T(N)\) is closer to \(w'\) than it is to \(w\).

Intuitively, this axiom says that \(T(N)\) should be close worlds that are highly compatible with \(N\). Thus it seems an obvious choice is to take \(T(N) \in \text{argmax}_{w \in \W}{\phi_w(N)}\); then \(T(N)\) corresponds exactly to the (one of the) maximally compatible worlds.

I think there is probably some simple property linking \(\phi\) and \(d\) which guarantees this argmax operator satisfies the axiom, but I cannot figure it out.

Formulation 4¶

Idea: take a simpler view on the possible worlds and constraint the compatibility function \(\phi\) to just 0 or 1. Note that in some sense this goes against the motivation behind Formulation 1.

Write \(\mathcal{Z} = \V^{\S \cup \F}\) for the set of TD operator outputs (so that an operator is a mapping \(\N \to \mathcal{Z}\)).

Note that \(\W\) here is not fixed (i.e. we are not using the definition of possible worlds given before formulation 1).

Intuitively, \(w \vDash N\) means that \(N\) is compatible with the true world being \(w\) (c.f. \(\phi_w(N) = 1\) in formulation 1). Write \([N] = \{w \in \W : w \vDash N\}\).

Consider a fixed epistemic model \(\tuple{\W, \vDash, e}\). Given an operator \(T\), a network \(N\) and a distance measure \(d: \mathcal{Z}^2 \to \R_{\ge 0}\), we can define a total preorder \(\preccurlyeq_N^T\) on \(\W\) by

Then \(\min(\W, \preccurlyeq_N^T)\) is the set of worlds ‘closest’ (via the embedding \(e\)) to the output of \(T\). We can consider these to be the worlds which \(T\) picks out as the ‘best’ (e.g. most probable). The fact that there may be several minimal worlds represents the uncertainty as to which one is actually the unique true one.

Two natural properties \(T\) may satisfy (for a given \(N\)) are the following:

(S) is a sort of ‘soundness’: every world which \(T\) finds is indeed a model of \(N\). (C) is a sort of ‘completeness’: every model of \(N\) is found by \(T\).

Problems with formulation 4¶

I think the idea behind this formulation and the complementary (S) and (C) properties are quite nice, but it seems difficult to work with in practice.

More importantly, care needs to be taken to ensure that \(d(e(w), T(N))\) is actually meaningful; otherwise \(\min(\W, \preccurlyeq_N^T)\) might not really be a good representations of the likely worlds from the point of view of \(T\).

For example, consider the epistemic model of the example above, and consider the network \(N\) of Figure 1.

Figure 1¶

Consider an operator \(T\) with \(T_N(h)=1\) and which assigns a score of 0.5 to all other nodes, for this seems like a sensible output for the network in question.

We have

\[\W = \{\tuple{\emptyset, fh} ,\tuple{\emptyset, gh} ,\tuple{s, fh} ,\tuple{s, gh} ,\tuple{t, fh} ,\tuple{t, gh} ,\tuple{st, fh} ,\tuple{st, gh} \} \]

\[[N] = \{\tuple{\emptyset, fh} ,\tuple{\emptyset, gh} ,\tuple{s, fh} ,\tuple{t, gh} \} \]

Using the \(\ell_p\) distance \(d(\alpha, \beta) = \left(\sum_{z \in \S \cup \F}{|\alpha(z) - \beta(z)|^p}\right)^{\frac{1}{p}}\) – which seems natural for a distance measure between functions – we have \(d(e(w), T(N)) = 2^{\frac{2}{p} - 1}\) for all \(w \in \W\). In particular, \(\min(\W, \preccurlyeq_N^T)=\W\), so ‘completeness’ (C) is trivially satisfied, and ‘soundness’ (S) is not.

Since the distance between (embeddings of) worlds and \(T(N)\) is constant, the notion is mostly useless. We might need a more sophisticated way to measure which set of worlds \(T(N)\) represents.

Alternatively, we could ditch the distance measure \(d\) and consider replacing \(\min(\W, \preccurlyeq_N^T)\) with a set of worlds \(R(T(N)) \subseteq \W\) – i.e. have a function \(R: \mathcal{Z} \to 2^\W\) which gives the set of worlds which \(T(N)\) best represents. The distance-based approach above is a special case of this, but there may be other choices of \(R\) which are more appropriate.

Other ideas¶

• If the agents have some particular properties (e.g. independence, reliability) which make the input look like the real world, the operator finds it (Condorcet, belief merging). This seems harder to generalise to TD, since we need to account for unreliable sources.

1

Note that this is the actual majority rule, which chooses the alternative with a strict majority. It is distinct from the plurality rule (which I previously called majority) in general, although the two conicide when only two alternatives are available.

2

Their voting rules are randomised, i.e. for each input profile they return a probability distribution over rankings.

3

Here \(x_i\) denotes the judgement set of the \(i\)-th agent, and \(x_i^{(j)}\) denotes the judgement of the \(i\)-th agent on the \(j\)-th proposition in the agenda.

4

The framework could be generalised a bit to make the single trustworthiness value less restrictive; e.g. if trust scores are values in \(\V'\) which is only partially ordered. Then incomparable elements of \(\V'\) could represent trustworthiness/reliability on different topics.

5

Here we assume \(\{0, 1\} \subseteq \V\).

6

Note that the totally-ordered set \(\V\) is used elsewhere for assessments of trust and belief, but \([0, 1]\) is chosen here for simplicity.

7

Here we speak of the pointwise limit a sequence of functions. This is defined as follows: a sequence \((g_k)_{k \in \Nat}\) of functions from a common domain \(D\) into \(\V\) converges pointwise to \(G: D \to \V\) iff for every \(x \in D\) we have \(\lim_{k \to \infty}{g_k(x)} = G(x)\).

In turn, this relies on taking the limit of the \(\V\)-valued sequence \((g_k(x))_{k \in \Nat}\). This can be defined in the usual way if \(\V\) is a bounded metric space for some distance function \(d: \V \times \V \to \mathbb{R}_{\ge 0}\). In most cases we will take \(\V \subseteq \mathbb{R}\) bounded, anyway…

8

Note that this could be worse than the case of malicious sources, who always claim false facts. In this case we at least know that the claims are false, whereas for random guessers no information is gained.

9

Here we enumerate \(\S = \{s_1,\ldots,s_m\}\).