A Gentle Introduction to the Gradient Boosting Algorithm for Machine Learning

Last Updated on August 15, 2020

Gradient boosting é uma das técnicas mais poderosas para construir modelos preditivos.

Neste post você vai descobrir o algoritmo de aprendizagem de máquinas de reforço de gradiente e obter uma introdução suave sobre de onde ele veio e como ele funciona.

Após ler este post, você vai saber:

• A origem do reforço da teoria de aprendizagem e AdaBoost.
• Como o reforço de gradiente funciona, incluindo a função de perda, alunos fracos e o modelo aditivo.
• Como melhorar a performance sobre o algoritmo base com vários esquemas de regularização.

Pick start your project with my new book XGBoost With Python, incluindo tutoriais passo-a-passo e os arquivos de código fonte Python para todos os exemplos.

Vamos começar.

• Ajuda com o XGBoost em Python?
• A Origem do Boosting
• AdaBoost the First Boosting Algorithm
• Generalização do AdaBoost como Gradient Boosting
• Como o Gradient Boosting Funciona
• Função de perda
• Weak Learner
• Modelo aditivo
• Improvements to Basic Gradient Boosting
• Condições de árvore
• 2. Atualizações ponderadas
• Stochastic Gradient Boosting
• Penalized Gradient Boosting
• Gradient Boosting Resources
• Vídeos de reforço de gradiente
• Gradient Boosting in Textbooks
• Gradient Boosting Papers
• Deslizes de Reforço de Gradientes
• Páginas Web de reforço de gradiente
• Sumário
• Descubra os concursos vencedores do algoritmo!
• Desenvolva seus próprios modelos XGBoost em minutos
• Bring The Power of XGBoost To Your Own Projects

Ajuda com o XGBoost em Python?

Toma o meu curso gratuito de 7 dias por email e descobre xgboost (com código de amostra).

Clica para te inscreveres agora e também obter uma versão PDF Ebook grátis do curso.

Inicie o seu Mini-Curso GRÁTIS Agora!

A Origem do Boosting

A ideia de boosting surgiu da ideia de se um aluno fraco pode ser modificado para se tornar melhor.

Michael Kearns articulou o objectivo como o “Problema do Reforço de Hipóteses” declarando o objectivo de um ponto de vista prático como:

… um algoritmo eficiente para converter hipóteses relativamente pobres em hipóteses muito boas

– Thoughts on Hypothesis Boosting , 1988

Uma hipótese fraca ou um aprendiz fraco é definido como aquela cujo desempenho é pelo menos ligeiramente melhor do que a hipótese aleatória.

Estas idéias foram construídas a partir do trabalho de Leslie Valiant sobre a distribuição livre ou Provavelmente Correta (PAC), uma estrutura para investigar a complexidade dos problemas de aprendizagem de máquinas.

Aprimoramento da hipótese foi a idéia de filtrar observações, deixando aquelas observações que o fraco aprendiz pode lidar e concentrando-se no desenvolvimento de novos fracos aprende a lidar com as observações difíceis restantes.

A idéia é usar o método de aprendizagem fraca várias vezes para obter uma sucessão de hipóteses, cada uma recentrada nos exemplos que as anteriores achavam difíceis e mal classificadas. … Note, porém, não é nada óbvio como isto pode ser feito

– Provavelmente Aproximadamente Correcto: Algoritmos da Natureza para Aprendizagem e Prosperação num Mundo Complexo, página 152, 2013

AdaBoost the First Boosting Algorithm

A primeira realização de boosting que viu grande sucesso na aplicação foi Adaptive Boosting ou AdaBoost para abreviar.

Boosting refere-se a este problema geral de produzir uma regra de previsão muito precisa através da combinação de regras de previsão aproximadas e moderadamente imprecisas.

– Uma generalização teórica da aprendizagem on-line e uma aplicação para impulsionar, 1995

Os alunos fracos no AdaBoost são árvores de decisão com uma única divisão, chamadas de cotos de decisão para a sua brevidade.

AdaBoost trabalha ponderando as observações, colocando mais peso nas instâncias difíceis de classificar e menos naquelas já bem tratadas. Novos alunos fracos são adicionados sequencialmente que focam seu treinamento nos padrões mais difíceis.

Isso significa que amostras que são difíceis de classificar recebem pesos cada vez maiores até que o algoritmo identifique um modelo que classifique corretamente essas amostras

– Modelagem Preditiva Aplicada, 2013

Previsões são feitas por maioria de votos dos alunos fracos, ponderados pela sua precisão individual. A forma mais bem sucedida do algoritmo AdaBoost foi para problemas de classificação binária e foi chamado de AdaBoost.M1.

Você pode aprender mais sobre o algoritmo AdaBoost no post:

• Boosting e AdaBoost para Aprendizagem de Máquina.

Generalização do AdaBoost como Gradient Boosting

AdaBoost e algoritmos relacionados foram reformulados num quadro estatístico primeiro por Breiman chamando-os de ARCing algorithms.

Arcing é um acrónimo para Adaptive Reweighting e Combining. Cada passo em um algoritmo de arco consiste em uma minimização ponderada seguida por uma recomputação de e .

– Prediction Games and Arching Algorithms , 1997

Esta estrutura foi desenvolvida por Friedman e chamada Gradient Boosting Machines. Mais tarde, chamado apenas de Gradient Boosting ou Gradient Tree Boosting.

O framework estatístico lançou o boosting como um problema de otimização numérica onde o objetivo é minimizar a perda do modelo, adicionando alunos fracos usando um procedimento de descida de gradiente como o procedimento.

Esta classe de algoritmos foi descrita como um modelo aditivo de estágio. Isto porque um novo aluno fraco é adicionado de cada vez e os alunos fracos existentes no modelo são congelados e deixados inalterados.

Note que esta estratégia por etapas é diferente das abordagens por etapas que reajustam termos previamente inseridos quando novos são adicionados.

– Aproximação da Função Gananciosa: A Gradient Boosting Machine , 1999

A generalização permitiu o uso de funções de perda diferenciáveis arbitrárias, expandindo a técnica além dos problemas de classificação binária para suportar regressão, classificação multiclasse e mais.

Como o Gradient Boosting Funciona

O Gradient Boosting envolve três elementos:

1. Uma função de perda a ser otimizada.
2. Um fraco aprendiz a fazer previsões.
3. Um modelo aditivo para adicionar aprendizes fracos para minimizar a função de perda.

Função de perda

A função de perda usada depende do tipo de problema a ser resolvido.

Deve ser diferenciável, mas muitas funções de perda padrão são suportadas e você pode definir a sua própria.

Por exemplo, a regressão pode usar um erro quadrático e a classificação pode usar perda logarítmica.

Um benefício da estrutura de reforço de gradiente é que um novo algoritmo de reforço não precisa ser derivado para cada função de perda que pode querer ser usada, em vez disso, é uma estrutura genérica o suficiente para que qualquer função de perda diferenciável possa ser usada.

Weak Learner

Árvores de decisão são usadas como o aprendiz fraco no reforço de gradiente.

Árvores de regressão específicas são usadas que produzem valores reais para splits e cujos outputs podem ser adicionados juntos, permitindo que os outputs dos modelos subseqüentes sejam adicionados e “corrigir” os residuais nas previsões.

Árvores são construídas de forma gananciosa, escolhendo os melhores pontos de divisão com base em escores de pureza como Gini ou para minimizar a perda.

Inicialmente, como no caso do AdaBoost, foram usadas árvores de decisão muito curtas que só tinham uma única divisão, chamada cepa de decisão. Árvores maiores podem ser usadas geralmente com 4 a 8 níveis.

É comum restringir os alunos fracos de maneiras específicas, tais como um número máximo de camadas, nós, divisões ou nós foliares.

Esta é assegurar que os alunos permaneçam fracos, mas ainda podem ser construídos de uma forma gananciosa.

Modelo aditivo

Árvores são adicionadas uma de cada vez, e árvores existentes no modelo não são alteradas.

Um procedimento de descida de gradiente é usado para minimizar a perda ao adicionar árvores.

Tradicionalmente, a descida de gradiente é usada para minimizar um conjunto de parâmetros, tais como os coeficientes em uma equação de regressão ou pesos em uma rede neural. Após o cálculo do erro ou perda, os pesos são atualizados para minimizar esse erro.

Em vez dos parâmetros, temos sub-modelos de aprendizes fracos ou mais especificamente árvores de decisão. Após o cálculo da perda, para realizar o procedimento de descida de gradiente, devemos adicionar uma árvore ao modelo que reduz a perda (ou seja, seguir o gradiente). Fazemos isto parametrizando a árvore, depois modificamos os parâmetros da árvore e nos movemos na direção correta (reduzindo a perda residual.

Generalmente esta abordagem é chamada de descida de gradiente funcional ou descida de gradiente com funções.

Uma maneira de produzir uma combinação ponderada de classificadores que otimiza é por descida de gradiente no espaço funcional

– Algoritmos de Impulso como Descida de Gradiente no Espaço Funcional , 1999

A saída para a nova árvore é então adicionada à saída da sequência existente de árvores, num esforço para corrigir ou melhorar a saída final do modelo.

Um número fixo de árvores é adicionado ou o treinamento pára quando a perda atinge um nível aceitável ou não melhora mais em um conjunto de dados de validação externa.

Improvements to Basic Gradient Boosting

O reforço de gradiente é um algoritmo ganancioso e pode sobreajustar um conjunto de dados de treinamento rapidamente.

Pode beneficiar de métodos de regularização que penalizam várias partes do algoritmo e geralmente melhoram o desempenho do algoritmo ao reduzir o sobreajuste.

Nesta seção veremos 4 melhorias para o aumento do gradiente básico:

1. Condições de árvore
2. Atraso
3. Amostras aleatórias
4. Aprendizagem penalizada

Condições de árvore

É importante que os alunos fracos tenham habilidade, mas permaneçam fracos.

Há uma série de maneiras que as árvores podem ser constrangidas.

Uma boa heurística geral é que quanto mais constrangida for a criação de árvores, mais árvores serão necessárias no modelo, e o inverso, onde menos árvores individuais constrangidas, menos árvores serão necessárias.

Below são algumas restrições que podem ser impostas na construção de árvores de decisão:

• Número de árvores, geralmente adicionando mais árvores ao modelo pode ser muito lento para o ajuste excessivo. O conselho é continuar adicionando árvores até que não se observe mais melhorias.
• Profundidade das árvores, árvores mais profundas são árvores mais complexas e árvores mais curtas são preferidas. Geralmente, melhores resultados são observados com 4-8 níveis.
• Número de nós ou número de folhas, como profundidade, isto pode limitar o tamanho da árvore, mas não é limitado a uma estrutura simétrica se outras restrições forem usadas.
• Número de observações por partição impõe uma restrição mínima à quantidade de dados de treinamento em um nó de treinamento antes que uma partição possa ser considerada
• Melhoria mínima à perda é uma restrição à melhoria de qualquer partição adicionada a uma árvore.

2. Atualizações ponderadas

As previsões de cada árvore são somadas sequencialmente.

A contribuição de cada árvore para essa soma pode ser ponderada para retardar o aprendizado pelo algoritmo. Esta ponderação é chamada de contração ou taxa de aprendizagem.

Cada actualização é simplesmente escalada pelo valor do “parâmetro de taxa de aprendizagem v”

– Aproximação da Função Gananciosa: A Gradient Boosting Machine , 1999

O efeito é que o aprendizado é retardado, por sua vez requer mais árvores a serem adicionadas ao modelo, por sua vez levando mais tempo para treinar, proporcionando um trade-off de configuração entre o número de árvores e a taxa de aprendizado.

Diminuir o valor de v aumenta o melhor valor para M .

– Aproximação da Função Gananciosa: A Gradient Boosting Machine , 1999

É comum ter pequenos valores na faixa de 0,1 a 0,3, bem como valores inferiores a 0,1,

Similiar a uma taxa de aprendizagem em otimização estocástica, a retração reduz a influência de cada árvore individual e deixa espaço para que as futuras árvores melhorem o modelo.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

Uma grande visão sobre ensacar conjuntos e floresta aleatória estava permitindo que árvores fossem gananciosamente criadas a partir de subamostras do conjunto de dados de treinamento.

Este mesmo benefício pode ser usado para reduzir a correlação entre as árvores na sequência em modelos de reforço de gradiente.

Esta variação de reforço é chamada de reforço de gradiente estocástico.

Em cada iteração uma subamostra dos dados de treinamento é desenhada aleatoriamente (sem substituição) a partir do conjunto de dados de treinamento completo. A subamostra selecionada aleatoriamente é então usada, ao invés da amostra completa, para caber no aprendiz base.

– Stochastic Gradient Boosting , 1999

Um pequeno número de variantes de reforço estocástico que pode ser usado:

• Subsample lines before creating each tree.
• Subsample columns before creating each tree
• Subsample columns before considering each split.

Subamostragem geralmente agressiva, como a selecção de apenas 50% dos dados mostrou ser benéfica.

>

De acordo com o feedback do utilizador, a utilização de subamostragem de coluna previne a sobreamostragem ainda mais do que a tradicional subamostragem de linha

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Alterações adicionais podem ser impostas às árvores parametrizadas além de sua estrutura.

Árvores de decisão clássica como CART não são usadas como aprendizes fracos, em vez disso, uma forma modificada chamada árvore de regressão é usada que tem valores numéricos nos nós da folha (também chamados de nós terminais). Os valores nas folhas das árvores podem ser chamados de pesos em alguma literatura.

Assim, os valores de peso das folhas das árvores podem ser regularizados usando funções populares de regularização, como:

• L1 regularização de pesos.
• L2 regularização de pesos.

O termo adicional de regularização ajuda a suavizar os pesos finais aprendidos para evitar o excesso de ajuste. Intuitivamente, o objetivo regularizado tenderá a selecionar um modelo empregando funções simples e preditivas.

– XGBoost: A Scalable Tree Boosting System, 2016

Gradient Boosting Resources

Gradient boosting é um algoritmo fascinante e eu tenho certeza que você quer ir mais fundo.

Esta seção lista vários recursos que você pode usar para aprender mais sobre o algoritmo de reforço de gradiente.

Vídeos de reforço de gradiente

• Gradient Boosting Machine Learning, Trevor Hastie, 2014
• Gradient Boosting, Alexander Ihler, 2012
• GBM, John Mount, 2015
• Learning: Boosting, MIT 6.034 Inteligência Artificial, 2010
• xgboost: Um Pacote R para Impulso Rápido e Preciso Gradiente, 2016
• XGBoost: A Scalable Tree Boosting System, Tianqi Chen, 2016

Gradient Boosting in Textbooks

• Section 8.2.3 Boosting, página 321, An Introduction to Statistical Learning: with Applications in R.
• Secção 8.6 Reforço, página 203, Modelagem Preditiva Aplicada.
• Secção 14.5 Reforço do Gradiente Estocástico, página 390, Modelagem Preditiva Aplicada.
• Secção 16.4 Reforço, página 556, Aprendizagem de Máquina: Uma Perspectiva Probabilística
• Capítulo 10 Árvores de Reforço e Aditivos, página 337, Os Elementos da Aprendizagem Estatística: Data Mining, Inference, and Prediction

Gradient Boosting Papers

• Thoughts on Hypothesis Boosting , Michael Kearns, 1988
• Uma generalização teórica de decisão de aprendizagem on-line e uma aplicação para impulsionar , 1995
• Arcing the edge , 1998
• Stochastic Gradient Boosting , 1999
• Boosting Algorithms as Gradient Descent in Function Space , 1999

Deslizes de Reforço de Gradientes

• Introdução ao Reforço de Árvores, 2014
• Uma Introdução Suave ao Reforço de Gradientes, Cheng Li

Páginas Web de reforço de gradiente

• Boosting (aprendizagem de máquina)
• Impulso de gradiente
• Impulso de árvore de gradiente em scikit-learn

Sumário

Neste post você descobriu o algoritmo de reforço de gradiente para modelagem preditiva na aprendizagem de máquina.

Especificamente, você aprendeu:

• A história do reforço na teoria da aprendizagem e AdaBoost.
• Como o algoritmo de reforço de gradiente funciona com uma função de perda, alunos fracos e um modelo aditivo.
• Como melhorar o desempenho do reforço de gradiente com regularização.

Você tem alguma pergunta sobre o algoritmo de reforço de gradiente ou sobre este post? Faça suas perguntas nos comentários e eu farei o meu melhor para responder.