Introduction
La régression quantile
QRANN
Expériences
Conclusion

La régression quantile
Et comment l’améliorer avec des réseaux de neurones
Adam Salvail
Adam.Salvail@USherbrooke.ca
BISOUS / SMART
Département d’informatique
Université de Sherbrooke

27 février 2015

Adam SalvailRégression quantile

1/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

Sommaire de la présentation
1

Introduction

2

La régression quantile
La régression standard
Vers une généralisation aux quantiles
Algorithmes de régression quantile

3QRANN
Le modèleLes détails
L’entrainement du modèle4Expériences
La méthodologie de test

5Conclusion
Adam SalvailRégression quantile

2/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

La régression en apprentissage automatique

Deux grands domaines de l’apprentissage automatique :la classification ;la régression.
Que recherche-t-on en régression ?
La moyenne (distance L2 ) ;La médiane (distance L1 ) ;Les paramètres d’une distribution.

Adam SalvailRégression quantile

3/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

Citation

Henri Poincaré aurait dit :Everyone believes in the [Gaussian] law of errors, theexperimenters because they think it is a mathematical theorem, themathematicians because they think it is an experimental fact. 

Adam SalvailRégression quantile

4/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

La régression quantile

Roger Koenker et Gilbert Bassett Jr. (1978) apporte unealternative : la régression quantile.
C’est une méthode non-paramétrique ;Peut facilement donner une prédiction de la médiane ;Peut également donner de une idée générale de la forme de ladistribution.

Adam SalvailRégression quantile

5/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

Exemple de régression quantile

Adam SalvailRégression quantile

6/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

Motivation : Récentes avancées en réseaux de neurones

Depuis 2006, les réseaux de neurones ont fait un retour en force !
Initialization judicieuse des paramètres ;Meilleure régularisation (Dropout, Maxout) ;Innovation au niveau des fonctions d’activation ;Meilleurs algorithmes d’optimisation stochastique.

Adam SalvailRégression quantile

7/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

La régression standard
Vers une généralisation aux quantiles
Algorithmes de régression quantile

La régression usuelle
Nous étudions un phénomène modélisé par une distribution D.
Soit (X, Y) ∼ D un échantillon de D où x ∈ X est un vecteur devariables explicatives et y ∈ Y la valeur à prédire.

1 X
L2 (fθ (x), y )|X|θx∈X
1 X
Médiane [P(y |x)] ≈ fθ∗ (x) ⇔ θ ∗ = arg min
L1 (fθ (x), y )|X|θE [P(y |x)] ≈ fθ∗ (x) ⇔ θ ∗ = arg minx∈XAdam SalvailRégression quantile

8/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

La régression standard
Vers une généralisation aux quantiles
Algorithmes de régression quantile

Quantiles

Un quantile Qτ se définit comme suit :Qτ (D) = inf{d : FD (d) ≥ τ }où FD (d) = P(D ≤ d) est la fonction de répartition de D.
Notez que Q0.50 (D) est la médiane de D.

Adam SalvailRégression quantile

9/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

La régression standard
Vers une généralisation aux quantiles
Algorithmes de régression quantile

Exemple d’utilisation des quantiles

En finance, une utilisation intéressante des quantiles (et de larégression quantile) est donnée par la valeur à risque.
VaRτ (L) = Q1−τ (L)Cette valeur représente le seuil que la perte monétaire encourruedépassera avec probabilité τ .

Adam SalvailRégression quantile

10/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

La régression standard
Vers une généralisation aux quantiles
Algorithmes de régression quantile

La fonction de perte machine à bouleDans leur travail séminal de 1978, Koenker et Bassett Jr. ont
introduit la pinball loss function, librement traduite par la fonctionde perte machine à boule.
On la dénote Lτ pour τ ∈ (0, 1).
(τxsi x ≥ 0Lτ =(τ − 1)x sinon.

Adam SalvailRégression quantile

11/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

La régression standard
Vers une généralisation aux quantiles
Algorithmes de régression quantile

Exemple de la fonction de perte machine à boule

La perte L0.25 .

La perte L1 .

Adam SalvailRégression quantile

12/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

La régression standard
Vers une généralisation aux quantiles
Algorithmes de régression quantile

Preuve de la convergence vers les quantiles
Soit d ∼ D. On cherche Qτ (D). On montre que :Qτ (D) = arg min ED [Lτ (d − x)].
x

Le membre de droite se réécritZ x
Z ∞arg min(τ − 1)d − x dFD (d) + τ
d − x dFD (d).
x−∞xEn prenant la dérivé par rapport à x, on retrouve
Z x
Z ∞−(τ − 1)
dFD (d) − τdFD (d) = FD (x) − τ.
−∞xAdam SalvailRégression quantile

13/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

La régression standard
Vers une généralisation aux quantiles
Algorithmes de régression quantile

Preuve de la convergence vers les quantiles (suite)

Supposons que x ∗ = Qτ . Alors,FD (Qτ ) = τ.
Donc, Qτ est un point stationnaire de Lτ (d − x).
Comme la dérivée de FD (x) est la fonction de densité de D, elle
est toujours positive. Par conséquent, Qτ est vraiment la valeur qui
minimise la fonction de perte machine à boule.

Adam SalvailRégression quantile

14/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

La régression standard
Vers une généralisation aux quantiles
Algorithmes de régression quantile

Version linéaire de la régression quantile

Le modèle original introduit par Koenker et Bassett tentait detrouverβ ∗ = arg min E[Lτ (Y − X β)]β∈RkPour y arriver, ils reformulaient le problème comme un programmelinéaire qui pouvait ensuite être résolu par simplexe.

Adam SalvailRégression quantile

15/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

La régression standardVers une généralisation aux quantiles
Algorithmes de régression quantile

Versions non-linéaire de la régression quantile

Voici quelques travaux tentant d’utiliser un modèle non-linéaire :Taylor (2001) : Utilisation d’un réseau de neurones simple ;Koenker et al. (2005) : Modèle non-linéaire utilisant dessplines ;Takeuchi et al. (2005) : Utilisation de SVM comme modèle ;Meinshausen (2006) : Modèle utilisant des forêts d’arbrealéatoire (Random Forests) ;Boukouvalas et al. (2012) : Utilisation de processus gaussiens.

Adam SalvailRégression quantile

16/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

Le modèleLes détails
L’entrainement du modèleRéseau de neurones
Soit (X, Y) un échantillon de notre distribution D.
On cherche le meilleur vecteur de paramètres θ pour le modèlefθ (X) qui pourra le plus précisément prédire Qτ (D).
Un réseau de neurones est une successions de couches qui prennent
une entrée, lui applique une transformation linéaire, puis une
fonction d’activation non-linéaire. La k-ième couche peut se décrirecomme :
zk = σ(Wk zk−1 + bk )où Wk , bk ∈ θ sont les paramètres à optimiser et σk est une
fonction d’activation.
En posant z0 = x, on définit le modèle fθ (x) = zn .
Adam SalvailRégression quantile

17/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

Le modèleLes détails
L’entrainement du modèleFonctions d’activations
Le choix de la fonction d’activation s’avère être crucial pourl’entrainement d’un réseau de neurones. Voici quelques choix :sigmoı̈de : 1+e1 −x ;tangente hyperbolique : tanh(x) ;Rectified Linear Unit : max(0, x) ;Leaky Rectified Linear Unit : max(0, x) + 0.01 min(0, x) ;Parametrized Rectified Linear Unit : max(0, x) + α min(0, x).

Récents développements
Un article de Microsoft, paru la semaine passée, a utilisé la PReLU
sur ImageNet pour obtenir des résultats supérieurs à ceux d’unhumain !
Adam SalvailRégression quantile

18/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

Le modèleLes détails
L’entrainement du modèleDropout
Afin d’éviter le surentrainement, il faut régulariser les paramètres
du modèle que l’on entraine. Pour y arriver, plusieurs méthodess’offrent à nous :Ajouter une pénalité λkθk à la fonction de perte ;Ajouter un bruit aléatoire aux entrées : z0 = x + N(0, σ) ;Utiliser Dropout (ou Maxout, ou DropConnect).

Récents développements
Un article de Google, paru la semaine passée, a utilisé une
technique appelée batch normalization afin d’obtenir des résultats
semblables à ceux de Microsoft et pouvant remplacer (et de façonplus efficiente) Dropout.
Adam SalvailRégression quantile

19/ 25

Introduction
La régression quantileQRANN
Expériences
Conclusion

Le modèleLes détails
L’entrainement du modèleDifférentiation automatique et gradients

Pour arriver à optimiser les paramètres du réseau de neurones, onutilise le gradient de la fonction de perteX
1Lτ (fθ (x), y ) .
∇θ 
|X|(x,y )∈(X,Y)

Pour ce faire, la différentiation automatique est très utile !
Dans le domaine des réseaux de neurones, la différentiation
automatique porte parfois le nom de backpropagation.

Adam SalvailRégression quantile

20/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

Le modèleLes détails
L’entrainement du modèleProblèmes de non-différentiabilitéLa fonction de perte machine à boule a un grand défaut : elle est
non différentiable en x = 0.
Pour contrer le problème, plusieurs solutions :utiliser un algorithme robuste aux points denon-différentiabilité ;lisser la fonction de perte ;faire semblant que le problème n’existe pas, celui-ci n’étant
presque jamais un problème.
La dernière solution fonctionne étonnament bien !

Adam SalvailRégression quantile

21/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

Le modèleLes détails
L’entrainement du modèleEntrainement du modèlePour entrainer le modèle, on utilise un algorithmes d’optimisation.
SGD La descente de gradient (stochastique). Très simple
et couramment utilisé en apprentissage automatique.
Elle suit la direction de plus forte descente.
AdaGrad Plus récent, ajuste individuellement chaque dimension
du gradient en fonction des gradients antérieurs.
Adam Basé sur AdaGrad, Adam généralise le concept mis del’avant par AdaGrad de modifier chaque dimension
du gradient en prenant également en considération lesecond moment de la fonction.
L-BFGS Algorithme d’approximation de la dérivée seconde dela fonction objectif. Utilise l’information ainsi
approximer pour corriger la direction dans laquelle
faire un pas.
Adam SalvailRégression quantile

22/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

La méthodologie de testÉvaluation d’un modèleIl existe quelques problèmes liés à la régression quantile.
Contrairement à la régression usuelle, la perte optimale n’est
pas zéro.
Pire, on ne connait pas la vraie valeur des quantiles de ladistribution conditionnelle.
Pour évaluer la performance de notre prédicteur de quantiles, onutilise donc deux critères :La fonction de perte machine à boule ;La ramp loss qui calcul la distance L1 moyenne entre lesquantiles marginaux de Y et de fθ (X).

Adam SalvailRégression quantile

23/ 25

Introduction
La régression quantile
QRANNExpériences
Conclusion

La méthodologie de test

Expériences et résultats
Plusieurs tests de comparaison :Modèle QRANN, quantregForest, kqr, qrnn ;Données Boston housing, Communities and crimes, Power
plant output, Million songs dataset, South Australia
Electricity Demand et Wine quality.
Pour QRANN, nous avons également testé différentes combinaisonsde topologie, fonction d’activation, lissage, régularisation etalgorithme d’optimisation.

Résultats
Malheureusement, toutes ses expériences sont en cours de calcul
sur Mammouth. Sur les tests préliminaires, QRANN est compétitifou surpasse ses concurants.
Adam SalvailRégression quantile

24/ 25

Introduction
La régression quantile
QRANN
Expériences
Conclusion

Conclusions et futurs directions de recherche
En conclusion :La régression quantile s’avère être un puissant outil deprédiction.
QRANN est, a priori, une méthode compétitive et moderne derégression quantile.
Surtout, QRANN est assez efficace pour être entrainé sur degrands jeux de données (Million songs dataset), alors que lesperformances de ses plus proches compétiteurs se dégradent
rapidement avec la taille de l’échantillon.
La prochaine étape : passer à un modèle temporel de régression
quantile. Les prédictions du domaine des séries chronologiques
profitent vraiment de l’information additionnelle apportée par larégression quantile.
Adam SalvailRégression quantile

25/ 25