Каскадная структура классификаторов

Каскадная структура классификаторов (каскадный классификатор, cascaded classifier) — это метод машинного обучения, при котором несколько последовательно соединённых классификаторов (моделей) обрабатывают входные данные поэтапно, с целью повышения общей точности и скорости принятия решений. Каждый последующий классификатор в цепочке получает на вход только те объекты, которые не были отвергнуты или классифицированы предыдущими. Такой подход позволяет отсеивать заведомо ложные или неинтересные варианты на ранних стадиях, экономя вычислительные ресурсы и уменьшая количество ложных срабатываний.

История

Идея каскадной обработки данных восходит к 1960-м годам, когда в статистике и теории распознавания образов начали применяться последовательные процедуры принятия решений. Одним из первых формальных описаний стала работа Абрахама Вальда по последовательному анализу (sequential analysis), где решение принималось после накопления определённого количества наблюдений.

В контексте компьютерного зрения и машинного обучения каскадные классификаторы получили широкое распространение после публикации в 2001 году статьи Пола Виолы и Майкла Джонса «Rapid Object Detection using a Boosted Cascade of Simple Features». Предложенный ими алгоритм для обнаружения лиц на изображениях в реальном времени сочетал в себе несколько ключевых элементов: интегральное представление изображения, бустинг (AdaBoost) и каскадную структуру. Этот метод позволил достичь скорости обработки 15 кадров в секунду на оборудовании того времени, что стало прорывом в области компьютерного зрения.

В последующие годы каскадные структуры адаптировались для решения задач в других областях: обработки естественного языка, биоинформатики, финансового мониторинга и робототехники.

Принцип работы

Каскадная структура классификаторов представляет собой последовательность (каскад) из N этапов, где каждый этап — это отдельный классификатор (часто называемый «слабый» или «простой» классификатор). Входные данные (например, изображение, текст, числовой вектор) поступают на первый этап. Если классификатор первого этапа принимает объект как положительный (то есть считает, что объект принадлежит искомому классу), объект передаётся на следующий этап. Если объект отвергается на любом этапе, он немедленно классифицируется как отрицательный и дальнейшая обработка прекращается.

Таким образом, каскад работает по принципу «от грубого к точному»:

• Ранние этапы содержат простые и быстрые классификаторы, которые пропускают большинство объектов, но отсеивают большую часть заведомо ложных вариантов.
• Поздние этапы используют более сложные и ресурсоёмкие модели, которые обрабатывают только те объекты, которые прошли все предыдущие фильтры.

Классификация и виды

Каскадные структуры можно классифицировать по нескольким признакам.

По типу используемых классификаторов

• Каскад на основе бустинга — каждый этап представляет собой ансамбль слабых классификаторов (например, решающих пней), обученных с помощью алгоритма AdaBoost. Пример: детектор Виолы-Джонса.
• Каскад на основе нейронных сетей — этапы могут быть реализованы в виде свёрточных нейронных сетей (CNN) или многослойных перцептронов. Используется в задачах, требующих высокой точности на поздних стадиях.
• Каскад на основе опорных векторов (SVM) — каждый этап обучается как линейный или нелинейный классификатор SVM.
• Каскад на основе деревьев решений — этапы представляют собой решающие деревья или случайные леса.

По структуре каскада

• Линейный каскад — классическая последовательная цепочка, где каждый этап обрабатывает все объекты, прошедшие предыдущий.
• Древовидный (иерархический) каскад — на некоторых этапах объект может направляться по одному из нескольких путей в зависимости от результата классификации. Применяется в задачах с множеством классов.
• Каскад с обратной связью — результаты поздних этапов могут влиять на переобучение или перенастройку ранних этапов (редко используется на практике из-за сложности).

По области применения

• Детекция объектов (лица, автомобили, пешеходы на изображениях).
• Классификация текстов (фильтрация спама, определение тональности).
• Медицинская диагностика (последовательное выявление заболеваний по анализам).
• Финансовый мониторинг (выявление мошеннических транзакций).

Устройство и характеристики

Основные параметры

• Количество этапов (N) — чем больше этапов, тем выше потенциальная точность, но ниже скорость.
• Порог отсечения (threshold) — для каждого этапа задаётся порог, при котором объект считается положительным. Изменение порогов позволяет регулировать баланс между полнотой (recall) и точностью (precision).
• Скорость работы — измеряется в количестве обработанных объектов в единицу времени. Зависит от сложности классификаторов на ранних этапах.
• Уровень ложных срабатываний (false positive rate, FPR) — доля объектов, ошибочно принятых за положительные. Каскад позволяет снизить FPR за счёт последовательной фильтрации.
• Полнота (recall) — доля истинно положительных объектов, которые были правильно обнаружены. Полнота может снижаться, если на ранних этапах отсекаются сложные примеры.

Обучение каскада

Обучение каскадного классификатора — это итеративный процесс:

1. На первом этапе обучается простой классификатор на всех обучающих данных.
2. Все объекты, которые классификатор первого этапа принял как положительные (включая ложные срабатывания), передаются на второй этап.
3. Второй этап обучается на этих объектах, стараясь отсеять как можно больше ложных срабатываний.
4. Процесс повторяется до тех пор, пока не будет достигнуто заданное качество (например, уровень ложных срабатываний ниже 1 % и полнота выше 95 %).

Применение

Компьютерное зрение

Наиболее известное применение — детектор лиц Виолы-Джонса. Каскад из 38 этапов позволял обнаруживать лица на изображениях с высокой скоростью. Этот метод использовался в цифровых фотоаппаратах, веб-камерах и системах видеонаблюдения до появления глубоких нейронных сетей.

Каскадные классификаторы также применяются для обнаружения других объектов: номерных знаков автомобилей, дорожных знаков, жестов рук.

Обработка естественного языка

В системах фильтрации спама каскад может состоять из этапов: быстрый фильтр по ключевым словам, затем анализ метаданных письма, затем более сложный классификатор (например, наивный байесовский или нейросетевой). Это позволяет отсеивать до 90 % спама на первом этапе, не нагружая вычислительные ресурсы.

Медицина

В диагностических системах каскад может последовательно проверять наличие симптомов, результатов анализов и данных инструментальных исследований. Например, при скрининге рака шейки матки сначала анализируются общие показатели, затем — результаты цитологии, и только потом — данные биопсии.

Финансы

В системах обнаружения мошенничества каскад позволяет сначала отсеивать заведомо легитимные транзакции по простым правилам (сумма, частота, география), а затем применять сложные модели машинного обучения к подозрительным операциям.

Преимущества и недостатки

Преимущества

• Высокая скорость обработки за счёт раннего отсеивания большинства объектов.
• Низкий уровень ложных срабатываний при правильно настроенном каскаде.
• Модульность — каждый этап можно обучать и оптимизировать независимо.
• Возможность работы в реальном времени на устройствах с ограниченными ресурсами (встраиваемые системы, мобильные телефоны).

Недостатки

• Сложность обучения — требуется тщательная настройка порогов и количества этапов.
• Риск снижения полноты — сложные или нетипичные положительные объекты могут быть отсеяны на ранних этапах.
• Необходимость большого объёма обучающих данных для каждого этапа.
• Трудность адаптации к новым классам — при добавлении нового класса часто требуется переобучать весь каскад.

Примеры реализации

• OpenCV — библиотека компьютерного зрения содержит встроенные каскады Хаара (Haar cascades) и LBP-каскады для детекции лиц, глаз, улыбок и других объектов.
• Scikit-learn — библиотека машинного обучения в Python позволяет строить каскадные классификаторы с помощью класса CascadeClassifier (экспериментальная поддержка).
• TensorFlow / PyTorch — фреймворки глубокого обучения используются для построения каскадных нейросетевых детекторов, например, в архитектуре MTCNN (Multi-task Cascaded Convolutional Networks) для обнаружения лиц.

Источники

• Viola, P., & Jones, M. (2001). Rapid object detection using a boosted cascade of simple features. Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.
• Viola, P., & Jones, M. (2004). Robust real-time face detection. International Journal of Computer Vision, 57(2), 137–154.
• Freund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1), 119–139.
• OpenCV documentation: Cascade Classifier Training. OpenCV team.
• Zhang, K., Zhang, Z., Li, Z., & Qiao, Y. (2016). Joint face detection and alignment using multitask cascaded convolutional networks. IEEE Signal Processing Letters, 23(10), 1499–1503.