Introduction
Dans la plupart des problèmes d’apprentissage machine, nous supposons que, pour chaque caractéristique, les exemples sont tirés au hasard à partir de la même distribution, ce qui peut ne pas être le cas lorsqu’il existe une dépendance temporelle et que certains comportements et modèles dans les données disparaissent.
Dans ce travail, nous étudions le problème de l’apprentissage lorsque la distribution de probabilité change entre l’ensemble de formation et l’ensemble de test. Notre méthode fonctionne pour les variables catégorielles et les variables numériques. Il est basé sur un paradigme à deux fenêtres où la fenêtre de référence se dilate lorsque la dérive n’est pas détectée et à chaque étape par rapport à la fenêtre de test. Nous utilisons deux types de divergences pour la comparaison : Divergence Jensen-Shannon et distance Hellinger.
Apprentissage dans des environnements non stationnaires
Soit P le processus de génération de données de tuples (xt,yt) échantillonnés à partir d’une distribution inconnue pt(x,y). Nous définissons pt(y|x) et pt(x) respectivement le postérieur et l’évidence. Les probabilités varient dans le temps, d’où l’indice t.
Nous avons deux types de dérives dans les données :
- Dérive virtuelle : pt(x) change sans affecter la limite de décision de l’algorithme.
- Dérive réelle : pt(y|x) change indépendamment de pt(x).
Dans notre travail, nous nous concentrons sur la dérive réelle parce qu’elle peut diminuer les performances du classificateur et que ce dernier a donc besoin de mettre à jour les paramètres.
Discrétisation des variables numériques
Dans le processus de détection de dérive, nous calculons la divergence entre les distributions discrètes de deux fenêtres (deux ensembles de données) en prenant en entrée seulement des variables catégorielles. Par conséquent, si nous voulons utiliser des variables numériques, nous avons besoin de discrétisation.
Il existe différentes méthodes dans l’état de l’art de la discrétisation :
- Discrétisation basée sur l’entropie
- Discrétisation basée sur le quantile
- Discrétisation de taille fixe
Comme nous exigeons de l’algorithme qu’il soit indépendant de la cible et de la performance de tout classificateur dans son processus, nous choisissons l’approche par quantile.
Divergence entre deux distributions
Dans notre approche, nous avons besoin d’un moyen de mesurer la divergence entre deux distributions de probabilités discrètes données par les fréquences empiriques des catégories pour chaque variable.
- Divergence Kullback-Leibler
Soit P et Q deux distributions de probabilité et w € Ω.
Pour les distributions discrètes : KL(P \Vert Q) = \sum_{w} P(w) log \frac{P(w)}{Q(w)}{Q(w)}
Pour des distributions continues : KL(P \Vert Q) = \int_{-\infty}^{\infty} p(x) log \frac{p(x)}{q(x)}
La divergence KL n’est définie que si Q(w) = 0 implique P(w)=0, alors que P peut avoir des valeurs nulles car dans ce cas P(w) log(P(w)) =0, ce qui signifie que nous ne pouvons pas avoir les deux valeurs égales à zéro pour un même ‘w’.
- Jensen Shannon Divergence
Comme nous pouvons le voir, la divergence KL n’est pas symétrique et n’est pas toujours définie comme indiqué ci-dessus. Pour résoudre ces problèmes, nous définissons la divergence symétrique de Jensen-Shannon comme :
JS(P \Vert \Vert Q) = \frac{1}{2} KL(P \Vert M) + \frac{1}{2} KL(Q \Vert \Vert M) where M = \frac{P+Q}{2}
Cela résout le problème d’avoir q(w)=0 et p(w) ≠ 0.
De plus, 0 ≤ JS ≤ 1 si on utilise le logarithme binaire dans la divergence KL et 0 ≤ JS ≤ ln(2) si on utilise le logarithme naturel à la place.
- Distance Hellinger
Soit P et Q deux distributions de probabilité et w € Ω.
Pour les distributions discrètes :
0 \geq H(P,Q) = \frac{1}{\sqrt{2}} \sqrt{\sum_{w} (\sqrt{p(w)} - \sqrt{q(w)} )} \leq 1Aussi :
1 - H(P,Q)^2 = \sum_{w} \sqrt{p(w) q(w)}La méthode de détection de dérive
Nous supposons que les données arrivent par lots comme dans l’apprentissage en ligne, ce n’est pas le cas dans notre problème mais nous pouvons facilement les adapter en divisant les données en lots (n_batch est le nombre de points à considérer dans chaque lot). Le choix de la distance Hellinger est également motivé par sa propriété de symétrie.
L’algorithme est basé sur un seuil adaptatif qui est utilisé pour décider si le changement doit être marqué comme dérive.
Comme nous l’avons déjà dit, les données sont censées arriver par lots. Soit \tau la position du lot où la dérive a été détectée et D_{\tau} le lot/la fenêtre qui correspond. Nous initialisons par paramétrage : D_{\tau} = D_1 et \tau= 1. Nous calculons la distance Hellinger entre la fenêtre de référence D et la fenêtre réelle :
d_h(t) = \frac{1}{d}{d} \sum_{feature} H( P_{feature} - Q_{feature}). Où d est le nombre de caractéristiques prises en compte.
Ensuite, nous calculons \epsilon(t) = d_h(t) - d_h(t-1) et le comparons au seuil.
Deux scénarios peuvent se produire :
\text{La dérive n'est pas détectée :} On étend D_{\tau} en le fusionnant avec le lot suivant, \tau est inchangé.
\text{La dérive est détectée :} Nous changeons la fenêtre de référence en fenêtre réelle, nous réglons \tau [\latex] à la position réelle et mettons à jour le seuil.
