Journal of Artificial Intelligence Resarch Vol. 22 (2004)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。
Responsibility and Blame: A Structural-Model Approach
責任と非難：構造モデルアプローチ
Causality is typically treated an all-or-nothing concept; either A is a cause of B or it is not. We extend the definition of causality introduced by Halpern and Pearl [2004a] to take into account the degree of responsibility of A for B. For example, if someone wins an election 11-0, then each person who votes for him is less responsible for the victory than if he had won 6-5. We then define a notion of degree of blame, which takes into account an agent’s epistemic state. Roughly speaking, the degree of blame of A for B is the expected degree of responsibility of A for B, taken over the epistemic state of an agent.
因果関係は通常、全か無かの概念として扱われます。つまり、AがBの原因であるかそうでないかのどちらかです。私たちは、HalpernとPearl [2004a]によって導入された因果関係の定義を拡張し、Bに対するAの責任の度合いを考慮に入れます。たとえば、誰かが選挙で11対0で勝利した場合、その人に投票した各人は、6対5で勝利した場合よりも勝利に対する責任が少なくなります。そこで、エージェントの認識状態を考慮した責任度の概念を定義します。大まかに言えば、Bに対するAの責任度は、エージェントの認識状態におけるBに対するAの責任度の期待値です。
A Comprehensive Trainable Error Model for Sung Music Queries
歌曲クエリのための包括的学習可能エラーモデル
We propose a model for errors in sung queries, a variant of the hidden Markov model (HMM). This is a solution to the problem of identifying the degree of similarity between a (typically error-laden) sung query and a potential target in a database of musical works, an important problem in the field of music information retrieval. Similarity metrics are a critical component of `query-by-humming’ (QBH) applications which search audio and multimedia databases for strong matches to oral queries. Our model comprehensively expresses the types of {m error} or variation between target and query: cumulative and non-cumulative local errors, transposition, tempo and tempo changes, insertions, deletions and modulation. The model is not only expressive, but automatically trainable, or able to learn and generalize from query examples. We present results of simulations, designed to assess the discriminatory potential of the model, and tests with real sung queries, to demonstrate relevance to real-world applications.
我々は、隠れマルコフモデル（HMM）の変種である、歌唱クエリにおけるエラーモデルを提案します。これは、（典型的にはエラーを含む）歌唱クエリと音楽作品データベース内の潜在的なターゲットとの間の類似度を特定するという問題に対する解決策であり、音楽情報検索の分野における重要な問題です。類似度メトリクスは、音声およびマルチメディアデータベースから口頭クエリに強く一致するものを検索する「ハミングによるクエリ」（QBH）アプリケーションの重要な要素です。我々のモデルは、ターゲットとクエリ間の{mエラー}または変動の種類、すなわち累積的および非累積的な局所エラー、転置、テンポおよびテンポ変更、挿入、削除、変調を包括的に表現します。このモデルは表現力に富んでいるだけでなく、自動的にトレーニング可能であり、クエリ例から学習して一般化することができます。モデルの識別能力を評価するために設計されたシミュレーションの結果と、実際の歌われたクエリを使用したテストの結果を示し、現実世界のアプリケーションとの関連性を示します。
Generalizing Boolean Satisfiability II: Theory
ブール充足可能性の一般化 II：理論
This is the second of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal is to define a representation in which this structure is apparent and can easily be exploited to improve computational performance. This paper presents the theoretical basis for the ideas underlying ZAP, arguing that existing ideas in this area exploit a single, recurring structure in that multiple database axioms can be obtained by operating on a single axiom using a subgroup of the group of permutations on the literals in the problem. We argue that the group structure precisely captures the general structure at which earlier approaches hinted, and give numerous examples of its use. We go on to extend the Davis-Putnam-Logemann-Loveland inference procedure to this broader setting, and show that earlier computational improvements are either subsumed or left intact by the new method. The third paper in this series discusses ZAP’s implementation and presents experimental performance results.
本稿は、ZAPについて説明する予定の3本の論文のうちの2本目です。ZAPは、既存のツールを大幅に一般化しつつ、現代の高性能ソルバーの性能特性を維持する充足可能性エンジンです。ZAPの根底にある基本的な考え方は、このようなエンジンに渡される多くの問題が、使用されるブール表現では隠蔽される豊富な内部構造を含んでいるというものです。私たちの目標は、この構造が明確で、計算性能の向上に容易に活用できる表現を定義することです。本稿では、ZAPの根底にある考え方の理論的根拠を提示し、この分野における既存の考え方は、問題内のリテラルの順列群の部分群を用いて単一の公理を操作することで、複数のデータベース公理が得られるという点で、単一の繰り返し構造を活用していると主張します。私たちは、この群構造が、以前のアプローチが示唆していた一般構造を正確に捉えていると主張し、その使用例を多数示します。我々は、Davis-Putnam-Logemann-Loveland推論手順をこのより広範な設定に拡張し、以前の計算改善が新しい手法によって吸収されるか、あるいはそのまま維持されるかを示します。本シリーズの3番目の論文では、ZAPの実装について議論し、実験的なパフォーマンス結果を示します。
LexRank: Graph-based Lexical Centrality as Salience in Text Summarization
LexRank：テキスト要約における顕著性としてのグラフベースの語彙中心性
We introduce a stochastic graph-based method for computing relative importance of textual units for Natural Language Processing. We test the technique on the problem of Text Summarization (TS). Extractive TS relies on the concept of sentence salience to identify the most important sentences in a document or set of documents. Salience is typically defined in terms of the presence of particular important words or in terms of similarity to a centroid pseudo-sentence. We consider a new approach, LexRank, for computing sentence importance based on the concept of eigenvector centrality in a graph representation of sentences. In this model, a connectivity matrix based on intra-sentence cosine similarity is used as the adjacency matrix of the graph representation of sentences. Our system, based on LexRank ranked in first place in more than one task in the recent DUC 2004 evaluation. In this paper we present a detailed analysis of our approach and apply it to a larger data set including data from earlier DUC evaluations. We discuss several methods to compute centrality using the similarity graph. The results show that degree-based methods (including LexRank) outperform both centroid-based methods and other systems participating in DUC in most of the cases. Furthermore, the LexRank with threshold method outperforms the other degree-based techniques including continuous LexRank. We also show that our approach is quite insensitive to the noise in the data that may result from an imperfect topical clustering of documents.
自然言語処理のためのテキスト単位の相対的な重要度を計算するための、確率的グラフベースの手法を紹介します。我々はテキスト要約(TS)の問題でこの手法をテストします。抽出TSは、文書または文書セット内の最も重要な文を識別するために文の顕著性の概念に依存しています。顕著性は通常、特定の重要な単語の存在または重心疑似文との類似性によって定義されます。我々は、文のグラフ表現における固有ベクトル中心性の概念に基づいて文の重要度を計算する新しいアプローチ、LexRankを検討します。このモデルでは、文内コサイン類似度に基づく接続行列が、文のグラフ表現の隣接行列として使用されます。LexRankに基づく当社のシステムは、最近のDUC 2004評価の複数のタスクで1位にランクされました。本稿では、このアプローチの詳細な分析を示し、以前のDUC評価のデータを含む大規模なデータ セットにそれを適用します。類似度グラフを使用して中心性を計算するいくつかの方法について説明します。結果は、次数ベースの手法（LexRankを含む）が、ほとんどの場合、重心ベースの手法およびDUCに参加する他のシステムよりも優れた性能を示すことを示しています。さらに、閾値法を用いたLexRankは、連続LexRankを含む他の次数ベースの手法よりも優れた性能を示します。また、本手法は、文書のトピッククラスタリングが不完全であることから生じる可能性のあるデータノイズに対して非常に鈍感であることも示しています。
Solving Transition Independent Decentralized Markov Decision Processes
遷移に依存しない分散マルコフ決定過程の解法
Formal treatment of collaborative multi-agent systems has been lagging behind the rapid progress in sequential decision making by individual agents. Recent work in the area of decentralized Markov Decision Processes (MDPs) has contributed to closing this gap, but the computational complexity of these models remains a serious obstacle. To overcome this complexity barrier, we identify a specific class of decentralized MDPs in which the agents’ transitions are independent. The class consists of independent collaborating agents that are tied together through a structured global reward function that depends on all of their histories of states and actions. We present a novel algorithm for solving this class of problems and examine its properties, both as an optimal algorithm and as an anytime algorithm. To our best knowledge, this is the first algorithm to optimally solve a non-trivial subclass of decentralized MDPs. It lays the foundation for further work in this area on both exact and approximate algorithms.
協調型マルチエージェントシステムの形式的処理は、個々のエージェントによる逐次的意思決定の急速な進歩に遅れをとっています。分散型マルコフ決定過程（MDP）の分野における最近の研究はこのギャップを埋めるのに貢献しましたが、これらのモデルの計算複雑性は依然として大きな障害となっています。この複雑性の壁を克服するために、我々はエージェントの遷移が独立している特定のクラスの分散型MDPを特定します。このクラスは、状態と行動の履歴すべてに依存する構造化されたグローバル報酬関数によって結び付けられた、独立した協調エージェントで構成されます。我々は、このクラスの問題を解くための新しいアルゴリズムを提示し、最適アルゴリズムおよびいつでもアルゴリズムとしての特性を検証します。我々の知る限り、これは分散型MDPの非自明なサブクラスを最適に解く最初のアルゴリズムです。これは、この分野における正確なアルゴリズムと近似アルゴリズムの両方のさらなる研究の基礎を築くものです。
On Prediction Using Variable Order Markov Models
可変順序マルコフモデルを用いた予測について
This paper is concerned with algorithms for prediction of discrete sequences over a finite alphabet, using variable order Markov models. The class of such algorithms is large and in principle includes any lossless compression algorithm. We focus on six prominent prediction algorithms, including Context Tree Weighting (CTW), Prediction by Partial Match (PPM) and Probabilistic Suffix Trees (PSTs). We discuss the properties of these algorithms and compare their performance using real life sequences from three domains: proteins, English text and music pieces. The comparison is made with respect to prediction quality as measured by the average log-loss. We also compare classification algorithms based on these predictors with respect to a number of large protein classification tasks. Our results indicate that a “decomposed” CTW (a variant of the CTW algorithm) and PPM outperform all other algorithms in sequence prediction tasks. Somewhat surprisingly, a different algorithm, which is a modification of the Lempel-Ziv compression algorithm, significantly outperforms all algorithms on the protein classification problems.
本論文は、可変順序マルコフモデルを用いて、有限アルファベット上の離散配列を予測するアルゴリズムについて考察します。このようなアルゴリズムのクラスは広く、原理的にはあらゆる可逆圧縮アルゴリズムが含まれます。本論文では、文脈木重み付け（CTW）、部分一致予測（PPM）、確率的接尾辞木（PST）を含む6つの主要な予測アルゴリズムに焦点を当てる。これらのアルゴリズムの特性を考察し、タンパク質、英語テキスト、楽曲という3つの領域における実際の配列を用いて、その性能を比較します。比較は、平均対数損失で測定された予測品質に基づいて行う。また、これらの予測子に基づく分類アルゴリズムを、いくつかの大規模なタンパク質分類タスクにおいて比較します。その結果、「分解」CTW（CTWアルゴリズムの変種）とPPMが、配列予測タスクにおいて他のすべてのアルゴリズムよりも優れた性能を示すことが示されました。やや意外なことに、Lempel-Ziv圧縮アルゴリズムを改良した別のアルゴリズムが、タンパク質分類問題においてすべてのアルゴリズムを大幅に上回る性能を示した。
Existence of Multiagent Equilibria with Limited Agents
エージェント数が制限されたマルチエージェント均衡の存在
Multiagent learning is a necessary yet challenging problem as multiagent systems become more prevalent and environments become more dynamic. Much of the groundbreaking work in this area draws on notable results from game theory, in particular, the concept of Nash equilibria. Learners that directly learn an equilibrium obviously rely on their existence. Learners that instead seek to play optimally with respect to the other players also depend upon equilibria since equilibria are fixed points for learning. From another perspective, agents with limitations are real and common. These may be undesired physical limitations as well as self-imposed rational limitations, such as abstraction and approximation techniques, used to make learning tractable. This article explores the interactions of these two important concepts: equilibria and limitations in learning. We introduce the question of whether equilibria continue to exist when agents have limitations. We look at the general effects limitations can have on agent behavior, and define a natural extension of equilibria that accounts for these limitations. Using this formalization, we make three major contributions: (i) a counterexample for the general existence of equilibria with limitations, (ii) sufficient conditions on limitations that preserve their existence, (iii) three general classes of games and limitations that satisfy these conditions. We then present empirical results from a specific multiagent learning algorithm applied to a specific instance of limited agents. These results demonstrate that learning with limitations is feasible, when the conditions outlined by our theoretical analysis hold.
マルチエージェントシステムがより普及し、環境がより動的になるにつれて、マルチエージェント学習は必要かつ困難な問題となります。この分野における画期的な研究の多くは、ゲーム理論、特にナッシュ均衡の概念からの注目すべき成果を利用しています。均衡を直接学習する学習者は、明らかにその存在に依存しています。均衡は学習の固定点であるため、他のプレイヤーとの関係で最適にプレイすることを求める学習者も均衡に依存します。別の視点から見ると、制限のあるエージェントは現実的かつ一般的です。これらの制限には、学習を扱いやすくするために使用される抽象化や近似手法などの自己課した合理的な制限だけでなく、望ましくない物理的な制限がある場合があります。この記事では、学習における均衡と制限という2つの重要な概念の相互作用について説明します。エージェントに制限がある場合でも均衡が存在し続けるかどうかという問題を紹介します。制限がエージェントの行動に及ぼす一般的な影響を確認し、これらの制限を考慮した均衡の自然な拡張を定義します。この形式化を用いて、我々は3つの主要な貢献を行う。(i)制約付き均衡の一般的な存在に対する反例、(ii)制約の存在を維持する十分条件、(iii)これらの条件を満たす3つの一般的なゲームと制約のクラスです。次に、特定のマルチエージェント学習アルゴリズムを、制約付きエージェントの特定のインスタンスに適用した実験結果を示す。これらの結果は、我々の理論分析によって概説された条件が満たされる場合、制約付き学習が実現可能であることを示す。
Towards Understanding and Harnessing the Potential of Clause Learning
節学習の可能性の理解と活用に向けて
Efficient implementations of DPLL with the addition of clause learning are the fastest complete Boolean satisfiability solvers and can handle many significant real-world problems, such as verification, planning and design. Despite its importance, little is known of the ultimate strengths and limitations of the technique. This paper presents the first precise characterization of clause learning as a proof system (CL), and begins the task of understanding its power by relating it to the well-studied resolution proof system. In particular, we show that with a new learning scheme, CL can provide exponentially shorter proofs than many proper refinements of general resolution (RES) satisfying a natural property. These include regular and Davis-Putnam resolution, which are already known to be much stronger than ordinary DPLL. We also show that a slight variant of CL with unlimited restarts is as powerful as RES itself. Translating these analytical results to practice, however, presents a challenge because of the nondeterministic nature of clause learning algorithms. We propose a novel way of exploiting the underlying problem structure, in the form of a high level problem description such as a graph or PDDL specification, to guide clause learning algorithms toward faster solutions. We show that this leads to exponential speed-ups on grid and randomized pebbling problems, as well as substantial improvements on certain ordering formulas.
節学習を追加したDPLLの効率的な実装は、最速の完全ブール充足可能性ソルバーであり、検証、計画、設計など、多くの重要な現実世界の問題を処理できます。その重要性にもかかわらず、この手法の究極の強みと限界についてはほとんど知られていません。本論文では、節学習を証明システム（CL）として初めて正確に特徴付け、よく研究されている導出証明システムと関連付けることで、その威力を理解する作業を開始します。特に、新しい学習スキームを用いることで、CLは、自然な性質を満たす一般導出（RES）の多くの適切な改良よりも指数関数的に短い証明を提供できることを示します。これには、通常のDPLLよりもはるかに強力であることが既に知られている通常の導出とデイビス・パトナム導出が含まれます。また、無制限の再開を持つCLのわずかなバリエーションが、RES自体と同じくらい強力であることも示します。しかし、これらの解析結果を実践に移すことは、節学習アルゴリズムの非決定性のために困難です。私たちは、グラフやPDDL仕様などの高レベルの問題記述の形で、根本的な問題構造を活用し、節学習アルゴリズムをより高速に解くように導く新しい方法を提案します。これにより、グリッド問題とランダムペブリング問題が指数関数的に高速化され、特定の順序付け公式が大幅に改善されることを示します。
Additive Pattern Database Heuristics
加法パターンデータベースヒューリスティックス
We explore a method for computing admissible heuristic evaluation functions for search problems. It utilizes pattern databases, which are precomputed tables of the exact cost of solving various subproblems of an existing problem. Unlike standard pattern database heuristics, however, we partition our problems into disjoint subproblems, so that the costs of solving the different subproblems can be added together without overestimating the cost of solving the original problem. Previously, we showed how to statically partition the sliding-tile puzzles into disjoint groups of tiles to compute an admissible heuristic, using the same partition for each state and problem instance. Here we extend the method and show that it applies to other domains as well. We also present another method for additive heuristics which we call dynamically partitioned pattern databases. Here we partition the problem into disjoint subproblems for each state of the search dynamically. We discuss the pros and cons of each of these methods and apply both methods to three different problem domains: the sliding-tile puzzles, the 4-peg Towers of Hanoi problem, and finding an optimal vertex cover of a graph. We find that in some problem domains, static partitioning is most effective, while in others dynamic partitioning is a better choice. In each of these problem domains, either statically partitioned or dynamically partitioned pattern database heuristics are the best known heuristics for the problem.
探索問題に対する許容ヒューリスティック評価関数を計算する手法を検討します。この手法では、パターン データベースを利用します。パターン データベースとは、既存の問題のさまざまな部分問題を解くための正確なコストを事前に計算したテーブルです。ただし、標準的なパターン データベース ヒューリスティックとは異なり、問題を互いに素な部分問題に分割することで、元の問題を解くコストを過大評価することなく、さまざまな部分問題を解くコストを合計することができます。以前、スライディング タイル パズルを互いに素なタイルのグループに静的に分割し、各状態と問題インスタンスに同じ分割を使用して、許容ヒューリスティックを計算する方法を示しました。今回はこの手法を拡張し、他の領域にも適用できることを示します。また、動的に分割されたパターン データベースと呼ぶ、加法的なヒューリスティックの別の手法も紹介します。この手法では、探索の各状態について、問題を互いに素な部分問題に動的に分割します。これらの手法それぞれの長所と短所について議論し、両方の手法を3つの異なる問題領域（スライディングタイルパズル、4ペグのハノイの塔問題、グラフの最適頂点被覆問題）に適用します。その結果、静的分割が最も効果的な問題領域もあれば、動的分割がより効果的な問題領域もあることがわかりました。これらの各問題領域において、静的分割または動的分割のパターンデータベースヒューリスティックは、問題に対する最もよく知られたヒューリスティックです。
Ordinal and Probabilistic Representations of Acceptance
受容の順序表現と確率表現
An accepted belief is a proposition considered likely enough by an agent, to be inferred from as if it were true. This paper bridges the gap between probabilistic and logical representations of accepted beliefs. To this end, natural properties of relations on propositions, describing relative strength of belief are augmented with some conditions ensuring that accepted beliefs form a deductively closed set. This requirement turns out to be very restrictive. In particular, it is shown that the sets of accepted belief of an agent can always be derived from a family of possibility rankings of states. An agent accepts a proposition in a given context if this proposition is considered more possible than its negation in this context, for all possibility rankings in the family. These results are closely connected to the non-monotonic ‘preferential’ inference system of Kraus, Lehmann and Magidor and the so-called plausibility functions of Friedman and Halpern. The extent to which probability theory is compatible with acceptance relations is laid bare. A solution to the lottery paradox, which is considered as a major impediment to the use of non-monotonic inference is proposed using a special kind of probabilities (called lexicographic, or big-stepped). The setting of acceptance relations also proposes another way of approaching the theory of belief change after the works of Gärdenfors and colleagues. Our view considers the acceptance relation as a primitive object from which belief sets are derived in various contexts.
受容信念とは、エージェントが十分に蓋然性が高いとみなし、あたかもそれが真実であるかのように推論できる命題です。本論文は、受容信念の確率的表現と論理的表現の間のギャップを埋める。この目的のため、命題間の関係における自然な性質、すなわち信念の相対的な強さを記述するものに、受容信念が演繹的に閉じた集合を形成することを保証するいくつかの条件を付加します。この要件は非常に厳しいことが判明します。特に、エージェントの受容信念の集合は、常に状態の可能性順位の族から導出できることが示されます。エージェントは、与えられた文脈において、その族内のすべての可能性順位において、ある命題がその文脈におけるその否定よりも蓋然性が高いとみなされる場合、その命題を受容します。これらの結果は、クラウス、レーマン、マギドールの非単調な「選好的」推論システム、およびフリードマンとハルパーンのいわゆる尤度関数と密接に関連しています。確率論が受容関係とどの程度両立するかが明らかになります。非単調推論の適用における大きな障害と考えられている宝くじパラドックスに対する解決策として、特殊な種類の確率（辞書式確率またはビッグステップ確率と呼ばれる）を用いる方法が提案されています。受容関係の設定は、ガーデンフォースらの研究に倣い、信念変化理論への新たなアプローチも提案しています。我々の見解では、受容関係は様々な文脈において信念集合が導出される基本的対象です。
Ordered Landmarks in Planning
計画における順序付きランドマーク
Many known planning tasks have inherent constraints concerning the best order in which to achieve the goals. A number of research efforts have been made to detect such constraints and to use them for guiding search, in the hope of speeding up the planning process. We go beyond the previous approaches by considering ordering constraints not only over the (top-level) goals, but also over the sub-goals that will necessarily arise during planning. Landmarks are facts that must be true at some point in every valid solution plan. We extend Koehler and Hoffmann’s definition of reasonable orders between top level goals to the more general case of landmarks. We show how landmarks can be found, how their reasonable orders can be approximated, and how this information can be used to decompose a given planning task into several smaller sub-tasks. Our methodology is completely domain- and planner-independent. The implementation demonstrates that the approach can yield significant runtime performance improvements when used as a control loop around state-of-the-art sub-optimal planning systems, as exemplified by FF and LPG.
多くの既知の計画タスクには、目標を達成するための最適な順序に関する固有の制約があります。計画プロセスを高速化することを目的として、このような制約を検出し、探索を誘導するためにそれらを使用する多くの研究が行われてきました。我々は、（最上位の）目標だけでなく、計画中に必然的に生じるサブ目標についても順序制約を考慮することで、従来のアプローチを凌駕します。ランドマークとは、すべての有効な解計画において、ある時点で必ず真となる事実です。我々は、ケーラーとホフマンによる最上位目標間の合理的な順序の定義を、ランドマークのより一般的なケースに拡張します。ランドマークの発見方法、その妥当な順序の近似値化方法、そしてこの情報を用いて特定の計画タスクを複数の小さなサブタスクに分解する方法を示します。本手法は、ドメインおよびプランナに完全に依存しません。実装により、FFやLPGに代表される最先端の準最適計画システムの制御ループとして本手法を用いた場合、実行時パフォーマンスが大幅に向上することが実証されました。
Use of Markov Chains to Design an Agent Bidding Strategy for Continuous Double Auctions
マルコフ連鎖を用いた連続ダブルオークションにおけるエージェント入札戦略の設計
As computational agents are developed for increasingly complicated e-commerce applications, the complexity of the decisions they face demands advances in artificial intelligence techniques. For example, an agent representing a seller in an auction should try to maximize the seller?s profit by reasoning about a variety of possibly uncertain pieces of information, such as the maximum prices various buyers might be willing to pay, the possible prices being offered by competing sellers, the rules by which the auction operates, the dynamic arrival and matching of offers to buy and sell, and so on. A naive application of multiagent reasoning techniques would require the seller?s agent to explicitly model all of the other agents through an extended time horizon, rendering the problem intractable for many realistically-sized problems. We have instead devised a new strategy that an agent can use to determine its bid price based on a more tractable Markov chain model of the auction process. We have experimentally identified the conditions under which our new strategy works well, as well as how well it works in comparison to the optimal performance the agent could have achieved had it known the future. Our results show that our new strategy in general performs well, outperforming other tractable heuristic strategies in a majority of experiments, and is particularly effective in a ‘seller?s market’, where many buy offers are available.
ますます複雑化する電子商取引アプリケーション向けに計算エージェントが開発されるにつれ、それらが直面する意思決定の複雑さは、人工知能技術の進歩を要求します。例えば、オークションで売り手を代表するエージェントは、様々な買い手が支払う可能性のある最高価格、競合する売り手が提示する可能性のある価格、オークションの運営ルール、売買オファーの動的な到着とマッチングなど、不確実性を伴う可能性のある様々な情報について推論することにより、売り手の利益を最大化しようと努める必要があります。マルチエージェント推論技術を単純に適用すると、売り手のエージェントは他のすべてのエージェントを長期間にわたって明示的にモデル化する必要があり、多くの現実的な規模の問題ではこの問題は扱いにくくなります。そこで我々は、オークションプロセスのより扱いやすいマルコフ連鎖モデルに基づいてエージェントが入札価格を決定できる新しい戦略を考案した。我々は、新しい戦略が効果的に機能する条件、そしてエージェントが未来を知っていた場合に達成できたであろう最適なパフォーマンスと比較して、どの程度効果的に機能するかを実験的に特定しました。結果は、新しい戦略が一般的に優れたパフォーマンスを発揮し、大多数の実験において他の扱いやすいヒューリスティック戦略を上回り、特に多くの買いオファーが存在する「売り手市場」において効果的であることを示しています。
Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis
協調システムの分散制御：分類と複雑性分析
Decentralized control of cooperative systems captures the operation of a group of decision makers that share a single global objective. The difficulty in solving optimally such problems arises when the agents lack full observability of the global state of the system when they operate. The general problem has been shown to be NEXP-complete. In this paper, we identify classes of decentralized control problems whose complexity ranges between NEXP and P. In particular, we study problems characterized by independent transitions, independent observations, and goal-oriented objective functions. Two algorithms are shown to solve optimally useful classes of goal-oriented decentralized processes in polynomial time. This paper also studies information sharing among the decision-makers, which can improve their performance. We distinguish between three ways in which agents can exchange information: indirect communication, direct communication and sharing state features that are not controlled by the agents. Our analysis shows that for every class of problems we consider, introducing direct or indirect communication does not change the worst-case complexity. The results provide a better understanding of the complexity of decentralized control problems that arise in practice and facilitate the development of planning algorithms for these problems.
協調システムの分散制御は、単一の全体的目標を共有する意思決定者グループの活動を捉える。このような問題を最適に解くことが困難になるのは、エージェントが動作時にシステムの全体的状態を完全に観測できない場合です。この問題はNEXP完全であることが示されています。本稿では、複雑度がNEXPからPの範囲にある分散制御問題のクラスを特定します。特に、独立遷移、独立観測、および目標指向目的関数を特徴とする問題を考察します。2つのアルゴリズムが、目標指向分散プロセスの最適有用クラスを多項式時間で解くことを示す。本稿では、意思決定者間の情報共有についても考察します。情報共有は意思決定者のパフォーマンスを向上させる可能性があります。エージェントが情報を交換する方法は、間接通信、直接通信、およびエージェントによって制御されていない状態特性の共有の3つに分類されます。本稿の分析は、検討するすべての問題クラスにおいて、直接通信または間接通信を導入しても、最悪ケースの複雑度は変化しないことを示す。これらの結果は、実際に生じる分散制御問題の複雑さをより深く理解し、これらの問題に対する計画アルゴリズムの開発を促進します。
Explicit Learning Curves for Transduction and Application to Clustering and Compression Algorithms
トランスダクションのための明示的学習曲線とクラスタリングおよび圧縮アルゴリズムへの応用
Inductive learning is based on inferring a general rule from a finite data set and using it to label new data. In transduction one attempts to solve the problem of using a labeled training set to label a set of unlabeled points, which are given to the learner prior to learning. Although transduction seems at the outset to be an easier task than induction, there have not been many provably useful algorithms for transduction. Moreover, the precise relation between induction and transduction has not yet been determined. The main theoretical developments related to transduction were presented by Vapnik more than twenty years ago. One of Vapnik’s basic results is a rather tight error bound for transductive classification based on an exact computation of the hypergeometric tail. While tight, this bound is given implicitly via a computational routine. Our first contribution is a somewhat looser but explicit characterization of a slightly extended PAC-Bayesian version of Vapnik’s transductive bound. This characterization is obtained using concentration inequalities for the tail of sums of random variables obtained by sampling without replacement. We then derive error bounds for compression schemes such as (transductive) support vector machines and for transduction algorithms based on clustering. The main observation used for deriving these new error bounds and algorithms is that the unlabeled test points, which in the transductive setting are known in advance, can be used in order to construct useful data dependent prior distributions over the hypothesis space.
帰納的学習は、有限のデータセットから一般的な規則を推論し、それを用いて新しいデータにラベルを付けるという学習法に基づいています。トランスダクションでは、学習前に学習者に与えられるラベルのない点の集合に、ラベル付きの訓練セットを用いてラベルを付けるという問題を解決しようとします。トランスダクションは一見帰納的学習よりも容易なタスクのように見えますが、トランスダクションに有効であることが証明されているアルゴリズムは多くありません。さらに、帰納的学習とトランスダクションの正確な関係はまだ解明されていません。トランスダクションに関する主要な理論的発展は、20年以上前にVapnikによって発表されました。Vapnikの基本的な成果の1つは、超幾何的裾の正確な計算に基づく、トランスダクティブ分類のかなり厳密な誤差境界です。この境界は厳密ではありますが、計算ルーチンによって暗黙的に与えられます。私たちの最初の貢献は、Vapnikのトランスダクティブ境界の若干拡張されたPACベイズ版の、いくぶん緩やかですが明示的な特徴付けです。この特徴付けは、非復元サンプリングによって得られたランダム変数の和の裾の集中不等式を使用して得られます。次に、(トランスダクティブ)サポートベクターマシンなどの圧縮スキームと、クラスタリングに基づくトランスダクションアルゴリズムの誤差境界を導出します。これらの新しい誤差境界とアルゴリズムを導出するために使用された主な観察は、トランスダクティブ設定で事前にわかっているラベルなしテストポイントを使用して、仮説空間上に有用なデータ依存事前分布を構築できるという点です。
A Maximal Tractable Class of Soft Constraints
最大限に扱いやすいソフト制約のクラス
Many researchers in artificial intelligence are beginning to explore the use of soft constraints to express a set of (possibly conflicting) problem requirements. A soft constraint is a function defined on a collection of variables which associates some measure of desirability with each possible combination of values for those variables. However, the crucial question of the computational complexity of finding the optimal solution to a collection of soft constraints has so far received very little attention. In this paper we identify a class of soft binary constraints for which the problem of finding the optimal solution is tractable. In other words, we show that for any given set of such constraints, there exists a polynomial time algorithm to determine the assignment having the best overall combined measure of desirability. This tractable class includes many commonly-occurring soft constraints, such as ‘as near as possible’ or ‘as soon as possible after’, as well as crisp constraints such as ‘greater than’. Finally, we show that this tractable class is maximal, in the sense that adding any other form of soft binary constraint which is not in the class gives rise to a class of problems which is NP-hard.
人工知能の多くの研究者は、（おそらく矛盾する）問題要件の集合を表現するためにソフト制約の使用を検討し始めています。ソフト制約とは、変数の集合に対して定義される関数であり、それらの変数の値の可能な組み合わせごとに、望ましさの尺度を関連付けます。しかし、ソフト制約の集合に対する最適解を見つけるための計算の複雑さという重要な問題は、これまでほとんど注目されていません。本論文では、最適解を見つける問題が扱いやすいソフトバイナリ制約のクラスを特定します。言い換えれば、そのような制約の任意の集合に対して、全体的な望ましさの総合的な尺度が最良の割り当てを決定する多項式時間アルゴリズムが存在することを示します。この扱いやすいクラスには、「できるだけ近い」や「できるだけ早く」といったよく使われるソフト制約や、「より大きい」といった明確な制約が多数含まれます。最後に、この扱いやすいクラスは、このクラスに含まれない他の形式のソフトバイナリ制約を追加するとNP困難な問題クラスが生じるという意味で最大であることを示します。