2016

Semi-supervised Kernel Metric Learning Using Relative Comparisons

Amid, Ehsan, Gionis, Aristides, Ukkonen, Antti

Understand

We consider the problem of metric learning subject to a set of constraints on relative-distance comparisons between the data items.

Such constraints are meant to reflect side-information that is not expressed directly in the feature vectors of the data items.
The relative-distance constraints used in this work are particularly effective in expressing structures at finer level of detail than must-link (ML) and cannot-link (CL) constraints, which are most commonly used for semi-supervised clustering.
Relative-distance constraints are thus useful in settings where providing an ML or a CL constraint is difficult because the granularity of the true clustering is unknown.

Built on

Adjustment of an inverse matrix corresponding to changes in the elements of a given column or a given row of the original matrix
J. Sherman and W. J. Morrison · 1949
Earlier work this paper cites.
The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming
L.M. Bregman · 1967
Earlier work this paper cites.
Comparing partitions
Lawrence Hubert and Phipps Arabie · 1985
Earlier work this paper cites.
Matrix Computations (3rd Ed.)
Gene H. Golub and Charles F. Van Loan · 1996
Earlier work this paper cites.
Clustering with instance-level constraints
Kiri Wagstaff and Claire Cardie · 2000
Earlier work this paper cites.
Modeling the shape of the scene: A holistic representation of the spatial envelope
Aude Oliva and Antonio Torralba · 2001
Earlier work this paper cites.
Constrained k k -means clustering with background knowledge
Kiri Wagstaff, Claire Cardie, Seth Rogers, and Stefan Schroedl · 2001
Earlier work this paper cites.
Mean shift: a robust approach toward feature space analysis
D. Comaniciu and P. Meer · 2002
Earlier work this paper cites.
From instance-level constraints to space-level constraints
Dan Klein, Sepandar D. Kamvar, and Christopher D. Manning · 2002
Earlier work this paper cites.
Distance metric learning with application to clustering with side-information
Eric P. Xing, Andrew Y. Ng, Michael I. Jordan, and Stuart J. Russell · 2002
Earlier work this paper cites.
Stochastic neighbor embedding
Geoffrey Hinton and Sam Roweis · 2003
Earlier work this paper cites.

Similar

Learning a distance metric from relative comparisons
Matthew Schultz and Thorsten Joachims · 2003
Cited alongside, same era.
Integrating constraints and metric learning in semi-supervised clustering
Mikhail Bilenko, Sugato Basu, and Raymond J. Mooney · 2004
Cited alongside, same era.
A unified view of kernel k-means, spectral clustering and graph cuts
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis · 2005
Cited alongside, same era.
Semi-supervised learning with penalized probabilistic clustering
Zhengdong Lu and Todd K. Leen · 2005
Cited alongside, same era.
Matrix exponentiated gradient updates for on-line learning and Bregman projection
K. Tsuda, G. Rätsch, and M. Warmuth · 2005
Cited alongside, same era.
Information-theoretic metric learning
Jason V Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S Dhillon · 2007
Cited alongside, same era.
Semi-supervised clustering with pairwise constraints: A discriminative approach
Zhengdong Lu · 2007
Cited alongside, same era.
Semisupervised clustering with metric learning using relative comparisons
Nimit Kumar and Krishna Kummamuru · 2008
Cited alongside, same era.
Constrained spectral clustering through affinity propagation
Zhengdong Lu and Miguel Carreira-Perpiñán · 2008
Cited alongside, same era.
Learning a mahalanobis distance metric for data clustering and classification
Shiming Xiang, Feiping Nie, and Changshui Zhang · 2008
Cited alongside, same era.
Active semi-supervision for pairwise constrained clustering
Sugato Basu, Arindam Banerjee, and Raymond J. Mooney
Cited in the paper.
A probabilistic framework for semi-supervised clustering
Sugato Basu, Mikhail Bilenko, and Raymond J. Mooney
Cited in the paper.

Then

Semi-supervised sparse metric learning using alternating linearization optimization
Wei Liu, Shiqian Ma, Dacheng Tao, Jianzhuang Liu, and Peng Liu · 2010
Later among the works it cites.
Constrained spectral clustering via exhaustive and efficient constraint propagation
Zhiwu Lu and Horace Ip · 2010
Later among the works it cites.
Metric and kernel learning using a linear transformation
Prateek Jain, Brian Kulis, Jason V. Davis, and Inderjit S. Dhillon · 2012
Later among the works it cites.
Metric learning from relative comparisons by minimizing squared residual
Eric Yi Liu, Zhishan Guo, Xiang Zhang, Vladimir Jojic, and Wei Wang · 2012
Later among the works it cites.
The crowd-median algorithm
Hannes Heikinheimo and Antti Ukkonen · 2013
Later among the works it cites.
Semi-supervised kernel mean shift clustering
S. Anand, S. Mittal, O. Tuzel, and P. Meer · 2014
Later among the works it cites.
Discriminative clustering with relative constraints
Original
Yuanli Pei, Xiaoli Z Fern, Rómer Rosales, and Teresa Vania Tjahja · 2014
Later among the works it cites.
A kernel-learning approach to semi-supervised clustering with relative distance comparisons
Ehsan Amid, Aristides Gionis, and Antti Ukkonen · 2015
Later among the works it cites.
Efficient online relative comparison kernel learning
Original
Eric Heim, Matthew Berger, Lee M. Seversky, and Milos Hauskrecht · 2015
Later among the works it cites.
Crowdsourced nonparametric density estimation using relative distances
Antti Ukkonen, Behrouz Derakhshan, and Hannes Heikinheimo · 2015
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…