Полуавтоматическое дерево решений
- Автор метода
- Various (Levin & Shapiro; Zhu & Goldberg lineage)
- Год
- 2000s
- Тип
- Semi-supervised classifier / regressor
- Семейство
- Machine learning
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Полуавтоматическое дерево решений расширяет стандартные методы построения деревьев решений — такие как CART или C4.5 — для использования неразмеченных наблюдений наряду с размеченным обучающим набором.
Путем итеративного присвоения предварительных меток неразмеченным данным и их включения в процесс роста или разделения дерева, алгоритм может достичь лучшей точности, чем полностью контролируемое дерево, обученное только на размеченном подмножестве, что особенно ценно, когда разметка является дорогостоящей или трудоемкой.
Интуиция метода
Разметка каждого наблюдения является дорогостоящей, однако неразмеченные данные все еще содержат полезную структурную информацию о пространстве признаков. Полуавтоматическое дерево решений использует это, сначала строя дерево на основе нескольких размеченных примеров, используя это дерево для предварительной разметки неразмеченных данных, а затем переобучая на расширенном наборе. Повторяющиеся итерации одновременно уточняют как предварительные метки, так и структуру дерева, поэтому модель учится на общем распределении данных, даже когда истинных меток мало.
История
Полуавтоматическое обучение возникло в конце 1990-х годов, когда исследователи стремились использовать изобилие неразмеченных данных, доступных в таких областях, как веб-классификация и вычислительная биология. Варианты самообучения деревьев решений, где дерево итеративно размечает свои собственные неразмеченные данные, были одними из первых реализаций. Формальное изложение появилось в обзоре Zhu & Goldberg (2009), который помещает самообучение на основе деревьев в более широкую таксономию полуавтоматического обучения. С тех пор подходы были расширены до ансамблевых настроек, породив полуавтоматические случайные леса и градиентно-усиленные деревья.
Когда применять
Полуавтоматические деревья решений подходят, когда размеченные данные редки и дороги в получении, но имеется большой пул неразмеченных наблюдений — что часто встречается при аннотировании медицинских изображений, классификации текстов и мониторинге на основе датчиков. Они особенно полезны, когда общее распределение признаков хорошо улавливается неразмеченным пулом и когда требуется интерпретируемая человеком модель (дерево). Избегайте этого метода, когда размеченная выборка настолько мала, что начальное дерево крайне ненадежно, когда неразмеченные данные не являются репрезентативными для тестового распределения, или когда ожидается, что процесс псевдоразметки будет распространять систематические ошибки (предвзятость подтверждения). В этих случаях чисто контролируемые методы на чистых размеченных данных или альтернативные полуавтоматические подходы, такие как распространение меток или совместное обучение, могут быть более безопасными.
Ограничения и замечания
- Ошибки псевдоразметки от ненадежного начального дерева могут усиливаться в течение итераций, снижая производительность по сравнению с полностью контролируемым базовым методом.
- Метод предполагает, что неразмеченные данные имеют то же базовое распределение, что и размеченные данные; сдвиг распределения нарушает это предположение.
- Вычислительные затраты растут с каждой итерацией, поскольку деревья переобучаются на все больших эффективных наборах данных.
- Выбор порога уверенности для включения псевдометок требует тщательной настройки и перекрестной проверки.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Использует неразмеченные данные для повышения точности при малом количестве размеченных примеров, снижая затраты на аннотирование.
- Сохраняет интерпретируемость деревьев решений: результирующая модель представляет собой читаемый человеком набор правил «если-то».
- Естественно обрабатывает смешанные типы признаков — непрерывные, категориальные, бинарные — без предварительной нормализации.
- Итеративное самообучение легко реализуется поверх любого существующего алгоритма построения деревьев.
- Может улавливать нелинейные границы и взаимодействия признаков, которые упускают линейные полуавтоматические модели.
Применение
- Классификация медицинских изображений и записей, где экспертная аннотация дорога, а существует большой архив неаннотированных данных.
- Классификация текстов и документов с небольшими размеченными корпусами и большими неразмеченными коллекциями.
- Анализ данных с датчиков и IoT, где лишь часть сегментов временных рядов размечена вручную.
- Задачи биоинформатики, такие как предсказание функции генов, с небольшим количеством экспериментально подтвержденных меток.
- Обнаружение мошенничества, когда размеченные случаи мошенничества редки по сравнению с объемом неразмеченных транзакций.
Как это работает
Как это работает
Стандартное дерево решений (например, CART или C4.5) подгоняется, используя только размеченную часть набора данных. Эта начальная модель дает первое приближение к границам принятия решений и служит затравкой для последующих полуавтоматических итераций.
Каждое неразмеченное наблюдение пропускается через текущее дерево, и предсказанный класс (для классификации) или предсказанное значение (для регрессии) присваивается в качестве предварительной метки. Оценки уверенности или вероятности из конечных узлов могут использоваться для выбора только наиболее надежных псевдометок, отфильтровывая назначения с низкой уверенностью.
Дерево переобучается с нуля, используя как исходные размеченные примеры, так и вновь псевдоразмеченные неразмеченные наблюдения. Псевдометки с высокой уверенностью способствуют принятию решений о разделении наряду с истинными метками, эффективно увеличивая эффективный обучающий набор.
Модифицированные критерии разделения — такие как энтропия или индекс Джини, вычисленные по размеченным и неразмеченным наблюдениям, или бикритериальные цели, которые балансируют контролируемую чистоту с согласованностью кластеров без контроля — направляют разделение узлов, чтобы учитывать базовое распределение данных, раскрытое неразмеченными точками.
Итерации продолжаются до тех пор, пока предварительные метки не стабилизируются в течение последовательных раундов или не будет достигнут максимальный предел итераций. Затем к конечному дереву применяются стандартные стратегии пост-обрезки (обрезка по стоимости-сложности, минимальный размер листа) для контроля переобучения на псевдоразмеченных данных.
Частые ошибки
- Использование всех псевдометок независимо от их уверенности, что позволяет низкокачественным назначениям доминировать в последующих итерациях.
- Неспособность проверить, что неразмеченные данные взяты из того же распределения, что и размеченный набор, перед обучением.
- Рассмотрение статистики конечных узлов финального дерева как чисто контролируемых при сообщении метрик производительности — требуется оценка вне выборки (out-of-bag) или на отложенном размеченном наборе.
- Пропуск обрезки после добавления псевдометок, что приводит к сильному переобучению на шумных предварительных метках.
- Прямое сравнение с полностью контролируемым деревом, обученным на том же размеченном подмножестве, без учета использованных дополнительных неразмеченных данных.
Часто задаваемые вопросы
Чем полуавтоматическое дерево решений отличается от обычного классификатора самообучения?
Основной принцип — использование предсказаний на неразмеченных данных для дополнения обучения — остается тем же. Что отличает подходы, специфичные для деревьев, так это возможность модифицировать сам критерий разделения для включения информации о распределении неразмеченных данных, а не просто итеративно расширять размеченный набор.
Сколько размеченных примеров мне нужно для начала?
Универсального минимума нет, но начальное контролируемое дерево должно быть достаточно надежным, чтобы давать полезные псевдометки. На практике часто рекомендуется не менее 20–50 размеченных примеров на класс; при меньшем количестве риск распространения ошибок высок, и лучше могут работать альтернативные подходы, такие как распространение меток.
Должен ли я использовать все неразмеченные данные или выбрать подмножество?
Выбор только псевдометок с высокой уверенностью — например, тех, где вероятность листа превышает порог, такой как 0.85 — как правило, дает лучшие результаты, чем использование всех неразмеченных точек, особенно когда начальное дерево несовершенно.
Заменяет ли это стандартную перекрестную проверку?
Нет. Поскольку псевдометки получены из самой модели, метрики внутри выборки оптимистичны. Оценка должна проводиться с использованием отложенного размеченного тестового набора или k-кратной перекрестной проверки, строго примененной к размеченному разделу.
Могу ли я объединить это с ансамблевыми методами?
Да. Полуавтоматические случайные леса и подходы совместного обучения (co-forest) расширяют эту идею на ансамбли, которые могут снизить дисперсию ошибок псевдоразметки и обычно превосходят одно полуавтоматическое дерево.
Похожие методы
Источники
Levin, E. & Shapiro, E. (2000). Learning Decision Trees from Semi-labeled Examples. Proceedings of the ICML Workshop on Attribute-Value and Relational Learning.
Открыть ссылку на публикациюСкопировано.Zhu, X. & Goldberg, A. B. (2009). Introduction to Semi-Supervised Learning. Morgan & Claypool Publishers.
ISBN: 978-1-598-29548-9Скопировано.