Dando continuidade a nossa série de posts sobre os gradient boosting, falaremos hoje sobre o XGBoost (Extreme Gradient Boosting), algoritmo extremamente conhecido no meio de machine learning. Explicaremos aqui sobre como o algoritmo constrói as árvores de decisão em cada iteração. Assumiremos aqui que o leitor já tem conhecimentos sobre os métodos de ensemble learning, falados na parte 1 dessa série. Caso você não tenha visto, basta clicar aqui. Além disso, assumimos que você está familiarizado com os conceitos de regularização. Caso queira uma introdução ao assunto, recomendamos esse post.
Para explicar o processo de construção de árvores, vamos usar um exemplo de como o XGBoost funciona para a regressão. Após a explicação, veremos as diferenças no caso de problemas de classificação.
Sem mais delongas, vamos à explicação!
Construção de árvores para regressão
Vamos começar aprendendo sobre como o XGBoost constrói as árvores de decisão. Para isso, vamos usar um exemplo de um problema de regressão, com dados extremamente simples, como podemos ver na figura abaixo.
No eixo x, temos diferentes dosagens de um remédio, enquanto no eixo y, medimos a efetividade do remédio. Existem duas observações com alta efetividade, o que significa que o remédio foi útil. Já as duas observações com baixa efetividade representam exemplos onde o remédio foi mais prejudicial do que benéfico.
O primeiro passo no processo de treinamento do XGBoost é fazer uma predição inicial. Esta predição pode ser qualquer coisa, mas por padrão ela é 0.5, tanto para os problemas de regressão quanto para os problemas de classificação. Vale dizer aqui que o parâmetro base_score controla essa predição inicial, então editando esse valor, podemos mudar essa predição de 0.5.
A predição, 0.5, corresponde a esta linha preta contínua na imagem acima. Para cada amostra, temos um resíduo, isto é, a diferença entre o valor observado e o predito, que nos mostra o quão boa a predição inicial é. Na imagem eles estão representados pelas linhas pretas pontilhadas. Agora, assim como o Gradient Boosting, o XGBoost treina uma árvore de decisão para os resíduos.
Então vamos falar sobre como construir uma árvore para regressão. Note que existem várias maneiras de construir essas árvores. Neste post falaremos da maneira mais comum de construí-las para regressão.
Cada árvore começa com uma única folha, e todos os resíduos vão para essa folha.
Agora, calculamos um score de qualidade, ou score de similaridade, para os resíduos. Este score de similaridade é dado por:
OBS: λ (lambda) é um parâmetro de regularização, e falaremos sobre ele mais a frente. Por enquanto, vamos dizer que λ=0.
Então colocamos todos os resíduos no numerador, e como há 4 resíduos na folha, colocamos 4 no denominador.
Então, o score de similaridade para os resíduos nessa folha é 4.
Observe que como não elevamos ao quadrado os resíduos antes de somarmos eles juntos no numerador, 7.5 e -7.5 se cancelarão. Em outras palavras, quando colocamos uma amostra acima da linha de predição com uma amostra abaixo da linha predição juntas na mesma folha, a soma dos seus resíduos tendem a se cancelar.
Agora a questão é se conseguimos uma maneira melhor de agrupar resíduos similares se dividirmos em dois grupos.
Para responder isso, primeiro focamos nas duas observações com as dosagens mais baixas.
Digamos que a média entre elas é 15, representada acima pela linha vermelha. Então dividimos as observações em dois grupos, baseado em quando uma amostra tem “dosagem < 15” ou não.
A observação mais a esquerda é a única com dosagem menor do que 15, então seu resíduo vai na folha da esquerda. Todos os outros resíduos vão para a folha da direita. Agora calculamos os scores de similaridade para as duas folhas, seguindo o mesmo procedimento mostrado antes, obtendo 110.25 para a folha da esquerda e 14.08 para a folha da direita.
Observe que quando os residuais em um nó são muito diferentes, eles se cancelam, fazendo o score de similaridade ser mais baixo. Em contraste, quando os resíduos são similares, ou há apenas um deles no nó, não há cancelamento, e o score de similaridade se torna mais alto.
Agora precisamos quantificar o quão melhor é termos essa divisão de folhas comparadas a quando todas estavam na raíz. Fazemos isso calculando o ganho de dividir os resíduos em dois grupos, que é dado por:
Nesse caso, temos um ganho de 120.33.
Agora que calculamos o ganho para o threshold “dosagem < 15”, o comparamos com o ganho para os outros thresholds.
Então deslocamos o threshold para que agora ele seja a média entre as próximas duas observações, e construímos uma árvore que divide as observações para o novo threshold, que é “dosagem < 22.5”.
Calculamos então os scores de similaridade para as folhas ( 8 para a esquerda e 0 para a direita) e depois o ganho.
Nesse caso, o ganho é igual a 4. Como esse ganho para “dosagem < 22.5” (ganho = 4) é menor que o ganho para “dosagem < 15” (ganho = 120.33), “dosagem < 15” é melhor dividindo os resíduos em clusters com valores similares.
Então, novamente deslocamos o threshold para que seja a média das próximas duas observações, e construímos uma árvore que divide as observações para o novo threshold, que é “dosagem < 30”.
Calculamos então os scores de similaridade para as folhas ( 4.08 para a esquerda e 56.25 para a direita) e depois o ganho.
Nesse caso, o ganho é igual a 56.33. Novamente, como o ganho para “dosagem < 30” (ganho = 56.33) é menor que o ganho para “dosagem < 15” (ganho = 120.33), “dosagem < 15” é melhor em dividir as observações. E como não podemos deslocar mais o threshold para a direita, já comparamos todos os thresholds diferentes possíveis, e usaremos então o threshold que nos dá o maior ganho, “dosagem < 15”, para o primeiro ramo na árvore.
Agora, como temos apenas um resíduo na folha da esquerda, não podemos dividi-la mais. No entanto, podemos dividir os três resíduos na direita. Repetindo o processo de escolha de thresholds descrito anteriormente, veremos que o melhor threshold nesse caso será “dosagem < 30”, fornecendo um ganho de 140.17.
Para manter o exemplo simples, vamos limitar a profundidade da árvore em dois níveis, o que significa que não iremos mais dividir as folhas, e esta árvore está completa. Vale ter em mente aqui que o parâmetro padrão é as árvores terem 6 níveis de profundidade.
Note que todos esses parâmetros comentados até aqui são customizáveis. Normalmente, controlamos a profundidade das árvores, os parâmetros de regularização, o número de estimadores, etc. Além disso, usamos algum critério de otimização de hiperparâmetros como o grid search ou o random search, por exemplo, de modo a maximizar a escolher os parâmetros que levam a um modelo com a maior performance possível no final.
Agora precisamos falar sobre o processo de pruning, ou em português, podagem. Como sabemos, métodos de ensemble podem facilmente levar ao problema de overfitting, visto a complexidade dos modelos. O pruning é um processo que visa evitar o overfitting, diminuindo o tamanho das árvores, e consequentemente, reduzindo a complexidade.
Nós podamos uma árvore do XGBoost baseado nos seus ganhos. Iniciamos tomando um valor, digamos por exemplo, 130. Este será mais um parâmetro de regularização, e o XGBoost chama este número de γ (gamma). Calculamos então a diferença entre o ganho associado ao ramo mais baixo na árvore e o valor γ. Se a diferença entre o ganho e o γ for negativa, removemos o ramo. Se for positiva, não removemos o ramo.
Nesse caso, a diferença entre o ganho (140.17) e gamma (130) é positiva, então não removemos esse ramo, e nenhum dos ramos acima deste. Desse modo, como essa árvore tem apenas duas divisões, terminamos o processo de podagem.
Note que o ganho para o primeiro ramo, 120.33, é menor que 130, o valor de gamma, então a diferença será negativa. Mas como não removemos o primeiro ramo, não removeremos a raíz. Caso configurássemos γ= 150, removeríamos os dois ramos, e tudo o que teríamos seria a predição original, o que é um caso extremo de podagem.
Agora vamos voltar aos resíduos iniciais, mas desta vez, quando calcularmos os scores de similaridade, vamos configurar λ=1. Lembre-se que o lambda é um parâmetro de regularização, o que significa que a intenção dele é reduzir a sensitividade das predições a observações individuais. O score de similaridade para a raíz é então:
Ou seja, obtemos um score de 3.2, o que é 80% do que tínhamos quando λ=0.
Quando calculamos os scores de similaridade para as folhas, obtemos 55.12 para a folha da esquerda (metade do que tínhamos antes) e 10.56 para a folha da direita (¾ do que tínhamos antes).
Notamos então que quando λ>0, os scores de similaridade são menores, e a quantidade de decréscimo é inversamente proporcional ao número de resíduos no nó. Em outras, palavras, a folha na esquerda tinha apenas um resíduo, e obteve o maior decréscimo no score de similaridade, 50%. Em contraste, a raíz tinha todos os quatro resíduos, e teve o menor decréscimo, 20%.
Agora quando nós calculamos o ganho, obtemos 62.48, o que é bem menor do que o ganho de 120.33 de quando λ=0. Similarmente, o ganho do próximo ramo “dosagem < 30” também é menor do que antes.
Agora, para efeitos de comparação, esses são os valores dos ganhos quando λ=0.
Quando falamos sobre podagem, configuramos primeiro γ=130, e como para o ramo mais profundo na primeira árvore, a diferença entre o ganho e a gamma era positiva, não podamos a árvore em nenhum momento.
Agora, com λ=1, os valores para o ganho dos dois ramos são menores que 130, o que nos faria podar a árvore inteira.
Então, quando λ>0, é mais fácil podar as folhas porque os valores para o ganho são menores.
Por agora, vamos assumir que esta é a árvore com a qual estamos trabalhando.
Vamos agora mostrar como calcular os valores de output para as folhas. O valor de output de uma folha é dado por:
Note que o valor de output é como o score de similaridade, exceto que nós não elevamos ao quadrado a soma dos resíduos.
Tomando como exemplo a folha com o resíduo -10.5, se λ=0, o output será igual a -10.5, mas se λ=1, o output será igual a -5.25. Em outras palavras, quando λ>0, ele irá reduzir a quantidade que uma folha individual adiciona na predição total. Então, λ, o parâmetro de regularização, vai reduzir a sensitividade da predição a observação individual. Por agora, vamos manter as coisas simples e deixar λ=0, porque esse é o valor padrão. Calculando os valores de output para cada uma das folhas, temos:
Repare que quando λ=0, o output de uma folha é simplesmente a média de seus resíduos.
Agora, depois de calcular os outputs de cada folha, finalmente a primeira árvore está completa.
Já que construímos nossa primeira árvore, podemos fazer novas predições.
E assim como o Gradient Boosting, XGBoost faz as novas predições com a predição inicial mais o output da árvore vezes uma learning rate (taxa de aprendizado).
Se você não sabe porque usamos essa learning rate, aqui vai uma explicação rápida. Basicamente todos os modelos de machine learning, no final, são treinados para minimizar uma função de perda. A função de perda é uma penalidade por uma má previsão, sendo uma uma medida de quão bom um modelo de previsão faz em termos de ser capaz de prever o resultado esperado. Com o objetivo de minimizar essa função de perda, normalmente usamos o chamado método do gradiente. Esse método, para encontrar um mínimo local de uma função usa-se um esquema iterativo, onde em cada passo se toma a direção a qual a função mais decresce. A learning rate é o que determina o tamanho do passo em cada iteração enquanto se move para um mínimo dessa função de perda. É como tentar encontrar o ponto mais baixo de uma montanha a noite. Para fazer isso, a cada momento você deve dar um pequeno passo na direção onde tem o maior declive. Como a learning rate influencia até que ponto as informações recém-adquiridas substituem as informações antigas, ela metaforicamente representa a velocidade com que um modelo de machine learning “aprende”.
Ao definir uma taxa de aprendizado, há um trade-off entre a taxa de convergência e um “overshooting”. Uma taxa de aprendizado muito alta fará com que o aprendizado salte sobre os mínimos, mas uma taxa de aprendizado muito baixa levará muito tempo para convergir ou ficará presa em um mínimo local indesejável. Abaixo temos uma figura que ilustra o que acabou de ser explicado.
O XGBoost chama a learning rate de ε(eta), e seu valor padrão é 0.3, então é esse que iremos usar.
Então, para a observação mais à esquerda no eixo x, com dosagem = 10, a nova predição será igual a predição inicial, 0.5, mais a learning rate, ε(eta), 0.3, vezes o output da folha, -10.5. Logo, 0.5 + (0.3 * -10.5) = -2.65.
Logo, vemos que o novo resíduo é menor do que antes, então acabamos de dar um pequeno passo na direção certa.
Similarmente, para as outras observações, teremos as seguintes novas predições.
Assim como a primeira, as novas predições para as observações restantes têm resíduos menores do que antes, sugerindo que cada pequeno passo foi dado na direção certa.
Agora construímos uma nova árvore baseada nos novos resíduos, e fazemos novas predições que nos dão resíduos menores:
E então continuamos construindo árvores até que os resíduos sejam menores que um certo limite, ou até que tenhamos atingido o número máximo de árvores.
E é assim que o XGBoost constrói as árvores para um problema de regressão.
Construção de árvores para classificação
O modo como as árvores do XGBoost são construídas para os problemas de classificação é bem similar ao modo como são feitas para a regressão. Existem três principais diferenças:
- O score de similaridade de uma folha agora é dado por:
Nesse caso, i representa cada resíduo de uma folha. Aqui vale lembrar que em problemas de classificação, cada predição é a probabilidade daquela observação pertencer à classe positiva. Então, quando construímos a árvore, usamos a probabilidade da predição anterior daquela amostra.
2. O output de uma folha agora é dado por:
Novamente, o output da folha é quase igual ao score de similaridade, com a diferença de que os resíduos não são elevados ao quadrado depois de somados.
3. Para atualizar as predições, precisamos converter a probabilidade anterior para um valor da log (odds), atualizar o valor da log (odds), e então converter o valor para uma probabilidade, isto é, um valor entre 0 e 1.
Caso o leitor não esteja familiarizado, aqui vão algumas definições.
Se um dado evento A tem a probabilidade p de ocorrer, definimos a chance (odds) do evento ocorrer como:
Tomando a probabilidade de um ponto x ter classe positiva como p = P(y = 1), temos então que:
Dessa forma, temos que a função logit está intimamente relacionada com a chance de um evento ocorrer.
Agora que temos um número real, podemos estimá-lo usando um regressor f qualquer. Lembrando que para classificar um ponto queremos estimar o probabilidade de y = 1, temos:
σ é a inversa de logit, também chamada de função sigmoide ou logística, definida por:
Essa função é definida para todos os números reais, e sua imagem, isto é, os valores que ela pode assumir, ficam entre 0 e 1.
Dessa maneira, para atualizar a probabilidade de uma amostra conforme construímos as árvores, fazemos o seguinte processo:
- Calculamos a log(odds) anterior ou logit(p) da probabilidade anterior
- Atualizamos a log(odds) por meio da fórmula:
3. Então, calculamos a nova probabilidade aplicando a função logística em log(odds):
Cabe ressaltar aqui que existe uma justificativa matemática por trás de cada cálculo de ganho e de score de similaridade, e por que são diferentes nos modelos de regressão e de classificação. Caso você se interesse, recomendamos esse vídeo.
Conclusão
Chegamos ao fim do nosso segundo post sobre a série de Gradient Boosting. Esperamos que tenha ficado claro como o XGBoost é treinado e como ele faz suas predições.
No próximo post falaremos sobre o LightGBM e o CatBoost, dois outros algoritmos de boosting muito populares também. Mostraremos suas principais diferenças, comparando-os com o XGBoost e mostrando alguns benchmarks do desempenho de cada modelo.
Agradecemos a atenção e até a próxima!
PARTE 1: Métodos de Ensemble Learning
PARTE 3: XGBoost vs LightGBM vs CatBoost
Cientista de dados
