Online Semi-Supervised Learning on Quantized Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Online Semi-Supervised Learning on Quantized Graphs

Résumé

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.
Fichier principal
Vignette du fichier
valko2010online.pdf (410.23 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00642361 , version 1 (18-11-2011)

Identifiants

  • HAL Id : hal-00642361 , version 1

Citer

Michal Valko, Branislav Kveton, Huang Ling, Ting Daniel. Online Semi-Supervised Learning on Quantized Graphs. Uncertainty in Artificial Intelligence, Jun 2010, Catalina Island, United States. ⟨hal-00642361⟩
207 Consultations
131 Téléchargements

Partager

Gmail Facebook X LinkedIn More