A list of research outputs can also be found on my Google scholar profile.
- Rankings for Bipartite Tournaments via Chain Editing [pdf] [bib] [video]
AbstractRanking 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]
AbstractWith 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]
AbstractThere 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]
AbstractWith 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.