Learning from a single labeled face and a stream of unlabeled data

Aquí se presenta un resumen técnico detallado del artículo "Learning from a Single Labeled Face and a Stream of Unlabeled Data" de Branislav Kveton y Michal Valko.

1. Definición del Problema

El artículo aborda el problema desafiante del reconocimiento facial a partir de una única imagen etiquetada por persona, específicamente en un entorno de mundo abierto donde:

• Etiqueta Positiva Única: Solo una imagen de una persona objetivo específica está etiquetada.
• Sin Etiquetas Negativas: Todos los demás individuos en la corriente de datos no están etiquetados. El sistema no puede modelar explícitamente ejemplos "negativos" (otras personas) porque el conjunto de posibles impostores es infinito y desconocido.
• Corriente de Datos: El sistema recibe una corriente continua de datos de video sin etiquetar (por ejemplo, desde una cámara web) junto con la única imagen etiquetada.
• Restricciones: La solución debe ser en línea (procesar datos en tiempo real), no paramétrica (no hacer suposiciones sobre la distribución de las caras) y robusta ante el cambio de concepto (envejecimiento, expresiones, iluminación).

Esto se formula como un problema de Clasificación de Una Sola Clase, donde el objetivo es aprender un límite de decisión (una hipersfera) que abarque la clase objetivo mientras rechaza los valores atípicos, sin un entrenamiento explícito con ejemplos negativos.

2. Metodología: Seguimiento de Variedad en Línea (OMT)

Los autores proponen el Seguimiento de Variedad en Línea (OMT), un algoritmo no paramétrico que aprende la estructura de la variedad facial sobre la marcha utilizando la corriente de datos sin etiquetar. El método consta de dos fases principales:

A. Cuantización de Datos en Línea (Aproximación de la Variedad)

Para manejar eficientemente la corriente de datos potencialmente infinita, OMT utiliza Agrupamiento de k-Centros en Línea para resumir los datos.

• Rostros Representativos: El algoritmo mantiene un conjunto de $k$ rostros representativos ($u_t$) que cubren los datos observados.
• Radio de Generalización ($R$): Un rostro $x_t$ solo se considera para la agrupación si cae dentro de un radio de generalización $R$ del único ejemplo etiquetado $x_l$. Esto asegura que el modelo no extrapole demasiado lejos hacia regiones irrelevantes del espacio de características.
• Cobertura Adaptativa: Si un nuevo rostro está lo suficientemente lejos de todos los representantes actuales (distancia $> r$, donde $r$ es el radio de cobertura), se añade al conjunto. Si el tamaño del conjunto supera $k$, el radio de cobertura $r$ se duplica y los representantes se reasignan para mantener una distancia mínima entre ellos.
• Complejidad: Este paso asegura que el tamaño del modelo permanezca acotado ($O(k)$) y no crezca con el tiempo.

B. Inferencia de Identidad (Caminata Aleatoria Basada en Grafos)

Una vez cuantizados los datos, el algoritmo infiere la identidad de un nuevo rostro utilizando una caminata aleatoria sobre un grafo.

• Construcción del Grafo: El grafo consta de los $k$ rostros representativos más el rostro etiquetado único ($x_l$).
• Vértice Sumidero: Para manejar la falta de etiquetas negativas, se introduce un vértice sumidero especial ($x_0$). Actúa como un atractor "negativo". Los nodos no etiquetados se conectan a $x_0$ con un peso $\gamma$.
• Probabilidades de Absorción: El algoritmo calcula la probabilidad de que una caminata aleatoria que comienza en un rostro no etiquetado $x_t$ sea absorbida por el rostro etiquetado $x_l$ frente al sumidero $x_0$.
  • Si la caminata es absorbida por $x_l$, es probable que el rostro sea el objetivo.
  • Si es absorbida por $x_0$, es probable que sea un valor atípico.
• Solución Armónica: Las probabilidades de absorción se calculan en forma cerrada utilizando el Laplaciano combinatorio del grafo:
  $$f = (L_{uu} + \gamma I_u)^{-1} W_{ul}$$
  donde $W$ es la matriz de similitud, $L$ es el Laplaciano y $\gamma$ controla la disimilitud con el sumidero.
• Decisión: Un rostro se clasifica como positivo si su probabilidad de absorción supera un umbral $\epsilon$.

3. Contribuciones Clave

1. Nueva Formulación del Problema: El artículo formaliza el reconocimiento facial como un problema de clasificación de una sola clase en un entorno de mundo abierto con un único ejemplo etiquetado y una corriente de datos sin etiquetar, abordando la falta de ejemplos negativos.
2. Seguimiento de Variedad en Línea (OMT): Un nuevo algoritmo que rastrea la variedad de baja dimensión de las caras en tiempo real sin requerir entrenamiento fuera de línea o datos etiquetados extensos.
3. Adaptación No Paramétrica: El método no hace suposiciones sobre la distribución de las caras, lo que le permite adaptarse naturalmente a cambios en la expresión, la postura y el envejecimiento.
4. Complementariedad con Características: Los autores demuestran que OMT no es un reemplazo para las características discriminativas, sino una capa complementaria. Puede aplicarse sobre características existentes (como las caras de Fisher) para mejorar el rendimiento.
5. Eficiencia: El algoritmo tiene complejidad de tiempo y espacio acotada ($O(k^3)$ por paso, independiente del tiempo total $t$), lo que lo hace adecuado para aplicaciones en tiempo real (aprox. 0.05 segundos por rostro).

4. Resultados Experimentales

El método fue evaluado en el conjunto de datos VidTIMIT que contiene 43 personas. La configuración consistió en insertar rostros "atípicos" aleatorios de otras personas en la corriente de video de la persona objetivo para simular un entorno realista y ruidoso.

• Rendimiento:
  • OMT logró una Tasa de Verdaderos Positivos (TPR) del 90% con una Tasa de Falsos Positivos (FPR) de casi cero ($10^{-4}$).
  • Esto representa una mejora del 15% sobre las caras de Fisher con la misma FPR.
  • Superó significativamente a un clasificador estándar de 1-Vecino Más Cercano (1-NN) entrenado con la misma única imagen etiquetada (50% de TPR más alta).
• Equivalencia al Aprendizaje Supervisado: El rendimiento de OMT (entrenado con 1 etiquetado + datos no etiquetados) fue comparable al de un clasificador 5-NN entrenado con 5 imágenes etiquetadas, efectivamente "aprendiendo" el equivalente de 4 ejemplos etiquetados adicionales a partir de la corriente no etiquetada.
• Robustez: El método mostró un rendimiento robusto incluso cuando los parámetros (como $R$, $k$ y $\sigma$) no estaban perfectamente ajustados.
• Velocidad: El sistema procesó video en tiempo real, reconociendo rostros en aproximadamente 0.02 a 0.05 segundos en promedio.

5. Significado y Conclusión

Este trabajo es significativo porque resuelve un cuello de botella crítico en el reconocimiento facial práctico: la incapacidad de recopilar grandes conjuntos de datos etiquetados para cada usuario (por ejemplo, en la autenticación de dispositivos personales o en la seguridad aeroportuaria).

• Practicidad: Permite sistemas de autenticación seguros que pueden aprender el rostro de un usuario a partir de una única foto de identificación y adaptarse con el tiempo utilizando el propio flujo de video del usuario, sin necesidad de entrenar explícitamente con datos de "impostores".
• Perspectiva Teórica: Demuestra que los datos no etiquetados pueden utilizarse eficazmente para aprender la geometría de una variedad de clases, incluso en ausencia de ejemplos negativos, mediante el uso de técnicas de aprendizaje semi-supervisado basadas en grafos adaptadas para entornos en línea.
• Futuras Direcciones: Los autores sugieren extender OMT a características faciales locales (ojos, nariz) en lugar de imágenes holísticas, lo que podría mejorar aún más la precisión en escenarios de imagen única.

En resumen, OMT proporciona una solución computacionalmente eficiente, robusta y altamente precisa para el reconocimiento facial de un solo disparo en entornos dinámicos y de mundo abierto.