エロン・リンデンシュトラウスが、平均次元、アナログ符号化、リスト復号、帯域幅、レート歪みといった概念を、位相力学系と情報理論の接点から丁寧に説明する講演である。次元の被覆による定義から出発し、シフト空間、位相エントロピー、シャノンのレート歪み理論、帯域制限信号空間、マーカー性質、埋め込みとリスト復号の定理へと進み、これらがどのように平均次元と結びつくかを解説する内容である。
導入と講演の狙い
では始めましょうか。みなさん、おはようございます。今日は月曜日ですが、Alon による火曜講演です。こういう場を持てるのは私たちにとってうれしいことです。いろいろな分野の人に、別のセミナーで話してもらえるからです。アナログ符号化、リスト復号、帯域幅、平均次元。私たちの多くは、このあたりをそこまでよく知っているわけではないと思います。Alon は私たちの質問にも辛抱強く答えてくれると思うので、理解をはっきりさせるために、できるだけたくさん質問してください。それから、要旨にはもう一つ重要なことが書かれていました。
では、始めます。
基本的に、私の目標はかなり控えめです。最後までうまくやれるかどうかは分かりませんが、私の狙いは、これらの言葉を丁寧に説明することです。そして、これらの言葉を説明していく中で、それらの間の関係も説明できればと思っています。最後から始めるつもりでした。いや、上から始めます。では、平均次元について話しましょう。ただ、本当に最後から始めたいなら、まずは次元について話すべきですね。標準的なものですが、次元について話します。
次元の被覆による定義
空間 X を考えます。話を簡単にするため、X はコンパクトで、よい空間、つまりよい可距化空間だとします。ただし、今のところ本当に距離を入れたいかは分かりません。
何か具体例を念頭に置けますか。RD のようなものですか。
はい、それで十分具体的です。かなりよい例です。では、これらのコンパクトな例を考えましょう。
定義として、X の次元とは、もちろんこれは位相次元の被覆による定義ですが、任意の開被覆に対して、コンパクト空間について話しているので有限開被覆を取れるとして、その細分被覆を見つけられ、重複度が d 以下になる、というものです。
ここで重複度というのは、どの点も d + 1 個より多くの集合には属さない、という意味です。これが次元の定義の一つです。初めて見ると、これがどう次元と関係しているのか不思議に思うかもしれません。そこで、少し変形した形を示します。こちらの方が扱いやすいです。
さて、ここで本当の問題にぶつかります。次元と距離の両方を d で表したいのです。でも、そうしないと自分が混乱するので、そのままにします。きっと混乱するのでうまくいかない気もしますが、小文字の d が二つ出てきます。一つは距離で、もう一つは次元です。分からなくなったら質問してください。完全に同値です。
最初にこの定義から始めたのは、一つには標準的な定義だからで、もう一つには、これが距離に依存しないという点が見えるからです。そこで今、X 上に距離 d を取ります。
X の次元が高々 d であるとは、任意の正の ε に対して、d 次元以下の単体複体で、精度 ε までこれをモデル化できることを言います。
これはいくつかの解釈が可能かもしれません。より形式的に言えば、任意の ε に対して、ある単体複体と連続写像を取れる、ということです。
単体複体というのは、いろいろな三角形、四面体、点などを貼り合わせたものです。そこにはいろいろな組合せ的情報があります。その組合せ的情報を忘れて、自然な位相を持つ点集合としてだけ考えたものを、絶対値記号で表します。点たちは R の中に置かれていると思ってもよいです。いや、これはたぶん望ましくありませんね。
グラフなら、予定していなくても話してよいものだと思います。ただ、この二本の線をグラフに置いたとき、それはあまり充実したものではありません。ともかく、三角形がつながっていて、それぞれの三角形には自然な位相があり、私は点だけを見て組合せ構造を忘れる、ということです。
標準的な用語が何なのか確認しようとしましたが、あまりはっきりしません。合っているとよいのですが。
定義の終わりは何ですか。定義の最後はどうなりますか。
はい。連続写像であって、任意の点について、その点の逆像の直径が高々 ε になる、ということです。
単体複体の点の逆像の直径が高々 ε です。
つまり、単射ではありません。単射ではないけれど、ある意味では全射的です。いや、S への全射ではありません。ただ、十分に大きく、ε 以上離れた点を区別できる、ということです。
もしかすると、私の空間全体が一点で、すべてを一点に写すだけかもしれません。それならそれで構いません。
いや、すみません。仮定していません。つまり、次元の定義を見落としているということです。たぶんよい形で質問されていますね。試されているわけですが、それはよいことです。
この概念は、実は無限次元の場合でも意味を持ちます。定義として、wε は、ε の解像度まで捉えられる最小の単体複体の次元です。
そこには何と書いてありますか。W ですか。
W(X, d, ε) です。ここで d は距離です。解像度 ε までに捉えられる次元の量です。眼鏡を外すと、たぶん 10cm か 10cm くらい離れているものしか区別できません。眼鏡なしではどれだけの次元が見えているのでしょうか。その W は何でしょうか。分かりませんが、水の柱みたいなものなので大丈夫です。
いや、ここでの d は距離です。ここでの b は距離で、ε は精度です。あまり単純すぎるものにはしたくないのです。
残念ながら、これからだんだん複雑になります。たとえば誰かが JPEG をくれたとして、それを符号化したいとします。その符号化がどれだけよいかを測る距離として何を使うべきかは明らかですか。明らかではありません。あなたにとっても、私にとっても、どの距離を使うべきかは明らかではありません。つまり、ε までモデル化する単体複体の最小次元を考えるわけです。
そしてもちろん、私の空間の次元が高々 d であるとは、ε を 0 に近づけたときのこの W が高々 d である、ということです。明らかにこれは単調に増える量になります。
これは、先ほど言ったことを言い換えているだけです。
立方体の例と次元の下限
では例を取りましょう。複雑なことはしないと約束します。例は単なる立方体です。そして距離を定義する必要があります。
d(x, y) = ||x – y||∞ とします。これが私にとって一番便利です。
このとき、W(X, d, ε) は d に等しくなります。ここで ε は 0 より大きく 1 より小さいとします。
明らかに立方体を三角形分割できます。したがって、X を精度 ε でモデル化するものとして恒等写像を取ればよいことは明らかです。私は単体複体と胞体複体を区別することについて少し雑に扱います。二つの単体複体を掛け合わせると本当の意味では単体複体ではありません。しかし、意味するものは分かると思います。単体複体、あるいは胞体複体のようなものです。
いずれにせよ、d 以下であることは明らかです。そして d 以上であることは、実は非自明です。大きな事実ではありませんが、ほとんどブラウアーの不動点定理と同値のものです。
RD の次元が 0 ではない、少なくとも 1 ではない、いや 0 ではないかもしれませんが、d – 1 にはできない、ということを示すには、何らかの非自明な位相的入力が必要です。ですから、ε が厳密に 1 より小さい限り、低い次元ではモデル化できません。
ε が 0 に近づくとこれが発散するような例はありますか。
もちろんです。それがここで話したいことです。
このブラウアーの不動点定理がどう出てくるのか、少しだけ説明してもらえますか。
立方体の各面に対して頂点を一つ置きます。少なくとも私にとって分かりやすいのは、次のようなよく似た主張を考えることです。
U を d 次元立方体の開被覆とします。どの開集合も互いに向かい合う二つの面を同時には交わらないとします。すると、少なくとも d + 1 個の集合に属する点が存在します。
その関係は見えると思います。やることとしては、各開集合に対して、立方体のある頂点を固定します。その開集合が交わるすべての面を含むような角を選ぶわけです。そして、この開被覆に従属する単位の分割を取り、立方体の任意の点を、それを含む面に対応する要素の線形結合に写すことができます。
そして、もし各点が高々 d 個の集合でしか覆われていないなら、この写像の像は d – 1 次元の空間の合併の上に来ることになります。すると抜けている点が存在し、それを使ってすべてを境界へ射影する、ということになります。そういうタイプの議論です。
ボルスーク・ウラムの定理はもっと立派なものです。もっと洗練された道具で、後で出てくるでしょう。これはそれより単純だと思います。ブラウアーよりも単純です。
理解できなかったのですが。
たぶん、同値な補題の形があると思います。いや、それを証明するものが同値です。少なくともこの変種のどれかはそうだと思います。
自分で理解しておくことは重要ですか。
はい、これは受け入れておくことが重要です。
分かりました。真面目に聞いています。ただ、この例はランダムに選んだわけではありません。
平均次元と位相力学系
では次に進みます。
この講演では二人の権威を引用します。一人はグロモフで、もう一人はシャノンです。私が何かはグロモフまたはシャノンによって導入されたと言ったとき、それがなぜ重要なのかを説明する責任は私にはありません。彼らは権威ですから。グロモフは時々ここに来ます。聞きたければ本人に聞けます。
今度は X はまたコンパクトで、よい可距化空間です。そして T は X から X への写像です。ここでは無限次元空間に関心があります。これは力学系と呼ばれます。位相力学系です。
これはどちらかというと電気工学に関係していますし、いろいろな方法にも現れます。フローについても話します。フローとは基本的に次のようなものです。空間 X があって、g_t という R 作用があります。つまり g_t は空間 X から X への写像です。
正当化に使う人物リストに入れるなら、この時点で書いていた人の一人はフローを力学系と呼んでいて、かなり混乱しました。フローという言葉が意味していたのは、今日の講演でおもしろい点の一つは、実はこの講演がソースについては何も扱わないということです。Benji は登場します。
これは単に写像、つまり連続写像です。R から X への連続写像のようなものです。少し変な書き方ですが、まあこれが私の書き方です。R × X から X への連続写像で、もちろん g は恒等写像を満たし、g_t g_s = g_{t+s} です。
左辺の前に g が抜けていますよ。g(tx) = という形になっています。
等号がありますね。左辺に g が必要です。
関数を定義しているわけですね。x を見ています。
はい、矢印にするか、x を選ぶかですね。その通りです。
さて、私の空間に距離 d があるとき、新しい定義をします。
W(X, d, ε, N) を定義します。距離 d、ε、そしてもう一つのパラメータ N を与えます。これは、距離 d_N に関して、精度 ε でモデル化する単体複体の最小次元です。ここで d_N は、i = 0 から N – 1 までの最大値として、T^i x と T^i y の距離を取ったものです。
力学系があるとき、点が近いことについてよりうるさくなる方法は二つあります。単に近い点を取ることもできますし、長い時間近いままであることを要求することもできます。
この上の部分は残しておきます。1時間以内にレート歪みに到達できれば、そのあと少し休憩を取るつもりです。ただ、進み具合を見ましょう。
ここで平均次元を定義できます。その前に一つ注意したいことがあります。W(X, d, ε, N + M) は、W(X, d, ε, N) + W(X, d, ε, M) 以下です。
なぜでしょうか。K_1 と、X から K_1 の点集合への写像 f_1 が、距離 d_N に関して ε モデルになっているとします。また K_2 と f_2 が、距離 d_M に関して ε モデルになっているとします。そして明らかに、K_1 の次元は最小、K_2 の次元も最小だとしておきます。必要な変更を加えればよいです。
すると K_1 × K_2 は、写像 x を f_1(x) と f_2(T^N x) の組に送ることで、d_{N+M} に関して ε モデルになります。先ほど言ったように、これは本当には単体複体ではなく胞体複体です。実際、私は胞体で扱う方が好きです。
このような劣加法性を見ると、私の骨の中で何かがうずきます。N を無限大にしたときに W(ε, N) を N で割った極限を見たくなるわけです。これはもちろん劣加法性により下限と等しくなります。そして ε を 0 に近づけた極限を取ります。これを平均次元と呼びます。
この定義で最初に出てくる言葉です。誰かが ε を固定しても変わらないことの証明をくれるのですか。
いや、そこがポイントです。ε は変わりません。全体がそういうふうに作られています。
記号の ε は、つまりこれはどんな意味でも等長ではありません。しかし、これが ε モデルであるということは、x と y が、T を k 回適用した後、k が大文字 N から大文字 N + n の間で近ければ、近いままであるという意味です。それがまさに必要なことです。
定義は、ε が正確に合うように設定されています。すべてが正しい形に設定されています。
ああ、無限大ノルムを見ているからですね。
そうです。この距離を見ています。
空間が低次元のものにつぶされている、という直感で考えるのはよいですか。
よい直感だと思います。後で例を出します。
ただ一つ言いたいことがあります。X, g_t がフローなら、平均次元は、g_1 を取って得るものと、任意の時刻 T による写像で得るものを、適切に時刻で割ったものが同じになります。ここではフローとしてではなく、一つの写像として、点 x を t_1 時間後の x に送る写像を考えます。これはまさにこの定義です。しかし T_2 についてもできるはずです。任意の時刻でできます。
そして t_1, t_2 が 0 でないとき、平均次元を |t_1| や |t_2| で割ったものが同じになる、ということが成り立ちます。この共通値、つまり g_1 に関する平均次元を、フローの平均次元と呼ぶことにします。
有限次元系と無限次元シフトの例
例に行きましょう。
力学系の教科書を開いて、フロー、猫写像などの例を見ると、どれも有限次元です。そして X の次元が有限なら平均次元は 0 です。なぜなら、任意の ε と N に対して、空間の次元で常に上から抑えられるからです。空間の次元で任意に高精度にモデル化できますし、固定された数を N で割れば 0 になります。したがって有限次元の力学系はすべて平均次元 0 です。
そこで無限次元系を取りましょう。ここで私が考えられる一番簡単なもの、あるいは少し洒落たものにしますが、単なる立方体の Z 乗です。そこに写像を入れます。写像は何でしょうか。
σ(x) を取ります。x は x_i の列で、それぞれの x_i は立方体の中にあります。σ(x) の i 番目の成分を x_{i+1} とします。これがシフトです。慣れ親しんだシフトですが、アルファベットが残念ながら、あるいは幸いにも非可算です。しかも単に非可算なだけではなく、位相を持っています。
距離を定義する必要があります。
はい、すでに謝っておきます。もう一度は謝りませんが、距離を d と呼びます。
何を取るかはあまり重要ではありませんが、もしかすると重要かもしれません。たとえば、各座標の距離に指数的に減衰する重みを付けて足し合わせるような距離を取ります。
この例では、立方体の次元を 1 にしない理由はありますか。何か大きな数であることが重要ですか。
いや、ただ説明上、1 にする利点もありますし、d にする利点もあります。どちらにするかというだけです。d の部分は無視してもらって構いません。
この距離は特に、0 番目の座標の距離以上です。
そこで、この距離によって時刻 N までに捉えられる次元を見ると、少なくとも、d_N に関して直径が ε 以下であるということは、最初の N 個の座標が近いことを意味します。大きな空間から何らかの複体への写像があり、その任意の点の逆像が、最初の N 座標について l∞ ノルムで高々 ε だけしか離れないことになります。
つまり、最初の補題によって、この W は下からだいたい N × d で抑えられます。というのも、この条件は、d_N(x, y) < ε なら i = 0 から N – 1 まで各座標について ||x_i – y_i||∞ < ε が成り立つことを含意するからです。
この d_N は、私が説明したものです。力学的エントロピー、つまり時刻 0 から N までの作用の最大値です。力学を 0 回から N – 1 回適用するわけです。d_N が ε 以下なら、座標 0 から N – 1 までが互いに ε 以内にあります。
すみません、大文字 D とは何ですか。
ここにあるものです。これは最大値です。σ^k x と σ^k y の距離を、k が 0 から N の間で取った最大値です。
N で正規化しないのですか。
正規化しません。最大値です。ここで正規化するのは自然ではありません。後で正規化します。
書かれているものは何ですか。
もし距離がここでの無限大ノルムで、x に関しては d 個の座標だけなら、そうです。
下線を引いたものは小さな d 個の列だと思ってください。それぞれの座標自体です。
もしかすると、最初から d を出さない方がよかったかもしれません。とはいえ、この W はだいたい N d かそれに近いものの間にあります。そして N で割ると次元 d が得られます。
では、今話したかった点にたどり着きます。
このほかの方向で、対数を伴う評価はどう得るのですか。
基本的には、尾の部分は常に小さくなるようにしておくわけです。余分な座標が少しあっても、その効果はすべて、もし x と y が時刻 -t から t の間で同じなら、距離は 2^{-t} 程度になります。指数的に減衰する絶対値を取っているからです。
負の方も絶対値を取るのですね。
はい、その通りです。
これはいつも授業で悩む点です。エントロピーを定義するとき、私はいつも log(1/ε) を取ります。ただここでは、もしかすると人々が文句を言うかもしれないと思いました。私の考えでは log(1/ε) です。絶対値は好きではありませんが、まあいいでしょう。
したがって、この立方体のシフトの平均次元は d です。上界と下界を取り、N で割って極限を取ると、正確に d になります。
これは、指数的減衰ではなく、0 に近づく任意の減衰を取っても同じままですか。1/ε にはならないかもしれませんが。
答えははいです。平均次元は位相の不変量です。同値な距離なら何を取っても同じ答えになります。
はい、まさに同値になります。そして同じ平均次元を与えます。ただしすぐ後で見るように、距離が役割を果たす理由があります。私が可距化空間について話し、距離を固定しないことにこだわったのは、単なる個人的な秘密のせいではありません。すぐに距離が役割を果たします。
ですから、私の空間の平均次元は d です。
位相エントロピーと平均次元
もう一つ、あまり明らかではないことがあります。これが何であるかを定義しますが、ゆっくりと歪みに近づいていきます。エントロピー・チャンネルはすぐ出てくると言いました。位相エントロピーが有限なら平均次元は 0 です。これは明らかではありません。Benji Weiss と私が気づいたことです。位相エントロピーが有限であることは、平均次元が 0 であることを意味します。
その理由を説明してみます。その前に、別の量を説明する必要があります。
立方体であることは本当に重要ではなかったのですね。任意の積空間でよいのですか。
任意の有限次元空間でいいです。ただし問題があります。C の場合を除けば、次元のどの定義も、積に対してそれほどよく振る舞うわけではありません。コンパクト可距化空間を見て積を取ると、次元は次元の和以下ですが、より小さくなることがあります。
ただし任意の単体複体を取れます。立方体に限りません。そこで今後のために、次の例を見ておいてほしいです。これを Y と呼びます。なぜ Y と呼ぶかというと、空間 y を取るからです。ここで y は文字ではなく、4 つの頂点と 3 つの辺を持つこのグラフです。このシフトを見ると、これも平均次元 1 を持ちます。
任意の次元 d の単体複体、あるいはよい空間を取れます。ただしこの特定の例は後で役割を果たします。
この距離はグラフ距離ですか。
いいえ、幾何的なグラフです。距離は長さから来る距離です。これはリスト復号のところで出てきます。
さて、空間を精度 ε でモデル化するもう一つの方法として、組合せ的にサンプリングしようとすることができます。N(X, d, ε) を、ε ネットに必要な最小点数として定義します。つまり、すべての点がその集合のどれかの点から ε 以内にあることが保証されるような点集合の最小個数です。
またしても申し訳ないですが、d を二回使い、N も二回使っています。ただ分かりやすくするためです。力学系では、d_N という距離に関する ε ネットの最小数を考えます。d_N は i = 0 から N までの距離の最大値です。
すると、これにも同様の劣加法性があります。時刻 N までの ε ネットと時刻 M までの ε ネットがあれば、その積を取り、正しい形で T^N によってシフトすれば、より長い時間に対する ε ネットを得られます。
これを見ると、劣加法的関数を見たときとほとんど同じくらい興奮します。そこで ε を固定し、1/N × log N(X, d_N, ε) の極限を見ることにします。これを s(ε) と呼びます。そして空間のエントロピーは、ε を 0 に近づけた極限です。これが位相エントロピーです。
時間が少し押しているので、エントロピーが有限なら平均次元が 0 になる理由をあまり詳しくは説明しません。これは本当にヒントだけです。
ε を固定し、X からある複体 K への ε モデル f を取ります。すると明らかに、K の N 乗は、最大距離に関して ε モデルになります。したがって連続写像が得られます。つまり X から K^N への連続写像で、モデルを実現します。
一方で、エントロピーが有限なら、N が大きいとき、空間をだいたい 2^{(h+η)N} 個程度の小さな球で覆えます。この写像のもとで、そうした小さな球は K^N の小さな球に写ります。したがって X の像は、比較的少数の小さな球の中に含まれます。
すると何が起こるかというと、K^N の中の単体で、その内部に X の像によって使われていない点があるようなものは、その単体を破裂させることができます。存在しない点から単体の辺へすべてを射影できるからです。そして点が非常に少ないので、かなり低い次元まで単体を破裂させることができます。これがアイデアです。
像に含まれない点を持つ単体を考えるわけです。誰かが、モデルを全射と仮定しているのかと聞きました。私は仮定していません。そしてまさに、写っていない点を使ってモデルを簡単化しているのです。
これは何倍ですか。
d_N 距離に関する ε 球です。
実際には積ではありませんが、時間方向にシフトされたものです。
これで左に書いたものの証明が見えたと思います。実際に定量化すれば、平均次元は、ε を 0 に近づけたときのある量で上から抑えられることが分かります。
先ほど上で書いた s(ε) だけを取って極限を取ればエントロピーになりますが、実際にはそれを log(1/ε) で割ります。これはもはや存在するとは限りません。増えるかもしれないし減るかもしれません。この量の下極限が平均次元を上から抑えます。そしてこれは距離に強く依存します。
たとえば私が定義した指数的に減衰する距離を持つ立方体を取ると、この量は実際に平均次元に収束します。しかし平均次元は、無限エントロピーの系に意味のある量を与えます。どの距離を使っても、スケール ε での複雑さを log ε で割ったものに対する下界を与えます。
私がヒルベルト立方体のために与えたきれいな距離を使えば、実際に等号になります。n^2 で減衰させるような距離を使うと、右辺の値はより大きくなります。間違った距離を使うと、悪い下界を得ることになります。半分だけのようなものです。
シャノンエントロピーとコルモゴロフ・シナイエントロピー
では、ゆっくりレート歪みに向かいましょう。
私はタイトルと要旨に書いたほとんどすべてについて心配していましたが、一つだけ安心していたものがあります。それがシャノンエントロピーです。では、これをシャノンエントロピーに関係づけてみましょう。正確にはシャノンエントロピーではなく、コルモゴロフ・シナイエントロピーですが、基本的には同じ話です。
シャノンエントロピーは確率過程についてのものです。確率過程、たとえば有限状態の確率過程です。可算でもよいですが、ここでは有限状態にしましょう。
では、私の系からどうやって確率過程を作るのでしょうか。コンパクト距離空間 X と T があります。これを有限状態の確率過程にするにはどうすればよいでしょうか。
基本的には二つのものを加える必要があります。一つは測度、確率測度 μ です。これは不変である必要があります。つまり押し出しが μ に等しいということです。もう一つは X の分割です。
普通、分割というと部分集合の族を取りますが、ここでは過程的な構造を強調したいので、空間から有限集合への関数として考えています。
このデータがあれば、エントロピーを定義できます。シャノンエントロピーを使って、P(x), P(Tx), P(T^2x), …, P(T^{n-1}x) という確率変数列のエントロピーを取り、それを n で割った極限を取ります。ここで確率測度はもちろん μ です。
コルモゴロフの偉大な洞察、あるいはコルモゴロフ・シナイエントロピーの洞察は、すべての分割について上限を取ると、力学系の不変量が得られるということです。力学系にとって意味のある数になります。それを計算すれば、空間と不変測度のエントロピーが得られます。
分割の部分の数は固定ですか。
分割 P は固定です。
そうです。ここでは上限を取ります。つまり、実際にはどんどん細かい分割を取るかもしれません。ただし実用上は定理があって、エントロピーが有限なら、P はエントロピー程度の大きさのアルファベットを持つものにできます。
これはアルファベットのようなものですか。
はい、その通りです。
情報理論で話しているこのものは、実際に関係があります。ただ、たとえばエルゴード的なフロー、測地フローがあるとき、取るべき明らかな分割はありません。ですからなぜ、という話になります。
非常によく振る舞うものを取ります。特別な場合には、エントロピーで力学系を分類するすばらしい定理があると言うべきでしょう。そういう話です。
ただ、私にはすべての言葉を一通り通るという非常に野心的な目標があり、ここまででようやくレート歪みの定義の半分まで来ました。
そして、美しい定理である変分原理があります。これは、力学系の位相エントロピーが、すべての測度 μ についてのコルモゴロフ・シナイエントロピーの上限に等しい、というものです。
これは美しい主張です。そしてまた大きな問題として、その上限が達成されるのはいつか、という問題があります。最大エントロピー測度を見つけられるか。空間上の確率過程で、この量を実際に実現するものを見つけられるか。これも美しい定理です。
名前を忘れてしまいました。西側では多くの……いや、ロシアで、実はそこまで有名ではない人々だったと思います。時期は 1970 年代、1980 年代、あるいは 1960 年代から 1970 年代かもしれません。Adler が位相エントロピーを定義したと思います。Adler は確かに関わっていました。Adler はその一人でした。
その測度が一意であるのはどれくらい典型的ですか。
一意性は複雑な問題です。ただ、少なくとも最大エントロピー測度が存在することについては、有限次元の力学系で写像が C∞ なら真です。しかし C^n、有限の n では、どれほど大きくても、必ずしも最大測度があるとは限りません。
測度が一意であることはかなり非典型的だと思います。非常に非典型的です。
ただ、今それに触れたので言うと、系が一意エルゴード的であるとは、不変測度が一つだけ存在することを言います。これはかなりまれです。ただし、任意の抽象的な測度保存系は、位相力学系の唯一の不変測度として実現できます。位相的にはまれです。
そしてもう一つ非自明な事実があります。これも Benji と私が示したことですが、その平均次元は 0 です。
レート歪みの定義
では歪みについて話しましょう。シャノンが情報理論を作ったとき、それはデジタル革命の前でした。ですから彼はデジタル伝送以上に、おそらくアナログ伝送についても心配していました。
彼は、たとえば音声録音があるとして、この音声を符号化するには 1 秒あたり何ビットの情報が必要なのかを考えていました。クラシック音楽の録音があるとして、それを圧縮したい。コンサート 1 分あたりどれだけの情報ビットが必要なのか、ということです。
シャノンは、コンパクト距離空間、変換、距離の概念、そして不変測度を持っていました。これがシャノンの使っていたものです。そして、この対象がどれだけの情報を含んでいるかを見ようとしていました。もちろん短い答えは、エントロピーは無限大になるというものです。なぜなら、無限に多くのビットを持つからです。
しかし彼は次のように定義しました。二つの確率変数の相互情報量を考えます。確率変数のエントロピーについては話しました。二つの確率変数 X と Y の相互情報量は、X と Y が有限個の値しか取らない場合、X のエントロピーと Y のエントロピーの和から、(X, Y) のエントロピーを引いたものとして定義されます。つまり X と Y が共有している情報量です。
X と Y が有限個の値を取るわけでない場合には、X と Y のすべての分割について上限を取ります。すると同様に定義できます。もちろん X と Y が無限個の値を取る場合、この量は無限大になり得ます。それでも意味のある形で定義できます。そして X と Y のエントロピーが等しい場合でも、この量は有限でよく定義された量になることがあります。
ここでレート歪みを定義します。そのあと 5 分休憩を取り、続けます。
この x, t の ε モデルとは、確率空間と確率変数 X, Y_0, Y_1, …, Y_{n-1} のことです。X は確率測度 μ に従って分布し、Y_i は X に ε 近い、という条件を満たします。今回は上限ノルムは取りません。平均ノルムを取ります。上限ノルムを取ることもできましたが、シャノンは平均ノルムを取りました。先ほど言ったように、シャノンとグロモフとは議論しません。彼らはただ来て、これは神秘的な空間だ、ということです。そして Y は何かの軌道である必要はありません。
そしてレート歪み R_μ(ε, n) を、X と Y_0, …, Y_{n-1} の間の相互情報量の下限として定義します。ただし、X の n ステップの ε モデル全体にわたって下限を取ります。これは基本的に、距離 d_N、あるいは d_N ではなくこのハミング平均距離に関して気にするとき、過程の中にどれだけの情報があるかを測っています。
Y たちはどう考えればよいのですか。今までモデルは複体でしたよね。
はい。多くの確率変数です。以前の一つのモデルは単体複体でした。もう一つのモデルは ε ネットという有限集合でした。今度は別のモデルです。
例を挙げましょう。私のお気に入りの系と距離、測度を取ります。測度は各成分で独立なルベーグ測度を取るのがよいでしょう。このときよい取り方の一つは、Y_i を座標の ε 切り捨てにすることです。
つまり X をランダムに取り、Y_i を実際に X の関数として取ります。Y_i は X_i の ε 切り捨てになります。このとき相互情報量は基本的に log(1/ε) × n のようなものになります。
ここで X_i は σ^i X の成分です。これが大きな絵にどう収まるかです。
質問されて話が逸れました。少し時間を超えてもよいでしょうか。休憩を入れればよいですか。
時々は時間を超えてもよいです。
では、よかったです。
ここで、Tsukamoto と私の定理があります。任意の X について、平均次元はある上限で抑えられます。劣加法性のおかげで、R_μ(ε, n)/n の n を無限大にした極限は存在します。これはシャノンのよい定義から従います。
平均次元は、すべての不変測度 μ についての上限を取り、ε を 0 に近づけたときの R_μ(ε)/log(1/ε) の上限によって抑えられます。
明らかに、左にあるものと、先ほど Benji との定理で得たものを比較するはずですね。
これから平均次元の上界を説明するのですか。
はい、これが平均次元です。左、左下を見てください。
よい質問です。この数はこの数より小さくなります。
ただ、まだ言っていませんでしたが、もし私の系が時計を持つという意味でよいなら、休憩後にその意味を説明しますが、その場合には実際に、X, T の平均次元は、距離 d についての下限と、不変測度 μ についての上限によるこの量に等しい、と言えます。
そしてこれは意味のあることです。実際、上限が実現されるような距離を見つけることができます。ここでは ε を 0 に近づける極限の上限を置いても下限を置いてもよいです。極限が存在するとは言いませんが、下極限でも上極限でも、どちらでやっても構いません。
これは二重変分原理です。ある種のミニマックスです。量を最小化する距離を取り、量を最大化する測度を取ります。そしてこの式が実際に平均次元になります。したがって、シャノンのレート歪みは平均次元と非常に密接に結びついています。
ここではこれ以上進めません。これは休憩後の次の 30 分くらいで扱うことになります。
時計とマーカー性質
朝起きるとき、目覚まし時計の最も重要な機能はスヌーズ機能です。ボタンを押すと、次にまた鳴るまでいくらか時間があることが保証されます。そして、それがいつ鳴るかには上限があります。それがちょうど 5 分なのか 6 分なのかはそれほど重要ではありません。ただ、もう少し眠る時間が欲しいし、どこかの時点で必ず起こしてくれることを知りたいのです。私は自分の力学系にも同じことを望みます。
その時計を説明する必要があります。
受け入れられている名前は悪い名前ではありません。時刻マーク性質、あるいはマーカー性質です。任意の n に対して、開集合 U と N が存在して、次のように振る舞います。U, T^{-1}U, …, T^{-n}U が互いに交わらず、かつ U, T^{-1}U, …, T^{-N}U の和集合が全空間を覆う、ということです。
空間がコンパクトなので、この大文字 N を無視して無限まで取る、と言っても同じことです。
この性質を持つ系はたくさんあります。任意の極小系が例です。そして無限マーカーを持ちます。
最も単純で、最もきれいな例はオドメーターです。車の走行距離計のようなもので、ただし 2 進法です。望むなら 10 進法でもよいです。中の桁は、車が長く走るので増えていきます。
もし系が時計を持っていないなら、時計を与える方法があります。たとえば区間上のシフトは時計を持ちません。そうできないことを示せます。一つの方法は、単に系に時計を与えることです。では、系に時計を与えるとはどういう意味でしょうか。X が力学系で、Y, S が時計を持つ、つまりマーカー性質を持つなら、X × Y にその性質が乗ります。
これは現実的なことにも関係しています。伝送があって、受信機と送信機の間で、追加情報を渡さずに同期できるようにしたい、という話です。とにかく、そういうものです。
なぜ時間を測るためなのですか。
これが私のボタンを押す動作です。私は待ちます。つまり、x が U に入っているなら、Tx は U に入っていない。少なくとも n 回の間はスヌーズ状態です。そして高々大文字 N 回のうちに起こされることが保証されます。
帯域幅と帯域制限信号
次の言葉は帯域幅です。
シフト作用素が R 上ではこのマーカー性質を持たないと言いましたか。
私が言ったのは、区間シフトはそれを持たないということです。
一つ、マーカー性質が保証することがあります。マーカー性質はまったく無害な条件ではありません。それは系に周期点がないことを保証します。なぜなら、周期が小さい周期点は、集合 U をまったく避けるか、少なくともその周期の頻度で U に当たってしまうからです。よい指摘です。マーカー性質は周期点がないことを意味します。したがって、マーカー性質を持つ系を掛けることで、周期点を開いてしまうわけです。それが起きることです。
では帯域幅です。
ここでもシャノンについて話します。シャノン・ナイキストの定理ですね。シャノンはサンプリングについて話していますが、ここでは古典的な設定から少しずれます。
私の観点からは、L^2 信号について話すのは自然ではありません。新しい送信装置を手に入れたとして、その装置が送れるものが L^2 ノルムで制限されている、というわけではありません。現実世界で自然な評価、少なくとも私にとって自然な評価は L∞ 制限です。
そこで、ある空間を見ます。これは標準的な定義だと思います。関数 f は R から R または C への有界連続関数で、フーリエ変換の台が [-a/2, a/2] に含まれるものです。バンドの幅が a です。
私の記法では、関数 f のフーリエ変換は ∫ e^{2πi xξ} f(x) dx、あるいはマイナスを付けるかもしれません。もちろん、有界関数に対してこの積分をそのまま見るのは意味がありません。収束する理由がないからです。意味を与える必要があります。
意味を与える代わりに、別の形で定義します。分布の意味で、というようなことですが、それを避けて代替定義をします。
X は、ある帯域幅 α の関数で、整関数に拡張でき、かつ |f(z)| が C_f exp(π α |Im z|) のようなもので抑えられるものとします。定数は f に依存します。すべてを正しくするには虚部に π を掛ける必要があるかもしれません。
例として sin(πx) があります。これはよい例です。すべてを満たします。定数 C_f は 1 か 2 かもしれません。とにかく定数は確かにあります。そしてこの関数は整数で 0 になることに注意してください。これがシャノンに言及した理由です。
ここで新しい力学系、つまりフローを定義します。関数の空間があります。実はきれいな名前を用意していました。順番を迷っていたのですが、信号空間と呼んでもよいでしょう。これは関数の空間で、関数空間には自然なフローがあります。
σ_t(f) を、f(· + t) とします。これがフローです。
この空間で使いたくなる明らかな距離、というより明らかな位相があります。明らかな距離ではありません。そして命題は、この信号空間の平均次元が帯域幅 a に等しい、というものです。
基本的に、フローなので示す必要があることは、たとえば B を取ったときに、少なくとも一方向で、B が 1 より小さいなら、シフト σ_B に関する平均次元が高々 1 であることです。ここでは固定した B での写像を見ています。ドットを付けるべきですね。これはフローです。
示したいのはこれが高々 1 であることです。基本的に、N ステップのモデルが何かを言えます。単にサンプリングするだけです。f を、f(kB) たちに送ります。k は -L から N + L までです。L は ε に依存します。そして B が 1 からどれだけ離れているかにも依存します。
ポイントは、イェンセンの公式によって、整関数の大きな境界上での絶対値、中央の値、そして零点の位置が関係づけられることです。もし二つの関数がこれらすべての時刻で一致するなら、その差はこれらすべての時刻で零点を持ちます。そして、この仮定によって、円周上の絶対値を制御できます。つまり、大きな円の中に十分多くの零点があるなら、たとえば 0 での値は非常に小さくなければならない、ということを示せます。
公式から、たとえば |f| が ε 未満であることを得られます。ただし |f| はある指数成長で抑えられ、f(k) = 0 が一定範囲の k で成り立つ、という条件のもとです。この N は定数 C の値に依存しますが、そのようなことができます。これはイェンセンの公式です。
すると基本的に、k を -L から N + L まで取れば、時刻 0 から N の間での F の値を制御できます。つまり F の大きさを大きな区間で制御できます。
これは単にサンプリングを見直したものです。L^2 の文脈ではなく B 空間の文脈ですが、同じです。
逆方向に行きたいなら、基本的には、B が 1 より大きいときには任意の列を補間できる、という事実と密接に関係しています。任意の l∞ 列に対して、その値を取る帯域制限関数を見つけられます。
f(x) を、x_k sinc(x – k) の和のように考えてください。ここでは B = 1 を仮定しているかもしれません。ただし、これには収束しないという小さな問題があります。L^2 の場合と違って、厳密な不等式が必要です。δ を入れて sinc(x – k) のように考えるべきかもしれません。
そして、そのように任意に値を設定できるので、最初に書いた立方体の W 次元に関する補題と組み合わせることで、平均次元が少なくともこの値であることが分かります。これが反対側の不等式を与えます。したがって実際に等式です。
使う必要のある一番洗練された道具は正規族の議論です。
何を証明したのですか。
すばらしい質問です。ちょうど次に言いたかったことです。
私が言いたかったのは、帯域幅が 1 より大きいなら、この標準的な系、つまり立方体のシフトを帯域制限チャンネルの中に埋め込めるということです。ここで埋め込みとは、写像 I が単射で、I(σ_2 x) = σ_1 I(x) のように作用と両立しているという意味です。私は埋め込んでいるのです。
ここでは I は最良の記号ではないですね。使うつもりでしたが、この文脈では少し紛らわしいです。
さて、時計を系にどう与えるかという話をしました。Goodman と Tsukamoto の定理があります。もし系の次元が a/2 より小さく、帯域幅が明らかな量の 2 倍より大きいなら、同様の埋め込みが存在します。
埋め込み定理と平均次元の下限
平均次元の性質から、一般に系を埋め込めるなら、平均次元は帯域幅以下でなければなりません。任意の X, T について、X, T を帯域幅 a の信号空間に埋め込めるなら、平均次元は a 以下である必要があります。つまり、帯域幅は平均次元を収容するだけ十分に大きくなければなりません。
たとえば衛星があって、14 個の太陽フレアの強度を測っているとします。この測定を送信するのにどれだけの帯域幅が必要かを知りたい。条件は、伝送を連続にしたいということだけです。実際に行われるようなアナログ・デジタル変換、ビットの操作、そしてデジタルからアナログへ戻す変換はしたくありません。そういうことは常にいくらか誤差を導入します。それはしたくありません。連続的な同期をしたいのです。すると、少なくとも平均次元分の帯域幅が必要であることが保証されます。
そしておそらく、このレート歪みとの関係は、デジタルからアナログへの変換やアナログからデジタルへの変換を許したとしても、何らかの合理的な仮定のもとでは制限を与えるでしょう。
もし平均次元が a/2 より小さいなら、系を帯域幅 a の信号に埋め込めます。そしてこの 2 は鋭いです。
その例として、幾何的実現された Y 上のシフトを取り、時計を装備させます。これは明らかに多くの周期点を持つので、そのままではこのクラスの系ではありません。X, T がマーカー性質を持つなら、という仮定が必要です。
もし X, T がマーカー性質を持たないなら、たとえば単に正方形を X として、各点をそれ自身に送る写像を取ることができます。この平均次元は 0 です。しかし a が 2 より小さいなどの場合、埋め込むことができません。点が多すぎるからです。
つまり、つまらない反例を避けるためには何らかの仮定が必要だと言っているのです。そして、それほどつまらなくない最近の反例を避けるには、より強い仮定が必要です。
しかし系がマーカー性質を持っていれば、よいゼロを持つことを期待できます。平均次元が帯域幅の半分より小さければ、系を符号化できます。そして 2 は鋭いです。
この系を取ります。いまは自明な理由で、たとえばそれを区間上のシフトに埋め込めません。なぜなら、ここでは固定点が Y のように見え、Y を区間に写すことはほぼできないからです。
固定点が Y のように見えるとはどういう意味ですか。
この複雑な空間の中で、σX = X となる点 X を見ます。それは Y のコピー一つにすぎません。定数関数、定数列は、Y の一つのコピーです。
これに時計を装備します。つまり積を取ります。非常に単純な極小系、たとえばカウンター、オドメーターとの積を取ります。すると a が 2 より小さい信号空間には埋め込めません。ここで使うのは、基本的には空の中の PC、あるいは Borsuk 型のものです。
衛星は何を送信しているのですか。音楽ですか。
たとえば衛星が 7 個の検出器を持っているとしましょう。毎秒 7 個の数を測定します。そしてそれを地球に送信したい。特別な時刻構造があるわけではありません。シフトがあるだけです。もちろん、物理的な制約があって、データを測ること自体が複雑かもしれません。そしてデータについて何か知っていれば、帯域幅を節約できるかもしれません。
この方向では、すべての測定を待ってから送るのですか。ブロックの形ですね。
はい。ブロックで通信できるようにするためには、ブロックがいつ始まるのかを決められる必要があります。だからマーカー性質が必要なのです。まさにそのためです。平均次元はブロックについての情報を与えますが、連続的な伝送をどうにかしてブロックに分解しなければなりません。ブロックへの分け方が分からなければ、動かし方も分かりません。これが、なぜマーカー性質が必要なのかという数学的な説明です。
リスト復号と有限対一符号化
では、何を扱ったか見てみましょう。被覆の話はそこまでしていませんね。ここで、たぶん最も最近の定理を述べます。これは Tsukamoto の美しい定理です。2024 年、あるいは 2023 年かもしれません。私はそういう細かいことが得意ではありませんが、2024 年、もしかすると 2025 年としておきましょう。
平均次元を D と呼び、それが a より小さいとします。すると、空間から帯域幅 a の信号空間への有限対一写像 φ を見つけることができます。これは作用と絡み合います。つまりシフトと両立し、φ(Tx) = σ(φ(x)) です。
有限対一写像が平均次元に何をするかというのは少し非自明な問題です。有限対一写像なら平均次元を変えないのはかなり明らかに思えますが、完全に自明な証明ではありません。なぜなら、私は無知だったので聞いたことがなかったのですが、Michael による美しい定理があります。普通の次元で、k 次元空間から何かへの L 対一写像があると、像の次元は高々 k + L – 1 次元になります。つまり L 対一写像は、次元をちょうど L – 1 だけ増やし得るのです。ペアノ曲線のようなものを作ると、それは 2 対 1 で、次元の問題が出ます。
したがって、平均次元が有限対一写像でどう振る舞うかは完全に明らかではありません。おそらく平均次元を減らすことはできず、増やすこともできないと思いますが、完全には確信していません。
この有限性はどれだけ難しいかに依存します。基本的には 1 + 定数/(a – D)^2 のような量で有界です。a – D であってほしいと期待するかもしれませんが、a – D の二乗が出てきます。
これはまさにアナログリスト復号です。ここで、きっとこのセミナーで何度も見られてきたことが現れます。符号化に関して、何らかの愚かなエントロピー理論的限界があり、それには到達できない、おそらく到達できません。しかし符号化ではなくリスト符号化を使うことを認めれば、その限界まで到達できます。
では、なぜ 2 という因子が必要なのでしょうか。離散の場合の符号化における 2 という因子は、二進アルファベットから来るのでしょうか。
基本的に、アナログ・デジタル変換によって、小さな誤差を除けば、帯域制限関数を次のように考えることができます。私は、帯域幅の逆数より大きい頻度でサンプリングすれば信号を復元できると言いました。そして帯域幅の逆数より小さい頻度で何が起こるかを指定すれば、任意のものを構成できます。道徳的には、帯域幅を固定することは、ちょうど帯域幅の密度で値を固定することと同じです。
つまり、時間を帯域幅の逆数だけ進めるように変えれば、基本的にこの系は区間上のシフトのようなものになります。
ここで観察してください。もし X の次元が d なら、X は R^{2d+1} に埋め込めます。これはよく知られています。たとえば複体はグラフに埋め込めます。三次元空間には常に埋め込めますが、この平面埋め込みではできません。
ここで必要なのは位相的な埋め込みだけです。これもよく知られています。
例として、2k + 1 単体の 2 骨格か何かを取るのです。ただ、これは私にとってはあまりよくありません。しかしこの補題を使うと、この平面グラフ Y は 2 次元には埋め込めるが、1 次元には埋め込めないことを示せます。だからこれが働くのです。
そしてこれが、Y 上のシフトで作業するのがよい理由です。少なくとも系の 2 倍が必要になります。
この 2 はどこから来るのでしょうか。基本的には、次の理由から来ます。何らかの単体があって、その点を R^n にランダムに置くとします。異なる二つの単体が交わらないようにしたい。すると、典型的に交わらないためには、ちょうど 2d が n より小さい必要があります。Y の場合とまったく同じ理由です。
おそらくおもしろいのは、リスト符号化なしではより大きい帯域幅を使わなければならないことを説明しようとする位相が存在する、という事実です。
これはもっと直接的な関係かもしれません。離散形から連続形を推論できる、あるいは逆に連続形から離散形を推論できるようなものですか。
あり得ると思います。非常に並行して見えますよね。似た主張があります。そこで疑問に思うのは、もしかすると経験的に、何かを符号化するのに 2 倍のビットが必要になるような興味深い場合があり、それ以上よくできないという可能な証明があるかもしれない、ということです。もしそのような興味深い設定があるなら、この種の位相的アイデアが関係する可能性があります。確信はありません。
普通はもっと別の理由から来るのかもしれません。
何かコメントや質問はありますか。
サンプリング近似に関する質問
σ_a の空間に対して使った近似を思い出させてもらえますか。関数を何らかの点で近似したところです。
どうやって単体複体で近似したのか、という質問ですか。
すみません、どうやって単体複体で近似したのか、ということですね。
たぶん、たくさんの点を持っていて、それを使いたかった部分について話しているのだと思います。
はい。平均次元では、空間をモデル化するために使える単体複体の最小次元は何か、と言っていました。私が使った単体複体は、もちろん本当の単体複体ではなく、少しごまかしていました。立方体だったからです。しかしそれは適切な次元の立方体で、写像も驚くようなものではありませんでした。単に離散的な時刻集合でサンプリングするだけです。
では、他の点でどう補間されるという議論だったのですか。
関数があり、その関数についての上界があるとします。イェンセンの公式は、複素数の虚部に関する上界から関数の大きさを制御するものを与えてくれます。そしてその公式は、大きな円周上での関数の絶対値の対数の積分が、基本的には 0 での関数の値の対数と、零点に関する何かに等しい、ということを言います。
私はモデルの任意の一点の逆像が小さい直径を持つことを望んでいました。つまり、私の信号空間の二つの元がこのモデルのもとで同じ点に写るなら、その差はこれらすべてのサンプリング時刻で 0 を持つ、ということです。したがって多くの零点があります。それは右辺でよりよい評価を与えます。
これは、整関数で多くの零点を持つものは小さくなりたがる、という普通の事実です。そこで通常の公式を使います。複素解析について私が使い方を知っている数少ないものの一つです。
質問はありますか。
では、もう一度ありがとうございました。
コメント