Quantum Computing and Phase Transitions in Combinatorial Search
組合せ探索における量子コンピューティングと相転移
We introduce an algorithm for combinatorial search on quantum computers that is capable of significantly concentrating amplitude into solutions for some NP search problems, on average. This is done by exploiting the same aspects of problem structure as used by classical backtrack methods to avoid unproductive search choices. This quantum algorithm is much more likely to find solutions than the simple direct use of quantum parallelism. Furthermore, empirical evaluation on small problems shows this quantum algorithm displays the same phase transition behavior, and at the same location, as seen in many previously studied classical search methods. Specifically, difficult problem instances are concentrated near the abrupt change from underconstrained to overconstrained problems.
我々は、量子コンピュータ上での組合せ探索アルゴリズムを導入します。このアルゴリズムは、平均して一部のNP探索問題において、振幅を解に著しく集中させることができます。これは、従来のバックトラック法で非生産的な探索選択を回避するために用いられるのと同じ問題構造の側面を利用することで実現されます。この量子アルゴリズムは、量子並列性を単純に直接用いる場合よりも、解を発見する可能性がはるかに高い。さらに、小規模な問題における実証的評価は、この量子アルゴリズムが、これまで研究されてきた多くの従来の探索法で見られるのと同じ相転移挙動を、同じ場所で示すことを示しています。具体的には、困難な問題インスタンスは、制約不足の問題から制約過剰の問題への急激な変化点付近に集中しています。
Improved Use of Continuous Attributes in C4.5
C4.5における連続属性の改良された利用法
A reported weakness of C4.5 in domains with continuous attributes is addressed by modifying the formation and evaluation of tests on continuous attributes. An MDL-inspired penalty is applied to such tests, eliminating some of them from consideration and altering the relative desirability of all tests. Empirical trials show that the modifications lead to smaller decision trees with higher predictive accuracies. Results also confirm that a new version of C4.5 incorporating these changes is superior to recent approaches that use global discretization and that construct small trees with multi-interval splits.
連続属性を持つ領域におけるC4.5の弱点として報告されているものは、連続属性に対するテストの構成と評価方法を変更することで対処します。MDLに着想を得たペナルティをこのようなテストに適用することで、一部のテストを考慮対象から除外し、すべてのテストの相対的な望ましさを変化させる。実験的検証の結果、これらの変更により、より小型の決定木が生成され、予測精度が向上することが示されました。また、これらの変更を組み込んだC4.5の新バージョンは、グローバル離散化を用い、複数区間に分割した小型の決定木を構築する最近の手法よりも優れていることも確認されました。
Mean Field Theory for Sigmoid Belief Networks
シグモイドビリーフネットワークのための平均場理論
We develop a mean field theory for sigmoid belief networks based on ideas from statistical mechanics. Our mean field theory provides a tractable approximation to the true probability distribution in these networks; it also yields a lower bound on the likelihood of evidence. We demonstrate the utility of this framework on a benchmark problem in statistical pattern recognition—the classification of handwritten digits.
統計力学の考え方に基づき、シグモイドビリーフネットワークの平均場理論を構築します。この平均場理論は、これらのネットワークにおける真の確率分布の扱いやすい近似値を提供します。また、証拠尤度の下限値も与える。この枠組みの有用性を、統計的パターン認識におけるベンチマーク問題（手書き数字の分類）を用いて実証します。
On Partially Controlled Multi-Agent Systems
部分制御マルチエージェントシステムについて
Motivated by the control theoretic distinction between controllable and uncontrollable events, we distinguish between two types of agents within a multi-agent system: controllable agents, which are directly controlled by the system’s designer, and uncontrollable agents, which are not under the designer’s direct control. We refer to such systems as partially controlled multi-agent systems, and we investigate how one might influence the behavior of the uncontrolled agents through appropriate design of the controlled agents. In particular, we wish to understand which problems are naturally described in these terms, what methods can be applied to influence the uncontrollable agents, the effectiveness of such methods, and whether similar methods work across different domains. Using a game-theoretic framework, this paper studies the design of partially controlled multi-agent systems in two contexts: in one context, the uncontrollable agents are expected utility maximizers, while in the other they are reinforcement learners. We suggest different techniques for controlling agents’ behavior in each domain, assess their success, and examine their relationship.
制御理論における制御可能な事象と制御不可能な事象の区別に基づき、マルチエージェントシステム内の2種類のエージェントを区別します。制御可能なエージェントはシステムの設計者によって直接制御され、制御不可能なエージェントは設計者の直接的な制御下にない。このようなシステムを部分制御マルチエージェントシステムと呼び、制御対象エージェントの適切な設計によって、制御不可能なエージェントの行動にどのような影響を与えることができるかを検証します。特に、どのような問題がこれらの用語で自然に記述されるか、制御不可能なエージェントに影響を与えるためにどのような手法を適用できるか、そのような手法の有効性、そして同様の手法が異なる領域で有効かどうかを理解します。本論文では、ゲーム理論的枠組みを用いて、部分制御マルチエージェントシステムの設計を2つの文脈で考察します。1つの文脈では、制御不可能なエージェントは期待効用最大化者であり、もう1つの文脈では強化学習者です。各領域においてエージェントの行動を制御するための異なる手法を提案し、その有効性を評価し、それらの関係性を検証します。
A Formal Framework for Speedup Learning from Problems and Solutions
問題と解からの高速学習のための形式的枠組み
Speedup learning seeks to improve the computational efficiency of problem solving with experience. In this paper, we develop a formal framework for learning efficient problem solving from random problems and their solutions. We apply this framework to two different representations of learned knowledge, namely control rules and macro-operators, and prove theorems that identify sufficient conditions for learning in each representation. Our proofs are constructive in that they are accompanied with learning algorithms. Our framework captures both empirical and explanation-based speedup learning in a unified fashion. We illustrate our framework with implementations in two domains: symbolic integration and Eight Puzzle. This work integrates many strands of experimental and theoretical work in machine learning, including empirical learning of control rules, macro-operator learning, Explanation-Based Learning (EBL), and Probably Approximately Correct (PAC) Learning.
高速化学習は、経験に基づく問題解決の計算効率を向上させることを目指しています。本稿では、ランダムな問題とその解から効率的な問題解決を学習するための形式的なフレームワークを開発します。このフレームワークを、学習済み知識の2つの異なる表現、すなわち制御規則とマクロ演算子に適用し、それぞれの表現における学習の十分条件を特定する定理を証明します。私たちの証明は、学習アルゴリズムを伴うという点で構成的です。私たちのフレームワークは、経験に基づく高速化学習と説明に基づく高速化学習の両方を統一的に捉えます。私たちは、記号積分とエイトパズルという2つの領域における実装を用いて、このフレームワークを説明します。この研究は、制御ルールの経験的学習、マクロ演算子学習、説明ベースの学習(EBL)、およびおそらく近似的に正しい(PAC)学習など、機械学習における実験的および理論的研究の多くの流れを統合しています。
A Principled Approach Towards Symbolic Geometric Constraint Satisfaction
記号幾何学的制約充足への原理的アプローチ
An important problem in geometric reasoning is to find the configuration of a collection of geometric bodies so as to satisfy a set of given constraints. Recently, it has been suggested that this problem can be solved efficiently by symbolically reasoning about geometry. This approach, called degrees of freedom analysis, employs a set of specialized routines called plan fragments that specify how to change the configuration of a set of bodies to satisfy a new constraint while preserving existing constraints. A potential drawback, which limits the scalability of this approach, is concerned with the difficulty of writing plan fragments. In this paper we address this limitation by showing how these plan fragments can be automatically synthesized using first principles about geometric bodies, actions, and topology.
幾何学的推論における重要な問題は、一連の与えられた制約を満たすように幾何学的物体の集合の構成を見つけることです。最近、この問題は幾何学について記号的に推論することによって効率的に解決できることが示唆されています。自由度解析と呼ばれるこのアプローチは、プランフラグメントと呼ばれる一連の特殊なルーチンを用いて、既存の制約を維持しながら新しい制約を満たすために、一連の物体の構成をどのように変更するかを指定します。このアプローチのスケーラビリティを制限する潜在的な欠点は、プランフラグメントの作成の難しさです。本稿では、幾何学的物体、アクション、および位相に関する第一原理を用いて、これらのプランフラグメントを自動的に合成する方法を示すことで、この限界に対処します。
Further Experimental Evidence against the Utility of Occam’s Razor
オッカムの剃刀の有用性に対するさらなる実験的証拠
This paper presents new experimental evidence against the utility of Occam’s razor. A~systematic procedure is presented for post-processing decision trees produced by C4.5. This procedure was derived by rejecting Occam’s razor and instead attending to the assumption that similar objects are likely to belong to the same class. It increases a decision tree’s complexity without altering the performance of that tree on the training data from which it is inferred. The resulting more complex decision trees are demonstrated to have, on average, for a variety of common learning tasks, higher predictive accuracy than the less complex original decision trees. This result raises considerable doubt about the utility of Occam’s razor as it is commonly applied in modern machine learning.
本論文では、オッカムの剃刀の有用性に反する新たな実験的証拠を提示します。C4.5によって生成された決定木を後処理するための体系的な手順を提示します。この手順は、オッカムの剃刀を否定し、代わりに類似のオブジェクトは同じクラスに属する可能性が高いという仮定に注意を払うことによって導き出されました。この手順は、推論の元となったトレーニング データに対する決定木のパフォーマンスを変更することなく、決定木の複雑さを増加させる。結果として得られるより複雑な決定木は、さまざまな一般的な学習タスクに対して、平均して、複雑さの少ない元の決定木よりも高い予測精度を持つことが実証されています。この結果は、現代の機械学習で一般的に適用されているオッカムの剃刀の有用性についてかなりの疑問を投げかける。
Logarithmic-Time Updates and Queries in Probabilistic Networks
確率ネットワークにおける対数時間更新とクエリ
Traditional databases commonly support efficient query and update procedures that operate in time which is sublinear in the size of the database. Our goal in this paper is to take a first step toward dynamic reasoning in probabilistic databases with comparable efficiency. We propose a dynamic data structure that supports efficient algorithms for updating and querying singly connected Bayesian networks. In the conventional algorithm, new evidence is absorbed in O(1) time and queries are processed in time O(N), where N is the size of the network. We propose an algorithm which, after a preprocessing phase, allows us to answer queries in time O(log N) at the expense of O(log N) time per evidence absorption. The usefulness of sub-linear processing time manifests itself in applications requiring (near) real-time response over large probabilistic databases. We briefly discuss a potential application of dynamic probabilistic reasoning in computational biology.
従来のデータベースは一般的に、データベースのサイズに対して線形以下の時間で動作する効率的なクエリおよび更新手順をサポートしています。本稿の目標は、同等の効率性を持つ確率データベースにおける動的推論への第一歩を踏み出すことです。我々は、単連結ベイジアンネットワークの更新とクエリのための効率的なアルゴリズムをサポートする動的データ構造を提案します。従来のアルゴリズムでは、新しい証拠の吸収はO(1)時間で行われ、クエリの処理はO(N)時間で行われます。ここでNはネットワークのサイズです。我々は、前処理段階の後、証拠の吸収ごとにO(log N)の時間を犠牲にして、クエリにO(log N)時間で回答できるアルゴリズムを提案します。線形以下の処理時間の有用性は、大規模な確率データベースに対して（ほぼ）リアルタイムの応答を必要とするアプリケーションにおいて顕著に現れます。本稿では、計算生物学における動的確率推論の潜在的な応用について簡単に議論します。
Adaptive Problem-solving for Large-scale Scheduling Problems: A Case Study
大規模スケジューリング問題に対する適応的問題解決：ケーススタディ
Although most scheduling problems are NP-hard, domain specific techniques perform well in practice but are quite expensive to construct. In adaptive problem-solving solving, domain specific knowledge is acquired automatically for a general problem solver with a flexible control architecture. In this approach, a learning system explores a space of possible heuristic methods for one well-suited to the eccentricities of the given domain and problem distribution. In this article, we discuss an application of the approach to scheduling satellite communications. Using problem distributions based on actual mission requirements, our approach identifies strategies that not only decrease the amount of CPU time required to produce schedules, but also increase the percentage of problems that are solvable within computational resource limitations.
ほとんどのスケジューリング問題はNP困難であるが、ドメイン固有の手法は実際には良好なパフォーマンスを示すものの、構築コストが非常に高い。適応型問題解決では、柔軟な制御アーキテクチャを備えた汎用的な問題解決器のために、ドメイン固有の知識が自動的に獲得されます。このアプローチでは、学習システムは、与えられたドメインと問題分布の偏心に適したヒューリスティック手法の可能な空間を探索します。本稿では、このアプローチの衛星通信スケジューリングへの応用について議論します。実際のミッション要件に基づく問題分布を用いて、本アプローチは、スケジュール作成に必要なCPU時間を削減するだけでなく、計算資源の制限内で解決可能な問題の割合を高める戦略を特定します。
Least Generalizations and Greatest Specializations of Sets of Clauses
節集合の最小一般化と最大特化
The main operations in Inductive Logic Programming (ILP) are generalization and specialization, which only make sense in a generality order. In ILP, the three most important generality orders are subsumption, implication and implication relative to background knowledge. The two languages used most often are languages of clauses and languages of only Horn clauses. This gives a total of six different ordered languages. In this paper, we give a systematic treatment of the existence or non-existence of least generalizations and greatest specializations of finite sets of clauses in each of these six ordered sets. We survey results already obtained by others and also contribute some answers of our own. Our main new results are, firstly, the existence of a computable least generalization under implication of every finite set of clauses containing at least one non-tautologous function-free clause (among other, not necessarily function-free clauses). Secondly, we show that such a least generalization need not exist under relative implication, not even if both the set that is to be generalized and the background knowledge are function-free. Thirdly, we give a complete discussion of existence and non-existence of greatest specializations in each of the six ordered languages.
帰納論理プログラミング（ILP）における主要な演算は、一般化と特殊化であり、これらは一般性順序においてのみ意味を持ちます。ILPにおいて最も重要な3つの一般性順序は、包摂、含意、そして背景知識に対する相対的含意です。最も頻繁に使用される2つの言語は、節の言語とホーン節のみの言語です。これにより、合計6つの異なる順序付き言語が存在します。本論文では、これら6つの順序付き集合のそれぞれにおける、節の有限集合の最小一般化と最大特殊化の存在または非存在について体系的に扱います。我々は既に他者によって得られた結果を概観し、また我々独自の解答もいくつか提示します。我々の主な新しい結果は、第一に、少なくとも1つの非トートローガスな関数自由節（必ずしも関数自由である必要はない節も含む）を含むすべての節の有限集合の含意の下で計算可能な最小一般化が存在することです。第二に、そのような最小一般化は、一般化される集合と背景知識の両方が関数自由であっても、相対的含意の下では必ずしも存在しないことを示します。第三に、6つの順序付き言語それぞれにおける最大特化の存在と非存在について徹底的に議論します。
Planning for Contingencies: A Decision-based Approach
偶発事象の計画：意思決定に基づくアプローチ
A fundamental assumption made by classical AI planners is that there is no uncertainty in the world: the planner has full knowledge of the conditions under which the plan will be executed and the outcome of every action is fully predictable. These planners cannot therefore construct contingency plans, i.e., plans in which different actions are performed in different circumstances. In this paper we discuss some issues that arise in the representation and construction of contingency plans and describe Cassandra, a partial-order contingency planner. Cassandra uses explicit decision-steps that enable the agent executing the plan to decide which plan branch to follow. The decision-steps in a plan result in subgoals to acquire knowledge, which are planned for in the same way as any other subgoals. Cassandra thus distinguishes the process of gathering information from the process of making decisions. The explicit representation of decisions in Cassandra allows a coherent approach to the problems of contingent planning, and provides a solid base for extensions such as the use of different decision-making procedures.
古典的なAIプランナーが前提とする基本的な仮定は、世界には不確実性は存在しないというものです。つまり、プランナーは計画が実行される条件を完全に把握しており、あらゆる行動の結果は完全に予測可能です。したがって、これらのプランナーはコンティンジェンシープラン、すなわち、異なる状況で異なる行動が実行されるプランを構築することができません。本稿では、コンティンジェンシープランの表現と構築において生じるいくつかの問題について議論し、半順序コンティンジェンシープランナーであるCassandraについて説明します。Cassandraは、プランを実行するエージェントがどのプラン分岐に従うかを決定できるようにする明示的な意思決定ステップを使用します。プラン内の意思決定ステップは、知識を獲得するためのサブゴールを生み出し、それらは他のサブゴールと同様に計画されます。このように、Cassandraは情報収集プロセスと意思決定プロセスを区別します。Cassandraにおける意思決定の明示的な表現は、コンティンジェンシープランニングの問題に対する一貫したアプローチを可能にし、異なる意思決定手順の使用などの拡張のための強固な基盤を提供します。
Reinforcement Learning: A Survey
強化学習：概観
This paper surveys the field of reinforcement learning from a computer-science perspective. It is written to be accessible to researchers familiar with machine learning. Both the historical basis of the field and a broad selection of current work are summarized. Reinforcement learning is the problem faced by an agent that learns behavior through trial-and-error interactions with a dynamic environment. The work described here has a resemblance to work in psychology, but differs considerably in the details and in the use of the word “reinforcement.” The paper discusses central issues of reinforcement learning, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state. It concludes with a survey of some implemented systems and an assessment of the practical utility of current methods for reinforcement learning.
本論文は、コンピュータサイエンスの観点から強化学習分野を概観します。機械学習に精通した研究者にとって分かりやすいように執筆されています。この分野の歴史的背景と、幅広い最新の研究成果の両方を概説します。強化学習とは、動的な環境との試行錯誤を通して行動を学習するエージェントが直面する問題です。本論文で述べる研究は心理学の研究と類似点があるものの、詳細と「強化」という用語の使用において大きく異なります。本論文では、探索と活用のトレードオフ、マルコフ決定理論による分野の基礎の確立、遅延強化からの学習、学習を加速するための経験的モデルの構築、一般化と階層性の活用、隠れ状態への対処など、強化学習の中心的な課題について論じる。最後に、いくつかの実装済みシステムの調査と、強化学習における現在の手法の実用性の評価を行う。
A Divergence Critic for Inductive Proof
帰納的証明のための発散批評
Inductive theorem provers often diverge. This paper describes a simple critic, a computer program which monitors the construction of inductive proofs attempting to identify diverging proof attempts. Divergence is recognized by means of a “difference matching” procedure. The critic then proposes lemmas and generalizations which “ripple” these differences away so that the proof can go through without divergence. The critic enables the theorem prover Spike to prove many theorems completely automatically from the definitions alone.
帰納的定理証明器はしばしば発散します。本論文では、帰納的証明の構築を監視し、発散する証明の試みを特定しようとするコンピュータプログラムである、シンプルな批評家について説明します。発散は「差異マッチング」手順によって認識されます。批評家は、これらの差異を「波及的に」解消し、証明が発散することなく通過できるように、補題と一般化を提案します。批評家により、定理証明器Spikeは定義のみから多くの定理を完全に自動的に証明できるようになります。
Well-Founded Semantics for Extended Logic Programs with Dynamic Preferences
動的選好を持つ拡張論理プログラムのための十分な根拠を持つ意味論
The paper describes an extension of well-founded semantics for logic programs with two types of negation. In this extension information about preferences between rules can be expressed in the logical language and derived dynamically. This is achieved by using a reserved predicate symbol and a naming technique. Conflicts among rules are resolved whenever possible on the basis of derived preference information. The well-founded conclusions of prioritized logic programs can be computed in polynomial time. A legal reasoning example illustrates the usefulness of the approach.
本論文では、2種類の否定を持つ論理プログラムに対するwell-founded semanticsの拡張について説明します。この拡張では、規則間の優先順位に関する情報を論理言語で表現し、動的に導出することができます。これは、予約語記号と命名技法を用いることで実現されます。規則間の衝突は、可能な限り導出された優先順位情報に基づいて解決されます。優先順位付けされた論理プログラムの根拠のある結論は、多項式時間で計算できます。法的推論の例は、このアプローチの有用性を示しています。
Practical Methods for Proving Termination of General Logic Programs
一般論理プログラムの停止性を証明するための実際的手法
Termination of logic programs with negated body atoms (here called general logic programs) is an important topic. One reason is that many computational mechanisms used to process negated atoms, like Clark’s negation as failure and Chan’s constructive negation, are based on termination conditions. This paper introduces a methodology for proving termination of general logic programs w.r.t. the Prolog selection rule. The idea is to distinguish parts of the program depending on whether or not their termination depends on the selection rule. To this end, the notions of low-, weakly up-, and up-acceptable program are introduced. We use these notions to develop a methodology for proving termination of general logic programs, and show how interesting problems in non-monotonic reasoning can be formalized and implemented by means of terminating general logic programs.
否定されたボディアトムを持つ論理プログラム（ここでは一般論理プログラムと呼ぶ）の停止性は重要なトピックです。その理由の1つは、クラークの失敗否定やチャンの構成的否定など、否定されたアトムを処理するために使用される多くの計算メカニズムが停止条件に基づいていることです。本論文では、Prologの選択規則に関して一般論理プログラムの停止性を証明するための方法論を紹介します。その考え方は、停止性が選択規則に依存するかどうかによってプログラムの一部を区別することです。この目的のために、低許容プログラム、弱上許容プログラム、および上許容プログラムの概念を導入します。これらの概念を用いて一般論理プログラムの停止性を証明するための方法論を開発し、非単調推論における興味深い問題が、一般論理プログラムの停止性によってどのように形式化され実装されるかを示す。
Iterative Optimization and Simplification of Hierarchical Clusterings
階層的クラスタリングの反復最適化と簡素化
Clustering is often used for discovering structure in data. Clustering systems differ in the objective function used to evaluate clustering quality and the control strategy used to search the space of clusterings. Ideally, the search strategy should consistently construct clusterings of high quality, but be computationally inexpensive as well. In general, we cannot have it both ways, but we can partition the search so that a system inexpensively constructs a `tentative’ clustering for initial examination, followed by iterative optimization, which continues to search in background for improved clusterings. Given this motivation, we evaluate an inexpensive strategy for creating initial clusterings, coupled with several control strategies for iterative optimization, each of which repeatedly modifies an initial clustering in search of a better one. One of these methods appears novel as an iterative optimization strategy in clustering contexts. Once a clustering has been constructed it is judged by analysts — often according to task-specific criteria. Several authors have abstracted these criteria and posited a generic performance task akin to pattern completion, where the error rate over completed patterns is used to `externally’ judge clustering utility. Given this performance task, we adapt resampling-based pruning strategies used by supervised learning systems to the task of simplifying hierarchical clusterings, thus promising to ease post-clustering analysis. Finally, we propose a number of objective functions, based on attribute-selection measures for decision-tree induction, that might perform well on the error rate and simplicity dimensions.
クラスタリングは、データの構造を発見するためによく使用されます。クラスタリングシステムは、クラスタリングの品質を評価するために使用される目的関数と、クラスタリング空間を探索するために使用される制御戦略が異なります。理想的には、探索戦略は一貫して高品質のクラスタリングを構築しつつ、計算コストも低く抑えるべきです。一般的に、この両方を同時に実現することはできませんが、システムが初期検討のための「暫定的な」クラスタリングを低コストで構築し、その後、反復最適化を行い、バックグラウンドで改善されたクラスタリングの探索を継続するように、探索を分割することは可能です。この動機に基づき、我々は初期クラスタリングを作成するための低コストな戦略と、より良いクラスタリングを求めて初期クラスタリングを繰り返し修正する反復最適化のための複数の制御戦略を評価します。これらの手法の1つは、クラスタリングのコンテキストにおける反復最適化戦略として斬新です。クラスタリングが構築されると、分析者によって、多くの場合タスク固有の基準に基づいて評価されます。いくつかの著者はこれらの基準を抽象化し、パターン補完に類似した汎用的なパフォーマンスタスクを仮定しました。このタスクでは、完了したパターンのエラー率を用いてクラスタリングの効用を「外部的に」判断します。このパフォーマンス課題を踏まえ、教師あり学習システムで用いられるリサンプリングに基づく枝刈り戦略を階層的クラスタリングの単純化タスクに適用することで、クラスタリング後の分析を容易にします。最後に、決定木誘導における属性選択尺度に基づき、エラー率と単純さの次元において良好なパフォーマンスを発揮する可能性のあるいくつかの目的関数を提案します。
Active Learning with Statistical Models
統計モデルを用いた能動学習
For many types of machine learning algorithms, one can compute the statistically `optimal’ way to select training data. In this paper, we review how optimal data selection techniques have been used with feedforward neural networks. We then show how the same principles may be used to select data for two alternative, statistically-based learning architectures: mixtures of Gaussians and locally weighted regression. While the techniques for neural networks are computationally expensive and approximate, the techniques for mixtures of Gaussians and locally weighted regression are both efficient and accurate. Empirically, we observe that the optimality criterion sharply decreases the number of training examples the learner needs in order to achieve good performance.
多くの種類の機械学習アルゴリズムにおいて、統計的に「最適な」学習データ選択方法を計算できます。本稿では、フィードフォワードニューラルネットワークにおいて最適なデータ選択技術がどのように用いられてきたかを概説します。次に、同じ原理が、統計に基づく2つの学習アーキテクチャ（混合ガウス分布と局所重み付き回帰）においてデータ選択にどのように適用できるかを示します。ニューラルネットワークの技術は計算コストが高く近似的ですが、混合ガウス分布と局所重み付き回帰の技術は効率的かつ正確です。経験的に、最適性基準によって、学習器が良好なパフォーマンスを達成するために必要な学習例の数が大幅に減少することがわかります。
The Design and Experimental Analysis of Algorithms for Temporal Reasoning
時間的推論のためのアルゴリズムの設計と実験的分析
Many applications — from planning and scheduling to problems in molecular biology — rely heavily on a temporal reasoning component. In this paper, we discuss the design and empirical analysis of algorithms for a temporal reasoning system based on Allen’s influential interval-based framework for representing temporal information. At the core of the system are algorithms for determining whether the temporal information is consistent, and, if so, finding one or more scenarios that are consistent with the temporal information. Two important algorithms for these tasks are a path consistency algorithm and a backtracking algorithm. For the path consistency algorithm, we develop techniques that can result in up to a ten-fold speedup over an already highly optimized implementation. For the backtracking algorithm, we develop variable and value ordering heuristics that are shown empirically to dramatically improve the performance of the algorithm. As well, we show that a previously suggested reformulation of the backtracking search problem can reduce the time and space requirements of the backtracking search. Taken together, the techniques we develop allow a temporal reasoning component to solve problems that are of practical size.
計画やスケジューリングから分子生物学の問題に至るまで、多くのアプリケーションは時間的推論コンポーネントに大きく依存しています。本稿では、時間情報を表現するためのAllenの影響力のある区間ベースのフレームワークに基づく時間的推論システムのアルゴリズムの設計と実証的分析について論じます。システムの中核となるのは、時間情報が一貫しているかどうかを判定し、一貫している場合は時間情報と一致する1つ以上のシナリオを見つけるアルゴリズムです。これらのタスクのための重要なアルゴリズムとして、パス一貫性アルゴリズムとバックトラッキングアルゴリズムの2つがあります。パス一貫性アルゴリズムについては、既に高度に最適化された実装と比較して最大10倍の高速化を実現する手法を開発します。バックトラッキングアルゴリズムについては、変数と値の順序付けに関するヒューリスティックを開発し、これがアルゴリズムの性能を劇的に向上させることが実証的に示されています。さらに、以前に提案されたバックトラッキング探索問題の定式化により、バックトラッキング探索に必要な時間と空間を削減できることを示します。我々が開発した技術を組み合わせることで、時間的推論コンポーネントが実用的な規模の問題を解決できるようになります。