Lecture 4.

Trees, forests, boostings

Закономерности

Деревья решений.

Закономерность φ называется интерпретируемой, если

1. Она сформулирована естественным языком
2. Зависит от небольшого числа параметров (1-7)

​

Пример (из русского языка): Если слово является наречием и оканчивается на шипящую букву (“ж”, “ч” или “ш”), в конце ставится “ь”.

Информативные закономерности

Деревья решений.

Закономерность φ называется информативной для класса c если:,

p - истинно положительные

n - ложно положительные

Правила

Деревья решений.

Что такое правило?

​

Какие правила можно выделить на этих данных?

Дерево по правилу

Деревья решений.

Правила

Деревья решений.

Где брать правила?

1. Создавать самостоятельно
2. Заимствовать у экспертов
3. Обучать

​

Как обучать правила?

1. Алгоритмы оптимизации
2. Эвристические методы
3. Алгоритмы машинного обучения

Дерево решений

Деревья решений.

Алгоритм классификации и регрессии.

​

Вершины содержат разделяюшие правила (вопросы).

Рёбра - возможные ответы на вопрос в родительской вершине.

Листья содержат решения (класс объекта для классификации, число или функцию для регрессии).

Дерево решений. Пример

Деревья решений.

Дерево решений. Тот же пример

Деревья решений.

Обучение дерева.

Деревья решений.

У нас есть множество разделяющих правил B и критерий ветвления Φ.

1. Выборка S в корне
2. На каждом шаге S обрабатывается рекурсивно

2.1. Если S содержит только объекты класса c, то создаем лист и останавливаемся.

2.2. Иначе выбираем правило b и разделяем выборку на подмножества Si

2.3. Если выполняется критерий остановки, то возвращаем наиболее популярный класс, иначе создаём новые вершины

• Подрезаем исходное дерево…

Обучение дерева.

Деревья решений.

Остаётся много вопросов:

1. Как выбирать разделяющие правила
2. Как выбирать критерий ветвления
3. Как выбирать критерий остановки
4. Как подрезать дерево

Обучение дерева. Выбор правила

Деревья решений.

Чаще всего мы используем вот такие правила:

Обучение дерева. Выбор правила

Деревья решений.

Как выбрать, какое правило нужно?

• Рассмотреть каждое правило и выбрать самое информативное
• Объединение диапазонов значений
• Пропуск маленьких диапазонов

​

Таким образом можно синтезировать правило для каждого признака

Обучение дерева. Выбор критерия ветвления

Деревья решений.

Обучение дерева. Выбор критерия ветвления

Деревья решений.

Максимизируем «выигрыш» критерия (Gini ↓, энтропия ↓, IG ↑) при разделении узла на дочерние.

​

Для дискретных признаков можем перебирать критерии для каждого признака.

Обучение дерева. Выбор критерия ветвления

Деревья решений.

Для непрерывных признаков есть несколько стратегий

​

1. Полный перебор (почти). Отсортировать значения признака в узле, рассмотреть пороги между уникальными значениями.
2. Гистограммный/квантилированный поиск (быстрый). Дискретизировать признак на B бинов (равные интервалы или по квантилям). Считаем счётчики классов по бинам, затем ищем лучший бин-границу за O(B). Используется в XGBoost/LightGBM/CatBoost.

​

Обучение дерева.

Деревья решений.

Рассчитаем энтропию для этого датасета:

Обучение дерева.

Деревья решений.

Sunny:

Overcast:

Rainy

Обучение дерева.

Деревья решений.

Information Gain:

Обучение дерева. Критерий остановки

Деревья решений.

Какой критерий выбрать?

Обучение дерева. Критерий остановки

Деревья решений.

Популярные критерии остановки:

1. Один из классов пустой после разбиения - слишком жёсткий вариант «ни одного примера класса» может мешать качественным сплитам при сильном дисбалансе.

​

• Φ(S) меньше некоторого порога - останавливаемся, если прирост критерий_родителя − взвешенная_сумма(критерий_детей) слишком мал. Порог выбирается в зависимости от шумности и количества данных.

Обучение дерева. Критерий остановки

Деревья решений.

Популярные критерии остановки:

3. |S| меньше некоторого порога - не сплитим, если в узле мало примеров (нет статистики).

​

4. Высота дерева выше некоторого порога - единый max_depth для всех ветвей может «резать» важные глубокие ветви и «щадить» пустые - смотрите на max_leaves как более гибкий контроль.

Обучение дерева. Критерий остановки

Деревья решений.

Остановка через тесты - другой тип остановки.

​

Останавливаем рост дерева, когда нет статистически значимой связи между каким-либо признаком и классом в конкретном узле.

​

Какие стат. тесты можем использовать? :)

Обучение дерева. Оптимизация для регрессии

Деревья решений.

Регрессионные деревья используются для решения задачи регрессии.

​

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

Обучение дерева. Оптимизация для регрессии

Деревья решений.

Что плохого можно увидеть на картинке?

​

​

​

​

Очень глубокие деревья переобучаются…

Обучение дерева. Слабые классификаторы

Деревья решений.

Слабая обучаемость означает, что за полиномиальное время можно найти алгоритм, производительность которого будет больше 0,5.

​

Сильная обучаемость означает, что за полиномиальное время можно найти алгоритм, производительность которого будет сколь угодно высокой.

Обучение дерева. Теорема Шапиро

Деревья решений.

Теорема (Шапиро, 1990)

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

Постановка задачи

Леса и бустинги

Берём семейство базовых классификаторов и делаем композицию из них.

Случайный лес

Леса и бустинги

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

Голосование

Леса и бустинги

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

​

Два типа голосования:

• Мажоритарное (подсчёт голосов)
• Мягкое (подсчёт вероятностей)

​

Также можно добавлять веса для участников голосования.

Признаки в слабых классификаторах

Леса и бустинги

Нельзя подавать всем деревьям все признаки!

Признаки в слабых классификаторах

Леса и бустинги

Самым простым примером корректирующей функции является голосование.

​

Два типа голосования:

• Мажоритарное (подсчёт голосов)
• Мягкое (подсчёт вероятностей)

​

Также можно добавлять веса для участников голосования.

Бустинги

Леса и бустинги

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

​

Отличие состоит в том, что в бэггинге и случайном лесе базовые алгоритмы учатся независимо и параллельно, а в бустинге - последовательно.

Бустинги

Леса и бустинги

LightGBM

Леса и бустинги

LightGBM строит деревья по принципу: «На каждом шаге делим вершину с наилучшим скором», а основным критерием остановки выступает максимально допустимое количество вершин в дереве.

XGBoost

Леса и бустинги

XGBoost строит деревья по принципу: «Строим дерево последовательно по уровням до достижения максимальной глубины».

CatBoost

Леса и бустинги

CatBoost строит деревья по принципу: «Все вершины одного уровня имеют одинаковый предикат».

Стекинг

Леса и бустинги

Стекинг (stacking) - алгоритм ансамблирования, основные отличия которого от предыдущих состоят в следующем:

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

Feature importance

Леса и бустинги

Сравнение

Леса и бустинги

SHAP values

Леса и бустинги

SHAP values

Леса и бустинги

Bias-variance exchange

Леса и бустинги

Ко(т)нец презентации

Bayes……

• всё, что в презентации было…

Теоретический минимум