AIは何でも知っているが嘘を言うと考えると、AIの間違いを人が確認できるかという問題は

Merlin–Arthurプロトコルと同じ？（Merlin；証明者をAI,Arthur：検証者を人間と考える）

とか考えた、９月２９日のマルゼミ

人工知能と複雑性理論

をメモメモ

---

・複雑系とは全然違う話（複雑という言葉では似たようなところあるけど）
・人工知能研究の方向性を複雑性理論から考える
　　→数学・物理
　　　チューリング：機械は考えることができるか：この問題に答えていない
　　　　ディープラーニング：感覚
　　　　避けるわけにはいかない

・人工知能：どういう全体を持つのか→可能性と限界

・複雑性理論を視野に入れたほうが見とおしよくなる

・複雑性理論
　　ゲーデルの不完全定理：どこまでが計算可能？
　　　第一世代
　　　第二世代；
　　P=NP?　数学的に考えられている

　　　第三世代：量子コンピューターの登場
　　　　情報過程を物理過程で→物理過程＝情報過程
　　　　ホーキング敗れる　AdS/CFT対応の発見
　　ゲーデルの不完全性定理

　認識の限界→認識が進んでいる：大きな謎は残っている
　多項式時間の制約　無限を考えられる？

・計算主義とコネクショニズム
　計算主義とは何か？
　　人間の知能の本質を計算として抽象しようとする
　　感情や意識：当面保留

　計算：ある入力をある出力に変換する機能→機械と人間は等価

　Googleの巨大UCP　人間の手計算と同じ？　　おなじ
　要：計算能力→複雑性理論

　Nの多項式→やさしい
　べき乗→むずかしい

・複雑性理論
　　complexity Zoo https://goo.gl/eabDas

・知能の階層性
　感覚＝運動的な認識能力の上に、いくつかの階層が積み重なって構成
　言語能力：遺伝する
　社会史的な発展
　「文字による知識の集積」と「数学科学的認識」
　知識・複雑な構成
　視覚の発達→運動能力の発達：
　言語能力の獲得：赤ん坊は必ず言語を獲得する
　文字

　バビロニアの数学
　印刷
　機械制大工業

　技術と人口増：特異点がある→産業革命
　　文字　BC3000　数学BC2000
　文字は遺伝するものではない

・生物学的進化：一瞬で起きた
　　数学・科学的な認識　　　　　　数学的認識能力　　　計算主義
　　文字による知識の集積　　　　　　　↑累積的　　　　　↓　←検索・知識表現
　　言語能力による認識の飛躍　　　言語能力　　　　　　　↑
　　感覚・運動的外界の把握　　　　感覚運動能力　　　　DeepLearning

　知識の集積・時代を超えて情報を伝える

　他の動物にはない特徴

・文字だけの集積でできないことを人間はやらかした→人工知能苦手

・コネクショニズムの形式性の認識能力と生成能力
　ディープラーニングでできること
　　　形式的特徴を見出すことができる
　　　得た知見を明確に他に渡すことができない
　　　　　→言語はできる（情報の圧縮）
　　　　　→移転が難しい

・LSTMの能力について
　　Hochreiterの９０年代の発見
　　　　文法を機械に覚えさせる（４万回ぐらい学習すると）
　　　　足し算・掛け算も学習できる
　　　　ロジカルにIF文で書くと簡単→DeepLearningでもできる
　　　　　　文法は学習しても、意味は理解していない
　　　　　colorless green ideas sleep furiously

　RNN
・Linuxのプログラムを書かせる
　　文法性を認識できる
　図形のまねができない
　グラフ同型問題
　　　グラフ同型　NP
　　　部分グラフ同型　NP完全

計算可能性
ヒルベルト・プログラム
　　有限の操作でできるもの

げーでる不完全性

　証明できない→半鐘もできない

　無矛盾性を証明できない
・チャーチチューリングのテーゼ
　　　認識：限られている
　　　どんな証明は可能かは言っていない
　　　　　帰納関数論
　　　　　ラムダかりきゅらす
　　　　　チューリングマシン

・チューリングマシンの停止問題　　

・計算可能性→チューリングマシンで解けること

・チャーチチューリングのテーゼ

・計算主義の源流
　チューリングとチョムスキー
　チューリングの問題提起「機械は考えることができるか？」

・楽観論：１９５７　サイモン→外れた　石田晴久さん→外れた
　→原理的可能性

・文法の階層性
　チョムスキー　ヒエラルキーについて
　　　タイプ０～
　　　Hochreiter
　　　Karpathy　BNF
　自然言語：コンテキストフリーのちょっと先

・ミニマリストプログラムとマージ
　　人間の言語能力と数学の違い

・チョムスキー→５０年後→ミニマリスト

・有限の立場と照明論
　ゲンツェンの数論
　Proof theo
　カテゴリー文法

・一般帰納関数の計算可能性
　アッカーマン関数

・カントールの順序数

・計算複雑性
　　ナッシュ：絶対破れない暗号→指数関数的な手間
　　ゲーデル：チューリングマシンが有限なら
　→手紙

　計算複雑性　２つの起源
　　チャーチチューリングのテーゼ

　計算機：計算する機械
　CookとLevin：新しい計算理論

７０年代
　　計算複雑性理論　P=NP?
　　計算可能性理論　チャーチチューリングのテーゼ
　　　　イプシロンゼロを使って、違う見方

・NP問題
　　素因数分解

　P：多項式時間
　NP(Pを含む）検証が多項式時間
　NPハード：指数時間かかる
　NP完全：NPハード＋NP
　→PはNPは含んでいるかも？
　　ミレニアム問題の１つ

・複雑さについての多様なアプローチ
　コルモゴロフの複雑性
　チャイティンの不完全性定理：

　マンデンブロー：複雑性で言われるが、簡単（フラクタル図形）
　惑星の描写:小さなプログラムで複雑なものを表現できる。

　我々の手の届かない有限：Busy Beaver（忙しいビーバー）問題

・量子複雑性理論
　８０年代
　ドイッチェ：
　　　チャーチチューリング　ドイッチェのテーゼ：物理的計算可能性
　　→計算可能性の概念が物理化
　　　　情報過程＝物理過程

　ファインマン　１９８２年"Simulating Physics with　Computers

　　計算過程＝物理過程＝情報過程

・ベルンシュタインとバジラーニ
　１９９３年　“Quantum Complexity Theory”
　BQP　P→量子コンピューターで多項式時間で解ける

・量子複雑性理論
　１９９３年　“Quantum Complexity Theory”　同じ題で出している
　　BQP:多項式時間　やさしい

・ショア
　多項式時間で素因数分解が量子コンピューターならできる
　→量子コンピューターでは多項式時間で容易にとけるものがあり、その１つが素因数分解
　　　１９９４　BQP

→　１９９３年　“Quantum Complexity Theory”

→NPの中には量子コンピューターを使っても、簡単に解けないものがあると思われている


　NPにBQPは含まれない
　近似解をBQPで解くというのが、行われている

・９０年代：量子コンピューター
　拡張したチャーチチューリングのテーゼ
　　→BQP

・物理過程に注目すると、NP完全を解く方法がある
　石鹸コンピューター（あやしいやつもある）

　NPを解く→ランダムに出す：人柱作戦
　物理と計算科学の橋渡し

　ブラックホールコンピューター：時間が止まってしまい・・

・物理学と量子情報理論
　ブラックホールで情報は？
　エンタングルメント：笠　高柳

・物理学：Susskind　真ん中に量子情報理論
　高柳　重力理論と量子エンタングルメント

・現在
　複雑性理論の体系ができて、それが影響している

・ヴォヴォスキー

・複雑性理論のクラス　Merlin-Arthurクラス
　QMA
　マーサーアーリンは知っといて！

・２１世紀にはいると量子情報理論と複雑性理論の関心が高まる
　　→計算複雑性理論

・Coqの照明支援
　　人間の証明を機械が支援→機械の証明を人間が支援：共生している