知的情報処理 其の三 20171020

探索についての続きをやっていきます。

問題分解法

　そのままでは解決不可能な大きな問題を、解決可能な小さな問題に分解して段階的に問題を解決していく方法。ここで使われるのはAND-OR木だ。AND分岐は、分割後の問題を両方解かないと解にたどり着かない。OR木はそのどちらかで解になる。
　次に、この問題分解法を用いるために必要な要素を書いていく。

• 元問題：これから解く問題
• 原子問題：簡単に解決できる問題
• オペレータ：問題を分割するための規則

また、問題を分割していく上での条件は

• 分割された問題は独立
• どちらの問題から解いてもいい

　この探索方法にも盲目的、発見的探索方法があるので、見ていく。

盲目的探索

　この探索方法にも状態空間探索の時と同じように「深さ優先探索」と「幅優先探索」が存在するか、同じ説明になるので割愛。以下では、AND分岐とOR分岐を次のように表すものとする。

そして、具体的に製品の売れ行きを上げたいという問題を解決していくものとする。
　さて、製品の売れ行きを上げる（問題Aとする）にはどうすればいいだろうか。考えられるのは２つ（もちろん、もっとあります）

• 製品の価格を下げる（Bとする）
• 製品の品質を向上させる（Cとする）

これで、元問題Aをちょっと簡単なBとCという問題のどちらかを解決すればいい、と変換することができた。このプロセスを次はBに関してやっていく。製品の価格を下げるにはどうすればいいだろうか…。

• 大量生産（D）
• 人件費削減（E）

などいろいろ。これは、突き詰めていっても解決できる原子問題に落とし込むのは難しいだろう。そこで問題Cを考えていく。
　品質向上のためには

• 機能追加（F）
• デザイン変更（G）

のどちらかを解決すればいいだろう。デザインの変更は、

• パッケージデザインの変更（H）
• 製品デザインの変更（I）

など、もっと小さな問題に落とし込むことができる。ここまでやってようやく原始問題っぽくなってきた。
　このように、小さな問題に問題を分割して、具体的な解決案を模索していくのが盲目的な探索になってくる。ブレインストーミングを用いて考えをまとめていくのと似ている。上の問題を木構造に対応させると次のようになる。

ここでは、問題H、問題Iを解決することで元問題Aを解決すると仮定する。その時

このようなグラフ構造を解グラフと呼ぶ。
　企画運営において、どこが分解しやすいかを考えながら解決し行くことは非常に重要になってくる。

発見的探索

　今度は、オセロや将棋、囲碁などの対戦相手がいる問題を解いていくものとする。ここでの木構造は、２手先、３手先の盤面を網羅的に表したものになる。これをゲーム木と呼ぶ。しかし、これでは組み合わせ数の爆発が起こってしまい、通常の探索だと終わらない。そこで、「ミニマックス探索」とそれを改良した「アルファ・ベータ探索」が用いられるようになった。

ミニマックス探索

　相手は自分にとって不利になる手を打つと仮定（ミニ）して、その中で自分は自分の有利になる最善の手を打つ（マックス）。相手は論理的な判断のもとに手を打つと仮定する（あえて囮を置いたりしない）。ここでいう有利というのは、発見関数が大きいものとする。
　この方法は数手先までの拡張が容易だが、どうしても計算量が膨大になってしまう。また、発見関数を見つけるのが難しい。オセロのように白黒の数だったら分かりやすいのだが、将棋・囲碁になってくると、どの盤面が自分にとって有利なのかが判断しにくく、最適な発見関数がなかなか見つからない。

アルファベータ探索

　ミニマックス探索を少し改良したもの。最大評価の下限（アルファ）と最小評価の上限（ベータ）を決めることにより、枝刈りを行っていく。ここでは、「自分→相手→自分」までの3手先の発見関数値から探索していくことを考える。グラフは次のようなものを仮定し、探索方法は深さ優先探索とする。

以下手順

1. Cの値が5に決まる→相手はC,Dの中から少ないほうを選ぶので、Aの値が5以下であることが分かる（β値）
2. Dの下を調べると、最初に6が出てくる→自分はD下の数の中で一番大きいものを選ぶので、Dは6以上だとわかる（α値）→Aは5以下なので、残りの枝は切り捨ててOK（βカット）→Aの値が5に決まる
3. Eの値が4と決まる→Bの値が4以下であることが分かる（β値）→Aの値は5なので、この時点でA>Bが確定する→Eの下を切り捨てることができる（αカット）

これで、自分にとって最善なたを3手先の発見関数値から求めることができた。先に状態の条件を確定しておくことによって、その後の探索をカットすることができるのがこの方法のいいところだ。
　しかし、発見関数の値によっては、全くカットできないなんてこともある。全てカットできなかった場合は、ミニマックス探索と同じになる。また、いくら探索をカットできたとしても、計算量はどうしても発散してしまう。

結局どっちがいいのか

　解が一本の経路の場合は状態空間探索。木やグラフ構造で表される場合は問題分割探索。また、これらすべてを合わせて問題空間と呼ぶ。

推論

　既存の知識でもって、新しい知識を作ることをどのようにコンピュータにやらせるのかを考えていく。
　推論には大きく三種類ある。

• 演繹推論：既知識を解析することで有効的な知識へ変化させる
• 類推推論：ある対象で成立する関係を、ほかの対象でも成立するように変更する
• 機能推論：具体例から一般的な法則を導く

　それでは、各推論手法についてみていく。

演繹推論

　これは数学の公式を新しく作るようなもの。この公式を一回手に入れれば、その後同じパターンの事象が出てきたときに、すぐ答えを手に入れることができる。
　この手法に必要なものは二つ。

• 既存知識
• 既存データ

　既存知識とは、例えば「、」のような論理関係を表す法則。既存データとは、「今、とが成り立っている」などの情報のことをいう。この場合、演繹推論によって得られる知識は「が成り立っている」ということ、または「」という関係式になる。そして、演繹推論によって得られた関係式のことを合成ルールと呼ぶ。

プロダクションシステム

　上のような仕組みをシステム化したものはプロダクションシステムと呼ばれる。このシステムは大きく二つに分けられる。

• 前向き推論
• 後ろ向き推論

　前向き推論とは先の例のような、ある状態が成り立っている結果、何が成り立つのかを推論していくシステムになる。これだけではつまらないが、プロダクションシステムの醍醐味は後ろ向き推論にある。
　後ろ向き推論とは、結果から現在どのような状態なのかを推論するシステムだ。結果から原因を推論してくれるシステムになる。ただ、その原因は必ず正しいとは言えない。
　講義で出てきた例を引用するなら、「寒気」と「鼻水」という二つの状態が成り立っているとき、「風邪です」と言ってくれるのが前向き推論。「風邪をひいている」という結果が分かった状態から「もしかして、寒気と鼻水がひどくないですか？」と言ってくれるのが後ろ向き推論。この時、実際は「鼻水は出てない」かもしれない、というのが先ほど「必ず正しいとは言えない」といった理由になる。

問題点

• 問題を解くことによりルールが増える。したがって、あまり問題を解きすぎるとルールを探すのに時間がかかってしまう。
• 適用したルールが失敗すると、バックトラックして再度同じ間違いをする。
• 入れた知識以上のことは得られない。

類推推論

　常に正しい知識をれられるとは限らないが、新しい状況に適応できる可能性がある。
　具体例を挙げると、「Aさんはマスクをしている。Aさんは風邪をひいている」という知識を持っていたとする。この知識を持ってマスクをしているBさんを見たらどのように推論するだろうか。きっと「Bさんは風邪をひいている」と推論するだろう。これこそが類推推論のいいところで、Bさんについての情報は無いにもかかわらず、「マスクをしている」という類似性の元で「Bさんは風邪だ」という知識を得た。
　既存知識を新しい対象に当てはめることで、知らないことまで知識にすることができた。しかし、Bさんは花粉症対策のためにマスクをしている可能性だってある。間違っている可能性もあるが、新しい知識を得られたことの重要度は大きい。

付けたし

　今回は、探索の続きと推論の前半についてでした。いよいよ人工知能感が増してきたって感じです。プログラムに落とし込みたいんですが、なかなか時間がなく…。課題のこともあるので、ぼちぼちやっていかないとなぁと考えてます。