Краткое изложение алгоритмов машинного обучения — GBDT

Ссылка выглядит следующим образом

• Машинное обучение (4) — от gbdt до xgboost
• Личное резюме распространенных алгоритмов машинного обучения (для интервью)
• Введение и практика xgboost (принцип)

Введение

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

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

GBDTпредставляет собой линейную комбинацию, которая хочет объединить набор слабых учеников, а именно:

F ∗ =a rgminE x ,y [L(y ,F (x))] F (x; p m ,am )= ∑ m =0 M p m h( x; a m )
в приведенной выше формуле p m представляет размер шага, мы можем использовать метод градиентного спуска, чтобы решить его в форме функционального пространства, сначала фиксированной х, тогда правильно F(x) найти оптимальное решение. Структурный процесс приведен ниже:

Что нам нужно сделать, так это оценить g m (x) , направление градиента, аппроксимированное с помощью реализации дерева решений g m (x) , чтобы расстояние между ними было как можно меньше, и существует множество способов измерения расстояния, включая среднеквадратичную ошибку иLogLossошибка. приведено ниже с использованиемLogLossКонкретный вывод функции потерь:

L (y,F )=log (1+ exp (−2yF))y ∈[− 1,1 ]

Step1Сначала найдите начальное значение F 0 , пусть его частная производная равна 0. (При реализации это остаток, который должен соответствовать первому дереву):

Step 2оценить g m (x) и сопоставить его с деревом решений. g m (x) — градиент, реализованный как первый Остатки, которые должны соответствовать m деревьям:

Step 3Используйте метод Ньютона, чтобы найти размер убывающего шага. r j m — размер шага подгонки, реализованный как прогнозируемое значение для каждого дерева. (Обычно этот шаг опускается в реализации и используется вместоShrinkageСтратегия задает размер шага по параметрам, чтобы избежать переобучения.

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

p =pr ed ict (0)+∑ m =1 M sh rin kag e∗p red ict (d m )
Если требуется, чтобы интервал вывода прогнозируемого значения был [ 0,1] , который можно преобразовать следующим образом:
p rob abi lit y = 1 1 +e − 2∗p red ict

Деревья в GBDT — это деревья регрессии, а не деревья классификации.

РФ против GBDT

(1) Дерево деревьев в РФпараллельносгенерировано; дерево в GBDTприказсгенерировано; слишком много деревьев обоих будут переобучать, ноGBDT более склонен к переоснащению;

(2) Каждое дерево в РФФункции разделения относительно случайны; Предыдущее разбиение дерева в GBDT предпочтительно разбивает признаки, которые отличают большинство выборок, а последнее разбиение дерева различает признаки для небольшого числа выборок;

(3) Основными параметрами в РФ являютсяколичество деревьев; Основными параметрами в GBDT являютсяГлубина дерева, обычно 1;

Shrinkage

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

y (1~i)=y (1~i−1 )+s шаг *y i

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

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

1. Высокая точность
2. Может обрабатывать нелинейные данные
3. Может обрабатывать несколько типов функций
4. Подходит для низкоразмерных плотных данных
5. хорошая интерпретируемость модели
6. Нет необходимости нормализовать функции, и функции могут выбираться автоматически.
7. Может учитывать различные функции потерь, включая среднеквадратичную ошибку иLogLossЖдать

недостаток

1. boostingЭто последовательный процесс, поэтому параллелизм затруднителен, и необходимо учитывать связь между верхним и нижним деревьями.
2. высокая вычислительная сложность
3. Не используйте многомерные разреженные функции

настройка параметров

1. Количество деревьев 100~10000
2. Глубина листьев 3~8
3. Скорость обучения 0,01~1
4. Максимальное дерево узлов на листьях 20
5. Коэффициент обучающей выборки 0,5~1
6. Коэффициент выборки тренировочных функций (√n)

xgboost

xgboost — отличная реализация повышения Tree, он сияет в недавних соревнованиях Kaggle. Он имеет следующие отличные характеристики:

1. Сложность древовидной модели показана как член регуляризации, добавленный к цели оптимизации.
2. При выводе формулы используется производная второго порядка и используется разложение Тейлора второго порядка.
3. Реализован алгоритм аппроксимации нахождения точки разделения.
4. Разреженность признаков эксплуатируется.
5. Данные сортируются заранее и хранятся в виде блоков, что способствует параллельным вычислениям.
6. Основанный на распределенной коммуникационной среде Rabit, он может работать на MPI и пряже. (Последний больше не основан на кролике)
7. Реализация оптимизирована для архитектуры, а производительность оптимизирована для кэша и памяти.

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

Функции

Эта часть содержания относится к вопросу и ответу на Zhihu-В чем разница между GBDT и XGBOOST в алгоритмах машинного обучения?, ответ - бог оружия

1. Традиционный GBDT использует CART в качестве базового классификатора, а xgboost также поддерживает линейные классификаторы.В настоящее время xgboost эквивалентен логистической регрессии (проблема классификации) или линейной регрессии (проблема регрессии) с условиями регуляризации L1 и L2.— Параметры можно задать через бустер [по умолчанию=gbtree]: gbtree: древовидные модели/gblinear: линейные модели

2. Традиционный GBDT использует информацию о производной только первого порядка во время оптимизации, в то время как xgboost выполняет разложение Тейлора второго порядка на функции стоимости и одновременно использует производные первого и второго порядка. Кстати, инструмент xgboost поддерживает пользовательские функции стоимости, если функция может принимать производные первого и второго порядка.— Улучшена функция потерь (разложение Тейлора, информация первого порядка g и информация второго порядка h).

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

4. усадка и подвыборка столбцов —или для предотвращения переобучения

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

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

5.алгоритмы поиска разделения:
(1) точный жадный алгоритм —Жадный алгоритм для получения оптимальной точки сегментации
(2) приближенный алгоритм —Приближенный алгоритм предлагает концепцию точек сегментации-кандидатов.Во-первых, распределение точек-кандидатов сегментации получается с помощью алгоритма гистограммы, а затем информация о непрерывных признаках сопоставляется с различными сегментами в соответствии с точками-кандидатами сегментации, и подсчитывается сводная информация.
(3) Взвешенный квантильный эскиз —Алгоритм распределенной взвешенной гистограммы
Алгоритмы (2) и (3) здесь предназначены для решения проблемы, что данные не могут быть загружены в память за один раз или алгоритм (1) неэффективен в распределенной ситуации.Следующая цитата является кратким изложением великого бога оружие:

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

6. Обработка пропущенных значений. Для образцов с отсутствующими значениями признаков xgboost может автоматически определить направление разделения.— Разреженный алгоритм

7.Встроенная перекрестная проверка

XGBoost allows user to run a cross-validation at each iteration of the boosting process and thus it is easy to get the exact optimum number of boosting iterations in a single run. This is unlike GBM where we have to run a grid-search and only a limited values can be tested.

8.продолжить существующую модель (затем обучение существующей модели)

User can start training an XGBoost model from its last iteration of previous run. This can be of significant advantage in certain specific applications. GBM implementation of sklearn also has this feature so they are even on this point.

9.Высокая гибкость

**XGBoost allow users to define custom optimization objectives and evaluation criteria. This adds a whole new dimension to the model and there is no limit to what we can do.**

10. Параллельная обработка— Модуль проектирования системы, проектирование блочной структуры и т. д.

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

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

использование кода

Ниже приведено простое использованиеxgboostПример этой рамки.

# 划分数据集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.01, random_state=1729)
print(X_train.shape, X_test.shape)

#模型参数设置
xlf = xgb.XGBRegressor(max_depth=10, 
                        learning_rate=0.1, 
                        n_estimators=10, 
                        silent=True, 
                        objective='reg:linear', 
                        nthread=-1, 
                        gamma=0,
                        min_child_weight=1, 
                        max_delta_step=0, 
                        subsample=0.85, 
                        colsample_bytree=0.7, 
                        colsample_bylevel=1, 
                        reg_alpha=0, 
                        reg_lambda=1, 
                        scale_pos_weight=1, 
                        seed=1440, 
                        missing=None)

xlf.fit(X_train, y_train, eval_metric='rmse', verbose = True, eval_set = [(X_test, y_test)],early_stopping_rounds=100)

# 计算 auc 分数、预测
preds = xlf.predict(X_test)

Код, примененный к практическому примеру, изВведение и реальный бой xgboost

import numpy as np
import pandas as pd
import xgboost as xgb
from sklearn.cross_validation import train_test_split

#from xgboost.sklearn import XGBClassifier
#from sklearn import cross_validation, metrics   #Additional scklearn functions
#from sklearn.grid_search import GridSearchCV   #Perforing grid search
#
#import matplotlib.pylab as plt
#from matplotlib.pylab import rcParams

#记录程序运行时间
import time 
start_time = time.time()

#读入数据
train = pd.read_csv("Digit_Recognizer/train.csv")
tests = pd.read_csv("Digit_Recognizer/test.csv") 

params={
'booster':'gbtree',
'objective': 'multi:softmax', #多分类的问题
'num_class':10, # 类别数，与 multisoftmax 并用
'gamma':0.1,  # 用于控制是否后剪枝的参数,越大越保守，一般0.1、0.2这样子。
'max_depth':12, # 构建树的深度，越大越容易过拟合
'lambda':2,  # 控制模型复杂度的权重值的L2正则化项参数，参数越大，模型越不容易过拟合。
'subsample':0.7, # 随机采样训练样本
'colsample_bytree':0.7, # 生成树时进行的列采样
'min_child_weight':3, 
# 这个参数默认是 1，是每个叶子里面 h 的和至少是多少，对正负样本不均衡时的 0-1 分类而言
#，假设 h 在 0.01 附近，min_child_weight 为 1 意味着叶子节点中最少需要包含 100 个样本。
#这个参数非常影响结果，控制叶子节点中二阶导的和的最小值，该参数值越小，越容易 overfitting。 
'silent':0 ,#设置成1则没有运行信息输出，最好是设置为0.
'eta': 0.007, # 如同学习率
'seed':1000,
'nthread':7,# cpu 线程数
#'eval_metric': 'auc'
}

plst = list(params.items())
num_rounds = 5000 # 迭代次数

train_xy,val = train_test_split(train, test_size = 0.3,random_state=1)
#random_state is of big influence for val-auc
y = train_xy[:, 0]
X = train_xy[:, 1:]
val_y = val[:, 0]
val_X = val[:, 1:]

xgb_val = xgb.DMatrix(val_X,label=val_y)
xgb_train = xgb.DMatrix(X, label=y)
xgb_test = xgb.DMatrix(tests)


watchlist = [(xgb_train, 'train'),(xgb_val, 'val')]

# training model 
# early_stopping_rounds 当设置的迭代次数较大时，early_stopping_rounds 可在一定的迭代次数内准确率没有提升就停止训练
model = xgb.train(plst, xgb_train, num_rounds, watchlist,early_stopping_rounds=100)

model.save_model('./model/xgb.model') # 用于存储训练出的模型
print "best best_ntree_limit",model.best_ntree_limit 

print "跑到这里了model.predict"
preds = model.predict(xgb_test,ntree_limit=model.best_ntree_limit)

np.savetxt('xgb_submission.csv',np.c_[range(1,len(tests)+1),preds],delimiter=',',header='ImageId,Label',comments='',fmt='%d')

#输出运行时长
cost_time = time.time()-start_time
print "xgboost success!",'\n',"cost time:",cost_time,"(s)"

Используемый набор данных взят из Kaggle.Classify handwritten digits using the famous MNIST data– Набор данных для распознавания рукописных цифр, т.е.Mnistнабор данных.