Função de perda XGBoost Aproximação com expansão de Taylor

28

Como exemplo, assumir a função objetivo do modelo XGBoost no 'th iteração:t

L(t)=i=1n(yi,y^i(t1)+ft(xi))+Ω(ft)

onde é a função de perda, é o 'th saída de árvore e é a regularização. Uma das (muitas) etapas principais para o cálculo rápido é a aproximação:fttΩ

L(t)i=1n(yi,y^i(t1))+gtft(xi)+12hift2(xi)+Ω(ft),

onde e são a primeira e a segunda derivadas da função de perda.gihi

O que estou pedindo é argumentos convincentes para desmistificar por que a aproximação acima funciona:

1) Como o XGBoost com a aproximação acima se compara ao XGBoost com a função de objetivo completo? Que comportamento potencialmente interessante de ordem superior se perde na aproximação?

2) É um pouco difícil de visualizar (e depende da função de perda), mas, se a função de perda tiver um componente cúbico grande, a aproximação provavelmente falhará. Como é que isso não causa problemas para o XGBoost?

Alex R.
fonte

Respostas:

62

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
  • Param1:M
    • Calcular pseudo-resíduosrim=(yi,Hm1(xi))Hm1(xi)
    • Encaixe um aluno de base nos pseudo-resíduoshm(x)
    • Calcule o multiplicador que minimiza o custo, , (usando a pesquisa de linha)γγ=argminγi=1N(yi,Hm1(xi)+γhm(xi))
    • Atualize o modelo .Hm(x)=Hm1(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,Hm1(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=argmaxhmi=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,Hm1(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 serf(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

    xc(i+1)=x(i)cf(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(xc(i+1))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+122f(x)x2a2+=n=01n!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)n=0k1n!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^i(t1))constant+giconstantft(xi)+12hiconstantft2(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

Winks
fonte
2
+1. Devo confessar que ainda não li essa resposta (ainda?) E não posso julgá-la de qualquer maneira porque está fora dos meus conhecimentos, mas parece tão impressionante que fico feliz em votar. Bem feito [parece]!
Ameba diz Reinstate Monica
Essa foi uma excelente resposta. O algoritmo de aumento de gradiente ajusta uma árvore de regressão ao gradiente negativo com o critério de divisão mse. Como a estrutura da árvore é determinada no XGBoost ??
precisa saber é
Você acertou em cheio a resposta, bom trabalho!
Marcin Zablocki 23/07