Pattern Matching and Discourse Processing in Information Extraction from Japanese Text
日本語テキストからの情報抽出におけるパターンマッチングと談話処理
Information extraction is the task of automaticallypicking up information of interest from an unconstrained text. Informationof interest is usually extracted in two steps. First, sentence level processing locates relevant pieces of information scatteredthroughout the text; second, discourse processing merges coreferential information to generate the output. In the first step, pieces of information are locally identified without recognizing any relationships among them. A key word search or simple patternsearch can achieve this purpose. The second step requires deeperknowledge in order to understand relationships among separately identified pieces of information. Previous information extraction systems focused on the first step, partly because they were not required to link up each piece of information with other pieces. To link the extracted pieces of information and map them onto a structuredoutput format, complex discourse processing is essential. This paperreports on a Japanese information extraction system that merges information using a pattern matcher and discourse processor. Evaluationresults show a high level of system performance which approaches human performance.
情報抽出とは、制約のないテキストから関心のある情報を自動的に拾い上げるタスクです。関心のある情報は通常、2つの段階で抽出されます。まず、文レベルの処理でテキスト全体に散在する関連情報を見つけ出します。次に、談話処理で共参照情報を統合し、出力を生成します。最初の段階では、情報間の関係性を認識せずに、情報の各部分をローカルに識別します。キーワード検索や単純なパターン検索でこの目的を達成できます。2番目の段階では、個別に識別された情報間の関係性を理解するために、より深い知識が必要です。従来の情報抽出システムは、各情報と他の情報をリンクする必要がなかったこともあり、最初の段階に重点を置いていました。抽出された情報の各部分をリンクし、構造化された出力形式にマッピングするには、複雑な談話処理が不可欠です。本稿では、パターンマッチングと談話プロセッサを用いて情報を統合する日本語情報抽出システムについて報告します。評価結果は、人間のパフォーマンスに匹敵する高いレベルのシステム性能を示しています。
Provably Bounded-Optimal Agents
証明可能有界最適エージェント
Since its inception, artificial intelligence has relied upon a theoretical foundation centered around perfect rationality as the desired property of intelligent systems. We argue, as others have done, that this foundation is inadequate because it imposes fundamentally unsatisfiable requirements. As a result, there has arisen a wide gap between theory and practice in AI, hindering progress in the field. We propose instead a property called bounded optimality. Roughly speaking, an agent is bounded-optimal if its program is a solution to the constrained optimization problem presented by its architecture and the task environment. We show how to construct agents with this property for a simple class of machine architectures in a broad class of real-time environments. We illustrate these results using a simple model of an automated mail sorting facility. We also define a weaker property, asymptotic bounded optimality (ABO), that generalizes the notion of optimality in classical complexity theory. We then construct universal ABO programs, i.e., programs that are ABO no matter what real-time constraints are applied. Universal ABO programs can be used as building blocks for more complex systems. We conclude with a discussion of the prospects for bounded optimality as a theoretical basis for AI, and relate it to similar trends in philosophy, economics, and game theory.
人工知能は誕生以来、インテリジェント システムの望ましい特性として完全な合理性を中心とした理論的基礎に依存してきました。他の研究者と同様に、我々はこの基盤は根本的に満たされない要件を課すため不十分であると主張します。その結果、AIにおける理論と実践の間には大きな隔たりが生じ、この分野の進歩を阻害しています。そこで我々は、代わりに「有界最適性」と呼ばれる特性を提案します。大まかに言えば、エージェントのプログラムが、そのアーキテクチャとタスク環境によって提示される制約付き最適化問題の解である場合、そのエージェントは有界最適です。我々は、広範なリアルタイム環境において、単純なマシンアーキテクチャのクラスに対して、この特性を持つエージェントを構築する方法を示す。これらの結果を、自動郵便仕分け施設の単純なモデルを用いて説明します。また、より弱い特性である漸近有界最適性（ABO）を定義します。これは、古典的な複雑性理論における最適性の概念を一般化するものです。そして、どのようなリアルタイム制約が適用されてもABOとなるプログラム、すなわち普遍的なABOプログラムを構築します。普遍的なABOプログラムは、より複雑なシステムの構成要素として用いることができます。最後に、AIの理論的基礎としての制限付き最適性の見通しについて議論し、それを哲学、経済学、ゲーム理論の同様の傾向と関連付けます。
Pac-learning Recursive Logic Programs: Negative Results
Pac学習再帰論理プログラム：否定的な結果
In a companion paper it was shown that the class of constant-depth determinate k-ary recursive clauses is efficiently learnable. In this paper we present negative results showing that any natural generalization of this class is hard to learn in Valiant’s model of pac-learnability. In particular, we show that the following program classes are cryptographically hard to learn: programs with an unbounded number of constant-depth linear recursive clauses; programs with one constant-depth determinate clause containing an unbounded number of recursive calls; and programs with one linear recursive clause of constant locality. These results immediately imply the non-learnability of any more general class of programs. We also show that learning a constant-depth determinate program with either two linear recursive clauses or one linear recursive clause and one non-recursive clause is as hard as learning boolean DNF. Together with positive results from the companion paper, these negative results establish a boundary of efficient learnability for recursive function-free clauses.
関連論文では、定数深度確定k項再帰節のクラスが効率的に学習可能であることが示されています。本論文では、このクラスの自然な一般化はValiantのpac学習可能性モデルでは学習困難であることを示す否定的な結果を示します。特に、次のプログラム クラスは暗号的に学習困難であることを示します:無制限の数の定数深度線形再帰節を持つプログラム、無制限の数の再帰呼び出しを含む1つの定数深度確定節を持つプログラム、および定数局所性の1つの線形再帰節を持つプログラム。これらの結果は、より一般的なプログラム クラスが学習不可能であることを直ちに意味します。また、2つの線形再帰節、または1つの線形再帰節と1つの非再帰節を持つ定数深度確定プログラムの学習は、ブールDNFの学習と同じくらい困難であることを示します。関連論文の肯定的な結果と合わせて、これらの否定的な結果は、再帰関数のない節の効率的な学習可能性の境界を確立します。
Pac-Learning Recursive Logic Programs: Efficient Algorithms
Pac学習再帰論理プログラム：効率的なアルゴリズム
We present algorithms that learn certain classes of function-free recursive logic programs in polynomial time from equivalence queries. In particular, we show that a single k-ary recursive constant-depth determinate clause is learnable. Two-clause programs consisting of one learnable recursive clause and one constant-depth determinate non-recursive clause are also learnable, if an additional “basecase” oracle is assumed. These results immediately imply the pac-learnability of these classes. Although these classes of learnable recursive programs are very constrained, it is shown in a companion paper that they are maximally general, in that generalizing either class in any natural way leads to a computationally difficult learning problem. Thus, taken together with its companion paper, this paper establishes a boundary of efficient learnability for recursive logic programs.
同値性クエリから多項式時間で関数フリー再帰論理プログラムの特定のクラスを学習するアルゴリズムを紹介します。特に、単一のk項再帰定数深度確定節が学習可能であることを示します。1つの学習可能な再帰節と1つの定数深度確定非再帰節からなる2節プログラムも、追加の「ベースケース」オラクルを仮定すれば学習可能です。これらの結果は、これらのクラスのpac学習可能性を直ちに示唆します。これらの学習可能な再帰プログラムのクラスは非常に制約が多いものの、関連論文では、いずれかのクラスを自然な方法で一般化すると計算的に困難な学習問題につながるという点で、最大限に一般化されていることが示されています。したがって、関連論文と併せて、本論文は再帰論理プログラムの効率的な学習可能性の境界を確立します。
Adaptive Load Balancing: A Study in Multi-Agent Learning
適応型負荷分散：マルチエージェント学習の研究
We study the process of multi-agent reinforcement learning in the context ofload balancing in a distributed system, without use of either centralcoordination or explicit communication. We first define a precise frameworkin which to study adaptive load balancing, important features of which are itsstochastic nature and the purely local information available to individualagents. Given this framework, we show illuminating results on the interplaybetween basic adaptive behavior parameters and their effect on systemefficiency. We then investigate the properties of adaptive load balancing inheterogeneous populations, and address the issue of exploration vs.exploitation in that context. Finally, we show that naive use ofcommunication may not improve, and might even harm system efficiency.
我々は、中央調整や明示的な通信を一切用いない、分散システムにおける負荷分散の文脈におけるマルチエージェント強化学習のプロセスを研究します。まず、適応型負荷分散を研究するための正確な枠組みを定義します。その重要な特徴は、その確率的性質と個々のエージェントが利用できる純粋にローカルな情報です。この枠組みを用いて、基本的な適応行動パラメータとそれらがシステム効率に与える影響の相互作用について、明快な結果を示す。次に、異種集団における適応型負荷分散の特性を調査し、その文脈における探索と活用の問題に取り組む。最後に、通信の単純な使用はシステム効率を改善しない可能性があり、むしろ悪化させる可能性があることを示す。
Using Pivot Consistency to Decompose and Solve Functional CSPs
ピボット一貫性を用いた関数型CSPの分解と解決
Many studies have been carried out in order to increase thesearch efficiency of constraint satisfaction problems; among them,some make use of structural properties of the constraintnetwork; others take into account semantic properties of theconstraints, generally assuming that all the constraints possessthe given property. In this paper, we propose a new decompositionmethod benefiting from both semantic properties of functional constraints (not bijective constraints) and structuralproperties of the network; furthermore, not all the constraints needto be functional. We show that under some conditions, the existenceof solutions can be guaranteed. We first characterize a particularsubset of the variables, which we name a root set. We thenintroduce pivot consistency, a new local consistency which is aweak form of path consistency and can be achieved in O(n^2d^2)complexity (instead of O(n^3d^3) for path consistency), and wepresent associated properties; in particular, we show that anyconsistent instantiation of the root set can be linearly extended to a solution, which leads to the presentation of the aforementioned new method for solving by decomposing functional CSPs.
制約充足問題の探索効率を高めるために多くの研究が行われてきた。その中には、制約ネットワークの構造的特性を利用するものもあれば、制約の意味的特性を考慮し、一般的にすべての制約が所定の特性を持つと仮定するものがあります。本稿では、関数的制約（単射制約ではない）の意味的特性とネットワークの構造的特性の両方を活用した新しい分解法を提案します。さらに、すべての制約が関数的である必要はない。ある条件下では、解の存在が保証されることを示す。まず、ルート集合と呼ぶ変数の特定の部分集合を特徴付ける。次に、ピボット一貫性を導入します。これはパス一貫性の弱い形態であり、O(n^2d^2)の計算量（パス一貫性ではO(n^3d^3)である）で実現可能な新しい局所一貫性であり、関連する特性を示す。特に、根集合の任意の矛盾のないインスタンス化は線形的に解へと拡張できることを示し、これにより、前述の関数型CSPを分解することによって解を求める新しい手法を提示します。
Rerepresenting and Restructuring Domain Theories: A Constructive Induction Approach
ドメイン理論の再表現と再構築：構成的誘導アプローチ
Theory revision integrates inductive learning and background knowledge by combining training examples with a coarse domain theory to produce a more accurate theory. There are two challenges that theory revision and other theory-guided systems face. First, a representation language appropriate for the initial theory may be inappropriate for an improved theory. While the original representation may concisely express the initial theory, a more accurate theory forced to use that same representation may be bulky, cumbersome, and difficult to reach. Second, a theory structure suitable for a coarse domain theory may be insufficient for a fine-tuned theory. Systems that produce only small, local changes to a theory have limited value for accomplishing complex structural alterations that may be required. Consequently, advanced theory-guided learning systems require flexible representation and flexible structure. An analysis of various theory revision systems and theory-guided learning systems reveals specific strengths and weaknesses in terms of these two desired properties. Designed to capture the underlying qualities of each system, a new system uses theory-guided constructive induction. Experiments in three domains show improvement over previous theory-guided systems. This leads to a study of the behavior, limitations, and potential of theory-guided constructive induction.
理論修正は、訓練例と粗い領域理論を組み合わせることで、帰納学習と背景知識を統合し、より正確な理論を生成します。理論修正やその他の理論誘導システムが直面する課題は2つあります。第一に、初期理論に適した表現言語が、改良された理論には適さない場合があります。元の表現は初期理論を簡潔に表現できるかもしれませんが、同じ表現を強制的に用いるより正確な理論は、大きく扱いにくく、到達が困難になる可能性があります。第二に、粗い領域理論に適した理論構造が、微調整された理論には不十分な場合があります。理論に小さな局所的な変更しか加えないシステムは、必要となる可能性のある複雑な構造変更を実現する上での価値が限られています。したがって、高度な理論誘導学習システムには、柔軟な表現と柔軟な構造が必要です。様々な理論修正システムと理論誘導学習システムを分析することで、これら2つの望ましい特性に関して、具体的な長所と短所が明らかになります。各システムの根底にある特性を捉えるように設計された新しいシステムは、理論誘導による構成的帰納法を用いています。3つの領域における実験では、従来の理論誘導システムよりも改善が見られました。これは、理論に基づく構成的帰納法の挙動、限界、そして可能性を研究することにつながる。
Cost-Sensitive Classification: Empirical Evaluation of a Hybrid Genetic Decision Tree Induction Algorithm
コスト感度分類：ハイブリッド遺伝的決定木誘導アルゴリズムの実証的評価
This paper introduces ICET, a new algorithm for cost-sensitive classification. ICET uses a genetic algorithm to evolve a population of biases for a decision tree induction algorithm. The fitness function of the genetic algorithm is the average cost of classification when using the decision tree, including both the costs of tests (features, measurements) and the costs of classification errors. ICET is compared here with three other algorithms for cost-sensitive classification – EG2, CS-ID3, and IDX – and also with C4.5, which classifies without regard to cost. The five algorithms are evaluated empirically on five real-world medical datasets. Three sets of experiments are performed. The first set examines the baseline performance of the five algorithms on the five datasets and establishes that ICET performs significantly better than its competitors. The second set tests the robustness of ICET under a variety of conditions and shows that ICET maintains its advantage. The third set looks at ICET’s search in bias space and discovers a way to improve the search.
本論文では、コストに配慮した分類のための新しいアルゴリズムICETを紹介します。ICETは、遺伝的アルゴリズムを用いて、決定木誘導アルゴリズムのためのバイアス集団を進化させます。遺伝的アルゴリズムの適応度関数は、決定木を用いた場合の分類の平均コストであり、テスト（特徴、測定値）のコストと分類エラーのコストの両方を含みます。本論文では、ICETを、コストに配慮した分類のための他の3つのアルゴリズム（EG2、CS-ID3、IDX）と、コストを考慮せずに分類を行うC4.5と比較します。5つのアルゴリズムは、5つの実際の医療データセットを用いて経験的に評価されます。3つの実験セットが実行されます。最初のセットでは、5つのデータセットにおける5つのアルゴリズムのベースラインパフォーマンスを検証し、ICETが競合製品よりも大幅に優れたパフォーマンスを発揮することを確認します。2番目のセットでは、様々な条件下でのICETの堅牢性をテストし、ICETがその優位性を維持することを示します。3番目のセットでは、バイアス空間でのICETの検索を調べ、検索を改善する方法を見つけます。
On the Informativeness of the DNA Promoter Sequences Domain Theory
DNAプロモーター配列ドメイン理論の情報性について
The DNA promoter sequences domain theory and database havebecome popular for testing systems that integrate empirical andanalytical learning. This note reports a simple change andreinterpretation of the domain theory in terms of M-of-N concepts,involving no learning, that results in an accuracy of 93.4% on the 106items of the database. Moreover, an exhaustive search of the space ofM-of-N domain theory interpretations indicates that the expectedaccuracy of a randomly chosen interpretation is 76.5%, and that amaximum accuracy of 97.2% is achieved in 12 cases. This demonstratesthe informativeness of the domain theory, without the complications ofunderstanding the interactions between various learning algorithms andthe theory. In addition, our results help characterize the difficultyof learning using the DNA promoters theory.
DNAプロモーター配列ドメイン理論とデータベースは、経験的学習と分析的学習を統合したシステムのテストに広く利用されています。本稿では、学習を伴わないM-of-N概念に基づくドメイン理論の単純な変更と再解釈により、データベースの106項目に対して93.4%の精度が得られることを報告します。さらに、M-of-Nドメイン理論の解釈空間を網羅的に探索した結果、ランダムに選択された解釈の期待精度は76.5%であり、最大精度97.2%は12のケースで達成されました。これは、様々な学習アルゴリズムと理論の相互作用を理解するという複雑さを伴わずに、ドメイン理論の情報価値を示すものです。さらに、我々の研究結果は、DNAプロモーター理論を用いた学習の難しさを特徴付けるのにも役立ちます。
Random Worlds and Maximum Entropy
ランダムワールドと最大エントロピー
Given a knowledge base KB containing first-order and statistical facts, we consider a principled method, called the random-worlds method, for computing a degree of belief that some formula Phi holds given KB. If we are reasoning about a world or system consisting of N individuals, then we can consider all possible worlds, or first-order models, withdomain {1,…,N} that satisfy KB, and compute thefraction of them in which Phi is true. We define the degree of belief to be the asymptotic value of this fraction as N grows large. We show that when the vocabulary underlying Phi andKB uses constants and unary predicates only, we can naturally associate an entropy with each world. As N grows larger,there are many more worlds with higher entropy. Therefore, we can usea maximum-entropy computation to compute the degree of belief. This result is in a similar spirit to previous work in physics and artificial intelligence, but is far more general. Of equal interest to the result itself are the limitations on its scope. Most importantly, the restriction to unary predicates seems necessary. Although the random-worlds method makes sense in general, the connection to maximum entropy seems to disappear in the non-unary case. These observations suggest unexpected limitations to the applicability of maximum-entropy methods.
一次事実と統計事実を含む知識ベースKBが与えられた場合、ある式PhiがKBを与えられたときに成立するという確信度を計算するための、ランダムワールド法と呼ばれる原理的な手法について考察します。N個の個体からなる世界またはシステムについて推論する場合、KBを満たすドメイン{1,…,N}を持つすべての可能世界、つまり一次モデルを考慮し、それらの中でPhiが真となる割合を計算することができます。確信度は、Nが大きくなるにつれてこの割合が漸近的に変化する値と定義します。PhiとKBの基盤となる語彙が定数と単項述語のみを使用する場合、各世界にエントロピーを自然に関連付けることができることを示す。Nが大きくなるにつれて、より高いエントロピーを持つ世界がさらに多く存在します。したがって、最大エントロピー計算を用いて確信度を計算できます。この結果は、物理学や人工知能におけるこれまでの研究と似た考え方に基づいているが、はるかに汎用性が高い。結果自体と同様に興味深いのは、その適用範囲の制限です。最も重要なのは、単項述語への制限が必要であるように思われることです。ランダムワールド法は一般的に理にかなっていますが、単項述語以外の場合には最大エントロピーとの関連性が失われるようです。これらの観察結果は、最大エントロピー法の適用性に予期せぬ限界があることを示唆しています。
A Domain-Independent Algorithm for Plan Adaptation
計画適応のためのドメイン非依存アルゴリズム
The paradigms of transformational planning, case-based planning, and plan debugging all involve a process known as plan adaptation – modifying or repairing an old plan so it solves a new problem. In this paper we provide a domain-independent algorithm for plan adaptation, demonstrate that it is sound, complete, and systematic, and compare it to other adaptation algorithms in the literature. Our approach is based on a view of planning as searching a graph of partial plans. Generative planning starts at the graph’s root and moves from node to node using plan-refinement operators. In planning by adaptation, a library plan – an arbitrary node in the plan graph – is the starting point for the search, and the plan-adaptation algorithm can apply both the same refinement operators available to a generative planner and can also retract constraints and steps from the plan. Our algorithm’s completeness ensures that the adaptation algorithm will eventually search the entire graph and its systematicity ensures that it will do so without redundantly searching any parts of the graph.
変換型プランニング、事例ベースプランニング、プランデバッグといったパラダイムはいずれも、プラン適応と呼ばれるプロセス、すなわち古いプランを修正または修復して新しい問題を解決するためのプロセスを伴う。本稿では、ドメインに依存しないプラン適応アルゴリズムを提示し、それが健全で完全かつ体系的であることを実証するとともに、文献で紹介されている他の適応アルゴリズムと比較します。本アプローチは、プランニングを部分プランのグラフを探索するものとして捉える考え方に基づいています。生成型プランニングはグラフのルートから開始し、プラン改良演算子を用いてノードからノードへと移動します。適応型プランニングでは、ライブラリプラン（プラングラフ内の任意のノード）が探索の開始点となり、プラン適応アルゴリズムは生成型プランナーで利用可能なものと同じ改良演算子を適用できるだけでなく、プランから制約やステップを削除することもできます。本アルゴリズムの完全性により、適応アルゴリズムは最終的にグラフ全体を探索することが保証され、体系性により、グラフのどの部分も冗長に探索することなく探索できることが保証されます。
Truncating Temporal Differences: On the Efficient Implementation of TD(lambda) for Reinforcement Learning
時間差の切り捨て：強化学習におけるTD(λ)の効率的な実装について
Temporal difference (TD) methods constitute a class of methods for learning predictions in multi-step prediction problems, parameterized by a recency factor lambda. Currently the most important application of these methods is to temporal credit assignment in reinforcement learning. Well known reinforcement learning algorithms, such as AHC or Q-learning, may be viewed as instances of TD learning. This paper examines the issues of the efficient and general implementation of TD(lambda) for arbitrary lambda, for use with reinforcement learning algorithms optimizing the discounted sum of rewards. The traditional approach, based on eligibility traces, is argued to suffer from both inefficiency and lack of generality. The TTD (Truncated Temporal Differences) procedure is proposed as an alternative, that indeed only approximates TD(lambda), but requires very little computation per action and can be used with arbitrary function representation methods. The idea from which it is derived is fairly simple and not new, but probably unexplored so far. Encouraging experimental results are presented, suggesting that using lambda > 0 with the TTD procedure allows one to obtain a significant learning speedup at essentially the same cost as usual TD(0) learning.
時間差分（TD）法は、近時性係数λによってパラメータ化された、多段階予測問題における予測学習手法の一種です。現在、これらの手法の最も重要な応用は、強化学習における時間的クレジット割り当てです。AHCやQ学習などのよく知られた強化学習アルゴリズムは、TD学習の例として考えることができます。本稿では、割引報酬総額を最適化する強化学習アルゴリズムで使用するための、任意のλに対するTD(λ)の効率的かつ汎用的な実装の問題について検討します。適格性トレースに基づく従来のアプローチは、非効率性と汎用性の欠如の両方に問題があるとされています。代替案として提案されているTTD（Truncated Temporal Differences）手順は、確かにTD(λ)を近似するだけであるが、アクションあたりの計算量は非常に少なく、任意の関数表現方法で使用できます。その導出元となるアイデアはかなり単純で目新しいものではないが、おそらくこれまで未開拓です。TTD手順でλ> 0を使用すると、通常のTD(0)学習と実質的に同じコストで学習を大幅に高速化できることを示唆する、有望な実験結果が提示されています。
Solving Multiclass Learning Problems via Error-Correcting Output Codes
誤り訂正出力コードを用いた多クラス学習問題の解法
Multiclass learning problems involve finding a definitionfor an unknown function f(x) whose range is a discrete setcontaining k > 2 values (i.e., k “classes”). Thedefinition is acquired by studying collections of training examples ofthe form [x_i, f (x_i)]. Existing approaches tomulticlass learning problems include direct application of multiclassalgorithms such as the decision-tree algorithms C4.5 and CART,application of binary concept learning algorithms to learn individualbinary functions for each of the k classes, and application ofbinary concept learning algorithms with distributed outputrepresentations. This paper compares these three approaches to a newtechnique in which error-correcting codes are employed as adistributed output representation. We show that these outputrepresentations improve the generalization performance of both C4.5and backpropagation on a wide range of multiclass learning tasks. Wealso demonstrate that this approach is robust with respect to changesin the size of the training sample, the assignment of distributedrepresentations to particular classes, and the application ofoverfitting avoidance techniques such as decision-tree pruning.Finally, we show that—like the other methods—the error-correctingcode technique can provide reliable class probability estimates.Taken together, these results demonstrate that error-correcting outputcodes provide a general-purpose method for improving the performanceof inductive learning programs on multiclass problems.
多クラス学習問題は、k > 2個の値（つまり、k個の「クラス」）を含む離散集合を値域とする未知の関数f(x)の定義を求める問題です。この定義は、[x_i, f (x_i)]という形式の訓練例の集合を学習することによって得られます。多クラス学習問題に対する既存のアプローチには、決定木アルゴリズムC4.5やCARTなどの多クラスアルゴリズムを直接適用する方法、k個のクラスそれぞれについて個別のバイナリ関数を学習するバイナリコンセプト学習アルゴリズムを適用する方法、分散出力表現を用いたバイナリコンセプト学習アルゴリズムを適用する方法などがあります。本論文では、これら3つのアプローチと、分散出力表現として誤り訂正符号を用いる新しい手法を比較します。これらの出力表現は、C4.5とバックプロパゲーションの両方において、幅広い多クラス学習タスクにおける汎化性能を向上させることを示します。また、このアプローチは、トレーニングサンプルのサイズ、特定のクラスへの分散表現の割り当て、決定木プルーニングなどの過剰適合回避手法の適用などの変化に対して堅牢であることを示します。最後に、他の手法と同様に、誤り訂正符号手法によって信頼性の高いクラス確率推定値が得られることを示します。これらの結果を総合すると、誤り訂正出力符号は、多クラス問題における帰納学習プログラムのパフォーマンスを向上させる汎用的な手法となることが示されます。
Total-Order and Partial-Order Planning: A Comparative Analysis
全順序プランニングと半順序プランニング：比較分析
For many years, the intuitions underlying partial-order planning were largely taken for granted. Only in the past few years has there been renewed interest in the fundamental principles underlying this paradigm. In this paper, we present a rigorous comparative analysis of partial-order and total-order planning by focusing on two specific planners that can be directly compared. We show that there are some subtle assumptions that underly the wide-spread intuitions regarding the supposed efficiency of partial-order planning. For instance, the superiority ofpartial-order planning can depend critically upon the search strategy and the structure of the search space. Understanding the underlying assumptions is crucial for constructing efficient planners.
長年にわたり、半順序計画の根底にある直感は、ほぼ当然のことと考えられてきました。このパラダイムの根底にある基本原理への関心が再び高まったのは、ここ数年のことです。本稿では、直接比較可能な2つのプランナーに焦点を当て、半順序計画と全順序計画の厳密な比較分析を行います。半順序計画の効率性に関する広く信じられている直感の根底には、いくつかの微妙な仮定が存在することを示します。例えば、半順序計画の優位性は、探索戦略と探索空間の構造に大きく依存する可能性があります。これらの仮定を理解することは、効率的なプランナーを構築する上で不可欠です。
Operations for Learning with Graphical Models
グラフィカルモデルを用いた学習のための操作
This paper is a multidisciplinary review of empirical, statistical learning from a graphical model perspective. Well-known examples of graphical models include Bayesian networks, directed graphs representing a Markov chain, and undirected networks representing a Markov field. These graphical models are extended to model data analysis and empirical learning using the notation of plates. Graphical operations for simplifying and manipulating a problem are provided including decomposition, differentiation, andthe manipulation of probability models from the exponential family. Two standard algorithm schemas for learning are reviewed in a graphical framework: Gibbs sampling and the expectation maximizationalgorithm. Using these operations and schemas, some popular algorithms can be synthesized from their graphical specification. This includes versions of linear regression, techniques for feed-forward networks, and learning Gaussian and discrete Bayesian networks from data. The paper concludes by sketching some implications for data analysis and summarizing how some popular algorithms fall within the framework presented. The main original contributions here are the decompositiontechniques and the demonstration that graphical models provide a framework for understanding and developing complex learning algorithms.
本論文は、グラフィカルモデルの観点から、経験的統計学習を多角的にレビューしたものです。グラフィカルモデルのよく知られた例としては、ベイジアンネットワーク、マルコフ連鎖を表す有向グラフ、マルコフ場を表す無向ネットワークなどが挙げられます。これらのグラフィカルモデルは、プレート表記法を用いたデータ分析と経験的学習のモデル化に拡張されています。分解、微分化、指数族からの確率モデルの操作など、問題を簡素化および操作するためのグラフィカル操作が提供されています。学習のための2つの標準的なアルゴリズムスキーム、ギブスサンプリングと期待値最大化アルゴリズムについて、グラフィカルフレームワークでレビューします。これらの操作とスキーマを用いることで、いくつかの一般的なアルゴリズムをグラフィカルな仕様から合成することができます。これには、線形回帰のさまざまなバージョン、フィードフォワードネットワークの手法、そしてデータからのガウスネットワークと離散ベイジアンネットワークの学習が含まれます。本論文は、データ分析へのいくつかの示唆を概説し、いくつかの一般的なアルゴリズムが提示された枠組みにどのように当てはまるかをまとめることで結論づけています。本論文における主な独創的な貢献は、分解手法と、グラフィカルモデルが複雑な学習アルゴリズムを理解し開発するための枠組みを提供するという実証です。
Wrap-Up: a Trainable Discourse Module for Information Extraction
まとめ：情報抽出のための学習可能な談話モジュール
The vast amounts of on-line text now available have ledto renewed interest in information extraction (IE) systems thatanalyze unrestricted text, producing a structured representation ofselected information from the text. This paper presents a novel approachthat uses machine learning to acquire knowledge for some of the higher level IE processing. Wrap-Up is a trainable IE discourse component that makes intersentential inferences and identifies logicalrelations among information extracted from the text. Previous corpus-based approaches were limited to lower level processing such as part-of-speech tagging, lexical disambiguation, and dictionary construction. Wrap-Up is fully trainable, and not onlyautomatically decides what classifiers are needed, but even derives the featureset for each classifier automatically. Performance equals that of a partially trainable discourse module requiring manual customization for each domain.
現在利用可能な膨大なオンラインテキストにより、制約のないテキストを分析し、テキストから選択された情報の構造化表現を生成する情報抽出（IE）システムへの関心が再び高まっています。本論文では、機械学習を用いて高レベルIE処理の一部に関する知識を獲得する新しいアプローチを紹介します。Wrap-Upは、文間推論を行い、テキストから抽出された情報間の論理的関係を識別する、学習可能なIE談話コンポーネントです。従来のコーパスベースのアプローチは、品詞タグ付け、語彙の曖昧性解消、辞書構築といった低レベルの処理に限られていました。Wrap-Upは完全に学習可能であり、必要な分類器を自動的に決定するだけでなく、各分類器の特徴セットも自動的に導出します。そのパフォーマンスは、各ドメインごとに手動でカスタマイズする必要がある、部分的に学習可能な談話モジュールと同等です。
On Planning while Learning
学習中のプランニングについて
This paper introduces a framework for Planning while Learning where an agent is given a goal to achieve in anenvironment whose behavior is only partially known to the agent. We discuss the tractability of various plan-design processes. We show that for a large natural class of Planning while Learning systems, a plan can be presented and verified in a reasonable time. However, coming up algorithmically with a plan, even for simple classes of systems is apparently intractable. We emphasize the role of off-line plan-design processes, andshow that, in most natural cases, the verification (projection) part canbe carried out in an efficient algorithmic manner.
本論文では、エージェントが環境の挙動を部分的にしか把握していない状況において、達成すべき目標を与えられる「学習しながらプランニングする」ためのフレームワークを紹介します。様々なプラン設計プロセスの扱いやすさについて議論します。「学習しながらプランニングする」システムの大規模な自然クラスにおいては、プランを提示し、妥当な時間で検証できることを示す。しかしながら、単純なシステムクラスであっても、アルゴリズム的にプランを立案することは明らかに困難です。本論文では、オフラインのプラン設計プロセスの役割を強調し、ほとんどの自然なケースにおいて、検証（投影）部分を効率的なアルゴリズムで実行できることを示す。
A System for Induction of Oblique Decision Trees
斜交決定木誘導システム
This article describes a new system for induction ofoblique decision trees. This system, OC1, combines deterministic hill-climbing with two forms of randomization to find a goodoblique split (in the form of a hyperplane) at each node of a decisiontree. Oblique decision tree methods are tuned especially for domains in which the attributes are numeric, although they can be adapted to symbolic or mixed symbolic/numeric attributes. We presentextensive empirical studies, using both real and artificial data, thatanalyze OC1’s ability to construct oblique trees that are smaller and more accurate than their axis-parallel counterparts. We also examinethe benefits of randomization for the construction of oblique decisiontrees.
本論文では、斜交決定木を帰納的に生成するための新しいシステムについて説明します。このシステムOC1は、決定論的な山登り法と2種類のランダム化手法を組み合わせることで、決定木の各ノードにおいて適切な斜交分岐（超平面形式）を求める。斜交決定木法は、特に属性が数値である領域向けに最適化されているが、記号属性や記号/数値混合属性にも適応可能です。本論文では、実データと人工データの両方を用いた広範な実証研究を行い、軸平行型よりも小型で高精度な斜交決定木を構築するOC1の能力を分析します。また、斜交決定木の構築におけるランダム化の利点についても検証します。