複雑さとは何かを考える - 機械のように今を輝き、少女のようにここを定義せよ

背景と直感的理解
複雑さについての言葉的な定義
複雑さについての定量的な定義
応用可能性
- 複雑さへの対処
- 複雑さの活用
まとめ
- 2019/08 ラデマッハー複雑度についての訂正
参考文献
- 投稿当初より
- 2019/08/17 追記分

こんにちは。センケイです。

この記事は

日曜数学 Advent Calendar 2018 の

19日目です。

adventar.org

※ 2019/08/17 追記 ↓

ラデマッハー複雑度に関する記述が

全くの見当違いであったため、

その個所を修正しております。

申し訳ありませんでした。

※ 追記ここまで ↑

私はかつて自己組織化に関する研究をし、

今では機械学習の仕事をしています。

そんな経歴だからなのか、

下記のような疑問が

よく頭をよぎります。

社会の複雑さは定量化できるのか？

機械が人間をマネ出来ないのは、

作業の複雑さのせいなのか？

人間が生まれて以降、

地球上の複雑さは増しているのだろうか？

複雑さは情報量なのか？

（後で複雑さ ≠ 情報量と分かります。）

そんな複雑さに魅了されて

たんたんと調べていたところ、

分野毎に「複雑」という言葉が

様々に異なる用法で使われていると

少しずつ分かってきました。

しかし、それらの相互の関係や、

総括を詳しくかいたようなものは、

あまり見かけることが

できませんでした。

ないものは作る！の精神で、

ひとつのまとまった記事にできればと思い

これを書くに至りました。

背景と直感的理解

「芸術とはなにか。」

この「芸術」を筆頭に、

学術的な定義が志半ばにもかからわず

日常会話ではよく使用される概念、

そのような概念が、

この世の中に数多く存在します。

しかも大変不思議なことに、

それで会話が成り立つことも可能です。

「複雑（さ）」も、

その典型的なメンバーの１つでしょう。

日常会話において、

「ちょっと問題が複雑すぎるので

　時間がかかってるんだ。」

と言われれば、

確かにその因果関係について

納得できてしまいます。

さて、

複雑さとは一体何なのでしょうか。

『複雑さと共に暮らす』を見ると、

「テスラーの複雑性保存則」という

経験則が提案されています。

この経験則の例は、例えばこうです。

フロント、すなわち

web やアプリの画面を簡単にすると、

今度はバックエンドの複雑さが増える。

といった具合です。

さて、ここで、

「保存則」という表現が使われる

その理由が気になってきます。

これは、私たちの直感が「複雑さ」を

量的なもの、

すなわちスカラー値として

理解していることを

示唆しているように見えます。

（熱力学においてはスカラー値の下位集合として

　示量変数と示強変数の２種類が提示されます。

　複雑さが保存則を有しているのであれば、

　特にこのうち示量変数にあてはまるものと考えられます。）

さて、このような直感的な説明がある中、

具体的にどう定量化されるのか。

そしてなぜ我々（少なくとも自分）は

その答えを簡単に入手できていないのか。

そう考えていくと、複雑さが次第に、

予想以上に魅力的な概念なのではないかと

そう思えてきます。

また、近現代の特徴の１つとして

「複雑さが増大している」という

通念が成立している今、

実用上の喫緊の課題でもあります。

そんな「複雑さ」について、

この場を借りて、

既存の議論を多少でも整理しつつ、

「複雑さとは何か？」という魅力に

接近してみたいと思います。

さて、本題に入る前に、

複雑さを理解することの必要性を

もう少しだけ振り返るため、

機械学習にも少し触れます。

（一応、本編に関係する要素でもあります。）

日々仕事で

機械学習を開発している身としては、

人工知能の汎用化を考えることに

もちろん魅了されます。

その中で、下記のような

疑問が浮かび上がってきます。

「人工知能は何をしているのか？」

「人工知能は複雑さを圧縮しているのか？」

あるいは、

「人工知能が人間より汎用的でないのは

　なぜなのか？」

「その理由は、処理可能な複雑さが

　まだ小さいためではないのか？」

といった具合に。

直感的に明らかに複雑さが小さければ、

確かに既存の機械学習でも

十分に回答できているように見えます。

この直感は、

機械学習の能力の限界が

複雑さによって定められていると

示唆して見えてきます。

果たして機械学習と複雑さは

どのように、どれほど

関係を持っているのか。

この問いは、

機械学習を取り巻く社会の変化、

あるいは自分の仕事、

どちらの関心においても、

もはや素通りできない問いだ、と

そのように感じられます。

さて、長くなりましたが、

そろそろ本論に入りたいと思います。

その前に最後に一言だけ。

議論を整理するとは書きましたが、

もちろん、

既存のあらゆる議論を整理した内容には

遠く及びません。

そればかりでなく、

現役で論文を執筆している研究者ではない

野良の個人による記事であり、

自分の興味に偏った内容であること、

予めご了承いただけると幸いです。

複雑さについての言葉的な定義

複雑さの既存の議論を顧みるにあたり、

強力な助っ人になる論文をまず

２つ挙げたいと思います。

それが

Prokopenko et al. (2009) と、

Fernandez et al. (2013) です。

Prokopenko et al. (2009) の３章は、

複雑なシステムを理解する目的に

付随する形ではありますが、

複雑さの既存の議論について

概要を記述しています。

複雑さ[と]は、以下の点に基づいて、

複雑なシステムの難易度を

捕捉しようとする[ものである]。

・記述に必要な情報の総量。

・記述に要する時間。

・系の大きさ。

・構成要素の数。

・相反する束縛の数。

・埋め込まれた次元の数。

いっぽう、

Fernandez et al. (2013) の 3.3 は

Lopez-Ruiz et al. (1995) を引用し

手短にこう述べています。

複雑さ C は、

変化（カオス）と安定（秩序）の

間にある。

こうした複雑さに対する

既存の共通認識を再定式化し、

定量化の仕方を提案したのが、

上記の Prokopenko et al. (2009) や、

Fernandez et al. (2013) の

仕事と言えるでしょう。

2010 年前後になってなお、

既往の定式化が林立していることを前提に

こうして再定式化がなされ、

（私が探す限り）

以降目立った議論があまりないため、

まだまだ複雑さの定量化は

発展途上である可能性が高そうです。

すなわち、

「複雑さとは何か」という問いに

この記事内で答えることが

不可能という結論に

なってしまいます。

が、気を落とさずに、

このことを前提としたうえで、

両論文の上記の整理および

指標の提案内容を

これから見ていきましょう。

まず、上記の言葉による定義ですが、

特にカオスと秩序の間、という議論は

直感にそぐうように思います。

ただ、

引用箇所がたまたまそうなだけかも

しれませんが・・・

変化≒カオス、安定≒秩序という見方は

少し大雑把に過ぎるように思います。

それに、ランダムによる無秩序、

時間変化、そして決定論的カオスは

互いに区別すべきとも思います。

そこで以下では、変化≒カオスの所を、

「無秩序」という言葉に置き換えてみます。

まとめると、

複雑さは完全な秩序と完全な無秩序の

間にある。

このようにまとめることで、

のちの議論の見通しが良くなると

思います。

さて、完全な秩序と完全な無秩序、

これらがともに複雑でないことは

何となく理解できます。

完全なに無秩序については、

例えば、砂浜の砂の配置がいかに

高い自由度をもっていて、

観測のシャノン情報量が高かろうと・・・

高度なシステムや社会ほどに

複雑なタスクを処理してくれそうにない、

このような事から何となく直感できます。

複雑さについての定量的な定義

複雑さの定量化に関しては、

上で紹介してきた論文の内外から、

下記のようなものが想定されます。

・アルゴリズム上の複雑さ

・情報理論 Fernandez 版

・情報理論 Prokopenko 版

他にもラデマッハー複雑度といった

指標も考え得ます。

しかしこれは私が理解している限り、

いかにモデルがデータを

追随できるかという指標であって、

当記事と関係が薄いと考えられるため、

ここでは除して考えます。

（理由としては、データの複雑さに依存する従属の指標であり、

　そのデータの複雑さ自体を絶対的に定式化するものではないと考えられるため。）

一方、計算複雑性理論という

一つの大きな体系もあります。

しかしこちらも、

計算時間のオーダーを測定する意味では

一部目的を共有しているものの、

以下の理由から、（念頭にはおくものの）

深入りを見送りたいと思います。

理由１：計算複雑性理論の主な対象は

　問題の回答であり、事象一般の複雑さを

　考えるわけではないと思われる。

理由２：

　それ自体が大きな体系をなすため、

　当記事の目的から大きく迂回してしまう。

というわけで計算複雑性理論も

一度除して進みます。

さて、扱う範囲を定めたところで、

早速見ていきましょう。

なお、各種の複雑さ間の関係は、

直接扱わない計算複雑性理論も含め、

まとめで少し振り返ります。

情報理論 Fernandez 版

情報理論を用いている２つの論文のうち

こちらのほうがシンプルに見えること、

また、

アルゴリズム上の複雑さを考えるにも

こちらを先に見ておくことで

見通しが良くなると思われるため、

これをはじめに扱っていきます。

まずここで、二つの情報理論の論文の

いずれでも登場するシャノン情報量 H を

最初に定義しておきましょう。

$\displaystyle H=-K\sum_{i=1}^n p_i \log p_i$

なお定数 K は、Fernandez の議論に限って、

H が実数 [0, 1] の範囲になるように

定めます。

さて、平均情報量とも言われる

シャノン情報量をご存知の方も

多くおられることと思いますが、

一応、定性的な意味を確認しましょう。

色々な値が確率的に選ばれるような

系を想像してみてください。

１つの値のみ選ばれるなら

サイコロの値（の時間変化）。

複数の値が選ばれるなら、

テレビの砂嵐（の時間変化）、

あるいは本物の浜辺の砂

（の位置・角度の空間的変化。後で詳しく考えます。）

を思い描くのが良いかと思います。

その確率が偏っていて、

（例えば真っ暗なままの画面みたく）

同じ値ばかりが出るときは、

（状態が確定したとき得られる）平均的な

情報量が小さいと言えます。

何度確認しても真っ暗である画面は、

次の瞬間にもやはり真っ暗だろう。

という具合に、次の出力値について

（状態が確定する前≒見る前から）

予想がついてしまうわけですからね。

言い換えれば、答えを確認する意味が

薄いということです。

一方、砂嵐のように、

様々な値が満遍なく取られる場合は、

次の出力値について

全く予想がつきません。

この場合は、答えを確認するさいの

意味合いが大きい、つまり

平均的な情報量が大きいと言えます。

要するに

シャノン情報量＝平均的な情報量は、

不確定性と言ってもいいでしょう。

（本物の砂の場合は、例えば既知の 1㎡の砂の状態についての統計的性質をもとに、

　未知の 1㎡の砂について位置・角度に関する完全な情報を予測することを

　考えると良いと思います。

　もちろん、その予測はあまりに難しく、

　予測の段階で分かっていたことと、実際に確認した後に分かることとに、

　大きな差があるわけです。

　これが平均的な情報量に相当するものと、考えることができます。

　なおこのように、他のグリッドの状態を確率変数だとみなす方法は、

　テレビの砂嵐の静止画バージョンでも使えます。

　観測済みのグリッドの状態から、未知のグリッドの状態を推定しようとするとき、

　もし、いかなる距離の間においても相関が無ければ、

　予測がまるでできないため、シャノン情報量が大きいというわけですね。）

f:id:a16777216:20181219100820p:plain 　

Fernandez らは、

この平均的な情報量 H を用い、

大胆にも複雑さ C を

$\displaystyle C = 4H (1-H)$

と表す提案をします。

かなり思い切った定式化に見えますが、

確かにこれで、

情報量が最小である秩序の極で C = 0,

情報量が最大である無秩序の極でもまた

C = 0 となり、

その中間で複雑さが最大になるため、

複雑さが要求する要件を満たします。

流石に大雑把すぎる気はしますが、

複雑さの定量化について

何も言うことができない状態だけは

これで回避できるようになりました。

ひとまず安心したところで？

他の定義を見ていきましょう。

（この後、もっとちゃんと

　緻密になっていきます！）

アルゴリズム上の複雑さ

前後しましたが、

アルゴリズムの長さに基づいて

複雑さを定式化する方法もまた

よく見受けられます。

これは、 Prokopenko の論文によれば、

Kolmogorov–Chaitin の複雑さとして

知られているようです。

定義は言葉の上では単純です。

実装のための可能な最短のプログラムの

コード長を複雑さとする。

というものです。

この定義は見たところうまい具合に、

秩序の極でも無秩序の極でもともに

小さな値をとるという

複雑さの要請を満たします。

真っ暗なままの画面のように

各要素が同じ値を取り続けたり、

あるいは単に周期的に

繰り返し明滅したりするだけの場合、

for 文などの繰り返しを利用した

短いコードで書くことができるため、

コード長は小さいものになります。

一方、無秩序の極、

砂嵐のような画面についてです。

もし、「ある特定の」砂嵐の時間変化を

完全に再現しようとした場合、

ピクセル×時刻の組ごとに、

すべて値を直接指定する必要があるため、

これのコード長は

とても長いものになります。

・・・これでは無秩序の極で、

複雑さが大きくなってしまいますね。

しかしここでは、

「特定の統計的性質を持つ」砂嵐の

実装を考えます。

例えば、

使用可能な任意の色が

（偶然による偏りを無視すれば）

等しい確率で現れ、

任意の時間的・空間的距離に関して

（偶然による偏りを無視すれば）

相関が現れない。

という砂嵐（の時間変化）。

これなら疑似乱数を生成する関数を用い

かなり短いコードで書けるはずです。

これで、コード長を用いて複雑さを

定義するというアイデアは、晴れて、

秩序・無秩序の極で

複雑さがともに小さいという、

複雑さの要求を満たしました。

しかし難点もあります。

「最短のプログラムのコード長」自体

計算可能なのかという点です。

Prokopenko の小括を借りれば、

このコード長を用いた定義は、

厳密な関数的表現はできないが、

大雑把に複雑さを見積もるには良い。

そのように言えるでしょう。

ところでちょっと雑談になりますが、

通常の絵画が秩序の極＝白紙に対し

要素を積み上げていく

ボトムアップだとすれば、

逆に無秩序の極＝砂嵐に対し

制限を加えていく

トップダウン的な絵画があっても

良いように思います。

それでやってみたのがこれですね。

ソースコードが短いため、

夜景とは案外単純な物かもしれません。

既出だったのでまた1から出直しだけど、自動で夜景を描くプログラムできた pic.twitter.com/MfgVgx9CTB
— センケイ (@a33554432) 2015年5月25日

一方、これの約10倍の労力とコード長で

昼間の風景を描くものも作りました。

プログラミングで半自動で描く音ノ木坂。
校章など自動化の難しいところはご容赦を。 pic.twitter.com/4ATgzd2wWs
— センケイ (@a33554432) 2016年3月30日

しかし、このことに反し後者は、

少なくともツイッター上で頂いた評価が

前者より高くありませんでした。

このことから、

以下のいずれかである可能性が

示唆されます。

・複雑であるほど良い絵だという相関はない。

・上のような相関はあるが、

　この２個の画像の場合は例外だった。

・ヒトは、夜景や類する視覚情報から

　目に映っていない構造も推定して補完し

　（例えばビルの壁や屋上など）、

　もっと複雑であると認識する。

もし「例外だった」以外が本当であれば

なかなか興味深いです。

例えばもし夜景のほうが、

ヒトに複雑な補完・想像をさせるよう

促しているのだとすれば、

マシンの限界が厳しい黎明期のゲームが

主に宇宙を扱っていた

（社会背景以外の）理由も

よりはっきりと伺われてきます。

なお、既出の夜景の描画は下記です。

作り終わったのちに調べてみて気づき、

新規性のなさに落胆しました笑。

gigazine.net

情報理論 Prokopenko 版

結論を先取りすると、

予測情報量 $I_{\rm pred}(T, T')$ や

統計的複雑さ $C_{\mu}$ 、

超過エントロピー $h_{\mu}$

が適切そうだ、と

議論されています。

１つずつ見ていきましょう。

f:id:a16777216:20181216231623p:plain

まず、予測情報量とは、

観測済みのもの $x_{\rm past}$ から

これから観測するもの $x_{\rm future}$ を

（平均的に）どれほど予測できるか？

というものです。

具体的には下記で定義されます。

$\displaystyle I_{\rm pred}(T, T')=\left\langle \frac{P(x_{\rm future}|x_{\rm past})}{P(x_{\rm future})} \right\rangle$

ここで $\langle \rangle$ は future と past についての平均です。

T は past のデータ長、

T' は future のデータ長を表します。

これは下記のようにも書けます。

$\displaystyle I_{\rm pred}(T, T')=H(T')-H(T'|T)$

つまり、予測情報量は、

未来の不確定性から

「過去から予想できない未来の不確定性」

を引いたもの。

というものだそうです。

過去から予想可能な

未来の不確実性ということですね。

また別の言い方をすると、

(assortative の和訳に悩みますが)

多様性から無連動性をひいたもの、

ともいえるようです。

なるほどこの指標もまた、

秩序の極と無秩序の極で

ともに小さいことが分かります。

常に同じ値を返す秩序の極では

未来の多様性ないし不確実性が

そもそも低いため、

$\displaystyle I_{\rm pred}(T, T')$ は小さくなります。

一方、完全ランダムに値を返す

無秩序の極では、

過去から予測可能な不確実性は

もはや全く無いため、

これまた $I_{\rm pred}(T, T')$ は小さくなります。

また、観測済みのものが十分多ければ

予測が立ちやすくなる、というのは

直感的にもしっくりきます。

自分の趣味で恐縮ですが、

電車の車窓なんかはまさにこれでしょう。

たとえば、

次にどんな高さの建物が来るかは

かなりさまざまで、

ふつう予測できそうにありません。

しかし、

１～２時間かけて田舎から都会に出る

通勤電車の車窓はどうでしょう。

まばらだった家はやがて密集し、

建物の隙間がなくなっていく様子。

はじめは家ばかりだったのが徐々に、

約 1km ほどの間隔で現れる駅ごとに

ほぼ周期的に十数階建のマンションが

現れるようになっていく様子、

そしてその予測が立ち始めること。

やがてそんな駅と駅の間にも

高い建物が目立ちはじめ、

以降ずっと高い建物が続く様子、

そしてそれを予測できること。

（そして自分が目指していた都会はもうすぐだ、と、

　心に興奮が満ちてきますね。）

このように、既知情報が集まるにつれ

未知の建物を推定しやすくなるさまは

何となく身に覚えがないでしょうか。

あるいは社会的な相互作用、

典型的には会話なんかにも、

予測情報量の考えが

よくあてはまるように思います。

まず会話は、

十分にフレーズの多様性があり、

かつ、完全にランダムではありません。

加えて、

同じ人と長く付き合っていると、

だんだんと会話が慣習化されて、

相手は次にこういうことを言うだろう

というのを、完全にではないものの

予測しやすくなってくると思います。

（もう少しいうと、

　自分が意見を述べたとき、相手が次に言うのは賛成か反対か分からないが

　少なくともそのいずれか一方だろう、とか、

　ご飯の場所を決めててイタリアンにしようと決まったとき、

　相手が次に言う具体的な店名は分からないが、

　少なくとも店名を言うだろう、とか。

　このような具合に、お互いのやりとりに枠組みが形成されて、

　少なくとも発言のジャンルまでは予測できるという事態になると思います。）

このほかにも、

言語の文法や隠喩、社会の法や組織、

情報空間上のゲームやサービス、

あるいは生命の細胞や生体分子など、

さまざまな複雑さの説明において

良く当てはまりそうな気がしますが、

それらをすべて見ていくのは

この記事の役目ではないでしょう。

是非、好きな複雑さがありましたら、

当てはめて考えてみて頂けると

幸いです。

続いて統計的複雑さです。

ここでは同値類を用いるため、

数学のアドベントカレンダーとしては

ある種ハイライトになりますね笑。

さきほど登場した

$x_{\rm future}$ や $x_{\rm past}$ を用いて、

以下の同値類を定めます。

$\displaystyle x_{\rm past}(t) \sim x_{\rm past}(t') \Leftrightarrow P(x_{\rm future}|x_{\rm past}(t)) = P(x_{\rm future}|x_{\rm past}(t')), \forall x_{\rm future}$

ここで $x_{\rm past}(t)$ は時刻 t 以下の

無限の（実用上は長い）過去を、

$x_{\rm future}(t)$ は時刻 t + 1 以上の

無限の（実用上は長い）未来を

それぞれ考えます。

この関係で同値だと定めた各クラス

（つまり似たものを集めたクラス、

同じ未来を予測できるクラス）を、

$\mathcal{S}_i$ とおきます。

これを用いて、統計的複雑さは

$\displaystyle C_{\mu} = - \sum_{\mathcal{S}_i \in \mathcal{S}}P(\mathcal{S}_i) \log P(\mathcal{S}_i)$

と定められます。

素直に解釈すれば、

過去から予測できる未来の多様さ、

という意味と考えられますね。

予測に要する資源の量、という

意味にもなるようです。

これは一般に予測情報量の境界を

下記のように与えます。

$\displaystyle I_{\rm pred}(T, T') \leq C_{\mu}$

最後の指標として、

（実は予測情報量が収束する先の

　量であると分かるのですが、）

超過エントロピーの定義を見ます。

そのために、ブロックエントロピーを

先に定義します。

データ長 L についての

ブロックエントロピー H(L) は

下記で与えられます。

$\displaystyle H(L) = - \sum_{x^L \in \mathcal{X}^L} P(x^L) \log P(x^L)$

ここで $\mathcal{X}$ は可能なブロックの集合です。

これを使ってエントロピーゲイン

$\displaystyle h_{\mu}(L) = H(L) - H(L-1)$

を定め、

さらにこの極限値を

$\displaystyle h_{\mu} = \lim_{L \to \infty} h_{\mu}(L) = \lim_{L \to \infty} \frac{H(L)}{L}$

とします。

これは熱力学のエントロピー密度に

相当するもののようです。

さて、これを用いて、

いよいよ超過エントロピーです。

直感的にはやや理解しにくいですが、

有限のエントロピーゲインの

過大評価分を集めて、

下記のように定義します。

$\displaystyle E = \sum_{L =1}^{\infty} [ h_{\mu}(L) - h_{\mu}$ ]

これは過去の時間長 T および

未来の時間長 T' が半無限のときに、

$\displaystyle I_{\rm pred}(T, T') = E$

となるそうです。

さて、超過エントロピーの

定性的な意味についてです。

少ない情報で「簡単に片付けようと」

していたところ、後から見たら

訂正されるべきだった分かる量、

そのような量（あるいは乱れ）の

総和となっています。

言ってみればこれこそ、

構造の豊かさと言えるわけです。

これと等しい値に収束する、

予測情報量という複雑さが、

過去を「知れば知るほど」

予測できる量であるということが、

改めて確認できてきましたね。

課題

さてここまで、

多種にわたる複雑さの定義を

それぞれ見てきました。

しかし、

現在プロの研究者でない私の目からも、

やはり明らかに課題もあるわけです。

（もちろん課題があることは悪いことではありません。）

ここまで見てきた限りでは、

複雑さは、

単に平板な時系列（または空間の列）の

羅列の上に定義されています。

もし、概念化や「ゲシュタルト」を

用いた、構造の階層化を考えたとき、

複雑さはどうなるのでしょうか。

あるいは階層化はどう定義される

べきでしょうか。

まだまだ複雑さは、

私たちの興味を掴んで離しては

くれないようです。

しかし、ここまでの定義たちから、

大分複雑さに対する理解の糸口が

大分見えてきたように感じます。

応用可能性

ここまでの定義を踏まえて、

現実の「複雑」といわれる事態に

どう接していくかについても、

少し考えていきます。

対処や活用ですね。

複雑さへの対処

『複雑さと共に暮らす』は、

複雑さ自体は必要だが、

意味のない複雑さは避けるべきだ、

と主張しています。

意味のない複雑さとは何か。

鍵は恣意性だと思います。

分かりやすさのため、

恣意的でない例を

先に考えていきましょう。

たとえば

「あまい」という言葉は甘い意味を、

「からい」という言葉は辛い意味を表す事、

これは日本語話者でなくても、

２択であれば偶然以上の正答率で

回答できるのではないかと思います。

このように記号や意味などの２つの指標が

独立でない関係にあることを

「有契性」というそうで、

これが「恣意性」の対義語にあたります。

逆に言えば、わざわざ

「からい」という言葉で甘い意味を、

「あまい」という言葉で辛い意味を

表すのは恣意的であり、

こうする理由はないわけです。

味を、

おいしさの１次元でなく、

あまさやからさを導入し

多次元で表現することは、

確かに複雑さを増します。

しかしこれは必要な複雑さかも

しれません。

ここで、言葉と意味とが恣意的にせず

意味のある有契的関係にすれば、

必要な複雑さを出来る限り倹約的に

理解・表現できるのではないか、

そのように考えることができます。

ところで、

複雑さを予測情報量で定義する場合、

ここまで「無駄な複雑さ」と表現した

恣意的な関係は、

むしろ複雑ではない、と言えるかも

しれません。

音韻という観測済みの情報から

意味という未観測の情報を

予測しようとしたとき、

てんでんばらばらで予測できないなら、

予測情報量は小さくなりますからね。

複雑さを予測情報量で定義する場合、

「無駄な複雑さ」というものは存在せず、

複雑さは存在すれば必ず意味がある、

あるいは活用可能な複雑さである、

と言えるかもしれません。

複雑さの活用

社会に現に多数、

複雑と思えるものが存在していること。

このことは、

事態が複雑でなくてはならない必要性を

間接的に支持しているように見えます。

複雑であることは有用なのでしょうか。

断定はできませんが、

間接的にこれを支持する情報がないか、

ここまで見てきた定義も振り返りつつ

確認していきましょう。

例えば『ビデオゲームの美学』は、

インタラクティブ性について、

スマッツから下記を引いています。

インタラクティブな事物が与える反応の種類は、コントロール可能なものとたんにランダムなものとのあいだにある。

これはまさに複雑さの要件である

秩序の極と無秩序の極の間、に

よくあてはまるものではないでしょうか。

いっぽう同書は、

井上明人さんを引きつつ、

ゲームの楽しさの議論の１つとして

次のような「学習説」を挙げています。

ゲーム行為は「認知のパターンや行為を調整、修正していく過程」（井上 2008, 33）である。楽しさを感じさせるゲームは「学習体験をきちんと誘発してくれる」ようなものであり、そこでは「プレイヤーがほどよい刺激を受けながら、試行錯誤の学習を経験してゆく」(ibid, 34)。

このことから、

インタラクティブである（≒複雑さを要求する）

行為の１つであるゲーム行為は、

認知の調整や修正に役立つかもしれない、

このように考えることが可能に思います。

これは私の妄想がかなり入りますが、

以下のような仮説が頭をよぎります。

人間は複雑（≒情報量が中程度）である

行為こそに魅力を感じており、

その理由は、

対象に対する認知的な処理を通じて

利用可能な情報を引き出せるためでは

ないか、と。

これが検証されるまでの道では

まだまだ繋がっていないパスが

行く手を阻んでいます。

しかし、

複雑さに惹かれる人間の認知こそが

数々の資源を利用可能にしてきたのだと

空想にふけってみると、

（しかもその複雑さには未だ明確な定義が与えられていない！ことに思いをはせると、）

中々ロマンが感じられませんか？

なお、『ルールズ・オブ・プレイ』は、

遊びは、（要約すると）

固定された構造の中の／に対する

自由な動きである、

と説明しています。

遊びが「楽しい」を包含するかは

非自明ですが、

しかし上記の説明が、

秩序の極と無秩序の極である

複雑さにこそ面白さがあることを

支持しているように思えます。

まとめ

長くなりましたが、

ここまでで、

複雑さを取り巻く様々な説明と、

定量的な定義、

そして日常的な直感への

あてはまりを、

それぞれ見てきました。

中には Prokopenko らのもののように、

緻密に定義され、

かつ日常の直感ともよく整合する

良さそうな定義がありました。

しかし、自分が知る限りまだ、

誰もが共通見解として

これを使っている様子ではありません。

ここから想像するに、

まだ複雑さの定義は、

完全に合意には至っておらず、

課題が残っていたり、

議論が続いていたりするのでしょう。

（パッと思いつく例でいくと、

　カオスの予測可能性をどう扱うかで

　見解が分かれそうに見えます。）

少し、各種の指標の関連性も

考えておきましょう。

当記事中で見てきた、

アルゴリズム上の複雑さ、

情報理論 Fernandez 版、

情報理論 Prokopenko 版、

この３つの複雑さは、

微細構造こそ微妙に異なりますが、

複雑さの定性的な要請を

目標として共有していました。

すなわち、

秩序の極と無秩序の極でともに

複雑さが小さくなる、という

要請のクリアを目標としました。

そしていずれの定義も、

その要請を満たしました。

ここで、計算複雑性理論は

どうでしょうか。

私の理解している限り、

計算複雑性理論は、

扱う対象も、

関心も、

いずれも異なるように思います。

対象は、現象というよりは、

問題（それも、ランダムさがない）を

解く過程だと思います。

かつ、特に関心を持っている複雑さは、

具体的な関数形ではなく、

以下のいずれかのオーダーか

―指数関数的か、それよりも小さいか―

であると考えられます。

しかしもちろん、

完全に無関係ではないでしょう。

具体的には、Prokopenko らの論文の

３章（複雑さの章）のまとめは、

エントロピーゲインや

アルゴリズムの複雑さが、

万能チューリングマシンと関係する旨を

述べています。

ここに、当記事で着目した

事象の複雑さと、

計算複雑性理論の複雑さとの

接点があるものと考えられます。

一方、ラデマッハー複雑度や、

これと関連する VC 次元は

どうでしょうか。

まずラデマッハー複雑度は、

学習中の学習器の、

予測精度の大きさを表すもの、

つまり学習の進度を表すものと

言えそうです。

※2019/08/17 追記

2019/08 ラデマッハー複雑度についての訂正

申し訳ありません。

完全に間違っていました。

ラデマッハー複雑度は、

関数ではなく関数の集合の複雑さを考えます。

このため、学習が進行した結果

判別や回帰の関数がどうなったか、ということは

全く議論していないのでした。

代わりに、

学習した場合に判別や回帰の関数が、

どういった範囲であれば取れ得るのか

（取れてしまえるのか）、

これを議論しています。

英語ですが、

こちらのドキュメントを参考にしながら、

定義を確認してみましょう。

http://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/10_rademacher.pdf

まず、データの集合 $\mathcal{Z}$ の中から、

$n$ 個のデータ $Z_i$ を取り出します。

これと同時に、独立かつ完全ランダムに、

$i$ ごとに $\pm 1$ のいずれかを取り、 $\sigma _i$ に格納します。

このとき、以下の値を考えます。

当のラデマッハー複雑度の式の中核であり、

複雑度の大きさに特に関わる箇所です。

$\displaystyle \sup _{g \in \mathcal{G}} \frac{1}{n} \sum ^n _{i=1} \sigma _i g(Z_i)$

先を急いで一気に書きましたが、

機械学習の文脈を追っていきましょう。

ここで $\mathcal{G}$ は、

僕らが学習のために用意しているモデルです。

学習を通じて適切な判別器ないし回帰器を

うまく得ようとしている僕らは、

モデル $\mathcal{G}$ の中から、データ $\mathcal{Z}$ に合うものを

探しているところというわけですね。

うまくデータにフィットして得た関数を

例えば $\hat{g} ( \in \mathcal{G})$ としましょう。

こいつが、次に現れるデータ $Z_{n+1}$ などに対し

判別やら回帰やらの予測をする関数だ、

というわけですね。

ここで、モデル $\mathcal{G}$ が

関数の集合になっている点にご注意ください。

得うる判別関数ないし回帰関数の全体を考えます。

なぜわざわざ関数の集合を考えるのかというと、

そのモデルの空間全体が、

どれほど豊かで、どんなフィット結果をも出せるか

（そして無駄に出せすぎてしまうのか）、

ということを知りたいからです。

上で書いた $\sup$ の話題に戻りましょう。

こいつは、

ただ単に与えたランダムな値 $\sigma$ に対して、

可能な限り大きい値を取ろうと

$\mathcal{G}$ の中を足掻きます。

もし、

与えたデータ $Z_i$ が何であろうと

この $\sup$ が大きな値を取れるとするならば。

そうすると、データ $Z_i$ 一式とはあまり関係なく

$g$ が任意に大・小の値を取りに行けてしまうことに

なってきます。

直感的には、 $\mathcal{G}$ は過剰に自由なんじゃないの？

ということになってきます。

さて、ここまで踏まえると、

ようやく経験ラデマッハー複雑度 $\mathcal{R}$ を

書くことができます。

$\displaystyle \hat{\mathcal{R}} _S (\mathcal{G}) := \mathbb{E} _{\sigma} \left[ \sup _{g \in \mathcal{G}} \frac{1}{n} \sum ^n _{i=1} \sigma _i g(Z_i) \right]$

さっきの $\sup$ を、

任意のランダムな $\sigma _i$ にデータ $(Z_i)$ を添え、

期待値を取ってやろうというわけです。

こいつがラデマッハー複雑度になります。

複雑度の高いモデルを選択すれば、

直感的には確かに、

理論上の訓練誤差（学習誤差、経験損失とも）は

小さくなっていくでしょう。

しかし同じ訓練誤差を実現するならば、

ここでいう複雑度は低いほうが

ムリヤリ合わせにいっている可能性が下がる分、

良いというわけです。

実際、汎化誤差と訓練誤差の差、

その理論上の上限は、

このラデマッハー複雑度の分だけ

大きくなるとされています*1。

逆に言えば、

それを超えて差が大きくなることはない、という

上端の評価になっています。

さて、ここまで踏まえると、

投稿時の私の以下の記述も

恥ずかしながら当を得ていません。

これに対して、

私たちがここまで見てきた

特に情報理論による定義は、

これから学習するさいの予測精度、

つまり理論上の学習可能な精度を

考えるものでした。

その意味では学習のどの時点に

着目するかについて

興味が異なっています。

しかし、

理論上の上限まで学習が済んだときの

ラデマッハー複雑度であれば、

データに関する理論上の

学習可能な精度を

表せはしないでしょうか？

このラデマッハー複雑度と、

その上限に関係する VC 次元は、

この予測精度の上限の観点から見ると、

当記事の内容と接点を持ちそうだと

考えることが出来ます。

ラデマッハー複雑度もまた

理論上の予測精度に関するものには

違いありません。

決定的に違うとすれば、

この記事が主に議論している複雑さが

データあるいは現実の複雑さなのに対し、

ラデマッハー複雑度はそれを予測するための

予測モデルの複雑さという点でしょう。

いずれにしても、

複雑さを用いようとする立場が大きく異なるため

類似性を考えることは難しいです。

ただ、数学的な類似性は一旦忘れて

問題設定にだけ着目すると、

理解するべき対象の複雑さと、

理解をするための解決器の複雑さということで

好対照をなしている点が面白いですね。

※ 追記ここまで↑

※ ↓ 2018/12/20 追記

また、複雑さと関係の強い、

自身の再帰的な定義についても

言及したいと思います。

例えば言語。

『記号と再帰』にあるように、

再帰性は言語系の大前提とされており、

言語の複雑さを考えるうえでは、

再帰性の議論は避けて通れないでしょう。

一方、社会における個人のあり方。

『集団と組織の社会学』や

『アニメ聖地巡礼の観光社会学』等で

ギデンズの再帰性あるいは

再帰的近代化について述べられています。

概括すると、

（ギデンズの論文の時期的に、恐らく90年代以降を指して、）

近年では集団や居住地の選択が自由になった反面、

絶え間ない内省をもとに選択したり、

自分のありようを自分で定めたりしなければ

ならなくなった、

という内容です。

これは個人に対してでなく、

個人間の（私的な）関係にも

あてはまるとされています。

つまり、社会における個人のありようも、

その複雑さ

（あるいは近現代の複雑さの変動）を

再帰性を考えることなく扱うことは

困難と言えるでしょう。

では、再帰的な定義がある場合、

複雑さはどうなるのか。

ここまで見てきた指標を早速用い、

考えてみましょう。

まずは再帰的な「定義」より先に、

単に再帰的なものである、

フラクタル図形を考えます。

フラクタル図形は、

複雑さに対して中立的です。

これはなぜか。

フラクタル図形は、

ある特定の区間で学習しようと、

必ずそれよりも長い相関が出現します。

このため、フラクタル図形は、

Prokopenko らの超過エントロピーは

大きいものになると考えられます。

※ ↓2019/01/06 追記

友人のリングさん（@matsumoring）に

教えてもらったんですが、

超過エントロピーは確率変数に対して

定義されるものなので、

１回こっきりのフラクタル図形に対して

これを観測するには、工夫が必要です。

一部分のみ抽出して

データ収集と予測を行い、

この繰り返しに対し平均操作をする等ですね。

一方ランダムさを持ったフラクタルであれば

素直に適用できます。

その際、超過エントロピーの値は、

繰り返し適用した結果に平均操作をして得ます。

※ ↑追記ここまで

しかし一方、

フラクタル図形は再帰性ゆえに、

短いコード長のプログラムで

出力することができてしまいます。

このため、コルモゴロフの複雑さは

小さいものになります。

複雑さの定義によって結論が

割れてしまうのです。

しかしこれは興味深いことです。

ある種の複雑じゃない条件から、

複雑な結果を出力していると

そのようにも見なせるでしょう。

このことは自己組織化とよく

参考文献

投稿当初より

複雑さと共に暮らす―デザインの挑戦

作者: ドナルド・ノーマン,伊賀聡一郎,岡本明,安村通晃
出版社/メーカー: 新曜社
発売日: 2011/07/28
メディア: 単行本
購入: 8人クリック: 67回
この商品を含むブログ (3件) を見る

記号と再帰新装版: 記号論の形式・プログラムの必然

作者: 田中久美子
出版社/メーカー: 東京大学出版会
発売日: 2017/04/29
メディア: 単行本
この商品を含むブログを見る

※近現代において複雑さが増大しているという通念について。

　また、言語・記号の再帰性について。

統計的学習理論 (機械学習プロフェッショナルシリーズ)

作者: 金森敬文
出版社/メーカー: 講談社
発売日: 2015/08/08
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

※ラデマッハ（ラデマッハー）複雑度および VC 次元について。

計算理論の基礎 [原著第2版] 3.複雑さの理論

作者: Michael Sipser,太田和夫,田中圭介,阿部正幸,植田広樹,藤岡淳,渡辺治
出版社/メーカー: 共立出版
発売日: 2008/05/21
メディア: 単行本
購入: 4人クリック: 34回
この商品を含むブログ (17件) を見る

M. Prokopenko, F. Boschetti, A.J. Ryan, An information-theoretic primer on complexity, self-organisation and emergence, Complexity 15 (1) (2009) 11–28, doi:10.1002/cplx.20249.

https://onlinelibrary.wiley.com/doi/abs/10.1002/cplx.20249

N. Fernandez, C. Maldonado, C. Gershenson, Information Measures of
Complexity, Emergence, Self-organization, Homeostasis, and Autopoiesis,
Springer Berlin Heidelberg, 2014 doi: 10.1007/978-3-642-53734-9_2.

https://link.springer.com/chapter/10.1007/978-3-642-53734-9_2

arxiv.org: https://arxiv.org/abs/1304.1842