Modularity Aspects of Disjunctive Stable Models
選言的安定モデルのモジュール性
Practically all programming languages allow the programmer to split a program into several modules which brings along several advantages in software development. In this paper, we are interested in the area of answer-set programming where fully declarative and nonmonotonic languages are applied. In this context, obtaining a modular structure for programs is by no means straightforward since the output of an entire program cannot in general be composed from the output of its components. To better understand the effects of disjunctive information on modularity we restrict the scope of analysis to the case of disjunctive logic programs (DLPs) subject to stable-model semantics. We define the notion of a DLP-function, where a well-defined input/output interface is provided, and establish a novel module theorem which indicates the compositionality of stable-model semantics for DLP-functions. The module theorem extends the well-known splitting-set theorem and enables the decomposition of DLP-functions given their strongly connected components based on positive dependencies induced by rules. In this setting, it is also possible to split shared disjunctive rules among components using a generalized shifting technique. The concept of modular equivalence is introduced for the mutual comparison of DLP-functions using a generalization of a translation-based verification method.
事実上すべてのプログラミング言語は、プログラムを複数のモジュールに分割することをプログラマに許可しており、これはソフトウェア開発において様々な利点をもたらします。本稿では、完全宣言型かつ非単調な言語が適用される解集合プログラミングの分野に焦点を当てます。この文脈において、プログラム全体の出力は一般にその構成要素の出力から構成できないため、プログラムのモジュール構造を得ることは決して容易ではありません。選言情報がモジュール性に与える影響をより深く理解するために、安定モデル意味論に従う選言論理プログラム（DLP）のケースに分析範囲を限定します。明確に定義された入出力インターフェースが提供されるDLP関数の概念を定義し、DLP関数の安定モデル意味論の構成性を示す新たなモジュール定理を確立します。このモジュール定理は、よく知られている分割集合定理を拡張し、ルールによって誘導される正の依存関係に基づいて、強連結構成要素が与えられたDLP関数の分解を可能にします。この設定では、一般化されたシフト技法を用いて、コンポーネント間で共有される選言規則を分割することも可能です。モジュラー同値性の概念は、翻訳ベースの検証手法の一般化を用いてDLP関数の相互比較を行うために導入されています。
Enhancing QA Systems with Complex Temporal Question Processing Capabilities
複雑な時系列質問処理機能によるQAシステムの強化
This paper presents a multilayered architecture that enhances the capabilities of current QA systems and allows different types of complex questions or queries to be processed. The answers to these questions need to be gathered from factual information scattered throughout different documents. Specifically, we designed a specialized layer to process the different types of temporal questions. Complex temporal questions are first decomposed into simple questions, according to the temporal relations expressed in the original question. In the same way, the answers to the resulting simple questions are recomposed, fulfilling the temporal restrictions of the original complex question. A novel aspect of this approach resides in the decomposition which uses a minimal quantity of resources, with the final aim of obtaining a portable platform that is easily extensible to other languages. In this paper we also present a methodology for evaluation of the decomposition of the questions as well as the ability of the implemented temporal layer to perform at a multilingual level. The temporal layer was first performed for English, then evaluated and compared with: a) a general purpose QA system (F-measure 65.47% for QA plus English temporal layer vs. 38.01% for the general QA system), and b) a well-known QA system. Much better results were obtained for temporal questions with the multilayered system. This system was therefore extended to Spanish and very good results were again obtained in the evaluation (F-measure 40.36% for QA plus Spanish temporal layer vs. 22.94% for the general QA system).
本論文では、現在のQAシステムの機能を強化し、さまざまな種類の複雑な質問やクエリを処理できるようにする多層アーキテクチャを提示します。これらの質問への回答は、さまざまな文書に散在する事実情報から収集する必要があります。具体的には、さまざまな種類の時間的質問を処理するための専用レイヤーを設計した。複雑な時間的質問は、元の質問で表現された時間的関係に従って、まず単純な質問に分解されます。同様に、結果として得られる単純な質問に対する回答は再構成され、元の複雑な質問の時間的制約を満たします。このアプローチの新しい側面は、他の言語に簡単に拡張できるポータブルなプラットフォームを得ることを最終目標として、最小限のリソースを使用する分解にあります。この論文では、質問の分解の評価と、実装された時間レイヤーが多言語レベルで実行する能力についても紹介します。時間レイヤーは最初に英語に対して実行され、次に以下と比較して評価されました。a)汎用QAシステム（QAプラス英語時間レイヤーのF値65.47%に対し、一般的なQAシステムでは38.01%）、およびb)よく知られたQAシステム。多層システムでは、時間に関する質問に対してはるかに良い結果が得られました。したがって、このシステムはスペイン語に拡張され、評価で再び非常に良好な結果が得られました(QAプラス スペイン語時間レイヤーのF値は40.36%、一般的なQAシステムでは22.94%)。
The Complexity of Circumscription in DLs
DLにおけるサーカムスクリプションの複雑さ
As fragments of first-order logic, Description logics (DLs) do not provide nonmonotonic features such as defeasible inheritance and default rules. Since many applications would benefit from the availability of such features, several families of nonmonotonic DLs have been developed that are mostly based on default logic and autoepistemic logic. In this paper, we consider circumscription as an interesting alternative approach to nonmonotonic DLs that, in particular, supports defeasible inheritance in a natural way. We study DLs extended with circumscription under different language restrictions and under different constraints on the sets of minimized, fixed, and varying predicates, and pinpoint the exact computational complexity of reasoning for DLs ranging from ALC to ALCIO and ALCQO. When the minimized and fixed predicates include only concept names but no role names, then reasoning is complete for NExpTime^NP. It becomes complete for NP^NExpTime when the number of minimized and fixed predicates is bounded by a constant. If roles can be minimized or fixed, then complexity ranges from NExpTime^NP to undecidability.
一階述語論理の断片である記述論理（DL）は、破棄可能継承やデフォルトルールといった非単調な機能を提供しない。多くのアプリケーションがそのような機能の利用から恩恵を受けるため、主にデフォルト論理と自己認識論理に基づく非単調DLのいくつかのファミリーが開発されてきた。本稿では、特に自然な方法で破棄可能継承をサポートする、非単調DLの興味深い代替アプローチとしてサーカムスクリプションを検討します。我々は、異なる言語制約下、および最小化述語、固定述語、可変述語の集合に対する異なる制約下で、サーカムスクリプションを拡張したDLを研究し、ALCからALCIO、ALCQOに至るまでのDLの推論の計算複雑度を正確に特定します。最小化述語および固定述語に概念名のみが含まれ、役割名が含まれない場合、推論はNExpTime^NPで完全となります。最小化述語および固定述語の数が定数で制限される場合、NP^NExpTimeで完全となります。役割を最小化または固定できる場合、計算複雑度はNExpTime^NPから決定不能性までの範囲となります。
Variable Forgetting in Reasoning about Knowledge
知識推論における変数の忘却
In this paper, we investigate knowledge reasoning within a simple framework called knowledge structure. We use variable forgetting as a basic operation for one agent to reason about its own or other agents\’ knowledge. In our framework, two notions namely agents\’ observable variables and the weakest sufficient condition play important roles in knowledge reasoning. Given a background knowledge base and a set of observable variables for each agent, we show that the notion of an agent knowing a formula can be defined as a weakest sufficient condition of the formula under background knowledge base. Moreover, we show how to capture the notion of common knowledge by using a generalized notion of weakest sufficient condition. Also, we show that public announcement operator can be conveniently dealt with via our notion of knowledge structure. Further, we explore the computational complexity of the problem whether an epistemic formula is realized in a knowledge structure. In the general case, this problem is PSPACE-hard; however, for some interesting subcases, it can be reduced to co-NP. Finally, we discuss possible applications of our framework in some interesting domains such as the automated analysis of the well-known muddy children puzzle and the verification of the revised Needham-Schroeder protocol. We believe that there are many scenarios where the natural presentation of the available information about knowledge is under the form of a knowledge structure. What makes it valuable compared with the corresponding multi-agent S5 Kripke structure is that it can be much more succinct.
本稿では、知識構造と呼ばれるシンプルなフレームワーク内での知識推論について考察します。あるエージェントが自身の知識、あるいは他のエージェントの知識について推論を行うための基本操作として、変数忘却を用います。本稿のフレームワークでは、エージェントの観測可能な変数と最弱十分条件という2つの概念が知識推論において重要な役割を果たしています。背景知識ベースと各エージェントの観測可能な変数の集合が与えられた場合、エージェントが公式を知っているという概念は、背景知識ベースにおける公式の最弱十分条件として定義できることを示す。さらに、最弱十分条件という一般化された概念を用いて、共通知識の概念を捉える方法を示す。また、知識構造という概念を用いることで、広報演算子を簡便に扱えることを示す。さらに、認識論的公式が知識構造で実現されるかどうかという問題の計算量についても考察します。一般的なケースでは、この問題はPSPACE困難であるが、いくつかの興味深いサブケースにおいては、co-NPに縮減できます。最後に、よく知られているマディ・チルドレン・パズルの自動解析や改訂版ニーダム・シュローダー・プロトコルの検証など、いくつかの興味深い分野における我々のフレームワークの適用可能性について議論します。知識に関する利用可能な情報の自然な表現が知識構造の形で提示されるシナリオは数多くあると我々は考えています。対応するマルチエージェントS5クリプキ構造と比較して知識構造が貴重なのは、はるかに簡潔に表現できることです。
Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width
有界幅を持つ適合計画問題における不確実性のコンパイル
Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state or action effects. The problem has been approached as a path-finding problem in belief space where good belief representations and heuristics are critical for scaling up. In this work, a different formulation is introduced for conformant problems with deterministic actions where they are automatically converted into classical ones and solved by an off-the-shelf classical planner. The translation maps literals L and sets of assumptions t about the initial situation, into new literals KL/t that represent that L must be true if t is initially true. We lay out a general translation scheme that is sound and establish the conditions under which the translation is also complete. We show that the complexity of the complete translation is exponential in a parameter of the problem called the conformant width, which for most benchmarks is bounded. The planner based on this translation exhibits good performance in comparison with existing planners, and is the basis for T0, the best performing planner in the Conformant Track of the 2006 International Planning Competition.
適合計画とは、初期状態または行動効果に不確実性がある場合に、目標を達成するための行動のシーケンスを見つける問題です。この問題は、適切な信念表現とヒューリスティックがスケールアップに不可欠となる、信念空間における経路探索問題としてアプローチされてきた。本研究では、決定論的行動を伴う適合問題に対して異なる定式化を導入し、それらを自動的に古典的な行動に変換し、既製の古典的なプランナーによって解く。この変換は、リテラルLと初期状況に関する仮定の集合tを、tが最初に真である場合にLが真でなければならないことを表す新しいリテラルKL/tにマッピングします。我々は、健全な一般的な変換スキームを提示し、変換が完全となる条件を確立します。完全な変換の複雑さは、この問題の適合幅と呼ばれるパラメータに対して指数関数的であることを示す。適合幅は、ほとんどのベンチマークでは有界です。この変換に基づくプランナーは、既存のプランナーと比較して優れた性能を示し、2006年国際プランニングコンペティションの適合トラックにおいて最高性能のプランナーであるT0の基盤となっています。
Bounds Arc Consistency for Weighted CSPs
重み付きCSPにおける境界アークの一貫性
The Weighted Constraint Satisfaction Problem (WCSP) framework allows representing and solving problems involving both hard constraints and cost functions. It has been applied to various problems, including resource allocation, bioinformatics, scheduling, etc. To solve such problems, solvers usually rely on branch-and-bound algorithms equipped with local consistency filtering, mostly soft arc consistency. However, these techniques are not well suited to solve problems with very large domains. Motivated by the resolution of an RNA gene localization problem inside large genomic sequences, and in the spirit of bounds consistency for large domains in crisp CSPs, we introduce soft bounds arc consistency, a new weighted local consistency specifically designed for WCSP with very large domains. Compared to soft arc consistency, BAC provides significantly improved time and space asymptotic complexity. In this paper, we show how the semantics of cost functions can be exploited to further improve the time complexity of BAC. We also compare both in theory and in practice the efficiency of BAC on a WCSP with bounds consistency enforced on a crisp CSP using cost variables. On two different real problems modeled as WCSP, including our RNA gene localization problem, we observe that maintaining bounds arc consistency outperforms arc consistency and also improves over bounds consistency enforced on a constraint model with cost variables.
重み付き制約充足問題(WCSP)フレームワークは、ハード制約とコスト関数の両方を含む問題の表現と解決を可能にします。これは、リソース割り当て、バイオインフォマティクス、スケジューリングなど、さまざまな問題に適用されています。このような問題を解決するために、ソルバーは通常、局所一貫性フィルタリング(主にソフトアーク一貫性)を備えた分岐限定アルゴリズムに依存します。しかし、これらの手法は、非常に大きなドメインの問題の解決には適していません。大規模ゲノム配列内のRNA遺伝子局在問題の解決に動機付けられ、また、クリスプCSPにおける大規模ドメインの境界一貫性の精神に則り、我々は、非常に大きなドメインを持つWCSPに特化して設計された新しい重み付き局所一貫性であるソフト境界アーク一貫性を導入します。ソフトアーク一貫性と比較して、BACは大幅に改善された時間と空間の漸近計算量を提供します。本稿では、コスト関数のセマンティクスを活用してBACの時間計算量をさらに改善する方法を示します。また、コスト変数を用いてクリスプCSPに境界一貫性を強制したWCSPにおけるBACの効率を、理論と実践の両方で比較します。WCSPとしてモデル化された2つの異なる現実の問題（我々のRNA遺伝子局在問題を含む）において、境界アーク一貫性の維持はアーク一貫性よりも優れており、コスト変数を含む制約モデルに強制された境界一貫性よりも改善されることがわかった。
Optimal Value of Information in Graphical Models
グラフィカルモデルにおける情報の最適価値
Many real-world decision making tasks require us to choose among several expensive observations. In a sensor network, for example, it is important to select the subset of sensors that is expected to provide the strongest reduction in uncertainty. In medical decision making tasks, one needs to select which tests to administer before deciding on the most effective treatment. It has been general practice to use heuristic-guided procedures for selecting observations. In this paper, we present the first efficient optimal algorithms for selecting observations for a class of probabilistic graphical models. For example, our algorithms allow to optimally label hidden variables in Hidden Markov Models (HMMs). We provide results for both selecting the optimal subset of observations, and for obtaining an optimal conditional observation plan.Furthermore we prove a surprising result: In most graphical models tasks, if one designs an efficient algorithm for chain graphs, such as HMMs, this procedure can be generalized to polytree graphical models. We prove that the optimizing value of information is $NP^{PP}$-hard even for polytrees. It also follows from our results that just computing decision theoretic value of information objective functions, which are commonly used in practice, is a #P-complete problem even on Naive Bayes models (a simple special case of polytrees).In addition, we consider several extensions, such as using our algorithms for scheduling observation selection for multiple sensors. We demonstrate the effectiveness of our approach on several real-world datasets, including a prototype sensor network deployment for energy conservation in buildings.
多くの現実世界の意思決定タスクでは、複数の高価な観測値から選択する必要があります。例えば、センサーネットワークでは、不確実性を最大限に低減すると期待されるセンサーのサブセットを選択することが重要です。医療上の意思決定タスクでは、最も効果的な治療を決定する前に、どの検査を実施するかを選択する必要があります。観測値の選択には、ヒューリスティックに基づく手順を使用するのが一般的でした。本稿では、確率的グラフィカルモデルのクラスに対して観測値を選択するための、初めて効率的な最適アルゴリズムを提示します。例えば、私たちのアルゴリズムは、隠れマルコフモデル（HMM）の隠れ変数に最適にラベル付けすることを可能にします。我々は、観測の最適なサブセットの選択と、最適な条件付き観測計画の取得の両方について結果を提供します。さらに、我々は驚くべき結果を証明しています。ほとんどのグラフィカルモデルのタスクでは、HMMなどのチェーングラフ用の効率的なアルゴリズムを設計すれば、この手順をポリツリーグラフィカルモデルに一般化できます。我々は、情報の値を最適化することは、ポリツリーの場合でも$NP^{PP}$困難であることを証明しています。また、我々の結果から、実際に一般的に使用される情報目的関数の決定理論的値を計算することは、ナイーブベイズモデル（ポリツリーの単純な特殊ケース）であっても#P完全問題であることがわかる。さらに、我々は、複数のセンサーの観測選択をスケジュールするためのアルゴリズムを使用するなど、いくつかの拡張を検討しています。我々は、建物の省エネのためのプロトタイプセンサーネットワーク展開を含む、いくつかの現実世界のデータセットで我々のアプローチの有効性を実証しています。
Solving Weighted Constraint Satisfaction Problems with Memetic/Exact Hybrid Algorithms
重み付き制約充足問題をミーム的/厳密なハイブリッドアルゴリズムで解く
A weighted constraint satisfaction problem (WCSP) is a constraint satisfaction problem in which preferences among solutions can be expressed. Bucket elimination is a complete technique commonly used to solve this kind of constraint satisfaction problem. When the memory required to apply bucket elimination is too high, a heuristic method based on it (denominated mini-buckets) can be used to calculate bounds for the optimal solution. Nevertheless, the curse of dimensionality makes these techniques impractical on large scale problems. In response to this situation, we present a memetic algorithm for WCSPs in which bucket elimination is used as a mechanism for recombining solutions, providing the best possible child from the parental set. Subsequently, a multi-level model in which this exact/metaheuristic hybrid is further hybridized with branch-and-bound techniques and mini-buckets is studied. As a case study, we have applied these algorithms to the resolution of the maximum density still life problem, a hard constraint optimization problem based on Conway’s game of life. The resulting algorithm consistently finds optimal patterns for up to date solved instances in less time than current approaches. Moreover, it is shown that this proposal provides new best known solutions for very large instances.
重み付き制約充足問題（WCSP）は、解間の選好を表現できる制約充足問題です。バケット消去法は、この種の制約充足問題を解くために一般的に用いられる包括的な手法です。バケット消去法を適用するために必要なメモリ量が大きすぎる場合、バケット消去法に基づくヒューリスティックな手法（ミニバケットと呼ばれる）を用いて最適解の境界を計算することができます。しかしながら、次元の呪いのため、これらの手法は大規模な問題では実用的ではありません。この状況に対処するため、本研究では、バケット消去法を解の再結合メカニズムとして用い、親集合から可能な限り最適な子を提供するWCSPのためのミームアルゴリズムを提示します。次に、この厳密解法とメタヒューリスティック解法の融合を、分枝限定法とミニバケット法とさらに融合させた多階層モデルを研究します。事例研究として、これらのアルゴリズムを、コンウェイのライフゲームに基づく難制約最適化問題である最大密度静物画問題の解法に適用しました。得られたアルゴリズムは、最新の解決済みインスタンスに対して、現在のアプローチよりも短時間で、一貫して最適なパターンを見つけます。さらに、この提案は非常に大規模なインスタンスに対して、新たな最良解を提供することが示されています。
Message-Based Web Service Composition, Integrity Constraints, and Planning under Uncertainty: A New Connection
メッセージベースのWebサービス構成、整合性制約、そして不確実性下における計画：新たな関連性
Thanks to recent advances, AI Planning has become the underlying technique for several applications. Figuring prominently among these is automated Web Service Composition (WSC) at the “capability” level, where services are described in terms of preconditions and effects over ontological concepts. A key issue in addressing WSC as planning is that ontologies are not only formal vocabularies; they also axiomatize the possible relationships between concepts. Such axioms correspond to what has been termed “integrity constraints” in the actions and change literature, and applying a web service is essentially a belief update operation. The reasoning required for belief update is known to be harder than reasoning in the ontology itself. The support for belief update is severely limited in current planning tools.Our first contribution consists in identifying an interesting special case of WSC which is both significant and more tractable. The special case, which we term “forward effects”, is characterized by the fact that every ramification of a web service application involves at least one new constant generated as output by the web service. We show that, in this setting, the reasoning required for belief update simplifies to standard reasoning in the ontology itself. This relates to, and extends, current notions of “message-based” WSC, where the need for belief update is removed by a strong (often implicit or informal) assumption of “locality” of the individual messages. We clarify the computational properties of the forward effects case, and point out a strong relation to standard notions of planning under uncertainty, suggesting that effective tools for the latter can be successfully adapted to address the former.Furthermore, we identify a significant sub-case, named “strictly forward effects”, where an actual compilation into planning under uncertainty exists. This enables us to exploit off-the-shelf planning tools to solve message-based WSC in a general form that involves powerful ontologies, and requires reasoning about partial matches between concepts. We provide empirical evidence that this approach may be quite effective, using Conformant-FF as the underlying planner.
近年の進歩により、AIプランニングは様々なアプリケーションの基盤技術となっています。中でも特に注目すべきは、「機能」レベルでの自動Webサービスコンポジション（WSC）です。WSCでは、サービスはオントロジー概念に基づく前提条件と効果によって記述されます。WSCをプランニングとして扱う上で重要な問題は、オントロジーが形式的な語彙であるだけでなく、概念間の可能な関係を公理化している点です。このような公理は、行動と変化に関する文献で「整合性制約」と呼ばれているものに相当し、Webサービスの適用は本質的には信念の更新操作です。信念の更新に必要な推論は、オントロジー自体における推論よりも困難であることが知られています。現在のプランニングツールでは、信念の更新のサポートは著しく限られています。私たちの最初の貢献は、WSCの興味深い特殊なケースを特定することです。これは重要かつ扱いやすいものです。「前方効果」と呼ぶこの特殊なケースは、Webサービスアプリケーションのあらゆる分岐に、Webサービスによって出力として生成される少なくとも1つの新しい定数が含まれるという特徴があります。この設定において、信念更新に必要な推論は、オントロジー自体における標準的な推論へと単純化されることを示す。これは、個々のメッセージの「局所性」という強い（しばしば暗黙的または非公式な）仮定によって信念更新の必要性が排除される、現在の「メッセージベース」WSCの概念に関連し、それを拡張するものです。我々は、順方向効果の場合の計算特性を明らかにし、不確実性下における計画の標準的な概念との強い関連性を指摘し、後者のための効果的なツールが前者にも適用可能であることを示唆します。さらに、「厳密な順方向効果」と呼ばれる重要なサブケースを特定し、不確実性下における計画への実際のコンパイルが存在します。これにより、強力なオントロジーを含み、概念間の部分的な一致に関する推論を必要とする一般的な形式で、メッセージベースWSCを解くために、市販の計画ツールを活用することが可能となります。我々は、基盤となるプランナーとしてConformant-FFを用いた場合、このアプローチが非常に効果的である可能性があることを実証的に証明します。
How Hard Is Bribery in Elections?
選挙における賄賂はどれほど難しいのか？
We study the complexity of influencing elections through bribery: How computationally complex is it for an external actor to determine whether by paying certain voters to change their preferences a specified candidate can be made the elections winner? We study this problem for election systems as varied as scoring protocols and Dodgson voting, and in a variety of settings regarding homogeneous-vs.-nonhomogeneous electorate bribability, bounded-size-vs.-arbitrary-sized candidate sets, weighted-vs.-unweighted voters, and succinct-vs.-nonsuccinct input specification. We obtain both polynomial-time bribery algorithms and proofs of the intractability of bribery, and indeed our results show that the complexity of bribery is extremely sensitive to the setting. For example, we find settings in which bribery is NP-complete but manipulation (by voters) is in P, and we find settings in which bribing weighted voters is NP-complete but bribing voters with individual bribe thresholds is in P. For the broad class of elections (including plurality, Borda, k-approval, and veto) known as scoring protocols, we prove a dichotomy result for bribery of weighted voters: We find a simple-to-evaluate condition that classifies every case as either NP-complete or in P.
私たちは、賄賂を通じて選挙に影響を与える複雑さを調査します。特定の有権者に金銭を支払って好みを変えてもらうことで、特定の候補者を選挙の勝者にできるかどうかを外部のアクターが判断することは、どれほど計算的に複雑でしょうか。我々はこの問題を、スコアリングプロトコルやドッドソン投票といった多様な選挙システム、そして均質な選挙民の賄賂可能性と非均質な選挙民の賄賂可能性、制限されたサイズの候補者集合と任意のサイズの候補者集合、重み付けされた投票者と重み付けされていない投票者、簡潔な入力仕様と簡潔でない入力仕様といった様々な設定において研究した。我々は多項式時間賄賂アルゴリズムと賄賂の扱いにくさの証明の両方を得た。そして実際、我々の結果は賄賂の複雑さが設定に極めて敏感であることを示しています。たとえば、賄賂はNP完全だが(有権者による)操作はPである設定や、重み付けされた有権者への賄賂はNP完全だが個別の賄賂しきい値による有権者への賄賂はPである設定が見つかります。スコアリング プロトコルとして知られる広範な選挙クラス(多数決、ボルダ、k承認、拒否権を含む)の場合、重み付けされた有権者の賄賂の二分法の結果を証明します。すべてのケースをNP完全またはPのいずれかに分類する、評価が簡単な条件が見つかります。
Efficient Markov Network Structure Discovery Using Independence Tests
独立性検定を用いた効率的なマルコフネットワーク構造の発見
We present two algorithms for learning the structure of a Markov network from data: GSMN* and GSIMN. Both algorithms use statistical independence tests to infer the structure by successively constraining the set of structures consistent with the results of these tests. Until very recently, algorithms for structure learning were based on maximum likelihood estimation, which has been proved to be NP-hard for Markov networks due to the difficulty of estimating the parameters of the network, needed for the computation of the data likelihood. The independence-based approach does not require the computation of the likelihood, and thus both GSMN* and GSIMN can compute the structure efficiently (as shown in our experiments). GSMN* is an adaptation of the Grow-Shrink algorithm of Margaritis and Thrun for learning the structure of Bayesian networks. GSIMN extends GSMN* by additionally exploiting Pearl’s well-known properties of the conditional independence relation to infer novel independences from known ones, thus avoiding the performance of statistical tests to estimate them. To accomplish this efficiently GSIMN uses the Triangle theorem, also introduced in this work, which is a simplified version of the set of Markov axioms. Experimental comparisons on artificial and real-world data sets show GSIMN can yield significant savings with respect to GSMN*, while generating a Markov network with comparable or in some cases improved quality. We also compare GSIMN to a forward-chaining implementation, called GSIMN-FCH, that produces all possible conditional independences resulting from repeatedly applying Pearl’s theorems on the known conditional independence tests. The results of this comparison show that GSIMN, by the sole use of the Triangle theorem, is nearly optimal in terms of the set of independences tests that it infers.
データからマルコフネットワークの構造を学習する2つのアルゴリズム、GSMN*とGSIMNを紹介します。どちらのアルゴリズムも、統計的独立性検定を用いて、検定結果と一致する構造集合を逐次制約することで構造を推定します。ごく最近まで、構造学習アルゴリズムは最大尤度推定に基づいていましたが、これはデータの尤度の計算に必要なネットワークパラメータの推定が困難であるため、マルコフネットワークではNP困難であることが証明されています。独立性に基づくアプローチでは尤度の計算が不要なため、GSMN*とGSIMNはどちらも構造を効率的に計算できます（実験で示したように）。GSMN*は、ベイジアンネットワークの構造を学習するためのMargaritisとThrunのGrow-Shrinkアルゴリズムを応用したものです。GSIMNはGSMN*を拡張し、Pearlの条件付き独立性関係に関するよく知られた特性をさらに活用することで、既知の独立性から新しい独立性を推定します。これにより、独立性を推定するための統計的検定の実行を回避します。これを効率的に達成するために、GSIMNは、本研究でも紹介されているマルコフ公理の簡略版である三角定理を使用します。人工データセットと現実世界のデータセットでの実験的比較により、GSIMNはGSMN*に比べて大幅な節約を実現しながら、同等または場合によっては品質が向上したマルコフ ネットワークを生成できることが示されています。また、既知の条件付き独立性テストにPearlの定理を繰り返し適用することで得られるすべての可能な条件付き独立性を生成する、GSIMN-FCHと呼ばれる前向き連鎖実装とGSIMNを比較します。この比較の結果、三角定理のみを使用するGSIMNは、推論する独立性テストのセットに関してほぼ最適であることがわかります。
Learning Bayesian Network Equivalence Classes with Ant Colony Optimization
アリコロニー最適化を用いたベイジアンネットワーク同値類の学習
Bayesian networks are a useful tool in the representation of uncertain knowledge. This paper proposes a new algorithm called ACO-E, to learn the structure of a Bayesian network. It does this by conducting a search through the space of equivalence classes of Bayesian networks using Ant Colony Optimization (ACO). To this end, two novel extensions of traditional ACO techniques are proposed and implemented. Firstly, multiple types of moves are allowed. Secondly, moves can be given in terms of indices that are not based on construction graph nodes. The results of testing show that ACO-E performs better than a greedy search and other state-of-the-art and metaheuristic algorithms whilst searching in the space of equivalence classes.
ベイジアンネットワークは、不確実な知識を表現するための有用なツールです。本論文では、ベイジアンネットワークの構造を学習するためのACO-Eと呼ばれる新しいアルゴリズムを提案します。これは、アントコロニー最適化（ACO）を用いてベイジアンネットワークの同値類空間を探索することで行われます。この目的のために、従来のACO手法の2つの新しい拡張が提案され、実装されました。第1に、複数の種類の移動が許可されます。第2に、移動は構築グラフノードに基づかないインデックスで指定できます。テストの結果、同値クラスの空間で検索する場合、ACO-Eは貪欲検索やその他の最先端のメタヒューリスティック アルゴリズムよりも優れたパフォーマンスを発揮することが示されました。
Automated Reasoning in Modal and Description Logics via SAT Encoding: the Case Study of K(m)/ALC-Satisfiability
SATエンコーディングによる様相論理と記述論理における自動推論：K(m)/ALC充足可能性のケーススタディ
In the last two decades, modal and description logics have been applied to numerous areas of computer science, including knowledge representation, formal verification, database theory, distributed computing and, more recently, semantic web and ontologies. For this reason, the problem of automated reasoning in modal and description logics has been thoroughly investigated. In particular, many approaches have been proposed for efficiently handling the satisfiability of the core normal modal logic K(m), and of its notational variant, the description logic ALC. Although simple in structure, K(m)/ALC is computationally very hard to reason on, its satisfiability being PSPACE-complete. In this paper we start exploring the idea of performing automated reasoning tasks in modal and description logics by encoding them into SAT, so that to be handled by state-of-the-art SAT tools; as with most previous approaches, we begin our investigation from the satisfiability in K(m). We propose an efficient encoding, and we test it on an extensive set of benchmarks, comparing the approach with the main state-of-the-art tools available. Although the encoding is necessarily worst-case exponential, from our experiments we notice that, in practice, this approach can handle most or all the problems which are at the reach of the other approaches, with performances which are comparable with, or even better than, those of the current state-of-the-art tools.
過去20年間、様相論理と記述論理は、知識表現、形式検証、データベース理論、分散コンピューティング、さらに最近ではセマンティック ウェブやオントロジーなど、コンピュータ サイエンスのさまざまな分野に適用されてきました。このため、様相論理と記述論理における自動推論の問題は徹底的に調査されてきました。特に、コアとなる通常の様相論理K(m)とその表記法の変形である記述論理ALCの充足可能性を効率的に処理するための多くのアプローチが提案されています。K(m)/ALCは構造が単純ですが、その充足可能性はPSPACE完全であるため、計算的に推論するのが非常に困難です。本稿では、様相論理と記述論理での自動推論タスクをSATにエンコードすることにより、最先端のSATツールで処理できるようにすることで、そのアイデアの検討を開始します。これまでのほとんどのアプローチと同様に、K(m)の充足可能性から調査を開始します。我々は効率的なエンコーディングを提案し、広範なベンチマークセットでテストし、このアプローチを利用可能な主要な最先端ツールと比較しました。エンコーディングは必然的に最悪ケースの指数関数的効果をもたらしますが、実験の結果、このアプローチは実際には他のアプローチが対応可能なほとんど、あるいはすべての問題を、現在の最先端ツールと同等か、あるいはそれ以上の性能で処理できることがわかりました。
Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
LlullとCopelandの投票は、賄賂と建設的支配に計算的に抵抗する
Control and bribery are settings in which an external agent seeks to influence the outcome of an election. Constructive control of elections refers to attempts by an agent to, via such actions as addition/deletion/partition of candidates or voters, ensure that a given candidate wins. Destructive control refers to attempts by an agent to, via the same actions, preclude a given candidate’s victory. An election system in which an agent can sometimes affect the result and it can be determined in polynomial time on which inputs the agent can succeed is said to be vulnerable to the given type of control. An election system in which an agent can sometimes affect the result, yet in which it is NP-hard to recognize the inputs on which the agent can succeed, is said to be resistant to the given type of control.Aside from election systems with an NP-hard winner problem, the only systems previously known to be resistant to all the standard control types were highly artificial election systems created by hybridization. This paper studies a parameterized version of Copeland voting, denoted by Copeland^\alpha, where the parameter \alpha is a rational number between 0 and 1 that specifies how ties are valued in the pairwise comparisons of candidates. In every previously studied constructive or destructive control scenario, we determine which of resistance or vulnerability holds for Copeland^\alpha for each rational \alpha, 0 \leq \alpha \leq 1. In particular, we prove that Copeland^{0.5}, the system commonly referred to as “Copeland voting,” provides full resistance to constructive control, and we prove the same for Copeland^\alpha, for all rational \alpha, 0 < \alpha < 1. Among systems with a polynomial-time winner problem, Copeland voting is the first natural election system proven to have full resistance to constructive control. In addition, we prove that both Copeland^0 and Copeland^1 (interestingly, Copeland^1 is an election system developed by the thirteenth-century mystic Llull) are resistant to all standard types of constructive control other than one variant of addition of candidates. Moreover, we show that for each rational \alpha, 0 \leq \alpha \leq 1, Copeland^\alpha voting is fully resistant to bribery attacks, and we establish fixed-parameter tractability of bounded-case control for Copeland^\alpha.We also study Copeland^\alpha elections under more flexible models such as microbribery and extended control, we integrate the potential irrationality of voter preferences into many of our results, and we prove our results in both the unique-winner model and the nonunique-winner model. Our vulnerability results for microbribery are proven via a novel technique involving min-cost network flow.
制御と賄賂は、外部エージェントが選挙の結果に影響を与えようとする状況です。選挙の建設的制御とは、エージェントが候補者または投票者の追加、削除、分割などのアクションを通じて、特定の候補者の勝利を確実にしようとする試みを指します。破壊的制御とは、エージェントが同じアクションを通じて、特定の候補者の勝利を妨げようとする試みを指します。エージェントが結果に影響を与えることがあり、どの入力でエージェントが成功できるかを多項式時間で決定できる選挙システムは、特定の種類の制御に対して脆弱であると言われています。エージェントが結果に影響を与えることがあるものの、エージェントが成功できる入力を認識することがNP困難である選挙システムは、特定の種類の制御に対して耐性があると言われています。NP困難な勝者問題を持つ選挙システムを除けば、これまで標準的な制御タイプのすべてに耐性があることが知られている唯一のシステムは、ハイブリッド化によって作成された高度に人工的な選挙システムでした。この論文では、Copeland^\alphaと表記される、パラメーター化されたCopeland投票バージョンを研究します。ここで、パラメーター\alphaは0から1までの有理数であり、候補者の一対比較で同点がどのように評価されるかを指定します。これまでに研究されたすべての構成的制御または破壊的制御シナリオで、各有理数\alpha, 0 \leq \alpha \leq 1に対して、Copeland^\alphaに抵抗と脆弱性のどちらが当てはまるかを判断します。特に、一般に「Copeland投票」と呼ばれるシステムであるCopeland^{0.5}が構成的制御に対して完全な抵抗を提供することを証明し、すべての有理数\alpha, 0 < \alpha < 1に対して、Copeland^\alphaでも同じことを証明します。多項式時間勝者問題を持つシステムの中で、Copeland投票は構成的制御に対して完全な抵抗があることが証明された最初の自然な選挙システムです。さらに、Copeland^0とCopeland^1（興味深いことに、Copeland^1は13世紀の神秘主義者リュイによって開発された選挙システムです）はどちらも、候補者の追加という1つの変種を除く、すべての標準的な構成的制御に対して耐性があることを証明します。さらに、各有理数\alpha, 0 \leq \alpha \leq 1に対して、Copeland^\alpha投票は賄賂攻撃に対して完全に耐性があることを示します。また、Copeland^\alphaの境界付きケース制御の固定パラメータの扱いやすさを確立しました。さらに、マイクロ賄賂や拡張制御などのより柔軟なモデルの下でのCopeland^\alpha選挙を研究し、投票者の選好の潜在的な非合理性を多くの結果に統合し、ユニーク勝者モデルと非ユニーク勝者モデルの両方で結果を証明しました。マイクロ賄賂に対する脆弱性の結果は、最小コストネットワークフローを含む新しい手法によって証明されています。
A Bilinear Programming Approach for Multiagent Planning
マルチエージェント計画のための双線形計画アプローチ
Multiagent planning and coordination problems are common and known to be computationally hard. We show that a wide range of two-agent problems can be formulated as bilinear programs. We present a successive approximation algorithm that significantly outperforms the coverage set algorithm, which is the state-of-the-art method for this class of multiagent problems. Because the algorithm is formulated for bilinear programs, it is more general and simpler to implement. The new algorithm can be terminated at any time and-unlike the coverage set algorithm-it facilitates the derivation of a useful online performance bound. It is also much more efficient, on average reducing the computation time of the optimal solution by about four orders of magnitude. Finally, we introduce an automatic dimensionality reduction method that improves the effectiveness of the algorithm, extending its applicability to new domains and providing a new way to analyze a subclass of bilinear programs.
マルチエージェントの計画および調整問題は一般的であり、計算困難であることが知られています。我々は、広範囲の2エージェント問題が双線形計画として定式化できることを示す。我々は、この種のマルチエージェント問題における最先端手法である被覆集合アルゴリズムを大幅に上回る逐次近似アルゴリズムを提示します。このアルゴリズムは双線形計画法向けに定式化されているため、より汎用的で実装がシンプルです。この新しいアルゴリズムはいつでも終了させることができ、被覆集合アルゴリズムとは異なり、有用なオンライン性能限界の導出を容易にします。また、効率もはるかに高く、最適解の計算時間を平均で約4桁短縮します。最後に、アルゴリズムの有効性を向上させる自動次元削減法を紹介します。これにより、アルゴリズムの適用範囲が新たな分野に拡張され、双線形計画法のサブクラスを解析する新しい方法も提供されます。
Transductive Rademacher Complexity and its Applications
トランスダクティブ・ラーデマッハ複雑性とその応用
We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in terms of transductive Rademacher complexity, together with a novel bounding technique for Rademacher averages for particular algorithms, in terms of their “unlabeled-labeled” representation. This technique is relevant to many advanced graph-based transductive algorithms and we demonstrate its effectiveness by deriving error bounds to three well known algorithms. Finally, we present a new PAC-Bayesian bound for mixtures of transductive algorithms based on our Rademacher bounds.
我々は、トランスダクティブ・ラーデマッハ複雑度に基づくトランスダクティブ学習アルゴリズムのデータ依存誤差境界を導出する手法を開発します。この手法は、トランスダクティブ・ラーデマッハ複雑度に基づくトランスダクティブ学習アルゴリズムの新たな一般誤差境界と、特定のアルゴリズムの「ラベルなし-ラベル付き」表現に基づくラーデマッハ平均の新たな境界設定手法に基づいています。この手法は多くの高度なグラフベース・トランスダクティブアルゴリズムに関連し、我々は3つのよく知られたアルゴリズムの誤差境界を導出することでその有効性を実証します。最後に、我々のラーデマッハ境界に基づき、トランスダクティブアルゴリズムの混合に対する新たなPACベイズ境界を提示します。
Eliciting Single-Peaked Preferences Using Comparison Queries
比較クエリを用いた単峰性の選好の抽出
Voting is a general method for aggregating the preferences of multiple agents. Each agent ranks all the possible alternatives, and based on this, an aggregate ranking of the alternatives (or at least a winning alternative) is produced. However, when there are many alternatives, it is impractical to simply ask agents to report their complete preferences. Rather, the agents’ preferences, or at least the relevant parts thereof, need to be elicited. This is done by asking the agents a (hopefully small) number of simple queries about their preferences, such as comparison queries, which ask an agent to compare two of the alternatives. Prior work on preference elicitation in voting has focused on the case of unrestricted preferences. It has been shown that in this setting, it is sometimes necessary to ask each agent (almost) as many queries as would be required to determine an arbitrary ranking of the alternatives. In contrast, in this paper, we focus on single-peaked preferences. We show that such preferences can be elicited using only a linear number of comparison queries, if either the order with respect to which preferences are single-peaked is known, or at least one other agent’s complete preferences are known. We show that using a sublinear number of queries does not suffice. We also consider the case of cardinally single-peaked preferences. For this case, we show that if the alternatives’ cardinal positions are known, then an agent’s preferences can be elicited using only a logarithmic number of queries; however, we also show that if the cardinal positions are not known, then a sublinear number of queries does not suffice. We present experimental results for all elicitation algorithms. We also consider the problem of only eliciting enough information to determine the aggregate ranking, and show that even for this more modest objective, a sublinear number of queries per agent does not suffice for known ordinal or unknown cardinal positions. Finally, we discuss whether and how these techniques can be applied when preferences are almost single-peaked.
投票は、複数のエージェントの選好を集約する一般的な手法です。各エージェントはすべての可能な選択肢を順位付けし、それに基づいて選択肢の総合的な順位付け（または少なくとも勝者となる選択肢）が生成されます。しかし、選択肢の数が多い場合、エージェントに単に選好の全てを報告させるのは現実的ではない。むしろ、エージェントの選好、あるいは少なくともその関連部分を引き出す必要があります。これは、エージェントに選好に関する（できれば少数の）単純なクエリ、例えば2つの選択肢を比較するクエリなどを求めることによって行われます。投票における選好の引き出しに関するこれまでの研究は、選好に制限がない場合に焦点を当ててきた。このような設定では、各エージェントに、選択肢の任意の順位付けを決定するために必要な数のクエリを（ほぼ）尋ねる必要がある場合があることが示されています。これに対し、本稿では、単峰性の選好に焦点を当てる。選好が単峰性を持つ順序が既知であるか、少なくとも他のエージェント1人の選好が完全に既知である場合、そのような選好は線形数の比較クエリのみを用いて抽出できることを示す。線形数以下のクエリを用いるだけでは不十分であることを示す。また、基数的に単峰性の選好の場合も考察します。この場合、選択肢の基数的位置が既知であれば、対数的クエリのみを用いてエージェントの選好を抽出できることを示す。しかし、基数的位置が既知でない場合は、線形数以下のクエリでは不十分であることも示す。すべての抽出アルゴリズムの実験結果を示す。さらに、総合ランキングを決定するのに十分な情報のみを抽出するという問題も考察し、このより控えめな目的においてさえ、基数的位置が既知または未知の場合、エージェントあたりの線形数以下のクエリでは不十分であることを示す。最後に、選好がほぼ単峰性である場合にこれらの手法を適用できるかどうか、またどのように適用できるかを議論します。
Trust-Based Mechanisms for Robust and Efficient Task Allocation in the Presence of Execution Uncertainty
実行の不確実性が存在する状況下での堅牢かつ効率的なタスク割り当てのための信頼に基づくメカニズム
Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive compatible, direct mechanisms that are efficient (i.e., maximise social utility) and individually rational (i.e., agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will “always” successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications, where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent’s probability of succeeding at a given task are often captured and reasoned about using the notion of “trust”. Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called “trust-based mechanisms”, that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2×10^5 possible allocations in 40 seconds).
Vickrey-Clarke-Groves（VCG）メカニズムは、利己的エージェントと合理的エージェントにタスクを割り当てる際によく用いられます。VCGメカニズムは、誘因両立的で直接的なメカニズムであり、効率的（すなわち、社会的効用を最大化する）かつ個々に合理的（すなわち、エージェントは参加を辞退するよりも参加を好む）です。しかし、これらのメカニズムの重要な前提は、エージェントが割り当てられたタスクを「常に」正常に完了するということです。明らかに、この仮定は多くの現実世界のアプリケーションにおいて非現実的です。エージェントは試みに失敗する可能性があり、実際に失敗することがよくあります。さらに、エージェントが失敗したとみなされるかどうかは、エージェントによって認識が異なる場合があります。エージェントが特定のタスクで成功する確率に関するこのような主観的な認識は、しばしば「信頼」という概念を用いて捉えられ、推論されます。こうした背景を踏まえ、本論文では、タスクを割り当てる際にエージェント間の信頼を考慮する新しいメカニズムの設計について検討します。具体的には、「信頼に基づくメカニズム」と呼ばれる新しいクラスのメカニズムを開発します。このメカニズムは、エージェントが特定のタスクで成功する確率に関する複数の主観的尺度を考慮し、社会的効用を最大化し、かつどのエージェントも負の効用を得ないようにする割り当てを生成します。次に、このようなメカニズムが、NP完全である新しい組み合わせ最適化問題を提示することを示し、この問題を解決するための新しい表現を考案し、効果的な整数計画法（約2×10^5通りの割り当て可能なインスタンスを40秒で解くことができる）を開発します。
Complex Question Answering: Unsupervised Learning Approaches and Experiments
複雑な質問応答：教師なし学習アプローチと実験
Complex questions that require inferencing and synthesizing information from multiple documents can be seen as a kind of topic-oriented, informative multi-document summarization where the goal is to produce a single text as a compressed version of a set of documents with a minimum loss of relevant information. In this paper, we experiment with one empirical method and two unsupervised statistical machine learning techniques: K-means and Expectation Maximization (EM), for computing relative importance of the sentences. We compare the results of these approaches. Our experiments show that the empirical approach outperforms the other two techniques and EM performs better than K-means. However, the performance of these approaches depends entirely on the feature set used and the weighting of these features. In order to measure the importance and relevance to the user query we extract different kinds of features (i.e. lexical, lexical semantic, cosine similarity, basic element, tree kernel based syntactic and shallow-semantic) for each of the document sentences. We use a local search technique to learn the weights of the features. To the best of our knowledge, no study has used tree kernel functions to encode syntactic/semantic information for more complex tasks such as computing the relatedness between the query sentences and the document sentences in order to generate query-focused summaries (or answers to complex questions). For each of our methods of generating summaries (i.e. empirical, K-means and EM) we show the effects of syntactic and shallow-semantic features over the bag-of-words (BOW) features.
複数の文書から情報を推論および統合する必要がある複雑な質問は、トピック指向の有益な複数文書要約の一種と見なすことができます。その目的は、関連情報の損失を最小限に抑えながら、一連の文書の圧縮バージョンとして単一のテキストを作成することです。この論文では、文の相対的な重要度を計算するために、1つの経験的手法と2つの教師なし統計機械学習手法（K平均法と期待最大化（EM））を試します。これらのアプローチの結果を比較します。実験では、経験的アプローチが他の2つの手法よりも優れており、EMがK平均法よりも優れていることが示されています。ただし、これらのアプローチのパフォーマンスは、使用される特徴セットとこれらの特徴の重み付けに完全に依存します。ユーザークエリの重要性と関連性を測定するために、各ドキュメント文に対してさまざまな種類の特徴（つまり、語彙、語彙意味、コサイン類似度、基本要素、ツリーカーネルベースの構文、浅い意味）を抽出します。特徴量の重みを学習するために、局所探索手法を用います。我々の知る限り、クエリ文と文書文の関連性を計算し、クエリに焦点を当てた要約（または複雑な質問への回答）を生成するといった、より複雑なタスクにおいて、ツリーカーネル関数を用いて統語的・意味的情報を符号化した研究は存在しない。要約生成手法（経験的手法、K平均法、EM法）ごとに、統語的特徴量と浅い意味的特徴量が、バッグオブワード（BOW）特徴量に与える影響を示す。