Journal of Artificial Intelligence Resarch Vol. 11 (1999)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。
Semantic Similarity in a Taxonomy: An Information-Based Measure and its Application to Problems of Ambiguity in Natural Language
分類法における意味的類似性：情報に基づく尺度と自然言語における曖昧性の問題への応用
This article presents a measure of semantic similarity in an IS-A taxonomy based on the notion of shared information content. Experimental evaluation against a benchmark set of human similarity judgments demonstrates that the measure performs better than the traditional edge-counting approach. The article presents algorithms that take advantage of taxonomic similarity in resolving syntactic and semantic ambiguity, along with experimental results demonstrating their effectiveness.
本稿では、共有情報量の概念に基づくIS-A分類における意味的類似性の尺度を提示します。人間による類似性判断のベンチマークセットを用いた実験的評価により、この尺度は従来のエッジカウントアプローチよりも優れた性能を示すことが示されました。本稿では、分類上の類似性を利用して構文的および意味的な曖昧さを解決するアルゴリズムと、その有効性を示す実験結果を提示します。
Cox’s Theorem Revisited
Coxの定理の再考
The assumptions needed to prove Cox’s Theorem are discussed and examined. Various sets of assumptions under which a Cox-style theorem can be proved are provided, although all are rather strong and, arguably, not natural.
Coxの定理を証明するために必要な仮定について議論し、検証します。Coxスタイルの定理を証明できる様々な仮定を提示するが、いずれもかなり強力であり、おそらく自然ではない。
Markov Localization for Mobile Robots in Dynamic Environments
動的環境における移動ロボットのマルコフ局所化
Localization, that is the estimation of a robot’s location from sensor data, is a fundamental problem in mobile robotics. This papers presents a version of Markov localization which provides accurate position estimates and which is tailored towards dynamic environments. The key idea of Markov localization is to maintain a probability density over the space of all locations of a robot in its environment. Our approach represents this space metrically, using a fine-grained grid to approximate densities. It is able to globally localize the robot from scratch and to recover from localization failures. It is robust to approximate models of the environment (such as occupancy grid maps) and noisy sensors (such as ultrasound sensors). Our approach also includes a filtering technique which allows a mobile robot to reliably estimate its position even in densely populated environments in which crowds of people block the robot’s sensors for extended periods of time. The method described here has been implemented and tested in several real-world applications of mobile robots, including the deployments of two mobile robots as interactive museum tour-guides.
位置推定、すなわちセンサーデータからロボットの位置を推定することは、移動ロボット工学における基本的な問題です。本論文では、正確な位置推定を可能にし、動的な環境に適したマルコフ位置推定の一形態を提示します。マルコフ位置推定の核となる考え方は、ロボットの環境内におけるすべての位置の空間全体にわたって確率密度を維持することです。本手法では、この空間を計量的に表現し、細粒度グリッドを用いて密度を近似します。本手法は、ロボットをゼロからグローバルに位置推定し、位置推定の失敗から回復することが可能です。また、環境の近似モデル（占有グリッドマップなど）やノイズの多いセンサー（超音波センサーなど）に対しても堅牢です。本手法には、人口密度が高く、群衆がロボットのセンサーを長時間遮るような環境でも、移動ロボットが確実に位置を推定できるようにするフィルタリング技術も含まれています。本手法は、インタラクティブな美術館ツアーガイドとして2台の移動ロボットを配備するなど、移動ロボットのいくつかの実世界アプリケーションで実装・テストされています。
The Complexity of Reasoning about Spatial Congruence
空間的合同性に関する推論の複雑さ
In the recent literature of Artificial Intelligence, an intensive research effort has been spent, for various algebras of qualitative relations used in the representation of temporal and spatial knowledge, on the problem of classifying the computational complexity of reasoning problems for subsets of algebras. The main purpose of these researches is to describe a restricted set of maximal tractable subalgebras, ideally in an exhaustive fashion with respect to the hosting algebras. In this paper we introduce a novel algebra for reasoning about Spatial Congruence, show that the satisfiability problem in the spatial algebra MC-4 is NP-complete, and present a complete classification of tractability in the algebra, based on the individuation of three maximal tractable subclasses, one containing the basic relations. The three algebras are formed by 14, 10 and 9 relations out of 16 which form the full algebra.
最近の人工知能の文献では、時間的および空間的な知識の表現に使用される質的関係のさまざまな代数について、代数のサブセットの推論問題の計算複雑性を分類する問題に集中的な研究努力が費やされてきました。これらの研究の主な目的は、理想的にはホスティング代数に関して網羅的な方法で、制限された最大に扱いやすいサブ代数の集合を記述することです。この論文では、空間合同について推論するための新しい代数を紹介し、空間代数MC-4の充足可能性問題がNP完全であることを示します。また、基本関係を含む1つのクラスを含む3つの最大に扱いやすいサブクラスの個別化に基づいて、代数の扱いやすさの完全な分類を提示します。3つの代数は、完全な代数を形成する16の関係のうちの14、10、および9の関係によって形成されます。
Committee-Based Sample Selection for Probabilistic Classifiers
確率的分類器のための委員会ベースのサンプル選択
In many real-world learning tasks, it is expensive to acquire a sufficient number of labeled examples for training. This paper investigates methods for reducing annotation cost by `sample selection’. In this approach, during training the learning program examines many unlabeled examples and selects for labeling only those that are most informative at each stage. This avoids redundantly labeling examples that contribute little new information. Our work follows on previous research on Query By Committee, extending the committee-based paradigm to the context of probabilistic classification. We describe a family of empirical methods for committee-based sample selection in probabilistic classification models, which evaluate the informativeness of an example by measuring the degree of disagreement between several model variants. These variants (the committee) are drawn randomly from a probability distribution conditioned by the training set labeled so far. The method was applied to the real-world natural language processing task of stochastic part-of-speech tagging. We find that all variants of the method achieve a significant reduction in annotation cost, although their computational efficiency differs. In particular, the simplest variant, a two member committee with no parameters to tune, gives excellent results. We also show that sample selection yields a significant reduction in the size of the model used by the tagger.
多くの実世界の学習タスクでは、訓練のために十分な数のラベル付きサンプルを取得するにはコストがかかります。本稿では、「サンプル選択」によってアノテーションコストを削減する方法を検討します。このアプローチでは、学習プログラムはトレーニング中に多数のラベルなし例を検査し、各段階で最も有益な例のみにラベルを付ける。これにより、新しい情報がほとんど提供されない例に冗長にラベルを付けるのを回避できます。本研究は、Query By Committeeに関する先行研究を踏襲したもので、委員会ベースのパラダイムを確率分類のコンテキストに拡張します。確率分類モデルにおける委員会ベースのサンプル選択のための経験的手法群について説明します。この手法は、複数のモデルバリアント間の不一致度を測定することで例の有益性を評価します。これらのバリアント（委員会）は、これまでにラベル付けされたトレーニングセットによって条件付けられた確率分布からランダムに抽出されます。この手法は、確率的品詞タグ付けという実際の自然言語処理タスクに適用されました。この手法のすべてのバリアントにおいて、計算効率は異なるものの、アノテーションコストが大幅に削減されることがわかった。特に、調整すべきパラメータのない2人構成の委員会という最も単純なバリアントは、優れた結果をもたらす。また、サンプル選択により、タグ付けツールが使用するモデルのサイズが大幅に削減されることも示します。
Decentralized Markets versus Central Control: A Comparative Study
分散型市場と中央集権的制御：比較研究
Multi-Agent Systems (MAS) promise to offer solutions to problems where established, older paradigms fall short. In order to validate such claims that are repeatedly made in software agent publications, empirical in-depth studies of advantages and weaknesses of multi-agent solutions versus conventional ones in practical applications are needed. Climate control in large buildings is one application area where multi-agent systems, and market-oriented programming in particular, have been reported to be very successful, although central control solutions are still the standard practice. We have therefore constructed and implemented a variety of market designs for this problem, as well as different standard control engineering solutions. This article gives a detailed analysis and comparison, so as to learn about differences between standard versus agent approaches, and yielding new insights about benefits and limitations of computational markets. An important outcome is that “local information plus market communication produces global control”.
マルチエージェントシステム（MAS）は、既存の古いパラダイムでは不十分な問題に対する解決策を提供することを約束します。ソフトウェアエージェントに関する出版物で繰り返し主張されているこうした主張を検証するためには、実用分野におけるマルチエージェントソリューションと従来のソリューションの長所と短所に関する、経験的かつ詳細な研究が必要です。大規模ビルにおける空調制御は、マルチエージェントシステム、特に市場指向プログラミングが非常に成功していると報告されている応用分野の一つですが、依然として中央制御ソリューションが標準的な手法となっています。そこで我々は、この問題に対して、様々な市場設計と様々な標準的な制御工学ソリューションを構築・実装しました。本稿では、標準的なアプローチとエージェントアプローチの違いを理解し、計算市場の利点と限界に関する新たな知見を得るために、詳細な分析と比較を行います。重要な成果として、「局所情報と市場コミュニケーションを組み合わせることで、グローバルな制御が実現される」ことが挙げられます。
Reasoning about Minimal Belief and Negation as Failure
最小確信と否定を失敗とみなす推論
We investigate the problem of reasoning in the propositional fragment of MBNF, the logic of minimal belief and negation as failure introduced by Lifschitz, which can be considered as a unifying framework for several nonmonotonic formalisms, including default logic, autoepistemic logic, circumscription, epistemic queries, and logic programming. We characterize the complexity and provide algorithms for reasoning in propositional MBNF. In particular, we show that entailment in propositional MBNF lies at the third level of the polynomial hierarchy, hence it is harder than reasoning in all the above mentioned propositional formalisms for nonmonotonic reasoning. We also prove the exact correspondence between negation as failure in MBNF and negative introspection in Moore’s autoepistemic logic.
リフシッツによって導入されたMBNFの命題フラグメント、すなわち最小信念の論理と失敗としての否定における推論の問題を考察します。MBNFは、デフォルト論理、自己認識論理、サーカムスクリプション、認識的クエリ、論理プログラミングなど、いくつかの非単調形式主義を統合する枠組みとみなすことができます。命題MBNFにおける推論の複雑さを特徴づけ、アルゴリズムを提供します。特に、命題MBNFにおける含意は多項式階層の第3レベルに位置し、したがって、非単調推論のための上記のすべての命題形式主義における推論よりも困難であることを示す。また、MBNFにおける失敗としての否定とムーアの自己認識論理における否定的内省との間の正確な対応を証明します。
Evolutionary Algorithms for Reinforcement Learning
強化学習のための進化的アルゴリズム
There are two distinct approaches to solving reinforcement learning problems, namely, searching in value function space and searching in policy space. Temporal difference methods and evolutionary algorithms are well-known examples of these approaches. Kaelbling, Littman and Moore recently provided an informative survey of temporal difference methods. This article focuses on the application of evolutionary algorithms to the reinforcement learning problem, emphasizing alternative policy representations, credit assignment methods, and problem-specific genetic operators. Strengths and weaknesses of the evolutionary approach to reinforcement learning are presented, along with a survey of representative applications.
強化学習問題を解くには、価値関数空間での探索とポリシー空間での探索という2つの異なるアプローチがあります。時間差分法と進化的アルゴリズムは、これらのアプローチのよく知られた例です。Kaelbling、Littman、およびMooreは最近、時間差分法に関する有益な調査研究を行った。本稿では、強化学習問題への進化的アルゴリズムの適用に焦点を当て、代替ポリシー表現、クレジット割り当て法、および問題固有の遺伝的演算子に重点を置く。強化学習への進化的アプローチの長所と短所、および代表的な応用例の調査を示す。
Unifying Class-Based Representation Formalisms
クラスベース表現形式の統合
The notion of class is ubiquitous in computer science and is central in many formalisms for the representation of structured knowledge used both in knowledge representation and in databases. In this paper we study the basic issues underlying such representation formalisms and single out both their common characteristics and their distinguishing features. Such investigation leads us to propose a unifying framework in which we are able to capture the fundamental aspects of several representation languages used in different contexts. The proposed formalism is expressed in the style of description logics, which have been introduced in knowledge representation as a means to provide a semantically well-founded basis for the structural aspects of knowledge representation systems. The description logic considered in this paper is a subset of first order logic with nice computational characteristics. It is quite expressive and features a novel combination of constructs that has not been studied before. The distinguishing constructs are number restrictions, which generalize existence and functional dependencies, inverse roles, which allow one to refer to the inverse of a relationship, and possibly cyclic assertions, which are necessary for capturing real world domains. We are able to show that it is precisely such combination of constructs that makes our logic powerful enough to model the essential set of features for defining class structures that are common to frame systems, object-oriented database languages, and semantic data models. As a consequence of the established correspondences, several significant extensions of each of the above formalisms become available. The high expressiveness of the logic we propose and the need for capturing the reasoning in different contexts forces us to distinguish between unrestricted and finite model reasoning. A notable feature of our proposal is that reasoning in both cases is decidable. We argue that, by virtue of the high expressive power and of the associated reasoning capabilities on both unrestricted and finite models, our logic provides a common core for class-based representation formalisms.
クラスの概念はコンピュータサイエンスのいたるところに見られ、知識表現とデータベースの両方で使用される構造化知識の表現のための多くの形式主義において中心的な役割を果たしています。本稿では、このような表現形式主義の根底にある基本的な問題を研究し、それらの共通の特徴と際立った特徴の両方を明らかにします。このような調査により、異なるコンテキストで使用される複数の表現言語の基本的な側面を捉えることができる統一的なフレームワークを提案することになります。提案される形式主義は、知識表現システムの構造的側面に意味的にしっかりとした基盤を提供する手段として知識表現に導入された記述論理のスタイルで表現されます。本論文で考察する記述論理は、優れた計算特性を持つ一階述語論理のサブセットです。非常に表現力に富み、これまで研究されていなかった斬新な構成要素の組み合わせを特徴とします。特徴的な構成要素は、存在と機能的依存関係を一般化する数制約、関係の逆を参照することを可能にする逆役割、そして現実世界のドメインを捉えるために必要となる可能性のある循環的表明です。まさにこうした構成要素の組み合わせこそが、フレームシステム、オブジェクト指向データベース言語、そしてセマンティックデータモデルに共通するクラス構造を定義するための必須機能群をモデル化できるほど強力な論理を実現していることを示すことができます。確立された対応関係の結果として、上記の各形式主義のいくつかの重要な拡張が可能となります。提案する論理の高い表現力と、異なる文脈における推論を捉える必要性から、非制約モデル推論と有限モデル推論を区別する必要があります。本提案の注目すべき特徴は、どちらの場合も推論が決定可能であることです。高い表現力と、制限のないモデルと有限なモデルの両方における関連する推論能力により、我々の論理はクラスベースの表現形式主義に共通の核を提供すると主張します。
Popular Ensemble Methods: An Empirical Study
一般的なアンサンブル法：実証的研究
An ensemble consists of a set of individually trained classifiers (such as neural networks or decision trees) whose predictions are combined when classifying novel instances. Previous research has shown that an ensemble is often more accurate than any of the single classifiers in the ensemble. Bagging (Breiman, 1996c) and Boosting (Freund & Shapire, 1996; Shapire, 1990) are two relatively new but popular methods for producing ensembles. In this paper we evaluate these methods on 23 data sets using both neural networks and decision trees as our classification algorithm. Our results clearly indicate a number of conclusions. First, while Bagging is almost always more accurate than a single classifier, it is sometimes much less accurate than Boosting. On the other hand, Boosting can create ensembles that are less accurate than a single classifier — especially when using neural networks. Analysis indicates that the performance of the Boosting methods is dependent on the characteristics of the data set being examined. In fact, further results show that Boosting ensembles may overfit noisy data sets, thus decreasing its performance. Finally, consistent with previous studies, our work suggests that most of the gain in an ensemble’s performance comes in the first few classifiers combined; however, relatively large gains can be seen up to 25 classifiers when Boosting decision trees.
アンサンブルは、個別にトレーニングされた分類器のセット(ニューラル ネットワークや決定木など)で構成され、新規インスタンスを分類するときには、それらの予測が組み合わされます。以前の研究では、アンサンブルは多くの場合、アンサンブル内の単一の分類器のいずれよりも正確であることが示されています。バギング(Breiman、1996c)とブースティング(Freund & Shapire、1996、Shapire、1990)は、アンサンブルを作成するための2つの比較的新しい方法ですが、一般的な方法です。この論文では、分類アルゴリズムとしてニューラル ネットワークと決定木の両方を使用し、23のデータ セットでこれらの方法を評価しました。その結果、いくつかの結論が明確に示されています。まず、バギングはほとんどの場合単一の分類器よりも正確ですが、ブースティングよりもはるかに正確でない場合があります。一方、ブースティングは、特にニューラル ネットワークを使用する場合、単一の分類器よりも正確性の低いアンサンブルを作成する可能性があります。分析により、ブースティング方法のパフォーマンスは、調査するデータ セットの特性に依存することが示されています。実際、さらなる結果から、ブースティングアンサンブルはノイズの多いデータセットに過剰適合し、その結果パフォーマンスが低下する可能性があることが示されています。最後に、以前の研究と一致して、私たちの研究は、アンサンブルのパフォーマンスの向上の大部分は最初のいくつかの分類器を組み合わせたときに得られることを示唆しています。ただし、決定木をブースティングすると、分類器が25個まで比較的大きな向上が見られます。
Identifying Mislabeled Training Data
誤ったラベル付けがされた学習データの識別
This paper presents a new approach to identifying and eliminating mislabeled training instances for supervised learning. The goal of this approach is to improve classification accuracies produced by learning algorithms by improving the quality of the training data. Our approach uses a set of learning algorithms to create classifiers that serve as noise filters for the training data. We evaluate single algorithm, majority vote and consensus filters on five datasets that are prone to labeling errors. Our experiments illustrate that filtering significantly improves classification accuracy for noise levels up to 30 percent. An analytical and empirical evaluation of the precision of our approach shows that consensus filters are conservative at throwing away good data at the expense of retaining bad data and that majority filters are better at detecting bad data at the expense of throwing away good data. This suggests that for situations in which there is a paucity of data, consensus filters are preferable, whereas majority vote filters are preferable for situations with an abundance of data.
本論文では、教師あり学習において誤ってラベル付けされた学習インスタンスを識別・除去するための新しいアプローチを提示します。このアプローチの目的は、学習データの品質を向上させることで、学習アルゴリズムによって生成される分類精度を向上させることです。本アプローチでは、一連の学習アルゴリズムを用いて、学習データのノイズフィルターとして機能する分類器を作成します。ラベル付けエラーが発生しやすい5つのデータセットにおいて、単一アルゴリズム、多数決、コンセンサスフィルターを評価します。実験では、フィルタリングによってノイズレベルが最大30%の場合の分類精度が大幅に向上することを示す。我々のアプローチの精度に関する分析的および実証的な評価により、コンセンサスフィルタは不良データを保持することで良質なデータを破棄する点で保守的であるのに対し、多数決フィルタは良質なデータを破棄することで不良データの検出に優れていることが示されました。これは、データが不足している状況ではコンセンサスフィルタが適しているのに対し、データが豊富な状況では多数決フィルタが適していることを示唆しています。
Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
意思決定理論的プランニング：構造的仮定と計算力
Planning under uncertainty is a central problem in the study of automated sequential decision making, and has been addressed by researchers in many different fields, including AI planning, decision analysis, operations research, control theory and economics. While the assumptions and perspectives adopted in these areas often differ in substantial ways, many planning problems of interest to researchers in these fields can be modeled as Markov decision processes (MDPs) and analyzed using the techniques of decision theory. This paper presents an overview and synthesis of MDP-related methods, showing how they provide a unifying framework for modeling many classes of planning problems studied in AI. It also describes structural properties of MDPs that, when exhibited by particular classes of problems, can be exploited in the construction of optimal or approximately optimal policies or plans. Planning problems commonly possess structure in the reward and value functions used to describe performance criteria, in the functions used to describe state transitions and observations, and in the relationships among features used to describe states, actions, rewards, and observations. Specialized representations, and algorithms employing these representations, can achieve computational leverage by exploiting these various forms of structure. Certain AI techniques — in particular those based on the use of structured, intensional representations — can be viewed in this way. This paper surveys several types of representations for both classical and decision-theoretic planning problems, and planning algorithms that exploit these representations in a number of different ways to ease the computational burden of constructing policies or plans. It focuses primarily on abstraction, aggregation and decomposition techniques based on AI-style representations.
不確実性下でのプランニングは、自動化された逐次意思決定の研究における中心的な問題であり、AIプランニング、意思決定分析、オペレーションズ・リサーチ、制御理論、経済学など、さまざまな分野の研究者によって研究されてきました。これらの分野で採用されている前提や視点はしばしば大きく異なりますが、これらの分野の研究者が関心を持つ多くの計画問題は、マルコフ決定過程（MDP）としてモデル化し、意思決定理論の手法を用いて分析することができます。本稿では、MDP関連手法の概要と統合を示し、AIで研究されている多くの種類の計画問題をモデル化するための統一的な枠組みを提供する方法を示します。また、特定の種類の問題に見られるMDPの構造的特性について説明し、最適または近似最適なポリシーや計画の構築に活用できる可能性についても考察します。計画問題は、パフォーマンス基準を記述するために使用される報酬関数と価値関数、状態遷移と観測を記述するために使用される関数、そして状態、行動、報酬、観測を記述するために使用される特徴間の関係において、一般的に構造を有しています。特殊な表現、およびそれらの表現を用いるアルゴリズムは、これらの様々な形態の構造を活用することで計算上の効果を発揮します。特定のAI技術、特に構造化された内包的表現を用いる技術は、このように捉えることができます。本論文では、古典的および意思決定理論的な計画問題における数種類の表現、そしてこれらの表現を様々な方法で活用してポリシーや計画の構築における計算負荷を軽減する計画アルゴリズムについて概説します。特に、AIスタイルの表現に基づく抽象化、集約、分解手法に焦点を当てる。