Esta é uma questão muito interessante. Para entender completamente o que estava acontecendo, eu tive que passar pelo que o XGBoost está tentando fazer e por outros métodos que tínhamos em nossa caixa de ferramentas para lidar com isso. Minha resposta aborda os métodos tradicionais e como / por que o XGBoost é uma melhoria. Se você deseja apenas os pontos de bala, há um resumo no final.
Reforço tradicional do gradiente
Considere o algoritmo tradicional de aumento de gradiente (Wikipedia) :
- Modelo básico deH0
- Param←1:M
- Calcular pseudo-resíduosrim=−∂ℓ(yi,Hm−1(xi))∂Hm−1(xi)
- Encaixe um aluno de base nos pseudo-resíduoshm(x)
- Calcule o multiplicador que minimiza o custo, , (usando a pesquisa de linha)γγ=argminγ∑Ni=1ℓ(yi,Hm−1(xi)+γhm(xi))
- Atualize o modelo .Hm(x)=Hm−1(x)+γhm(x)
- Você recebe seu modelo .HM(x)
A aproximação da função é importante para a parte seguinte,
Encaixe um aluno de base nos pseudo-resíduos.hm(x)
Imagine você onde construir seu algoritmo de aumento de gradiente ingenuamente. Você criaria o algoritmo acima usando árvores de regressão existentes como alunos fracos. Vamos supor que você não tenha permissão para ajustar a implementação existente dos alunos fracos. No Matlab , o critério de divisão padrão é o erro médio quadrático. O mesmo vale para o scikit learn .
Você está tentando encontrar o melhor modelo que minimize o custo . Mas, para fazer isso, você está ajustando um modelo de regressão simples aos resíduos usando o MSE como função objetivo. Observe que você não está minimizando diretamente o que deseja, mas usando os resíduos e o MSE como proxy para fazer isso. A parte ruim é que ela não produz necessariamente a solução ideal. A parte boa é que funciona.hm(x)ℓ(yi,Hm−1(xi)+hm(xi))
Descida tradicional de gradiente
Isso é análogo ao tradicional Gradient Descent (Wikipedia) , onde você está tentando minimizar uma função de custo seguindo o gradiente (negativo do) da função, a cada passo.f(x)−∇f(x)
x(i+1)=x(i)−∇f(x(i))
Não permite encontrar o mínimo exato após um passo, mas cada passo o aproxima do mínimo (se a função for convexa). Essa é uma aproximação, mas funciona muito bem e é o algoritmo que tradicionalmente usamos para fazer uma regressão logística, por exemplo.
Interlúdio
Nesse ponto, o que se deve entender é que o algoritmo geral de aumento de gradiente não calcula a função de custo para cada divisão possível, usa a função de custo do aluno fraco de regressão para ajustar os resíduos.ℓ
O que sua pergunta parece sugerir é que o "XGBoost verdadeiro" deve calcular a função de custo para cada divisão e que o "XGBoost aproximado" está usando uma heurística para aproximar isso. Você pode ver dessa maneira, mas historicamente, tivemos o algoritmo geral de aumento de gradiente, que não usa informações sobre a função de custo, exceto a derivada no ponto atual. O XGBoost é uma extensão do Gradient Boosting que tenta ser mais inteligente sobre o crescimento das árvores de regressão fracas, usando uma aproximação mais precisa do que apenas o gradiente.
Outras maneiras de escolher o melhor modelohm(x)
Se dermos uma olhada no AdaBoost como um caso especial de aumento de gradiente, ele não seleciona regressores, mas classificadores como alunos fracos. Se , a maneira como o AdaBoost seleciona o melhor modelo é encontrarhm(x)∈{−1,1}
hm=argmaxhm∑i=1Nwihm(xi)
onde são os resíduos ( origem, começa no slide 20 ). O raciocínio para o uso dessa função objetivo é que, se e vão na mesma direção / têm o mesmo sinal, o ponto está se movendo na direção certa e você está tentando maximizar a quantidade máxima de movimento em a direção certa.wiwihm(xi)
Porém, mais uma vez, isso não está medindo diretamente o que minimiza . Ele está medindo o quão bom é o movimento , com respeito à direção geral que você deve seguir, conforme medido com os resíduos , que também são uma aproximação. Os resíduos indicam em que direção você deve se mover pelo sinal deles e aproximadamente pela magnitude, mas eles não informam exatamente onde você deve parar.hmℓ(yi,Hm−1(xi)+hm(xi))hmwi
Melhor descida de gradiente
Os próximos três exemplos não são essenciais para a explicação e estão aqui apenas para apresentar algumas maneiras de fazer melhor do que uma descida em gradiente de baunilha, para apoiar a idéia de que o que o XGBoost faz é apenas outra maneira de melhorar a descida em gradiente. Em uma configuração tradicional de descida de gradiente, ao tentar minimizar , é possível fazer melhor do que apenas seguir o gradiente. Muitas extensões foram propostas (Wikipedia) . Aqui estão alguns deles, para mostrar que é possível fazer melhor, considerando mais tempo de computação ou mais propriedades da função .f(x)f
Pesquisa de linha / retrocesso: na descida do gradiente, uma vez calculado o gradiente , o próximo ponto deve ser−∇f(x(i))
x(i+1)=x(i)−∇f(x(i))
Mas o gradiente fornece apenas a direção na qual se deve mover, não realmente "quanto", para que outro procedimento possa ser usado, para encontrar o melhor modo quec>0
x(i+1)c=x(i)−c∇f(x(i))
minimiza a função de custo. Isso é feito avaliando para alguns , e como a função deve ser convexa, é relativamente fácil fazer isso através da Pesquisa de linha (Wikipedia) ou Pesquisa de linha de retorno (Wikipedia) . Aqui, o principal custo é a avaliação . Portanto, essa extensão funciona melhor se for fácil de calcular. Observe que o algoritmo geral para aumentar o gradiente usa a pesquisa de linhas, como mostrado no início da minha resposta.f(x(i+1)c)cff(x)f
Método do gradiente proximal rápido: se a função de minimizar é fortemente convexa e seu gradiente é suave ( Lipschitz (Wikipedia) ), então há algum truque usando essas propriedades que aceleram a convergência.
Descida do gradiente estocástico e o método Momentum: Na descida do gradiente estocástico, você não avalia o gradiente em todos os pontos, mas apenas em um subconjunto desses pontos. Você dá um passo, calcula o gradiente em outro lote e continua. A descida estocástica de gradiente pode ser usada porque o cálculo de todos os pontos é muito caro, ou talvez todos esses pontos nem se encaixem na memória. Isso permite que você execute mais etapas, mais rapidamente, mas com menos precisão.
Ao fazer isso, a direção do gradiente pode mudar dependendo de quais pontos são amostrados. Para combater esse efeito, os métodos de momento mantêm uma média móvel da direção de cada dimensão, reduzindo a variação em cada movimento.
A extensão mais relevante para a descida do gradiente em nossa discussão sobre o XGBoost é o método de Newton (Wikipedia) . Em vez de apenas calcular o gradiente e segui-lo, ele usa a derivada de segunda ordem para reunir mais informações sobre a direção em que deve seguir. Se usarmos descida gradiente, teremos que a cada iteração, atualizaremos nosso ponto seguinte forma,x(i)
x(i+1)=x(i)−∇f(x(i))
E como o gradiente aponta para a direção do maior aumento em , seus pontos negativos na direção da maior diminuição, e esperamos que . Isso pode não ser válido, pois podemos ir muito longe na direção do gradiente (daí a extensão de pesquisa de linha), mas é uma boa aproximação. No método de Newton, atualizamos seguinte forma:∇f(x(i))ff(x(i+1))<f(x(i))x(i)
x(i+1)=x(i)−∇f(x(i))Hessf(x(i))
Onde é o hessiano de em . Esta atualização leva em consideração as informações de segunda ordem; portanto, a direção não é mais a direção da diminuição mais alta, mas deve apontar com mais precisão para modo que (ou o ponto em que é mínimo, se não houver zero). Se é um polinômio de segunda ordem, o método de Newton, associado a uma pesquisa de linha, deve ser capaz de encontrar o mínimo em uma etapa.Hessf(x)fxx(i+1)f(x(i+1))=0ff
O método de Newton contrasta com a descida do gradiente estocástico. Na descida estocástica do gradiente, usamos menos pontos para levar menos tempo para calcular a direção que devemos seguir, a fim de fazer mais deles, na esperança de chegarmos mais rapidamente. No método de Newton, levamos mais tempo para calcular a direção em que queremos seguir, na esperança de que precisamos dar menos passos para chegar lá.
Agora, a razão pela qual o método de Newton funciona é a mesma pela qual a aproximação do XGBoost funciona e depende da expansão de Taylor (Wikipedia) e do teorema de Taylor (Wikipedia) . A expansão de Taylor (ou série de Taylor) de uma função no ponto éf(x+a)
f(x)+∂f(x)∂xa+12∂2f(x)∂x2a2+⋯=∑n=0∞1n!∂nf(x)∂xnan.
Observe a semelhança entre esta expressão e a aproximação que o XGBoost está usando. O Teorema de Taylor afirma que se você interromper a expansão na ordem , então o erro ou a diferença entre e , é, no máximo, , onde é uma função com a propriedade agradável que ele vai para zero, como vai a zero.kf(x+a)∑kn=01n!∂nf(x)∂xnanhk(x)akhka
Se você deseja uma visualização de quão bem ela aproxima algumas funções, dê uma olhada nas páginas da Wikipedia, elas têm alguns gráficos para a aproximação de funções não polinomiais como , .exlog(x)
O que deve ser observado é que a aproximação funciona muito bem se você deseja calcular o valor de na vizinhança de , ou seja, para alterações muito pequenas . É isso que queremos fazer no Boosting. É claro que gostaríamos de encontrar a árvore que faz a maior mudança. Se os alunos fracos que construímos são muito bons e querem fazer uma mudança muito grande, podemos arbitrariamente impedir isso aplicando apenas oufxa0.10.01do seu efeito. Esse é o tamanho da etapa ou a taxa de aprendizado da descida do gradiente. Isso é aceitável, porque se nossos alunos fracos estão obtendo soluções muito boas, isso significa que o problema é fácil; nesse caso, acabaremos com uma boa solução de qualquer maneira, ou estaremos super adaptados, então vamos um pouco ou muito muita coisa nessa direção ruim não muda o problema subjacente.
Então, o que o XGBoost está fazendo e por que funciona?
O XGBoost é um algoritmo de aumento de gradiente que constrói árvores de regressão como alunos fracos. O algoritmo tradicional de aumento de gradiente é muito semelhante a uma descida de gradiente com uma pesquisa de linha, em que a direção na qual se deve traçar os alunos fracos disponíveis. A implementação ingênua do Gradient Boosting usaria a função de custo do aluno fraco para ajustá-lo ao residual. Esse é um proxy para minimizar o custo do novo modelo, que é caro para calcular. O que o XGBoost está fazendo é criar uma função de custo personalizada para caber nas árvores, usando a série Taylor da ordem dois como uma aproximação para a função de custo real, para que possa ter mais certeza de que a árvore escolhida é boa. A esse respeito, e como uma simplificação, o XGBoost é aumentar o gradiente do que o método de Newton é o gradiente de descida.
Por que eles construíram dessa maneira
Sua pergunta sobre o porquê do uso dessa aproximação resulta em uma troca de custo / desempenho. Essa função de custo é usada para comparar possíveis divisões para árvores de regressão; portanto, se nossos pontos tiverem 50 características, com uma média de 10 valores diferentes, cada nó tem 500 possíveis divisões, portanto, 500 avaliações da função. Se você soltar um recurso contínuo, o número de divisões explodirá e a avaliação da divisão será chamada cada vez mais (o XGBoost tem outro truque para lidar com os recursos contínuos, mas isso está fora do escopo). Como o algoritmo passa a maior parte do tempo avaliando divisões, a maneira de acelerar o algoritmo é acelerar a avaliação em árvore.
Se você avaliou a árvore com a função de custo total, , é um novo cálculo para cada nova divisão. Para fazer a otimização no cálculo da função de custo, você precisa ter informações sobre a função de custo, que é o ponto principal do Gradient Boosting: ele deve funcionar para todas as funções de custo.ℓ
A aproximação de segunda ordem é computacionalmente agradável, porque a maioria dos termos é a mesma em uma determinada iteração. Para uma determinada iteração, a maior parte da expressão pode ser calculada uma vez e reutilizada como constante para todas as divisões:
L(t)≈∑i=1nℓ(yi,y^(t−1)i)constant+giconstantft(xi)+12hiconstantf2t(xi)+Ω(ft),
Portanto, a única coisa que você precisa calcular é e , e o que resta são principalmente adições e algumas multiplicações. Além disso, se você der uma olhada no artigo do XGBoost (arxiv) , verá que eles usam o fato de estarem construindo uma árvore para simplificar ainda mais a expressão até um monte de soma de índices, o que é muito, muito rápido.ft(xi)Ω(ft)
Sumário
Você pode ver o XGBoost (com aproximação) como uma regressão da solução exata, uma aproximação do "verdadeiro XGBoost", com avaliação exata. Mas como a avaliação exata é tão cara, outra maneira de ver é que, em enormes conjuntos de dados, a aproximação é tudo o que podemos fazer realisticamente, e essa aproximação é mais precisa do que a aproximação de primeira ordem que um algoritmo de aumento de gradiente "ingênuo" faria. .
A aproximação em uso é semelhante ao Método de Newton , e é justificada por Taylor Series (Wikipedia) e Taylor Theorem (Wikipedia) .
De fato, informações de ordem superior não são completamente usadas, mas não são necessárias, porque queremos uma boa aproximação na vizinhança de nosso ponto de partida .
Para visualização, consulte a página da Wikipedia de Taylor Series / Teorema de Taylor , ou a Academia Khan sobre aproximação de Taylor Series , ou a página MathDemo sobre aproximação polinomial de não-polinômios