Courbe ROC#

Ce document introduit la courbe ROC (Receiving Operator Characteristic) qui est communément utilisée pour mesurer la performance d’un classifieur. Il introduit aussi des termes comme précision, rappel, AUC, qui sont présents dans la plupart des articles qui traitent de machine learning. Le module roc implémente les calculs ci-dessous qu’on peut tester avec le notebook ROC.

Définitions#

Supposons que nous avons un classifieur qui classe des observations en un ensemble de classes. De plus, il donne cette réponse accompagnée d’un score de pertinence. Deux cas sont possibles : soit la réponse est bonne (1), soit la réponse est fausse (0). Pour chaque observation, on associe un couple (r,x) où r est égal à 0 ou 1. x est le score de pertinence. On cherche à déterminer à partir de quel seuil de pertinence, la réponse du classifieuur est fiable. En faisant varier x, on obtient une courbe (source : wikipedia) :

../_images/Roccurves.png

Cette courbe sert également à comparer différents classifieurs. Plus une courbe a des valeurs élevées, plus l’aire sous la courbe est grande, moins le classifieur fait d’erreur.

D’une manière simplifiée, le classifieur retourne une réponse qui est soit mauvaise (-) soit bonne (+). On peut l’évaluer car pour construire un classifier on dispose toujours d’une base contenant les réponses attendues. En fonction du score x et d’un seuil s, on définit quatre cas :

cas

réponse prédite est bonne (+)

réponse prédite est mauvaise (-)

x \supegal s

TP: vrai (true) positif

FP: faux positif

x < s

TN: vrai (true) négatif

FN: faux négatif

Ces résultats sont souvent présentés selon une matrice confusion :

réponse attendue

0

1

0

TN

FP

1

FN

TP

A partir de ces définitions, on définit :

En choisissant un seuil relatif au score de pertinence x, au-dessus, on valide la réponse du classifieur, en-dessous, on ne la valide pas. On peut toujours calculer la précision et le rappel pour toutes les réponses dont le score est au-dessus d’un seuil s. La courbe ROC s’obtient en faisant varier s.

Définition D1 : Courbe ROC

On suppose que Y est la variable aléatoire des scores des expériences qui ont réussi. X est celle des scores des expériences qui ont échoué. On suppose également que tous les scores sont indépendants. On note F_Y et F_X les fonctions de répartition de ces variables. F_Y(s)=\pr{Y \infegal s} et F_X(s)=\pr{X \infegal s}. On définit en fonction d’un seuil s \in \R :

  • R(s) = 1 - F_Y(s) = \pr{Y > s}

  • E(s) = 1 - F_X(s) = \pr{X > s}

La courbe ROC est le graphe \pa{E(s),R(s)} lorsque s varie dans \R.

TP(s) désigne les true positifs au-dessus du seuil s, avec les notations TP, FP, FN, TN, cela revient à :

\begin{eqnarray*} E(s) &=& 1 - \frac{ TP(s) } { TP(s) + TN(s) } \\ R(s) &=& 1 - \frac{ FN(s) } { FP(s) + FN(s) } \end{eqnarray*}

On remarque que \forall s, \; TP(s) + TN(s) est constant. De même pour FP(s) + FN(s).

../_images/rocwi.png

On remarque que les fonctions s \longrightarrow E(s) et s \longrightarrow R(s) sont décroissantes toutes deux. Elles sont donc inversibles. Dans le cas où la variable aléatoire \theta est indépendante de la variable X, la courbe ROC est une droite reliant les points (0,0) et (1-p,p) où p = \pr{\theta=1}. Ceci signifie que la connaissance du score X n’apporte pas d’information quant à la réussite de l’expérience.

Il peut paraître complexe de distinguer la réponse et le score du classifieur. C’est pourtant nécessaire dans le cas où le classifieur retourne un entier qui désigne une classe parmi n. Un cas positif est lorsque la classe prédite est égale à la classe attendue, il est négatif dans le cas contraire. La courbe peut être adaptée pour d’autres problèmes tels que le ranking (voir [Agarwal2005]).

Une autre façon de l’exprimer car je ne retiens jamais la définition des FP, TP, FN, TN… Pour quelqu’un qui doit réfléchir trois secondes à chaque fois qu’on me demande où est la gauche, ce n’est jamais évident.

\begin{array}{rcl} N_+ &=& \sum_{i=1}^n \indicatrice{y_i == 1}\\ TPR(s) &=& \frac{1}{N_+}\sum_{i=1}^n \indicatrice{score(X_i) \geqslant s}\indicatrice{y_i == 1}\\ FPR(s) &=& \frac{1}{1 - N_+}\sum_{i=1}^n \indicatrice{score(X_i) \geqslant s}\indicatrice{y_i \neq 1} \end{array}

x = FPR(s), y = TPR(s). (FPR = False Positive Rate, TPR = True Positive Rate)

../_images/rocwi2.png

Aire sous la courbe#

Expression#

L’aire sous la courbe (AUC) correspond à l’intégrale de la fonction ROC. Elle se calcule à partir du théorème suivant :

Théorème T1 : Aire sous la courbe (AUC)

On utilise les notations de la définition de la Courbe ROC. L’aire sous la courbe ROC est égale à \pr{ Y > X}.

Rappel

Soit X une variable aléatoire de densité f et de fonction de répartition F. Si U = F(X), alors :

\pr{ U \infegal t} = \pr{ F(X) \infegal t} = \pr{ X \infegal F^{-1}(t)} = F \pa{ F^{-1}(t) } = t

La variable U est de loi uniforme sur \cro{0,1}. De plus, soit g une fonction intégrable quelconque, on pose u = F(x) et :

\int_{\R} g(x) \, f(x) \,dx = \int_{\cro{0,1}} g(F^{-1}(u)) \, du

Démonstration

On note f_X la densité de la variable X et f_Y celle de la variable Y. On peut alors définir la probabilité \pr{ Y > X} par une intégrale :

\begin{eqnarray*} P \pa{Y>X} &=& \int_x \int_y f_X(x) \; f_Y(y) \; \indicatrice{y > x} dx dy \end{eqnarray*}

On note F_X la fonction de répartition de X soit F_X(x) = \int_{-\infty}^x f_X(u)du. On pose comme changement de variable : u = F_X(x). On en déduit que du = f_X(x) dx. La variable aléatoire U = F_X(X) est uniforme et comprise dans \cro{0,1}.

\begin{eqnarray*} P \pa{Y>X} &=& \int_x f_X(x) dx \int_y \; f_Y(y) \; \indicatrice{y > x} dy \\ &=& \int_u du \int_y \; f_Y(y) \; \indicatrice{y > F_X^{-1}(u)} dy \\ &=& \int_u du \; \pr{Y > F_X^{-1}(u)} \nonumber \end{eqnarray*}

Or si u = F_X(s) = E(s), alors F_X^{-1}(u) = s et \pr{Y > F_X^{-1}(u)} = R'(s). Par conséquent :

P \pa{Y>X} = \int_u du \; \pr{Y > F_X^{-1}(u)} = \int_u du \; R'(F_X^{-1}(u))

Cette dernière expression est l’aire recherchée. Ce théorème nous permet de définir un estimateur pour l’aire sous la courbe ROC à l’aide des U-statistiques de Mann-Whitney (voir [Saporta1990]).

Corollaire C1 : Estimateur de l’aire sous la courbe ROC

On dispose des scores \vecteur{Y_1}{Y_n} des expériences qui ont réussi et \vecteur{X_1}{X_m} les scores des expériences qui ont échoué. On suppose également que tous les scores sont indépendants. Les scores (Y_i) sont identiquement distribués, il en est de même pour les scores (X_i). Un estimateur de l’aire A sous la courbe ROC” est :

(1)#\hat{A} = \frac{1}{nm} \; \sum_{i=1}^{m}\sum_{j=1}^{n} \pa{\indicatrice{ Y_j > X_i} + \frac{1}{2} \indicatrice{ Y_j = X_i}}

Démonstration

La démonstration est évidente :

\esp\pa{\hat{A}} = \frac{1}{nm} \; \sum_{i=1}^{m}\sum_{j=1}^{n} \pa{\pr{ Y_j > X_i} + \frac{1}{2} \pr{X_i=Y_j}} = \pr{ Y > X} + \frac{1}{2}\pr{ Y = X}

Dans le cas où X ou Y sont continues, \pr{X=Y} = 0.

Intervalles de confiance#

Il est possible de déterminer un intervalle de confiance pour cet estimateur. Le théorème central limite nous permet de dire que cet estimateur tend vers une loi normale lorsque n et m tendent vers l’infini.

Corollaire C2 : Variance de l’estimateur AUC

On note P_X = \pr{ X < \min\acc{Y_i,Y_j }} et P_Y = \pr { \max\acc{X_i,X_j} < Y}. X_i et X_j sont de même loi que X, Y_i, Y_j sont de même loi que Y. La variance de l’estimateur \hat{A} définie par (1) est :

\var{\hat{A}} = \frac{ \hat{A} (1-\hat{A})}{nm} \; \cro{ 1 + (n-1) \frac { P_Y - \hat{A}^2 } { \hat{A} (1-\hat{A}) } + (m-1) \frac { P_X - \hat{A}^2 } { \hat{A} (1-\hat{A}) } }

Démonstration

Cette démonstration n’est vraie que dans le cas continu. Par conséquent, \pr{X=Y} = 0. On calcule tout d’abord \esp{\hat{A}^2} et on utilise le fait que \var{\hat{A}} = \esp\pa{\hat{A}^2} - \hat{A}^2.