人工知能と複雑性理論
2018/09/27 角川連続ナイトセミナー「人工知能と計算複雑性」概要
小論は、人口知能研究の今後の発展の方向を、数学的・物理学的認識可能性の理論でもある「複雑性理論」の成立・発展を中軸にして考察したものである。 なぜ、数学的・物理学的認識が問題になるのか？
もちろん、人工知能研究の基本的な問題は、「機械は考えることができるか？」という、チューリング以来の問題である。 「機械が考えること」の中に、感覚＝運動的な認識能力だけで無く、言語的な認識や数学的認識を含めると問題は急に難しくなる。ただ、こうした問題を避けるわけにはいかないと、筆者は考えている。また、人工知能は、理論的な構成物としてではなく、物理的なものとして実装されねばならない。
人間と機械の数学的・物理的認識の限界（筆者は、両者は同じ限界を持つと考えている）を知ることは、すなわち、人工知能の認識の限界を知ることに他ならない
スライドは、少し長く、一部は難しい表現も含まれているかもしれない。ただ、この問題領域での興味ふかいエピソードを沢山盛り込んだ。わからないところは飛ばして、面白そうなところだけ読んでもらっても、この世界の広がりは伝わると考えている。
資料の構成
はじめに
Part I 計算主義とコネクショニズム
人工知能論における「計算主義」とは、人間の「知能」の本質を「計算」として抽象しようとするものである。僕は、基本的には、「計算主義」の立場に立っている。
「知能」に対する「計算主義的」なアプローチは、僕が人工知能が将来実現すべき課題として関心を持っている、人間の「言語能力」や日常的な「論理的推論能力」、抽象的な「数学的能力」、さらには「科学する能力」の機械による実現には、そうしたアプローチが不可欠だと考えている。
Part II 計算可能性理論
ゲーデルの不完全性定理は、確かに驚くべきものではあるのだが、ほとんど役に立たない定理である。
というのは、言い過ぎなのだが、この定理から、我々人間の（同時に、それは人工知能にとっての）認識能力の限界を議論するのは、あまりに、荒い議論であると僕は考えている。
一つには、不完全性定理による原理的な「限界」以外にも、形式的演繹による認識には、実質的には、様々な「限界」が存在しているからだ。我々の形式的認識の「限界」を構成しているのは、不完全性定理だけではないのだ。
（あとで見るように、複雑性理論は、もっと精緻に、その「限界」を境界づけようとしている。）
Part III 計算複雑性理論
ある数学的命題Sの真偽を決定する「純粋に機械的手続き」は存在しないにせよ、そのSが、ある制限長さn以下の証明を持つかどうかを決定する手続きは存在する。単純に、長さn以下の証明を全て枚挙して、それが命題Sの証明になっているかをチェックすればいい。
しかし、この方法は指数関数的な時間を必要とする。P=NP?問題は、こうした問題を解く「高速」なアルゴリズムがあるかを問うている。その意味では、 P=NP?問題は、ヒルベルトの問題提起の現代版だと考えることができる。
Part IV 量子複雑性理論
「計算可能性理論」が、大きな転機を迎えるのは、1980年代に入ってからだ。
ファインマンが、コンピュータでは量子力学の法則に従う自然のシミュレートができないことに気づく。彼は、自然のシミュレートが可能なコンピュータは、量子力学の法則に従ったコンピュータでなければならないと主張する。
この指摘が、「量子コンピュータ」研究の始まりである。
数学的体系と同様に、自然もまた、我々の認識の対象である。数学だけでなく、物理学もまた、我々の認識の可能性と限界について、強い関心を持っているのだ。
Part V数学の「証明」をめぐって
昨年亡くなったVoevodskyは、Milner予想、Bloch-Kato予想を解くなど、代数幾何でグロタンディックが進もうとした道で、大きな業績を残した。ヴョブドスキーの最後の仕事は、数学の基礎とコンピュータに関係していた。 o彼は、数学の証明に、コンピュータを使うべきだと主張した最初の数学者の一人で、また、そのためのコンピュータによる証明支援システムのライブラリーUniMthを開発した。
まとめにかえて
複雑性理論は、かつての数学的・抽象的な認識の限界の理論（「チャーチ＝チューリングのテーゼ」）から、物理的・具体的ではあるが、観念の中にしかないものを対象にした限界の理論（「チャーチ＝チューリング＝ドイッチェのテーゼ」）へと発展してきた。かつ、それは、量子コンピュータが現実味を増すにつれて、より具体的な量子複雑性のもとでの限界の理論（「拡大されたチャーチ＝チューリングのテーゼ」）へと変化してきた。
人工知能技術を「機械に何ができるか？」という視点でだけ捉えるのは、狭いのだと思う。この分野で重要なことは、「機械に何ができるか？」ということではなく、「機械と人間で何ができるのか？」ということではないかと考えている。複雑性理論での、MAあるいはAM問題の捉え方は示唆的である。どちらかを人間にどちらかを機械と考えればいい。
