\[\gdef{\S}{\mathcal{S}} % Note: overrides existing command \gdef{\O}{\mathcal{O}} % Note: overrides existing command \gdef{\F}{\mathcal{F}} \gdef{\N}{\mathcal{N}} \gdef{\R}{\mathbb{R}} \gdef{\Nat}{\mathbb{N}} \gdef{\sign}{sign} \gdef{\L}{\mathcal{L}} \gdef{\C}{\mathcal{C}} \gdef{\V}{\mathcal{V}} \gdef{\W}{\mathcal{W}} \gdef{\G}{\mathcal{G}} \gdef{\vle}{\preceq} % Source and fact orderings \gdef{\sle}{\sqsubseteq} \gdef{\slt}{\sqsubset} \gdef{\sge}{\ge} \gdef{\seq}{\simeq} \gdef{\fle}{\preceq} \gdef{\flt}{\prec} \gdef{\fgt}{\succ} \gdef{\fge}{\succeq} \gdef{\feq}{\approx} \gdef{\src}{\mathsf{src}} \gdef{\facts}{\mathsf{facts}} \gdef{\obj}{\mathsf{obj}} \gdef{\mut}{\mathsf{mut}} \gdef{\orderings}{\mathcal{L}} \gdef{\num}{\mathcal{T}_{Num}} \gdef{\rec}{\mathsf{rec}} \gdef{\norm}{\mathsf{norm}} \gdef{\ord}#1{\langle{#1}\rangle} % Shortcuts \gdef{\limn}{\lim_{n \to \infty}} \gdef{\voting}{\emph{Voting}} \gdef{\sums}{\emph{Sums}} \gdef{\usums}{\emph{UnboundedSums}} \gdef{\avlog}{\emph{Average$\cdot$Log}} \gdef{\scvoting}{\emph{SC-Voting}} \gdef{\scoh}{\mathrel{\lhd}} \gdef{\fcoh}{\mathrel{\blacktriangleleft}} \gdef{\tuple}#1{{\langle{#1}\rangle}}\]

Ideas for next papers¶

Ideas for extensions or new directions which are compatible with the existing framework we have, and which can be tackled reasonably soon.

Journal version of the axiomatic approach¶

The journal version should be within the same framework but with some ‘bonus material’ added in. Key things to aim for are:

Answer for whether USums satisfies Monotonicity
Characterisation of USums
Axiom which discredits Sums/USums: a source cannot simply add many facts to improve its trust score

Belief revision inspired axioms¶

In belief revision we have an existing belief base $B$, and want to add new (possibly conflicting) information $\alpha$ to obtain a consistent belief base $B * \alpha$ which includes $\alpha$. There is lots of work on the axioms that $*$ should satisfy.

Maybe we could take a similar approach with truth discovery. If $N$ and $N'$ are networks differing by a single edge, we could think of the rankings in $N$ as the original belief base, and the rankings in $N'$ as the belief base after the revision step. Then axioms that apply to the revision operator in belief revision could be adapted to the truth discovery operator.

Thing to be careful of is that in belief revision the new information $\alpha$ must always be accepted after revision. In looking at a truth discovery network edge-by-edge, maybe there are cases where we don’t want to accept the fact of the new edge?

Another idea is this. Suppose we start with $B$ as the beliefs of a source $s$. First suppose $s$ is trustworthy. Going through and adding the other source’s beliefs in turn, there should not be much change to $B$ since other sources will generally agree with $s$. If $s$ is untrustworthy, there might be lots of changes since $s$ disagrees with others a lot along the way. So maybe a way to determine trustworthiness is to measure how much $B$ changes.

Constraint-based approach to rankings¶

The idea with this is to impose constraints on the ranking of sources and facts so that our axioms are satisfied. E.g. if $\src_N(f_1)$ is less-trustworthy than $\src_N(f_2)$ then we add a constraint $f_1 \fle_N^T f_2$.

Then the truth discovery process is just finding rankings that satisfy the constraints. We investigated this a little bit, and some explanation is given in the contraint-based document in the aamas repo.

Some things to flesh out are

What are the constraints?
Will we come up with lots of constraints up front, or should we iteratively make choices about the ranking and then add new constraints that arise?
How do we produce the ranking satisfying the constraints without making cycles etc.?

Axioms which deal with making changes to the network¶

Drawing inspiration from the PageRank axiomatisation, we could come up with more axioms that describe how the rankings should be affected by small changes to the network. We have this with Monotonicity (and maybe Independence at a stretch) but there are many more axioms to be stated.

The PageRank work has axioms for adding new vertices, deleting vertices, ‘collapsing’ vertices etc. This allows them to give an algorithm for taking any input graph and manipulating it to obtain another graph which has the same rankings (if the axioms are satisfied). The new graph is somehow ‘simpler’ so that they are able to show that there is a unique ranking, which shows that any two ranking systems satisfying the appropriate axioms must be the same.

Initial ideas for truth discovery are as follows.

Combine facts into composite facts¶

If we have propositions $p, \neg p$ and $q, \neg q$, we can either model it as two binary objects or a single object with fats $p \wedge q$, $\neg p \wedge q$ etc. By some kind of ‘language independence’ idea, the rankings should be the same in both cases. As an axiom, we could say that when merging the two objects (going from two binary objects to one four-fact object), the merged fact corresponding to the two most-believed facts should itself be most-believed.

This is not specific to binary objects either. E.g.

Take two objects $o_1, o_2$ where any source claiming a fact for one must also claim a fact for the other.
Make a new object $o'$ whose facts represent pairs $(f, g)$ where $\obj_N(f) = o_1$ and $\obj_N(g) = o_2$ (put this in a new network $N'$ and work out the new claims)
Axiom: if $f \in \max_{\fle_N^T}(obj_N^{-1}(o_1))$ and $g \in \max_{\fle_N^T}(obj_N^{-1}(o_2))$ then $(f, g) \in \max_{\fle_{N'}^T}(obj_{N'}^{-1}(o'))$. Something like that anyway…

Combine sources into composite sources¶

Continuing with the language independence idea from above, consider the following: a number of reporters work for the same new organisation, and make a bunch of claims. We could model each reporter as an individual source, or group them together into a single source. There could be some kind of axiom saying that the situations are the same, since both approaches are valid.

Pasternack’s thesis might have relevant stuff to say about this kind of ‘grouping’. See the sections on ‘Groups and Attributes’.