Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
5 juillet 2009 7 05 /07 /juillet /2009 16:11




Objectif: en apprentissage artificiel, traiter de grandes bases de données.


       Données: des couples entrée x sortie.
       Sorties: une fonction qui devine les sorties à partir des entrées
       Cadre: beaucoup de données.
       Vulgarisation/exemples:
  • imaginez un petit robot à qui vous montrez plein d'exemples d'ours et plein d'exemples d'éléphants, et qui doit apprendre à différencier les ours des éléphants.
  • imaginez un détecteur qui doit apprendre à faire la différence entre l'écho sonar d'une mine et l'écho sonar d'un rocher.
  • imaginez un détecteur qui en fonction d'indicateurs de votre chaine de production industrielle doit vous prédire la localisation d'une panne




Rapide survol de quelques techniques pour effectuer un apprentissage supervisé d'un grand jeu de données. Attention, fortement influencé par mon cadre applicatif préféré: grand nombre de points, mais dimension modérée. (difficile d'accès pour grand public - version encore à travailler, tout conseil bienvenu)  

1. Première approche: prendre un algo genre SVM gaussiennes et le rendre le plus efficace possible sur grandes bases, notamment à coups de parallélisme.


Exemples:
  • La parallel Mixture of SVMs: malheureusement speed-up modéré malgré des grands nombres de processeurs. 
  • La Cascade SVM: là aussi, amélioration modérée sauf si le nombre de support vectors est faible devant le volume du problème (cas assez rare pour des prévisions numériques, i.e. régression) 
Autres exemples pas encore assez étudiés pour que j'ai un avis: différents papiers sur l'amélioration des SVM gaussiennes ==> Core Support Vector Machines (semble avoir une généralité modérée mais il faudra que j'étude ça plus avant), "a gentle hessian for efficient gradient descent" que j'ai pas étudié assez aussi.

Conclusion (temporaire) à mon avis: des améliorations modérés;
il y a au moins un truc où le parallélisme apporte beaucoup, c'est le choix d'hyperparamètres "Weka-parallel: machine learning in parallel" ==> on parallélise la recherche d'hyperparamètres par cross-validation. Il y a aussi les méthodes "généralistes" de parallélisation, auxquelles je reviens plus bas.


2. Prendre un algo qui passe bien à l'échelle

...plutôt que d'optimiser à fond un algo qui passe mal.  Typiquement, se dire que les SVM linéaires c'est drôlement plus rapides et que ça compense le fait que c'est pas terrible asymptotiquement. Un arbre de décision, surtout en classification, peut aussi faire l'affaire, d'autant plus qu'il peut se randomiser commodémment et ainsi être parallélisé / mixé à du bagging ou subagging. L'article "Comments on << A parallel mixture of SVMs for large scale problems>>" signale en particulier que la "parallel mixture of SVMs" marche en fait beaucoup moins bien qu'une randomisation de C4.5 (moyenner plusieurs runs de C4.5 avec randomisation).


    


 Semble pas mal si dimension suffisamment grande pour que linéaire soit bon. Pour éviter le purement linéaire: des gens se sont mis à faire des reformulations non-linéaires rapides: random kitchen sinks (RKS; dans l'esprit des "reservoir methods" d'ailleurs), On est très loin des SVMs au bout du compte: la constante C des SVM devient sans impact pour la régression (on prend C=infini), et ça revient à faire du simple "linear least squares" sur des données transformées non-linéairement.



Conclusion: ça a l'air intéressant comme approche et très simple Cf l'article Rahimi et Recht: Weighted sums of Random Kitchen Sinks: Replacing minimization with randomization in Learning; aussi, sur leur page web, on trouve un codage en quelques lignes de matlab ou octave des RKS.


Autre idée, prendre les bons vieux réseaux de neurones à backprop, qui ont l'avantage de bigrement bien passer à l'échelle et de permettre facilement tant régression que classification

3. Paralléliser de manière externe 


(ci-dessus un des clusters de la formidable grille Grid5000)


Il s'agit de paralléliser sans toucher le fonctionnement interne de l'algorithme. Ca peut être avec les approches précédentes d'ailleurs. Quelques grandes catégories d'approches:

  • Bagging: forcément très parallèle tant que le nombre de procs est plus petit que le nombre de bootstraps. 
  • Approche tentante: le subagging, qui fait du bagging sur des petits morceaux de la base et non sur la base complète, et moyenne tout ça. Beaucoup plus parallèle que le bagging. 
  • Randomiser l'algorithme d'apprentissage (c'est finalement une généralisation de bagging/subagging et faire la moyenne des algos obtenus. En particulier, l'article " Comment on << A parallel Mixture of SVMs for Very Large Scale Problems >>" signale que randomiser C4.5 permet de faire beaucoup mieux que la parallel mixture of SVM citée plus haut et d'avoir un algo beaucoup plus parallèle (au total, sur l'appli du papier initial, ils vont beaucoup plus vite, sont largement plus efficace, et ont un programme beaucoup plus simple). 
  • random subspace: on prend pas les même feature pour les différents algos "Combining Bagging and Random Subspaces to Create Better Ensembles": random subspaces vraiment pas limités aux random forests ==> bon pour tout algo 
  • paralléliser la recherche d'hyperparamètres; on sent que c'est simple et efficace, cf "Weka-parallel: machine learning in parallel".
4. Conclusions (temporaires)
 (ces conclusions sont personnelles, instables car juste en début de projet):
  • subagging ça a l'air bien, simple, efficace, passant à l'échelle, sans trop de paramètres à régler;
  • parallélisation de recherche d'hyperparamètre aussi 
  • En cours: voir à quel point il est rentable de prendre un algo moins bien usuellement, mais qui s'avèrerait meilleur au niveau du passage à l'échelle, modulo quelques "random kitchen sinks" par exemple.
  • A tester urgemment: random subspace method (très lié aux RKS)
  • A tester urgemment: RKS à tester plus intensivement que je ne l'ai fait.

Partager cet article

Repost 0
Published by teytaud - dans Recherche
commenter cet article

commentaires