Online Semi-Supervised Learning on Quantized Graphs

Michal Valko 1 Branislav Kveton 2 Huang Ling 3 Ting Daniel 4
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
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.
Type de document :
Communication dans un congrès
Uncertainty in Artificial Intelligence, Jun 2010, Catalina Island, United States
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00642361
Contributeur : Michal Valko <>
Soumis le : vendredi 18 novembre 2011 - 00:25:07
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : dimanche 19 février 2012 - 02:21:06

Fichier

valko2010online.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00642361, version 1

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

391

Téléchargements de fichiers

189