Cet article est la troisième partie du compte-rendu du Hadoop Summit, qui a eu lieu à Amsterdam début avril. Il est dédié aux aspects algorithmiques, qui sont une application importante de la technologie.

Si la terminologie du machine learning (recommandation, régression, classification, …) ne vous est pas familière, l’article risque d’être obscur. Vous pouvez commencer par (re)lire cet article de notre blog, qui vous présente les bases nécessaires pour comprendre le présent article.

How to tell which algorithms really matter

(Ted Dunning, MapR)

Comme toutes les sessions de Ted Dunning, celle-ci était plutôt dense et destinée à un public “matheux”. Elle reprenait des éléments de présentations déjà vues ailleurs, mais de manière un peu plus accessible (ouf). Et contrairement à beaucoup de sessions de Ted Dunning, on n’a pas eu droit à un tour de magie (en revanche il avait son éternelle casquette rouge) ;-)

Elle commençait par un “cahier des charges” des algorithmes utiles en pratique, par opposition aux travaux purement académiques. De tels algorithmes doivent être :

• déployables sur des systèmes réels
• robustes face aux erreurs, volontaires ou non (exemple des bots)
• transparents (la dégradation de la qualité des prédictions doit pouvoir être mesurée)
• exploitables (Ted oppose ici le skillset des exploitants et le mindset des scientifiques, je traduis ainsi cette opposition)
• proportionnés (avoir un ROI acceptable)

Quels sont les algorithmes qui se “comportent bien” ? Un contre-exemple intéressant, est l’algorithme gagnant du concours Netflix. Il combinait plus de 250 algorithmes individuels, ce qui le rend inexploitable en pratique, autant pour ses performances qu’à cause du fait que personne ne comprend ce qu’il fait.

Pour les cas de recommandation

Utiliser le result dithering pour laisser l’algorithme explorer des pistes qu’il ne testerait pas autrement, donc pour le forcer à sortir des optima locaux en lui interdisant de trop se répéter.

Dans le cas de recommandations classées par pertinence, cela revient à introduire un peu de bruit dans le classement pour faire remonter des suggestions qui ne seraient jamais visibles autrement. Cela permet de gagner quelques pour-cents de performance, tout en autorisant une implémentation plus rapide dès lors qu’on ne cherche pas un optimum théorique.

Un autre cas d’utilisation pertinent du dithering, est le bandit bayésien. Dans ce cas, le pouvoir d’exploration dépend de l’incertitude que l’on a sur la situation. Pour la recommandation publicitaire, en pratique, la technique du Thompson sampling s’avère efficace. [NDLR : voir cet article du blog sur la technique du bandit manchot en général, avec des commentaires sur le Thompson sampling]

Le clustering en ligne

Cette technique permet de faire du clustering de manière très performante, donc potentiellement en ligne sur de nouveaux échantillons qui arrivent au fil de l’eau. Le principe est de “compresser” un historique au moyen d’un algorithme de clustering comme le k-means, en le résumant ainsi à ses quelques centroïdes. Le classement des nouvelles données se fait alors sur un échantillon très petit, sans perte de précision notable.

Le “search abuse”

(le terme est de T.Dunning) Pour la recommandation, à nouveau : on utilise un moteur de recherche non pour indexer, mais pour capter un comportement utilisateur. Une requête sur le moteur, et le comportement résultant sur les documents présentés, deviennent des éléments de recommandation analogues à des “produits” (autrement dit on ne recommande plus les documents eux-mêmes mais les requêtes qui y conduisent, enfin c’est comme ça que je le comprends. Heureusement j’avais déjà vu une de ses présentations sur le sujet...).

L’idée derrière est, encore une fois, de proposer de nouvelles choses qui ne le seraient pas avec des algorithmes de recommandation habituels. Ces algorithmes proposent ce que le plus grand nombre a déjà vu, ce qui peut s’avérer restrictif à terme, et qui a aussi le désavantage d’être trop sensible aux comportements artificiels comme les bots.

Economies and diseconomies of scale for predictive analytics

(Zoltan Prekopcsak, Radoop)

La session part du constat que pour améliorer une prédiction on est confronté à 2 dilemmes :

• 1. améliorer les algorithmes ou obtenir plus de données
• et quand on a trop de données, face à la complexité démultipliée par le grand nombre de dimensions, 2) distribuer le calcul ou sous-échantillonner pour rester sur un seul noeud

La présentation énumère des approches de prédiction classiques (recommandation, clustering, etc.), avec à chaque fois l’opportunité de distribuer et des seuils empiriques à partir desquels c’est nécessaire. Nous les résumons ci-dessous.

Pour la recommandation

Il est préférable de récupérer plus de données, plutôt que de complexifier à l’extrême les algorithmes. Les algorithmes se distribuent bien donc il ne faut pas hésiter à le faire. Le seuil à partir duquel cela devient nécessaire se situe autour de 10 millions d’enregistrements.

Pour la détection d’anomalies

En supervisé, le sous-échantillonnage est possible, à condition de garder les proportions de cas normaux et anormaux. En approche non supervisée, conseillée, la distribution est possible à partir de 100 millions d’enregistrements.

Pour le clustering

Le calcul des moyennes (les centroïdes) est robuste au sous-échantillonnage, en revanche les intervalles de confiance s’élargissent rapidement avec le nombre de dimensions, autrement dit avec le nombre de variables d'entrée. L’heuristique donnée est la suivante :

• en-dessous de 100 millions d’enregistrements, un noeud suffit
• au-delà : si les clusters font moins de 10.000 points ou que le nombre de dimensions reste inférieur à 10, on peut sous-échantilonner sur un seul noeud. Autrement il faut distribuer

Pour la classification

Les arbres de décision calculant des seuils, ils supportent le sous-échantillonnage. Quant aux random forests, le sous-échantillonnage (en nombre d’échantillons comme en nombre de dimensions) est au coeur des implémentations. La comparaison des erreurs d’entraînement et de généralisation permet de savoir si on dispose d’assez de données dans l’échantillon, car elles sont censées converger vers une limite commune à mesure que la taille de l’échantillon augmente.

La règle donnée est la suivante : en-dessous de 100 millions d’enregistrements, un seul noeud de calcul suffit pour peu que la courbe d’apprentissage valide la taille de l’échantillon. Autrement il faut distribuer, ce qui n’est pas simple pour tous les algorithmes...

Personalizing live TV

(Ranadip Chatterjee, Optimo Cloud Consulting Ltd & Tamas Jambor, BSkyB)

Cette session avait pour but de présenter une méthode pour résoudre un problème a priori difficile : “désagréger” un foyer pour faire des recommandations individuelles, lorsque c’est possible, et des recommandations plus globales par ailleurs (quand toute la famille est réunie par exemple). Bien sûr, le tout sans connaître précidément la composition du foyer sinon c’est trop facile :-)

Ce qui rend la méthode intéressante, c’est la combinaison des approches fines servant à relever ce défi.

Dans les cas favorables, un croisement entre des micro-segments (démographie, géographie, … ainsi bien sûr que l’historique de choix et de visualisation), des canaux (télévision connectée, mobile, web), des habitudes temporelles sont autant de variables qui alimentent des profils appris. La notion de canal est importante car un mobile, contrairement à une télévision, est un objet personnel pouvant aider à affiner la désagrégation. Ainsi les profils existent à 2 niveaux (foyer et individus) et rentrent dans un moteur de recommandation. Il faut d’abord identifier la personne en fonction de son comportement présent et de ses habitudes (“fan de Untel”, “regarde la télé le week-end”, …), puis observer ses réactions pour continuer à apprendre. Le niveau “foyer” est en quelque sorte le niveau de recommandation par défaut lorsque l’individu n’a pas pu être reconnu avec assez de précision.

Pour les nouveaux profils, dont on ne connaît pas les habitudes, les réseaux sociaux sont une source d’initialisation.

Pour les nouveaux contenus, la recommandation s’appuie sur les méta-données desdits contenus (content-based recommendation).

Le but ultime est de proposer des chaînes de télévision personnalisées, s’appuyant sur un catalogue large (télévision, VOD, catch-up TV) et un ordonnanceur qui va enchaîner les contenus sans que la personne, harrassée par une longue journée de travail (ou abrutie par une gueule de bois persistante pourrait-on ajouter, ça arrive aussi), n’ait à chercher la télécommande…

En termes de technologies, la solution présentée s’appuie sur Mahout et du code Scala “maison”.