推論・探索・知識表現の基礎

推論・探索・知識表現の基礎 — 概要

状態空間探索、論理推論、知識表現、プランニングまで、記号的AIの中核技術を体系的に学ぶ入門ガイド

状態空間表現 — 問題を状態と操作で定式化する枠組み

状態、初期状態、目標状態、オペレータ、状態遷移グラフ、8パズルや宣教師と人食い人種問題での例示

問題の定式化 — 行動・経路コスト・目標判定の設計

行動集合、遷移モデル、経路コスト、目標判定関数、抽象化の粒度、実世界問題からの問題定義の切り出し

幅優先探索 — 浅い順に展開する完全な無情報探索

FIFOキュー、完全性、最短ステップ解の保証、指数的メモリ消費、分岐因子と探索深さによる計算量解析

深さ優先探索 — スタックで深く潜る省メモリ探索

LIFOスタック、後戻り、線形メモリ、無限経路での不完全性、深さ制限探索による打ち切りとその限界

反復深化探索 — 深さ制限を増やし完全性と省メモリを両立

深さ制限の漸増、再展開コストの解析、幅優先の完全性と深さ優先の省メモリ性の両立、ゲーム木での利用

均一コスト探索 — 経路コスト最小を保証する展開順制御

優先度付きキュー、経路コストgによる展開、ダイクストラ法との関係、非負コスト条件、最適性の証明

双方向探索 — 初期側と目標側から同時に掘り進める手法

前向き・後ろ向き探索の同時実行、フロンティアの出会い判定、探索量の平方根オーダー削減、適用条件

ヒューリスティック関数 — 目標までの残距離を見積もる評価

マンハッタン距離、ミスタイル数、緩和問題からの導出、支配関係、精度と計算コストのトレードオフ

A*探索 — f=g+hで最良優先に展開する最適探索

評価関数f(n)=g(n)+h(n)、オープン・クローズドリスト、許容的hによる最適性、経路探索への広い応用

許容性と無矛盾性 — h関数が最適解を保証する条件

許容性（過大評価しない）、無矛盾性（三角不等式）、再展開の有無、最適性証明、ヒューリスティックの比較

IDA*とメモリ制限探索 — A*の記憶量を抑える反復手法群

f値を閾値とする反復深化、再帰的最良優先探索RBFS、SMA*、メモリと再計算のトレードオフ

パターンデータベース — 部分問題の厳密解を表引きする技法

部分パターンの全解事前計算、15パズルやルービックキューブへの適用、加法的パターンデータベース

貪欲最良優先探索 — h値のみで進む高速だが非最適な探索

評価関数f=h、目標への直行性、最適性の欠如、行き止まりへの脆弱性、A*との比較、実用場面

ビームサーチ — 上位k候補のみ保持する幅制限探索

ビーム幅k、メモリ上限下での探索、解の見落としリスク、音声認識や機械翻訳のデコーディングでの利用

山登り法 — 局所改善のみで進む局所探索と停留点問題

近傍の最良移動、局所最適・台地・尾根での停滞、ランダム再スタート、確率的山登り法の変種

焼きなまし法 — 温度で悪化受理を制御する確率的局所探索

温度スケジュール、悪化解の確率的受理、冷却率、金属焼きなましとの類推、大域最適への漸近的収束

遺伝的アルゴリズム — 交叉・突然変異・選択による進化計算

個体群、適応度関数、ルーレット選択、交叉、突然変異、世代交代、スキーマ定理、組合せ最適化への応用

タブーサーチ — 禁止リストで巡回を防ぐメタヒューリスティック

タブーリスト、短期記憶による巡回回避、アスピレーション基準、多様化と集中化、スケジューリング応用

制約充足問題（CSP） — 変数・領域・制約で表す問題クラス

変数、値領域、制約グラフ、地図彩色、n-クイーン、数独、時間割問題、CSPとしての定式化の利点

バックトラッキング探索 — 変数順序と値順序の工夫

深さ優先の割当と後戻り、最小残余値（MRV）、次数ヒューリスティック、最小制約値、前方チェック

制約伝播 — アーク整合性による領域の事前刈り込み

アーク整合性、AC-3アルゴリズム、ノード整合性、経路整合性、伝播と探索の組合せによる高速化

局所探索によるCSP — min-conflictsヒューリスティック

完全割当からの修復、衝突最小の値選択、百万クイーン問題の高速解法、位相転移と問題の難しさ

ゲーム木とミニマックス法 — 二人零和ゲームの最適戦略

ゲーム木、MAX/MINノード、ミニマックス値、後退帰納法、評価関数、探索深さと棋力の関係

アルファベータ枝刈り — 無駄な部分木を切る探索削減

α値とβ値、カットオフ、手順序の重要性、最良手順で探索量が平方根に、反復深化との併用、置換表

期待値ミニマックス — 偶然要素を含むゲームの探索

チャンスノード、期待値計算、バックギャモンなどサイコロゲーム、評価関数のスケール依存性

モンテカルロ木探索（MCTS） — 乱択シミュレーションの木探索

選択・展開・シミュレーション・逆伝播の4段階、UCB1による探索と活用の均衡、囲碁AIでの成功

ゲームAIの歴史 — チェッカーからチェス・囲碁への到達

サミュエルのチェッカー、Deep Blueの対カスパロフ戦、Chinookのチェッカー完全解析、AlphaGo

命題論理 — 真理値と結合子による知識の記述

命題変数、論理結合子、真理値表、恒真式、充足可能性、含意と同値、標準形（CNF/DNF）への変換

一階述語論理 — 量化子と述語による表現力の拡張

述語、項、関数記号、全称・存在量化子、解釈とモデル、スコーレム化、知識ベースの一階論理記述

推論規則と健全性・完全性 — 論理的帰結の形式化

モーダスポネンス、全称例化、健全性、完全性、ゲーデルの完全性定理、決定不能性と半決定可能性

導出原理（リゾリューション） — 反駁による自動証明の基盤

節形式への変換、導出規則、反駁完全性、空節の導出、証明戦略（単位優先、集合支持）

単一化（ユニフィケーション） — 項を一致させる代入の計算

代入、最汎単一化子（MGU）、出現検査、単一化アルゴリズム、リゾリューションと論理プログラムでの役割

ホーン節と論理プログラミング — Prologの理論的基礎

ホーン節、確定節、SLD導出、Prologの実行モデル、カット、失敗による否定、宣言的プログラミング

前向き推論 — データ駆動で結論を導く推論方式

事実からルール適用を繰り返す前向き連鎖、プロダクションシステム、競合解消戦略、監視・制御系での利用

後ろ向き推論 — ゴール駆動で前提を遡る推論方式

目標からサブゴールへの分解、後ろ向き連鎖、証明木、診断・質問応答での利用、前向き推論との使い分け

Reteアルゴリズム — ルールマッチングを高速化する技法

パターンネットワークの共有、部分一致の記憶、作業記憶の差分伝播、大規模ルールベースの実用化

SATソルバ — 命題論理の充足可能性判定エンジン

DPLL法、単位伝播、節学習（CDCL）、再スタート、変数選択ヒューリスティック、検証・計画への応用

SMTソルバ — 背景理論付きの充足可能性判定

等式理論、線形算術、配列理論、ビットベクトル、理論結合、プログラム検証やシンボリック実行での利用

自動定理証明と証明支援系 — 数学的証明の機械化

一階自動証明器、対話的証明支援系、四色定理の機械検証、形式化数学、ソフトウェアの形式検証

モデル検査 — 時相論理による仕様の網羅的検証

線形時相論理LTL、計算木論理CTL、状態爆発問題、記号モデル検査、ハードウェア・プロトコル検証

意味ネットワーク — ノードとリンクによる概念の関係表現

is-aリンク、part-ofリンク、継承、活性拡散、初期の連想記憶モデル、フレームやオントロジーへの発展

フレーム理論 — スロットとデフォルト値による構造化知識

ミンスキーのフレーム、スロット・フィラー、デフォルト値、デーモン手続き、オブジェクト指向への影響

スクリプト理論 — 定型的な出来事系列の知識表現

シャンクとエイベルソンのスクリプト、レストランスクリプト、概念依存理論、物語理解と省略の補完

オントロジー — 概念体系の明示的な仕様化

概念階層、関係、公理、上位オントロジー、ドメインオントロジー、語彙統制、知識共有と相互運用性

記述論理 — 概念の包摂関係を扱う決定可能な論理体系

TBoxとABox、概念構成子、包摂判定、タブロー法、表現力と計算量のトレードオフ、OWLの理論基盤

セマンティックWeb — Web上の機械可読な知識基盤

RDFトリプル、RDFS、OWL、SPARQLクエリ、URI、リンクトオープンデータ、語彙の再利用

知識グラフ — エンティティと関係の大規模グラフ構造

トリプルストア、エンティティリンキング、Wikidata、DBpedia、検索エンジンでの知識パネル活用

Cycと常識知識ベース — 常識の大規模手作業符号化の試み

Cycプロジェクト、ミクロ理論、常識推論の困難さ、ConceptNetなどクラウド型常識知識との比較

WordNetと語彙知識資源 — 語彙間の意味関係のデータベース

同義語集合synset、上位語・下位語、全体・部分関係、語義曖昧性解消、多言語WordNetの展開

エキスパートシステム — 知識ベースと推論エンジンの分離

MYCIN、DENDRAL、知識ベース、推論エンジン、説明機能、1980年代の商用化ブームと限界

知識獲得ボトルネック — 専門知識の形式化の困難

知識工学、専門家インタビュー、プロトコル分析、ルール抽出、保守コスト、機械学習への移行の背景

不確実性下の推論 — 確信度と確率による不確実知識の扱い

MYCINの確信度因子、確率的推論への批判と発展、主観確率、不確実性表現の諸方式の比較

ファジィ論理 — 段階的な真理値による曖昧さの表現

メンバーシップ関数、ファジィ集合、ファジィ推論、非ファジィ化、家電・制御分野での実用化

デンプスター・シェーファー理論 — 証拠の信念関数による統合

信念関数、尤度関数、証拠結合則、無知の表現、確率論との違い、センサー融合への応用

ベイジアンネットワーク基礎 — 条件付き独立の有向グラフ表現

有向非巡回グラフ、条件付き確率表、d分離、確率伝播、診断・原因推論、記号的推論との接点

非単調推論 — 追加情報で結論が撤回される推論

単調性の破れ、飛ぶ鳥と例外のペンギン、非単調論理の諸体系、常識推論の形式化への動機

デフォルト論理 — 例外を許す規則による推論の形式化

ライターのデフォルト規則、拡張の概念、正規デフォルト、複数拡張の問題、常識知識の記述

閉世界仮説と失敗による否定 — 記載なき事実の否定的解釈

閉世界仮説CWA、開世界仮説との対比、失敗による否定、データベース意味論、Prologでの実装

サーカムスクリプション — 述語最小化による常識推論

マッカーシーの提案、異常述語の最小化、二階論理による定式化、フレーム問題への適用の試み

真理維持システム（TMS） — 導出依存関係の記録と信念管理

正当化の記録、依存関係逆伝播、矛盾解消、仮定ベースTMS（ATMS）、推論の撤回と再利用

信念改訂 — 新情報と矛盾する知識ベースの整合的更新

AGM公準、拡張・縮約・改訂の三操作、最小変更原理、認識的固執、知識ベース更新との区別

アブダクション（仮説推論） — 最良の説明を求める推論

観測から仮説への逆向き推論、診断への応用、説明の最良性基準、演繹・帰納との論理的対比

演繹・帰納・類推 — 三つの推論形式の性質と比較

演繹の真理保存性、帰納の一般化と不確実性、類推による写像、構造写像理論、推論形式の使い分け

事例ベース推論（CBR） — 過去事例の再利用による問題解決

検索・再利用・修正・保持の4Rサイクル、類似度計算、事例ベースの保守、ヘルプデスク・診断への応用

プランニングの基礎とSTRIPS — 前提条件と効果による行為表現

STRIPS表現、前提条件、追加・削除リスト、状態の論理表現、ブロックワールド、進行と回帰の探索

PDDL — プランニング問題の標準記述言語

ドメイン定義と問題定義の分離、型付きオブジェクト、数値・時間拡張、プランナ間の共通ベンチマーク化

部分順序プランニング — 最小拘束による柔軟な計画生成

因果リンク、脅威の解消、順序制約の最小化、最小拘束戦略、全順序プランニングとの比較

GraphPlan — プラングラフを用いた計画探索の高速化

プラングラフの層構造、相互排除関係、到達可能性解析、解抽出、後続のヒューリスティック計画への影響

階層型タスクネットワーク（HTN） — タスク分解による計画

複合タスク、分解メソッド、プリミティブ行為、ドメイン知識の活用、ゲームAIや実務計画での採用

状況計算 — 一階論理による行為と変化の記述

状況、流動命題（フルーエント）、後継状態公理、行為の前提条件、マッカーシーによる定式化

フレーム問題 — 変化しない事柄の記述をめぐる難問

慣性の公理化、資格問題、波及問題、後継状態公理による解決、哲学的フレーム問題への波及

手段目標分析とGPS — 差異削減による汎用問題解決

ニューウェルとサイモンのGeneral Problem Solver、現状と目標の差異、オペレータ選択、部分目標設定

物理記号システム仮説 — 記号操作としての知能の主張

ニューウェルとサイモンの仮説、記号と指示、十分性と必要性の主張、記号接地問題からの批判

SHRDLUと積み木の世界 — 言語理解と計画の初期統合

ウィノグラードのSHRDLU、積み木世界での対話、手続き的意味論、マイクロワールド研究の意義と限界

Logic Theoristと初期の記号AI — 定理証明プログラムの誕生

ニューウェル・サイモン・ショーによる開発、数学原理の定理証明、ダートマス会議、ヒューリスティック探索の起源

時間推論 — 時点と区間による時間的知識の表現

アレンの区間代数、13の区間関係、時点論理、時間制約ネットワーク、スケジュール推論への応用

空間推論 — 定性的な空間関係の代数的表現

領域結合計算RCC-8、位相関係、方位関係、定性空間推論、地理情報システムやロボットでの利用

定性推論 — 数値を使わない物理系の挙動予測

定性物理、定性微分方程式、エンビジョニング、順序尺度での状態記述、装置の故障解析への応用

様相論理と認識論理 — 可能性・知識・信念の論理化

可能世界意味論、必然と可能の演算子、知識演算子、共有知識、マルチエージェントの認識状態の記述

エージェントアーキテクチャ — 知覚から行動までの設計様式

単純反射型、モデルベース型、目標ベース型、効用ベース型、包摂アーキテクチャ、熟慮と反応の統合

BDIモデル — 信念・願望・意図によるエージェント設計

信念・願望・意図の三要素、実践的推論、コミットメント戦略、プラン ライブラリ、エージェント言語への実装

黒板アーキテクチャ — 複数知識源の協調による問題解決

黒板（共有作業領域）、知識源、制御機構、音声理解システムHearsay-IIでの起源、機会主義的推論

回答集合プログラミング（ASP） — 安定モデルによる宣言的解法

安定モデル意味論、否定を含むルール、グラウンディングとソルバ、組合せ問題の宣言的記述

制約論理プログラミング — 論理と制約解消の統合

CLPスキーム、有限領域制約、算術制約、制約ストア、Prolog処理系の制約拡張、スケジューリング応用

モデルベース診断 — 装置モデルと観測の食い違いから故障推定

整合性ベース診断、最小診断、構造と挙動のモデル、複数故障の扱い、回路・プラント診断への応用

スケジューリングと割当問題 — 探索・制約技術の実務応用

ジョブショップスケジューリング、時間割作成、乗務員割当、資源制約、CSPと局所探索の併用

経路探索の実応用 — 地図ナビとゲームAIの探索技術

カーナビの経路計算、グリッドマップ探索、階層的経路探索、ゲームキャラクタの移動、動的再計画

組合せ爆発と計算量 — 探索空間の指数的増大への対処

分岐因子と深さ、NP困難性、位相転移現象、問題分解、抽象化、近似解法による現実的対処

探索・プランニングの評価 — ベンチマークと競技会文化

国際プランニング競技会IPC、SATコンペティション、標準問題集、被展開ノード数・計画長などの評価指標

GOFAIと記号主義論争 — 記号処理AIの興隆と批判の歴史

記号主義とコネクショニズムの対立、AIの冬、エキスパートシステムの盛衰、記号接地問題、中国語の部屋

オントロジーアラインメント — 異種知識体系の対応付け

概念マッチング、語彙類似度、構造的類似度、マッピングの評価、異種データベース統合への応用

知識グラフ埋め込み — 記号的知識のベクトル空間表現

TransEなどの並進モデル、リンク予測、知識グラフ補完、記号表現と分散表現の橋渡し

ニューロシンボリックAI — 記号推論とニューラルネットの統合

論理制約付き学習、微分可能推論、ニューラル定理証明、記号的知識注入、頑健性と説明性の両立の追求

大規模言語モデルと記号推論 — 生成AI時代の推論・探索

思考連鎖プロンプティング、外部ソルバ・ツールの呼び出し、検索との組合せ、論理的整合性の課題

常識推論の評価 — ベンチマークによる常識能力の測定

ウィノグラード スキーマ チャレンジ、照応解決、物理・社会常識の質問応答、評価の妥当性論争

議論（アーギュメンテーション）理論 — 論証の攻撃関係の形式化

ダングの抽象議論フレームワーク、攻撃関係、許容集合の意味論、非単調推論との関係、法的推論への応用

認知アーキテクチャ — 人間の認知を模す統合推論基盤

Soar、ACT-R、プロダクション規則、宣言的記憶と手続き的記憶、チャンキング、認知モデリング研究

説明可能性と記号的知識 — 推論過程の説明への活用

ルールベースの説明生成、証明木の提示、ニューラルモデルからのルール抽出、説明責任と監査可能性

推論・探索・知識表現の基礎 — 退避・古典資料archive

旧版の講義資料、歴代エキスパートシステムの文献、初期AI論文集など、現役を退いた古典・退避資料の保管棚