Multi-armed bandits for non-stationary data streams
Bandits Manchots sur Flux de Données Non Stationnaires
Résumé
Online Classification on data streams allows to learn on large volumes with controlled treatment costs and to manage non stationarity within the process generating data. Within a BigData context, online classification can be an alternative to classic data mining approach with high treatment costs. Within a FastData context, online classification is crucial to quickly react to stationarity changes. In CRM, the context changes frequently, per example, the availability of a new offer can disturb the subscription rate. There is several option to handle non-stationarity within the data stream. The first consider two different problems: the drift detection within the data stream and the learning of an online model. The principal weakness of this approach is the assumption of local stationarity. If local stationarity does not exist, algorithm does not have any guarantee. The second approach is to use stochastic models able to adapt online to non stationarity of the data stream. This adds a trade-off between a fast learning, with the creation of an inaccurate model reacting quickly to changes and a more accurate model but reacting slowly to changes. A way to combine the two approaches can be to use multi-experts system, like EXP3. Guarantees on such system exist with non assumption on the data distribution. A promising approach is to use an hybrid approach, construction these experts and selecting the best one during the run.
La classification en ligne sur des flux de données permet d'apprendre sur de très grands volumes avec des coûts de traitements maîtrisés, et de prendre en compte la non stationnarité des processus générant les données. Dans un contexte BigData, la classification en ligne est une alternative séduisante au processus classique de data mining, qui demande de grandes capacités de traitements pour construire le datamart utilisé par le modèle de classification. Au-delà du contexte BigData, la classification en ligne est un enjeu crucial lorsque l'on veut réagir au plus vite à des événements de contexte. Dans le CRM, il n'est pas rare que le contexte change. Par exemple, l'arrivée d'une nouvelle offre Orange ou d'une offre d'un concurrent, peut perturber le taux de souscription de toutes les campagnes marketing. Il y a plusieurs options possibles pour prendre en compte la non-stationnarité du flux de données. Une première approche consiste à considérer deux problèmes séparément : la détection d'une rupture de stationnarité dans les performances du modèle où sur les données elles-mêmes, et l'apprentissage de modèles en ligne sur les périodes stationnaires. Le défaut principal de cette approche réside dans l'existence d'un régime stationnaire par morceau. S'il n'existe pas, les garanties de performances n'existent pas non plus. Une autre approche est d'utiliser un modèle qui prend en compte la non stationnarité des données. L'utilisation d'un algorithme d'apprentissage stochastique permet de s'adapter en ligne aux évolutions des données. Se pose alors le problème du réglage entre la vitesse de convergence de l'algorithme stochastique et la vitesse d'évolution des processus générant les données. Un modèle trop lent ne prendrait pas en compte les évolutions des processus, et un modèle trop rapide n'apprendrait que du bruit. Afin de combiner les avantages des deux premières approches, il est possible d'utiliser des systèmes multi-experts, comme Exp3, sur lesquels nous avons des garanties sur des données non stationnaires, ici les performances des experts, pour minimiser le regret entre la performance du meilleur expert et l'expert choisi. Reste que les experts eux-mêmes ne fonctionnent que sur des périodes stationnaires, et que la performance sera dépendante du nombre et de l'a priori sur les experts. Une approche prometteuse est d'utiliser ce type d'algorithme non seulement pour tirer mais aussi pour construire les meilleurs experts. L'avantage est de contrôler la ressource nécessaire à construction des experts en fonction de la performance attendue.