Здесь, в этом блоге, я хотел бы обсудить, что происходит внутри алгоритма Xgboost (математически)? Как это работает внутри?
Давайте рассмотрим приведенный ниже набор данных. В этом наборе данных алгоритм должен решить, основываясь на зарплате человека и его кредитном статусе, будет ли одобрен его запрос на кредитную карту или нет?
Зарплата ‹=50к и ›50к, всего 2 класса.
Кредит: B-плохо, G-хорошо, N-нормально.
Зарплата ‹=50к и ›50к, всего 2 класса.
Кредит: B-плохо, G-хорошо, N-нормально.
Основная цель любого алгоритма — уменьшить количество ошибок.
Вот шаги, которые xgboost предпринимает для минимизации ошибок:
· Расчет вероятности и остатков.
· Построить дерево решений.
· Рассчитать вес подобия и прирост информации
· Обрезка
· Выход базовой модели
· Повторяем процесс, пока не получим минимальные ошибки
Рассчитать вероятность и остатки:
Сначала xgboost вычисляет вероятность и остатки.
У нас есть фактическое «у», которое означает одобрение. У нас всего 2 класса 0 и 1. Ноль говорит не одобрено, 1 говорит одобрено.
Здесь легко рассчитать остатки, так как вероятность равна 0,5 (вероятность 0 и 1 равна 0,5). и вероятность различается в зависимости от данных.
А как считать остатки? Используя приведенную ниже формулу
Остатки = Фактический ‘y’ — Вероятность
Итак, как только вероятность и остатки вычисляются xgboost, на основе этого он строит деревья решений.
Построить дерево:
У нас есть две колонки справа, зарплата и кредитный статус. Таким образом, для этих двух столбцов будут построены разные деревья.
Теперь xgboost строит дерево со столбцом salary.
Все остатки будут присутствовать в корневом узле.
Теперь алгоритм разбивает наш корневой узел на основе ‹=50k и ›50k. поэтому создаются два листовых узла.
И значения остатков разбиваются соответственно.
Расчет веса сходства и коэффициента усиления:
Как только дерево создано для одного столбца, то есть для столбца зарплаты, xgboost вычисляет вес подобия и прирост информации.
Они рассчитываются для выбора наилучшего дерева или выбора наилучшей структуры для дерева.
Но как они рассчитываются?
Формула веса подобия (SW)
Вероятность
SW = сумма(остатки)²/(сумма(вероятность(1-вероятность)+лямбда)
Примените остатки и значения вероятности в этой формуле. Предположим, что лямбда равна 0. Лямбда — это гиперпараметр.
Вес подобия (SW) = (-0,5+0,5+0,5)² / (0,5(1-(-0,5))+0,5(1–0,5)+0,5(1–0,5) = 0,25/0,75 = 1/3
SW = 0.33
Таким образом, мы должны рассчитать SW.
Это SW для каждого узла. SWparent = 0,14, SW левый узел = 0, SW правый узел = 0,33.
Теперь xgboost необходимо рассчитать прирост или прирост информации.
Прирост = SW конечного узла 1 + SW конечного узла 2 — SW корневого узла.
Прирост = 0+0,33–0,14=0,21
Прирост = 0,21 для столбца зарплаты.
Итак, мы получили информационный прирост для столбца зарплаты.
Давайте сделаем то же самое для кредитной колонки.
Здесь на изображении алгоритм разделил кредит на 2 листа. B и (G, N) узлы.
Но почему не 3? У нас 3 класс? Таким образом, листья должны быть разделены на 3.
Нет, потому что xgboost выполняет только бинарное разделение, он не может выполнять более 2 разделений в одном корневом узле.
Итак, первая структура/дерево, как указано выше.
Затем алгоритм создает другую древовидную структуру.
(B,G) и N уходит в другую структуру.
Как только вы это понимаете, возникает другой вопрос. Но какое дерево выбрать? Так как здесь мы получили 2 древовидные структуры в столбце кредитных карт.
Это просто.
Сравните усиление для каждой структуры. А затем проверьте, какая структура дает лучший прирост.
Наибольший прирост станет корневым/родительским узлом, меньший — конечным узлом.
Итак, на данный момент алгоритм имеет одно дерево, созданное из структуры зарплаты, и 2 дерева из кредита.
Какой из них будет родительским узлом?
Простой, тот, который имеет лучший выигрыш, является родительским узлом.
Здесь, ради обучения, давайте предположим, что дерево зарплат имеет самый высокий прирост, а для столбца кредитов прирост меньше. На основе этого будет построено дерево. Здесь на изображении ниже вы можете увидеть, как формируется дерево.
Структура кредитного дерева находится ниже столбца зарплаты, так как мы получили (предполагаемый) меньший выигрыш по сравнению со столбцом зарплаты.
Таким образом, лучший сплит рассчитывается через Gain.
Но остановится ли это или алгоритм пойдет на расщепление?
Сокращение:
Это решается обрезкой. Останавливаться или позволить ей расколоться дальше. Обрезка режет деревья или, можно сказать, останавливает раскол.
Сокращение рассчитывается через значение покрытия.
Но как рассчитать стоимость покрытия? Вот формула
SW = сумма(остатки)²/(сумма(вероятность(1-вероятность)+лямбда)
значение покрытия = (сумма(вероятность(1-вероятность)+лямбда)
В формуле веса подобия часть знаменателя является значением покрытия.
Предположим, что лямбда = 0.
теперь мы получим значение покрытия как = 0,25
Теперь, если усиление разделения меньше значения покрытия, нам нужно отрезать ветку. Если больше 0,25, то разделение продолжается.
На этом обучающая часть завершена. Что, если мы получим тестовые данные?
Базовая модель:
То же самое повторяется и в тестовых данных. Но перед этим нам нужно правильно рассчитать вероятность. Это делается через выходные данные базовой модели. Как рассчитывается базовая модель?
Базовая модель = log (p/(1-p) = log 1 = 0
P-прежняя вероятность (которая была 0,5)
Теперь мы получаем Базовую модель = 0
Алгоритм будет использовать выходное значение базовой модели в сигмовидном уравнении.
Сигма(вывод базовой модели + альфа(SWtree1)+ альфа(SWtree2)+…+ альфа(SWдерево ‘n’)
Альфа — скорость обучения (это гиперпараметр)
Сигма (0+0,1(1))
Сигма (0,1)
Сигмовидное уравнение
1/(1+e⁰.1) = 0.6
Таким образом, с помощью этого алгоритма значение вероятности равно 0,6. Теперь алгоритм может вычислять остатки. И процесс продолжается.
