A Uniform Framework for Concept Definitions in Description Logics
記述論理における概念定義のための統一的枠組み
Most modern formalisms used in Databases and Artificial Intelligence for describing an application domain are based on the notions of class (or concept) and relationship among classes. One interesting feature of such formalisms is the possibility of defining a class, i.e., providing a set of properties that precisely characterize the instances of the class. Many recent articles point out that there are several ways of assigning a meaning to a class definition containing some sort of recursion. In this paper, we argue that, instead of choosing a single style of semantics, we achieve better results by adopting a formalism that allows for different semantics to coexist. We demonstrate the feasibility of our argument, by presenting a knowledge representation formalism, the description logic muALCQ, with the above characteristics. In addition to the constructs for conjunction, disjunction, negation, quantifiers, and qualified number restrictions, muALCQ includes special fixpoint constructs to express (suitably interpreted) recursive definitions. These constructs enable the usual frame-based descriptions to be combined with definitions of recursive data structures such as directed acyclic graphs, lists, streams, etc. We establish several properties of muALCQ, including the decidability and the computational complexity of reasoning, by formulating a correspondence with a particular modal logic of programs called the modal mu-calculus.
データベースと人工知能においてアプリケーションドメインを記述するために使用される現代の形式主義のほとんどは、クラス（または概念）とクラス間の関係という概念に基づいています。このような形式主義の興味深い特徴の一つは、クラスを定義できること、つまり、クラスのインスタンスを正確に特徴付ける一連のプロパティを提供できることです。最近の多くの論文では、何らかの再帰を含むクラス定義に意味を割り当てる方法が複数あることが指摘されています。本稿では、単一の意味論スタイルを選択するのではなく、異なる意味論の共存を可能にする形式主義を採用することで、より良い結果が得られると主張します。この主張の実現可能性を示すために、上記の特徴を持つ知識表現形式主義、記述論理muALCQを提示します。muALCQは、連言、選言、否定、量指定子、限定数制約といった構成要素に加えて、（適切に解釈された）再帰定義を表現するための特別な不動点構成要素も備えています。これらの構成により、通常のフレームベースの記述を、有向非巡回グラフ、リスト、ストリームなどの再帰データ構造の定義と組み合わせることができます。我々は、様相μ計算と呼ばれるプログラムの特定の様相論理との対応を定式化することにより、muALCQのいくつかの特性、例えば決定可能性や推論の計算量などを確立します。
SCREEN: Learning a Flat Syntactic and Semantic Spoken Language Analysis Using Artificial Neural Networks
SCREEN: 人工ニューラルネットワークを用いた平坦な統語的・意味的音声言語分析の学習
Previous approaches of analyzing spontaneously spoken language often have been based on encoding syntactic and semantic knowledge manually and symbolically. While there has been some progress using statistical or connectionist language models, many current spoken- language systems still use a relatively brittle, hand-coded symbolic grammar or symbolic semantic component. In contrast, we describe a so-called screening approach for learning robust processing of spontaneously spoken language. A screening approach is a flat analysis which uses shallow sequences of category representations for analyzing an utterance at various syntactic, semantic and dialog levels. Rather than using a deeply structured symbolic analysis, we use a flat connectionist analysis. This screening approach aims at supporting speech and language processing by using (1) data-driven learning and (2) robustness of connectionist networks. In order to test this approach, we have developed the SCREEN system which is based on this new robust, learned and flat analysis. In this paper, we focus on a detailed description of SCREEN’s architecture, the flat syntactic and semantic analysis, the interaction with a speech recognizer, and a detailed evaluation analysis of the robustness under the influence of noisy or incomplete input. The main result of this paper is that flat representations allow more robust processing of spontaneous spoken language than deeply structured representations. In particular, we show how the fault-tolerance and learning capability of connectionist networks can support a flat analysis for providing more robust spoken-language processing within an overall hybrid symbolic/connectionist framework.
これまで、自発的に話された言語を分析するアプローチは、統語的および意味的知識を手動で記号的に符号化することに基づいていることが多かった。統計的言語モデルやコネクショニスト言語モデルを用いることである程度は進歩があったものの、現在の多くの音声言語システムは、依然として比較的脆弱な、手動でコーディングされた記号文法または記号的意味コンポーネントを使用しています。これに対し、我々は、自発的な話し言葉の堅牢な処理を学習するための、いわゆるスクリーニング手法について述べる。スクリーニング手法とは、浅いカテゴリ表現のシーケンスを用いて発話を様々な統語的、意味的、対話レベルで分析するフラットな分析です。深く構造化された記号分析ではなく、フラットなコネクショニスト分析を用います。このスクリーニング手法は、(1)データ駆動型学習と(2)コネクショニストネットワークの堅牢性を用いて音声言語処理を支援することを目的としています。この手法をテストするために、我々はこの新しく堅牢で学習済みのフラットな分析に基づくSCREENシステムを開発した。本稿では、SCREENのアーキテクチャ、フラットな統語的・意味的分析、音声認識装置とのインタラクション、そしてノイズや不完全な入力の影響下における堅牢性の詳細な評価分析について詳細に記述します。本稿の主な結論は、フラットな表現を用いることで、深く構造化された表現よりも自発的な話し言葉をより堅牢に処理できるということです。特に、コネクショニスト ネットワークのフォールト トレランスと学習能力が、全体的なハイブリッド シンボリック/コネクショニスト フレームワーク内でより堅牢な音声言語処理を提供するためのフラット分析をどのようにサポートできるかを示します。
Flaw Selection Strategies for Partial-Order Planning
半順序プランニングにおける欠陥選択戦略
Several recent studies have compared the relative efficiency of alternative flaw selection strategies for partial-order causal link (POCL) planning. We review this literature, and present new experimental results that generalize the earlier work and explain some of the discrepancies in it. In particular, we describe the Least-Cost Flaw Repair (LCFR) strategy developed and analyzed by Joslin and Pollack (1994), and compare it with other strategies, including Gerevini and Schubert’s (1996) ZLIFO strategy. LCFR and ZLIFO make very different, and apparently conflicting claims about the most effective way to reduce search-space size in POCL planning. We resolve this conflict, arguing that much of the benefit that Gerevini and Schubert ascribe to the LIFO component of their ZLIFO strategy is better attributed to other causes. We show that for many problems, a strategy that combines least-cost flaw selection with the delay of separable threats will be effective in reducing search-space size, and will do so without excessive computational overhead. Although such a strategy thus provides a good default, we also show that certain domain characteristics may reduce its effectiveness.
最近のいくつかの研究では、半順序因果リンク（POCL）プランニングにおける代替欠陥選択戦略の相対的な効率を比較しています。我々はこれらの文献をレビューし、以前の研究を一般化し、その矛盾の一部を説明する新しい実験結果を示す。特に、JoslinとPollack（1994）によって開発および分析された最小コスト欠陥修復（LCFR）戦略について説明し、GereviniとSchubert（1996）のZLIFO戦略を含む他の戦略と比較します。LCFRとZLIFOは、POCL計画における探索空間サイズを削減する最も効果的な方法について、非常に異なった、そして一見矛盾する主張をしています。我々はこの矛盾を解決し、GereviniとSchubertがZLIFO戦略のLIFOコンポーネントに帰する利点の多くは、他の原因による方がよいと主張します。我々は、多くの問題において、最小コストの欠陥選択と分離可能な脅威の遅延を組み合わせた戦略が、探索空間サイズを削減するのに効果的であり、過度の計算オーバーヘッドなしにそれを実現することを示す。このように、このような戦略は良いデフォルトを提供するが、特定のドメイン特性がその有効性を低下させる可能性があることも示す。
A Complete Classification of Tractability in RCC-5
RCC-5における扱いやすさの完全分類
We investigate the computational properties of the spatial algebra RCC-5 which is a restricted version of the RCC framework for spatial reasoning. The satisfiability problem for RCC-5 is known to be NP-complete but not much is known about its approximately four billion subclasses. We provide a complete classification of satisfiability for all these subclasses into polynomial and NP-complete respectively. In the process, we identify all maximal tractable subalgebras which are four in total.
我々は、空間推論のためのRCCフレームワークの制限版である空間代数RCC-5の計算特性を調査します。RCC-5の充足可能性問題はNP完全であることが知られているが、その約40億のサブクラスについてはあまり知られていない。我々は、これらすべてのサブクラスの充足可能性を、それぞれ多項式とNP完全へと完全に分類します。その過程で、我々は合計4つあるすべての最大扱い可能なサブ代数を特定します。
Connectionist Theory Refinement: Genetically Searching the Space of Network Topologies
コネクショニスト理論の洗練：ネットワークトポロジー空間の遺伝的探索
An algorithm that learns from a set of examples should ideally be able to exploit the available resources of (a) abundant computing power and (b) domain-specific knowledge to improve its ability to generalize. Connectionist theory-refinement systems, which use background knowledge to select a neural network’s topology and initial weights, have proven to be effective at exploiting domain-specific knowledge; however, most do not exploit available computing power. This weakness occurs because they lack the ability to refine the topology of the neural networks they produce, thereby limiting generalization, especially when given impoverished domain theories. We present the REGENT algorithm which uses (a) domain-specific knowledge to help create an initial population of knowledge-based neural networks and (b) genetic operators of crossover and mutation (specifically designed for knowledge-based networks) to continually search for better network topologies. Experiments on three real-world domains indicate that our new algorithm is able to significantly increase generalization compared to a standard connectionist theory-refinement system, as well as our previous algorithm for growing knowledge-based networks.
一連の例から学習するアルゴリズムは、理想的には、(a)豊富な計算能力と(b)ドメイン固有の知識という利用可能なリソースを活用して、一般化能力を向上させることができるはずです。背景知識を用いてニューラルネットワークのトポロジーと初期重みを選択するコネクショニスト理論改良システムは、ドメイン固有の知識を活用するのに効果的であることが証明されていますが、そのほとんどは利用可能な計算能力を活用していません。この弱点は、生成するニューラルネットワークのトポロジーを改良する能力が欠如しているために発生し、特にドメイン理論が貧弱な場合、一般化が制限されます。本稿では、REGENTアルゴリズムを紹介します。このアルゴリズムは、(a)ドメイン固有の知識を用いて知識ベースニューラルネットワークの初期集団を作成し、(b)知識ベースネットワーク向けに特別に設計された交差および突然変異の遺伝的演算子を用いて、より良いネットワークトポロジーを継続的に探索します。3つの実世界ドメインにおける実験により、この新しいアルゴリズムは、標準的なコネクショニスト理論に基づく改良システムや、知識ベースネットワークを成長させるための従来のアルゴリズムと比較して、汎化率を大幅に向上できることが示されました。
Query DAGs: A Practical Paradigm for Implementing Belief-Network Inference
クエリDAG：信念ネットワーク推論を実装するための実用的なパラダイム
We describe a new paradigm for implementing inference in belief networks, which consists of two steps: (1) compiling a belief network into an arithmetic expression called a Query DAG (Q-DAG); and (2) answering queries using a simple evaluation algorithm. Each node of a Q-DAG represents a numeric operation, a number, or a symbol for evidence. Each leaf node of a Q-DAG represents the answer to a network query, that is, the probability of some event of interest. It appears that Q-DAGs can be generated using any of the standard algorithms for exact inference in belief networks (we show how they can be generated using clustering and conditioning algorithms). The time and space complexity of a Q-DAG generation algorithm is no worse than the time complexity of the inference algorithm on which it is based. The complexity of a Q-DAG evaluation algorithm is linear in the size of the Q-DAG, and such inference amounts to a standard evaluation of the arithmetic expression it represents. The intended value of Q-DAGs is in reducing the software and hardware resources required to utilize belief networks in on-line, real-world applications. The proposed framework also facilitates the development of on-line inference on different software and hardware platforms due to the simplicity of the Q-DAG evaluation algorithm. Interestingly enough, Q-DAGs were found to serve other purposes: simple techniques for reducing Q-DAGs tend to subsume relatively complex optimization techniques for belief-network inference, such as network-pruning and computation-caching.
我々は、信念ネットワークで推論を実装するための新しいパラダイムについて説明します。これは、(1)信念ネットワークをクエリDAG (Q-DAG)と呼ばれる算術式にコンパイルするステップと、(2)単純な評価アルゴリズムを使用してクエリに回答するステップの2つのステップで構成されます。Q-DAGの各ノードは、数値演算、数値、または証拠のシンボルを表す。Q-DAGの各リーフ ノードは、ネットワーク クエリに対する回答、つまり、関心のあるイベントの確率を表します。Q-DAGは、ビリーフ ネットワークにおける正確な推論を行う標準的なアルゴリズムのいずれかを使用して生成できるようです(クラスタリング アルゴリズムとコンディショニング アルゴリズムを使用してQ-DAGを生成する方法を示します)。Q-DAG生成アルゴリズムの時間と空間の計算量は、それが基づいている推論アルゴリズムの時間計算量よりも悪くありません。Q-DAG評価アルゴリズムの計算量はQ-DAGのサイズに比例し、このような推論はQ-DAGが表す算術式の標準的な評価に相当します。Q-DAGの意図された価値は、オンラインの実際のアプリケーションでビリーフ ネットワークを利用するために必要なソフトウェアおよびハードウェア リソースを削減することにあります。提案されたフレームワークでは、Q-DAG評価アルゴリズムが単純であるため、さまざまなソフトウェアおよびハードウェア プラットフォーム上でのオンライン推論の開発も容易になります。興味深いことに、Q-DAGは他の目的にも役立つことが分かりました。Q-DAGを削減するための単純な手法は、ネットワークプルーニングや計算キャッシュといった、ビリーフネットワーク推論のための比較的複雑な最適化手法を包含する傾向があります。
Lifeworld Analysis
ライフワールド分析
We argue that the analysis of agent/environment interactions should be extended to include the conventions and invariants maintained by agents throughout their activity. We refer to this thicker notion of environment as a lifeworld and present a partial set of formal tools for describing structures of lifeworlds and the ways in which they computationally simplify activity. As one specific example, we apply the tools to the analysis of the Toast system and show how versions of the system with very different control structures in fact implement a common control structure together with different conventions for encoding task state in the positions or states of objects in the environment.
エージェントと環境の相互作用の分析は、エージェントが活動を通じて維持する慣習と不変条件を含めるように拡張されるべきであると主張します。我々は、この環境のより広い概念を生活世界と呼び、生活世界の構造と、それらが活動を計算的に単純化する方法を説明する形式的ツールの部分的なセットを提示します。具体的な例として、我々はこれらのツールをToastシステムの分析に適用し、非常に異なる制御構造を持つシステムのバージョンが、実際には共通の制御構造と、環境内のオブジェクトの位置または状態にタスク状態をエンコードするための異なる慣習を実装していることを示す。
Improved Heterogeneous Distance Functions
改良された異種距離関数
Instance-based learning techniques typically handle continuous and linear input values well, but often do not handle nominal input attributes appropriately. The Value Difference Metric (VDM) was designed to find reasonable distance values between nominal attribute values, but it largely ignores continuous attributes, requiring discretization to map continuous values into nominal values. This paper proposes three new heterogeneous distance functions, called the Heterogeneous Value Difference Metric (HVDM), the Interpolated Value Difference Metric (IVDM), and the Windowed Value Difference Metric (WVDM). These new distance functions are designed to handle applications with nominal attributes, continuous attributes, or both. In experiments on 48 applications the new distance metrics achieve higher classification accuracy on average than three previous distance functions on those datasets that have both nominal and continuous attributes.
インスタンスベース学習手法は通常、連続および線形の入力値を適切に処理しますが、名義入力属性を適切に処理できないことがよくあります。値差異メトリック(VDM)は、名義属性値間の適切な距離値を見つけるように設計されていますが、連続属性を大部分無視するため、連続値を名義値にマッピングするには離散化が必要です。本論文では、異種値差メトリック（HVDM）、補間値差メトリック（IVDM）、ウィンドウ値差メトリック（WVDM）と呼ばれる3つの新しい異種距離関数を提案します。これらの新しい距離関数は、名義属性、連続属性、またはその両方を持つアプリケーションに対応するように設計されています。48のアプリケーションを対象とした実験では、名義属性と連続属性の両方を持つデータセットにおいて、新しい距離メトリックは、従来の3つの距離関数よりも平均して高い分類精度を達成しました。