Глубокая связь между бустингом и LASSO

Понимание мощного алгоритма через радикальное изменение точки зрения

Повышение градиента используется повсеместно и повсеместно недооценивается.

Обсуждая его эффективность, люди обычно по умолчанию придерживаются двух точек зрения:

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

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

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

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

Резюме: функциональный градиентный спуск

Распространенной аналогией повышения является градиентный спуск в функциональном пространстве. Вместо итеративного обновления n-мерных векторов параметров мы теперь итеративно обновляем функции параметров (которые принадлежат потенциально бесконечномерному функциональному пространству).

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

Здесь причудливая буква «L» — это наша традиционная функция потерь при моделировании, которая принимает в качестве аргументов как истинные метки, так и выходные данные, полученные нашей моделью (где наша модель представлена функцией «f»).

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

Я избавлю от вывода фактического градиента; для получения более подробной информации см. Эти превосходные конспекты лекций Алекса Грабба и Саманты Хорват. Просто знайте, что результирующий градиент представляет собой функцию пика, которая выдает остатки (истинные остатки, если функция потерь L представляет собой квадрат потерь, в противном случае — псевдоостатки) текущих прогнозов при оценке в тренировочных точках x{ i} и выдает ноль при оценке в другом месте. Вот визуализация функции градиента и полученного обновления:

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

Элегантные вещи. Однако остается один ключевой вопрос:

Почему повышение эффективности работает так хорошо, если слабые ученики плохо справляются (по определению) с подбором градиента?

На мой взгляд, именно здесь рушится высокоуровневая аналогия с функциональным градиентным спуском (более подробная версия, вероятно, работает лучше). Есть другие способы объяснить силу бустинга, но формулировка LASSO одновременно интуитивно понятен и чрезвычайно полезен для сравнения бустинга с другими методами, такими как SVM.

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

Векторное пространство бустинг-деревьев

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

На самом деле понятия «векторы» и «векторные пространства» гораздо более абстрактны.

Единственное требование для того, чтобы пространство было векторным пространством, состоит в том, что добавление и масштабирование векторов дает другой вектор в этом пространстве (вам также необходимо существование «нулевого» вектора, который ничего не делает при добавлении к другому вектору).

Это означает, что многие, много множеств являются векторными пространствами. Множество всех многочленов является векторным пространством (проверьте это сами с помощью правил!) Множество всех матриц 2x2 является векторным пространством.

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

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

И точно так же, как вы можете воссоздать все евклидово пространство с помощью линейных комбинаций конечного набора векторов (векторов осей), вы можете воссоздать все увеличенное древовидное пространство с помощью линейных комбинаций отдельных деревьев! Если мы разрешаем разбиение дерева только на наблюдаемые точки данных или между ними, то оказывается, что любое отдельное дерево с глубиной D может быть записано как линейная комбинация конечного числа деревьев «строительных блоков» с глубиной D.

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

И если мы можем записать любое дерево глубины D в виде линейной комбинации деревьев «строительных блоков», то мы можем также представить любое дерево с бустингом глубины D в виде линейной комбинации следующим образом:

Формула слева выглядит знакомой? Если это похоже на линейную регрессию, то вы на верном пути! Теоретически мы можем свести нашу проблему поиска хорошего аддитивного ансамбля деревьев к линейной регрессии по набору деревьев, которые генерируют пространство всех возможных усиленных деревьев. Но мы столкнемся с двумя серьезными проблемами, если наивно попробуйте построить регрессионную модель:

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

Что касается № 2, «иметь во много раз больше функций, чем точек данных» — это именно проблема, которую может решить LASSO!

Повышение аппроксимации Настройка LASSO

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

Сначала мы оцениваем каждую функцию по всем точкам данных, чтобы создать столбцы в нашей матрице признаков X. Теперь, когда у нас есть наши признаки, мы решаем следующую задачу оптимизации регрессии LASSO:

Это определение (минимизировать сумму проигрышей со штрафом L1) наверняка знакомо многим. Менее знакомой, но все же часто используемой является следующая формулировка LASSO с ограничением L1:

Для каждого значения λ на рис. 5 существует уникальное значение T на рис. 6, которое восстанавливает одно и то же решение, и наоборот (где увеличение T соответствует уменьшению λ до тех пор, пока λ = 0, после чего любое большее значение T восстанавливает одно и то же решение: нерегулярное решение.)

Давайте быстро покажем, почему каждое λ отображается в уникальное T (другое направление немного сложнее, и аргументы, использующие двойственность Лагранжа, можно найти в Интернете). Я оставлю это доказательство самодостаточным в следующем пронумерованном списке, чтобы его можно было пропустить. легко:

При заданном значении λ решение задачи оптимизации на рис. 5 соответствует вектору β, имеющему некоторую конечную L1-норму N, меньшую, чем норма, соответствующая нерегуляризованному решению (λ = 0).
Теперь рассмотрим задачу оптимизации с ограничениями на рис. 6 с T = N. Решение на рис. 6 с T = N не может иметь норму L1 меньше N, так как это будет локальный оптимум в пределах набора ограничений (противореча тому факту, что что для нашей выпуклой цели существует только один локальный оптимум.) Следовательно, решение на рис. 6 с T = N имеет норму L1, равную точно N.
Поскольку решение на рис. 6 с T = N минимизирует цель рис. 6 среди всех решений с нормой L1, равной N, оно также должно минимизировать цель на рис. 5 с данным λ среди всех решений с нормой L1 N.
Следовательно, решение рис. 6 при T = N равно решению рис. 5 при заданном λ, так как последнее решение также имеет L1-норму N.
Любое значение T ‹ N или T › N на рис. 6 не может восстановить одно и то же решение из-за наличия нормы, отличной от N (см. аргумент в № 2). Следовательно, отображение λ → T = N уникально.

Другими словами, решение задачи оптимизации с ограничением L1 на рис. 6 для многих последовательно больших значений T решает задачу оптимизации LASSO для многих последовательно меньших значений λ (в диапазоне от λ = ∞ до λ = 0).

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

Таким образом, исходя из двойственности между T и λ, это означает, что бустинг решает несколько проблем LASSO с широким диапазоном значений λ, заканчиваясь, когда мы находим уровень регуляризации, который приводит к хорошей производительности проверки (это «ранняя остановка», применяемая на практике). .) Другими словами, бустинг эффективно приближается к настройке гиперпараметров LASSO в нашем очень многомерном пространстве признаков.

Чтобы понять, почему бустинг эквивалентен последовательности задач регрессии с ограничениями L1, рассмотрим следующую задачу инкрементной оптимизации:

Здесь β_last — это решение задачи с ограничениями L1 на рис. 6 с определенным значением T (T_last). Теперь мы хотим найти оптимальное решение для немного более слабого ограничения L1, т. е. немного большего значения T — отсюда «инкрементальный» характер проблемы.

Предположим, что решение задачи на рис. 7 является «монотонным» обновлением, т. е. абсолютное значение каждой координаты решения больше или равно значению β_last (другими словами, «монотонность» означает, что обновление увеличивает расстояние от начала координат по каждой координате.) Наилучшее обновление на самом деле будет монотонным обновлением — обычное явление на практике, особенно для малых значений эпсилон. (Мы вернемся к вопросу почему нам нужна монотонность позже в этом разделе.)

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

Теперь — если наилучшее обновление на рис. 7 является монотонным, то оно по-прежнему является оптимальным решением, когда вы добавляете новое ограничение монотонности поверх существующего ограничения на рис. 7, поэтому мы можем добавить это ограничение монотонности без изменения окончательного решение. Эти два комбинированных ограничения эквивалентны следующему набору ограничений («эквивалентны» в смысле создания одного и того же набора допустимых β):

(Вы можете показать эту эквивалентность, используя определение монотонности вместе с неравенствами, включающими арифметические и абсолютные значения. На этот раз я опустил доказательство, но не стесняйтесь проверить меня на это!)

Если мы восстановим наше монотонное наилучшее обновление при паре ограничений на рис. 8, то мы также восстановим его, если отбросим второе ограничение и будем использовать только ограничение соседства L1 в первой строке. (Обратите внимание, что все β, которые достижимы при этом единственном ограничении соседства L1, также достижимы при исходном ограничении на рис. 7, поэтому мы никогда не «превышаем» исходное ограничение.)

У нас осталось ограничение, которое ограничивает наше обновление, чтобы оно было близким по расстоянию L1 к предыдущему параметру β_last. Другими словами, если оптимальное решение исходной задачи на рис. 7 — это монотонное обновление, то мы также восстановим его с помощью задачи локальной оптимизации, сосредоточенной вокруг β_last.

Мы почти там! Давайте перепишем задачу оптимизации на рис. 7, используя новое ограничение выше. Более того, если наша локальная окрестность вокруг β_lastдостаточно «маленькая» и наша функция стоимости C гладкая, то мы можем заменить целевую функцию (функцию «суммы затрат», которую мы минимизируем в фигурных скобках на рис. 7) с линейной аппроксимацией с использованием его градиента. Выполнение этих замен ограничения и целевой функции приводит к этой окончательной задаче оптимизации, которая восстанавливает то же самое лучшее обновление, что и на рис. 7, всякий раз, когда наилучшее обновление на рис. 7 является монотонным:

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

Это звучит знакомо? На каждом шаге мы обновляем только самую «важную» координату β; это эквивалентно небольшому шагу в наиболее «влиятельной» функции признаков (коэффициентом которой является указанная координата β).

Итак, резюмируем: задача оптимизации на рис. 7 — это инкрементная версия задачи оптимизации на рис. 6. Если мы решим рис. 6 для определенного значения T, а решение для немного большего значения T будет монотонным update, затем мы восстанавливаем его с помощью жадного повышения эпсилон. Пока каждая инкрементальная проблема решается монотонным обновлением, мы отслеживаем всю последовательность решений LASSO в рамках последовательности повышающих итераций. В этом случае каждая итерация повышения решает проблему LASSO для несколько меньшее значение λ.

Теперь мы упомянули, что важна монотонность; это связано с тем, что если монотонность нарушается, то больше нет идеального соответствия 1: 1 между нашей последовательностью повышающих решений и последовательностью решений LASSO. Это связано с тем, что нарушение монотонности означает, что мы эффективно пересматриваем и обновляем решение с меньшей нормой L1, а не ищем решение с постепенно увеличивающейся нормой L1 (соответствующей постепенно уменьшающемуся λ) на этой итерации. Однако в этом случае бустинг часто близко аппроксимирует последовательность LASSO even. Изучите следующий рисунок из этой статьи Efron et. al, сравнивая последовательность коэффициентов LASSO и последовательность бустинга в наборе данных о диабете:

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

Собираем вместе: Повышение дерева

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

В этом разделе мы быстро обсудим, как выглядит обновление эпсилон-жадного повышения с использованием наших деревьев «строительных блоков» и как оно сравнивается с классическим повышением дерева.

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

Напомним, что F_hat — это вектор выходных данных, сгенерированный путем оценки нашего аддитивного ансамбля по всем точкам данных (до любого нелинейного преобразования). Первая частная производная в правой части рис. 11 — это невязка/псевдоостаток, которую мы «подходят» на каждой итерации, когда мы делаем традиционное повышение градиента. Вторая частная производная — это элемент, который вводит зависимость от вектора коэффициентов β. Вот полное разложение этой частной производной:

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

Теперь, если наши функции «строительного блока» представляют собой «деревья с одним горячим элементом», как показано на рис. 3, тогда элементы вектора на рис. 12 равны 1 для всех x, которые попадают в «активный лист» соответствующего -горячее дерево F_i и ноль в противном случае. Тогда произведение на рис. 11 можно переписать следующим образом:

Другими словами, нахождение координаты β с наибольшим (абсолютным) градиентом эквивалентно нахождению листа разбиения с наибольшей (абсолютной) суммой невязок/псевдоостатков!

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

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

Сравнение с ядерными методами

Утверждается, что методы бустинга и кернела подходят для чего угодно. В традиционном мире машинного обучения оба являются «черным ящиком». Так в чем же преимущество одного над другим?

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

Используя ядерные методы, мы часто подгоняем линейную модель к новому «ядерному» пространству признаков. Вот пример с ядерной линейной регрессией, где цель оптимизации расширена за счет включения неявных функций ядра:

Обратите внимание, как похожа эта задача на задачу бустинга на рис. 5!

Сразу же мы можем увидеть один существенный недостаток ядерных методов: У нас мало выбора в отношении того, что такое неявные функции ядра ɸ.

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

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

Большинство ядерных методов используют ту или иную форму регуляризации для борьбы с переобучением и сверхпараметризацией (рис. 14 является примером ядерной гребневой регрессии, т. е. регуляризации L2). И хорошо известно, что вам необходимо масштабировать свои функции перед использованием L1/ Регуляризация L2 и родственные методы; в противном случае «меньшие» функции будут подвергаться большему наказанию, чем «крупные».

Однако ядерные методы делают невозможным надежное сохранение окончательных «функций ядра» в том же масштабе!

Рассмотрим полиномиальное ядро. Некоторые термины в полиномиальных ядрах имеют относительно большие масштабы — подумайте о (1 + xy)² и о том, как произведение термина «xy» имеет коэффициент 2, что дает конечному признаку степени-1 коэффициент √2, а конечную степень- 2 имеют меньший коэффициент, равный 1. В результате мы вынуждены непропорционально наказывать определенные термины при добавлении в регуляризацию, что может быть нежелательно для так называемого алгоритма «общего назначения».

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

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

С другой стороны, мы уже исследовали связь между бустингом и LASSO, а также то, как жадное эпсилон-бустинг, как и эффективные версии LASSO, решает несколько значений T/λ за одну подгонку, эффективно отслеживая всю «траекторию решений». ” в течение нескольких итераций повышения. Другими словами, бустирование в том виде, в каком оно обычно практикуется, дает нам форму настройки гиперпараметров в рамках одного подбора. Хорошо!

Заключение

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

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

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