Quelques faits sur les classificateurs en cascade, qui sont rarement sérieusement pris en compte dans les articles scientifiques.

Salut Habr! Aujourd'hui, nous parlerons à nouveau de reconnaissance. À savoir, sur un modèle de reconnaissance aussi simple qu'un classificateur en cascade. Cette cascade est utilisée dans la méthode populaire de Viola et Jones, sur laquelle ils ont déjà écrit tant de fois sur Habré (par exemple, ici , ici et ici ). Ce qui est triste, c'est que malgré l'abondance d'articles, personne n'a sérieusement étudié les classificateurs en cascade. Et pas seulement sur Habré, mais aussi la communauté scientifique. Bien que le classificateur en cascade semble simple, il existe de nombreux pièges et fonctionnalités intéressantes. Par conséquent, nous sommes pressés de partager nos connaissances avec vous. Donc, si vous êtes intéressé, bienvenue au chat.

Le classificateur en cascade est un modèle très simple. Il se compose de plusieurs niveaux successifs, chacun pouvant être représenté comme un classificateur binaire. Le précédent étudié est alimenté à l'entrée du premier niveau puis «voyage» niveau par niveau. Si au niveau suivant, le classificateur reconnaît le précédent comme négatif, il n'est plus analysé par les classificateurs restants de la cascade. Un modèle aussi simple est devenu populaire après la publication de la méthode Viola et Jones [1], où, comme indiqué, il a été utilisé pour fournir des performances élevées. Mais est-ce juste pour ça? Est-ce juste un classificateur en cascade? Voyons ça!

Nous allons construire l'article d'aujourd'hui sur Habré dans un format nouveau pour nous. Nous sélectionnerons plusieurs déclarations que nous révélerons en détail et même réfuterons quelque part. Alors, commençons!

Le classificateur en cascade de la méthode Viola et Jones est simplement utilisé pour accélérer le fonctionnement du détecteur d'objet

Dans l'article original [1] sur la toute première page, il y a une telle phrase:

La troisième contribution majeure de cet article est une méthode pour combiner des classificateurs successivement plus complexes dans une structure en cascade qui augmente considérablement la vitesse du détecteur en concentrant l'attention sur les régions prometteuses de l'image.

En effet, la méthode originale de Viola et Jones est conçue pour rechercher des objets dans l'image. De plus, le problème de détection est résolu par la méthode de la fenêtre coulissante utilisant un classificateur binaire, qui est appliqué à chaque point de l'image étudiée à différentes échelles. Le déséquilibre des données étudiées au stade de la détection (régions «vides» sans l'objet souhaité dans chaque image étudiée, des millions voire des milliards de fois plus que des régions avec des objets) a incité à utiliser une cascade - un mécanisme qui vous permet de couper rapidement les régions «vides».

Mais il s'agissait d'utiliser un classificateur déjà formé. Passons maintenant à la procédure de formation du classificateur. Il s'avère qu'il y a exactement le même problème de déséquilibre des échantillons: le nombre d'exemples négatifs est beaucoup plus important (des millions voire des milliards de fois plus) que le nombre d'exemples positifs. Mais grâce à son architecture, chaque nouveau niveau de la cascade est entraîné par la méthode AdaBoost non pas sur l'ensemble de l'échantillon d'entraînement négatif, mais uniquement sur un ensemble limité d'erreurs des niveaux précédents de la cascade! Cela vous permet d'exécuter la machine d'entraînement AdaBoost sur un échantillon équilibré et limité!

Comme vous pouvez le voir, l'utilisation du classificateur en cascade dans la méthode Viola et Jones tire deux fois:

1. Il vous permet de former facilement le classificateur, évitant naturellement le problème de l'ensemble d'entraînement "infini";
2. Il permet un écrêtage rapide des régions «vides» lors de la détection d'objets, grâce à laquelle une productivité moyenne élevée est atteinte.

Eh bien, continuons à étudier la cascade classique et passons à la question de la performance.

Dans cet esprit, un classificateur en cascade est un outil d'accélération.

Revenons une fois de plus à la question du but de la cascade, mais maintenant d'un autre côté. Si vous regardez mathématiquement le classificateur en cascade, vous pouvez voir que la cascade est une forme conjonctive de classificateurs forts (dont chacun peut être représenté comme une composition linéaire d'attributs):

$$

$$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],$$

Où $$$\left[\bullet\right]$- fonction indicateur.

Dans des conditions d'un nombre limité d'attributs disponibles (qui, en pratique, lors de la recherche de performances, il s'avère être une situation normale), la forme conjonctive de classificateurs forts a une plus grande capacité d'expression qu'un classificateur linéaire unique. Ceci est facile à comprendre si vous imaginez un exemple simple, où l'espace d'entité se compose de deux éléments, et les objets positifs et négatifs exprimés dans les coordonnées de ces caractéristiques sont situés comme indiqué dans la figure ci-dessous (les objets verts sont les positifs et les rouges les négatifs). Il est clair qu'il n'existe pas de classificateur linéaire unique capable de diviser correctement cet échantillon. Mais une cascade de quatre niveaux permettrait de faire face à cette tâche garantie.


Ainsi, l'utilisation d'un classificateur en cascade, en plus d'augmenter la productivité, fournit également une plus grande puissance expressive qu'un classificateur linéaire unique, dans des conditions d'un nombre limité de caractéristiques.

Le classificateur en cascade offre des performances constamment élevées et peut être facilement utilisé dans les systèmes de reconnaissance en temps réel

Comme nous l'avons dit ci-dessus, le schéma en cascade vous permet d'obtenir des performances élevées en raison du filtrage rapide des régions "vides", car leur nombre est supérieur de plusieurs ordres de grandeur au nombre de régions contenant l'objet. Le temps de traitement de la région «vide» diffère du temps de traitement de la région avec l'objet de plusieurs fois (proportionnellement à la longueur de la cascade - le nombre de niveaux de la cascade).

Étant donné que le nombre de régions contenant l'objet diffère d'une image à l'autre, le temps de traitement de chaque image est également différent. En raison du fait qu'il y a beaucoup moins de régions avec un objet sur le cadre que de régions sans objet, la différence de temps de traitement est mesurée non pas des dizaines de fois, mais des dizaines de pour cent, ce qui est néanmoins significatif dans les systèmes de reconnaissance industrielle.

Ainsi, le temps de fonctionnement du classificateur en cascade dans différentes images peut varier considérablement. Par conséquent, lors de la réalisation de mesures sérieuses de la performance des classificateurs, des mesures doivent être faites du temps de fonctionnement en moyenne et dans les pires cas. Et soyez toujours prêt pour de telles «incohérences» temporaires lorsque vous utilisez des classificateurs en cascade.

Dans notre pratique, nous avons déjà rencontré de sérieux problèmes en raison d'un écart important dans le temps de fonctionnement en cascade dans la moyenne et le pire des cas. Dans le cadre du projet d'automatisation de la route à péage, nous avons résolu le problème de la reconnaissance du type de voiture, où l'une des principales sous-tâches était le problème du comptage des essieux. Bien sûr, nous avons utilisé la méthode Viola et Jones pour détecter les roues sur des cadres individuels. En raison de la grande variabilité des roues (voir la figure ci-dessous), la cascade entraînée était assez longue (20 niveaux). Nous avons observé en direct des problèmes désagréables associés à des temps de traitement différents pour chaque image, ce qui nous a sérieusement empêchés de construire un système de reconnaissance en temps réel.


Nous avons ensuite développé l'idée d'un classificateur classique en cascade vers un arbre de décision à part entière, développant une technologie d'apprentissage unique pour un tel arbre de décision (rappelez-vous qu'il était nécessaire de proposer un algorithme qui nous permettrait d'éviter les problèmes associés à l'ensemble de formation `` sans fin ''). Les détails de cet algorithme peuvent être trouvés dans nos travaux scientifiques [3]. Nous ne rapportons ici que quelques faits:

1. Le chemin le plus long dans un arbre formé se compose de 6 classificateurs forts (le schéma d'un classificateur d'arbre formé est illustré dans la figure ci-dessous).
2. Un classificateur d'arbres formé a fourni une meilleure qualité de travail par rapport à une cascade précédemment formée. Ceci est logique et découle du fait que le pouvoir expressif de la cascade arborescente (qui est une forme conjonctive-disjonctive) est supérieur au pouvoir expressif de la cascade (forme conjonctive).
3. Un classificateur d'arbres formé a sérieusement contourné la cascade dans le pire des cas, presque sans perdre en moyenne.

Le tableau ci-dessous présente des comparaisons numériques des classificateurs en cascade et en arborescence.


Ainsi, si vous voulez vraiment utiliser les classificateurs en cascade dans les systèmes de reconnaissance en temps réel, souvenez-vous toujours des caractéristiques associées à la vitesse de travail dans la moyenne et dans les pires cas.

Les technologies de formation des classificateurs en cascade sont si évidentes qu'il n'y a rien à craindre sérieusement.

Oh, c'est probablement l'un des sujets les plus difficiles liés aux classificateurs en cascade. L'essentiel est que dans tous les articles que nous avons rencontrés, le processus d'apprentissage en cascade est décrit si mal, superficiellement et sans justification appropriée de l'efficacité de l'algorithme d'apprentissage en cascade. Habituellement, l'algorithme d'apprentissage en cascade ressemble à ceci:

1. Décider des valeurs de la part de la fausse reconnaissance ($$$F$) pour toute la cascade.
2. Décider des valeurs de la part de la vraie reconnaissance ($$$d$) et des fractions de fausse reconnaissance ($$$f \lt F$) pour chaque niveau de reconnaissance.
3. Choisissez un échantillon de validation pour évaluer honnêtement les indicateurs de qualité du classificateur final.
4. Former chaque nouveau niveau de la cascade (qui, rappelons-le, est formé sur tous les exemples positifs disponibles, ainsi que sur les fausses erreurs positives de la cascade actuelle) afin que ses performances $$$d_i$et $$$f_i$étaient pas pire que ce qui est donné, c'est $$$d_i>d$et $$$f_i \lt f$. Soit dit en passant, le processus visant à garantir ces indicateurs en soi présente également un grand intérêt.
5. Ajoutez le niveau nouvellement formé à la cascade et évaluez ses indicateurs de qualité dans l'échantillon de validation. Si le taux de fausse reconnaissance est inférieur à l'objectif$$$F$, puis terminez la formation. Sinon, passez à l'étape 4 pour apprendre un nouveau niveau de cascade.

Si à la suite de l'algorithme ci-dessus formé $$$K$niveaux de la cascade, vous pouvez alors estimer la complexité moyenne de la part de reconnaissance correcte de la cascade comme suit:

$$

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

Où $$$n_i$- complexité $$$i$niveau cascade $$$p_i$- probabilité de calcul $$$i$cascade de niveaux, et $$$d_i$- part de reconnaissances correctes $$$i$cascade de niveaux.

Comme vous pouvez le voir, la complexité de la cascade ne participe pas à l'algorithme de formation présenté, donc, bien sûr, elle ne peut pas être qualifiée d'efficacité en performance. Dans le même temps, nous savons avec certitude que les scientifiques du monde entier sont fermement convaincus de l'importance d'apprendre des algorithmes pour des cascades efficaces. Pour confirmation, voici une citation d'un article de Paul Viola et 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.

Il est intéressant de noter que notre revue de la littérature pertinente, réalisée en 2016, a montré qu'à cette époque, il n'existait aucun algorithme de formation efficace pour les classificateurs en cascade. Au fait, c'est alors que chez Smart Engines, nous avons résolu ce problème. Nous avons étudié la fonctionnalité suivante, qui dépend des erreurs de détection du premier type ($$$E_1$), des erreurs de détection du second type ($$$E_2$) et difficulté moyenne ($$$N$):

$$

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

Sélection des paramètres $$$\beta_1$, $$$\beta_2$et $$$\beta_3$, définissez le coût relatif des erreurs du premier et du deuxième type, ainsi que la complexité du détecteur résultant. De plus, dans le processus de formation du classificateur en cascade, un algorithme gourmand a été utilisé pour énumérer les paramètres à chaque niveau afin d'obtenir des cascades qui maximisent la fonction sélectionnée. Une description détaillée de l'algorithme développé dépasse le cadre de cet article, mais nous sommes toujours prêts à le partager avec vous, notre lecteur, en fournissant un lien bibliographique [5].

Conclusion

Pour résumer tout ce qui a été dit de notre part, en utilisant le modèle de classificateur en cascade comme exemple, nous voulons tirer les conclusions suivantes:

1. Il est rarement possible de rencontrer un travail scientifique dans lequel tous les détails nécessaires sont décrits en détail.
2. Il est très utile de relire des articles scientifiques, en réfléchissant sérieusement aux propriétés et aux limites des modèles qui y sont présentés, même si à première vue il semble que tout soit «mâché» dans l'article.
3. Il y aura toujours une place pour une recherche scientifique digne, même si le modèle étudié a été proposé il y a 20 ans.

Nous sommes très heureux si le matériel présenté dans cet article est utile et, bien sûr, toujours prêt pour une discussion fructueuse dans les commentaires.

Remercier.