An approximative inference method for solving ∃∀SO satisfiability problems
∃∀SO充足可能性問題を解くための近似推論法
This paper considers the fragment ∃∀SO of second-order logic. Many interesting problems, such as conformant planning, can be naturally expressed as finite domain satisfiability problems of this logic. Such satisfiability problems are computationally hard (ΣP2) and many of these problems are often solved approximately. In this paper, we develop a general approximative method, i.e., a sound but incomplete method, for solving ∃∀SO satisfiability problems. We use a syntactic representation of a constraint propagation method for first-order logic to transform such an ∃∀SO satisfiability problem to an ∃SO(ID) satisfiability problem (second-order logic, extended with inductive definitions). The finite domain satisfiability problem for the latter language is in NP and can be handled by several existing solvers. Inductive definitions are a powerful knowledge representation tool, and this moti- vates us to also approximate ∃∀SO(ID) problems. In order to do this, we first show how to perform propagation on such inductive definitions. Next, we use this to approximate ∃∀SO(ID) satisfiability problems. All this provides a general theoretical framework for a number of approximative methods in the literature. Moreover, we also show how we can use this framework for solving practical useful problems, such as conformant planning, in an effective way.
本論文では、二次階述語論理のフラグメント∃∀SOを検討します。適合計画などの多くの興味深い問題は、この論理の有限領域の充足可能性問題として自然に表現できます。このような充足可能性問題は計算量的に困難(ΣP2)であり、多くの場合、近似的に解かれます。この論文では、∃∀SO充足可能性問題を解くための一般的な近似法、つまり健全だが不完全な方法を開発します。私たちは、一階述語論理の制約伝播法の構文表現を使用して、このような ∃∀SO充足可能性問題を ∃SO(ID)充足可能性問題(帰納的定義で拡張された二階述語論理)に変換します。後者の言語の有限領域の充足可能性問題はNPであり、いくつかの既存のソルバーで処理できます。帰納的定義は強力な知識表現ツールであり、これが ∃∀SO(ID)問題の近似にもつながる理由です。これを実行するために、まず、このような帰納的定義に対して伝播を実行する方法を示します。次に、これを用いて∃∀SO(ID)の充足可能性問題を近似します。これにより、文献で紹介されている多くの近似手法に対する一般的な理論的枠組みが提供されます。さらに、この枠組みを用いて、適合計画などの実用上有用な問題を効果的に解く方法も示す。
Evaluating Indirect Strategies for Chinese-Spanish Statistical Machine Translation
中国語-スペイン語統計機械翻訳における間接戦略の評価
Although, Chinese and Spanish are two of the most spoken languages in the world, not much research has been done in machine translation for this language pair. This paper focuses on investigating the state-of-the-art of Chinese-to-Spanish statistical machine translation (SMT), which nowadays is one of the most popular approaches to machine translation. For this purpose, we report details of the available parallel corpus which are Basic Traveller Expressions Corpus (BTEC), Holy Bible and United Nations (UN). Additionally, we conduct experimental work with the largest of these three corpora to explore alternative SMT strategies by means of using a pivot language. Three alternatives are considered for pivoting: cascading, pseudo-corpus and triangulation. As pivot language, we use either English, Arabic or French. Results show that, for a phrase-based SMT system, English is the best pivot language between Chinese and Spanish. We propose a system output combination using the pivot strategies which is capable of outperforming the direct translation strategy. The main objective of this work is motivating and involving the research community to work in this important pair of languages given their demographic impact.
中国語とスペイン語は世界で最も多く話されている2つの言語ですが、この言語ペアの機械翻訳に関する研究はあまり行われていません。本論文では、現在最も人気のある機械翻訳手法の1つである、中国語からスペイン語への統計的機械翻訳（SMT）の現状調査に焦点を当てています。この目的のために、利用可能な対訳コーパスであるBasic Traveller Expressions Corpus（BTEC）、Holy Bible、United Nations（UN）の詳細を報告します。さらに、これら3つのコーパスの中で最大のものを使用して実験作業を行い、ピボット言語を使用することで代替のSMT戦略を探索します。ピボットには、カスケーディング、疑似コーパス、および三角測量の3つの選択肢が考えられます。ピボット言語として、英語、アラビア語、またはフランス語を使用します。結果は、フレーズベースのSMTシステムの場合、英語が中国語とスペイン語の間の最適なピボット言語であることを示しています。私たちは、直接翻訳戦略よりも優れたパフォーマンスを発揮する、ピボット戦略を使用したシステム出力の組み合わせを提案します。本研究の主な目的は、人口統計学的影響を考慮して、この重要な言語ペアでの作業に研究コミュニティを動機付け、関与させることです。
Tractable Set Constraints
扱いやすい集合制約
Many fundamental problems in artificial intelligence, knowledge representation, and verification involve reasoning about sets and relations between sets and can be modeled as set constraint satisfaction problems (set CSPs). Such problems are frequently intractable, but there are several important set CSPs that are known to be polynomial-time tractable. We introduce a large class of set CSPs that can be solved in quadratic time. Our class, which we call EI, contains all previously known tractable set CSPs, but also some new ones that are of crucial importance for example in description logics. The class of EI set constraints has an elegant universal-algebraic characterization, which we use to show that every set constraint language that properly contains all EI set constraints already has a finite sublanguage with an NP-hard constraint satisfaction problem.
人工知能、知識表現、検証における多くの基本的な問題は、集合および集合間の関係についての推論を伴い、集合制約充足問題(集合CSP)としてモデル化できます。このような問題はしばしば扱いにくいものですが、多項式時間で扱いやすいことが知られている重要な集合CSPがいくつかあります。私たちは、2次時間で解くことができる集合CSPの大規模なクラスを導入します。EIと呼ぶこのクラスには、これまで知られている扱いやすい集合CSPがすべて含まれているだけでなく、記述論理などで非常に重要になる新しい集合CSPもいくつか含まれています。EI集合制約のクラスにはエレガントな普遍代数的特徴付けがあり、これを使用して、すべてのEI集合制約を適切に含むすべての集合制約言語には、NP困難な制約充足問題を持つ有限の部分言語がすでに存在することを示します。
The Time Complexity of A* with Approximate Heuristics on Multiple-Solution Search Spaces
複数解探索空間における近似ヒューリスティックを用いたA*の時間計算量
We study the behavior of the A* search algorithm when coupled with a heuristic h satisfying (1-epsilon1)h* <= h <=(1+epsilon2)h*, where 0 <= epsilon1, epsilon2 < 1 are small constants and h* denotes the optimal cost to a solution. We prove a rigorous, general upper bound on the time complexity of A* search on trees that depends on both the accuracy of the heuristic and the distribution of solutions. Our upper bound is essentially tight in the worst case; in fact, we show nearly matching lower bounds that are attained even by non-adversarially chosen solution sets induced by a simple stochastic model. A consequence of our rigorous results is that the effective branching factor of the search will be reduced as long as epsilon1+epsilon2 < 1 and the number of near-optimal solutions in the search tree is not too large. We go on to provide an upper bound for A* search on graphs and in this context establish a bound on running time determined by the spectrum of the graph.We then experimentally explore to what extent our rigorous upper bounds predict the behavior of A* in some natural, combinatorially-rich search spaces. We begin by applying A* to solve the knapsack problem with near-accurate admissible heuristics constructed from an efficient approximation algorithm for this problem. We additionally apply our analysis of A* search for the partial Latin square problem, where we can provide quite exact analytic bounds on the number of near-optimal solutions. These results demonstrate a dramatic reduction in effective branching factor of A* when coupled with near-accurate heuristics in search spaces with suitably sparse solution sets.
我々は、(1-epsilon1)h* <= h <=(1+epsilon2)h*を満たすヒューリスティックhと組み合わせた場合のA*検索アルゴリズムの挙動を調べる。ここで、0 <= epsilon1、epsilon2 < 1は小さな定数であり、h*はソリューションへの最適コストを表す。木構造上のA*探索の時間計算量について、厳密で一般的な上限を証明します。この上限は、ヒューリスティックの精度と解の分布の両方に依存します。この上限は、最悪の場合でも本質的に厳密です。実際、単純な確率モデルによって誘導される非敵対的に選択された解集合によっても、ほぼ一致する下限が達成されることを示しています。厳密な結果の結果として、epsilon1+epsilon2 < 1かつ探索木内の準最適解の数が多すぎない限り、探索の有効分岐係数が低減されます。次に、グラフ上のA*探索の上限を示し、このコンテキストで、グラフのスペクトルによって決まる実行時間の上限を確立します。次に、この厳密な上限が、いくつかの自然で組み合わせが豊富な探索空間におけるA*の挙動をどの程度予測できるかを実験的に調査します。まず、ナップサック問題にA*を適用し、この問題に対する効率的な近似アルゴリズムから構築された準正確な許容ヒューリスティックを用いて解く。さらに、A*探索の解析を部分ラテン方陣問題に適用し、準最適解の数について非常に正確な解析的限界を与える。これらの結果は、解集合が適度に疎な探索空間において、準正確なヒューリスティックと組み合わせることで、A*の有効分岐係数が劇的に減少することを示す。
Learning to Predict from Textual Data
テキストデータからの予測学習
Given a current news event, we tackle the problem of generating plausible predictions of future events it might cause. We present a new methodology for modeling and predicting such future news events using machine learning and data mining techniques. Our Pundit algorithm generalizes examples of causality pairs to infer a causality predictor. To obtain precisely labeled causality examples, we mine 150 years of news articles and apply semantic natural language modeling techniques to headlines containing certain predefined causality patterns. For generalization, the model uses a vast number of world knowledge ontologies. Empirical evaluation on real news articles shows that our Pundit algorithm performs as well as non-expert humans.
現在のニュースイベントが与えられた場合、それが引き起こす可能性のある将来のイベントについて妥当な予測を生成する問題に取り組む。我々は、機械学習とデータマイニング技術を用いて、このような将来のニュースイベントをモデル化および予測するための新しい方法論を提示します。我々のPunditアルゴリズムは、因果関係のペアの例を一般化して因果関係の予測子を推論します。正確にラベル付けされた因果関係の例を得るために、我々は150年分のニュース記事をマイニングし、特定の事前定義された因果関係パターンを含む見出しにセマンティック自然言語モデリング技術を適用します。一般化のために、モデルは膨大な数の世界知識オントロジーを使用します。実際のニュース記事を用いた実証的評価では、我々のPunditアルゴリズムが非専門家の人間と同等の性能を示すことが示されました。
Irrelevant and independent natural extension for sets of desirable gambles
望ましいギャンブル集合の無関係かつ独立した自然拡張
The results in this paper add useful tools to the theory of sets of desirable gambles, a growing toolbox for reasoning with partial probability assessments. We investigate how to combine a number of marginal coherent sets of desirable gambles into a joint set using the properties of epistemic irrelevance and independence. We provide formulas for the smallest such joint, called their independent natural extension, and study its main properties. The independent natural extension of maximal coherent sets of desirable gambles allows us to define the strong product of sets of desirable gambles. Finally, we explore an easy way to generalise these results to also apply for the conditional versions of epistemic irrelevance and independence. Having such a set of tools that are easily implemented in computer programs is clearly beneficial to fields, like AI, with a clear interest in coherent reasoning under uncertainty using general and robust uncertainty models that require no full specification.
本論文の結果は、望ましいギャンブルの集合の理論、つまり部分確率評価を用いた推論のための成長を続けるツールボックスに役立つツールを追加するものです。認識論的無関連性と独立性の特性を用いて、望ましいギャンブルの複数の周辺整合集合を結合集合に結合する方法を調査します。我々は、それらの独立自然拡張と呼ばれるそのような最小の結合の公式を提供し、その主要な特性を研究します。望ましいギャンブルの最大整合集合の独立自然拡張により、望ましいギャンブル集合の強積を定義することができます。最後に、これらの結果を一般化し、認識論的無関連性と独立性の条件付きバージョンにも適用する簡単な方法を探求します。コンピュータプログラムに簡単に実装できるこのようなツールセットを持つことは、完全な仕様を必要としない一般性と堅牢性を備えた不確実性モデルを用いた不確実性下での整合推論に明確な関心を持つAIなどの分野にとって明らかに有益です。
Replanning in Domains with Partial Information and Sensing Actions
部分情報と感知行動を含む領域における再計画
Replanning via determinization is a recent, popular approach for online planning in MDPs. In this paper we adapt this idea to classical, non-stochastic domains with partial information and sensing actions, presenting a new planner: SDR (Sample, Determinize, Replan). At each step we generate a solution plan to a classical planning problem induced by the original problem. We execute this plan as long as it is safe to do so. When this is no longer the case, we replan. The classical planning problem we generate is based on the translation-based approach for conformant planning introduced by Palacios and Geffner. The state of the classical planning problem generated in this approach captures the belief state of the agent in the original problem. Unfortunately, when this method is applied to planning problems with sensing, it yields a non-deterministic planning problem that is typically very large. Our main contribution is the introduction of state sampling techniques for overcoming these two problems. In addition, we introduce a novel, lazy, regression-based method for querying the agent’s belief state during run-time. We provide a comprehensive experimental evaluation of the planner, showing that it scales better than the state-of-the-art CLG planner on existing benchmark problems, but also highlighting its weaknesses with new domains. We also discuss its theoretical guarantees.
決定化による再計画は、MDPにおけるオンラインプランニングにおいて最近よく使われる手法です。本稿では、この考え方を部分情報とセンシングアクションを伴う古典的な非確率的領域に適用し、新しいプランナーであるSDR（Sample, Determinize, Replan）を提示します。各ステップにおいて、元の問題によって誘導された古典的な計画問題に対する解プランを生成します。このプランは、実行が安全である限り実行し、安全でなくなった場合は再プランニングを行います。生成する古典的な計画問題は、PalaciosとGeffnerによって導入されたコンフォーマント計画のための変換ベースのアプローチに基づいています。このアプローチで生成される古典的な計画問題の状態は、元の問題におけるエージェントの信念状態を捉えます。しかしながら、この手法をセンシングを伴う計画問題に適用すると、典型的には非常に大規模な非決定論的計画問題が生成されます。私たちの主な貢献は、これら2つの問題を克服するための状態サンプリング手法の導入です。さらに、実行時にエージェントの信念状態を照会するための、遅延回帰に基づく新しい手法を導入します。このプランナーの包括的な実験的評価を行い、既存のベンチマーク問題において最先端のCLGプランナーよりも優れたスケール性を示すとともに、新しい領域における弱点も明らかにします。また、その理論的な保証についても考察します。
Safe Exploration of State and Action Spaces in Reinforcement Learning
強化学習における状態空間と行動空間の安全な探索
In this paper, we consider the important problem of safe exploration in reinforcement learning. While reinforcement learning is well-suited to domains with complex transition dynamics and high-dimensional state-action spaces, an additional challenge is posed by the need for safe and efficient exploration. Traditional exploration techniques are not particularly useful for solving dangerous tasks, where the trial and error process may lead to the selection of actions whose execution in some states may result in damage to the learning system (or any other system). Consequently, when an agent begins an interaction with a dangerous and high-dimensional state-action space, an important question arises; namely, that of how to avoid (or at least minimize) damage caused by the exploration of the state-action space. We introduce the PI-SRL algorithm which safely improves suboptimal albeit robust behaviors for continuous state and action control tasks and which efficiently learns from the experience gained from the environment. We evaluate the proposed method in four complex tasks: automatic car parking, pole-balancing, helicopter hovering, and business management.
本稿では、強化学習における安全な探索という重要な問題について考察します。強化学習は複雑な遷移ダイナミクスと高次元の状態行動空間を持つ領域に適しているが、安全で効率的な探索の必要性によってさらなる課題が生じる。従来の探索手法は、危険なタスクの解決には特に有用ではありません。試行錯誤のプロセスによって、ある状態では実行が学習システム（あるいは他のシステム）に損害を与える可能性のある行動が選択されてしまう可能性があるからです。その結果、エージェントが危険で高次元の状態-行動空間との相互作用を開始すると、重要な問題が生じます。それは、状態-行動空間の探索によって引き起こされる損害をどのように回避（あるいは少なくとも最小限に抑えるか）するかということです。本稿では、連続的な状態および行動制御タスクにおいて、準最適ではあるもののロバストな行動を安全に改善し、環境から得られる経験から効率的に学習するPI-SRLアルゴリズムを紹介します。提案手法を、自動駐車、ポールバランシング、ヘリコプターホバリング、そして経営管理という4つの複雑なタスクで評価します。
Complexity of Judgment Aggregation
判断集約の計算量
We analyse the computational complexity of three problems in judgment aggregation: (1) computing a collective judgment from a profile of individual judgments (the winner determination problem); (2) deciding whether a given agent can influence the outcome of a judgment aggregation procedure in her favour by reporting insincere judgments (the strategic manipulation problem); and (3) deciding whether a given judgment aggregation scenario is guaranteed to result in a logically consistent outcome, independently from what the judgments supplied by the individuals are (the problem of the safety of the agenda). We provide results both for specific aggregation procedures (the quota rules, the premise-based procedure, and a distance-based procedure) and for classes of aggregation procedures characterised in terms of fundamental axioms.
我々は判断集約における3つの問題の計算複雑性を分析します。すなわち、(1)個々の判断のプロファイルから集合的な判断を計算する問題(勝者決定問題)、(2)特定のエージェントが不誠実な判断を報告することで判断集約手順の結果を自身に有利に左右できるかどうかを判断する問題(戦略的操作問題)、(3)特定の判断集約シナリオが、個々の判断とは無関係に、論理的に一貫した結果をもたらすことが保証されているかどうかを判断する問題(アジェンダの安全性問題)です。我々は、特定の集約手順(割り当てルール、前提に基づく手順、距離に基づく手順)と、基本公理によって特徴付けられる集約手順のクラスの両方について結果を示す。
The Tractability of CSP Classes Defined by Forbidden Patterns
禁制パターンで定義されたCSPクラスの扱いやすさ
The constraint satisfaction problem (CSP) is a general problem central to computer science and artificial intelligence. Although the CSP is NP-hard in general, considerable effort has been spent on identifying tractable subclasses. The main two approaches consider structural properties (restrictions on the hypergraph of constraint scopes) and relational properties (restrictions on the language of constraint relations). Recently, some authors have considered hybrid properties that restrict the constraint hypergraph and the relations simultaneously.Our key contribution is the novel concept of a CSP pattern and classes of problems defined by forbidden patterns (which can be viewed as forbidding generic sub-problems). We describe the theoretical framework which can be used to reason about classes of problems defined by forbidden patterns. We show that this framework generalises certain known hybrid tractable classes.Although we are not close to obtaining a complete characterisation concerning the tractability of general forbidden patterns, we prove a dichotomy in a special case: classes of problems that arise when we can only forbid binary negative patterns (generic sub-problems in which only disallowed tuples are specified). In this case we show that all (finite sets of) forbidden patterns define either polynomial-time solvable or NP-complete classes of instances.
制約充足問題(CSP)は、コンピューター サイエンスと人工知能の中心となる一般的な問題です。CSPは一般にNP困難ですが、扱いやすいサブクラスを特定するためにかなりの労力が費やされてきました。主な2つのアプローチでは、構造的プロパティ(制約スコープのハイパーグラフに対する制限)と関係的プロパティ(制約関係の言語に対する制限)が考慮されます。最近、何人かの著者は、制約ハイパーグラフと関係を同時に制限するハイブリッド特性を検討しました。私たちの主要な貢献は、CSPパターンの新しい概念と、禁制パターンによって定義される問題のクラス(禁制の一般的なサブ問題と見なすことができます)です。禁制パターンによって定義される問題のクラスについて推論するために使用できる理論的枠組みについて説明します。この枠組みにより、既知のハイブリッドの扱いやすいクラスが一般化されることを示します。一般的な禁制パターンの扱いやすさに関する完全な特徴付けはまだ得られていませんが、特殊なケース、つまり、バイナリ負パターン(許可されていないタプルのみが指定されている一般的なサブ問題)のみを禁止できる場合に発生する問題のクラスで二分法を証明します。この場合、すべての(有限の)禁制パターンが、多項式時間で解けるか、NP完全なインスタンスのクラスを定義することを示します。
A New Look at BDDs for Pseudo-Boolean Constraints
擬似ブール制約に対するBDDの新たな視点
Pseudo-Boolean constraints are omnipresent in practical applications, and thus a significant effort has been devoted to the development of good SAT encoding techniques for them. Some of these encodings first construct a Binary Decision Diagram (BDD) for the constraint, and then encode the BDD into a propositional formula. These BDD-based approaches have some important advantages, such as not being dependent on the size of the coefficients, or being able to share the same BDD for representing many constraints.We first focus on the size of the resulting BDDs, which was considered to be an open problem in our research community. We report on previous work where it was proved that there are Pseudo-Boolean constraints for which no polynomial BDD exists. We also give an alternative and simpler proof assuming that NP is different from Co-NP. More interestingly, here we also show how to overcome the possible exponential blowup of BDDs by \emph{coefficient decomposition}. This allows us to give the first polynomial generalized arc-consistent ROBDD-based encoding for Pseudo-Boolean constraints.Finally, we focus on practical issues: we show how to efficiently construct such ROBDDs, how to encode them into SAT with only 2 clauses per node, and present experimental results that confirm that our approach is competitive with other encodings and state-of-the-art Pseudo-Boolean solvers.
擬似ブール制約は実用アプリケーションにおいて遍在するため、それらに対する優れたSATエンコード手法の開発には多大な努力が払われてきた。これらのエンコード手法の中には、まず制約の二分決定図（BDD）を構築し、次にそのBDDを命題論理式にエンコードするものがあります。これらのBDDベースのアプローチには、係数のサイズに依存しない、または多くの制約を表すために同じBDDを共有できるなど、いくつかの重要な利点があります。まず、結果として得られるBDDのサイズに焦点を当てる。これは、私たちの研究コミュニティでは未解決の問題と考えられていた。多項式BDDが存在しない擬似ブール制約が存在することが証明された過去の研究を報告します。また、NPとCo-NPが異なると仮定した場合の、より単純な代替証明も示す。さらに興味深いことに、ここでは\emph{係数分解}によってBDDの指数関数的爆発を克服する方法も示しています。これにより、擬似ブール制約に対する最初の多項式一般化弧無矛盾ROBDDベースのエンコーディングが可能になります。最後に、実用的な問題に焦点を当てます。このようなROBDDを効率的に構築する方法、ノードごとに2つの節のみを使用してROBDDをSATにエンコードする方法を示し、私たちのアプローチが他のエンコーディングや最先端の擬似ブールソルバーと競合できることを確認する実験結果を示します。
Transforming Graph Data for Statistical Relational Learning
統計的関係学習のためのグラフデータの変換
Relational data representations have become an increasingly important topic due to the recent proliferation of network datasets (e.g., social, biological, information networks) and a corresponding increase in the application of Statistical Relational Learning (SRL) algorithms to these domains. In this article, we examine and categorize techniques for transforming graph-based relational data to improve SRL algorithms. In particular, appropriate transformations of the nodes, links, and/or features of the data can dramatically affect the capabilities and results of SRL algorithms. We introduce an intuitive taxonomy for data representation transformations in relational domains that incorporates link transformation and node transformation as symmetric representation tasks. More specifically, the transformation tasks for both nodes and links include (i) predicting their existence, (ii) predicting their label or type, (iii) estimating their weight or importance, and (iv) system- atically constructing their relevant features. We motivate our taxonomy through detailed examples and use it to survey competing approaches for each of these tasks. We also dis- cuss general conditions for transforming links, nodes, and features. Finally, we highlight challenges that remain to be addressed.
近年のネットワークデータセット（社会ネットワーク、生物ネットワーク、情報ネットワークなど）の急増と、それに伴う統計的関係学習（SRL）アルゴリズムのこれらの分野への適用増加により、関係データ表現はますます重要なトピックとなっています。本稿では、グラフベースの関係データを変換してSRLアルゴリズムを改善する手法を検証し、分類します。特に、データのノード、リンク、および／または特徴の適切な変換は、SRLアルゴリズムの機能と結果に劇的な影響を与える可能性があります。本稿では、リンク変換とノード変換を対称的な表現タスクとして組み込んだ、関係領域におけるデータ表現変換のための直感的な分類法を紹介します。より具体的には、ノードとリンクの両方に対する変換タスクには、(i)存在の予測、(ii)ラベルまたはタイプの予測、(iii)重みまたは重要度の推定、(iv)関連する特徴の体系的な構築が含まれます。詳細な例を用いてこの分類法の根拠を示し、各タスクにおける競合アプローチを概観します。また、リンク、ノード、およびフィーチャの変換に関する一般条件についても議論します。最後に、取り組むべき課題についても強調します。
A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing
自然言語処理における推論のための双対分解とラグランジュ緩和法に関するチュートリアル
Dual decomposition, and more generally Lagrangian relaxation, is a classical method for combinatorial optimization; it has recently been applied to several inference problems in natural language processing (NLP). This tutorial gives an overview of the technique. We describe example algorithms, describe formal guarantees for the method, and describe practical issues in implementing the algorithms. While our examples are predominantly drawn from the NLP literature, the material should be of general relevance to inference problems in machine learning. A central theme of this tutorial is that Lagrangian relaxation is naturally applied in conjunction with a broad class of combinatorial algorithms, allowing inference in models that go significantly beyond previous work on Lagrangian relaxation for inference in graphical models.
双対分解、およびより一般的にはラグランジュ緩和は、組合せ最適化の古典的な手法であり、最近では自然言語処理（NLP）におけるいくつかの推論問題に適用されています。このチュートリアルでは、この手法の概要を説明します。サンプルアルゴリズムについて説明し、この手法の形式的な保証について説明し、アルゴリズムの実装における実際的な問題について説明します。ここでの例は主にNLPの文献から引用されていますが、この資料は機械学習の推論問題に一般的に関連するはずです。このチュートリアルの中心的なテーマは、ラグランジュ緩和が幅広い組み合わせアルゴリズムと組み合わせて自然に適用されることで、グラフィカル モデルでの推論におけるラグランジュ緩和に関するこれまでの研究を大幅に超えるモデルでの推論が可能になることです。
Removing Redundant Messages in N-ary BnB-ADOPT
N項BnB-ADOPTにおける冗長メッセージの削除
This note considers how to modify BnB-ADOPT, a well-known algorithm for optimally solving distributed constraint optimization problems, with a double aim: (i) to avoid sending most of the redundant messages and (ii) to handle cost functions of any arity. Some of the messages exchanged by BnB-ADOPT turned out to be redundant. Removing most of the redundant messages increases substantially communication efficiency: the number of exchanged messages is – in most cases – at least three times fewer (keeping the other measures almost unchanged), and termination and optimality are maintained. On the other hand, handling n-ary cost functions was addressed in the original work, but the presence of thresholds makes their practical usage more complex. Both issues – removing most of the redundant messages and efficiently handling n-ary cost functions – can be combined, producing the new version BnB-ADOPT+. Experimentally, we show the benefits of this version over the original one.
本稿では、分散制約最適化問題を最適に解くためのよく知られたアルゴリズムであるBnB-ADOPTの修正方法について考察します。その目的は、(i)冗長なメッセージの送信をほとんど回避すること、および(ii)任意のアリティのコスト関数を処理することです。BnB-ADOPTによって交換されるメッセージの中には冗長なものがいくつかあることが判明しました。冗長メッセージのほとんどを削除すると、通信効率が大幅に向上します。交換されるメッセージ数は、ほとんどの場合、少なくとも3分の1に減少します（他の指標はほとんど変化しません）。また、終了性と最適性は維持されます。一方、n元コスト関数の処理は元の研究で取り上げられていましたが、閾値の存在により、実際の使用はより複雑になります。冗長メッセージのほとんどを削除し、n元コスト関数を効率的に処理するという両方の問題を組み合わせることで、新しいバージョンBnB-ADOPT+を作成できます。実験的に、このバージョンが元のバージョンよりも優れていることを示します。
Generating Approximate Solutions to the TTP using a Linear Distance Relaxation
線形距離緩和法を用いたTTPの近似解の生成
In some domestic professional sports leagues, the home stadiums are located in cities connected by a common train line running in one direction. For these instances, we can incorporate this geographical information to determine optimal or nearly-optimal solutions to the n-team Traveling Tournament Problem (TTP), an NP-hard sports scheduling problem whose solution is a double round-robin tournament schedule that minimizes the sum total of distances traveled by all n teams.We introduce the Linear Distance Traveling Tournament Problem (LD-TTP), and solve it for n=4 and n=6, generating the complete set of possible solutions through elementary combinatorial techniques. For larger n, we propose a novel “expander construction” that generates an approximate solution to the LD-TTP. For n congruent to 4 modulo 6, we show that our expander construction produces a feasible double round-robin tournament schedule whose total distance is guaranteed to be no worse than 4/3 times the optimal solution, regardless of where the n teams are located. This 4/3-approximation for the LD-TTP is stronger than the currently best-known ratio of 5/3 + epsilon for the general TTP.We conclude the paper by applying this linear distance relaxation to general (non-linear) n-team TTP instances, where we develop fast approximate solutions by simply “assuming” the n teams lie on a straight line and solving the modified problem. We show that this technique surprisingly generates the distance-optimal tournament on all benchmark sets on 6 teams, as well as close-to-optimal schedules for larger n, even when the teams are located around a circle or positioned in three-dimensional space.
国内プロスポーツリーグの中には、ホームスタジアムが一方向に走る共通の鉄道路線で結ばれた都市に所在するものがあります。このような場合、この地理情報を取り入れることで、nチーム移動トーナメント問題（TTP）の最適解、あるいは近似解を求めることができます。TTPはNP困難なスポーツスケジューリング問題であり、その解はnチームすべての移動距離の合計を最小化するダブルラウンドロビン方式のトーナメントスケジュールです。本研究では、線形距離移動トーナメント問題（LD-TTP）を提示し、n=4およびn=6の場合にこれを解き、基本的な組合せ論的手法を用いて可能な解の完全な集合を生成します。より大きなnの場合、LD-TTPの近似解を生成する新しい「エクスパンダー構築」を提案します。nが6を法として4と合同な場合、このエクスパンダー構築によって、nチームの所在地に関わらず、総移動距離が最適解の4/3倍以下になることが保証される、実行可能なダブルラウンドロビン方式のトーナメントスケジュールが生成されることを示します。LD-TTPのこの4/3近似は、一般的なTTPにおいて現在最もよく知られている5/3 +イプシロン比よりも強力です。本論文では、この線形距離緩和を一般的な（非線形）nチームTTPインスタンスに適用することで結論付けます。ここでは、nチームが直線上に並んでいると単純に「仮定」し、修正された問題を解くことで、高速な近似解を開発します。この手法は、6チームのすべてのベンチマークセットにおいて距離最適トーナメントを生成し、チームが円周上に配置されている場合や3次元空間に配置されている場合であっても、より大きなnに対して最適に近いスケジュールを生成することを驚くべき方法で示します。
Reasoning over Ontologies with Hidden Content: The Import-by-Query Approach
隠れコンテンツを含むオントロジー上の推論：クエリによるインポートアプローチ
There is currently a growing interest in techniques for hiding parts of the signature of an ontology Kh that is being reused by another ontology Kv. Towards this goal, in this paper we propose the import-by-query framework, which makes the content of Kh accessible through a limited query interface. If Kv reuses the symbols from Kh in a certain restricted way, one can reason over Kv U Kh by accessing only Kv and the query interface. We map out the landscape of the import-by-query problem. In particular, we outline the limitations of our framework and prove that certain restrictions on the expressivity of Kh and the way in which Kv reuses symbols from Kh are strictly necessary to enable reasoning in our setting. We also identify cases in which reasoning is possible and we present suitable import-by-query reasoning algorithms.
現在、あるオントロジーKhのシグネチャの一部を別のオントロジーKvによって再利用されている状態で隠蔽する技術への関心が高まっています。この目標に向けて、本稿では、限定されたクエリインターフェースを介してKhの内容にアクセスできるようにする、import-by-queryフレームワークを提案します。KvがKhのシンボルを特定の制限された方法で再利用する場合、Kvとクエリインターフェースのみにアクセスすることで、Kv U Khを推論できます。import-by-query問題のランドスケープを図解します。特に、このフレームワークの限界を概説し、Khの表現力とKvがKhからシンボルを再利用する方法に対する特定の制限が、この設定で推論を可能にするために厳密に必要であることを証明します。また、推論が可能なケースを特定し、適切なimport-by-query推論アルゴリズムを提示します。
Coalition Structure Generation over Graphs
グラフ上の連携構造生成
We give the analysis of the computational complexity of coalition structure generation over graphs. Given an undirected graph G = (N,E) and a valuation function v : P(N) → R over the subsets of nodes, the problem is to find a partition of N into connected subsets, that maximises the sum of the components values. This problem is generally NPcomplete; in particular, it is hard for a defined class of valuation functions which are independent of disconnected membersthat is, two nodes have no effect on each others marginal con- tribution to their vertex separator. Nonetheless, for all such functions we provide bounds on the complexity of coalition structure generation over general and minorfree graphs. Our proof is constructive and yields algorithms for solving corresponding instances of the problem. Furthermore, we derive linear time bounds for graphs of bounded treewidth. However, as we show, the problem remains NPcomplete for planar graphs, and hence, for any K_k minorfree graphs where k ≥ 5. Moreover, a 3-SAT problem with m clauses can be represented by a coalition structure generation problem over a planar graph with O(m^2) nodes. Importantly, our hardness result holds for a particular subclass of valuation functions, termed edge sum, where the value of each subset of nodes is simply determined by the sum of given weights of the edges in the induced subgraph.
グラフ上の提携構造生成の計算複雑性について分析を行う。無向グラフG = (N,E)と評価関数vが与えられたとします。: P(N)→Rをノードのサブセット上で展開する場合、問題はNを連結サブセットに分割し、構成要素の値の合計を最大化する問題です。この問題は一般にNP完全です。特に、切断された要素から独立な、つまり2つのノードが互いの頂点セパレータへの周辺寄与に影響を与えないような、定義されたクラスの評価関数に対しては困難です。しかしながら、そのようなすべての関数に対して、一般グラフおよびマイナーフリーグラフ上の提携構造生成の計算量に関する上限を示します。私たちの証明は構成的であり、問題の対応するインスタンスを解くアルゴリズムを提供します。さらに、木幅が制限されたグラフの線形時間上限を導出します。しかし、ここで示すように、この問題は平面グラフ、つまりk≥5の任意のK_kマイナーフリーグラフに対してNP完全のままです。さらに、m個の節を持つ3-SAT問題は、O(m^2)個のノードを持つ平面グラフ上の提携構造生成問題として表現できます。重要なのは、私たちの困難性の結果です。は、エッジ和と呼ばれる評価関数の特定のサブクラスに対して成り立ち、そこでは、各ノードのサブセットの値は、誘導されたサブグラフ内のエッジの与えられた重みの合計によって単純に決定されます。
Towards Unsupervised Learning of Temporal Relations between Events
事象間の時間的関係の教師なし学習に向けて
Automatic extraction of temporal relations between event pairs is an important task for several natural language processing applications such as Question Answering, Information Extraction, and Summarization. Since most existing methods are supervised and require large corpora, which for many languages do not exist, we have concentrated our efforts to reduce the need for annotated data as much as possible. This paper presents two different algorithms towards this goal. The first algorithm is a weakly supervised machine learning approach for classification of temporal relations between events. In the first stage, the algorithm learns a general classifier from an annotated corpus. Then, inspired by the hypothesis of “one type of temporal relation per discourse”, it extracts useful information from a cluster of topically related documents. We show that by combining the global information of such a cluster with local decisions of a general classifier, a bootstrapping cross-document classifier can be built to extract temporal relations between events. Our experiments show that without any additional annotated data, the accuracy of the proposed algorithm is higher than that of several previous successful systems. The second proposed method for temporal relation extraction is based on the expectation maximization (EM) algorithm. Within EM, we used different techniques such as a greedy best-first search and integer linear programming for temporal inconsistency removal. We think that the experimental results of our EM based algorithm, as a first step toward a fully unsupervised temporal relation extraction method, is encouraging.
イベントペア間の時間的関係の自動抽出は、質問応答、情報抽出、要約といった様々な自然言語処理アプリケーションにとって重要なタスクです。既存の手法の多くは教師あり学習であり、多くの言語では存在しない大規模なコーパスを必要とするため、我々はアノテーション付きデータの必要性を可能な限り低減することに注力してきました。本論文では、この目標に向けた2つの異なるアルゴリズムを紹介します。1つ目のアルゴリズムは、イベント間の時間的関係を分類するための弱教師あり機械学習アプローチです。第1段階では、アルゴリズムはアノテーション付きコーパスから汎用分類器を学習します。次に、「談話ごとに1種類の時系列関係」という仮説に着想を得て、トピック的に関連する文書のクラスターから有用な情報を抽出します。このようなクラスターのグローバル情報と、一般的な分類器のローカルな決定を組み合わせることで、イベント間の時系列関係を抽出するためのブートストラッピング型文書間分類器を構築できることを示す。実験では、追加の注釈データなしでも、提案アルゴリズムの精度は、これまでのいくつかの成功したシステムよりも高いことが示されました。時系列関係抽出のための2つ目の提案手法は、期待最大化（EM）アルゴリズムに基づく。EMでは、時間的な矛盾の除去に、貪欲な最良優先探索や整数線形計画法などの様々な手法を用いた。このEMベースのアルゴリズムの実験結果は、完全な教師なし時系列関係抽出法への第一歩として、有望であると考えています。
Interactions between Knowledge and Time in a First-Order Logic for Multi-Agent Systems: Completeness Results
マルチエージェントシステムのための一階述語論理における知識と時間の相互作用：完全性結果
We investigate a class of first-order temporal-epistemic logics for reasoning about multi-agent systems. We encode typical properties of systems including perfect recall, synchronicity, no learning, and having a unique initial state in terms of variants of quantified interpreted systems, a first-order extension of interpreted systems. We identify several monodic fragments of first-order temporal-epistemic logic and show their completeness with respect to their corresponding classes of quantified interpreted systems.
本研究では、マルチエージェントシステムの推論のための一階時相認識論的論理の一群を調査します。システムの典型的な特性、例えば完全想起、同期性、学習なし、一意な初期状態を持つことなどを、一階解釈システムの拡張である量化解釈システムの変種を用いて符号化します。一階時相認識論的論理のいくつかの単項的断片を特定します。時間認識論的論理を記述し、対応する量化解釈システムのクラスに関してその完全性を示します。