A discriminative framework for clustering via similarity functions

By Maria-Florina Balcan, Avrim Blum, Santosh Srinivas Vempala. 2008

195 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Learning Discrete Distributions from Untrusted Batches (2017, background): “…two learning frameworks were proposed for this case in [CSV17]: the list-decodable learning framework (ﬁrst introduced by Balcan et al. [BBV08]), in which the learning algorithm is allowed to output multiple answers to the learning problem (perhaps 1 / (1 − ǫ )), and the semi-veriﬁed…”
Learning from untrusted data (2016, background): “To this end, we consider a notion of successful learning called list decodable learning, first introduced by Balcan et al. (2008). In analogy with list decodable coding theory, the goal is for the learning algorithm to output a short list of possible hypotheses.”
A Survey on Metric Learning for Feature Vectors and Structured Data (2013, methodology): “Bellet et al. (2011, 2012a,b) rely upon the theory of learning with (ǫ, γ, τ)-good similarity function (Balcan et al., 2008a), which makes the link between properties of a similarity function and the generalization of a linear classifier built from this similarity.”
List-decodable robust mean estimation and learning mixtures of spherical gaussians (2017, background): “This is the notion of list-decodable learning, a model introduced by [6].”
K-means properties on six clustering benchmark datasets (2018, methodology): “This has been proved for the average linkage agglomerative clustering algorithm [47] and for the ratio-cut spectral clustering [48].”
Better Agnostic Clustering Via Relaxed Tensor Norms (2017, methodology): “In this case we no longer output exactly k means, and must instead consider the list-decodable model [BBV08, CSV17], where we output a list of O( 1 / α ) means of which the true means are a sublist.”
Hierarchical Clustering (2017, background): “Previous work also proved that average-linkage can be useful to recover an underlying partition-based clustering when it exists under certain stability conditions [8, 9].”