A Monte-Carlo AIXI Approximation
モンテカルロAIXI近似
This paper introduces a principled approach for the design of a scalable general reinforcement learning agent. Our approach is based on a direct approximation of AIXI, a Bayesian optimality notion for general reinforcement learning agents. Previously, it has been unclear whether the theory of AIXI could motivate the design of practical algorithms. We answer this hitherto open question in the affirmative, by providing the first computationally feasible approximation to the AIXI agent. To develop our approximation, we introduce a new Monte-Carlo Tree Search algorithm along with an agent-specific extension to the Context Tree Weighting algorithm. Empirically, we present a set of encouraging results on a variety of stochastic and partially observable domains. We conclude by proposing a number of directions for future research.
本論文では、スケーラブルな汎用強化学習エージェントの設計のための原理的なアプローチを紹介します。このアプローチは、汎用強化学習エージェントのベイズ最適性概念であるAIXIの直接近似に基づいています。これまで、AIXIの理論が実用的なアルゴリズムの設計の動機付けとなるかどうかは不明でした。私たちは、AIXIエージェントに対する計算的に実行可能な最初の近似を提供することで、このこれまで未解決の疑問に肯定的に答えます。この近似を開発するために、コンテキストツリー重み付けアルゴリズムのエージェント固有の拡張とともに、新しいモンテカルロ木探索アルゴリズムを導入します。経験的には、さまざまな確率的および部分観測領域で一連の有望な結果を示します。結論として、将来の研究の方向性をいくつか提案します。
Regression Conformal Prediction with Nearest Neighbours
最近傍点を用いた回帰共形予測
In this paper we apply Conformal Prediction (CP) to the k-Nearest Neighbours Regression (k-NNR) algorithm and propose ways of extending the typical nonconformity measure used for regression so far. Unlike traditional regression methods which produce point predictions, Conformal Predictors output predictive regions that satisfy a given confidence level. The regions produced by any Conformal Predictor are automatically valid, however their tightness and therefore usefulness depends on the nonconformity measure used by each CP. In effect a nonconformity measure evaluates how strange a given example is compared to a set of other examples based on some traditional machine learning algorithm. We define six novel nonconformity measures based on the k-Nearest Neighbours Regression algorithm and develop the corresponding CPs following both the original (transductive) and the inductive CP approaches. A comparison of the predictive regions produced by our measures with those of the typical regression measure suggests that a major improvement in terms of predictive region tightness is achieved by the new measures.
本稿では、共形予測(CP)をk最近傍回帰(k-NNR)アルゴリズムに適用し、これまで回帰に使用されてきた典型的な不適合尺度の拡張方法を提案します。点予測を生成する従来の回帰法とは異なり、共形予測器は、指定された信頼水準を満たす予測領域を出力します。どの共形予測器によって生成された領域も自動的に有効ですが、その厳密さ、ひいては有用性は、各CPで使用される不適合尺度に依存します。実際、不適合尺度は、従来の機械学習アルゴリズムに基づいて、特定の例が他の例の集合と比較してどの程度奇妙であるかを評価するものです。本稿では、k最近傍回帰アルゴリズムに基づいて6つの新しい不適合尺度を定義し、元の(トランスダクティブ) CPアプローチと帰納的CPアプローチの両方に従って対応するCPを開発します。私たちの尺度によって生成された予測領域と一般的な回帰尺度の予測領域を比較すると、新しい尺度によって予測領域の厳密さの点で大きな改善が達成されたことが示唆されます。
Scaling up Heuristic Planning with Relational Decision Trees
関係決定木を用いたヒューリスティックプランニングのスケールアップ
Current evaluation functions for heuristic planning are expensive to compute. In numerous planning problems these functions provide good guidance to the solution, so they are worth the expense. However, when evaluation functions are misguiding or when planning problems are large enough, lots of node evaluations must be computed, which severely limits the scalability of heuristic planners. In this paper, we present a novel solution for reducing node evaluations in heuristic planning based on machine learning. Particularly, we define the task of learning search control for heuristic planning as a relational classification task, and we use an off-the-shelf relational classification tool to address this learning task. Our relational classification task captures the preferred action to select in the different planning contexts of a specific planning domain. These planning contexts are defined by the set of helpful actions of the current state, the goals remaining to be achieved, and the static predicates of the planning task. This paper shows two methods for guiding the search of a heuristic planner with the learned classifiers. The first one consists of using the resulting classifier as an action policy. The second one consists of applying the classifier to generate lookahead states within a Best First Search algorithm. Experiments over a variety of domains reveal that our heuristic planner using the learned classifiers solves larger problems than state-of-the-art planners.
現在のヒューリスティック プランニングの評価関数は計算コストが高いです。多くのプランニング問題において、これらの関数はソリューションへの優れたガイダンスを提供するため、コストに見合う価値があります。しかし、評価関数が誤ったガイドとなる場合やプランニング問題が十分に大きい場合は、多くのノード評価を計算する必要があり、ヒューリスティック プランナーのスケーラビリティが大幅に制限されます。本稿では、機械学習に基づくヒューリスティックプランニングにおけるノード評価を削減する新たなソリューションを提示します。特に、ヒューリスティックプランニングのための探索制御の学習タスクを関係分類タスクとして定義し、この学習タスクに対処するために市販の関係分類ツールを用います。この関係分類タスクは、特定のプランニングドメインにおける様々なプランニングコンテキストにおいて選択すべき優先アクションを捕捉します。これらのプランニングコンテキストは、現在の状態における有用なアクションの集合、達成すべき残りの目標、そしてプランニングタスクの静的述語によって定義されます。本稿では、学習済み分類器を用いてヒューリスティックプランナーの探索を導く2つの手法を示す。1つ目は、得られた分類器を行動方針として用いる手法です。2つ目は、この分類器を用いてBest First Searchアルゴリズム内で先読み状態を生成する手法です。様々なドメインでの実験により、学習済み分類器を用いた本ヒューリスティックプランナーは、最先端のプランナーよりも大規模な問題を解決できることが明らかになった。
Exploiting Structure in Weighted Model Counting Approaches to Probabilistic Inference
重み付きモデルカウント法における構造の活用による確率推論への応用
Previous studies have demonstrated that encoding a Bayesian network into a SAT formula and then performing weighted model counting using a backtracking search algorithm can be an effective method for exact inference. In this paper, we present techniques for improving this approach for Bayesian networks with noisy-OR and noisy-MAX relations—two relations that are widely used in practice as they can dramatically reduce the number of probabilities one needs to specify. In particular, we present two SAT encodings for noisy-OR and two encodings for noisy-MAX that exploit the structure or semantics of the relations to improve both time and space efficiency, and we prove the correctness of the encodings. We experimentally evaluated our techniques on large-scale real and randomly generated Bayesian networks. On these benchmarks, our techniques gave speedups of up to two orders of magnitude over the best previous approaches for networks with noisy-OR/MAX relations and scaled up to larger networks. As well, our techniques extend the weighted model counting approach for exact inference to networks that were previously intractable for the approach.
以前の研究では、ベイジアンネットワークをSAT式にエンコードし、バックトラッキング検索アルゴリズムを使用して重み付きモデルカウントを実行すると、正確な推論を行う効果的な方法になり得ることが実証されています。本稿では、指定する必要がある確率の数を大幅に削減できるため、実際に広く使用されている2つの関係である、ノイズ付きOR関係とノイズ付きMAX関係を持つベイジアンネットワークに対してこのアプローチを改善する手法を紹介します。特に、我々は、関係の構造または意味論を利用して時間と空間の両方の効率を改善する、noisy-OR用の2つのSATエンコーディングとnoisy-MAX用の2つのエンコーディングを提示し、エンコーディングの正しさを証明します。我々は、大規模な実際のベイジアン ネットワークとランダムに生成されたベイジアン ネットワークで実験的にこの手法を評価しました。これらのベンチマークでは、noisy-OR/MAX関係を持つネットワークに対して、我々の手法は以前の最良のアプローチに対して最大2桁の高速化をもたらし、より大きなネットワークにスケールアップされました。また、我々の手法は、正確な推論のための重み付きモデル カウンティング アプローチを、以前はこのアプローチでは処理不可能だったネットワークに拡張します。
Computing Small Unsatisfiable Cores in Satisfiability Modulo Theories
充足可能性法における小さな充足不可能コアの計算理論
The problem of finding small unsatisfiable cores for SAT formulas has recently received a lot of interest, mostly for its applications in formal verification. However, propositional logic is often not expressive enough for representing many interesting verification problems, which can be more naturally addressed in the framework of Satisfiability Modulo Theories, SMT. Surprisingly, the problem of finding unsatisfiable cores in SMT has received very little attention in the literature.In this paper we present a novel approach to this problem, called the Lemma-Lifting approach. The main idea is to combine an SMT solver with an external propositional core extractor. The SMT solver produces the theory lemmas found during the search, dynamically lifting the suitable amount of theory information to the Boolean level. The core extractor is then called on the Boolean abstraction of the original SMT problem and of the theory lemmas. This results in an unsatisfiable core for the original SMT problem, once the remaining theory lemmas are removed.The approach is conceptually interesting, and has several advantages in practice. In fact, it is extremely simple to implement and to update, and it can be interfaced with every propositional core extractor in a plug-and-play manner, so as to benefit for free of all unsat-core reduction techniques which have been or will be made available.We have evaluated our algorithm with a very extensive empirical test on SMT-LIB benchmarks, which confirms the validity and potential of this approach.
SAT式の小さな不満足なコアを見つける問題は、最近、主に形式検証への応用で大きな注目を集めています。しかし、命題論理は、多くの興味深い検証問題を表現するには表現力が不十分であることが多く、これらの問題は、充足可能性モジュロ理論(SMT)のフレームワークでより自然に対処できます。驚くべきことに、SMTで不満足なコアを見つける問題は、文献ではほとんど注目されていません。この論文では、この問題に対する新しいアプローチである「補題リフティング」を紹介します。主なアイデアは、SMTソルバーを外部の命題コア抽出器と組み合わせることです。SMTソルバーは、検索中に見つかった理論の補題を生成し、適切な量の理論情報をブールレベルに動的に持ち上げます。次に、コア抽出器は、元のSMT問題と理論の補題のブール抽象化に対して呼び出されます。残りの理論補題を除去すると、元のSMT問題に対する不満足なコアが生成されます。このアプローチは概念的に興味深く、実践上もいくつかの利点があります。実際、実装と更新が非常に簡単で、プラグアンドプレイ方式ですべての命題コア抽出器とインターフェースできるため、利用可能になった、または利用可能になるすべての不満足なコア削減手法を無料で利用できます。私たちは、SMT-LIBベンチマークでの非常に広範な実証テストでアルゴリズムを評価し、このアプローチの妥当性と可能性を確認しました。
Identifying Aspects for Web-Search Queries
Web検索クエリのアスペクトの特定
Many web-search queries serve as the beginning of an exploration of an unknown space of information, rather than looking for a specific web page. To answer such queries effec- tively, the search engine should attempt to organize the space of relevant information in a way that facilitates exploration.We describe the Aspector system that computes aspects for a given query. Each aspect is a set of search queries that together represent a distinct information need relevant to the original search query. To serve as an effective means to explore the space, Aspector computes aspects that are orthogonal to each other and to have high combined coverage.Aspector combines two sources of information to compute aspects. We discover candidate aspects by analyzing query logs, and cluster them to eliminate redundancies. We then use a mass-collaboration knowledge base (e.g., Wikipedia) to compute candidate aspects for queries that occur less frequently and to group together aspects that are likely to be semantically related. We present a user study that indicates that the aspects we compute are rated favorably against three competing alternatives related searches proposed by Google, cluster labels assigned by the Clusty search engine, and navigational searches proposed by Bing.
多くのWeb検索クエリは、特定のWebページを探すためではなく、未知の情報空間の探索の始まりとして機能します。このようなクエリに効果的に回答するために、検索エンジンは、探索を容易にするような方法で関連情報の空間を整理しようと試みるべきです。ここでは、特定のクエリの側面を計算するAspectorシステムについて説明します。各側面とは、元の検索クエリに関連する明確な情報ニーズを表す検索クエリのセットです。空間を探索するための効果的な手段として、Aspectorは互いに直交し、高い総合的カバレッジを持つ側面を計算します。Aspectorは、2つの情報源を組み合わせて側面を計算します。クエリ ログを分析することで候補となる側面を発見し、それらをクラスタ化して冗長性を排除します。次に、大規模コラボレーション知識ベース(Wikipediaなど)を使用して、出現頻度の低いクエリの候補となる側面を計算し、意味的に関連する可能性が高い側面をグループ化します。ユーザー スタディでは、計算した側面が、Googleが提案する関連検索、Clusty検索エンジンによって割り当てられたクラスター ラベル、Bingが提案するナビゲーション検索という3つの競合する代替検索に対して好意的に評価されていることを示しています。
The Complexity of Integer Bound Propagation
整数境界伝播の計算量
Bound propagation is an important Artificial Intelligence technique used in Constraint Programming tools to deal with numerical constraints. It is typically embedded within a search procedure (branch and prune) and used at every node of the search tree to narrow down the search space, so it is critical that it be fast. The procedure invokes constraint propagators until a common fixpoint is reached, but the known algorithms for this have a pseudo-polynomial worst-case time complexity: they are fast indeed when the variables have a small numerical range, but they have the well-known problem of being prohibitively slow when these ranges are large. An important question is therefore whether strongly-polynomial algorithms exist that compute the common bound consistent fixpoint of a set of constraints. This paper answers this question. In particular we show that this fixpoint computation is in fact NP-complete, even when restricted to binary linear constraints.
境界伝播は、制約プログラミングツールで数値制約を扱うために使用される重要な人工知能技術です。これは通常、検索手順(分岐と刈り込み)内に組み込まれ、検索空間を絞り込むために検索木のすべてのノードで使用されるため、高速であることが非常に重要です。この手順では、共通の不動点に到達するまで制約伝播関数が呼び出されますが、このための既知のアルゴリズムは、最悪のケースで疑似多項式的な時間計算量を持ちます。つまり、変数の数値範囲が狭い場合は確かに高速ですが、範囲が大きい場合は法外に遅くなるというよく知られた問題があります。したがって、一連の制約の共通の境界を持つ一貫性のある不動点を計算する強力多項式アルゴリズムが存在するかどうかが重要な問題となります。本論文では、この質問に答えます。特に、この不動点計算は、2値線形制約に制限された場合でも、実際にはNP完全であることを示します。
Decidability and Undecidability Results for Propositional Schemata
命題スキーマの決定可能性と決定不能性の結果
We define a logic of propositional formula schemata adding to the syntax of propositional logic indexed propositions and iterated connectives ranging over intervals parameterized by arithmetic variables. The satisfiability problem is shown to be undecidable for this new logic, but we introduce a very general class of schemata, called bound-linear, for which this problem becomes decidable. This result is obtained by reduction to a particular class of schemata called regular, for which we provide a sound and complete terminating proof procedure. This schemata calculus allows one to capture proof patterns corresponding to a large class of problems specified in propositional logic. We also show that the satisfiability problem becomes again undecidable for slight extensions of this class, thus demonstrating that bound-linear schemata represent a good compromise between expressivity and decidability.
我々は、命題論理の構文に、算術変数によってパラメータ化された区間にわたるインデックス付き命題と反復接続詞を追加した命題式スキーマの論理を定義します。この新しい論理では充足可能性問題は決定不可能であることが示されるが、我々は境界線形と呼ばれる非常に一般的なスキーマのクラスを導入し、この問題は決定可能になります。この結果は、正規と呼ばれる特定のスキーマのクラスへの還元によって得られ、これに対して健全で完全な停止証明手続きを提供します。このスキーマ計算により、命題論理で規定される問題の大規模なクラスに対応する証明パターンを捕捉することができます。また、このクラスをわずかに拡張すると充足可能性問題が再び決定不可能になることを示し、境界線形スキーマが表現力と決定可能性の間の良好な妥協点となることを示す。
Multiagent Learning in Large Anonymous Games
大規模匿名ゲームにおけるマルチエージェント学習
In large systems, it is important for agents to learn to act effectively, but sophisticated multi-agent learning algorithms generally do not scale. An alternative approach is to find restricted classes of games where simple, efficient algorithms converge. It is shown that stage learning efficiently converges to Nash equilibria in large anonymous games if best-reply dynamics converge. Two features are identified that improve convergence. First, rather than making learning more difficult, more agents are actually beneficial in many settings. Second, providing agents with statistical information about the behavior of others can significantly reduce the number of observations needed.
大規模システムでは、エージェントが効果的に行動することを学習することが重要だが、洗練されたマルチエージェント学習アルゴリズムは一般的にスケールしない。代替アプローチは、単純で効率的なアルゴリズムが収束するゲームの限定されたクラスを見つけることです。大規模匿名ゲームにおいて、最善応答ダイナミクスが収束する場合、段階学習はナッシュ均衡に効率的に収束することが示されます。収束を改善する2つの特徴が特定されています。第一に、学習を困難にするのではなく、多くの状況において、エージェントの数が増えることは実際には有益です。第二に、エージェントに他者の行動に関する統計情報を提供することで、必要な観測数を大幅に削減できます。
False-Name Manipulations in Weighted Voting Games
重み付き投票ゲームにおける偽名操作
Weighted voting is a classic model of cooperation among agents in decision-making domains. In such games, each player has a weight, and a coalition of players wins the game if its total weight meets or exceeds a given quota. A player’s power in such games is usually not directly proportional to his weight, and is measured by a power index, the most prominent among which are the Shapley-Shubik index and the Banzhaf index.In this paper, we investigate by how much a player can change his power, as measured by the Shapley-Shubik index or the Banzhaf index, by means of a false-name manipulation, i.e., splitting his weight among two or more identities. For both indices, we provide upper and lower bounds on the effect of weight-splitting. We then show that checking whether a beneficial split exists is NP-hard, and discuss efficient algorithms for restricted cases of this problem, as well as randomized algorithms for the general case. We also provide an experimental evaluation of these algorithms. Finally, we examine related forms of manipulative behavior, such as annexation, where a player subsumes other players, or merging, where several players unite into one. We characterize the computational complexity of such manipulations and provide limits on their effects. For the Banzhaf index, we describe a new paradox, which we term the Annexation Non-monotonicity Paradox.
加重投票は、意思決定領域におけるエージェント間の協力の古典的なモデルです。このようなゲームでは、各プレイヤーは重みを持ち、プレイヤー連合は、その重みの合計が所定のノルマを満たすか超えた場合、ゲームに勝利します。このようなゲームにおけるプレイヤーの力は通常、重みと正比例せず、シャプレー・シュビック指数とバンザフ指数などの力指数によって測定されます。本稿では、偽名操作、すなわち重みを複数のアイデンティティに分割することで、プレイヤーがシャプレー・シュビック指数またはバンザフ指数で測定される自身の力をどの程度変化させることができるかを調査します。両指数について、重み分割の効果の上限と下限を与える。次に、有益な分割が存在するかどうかの判定がNP困難であることを示し、この問題の限定されたケースに対する効率的なアルゴリズムと、一般的なケースに対するランダム化アルゴリズムについて議論します。また、これらのアルゴリズムの実験的評価も提供します。最後に、プレイヤーが他のプレイヤーを包摂する併合や、複数のプレイヤーが一つに統合する合併といった、関連する操作行動の形態を検証します。このような操作の計算複雑性を特徴づけ、その影響に限界を与える。バンザフ指数については、「併合非単調性パラドックス」と呼ぶ新たなパラドックスを説明します。
Efficient Planning under Uncertainty with Macro-actions
マクロアクションを用いた不確実性下での効率的なプランニング
Deciding how to act in partially observable environments remains an active area of research. Identifying good sequences of decisions is particularly challenging when good control performance requires planning multiple steps into the future in domains with many states. Towards addressing this challenge, we present an online, forward-search algorithm called the Posterior Belief Distribution (PBD). PBD leverages a novel method for calculating the posterior distribution over beliefs that result after a sequence of actions is taken, given the set of observation sequences that could be received during this process. This method allows us to efficiently evaluate the expected reward of a sequence of primitive actions, which we refer to as macro-actions. We present a formal analysis of our approach, and examine its performance on two very large simulation experiments: scientific exploration and a target monitoring domain. We also demonstrate our algorithm being used to control a real robotic helicopter in a target monitoring experiment, which suggests that our approach has practical potential for planning in real-world, large partially observable domains where a multi-step lookahead is required to achieve good performance.
部分的に観測可能な環境においてどのように行動するかを決定することは、依然として活発な研究分野です。良好な制御性能を得るためには、多くの状態を持つ領域において将来に向けて複数ステップの計画が必要となる場合、適切な意思決定シーケンスを特定することは特に困難です。この課題に対処するため、我々は事後確信分布（PBD）と呼ばれるオンライン順方向探索アルゴリズムを提示します。PBDは、一連のアクションを実行した後に得られる確信の事後分布を、このプロセス中に受信される可能性のある一連の観測シーケンスを与えられた場合に計算する、新しい手法を活用します。この手法により、マクロアクションと呼ばれる一連の基本アクションの期待報酬を効率的に評価できます。本稿では、本手法の形式的な分析を提示し、科学的探査と目標監視という2つの大規模シミュレーション実験における性能を検証します。また、本アルゴリズムを用いて実際のロボットヘリコプターを目標監視実験で制御する様子も示す。これは、本手法が、良好な性能を得るために複数段階の先読みが必要となる、現実世界の大規模な部分観測領域における計画において実用的な可能性を有することを示唆します。
Narrowing the Modeling Gap: A Cluster-Ranking Approach to Coreference Resolution
モデリングギャップの縮小：共参照解決へのクラスターランキングアプローチ
Traditional learning-based coreference resolvers operate by training the mention-pair model for determining whether two mentions are coreferent or not. Though conceptually simple and easy to understand, the mention-pair model is linguistically rather unappealing and lags far behind the heuristic-based coreference models proposed in the pre-statistical NLP era in terms of sophistication. Two independent lines of recent research have attempted to improve the mention-pair model, one by acquiring the mention-ranking model to rank preceding mentions for a given anaphor, and the other by training the entity-mention model to determine whether a preceding cluster is coreferent with a given mention. We propose a cluster-ranking approach to coreference resolution, which combines the strengths of the mention-ranking model and the entity-mention model, and is therefore theoretically more appealing than both of these models. In addition, we seek to improve cluster rankers via two extensions: (1) lexicalization and (2) incorporating knowledge of anaphoricity by jointly modeling anaphoricity determination and coreference resolution. Experimental results on the ACE data sets demonstrate the superior performance of cluster rankers to competing approaches as well as the effectiveness of our two extensions.
従来の学習ベースの共参照解決器は、2つの言及が共参照であるかどうかを判断するための言及ペア モデルをトレーニングすることによって動作します。概念的には単純で理解しやすいものの、言及ペア モデルは言語的にはあまり魅力がなく、洗練度という点では統計以前のNLP時代に提案されたヒューリスティック ベースの共参照モデルに大きく遅れをとっています。最近の2つの独立した研究ラインでは、言及ペア モデルの改善が試みられています。1つは、特定のアナフォラに対して先行する言及をランク付けする言及ランキング モデルを取得するものであり、もう1つは、先行するクラスターが特定の言及と共参照であるかどうかを判断するためにエンティティ言及モデルをトレーニングするというものです。私たちは、言及ランキング モデルとエンティティ言及モデルの長所を組み合わせたクラスター ランキング アプローチを共参照解決に提案します。このアプローチは理論的にはこれら2つのモデルよりも魅力的です。さらに、我々は2つの拡張、すなわち(1)語彙化と(2)アナフォリシティの決定と共参照解決を共同でモデル化することによりアナフォリシティに関する知識を組み込むことを通して、クラスターランカーの改良を目指します。ACEデータセットにおける実験結果は、クラスターランカーが競合アプローチよりも優れた性能を発揮すること、そして我々の2つの拡張の有効性を実証しています。
On-line Planning and Scheduling: An Application to Controlling Modular Printers
オンラインプランニングとスケジューリング：モジュラープリンターの制御への応用
We present a case study of artificial intelligence techniques applied to the control of production printing equipment. Like many other real-world applications, this complex domain requires high-speed autonomous decision-making and robust continual operation. To our knowledge, this work represents the first successful industrial application of embedded domain-independent temporal planning. Our system handles execution failures and multi-objective preferences. At its heart is an on-line algorithm that combines techniques from state-space planning and partial-order scheduling. We suggest that this general architecture may prove useful in other applications as more intelligent systems operate in continual, on-line settings. Our system has been used to drive several commercial prototypes and has enabled a new product architecture for our industrial partner. When compared with state-of-the-art off-line planners, our system is hundreds of times faster and often finds better plans. Our experience demonstrates that domain-independent AI planning based on heuristic search can flexibly handle time, resources, replanning, and multiple objectives in a high-speed practical application without requiring hand-coded control knowledge.
本稿では、生産印刷機器の制御に人工知能技術を適用したケーススタディを紹介します。他の多くの実世界アプリケーションと同様に、この複雑な領域では、高速な自律的意思決定と堅牢な継続的運用が求められます。私たちの知る限り、本研究は組み込み型ドメイン非依存時間計画の産業応用として初めて成功した事例です。本システムは、実行失敗と多目的設定に対応します。その中核となるのは、状態空間計画と半順序スケジューリングの技術を組み合わせたオンラインアルゴリズムです。よりインテリジェントなシステムが継続的なオンライン環境で動作するようになるにつれ、この汎用アーキテクチャは他のアプリケーションにも有用となる可能性があります。本システムは、いくつかの商用プロトタイプの駆動に使用され、産業パートナーにとって新しい製品アーキテクチャを実現しました。最先端のオフラインプランナーと比較すると、本システムは数百倍高速で、多くの場合、より優れた計画を見つけます。私たちの経験は、ヒューリスティック探索に基づくドメイン非依存AI計画が、手作業でコーディングされた制御知識を必要とせずに、高速な実用アプリケーションにおいて、時間、リソース、再計画、そして複数の目的を柔軟に処理できることを示しています。
Evaluating Temporal Graphs Built from Texts via Transitive Reduction
推移的縮約によるテキストから構築された時系列グラフの評価
Temporal information has been the focus of recent attention in information extraction, leading to some standardization effort, in particular for the task of relating events in a text. This task raises the problem of comparing two annotations of a given text, because relations between events in a story are intrinsically interdependent and cannot be evaluated separately. A proper evaluation measure is also crucial in the context of a machine learning approach to the problem. Finding a common comparison referent at the text level is not obvious, and we argue here in favor of a shift from event-based measures to measures on a unique textual object, a minimal underlying temporal graph, or more formally the transitive reduction of the graph of relations between event boundaries. We support it by an investigation of its properties on synthetic data and on a well-know temporal corpus.
時間情報は、情報抽出において近年注目されており、特にテキスト内のイベントを関連付けるタスクにおいて、標準化の取り組みが進められています。このタスクは、与えられたテキストの2つの注釈を比較するという問題を提起します。なぜなら、物語内のイベント間の関係は本質的に相互依存しており、個別に評価することができないからです。この問題に対する機械学習アプローチの文脈においても、適切な評価尺度は極めて重要です。テキストレベルで共通の比較参照先を見つけることは自明ではない。そこで我々は、イベントベースの尺度から、一意のテキストオブジェクト、つまり最小限の基礎となる時間グラフ、あるいはより正式にはイベント境界間の関係グラフの推移的縮約に基づく尺度への移行を支持します。我々は、合成データおよび既知の時間コーパスにおけるその特性を調査することにより、この考え方を支持します。
Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
多数のリスタートと制限幅解決を伴う節学習アルゴリズム
We offer a new understanding of some aspects of practical SAT-solvers that are based on DPLL with unit-clause propagation, clause-learning, and restarts. We do so by analyzing a concrete algorithm which we claim is faithful to what practical solvers do. In particular, before making any new decision or restart, the solver repeatedly applies the unit-resolution rule until saturation, and leaves no component to the mercy of non-determinism except for some internal randomness. We prove the perhaps surprising fact that, although the solver is not explicitly designed for it, with high probability it ends up behaving as width-k resolution after no more than O(n^{2k+2}) conflicts and restarts, where n is the number of variables. In other words, width-k resolution can be thought of as O(n^{2k+2}) restarts of the unit-resolution rule with learning.
単位節伝播、節学習、およびリスタートを備えたDPLLに基づく実用的なSATソルバーのいくつかの側面について、新たな理解を提供します。これは、実用的なソルバーの動作に忠実であると主張する具体的なアルゴリズムを分析することにより行う。特に、新たな決定やリスタートを行う前に、ソルバーは飽和するまで単位解決規則を繰り返し適用し、内部のランダム性を除いて、非決定性に左右される要素を残さない。ソルバーは明示的にそのために設計されていないが、nを変数の数とした場合、O(n^{2k+2})回以下の競合とリスタートの後、高い確率で幅kの解決として動作するという、おそらく驚くべき事実を証明します。言い換えれば、幅k解像度は、学習を伴う単位解像度ルールのO(n^{2k+2})回の再開と考えることができます。
Multimode Control Attacks on Elections
選挙に対するマルチモード制御攻撃
In 1992, Bartholdi, Tovey, and Trick opened the study of control attacks on elections—attempts to improve the election outcome by such actions as adding/deleting candidates or voters. That work has led to many results on how algorithms can be used to find attacks on elections and how complexity-theoretic hardness results can be used as shields against attacks. However, all the work in this line has assumed that the attacker employs just a single type of attack. In this paper, we model and study the case in which the attacker launches a multipronged (i.e., multimode) attack. We do so to more realistically capture the richness of real-life settings. For example, an attacker might simultaneously try to suppress some voters, attract new voters into the election, and introduce a spoiler candidate. Our model provides a unified framework for such varied attacks. By constructing polynomial-time multiprong attack algorithms we prove that for various election systems even such concerted, flexible attacks can be perfectly planned in deterministic polynomial time.
1992年、バルトルディ、トーヴィー、トリックは選挙に対する制御攻撃、すなわち候補者や投票者の追加・削除といった行為によって選挙結果を改善しようとする攻撃の研究を開始しました。この研究は、選挙への攻撃を発見するためのアルゴリズムの活用方法や、複雑性理論的困難性の結果を攻撃に対する防御策として活用する方法に関する多くの成果につながりました。しかし、この分野における研究はすべて、攻撃者が単一の種類の攻撃のみを用いると仮定していました。本稿では、攻撃者が多方面にわたる（すなわちマルチモードの）攻撃を仕掛けるケースをモデル化し、考察します。これは、現実世界の状況の多様性をより現実的に捉えるためです。例えば、攻撃者は一部の投票者の投票意欲を削ぎ、新たな投票者を選挙に呼び込み、そして妨害候補者を擁立しようとする可能性があります。本モデルは、このような多様な攻撃に対する統一的な枠組みを提供します。多項式時間マルチプロング攻撃アルゴリズムを構築することにより、様々な選挙システムにおいて、そのような協調的で柔軟な攻撃でさえも決定論的多項式時間で完全に計画できることを証明します。
Iterated Belief Change Due to Actions and Observations
行動と観察による反復的な信念変化
In action domains where agents may have erroneous beliefs, reasoning about the effects of actions involves reasoning about belief change. In this paper, we use a transition system approach to reason about the evolution of an agent’s beliefs as actions are executed. Some actions cause an agent to perform belief revision while others cause an agent to perform belief update, but the interaction between revision and update can be non-elementary. We present a set of rationality properties describing the interaction between revision and update, and we introduce a new class of belief change operators for reasoning about alternating sequences of revisions and updates. Our belief change operators can be characterized in terms of a natural shifting operation on total pre-orderings over interpretations. We compare our approach with related work on iterated belief change due to action, and we conclude with some directions for future research.
エージェントが誤った信念を持つ可能性のある行動領域において、行動の効果についての推論は、信念の変化についての推論を伴います。本論文では、遷移システムアプローチを用いて、行動の実行に伴うエージェントの信念の進化について推論します。エージェントは、ある行動によって信念の修正を行い、他の行動によって信念の更新を行うが、修正と更新の相互作用は非基本的なものとなり得る。本稿では、修正と更新の相互作用を記述する合理性特性を提示し、修正と更新の交互シーケンスに関する推論のための新しいクラスの信念変更演算子を導入します。この信念変更演算子は、解釈上の全順序付けに対する自然なシフト操作として特徴付けられます。本稿では、本手法を、行動による反復的な信念変更に関する関連研究と比較し、今後の研究の方向性について結論付ける。
A Logical Study of Partial Entailment
部分含意の論理的研究
We introduce a novel logical notion–partial entailment–to propositional logic. In contrast with classical entailment, that a formula P partially entails another formula Q with respect to a background formula set \Gamma intuitively means that under the circumstance of \Gamma, if P is true then some “part” of Q will also be true. We distinguish three different kinds of partial entailments and formalize them by using an extended notion of prime implicant. We study their semantic properties, which show that, surprisingly, partial entailments fail for many simple inference rules. Then, we study the related computational properties, which indicate that partial entailments are relatively difficult to be computed. Finally, we consider a potential application of partial entailments in reasoning about rational agents.
私たちは、命題論理に新しい論理概念である部分含意を導入します。古典的な含意とは対照的に、背景論理式集合\Gammaに関して論理式Pが別の論理式Qを部分的に含意することは、直感的に、\Gammaの状況下ではPが真であればQの「一部」も真となることを意味します。我々は3種類の部分含意を区別し、主含意の拡張概念を用いてそれらを形式化します。それらの意味特性を研究し、驚くべきことに、多くの単純な推論規則において部分含意は成立しないことを示します。次に、関連する計算特性を研究し、部分含意の計算が比較的困難であることを示します。最後に、合理的エージェントに関する推論における部分含意の潜在的な応用について考察します。
A Probabilistic Approach for Maintaining Trust Based on Evidence
証拠に基づく信頼維持のための確率的アプローチ
Leading agent-based trust models address two important needs. First, they show how an agent may estimate the trustworthiness of another agent based on prior interactions. Second, they show how agents may share their knowledge in order to cooperatively assess the trustworthiness of others. However, in real-life settings, information relevant to trust is usually obtained piecemeal, not all at once. Unfortunately, the problem of maintaining trust has drawn little attention. Existing approaches handle trust updates in a heuristic, not a principled, manner.This paper builds on a formal model that considers probability and certainty as two dimensions of trust. It proposes a mechanism using which an agent can update the amount of trust it places in other agents on an ongoing basis. This paper shows via simulation that the proposed approach (a) provides accurate estimates of the trustworthiness of agents that change behavior frequently; and (b) captures the dynamic behavior of the agents. This paper includes an evaluation based on a real dataset drawn from Amazon Marketplace, a leading e-commerce site.
主要なエージェントベースの信頼モデルは、2つの重要なニーズに対応しています。第一に、エージェントが過去の相互作用に基づいて他のエージェントの信頼性を推定する方法を示します。第二に、エージェントが協力して他者の信頼性を評価するために、知識を共有する方法を示します。しかし、現実の状況では、信頼に関連する情報は通常、一度にすべてではなく、断片的に得られます。残念ながら、信頼の維持という問題はほとんど注目されていません。既存のアプローチは、信頼の更新を原則的な方法ではなく、ヒューリスティックな方法で処理します。本論文は、確率と確実性を信頼の2つの次元として扱う形式モデルに基づいています。エージェントが他のエージェントに置く信頼の量を継続的に更新できるメカニズムを提案します。本論文では、シミュレーションを通じて、提案されたアプローチが(a)頻繁に行動を変えるエージェントの信頼性を正確に推定し、(b)エージェントの動的な行動を捉えることを示します。本論文には、主要なeコマースサイトであるAmazon Marketplaceから取得した実際のデータセットに基づく評価が含まれています。
Second-Order Consistencies
二次整合性
In this paper, we propose a comprehensive study of second-order consistencies (i.e., consistencies identifying inconsistent pairs of values) for constraint satisfaction. We build a full picture of the relationships existing between four basic second-order consistencies, namely path consistency (PC), 3-consistency (3C), dual consistency (DC) and 2-singleton arc consistency (2SAC), as well as their conservative and strong variants. Interestingly, dual consistency is an original property that can be established by using the outcome of the enforcement of generalized arc consistency (GAC), which makes it rather easy to obtain since constraint solvers typically maintain GAC during search. On binary constraint networks, DC is equivalent to PC, but its restriction to existing constraints, called conservative dual consistency (CDC), is strictly stronger than traditional conservative consistencies derived from path consistency, namely partial path consistency (PPC) and conservative path consistency (CPC). After introducing a general algorithm to enforce strong (C)DC, we present the results of an experimentation over a wide range of benchmarks that demonstrate the interest of (conservative) dual consistency. In particular, we show that enforcing (C)DC before search clearly improves the performance of MAC (the algorithm that maintains GAC during search) on several binary and non-binary structured problems.
本論文では、制約充足のための二次整合性（すなわち、矛盾する値のペアを識別する整合性）の包括的な研究を提案します。パス整合性（PC）、3整合性（3C）、双対整合性（DC）、2シングルトンアーク整合性（2SAC）という4つの基本的な二次整合性と、それらの保守的および強力な変種間の関係の全体像を構築します。興味深いことに、二重一貫性は、一般化アーク一貫性(GAC)の強制の結果を使用して確立できる独自の特性であり、制約ソルバーは通常、検索中にGACを維持するため、比較的簡単に取得できます。バイナリ制約ネットワークでは、DCはPCと同等ですが、保守的な二重一貫性(CDC)と呼ばれる既存の制約への制限は、パス一貫性から導かれる従来の保守的な一貫性、つまり部分パス一貫性(PPC)と保守的なパス一貫性(CPC)よりも厳密に強力です。強力な(C)DCを強制する一般的なアルゴリズムを紹介した後、(保守的な)二重一貫性の面白さを示すさまざまなベンチマークでの実験結果を示します。特に、検索前に(C)DCを強制すると、いくつかのバイナリおよび非バイナリ構造の問題でMAC (検索中にGACを維持するアルゴリズム)のパフォーマンスが明らかに向上することを示します。
Automated Search for Impossibility Theorems in Social Choice Theory: Ranking Sets of Objects
社会選択理論における不可能定理の自動探索：オブジェクト集合のランキング
We present a method for using standard techniques from satisfiability checking to automatically verify and discover theorems in an area of economic theory known as ranking sets of objects. The key question in this area, which has important applications in social choice theory and decision making under uncertainty, is how to extend an agent’s preferences over a number of objects to a preference relation over nonempty sets of such objects. Certain combinations of seemingly natural principles for this kind of preference extension can result in logical inconsistencies, which has led to a number of important impossibility theorems. We first prove a general result that shows that for a wide range of such principles, characterised by their syntactic form when expressed in a many-sorted first-order logic, any impossibility exhibited at a fixed (small) domain size will necessarily extend to the general case. We then show how to formulate candidates for impossibility theorems at a fixed domain size in propositional logic, which in turn enables us to automatically search for (general) impossibility theorems using a SAT solver. When applied to a space of 20 principles for preference extension familiar from the literature, this method yields a total of 84 impossibility theorems, including both known and nontrivial new results.
本研究では、経済理論におけるオブジェクトのランキング集合として知られる定理を、充足可能性検証の標準的手法を用いて自動的に検証・発見する方法を提示します。社会選択理論や不確実性下での意思決定において重要な応用を持つこの分野の鍵となる問題は、エージェントの複数のオブジェクトに対する選好を、そのようなオブジェクトの空でない集合に対する選好関係にどのように拡張するかです。この種の選好拡張における一見自然な原理の組み合わせは、論理的な矛盾を引き起こす可能性があり、それが多くの重要な不可能性定理につながっています。本研究ではまず、多ソート一階述語論理で表現された際の統語的形式によって特徴付けられる、そのような原理の広範な範囲において、固定された（小さな）ドメインサイズで示されるあらゆる不可能性は、必然的に一般の場合にも拡張されることを示す一般的な結果を証明した。次に、命題論理において固定された領域サイズで不可能定理の候補を定式化する方法を示し、これによりSATソルバーを用いて（一般）不可能定理を自動的に探索することが可能になります。文献でよく知られている選好拡張の原理20個の空間にこの手法を適用すると、既知の結果と非自明な新しい結果の両方を含む合計84個の不可能定理が得られます。
Non-Deterministic Policies in Markovian Decision Processes
マルコフ決定過程における非決定論的ポリシー
Markovian processes have long been used to model stochastic environments. Reinforcement learning has emerged as a framework to solve sequential planning and decision-making problems in such environments. In recent years, attempts were made to apply methods from reinforcement learning to construct decision support systems for action selection in Markovian environments. Although conventional methods in reinforcement learning have proved to be useful in problems concerning sequential decision-making, they cannot be applied in their current form to decision support systems, such as those in medical domains, as they suggest policies that are often highly prescriptive and leave little room for the user’s input. Without the ability to provide flexible guidelines, it is unlikely that these methods can gain ground with users of such systems.This paper introduces the new concept of non-deterministic policies to allow more flexibility in the user’s decision-making process, while constraining decisions to remain near optimal solutions. We provide two algorithms to compute non-deterministic policies in discrete domains. We study the output and running time of these method on a set of synthetic and real-world problems. In an experiment with human subjects, we show that humans assisted by hints based on non-deterministic policies outperform both human-only and computer-only agents in a web navigation task.
マルコフ過程は、確率的環境のモデル化に長年用いられてきました。強化学習は、このような環境における逐次的な計画および意思決定問題を解決するための枠組みとして登場しました。近年、強化学習の手法をマルコフ環境における行動選択のための意思決定支援システムの構築に応用する試みがなされています。強化学習における従来の手法は、逐次的な意思決定に関する問題において有用であることが証明されていますが、医療分野などの意思決定支援システムには、現状のままでは適用できません。なぜなら、従来の手法は、しばしば非常に規範的な方針を示唆し、ユーザーの入力をほとんど考慮しないからです。柔軟なガイドラインを提供できない限り、これらの手法がこのようなシステムのユーザーに受け入れられる可能性は低いでしょう。本稿では、ユーザーの意思決定プロセスに柔軟性を持たせつつ、意思決定を最適解に近い状態に制約する、非決定論的方針という新しい概念を紹介します。離散領域において非決定論的方針を計算するための2つのアルゴリズムを提示します。これらの手法の出力と実行時間を、一連の合成問題と実世界問題に対して検証します。人間を被験者とした実験において、非決定論的なポリシーに基づくヒントによって支援された人間は、ウェブナビゲーションタスクにおいて、人間のみのエージェントとコンピュータのみのエージェントの両方よりも優れたパフォーマンスを発揮することを示す。