Принятие решений [GDBT] как оружие на kaggle (3)

08 BDT (Дерево усиления)

Давайте сначала взглянем на простое дерево решений повышения, Дерево повышения — это интегрированный метод обучения, основанный на дереве решений CART в качестве базового ученика.

Усиленное дерево на самом деле представляет собой аддитивную модель и алгоритм прямого распределения, который выражается как

f_0(x)=0\\ f_m(x)=f_{m-1}+T(x,\Theta_m)\\ f_M=\sum_{m=1}^MT(x,\Theta_m)

На шаге m алгоритма прямого распределения при текущей модели $f_{m-1}(x）$ , решать

min(\sum_{i=1}^NL(y_i,f_{m-1}(x)+T(x,\Theta_m)))

получить m-е дерево решений $T(x,\Theta_m)$ . Разница между повышением деревьев для разных задач заключается в различии функций потерь, таких как экспоненциальная функция потерь для классификации и потеря квадратной ошибки для регрессии.

Когда усиленное дерево использует квадрат функции потерь, m-я итерация выражается как

L(y,.f_{m-1}(x)+T(x,\Theta_m))=(y-f_{m-1}(x)-T(x,\Theta_m))^2\\ =(r-T(x,\Theta_m))^2

Назовите r остатком, поэтому m-е дерево решений $T(x,\Theta_m)$ соответствует этому остатку. Следует отметить, что базовое дерево CART обучаемого в алгоритме повышенного дерева является деревом регрессии.

09 GBDT (Дерево повышения градиента)

Полное название GBDT: Gradient Boosting Decision Tree, то есть градиентное бустинговое дерево решений, под которым понимается градиентное бустинг + дерево решений. Фридман предлагает аппроксимацию с использованием наискорейшего спуска для соответствия базовому учащемуся с использованием отрицательного градиента функции потерь:

-[\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}]_{F(x)=F_{t-1}(x)}

Для удобства вывода умножьте на 1/2 перед функцией потерь

Взяв производную от F (Xi), имеем

\frac{\partial (y_i, F(x_i))}{\partial F(x_i)}=F(x_i)-y_i

Остаток является обратным градиенту, т.е.

r_{ti}=y_i-F_{t-1}=-[\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}]_{F(x)=F_{t-1}(x)}

Используйте отрицательные градиенты в качестве остатков для подгонки в BDT.

Процесс повышения градиента GBDT

Вход: тренировочный набор: $Data=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\},y_i\in \{+1,-1\}$

инициализация: $F_0(x)=argmin_{h_0}\sum_{i=1}^NL(y_i,h_0(x))$

for t=1 to T do

Вычислить отрицательный градиент $\widetilde{y_i}=-[\frac{\partial L(y_i,F(x)i)}{\partial F(x_i)}]_{F(x)=F_{t-1}(x)},i=1,2,3...,N$
Установите остаток, чтобы получить базового ученика $w_t=arg min_{w_t}\sum_{i=1}^N(\widetilde{y_i}-h_t(x;w_t))^2$
Получите веса базового обучения: $\alpha_t=argmin_{\alpha_t}\sum_{i=1}^NL(y_i,f_{t-1}(x_i)+\alpha_t h_t(x;w_t))$
возобновить $F_t(x)=F_{t-1}(x_i)+\alpha_th_t(x;w_t)$

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

Процесс ГБДТ

GBDT - это дерево решений, использующее повышение градиента (CART). Регрессия дерева CART делит пространство на K непересекающихся областей и определяет выход k каждой области. Математическое выражение выглядит следующим образом

Поток GBDT (регрессия)

Вход: Тренировочный набор: $Data=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\},y_i\in \{+1,-1\}$

инициализация: $F_0(x)=argmin_{h_0}\sum_{i=1}^NL(y_i,h_0(x))=argmin_c\sum_{i=1}^NL(y_i,c)$

for t-1 to T do

Вычислить отрицательный градиент: $\widetilde{y_i}=-[\frac{\partial L(y_i,F(x)i)}{\partial F(x_i)}]_{F(x)=F_{t-1}(x)},i=1,2,3...,N$
Сопоставьте невязку, чтобы получить дерево регрессии, и получите площадь листового узла t-го дерева $h_t(x)=\sum_{k=1}^Kc_kI(X\in R_{tk})$
возобновить $F_t(x)=F_{t-1}(x_i)+h_t(x)=F_{t-1}(x_i)+\sum_{k=1}^Kc_kI(X\in R_{tk})$

получить аддитивную модель $F(X)=\sum_{t-1}^Th_t(x)$

Поток (классификация) GBDT

GBDT для классификации по-прежнему использует дерево регрессии CART, использует softmax для отображения вероятностей, а затем подбирает остатки вероятностей.

$F_{k0}(x)=0,k=1,K$

For m=1 to M do:

$p_k(x)=\exp(F_k(x))/\sum_{l=1}^K\exp(F_t(X)),k=1,K$
For k=1 to K do:
- $\widetilde{y_{ik}}=y_{ik}-p_k(x_i),i=1,N$
- $\{R_{jkm}\}_{j=1}^J=J-terminal nodetree(\{\widetilde{y_{ik}},x_i\}_1^N)$
- $\gamma_{ikm}=\frac{K-1}{K}\frac{\sum_{x_i \in R_{jkm}}\widetilde{y_{ik}}}{s\sum_{x_i \in R_{jkm}}|\widetilde{y}_{ik}|(1-|\widetilde{y_{ik}}|)},j=1,N$
- $F_{km}(x)=F_{k,{m-1}}(x)+\sum_{j=1}^J\gamma_{jkm}1(x\in R_{jkm})$
endFor