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

Дерево решений с активным обучением

Автор метода
Settles, B. (active learning framework); Breiman et al. (decision tree base)
Год
1984–2010
Тип
Active learning with decision tree base learner
Семейство
Machine learning

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

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

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

Активное обучение с использованием дерева решений сочетает интерпретируемую структуру дерева в стиле CART с стратегией запросов, которая выбирает наиболее информативные неразмеченные экземпляры для аннотирования человеком.

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

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

Разметка каждого обучающего примера является дорогостоящей. Активное обучение решает эту проблему, позволяя модели задавать вопрос: «Какой неразмеченный пример, если бы он был размечен, научил бы меня больше всего?» Дерево решений используется в качестве классификатора, который оценивает неопределенность на каждом шаге запроса. После добавления каждой новой метки дерево переобучается, и цикл запросов повторяется. Результатом является модель, которая достигает конкурентоспособной точности при гораздо меньшем количестве размеченных примеров, чем полностью контролируемое дерево, обученное с нуля, что делает ее практичной для сценариев, где аннотирование дорого или занимает много времени.

История

Деревья решений как классификаторы восходят к CART Бреймана и др. (1984) и C4.5 Куинлана (1993). Активное обучение как систематическая структура было всесторонне рассмотрено Берром Сеттлсом (2010), который документировал стратегии выборки неопределенности, запроса по комитету и ожидаемого изменения модели. Деревья решений являются стандартным базовым учеником в бенчмарках активного обучения с конца 1990-х годов, появляясь в ранних работах по выборке из пула Коэна, Атласа и Ладнера (1994) и последующих эмпирических сравнениях различных типов учеников.

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

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

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

  • Стратегия запросов и переобучение дерева вместе могут быть вычислительно затратными, когда пул неразмеченных экземпляров очень велик.
  • Деревья решений являются учениками с высокой дисперсией; при малом количестве начальных меток раннее дерево может быть ненадежным, что приводит к плохим ранним запросам.
  • Потолок производительности ниже, чем у ансамблевых методов, таких как случайный лес или градиентный бустинг, при том же бюджете на разметку.
  • Предполагает, что метки оракула точны; зашумленные или непоследовательные метки могут деградировать активный цикл быстрее, чем при пассивном обучении.

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

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

  • Резко сокращает количество меток, необходимых для достижения целевой точности, по сравнению со случайной выборкой.
  • Базовая модель дерева решений интерпретируема для человека, что делает ее подходящей для регулируемых областей или областей, требующих объяснений.
  • Хорошо работает на табличных наборах данных умеренного размера со смешанными типами признаков без необходимости масштабирования признаков.
  • Стратегии запросов на основе неопределенности просты в реализации и объяснении заинтересованным сторонам.
  • Точность вне выборки (out-of-bag) или точность на валидационном наборе после каждой итерации обеспечивает прозрачную кривую обучения.

Применение

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

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

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

1

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

2

На текущем размеченном наборе обучается классификатор на основе дерева решений (обычно CART или C4.5). Дерево изучает правила разбиения, которые минимизируют примесь (джини или энтропию) в каждом узле, создавая классификатор, который также может выдавать оценки вероятности класса для любого неразмеченного экземпляра.

3

Критерий информативности — чаще всего выборка неопределенности на основе энтропии предсказания H или разницы между двумя наиболее вероятными классами — оценивает каждый неразмеченный экземпляр. Экземпляр с наивысшим показателем неопределенности выбирается в качестве запроса: x* = argmax H(y-hat | x).

Формула
x^* = \arg\max_{x \in U} H(\hat{y} \mid x)
4

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

5

Дерево решений переобучается с нуля на расширенном размеченном наборе, и цикл запроса-оценки-метки повторяется. Критерии остановки включают достижение бюджета на разметку, минимальный порог точности на отложенном наборе для валидации или максимальное количество итераций. Окончательная оценка должна проводиться на полностью независимом тестовом наборе.

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

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

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

Почему следует использовать дерево решений вместо более мощной модели в качестве базового ученика?

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

Сколько начальных размеченных примеров мне нужно для старта?

Общее практическое правило — по крайней мере один или два примера на класс, чтобы дерево могло делать осмысленные разбиения. На практике типичным является старт с 5–20 размеченными экземплярами; меньше этого есть риск, что начальное дерево будет слишком дегенеративным, чтобы выдавать информативные оценки неопределенности.

Имеет ли порядок запросов значение?

Да. Последовательность запросов зависит от пути: ранние запросы формируют то, что изучает дерево, и, следовательно, какие последующие примеры выглядят наиболее неопределенными. Различные случайные начальные значения или начальные размеченные наборы могут привести к существенно разным кривым обучения, поэтому при сравнении стратегий воспроизводите эксперименты с разными начальными значениями.

Когда следует прекратить запросы?

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

Можно ли использовать этот подход для многоклассовых задач?

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

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

Источники

  1. Settles, B. (2010). Active Learning Literature Survey. Computer Sciences Technical Report 1648, University of Wisconsin-Madison.

    Открыть ссылку на публикацию
    Скопировано.
  2. Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and Regression Trees. Wadsworth & Brooks.

    ISBN: 978-0-412-04841-8
    Скопировано.