Parallel and Distributed Approaches for Graph Based Semi-supervised Learning

Résumé : Deux approches pour l'apprentissage semi-supervisé basé sur le graphe de similarité sont proposés. La première approche est basée sur l'itération d'un opérateur affine. Un élément clé de l'itération de l'opérateur affine est la multiplication vecteur par matrice de type sparse, qui a plusieurs implémentations parallèles très efficaces. La seconde approche appartient à la classe des algorithmes de Monte-Carlo par chaînes de Markov (MCMC). Elle est basé sur un échantillonnage de noeuds en effectuant une marche aléatoire sur le graphe de similarité. Cette dernière approche est distribué par sa nature et peut être facilement mis en oeuvre sur plusieurs processeurs ou sur un réseau. Évaluations théoriques ainsi que pratiques sont fournis. On constate que les noeuds sont classés dans leurs classes avec très petite erreur. La capacité de l'algorithme MCMC de suivre les nouveaux noeuds arrivants online et de les classer est également démontré.
Type de document :
Rapport
[Research Report] RR-8767, Inria Sophia Antipolis. 2015, pp.24
Liste complète des métadonnées

https://hal.inria.fr/hal-01192871
Contributeur : Konstantin Avrachenkov <>
Soumis le : jeudi 3 septembre 2015 - 17:14:40
Dernière modification le : samedi 27 janvier 2018 - 01:31:42
Document(s) archivé(s) le : vendredi 4 décembre 2015 - 12:04:03

Fichiers

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

Identifiants

  • HAL Id : hal-01192871, version 1
  • ARXIV : 1509.01349

Collections

Citation

Konstantin Avrachenkov, Vivek Borkar, Krishnakant Saboo. Parallel and Distributed Approaches for Graph Based Semi-supervised Learning. [Research Report] RR-8767, Inria Sophia Antipolis. 2015, pp.24. 〈hal-01192871〉

Partager

Métriques

Consultations de la notice

202

Téléchargements de fichiers

103