多変量解析的なカーネル密度推定(TPE・Optunaの応用)

# はじめに

現在までに[TPE](https://qiita.com/nabenabe0928/items/708d221dbccebf31f01c)に関する記事を何度か書いてきた．

これまでの記事にも記載されているが，TPEの利点でもあり，欠点でもあるのが，各変数の独立性を仮定していることである．そこでTPEの確率密度推定手法を多変量的に行ったという[論文](https://ml.informatik.uni-freiburg.de/papers/18-ICML-BOHB.pdf)を発見したので記録を残す．参照した論文の主題は確率密度推定ではなく，HyperBandとベイズ最適化を組み合わせたことであるが，今回は確率密度推定に焦点を当てる．

また，参考にしたコードは[こちら](https://github.com/automl/HpBandSter/tree/master/hpbandster/optimizers/kde)．

# 論文における確率密度推定に対する意見
１．カーネル密度推定において本質的なことはカーネルの選択ではなく，バンド幅の選択方法である．
２．TPEでは各変数の相関性を考慮していないので，多変量的なカーネルを使用する．

# 多変量カーネル密度推定

```math
n: ハイパパラメータの次元数，m: 評価したハイパパラメータの個数\\
data = \{
( 
t_{1,1},...,t_{1,n}
),...
( 
t_{m,1},...,t_{m,n}
)
\}

\\
\overline t_{d} = \frac{\sum_{k = 1}^{m} t_{k, d}}{m}
\\ 
\sigma_{d} = \frac{\sqrt{\sum_{k = 1}^{m}(\overline t_{d} - t_{k, d})^2}}{m}
\\
{\rm IQR}_{d} = \{ t_{1,d},...,t_{m,d}\} 中，上位25％値と下位25％値の差
```

[この文献の8ページ](http://www.lib.kobe-u.ac.jp/repository/81006929.pdf)にあるように入力変数の分布が正規分布に従う場合，リスク値を最小にするバンド幅の値は数値解析的に提示されている．その式を利用して，以下のようにバンド幅を設定する．ただし，上位群と下位群の発生確率が明らかに高い場合は分散を[Interquantile Ranking](https://ja.wikipedia.org/wiki/%E5%88%86%E4%BD%8D%E6%95%B0)によって代替している．参考にしたBOHBの論文においては`Scott's rules`を採用したという記述があるが，その規則がどのようなものであるか，はっきりとわかっていない．

```math
\begin{eqnarray}
h_d = \left\{ \begin{array}{ll}
1.059\ m^{-\frac{1}{5}} {\rm min}(\sigma_d,\ {\rm IQR}_d) & (10^{-4} \leq h \leq 0.5) \\
10^{-4} & (h < 10^{-4}) \\
0.5 & (h > 0.5\ {\rm and\ continuous} ) \\
0.999 & (h > 0.999\ {\rm and\ categorical\ or\ discrete} ) \\
\end{array} \right.
\end{eqnarray} 
```

# カーネルの種類

以下の処理において，連続値は定義域を $[0 ,1]$ に変換してから，すべての計算を行うものとする．また，カテゴリカル値，離散値に関しては値と値の間隔を $1$ になるように変換している．

## Gauss Kernel(連続値)

```math
\\
\frac{1}{2}\Biggl({\rm erf }\ \frac{x}{\sqrt{2h^2}} + {\rm erf }\ \frac{1 - x}{\sqrt{2h^2}}\Biggl)
= \frac{1}{2}\int_{- x}^{1 - x} \frac{1}{\sqrt{2\pi h^2}}\exp\Biggl(-\frac{x'\ ^2}{2h^2}\Biggl) dx'
= \frac{1}{2}\frac{1}{\sqrt{2\pi h^2}} \int_{0}^{1} \exp\Biggl(-\frac{(x' - x)^2}{2h^2}\Biggl) dx' 

```

```math
w_{k, d} = \frac{2}{{\rm erf }\Biggl(\frac{1 - t_{k, d}}{\sqrt{2h_d^2}}\Biggl) + {\rm erf} \Biggl(\frac{t_{k, d}}{\sqrt{2h_d^2}} \Biggl)}\\

K_{k, d}(x_k) = \frac{1}{\sqrt{2\pi h_d^2}}\exp \biggl(- \frac{(x_k - t_{k, d})^2}{2h_d^2}\biggl) \\

```

## Wang Ryzin Kernel(離散値)

![Wang Ryzin Kernel.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355593/094fc860-dbe6-1243-ac61-a86540f81778.png)

```math
c = {\rm the\ number\ of\ choices} \\

\begin{eqnarray}
K_{k, d}(x_k) = \left\{ \begin{array}{ll}
1 - h & (|x_k - t_{k, d}| < \frac{1}{3c} \ ) \\
\frac{1 - h}{2}h\ ^{c|x_k - t_{k, d}|} & (otherwise) \\
\end{array} \right.
\end{eqnarray} \\

w_k = \frac{1}{\sum_{i = 1}^{c}\sum_{d = 1}^{m}K_{k, d}(i)} 
```

## Aitchison Aitken Kernel(カテゴリカル値)

![Aitchison Aitken Kernel.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355593/be5ee865-5864-2ea9-29a0-bd8e878aa602.png)


```math
c = {\rm the\ number\ of\ choice} \\
\begin{eqnarray}
K_{k, d} = \left\{ \begin{array}{ll}
1 - h & ({\rm round} (x_k - t_{k, d}) == 0 \ ) \\
\frac{h}{c - 1} & (otherwise) \\
\end{array} \right.
\end{eqnarray} 
```

# パラメータ空間の評価

## TPEにおける確率密度関数

各変数の確率密度関数を独立に求め，最終的な総和を取る．(注意：下の重み $w$ は本記事における $w$ とは異なる値である．[正確な値の参照](https://qiita.com/nabenabe0928/items/c895d96c0ff7a499d733)．)

```math
f(x) = \frac{1}{m}\prod_{d = 1}^n\sum_{k = 1}^{m} w_{k, d}K_{k, d}(x_k)
```

## 多変量カーネル密度推定の確率密度関数

各データに基づく多変量カーネルを求め，多変量カーネルの線形和を取る．

```math
f(x) = \frac{1}{m}\sum_{k = 1}^{m}\prod_{d = 1}^n w_{k, d}K_{k, d}(x_k)
```

# まとめ

TPEにおける確率密度関数を大幅に変更し，高性能を達成したという報告を受けている．その手法においては時間削減のアルゴリズムを適用しているため，今回の確率密度推定単体の長所を知ることはできていない．だが，TPEの欠点の一つでもある変数間の相関関係を考慮した確率密度を構築していることは注目に値する．今回は簡単ではあるが，多変量確率密度推定ともとの1変量確率密度推定の違いを簡単に記述した．式を見ると単純に記号の順番が入れ替わっているだけであるが，本質的な意味は大きく異なる．

ただし，従来の手法では1変数の高低の確率密度推定のみであったため，構築した探索モデル上の評価を容易に行うことができたが，変数間の相関関係を考慮した確率密度関数を構築した場合は，その空間を効率的に良い値を見つける必要がある．参考にした論文では単純なランダムサンプリングのみであったため，今後は探索モデルの構築が必要であろう．