Error Analysis of Laplacian Eigenmaps for Semi-supervised Learning

Xueyuan Zhou, Nathan Srebro
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:901-908, 2011.

Abstract

We study the error and sample complexity of semi-supervised learning by Laplacian Eignmaps at the limit of infinite unlabeled data. We provide a bound on the error, and show that it is controlled by the graph Laplacian regularizer. Our analysis also gives guidance to the choice of the number of eigenvectors $k$ to use: when the data lies on a $d$-dimensional domain, the optimal choice of $k$ is of order $(n/\log(n))^{\frac{d}{d+2}}$, yielding an asymptotic error rate of $(n/\log(n))^{-\frac{2}{2+d}}$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-zhou11c, title = {Error Analysis of Laplacian Eigenmaps for Semi-supervised Learning}, author = {Zhou, Xueyuan and Srebro, Nathan}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {901--908}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/zhou11c/zhou11c.pdf}, url = {https://proceedings.mlr.press/v15/zhou11c.html}, abstract = {We study the error and sample complexity of semi-supervised learning by Laplacian Eignmaps at the limit of infinite unlabeled data. We provide a bound on the error, and show that it is controlled by the graph Laplacian regularizer. Our analysis also gives guidance to the choice of the number of eigenvectors $k$ to use: when the data lies on a $d$-dimensional domain, the optimal choice of $k$ is of order $(n/\log(n))^{\frac{d}{d+2}}$, yielding an asymptotic error rate of $(n/\log(n))^{-\frac{2}{2+d}}$.} }
Endnote
%0 Conference Paper %T Error Analysis of Laplacian Eigenmaps for Semi-supervised Learning %A Xueyuan Zhou %A Nathan Srebro %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-zhou11c %I PMLR %P 901--908 %U https://proceedings.mlr.press/v15/zhou11c.html %V 15 %X We study the error and sample complexity of semi-supervised learning by Laplacian Eignmaps at the limit of infinite unlabeled data. We provide a bound on the error, and show that it is controlled by the graph Laplacian regularizer. Our analysis also gives guidance to the choice of the number of eigenvectors $k$ to use: when the data lies on a $d$-dimensional domain, the optimal choice of $k$ is of order $(n/\log(n))^{\frac{d}{d+2}}$, yielding an asymptotic error rate of $(n/\log(n))^{-\frac{2}{2+d}}$.
RIS
TY - CPAPER TI - Error Analysis of Laplacian Eigenmaps for Semi-supervised Learning AU - Xueyuan Zhou AU - Nathan Srebro BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-zhou11c PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 901 EP - 908 L1 - http://proceedings.mlr.press/v15/zhou11c/zhou11c.pdf UR - https://proceedings.mlr.press/v15/zhou11c.html AB - We study the error and sample complexity of semi-supervised learning by Laplacian Eignmaps at the limit of infinite unlabeled data. We provide a bound on the error, and show that it is controlled by the graph Laplacian regularizer. Our analysis also gives guidance to the choice of the number of eigenvectors $k$ to use: when the data lies on a $d$-dimensional domain, the optimal choice of $k$ is of order $(n/\log(n))^{\frac{d}{d+2}}$, yielding an asymptotic error rate of $(n/\log(n))^{-\frac{2}{2+d}}$. ER -
APA
Zhou, X. & Srebro, N.. (2011). Error Analysis of Laplacian Eigenmaps for Semi-supervised Learning. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:901-908 Available from https://proceedings.mlr.press/v15/zhou11c.html.

Related Material