Generalized Optimization Framework for Graph-based Semi-supervised Learning

Résumé : Dans ce rapport nous proposons un schéma d'optimisation générique pour l'apprentissage semi-supervisé sur des graphes. Ce cadre intègre comme cas particuliers les approches dites du Laplacien standard et du Laplacien normalis é ainsi qu'une méthode basée sur PageRank. Nous proposons également une interprétation probabiliste originale qui s'appuie sur la notion de marche aléatoire, puis nous étudions les comportements limites de ces méthodes. Le recours aux marches aléatoires nous permet d'expliquer les di érences de performances existant entre ces trois noyaux de lissage. Une des conclusions principales de ce travail est que les méthodes construites sur PageRank sont plus robustes face au choix du paramètre de régularisation et des points marqués. Nous illustrons nos résultats théoriques avec deux jeux de données réelles représentatives de deux dé s distincts: celui des réseaux sociaux avec le cas des personnages du roman "Les Misérables" et celui des graphes d'hyper-liens à travers l'application Wikipedia. En particulier, nous démontrons qu'il est possible de classi er les articles de Wikipedia avec une très bonne précision et un très bon rappel, à partir de la seule information fournie par les liens hyper-texte.
Type de document :
Rapport
[Research Report] RR-7774, INRIA. 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00633818
Contributeur : Marina Sokol <>
Soumis le : mercredi 19 octobre 2011 - 14:56:52
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : jeudi 15 novembre 2012 - 10:01:55

Fichiers

RR-7774.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00633818, version 1
  • ARXIV : 1110.4278

Collections

Citation

Konstantin Avrachenkov, Paulo Gonçalves, Alexey Mishenin, Marina Sokol. Generalized Optimization Framework for Graph-based Semi-supervised Learning. [Research Report] RR-7774, INRIA. 2011. 〈inria-00633818〉

Partager

Métriques

Consultations de la notice

441

Téléchargements de fichiers

243