Деревья решений и ансамбли

Одно дерево и цена его жадности

Дерево играет в «двадцать вопросов». На каждом шаге оно перебирает признаки и пороги и выбирает тот, который сильнее всего делит данные на однородные части: в классификации однородность меряют через Gini или энтропию, в регрессии - через разброс значений. Выбрало - и растит дальше, назад не оглядываясь.

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

// И ещё одно врождённое свойство, которое любят спрашивать: дерево не умеет экстраполировать. В листе лежит среднее по обучающим примерам, поэтому предсказать значение больше максимума в трейне оно не может физически. Растёт площадь квартиры - предсказанная цена упирается в потолок и стоит.

Gini и энтропия

две меры того, насколько в узле всё вперемешку; сплит выбирают по их падению

Random Forest: толпа, которая гасит шум

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

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

Деревья не зависят друг от друга, поэтому обучение легко раскидать по ядрам. Приятный бонус: объекты, не попавшие в выборку конкретного дерева, можно использовать как проверочные - получается OOB-оценка (out-of-bag), почти бесплатная валидация.

// Стоит понимать, что именно лечит лес. Он гасит чувствительность к выборке, но не лечит систематическую ошибку. Если одиночное дерево слишком примитивно для задачи, тысяча таких же примитивных ничего не спасёт.

бэггинг

обучить много моделей на разных случайных выборках и усреднить их ответы

Бустинг: деревья чинят друг за другом

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

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

// Три главные библиотеки делают одно и то же немного по-разному. LightGBM растит дерево в сторону самого выгодного листа - выходит глубже и переобучается легче. XGBoost растит по уровням. CatBoost умеет категориальные признаки из коробки, кодируя их так, чтобы объект не подглядывал в собственный ответ.

ранняя остановка

перестать добавлять деревья, как только метрика на валидации перестала улучшаться

learning rate

насколько сильно каждое новое дерево вмешивается в общий ответ

Стекинг: модель, которая решает, кому верить

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

// Тонкость, которую и проверяют: прогнозы базовых моделей для обучения мета-модели надо брать out-of-fold, то есть каждый объект должен быть предсказан моделью, которая его не видела. Иначе базовая модель «помнит» ответ на этот объект, мета решит, что она гениальна, и на проде всё развалится. Блендинг - тот же приём, только прогнозы берут на отдельном отложенном куске.

out-of-fold

прогноз для объекта, полученный моделью, которая при обучении его не видела

Как отвечать: «Чем Random Forest отличается от градиентного бустинга?»

Лес строит глубокие деревья независимо, каждое на своей случайной выборке, и усредняет - это бэггинг, он гасит чувствительность к данным. Бустинг строит мелкие деревья по очереди, и каждое доучивает ошибки предыдущих - он бьёт по систематической ошибке. На практике разница такая: лес почти не требует тюнинга, отлично параллелится и устойчив на шумных маленьких данных, а бустинг на табличных задачах обычно точнее, но просит подобрать скорость обучения, поставить раннюю остановку и иметь честную валидацию. Я бы начал с бустинга на дефолтах с ранней остановкой, а лес держал рядом как быстрый устойчивый бейзлайн.

Названы механизм, следствие для практики и порядок действий. Видно человека, который обе модели запускал, а не читал про них.

На чём валят

• −«Бустинг всегда лучше леса»: на шумных данных и малых выборках лес устойчивее, да ещё и учится параллельно.
• −Верить встроенной важности признаков по gain: она завышает признаки с большим числом уникальных значений; надёжнее permutation importance.
• −Ждать от дерева или леса экстраполяции в регрессии: выше максимума обучающих данных они не предскажут ничего.
• −Поднять скорость обучения ради скорости и не увеличить обратно число деревьев: качество съезжает тихо и незаметно.