Web鼎談 １０月号

その前に，作図のたとえ話について，もうひとこと．根上さんは，「１７回や１８回の差をいうのは面白味がない」とコメントされていました．その背景には，多分，「１７回でできるかどうか，すべてのやり方を試してみればわかる」という心理（？）があるようにも思えます．でも，実際は，単純にはすべてのやり方を試すことはできません．というのもコンパスを使うのは１７回だけれども，定規を使う回数には制限がないからです．ですから，可能性は無限にあります．

これと同じようなことが，計算回路の複雑さの解析にも顔を出します．計算回路とは，AND や OR や NOT などを使って計算をする回路です．与えられた計算問題の困難性を示すのに，その計算問題を計算する最小の計算回路の大きさを議論するというアプローチがあります．これを回路計算量の解析と言います．

回路計算量の解析の研究で重要な研究課題の一つに，どんな問題が多項式サイズの回路で解くことができないか？ということを調べるという課題があります．たとえば，巡回セールスマン問題を解く回路で多項式サイズの回路があるか？などという疑問に答えようということです．（これは，よく話題になる P /= NP 問題の回路版です．）

ただ，それは今のところ難しいので，まずは，回路の段数を制限した場合を考えましょう，ということになりました．回路は普通，入力から段々に積み上げて作られるので，その段数を制限すると，当然，回路の機能が制限される訳です．そういった制限を仮定すれば，多項式サイズの回路の計算能力をうまく特徴付けられないか，と考えた訳です．

たとえば，段数を１７段に制限した多項式サイズの回路で何ができるか？ということです．

これには，かなりきれいな特徴付けが得られています．簡単にいうと，「段数を k 段に制限した多項式サイズの回路で計算できるような関数は，次数が高々 d(k) の整数多項式で近似できる」という結果です．ここで d は，比較的小さな関数です．（この結果自体は，Smolensky というロシアの研究者の結果ですが，関連の研究に日大の戸田さんや電通大の垂井さんが大きな貢献をしています．）

こういう風にきれいに特徴付けられますと，あとは，目標の計算問題に対し，それが低い次数 d(k) の多項式で近似できないことを示すことにより，その問題が k 段の回路で計算できないことが，つまりある意味での困難性を示すことができます．

なお，この例では，k = 17 でも k = 18 でも特徴付けは同じようにできます．ただ，そのように同じ特徴付けができない例もあります．

長くなってしまってすみません．
 
 

今までの話では、例として「計算の困難性」が挙がっていましたが、
　計算の困難性の議論の最初は、
　情報量の概念を用いたものではないしょうか。
ある問題がどのくらいの手数で解けるのか？という値の下界として、
　情報量と呼ばれる概念が使えるというのは、
　コンピュータ・サイエンス黎明期の大きな話だと思います。

そういえば、この３人の鼎談だと、
　　情報量理論や符号理論あたりも弱いのかな。

渡辺さんがいない間に，二人きりでおしゃべりしていましょう．

私は，てっきり，その特徴づけのスタイル自身に大きな違いがあるのかと思っていました．だから，手数が１７から１８に変わっただけでも大変なことになるのだと，渡辺さんは主張したいのだと思っていました．というよりも，私は，そうなっていくことを期待していて，コンピュータ・サイエンスの良さを引き出したいと思っていたのです．

でも，期待どおりではないにしろ，数学とは違うコンピュータ・サイエンスの世界が見え出してきた感じです．

もしそういう例があれば、たかが手数の違いといえども、あなどれないな、という感じがしてきます。

例えば、ちょっと難しい話になってしまうけれど、R^nに入る微分構造が4次元のときだけ、複数になるという現象があります。線形代数的に見れば、次元なんて、どれも同じようなものという感じがしますが、微分構造という視点を入れると、４次元だけ特別という現象が見えてくるわけです。となれば、たかが次元といえども、あなどればいぞ。そういう警戒を促す視点を微分トポロジーが我々に提供してくれているわけです。

それと同じように、コンピュータ・サイエンスが提供する視点から見ると、単なる手数の大小以上の違いが見えてくる、という話にはならないでしょうか。そういう観点とか視点を突き詰めていくと、松井さんが以前、言っていた、コンピュータ・サイエンスの精神のようなものが見えてくると思うのだけれど。

根上：うん，なるほどね．よくわかった．
渡辺：でしょ．
根上：でも，それは数学ですよ．

ということになってしまうような気がします．う〜ん，困ったなぁ．

実は，今，久しぶりに「論文漬け」状態になっています．というのも，今年で１０年目の Algorithmic Learning Theory Conference の論文選定委員長をやらされていて，投稿論文のうち，少なくとも３０件を，まじめに読んで審査しなければならないからです．しかも４週間で！（数学でも，こういったことってあります？）

この会議は，計算論的学習理論という分野の会議です．これは，今，鼎談でも話題になっています理論計算機科学を中心に始まりました．ただ，内容的に人工知能にも近いので，人工知能の研究者も多く加わっています．また，最近では，ニューラルネットワークを発端として，数理物理学者からの投稿も増えてきました．

そうしたいろいろな分野の論文を読んでいると，各分野の色というのが見えてきます．とくに，数理物理学的なアプローチと理論計算機科学的なアプローチは，かなり違います．この違いが，数学と計算幾何学の違いに通じる，と私は思っているのです．

実は，私は６月22日から７月４日まで，スロバキアとスロベニアに行っているので，その説明は，帰国後にゆっくり見ることにします．

まず，渡辺さんが想定している私の突っ込みは否定しませんが，「だから，コンピュータ・サイエンスは数学のうちだ」という結論を導こうとしてるのではありませんよ．私はあえてそういう結論を導こうと仕掛けますが，それに渡辺さんたちが対抗してくれることで，コンピュータ・サイエンス独自の観点が引き出せることを期待しているのです．

「それは数学じゃないか！」という言葉には，「数学を使って論証しているね」という意味でしかありません．それは，数学は使っているけれど，数学とは違う発想なり観点なりに基づいて，やっていることなんだという反論を期待しての突っ込みです．そして，その発想や観点が何かを明らかにしたい．

そこになかなか答えてくれないので，「数式」にこだわる数学（私はこだわっていないけれど）と「計算」に注目するコンピュータ・サイエンスという対立構造を提示してみたわけです．コンピュータ・サイエンスが何でも数式で書き下せるという幻想を打ち砕いてくれて，新しい世界観を開いてくれるのならいいのに．

以前，松井さんが言っていたと思いますが，個別事例をいろいろと検討して，それに共通する精神やそれが提示してくれる世界観が抽出していけるといいですね．くれぐれも，事情通どうしの知識の示し合いに陥らないように．

では，しばれらく沈黙します．

取りあえず，先の話の続きの計算論的学習理論の論文の話の続きをしましょう．根上さんの遺言にも関係ありそうですし．

さて，「学習」と言っていますが，人間をはじめ，生物が行っているような複雑な学習の話ではありません．大量のデータ中に隠れる，何かの法則を見出す方法（アルゴリズム）の研究が主たるテーマです．（もちろん，究極の目標の一つには，生物の学習アルゴリズムの解明もありますが．）

したがって，研究の内容としては，新しいアルゴリズムの提案とか，アルゴリズムの動き（学習過程）や性能（学習効率）の解析などがあります．従来は，計算機科学の分野でしたが，先にも言いましたように，いわゆる理論物理学系の論文もちらほら出るようになってきました．

そうした論文にも学習メカニズムの挙動や効率を解析したものがありますが，その解析手法には，ある種の色があります．たとえば，データ中のノイズに対する挙動を調べる論文だったとします．その場合，大抵は，「ノイズはガウス分布に従って生じる」といった類の仮定が出てきます．そうした仮定は，ある意味で妥当なのですが，それ以上に，仮定がなければ解析できないといった事情があるようです．この場合の「解析できない」とは，いわゆる数式をうまく操って，解析的な結果を出すということです．
 

つまり，そのような最悪の状況を考えても，何とかうまく学習できることを示そう，というわけです．

もちろん，敵にも一定の条件が課せられます．（そうでなくては，あまりに学習アルゴリズムに対して不利ですから．）ただ，その条件は，解析をやりやすくするためのものというよりも，設定をより現実的にするためのものがほとんどです．

だからといって，理論物理学的なアプローチが単純で，コンピュータ・サイエンス的なアプローチの方が高級だ，といっているではありません．

いくら仮定を導入したからって，そう簡単に数式をきれいにすることはできません．そこには，多くの技巧が必要ですし，また，深い理論を伴った数学も必要になります．いろいろな仮定を設けることで，より深い議論が可能になっているとも言えるでしょう．

一方，アドバーサリー論法のように，何でもあり，を相手にすると，なかなかよい結果が得られません．深い議論へと進むのが，なかなか難しい．ううんと苦労して，やっと丘を一つ登るといった状況でしょうか．さらに，登ってみると，そこには，すでに理論物理系の人たちが作った高速道路が走っていた，なんてこともあり得るわけです．

理論物理系の方のアプローチというのは，
単にその分野の方たちが使い慣れている道具を使っているというだけで，
「理論物理」という学問とあまり関係なかったりするのじゃないのですか？
コンピュータサイエンスの研究者のアプローチというのは，
「理論物理的？」でなく，「コンピュータサイエンス的？なのは，
どんなところなんでしょう．
 

非常に大雑把にいうと，理論物理の人たちのアプローチは，計算です．つまり，式を変形していって，所望の式を導き出すというやり方です．黒板一杯に式を導出して行って，最後に E = mc^2 を出す，といった流れです．

それに対し，理論計算機科学は，論理的な議論がかなり入ってきます．単純に言えば，いろいろな場合わけを考えているからかもしれません．そういったことは，いわゆる一つの式として導出できませんからね．

先日，理論物理学の先生で，最近，計算機科学に興味を持って，かなり深く勉強されている方のお話を聞く機会がありました．（本当によく勉強されているので，本職の私が恥ずかしい思いをしました．）その先生が，理論計算機科学のある種の研究を指して，論理学のようだ，と言われていました．多分，あまり肌に合わなかったのではないかと邪推しています．面倒な理屈を捏ね回しているように思えるのではないでしょうか？

スロベニアで開催されていたグラフ理論の国際会議に参加して，有意義な時間を過ごしてきました．

それとは裏腹に，２週間も大学を不在にしていると，仕事がたんととまっているはずです．それが片付くまで，しばらく二人のやり取りを傍観しています．

いずれにせよ，「学習理論」とか「論理の暗算」とか，渡辺さんの頭の中にあるイメージをもっと表現してみてください．

ようやく，出張前（明日から１０日ほどチェコへ出張です）のごたごたが片付いて，ほっと一息，コーヒーを飲みながら書いています．

さて，先日の Wigderson とのやりとりの話，例としてはちょっとまずかったですね．確かに，だれでも論理の暗算はやりますね（たとえば，シャーロックホームズも）．ただ，もう少し違うといいたいのですが，この話は，先に延ばしましょう．

それより，その前の（理論）物理学的アプローチと（理論）計算機科学的アプローチｈの違いについてもう少し突っ込んでみましょう．

もう少し言いましょう．私などから見ると，彼らの使う数式や変形手法には，それぞれそれなりの物理的な意味付けがつねにあるように思うのです．したがって，どんな式が成り立ちそうか，あるいはどんな式が導けそうか，ということに対するある程度の直観があって，その上で，目標に向かって進んでいると見えるのです．

計算機科学にも，もちろん直観する部分はある程度はあります．ただ，あえて言うならば，むしろその直観とは，距離をおいて，論理をベースにゴリゴリと証明していく，という雰囲気です．

もちろん，それは，松井さんの言われたように，使う道具の違いからくるという面もあります．ただ，そういった違った道具が使われるようになったには，わけがあると思うのです．たとえば，板前さんとフレンチのシェフが使う道具が違うのに理由があるように．

では，何が使う道具の違いを生み出し，そして，アプローチの違いを生み出しているでしょうか？その原因が，以前から言っているような扱う対象の違いです．つまり，自然物を対象とする学問と人工物を対象とする学問の違いだと思うのです．

だから扱う対象に自由度が非常にあり，何も仮定できない．そのために議論も慎重にしなければならなくなるのです．

根上さんは，それでは基礎科学にならないのでは，とおっしゃいました．何も構造がないのでは，深く理論を進めることができないと思われたからだと思います．でも，おもしろいことに，そういった構造なしの世界を対象としていても，かなり深い議論もできるのです．その一例として，計算の複雑さの証明の話を持ち出したわけです．

東工大では，高校生を対象にスーパーコンピュータコンテストをやっています．数セミでも毎回，紹介させてもらっています．

ある年，このコンテストの参加者を決めるための予選として，円周率 pi に対して (pi)^2/3 を 1000 桁計算する課題を考えました（正確な問題は忘れましたが，大体そんな問題です）．もちろん，より高速で，より単純なプログラムを作った人の方がよい成績というわけです．

この課題を考えられたのは，コンテストの委員会の中の物理系の先生だったと思います．

数値計算の技術やプログラムの技術を見る，ある意味でよい問題なのですが，私などには，少々，心配なところがあります．たとえば，あらかじめ (pi)^2/3 を 1000 桁計算しておいて，そして，それを単位プリント文で印刷するプログラムを解答として出されたらどうするのだろう？という心配です．1000 桁計算するのに，いくら時間がかっかても構いません．実際のプログラムは，ただ単に数字を印刷するだけのプログラムですから，超簡単，超高速です．

私がその心配を言ったとき，出題された先生は，「そんなのはずるいよ」と即座に否定しました．確かに心情はわかります．でも，計算機科学では，何がずるくて，何がずるくないかの基準を明確にしない限り，「ずるい」とは決められないのです．

この土俵の広さは，分野を散漫にする危険性を含んでいます．ただ，計算機科学では，まだまだ理論的な深さを保っていると思います．

一方，土俵の広さのお陰で，何でも手を出せます．松井さんは，ときどき「××は，我々の守備範囲外ですね」といったコメントをされますが，実は，
計算機科学には，あまり守備範囲外というのはありません．まあ，計算機科学者がそれだけ厚顔無恥なのかもしれませんが，．．．

たとえば，学習理論，情報理論，暗号，などなど，要は，頭に「計算論的」さえ付ければ，計算機科学になるのです :-)　ただし，計算論的脳科学というのはだめです．物理屋さんたちが，すでにそういった名前の分野を作ってしまっているので．．．

私など，最近，統計に興味を持ってまして，計算論的統計学といったような雰囲気のこともやっています．（尻が軽いというご批判はあるかと思いますが，．．．）

では，また．

いろいと揺さ振りを掛けているのに，いっこうに渡辺さんはいくつかの「思い込み」から脱してくれないような気がするのですが，どう思います，松本さん．「構造がない！」の一点張りだし．

私は，何かが議論できたり，理論が作り上げられるという時点で，そこには構造があると思っています．そして，一見，構造がないように見えるものに，構造を見出したり，もしくは，構造を付加することで，よりよく見えるようにして，現象を整理してり，その原理を探ったりするのが，学問や研究だと思うのですけどねぇ．

もし，本当に構造がないのなら，何も言えません．何も言えないということは，誰にも伝わらない．伝わらないから，誰も見ようとも，使おうともしない．そういうものが，基礎科学になりえると思いますか？

現在，動いている計算機科学の「項目」は渡辺さんの話からよくわかるのですが，それが基礎科学として成長する資格，もしくは，兆しがあるのかどうかという議論が足りない気がするのですが．

以前，「数式に執着している数学者（私はしてない）」のような話をしましたが，本当は数学者が数式に執着しているのではなくて，世間の人たちが，数学者は数式に執着していると，思い込んでいるだけです．

渡辺さんの言葉を信じると，物理系の人は直観をたよりに数式を運用していくけど，計算機科学者は直観を排して論理を運用していくのでしょ．数学者だったら，数式も論理も両方とも直観をたよりに運用しているのですけどね．

実は，こんな話があります．

あるとき，私のところに，大変長い論文が送られてきました．それはある有向グラフに関する論文なんですが，その詳しいところはどうでもよいでしょう．その論文では，ある条件を満たす有向グラフが有限個しかないことを示した上で，それを全部構成してみせるというものでした．

その前半の有限性の議論はよく書けているのですが，後半の例を構成する部分になると，その論理展開が極めて機械的になっていて，その部分が以上に長いのです．こんな長い議論をよくできるなあと，その著者にたずねてみたところ，Mathematicaでプログラムを組んで，その証明を生成したのだそうです．
どおりで，見事に直観を排した機械的な論理展開ができたわけです．

私は，そんな機械が生み出したものを人間の目に触れさせてはいけないと，彼にアドバイスをすることになるわけです．本質的な部分だけを人間の言葉で（直観をたよりに運用できる論理で）書いて，あとは機械で（直観を排した論理で）できると書くにとどめればよいと．

渡辺さんの言っている「論理をベースにゴリゴリと」というのは私が切り捨てようとしている機械的な論理のことなのでしょうか？だとすると，論理を暗算でできる計算機科学者というのは，機械みたいな人だといわざるをえませんね．

もちろん，論文の中では機械的な論理を排除することを求めていますが，昔に書いた私の発言からわかってもらえるように，私は，その機械的な論理自体を否定しているのではありません．そういう機械的な論理展開の末に見えてくれる現象だってあるのだという指摘は大事だと思います．それは数式ではなく，計算で見えてくる，もしくは記述できる現象だと言ってもいいでしょう．

そういう指摘をする，もしくはそういう「計算」という構造を付加することで見えてくる現象を解析する．それは計算機科学の（すべてではないにしても）１つの役目だ！そういう考えに同意してもらえると，計算機科学を基礎科学に加えてあげてもよい気にはなれるのですが，松井さんはどう思いますか？

ただ，コンピュータサイエンスでは，その前提や縛りの選択を，
陽な形で議論して設定する事が多く，
またそれ自体が大きな研究であることが多いのだと思います．
多分，物理のような学問では，
前提や縛りを自体を議論することは少ないのでしょう
（こんな展開は，前にも使った気がするな）.
渡辺さんは, 上記のような違いを指して, 
「計算機科学が, 構造(前提, 分野)にとらわれない」
という特徴とその魅力を主張しているのでしょう.

渡辺さんの言う通り，(多分)コンピュータサイエンスは,
いままでの科学とちがうのですから，
それが連れていってくれる世界は，何か新しいものなのです．
でもそれが何処なのか？という問いの答えが，
「構造を前提としていないから，何処でも行けるんだよ」じゃ，
困るのです.
困るというのは，それでは基礎科学にはなり得ないと思うからです．