Entropic Affinities: Properties and Efficient Numerical Computation

Max Vladymyrov, Miguel Carreira-Perpinan
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):477-485, 2013.

Abstract

Gaussian affinities are commonly used in graph-based methods such as spectral clustering or nonlinear embedding. Hinton and Roweis (2003) introduced a way to set the scale individually for each point so that it has a distribution over neighbors with a desired perplexity, or effective number of neighbors. This gives very good affinities that adapt locally to the data but are harder to compute. We study the mathematical properties of these “entropic affinities” and show that they implicitly define a continuously differentiable function in the input space and give bounds for it. We then devise a fast algorithm to compute the widths and affinities, based on robustified, quickly convergent root-finding methods combined with a tree- or density-based initialization scheme that exploits the slowly-varying behavior of this function. This algorithm is nearly optimal and much more accurate and fast than the existing bisection-based approach, particularly with large datasets, as we show with image and text data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-vladymyrov13, title = {Entropic Affinities: Properties and Efficient Numerical Computation}, author = {Vladymyrov, Max and Carreira-Perpinan, Miguel}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {477--485}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/vladymyrov13.pdf}, url = {https://proceedings.mlr.press/v28/vladymyrov13.html}, abstract = {Gaussian affinities are commonly used in graph-based methods such as spectral clustering or nonlinear embedding. Hinton and Roweis (2003) introduced a way to set the scale individually for each point so that it has a distribution over neighbors with a desired perplexity, or effective number of neighbors. This gives very good affinities that adapt locally to the data but are harder to compute. We study the mathematical properties of these “entropic affinities” and show that they implicitly define a continuously differentiable function in the input space and give bounds for it. We then devise a fast algorithm to compute the widths and affinities, based on robustified, quickly convergent root-finding methods combined with a tree- or density-based initialization scheme that exploits the slowly-varying behavior of this function. This algorithm is nearly optimal and much more accurate and fast than the existing bisection-based approach, particularly with large datasets, as we show with image and text data.} }
Endnote
%0 Conference Paper %T Entropic Affinities: Properties and Efficient Numerical Computation %A Max Vladymyrov %A Miguel Carreira-Perpinan %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-vladymyrov13 %I PMLR %P 477--485 %U https://proceedings.mlr.press/v28/vladymyrov13.html %V 28 %N 3 %X Gaussian affinities are commonly used in graph-based methods such as spectral clustering or nonlinear embedding. Hinton and Roweis (2003) introduced a way to set the scale individually for each point so that it has a distribution over neighbors with a desired perplexity, or effective number of neighbors. This gives very good affinities that adapt locally to the data but are harder to compute. We study the mathematical properties of these “entropic affinities” and show that they implicitly define a continuously differentiable function in the input space and give bounds for it. We then devise a fast algorithm to compute the widths and affinities, based on robustified, quickly convergent root-finding methods combined with a tree- or density-based initialization scheme that exploits the slowly-varying behavior of this function. This algorithm is nearly optimal and much more accurate and fast than the existing bisection-based approach, particularly with large datasets, as we show with image and text data.
RIS
TY - CPAPER TI - Entropic Affinities: Properties and Efficient Numerical Computation AU - Max Vladymyrov AU - Miguel Carreira-Perpinan BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-vladymyrov13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 477 EP - 485 L1 - http://proceedings.mlr.press/v28/vladymyrov13.pdf UR - https://proceedings.mlr.press/v28/vladymyrov13.html AB - Gaussian affinities are commonly used in graph-based methods such as spectral clustering or nonlinear embedding. Hinton and Roweis (2003) introduced a way to set the scale individually for each point so that it has a distribution over neighbors with a desired perplexity, or effective number of neighbors. This gives very good affinities that adapt locally to the data but are harder to compute. We study the mathematical properties of these “entropic affinities” and show that they implicitly define a continuously differentiable function in the input space and give bounds for it. We then devise a fast algorithm to compute the widths and affinities, based on robustified, quickly convergent root-finding methods combined with a tree- or density-based initialization scheme that exploits the slowly-varying behavior of this function. This algorithm is nearly optimal and much more accurate and fast than the existing bisection-based approach, particularly with large datasets, as we show with image and text data. ER -
APA
Vladymyrov, M. & Carreira-Perpinan, M.. (2013). Entropic Affinities: Properties and Efficient Numerical Computation. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):477-485 Available from https://proceedings.mlr.press/v28/vladymyrov13.html.

Related Material