Building and Refining Abstract Planning Cases by Change of Representation Language
表現言語の変更による抽象計画事例の構築と改良
Abstraction is one of the most promising approaches to improve the performance of problem solvers. In several domains abstraction by dropping sentences of a domain description — as used in most hierarchical planners — has proven useful. In this paper we present examples which illustrate significant drawbacks of abstraction by dropping sentences. To overcome these drawbacks, we propose a more general view of abstraction involving the change of representation language. We have developed a new abstraction methodology and a related sound and complete learning algorithm that allows the complete change of representation language of planning cases from concrete to abstract. However, to achieve a powerful change of the representation language, the abstract language itself as well as rules which describe admissible ways of abstracting states must be provided in the domain model. This new abstraction approach is the core of Paris (Plan Abstraction and Refinement in an Integrated System), a system in which abstract planning cases are automatically learned from given concrete cases. An empirical study in the domain of process planning in mechanical engineering shows significant advantages of the proposed reasoning from abstract cases over classical hierarchical planning.
抽象化は、問題解決ツールのパフォーマンスを向上させる最も有望なアプローチの1つです。いくつかのドメインでは、ほとんどの階層型プランナーで使用されているように、ドメイン記述の文を削除することによる抽象化が有用であることが証明されています。本稿では、文を省略することによる抽象化の重大な欠点を示す例を示します。これらの欠点を克服するために、表現言語の変更を含む抽象化のより一般的な見方を提案します。私たちは、プランニングケースの表現言語を具体的なものから抽象的なものに完全に変更できる、新しい抽象化方法論と、関連する健全で完全な学習アルゴリズムを開発しました。ただし、表現言語の強力な変更を実現するには、抽象言語自体と、状態を抽象化する許容される方法を記述したルールをドメインモデルに提供する必要があります。この新しい抽象化アプローチは、抽象的なプランニングケースを特定の具体的なケースから自動的に学習するシステムであるParis (統合システムにおける計画の抽象化と洗練)の中核です。機械工学のプロセスプランニングの分野での実証的研究により、抽象ケースから提案された推論が従来の階層型プランニングよりも大きな利点を持つことが示されています。
Generalization of Clauses under Implication
含意に基づく節の一般化
In the area of inductive learning, generalization is a main operation, and the usual definition of induction is based on logical implication. Recently there has been a rising interest in clausal representation of knowledge in machine learning. Almost all inductive learning systems that perform generalization of clauses use the relation theta-subsumption instead of implication. The main reason is that there is a well-known and simple technique to compute least general generalizations under theta-subsumption, but not under implication. However generalization under theta-subsumption is inappropriate for learning recursive clauses, which is a crucial problem since recursion is the basic program structure of logic programs. We note that implication between clauses is undecidable, and we therefore introduce a stronger form of implication, called T-implication, which is decidable between clauses. We show that for every finite set of clauses there exists a least general generalization under T-implication. We describe a technique to reduce generalizations under implication of a clause to generalizations under theta-subsumption of what we call an expansion of the original clause. Moreover we show that for every non-tautological clause there exists a T-complete expansion, which means that every generalization under T-implication of the clause is reduced to a generalization under theta-subsumption of the expansion.
帰納学習の分野では、一般化が主要な操作であり、帰納の通常の定義は論理的含意に基づいています。最近、機械学習における知識の節表現への関心が高まっています。節の一般化を実行するほとんどすべての帰納学習システムは、含意ではなく関係シータ包含を使用します。その主な理由は、シータ包含の下では最小一般化を計算するよく知られた単純な手法があるが、含意の下では計算できないためです。しかし、シータ含意による一般化は再帰節の学習には不適切であり、これは再帰が論理プログラムの基本的なプログラム構造であるため重大な問題です。節間の含意は決定不可能であることに注目し、したがって節間で決定可能なT含意と呼ばれるより強い形式の含意を導入します。節の有限集合ごとに、T含意による最小一般化が存在することを示す。節の含意による一般化を、元の節の展開と呼ばれるもののシータ含意による一般化に縮減する手法について説明します。さらに、すべての非トートロジー節に対してT完全展開が存在することを示す。これは、節のT含意によるすべての一般化が、展開のシータ含意による一般化に縮減されることを意味します。
OPUS: An Efficient Admissible Algorithm for Unordered Search
OPUS：順序なし探索のための効率的な許容アルゴリズム
OPUS is a branch and bound search algorithm that enables efficient admissible search through spaces for which the order of search operator application is not significant. The algorithm’s search efficiency is demonstrated with respect to very large machine learning search spaces. The use of admissible search is of potential value to the machine learning community as it means that the exact learning biases to be employed for complex learning tasks can be precisely specified and manipulated. OPUS also has potential for application in other areas of artificial intelligence, notably, truth maintenance.
OPUSは、探索演算子の適用順序が重要でない空間で効率的な許容探索を可能にする分岐限定探索アルゴリズムです。このアルゴリズムの探索効率は、非常に大規模な機械学習探索空間に対して実証されています。許容探索の使用は、複雑な学習タスクに用いられる正確な学習バイアスを正確に指定および操作できることを意味するため、機械学習コミュニティにとって潜在的な価値があります。OPUSは、人工知能の他の分野、特に真理維持にも応用できる可能性があります。
Decision-Theoretic Foundations for Causal Reasoning
因果推論の決定理論的基礎
We present a definition of cause and effect in terms of decision-theoretic primitives and thereby provide a principled foundation for causal reasoning. Our definition departs from the traditional view of causation in that causal assertions may vary with the set of decisions available. We argue that this approach provides added clarity to the notion of cause. Also in this paper, we examine the encoding of causal relationships in directed acyclic graphs. We describe a special class of influence diagrams, those in canonical form, and show its relationship to Pearl’s representation of cause and effect. Finally, we show how canonical form facilitates counterfactual reasoning.
我々は、意思決定理論のプリミティブの観点から因果関係の定義を提示し、因果推論の原理的な基盤を提供します。我々の定義は、因果関係の主張が利用可能な意思決定の集合によって変化する可能性があるという点で、従来の因果関係の見方から逸脱しています。このアプローチは、原因の概念をより明確にすると主張します。また、本論文では、有向非巡回グラフにおける因果関係の符号化についても考察します。影響図の特別なクラスである正準形式について説明し、それがパールの因果関係表現とどのように関係するかを示します。最後に、正準形式が反事実的推論をどのように促進するかを示します。
Rule-based Machine Learning Methods for Functional Prediction
機能予測のためのルールベース機械学習手法
We describe a machine learning method for predicting the value of a real-valued function, given the values of multiple input variables. The method induces solutions from samples in the form of ordered disjunctive normal form (DNF) decision rules. A central objective of the method and representation is the induction of compact, easily interpretable solutions. This rule-based decision model can be extended to search efficiently for similar cases prior to approximating function values. Experimental results on real-world data demonstrate that the new techniques are competitive with existing machine learning and statistical methods and can sometimes yield superior regression performance.
複数の入力変数の値が与えられた場合に、実数値関数の値を予測する機械学習手法について説明します。この手法は、順序付き選言正規形（DNF）決定規則の形でサンプルから解を導出します。この手法と表現の中心的な目的は、簡潔で解釈しやすい解を導出することです。このルールベースの決定モデルは、関数値を近似する前に類似のケースを効率的に検索するように拡張することができます。実世界データを用いた実験結果は、これらの新しい手法が既存の機械学習および統計手法と競合し、場合によっては優れた回帰性能を発揮できることを実証しています。
Statistical Feature Combination for the Evaluation of Game Positions
ゲームポジション評価のための統計的特徴量の組み合わせ
This article describes an application of three well-known statistical methods in the field of game-tree search: using a large number of classified Othello positions, feature weights for evaluation functions with a game-phase-independent meaning are estimated by means of logistic regression, Fisher’s linear discriminant, and the quadratic discriminant function for normally distributed features. Thereafter, the playing strengths are compared by means of tournaments between the resulting versions of a world-class Othello program. In this application, logistic regression – which is used here for the first time in the context of game playing – leads to better results than the other approaches.
本稿では、ゲームツリー探索の分野における3つのよく知られた統計手法の応用について述べる。分類された多数のオセロ局面を用いて、ゲーム局面に依存しない意味を持つ評価関数の特徴重みを、ロジスティック回帰、フィッシャーの線形判別式、および正規分布する特徴に対する2次判別式を用いて推定します。その後、得られた世界クラスのオセロプログラム間でトーナメントを行い、プレイの強さを比較します。この応用において、ゲームプレイの文脈で初めて用いられるロジスティック回帰は、他の手法よりも優れた結果をもたらす。
Translating between Horn Representations and their Characteristic Models
ホーン表現とその特性モデル間の変換
Characteristic models are an alternative, model based, representation for Horn expressions. It has been shown that these two representations are incomparable and each has its advantages over the other. It is therefore natural to ask what is the cost of translating, back and forth, between these representations. Interestingly, the same translation questions arise in database theory, where it has applications to the design of relational databases. This paper studies the computational complexity of these problems. Our main result is that the two translation problems are equivalent under polynomial reductions, and that they are equivalent to the corresponding decision problem. Namely, translating is equivalent to deciding whether a given set of models is the set of characteristic models for a given Horn expression. We also relate these problems to the hypergraph transversal problem, a well known problem which is related to other applications in AI and for which no polynomial time algorithm is known. It is shown that in general our translation problems are at least as hard as the hypergraph transversal problem, and in a special case they are equivalent to it.
特性モデルは、ホーン表現の代替となるモデルベースの表現です。これら2つの表現は比較不可能であり、それぞれに利点があることが示されています。したがって、これらの表現間を相互に変換するコストはどの程度かという疑問が生じるのは当然です。興味深いことに、同じ変換の問題はデータベース理論にも生じ、関係データベースの設計に応用されています。本論文では、これらの問題の計算複雑性について検討します。主な結果は、2つの変換問題は多項式縮約の下では同等であり、対応する決定問題と同等であるということです。つまり、変換は、与えられたモデル集合が与えられたホーン式の特性モデル集合であるかどうかを判断することと同等です。また、これらの問題をハイパーグラフ横断問題に関連付けます。これはAIの他の応用にも関連し、多項式時間アルゴリズムが知られていない、よく知られた問題です。一般に、私たちの変換問題はハイパーグラフ横断問題と少なくとも同程度に難しく、特殊なケースではハイパーグラフ横断問題と同等であることが示されています。
Vision-Based Road Detection in Automotive Systems: A Real-Time Expectation-Driven Approach
自動車システムにおける視覚ベースの路面検出：リアルタイム期待駆動型アプローチ
The main aim of this work is the development of a vision-based road detection system fast enough to cope with the difficult real-time constraints imposed by moving vehicle applications. The hardware platform, a special-purpose massively parallel system, has been chosen to minimize system production and operational costs. This paper presents a novel approach to expectation-driven low-level image segmentation, which can be mapped naturally onto mesh-connected massively parallel SIMD architectures capable of handling hierarchical data structures. The input image is assumed to contain a distorted version of a given template; a multiresolution stretching process is used to reshape the original template in accordance with the acquired image content, minimizing a potential function. The distorted template is the process output.
本研究の主な目的は、移動車両アプリケーションによって課される厳しいリアルタイム制約に十分対応できる速度を持つ、ビジョンベースの道路検出システムの開発です。ハードウェアプラットフォームとして、専用の超並列システムを選択し、システムの製造コストと運用コストを最小限に抑えました。本論文では、階層型データ構造を処理できるメッシュ接続の超並列SIMDアーキテクチャに自然にマッピングできる、期待値駆動型の低レベル画像セグメンテーションに対する新しいアプローチを提示します。入力画像には、与えられたテンプレートの歪んだバージョンが含まれていると仮定します。マルチ解像度ストレッチ処理を使用して、取得した画像の内容に応じて元のテンプレートの形状を変更し、ポテンシャル関数を最小化します。歪んだテンプレートがプロセスの出力です。
Flexibly Instructable Agents
柔軟に指示可能なエージェント
This paper presents an approach to learning from situated, interactive tutorial instruction within an ongoing agent. Tutorial instruction is a flexible (and thus powerful) paradigm for teaching tasks because it allows an instructor to communicate whatever types of knowledge an agent might need in whatever situations might arise. To support this flexibility, however, the agent must be able to learn multiple kinds of knowledge from a broad range of instructional interactions. Our approach, called situated explanation, achieves such learning through a combination of analytic and inductive techniques. It combines a form of explanation-based learning that is situated for each instruction with a full suite of contextually guided responses to incomplete explanations. The approach is implemented in an agent called Instructo-Soar that learns hierarchies of new tasks and other domain knowledge from interactive natural language instructions. Instructo-Soar meets three key requirements of flexible instructability that distinguish it from previous systems: (1) it can take known or unknown commands at any instruction point; (2) it can handle instructions that apply to either its current situation or to a hypothetical situation specified in language (as in, for instance, conditional instructions); and (3) it can learn, from instructions, each class of knowledge it uses to perform tasks.
本稿では、実行中のエージェント内で状況に応じた対話型チュートリアル指示から学習するアプローチを紹介します。チュートリアル指示は、どのような状況でもエージェントが必要とする可能性のあるあらゆる種類の知識をインストラクターが伝えることができるため、タスクを教える上で柔軟(かつ強力)なパラダイムです。ただし、この柔軟性をサポートするには、エージェントが広範囲の指示対話から複数の種類の知識を学習できなければなりません。状況説明と呼ばれる私たちのアプローチは、分析技術と帰納的技術の組み合わせによってこのような学習を実現します。これは、各指示に状況に応じた説明ベースの学習形式と、不完全な説明に対する状況に応じて誘導される一連の応答を組み合わせたものです。このアプローチは、対話型自然言語指示から新しいタスクの階層やその他のドメイン知識を学習するInstructo-Soarと呼ばれるエージェントに実装されています。Instructo-Soarは、以前のシステムとは異なる柔軟な指示可能性の3つの主要な要件を満たしています。(1)どの指示ポイントでも既知または未知のコマンドを受け入れることができる(2)現在の状況、または言語で指定された仮定の状況（例えば条件付き命令）のいずれかに適用される命令を処理できること、(3)タスク実行に使用する各クラスの知識を命令から学習できること。
FLECS: Planning with a Flexible Commitment Strategy
FLECS：柔軟なコミットメント戦略を用いたプランニング
There has been evidence that least-commitment planners can efficiently handle planning problems that involve difficult goal interactions. This evidence has led to the common belief that delayed-commitment is the “best” possible planning strategy. However, we recently found evidence that eager-commitment planners can handle a variety of planning problems more efficiently, in particular those with difficult operator choices. Resigned to the futility of trying to find a universally successful planning strategy, we devised a planner that can be used to study which domains and problems are best for which planning strategies. In this article we introduce this new planning algorithm, FLECS, which uses a FLExible Commitment Strategy with respect to plan-step orderings. It is able to use any strategy from delayed-commitment to eager-commitment. The combination of delayed and eager operator-ordering commitments allows FLECS to take advantage of the benefits of explicitly using a simulated execution state and reasoning about planning constraints. FLECS can vary its commitment strategy across different problems and domains, and also during the course of a single planning problem. FLECS represents a novel contribution to planning in that it explicitly provides the choice of which commitment strategy to use while planning. FLECS provides a framework to investigate the mapping from planning domains and problems to efficient planning strategies.
最小コミットメントプランナーは、困難な目標相互作用を伴う計画問題を効率的に処理できるという証拠があります。この証拠から、遅延コミットメントが「最良」の計画戦略であるという一般的な考えが生まれた。しかし、最近、我々は、イーガーコミットメントプランナーが様々な計画問題、特にオペレータ選択が難しい問題をより効率的に処理できるという証拠を発見しました。普遍的に成功する計画戦略を見つけようとする試みは無駄だと諦め、どの領域と問題がどの計画戦略に最適かを研究するために使用できるプランナーを考案しました。本稿では、プランステップの順序付けに関してフレキシブルコミットメント戦略を用いるこの新しい計画アルゴリズムFLECSを紹介します。この戦略は、遅延コミットメントからイーガーコミットメントまで、あらゆる戦略を使用することができます。遅延コミットメントとイーガーコミットメントのオペレータ順序付けコミットメントを組み合わせることで、FLECSはシミュレートされた実行状態を明示的に使用し、計画制約について推論することの利点を活用できます。FLECSは、異なる問題や領域間で、また単一の計画問題の実行中にも、コミットメント戦略を変化させることができます。FLECSは、計画中にどのコミットメント戦略を使用するかを明示的に選択できるという点で、計画への新たな貢献となります。FLECSは、計画領域と問題から効率的な計画戦略へのマッピングを調査するための枠組みを提供します。
Diffusion of Context and Credit Information in Markovian Models
マルコフモデルにおけるコンテキストとクレジット情報の拡散
This paper studies the problem of ergodicity of transition probability matrices in Markovian models, such as hidden Markov models (HMMs), and how it makes very difficult the task of learning to represent long-term context for sequential data. This phenomenon hurts the forward propagation of long-term context information, as well as learning a hidden state representation to represent long-term context, which depends on propagating credit information backwards in time. Using results from Markov chain theory, we show that this problem of diffusion of context and credit is reduced when the transition probabilities approach 0 or 1, i.e., the transition probability matrices are sparse and the model essentially deterministic. The results found in this paper apply to learning approaches based on continuous optimization, such as gradient descent and the Baum-Welch algorithm.
本論文では、隠れマルコフモデル（HMM）などのマルコフモデルにおける遷移確率行列のエルゴード性の問題、そしてそれが時系列データの長期コンテキスト表現学習をいかに困難にするかを考察します。この現象は、長期コンテキスト情報の順方向伝播だけでなく、信用情報を時間的に逆方向に伝播させることに依存する長期コンテキストを表現するための隠れ状態表現の学習にも悪影響を及ぼす。マルコフ連鎖理論の結果を用いて、遷移確率が0または1に近づく、すなわち遷移確率行列がスパースでモデルが本質的に決定論的であるとき、このコンテキストと信用の拡散の問題が軽減されることを示す。本論文で得られた結果は、勾配降下法やバウム・ウェルチ法といった連続最適化に基づく学習手法にも当てはまる。
Improving Connectionist Energy Minimization
コネクショニストエネルギー最小化の改善
Symmetric networks designed for energy minimization such as Boltzman machines and Hopfield nets are frequently investigated for use in optimization, constraint satisfaction and approximation of NP-hard problems. Nevertheless, finding a global solution (i.e., a global minimum for the energy function) is not guaranteed and even a local solution may take an exponential number of steps. We propose an improvement to the standard local activation function used for such networks. The improved algorithm guarantees that a global minimum is found in linear time for tree-like subnetworks. The algorithm, called activate, is uniform and does not assume that the network is tree-like. It can identify tree-like subnetworks even in cyclic topologies (arbitrary networks) and avoid local minima along these trees. For acyclic networks, the algorithm is guaranteed to converge to a global minimum from any initial state of the system (self-stabilization) and remains correct under various types of schedulers. On the negative side, we show that in the presence of cycles, no uniform algorithm exists that guarantees optimality even under a sequential asynchronous scheduler. An asynchronous scheduler can activate only one unit at a time while a synchronous scheduler can activate any number of units in a single time step. In addition, no uniform algorithm exists to optimize even acyclic networks when the scheduler is synchronous. Finally, we show how the algorithm can be improved using the cycle-cutset scheme. The general algorithm, called activate-with-cutset, improves over activate and has some performance guarantees that are related to the size of the network’s cycle-cutset.
ボルツマンマシンやホップフィールドネットなどのエネルギー最小化のために設計された対称ネットワークは、最適化、制約充足、NP困難問題の近似への応用について頻繁に研究されています。しかしながら、大域解（すなわち、エネルギー関数の大域的最小値）の発見は保証されておらず、局所解でさえ指数関数的なステップ数を要する場合があります。本稿では、このようなネットワークに使用される標準的な局所活性化関数の改良を提案します。改良されたアルゴリズムは、ツリー状サブネットワークにおいて線形時間で大域的最小値を見つけることを保証します。activateと呼ばれるこのアルゴリズムは均一であり、ネットワークがツリー状であることを仮定しません。このアルゴリズムは、循環トポロジ（任意のネットワーク）であってもツリー状サブネットワークを識別し、これらのツリーに沿った局所的最小値を回避することができます。非循環ネットワークの場合、このアルゴリズムはシステムの任意の初期状態から大域的最小値に収束することが保証されており（自己安定化）、様々なタイプのスケジューラの下でも正しいままです。欠点としては、サイクルが存在する場合、逐次型非同期スケジューラの下でも最適性を保証する均一なアルゴリズムは存在しないことを示します。非同期スケジューラは一度に1つのユニットしかアクティブ化できませんが、同期スケジューラは1つのタイムステップで任意の数のユニットをアクティブ化できます。さらに、スケジューラが同期型である場合、非循環ネットワークでさえも最適化する均一なアルゴリズムは存在しません。最後に、サイクルカットセット法を用いてこのアルゴリズムをどのように改良できるかを示します。activate-with-cutsetと呼ばれる一般的なアルゴリズムは、activateよりも改善されており、ネットワークのサイクル カットセットのサイズに関連するパフォーマンス保証がいくつかあります。
Learning Membership Functions in a Function-Based Object Recognition System
関数ベース物体認識システムにおけるメンバーシップ関数の学習
Functionality-based recognition systems recognize objects at the category level by reasoning about how well the objects support the expected function. Such systems naturally associate a “measure of goodness” or “membership value” with a recognized object. This measure of goodness is the result of combining individual measures, or membership values, from potentially many primitive evaluations of different properties of the object’s shape. A membership function is used to compute the membership value when evaluating a primitive of a particular physical property of an object. In previous versions of a recognition system known as Gruff, the membership function for each of the primitive evaluations was hand-crafted by the system designer. In this paper, we provide a learning component for the Gruff system, called Omlet, that automatically learns membership functions given a set of example objects labeled with their desired category measure. The learning algorithm is generally applicable to any problem in which low-level membership values are combined through an and-or tree structure to give a final overall membership value.
機能ベースの認識システムは、オブジェクトが期待される機能をどの程度サポートしているかを推論することにより、カテゴリレベルでオブジェクトを認識します。このようなシステムは、認識したオブジェクトに「良さの尺度」または「メンバーシップ値」を自然に関連付けます。この良さの尺度は、オブジェクトの形状のさまざまな特性に関する、場合によっては多数のプリミティブ評価から得られる個々の尺度、またはメンバーシップ値を組み合わせた結果です。メンバーシップ関数は、物体の特定の物理的特性のプリミティブを評価する際に、メンバーシップ値を計算するために使用されます。Gruffと呼ばれる認識システムの以前のバージョンでは、各プリミティブ評価のメンバーシップ関数はシステム設計者によって手作業で作成されていました。本稿では、Gruffシステム用の学習コンポーネントであるOmletを提供します。Omletは、望ましいカテゴリ尺度でラベル付けされたサンプルオブジェクトのセットが与えられた場合に、メンバーシップ関数を自動的に学習します。この学習アルゴリズムは、低レベルのメンバーシップ値をAND-ORツリー構造で組み合わせて最終的な全体的なメンバーシップ値を生成するあらゆる問題に一般的に適用可能です。
An Integrated Framework for Learning and Reasoning
学習と推論のための統合フレームワーク
Learning and reasoning are both aspects of what is considered to be intelligence. Their studies within AI have been separated historically, learning being the topic of machine learning and neural networks, and reasoning falling under classical (or symbolic) AI. However, learning and reasoning are in many ways interdependent. This paper discusses the nature of some of these interdependencies and proposes a general framework called FLARE, that combines inductive learning using prior knowledge together with reasoning in a propositional setting. Several examples that test the framework are presented, including classical induction, many important reasoning protocols and two simple expert systems.
学習と推論は、どちらも知能とみなされるものの要素です。AIにおけるこれらの研究は歴史的に分離されており、学習は機械学習とニューラルネットワークの分野であり、推論は古典的（またはシンボリック）AIの分野です。しかし、学習と推論は多くの点で相互に依存しています。本論文では、これらの相互依存性の性質について議論し、事前知識を用いた帰納的学習と命題設定における推論を組み合わせたFLAREと呼ばれる一般的なフレームワークを提案します。このフレームワークを検証する例として、古典的帰納法、多くの重要な推論プロトコル、そして2つのシンプルなエキスパートシステムなどが挙げられます。
Using Qualitative Hypotheses to Identify Inaccurate Data
質的仮説を用いた不正確なデータの識別
Identifying inaccurate data has long been regarded as a significant and difficult problem in AI. In this paper, we present a new method for identifying inaccurate data on the basis of qualitative correlations among related data. First, we introduce the definitions of related data and qualitative correlations among related data. Then we put forward a new concept called support coefficient function (SCF). SCF can be used to extract, represent, and calculate qualitative correlations among related data within a dataset. We propose an approach to determining dynamic shift intervals of inaccurate data, and an approach to calculating possibility of identifying inaccurate data, respectively. Both of the approaches are based on SCF. Finally we present an algorithm for identifying inaccurate data by using qualitative correlations among related data as confirmatory or disconfirmatory evidence. We have developed a practical system for interpreting infrared spectra by applying the method, and have fully tested the system against several hundred real spectra. The experimental results show that the method is significantly better than the conventional methods used in many similar systems.
不正確なデータを識別することは、長い間、AIにおける重要かつ困難な問題と考えられてきた。本論文では、関連データ間の質的相関に基づいて不正確なデータを識別する新しい手法を提示します。まず、関連データの定義と関連データ間の質的相関を紹介します。次に、サポート係数関数(SCF)と呼ばれる新しい概念を提唱します。SCFは、データセット内の関連データ間の質的相関を抽出、表現、計算するために使用できます。不正確なデータの動的シフト間隔を決定するアプローチと、不正確なデータを識別する可能性を計算するアプローチをそれぞれ提案します。どちらのアプローチもSCFに基づいています。最後に、関連データ間の質的相関を確証的または反証的な証拠として使用して、不正確なデータを識別するアルゴリズムを紹介します。この方法を適用して、赤外線スペクトルを解釈するための実用的なシステムを開発し、数百の実際のスペクトルに対してシステムを徹底的にテストしました。実験結果は、この方法が多くの同様のシステムで使用されている従来の方法よりも大幅に優れていることを示しています。
Induction of First-Order Decision Lists: Results on Learning the Past Tense of English Verbs
一階決定リストの誘導：英語動詞の過去形の学習結果
This paper presents a method for inducing logic programs from examples that learns a new class of concepts called first-order decision lists, defined as ordered lists of clauses each ending in a cut. The method, called FOIDL, is based on FOIL (Quinlan, 1990) but employs intensional background knowledge and avoids the need for explicit negative examples. It is particularly useful for problems that involve rules with specific exceptions, such as learning the past-tense of English verbs, a task widely studied in the context of the symbolic/connectionist debate. FOIDL is able to learn concise, accurate programs for this problem from significantly fewer examples than previous methods (both connectionist and symbolic).
本論文では、例から論理プログラムを誘導する手法を提示します。この手法は、カットで終わる節の順序付きリストとして定義される、一階決定リストと呼ばれる新しい概念クラスを学習します。FOIDLと呼ばれるこの手法は、FOIL (Quinlan, 1990)に基づいているが、内包的背景知識を使用し、明示的な負の例を必要としない。これは、英語の動詞の過去形を学習するなど、特定の例外を伴う規則を含む問題に特に有用です。このタスクは、記号的/コネクショニスト論争の文脈で広く研究されています。FOIDLは、この問題に対する簡潔で正確なプログラムを、従来の手法(コネクショニストおよび記号的)よりもはるかに少ない例から学習することができます。