BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm
BnB-ADOPT：非同期分岐限定DCOPアルゴリズム
Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. A DCOP problem is a problem where several agents coordinate their values such that the sum of the resulting constraint costs is minimal. It is often desirable to solve DCOP problems with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search algorithm that uses the message-passing and communication framework of ADOPT (Modi, Shen, Tambe, & Yokoo, 2005), a well known memory-bounded asynchronous DCOP search algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a memory-bounded synchronous DCOP search algorithm, for most of these DCOP problems. Additionally, it is often desirable to find bounded-error solutions for DCOP problems within a reasonable amount of time since finding cost-minimal solutions is NP-hard. The existing bounded-error approximation mechanism allows users only to specify an absolute error bound on the solution cost but a relative error bound is often more intuitive. Thus, we present two new bounded-error approximation mechanisms that allow for relative error bounds and implement them on top of BnB-ADOPT.
分散制約最適化（DCOP）問題は、エージェント調整問題を定式化し、解くための一般的な方法です。DCOP問題とは、複数のエージェントがそれぞれの値を調整し、結果として生じる制約コストの合計が最小となるようにする問題です。DCOP問題は、メモリ制限のある非同期アルゴリズムを用いて解くことが望ましい場合が多い。我々は、よく知られたメモリ制限非同期DCOP探索アルゴリズムであるADOPT (Modi, Shen, Tambe, & Yokoo, 2005)のメッセージパッシングおよび通信フレームワークを使用し、ADOPTの探索戦略を最良優先探索から深さ優先の分岐限定探索に変更した、メモリ制限非同期DCOP探索アルゴリズムである分岐限定ADOP (BnB-ADOPT)を紹介します。実験結果によると、BnB-ADOPTは、さまざまな大規模DCOP問題に対してADOPよりも最大1桁高速にコスト最小解を見つけ、これらのDCOP問題のほとんどに対してメモリ制限同期DCOP探索アルゴリズムであるNCBBと同程度の速度です。さらに、コスト最小解を見つけることはNP困難であるため、DCOP問題に対して妥当な時間内に誤差が制限された解を見つけることがしばしば望まれます。既存の誤差が制限された近似メカニズムでは、ユーザーは解のコストに対して絶対的な誤差限界しか指定できませんが、相対的な誤差限界の方が多くの場合より直感的です。そこで、相対的な誤差境界を考慮し、BnB-ADOPT上に実装する2つの新しい境界誤差近似メカニズムを紹介します。
Automatic Induction of Bellman-Error Features for Probabilistic Planning
確率的計画のためのベルマン誤差特性の自動誘導
Domain-specific features are important in representing problem structure throughout machine learning and decision-theoretic planning. In planning, once state features are provided, domain-independent algorithms such as approximate value iteration can learn weighted combinations of those features that often perform well as heuristic estimates of state value (e.g., distance to the goal). Successful applications in real-world domains often require features crafted by human experts. Here, we propose automatic processes for learning useful domain-specific feature sets with little or no human intervention. Our methods select and add features that describe state-space regions of high inconsistency in the Bellman equation (statewise Bellman error) during approximate value iteration. Our method can be applied using any real-valued-feature hypothesis space and corresponding learning method for selecting features from training sets of state-value pairs. We evaluate the method with hypothesis spaces defined by both relational and propositional feature languages, using nine probabilistic planning domains. We show that approximate value iteration using a relational feature space performs at the state-of-the-art in domain-independent stochastic relational planning. Our method provides the first domain-independent approach that plays Tetris successfully (without human-engineered features).
ドメイン固有の特徴は、機械学習と意思決定理論に基づくプランニングにおいて、問題構造を表現する上で重要です。プランニングにおいて、状態特徴が提供されると、近似値反復法などのドメイン非依存アルゴリズムは、これらの特徴の重み付き組み合わせを学習することができ、これは状態値（例えば、ゴールまでの距離）のヒューリスティック推定として優れた性能を示すことがよくあります。現実世界のドメインにおけるアプリケーションの成功には、多くの場合、人間の専門家によって作成された特徴が必要です。本稿では、人間の介入をほとんど、あるいは全く必要とせずに、有用なドメイン固有の特徴セットを学習するための自動プロセスを提案します。本手法は、近似値反復法において、ベルマン方程式における高い不整合（状態ごとのベルマン誤差）を示す状態空間領域を記述する特徴を選択および追加します。本手法は、任意の実数値特徴仮説空間と、状態値ペアのトレーニングセットから特徴を選択するための対応する学習手法を用いて適用できます。我々は、9つの確率的プランニングドメインを用いて、関係型および命題型の両方の特徴言語で定義された仮説空間を用いて本手法を評価した。関係型特徴空間を用いた近似値反復法が、ドメイン非依存の確率的関係プランニングにおいて最先端の性能を発揮することを示す。本手法は、テトリスを（人間工学的特徴なしで）正常にプレイできる初めてのドメイン非依存アプローチを提供します。
Non-Transferable Utility Coalitional Games via Mixed-Integer Linear Constraints
混合整数線形制約による移転不可能効用連合ゲーム
Coalitional games serve the purpose of modeling payoff distribution problems in scenarios where agents can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. In the classical Transferable Utility (TU) setting, coalition worths can be freely distributed amongst agents. However, in several application scenarios, this is not the case and the Non-Transferable Utility setting (NTU) must be considered, where additional application-oriented constraints are imposed on the possible worth distributions.In this paper, an approach to define NTU games is proposed which is based on describing allowed distributions via a set of mixed-integer linear constraints applied to an underlying TU game. It is shown that such games allow non-transferable conditions on worth distributions to be specified in a natural and succinct way. The properties and the relationships among the most prominent solution concepts for NTU games that hold when they are applied on (mixed-integer) constrained games are investigated. Finally, a thorough analysis is carried out to assess the impact of issuing constraints on the computational complexity of some of these solution concepts.
提携ゲームは、エージェントが単独で行動するよりも高い価値を得るために提携を形成することで協力できるシナリオにおける利得分配問題をモデル化することを目的としています。従来の移転可能効用（TU）設定では、提携価値はエージェント間で自由に分配できます。しかし、いくつかの応用シナリオではそうではなく、移転不可能効用（NTU）設定を考慮する必要があります。NTU設定では、可能な価値分配にアプリケーション指向の追加制約が課されます。本稿では、基礎となるTUゲームに適用される一連の混合整数線形制約を介して許容される分配を記述することに基づく、NTUゲームを定義するアプローチを提案します。このようなゲームでは、価値分配に関する移転不可能な条件を自然かつ簡潔な方法で指定できることが示されます。NTUゲームの最も有力な解概念を（混合整数）制約ゲームに適用した場合に成立する特性とそれらの関係を調査します。最後に、制約の発行がこれらのソリューションコンセプトの計算複雑性に与える影響を評価するために、徹底的な分析を実施します。
Cause Identification from Aviation Safety Incident Reports via Weakly Supervised Semantic Lexicon Construction
弱教師付き意味語彙構築による航空安全インシデント報告書からの原因特定
The Aviation Safety Reporting System collects voluntarily submitted reports on aviation safety incidents to facilitate research work aiming to reduce such incidents. To effectively reduce these incidents, it is vital to accurately identify why these incidents occurred. More precisely, given a set of possible causes, or shaping factors, this task of cause identification involves identifying all and only those shaping factors that are responsible for the incidents described in a report. We investigate two approaches to cause identification. Both approaches exploit information provided by a semantic lexicon, which is automatically constructed via Thelen and Riloff’s Basilisk framework augmented with our linguistic and algorithmic modifications. The first approach labels a report using a simple heuristic, which looks for the words and phrases acquired during the semantic lexicon learning process in the report. The second approach recasts cause identification as a text classification problem, employing supervised and transductive text classification algorithms to learn models from incident reports labeled with shaping factors and using the models to label unseen reports. Our experiments show that both the heuristic-based approach and the learning-based approach (when given sufficient training data) outperform the baseline system significantly.
航空安全報告システムは、航空安全インシデントに関する自主的に提出された報告書を収集し、インシデント削減を目指す研究を促進しています。これらのインシデントを効果的に削減するには、インシデントが発生した理由を正確に特定することが不可欠です。より正確には、考えられる原因、つまり形成要因の集合が与えられた場合、この原因特定作業では、報告書に記載されているインシデントの原因となるすべての形成要因のみを特定します。私たちは原因特定のための2つのアプローチを検討します。どちらのアプローチも、ThelenとRiloffのBasiliskフレームワークに、私たちの言語的およびアルゴリズム的な修正を加えて自動的に構築された意味語彙集によって提供される情報を利用します。最初のアプローチは、意味語彙学習プロセス中にレポート内で獲得された単語やフレーズを探す単純なヒューリスティックを用いてレポートにラベルを付けるものです。2つ目のアプローチは、原因特定をテキスト分類問題として捉え直し、教師ありおよびトランスダクティブなテキスト分類アルゴリズムを用いて、シェーピングファクターでラベル付けされたインシデントレポートからモデルを学習し、そのモデルを用いて未知レポートにラベル付けします。実験では、ヒューリスティックベースのアプローチと学習ベースのアプローチの両方（十分なトレーニングデータが与えられた場合）が、ベースラインシステムを大幅に上回る性能を示すことが示されました。
Logical Foundations of RDF(S) with Datatypes
データ型付きRDF(S)の論理的基礎
The Resource Description Framework (RDF) is a Semantic Web standard that provides a data language, simply called RDF, as well as a lightweight ontology language, called RDF Schema. We investigate embeddings of RDF in logic and show how standard logic programming and description logic technology can be used for reasoning with RDF. We subsequently consider extensions of RDF with datatype support, considering D entailment, defined in the RDF semantics specification, and D* entailment, a semantic weakening of D entailment, introduced by ter Horst. We use the embeddings and properties of the logics to establish novel upper bounds for the complexity of deciding entailment. We subsequently establish two novel lower bounds, establishing that RDFS entailment is PTime-complete and that simple-D entailment is coNP-hard, when considering arbitrary datatypes, both in the size of the entailing graph. The results indicate that RDFS may not be as lightweight as one may expect.
リソース記述フレームワーク（RDF）は、単にRDFと呼ばれるデータ言語と、RDFスキーマと呼ばれる軽量オントロジー言語を提供するセマンティックWeb標準です。我々は、RDFの論理への埋め込みを調査し、標準的な論理プログラミングと記述論理技術をRDFを用いた推論にどのように使用できるかを示す。次に、RDF意味論仕様で定義されているD含意と、ter Horstによって導入されたD含意の意味的弱化であるD*含意を考慮し、データ型サポートを備えたRDFの拡張を検討します。我々は、埋め込みと論理の特性を用いて、含意を決定する複雑さの新たな上限を確立します。さらに、任意のデータ型を考慮した場合、含意グラフのサイズにおいて、RDFS含意はPTime完全であり、単純D含意はcoNP困難であるという2つの新たな下限を確立します。結果は、RDFSが期待されるほど軽量ではない可能性があることを示唆しています。
Algorithms for Closed Under Rational Behavior (CURB) Sets
クローズドな議論のためのアルゴリズム有理的行動（CURB）集合の仮定
We provide a series of algorithms demonstrating that solutions according to the fundamental game-theoretic solution concept of closed under rational behavior (CURB) sets in two-player, normal-form games can be computed in polynomial time (we also discuss extensions to n-player games). First, we describe an algorithm that identifies all of a players best responses conditioned on the belief that the other player will play from within a given subset of its strategy space. This algorithm serves as a subroutine in a series of polynomial-time algorithms for finding all minimal CURB sets, one minimal CURB set, and the smallest minimal CURB set in a game. We then show that the complexity of finding a Nash equilibrium can be exponential only in the size of a games smallest CURB set. Related to this, we show that the smallest CURB set can be an arbitrarily small portion of the game, but it can also be arbitrarily larger than the supports of its only enclosed Nash equilibrium. We test our algorithms empirically and find that most commonly studied academic games tend to have either very large or very small minimal CURB sets.
我々は、2人プレイの通常形式ゲームにおける合理的行動の下で閉じた(CURB)集合という基本的なゲーム理論的解法の概念に従った解が、多項式時間で計算できることを実証する一連のアルゴリズムを提供する(また、n人プレイゲームへの拡張についても議論する)。まず、他のプレイヤーが戦略空間の特定のサブセット内からプレイするという信念を条件として、プレイヤーの最善の応答をすべて特定するアルゴリズムについて説明します。このアルゴリズムは、ゲーム内のすべての最小CURB集合、1つの最小CURB集合、および最小の最小CURB集合を見つけるための一連の多項式時間アルゴリズムのサブルーチンとして機能させる。次に、ナッシュ均衡を見つける複雑さは、ゲームの最小CURB集合のサイズに対してのみ指数関数的になる可能性があることを示す。これに関連して、最小のCURB集合はゲームの任意の小さな部分になり得るが、その唯一の閉じたナッシュ均衡のサポートよりも任意に大きくなる可能性があることを示す。我々はアルゴリズムを経験的にテストし、最も一般的に研究されている学術的ゲームは、最小CURB集合が非常に大きいか非常に小さい傾向があることを発見した。
Change in Abstract Argumentation Frameworks: Adding an Argument
抽象的議論フレームワークの変化：議論の追加
In this paper, we address the problem of change in an abstract argumentation system. We focus on a particular change: the addition of a new argument which interacts with previous arguments. We study the impact of such an addition on the outcome of the argumentation system, more particularly on the set of its extensions. Several properties for this change operation are defined by comparing the new set of extensions to the initial one, these properties are called structural when the comparisons are based on set-cardinality or set-inclusion relations. Several other properties are proposed where comparisons are based on the status of some particular arguments: the accepted arguments; these properties refer to the evolution of this status during the change, e.g., Monotony and Priority to Recency. All these properties may be more or less desirable according to specific applications. They are studied under two particular semantics: the grounded and preferred semantics.
本稿では、抽象的な議論システムにおける変更の問題を扱う。特に、以前の議論と相互作用する新しい議論の追加という特定の変更に焦点を当てる。このような追加が議論システムの結果、特にその拡張セットに与える影響を調べる。この変更操作のいくつかの特性は、新しい拡張セットを最初の拡張セットと比較することによって定義されます。これらの特性は、比較が集合濃度または集合包含関係に基づく場合、構造的と呼ばれます。他のいくつかの特性は、いくつかの特定の議論の状態、すなわち受け入れられた議論の状態に基づく比較で提案されます。これらの特性は、変更中のこの状態の進化を参照します。たとえば、単調性や新しさへの優先順位などです。これらすべての特性は、特定のアプリケーションに応じて、多かれ少なかれ望ましい可能性があります。これらは、グラウンデッド セマンティクスとプリファード セマンティクスという2つの特定のセマンティクスの下で調べられます。
A Minimum Relative Entropy Principle for Learning and Acting
学習と行動のための最小相対エントロピー原理
This paper proposes a method to construct an adaptive agent that is universal with respect to a given class of experts, where each expert is designed specifically for a particular environment. This adaptive control problem is formalized as the problem of minimizing the relative entropy of the adaptive agent from the expert that is most suitable for the unknown environment. If the agent is a passive observer, then the optimal solution is the well-known Bayesian predictor. However, if the agent is active, then its past actions need to be treated as causal interventions on the I/O stream rather than normal probability conditions. Here it is shown that the solution to this new variational problem is given by a stochastic controller called the Bayesian control rule, which implements adaptive behavior as a mixture of experts. Furthermore, it is shown that under mild assumptions, the Bayesian control rule converges to the control law of the most suitable expert.
本論文では、各エキスパートが特定の環境向けに特別に設計されている、特定のエキスパートクラスに関して普遍的な適応型エージェントを構築する手法を提案します。この適応制御問題は、未知の環境に最も適したエキスパートに対する適応型エージェントの相対エントロピーを最小化する問題として定式化されます。エージェントが受動的な観察者である場合、最適解はよく知られたベイズ予測器です。しかし、エージェントが能動的な場合、その過去の行動は、正規確率条件ではなく、I/Oストリームへの因果的介入として扱う必要があります。本稿では、この新しい変分問題の解が、ベイズ制御則と呼ばれる確率制御器によって与えられることを示す。この制御器は、複数のエキスパートを混合することで適応行動を実現します。さらに、弱い仮定の下では、ベイズ制御則は最も適切なエキスパートの制御則に収束することを示す。
Resource-Driven Mission-Phasing Techniques for Constrained Agents in Stochastic Environments
確率的環境における制約付きエージェントのためのリソース駆動型ミッションフェーズ化手法
Because an agent’s resources dictate what actions it can possibly take, it should plan which resources it holds over time carefully, considering its inherent limitations (such as power or payload restrictions), the competing needs of other agents for the same resources, and the stochastic nature of the environment. Such agents can, in general, achieve more of their objectives if they can use — and even create — opportunities to change which resources they hold at various times. Driven by resource constraints, the agents could break their overall missions into an optimal series of phases, optimally reconfiguring their resources at each phase, and optimally using their assigned resources in each phase, given their knowledge of the stochastic environment.In this paper, we formally define and analyze this constrained, sequential optimization problem in both the single-agent and multi-agent contexts. We present a family of mixed integer linear programming (MILP) formulations of this problem that can optimally create phases (when phases are not predefined) accounting for costs and limitations in phase creation. Because our formulations multaneously also find the optimal allocations of resources at each phase and the optimal policies for using the allocated resources at each phase, they exploit structure across these coupled problems. This allows them to find solutions significantly faster(orders of magnitude faster in larger problems) than alternative solution techniques, as we demonstrate empirically.
エージェントのリソースはエージェントが実行できる行動を決定するため、エージェントは自身の固有の制限（電力やペイロードの制限など）、同じリソースに対する他のエージェントの競合するニーズ、そして環境の確率的性質を考慮し、時間の経過とともにどのリソースを保持するかを慎重に計画する必要があります。このようなエージェントは、様々な時点で保持するリソースを変更する機会を利用（さらには創出）できれば、一般的にはより多くの目的を達成できます。リソース制約に基づいて、エージェントは全体のミッションを最適な一連のフェーズに分割し、各フェーズでリソースを最適に再構成し、確率的環境に関する知識に基づいて各フェーズで割り当てられたリソースを最適に使用することができます。本稿では、この制約付き逐次最適化問題を、シングルエージェントとマルチエージェントの両方のコンテキストで正式に定義し、分析します。我々は、この問題に対する混合整数線形計画法（MILP）による定式化のファミリーを提示します。これらの定式化は、フェーズ作成のコストと制限を考慮し、フェーズを最適に作成することができます。我々の定式化は、各フェーズにおける最適なリソース割り当てと、各フェーズで割り当てられたリソースを使用するための最適なポリシーも同時に発見するため、これらの連成問題全体の構造を活用します。これにより、我々が実証的に証明するように、他の解法手法よりも大幅に高速に（大規模な問題では桁違いに高速に）解を見つけることができます。
Approximate Model-Based Diagnosis Using Greedy Stochastic Search
貪欲確率的探索を用いた近似モデルベース診断
We propose a StochAstic Fault diagnosis AlgoRIthm, called SAFARI, which trades off guarantees of computing minimal diagnoses for computational efficiency. We empirically demonstrate, using the 74XXX and ISCAS-85 suites of benchmark combinatorial circuits, that SAFARI achieves several orders-of-magnitude speedup over two well-known deterministic algorithms, CDA* and HA*, for multiple-fault diagnoses; further, SAFARI can compute a range of multiple-fault diagnoses that CDA* and HA* cannot. We also prove that SAFARI is optimal for a range of propositional fault models, such as the widely-used weak-fault models (models with ignorance of abnormal behavior). We discuss the optimality of SAFARI in a class of strong-fault circuit models with stuck-at failure modes. By modeling the algorithm itself as a Markov chain, we provide exact bounds on the minimality of the diagnosis computed. SAFARI also displays strong anytime behavior, and will return a diagnosis after any non-trivial inference time.
我々は、最小診断を計算する保証と計算効率をトレードオフする、確率的故障診断アルゴリズムSAFARIを提案します。74XXXおよびISCAS-85ベンチマーク組み合わせ回路スイートを使用して、SAFARIが多重故障診断において2つのよく知られた決定論的アルゴリズムCDA*およびHA*よりも数桁高速化することを実証します。さらに、SAFARIはCDA*やHA*では計算できないさまざまな多重故障診断を計算できます。また、広く使用されている弱故障モデル(異常な動作を無視するモデル)などのさまざまな命題故障モデルに対してSAFARIが最適であることも証明します。縮退故障モードを持つ強故障回路モデルのクラスにおけるSAFARIの最適性について議論します。アルゴリズム自体をマルコフ連鎖としてモデル化することにより、計算される診断の最小性の厳密な境界を提供します。SAFARIは強力な「いつでも」動作も示し、ある程度の推論時間が経過した後には診断結果を返します。
Mixed Strategies in Combinatorial Agency
組み合わせエージェンシーにおける混合戦略
In many multiagent domains a set of agents exert effort towards a joint outcome, yet the individual effort levels cannot be easily observed. A typical example for such a scenario is routing in communication networks, where the sender can only observe whether the packet reached its destination, but often has no information about the actions of the intermediate routers, which influences the final outcome. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper we devise and study a basic ”combinatorial agency” model for this setting, where the principal is restricted to inducing a pure Nash equilibrium. Here we study various implications of this restriction. First, we show that, in contrast to the case of observable efforts, inducing a mixed-strategies equilibrium may be beneficial for the principal. Second, we present a sufficient condition for technologies for which no gain can be generated. Third, we bound the principal’s gain for various families of technologies. Finally, we study the robustness of mixed equilibria to coalitional deviations and the computational hardness of the optimal mixed equilibria.
多くのマルチエージェント領域において、エージェントの集合は共通の結果に向けて努力しますが、個々の努力レベルは容易に観察できません。このようなシナリオの典型的な例として、通信ネットワークにおけるルーティングが挙げられます。送信者はパケットが宛先に到達したかどうかしか観察できず、最終結果に影響を与える中間ルーターの行動に関する情報を持たない場合が多くあります。本稿では、プリンシパルがエージェントのチームを動機付ける必要がある状況を検討します。エージェントのチームの隠れた努力の組み合わせが、確率的に結果を決定します。関連論文では、この状況に対する基本的な「組合せエージェンシー」モデルを考案し、検討します。このモデルでは、プリンシパルは純粋ナッシュ均衡を誘導することしかできません。本稿では、この制限の様々な意味合いを検討します。まず、観測可能な努力の場合とは対照的に、混合戦略均衡を誘導することがプリンシパルにとって有益となる可能性があることを示す。次に、利得を生み出せない技術に対する十分条件を提示します。最後に、様々な技術群におけるプリンシパル利得の上限を示す。最後に、混合均衡の提携偏差に対する堅牢性と、最適な混合均衡の計算困難性を検証します。
Fast Set Bounds Propagation Using a BDD-SAT Hybrid
BDD-SATハイブリッドを用いた高速境界伝播
Binary Decision Diagram (BDD) based set bounds propagation is a powerful approach to solving set-constraint satisfaction problems. However, prior BDD based techniques in- cur the significant overhead of constructing and manipulating graphs during search. We present a set-constraint solver which combines BDD-based set-bounds propagators with the learning abilities of a modern SAT solver. Together with a number of improvements beyond the basic algorithm, this solver is highly competitive with existing propagation based set constraint solvers.
二分決定図（BDD）に基づく集合境界伝播法は、集合制約充足問題を解決するための強力なアプローチです。しかし、従来のBDDベースの手法では、探索中にグラフを構築および操作するという大きなオーバーヘッドが発生していました。本稿では、BDDベースのセット境界プロパゲーターと最新のSATソルバーの学習能力を組み合わせたセット制約ソルバーを紹介します。基本アルゴリズムに加え、数々の改良を加えることで、このソルバーは既存のプロパゲーションベースのセット制約ソルバーと高い競争力を発揮します。
Developing Approaches for Solving a Telecommunications Feature Subscription Problem
電気通信機能サブスクリプション問題の解決手法の開発
Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their service. The configuration of a feature subscription involves choosing and sequencing features from a catalogue and is subject to constraints that prevent undesirable feature interactions at run-time. When the subscription requested by a user is inconsistent, one problem is to find an optimal relaxation, which is a generalisation of the feedback vertex set problem on directed graphs, and thus it is an NP-hard task. We present several constraint programming formulations of the problem. We also present formulations using partial weighted maximum Boolean satisfiability and mixed integer linear programming. We study all these formulations by experimentally comparing them on a variety of randomly generated instances of the feature subscription problem.
通話制御機能（転送、ボイスメールなど）は、ユーザーがオフラインで加入してサービスをパーソナライズできる基本的なオプションです。機能サブスクリプションの設定には、カタログから機能を選択し、順序付ける作業が含まれ、実行時に望ましくない機能の相互作用を防ぐ制約が適用されます。ユーザーが要求したサブスクリプションに一貫性がない場合、最適な緩和策を見つけることが一つの問題となります。これは、有向グラフ上のフィードバック頂点集合問題の一般化であり、NP困難なタスクです。本稿では、この問題の制約プログラミングによる定式化をいくつか示します。また、部分重み付き最大ブール充足可能性法と混合整数線形計画法を用いた定式化も示します。これらのすべての定式化を、機能サブスクリプション問題のさまざまなランダムに生成されたインスタンスで実験的に比較することにより、検証します。
Grounding FO and FO(ID) with Bounds
境界を用いたFOとFO(ID)のグラウンディング
Grounding is the task of reducing a first-order theory and finite domain to an equivalent propositional theory. It is used as preprocessing phase in many logic-based reasoning systems. Such systems provide a rich first-order input language to a user and can rely on efficient propositional solvers to perform the actual reasoning. Besides a first-order theory and finite domain, the input for grounders contains in many applications also additional data. By exploiting this data, the size of the grounder’s output can often be reduced significantly. A common practice to improve the efficiency of a grounder in this context is by manually adding semantically redundant information to the input theory, indicating where and when the grounder should exploit the data. In this paper we present a method to compute and add such redundant information automatically. Our method therefore simplifies the task of writing input theories that can be grounded efficiently by current systems.We first present our method for classical first-order logic (FO) theories. Then we extend it to FO(ID), the extension of FO with inductive definitions, which allows for more concise and comprehensive input theories. We discuss implementation issues and experimentally validate the practical applicability of our method.
グラウンディングとは、一階述語理論と有限領域を等価な命題理論に縮減するタスクです。これは、多くの論理ベース推論システムの前処理フェーズとして用いられます。このようなシステムは、ユーザーに豊富な一階述語入力言語を提供し、効率的な命題ソルバーを用いて実際の推論を実行することができます。多くのアプリケーションでは、一階述語理論と有限領域に加えて、グラウンダーの入力には追加データも含まれます。このデータを活用することで、グラウンダーの出力サイズを大幅に削減できる場合が多い。この文脈においてグラウンダーの効率を向上させる一般的な方法は、グラウンダーがデータを活用すべき場所とタイミングを示す意味的に冗長な情報を入力理論に手動で追加することです。本稿では、このような冗長情報を自動的に計算して追加する方法を提示します。したがって、本手法は、既存のシステムによって効率的にグラウンディング可能な入力理論の作成作業を簡素化します。まず、古典的な一階述語論理（FO）理論に対する本手法を提示します。次に、これをFOに帰納的定義を加えた拡張であるFO(ID)へと拡張し、より簡潔で包括的な入力理論の構築を可能にします。実装上の問題について議論し、本手法の実用性を実験的に検証します。
Constructing Reference Sets from Unstructured, Ungrammatical Text
非構造化・非文法的テキストからの参照集合の構築
Vast amounts of text on the Web are unstructured and ungrammatical, such as classified ads, auction listings, forum postings, etc. We call such text posts. Despite their inconsistent structure and lack of grammar, posts are full of useful information. This paper presents work on semi-automatically building tables of relational information, called reference sets, by analyzing such posts directly. Reference sets can be applied to a number of tasks such as ontology maintenance and information extraction. Our reference-set construction method starts with just a small amount of background knowledge, and constructs tuples representing the entities in the posts to form a reference set. We also describe an extension to this approach for the special case where even this small amount of background knowledge is impossible to discover and use. To evaluate the utility of the machine-constructed reference sets, we compare them to manually constructed reference sets in the context of reference-set-based information extraction. Our results show the reference sets constructed by our method outperform manually constructed reference sets. We also compare the reference-set-based extraction approach using the machine-constructed reference set to supervised extraction approaches using generic features. These results demonstrate that using machine-constructed reference sets outperforms the supervised methods, even though the supervised methods require training data.
ウェブ上の膨大な量のテキストは、分類広告、オークションリスト、フォーラム投稿など、非構造化かつ非文法的です。このようなテキストを投稿と呼びます。一貫性のない構造と文法の欠如にもかかわらず、投稿は有用な情報でいっぱいです。この論文では、このような投稿を直接分析することにより、参照セットと呼ばれる関係情報のテーブルを半自動的に構築する取り組みを紹介します。参照セットは、オントロジーの維持や情報抽出などの多くのタスクに適用できます。私たちの参照セット構築法は、わずかな背景知識から始めて、投稿内のエンティティを表すタプルを構築し、参照セットを形成します。また、このわずかな背景知識さえも発見および使用することが不可能な特殊なケースのために、このアプローチを拡張する方法についても説明します。機械で構築された参照セットの有用性を評価するために、参照セットベースの情報抽出のコンテキストで、手動で構築された参照セットと比較します。結果は、私たちの方法で構築された参照セットが手動で構築された参照セットよりも優れていることを示しています。また、機械構築された参照セットを用いた参照セットベースの抽出手法と、汎用的な特徴を用いた教師あり抽出手法を比較します。これらの結果は、教師あり手法が学習データを必要とするにもかかわらず、機械構築された参照セットを用いた方が教師あり手法よりも性能が高いことを示しています。
A Survey of Paraphrasing and Textual Entailment Methods
パラフレージングとテキスト含意法のサーベイ
Paraphrasing methods recognize, generate, or extract phrases, sentences, or longer natural language expressions that convey almost the same information. Textual entailment methods, on the other hand, recognize, generate, or extract pairs of natural language expressions, such that a human who reads (and trusts) the first element of a pair would most likely infer that the other element is also true. Paraphrasing can be seen as bidirectional textual entailment and methods from the two areas are often similar. Both kinds of methods are useful, at least in principle, in a wide range of natural language processing applications, including question answering, summarization, text generation, and machine translation. We summarize key ideas from the two areas by considering in turn recognition, generation, and extraction methods, also pointing to prominent articles and resources.
言い換え手法は、ほぼ同じ情報を伝えるフレーズ、文、またはより長い自然言語表現を認識、生成、または抽出します。一方、テキスト含意手法は、ペアの最初の要素を読んで（そして信頼して）いる人間が、もう一方の要素も真であると推論する可能性が最も高いような自然言語表現のペアを認識、生成、または抽出します。言い換えは双方向のテキスト含意と見なすことができ、この2つの分野の手法は多くの場合類似しています。どちらの手法も、少なくとも原理的には、質問応答、要約、テキスト生成、機械翻訳など、幅広い自然言語処理アプリケーションで有用です。本稿では、認識、生成、抽出手法を順に検討し、著名な論文やリソースを紹介することで、この2つの分野の主要なアイデアを要約します。
Using Local Alignments for Relation Recognition
関係認識のための局所アライメントの利用
This paper discusses the problem of marrying structural similarity with semantic relatedness for Information Extraction from text. Aiming at accurate recognition of relations, we introduce local alignment kernels and explore various possibilities of using them for this task. We give a definition of a local alignment (LA) kernel based on the Smith-Waterman score as a sequence similarity measure and proceed with a range of possibilities for computing similarity between elements of sequences. We show how distributional similarity measures obtained from unlabeled data can be incorporated into the learning task as semantic knowledge. Our experiments suggest that the LA kernel yields promising results on various biomedical corpora outperforming two baselines by a large margin. Additional series of experiments have been conducted on the data sets of seven general relation types, where the performance of the LA kernel is comparable to the current state-of-the-art results.
本論文では、テキストからの情報抽出において、構造的類似性と意味的関連性を組み合わせる問題について議論します。関係性の正確な認識を目指して、局所アライメントカーネルを導入し、このタスクでそれらを使用するさまざまな可能性を検討します。配列類似性尺度としてスミス-ウォーターマンスコアに基づく局所アライメント（LA）カーネルの定義を示し、配列要素間の類似性を計算するためのさまざまな可能性を検討します。ラベルなしデータから得られた分布類似性尺度を、意味的知識として学習タスクに組み込む方法を示します。実験では、LAカーネルがさまざまな生物医学コーパスにおいて、2つのベースラインを大幅に上回る有望な結果をもたらすことが示唆されました。7種類の一般的な関係タイプのデータセットに対して追加の一連の実験が行われ、LAカーネルの性能は現在の最先端の結果と同等であることが示されました。