a_novel_distance_metric_for_rank_aggregation

Farzad Farnoud (UIUC)

Wed April 11, 2:00pm. EEB 248

Abstract: The problem of rank aggregation arises in research areas as diverse as computer science, social sciences, management, and marketing. Rank aggregation may be succinctly described as follows: given a set of rankings, each produced by an expert, find the ranking that minimizes the sum of the distances to the original rankings. Here, the distance function is chosen according to some predefined relevance criteria, such as similarity of ranked subjects and cut-off thresholds for the rankings.

In most rank aggregation scenarios, one usually refers to the Kendall’s tau distance which leads to Kemeny optimal orderings. Although Kendall’s tau and many other classical distance functions including Spearman’s Footrule are well-established and well-studied, they cannot take into account two important factors in rank aggregation. First, in many applications the top of the list is more important than the bottom of the list, and hence changes to the top of the list must be compensated for by larger distance. Second, transposing elements that are similar must be less costly than transposing dissimilar elements.

In this talk, we propose a distance function, termed generalized Cayley distance, based on transpositions with non-uniform costs that enables us to address the problems described above. Many of the previously proposed distance functions may be viewed as a specialization of the proposed distance function. We also describe a polynomial time algorithm for computing the Cayley distance using a variety of tools including graph theoretic tools and dynamic programming. We conclude the talk by describing a novel aggregation method for the generalized Cayley distance and by presenting its performance on survey data collected at the UIUC campus.

Bio: Farzad Farnoud (Hassanzadeh) received his BSc degree in Electrical Engineering from Sharif University of Technology, Iran, on August 2006. He received his MSc degree in Electrical and Computer Engineering from University of Toronto, Canada. His Master's thesis is titled “Reliable Broadcast of Safety Messages in Vehicular Ad hoc Networks” and describes a novel method for broadcasting critical messages in a vehicular environment. He is currently a PhD candidate in Electrical and Computer Engineering at UIUC. His current research interests are rank modulation for flash memories and rank aggregation.

Host: Alex Dimakis, dimakis [at] usc.edu

Back to CommNetS Seminar Page

a_novel_distance_metric_for_rank_aggregation.txt · Last modified: 2016/09/01 19:15 (external edit)