代数幾何学で遊ぼう ~Nullstellensatzの強形と弱形~

趣味で数学を勉強し始めてから幾星霜、ついにここまで来た。そう、代数幾何学である。ついにこの高みに手を伸ばすところまで辿り着いたのだ。

修士一年の頃から約8年、研究に役立てばと群論を学び始めたのがきっかけだったが*1、その道すがらで出会った代数幾何学、これだけはなんとしてもチャレンジしてみたいという気持ちがあった。

しかし、いざ学び始めてみると前評判以上の難しさである。すでに理解できていないポイントがいくつも出てきており、この辺りで腰を落ち着けて分からないことを1つずつ片付けていく必要がある。

そこで、本稿より続くいくつかの記事の中で、私が代数幾何学に対して抱いた疑問点を解消していこうと思う。本稿ではそのトップバッターとして、Hilbertの零点定理 (Nullstellensatz) の強形と弱形の関係性について調べる。

Hilbertの零点定理に関する疑問点

Hilbertの零点定理には強形と弱形と呼ばれる2つのバージョンがある。両者の間には一体どういう関係があるのだろうか?名前の感じからすると、弱形は強形より導かれそうな感じがする。しかし、両者は一見すると似ても似つかない形をしている。一体、どうやって片方から他方を導いてやれば良いのだろうか?

強形が先か弱形が先か

前述した疑問の答えを探る中で、Wikipediaに以下のような記載があるのを見つけた[2]。

Hilbert's Nullstellensatz states that (中略、ここで強形の説明).

An immediate corollary is the weak Nullstellensatz: (後略、ここで弱形の説明)

なるほど、弱形は強形から導かれる系というわけだ。これで前半の疑問は解消した…と思った矢先、さらに以下のような記事を見つけた[3]。

Typically the way that the strong Nullstellensatz is proved is by reduction to the so-called “weak Nullstellensatz” by means of the “Rabinowitsch trick”. (The “weak” here may be misleading, as the weak Nullstellensatz may be considered the core result and the strong Nullstellensatz a corollary.)

どっちやねん!結局どっちが主定理でどっちが系やねん!と思わず荒ぶってしまうような状況である。以下、私の理解を順に説明していく。

記号の定義

 k[X_1, X_2, \cdots , X_n]の部分集合 Tの共通零点の集合を Z(T)で表す。また、 k^nの部分集合 Yの全ての点において0となる多項式の集合は k[X_1, X_2, \cdots , X_n]イデアルとなるが、これを I(Y)と書く。

定理の主張

Hilbertの零点定理の主張を本[1]より引用する。

Hilbertの零点定理
 k代数的閉体とし,  {\bf a} k[X_1, X_2, \cdots , X_n]イデアルとする.  g \in k[X_1, X_2, \cdots , X_n] Z({\bf a})のすべての点で0になるならば g \in \sqrt{{\bf a}}である.
Hilbertの弱零点定理 (その1)
 k代数的閉体とする.  k上の n変数多項式環 k[X_1, X_2, \cdots , X_n]の極大イデアルは,  k^nの適当な元 (a_1, a_2, \cdots , a_n)によって,  (X_1 - a_1, X_2 - a_2, \cdots , X_n - a_n)で与えられる.

調べてみると、Hilbertの零点定理はいろいろなバリエーションがあるようだ。以下にWikipediaに記載されていた弱形の主張を示す[2]。

Hilbertの弱零点定理 (その2)
The ideal  I\subset k[X_{1},\ldots ,X_{n}] contains 1 if and only if the polynomials in  I do not have any common zeros in  K^n. It may also be formulated as follows: if  I is a proper ideal in  k[X_{1},\ldots ,X_{n}], then  V(I) cannot be empty, i.e. there exists a common zero for all the polynomials in the ideal in every algebraically closed extension of  k.

 V(I)は本[1]の記号で言えば Z(I)のことである。

Wikipediaでは kを体、 K kの拡大体かつ代数的閉体としており、本[1]とは記号の意味が違う。しかし、実際には k = Kでもよく、かつそのケースが一番強い主張になるため、初めから k = Kとして考えても問題にはならない。

強形から弱形を導く

Wikipediaには出来ると書いてあるのだから、きっと出来るのだろう。というわけで証明してみよう。

準備

まず、Hilbertの零点定理は以下のように言い換えられる[1][2]。

 \displaystyle{
I(Z({\bf a})) = \sqrt{{\bf a}}
}

簡単に説明しておくと、まず I(Z({\bf a})) \subset \sqrt{{\bf a}}はHilbertの零点定理の単なる言い換えに過ぎない。また、任意の f \in \sqrt{{\bf a}}について、イデアルの根基の定義より f^m \in {\bf a}を満たす自然数 mが存在する。 f f^mの零点集合は一致するので、 f Z({\bf a})の全ての点で0になる。よって f \in I(Z({\bf a}))である。 fは任意だから \sqrt{{\bf a}} \subset I(Z({\bf a}))となる。

弱形 (その2) の証明

こちらの方が簡単なので、こちらから証明する。証明は[6]を参考にした。

 k[X_1, X_2, \cdots , X_n]イデアル {\bf a}について、その代数的集合が空集合、すなわち Z({\bf a}) = \phiであるとする。Hilbertの零点定理 (の前述した言い換え) より以下の式が成り立つ。

 \displaystyle{
\begin{eqnarray}
\sqrt{{\bf a}} &=& I(Z({\bf a})) \\
&=& I(\phi) \\
&=& k[X_1, X_2, \cdots , X_n]
\end{eqnarray}
}

これより 1 \in \sqrt{{\bf a}}なので 1 \in {\bf a}となり、 {\bf a}
= k[X_1, X_2, \cdots , X_n]が成立する。

弱形 (その1) の証明

弱形 (その1) をただ証明するだけなら本[1]等にやり方が載っている。しかし、強形から弱形 (その1) を導く方法というのが意外と見つからない。仕方がないので自分で考えてみた。

 k^nの適当な点 (a_1, a_2, \cdots , a_n)によって (X_1 - a_1, X_2 - a_2, \cdots , X_n - a_n)と表される k[X_1, X_2, \cdots , X_n]イデアルが極大イデアルであることの証明は割愛する。詳しくは本[1][4]等を参照のこと。以下ではその逆を示す。

 {\bf m} k[X_1, X_2, \cdots , X_n]の極大イデアルとする。極大イデアルは真のイデアルであるから、弱形 (その2) より Z({\bf m}) \ne \phiである。

 I(Z({\bf m}))の任意の元 f Z({\bf m})の任意の点 (a_1, a_2, \cdots , a_n)について f \in (X_1 - a_1, X_2 - a_2, \cdots , X_n - a_n)となる。つまり、 I(Z({\bf m})) \subset (X_1 - a_1, X_2 - a_2, \cdots , X_n - a_n)である。これは意外と自明ではないので、念のため示しておく。

 f (X_1 - a_1)で割ると f = f_1(X_1, X_2, \cdots , X_n)(X_1 - a_1) + F_1(X_2, X_3, \cdots , X_n)と書ける。ここで F_1 (X_2 - a_2)で割ると F_1 = f_2(X_2, X_3, \cdots , X_n)(X_2 - a_2) + F_2(X_3, X_4, \cdots , X_n)と書ける。これを fの式に代入すると f = f_1(X_1, X_2, \cdots , X_n)(X_1 - a_1) + f_2(X_2, X_3, \cdots , X_n)(X_2 - a_2) + F_2(X_3, X_4, \cdots , X_n)となる。これを繰り返すと最終的に以下のようになる。

 \displaystyle{
f = f_1(X_1, X_2, \cdots , X_n)(X_1 - a_1) + f_2(X_2, X_3, \cdots , X_n)(X_2 - a_2) + \cdots + c_n(X_n - a_n) + c\ (c_n, c \in k)
}

 fは定義より点 (a_1, a_2, \cdots , a_n)において0になるので c = 0が言える。よって f \in (X_1 - a_1, X_2 - a_2, \cdots , X_n - a_n)となる。

 I(Z({\bf m}))の元は Z({\bf m})の全ての点で0になる必要があるので、以下の式が成り立つ。

 \displaystyle{
I(Z({\bf m})) \subset \bigcap_{(a_1, a_2, \cdots , a_n) \in Z({\bf m})}{(X_1 - a_1, X_2 - a_2, \cdots , X_n - a_n)}
}

Hilbertの零点定理 (の前述した言い換え) より上式の左辺は \sqrt{{\bf m}}に等しい。 \sqrt{{\bf m}}イデアルであり、 {\bf m} \subset \sqrt{{\bf m}}であるが、 {\bf m}は極大イデアルなので {\bf m} = \sqrt{{\bf m}}となる。つまり、以下の式が成り立つ。

 \displaystyle{
{\bf m} \subset \bigcap_{(a_1, a_2, \cdots , a_n) \in Z({\bf m})}{(X_1 - a_1, X_2 - a_2, \cdots , X_n - a_n)}
}

左辺は極大イデアルであり、かつ右辺で共通部分を取っている集合 (X_1 - a_1, X_2 - a_2, \cdots , X_n - a_n)もそれぞれ極大イデアルであるため、 {\bf m}は適当な点 (a_1, a_2, \cdots , a_n)について (X_1 - a_1, X_2 - a_2, \cdots , X_n - a_n)に一致する。これで弱形 (その1) が示せた。

弱形 (その1) と弱形 (その2) の関係

Hilbertの零点定理には2つの弱形があった。これらの間にはどういう関係があるのだろうか?どちらも弱形と呼ばれるからには、同値な命題であることが期待される。以下で調べてみよう。

その1からその2を導く

 k[X_1, X_2, \cdots , X_n]の真のイデアルは全ていずれかの極大イデアルに含まれる。弱形 (その1) より極大イデアル (X_1 - a_1, X_2 - a_2, \cdots , X_n - a_n)と表されるため、少なくとも点 (a_1, a_2, \cdots , a_n)では0となる。

その2からその1を導く

 k[X_1, X_2, \cdots , X_n]の極大イデアル {\bf m}について、弱形 (その1) より Z({\bf m}) \ne \phiである。 Z({\bf m})から1点 (a_1, a_2, \cdots , a_n)を選べば、 {\bf m}の全ての元はこの点において0となる。よって {\bf m} \subset (X_1 - a_1, X_2 - a_2, \cdots , X_n - a_n)となる。両辺とも極大イデアルなので、結局 {\bf m} = (X_1 - a_1, X_2 - a_2, \cdots , X_n - a_n)が言える。

弱形から強形を導く

先にも述べたが、どうやら弱形から強形を導くことも出来るらしい。これにはRabinowitsch trickなる技を使うようだ[5]。Wikipediaの記事を見てみると、そのまんま本[1]に書いてある強形の証明だった。Trickと呼ばれるだけあって (面倒だが) 初等的な式変形で証明出来るため、興味がある方はご覧頂くと良いだろう。

Rabinowitsch trickは厳密には弱形 (その1) から強形を導くためのものに見える。そのため、弱形 (その2) から直接強形を導くことは出来なさそうだ。ただし、先に述べた通り2つの弱形は同値なので、あまり気にする必要はない。

結局、強弱とは何なのか?

強形から弱形、弱形から強形をそれぞれ証明出来たのだから、両者は同値であると言える。それであればなぜ強とか弱とか名前が付いているのか疑問だが、そこまでは分からなかった。少なくとも見た目だけでも強形が弱形の一般化っぽく見えていればまだ納得できるが、両者の主張にはどうも統一感がない。まだ見ぬ同値なステートメントがあるのかも知れない。

まとめ

本稿ではHilbertの零点定理について調べた。この定理には強形、弱形と呼ばれるバリエーションが存在するが、名前に反してそれらは同値であることを明らかにした。

Hilbertの零点定理は以前より名前だけは聞いたことがあり、どんな定理か気になっていた。本稿の執筆を通してそこそこ理解できて嬉しい。

参考

[1]

共立講座21世紀の数学 (17) 代数幾何入門

共立講座21世紀の数学 (17) 代数幾何入門

[2] Hilbert's Nullstellensatz - Wikipedia
[3] Nullstellensatz in nLab
[4]
代数学2 環と体とガロア理論

代数学2 環と体とガロア理論

[5] Rabinowitsch trick - Wikipedia
[6] http://math.ucsd.edu/~doprea/resultants.pdf

*1:結局、群論は私の研究には使えなかった (というか使いこなせなかった) が、幸い修士の学位は得られた。

16進数から10進数への変換を概算で求める

私はソフトウェア開発という仕事柄、日常的に16進数を扱っているのだが、16進数を10進数に変換したくなることがよくある。これはWindowsの電卓機能で簡単に実現できるためどうということはないのだが、もしこの変換を暗算で高速に行えると良いと思うことがある。

しかし、10進数と16進数というのは相性がよくない。どちらも2のべき乗であればまだ何とかなったと思うのだが、人類が10進数などというわけのわからない表記を好んで使うものだから、誤差なく簡単に変換することは不可能と思われる。ここで言う「簡単に」というのは、変換したい16進数をマウスでコピーし、Windowsの電卓アプリを開き値をペーストするよりも手軽に、という意味であると定義しておく。

そこで本稿では概算によりこの16進数から10進数への変換を簡単に行える方法について説明する。また、概算によってどれくらいの誤差が生じ得るかについても調べる。

概算の方法

概算のステップは大きく以下の2つに分けて考える。

  1. 上位桁のシンプルな数への近似
  2. 桁上げ

1点目について、概算の仕方として以下の3つの方法を考える。

  1. ある桁以下の値を切り捨てる。
  2. ある桁の数を7捨8入する。
  3. ある桁の数を0, 8, 16のどれかに丸める。

上の方法ほど計算は簡単だが誤差が大きく、下の方法ほど計算は複雑だが誤差は小さくなる。

3つ目の方法について補足しておく。これは例えば0x12について、1桁目の数値が2だからこれは切り捨てて \mathrm{0x12} \simeq \mathrm{0x10}とするとか、0xa7であれば間をとって8に寄せて \mathrm{0xa7} \simeq \mathrm{0xa8}にするとか、そういう方法である。ただし、値がいくつであれば0, 8, 16のうちどれに丸めるかというのは選択の余地がある。

その後、0となった下位の桁の分だけ桁上げの計算を行う必要がある。例えば0x5000の場合、後ろに3つ0が並んでいるので、 5 \times 16^3を計算すると、10進数への概算による変換が完了する。ただし、この計算を愚直に実行すると暗算では厳しいため、これについても概算による単純化を試みる。

対象とする16進数の大きさ

実用上、1, 2, 4, 8byteの整数値を16進数として表現することが考えられる。8byteはさすがに大きすぎて暗算では厳しそうなので、2byteの16進整数を必須の対象とし、4byteを努力目標とする。

上位桁の近似

切り捨て

前述した3つの方法のうち、もし切り捨てで話が簡単になるならそれほど嬉しいことはない。まずは楽観的にこの方針について調べてみよう。

最悪ケースでの誤差

まず、上位から3桁目以降を切り捨てた場合の誤差について考えてみる。この場合、最も切り捨てによる誤差が大きくなるのは、残された上位2桁が最小で、切り捨てられる3桁目以降が最大になる時、つまり0x10ff...fである。これの3桁目以降を切り捨てた値は0x1000...0となる。この場合の誤差は以下のように計算できる。

 \displaystyle{
\frac{|\mathrm{0x1000 \cdots 0} - \mathrm{0x10ff \cdots f}|}{\mathrm{0x10ff \cdots f}} < \frac{|\mathrm{0x1000 \cdots 0} - \mathrm{0x1100 \cdots 0}|}{\mathrm{0x1000 \cdots 0}} = \frac{1}{16} = 0.0625
}

これより、3桁目以降を切り捨てた場合の誤差は約6%以下であり、この程度であれば無視してしまってもよいだろう。よって概算を考える上では、上位2桁だけを考えればよいと言える。これは大きな収穫だ。

次に、上位から2桁目以降を切り捨てた場合の誤差について考えてみる。この場合、先ほどと同様に考えて、最も切り捨てによる誤差が大きくなるのは0x1ff...fである。これの2桁目以降を切り捨てた値は0x100...0となる。この場合の誤差は以下のように計算できる。

 \displaystyle{
\frac{|\mathrm{0x100 \cdots 0} - \mathrm{0x1ff \cdots f}|}{\mathrm{0x1ff \cdots f}} < \frac{|\mathrm{0x100 \cdots 0} - \mathrm{0x200 \cdots 0}|}{\mathrm{0x1f0 \cdots 0}} = \frac{16}{31} \simeq 0.516
}

これより、2桁目以降を切り捨てた場合の誤差は約52%以下である。さすがに2桁目の値を無視するのは誤差が大きくなりすぎるようだ。

7捨8入

上位2桁をそのまま残す必要があるとなると、暗算が苦手な私としては電卓を使いたくなる。そこで、誤差を減らすために2桁目を7捨8入することを考えてみよう。

最悪ケースでの誤差

7捨8入の場合、切り捨てる場合と切り上げる場合の誤差についてそれぞれ考える必要がある。

まず、切り捨てる場合の誤差について考えてみる。この場合、誤差が最も大きくなるのは0x17ff...fである。これの2桁目を7捨8入した値は0x1000...0となる。この場合の誤差は以下のように計算できる。

 \displaystyle{
\frac{|\mathrm{0x1000 \cdots 0} - \mathrm{0x17ff \cdots f}|}{\mathrm{0x17ff \cdots f}} < \frac{|\mathrm{0x1000 \cdots 0} - \mathrm{0x1800 \cdots 0}|}{\mathrm{0x1700 \cdots 0}} = \frac{8}{23} \simeq 0.348
}

これより、2桁目を7捨8入により切り捨てた場合の誤差は約35%以下となる。

次に、切り上げる場合の誤差について考えてみる。この場合、誤差が最も大きくなるのは0x1800...0である。これの2桁目を7捨8入した値は0x2000...0となる。この場合の誤差は以下のように計算できる。

 \displaystyle{
\frac{|\mathrm{0x2000 \cdots 0} - \mathrm{0x1800 \cdots 0}|}{\mathrm{0x1800 \cdots 0}} = \frac{1}{3} \simeq 0.333
}

これより、2桁目を7捨8入により切り捨てた場合の誤差は約33%以下となる。

切り捨てと切り上げの結果をまとめると、誤差は約35%以下と言える。先ほどよりは誤差を削減することができた。

1桁目がfの場合の切り上げ

1桁目がfの場合、2桁目を切り上げるとさらに桁上がりが発生してしまう。しかし、だからと言って特に後の計算に変化はない。このケースについては後述する具体例の中でも取り上げる。

0, 8, 16に丸める際の誤差

7捨8入によってある程度誤差を小さくできたが、1桁目の値が小さいとまだ誤差が大きい。もう少しだけ誤差を小さくするために、0, 8, 16のどれかに丸める方法を考えてみよう。

冒頭でも述べたが、この方法においては値がいくつの場合に0, 8, 16のどれに丸めるかを決めておく必要がある。できるだけ自然なルールにすることが望ましい。そこで、本稿では以下のように丸め方を決める。

  1. 上位2桁の値を2倍する。
  2. 7捨8入する。
  3. 値を2で割る。

上記手順の考え方であるが、大きい数ほど丸めの影響を受けにくいという性質に基づいている。対象となる値を2倍することで7捨8入によって混入する誤差を半分にし、その後に2で割って元のスケールに戻しているのである。このようにすることで、上位から2桁目の値が必ず0, 8のいずれかになる。また、0の場合は切り捨てされる場合と切り上げされる場合があるが、切り上げされる場合は16に丸めることに相当する。

この方法により、2桁目が0~3ならば0、4~bならば8、c~fならば16に丸められることになる。

最悪ケースでの誤差

今回は丸め先が3通りあるので、それぞれについて最悪ケースを考える必要がある。以下で順に見ていこう。

0に丸める場合

この場合、誤差が最も大きくなるのは0x13ff...fである。誤差は以下のように計算できる。

 \displaystyle{
\frac{|\mathrm{0x1000 \cdots 0} - \mathrm{0x13ff \cdots f}|}{\mathrm{0x13ff \cdots f}} < \frac{|\mathrm{0x1000 \cdots 0} - \mathrm{0x1400 \cdots 0}|}{\mathrm{0x1300 \cdots 0}} = \frac{4}{19} \simeq 0.211
}

これより、誤差が約21%以下となる。

8に丸める場合

この場合、誤差が最も大きくなるのは0x1400...0か0x1bff...fのどちらかである。誤差はそれぞれ以下のように計算できる。

 \displaystyle{
\frac{|\mathrm{0x1800 \cdots 0} - \mathrm{0x1400 \cdots 0}|}{\mathrm{0x1400 \cdots 0}} = \frac{1}{5} = 0.200
}

 \displaystyle{
\frac{|\mathrm{0x1800 \cdots 0} - \mathrm{0x1bff \cdots f}|}{\mathrm{0x1bff \cdots f}} < \frac{|\mathrm{0x1800 \cdots 0} - \mathrm{0x1c00 \cdots 0}|}{\mathrm{0x1b00 \cdots 0}} = \frac{4}{27} \simeq 0.148
}

これより、誤差は約20%以下となる。

16に丸める場合

この場合、誤差が最も大きくなるのは0x1c00...0である。誤差は以下のように計算できる。

 \displaystyle{
\frac{|\mathrm{0x2000 \cdots 0} - \mathrm{0x1c00 \cdots 0}|}{\mathrm{0x1c00 \cdots 0}} = \frac{1}{7} \simeq 0.143
}

これより、誤差は約14%以下となる。

結局、この方法では誤差は約21%以下に抑えられる。

ここまでのまとめ

ここまでの議論をまとめておく。16進数から10進数への変換を概算で求める際、上位から3桁目以降は無視してよいが、2桁目は無視できない。

最上位桁がある程度大きければ上位から2桁目以降を切り捨てても問題ないが、7捨8入くらいであれば暗算でも苦労なく行えるので、あまり考えずに7捨8入してしまうのがよいだろう。

最上位桁がある程度小さい場合、0, 8, 16にまとめる方法によって誤差を抑えることができる。しかし、8に丸める場合は上位2桁が残ってしまう。これだとこの後の桁上げの計算が煩雑になるため、このケースは素直に電卓を使った方が速いだろう。もしくは、35%程度の誤差が許容できるのであれば7捨8入してもよい。

桁上げの計算

これまで上位2桁の誤差にだけ着目して議論してきたが、ここからは桁上げの概算方法について考えてみよう。

今、7捨8入によって値は必ず0xz00...0という形になっている。zには適当な値が入る。zの後に続く0の数を nとすると、10進数としての値は以下のようになる。

 \displaystyle{
z_{10} \times 16^n = z_{10} \times 2^{4n}
}

ただし、 z_{10}はzを10進数で表した数を意味する。ここで、右辺を暗算で正確に計算しようとすると、場合によってはかなり厳しいことが分かる。例えばz = d, n = 3の場合を考えると、 13 \times 2^{12}という計算を実行する必要があり、大変面倒くさい。

そこで、以下の2つの近似によって計算を簡略化する。

  1.  z_{10}を偶数に丸める。
  2.  2^{10} \simeq 1000と置き換える。
  3.  2^{9} \simeq 500と置き換える。
  4.  2^{5} \simeq 30と置き換える。

2つ目から4つ目は古典的な方法なので説明を割愛し、1つ目についてのみ説明する。

1桁目の16進数を偶数に丸める

先ほどの計算例でz = cとすると、 12 \times 2^{12}を計算することになる。12は偶数、しかも4の倍数なので、実際に計算を開始する前に 3 \times 2^{14}という形に変換できる。ここまでくれば、あとは 3 \times 2^4 \times 1000 = 48000と近似計算できる。実際、 \mathrm{0xc000} = 49152なので、これはそこまで外していない。

つまり、偶数の場合は計算が幾分かやりやすくなるのである。そこで、zが奇数の場合は1足すか引くかして、偶数に丸めてしまえばよい。ただし、 z_{10}が1桁の奇数の場合、値が1変わるとそれだけで10%以上の誤差が生じる。1桁の場合はそもそもそこまで計算が大変でもないので、この近似は z_{10}が2桁の場合にのみ実施する。

あと決めることは奇数に対して1足すか引くかである。対象となる奇数は11, 13, 15である。折角なら4の倍数に丸めた方が後の計算が楽になるので、これらはそれぞれ12, 12, 16に丸めることにする。

誤差の評価

桁上げ、および11, 13, 15の偶数への丸め誤差について考える。まず、 2^{5},  2^{9},  2^{10}を30, 500, 1000と近似する際の誤差はそれぞれ以下のようになる。

 \displaystyle{
\frac{|30 - 32|}{32} = \frac{1}{16} = 0.0625
}

 \displaystyle{
\frac{|500 - 512|}{512} = \frac{3}{128} = 0.0234
}

 \displaystyle{
\frac{|1000 - 1024|}{1024} = \frac{3}{128} \simeq 0.0234
}

11, 13, 15の偶数への丸めについては11のケースで一番誤差が大きくなるので、11についてのみ誤差を計算する。

 \displaystyle{
\frac{|12 - 11|}{11} = \frac{1}{11} \simeq 0.0909
}

これらの近似は場合によって実施したり実施しなかったりするので、上記の誤差は近似を行った場合にのみ混入する。

手順まとめ

以上の議論をもとに、最終的な手順をまとめておく。

  1. 上位から2桁目を7捨8入する。
  2. 1桁目の値を10進数に変換したとき、11, 13, 15であればそれぞれ12, 12, 16に置き換える。
  3. 1桁目の値の素因数のうち2の個数を mとし、それ以外の素因数の積を gとする。また、2桁目以降の桁数を nとする。この時、上記ステップまでの変換で得られた数を g \times 2^{m+4n}という形で表せる。
  4.  10 \le m+4nであれば 2^{10}の素因数を1000で置き換える。さらに残った指数部が9以上または5以上であれば 2^9,  2^5をそれぞれ500, 30で置き換える。
  5. あとは素直に計算する。

計算全体の誤差

ここまで計算の各種ステップにおける誤差については都度説明してきた。実際にはそれらがすべて積みあがったものが計算全体の誤差となる。本当は誤差についてはいろいろと理論があるようだが、厳密に誤差を評価することは今の私の実力では難しいため、厳しめに評価して単純に誤差を足し合わせるのが安全だろう。

ただし、一番誤差が大きくなるポテンシャルがある7捨8入で実際に誤差が大きくなるのは1桁目が小さいときである。この時は1桁目を偶数に置き換えることはしないため、これらの誤差が同時にのしかかることはない。結局、1桁目が1のときにかかる約35%の誤差と桁上げの誤差数%を合わせた40%程度の誤差が最大と考えられる。

具体例

いくつか具体例を示しておく。

0x750e

正確な値は29966である。

上位から2桁目を7捨8入すると0x7000となる。最上位桁が10進で1桁なので、置き換えは必要ない。すると、 \mathrm{0x7000} = 7 \times 2^{12}となる。 2^{10}を1000で置き換えると 7 \times 4 \times 1000となる。これを計算して28000を得る。

0xc9af

正確な値は51631である。

上位から2桁目を7捨8入すると0xd000となる。0xd = 13なので12 = 0xcに置き換える。すると、 \mathrm{0xc000} = 3 \times 2^{2 + 12} = 3 \times 2^{14}となる。 2^{10}を1000で置き換えると 3 \times 16 \times 1000となる。これを計算して48000を得る。

0xeb0abc43

正確な値は3943349315である。

上位から2桁目を7捨8入すると0xf0000000となる。0xf = 15なので16 = 0x10に置き換える。すると、 \mathrm{0x100000000} = 1 \times 2^{32}となる。 2^{10}を1000で置き換えると 4 \times 1000 \times 1000 \times 1000となる。これを計算して4000000000を得る。

0xfa000000

正確な値は4194304000である。

上位から2桁目を7捨8入すると0x100000000となる。もともと1桁目がfなので、2桁目を切り上げるとさらに桁上がりが発生している点に注意されたい。最上位桁が10進で1桁なので、置き換えは必要ない。すると、 \mathrm{0x100000000} = 1 \times 2^{32}となる。 2^{10}を1000で置き換えると 4 \times 1000 \times 1000 \times 1000となる。これを計算して4000000000を得る。

誤差の推移

最後に、もっと多くの具体例について、それぞれ誤差がどうなるかを見てみよう。

16進数 10進数 近似値 誤差[%]
0x1000 4096 4000 2.34
0x1700 5888 4000 32.1
0x1e00 7680 8000 4.17
0x2500 9472 8000 15.5
0x2c00 11264 12000 6.53
0x3300 13056 12000 8.09
0x3a00 14848 16000 7.76
0x4100 16640 16000 3.85
0x4800 18432 20000 8.51
0x4f00 20224 20000 1.11
0x5600 22016 20000 9.16
0x5d00 23808 24000 0.80
0x6400 25600 24000 6.25
0x6b00 27392 28000 2.22
0x7200 29184 28000 4.06
0x7900 30976 32000 3.31
0x8000 32768 32000 2.34
0x8700 34560 32000 7.41
0x8e00 36352 36000 0.968
0x9500 38144 36000 5.62
0x9c00 39936 40000 0.160
0xa300 41728 40000 4.14
0xaa00 43520 48000 10.1
0xb100 45312 48000 5.93
0xb800 47104 48000 1.90
0xbf00 48896 48000 1.83
0xc600 50688 48000 5.30
0xcd00 52480 48000 8.54
0xd400 54272 48000 11.6
0xdb00 56064 56000 0.114
0xe200 57856 56000 3.21
0xe900 59648 60000 0.590
0xf000 61440 60000 2.34
0xf700 63232 60000 5.11
0xfe00 65024 60000 7.73

グラフも載せておく。

f:id:peng225:20200101225305p:plain

入力が小さいところで誤差が大きいのは7捨8入による影響である。入力が大きいところでも小さいピークがみられるのは、奇数を偶数に丸めている影響である。上記はあくまでサンプリングを行った上でのプロットであるため確かなことは言えないが、1桁目が3以上であればある程度誤差を気にせず概算を行うことができそうだ。

まとめ

本稿では16進数の10進数への変換を概算によって高速に行う方法について述べた。正直、期待したほど良い結果は得られなかったが、誤差の振る舞いについて理解していれば何とか使えそうな方法を編み出すことができた。やはり世の中に確立された方法がないということは、それだけ難しいテーマだということなのだろう。

情報幾何学を嗜む ~ダイバージェンスの不変性~

前回までの記事で確率分布のパラメータが成す空間の双対平坦性や、重要な確率分布族である指数型分布族について説明してきた。本稿では確率分布のパラメータが成す空間の幾何学的な構造について不変性というキーワードからアプローチし、KLダイバージェンスがいかに特別なものであるかについて説明する。

なお、不変性について議論するにあたり、確率分布としては離散・連続のどちらを考えても良いはずである。しかし、残念ながら参考にしている本[1]が離散確率分布のみをターゲットに議論しているため*1、ここでもそうすることにする。

不変性の要請

確率分布族から双対平坦な空間を構成する際、その空間における点 p({\bf x}, {\boldsymbol \theta})を定めるのは確率分布のパラメータ {\boldsymbol \theta}であり、 {\bf x}ではない。そのため、例えば {\bf x}全単射により可逆的に変換される場合などでは、確率分布の表現の仕方は変わってもパラメータは変わらないため、この空間の幾何学的構造にも変化がない事が望まれる。

この考え方をもう一歩進めて、十分統計量というものを考える。十分統計量とは何であるかを説明しだすと長くなるので詳細な解説は他サイト[2]に譲るが、ざっくり言えばパラメータを推定するために十分な統計量である。

 s {\boldsymbol \theta}の十分統計量とすると、Fisherの因子分解定理[3]により確率分布 p({\bf x}, {\boldsymbol \theta})は以下のように書ける。

 \displaystyle{
p({\bf x}, {\boldsymbol \theta}) = \overline{p}(s, {\boldsymbol \theta}) r({\bf x})
}

この時、以下のように不変性の要請が定められる[1]。

不変性の要請
確率分布空間に導入する幾何学的量は, 任意の十分統計量を用いて分布 \overline{p}(s, {\boldsymbol \theta})から導くことができる.

fダイバージェンス

不変性が要請される幾何学的量として、ダイバージェンスは重要なものの1つである。不変なダイバージェンス*2の具体例はいろいろ考えられるが、不変性に加えてさらに分解可能性という性質を要求するとき、それらを満たすダイバージェンスはfダイバージェンスのみである事が知られている。分解可能なダイバージェンス、及びfダイバージェンスの定義を以下に示す[1] (記号の導入のために一部改変して引用する)。

離散確率分布 S_n (n \ge 3)の2つの分布 {\bf p}, {\bf q}ダイバージェンス D[{\bf p}, {\bf q}]を考えよう. これが成分ごとの和の形
 \displaystyle{
D[{\bf p}, {\bf q}] = \sum d(p_i, q_i)
}
に書ける場合, これを分解可能なダイバージェンスと言う.
分解可能で不変なダイバージェンスは,  f(1) = 0を満たす微分可能な凸関数 fを用いて
 \displaystyle{
D_f [{\bf p}, {\bf q} ] = \sum p_i f\left(\frac{q_i}{p_i} \right)
}
と書ける. これをfダイバージェンスと呼ぶ.

 f(1) = 0という条件は D_f [{\bf p}, {\bf p} ] = 0となるために必要である。

双対ダイバージェンス

fダイバージェンスには双対ダイバージェンスが存在する。まず、以下のような関数を考える。

 \displaystyle{
f^* (x) = x f \left(\frac{1}{x} \right)
}

これを用いたfダイバージェンスは以下のようになる。

 \displaystyle{
\begin{eqnarray}
D_{f^*} [{\bf p}, {\bf q} ] &=& p_i \left(\frac{q_i}{p_i} f \left(\frac{p_i}{q_i} \right) \right) \\
&=& q_i f \left(\frac{p_i}{q_i} \right)
\end{eqnarray}
}

 D_{f^*} [{\bf p}, {\bf q} ] D_f^* [{\bf p}, {\bf q} ]と書くことにすると、以下の式が成り立つ。

 \displaystyle{
D_f^* [{\bf p}, {\bf q} ] = D_f [{\bf q}, {\bf p} ]
}

具体例

KLダイバージェンス

 f(x) = -\log{x}とするとfダイバージェンスは以下のようになる。

 \displaystyle{
\begin{eqnarray}
D_f [{\bf p}, {\bf q} ] &=& \sum -p_i \log{\frac{q_i}{p_i}}  \\
&=& \sum p_i \log{\frac{p_i}{q_i}}
\end{eqnarray}
}

これはKLダイバージェンスになっている。

 \alphaダイバージェンス

 \alphaを実パラメータとして f_{\alpha}(x)を以下のように定める。

 \displaystyle{
f_{\alpha}(x) = \begin{cases}
  \frac{4}{1 - \alpha^2} \left(1 - x^{\frac{1+\alpha}{2}} \right) & (\alpha \ne \pm 1) \\
  x \log{x} & (\alpha = 1) \\
  -\log{x} & (\alpha = -1)
\end{cases}
}*3

この時、 f_{\alpha}(x)に関するfダイバージェンスは以下のようになる*4

 \displaystyle{
D_{\alpha} [{\bf p}, {\bf q} ] = \begin{cases}
\frac{4}{1 - \alpha^2} \left(1 - \sum p_i^{\frac{1-\alpha}{2}} q_i^{\frac{1+\alpha}{2}} \right) & (\alpha \ne \pm 1) \\
\sum q_i \log{\frac{q_i}{p_i}} & (\alpha = 1) \\
\sum p_i \log{\frac{p_i}{q_i}} & (\alpha = -1)
\end{cases}
}

 \alphaダイバージェンスはいろいろなダイバージェンスの一般化となっている。例えば、 \alpha = -1とすればこれはKLダイバージェンスになり、 \alpha = 1とすればKLダイバージェンスの双対になる。

標準凸関数

fダイバージェンスには以下の2つの性質がある。

  • 凸関数 f(x) c(x - 1) ( cは定数) という形の1次式を加えたものを用いても値が変わらない。
  • 凸関数 f(x)を定数倍した cf(x)を用いると値が c倍される。

これより、 fの代わりに以下の凸関数を考えても良い。

 \displaystyle{
\overline{f}(x) = \frac{1}{f''(1)}(f(x) - f'(1)(x - 1))
}

 \overline{f}(x) f(1) = 0, f'(1) = 0, f''(1) = 1を満たす。このような凸関数 \overline{f}(x)を標準凸関数と呼ぶ。

標準凸関数の双対

本筋とは外れるが、標準凸関数の双対 \overline{f}^* (x)は標準凸関数になるのだろうか?以下で確かめてみよう。まず、 \overline{f}^* (x)の一階導関数、二階導関数はそれぞれ以下のようになる。

 \displaystyle{
\overline{f}^*{'}(x) = \overline{f} \left(\frac{1}{x} \right) - \frac{1}{x} \overline{f}' \left(\frac{1}{x} \right)
}

 \displaystyle{
\overline{f}^*{'}{'}(x) = \frac{1}{x^3} \overline{f}'' \left(\frac{1}{x} \right)
}

よって f(1), f'(1), f''(1)の値はそれぞれ以下のようになる。

 \displaystyle{
\begin{eqnarray}
\overline{f}^*(1) &=&  \overline{f}(1) \\
&=& 0
\end{eqnarray}
}

 \displaystyle{
\begin{eqnarray}
\overline{f}^*{'}(1) &=&  \overline{f}(1) -  \overline{f}'(1) \\
&=& 0
\end{eqnarray}
}

 \displaystyle{
\begin{eqnarray}
\overline{f}^*{'}{'}(1) &=& \overline{f}''(1) \\
&=& 1
\end{eqnarray}
}

以上により、 \overline{f}^* (x)も標準凸関数であることが分かった。

正測度空間

ここで、後の議論のために必要な正測度空間*5に言及しておく。

正測度空間とは確率分布から制約 \sum p_i = 1を外すことで得られる空間であり、以下のように表すことができる。

 \displaystyle{
M_n = \{{\bf m} = (m_1, \cdots , m_n) , m_i > 0 \}
}

正測度空間にも確率分布の空間と同様にfダイバージェンスを定義できる。すなわち、 fを標準凸関数とすると、 M_nの任意の2点 {\bf x}, {\bf y}についてf ダイバージェンスは以下のように定義できる。

 \displaystyle{
D_f[{\bf x}, {\bf y} ]= \sum x_i f \left(\frac{y_i}{x_i} \right)
}

正測度空間の場合、 fは標準凸関数であることが必要らしい。標準凸関数でないとダイバージェンスの定義を満たさなくなるようである。

双対平坦空間を導く不変で分解可能なダイバージェンス

ここまでで確率分布の空間や正測度空間に導入される不変なダイバージェンスとしてfダイバージェンスについて説明した。しかし、幾何学的構造が不変性を持っていると望ましいと思う一方で、情報幾何学的な議論を展開する上でやはり双対平坦性は欠かせない。

では、不変性を持ち、かつ双対平坦空間を導くような良いとこ取りなダイバージェンスは存在しないのだろうか?この疑問の答えを与えるのが以下の定理である[1]。

KLダイバージェンスの特徴付け
双対平坦性を導く不変で分解可能なダイバージェンスはKLダイバージェンス (またはその双対) であり, それ以外にはない.

この事実こそがKLダイバージェンスを唯一無二の特別なダイバージェンス足らしめるのである。

正測度空間の場合

ここで話を正測度空間にまで広げると、他にも双対平坦性を導く不変で分解可能なダイバージェンスが存在する。それを説明するために、以下のような関数を考える。

 \displaystyle{
k_{\alpha}(x) = \begin{cases}
  \frac{2}{1 - \alpha} \left(x^{\frac{1-\alpha}{2}} - 1 \right) & (\alpha \ne 1) \\
  \log{x} & (\alpha = 1) \\
\end{cases}
}

これを用いて {\bf m}の各座標を以下のように変換する。

 \displaystyle{
\theta^i = k_{\alpha}(m_i)
}

これを正測度 m_i \alpha表現と呼ぶ。この時、以下の定理が成立する[1]。

 M_nにおいて,  \alphaダイバージェンス \alpha表現をアファイン座標系とする不変で分解可能なBregmanダイバージェンスであり、これ以外に不変で分解可能なBregmanダイバージェンスはない.

厳密な証明は本[1]に譲るとして、ここではBregmanダイバージェンス \alphaダイバージェンスが両立することの雰囲気だけ説明しておく。まず、関数 U_{\alpha}(x)を以下のように定義する*6

 \displaystyle{
U_{\alpha}(x) = \frac{2}{1+\alpha} k^{-1}_{\alpha}(x)
}

この時、 M_nにおいて凸関数 \Psi_{\alpha}({\boldsymbol \theta})を以下のように定義する。

 \displaystyle{
\Psi_{\alpha}({\boldsymbol \theta}) = \sum U_{\alpha}(\theta^i)
}

これを用いて得られるBregmanダイバージェンス {\boldsymbol \theta}座標から {\bf m}座標に戻すと \alphaダイバージェンスになる*7

再び確率分布の空間の場合

確率分布の空間が正測度空間の部分集合であることに着目すると、KLダイバージェンスの特徴付けについては正測度空間の特別な場合として説明できる。

確率分布の場合は \sum m_i = 1でなければならない。これに m_i = k_{\alpha}^{-1} (\theta^i)を代入すると、 \sum k_{\alpha}^{-1} (\theta^i) = 1となる。 k_{\alpha}^{-1} (\theta^i) \alpha = -1でのみ1次関数になるため、この時に限り確率分布の空間が双対平坦な正測度空間内の超平面になる。これよりKLダイバージェンスだけが不変で分解可能かつ双対平坦空間を導くダイバージェンスとなる。

まとめ

本稿では不変で分解可能なダイバージェンスとしてfダイバージェンスを導入し、さらに双対平坦性も兼ね備えるダイバージェンスとしてKLダイバージェンス \alphaダイバージェンスの特徴付けを行った。

正直、本[1]だけでは理解できない部分が多く、書きたかったことの全てを書ききれなかったが、これまでの一連の記事を書き上げる中で情報幾何学に対する一定の理解は得たと思う。

ただし、触れられたのは基礎的な部分だけで、応用面については取り上げることが出来なかった。本[1]をパラパラと読み進めてみると、情報幾何学の手法を用いて解決された実用的な問題もあるようだが、数学的な難易度は更に増しているように見える。今すぐにとはいかないが、そのうち応用についても理解したい。

*1:ここまでずっと連続確率分布を扱っておきながら、いざ数学的な扱いが面倒になると離散確率分布に逃げる本書のスタンスは好ましいものとは思えない。

*2:この用語はもっと厳密に定義しておくべきであるが、本[1]やネット上の情報を漁っても納得のいく答えが得られなかった。そのため、大変心苦しいが定義を誤魔化したまま議論を進めている。

*3: \alpha = \pm 1の場合だけ特別な式が与えられている。本[1]によるとこれは \alpha \ne \pm 1の式の極限になっているとのことだが、明らかに \alpha \to 1の時に発散する。一体どういうことなのだろう…もし何か理由があってこの定義に妥当性があるのだとしても、全く自明ではないので説明して欲しかった。

*4:本[1]の式は符号が間違っている

*5:「正測度空間」という言葉をググってみても、全然それらしいページがヒットしない。この用語はどれくらいフォーマルなものなのだろうか。

*6: \alpha = -1では定義されないが、本[1]でそれに対する言及はない。恐らく、また極限を考えるのだろう。

*7:本[1]からはこのように読み取れたのだが、計算が複雑で、結局自分では確かめることができなかった。どなたか計算を追うことができた方がいれば、ぜひ真偽の程を教えて頂きたい。

情報幾何学を嗜む ~指数型分布族の幾何学~

前回の記事では双対平坦空間について説明した。これまでの記事では具体的な確率分布族は登場せず、ひたすら抽象的な議論が続いたが、いよいよ具体的な確率分布族について考えてみる。本稿では情報幾何学的に重要である指数型分布族に着目し、その幾何学的な構造について述べる。

指数型分布族

定義

指数型分布族とは {\bf u}を確率変数、 {\boldsymbol \theta}をパラメータとして、確率密度関数が以下のように書ける確率分布の族である。

 \displaystyle{
p({\bf u}, {\boldsymbol \theta}) = \exp \left(\sum_i \theta^i k_i({\bf u}) + r({\bf u})- \psi({\boldsymbol \theta}) \right)
}

いきなりだが、ここで (情報幾何学的な議論の本筋とはあまり関係ないが) 重要なポイントがある。それは、確率密度関数積分してなんぼであり、その積分とは通常はLebesgue積分であるため、確率密度関数は測度と密接な関係にあるということである。確率密度関数と測度の両方が定まって初めて積分により確率を求める事ができる。

今、 \exp(r({\bf u}))に着目すると、これは {\boldsymbol \theta}に依存していないため、確率密度関数から測度に追いやる事ができる。そうして、積分する際には測度として \exp(r({\bf u}))を折り込み済みのものを使用するのである。

このように考えることで、指数型分布族の定義式から \exp(r({\bf u}))を省く事ができる。ここでさらに x_i = k_i({\bf u})と置き、 {\bf x} = (x_1, x_2, \cdots, x_n)とすれば、確率密度関数は以下のように表せる。

 \displaystyle{
p({\bf x}, {\boldsymbol \theta}) = \exp({\boldsymbol \theta} \cdot {\bf x} - \psi({\boldsymbol \theta}))
}

左辺は確率密度関数なので、定義域全域で積分して1にならなければならない。この条件より \psi({\boldsymbol \theta})は以下のようになる。

 \displaystyle{
\begin{eqnarray}
\int p({\bf x}, {\boldsymbol \theta}) d{\bf x} &=& \int \exp({\boldsymbol \theta} \cdot {\bf x} - \psi({\boldsymbol \theta})) d{\bf x} \\
1 &=& \int \exp({\boldsymbol \theta} \cdot {\bf x} - \psi({\boldsymbol \theta})) d{\bf x} \\
\exp(\psi({\boldsymbol \theta})) &=& \int \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x} \\
\psi({\boldsymbol \theta}) &=& \log \int \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x}
\end{eqnarray}
}

念のため述べておくが、上記の計算に登場する積分では測度に \exp(r({\bf u }))が掛かる影響を考慮済みであると暗に仮定している。以降の計算でも同様である。

 \psi({\boldsymbol \theta})の凸性

前節で登場した \psi({\boldsymbol \theta})は凸関数である。それを示すためにHesse行列を求めてみよう。

 \displaystyle{
\begin{eqnarray}
\frac{\partial^2}{\partial \theta^i \partial \theta^j} \psi({\boldsymbol \theta})
&=& \frac{\partial^2}{\partial \theta^i \partial \theta^j} \log \int \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x} \\
&=& \frac{\partial}{\partial \theta^i} \frac{\int x_j \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x}}{\int \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x}} \\
&=& \frac{\int x_i x_j \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x} \int \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x} - \int x_i \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x} \int x_j \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x}}
{\left \{\int \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x} \right \}^2} \\
&=& \frac{\int x_i x_j p({\bf x}, {\boldsymbol \theta}) d{\bf x} \int p({\bf x}, {\boldsymbol \theta}) d{\bf x} - \int x_i p({\bf x}, {\boldsymbol \theta}) d{\bf x} \int x_j p({\bf x}, {\boldsymbol \theta}) d{\bf x}}
{\left \{\int p({\bf x}, {\boldsymbol \theta}) d{\bf x} \right \}^2} \\
&=& \int x_i x_j p({\bf x}, {\boldsymbol \theta}) d{\bf x} - \int x_i p({\bf x}, {\boldsymbol \theta}) d{\bf x} \int x_j p({\bf x}, {\boldsymbol \theta}) d{\bf x} \\
&=& \mathrm{E} [x_i x_j ] - \mathrm{E} [x_i ] \mathrm{E} [x_j ] \\
&=& \mathrm{Cov}(x_i, x_j)
\end{eqnarray}
} ・・・(1)

これより、Hesse行列は共分散行列となる。共分散行列は半正定値であるため、 \psi({\boldsymbol \theta})は凸関数である[2][3]。

指数型分布族の双対平坦構造

これまでの議論により指数型分布族には自然と凸関数が備わっていることが分かった。前回、前々回の記事より、凸関数が与えられればBregmanダイバージェンスや双対平坦空間が得られることを見てきた。これらの事実より、指数型分布族にもこれらの情報幾何学的な構造を定めることができる。本章ではそれを見ていこう。

双対空間

まずは双対座標、及び双対凸関数を求めてみよう。それぞれ以下のように計算できる。

 \displaystyle{
\begin{eqnarray}
{\boldsymbol \eta} &=& \nabla \psi({\boldsymbol \theta}) \\
&=& \nabla \log \int \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x} \\
&=& \frac{\int {\bf x} \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x}}{\int \exp({\boldsymbol \theta} \cdot {\bf x}) d{\bf x}} \\
&=& \int {\bf x} \exp({\boldsymbol \theta} \cdot {\bf x} - \psi({\boldsymbol \theta})) d{\bf x} \\
&=& \int {\bf x} p({\bf x}, {\boldsymbol \theta}) d{\bf x}
\end{eqnarray}
}

 \displaystyle{
\begin{eqnarray}
\phi({\boldsymbol \eta}) &=& \max_{{\boldsymbol \theta}} ({\boldsymbol \theta} \cdot {\boldsymbol \eta} - \psi({\boldsymbol \theta})) \\
&=& {\boldsymbol \theta}({\boldsymbol \eta}) \cdot \int {\bf x} \exp({\boldsymbol \theta}({\boldsymbol \eta}) \cdot {\bf x} - \psi({\boldsymbol \theta}({\boldsymbol \eta}))) d{\bf x} - \psi({\boldsymbol \theta}({\boldsymbol \eta})) \\
&=& \int {\boldsymbol \theta}({\boldsymbol \eta}) \cdot {\bf x} \exp({\boldsymbol \theta}({\boldsymbol \eta}) \cdot {\bf x} - \psi({\boldsymbol \theta}({\boldsymbol \eta}))) d{\bf x} - \psi({\boldsymbol \theta}({\boldsymbol \eta})) \int \exp({\boldsymbol \theta}({\boldsymbol \eta}) \cdot {\bf x} - \psi({\boldsymbol \theta}({\boldsymbol \eta}))) \\
&=&  \int ({\boldsymbol \theta}({\boldsymbol \eta}) \cdot {\bf x} - \psi({\boldsymbol \theta}({\boldsymbol \eta}))) \exp({\boldsymbol \theta}({\boldsymbol \eta}) \cdot {\bf x} - \psi({\boldsymbol \theta}({\boldsymbol \eta}))) d{\bf x} \\
&=& \int p({\bf x}, {\boldsymbol \theta}({\boldsymbol \eta})) \log p({\bf x}, {\boldsymbol \theta}({\boldsymbol \eta})) d{\bf x}
\end{eqnarray}
}

これより、 {\boldsymbol \eta} p({\bf x}, {\boldsymbol \theta})の期待値、 \phi({\boldsymbol \eta}) p({\bf x}, {\boldsymbol \theta}({\boldsymbol \eta}))エントロピーの符号を変えたものになっていることが分かる。

Bregmanダイバージェンス

次に \psi({\boldsymbol \theta})から導かれるBregmanダイバージェンスを計算してみる。

 \displaystyle{
\begin{eqnarray}
D[{\boldsymbol \theta}' : {\boldsymbol \theta} ] &=& \psi({\boldsymbol \theta}') + \phi({\boldsymbol \eta}) - {\boldsymbol \theta}' \cdot {\boldsymbol \eta} \\
&=& \psi({\boldsymbol \theta}') \int p({\bf x}, {\boldsymbol \theta}) d{\bf x} + \int p({\bf x}, {\boldsymbol \theta}) \log p({\bf x}, {\boldsymbol \theta}) d{\bf x} - \int {\boldsymbol \theta}' \cdot {\bf x} p({\bf x}, {\boldsymbol \theta}) d{\bf x} \\
&=&  \int p({\bf x}, {\boldsymbol \theta}) \log p({\bf x}, {\boldsymbol \theta}) d{\bf x} - \int ({\boldsymbol \theta}' \cdot {\bf x} - \psi({\boldsymbol \theta}')) p({\bf x}, {\boldsymbol \theta}) d{\bf x} \\
&=&  \int p({\bf x}, {\boldsymbol \theta}) \log p({\bf x}, {\boldsymbol \theta}) d{\bf x} - \int p({\bf x}, {\boldsymbol \theta}) \log p({\bf x}, {\boldsymbol \theta}') d{\bf x} \\
&=& \int p({\bf x}, {\boldsymbol \theta}) \log \frac{p({\bf x}, {\boldsymbol \theta})}{p({\bf x}, {\boldsymbol \theta}')} d{\bf x}
\end{eqnarray}
}

ただし、 {\boldsymbol \theta} {\boldsymbol \eta}、および {\boldsymbol \theta}' {\boldsymbol \eta}'がそれぞれ互いに双対であるとする。これはKLダイバージェンスに他ならない[4]。

Riemann計量

Riemann計量は以下のように求められるのだった。

 \displaystyle{
g_{ij} = \frac{\partial^2}{\partial \theta^i \partial \theta^j} \psi({\boldsymbol \theta})
}

右辺は式(1)である程度まで計算したが、それをさらに以下のように変形してみる。

 \displaystyle{
\begin{eqnarray}
g_{ij} &=& \mathrm{Cov}(x_i, x_j) \\
&=& \mathrm{E} [(x_i - \mathrm{E} [x_i ])(x_j  - \mathrm{E} [x_j ]) ] \\
&=& \mathrm{E} \left [\left(x_i - \frac{\partial}{\partial \theta^i} \psi({\boldsymbol \theta}) \right) \left( x_j  - \frac{\partial}{\partial \theta^j} \psi({\boldsymbol \theta}) \right) \right ] \\
&=& \mathrm{E} \left [\frac{\partial}{\partial \theta^i} ({\boldsymbol \theta} \cdot {\bf x} - \psi({\boldsymbol \theta})) \frac{\partial}{\partial \theta^j}({\boldsymbol \theta} \cdot {\bf x}  - \psi({\boldsymbol \theta})) \right ] \\
&=& \mathrm{E} \left [\frac{\partial}{\partial \theta^i} \log p({\bf x}, {\boldsymbol \theta}) \frac{\partial}{\partial \theta^j} \log p({\bf x}, {\boldsymbol \theta}) \right ]
\end{eqnarray}
}

これはFisher情報行列に他ならない[5]。

例:指数分布

せっかくなので例を見てみよう。指数型分布族に属する確率分布はいろいろあるが、ここでは指数分布をピックアップしてみる。指数分布の確率密度関数は以下の式で表される[6]。

 \displaystyle{
p(x, \lambda)=\left\{{\begin{array}{ll}\lambda e^{-\lambda x}&(x\geq 0)\\0&(x<0)\end{array}}\right.
}

ただし、 \lambda >0である。 x\geq 0の場合の式において \theta = -\lambdaと置いて少し変形すると以下のようにできる。

 \displaystyle{
p(x, \theta) = \exp( \theta x - (-\log (-\theta)) )
}

そのため、指数分布は指数型分布族に含まれる。

双対座標と双対凸関数

双対座標 \etaは以下のようになる。

 \displaystyle{
\begin{eqnarray}
\eta &=& \int x p(x, \theta) dx \\
&=& \int_0^{\infty} x (-\theta) e^{\theta x} dx \\
&=& -\theta \left \{\left [x \frac{e^{\theta x}}{\theta} \right ]_0^{\infty} -  \int_0^{\infty} \frac{e^{\theta x}}{\theta} dx \right \} \\
&=& \int_0^{\infty} e^{\theta x} dx \\
&=& \left [  \frac{e^{\theta x}}{\theta} \right ]_0^{\infty} \\
&=& -\frac{1}{\theta}
\end{eqnarray}
}

双対凸関数 \phiは以下のようになる。

 \displaystyle{
\begin{eqnarray}
\phi(\eta) &=& \int p(x, \theta(\eta)) \log p(x, \theta(\eta)) dx \\
&=& \int_0^{\infty} (-\theta) e^{\theta x} \log ((-\theta) e^{\theta x}) dx \\
&=& \int_0^{\infty} (-\theta) e^{\theta x} (\log (-\theta) + \theta x) dx \\
&=& \log (-\theta) \int_0^{\infty} (-\theta) e^{\theta x} dx + \theta \int_0^{\infty} x (-\theta) e^{\theta x} dx \\
&=& \log (-\theta) \left [ -e^{\theta x} \right ]_0^{\infty} - 1 \\
&=& \log (-\theta) - 1 \\
&=& -\log \eta - 1
\end{eqnarray}
}

Bregmanダイバージェンス

Bregmanダイバージェンスは以下のようになる。

 \displaystyle{
\begin{eqnarray}
D[\theta' : \theta ] &=& \int p(x, \theta) \log \frac{p(x, \theta)}{p(x, \theta')} dx \\
&=& \int_0^{\infty} (-\theta) e^{\theta x} \log \frac{(-\theta) e^{\theta x}}{(-\theta') e^{\theta' x}} dx \\
&=& (-\theta) \int_0^{\infty} e^{\theta x} (\log (-\theta) + \theta x - \log (-\theta') - \theta' x) dx \\
&=& (-\theta) \left \{ (\log (-\theta) - \log (-\theta')) \int_0^{\infty} e^{\theta x} dx + (\theta - \theta') \int_0^{\infty} x e^{\theta x}  dx \right \} \\
&=& (-\theta) \left \{ (\log (-\theta) - \log (-\theta')) \frac{-1}{\theta} + \frac{\theta - \theta'}{\theta^2} \right \} \\
&=& \log (-\theta) - \log (-\theta') - 1 + \frac{\theta'}{\theta} \\
&=& - \log (-\theta') -\log \eta - 1 - \theta' \eta
\end{eqnarray}
}

Riemann計量

指数分布はパラメータが1つしかないため、Riemann計量はスカラーとなる。具体的には以下のように計算される。

 \displaystyle{
\begin{eqnarray}
g &=& \frac{\partial^2}{\partial \theta^2} \psi(\theta) \\
&=& \frac{\partial^2}{\partial \theta^2} (-\log (-\theta)) \\
&=& \frac{\partial}{\partial \theta} \frac{-1}{\theta} \\
&=& \frac{1}{\theta^2}
\end{eqnarray}
}

Riemann計量が分かるとパラメータ空間の中での確率分布同士の距離が分かる。確率分布同士の距離とは、定性的には確率分布の形状が互いにどれくらい異なるかを表すものと考えられる。

今回の例の場合、指数分布の平均は \frac{-1}{\theta}であるため、 \thetaの絶対値が大きくなると平均は0に近づいていく。そのような領域では \thetaの値が少し違う分布同士でほとんど形状の差がなくなる。これは \thetaの絶対値が大きくなるに連れてRiemann計量の値が0に近づいていくことに対応する。

一方、 \thetaが0に近いところでは \thetaが僅かに変わるだけで平均値が大幅に変動し、分布の形状が大きく変わる。これは \thetaが0に漸近するに連れてRiemann計量が急激に大きくなることと関連している。

ただし、本当は分散による影響も加味する必要がある。指数分布の分散は \frac{1}{\theta^2}であるため、 \thetaが0に近いところでは分散が大きくなる。分散が大きくなると分布が散らばるため、 \thetaが変化しても分布が変動し辛くなる。これは先程の平均の議論と逆のことを言っていることになるが、指数分布の場合は平均の変化の方が分布の形状を決める上で支配的な要因になっているということなのだろう。

まとめ

本稿では指数型分布族が持つ情報幾何学的な構造について調べた。指数型分布族には必ず凸関数が付随し、これにより得られるBregmanダイバージェンスはKLダイバージェンスになっていることを見た。さらに、付随する凸関数から定められるRiemann計量はFisher情報行列に一致することが分かった。

実はKLダイバージェンスは情報幾何学において特別な意味を持つ。次回はそのあたりの話を書きたいと思う。

情報幾何学を嗜む ~微分幾何学的な双対平坦空間の導入~

前回の記事ではBregmanダイバージェンスから導かれる双対空間について述べた。本稿ではこれらの空間に定められる双対接続、及びそこから導かれる双対平坦空間について考えてみる。

基本的には本[1]を参考にしているのだが、この本はどうも双対平坦な空間の導出がざっくりしすぎていて、少々納得感に欠けた。そのため、本稿では双対平坦な空間の導出に関する計算を少しだけ泥臭く書いてみることにする。

なお、本稿では全体的にEinsteinの規約を用いているので注意されたい。

ダイバージェンスから導かれるRiemann計量

前回の記事でダイバージェンスの定義について説明した。その中で、Taylor展開した際の2次の項の係数が正定値対称行列になるという条件があった。この正定値対称という条件はいかにもRiemann計量を想起させる。実際、情報幾何学ではこれをRiemann計量として使うことで、確率分布のパラメータの空間をRiemann多様体と見なすのである。

Bregmanダイバージェンスの場合の例

例として、以下の2変数凸関数から導かれるBregmanダイバージェンスについて、そこから得られるRiemann計量を計算してみよう。

 \displaystyle{
f(x, y) = x^2 + 3xy + 4y^2
}

始めに f(x, y)が凸関数であることを確認する。Hesse行列は以下のようになる。

 \displaystyle{
G = \left(
\begin{array}{cc}
2 & 3 \\
3 & 8
\end{array}
\right)
}

 \mathrm{det} G = 7 \gt 0となるため、これは凸関数である。

次に、Riemann計量を求めてみる。と言っても、前回の記事でBregmanダイバージェンスをTaylor展開した際の2次の項は、元になる凸関数のHesse行列に等しいことを述べた。そのため、結局 Gがリーマン計量である。

よく見ると Gは確かに対称行列になっている。これは f(x, y) C^2級なので当然である。また、以下の計算により正定値行列であることも分かる。

 \displaystyle{
\begin{eqnarray}
\left(
\begin{array}{cc}
x & y
\end{array}
\right)
G
\left(
\begin{array}{c}
x \\
y
\end{array}
\right)
&=&
2(x^2 + 3xy + 4y^2) \\
&=& 2\left(\left(x + \frac{3}{2}y \right)^2 + \frac{7}{4}y^2 \right) \gt 0
\end{eqnarray}
}

ただし、 (x, y) \ne (0, 0)である。

Riemann計量を成分毎に書き下すと以下のようになる。

 \displaystyle{
\begin{eqnarray}
g_{1, 1} &=& 2 \\
g_{1, 2} &=& g_{2, 1} = 3 \\
g_{2, 2} &=& 8
\end{eqnarray}
}

双対接続

次に、多様体の接続について考えてみる。情報幾何学において特に重要な概念として双対接続がある。少々難しい概念なので、順を追って説明していこう。

接続とは

ざっくり言うと、接続とは多様体の異なる点における接空間の間に対応関係を与えるものである。特に、その対応関係にある種の線形性があるものをAffine接続と呼ぶ。Affine接続を説明すると長くなるので、詳細は[2]などを参照のこと。

Levi-Civita接続

Affine接続のうち、さらに以下の2つの性質を満たすものをLevi-Civita接続と呼ぶ。

  1.  \nabla_{{\bf X}} {\bf Y} - \nabla_{{\bf Y}} {\bf X} = [{\bf X}, {\bf Y}] (対称な接続) 
  2.  {\bf X} g({\bf Y}, {\bf Z}) = g(\nabla_{{\bf X}}{\bf Y}, {\bf Z}) + g({\bf Y}, \nabla_{{\bf X}}{\bf Z}) (計量との整合性) 

Levi-Civita接続はベクトルの平行移動に対して計量を保つため、Riemann計量と強い依存関係がある。実際、Levi-Civita接続の接続係数はRiemann計量から一意に定まる。詳細は[2]などを参照のこと。

ここで、 {\bf X} = \partial_i, {\bf Y} = \partial_j, {\bf Z} = \partial_kを1つ目の式に代入してみる。ただし、局所座標系を (x^1, x^2, \cdots , x^n)とし、 \partial_i = \frac{\partial}{\partial x^i}とする。

 \displaystyle{
\begin{eqnarray}
\nabla_{\partial_i} \partial_j - \nabla_{\partial_j} {\partial_i} &=& [\partial_i, \partial_j] \\
\Gamma_{ij}^l \partial_l - \Gamma_{ji}^l \partial_l &=& \partial_i \partial_j - \partial_j \partial_i \\
\Gamma_{ij}^l \partial_l &=& \Gamma_{ji}^l \partial_l
\end{eqnarray}
}

成分を比較して \Gamma_{ij}^l = \Gamma_{ji}^lとなる。

次に、 {\bf X} = \partial_i, {\bf Y} = \partial_j, {\bf Z} = \partial_kを2つ目の式に代入してみる。

 \displaystyle{
\begin{eqnarray}
\partial_i g(\partial_j, \partial_k) &=& g(\nabla_{\partial_i} \partial_j, \partial_k) + g(\partial_j, \nabla_{\partial_i} \partial_k) \\
\partial_i g_{jk} &=& g(\Gamma_{ij}^l \partial_l, \partial_k) + g(\partial_j, \Gamma_{ik}^l \partial_l) \\
\partial_i g_{jk} &=& \Gamma_{ij}^l g_{lk} + \Gamma_{ik}^l g_{jl}
\end{eqnarray}
}

最後の式の右辺で  \Gamma_{ijk} = \Gamma_{ij}^l g_{lk}などの置き換えをすると以下のようになる。

 \displaystyle{
\partial_i g_{jk} = \Gamma_{ijk} + \Gamma_{ikj}
}

双対接続

Levi-Civita接続における計量との整合性の条件を外し、代わりに2つの接続 \nabla, \nabla^{*}が以下の条件を満たすとする。

 \displaystyle{
{\bf X} g({\bf Y}, {\bf Z}) = g(\nabla_{{\bf X}}{\bf Y}, {\bf Z}) + g({\bf Y}, \nabla^{*}_{{\bf X}}{\bf Z})
}

このような接続を双対接続と呼ぶ。

Levi-Civita接続の時と同様に {\bf X} = \partial_i, {\bf Y} = \partial_j, {\bf Z} = \partial_kを代入すると以下のようになる。

 \displaystyle{
\partial_i g_{jk} = \Gamma_{ijk} + \Gamma_{ikj}^{*}
} ・・・(1)

ただし、接続係数の右肩に*が付いているものは \nabla^{*}の接続係数であることを意味する。

Bregmanダイバージェンスから導かれるRiemann空間の双対平坦性

前回の記事で、Bregmanダイバージェンスから導かれる双対空間について述べた。以下では元の空間の座標を {\boldsymbol \theta}、双対空間の座標を {\boldsymbol \eta}で表す。

今、双対接続 \nabla, \nabla^{*}として、接続 \nabla {\boldsymbol \theta}座標における接続係数が全て大域的に0になるようなものを考える。これはつまり、曲率が0の平坦な接続であることを意味する。この時、接続 \nabla^{*}がどうなるかを考えてみよう。

準備

いくつか式を準備しておこう。ここでは {\boldsymbol \theta}座標、 {\boldsymbol \eta}座標で表した接続係数をそれぞれ \Gamma_{ijk}^{({\boldsymbol \theta})}, \Gamma_{ijk}^{({\boldsymbol \eta})}などと表記する。また、Riemann計量についても同様に g^{({\boldsymbol \theta})}_{ij}, g^{({\boldsymbol \eta})}_{ij}のように表記する。

片方の接続が平坦な場合の双対接続の式

まず(1)式に接続係数0を代入すると以下の式が成立する。

 \displaystyle{
\frac{\partial}{\partial \theta^i} g^{({\boldsymbol \theta})}_{jk} = \Gamma_{ikj}^{* ({\boldsymbol \theta})}
} ・・・(2)

ここで、Riemann計量の対称性より g^{({\boldsymbol \theta})}_{jk} = g^{({\boldsymbol \theta})}_{kj}であり、さらに接続の対称性より \Gamma_{ikj}^{* ({\boldsymbol \theta})} = \Gamma_{kij}^{* ({\boldsymbol \theta})}となる。これらを組み合わせると、添字の並び替えに対して \nabla^{*}の接続係数が不変となることが分かる。特に、以下の式はのちほど利用するため明示的に述べておく。

 \displaystyle{
\Gamma_{ikj}^{* ({\boldsymbol \theta})} = \Gamma_{jki}^{* ({\boldsymbol \theta})}
} ・・・(3)

Riemann計量の別表現

元の空間に定義された凸関数を \psi、双対空間に定義された凸関数を \phiとすると、 {\boldsymbol \theta}座標と {\boldsymbol \eta}座標の変換は以下の式で表されるのだった。

 \displaystyle{
\begin{eqnarray}
\eta_i &=& \frac{\partial \psi}{\partial \theta^i} \\
\theta^i &=& \frac{\partial \phi}{\partial \eta_i}
\end{eqnarray}
}

これらの両辺をそれぞれ \theta^j, \eta_j偏微分すると以下のようになる。

 \displaystyle{
\begin{eqnarray}
\frac{\partial \eta_i}{\partial \theta^j} &=& \frac{\partial^2 \psi}{\partial \theta^i \partial \theta^j} \\
&=& g_{ij}^{({\boldsymbol \theta})}
\end{eqnarray}
} ・・・(4)

 \displaystyle{
\begin{eqnarray}
\frac{\partial \theta^i}{\partial \eta_j} &=& \frac{\partial^2 \phi}{\partial \eta_i \partial \eta_j} \\
&=& g_{ij}^{({\boldsymbol \eta})}
\end{eqnarray}
} ・・・(5)

以上により、 {\boldsymbol \theta}座標、 {\boldsymbol \eta}座標におけるRiemann計量を凸関数を用いずに表すことが出来た。

接続係数の座標変換

最後に、接続係数の座標変換について述べる。 {\bf x}座標系から {\bf x}'座標系への接続係数の変換式は以下のようになる[2]。

 \displaystyle{
\Gamma{'}_{k'm'}^{i'} = \frac{\partial x^k}{\partial x{'}^{k'}} \frac{\partial x^m}{\partial x{'}^{m'}} \frac{\partial x{'}^{i'}}{\partial x^i} \Gamma_{km}^i + \frac{\partial^2 x^r}{\partial x{'}^{k'} \partial x{'}^{m'}} \frac{\partial x{'}^{i'}}{\partial x^r}
}

この変換式は有名なので調べればすぐに出てくるが、添字を下げた版の \Gamma_{ijk}の座標変換式に関してはほとんど情報がない。幸いEMANさんのサイト[3]がヒントになったので、それを参考に変換式を導出してみる。

まず、上で示した変換式の両辺に g'_{i'l'}をかけて i'について和を取る。和の記号はEinsteinの規約により省略する。

 \displaystyle{
g'_{i'l'} \Gamma{'}_{k'm'}^{i'} = g'_{i'l'} \frac{\partial x^k}{\partial x{'}^{k'}} \frac{\partial x^m}{\partial x{'}^{m'}} \frac{\partial x{'}^{i'}}{\partial x^i} \Gamma_{km}^i + g'_{i'l'} \frac{\partial^2 x^r}{\partial x{'}^{k'} \partial x{'}^{m'}} \frac{\partial x{'}^{i'}}{\partial x^r}
}

ここで、Riemann計量の座標変換式を利用する。これもEMANの物理学[4]から式を引用する。

 \displaystyle{
g'_{i'j'}  = \frac{\partial x^k}{\partial x'^{i'}} \frac{\partial x^l}{\partial x'^{j'}} g_{kl}
}

これを代入し、さらに左辺を添え字を下げた記号に置き換えると以下のようになる。

 \displaystyle{
\begin{eqnarray}
\Gamma{'}_{k'm'l'} &=& \frac{\partial x^i}{\partial x{'}^{i'}} \frac{\partial x^l}{\partial x{'}^{l'}} g_{il} \frac{\partial x^k}{\partial x{'}^{k'}} \frac{\partial x^m}{\partial x{'}^{m'}} \frac{\partial x{'}^{i'}}{\partial x^i} \Gamma_{km}^i + \frac{\partial x^s}{\partial x{'}^{i'}} \frac{\partial x^t}{\partial x{'}^{l'}} g_{st} \frac{\partial^2 x^r}{\partial x{'}^{k'} \partial x{'}^{m'}} \frac{\partial x{'}^{i'}}{\partial x^r} \\
&=& \frac{\partial x^k}{\partial x{'}^{k'}} \frac{\partial x^m}{\partial x{'}^{m'}} \frac{\partial x^l}{\partial x{'}^{l'}} \Gamma_{kml} + g_{st} \frac{\partial^2 x^s}{\partial x{'}^{k'} \partial x{'}^{m'}} \frac{\partial x^t}{\partial x{'}^{l'}}
\end{eqnarray}
} ・・・(6)

双対平坦性の導出

準備が整ったので本題に入る。少々天下り的だが、 \Gamma_{ikj}^{* ({\boldsymbol \eta})} \Gamma_{ikj}^{* ({\boldsymbol \theta})}に変換する式を考えてみる。

 \displaystyle{
\begin{eqnarray}
\Gamma_{ikj}^{* ({\boldsymbol \theta})}
&=& \frac{\partial \eta^{i'}}{\partial \theta_i} \frac{\partial \eta^{k'}}{\partial \theta_k} \frac{\partial \eta^{j'}}{\partial \theta_j} \Gamma_{i'k'j'}^{* ({\boldsymbol \eta})}
 + g_{st}^{({\boldsymbol \eta})} \frac{\partial^2 \eta^s}{\partial \theta_i \partial \theta_k} \frac{\partial \eta^t}{\partial \theta_j} \\
&=& \frac{\partial \eta^{i'}}{\partial \theta_i} \frac{\partial \eta^{k'}}{\partial \theta_k} \frac{\partial \eta^{j'}}{\partial \theta_j} \Gamma_{i'k'j'}^{* ({\boldsymbol \eta})}
 + \frac{\partial \theta_s}{\partial \eta^t} \frac{\partial^2 \eta^s}{\partial \theta_i \partial \theta_k} \frac{\partial \eta^t}{\partial \theta_j} \\
&=& \frac{\partial \eta^{i'}}{\partial \theta_i} \frac{\partial \eta^{k'}}{\partial \theta_k} \frac{\partial \eta^{j'}}{\partial \theta_j} \Gamma_{i'k'j'}^{* ({\boldsymbol \eta})}
 + \frac{\partial^2 \eta^s}{\partial \theta_i \partial \theta_k} \frac{\partial \theta_s}{\partial \theta_j} \\
&=& \frac{\partial \eta^{i'}}{\partial \theta_i} \frac{\partial \eta^{k'}}{\partial \theta_k} \frac{\partial \eta^{j'}}{\partial \theta_j} \Gamma_{i'k'j'}^{* ({\boldsymbol \eta})}
 + \frac{\partial^2 \eta^j}{\partial \theta_i \partial \theta_k} \\
&=& \frac{\partial \eta^{i'}}{\partial \theta_i} \frac{\partial \eta^{k'}}{\partial \theta_k} \frac{\partial \eta^{j'}}{\partial \theta_j} \Gamma_{i'k'j'}^{* ({\boldsymbol \eta})}
 + \Gamma_{jki}^{* ({\boldsymbol \theta})} \\
&=& \frac{\partial \eta^{i'}}{\partial \theta_i} \frac{\partial \eta^{k'}}{\partial \theta_k} \frac{\partial \eta^{j'}}{\partial \theta_j} \Gamma_{i'k'j'}^{* ({\boldsymbol \eta})}
 + \Gamma_{ikj}^{* ({\boldsymbol \theta})}
\end{eqnarray}
}

1つ目の等号は式(6)から、2つ目の等号は式(5)から、3つ目の等号は偏微分の連鎖律から、5つ目の等号は式(2)(4)から、6つ目の等号は式(3)からそれぞれ得られる。

右辺第2項と左辺が一致するため、任意の点において右辺第1項は0でなければならない。右辺第1項に式(4)を適用すると以下のようになる。

 \displaystyle{
\begin{eqnarray}
\Gamma_{ikj}^{* ({\boldsymbol \theta})}
&=& g_{i'i}^{({\boldsymbol \theta})} g_{k'k}^{({\boldsymbol \theta})} g_{j'j}^{({\boldsymbol \theta})} \Gamma_{i'k'j'}^{* ({\boldsymbol \eta})}
 + \Gamma_{ikj}^{* ({\boldsymbol \theta})}
\end{eqnarray}
}

今考えている状況においてRiemann計量はgivenであるため、右辺第1項が0になるためには \Gamma_{i'k'j'}^{* ({\boldsymbol \eta})} = 0になる他ない。つまり、双対座標系において接続 \nabla^{*}は平坦となるのである。

以上の議論をまとめてみる。多様体上にBregmanダイバージェンスから定まるRiemann計量が与えられ、更に双対接続 \nabla, \nabla^{*}が与えられたとする。接続 \nabla {\boldsymbol \theta}座標系で平坦となるとき、接続 \nabla^{*} {\boldsymbol \eta}座標系において平坦となる。このような接続の組が与えられた空間を双対平坦空間と呼ぶ。

蛇足

双対平坦空間の説明として、本稿のように接続係数の座標変換から直接的に平坦性を示す方法を採っている記事が全く見つからなかったため、本稿の計算は完全に私が考えたものである。先人がいないということもあり、正直あまり自信がない。本[1]から結論だけは分かっていたため、やや結論ありきで論理展開してしまっているような気がする。もし不備にお気づきの際はご指摘頂けるとありがたい。

まとめ

本稿ではBregmanダイバージェンスからRiemann計量が得られ、さらにそこから双対平坦な空間が導かれることを述べた。双対平坦性の導出には少々複雑な計算を行ったが、おかげでこれまでのもやもやが少しだけ晴れたような気がする。

情報幾何学関連の記事はまだまだ書きたい事が多いが、なんとか今年中には書き終えたい。

情報幾何学を嗜む ~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}
}

まとめ

本稿では情報幾何学のトピックのうち、Bregmanダイバージェンスとその双対ダイバージェンスに関する事柄について述べた。ダイバージェンスは対称性を持たないが、BregmanダイバージェンスについてはLegendre変換による双対空間まで考えることで美しい対称構造が得られることを確認した。

本稿ではまだ微分幾何学らしい概念は登場しなかった。つまり、ここで述べたことは情報幾何学の中ではまだまだ序の口ということである。次回以降、少しずつ幾何学的な内容に踏み込んでいきたいと思う。

*1:甘利先生の本[1]ではダイバージェンス微分可能性などに触れられないままいきなりTaylor展開しているところがもやもやする。あまり細かい数学的議論に重きを置いた本ではないので、これについては滑らかな関数であり、かつ剰余項は収束すると仮定を置いてしまうしかないのだろう。

*2:ダイバージェンスの引数に点を入れたり点の座標を入れたりと記号がぶれているが、本[1]に合わせた結果なので好意的に解釈して頂けるとありがたい。

*3:本[1]ではBregmanダイバージェンスの定義に用いる凸関数の性質について厳密な条件が記載されていない。議論を簡単にするために、ここでは滑らかな狭義凸関数であるとした。