Gradient Boosting Parte 3: XGBoost vs LightGBM vs CatBoost
por Guilherme Duarte, Data Scientist na Datarisk.io
Dando continuidade a nossa série de posts sobre os gradient boosting, mostraremos as diferenças teóricas e práticas entre o XGBoost, o LightGBM e o CatBoost, os três algoritmos de boosting mais populares do momento. Assumiremos aqui que o leitor está familiarizado com as principais diferenças entre os métodos de ensemble learning e com a heurística usada pelo XGBoost na construção das suas árvores de decisão. Caso esses tipos de conceitos não façam muito sentido para você no momento, recomendamos a Parte 1 e a Parte 2 da nossa série, onde tudo isso é explicado.
Sem mais delongas, vamos à explicação!
Introdução
Abaixo temos uma linha cronológica de quando cada algoritmo foi lançado.
O XGBoost é o mais antigo deles, sendo talvez por isso o mais conhecido entre eles. Começou como um projeto de pesquisa de Tianqi Chen e do brasileiro Carlos Guestrin, que publicaram juntos um artigo descrevendo o algoritmo. Caso queira conferir o artigo original, basta clicar aqui. Apesar disso, seu uso só ficou popular em 2016, quando começou a ser muito usado nas competições de Machine Learning, superando a performance de quase todos os outros algoritmos facilmente.
Em 2017, as primeiras versões estáveis e abertas ao público do LightGBM e do CatBoost foram lançadas. Apesar de similares com o XGBoost, cada um deles veio com uma proposta bem clara sobre qual o aspecto que eles tinham o objetivo de superar o XGBoost. Falaremos sobre isso mais a frente.
Dada a disponibilidade de artigos internet afora sobre o XGBoost (incluindo a parte 2 dessa série), hoje o foco será no LightGBM e no CatBoost. Falaremos sobre as diferenças estruturais destes em relação ao XGBoost, o propósito de cada algoritmo, como eles lidam com variáveis categóricas, a semelhança nos hiperparâmetros e mostraremos algumas comparações de performance.
Dito isso, vamos começar pelo LightGBM.
LightGBM
O principal objetivo do LightGBM é acelerar o treinamento, mantendo a mesma performance do XGBoost. Para isso, ele tem três grandes otimizações durante o processo de construção das árvores.
Em primeiro lugar, as variáveis contínuas são discretizadas em bins discretos na fase de encontrar o melhor threshold para dividir as amostras. Na semana passada, vimos que o XGBoost, em cada momento que dividia as amostras na construção da árvore, ordenava as amostras para cada feature, e escolhia a divisão que maximizava o ganho. O LightGBM também faz o mesmo processo, porém, discretizando as variáveis contínuas, temos um número bem menor de thresholds para testar, o que acelera o processo de treinamento.
Além disso, o LightGBM usa uma técnica de amostragem chamada de GOSS (Gradient-based One-Side Sampling), que consiste no seguinte: o gradiente representa a inclinação da tangente da função de perda; portanto, se o gradiente de uma determinada amostra é grande em algum sentido, essa amostra apresenta maior erro, tornando esses pontos importantes para encontrar o ponto de divisão ideal. Aqui podemos fazer uma analogia com o AdaBoost, que a cada iteração, estabelece um peso para as amostras proporcional ao erro em sua estimação, indicando quais amostras o modelo está errando mais na predição. A ideia aqui é a mesma: as amostras com maior valor do gradiente são amostras com um erro maior.
Após o cálculo dos gradientes, vêm a etapa da amostragem. O GOSS mantém todas as instâncias com gradientes altos e realiza uma amostragem aleatória nas instâncias com pequenos gradientes. Por exemplo, digamos que eu tenha um conjunto de dados com 500 mil linhas, sendo que em 10 mil, temos erros mais altos. Portanto, o algoritmo escolherá 10 mil linhas de gradiente mais alto + x% das 490 mil linhas restantes escolhidas aleatoriamente. Supondo que x seja 10, o total de linhas selecionadas terá 59k (10k+49k) de 500K com base no valor da divisão, se encontrado. Dessa maneira, na próxima iteração, teremos um número bem menor de amostras para serem consideradas, o que também acelera o treinamento.
A suposição básica tomada aqui é que as amostras com gradientes pequenos apresentam um erro de treinamento menor e já estão bem treinadas. Para manter a mesma distribuição de dados, ao calcular o ganho de informações, o GOSS introduz um multiplicador constante para as instâncias de dados com pequenos gradientes. Assim, o GOSS alcança um bom equilíbrio entre reduzir o número de instâncias de dados e manter a precisão das árvores de decisão.
Por último, temos uma diferença no modo como as árvores de decisão crescem. O XGBoost usa uma abordagem chamada de level-wise tree growth, enquanto o LightGBM usa a abordagem denominada leaf-wise tree growth. Abaixo temos duas imagens ilustrando como cada árvore fica mais profunda.
Repare que, na abordagem leaf-wise, em cada nível, apenas um dos lados da árvore fica mais profunda. Isto significa que a cada nível, temos uma quantidade cada vez menor de resíduos a se considerar de modo a encontrar o threshold que maximize o ganho. Logo, temos outra aceleração no processo de treinamento aqui.
CatBoost
O CatBoost, por sua vez, tem dois grandes objetivos: evitar o overfitting e fornecer bons hiperparâmetros padrão. Seu nome é uma abreviação de Categorical Boosting, devido a sua maneira especial de lidar com variáveis categóricas.
A primeira diferença estrutural que podemos citar do CatBoost é o uso de uma estrutura de dados chamada Oblivious Tree, onde cada nível da árvore tem o mesmo split para todos os ramos. Para exemplificar:
Esse tipo de estrutura leva a um tempo de predição muito baixo, visto que o número de splits distintos cresce linearmente com a profundidade da árvore, e não exponencialmente como o XGBoost.
Para explicar como o CatBoost tenta evitar o overfitting, vamos comparar o procedimento adotado por ele com o procedimento adotado pelos outros algoritmos de boosting.
De um modo geral, para o XGBoost e para o LightGBM, temos os seguintes passos:
- Considere todos (ou uma amostra ) dos dados para treinar um modelo com alto bias.
- Calcule os resíduos para cada ponto.
- Treine outro modelo com os mesmos pontos e seus correspondentes resíduos como variável resposta.
- Repita o passo 2 e 3 (por n iterações).
Esse procedimento é muito propenso ao overfitting, porque estamos calculando os resíduos de cada ponto usando um modelo que já foi treinado no mesmo conjunto de pontos.
Tendo em vista esse problema, o CatBoost faz o boosting de uma maneira muito elegante. Vamos explicá-la usando um exemplo simples.
Digamos que temos 10 pontos em nosso conjunto e estão ordenados no tempo como mostrado abaixo.
Se os dados não tem uma ordenação, a cada iteração o algoritmo seleciona uma ordenação aleatória, como se criasse um tempo artificial para cada ponto.
Após isso, o CatBoost adota o seguinte procedimento:
- Calcula os resíduos de cada ponto usando um modelo que foi treinado em todos os outros pontos anteriores a ele . Por exemplo, para calcular o resíduo do ponto x5, treinamos um modelo usando os pontos x1, x2, x3 e x4. Portanto treinamos diferentes modelos para pontos diferentes. No final, estamos calculando resíduos para pontos onde o modelo correspondente nunca foi treinado.
- Treine o modelo usando os resíduos de cada ponto como variável resposta.
- Repita os passos 1 e 2 (por n iterações).
Para o conjunto de dados acima, devemos treinar 9 modelos diferentes para obter resíduos para 9 pontos. Isso pode ser computacionalmente caro. Portanto, por padrão, em vez de treinar modelos diferentes para cada um dos pontos, isto é, n modelos para n pontos, são treinados log (n) modelos, de modo que se um modelo foi treinado em n pontos, esse modelo é usado para calcular resíduos para os próximos n pontos. Ou seja, um modelo que foi treinado no primeiro ponto é usado para calcular o resíduo do segundo ponto. Outro modelo que foi treinado nos dois primeiros pontos é usado para calcular resíduos do terceiro e quarto pontos, e assim por diante.
Todo esse procedimento explicado até agora é conhecido como ordered boosting (boosting ordenado).
A última característica que iremos mostrar do CatBoost é a forma com o qual ele lida com features categóricas.
Por padrão, o CatBoost utiliza a abordagem One-hot Encoding somente se uma feature categórica tiver apenas duas categorias diferentes. Se você deseja implementar o One-hot enconding em uma feature categórica que possui N categorias diferentes, é possível configurar o parâmetro one_hot_max_size como igual a N.
O CatBoost possui uma representação muito boa de dados categóricos. Ele utiliza conceitos do ordered boosting e aplica o mesmo a uma técnica chamada response coding (ou target encoding). No response coding, representamos cada feature categórica usando a média da coluna target de todos os pontos com aquele mesmo valor para a variável categórica. No entanto, podemos acabar representando o valor de uma variável usando seu rótulo. Isso leva a um problema denominado target leakage, isto é, usamos informação da variável que queremos prever para a construção das features. Já o CatBoost, para codificar uma instância de uma variável categórica, considera apenas os pontos anteriores a ela e calcula a média do target desses pontos com o mesmo valor dessa variável categórica. Abaixo temos um exemplo de como isso funciona na prática.
Digamos que temos o seguinte dataset (todos os pontos já ordenados no tempo):
Nós temos a Feature1, uma feature categórica com 3 diferentes categorias. Com o response coding, nós representaríamos nublado = (15 +14 +20+25) / 4 = 18.5. Isso realmente leva ao data leakage, porque estamos construindo uma feature de um ponto usando o target do mesmo ponto.
O CatBoost transforma todas as features categóricas sem qualquer data leakage. Ao invés de considerar todos os pontos, ele considera apenas os pontos anteriores a um determinado ponto. Assim, ele transforma as categorias em números usando a seguinte fórmula:
Aqui temos que:
- avg_target é o valor numérico da instância após a transformação
- countInClass é a soma do valor do target para instâncias com o valor atual da feature categórica
- prior é um valor preliminar para a feature
- totalCount é a quantidade de vezes que uma instância apareceu com o atual valor da feature categórica
No caso do nosso dataset, se deixarmos prior = 0.05, temos como exemplo:
- Na sexta-feira, nublado = (15 + 14 + 0.05) / 3 = 9.68
- No sábado, nublado = (15 + 14 + 20 + 0.05) / 3 = 12.26
- Na terça-feira, nublado = 0.05 / 2 = 0.025
Hiperparâmetros
Todos esses três algoritmos têm muitos parâmetros para ajustar, mas abordaremos apenas os importantes. Abaixo temos uma tabela com esses parâmetros de acordo com sua função e suas contrapartes nos diferentes modelos. Cabe ressaltar aqui que os parâmetros mais importantes são bem similares nos três, com leves alterações no nome, por exemplo, mas com a mesma funcionalidade.
Benchmarks
Abaixo mostraremos os resultados de alguns testes feitos para comparar a performance e o tempo de cada um dos algoritmos. Aqui vale ressaltar que os dois últimos exemplos foram executados em bases de dados que utilizamos na prática aqui na Datarisk.
Os testes foram executados em uma instância r5.8xlarge do Amazon EC2, com 256GB de RAM. A técnica utilizada para a otimização de hiperparâmetros em todos os casos foi um RandomSearch com 50 iterações cada.
Exemplo 1
Aqui temos um problema de regressão, onde a métrica de comparação é o R2. Basicamente, este coeficiente indica quanto o modelo foi capaz de explicar os dados coletados. O melhor score possível é 1.0 e ele pode ser negativo (porque o modelo pode ser arbitrariamente ruim). Um modelo constante que sempre prediz a média de y, não importando as features de input, terá um score R2de 0.0.
A base continha 20.640 linhas e 8 features ao todo, sendo usada a divisão treino/teste com 20% indo para o conjunto de teste.
Eis os resultados:
Exemplo 2
Aqui temos um problema de classificação, onde a métrica de comparação é o AUC. Caso o leitor não esteja familiarizado com o que essa métrica significa, recomendamos este post.
A base continha 83.602 linhas e 80 features ao todo, sendo usada a divisão treino/teste com 20% indo para o conjunto de teste.
Aqui temos variáveis categóricas na base, e com o intuito de comparar a heurística de tratamento de categóricas do CatBoost, para este modelo, fizemos dois testes: um passando os índices das features categóricas e outro tratando-as previamente com o RankCountVectorizer. Para o XGBoost e o LightGBM, também utilizamos o RankCountVectorizer.
Eis os resultados:
Exemplo 3
Aqui temos outro problema de classificação, onde novamente usamos o AUC como métrica de performance.
A base continha 83.623 linhas e 42 features ao todo, sendo usada a divisão treino/teste com 20% indo para o conjunto de teste.
Assim como no último exemplo, faremos a mesma comparação da abordagem do CatBoost em relação as categóricas, comparando-o com o RankCountVectorizer.
Eis aqui os resultados:
Comparando os resultados dos três testes, podemos fazer algumas observações.
- O LightGBM e o CatBoost normalmente têm sempre cerca de 4 ou 5 pontos de score a mais com os hiperparâmetros padrão comparado ao XGBoost.
- O tempo de treinamento do LightGBM é significativamente menor do que os outros dois (especialmente na otimização de hiperparâmetros).
- O XGBoost apresentou melhor performance após a otimização de hiperparâmetros (o que pode também ser causado pela grade de parâmetros testados para os três frameworks)
- A heurística de tratamento de variáveis categóricas do CatBoost não mostrou diferença significativa no desempenho final.
Por fim, devo dizer que essas observações são verdadeiras para esses conjunto de dados específicos, e podem ou não permanecer válidas para outros conjuntos de dados. No entanto, uma coisa que é verdade em geral é que o XGBoost é mais lento que os outros dois algoritmos, e o LightGBM é o mais rápido entre eles.
Deixamos aqui algumas dicas de como usufruir da melhor forma dos três modelos.
- Sem otimização de hiperparâmetros, o CatBoost normalmente é uma boa escolha, pois um dos objetivos de seu desenvolvimento é justamente esse (pelos nossos testes, o LightGBM também apresentou boa performance com os parâmetros padrão, então pelo seu tempo de treinamento baixo, pode ser uma boa escolha para essa situação também).
- Para fazer feature selection, feature engineering e otimização de hiperparâmetros, use o LightGBM.
- Ao final de tudo, use o pré-processamento e os hiperparâmetros que levaram a melhor performance e teste os três. Normalmente a performance é muito parecida, e qualquer leve ganho de score será bem-vindo.
Nos exemplos acima, fizemos testes executando o RandomSearch no LightGBM e depois usando os melhores hiperparâmetros obtidos, treinamos um XGBoost. No exemplo 1, obtivemos um R2 de 0,85038 (acima do que tínhamos para o LightGBM, mas abaixo do score obtido pelo XGBoost otimizado). No exemplo 2, obtivemos um AUC de 0,77612 (resultado pior do que qualquer um dos modelos otimizados). Por fim, no exemplo 3, obtivemos um AUC de 0,81891 (novamente acima do que tínhamos para o LightGBM, mas abaixo do score obtido pelo XGBoost otimizado). Isso é um bom indicativo de que após a otimização de hiperparâmetros em um modelo, ainda é válido testar os resultados nos outros, selecionando aquele com melhor performance.
Conclusão
E assim chegamos ao fim da nossa série sobre Gradient Boosting. Saímos de uma explicação introdutória sobre métodos de ensemble learning, passando por todo o processo de construção de árvores no XGBoost (e nos outros modelos de boosting baseado em árvores no geral) e chegamos na comparação entre os três principais algoritmos de boosting no momento.
Agradecemos a atenção e até a próxima!
PARTE 1: Métodos de Ensemble Learning
PARTE 2: XGBoost
