I moved my website to a new host provider.

You are automatically redirected to the new site within a few seconds!

If it does not work: http://biometrics.mainguet.org/


Accuracy / Précision

Under construction

I started this page in french, I need to translate it into english... Et le français n'est pas encore vraiment terminé. Mais bon, ça devrait déjà suffire à bon nombre de lecteurs.


Evidemment, tout le monde aimerait avoir un système parfait, qui ne se trompe jamais. Dans le cas de la biométrie, nous sommes en face de 2 populations:

  • Les gentils utilisateurs, ceux qui sont dûment autorisés à pénétrer dans la zone protégée
  • Les méchants truands (les imposteurs), qui n'ont aucune autorisation, mais qui vont quand même essayer de rentrer
  • Le système parfait laissera passer les gentils utilisateurs, mais bloquera tous les méchants. Malheureusement, aucun système n'est parfait, voir le mythe sur la sécurité absolue).

    Dans ce qui suit, on prendra l'exemple d'un contrôle d'accès d'un bâtiment par empreinte digitale et un badge, afin de fixer les idées.

    Enrôlement / FTE (failure to enroll)

    Dans le cas de la biométrie, il faut d'abord enrôler les gentils utilisateurs: une représentation de chaque utilisateur autorisé sera enregistrée.

    Déjà à ce stade, des problèmes peuvent se produire: il est possible qu'un gentil utilisateur ne puisse pas être enrôlé pour diverses raisons (voir le mythe sur la biométrie pour tous). On définit un taux qui s'appelle "Failure to Enroll Rate" (FTR) ou taux d'échec à l'enrôlement, qui est la proportion de gentils utilisateurs qu'on n'arrive pas à enregistrer. Dans le cas des empreintes, il existe certaines personnes qui n'ont pas d'empreintes pour des raisons génétiques, ou des empreintes quasi-inexistantes pour des raisons médicales.

    Failure to Enroll

    Notons qu'à ce stade, plusieurs politiques sont envisageables, dont certaines auront des conséquences drastiques. Par exemple, on peut arbitrairement décider de ne pas enregistrer les gentils utilisateurs dit "difficiles", ce qui augmentera, on s'en doute, les performances globales du système plus tard: si on rejete tous ceux qu'on ne peut pas reconnaitre, alors on est sûr de toujours reconnaitre ceux qui sont enregistrés! A l'inverse, enregistrer tout le monde quoi qu'il arrive mènera à des erreurs: il sera plus facile pour un imposteur d'imiter une personne qu'un système a du mal à reconnaitre.

    Dans notre exemple avec les empreintes, les gentils utilisateurs qui sont enrôlés auront donc une représentation de leurs empreintes enregistrée dans un badge qu'on leur donnera. On ne s'intéressera pas à ce qui arrive à ceux qui ne sont pas enregistrés, ce n'est plus un problème biométrique, c'est juste un problème de politique administrative pour ce genre de cas.

    Système opérationel

    Dans un système opérationel, le gentil utilisateur se présente, une nouvel capture dite "live" est effectuée (on reprend une nouvelle empreinte), et on compare à la représentation enregistrée (dans le badge en ce qui concerne notre exemple). Le logiciel biométrique va alors décider si la correspondance est suffisante, en calculant un score.

    Deux cas se présentent:

  • Soit le score est plus grand qu'un certain seuil, et le gentil utilisateur pourra passer: c'est le cas qu'on aimerait toujours avoir.
  • Soit le score est plus petit que le seuil, et le gentil utilisateur ne pourra pas entrer. C'est le cas défavorable, et on remarquera que ce n'est pas un problème de sécurité, uniquement un problème de commodité: l'utilisateur n'est certe pas content de rentrer, mais après tout, ce n'est rien à coté d'une intrusion.


  • Scoring definition

    Ce qui nous amène au cas des imposteurs, les méchants truands. Encore une fois, deux cas se présentent (dans notre exemple, on suppose que l'imposteur s'est procuré le badge d'une personne autorisée):

  • Soit le score est plus petit que le seuil, et l'imposteur est rejeté: c'est ce qu'on aimerait toujours avoir.
  • Soit le score est plus grand que le seuil, et le système laisse entrer l'imposteur: alors là, ça ne va pas du tout, on a une faille dans la sécurité du système!
  • Important: à ce stade, il est important de noter qu'un gentil utilisateur peut être rejeté lors d'une présentation un jour (il s'est abimé son doigt ce jour-là par exemple), et accepté un autre jour. La même chose pour les imposteurs, et lors de la comptabilité, on doit tout compter, bien sûr. On parle alors de tentative de transaction.

    Comptabilité des erreurs: FAR, FRR

    Il est donc désirable de connaitre les taux d'erreur:

  • Quelle est la proportion de tentatives de gentils utilisateurs acceptées / rejetées?
  • Quelle est la proportion de tentatives d'imposteurs rejetées / acceptées?
  • Il existe plusieurs manières d'annoncer ces taux:

  • On peut indiquer la proportion des gentils utilisateurs acceptés et des imposteurs rejetés: ces taux doivent être aussi proche de 100% que possible. On les appelle taux de vrai acceptés TVA et taux de faux rejetés TFR.
  • Inversement, on peut indiquer la proportion de gentils utilisateurs rejetés et d'imposteurs acceptés: ces taux doivent être aussi petit que possible, idéalement zéro. On les appelle taux de vrai rejetés TVR et taux de faux acceptés TFA, et évidemment, ils sont simplement liés aux précédents par les relations TVA = 1 - TVR et TFR = 1 - TFA.
  • Rien qu'avec ces simples définitions, on a déjà une petite gymnastique d'esprit pour savoir de quoi on parle, et c'est facile de confondre. Là-dessus vient se greffer les termes anglais équivalents qui sont habituellement utilisés, et on peut facilement faire des confusions.

    Pour arranger les choses, il est rarement pratique d'utiliser des nombres du genre 99.97%, avec seulement quelques décimales qui diffèrent. Et c'est le cas avec les taux de faux refusés (= le nombre de méchants truands qui n'ont pas pu entrer dans le système, vous voyez bien que ce n'est pas facile à manipuler). En fait, on voudra avoir un nombre d'imposteurs qui ont pu entrer dans le système aussi faible que possible, car dans le cas d'une recherche d'empreinte digitale prise sur une scène de crime, on va comparer à des centaines de millions d'empreintes, et une erreur de l'ordre de 1 pour 1 million (soit 99.9999%) génèrera une centaine de réponses possibles.

    FAR / FRR definitions

    Aussi je préconise généralement de n'utiliser que deux termes qui sont couramment utilisés dans l'industrie biométrique, d'origine anglaise (ça vous évitera de mémoriser plusieurs noms et ça fait bien dans la conversation):

  • le FRR, False Rejection Rate, taux de vrai refusé en français. On doit normalement manipuler des nombres de l'ordre du %, ce qui correspond à une tentative sur 100. Ce nombre caractérise la commodité du système.
  • le FAR, False Acceptance Rate, taux de faux accepté en français. Ce nombre devrait être très petit, de l'ordre de 0.01% voire plus faible encore pour des grosses bases de données, et on préfère souvent utiliser une puissance de 10, plus commode, comme par exemple 10-4 (1 pour 10 000 soit 0.01%) ou 10-6 (1 pour 1 million). Ce nombre caractérise le niveau de sécurité du système.
  • Les deux taux sont liés

    Il ne faut jamais perdre de vue le fait que les deux taux sont toujours liés: un système réglé sur "dur" ou "haute sécurité" = avec un seuil élevé, laissera difficilement entrer un imposteur, donc aura un FAR très faible. Mais les gentils utilisateurs auront eux aussi du mal à entrer, et le FRR sera élevé. A l'inverse, un système permissif, reglé sur une sécurité faible, laissera facilement entrer les gentils utilisateurs (ils seront contents, le FRR sera faible), mais aussi les imposteurs, et le FAR sera relativement élevé.

    On peut démontrer et évaluer cela avec les distributions de score. Prenez un système biométrique, et calculer/simuler/essayer vraiment, peu importe, les scores obtenus par les gentils utilisateurs et les méchants truands, les imposteurs.

    Commençons par les gentils utilisateurs. Normalement, ils devraient toujours avoir des scores élevés, plutôt proche de 100 sur une échelle de 0 à 100. C'est évidemment le cas, mais on observe dans la réalité, que certains moins gentils utilisateurs obtiennent parfois des scores assez faibles. Pour l'instant, ce n'est pas très grave, et on obtient ce genre de distribution (le score en abscisse, le nombre d'utilisateurs ayant eu ce score (probabilité) en ordonnée):

    genuine distribution of scores

    Effectuons la même chose avec les imposteurs. Cette fois, les scores devraient être proche de zéro, mais il arrive parfois qu'un imposteur obtienne un score ma foi assez élevé, et on peut observer ce genre de distribution:

    impostors distribution of scores

    La forme des distributions peut être très variable, peu importe, ce n'est pas le soucis ici. Par contre, lorsque l'on superpose les deux distributions, on a malheureusement toujours une zone de recouvrement. On aimerait évidemment avoir les deux distributions parfaitement disjointes, ce qui permettrait idéalement de séparer les gentils des méchants, mais ce n'est jamais le cas dans la dure réalité de la vie:

    distribution of scores

    Le responsable du système biométrique devra choisir un seuil d'acceptation, mais où le placer? Il a choix:

  • soit il choisit un seuil faible, ce qui laissera passer tout les gentils utilisateurs (et il ne sera pas ennuyé par ses gentils utilisateurs, de loin les plus nombreux et à qui il a à faire tous les jours), mais alors un imposteur passera assez facilement
  • soit il choisit un seuil fort, ce qui bloquera tous les imposteurs et protègera efficacement son système, mais alors il aura des ennuis avec les gentils utilisateurs qui viendront se plaindre que le système ne les laisse pas entrer


  • FAR FRR

    Grâce aux courbes de distribution, on pourra calculer les taux de FAR et de FRR pour différentes valeurs de seuil, et on se rend bien compte que ces deux nombres sont liés. On constate parfois des personnes peu scrupuleuses qui annoncent des FAR et FRR assez avantageux, parce qu'ils n'utilisent pas le même seuil pour les deux nombres (ou laisse le contexte tellement ambigüe que ça ne veut plus rien dire), voir le mythe concernant la précision

    Courbes caractéristiques d'un système biométrique: ROC, DET...

    La liaison entre le FAR et le FRR pour différentes valeurs de seuil peut se traduire par des courbes dites DET et/ou ROC. Il faut admettre que la normalisation des résultats n'est pas encore très utilisée, aussi on rencontre à peu près toutes les configurations car vous pouvez choisir de mettre en abcisse soit le FRR, soit le FAR (ou les autres taux), avec des échelles soit linéaires, soit logarithmiques ou en combinaison...

  • Detection Error Trade-off (DET) curve:
    a DET curve plots error rates on both axes, giving uniform treatment to both types of error. The graph can then be plotted using logarithmic axes. DET curves can be used to plot matching error rates (False Nonmatch Rate against False Match Rate) as well as decision error rates (False Rejection Rate against False Accept Rate).
  • Receiver Operating Characteristics (ROC) curve
    shows the performance of pattern matching algorithms over a range of decision criteria. Such curves plot the “false accept probability” (i.e., false acceptance rate) on the x-axis, and “correct detection probability” (i.e., 1- false rejection rate) on the y-axis.


  • DET curve ROC curve

    Résultat des courses: il faut à chaque fois refaire une gymnastique intellectuelle pour remettre les courbes dans le sens qu'on aime bien utiliser. Pour ma part, j'aime bien le FRR en abcisse avec des valeurs linéaires car on manipule en général quelques pour %, et des FAR en ordonnée en échelle logarithmique, car on manipule des nombres variant de 10-1 à 10-6.

    On remarquera que généralement, une bonne moitié de la courbe est sans intérêt: avoir des taux de fausses acceptations (les imposteurs qui entrent) plus élevés que les taux de faux rejets (les gentils qui restent bloqués à l'entrée) n'a guère d'utilité.

    EER

    Il existe un point particulier parfois utilisé pour comparer (malheureusement à tort, même par des spécialistes) divers systèmes: c'est le point où on a autant de faux rejets que de fausses acceptations, autrement dit le point où la courbe coupe la diagonale. On l'appelle EER Equal Error Rate en anglais.

    Si les courbes étaient plus ou moins symétriques et régulières, alors effectivement, on pourrait comparer plusieurs systèmes entre eux: plus l'EER est faible, mieux c'est. Seulement, ce n'est pas toujours le cas, et de plus on peut très bien avoir un EER assez mauvais, mais un excellent système dans la zone où on l'utilise vraiment, par exemple à FAR=10-4, où le FRR correspondant est de 1%, tout simplement parce que le système a été conçu pour fonctionner dans cette zone, et que les valeurs à fort FAR n'ont pas d'intérêt et donne un résultat non significatif.

    Pour ma part, j'aime bien comparer des systèmes simplement avec leur taux de FRR pour un FAR fixé à 10-4. C'est arbitraire, mais commode. Ceci dit, la régularité de la courbe donne aussi des informations précieuses sur la stabilité du système, et il vaut mieux examiner la courbe.

    Suffit-il d'être patient pour entrer?

    Ainsi donc, je suis un imposteur qui sait que la précision du système biométrique est de 1 pour 1000, soit un FAR de 10-3. Suffit-il d'essayer 1000 fois pour entrer dans le système? Après tout, s'il faut 2 à 3 secondes par essai, en moins d'une heure je serai à l'intérieur, ce qui parait acceptable, surtout que je n'ai besoin de rien, juste mon doigt?

    C'est ne pas avoir bien compris ce que signifient les nombres précédents que de croire cela. Si vous essayez 1000 fois le même doigt, s'il n'a pas marché la première fois, et bien il n'y a pratiquement aucune chance pour que ça marche plus tard, car vous présentez à chaque fois le même échantillon, et évidemment le système va retourner à chaque fois le même résultat! C'est le propre des programmes informatiques que de retourner une réponse constante à données initiales identiques...

    Donc si vous voulez tenter votre chance de cette manière, alors il faudra faire varier les données. Dans le cas des empreintes, il faudra essayer au moins avec 1000 empreintes différentes pour avoir une chance non négligeable d'entrer, et encore, ce n'est qu'une probabilité, ce n'est jamais du 100% comme cela le serait avec un code à 3 chiffres (il n'y a que 1000 cas au total, donc forcément la solution est dedans).

    Comment se faire entuber

    Ou plus positivement, que faut-il indiquer pour avoir confiance dans les résultats annoncés.

    En effet, nous n'avons jusqu'à présent jamais parlé de la manière précise de comptabiliser, et en particulier, un certain nombre de questions se posent:

  • Imaginer que vous soyez en face d'une porte avec un capteur d'empreinte. Vous présentez une première fois votre doigt, et le système vous refuse. Vous essayez une seconde fois, et encore une fois, le système vous refuse. A la troisième tentative, enfin la porte s'ouvre. Comment comptabiliser cette transaction? Faut-il compter 2 tentatives ratées et une tentative réussie? Ou regarde-t-on la transaction globale, et on comptabilisera seulement une entrée réussie? Cette dernière manière de comptabiliser est tout à fait acceptable, car vous êtes vraiment parvenu à entrer, sans déranger qui que soit pour vous aider, et c'est un fait important pour ce genre de système.
  • Mais comment fait-on pour obtenir des valeurs de FAR de 1 pour 1 million? Est-ce qu'il aura fallu essayer effectivement avec 1 million de personne pour voir si on entre dans le système "par erreur"? Evidemment non, cela coûterait bien trop cher à réaliser, et il faudrait avoir un million de personne sous la main, ce qui n'est pas réaliste. En fait, il suffit de collecter par exemple 2000 photos, puis d'essayer toutes les paires possibles, ce qui nous amène à environ 2 millions de tests (on ne teste pas la diagonale, et c'est symétrique). On appelle cela un test technologique, car il est effectué par ordinateur et non réellement.
  • Que se passe-t-il si on combine plusieurs biométries ensemble? Cela devient nettement plus compliqué, car on peut combiner de différentes manières, comme par exemple simplement accepter au moins une seule biométrie, ou alors exiger que toutes soit positives. Si en plus on a des corrélations entre biométrie, cela fausse nettement les calculs théoriques simplistes.
  • Combien de personnes faut-il essayer pour avoir confiance dans les résultats? On entre là dans le domaine des statisticiens, mais on peut se souvenir au moins d'une règle de bon sens: pour donner un taux d'erreur, il faut au minimum avoir observé quelques erreurs! Et n'oublier pas que l'on s'adresse à des humains, et qu'il faut tester les différentes catégories de personnes, pas uniquement quelques individus dans un bureau ou un laboratoire, qui seront représentatifs uniquement que pour une population de bureau, probablement pas d'agriculteurs ou de mineurs de fond...
  • Conclusion: les résultats de test ne veulent rien dire tant que les conditions de test ne sont pas explicitement décrites, et dans le détail. Exigez-les pour comprendre.

    On pourra également jeter un oeil au mythe sur la précision.

    Echec d'acquisition / FTA (failure to acquire)

    Il arrive parfois qu'un système n'arrive pas à acquérir les données biométriques pour diverses raisons. Par exemple, un système de reconnaissance faciale peut éventuellement manquer un visage dans une scène, peut-être à cause de l'arrière-plan, ou alors un passage furtif d'un doigt sur un capteur d'empreinte peut passer inaperçu. Parfois, on ne voit pas de raison particulière due à l'utilisateur (bug informatique).

    Il est souvent difficile de savoir "qui a raison" dans ce genre de cas: est-ce la faute du capteur? Est-ce la faute de l'utilisateur? Peu importe la raison pour comptabiliser ces cas, on définit un taux d'échec à l'acquisition, le FTA -Failure To Acquire rate-, qui est le ratio du nombre de raté sur le nombre total d'essai.

    Une grosse difficulté est la comptabilité: comme le système n'a rien vu, seul un observateur extérieur peut effectuer cette comptabilité!

    Il arrive parfois que l'on compte ces essais ratés dans la catégorie des faux rejets (FRR), aussi faut-il faire attention dans les rapports d'essai et les nombres annoncés.


    Biometrics visitors