Прошу прощения у деревьев, но сегодня я снова планирую обзываться.
Дело в том, что деревья - не только жадные, но некоторые из них еще, как говорится, с памятью как у рыбы. Забывчивые.
Такие забывчивые деревья (oblivious decision trees) не помнят, что на предыдущем сплите было применено правило, которое разделило объекты на уникальные подмножества в каждой из ветвей. И просто фигачат одно и то же правило для всего уровня, а потом следующее правило для всего следующего уровня.
Такие забывчивые деревья, а точнее их частный случай - решающие таблицы, использует алгоритм Catboost (тот самый, который и кот, и categorical, и out of the box, и open-source). И там забывчивые деревья настолько обленились, что не только правило применяют одно для всего уровня, но и общий порог разделения. При таком подходе становится возможным переставлять уровни - порядок следования правил становится не важен.
По итогу решающая таблица выходит размерностью в N столбцов по горизонтали (количество уровней дерева) и 2^N строк по вертикали (решающее правило принимает значение 0 или 1). Каждой строке сопоставляется константное значение целевого признака.
Несколько решающих таблиц можно объединить в одну. А вот в обратную сторону работает не всегда: не все сложные таблицы могут быть разложены на простые.
Зачем Catboost-у забывчивые деревья? Все просто. Они быстрее, а значит в высоконагруженных системах быстрее инференс, и они устойчивее по качеству модели при изменении параметров, а значит алгоритм хорош «из коробки».
Но если очень хочется, забывчивые деревья можно переключить на обычные через параметр grow_policy.
Полезности: Общий признак Общий признак 2 Общий порог Параметр типа дерева
