符号付き整数の代数的構造

数学の勉強に行き詰まったので、プログラミング関連で思い付いた小ネタについて書いてみる。

C言語でプログラミングをしたことがあれば、符号付き整数というものは扱ったことがあるだろう。例えばint型の変数とか、そういうものである。符号付き整数では負の数を扱う必要があるため、ビット列をそのまま2進数で表現された整数として解釈するわけにはいかず、表現したい整数との間に何らかの対応付けが必要となる。

先日、この符号付き整数の背後には何らかの代数的構造が潜んでいるのではないかと思い立った。本稿ではそれについて私が考えたことをまとめる。

準備

記号の導入

本稿では0, 1の並びにより表現されるビット列の集合について考える。ビット列に言及するとき、それがビット列であることが分かるように添字 bを付ける。例えば、 1011_bと書いたら、これは1, 0, 1, 1というビット列を意味する。ただし、変数に対して添字は付けない。

本稿で考えるビット列の長さは有限である。特に断らない限り、長さは全て d \in \mathbb{N}であるとする。

全てのビットが0であるようなビット列は、簡潔のため、単に 0_bと書くことにする。また、最下位ビットだけ1で他が全て0であるようなビット列は、簡潔のため、単に 1_bと書くことにする。

ビット列 aに対して、その全てのビットを反転させて得られるビット列を \overline{a}と書く。特に、全てのビットが1であるようなビット列は \overline{0_b}と書く。

0と1の割り当てについて

符号無し整数の場合、 00...00_b, 00...01_bはそのまま整数の0, 1に対応する。符号付き整数の場合はこの後の議論を待たないとどのビット列をどの整数に割り当てるか決められないところだが、 00...00_b, 00...01_bだけは符号無し整数の場合と同じく0, 1に割り当てることにする。

環としての構造

長さ dのビット列を全て集めた集合 S_dを考える。符号のことは一旦忘れて、ビット列を2進数で表現された整数であると見なせば、 S_dの任意の2元に対して足し算を行うことが出来る。その和をさらに 2^dで割った余りを2進数で表せば、これは S_dの元になる。このようにして S_dに加法の演算を与えることが出来る。

乗法についても同様に与えることが出来る。結局、このようにして加法と乗法が与えられた集合 S_d \mathbb{Z}/2^d \mathbb{Z}と同型な可換環になる。

イデアル

 S_dはどんなイデアルを持つだろうか?それを知るために、 S_dと同型な環である \mathbb{Z}/2^d \mathbb{Z}イデアルについて考えてみよう。

対応定理[1]により、 \mathbb{Z}イデアルのうち 2^d \mathbb{Z}を含むものと、 \mathbb{Z}/2^d \mathbb{Z}イデアルは一対一に対応する。 2^d \mathbb{Z}を含む \mathbb{Z}イデアルは以下の d+1個である。

 \displaystyle{
2^d \mathbb{Z}, 2^{d-1} \mathbb{Z}, \cdots , 
2 \mathbb{Z}, \mathbb{Z}
}

これらに対応する \mathbb{Z}/2^d \mathbb{Z}イデアルは以下の通りである。

 \displaystyle{
\begin{eqnarray}
&& \{0\}, \\
&& \{0, 2^{d-1}\}, \\
&& \cdots , \\
&& \{0, 2, 4, \cdots, 2^d - 2\}, \\
&& \mathbb{Z}/2^d \mathbb{Z}
\end{eqnarray}
}

特筆すべきは、これら以外の部分集合はイデアルにならないということである。例えば、 \mathbb{Z}/2^d \mathbb{Z}の元のうち3の倍数の集合はイデアルではない。

ただし、これはビット列をそのまま2進数で表現された整数であると見なした場合の話である。そのようなビット列と整数の間の対応関係の与え方はまさに符号無し整数そのものであるため、符号無し整数については \mathbb{Z}/2^d \mathbb{Z}と全く同じことが言える。

では、符号付き整数の場合はどうであろうか?この時点ではまだ符号付きの場合のビット列と整数の対応付けについて述べていないため詳細は割愛するが、結論としてはやはり2の冪乗以外はイデアルの元とならない。

これは実際にプログラミングを行う際に注意が必要である。以下にこの重要性を示すためのサンプルコードと実行結果を示す。

サンプルコード:

#include <stdio.h>

int main()
{
    int a = 3;
    int b = 2000000000;
    int ab = a*b;

    printf("a = %d, b = %d, a*b = %d\n",
           a, b, ab);

    if(ab % 3 == 0){
        printf("ab can be divided by 3.\n");
    }else{
        printf("ab cannot be divided by 3.\n");
    }
    return 0;
}

実行結果:

a = 3, b = 2000000000, a*b = 1705032704
ab cannot be divided by 3.

ご覧の通り、3と他の整数の積を計算しているのに、その結果が3で割り切れないケースが存在する。

零因子

 d = 1の時、 S_d F_2と同型な体になる。一方、 d \ne 1の時は体どころか整域にすらならない。これも実際にプログラミングをする際には注意を要する事実である。例えば、2つのint型整数 a, bに対して、どちらも0でないことを確かめるために a * bが0かどうかチェックするのは誤りになる。

ここでの議論は符号付き整数・符号無し整数どちらについても成り立つ。符号の有無とはビット列の解釈の仕方の問題なのであって、環としての構造に違いはないためである。また、準備の章で 00...00_bは符号の有無に関わらず0に割り当てると決めたので、ビット列として考えても、符号化された整数として考えても、零因子を持つということに変わりはない。

このことを具体的に動くプログラムで確かめた結果を以下に示す。

サンプルコード:

#include <stdio.h>

int main()
{
    int a = 65536;
    int b = 196608;
    int ab = a*b;

    printf("a = %d, b = %d, a*b = %d\n",
           a, b, ab);

    if(ab == 0){
        printf("ab is 0.\n");
    }else{
        printf("ab is not 0.\n");
    }
    return 0;
}

実行結果:

a = 65536, b = 196608, a*b = 0
ab is 0.

ご覧の通り、0でない2つの整数の積が0になるケースがあることが分かる。

ビット列と符号付き整数の対応関係

ここからはいよいよ符号付き整数でのビット列と整数の対応付けの議論に踏み込んでいく。そのために、まずは以下のような写像 nを考える。

 \displaystyle{
n : S_d \ni x \mapsto \overline{x} + 1_b \in S_d
}

以下でこの写像の性質について調べてみよう。

基本的性質

写像 nについて以下の式が成り立つ。

  1.  x + n(x) = 0_b
  2.  n(n(x)) = x
  3.  n(x + y) = n(x) + n(y)
  4.  n(x)n(y) = xy

以下で順に証明していく。

式1の証明

 \displaystyle{
\begin{eqnarray}
x + n(x) &=& x + \overline{x} + 1_b \\
&=& \overline{0_b} + 1_b \\
&=& 0_b
\end{eqnarray}
}

式2の証明

 \displaystyle{
\begin{eqnarray}
n(n(x)) &=& \overline{n(x)} + 1_b \\
&=& \overline{\overline{x}+1_b} + 1_b \\
&=& \overline{\overline{x}+1_b} + (x + \overline{x} + 1_b) + 1_b \\
&=& \overline{\overline{x}+1_b} + (\overline{x} + 1_b) + x + 1_b \\
&=& \overline{0_b} + x + 1_b \\
&=& x
\end{eqnarray}
}

式3の証明

 \displaystyle{
\begin{eqnarray}
n(x+y) &=& \overline{x+y} + 1_b \\
&=& \overline{x+y} + (x + n(x)) + (y + n(y)) + 1_b \\
&=& \overline{x+y} + (x+y) + n(x) + n(y) + 1_b \\
&=& n(x) + n(y)
\end{eqnarray}
}

式4の証明

 \displaystyle{
\begin{eqnarray}
n(x)n(y) &=& n(x)n(y) + x(y+n(y)) \\
&=& n(x)n(y) + xy + xn(y) \\
&=& n(y)(n(x)+x) + xy \\
&=& xy
\end{eqnarray}
}

それぞれの式の意味

上で述べた4つの式にはそれぞれ重要な意味がある。

まず、式1は x \in S_dの加法による逆元が n(x)であることを述べている。つまり、 xを符号付き整数として見なしたとき、 n(x)はその符号を反転したものだと解釈することができる。

次に式2だが、これは写像 nを2回施すと元に戻るということを述べている。このことからも、 nが符号を反転させるための写像として相応しい性質を持っていることが分かるだろう。

続いて式3であるが、これは和を取ってから符号を反転したものは、符号を反転してから和を取ったものと一致することを述べている。これは S_dを加法について群と見なした時に、 nが群準同型になっていることを示している。

最後に、式4は符号を反転した2つの整数の積が符号を反転する前の2つの整数の積に等しいことを示している。これにより、さまざまな符号の組み合わせでの掛け算をうまく定義できるようになる。

全単射

符号を反転する写像であるならば、 n全単射であって欲しいが、果たしてそうなっているであろうか?以下で確かめてみよう。

単射性の証明

 \mathrm{Ker}(n)が自明であることを示す。任意の x \in \mathrm{Ker}(n)について n(x) = 0_bが成立する。これを変形すると以下のようになる。

 \displaystyle{
\begin{eqnarray}
n(x) &=& 0_b \\
\overline{x} + 1_b &=& 0_b \\
\overline{x} + 1_b + \overline{0_b} &=& 0_b + \overline{0_b} \\
\overline{x} &=& \overline{0_b} \\
x &=& 0_b
\end{eqnarray}
}

よって \mathrm{Ker}(n) = \{0_b\}となる。

全射性の証明

 n(n(x)) = xより明らかである。

以上により、 n全単射である。 nは群準同型でもあり、かつ S_d S_d自身に写すため、結局 n S_dの群自己同型となる。

不動点

符号付き整数の特異な構造を理解するために、 n不動点について理解しておくことは重要である。どのような点が不動点になるか、具体的に計算で確かめてみよう。

 \displaystyle{
\begin{eqnarray}
n(x) &=& x \\
n(x) + x &=& x + x \\
x + x &=& 0_b
\end{eqnarray}
}

この条件を満たすビット列としては 0_b, 100...0_bの2つがある。後述するが、例えば1バイトの符号付き整数の場合、 10000000_bは-128に対応する。これの符号を反転しようとしても、残念ながら符号は変わらず-128のままとなる。

これについても念のため実際のプログラムで確かめておこう。

サンプルコード:

#include <stdio.h>

int main()
{
    int a = (1 << 31);
    printf("a = %d, -a = %d\n", a, -a);
    return 0;
}

実行結果:

a = -2147483648, -a = -2147483648

考察の通り、符号を反転しても値が変わらないという結果になった。

 nは環自己同型か?

ここまで n S_dの群自己同型であることを見た。しかし、 S_dは環なのだから、環準同型にはならないのか?という疑問は当然湧いてくる。結論から言うと、 d = 1の時に限り nは環準同型になるが、それ以外の場合にはそうならない。

実際、環準同型であるためには n(1_b) = 1_bとなる必要があるが、 1_b n不動点になるのは d = 1の時だけである。

ビット列と符号付き整数の対応

これまでの議論を元に、ビット列と符号付き整数の対応関係を以下に示す。

ビット列 符号付き整数  n不動点 備考
 000 \cdots 00_b 0 加法の単位元
 000 \cdots 01_b 1 乗法の単位元
 000 \cdots 10_b 2
... ...
 011 \cdots 11_b  2^d - 1
 100 \cdots 00_b  -2^d
 100 \cdots 01_b  -2^d + 1  n(011 \cdots 11_b)
... ...
 111 \cdots 10_b -2  n(000 \cdots 10_b)
 111 \cdots 11_b -1  n(000 \cdots 01_b)

0以上の整数は最上位ビットが0、負の整数は最上位ビットが1になっていることが分かる。これより、最上位ビットは符号ビットと呼ばれる。

結局、符号ビットが0の整数に対してビット反転して1を足したものを、その整数の符号を反転して得られる負の整数としているわけである。こんなよく分からない規則で負の数を作り出している割には、足し算・掛け算はビット列を符号無し整数とみなした時と同じ規則で行えるというのは、なんとも不思議な気持ちになる。しかし、それは全て写像 nの性質に裏打ちされてのことなのである。

まとめ

本稿では符号付き整数の背後に潜む代数的構造について考察した。符号付き整数は可換環の構造を成しており、符号反転のための写像をうまく与えることで、綺麗にビット列と符号付き整数との間の対応関係を与えられることが分かった。

情報科学の多くの分野には数学が密接に関わっており、我々は普段それを意識せずに使っていることが多い。たまにはその背景にある数学的理論に思いを馳せるのも面白いだろう。

代数幾何学で遊ぼう ~なぜZariski位相を使うのか~

前回に続き本稿でも代数幾何学について考えてみる。今回のテーマはZariski位相である。

代数幾何学と言えば必ずと言って良いほどZariski位相が登場する。Zariski位相は多項式の集合の共通零点によって定められ、確かに代数多様体に入れる位相として相応しいような気がする。

しかし、本当にZariski位相でなければダメなのだろうか?代数幾何学を議論する上で、なぜ通常の位相ではなくZariski位相を持ち出したくなるのだろうか?本稿ではそのモチベーションに迫ってみたいと思う。

定義

 k代数的閉体とし、 {\bf A}^n = k^n n次元アフィン空間とする。Zariski位相の定義を本[1]から引用する。

Zariski位相
 {\bf A}^nに代数的集合を閉集合とする位相を入れる. この位相を {\bf A}^nのザリスキ位相 (Zariski topology) という.

代数幾何学の主要な研究対象は代数多様体である。代数多様体はアフィン代数多様体の張り合わせで作られるようなので、ここではアフィン代数多様体の定義を示しておく[1]。

アフィン代数多様体 (古典的定義)
 {\bf A}^nの既約な閉集合 Xにザリスキ位相から誘導された位相を入れたものをアフィン代数多様体 (affine algebraic variety) またはアフィン多様体 (affine variety) という.

アフィン代数多様体上の関数

アフィン代数多様体は上で示したようにアフィン空間の部分集合である。今、アフィン空間 {\bf A}^n上の関数をアフィン代数多様体 Xに制限したものを考える。アフィン空間全体で見れば異なる関数 f, gがあったとして、もしこれらが X上で一致するのであれば、両者を区別する意味はない。 X上の関数を考える場合、これらの違いは無視したい。

そこで登場するのが座標環である。定義を以下に示す[1]。

座標環
 {\bf A}^n \supset Xを代数的集合とする.
 \displaystyle{
A(X) = k[X_1, X_2, \cdots , X_n] / I(X)
}
 Xの座標環 (coordinate ring) またはアフィン座標環 (affine coordinate ring) という.

Zariski位相の特徴

Zariski位相の有用性を知るために、Zariski位相が入った空間の特徴をいろいろな角度から調べてみよう。

分離性

Zariski位相が入ったアフィン空間は T_1空間となるが、Hausdorff空間ではない。つまり、普段良く考える距離位相などに比べると、密着度の高い位相空間と言える。

分離性が T_0までは落ちず何とか T_1で踏み留まったのは、空間の各点が閉集合になるようにZariski位相を定義したことによる。実際、Wikipedia[2]には以下のような記載がある。

位相空間 Xに対して、以下の条件はどれもたがいに同値である。

  •  X T_1-空間である。
  • (中略)
  • 各点が Xにおいて閉じている、即ち Xの各点 xに対して単元集合 \{x\}閉集合である。

なお、各点が閉集合であることはHilbertの零点定理から分かる。

ここまでの説明を見て「なんだ、Hausdorff空間じゃないのか。そんな病的な位相を考えて何になるんだ?」と思うかも知れない。私自身、まだHausdorff空間でないことのメリット・デメリットを深くは理解していないが、差し当たり以下の文章を引用しておく[3]。

so basically anything one doesn't understand yet is not very interesting? The Zariski topology is very, very, very natural:
(中略)
Also, it is a misconception that non-hausdorff spaces are pathological.

コンパクト性

Zariski位相が入ったアフィン空間だけでなく、アフィン代数多様体もHausdorff空間ではない。しかし、任意の開被覆から有限開被覆を取ることが出来るので準コンパクト空間になる。

証明は本[1]の演習問題の回答に記載があるが、さすがにそれを引用するのはネタバレのようで気が引けるため、証明は割愛する。

開基

アフィン代数多様体には開基を考えることが出来る。 X \subset {\bf A}^nをアフィン代数多様体 A(X) = k[X_1, X_2, \cdots , X_n] / I(X)を座標環とする。この時、以下のように基本開集合が定義される[1]。

基本開集合
 A(X) \ni f \ne 0に対し
 \displaystyle{
X_f = \{x \in X | f(x) \ne 0\}
}
とおき,  Xの基本開集合 (distinguished open set) という.

これを用いて、開基は \{X_f | f \in A(x), f \ne 0\}と書ける。すなわち、1つの関数から定められる代数的集合の補集合が開基の元となる。

位相の強さ

位相の強さと写像の連続性

位相の強さと写像の連続性の間には関係がある。位相空間 U, Vに対して写像 f: U \to Vがあったとする。このとき、 Vの位相が強ければ強いほど、 fが連続になるために Uに課される条件は厳しくなる。つまり、 fが連続になりにくくなる。

逆に、 Uの位相が強ければ強いほど、連続になるために Vから課される条件に対して対応しやすくなる。つまり、 fが連続になりやすくなる。

多項式関数の連続性

では、 {\bf A}^nにZariski位相を入れた空間における写像の連続性についてはどうなるだろうか?Zariski位相は通常の位相に比べて弱いため、何となくこの空間に定義域を持つような写像は連続になりにくいように思える。

しかし、実は多項式関数は連続になる。以下でそれを確かめてみよう。証明は[4]を参考にした。

 f : k^n \to k多項式関数とする。 kの任意の閉集合 Sに対して、 f^{-1}(S)閉集合であることが言えれば良い。

Zariski位相における閉集合の定義より、 I \subset k[X_1, X_2, \cdots , X_n]が存在して
S = \{x | \forall h \in I, h(x) = 0\}となる。任意の p \in f^{-1}(S)について明らかに f(p) \in Sとなるので、 \forall h \in I, h \circ f(p) = 0となる。多項式関数同士の合成はやはり多項式関数になるので、 \{h \circ f | h \in I \} \subset k[X_1, X_2, \cdots , X_n]となる。

以上により、 p多項式の集合 \{h \circ f | h \in I \}の共通零点として表すことが出来た。 pは任意なので、Zariski位相の定義より f^{-1}(S)閉集合である。

正則写像の連続性

多項式関数を拡張したような概念として正則写像がある。定義を本[1]より引用する。

正則写像
 X \subset {\bf A^m}, Y \subset {\bf A^n}代数的閉体 k上のアフィン代数多様体とし, (中略). 写像 \alpha : X \to Y f_1(x_1, \cdots x_m), \cdots , f_n(x_1, \cdots x_m) \in k[x_1, \cdots , x_m]を用いて  \displaystyle{
\begin{eqnarray}
\alpha : &X& \to &Y& \\
&(a_1, \cdots a_m)& \mapsto &(f_1(x_1, \cdots x_m), \cdots , f_n(x_1, \cdots x_m))&
\end{eqnarray}
} と与えられるとき,  \alpha Xから Yへの正則写像 (morphism) という.

*1

正則写像もZariski位相について連続となる[1]。それだけでなく、Zariski位相は正則写像が連続となり、かつ空間の各点が閉集合となるような最弱の位相になっているようだ[5]。

なぜZariski位相を使うのか?

調べれど答えは見つからず

ここまでZariskiの特徴を見てきたが、結局なぜ代数幾何学ではZariski位相を使うのだろうか?この問いに対するストレートな答えは、頑張ってググっても見つからなかった。Mathematics Stack Exchangeにそれらしい質問[3]が投稿されてはいたが、私が納得できる回答はなかった。

ただ、運良く以下のようなツイートを見つけることが出来た。

なるほど、Zariski位相をより一般に環から作られた位相の一種だと考えれば、多項式環以外から作られた位相と並べてみることでZariski位相の自然さが理解出来るというわけだ。

このツイートはなかなかの説得力があり、これで納得しても良いのだが、せっかくなのでちょっとだけ自分の考えも書いてみる。

空間に位相を入れる目的

そもそも、空間に位相を入れる目的はなんだろうか?これが分からなければZariski位相以前の問題である。

その答えは、連続写像が定義できることである。そして、連続写像を通して、異なる空間同士を位相同型の名の元に同一視出来ることである、というのが私の考えだ。

空間にどのような位相を入れるかは、どのような空間を同一視するか?ということと関係しており、考えたい問題に応じて適切な位相を選択する必要がある。

Zariski位相を入れることの意味

では、Zariski位相を選択する意味とは何だろうか?そもそも代数幾何学多項式環から定まる代数多様体を研究する分野だと考えれば、その文脈で登場する写像の中では多項式関数や正則写像が主役となるのは明白であろう。となれば、これらが連続となるような位相を入れたくなる。

逆に、それ以外の写像が変に連続になってしまうと、代数多様体の間に余計な同一視が生まれる恐れがある。出来る限りそのような不純物が入り込まないよう、正則写像が連続となる位相の中で最弱の位相を入れたくなる。そうすることで、異なる代数多様体を真に代数幾何学的に意味のある方法で同一視することが出来るのである。

ただ、あまりに位相が弱すぎても実用に耐えないので、 T_1くらいの分離性はあった方が良いのだろう。結局、そうして選ばれたのがZariski位相だったのではないかというのが、本稿を書く中で私がたどり着いた答えである。

まとめ

本稿ではZariski位相の基本的な性質を調べた上で、代数幾何学においてなぜZariski位相を使うのかについて考察した。私の出した答えは「Zariski位相が正則写像が連続になり、かつ T_1空間となる最弱の位相だから」というものであった。これが正しいかどうかは分からないが、こういった根本的な疑問の答えを探す営みは理解を助けてくれるので、今後も継続していきたい。

*1:正則写像の英訳ってregular mapではないのだろうか?

代数幾何学で遊ぼう ~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}という計算を実行する必要があり、大変面倒くさい。

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

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