Классификация с многими метками

Привет, Хаброжители! Мы решили привести опубликовать отрывок из книги Андрея Буркова «Машинное обучение без лишних слов», посвященный классификации.

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

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

Нейронные сети можно естественным образом обучить классификации с многими метками, используя в качестве функции стоимости бинарную перекрестную энтропию (binary cross-entropy). Выходной слой нейронной сети в этом случае имеет по одному узлу на метку. Каждый узел в выходном слое имеет сигмоидную функцию активации. Соответственно, каждая метка l является бинарной где l = 1, ..., L и i = 1, ..., N. Бинарная перекрестная энтропия определяет вероятность что образец xi имеет метку l, определяется как

Критерий минимизации — простое среднее значение всех членов бинарной перекрестной энтропии во всех обучающих образцах и всех их метках.

В случаях, когда число возможных значений меток невелико, можно попробовать преобразовать задачу классификации с многими метками в задачу многоклассовой классификации. Представьте следующую задачу. Требуется присвоить изображениям метки двух типов. Метки первого типа могут иметь два возможных значения: {фото, живопись}; метки второго типа могут иметь три возможных значения: {портрет, пейзаж, другое}. Для каждой комбинации двух исходных классов можно создать новый фиктивный класс, например:

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

Основное преимущество этого последнего подхода в том, что метки остаются коррелированными, в отличие от методов, описанных выше, которые предсказывают каждую метку независимо друг от друга. Во многих задачах корреляция между метками может быть существенным фактором. Например, представьте, что нужно классифицировать электронную почту как спам и не_спам, и одновременно как обычная и важная. Вы наверняка пожелали бы исключить такие прогнозы, как [спам, важная].

7.5. Обучение ансамбля

Фундаментальные алгоритмы, которые мы рассмотрели в главе 3, имеют свои ограничения. Из-за простоты иногда они не могут создать модель, достаточно эффективную для вашей задачи. В таких случаях можно попробовать использовать глубокие нейронные сети. Однако на практике глубокие нейронные сети требуют значительного объема размеченных данных, которых у вас может не быть. Другой способ повысить эффективность простых алгоритмов обучения — использовать обучение ансамбля.

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

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

Чтобы получить окончательный прогноз для входа x, прогнозы всех слабых моделей объединяются с использованием некоторого метода взвешенного голосования. Конкретная форма взвешивания голосов зависит от алгоритма, но сама суть не зависит от него: если по совокупности слабые модели предсказывают, что электронное письмо является спамом, мы присваиваем образцу x метку спам.

Двумя основными методами обучения ансамблей являются бустинг (boosting — форсирование) и бэггинг (bagging — агрегирование). Переводы терминов boosting и bagging неточные и не прижившиеся.

7.5.1. Бустинг и бэггинг

Метод бустинга заключается в использовании исходных обучающих данных и итеративного создания нескольких моделей с применением слабого алгоритма.

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

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

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

«Классический» алгоритм бэггинга работает следующим образом. Из имеющегося обучающего набора создается B случайных выборок (для каждого b = 1, ..., B) и на основе каждой выборки строится модель дерева решений. Чтобы получить выборку для некоторого b, производится выборка с заменой. То есть сначала создается пустая выборка, а затем из обучающего набора выбирается случайный образец, и его точная копия помещается в , при этом сам образец остается в исходном обучающем наборе. Выбор данных продолжается, пока не выполнится условие

В результате обучения получается B деревьев решений. Прогноз для нового образца x, в случае регрессии, определяется как среднее из B прогнозов

или большинством голосов в случае классификации.

Случайный лес имеет только одно отличие от классического бэггинга. Он использует модифицированный алгоритм обучения дерева, который при каждом расщеплении в процессе обучения проверяет случайное подмножество признаков. Это делается с целью устранить корреляцию между деревьями: если один или несколько признаков имеют большую прогнозирующую способность, многие деревья будут выбирать их для расщепления данных. Это приведет к появлению в «лесу» большого числа коррелированных деревьев. Корреляция по признакам с большой прогнозирующей способностью препятствует повышению точности предсказания. Высокая эффективность ансамбля моделей объясняется тем, что хорошие модели, вероятнее всего, согласятся с одним и тем же прогнозом, а плохие — не согласятся и дадут разные прогнозы. Корреляция сделает плохие модели более склонными к согласию, что исказит картину голосования или повлияет на среднее значение.

Наиболее важными гиперпараметрами для настройки являются количество деревьев B и размер случайного подмножества признаков, которые необходимо учитывать при каждом расщеплении.
Случайный лес — один из наиболее широко используемых алгоритмов обучения ансамблей. Чем обусловлена его эффективность? Причина в том, что, используя несколько выборок из исходного набора данных, мы уменьшаем дисперсию конечной модели. Помните, что низкая дисперсия означает слабую предрасположенность к переобучению. Переобучение происходит, когда модель пытается объяснить небольшие вариации в наборе данных, потому что набор данных является лишь небольшой выборкой из всех возможных примеров явления, которое мы пытаемся смоделировать. В случае неудачного подхода к формированию обучающего набора в него могут попасть некоторые нежелательные (но неизбежные) артефакты: шум, аномальные и чрезмерно или недостаточно представительные данные. Создавая несколько случайных выборок с заменой обучающего набора, мы уменьшаем влияние этих артефактов.

7.5.3. Градиентный бустинг

Другой эффективный алгоритм обучения ансамблей, основанный на идее бустинга, — градиентный бустинг. Сначала рассмотрим применение градиентного бустинга в регрессии. Построение эффективной регрессионной модели мы начнем с константной модели (как мы это делали в ID3):

Затем изменим метки во всех образцах i = 1, ..., N в обучающем наборе:

где называется остатком и является новой меткой образца

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

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

Давайте интуитивно разберемся в том, что тут происходит. Вычисляя остатки, мы определяем, насколько хорошо (или плохо) предсказывается цель каждого обучающего образца текущей моделью f. Затем мы обучим другое дерево для исправления ошибок текущей модели (именно поэтому мы используем остатки вместо фактических меток) и добавим новое дерево в существующую модель с некоторым весом α. В результате каждое новое дерево, добавленное в модель, частично исправляет ошибки, допущенные предыдущими деревьями. Процесс продолжается, пока не будет объединено максимальное количество M (еще один гиперпараметр) деревьев.

Теперь попробуем ответить на вопрос, почему этот алгоритм называется градиентным бустингом. В градиентном бустинге мы не вычисляем градиент, в отличие от того, что мы делали в главе 4, решая задачу линейной регрессии. Чтобы увидеть сходство между градиентным бустингом и градиентным спуском, вспомните, для чего мы вычисляли градиент в линейной регрессии: чтобы узнать направление изменения значений параметров для минимизации функции стоимости MSE. Градиент показывает направление, но не показывает, как далеко идти в этом направлении, поэтому в каждой итерации мы делали небольшой шаг, а затем вновь определяли направление. То же происходит в градиентном бустинге, только вместо непосредственного вычисления градиента мы используем его оценку в форме остатков: они показывают, как следует скорректировать модель, чтобы уменьшить ошибку (остаток).

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

Можно показать, что обучение по остаткам оптимизирует общую модель f для критерия среднеквадратичной ошибки. Здесь можно заметить отличие от бэггинга: бустинг уменьшает смещение (или недообученность) вместо дисперсии. Как результат, бустинг подвержен переобучению. Однако, настраивая глубину и количество деревьев, можно в значительной степени избежать переобучения.

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

где дерево регрессии.

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

Алгоритм начинает работу с начальной константной модели где (Можно показать, что такая инициализация оптимальна для сигмоидной функции.) Затем в каждой итерации m в модель добавляется новое дерево fm. Чтобы найти наилучшее дерево Чтобы найти наилучшее дерево сначала вычисляется частная производная текущей модели для каждого i = 1, ..., N:

где f — модель ансамблевого классификатора, построенная на предыдущей итерации m — 1. Чтобы вычислить , нужно найти производные от по f для всех i. Обратите внимание, что Производная по f правого члена в предыдущем уравнении равна

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

В конце итерации m мы обновляем модель ансамбля добавляя новое дерево

Итерации продолжаются, пока не выполнится условие m = M, после чего обучение прекращается и в результате получается модель ансамбля f.

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