Besoin d'aide pour comprendre la proposition approximative de points de partage de xgboost

12

Contexte:

dans xgboost, l' itération tente d'ajuster un arbre sur tous les exemples, ce qui minimise l'objectif suivant:f t ntftn

i=1n[gift(xi)+12hift2(xi)]

où sont des premier ordre et de second ordre sur notre meilleure estimation précédente (à partir de l'itération ):y t - 1gi,hiy^t1

  • gi=dy^l(yi,y^)
  • hi=dy^2l(yi,y^)

et est notre fonction de perte.l


La question (enfin):

Lors de la construction de et de l'examen d'une caractéristique spécifique dans une division spécifique, ils utilisent l'heuristique suivante pour évaluer uniquement certains candidats de division: ils trient tous les exemples par leur , passent sur la liste triée et additionnent leur deuxième dérivée . Ils considèrent un candidat divisé uniquement lorsque la somme change plus de . Pourquoi donc??? k x k h i ϵftkxkhiϵ

L'explication qu'ils me donnent m'échappe:

Ils prétendent que nous pouvons réécrire l'équation précédente comme suit:

i=1n12hi[ft(xi)gi/hi]2+constant

et je ne parviens pas à suivre l'algèbre - pouvez-vous montrer pourquoi est-elle égale?

Et puis ils affirment que "c'est exactement la perte au carré pondérée avec les étiquettes et les poids " - une déclaration avec laquelle je suis d'accord, mais je ne comprends pas comment cela se rapporte à l'algorithme de fractionnement candidat qu'ils utilisent ...h igi/hihi

Merci et désolé si c'est trop long pour ce forum.

ihadanny
la source

Réponses:

8

Je n'entrerai pas dans les détails mais ce qui suit devrait vous aider à saisir l'idée.

Ils utilisent Quantiles (Wikipedia) pour déterminer où se diviser. Si vous avez 100 points de partage possibles, (triés), vous pouvez essayer les points de partage de quantiles et ont déjà une bonne approximation. C'est ce que fait le paramètre . Ils considèrent un point de partage lorsque le partage a plus de points en dessous que le dernier point de partage. Si , vous vous retrouverez avec points de partage, étant plus grand que des autres points. Ils n'envisagent pas une nouvelle scission lorsque "la somme change de plus de{x1,,x100}10{x10,x20,,x90}ϵϵNϵ=0.01100{1%,2%,...,99%}ϵ "mais lorsque le nombre de points sous le point actuel est plus grand de que le dernier.ϵ

Maintenant, si vous avez beaucoup de points continus qui sont déjà bien classés, il pourrait être inutile de les partager. Vous souhaitez diviser les parties de votre ensemble de données qui sont très erronées, celles qui sont difficiles à apprendre. Pour ce faire, ils utilisent des quantiles pondérés. C'est là que les poids jouent un rôle. Le premier -quantile ne sera pas le premier point supérieur à des points, mais le premier point supérieur à des poids.1010%10%

Clins d'oeil
la source
Je me suis connecté juste pour vous donner un vote positif. Merci pour l'explication facile à saisir.
Pakpoom Tiwakornkit
3

Il suffit d'ajouter la partie algébrique à la réponse @Winks:

La deuxième équation devrait avoir son signe inversé, comme dans:

i=1n12hi[ft(xi)(gi/hi)]2+constant=i=1n12hi[ft2(xi)+2ft(xi)gihi+(gi/hi)2]=i=1n[gift(xi)+12hift2(xi)+gi22hi]

Le dernier terme est en effet constant: rappelez-vous que les et sont déterminés par l'itération précédente, ils sont donc constants lorsque vous essayez de définir .gihift

Donc, maintenant, nous pouvons affirmer que "c'est exactement la perte au carré pondérée avec les étiquettes et les poids "gi/hihi

Nous remercions Yaron et Avi de mon équipe de m'avoir expliqué cela.

ihadanny
la source
0

Et puis ils affirment que "c'est exactement la perte au carré pondérée avec les étiquettes gi / higi / hi et les poids hihi" - une déclaration avec laquelle je suis d'accord, mais je ne comprends pas comment cela se rapporte à l'algorithme de fractionnement candidat qu'ils utilisent .. .

  1. S'il n'y a qu'un seul échantillon et que vous optimisez le à l' itération , il est facile de voir que la valeur serait , expliquantwtthw=gi/hi(ft(gi/hi))2

  2. Vous disposez maintenant d'un ensemble de données complet. Dans le cas où la fonction de perte a une dérivée seconde identique, le deviendrait au lieu de . Je l'ai écrit de cette façon parce que dans ce cas, le ne serait pas pertinent pour la différence de entre les échantillons, car il n'y a pas de différence. Cependant, en réalité, lorsque reste inchangé, le fluctue avec la distribution de .wavg(gi)/constsigma(gi)/sigma(hi)whigiwhi

Je pense que cela explique pourquoi cela fonctionne car il est pondéré par .hi

xy.Z
la source