総集編 No.7

鼎談の表紙へ， 鼎談のあらすじへ， キーフレーズから見た鼎談へ，

７．１．ＣＳの一例のアルゴリズムの研究の一例：回路計算量の研究例

それでは少し長くなりますが， 比喩ではなく本当の研究の話をしてみますね．

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

計算回路の複雑さ（回路計算量）の解析の話をします． まずは回路計算量ですが，ざっとまとめると次のようなことです．

計算回路と回路計算量： 計算回路とは， AND や OR や NOT などの素子を使って計算をする回路のこと． 計算問題の回路計算量とは， その問題を計算する最小の計算回路の大きさのこと． 与えられた計算問題の回路計算量を解析し， それによってその問題の困難性を示すというアプローチがある．

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

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

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

これには次のような， きれいな特徴付けが得られています．

段数を k 段に制限した多項式サイズの回路で計算できるような関数は， 高々 d(k) 次の整数多項式で近似できる．

この結果自体は Smolensky　というロシアの研究者の結果ですが， 関連の研究に日大の戸田さんや電通大の垂井さんが大きな貢献をしています．

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

長くなってしまってすみませんでした． なお，この例では k = 17 でも k = 18 でも特徴付けは同じようにできます． けれども， このような同じ特徴付けができない例もあります．

読み返すと， 根上さんが（わざと） 議論を大きく揺さぶっているのがよく分かりますね．

渡辺さんは， それに対し一貫して， 「計算」を対象にする研究は「実は難しいんだ」という主張をしているようですね． とくに「単純そうに見える」という誤解を持っている人に対して．

根上さんの質問には， 「計算」を対象にする研究には，こんな美しい世界もあるのだ， という話をこれから展開していけばいいのでしょう．

やっと目を覚ましたようだね．松井さん． 渡辺さんが忙しい間に二人きりでおしゃべりしていましょう．

いずれにせよ今回の渡辺さんの話は非常に具体的でよいです． やっと私の疑問に答えてもらえた感じです． でもやはり「17 回...」と「18 回...」の特徴づけの差はなかったんですね． ある意味では d(k) という値が指標となって， その二つを区別はできるけれど， 特徴づけのスタイル自体は同じです．

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

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

根上さんは 17 回と 18 回で特徴付けに使う道具（分野）が， まったく違うような例が欲しかったという意味ですか？

そうです． もしそういう例があれば， たかが手数の違いといえども「あなどれないな」という感じがしてきます．

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

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

う〜ん． 根上さんの要求しているのは， どうも数学的な特徴付けのように思われてしょうがないのですが．．．

もしうまく納得してもらったとしても，

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

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

７．２．ＣＳの一例：計算論的学習理論

ちょっと視点を変えてみましょう．

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

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

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

ほほー．それはどんな違いなのですか？ ただ， 私は少しの間， スロバキアとスロベニアに行ってきます． ですから， その説明は帰国後にゆっくり見ることにします．

というわけで，いくつか遺言を残しておきます．

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

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

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

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

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

まあ頑張ってみましょう．松井さん！

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

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

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

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

それに対して， コンピュータ・サイエンティストが同じようにノイズに関する議論をする場合をどうでしょう． かなり違ったアプローチを取ります． たとえば，アドバーサリー（敵者）論法というのがあります． いま解析している学習アルゴリズムに対して最も意地悪な敵を想定するのです． 「ノイズは，その敵が（こちらの手の内を読みきった上で）出すものだ」と考える枠組みです．

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

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

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

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

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

７．３．ＣＳ vs. 理論物理学

「学習」に関しては私はまったく素人なのですが， きっと読者にもそういう人が多いでしょうから怖がらずにいろいろ尋ねる事にします．

理論物理系の方のアプローチというのは， 単にその分野の方たちが使い慣れている道具を使っているというだけで， 「理論物理」という学問とあまり関係なかったりするのじゃないのですか？

コンピュータ・サイエンスの研究者のアプローチの「コンピュータサイエンス的？」なのは， どんなところなんでしょう？ 「敵は何でもあり」というところですか？

そんな場合でも， ある種のモデル・仮定・道具を使うのだと思うのですが， どんなものを使っているのですか？

はい， 「敵は何でもあり」というところがコンピュータサイエンス的なのです． もちろん，計算モデルを使って議論するわけですが，．．．

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

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

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

ＣＳ（とくに理論計算機科学）では， 機械的な論理の演繹に立ち戻って議論することが最終的に重要になります． まあ， 理論物理での道具が「式の計算」だったら， 理論計算機科学の道具は「論理の暗算」にでもなるでしょうかね．

論理的に議論するのは， どんな分野でも研究者として当たり前の気がしますが． 渡辺さんの言っている「論理の暗算」というのは， それとはちょっと質が違うんですね．

たしかに理論的な分野では厳密性が要求されます． ただ， 普通は直観が結構きく場合が多くて， 論理を厳密に追う必要がない場合が多いのではないでしょうか？ 一方，ＣＳでは直観が働かない（あるいは間違える）おそれがあるので， もっと厳密になってしまうのです．

アドバーサリー復活！

アンゴルモアの大王がスロベニアから帰国しました． グラフ理論の国際会議に参加して有意義な時間を過ごしてきました． それとは裏腹に，2 週間も大学を不在にしていると仕事がたんと待っていました． それが片付くまで，しばらく二人のやり取りを傍観しています．

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

それれは（理論）物理学的アプローチと（理論）ＣＳ的アプローチの違いについて， もう少し突っ込んでみましょう．

学習理論の話で私が言いたかったのは， いわゆる物理学系の人たちがやっている数学的解析と， ＣＳ系での数学的解析の違いです． 非常に簡単にいうと， 数式の変形を基にした導出と，論理の積み上げといった違いです．

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

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

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

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

ちょっと待って！ 「数式」と「論理」の対峙ですが，これは数学に対する偏見ではないかな．

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

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

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

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

どおりで見事に直観を排した機械的な論理展開ができたわけです．

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

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

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

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

７．４．人工物 vs. 自然物

先日「ファインマン計算機科学」（参考文献参照） という本の序を読んでいたら， ファインマンの言葉で

計算機科学は実際に科学ではないという点で物理学とは異なる． 計算機科学は自然を対象として研究しない．

という文章がありました． 渡辺さんのいう「人工物を相手にしている」という感覚は， これと近いのでしょうね． ちなみにその直後の文章は

数学的推論をかなり長々と使うが，数学でもない． 計算機科学はむしろ工学のようなものである．

です．

「計算」は有限個のルールの組み合わせで構成できるものは何でも表せてしまうのです． 私のいう「人工物」というのは， そういった種類のもの， つまり，少数の基本（ルールとか物体とか）を有限個組み合わせてできる物と考えて頂いても結構です．

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

「対象に何も仮定しない」という話の一例として， あるエピソードをご紹介しましょう．

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

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

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

このように， ＣＳが対象とする世界は妥当な方法で陽に制限しない限り， 何でもありな世界なわけです． 土俵が広いわけです．

この土俵の広さは分野を散漫にする危険性を含んでいます． ただ，ＣＳでは，まだまだ理論的な深さを保っていると思います． （その例を言おうとして計算の複雑さの研究の話を持ち出したのです．）

一方，土俵の広さのお陰で何でも手を出せます． そのため， ＣＳには守備範囲外というのは少ないのです． まあ，計算機科学者がそれだけ厚顔無恥なのかもしれませんが，．．．

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

う〜ん．しょうがないなぁ．

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

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

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

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

渡辺さの言う「構造が無い」というのは， 多分「構造が前提とされていない」が正しいことばなのでしょう．

根上さんの言うように， どんな学問でも， 議論をするには前提とする土台あるいは構造， つまり共通認識が必要なはずです． コンピュータサイエンスでも，それは同じです．

ただ，コンピュータサイエンスでは， その前提や縛りの選択を陽な形で議論して設定する事が多く， その設定自体が重要な研究であることが多いのだと思います． 多分， 物理のような学問では， 前提や縛りを自体を議論することは少ないのでしょう．

渡辺さんは, 上記のような違いをさして 「ＣＳが構造（前提や分野）にとらわれない」 という特徴とその魅力を主張しているのでしょう.

さて， 私達の議論の大もと「基礎科学云々」に戻ると， 「ＣＳが構造にとらわれない」という特徴と魅力を持っているとしても， それだけでは基礎科学となりうる理由としては弱い！ というのが根上さんの言っていることですよね．

これには私も肯きます. 「構造を前提としていないから自由に形を変えられる」 というのはいいことです． でも， 基礎科学として存在するには， その学問のもつ固有の力や美しさに加えて，

それを学ぶ者をどこに連れて行ってくれるのか？

という道が開けていてほしいですよね．

渡辺さんの言う通り， コンピュータサイエンスは（多分） いままでの科学とちがうのですから， それが連れていってくれる世界は何か新しいものなのです．

でも「それが何処なのか？」という問いの答えが， 「構造を前提としていないから何処でも行けるんだよ」じゃ，困るのです. それでは基礎科学にはなり得ないと思うのです．

==> １１月の鼎談へと続く

鼎談の表紙へ， 鼎談のあらすじへ， キーフレーズから見た鼎談へ，