Alguns fatos sobre classificadores em cascata, que raramente são considerados seriamente em artigos científicos.

Oi Habr! Hoje vamos falar sobre reconhecimento novamente. Ou seja, sobre um modelo reconhecedor tão simples como um classificador em cascata. Essa cascata é usada no método popular de Viola e Jones, sobre o qual eles já escreveram tantas vezes em Habré (por exemplo, aqui , aqui e aqui ). O triste é que, apesar da abundância de artigos, ninguém estudou seriamente os classificadores em cascata. E não apenas em Habré, mas também na comunidade científica. Embora o classificador em cascata pareça simples, existem muitas armadilhas e recursos interessantes. Portanto, estamos com pressa de compartilhar nosso conhecimento com você. Então, se estiver interessado, seja bem-vindo ao gato.

O classificador em cascata é um modelo muito simples. Consiste em vários níveis sucessivos, cada um dos quais pode ser representado como um classificador binário. O precedente investigado é alimentado na entrada do primeiro nível e depois "viaja" nível por nível. Se, no próximo nível, o classificador reconhecer o precedente como negativo, ele não será mais analisado pelos demais classificadores da cascata. Um modelo tão simples tornou-se popular após a publicação do método Viola e Jones [1], onde, como afirmado, era usado para fornecer alto desempenho. Mas é só por isso? É apenas um classificador em cascata? Vamos descobrir!

Vamos construir o artigo de hoje sobre Habré em um formato novo para nós. Selecionaremos várias declarações que revelaremos em detalhes e até refutaremos em algum lugar. Então vamos começar!

O classificador em cascata no método Viola e Jones é simplesmente usado para acelerar a operação do detector de objetos

No artigo original [1], na primeira página, existe uma frase:

A terceira grande contribuição deste artigo é um método para combinar classificadores sucessivamente mais complexos em uma estrutura em cascata que aumenta drasticamente a velocidade do detector, concentrando a atenção em regiões promissoras da imagem.

De fato, o método original de Viola e Jones foi projetado para procurar objetos na imagem. Além disso, o problema de detecção é resolvido pelo método da janela deslizante usando um classificador binário, que é aplicado em cada ponto da imagem investigada em diferentes escalas. O desequilíbrio dos dados estudados no estágio de detecção (regiões "vazias" sem o objeto desejado em cada imagem em estudo, milhões ou bilhões de vezes mais que regiões com objetos) levou ao uso de uma cascata - um mecanismo que permite cortar rapidamente regiões "vazias".

Mas era sobre usar um classificador já treinado. Agora vamos ao procedimento de treinamento do classificador. Acontece que existe exatamente o mesmo problema de desequilíbrio da amostra: o número de exemplos negativos é muitas vezes maior (milhões e até bilhões vezes mais) do que o número de exemplos positivos. Mas, graças à sua arquitetura, cada novo nível da cascata é treinado pelo método AdaBoost, não em toda a amostra negativa de treinamento, mas apenas em um conjunto limitado de erros dos níveis anteriores da cascata! Isso permite que você execute a máquina de treinamento AdaBoost em uma amostra equilibrada e limitada!

Como você pode ver, o uso do classificador em cascata no método Viola e Jones dispara duas vezes:

1. Ele permite que você treine facilmente o classificador, evitando naturalmente o problema do conjunto de treinamento "infinito";
2. Ele fornece um recorte rápido de regiões "vazias" durante a detecção de objetos, devido à alta produtividade média obtida.

Bem, vamos continuar estudando a cascata clássica e voltando-se para a questão do desempenho.

Com isso em mente, um classificador em cascata é uma ferramenta de aceleração.

Voltemos mais uma vez à questão do propósito da cascata, mas agora, por outro lado. Se você observar matematicamente o classificador em cascata, poderá ver que a cascata é uma forma conjuntiva de classificadores fortes (cada um dos quais pode ser representado como uma composição linear 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],$$

Onde $$$\left[\bullet\right]$- função indicadora.

Dado o número limitado de atributos disponíveis (que, na prática, ao perseguir o desempenho, acaba sendo uma situação normal), a forma conjuntiva de classificadores fortes tem uma capacidade mais expressiva do que um único classificador linear. Isso é fácil de entender se você imaginar um exemplo simples, onde o espaço de feição consiste em dois elementos, e os objetos positivos e negativos expressos nas coordenadas dessas características estão localizados como mostrado na figura abaixo (os objetos verdes são os positivos e os vermelhos são os negativos). É claro que não existe um classificador linear único que possa dividir corretamente essa amostra. Mas uma cascata de quatro níveis lidaria com essa tarefa garantida.


Assim, o uso de um classificador em cascata, além de aumentar a produtividade, também fornece maior poder expressivo que um único classificador linear, em condições de um número limitado de recursos.

O classificador em cascata oferece alto desempenho consistente e pode ser facilmente usado em sistemas de reconhecimento em tempo real

Como dissemos acima, o esquema em cascata permite obter alto desempenho devido à rápida triagem de regiões "vazias", pois seu número é várias ordens de magnitude maiores que o número de regiões que contêm o objeto. O tempo de processamento de uma região "vazia" difere do tempo de processamento de uma região com um objeto várias vezes (proporcionalmente ao comprimento da cascata - o número de níveis em cascata).

Como o número de regiões que contêm o objeto é diferente de imagem para imagem, o tempo de processamento de cada quadro é diferente. Devido ao fato de haver significativamente menos regiões com um objeto no quadro do que regiões sem um objeto, a diferença no tempo de processamento é medida não dezenas de vezes, mas dezenas de por cento, o que, no entanto, é significativo nos sistemas de reconhecimento industrial.

Assim, o tempo de operação do classificador em cascata em diferentes imagens pode variar significativamente. Portanto, ao realizar medições sérias do desempenho dos classificadores, devem ser feitas medições do tempo de operação em média e nos piores casos. E sempre esteja preparado para essas "inconsistências" temporárias ao usar classificadores em cascata.

Em nossa prática, já enfrentamos sérios problemas devido a uma discrepância significativa no tempo de operação em cascata nos casos médios e piores. Como parte do projeto de automação de rodovia com pedágio, resolvemos o problema de reconhecer o tipo de carro, onde uma das principais subtarefas era o problema de contar rodados. Obviamente, usamos o método Viola e Jones para detectar rodas em quadros individuais. Devido à grande variabilidade das rodas (veja a figura abaixo), a cascata treinada era bastante longa (20 níveis). Assistimos ao vivo problemas desagradáveis ​​associados a diferentes tempos de processamento para cada quadro, o que nos impediu seriamente de construir um sistema de reconhecimento em tempo real.


Em seguida, desenvolvemos a ideia de um classificador em cascata clássico em uma árvore de decisão completa, desenvolvendo uma tecnologia de aprendizado exclusiva para essa árvore de decisão (lembre-se de que era necessário propor um algoritmo que nos permitisse evitar os problemas associados ao conjunto de treinamento "sem fim"). Detalhes deste algoritmo podem ser encontrados em nosso trabalho científico [3]. Aqui relatamos apenas alguns fatos:

1. O caminho mais longo em uma árvore treinada consiste em 6 classificadores fortes (o esquema de um classificador de árvore treinado é mostrado na figura abaixo).
2. Um classificador de árvore treinado forneceu uma melhor qualidade de trabalho em comparação com uma cascata treinada anteriormente. Isso é lógico e decorre do fato de que o poder expressivo da cascata em forma de árvore (que é uma forma conjuntivo-disjuntiva) é maior que o poder expressivo da cascata (forma conjuntiva).
3. Um classificador de árvores treinado contornou seriamente a cascata no pior dos casos, quase sem perder em média.

A tabela abaixo apresenta comparações numéricas de classificadores em cascata e árvore.


Portanto, se você realmente deseja usar classificadores em cascata em sistemas de reconhecimento em tempo real, lembre-se sempre dos recursos associados à velocidade do trabalho nos casos médios e piores.

As tecnologias de treinamento em cascata de classificadores são tão óbvias que não há com o que se preocupar seriamente.

Ah, esse é provavelmente um dos tópicos mais difíceis relacionados aos classificadores em cascata. O ponto principal é que, em todos os artigos que encontramos, o processo de aprendizado em cascata é descrito de maneira tão pobre, superficial e sem justificativa adequada da eficácia do algoritmo de aprendizado em cascata. Normalmente, o algoritmo de aprendizado em cascata é mais ou menos assim:

1. Decida sobre os valores da parcela do falso reconhecimento ($$$F$) para toda a cascata.
2. Decida sobre os valores da parcela do verdadeiro reconhecimento ($$$d$) e frações de falso reconhecimento ($$$f \lt F$) para cada nível de reconhecimento.
3. Decida uma amostra de validação para avaliar honestamente os indicadores de qualidade do classificador final.
4. Treine cada novo nível da cascata (que, lembramos, é treinado em todos os exemplos positivos disponíveis, bem como em erros positivos falsos positivos da cascata atual) para que seu desempenho $$$d_i$e $$$f_i$não foram piores do que os dados, isto é $$$d_i>d$e $$$f_i \lt f$. A propósito, o processo de garantir esses indicadores em si também é de grande interesse.
5. Adicione o nível recém treinado à cascata e avalie seus indicadores de qualidade na amostra de validação. Se a taxa de falso reconhecimento for menor que a meta$$$F$, então termine o treinamento. Caso contrário, vá para a etapa 4 para aprender um novo nível de cascata.

Se, como resultado do algoritmo acima treinado $$$K$níveis da cascata, é possível estimar a complexidade média da parcela do reconhecimento correto da cascata da seguinte maneira:

$$

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

Onde $$$n_i$- complexidade $$$i$nível em cascata $$$p_i$- probabilidade de cálculo $$$i$cascata de nível e $$$d_i$- compartilhamento de reconhecimentos corretos $$$i$cascata de nível.

Como você pode ver, a complexidade da cascata não participa do algoritmo de treinamento apresentado; portanto, é claro, não pode ser chamado de eficaz no desempenho. Ao mesmo tempo, sabemos com certeza que cientistas de todo o mundo estão firmemente convencidos da importância de aprender algoritmos para cascatas eficazes.Como confirmação, aqui está uma citação de um artigo de Paul Viola e 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.

É interessante que nossa revisão da literatura relevante, feita em 2016, mostrou que naquela época não havia algoritmos de treinamento eficazes para classificadores em cascata. A propósito, foi então que nós da Smart Engines resolvemos esse problema. Estudamos o seguinte funcional, que depende de erros de detecção do primeiro tipo ($$$E_1$), erros de detecção do segundo tipo ($$$E_2$) e dificuldade média ($$$N$):

$$

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

Seleção de parâmetros $$$\beta_1$, $$$\beta_2$e $$$\beta_3$, defina o custo relativo dos erros do primeiro e do segundo tipo, bem como a complexidade do detector resultante. Além disso, no processo de treinamento do classificador em cascata, um algoritmo ganancioso foi usado para enumerar parâmetros em cada nível, a fim de obter cascatas que maximizem o funcional selecionado. Uma descrição detalhada do algoritmo desenvolvido está além do escopo deste artigo, mas estamos sempre prontos para compartilhá-lo com você, nosso leitor, fornecendo um link bibliográfico [5].

Conclusão

Para resumir tudo o que foi dito de nossa parte, usando o modelo de classificador em cascata como exemplo, queremos tirar as seguintes conclusões:

1. Raramente é possível encontrar um trabalho científico no qual todos os detalhes necessários sejam detalhadamente descritos.
2. É muito útil reler artigos científicos, pensando seriamente nas propriedades e limitações dos modelos apresentados neles, mesmo que à primeira vista pareça que tudo está "mastigado" no artigo.
3. Sempre haverá um lugar para pesquisas científicas dignas, mesmo que o modelo estudado tenha sido proposto há 20 anos.

Ficamos muito satisfeitos se o material apresentado neste artigo for útil e, é claro, sempre pronto para uma discussão proveitosa nos comentários.

Obrigado.