フレーム問題に関する断想

ロボットにつけるクスリ―誤解だらけのコンピュータサイエンス

突然だけどこの本面白かった。フレーム問題、記号着地問題、行動AI、進化的計算、ゲーム理論、創発、チューリングテスト、自意識、自己言及など人工知能の哲学に関する興味深い話題がほとんど網羅されている。あと著者がSF好きとあって人工知能に関するSFもたくさん紹介されている。説明がかみくだかれていてひじょーにわかりやすいので人工知能の哲学的側面に興味がある人はこれから入るとよいかも。この本の後半にフレーム問題に関する学生の質問へのプロフェッサー星野の回答がある。ちょっと思ったことがあるのでメモ。

フレーム問題っていうのは、人工知能の難問の1つで簡単に言うと「ある問題を解くために、無関係な無数の知識を無視し、関係のある知識だけを有限時間で取り出すのが困難」という問題。デネットによる有名な例はフレーム問題（Wikipedia）を参照。

Q. 関係の深い情報の優先順位を高くし、低い順位の情報を無視することで、フレーム問題は解決するのでは？

A. 無視する時間が膨大になります。コンピュータにとって「無視する」という仕事も、ある時間（1億分の1秒としよう）を要します。膨大な（1兆個としよう）無視すべきデータがあるので、無視するだけでも長時間（1万秒＝約3時間も）かかります。

関係のない知識を無視するのに時間がかかるというのがフレーム問題だけど・・・これホントかな？ちょっと考えてみた。

ある選択をすることは、他のすべての選択肢を捨てることと同じ（これ真理ね）。つまり、他のすべての選択肢を捨てたければ（無視したければ）、ある1つの選択をすればよいわけだ。

これを実現するデータ構造としてハッシュがある。ハッシュはクエリとして与えたオブジェクトと「同一」のオブジェクトを計算量O(1)で見つける。ハッシュはハッシュ内のすべてのオブジェクトに対して同じか違うか調べるという方法は取らない。直接クエリと同一のオブジェクトを探し出す（＝クエリと異なるオブジェクトは全部無視される）。無視するのに時間なぞかからないのだ。

もう少し高級な例だとLocality Sensitive Hash (LSH)がある。LSHは「類似した」オブジェクトほど同一のハッシュ値を取る確率が高くなる特殊なハッシュ。LSHを使うとクエリと類似したオブジェクトを計算量O(1)で見つけられる。LSHはLSH内のすべてのオブジェクトに対して似てるか似てないか調べるという方法は取らない。直接クエリと類似したオブジェクトを探し出す（＝クエリと類似してないオブジェクトは全部無視される）。無視するのに時間なぞかからないのだ。

ここで、クエリ＝与えられた問題、類似した＝関係のある、オブジェクト＝知識と置き換えてみよう。すると与えられた問題と関係のある知識を直接探し出し、与えられた問題と関係のない知識は全部無視される。ハッシュなので関係のない知識を無視するのに時間なぞかからないのだ！

どこがおかしいのかな？ハッシュって衝突があるから表が巨大じゃないとO(1)で見つけられないんだよなー。無限個のオブジェクト格納したら衝突しまくりで探すのに無限の時間かかるからダメってこと？そういう問題なのかな。