Correlation Clustering with Adaptive Similarity Queries

Bressan, Marco; Cesa-Bianchi, Nicolo; Paudice, Andrea; Vitale, Fabio

Type de document :

Communication dans un congrès avec actes

Titre :

Correlation Clustering with Adaptive Similarity Queries

Auteur(s) :

Bressan, Marco [Auteur]
Università degli Studi di Roma "La Sapienza" = Sapienza University [Rome] [UNIROMA]
Cesa-Bianchi, Nicolo [Auteur]
Dipartimento di Scienze dell'Informazione [Milano]
Paudice, Andrea [Auteur]
Università degli Studi di Milano = University of Milan [UNIMI]
Vitale, Fabio [Auteur]
Machine Learning in Information Networks [MAGNET]

Titre de la manifestation scientifique :

Conference on Neural Information Processing Systems

Ville :

Vancouver

Pays :

Canada

Date de début de la manifestation scientifique :

2019-12-08

Discipline(s) HAL :

Informatique [cs]/Intelligence artificielle [cs.AI]

Résumé en anglais : [en]

In correlation clustering, we are given $n$ objects together with a binary similarity score between each pair of them. The goal is to partition the objects into clusters so to minimise the disagreements with the scores. ...
Lire la suite >In correlation clustering, we are given $n$ objects together with a binary similarity score between each pair of them. The goal is to partition the objects into clusters so to minimise the disagreements with the scores. In this work we investigate correlation clustering as an active learning problem: each similarity score can be learned by making a query, and the goal is to minimise both the disagreements and the total number of queries. On the one hand, we describe simple active learning algorithms, which provably achieve an almost optimal trade-off while giving cluster recovery guarantees, and we test them on different datasets. On the other hand, we prove information-theoretical bounds on the number of queries necessary to guarantee a prescribed disagreement bound. These results give a rich characterization of the trade-off between queries and clustering error.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal.inria.fr/hal-02376961/document
Accès libre
Accéder au document

http://arxiv.org/pdf/1905.11902
Accès libre
Accéder au document

https://hal.inria.fr/hal-02376961/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-02376961/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

1905.11902.pdf
Accès libre
Accéder au document

1905.11902
Accès libre
Accéder au document

Correlation Clustering with Adaptive ... BibTeX CSV Excel RIS

Fichiers

Correlation Clustering with Adaptive ...

BibTeX

CSV

Excel

RIS