Semi-supervised Learning with Density Based Distances

Avleen S. Bijral, Nathan Ratliff, Nathan Srebro
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:60-67, 2011.

Abstract

We present a simple, yet effective, approach to Semi-Supervised Learning. Our approach is based on estimating density-based distances (DBD) using a shortest path calculation on a graph. These Graph-DBD estimates can then be used in any distance-based supervised learning method, such as Nearest Neighbor methods and SVMs with RBF kernels. In order to apply the method to very large data sets, we also present a novel algorithm which integrates nearest neighbor computations into the shortest path search and can find exact shortest paths even in extremely large dense graphs. Significant runtime improvement over the commonly used Laplacian regularization method is then shown on a large scale dataset.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-bijral11a, title = {Semi-supervised Learning with Density Based Distances}, author = {Bijral, Avleen S. and Ratliff, Nathan and Srebro, Nathan}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {60--67}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/bijral11a/bijral11a.pdf}, url = {https://proceedings.mlr.press/r9/bijral11a.html}, abstract = {We present a simple, yet effective, approach to Semi-Supervised Learning. Our approach is based on estimating density-based distances (DBD) using a shortest path calculation on a graph. These Graph-DBD estimates can then be used in any distance-based supervised learning method, such as Nearest Neighbor methods and SVMs with RBF kernels. In order to apply the method to very large data sets, we also present a novel algorithm which integrates nearest neighbor computations into the shortest path search and can find exact shortest paths even in extremely large dense graphs. Significant runtime improvement over the commonly used Laplacian regularization method is then shown on a large scale dataset.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Semi-supervised Learning with Density Based Distances %A Avleen S. Bijral %A Nathan Ratliff %A Nathan Srebro %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-bijral11a %I PMLR %P 60--67 %U https://proceedings.mlr.press/r9/bijral11a.html %V R9 %X We present a simple, yet effective, approach to Semi-Supervised Learning. Our approach is based on estimating density-based distances (DBD) using a shortest path calculation on a graph. These Graph-DBD estimates can then be used in any distance-based supervised learning method, such as Nearest Neighbor methods and SVMs with RBF kernels. In order to apply the method to very large data sets, we also present a novel algorithm which integrates nearest neighbor computations into the shortest path search and can find exact shortest paths even in extremely large dense graphs. Significant runtime improvement over the commonly used Laplacian regularization method is then shown on a large scale dataset. %Z Reissued by PMLR on 04 October 2026.
APA
Bijral, A.S., Ratliff, N. & Srebro, N.. (2011). Semi-supervised Learning with Density Based Distances. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:60-67 Available from https://proceedings.mlr.press/r9/bijral11a.html. Reissued by PMLR on 04 October 2026.

Related Material