Journal of Artificial Intelligence Resarch Vol. 28 (2007)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。
Consistency and Random Constraint Satisfaction Models
一貫性とランダム制約充足モデル
In this paper, we study the possibility of designing non-trivial random CSP models by exploiting the intrinsic connection between structures and typical-case hardness. We show that constraint consistency, a notion that has been developed to improve the efficiency of CSP algorithms, is in fact the key to the design of random CSP models that have interesting phase transition behavior and guaranteed exponential resolution complexity without putting much restriction on the parameter of constraint tightness or the domain size of the problem. We propose a very flexible framework for constructing problem instances withinteresting behavior and develop a variety of concrete methods to construct specific random CSP models that enforce different levels of constraint consistency. A series of experimental studies with interesting observations are carried out to illustrate the effectiveness of introducing structural elements in random instances, to verify the robustness of our proposal, and to investigate features of some specific models based on our framework that are highly related to the behavior of backtracking search algorithms.
本稿では、構造と典型的ケースの困難性との間の本質的な関係を利用することで、非自明なランダムCSPモデルの設計可能性を検討します。CSPアルゴリズムの効率性を向上させるために開発された概念である制約一貫性は、制約の厳密さのパラメータや問題の領域サイズに大きな制限を課すことなく、興味深い相転移挙動と保証された指数関数的解決複雑性を備えたランダムCSPモデルを設計するための鍵となることを示す。興味深い挙動を示す問題インスタンスを構築するための非常に柔軟なフレームワークを提案し、異なるレベルの制約一貫性を強制する特定のランダムCSPモデルを構築するための様々な具体的な手法を開発します。ランダムインスタンスに構造要素を導入することの有効性を示し、提案の堅牢性を検証し、バックトラッキング探索アルゴリズムの挙動と密接に関連する、本フレームワークに基づくいくつかの特定のモデルの特徴を調査するために、興味深い観察を伴う一連の実験研究を実施します。
The Strategy-Proofness Landscape of Merging
マージの戦略証明性ランドスケープ
Merging operators aim at defining the beliefs/goals of a group of agents from the beliefs/goals of each member of the group. Whenever an agent of the group has preferences over the possible results of the merging process (i.e., the possible merged bases), she can try to rig the merging process by lying on her true beliefs/goals if this leads to better merged base according to her point of view. Obviously, strategy-proof operators are highly desirable in order to guarantee equity among agents even when some of them are not sincere. In this paper, we draw the strategy-proof landscape for many merging operators from the literature, including model-based ones and formula-based ones. Both the general case and several restrictions on the merging process are considered.
マージ演算子は、エージェント集団の信念／目標を、集団の各メンバーの信念／目標から定義します。集団内のエージェントがマージプロセスの可能な結果（すなわち、可能なマージベース）に対して選好を持つ場合、そのエージェントは、自身の視点から見てより良いマージベースにつながるのであれば、真の信念／目標を偽ってマージプロセスを操作しようとする可能性があります。明らかに、一部のエージェントが誠実でない場合でも、エージェント間の公平性を保証するためには、戦略不可能な演算子が非常に望ましい。本稿では、モデルベースや数式ベースを含む文献から、多くのマージ演算子の戦略不可能なランドスケープを描く。一般的なケースと、マージプロセスに対するいくつかの制約の両方を考慮します。
Abstract Reasoning for Planning and Coordination
計画と調整のための抽象推論
The judicious use of abstraction can help planning agents to identify key interactions between actions, and resolve them, without getting bogged down in details. However, ignoring the wrong details can lead agents into building plans that do not work, or into costly backtracking and replanning once overlooked interdependencies come to light. We claim that associating systematically-generated summary information with plans’ abstract operators can ensure plan correctness, even for asynchronously-executed plans that must be coordinated across multiple agents, while still achieving valuable efficiency gains. In this paper, we formally characterize hierarchical plans whose actions have temporal extent, and describe a principled method for deriving summarized state and metric resource information for such actions. We provide sound and complete algorithms, along with heuristics, to exploit summary information during hierarchical refinement planning and plan coordination. Our analyses and experiments show that, under clearcut and reasonable conditions, using summary information can speed planning as much as doubly exponentially even for plans involving interacting subproblems.
抽象化を適切に使用することで、プランニングエージェントはアクション間の重要な相互作用を識別し、詳細にとらわれることなくそれらを解決できるようになります。しかし、誤った詳細を無視すると、エージェントが機能しないプランを作成したり、見落とされていた相互依存関係が明らかになったときにコストのかかるバックトラッキングと再プランニングを実行したりする可能性があります。体系的に生成された要約情報をプランの抽象演算子に関連付けることで、複数のエージェント間で調整する必要がある非同期実行プランであっても、プランの正確性を保証し、貴重な効率性の向上を実現できると主張します。本稿では、アクションが時間的範囲を持つ階層型プランを正式に特徴付け、そのようなアクションの要約された状態およびメトリックリソース情報を導出するための原理的な方法について説明します。階層的な詳細化プランニングとプラン調整中に要約情報を活用するための健全で完全なアルゴリズムとヒューリスティックを提供します。我々の分析と実験は、明確かつ合理的な条件下では、要約情報を用いることで、相互作用する部分問題を含む計画であっても、計画立案を2倍の指数関数的に高速化できることを示しています。
Discovering Classes of Strongly Equivalent Logic Programs
強等価論理プログラムのクラスの発見
In this paper we apply computer-aided theorem discovery technique to discover theorems about strongly equivalent logic programs under the answer set semantics. Our discovered theorems capture new classes of strongly equivalent logic programs that can lead to new program simplification rules that preserve strong equivalence. Specifically, with the help of computers, we discovered exact conditions that capture the strong equivalence between a rule and the empty set, between two rules, between two rules and one of the two rules, between two rules and another rule, and between three rules and two of the three rules.
本論文では、コンピュータ支援定理発見技術を適用し、解答集合意味論の下での強同値論理プログラムに関する定理を発見します。発見された定理は、強同値性を維持する新しいプログラム簡素化規則につながる、強同値論理プログラムの新しいクラスを捉えています。具体的には、コンピュータの助けを借りて、規則と空集合、2つの規則間、2つの規則と2つの規則のうちの1つの規則間、2つの規則と別の規則間、そして3つの規則と3つの規則のうちの2つの規則間の強同値性を正確に捉える条件を発見した。
Bin Completion Algorithms for Multicontainer Packing, Knapsack, and Covering Problems
複数コンテナのパッキング、ナップサック、被覆問題のためのビン補完アルゴリズム
Many combinatorial optimization problems such as the bin packing and multiple knapsack problems involve assigning a set of discrete objects to multiple containers. These problems can be used to model task and resource allocation problems in multi-agent systems and distributed systms, and can also be found as subproblems of scheduling problems. We propose bin completion, a branch-and-bound strategy for one-dimensional, multicontainer packing problems. Bin completion combines a bin-oriented search space with a powerful dominance criterion that enables us to prune much of the space. The performance of the basic bin completion framework can be enhanced by using a number of extensions, including nogood-based pruning techniques that allow further exploitation of the dominance criterion. Bin completion is applied to four problems: multiple knapsack, bin covering, min-cost covering, and bin packing. We show that our bin completion algorithms yield new, state-of-the-art results for the multiple knapsack, bin covering, and min-cost covering problems, outperforming previous algorithms by several orders of magnitude with respect to runtime on some classes of hard, random problem instances. For the bin packing problem, we demonstrate significant improvements compared to most previous results, but show that bin completion is not competitive with current state-of-the-art cutting-stock based approaches.
ビンパッキング問題や多重ナップサック問題など、多くの組み合わせ最適化問題は、離散オブジェクトの集合を複数のコンテナに割り当てることを伴っています。これらの問題は、マルチエージェントシステムや分散システムにおけるタスクおよびリソース割り当て問題のモデル化に利用でき、スケジューリング問題の部分問題としても捉えられます。本稿では、1次元の複数コンテナパッキング問題に対する分枝限定法であるビン補完を提案します。ビン補完は、ビン指向の探索空間と、空間の大部分を枝刈りすることを可能にする強力な優位性基準を組み合わせたものです。基本的なビン補完フレームワークの性能は、優位性基準をさらに活用できるnogoodベースの枝刈り手法など、様々な拡張を用いることで向上させることができます。ビン補完は、多重ナップサック問題、ビン被覆問題、最小コスト被覆問題、ビンパッキング問題の4つの問題に適用されます。本稿では、本ビン補完アルゴリズムが、多重ナップサック問題、ビン被覆問題、最小コスト被覆問題において、最新の新しい結果をもたらし、いくつかの困難なランダム問題インスタンスにおいて、実行時間に関して従来のアルゴリズムを数桁上回る性能を示すことを示します。ビンパッキング問題において、我々はこれまでのほとんどの結果と比較して大幅な改善を示したが、ビン補完は現在の最先端のカッティングストックベースのアプローチと競合できないことを示す。
Closed-Loop Learning of Visual Control Policies
視覚制御ポリシーの閉ループ学習
In this paper we present a general, flexible framework for learning mappings from images to actions by interacting with the environment. The basic idea is to introduce a feature-based image classifier in front of a reinforcement learning algorithm. The classifier partitions the visual space according to the presence or absence of few highly informative local descriptors that are incrementally selected in a sequence of attempts to remove perceptual aliasing. We also address the problem of fighting overfitting in such a greedy algorithm. Finally, we show how high-level visual features can be generated when the power of local descriptors is insufficient for completely disambiguating the aliased states. This is done by building a hierarchy of composite features that consist of recursive spatial combinations of visual features. We demonstrate the efficacy of our algorithms by solving three visual navigation tasks and a visual version of the classical “Car on the Hill” control problem.
本論文では、環境との相互作用を通して画像から行動へのマッピングを学習するための、汎用的かつ柔軟なフレームワークを提示します。基本的な考え方は、強化学習アルゴリズムの前に特徴ベースの画像分類器を導入することです。分類器は、知覚エイリアシングを除去するための一連の試行において段階的に選択される、情報量の多い少数の局所記述子の有無に基づいて視覚空間を分割します。また、このような貪欲アルゴリズムにおける過剰適合の問題にも対処します。最後に、局所記述子のパワーがエイリアシングされた状態を完全に解消するのに不十分な場合に、高レベルの視覚特徴を生成する方法を示す。これは、視覚特徴の再帰的な空間的組み合わせからなる複合特徴の階層を構築することによって行われます。3つの視覚ナビゲーションタスクと、古典的な「丘の上の車」制御問題の視覚バージョンを解くことで、本アルゴリズムの有効性を実証します。
Supporting Temporal Reasoning by Mapping Calendar Expressions to Minimal Periodic Sets
カレンダー式を最小周期集合にマッピングすることによる時間的推論のサポート
In the recent years several research efforts have focused on the concept of time granularity and its applications. A first stream of research investigated the mathematical models behind the notion of granularity and the algorithms to manage temporal data based on those models. A second stream of research investigated symbolic formalisms providing a set of algebraic operators to define granularities in a compact and compositional way. However, only very limited manipulation algorithms have been proposed to operate directly on the algebraic representation making it unsuitable to use the symbolic formalisms in applications that need manipulation of granularities.This paper aims at filling the gap between the results from these two streams of research, by providing an efficient conversion from the algebraic representation to the equivalent low-level representation based on the mathematical models. In addition, the conversion returns a minimal representation in terms of period length. Our results have a majorpractical impact: users can more easily define arbitrary granularities in terms of algebraic operators, and then access granularity reasoning and other services operating efficiently on the equivalent, minimal low-level representation. As an example, we illustrate the application to temporal constraint reasoning with multiple granularities.From a technical point of view, we propose an hybrid algorithm that interleaves the conversion of calendar subexpressions into periodical sets with the minimization of the period length. The algorithm returns set-based granularity representations having minimal period length, which is the most relevant parameter for the performance of the considered reasoning services. Extensive experimental work supports the techniques used in the algorithm, and shows the efficiency and effectiveness of the algorithm.
近年、いくつかの研究努力が時間粒度の概念とその応用に焦点を当ててきました。最初の研究の流れでは、粒度の概念の背後にある数学モデルと、それらのモデルに基づいて時間データを管理するアルゴリズムを調査しました。2番目の研究の流れでは、粒度をコンパクトかつ構成的な方法で定義するための代数演算子のセットを提供する記号形式主義を調査しました。しかし、代数表現を直接操作する操作アルゴリズムはごく限られているため、粒度を操作する必要があるアプリケーションで記号形式主義を使用することは不適切です。本論文は、数学モデルに基づいて代数表現から同等の低レベル表現への効率的な変換を提供することで、これら2つの研究ストリームの結果のギャップを埋めることを目的としています。さらに、この変換では、期間の長さに関して最小限の表現を返します。私たちの結果は実用上大きな影響があります。ユーザーは代数演算子を使用して任意の粒度をより簡単に定義し、同等の最小限の低レベル表現で効率的に動作する粒度推論やその他のサービスにアクセスできます。例として、複数の粒度を持つ時間的制約推論への応用を示します。技術的な観点からは、カレンダー部分式から周期セットへの変換と期間の長さの最小化をインターリーブするハイブリッド アルゴリズムを提案します。このアルゴリズムは、最小周期長を持つ集合ベースの粒度表現を返します。これは、検討対象の推論サービスのパフォーマンスにとって最も重要なパラメータです。広範な実験作業により、このアルゴリズムで使用されている手法が裏付けられ、アルゴリズムの効率性と有効性が示されています。
Anytime Heuristic Search
いつでもヒューリスティック探索
We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted heuristic search to find an approximate solution quickly, and then continues the weighted search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a search problem is limited or uncertain, this creates an anytime heuristic search algorithm that allows a flexible tradeoff between search time and solution quality. We analyze the properties of the resulting Anytime A* algorithm, and consider its performance in three domains; sliding-tile puzzles, STRIPS planning, and multiple sequence alignment. To illustrate the generality of this approach, we also describe how to transform the memory-efficient search algorithm Recursive Best-First Search (RBFS) into an anytime algorithm.
ヒューリスティック探索アルゴリズムA*を、改善された解のシーケンスを探索し、最終的に最適解に収束する、いつでも実行可能なアルゴリズムに変換する方法を説明します。採用する手法は、重み付きヒューリスティック探索を用いて近似解を迅速に探索し、その後、重み付き探索を継続して改善された解を探索するとともに、現在の解の準最適性の境界を改善します。探索問題を解くために利用できる時間が限られているか不確実な場合、探索時間と解の質の間で柔軟なトレードオフを可能にする、いつでも実行可能なヒューリスティック探索アルゴリズムが作成されます。結果として得られるAnytime A*アルゴリズムの特性を分析し、スライディングタイルパズル、STRIPSプランニング、多重配列アライメントの3つの領域におけるそのパフォーマンスを検討します。このアプローチの一般性を示すために、メモリ効率の高い探索アルゴリズムである再帰最良優先探索(RBFS)をいつでも実行可能なアルゴリズムに変換する方法も説明します。
Auctions with Severely Bounded Communication
通信が厳密に制限されたオークション
We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare- and profit-maximizing auctions under this communication restriction. For both measures, we determine the optimal auction and show that the loss incurred relative to unconstrained auctions is mild. We prove non-surprising properties of these kinds of auctions, e.g., that in optimal mechanisms bidders simply report the interval in which their valuation lies in, as well as some surprising properties, e.g., that asymmetric auctions are better than symmetric ones and that multi-round auctions reduce the communication complexity only by a linear factor.
通信量に厳しい制約が課せられたオークションを考察します。各入札者はオークション主催者にtビットの情報しか送信できない。この通信制約下での厚生最大化オークションと利益最大化オークションの両方を考察します。両方の尺度において最適なオークションを決定し、制約のないオークションと比較して発生する損失が軽微であることを示す。この種のオークションには、例えば最適なメカニズムでは入札者が自身の評価値が含まれる区間を単に報告するといった、驚くべき性質は存在しない。また、例えば非対称オークションは対称オークションよりも優れていること、複数ラウンドオークションは通信の複雑さを線形係数でしか低減しないことといった、驚くべき性質も存在します。
Proactive Algorithms for Job Shop Scheduling with Probabilistic Durations
確率的持続時間を持つジョブショップスケジューリングのためのプロアクティブアルゴリズム
Most classical scheduling formulations assume a fixed and known duration for each activity. In this paper, we weaken this assumption, requiring instead that each duration can be represented by an independent random variable with a known mean and variance. The best solutions are ones which have a high probability of achieving a good makespan. We first create a theoretical framework, formally showing how Monte Carlo simulation can be combined with deterministic scheduling algorithms to solve this problem. We propose an associated deterministic scheduling problem whose solution is proved, under certain conditions, to be a lower bound for the probabilistic problem. We then propose and investigate a number of techniques for solving such problems based on combinations of Monte Carlo simulation, solutions to the associated deterministic problem, and either constraint programming or tabu search. Our empirical results demonstrate that a combination of the use of the associated deterministic problem and Monte Carlo simulation results in algorithms that scale best both in terms of problem size and uncertainty. Further experiments point to the correlation between the quality of the deterministic solution and the quality of the probabilistic solution as a major factor responsible for this success.
ほとんどの古典的なスケジューリング定式化は、各活動の所要時間が固定かつ既知であると仮定しています。本論文では、この仮定を弱め、代わりに各所要時間を既知の平均と分散を持つ独立確率変数で表せることを要求します。最良の解は、良好なメイクスパンを達成する確率が高い解です。まず、この問題を解くためにモンテカルロシミュレーションと決定論的スケジューリングアルゴリズムを組み合わせる方法を正式に示す理論的枠組みを構築します。我々は、特定の条件下でその解が確率問題の下限値であることが証明されている、関連する決定論的スケジューリング問題を提案します。次に、モンテカルロシミュレーション、関連する決定論的問題の解、そして制約計画法またはタブーサーチのいずれかを組み合わせた、こうした問題を解決するためのいくつかの手法を提案し、検証します。実験結果から、関連する決定論的問題とモンテカルロシミュレーションを組み合わせることで、問題規模と不確実性の両面において最もスケーラブルなアルゴリズムが得られることがわかった。さらに実験を重ねた結果、この成功の大きな要因として、決定論的解の質と確率的解の質の相関関係が示唆されています。
Junta Distributions and the Average-Case Complexity of Manipulating Elections
ジュンタ分布と選挙操作の平均ケース計算量
Encouraging voters to truthfully reveal their preferences in an election has long been an important issue. Recently, computational complexity has been suggested as a means of precluding strategic behavior. Previous studies have shown that some voting protocols are hard to manipulate, but used NP-hardness as the complexity measure. Such a worst-case analysis may be an insufficient guarantee of resistance to manipulation.Indeed, we demonstrate that NP-hard manipulations may be tractable in the average case. For this purpose, we augment the existing theory of average-case complexity with some new concepts. In particular, we consider elections distributed with respect to junta distributions, which concentrate on hard instances. We use our techniques to prove that scoring protocols are susceptible to manipulation by coalitions, when the number of candidates is constant.
選挙において有権者が自分の好みを正直に表明することを促すことは、長年重要な課題であった。近年、計算複雑性が戦略的行動を排除する手段として提案されています。過去の研究では、一部の投票プロトコルは操作が困難であることが示されていたが、その複雑さの尺度としてNP困難性が用いられていた。このような最悪ケースの分析は、操作に対する耐性を十分に保証するものではない可能性があります。実際、本稿では、NP困難な操作が平均的なケースでは扱いやすい可能性があることを示す。この目的のために、我々は既存の平均ケース複雑性理論にいくつかの新しい概念を追加します。特に、困難な事例に集中する軍事政権分布に関して分布する選挙を考察します。我々は我々の手法を用いて、候補者数が一定の場合、スコアリングプロトコルが連合による操作の影響を受けやすいことを証明します。
Marvin: A Heuristic Search Planner with Online Macro-Action Learning
Marvin：オンラインマクロアクション学習を備えたヒューリスティック探索プランナー
This paper describes Marvin, a planner that competed in the Fourth International Planning Competition (IPC 4). Marvin uses action-sequence-memoisation techniques to generate macro-actions, which are then used during search for a solution plan. We provide an overview of its architecture and search behaviour, detailing the algorithms used. We also empirically demonstrate the effectiveness of its features in various planning domains; in particular, the effects on performance due to the use of macro-actions, the novel features of its search behaviour, and the native support of ADL and Derived Predicates.
本稿では、第4回国際プランニングコンペティション（IPC 4）に出場したプランナーMarvinについて述べる。Marvinは、アクションシーケンスメモ化技術を用いてマクロアクションを生成し、解プランの探索に用います。本稿では、そのアーキテクチャと探索動作の概要を示し、用いられるアルゴリズムを詳述します。また、様々なプランニング領域におけるMarvinの機能の有効性を実証的に検証します。特に、マクロアクションの使用によるパフォーマンスへの影響、探索動作の斬新な特徴、そしてADLと導出述語のネイティブサポートについて検証します。
Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively
解を巧妙に隠蔽することで困難な充足可能式を生成する
To test incomplete search algorithms for constraint satisfaction problems such as 3-SAT, we need a source of hard, but satisfiable, benchmark instances. A simple way to do this is to choose a random truth assignment A, and then choose clauses randomly from among those satisfied by A. However, this method tends to produce easy problems, since the majority of literals point toward the “hidden” assignment A. Last year, Achlioptas, Jia and Moore proposed a problem generator that cancels this effect by hiding both A and its complement. While the resulting formulas appear to be just as hard for DPLL algorithms as random 3-SAT formulas with no hidden assignment, they can be solved by WalkSAT in only polynomial time. Here we propose a new method to cancel the attraction to A, by choosing a clause with t > 0 literals satisfied by A with probability proportional to q^t for some q < 1. By varying q, we can generate formulas whose variables have no bias, i.e., which are equally likely to be true or false; we can even cause the formula to “deceptively” point away from A. We present theoretical and experimental results suggesting that these formulas are exponentially hard both for DPLL algorithms and for incomplete algorithms such as WalkSAT.
3-SATのような制約充足問題における不完全探索アルゴリズムをテストするには、困難だが充足可能なベンチマークインスタンスのソースが必要です。これを行う簡単な方法は、ランダムな真理値割り当てAを選択し、Aが満たす節の中からランダムに節を選択することです。しかし、この手法は簡単な問題を生成する傾向があります。リテラルの大部分は「隠された」割り当てAを指し示します。昨年、Achlioptas、Jia、Mooreは、Aとその補集合の両方を隠すことでこの効果を打ち消す問題生成器を提案しました。結果として得られる式は、DPLLアルゴリズムでは隠れた割り当てのないランダムな3-SAT式と同じくらい難しいように見えますが、WalkSATでは多項式時間で解くことができます。本稿では、Aへの引力を打ち消す新しい手法を提案します。これは、あるq < 1に対して、t > 0のリテラルがAによって満たされる確率がq^tに比例する節を選択することです。qを変化させることで、変数に偏りがなく、つまり真と偽の確率が等しい式を生成できます。さらに、式がAから「欺瞞的に」離れるようにすることも可能です。これらの式は、DPLLアルゴリズムとWalkSATのような不完全アルゴリズムの両方にとって指数関数的に困難であることを示唆する理論および実験結果を示します。
Cutset Sampling for Bayesian Networks
ベイジアンネットワークのためのカットセットサンプリング
The paper presents a new sampling methodology for Bayesian networks that samples only a subset of variables and applies exact inference to the rest. Cutset sampling is a network structure-exploiting application of the Rao-Blackwellisation principle to sampling in Bayesian networks. It improves convergence by exploiting memory-based inference algorithms. It can also be viewed as an anytime approximation of the exact cutset-conditioning algorithm developed by Pearl. Cutset sampling can be implemented efficiently when the sampled variables constitute a loop-cutset of the Bayesian network and, more generally, when the induced width of the network’s graph conditioned on the observed sampled variables is bounded by a constant w. We demonstrate empirically the benefit of this scheme on a range of benchmarks.
本論文では、新しいサンプリング手法を提示します。ベイジアンネットワークの手法の一つで、変数のサブセットのみをサンプリングし、残りの変数には正確な推論を適用します。カットセットサンプリングは、ネットワーク構造を活用したRao-Blackwellization原理をベイジアンネットワークのサンプリングに適用したものです。メモリベースの推論アルゴリズムを利用することで収束性を向上させる。また、Pearlによって開発された正確なカットセット条件付けアルゴリズムの任意近似とみなすこともできます。カットセットサンプリングは、サンプリングされた変数がベイジアンネットワークのループカットセットを構成する場合、そしてより一般的には、観測されたサンプリングされた変数を条件とするネットワークのグラフの誘導幅が定数wで制限される場合に効率的に実装できます。我々は、この手法の利点を様々なベンチマークで実証的に証明します。