雑記: 1の分割の話

お気付きの点がありましたらご指摘いただけますと幸いです。全体的に参考文献 3. がないと(あっても)意味がわかりません。
参考文献

  1. 1の分割 - Wikipedia
  2. パラコンパクト空間 - Wikipedia
  3. 多様体の基礎 (基礎数学) | 松本 幸夫 |本 | 通販 | Amazon

※ キャラクターは架空のものです。
f:id:cookie-box:20190101155733p:plain:w60

「1の分割」というものがあるらしいんですが…。

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

導入が雑すぎる…。

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

そういわれても…じゃあ真面目に説明しますね。


ベイズ統計の理論と方法の4章では、真の分布 q(x) と確率モデル p(x|w) の関係に(「相対的に有限な分散をもつ」ということ以外は)何も仮定がない場合を扱うんですが、平均誤差関数を標準形にするために、パラメータを適当な多様体上の局所座標に変換してしまうみたいなんです。こうして得た「パラメータ改」が [0, 1]^d の有限和でかけるものとしてよいとするのに、「1の分割」なるものが存在するという定理を利用するようなんですが(厳密には「1の分割」そのものではなく同様の手続きということなんですが)…。
…という導入であればモチベーションがわかりやすいでしょうか?

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

わかりやすくはない…。

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

どうしろと…。

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

ともかく、定理の主張はつかめたの?

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

はい。調べたのですが、「1の分割」というのはある位相空間に対して指定の条件を満たす関数族(関数の集合)のことのようですね。

定義.1の分割
\mathcal{M}位相空間とする.\{\varphi_\alpha(p)\}_{\alpha \in A}\varphi_\alpha: \mathcal{M} \to [0, 1] であるような連続関数の集合とする.\{\varphi_\alpha(p)\}_{\alpha \in A} が任意の  p \in \mathcal{M} について以下の2つの条件を満たすとき,\{\varphi_\alpha(p)\}_{\alpha \in A}\mathcal{M} の1の分割という.
  1. p を元として含むある開集合 V が存在して,\{\varphi_\alpha(p)\}_{\alpha \in A} から任意の p \in V\varphi_\alpha(p)=0 になる元を除くと,有限集合になる( \{\varphi_\alpha(p)\}_{\alpha \in A} のうち V 内のどこかで 0 より大きい値をとるようなものは有限個である).
  2.  \sum_{\alpha \in A} \varphi_\alpha(p) = 1 である.
特に,\mathcal{M}開被覆  \{U_\alpha\}_{\alpha \in A} に対して,\varphi_\alpha(p) = 0, \, p \notin U_\alpha であるような1の分割 \{\varphi_\alpha(p)\}_{\alpha \in A}開被覆  \{U_\alpha\}_{\alpha \in A} に従属する1の分割という.
関数族の元は無限にあっても構わないようですが、位相空間内の各点の周りだけに注目したときは有限個を除いてゼロでなければならないようですね。また、位相空間の任意の点で関数族の値の和は1でなければなりません…関数族が1を分け合うことから「1の分割」と名付けられたのでしょうか。また、位相空間開被覆―開集合族であって、和集合がその位相空間を覆いつくすものですね―及び開被覆と同じ添え字をもつ1の分割があるとき、1の分割の各元が同じ添え字の開集合の外では常にゼロであるならば、その1の分割はその開被覆に従属するというようです。それで、ベイズ本の文脈では、開被覆の方が先に決まっていて、それに従属する1の分割がほしいはずなんです。しかし、一般の位相空間では任意の開被覆に1の分割が存在するわけではありません。調べたところによると、「ハウスドルフ性」をもつ位相空間が「パラコンパクト性」をもつとき、またそのときに限り、その位相空間は任意の開被覆に従属な1の分割をもつそうです。
定理.1の分割の存在
\mathcal{M}ハウスドルフ空間とする.\mathcal{M} がパラコンパクトであることと,\mathcal{M} の任意の開被覆が従属な1の分割をもつことは同値である.
このことはウィキペディアパラコンパクト空間に証明がのっているんですが、ちょっと日本語と英語が混ざったルー大柴状態で読みづらく…。

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

いや、いうほど混ざってもないしルー大柴は「局所有限開被覆」とかいわないと思う…。そもそも英語版を参照すればいいんじゃ…でも、この証明は別の補題を利用していて追いかけづらいのかな。難しかったらいきなりパラコンパクトハウスドルフ空間における証明を目指すんじゃなくて、証明しやすい場合で証明すればいいんじゃない? 以下の本の186ページに、まずコンパクトな微分可能多様体における「1の"2"分割」の存在の証明があるよ。その後190ページにσコンパクトな微分可能多様体の任意の開被覆の細分に対する1の分割の存在の証明、198ページにはσコンパクトな微分可能多様体の任意の有限開被覆に従属する1の分割の存在の証明があるね。


多様体の基礎 (基礎数学)

多様体の基礎 (基礎数学)

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

え、えっと、「パラコンパクト性」の他に「コンパクト性」「σコンパクト性」というのもあるのですか? ご兄弟がいらっしゃったのですね…。あと、「1の分割」は位相空間に対する概念ではなかったのですか? 位相空間ではなくて多様体なんですか?

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

いや、多様体ってハウスドルフ性(任意の異なる2つの元に対してそれぞれを元として含む共通部分のない開集合がとれるという性質)と地図帳をもってる位相空間のことだからね(注: 単に多様体といったときの定義は文献によります)。

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

私は地理選択ではないので地図帳はもっていませんね。

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

位相空間開被覆  \{U_\alpha\}_{\alpha \in A} があって、それぞれの  U_\alpha から \mathbb{R}^m の開集合への同相写像  \varphi_\alpha があれば、 \{ (U_\alpha, \varphi_\alpha) \}_{\alpha \in A} は地図帳(アトラス; m 次元座標近傍系)だね。この地図帳があれば、位相空間の任意の点に対してどこかの \alpha ページに m 次元ベクトルの住所がかいてある。

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

なるほど…でも、その点で開被覆  U_{\alpha_0} , \, U_{\alpha_1} が重なっているような点だと、 \alpha_0 ページと \alpha_1 ページに異なる住所がかいてあるようなことになりませんか?

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

 \alpha_0 ページで住所が m 次元ベクトル x_0 であるような点は、 \alpha_1 ページでの住所に直すと  \varphi_{\alpha_1}  \circ \varphi_{\alpha_0}^{-1}(x_0) だね。もっとも、U_{\alpha_0}U_{\alpha_1} の共通部分に属する点については、ということだけどね。この写像  \varphi_{\alpha_1}  \circ \varphi_{\alpha_0}^{-1} を座標変換といって、任意の「重なりがあるページ」間の座標変換が  C^r 級なら、そんな地図帳をもっている多様体m 次元 C^r微分可能多様体C^r多様体)というよ。

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

あるページにおける住所表示から別のページにおける住所表示への変換が滑らかなら C^r多様体ということでしょうか。確かに、地図帳のあるページにあった公園が、別のページでは2つに引き裂かれていたら嫌かもしれないですね。そういうことがない地図帳ということですね。

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

まあこの「地図帳が C^r 級である」というのはこれを仮定しないと1の分割ができないわけじゃないはずなんだけど(実際、一般の1の分割の存在定理は多様体を仮定してなかった=地図帳を仮定してなかったしね)、仮定するのが証明しやすいんだと思う。あ、あと 186 ページの証明では地図帳が  C^r 級であることの他に、位相空間自体に「コンパクト性」も要るね。任意の開被覆が有限部分開被覆をもつ(開被覆の有限個の部分集合だけで位相空間を覆いつくせる)という性質だね。

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

「コンパクト性」ですか…よくわかりませんね。だから何といった感じなんですが。1の分割をするのになぜそんな性質が必要なんです?

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

位相空間をコンパクト集合で覆いたいからかな。コンパクト性がないとそれが保証されない。1の分割って各点で有限個の関数さんたちに1を分け合ってほしいんだよね。逆にいうと、ある点でどの関数さんも分け前をもらっていってくれなかったら(どの関数の値もゼロだったら)困るよね。だから、位相空間をコンパクト集合で覆って、関数さんたちに「担当するコンパクト集合内では必ず正の値をとってね」って指示したいんだよね。まあ詳しくはおいおいかな。


具体的に、186 ページにある1の分割の最初の一歩はこうだね。
定理.コンパクト微分可能多様体を覆う2つの開集合に従属する1の分割
\mathcal{M} をコンパクト  C^r多様体とし,開集合 U, V \subset \mathcal{M}U \cap V = \mathcal{M} を満たすものとする.このとき,以下の3つの条件を満たす \mathcal{M} 上の  C^r 級関数 f: \mathcal{M} \to \mathbb{R}g: \mathcal{M} \to \mathbb{R} が存在する.
  1.  0 \leqq f \leqq 1 0 \leqq g \leqq 1
  2.  {\rm supp}(f) \subset U {\rm supp}(g) \subset V
  3.  f + g \equiv 1

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

はあ…ん? 副部長、誤植がありますよ。{\rm supp} じゃなくて {\rm sup} です。

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

それは {\rm supp} で合ってるよ。 {\rm supp}(f) \equiv {\rm cl} \{q \in \mathcal{M} \, | \, f(q) \neq 0 \} で、日本語でいうとサポートとか台だね。関数の値がゼロでない点の集合の閉包のことだよ。てか {\rm sup} じゃ意味通んないでしょ。

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

なるほど。しかし、「このような関数たちが存在する」ということの証明はどうやるのでしょう? やり方が思い付きません…。

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

実際に構成できるんだよ。上の定理の証明の流れはこうだね。

  1.  \mathcal{M} のコンパクト部分集合 K, \, L であって  K \subset U, \, L \subset V かつ  K \cup L = \mathcal{M} となるものが存在する(これにコンパクト性が必要)。
  2.  \mathcal{M} の任意の点とその開近傍 p, \, U に対して、次のような  C^r 級関数 \varphi が存在する;U に包含されるある開近傍の閉包 {\rm cl} W 内では1をとり、 U \setminus {\rm cl} W では0以上1未満の値をとり、 \mathcal{M} \setminus U では0をとる(証明は、\varphi を実際につくることによる)。
  3. 1. の  K の各点  p に対して、p, \, U に 2. を適用すると  \varphi_p, \, W_p をとれる。また、K はコンパクトなので有限個の W_p で覆うことができる。この有限個に対応する  \varphi_p を足し上げたものを  h_K とする。1. の L に対しても同様に h_L を得る。f = h_K / (h_K + h_L), \, g = h_L / (h_K + h_L) が題意を満たす。

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

流れだけかかれても…。

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

証明かくのしんどいからね。

つづかない

雑記: KKT条件の話

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

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

注意(2019-07-16 追記)

※ キャラクターは架空のものです。
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 が修士論文でこの条件を主張していたのが見つかって、彼の名も冠してこの名前になったのかな?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

「より小さくなることはない」を言い換える。「  \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 に十分近いところでは」のようなイメージで理解できると思いますが、近似的でなくても成り立ちます。が、証明はここでは割愛します。

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

え、えっと?  \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)^\topfx^\ast におけるヤコビ行列そのもので、 \nabla f(x^\ast)^\top sf の起点 x^\ast における増分 s微分ですね…この微分が負になるような増分は存在しない、ということは…起点 x^\ast からどんな方向付きステップ s だけ進んでも、より小さくなることはない、ということですね。

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

だから、どんな 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}

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

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

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

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

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

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

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

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

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

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

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

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

だから、さっきと同様の議論により、 \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) に直交しないといけないからね。

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

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

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

だから、等式制約が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) = 0x^\ast が問題(P)の局所最適解だから等式制約を満たしているって当然の話だけど、普通これも合わせてかくね。

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

あ、今度は  \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つ目の条件式と同じ形になりますね!

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

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

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

え?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

《 注意 》ドーナツの例が文章で伝わらなかった方は、参考文献1. の 148 ページの例 9.2 が同じ趣旨だったのでこれをご参照ください。
だからもう、制約付き最適化の局所最適解の必要条件を考えるとき、こういうケースは除外しちゃう。

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

ええ…。

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

よく仮定されるのがこの中の 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 と同じだけど、それ以外はちょっとよくわかってないや。そもそもこれらの制約想定が不等式制約もある場合のものだけど。

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

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

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

例えば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 を小さくする向きが存在しない」点といえる。

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

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

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

それだとドーナツ重ね問題が発生するんだよね。ドーナツの内部が負のとき、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 も満たしちゃうからね。

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

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

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

それでもいいけど、もっと弱い仮定もあるよ。この中の 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つのドーナツの内部に向かうベクトルはないからね。

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

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

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

まず 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}

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

どちらも同じにみえるんですが…あ、よくみると、下の定理では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 は要らないんですか?

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

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

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

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

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

下の定理の場合は、もしこのような 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 を少しずらせばイコールがとれるんだよね。

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

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

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

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

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

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

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

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

補題.Farkas’ lemma
A \in \mathbb{R}^{m \times n}c \in \mathbb{R}^n に対して次の(1)または(2)が成り立つ.しかし同時に(1),(2)が成立することはない.
(1) \exists x \in \mathbb{R}^n, \; Ax \leqq \vec{0}, \; c^\top x < 0
(2) \exists y \in \mathbb{R}^m, \; A^\top y + c = \vec{0}, \; y \geqq 0

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

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

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

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

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

えっと、そのように cA を読み替えれば、(1)は確かに先ほどの定理を否定のようですね。先ほどの定理では存在しないといったものを存在するといっている。…否定じゃ駄目なんじゃないですか?

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

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

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

(2)の y\lambda^\ast とかき換えて、cA もかき換えると、こうですね。…これ、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番目の条件式も足りませんし。

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

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

力尽きた

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

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

ベイズ統計の理論と方法

ベイズ統計の理論と方法

書籍サポートページ
f:id:cookie-box:20190101155733p:plain:w60

前回(ノート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) は実質的にユニーク 

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

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

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

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) と名付けられていますね。「損失」やら「誤差」やら「平均」やら「汎化」やら色々な言葉が出てきて、何がなにやらといった感じですが…。

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

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

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

では自由エネルギーは何だったのかというと、確率モデルの下でのサンプルの選択情報量のような量ですが、逆温度にもより、逆温度が正の無限大の極限で確率モデルの負の対数尤度になるのでしたっけ。それで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) というものなんですね。\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) はそれをさらに真の分布で平均したり、真の分布の代わりに経験分布で平均したりしたものであるようですが。そしてこれらを \alphak微分して \alpha = 0 としたのが k 次キュムラントですか…我々はなぜ急にキュムラントなるものを突き付けられたのでしょう?

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

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

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

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

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

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

  • 最適なパラメータにおける平均対数損失。
  • 平均誤差の事後分布による期待値。
  • 対数尤度比の2乗の事後分布による期待値から対数尤度比の事後分布による期待値の2乗を引いたものの真の分布の期待値。
ここからさらに仮定をおいていくことで、ベイズ推測は「n \to + \infty で収束するのか」「どこに収束するのか」「どのように収束するのか」が議論できるようになるんじゃないのかな…わからないけど。

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

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

つづきは後で

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
※ キャラクターは架空のものです。解釈の誤りは筆者に帰属します。おかしな点がありましたらご指摘ください。
次回:まだ
f:id:cookie-box:20190101155733p:plain:w60

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 1つ目はキャリブレーション…モデルの予測分布と、実際にそれを長期にわたって稼働させたときの頻度分布のずれを測る指標ということでしょうか。モデルがよくキャリブレーションされているかどうかは proper scoring rules なるもので計測されるようです。「モデルの予測は正確でもキャリブレーションされていない場合もあるし、逆も然り」とありますが…? 参考文献は割に古いんですね。
  • 2つ目は「ネットワークが、『ネットワーク自身が何を知っているか』を知っているかを測る」? 「例えばある訓練済みのネットワークを訓練データからかけ離れたデータでテストしたら、ネットワークの予測は不確かであるべきだ」と…いっていることはわかる気はします。本当にネットワークが知らないはずのデータを入力しても自信満々に予測するなら「そのネットワークは自信過剰なのではないか」となりそうです。
誤って自信満々に予測してしまうのを防ぐことや、データの様相が変わったときにも正しい不確かさで予測することは、天気予報や医療診断など多くの実用分野で重要だとありますね。それはそうでしょう。

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

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

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

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

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

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

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

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

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

そんなに近似解法挙げておいて!?

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

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

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

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

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

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

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

(次回があれば)つづく

雑記

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


行列 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}
なのでこれを横に並べれば FX におけるヤコビ行列になります。行列変数をとる関数のヤコビ行列の定義は Magnus and Neudecker に倣います。つまり、この F のヤコビ行列 J1nn 列になり、具体的に 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} はもう 22 列なので、これの余因子は行列式というか成分そのものです。上の式の中で dx_{1,2} が出てくる項が6つあるので、3 \times 3 行列の行列式のたすき掛けををくくり出す未来しかみえないです。 一般の  n \times n 行列の行列式微分をこの手順で出そうと思うとこんな流れになる気がします(日本語は雰囲気です)。

  • 余因子展開より、ただちに n 列目の微分の係数が求まる。
  • 余因子の余因子展開より、n-1 列目の微分の係数が求まる。
    • 一旦 (n-2) \times (n-2) サイズの行列式まで砕いてから、 (n-1) \times (n-1) サイズの余因子に貼り合わせる。
  • 余因子の余因子の余因子展開より、n-2 列目の微分の係数が求まる。
    • 一旦 (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 でも成り立つ、がいえるはずと思います。ここからそれをかくのは面倒なのでやめます。