『エントロピーと多様性の数理』をちょっと読んだ

エントロピーと多様性の数理｜森北出版株式会社

www.morikita.co.jp

妻からクリスマスプレゼントに『エントロピーと多様性の数理』をもらった。ちょっと読んだけど、すごく面白い。全部読みたいけれども冬休み中には読めないので、あとで読み進めたところを振り返りやすいようにおもしろポイントを書き残す。

多様性の定量化、エントロピー、そしてマグニチュード
#

序文で本全体を通したあらすじが書かれているのだけど、この時点ですごく面白い。以下はその一端。

例えば、以下 2 つの群衆では、どちらがより「多様性」が高いといえるだろうか？

A: 4 つの種が存在し、単一の種の個体数の割合が 90%
B: 3 つの種が存在し、それぞれの種の個体数の割合が 33%

“種"の現存数で見れば、群衆 A のほうが多様性が高いといえる。一方、“群集の釣り合い"で見れば、対立する視点の影響力が均衡している群衆 B のほうが多様性が高いといえる。

これは実は多様度と呼ばれる連続な 1 パラメータ族 $(D_q)_{q \in [0, \infty)}$ の両極端にある。この $D$ はどのような視点で多様性を測るかという「視点」と捉えられよう。

実は $D_1$ の対数（上のケースで言えば B）は実は Shannon エントロピーの指数関数と一致する。これは直感にあう。Shannon エントロピーは一様分布で最大になるから。

この $D$ が具体的にどんな形で得られるのかはこの時点ではわからない。

面白いのは、任意の距離空間に対して、すべての視点 $q$ に対してそれを最大にする単一の分布が存在するということ。有限距離空間については、なんと一意に存在することが証明される。つまり、多様性は距離空間の不変量となるのだ。

ここでマグニチュードあるいはEuler 標数と呼ばれる、圏それ自体に対するサイズの概念を定義すると、さらにおもしろいことがわかる。

マグニチュードの定義を、圏よりもさらに広い豊穣圏に拡張できる。任意の距離空間は豊穣圏とみなすことができるので、距離空間 $X$ のマグニチュード $|X| \in \mathbb{R}$ の定義を得られる。

まずこのマグニチュードは幾何学的に豊かな性質を持つ。マグニチュードのある形は、以下を復元できる：

$X$ の Minkowski 次元。これはポテンシャル論における結果を用いて証明される。
$X$ の体積。これは偏微分方程式の技法を用いて証明される。
$X$ の表面積。これは大域解析の技法を用いて証明される。

そして、距離空間 $X$ の $q$ に対する最大の多様度 $D_{\text{max}}$ は、$X$ のある部分空間のマグニチュードと一致する！

Cauchy の関数方程式の条件をどこまで緩められるか
#

$f(x+y) = f(x) + f(y)$ が成り立つ関数 $f$ を加法的関数と呼ぶ。

これは $f$ が微分可能ならば、$f(x) = ax$ という線形関数になることが知られている。

ではこの条件をどこまで緩めることができるか？

この本では

微分可能
連続
一つ以上の点で連続
可測

という条件でも、線形関数になることが証明される。本の中では詳しく語られないが、どうもこの条件はさらに緩められるようだ。

面白いことに、選択公理を仮定すると、線形でない加法的関数 $f: \mathbb{R} \to \mathbb{R}$ が存在することになる。

まず実数直線 $\mathbb{R}$ は明らかな仕方で $\mathbb{Q}$ 上のベクトル空間であることに注意する。$\mathbb{Q}$ 上の基底 $B$ を選び、$B$ の元 $b$ を選び、$b$ で 1、他では 0 の値をとる関数を $\phi: B \to \mathbb{R}$ とする。基底の普遍性より、$\phi$ は $\mathbb{Q}$-線形写像 $f: \mathbb{R} \to \mathbb{R}$ に一意的に拡張される。

上のどこで選択公理が使われているかというと「$\mathbb{Q}$ 上の基底 $B$ を選び」の部分。任意のベクトル空間、特に今回は $\mathbb{R}$ は $\mathbb{Q}$ 上のベクトル空間とみなしたときに、基底の存在を保証するために選択公理が必要になる。

ここで、すべての関数 $f: \mathbb{R} \to \mathbb{R}$ が可測であることは ZF 公理（つまり選択公理を除いた ZFC 公理系）上、無矛盾であることが知られている。

一方、よく知られているように選択公理もまた ZF 公理上、無矛盾。

すなわち、ZF から出発すればすべての加法的関数が線形であるか、あるいはすべての加法的関数が線形であるというわけではないことの、いずれか一方を、矛盾することなく仮定することができる！

$q$対数
#

実数の数列 $f(1), f(2), \ldots$ は、すべての $m, n \geq 1$ に対して

$$ f(mn) = f(m) + f(n) $$

であるとき、対数的と呼ばれる。

ある条件のもとで、対数的な $f$ は

$$ f(n) = a \log n $$

である。

これを拡張した $q$対数というものがある：

$$ \ln_q x = \int_1^x t^{-q} dt $$

$q$対数は $q$ が 1 のときには対数と一致する。そういう意味では $q$対数は対数の一般化といえる。

では、対数がもともと持っていた性質をどの程度 $q$対数は維持しているだろうか？

$q$対数は対数と違って対数的ではない：

$$ \ln_q (xy) \neq \ln_q x + \ln_q y $$

代わりに、ある $g$ が存在して

$$ \ln_q (xy) = \ln_q x + g(x) \ln_q y $$

となる。逆に、ある $f$ に上を満たす $g$ が存在すれば、$f$ は $q$対数である。

この拡張された $q$対数を Shannon エントロピーの中の対数として用いることで、$q$対数的エントロピーというものが定義される。

この $q$対数的エントロピーは、$q$ が 1 のときには Shannon エントロピーと一致する。つまり、これも Shannon エントロピーの拡張といえる。

これは 4 章で語られるが、この $q$対数的エントロピーは驚きの期待値を表すことになる！

符号化の観点で見た Shannon エントロピー
#

アルファベットを 0 と 1 の有限列で符号化する方式を考える。このとき、その符号化した列の長さがなるべく小さくなるようにしたい。

こう考えようとしたときに、アルファベットの出現頻度を考慮するとよい。簡単に言えば、出現頻度の高い文字は短い符号で表現し、一方出現頻度の低い文字は長い符号で表現する。

このように考えたときの符号語長の期待値は、底を 2 とした Shannon エントロピーと一致する。これが情報源符号化定理。

例えば、4 つのシンボル a,b,c,d の頻度分布がそれぞれ $p = (1/2, 1/4, 1/8, 1/8)$ であるとき、以下のように符号化する：

a: 0
b: 10
c: 110
d: 111

このとき、符号語長の期待値は

$$ \frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 + \frac{1}{8} \cdot 3 + \frac{1}{8} \cdot 3 = \frac{1}{2} + \frac{1}{2} + \frac{3}{8} + \frac{3}{8} = \frac{7}{4} $$

となる。

これは底を 2 とした Shannon エントロピーと一致する：

$$ H(p) = \frac{1}{2} \log_2 \frac{1}{2} + \frac{1}{4} \log_2 \frac{1}{4} + \frac{1}{8} \log_2 \frac{1}{8} + \frac{1}{8} \log_2 \frac{1}{8} = \frac{7}{4} $$

ここで気にしたいのは、上に示した符号化の対応である：

a: 0
b: 10
c: 110
d: 111

例えば b の符号を 11 にしたらどうなるか？

こうすると例えば 110 という符号は c と ba どちらとも解釈できる。故に適切なマッピングになっていない。

一意な方法で符号化できる符号を瞬時符号と呼ぶ。

この瞬時符号、いつでも見つけられるのか？

それができる。それがKraft の不等式。平均符号語長よりも短い瞬時符号を見つけることは不可能である。すなわち、

すべての $p \in \Delta_n$ に対して

$$ \sum_{i=1}^n p_i L_i \geq H^{(2)} (p) $$

が成り立つ。ここで $p$ は $n$ 個のシンボルの頻度分布であり、$L_i$ はそれぞれのシンボルの符号語長である。

さらに以下も成立する：

符号語長が $\lceil \log_2 (1/p_1) \rceil, \ldots, \lceil \log_2 (1/p_n) \rceil$ である瞬時符号は存在する。
任意のこのような符号は $H^{(2)} (p) + 1$ よりも真に短い平均符号語長を持つ。

とりわけ $p$ が 1/2 の累乗で表現されるときは、$H^{(2)} (p)$ とちょうど一致する瞬時符号をいつでも見つけられる。一般には必ずしもそうではないけども、まあ大抵の場合は似たような状態になる、というのが上の定理で述べられていること。

気になるのは、この瞬時符号を見つけるためのアルゴリズム。そのアルゴリズムは証明の中で語られるが、アイディアはすごくシンプル。$\sum_{i=1}^{n} (1/2)^{L_i} \leq 1$ であるから、区間[0, 1]を $n$ 個の区間に分割する。その区間のうち、$p_i$ に対応する区間の長さが $(1/2)^{L_i}$ となる、交わらない区間を考えることができる。ある一つの区間に注目したときに、そこから任意の元を選び、それを二進数展開すると、同じ区間に属する元は、必ず先頭数文字が同じになる。その数文字を符号とすればよい。こうやって選んだ符号は瞬時符号になる。なぜなら、逆に選んだ元が瞬時符号になっていないならば、その被った元と同じ区間に属することになって、これは前提と矛盾するから。