# ヒューリスティック探索 ## 定義 ヒューリスティック探索とは、問題解決を「環境を記述する広大な可能性の迷路の探索」と捉えたうえで、その迷路を**選択的に**探索して扱える大きさに縮める方法を指す。Simon は問題解決をしばしばこの形で記述する。成功する問題解決とは、迷路を網羅的に踏破することではなく、選択的に探索して規模を管理可能な水準まで落とすことである。(Source: [[@1996__MITPress__The Sciences of the Artificial - Chapter 3 The Psychology of Thinking - Embedding Artifice in Nature]] p.54) > [!note] 用語について > 第 3 章の本文には "heuristic search"・"problem space"・"means-ends analysis" という語句そのものは現れない。本章が扱うのは、暗号算術問題を題材とした**選択的探索の具体例**と、それを可能にする戦略の学習である。探索の一般理論としての定式化は第 5 章(設計の科学)に送られている。 > 3 語はいずれも第 4 章で初めて本文に現れる。"means-ends analysis" は「第 3 章で既に同定した」一般過程として言及され(p.94)、"heuristic search" は発見プログラムの中心機構を「他ならぬ我々の旧友」と呼ぶ形で(p.106)、"problem space" は問題表現の言い換えとして(p.108-109)導入される。すなわち Simon は第 3 章で機構を具体例として示し、第 4 章で既知の術語として振り返るという順序を取っている。 ## 暗号算術問題における 3 段階の戦略 Simon は DONALD + GERALD = ROBERT(D = 5 が与件)を題材に、探索戦略の洗練が探索量をどう減らすかを 3 段階で示す。 1. **総当たり**: 10 文字への数字の割り当て 10! = 3,628,800 通りを系統的に生成・検査する。計算機なら現実的だが(1 件 0.1 秒でも最大 10 時間程度)、人間には不可能である。1 件 1 分としても数人年を要し、しかもどこまで試したかの記録に難儀する。(Source: ch.3 p.54-55) 2. **系統的割り当て + 早期の矛盾検出**: 右端から 1 文字ずつ割り当て、割り当てが完成する前に矛盾を検出することで、ありうる割り当ての「クラス」を一段でまとめて排除する。さらに、2 つの加数が判明した桁については和を直接計算して推論する。この方式では探索木は全体で 68 分岐にとどまり、紙と鉛筆で 10 分ほどで解ける。(Source: ch.3 "Search Strategies" p.56-57) 3. **決定性の高い桁を選ぶ**: 右から左へという系統的順序を捨て、新しい割り当てまたは推論を許すだけの決定性を持つ桁を探す。D = 5 から T = 0 と R が奇数であること、左端から R > 5 が出る。左から 2 番目の桁が O + E = O という特異な構造を持つことに気づけば E = 9 が定まり、R = 7 が確定する。こうして試行錯誤的探索をほぼ消去できる。ただしこの方法がすべての暗号算術問題で効くわけではない(例: CROSS + ROADS = DANGER)。(Source: ch.3 p.57-58) Simon はこれを「総当たり探索の代わりに、探索と『推論』を組み合わせた体系を置いた」と表現する。(Source: ch.3 p.57) ## 探索を縮める仕組みの限界と自己言及性 - 「矛盾を検出する」といっても、検出できるのは**比較的直接的な**矛盾だけである。直接・間接を問わずすべての不整合な含意を高速に検出できる過程があるなら、それは問題の解をほぼ即座に見つけてしまう。この問題では、唯一の正解以外のどんな割り当ての組も矛盾を含意するからである。(Source: ch.3 p.57) - 実際の「直接的な矛盾の探索」とは、新しい割り当てのあとに、その文字が現れる桁を調べ、可能ならまだ未割り当ての文字について解き、その数字が未使用のまま残っているかを検査する、という程度の処理である。(Source: ch.3 p.57) ## 戦略は学習された人工物である - 戦略がいったん選ばれてしまえば、探索の経過は**問題の構造だけ**に依存し、問題解決者の特性には依存しない。人や自動機械の遂行を観察して分かるのは、どの戦略が使われたか、誤りとその回復から見える記憶と基本処理の容量・正確さ・速度、そして状況次第でどの戦略を実際に獲得できたか、といったことに限られる。中枢神経系の神経学的特性については何も学べないし、その細部は可能性に境界を置く以上には行動に関係しない。(Source: ch.3 p.58-59) - 被験者によって適用する戦略は異なり、その洗練の度合いは数学への習熟度と相関する。ただし戦略をどう学習し、あるいは遂行中にどう発見するのかは十分には分かっていない。(Source: ch.3 p.62) - 人間は、教われば容易に使えるはずの巧妙な戦略を、自力ではしばしば発見しない(チェスの名人が初級者と指すのを見ればわかる)。(Source: ch.3 p.61) - 暗号算術課題で戦略以外に強く現れる人間の特性は、短期記憶の小ささだけである。より組合せ的な戦略の実行で被験者が苦しむのは、どこまで進んだか、どの割り当てを済ませたか、条件つきの割り当てにどんな仮定が伏在するかを忘れてしまうためであり、これは少数のチャンクしか短期記憶に保持できず、長期記憶への転送に時間が足りない処理器なら必然的に生じる困難である。(Source: ch.3 p.63) ## 探索の一般理論への接続 Simon は章末で、情報処理心理学を内側では生理学に接続し、外側では課題環境の側、すなわち**大規模な組合せ空間の探索の一般理論**に接続することになる、と述べる。そして「設計の理論とはその探索の一般理論に他ならない」として、議論を第 5 章に送る。(Source: ch.3 p.83) ## 横断的知見 - 探索木を全展開せず有望な枝を優先して伸ばす、という発想は [[モンテカルロ木探索]] と共通する。ただし枝刈りの根拠が異なる。Simon の暗号算術では、問題の構造から導かれる**論理的矛盾**によって枝が確定的に切られるのに対し、MCTS では行動価値と訪問回数に基づく**統計的な有望さ**の推定によって探索資源が配分される。前者は「探索と推論の組み合わせ」であり、後者は「探索とサンプリングの組み合わせ」である。(Source: [[@1996__MITPress__The Sciences of the Artificial - Chapter 3 The Psychology of Thinking - Embedding Artifice in Nature]], [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]]) - 意味的に豊かな領域では、探索の場そのものが変わる。第 3 章の暗号算術では、記憶の組織ではなく**問題の構造**が探索を導いた。第 4 章によれば、意味的に豊かな領域では問題解決の探索の大部分が**長期記憶の中で**行われ、そこで発見された情報に導かれる。医療診断では、探索が医師の医学知識という心的な図書館と患者の身体という 2 つの環境で交互に行われる。ヒューリスティック探索の対象は問題空間だけではなく、記憶そのものでもある。(Source: [[@1996__MITPress__The Sciences of the Artificial - Chapter 3 The Psychology of Thinking - Embedding Artifice in Nature]] p.54-58, [[@1996__MITPress__The Sciences of the Artificial - Chapter 4 Remembering and Learning - Memory as Environment for Thought]] p.87-88) - 熟達は探索を認識で置き換える。第 3 章は選択的探索が総当たりを 3,628,800 通りから 68 分岐へ縮めることを示したが、第 4 章はさらに先の縮約を示す。熟達者の「直観的な飛躍」の大半は認識の行為であり、パターンを認識した瞬間に、それに結びついた行動(オープンファイルを見てルークをそのファイルへ動かす可能性)が想起される。1 手 10 秒の対局でもマスターは相対的に強いチェスを指せる。探索の縮約は戦略の洗練だけでなく、長期記憶に蓄えた約 5 万チャンクの索引によっても達成される。(Source: [[@1996__MITPress__The Sciences of the Artificial - Chapter 3 The Psychology of Thinking - Embedding Artifice in Nature]] p.56-58, [[@1996__MITPress__The Sciences of the Artificial - Chapter 4 Remembering and Learning - Memory as Environment for Thought]] p.89-90) ## 未解決の問い - 第 5 章が約束する「大規模な組合せ空間の探索の一般理論」としての設計の科学は、本章の選択的探索の議論をどう一般化しているか。問題空間や手段目的分析といった定式化はそこで導入されるのか。 - 「探索を縮めるには推論が要るが、推論が強すぎれば探索そのものが不要になる」という第 3 章の指摘は、探索と推論のあいだにトレードオフの尺度がありうることを示唆する。この尺度は本書のどこかで定量化されるか。 - 第 3 章は戦略の学習・発見の機構を第 4 章に送った。第 4 章は例からの学習(David Neves)とすることによる学習(Anzai と Simon のハノイの塔)という 2 つの具体的な機構でこれに部分的に答えている。ただし答えられたのはプロダクションの獲得であって、第 3 章の暗号算術で被験者が示したような**戦略の水準の差**(数学への習熟度と相関する)がどう生じるかは、両章とも扱っていない。 ## 関連 - 章: [[@1996__MITPress__The Sciences of the Artificial - Chapter 3 The Psychology of Thinking - Embedding Artifice in Nature]] / [[@1996__MITPress__The Sciences of the Artificial - Chapter 4 Remembering and Learning - Memory as Environment for Thought]] - 概念: [[情報処理システムとしての人間]] / [[チャンクと記憶の制約]] / [[モンテカルロ木探索]] / [[問題の理解と表現]] / [[計算による科学的発見]] - 実体: [[Herbert A. Simon]] / [[Allen Newell]] / [[BACON]] - 書籍: [[The Sciences of the Artificial]] ## 出典 - Herbert A. Simon, *The Sciences of the Artificial*, third edition, The MIT Press, 1996, Chapter 3, pp. 51-84. - Herbert A. Simon, *The Sciences of the Artificial*, third edition, The MIT Press, 1996, Chapter 4, pp. 85-110.