LightGBM алгоритмов машинного обучения

В предыдущей статье была представлена модель дерева решений с градиентным усилением.XGBoost, в этой статье мы продолжаем учитьсяGBDTЕще одна эволюция модели: LightGBM. LigthGBM — новый член модели повышающего ансамбля. Предоставляется Microsoft. Как и XGBoost, это эффективная реализация GBDT. В принципе, он похож на GBDT и XGBoost. Оба используют отрицательный градиент функции потерь в качестве остаточная аппроксимация текущего дерева решений, чтобы соответствовать новому дереву решений.

LightGBM во многом превзойдет XGBoost. Он имеет следующие преимущества:

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

Из экспериментальных данных на рисунке ниже видно, что LightGBM почти в 10 раз быстрее, чем XGBoost, использование памяти составляет примерно 1/6 от XGBoost, а также улучшена точность.

После прочтения этих удивительных экспериментальных результатов у меня возникли сомнения по поводу следующих двух вопросов: XGBoost уже идеален, зачем использовать модель с более высокой скоростью и меньшим использованием памяти? Каковы технические детали улучшения и расширения алгоритма GBDT?

Мотивация для предложения LightGBM

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

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

Преимущества и недостатки XGBoost

точный жадный алгоритм

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

преимущество:

Точные условия разделения можно найти

недостаток:

Огромное количество вычислений
огромное использование памяти
склонен к переоснащению

Итерация по уровням

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

преимущество:

Может использовать многопоточность
Ускоряет точные жадные алгоритмы

недостаток:

Неэффективно, может генерировать ненужные конечные узлы

Не дружит с оптимизацией кеша

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

Где оптимизирован LightGBM?

Вышесказанное является не столько недостатком XGBoost, сколько моментом, на который обращают внимание авторы LightGBM при построении новых алгоритмов. Какая проблема решена, то оригинальная модель не решает недостатков исходной модели.

В целом, lightGBM в основном имеет следующие характеристики:

Алгоритм дерева решений на основе гистограммы
Стратегия роста листьев по листу с ограничением глубины
Гистограмма дифференциального ускорения
Прямая поддержка категориальной функции
Оптимизация коэффициента попаданий в кэш
Оптимизация разреженных признаков на основе гистограммы
Многопоточная оптимизация

алгоритм дерева решений

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

Во-первых, все функции предварительно отсортированы по номерам.
Во-вторых, при каждой выборочной сегментации оптимальная точка сегментации для каждого признака находится со стоимостью O(# данных).
Наконец, найдите последний объект и точку разделения и разделите данные на левый и правый дочерние узлы.

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

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

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

Есть много преимуществ использования алгоритма гистограммы. Первый и самый очевидный — это уменьшение потребления памяти, алгоритм гистограммы не только не нуждается в хранении предварительно отсортированных результатов, но может только сохранять значение признака после дискретизации, а этого значения обычно достаточно для хранения в 8-битное целое число, а потребление памяти может быть уменьшено до 1/8 от исходного.

Тогда вычислительные затраты также значительно снижаются.Алгоритму предварительной сортировки необходимо вычислять усиление разделения каждый раз, когда он пересекает собственное значение, в то время как алгоритм гистограммы должен вычислять только k раз (k можно рассматривать как константу), а время сложность от O(# data*#feature) оптимизирована до O(k*#features).

Histogram algorithm

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

Есть несколько замечаний по алгоритму гистограммы:

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

Замечания по алгоритму гистограммы:

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

Преимущества и недостатки алгоритма гистограммы:

Алгоритм гистограммы не идеален. Так как признаки дискретизированы, находят не очень точные точки сегментации, поэтому это повлияет на результаты. Однако фактический набор данных показывает, что дискретизированные точки разделения мало влияют на конечную точность, а то и больше. Причина в том, что само дерево решений является слабым обучаемым, и использование алгоритма гистограммы будет иметь эффект регуляризации и эффективно предотвратит переоснащение модели.
Затраты времени сокращаются с O(#data * #features) до O(k * #features). Из-за дискретизации #bin намного меньше, чем #data, поэтому время значительно улучшается.

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

Стратегия роста дерева решений

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

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

LightGBM использует стратегию роста по листам, и каждый раз он находит лист с наибольшим усилением разделения (как правило, с наибольшим объемом данных) из всех текущих листьев, а затем разделяет его и так далее. Таким образом, по сравнению с Level-wise, Leaf-wise может уменьшить количество ошибок и получить более высокую точность при том же количестве расщеплений. Недостатком Leaf-wise является то, что он может вырастить относительно глубокое дерево решений, что приведет к переоснащению. Поэтому LightGBM добавляет максимальное ограничение глубины поверх Leaf-wise, чтобы предотвратить переобучение и обеспечить высокую эффективность.

Разностное ускорение гистограммы

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

Прямая поддержка функций категории

На самом деле, большинство инструментов машинного обучения не могут напрямую поддерживать функции категорий.Как правило, функции категорий необходимо преобразовать в однократные функции, что снижает эффективность использования пространства и времени. Использование категориальных признаков обычно используется на практике. Основываясь на этом соображении, LightGBM оптимизирует поддержку функций категории и может напрямую вводить функции категории без дополнительного расширения 0/1. И правило принятия решения о признаке категории добавляется к алгоритму дерева решений.

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

Разделение по этой функции категории может быть невозможным (т. е. эта функция тратится впустую). Использование однократного кодирования означает, что на каждом узле решения может использоваться только одно сравнение с остальными (например, собака, кошка и т. д.). Когда значений категории много, данных по каждой категории может быть относительно мало, и сегментация в это время будет несбалансированной, а значит, и выигрыш от сегментации будет небольшим (более интуитивное понимание состоит в том, что несбалансированная сегментация и несбалансированные точки сегментации без разницы).
Это повлияет на изучение дерева решений. Потому что, даже если их можно сегментировать в этой категории, данные будут сегментированы на множество фрагментированных небольших пространств, как показано в левой части рисунка 1. В обучении дерева решений используется статистическая информация.В этих небольших пространствах данных статистическая информация неточна, и обучение будет ухудшаться. Но если вы используете метод разделения в правой части рисунка ниже, данные будут разделены на два больших пространства, и дальнейшее обучение будет лучше.

Значение конечного узла в правой части рисунка ниже состоит в том, что X=A или X=C помещаются в левый дочерний элемент, а остальные помещаются в правый дочерний узел.

Общий процесс классификации обработки LightGBM включает:

Чтобы решить проблему недостаточности горячего кодирования для работы с категориальными функциями. LightGBM использует метод сегментации «Многие против многих» для достижения оптимальной сегментации характеристик категорий. С LightGBM вы можете напрямую вводить характеристики категорий и создавать эффект в правой части рисунка выше. Чтобы найти оптимальную сегментацию в признаке k-мерной категории, сложность простого алгоритма перечисления равна O(2^k) , в то время как LightGBM использует, например,On Grouping For Maximum Homogeneityметод реализован $O(k\log k)$ алгоритм.

Поток алгоритма показан на следующем рисунке: Перед перечислением точек разделения сначала отсортируйте гистограмму по среднему значению каждой категории, затем по очереди перечислите оптимальные точки разделения в соответствии с результатом среднего. Как видно из рисунка ниже, Сумма(у)/Количество(у) — это среднее значение категории. Конечно, этот метод склонен к переобучению, поэтому в LGBM к этому методу добавляется множество ограничений и регуляризаций.

На рисунке ниже показан простой сравнительный эксперимент, видно, что оптимальный метод улучшает AUC на 1,5 балла, а время увеличивается только на 20%.

Ниже подробно описывается процесс решения оптимальной сегментации функций категорий в коде:

Процесс создания гистограммы дискретных признаков: подсчитайте количество вхождений каждого дискретного значения в признаке и отсортируйте их от большего к меньшему, отфильтруйте собственные значения с меньшим количеством вхождений, а затем создайте бин-контейнер для каждого eigenvalue. , Непосредственно отфильтруйте собственные значения, которые реже появляются в контейнере бина, и не создавайте контейнер бина.
Процесс расчета порога разделения:
- Сначала посмотрите на количество мусорных контейнеров, разделенное на эту функцию.Если количество мусорных контейнеров меньше 4, напрямую используйте метод «один против другого» для сканирования каждого мусорного контейнера один за другим, чтобы найти лучшую точку разделения;
- В случае большого количества мусорных контейнеров сначала отфильтруйте и разрешите участвовать в расчете порога деления только контейнерам с большими подмножествами, а затем выполните расчет формулы для каждого подходящего контейнера (формула выглядит следующим образом: первый шаг всех выборок в бин-контейнер Сумма градусов/сумма градиентов второго порядка всех выборок под бин-контейнером + обычный член (параметр cat_smooth), почему это не среднее значение метки?На самом деле приведенный выше пример только для простоты понимания, только для изучения дерева и В случае проблемы регрессии, в настоящее время первая производная равна Y, а вторая производная равна 1), получить значение, отсортировать контейнер корзины от меньшего к большему в соответствии к значению, а затем выполнить поиск слева направо и справа налево, получить оптимальный порог разделения. Но есть один момент, вместо перебора всех бин-контейнеров задается верхний предел количества обыскиваемых бин-контейнеров, который в программе установлен равным 32, то есть параметром max_num_cat. Многие дискретные функции реализованы в LightGBM. по сравнению со стратегией многих, все контейнеры бинов слева или справа от оптимального порога деления в этих 32 бинах являются набором множества, а другие контейнеры бинов - другим набором множества.
- Для непрерывных объектов существует только один порог разделения. Для дискретных значений может быть несколько порогов разделения. Каждое пороговое значение разделения соответствует номеру контейнера бина. При использовании дискретных объектов для разделения, если номер контейнера бина соответствует данным выборка находится в пределах этих пороговых значений. В соответствующем наборе бинов эти данные добавляются в левое поддерево после разделения, в противном случае они добавляются в правое поддерево после разделения.

Прямая поддержка эффективного параллелизма

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

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

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

Для получения более подробной информации см. статью NIPS2016:A Communication-Efficient Parallel Algorithm for Decision Tree

оптимизация сетевого взаимодействия

Поскольку XGBoost использует предварительно отсортированный алгоритм, стоимость связи очень высока, поэтому алгоритм гистограммы также используется параллельно; алгоритм гистограммы, принятый LightGBM, имеет низкую стоимость связи, а линейное ускорение параллельных вычислений может быть достигнуто с помощью алгоритм коллективного общения.

Принцип LightGBM

Адрес бумаги:LightGBM A Highly Efficient Gradient Boosting

Дерево повышения — это процесс оптимизации, в котором для обучения используется аддитивная модель и алгоритм прямого распределения.У него есть несколько эффективных реализаций, таких как XGBoost, pGBRT, GBDT (дерево принятия решений с градиентным усилением) и т. д. Среди них GBDT использует отрицательный градиент в качестве показателя деления (прироста информации), а XGBoost использует вторую производную. Их общий недостаток заключается в том, что при вычислении прироста информации требуется сканирование всех выборок для нахождения оптимальной точки разбиения. При столкновении с большим объемом данных или высокой размерностью функций их эффективность и масштабируемость трудно удовлетворить. Прямой способ решить эту проблему - уменьшить количество признаков и данных, не влияя на точность.Некоторые работы ускоряют процесс повышения на основе выборки весов данных, но поскольку GBDT не имеет весов выборки, его нельзя применять.

LightGBM от Microsoft с открытым исходным кодом (основанный на GBDT) является хорошим решением этих проблем и в основном включает в себя два алгоритма:

Односторонняя выборка на основе градиента (GOSS)

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

Взаимоисключающая привязка функций, Exclusive Feature Bundling (EFB)

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

Алгоритм GBDT, который сочетает в себе GOSS и EFB, называется LightGBM.

Односторонняя выборка на основе градиента (GOSS)

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

Алгоритм Описание

В AdaBoost вес выборки является индикатором важности экземпляра данных. Однако в GBDT нет исходного веса выборки, и выборка по весу не может быть применена. К счастью, мы заметили, что каждые данные в GBDT имеют разное значение градиента, что очень полезно для выборки, то есть градиент экземпляра невелик, и ошибка обучения экземпляра также мала. , а прям идея выбросить эту часть данных с небольшими градиентами. Однако это изменит распределение данных, что повлияет на точность обученной модели.Чтобы избежать этой проблемы, мы предлагаем GOSS.

GOSS сохраняет все экземпляры с большими градиентами и использует случайную выборку для экземпляров с малыми градиентами. Чтобы компенсировать влияние на распределение данных, при расчете прироста информации GOSS вводит постоянный множитель для данных с небольшими градиентами. GOSS сначала сортирует по абсолютному значению градиента данных и выбирает верхние экземпляры. Затем случайным образом выберите b экземпляров из оставшихся данных. Затем при расчете прироста информации выборочные данные малого градиента умножаются на (1-a)/b, чтобы алгоритм уделял больше внимания недостаточно обученным экземплярам, не слишком сильно изменяя распределение исходного набора данных.

теоретический анализ

GBDT использует деревья решений, чтобы научиться получать функцию, которая отображает входное пространство в пространство градиента. Предположим, что обучающий набор имеет n экземпляров ${x_1,...,x_n}$ , а размер объекта равен s. На каждой итерации градиента направление отрицательного градиента функции потерь переменной данных модели выражается как ${g_1,...,g_n}$ , дерево решений делит данные на каждый узел через оптимальную точку разделения (точку максимального прироста информации). GBDT измеряет прирост информации по дисперсии после сегментации.

Определение: O представляет обучающий набор фиксированного узла, а точка сегментации d признака сегментации j определяется как:

$V_{j|O}(d) = \frac{1}{n_O} ( \frac{ ( \sum_{ \{x_i \in O: x_{ij} \le d \} } g_i )^2 }{n^j_{l|O}(d)} + \frac{ ( \sum_{ \{x_i \in O: x_{ij} > d \} } g_i )^2 }{n^j_{r|O}(d)} )$

в, $n_O = \sum I[x_i \in O], n^j_{l|O} = \sum I[x_i \in O: x_i \ge d ], n^j_{r|O} = \sum I[x_i \in O: x_i > d ]$

Переберите каждую точку разделения каждой функции и найдите d^*_j = argmax_d V_j(d) и рассчитать максимальный информационный прирост V_j(d^*_j) , затем разделите данные по признакам j^* точка разделения d^*_j Разделите данные на левый и правый дочерние узлы.

В ГОСТ,

Сначала отсортируйте обучение в порядке убывания в соответствии с градиентом данных.
Сохраняйте верхние экземпляры данных как подмножество данных A.
Для остальных экземпляров данных подмножество B данных размера b получается путем случайной выборки.
Наконец, мы оцениваем прирост информации по следующему уравнению:

(1) $\tilde{V}_j (d) = \frac{1}{n} ( \frac{ ( \sum_{ {x_i \in A: x_{ij} \le d } } g_i + \frac{1-a}{b}\sum_{ {x_i \in B: x_{ij} \le d } } g_i )^2 }{n^j{l}(d)} + \frac{ ( \sum_{ {x_i \in A: x{ij} > d } } g_i + \frac{1-a}{b}\sum_{ {x_i \in B: x{ij} > d } } g_i )^2 }{n^j_{r}(d)} )$

Здесь GOSS оценивает прирост информации с меньшим набором данных. $\tilde{V}{j}(d)$ Объем вычислений значительно сократится. Что еще более важно, далее мы теоретически показываем, что GOSS не сильно теряет точность обучения по сравнению со случайной выборкой, доказательство теории находится в дополнительном материале.

Мы определяем ошибку аппроксимации GOSS как:

$\varepsilon(d) = |\tilde{V}_j(d) - V_j(d) |$

$\bar{g}_l^j(d)=\frac{\sum_{x_i \in (A \cup A^c)_l} |g_i|}{n_l^j(d)}$

Вероятность не менее $1- \delta1$ ,имеют:

(2) $\varepsilon(d) \le C_{a, b}^2 \ln (1/\delta) * \max\{ \frac{1}{n_l^j(d)} , \frac{1}{n_r^j(d)} \} + 2*D*C_{a,b} \sqrt{ \frac{\ln(1/\delta)}{n}}$

в $C_{a,b}=\frac{1-a}{\sqrt{b}} \max_{x \in A^c}{|g_i|}, D=\max(\bar{g}_l^j(d), \bar{g}_r^j(d))$

На основании вышеизложенной теории делаем следующие выводы:

Коэффициент асимптотической аппроксимации GOSS $O(\frac{1}{n_l^j(d)}+ \frac{1}{n_r^j(d)} + \frac{1}{\sqrt{n}})$ . Если разделение данных не является чрезвычайно несбалансированным (например, $n_l^j(d) \ge O(\sqrt{n})$ и $n_r^j \ge O(\sqrt{n})$ ), то в погрешности аппроксимации в неравенстве (2) будет доминировать второе слагаемое, когда n стремится к бесконечности (при большом количестве данных), $O(\sqrt{n})$ будет стремиться к 0, то есть чем больше объем данных, тем меньше ошибка и выше точность.
Случайная выборка является случаем GOSS при a=0. В большинстве случаев GOSS превосходит случайную выборку, то есть в следующих случаях: $C_{0, \beta} > C_{a, \beta-a}$ ,Сейчас $\frac{\alpha_a}{\sqrt{\beta}} > \frac{1-a}{\sqrt{\beta-a}}$ ,в $\alpha_a = \max_{x_i \in A \cup A^c} |g_i| / \max_{x_i \in A^c} |g_i|$

Обобщение GOSS анализируется ниже. Учитывать ошибку обобщения GOSS $\varepsilon_{gen}^{GOSS}(d) = |\tilde{V}_j(d) - V_*(d)|$ , который представляет собой разницу между приростом дисперсии, рассчитанным экземпляром выборки GOSS, и фактическим приростом дисперсии выборки. превратиться в $\varepsilon_{gen}^{GOSS}(d) = |\tilde{V}_j(d) - V_j(d)|+ |V_j(d) - V_*(d)| \triangleq \varepsilon_{GOSS}(d)+ \varepsilon_{gen}(d)$ , следовательно, в случае точного GOSS ошибка обобщения GOSS аппроксимирует полный объем реальных данных. С другой стороны, выборка увеличит разнообразие базового обучаемого (поскольку данные, полученные от каждой выборки, могут быть разными), что улучшит обобщение.

Пакет эксклюзивных функций (EFB)

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

Шаги алгоритма EBF следующие:

Сортировка объектов по количеству ненулевых значений
Рассчитать коэффициент конфликта между различными функциями
Переберите каждую функцию и попытайтесь объединить функции, чтобы свести к минимуму коэффициент конфликта.

Данные высокого порядка обычно разрежены, и эта разреженность вдохновляет нас на разработку метода без потерь для уменьшения размерности признаков. В частности, в разреженном пространстве признаков многие признаки являются взаимоисключающими, то есть они никогда не бывают ненулевыми одновременно. Мы можем связать взаимоисключающие функции в одну функцию, и, тщательно разработав алгоритм маскирования функций, мы создадим ту же гистограмму функций, что и одна функция из набора функций. Таким образом, временная сложность межгистограммы снижается с O(#data * #feature) до O(#data * #bundle). Благодаря функции #bundle

Есть две проблемы:

Как решить, какие функции должны быть объединены вместе (сборка в комплекте)?
Как объединить функции в одну (объединить функцию)?

комплект (какие характеристики входят в комплект)?

**Теория 1:** Разбиение объекта на меньшее количество взаимоисключающих групп объектов является NP-трудным.

Доказательство: сведите задачу раскраски графа к этой задаче, а раскраска графа NP-трудна, поэтому эта задача NP-трудна.

Дан экземпляр раскраски графа G=(V, E). Взяв каждый признак строки матрицы сродства G, мы получим экземпляр нашей проблемы с признаками |V|. Легко видеть, что в нашей задаче набору вершин одного цвета соответствует набор уникальных признаков, и наоборот.

Теория 1 показывает, что решить эту NP-сложную задачу за полиномиальное время невозможно. Чтобы найти хороший алгоритм аппроксимации, мы сводим задачу оптимального связывания к задаче раскраски графа.Если два признака не являются взаимоисключающими, то мы соединяем их ребром, а затем используем разумный жадный алгоритм (с постоянной аппроксимацией ratio) ) используется для раскраски графика для объединения функций. Кроме того, отметим, что часто существует множество признаков, которые хотя и не являются на 100% взаимоисключающими, но редко одновременно принимают ненулевые значения. Если наш алгоритм может выдерживать небольшую долю коллизий, мы можем получить меньше пакетов функций, что еще больше повысит эффективность вычислений. После несложного расчета больше всего на точность повлияет случайное засорение небольшого числа собственных значений $O([(1 - \gamma)n]^{-2/3})$ , $\gamma$ - максимальное отношение столкновений в каждой привязке, когда оно относительно невелико, можно достичь компромисса между точностью и эффективностью.

**Алгоритм 3:** На основе приведенного выше обсуждения мы разработали Алгоритм 3, псевдокод показан на рисунке ниже, конкретный алгоритм:

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

Временная сложность алгоритма 3 равна O(#feature^2) , который обрабатывается только один раз перед обучением, и его временная сложность приемлема, когда признаков не слишком много, но сложно иметь дело с миллионами размерных признаков. Чтобы продолжать повышать эффективность, мы предлагаем более эффективную стратегию сортировки без графа: сортировка признаков по количеству ненулевых значений, что аналогично использованию степенной сортировки узлов графа, потому что обычно больше ненулевых значений привести к конфликтам, Новый алгоритм меняет стратегию сортировки на основе Алгоритма 3.

слияние функций

Как объединить функции из одного пакета, чтобы сократить время обучения. Дело в том, что исходные собственные значения можно отличить от связок. Учитывая, что алгоритм гистограммы хранит дискретные значения, а не непрерывные значения признаков, мы строим пакеты, помещая взаимоисключающие признаки в разные ячейки. Этого можно добиться, добавив смещение к исходному значению функции, например, предположим, что в наборе есть две функции, исходная функция A принимает значение [0, 10], а B принимает значение [0, 20]. Мы добавляем смещение 10 к B, поэтому B принимает значение [10, 30]. Таким образом, признаки A и B можно безопасно объединить, а признак со значением [0, 30] можно использовать для замены AB. См. Алгоритм 4 для алгоритма,

Алгоритм EFB может превратить многие взаимоисключающие признаки в малоразмерные плотные признаки, что может эффективно избежать вычисления ненужных признаков с нулевым значением. Фактически, записывая ненулевые значения в данные с таблицей, признак нулевого значения игнорируется, а базовый алгоритм гистограммы оптимизируется. При сканировании данных в таблице временная сложность построения гистограммы будет снижена с O(#data) до O(#non_zero_data). Конечно, этот подход требует дополнительной памяти и вычислительных ресурсов для поддержки таблицы предварительных признаков во время построения дерева. Мы используем эту оптимизацию в качестве базовой функции в lightGBM, потому что эта оптимизация не конфликтует с EFB (может использоваться для EFB), когда пакеты разрежены.

Ссылка на ссылку:blog.CSDN.net/Это 199308…

Как использовать LightGBM

Значение всех параметров см. на странице: http://lightgbm.apachecn.org/#/docs/6.

Процесс настройки параметров:

количество_листьев. LightGBM использует листовой алгоритм, поэтому num_leaves используется вместо max_depth при настройке сложности дерева. Приблизительное соотношение конверсии: $num\_leaves = 2^{(max\_depth)}$
Пример несбалансированного набора данных распределения: can param['is_unbalance']='true'
Параметры бэггинга: bagging_fraction+bagging_freq (должны быть заданы одновременно), feature_fraction. bagging_fraction может ускорить работу мешков, feature_fraction устанавливает пропорцию функций, используемых в каждой итерации.
min_data_in_leaf, min_sum_hessian_in_leaf: увеличение его значения может предотвратить переоснащение, и его значение обычно устанавливается относительно большим.

Подробнее см.:у-у-у. huaxiaozhuan.com/%E5%B7%A5%E…

Пример LightGBM в виде интерфейса sklearn

import lightgbm as lgb
from sklearn.metrics import mean_squared_error
from sklearn.model_selection import GridSearchCV
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
 
# 加载数据
iris = load_iris()
data = iris.data
target = iris.target
X_train, X_test, y_train, y_test = train_test_split(data, target, test_size=0.2)
 
# 创建模型，训练模型
gbm = lgb.LGBMRegressor(objective='regression', num_leaves=31, learning_rate=0.05, n_estimators=20)
gbm.fit(X_train, y_train, eval_set=[(X_test, y_test)], eval_metric='l1', early_stopping_rounds=5)
 
# 测试机预测
y_pred = gbm.predict(X_test, num_iteration=gbm.best_iteration_)
 
# 模型评估
print('The rmse of prediction is:', mean_squared_error(y_test, y_pred) ** 0.5)
 
# feature importances
print('Feature importances:', list(gbm.feature_importances_))
 
# 网格搜索，参数优化
estimator = lgb.LGBMRegressor(num_leaves=31)
param_grid = {
    'learning_rate': [0.01, 0.1, 1],
    'n_estimators': [20, 40]
}
gbm = GridSearchCV(estimator, param_grid)
gbm.fit(X_train, y_train)
print('Best parameters found by grid search are:', gbm.best_params_)

Нативная форма с использованием lightgbm

import lightgbm as lgb
from sklearn.metrics import mean_squared_error
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
 
iris = load_iris()
data = iris.data
target = iris.target
X_train, X_test, y_train, y_test = train_test_split(data, target, test_size=0.2)
 
# 创建成lgb特征的数据集格式
lgb_train = lgb.Dataset(X_train, y_train)
lgb_eval = lgb.Dataset(X_test, y_test, reference=lgb_train)
 
# 将参数写成字典下形式
params = {
    'task': 'train',
    'boosting_type': 'gbdt',  # 设置提升类型
    'objective': 'regression',  # 目标函数
    'metric': {'l2', 'auc'},  # 评估函数
    'num_leaves': 31,  # 叶子节点数
    'learning_rate': 0.05,  # 学习速率
    'feature_fraction': 0.9,  # 建树的特征选择比例
    'bagging_fraction': 0.8,  # 建树的样本采样比例
    'bagging_freq': 5,  # k 意味着每 k 次迭代执行bagging
    'verbose': 1  # <0 显示致命的, =0 显示错误 (警告), >0 显示信息
}
 
# 训练 cv and train
gbm = lgb.train(params, lgb_train, num_boost_round=20, valid_sets=lgb_eval, early_stopping_rounds=5)
 
# 保存模型到文件
gbm.save_model('model.txt')
 
# 预测数据集
y_pred = gbm.predict(X_test, num_iteration=gbm.best_iteration)
 
# 评估模型
print('The rmse of prediction is:', mean_squared_error(y_test, y_pred) ** 0.5)

быстрая проверка параметров

xgb	lgb	xgb.sklearn	lgb.sklearn
бустер = 'gbtree'	повышение = 'ГБТ'	бустер = 'gbtree'	boosting_type = 'ГБДТ'
target='бинарный:логистика'	приложение = 'двоичный'	target='бинарный:логистика'	цель = 'двоичный'
max_depth=7	num_leaves=2**7	max_depth=7	num_leaves=2**7
eta=0.1	learning_rate=0.1	learning_rate=0.1	learning_rate=0.1
num_boost_round=10	num_boost_round=10	n_estimators=10	n_estimators=10
gamma=0	min_split_gain=0.0	gamma=0	min_split_gain=0.0
min_child_weight=5	min_child_weight=5	min_child_weight=5	min_child_weight=5
subsample=1	bagging_fraction=1	subsample=1.0	subsample=1.0
colsample_bytree=1.0	feature_fraction=1	colsample_bytree=1.0	colsample_bytree=1.0
alpha=0	lambda_l1=0	reg_alpha=0.0	reg_alpha=0.0
lambda=1	lambda_l2=0	reg_lambda=1	reg_lambda=0.0
scale_pos_weight=1	scale_pos_weight=1	scale_pos_weight=1	scale_pos_weight=1
seed	bagging_seed feature_fraction_seed	random_state=888	random_state=888
nthread	num_threads	n_jobs=4	n_jobs=4
evals	valid_sets	eval_set	eval_set
eval_metric	metric	eval_metric	eval_metric
early_stopping_rounds	early_stopping_rounds	early_stopping_rounds	early_stopping_rounds
verbose_eval	verbose_eval	verbose	verbose

Ссылка на ссылку:Баченг Тереус.GitHub.IO/2018/09/13/…

больше ссылок

адрес проекта:GitHub.com/Microsoft/l…
Китайский документ:lightgbm.apachecn.org/
Ссылка на ссылку:Ууху. Call.com/question/26…

Вознаграждение автора WeChat Pay 标点符 wechat qrcode

Alipay