Ансамбли моделей для распознавания рукописных цифр

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

В данном посте будет рассказано об алгоритмах ансамблирования. Ансамблевые методы применяются, чтобы объединить в себе несколько моделей машинного обучения. Такая композиция может привести к увеличению качества решаемой задачи за счет использования сразу нескольких моделей вместо одной. Логику алгоритма можно объяснить поговоркой – “одна голова хорошо, а две лучше”. Далее будет объяснено с математической точки зрения, почему же это так.

Например, есть некоторый метод обучения - линейная регрессия. У этого алгоритма существует ошибка. Ошибку метода обучения можно разложить на 3 компоненты: шум, смещение и разброс. Шум показывает, насколько ошибается построенная модель, и он не зависит от модели. Он характеризует насколько репрезентативна была выборка данных, на которой мы обучали модель. Смещение (bias) показывает, насколько отличается средняя модель по всем возможным обучающим выборкам от истинной зависимости. Разброс (variance) - как сильно меняется модель в зависимости от выборки, на которой обучается модель. Подытожив, шум – это показатель данных, смещение характеризует приближенность к реальной зависимости модели, разброс говорит о чувствительности к обучающей выборке. Такое разложение называется bias-variance decomposition.

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

Существует несколько методов ансамблирования – бэггинг (bagging), бустинг (boosting), стэкинг (stacking) и блэндинг (blending). Бэггинг осуществляется следующим образом: для каждого алгоритма формируется своя выборка методом бутстрапа (bootstrap) – из всей обучающей выборки берется некоторая доля наблюдений с возвращением. То есть в подвыборку могут попасть некоторые объекты несколько раз, а какие-то вовсе не попасть. На каждой подвыборке тренируется модель, а далее результаты этих моделей усредняются. В результате такого подхода по математическим выкладкам получается, что смещение такой композиции моделей равно смещению одной базовой модели из этой композиции. Отсюда выходит вывод, что базовые модели при таком подходе нужно строить посложнее, например, глубокие деревья. Поэтому в бэггинге ошибку обучения можно уменьшить за счет снижения разброса.

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

Чтобы реализовать случайный лес необходимо: построить n базовых деревьев, причем глубоких, чтобы смещение композиции было небольшим; при выборе лучшего предиката ограничиться m случайными признаками; если осуществлялась задача регрессии, то усреднить результаты деревьев, если задача классификации, то результат принимается по голосованию большинства деревьев для объекта. При этом, для случайного леса можно взять деревьев побольше, так как это будет снижать разброс, не приводя к переобучению композиции. Однако,более целесообразно построить график ошибки от количества деревьев, и ограничиться тем количеством, где ошибка перестанет значительно снижаться. Обучение случайного леса также можно воспроизвести распределенно по процессорам.

Продемонстрирую работу Random Forest на примере датасета с платформы kaggle – MNIST (Digit Recognizer | Kaggle). В данной задаче необходимо классифицировать изображения с рукописными цифрами. Каждое изображение в данном датасете состоит из 28 пикселей в ширину и 28 пикселей в длину, что составляет в общем 784 пикселя. У каждого пикселя есть свое значение, характеризующее его яркость или темноту. Эти значения находятся в диапазоне от 0 до 255.

Качество случайного леса показало достаточно высокие результаты. Далее будет рассмотрен бустинг и его модификации.

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

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

На практике часто используется градиентный бустинг. Опишем его идею более детально. Если в качестве базовых моделей используются решающие деревья, то такая композиция будет называться градиентным бустингом над решающими деревьями (GBDT). Опишу общую схему GBDT для задачи регрессии с функцией потерь MSE. Итак, например, была построена одна базовая модель, и известно, на каких объектах она ошибается. Таким образом, можно узнать сдвиг – насколько созданная композиция (состоящая пока что из одной модели) отклоняется от истинного ответа на каждом объекте.

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

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

Покажу также общий случай обучения композиции для дифференцируемой функции потерь. Также представлю, что уже построена первая (N-1) базовая модель, и нужно обучить N-ую модель, тогда:

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

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

Существует несколько различных вариаций GBDT – это XGBoost, LightGBM и CatBoost. Они отличаются друг от друга по нескольким критериям – симметричность деревьев, метод разбиения объектов, обработка категориальных признаков, интерпретация пропущенных значений, обработка текстовых признаков. В CatBoost деревья симметричные на каждом уровне, в двух других алгоритмах – ассиметричные. Таким образом, в LightGBM алгоритме деревья растут по листьям, горизонтально (leaf-wise growth), а в XGBoost деревья растут по уровням, вертикально (level-wise growth). В CatBoost используется жадный алгоритм разбиения наблюдений, в LightGBM используется Gradient-based One-Side Sampling, основанный на значениях градиента для наблюдений, а в XGBoost разбиение работает по предварительной сортировке значений признаков. На вход CatBoost могут подаваться категориальные признаки, LightGBM может принимать их на вход только в числовом формате, однако можно в порядковом виде. А XGBoost не может работать с порядковыми данными, категориальные признаки должны подаваться только после кодирования.

Рассмотрю XGBoost, LightGBM и CatBoost на примере ранее описанного датасета с платформы kaggle – MNIST. Реализация на Python:

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