Algunos datos sobre los clasificadores en cascada, que rara vez se consideran seriamente en los artículos científicos.

Hola habr Hoy volveremos a hablar sobre el reconocimiento. A saber, sobre un modelo de reconocimiento tan simple como un clasificador en cascada. Esa cascada se usa en el método popular de Viola y Jones, sobre el cual ya han escrito tantas veces en Habré (por ejemplo, aquí , aquí y aquí ). Lo triste es que a pesar de la abundancia de artículos, nadie estudió seriamente los clasificadores en cascada. Y no solo en Habré, sino también en la comunidad científica. Aunque el clasificador en cascada parece simple, hay muchas trampas y características interesantes. Por lo tanto, tenemos prisa por compartir nuestros conocimientos con usted. Entonces, si está interesado, bienvenido a cat.

El clasificador en cascada es un modelo muy simple. Consiste en varios niveles sucesivos, cada uno de los cuales se puede representar como un clasificador binario. El precedente investigado se alimenta a la entrada del primer nivel y luego "viaja" nivel por nivel. Si en el siguiente nivel el clasificador reconoce el precedente como negativo, los clasificadores restantes de la cascada ya no lo analizarán. Un modelo tan simple se hizo popular después de la publicación del método Viola y Jones [1], donde, como se dijo, se utilizó para proporcionar un alto rendimiento. ¿Pero es solo por esto? ¿Es solo un clasificador en cascada? ¡Vamos a resolverlo!

Construiremos el artículo de hoy sobre Habré en un formato nuevo para nosotros. Seleccionaremos varias declaraciones que revelaremos en detalle e incluso refutaremos en alguna parte. ¡Entonces empecemos!

El clasificador en cascada en el método Viola y Jones simplemente se usa para acelerar el funcionamiento del detector de objetos

En el artículo original [1] en la primera página hay una frase:

La tercera contribución principal de este artículo es un método para combinar sucesivamente clasificadores más complejos en una estructura en cascada que aumenta dramáticamente la velocidad del detector al enfocar la atención en regiones prometedoras de la imagen.

De hecho, el método original de Viola y Jones está diseñado para buscar objetos en la imagen. Además, el problema de detección se resuelve mediante el método de ventana deslizante utilizando un clasificador binario, que se aplica en cada punto de la imagen investigada a diferentes escalas. El desequilibrio de los datos estudiados en la etapa de detección (regiones "vacías" sin el objeto deseado en cada imagen en estudio, millones o incluso miles de millones de veces más que regiones con objetos) provocó el uso de una cascada, un mecanismo que le permite cortar rápidamente las regiones "vacías".

Pero se trataba de usar un clasificador ya entrenado. Ahora pasemos al procedimiento de entrenamiento del clasificador. Resulta que existe exactamente el mismo problema de desequilibrio de la muestra: la cantidad de ejemplos negativos es muchas veces mayor (millones e incluso miles de millones de veces más) que la cantidad de ejemplos positivos. Pero gracias a su arquitectura, cada nuevo nivel de la cascada está entrenado por el método AdaBoost, no en toda la muestra de entrenamiento negativo, ¡sino solo en un conjunto limitado de errores de los niveles anteriores de la cascada! ¡Esto le permite ejecutar la máquina de entrenamiento AdaBoost en una muestra equilibrada y limitada!

Como puede ver, usar el clasificador en cascada en el método Viola y Jones dispara dos veces:

1. Le permite entrenar fácilmente el clasificador, evitando naturalmente el problema del conjunto de entrenamiento "infinito";
2. Proporciona un recorte rápido de las regiones "vacías" durante la detección de objetos, debido a lo cual se logra una alta productividad promedio.

Bueno, continuemos estudiando la clásica cascada y pasemos al tema del rendimiento.

Con esto en mente, un clasificador en cascada es una herramienta de aceleración.

Volvamos una vez más a la cuestión del propósito de la cascada, pero ahora, por otro lado. Si observa el clasificador en cascada matemáticamente, puede ver que la cascada es una forma conjunta de clasificadores fuertes (cada uno de los cuales puede representarse como una composición lineal de atributos):

$$

$$Cascade\left(x\right)=\prod_{i=1}^{N}\left[S_i\left(x\right)>0\right], \\ S\left(x\right)=\left[\sum_{t=1}^{T}{\alpha_t\cdot h_t\left(x\right)}>0\right],$$

Dónde $$$\left[\bullet\right]$- función indicadora.

En condiciones de un número limitado de atributos disponibles (que en la práctica, al perseguir el rendimiento, resulta ser una situación normal), la forma conjuntiva de clasificadores fuertes tiene una mayor capacidad expresiva que un solo clasificador lineal. Esto es fácil de entender si imagina un ejemplo simple, donde el espacio de características consta de dos elementos, y los objetos positivos y negativos expresados ​​en las coordenadas de estas características se ubican como se muestra en la figura a continuación (los objetos verdes son los positivos y los rojos son los negativos). Está claro que no existe un clasificador lineal único que pueda dividir correctamente esta muestra. Pero una cascada de cuatro niveles haría frente a esta tarea garantizada.


Por lo tanto, el uso de un clasificador en cascada, además de aumentar la productividad, también proporciona un mayor poder expresivo que un único clasificador lineal, en condiciones de un número limitado de características.

El clasificador en cascada proporciona un alto rendimiento constante y se puede usar fácilmente en sistemas de reconocimiento en tiempo real

Como dijimos anteriormente, el esquema en cascada le permite lograr un alto rendimiento debido a la detección rápida de regiones "vacías", ya que su número es de varios órdenes de magnitud mayor que el número de regiones que contienen el objeto. El tiempo de procesamiento de la región "vacía" difiere del tiempo de procesamiento de la región con el objeto varias veces (en proporción a la longitud de la cascada, el número de niveles de la cascada).

Dado que el número de regiones que contienen el objeto difiere de una imagen a otra, el tiempo de procesamiento de cada cuadro también es diferente. Debido al hecho de que hay significativamente menos regiones con un objeto en el marco que regiones sin un objeto, la diferencia en el tiempo de procesamiento no se mide decenas de veces, sino decenas de por ciento, lo que, sin embargo, es significativo en los sistemas de reconocimiento industrial.

Por lo tanto, el tiempo de funcionamiento del clasificador en cascada en diferentes imágenes puede variar significativamente. Por lo tanto, cuando se realizan mediciones serias del rendimiento de los clasificadores, se deben tomar medidas del tiempo de operación en promedio y en el peor de los casos. Y siempre esté preparado para tales "inconsistencias" temporales cuando use clasificadores en cascada.

En nuestra práctica, ya nos hemos enfrentado a serios problemas debido a una discrepancia significativa en el tiempo de operación en cascada en los casos promedio y peor. Como parte del proyecto de automatización de carreteras de peaje, resolvimos el problema de reconocer el tipo de automóvil, donde una de las principales subtareas era el problema de contar los juegos de ruedas. Por supuesto, utilizamos el método Viola y Jones para detectar ruedas en cuadros individuales. Debido a la gran variabilidad de las ruedas (ver la figura a continuación), la cascada entrenada fue bastante larga (20 niveles). Observamos en vivo problemas desagradables asociados con diferentes tiempos de procesamiento para cada cuadro, lo que nos impidió seriamente construir un sistema de reconocimiento en tiempo real.


Luego desarrollamos la idea de un clasificador en cascada clásico para un árbol de decisión completo, desarrollando una tecnología de aprendizaje única para dicho árbol de decisión (recuerde que era necesario proponer un algoritmo que nos permitiera evitar los problemas asociados con el conjunto de entrenamiento "interminable"). Los detalles de este algoritmo se pueden encontrar en nuestro trabajo científico [3]. Aquí informamos solo algunos hechos:

1. El camino más largo en un árbol entrenado consiste en 6 clasificadores fuertes (el esquema de un clasificador de árbol entrenado se muestra en la figura a continuación).
2. Un clasificador de árbol entrenado proporcionó una mejor calidad de trabajo en comparación con una cascada previamente entrenada. Esto es lógico y se deduce del hecho de que el poder expresivo de la cascada en forma de árbol (que es una forma conjuntiva-disyuntiva) es mayor que el poder expresivo de la cascada (forma conjuntiva).
3. Un clasificador de árboles entrenado eludió seriamente la cascada en el peor de los casos, casi sin perder en promedio.

La siguiente tabla presenta comparaciones numéricas de clasificadores en cascada y en árbol.


Por lo tanto, si realmente desea utilizar clasificadores en cascada en sistemas de reconocimiento en tiempo real, recuerde siempre las características asociadas con la velocidad del trabajo en los casos promedio y peor.

Las tecnologías de entrenamiento del clasificador en cascada son tan obvias que no hay nada con lo que preocuparse seriamente.

Oh, este es probablemente uno de los temas más difíciles relacionados con los clasificadores en cascada. La conclusión es que en todos los artículos que hemos conocido, el proceso de aprendizaje en cascada se describe de manera tan pobre, superficial y sin una justificación adecuada de la efectividad del algoritmo de aprendizaje en cascada. Por lo general, el algoritmo de aprendizaje en cascada se parece a esto:

1. Decida los valores de la parte del reconocimiento falso ($$$F$) para toda la cascada.
2. Decida los valores de la parte del reconocimiento verdadero ($$$d$) y fracciones de falso reconocimiento ($$$f \lt F$) para cada nivel de reconocimiento.
3. Elija una muestra de validación para evaluar honestamente los indicadores de calidad del clasificador final.
4. Capacite a cada nuevo nivel de la cascada (que, recordamos, está capacitado en todos los ejemplos positivos disponibles, así como en los falsos errores positivos de la cascada actual) para que su rendimiento $$$d_i$y $$$f_i$no fueron peores de lo dado, es decir $$$d_i>d$y $$$f_i \lt f$. Por cierto, el proceso de asegurar estos indicadores en sí mismo también es de gran interés.
5. Agregue el nivel recién entrenado a la cascada y evalúe sus indicadores de calidad en la muestra de validación. Si la tasa de reconocimiento falso es menor que el objetivo$$$F$, luego termina el entrenamiento. De lo contrario, vaya al paso 4 para aprender un nuevo nivel de cascada.

Si como resultado del algoritmo anterior entrenado $$$K$niveles de la cascada, entonces puede estimar la complejidad promedio de la cuota de reconocimiento correcto de la cascada de la siguiente manera:

$$

$$N=n_1+\sum_{i=2}^{K}\left(n_i\prod_{j=2}^{i}p_j\right),\\ D=\prod_{i=1}^{K}d_i,$$

Dónde $$$n_i$- complejidad $$$i$nivel en cascada $$$p_i$- probabilidad de cálculo $$$i$cascada de nivel, y $$$d_i$- cuota de reconocimientos correctos $$$i$Cascada de nivel.

Como puede ver, la complejidad de la cascada no participa en el algoritmo de entrenamiento presentado, por lo tanto, por supuesto, no puede llamarse eficaz en el rendimiento. Al mismo tiempo, sabemos con certeza que los científicos de todo el mundo están firmemente convencidos de la importancia de aprender algoritmos para cascadas efectivas. Como confirmación, aquí hay una cita de un artículo de Paul Viola y Michael Jones [4]:

The overall training process involves two types of tradeoffs. In most cases classifiers with more features will achieve higher detection rates and lower false positive rates. At the same time classifiers with more features require more time to compute. In principle one could define an optimization framework in which
– the number of classifier stages,
– the number of features, $$$n_i$, of each stage,
– the threshold of each stage
are traded off in order to minimize the expected number of features $$$N$given a target for $$$F$and $$$D$. Unfortunately finding this optimum is a tremendously difficult problem.

Es interesante que nuestra revisión de la literatura relevante, realizada en 2016, mostró que en ese momento no había algoritmos de entrenamiento efectivos para los clasificadores en cascada. Por cierto, fue entonces cuando en Smart Engines resolvimos este problema. Estudiamos las siguientes funciones, que dependen de errores de detección del primer tipo ($$$E_1$), errores de detección del segundo tipo ($$$E_2$) y dificultad media ($$$N$):

$$

$$F\left(E_1,\ {\ E}_2,\ N\right)=\ {\ \beta_1\cdot\ E}_1+\ \beta_2\cdot E_2+\ \ \beta_3\cdot N.$$

Selección de parámetros. $$$\beta_1$, $$$\beta_2$y $$$\beta_3$, establezca el costo relativo de los errores del primer y segundo tipo, así como la complejidad del detector resultante. Además, en el proceso de entrenamiento del clasificador en cascada, se utilizó un algoritmo codicioso para enumerar los parámetros en cada nivel a fin de obtener cascadas que maximicen la funcionalidad seleccionada. Una descripción detallada del algoritmo desarrollado está más allá del alcance de este artículo, pero siempre estamos listos para compartirlo con usted, nuestro lector, al proporcionar un enlace bibliográfico [5].

Conclusión

Para resumir todo lo que se dijo de nuestra parte, utilizando el modelo clasificador en cascada como ejemplo, queremos sacar las siguientes conclusiones:

1. Rara vez es posible encontrar un trabajo científico en el que todos los detalles necesarios se describen a fondo.
2. Es muy útil volver a leer artículos científicos, pensando seriamente en las propiedades y limitaciones de los modelos presentados en ellos, incluso si a primera vista parece que todo está "masticado" en el artículo.
3. Siempre habrá un lugar para una investigación científica digna, incluso si el modelo estudiado fue propuesto hace 20 años.

Estamos muy contentos si el material presentado en este artículo es útil y, por supuesto, siempre está listo para una discusión fructífera en los comentarios.

Gracias.