Aumento de gradiente - Gradient boosting

O aumento de gradiente é uma técnica de aprendizado de máquina para regressão , classificação e outras tarefas, que produz um modelo de previsão na forma de um conjunto de modelos de previsão fracos, normalmente árvores de decisão . Quando uma árvore de decisão é o aluno fraco, o algoritmo resultante é chamado de árvores com aumento de gradiente, que geralmente supera a floresta aleatória . Ele constrói o modelo em uma forma de estágio, como outros métodos de boosting fazem, e os generaliza permitindo a otimização de uma função de perda diferenciável arbitrária .

História

A ideia do boost de gradiente originou-se da 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 aumento de gradiente de regressão foram subsequentemente desenvolvidos por Jerome H. Friedman , simultaneamente com a perspectiva de aumento de gradiente funcional mais geral de Llew Mason, Jonathan Baxter, Peter Bartlett e Marcus Frean. Os dois últimos artigos introduziram a visão de algoritmos de impulso como algoritmos de descida de gradiente funcional iterativos . Ou seja, algoritmos que otimizam uma função de custo sobre o espaço de função escolhendo iterativamente uma função (hipótese fraca) que aponta na direção do gradiente negativo. Essa visão de gradiente funcional do boosting levou ao desenvolvimento de algoritmos de boosting em muitas áreas de aprendizado de máquina e estatística, além da regressão e classificação.

Introdução informal

(Esta seção segue a exposição do aumento de gradiente por Li.)

Como outros métodos de reforço, o aumento de gradiente combina "alunos" fracos em um único aluno forte de forma iterativa. É mais fácil explicar na configuração de regressão de mínimos quadrados , onde o objetivo é "ensinar" um modelo a prever valores do formulário , minimizando o erro quadrático médio , onde os índices sobre algum conjunto de treinamento de tamanho de valores reais da saída variável : ${\ displaystyle F}$ ${\ displaystyle {\ hat {y}} = F (x)}$ ${\ displaystyle {\ tfrac {1} {n}} \ sum _ {i} ({\ hat {y}} _ {i} -y_ {i}) ^ {2}}$ ${\ displaystyle i}$ ${\ displaystyle n}$ ${\ displaystyle y}$

${\ displaystyle {\ hat {y}} _ {i} =}$ o valor predito ${\ displaystyle F (x)}$
${\ displaystyle y_ {i} =}$ o valor observado
${\ displaystyle n}$ o número de amostras em ${\ displaystyle y}$

Agora, vamos considerar um algoritmo de aumento de gradiente com estágios. Em cada estágio ( ) de aumento de gradiente, suponha algum modelo imperfeito (para baixo , este modelo pode simplesmente retornar , onde o RHS é a média de ). A fim de melhorar , nosso algoritmo deve adicionar algum novo estimador ,. Assim, ${\ displaystyle M}$ ${\ displaystyle m}$ ${\ displaystyle 1 \ leq m \ leq M}$ ${\ displaystyle F_ {m}}$ ${\ displaystyle m}$ ${\ displaystyle {\ hat {y}} _ {i} = {\ bar {y}}}$ ${\ displaystyle y}$ ${\ displaystyle F_ {m}}$ ${\ displaystyle h_ {m} (x)}$

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

ou equivalente,

{\ displaystyle h_ {m} (x) = y-F_ {m} (x)}

.

Portanto, o aumento de gradiente ajustará $h$ ao residual . Como em outras variantes de boost, cada uma tenta corrigir os erros de seu antecessor . Uma generalização desta ideia para outras funções de perda além do erro quadrático, e para problemas de classificação e classificação , segue da observação de que os resíduos para um determinado modelo são proporcionais equivalentes aos gradientes negativos da função de perda do erro quadrático médio (MSE) (em relação para ): ${\ displaystyle y-F_ {m} (x)}$ ${\ displaystyle F_ {m + 1}}$ ${\ displaystyle F_ {m}}$ ${\ displaystyle h_ {m} (x)}$ ${\ displaystyle F (x)}$

{\ displaystyle L _ {\ rm {MSE}} = {\ frac {1} {n}} \ left (yF (x) \ right) ^ {2}}

{\ displaystyle - {\ frac {\ partial L _ {\ rm {MSE}}} {\ partial F}} = {\ frac {2} {n}} (yF (x)) = {\ frac {2} { n}} h_ {m} (x)}

.

Portanto, o aumento de gradiente pode ser especializado em um algoritmo de descida de gradiente , e generalizá-lo envolve "conectar" uma perda diferente e seu gradiente.

Algoritmo

Em muitos problemas de aprendizagem supervisionada , há uma variável de saída $y$ e um vetor de variáveis de entrada $x$ , relacionadas entre si com alguma distribuição probabilística. O objetivo é encontrar alguma função que melhor se aproxime da variável de saída a partir dos valores das variáveis de entrada. Isso é formalizado pela introdução de alguma função de perda e minimizando-a: ${\ displaystyle {\ hat {F}} (x)}$ ${\ displaystyle L (y, F (x))}$

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

.

O método de aumento de gradiente assume um $y com$ valor real e busca uma aproximação na forma de uma soma ponderada de funções de alguma classe , chamados de alunos básicos (ou fracos ): ${\ displaystyle {\ hat {F}} (x)}$ ${\ displaystyle h_ {i} (x)}$ ${\ displaystyle {\ mathcal {H}}}$

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

.

Normalmente, recebemos um conjunto de treinamento de valores de amostra conhecidos de $xe$ valores correspondentes de $y$ . De acordo com a minimização do risco empírico princípio, o método tenta encontrar uma aproximação que minimiza o valor médio da função de perda no conjunto de treinamento, ou seja, minimiza o risco empírico. Ele faz isso começando com um modelo, que consiste em uma função constante , e o expande gradativamente de maneira gananciosa : ${\ displaystyle \ {(x_ {1}, y_ {1}), \ dots, (x_ {n}, y_ {n}) \}}$ ${\ displaystyle {\ hat {F}} (x)}$ ${\ displaystyle F_ {0} (x)}$

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

,

{\ displaystyle 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}))}} \direito]}

,

onde é uma função de aluno base. ${\ displaystyle h_ {m} \ in {\ mathcal {H}}}$

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

A ideia é aplicar um degrau de descida mais íngreme a este problema de minimização (descida de gradiente funcional).

A ideia básica por trás da descida mais íngreme é encontrar um mínimo local da função de perda iterando no . De fato, pode ser provado que a direção descendente máxima (derivada negativa mais forte) da função de perda para o mínimo local ao longo da é a própria função subtraída pelo próprio gradiente da função de perda. Portanto: ${\ displaystyle F_ {m} (x)}$ ${\ displaystyle F_ {m} (x)}$

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

Onde . Isto implica: . ${\ displaystyle \ gamma> 0}$ ${\ displaystyle L (y_ {i}, F_ {m} (x_ {i})) \ leq L (y_ {i}, F_ {m-1} (x_ {i}))}$

Além disso, podemos otimizar encontrando o valor para o qual a Função de Perda tem um mínimo: ${\ displaystyle \ gamma}$ ${\ displaystyle \ gamma}$

${\ displaystyle \ gamma _ {m} = {\ underset {\ gamma} {\ arg \ min}} {\ sum _ {i = 1} ^ {n} {L \ left (y_ {i}, F_ {m }) \ right)}} = {\ underset {\ gamma} {\ arg \ min}} {\ sum _ {i = 1} ^ {n} {L \ left (y_ {i}, F_ {m-1 } (x_ {i}) - \ gamma \ nabla _ {F_ {m-1}} L (y_ {i}, F_ {m-1} (x_ {i})) \ direita)}},}$

Se considerarmos o caso contínuo, ou seja, onde está o conjunto de funções diferenciáveis arbitrárias , atualizaríamos o modelo de acordo com as seguintes equações ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle \ mathbb {R}}$

{\ displaystyle 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}))}}

Onde:

{\ displaystyle \ gamma _ {m} = {\ underset {\ gamma} {\ arg \ min}} {\ sum _ {i = 1} ^ {n} {L \ left (y_ {i}, F_ {m -1} (x_ {i}) - \ gamma \ nabla _ {F_ {m-1}} L (y_ {i}, F_ {m-1} (x_ {i})) \ direita)}},}

onde as derivadas são obtidas em relação às funções para , e é o comprimento do passo. Porém, no caso discreto, isto é, quando o conjunto é 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 busca linear nas equações acima. Observe que essa abordagem é uma heurística e, portanto, não produz uma solução exata para o problema fornecido, mas sim uma aproximação. Em pseudocódigo, o método genérico de aumento de gradiente é: ${\ displaystyle F_ {i}}$ ${\ displaystyle i \ in \ {1, .., m \}}$ ${\ displaystyle \ gamma _ {m}}$ ${\ displaystyle {\ mathcal {H}}}$

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

Algoritmo:

Inicialize o modelo com um valor constante:
${\ displaystyle F_ {0} (x) = {\ underset {\ gamma} {\ arg \ min}} \ sum _ {i = 1} ^ {n} L (y_ {i}, \ gamma).}$
Para m = 1 a M :
1. Calcule os chamados pseudo-residuais :
  ${\ displaystyle r_ {im} = - \ left [{\ frac {\ parcial L (y_ {i}, F (x_ {i}))} {\ parcial F (x_ {i})}} \ direita] _ {F (x) = F_ {m-1} (x)} \ quad {\ mbox {para}} i = 1, \ ldots, n.}$
2. Ajustar um aluno básico (ou aluno fraco, por exemplo, árvore) fechado sob escala para pseudo-residuais, ou seja, treine-o usando o conjunto de treinamento . ${\ displaystyle h_ {m} (x)}$ ${\ displaystyle \ {(x_ {i}, r_ {im}) \} _ {i = 1} ^ {n}}$
3. Calcule o multiplicador resolvendo o seguinte problema de otimização unidimensional : ${\ displaystyle \ gamma _ {m}}$
  ${\ displaystyle \ 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}) \ direita).}$
4. Atualize o modelo:
  ${\ displaystyle F_ {m} (x) = F_ {m-1} (x) + \ gamma _ {m} h_ {m} (x).}$
Saída ${\ displaystyle F_ {M} (x).}$

Aumento de gradiente de árvore

O aumento de gradiente é normalmente usado com árvores de decisão (especialmente árvores CART ) de tamanho fixo como aprendizes básicos. Para este caso especial, Friedman propõe uma modificação no método de aumento de gradiente que melhora a qualidade de ajuste de cada aluno básico.

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

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

onde está o valor previsto na região . ${\ displaystyle b_ {jm}}$ ${\ displaystyle R_ {jm}}$

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

{\ displaystyle 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} (XI})).}

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

{\ displaystyle 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

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

Hastie et al. comentário que normalmente funciona bem para impulsionar e os resultados são bastante insensíveis à escolha de neste intervalo, é insuficiente para muitas aplicações e é improvável que seja necessário. ${\ displaystyle 4 \ leq J \ leq 8}$ ${\ displaystyle J}$ ${\ displaystyle J = 2}$ ${\ displaystyle J> 10}$

Regularização

Ajustar o conjunto de treinamento muito próximo pode levar à degradação da capacidade de generalização do modelo. Várias técnicas chamadas de regularização reduzem esse efeito de sobreajuste ao restringir o procedimento de ajuste.

Um parâmetro de regularização natural é o número de iterações M de aumento de gradiente (ou seja, o número de árvores no modelo quando o aluno base é uma árvore de decisão). Aumentar M reduz o erro no conjunto de treinamento, mas defini-lo muito alto pode levar ao sobreajuste. Um valor ideal de M é frequentemente selecionado monitorando o erro de predição em um conjunto de dados de validação separado. Além de controlar M , várias outras técnicas de regularização são utilizadas.

Outro parâmetro de regularização é a profundidade das árvores. Quanto mais alto for esse valor, maior será a probabilidade de o modelo super ajustar os dados de treinamento.

Encolhimento

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

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

onde o parâmetro é chamado de "taxa de aprendizagem". ${\ displaystyle \ nu}$

Empiricamente, descobriu-se que o uso de pequenas taxas de aprendizagem (como ) produz melhorias dramáticas na capacidade de generalização dos modelos sobre o aumento de gradiente sem encolher ( ). No entanto, isso tem o preço de aumentar o tempo computacional durante o treinamento e a consulta : a taxa de aprendizado mais baixa requer mais iterações. ${\ displaystyle \ nu <0,1}$ ${\ displaystyle \ nu = 1}$

Aumento de gradiente estocástico

Logo após a introdução do gradiente aumentando, Friedman propôs uma pequena modificação ao algoritmo, motivado por Breiman da agregação de bootstrap (método 'ensacamento'). Especificamente, ele propôs que a cada iteração do algoritmo, um aluno básico deveria ser ajustado em uma subamostra do conjunto de treinamento desenhado aleatoriamente sem substituição. Friedman observou uma melhoria substancial na precisão do aumento de gradiente com esta modificação.

O tamanho da subamostra é uma fração constante do tamanho do conjunto de treinamento. Quando , o algoritmo é determinístico e idêntico ao descrito acima. Valores menores de introduzem aleatoriedade no algoritmo e ajudam a prevenir overfitting , agindo como uma espécie de regularização . O algoritmo também se torna mais rápido, porque as árvores de regressão precisam se ajustar a conjuntos de dados menores a cada iteração. Friedman obteve que leva a bons resultados para conjuntos de treinamento de tamanho pequeno e moderado. Portanto, é normalmente definido como 0,5, o que significa que metade do conjunto de treinamento é usada para construir cada aluno básico. ${\ displaystyle f}$ ${\ displaystyle f = 1}$ ${\ displaystyle f}$ ${\ displaystyle 0,5 \ leq f \ leq 0,8}$ ${\ displaystyle f}$

Além disso, como no bagging, a subamostragem permite definir um erro fora do saco da melhoria de desempenho de predição, avaliando predições sobre as observações que não foram usadas na construção do próximo aluno base. As estimativas out-of-bag ajudam a evitar a necessidade de um conjunto de dados de validação independente, mas muitas vezes subestimam a melhoria real do desempenho e o número ideal de iterações.

Número de observações nas folhas

Implementações de aumento de gradiente de árvore geralmente também usam regularização, limitando o número mínimo de observações nos nós terminais das árvores. Ele é usado no processo de construção da árvore, ignorando quaisquer divisões que levem a nós contendo menos do que este número de instâncias de conjunto de treinamento.

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

Penalize a complexidade da árvore

Outra técnica de regularização útil para árvores com aumento de gradiente é 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 de perda e complexidade do modelo corresponde a um algoritmo de pós-poda para remover ramos que falham em reduzir a perda por um limite. Outros tipos de regularização, como uma penalidade nos valores das folhas, também podem ser adicionados para evitar o sobreajuste . ${\ displaystyle \ ell _ {2}}$

Uso

O aumento de gradiente pode ser usado no campo de aprendizado de classificação . Os motores de busca comerciais da web Yahoo e Yandex usam variantes de aumento de gradiente em seus motores de classificação aprendidos por máquina. O aumento de gradiente também é utilizado na Física de Altas Energias na análise de dados. No Large Hadron Collider (LHC), as variantes das Redes Neurais Profundas (DNN) que aumentam o gradiente foram bem-sucedidas na reprodução dos resultados de métodos de análise sem aprendizagem de máquina em conjuntos de dados usados para descobrir o bóson de Higgs .

Nomes

O método tem vários nomes. Friedman introduziu sua técnica de regressão como "Gradient Boosting Machine" (GBM). Mason, Baxter et al. descreveu a classe abstrata generalizada de algoritmos como "aumento de gradiente funcional". Friedman et al. descrever um avanço de modelos com aumento de gradiente como Árvores de Regressão Múltipla Aditiva (MART); Elith et al. descrever essa abordagem como "Boosted Regression Trees" (BRT).

Uma implementação popular de código aberto para R o chama de "Modelo de Boosting Generalizado", no entanto, os pacotes que expandem este trabalho usam BRT. Ainda outro nome é TreeNet, após uma implementação comercial inicial de Dan Steinberg, do Salford System, um dos pesquisadores que foi o pioneiro no uso de métodos baseados em árvore. XGBoost é outra implementação moderna popular do método com algumas extensões, como otimização de segunda ordem.

Desvantagens

Embora o boosting possa aumentar a precisão de um aluno básico, como uma árvore de decisão ou regressão linear, ele sacrifica a inteligibilidade e a interpretabilidade . Além disso, sua implementação pode ser mais difícil devido à maior demanda computacional.

Veja também

Referências

Leitura adicional

Boehmke, Bradley; Greenwell, Brandon (2019). "Gradient Boosting". Hands-On máquina de aprendizagem com R . Chapman & Hall. pp. 221–245. ISBN 978-1-138-49568-5.

Languages

In other projects