Zenn
📝

Gradient Boost Modelにおける多クラス分類の目的関数について

2024/02/18に公開
#
xgboost
#
gbdt
tech

概要

本稿ではgradient boosting modelによるMulti classの分類問題に関する以下の内容について説明する。

  1. 目的関数がsoftmaxの場合のgradientとhessianの導出過程について
  2. soft-labelの場合の拡張について
  3. LightGBM, XGBoostの組み込みの多クラス分類の目的関数では、hessianにある乗数が乗じられていること

前提知識

本稿の内容を理解するための前提知識は以下:

  1. Gradient Boosting ModelがどのようにDecision Treeのパラメータを学習するかについての知識[9]
  2. 多変数関数の（偏）微分の計算方法

経緯

XGBoostのカスタムobjectiveについての公式のチュートリアル[2,3]を見るとmulti:softprobの模擬実装が掲載されている。ここではpointwiseのgradientおよびHessianは以下のように計算されている。

g_{i,c} := \begin{cases} S_{i, c} - 1 & \text{ if } c = \text{target} \\ S_{i, c} & \text{ otherwise} \tag{1} \end{cases}
h_{i, c} := 2 S_{i, c} (1 - S_{i, c}) \tag{2}

なお、上記におけるS_{i, c}はモデルの予測値にsoftmaxを適用した値を表す。

S_{i, c} := \frac{e^{z_{i,c}}}{\sum_{c^\prime} e^{z_{i, c^\prime}}}

以下では目的関数がsoftmaxの場合に(1)式の勾配が導出できることを示す。
また、(2)式におけるHessianの対角要素(以下単にHessianと記述)については理論的に計算される値の2倍に設定してあることについても示す。

Cross entropy目的関数の勾配の導出

softmaxを適用する前のモデルの予測値をz_{i, c}とするとき（i: サンプルのindex, c: クラスのindex）、目的関数をCross Entropyとした場合は以下のように表せる。

\begin{align*} \mathcal{L} &:= -\sum_{i, c} y_{i, c} \log \frac{e^{z_{i,c}}}{\sum_{c^\prime} e^{z_{i, c^\prime}}} \\ &= -\sum_{i, c} y_{i, c} \left( z_{i,c} - \log \sum_{c^\prime} e^{z_{i, c^\prime}} \right) \tag{3} \end{align*}

(3) 式についてz_{i, c} に関する（偏）微分を計算したいので、z_{i, c} が関与する部分のみまとめると、

\mathcal{L}_{i, c} := -y_{i, c} z_{i, c} + \sum_{c^\prime} y_{i, c^\prime} \log(e^{z_{i, c}} + C_{i, c})

C_{i, c} はsoftmaxの分母からz_{i,c} に関する項を除いた定数で、

C_{i, c} := \sum_{c^\prime \ne c} e^{z_{i, c^\prime}}

したがって、

\begin{align*} \frac{\partial \mathcal{L}_{i, c}}{\partial z_{i, c}} &= -y_{i, c} \sum_{c^\prime} y_{i, c^\prime} \left( \frac{e^{z_{i, c}}}{e^{z_{i, c}} + C_{i, c}} \right) \\ &= -y_{i, c} + \sum_{c^\prime} y_{i, c^\prime} S_{i, c} \\ &= -y_{i, c} + S_{i, c} \tag{4} \end{align*}

hard target(各クラスの確率が正解の場合1、それ以外は0)の場合、(1)式が導出できる。

なお、正解ラベルがhard targetでなく、一般的な確率分布で与えられる場合は(4)式によって勾配を計算できる。

Hessianの乗数について

Hessianは(4)式より、

\frac{\partial^2\mathcal{L}_{i, c}}{\partial^2 z_{i, c}} = \frac{\partial}{\partial z_{i, c}} \left( \frac{e^{z_{i, c}}}{e^{z_{i, c}} + C_{i, c}} \right) = S_{i, c} (1 - S_{i,c}) \tag{5}

XGBoostの組み込みの目的関数multi:softprobでは(2)式のように、これを2倍したものになっている。この根拠については見つけられていないが、lightGBMのmulti_loglossでも過去のバージョンで同じように理論値の2倍の値を採用しており[4]、何らかの理論的、経験的な理由があるのだと思う。

現行のLightGBMの最新版(v4.3.0)では乗数として2でなくK/(K-1) を採用していて（K: クラス数）[6]、コメントの記述によると、「FriedmanのGBDTの論文に基づき、冗長なクラスの効果を補正するため」とある。

This factor is to rescale the redundant form of K-classification, to the non-redundant form
In the traditional settings of K-classification, there is one redundant class, whose output is set to 0 (like the class 0 in binary classification).
This is from the Friedman GBDT paper.

FriedmanによるGBDTの論文[7]を読むと、以下の内容についての記述がある。

  1. Hessianの対角要素による近似を行っていること[1]
  2. Hessianに補正項K/(K-1) が適用してあること(論文[7]中の33式)
  3. Hessianが0に近い場合に数値計算的に不安定になること

学び/今後の課題

  • LightGBMにせよXGBoostにせよ、Hessianについては微分して得られる値をそのまま設定してあるわけではなさそうなので、自分でobjectiveを設計する場合は組み込みのobjectiveをcustomで再実装して、組み込みの結果と乖離がないか見ておいた方が良い。
  • Hessianの対角要素による近似についての理論的な背景について理解するためにはFriedmanのGradient Boostingの論文[7]や、その前身であるLogitBoost[8]の論文を読んだ方が良さそう。

Reference

脚注

  1. なお、これはGradient Boostの前身であるFHT00[8]からそうしているとのこと。 ↩︎

GitHubで編集を提案

Discussion