Estadísticas de error en biometría - UPV/EHU · El fenómeno del “envejecimiento de los patrones” consiste en el aumento de las distancias de las muestras respecto de los patrones

error sistemas biometricos 1

Estadísticas de error en biometría

Error rate equations for the general biometric system, J.L.Wayman, IEEE Robotics & Automation Magazine, (march 1999) 6

(1) pp. 35-48


Introducción

• Identificación biométrica: verificar que el usuario es quien dice ser ono es quien dice no ser.

• Verificación: emparejamiento uno-a-uno, la base de datos es de unúnico individuo.

• Identificación: emparejamiento uno-a-muchos, la base de datos es demuchos individuos.

• Test de sistemas miden:– Falsa aceptación (falsa alarma, falso positivo)

– Falso rechazo (falso negativo)

– Listas de candidatos.

• El objetivo del trabajo de Wayman es desacoplar la evaluación delrendimiento del sistema del tamao de la búsqueda, la política dedecisión y el diseño del test.


• En general los sistemas biométricos permiten registrar varias medidaso varias presentaciones del mismo usuario y durante la operaciónpermiten presentar varias muestras para el emparejamiento.

• El sistema puede realizar múltiples comparaciones para verificar laidentidad

• Los sistemas son comparaciones M-a-N– M es el número de muestras que se puden utilizar en la operación, de la

misma o diferentes características biométricas. Es el “conjunto muestra”.

– N es el tamaño de la base de datos.

• Existen U usuarios registrados con T patrones o modelos almacenadospara cada uno.– Los modelos de cada usuario se consideran independientes en el sentido

estadístico

– Si es el mismo numero de patrones para cada usuario tenemos

N=T * U.



Medidas basicas

• Coeficiente de penetración

• El error de pre-clasificación “bin-error”

• Tasa de falsos positivos en comparaciónsimple.

• Tasa de falso negativos en comparaciónsimple.

• Tasa de comparaciones del sistema(comparaciones por unidad de tiempo)


Particiones de los datos

• Está orientada a reducir el número de comparacionesnecesarias para realizar la búsqueda.

• Partición de los N datos tomados en función decaracterísticas internas: binning

• Partición basada en características externas (nombre, etc):filtering.

• Un patrón puede colocarse en muchas particionessimultáneamente si existe incertidumbre en su clasificación

• En operación, las muestras se clasifican y sólo secomparan con los datos en las mismas particiones.


Coeficiente de penetración

• Es la porción de la base de datos total que se examina, enpromedio por cada muestra de entrada.

• Se asume que la búsqueda no termina cuando se encuentrael emparejamiento, sino que se extiende a la particióncorrespondiente.– Depende de la forma de particionar los datos.

• Cuanto menor es el coeficiente de penetración, mejor es laeficiencia del sistema.


• En sistemas de verificación, los datos de los usuariospueden estar almacenados– en una tarjeta inteligente.

• En cada transacción la base de datos son los T patrones en la tarjeta.

– de forma centralizada, donde los datos pueden particionarse en Kclases

• En cada transacción sólo examina N/K datos.

• Si K=U sólo se examinan los datos correspondientes a cada usuario.

• Independientemente de la arquitectura de almacenamientoel coeficiente de penetración es

PT

N U= =

1


• En sistemas de identificación se trata de comprobar unaidentidad no especificada.

• Se puede considerar T particiones de U datos en cada una.

• Los datos entre particiones están ligados por la identidaddel usuario. La partición es un filtrado.

• En este caso el coeficiente de penetración es

PU

N T= =

1


• En el caso general tenemos K particiones de los datos y pi

es la probabilidad de que un patrón caiga en la i-esimapartición.

• Cada partición tendrá N* pi patrones. El número decomparaciones esperado es

• El coeficiente de penetración es

Si las particiones son exclusivas


• En el caso de exista una partición etiquetada como“desconocido”– Las muestras etiquetadas como desconocido tienen que ser

comparadas con todos los patrones

– Todas las muestras tienen que ser comparadas con los patrones enla clase desconocido.

– Sigue manteniendose la intersección nula entre clases

• El numero de comparaciones promedio por muestra:

Muestras etiquetadascomo desconocidas

Restantesmuestras

Coeficiente depenetración


• Cuando la clasificación es incierta pero no completamentedesconocida, la muestra se coloca en múltiples bins por loque

• El coeficiente de penetración promedio en este caso puedeser calculado empíricamente como


• Supuesto que existen B métodos independientes de partición de lospatrones (filtering & binning)

• Si los métodos de partición son realmente independientes, elcoeficiente de penetración de la i-esima medida se escribe como

• Si existe correlación entre los métodos de partición esta ecuaciónsubestima el coeficiente de penetración.

• ensemble binning: Si el número de medidas por usuario es T>1 y elnúmero de muestras es M=T y las clases están definidas sobre todas lasmedidas simultaneamente


Error de clasificaciónbin-error rate

• Refleja los errores inducidos por las inconsistencias en elproceso de partición de los patrones y de clasificación delas muestras

• Los errores en la clasificación basada en característicaspropias (binning) son difíciles de caracterizar.

• Los errores de filtrado se deben a errores en la recolecciónde los datos, no son medibles y dan lugar a fraudes eirregularidades. Es preferible el proceso de binning oclasificación automática


• El error de clasificación empírico se calcula como

• En el caso de múltiples métodos de partición, laprobabilidad de no error de partición (asumiendoindependencia) para cada medida es

• Si todos los métodos tienen el mismo error

• Para los ensemble binnings:



Distancias

• El sistema de reconocimiento de patrones calcula una medida D escalar ypositiva por cada comparación entre los patrones y la muestra: la “distancia”.

• D es creciente con la diferencia entre muestra y patrón.

• La distribución “genuina” ΨG(D) de las distancia es el histograma de lasdistancias entre muestras y patrones que corresponden a emparejamientoscorrectos.

• Esta distribución mide la repetibilidad del patrón.

• El fenómeno del “envejecimiento de los patrones” consiste en el aumento delas distancias de las muestras respecto de los patrones conforme pasa eltiempo.


• La disribución de los “impostores” ΨI(D) es el histograma de las distancias delos emparejamientos incorrectos. Puede construirse de varias maneras:

– Comparando cada muestra con un único patrón no-mismo

– Comparando cada muestra con cada patrón de identidad distinta

– Mediante remuestreo aleatorio, en el que se extraen aleatoriamente los patrones.

– Creando una base de datos de patrones “de fondo” para los que no hayemparejamiento.

• La estimación de la distribución de impostores puede ser más crítica que la dela distribución genuina. Necesita muchos más datos para su estimación yesmucho más suave.

• La distribución genuina permite calcular las tasas de error de falsos rechazos(falso negativo).

• La distribución de impostores permite calcular las tasas de error de falsoemparejamiento (falso positivo).

• Idealmente las distribuciones genuina y de impostor tendrían soporte disjunto,con lo que un umbral sobre la distancia permitiría decidir correctamente.



• La distribución genuina ΨG(D) suele ser bimodal.

• El segundo modo de la distribución ΨG(D) coincide con elmodo principal de ΨI(D)

• Las colas de ambas distribuciones se solapan fuertemente.• La distribución interpatrones ΨT(D) modela la distancia

entre los patrones indep. de la identidad y la clase.


Single comparison False-match rate

• Una muestra es asignada incorrectamente a unpatrón dado que la distancia está bajo un umbral τ.

• Puede calcularse a partir de la distribución deimpostores la tasa de error de falsoemparejamiento


Single comparison false-nonmatch rate

• Un falso no emparejamiento ocurre cuandose rechaza incorrectamente elemparejamiento una muestra en base alumbral de distancias.

• Se calcula sobre la distribución genuina


Rendimiento del sistema

• Emparejamiento y desemparejamiento correcto yen tiempo de clientes a identidades en una base dedatos de N patrones basado en una política dedecisión que utiliza M muestras de cada cliente.Una muestra de cada medida M=T.

• En sistemas multi-medida, se utiliza unsubconjunto de m<M medidas para hacer unabúsqueda previa y descartar de forma eficiente lamayor parte de los usuarios en la BD.


Esquema de decisión

• Para declarar un emparejamiento se requiere que se emparejen Q de las Mmedidas sobre un conjunto de T patrones.

• Se hace una búsqueda inicial con m medidas sobre las particiones relevantesde la base de patrones. Se hace un total de comparaciones

• Los emparejamientos se confirman comparando las M muestras contra los Tpatrones del mismo conjunto de patrones.

• Se activa la comparación cuando una de las m medidas es positiva.

• Si no se empareja ninguna de las m muestras u ocurren más de T-Q no-emparejamientos de los M muestras, se declara como no emparejado.

• Las m muestras consideradas en la búsqueda inicial tienen erroresindependientes

Tasas de error uniformes


System False-nonmatch rate

• Para que no ocurra un falso nonmatch debe nohaber– Error de clasificación (binning)

– Error de emparejamiento

• Asumiendo los errores independientes, laprobabilidad de emparejamiento correcto es

Prob. de no emparej.


• Si el sistema no hace combinaciones de losemparejamientos de las distintas medidas, sino que lasconsidera independientes, el falso nonmatch del sistemaocurre cuando todas las m comparaciones resultan en unfalso nonmatch

• Esta ecuación subestima la probabilidad dado que en lapractica se observa una cierta dependencia entre losresultados de los emparejamientos.


• Para sistemas que emplean ensembles, la i-esima de mcomparaciones contra todo el ensemble, requiere para queno se produzca un falso nonmatch– La comparación inicial de muestra y patrón no sea un falso

nonmatch

– Q-1 de los restantes patrones del ensamble sean correctamenteemparejados

• La probabilidad de declarar una correcta identificación enla i-esima de m comparaciones

Q o más emparejamientoscorrectos a partir de la i-esimamuestra


La probabilidad de falso nonmatch es la complementaria

Si las comparaciones son independientes, la probabilidad deun falso nonmatch del sistema es

En el caso de ensemble binning la probabilidad de error declasificación es la misma para todas las muestras, por lo que lasprobabilidades de emparejamiento correcto no son independientespara cada muestra y no se pueden aplicar a las ecuacionesanteriores.


En el caso de ensemble binning, el error de clasificación no esindependiente sobre las M comparaciones, ya que cada comparaciónmira en la misma partición. Reescribiendo

Para obtener una identificación correcta en el caso de los ensemblebinning requiere 1) no hay error de clasificación para todo el ensemble,2) no hay fallo en las búsquedas iniciales.


System false-match rate

• En sistemas sencillos se declara un emparejamiento sicualquiera de las m comparaciones resulta en unemparejamiento.

Esta cantidad se aproxima siempres a 1 para grandesm*N*Pi


En un sistema que utiliza varias medidas, se declara un falsoemparejamiento si Q falsos emparejamientos ocurren contralos patrones de registro de un usuario, cuando antes m falsosemparejamientos iniciales se han realizado.

Copiado literalmente pero seguro que hay que sustituir FNM por FMR

Al recorrer todas las distintas particiones, la probabilidad de quelas m búsquedas iniciales no terminaran en un falsoemparejamiento


Para el sistema completo, la tasa de error de falsoemparejamiento, considerando independientes las mcomparaciones iniciales.

La tasa de falsos emparejamientos decrece con el coeficientede penetración.

Permite tasas de error razonables incluso para grandes N.


System throughput

• Capacidad de proceso del sistema

• Depende de– La tasa harware de comparación

– El número m de muestras comparadas con labase de datos

– El número de patrones N

– El coeficiente de penetración


En el caso de que no se encuentren emparejamientos, elthroughput en clientes por unidad de tiempo

C es la tasa hardware de proceso uno-a-uno

Si hay ensemble binning

Minimizar los costos frente a un throughput establecidoobliga a modificar el coeficiente de penetración (mediantebinning o filtering) aumentando la tasa de falso nonmatch ydecreciendo la tasa de falso emparejamiento.


Sistema uno-a-uno

• Muestra única y patrón único de un usuario paraverificación.

• T=1, N=T=1, Psys=1, N=U*T, Psys=1/U, N*Psys=T=1.m=1


Uno-a-uno con tres intentos.

La tasa de falsosrechazos decreceexponencialmente conel número de reintentos,sin embargo la tasa defalsas aceptaciones solodecrece linealmente


One-to-several verification systems

Comparaciones independientes

Una medida y varias muestras y patrones almacenados

Los falsos emparejamientos (falsas aceptaciones) crecenlinealmente (FMR tiende a 1), los falsos rechazosdecrecen exponencialmente.


“One to many” singlecomparison systems

Coeficiente de penetración menor que 1, existe bin-errorfingerprint

Filtro de género: asumiendo 2% de género desconocido, mitad y mitad

Coeficiente de penetración.


Falsos noemparejamientos sonindependientes de N.

Espectación de falsos emparejamientos

Condición para una buena definición del sistema de identificación



M-to-NDatos de 4 dedos (Filipinas)

comparaciones

Al menos tres dedos emparejados


Muestras independientes

Ensemble binning

El error de falsos no emparejamientos es 5 veces mayor


Si el coeficiente de penetración es el mismo


40,000 por semana

Documents

Estadísticas de error en biometría - UPV/EHU · El fenómeno del “envejecimiento de los patrones” consiste en el aumento de las distancias de las muestras respecto de los patrones