Automatic Aggregation by Joint Modeling of Aspects and Values
アスペクトと値の結合モデリングによる自動集約
We present a model for aggregation of product review snippets by joint aspect identification and sentiment analysis. Our model simultaneously identifies an underlying set of ratable aspects presented in the reviews of a product (e.g., sushi and miso for a Japanese restaurant) and determines the corresponding sentiment of each aspect. This approach directly enables discovery of highly-rated or inconsistent aspects of a product. Our generative model admits an efficient variational mean-field inference algorithm. It is also easily extensible, and we describe several modifications and their effects on model structure and inference. We test our model on two tasks, joint aspect identification and sentiment analysis on a set of Yelp reviews and aspect identification alone on a set of medical summaries. We evaluate the performance of the model on aspect identification, sentiment analysis, and per-word labeling accuracy. We demonstrate that our model outperforms applicable baselines by a considerable margin, yielding up to 32% relative error reduction on aspect identification and up to 20% relative error reduction on sentiment analysis.
側面識別と感情分析を組み合わせた製品レビュースニペットの集約モデルを紹介します。このモデルは、製品のレビューで提示された評価可能な側面の基礎となるセット(たとえば、日本食レストランの寿司と味噌)を同時に識別し、各側面に対応する感情を決定します。このアプローチにより、製品の高評価の側面や一貫性のない側面を直接発見できます。この生成モデルは、効率的な変分平均場推論アルゴリズムを受け入れます。このモデルは容易に拡張可能であり、いくつかの変更点と、それらがモデル構造と推論に与える影響について説明します。Yelpのレビューセットにおけるアスペクト識別と感情分析の併用、および医療要約セットにおけるアスペクト識別のみの2つのタスクでモデルをテストします。アスペクト識別、感情分析、および単語ごとのラベル付け精度におけるモデルの性能を評価します。その結果、このモデルは適用可能なベースラインを大幅に上回り、アスペクト識別で最大32%、感情分析で最大20%の相対誤差削減を実現しました。
NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover
NuMVC：最小頂点被覆のための効率的な局所探索アルゴリズム
The Minimum Vertex Cover (MVC) problem is a prominent NP-hard combinatorial optimization problem of great importance in both theory and application. Local search has proved successful for this problem. However, there are two main drawbacks in state-of-the-art MVC local search algorithms. First, they select a pair of vertices to exchange simultaneously, which is time-consuming. Secondly, although using edge weighting techniques to diversify the search, these algorithms lack mechanisms for decreasing the weights. To address these issues, we propose two new strategies: two-stage exchange and edge weighting with forgetting. The two-stage exchange strategy selects two vertices to exchange separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. These two strategies are used in designing a new MVC local search algorithm, which is referred to as NuMVC.We conduct extensive experimental studies on the standard benchmarks, namely DIMACS and BHOSLIB. The experiment comparing NuMVC with state-of-the-art heuristic algorithms show that NuMVC is at least competitive with the nearest competitor namely PLS on the DIMACS benchmark, and clearly dominates all competitors on the BHOSLIB benchmark. Also, experimental results indicate that NuMVC finds an optimal solution much faster than the current best exact algorithm for Maximum Clique on random instances as well as some structured ones. Moreover, we study the effectiveness of the two strategies and the run-time behaviour through experimental analysis.
最小頂点被覆（MVC）問題は、理論と応用の両方において非常に重要な、NP困難な組合せ最適化問題として広く知られています。この問題に対しては、局所探索が有効であることが実証されています。しかし、最先端のMVCローカル サーチ アルゴリズムには、主に2つの欠点があります。まず、同時に交換する頂点のペアを選択するため、時間がかかります。次に、検索を多様化するためにエッジの重み付け手法を使用していますが、これらのアルゴリズムには重みを減らすメカニズムがありません。これらの問題を解決するために、2段階交換と忘却によるエッジの重み付けという2つの新しい戦略を提案します。2段階交換戦略では、交換する2つの頂点を別々に選択し、2段階で交換を実行します。忘却によるエッジの重み付けの戦略では、カバーされていないエッジの重みが増加するだけでなく、各エッジの重みが定期的に減ります。これら2つの戦略は、NuMVCと呼ばれる新しいMVCローカル サーチ アルゴリズムの設計に使用されます。標準ベンチマークであるDIMACSとBHOSLIBで広範な実験的研究を実施します。NuMVCと最先端のヒューリスティックアルゴリズムを比較した実験では、NuMVCはDIMACSベンチマークで最も近い競合相手であるPLSと少なくとも競合でき、BHOSLIBベンチマークではすべての競合相手を明らかに上回っていることが示されています。また、実験結果によると、NuMVCは、ランダムインスタンスと一部の構造化インスタンスの両方で、最大クリークの現在の最良厳密アルゴリズムよりもはるかに高速に最適解を見つけることがわかりました。さらに、実験分析を通じて、2つの戦略の有効性と実行時の挙動を調査します。
Description Logic Knowledge and Action Bases
記述論理知識ベースとアクションベース
Description logic Knowledge and Action Bases (KAB) are a mechanism for providing both a semantically rich representation of the information on the domain of interest in terms of a description logic knowledge base and actions to change such information over time, possibly introducing new objects. We resort to a variant of DL-Lite where the unique name assumption is not enforced and where equality between objects may be asserted and inferred. Actions are specified as sets of conditional effects, where conditions are based on epistemic queries over the knowledge base (TBox and ABox), and effects are expressed in terms of new ABoxes. In this setting, we address verification of temporal properties expressed in a variant of first-order mu-calculus with quantification across states. Notably, we show decidability of verification, under a suitable restriction inspired by the notion of weak acyclicity in data exchange.
記述論理知識・アクションベース（KAB）は、対象ドメインに関する情報を記述論理知識ベースを用いて意味的に豊かに表現するとともに、時間の経過とともにそのような情報を変化させ、場合によっては新しいオブジェクトを導入するアクションを提供するメカニズムです。本研究では、DL-Liteの派生版を用います。この派生版では、一意名仮定が強制されず、オブジェクト間の等価性が表明および推論されます。アクションは条件付き効果の集合として規定され、条件は知識ベース（TBoxおよびABox）に対する認識論的クエリに基づいており、効果は新しいABoxによって表現されます。この設定において、状態をまたがる量化を伴う一次階ミュー計算の派生版で表現された時間的特性の検証を扱います。特に、データ交換における弱非巡回性の概念に着想を得た適切な制約の下で、検証の決定可能性を示します。
Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality
ゲーム理論的ネットワーク中心性のためのシャプレー値の効率的な計算
The Shapley value—probably the most important normative payoff division scheme in coalitional games—has recently been advocated as a useful measure of centrality in networks. However, although this approach has a variety of real-world applications (including social and organisational networks, biological networks and communication networks), its computational properties have not been widely studied. To date, the only practicable approach to compute Shapley value-based centrality has been via Monte Carlo simulations which are computationally expensive and not guaranteed to give an exact answer. Against this background, this paper presents the first study of the computational aspects of the Shapley value for network centralities. Specifically, we develop exact analytical formulae for Shapley value-based centrality in both weighted and unweighted networks and develop efficient (polynomial time) and exact algorithms based on them. We empirically evaluate these algorithms on two real-life examples (an infrastructure network representing the topology of the Western States Power Grid and a collaboration network from the field of astrophysics) and demonstrate that they deliver significant speedups over the Monte Carlo approach. For instance, in the case of unweighted networks our algorithms are able to return the exact solution about 1600 times faster than the Monte Carlo approximation, even if we allow for a generous 10% error margin for the latter method.
シャプレー値は、おそらく連合ゲームにおける最も重要な規範的な利得分配スキームであり、ネットワークにおける中心性の有用な尺度として最近提唱されています。しかし、このアプローチは現実世界で様々な応用（社会ネットワーク、組織ネットワーク、生物ネットワーク、コミュニケーションネットワークなど）があるにもかかわらず、その計算特性は広く研究されていません。これまで、シャプレー値ベースの中心性を計算する唯一の実用的な方法はモンテカルロシミュレーションでしたが、これは計算コストが高く、正確な答えが得られる保証はありません。このような背景から、本論文では、ネットワーク中心性に対するシャプレー値の計算面に関する初の研究を紹介します。具体的には、重み付きネットワークと重みなしネットワークの両方において、シャプレー値ベースの中心性に関する正確な解析式を開発し、それに基づいて効率的(多項式時間)かつ正確なアルゴリズムを開発します。これらのアルゴリズムを2つの実際の例(Western States Power Gridのトポロジを表すインフラストラクチャネットワークと、天体物理学の分野のコラボレーションネットワーク)で経験的に評価し、モンテカルロ手法に比べて大幅な高速化を実現することを実証しました。たとえば、重みなしネットワークの場合、後者の方法に10%の誤差マージンを許容した場合でも、私たちのアルゴリズムはモンテカルロ近似よりも約1600倍速く正確な解を返すことができます。
Predicting Behavior in Unstructured Bargaining with a Probability Distribution
確率分布を用いた非構造化交渉における行動予測
In experimental tests of human behavior in unstructured bargaining games, typically many joint utility outcomes are found to occur, not just one. This suggests we predict the outcome of such a game as a probability distribution. This is in contrast to what is conventionally done (e.g, in the Nash bargaining solution), which is predict a single outcome. We show how to translate Nash’s bargaining axioms to provide a distribution over outcomes rather than a single outcome. We then prove that a subset of those axioms forces the distribution over utility outcomes to be a power-law distribution. Unlike Nash’s original result, our result holds even if the feasible set is finite. When the feasible set is convex and comprehensive, the mode of the power law distribution is the Harsanyi bargaining solution, and if we require symmetry it is the Nash bargaining solution. However, in general these modes of the joint utility distribution are not the experimentalist’s Bayes-optimal predictions for the joint utility. Nor are the bargains corresponding to the modes of those joint utility distributions the modes of the distribution over bargains in general, since more than one bargain may result in the same joint utility. After introducing distributional bargaining solution concepts, we show how an external regulator can use them to optimally design an unstructured bargaining scenario. Throughout we demonstrate our analysis in computational experiments involving flight rerouting negotiations in the National Airspace System. We emphasize that while our results are formulated for unstructured bargaining, they can also be used to make predictions for noncooperative games where the modeler knows the utility functions of the players over possible outcomes of the game, but does not know the move spaces the players use to determine those outcomes.
非構造化交渉ゲームにおける人間の行動の実験的検証では、通常、1つだけでなく、多数の共同効用結果が発生することが分かっています。これは、このようなゲームの結果を確率分布として予測することを示唆しています。これは、従来行われてきた方法（例えば、ナッシュ交渉解）が単一の結果を予測するのとは対照的です。本稿では、ナッシュの交渉公理を、単一の結果ではなく複数の結果にわたる分布を与えるように変換する方法を示します。次に、これらの公理のサブセットが、効用結果にわたる分布をべき乗分布に強制することを証明します。ナッシュの元の結果とは異なり、本稿の結果は実行可能集合が有限であっても成立します。実行可能集合が凸包的かつ包括的である場合、べき乗分布のモードはハルサニの交渉解であり、対称性を要求する場合はナッシュ交渉解です。しかしながら、一般に、これらの共同効用分布のモードは、実験者による共同効用に関するベイズ最適予測ではありません。また、これらの共同効用分布のモードに対応する取引は、一般的な取引における分配モードとも異なります。なぜなら、複数の取引が同じ共同効用をもたらす可能性があるからです。分配交渉ソリューションの概念を導入した後、外部規制当局がそれらを用いて非構造化交渉シナリオを最適に設計する方法を示します。全体を通して、国家空域システムにおける飛行経路変更交渉を含む計算実験において、私たちの分析を実証します。私たちの結果は非構造化交渉のために定式化されていますが、モデル作成者がゲームの可能な結果に対するプレイヤーの効用関数を知っているものの、プレイヤーがそれらの結果を決定するために使用する移動空間を知らない非協力ゲームの予測にも使用できることを強調します。
Probabilistic Planning for Continuous Dynamic Systems under Bounded Risk
制限リスク下における連続動的システムの確率的計画
This paper presents a model-based planner called the Probabilistic Sulu Planner or the p-Sulu Planner, which controls stochastic systems in a goal directed manner within user-specified risk bounds. The objective of the p-Sulu Planner is to allow users to command continuous, stochastic systems, such as unmanned aerial and space vehicles, in a manner that is both intuitive and safe. To this end, we first develop a new plan representation called a chance-constrained qualitative state plan (CCQSP), through which users can specify the desired evolution of the plant state as well as the acceptable level of risk. An example of a CCQSP statement is “go to A through B within 30 minutes, with less than 0.001% probability of failure.” We then develop the p-Sulu Planner, which can tractably solve a CCQSP planning problem. In order to enable CCQSP planning, we develop the following two capabilities in this paper: 1) risk-sensitive planning with risk bounds, and 2) goal-directed planning in a continuous domain with temporal constraints. The first capability is to ensures that the probability of failure is bounded. The second capability is essential for the planner to solve problems with a continuous state space such as vehicle path planning. We demonstrate the capabilities of the p-Sulu Planner by simulations on two real-world scenarios: the path planning and scheduling of a personal aerial vehicle as well as the space rendezvous of an autonomous cargo spacecraft.
本論文では、確率的Suluプランナー（p-Suluプランナー）と呼ばれるモデルベースのプランナーを紹介します。このプランナーは、ユーザーが指定したリスク範囲内で、確率的システムを目標指向的に制御します。p-Suluプランナーの目的は、無人航空機や宇宙船などの連続的な確率的システムを、ユーザーが直感的かつ安全に制御できるようにすることです。この目的のために、まず、チャンス制約定性状態計画（CCQSP）と呼ばれる新しい計画表現を開発します。これにより、ユーザーはプラント状態の望ましい発展と許容可能なリスクレベルを指定できます。CCQSPステートメントの例としては、「失敗の確率を0.001%未満にして、30分以内にBを経由してAに到達する」などがあります。次に、CCQSP計画問題を適切に解決できるp-Suluプランナーを開発します。CCQSP計画を可能にするために、本稿では、1)リスク限界を伴うリスクに配慮した計画、2)時間的制約を伴う連続領域での目標指向計画、という2つの機能を開発します。最初の機能は、失敗の確率が制限されていることを保証することです。2番目の機能は、プランナーが車両経路計画などの連続状態空間の問題を解くために不可欠です。個人用航空機の経路計画とスケジュール、および自律型貨物宇宙船の宇宙ランデブーという2つの実際のシナリオでシミュレーションを実行し、p-Suluプランナーの機能を実証します。
Optimal Rectangle Packing: An Absolute Placement Approach
最適矩形パッキング：絶対配置アプローチ
We consider the problem of finding all enclosing rectangles of minimum area that can contain a given set of rectangles without overlap. Our rectangle packer chooses the x-coordinates of all the rectangles before any of the y-coordinates. We then transform the problem into a perfect-packing problem with no empty space by adding additional rectangles. To determine the y-coordinates, we branch on the different rectangles that can be placed in each empty position. Our packer allows us to extend the known solutions for a consecutive-square benchmark from 27 to 32 squares. We also introduce three new benchmarks, avoiding properties that make a benchmark easy, such as rectangles with shared dimensions. Our third benchmark consists of rectangles of increasingly high precision. To pack them efficiently, we limit the rectangles’ coordinates and the bounding box dimensions to the set of subset sums of the rectangles’ dimensions. Overall, our algorithms represent the current state-of-the-art for this problem, outperforming other algorithms by orders of magnitude, depending on the benchmark.
与えられた長方形集合を重なり合うことなく包含できる、面積が最小の囲み長方形をすべて見つける問題を考察します。本長方形パッカーは、すべての長方形のx座標を、どのy座標よりも先に選択します。次に、長方形を追加することで、この問題を空きスペースのない完全なパッキング問題に変換します。y座標を決定するために、各空き位置に配置可能な異なる長方形を分岐させる。本パッカーにより、連続正方形ベンチマークの既知の解を27個から32個に拡張することができます。また、共通の寸法を持つ長方形など、ベンチマークを容易にする特性を回避した3つの新しいベンチマークも導入します。3つ目のベンチマークは、精度が徐々に高くなる長方形で構成されます。これらの長方形を効率的にパッキングするため、長方形の座標と境界ボックスの寸法を、長方形の寸法のサブセット和の集合に制限します。全体として、本アルゴリズムはこの問題における最新のアルゴリズムであり、ベンチマークによっては他のアルゴリズムを桁違いに上回る性能を示す。
Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs
Dec-POMDPにおける高速最適計画のための増分クラスタリングと拡張
This article presents the state-of-the-art in optimal solution methods for decentralized partially observable Markov decision processes (Dec-POMDPs), which are general models for collaborative multiagent planning under uncertainty. Building off the generalized multiagent A* (GMAA*) algorithm, which reduces the problem to a tree of one-shot collaborative Bayesian games (CBGs), we describe several advances that greatly expand the range of Dec-POMDPs that can be solved optimally. First, we introduce lossless incremental clustering of the CBGs solved by GMAA*, which achieves exponential speedups without sacrificing optimality. Second, we introduce incremental expansion of nodes in the GMAA* search tree, which avoids the need to expand all children, the number of which is in the worst case doubly exponential in the node’s depth. This is particularly beneficial when little clustering is possible. In addition, we introduce new hybrid heuristic representations that are more compact and thereby enable the solution of larger Dec-POMDPs. We provide theoretical guarantees that, when a suitable heuristic is used, both incremental clustering and incremental expansion yield algorithms that are both complete and search equivalent. Finally, we present extensive empirical results demonstrating that GMAA*-ICE, an algorithm that synthesizes these advances, can optimally solve Dec-POMDPs of unprecedented size.
本稿では、不確実性下での協調型マルチエージェント計画の一般的なモデルである、分散型部分観測マルコフ決定プロセス（Dec-POMDP）の最適解法の最先端の手法を紹介します。問題をワンショット協調ベイズゲーム（CBG）のツリーに簡略化する一般化マルチエージェントA*（GMAA*）アルゴリズムを基に、最適に解くことができるDec-POMDPの範囲を大幅に拡大するいくつかの進歩について説明します。まず、GMAA*によって解決されるCBGのロスレス増分クラスタリングを導入します。これにより、最適性を犠牲にすることなく指数関数的な高速化を実現します。次に、GMAA*検索ツリーのノードの増分拡張を導入します。これにより、最悪の場合、ノードの深さに対して二重指数関数的になる子をすべて拡張する必要がなくなります。これは、クラスタリングがほとんど不可能な場合に特に有益です。さらに、よりコンパクトな新しいハイブリッド ヒューリスティック表現を導入し、より大きなDec-POMDPの解決を可能にします。適切なヒューリスティックを使用すると、増分クラスタリングと増分拡張の両方で、完全かつ検索と同等のアルゴリズムが得られるという理論的な保証を提供します。最後に、これらの進歩を統合したアルゴリズムであるGMAA*-ICEが、前例のない規模のDec-POMDPを最適に解くことができることを示す広範な実験結果を示します。
Qualitative Order of Magnitude Energy-Flow-Based Failure Modes and Effects Analysis
エネルギーフローに基づく定性的規模オーダーの故障モード影響分析
This paper presents a structured power and energy-flow-based qualitative modelling approach that is applicable to a variety of system types including electrical and fluid flow. The modelling is split into two parts.Power flow is a global phenomenon and is therefore naturally represented and analysed by a network comprised of the relevant structural elements from the components of a system. The power flow analysis is a platform for higher-level behaviour prediction of energy related aspects using local component behaviour models to capture a state-based representation with a global time. The primary application is Failure Modes and Effects Analysis (FMEA) and a form of exaggeration reasoning is used, combined with an order of magnitude representation to derive the worst case failure modes. The novel aspects of the work are an order of magnitude(OM) qualitative network analyser to represent any power domain and topology, including multiple power sources, a feature that was not required for earlier specialised electrical versions of the approach. Secondly, the representation of generalised energy related behaviour as state-based local models is presented as a modelling strategy that can be more vivid and intuitive for a range of topologically complex applications than qualitative equation-based representations.The two-level modelling strategy allows the broad system behaviour coverage of qualitative simulation to be exploited for the FMEA task, while limiting the difficulties of qualitative ambiguity explanation that can arise from abstracted numerical models. We have used the method to support an automated FMEA system with examples of an aircraft fuel system and domestic a heating system discussed in this paper.
本論文では、電気や流体の流れを含むさまざまなシステム タイプに適用可能な構造化された電力およびエネルギー フロー ベースの定性的なモデリング手法を紹介します。モデリングは2つの部分に分かれています。電力フローはグローバルな現象であるため、当然のことながら、システムのコンポーネントの関連する構造要素で構成されたネットワークによって表現および解析されます。電力フロー解析は、ローカル コンポーネントの動作モデルを使用してグローバル時間による状態ベースの表現を捕捉し、エネルギー関連の側面の高レベルな動作予測を行うプラットフォームです。主な用途は故障モード影響解析(FMEA)であり、ある種の誇張推論が桁違い表現と組み合わせて使用され、最悪の故障モードが導出されます。本研究の新しい側面は、桁違い(OM)の定性的なネットワーク アナライザーを使用して、複数の電源を含むあらゆる電力ドメインとトポロジーを表現できることです。これは、以前の専門的な電気バージョンのアプローチでは必要とされなかった機能です。第二に、一般化されたエネルギー関連挙動を状態ベースのローカルモデルとして表現することは、定性的な方程式ベースの表現よりも、位相的に複雑なさまざまなアプリケーションに対して、より鮮明で直感的なモデリング戦略として提示されます。2レベルのモデリング戦略により、抽象化された数値モデルから生じる可能性のある定性的な曖昧性の説明の困難さを抑えながら、定性シミュレーションの広範なシステム挙動カバレッジをFMEAタスクに活用できます。この手法を使用して、本稿で説明する航空機燃料システムと家庭用暖房システムを例に、自動化されたFMEAシステムをサポートしました。
A Hybrid LP-RPG Heuristic for Modelling Numeric Resource Flows in Planning
計画における数値資源フローのモデリングのためのハイブリッドLP-RPGヒューリスティック
Although the use of metric fluents is fundamental to many practical planning problems, the study of heuristics to support fully automated planners working with these fluents remains relatively unexplored. The most widely used heuristic is the relaxation of metric fluents into interval-valued variables — an idea first proposed a decade ago. Other heuristics depend on domain encodings that supply additional information about fluents, such as capacity constraints or other resource-related annotations. A particular challenge to these approaches is in handling interactions between metric fluents that represent exchange, such as the transformation of quantities of raw materials into quantities of processed goods, or trading of money for materials. The usual relaxation of metric fluents is often very poor in these situations, since it does not recognise that resources, once spent, are no longer available to be spent again.We present a heuristic for numeric planning problems building on the propositional relaxed planning graph, but using a mathematical program for numeric reasoning. We define a class of producer–consumer planning problems and demonstrate how the numeric constraints in these can be modelled in a mixed integer program (MIP). This MIP is then combined with a metric Relaxed Planning Graph (RPG) heuristic to produce an integrated hybrid heuristic. The MIP tracks resource use more accurately than the usual relaxation, but relaxes the ordering of actions, while the RPG captures the causal propositional aspects of the problem. We discuss how these two components interact to produce a single unified heuristic and go on to explore how further numeric features of planning problems can be integrated into the MIP. We show that encoding a limited subset of the propositional problem to augment the MIP can yield more accurate guidance, partly by exploiting structure such as propositional landmarks and propositional resources. Our results show that the use of this heuristic enhances scalability on problems where numeric resource interaction is key in finding a solution.
計量フルエントの使用は多くの実用的な計画問題において基本的なものですが、これらのフルエントを扱う完全自動プランナーを支援するヒューリスティックの研究は比較的未開拓です。最も広く用いられているヒューリスティックは、計量フルエントを区間値変数に緩和するものです。これは10年前に初めて提案されたアイデアです。他のヒューリスティックは、キャパシティ制約やその他のリソース関連の注釈など、フルエントに関する追加情報を提供するドメインエンコーディングに依存しています。これらのアプローチの特に大きな課題は、原材料の量から加工品の量への変換や、金銭と材料の交換など、交換を表す計量フルエント間の相互作用の処理です。通常の計量フルエントの緩和は、これらの状況では非常に不十分であることが多いです。なぜなら、一度消費されたリソースは再び消費できないことを認識していないからです。本稿では、命題緩和計画グラフを基盤とし、数値推論には数学的プログラムを用いた、数値計画問題のためのヒューリスティックを提示します。我々は生産者-消費者計画問題のクラスを定義し、これらの問題における数値制約を混合整数計画法(MIP)でモデル化する方法を示します。次に、このMIPをメトリック緩和計画グラフ(RPG)ヒューリスティックと組み合わせて、統合ハイブリッド ヒューリスティックを生成します。MIPは通常の緩和法よりも正確にリソース使用を追跡しますが、アクションの順序付けを緩和します。一方、RPGは問題の因果的な命題的側面を捉えます。これら2つのコンポーネントがどのように相互作用して単一の統合ヒューリスティックを生成するかについて説明し、計画問題のさらなる数値的特徴をMIPにどのように統合できるかを検討します。命題問題の限定されたサブセットをエンコードしてMIPを拡張すると、命題ランドマークや命題リソースなどの構造を活用することで、より正確なガイダンスが得られることを示します。結果は、このヒューリスティックの使用により、数値リソースの相互作用が解を見つける鍵となる問題においてスケーラビリティが向上することを示しています。
Boolean Equi-propagation for Concise and Efficient SAT Encodings of Combinatorial Problems
組み合わせ問題の簡潔かつ効率的なSATエンコーディングのためのブール等伝播法
We present an approach to propagation-based SAT encoding of combinatorial problems, Boolean equi-propagation, where constraints are modeled as Boolean functions which propagate information about equalities between Boolean literals. This information is then applied to simplify the CNF encoding of the constraints. A key factor is that considering only a small fragment of a constraint model at one time enables us to apply stronger, and even complete, reasoning to detect equivalent literals in that fragment. Once detected, equivalences apply to simplify the entire constraint model and facilitate further reasoning on other fragments. Equi-propagation in combination with partial evaluation and constraint simplification provide the foundation for a powerful approach to SAT-based finite domain constraint solving. We introduce a tool called BEE (Ben-Gurion Equi-propagation Encoder) based on these ideas and demonstrate for a variety of benchmarks that our approach leads to a considerable reduction in the size of CNF encodings and subsequent speed-ups in SAT solving times.
組合せ問題の伝播ベースのSAT符号化へのアプローチであるブール等伝播を提示します。このアプローチでは、制約はブール関数としてモデル化され、ブール関数はブールリテラル間の等式に関する情報を伝播します。この情報は、制約のCNF符号化を簡素化するために適用されます。重要な要素は、制約モデルのごく一部を一度に検討するだけで、より強力で、さらには完全な推論を適用して、その部分に含まれる等価なリテラルを検出できる点です。等価性が検出されると、制約モデル全体が簡素化され、他の部分における推論が容易になります。等価伝播は、部分評価および制約の簡素化と組み合わせることで、SATベースの有限領域制約解決に対する強力なアプローチの基盤となります。これらのアイデアに基づいて、BEE（Ben-Gurion Equi-propagation Encoder）と呼ばれるツールを紹介し、様々なベンチマークにおいて、このアプローチがCNFエンコーディングのサイズを大幅に削減し、SAT解決時間を短縮することを実証します。
Parameterized Complexity Results for Exact Bayesian Network Structure Learning
正確なベイジアンネットワーク構造学習のためのパラメータ化された複雑性の結果
Bayesian network structure learning is the notoriously difficult problem of discovering a Bayesian network that optimally represents a given set of training data. In this paper we study the computational worst-case complexity of exact Bayesian network structure learning under graph theoretic restrictions on the (directed) super-structure. The super-structure is an undirected graph that contains as subgraphs the skeletons of solution networks. We introduce the directed super-structure as a natural generalization of its undirected counterpart. Our results apply to several variants of score-based Bayesian network structure learning where the score of a network decomposes into local scores of its nodes.Results: We show that exact Bayesian network structure learning can be carried out in non-uniform polynomial time if the super-structure has bounded treewidth, and in linear time if in addition the super-structure has bounded maximum degree. Furthermore, we show that if the directed super-structure is acyclic, then exact Bayesian network structure learning can be carried out in quadratic time. We complement these positive results with a number of hardness results. We show that both restrictions (treewidth and degree) are essential and cannot be dropped without loosing uniform polynomial time tractability (subject to a complexity-theoretic assumption). Similarly, exact Bayesian network structure learning remains NP-hard for “almost acyclic” directed super-structures. Furthermore, we show that the restrictions remain essential if we do not search for a globally optimal network but aim to improve a given network by means of at most k arc additions, arc deletions, or arc reversals (k-neighborhood local search).
ベイジアンネットワーク構造学習は、与えられた訓練データセットを最適に表現するベイジアンネットワークを発見するという、非常に困難な問題として知られています。本稿では、（有向）スーパー構造に対するグラフ理論的制約の下で、ベイジアンネットワーク構造の厳密な学習における計算量の最悪ケースを考察します。スーパー構造とは、解ネットワークのスケルトンをサブグラフとして含む無向グラフです。本稿では、無向スーパー構造の自然な一般化として、有向スーパー構造を導入します。本研究の結果は、ネットワークのスコアをノードのローカルスコアに分解する、スコアベースのベイジアンネットワーク構造学習のいくつかのバリエーションに適用されます。結果：スーパー構造のツリー幅が制限されている場合、ベイジアンネットワーク構造の厳密な学習は非一様多項式時間で実行でき、さらにスーパー構造の最大次数が制限されている場合は線形時間で実行できることを示します。さらに、有向スーパー構造が非巡回である場合、ベイジアンネットワーク構造の厳密な学習は二次時間で実行できることを示します。これらの肯定的な結果を、いくつかの困難性の結果で補完します。木幅と次数という両方の制約は本質的であり、一様多項式時間での扱いやすさを失うことなく削除することはできないことを示す（計算量理論的仮定に従う）。同様に、ベイジアンネットワークの正確な構造学習は、「ほぼ非巡回」な有向スーパー構造に対してNP困難のままです。さらに、大域的に最適なネットワークを探索するのではなく、最大k回のアーク追加、アーク削除、またはアーク反転（k近傍局所探索）によって与えられたネットワークを改善することを目指す場合も、これらの制約は本質的であることを示す。
Toward Supervised Anomaly Detection
教師あり異常検出に向けて
Anomaly detection is being regarded as an unsupervised learning task as anomalies stem from adversarial or unlikely events with unknown distributions. However, the predictive performance of purely unsupervised anomaly detection often fails to match the required detection rates in many tasks and there exists a need for labeled data to guide the model generation. Our first contribution shows that classical semi-supervised approaches, originating from a supervised classifier, are inappropriate and hardly detect new and unknown anomalies. We argue that semi-supervised anomaly detection needs to ground on the unsupervised learning paradigm and devise a novel algorithm that meets this requirement. Although being intrinsically non-convex, we further show that the optimization problem has a convex equivalent under relatively mild assumptions. Additionally, we propose an active learning strategy to automatically filter candidates for labeling. In an empirical study on network intrusion detection data, we observe that the proposed learning methodology requires much less labeled data than the state-of-the-art, while achieving higher detection accuracies.
異常検出は、分布が未知の敵対的または起こりそうもないイベントに起因して発生するため、教師なし学習タスクとみなされています。しかし、純粋な教師なし異常検出の予測性能は、多くのタスクで要求される検出率に一致しないことが多く、モデル生成を導くためのラベル付きデータが必要です。私たちの最初の貢献は、教師あり分類器に由来する古典的な半教師ありアプローチが不適切であり、新しい未知の異常をほとんど検出できないことを示しています。私たちは、半教師あり異常検出は教師なし学習パラダイムを基盤とし、この要件を満たす新しいアルゴリズムを考案する必要があると主張します。本質的に非凸ではありますが、比較的穏やかな仮定の下では、最適化問題には凸問題に相当するものがあることをさらに示します。さらに、ラベル付けの候補を自動的にフィルタリングする能動学習戦略を提案します。ネットワーク侵入検知データに関する実証的研究では、提案された学習方法では、最先端の方法よりもラベル付けされたデータがはるかに少なくて済むにもかかわらず、より高い検知精度が達成されることがわかりました。
Integrative Semantic Dependency Parsing via Efficient Large-scale Feature Selection
統合的な意味的依存関係解析効率的な大規模特徴選択
Semantic parsing, i.e., the automatic derivation of meaning representation such as an instantiated predicate-argument structure for a sentence, plays a critical role in deep processing of natural language. Unlike all other top systems of semantic dependency parsing that have to rely on a pipeline framework to chain up a series of submodels each specialized for a specific subtask, the one presented in this article integrates everything into one model, in hopes of achieving desirable integrity and practicality for real applications while maintaining a competitive performance. This integrative approach tackles semantic parsing as a word pair classification problem using a maximum entropy classifier. We leverage adaptive pruning of argument candidates and large-scale feature selection engineering to allow the largest feature space ever in use so far in this field, it achieves a state-of-the-art performance on the evaluation data set for CoNLL-2008 shared task, on top of all but one top pipeline system, confirming its feasibility and effectiveness.
意味解析、すなわち文の述語項構造のインスタンス化といった意味表現の自動導出は、自然言語の深層処理において重要な役割を果たします。意味係り受け解析の他の主要なシステムはすべて、特定のサブタスクに特化した一連のサブモデルをパイプラインフレームワークに連結する必要がありましたが、本稿で紹介するシステムは、すべてを1つのモデルに統合することで、競争力のあるパフォーマンスを維持しながら、実アプリケーションで望ましい整合性と実用性を実現することを目指しています。この統合的なアプローチは、最大エントロピー分類器を用いた単語ペア分類問題として意味解析を扱います。項候補の適応的枝刈りと大規模な特徴選択エンジニアリングを活用することで、この分野でこれまで用いられた中で最大の特徴空間を実現し、CoNLL-2008共有タスクの評価データセットにおいて、1つを除くすべての主要なパイプラインシステム上で最先端のパフォーマンスを達成し、その実現可能性と有効性を確認しました。
Generating Extractive Summaries of Scientific Paradigms
科学的パラダイムの抽出要約の生成
Researchers and scientists increasingly find themselves in the position of having to quickly understand large amounts of technical material. Our goal is to effectively serve this need by using bibliometric text mining and summarization techniques to generate summaries of scientific literature. We show how we can use citations to produce automatically generated, readily consumable, technical extractive summaries. We first propose C-LexRank, a model for summarizing single scientific articles based on citations, which employs community detection and extracts salient information-rich sentences. Next, we further extend our experiments to summarize a set of papers, which cover the same scientific topic. We generate extractive summaries of a set of Question Answering (QA) and Dependency Parsing (DP) papers, their abstracts, and their citation sentences and show that citations have unique information amenable to creating a summary.
研究者や科学者は、大量の技術資料を迅速に理解しなければならない状況にますます直面しています。我々の目標は、計量書誌学的テキストマイニングと要約技術を用いて科学文献の要約を生成することで、このニーズに効果的に応えることです。引用文献を用いて、自動生成され、容易に利用可能な技術抽出要約を作成する方法を示す。まず、引用文献に基づいて単一の科学論文を要約するモデルであるC-LexRankを提案します。これは、コミュニティ検出を用いて、重要な情報に富んだ文を抽出します。次に、実験をさらに拡張し、同じ科学トピックを扱う論文セットを要約します。質問応答（QA）論文と依存関係解析（DP）論文のセット、その抄録、および引用文の抽出要約を生成し、引用文献が要約作成に適した固有の情報を持っていることを示す。
Undominated Groves Mechanisms
非劣グローブ機構
The family of Groves mechanisms, which includes the well-known VCG mechanism (also known as the Clarke mechanism), is a family of efficient and strategy-proof mechanisms. Unfortunately, the Groves mechanisms are generally not budget balanced. That is, under such mechanisms, payments may flow into or out of the system of the agents, resulting in deficits or reduced utilities for the agents. We consider the following problem: within the family of Groves mechanisms, we want to identify mechanisms that give the agents the highest utilities, under the constraint that these mechanisms must never incur deficits.We adopt a prior-free approach. We introduce two general measures for comparing mechanisms in prior-free settings. We say that a non-deficit Groves mechanism M individually dominates another non-deficit Groves mechanism M’ if for every type profile, every agent’s utility under M is no less than that under M’, and this holds with strict inequality for at least one type profile and one agent. We say that a non-deficit Groves mechanism M collectively dominates another non-deficit Groves mechanism M’ if for every type profile, the agents’ total utility under M is no less than that under M’, and this holds with strict inequality for at least one type profile. The above definitions induce two partial orders on non-deficit Groves mechanisms. We study the maximal elements corresponding to these two partial orders, which we call the individually undominated mechanisms and the collectively undominated mechanisms, respectively.
よく知られているVCGメカニズム（クラークメカニズムとしても知られる）を含むグローブメカニズムファミリーは、効率的で戦略証明不可能なメカニズムファミリーです。残念ながら、グローブメカニズムは一般的に予算均衡が取れていません。つまり、このようなメカニズムでは、支払いがエージェントのシステムに流入または流出する可能性があり、その結果、エージェントの赤字または効用の低下が生じます。我々は以下の問題を考察する：グローブスメカニズムのファミリーの中で、これらのメカニズムが決して欠陥を招いてはならないという制約の下で、エージェントに最高の効用を与えるメカニズムを特定します。我々は事前制約のないアプローチを採用します。事前制約のない設定でメカニズムを比較するための2つの一般的な尺度を導入します。あらゆるタイプ プロファイルについて、Mの下でのすべてのエージェントの効用がM’の下での効用以上であり、少なくとも1つのタイプ プロファイルと1つのエージェントについて厳密な不等式が成り立つ場合、非欠陥グローブスメカニズムMは個別に別の非欠陥グローブスメカニズムM’を支配するという。あらゆるタイプ プロファイルについて、Mの下でのエージェントの合計効用がM’の下での効用以上であり、少なくとも1つのタイプ プロファイルについて厳密な不等式が成り立つ場合、非欠陥グローブスメカニズムMは別の非欠陥グローブスメカニズムM’を集合的に支配するという。上記の定義は、非欠陥グローブスメカニズムに2つの部分順序を誘導します。我々は、これら2つの半順序に対応する最大元を研究し、それぞれを個別非優越メカニズムと集団非優越メカニズムと呼ぶ。
Short and Long Supports for Constraint Propagation
制約伝播のための短サポートと長サポート
Special-purpose constraint propagation algorithms frequently make implicit use of short supports — by examining a subset of the variables, they can infer support (a justification that a variable-value pair may still form part of an assignment that satisfies the constraint) for all other variables and values and save substantial work — but short supports have not been studied in their own right. The two main contributions of this paper are the identification of short supports as important for constraint propagation, and the introduction of HaggisGAC, an efficient and effective general purpose propagation algorithm for exploiting short supports. Given the complexity of HaggisGAC, we present it as an optimised version of a simpler algorithm ShortGAC. Although experiments demonstrate the efficiency of ShortGAC compared with other general-purpose propagation algorithms where a compact set of short supports is available, we show theoretically and experimentally that HaggisGAC is even better. We also find that HaggisGAC performs better than GAC-Schema on full-length supports. We also introduce a variant algorithm HaggisGAC-Stable, which is adapted to avoid work on backtracking and in some cases can be faster and have significant reductions in memory use. All the proposed algorithms are excellent for propagating disjunctions of constraints. In all experiments with disjunctions we found our algorithms to be faster than Constructive Or and GAC-Schema by at least an order of magnitude, and up to three orders of magnitude.
特殊な制約伝播アルゴリズムは、短いサポートを暗黙的に使用することがよくあります。つまり、変数のサブセットを調べることで、他のすべての変数と値のサポート（変数と値のペアが、制約を満たす割り当ての一部を形成している可能性があるという根拠）を推論し、作業を大幅に節約できます。しかし、短いサポート自体は研究されていません。本論文の主な貢献は、制約伝播にとって短いサポートが重要であることを特定したことと、短いサポートを活用するための効率的で効果的な汎用伝播アルゴリズムであるHaggisGACを導入したことです。HaggisGACの複雑さを考慮し、より単純なアルゴリズムShortGACの最適化バージョンとしてHaggisGACを提示します。実験では、コンパクトな短いサポートセットが利用可能な他の汎用伝播アルゴリズムと比較してShortGACの効率が実証されていますが、HaggisGACはさらに優れていることを理論的かつ実験的に示します。また、HaggisGACは、全長のサポートに対してGAC-Schemaよりも優れたパフォーマンスを発揮することもわかりました。また、バックトラック処理を回避するように適応され、場合によっては高速化とメモリ使用量の大幅な削減を実現するバリアントアルゴリズムHaggisGAC-Stableも導入します。提案されたアルゴリズムはすべて、制約の論理和の伝播に優れています。論理和を用いたすべての実験において、私たちのアルゴリズムはConstructive OrやGAC-Schemaよりも少なくとも1桁、最大3桁高速であることがわかりました。