Journal of Artificial Intelligence Resarch Vol. 26 (2006)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。
Engineering Benchmarks for Planning: the Domains Used in the Deterministic Part of IPC-4
計画のためのエンジニアリングベンチマーク：IPC-4の決定論的部分で使用されるドメイン
In a field of research about general reasoning mechanisms, it is essential to have appropriate benchmarks. Ideally, the benchmarks should reflect possible applications of the developed technology. In AI Planning, researchers more and more tend to draw their testing examples from the benchmark collections used in the International Planning Competition (IPC). In the organization of (the deterministic part of) the fourth IPC, IPC-4, the authors therefore invested significant effort to create a useful set of benchmarks. They come from five different (potential) real-world applications of planning: airport ground traffic control, oil derivative transportation in pipeline networks, model-checking safety properties, power supply restoration, and UMTS call setup. Adapting and preparing such an application for use as a benchmark in the IPC involves, at the time, inevitable (often drastic) simplifications, as well as careful choice between, and engineering of, domain encodings. For the first time in the IPC, we used compilations to formulate complex domain features in simple languages such as STRIPS, rather than just dropping the more interesting problem constraints in the simpler language subsets. The article explains and discusses the five application domains and their adaptation to form the PDDL test suites used in IPC-4. We summarize known theoretical results on structural properties of the domains, regarding their computational complexity and provable properties of their topology under the h+ function (an idealized version of the relaxed plan heuristic). We present new (empirical) results illuminating properties such as the quality of the most wide-spread heuristic functions (planning graph, serial planning graph, and relaxed plan), the growth of propositional representations over instance size, and the number of actions available to achieve each fact; we discuss these data in conjunction with the best results achieved by the different kinds of planners participating in IPC-4.
一般的な推論メカニズムの研究分野では、適切なベンチマークが不可欠です。理想的には、ベンチマークは開発された技術の考えられる応用を反映する必要があります。AIプランニングでは、研究者が国際プランニング コンペティション(IPC)で使用されるベンチマーク コレクションからテスト例を引き出す傾向がますます高まっています。そのため、4回目のIPCであるIPC-4 (の決定論的部分)の構成において、著者らは有用なベンチマーク セットの作成に多大な労力を費やしました。これらは、空港の地上交通管制、パイプライン ネットワークにおける石油派生製品の輸送、安全性プロパティのモデル チェック、電力供給復旧、UMTS通話セットアップという、5つの異なる(潜在的な)現実世界のプランニング アプリケーションから来ています。このようなアプリケーションをIPCのベンチマークとして使用するために適応および準備するには、その時点で、避けられない(多くの場合大幅な)単純化、およびドメイン エンコーディングの慎重な選択とエンジニアリングが伴います。IPCでは初めて、より興味深い問題の制約をより単純な言語サブセットに単に落とすのではなく、STRIPSなどの単純な言語で複雑なドメイン機能を定式化するためにコンパイルを使用しました。この記事では、5つのアプリケーション ドメインと、IPC-4で使用されるPDDLテスト スイートを形成するためのそれらの適応について説明し、考察します。ドメインの構造的特性、つまり計算複雑性やh+関数(緩和プラン ヒューリスティックの理想化バージョン)の下での位相の証明可能な特性に関する既知の理論的結果を要約します。最も広く普及しているヒューリスティック関数(プランニング グラフ、シリアル プランニング グラフ、緩和プラン)の品質、インスタンス サイズに対する命題表現の増加、各事実を達成するために利用可能なアクションの数などの特性を明らかにする新しい(経験的)結果を示します。これらのデータを、IPC-4に参加しているさまざまな種類のプランナーによって達成された最良の結果と併せて考察します。
Multiple-Goal Heuristic Search
多目標ヒューリスティック探索
This paper presents a new framework for anytime heuristic searchwhere the task is to achieve as many goals as possible within theallocated resources. We show the inadequacy of traditionaldistance-estimation heuristics for tasks of this type and presentalternative heuristics that are more appropriate for multiple-goalsearch. In particular, we introduce the marginal-utilityheuristic, which estimates the cost and the benefit of exploring asubtree below a search node. We developed two methods for onlinelearning of the marginal-utility heuristic. One is based on localsimilarity of the partial marginal utility of sibling nodes, andthe other generalizes marginal-utility over the state featurespace. We apply our adaptive and non-adaptive multiple-goal searchalgorithms to several problems, including focused crawling, andshow their superiority over existing methods.
本論文では、割り当てられたリソース内で可能な限り多くの目標を達成することをタスクとする、いつでもヒューリスティック検索のための新しいフレームワークを提示します。本稿では、従来の距離推定ヒューリスティックがこの種のタスクに不十分であることを示し、多目的探索により適した代替ヒューリスティックを提示します。特に、探索ノードの下位にあるサブツリーを探索する際のコストと便益を推定する限界効用ヒューリスティックを紹介します。限界効用ヒューリスティックのオンライン学習には2つの手法を開発した。1つは兄弟ノードの部分限界効用の局所的類似性に基づく手法であり、もう1つは状態特徴空間全体に限界効用を一般化する手法です。適応型および非適応型の多目的探索アルゴリズムを、フォーカスクローリングを含むいくつかの問題に適用し、既存の手法に対する優位性を示す。
Clause/Term Resolution and Learning in the Evaluation of Quantified Boolean Formulas
量化ブール式の評価における節／項解決と学習
Resolution is the rule of inference at the basis of most procedures for automated reasoning. In these procedures, the input formula is first translated into an equisatisfiable formula in conjunctive normal form (CNF) and then represented as a set of clauses. Deduction starts by inferring new clauses by resolution, and goes on until the empty clause is generated or satisfiability of the set of clauses is proven, e.g., because no new clauses can be generated.In this paper, we restrict our attention to the problem of evaluating Quantified Boolean Formulas (QBFs). In this setting, the above outlined deduction process is known to be sound and complete if given a formula in CNF and if a form of resolution, called “Q-resolution”, is used. We introduce Q-resolution on terms, to be used for formulas in disjunctive normal form. We show that the computation performed by most of the available procedures for QBFs –based on the Davis-Logemann-Loveland procedure (DLL) for propositional satisfiability– corresponds to a tree in which Q-resolution on terms and clauses alternate. This poses the theoretical bases for the introduction of learning, corresponding to recording Q-resolution formulas associated with the nodes of the tree. We discuss the problems related to the introduction of learning in DLL based procedures, and present solutions extending state-of-the-art proposals coming from the literature on propositional satisfiability. Finally, we show that our DLL based solver extended with learning, performs significantly better on benchmarks used in the 2003 QBF solvers comparative evaluation.
導出は、自動推論のほとんどの手順の基礎となる推論規則です。これらの手順では、入力式はまず連言標準形（CNF）の等充足式に変換され、次に節の集合として表現されます。演繹は、導出によって新しい節を推論することから始まり、空の節が生成されるか、節の集合の充足可能性が証明されるまで（例えば、新しい節を生成できないなど）続きます。本稿では、量化ブール式（QBF）の評価問題に焦点を絞ります。この設定では、CNFで記述された式が与えられ、「Q-導出」と呼ばれる導出形式が使用される場合、上記で概説した演繹プロセスは健全かつ完全であることが知られています。本稿では、選言標準形の式に使用される項のQ-導出を導入します。QBF（命題充足可能性のためのDavis-Logemann-Loveland手順（DLL）に基づく）の利用可能な手順のほとんどによって実行される計算は、項と節のQ解決が交互に行われるツリーに対応することを示します。これは、ツリーのノードに関連付けられたQ解決式を記録することに対応する、学習導入の理論的根拠を提示します。DLLベースの手順への学習導入に関連する問題について議論し、命題充足可能性に関する文献からの最先端の提案を拡張する解決策を提示します。最後に、学習機能を追加したDLLベースのソルバーは、2003年のQBFソルバー比較評価で使用されたベンチマークにおいて、大幅に優れたパフォーマンスを発揮することを示します。
Planning Graph Heuristics for Belief Space Search
確信空間探索のための計画グラフヒューリスティック
Some recent works in conditional planning have proposed reachability heuristics to improve planner scalability, but many lack a formal description of the properties of their distance estimates. To place previous work in context and extend work on heuristics for conditional planning, we provide a formal basis for distance estimates between belief states. We give a definition for the distance between belief states that relies on aggregating underlying state distance measures. We give several techniques to aggregate state distances and their associated properties. Many existing heuristics exhibit a subset of the properties, but in order to provide a standardized comparison we present several generalizations of planning graph heuristics that are used in a single planner. We compliment our belief state distance estimate framework by also investigating efficient planning graph data structures that incorporate BDDs to compute the most effective heuristics.We developed two planners to serve as test-beds for our investigation. The first, CAltAlt, is a conformant regression planner that uses A* search. The second, POND, is a conditional progression planner that uses AO* search. We show the relative effectiveness of our heuristic techniques within these planners. We also compare the performance of these planners with several state of the art approaches in conditional planning.
条件付きプランニングに関する最近の研究では、プランナーのスケーラビリティを向上させるための到達可能性ヒューリスティックが提案されていますが、その多くは距離推定の特性に関する正式な記述を欠いています。これまでの研究を文脈に当てはめ、条件付きプランニングのヒューリスティックに関する研究を拡張するために、我々は確信状態間の距離推定の正式な基盤を提供します。我々は、基礎となる状態距離尺度の集約に基づく確信状態間の距離の定義を提供します。状態距離とその関連特性を集約するためのいくつかの手法を示します。既存のヒューリスティックの多くは特性のサブセットを示していますが、標準化された比較を行うために、単一のプランナーで使用されるプランニンググラフヒューリスティックの一般化をいくつか示します。私たちは、BDDを組み込んで最も効果的なヒューリスティックを計算する効率的なプランニンググラフデータ構造も調査することで、確信状態距離推定フレームワークを補完します。私たちは、調査のテストベッドとして機能する2つのプランナーを開発しました。1つ目はCAltAltで、A*検索を使用する適合回帰プランナーです。2つ目はPONDで、AO*検索を使用する条件付き進行プランナーです。これらのプランナーにおける私たちのヒューリスティック手法の相対的な有効性を示します。また、これらのプランナーのパフォーマンスを、条件付きプランニングにおけるいくつかの最先端のアプローチと比較します。
Temporal Planning using Subgoal Partitioning and Resolution in SGPlan
SGPlanにおけるサブゴール分割と解決を用いた時間計画
In this paper, we present the partitioning of mutual-exclusion (mutex) constraints in temporal planning problems and its implementation in the SGPlan4 planner. Based on the strong locality of mutex constraints observed in many benchmarks of the Fourth International Planning Competition (IPC4), we propose to partition the constraints of a planning problem into groups based on their subgoals. Constraint partitioning leads to significantly easier subproblems that are similar to the original problem and that can be efficiently solved by the same planner with some modifications to its objective function. We present a partition-and-resolve strategy that looks for locally optimal subplans in constraint-partitioned temporal planning subproblems and that resolves those inconsistent global constraints across the subproblems. We also discuss some implementation details of SGPlan4, which include the resolution of violated global constraints, techniques for handling producible resources, landmark analysis, path finding and optimization, search-space reduction, and modifications of Metric-FF when used as a basic planner in SGPlan4. Last, we show results on the sensitivity of each of these techniques in quality-time trade-offs and experimentally demonstrate that SGPlan4 is effective for solving the IPC3 and IPC4 benchmarks.
本稿では、時間計画問題における相互排他（ミューテックス）制約の分割と、SGPlan4プランナーへの実装について述べる。第4回国際計画コンペティション（IPC4）の多くのベンチマークで観察されたミューテックス制約の強い局所性に基づき、計画問題の制約をサブゴールに基づいてグループに分割することを提案します。制約分割により、元の問題に類似した、目的関数に若干の修正を加えることで同じプランナーで効率的に解ける、大幅に容易なサブ問題が生成されます。本稿では、制約分割された時間計画サブ問題において局所的に最適なサブプランを探し、サブ問題間で矛盾するグローバル制約を解決する、分割解決戦略を提示します。また、SGPlan4の実装の詳細についても議論します。これには、違反したグローバル制約の解決、生産可能なリソースの処理手法、ランドマーク分析、経路探索と最適化、探索空間の縮小、そしてSGPlan4の基本プランナーとして使用される場合のMetric-FFの修正が含まれます。最後に、これらの各手法が品質と時間のトレードオフにどのように影響するかについての結果を示し、SGPlan4がIPC3およびIPC4ベンチマークを解くのに効果的であることを実験的に実証します。
Breaking Instance-Independent Symmetries In Exact Graph Coloring
正確なグラフ彩色におけるインスタンス非依存の対称性の破れ
Code optimization and high level synthesis can be posed as constraint satisfaction and optimization problems, such as graph coloring used in register allocation. Graph coloring is also used to model more traditional CSPs relevant to AI, such as planning, time-tabling and scheduling. Provably optimal solutions may be desirable for commercial and defense applications. Additionally, for applications such as register allocation and code optimization, naturally-occurring instances of graph coloring are often small and can be solved optimally. A recent wave of improvements in algorithms for Boolean satisfiability (SAT) and 0-1 Integer Linear Programming (ILP) suggests generic problem-reduction methods, rather than problem-specific heuristics, because (1) heuristics may be upset by new constraints, (2) heuristics tend to ignore structure, and (3) many relevant problems are provably inapproximable. Problem reductions often lead to highly symmetric SAT instances, and symmetries are known to slow down SAT solvers. In this work, we compare several avenues for symmetry breaking, in particular when certain kinds of symmetry are present in all generated instances. Our focus on reducing CSPs to SAT allows us to leverage recent dramatic improvement in SAT solvers and automatically benefit from future progress. We can use a variety of black-box SAT solvers without modifying their source code because our symmetry-breaking techniques are static, i.e., we detect symmetries and add symmetry breaking predicates (SBPs) during pre-processing.An important result of our work is that among the types of instance-independent SBPs we studied and their combinations, the simplest and least complete constructions are the most effective. Our experiments also clearly indicate that instance-independent symmetries should mostly be processed together with instance-specific symmetries rather than at the specification level, contrary to what has been suggested in theliterature.
コード最適化と高位合成は、レジスタ割り当てで使用されるグラフカラーリングなどの制約充足問題および最適化問題として扱うことができます。グラフカラーリングは、計画、タイムテーブル作成、スケジューリングなど、AIに関連するより伝統的なCSPをモデル化するためにも使用されます。商用および防衛用途では、証明可能な最適解が望ましい場合があります。さらに、レジスタ割り当てやコード最適化などの用途では、グラフカラーリングの自然発生的なインスタンスは小さく、最適に解決できる場合が多いです。ブール充足可能性（SAT）と0-1整数線形計画法（ILP）のアルゴリズムにおける最近の一連の改善は、問題固有のヒューリスティックではなく、一般的な問題縮減法を示唆しています。その理由は、（1）ヒューリスティックは新しい制約によって覆される可能性があること、（2）ヒューリスティックは構造を無視する傾向があること、（3）多くの関連する問題は近似不可能であることが証明されているためです。問題の縮減は、高度に対称的なSATインスタンスにつながることが多く、対称性はSATソルバーの速度を低下させることが知られています。本研究では、特に生成されたすべてのインスタンスに特定の種類の対称性が存在する場合の対称性破壊の複数の方法を比較します。CSPをSATに縮小することに焦点を当てることで、SATソルバーの最近の劇的な改善を活用し、将来の進歩から自動的に恩恵を受けることができます。対称性破壊手法は静的であるため、つまり、前処理中に対称性を検出して対称性破壊述語(SBP)を追加するため、さまざまなブラックボックスSATソルバーをソースコードを変更することなく使用できます。本研究の重要な結果は、調査したインスタンスに依存しないSBPの種類とその組み合わせの中で、最も単純で不完全な構成が最も効果的であるということです。また、実験では、文献で示唆されているのとは反対に、インスタンスに依存しない対称性は、仕様レベルではなく、インスタンス固有の対称性と一緒に処理する必要があることが明確に示されています。
How the Landscape of Random Job Shop Scheduling Instances Depends on the Ratio of Jobs to Machines
ランダムジョブショップスケジューリングインスタンスのランドスケープがジョブとマシンの比率にどのように依存するか
We characterize the search landscape of random instances of the job shop scheduling problem (JSP). Specifically, we investigate how the expected values of (1) backbone size, (2) distance between near-optimal schedules, and (3) makespan of random schedules vary as a function of the job to machine ratio (N/M). For the limiting cases N/M approaches 0 and N/M approaches infinity we provide analytical results, while for intermediate values of N/M we perform experiments. We prove that as N/M approaches 0, backbone size approaches 100%, while as N/M approaches infinity the backbone vanishes. In the process we show that as N/M approaches 0 (resp. N/M approaches infinity), simple priority rules almost surely generate an optimal schedule, providing theoretical evidence of an “easy-hard-easy” pattern of typical-case instance difficulty in job shop scheduling. We also draw connections between our theoretical results and the “big valley” picture of JSP landscapes.
ジョブショップ・スケジューリング問題（JSP）のランダムインスタンスの探索ランドスケープを特徴づける。具体的には、(1)バックボーンのサイズ、(2)準最適スケジュール間の距離、(3)ランダムスケジュールのメイクスパンの期待値が、ジョブ対機械比（N/M）の関数としてどのように変化するかを調査します。N/Mが0に近づく場合とN/Mが無限大に近づく場合の極限ケースについては解析結果を示し、N/Mの中間値については実験を行う。N/Mが0に近づくとバックボーンのサイズは100%に近づくが、N/Mが無限大に近づくとバックボーンが消滅することを証明した。その過程で、N/Mが0に近づく（またはN/Mが無限大に近づく）と、単純な優先順位ルールによってほぼ確実に最適スケジュールが生成されることを示し、ジョブショップ・スケジューリングにおける典型的なインスタンスの難易度が「簡単-難しい-簡単」というパターンであることを理論的に証明した。また、理論的結果とJSPランドスケープの「大きな谷」図との関連性も示す。
The Fast Downward Planning System
高速下方計画システム
Fast Downward is a classical planning system based on heuristic search. It can deal with general deterministic planning problems encoded in the propositional fragment of PDDL2.2, including advanced features like ADL conditions and effects and derived predicates (axioms). Like other well-known planners such as HSP and FF, Fast Downward is a progression planner, searching the space of world states of a planning task in the forward direction. However, unlike other PDDL planning systems, Fast Downward does not use the propositional PDDL representation of a planning task directly. Instead, the input is first translated into an alternative representation called multi-valued planning tasks, which makes many of the implicit constraints of a propositional planning task explicit. Exploiting this alternative representation, Fast Downward uses hierarchical decompositions of planning tasks for computing its heuristic function, called the causal graph heuristic, which is very different from traditional HSP-like heuristics based on ignoring negative interactions of operators.In this article, we give a full account of Fast Downward’s approach to solving multi-valued planning tasks. We extend our earlier discussion of the causal graph heuristic to tasks involving axioms and conditional effects and present some novel techniques for search control that are used within Fast Downward’s best-first search algorithm: preferred operators transfer the idea of helpful actions from local search to global best-first search, deferred evaluation of heuristic functions mitigates the negative effect of large branching factors on search performance, and multi-heuristic best-first search combines several heuristic evaluation functions within a single search algorithm in an orthogonal way. We also describe efficient data structures for fast state expansion (successor generators and axiom evaluators) and present a new non-heuristic search algorithm called focused iterative-broadening search, which utilizes the information encoded in causal graphs in a novel way.Fast Downward has proven remarkably successful: It won the “classical” (i.e., propositional, non-optimising) track of the 4th International Planning Competition at ICAPS 2004, following in the footsteps of planners such as FF and LPG. Our experiments show that it also performs very well on the benchmarks of the earlier planning competitions and provide some insights about the usefulness of the new search enhancements.
Fast Downwardは、ヒューリスティック探索に基づく古典的なプランニングシステムです。Fast Downwardは、PDDL2.2の命題フラグメントにエンコードされた一般的な決定論的プランニング問題に対応でき、ADL条件と効果、導出述語（公理）といった高度な機能も含みます。HSPやFFといった他のよく知られたプランナーと同様に、Fast Downwardはプログレッションプランナーであり、プランニングタスクの世界状態空間を順方向に探索します。しかし、他のPDDLプランニングシステムとは異なり、Fast Downwardはプランニングタスクの命題的PDDL表現を直接使用しません。代わりに、入力はまず多値プランニングタスクと呼ばれる代替表現に変換され、これにより命題的プランニングタスクの暗黙的な制約の多くが明示化されます。この代替表現を活用して、Fast Downwardは、因果グラフ ヒューリスティックと呼ばれるヒューリスティック関数を計算するための計画タスクの階層的分解を使用します。これは、演算子の負の相互作用を無視することに基づく従来のHSPのようなヒューリスティックとは大きく異なります。この記事では、多値計画タスクを解決するためのFast Downwardのアプローチについて詳しく説明します。因果グラフ ヒューリスティックに関する以前の説明を、公理と条件付き効果を含むタスクに拡張し、Fast Downwardのベスト ファースト検索アルゴリズム内で使用される検索制御の新しい手法をいくつか紹介します。優先演算子は、役立つアクションの考え方をローカル検索からグローバル ベスト ファースト検索に移行します。ヒューリスティック関数の遅延評価は、大きな分岐要因が検索パフォーマンスに与える悪影響を軽減します。また、マルチヒューリスティック ベスト ファースト検索は、単一の検索アルゴリズム内で複数のヒューリスティック評価関数を直交的に組み合わせます。また、高速な状態拡張（後継生成器と公理評価器）のための効率的なデータ構造についても説明し、因果グラフにエンコードされた情報を斬新な方法で利用する、フォーカス反復拡張探索と呼ばれる新しい非ヒューリスティック探索アルゴリズムを紹介します。Fast Downwardは目覚ましい成功を収め、FFやLPGといったプランナーに続き、ICAPS 2004の第4回国際プランニングコンペティションの「古典的」（つまり、命題的、非最適化）トラックで優勝しました。私たちの実験では、以前のプランニングコンペティションのベンチマークでも非常に優れたパフォーマンスを示し、新しい探索拡張機能の有用性に関する知見が得られました。
Convexity Arguments for Efficient Minimization of the Bethe and Kikuchi Free Energies
ベーテ自由エネルギーと菊池自由エネルギーの効率的な最小化のための凸性論証
Loopy and generalized belief propagation are popular algorithms for approximate inference in Markov random fields and Bayesian networks. Fixed points of these algorithms have been shown to correspond to extrema of the Bethe and Kikuchi free energy, both of which are approximations of the exact Helmholtz free energy. However, belief propagation does not always converge, which motivates approaches that explicitly minimize the Kikuchi/Bethe free energy, such as CCCP and UPS.Here we describe a class of algorithms that solves this typically non-convex constrained minimization problem through a sequence of convex constrained minimizations of upper bounds on the Kikuchi free energy. Intuitively one would expect tighter bounds to lead to faster algorithms, which is indeed convincingly demonstrated in our simulations. Several ideas are applied to obtain tight convex bounds that yield dramatic speed-ups over CCCP.
ループ型および一般化ビリーフプロパゲーションは、マルコフ確率場およびベイジアンネットワークにおける近似推論のための一般的なアルゴリズムです。これらのアルゴリズムの固定点は、ベーテ自由エネルギーおよび菊池自由エネルギーの極値に対応することが示されていることが示されています。これらの自由エネルギーはどちらも、正確なヘルムホルツ自由エネルギーの近似です。しかし、ビリーフプロパゲーションは常に収束するわけではないため、CCCPやUPSなど、菊池/ベーテ自由エネルギーを明示的に最小化するアプローチが求められています。ここでは、この典型的には非凸制約最小化問題を、菊池自由エネルギーの上限に対する一連の凸制約最小化を通じて解くアルゴリズムのクラスについて説明します。直感的には、より狭い境界がアルゴリズムの高速化につながると予想されますが、これは実際に私たちのシミュレーションで説得力を持って実証されています。CCCPよりも劇的な高速化をもたらすタイトな凸境界を得るために、いくつかのアイデアが適用されます。
Admissible and Restrained Revision
許容修正と制約修正
As partial justification of their framework for iterated belief revision Darwiche and Pearl convincingly argued against Boutilier’s natural revision and provided a prototypical revision operator that fits into their scheme. We show that the Darwiche-Pearl arguments lead naturally to the acceptance of a smaller class of operators which we refer to as admissible. Admissible revision ensures that the penultimate input is not ignored completely, thereby eliminating natural revision, but includes the Darwiche-Pearl operator, Nayak’s lexicographic revision operator, and a newly introduced operator called restrained revision. We demonstrate that restrained revision is the most conservative of admissible revision operators, effecting as few changes as possible, while lexicographic revision is the least conservative, and point out that restrained revision can also be viewed as a composite operator, consisting of natural revision preceded by an application of a “backwards revision” operator previously studied by Papini. Finally, we propose the establishment of a principled approach for choosing an appropriate revision operator in different contexts and discuss future work.
反復的信念修正のための彼らの枠組みの部分的な正当化として、DarwicheとPearlは、Boutilierの自然修正に反論し、彼らのスキームに適合するプロトタイプの修正演算子を提示した。我々は、Darwiche-Pearlの議論が、我々が許容可能と呼ぶより少数の演算子の受け入れに自然に繋がることを示す。許容可能な修正は、最後から2番目の入力が完全に無視されることを保証し、それによって自然修正を排除するが、Darwiche-Pearl演算子、Nayakの辞書式修正演算子、そして新たに導入された制限修正と呼ばれる演算子を含む。我々は、抑制された修正が許容される修正演算子の中で最も保守的であり、可能な限り変更を少なくする一方、辞書式修正は最も保守的でないことを示す。また、抑制された修正は、Papiniが以前に研究した「後方修正」演算子を適用した自然修正からなる複合演算子と見なすこともできることを指摘します。最後に、様々な状況において適切な修正演算子を選択するための原理的なアプローチの確立を提案し、今後の研究課題について議論します。
Domain Adaptation for Statistical Classifiers
統計的分類器のドメイン適応
The most basic assumption used in statistical learning theory is that training data and test data are drawn from the same underlying distribution. Unfortunately, in many applications, the “in-domain” test data is drawn from a distribution that is related, but not identical, to the “out-of-domain” distribution of the training data. We consider the common case in which labeled out-of-domain data is plentiful, but labeled in-domain data is scarce. We introduce a statistical formulation of this problem in terms of a simple mixture model and present an instantiation of this framework to maximum entropy classifiers and their linear chain counterparts. We present efficient inference algorithms for this special case based on the technique of conditional expectation maximization. Our experimental results show that our approach leads to improved performance on three real world tasks on four different data sets from the natural language processing domain.
統計学習理論において用いられる最も基本的な仮定は、訓練データとテストデータが同じ基礎分布から抽出されるというものです。残念ながら、多くの応用において、「ドメイン内」のテストデータは、訓練データの「ドメイン外」の分布と関連しているものの同一ではない分布から抽出されます。我々は、ラベル付きドメイン外データは豊富であるが、ラベル付きドメイン内データは乏しいという一般的なケースを検討します。我々は、この問題の統計的定式化を単純な混合モデルで導入し、この枠組みを最大エントロピー分類器とその線形連鎖対応物に具体化します。我々は、条件付き期待値最大化の手法に基づく、この特殊なケースに対する効率的な推論アルゴリズムを提示します。実験結果は、我々のアプローチが、自然言語処理分野の4つの異なるデータセットを用いた3つの実世界タスクにおいてパフォーマンスの向上につながることを示しています。
A Logic for Reasoning about Evidence
証拠に関する推論のための論理
We introduce a logic for reasoning about evidence that essentiallyviews evidence as a function from prior beliefs (before making anobservation) to posterior beliefs (after making the observation). We provide a sound and complete axiomatization for the logic, andconsider the complexity of the decision problem. Although the reasoning in the logic is mainly propositional, we allow variables representing numbers and quantification over them. This expressive power seems necessary to capture important properties of evidence.
我々は、証拠を本質的に事前の信念（観察を行う前）から事後的な信念（観察を行った後）への関数とみなす、証拠に関する推論のための論理を導入します。この論理に対して健全かつ完全な公理化を提供し、決定問題の複雑さを考慮します。この論理における推論は主に命題的であるが、数値を表す変数とそれらに対する量化を許容します。この表現力は、証拠の重要な特性を捉えるために必要と思われます。