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.
Imagem: PLeia2 · BY · Openverse
(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 {\displaystyle F} a prever valores da forma y ^ = F ( x ) {\displaystyle {\hat {y}}=F(x)} minimizando o erro médio quadrático 1 n ∑ i ( y ^ i − y i ) 2 , {\displaystyle {\tfrac {1}{n}}\sum _{i}({\hat {y}}_{i}-y_{i})^{2},} em que o índice i {\displaystyle i} percorre algum conjunto de treinamento de tamanho n {\displaystyle n} dos valores reais da variável de saída y : {\displaystyle y:} Agora, vamos considerar um algoritmo de gradient boosting com M {\displaystyle M} etapas. Em cada etapa m {\displaystyle m} ( 1 ≤ m ≤ M {\displaystyle 1\leq m\leq M} ) de gradient boosting, considere algum modelo imperfeito F m {\displaystyle F_{m}} (para um m {\displaystyle m} baixo, tal modelo pode simplesmente retornar y ^ i = y ¯ , {\displaystyle {\hat {y}}_{i}={\bar {y}},} isto é, a média de y {\displaystyle y} ) Para melhorar F m , {\displaystyle F_{m},} o algoritmo deve adicionar algum novo estimador, h m ( x ) . {\displaystyle h_{m}(x).} Portanto,
Imagem: worldoflard · BY-NC · Openverse
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 ) . {\displaystyle P(x,y).} Usando um conjunto de treinamento { ( x 1 , y 1 ) , … , ( x n , y n ) } {\displaystyle \{(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 F ^ ( x ) {\displaystyle {\hat {F}}(x)} para uma função F ( x ) {\displaystyle F(x)} que minimiza o valor esperado de alguma função de perda especificada L ( y , F ( x ) ) : {\displaystyle L(y,F(x)):} F ^ = arg min F E x , y [ L ( y , F ( x ) ) ] . {\displaystyle {\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 F ^ ( x ) {\displaystyle {\hat {F}}(x)} na forma de uma soma ponderada de funções h i ( x ) {\displaystyle h_{i}(x)} de alguma classe H , {\displaystyle {\mathcal {H}},} chamada de modelos de aprendizagem básicos (ou fracos):
Imagem: jpctalbot · BY · Openverse
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 ) {\displaystyle h_{m}(x)} a pseudo-resíduos. Seja J m {\displaystyle J_{m}} a sua quantidade de folhas. A árvore divide o espaço de entrada em J m {\displaystyle J_{m}} regiões disjuntas R 1 m , … , R J m m {\displaystyle 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 ) {\displaystyle h_{m}(x)} para a entrada x pode ser escrita como a soma: h m ( x ) = ∑ j = 1 J m b j m 1 R j m ( x ) , {\displaystyle h_{m}(x)=\sum _{j=1}^{J_{m}}b_{jm}\mathbf {1} _{R_{jm}}(x),}
Tamanho das árvores
O valor de J , {\displaystyle 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 {\displaystyle J=2} (stumps de decisão), nenhuma interação entre variáveis é permitida. Com J = 3 {\displaystyle 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 ≤ J ≤ 8 {\displaystyle 4\leq J\leq 8} funciona bem para o boosting e os resultados são bastante insensíveis à escolha de J {\displaystyle J} nesta faixa, J = 2 {\displaystyle J=2} é insuficiente para muitas aplicações e é improvável a necessidade de J > 10. {\displaystyle J>10.}
Imagem: Rob Ellis' · BY · Openverse
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 ) + ν ⋅ γ m h m ( x ) , 0 < ν ≤ 1 , {\displaystyle F_{m}(x)=F_{m-1}(x)+\nu \cdot \gamma _{m}h_{m}(x),\quad 0<\nu \leq 1,} em que o parâmetro ν {\displaystyle \nu } é chamado de "taxa de aprendizado". Empiricamente, verificou-se que o uso de taxas de aprendizado pequenas (tais como ν < 0.1 {\displaystyle \nu <0.1} ) produz melhorias drásticas na capacidade de generalização dos modelos em relação ao gradient boosting sem encolhimento ( ν = 1 {\displaystyle \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 {\displaystyle f} do tamanho do conjunto de treinamento. Quando f = 1 , {\displaystyle f=1,} o algoritmo é determinístico e idêntico ao descrito acima. Valores menores de f {\displaystyle 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 ≤ f ≤ 0.8 {\displaystyle 0.5\leq f\leq 0.8} leva a bons resultados para conjuntos de treinamento de tamanho pequeno e moderado. Portanto, f {\displaystyle f} normalmente é definido como 0,5, o que significa que metade do conjunto de treinamento é usada para criar cada modelo de aprendizado básico.
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 ℓ 2 {\displaystyle \ell _{2}} nos valores das folhas, também podem ser adicionadas para evitar sobreajustes.
Imagem: timsackton · BY-SA · Openverse
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.
Imagem: worldoflard · BY-NC · Openverse
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?]
