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.


Mardi 20 juin 2017

Séminaire à 14h en GI042 (bâtiment Blaise Pascal), présenté par Patrice Perny, LIP6.
« Décision interactive sur domaine combinatoire par élicitation incrémentale de préférences ».

Jeudi 11 mai 2017

Séminaire à 14h en GI042 (bâtiment Blaise Pascal), présenté par Nicolas Maudet, LIP6 (Equipe SMA).
« Current issues in argumentation ».

Mardi 4 avril 2017

Séminaire à 14 h dans l’amphi du Centre d’Innovation de l’UTC, présenté par Xavier LAGORCE, PhD, Head of Computer Vision, Chronocam.
« Chronocam : Event-based cameras for machine vision »

Jeudi 27 octobre 2016

Séminaire à 14 h en GI016, présenté par Fabien Pfaender, UTSEUS.
« State of Cities - A Massive, Systematic, Data Powered, Comparative Analysis Of Cities ».

Pages 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ...


FR SHIC 3272

Collegium UTC/CNRS