Повышение градиента
Часть серии о |
Машинное обучение и интеллектуальный анализ данных |
---|
Градиентное повышение — это метод машинного обучения, основанный на повышении в функциональном пространстве, где целью являются псевдоостатки, а не типичные остатки, используемые при традиционном повышении. Он дает модель прогнозирования в форме ансамбля слабых моделей прогнозирования, т. е. моделей, которые делают очень мало предположений о данных, которые обычно представляют собой простые деревья решений . [ 1 ] [ 2 ] Когда дерево решений является слабым обучаемым, результирующий алгоритм называется деревьями с градиентным усилением; обычно он превосходит случайный лес . [ 1 ] Модель деревьев с градиентным усилением строится поэтапно, как и в других методах повышения , но она обобщает другие методы, позволяя оптимизировать произвольную дифференцируемую функцию потерь .
История
[ редактировать ]Идея повышения градиента возникла в результате наблюдения Лео Бреймана о том, что повышение можно интерпретировать как алгоритм оптимизации подходящей функции стоимости. [ 3 ] Алгоритмы явного повышения градиента регрессии были впоследствии разработаны Джеромом Х. Фридманом . [ 4 ] [ 2 ] (в 1999 году и позже в 2001 году) одновременно с более общей точкой зрения Лью Мейсона, Джонатана Бакстера, Питера Бартлетта и Маркуса Фрина на повышение функционального градиента. [ 5 ] [ 6 ] В последних двух статьях представлен взгляд на алгоритмы повышения как на итеративные функциональные алгоритмы градиентного спуска . То есть алгоритмы, которые оптимизируют функцию стоимости в пространстве функций путем итеративного выбора функции (слабая гипотеза), которая указывает в направлении отрицательного градиента. Этот функциональный градиентный взгляд на повышение привел к разработке алгоритмов повышения во многих областях машинного обучения и статистики, помимо регрессии и классификации.
Неофициальное знакомство
[ редактировать ](Этот раздел следует за изложением повышения градиента Ченг Ли. [ 7 ] )
Как и другие методы повышения, градиентное повышение итеративным образом объединяет слабых «обучающихся» в одного сильного обучающегося. Это проще всего объяснить с помощью наименьших квадратов регрессии , где цель состоит в том, чтобы «обучить» модель. прогнозировать значения формы минимизируя среднеквадратическую ошибку , где индексы по некоторому обучающему набору размера фактических значений выходной переменной :
- прогнозируемое значение
- наблюдаемое значение
- количество образцов в
Теперь давайте рассмотрим алгоритм повышения градиента с этапы. На каждом этапе ( ) повышения градиента, предположим, какая-то несовершенная модель (для низких , эта модель может просто вернуться , где RHS — среднее значение ). Чтобы улучшить , наш алгоритм должен добавить новую оценку, . Таким образом,
или, что то же самое,
- .
Поэтому повышение градиента подойдет к остатку . Как и в других вариантах повышения, каждый пытается исправить ошибки своего предшественника . Обобщение этой идеи на функции потерь , отличные от квадратичной ошибки, а также на задачи классификации и ранжирования следует из наблюдения, что остатки для данной модели пропорциональны отрицательным градиентам функции потерь среднеквадратической ошибки (MSE) (по отношению к ):
- .
Таким образом, повышение градиента может быть специализировано для алгоритма градиентного спуска , и его обобщение влечет за собой «подключение» других потерь и их градиента.
Алгоритм
[ редактировать ]Во многих задачах обучения с учителем имеется выходная переменная y и вектор входных переменных x , связанные друг с другом некоторым вероятностным распределением. Цель состоит в том, чтобы найти некоторую функцию который лучше всего аппроксимирует выходную переменную из значений входных переменных. Это формализуется введением некоторой функции потерь и минимизируем его в ожидании:
- .
Метод повышения градиента предполагает действительное значение y . Он ищет приближение в виде взвешенной суммы M функций из какого-то класса , называемые базовыми (или слабыми ) учащимися:
- .
Обычно нам дают обучающий набор известных выборочных значений x и соответствующих значений y . В соответствии с принципом минимизации эмпирического риска метод пытается найти приближение что минимизирует среднее значение функции потерь на обучающем наборе, т. е. минимизирует эмпирический риск. Для этого он начинает с модели, состоящей из постоянной функции и постепенно жадно расширяет его :
- ,
- ,
для , где это базовая функция обучающегося.
К сожалению, выбор лучшей функции на каждом шаге для произвольной функции потерь L в целом является вычислительно неосуществимой задачей оптимизации. Поэтому мы ограничимся подходом к упрощенному варианту задачи.
Идея состоит в том, чтобы применить к этой задаче минимизации шаг наискорейшего спуска (функциональный градиентный спуск).
Основная идея наикрутейшего спуска состоит в том, чтобы найти локальный минимум функции потерь путем итерации по . Фактически, локальное направление максимального спуска функции потерь представляет собой отрицательный градиент. [ 8 ]
Таким образом, перемещение небольшого количества так что линейное приближение остается справедливым:
где . Для маленьких , это означает, что .
Доказательство функциональной формы производной
|
---|
Кроме того, мы можем оптимизировать найдя значение, при котором функция потерь имеет минимум:
Если мы рассмотрели непрерывный случай, т. е. когда – множество произвольных дифференцируемых функций на , мы обновим модель в соответствии со следующими уравнениями
где длина шага, определяемая как Однако в дискретном случае, т. е. когда множество конечно [ нужны разъяснения ] , мы выбираем функцию-кандидат h, ближайшую к градиенту L , для которой коэффициент γ затем можно вычислить с помощью поиска строки по приведенным выше уравнениям. Обратите внимание, что этот подход является эвристическим и поэтому не дает точного решения данной задачи, а скорее приближения. В псевдокоде общий метод повышения градиента: [ 4 ] [ 1 ]
Входные данные: обучающий набор. дифференцируемая функция потерь итераций М. количество
Алгоритм:
- Инициализируйте модель постоянным значением:
- Для m = 1 до M :
- Вычислите так называемые псевдоостатки :
- Подберите базового ученика (или слабого ученика, например дерева), закрытого при масштабировании. к псевдоостаткам, т.е. обучить его с помощью обучающего набора .
- Вычислить множитель решив следующую одномерную задачу оптимизации:
- Обновите модель:
- Вычислите так называемые псевдоостатки :
- Выход
Повышение градиентного дерева
[ редактировать ]Повышение градиента обычно используется с деревьями решений (особенно CART ) фиксированного размера в качестве базовых обучающихся. Для этого особого случая Фридман предлагает модификацию метода повышения градиента, которая улучшает качество соответствия каждого базового обучаемого.
Общее повышение градиента на m -м шаге соответствует дереву решений. к псевдоостаткам. Позволять быть числом его листьев. Дерево разбивает входное пространство на непересекающиеся регионы и прогнозирует постоянное значение в каждом регионе. Используя обозначение индикатора , вывод для входа x можно записать в виде суммы:
где прогнозируемое значение в регионе . [ 9 ]
Тогда коэффициенты умножаются на некоторое значение , выбранное с помощью линейного поиска так, чтобы минимизировать функцию потерь, и модель обновляется следующим образом:
Фридман предлагает модифицировать этот алгоритм так, чтобы он выбирал отдельное оптимальное значение. для каждой области дерева, а не по одному за все дерево. Он называет модифицированный алгоритм «TreeBoost». Коэффициенты из процедуры подгонки дерева можно просто отказаться, и правило обновления модели будет выглядеть следующим образом:
Размер деревьев
[ редактировать ], количество конечных узлов в деревьях, является параметром метода, который можно настроить для имеющегося набора данных. Он контролирует максимально допустимый уровень взаимодействия между переменными в модели. С ( пни решения ), взаимодействие между переменными не допускается. С модель может включать эффекты взаимодействия между двумя переменными и так далее.
Хасти и др. [ 1 ] прокомментируйте, что обычно хорошо работают для повышения, и результаты довольно нечувствительны к выбору в этом диапазоне, недостаточно для многих приложений, и вряд ли понадобится.
Регуляризация
[ редактировать ]Слишком точная подборка обучающего набора может привести к ухудшению способности модели к обобщению. Несколько так называемых методов регуляризации уменьшают этот эффект переоснащения , ограничивая процедуру подгонки.
Одним из естественных параметров регуляризации является количество итераций повышения градиента M (т. е. количество деревьев в модели, когда базовым обучаемым является дерево решений). Увеличение M уменьшает ошибку в обучающем наборе, но установка слишком высокого значения может привести к переобучению. Оптимальное значение M часто выбирается путем мониторинга ошибки прогнозирования на отдельном наборе данных проверки. Помимо управления M , используется несколько других методов регуляризации.
Еще одним параметром регуляризации является глубина деревьев. Чем выше это значение, тем больше вероятность того, что модель будет соответствовать обучающим данным.
Усадка
[ редактировать ]Важной частью метода повышения градиента является регуляризация путем сжатия, которая заключается в изменении правила обновления следующим образом:
где параметр называется «скоростью обучения».
Эмпирически было обнаружено, что использование небольших скоростей обучения (таких как ) дает значительное улучшение способности моделей к обобщению по сравнению с повышением градиента без сжатия ( ). [ 1 ] Однако за это приходится платить увеличением времени вычислений как во время обучения, так и во время выполнения запросов : более низкая скорость обучения требует большего количества итераций.
Стохастическое усиление градиента
[ редактировать ]Вскоре после введения повышения градиента Фридман предложил небольшую модификацию алгоритма, мотивированную Бреймана . ( методом бутстреп-агрегации «бэггинга») [ 2 ] В частности, он предположил, что на каждой итерации алгоритма базовый обучаемый должен соответствовать подвыборке обучающего набора, выбранной случайным образом без замены. [ 10 ] Благодаря этой модификации Фридман заметил существенное улучшение точности повышения градиента.
Размер подвыборки представляет собой некоторую постоянную долю размера обучающего набора. Когда , алгоритм детерминирован и идентичен описанному выше. Меньшие значения ввести случайность в алгоритм и помочь предотвратить переобучение , действуя как своего рода регуляризация . Алгоритм также становится быстрее, поскольку деревья регрессии должны соответствовать меньшим наборам данных на каждой итерации. Фридман [ 2 ] получил, что приводит к хорошим результатам для обучающих наборов небольшого и среднего размера. Поэтому, обычно устанавливается равным 0,5, что означает, что половина обучающего набора используется для построения каждого базового обучаемого.
Кроме того, как и в случае с пакетированием, подвыборка позволяет определить ошибку улучшения производительности прогнозирования путем оценки прогнозов на основе тех наблюдений, которые не использовались при построении следующего базового обучаемого. Готовые оценки помогают избежать необходимости в независимом наборе данных для проверки, но часто недооценивают фактическое улучшение производительности и оптимальное количество итераций. [ 11 ] [ 12 ]
Количество наблюдений в листьях
[ редактировать ]Реализации повышения градиентного дерева часто также используют регуляризацию, ограничивая минимальное количество наблюдений в конечных узлах деревьев. Он используется в процессе построения дерева, игнорируя любые разделения, которые приводят к узлам, содержащим меньшее количество экземпляров обучающего набора.
Наложение этого ограничения помогает уменьшить дисперсию прогнозов на листьях.
Штрафовать за сложность дерева
[ редактировать ]Еще один полезный метод регуляризации для деревьев с градиентным усилением — это штраф за сложность изученной модели. [ 13 ] Сложность модели можно определить как пропорциональное количество листьев в изученных деревьях. Совместная оптимизация потерь и сложности модели соответствует алгоритму пост-обрезки для удаления ветвей, которые не могут уменьшить потери на пороговое значение. Другие виды регуляризации, такие как Также можно добавить штраф к конечным значениям, чтобы избежать переобучения .
Использование
[ редактировать ]Повышение градиента можно использовать в области обучения ранжированию . Коммерческие поисковые системы Yahoo [ 14 ] и Яндекс [ 15 ] использовать варианты повышения градиента в своих механизмах ранжирования с машинным обучением. Повышение градиента также используется в физике высоких энергий при анализе данных. На Большом адронном коллайдере (БАК) варианты градиентного усиления глубоких нейронных сетей (DNN) успешно воспроизвели результаты немашинного обучения методов анализа на наборах данных, использованных для открытия бозона Хиггса . [ 16 ] Дерево решений повышения градиента также применялось при геологических исследованиях и исследованиях земли – например, при оценке качества коллектора из песчаника. [ 17 ]
Имена
[ редактировать ]Метод имеет множество названий. Фридман представил свою технику регрессии как «Машину повышения градиента» (GBM). [ 4 ] Мейсон, Бакстер и др. описал обобщенный абстрактный класс алгоритмов как «функциональное повышение градиента». [ 5 ] [ 6 ] Фридман и др. описать развитие моделей с градиентным усилением как деревьев множественной аддитивной регрессии (MART); [ 18 ] Элит и др. опишите этот подход как «Деревья усиленной регрессии» (BRT). [ 19 ]
Популярная реализация R с открытым исходным кодом называет ее «Обобщенной моделью повышения». [ 11 ] однако пакеты, расширяющие эту работу, используют BRT. [ 20 ] Еще одно название — TreeNet, в честь ранней коммерческой реализации Дэна Стейнберга из Salford System, одного из исследователей, которые первыми начали использовать древовидные методы. [ 21 ]
Рейтинг важности функций
[ редактировать ]Повышение градиента можно использовать для ранжирования важности функций, которое обычно основано на агрегирующей функции важности базовых учащихся. [ 22 ] Например, если алгоритм деревьев с градиентным усилением разработан с использованием деревьев решений на основе энтропии , алгоритм ансамбля ранжирует важность функций также на основе энтропии с оговоркой, что он усредняется по всем базовым учащимся. [ 22 ] [ 1 ]
Недостатки
[ редактировать ]Хотя повышение может повысить точность базового метода обучения, такого как дерево решений или линейная регрессия, оно жертвует разборчивостью и интерпретируемостью . [ 22 ] [ 23 ] Например, проследить путь, по которому дерево решений принимает решение, тривиально и самоочевидно, но следовать путям сотен или тысяч деревьев гораздо сложнее. Чтобы добиться как производительности, так и интерпретируемости, некоторые методы сжатия модели позволяют преобразовать XGBoost в единое «возрожденное» дерево решений, которое аппроксимирует одну и ту же функцию принятия решений. [ 24 ] Кроме того, его реализация может быть более сложной из-за более высоких вычислительных затрат.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д и ж Хасти, Т.; Тибширани, Р.; Фридман, Дж. Х. (2009). «10. Бустинг и аддитивные деревья» . Элементы статистического обучения (2-е изд.). Нью-Йорк: Спрингер. стр. 337–384. ISBN 978-0-387-84857-0 . Архивировано из оригинала 10 ноября 2009 г.
- ^ Перейти обратно: а б с д Фридман, Дж. Х. (март 1999 г.). «Повышение стохастического градиента» (PDF) . Архивировано из оригинала (PDF) 1 августа 2014 г. Проверено 13 ноября 2013 г.
- ^ Брейман, Л. (июнь 1997 г.). «Двигаясь по краю» (PDF) . Технический отчет 486 . Статистический факультет Калифорнийского университета в Беркли.
- ^ Перейти обратно: а б с Фридман, Дж. Х. (февраль 1999 г.). «Приближение жадных функций: машина повышения градиента» (PDF) . Архивировано из оригинала (PDF) 1 ноября 2019 г. Проверено 27 августа 2018 г.
- ^ Перейти обратно: а б Мейсон, Л.; Бакстер, Дж.; Бартлетт, Польша; Фрин, Маркус (1999). «Алгоритмы повышения как градиентный спуск» (PDF) . В С. А. Солле , Т. К. Лине и К. Мюллере (ред.). Достижения в области нейронных систем обработки информации 12 . МТИ Пресс. стр. 512–518.
- ^ Перейти обратно: а б Мейсон, Л.; Бакстер, Дж.; Бартлетт, Польша; Фрин, Маркус (май 1999 г.). «Алгоритмы повышения как градиентный спуск в функциональном пространстве» (PDF) . Архивировано из оригинала (PDF) 22 декабря 2018 г.
- ^ Ченг Ли. «Нежное введение в повышение градиента» (PDF) .
- ^ Ламберс, Джим (2011–2012). «Метод наикрутейшего спуска» (PDF) .
- ^ Примечание: в случае обычных деревьев CART деревья подбираются с использованием потерь по методу наименьших квадратов, поэтому коэффициент для региона равно значению выходной переменной, усредненному по всем экземплярам обучения в .
- ^ Обратите внимание, что это отличается от пакетирования, при котором производится выборка с заменой, поскольку используются выборки того же размера, что и обучающий набор.
- ^ Перейти обратно: а б Риджуэй, Грег (2007). Обобщенные усиленные модели: руководство по пакету gbm.
- ^ Изучите алгоритм повышения градиента для получения более точных прогнозов (с кодами на R)
- ^ Тяньци Чен. Введение в усиленные деревья
- ^ Казок, Дэвид и Чжан, Тонг (2008). Статистический анализ ранжирования оптимального байесовского подмножества. Архивировано 7 августа 2010 г. на Wayback Machine , страница 14.
- ^ Запись в корпоративном блоге Яндекса о новой модели ранжирования «Снежинск». Архивировано 1 марта 2012 г. на Wayback Machine (на русском языке).
- ^ Лалчанд, Видхи (2020). «Извлечение большего из расширенных деревьев решений: пример физики высоких энергий». arXiv : 2001.06033 [ stat.ML ].
- ^ Ма, Лунфэй; Сяо, Ханьмин; Тао, Цзинвэй; Чжэн, Тайи; Чжан, Хайцинь (1 января 2022 г.). «Интеллектуальный подход к оценке качества коллектора из плотного песчаника с использованием алгоритма дерева решений повышения градиента» . Открытые геологические науки . 14 (1): 629–645. Бибкод : 2022OGeo...14..354M . дои : 10.1515/geo-2022-0354 . ISSN 2391-5447 .
- ^ Фридман, Джером (2003). «Множественные деревья аддитивной регрессии с применением в эпидемиологии». Статистика в медицине . 22 (9): 1365–1381. дои : 10.1002/сим.1501 . ПМИД 12704603 . S2CID 41965832 .
- ^ Элит, Джейн (2008). «Рабочее руководство по усиленным деревьям регрессии» . Журнал экологии животных . 77 (4): 802–813. Бибкод : 2008JAnEc..77..802E . дои : 10.1111/j.1365-2656.2008.01390.x . ПМИД 18397250 .
- ^ Элит, Джейн. «Деревья усиленной регрессии для экологического моделирования» (PDF) . КРАН . Архивировано из оригинала (PDF) 25 июля 2020 года . Проверено 31 августа 2018 г.
- ^ «Эксклюзив: интервью с Дэном Стейнбергом, президентом Salford Systems, пионером в области интеллектуального анализа данных» .
- ^ Перейти обратно: а б с Пирионеси, С. Маде; Эль-Дираби, Тамер Э. (01 марта 2020 г.). «Анализ данных в управлении активами: экономически эффективное прогнозирование индекса состояния дорожного покрытия» . Журнал инфраструктурных систем . 26 (1): 04019036. doi : 10.1061/(ASCE)IS.1943-555X.0000512 . ISSN 1943-555X . S2CID 213782055 .
- ^ У, Синьдун; Кумар, Випин; Росс Куинлан, Дж.; Гош, Джойдип; Ян, Цян; Мотода, Хироши; Маклахлан, Джеффри Дж.; Нг, Ангус; Лю, Бинг; Ю, Филип С.; Чжоу, Чжи-Хуа (01 января 2008 г.). «10 лучших алгоритмов интеллектуального анализа данных». Знания и информационные системы . 14 (1): 1–37. дои : 10.1007/s10115-007-0114-2 . hdl : 10983/15329 . ISSN 0219-3116 . S2CID 2367747 .
- ^ Саги, Омер; Рокач, Лиор (2021). «Аппроксимация XGBoost с помощью интерпретируемого дерева решений». Информационные науки . 572 (2021): 522–542. дои : 10.1016/j.ins.2021.05.055 .
Дальнейшее чтение
[ редактировать ]- Бёмке, Брэдли; Гринвелл, Брэндон (2019). «Усиление градиента». Практическое машинное обучение с помощью R . Чепмен и Холл. стр. 221–245. ISBN 978-1-138-49568-5 .