Skip to content
Назад к результатам поиска

Online Bagging

Автор метода
Oza, N. C. & Russell, S.
Год
2001
Тип
Online ensemble (streaming bagging)
Семейство
Machine learning

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Online Bagging — это потоковый ансамблевый метод, представленный Oza и Russell в 2001 году, который адаптирует классическую структуру бутстрэп-агрегирования (Bagging) к условиям онлайн-обучения.

Вместо повторной выборки фиксированного набора данных, каждый поступающий экземпляр подается каждому базовому ученику количество раз, распределенное по Пуассону с параметром 1 (Poisson(1)), что точно аппроксимирует бутстрэп-выборку по мере эволюции потока. Результатом является робастный, инкрементально обновляемый ансамбль, который может обрабатывать дрейф концепции и непрерывное поступление данных без хранения всего набора данных.

Интуиция метода

Классический Bagging выполняет случайную бутстрэп-выборку из фиксированного набора данных и обучает одно дерево для каждой выборки. Online Bagging имитирует это, никогда не видя весь набор данных одновременно: когда появляется новый пример, он подается каждому базовому ученику случайное количество раз, взятое из распределения Пуассона со средним значением 1. В среднем каждый ученик видит пример один раз — точно так же, как бутстрэп-повторная выборка достигается в пакетном режиме — но случайность декоррелирует учеников. Поскольку данные не нужно хранить, ансамбль может неограниченно расти вместе с потоком и естественно адаптироваться к меняющимся распределениям со временем.

История

Online Bagging был представлен Nitesh Oza и Stuart Russell на конференции AISTATS 2001 как теоретическое и практическое расширение алгоритма Bagging Breiman 1996 года для онлайн-среды. Ключевая идея — замена бутстрэп-повторной выборки на взвешивание Пуассона (Poisson(1)) на экземпляр — сделала аппроксимацию математически строгой. Он стал фундаментальным алгоритмом в литературе по потоковому машинному обучению и является базовым ансамблем в таких платформах, как MOA (Massive Online Analysis), которая с 2010 года стимулирует большинство эмпирических оценок классификаторов потоков.

Когда применять

Используйте Online Bagging, когда данные поступают в виде непрерывного потока, а хранение полного набора данных невозможно или запрещено (например, журналы датчиков, кликстримы, финансовые тиковые данные, мониторинг в реальном времени). Он подходит, когда вам нужна классификация или регрессия, которая обновляется с каждым новым наблюдением, терпима к легкому дрейфу концепции и остается эффективной по памяти. Не используйте Online Bagging в качестве прямой замены пакетного Random Forest на фиксированном наборе данных малого или среднего размера — пакетные ансамбли с перекрестной проверкой там покажут лучшие результаты. Также избегайте его, когда поток данных демонстрирует сильный резкий дрейф без добавления явного механизма обнаружения дрейфа.

Ограничения и замечания

  • На статических наборах данных пакетные методы, такие как Random Forest или XGBoost, стабильно превосходят Online Bagging, поскольку они могут использовать полную перекрестную проверку и оптимальные разбиения.
  • Базовый Online Bagging предлагает лишь ограниченную устойчивость к сильному дрейфу концепции; специализированные детекторы дрейфа (например, ADWIN) должны быть добавлены внешне.
  • Весовые коэффициенты Пуассона вносят дополнительную дисперсию на экземпляр, что может замедлить сходимость на коротких потоках.
  • Интерпретируемость низкая: ансамбль из множества инкрементально выращенных деревьев сложнее анализировать, чем одно дерево решений.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Обрабатывает данные по одному экземпляру за раз с постоянным объемом памяти, обеспечивая действительно неограниченные потоки.
  • Весовые коэффициенты Пуассона теоретически аппроксимируют бутстрэп-повторную выборку, обеспечивая снижение дисперсии ансамбля, сравнимое с пакетным Bagging.
  • Естественно распараллеливается: каждый базовый ученик обновляется независимо, что делает его подходящим для распределенных потоковых архитектур.
  • Нет гиперпараметров, столь же чувствительных, как глубина дерева — ансамбль саморегулируется за счет разнообразия.
  • Легко расширяется до многоклассовой классификации и регрессии без структурных изменений.

Применение

  • Обнаружение мошенничества в реальном времени на непрерывных потоках транзакций.
  • Прогнозная аналитика для обслуживания на основе потоков данных с датчиков в промышленных IoT-системах.
  • Прогнозирование кликабельности в онлайн-рекламе, где поведение пользователей постоянно меняется.
  • Обнаружение сетевых вторжений в потоках пакетов с высокой пропускной способностью.
  • Экологический мониторинг: инкрементальная классификация показаний датчиков качества воздуха или погоды.

Как это работает

Как это работает

1

Для каждого поступающего экземпляра вес k независимо выбирается из распределения Пуассона (Poisson(1)) для каждого базового ученика. Вес 0 означает, что ученик полностью пропускает этот экземпляр; вес 2 означает, что он учится на экземпляре дважды. Это стохастическое взвешивание является онлайн-аналогом бутстрэп-повторной выборки и составляет математическое ядро алгоритма.

Формула
k \sim \text{Poisson}(1)
2

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

3

Когда требуется предсказание, все M базовых учеников выдают свой индивидуальный результат для запрошенного экземпляра. Ансамбль объединяет их большинством голосов для классификации или арифметическим средним для регрессии, давая ту же агрегатную логику, что и пакетный Bagging, но вычисленную на инкрементально обученных моделях.

Формула
\hat{y} = \text{mode/mean of } M \text{ base learners}

Частые ошибки

  • Оценивать Online Bagging с помощью отложенного тестового набора, созданного до начала обучения — вместо этого используйте преквенциальную (тест-затем-обучение) оценку, которая является стандартом в потоковом машинном обучении.
  • Предполагая, что стандартное количество базовых учеников (часто 10) достаточно; для стабильных предсказаний обычно требуется от 50 до 100 учеников.
  • Игнорирование дрейфа концепции: развертывание Online Bagging на дрейфующем потоке без обнаружения дрейфа приводит к скрытому снижению точности.
  • Сравнение точности на статических бенчмарках с пакетными методами и вывод о том, что Online Bagging уступает — правильное сравнение — это точность на экземпляр, увиденный на потоковом бенчмарке.
  • Использование базовых учеников, которые не являются истинно инкрементальными (например, переобученные пакетные деревья), что сводит на нет преимущества онлайн-фреймворка в памяти и скорости.

Часто задаваемые вопросы

Почему именно Пуассон(1)?

Распределение Пуассона со средним значением 1 аппроксимирует количество раз, которое наблюдение появляется в бутстрэп-выборке размера n по мере того, как n стремится к бесконечности. Использование Пуассона(1) на экземпляр на ученика точно воспроизводит это предельное поведение, делая онлайн-аппроксимацию теоретически обоснованной.

Чем Online Bagging отличается от Adaptive Random Forest?

Adaptive Random Forest (Gomes et al., 2017) расширяет Online Bagging, добавляя случайную подвыборку признаков при каждом разбиении (как в пакетном Random Forest) и интегрируя детекторы дрейфа для каждого дерева, которые сбрасывают отдельные ученики при обнаружении дрейфа концепции. Online Bagging является более простой основой; Adaptive Random Forest — это текущий передовой потоковый ансамбль, построенный на его основе.

Какой базовый ученик мне следует использовать?

Наиболее распространенным выбором является Hoeffding Tree (также называемый VFDT), который является каноническим инкрементальным деревом решений. Он использует границы Хоффдинга, чтобы определить, когда было увидено достаточно данных в узле для разбиения, сохраняя дерево обновляемым без хранения прошлых экземпляров.

Сколько базовых учеников мне нужно?

Эмпирические бенчмарки в рамках MOA предполагают использование 50–100 базовых учеников для стабильной производительности ансамбля на большинстве потоковых задач. Меньшее количество учеников снижает вычислительные затраты, но увеличивает дисперсию предсказаний, особенно на ранних этапах потока.

Как следует оценивать классификатор Online Bagging?

Используйте преквенциальную оценку: для каждого поступающего экземпляра сначала предскажите его метку, затем обновите модель. Точность вычисляется как скользящее среднее правильных предсказаний. Это позволяет избежать смещения взгляда вперед и отражает реальные условия развертывания.

Похожие методы

Источники

  1. Oza, N. C., & Russell, S. (2001). Online bagging and boosting. In Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics (AISTATS 2001), pp. 105–112.

    Открыть ссылку на публикацию
    Скопировано.
  2. Bifet, A., Holmes, G., Kirkby, R., & Pfahringer, B. (2010). MOA: Massive Online Analysis. Journal of Machine Learning Research, 11, 1601–1604.

    Открыть ссылку на публикацию
    Скопировано.