Gradient boosting

O gradient boosting é uma técnica de aprendizado de máquina para problemas de regressão e classificação, que produz um modelo de previsão na forma de um ensemble de modelos de previsão fracos, geralmente árvores de decisão. Ela constrói o modelo em etapas, como outros métodos de boosting, e os generaliza, permitindo a otimização de uma função de perda diferenciável arbitrária.

A ideia de gradient boosting originou-se na observação de Leo Breiman de que o boosting pode ser interpretado como um algoritmo de otimização em uma função de custo adequada. Algoritmos explícitos de gradient boosting de regressão foram desenvolvidos posteriormente por Jerome H. Friedman, simultaneamente com a perspectiva mais geral de gradient boosting funcional de Llew Mason, Jonathan Baxter, Peter Bartlett e Marcus Frean. Os dois últimos trabalhos introduziram a visão dos algoritmos de boosting como algoritmos iterativos de descida de gradiente funcionais, ou seja, algoritmos que otimizam uma função de custo sobre um espaço de funções, escolhendo iterativamente uma função (hipótese fraca) que aponta na direção oposta do gradiente. Essa visão dos algoritmos de boosting em termos de gradientes funcionais levou ao desenvolvimento de algoritmos de boosting em muitas áreas do aprendizado de máquina e da estatística além da regressão e classificação.

Introdução informal

(Esta seção segue a exposição de gradient boosting por Li. )

Como outros métodos de boosting, o gradient boosting combina "modelos de aprendizado" fracos em um único modelo de aprendizagem forte, de maneira iterativa. Isso pode ser explicado mais facilmente no contexto da regressão por mínimos quadrados, em que o objetivo é "ensinar" um modelo $F$ a prever valores da forma ${\hat {y}}=F(x)$ minimizando o erro médio quadrático ${\tfrac {1}{n}}\sum _{i}({\hat {y}}_{i}-y_{i})^{2},$ em que o índice $i$ percorre algum conjunto de treinamento de tamanho $n$ dos valores reais da variável de saída $y:$

• ${\hat {y}}_{i}=$ o valor previsto $F(x)$
• $y_{i}=$ o valor real
• $n$ o número de amostras em $y$

Agora, vamos considerar um algoritmo de gradient boosting com $M$ etapas. Em cada etapa $m$ ( $1\leq m\leq M$ ) de gradient boosting, considere algum modelo imperfeito $F_{m}$ (para um $m$ baixo, tal modelo pode simplesmente retornar ${\hat {y}}_{i}={\bar {y}},$ isto é, a média de $y$ ) Para melhorar $F_{m},$ o algoritmo deve adicionar algum novo estimador, $h_{m}(x).$ Portanto,

$$F_{m+1}(x)=F_{m}(x)+h_{m}(x)=y$$

ou, equivalentemente,

$$h_{m}(x)=y-F_{m}(x).$$

Portanto, o gradient boosting ajustará h ao resíduo $y-F_{m}(x).$ Como em outras variantes de boosting, cada $F_{m+1}$ tenta corrigir os erros de seu antecessor $F_{m}.$ Uma generalização dessa ideia para funções de perda que não sejam a de erro quadrático, e para problemas de classificação e ordenação segue da observação de que os resíduos $y-F(x)$ para um determinado modelo são os opostos dos gradientes (em relação a $F(x)$ ) da função de perda de erros quadráticos ${\frac {1}{2}}(y-F(x))^{2}.$ Portanto, o gradient boosting é um algoritmo de descida de gradiente e generalizá-lo implica em "conectar" uma função de perda diferente e seu gradiente.

Algoritmo

Em muitos problemas de aprendizado supervisionado, há uma variável de saída y e um vetor de variáveis de entrada x descritas por meio de uma distribuição de probabilidade conjunta $P(x,y).$ Usando um conjunto de treinamento $\{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}$ de valores conhecidos de x e valores correspondentes de y, o objetivo é encontrar uma aproximação ${\hat {F}}(x)$ para uma função $F(x)$ que minimiza o valor esperado de alguma função de perda especificada $L(y,F(x)):$

$${\hat {F}}={\underset {F}{\arg \min }}\,\mathbb {E} _{x,y}[L(y,F(x))].$$

O método de gradient boosting assume um y com valores reais e busca uma aproximação ${\hat {F}}(x)$ na forma de uma soma ponderada de funções $h_{i}(x)$ de alguma classe ${\mathcal {H}},$ chamada de modelos de aprendizagem básicos (ou fracos):

$${\hat {F}}(x)=\sum _{i=1}^{M}\gamma _{i}h_{i}(x)+{\mbox{const}}.$$

De acordo com o princípio de minimização de risco empírico, o método tenta encontrar uma aproximação ${\hat {F}}(x)$ que minimiza o valor médio da função de perda no conjunto de treinamento, ou seja, minimiza o risco empírico. Isso é feito começando com um modelo, consistindo de uma função constante $F_{0}(x)$ e expandindo-o gradualmente de maneira gananciosa:

$$F_{0}(x)={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L(y_{i},\gamma )}},$$

$$F_{m}(x)=F_{m-1}(x)+{\underset {h_{m}\in {\mathcal {H}}}{\operatorname {arg\,min} }}\left[{\sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}\right],$$

em que $h_{m}\in {\mathcal {H}}$ é uma função de modelo de aprendizagem básico.

Infelizmente, escolher a melhor função h em cada etapa para uma função de perda arbitrária L é, em geral, um problema de otimização computacionalmente inviável. Portanto, a abordagem se restringe a uma versão simplificada do problema.

A ideia é aplicar uma etapa de máximo declive a esse problema de minimização (descida de gradiente funcional). Se considerarmos o caso contínuo, ou seja, aquele em que ${\mathcal {H}}$ é o conjunto de funções diferenciáveis arbitrárias em $\mathbb {R} ,$ atualizaríamos o modelo de acordo com as seguintes equações

$$F_{m}(x)=F_{m-1}(x)-\gamma _{m}\sum _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))},$$

em que as derivadas são obtidas com relação às funções $F_{i}$ para $i\in \{1,..,m\}$ e $\gamma _{m}$ é o comprimento do passo. No entanto, no caso discreto, ou seja, quando o ${\mathcal {H}}$ é finito, escolhemos a função candidata h mais próxima do gradiente de L para a qual o coeficiente γ pode então ser calculado com o auxílio da pesquisa linear nas equações acima. Observe que essa abordagem é uma heurística e, portanto, não produz uma solução exata para o problema em questão, e sim uma aproximação. Em pseudocódigo, o método genérico de gradient boosting é:

Entrada: conjunto de treino $\{(x_{i},y_{i})\}_{i=1}^{n},$ uma função de perda diferenciável $L(y,F(x)),$ número de iteraçõesM.

Algoritmo:

1. Inicialize o modelo com um valor constante:

   $F_{0}(x)={\underset {\gamma }{\arg \min }}\sum _{i=1}^{n}L(y_{i},\gamma ).$

2. Para m = 1 até M:
   1. Calcule os chamados pseudo-resíduos:

      $r_{im}=-\left[{\frac {\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}}\right]_{F(x)=F_{m-1}(x)}\quad {\mbox{for }}i=1,\ldots ,n.$

   2. Ajuste um modelo de aprendizagem básico (ou fraco, tal como uma árvore) fechado sob escala $h_{m}(x)$ aos pseudo-resíduos, isto é, treine-o utilizando o conjunto de treino $\{(x_{i},r_{im})\}_{i=1}^{n}.$
   3. Calcule o multiplicador $\gamma _{m}$ através da resolução de um problema de otimização unidimensional:

      $\gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L\left(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})\right).$

   4. Atualize o modelo:

      $F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x).$

3. Saída $F_{M}(x).$

Gradient boosting em árvore

O gradient boosting normalmente é utilizado com árvores de decisão (especialmente árvores CART ) de um tamanho fixo como modelos de aprendizagem básicos. Para este caso especial, Friedman propõe uma modificação no método de gradient boosting que melhora a qualidade do ajuste de cada modelo básico.

O gradient boosting genérico na m- ésima etapa ajustaria uma uma árvore de decisão $h_{m}(x)$ a pseudo-resíduos. Seja $J_{m}$ a sua quantidade de folhas. A árvore divide o espaço de entrada em $J_{m}$ regiões disjuntas $R_{1m},\ldots ,R_{J_{m}m}$ e prevê um valor constante em cada região. Usando a notação do indicador, a saída de $h_{m}(x)$ para a entrada x pode ser escrita como a soma:

$$h_{m}(x)=\sum _{j=1}^{J_{m}}b_{jm}\mathbf {1} _{R_{jm}}(x),$$

onde $b_{jm}$ é o valor previsto na região $R_{jm}.$

Então os coeficientes $b_{jm}$ são multiplicados por algum valor $\gamma _{m},$ escolhido usando a pesquisa linear para minimizar a função de perda e o modelo é atualizado da seguinte forma:

$$F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x),\quad \gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})).$$

Friedman propõe modificar esse algoritmo para escolher um valores ótimos $\gamma _{jm}$ separados para cada uma das regiões da árvore, em vez de um único $\gamma _{m}$ para a árvore inteira. Ele chama o algoritmo modificado de "TreeBoost". Os coeficientes $b_{jm}$ do procedimento de ajuste de árvore podem então ser simplesmente descartados e a regra de atualização do modelo se torna:

$$F_{m}(x)=F_{m-1}(x)+\sum _{j=1}^{J_{m}}\gamma _{jm}\mathbf {1} _{R_{jm}}(x),\quad \gamma _{jm}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{x_{i}\in R_{jm}}L(y_{i},F_{m-1}(x_{i})+\gamma ).$$

Tamanho das árvores

O valor de $J,$ que é o número de nós terminais nas árvores, é o parâmetro do método que pode ser ajustado para um conjunto de dados disponível. Ele controla o nível máximo permitido de interação entre variáveis no modelo. Com $J=2$ (stumps de decisão), nenhuma interação entre variáveis é permitida. Com $J=3$ o modelo pode incluir efeitos da interação entre até duas variáveis e assim por diante.

Hastie et al. comenta que normalmente $4\leq J\leq 8$ funciona bem para o boosting e os resultados são bastante insensíveis à escolha de $J$ nesta faixa, $J=2$ é insuficiente para muitas aplicações e é improvável a necessidade de $J>10.$

Regularização

Um ajuste excessivo ao conjunto de treinamento pode levar à degradação da capacidade de generalização do modelo. Várias técnicas de regularização reduzem esse efeito de sobreajuste restringindo o procedimento de ajuste.

Um parâmetro de regularização natural é o número M de iterações de gradient boosting (ou seja, o número de árvores no modelo quando o modelo de aprendizagem básico é uma árvore de decisão). Aumentar M reduz o erro no conjunto de treinamento, mas configurá-lo alto demais pode levar ao sobreajuste. Um valor ideal de M frequentemente é selecionado pelo monitoramento do erro de previsão em um conjunto de dados de validação separado. Além deste controle do valor de M, são utilizadas várias outras técnicas de regularização.

Outro parâmetro de regularização é a profundidade das árvores. Quanto maior é esse valor, maior é a probabilidade de o modelo superestimar os dados de treinamento.

Encolhimento

Uma parte importante do método de gradient boosting é a regularização por encolhimento, que consiste em modificar a regra de atualização da seguinte maneira:

$$F_{m}(x)=F_{m-1}(x)+\nu \cdot \gamma _{m}h_{m}(x),\quad 0<\nu \leq 1,$$

em que o parâmetro $\nu$ é chamado de "taxa de aprendizado".

Empiricamente, verificou-se que o uso de taxas de aprendizado pequenas (tais como $\nu <0.1$ ) produz melhorias drásticas na capacidade de generalização dos modelos em relação ao gradient boosting sem encolhimento ( $\nu =1$ ) No entanto, isso tem como preço o aumento do tempo computacional durante o treinamento e as consultas: uma taxa de aprendizado mais baixa exige mais iterações.

Gradient boosting estocástico

Pouco depois da introdução do gradient boosting, Friedman propôs uma pequena modificação no algoritmo, motivada pelo método de agregação de bootstrap ("bagging") de Breiman. Especificamente, ele propôs que, a cada iteração do algoritmo, um modelo de aprendizagem básico deveria ser ajustado a uma subamostra do conjunto de treinamento extraída aleatoriamente sem substituição. Friedman observou uma melhoria substancial na precisão do gradient boosting com esta modificação.

O tamanho da subamostra é uma fração constante $f$ do tamanho do conjunto de treinamento. Quando $f=1,$ o algoritmo é determinístico e idêntico ao descrito acima. Valores menores de $f$ introduzem aleatoriedade no algoritmo e ajudam a evitar o sobreajuste, agindo como um tipo de regularização. O algoritmo também se torna mais rápido, porque as árvores de regressão precisam ser ajustadas a conjuntos de dados menores a cada iteração. Friedman obteve que $0.5\leq f\leq 0.8$ leva a bons resultados para conjuntos de treinamento de tamanho pequeno e moderado. Portanto, $f$ normalmente é definido como 0,5, o que significa que metade do conjunto de treinamento é usada para criar cada modelo de aprendizado básico.

Além disso, como na bagging, a subamostragem permite que seja definida um erro fora da bolsa da melhoria do desempenho das previsões, avaliando as previsões nas observações que não foram usadas na construção do próximo modelo de aprendizado básico. As estimativas fora da bolsa ajudam a evitar a necessidade de um conjunto de dados de validação independente, mas geralmente subestimam a melhoria real do desempenho e o número ideal de iterações.

Número de observações em folhas

As implementações de gradient boosting de árvore geralmente também usam regularização limitando o número mínimo de observações nos nós terminais das árvores (esse parâmetro é chamado n.minobsinnode no pacote R gbm ). Isso é usado no processo de construção da árvore ignorando quaisquer divisões que levem a nós que contêm menos que esse número de instâncias do conjunto de treinamento.

A imposição desse limite ajuda a reduzir a variância nas previsões nas folhas.

Penalização da complexidade da árvore

Outra técnica de regularização útil para gradient boosting de árvores é penalizar a complexidade do modelo aprendido. A complexidade do modelo pode ser definida como o número proporcional de folhas nas árvores aprendidas. A otimização conjunta da perda e da complexidade do modelo corresponde a um algoritmo pós-poda para remover ramificações que falham em reduzir a perda por um limite. Outros tipos de regularização, como uma penalidade $\ell _{2}$ nos valores das folhas, também podem ser adicionadas para evitar sobreajustes.

Uso

Gradient boosting pode ser usado no campo da aprendizagem da classificação. Os mecanismos comerciais de busca na web Yahoo e Yandex usam variantes de gradient boosting em seus mecanismos de classificação aprendidos por máquina.

Nomes

O método é conhecido por vários nomes. Friedman introduziu sua técnica de regressão como uma "Gradient Boosting Machine" (GBM). Mason, Baxter et al. descreveram a classe abstrata generalizada de algoritmos como "gradient boosting funcional". Friedman et al. descreveram um avanço de modelos de gradient boosting como árvores de regressão aditiva múltipla (MART); Elith et al. descrevem essa abordagem como "Boosted Regression Trees" (BRT).

Uma implementação popular de código aberto para R chama o método de de "Generalized Boosting Model", no entanto os pacotes que expandem esse trabalho usam o BRT. As implementações comerciais da Salford Systems usam os nomes "Multiple Additive Regression Trees" (MART) e TreeNet, ambos com marca registrada.^{[carece de fontes]}

Ver também

• AdaBoost
• Floresta aleatória
• XGBoost
• LightGBM
• CatBoost
• Aprendizado em árvore de decisão

Leitura complementar

• Boehmke, Bradley; Greenwell, Brandon (2019). «Gradient Boosting». Hands-On Machine Learning with R. Chapman & Hall. [S.l.: s.n.] pp. 221–245. ISBN 978-1-138-49568-5 

Ligações externas

• Como explicar o gradient boosting
• Árvores de regressão com gradient boosting