2021-02-09

汎化誤差を抑える様々な手法とその関係性（１）

今回は、二値ラベル分類の誤差解析に役立ついろいろな指標について解説していきます。

まずは、「経験ラデマッハ複雑度」です。「経験ラデマッハ複雑度」とは、関数のクラスFに対して定まる集合で、

$\displaystyle{ R_{n}\left( F\right) = E\left[ \dfrac{1}{n}\sup _{f\in F}\sum ^{n}_{i=1}\sigma _{i}f\left( x_{i}\right) \right] }$

ただし、 $\sigma_1, \ldots, \sigma_n$ は $P(\sigma_i=1) = P(\sigma_i=-1) = 1/2$ を満たす確率変数で、期待値は $Z_1, Z_2, \ldots, Z_n$ および $\sigma_1, \sigma_2, \cdots, \sigma_n$ についてとっています。

これは、関数のクラスの「複雑度」を表す一つの指標です。

直観的には、 $\sigma_i$ はランダムラベルとみなすことができ、 $\displaystyle{ \sigma _ {i} f\left( x _ {i}\right) \gt0 }$ のとき関数fの当てはまりが成功しており、そうでないとき失敗しています。つまり、ラデマッハ複雑度は、どんなラベルに対しても、関数をクラスの中からうまく選べば、ある程度大きな値をとる（＝当てはめることができる）ことを（大雑把には）意味しています。

これは、何に役立つかというと深層学習における汎化誤差の解析です。詳しくは述べませんが、この値を用い、「どれぐらい過学習してしまうか」を確率的に不等式で抑えることができるのです。

この「ラデマッハ複雑度」についてですが、以下の不等式が「Massartの補題」というものから成立することが知られています。（証明略）

二値仮説関数の集合をhのクラスをHとし、Hは有限集合とすると

$\displaystyle{ R_{n}\left( H\right) =\sqrt{\dfrac{2\log \left| H\right| }{n}} }$

以上のことを仮定して、growth function, VC dimension, covering numberについて、さらにそれらの関係性について説明をしていきます。

まず、growth functionとは、fを二値関数としてそのset をFとすると、n個の点 $x_1, x_2, \ldots, x_n$ で $\displaystyle{ \tau _ {F}\left( x _ {1}, \ldots ,x _ {N}\right):=max _ {\left( x _ {1}, \ldots ,x _ {N}\right) }\tau _ {F}\left(x _ {1}, \ldots ,x _ {N}\right) }$ と定義したとき

$\displaystyle{ \tau_{F}\left( n\right) :=\max _{\left(x_{1}, \ldots ,x_{N}\right) }\tau_{F}\left( x_{1},\ldots,x_{N}\right) }$

直観的には、n個の点をうまく選んで、fを色々変えたときのありうる結果の場合の数の最大値になります。クラスの自由度が高いほど（＝複雑なほど）この数が大きくなることがわかると思います。

このgrowth functionについて、①式より

$\displaystyle{ R_{n}\left( F\right) \leq \sqrt{\dfrac{2\log \tau_{F}\left(n\right) }{n}} }$

が成立します。

この式より、ラデマッハ複雑度の方が汎化誤差の不等式を強く抑えることができる、ということがわかります。

2020-08-29

続.Conditional Monte Carloの金融工学への応用

前ブログの定理の証明を書きます。

この証明のキーポイントは

$\hat{F}_{n; R}^{Cond}(\hat{q}) - \hat{F}_{n; R}^{Cond}(q) = (\hat{q} - q)f_{n}(q)(1+o(1))$ (1)

という式を示すことです。実際、

$\hat{F}_{n;R}^{Cond}(\hat{q}_{Cond})=\alpha=F_{n}(q)$ が成り立つことに注意すると、（左辺はサンプルから推定したVaRボーダー、右辺は実際のVaRボーダーについての式ですね）

$0=\hat{F}_{n, R}^{Cond}(\hat{q}) - \hat{F}_{n; R}^{Cond}(q) + \hat{F}_{n; R}^{Cond}(q) - F_{n}(q)$ $=(\hat{q}-q)f_{n}(q)(1+o(1))$ $+\frac{\sqrt{Var(F(q-S_{n-1}))}}{\sqrt{R}}V(1+o(1))$

となり、(V~N(0, 1)です)この式を変形すれば示せます。

$f_n$ を連続とします。

$\hat{F}_{n, R}^{Cond}(\hat{q})-\hat{F}_{n, R}^{Cond}(q)=(\hat{q}-q)\hat{f}_{n,R}^{Cond}(q^{*})$

をみたす $q^{*}$ が $\hat{q}$ と $q$ の間にあります。

$f$ を広義単調減少と仮定すると、十分大きなRに対して $|\hat{q}-q|\leq\epsilon$ なので

$\hat{f}_{n;R}^{Cond}(q+\epsilon)\leq\hat{f}_{n, R}^{Cond}(q^{*})\leq\hat{f}_{n,R}^{Cond}(q-\epsilon)$

がそのRに対して成り立ちます。

この式と $\hat{f}_{n,R}^{Cond}(\cdot)$ の一致性より、

$\hat{f}_{n, R}^{Cond}(q^{*})⇀f_{n}(q)$

となり、(1)式が示せます。

この記事を読んだ方の中には、 $S_{n-1}$ が与えられた中での $S_{n}$ の条件付き分布の $\alpha$ 分位点を、R回繰り返す、という方法をとったほうがより単純にVaRを推定できるのでは？と思うかもしれません。しかし、この方法での推定値は $R⇀\infty$ にしてもバイアスがあります。

これはi.i.d.でN(0, 1)の例を考えれば単純で、推定値は

$\tilde{q}=S_{n-1}+z_{\alpha}$ ( $z_{\alpha}=\Phi^{-1}(\alpha)$ )

となりますが、

$\sqrt{n}z_{\alpha}$ が正しい推定値です。

2020-08-08

Conditional Monte Carlo法の金融工学への応用

Conditional Monte Carloの金融への応用に関する論文があったので内容を一部紹介します。

Conditional Monte Carlo(以下、CdMCと記します)とは、大雑把に言えば、「今までのシミュレーションした情報」ともとに「条件付き期待値」を求めることで期待値を推定する方法です。

この論文では、「確率変数の和の推定」という例でこの手法の利点や応用例を多く説明しています。

素朴なモンテカルロ法では、 $S_n=X_1+X_2+\cdots+X_n$ を確率変数の和と定義したとき、 $P(S_n \leq x)$ を推定する際は、

$Z=Z(x)=I(S_n\leq x)$

で推定されます。(Iは定義関数)

CdMCでは、 $X_1, X_2, \cdots, X_n$ がi.i.d.で共通の分布関数Fを持つ場合、

$Z_{cond}=P(S_n\leq x | X_1, X_2, \cdots, X_n)=F(x-S_{n-1})$

と推定されます。

この方法は、以下の点で優れています。

1, $x$ が固定されているときは、従来の方法より分散が小さい

2, CdMCでシミュレーションをR回繰り返して $S_n$ の平均を取って推定した分布関数は、従来の方法で $S_n$ のR回のシミュレーションを繰り返して分布関数を得るより滑らかな関数が得られる。

2番目については、累積分布関数が連続ならばその平均も連続なのであることからすぐわかります。１番目は、以下の条件付き分散に関するRao-Blackwellizationの公式

$VarZ \geq Var[E[Z|F$ ]] $=VarZ_{cond}$

によって成り立ちます。

実は、興味があるのが１の分散を減らすことだけであるならば、別の手法を用いたほうが効率がいいです。（ここでは省略します。）２の「推定される分布関数が滑らかである」ことがポイントです。

この手法を用いてVaRという、金融機関でよく使われるリスク指標を推定する方法について説明します。

$S_n$ の $\alpha$ 水準の $VaR_{\alpha}(S_n)$ は $VaR_{\alpha}(S_n)$ より損失値が大きくなる確率が $1-\alpha$ であることを表します。

数値としてほかの定義をすることもありますが、ここでは $\alpha$ 分位点 $q=q_{\alpha, n}$ で定義します。以下、分布関数Fは連続と仮定します。

素朴なモンテカルロ法でR回シミュレーションして推測すると

$\hat{F}_{n; R}(x; S_n) = \frac{1}{R}\sum_{r=1}^R{I(S_n^{(r)}\leq x)}$

と定義したときの

$\hat{q}_{cr}=\hat{F}_{n; R}^{-1}(\alpha)$

が推測値となります。

これは確率変数がi.i.d.である場合より複雑ですが、それでも中心極限定理のような式が成り立ち、

$\sqrt{R}(\hat{q}_{cr}-q) \rightarrow N(0, \sigma_{cr}^2)$

ただし

$\sigma_{cr}^{2}=\frac{\alpha(1-\alpha)}{f_n(q)^2}$

となることが知られています。ここで $f_n(q)$ を推定するのが必要になりますが、( $f_n(q)$ は密度関数です)これはとても難しいことが知られています。

しかし、CdMCを用いると、 $f(x-S_{n-1})$ を用いることで $S_n$ の密度関数を推定できます。（この推定値は、 $S_n$ の密度関数を $f_{n}(x)$ としたとき、 $E[f(x-S_{n-1})$ ] $= \int{f_{n-1}(y)f(x-y)dy} = f_n(x)$ なので不偏推定量になります）