On Similarity Prediction and Pairwise Clustering

Abstract : We consider the problem of clustering a finite set of items from pairwise similarity information. Unlike what is done in the literature on this subject, we do so in a passive learning setting, and with no specific constraints on the cluster shapes other than their size. We investigate the problem in different settings: i. an online setting, where we provide a tight characterization of the prediction complexity in the mistake bound model, and ii. a standard stochastic batch setting, where we give tight upper and lower bounds on the achievable generalization error. Prediction performance is measured both in terms of the ability to recover the similarity function encoding the hidden clustering and in terms of how well we classify each item within the set. The proposed algorithms are time efficient.
Document type :
Conference papers
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01916976
Contributor : Claudio Gentile <>
Submitted on : Friday, November 9, 2018 - 3:17:30 AM
Last modification on : Friday, March 22, 2019 - 1:36:24 AM
Long-term archiving on : Sunday, February 10, 2019 - 12:28:27 PM

File

alt18.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01916976, version 1

Citation

Stephen Pasteris, Fabio Vitale, Claudio Gentile, Mark Herbster. On Similarity Prediction and Pairwise Clustering. ALT 2018 - 29th International Conference on Algorithmic Learning Theory, Apr 2018, Lanzarote, Spain. pp.1 - 28. ⟨hal-01916976⟩

Share

Metrics

Record views

70

Files downloads

49