知識コンパイルは、人工知能におけるアプローチの一群であり、命題モデルを用いた推論の計算上の難解さに対処するものである。複雑なモデルに対して直接クエリに答える代わりに、モデルはオフライン段階で、特定のクエリを多項式時間でサポートするコンパイル済み表現に変換される。この2段階プロセス（コンパイル、その後のクエリ応答）は、初期の計算労力を、実行時におけるより高速で予測可能な推論と引き換えにする。
中心的な課題は、適切なコンパイル済み表現を選択することにある。なぜなら、異なる表現は異なるトレードオフを提供するからである。コンパイル済み表現を特徴づける3つの主要な特性は、そのコンパクト性（元のモデルをどれだけ簡潔に表現するか）、多項式時間でサポートするクエリの集合、そして多項式時間で実行できる変換である。単一の表現がこれら3つすべてに優れることはないため、実践者は回答する必要のあるクエリとアプリケーションのサイズ制約に基づいて表現を選択する。
表現のクラス
コンパイル済み表現は、いくつかの広いカテゴリに分類される。図式クラスには、決定木、順序付き二分決定図（OBDD）、自由二分決定図（FBDD）、非決定的OBDD、多値決定図（MDD）が含まれる。これらのグラフ構造は、ブール関数を有向非巡回グラフとして表現し、各経路は変数の割り当てに対応する。
式クラスには、選言標準形（DNF）と連言標準形（CNF）が含まれる。CNFは多くの推論タスクの一般的な入力形式であるが、すべてのクエリを効率的にサポートするわけではなく、他の形式へのコンパイルが動機となる。回路クラスには、否定標準形（NNF）、分解可能NNF（DNNF）、決定的DNNF（d-DNNF）、文型決定図（SDD）が含まれる。これらの回路は、整合性チェックやモデル計数などの特定のクエリに対する多項式時間操作を可能にする構造的制約を課す。
知識コンパイラ
知識コンパイルを自動的に実行するためのソフトウェアツールがいくつか開発されている。c2dコンパイラはd-DNNFへのコンパイルをサポートし、これは多項式時間でのモデル計数と整合性チェックを可能にする表現である。d4コンパイラもd-DNNFを対象としており、大規模なインスタンスでの効率性で知られている。miniC2DはSDDにコンパイルし、これはより広範なクエリと変換をサポートする比較的新しい表現である。KCBoxはOBDD、OBDD[AND]、CCDDへのコンパイルをサポートし、異なる図式クラス間での柔軟性を提供する。
これらのコンパイラは、確率的推論、計画、構成管理などのアプリケーションで使用され、繰り返しのクエリ応答が必要とされる。モデルを一度コンパイルすることで、システムは多くのクエリに迅速に答えることができ、これはリアルタイムまたは対話型の設定で重要である。
トレードオフと選択基準
コンパイル済み表現の選択は、アプリケーションの特定の要件に依存する。例えば、OBDDは多くの実用的な関数に対してコンパクトであり、多項式時間での等価性テストをサポートするが、一部の関数では指数関数的に爆発する可能性がある。DNNFとd-DNNFは一般により簡潔であるが、サポートするクエリが少ない。SDDは中間的な立場を提供し、モデル計数と条件付けの両方を多項式時間でサポートしながら、コンパイルを容易にする構造的特性を維持する。
変換も重要である。一部のアプリケーションでは、証拠への条件付けや追加制約との結合など、コンパイル済み表現の修正が必要となる。これらの変換を多項式時間でサポートする表現は、代替表現よりもコンパクトでない場合でも、動的な設定で好まれる。
機械学習との関係
知識コンパイルは、データからパターンを学習することに焦点を当てた機械学習や深層学習とは概念的に異なる。しかし、コンパイル済み表現は、学習済みモデルをより解釈可能にしたり、記号的推論とニューラルアプローチを統合したりする方法として探求されてきた。例えば、決定図は、訓練されたニューラルネットワークの決定境界を、形式的検証をサポートする形式で表現するために使用できる。
最近の研究では、大規模言語モデルの推論との関連も検討されており、コンパイル済み知識ベースが生成モデルを強化するための構造化された背景知識を提供できる可能性がある。これらの取り組みはまだ初期段階であるが、記号的AIと下位記号的AIを橋渡しするツールとしての知識コンパイルの継続的な関連性を強調している。
現在の方向性
知識コンパイルの研究は、より良いトレードオフを持つ新しい表現クラスの開発、コンパイラのスケーラビリティの向上、命題論理を超えたより豊かな論理言語へのコンパイルの拡張に焦点を当て続けている。また、データから直接コンパイル済み表現を学習することへの関心もあり、これはコンパイルと機械学習の間の境界を曖昧にするだろう。AIシステムがより複雑になるにつれて、構造化された知識に対する効率的な推論能力は依然として重要な課題であり、知識コンパイルはそれに対処するための原理的な枠組みを提供する。
参考文献
- Darwiche, A., & Marquis, P. (2002). A knowledge compilation map. Journal of Artificial Intelligence Research, 17, 229-264.
- Huang, J., & Darwiche, A. (2007). On compiling system models to faster SAT solvers. In Proceedings of the National Conference on Artificial Intelligence.
- Muise, C., McIlraith, S., Beck, J. C., & Hsu, E. (2012). Dsharp: Fast d-DNNF compilation with sharpSAT. In Canadian Conference on Artificial Intelligence.