HOME

計算的な深さと脳

ニューロンが入力を受けてからスパイクを出すまでは早くとも数ミリ秒かかる。人間が反応するまでの時間は零点何秒かだから、入力と出力の間には最大に見積もっても数十段のニューロンが介在するだけである。(実際はもっと段数が低いだろう。) 一方コンピュータの方は現在のネズミ以下の判別能力しかないような画像認識をするにあたってさえ数千万サイクルの計算を行わなくてはならない。 だから、脳が物凄い並列計算をやっているに違い無い。ここまでは普通の話ね。

で、問題は「じゃ、物凄い並列な機械をつくったら脳の能力を再現できるのかよ」ということ。もちろん誰も答えをしらない。どんなアルゴリズムを使えば良いか分からないし。 人によっては絶望して「新しい物理法則を」とか「量子論的並列性」とか、「魂」とかに行っちゃう。

で、僕も答えは持って無いけど、この問題を考えるにあたって以下の「計算的大きさ」と「計算的深さ」の概念をしっかり持っておくと役に立つと思う。この用語は今日思い付いたんだけど、計算機を知っている人は誰もが前からぼんやりと意識している概念だとおもう。※

そして、 一般的に計算的深さは良い物だと考えられているけど、むしろ計算的浅さの方が現実の問題を解くにふさわしい場合があることを、最後にコメントするね。

(※これを書いた後に計算量の理論では「時間的複雑」さと「空間的複雑」さと呼ばれているということを知った。でも「深さ」と「大きさ」のほうが分かりやすいからそのままにしておく。(31日追記:どうも空間的複雑、時間的複雑とも意味が違うみたい。失敗失敗。))

1、計算的深さと計算的大きさとは

計算的大きさとは、これは普通でその定義された計算(~写像)を完了するまでに要する計算の数のこと。 では一方、計算的深さとは、相互依存する計算の段数のことだ。並列な演算機が無限にあるとき何ステップで終了するかと言ってもいい。

たとえば n=1000 として

double* func(double* A, double* B, int n){
	double* R = malloc(sizeof(double)*n);
	for(int i=0; i < n; i++) {
		R[i] = A[i] + B[i];
	}
	return R;
}
てな感じのプログラムがあったとき、その計算的な大きさは1000だ。でも計算的な深さは足し算の分の1に過ぎない。 一般に言って、index i の走る順序に結果が依存しないようなループは深さには全く寄与しない。(そう考えると、一般のプログラムの演算的深さは意外に浅いことに気付くだろう。)

一方、例えば

double funny(double x,  int n){
	double a=なんか定数;
	for(int i=0; i < n; i++) {
		x = a*x*(1-x);
	}
	return x;
}
のような計算はn=1000で計算的大きさは乗算と可算で3*1000だ。で、計算的な深さはそのまま3000に達する。上と似て見える割にはなんと違う事か。

注意しておきたいのは本質と関係ない計算的深さもあるということだ。

double sum(double* A int n){
	double s = 0.0;
	for(int i=0; i < n; i++) {
		s += A[i];
	}
	return s;
}
これは確かに深さ1000であり、1000と定義するべきだけども、誤差を除けばカスケード的な和に置き変える事ができるから本質的な深さは log 1000/log 2 = 10程度に過ぎない。

(31日追記:funnyを訂正。もとのままだと0しか出ません。)

2、マイクロプロセッサの歴史と計算的深さへの執着

ここ十数年のマイクロプロセッサの歴史では、クロックを1.4倍にあげられるならトランジスタ数を2倍に増やしてもいいという感じでプロセッサは進化してきた。数字自体はいい加減だけど、このあたりはみんな知っていることと思う。

2倍のトランジスタ数を使えば単純にプロセッサを2つにして2倍の計算的大きさを得られるのに、代わりに1.4倍の計算的深さを欲したということだ。ここ十数年分を積算すると1000倍の計算的大きさを32倍の計算的深さと取り引きしたということだあきらかにコンピュータの技術は計算的深さへの執着に駆動されている。

では、なぜこのような一見不釣り合いな取り引きをしたのか。 それは計算的深さの方が遥かに能力が大きいからだ。

まず、単純に深さ1で大きさ1000と、深さ1000で大きさ1000の二つをくらべてみる。同じ計算的大きさでも、後者にはできても前者にはできないこと明らかにある。反対に前者にできる事なら、なんでも後者はできる。同じ大きさなら深い方が能力が大きい。 と、いうことは有用性で言った時、多少計算的大きさを犠牲にしても深さを稼いだ方がいいだろうと想像できる。

では、どれくらいの取り引きならば割に合うのか。実は僕もまだその辺りについてはあまり良い議論を持っていない。 しかし、たとえば、ある簡単な等式を n=10億まで証明するよりもずっと早く、数式処理によって無限まで成り立つ定理を証明できたりすることなどを考えると、直列的な深さは非常に大きな能力を持っていて、かなりrateの違う取り引きが可能なのだと思う。

3、計算的深さは単位演算の定義により定数倍だけ異なる

たとえば1000個の数を加えることを考える。最大限に並列にやるにはカスケード的に足していけば良いから、その深さはlog 1000/log 2 ≒10くらいだ。これは単位演算が2項加算であるばあいだ。 もし単位演算が4項加算であればその深さは半分の5になる。

このように計算的深さは定義に依存するが、違うのは定数倍である。恐らく2項演算で定義するのがもっとも明解だろうから以降はこれを使う。(本当はビット演算まで還元しなくてはならないかも知れない。)

で、この話をなんで持ち出したかというと、神経細胞の一段はこの定義での1段では無いからだ。 神経細胞のやっている計算は、控えめな見積もりとしては、1万程度の入力の和をとってそれに非線形関数をかけて出力する事だ。その計算的な深さは二項演算を基準にすればlog 104/ log 2 ≒13くらいだ。非線形性はまあ、テーブル引きでもいいから気にしない。

つまり、神経細胞の数十段は計算機で言えば1000段くらいの深さかなということ。

4、計算的深さとカオス

上の計算的に深い計算の例がいわゆる、決定論的カオスの例として有名なロジスティック写像であるのは偶然では無い。 カオスは計算的に深い系にしかあらわれない。反対に計算的に深い系の全てがカオスではない。

これに証明とかは与える事はできないけど、実数についてならば荒っぽい議論はできる。非常に小さな初期値の違いが大きな結果の違いをもたらすというのがカオスの本質である。乗算や可算などの連続演算の有限回の適用では微少な入力は微少な出力の差しか生み出さない。だからカオスにはなりえない。

このようにカオスと計算的深さには深い関係がある。

5、現在の普通のプログラムが持っている計算的深さは意外と浅い

私の考えでは普通のプログラムの計算的深さはかなり浅い。10以下という所だろう。

評価順序に依存しないループはみな深さにはまったく寄与しない。 深さに寄与するのは2項以上の引き数をとるような演算子やif文(これも3項演算子ですね)などだけで、それがトップレベルからもっとも下端になるサブルーチンまでのレベルを数えていっても普通は10をこえないだろう。

もっとも、計算的に物凄い深いプログラムもある。100万レベルに達するような。しかし、それらの多くは間違って深くなっているプログラムだと思う。

(ここで「普通」という言葉で指しているのは我々が普段見かけるアプリのような物、あるいは「人工知能」ではないプログラムを、なんとなく、意味している。)

6、「間違って計算的に深い」プログラムとは?

例として、英語のテキスト圧縮アルゴリズムを考える。 まずテキストを頭から読んでいき初めて出てきた単語はストリームにタグを付けて書き出す。二度目以降に出てきた時は前回に出現したのは何文字前か数字で書き出す。数字はハフマンコードをするといいかも知れない。

簡単な例だけど、実際のテキスト圧縮プログラムに似ていると思う。 これに数メガバイトのファイルを入力してやるとその計算的深さは数千万に達するだろう。(もっとかな)一つの単語をどうにかするのにもいちいちそれまでの全ての文章が影響するからだ。そしてその単語の影響もまた後ろに及ぶ。

しかし、実際はその深さは、それほど必要な物でも無いのだ。 仮に問題のテキストを10個に区切って、それぞれにこのアルゴリズムを適用した場合、おそらく圧縮効率はほとんど変わらないだろうが、深さはずっと小さくなる。 要するにプログラムの目的とする機能に全くでは無いが、大して効かないような使われ方をしているのだ、深さが。

計算的深さはコンピュータのチューリング完全性とも関係がある極めて中核的な能力だが、それが無駄遣いされている。 なぜかといえば現在のCPUアーキテクチャやプログラミング言語は無駄な深さに対してまったく何のペナルティーも課さないからだ。

このような使い方を排して、あえて計算的に浅いアルゴリズム(〜並列性の高いアルゴリズム)を追求すれば、やはり現在のプログラム達はかなり計算的に浅くできるのではないかと思う。

また、一つ計算的に深いプログラムの特徴がある。それは入力の微細な変動に対して出力が激しく変動する事だ。たとえば圧縮アルゴリズムの例だと、テキストの前の方で一文字違っただけで、出力のビットパターンが全体に渡って違ってくる可能性がある。圧縮アルゴリズムの場合はこの性質は無害ではある。

しかし、この小さな入力の変動が出力の激しい変動に繋がり、しかも人間にすら予測不能な変動を起こすと言うのは計算的に深いアルゴリズムの特徴である。※2

(※2これとカオスの話を合わせてみると、我々の「複雑さ」という観念はほぼ「計算的な深さ」に対応しているような気がする。)

7、「人工知能」のプログラムは計算的に深い、恐らく間違って

「人工知能」としてはここではコンピュータビジョンみたいな物を考える。そうで無くとも大して変わらないと思うけど。

人工知能のプログラムはどれも非常に計算的に深いアルゴリズムを使っている。先ほどの圧縮の例のような簡単な分割はできないだろう。

人工知能のプログラムにありがちな問題はノイズに弱い事である。入力のわずかな変動が出力の大きなそして予測不能な変動につながる。トイワールドではうまく動くプログラムが実用にならないのは多くはこの理由である。

ここでカオスの所で論じた事を思い出してみよう。入力の小さな変動が出力の大きなそして予測不能な変動に繋がるのは計算的に深いアルゴリズムの特徴だった。深いのが必ずこの種の不安定を持つわけでは無いが、深く無ければこの種の不安定は存在し得ない。

だとすると、人工知能的アプローチの失敗は計算的に深すぎる為であると想像する事もできる。

(「人工知能」的アプローチがみな計算的に深いことに関しては、単に「そうなっちゃった」とか「浅いアルゴリズムを思い付かなかった」という側面もあるが、わざとの側面もあると思われる。 人間の知覚は安定であるが、同時に人間の知能には極めて小さな入力の変化が劇的な行動の変化をもたらすという側面が確かにある。 だから計算的に深い側面があるのだろうが、その側面ばかりを見るのはまずいだろう。)

一方、脳による知覚の機能は普通、ノイズに対して安定である。もちろんそれが計算的に深い系であることは論理的には否定はできない。 しかし、これまでむしろ脳は計算的に深そうだという無意識の思い込みがこれらの分野に支配していた訳で、反対に脳が計算的に浅い仕組みを使っている可能性を今後は考える必要があるように思える。

(この項にはできればもっと具体的な例を加えたい。)

最後にもとの問題

つまり脳から推測される100段以下の計算的深さでもって、物体の認識をはじめとする脳の機能を再現することができるかとうい問題だ。

コンピュータ的に言えば1000段程度の計算的深さで可能かである。

それが無理そうに見える理由は、第一にはリーチが短いように思えることだし、第二にはターゲットが遠すぎるような気がするからである。

リーチが短いような気がするのはなぜか。それは我々の知っている普通のプログラムがすでに計算的に1000段程度ですまないくらい深いように見えるからである。 しかし、実際のところ普通のプログラムは計算的には非常に浅い事を論じた。また必要もないのに間違って深いプログラムも多い。

次に、ターゲットが遠すぎるような気がする理由は、つまり脳の機能を記述するアルゴリズムが全く想像できないからである。しかし、人工知能の項で触れたように、我々の知覚や運動が安定しているという事実ははそれが計算的に意外と浅いプロセスであるかも知れない可能性を思わせる。つまりターゲットは意外と近いのかも知れないのだ。

この二つをあわせて考えればあるいは、1000段以下の計算的深さでもって脳の機能を再現することもあり得ない事では無いように思えてきませんか?(もちろん計算的な大きさは極めて大きいけど。)

2005年10月29日 ver.1


| Home |
T. Mogami
e-mail: mogami@yugiri.bnf.brain.riken.go.jp