2019-07-09

雑記： KKT条件の話

雑記

お気付きの点がありましたらご指摘いただけますと幸いです。全体的にきちんとした証明を欠きます。

参考文献

機械学習のための連続最適化 (機械学習プロフェッショナルシリーズ) | 金森敬文, 鈴木大慈, 竹内一郎, 佐藤一誠 |本 | 通販 | Amazon
- 162ページに KKT 条件が出てくる（1次独立制約想定での証明がある）。
Convex Optimization – Boyd and Vandenberghe
- ウェブで読める凸最適化の本で、263ページに Farkas の補題がある。
https://www.jstage.jst.go.jp/article/ieejeiss1987/109/4/109_4_178/_pdf
- ウェブに落ちていた PDF で、183 ページにバナッハ空間かつ制約想定を課さないときの KKT 条件（KKT 条件ではないが）が出てくる。
KKT 条件 - 数理計画用語集
工学基礎最適化とその応用 (新・工科系の数学) | 矢部博 |本 | 通販 | Amazon

注意（2019-07-16 追記）

この記事では適当な制約想定を課してから Farkas の補題によって KKT 条件を得る流れを紹介していますが、KKT 条件を得る流れは他にもたくさんあります。例えば、
- 先に Fritz John の定理を示し、それに適当な制約想定を課して KKT 条件とする（参考文献5. ）。
- 一次独立制約想定を課し、最適解が有効制約について等式制約付き最適化問題の最適解にもなっていることを利用して KKT 条件を得る（参考文献1. ）。
- 強双対性を課し、強双対性から示す（サポートベクターマシンの文脈でよくみられるはず；下記）。
サポートベクターマシンの文脈でみられる（＝強双対性を課した下での）の KKT 条件は、「が存在する」だけでなく、「が存在し、かつこれが双対問題の最適解である」というもっと強いことをいっています（ので、最適化問題を解く代わりにその双対問題を解いてもよい、ということになります）。それは強双対性が満たされている場合にのみ成り立つ話なのでご注意ください。サポートベクターマシンの文脈に絞った KKT 条件を知りたい方は、この記事を読んでも得るものが少ないので、強双対性の下で KKT 条件を示している文献を参照されるのがよいと思います。例えば、以下の書籍の付録Bがそうです。
- カーネル法入門―正定値カーネルによるデータ解析 (シリーズ多変量データの統計科学) | 福水健次 |本 | 通販 | Amazon
この記事は冒頭でサポートベクターマシンに言及していますが、サポートベクターマシンの文脈での最適化問題を想定しているわけではありませんのでご注意ください。

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

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

サポートベクターマシンの本を読んでいくと、突如として KKT 条件というのが出てきて戸惑いませんか？急に見知らぬ変数と不等式が増えますし、KKT という名前もどこの株式会社かといった感じですし…。

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

Karush–Kuhn–Tucker 条件は不等式制約付きの最適化問題の局所最適解が満たす必要条件だね。

定理．Karush–Kuhn–Tucker（KKT）条件

$x^\ast$ を問題（P）の局所最適解とする．但し， $f, \, g_i \, (i = 1, \cdots, m)$ は $x^\ast$ で微分可能であり，かつ，ある条件（例えばこの中のどれか）が満たされているものとする．

（P） $\displaystyle \underset{x \in \mathbb{R}^n}{\rm minimize} \; \; f(x) \quad {\rm subject \; to} \; \; \; g_i(x) \leqq 0, \quad i = 1, \cdots, m$

このとき，以下を満たす $\lambda^\ast \in \mathbb{R}^m$ が存在する．

$\begin{cases} \displaystyle \nabla f (x^\ast) + \sum_{i=1}^m \lambda^\ast_i \nabla g_i (x^\ast) = \vec{0} \\[5pt] g_i(x^\ast) \leqq 0 \; \; (i = 1, \cdots, m) \\[5pt] \lambda^\ast_i g_i (x^\ast) = 0 \; \; (i = 1, \cdots, m) \\[5pt] \lambda^\ast_i \geqq 0 \; \; (i = 1, \cdots, m) \end{cases}$

Wikipedia によると最初はこの条件を発表した Kuhn と Tucker にちなんで呼ばれていたみたいだけど、後に彼らの発表の 12 年前に Karush が修士論文でこの条件を主張していたのが見つかって、彼の名も冠してこの名前になったのかな？

なんと、それで KKT というのですか…研究成果を12年前に修士論文で導出していましたといわれるのもなかなかショックですね。Karush 氏ももっとツイッターで自身の結果を宣伝しておくとよかったのでは？

1939年にツイッターはないからね。

さておき、なぜサポートベクターマシンの本で急に KKT 条件が出てくるのでしょう？ $\lambda^\ast$ （これは $\alpha^\ast$ かもしれないしお手元の本によります）という知らないベクトルが存在するといわれても反応に困るんですが。 $\lambda^\ast$ って何なんです？そしてなぜそのような不等式たちが成り立つんです？そもそも、「最適解はこのような条件たちを満たす」といわれても、だから何なんです？式が増えてかえってややこしくなった気がするんですが…。

$\lambda$ は KKT 乗数ともよばれる、等式制約付き最適化でいうラグランジュ乗数に相当するものだね。それが何なのかというのは、なぜ KKT 条件が成り立つのかを証明する過程で得ないといけないかな。先に、KKT 条件を満たすから何なのかというのは、どこにあるかまるで見当もつかない「最適解」について、「このような条件を満たす」という情報が得られること自体がありがたいんじゃないのないかな？ KKT 条件があるお陰で、これをつかって最適解に向かうアルゴリズムを構築することができる（実際多くのアルゴリズムが KKT 条件を解いていると解釈できるらしい）けど、これがなかったら定義域の1点1点を「不等式制約を満たすか」「これまで探索した点より小さいか」をあてもなく探索しないといけなくて、途方もないよ？それにサポートベクターマシンの場合は、KKT 条件から「限られた一部のデータ（サポートベクター）のみが解となる分離超平面を形づくっている」という重要な事実が直接的にわかるからね。最適解の必要条件がわかることは強力だよ？

うーん、そういわれてみれば最適解について重要な手がかりを与えてくれているような気はしてきましたが…しかし、なぜ最適解では KKT 条件が成り立つんでしょう？どのように考え始めればいいやら…。

そうだな…まず、制約がない場合をイメージしてみると、局所最適解ってどんな点かな？あ、 $x^\ast$ が局所最適解っていうのは、その点 $x^\ast$ を中心にしたある半径 $\delta > 0$ の開球 $B(x^\ast; \delta)$ の中でその点が最小 $\forall x \in B(x^\ast; \delta), \; f(x^\ast) \leqq f(x)$ って意味ね。局所最適解であっても大域最適解とは限らないけど、大域最適解は必ず局所最適解だから、大域最適解がどんな点か調べるのに局所最適解がどんな点かを考えてもいい。

制約がない場合に局所最適解はどんな点かといわれても…制約がないんだったらもう単純に $f(x)$ が一番小さい点でしかないですよね？

うん。言い換えると、 $x^\ast$ からどんな向きに進んでも $f$ の値が「より小さくなる」ことはないよね？

そうですね、もし最適解が平らな場所にあったら、少し進んでも $f$ の値が変わらない（最適解から少し進んでも最適解という状態）ということはあるかもしれませんが、 $f$ の値が小さくなることは絶対にないです。もし小さくなるなら、そこはもはや最適解ではないですから。

「より小さくなることはない」を言い換える。「 $\nabla f(x^\ast)^\top s < 0$ となるような $s \in \mathbb{R}^n$ は存在しない」。

《注意》この言い換えは $f(x^\ast + s)$ が $f(x^\ast + s) \approx f(x^\ast) + \nabla f(x^\ast)^\top s$ と一次近似できるほど $x^\ast$ に十分近いところでは」のようなイメージで理解できると思いますが、近似的でなくても成り立ちます。が、証明はここでは割愛します。

え、えっと？ $\nabla f(x)$ は $f(x)$ の勾配といって、ヤコビ行列の転置なのですね。

$\nabla f(c)^\top = Df(c) = \displaystyle \left( \frac{\partial f}{\partial x_1}(c) \;\; \cdots \;\; \frac{\partial f}{\partial x_n}(c) \right)$ ならば $\nabla f(x^\ast)^\top$ は $f$ の $x^\ast$ におけるヤコビ行列そのもので、 $\nabla f(x^\ast)^\top s$ は $f$ の起点 $x^\ast$ における増分 $s$ の微分ですね…この微分が負になるような増分は存在しない、ということは…起点 $x^\ast$ からどんな方向付きステップ $s$ だけ進んでも、より小さくなることはない、ということですね。

だから、どんな $s$ でも $\nabla f(x^\ast)^\top s \geqq 0$ でないといけないし、一方、 $-s$ に対しても $-\nabla f(x^\ast)^\top s \geqq 0$ でないといけない。結局、任意の $s$ に対して $\nabla f(x^\ast)^\top s = 0$ でないといけない。であれば、 $\nabla f(x^\ast) = \vec{0}$ でないといけない。制約がないバージョンの「KKT条件」はこれで終わりだ。

定理．制約がないときの1次の必要条件

$x^\ast$ を問題（P）の局所最適解とする．但し， $f$ は $x^\ast$ で微分可能であるものとする．

（P） $\displaystyle \underset{x \in \mathbb{R}^n}{\rm minimize} \; \; f(x)$

このとき，以下が満たされる．

$\; \nabla f (x^\ast) = \vec{0}$

これだけですか？ $\lambda^\ast$ などは出てこないんですね。KKT 条件の最初の式のもっとシンプルなのだけ、といった感じでしょうか。

あくまで必要条件だから、 $\nabla f(x) = \vec{0}$ なら $x$ が局所最適解というわけではないからね。…じゃあ等式制約 $h_i(x) = 0 \, (i = 1, \cdots, m)$ がある場合はどうだろう？最適解 $x^\ast$ は依然として「どんな向きに進んでも $f$ の値がより小さくなることはない」点だろうか？

等式制約がある場合は…等式制約を満たす範囲で $f$ が最小の点を探さなければなりませんね。 $x$ が2次元の場合でイメージすると、制約がない場合は2次元平面全体から解を探していたのが、 $h(x)=0$ という制約があるとこれを満たす曲線上でだけ解を探すといった感じです。この場合の $x^\ast$ も「どんな向きに進んでも $f$ の値がより小さくなることはない」点になっているかといわれると…違いますね。 $x^\ast$ はあくまで曲線 $h(x)=0$ 上で一番小さい点です。この曲線をはみ出す向きに進むならば $f(x)$ は小さくならないとは限りません。

つまり、「 $\nabla h(x^\ast)^\top s = 0$ かつ $\nabla f(x^\ast)^\top s < 0$ となるような $s \in \mathbb{R}^n$ は存在しない」かな？

《注意》というには「このような $s$ が存在するならば $x^\ast$ が局所最適解であることに矛盾」をきちんと示さないといけないですが、 $f, \, h$ が $x^\ast$ で微分可能で $\nabla h(x^\ast) \neq 0$ ならば結果的には大丈夫だと思うんですが、あんまりイメージでものをいうのはよくないと思います。

今度は $h$ の微分も出てきましたね… $\nabla h(x^\ast)^\top s = 0$ とは $x^\ast$ から $s$ だけ進んでも $h$ の値が変わらないということですよね。…なるほど、最適解 $x^\ast$ は「 $h$ の値を変えずに $f$ を減らすような方向付きステップ $s$ が存在しない」点だといいたいのですね？

だから、さっきと同様の議論により、 $\nabla h(x^\ast)^\top s = 0$ を満たす $s$ では $\nabla f(x^\ast)^\top s = 0$ でないといけない（ここで $\nabla h(x^\ast) = 0$ となるような局所最適解 $x^\ast$ については考えないことにする； $h(x) = 0$ 上にこういう点があったら別途調べることにしよう）。ということは、 $\nabla h(x^\ast)$ と $\nabla f(x^\ast)$ って平行でないといけない。 $\nabla h(x^\ast)$ に直交する任意の $s$ が $\nabla f(x^\ast)$ に直交しないといけないからね。

え、直交？ああ、2つのベクトルの内積がゼロということは、直交するということでしたね。

だから、等式制約が1つのバージョンの「KKT条件」はこうなる。

定理．等式制約が1つあるときの1次の必要条件

$x^\ast$ を $\nabla h(x^\ast) = 0$ ではない問題（P）の局所最適解とする．但し， $f, \, h$ は $x^\ast$ で微分可能とする．

（P） $\displaystyle \underset{x \in \mathbb{R}^n}{\rm minimize} \; \; f(x) \quad {\rm subject \; to} \; \; \; h(x) = 0$

このとき，以下を満たす $\lambda^\ast \in \mathbb{R}$ が存在する．

$\begin{cases} \nabla f (x^\ast) + \lambda^\ast \nabla h (x^\ast) = \vec{0} \\[5pt] h(x^\ast) = 0 \end{cases}$

2つ目の条件式の $h(x^\ast) = 0$ は $x^\ast$ が問題（P）の局所最適解だから等式制約を満たしているって当然の話だけど、普通これも合わせてかくね。

あ、今度は $\lambda^\ast$ が出てきましたね…この $\lambda^\ast$ が存在することは $\nabla h(x^\ast)$ と $\nabla f(x^\ast)$ が平行であるための必要十分条件ですね。では KKT 条件の $\lambda^\ast$ も同じ意味なんでしょうか…ってあれ？いまは等式制約が1つのみの場合の条件を考えたんですね。KKT 条件を目標とするなら、等式制約が複数の場合についても考えた方がよいのではないでしょうか。その場合、「 $h_1, \cdots, h_m$ の値を変えずに $f$ を減らすような方向付きステップ $s$ が存在しない」のですよね。なので、 $\nabla h_i(x^\ast)^\top s = 0 \, (i = 1, \cdots, m)$ をすべて満たす $s$ では $\nabla f(x^\ast)^\top s = 0$ でもなければならないということになりますが、これは $\nabla f(x^\ast)$ が $\nabla h_i(x^\ast) \, (i = 1, \cdots, m)$ たちと同じ超平面内にあるというイメージです。とすると、 $\nabla f(x^\ast)$ が $\nabla h_i(x^\ast) \, (i = 1, \cdots, m)$ の線形和でかければよく、上の1つ目の条件式が $\nabla f (x^\ast) + \sum_{i=1}^m \lambda_i^\ast \nabla h_i (x^\ast) = \vec{0}$ と修正されるのではないでしょうか？あ、こうすれば KKT 条件の1つ目の条件式と同じ形になりますね！

その条件式でいいケースと駄目なケースがあるかな。

え？

3次元空間内での等式制約付き最適化を考えてみよう。 $xy$ 平面上にトーラスを置く。このトーラスの表面が $h(x)=0$ だとする。 $h(x)$ はトーラスの外側に向かうほど大きくなる関数とでもしよう。このとき、 $g(x)=0$ の下で $f(x, y, z) = x$ を最小化する点は、トーラスの表面上で $x$ 座標が一番小さい点だよね。この点ではトーラス上の勾配は $x$ 軸のマイナス方向を向いている。他方、 $f(x, y, z) = x$ の勾配は空間内のどこでも $x$ 軸のプラス方向を向いている。確かに2つの勾配は平行になっている。

文章だとわかりづらいですね…絵でも描いてくださいよ…。

じゃあ等式制約をもう1つ増やそう。ドーナツの上にドーナツを重ねるようにトーラスの上にもう1つトーラスを置こう。制約を満たす領域（よく実行可能領域というね）は曲面から曲線になる。2つのトーラスが接する円周上になるからね。

いや、日常でドーナツの上にドーナツを重ねませんよ…。

このとき制約下で $f(x, y, z)=x$ を最小化する点は円周上で $x$ 座標が一番小さい点だけど、この点で $f$ の勾配は、トーラス（下側）の勾配とトーラス（上側）の勾配の線形和になるかな？

あれ、ならないですね。 $f$ の勾配は $-x$ 方向を向いている一方で、トーラスたちの勾配は $+z$ 方向と $-z$ 方向です。これらでは $f$ の勾配をつくれません…。

トーラスどうしが少しでもめり込んでいたらそうならないんだけどね。「どっちのトーラスの勾配にも垂直な向き」がちゃんと「すべての制約からはみ出さない向き」になるから。でも、トーラスどうしが接していると「どっちのトーラスの勾配にも垂直な向き」が「すべての制約からはみ出さない向き」にならないんだよね。勾配どうしが平行になっちゃってるせいで「どっちのトーラスの勾配にも垂直な向き」じゃ制約の中に閉じ込められないって感じかな。

《注意》ドーナツの例が文章で伝わらなかった方は、参考文献1. の 148 ページの例 9.2 が同じ趣旨だったのでこれをご参照ください。

だからもう、制約付き最適化の局所最適解の必要条件を考えるとき、こういうケースは除外しちゃう。

ええ…。

よく仮定されるのがこの中の LICQ（Linear Independence Constraint Qualification）だね。局所最適解 $x^\ast$ では全ての制約の勾配が線形独立であるとするって仮定。

定理．等式制約があるときの1次の必要条件

$x^\ast$ を問題（P）の局所最適解とする．但し， $f, \, h_i \, (i = 1, \cdots, m)$ は $x^\ast$ で微分可能であり，かつ，LICQ が満たされているものとする．

（P） $\displaystyle \underset{x \in \mathbb{R}^n}{\rm minimize} \; \; f(x) \quad {\rm subject \; to} \; \; \; h_i(x) = 0, \quad i = 1, \cdots, m$

このとき，以下を満たす $\lambda^\ast \in \mathbb{R}^m$ が存在する．

$\begin{cases} \displaystyle \nabla f (x^\ast) + \sum_{i=1}^m \lambda^\ast_i \nabla h_i (x^\ast) = \vec{0} \\[5pt] h_i(x^\ast) = 0 \; \; (i = 1, \cdots, m) \end{cases}$

上には LICQ とかいたけど、例えば LICQ の1つ上にある LCQ（Linearity Constraint Qualification）を仮定してもいいよ。こっちは全ての制約が線形関数という仮定だね。全ての制約が線形なら「ちょうど局所最適解のところでだけ接する」なんてことにならないからね。ただ LCQ は LICQ よりずっと強い仮定になるね。LICQ や LCQ のような仮定は制約想定（constraint qualification；CQ）といわれるよ。LICQ より下の方の仮定は MFCQ は等式制約のみの場合は LICQ と同じだし、SC は LCQ と同じだけど、それ以外はちょっとよくわかってないや。そもそもこれらの制約想定が不等式制約もある場合のものだけど。

そうです、考えたかったのは不等式制約の場合です。早速そちらを考えていきましょう。これまでと同じように考えると…あれ？えっと、どう考えればいいのでしょう？？

例えば2次元平面内での最適化だったら、等式制約 $h(x)=0$ は実行可能領域をある曲線上に絞り込むようなイメージだけど、不等式制約 $g(x) \leqq 0$ は曲線で囲まれた領域に絞り込むイメージだね。それで、不等式制約付き最適化の場合は、考える局所最適解 $x^\ast$ が、領域の境界上にある場合も、領域の内部にある場合もある。不等式制約が複数ある場合は一般に、 $x^\ast$ はある不等式制約たちについては領域の境界上だけど、その他の不等式制約たちについては領域の内部って感じになる。前者の制約では $g_i(x^\ast) = 0$ で、後者の制約では $g_i(x^\ast) < 0$ だね。この前者の $g_i(x^\ast) = 0$ となる制約を「有効」な制約ということが多いよ。まあそれで、不等式制約付き最適化問題の局所最適解 $x^\ast$ は、「有効な $g_i$ を大きくしないままに $f$ を小さくする向きが存在しない」点といえる。

なるほど、「不等式を満たしながら最適化せよ」という問題ですから、「余裕で満たされる」制約もあれば、「ぎりぎり満たされる」制約もありますね。ある制約が余裕で満たされている場合は、その制約は局所最適解が満たす条件に関わってこないということですね。確かに、局所的にはそんな制約は最初からなかったも同然ですもんね。では、「有効なすべての $g_i$ に対して $\nabla g_i(x^\ast)^\top s \leqq 0$ であって、かつ $\nabla f(x^\ast)^\top s < 0$ となるような $s \in \mathbb{R}^n$ は存在しない」といった感じになるでしょうか？

それだとドーナツ重ね問題が発生するんだよね。ドーナツの内部が負のとき、2つのドーナツが接する円周上が実行可能領域になるけど、この円周上の最適解 $x^\ast$ から $-x$ 方向に向かうベクトル $s$ は $\nabla g_1(x^\ast)^\top s = 0$ も $\nabla g_2(x^\ast)^\top s = 0$ も $\nabla f(x^\ast)^\top s = 0$ も満たしちゃうからね。

では、すべての有効な制約の勾配に LICQ を仮定すればいいですね。

それでもいいけど、もっと弱い仮定もあるよ。この中の LICQ の下にある MFCQ が例えばそう。表の下に LICQ ⇒ MFCQ ってあるよね。MFCQ は $\exists d \in \mathbb{R}^n, \, \nabla g_i(x^\ast) ^\top d < 0$ for all active inequality constraints ―つまり、「すべての有効な制約について $g_i(x^\ast)$ を同時に減らす方向 $d$ が存在する」って感じかな。ドーナツを2つ重ね置きした場合のドーナツが接する円周上にそんな点はないよね。同時に2つのドーナツの内部に向かうベクトルはないからね。

へえ。しかし、なぜその仮定で大丈夫なんです？

まず MFCQ を課さずに以下の上の定理が示せて、それに MFCQ を課すと下の定理が示せるんだよね。あ、 $I(x^\ast)$ は $x^\ast$ において有効な制約の添え字を集めた集合ね。

定理．不等式制約があるときの1次の必要条件

$x^\ast$ を問題（P）の局所最適解とする．但し， $f, \, h_i \, (i = 1, \cdots, m)$ は $x^\ast$ で微分可能であるものとする．

（P） $\displaystyle \underset{x \in \mathbb{R}^n}{\rm minimize} \; \; f(x) \quad {\rm subject \; to} \; \; \; g_i(x) \leqq 0, \quad i = 1, \cdots, m$

このとき，以下を満たす $s \in \mathbb{R}^n$ は存在しない．但し， $I(x) = \{i \, | \, g_i(x) = 0\}$ とする．

$\begin{cases} \displaystyle \nabla f (x^\ast) ^\top s < 0 \\[5pt] \nabla g_i (x^\ast) ^\top s < 0 \; \; (i \in I(x) \, ) \end{cases}$

定理．不等式制約があるときの1次の必要条件（MFCQ下）

$x^\ast$ を問題（P）の局所最適解とする．但し， $f, \, h_i \, (i = 1, \cdots, m)$ は $x^\ast$ で微分可能であり，かつ，MFCQ が満たされているものとする．

（P） $\displaystyle \underset{x \in \mathbb{R}^n}{\rm minimize} \; \; f(x) \quad {\rm subject \; to} \; \; \; g_i(x) \leqq 0, \quad i = 1, \cdots, m$

このとき，以下を満たす $s \in \mathbb{R}^n$ は存在しない．但し， $I(x) = \{i \, | \, g_i(x) = 0\}$ とする．

$\begin{cases} \displaystyle \nabla f (x^\ast) ^\top s < 0 \\[5pt] \nabla g_i (x^\ast) ^\top s \leqq 0 \; \; (i \in I(x) \, ) \end{cases}$

どちらも同じにみえるんですが…あ、よくみると、下の定理では2つ目の条件式にイコールが付いているんですね。というか、下の定理はよくみるとさっき直感的に考えた「有効なすべての $g_i$ に対して $\nabla g_i(x^\ast)^\top s \leqq 0$ であって、かつ $\nabla f(x^\ast)^\top s < 0$ となるような $s \in \mathbb{R}^n$ は存在しない」と同じですね。イコールがない上の場合は MFCQ は要らないんですか？

うん。もしこのような $s \in \mathbb{R}^n$ が存在したら、 $g_i(x^\ast + ts) < 0$ かつ $f(x^\ast + ts) < f(x^\ast)$ を満たす $t \in \mathbb{R}$ がとれるからね。 $x^\ast$ が局所最適解であることに矛盾する。

では、MFCQ が課された場合は、つまり、 $\exists d \in \mathbb{R}^n, \, \nabla g_i(x^\ast) ^\top d < 0, \, \forall i \in I(x^\ast)$ が成り立つ場合はどうなるんでしょう？

下の定理の場合は、もしこのような $s \in \mathbb{R}^n$ が存在したら、 $s$ を少しずらした $\hat{s}$ が存在して $\nabla f(x^\ast) ^\top \hat{s} < 0, \, \nabla g_i(x^\ast) ^\top \hat{s} < 0, \, \forall i \in I(x^\ast)$ となるようにできる。これに上の定理を用いると $x^\ast$ が局所最適解であることに矛盾する。もし下の定理の2つ目の条件がイコールで成り立っていたら上の定理を適用できないけど、MFCQ ですべての有効な $g_i(x^\ast)$ が減る方向が存在することを仮定しているから、 $s$ を少しずらせばイコールがとれるんだよね。

説明が雑ですね…しかし、下の定理が示せたにしろ、冒頭の KKT 条件とだいぶ違いませんか？いま、「なぜ最適解では KKT 条件が成り立つのか」を知りたいんですが。

この下の定理と KKT 条件は同値だよ。

え、同値なんですか？そうはみえないんですが…。

次の補題をつかう。ここで（１）の $Ax \leqq \vec{0}$ はベクトルの各成分がゼロ以下って意味ね。

補題．Farkas’ lemma

$A \in \mathbb{R}^{m \times n}$ と $c \in \mathbb{R}^n$ に対して次の（１）または（２）が成り立つ．しかし同時に（１），（２）が成立することはない．

（１）　 $\exists x \in \mathbb{R}^n, \; Ax \leqq \vec{0}, \; c^\top x < 0$

（２）　 $\exists y \in \mathbb{R}^m, \; A^\top y + c = \vec{0}, \; y \geqq 0$

どちらか一方が成立し、同時に成立することはない、ですか。不思議な定理ですね。

Farkas の二者択一定理ともいうみたいだね。この（１）の $c$ を $\nabla f(x^\ast)$ に読み替えて、 $A$ を有効な制約について横ベクトル $\nabla g_i(x^\ast)^\top$ を縦に並べた行列に読み替えると、（１）が主張する「このような $x$ が存在する」は、不等式制約があるときの1次の必要条件（MFCQ下）の「このような $s$ は存在しない」の否定になっているよね？

えっと、そのように $c$ と $A$ を読み替えれば、（１）は確かに先ほどの定理を否定のようですね。先ほどの定理では存在しないといったものを存在するといっている。…否定じゃ駄目なんじゃないですか？

さっきの定理を仮定すると（１）が否定される。ということは、必ず（２）が成り立つ。二者択一定理だからね。そして、（２）が成り立つならば、 $y$ が存在する。この $y$ を $\lambda^\ast$ とかき換えるとどうだろう。

（２）の $y$ を $\lambda^\ast$ とかき換えて、 $c$ と $A$ もかき換えると、こうですね。…これ、KKT 条件の1番目と4番目の条件式ですね！

$\begin{cases} \displaystyle \nabla f (x^\ast) + \sum_{i \in I(x)} \lambda^\ast_i \nabla g_i (x^\ast) = \vec{0} \\[5pt] \lambda^\ast_i \geqq 0 \; \; (i = 1, \cdots, m) \end{cases}$

…でもよくみると、1番目の条件式の和が制約が有効な $i$ についてだけになってしまっていますね。それに、2番目と3番目の条件式も足りませんし。

KKT 条件の2番目の条件式は $x^\ast$ が局所最適解であることからただちにしたがうからさっきの定理から示す必要はないよ。そして残りの問題は、制約が有効でない $i$ で $\lambda_i^\ast = 0$ とすれば全部解決するかな。

力尽きた

2019-06-24

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

本読み機械学習

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

ベイズ統計の理論と方法

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

書籍サポートページ

これまで：ノート1 ／ノート2 ／ノート2.5 ／ノート3 ／ノート4章その0.1

前回（ノート3）で読んだ 30～40 ページをまとめるとこうですね。

$q(x)$ が $p(x|w)$ で実現可能　 $\Rightarrow$ 　 $f(x,w)$ は相対的に有限な分散をもつ
$q(x)$ が $p(x|w)$ で実現可能　 $\Rightarrow$ 　 $f(x,w)$ は相対的に有限な分散をもつ
$f(x,w)$ が相対的に有限な分散をもつ　 $\Rightarrow$ 　 $q(x)$ に対して最適な $p(x|w)$ は実質的にユニーク

それただの補題 4 じゃん…。

41ページに進むと、最適な確率分布 $p_0(x)$ が実質的にユニークな場合に限って考えれば、あらゆるパラメータにおける確率モデルを画一的に $\displaystyle p(x|w) = p_0(x) \frac{p(x|w)}{p_0(x)} = p_0(x) e^{ - p_0(x) / \log p(x|w)} = p_0(x)^{- f(x, w)}$ とかくことができるということです。あらゆる $x$ における $f(x, w)$ は $- \log(x|w)$ を定数 $\log p_0(x)$ だけシフトしたものになると。それはそうですね。また、あるパラメータにおける平均対数損失 $L(w)$ の、最適なパラメータにおける $L(w_0)$ との誤差は、 $\displaystyle L(w) - L(w_0) = - \int q(x) \log p(x|w) dx + \int q(x) \log p(x|w_0) dx = \int q(x) \log \frac{p(x|w_0)}{p(x|w)} dx$ より $f(x,w)$ の真の分布に対する平均に等しくなりますが、これが平均誤差 $K(w)$ と名付けられていますね。「損失」やら「誤差」やら「平均」やら「汎化」やら色々な言葉が出てきて、何がなにやらといった感じですが…。

「損失」というのは専ら「負の対数尤度」に用いられていると思う。この損失が小さくなるパラメータを探せというもので、「いまのパラメータのよさ」ともいえる。確率モデルに対する損失で真の分布に対する平均なら「平均対数損失」、経験分布に対する損失なら「経験対数損失」だね。他方、予測モデルに対する損失は「ベイズ推測という枠組み自体のよさ」で、「汎化損失」「経験損失」で測られるけど、「平均対数汎化損失」「経験対数汎化損失」という方が丁寧かもね。誤差は「損失を最小にする最適なパラメータとの対数（汎化）損失の差」だね。自由エネルギーのふるまいを知るのに平均対数損失じゃなく平均誤差を主役にした「正規化された自由エネルギー」で議論するみたい。最適なパラメータにおける自由エネルギーを原点にとるんだね。

では自由エネルギーは何だったのかというと、確率モデルの下でのサンプルの選択情報量のような量ですが、逆温度にもより、逆温度が正の無限大の極限で確率モデルの負の対数尤度になるのでしたっけ。それで44ページで、実数 $\alpha$ に対して汎化損失と経験損失のキュムラント母関数というのが定義されていますね。

　 $\mathcal{G}_n(\alpha) \equiv \mathbb{E}_X \Bigl[ \log \mathbb{E}_w \bigl[ p(X|w)^\alpha \bigr] \Bigl]$ 　 $\Biggl( G_n = - \mathbb{E}_X \Bigl[ \log \mathbb{E}_w \bigl[ p(X|w) \bigr] \Bigl] = - \mathcal{G}_n(1) \Biggr)$
　 $\mathcal{T}_n(\alpha) \equiv \displaystyle \frac{1}{n} \sum_{i=1}^n \log \mathbb{E}_w \bigl[ p(X_i |w)^\alpha \bigr]$ 　 $\Biggl( T_n = - \displaystyle \frac{1}{n} \sum_{i=1}^n \log \mathbb{E}_w \bigl[ p(X_i |w) \bigr] = - \mathcal{T}_n(1) \Biggr)$

確率変数 $X$ のキュムラント母関数 $K_X(t)$ とは、モーメント母関数 $M_X(t)$ を用いて $K_X(t) \equiv \log \bigl( M_X(t) \bigr) = \log \bigl( \mathbb{E} (e^{tX}) \bigr)$ というものなんですね。

キュムラント母関数 - Wikipedia

$\mathbb{E}_w \bigl[ \cdot \bigr]$ は事後分布による平均の意味なので、 $\mathbb{E}_w \bigl[ p(X|w)^\alpha \bigr]$ は、 $\alpha = 1$ とすればデータ $X$ が観測される確率の予測値（予測分布の $x=X$ での値）という二重の意味での確率変数ですね。つまり、 $\log \mathbb{E}_w \bigl[ p(X|w)^\alpha \bigr]$ は「ある未知データの対数尤度」なる確率変数 $\log p(X|w)$ の、予測分布を計算するのに用いた訓練サンプルの出方に対するキュムラント母関数ですね。 $\mathcal{G}_n(\alpha)$ と $\mathcal{T}_n(\alpha)$ はそれをさらに真の分布で平均したり、真の分布の代わりに経験分布で平均したりしたものであるようですが。そしてこれらを $\alpha$ で $k$ 階微分して $\alpha = 0$ としたのが $k$ 次キュムラントですか…我々はなぜ急にキュムラントなるものを突き付けられたのでしょう？

ゴールは47ページの定理1だね。

なんと、汎化損失と経験損失はキュムラントを用いてこのようにかけるのですか…だから何なのでしょう？

汎化損失を以下の要素と残差の和に展開できたんだから、

最適なパラメータにおける平均対数損失。
平均誤差の事後分布による期待値。
対数尤度比の2乗の事後分布による期待値から対数尤度比の事後分布による期待値の2乗を引いたものの真の分布の期待値。

ここからさらに仮定をおいていくことで、ベイズ推測は「 $n \to + \infty$ で収束するのか」「どこに収束するのか」「どのように収束するのか」が議論できるようになるんじゃないのかな…わからないけど。

補題 7 が $k$ 次キュムラントと対数尤度比の関係をいっているのですか。それに先立つ補題 6 が $k$ 次キュムラントと確率モデルの関係といった感じなんですね。補題 9 は、汎化損失と経験損失のキュムラント母関数のサンプルの出方に関する期待値の関係ですか。

つづきは後で

2019-06-16

NIPS2017読みメモ： Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles（その1）

論文読み

以下の論文を読みます。

Balaji Lakshminarayanan, Alexander Pritzel, Charles Blundell. Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles. In Advances in Neural Information Processing Systems 30 (NIPS 2017). https://arxiv.org/abs/1612.01474

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

次回：まだ

「ニューラルネットの予測の不確かさを如何に定量化するか」という課題を掲げていますね。重みの分布を学ぶベイジアンニューラルネットというのが現状その課題に対するSOTAな解法であるそうですが、一方でそれは従来のニューラルネットをあまりに改造しなければならず、計算コストもあまりに増大するといっています。そこで本論文では代わりにもっと手軽な手法を考案すると。この手法は分類問題においても回帰問題においても近似ベイジアンニューラルネットと同等以上の不確かさの推定性能を記録したようです…アブストラクトの時点では手法の内容についてはまだよくわかりませんね。

従来のニューラルネットをあまり改変しなくて済むってことくらいかな？あと論文のタイトルをみるにモデルをアンサンブルするっぽいね。先に最後の節もみてみようか…あ、ページをめくっていくと9ページの Figure 6 に「不確かな手書き数字」がみえるね。

いわれてみればタイトルの Scalable やら Ensembles やらがアブストで回収されていませんね…というか Figure 6 の字汚っ！これはさすがに判定させられるニューラルネットさんも怒っていいでしょう…いえ、通常のニューラルネットさんは「これが数字かどうかはとても不確かなのでは？」と文句をいうことができないのですね。それで、4節の Discussion の2文目が今回の提案手法について言及していますね…しかしここでも何やら「proper scoring rules」「アンサンブル」「敵対的学習」が用いられるらしいことくらいしかわかりません。イントロに戻ってみると、冒頭にはニューラルネットは強力な手法だが「予測の不確かさを定量化するのが不得手で自信過剰な予測をしがち」とあります…えっと、どういうことですか？ニューラルネットって欠陥品なんですか？

想像だけど、ニューラルネットが欠陥品というよりは、「人間が1つの正解をアノテートして、それだけを出力させるようモデルを訓練する」というやり方の限界なんだと思う。例えば、入力したメールがスパムメールでないなら０、スパムメールなら 1 を出力することを目指すニューラルネットなら、 $x_i$ がスパムメールでないなら $- \log (1 - f(x_i))$ 、 $x_i$ がスパムメールなら $- \log f(x_i)$ をそのデータの損失として損失の総和を最小化する（つまり正解ラベルのみで1をとる確率分布との交差エントロピーを最小化する）ことを目指すと思うけど、そうして学習したモデルの出力値を「入力したメールがスパムメールである確率」と解釈すべきではないんだよね。というのは、学習の目的関数が「真の分布は正解ラベルのみで1をとる」と仮定しているのがおそらく実際には正しくない。訓練データの中には、「現にスパムメールではあったけどそれが未知メールだと考えるとスパムメールでない確率もそこそこありそう」みたいなメールもあるかもしれない。逆も然り。だから、ある未知のメールを入力したときのモデルの出力が 0.5 だったとしても、それは「訓練データ中の非スパムメールたちとスパムメールたちの分離境界上にあたる」って意味でしかなくて「そのメールは 50% の確率でスパムメールである」ではないかもしれない。分離境界に近い非スパムメールが本当は胡散臭いものだったかもしれないし。モデルの出力が 0.99 だったとしても「訓練データ中のスパムメールに近いが非スパムメールには近くない」って意味でしかなくて「かなり確実にスパムメールである」ということもないかもしれない。その未知メールに近い訓練データ中のメールはスパムだけど非スパムでもありうるようなものだったかもしれない。だからスパムメールフィルタにかけるのは「自信過剰」かもしれない。

であれば、厳密な正解ラベルを付ければいいのでしょうか。「このメールは60%の確率でスパムメールで、40%の確率で非スパムメールである」というような。この正解分布との交差エントロピーを最小化するようモデルを訓練すればよいはずです。

そういう正解ラベルを付けられるならいいと思うんだけど、付けられるかな？

む…確かにイントロの2段落目に、私たちは通常「正しい不確かさ」を知り得ないとありますね。なので、ニューラルネットの応用場面で用いられる2つの評価指標に目を付けたといっています？

1つ目はキャリブレーション…モデルの予測分布と、実際にそれを長期にわたって稼働させたときの頻度分布のずれを測る指標ということでしょうか。モデルがよくキャリブレーションされているかどうかは proper scoring rules なるもので計測されるようです。「モデルの予測は正確でもキャリブレーションされていない場合もあるし、逆も然り」とありますが…？参考文献は割に古いんですね。

http://fitelson.org/seminar/dawid.pdf

2つ目は「ネットワークが、『ネットワーク自身が何を知っているか』を知っているかを測る」？「例えばある訓練済みのネットワークを訓練データからかけ離れたデータでテストしたら、ネットワークの予測は不確かであるべきだ」と…いっていることはわかる気はします。本当にネットワークが知らないはずのデータを入力しても自信満々に予測するなら「そのネットワークは自信過剰なのではないか」となりそうです。

誤って自信満々に予測してしまうのを防ぐことや、データの様相が変わったときにも正しい不確かさで予測することは、天気予報や医療診断など多くの実用分野で重要だとありますね。それはそうでしょう。

モデルの正確さとキャリブレーションの話は、「予測分布の最頻値による予測の正解率はよいが、予測分布としてはフィットしていない」「予測分布はよくフィットしているが、最頻値による予測の正解率はよくない」ということなのかな。

なるほど。次の段落で、ニューラルネットで不確かさを扱おうとする方法として主流なのはベイズ的なネットワークの重みの分布の更新とありますが、これで先の正解ラベルが厳密でない問題って解決します？

厳密な正解ラベルが付けられないという点は解消されないよ。解消されたのは「訓練データの正解ラベルを目指すべき真の分布とする」という考え方だろう。

はあ。続きをみると、しかし厳密なベイジアンニューラルネットは取り扱うのが大変なので、近似的なアプローチがよく用いられるということなんですね。ラプラス近似や MCMC、変分ベイズ法、仮定密度フィルタリング（assumed density filtering）、期待値伝搬法（expectation propagation）、各種の確率的勾配MCMCなどが挙げられています。そしてベイジアンニューラルネットの予測の不確かさは、その計算手段の制約に起因する近似の度合いや、事前分布に依存すると。まあそれでなんか結局ベイジアンニューラルネットは実装も大変だし計算も遅いのでもっと従来のニューラルネットを改変せずに予測の不確かさを取り扱いたいといっていますね。

そんなに近似解法挙げておいて！？

それで近年、Gal and Ghahramani という方が予測の不確かさを推定するために評価時にモンテカルロドロップアウト（MC-dropout）する手法を提案したそうです。

Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning

Gal and Ghahramani さんの提案内容は追えていないのですが、dropout はある種モデルのアンサンブルととらえられ、本論文でも予測の不確かさを推定するのにモデルのアンサンブルを利用するようですね。その次の段落は何をいいたいのでしょう…どうも、モデルのアンサンブルと Bayesian model averaging（BMA）は似て非なるものだといいたいようですね。BMA は考え方としてはソフトに（重み付き平均で）1つのモデルを選択しようとするものだが、アンサンブルはモデルを組み合わせようとするものであると。BMA というものをよく知らないのですが、色々な異なるモデルを事後確率で重み付けして足し合わせて1つのモデルとするものであるようですが、確かに対してアンサンブルというのは同じモデルを別々に抽出したデータセットで学習して組み合わせるといったものと思うので、違うようにみえます。しかしなぜここで急に BMA を目の敵にしたのかがよくわかりませんが…。

次の段落にこの論文の要点がまとめられているのかな。つまり、proper scoring rule を利用して分布を予測するニューラルネットを学習する手法、および予測の不確かさの推定のよさを評価するタスクを提案するみたいだね。

イントロの最後の段落は、ディープアンサンブルや敵対的学習の、不確かさの推定への有用性について調べ、かつ SOTA な近似ベイジアンニューラルネットと比較検証したのは本論文が初めてだとかそんな感じですかね。

（次回があれば）つづく

2019-06-08

雑記

おかしい点があったらご指摘いただけますと幸いです。

行列 $X \in \mathbb{R}^{n \times n}$ を、行列式 $|X| \in \mathbb{R}$ に移す写像 $F: \mathbb{R}^{n \times n} \to \mathbb{R}$ を行列のある成分 $x_{i,j}$ について偏微分したいとします。これは $|X|$ を $j$ 列目で余因子展開するとわかります。 $c_{i,j}$ は $X$ の $(i,j)$ -余因子とします。

　 $|X|=\displaystyle \sum_{i'=1}^{n} c_{i',j}x_{i',j}$ 　　∴　 $\displaystyle \frac{\partial |X|}{\partial x_{i,j}} = c_{i,j}$

なのでこれを横に並べれば $F$ の $X$ におけるヤコビ行列になります。行列変数をとる関数のヤコビ行列の定義は Magnus and Neudecker に倣います。つまり、この $F$ のヤコビ行列 $J$ は $1$ 行 $nn$ 列になり、具体的に $X$ の余因子行列を $C$ として $J = ({\rm vec}C )^{\top}$ です。ただこれは $X$ においてヤコビ行列 $J$ が存在するといっているだけで、 $X$ において全微分可能であるとはいっていないです。そこが気になると思います。全微分可能であることの示し方は色々あると思いますが、そもそも最初から全微分が出せたらそれに越したことはない気がします。なので考えてみます。仮に最後の列で余因子展開していきたいと思います。

　 $d|X|=d \displaystyle \left( \sum_{i=1}^{n} c_{i,n}x_{i,n}\right)$
　 $\qquad \; = \displaystyle \sum_{i=1}^{n} d \left( c_{i,n}x_{i,n} \right)$ 　∵ $d(f + g) = df + dg$
　 $\qquad \; = \displaystyle \sum_{i=1}^{n} \Bigl( ( d c_{i,n} ) x_{i,n} + c_{i,n} d x_{i,n} \Bigr)$ 　∵ $d(fg) = (df)g + fdg$
　 $\qquad \; = \displaystyle \sum_{i=1}^{n} \Bigl( (-1)^{i + n} x_{i,n} d |X_{i,n}| + c_{i,n} d x_{i,n} \Bigr)$ 　 $|X_{i,n}|$ は $X$ の $(i,j)$ -小行列式
　 $\qquad \; = \displaystyle \sum_{i=1}^{n} \Bigl( (-1)^{i + n} x_{i,n} \sum_{i'=1, i' \neq i}^{n} d (c_{i,n, i', n-1} x_{i', n-1}) + c_{i,n} d x_{i,n} \Bigr)$
　 $\qquad \; = \displaystyle \sum_{i=1}^{n} \Bigl( (-1)^{i + n} x_{i,n} \sum_{i'=1, i' \neq i}^{n} (x_{i', n-1} d c_{i,n, i', n-1} + c_{i,n, i', n-1} dx_{i', n-1}) + c_{i,n} d x_{i,n} \Bigr)$

ここで $c_{i,n, i', n-1}$ はこの記事の中でだけ用いられる見づらい記法で、 $X$ から $i$ 行目と $n$ 列目を消した行列の $(i', n-1)$ -余因子、但し、行と列のインデックスは元の行列におけるインデックスをずっとつかう、という意味です。元の行列におけるインデックスをつかうので、以下のような場合分けが生じることに注意します。

　 $c_{i,n, i', n-1} = \begin{cases} (-1)^{i' + n - 1}|X_{i,n, i', n-1}| & (i' < i) \\ (-1)^{i' - 1 + n - 1}|X_{i,n, i', n-1}| & (i' > i) \end{cases}$

ここで $|X_{i,n, i', n-1}|$ もこの記事の記法で、 $X$ から $i$ 行目と $n$ 列目と $i'$ 行目と $n-1$ 列目を消した行列の行列式です。一般の $n$ だとわかりづらいので、 $n = 4$ として上の微分がどうなるか考えてみます。

　 $d|X|= \displaystyle \sum_{i=1}^{4} \Bigl( (-1)^{i + 4} x_{i,4} \sum_{i'=1, i' \neq i}^{4} (x_{i', 3} d c_{i,4, i', 3} + c_{i,4, i', 3} dx_{i', 3}) + c_{i,4} d x_{i,4} \Bigr)$
　 $\qquad \; = \displaystyle \sum_{i=1}^{4} (-1)^{i + 4} x_{i,4} \sum_{i'=1, i' \neq i}^{4} (x_{i', 3} d c_{i,4, i', 3} + c_{i,4, i', 3} dx_{i', 3}) + \sum_{i=1}^{4} c_{i,4} d x_{i,4}$
　 $\qquad \; = \displaystyle (-1)^{1 + 4} x_{1, 4} (x_{2, 3} d c_{1, 4, 2, 3} + c_{1, 4, 2, 3} dx_{2, 3} + x_{3, 3} d c_{1, 4, 3, 3} + c_{1, 4, 3, 3} dx_{3, 3} + x_{4, 3} d c_{1, 4, 4, 3} + c_{1, 4, 4, 3} dx_{4, 3})$
　 $\qquad \; \; + \displaystyle (-1)^{2 + 4} x_{2, 4} (x_{1, 3} d c_{2, 4, 1, 3} + c_{2, 4, 1, 3} dx_{1, 3} + x_{3, 3} d c_{2, 4, 3, 3} + c_{2, 4, 3, 3} dx_{3, 3} + x_{4, 3} d c_{2, 4, 4, 3} + c_{2, 4, 4, 3} dx_{4, 3})$
　 $\qquad \; \; + \displaystyle (-1)^{3 + 4} x_{3, 4} (x_{1, 3} d c_{3, 4, 1, 3} + c_{3, 4, 1, 3} dx_{1, 3} + x_{2, 3} d c_{3, 4, 2, 3} + c_{3, 4, 2, 3} dx_{2, 3} + x_{4, 3} d c_{3, 4, 4, 3} + c_{3, 4, 4, 3} dx_{4, 3})$
　 $\qquad \; \; + \displaystyle (-1)^{4 + 4} x_{4, 4} (x_{1, 3} d c_{4, 4, 1, 3} + c_{4, 4, 1, 3} dx_{1, 3} + x_{2, 3} d c_{4, 4, 2, 3} + c_{4, 4, 2, 3} dx_{2, 3} + x_{3, 3} d c_{4, 4, 3, 3} + c_{4, 4, 3, 3} dx_{3, 3})$
　 $\qquad \; \; + \displaystyle \sum_{i=1}^{4} c_{i,4} d x_{i,4}$

上式で $dx_{1,3}$ の係数を集めてくるとこうなります。 $x_{2,4}$ は元の行列では2行目の4列目ですが、元の行列から1行目と3列目を削除した行列では1行目の3列目であることなどに注意します。

　 $x_{2,4} c_{2, 4, 1, 3} - x_{3,4} c_{3, 4, 1, 3} + x_{4,4} c_{4, 4, 1, 3} = x_{2,4} |X_{2, 4, 1, 3}| - x_{3,4} |X_{3, 4, 1, 3}| + x_{4,4} |X_{4, 4, 1, 3}| = |X_{1,3}| = c_{1,3}$

$dx_{2,3} , \, dx_{3,3}, \, dx_{4,3}$ の係数もかき集めてくると以下のようになります。上の場合分けに注意します。

　 $- x_{1,4} c_{1, 4, 2, 3} - x_{3,4} c_{3, 4, 2, 3} + x_{4,4} c_{4, 4, 2, 3} = - x_{1,4} |X_{1, 4, 2, 3}| + x_{3,4} |X_{3, 4, 2, 3}| - x_{4,4} |X_{4, 4, 2, 3}| = - |X_{2,3}| = c_{2,3}$
　 $- x_{1,4} c_{1, 4, 3, 3} + x_{2,4} c_{2, 4, 3, 3} + x_{4,4} c_{4, 4, 3, 3} = x_{1,4} |X_{1, 4, 3, 3}| - x_{3,4} |X_{2, 4, 3, 3}| + x_{4,4} |X_{4, 4, 3, 3}| = |X_{3,3}| = c_{3,3}$
　 $- x_{1,4} c_{1, 4, 4, 3} + x_{2,4} c_{2, 4, 4, 3} - x_{4,4} c_{3, 4, 4, 3} = - x_{1,4} |X_{1, 4, 4, 3}| + x_{2,4} |X_{2, 4, 4, 3}| - x_{4,4} |X_{3, 4, 4, 3}| = - |X_{4,3}| = c_{4,3}$

そうなると、こうなります。

　 $d|X|= \displaystyle (-1)^{1 + 4} x_{1, 4} (x_{2, 3} d c_{1, 4, 2, 3} + x_{3, 3} d c_{1, 4, 3, 3} + x_{4, 3} d c_{1, 4, 4, 3} )$
　 $\qquad \; \; + \displaystyle (-1)^{2 + 4} x_{2, 4} (x_{1, 3} d c_{2, 4, 1, 3} + x_{3, 3} d c_{2, 4, 3, 3} + x_{4, 3} d c_{2, 4, 4, 3} )$
　 $\qquad \; \; + \displaystyle (-1)^{3 + 4} x_{3, 4} (x_{1, 3} d c_{3, 4, 1, 3} + x_{2, 3} d c_{3, 4, 2, 3} + x_{4, 3} d c_{3, 4, 4, 3} )$
　 $\qquad \; \; + \displaystyle (-1)^{4 + 4} x_{4, 4} (x_{1, 3} d c_{4, 4, 1, 3} + x_{2, 3} d c_{4, 4, 2, 3} + x_{3, 3} d c_{4, 4, 3, 3} )$
　 $\qquad \; \; + \displaystyle \sum_{i=1}^{4} c_{i,3} d x_{i,3} + \sum_{i=1}^{4} c_{i,4} d x_{i,4}$

ゴールは $d|X|= \displaystyle \sum_{i=1}^{4} c_{i,1} d x_{i,1} + \sum_{i=1}^{4} c_{i,2} d x_{i,2} + \sum_{i=1}^{4} c_{i,3} d x_{i,3} + \sum_{i=1}^{4} c_{i,4} d x_{i,4}$ なので少し近づきました。それで、ここから $dc_{2,4,1,3} = d|X_{2,4,1,3}|$ を余因子展開するとさらに話を進められますが、 $X_{2,4,1,3}$ はもう $2$ 行 $2$ 列なので、これの余因子は行列式というか成分そのものです。上の式の中で $dx_{1,2}$ が出てくる項が6つあるので、 $3 \times 3$ 行列の行列式のたすき掛けををくくり出す未来しかみえないです。一般の $n \times n$ 行列の行列式の微分をこの手順で出そうと思うとこんな流れになる気がします（日本語は雰囲気です）。

余因子展開より、ただちに $n$ 列目の微分の係数が求まる。
余因子の余因子展開より、列目の微分の係数が求まる。
- 一旦 $(n-2) \times (n-2)$ サイズの行列式まで砕いてから、 $(n-1) \times (n-1)$ サイズの余因子に貼り合わせる。
余因子の余因子の余因子展開より、列目の微分の係数が求まる。
- 一旦 $(n-3) \times (n-3)$ サイズの行列式まで砕いてから、 $(n-2) \times (n-2)$ サイズの行列式に貼り合わせ、さらに $(n-1) \times (n-1)$ サイズの余因子に貼り合わせる。
以下繰り返し。

なんかもう大変なので数学的に帰納した方がいいと思います。 $d|X|= \displaystyle \sum_{i=1}^{n} \sum_{j=1}^{n} c_{i,j} d x_{i,j}$ が成り立つとすると、

　 $d|X|=d \displaystyle \left( \sum_{i=1}^{n+1} c_{i,n + 1}x_{i,n + 1}\right)$
　 $\qquad \; = \displaystyle \sum_{i=1}^{n + 1} \Bigl( (-1)^{i + n + 1} x_{i,n + 1} d |X_{i,n + 1}| + c_{i,n + 1} d x_{i,n + 1} \Bigr)$
　 $\qquad \; = \displaystyle \sum_{i=1}^{n + 1} \Bigl( (-1)^{i + n + 1} x_{i,n + 1} \displaystyle \sum_{i'=1}^{n} \sum_{j=1}^{n} c_{i, n+1, i',j} d x_{i',j} + c_{i,n + 1} d x_{i,n + 1} \Bigr)$

これについて、それぞれの $j$ について上の要領で余因子の貼り合わせをすれば $n + 1$ でも成り立つ、がいえるはずと思います。ここからそれをかくのは面倒なのでやめます。

2019-05-28

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

本読み機械学習

ベイズ統計の理論と方法

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

書籍サポートページ

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

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

なんで！？

勉強会で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$ である。