Synthesizing Customized Planners from Specifications
仕様に基づくカスタマイズされたプランナーの合成
Existing plan synthesis approaches in artificial intelligence fall into two categories — domain independent and domain dependent. The domain independent approaches are applicable across a variety of domains, but may not be very efficient in any one given domain. The domain dependent approaches need to be (re)designed for each domain separately, but can be very efficient in the domain for which they are designed. One enticing alternative to these approaches is to automatically synthesize domain independent planners given the knowledge about the domain and the theory of planning. In this paper, we investigate the feasibility of using existing automated software synthesis tools to support such synthesis. Specifically, we describe an architecture called CLAY in which the Kestrel Interactive Development System (KIDS) is used to derive a domain-customized planner through a semi-automatic combination of a declarative theory of planning, and the declarative control knowledge specific to a given domain, to semi-automatically combine them to derive domain-customized planners. We discuss what it means to write a declarative theory of planning and control knowledge for KIDS, and illustrate our approach by generating a class of domain-specific planners using state space refinements. Our experiments show that the synthesized planners can outperform classical refinement planners (implemented as instantiations of UCP, Kambhampati & Srivastava, 1995), using the same control knowledge. We will contrast the costs and benefits of the synthesis approach with conventional methods for customizing domain independent planners.
人工知能における既存の計画合成アプローチは、ドメイン非依存型とドメイン依存型の2つのカテゴリに分類されます。ドメイン非依存型アプローチは様々なドメインに適用可能ですが、特定のドメインではあまり効率的ではない可能性があります。ドメイン依存型アプローチは、各ドメインごとに（再）設計する必要がありますが、設計されたドメインでは非常に効率的です。これらのアプローチの魅力的な代替案の1つは、ドメインに関する知識と計画理論に基づいて、ドメイン非依存型プランナーを自動的に合成することです。本稿では、既存の自動ソフトウェア合成ツールを使用してこのような合成をサポートする可能性を調査します。具体的には、Kestrel Interactive Development System（KIDS）を使用して、宣言的な計画理論と特定のドメインに固有の宣言的な制御知識を半自動的に組み合わせることで、ドメインカスタマイズされたプランナーを導出するCLAYと呼ばれるアーキテクチャについて説明します。KIDSのための計画と制御知識に関する宣言的理論を記述することの意味を議論し、状態空間の改良を用いてドメイン固有のプランナーのクラスを生成することで、我々のアプローチを示す。実験では、合成されたプランナーは、同じ制御知識を用いて、古典的な改良プランナー（UCPのインスタンスとして実装、Kambhampati & Srivastava, 1995）よりも性能が優れていることが示されました。我々は、合成アプローチのコストと利点を、ドメイン非依存プランナーをカスタマイズするための従来の方法と比較します。
Cached Sufficient Statistics for Efficient Machine Learning with Large Datasets
大規模データセットを用いた効率的な機械学習のためのキャッシュされた十分統計量
This paper introduces new algorithms and data structures for quick counting for machine learning datasets. We focus on the counting task of constructing contingency tables, but our approach is also applicable to counting the number of records in a dataset that match conjunctive queries. Subject to certain assumptions, the costs of these operations can be shown to be independent of the number of records in the dataset and loglinear in the number of non-zero entries in the contingency table. We provide a very sparse data structure, the ADtree, to minimize memory use. We provide analytical worst-case bounds for this structure for several models of data distribution. We empirically demonstrate that tractably-sized data structures can be produced for large real-world datasets by (a) using a sparse tree structure that never allocates memory for counts of zero, (b) never allocating memory for counts that can be deduced from other counts, and (c) not bothering to expand the tree fully near its leaves. We show how the ADtree can be used to accelerate Bayes net structure finding algorithms, rule learning algorithms, and feature selection algorithms, and we provide a number of empirical results comparing ADtree methods against traditional direct counting approaches. We also discuss the possible uses of ADtrees in other machine learning methods, and discuss the merits of ADtrees in comparison with alternative representations such as kd-trees, R-trees and Frequent Sets.
本論文では、機械学習データセットの迅速なカウントのための新しいアルゴリズムとデータ構造を紹介します。分割表を構築するカウントタスクに焦点を当てるが、このアプローチは、データセット内の結合クエリに一致するレコードの数をカウントすることにも適用できます。特定の仮定のもと、これらの操作にかかるコストはデータセット内のレコード数とは独立であり、分割表における非ゼロエントリの数に対数線形に比例することが示せます。メモリ使用量を最小限に抑えるため、非常に疎なデータ構造であるADtreeを提供します。この構造について、いくつかのデータ分布モデルに対する解析的な最悪ケースの境界を示します。(a)ゼロのカウントにメモリを割り当てない疎なツリー構造を使用する、(b)他のカウントから推測できるカウントにメモリを割り当てない、(c)ツリーを葉の近くまで完全に拡張しない、という3つの方法により、大規模な実世界データセットに対して扱いやすいサイズのデータ構造を生成できることを実証的に示します。ADtreeを用いてベイズネット構造発見アルゴリズム、ルール学習アルゴリズム、および特徴選択アルゴリズムを高速化する方法を示し、ADtree法と従来の直接カウント法を比較したいくつかの実験結果を示します。また、他の機械学習手法におけるADtreeの使用法についても説明し、kd-tree、R-tree、Frequent Setsなどの代替表現と比較したADtreeのメリットについても説明します。
Tractability of Theory Patching
理論パッチングの扱いやすさ
In this paper we consider the problem of `theory patching’, in which we are given a domain theory, some of whose components are indicated to be possibly flawed, and a set of labeled training examples for the domain concept. The theory patching problem is to revise only the indicated components of the theory, such that the resulting theory correctly classifies all the training examples. Theory patching is thus a type of theory revision in which revisions are made to individual components of the theory. Our concern in this paper is to determine for which classes of logical domain theories the theory patching problem is tractable. We consider both propositional and first-order domain theories, and show that the theory patching problem is equivalent to that of determining what information contained in a theory is `stable’ regardless of what revisions might be performed to the theory. We show that determining stability is tractable if the input theory satisfies two conditions: that revisions to each theory component have monotonic effects on the classification of examples, and that theory components act independently in the classification of examples in the theory. We also show how the concepts introduced can be used to determine the soundness and completeness of particular theory patching algorithms.
本論文では、「理論パッチング」の問題を検討します。この問題では、一部の構成要素に欠陥がある可能性のあるドメイン理論と、そのドメイン概念のラベル付きトレーニング例の集合が与えられます。理論パッチング問題とは、理論の指摘された構成要素のみを修正し、結果として得られる理論がすべてのトレーニング例を正しく分類できるようにすることです。理論パッチングは、理論の個々の構成要素に修正を加える理論修正の一種です。本論文では、どのクラスの論理領域理論において理論パッチング問題が扱いやすいかを明らかにすることを目的とします。命題論理的領域理論と一階述語論理的領域理論の両方を考慮し、理論パッチング問題は、理論にどのような修正が加えられたとしても、理論に含まれるどの情報が「安定」しているかを判断する問題と等価であることを示す。入力理論が2つの条件を満たす場合、安定性の判断が扱いやすいことを示す。すなわち、各理論構成要素への修正が例の分類に単調な影響を与えること、および各理論構成要素が理論内の例の分類において独立して作用することです。また、導入された概念が、特定の理論パッチングアルゴリズムの健全性と完全性を判断するためにどのように使用できるかを示す。
Incremental Recompilation of Knowledge
知識の増分的再コンパイル
Approximating a general formula from above and below by Horn formulas (its Horn envelope and Horn core, respectively) was proposed by Selman and Kautz (1991, 1996) as a form of “knowledge compilation,” supporting rapid approximate reasoning; on the negative side, this scheme is static in that it supports no updates, and has certain complexity drawbacks pointed out by Kavvadias, Papadimitriou and Sideri (1993). On the other hand, the many frameworks and schemes proposed in the literature for theory update and revision are plagued by serious complexity-theoretic impediments, even in the Horn case, as was pointed out by Eiter and Gottlob (1992), and is further demonstrated in the present paper. More fundamentally, these schemes are not inductive, in that they may lose in a single update any positive properties of the represented sets of formulas (small size, Horn structure, etc.). In this paper we propose a new scheme, incremental recompilation, which combines Horn approximation and model-based updates; this scheme is inductive and very efficient, free of the problems facing its constituents. A set of formulas is represented by an upper and lower Horn approximation. To update, we replace the upper Horn formula by the Horn envelope of its minimum-change update, and similarly the lower one by the Horn core of its update; the key fact which enables this scheme is that Horn envelopes and cores are easy to compute when the underlying formula is the result of a minimum-change update of a Horn formula by a clause. We conjecture that efficient algorithms are possible for more complex updates.
セルマンとカウツ（1991、1996）は、一般公式を上と下からホーン公式（それぞれホーンエンベロープとホーンコア）で近似する手法を「知識コンパイル」の一形態として提案し、迅速な近似推論を支援します。この手法の欠点としては、更新をサポートしないという点で静的であり、カヴヴァディアス、パパディミトリウ、シデリ（1993）が指摘したように、計算量に関する欠点があります。一方、理論の更新と改訂のために文献で提案されている多くの枠組みや手法は、ホーンの場合ですら深刻な計算量理論的障害に悩まされており、これはアイターとゴットロブ（1992）によって指摘され、本論文でもさらに実証されています。より根本的な問題として、これらの手法は帰納的ではなく、表現される公式集合の肯定的な特性（サイズが小さい、ホーン構造など）が一度の更新で失われる可能性があります。本論文では、ホーン近似とモデルベースの更新を組み合わせた新しい手法、増分再コンパイルを提案します。この手法は帰納的かつ非常に効率的であり、構成要素が直面する問題を回避できます。論理式の集合は、上側ホーン近似と下側ホーン近似で表されます。更新を行うには、上側ホーン論理式をその最小変化更新のホーンエンベロープに置き換え、同様に下側ホーン近似を更新のホーンコアに置き換える。この手法を可能にする鍵となる事実は、基礎となる論理式がホーン論理式を節で最小変化更新した結果である場合、ホーンエンベロープとコアの計算が容易であるということにあります。より複雑な更新に対しても効率的なアルゴリズムが実現可能と推測されます。
A Selective Macro-learning Algorithm and its Application to the NxN Sliding-Tile Puzzle
選択的マクロ学習アルゴリズムとそのNxNスライディングタイルパズルへの応用
One of the most common mechanisms used for speeding up problem solvers is macro-learning. Macros are sequences of basic operators acquired during problem solving. Macros are used by the problem solver as if they were basic operators. The major problem that macro-learning presents is the vast number of macros that are available for acquisition. Macros increase the branching factor of the search space and can severely degrade problem-solving efficiency. To make macro learning useful, a program must be selective in acquiring and utilizing macros. This paper describes a general method for selective acquisition of macros. Solvable training problems are generated in increasing order of difficulty. The only macros acquired are those that take the problem solver out of a local minimum to a better state. The utility of the method is demonstrated in several domains, including the domain of NxN sliding-tile puzzles. After learning on small puzzles, the system is able to efficiently solve puzzles of any size.
問題解決者の高速化に用いられる最も一般的なメカニズムの一つは、マクロ学習です。マクロとは、問題解決中に獲得される基本演算子のシーケンスです。問題解決者は、マクロを基本演算子であるかのように使用します。マクロ学習がもたらす主な問題は、獲得可能なマクロの数が膨大になることです。マクロは探索空間の分岐係数を増加させ、問題解決の効率を著しく低下させる可能性があります。マクロ学習を有効活用するには、プログラムはマクロを選択的に獲得し、利用する必要があります。本論文では、マクロを選択的に獲得するための一般的な手法について説明します。解ける訓練問題は、難易度の昇順で生成されます。獲得されるマクロは、問題解決者を局所的最小値からより良い状態へと導くものだけです。この手法の有用性は、NxNスライディングタイルパズルを含むいくつかの領域で実証されています。小さなパズルで学習した後、システムはあらゆるサイズのパズルを効率的に解くことができます。
Model-Based Diagnosis using Structured System Descriptions
構造化システム記述を用いたモデルベース診断
This paper presents a comprehensive approach for model-based diagnosis which includes proposals for characterizing and computing preferred diagnoses, assuming that the system description is augmented with a system structure (a directed graph explicating the interconnections between system components). Specifically, we first introduce the notion of a consequence, which is a syntactically unconstrained propositional sentence that characterizes all consistency-based diagnoses and show that standard characterizations of diagnoses, such as minimal conflicts, correspond to syntactic variations on a consequence. Second, we propose a new syntactic variation on the consequence known as negation normal form (NNF) and discuss its merits compared to standard variations. Third, we introduce a basic algorithm for computing consequences in NNF given a structured system description. We show that if the system structure does not contain cycles, then there is always a linear-size consequence in NNF which can be computed in linear time. For arbitrary system structures, we show a precise connection between the complexity of computing consequences and the topology of the underlying system structure. Finally, we present an algorithm that enumerates the preferred diagnoses characterized by a consequence. The algorithm is shown to take linear time in the size of the consequence if the preference criterion satisfies some general conditions.
本論文では、システム記述がシステム構造（システムコンポーネント間の相互接続性を説明する有向グラフ）によって拡張されていると仮定し、好ましい診断を特徴付け、計算するための提案を含む、モデルベース診断のための包括的なアプローチを提示します。具体的には、まず、すべての一貫性に基づく診断を特徴付ける、統語的に制約のない命題文である結果の概念を導入し、最小衝突などの診断の標準的な特徴付けが、結果の統語的バリエーションに対応することを示します。次に、否定正規形（NNF）として知られる結果の新しい統語的バリエーションを提案し、標準的なバリエーションと比較したその利点について論じます。最後に、構造化されたシステム記述が与えられた場合にNNFで結果を計算する基本アルゴリズムを導入します。システム構造にサイクルが含まれていない場合、NNFには常に線形サイズの結果が存在し、線形時間で計算できることを示します。任意のシステム構造について、結果の計算の複雑さと、基礎となるシステム構造のトポロジとの間に明確な関連性があることを示します。最後に、結果によって特徴付けられる好ましい診断を列挙するアルゴリズムを提示します。選好基準がいくつかの一般条件を満たす場合、このアルゴリズムは結果のサイズに対して線形時間で計算されることを示します。
Integrative Windowing
統合ウィンドウ処理
In this paper we re-investigate windowing for rule learning algorithms. We show that, contrary to previous results for decision tree learning, windowing can in fact achieve significant run-time gains in noise-free domains and explain the different behavior of rule learning algorithms by the fact that they learn each rule independently. The main contribution of this paper is integrative windowing, a new type of algorithm that further exploits this property by integrating good rules into the final theory right after they have been discovered. Thus it avoids re-learning these rules in subsequent iterations of the windowing process. Experimental evidence in a variety of noise-free domains shows that integrative windowing can in fact achieve substantial run-time gains. Furthermore, we discuss the problem of noise in windowing and present an algorithm that is able to achieve run-time gains in a set of experiments in a simple domain with artificial noise.
本稿では、ルール学習アルゴリズムのためのウィンドウイングを再調査します。決定木学習におけるこれまでの結果とは対照的に、ウィンドウ処理はノイズのない領域において実際に大幅な実行時間短縮を達成できることを示し、ルール学習アルゴリズムが各ルールを独立に学習するという事実によって異なる動作を説明します。本論文の主な貢献は、統合ウィンドウ処理です。これは、優れたルールが発見された直後に最終理論に統合することでこの特性をさらに活用する新しいタイプのアルゴリズムです。これにより、ウィンドウ処理プロセスの後続の反復においてこれらのルールを再学習する必要がなくなります。様々なノイズのない領域における実験的証拠は、統合ウィンドウ処理が実際に大幅な実行時間短縮を達成できることを示す。さらに、ウィンドウ処理におけるノイズの問題について議論し、人工ノイズを含む単純な領域における一連の実験において実行時間短縮を達成できるアルゴリズムを提示します。
Monotonicity and Persistence in Preferential Logics
選好論理における単調性と持続性
An important characteristic of many logics for Artificial Intelligence is their nonmonotonicity. This means that adding a formula to the premises can invalidate some of the consequences. There may, however, exist formulae that can always be safely added to the premises without destroying any of the consequences: we say they respect monotonicity. Also, there may be formulae that, when they are a consequence, can not be invalidated when adding any formula to the premises: we call them conservative. We study these two classes of formulae for preferential logics, and show that they are closely linked to the formulae whose truth-value is preserved along the (preferential) ordering. We will consider some preferential logics for illustration, and prove syntactic characterization results for them. The results in this paper may improve the efficiency of theorem provers for preferential logics.
人工知能のための多くの論理の重要な特徴は、その非単調性です。これは、前提に式を追加すると、いくつかの帰結が無効になる可能性があることを意味します。しかし、いかなる帰結も損なうことなく前提に安全に追加できる式も存在する可能性があります。これらは単調性を尊重する式であると言う。また、帰結である場合、前提に式を追加しても無効にならない式も存在する可能性があります。これらは保守的であると言う。本稿では、優先論理のこれらの2つのクラスの式を研究し、それらが（優先）順序に沿って真理値が保存される式と密接に関連していることを示す。例としていくつかの優先論理を考察し、それらの統語的特徴付けの結果を証明します。本稿の結果は、優先論理の定理証明器の効率を向上させる可能性があります。