規則性と複雑さと理解
「同じ著者の小説をつなげてzip圧縮したら、複数の著者の小説をつなげて圧縮するよりも圧縮率がいいから著者推定に使える！」って論文が見つかった。
二つの文字列A,Bが「近け」れば「近い」ほど(A+B)の圧縮率が高くなるというのは、昔からありそうでない新しい見方に思います。単純に文字列を比較するときは、編集距離(レーベンシュタイン距離)が思い浮かびますが、自明でないパターンを共通項にもつような場合はこの「近さ」は向かないかもしれません。
圧縮による「近さ」が面白いのは、いろいろな形式のデータに適用可能であるということです。テキストはもちろん、画像形式や音楽ファイルなどにも適用できるかもしれません。特に人が似ていると感じるときに(脳内で)処理されていると思われる不可逆圧縮にまで広げると面白い結果になるのではないかと思います。
集合において距離という量は重要です。距離によって「近さ」が定義でき、似たようなグループを構成することができるからです。距離は構造化、抽象化をする上で根本的なものだと思います。人が世界にあるものを構造化して理解するプロセスでは何らかの類似性の判断に基づいて概念形成をしていくと考えると、特定の圧縮アルゴリズムと概念形成は対応していると考えることができます。
ここで圧縮についてですが、この操作は複雑さを計算しているといえます。規則性が強い文字列は圧縮率が高く、ランダムであるほど圧縮率が低くなるからです。複雑さといえばコルモゴロフ複雑性がありますが、これは、以下の面白い性質を持っています。
コルモゴロフ複雑性に関する計算理論上の興味深い帰結のひとつは、コルモゴロフ複雑性が実効的に計算できないということである。
…
また、コルモゴロフ複雑性が計算不能であるという事実は、すべての文字列 x に対してコルモゴロフ複雑性がしめす究極の圧縮を実現するプログラムを作ることが原理的に不可能であるということを意味している。
つまり、世界の完全な理解(=究極の圧縮アルゴリズム)は計算不可能と言えます。プログラミングで言うと名前空間の設計がそのまま対応しそうです。逆にいうと、どれが最適解かが分からないので理解の仕方にはどれも可能性があって、多様なものの見方、考え方が重要であるともいえます。
