2019-12-31

雑記：サンプリング定理の話

雑記

キャラクターは架空のものです。おかしい点がありましたらご指摘いただけますと幸いです。

参考文献

Nyquist–Shannon sampling theorem - Wikipedia

f:id:cookie-box:20190101155733p:plain:w60

Nyquist–Shannon sampling theorem - Wikipedia に以下のようにあります。

関数 $x(t)$ が $B$ ヘルツを超える周波数を含まないならば^※、 $x(t)$ は $1/(2B)$ ごとにサンプリングした値から完全に復元することができる。

※ ただし、ちょうど $B$ ヘルツの正弦波を含んではならない。「 $B$ ヘルツ以上の周波数を含まないならば」とされることも多い。

…サンプリングしたのに元の関数が「完全に復元できる」とは不思議ではありませんか？

あ、ちなみにこの定理、ウィキペディアの記事名は「ナイキスト‐シャノンのサンプリング定理」となっていますが、後にコテルニコフさんという方が先にこの定理を発表していたのが発見されたので、「ナイキスト‐シャノン‐コテルニコフのサンプリング定理」ともいうようですね。まるでカルーシュ‐クーン‐タッカー条件のようです。

f:id:cookie-box:20190101160814p:plain:w60

何にせよ $x(t)$ を完全に復元できるサンプリング周波数 $2B$ をナイキストレートというんだね。他方、実際のサンプリング周波数 $f_s$ の半分 $f_s/2$ をナイキスト周波数というのか…ややこしいな。サンプリング周波数 $f_s$ でサンプリングしたときは $f < f_s/2$ を満たす周波数成分は再構築されることが保証されると。だからなぜ保証されるかが知りたいんだけど…先にエイリアシングという節で次の式が出てくる。

$\displaystyle X_s(f) := \sum_{k=-\infty}^\infty X(f - k f_s) = \sum_{n=-\infty}^\infty \frac{1}{f_s} \cdot x \left( \frac{n}{f_s} \right) e^{- 2 \pi i n f / f_s}$ これは、「もし関数 $x(t)$ を $f_s$ ごとにサンプリングしたサンプル $x(n/f_s)$ が無限に手元にあったら、それに $e^{- 2 \pi i n f / f_s}$ をかけて足したものは、周波数の世界で間隔 $f_s$ ごとに元の関数のフーリエ変換 $X(f)$ を無限に重ねていったものと等しい」という式かな。これ自体はポアソンの和公式にサンプルたちを当てはめただけだ。中辺で表される周期関数から出発してフーリエ級数展開した係数を求めたらこうなったともいえる。

Poisson の和公式 - 記憶帳

えっと、だから何なんですか？私たちはいま、サンプル $x(n/f_s)$ たちから元の関数 $x(t)$ を復元できるのかに興味があると思うんですが。

だからだよ。最右辺をみたらこれは元の関数の「離散フーリエ変換」だ。上式の主張は、「ある関数を離散フーリエ変換すると、素直に周波数成分が出てきてくれるのではなく、周波数成分が無限に『かげぶんしん』したものが出てきてしまう」といっているに他ならない。ウィキペディアの下図のようにね。

AliasedSpectrum.png

私たちは「サンプルから元の関数が復元できるのか」に興味があるけど、これは現在の文脈でもっと正確にいうと「サンプルたちから元の関数の周波数成分の情報を得て、そこから元の関数が復元できるのか」だね。そして上図が示唆することは、「サンプリング周波数 $f_s$ の半分を超える周波数成分は復元できない」だ。なぜなら、周波数成分のグラフ（青色）の $f_s/2$ を超える部分は自身の「かげぶんしん」（黄緑色）と重なって一般的には識別できなくなってしまうからね。

ちなみに、画像や音声をデジタル化するときに高周波成分が低周波なノイズになってあらわれる現象を「エイリアシング」というみたいだね。これを防ぐために予め元の情報をローパスフィルタにかけるらしいよ。

折り返し雑音 - Wikipedia

「サンプリング周波数 $f_s$ の半分を超える周波数成分は復元できない」ですか…想像するに、1秒光って1秒消えるような周期2秒の点滅を繰り返すランプがあったとして、これを1秒おきに観測するなら「1秒おきに光っていそうだ」とわかりそうですが、2秒おきに観測するならもう点滅しているかもわからなさそうですね…。他方、対象の関数 $x(t)$ の周波数成分がサンプリング周波数 $f_s$ の半分を超えない範囲に収まっていれば、 $X(f)$ が識別できるのでそれをフーリエ逆変換すればよいということなんですね。

そうなんだけど、元の関数を直接サンプルたちで表す式も続きにあるね。上で定義した「かげぶんしん付き」フーリエ変換 $X_s(f)$ からかげぶんしんを排除するため、矩形関数で $f < |f_s/2|$ の部分だけ切り取る。

$\displaystyle \begin{split} X(f) &= {\rm rect}\left( \frac{f}{f_s} \right) X_s(f) \\ & = {\rm rect}\left( \frac{f}{f_s} \right) \sum_{n=-\infty}^\infty \frac{1}{f_s} \cdot x \left( \frac{n}{f_s} \right) e^{- 2 \pi i n f / f_s} \\ & = \sum_{n=-\infty}^\infty x \left( \frac{n}{f_s} \right) \cdot \frac{1}{f_s} {\rm rect}\left( \frac{f}{f_s} \right) e^{- 2 \pi i n f / f_s} \end{split}$ 矩形関数はsinc関数のフーリエ変換だから、両辺をフーリエ逆変換することで以下を得る。 $\displaystyle x(t) = \sum_{n=-\infty}^{\infty} x \left( \frac{n}{f_s} \right) \cdot {\rm sinc}\left( f_s t - n\right)$ sinc関数や矩形関数の定義は（そもそもフーリエ変換の定義も）、冒頭の記事からもリンクがあるけど、以下に準拠するよ。

https://en.wikipedia.org/wiki/Fourier_transform#Square-integrable_functions,_one-dimensional

「矩形関数はsinc関数のフーリエ変換だから」で片付けられても…本当にそのsinc関数をフーリエ変換すると矩形関数になりますか？

$\displaystyle \begin{split} \mathcal{F}[{\rm sinc}(f_s t - n)](f) &= \int_{-\infty}^\infty {\rm sinc}\left( f_s t - n\right) e^{-2 \pi i t f}dt \\ &= \int_{-\infty}^\infty {\rm sinc}\left( f_s t' \right) e^{-2 \pi i t' f} e^{-2 \pi i n f / f_s} dt' \qquad (t' = t - n/f_s) \\ &= e^{-2 \pi i n f / f_s} \int_{-\infty}^\infty {\rm sinc} \left( f_s t' \right) e^{-2 \pi i t' f} dt' \\ &= e^{-2 \pi i n f / f_s} \frac{1}{f_s} \int_{-\infty}^\infty {\rm sinc} \left( t'' \right) e^{-2 \pi i t'' f / f_s } dt'' \qquad (t'' = f_s t') \\ &= e^{-2 \pi i n f / f_s} \frac{1}{f_s} \int_{-\infty}^\infty \frac{\sin (\pi t'')}{\pi t''} e^{-2 \pi i t'' f / f_s} dt'' \end{split}$ この積分が ${\rm rect}(f/f_s)$ になるはずですが…難しそうですね。逆に矩形関数をフーリエ逆変換しますか。 $\displaystyle \begin{split} \mathcal{F}^{-1}[{\rm rect}(f)](t) &= \int_{-\infty}^\infty {\rm rect}(f) \cdot e^{2 \pi i t f} df \\&= \int_{-1/2}^{1/2} e^{2 \pi i t f} df \\&= \left[ \frac{e^{2 \pi i t f}}{2 \pi i t} \right]_{f=-1/2}^{f=1/2}\\&=\frac{e^{\pi i t } - e^{-\pi i t}}{2 \pi i t} \\ &=\frac{\sin (\pi t)}{\pi t} = {\rm sinc}(t) \end{split}$ …確かに矩形関数のフーリエ逆変換がsinc関数なので、sinc関数のフーリエ変換は矩形関数ですね。

ここまでの話を整理すると、

サンプリング周波数 $f_s$ で取ってきた関数の値のサンプルたちから、周波数成分の情報を得ることを経由して元の関数を復元したい。＝サンプルたちをフーリエ変換してから逆フーリエ変換することで元の関数を復元したい。
サンプルたちを素直に離散フーリエ変換すると $[-f_s/2, f_s/2]$ の範囲が延々と繰り返されたものになってしまうことがわかる。ので、元の関数の周波数成分がこの範囲に収まるようにサンプリング周波数 $f_s$ を大きくとり、かつ、サンプルたちの離散フーリエ変換に対して矩形関数で $[-f_s/2, f_s/2]$ の範囲を切り取ってから逆フーリエ変換する必要がある。
「サンプルたちの離散フーリエ変換に矩形関数をかけて逆フーリエ変換したもの」は、「サンプルたちにその位置でてっぺんになるsinc関数をかけて足したもの」に他ならない。

ということですか…ん、ちょうど $f_s/2$ の周波数成分はどうなるんです？ウィキペディアの Introduction のところに、「ちょうど $B$ ヘルツの正弦波を含んではならない」というようにありましたが、正弦波限定でだめなんですか？では余弦波は大丈夫だと？

…じゃあ部長に演習問題だ。以下の関数をサンプリング周波数 $f_s$ でサンプリングしてから復元してほしい。

$x(t) = \cos(\pi f_s t)$
$x(t) = \sin(\pi f_s t)$

ええ…1. は $x( n /f_s) = \cos(n \pi)$ なので、これは $n$ が偶数のとき $1$ 、 $n$ が奇数のとき $-1$ ですね。

$\displaystyle \begin{split} x(t) &=\sum_{n=-\infty}^\infty (-1)^n {\rm sinc}\left( f_s t - n\right)=\sum_{n=-\infty}^\infty (-1)^n \frac{\sin \bigl( \pi( f_s t - n) \bigr)}{\pi( f_s t - n)} \\&=\sum_{n=-\infty}^\infty (-1)^n \frac{\sin ( \pi f_s t) \cos(n \pi ) - \cos( \pi f_s t) \sin(n \pi ) }{\pi( f_s t - n)} = \sum_{n=-\infty}^\infty \frac{\sin ( \pi f_s t)}{\pi( f_s t - n)} \\&= \sin ( \pi f_s t) \sum_{n=-\infty}^\infty \frac{1}{\pi f_s t - n \pi} \\&= \sin ( \pi f_s t) \frac{\cos(\pi f_s t) }{\sin(\pi f_s t)} = \cos(\pi f_s t) \end{split}$ ここで最後の行への式変形は以下の記事の極展開によりました。

ミッタク＝レフラーの定理 - Wikipedia

$f_s t$ が整数に一致するような $t$ ではこの変形はできませんが、逆に $f_s t$ が整数に一致しているならば最初の行からただちに $x(t)=1$ （偶数に一致しているとき）または $x(t)=-1$ （奇数に一致しているとき）なので結局如何なる $t$ でも $x(t)=\cos(\pi f_s t)$ といえるのではないでしょうか。つまり、「サンプリング周波数の半分ぴったりの余弦波は完全に復元できる」といえそうです（自信はありませんが…）。

それでは 2. は、 $x( n /f_s) = \sin(n \pi)$ なので…え、これサンプルが全て $0$ ですね。だったら復元しても $x(t)=0$ にしかなりません…しかし、なぜ余弦波と正弦波でこのような違いが… 慢心、環境の違い…。

原点を起点にサンプリングしていくなら、正弦波は波のてっぺんの位置がちょうど悪くて（サンプリングするインターバルのちょうど中間にてっぺんがきてしまって、サンプリングする点ではいつも波が全くない）、余弦波は逆にちょうどいいってことだと思う。あと、余弦波と正弦波をフーリエ変換してみてもなんでこの違いが出るのかわかると思うよ。

つづくかも

f:id:cookie-box:20191231173321p:plain:w390

2019-12-22

雑記：レーティングのベイズ的解釈の話

雑記

キャラクターは架空のものです。お気付きの点がありましたらご指摘いただけますと幸いです。

一昨日、佐藤和俊七段が渡辺明三冠に勝利して、以下のサイトでの両者のレーティングが $14$ 変化しましたね。以下のサイトでのイロレーティングの定数値 $K$ は $16$ ですから、一回のレーティング変化の理論上限が $16$ であり、 $14$ というのは相当大きな変化ということになります。

将棋連盟棋士別成績一覧（レーティング）

今回の変化を表にまとめると以下です。

	12月20日対局前	12月20日対局後
渡辺明三冠レーティング $R_W$	$R_W^{(0)} = 2016$	$R_W^{(1)} = R_W^{(0)} - 16 W_{WS}^{(0)} = 2002$
佐藤和俊七段レーティング $R_S$	$R_S^{(0)} = 1696$	$R_S^{(1)} = R_S^{(0)} + 16 W_{WS}^{(0)} = 1710$
佐藤和俊七段が渡辺明三冠に勝利する確率 $W_{SW}$	$W_{SW}^{(0)} = 0.1368$	$W_{SW}^{(1)} = 0.1570$
渡辺明三冠が佐藤和俊七段に勝利する確率 $W_{WS}$	$W_{WS}^{(0)} = 0.8632$	$W_{WS}^{(1)} = 0.8430$

勝利確率はレーティングから算出される勝利確率 $\displaystyle W_{SW}^{(t)} = \frac{1}{10^{(R_W^{(t)} - R_s^{(t)})/400} + 1}$ ですね。 $400$ はただのスケーリング係数です。レーティングの更新規則も表の中に示しました。 $K=16$ は上記のサイトで採用されている定数値、いわば更新の度合いのハイパーパラメータですね。大きいほど直近の対局結果を反映するレーティングになります。つまりレーティングとは、負けた方から勝った方へ数値を移動させる、どれだけ数値を移動させるかは「勝った方が勝てなかったであろう確率」に比例させる、というパイの奪い合いです。そのため、パイを奪って引退する人が多いとレーティングはデフレし、奪われて引退する人が多いとレーティングはインフレします。将棋のプロ棋士の場合、引退間際には棋力が衰えてパイを奪われた状態で引退するケースが多いと思われるのでインフレ傾向にあると思われますが。無論、対局が強い対局者同士／弱い対局者同士に偏っていたり、棋士によって対局の頻度が違ったり、更新の度合いが状況の変化に追いつかないとレーティングは実態から乖離しますし、そもそも棋力は1次元に射影できるものでもありませんが…。

…さておき、上の表をみると、佐藤和俊七段が渡辺明三冠に勝利する確率（またはその逆）が、12月20日の対局の結果を受けて 13.68% から 15.70% に更新されていますが、まるでベイズ推測のようではないですか？であれば、更新の度合い $K$ とは、ベイズ逆温度 $\beta$ に相当するのではないでしょうか？？

…まぎれもなく12月20日の対局の結果を受けて更新されてはいるよね。ただそれがベイズ的かどうかは、ベイズ推定の枠組みにはまるかどうかという気がするけど…「佐藤和俊七段が渡辺明三冠に勝つか負けるか」の確率モデルはベルヌーイ分布だよね。なら共役事前分布はベータ分布 ${\rm Beta}(a, b)$ になる。以下の日記でやったコイン投げの例だね。

ベイズ統計の理論と方法：ノート2.5 - クッキーの日記

$\varphi(w) = {\rm Beta}(a, b)$ とすれば、まだデータを1つも観測していないときは $p^{\ast}( {\rm head} ) = a/ (a + b)$ 、 $p^{\ast}( {\rm tail} ) = b/ (a + b)$ だね。「表（勝ち）」のデータを1つ観測したときは以下のように更新される。

$Z_1(\beta) = \int_{0}^{1} w^{a - 1 + \beta} (1-w)^{b - 1} dw = \Gamma(a + \beta) \Gamma(b) / \Gamma(a + b + \beta)$
$p(w|X^1) = \bigl\{ \Gamma(a + b + \beta) / \Gamma(a + \beta) \Gamma(b) \bigr\} w^{a - 1 + \beta} (1-w)^{b - 1}$
$p^{\ast}( {\rm head} ) = \bigl\{ \Gamma(a + b + \beta) / \Gamma(a + \beta) \Gamma(b) \bigr\} \cdot \int_{0}^{1} w^{a - 1 + \beta + 1} (1-w)^{b - 1} dw = (a + \beta) / (a + b + \beta)$
$p^{\ast}( {\rm tail} ) = \bigl\{ \Gamma(a + b + \beta) / \Gamma(a + \beta) \Gamma(b) \bigr\} \cdot \int_{0}^{1} w^{a - 1 + \beta} (1-w)^{b - 1 + 1} dw = b/ (a + b + \beta)$

$\varphi(w) = {\rm Beta}(a, b)$ を事前分布にしてベイズ推測するのは、予め「表（勝ち）」を $a$ 回、「裏（負け）」を $b$ 回観測しておいたと考えて、観測したデータを $\beta$ 倍に「水増し」して最尤推定した結果と同じになるね。…それで、上の結果をイロレーティングと対比するとこうかな（ここで、本質的でない係数や対数の底を適当に変換したよ）。

	ベルヌーイ分布のベイズ推測	イロレーティング
対局前の勝利確率	$\displaystyle \frac{a}{a + b}$	$\displaystyle \frac{1}{\exp \bigl( R_W - R_S \bigr) + 1}$
対局後の勝利確率	$\displaystyle \frac{a + \beta}{a + b + \beta}$	$\displaystyle \frac{1}{\exp \left( R_W - R_S - \frac{2K}{\exp(R_S - R_W) + 1} \right) + 1}$

ちょっとみづらいから $r_{W} := \exp(R_W)$ 、 $r_{S} := \exp(R_S)$ とおくか。ウィキペディアのイロレーティングの記事をみるとわかるけど、レーティングのエクスポネンシャルは意味としては平均的なプレイヤーに対するオッズ（勝つ確率／負ける確率）だね。どちらかというと、オッズの対数がレーティングなんだけど。

	ベルヌーイ分布のベイズ推測	イロレーティング
対局前の勝利確率	$\displaystyle \frac{a}{a + b}$	$\displaystyle \frac{r_S}{ r_S + r_W}$
対局後の勝利確率	$\displaystyle \frac{a + \beta}{a + b + \beta}$	$\displaystyle \frac{r_S}{r_S + \exp \left( - \frac{2 K r_W}{r_S + r_W} \right) r_W}$ $\displaystyle = \frac{r_S \exp \left( \frac{2 K r_W}{r_S + r_W} \right) }{r_S \exp \left( \frac{2 K r_W}{r_S + r_W} \right) + r_W}$ $\displaystyle = \frac{r_S + r_S \left[ \exp \left( \frac{2 K r_W}{r_S + r_W} \right) -1 \right] }{r_S + r_W + r_S \left[ \exp \left( \frac{2 K r_W}{r_S + r_W} \right) -1 \right]}$

無理やり形を合わせにいってみた…変なことをしていない自信はない…。上の式変形を認めるなら、ベイズ推測とイロレーティングの対応は以下だな。

	ベルヌーイ分布のベイズ推測における各パラメータの役割	イロレーティングをベイズ更新と解釈すると対応するもの
事前分布 ${\rm Beta}(a, b)$ の $a$	予め相手に $a$ 回勝っていたと考える	自分の平均的プレイヤーへのオッズ $r_S$
事前分布 ${\rm Beta}(a, b)$ の $b$	予め相手に $b$ 回負けていたと考える	相手の平均的プレイヤーへのオッズ $r_W$
ベイズ逆温度 $\beta$	対局結果を $\beta$ 倍に水増しする	$\displaystyle r_S \left[ \exp \left( \frac{2 K r_W}{r_S + r_W} \right) -1 \right]$ $K$ は予め適当に決めた定数 $r_W/(r_S + r_W)$ は事前の負け確率

だから「更新の度合い $K$ はベイズ逆温度 $\beta$ に相当するのか」という問いへの答えは、ぴったり対応はしていない。でも、以下の極限での挙動は一致している。

$\beta \to 0$ も $K \to 0$ も、対局結果を全く取り入れないことに相当する。
$\beta \to +\infty$ も $K \to +\infty$ も、対局結果にしたがい勝った方の勝率を $1$ にすることに相当する。

イロレーティングにおいてベイズ逆温度 $\beta$ に相当するもの $\displaystyle r_S \left[ \exp \left( \frac{2 K r_W}{r_S + r_W} \right) -1 \right]$ は、更新の度合い $K$ の他に自分のオッズ $r_S$ と事前の負け確率 $r_W/(r_S + r_W)$ が入っているね。

自分のオッズ $r_S$ が大きいほどそれに比例して対局結果を水増しする。
更新の度合い $K$ が大きいほど指数関数的に対局結果を水増しする。
（勝ったとき）事前の負け確率 $r_W/(r_S + r_W)$ が大きいほど指数関数的に対局結果を水増しする。

ん？ $K$ や事前の負け確率が大きいほどレーティングが大きく変動するのはわかります。そのような定義式ですし。でも、自分のオッズ $r_S$ が大きいほどレーティングは大きく変化するということはありませんよ？レーティング変化は水準によらず、 $K$ に事前の負け確率をかけた数値です。

レーティングはね。でもレーティングと勝利確率は違うよ。例えば冒頭の対局結果は両対局者のレーティングが 400 ずつ低かったとしても対局前後の勝利確率は同じになるけど（勝利確率はレーティング差にしか依存しないからね）、レーティングが低い（オッズが小さい）のに同じだけの勝利確率の変化をさせたかったら、対局結果をオッズをかけて取り込まないといけないって感じかな。ただそもそも上の定義だと「予め相手に $a$ 回勝っていたと考える」の $a$ が自分のオッズだから自分のオッズが大きいほど強い事前信念をもっている感じになっちゃうんだよね…全体を自分のオッズで割ってからベイズ推測とイロレーティングを対応させた方がよかったかな…。

	ベルヌーイ分布のベイズ推測	イロレーティング
対局前の勝利確率	$\displaystyle \frac{a}{a + b}$	$\displaystyle \frac{1}{ 1 + \frac{r_W}{r_S}}$
対局後の勝利確率	$\displaystyle \frac{a + \beta}{a + b + \beta}$	$\displaystyle \frac{1}{1 + \exp \left( - \frac{2 K r_W}{r_S + r_W} \right) \frac{r_W}{r_S}}$ $\displaystyle = \frac{\exp \left( \frac{2 K r_W}{r_S + r_W} \right) }{\exp \left( \frac{2 K r_W}{r_S + r_W} \right) + \frac{r_W}{r_S}}$ $\displaystyle = \frac{1 + \left[ \exp \left( \frac{2 K r_W}{r_S + r_W} \right) -1 \right] }{1 + \frac{r_W}{r_S} + \left[ \exp \left( \frac{2 K r_W}{r_S + r_W} \right) -1 \right]}$

つづかない

2019-12-19

論文読みメモ： Latent Ordinary Differential Equations for Irregularly-Sampled Time Series（その1）

論文読み

以下の論文を読みます。

Yulia Rubanova, Tian Qi Chen, David K. Duvenaud. Latent Ordinary Differential Equations for Irregularly-Sampled Time Series. In Advances in Neural Information Processing Systems 32, 2019.
https://papers.nips.cc/paper/8773-latent-ordinary-differential-equations-for-irregularly-sampled-time-series

※ キャラクターは架空のものです。解釈の誤りは筆者に帰属します。おかしい点がありましたらご指摘ください。

前回：雑記： NeurIPS 2019 Proceedings の「時系列」を含むタイトル／次回：まだ

前回のあらすじです。

「不規則にサンプリングされた時系列のための隠れ常微分方程式」？不規則にサンプリングされた時系列は通常のRNNで扱うのは難しいと。それはそうですね。そこでRNNを、常微分方程式による連続的な隠れ状態をもつものに魔改造されたのですね。なるほど、だから「隠れ常微分方程式」ですか…。そもそもこれ以前に Latent ODE という手法が提案されているのですね。この ODE-RNNs も Latent ODE もポアソン過程から不規則にサンプリングされた系列を上手くモデリングしたようですね。この ODE を用いた手法は既存の RNN ベースの手法よりアウトパフォームしたということです。

ところでRNNには「等間隔でない」系列の特徴を学ぶのは難しいんですか？ RNNに入力するのって必ずしも時間方向に増えていく系列ではないと思うので等間隔というのがよくわからないんですが、例えば文章を形態素ごとに入力していくのとかは「等間隔」なんですか？

RNNは「最新の入力」と「直前までの特徴」から「最新の特徴」を出すモデルだよね。「直前までの特徴」を「最新の特徴」に更新できるだけの情報が各 $x_i$ に含まれていればいいと思うから、不等間隔というよりはそれで情報が欠落するのが問題なんじゃないかな。もちろん、情報の欠落がなかったとしても、あまりにばらばらな間隔の情報がどんどんモデルに投げ込まれてきたら、パターンが爆発して、モデル側も学習しづらいと思うけど。

うーん、それで、不等間隔なデータを取り扱う常套手段として、「等間隔になるようにプレ処理する」がありますが、これは情報を損ねると。特に情報が到着したタイミングなどを。それはそうですね。だから連続時間に対応できるモデルが望ましいといっています。それで、近年では観測時点の間で内部状態が指数関数的に減衰するような RNN（RNN-Decay）が発表されているそうです。指数関数的に減衰させるというのはそれはそれでいいんでしょうか？まあ、あまりに長い間観測値が入ってこなかったらRNNさんもいまどんな状況なのか全然わからなくなりそうなので、そういう意味ではもっている情報が減衰していくことになるんでしょうか…。また別のモデルとして、著者の方々のグループが過去に Neural ODEs というのを発表しているようですね。これは Figure 1 をみるに隠れ状態の各次元の時間変化を柔軟に記述しているようですが、どのようなものなんでしょうか。これは RNN ではなさそうですね。今回はその Neural ODEs で構築した、ODE による連続的な状態変化を RNN に組み込むといった感じなのですね。それが ODE-RNN だと…。それで2節に入ると、不等間隔なデータをRNNで取り扱う最もシンプルな方法は、前回の入力からの時間差をモデルに入れてしまうことだとありますね。確かに、これならRNNさんはいまの入力をどのように受け止めるべきか知ることができるかもしれません。

$h_i = {\rm RNNCell}(h_{i-1}, \Delta_t, x_i)\tag{1}$ しかしこれだと観測間の隠れ状態をどう定義するかに疑問が残る…？ RNNさんが出力するのは、「これまで受け取った系列の特徴はこうです」ですよね？観測間の隠れ状態を定義する必要があるんですか？？

だから、判定を常に出しっぱなしにしてほしいんだろうね。例えば、不定期的にジムにトレーニングに来るお客さんがいたとして、その人がもうジムに来なくなってしまう確率を毎日出しっぱなしにしたいとか？きっと日々変化していくよね。最後に来てから日が空くほど徐々に離脱確率は高まっていきそうだし、来てくれたらまた下がりそうだし。離脱確率が高い人が判定できれば確率が高い人たちだけに無料クーポンを配布するとかできそうだよね…まあそんな風に行動履歴をつかえるのかとか、クーポンが配布されなかったお客さんに不公平感か出ないかとかはありそうだけど。…これだと単純そうだから医療の例とかの方がいいのかな。色々な症状が不定期的に出て来院する患者さんが向こう1年に重大な病気を発症する可能性、とか？

急に中途半端に現実的になりましたね…ともかく、いまの問題設定は通常のRNNの想定と少しずれている気がします。通常のRNNってこうでしょう？

「最新の入力」と「直前までの特徴」から「最新の特徴」を出す。そういう仕組みで現在までに順番に入力されてきた入力たちの特徴を出す。

しかし、いまの文脈だとこうなのですね？

不定期的に入力される入力を受け取って常に特徴を出し続ける。

これだけ状況が変わると、まずリカレントにやるべきなんでしょうか…まあそれで、状態を連続的に出し続ける1つの方法は、ずっと同じ状態を出し続けることですね。しかしそれではよくないだろうということで次の RNN-Decay ですか。 $h_i = {\rm RNNCell} \bigl( h_{i-1} \cdot \exp(- \tau \Delta_t), x_i\bigr)\tag{2}$ 左辺が $h_i$ ですが連続時間の特徴を考えるなら添え字を $t$ にした方がいい気もしますが、とにかく $x_i$ が入力されたときに出力される状態（特徴）が $h_i$ ですね。しかし RNN-Decay では予測性能がよくならなかったと…何のタスクでなんでしょうか。そもそも RNN-Decay 自体何がやりたいのかよくわからないし…。

何がしたいのかも含めて読んでいけばわかるんじゃないかな。次に Neural ODEs の話が出てくるけど、隠れ状態 $h(t)$ を次の ODE の解とするんだね。

$\displaystyle \frac{dh(t)}{dt} = f_\theta \bigl( h(t), t \bigr), \; h(t_0) = h_0 \tag{3}$ この $f_\theta$ を学びさえすれば好きな時刻の $h(t)$ を手に入れられると。これはどのタイミングで学習してどのタイミングで利用するモデルなのかな…。まあそれで今回提案する ODE-RNN は3ページ目の上にある Algorithm 1 をみればいいのかな。つまり、各時刻 $t_i$ に、状態をまず時間発展させて、時間発展させた状態を通常のRNNのようにつかうんだね。

「最新の入力」と「直前の特徴をその時刻まで時間発展させたもの」から「最新の特徴」を出す。そういう仕組みで現在までに順番に入力されてきた入力たちの特徴を出す。

入力がない時刻についても時間発展させた状態が取り出せそうかな。RNN-Decay は減衰しかできなかったのを、より柔軟な時間発展が学習できるようにしたって感じだね。

（その2があれば）つづく

2019-12-19

論文読みメモ： Nonparametric density estimation in compound Poisson process using convolution power estimators（その1）

論文読み

以下の論文を読みます。

F. Comte, C. Duval, V. Genon-Catalot. Nonparametric density estimation in compound Poisson process using convolution power estimators. Metrika, Springer Verlag, 77 163–183, 2014.
https://hal.archives-ouvertes.fr/hal-00780300/document

※ キャラクターは架空のものです。解釈の誤りは筆者に帰属します。お気付きの点がありましたらご指摘ください。

次回：まだ

$(\xi_j, j \geqq 0)$ を独立に同一の確率密度 $f$ にしたがう実数値確率変数とし、 $(N_t)$ を強度 $c>0$ のポアソン過程として、複合ポアソン過程 $(X_t, t \geqq 0)$ は以下のように表せるということです。

$\displaystyle X_t = \sum_{i=1}^{N_t} \xi_i \tag{1}$ これはつまり、時刻 $t$ までに隕石が庭に降ってくる回数 $N_t$ が強度 $c$ のポアソン過程にしたがい、個々の隕石の質量 $\xi_i$ は独立に確率密度 $f$ にしたがうというときに、時刻 $t$ までに庭に降ってくる隕石の質量の総和ですね。

喩えが大災害だな…。

しかし、隕石がいつ庭に落ちてくるかずっと監視しているほど暇ではありませんので、一定時間間隔 $\Delta$ ごとに、その時点までに降ってきた隕石の総質量 $(X_{j \Delta}, j \geqq 0)$ が観測されるのみとしましょう。このときに隕石の質量がしたがう確率密度 $f$ を推測するのが今回のやりたいことですね。無論 $c$ も $f$ も未知です。

いや庭に隕石が振ってきたら気付くよね普通…。

複合ポアソン過程はレヴィ過程の特別な場合で、レヴィ密度が $cf(\cdot)$ の場合に相当します。なので、もし $c$ が既知ならば $f$ の推定はジャンプのみからなるレヴィ過程のレヴィ密度の推定に等しいと。これについてはこれまでに多くの論文で取り扱われているとあります。しかし、複合ポアソン過程に特化した推定手法も研究されていて、Buchmann and Grübel (2003) は初めて特に $f$ を推定する手法を考案したのですかね？実際、1回の観測間隔の増分 $X_\Delta$ の確率密度は以下のようになるということです。

$\mathbb{P}_{X_\Delta}(dx) = e^{-c\Delta} \delta_0 (dx) + (1 - e^{-c\Delta}) g_\Delta (x) dx \tag{2}$ ただし $g_\Delta$ は $X_\Delta$ が $0$ でない下での条件付き分布であって、
$\displaystyle g_\Delta = \sum_{m \geqq 1} \frac{e^{-c\Delta}}{1 - e^{-c\Delta}} \frac{(c \Delta)^m}{m!} f^{\ast m} \tag{3}$ $f^{\ast m}$ は $f$ の $m$ 次の畳み込み（合成積）であるということですが…なんでこうなるんですか？

まず時刻 $\Delta$ までに隕石の降ってくる回数 $m$ がしたがう確率分布は $P(N_\Delta = m) = e^{-c\Delta} (c \Delta)^m / m!$ だから、時刻 $\Delta$ までに1個も隕石が振ってこない確率は $P(N_\Delta = 0) = e^{-c\Delta}$ で、1個以上隕石が振ってくる確率は $P(N_\Delta \geqq 1) = 1 - e^{-c\Delta}$ だね。さらに $m \geqq 0$ 回隕石が振ってくるとき、その質量の和 $\xi_1 + \xi_2 + \cdots + \xi_m$ がしたがう密度関数は、 $f$ を $m$ 回畳み込んだ関数になる。…あたりをつかえば、 $(2)$ と $(3)$ が成り立つことが容易にわかるよ。

合成積（畳み込み）の意味と応用３つ | 高校数学の美しい物語

だから増分 $X_\Delta$ をたくさん観測しても $X_\Delta = 0$ のデータについては $f$ を知る上で「何の足しにもならない」…その $\Delta$ 間に隕石が降ってこなかったら隕石の質量がしたがう分布について何も得るものがないのは当然だよね。だから van Es et al. (2007) はゼロでない観測だけ抜き出したらしい。以下のようにすれば増分がゼロでないインデックス $S_i$ だけ取ってこれるね。
$S_1 = {\rm inf} \{j \geqq 1, X_{j \Delta} - X_{(j-1)\Delta} \neq 0 \} , \quad S_i = {\rm inf} \{j > S_{i-1}, X_{j \Delta} - X_{(j-1)\Delta} \neq 0 \} \tag{4}$
$Z_i = X_{S_i \Delta} - X_{(S_i - 1) \Delta} \tag{5}$ こうして $(S_i, Z_i) \, (i = 1, \cdots, n)$ を集めれば、 $Z_1, \cdots, Z_n$ は $X_\Delta$ が $0$ でない下での条件付き分布 $g_\Delta$ にしたがう。解くべき問題は「確率密度 $g_\Delta$ からの $n$ 個のサンプルから $f$ を推定する」にブレークダウンされたわけだ。

van Es et al. (2007) は $c$ が既知で $\Delta = 1$ のケースについて、 $f$ の特性関数と $g_\Delta$ の特性関数の関係を利用して $f$ の推定量を構築したんですね。Duval (2012a) はまた別の推定量を考えたようです。変換 $f \to g_\Delta := P_\Delta f$ は明示的に逆変換できるので $f = P_\Delta^{-1} g_\Delta$ でよいと。 $c\Delta < \log2$ を仮定すれば $P_\Delta^{-1}$ は以下の級数で与えられるそうです。

$\displaystyle P_{\Delta}^{-1} (g) = \sum_{m \geqq 1} \frac{(-1)^{m+1}}{m} \frac{(e^{c\Delta} - 1)^m}{c \Delta} g^{\ast m} \tag{6}$ 実際には $K+1$ 項目まででトランケートして以下を推定量とすると。
$\displaystyle f \cong \sum_{m \geqq 1}^{K+1} \frac{(-1)^{m+1}}{m} \frac{(e^{c\Delta} - 1)^m}{c \Delta} g_{\Delta}^{\ast m} \tag{7}$ $\Delta$ が小さい場合はこの近似は有効であるということですが…なぜこうなるんでしょう？

…合成積ってフーリエ変換すると、合成積する前の関数のフーリエ変換の積になるよね。そう考えると、 $(3)$ って両辺をフーリエ変換すれば右辺がエクスポネンシャルのマクローリン展開にみえる。そう考えて式変形すると以下までたどり着けるかな。

$\displaystyle \mathcal{F}[f] = \frac{1}{c\Delta} \log \left( 1 + \frac{1 - e^{-c\Delta}}{e^{-c\Delta}} \mathcal{F}[g_\Delta] \right)$ そしたらこれをもっかいマクローリン展開すればいい。 $\displaystyle \mathcal{F}[f] = \frac{1}{c\Delta} \sum_{m \geqq 1} \frac{(-1)^{m+1}}{m} (e^{c\Delta} - 1)^m \mathcal{F}[g_\Delta]^{m}$ これを逆フーリエ変換すれば $(6)$ を得るね。

マクローリン展開 log(1+x)

普通に Duval (2012a) の原論文もみられるから貼っておくね。27～28ページのところでやっぱりフーリエ変換しているよね。

[1203.3135] Adaptive wavelet estimation of a compound Poisson process

そういうわけで、 $g_{\Delta}^{\ast m}$ を $Z_1, \cdots, Z_n$ から推定すればいいことになったけど、これはこれでそう簡単でもないっぽいな。Duval は wavelet threshold estimator というのを構築したらしい。 $g_{\Delta}^{\ast m}$ は $g_{\Delta}$ にしたがう確率変数 $m$ 個の和がしたがう密度なんだから、 $m$ 個の観測の和をとって推定したのかな？これはこれで収束性はよいみたいだけど、 $Z_1, \cdots, Z_n$ から $m$ 個のサンプルの和をつくるのは計算コストがかかると。だからこの論文では $(7)$ を利用するけど $g_{\Delta}^{\ast m}$ の推定手法は変えるらしい。

なるほど…先に進むと、以降、 $g_\Delta, \,g_{\Delta}^{\ast m}$ を表記するとき $\Delta$ を省くとあります。そして、「確率密度 $g$ からの $n$ 個のサンプルから、 $g^{\ast m} \, (m \geqq 2)$ の『 $\sqrt{n}$ -consistent nonparametric estimator』がつくれることはよく知られている」とありますね。これはどういう意味ですか？私によく知られていないんですが。

特に最近 Chesneau et al. (2013) がシンプルな推定量を提案したとあって以下に続くのがその方法なんじゃないかな。 $g^\ast$ を $g$ のフーリエ変換、 $(g^\ast)^m$ を $g^{\ast m}$ のフーリエ変換とするよ（ややこしいな）。この合成フーリエ変換（？） $(g^\ast)^m$ に対し、経験合成フーリエ変換（？） $(\tilde{g}^\ast)^m$ を以下で定義する。

$\displaystyle \tilde{g}^\ast(t) = \frac{1}{n} \sum_{j=1}^n e^{it Z_j} \tag{9}$ 本当は $g^\ast = \int g(x) e^{itx} dx$ なのを経験分布上での平均にした版だね。そして $(9)$ の $m$ 乗を逆フーリエ変換して $g^{\ast m}$ の推定量を得る。このときカットオフを $\ell$ として積分区間を $[-\pi \ell, \pi \ell]$ とするみたいだね。 $\displaystyle \widehat{g_{\ell}^{\ast m}} (x) = \frac{1}{2\pi} \int_{-\pi \ell}^{\pi \ell} e^{-itx} \bigl( \tilde{g}^\ast (t) \bigr)^m dt \tag{10}$ これをそのまま $(7)$ に代入すればいい。 $\displaystyle \widetilde{f_{K, \ell}}(x) = \sum_{m \geqq 1}^{K+1} \frac{(-1)^{m+1}}{m} \frac{(e^{c\Delta} - 1)^m}{c \Delta} \widehat{g_{\ell}^{\ast m}} (x) \tag{11}$

おお、これで隕石の質量がしたがう分布 $f$ が手に入り…ませんね。副部長、いま隕石が到着する頻度の強度 $c$ は未知です。右辺に $c$ があっては駄目でしょう。

いやだからまだこれは $f$ の推定量 $\widehat{f_{K, \ell}}(x)$ じゃないよ。 $\displaystyle c_m(\Delta) = \frac{(e^{c\Delta} - 1)^m}{c \Delta}$ にも何か推定量 $\widehat{c_m(\Delta)}$ をつくるみたいだね。以降で、 $\widehat{f_{K, \ell}}$ のL2リスクと、データに応じた $\hat{\ell}$ の選択方法が示されるみたいだよ。2節で $\widehat{c_m(\Delta)}$ をつくってそのL2リスクを議論して、3節で Chesneau et al. (2013) の合成確率密度の推定を復習して、4節で $f$ の推定とL2リスクを議論して、5節でさまざまな分布に対してシミュレーションして、6節がまとめ、7節に定理の証明が集められているのかな。

え、ああ、まだイントロダクションだったんですね…普通に番号付きの数式がどんどん出てくるのでてっきりもう本論に入っているのかと…。それでようやく2節に進むと、この節は Proposition 2つからなっていますね。1つ目の Proposition の主張は、 $k \geqq 1$ に対して、以下が成り立つということですか？

$\mathbb{P}(S_1 = k, Z_1 \leqq x) = e^{-c(k-1) \Delta} (1 - e^{-c \Delta}) \mathbb{P} (X_\Delta \leqq x | X_\Delta \neq 0)$ この数式は日本語訳するならば、

　「初めてゼロでない質量を観測するインデックス $S_1$ が $k$ に等しく、かつそのとき観測された質量が $x$ 以下である確率」は、
　「k-1回目までの観測ですべて『隕石が1個も降ってこない」を引く確率」
　×「k回目の観測で『隕石が1個は降ってくる』を引く確率」
　×「その観測での増分がゼロでない条件の下で、その観測の増分 $Z_1$ が $x$ 以下である確率」

に等しいということですね。したがって、初めてゼロでない質量を観測するインデックス $S_1$ と、そのとき観測される質量 $Z_1$ は独立だと。そして $S_1$ はパラメータが $1 - e^{-c \Delta}$ の幾何分布にしたがうと。これはそうなりそうですね。2つ目の Proposition の主張は、 $c \in [c_0, c_1], \, c_0 > 0, \, c_1 \Delta \leqq \log(2)/2$ として、 $1$ 以上の $m$ に対して次の $(12)$ $(13)$ を定義すると、 $\displaystyle H_m(\xi) = \frac{1}{(\xi - 1)^m \log \frac{\xi}{\xi - 1}} \tag{12}$
$\displaystyle \widehat{c_m(\Delta)} = H_m(S_n / n) {\bf 1}_{ \left\{1 + \frac{1}{e^{2 c_1 \Delta} -1} \leqq \frac{S_n}{n} \leqq 1 + \frac{1}{e^{c_0 / (2\Delta)} -1} \right\} } \tag{13}$ 以下が成り立つということですね。 $C_m$ は $c_0, c_1, m$ の関数であるそうです。 $\displaystyle \mathbb{E} \left( \widehat{c_m(\Delta)} - c_m(\Delta) \right)^2 \leqq C_m \frac{\Delta^{2(m-1)}}{n} \tag{14}$ つまり $\widehat{c_m(\Delta)}$ は漸近的ではなく普通に $c_m(\Delta)$ との2乗誤差が上式で抑えられる推定量になっているということですが…この関数をいきなりみてもどうしてこうなったのやらですね…。

証明は 9 ページにあるね。まず $p(\Delta) = 1 - e^{-c\Delta}$ とおいている。これは $\Delta$ 間に「『隕石が1個は降ってくる』を引く確率」だね。これは、 $\displaystyle c \Delta =- \log \bigl( 1 - p(\Delta) \bigr) = \log \left( \frac{p(\Delta)^{-1}}{p(\Delta)^{-1} - 1} \right)$ の関係がある。そうすると、 $\displaystyle c_m(\Delta) = \frac{(e^{c\Delta}-1)^m}{c \Delta} = \frac{(e^{c\Delta}-1)^m}{\log \left( \frac{p(\Delta)^{-1}}{p(\Delta)^{-1} - 1} \right)} = \frac{1}{\bigl(p(\Delta)^{-1}-1 \bigr)^m \log \left( \frac{p(\Delta)^{-1}}{p(\Delta)^{-1} - 1} \right)} = H_m \bigl( p(\Delta)^{-1} \bigr)$ となる。 $h_m$ は $\Delta$ 間に「『隕石が1個は降ってくる』を引く確率」（の逆数）を求める量に変換してくれる関数だったってだけだね。そして、 $\Delta$ 間に「『隕石が1個は降ってくる』を引く確率」の最尤推定量は $n / S_n$ になる。 $S_n$ は「隕石が1個は降ってくる」を $n$ 回観測するのに費やした観測の回数だからね。だから $\widehat{c_m(\Delta)} = H_m(S_n / n)$ としたいけど、 $S_n / n$ は $1$ になりうるのでこれはできない、か。確かに観測する度に隕石が1個以上落ちているケースだと、隕石が落ちたインデックスから強度を逆算しようとしても「常に隕石が落ちてる」にしかならないね。 $S_n / n$ が $1$ より大きくないと困る。だから、真の強度が入っている区間を $[c_0, c_1]$ だろうということにしておいて、観測された $S_n / n$ が想定される範囲をずれていたら $\widehat{c_m(\Delta)}$ はゼロにしてしまうという回避策を入れたみたいだ。実際、 $c_m(\Delta)$ は強度が大きいとゼロに近づくし…ただ、 $\widehat{c_m(\Delta)} = 0$ だと $f$ の推定はできなさそうだな…。

その推定方法で目的の量を推定した結果を貼っておきます。いまサンプルの強度しか関係しないので単なるポアソン過程を生成しました。まあこれだけだとだから何なんですが…。

つづいたらつづく

gist570484df18205751f859829b82b25d0f

2019-12-17

雑記： NeurIPS 2019 Proceedings の「不確か」を含むタイトル

雑記

キャラクターは架空のものです。何かありましたらご指摘いただけますと幸いです。

参考文献

NeurIPS 2019 Proceedings

NeurIPS 2019 Proceedings のサイトをみるとタイトルに uncertain を含む発表が…17件もありますね。上から順にメモしていきますか…面倒ですが…。なお、現時点でクリック先で閲覧できるアブストラクトを一通り読んだのみの直感的な理解であることに留意ください。

Correlated Uncertainty for Learning Dense Correspondences from Noisy Labels
Natalia Neverova, David Novotny, Andrea Vedaldi

ノイジーなラベルから密な対応を学ぶために不確かさを利用するんでしょうか？機械学習モデルは基本的に人間が作成した教師データに基づいて学習しますが、DensePose のような場合はアノテーションに限界があるといっていますね。この DensePose というのはサイト上の画像をみるに「ある幼児の体の表面のこの座標がある大人の体の表面のこの座標に対応している」のような対応を取るものなんでしょうか。それは確かにアノテーションし切れませんね…。なので、ニューラルネットの出力としてラベルだけでなくラベルにわたる分布も出すようにして、アノテーションの不確かさを捉えるようにした…？先行手法に比べて、どこで誤るかの相関も捉えているということですが、これって例えば肩のある点で対応が誤っていたら、肩から少しずれたところでも対応が誤っているだろう、ということなんでしょうか。それで、DensePose のタスクをより正確に解くことができたと。また、複数のモデルを組み合わせてより精度を向上させた例も紹介されているとのことです。

Verified Uncertainty Calibration
Ananya Kumar, Percy S. Liang, Tengyu Ma

天気予報やパーソナライズ度な薬の需要予測では確率が正しく推測されるようにキャリブレーションをするということですが、多くのモデルでこのキャリブレーションは out of the box になされているのではなくモデル出力へのポスト処理としてなされているということです…？この out of the box にやってないとは「ちゃんとやってないよね？」という意味なんでしょうか…。例えばよく知られている「Platt scaling」や「temperature scaling」という手法は実は報告よりキャリブレーションされておらず、自分たちがどれだけ誤っているかに気付けないと…えぇ…。「histogram binning」というどれだけ誤っているか計測できる手法もあるんですが、これはこれで精度を出すには膨大なサンプル数を必要とするようですね。だから「scaling-binning calibrator」を提案するそうです。まずパラメトリックな関数をフィッティングして、次にその値を適切に bin で切るのですかね？そうするとサンプル数がより抑えらえるそうです。でもこれでもサンプルが最小で済むというわけではないのですかね…suboptimal とあります。それで、CIFAR-10 と ImageNet で実験して histogram binning よりも 35% 低いキャリブレーションエラーを達成したとあります。

Modeling Uncertainty by Learning a Hierarchy of Deep Neural Connections
Raanan Yehezkel Rohekar, Yaniv Gurwicz, Shami Nisimov, Gal Novik

ニューラルネットで不確かさもモデリングするのにベイジアンニューラルネットは有力な方法ですが、ネットワークの重みの事前分布の選択が必要になり、正規分布や疎性が利用できる分布がよく選択されるということですね。しかしこれらのような事前分布はデータの生成プロセスに agnostic、まあデータの生成プロセスを無視しており、訓練データから外れたテストデータに不適切な推測をしてしまう恐れがあると。不適切というのはそのようなデータについてはまだ何もわからないはずだというデータに何か自信満々に推測してしまうといったことなのでしょうか。それなら何となくわかるような気はしますが。それで、入力データと識別関数に交絡因子がある？だからその交絡因子もモデリングする？生成ネットワークと識別ネットワークがネットワークの結合っぷりを共有するというように読めますが…。それでなんか最終的に事後分布に応じてヒエラルキーからサンプリングするとあるんですが、ヒエラルキーということは最終的なモデルの中にも社長さん、部長さん、課長さん、平社員さんがいらっしゃるのでしょうか…。タイトルからするとネットワーク結合にヒエラルキーがあるというので「この結合は社長さん」ということですか…？？

Propagating Uncertainty in Reinforcement Learning via Wasserstein Barycenters
Alberto Maria Metelli, Amarildo Likmeta, Marcello Restelli

「価値関数の不確かさはどのように伝播していくだろうか？」と始まっていますね。囲碁や将棋のAIでは盤面の価値を評価しますけど、そのような価値の不確かさですよね。この論文ではベイズ手法で価値関数の不確かさをモデリングして、ワッサースタイン重心の伝播をみるとあります。さらに Wasserstein Q-Learning (WQL) というアルゴリズムを考案すると。この WQL は適当な仮定の下で理論的に望ましい性質をもつということですが…？ Atari ゲームでの実験でも WQL の有効性を示しているようですね。

Uncertainty-based Continual Learning with Adaptive Regularization
Hongjoon Ahn, Sungmin Cha, Donggyu Lee, Taesup Moon

Uncertainty-regularized Continual Learning (UCL) なる新しい継続学習のアルゴリズムを提案するとのことです。変分推論をベースにしているようです。正則化に基づく手法では、正則化の強さを決めるメモリコストの問題や、忘却する性能に欠ける問題があるそうですが、UCL は KL ダイバージェンス項を平均場近似の変分下限と解釈してこれらの問題を克服したと…？そもそも継続学習というのがよくわかっていませんが、学習し続けるのだから状況が変化したときはさっぱり忘れて新しく学習するべきといった感じなのでしょうか。2つの問題の後者については、重要なパラメータの値を維持してモデルを安定させる正則化項と、新しいタスクを学ぶための正則化項を新しく導入したようですね。実験でも UCL の有効性を実証しています。ソースコードへのリンクもありますね。

副部長、今回は5件ごとに背景色変えたいんでここで交代してください。

私たちは背景色みたいな概念に agnostic でないといけないんじゃないのかな…。

Successor Uncertainties: Exploration and Uncertainty in Temporal Difference Learning
David Janz, Jiri Hron, Przemysław Mazur, Katja Hofmann, José Miguel Hernández-Lobato, Sebastian Tschiatschek

Posterior sampling for reinforcement learning (PSRL) という、強化学習で効果的に探索と利用のバランスを取る手法があると。さらに Randomised value functions (RVF) というのが PSRL をスケールさせる有力な手段とみられているらしいけど、ニューラルネットにそれを組み合わせても PSRL の性質は上手く発揮されなかったらしい。不確かさの伝播でもっても駄目だったって。だから Successor Uncertainties (SU) という RVF の実装方法を考案すると。これはニューラルネットワークなのかな？？まあそれで SU は Atari ゲームで人間とか Bootstrapped DQN とかを上回ったって。

Single-Model Uncertainties for Deep Learning
Natasa Tagasovska, David Lopez-Paz

「偶然な不確かさ」と「わかっている不確かさ」を1つのモデルでモデリングするみたいだね。前者の不確かさに対しては、Simultaneous Quantile Regression (SQR) っていうので目的変数のクオンタイルを捉えるらしい。後者の不確かさに対しては、Orthonormal Certificates (OCs) っていう、全ての訓練データを 0 に移す関数を用意して、これで 0 に移されなかったら out-of-distribution であるシグナルになると。なるほど、それなら「訓練データになかったから知らないよ」とわかるね。それらの工夫で不確かさも含めたモデリングをアンサンブルなしで実現したらしい。まあ別にモデルのアンサンブルが必要となってそこまですごい困るってわけでもないと思うけど、不確かさのモデリングをアンサンブルに丸投げせずにきちんと考えるってのは大事そうだな…。

Accurate Uncertainty Estimation and Decomposition in Ensemble Learning
Jeremiah Liu, John Paisley, Marianthi-Anna Kioumourtzoglou, Brent Coull

お次はアンサンブルか。Bayesian nonparametric ensemble (BNE) という手法を提案するらしい。これも色んなとこからくる不確かさを考慮するっていってるな…。その色んなとこってどこなんだろう。noise と error ってことなのかな。さっきの論文でいう「偶然な不確かさ」と「わかっている不確かさ」に相当しそうだけどやっぱりしないのかな。error っていうのは損失があるとわかっているけど表現力の限界で埋められないといったイメージがあるな…わからないけど。まあそれで、不確かさをロバストに推定できる理論的な保証もあるらしい。あと、不確かさをそのソース別に分解もできるんだって。大気汚染のデータで実験して有効性を示しているらしい。

CXPlain: Causal Explanations for Model Interpretation under Uncertainty
Patrick Schwab, Walter Karlen

feature importance はその特徴がモデル出力にどれくらい影響するかを推定した量で、モデルを評価したり解釈したりするのに重要だけど、高次元データの feature importance の高速な推定やその不確かさの推定は課題として残っているとあるね。そこで、機械学習モデルの判断を解釈するのを因果学習のタスクと捉えて、causal explanation (CXPlain) なるモデルを学習するらしい。CXPlain は対象の機械学習モデルにある入力を入れるとどんな出力をどれくらい出てきそうかをモデリングするのかな？ CXPlain を一旦学習すればそれを利用して簡単に対象の機械学習モデルを説明できると。ブートストラップアンサンブルによって feature importance の不確かさも定量評価できるらしい。テストデータにおける feature importance も上手く予測できるのかな？

Adaptive Temporal-Difference Learning for Policy Evaluation with Per-State Uncertainty Estimates
Carlos Riquelme, Hugo Penedones, Damien Vincent, Hartmut Maennel, Sylvain Gelly, Timothy A. Mann, Andre Barreto, Gergely Neu

on-policy で trajectory データのバッチから価値関数を推定することを考える。TD手法とモンテカルロ手法の様々な問題に焦点を当てると。TD法はバリアンスは小さいがバイアスは大きい傾向があるらしい。モンテカルロ手法はその逆なのかな？それで、TD法のバイアスは局所近似の誤差が増幅された結果で、各状態において適応的に TD かモンテカルロかスイッチするモデルで誤差が軽減されるんだって。このスイッチ式の手法だと学習の信頼区間から TD のバイアスを検知できるっていってるのかな？まあ性質の異なる2つのモデルをそれぞれの得意な場面でだけつかうようにできるのならそれはよさそうだよね。

ここまでで10件だね。うち4件目、6件目、10件目が強化学習だけどこれらはもうわかんないな…。

11～15件目です。

Uncertainty on Asynchronous Time Event Prediction
Bertrand Charpentier, Marin Biloš, Stephan Günnemann

未来に発生するイベントを予測するようなときに、遠い未来のできごとは自信がないはずだから、不確かさを捉えるのは大切だということでしょうか？？それで、WGP-LN と FD-Dir というモデルを提案するようですね。それぞれ probability simplex 上の分布にロジット正規分布とディリクレ分布をつかうと。probability simplex というのがよくわからないですが逆にいうとディリクレ分布がその上に分布しているというようなのが probability simplex なのでしょうね。ディリクレ分布は確率分布たちの上の確率分布ですね。これらの分布が時間に依存するということです。RNN を Gaussian process または function decomposition と組み合わせて分布のパラメータの時間発展を表現するようですね。これ、遠い未来の予測ほどロジット正規分布とディリクレ分布の確率密度が無情報な分布のところに集まっていてほしいということですよね…？まあそれで提案モデルは色々なタスクでの実験でハイパフォーマンスを発揮したそうです。

A Simple Baseline for Bayesian Uncertainty in Deep Learning
Wesley J. Maddox, Pavel Izmailov, Timur Garipov, Dmitry P. Vetrov, Andrew Gordon Wilson

SWA-Gaussian (SWAG) なる、シンプルでスケーラブルで汎用的な不確かさのモデリング＆キャリブレーション手法を提案するそうです。SGD による学習時に Stochastic Weight Averaging (SWA) という手法を用いるとニューラルネットの汎化性能の向上に寄与するらしいですが、SWAG はどうもそれにガウシアンな不確かさを加味した版ですね。SWAG で out-of-sample の検知や、キャリブレーションや、転移学習も上手くできるらしいです。比較した手法として変分推論や MC dropout、KFAC Laplace、temperature scaling などの名前が挙がっていますね。

On Mixup Training: Improved Calibration and Predictive Uncertainty for Deep Neural Networks
Sunil Thulasidasan, Gopinath Chennupati, Jeff A. Bilmes, Tanmoy Bhattacharya, Sarah Michalak

Mixup というのは近年提案された、訓練中に追加的にサンプルを生成するニューラルネットワークの訓練手法であるそうです。ランダムなデータのペアを合成して新しいデータとするのですかね。シンプルなのに画像分類におけるデータの増強に驚くほど効果を発揮するそうです。しかしこれまで Mixup で訓練したモデルのキャリブレーションについては触れられてこなかったと。なんと、Mixup で訓練したモデルはよくキャリブレーションされていたとのことです。つまり、モデルが出力する softmax スコアは実際の尤度をよく表現していたと。また、単に特徴を混合したのでは同じようなよいキャリブレーションは得られず、したがって Mixup でのラベルスムージングが重要な役割を果たしていたといえると指摘しています。さらに、Mixup で訓練したモデルは out-of-distribution や random-noise データに over-confident になりにくかったともありますね。そんなこんなで、ニューラルネットの典型的な overconfidence はハードラベルによる学習からくると結論付けています。

Can you trust your model's uncertainty? Evaluating predictive uncertainty under dataset shift
Jasper Snoek, Yaniv Ovadia, Emily Fertig, Balaji Lakshminarayanan, Sebastian Nowozin, D. Sculley, Joshua Dillon, Jie Ren, Zachary Nado

「モデルの不確かさを信頼できますか？」とは語りかけてくるタイプのタイトルですね…。不確かさを取り扱う深層学習手法はベイズ手法であるものないもの色々提案されていますが、著者らの知る限りでは、これらの手法について厳密なデータのシフトへの性能が比較されていないと。そこで分類タスクの SOTA な手法たちについてデータのシフトが精度やキャリブレーションに与える影響を調査したとのことです。実際、伝統的（？）なキャリブレーション手法は性能がよくなかったそうです。しかしいくつかの手法は様々なタスクですばらしい性能をみせたと。

Reverse KL-Divergence Training of Prior Networks: Improved Uncertainty and Adversarial Robustness
Andrey Malinin, Mark Gales

アンサンブルによる不確かさの推定は誤分類の検知や、out-of-distribution の検知や、敵対的攻撃の検知に応用されていると。Prior Network というのも事後分布たちの上のディリクレ分布をパラメタライズすることで分類モデルのアンサンブルを抽出できると。これらのモデルは out-of-distribution に対する性能で MC-Dropout などの比較手法を上回っていると。しかし、Prior Network は分類するクラスが多いとき同じ学習方法だとスケールしない？よくわかりませんが、クラスが増えると事後分布たちの空間がどんどん大きくなりそうな感じはしますね。そこでこの論文では、ディリクレ分布間の reverse KLダイバージェンスというのをつかって適切な学習を実現したそうです。さらにこの論文では、Prior Network を利用した敵対的攻撃の検知とか敵対的トレーニングの一般化もやっているそうです。提案手法によって CIFAR-10 や CIFAR-100 で学習したモデルを攻撃するには、他の敵対的トレーニングをしたモデルや MC-Dropout よりもとても苦労したと。

…しかし、Mixup がキャリブレーションに有効かどうかもまたデータドメインによりそうですよね？それをいい出すと全てのモデルが有効かどうかはデータドメインによりますが…。しかし、「不確かさ」パートには「既存手法のこんな側面には焦点が当てられてこなかった」という論文がちょいちょい見受けられますね。

最後16、17件目が以下だね。

Bayesian Layers: A Module for Neural Network Uncertainty
Dustin Tran, Mike Dusenberry, Mark van der Wilk, Danijar Hafner

「ベイジアン層」というのを提案するらしい。ベイジアンニューラルネット層とか、Dropout層とか、確率的アウトプット層とか、ガウス過程層とかかかれているけど、既存のニューラルネットの対応する層をこれらに置き換えろって話なのかな？機械翻訳タスクで実験したみたい。

Using Self-Supervised Learning Can Improve Model Robustness and Uncertainty
Dan Hendrycks, Mantas Mazeika, Saurav Kadavath, Dawn Song

self-supervised learning はラベルを必要としない便利な方法だけど、アノテーションの手間が省ける以上のメリットは世間一般に認識されていない、っていってるね。でも、著者らは敵対的サンプルや、ラベルの腐敗（どう訳すのかな）や、common input の腐敗に対するロバスト性とかがあるのを発見したと。さらに out-of-distribution の検知もできて、完全な教師あり学習のパフォーマンスを凌駕したと。

つづかない