NGBoost - HackMD

--- lang: ja-jp tags: survey --- # NGBoost - [arXiv : "NGBoost : Natural Gradient Boosting for Probabilistic Prediction"](https://arxiv.org/abs/1910.03225) - [GitHub : stanfordmlgroup/ngboost](https://github.com/stanfordmlgroup/ngboost) ## :memo: Keywords 情報幾何学と統計的学習の概念が頻出します： - (Proper) Scoring Rules - Divergence - **Natural Gradient** ## :book: TL;DR - 回帰問題を不確かさを考慮して解くアルゴリズム - アンサンブル手法として Boosting を使用する - 出力に対して確率分布を設定し、その確率分布のパラメータを Boosting により獲得する - Boosting する際に自然勾配を使用している（理由は後述）  ## :100: Summary of Contributions 1. 確率的回帰モデルとしての汎用的な **Natural Gradient Boosting** アルゴリズムを提案 - （出力する分布の）複数のパラメータに対する（ Scoring Rule の）自然勾配を使用した Boosting 手法による学習を導入している点が特徴的： a. （ Boosting 手法を用いるので）弱学習器の設定 `e.g. Regression Tree` b. （分布を出力とするので）パラメトリックな確率分布の設定 `e.g. Normal, Laplace` c. （統計的にパラメータを学習するので） Scoring Rule の設定 `e.g. MLE, CRPS` 2. CRPS といった Scoring Rule への自然勾配の一般化を導出 3. 提案手法がその他の出力の不確かさをモデリングする手法（や、あるいは点推定を行う手法）に対して匹敵する精度を実現することを実験から確認 ### Overview - 観測データの出力に対してパラメトリックな確率分布 $P_{\theta}$ を設定 - $P_{\theta}$ と $y$ に対して Scoring Rule $\mathcal{S} \left( P_{\theta}, y \right)$ を設定 - 確率分布のパラメータ $\theta$ を自然勾配を利用した Boosting 手法で推論 - モデルの出力として（推論されたパラメータを持つ）確率分布が得られる ![](https://i.imgur.com/0B9w2V7.png) ## :satellite: Natural Gradient Boosting 問題設定が通常の（点推定を行う）回帰問題とは異なる： | | Standard prediction settings | (proposing) Natural Gradient Boosting| | - |:----------------------------:|:-------:| | Input | $\mathbf{x}$ | $\mathbf{x}$ | | Output | $\mathbb{E} \left[ y ; x \right]$ | $P \left( y; x \right)$ with CDF $F_{\theta}$| | Objective | Loss Function <br />観測データと損失を比較する | **Scoring Rules**<br />推定される確率分布と観測データを比較する | ### Proper Scoring Rules - Scoring Rule $\mathcal{S}$ - 入力 : 推定される確率分布 $P$ と（一つの）観測データのラベル $y$ - 出力 : $\mathcal{S} \left( P, y \right) \in \mathbb{R}$ - 目的 : 確率分布に対する当てはまりの良さを評価するため  【定義】 Scoring Rule について、以下の条件を満たす場合（またその場合に限り） **Proper** であると言う： $$ \mathbb{E}_{y \sim Q} \left[ \mathcal{S} \left( Q, y \right) \right] \le \mathbb{E}_{y \sim Q} \left[ \mathcal{S} \left( P, y \right) \right] \forall P, Q $$ $Q$ は出力 $y$ の「真の」分布を、 $P$ はその他（モデルにより出力される）分布を意味している。$y$ が従う分布をモデルが出力する場合に最小になるという性質のこと？ :::info #### 自問自答 Q. **Proper** であることを考える理由は？ A. 最もデータを良く表現する確率分布を選定出来るようにするため？ :thinking_face: $\mathbb{E}_{y \sim Q} \left[ \mathcal{S} \left( Q, y \right) \right] \gt \mathbb{E}_{y \sim Q} \left[ \mathcal{S} \left( P, y \right) \right]$ であるような $P$ と $Q$ の比較があると適切なものを選択出来なくなる。 ::: 提案手法ではパラメトリックな確率分布を前提としているので、確率分布 $P, Q$ の表現をその確率分布のパラメータ $\theta$ に置き換えて表記する（ $\mathcal{S} \left( \theta, y \right)$ として表す）。よく利用される Proper Scoring Rules を取り上げる： #### Logarithmic Score - 最もよく利用されるもの - 最小化される場合に MLE （最尤推定）の手法に一致する - 普段の場合だと、「対数尤度の最大化」 - Negative Log-Likelihood - 表記は $\mathcal{L}$ $$ \mathcal{L} \left( \theta, y \right) = - \log P_{\theta} \left( \theta \right) $$ #### Continuous Ranked Probability Score (CRPS) - *Gebetsberger et.al, 2018* - [LOKAD : Continuous Ranked Probability Score (CRPS)](https://www.lokad.com/continuous-ranked-probability-score) >The Continuous Ranked Probability Score (CRPS) generalizes the MAE to the case of probabilistic forecasts - 最尤推定より Robust なものとして紹介される - 表記は $\mathcal{C}$ $$ \mathcal{C} \left( \theta, y \right) = \int_{-\infty}^{y} F_{\theta} \left( z \right)^{2} \text{d}z + \int_{y}^{\infty} \left( 1 - F_{\theta} \left( z \right) \right)^{2} \text{d}z $$ ### The Generalized Natural Gradient :::warning このセクションが提案手法を理解する上での大事な箇所です（注：理解したとは言ってない） ::: Scoring Rule を最小にするようなパラメータを得るために、各データ点 $\mathbf{x}$ におけるスコアに対するパラメータの「勾配」（ $\nabla \mathcal{S} \left( \theta, y \right)$ と表記）を求めて勾配降下法により最適化を行いたいが、通常の「勾配」を使うと「ある種の不具合」が生じてしまう（とのこと）。 :::success 「不具合の正体：〇〇」を説明し、その解決策が自然勾配の導入であることを理解することが目標となります！ ::: $\nabla \mathcal{S} \left( \theta, y \right)$ は「値を最も大きくさせる方向」となる。換言すれば、微小に $\mathbf{d} \in \mathbb{R}^{p}$ 方向だけその勾配に沿って動かした場合に値を最も大きくスコアを動かすものとなる： $$ \nabla \mathcal{S} \left( \theta, y \right) \propto \lim_{\epsilon \rightarrow 0} \arg \max_{\mathbf{d}:\|\mathbf{d}\| = \epsilon} \mathcal{S} \left( \theta + \mathbf{d}, y \right) $$ > This gradient is *not* invariant to reparameterization. この「勾配」は ==reparameterization== について **不変ではない**（パラメータのスケールを変えると、最小化の結果は変わらないにも関わらず、勾配が違ったものになってしまう？ :thinking_face:）。そのため、**パラメータの更新方法が学習に際して大きな課題となる**。 :::info #### 「不変ではない」の具体例 $A$ のすべての事象について $P_{\theta}\left( y \in A \right) = P_{\psi}\left( y \in A \right)$ （ただし $\psi = z\left(\theta\right)$）となるように $P_{\theta}$ を $P_{z\left(\theta\right)}\left(y\right)$ に置き換える（ e.g. $\frac{1}{2}$ 倍する）。勾配は $\theta$ について微小なステップだけ動かすことで得られるが、 $\theta$ を $\theta + d \theta$ の勾配方向に動かした分布と $\psi$ を $\psi + d \psi$ に動かした分布では結果が「大きく」異なりうる。換言すれば、 $P_{\theta + d \theta} \left( y \in A \right) \neq P_{\psi + d \psi} \left( y \in A \right)$ となってしまうということ。 ※ [SlideShare : 幾何を使った統計のはなし](https://www.slideshare.net/motivic/ss-14465676) の p11 ~ 13 を見て、具体的なイメージを得る。 ::: #### Introduction to Natural Gradient > The problem is that "distance" between two parameter values does not correspond to an appropriate "distance" between the distributions that those parameters identify. 「パラメータの空間内での距離」と「パラメータにより決まる確率分布の空間内での距離」の対応関係が複雑である、ということ :thinking_face: これを解決するために、情報幾何学から自然勾配という概念を活用する（ので、導入のために divergence の概念をおさらいする）。 ### Divergences Proper Scoring Rule であれば確率分布の空間においてのローカルな距離の指標としての *divergence* を導くことが出来る： $$ D_{\mathcal{S} \left( Q || P \right)} = \mathbb{E}_{y \sim Q} \left[ \mathcal{S} \left( P, y \right) \right] - \mathbb{E}_{y \sim Q} \left[ \mathcal{S} \left( Q, y \right) \right] \ge 0 $$ 分布 $Q$ から分布 $P$ への「離れ具合」の指標として解釈される。各 Proper Scoring Rule での divergence は次のように対応する： | Scoring Rule | Divergence | Notation | |:------------:|:----------:|:--------:| | [Logarithmic Score](#Logarithmic-Score) | Kullback-Leibler divergence | $D_{\text{KL}}$ | | [CRPS](#Continuous-Ranked-Probability-Score-CRPS) | $L^{2}$ divergence | $D_{L^{2}}$ **$D_{\text{KL}}$ , $D_{L^{2}}$ いずれも $P$ や $Q$ がどのようにパラメータ化されるかの詳細に関わらず不変である**という都合の良い性質が得られるため、 Scoring Rule に対する勾配ではなく、 Divergence に対する勾配を利用することで、パラメータの更新の安定化を実現できる。 Divergence から派生する勾配が「自然勾配」となる。 #### ==WIP== case: KL divergence 「パラメータ化の詳細に関わらず〜」を KL divergence について確かめる： $$ \text{KL} \left[ q\left( x; \theta \right) || p\left( x; \theta \right) \right] = - \int q\left( x; \theta \right) \ln \frac{p\left( x; \theta \right)}{q\left( x; \theta \right)} \text{d}x $$ ### Natural Gradient :::warning 論文には Divergence から自然勾配を導出する過程が省略されている && 情報幾何学について発表者が無知であるため、 "As Is" なものとして聴いてくださいmm  ::: 自然勾配の一般型は `Riemannian Space` における最急な勾配方向であり、次のように定義される： $$ \tilde{\nabla} \mathcal{S} \left( \theta, y \right) \propto \lim_{\epsilon \rightarrow 0} \arg\max_{d:D_{\mathcal{S}} \left( P_{\theta} || P_{\theta + d \theta} \right) = \epsilon} D_{\mathcal{S}} \left( \theta + d, y \right) $$ 対応する最適化問題を解くと、自然勾配は次のような性質を持つことがわかる（らしい）： $$ \tilde{\nabla} \mathcal{S} \left( \theta, y \right) \propto \mathcal{I}_{\mathcal{S}} \left( \theta \right)^{-1} \nabla \mathcal{S} \left( \theta, y \right) $$ $\mathcal{I}_{\mathcal{L}} \left( \theta \right)$ は ==Riemannian metric of the statistical manifold at $\theta$== であり、 $\mathcal{S}$ により導入される。 $\propto$ で自然勾配の表現がなされているのは、パラメータ更新に際して学習率（ i.e. step size ） $\eta$ を乗じるため影響を与えないから？ - - - 【$\mathcal{S}$ として $\mathcal{L}$ を選んだ場合】 NLL (Negative Log-Likelihood) の場合： $$ \tilde{\nabla} \mathcal{L} \left( \theta, y \right) \propto \mathcal{I}_{\mathcal{L}} \left( \theta \right)^{-1} \nabla \mathcal{L} \left( \theta, y \right) $$ の $\mathcal{I}_{\mathcal{L}} \left( \theta \right)$ は Fisher 情報行列に一致する（らしい）。 $$ \mathcal{I}_{\mathcal{L}}(\theta)=\mathbb{E}_{y \sim P_{\theta}}\left[\nabla_{\theta} \mathcal{L}(\theta, y) \nabla_{\theta} \mathcal{L}(\theta, y)^{T}\right] $$ パラメータ空間における NLL (as a Scoring Rule) の勾配を、フィッシャー情報行列の逆行列で補正する、というイメージか。 - - - 【$\mathcal{S}$ として $\mathcal{C}$ を選んだ場合】 ==WIP== - - - #### 普通の勾配との違いの可視化 ![](https://i.imgur.com/x0FLq2O.png) #### 出力される確率分布の違いの可視化 ![](https://i.imgur.com/G2XXkrn.png) ### NGBoost : Natural Gradient Boosting #### Notation - $\eta$ : 学習率（たいてい 0.1 か 0.01 程度の数値） - $f^{(m)}$ : $m$ 個めの弱学習器 - $g_{i}^{(m)}$ : $m$ 個めの弱学習器の目的変数 #### Algorithm ![](https://i.imgur.com/xy0FG13.png) ### Computational Complexity - NGBoost では「パラメータの数だけ」弱学習器列の学習が必要になる - GBRT とかだと弱学習器は１列のみ - （通常の Boosting アルゴリズムと比較した際に）確率分布のパラメータが $p$ 個であれば学習に必要な時間計算量は $p$ 倍だけ線形に増加する - 自然勾配の計算を観測データ（点）ごとに行う必要がある - $p \times p$ 次元の $\mathcal{I}_{\mathcal{S}}$ の逆行列を観測データごとに計算（時間計算量は $O \left( N \times p^{3} \right)$ となる） - $m$ 次元の正則行列の逆行列の時間計算量は $O \left( m^{3} \right)$ らしいこの事実に対して論文の筆者は次のようにまとめている： - パラメータ数が $5$ を超えるような確率分布はめったにない（ von-Mises Fisher Dist. とか？）ので $p$ の次元数に対する時間計算量の増大は現実ではさほど問題にはならない - データセット数 $N$ が大きい場合には逆行列の演算に時間がかかるため、多数の小さい行列を Sub-sampling することで学習をミニバッチ化することでパフォーマンスの改善を実現できる - 総じて「 $p$ が小さい限り、 NGBoost はその他の Boosting アルゴリズムと同じようなスケールの仕方をする」 ## :flashlight: Experiments ==あとで文章にまとめる（発表時は論文に飛ぶ）== ## :hammer: Future Work ==WIP==