Frères Peyronnet

Veille technologique & Référencement web

Dimanche

3

mars 2013

1

COMMENTAIRES

A/B testing et bandits manchots

Ecrit par , Publié dans Théorie

Un article heureux est un article partagé !Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

Voici le deuxième article que j’avais mis dans ma première newsletter.

Dans cet article,  je vais présenter ce qu’est le A/B testing (également appelé split testing). Puis je vous parlerais un petit peu des bandits manchots, qui est une méthode statistique plus
adaptée que le A/B testing pour faire la même chose ou presque, mais en mieux. Une partie de cet article est une reprise d’un des mes billets sur ce blog (bouh le gros re-use).

L’A/B testing permet de choisir parmi plusieurs modifications de votre site celle qui maximisera un certain critère (taux de conversion, durée de la visite etc.).  Le concept derrière le A/B testing est complètement idiot : il s’agit de couper aléatoirement ses visiteurs en plusieurs groupes, et de fournir à chaque groupe une expérience utilisateur différente. Un groupe sera appelé le groupe de contrôle (groupe A), il est constitué des visiteurs de votre site qui navigueront sur le site classique. Un autre groupe, noté B, aura lui une version différente du site. Pour chacun de ses groupes, on mesure le critère, la version de votre site qui donne la meilleure valeur au critère est celle que vous mettrez en place.

Pour mieux comprendre ce qu’est le A/B testing, prenons un exemple. Imaginez que vous ayez un site de vente de livres et que le bouton d’achat soit un bouton tout bête avec le mot « Acheter » en noir sur fond blanc.  Vous voulez savoir si en faisant clignoter le texte « Acheter » avec une couleur fluo vous aurez un meilleur taux de clics. Pour cela vous allez faire un A/B test : 90% de vos visiteurs restent avec le bouton classique tandis que 10% ont le bouton avec le texte en vert fluo clignotant.  Vous attendez un peu, et au bout de quelques temps, vous regardez le résultat.  par exemple, vous avez eu 10000 visiteurs, et les résultats sont les suivants :

  • Groupe A : 9000 VU, 180 clicks (2 %)
  • Groupe B : 1000 VU, 10 clicks (1 %)

La conclusion naturelle qui va être la votre sera : je garde le bouton comme il est car le taux est meilleur.

Vous êtes pourtant peut-être en train de faire une erreur en concluant que l’un des choix est meilleur que l’autre alors que la différence peut être due à une variation tout à fait normale des variables aléatoires. Cela arrive dans un cas très balisé : celui où la taille de l’échantillon est trop petite pour que, dans la cas d’une différence de valeurs faibles sur le critère, l’on puisse avoir une conclusion significative. Il faut donc s’interroger sur la taille minimale de l’échantillon.

Tout est une histoire de précision et de confiance. Ce que l’on souhaite, c’est estimer de manière suffisamment précise la valeur obtenue pour chacune des possibilités. Imaginons que le critère soit noté C. C(A) est la valeur réelle du critère pour le choix A (avec un nombre infini de visiteurs), C(B) est la même chose pour B. On a : C(A) - C(B) = P, Cela signifie que P/2 est la précision suffisante pour départager les hypothèse A et B. En effet, on ne peut pas calculer exactement C(A) et C(B) car les échantillons ne peuvent être de taille infinie. Ce que l’on va calculer est E(A) et E(B), une valeur estimée (c’est-à-dire approchée) de C(A) et C(B). Cela signifie que l’on va obtenir E(A) avec la propriété espérée que :

C(A) - \varepsilon \leq E(A) \leq C(A) + \varepsilon

C’est bien sur pareil pour E(B) et C(B).

\varepsilon est appelé la précision de notre processus de test. Par ailleurs, comme notre approche tire au hasard les visiteurs, il y a une certaine probabilité d’erreur (le cas où l’on ne tire que les « mauvais » visiteurs lors du tirage aléatoire). Cette probabilité est notée \delta. Au final, on voudrait donc un échantillon de taille suffisante pour garantir que :

Proba~ (C(A) - \varepsilon =< E(A) =< C(A) + \varepsilon) > 1 - \delta

Typiquement, \delta est de l’ordre de 5% dans la littérature marketing (en sciences dures, où les mêmes outils servent à estimer la correction de systèmes informatiques, on prend 0,00000001 %). \varepsilon va dépendre de la précision requise pour départager les hypothèse, mais souvent on va utiliser un processus adaptatif (on choisit \varepsilon=10\%, puis si ça ne suffit pas on prend 1%, puis etc….)

Y a t-il une formule qui donne la taille de l’échantillon en fonction des \varepsilon et \delta ? Oui, bien sur. Il y en a même une quantité industrielle, elles dépendant des hypothèses sur les probabilités de choix des utilisateurs, on appelle cela des inégalités de concentration et autres joyeusetés. Pour ma part j’utilise la borne de Chernoff-Hoeffding, borne overkill pour ce genre d’utilisation, mais qui fonctionne. La formule nous dit alors :

Taille~(echantillon)=(ln(2/\delta))/2\varepsilon^2

Par exemple, si delta = 5%, et epsilon=0,5%, on obtient Taille(echantillon)= 74000. Cela prouve que dans l’exemple précédent la décision prise est potentiellement mauvaise car il faudrait que la taille du groupe B soit de au moins 74000 visiteurs. Pour \delta=5% et \varepsilon=5%, on aurait une taille de 740, ce qui est plus simple a obtenir.

Ce qu’il faut retenir concernant le A/B testing, c’est que c’est une technique qui permet de choisir entre plusieurs alternatives en estimant l’impact d’un choix sur un critère quantifiable. Il y a de  nombreux problèmes de mise en place : pour que la conclusion soit valable, il faut que les possibilités étudiées soient données au hasard aux visiteurs, il faut que les hypothèses soient non corrélées, etc. Mais une autre barrière est que le A/B testing c’est du one shot / 2 steps. One shot car si on veut rajouter en cours des routes des hypothèses supplémentaires il faudra tout recommencer. Et 2 steps car il y a une phase d’étude, puis une phase d’exploitation du résultat. Ce qui paraitrait plus raisonnable, c’est un algorithme où je fais une liste des hypothèses qui sont à considérer, et qui va en même temps choisir la ou les meilleures hypothèses, les utiliser et permettre d’en rajouter des nouvelles.

Et bien cette méthode algorithmique existe. Il s’agit de la méthode des bandits manchots. Dont je vais vous esquisser le principe ici. Les deux principales caractéristiques de la méthode sont les suivantes : il peut y avoir autant d’options qu’on le souhaite, et qu’on peut rajouter ou enlever des options en temps réel.

Le nom de bandits manchots vient bien du monde des casino. Imaginez que vous soyez devant plusieurs machines, quelle est votre stratégie pour gagner le plus possible ? Ce qu’il faut faire c’est jouer le plus souvent sur les machines qui vous rapporte le plus, et de temps en temps essayer les autres machines pour voir si elles se mettent à rapporter plus. Ce procédé, que l’on appelle exploration–exploitation est le coeur de la technique des bandits manchots.

La figure suivante vous résume la méthode :

Lorsqu’un visiteur arrive sur le site, vous tirer au hasard entre l’exploration et l’exploitation. Ici j’ai mis 10%, mais en pratique cette valeur commence plus haut (50% par exemple) afin de tester rapidement toutes les hypothèses, puis décroit ensuite pour maximiser l’exploitation.  Lorsque l’on est en phase d’exploration, on tire au hasard une des hypothèses et on met à jour la valeur de la mesure correspondante (le taux de clics par exemple). Lorsque l’on est en phase d’exploitation on fournit à l’utilisateur la meilleure hypothèse.

Plus le nombre de visiteurs augmente, plus les valeurs de chaque hypothèse calculées à l’aide des bandits manchots sont proches des vraies valeurs. Bien sur je passe sous silence tous les aspects techniques, mais vous pouvez également retenir que ce qui est important c’est la gestion de la proportion exploration-exploitation. Maintenir un taux constant (par exemple 10%) correspond à ce que l’on appelle la stratégie \varepsilon-gloutonne) tandis qu’avoir un taux de 100% au début puis le faire décroitre à 0% est ce que l’on appelle une stratégie \varepsilon-first. Cette dernière correspond au A/B testing standard.

Il existe des stratégies beaucoup plus complexes et plus efficaces, mais dans le contexte d’une application au web, il est inutile de les utiliser.

En guise de conclusion, je vous rappelle que la méthode des bandits manchots n’a que des avantages. Elle travaille en continu, tant pour l’exploration que pour l’exploitation. On peut rajouter et enlever des hypothèses en permanence. Et enfin, elle s’adapte au changement : votre audience change, la méthode le détecte et s’adapte.

Un article heureux est un article partagé !Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

1 Commentaire