Publications¶
A list of my work can also be found on my Google scholar profile.
- Trustworthiness and Expertise: Social Choice and Logic-based Perspectives [pdf] [bib]
Abstract
This thesis studies problems involving unreliable information. We look at how to aggregate conflicting reports from multiple unreliable sources, how to assess the trustworthiness and expertise of sources, and investigate the extent to which the truth can be found with imperfect information. We take a formal approach, developing mathematical frameworks in which these problems can be formulated precisely and their properties studied. The results are of a conceptual and technical nature, which aim to elucidate interesting properties of the problem at the core abstract level. In the first half we adopt the axiomatic approach of social choice theory. We formulate truth discovery -- the problem of aggregating reports to estimate true information and reliability of the sources -- as a social choice problem. We apply the axiomatic method to investigate desirable properties of such aggregation methods, and analyse a specific truth discovery method from the literature. We go on to study ranking methods for bipartite tournaments. This setting can be applied to rank sources according to their accuracy on a number of topics, and is also of independent interest. In the second half we take a logic-based perspective. We use modal logic to formalise the notion of expertise, and explore connections with knowledge and truthfulness of information. We use this as the foundation for a belief change problem, in which reports must be aggregated to form beliefs about the true state of the world and the expertise of the sources. We again take an axiomatic approach -- this time in the tradition of belief revision -- where several postulates are proposed as rationality criteria. Finally, we address truth-tracking: the problem of finding the truth given non-expert reports. Adapting recent work combining logic with formal learning theory, we investigate the extent to which truth-tracking is possible, and how truth-tracking interacts with rationality. - Expertise and information: an epistemic logic perspectives [pdf] [bib]
Abstract
In this paper we present a modal logic framework to reason about the expertise of information sources. A source is considered an expert on a proposition φ if they are able to correctly refute φ in any possible world where φ is false. Closely connected with expertise is a notion of soundness of information: φ is said to be "sound" if it is true up to lack of expertise of the source. That is, any statement logically weaker than φ on which the source has expertise must in fact be true. This is relevant for modelling situations in which sources make claims beyond their domain of expertise. Particular attention is paid to the connection between expertise and knowledge: we show that expertise and soundness admit precise interpretations in terms of S4 and S5 epistemic logic, under certain conditions. We go on to extend the framework to multiple sources, defining two notions of collective expertise. These also have epistemic interpretations via distributed and common knowledge from multi-agent epistemic logic. On the technical side, we give several sound and complete axiomatisations of various classes of expertise models. - Towards An Axiomatic Approach to Truth Discovery [pdf] [bib]
Abstract
The problem of truth discovery, i.e., of trying to find the true facts concerning a number of objects based on reports from various information sources of unknown trustworthiness, has received increased attention recently. The problem is made interesting by the fact that the relative believability of facts depends on the trustworthiness of their sources, which in turn depends on the believability of the facts the sources report. Several algorithms for truth discovery have been proposed, but their evaluation has mainly been performed experimentally by computing accuracy against large datasets. Furthermore, it is often unclear how these algorithms behave on an intuitive level. In this paper we take steps towards a framework for truth discovery which allows comparison and evaluation of algorithms based instead on their theoretical properties. To do so we pose truth discovery as a social choice problem, and formulate various axioms that any reasonable algorithm should satisfy. Along the way we provide an axiomatic characterisation of the baseline 'Voting' algorithm -- which leads to an impossibility result showing that a certain combination of the axioms cannot hold simultaneously -- and check which axioms a particular well-known algorithm satisfies. We find that, surprisingly, our more fundamental axioms do not hold, and propose modifications to the algorithms to partially fix these problems. - Truth-Tracking with Non-Expert Information Sources [pdf] [bib] [slides]
Abstract
We study what can be learned when receiving reports from multiple non-expert information sources. We suppose that sources report all that they consider possible, given their expertise. This may result in false and inconsistent reports when sources lack expertise on a topic. A learning method is truth-tracking, roughly speaking, if it eventually converges to correct beliefs about the "actual" world. This involves finding both the actual state of affairs in the domain described by the sources, and finding the extent of the expertise of the sources themselves. We investigate the extent to which truth-tracking is possible, and describe what information can be learned even if the actual world cannot be pinned down uniquely. We find that a broad spread of expertise among the sources allows the actual state of affairs to be found, even if no individual source is an expert on all topics. On the other hand, narrower expertise at the individual level allows the actual expertise to be found more easily. Finally, we turn to learning methods themselves: we provide a postulate-based characterisation of truth-tracking for general methods under mild assumptions, before looking at a specific class of methods well-known from the belief change literature. - Who's the Expert? On Multi-source Belief Change [pdf] [bib] [slides]
Abstract
Consider the following belief change/merging scenario. A group of information sources gives a sequence of reports about the state of the world at various instances (e.g. different points in time). The true states at these instances are unknown to us. The sources have varying levels of expertise, also unknown to us, and may be knowledgeable on some topics but not others. This may cause sources to report false statements in areas they lack expertise. What should we believe on the basis of these reports? We provide a framework in which to explore this problem, based on an extension of propositional logic with expertise formulas. This extended language allows us to express beliefs about the state of the world at each instance, as well as beliefs about the expertise of each source. We propose several postulates, provide a couple of families of concrete operators, and analyse these operators with respect to the postulates. - A Logic of Expertise [pdf] [bib] [slides]
Abstract
In this paper we introduce a simple modal logic framework to reason about the expertise of an information source. In the framework, a source is an expert on a proposition p if they are able to correctly determine the truth value of p in any possible world. We also consider how information may be false, but true after accounting for the lack of expertise of the source. This is relevant for modelling situations in which information sources make claims beyond their domain of expertise. We use non-standard semantics for the language based on an expertise set with certain closure properties. It turns out there is a close connection between our semantics and S5 epistemic logic, so that expertise can be expressed in terms of knowledge at all possible states. We use this connection to obtain a sound and complete axiomatisation. - Rankings for Bipartite Tournaments via Chain Editing [pdf] [bib] [video]
Abstract
Ranking the participants of a tournament has applications in voting, paired comparisons analysis, sports and other domains. In this paper we introduce bipartite tournaments, which model situations in which two different kinds of entity compete indirectly via matches against players of the opposite kind; examples include education (students/exam questions) and solo sports (golfers/courses). In particular, we look to find rankings via chain graphs, which correspond to bipartite tournaments in which the sets of adversaries defeated by the players on one side are nested with respect to set inclusion. Tournaments of this form have a natural and appealing ranking associated with them. We apply chain editing — finding the minimum number of edge changes required to form a chain graph — as a new mechanism for tournament ranking. The properties of these rankings are investigated in a probabilistic setting, where they arise as maximum likelihood estimators, and through the axiomatic method of social choice theory. Despite some nice properties, two problems remain: an important anonymity axiom is violated, and chain editing is NP-hard. We address both issues by relaxing the minimisation constraint in chain editing, and characterise the resulting ranking methods via a greedy approximation algorithm. - On the Link Between Truth Discovery and Bipolar Abstract Argumentation [pdf] [bib]
Abstract
With the abundance of data available in today’s world, e.g. from the web, social media platforms and crowdsourcing systems, it is common to find conflicting information from different data sources. Truth discovery algorithms aim to find the true ‘facts’ amongst such conflicts by estimating the trustworthiness of data sources, so that the claims made by trustworthy sources can be given priority. Since source trustworthiness is unknown a priori, such algorithms jointly estimate trust in sources and belief in facts, assigning higher trust scores to sources who claim believable facts and higher belief scores to facts claimed by trusted sources. Truth discovery has received increasing attention in the data mining and crowdsourcing literature, but other perspectives may offer additional insight into the problem and potential solutions. In this paper we discuss the link between truth discovery and argumentation, with a particular focus on bipolar abstract argumentation. - An Axiomatic Approach to Truth Discovery (extended abstract) [pdf] [bib]
Abstract
There is an increasing amount of data available in today’s world, particularly from the web, social media platforms and crowdsourcing systems. The openness of such platforms makes it simple for a wide range of users to share information quickly and easily, potentially reaching a wide international audience. It is inevitable that amongst this abundance of data there are conflicts, where data sources disagree on the truth regarding a particular object or entity. This can be caused by low-quality sources mistakenly providing erroneous data, or by malicious sources aiming to misinform. Truth discovery methods have emerged to resolve such conflicts and find the true facts by considering the trustworthiness of sources. The general principle is that believable facts are those claimed by trustworthy sources, and trustworthy sources are those that claim believable facts. Application areas include real-time traffic navigation, crowdsourcing and social sensing. In this paper we initiate work on formal foundations for truth discovery by providing a general framework which allows algorithms to be evaluated in a principled way based on their theoretical properties. To do so we pose truth discovery as a social choice problem and apply the axiomatic approach, as has been successfully done for closely related problems such as judgment aggregation, voting theory and ranking systems. - Implementation and Analysis of Truth Discovery Algorithms [pdf] [bib]
Abstract
With the vast amount of data available in today’s world, particularly on the web, it is common to find conflicting information from different sources. Given an input consisting of conflicting claims from multiple sources of unknown trustworthiness and reliability, truth discovery algorithms aim to evaluate which claims should be believed and which sources should be trusted. The evaluations of trust and belief should cohere with one another, so that a claim receives a high belief ranking if it is backed up by trustworthy sources and vice versa. This project investigates truth discovery from practical and theoretical perspectives. On the practical side, a number of algorithms from the literature are implemented in software and analysed. On the theoretical side, a formal framework is developed to study truth discovery from a general point of view, allowing results to be proved and comparisons made between truth discovery and related areas in the literature. Desirable properties of truth discovery algorithms are defined in the framework, and we consider whether they are satisfied by a particular real-world algorithm, Sums.