2019-05-28

ベイズ統計の理論と方法：ノート4章その0.1

本読み機械学習

以下の本を読みます。キャラクターは架空のものです。解釈の誤りは筆者に帰属します。おかしい点がありましたらコメント等でご指摘いただけますと幸いです。

ベイズ統計の理論と方法

作者: 渡辺澄夫
出版社/メーカー: コロナ社
発売日: 2012/03/01
メディア: 単行本
購入: 1人クリック: 4回
この商品を含むブログ (8件) を見る

書籍サポートページ

これまで：ノート1 ／ノート2 ／ノート2.5 ／ノート3

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

というわけで4章にとびます。

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

なんで！？

勉強会で4章の前半を担当するので準備しないといけないんですが、なんかこの箇所はただ数学であって、それまでの内容に依存していなさそうなので先に読んでおいてもよさそうな気がしたんですよね。

本当かなあ…。

85ページから読んでいくと、4章ではベイズ推測の事後分布が正規分布で近似できない場合の理論を取り扱っていくのですね。35ページのベン図でいうと、「正則」の丸の中で何が成り立つのかを3章でやって、次に「相対的に有限な分散をもつ」の丸の中で何が成り立つのかを4章でやろうというところだと思います。3章をまだ読んでいませんが。それで、4章の前半は数学的準備なのですが、何を目指して準備するのかを把握しておきたいですね。4章の序文にこの章で目指すことが4点紹介されています。まず (1) は、経験誤差の $n$ 倍である $nK_n$ 、つまり各サンプルの対数尤度比の和がある形にかけると主張していますね？正規確率過程って何ですか？

ガウス過程のことかな？索引によると210ページだね…210ページの $\xi(w)$ は $w$ を添え字とするガウス過程だね。

ということは、あるパラメータ $w$ における各サンプルの対数尤度比の和は、それを何らかの写像 $g^{-1}(\cdot)$ で変換したパラメータ $u$ の式でかける確率変数であり、その確率的なファクター $\xi_n(u)$ はサンプル数が多いときガウス過程に近いと…うーん、そもそも正則な場合はどうだったのかもわからないし何を思えばいいのかわかりません。

正則の場合の経験誤差 $K_n$ のふるまいは70ページがそうなのかな（最終目標は経験誤差じゃなくて汎化損失 $G_n$ と経験損失 $T_n$ のふるまいだけど）。この $J$ は平均対数損失 $L(w)$ 、つまり真の分布と確率モデルの交差エントロピーのヘッセ行列だね（52ページ）。実現可能で正則なケースではこれが単位行列なのか（65ページ）。3章での $\xi_n$ は60ページをみると、各サンプルの「平均誤差 $K(w)$ と対数尤度の差」の和の $n^{-1/2}$ 倍の最適なパラメータ $w_0$ におけるナブラに $J^{-1/2}$ をかけたもので、正規分布に分布収束するらしい（60ページ）。たぶんだけど、パラメータ空間で最適なパラメータが深い谷になってるほど $\xi_n$ はあまりばらつかなくて、最適なパラメータが浅い谷になってるほど $\xi_n$ もばらつくのかな…。

正則であろうとなかろうと、汎化損失 $G_n$ や経験損失 $T_n$ のふるまいを知りたいとき先に経験誤差 $K_n$ のふるまいを考えるらしいということしかわかりませんね。 $T_n$ の1次キュムラントが最適パラメータにおける経験対数損失 $L_n(w_0)$ と経験誤差 $K_n$ のパラメータ平均の和のマイナス1倍で表せるからでしょうか…というか2章もまだ前半しか読んでなかったですね。

それで4章の序文を理解するのは無理でしょ…さしあたり4章の目指すところは、正則でない場合の (1) 経験誤差のふるまい、(2) 自由エネルギーのふるまい、(3) 汎化損失の分布、(4) ベイズ推測でない推測方法の場合の性質―を考える、ってことでいいんじゃないかな。

もどかしいですがそれで手を打つよりないですね…ん？ (4) のところにちょっと気になることがかいていませんか？「平均プラグイン推測では、漸近的にも真の分布が推測できない」って、漸近的にも無理とか推測手法としてどれだけ駄目なんですか？平均プラグイン推測の何がそれほどの欠陥なんですか？？

いや、正則でない場合って普通に悪条件だと思うからそこまでいわなくても…まあでも125ページをみると何が欠陥なのかは簡単だ。最適なパラメータが「凸集合じゃない」から。そりゃ平均をとっちゃ駄目でしょって話だ。最適なパラメータがドーナツ状に分布してたら、その平均（重心）はドーナツからはみ出すからね。いくらサンプルを増やしてもこれは解決しない。

なるほど。逆に他の推測方法ではそのような事態にはならないんですね。 $w$ の何らかの関数の最大点を取るとか $w$ の分布で確率モデルを平均するということをすれば大丈夫ということなんでしょうか。…序文の続きをみると、事後分布による平均操作って経験誤差 $K_n$ でこんな風にかけるんですか？

事後分布は元々対数尤度でかけるし、そこを対数尤度比にしてもいいよ。最適なパラメータにおける尤度で割ることになっちゃうけど、正規化定数の方も割ってるから問題ないね。

いわれてみればそうですね。それでだから事後微小積分を考える？確かにベイズ推測とは事後分布による確率モデルの平均ですが…正則でない場合には事後分布は特異点を含んでいる？特異点というのはSIREN2で主人公が最後に飛ばされる舞台のことですか？

違うかな。特異点の定義は文脈依存だと思うから読んでいけばいいと思う。まあでも、正則でないときにはパラメータ空間内で損失が何かしら滑らかでないことになってるんだろう。でもベイズ推測の性質を調べるためにはそこを滑らかにしたくて…だから多様体か。というか特異点解消定理をつかうんだね。あ、特異点解消定理で検索したら著者の方のページが出てきたよ。

特異点の解消

そのページをみると結び目がほどけたような…というか広中の定理というのをみて「誰？」と思ったんですが「日本人なら誰でもよく知っている」とは圧が強いですね…。しかし何となくは4章のモチベーションがわかった気がします。本編に入っていきましょう。…すみません、開集合って一般の集合に定義されるんですか？開集合とは数直線上で端っこが白丸の区間といった理解なんですが…。

定義されるっていうかルールを満たすように決めていいんだよね。ある集合 $\mathcal{M}$ のべき集合の部分集合 $\mathcal{O}$ であって、【１】 $\emptyset$ も $\mathcal{M}$ も $\mathcal{O}$ の元で、【２】 $\mathcal{O}$ の有限個の元の共通部分もまた $\mathcal{O}$ の元で、【３】 $\mathcal{O}$ の任意の個数の元の和集合もまた $\mathcal{O}$ であるような $\mathcal{O}$ であれば開集合全体として認めてもらえるんだよね。

位相空間 - Wikipedia

例えばだけど、｛りんご、みかん、ぶどう｝という集合があったとして、「この集合の任意の部分集合を開集合とする」と決めてもいいし、「空集合と全体集合のみを開集合とする」と決めてもいいよ。

はあ。え、ん？あの、任意の部分集合を開集合とする場合、｛りんご｝も開集合で｛みかん、ぶどう｝も開集合なのですよね？しかし、そのウィキペディアの記事にもあるように、補集合が開集合であるような集合は閉集合なのではないのですか？どちらかは閉集合でなければおかしくないですか？

いや、だから、｛りんご｝も｛みかん、ぶどう｝も開集合でもあり閉集合でもあるよ。

開集合でも閉集合でもある？それはもう開いているのか閉じているのかどっちなんですか？？自然言語としておかしいでしょう！？

私にいわれても…数学で自然言語がどうとかいいだしたら、数理論理学で「不完全性」が「完全性をもたない」って意味じゃないことの方がよっぽどだよ。

それもよっぽどですね！？ …まあその辺は百歩ゆずるとして、「開集合はルールを守って決めましょう」というルールはわかりました。しかし、何を目指して決めればいいんです？言い換えると、「空集合と全体集合と｛りんご｝を開集合とする」と決めたとして、だから何なんです？

開集合を決めると、各点の「近傍」が決まり、「連続な写像」が決まり、さらに近傍が決まると「収束」が決まってったりするよ。近傍というのはその点を含む任意の開集合（を包含する任意の集合）だね。開集合で囲まれた内側はご近所さんのくくりって感じかな。もちろん狭いレベルのご近所さんも広いレベルのご近所さんも色々あるけど。それで点列がある点に収束することの定義はあるインデックス以降でその点の任意の近傍に入ることだから、｛りんご｝が開集合だったらりんごに収束する点列は絶対にあるインデックス以降でりんごにならないといけない。でもみかんとぶどうに収束する点列はそうじゃなくてもいいかな。みかんにとって一番狭いご近所さんは｛りんご、みかん、ぶどう｝だからね。ぶどうも同じ。

その場合、みかんに収束するのにみかんに収束しなくてもいいということですか？ややこしいですね…。

まあハウスドルフ空間ならそんなことにならないんだけどね。

（ノート4章のつづきがあれば）つづく

メモ

$L(w)$	平均対数損失	真の分布と確率モデルの交差エントロピー（なのでサンプルは関係ない）。これが小さいパラメータほど、そのパラメータにおける確率モデルが真の分布に近い。この $L(w)$ の最小点 $w_0$ が「最適なパラメータ」といわれる。真の分布が確率モデルで実現可能な場合には、最小点 $w_0$ における確率モデルは真の分布を再現し、 $L(w_0)$ は真の分布のエントロピーを達成する。
$L_n(w)$	経験対数損失	サンプルによる経験分布と確率モデルの交差エントロピー（なのでサンプル依存）。
$G_n$	汎化損失	真の分布と予測分布の交差エントロピー（なのでサンプル依存）。なので、ベイズ推測はこれを小さくするものであってほしいし、どれくらい小さくなるものか知りたい。
$T_n$	経験損失	サンプルによる経験分布と予測分布の交差エントロピー（なのでサンプル依存）。
$K(w)$	平均誤差	真の分布上での、対数尤度比 $f(x,w) = \log p(x\|w_0) / p(x\|w)$ の平均（なのでサンプルは関係ない）。平均損失の最適なパラメータとの差 $L(w)-L(w_0)$ に等しい。ということからも明らかだが、最適なパラメータ $w_0$ においては任意の $x$ で $f(x,w_0)$ = 0 なので $K(w_0)=0$ である。なので結局 $K(w)$ とは $L(w)$ の最小値をゼロにずらしたもので、その大小の意味するところは $L(w)$ と同じでこれが小さいパラメータほど、そのパラメータにおける確率モデルが真の分布に近い。
$K_n(w)$	経験誤差	サンプルによる経験分布上での、対数尤度比の平均（なのでサンプル依存）。経験損失の最適なパラメータとの差 $L_n(w)-L_n(w_0)$ に等しく、 $K_n(w_0)=0$ である。

2019-05-20

NeurIPS2018読みメモ： CatBoost: unbiased boosting with categorical features（その0）

論文読み

以下の論文を読みます。

Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, Andrey Gulin. CatBoost: unbiased boosting with categorical features. In Proceedings of NIPS 2018. https://papers.nips.cc/paper/7898-catboost-unbiased-boosting-with-categorical-features

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

前回：その-1 ：そもそも gradient boosting がわからない／次回：まだ

前回の話をまとめると、「勾配ブースティング」とは複数のモデル（弱学習器）を直列に組み合わせて一つの判定モデル（強学習器）とする「ブースティング」といわれるアンサンブル学習手法の一つです。勾配ブースティングの考え方としては「現時点の強学習器に足し合わせると損失が最小になる弱学習器」を探して重ねていくわけですが、厳密に探すのは難しいので近似的に「『現時点の強学習器の予測の正解との誤差』を正解ラベルとして学習した弱学習器」を最適な重みで重ねていきます。

「勾配ブースティング」の個々の弱学習器として具体的に採用されるのは典型的には「決定木」であるそうです。決定木とはよくある性格診断テストのように Yes/No で答えられる質問をして、その回答によってまた別の質問をして、最終判断まで導くモデルです。弱学習器として決定木を採用する場合、最終的にたどりつく診断結果のマスごとに、強学習器に足し合わせるときの重みを変えることができるんでしたよね。

それでこの論文は CatBoost という勾配ブースティングのツールがすごいっていう話なんですよね。やはり弱学習器は決定木ということなんでしょうか。

論文を "tree" で検索すると2ページの中ほどに "CatBoost is an implementation of gradient boosting, which uses binary decision trees as base predictors" とあるから決定木、それも二分木を弱学習器として採用しているということで間違いないね。gradient boosting（勾配ブースティング）とだけいったとき gradient boosting decision tree（勾配ブースティング決定木）を意味していることが多いんだと思う。

なるほど。二分木というのは枝分かれが必ず2つということでしょうか。確かに Yes/No で分岐していく木をイメージしていましたが、必ず2つの枝に分かれると決めなくてもいい気もしますが。

初期の決定木の実装には、「カテゴリカル値をとる特徴について、とりうるカテゴリカル値だけ分岐させる」という方針のものもあったみたいだけどね。

雑記：決定木の話（途中） - クッキーの日記

でも、多分木で実現できる決定木って別に二分木でも実現できるからね。分岐が深くはなるけど。それに、分岐数を任意にしてしまったら、そのノードで分岐に用いる特徴を選択する基準をどうするって話になる。特徴ごとに分岐数が違ったら、分岐が多ければ分岐後の誤差が小さいのは当然だから特徴間のフェアな比較ができない。そもそも分岐数に上限を設けなきゃ連続値特徴は全てのデータをばらばらに分岐することになっちゃうね。カテゴリカル値をとる特徴であっても、カテゴリカル値だけ必ず分岐させてしまうのは過学習になりそうだな。このカテゴリカル値とこのカテゴリカル値は実は目的上分けて取り扱う必要がないってありそうだし。なるべくシンプルなモデルから攻めて最低限の精度を達成するようにしたい気がするよね。

まあそういわれれば。それで、この論文で紹介する CatBoost はアルゴリズムに以下の2つの特長を取り入れたとありますね。

ordered boosting, a permutation-driven alternative to the classic algorithm
innovative algorithm for processing categorical features

これらは prediction shift という既存のあらゆる実装にみられるリーケージを対処するために導入されたようですが、勾配ブースティング業界の知識がないと何をいっているのかさっぱりですね…。alternatibe to classic algorithm といわれてもそもそも既存のアルゴリズムがどうなのかよくわからないですし…。というか、勾配ブースティングって前回みたウィキペディアの記事にかいてるアルゴリズムが全てじゃないんですか？色々なアルゴリズムのバリエーションがぽんぽん出てくるものなんですか？

私も勾配ブースティング業界の知識はないからそこは続きを読みながらの宿題なんだけど、イメージで言うと…まずベースの決定木というのがこれと確定されたアルゴリズムじゃないよね。「特徴と境界の選択」「分岐の終了」「予測値の割り当て」をそれぞれどう達成するかは自明じゃない。勾配ブースティング決定木の実装をみてみると、特徴と境界の選択を全探索しているわけでもなかったりする。全探索すると計算が遅くなりすぎるからどう全探索せずにモデルの性能を保つかってのも勾配ブースティング決定木パッケージの領分なのかも。その2点目のようにカテゴリ特徴をどう扱うかってのも流儀がありそう。加えて、勾配ブースティングでは1ラウンド、2ラウンド、…と決定木を学習していくわけだから、1ラウンド目はこの流儀で学習して、2ラウンド目はそれを補うようにこの流儀で学習して、…っていう自由度もありそうかな。

そのレベルの話だとどんなデータセットを学習するのかにもよりそうですね…勾配ブースティング業界に詳しくないのでイントロから読んでいきましょう。勾配ブースティングはここ何年も、データが異質な特徴が混在するものであったり、ノイジーであったり、複雑な依存構造があったりするときには primary な手法であり続けていると。勾配ブースティングの理論は以下の文献に示されているのですか？タイトルとアブストラクトを読む限り「distribution-free な2値モデルには限界がある」という話にみえますが…。

https://www.cis.upenn.edu/~mkearns/papers/crypto.pdf

まあそれは置いておいて、既存のあらゆる勾配ブースティングの実装の問題点というのは「数ラウンド学習した強学習器は全ての学習データに依存している」ということらしいですが、このことが問題なんですか？？これによってリーケージが生じるということですが、この箇所だけだとわからないですね…。あと、カテゴリカル値をとる特徴の取り扱いも、目的変数の統計量に代替する手法がよく使われるが、これもリーケージを引き起こすと…目的変数の統計量にエンコーディングするやり方ではリーケージになりそうというのはわかりますが、これはもう特徴量エンジニアリングの話ですよね？既存の勾配ブースティングのパッケージってそんな機能まで内蔵してるんですか？

引き合いに出されている既存のパッケージは以下だよね。

XGBoost（ https://www.kdd.org/kdd2016/papers/files/rfp0697-chenAemb.pdf ）
LightGBM（ LightGBM: A Highly Efficient Gradient Boosting Decision Tree ）

アブストを見る限りカテゴリカル値をとる特徴をどう扱っているとかはないかな…XGBoost は省リソースでたくさんのデータを扱えるよってみえるし、LightGBM は分岐点候補のサンプリングを上手くしたよってかいてあるようにみえるよね。Light の名の通り。

それだとなんかあるパッケージは捌けるデータ量を競い、あるパッケージは学習速度を競い、あるパッケージはカテゴリカル値をとる特徴の取り扱いを競っていることになってしまいませんか…。2節に移ると、冒頭にデータ $(x_k, y_k) \in (\mathbb{R}^m, \mathbb{R})$ は i.i.d. に $P(\cdot, \cdot)$ にしたがうとするとありますね。現実のデータって独立なものなんでしょうか…まあいいです、いまの目的は損失 $\mathcal{L}(F)$ を最小にする関数 $F: \mathbb{R}^m \to \mathbb{R}$ を探すことですね。ここで $\mathcal{L}(F) \equiv \mathbb{E} L \bigl(y, f(x) \bigr)$ ということですから、訓練データセット上での損失でもテストデータセット上での損失でもなく、未知のあるデータに対する期待損失ですね。それは目指すところはそうでしょう。勾配ブースティングでは前回みたとおり $F^t = F^{t-1} + \alpha h^t$ といった形でこれを求めていくわけです。 $h^t = \underset{h \in H}{\rm arg \, min} \, \mathbb{E} L(y, F^{t-1}(x) +h(x))$ です。無論、真の分布 $P(\cdot, \cdot)$ を知り得ないので真にこの最適化を実行することはできないですよね。よく用いられる手法としては、 $h(x)$ と「時点 $t-1$ での予測値 $F^{t-1}(x)$ における損失の傾きのマイナス1倍」との誤差の2乗の期待値が最小になるような $h^t(x)$ を選ぶということですが（傾きが負なら予測値を増やすべきですし、傾きが正なら予測値を減らすべきですし、そのような理想的な修正がなるべく全ての $x$ で達成されてほしいですね）、これも真の分布を知らなければ真に誤差の2乗の期待値を知ることはできないと思います。私たちは未知の $x$ における正解 $y$ （の期待値）を知らないので、未知の $x$ でも理想的な修正が達成されているかをわからないと思うのですが…。

3節はカテゴリカル値をとる特徴の話のようですね。二分木でカテゴリカル値をとる特徴を扱う常套手段として one-hot encoding がありますが、取りうるカテゴリカル値が多いと特徴が増殖しすぎてしまうのはそれはそうですね。それでよくとられる方法として、多すぎるカテゴリカル値を目的変数に応じてグルーピングするとか、カテゴリカル値を目的変数に応じた数値変数にしてしまうとか（TS: target statistics）があるということです。

以下の本の5章でやった話だね。

機械学習のための特徴量エンジニアリング：ノート2 - クッキーの日記

まあ何にせよカテゴリカル値をとる特徴をより粗いカテゴリカル値とか数値とかの新しい特徴に変換した上で、新しい特徴の上でありうるあらゆる分岐点の中から、対数損失（各データについて、正例であれば負例っぽさの対数、負例であれば正例っぽさの対数をとったものの和でしょうか）なりジニ係数なりMSEなりを最小にする分岐点を選ぶというわけです。…改めて、膨大なカテゴリカル値をとる特徴を変換するというのは、「分岐点の候補を捨てる」ということなんですね。粗いカテゴリにまとめるなら、一緒にまとめられたカテゴリはもう分岐されることはありませんし、何らかの数値特徴に変換するにしても、変換の仕方如何で分岐は大いにコントロールされてしまうでしょう。それで、単なる特徴の変換とはまた違った方法として、LightGBM ではカテゴリカル値をとる特徴を勾配ブースティングの各ラウンドで "gradient statistics" に変換するとありますね？この方法は有用な情報を引き出せる一方で、計算時間とメモリを消費するので、少数カテゴリをひとまとめにするなどの対策をしなければならず、情報の損失を免れないとか。

LightGBM のペーパーにそんなことかいてあったかな…と思ったけど LightGBM のドキュメントの方に載ってるのか。LightGBM のカテゴリカル値をとる特徴の取り扱いは ont-hot じゃなかったんだね。以下の記述をみるに、どうも各ラウンド毎に、その時点での各カテゴリカル値のデータに残っている勾配の合計値を計算して、その合計値でカテゴリをソートして（合計値を数値特徴のように扱って）分岐点候補を絞っているみたいだ。参考文献が付されているみたいだけど、このアイデア自体は LightGBM 独自のものでなく伝統的なものってことなのかな。

というか「とりうるカテゴリカル値が膨大なときは単純に整数として扱うか、低次元に埋め込むのがよいことが多い」ってかいてあるね…。

そんな殺生な…できたら苦労しませんよ…。まあしかし、gradient statistics は計算が大変なのでやはり target statistics を利用したいわけです。つまり、カテゴリカル値をとる特徴 $i$ についてカテゴリカル値 $x_k^i$ を数値 $\hat{x}_k^i$ に変換してしまいたいのですが、基本路線としては $\hat{x}_k^i \approx \mathbb{E}(y|x^i = x_k^i)$ というようにその特徴が与えられた下での目的変数の期待値にするということです…うーん、ユーザが検索結果のリンクをクリックするか予測するのに、ユーザIDを特徴とするととりうる値が膨大すぎるのでそのユーザのクリック率の期待値で代えるということですよね。なんだか荒っぽくないですか？いくら普段からクリック率が高めのユーザでも、興味がないリンクはクリックしないと思うんですが。

私にいわれても…別に、ユーザIDをクリック率に代えるという操作はそのユーザIDに対する予測値をただちに上げるわけじゃないし。クリック率が高いユーザは検索語が含まれるサイトを軒並みクリックするようだが、クリック率が低いユーザは必ずしもそうでない傾向がみられる、みたいな「境界」を発見できればいいんだよ。発見できるかは知らないけど…。

はあ。とにかくそれで、TS を扱うやり方でも Greedy TS、Holdout TS、Leave-one-out TS、Ordered TS と4種類が紹介されていますね。最後の Ordered TS が CatBoost が採用している流儀ということです。

Greedy TS：期待値を単純に訓練データ上の平均としてしまうやり方ですが、単純すぎるので事前信念値（いま適当につくった語） $p$ を $a$ 件分混ぜ込むといった感じのようですね。少数カテゴリに弱いようです。そしてこれは当然のようにリーケージを起こします。
Holdout TS：期待値の計算を訓練データでやるのは乱暴なので、訓練データを期待値用と訓練用に分割するということですが、データを有効につかえないのが欠点とありますね。
Leave-one-out TS：期待値の計算に「自分を除いた」データをつかうということのようですね。
Ordered TS：訓練データをランダムに並べて「自分より過去の」データをつかうようです。ラウンド毎にランダムに並び替えるようですね。この箇所だけ読むと Leave-one-out TS に対する優位性がよくわからないのですが、後の方を読んでみると、Leave-one-out TS はむしろ多数カテゴリに弱いようですが…？

…こういうイメージかな。同じカテゴリカル値をもつデータの目的変数が実は結構ばらついているとき、Leave-on-out TS によるエンコーディングだとそのばらつきを捕捉しにくい。実はばらついていることに気付かず決定木の根拠に採用されてしまうかもしれない。だけど、Ordred TS によるエンコーディングならきっとデータごと、ラウンドごとにエンコーディングされる値がどんどんばらつくから、決定木が「この特徴はつかわないでおこう」ってなりやすいとか？ぱっと考えただけだからわからないけど…。

（次回があれば）つづく

2019-05-17

雑記：積の微分公式の話

雑記

おかしい点がありましたらご指摘いただけますと幸いです。用語の定義は参考文献 3. に倣っていますが別の文献では異なる可能性があります。参考文献 3. を参考にしていますが解釈の誤りは筆者に帰属します。極限の定義に不明瞭なところがあると思います。

参考文献

※ キャラクターは架空のものです。

積の微分公式ってありますよね。

以下に証明まであるね。そこに出てくる導関数の定義はさらに下のページかな。

積の微分公式とその証明の味わい | 高校数学の美しい物語

関数の連続性と微分可能性の意味と関係 | 高校数学の美しい物語

それはそうなんですが、まさにその記事で重要なテクニックとされている、「扱いにくいので以下のように二つの和に分解する」というのが素直な発想ではない気がしませんか？そこに気が付かないと詰んでしまいますよね？

そ、そうかな…（この前多様体の接ベクトルを求めたときにもそのテクニックを使ったんだけど…）。

そうです。そもそも微分ってよく以下のように説明されると思うのですけど、

$\phi(x)$ が $x=c$ で微分可能 $\, \overset{\rm def}{\Leftrightarrow} \; \displaystyle a \equiv \lim_{u \to 0} \frac{\phi(c + u) - \phi(c)}{u}$ が存在する

この定義の形だと、 $a$ とは何なのかわかりにくいですし、あと入出力をベクトルや行列に拡張しにくいですよね。だからなのかはわからないですが、行列の微分を扱う参考文献 3. ではこちらの形です。

$\phi(x)$ が $x=c$ で微分可能 $\, \overset{\rm def}{\Leftrightarrow} \; \exists a \in \mathbb{R} \quad {\rm s.t.} \quad \phi(c+u) = \phi(c) + au + \mathcal{o}(u), \; \forall u \in \mathbb{R}$

ここで、 $\mathcal{o}(\cdot)$ はランダウ記号のスモールオーで、関数 $r(u)$ が $\displaystyle \lim_{u \to 0} \frac{r(u)}{u} = 0$ であるときに $r(u)$ を $\mathcal{o}(u)$ とかきかえて、「 $r(u)$ は $u$ よりも速く $0$ に収束する」などといいますね。もちろん色々な関数が $\mathcal{o}(u)$ にかきかえられるので、一度 $\mathcal{o}(u)$ にかきかえると元々の関数は復元できない、収束の速さにだけ注目した丸め記法といったところでしょうか。…こちらの定義の方がテイラー展開の形をしていて近似めいたことをしようとしているのだとわかりやすいでしょう？無論このような $a$ が存在したら前者の定義の式で求めることになるので前者の定義の式はつかうのですけど。

テイラー展開がわかりやすいって人は既に微分の知識があるんじゃ…。

それで、 $d \phi(c;u) \equiv au$ のことを「起点 $c$ における増分 $u$ についての微分」と呼ぶそうです。微分係数 $a$ は $\phi '(c)$ ともかき、起点 $c$ の関数であることを意識すると導関数と呼ばれますね。本題に戻ると、いま積の微分 $d(fg)(c;u)$ を知りたいというか、 $df(c;u), \; dg(c;u)$ との関係を知りたいわけです（参考文献 1. の記事では積の導関数 $(fg)'(c)$ で考えていますが、導関数は増分 $u$ によりませんから $u$ をかけた $d(fg)(c;u)$ を考えても同じ関係が得られるはずです）。テイラー展開形式の定義に基づいて示してみますね。

$f$ も $g$ も微分可能な起点 $c$ を考えます。そこで共通の増分 $u$ について以下が成り立ちますね。 $r_f(u)$ と $r_g(u)$ は $u$ よりも速く $0$ に収束する残差です。 $f(c+u) = f(c) + df(c;u) + r_f(u)$
$g(c+u) = g(c) + dg(c;u) + r_g(u)$ これらの各辺どうしをかけ合わせるとこうなります。 $\begin{split} f(c+u)g(c+u) =& f(c)g(c) + f(c)dg(c;u) + g(c)df(c;u) \\ &+ f(c)r_g(u) + g(c)r_f(u) \\ &+ \bigl( df(c;u) + r_f(u) \bigr) \bigl( dg(c;u) + r_g(u) \bigr) \end{split}$ ここで、 $f(c)$ と $g(c)$ は $u$ によりませんから、 $f(c)r_g(u)$ も $g(c)r_f(u)$ も $\mathcal{o}(u)$ にかきかえられます。また、 $\begin{split} \bigl( df(c;u) + r_f(u) \bigr) \bigl( dg(c;u) + r_g(u) \bigr) &= \bigl( f'(c)u + r_f(u) \bigr) \bigl( g'(c)u + r_g(u) \bigr) \\ &= f'(c)g'(c)u^2 + f'(c) r_g(u) u + g'(c) r_f(u) u + r_f(u) r_g(u) \end{split}$ であり、この各項は $u$ よりも速く $0$ に収束するのでやはり $\mathcal{o}(u)$ とかきかえられ、結局、 $f(c+u)g(c+u) = f(c)g(c) + f(c)dg(c;u) + g(c)df(c;u) + \mathcal{o}(u)$ となりますが、これはテイラー展開の形式です。つまり、 $d(fg)(c;u) = f(c)dg(c;u) + g(c)df(c;u)$ であるといっていることに他なりません。

$\square$

ほら、テクニックを用いずに積の微分公式を示せたでしょう？

テクニックが要らなくなった一方でちょいちょいランダウ記号に関する定理が前提とされているような…それに、テクニックを回避できたのはテイラー展開形式の定義にしたのが要因じゃないんじゃない？テクニックが回避できたのは、その証明が「 $(fg)(c+u)$ の一次近似は $f(c+u)$ の一次近似と $g(c+u)$ の一次近似の積からつくることができるはずだ」っていうあまり明らかじゃない出発点から始まっているからだと思う。だって、テイラー展開形式の定義にするにしても、素直に出発するなら、

$\begin{split} (fg)(c + u) &= (fg)(c) + d(fg)(c;u) + r_{fg}(u) \\ \Rightarrow d(fg)(c;u) &= (fg)(c + u) - (fg)(c) - r_{fg}(u) \\ &= f(c + u)g(c+u) - f(c)g(c) - r_{fg}(u) \\ &= f(c+u)g(c+u) - f(c)g(c+u) + f(c)g(c+u) -f(c)g(c) - r_{fg}(u)\\ &= g(c+u)df(c;u) + f(c)dg(c;u) + g(c+u)r_f(u) + f(c)r_g(u) - r_{fg}(u) \end{split}$ ここまでは任意の $u$ について成り立つ。残差部分が邪魔だから両辺を $u$ で割ってから $u \to 0$ とすると、 $(fg)'(c) = g(c)f'(c) + f(c)g'(c)$ を得る（∵ 積の極限は極限の積）。

$\square$

…こうするとやっぱり例のテクニックをつかう。上の3行目から4行目の式変形がそうだね。

あれ、そういわれるとそんな気も…。

それに、微分係数形式の定義でも「 $f'(c)$ と $g'(c)$ の積をとってみよう」という発想から出発するなら例のテクニックを回避できる気がするな。

$\begin{split} f'(c)g'(c) &= \displaystyle \left( \lim_{u \to 0} \frac{f(c + u) - f(c)}{u} \right) \left( \lim_{u \to 0} \frac{g(c + u) - g(c)}{u} \right) \\ &= \lim_{u \to 0} \frac{f(c + u) - f(c)}{u} \cdot \frac{g(c + u) - g(c)}{u} \\ &= \lim_{u \to 0} \frac{1}{u} \cdot \frac{f(c + u)g(c+u) - f(c+u)g(c) - f(c)g(c+u) + f(c)g(c)}{u} \\ &= \lim_{u \to 0} \frac{1}{u} \left( \frac{f(c + u)g(c+u) - f(c)g(c)}{u} \right. \\ & \qquad \qquad \quad \left. - \frac{f(c + u)g(c) - f(c)g(c)}{u} - \frac{f(c)g(c+u) - f(c)g(c)}{u} \right) \end{split}$ 上式が有限の値に収束しなければならないので、カッコ内は $u \to 0$ で $0$ に収束しなければならない。であれば、 $(fg)'(c) = g(c)f'(c) + f(c)g'(c)$ でなければならない。

$\square$

…どうだろう。例のテクニックっぽいっちゃぽいけど、例のテクニックと違って「経由点を差し挟む」という操作はせずに済む。

え、えっと、なんかもう何が素直で何が素直でないのかわからなくなってきました…。

「この証明の仕方は素直である」の真偽を問いたければこれを数学の言葉で定義しないといけないね。骨が折れそうだ。…そういえば、さっき「入出力をベクトルや行列に拡張」っていってたのは？

あ、はい、ここまではスカラー変数をとるスカラー値関数の微分を考えていましたが、テイラー展開形式の定義はベクトル変数をとるベクトル値関数にも拡張できます。面倒なので文字を使い回します。 $\phi : \mathbb{R}^n \to \mathbb{R}^m$ として、

$\phi(x)$ が $x=c$ で微分可能 $\, \overset{\rm def}{\Leftrightarrow} \; \; \exists A \in \mathbb{R}^{m \times n} \;\; {\rm s.t.} \;\; \phi(c+u) = \phi(c) + Au + \mathcal{o}(u), \;\; \forall u \in \mathbb{R}^n$

です。ここで、 $\mathcal{o}(u)$ は入出力がベクトルのときは $\displaystyle \lim_{u \to \vec{0}} \frac{r(u)}{||u||} = \vec{0}$ を満たす関数 $r(u)$ をかきかえたものとしてください。そして、 $A$ がどのような行列か知るには上の式の $i$ 番目の成分をとります。 $\displaystyle \phi_i(c+u) = \phi_i(c) + \sum_{j=1}^m a_{ij}u_j + \mathcal{o}(u), \; \forall u \in \mathbb{R}^n$ $\phi(x)$ が $x=c$ で微分可能ならば上の $a_{i1}, \cdots, a_{im}$ は存在しますが、他方、上の $u$ を $u = t e_j$ （ $t \in \mathbb{R}$ ， $e_j \in \mathbb{R}^n$ は $j$ 番目の成分のみ $1$ でその他の成分が $0$ ）とすると、 $a_{ij}$ は以下だったことがわかります。 $\displaystyle \phi_i(c+ t e_j) = \phi_i(c) + a_{ij} t + \mathcal{o}(t) \; \Leftrightarrow \; a_{ij} = \lim_{t \to 0} \frac{\phi_i(c + t e_j) - \phi_i(c)}{t}$ 上の $a_{ij}$ のことを $D_j \phi_i(c)$ とか $\displaystyle \frac{\partial \phi_i(c)}{\partial x_j}$ などとかくということです。なお、各 $a_{ij}$ が存在しても $\phi(x)$ が $x=c$ で微分可能であるとは限りません。 $\phi(x)$ が $x=c$ で微分可能であるならば各 $a_{ij}$ は存在し上式で求まるということです。この $a_{ij}$ を各成分にもつ微分係数行列 $A$ のことを $D \phi(c)$ とかいてヤコビ行列ともよびます。 $d\phi(c;u) \equiv Au$ が $c$ における $u$ についての微分になります。

ヤコビ行列の行列式（ヤコビアン）は確率変数を変換するときによくつかうね。

はい。それで、 $\phi : \mathbb{R}^n \to \mathbb{R}$ のときに積の微分公式がどうなるかを考えてみます。このときヤコビ行列は $A \in \mathbb{R}^{1 \times n}$ で、形としては横ベクトルです。上の3つの証明のうち1番上の証明で考えますが、前半部分（「また、」の直前まで）は $c, u \in \mathbb{R}^n$ だろうと変わりません。その後が、

$\begin{split} \bigl( df(c;u) + r_f(u) \bigr) \bigl( dg(c;u) &+ r_g(u) \bigr) = \bigl( Df(c)u + r_f(u) \bigr) \bigl( Dg(c)u + r_g(u) \bigr) \\ &= Df(c)u \cdot Dg(c)u + D f(c)u \cdot r_g(u) + Dg(c)u \cdot r_f(u) + r_f(u) r_g(u) \end{split}$ こうなりますが、これらが $||u||$ で割っても $u \to \vec{0}$ で $0$ に収束するかを確認しなければなりません。しかし、これは大丈夫です。第1項から第3項には $u$ が含まれているので（第1項は2つ含まれているうちのどちらでもいいですが）、 $||u||$ で割ると単位ベクトルが残り、そこは $u$ の長さに依存しなくなります。しかし、それでももう1つの $u$ や $r_g(u)$ や $r_f(u)$ が残りますので $u \to \vec{0}$ で $0$ に収束します。第4項も $||u||$ で割ってもなお $u \to \vec{0}$ で $0$ に収束します。なので、 $f,g$ がベクトル値をとるスカラー関数であっても積の微分公式 $d(fg)(c;u) = f(c)dg(c;u) + g(c)df(c;u)$ は成立します。

$\square$

なるほど。微分係数行列の定義に基づいてやるとこうかな。

$\begin{split} d(fg)(c;u) &= D(fg)(c)u = \displaystyle \sum_{j = 1}^{n} D_j(fg)(c)u_j = \sum_{j = 1}^{n} \left( \lim_{t \to 0} \frac{(fg)(c + t e_j) - (fg)(c)}{t} \right) u_j \\ &= \sum_{j = 1}^{n} \left( \lim_{t \to 0} \frac{f(c + t e_j)g(c + t e_j) - f(c)g(c + t e_j) + f(c)g(c + t e_j) - f(c)g(c)}{t} \right) u_j \\ &= \sum_{j = 1}^{n} \Bigl( g(c)D_jf(c) + f(c)D_jg(c) \Bigr) u_j = f(c)dg(c;u) + g(c)df(c;u) \end{split}$

$\square$

テイラー展開式で定義から出発するなら、以下の式変形まではスカラー変数のときと変わらないね。

$\begin{split} d(fg)(c;u) = g(c+u)df(c;u) + f(c)dg(c;u) + g(c+u)r_f(u) + f(c)r_g(u) - r_{fg}(u) \end{split}$ ここまでは任意の $u$ について成り立つ。残差部分が邪魔だから両辺を $||u||$ で割ってから $u \to \vec{0}$ とすると、 $D(fg)(c) \hat{u} = g(c)Df(c) \hat{u} + f(c)Dg(c) \hat{u}$ を得る（ $\hat{u}$ は $u$ 方向の単位ベクトル）。任意の方向 $\hat{u}$ についてこれが成り立つので結局 $D(fg)(c) = g(c)Df(c) + f(c)Dg(c)$ が成り立つ。

$\square$

最後に、微分係数どうしの積から出発する場合だけど、微分係数行列どうしはサイズ的にそのまま積が定義できないね。アダマール積を取らないといけないな。

$\begin{split} D_jf(c)D_jg(c) &= \displaystyle \left( \lim_{t \to 0} \frac{f(c + t e_j) - f(c)}{t} \right) \left( \lim_{t \to 0} \frac{g(c + t e_j) - g(c)}{t} \right) \\ &= \lim_{t \to 0} \frac{f(c + t e_j) - f(c)}{t} \cdot \frac{g(c + t e_j) - g(c)}{t} \\ &= \lim_{t \to 0} \frac{1}{t} \cdot \frac{f(c + t e_j)g(c+t e_j) - f(c+t e_j)g(c) - f(c)g(c+t e_j) + f(c)g(c)}{t} \\ &= \lim_{t \to 0} \frac{1}{t} \left( \frac{f(c + t e_j)g(c+t e_j) - f(c)g(c)}{t} \right. \\ & \qquad \qquad \quad \left. - \frac{f(c + t e_j)g(c) - f(c)g(c)}{t} - \frac{f(c)g(c+t e_j) - f(c)g(c)}{t} \right) \end{split}$ 上式が有限の値に収束しなければならないので、カッコ内は $t \to 0$ で $0$ に収束しなければならない。であれば、 $D_j(fg)(c) = g(c)D_jf(c) + f(c)D_jg(c)$ でなければならない。任意の $j = 1, \cdots, n$ についてこれが成り立つので結局 $D(fg)(c) = g(c)Df(c) + f(c)Dg(c)$ でなければならない。

$\square$

じゃあベクトル値をとるスカラー関数じゃなくて、ベクトル値をとるベクトル関数どうしの積の微分はどうなるかっていうと…これも次元をそろえて片方を転置でもしないと関数どうしの積が定義できないね。

結論からいえばそれも積が定義できる形にしてあれば同様の積の微分公式が成り立ちます。ただ、それを考えるならば微分の定義を行列を変数にとる行列関数の微分にまで拡張した方がもっと一般化して考えられます。行列を変数にとる行列関数の微分の定義は、 $F : \mathbb{R}^{n \times q} \to \mathbb{R}^{m \times p}$ として、

$F(X)$ が $X=C$ で微分可能 $\, \overset{\rm def}{\Leftrightarrow} \; \; \exists A \in \mathbb{R}^{mp \times nq} \;\; {\rm s.t.} \;\; {\rm vec}F(C+U) = {\rm vec}F(C) + A{\rm vec}U + \mathcal{o}(U), \;\; \forall U \in \mathbb{R}^{n \times q}$

です。 $\mathcal{o}(U)$ は入出力が行列のときは $\displaystyle \lim_{U \to O} \frac{R(U)}{||U||} = O$ を満たす関数 $R(U)$ をかきかえたものとしてください。また、 $||U|| \equiv ( {\rm tr} \, U^{\top} U)^{1/2}$ です。 ${\rm vec} X$ は行列 $X$ を縦ベクトルにばらして縦に並べたものという意味です。沖本本の7章でよく似た ${\rm vech}$ 作用素というのがありましたが、あちらは行列の下三角にある成分を並べてベクトルにする作用素だったので少し違いますね。何にせよこの手のものは定義を要確認です。

${\rm vec}$ 作用素を使うんだ。それだと形式はベクトル値をとるベクトル関数と同じになるね。

ええ、それで微分は、 ${\rm vec} d F(C;U) \equiv A {\rm vec}U$ と定義されます。そうすると $d(FG)(C;U) = \bigl(dF(C;U) \bigr)G(C) + F(C)dG(C;U)$ が成り立つんですがもう疲れたので終わります…。

つづかない

2019-05-14

ベイズ統計の理論と方法：ノート3

本読み機械学習

ベイズ統計の理論と方法

作者: 渡辺澄夫
出版社/メーカー: コロナ社
発売日: 2012/03/01
メディア: 単行本
購入: 1人クリック: 4回
この商品を含むブログ (8件) を見る

書籍サポートページ

前回：ノート2.5 ／次回：まだ

2章に入る前に、1章の章末問題がそれぞれどういうことかと、証明のスケッチをメモしておきますね。

【１】「自由エネルギーの逆温度 $\beta$ に関する下限」は「確率モデルの負の対数尤度のパラメータ $w$ に関する下限」に等しい。この後者は言い換えると「パラメータの最尤推定値 $w_{ML}$ における確率モデルの負の対数尤度」である。

まず自由エネルギーを下から評価する。自由エネルギーは「負の対数尤度に $-\beta$ をかけて、エクスポネンシャルをとって、 $\varphi(w)$ の重みで積分して、対数をとって、 $-\beta^{-1}$ をかけたもの」（★）なので、負の対数尤度が小さいほど小さくなる。負の対数尤度は $w=w_{ML}$ で下限をとるので、（★）の負の対数尤度を $w=w_{ML}$ における負の対数尤度に置き換えると自由エネルギーを下から評価できる（そしてこれは結局 $w=w_{ML}$ における負の対数尤度そのものになり、 $\beta$ によらない）。つまり、自由エネルギーは $\beta$ をどう動かしても $w=w_{ML}$ における負の対数尤度以上には大きい（が、本当にある $\beta$ でそこまで小さくなるかはまだわからない）。
次に自由エネルギーを上から評価する。自由エネルギーは（★）の積分範囲を狭めたものよりは小さい（∵ 被積分関数は任意の $w$ で正、かつ積分した後に負数をかけるので）。なので、積分範囲を「負の対数尤度＜ $w=w_{ML}$ における負の対数尤度＋ $\varepsilon$ 」が成り立つ $w$ に狭める。さらに、負の対数尤度を $w=w_{ML}$ における負の対数尤度＋ $\varepsilon$ に置き換えてよい（∵ 負数をかけて積分して負数をかけるので、この積分範囲でとる値の上限に置き換えれば上から抑えられる）。すると「自由エネルギーはこれ以下には小さい」という式が出るが、これと $w=w_{ML}$ における負の対数尤度との差の絶対値は任意の正数 $\varepsilon'$ より小さくできる（ $\varepsilon=\varepsilon'$ とした後 $\beta \to \infty$ とすればよい）。つまり、自由エネルギーはこれ以下には小さい、という値は $\beta \to \infty$ で $w=w_{ML}$ における負の対数尤度に近づく。

【２】「未知サンプル $X$ の対数尤度の期待値の $n$ 倍のマイナス1倍 $nL(w)$ に、 $-\beta$ をかけて、エクスポネンシャルをとって、 $\varphi(w)$ の重みで積分して、対数をとって、 $-\beta^{-1}$ をかけたもの」は、「自由エネルギーのサンプルの現れ方に対する平均値」よりは小さくならない（29ページにはこの $n$ 倍がないが誤植）。この前者は自由エネルギーの式における「負の対数尤度 $nL_n(w)$ 」を未知サンプルに対するそれの $n$ 倍 $nL(w)$ に置き換えたものである。

方針として、後者（のサンプルの現れ方に対する平均を取る前）から無理やり前者を絞り出す。すると以下の左辺が残るので右辺のように変形する。 $\displaystyle -\frac{1}{\beta} \log \frac{\int e^{-\beta n L_n(w)} \varphi(w) dw}{\int e^{-\beta n L(w)} \varphi(w) dw} = -\frac{1}{\beta} \log \frac{\int e^{-\beta n \bigl( L_n(w) - L(w) \bigr)} e^{-\beta n L(w)} \varphi(w) dw}{\int e^{-\beta n L(w)} \varphi(w) dw}$ （★）上式の右辺の対数の中身は $f_0(w) = e^{-\beta n L(w)} \varphi(w) / \bigl( \int e^{-\beta n L(w')} \varphi(w') dw' \bigr)$ という確率密度関数による平均にみえ、また、 $f_1(z) = e^{-\beta n z}$ は凸関数なのでイェンセンの不等式が適用できる。つまり、（★）は「 $L_n(w) - L(w)$ の $f_0(w)$ による平均の $n$ 倍」（★★）以下であることがわかる。次に（★★）のサンプルの現れ方に対する平均をとることにすると、 $f_0(w)$ による平均と積分順序を交換できるので先に $L_n(w)-L(w)$ のサンプルの現れ方に対する平均をとってよいが、これはゼロである（∵ $L_n(w)$ 、 $L(w)$ 、平均の定義）。つまり、後者マイナス前者はゼロ以下なので、前者は後者以上である。前者は後者より小さくならない。

【３】略（確率モデル $\displaystyle \prod_{i=1}^n p(X_i|w)^\beta$ と事前分布 $\varphi(w|\phi)$ の積が $a \varphi(w|\hat{\phi})$ の形にかければよく、つくり方は14ページの例1と同じ）。

【１】からは自由エネルギーとはこういうものだったのだという印象も受けるね。【２】は1つの未知サンプルの対数尤度の期待値に対する自由エネルギー（のようなもの）は、訓練サンプルの自由エネルギー（＝通常の自由エネルギー）のサンプルの現れ方に対する期待値よりは小さくならないということだね。等号成立について考えてみても面白いだろう。（★）のサンプルの現れ方に対する平均がゼロになるのはいつかということだね。以下のときには明らかに等号成立する。ベイズ推定をする意味がない状況だけど…。

サンプルの出方が確率的ではない（ $X$ がもはや確率変数でなく定数 $c$ である）のとき。
$\varphi(w)$ がデルタ関数のとき。

$\beta \to \infty$ のときは成立しないかな。最尤推定になるわけだけど、負の対数尤度を最小にしたときの自由エネルギーの期待値と、負の対数尤度の期待値を最小にしたときの自由エネルギーは違う気がするから…間違ってたらごめん…。

2章に入りましょう。31ページの最後で1章の章末問題【２】の $L(w)$ が出てきますね。こうみると、真の分布と確率モデルの交差エントロピーの形をしています。ということは、「真の分布の（微分）エントロピー」から「真の分布と確率モデルのカルバック・ライブラー情報量」を差し引いたものということです。1章では $\mathbb{E} [ F_n(1) ]$ が真の分布と $Z_n(1)$ の交差エントロピーでしたが、それとはまた違いますね。そしてこの $L(w)$ が「真の分布に対して最適なパラメータの集合」を規定するのですか…。

ベイズ推定の目指すところは「尤度の（サンプルの出方に対する）期待値を最大化する」⇔「真の分布と確率モデルのカルバック・ライブラー情報量を最小化する」ということなのかな。

その後に「 $q(x)$ は $p(x|w)$ に対して正則」という言葉が出てきますが、これは $q(x)$ が $p(x|w)$ で実現可能かどうかに関係なく、唯一の最適解 $w_0$ が存在するかといったところですね…でも逆に、 $w_0$ が唯一の最適解であってそこでのヘッセ行列が正定値じゃないってどういう状況です？ $w_0$ が唯一の最適解だったらそこで「お椀の底」になっているものじゃないんですか？

うーん、ぱっと思い付くのは、パラメータ集合が $w_0$ の1点のみとか、そうでなくても $w_0$ の1点のみが飛び地になってるとか、そもそも $w_0$ で微分可能でないとか？そしたら、 $w_0$ の近くから $w_0$ に向かって滑り落ちることはできないね。あと、 $w_0$ が領域の端っこなケースだったら「あらゆる方向から滑り落ちる」って感じになってなくても最小点になることがありえそうだね。

33ページにパラメータ集合がコンパクトで連続なら $W_0 \neq \emptyset$ とありますが、どこかに最小点があるはずですからそれはそうですね。しかし、元が1つとも限らなければ、正則とも限らないでしょうね。そして、 $q(x)$ が $p(x|w)$ で実現可能でないときの $W_0$ の異なる2つの元は同じ確率分布を表すとは限らない…？

それは簡単かな。例えば、まあめちゃくちゃ極端な例だけど「コインを1枚投げて表か裏か」を生成する真の分布が $q({\rm head}) = 0.5$ だったとする。でも、なぜか確率モデルとパラメータ集合は $p({\rm head} | w) = w, \; W = \{0,2, \, 0.4, \, 0.6, \, 0.8\}$ みたいになってて真の分布を実現可能じゃなかったとする。このとき、 $W_0 = \{0.4, \, 0.6\}$ だけど、 $w_0 = 0.4$ が与える分布と $w_0 = 0.6$ が与える分布は違う。

なるほど。確率モデルの制約で真の分布を実現できないが、最接近点が2つ以上あるといった感じですか。例8（1）はそれよりさらに極端な例ですね、あらゆる $\theta$ で $L(\theta)$ は同じになります。ので、すべての $\theta$ が最適ですが、 $\theta$ が異なれば確率モデルが与える確率分布は異なります。例8（2）は…何ですかこれ？

確率モデルは分散1の正規分布にみえるね。平均が $x,y,w$ によって異なる…これ、さながら中間層が1層のニューラルネットワークだね。 $z$ の真の平均は $\exp(-x^2-y^2)$ っていう原点が頂点の山だけど、2つの $\tanh()$ の和でこれを表すのは表現力が足りないし、 $L(w)$ を最小にするパラメータが1つあったとして $(b_{11}, b_{21}), \, (b_{12}, b_{22})$ の偏角を同じだけずつぐるっと回しても $L(w)$ は同じはずだから結局最適な $w_0$ は無数にある。そしてそれぞれが与える確率分布は違う。

パラメトリックな確率モデルとしてそういうものを選んでしまうと最適解が無限にある谷底になってしまうんですね…。35ページでは対数尤度比の「相対的に有限な分散」という概念が出てきますね。36ページの一番下のようにもかけるということですが…だから何なのでしょう。

対数尤度比は最適なパラメータでゼロをとり、その2乗平均はあらゆる $x$ で対数尤度比がゼロの周りで平均的にどれだけばらつくかを意味するね。ゼロの周りでのばらつきは一般に小さい方がいいだろう。ばらつきが大きいなら、最適に近いパラメータがたくさんあることになって、推定が不安定そうだからね。ただ、対数尤度比がゼロの周りでばらつくとしても、対数尤度比自体が平均的に小さいなら、本当に最適に近いパラメータの範囲が広いんだからばらついてもしょうがない。だから「対数尤度比のゼロの周りでのばらつきが対数尤度比の期待値の定数倍で抑えられてほしい」ってことになるのかな。だいぶ雰囲気だけど。さっきのコイン投げの例で $W = \{0.4, \, 0.6\}$ とすると相対的に有限な分散にはならないと思う。 $\mathbb{E}_X [f(x, 0.4, 0.6)]$ $= \mathbb{E}_X [f(x, 0.6, 0.4)] = 0$ だけど、一方で $\mathbb{E}_X [f(x, 0.4, 0.6)^2]$ $= \mathbb{E}_X [f(x, 0.6, 0.4)^2] > 0$ だから、やっぱり定数 $c_0$ をどうとっても式 (2.6) を成り立たせることができない。

はあ…補題4もみてみますね。(1) のいっていることは、最適なパラメータが複数あったとしても、対数尤度比が相対的に有限な分散をもつ場合は、最適な異なる2つのパラメータ間の対数尤度比がいかなる $x$ でもゼロになる…であれば、いかなる $x$ でも確率確率密度は同じということなので、実質的にユニークですね。相対的に有限な分散をもたない場合は最右辺がかけないので対数尤度比がいかなる $x$ でもゼロとはいえないですね。対数尤度比の期待値はゼロだが、それはある $x$ では片方の確率密度が大きく、また別の $x$ ではもう片方の確率密度が大きく、対数尤度比がマイナスとプラスを波打ち、均してゼロになっているという状態ですね。(2) は…何がなんだか。

…実現可能なときは、最適なパラメータとの対数尤度比の期待値はカルバック・ライブラー情報量になるんだね。このカルバック・ライブラー情報量は最適なパラメータの近くではゼロに近いから、実現可能な場合には最適なパラメータの近くで対数尤度比の期待値がゼロに近くて、分散の大きさも抑えられるということを示しているんだとは思うけど…。(3) も証明を追えてないけど、察するに最適なパラメータがお椀の底である場合には相対的に有限な分散をもちそうだね。というより、対数尤度比の期待値がちゃんと正の値になりそう。

注意13の (2) も気になりますが、置いておきますか。…と、ここまでが 2.1 節ですか。えっと、私たちはこの節で何を学んだのでしたっけ…？

私たちがこの節で学んだことは図 2.1 に他ならないよ。このベン図は6つの領域に区切られているけど、あらゆる「真の分布」と「それに寄せたいパラメトリックな分布」の関係はこの6つの領域のどこかに落ちる。

なるほど。これ、補題3と補題4が集約された図なんですね。しかし、節の最後に、ここまではサンプルが介さない話だともありますね…。

（ノート4があれば）つづく

2019-04-30

論文読みメモ： Poincaré Embeddings for Learning Hierarchical Representations（その1）

論文読み

以下の論文を読みます。

Maximilian Nickel, Douwe Kiela. Poincaré Embeddings for Learning Hierarchical Representations. In Advances in Neural Information Processing Systems, 2017. https://papers.nips.cc/paper/7213-poincare-embeddings-for-learning-hierarchical-representations

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

次回：まだ

階層的な表現を学習するためのポアンカレ埋め込み…テキストやグラフといったシンボリックなデータを数値ベクトル化したいとき、そのようなデータは潜在的な階層構造（？）をもつことが多いので、それを考慮するには双曲空間（ここでは特にn次元ポアンカレ球体模型）という空間の数値ベクトルにすると階層構造も類似度も同時に捉えられてよい、という話なのですね？具体的にこの論文で行ったことは、そのような数値ベクトル表現を得る方法をリーマン計量（？）における最適化に基づいて提案し、潜在的な階層構造をもつデータで検証して、ポアンカレ球体模型への埋め込みはユークリッド空間への埋め込みより表現力も汎化性能も上回ることを示したようですが…表現力と汎化性能って別の概念なんですか？

6ページのテーブルの下の Reconstruction と Link Prediction がそれぞれその指標みたいだね。グラフ埋め込みでよく用いられる指標みたい。まだきちんと読んでないけど、前者は上位概念―下位概念の関係をもつ単語ペアを、そのような関係をもたない単語ペアより近くに配置したかって感じなのかな。後者は、評価対象の単語ペアの関係を意図的に排除した状態で学習して、関係をもつ単語ペアを正しく近くに配置したかの推論の性能をみていると思う。両者は違う性能を測っているようにみえるね。単語ペアの関係がどのように与えられているデータセットなのかが確認しないとそれってどういう推論なのかはよくわからないけど…。

上位概念―下位概念とは？

例えば、「動物」という単語と「猫」という単語は上位概念―下位概念だろうし、「猫」と「アメリカンショートヘア」もまた上位概念―下位概念だよね…自然言語は否応なくそういう構造をもってる。というか7ページの学習結果の図示をみても、そのまま mammal（哺乳類）― carnivore（肉食動物）― canine（イヌ科）― German Shephered（ジャーマンシェパード）っていう階層がみえるね。

単語の意味の包含関係ということでしょうか。しかし、それを聞くと潜在的ではなく明示的な階層構造をもつデータで、階層構造に基づいた評価をしているようにみえるんですが…まあいいです。それが双曲空間という空間だと上手くいくというというのはどういうことなんでしょう？双曲空間というのも数値ベクトルの集合ではあるんですよね？双曲空間だと上手くいくというからにはユークリッド空間とは何かが違うようですが、何が違うんでしょう？

そうだな…例えば、「犬」「柴犬」「ポメラニアン」という3つの単語を2次元に埋め込むことを考える。このとき、「犬」と「柴犬」、「犬」と「ポメラニアン」の角度はそれぞれ同じにしたいし、「柴犬」と「ポメラニアン」の角度はそれよりは大きい角度にしたいという要望があるとする。こういう埋め込みってできるだろうか？

え？うーん、犬を適当な $\theta$ 方向に配置して、 $\theta - \Delta \theta$ 方向に「柴犬」、 $\theta + \Delta \theta$ 方向に「ポメラニアン」を配置でもすればいいんじゃないですか？

まあそれでいいよね。じゃあ、犬種が10種類あったらどうだろう？

10種類ですか！？それは…「犬」の周りに犬種たちを配置してしまうとどうしても犬種どうしが近くなってしまいますね…2次元に埋め込むのは難しいと思います。次元がもっとほしいですね…。

うん、近似的に表現するにしても、あまりよくなさそうだよね。自然言語って、きっとある単語にひもづく下位概念の単語がたくさんあって、その中の単語にもまた下位概念の単語がたくさんあって、でも下位概念にいけばいくほど必ずしも単語同士の意味が実際的に近くなるってわけでもないんだよね。単語 $a$ の周りにたくさんの単語を埋め込みたいし、その中の一つの単語 $b$ の周りにもたくさんの単語を埋め込みたいし、さらにその中の一つの単語 $c$ の周りにもたくさんの単語を埋め込みたいけど、埋め込む場所はそんなに狭くしていきたくない、みたいな。そういう願いがあるとき、ユークリッド空間は狭い。

いやそこで空間に文句を付けてどうするんです？狭いといっても、それはもう仕方ないでしょう。

仕方なくないかな。だって、距離の定義を変えればいいんだから。

距離の定義を変える？この点とこの点の間の距離はこう、と勝手に決めてしまうのですか？確かに「単語 $b$ の周りの点は単語 $b$ から離れているとする」「単語 $c$ の周りの点は単語 $c$ から離れているとする」などとすれば「そんなに狭くしていきたくない」を達成できるかもしれませんが、それだとめちゃくちゃな空間になってしまいませんか？というかちゃんと任意の2点間に距離が定義できますか？

「距離の定義を変える」というのは2点間の距離を定義するんじゃないよ。点 $x$ と点 $y$ の距離っていうのは点 $x$ と点 $y$ を結ぶあらゆる連続な経路の「長さ」のうち一番短いものと考える。この「長さ」の定義を変える。例えば、ある点を通るとき、ある向きに通るときはその微小経路で「長さ」を $1dt$ 消費することにするけど、同じ点を別の向きに通るときは「長さ」を $100dt$ 消費することにする。こんな風に、あらゆる点に対してあらゆる向きに通るときの「長さ」を決める。経路の長さは経路上の点のそれを積分する。そうすると、最短経路が直線とも限らなくなってきて、空間内の2点間の「距離」が変わってくる。

点や通る向きによっても「長さ」を変えてしまうんですか？なんだか場所や向きによって通りにくさが違うようですね。通りにくい場所では地面がぬかるんでいるんでしょうか。向きによっても通りにくさが違うということは風も吹いている？ …随分天候が悪い空間ですね。

いや知らないよ…。

しかし、あらゆる点に対してあらゆる向きに通ったときの微小長さを定義すれば差し障りなく空間内の距離を改造できるということなんですか？

本当は微小長さを勝手に直接定義するわけじゃないんだけどね。厳密にいうと、各点に対して「その点を通るあらゆる向き」の集合ではなくて、「その点を通ったとき滑らかな関数がどれだけ変化するかの写像（関数から微小変化への写像）」の集合を考える（この集合を接空間といって、この集合の元を接ベクトルというよ）。空間に定義される滑らかな関数がその点でどれだけ変化するかは、結局その点をどんな向きにどんな速度で通るかによるから、「その点を通るあらゆる向き」の集合を考えてるのとだいたい似てるんだけど。それでいま各点の接空間（その点を通るあらゆる向きっぽい集合）の各元に対して「その向きに通ったときの微小長さ」を定義したいんだったよね。ここでは接空間にノルムを入れてそれを微小長さとすることでそれを達成する。ノルムというか内積を定義して内積が誘導するノルムを採用するんだけどね。この内積がリーマン計量だ。

リーマン計量？アブストラクトにも「リーマン計量における最適化」とありました。

こういう枠組みで「長さ」を一般化して最適化を考えるということだろうね。リーマン計量によって長さが定義された空間をリーマン多様体というよ。私たちがよく知るユークリッド空間も、この論文が採用した双曲空間も、リーマン多様体の例だね。

…あの、リーマン計量では接空間に内積を定義することによって長さを定めるようですが、そこは内積やノルムによらないといけないものなんですか？そのリーマン計量を入れたリーマン多様体というのが空間の「長さ」を一般化した姿としてしっくりくるものなのかよくわからなくて。

そこを外すと「長さ」というものが素朴に満たしてほしい性質を満たさなくなってくると思うな…長さが負とかになってもいいならノルムの正定値性を落としてもいいよ？擬リーマン多様体っていってそういう対象も物理学とかでは利用されているみたいだから。

あ、長さが負とかは結構です。…そうですね、通常のユークリッド空間のリーマン計量というのは、どのような内積なんでしょうか。

ユークリッド計量はこうかな。

$\displaystyle g_p \left( \sum a_i \left( \frac{\partial}{\partial x_i} \right)_p , \; \sum b_i \left( \frac{\partial}{\partial x_i} \right)_p \right) \equiv \sum a_i b_i$ つまり、点 $p$ をある方向にある速度で通るときの微小変化が $\displaystyle \sum a_i \left( \frac{\partial}{\partial x_i} \right)_p$ なら、ここをそのように通るときの微小長さが $\sqrt{ || a ||^2 }$ ってことだね。

…すみません、それがどう私たちの知る距離を意味しているのか。

2次元平面を考えよう。時刻 $t=0$ に $(x_1, x_2) = (0,0)$ を出発して、時刻 $t=1$ に $(x_1, x_2) = (1,1)$ に到着するようにまっすぐ等速で歩く（まっすぐとは何かは計量によるけど、いまはユークリッド計量だから私たちのよく知るまっすぐね）。この経路の長さを測ろう。時刻 $t_0$ に $\gamma(t_0) = (t_0, t_0)$ にいるような経路だね。 $(t_0, t_0)$ を通る時、2次元平面上の任意の滑らかな関数 $f$ がどう微小変化するかを、 $v_{t_0}(f)$ とかこうか。 $v_{t_0}(f)$ は、

$\displaystyle v_{t_0}(f) = \lim_{t \to t_0}\frac{f(\gamma(t)) - f(\gamma(t_0))}{t - t_0} = \lim_{t \to t_0}\frac{f(t,t) - f(t_0, t_0)}{t - t_0}$
$\displaystyle \qquad \; \; = \lim_{t \to t_0}\frac{f(t,t) - f(t_0, t)}{t - t_0}+ \lim_{t \to t_0}\frac{f(t_0,t) - f(t_0, t_0)}{t - t_0}$
$\displaystyle \qquad \; \; = \left. \frac{\partial f}{\partial x_1} \right|_{(x_1, x_2)=(t_0, t_0)} + \left. \frac{\partial f}{\partial x_2} \right|_{(x_1, x_2)=(t_0, t_0)}$

だから結局、時刻 $t_0$ の接ベクトル $v_{t_0}$ がどういう写像だったのかというと、

$\displaystyle v_{t_0} = \left. \frac{\partial}{\partial x_1} \right|_{(x_1, x_2)=(t_0, t_0)} + \left. \frac{\partial}{\partial x_2} \right|_{(x_1, x_2)=(t_0, t_0)}$

だから、 $a_1 = a_2 = 1$ だね。よってこの経路の長さは、

$\displaystyle L(\gamma) = \int_0^1 \sqrt{g_p (v_t, v_t)} dt = \int_0^1 \sqrt{a_1^2 + a_2^2} dt = \int_0^1 \sqrt{1 + 1} dt = \sqrt{2}$

確かに $\sqrt{2}$ ですね。では、ユークリッド計量から別のリーマン計量に変えるとどうなるのでしょう。

この論文ではポアンカレ球体模型というリーマン多様体を利用しているからそれにしようか。さっきの経路の例で最後の計量だけ取り替えよう…と思ったけど、ポアンカレ球体模型は原点からのユークリッド距離が1未満の開球みたいだからさっきの経路だと突き抜けちゃうな。途中の時刻で歩くのをやめようか。ポアンカレ球体模型の計量は、論文の3ページにユークリッド計量との関係式があるね（計量ではなくて計量テンソルというものの関係式としてかかれているけど、この場合は計量の関係式と考えていいよ）。つまり、ユークリッド計量の $\displaystyle \left( \frac{2}{1 - ||x||^2} \right)^2$ 倍にしろってことみたいだ（ $||x||$ はユークリッドノルム）。その点を通るときの微小長さが原点からのユークリッド距離に依存することになる。この倍率は原点では 4 で、開球の端（ $||x||=1$ ）に近づくほど正の無限大に近づくね。つまり、開球の端の方では、近い点がめちゃくちゃ遠い。

何ですかその謎の日本語は…「ユークリッド計量では近い点が」という意味だとわかりますけど。

まあそれで $(0,0)$ から $(T, T)$ まで歩く経路の長さはこうなる。

$\displaystyle L(\gamma) = \int_0^T \frac{2 \sqrt{ g_p (v_t, v_t) } }{1 - ||(t,t)||^2} dt = \int_0^T \frac{2 \sqrt{2}}{1 - 2t^2} dt = 2 \, {\rm artanh} (\sqrt{2}T)$

論文の4ページに任意の2点間の距離の式が明示的にかいてあるけど、 $u=(0,0), \,v=(T, T)$ を代入するとこの結果と一致するよ。計算してみて。

え？えっと、 ${\rm artanh}(x)$ と ${\rm arcosh}(x)$ の定義に戻せば…確かに一致しますね。ん？いやでも、論文4ページの式 (1) は点 $u$ と点 $v$ の「距離」、つまり、「点 $u$ と点 $v$ を結ぶ経路のうち最短なものの長さ」ですよね。いま点 $(0,0)$ から点 $(T, T)$ にまっすぐ歩いた経路は確かにユークリッド空間において最短経路ですが、ポアンカレ球体模型においてもこれが $(0,0)$ から $(T, T)$ への最短経路ということですか？

まさしく。ポアンカレ球体模型の計量でユークリッド計量に乗じる倍率 $\displaystyle \left( \frac{2}{1 - ||x||^2} \right)^2$ って、原点から動径方向に遠ざかるほど「微小長さ」が長くなっていくことを意味してるけど、だったら現在地から動径方向にある目的地に行きたいときは迂回しても意味ないからね。「迂回すると微小長さが短い領域を歩けてお得」ってことにならないから。だから素直に動径方向に歩くのが最短。最短経路がユークリッド計量のときとずれてくるのは、スタートからゴールの向きが動径方向ではないときだ。この場合は（ユークリッド計量でいう）まっすぐ進むよりも、ちょっと原点に引っ張られるようにカーブしながら進む方が「微小長さ」を節約できる。原点に近いほど「微小長さ」が短いからね。論文3ページの Figure 1 の (a) にピンクとブルーとオレンジの線があるけど、これらはこの両端の点を結ぶ最短経路だよって図だと思う。ピンクだけは動径方向だから「まっすぐ」だね。

対して、ブルーとオレンジの線は確かに原点にひっぱられたカーブといった感じがしますね…これらは具体的にどういうカーブなんでしょう？

まずこういう2点を結ぶ最短経路のことを測地線というんだけど、ポアンカレ球体模型の場合は測地線は境界面に直交する円弧になる。ブルーとオレンジの線もそうみえるよね。

境界面に直交する円弧が本当に最短かどうかは、そういう円弧が測地線方程式っていう微分方程式を満たすことを示せばいい。けどすぐできなかった。ポアンカレ球体模型じゃなくてポアンカレ半平面模型っていうちょっと違うリーマン多様体の場合は測地線方程式から測地線はこうって記事が結構みつかる気がする。こっちの場合の測地線も境界と直交する円弧なんだけどこっちは球体じゃない。

そうですか…論文に戻って、先に最後の Discussion and Future Work もみておきます。…といっても、今後の展望として色々あって、埋め込み後の後段のタスクのモデルが現状ではユークリッド空間向けになっているので双曲空間向けにしなくては、といったくらいですかね。

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