[PDF] Receiving Operator Characteristic (ROC) pdfauthor=Xavier Dupré

P(maxfXi;Xkg< Yj) +

P(Xi ^A2 V ^A2 =1nm h^A+ (n1)PY+ (m1)PX(n+m+ 1)^A2i 1nm h^A+ (n1) P Y^A2 + (m1) P X^A2 +^A2i

On retrouve l"expression cherchée.

(6) ut

3 Intervalles de confiance pour la courbe

Les systèmes de reconnaissance sont souvent ajustés de telle manière que le taux d"erreur soit

constant, par exemple 1%. C"est la proportion de documents reconnus qui détermine la performance

de ce système. L"objectif ce paragraphe est de déterminer un intervalle de confiance du taux de

reconnaissance pour un taux d"erreur fixé. 5

3.1 Construction de la courbe ROC

Ce premier paragraphe détaille la manière dont est construite une courbe ROC (voir définition 1).Algorithme 7 : courbe ROC

On suppose qu"on dispose d"un ensemble de points(Xi;i)2Rf0;1gpouri2 f1;:::;ng. X

iest le score obtenu pour l"expériencei,ivaut 1 si elle a réussi et 0 si elle a échoué. On

suppose également que cette liste est triée par ordre croissant :8i; Xi6Xi+1. On souhaite également tracerkpoints sur la courbe, on détermine pour celakseuilsfs1;:::;skgdéfinis par :8j;sk=Xj kn On construit ensuite les points(Rj;Ej)définis par : R j=1n n X i=1 i11fXi>sjgetEj=1n n X i=1(1i)11fXi>sjg(6) La courbe ROC est composée de l"ensembleROC=f(Ej;Rj)j16j6kg.

Les deux suites(Rj)jet(Ej)jsont toutes les deux décroissantes d"après leur définition. Une autre

de ces courbe est données par la figure 2. La courbe peut être rendue continue par interpolation.Algorithme 8 : taux de classification à erreur fixe

On cherche un taux de reconnaissance pour un taux d"erreur donné. On dispose pour cela d"une courbe ROC obtenue par l"algorithme 7 et définie par les pointsROC= f(ej;rj)j16j6kg. On suppose ici que(e1;r1) = (1;1)et(ek;rk) = (0;). Si ce n"est pas le cas, on ajoute ces valeurs à l"ensembleROC. Pour un taux d"erreur donnée, on cherchejtel que : e j+16e6ej(7) Le taux de reconnaissancecherché est donné par : =exjx j+1xj[rj+1rj] +rj(8) Il ne reste plus qu"à détailler la méthodebootstrap.

3.2 Méthode boostrap

Une seule courbe ROC ne permet d"obtenir qu"un seul taux. On cherche ici à construire plusieurs

courbes ROC à partir de la même expérience de façon à obtenir plusieurs taux de reconnaissance pour

le même taux d"erreur. De cette manière, il sera possible de déterminer un intervalle de confiance.

6 On s"inspire pour cela des méthodes debootstrap.Algorithme 9 : courbe ROC, méthode boostrap On dispose toujours du nuage de pointsE= (Xi;i)2R f0;1gaveci2 f1;:::;ng. On choisitC2Nle nombre de courbes ROC qu"on désire tracer. Pour chaque courbe c2 f1;:::;Cg: 1. On construit un nouv elensem ble(X0i;0i)16i6nconstruit par un tirage aléatoire dans l"ensembleEavec remise. 2. L"algorithme 7 p ermetd econstuire la courb eRkOC. 3. L"algorithme 8 p ermetensuite de déterminer un taux d ereconnaissance kpour le taux d"erreure. La liste(1;:::;C)est triée par ordre croissant. Les quantiles sont ensuite utilisés pour déterminer l"intervalle de confiance[1;2]du taux de reconnaissance pour le taux d"erreur e de telle sorte que :

P(2[1;2]) = 1(9)

On prend généralement= 5%.

La figure 2 illustre les résultats obtenus par l"algorithme 9.Figure2 :La première image est celle d"une courbe ROC (l"axe des abscisses est inversé), la seconde

représente toutes celles obtenues par la méthode bootstrap pour trois courbes. La troisième image superpose

cent courbes. Moins il y a de points pour estimer une partie de la courbe, plus les courbes sont espacées.

Ces courbes ont été construites avec 12000 points. Le taux de lecture pour 1% d"erreur est égal à 68,09%.

L"intervalle de confiance à 95% est[66;10%;70;16%](construit avec 500 courbes). Moyenne (68,25) et mé-

diane (68,12) sont sensiblement égales au taux calculé sur la première courbe construite sans tirage aléatoire.

L"écart-type est1;10, cela donne un intervalle de confiance équivalent au précédent si on considère que la

moyenne des taux suit asymptotiquement une loi normale. Cette expérience a été reproduite plusieurs fois et

ces bornes sont assez stables contrairement (0;05%) aux extremas (1%). 7

3.3 Aire sous la courbe

La méthode bootstrap peut elle aussi être appliquée pour calculer un intervalle de confiance pour

l"aire sous la courbe (AUC).Figure3 :Courbe ROC (l"axe des abscisse est inversé) obtenue pour 100 tirages aléatoires. L"aire sous la

courbe est égale à 0.80 et l"intervalle de confiance à 95% mesurée par la méthode bootsrap est :[0:79;0:80].

Les extremas sont presque identiques à ces chiffres.

4 Pour aller plus loin

4.1 Distribution des scores mauvais et bons

On appelle un mauvais score un score associé à un mauvais résultat, de même, un bon score est

le score d"un bon résultat. Si le score est une probabilité, on s"attend à trouver les bons scores

regroupés autour de la valeur 1. Si le score est un mauvais score, il devrait être plus proche de zéro.

La figure 4 montre des distributions obtenues pour deux problèmes différents. Dans les deux cas,

le but recherché est la détermination d"un seuil séparant le score d"un bon résultat de celui d"un

mauvais résultat. Lorsque ceci n"est pas possible, le score ne peut correspondre à un quelconque

critère confiance.

4.2 Taux de lecture ou de reconnaissance

Il n"existe pas une grande différence lorsque le taux d"erreur est faible. Le taux de lecture est simplement la proportion de documents pour lesquels le score est aussi d"un seuilsque la réponse du classifieur soit bonne ou mauvaise. Par exemple, pour un taux desubstitutionde 1%, si on a

70% en taux de lecture, cela signifie que sur 100 documents, le système va en accepter 70 et parmi

ces 70, 1% seront mal traités. Le taux de substitution est un taux d"erreur rapporté à un taux de

lecture donné. L"inconvénient du taux de lecture rapporté au taux de substitution est que la méthode

développée au paragraphe 3 ne s"applique plus aussi bien car pour un taux de substitution donné,

il peut exister plusieurs taux de lecture, ce que montre la figure 5. Cette même figure montre les

répercussions sur le calcul des intervalles de confiance. 8

Figure4 :Distribution des bons et mauvais scores. La première courbe montre deux distributions qui

se chevauchent même si les bons scores semblent plus concentrés autour des grandes valeurs. Le seconde

courbe montre un problème mieux séparable. L"existence d"un seuil entre un bon et un mauvais score est plus

plausible. On peut démontrer que la courbe taux de lecture / taux de substitution n"est pas une courbe ni monotone ni inversible. Pour cela on dispose d"une suite de couple(Xi;i)croissante selon lesXi.i

vaut 1 si l"expérience a réussi, 0 sinon. Pour un seuil donnés, on noteE0(s)le taux de substitution

etR0(s)le taux de lecture, on obtient : R

0(s) =1n

n X i=111 fXi>sg E

0(s) =1nR

0(s)n X i=1(1i)11fXi>sg On écrit différemment ces expressions en supposant queXi(s1)1< s16Xi(s1): R

0(s1) =ni(s1)n

E

0(s1) =1ni(s1)n

X i=i(s1)(1i) On suppose maintenant queXi(s2)1< s26Xi(s2)eti(s1) + 1 =i(s2): 9

Figure5 :La première image montre 5 courbes taux de lecture / taux de substitutions. Les courbes ne sont

pas monotones et montre qu"il existe parfois plusieurs taux de lecture pour un même taux de substitution.

Comme le calcul des intervalles de confiance fait intervenir une interpolation linéaire, lorsque les courbes

sont trop cahotiques, le calcul retourne des valeurs fausses. R

0(s2) =ni(s2)n

< R0(s1) E

0(s2) =1ni(s2)n

X i=i(s2)(1i) =1ni(s2)ni(s1)ni(s1)0

1i(s1)+nX

i=i(s1)(1i)1 A =1i(s1)ni(s2)+n P Si on suppose quei(s1)= 1, autrement dit, l"expériences1a réussi, on en déduit que : E

0(s2) =E0(s1)ni(s1)ni(s2)=E0(s1)ni(s2) + 1ni(s2)> E0(s1)

En revanche sii= 0:

E

0(s2) =E0(s1)

1 +1ni(s2)

1ni(s2)=E0(s1) +E(s1)1ni(s2)< E0(s1)

Il n"existe donc pas toujours une fonctionfreliantR0(s)àE0(s)à moins de construire cette courbe

de telle sorte qu"elle soit monotone en ne choisissant qu"une sous-suite(E0(Xi);R0(Xi))iqui vérifie

cette hypothèse. 10

Références

[Agarwal2005] Shiv aniAgarw al,Thore Graep el,Ralf Herb ich,Sariel Har-P eled,Dan Roth, Gene- ralization Bounds for the Area Under the ROC Curve, Journal of Machine Learning Research

6 (2005), pp 393-425

[Saporta1990] Gilb ertS aporta,Probabilités, analyse des données et statistique, Editions Technip (1990) 11 Index A aire

ROC ..................................... 3

Algorithme

courbe ROC..............................6 courbe ROC, méthode boostrap...........7 taux de classification à erreur fixe.........6

Area Under the ROC Curb ................... 3

AUC ....................................... 3, 8

B C

Corollaire

estimateur de l"aire sous la courbe ROC...4 variance de l"estimateur...................5 critère confiance ................................. 8 D

Définition

ROC ..................................... 2

distribution ............................... 9, 10 I intervalle de confiance .............................. 4 M P R rappel ........................................ 2 recall ......................................... 2

Receiver Operating Characteristic .......... 7, 8

Receiver Operator Characteristic..............1

références

Agarwal2005..........................3, 11

Saporta1990 .......................... 4, 11

remarque fonctions monotones ...................... 3 score aléatoire ............................ 3 ROC.....................................1, 7, 8bootstrap.................................6 S T taux

Théorème

aire sous la courbe........................3 tirage avec remise ............................... 7 U W Z numéros

Algorithme

7 ....................................... 6

8 ....................................... 6

9 ....................................... 7

Corollaire

5 ....................................... 4

6 ....................................... 5

Définition

1 ....................................... 2

démonstration corollaire 5 ............................. 4 corollaire 6 ............................. 5 théorème 4 ............................. 3

Théorème

4 ....................................... 3

liens http :// en. wikipedia. org/ wiki/

File :Roccurves.png...................2

http ://www.xavierdupre.fr/..............1 12quotesdbs_dbs35.pdfusesText_40