情報幾何学を嗜む～Bregmanダイバージェンスとその双対～

最近、情報幾何学の勉強をしている。情報幾何学は日本の甘利先生という方が切り開いてきた分野で、主には確率分布のパラメータが成す空間をリーマン多様体と捉えることで、確率分布族に対して幾何学的な解釈を与えるものである。

情報幾何学は情報科学の一分野でありながら、微分幾何学の理解を要する難解なものである。はっきり言って、情報系の人間で可微分多様体やらリーマン計量やら接続やらを理解している人は一握りであろう。私も情報系、それも工学部の出身であるから、甘利先生の本を初めて手に取った修士2年のときは、あまりの難しさに一瞬で心が折れたのを覚えている。

しかし時は流れ、私も今ではわずかばかり数学の心が分かるようになってきた。そこで、いよいよこの難攻不落の要塞に攻めいってみようというわけである。

というわけで、本稿から始まるいくつかの記事の中で、情報幾何学における主要なトピックについて私が理解したところを書き連ねてみようと思う。本稿ではその第一歩として、Bregmanダイバージェンスとその双対ダイバージェンスについて考えてみる。

ダイバージェンス

情報幾何学を語る上でダイバージェンスの存在は外せない。ダイバージェンスの定義を[1]から引用する*1 *2。

ダイバージェンス

次の3条件を満たす2点関数 $D[P : Q]$ をダイバージェンスと呼ぶ.
1) $D[P : Q] \ge 0$ .
2) $P = Q$ のとき, このときに限り, $D[P : Q] = 0$ .
3) $P$ 点と $Q$ 点が近いとし, それぞれの座標を, ${\boldsymbol \xi},\ {\boldsymbol \xi} + d{\boldsymbol \xi}$ とする. このとき, $D[{\boldsymbol \xi} : {\boldsymbol \xi} + d{\boldsymbol \xi}]$ をテイラー展開すると,
$\displaystyle{ D[{\boldsymbol \xi} : {\boldsymbol \xi} + d{\boldsymbol \xi}] = \frac{1}{2} \sum g_{ij}({\boldsymbol \xi}) d\xi_i d\xi_j }$
と2次の項が最初に出るが, 行列
$\displaystyle{ G({\boldsymbol \xi}) = (g_{ij}({\boldsymbol \xi})) }$
は正定値対称である.

ただし、 ${\boldsymbol \xi}$ は有限次元ベクトルである。

ダイバージェンスは距離の公理を満たしていない。すなわち、一般には $D[P : Q] = D[Q : P]$ とならない。この醜い非対称性が後に華麗な蝶へと変貌を遂げるのであるが、それは双対ダイバージェンスのところで説明する。

Bregmanダイバージェンス

ダイバージェンスの中でも特に重要なものの1つにBregmanダイバージェンスがある。これは滑らかな狭義凸関数 $\psi({\boldsymbol \xi})$ *3を用いて以下のように定義される[1]。

まず、点 ${\boldsymbol \xi}'$ における接超平面の方程式は以下のようになる。

$\displaystyle{ z = \psi({\boldsymbol \xi}') + \nabla \psi({\boldsymbol \xi}') ({\boldsymbol \xi} - {\boldsymbol \xi}') }$

点 ${\boldsymbol \xi}$ において、この接超平面と元の関数 $\psi({\boldsymbol \xi})$ の差は以下のようになる。

$\displaystyle{ D[{\boldsymbol \xi} : {\boldsymbol \xi}'] = \psi({\boldsymbol \xi}) - \psi({\boldsymbol \xi}') - \nabla \psi({\boldsymbol \xi}') ({\boldsymbol \xi} - {\boldsymbol \xi}') }$

これを凸関数 $\psi$ から導かれる ${\boldsymbol \xi}$ から ${\boldsymbol \xi}'$ へのBregmanダイバージェンスと呼ぶ。

Bregmanダイバージェンスがダイバージェンスの定義を満たすことは自明ではないため、本来であれば証明すべきである。実際、ノートで計算して確かめることは出来たのだが、それをブログに書き起こす気力と時間がなくなってしまったため、ここでは割愛する。

参考までに計算の指針だけ述べておく。まず、 $D[ {\boldsymbol a} : {\boldsymbol \xi} ]$ について ${\boldsymbol \xi} = {\boldsymbol a}$ における多変数のTaylor展開を計算する。0次の項は $D[{\boldsymbol a} : {\boldsymbol a}] = 0$ である。1次の項も計算すると0になる。2次の項は計算すると $\psi$ のHesse行列に等しくなる。 $\psi$ は滑らかな凸関数と仮定しているため、これは正定値対称となる。

Legendre変換による双対空間

Bregmanダイバージェンスを定義するために凸関数が登場した。凸関数といえば皆さん何を思い浮かべるだろうか？いろいろあると思うが、凸関数にまつわる重要な概念としてLegendre変換が挙げられる。Legendre変換を行うことで、凸関数が定義された空間の双対空間、及び双対凸関数を得ることができる。

最終的には多変数の場合を考える必要があるが、まずは1変数の場合から考えてみよう。

1変数凸関数のLegendre変換

1変数の滑らかな凸関数 $\psi(x)$ を考える。滑らかな凸関数の導関数は異なる $x$ に対して必ず異なる値を取る。逆に適当な実数 $p$ を与えると、それを導関数の値とするような点 $x$ が一意に決まる。

すなわち、 $\psi'(x)$ の定義域を $S$ 、値域を $D$ とすると、 $\psi' : S \ni x \mapsto p \in D$ は全単射となる。 $D$ のことを双対空間と呼ぶ。

ここで、 $\psi(x)$ に以下のような変換を施すことで双対空間に対して新たな関数 $\psi^{*}(p)$ を定める事ができる。

$\displaystyle{ \psi^{*}(p) = \max_{x}(px - \psi(x)) }$

これをLegendre変換と呼ぶ。

右辺の $px - \psi(x)$ を最大にする $x$ について考えてみよう。最大値を与える $x$ においては、この式を $x$ で微分したものが0となる必要がある。すなわち、以下が成立する。

$\displaystyle{ \begin{eqnarray} \frac{d}{dx}(px - \psi(x)) &=& 0 \\ p - \psi'(x) &=& 0 \\ p &=& \psi'(x) \end{eqnarray} }$

すなわち、 $\psi'(x)$ の値が $p$ となるような $x$ において $px - \psi(x)$ は最大となる。これはつまり、 $D$ の元と一対一に対応する $S$ の元を選べば良いということを意味する。

詳細は後述するが、実は $\psi^{*}(p)$ も凸関数であり、これを双対凸関数と呼ぶ。そのため、 $\psi^{*}(p)$ に対して再度Legendre変換を施すことができるが、その結果は元の関数 $\psi(x)$ と一致する[2]。つまり、Legendre変換の逆変換はLegendre変換そのものである。これより、双対性というのはあくまで相対的な概念に過ぎないことが分かる。

双対凸関数が凸関数であることの証明

双対凸関数が凸関数であることは自明ではないので、以下で証明してみよう。 $\psi^{*}(p)$ の定義式において $x$ は $p$ の関数であると考えると、2階導関数は以下のようになる。

$\displaystyle{ \begin{eqnarray} \frac{\partial^2 \psi^{*}}{\partial p^2} &=& \frac{\partial^2}{\partial p^2} (px - \psi(x)) \\ &=& \frac{\partial}{\partial p} (x + px' - \psi'(x) x') \\ &=& 2x' - \psi''(x){x'}^2 + x''(p - \psi'(x)) \end{eqnarray} }$

$p = \psi'(x)$ を代入すると以下のようになる。

$\displaystyle{ \frac{\partial^2 \psi^{*}}{\partial p^2} = 2x' - \psi''(x){x'}^2 }$

$p = \psi'(x)$ の両辺をpで微分して整理すると $x' = \frac{1}{\psi''(x)}$ となる。これを代入すると以下のようになる。

$\displaystyle{ \frac{\partial^2 \psi^{*}}{\partial p^2} = \frac{1}{\psi''(x)} }$

2階導関数が瞬間的にでも0になることがあるような関数は面倒なので除外して考えると、 $\psi''(x)$ は上に凸なら常に負、下に凸なら常に正となる。よって $\psi^{*}{''}(p)$ の符号も一定となるため、 $\psi^{*}(p)$ は凸関数である。

多変数凸関数のLegendre変換

少々くどいかもしれないが、1変数のときと同じ議論を多変数についても行ってみよう。

2つ以上の変数を持つ滑らかな凸関数 $\psi({\boldsymbol \xi})$ を考える。滑らかな凸関数の勾配ベクトルは異なる ${\boldsymbol \xi}$ に対して必ず異なるベクトルとなる。逆に適当な実数値ベクトル ${\boldsymbol \xi}^{*}$ を与えると、それを勾配ベクトルとするような点 ${\boldsymbol \xi}$ が一意に決まる。

この対応関係により、定義域と $\psi({\boldsymbol \xi})$ の勾配ベクトルが取り得る値の間に一対一の対応関係が得られる。 ${\boldsymbol \xi}^{*}$ が成す空間のことを双対空間と呼ぶ。

すなわち、 $\nabla \psi({\boldsymbol \xi})$ の定義域を $S$ 、値域を $D$ とすると、 $\nabla \psi : S \ni {\boldsymbol \xi} \mapsto {\boldsymbol \xi}^{*} \in D$ は全単射となる。 $D$ のことを双対空間と呼ぶ。

ここで、 $\psi({\boldsymbol \xi})$ に以下のような変換を施すことで双対空間に対して新たな関数 $\psi^{*}({\boldsymbol \xi}^{*})$ を定める事ができる。

$\displaystyle{ \psi^{*}({\boldsymbol \xi}^{*}) = \max_{{\boldsymbol \xi}}({\boldsymbol \xi} \cdot {\boldsymbol \xi}^{*} - \psi({\boldsymbol \xi})) }$

これをLegendre変換と呼ぶ。

右辺の ${\boldsymbol \xi} \cdot {\boldsymbol \xi}^{*} - \psi({\boldsymbol \xi})$ を最大にする ${\boldsymbol \xi}$ について考えてみよう。最大値を与える ${\boldsymbol \xi}$ においては、勾配ベクトルが零ベクトルとなる必要がある。すなわち、以下が成立する。

$\displaystyle{ \begin{eqnarray} \nabla ({\boldsymbol \xi} \cdot {\boldsymbol \xi}^{*} - \psi({\boldsymbol \xi})) &=& 0 \\ {\boldsymbol \xi}^{*} - \nabla \psi({\boldsymbol \xi}) &=& 0 \\ {\boldsymbol \xi}^{*} &=& \nabla \psi({\boldsymbol \xi}) \end{eqnarray} }$

すなわち、 $\nabla \psi({\boldsymbol \xi})$ の値が ${\boldsymbol \xi}^{*}$ となるような ${\boldsymbol \xi}$ において ${\boldsymbol \xi} \cdot {\boldsymbol \xi}^{*} - \psi({\boldsymbol \xi})$ は最大となる。これはつまり、 $D$ の元と一対一に対応する $S$ の元を選べば良いということを意味する。

証明は大変そうなので諦めるが、1変数の場合と同じく $\psi^{*}({\boldsymbol \xi}^{*})$ も凸関数であり、これを双対凸関数と呼ぶ。そのため、 $\psi^{*}({\boldsymbol \xi}^{*})$ に対して再度Legendre変換を施すことができるが、その結果が元の関数 $\psi({\boldsymbol \xi})$ と一致するというのも1変数の場合と同様である。

双対ダイバージェンス

双対凸関数は凸関数なので、これを用いると双対空間にもBregmanダイバージェンスを定義できる。

$\displaystyle{ D^{*}[{\boldsymbol \xi}^{*} : {\boldsymbol \xi}'^{*}] = \psi^{*}({\boldsymbol \xi}^{*}) - \psi^{*}({\boldsymbol \xi}'^{*}) - \nabla \psi^{*}({\boldsymbol \xi}'^{*}) ({\boldsymbol \xi}^{*} - {\boldsymbol \xi}'^{*}) }$

これを双対ダイバージェンスと呼ぶ。

元のダイバージェンスとの関係

双対ダイバージェンスと元のダイバージェンスとの間には重要な関係がある。以下でそれを導いてみよう。

${\boldsymbol \xi}, {\boldsymbol \xi}'$ について、双対空間において対応する点がそれぞれ ${\boldsymbol \xi}^{*}, {\boldsymbol \xi}'^{*}$ であるとする。このとき以下の式が成り立つ。

$\displaystyle{ \begin{eqnarray} \psi^{*}({\boldsymbol \xi}^{*}) &=& {\boldsymbol \xi} \cdot {\boldsymbol \xi}^{*} - \psi({\boldsymbol \xi}) \\ \psi^{*}({\boldsymbol \xi}'^{*}) &=& {\boldsymbol \xi}' \cdot {\boldsymbol \xi}'^{*} - \psi({\boldsymbol \xi}') \\ \nabla \psi^{*}({\boldsymbol \xi}'^{*}) &=& {\boldsymbol \xi}' \end{eqnarray} }$

これらを双対ダイバージェンスの式に代入すると以下のようになる。

$\displaystyle{ \begin{eqnarray} D^{*}[{\boldsymbol \xi}^{*} : {\boldsymbol \xi}'^{*}] &=& ({\boldsymbol \xi} \cdot {\boldsymbol \xi}^{*} - \psi({\boldsymbol \xi})) - ({\boldsymbol \xi}' \cdot {\boldsymbol \xi}'^{*} - \psi({\boldsymbol \xi}')) - {\boldsymbol \xi}' ({\boldsymbol \xi}^{*} - {\boldsymbol \xi}'^{*}) \\ &=& \psi({\boldsymbol \xi}') - \psi({\boldsymbol \xi}) - {\boldsymbol \xi}^{*}({\boldsymbol \xi}' - {\boldsymbol \xi}) \end{eqnarray} }$

これに ${\boldsymbol \xi}^{*} = \nabla \psi({\boldsymbol \xi})$ を代入すると以下のようになる。

$\displaystyle{ \begin{eqnarray} && \psi({\boldsymbol \xi}') - \psi({\boldsymbol \xi}) - \nabla \psi({\boldsymbol \xi}) ({\boldsymbol \xi}' - {\boldsymbol \xi}) \\ &=& D[{\boldsymbol \xi}' : {\boldsymbol \xi}] \end{eqnarray} }$

結局、以下の式が得られた。

$\displaystyle{ D^{*}[{\boldsymbol \xi}^{*} : {\boldsymbol \xi}'^{*}] = D[{\boldsymbol \xi}' : {\boldsymbol \xi}] }$

ダイバージェンスの定義を説明した際、ダイバージェンスは対称性を満たさないということを述べた。しかし、上式が示す通りBregmanダイバージェンスについては2つの引数を入れ替えたものは双対ダイバージェンスに一致するのである。元の空間だけでは対称性がないように見えるが、双対空間まで広げて考えるとこのように美しい対称性が現れるというのは非常に面白い。

ナブラを使わない表現方法

Bregmanダイバージェンスの定義式にはナブラ ( $\nabla$ ) が含まれており少々複雑である。実はこれはちょっとした式変形で回避できる。

これまでの議論が追えていれば簡単なので、以下に式変形だけ示す。

$\displaystyle{ \begin{eqnarray} D[{\boldsymbol \xi} : {\boldsymbol \xi}'] &=& \psi({\boldsymbol \xi}) - \psi({\boldsymbol \xi}') - \nabla \psi({\boldsymbol \xi}') ({\boldsymbol \xi} - {\boldsymbol \xi}') \\ &=& \psi({\boldsymbol \xi}) - \psi({\boldsymbol \xi}') - {\boldsymbol \xi}'^{*} ({\boldsymbol \xi} - {\boldsymbol \xi}') \\ &=& \psi({\boldsymbol \xi}) + ({\boldsymbol \xi}' \cdot {\boldsymbol \xi}'^{*} - \psi({\boldsymbol \xi}')) - {\boldsymbol \xi}'^{*} \cdot {\boldsymbol \xi} \\ &=& \psi({\boldsymbol \xi}) + \psi^{*}({\boldsymbol \xi}'^{*}) - {\boldsymbol \xi}'^{*} \cdot {\boldsymbol \xi} \end{eqnarray} }$