Grouping Games: Finding Clusters in Graphs, Digraphs and Hypergraphs
Marcello Pelillo
Ca' Foscari University of Venice, Italy
DEIB - 3A Room
April 18th, 2016
2.00 pm
Contacts:
Viola Schiaffonati
Research Line:
Artificial intelligence and robotics
Ca' Foscari University of Venice, Italy
DEIB - 3A Room
April 18th, 2016
2.00 pm
Contacts:
Viola Schiaffonati
Research Line:
Artificial intelligence and robotics
Abstract
Clustering refers to the process of extracting maximally coherent groups from a set of objects using pairwise, or high-order, similarities. Traditional approaches to this problem are based on the idea of partitioning the input data into a predetermined number of classes, thereby obtaining the clusters as a by-product of the partitioning process. In this talk, I'll provide a brief review of recent work done in my group which offers a radically different view of the problem. In contrast to the classical approach, in fact, we attempt to provide a meaningful formalization of the very notion of a cluster and we show that game theory offers an attractive and unexplored perspective that serves well our purpose. To this end, we formulate the clustering problem in terms of a non-cooperative “clustering game” and show that a natural notion of a cluster turns out to be equivalent to a classical (evolutionary) game-theoretic equilibrium concept. We prove that the problem of finding the equilibria of our clustering game is equivalent to locally optimizing a polynomial function over the standard simplex, and we provide a discrete-time dynamics to perform this optimization, based on the Baum-Eagon inequality. The proposed grouping framework, which has already found applications in a variety of application fields, including computer vision, security and video surveillance, bioinformatics, etc., is general and can be applied to weighted graphs, digraphs and hypergraphs alike.
Short Bio
Marcello Pelillo is Professor of Computer Science at Ca' Foscari University in Venice, Italy, where he directs the European Center for Living Technology (ECLT) and the Computer Vision and Pattern Recognition group. He held visiting research positions at Yale University, McGill University, the University of Vienna, York University (UK), the University College London, and the National ICT Australia (NICTA). He has published more than 200 technical papers in refereed journals, handbooks, and conference proceedings in the areas of pattern recognition, computer vision and machine learning. He is General Chair for ICCV 2017 and has served as Program Chair for several conferences and workshops, many of which he initiated (e.g., EMMCVPR, SIMBAD, IWCV). He serves (has served) on the Editorial Boards of the journals IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), Pattern Recognition, IET Computer Vision, Frontiers in Computer Image Analysis, Brain Informatics, and serves on the Advisory Board of the International Journal of Machine Learning and Cybernetics. Prof. Pelillo has been elected a Fellow of the IEEE and a Fellow of the IAPR, and has recently been appointed IEEE Distinguished Lecturer.