Online Semi-Supervised Learning on Quantized Graphs

Michal Valko, Branislav Kveton, Ling Huang, Daniel Ting
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:613-621, 2010.

Abstract

In this paper, we tackle the problem of online semi-supervised learning (SSL). When data arrive in a stream, the dual problems of computation and data storage arise for any SSL method. We propose a fast approximate online SSL algorithm that solves for the harmonic solution on an approximate graph. We show, both empirically and theoretically, that good behavior can be achieved by collapsing nearby points into a set of local “representative points” that minimize distortion. Moreover, we regularize the harmonic solution to achieve better stability properties. We apply our algorithm to face recognition and optical character recognition applications to show that we can take advantage of the manifold structure to outperform the previous methods. Unlike previous heuristic approaches, we show that our method yields provable performance bounds.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-valko10a, title = {Online Semi-Supervised Learning on Quantized Graphs}, author = {Valko, Michal and Kveton, Branislav and Huang, Ling and Ting, Daniel}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {613--621}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/valko10a/valko10a.pdf}, url = {https://proceedings.mlr.press/r8/valko10a.html}, abstract = {In this paper, we tackle the problem of online semi-supervised learning (SSL). When data arrive in a stream, the dual problems of computation and data storage arise for any SSL method. We propose a fast approximate online SSL algorithm that solves for the harmonic solution on an approximate graph. We show, both empirically and theoretically, that good behavior can be achieved by collapsing nearby points into a set of local “representative points” that minimize distortion. Moreover, we regularize the harmonic solution to achieve better stability properties. We apply our algorithm to face recognition and optical character recognition applications to show that we can take advantage of the manifold structure to outperform the previous methods. Unlike previous heuristic approaches, we show that our method yields provable performance bounds.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Online Semi-Supervised Learning on Quantized Graphs %A Michal Valko %A Branislav Kveton %A Ling Huang %A Daniel Ting %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-valko10a %I PMLR %P 613--621 %U https://proceedings.mlr.press/r8/valko10a.html %V R8 %X In this paper, we tackle the problem of online semi-supervised learning (SSL). When data arrive in a stream, the dual problems of computation and data storage arise for any SSL method. We propose a fast approximate online SSL algorithm that solves for the harmonic solution on an approximate graph. We show, both empirically and theoretically, that good behavior can be achieved by collapsing nearby points into a set of local “representative points” that minimize distortion. Moreover, we regularize the harmonic solution to achieve better stability properties. We apply our algorithm to face recognition and optical character recognition applications to show that we can take advantage of the manifold structure to outperform the previous methods. Unlike previous heuristic approaches, we show that our method yields provable performance bounds. %Z Reissued by PMLR on 04 October 2026.
APA
Valko, M., Kveton, B., Huang, L. & Ting, D.. (2010). Online Semi-Supervised Learning on Quantized Graphs. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:613-621 Available from https://proceedings.mlr.press/r8/valko10a.html. Reissued by PMLR on 04 October 2026.

Related Material