Parallel and Distributed Approaches for Graph Based Semi-supervised Learning
Les Approches Parallèles et Distribués pour l'Apprentissage Semi-supervisé
Résumé
Two approaches for graph based semi-supervised learning are proposed. The first
approach is based on iteration of an affine map. A key element of the affine map iteration is sparse
matrix-vector multiplication, which has several very efficient parallel implementations. The second
approach belongs to the class of Markov Chain Monte Carlo (MCMC) algorithms. It is based on
sampling of nodes by performing a random walk on the graph. The latter approach is distributed
by its nature and can be easily implemented on several processors or over the network. Both
theoretical and practical evaluations are provided. It is found that the nodes are classified into
their class with very small error. The sampling algorithm's ability to track new incoming nodes
and to classify them is also demonstrated.
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é.
Origine : Fichiers produits par l'(les) auteur(s)