Accelerating Partial-Order Planners: Some Techniques for Effective Search Control and Pruning
半順序プランナーの高速化：効果的な探索制御と枝刈りのためのいくつかの手法
We propose some domain-independent techniques for bringing well-founded partial-order planners closer to practicality. The first two techniques are aimed at improving search control while keeping overhead costs low. One is based on a simple adjustment to the default A* heuristic used by UCPOP to select plans for refinement. The other is based on preferring “zero commitment” (forced) plan refinements whenever possible, and using LIFO prioritization otherwise. A more radical technique is the use of operator parameter domains to prune search. These domains are initially computed from the definitions of the operators and the initial and goal conditions, using a polynomial-time algorithm that propagates sets of constants through the operator graph, starting in the initial conditions. During planning, parameter domains can be used to prune nonviable operator instances and to remove spurious clobbering threats. In experiments based on modifications of UCPOP, our improved plan and goal selection strategies gave speedups by factors ranging from 5 to more than 1000 for a variety of problems that are nontrivial for the unmodified version. Crucially, the hardest problems gave the greatest improvements. The pruning technique based on parameter domains often gave speedups by an order of magnitude or more for difficult problems, both with the default UCPOP search strategy and with our improved strategy. The Lisp code for our techniques and for the test problems is provided in on-line appendices.
本稿では、well-founded半順序プランナーを実用化に近づけるための、ドメイン非依存の手法をいくつか提案します。最初の2つの手法は、オーバーヘッドコストを低く抑えながら探索制御を改善することを目的としています。1つは、UCPOPが改良計画を選択する際に使用するデフォルトのA*ヒューリスティックを単純に調整したものです。もう1つは、可能な限り「ゼロコミットメント」（強制）プラン改良を優先し、そうでない場合はLIFO優先順位付けを使用します。より根本的な手法は、演算子パラメータドメインを用いて探索を枝刈りすることです。これらのドメインは、演算子の定義と初期条件および目標条件から、初期条件から開始して演算子グラフ全体に定数セットを伝播させる多項式時間アルゴリズムを用いて最初に計算されます。計画段階では、パラメータドメインを用いて、実行不可能な演算子インスタンスを枝刈りし、不要なクローバリングの脅威を取り除くことができます。UCPOPの修正に基づく実験では、改良された計画および目標選択戦略により、修正されていないバージョンでは容易ではないさまざまな問題に対して、5倍から1000倍以上の高速化が実現しました。重要なのは、最も難しい問題で最も大きな改善が得られたことです。パラメータ領域に基づく枝刈り手法は、デフォルトのUCPOP検索戦略と改良された戦略の両方で、難しい問題に対して1桁以上の高速化を実現することがよくあります。私たちの手法とテスト問題のLispコードは、オンラインの付録で提供されています。
Cue Phrase Classification Using Machine Learning
機械学習を用いたキューフレーズ分類
Cue phrases may be used in a discourse sense to explicitly signal discourse structure, but also in a sentential sense to convey semantic rather than structural information. Correctly classifying cue phrases as discourse or sentential is critical in natural language processing systems that exploit discourse structure, e.g., for performing tasks such as anaphora resolution and plan recognition. This paper explores the use of machine learning for classifying cue phrases as discourse or sentential. Two machine learning programs (Cgrendel and C4.5) are used to induce classification models from sets of pre-classified cue phrases and their features in text and speech. Machine learning is shown to be an effective technique for not only automating the generation of classification models, but also for improving upon previous results. When compared to manually derived classification models already in the literature, the learned models often perform with higher accuracy and contain new linguistic insights into the data. In addition, the ability to automatically construct classification models makes it easier to comparatively analyze the utility of alternative feature representations of the data. Finally, the ease of retraining makes the learning approach more scalable and flexible than manual methods.
キューフレーズは、談話構造を明示的に示す談話的な意味で用いられる場合もあれば、構造情報ではなく意味情報を伝達する文的な意味で用いられる場合もあります。談話構造を利用する自然言語処理システム（例えば、照応解決やプラン認識などのタスクを実行する場合）においては、キューフレーズを談話的または文的に正しく分類することが非常に重要です。本論文では、機械学習を用いてキューフレーズを談話的または文的に分類する方法について考察します。2つの機械学習プログラム（CgrendelとC4.5）を用いて、テキストと音声における事前分類済みのキューフレーズとその特徴のセットから分類モデルを導出します。機械学習は、分類モデルの生成を自動化するだけでなく、過去の結果を改善する効果的な手法であることが示されています。文献に既に存在する手動で導出された分類モデルと比較すると、学習されたモデルは多くの場合、より高い精度で動作し、データに関する新たな言語的知見を含んでいます。さらに、分類モデルを自動的に構築できるため、データの代替的な特徴表現の有用性を比較分析することが容易になります。最後に、再学習の容易さにより、この学習アプローチは手動による方法よりもスケーラブルで柔軟性に優れています。
Quantitative Results Comparing Three Intelligent Interfaces forInformation Capture: A Case Study Adding Name Information into an Electronic Personal Organizer
情報収集のための3つのインテリジェントインターフェースの比較による定量的結果：電子パーソナルオーガナイザーへの名前情報の追加に関するケーススタディ
Efficiently entering information into a computer is key to enjoying the benefits of computing. This paper describes three intelligent user interfaces: handwriting recognition, adaptive menus, and predictive fillin. In the context of adding a personUs name and address to an electronic organizer, tests show handwriting recognition is slower than typing on an on-screen, soft keyboard, while adaptive menus and predictive fillin can be twice as fast. This paper also presents strategies for applying these three interfaces to other information collection domains.
コンピュータに情報を効率的に入力することは、コンピューティングのメリットを享受するための鍵です。この論文では、手書き認識、適応型メニュー、予測入力という3つのインテリジェントなユーザーインターフェースについて説明します。電子手帳に氏名と住所を追加するという状況において、手書き認識は画面上のソフトキーボードでの入力よりも遅いことがテストで示されています。一方、アダプティブメニューと予測入力は2倍の速さで入力できます。本稿では、これら3つのインターフェースを他の情報収集分野に適用するための戦略も示します。
Exploiting Causal Independence in Bayesian Network Inference
ベイジアンネットワーク推論における因果独立性の活用
A new method is proposed for exploiting causal independencies in exact Bayesian network inference. A Bayesian network can be viewed as representing a factorization of a joint probability into the multiplication of a set of conditional probabilities. We present a notion of causal independence that enables one to further factorize the conditional probabilities into a combination of even smaller factors and consequently obtain a finer-grain factorization of the joint probability. The new formulation of causal independence lets us specify the conditional probability of a variable given its parents in terms of an associative and commutative operator, such as “or”, “sum” or “max”, on the contribution of each parent. We start with a simple algorithm VE for Bayesian network inference that, given evidence and a query variable, uses the factorization to find the posterior distribution of the query. We show how this algorithm can be extended to exploit causal independence. Empirical studies, based on the CPCS networks for medical diagnosis, show that this method is more efficient than previous methods and allows for inference in larger networks than previous algorithms.
正確なベイジアンネットワーク推論において因果的独立性を利用するための新しい手法を提案します。ベイジアンネットワークは、結合確率を条件付き確率の集合の乗算に因数分解したものと見なすことができます。本稿では、条件付き確率をさらに小さな因子の組み合わせに因数分解し、結果として結合確率のより細粒度の因数分解を得ることを可能にする因果的独立性の概念を提示します。因果独立性の新たな定式化により、各親の寄与に対する「または」、「合計」、「最大」などの結合的かつ可換的な演算子を用いて、親を与えられた変数の条件付き確率を指定できるようになりました。ベイジアンネットワーク推論のためのシンプルなアルゴリズムVEから始めます。このアルゴリズムは、証拠とクエリ変数が与えられた場合に、因数分解を使用してクエリの事後分布を見つけます。このアルゴリズムを拡張して因果独立性を活用する方法を示します。医療診断用のCPCSネットワークに基づく実証的研究は、この方法が従来の方法よりも効率的であり、従来のアルゴリズムよりも大規模なネットワークでの推論を可能にすることを示しています。
Characterizations of Decomposable Dependency Models
分解可能な依存モデルの特性評価
Decomposable dependency models possess a number of interesting and useful properties. This paper presents new characterizations of decomposable models in terms of independence relationships, which are obtained by adding a single axiom to the well-known set characterizing dependency models that are isomorphic to undirected graphs. We also briefly discuss a potential application of our results to the problem of learning graphical models from data.
分解可能な依存モデルは、興味深く有用な特性を数多く備えています。本稿では、独立関係の観点から分解可能モデルを新たに特徴づけます。独立関係は、無向グラフと同型な依存モデルを特徴づける既知の集合に、単一の公理を追加することで得られます。また、データからグラフィカルモデルを学習する問題への本研究結果の潜在的な応用についても簡単に説明します。
A Hierarchy of Tractable Subsets for Computing Stable Models
安定モデルを計算するための扱いやすいサブセットの階層構造
Finding the stable models of a knowledge base is a significant computational problem in artificial intelligence. This task is at the computational heart of truth maintenance systems, autoepistemic logic, and default logic. Unfortunately, it is NP-hard. In this paper we present a hierarchy of classes of knowledge bases, Omega_1,Omega_2,…, with the following properties: first, Omega_1 is the class of all stratified knowledge bases; second, if a knowledge base Pi is in Omega_k, then Pi has at most k stable models, and all of them may be found in time O(lnk), where l is the length of the knowledge base and n the number of atoms in Pi; third, for an arbitrary knowledge base Pi, we can find the minimum k such that Pi belongs to Omega_k in time polynomial in the size of Pi; and, last, where K is the class of all knowledge bases, it is the case that union{i=1 to infty} Omega_i = K, that is, every knowledge base belongs to some class in the hierarchy.
知識ベースの安定したモデルを見つけることは、人工知能における重要な計算問題です。このタスクは、真理維持システム、自己認識論理、およびデフォルト論理の計算の中核を成すものです。残念ながら、これはNP困難です。この論文では、知識ベースのクラスの階層Omega_1、Omega_2、…を提示し、次の特性を示します。第1に、Omega_1はすべての階層化知識ベースのクラスです。第2に、知識ベースPiがOmega_kに属する場合、Piには最大でk個の安定モデルがあり、それらすべてをO(lnk)の時間で見つけることができます(lは知識ベースの長さ、nはPi内の原子の数)。第3に、任意の知識ベースPiについて、PiがOmega_kに属する最小のkを、Piのサイズの多項式時間で見つけることができます。最後に、Kをすべての知識ベースのクラスとすると、union{i=1 to infty} Omega_i = Kとなります。つまり、すべての知識ベースが階層内のいずれかのクラスに属します。
MUSE CSP: An Extension to the Constraint Satisfaction Problem
MUSE CSP：制約充足問題への拡張
This paper describes an extension to the constraint satisfaction problem (CSP) called MUSE CSP (MUltiply SEgmented Constraint Satisfaction Problem). This extension is especially useful for those problems which segment into multiple sets of partially shared variables. Such problems arise naturally in signal processing applications including computer vision, speech processing, and handwriting recognition. For these applications, it is often difficult to segment the data in only one way given the low-level information utilized by the segmentation algorithms. MUSE CSP can be used to compactly represent several similar instances of the constraint satisfaction problem. If multiple instances of a CSP have some common variables which have the same domains and constraints, then they can be combined into a single instance of a MUSE CSP, reducing the work required to apply the constraints. We introduce the concepts of MUSE node consistency, MUSE arc consistency, and MUSE path consistency. We then demonstrate how MUSE CSP can be used to compactly represent lexically ambiguous sentences and the multiple sentence hypotheses that are often generated by speech recognition algorithms so that grammar constraints can be used to provide parses for all syntactically correct sentences. Algorithms for MUSE arc and path consistency are provided. Finally, we discuss how to create a MUSE CSP from a set of CSPs which are labeled to indicate when the same variable is shared by more than a single CSP.
本論文では、制約充足問題（CSP）の拡張であるMUSE CSP（MUltiply SEgmented Constraint Satisfaction Problem）について説明します。この拡張は、部分的に共有される変数の複数の集合に分割する問題に特に有用です。このような問題は、コンピュータビジョン、音声処理、手書き認識などの信号処理アプリケーションにおいて自然に発生します。これらのアプリケーションでは、セグメンテーションアルゴリズムで利用される低レベルの情報を考慮すると、データを一方向にのみ分割することが困難な場合が多い。MUSE CSPは、制約充足問題の類似したインスタンスを複数コンパクトに表現するために使用できます。CSPの複数のインスタンスに、同じドメインと制約を持つ共通の変数がいくつかある場合、それらを1つのMUSE CSPインスタンスに結合して、制約を適用するために必要な作業を削減できます。ここでは、MUSEノード一貫性、MUSEアーク一貫性、およびMUSEパス一貫性の概念を紹介します。次に、MUSE CSPを使用して、語彙的に曖昧な文や、音声認識アルゴリズムによって生成されることが多い複数の文仮説をコンパクトに表現し、文法制約を使用してすべての構文的に正しい文の解析を提供する方法を示します。MUSEアーク一貫性とパス一貫性のアルゴリズムが提供されます。最後に、同じ変数が複数のCSPで共有されているかどうかを示すラベルが付けられたCSPの集合から、MUSE CSPを作成する方法について説明します。
Mechanisms for Automated Negotiation in State Oriented Domains
状態指向領域における自動交渉のメカニズム
This paper lays part of the groundwork for a domain theory of negotiation, that is, a way of classifying interactions so that it is clear, given a domain, which negotiation mechanisms and strategies are appropriate. We define State Oriented Domains, a general category of interaction. Necessary and sufficient conditions for cooperation are outlined. We use the notion of worth in an altered definition of utility, thus enabling agreements in a wider class of joint-goal reachable situations. An approach is offered for conflict resolution, and it is shown that even in a conflict situation, partial cooperative steps can be taken by interacting agents (that is, agents in fundamental conflict might still agree to cooperate up to a certain point). A Unified Negotiation Protocol (UNP) is developed that can be used in all types of encounters. It is shown that in certain borderline cooperative situations, a partial cooperative agreement (i.e., one that does not achieve all agents’ goals) might be preferred by all agents, even though there exists a rational agreement that would achieve all their goals. Finally, we analyze cases where agents have incomplete information on the goals and worth of other agents. First we consider the case where agents’ goals are private information, and we analyze what goal declaration strategies the agents might adopt to increase their utility. Then, we consider the situation where the agents’ goals (and therefore stand-alone costs) are common knowledge, but the worth they attach to their goals is private information. We introduce two mechanisms, one ‘strict’, the other ‘tolerant’, and analyze their affects on the stability and efficiency of negotiation outcomes.
本論文は、交渉のドメイン理論、すなわち、与えられたドメインにおいて、どの交渉メカニズムと戦略が適切であるかを明確にするための相互作用の分類法の基礎を築くものです。相互作用の一般的なカテゴリーとして、状態指向ドメインを定義します。協力の必要十分条件を概説します。価値の概念を効用の定義に用いることで、より広範な共同目標到達可能な状況における合意を可能にします。紛争解決のためのアプローチを提示し、紛争状況下であっても、相互作用するエージェントが部分的な協力措置を講じることができることを示す（つまり、根本的に対立するエージェントであっても、ある程度までは協力することに合意する可能性がある）。あらゆる種類の遭遇において使用可能な統一交渉プロトコル（UNP）が開発されます。特定の協力の境界線上にある状況においては、すべてのエージェントの目標を達成できる合理的な合意が存在するにもかかわらず、すべてのエージェントが部分的な協力合意（すなわち、すべてのエージェントの目標を達成しない合意）を好む可能性があることを示す。最後に、エージェントが他のエージェントの目標と価値について不完全な情報しか持たないケースを分析します。まず、エージェントの目標が私的情報である場合を考察し、エージェントが効用を高めるためにどのような目標宣言戦略を採用するかを分析します。次に、エージェントの目標（およびそれに伴う独立コスト）は共通知識であるものの、目標に付与する価値は私的情報である状況を考察します。「厳密な」メカニズムと「寛容な」メカニズムの2つのメカニズムを導入し、それらが交渉結果の安定性と効率性に与える影響を分析します。
Learning First-Order Definitions of Functions
関数の一次定義の学習
First-order learning involves finding a clause-form definition of a relation from examples of the relation and relevant background information. In this paper, a particular first-order learning system is modified to customize it for finding definitions of functional relations. This restriction leads to faster learning times and, in some cases, to definitions that have higher predictive accuracy. Other first-order learning systems might benefit from similar specialization.
一次学習とは、関係の例と関連する背景情報から、関係の節形式の定義を見つけることです。本稿では、特定の一次学習システムを修正し、関数関係の定義を見つけるようにカスタマイズします。この制約により、学習時間が短縮され、場合によっては予測精度の高い定義が得られます。他の一次学習システムも同様の特化から恩恵を受ける可能性があります。
Spatial Aggregation: Theory and Applications
空間集約：理論と応用
Visual thinking plays an important role in scientific reasoning. Based on the research in automating diverse reasoning tasks about dynamical systems, nonlinear controllers, kinematic mechanisms, and fluid motion, we have identified a style of visual thinking, imagistic reasoning. Imagistic reasoning organizes computations around image-like, analogue representations so that perceptual and symbolic operations can be brought to bear to infer structure and behavior. Programs incorporating imagistic reasoning have been shown to perform at an expert level in domains that defy current analytic or numerical methods. We have developed a computational paradigm, spatial aggregation, to unify the description of a class of imagistic problem solvers. A program written in this paradigm has the following properties. It takes a continuous field and optional objective functions as input, and produces high-level descriptions of structure, behavior, or control actions. It computes a multi-layer of intermediate representations, called spatial aggregates, by forming equivalence classes and adjacency relations. It employs a small set of generic operators such as aggregation, classification, and localization to perform bidirectional mapping between the information-rich field and successively more abstract spatial aggregates. It uses a data structure, the neighborhood graph, as a common interface to modularize computations. To illustrate our theory, we describe the computational structure of three implemented problem solvers — KAM, MAPS, and HIPAIR — in terms of the spatial aggregation generic operators by mixing and matching a library of commonly used routines.
視覚的思考は科学的推論において重要な役割を果たしています。力学系、非線形制御器、運動機構、流体運動に関する多様な推論タスクの自動化に関する研究に基づき、我々は視覚的思考の一形態であるイメージ的推論を特定した。イメージ的推論は、画像のようなアナログ表現を中心に計算を体系化し、知覚的および記号的な操作を用いて構造と動作を推論できるようにします。イメージ的推論を組み込んだプログラムは、現在の解析手法や数値手法では対応できない領域において、専門家レベルのパフォーマンスを発揮することが示されています。私たちは、イメージ的問題解決プログラムのクラスの記述を統一するために、空間集約という計算パラダイムを開発しました。このパラダイムで書かれたプログラムには、次の特性があります。連続フィールドとオプションの目的関数を入力として受け取り、構造、動作、または制御アクションの高レベルの記述を生成します。同値類と隣接関係を形成することで、空間集約と呼ばれる多層の中間表現を計算します。集約、分類、局所化などの一般的な演算子の小さなセットを使用して、情報豊富なフィールドと、より抽象的な空間集約との間で双方向のマッピングを実行します。計算をモジュール化するための共通インターフェースとして、データ構造である近傍グラフを使用します。本理論を説明するために、実装された3つの問題解決ツール（KAM、MAPS、HIPAIR）の計算構造を、空間集約汎用演算子の観点から、一般的に使用されるルーチンのライブラリを組み合わせて説明します。