Séminaire (Organisé par l’Equipe de recherche DI)

Yuan YAO

Professor in Bairen program, School of Mathematical Sciences, Peking University

Robust Ranking on Graphs

Jeudi 31 janvier 2013 à 10h30 en salle RD134

Résumé :

The problem of ranking or rating based on pairwise comparisons, as an uni-dimensional scaling, is a fundamental problem which can be traced back at least to the $18^th$ century. Recently there is a rapid growth of paired comparison data which are imbalanced, incomplete, and distributed on graphs, for example the crowdsourcing experiments on Internet. It is important to monitor the quality of such data where the existence of outliers may cause instability to the inference of global ranking. To reach a robust ranking with paired comparison data on graphs, in this paper we provide a systematic study on a general linear model in the presence of sparse symmetric outliers and Gaussian-type noise. Exterior calculus on graphs plays a central role to form a unified framework for various ranking algorithms.

We present various conditions and algorithms under which outliers can be detected and the underlying global ranking function can be recovered, exactly or approximately. In particular, we benefit from exploiting Erd\"os-R\’enyi random graphs in crowdsourcing experiments in the following sense : against sparse symmetric outliers, a least absolute deviation (LAD or L1) solution may achieve exact recovery of global ranking function at optimal rates up to a logarithmic factor ; against a mixture of sparse outliers and Gaussian noise, it helps outlier detection LASSO meet some necessary conditions and tune the regularization parameter with random projections.


FR SHIC 3272

Collegium UTC/CNRS