From jairmail@ISI.EDU Tue Jan 21 17:07:49 2003 Received: from nitro.isi.edu (nitro.isi.edu [128.9.208.207]) by gamma.isi.edu (8.11.6/8.11.2) with ESMTP id h0M17mD10439 for ; Tue, 21 Jan 2003 17:07:48 -0800 (PST) Received: (from jairmail@localhost) by nitro.isi.edu (8.11.6/8.11.2) id h0M17mF22876; Tue, 21 Jan 2003 17:07:48 -0800 (PST) Date: Tue, 21 Jan 2003 17:07:48 -0800 (PST) Message-Id: <200301220107.h0M17mF22876@nitro.isi.edu> From: JAIRMAIL To: jairsubscribers@ISI.EDU Subject: [Jairsubscribers] Welcome JAIR Subscribers Sender: jairsubscribers-admin@mailman.isi.edu Errors-To: jairsubscribers-admin@mailman.isi.edu X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.0.5 Precedence: bulk Reply-To: jair-ed@isi.edu List-Help: List-Archive: Dear JAIR Subscribers: Thank you for resubscribing to the JAIR mailing list. We plan to send out notices every two months or so listing new JAIR papers. If you have any comments or questions, please send mail to jair-ed@isi.edu. Note that this mailing list is read only... we do not accept any posts here. To unsubscribe, visit http://mailman.isi.edu/mailman/listinfo/jairsubscribers Since notices were not sent out over the last few months due to the problems with our previous mailing system, below you'll find a list of recent papers for your convenience: Wolpert, D.H. and Tumer, K. (2002) "Collective Intelligence, Data Routing and Braess' Paradox" Pynadath, D.V. and Tambe, M. (2002) "The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models" Baget, J.F. and Mugnier, M.L. (2002) "Extensions of Simple Conceptual Graphs: the Complexity of Rules and Constraints" Howe, A.E. and Dahlman, E. (2002) "A Critical Assessment of Benchmark Comparison in Planning" Barzilay, R., Elhadad, N., and McKeown K.R. (2002) "Inferring Strategies for Sentence Ordering in Multidocument News Summarization" Halpern, J.Y. and Pucella, R. (2002) "A Logic for Reasoning about Upper Probabilities" Kaminka, G.A., Pynadath, D.V. and Tambe, M. (2002) "Monitoring Teams by Overhearing: A Multi-Agent Plan-Recognition Approach" Nock, R. (2002) "Inducing Interpretable Voting Classifiers without Trading Accuracy for Simplicity: Theoretical Results, Approximation Algorithms, and Experiments" Scerri, P., Pynadath, D.V., Tampe, M. (2002) "Towards Adjustable Autonomy for the Real World" Volume 17, pages 171-228. Darwiche, A. and Marquis, P. (2002) "A Knowledge Compilation Map" Chan, H. and Darwiche, A. (2002) "When do Numbers Really Matter?" Bod, R. (2002) "A Unified Model of Structural Organization in Language and Music" Gao, Y. and Culberson, J. (2002) "An Analysis of Phase Transition in NK Landscapes" Al-Ani, A. and Deriche, M. (2002) "A New Technique for Combining Multiple Classifiers using The Dempster-Shafer Theory of Evidence" Tennenholtz, M. (2002) "Competitive Safety Analysis: Robust Decision-Making in Multi-Agent Systems" Fern, A., Givan, R., and Siskind, J.M. (2002) "Specific-to-General Learning for Temporal Events with Application to Learning Event Definitions from Video" Bui, H.H., Venkatesh, S., and West, G. (2002) "Policy Recognition in the Abstract Hidden Markov Model" Gamberger, D. and Lavrac, N. (2002) "Expert-Guided Subgroup Discovery: Methodology and Application" From jairmail@ISI.EDU Fri Feb 28 17:36:27 2003 Received: from nitro.isi.edu (nitro.isi.edu [128.9.208.207]) by gamma.isi.edu (8.11.6/8.11.2) with ESMTP id h211aRD13829 for ; Fri, 28 Feb 2003 17:36:27 -0800 (PST) Received: (from jairmail@localhost) by nitro.isi.edu (8.11.6/8.11.2) id h211aQE18356; Fri, 28 Feb 2003 17:36:26 -0800 (PST) Date: Fri, 28 Feb 2003 17:36:26 -0800 (PST) Message-Id: <200303010136.h211aQE18356@nitro.isi.edu> From: JAIRMAIL To: jairsubscribers@ISI.EDU Subject: [Jairsubscribers] Recent JAIR articles Sender: jairsubscribers-admin@mailman.isi.edu Errors-To: jairsubscribers-admin@mailman.isi.edu X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.0.5 Precedence: bulk Reply-To: jair-ed@isi.edu List-Help: List-Archive: CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) - Halpern, J.Y. (1999) "Cox's Theorem Revisited" - Kambhampati, S. (2000) "Planning Graph as a (Dynamic) CSP: Exploiting EBL, DDB and other CSP Search Techniques in Graphplan" - Barber, F. (2000) "Reasoning on Interval and Point-based Disjunctive Metric Constraints in Temporal Contexts" ---------------------------------------------------------------- I. NEW ARTICLES: Halpern, J.Y. (1999) "Cox's Theorem Revisited", Volume 11, pages 429-435. Available in PDF, PostScript and compressed PostScript. For quick access go to Abstract: The assumptions needed to prove Cox's Theorem are discussed and examined. Various sets of assumptions under which a Cox-style theorem can be proved are provided, although all are rather strong and, arguably, not natural. Kambhampati, S. (2000) "Planning Graph as a (Dynamic) CSP: Exploiting EBL, DDB and other CSP Search Techniques in Graphplan", Volume 12, pages 1-34. Available in PDF, PostScript and compressed PostScript. For quick access go to Abstract: This paper reviews the connections between Graphplan's planning-graph and the dynamic constraint satisfaction problem and motivates the need for adapting CSP search techniques to the Graphplan algorithm. It then describes how explanation based learning, dependency directed backtracking, dynamic variable ordering, forward checking, sticky values and random-restart search strategies can be adapted to Graphplan. Empirical results are provided to demonstrate that these augmentations improve Graphplan's performance significantly (up to 1000x speedups) on several benchmark problems. Special attention is paid to the explanation-based learning and dependency directed backtracking techniques as they are empirically found to be most useful in improving the performance of Graphplan. Barber, F. (2000) "Reasoning on Interval and Point-based Disjunctive Metric Constraints in Temporal Contexts", Volume 12, pages 35-86. Available in HTML, PDF, PostScript and compressed PostScript. For quick access go to Abstract: We introduce a temporal model for reasoning on disjunctive metric constraints on intervals and time points in temporal contexts. This temporal model is composed of a labeled temporal algebra and its reasoning algorithms. The labeled temporal algebra defines labeled disjunctive metric point-based constraints, where each disjunct in each input disjunctive constraint is univocally associated to a label. Reasoning algorithms manage labeled constraints, associated label lists, and sets of mutually inconsistent disjuncts. These algorithms guarantee consistency and obtain a minimal network. Additionally, constraints can be organized in a hierarchy of alternative temporal contexts. Therefore, we can reason on context-dependent disjunctive metric constraints on intervals and points. Moreover, the model is able to represent non-binary constraints, such that logical dependencies on disjuncts in constraints can be handled. The computational cost of reasoning algorithms is exponential in accordance with the underlying problem complexity, although some improvements are proposed. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) Each complete volume of JAIR is also published by Morgan Kaufmann Publishers. To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from either of the two sites below: CMU Machine: ftp.cs.cmu.edu directory: project/jair Genoa Machine: ftp.mrg.dist.unige.it directory: pub/jair/pub -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/) and follow the link "notify me of new articles". In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jairmail@ISI.EDU Fri Feb 28 18:06:43 2003 Received: from nitro.isi.edu (nitro.isi.edu [128.9.208.207]) by gamma.isi.edu (8.11.6/8.11.2) with ESMTP id h2126hD05763 for ; Fri, 28 Feb 2003 18:06:43 -0800 (PST) Received: (from jairmail@localhost) by nitro.isi.edu (8.11.6/8.11.2) id h2126gj06603; Fri, 28 Feb 2003 18:06:42 -0800 (PST) Date: Fri, 28 Feb 2003 18:06:42 -0800 (PST) Message-Id: <200303010206.h2126gj06603@nitro.isi.edu> From: JAIRMAIL To: jairsubscribers@ISI.EDU Subject: [Jairsubscribers] Correction! New articles... Sender: jairsubscribers-admin@mailman.isi.edu Errors-To: jairsubscribers-admin@mailman.isi.edu X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.0.5 Precedence: bulk Reply-To: jair-ed@isi.edu List-Help: List-Archive: My apologies! As you can see from the last message, we are still experiencing a few glitches with our new mailing last. I inadvertently sent out a 3-year-old message. The correct message below lists JAIR articles recently published in Volume 18. - Steven Minton JAIR Managing Editor CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) Thompson, C.A and Mooney, R.J. (2003) "Acquiring Word-Meaning Mappings for Natural Language Interfaces", For quick access go to Cemgil, A.T. and Kappen, B. (2003) "Monte Carlo Methods for Tempo Tracking and Rhythm Quantization", For quick access go to Brumberg, O., Livne, S. and Markovitch, S. (2003) "Learning to Order BDD Variables in Verification", For quick access go to Peral, J. and Ferrandez, A. (2003) "Translation of Pronominal Anaphora between English and Spanish: Discrepancies and Evaluation", For quick access go to Lerman, K., Minton, S.N. and Knoblock, C.A. (2003) "Wrapper Maintenance: A Machine Learning Approach", Volume 18, pages 149-181. For quick access go to Tan, K.C., Khor, E.F., Lee, T.H. and Sathikannan, R. (2003) "An Evolutionary Algorithm with Advanced Goal and Priority Specification for Multi-objective Optimization", Volume 18, pages 183-215. For quick access go to ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jairmail@ISI.EDU Tue Apr 1 09:23:31 2003 Received: from nitro.isi.edu (nitro.isi.edu [128.9.208.207]) by gamma.isi.edu (8.11.6p2/8.11.2) with ESMTP id h31HNVk10407 for ; Tue, 1 Apr 2003 09:23:31 -0800 (PST) Received: (from jairmail@localhost) by nitro.isi.edu (8.11.6p2/8.11.2) id h31HNU311650; Tue, 1 Apr 2003 09:23:30 -0800 (PST) Date: Tue, 1 Apr 2003 09:23:30 -0800 (PST) Message-Id: <200304011723.h31HNU311650@nitro.isi.edu> From: JAIRMAIL To: jairsubscribers@ISI.EDU Subject: [Jairsubscribers] Announcement: JMLG Sender: jairsubscribers-admin@mailman.isi.edu Errors-To: jairsubscribers-admin@mailman.isi.edu X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.0.5 Precedence: bulk Reply-To: jair-ed@isi.edu List-Help: List-Archive: JAIR Readers: The announcement below was passed to us by Michael Littman (mlittman@cs.rutgers.edu). JAIR is not responsible for any of the content. Thanks! -Ed. .................................................. To the AI and ML community: We are pleased to announce the first volume of a new online journal, the Journal of Machine Learning Gossip. The volume includes the following award-winning papers: Markov Indecision Processes: A Formal Model of Decision-Making Under Extreme Confusion by Harry Q. Bovik, Judy Q. Goldsmith, Andrew Q. Klapper, and Michael Q. Littman Data Set Selection by Doudou LaLoudouana and Mambobo Bonouliqui Tarare On the Origin and Destiny of Inductive Machine Learning by Terran Lane Visit our web site http://www.jmlg.org/papers.htm for access to these papers and for more information about the journal and its goals. We look forward to serving you in the coming years. Sincerely, Cycle L. Bittmap, PhD on behalf of the editors of the JMLG From jairmail@ISI.EDU Wed Apr 30 17:46:03 2003 Received: from nitro.isi.edu (nitro.isi.edu [128.9.208.207]) by gamma.isi.edu (8.11.6p2/8.11.2) with ESMTP id h410k2019769 for ; Wed, 30 Apr 2003 17:46:02 -0700 (PDT) Received: (from jairmail@localhost) by nitro.isi.edu (8.11.6p2/8.11.2) id h410k2u07498; Wed, 30 Apr 2003 17:46:02 -0700 (PDT) Date: Wed, 30 Apr 2003 17:46:02 -0700 (PDT) Message-Id: <200305010046.h410k2u07498@nitro.isi.edu> From: JAIRMAIL To: jairsubscribers@ISI.EDU Subject: [Jairsubscribers] JAIR News Sender: jairsubscribers-admin@mailman.isi.edu Errors-To: jairsubscribers-admin@mailman.isi.edu X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.0.5 Precedence: bulk Reply-To: jair-ed@isi.edu List-Help: List-Archive: CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) Wilkins, D.E., Lee, T.J. and Berry, P. (2003) "Interactive Execution Monitoring of Agent Teams" Poole, D. and Zhang, N.L. (2003) "Exploiting Contextual Independence In Probabilistic Inference" Brafman, R.I. and Domshlak, C. (2003) "Structure and Complexity in Planning with Unary Operators" ---------------------------------------------------------------- I. New JAIR Articles Wilkins, D.E., Lee, T.J. and Berry, P. (2003) "Interactive Execution Monitoring of Agent Teams", Volume 18, pages 217-261. For quick access go to Abstract: There is an increasing need for automated support for humans monitoring the activity of distributed teams of cooperating agents, both human and machine. We characterize the domain-independent challenges posed by this problem, and describe how properties of domains influence the challenges and their solutions. We will concentrate on dynamic, data-rich domains where humans are ultimately responsible for team behavior. Thus, the automated aid should interactively support effective and timely decision making by the human. We present a domain-independent categorization of the types of alerts a plan-based monitoring system might issue to a user, where each type generally requires different monitoring techniques. We describe a monitoring framework for integrating many domain-specific and task-specific monitoring techniques and then using the concept of value of an alert to avoid operator overload. We use this framework to describe an execution monitoring approach we have used to implement Execution Assistants (EAs) in two different dynamic, data-rich, real-world domains to assist a human in monitoring team behavior. One domain (Army small unit operations) has hundreds of mobile, geographically distributed agents, a combination of humans, robots, and vehicles. The other domain (teams of unmanned ground and air vehicles) has a handful of cooperating robots. Both domains involve unpredictable adversaries in the vicinity. Our approach customizes monitoring behavior for each specific task, plan, and situation, as well as for user preferences. Our EAs alert the human controller when reported events threaten plan execution or physically threaten team members. Alerts were generated in a timely manner without inundating the user with too many alerts (less than 10 percent of alerts are unwanted, as judged by domain experts). Poole, D. and Zhang, N.L. (2003) "Exploiting Contextual Independence In Probabilistic Inference", Volume 18, pages 263-313. For quick access go to Abstract: Bayesian belief networks have grown to prominence because they provide compact representations for many problems for which probabilistic inference is appropriate, and there are algorithms to exploit this compactness. The next step is to allow compact representations of the conditional probabilities of a variable given its parents. In this paper we present such a representation that exploits contextual independence in terms of parent contexts; which variables act as parents may depend on the value of other variables. The internal representation is in terms of contextual factors (confactors) that is simply a pair of a context and a table. The algorithm, contextual variable elimination, is based on the standard variable elimination algorithm that eliminates the non-query variables in turn, but when eliminating a variable, the tables that need to be multiplied can depend on the context. This algorithm reduces to standard variable elimination when there is no contextual independence structure to exploit. We show how this can be much more efficient than variable elimination when there is structure to exploit. We explain why this new method can exploit more structure than previous methods for structured belief network inference and an analogous algorithm that uses trees. Brafman, R.I. and Domshlak, C. (2003) "Structure and Complexity in Planning with Unary Operators", Volume 18, pages 315-349. For quick access go to Abstract: Unary operator domains -- i.e., domains in which operators have a single effect -- arise naturally in many control problems. In its most general form, the problem of STRIPS planning in unary operator domains is known to be as hard as the general STRIPS planning problem -- both are PSPACE-complete. However, unary operator domains induce a natural structure, called the domain's causal graph. This graph relates between the preconditions and effect of each domain operator. Causal graphs were exploited by Williams and Nayak in order to analyze plan generation for one of the controllers in NASA's Deep-Space One spacecraft. There, they utilized the fact that when this graph is acyclic, a serialization ordering over any subgoal can be obtained quickly. In this paper we conduct a comprehensive study of the relationship between the structure of a domain's causal graph and the complexity of planning in this domain. On the positive side, we show that a non-trivial polynomial time plan generation algorithm exists for domains whose causal graph induces a polytree with a constant bound on its node indegree. On the negative side, we show that even plan existence is hard when the graph is a directed-path singly connected DAG. More generally, we show that the number of paths in the causal graph is closely related to the complexity of planning in the associated domain. Finally we relate our results to the question of complexity of planning with serializable subgoals. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jairmail@ISI.EDU Tue Jul 1 16:53:37 2003 Received: from nitro.isi.edu (nitro.isi.edu [128.9.208.207]) by gamma.isi.edu (8.11.6p2/8.11.2) with ESMTP id h61NrbL08882 for ; Tue, 1 Jul 2003 16:53:37 -0700 (PDT) Received: (from jairmail@localhost) by nitro.isi.edu (8.11.6p2/8.11.2) id h61NraF26381; Tue, 1 Jul 2003 16:53:36 -0700 (PDT) Date: Tue, 1 Jul 2003 16:53:36 -0700 (PDT) Message-Id: <200307012353.h61NraF26381@nitro.isi.edu> From: JAIRMAIL To: jairsubscribers@ISI.EDU Subject: [Jairsubscribers] JAIR update Sender: jairsubscribers-admin@mailman.isi.edu Errors-To: jairsubscribers-admin@mailman.isi.edu X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.0.5 Precedence: bulk Reply-To: jair-ed@isi.edu List-Help: List-Archive: CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) Patel-Schneider, P.F. and Sebastiani, R. (2003) "A New General Method to Generate Random Modal Formulae for Testing Decision Procedures" Lang, J., Liberatore, P. and Marquis, P. (2003) "Propositional Independence - Formula-Variable Independence and Forgetting" Acid, S. and de Campos. L.M. (2003) "Searching for Bayesian Network Structures in the Space of Restricted Acyclic Partially Directed Graphs" Reiter, E., Sripada, S.G., and Robertson, R. (2003) "Acquiring Correct Knowledge for Natural Language Generation" ---------------------------------------------------------------- I. New JAIR Articles Patel-Schneider, P.F. and Sebastiani, R. (2003) "A New General Method to Generate Random Modal Formulae for Testing Decision Procedures", Volume 18, pages 351-389. Available in PDF, PostScript and compressed PostScript. For quick access go to Abstract: The recent emergence of heavily-optimized modal decision procedures has highlighted the key role of empirical testing in this domain. Unfortunately, the introduction of extensive empirical tests for modal logics is recent, and so far none of the proposed test generators is very satisfactory. To cope with this fact, we present a new random generation method that provides benefits over previous methods for generating empirical tests. It fixes and much generalizes one of the best-known methods, the random CNF_[]m test, allowing for generating a much wider variety of problems, covering in principle the whole input space. Our new method produces much more suitable test sets for the current generation of modal decision procedures. We analyze the features of the new method by means of an extensive collection of empirical tests. Lang, J., Liberatore, P. and Marquis, P. (2003) "Propositional Independence - Formula-Variable Independence and Forgetting", Volume 18, pages 391-443. Available in PDF, PostScript and compressed PostScript. For quick access go to Abstract: Independence -- the study of what is relevant to a given problem of reasoning -- has received an increasing attention from the AI community. In this paper, we consider two basic forms of independence, namely, a syntactic one and a semantic one. We show features and drawbacks of them. In particular, while the syntactic form of independence is computationally easy to check, there are cases in which things that intuitively are not relevant are not recognized as such. We also consider the problem of forgetting, i.e., distilling from a knowledge base only the part that is relevant to the set of queries constructed from a subset of the alphabet. While such process is computationally hard, it allows for a simplification of subsequent reasoning, and can thus be viewed as a form of compilation: once the relevant part of a knowledge base has been extracted, all reasoning tasks to be performed can be simplified. Acid, S. and de Campos. L.M. (2003) "Searching for Bayesian Network Structures in the Space of Restricted Acyclic Partially Directed Graphs", Volume 18, pages 445-490. Available in HTML, PDF, PostScript and compressed PostScript. For quick access go to Abstract: Although many algorithms have been designed to construct Bayesian network structures using different approaches and principles, they all employ only two methods: those based on independence criteria, and those based on a scoring function and a search procedure (although some methods combine the two). Within the score+search paradigm, the dominant approach uses local search methods in the space of directed acyclic graphs (DAGs), where the usual choices for defining the elementary modifications (local changes) that can be applied are arc addition, arc deletion, and arc reversal. In this paper, we propose a new local search method that uses a different search space, and which takes account of the concept of equivalence between network structures: restricted acyclic partially directed graphs (RPDAGs). In this way, the number of different configurations of the search space is reduced, thus improving efficiency. Moreover, although the final result must necessarily be a local optimum given the nature of the search method, the topology of the new search space, which avoids making early decisions about the directions of the arcs, may help to find better local optima than those obtained by searching in the DAG space. Detailed results of the evaluation of the proposed search method on several test problems, including the well-known Alarm Monitoring System, are also presented. Reiter, E., Sripada, S.G., and Robertson, R. (2003) "Acquiring Correct Knowledge for Natural Language Generation", Volume 18, pages 491-516. Available in HTML, PDF, PostScript and compressed PostScript. For quick access go to Abstract: Natural language generation (NLG) systems are computer software systems that produce texts in English and other human languages, often from non-linguistic input data. NLG systems, like most AI systems, need substantial amounts of knowledge. However, our experience in two NLG projects suggests that it is difficult to acquire correct knowledge for NLG systems; indeed, every knowledge acquisition (KA) technique we tried had significant problems. In general terms, these problems were due to the complexity, novelty, and poorly understood nature of the tasks our systems attempted, and were worsened by the fact that people write so differently. This meant in particular that corpus-based KA approaches suffered because it was impossible to assemble a sizable corpus of high-quality consistent manually written texts in our domains; and structured expert-oriented KA techniques suffered because experts disagreed and because we could not get enough information about special and unusual cases to build robust systems. We believe that such problems are likely to affect many other NLG systems as well. In the long term, we hope that new KA techniques may emerge to help NLG system builders. In the shorter term, we believe that understanding how individual KA techniques can fail, and using a mixture of different KA techniques with different strengths and weaknesses, can help developers acquire NLG knowledge that is mostly correct. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jairmail@ISI.EDU Tue Oct 7 15:02:18 2003 Received: from nitro.isi.edu (nitro.isi.edu [128.9.208.207]) by gamma.isi.edu (8.11.6p2+0917/8.11.2) with ESMTP id h97M2IO11408 for ; Tue, 7 Oct 2003 15:02:18 -0700 (PDT) Received: (from jairmail@localhost) by nitro.isi.edu (8.11.6p2+0917/8.11.2) id h97M2I218182; Tue, 7 Oct 2003 15:02:18 -0700 (PDT) Date: Tue, 7 Oct 2003 15:02:18 -0700 (PDT) Message-Id: <200310072202.h97M2I218182@nitro.isi.edu> From: JAIRMAIL To: jairsubscribers@ISI.EDU Subject: [Jairsubscribers] JAIR update Sender: jairsubscribers-admin@mailman.isi.edu Errors-To: jairsubscribers-admin@mailman.isi.edu X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.0.5 Precedence: bulk Reply-To: jair-ed@isi.edu List-Help: List-Archive: CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) Zanuttini, B. (2003) "New Polynomial Classes for Logic-Based Abduction" Brafman, R.I. and Tennenholtz, M. (2003) "Learning to Coordinate Efficiently: A Model-based Approach" Eiter, T., Faber, W., Leone, N., Pfeifer, G. and Polleres, A. (2003) "Answer Set Planning Under Action Costs" Finkelstein, L., Markovitch, S. and Rivlin, E. (2003) "Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources" Leisink, M. and Kappen, B. (2003) "Bound Propagation" Maynard-Zhang, P. and Lehmann, D. (2003) "Representing and Aggregating Conflicting Beliefs" Wiewiora, E. (2003) "Potential-Based Shaping and Q-Value Initialization are Equivalent" Stone, P., Schapire, R.E., Littman, M.L., Csirik, J.A. and McAllester, D.(2003) "Decision-Theoretic Bidding Based on Learned Density Models in Simultaneous, Interacting Auctions" ---------------------------------------------------------------- I. New JAIR Articles Zanuttini, B. (2003) "New Polynomial Classes for Logic-Based Abduction", Volume 19, pages 1-10. Available in HTML, PDF, PostScript and compressed PostScript. An online appendix (Technical report with proofs and examples) is also a available. For quick access go to Abstract: We address the problem of propositional logic-based abduction, i.e., the problem of searching for a best explanation for a given propositional observation according to a given propositional knowledge base. We give a general algorithm, based on the notion of projection; then we study restrictions over the representations of the knowledge base and of the query, and find new polynomial classes of abduction problems. Brafman, R.I. and Tennenholtz, M. (2003) "Learning to Coordinate Efficiently: A Model-based Approach", Volume 19, pages 11-23. For quick access go to Abstract: In common-interest stochastic games all players receive an identical payoff. Players participating in such games must learn to coordinate with each other in order to receive the highest-possible value. A number of reinforcement learning algorithms have been proposed for this problem, and some have been shown to converge to good solutions in the limit. In this paper we show that using very simple model-based algorithms, much better (i.e., polynomial) convergence rates can be attained. Moreover, our model-based algorithms are guaranteed to converge to the optimal value, unlike many of the existing algorithms. Eiter, T., Faber, W., Leone, N., Pfeifer, G. and Polleres, A. (2003) "Answer Set Planning Under Action Costs", Volume 19, pages 25-71. For quick access go to Abstract: Recently, planning based on answer set programming has been proposed as an approach towards realizing declarative planning systems. In this paper, we present the language Kc, which extends the declarative planning language K by action costs. Kc provides the notion of admissible and optimal plans, which are plans whose overall action costs are within a given limit resp. minimum over all plans (i.e., cheapest plans). As we demonstrate, this novel language allows for expressing some nontrivial planning tasks in a declarative way. Furthermore, it can be utilized for representing planning problems under other optimality criteria, such as computing ``shortest'' plans (with the least number of steps), and refinement combinations of cheapest and fastest plans. We study complexity aspects of the language Kc and provide a transformation to logic programs, such that planning problems are solved via answer set programming. Furthermore, we report experimental results on selected problems. Our experience is encouraging that answer set planning may be a valuable approach to expressive planning systems in which intricate planning problems can be naturally specified and solved. Finkelstein, L., Markovitch, S. and Rivlin, E. (2003) "Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources", Volume 19, pages 73-138. For quick access go to Abstract: The performance of anytime algorithms can be improved by simultaneously solving several instances of algorithm-problem pairs. These pairs may include different instances of a problem (such as starting from a different initial state), different algorithms (if several alternatives exist), or several runs of the same algorithm (for non-deterministic algorithms). In this paper we present a methodology for designing an optimal scheduling policy based on the statistical characteristics of the algorithms involved. We formally analyze the case where the processes share resources (a single-processor model), and provide an algorithm for optimal scheduling. We analyze, theoretically and empirically, the behavior of our scheduling algorithm for various distribution types. Finally, we present empirical results of applying our scheduling algorithm to the Latin Square problem. Leisink, M. and Kappen, B. (2003) "Bound Propagation", Volume 19, pages 139-154. For quick access go to Abstract: In this article we present an algorithm to compute bounds on the marginals of a graphical model. For several small clusters of nodes upper and lower bounds on the marginal values are computed independently of the rest of the network. The range of allowed probability distributions over the surrounding nodes is restricted using earlier computed bounds. As we will show, this can be considered as a set of constraints in a linear programming problem of which the objective function is the marginal probability of the center nodes. In this way knowledge about the maginals of neighbouring clusters is passed to other clusters thereby tightening the bounds on their marginals. We show that sharp bounds can be obtained for undirected and directed graphs that are used for practical applications, but for which exact computations are infeasible. Maynard-Zhang, P. and Lehmann, D. (2003) "Representing and Aggregating Conflicting Beliefs", Volume 19, pages 155-203. For quick access go to Abstract: We consider the two-fold problem of representing collective beliefs and aggregating these beliefs. We propose a novel representation for collective beliefs that uses modular, transitive relations over possible worlds. They allow us to represent conflicting opinions and they have a clear semantics, thus improving upon the quasi-transitive relations often used in social choice. We then describe a way to construct the belief state of an agent informed by a set of sources of varying degrees of reliability. This construction circumvents Arrow's Impossibility Theorem in a satisfactory manner by accounting for the explicitly encoded conflicts. We give a simple set-theory-based operator for combining the information of multiple agents. We show that this operator satisfies the desirable invariants of idempotence, commutativity, and associativity, and, thus, is well-behaved when iterated, and we describe a computationally effective way of computing the resulting belief state. Finally, we extend our framework to incorporate voting. Wiewiora, E. (2003) "Potential-Based Shaping and Q-Value Initialization are Equivalent", Volume 19, pages 205-208. For quick access go to Abstract: Shaping has proven to be a powerful but precarious means of improving reinforcement learning performance. Ng, Harada, and Russell (1999) proposed the potential-based shaping algorithm for adding shaping rewards in a way that guarantees the learner will learn optimal behavior. In this note, we prove certain similarities between this shaping algorithm and the initialization step required for several reinforcement learning algorithms. More specifically, we prove that a reinforcement learner with initial Q-values based on the shaping algorithm's potential function make the same updates throughout learning as a learner receiving potential-based shaping rewards. We further prove that under a broad category of policies, the behavior of these two learners are indistinguishable. The comparison provides intuition on the theoretical properties of the shaping algorithm as well as a suggestion for a simpler method for capturing the algorithm's benefit. In addition, the equivalence raises previously unaddressed issues concerning the efficiency of learning with potential-based shaping. Stone, P., Schapire, R.E., Littman, M.L., Csirik, J.A. and McAllester, D.(2003) "Decision-Theoretic Bidding Based on Learned Density Models in Simultaneous, Interacting Auctions", Volume 19, pages 209-242. For quick access go to Abstract: Auctions are becoming an increasingly popular method for transacting business, especially over the Internet. This article presents a general approach to building autonomous bidding agents to bid in multiple simultaneous auctions for interacting goods. A core component of our approach learns a model of the empirical price dynamics based on past data and uses the model to analytically calculate, to the greatest extent possible, optimal bids. We introduce a new and general boosting-based algorithm for conditional density estimation problems of this kind, i.e., supervised learning problems in which the goal is to estimate the entire conditional distribution of the real-valued label. This approach is fully implemented as ATTac-2001, a top-scoring agent in the second Trading Agent Competition (TAC-01). We present experiments demonstrating the effectiveness of our boosting-based price predictor relative to several reasonable alternatives. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jairmail@ISI.EDU Wed Dec 31 01:00:27 2003 Received: from nitro.isi.edu (nitro.isi.edu [128.9.208.207]) by gamma.isi.edu (8.11.6p2+0917/8.11.2) with ESMTP id hBV90Rm19013 for ; Wed, 31 Dec 2003 01:00:27 -0800 (PST) Received: (from jairmail@localhost) by nitro.isi.edu (8.11.6p2+0917/8.11.2) id hBV90RT08306; Wed, 31 Dec 2003 01:00:27 -0800 (PST) Date: Wed, 31 Dec 2003 01:00:27 -0800 (PST) Message-Id: <200312310900.hBV90RT08306@nitro.isi.edu> From: JAIRMAIL To: jairsubscribers@mailman.isi.edu Subject: [Jairsubscribers] JAIR Update Sender: jairsubscribers-admin@mailman.isi.edu Errors-To: jairsubscribers-admin@mailman.isi.edu X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.0.5 Precedence: bulk Reply-To: jair-ed@isi.edu List-Help: List-Archive: CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) Grunwald, P.D. and Halpern, J.Y. "Updating Probabilities" Lin, F. "Compiling Causal Theories to Successor State Axioms and STRIPS-Like Systems" Weiss, G.M. and Provost, F. "Learning When Training Data are Costly: The Effect of Class Distribution on Tree Induction" Wray, R.E. and Laird, J.E. "An Architectural Approach to Ensuring Consistency in Hierarchical Execution" Guestrin, C., Koller, D., Parr, R. and Venkataraman, S. "Efficient Solution Algorithms for Factored MDPs" Console, L., Picardi, C. and Theseider Dupre, D. "Temporal Decision Trees: Model-based Diagnosis of Dynamic Systems On-Board" Walsh, W.E. and Wellman, M.P. "Decentralized Supply Chain Formation: A Market Protocol and Competitive Equilibrium Analysis" Price, B. and Boutilier, C. "Accelerating Reinforcement Learning through Implicit Imitation" Sanchez, R. and Kambhampati, S. "AltAltp: Online Parallelization of Plans with Heuristic State Search" ---------------------------------------------------------------- I. New JAIR Articles Grunwald, P.D. and Halpern, J.Y. (2003) "Updating Probabilities", Volume 19, pages 243-278. For quick access go to Abstract: As examples such as the Monty Hall puzzle show, applying conditioning to update a probability distribution on a ``naive space'', which does not take into account the protocol used, can often lead to counterintuitive results. Here we examine why. A criterion known as CAR (``coarsening at random'') in the statistical literature characterizes when ``naive'' conditioning in a naive space works. We show that the CAR condition holds rather infrequently, and we provide a procedural characterization of it, by giving a randomized algorithm that generates all and only distributions for which CAR holds. This substantially extends previous characterizations of CAR. We also consider more generalized notions of update such as Jeffrey conditioning and minimizing relative entropy (MRE). We give a generalization of the CAR condition that characterizes when Jeffrey conditioning leads to appropriate answers, and show that there exist some very simple settings in which MRE essentially never gives the right results. This generalizes and interconnects previous results obtained in the literature on CAR and MRE. Lin, F. (2003) "Compiling Causal Theories to Successor State Axioms and STRIPS-Like Systems", Volume 19, pages 279-314. An online appendix (Benchmark action domain descriptions) is also a available. For quick access go to Abstract: We describe a system for specifying the effects of actions. Unlike those commonly used in AI planning, our system uses an action description language that allows one to specify the effects of actions using domain rules, which are state constraints that can entail new action effects from old ones. Declaratively, an action domain in our language corresponds to a nonmonotonic causal theory in the situation calculus. Procedurally, such an action domain is compiled into a set of logical theories, one for each action in the domain, from which fully instantiated successor state-like axioms and STRIPS-like systems are then generated. We expect the system to be a useful tool for knowledge engineers writing action specifications for classical AI planning systems, GOLOG systems, and other systems where formal specifications of actions are needed. Weiss, G.M. and Provost, F. (2003) "Learning When Training Data are Costly: The Effect of Class Distribution on Tree Induction", Volume 19, pages 315-354. For quick access go to Abstract: For large, real-world inductive learning problems, the number of training examples often must be limited due to the costs associated with procuring, preparing, and storing the training examples and/or the computational costs associated with learning from them. In such circumstances, one question of practical importance is: if only n training examples can be selected, in what proportion should the classes be represented? In this article we help to answer this question by analyzing, for a fixed training-set size, the relationship between the class distribution of the training data and the performance of classification trees induced from these data. We study twenty-six data sets and, for each, determine the best class distribution for learning. The naturally occurring class distribution is shown to generally perform well when classifier performance is evaluated using undifferentiated error rate (0/1 loss). However, when the area under the ROC curve is used to evaluate classifier performance, a balanced distribution is shown to perform well. Since neither of these choices for class distribution always generates the best-performing classifier, we introduce a budget-sensitive progressive sampling algorithm for selecting training examples based on the class associated with each example. An empirical analysis of this algorithm shows that the class distribution of the resulting training set yields classifiers with good (nearly-optimal) classification performance. Wray, R.E. and Laird, J.E. (2003) "An Architectural Approach to Ensuring Consistency in Hierarchical Execution", Volume 19, pages 355-398. For quick access go to Abstract: Hierarchical task decomposition is a method used in many agent systems to organize agent knowledge. This work shows how the combination of a hierarchy and persistent assertions of knowledge can lead to difficulty in maintaining logical consistency in asserted knowledge. We explore the problematic consequences of persistent assumptions in the reasoning process and introduce novel potential solutions. Having implemented one of the possible solutions, Dynamic Hierarchical Justification, its effectiveness is demonstrated with an empirical analysis. Guestrin, C., Koller, D., Parr, R. and Venkataraman, S. (2003) "Efficient Solution Algorithms for Factored MDPs", Volume 19, pages 399-468. For quick access go to Abstract: This paper addresses the problem of planning under uncertainty in large Markov Decision Processes (MDPs). Factored MDPs represent a complex state space using state variables and the transition model using a dynamic Bayesian network. This representation often allows an exponential reduction in the representation size of structured MDPs, but the complexity of exact solution algorithms for such MDPs can grow exponentially in the representation size. In this paper, we present two approximate solution algorithms that exploit structure in factored MDPs. Both use an approximate value function represented as a linear combination of basis functions, where each basis function involves only a small subset of the domain variables. A key contribution of this paper is that it shows how the basic operations of both algorithms can be performed efficiently in closed form, by exploiting both additive and context-specific structure in a factored MDP. A central element of our algorithms is a novel linear program decomposition technique, analogous to variable elimination in Bayesian networks, which reduces an exponentially large LP to a provably equivalent, polynomial-sized one. One algorithm uses approximate linear programming, and the second approximate dynamic programming. Our dynamic programming algorithm is novel in that it uses an approximation based on max-norm, a technique that more directly minimizes the terms that appear in error bounds for approximate MDP algorithms. We provide experimental results on problems with over 10^40 states, demonstrating a promising indication of the scalability of our approach, and compare our algorithm to an existing state-of-the-art approach, showing, in some problems, exponential gains in computation time. Console, L., Picardi, C. and Theseider Dupré, D. (2003) "Temporal Decision Trees: Model-based Diagnosis of Dynamic Systems On-Board", Volume 19, pages 469-512. For quick access go to Abstract: The automatic generation of decision trees based on off-line reasoning on models of a domain is a reasonable compromise between the advantages of using a model-based approach in technical domains and the constraints imposed by embedded applications. In this paper we extend the approach to deal with temporal information. We introduce a notion of temporal decision tree, which is designed to make use of relevant information as long as it is acquired, and we present an algorithm for compiling such trees from a model-based reasoning system. Walsh, W.E. and Wellman, M.P. (2003) "Decentralized Supply Chain Formation: A Market Protocol and Competitive Equilibrium Analysis", Volume 19, pages 513-567. For quick access go to Abstract: Supply chain formation is the process of determining the structure and terms of exchange relationships to enable a multilevel, multiagent production activity. We present a simple model of supply chains, highlighting two characteristic features: hierarchical subtask decomposition, and resource contention. To decentralize the formation process, we introduce a market price system over the resources produced along the chain. In a competitive equilibrium for this system, agents choose locally optimal allocations with respect to prices, and outcomes are optimal overall. To determine prices, we define a market protocol based on distributed, progressive auctions, and myopic, non-strategic agent bidding policies. In the presence of resource contention, this protocol produces better solutions than the greedy protocols common in the artificial intelligence and multiagent systems literature. The protocol often converges to high-value supply chains, and when competitive equilibria exist, typically to approximate competitive equilibria. However, complementarities in agent production technologies can cause the protocol to wastefully allocate inputs to agents that do not produce their outputs. A subsequent decommitment phase recovers a significant fraction of the lost surplus. Price, B. and Boutilier, C. (2003) "Accelerating Reinforcement Learning through Implicit Imitation", Volume 19, pages 569-629. For quick access go to Abstract: Imitation can be viewed as a means of enhancing learning in multiagent environments. It augments an agent's ability to learn useful behaviors by making intelligent use of the knowledge implicit in behaviors demonstrated by cooperative teachers or other more experienced agents. We propose and study a formal model of implicit imitation that can accelerate reinforcement learning dramatically in certain cases. Roughly, by observing a mentor, a reinforcement-learning agent can extract information about its own capabilities in, and the relative value of, unvisited parts of the state space. We study two specific instantiations of this model, one in which the learning agent and the mentor have identical abilities, and one designed to deal with agents and mentors with different action sets. We illustrate the benefits of implicit imitation by integrating it with prioritized sweeping, and demonstrating improved performance and convergence through observation of single and multiple mentors. Though we make some stringent assumptions regarding observability and possible interactions, we briefly comment on extensions of the model that relax these restricitions. Sanchez, R. and Kambhampati, S. (2003) "AltAltp: Online Parallelization of Plans with Heuristic State Search", Volume 19, pages 631-657. For quick access go to Abstract: Despite their near dominance, heuristic state search planners still lag behind disjunctive planners in the generation of parallel plans in classical planning. The reason is that directly searching for parallel solutions in state space planners would require the planners to branch on all possible subsets of parallel actions, thus increasing the branching factor exponentially. We present a variant of our heuristic state search planner AltAlt, called AltAltp which generates parallel plans by using greedy online parallelization of partial plans. The greedy approach is significantly informed by the use of novel distance heuristics that AltAltp derives from a graphplan-style planning graph for the problem. While this approach is not guaranteed to provide optimal parallel plans, empirical results show that AltAltp is capable of generating good quality parallel plans at a fraction of the cost incurred by the disjunctive planners. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jairmail@ISI.EDU Fri Jan 23 18:03:07 2004 Received: from nitro.isi.edu (nitro.isi.edu [128.9.208.207]) by gamma.isi.edu (8.11.6p2+0917/8.11.2) with ESMTP id i0O237k20661 for ; Fri, 23 Jan 2004 18:03:07 -0800 (PST) Received: (from jairmail@localhost) by nitro.isi.edu (8.11.6p2+0917/8.11.2) id i0O237d07374; Fri, 23 Jan 2004 18:03:07 -0800 (PST) Date: Fri, 23 Jan 2004 18:03:07 -0800 (PST) Message-Id: <200401240203.i0O237d07374@nitro.isi.edu> From: JAIRMAIL To: jairsubscribers@mailman.isi.edu Subject: [Jairsubscribers] JAIR Update (Special Issue) X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.4 Precedence: list Reply-To: jair-ed@isi.edu List-Id: jairsubscribers.mailman.isi.edu List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 24 Jan 2004 02:03:08 -0000 CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR (Volume 21: The JAIR Special Issue on the 3rd International Planning Competition) and describes how to access them. If you wish to remove yourself from this mailing list, see section II. Long, D. and Fox, M. "The 3rd International Planning Competition: Results and Analysis" Fox, M. and Long, D. "PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains" Bacchus, F. "The Power of Modeling---a Response to PDDL2.1" Boddy, M.S. "Imperfect Match: PDDL 2.1 and Real Applications" Geffner, H.A. "PDDL 2.1: Representation vs. Computation" McDermott, D. "PDDL2.1 -- The Art of the Possible? Commentary on Fox and Long" Smith, D.E. "The Case for Durative Actions: A Commentary on PDDL2.1" Do, M. and Kambhampati, S. "SAPA: A Multi-objective Metric Temporal Planner" Edelkamp, S. "Taming Numbers and Durations in the Model Checking Integrated Planning System" Gerevini, A., Saetti, A. and Serina, I. "Planning Through Stochastic Local Search and Temporal Action Graphs in LPG" Hoffmann, J. "The Metric-FF Planning System: Translating ``Ignoring Delete Lists'' to Numeric State Variables" Kvarnström, J. and Magnusson, M. "TALplanner in IPC-2002: Extensions and Control Rules" Nau, D.S., Au, T.C., Ilghami, O., Kuter, U., Murdock, J.W., Wu, D. and Yaman, F "SHOP2: An HTN Planning System" Younes, H.L.S. and Simmons, R.G. "VHPOP: Versatile Heuristic Partial Order Planner" ---------------------------------------------------------------- I. New JAIR Articles Long, D. and Fox, M. (2003) "The 3rd International Planning Competition: Results and Analysis", Volume 20, pages 1-59. For quick access go to Abstract: This paper reports the outcome of the third in the series of biennial international planning competitions, held in association with the International Conference on AI Planning and Scheduling (AIPS) in 2002. In addition to describing the domains, the planners and the objectives of the competition, the paper includes analysis of the results. The results are analysed from several perspectives, in order to address the questions of comparative performance between planners, comparative difficulty of domains, the degree of agreement between planners about the relative difficulty of individual problem instances and the question of how well planners scale relative to one another over increasingly difficult problems. The paper addresses these questions through statistical analysis of the raw results of the competition, in order to determine which results can be considered to be adequately supported by the data. The paper concludes with a discussion of some challenges for the future of the competition series. Fox, M. and Long, D. (2003) "PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains", Volume 20, pages 61-124. For quick access go to Abstract: In recent years research in the planning community has moved increasingly toward s application of planners to realistic problems involving both time and many typ es of resources. For example, interest in planning demonstrated by the space res earch community has inspired work in observation scheduling, planetary rover ex ploration and spacecraft control domains. Other temporal and resource-intensive domains including logistics planning, plant control and manufacturing have also helped to focus the community on the modelling and reasoning issues that must be confronted to make planning technology meet the challenges of application. The International Planning Competitions have acted as an important motivating fo rce behind the progress that has been made in planning since 1998. The third com petition (held in 2002) set the planning community the challenge of handling tim e and numeric resources. This necessitated the development of a modelling langua ge capable of expressing temporal and numeric properties of planning domains. In this paper we describe the language, PDDL2.1, that was used in the competition. We describe the syntax of the language, its formal semantics and the validation of concurrent plans. We observe that PDDL2.1 has considerable modelling power --- exceeding the capabilities of current planning technology --- and presents a number of important challenges to the research community. Bacchus, F. (2003) "The Power of Modeling---a Response to PDDL2.1", Volume 20, pages 125-132. For quick access go to Abstract: In this commentary I argue that although PDDL is a very useful standard for the planning competition, its design does not properly consider the issue of domain modeling. Hence, I would not advocate its use in specifying planning domains outside of the context of the planning competition. Rather, the field needs to explore different approaches and grapple more directly with the problem of effectively modeling and utilizing all of the diverse pieces of knowledge we typically have about planning domains. Boddy, M.S. (2003) "Imperfect Match: PDDL 2.1 and Real Applications", Volume 20, pages 133-137. For quick access go to Abstract: PDDL was originally conceived and constructed as a lingua franca for the International Planning Competition. PDDL2.1 embodies a set of extensions intended to support the expression of something closer to ``real planning problems.'' This objective has only been partially achieved, due in large part to a deliberate focus on not moving too far from classical planning models and solution methods. Geffner, H.A. (2003) "PDDL 2.1: Representation vs. Computation", Volume 20, pages 139-144. For quick access go to Abstract: I comment on the PDDL 2.1 language and its use in the planning competition, focusing on the choices made for accommodating time and concurrency. I also discuss some methodological issues that have to do with the move toward more expressive planning languages and the balance needed in planning research between semantics and computation. McDermott, D. (2003) "PDDL2.1 -- The Art of the Possible? Commentary on Fox and Long", Volume 20, pages 145-148. For quick access go to Abstract: PDDL2.1 was designed to push the envelope of what planning algorithms can do, and it has succeeded. It adds two important features: durative actions,which take time (and may have continuous effects); and objective functions for measuring the quality of plans. The concept of durative actions is flawed; and the treatment of their semantics reveals too strong an attachment to the way many contemporary planners work. Future PDDL innovators should focus on producing a clean semantics for additions to the language, and let planner implementers worry about coupling their algorithms to problems expressed in the latest version of the language. Smith, D.E. (2003) "The Case for Durative Actions: A Commentary on PDDL2.1", Volume 20, pages 149-154. For quick access go to Abstract: The addition of durative actions to PDDL2.1 sparked some controversy. Fox and Long argued that actions should be considered as instantaneous, but can start and stop processes. Ultimately, a limited notion of durative actions was incorporated into the language. I argue that this notion is still impoverished, and that the underlying philosophical position of regarding durative actions as being a shorthand for a start action, process, and stop action ignores the realities of modelling and execution for complex systems. Do, M. and Kambhampati, S. (2003) "SAPA: A Multi-objective Metric Temporal Planner", Volume 20, pages 155-194. For quick access go to Abstract: SAPA is a domain-independent heuristic forward chaining planner that can handle durative actions, metric resource constraints, and deadline goals. It is designed to be capable of handling the multi-objective nature of metric temporal planning. Our technical contributions include (i) planning-graph based methods for deriving heuristics that are sensitive to both cost and makespan (ii) techniques for adjusting the heuristic estimates to take action interactions and metric resource limitations into account and (iii) a linear time greedy post-processing technique to improve execution flexibility of the solution plans. An implementation of SAPA using many of the techniques presented in this paper was one of the best domain independent planners for domains with metric and temporal constraints in the third International Planning Competition, held at AIPS-02. We describe the technical details of extracting the heuristics and present an empirical evaluation of the current implementation of SAPA. Edelkamp, S. (2003) "Taming Numbers and Durations in the Model Checking Integrated Planning System", Volume 20, pages 195-238. For quick access go to Abstract: The Model Checking Integrated Planning System (MIPS) is a temporal least commitment heuristic search planner based on a flexible object-oriented workbench architecture. Its design clearly separates explicit and symbolic directed exploration algorithms from the set of on-line and off-line computed estimates and associated data structures. MIPS has shown distinguished performance in the last two international planning competitions. In the last event the description language was extended from pure propositional planning to include numerical state variables, action durations, and plan quality objective functions. Plans were no longer sequences of actions but time-stamped schedules. As a participant of the fully automated track of the competition, MIPS has proven to be a general system; in each track and every benchmark domain it efficiently computed plans of remarkable quality. This article introduces and analyzes the most important algorithmic novelties that were necessary to tackle the new layers of expressiveness in the benchmark problems and to achieve a high level of performance. The extensions include critical path analysis of sequentially generated plans to generate corresponding optimal parallel plans. The linear time algorithm to compute the parallel plan bypasses known NP hardness results for partial ordering by scheduling plans with respect to the set of actions and the imposed precedence relations. The efficiency of this algorithm also allows us to improve the exploration guidance: for each encountered planning state the corresponding approximate sequential plan is scheduled. One major strength of MIPS is its static analysis phase that grounds and simplifies parameterized predicates, functions and operators, that infers knowledge to minimize the state description length, and that detects domain object symmetries. The latter aspect is analyzed in detail. MIPS has been developed to serve as a complete and optimal state space planner, with admissible estimates, exploration engines and branching cuts. In the competition version, however, certain performance compromises had to be made, including floating point arithmetic, weighted heuristic search exploration according to an inadmissible estimate and parameterized optimization. Gerevini, A., Saetti, A. and Serina, I. (2003) "Planning Through Stochastic Local Search and Temporal Action Graphs in LPG", Volume 20, pages 239-290. For quick access go to Abstract: We present some techniques for planning in domains specified with the recent standard language PDDL2.1, supporting 'durative actions' and numerical quantities. These techniques are implemented in LPG, a domain-independent planner that took part in the 3rd International Planning Competition (IPC). LPG is an incremental, any time system producing multi-criteria quality plans. The core of the system is based on a stochastic local search method and on a graph-based representation called 'Temporal Action Graphs' (TA-graphs). This paper focuses on temporal planning, introducing TA-graphs and proposing some techniques to guide the search in LPG using this representation. The experimental results of the 3rd IPC, as well as further results presented in this paper, show that our techniques can be very effective. Often LPG outperforms all other fully-automated planners of the 3rd IPC in terms of speed to derive a solution, or quality of the solutions that can be produced. Hoffmann, J. (2003) "The Metric-FF Planning System: Translating ``Ignoring Delete Lists'' to Numeric State Variables", Volume 20, pages 291-341. An online appendix (C code for the Metric-FF system) is also a available. For quick access go to Abstract: Planning with numeric state variables has been a challenge for many years, and was a part of the 3rd International Planning Competition (IPC-3). Currently one of the most popular and successful algorithmic techniques in STRIPS planning is to guide search by a heuristic function, where the heuristic is based on relaxing the planning task by ignoring the delete lists of the available actions. We present a natural extension of ``ignoring delete lists'' to numeric state variables, preserving the relevant theoretical properties of the STRIPS relaxation under the condition that the numeric task at hand is ``monotonic''. We then identify a subset of the numeric IPC-3 competition language, ``linear tasks'', where monotonicity can be achieved by pre-processing. Based on that, we extend the algorithms used in the heuristic planning system FF to linear tasks. The resulting system Metric-FF is, according to the IPC-3 results which we discuss, one of the two currently most efficient numeric planners. Kvarnström, J. and Magnusson, M. (2003) "TALplanner in IPC-2002: Extensions and Control Rules", Volume 20, pages 343-377. For quick access go to Abstract: TALplanner is a forward-chaining planner that relies on domain knowledge in the shape of temporal logic formulas in order to prune irrelevant parts of the search space. TALplanner recently participated in the third International Planning Competition, which had a clear emphasis on increasing the complexity of the problem domains being used as benchmark tests and the expressivity required to represent these domains in a planning system. Like many other planners, TALplanner had support for some but not all aspects of this increase in expressivity, and a number of changes to the planner were required. After a short introduction to TALplanner, this article describes some of the changes that were made before and during the competition. We also describe the process of introducing suitable domain knowledge for several of the competition domains. Nau, D.S., Au, T.C., Ilghami, O., Kuter, U., Murdock, J.W., Wu, D. and Yaman, F. (2003) "SHOP2: An HTN Planning System", Volume 20, pages 379-404. For quick access go to Abstract: The SHOP2 planning system received one of the awards for distinguished performance in the 2002 International Planning Competition. This paper describes the features of SHOP2 which enabled it to excel in the competition, especially those aspects of SHOP2 that deal with temporal and metric planning domains. Younes, H.L.S. and Simmons, R.G. (2003) "VHPOP: Versatile Heuristic Partial Order Planner", Volume 20, pages 405-430. An online appendix (Source code for VHPOP version 2.2) is also a available. For quick access go to Abstract: VHPOP is a partial order causal link (POCL) planner loosely based on UCPOP. It draws from the experience gained in the early to mid 1990's on flaw selection strategies for POCL planning, and combines this with more recent developments in the field of domain independent planning such as distance based heuristics and reachability analysis. We present an adaptation of the additive heuristic for plan space planning, and modify it to account for possible reuse of existing actions in a plan. We also propose a large set of novel flaw selection strategies, and show how these can help us solve more problems than previously possible by POCL planners. VHPOP also supports planning with durative actions by incorporating standard techniques for temporal constraint reasoning. We demonstrate that the same heuristic techniques used to boost the performance of classical POCL planning can be effective in domains with durative actions as well. The result is a versatile heuristic POCL planner competitive with established CSP-based and heuristic state space planners. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jairmail@ISI.EDU Fri Apr 2 11:39:30 2004 Received: from nitro.isi.edu (nitro.isi.edu [128.9.208.207]) by gamma.isi.edu (8.11.6p2+0917/8.11.2) with ESMTP id i32JdUk23775 for ; Fri, 2 Apr 2004 11:39:30 -0800 (PST) Received: (from jairmail@localhost) by nitro.isi.edu (8.11.6p2+0917/8.11.2) id i32JdUn02918; Fri, 2 Apr 2004 11:39:30 -0800 (PST) Date: Fri, 2 Apr 2004 11:39:30 -0800 (PST) Message-Id: <200404021939.i32JdUn02918@nitro.isi.edu> From: JAIRMAIL To: jairsubscribers@mailman.isi.edu Subject: [Jairsubscribers] JAIR Update X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.4 Precedence: list Reply-To: jair-ed@isi.edu List-Id: jairsubscribers.mailman.isi.edu List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 02 Apr 2004 19:39:31 -0000 CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) Zhang, N.L. and Kocka, T. (2004) "Effective Dimensions of Hierarchical Latent Class Models" Wellman, M.P., Reeves, D.M., Lochner, K.M. and Vorobeychik, Y. (2004) "Price Prediction in a Trading Agent Competition" Monderer, D. and Tennenholtz, M. (2004) "K-Implementation" Stanley, K.S. and Miikkulainen, R. (2004) "Competitive Coevolution through Evolutionary Complexification" Park, J.D. and Darwiche, A. (2004) "Complexity Results and Approximation Strategies for MAP Explanations" Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H.H. and Poole, D. (2004) "CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements" Dixon, H.E., Ginsberg, M.L. and Parkes, A.J. (2004) "Generalizing Boolean Satisfiability I: Background and Survey of Existing Work" Arieli, O., Denecker, M., Van Nuffelen, B. and Bruynooghe, M. (2004) "Coherent Integration of Databases by Abductive Logic Programming" Nederhof, M.J. and Satta, G. (2004) "IDL-Expressions: A Formalism for Representing and Parsing Finite Languages in Natural Language Processing" Hnich, B., Smith, B.M. and Walsh, T. (2004) "Dual Modelling of Permutation and Injection Problems" Halpern, J.Y. and Koller, D. (2004) "Representation Dependence in Probabilistic Inference" Thompson, C.A., Goker, M.H. and Langley, P. (2004) "A Personalized System for Conversational Recommendations" ---------------------------------------------------------------- I. New JAIR Articles Zhang, N.L. and Kocka, T. (2004) "Effective Dimensions of Hierarchical Latent Class Models", Volume 21, pages 1-17. For quick access go to Abstract: Hierarchical latent class (HLC) models are tree-structured Bayesian networks where leaf nodes are observed while internal nodes are latent. There are no theoretically well justified model selection criteria for HLC models in particular and Bayesian networks with latent nodes in general. Nonetheless, empirical studies suggest that the BIC score is a reasonable criterion to use in practice for learning HLC models. Empirical studies also suggest that sometimes model selection can be improved if standard model dimension is replaced with effective model dimension in the penalty term of the BIC score. Effective dimensions are difficult to compute. In this paper, we prove a theorem that relates the effective dimension of an HLC model to the effective dimensions of a number of latent class models. The theorem makes it computationally feasible to compute the effective dimensions of large HLC models. The theorem can also be used to compute the effective dimensions of general tree models. Wellman, M.P., Reeves, D.M., Lochner, K.M. and Vorobeychik, Y. (2004) "Price Prediction in a Trading Agent Competition", Volume 21, pages 19-36. For quick access go to Abstract: The 2002 Trading Agent Competition (TAC) presented a challenging market game in the domain of travel shopping. One of the pivotal issues in this domain is uncertainty about hotel prices, which have a significant influence on the relative cost of alternative trip schedules. Thus, virtually all participants employ some method for predicting hotel prices. We survey approaches employed in the tournament, finding that agents apply an interesting diversity of techniques, taking into account differing sources of evidence bearing on prices. Based on data provided by entrants on their agents' actual predictions in the TAC-02 finals and semifinals, we analyze the relative efficacy of these approaches. The results show that taking into account game-specific information about flight prices is a major distinguishing factor. Machine learning methods effectively induce the relationship between flight and hotel prices from game data, and a purely analytical approach based on competitive equilibrium analysis achieves equal accuracy with no historical data. Employing a new measure of prediction quality, we relate absolute accuracy to bottom-line performance in the game. Monderer, D. and Tennenholtz, M. (2004) "K-Implementation", Volume 21, pages 37-62. For quick access go to Abstract: This paper discusses an interested party who wishes to influence the behavior of agents in a game (multi-agent interaction), which is not under his control. The interested party cannot design a new game, cannot enforce agents' behavior, cannot enforce payments by the agents, and cannot prohibit strategies available to the agents. However, he can influence the outcome of the game by committing to non-negative monetary transfers for the different strategy profiles that may be selected by the agents. The interested party assumes that agents are rational in the commonly agreed sense that they do not use dominated strategies. Hence, a certain subset of outcomes is implemented in a given game if by adding non-negative payments, rational players will necessarily produce an outcome in this subset. Obviously, by making sufficiently big payments one can implement any desirable outcome. The question is what is the cost of implementation? In this paper we introduce the notion of k-implementation of a desired set of strategy profiles, where k stands for the amount of payment that need to be actually made in order to implement desirable outcomes. A major point in k-implementation is that monetary offers need not necessarily materialize when following desired behaviors. We define and study k-implementation in the contexts of games with complete and incomplete information. In the latter case we mainly focus on the VCG games. Our setting is later extended to deal with mixed strategies using correlation devices. Together, the paper introduces and studies the implementation of desirable outcomes by a reliable party who cannot modify game rules (i.e. provide protocols), complementing previous work in mechanism design, while making it more applicable to many realistic CS settings. Stanley, K.S. and Miikkulainen, R. (2004) "Competitive Coevolution through Evolutionary Complexification", Volume 21, pages 63-100. For quick access go to Abstract: Two major goals in machine learning are the discovery and improvement of solutions to complex problems. In this paper, we argue that complexification, i.e. the incremental elaboration of solutions through adding new structure, achieves both these goals. We demonstrate the power of complexification through the NeuroEvolution of Augmenting Topologies (NEAT) method, which evolves increasingly complex neural network architectures. NEAT is applied to an open-ended coevolutionary robot duel domain where robot controllers compete head to head. Because the robot duel domain supports a wide range of strategies, and because coevolution benefits from an escalating arms race, it serves as a suitable testbed for studying complexification. When compared to the evolution of networks with fixed structure, complexifying evolution discovers significantly more sophisticated strategies. The results suggest that in order to discover and improve complex solutions, evolution, and search in general, should be allowed to complexify as well as optimize. Park, J.D. and Darwiche, A. (2004) "Complexity Results and Approximation Strategies for MAP Explanations", Volume 21, pages 101-133. For quick access go to Abstract: MAP is the problem of finding a most probable instantiation of a set of variables given evidence. MAP has always been perceived to be significantly harder than the related problems of computing the probability of a variable instantiation Pr, or the problem of computing the most probable explanation (MPE). This paper investigates the complexity of MAP in Bayesian networks. Specifically, we show that MAP is complete for NP^PP and provide further negative complexity results for algorithms based on variable elimination. We also show that MAP remains hard even when MPE and Pr become easy. For example, we show that MAP is NP-complete when the networks are restricted to polytrees, and even then can not be effectively approximated. Given the difficulty of computing MAP exactly, and the difficulty of approximating MAP while providing useful guarantees on the resulting approximation, we investigate best effort approximations. We introduce a generic MAP approximation framework. We provide two instantiations of the framework; one for networks which are amenable to exact inference Pr, and one for networks for which even exact inference is too hard. This allows MAP approximation on networks that are too complex to even exactly solve the easier problems, Pr and MPE. Experimental results indicate that using these approximation algorithms provides much better solutions than standard techniques, and provide accurate MAP estimates in many cases. Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H.H. and Poole, D. (2004) "CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements", Volume 21, pages 135-191. For quick access go to Abstract: Information about user preferences plays a key role in automated decision making. In many domains it is desirable to assess such preferences in a qualitative rather than quantitative way. In this paper, we propose a qualitative graphical representation of preferences that reflects conditional dependence and independence of preference statements under a ceteris paribus (all else being equal) interpretation. Such a representation is often compact and arguably quite natural in many circumstances. We provide a formal semantics for this model, and describe how the structure of the network can be exploited in several inference tasks, such as determining whether one outcome dominates (is preferred to) another, ordering a set outcomes according to the preference relation, and constructing the best outcome subject to available evidence. Dixon, H.E., Ginsberg, M.L. and Parkes, A.J. (2004) "Generalizing Boolean Satisfiability I: Background and Survey of Existing Work", Volume 21, pages 193-243. For quick access go to Abstract: This is the first 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 is a survey of the work underlying ZAP, and discusses previous attempts to improve the performance of the Davis-Putnam-Logemann-Loveland algorithm by exploiting the structure of the problem being solved. We examine existing ideas including extensions of the Boolean language to allow cardinality constraints, pseudo-Boolean representations, symmetry, and a limited form of quantification. While this paper is intended as a survey, our research results are contained in the two subsequent articles, with the theoretical structure of ZAP described in the second paper in this series, and ZAP's implementation described in the third. Arieli, O., Denecker, M., Van Nuffelen, B. and Bruynooghe, M. (2004) "Coherent Integration of Databases by Abductive Logic Programming", Volume 21, pages 245-286. For quick access go to Abstract: We introduce an abductive method for a coherent integration of independent data-sources. The idea is to compute a list of data-facts that should be inserted to the amalgamated database or retracted from it in order to restore its consistency. This method is implemented by an abductive solver, called Asystem, that applies SLDNFA-resolution on a meta-theory that relates different, possibly contradicting, input databases. We also give a pure model-theoretic analysis of the possible ways to `recover' consistent data from an inconsistent database in terms of those models of the database that exhibit as minimal inconsistent information as reasonably possible. This allows us to characterize the `recovered databases' in terms of the `preferred' (i.e., most consistent) models of the theory. The outcome is an abductive-based application that is sound and complete with respect to a corresponding model-based, preferential semantics, and -- to the best of our knowledge -- is more expressive (thus more general) than any other implementation of coherent integration of databases. Nederhof, M.J. and Satta, G. (2004) "IDL-Expressions: A Formalism for Representing and Parsing Finite Languages in Natural Language Processing", Volume 21, pages 287-317. For quick access go to Abstract: We propose a formalism for representation of finite languages, referred to as the class of IDL-expressions, which combines concepts that were only considered in isolation in existing formalisms. The suggested applications are in natural language processing, more specifically in surface natural language generation and in machine translation, where a sentence is obtained by first generating a large set of candidate sentences, represented in a compact way, and then by filtering such a set through a parser. We study several formal properties of IDL-expressions and compare this new formalism with more standard ones. We also present a novel parsing algorithm for IDL-expressions and prove a non-trivial upper bound on its time complexity. Hnich, B., Smith, B.M. and Walsh, T. (2004) "Dual Modelling of Permutation and Injection Problems", Volume 21, pages 357-391. For quick access go to Abstract: When writing a constraint program, we have to choose which variables should be the decision variables, and how to represent the constraints on these variables. In many cases, there is considerable choice for the decision variables. Consider, for example, permutation problems in which we have as many values as variables, and each variable takes an unique value. In such problems, we can choose between a primal and a dual viewpoint. In the dual viewpoint, each dual variable represents one of the primal values, whilst each dual value represents one of the primal variables. Alternatively, by means of channelling constraints to link the primal and dual variables, we can have a combined model with both sets of variables. In this paper, we perform an extensive theoretical and empirical study of such primal, dual and combined models for two classes of problems: permutation problems and injection problems. Our results show that it often be advantageous to use multiple viewpoints, and to have constraints which channel between them to maintain consistency. They also illustrate a general methodology for comparing different constraint models. Halpern, J.Y. and Koller, D. (2004) "Representation Dependence in Probabilistic Inference", Volume 21, pages 319-356. For quick access go to Abstract: Non-deductive reasoning systems are often representation dependent: representing the same situation in two different ways may cause such a system to return two different answers. Some have viewed this as a significant problem. For example, the principle of maximum entropyhas been subjected to much criticism due to its representation dependence. There has, however, been almost no work investigating representation dependence. In this paper, we formalize this notion and show that it is not a problem specific to maximum entropy. In fact, we show that any representation-independent probabilistic inference procedure that ignores irrelevant information is essentially entailment, in a precise sense. Moreover, we show that representation independence is incompatible with even a weak default assumption of independence. We then show that invariance under a restricted class of representation changes can form a reasonable compromise between representation independence and other desiderata, and provide a construction of a family of inference procedures that provides such restricted representation independence, using relative entropy. Thompson, C.A., Goker, M.H. and Langley, P. (2004) "A Personalized System for Conversational Recommendations", Volume 21, pages 393-428. For quick access go to Abstract: Searching for and making decisions about information is becoming increasingly difficult as the amount of information and number of choices increases. Recommendation systems help users find items of interest of a particular type, such as movies or restaurants, but are still somewhat awkward to use. Our solution is to take advantage of the complementary strengths of personalized recommendation systems and dialogue systems, creating personalized aides. We present a system -- the Adaptive Place Advisor -- that treats item selection as an interactive, conversational process, with the program inquiring about item attributes and the user responding. Individual, long-term user preferences are unobtrusively obtained in the course of normal recommendation dialogues and used to direct future conversations with the same user. We present a novel user model that influences both item search and the questions asked during a conversation. We demonstrate the effectiveness of our system in significantly reducing the time and number of interactions required to find a satisfactory item, as compared to a control group of users interacting with a non-adaptive version of the system. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jairmail@ISI.EDU Sat Jul 24 14:25:03 2004 Received: from nitro.isi.edu (nitro.isi.edu [128.9.208.207]) by gamma.isi.edu (8.11.6p2+0917/8.11.2) with ESMTP id i6OLOSi04293 for ; Sat, 24 Jul 2004 14:24:28 -0700 (PDT) Received: (from jairmail@localhost) by nitro.isi.edu (8.11.6p2+0917/8.11.2) id i6OLOSM10804; Sat, 24 Jul 2004 14:24:28 -0700 (PDT) Date: Sat, 24 Jul 2004 14:24:28 -0700 (PDT) Message-Id: <200407242124.i6OLOSM10804@nitro.isi.edu> From: JAIRMAIL To: jairsubscribers@mailman.isi.edu X-ISI-4-30-3-MailScanner: Found to be clean X-MailScanner-From: jairmail@isi.edu Subject: [Jairsubscribers] JAIR Update X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.4 Precedence: list Reply-To: jair-ed@isi.edu List-Id: jairsubscribers.mailman.isi.edu List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 24 Jul 2004 21:25:04 -0000 CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles and Unsubscribing Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) Zhang, W. "Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem" Keppens, J. and Shen, Q. "Compositional Model Repositories via Dynamic Constraint Satisfaction with Order-of-Magnitude Preferences" Liberatore, P. "On Polynomial Sized MDP Succinct Policies" Borodin, A., El-Yaniv, R. and Gogan, V. "Can We Learn to Beat the Best Stock" Babaioff, M. and Nisan, N. "Concurrent Auctions Across The Supply Chain" Felner, A., Stern, R., Ben-Yair, A., Kraus, S. and Netanyahu, N. "PHA*: Finding the Shortest Path with A* in An Unknown Physical Environment" ---------------------------------------------------------------- I. New JAIR Articles Zhang, W. (2004) "Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem", Volume 21, pages 471-497. For quick access go to Abstract: In recent years, there has been much interest in phase transitions of combinatorial problems. Phase transitions have been successfully used to analyze combinatorial optimization problems, characterize their typical-case features and locate the hardest problem instances. In this paper, we study phase transitions of the asymmetric Traveling Salesman Problem (ATSP), an NP-hard combinatorial optimization problem that has many real-world applications. Using random instances of up to 1,500 cities in which intercity distances are uniformly distributed, we empirically show that many properties of the problem, including the optimal tour cost and backbone size, experience sharp transitions as the precision of intercity distances increases across a critical value. Our experimental results on the costs of the ATSP tours and assignment problem agree with the theoretical result that the asymptotic cost of assignment problem is pi ^2 /6 the number of cities goes to infinity. In addition, we show that the average computational cost of the well-known branch-and-bound subtour elimination algorithm for the problem also exhibits a thrashing behavior, transitioning from easy to difficult as the distance precision increases. These results answer positively an open question regarding the existence of phase transitions in the ATSP, and provide guidance on how difficult ATSP problem instances should be generated. Keppens, J. and Shen, Q. (2004) "Compositional Model Repositories via Dynamic Constraint Satisfaction with Order-of-Magnitude Preferences",Volume 21, pages 499-550. For quick access go to Abstract: The predominant knowledge-based approach to automated model construction, compositional modelling, employs a set of models of particular functional components. Its inference mechanism takes a scenario describing the constituent interacting components of a system and translates it into a useful mathematical model. This paper presents a novel compositional modelling approach aimed at building model repositories. It furthers the field in two respects. Firstly, it expands the application domain of compositional modelling to systems that can not be easily described in terms of interacting functional components, such as ecological systems. Secondly, it enables the incorporation of user preferences into the model selection process. These features are achieved by casting the compositional modelling problem as an activity-based dynamic preference constraint satisfaction problem, where the dynamic constraints describe the restrictions imposed over the composition of partial models and the preferences correspond to those of the user of the automated modeller. In addition, the preference levels are represented through the use of symbolic values that differ in orders of magnitude. Liberatore, P. (2004) "On Polynomial Sized MDP Succinct Policies", Volume 21, pages 551-577. For quick access go to Abstract: Policies of Markov Decision Processes (MDPs) determine the next action to execute from the current state and, possibly, the history (the past states). When the number of states is large, succinct representations are often used to compactly represent both the MDPs and the policies in a reduced amount of space. In this paper, some problems related to the size of succinctly represented policies are analyzed. Namely, it is shown that some MDPs have policies that can only be represented in space super-polynomial in the size of the MDP, unless the polynomial hierarchy collapses. This fact motivates the study of the problem of deciding whether a given MDP has a policy of a given size and reward. Since some algorithms for MDPs work by finding a succinct representation of the value function, the problem of deciding the existence of a succinct representation of a value function of a given size and reward is also considered. Borodin, A., El-Yaniv, R. and Gogan, V. (2004) "Can We Learn to Beat the Best Stock", Volume 21, pages 579-594. For quick access go to Abstract: A novel algorithm for actively trading stocks is presented. While traditional expert advice and ``universal'' algorithms (as well as standard technical trading heuristics) attempt to predict winners or trends, our approach relies on predictable statistical relations between all pairs of stocks in the market. Our empirical results on historical markets provide strong evidence that this type of technical trading can ``beat the market'' and moreover, can beat the best stock in the market. In doing so we utilize a new idea for smoothing critical parameters in the context of expert learning. Babaioff, M. and Nisan, N. (2004) "Concurrent Auctions Across The Supply Chain", Volume 21, pages 595-629. For quick access go to Abstract: With the recent technological feasibility of electronic commerce over the Internet, much attention has been given to the design of electronic markets for various types of electronically-tradable goods. Such markets, however, will normally need to function in some relationship with markets for other related goods, usually those downstream or upstream in the supply chain. Thus, for example, an electronic market for rubber tires for trucks will likely need to be strongly influenced by the rubber market as well as by the truck market. In this paper we design protocols for exchange of information between a sequence of markets along a single supply chain. These protocols allow each of these markets to function separately, while the information exchanged ensures efficient global behavior across the supply chain. Each market that forms a link in the supply chain operates as a double auction, where the bids on one side of the double auction come from bidders in the corresponding segment of the industry, and the bids on the other side are synthetically generated by the protocol to express the combined information from all other links in the chain. The double auctions in each of the markets can be of several types, and we study several variants of incentive compatible double auctions, comparing them in terms of their efficiency and of the market revenue. Felner, A., Stern, R., Ben-Yair, A., Kraus, S. and Netanyahu, N. (2004) "PHA*: Finding the Shortest Path with A* in An Unknown Physical Environment", Volume 21, pages 631-670. For quick access go to Abstract: We address the problem of finding the shortest path between two points in an unknown real physical environment, where a traveling agent must move around in the environment to explore unknown territory. We introduce the Physical-A* algorithm (PHA*) for solving this problem. PHA* expands all the mandatory nodes that A* would expand and returns the shortest path between the two points. However, due to the physical nature of the problem, the complexity of the algorithm is measured by the traveling effort of the moving agent and not by the number of generated nodes, as in standard A*. PHA* is presented as a two-level algorithm, such that its high level, A*, chooses the next node to be expanded and its low level directs the agent to that node in order to explore it. We present a number of variations for both the high-level and low-level procedures and evaluate their performance theoretically and experimentally. We show that the travel cost of our best variation is fairly close to the optimal travel cost, assuming that the mandatory nodes of A* are known in advance. We then generalize our algorithm to the multi-agent case, where a number of cooperative agents are designed to solve the problem. Specifically, we provide an experimental implementation for such a system. It should be noted that the problem addressed here is not a navigation problem, but rather a problem of finding the shortest path between two points for future usage. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jairmail@ISI.EDU Mon Nov 8 10:14:30 2004 Received: from nitro.isi.edu (nitro.isi.edu [128.9.208.207]) by gamma.isi.edu (8.11.6p2+0917/8.11.2) with ESMTP id iA8IDYT13339 for ; Mon, 8 Nov 2004 10:13:34 -0800 (PST) Received: (from jairmail@localhost) by nitro.isi.edu (8.11.6p2+0917/8.11.2) id iA8IDY120434; Mon, 8 Nov 2004 10:13:34 -0800 (PST) Date: Mon, 8 Nov 2004 10:13:34 -0800 (PST) Message-Id: <200411081813.iA8IDY120434@nitro.isi.edu> From: JAIRMAIL To: jairsubscribers@mailman.isi.edu X-ISI-4-30-3-MailScanner: Found to be clean X-MailScanner-From: jairmail@isi.edu Subject: [Jairsubscribers] JAIR Update X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.4 Precedence: list Reply-To: jair-ed@isi.edu List-Id: jairsubscribers.mailman.isi.edu List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 08 Nov 2004 18:14:30 -0000 CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles III. News: 2004 IJCAII-JAIR Best Paper Prize awarded to Ygge and Akkermans Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) ---------------------------------------------------------------- I. New JAIR Articles Cohen, D., Cooper, M., Jeavons, P. and Krokhin, A. (2004) "A Maximal Tractable Class of Soft Constraints", Volume 22, pages 1-22. For quick access go to Abstract: 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. Dubois, D., Fargier, H. and Prade, H. (2004) "Ordinal and Probabilistic Representations of Acceptance", Volume 22, pages 23-56. For quick access go to Abstract: 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. Meek, C.J. and Birmingham, W.P. (2004) "A Comprehensive Trainable Error Model for Sung Music Queries", Volume 22, pages 57-91. For quick access go to Abstract: 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. Chockler, H. and Halpern, J.Y. (2004) "Responsibility and Blame: A Structural-Model Approach", Volume 22, pages 93-115. For quick access go to Abstract: 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. Derbeko, P, El-Yaniv, R. and Meir, R. (2004) "Explicit Learning Curves for Transduction and Application to Clustering and Compression Algorithms", Volume 22, pages 117-142. For quick access go to Abstract: 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. Goldman, C.V. and Zilberstein, S. (2004) "Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis", Volume 22, pages 143-174. For quick access go to Abstract: 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. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. ---------------------------------------------------------------- III. News: IJCAII-JAIR Best Paper Award The winner of the 2004 IJCAII-JAIR Best Paper Prize is: Ygge, F. and Akkermans, H. (1999) "Decentralized Markets versus Central Control: A Comparative Study", 11, 301-333 The following paper was selected for Honorable Mention: Fox, D., Burgard, W. and Thrun, S. (1999) "Markov Localization for Mobile Robots in Dynamic Environments", 11, 391-427. The Annual IJCAII-JAIR Best Paper Prize is awarded to an outstanding paper published in JAIR in the preceding five calendar years. For 2003, papers published between 1999 and 2003 (inclusive) were eligible. The prize committee is comprised of associate editors and members of the JAIR Advisory Board; their decision is based on both the significance of the paper and the quality of presentation. The recipient(s) of the award receives a prize of US$500 (to be split amongst the authors of a co-authored paper). Funding for this award was provided by the International Joint Conference on Artificial Intelligence, Inc. From www-data@booberry.fetch.com Wed Jul 2 11:51:12 2008 Received: from fetch.com (mail.fetch.com [12.157.138.12]) by gamma.isi.edu (8.13.8/8.13.8) with ESMTP id m62IkA2T015913 for ; Wed, 2 Jul 2008 11:46:11 -0700 (PDT) Received: from booberry.fetch.local ([192.168.219.143]) by fetch.com with Microsoft SMTPSVC(6.0.3790.1830); Wed, 2 Jul 2008 11:46:45 -0700 Received: from www-data by booberry.fetch.local with local (Exim 4.60) (envelope-from ) id 1KE7LB-0008EA-Ti; Wed, 02 Jul 2008 18:46:05 +0000 To: jairsubscribers@mailman.isi.edu MIME-Version: 1.0 X-Mailer: htmlMimeMail5 From: jair-ed@ISI.EDU Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit Message-ID: Date: Wed, 02 Jul 2008 18:46:05 +0000 X-OriginalArrivalTime: 02 Jul 2008 18:46:45.0968 (UTC) FILETIME=[FA5B0D00:01C8DC73] X-TM-AS-Product-Ver: SMEX-7.5.0.1243-5.5.1027-16008.001 X-TM-AS-Result: No--9.839000-5.000000-31 X-TM-AS-User-Approved-Sender: No X-TM-AS-User-Blocked-Sender: No X-ISI-4-43-8-MailScanner: Found to be clean X-MailScanner-From: www-data@booberry.fetch.com Cc: jair-ed@ISI.EDU, keith@ucla.edu Subject: [Jairsubscribers] 7 new articles published by JAIR X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.6 Precedence: list Reply-To: jair-ed@isi.edu List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 02 Jul 2008 18:51:15 -0000 Dear JAIR subscriber: We are pleased to announce that the JAIR mailing list is back in operation. This message lists papers that have been published in JAIR in the last month and describes how to access them. (If you wish to remove yourself from this mailing list, see instructions at the end of this message.) ---------------------------------------------------------------- I. New JAIR Articles V. Bulitko, M. Lustrek, J. Schaeffer, Y. Bjornsson and S. Sigmundarson (2008) "Dynamic Control in Real-Time Heuristic Search", Volume 32, pages 419-452 For quick access go to Abstract: Real-time heuristic search is a challenging type of agent-centered search because the agent's planning time per action is bounded by a constant independent of problem size. A common problem that imposes such restrictions is pathfinding in modern computer games where a large number of units must plan their paths simultaneously over large maps. Common search algorithms (e.g., A*, IDA*, D*, ARA*, AD*) are inherently not real-time and may lose completeness when a constant bound is imposed on per-action planning time. Real-time search algorithms retain completeness but frequently produce unacceptably suboptimal solutions. In this paper, we extend classic and modern real-time search algorithms with an automated mechanism for dynamic depth and subgoal selection. The new algorithms remain real-time and complete. On large computer game maps, they find paths within 7% of optimal while on average expanding roughly a single state per action. This is nearly a three-fold improvement in suboptimality over the existing state-of-the-art algorithms and, at the same time, a 15-fold improvement in the amount of planning per action. B. C. Csaji and L. Monostori (2008) "Adaptive Stochastic Resource Control: A Machine Learning Approach", Volume 32, pages 453-486 For quick access go to Abstract: The paper investigates stochastic resource allocation problems with scarce, reusable resources and non-preemtive, time-dependent, interconnected tasks. This approach is a natural generalization of several standard resource management problems, such as scheduling and transportation problems. First, reactive solutions are considered and defined as control policies of suitably reformulated Markov decision processes (MDPs). We argue that this reformulation has several favorable properties, such as it has finite state and action spaces, it is aperiodic, hence all policies are proper and the space of control policies can be safely restricted. Next, approximate dynamic programming (ADP) methods, such as fitted Q-learning, are suggested for computing an efficient control policy. In order to compactly maintain the cost-to-go function, two representations are studied: hash tables and support vector regression (SVR), particularly, nu-SVRs. Several additional improvements, such as the application of limited-lookahead rollout algorithms in the initial phases, action space decomposition, task clustering and distributed sampling are investigated, too. Finally, experimental results on both benchmark and industry-related data are presented. F. Stulp and M. Beetz (2008) "Refining the Execution of Abstract Actions with Learned Action Models", Volume 32, pages 487-523 For quick access go to Abstract: Robots reason about abstract actions, such as "go to position `l'", in order to decide what to do or to generate plans for their intended course of action. The use of abstract actions enables robots to employ small action libraries, which reduces the search space for decision making. When executing the actions, however, the robot must tailor the abstract actions to the specific task and situation context at hand. In this article we propose a novel robot action execution system that learns success and performance models for possible specializations of abstract actions. At execution time, the robot uses these models to optimize the execution of abstract actions to the respective task contexts. The robot can so use abstract actions for efficient reasoning, without compromising the performance of action execution. We show the impact of our action execution model in three robotic domains and on two kinds of action execution problems: (1) the instantiation of free action parameters to optimize the expected performance of action sequences; (2) the automatic introduction of additional subgoals to make action sequences more reliable. S. Bouveret and J. Lang (2008) "Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity", Volume 32, pages 525-564 For quick access go to Abstract: We consider the problem of allocating fairly a set of indivisible goods among agents from the point of view of compact representation and computational complexity. We start by assuming that agents have dichotomous preferences expressed by propositional formulae. We express efficiency and envy-freeness in a logical setting, which reveals unexpected connections to nonmonotonic reasoning. Then we identify the complexity of determining whether there exists an efficient and envy-free allocation, for several notions of efficiency, when preferences are represented in a succinct way (as well as restrictions of this problem). We first study the problem under the assumption that preferences are dichotomous, and then in the general case. L. Xu, F. Hutter, H. H. Hoos and K. Leyton-Brown (2008) "SATzilla: Portfolio-based Algorithm Selection for SAT", Volume 32, pages 565-606 For quick access go to Abstract: It has been widely observed that there is no single "dominant" SAT solver; instead, different solvers perform best on different instances. Rather than following the traditional approach of choosing the best solver for a given class of instances, we advocate making this decision online on a per-instance basis. Building on previous work, we describe SATzilla, an automated approach for constructing per-instance algorithm portfolios for SAT that use so-called empirical hardness models to choose among their constituent solvers. This approach takes as input a distribution of problem instances and a set of component solvers, and constructs a portfolio optimizing a given objective function (such as mean runtime, percent of instances solved, or score in a competition). The excellent performance of SATzilla was independently verified in the 2007 SAT Competition, where our SATzilla07 solvers won three gold, one silver and one bronze medal. In this article, we go well beyond SATzilla07 by making the portfolio construction scalable and completely automated, and improving it by integrating local search solvers as candidate solvers, by predicting performance score instead of runtime, and by using hierarchical hardness models that take into account different types of SAT instances. We demonstrate the effectiveness of these new techniques in extensive experimental results on data sets including instances from the most recent SAT competition. L. Bordeaux, M. Cadoli and T. Mancini (2008) "A Unifying Framework for Structural Properties of CSPs: Definitions, Complexity, Tractability", Volume 32, pages 607-629 For quick access go to Abstract: Literature on Constraint Satisfaction exhibits the definition of several ``structural'' properties that can be possessed by CSPs, like (in)consistency, substitutability or interchangeability. Current tools for constraint solving typically detect such properties efficiently by means of incomplete yet effective algorithms, and use them to reduce the search space and boost search. In this paper, we provide a unifying framework encompassing most of the properties known so far, both in CSP and other fields' literature, and shed light on the semantical relationships among them. This gives a unified and comprehensive view of the topic, allows new, unknown, properties to emerge, and clarifies the computational complexity of the various detection problems. In particular, among the others, two new concepts, fixability and removability emerge, that come out to be the ideal characterisations of values that may be safely assigned or removed from a variable's domain, while preserving problem satisfiability. These two notions subsume a large number of known properties, including inconsistency, substitutability and others. Because of the computational intractability of all the property-detection problems, by following the CSP approach we then determine a number of relaxations which provide sufficient conditions for their tractability. In particular, we exploit forms of language restrictions and local reasoning. F. Yang , J. Culberson , R. Holte, U. Zahavi and A. Felner (2008) "A General Theory of Additive State Space Abstractions", Volume 32, pages 631-662 For quick access go to Abstract: Informally, a set of abstractions of a state space S is additive if the distance between any two states in S is always greater than or equal to the sum of the corresponding distances in the abstract spaces. The first known additive abstractions, called disjoint pattern databases, were experimentally demonstrated to produce state of the art performance on certain state spaces. However, previous applications were restricted to state spaces with special properties, which precludes disjoint pattern databases from being defined for several commonly used testbeds, such as Rubik's Cube, TopSpin and the Pancake puzzle. In this paper we give a general definition of additive abstractions that can be applied to any state space and prove that heuristics based on additive abstractions are consistent as well as admissible. We use this new definition to create additive abstractions for these testbeds and show experimentally that well chosen additive abstractions can reduce search time substantially for the (18,4)-TopSpin puzzle and by three orders of magnitude over state of the art methods for the 17-Pancake puzzle. We also derive a way of testing if the heuristic value returned by additive abstractions is provably too low and show that the use of this test can reduce search time for the 15-puzzle and TopSpin by roughly a factor of two. ---------------------------------------------------------------- II. Unsubscribing from our Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed at isi.edu. From www-data@booberry.fetch.com Wed Sep 17 09:10:40 2008 Received: from fetch.com (mail.fetch.com [12.157.138.12]) by gamma.isi.edu (8.13.8/8.13.8) with ESMTP id m8HG7IXr028744 for ; Wed, 17 Sep 2008 09:07:19 -0700 (PDT) Received: from booberry.fetch.local ([192.168.219.143]) by fetch.com with Microsoft SMTPSVC(6.0.3790.1830); Wed, 17 Sep 2008 09:08:54 -0700 Received: from www-data by booberry.fetch.local with local (Exim 4.60) (envelope-from ) id 1KfzYj-0000SE-6q; Wed, 17 Sep 2008 16:07:17 +0000 To: jairsubscribers@mailman.isi.edu MIME-Version: 1.0 X-Mailer: htmlMimeMail5 From: jair-ed@ISI.EDU Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit Message-ID: Date: Wed, 17 Sep 2008 16:07:17 +0000 X-OriginalArrivalTime: 17 Sep 2008 16:08:54.0703 (UTC) FILETIME=[AED973F0:01C918DF] X-TM-AS-Product-Ver: SMEX-7.5.0.1243-5.5.1027-16164.000 X-TM-AS-Result: No--5.189400-5.000000-31 X-TM-AS-User-Approved-Sender: No X-TM-AS-User-Blocked-Sender: No X-ISI-4-43-8-MailScanner: Found to be clean X-MailScanner-From: www-data@booberry.fetch.com Cc: jair-ed@ISI.EDU Subject: [Jairsubscribers] 8 new articles published by JAIR X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.6 Precedence: list Reply-To: jair-ed@isi.edu List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 17 Sep 2008 16:10:41 -0000 Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see instructions at the end of this message.) ---------------------------------------------------------------- I. New JAIR Articles S. Ross, J. Pineau, S. Paquet and B. Chaib-draa (2008) "Online Planning Algorithms for POMDPs", Volume 32, pages 663-704 For quick access go to Abstract: Partially Observable Markov Decision Processes (POMDPs) provide a rich framework for sequential decision-making under uncertainty in stochastic domains. However, solving a POMDP is often intractable except for small problems due to their complexity. Here, we focus on online approaches that alleviate the computational complexity by computing good local policies at each decision step during the execution. Online algorithms generally consist of a lookahead search to find the best action to execute at each time step in an environment. Our objectives here are to survey the various existing online POMDP methods, analyze their properties and discuss their advantages and disadvantages; and to thoroughly evaluate these online approaches in different environments under various metrics (return, error bound reduction, lower bound improvement). Our experimental results indicate that state-of-the-art online heuristic search methods can handle large POMDP domains efficiently. A. Petcu, B. Faltings and D. C. Parkes (2008) "M-DPOP: Faithful Distributed Implementation of Efficient Social Choice Problems", Volume 32, pages 705-755 For quick access go to Abstract: In the efficient social choice problem, the goal is to assign values, subject to side constraints, to a set of variables to maximize the total utility across a population of agents, where each agent has private information about its utility function. In this paper we model the social choice problem as a distributed constraint optimization problem (DCOP), in which each agent can communicate with other agents that share an interest in one or more variables. Whereas existing DCOP algorithms can be easily manipulated by an agent, either by misreporting private information or deviating from the algorithm, we introduce M-DPOP, the first DCOP algorithm that provides a faithful distributed implementation for efficient social choice. This provides a concrete example of how the methods of mechanism design can be unified with those of distributed optimization. Faithfulness ensures that no agent can benefit by unilaterally deviating from any aspect of the protocol, neither information-revelation, computation, nor communication, and whatever the private information of other agents. We allow for payments by agents to a central bank, which is the only central authoritythat we require. To achieve faithfulness, we carefully integrate the Vickrey-Clarke-Groves (VCG) mechanism with the DPOP algorithm, such that each agent is only asked to perform computation, report information, and send messages that is in its own best interest. Determining agent i's payment requires solving the social choice problem without agent i. Here, we present a method to reuse computation performed in solving the main problem in a way that is robust against manipulation by the excluded agent. Experimental results on structured problems show that as much as 87% of the computation required for solving the marginal problems can be avoided by re-use, providing very good scalability in the number of agents. On unstructured problems, we observe a sensitivity of M-DPOP to the density of the problem, and we show that reusability decreases from almost 100% for very sparse problems to around 20% for highly connected problems. We close with a discussion of the features of DCOP that enable faithful implementations in this problem, the challenge of reusing computation from the main problem to marginal problems in other algorithms such as ADOPT and OptAPO, and the prospect of methods to avoid the welfare loss that can occur because of the transfer of payments to the bank. J. Delgrande, Y. Jin and F. J. Pelletier (2008) "Compositional Belief Update", Volume 32, pages 757-791 For quick access go to Abstract: In this paper we explore a class of belief update operators, in which the definition of the operator is compositional with respect to the sentence to be added. The goal is to provide an update operator that is intuitive, in that its definition is based on a recursive decomposition of the update sentence's structure, and that may be reasonably implemented. In addressing update, we first provide a definition phrased in terms of the models of a knowledge base. While this operator satisfies a core group of the benchmark Katsuno-Mendelzon update postulates, not all of the postulates are satisfied. Other Katsuno-Mendelzon postulates can be obtained by suitably restricting the syntactic form of the sentence for update, as we show. In restricting the syntactic form of the sentence for update, we also obtain a hierarchy of update operators with Winslett's standard semantics as the most basic interesting approach captured. We subsequently give an algorithm which captures this approach; in the general case the algorithm is exponential, but with some not-unreasonable assumptions we obtain an algorithm that is linear in the size of the knowledge base. Hence the resulting approach has much better complexity characteristics than other operators in some situations. We also explore other compositional belief change operators: erasure is developed as a dual operator to update; we show that a forget operator is definable in terms of update; and we give a definition of the compositional revision operator. We obtain that compositional revision, under the most natural definition, yields the Satoh revision operator. L. Miclet, S. Bayoudh and A. Delhay (2008) "Analogical Dissimilarity: Definition, Algorithms and Two Experiments in Machine Learning", Volume 32, pages 793-824 For quick access go to Abstract: This paper defines the notion of analogical dissimilarity between four objects, with a special focus on objects structured as sequences. Firstly, it studies the case where the four objects have a null analogical dissimilarity, i.e. are in analogical proportion. Secondly, when one of these objects is unknown, it gives algorithms to compute it. Thirdly, it tackles the problem of defining analogical dissimilarity, which is a measure of how far four objects are from being in analogical proportion. In particular, when objects are sequences, it gives a definition and an algorithm based on an optimal alignment of the four sequences. It gives also learning algorithms, i.e. methods to find the triple of objects in a learning sample which has the least analogical dissimilarity with a given object. Two practical experiments are described: the first is a classification problem on benchmarks of binary and nominal data, the second shows how the generation of sequences by solving analogical equations enables a handwritten character recognition system to rapidly be adapted to a new writer. G. M. Coghill, A. Srinivasan and R. D. King (2008) "Qualitative System Identification from Imperfect Data", Volume 32, pages 825-877 For quick access go to Abstract: Experience in the physical sciences suggests that the only realistic means of understanding complex systems is through the use of mathematical models. Typically, this has come to mean the identification of quantitative models expressed as differential equations. Quantitative modelling works best when the structure of the model (i.e., the form of the equations) is known; and the primary concern is one of estimating the values of the parameters in the model. For complex biological systems, the model-structure is rarely known and the modeler has to deal with both model-identification and parameter-estimation. In this paper we are concerned with providing automated assistance to the first of these problems. Specifically, we examine the identification by machine of the structural relationships between experimentally observed variables. These relationship will be expressed in the form of qualitative abstractions of a quantitative model. Such qualitative models may not only provide clues to the precise quantitative model, but also assist in understanding the essence of that model. Our position in this paper is that background knowledge incorporating system modelling principles can be used to constrain effectively the set of good qualitative models. Utilising the model-identification framework provided by Inductive Logic Programming (ILP) we present empirical support for this position using a series of increasingly complex artificial datasets. The results are obtained with qualitative and quantitative data subject to varying amounts of noise and different degrees of sparsity. The results also point to the presence of a set of qualitative states, which we term kernel subsets, that may be necessary for a qualitative model-learner to learn correct models. We demonstrate scalability of the method to biological system modelling by identification of the glycolysis metabolic pathway from data. Y. Wang, N. L. Zhang and T. Chen (2008) "Latent Tree Models and Approximate Inference in Bayesian Networks", Volume 32, pages 879-900 For quick access go to Abstract: We propose a novel method for approximate inference in Bayesian networks (BNs). The idea is to sample data from a BN, learn a latent tree model (LTM) from the data offline, and when online, make inference with the LTM instead of the original BN. Because LTMs are tree-structured, inference takes linear time. In the meantime, they can represent complex relationship among leaf nodes and hence the approximation accuracy is often good. Empirical evidence shows that our method can achieve good approximation accuracy at low online computational cost. N. C. A. Moore and P. Prosser (2008) "The Ultrametric Constraint and its Application to Phylogenetics", Volume 32, pages 901-938 For quick access go to Abstract: A phylogenetic tree shows the evolutionary relationships among species. Internal nodes of the tree represent speciation events and leaf nodes correspond to species. A goal of phylogenetics is to combine such trees into larger trees, called supertrees, whilst respecting the relationships in the original trees. A rooted tree exhibits an ultrametric property; that is, for any three leaves of the tree it must be that one pair has a deeper most recent common ancestor than the other pairs, or that all three have the same most recent common ancestor. This inspires a constraint programming encoding for rooted trees. We present an efficient constraint that enforces the ultrametric property over a symmetric array of constrained integer variables, with the inevitable property that the lower bounds of any three variables are mutually supportive. We show that this allows an efficient constraint-based solution to the supertree construction problem. We demonstrate that the versatility of constraint programming can be exploited to allow solutions to variants of the supertree construction problem. E. H. Gerding, R. K. Dash, A. Byde and N. R. Jennings (2008) "Optimal Strategies for Simultaneous Vickrey Auctions with Perfect Substitutes", Volume 32, pages 939-982 For quick access go to Abstract: We derive optimal strategies for a bidding agent that participates in multiple, simultaneous second-price auctions with perfect substitutes. We prove that, if everyone else bids locally in a single auction, the global bidder should always place non-zero bids in all available auctions, provided there are no budget constraints. With a budget, however, the optimal strategy is to bid locally if this budget is equal or less than the valuation. Furthermore, for a wide range of valuation distributions, we prove that the problem of finding the optimal bids reduces to two dimensions if all auctions are identical. Finally, we address markets with both sequential and simultaneous auctions, non-identical auctions, and the allocative efficiency of the market. ---------------------------------------------------------------- II. Unsubscribing from our Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed at isi.edu. ---------------------------------------------------------------- From www-data@booberry.fetch.com Wed Oct 1 10:42:55 2008 Received: from fetch.com (mail.fetch.com [12.157.138.12]) by gamma.isi.edu (8.13.8/8.13.8) with ESMTP id m91HfCZb028277 for ; Wed, 1 Oct 2008 10:41:13 -0700 (PDT) Received: from booberry.fetch.local ([192.168.219.143]) by fetch.com with Microsoft SMTPSVC(6.0.3790.1830); Wed, 1 Oct 2008 10:42:59 -0700 Received: from www-data by booberry.fetch.local with local (Exim 4.69) (envelope-from ) id 1Kl5hH-0001II-Nm; Wed, 01 Oct 2008 17:41:11 +0000 To: jairsubscribers@mailman.isi.edu MIME-Version: 1.0 X-Mailer: htmlMimeMail5 From: jair-ed@ISI.EDU Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit Message-ID: Date: Wed, 01 Oct 2008 17:41:11 +0000 X-OriginalArrivalTime: 01 Oct 2008 17:42:59.0750 (UTC) FILETIME=[2557C460:01C923ED] X-TM-AS-Product-Ver: SMEX-7.5.0.1243-5.5.1027-16192.000 X-TM-AS-Result: No-3.609600-5.000000-31 X-TM-AS-User-Approved-Sender: No X-TM-AS-User-Blocked-Sender: No X-ISI-4-43-8-MailScanner: Found to be clean X-MailScanner-From: www-data@booberry.fetch.com Cc: jair-ed@ISI.EDU Subject: [Jairsubscribers] 5 new articles published by JAIR X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.6 Precedence: list Reply-To: jair-ed@isi.edu List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 01 Oct 2008 17:42:58 -0000 Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see instructions at the end of this message.) ---------------------------------------------------------------- I. New JAIR Articles S. Esmeir and S. Markovitch (2008) "Anytime Induction of Low-cost, Low-error Classifiers: a Sampling-based Approach", Volume 33, pages 1-31 For quick access go to Abstract: Machine learning techniques are gaining prevalence in the production of a wide range of classifiers for complex real-world applications with nonuniform testing and misclassification costs. The increasing complexity of these applications poses a real challenge to resource management during learning and classification. In this work we introduce ACT (anytime cost-sensitive tree learner), a novel framework for operating in such complex environments. ACT is an anytime algorithm that allows learning time to be increased in return for lower classification costs. It builds a tree top-down and exploits additional time resources to obtain better estimations for the utility of the different candidate splits. Using sampling techniques, ACT approximates the cost of the subtree under each candidate split and favors the one with a minimal cost. As a stochastic algorithm, ACT is expected to be able to escape local minima, into which greedy methods may be trapped. Experiments with a variety of datasets were conducted to compare ACT to the state-of-the-art cost-sensitive tree learners. The results show that for the majority of domains ACT produces significantly less costly trees. ACT also exhibits good anytime behavior with diminishing returns. B. Lubin, A. I. Juda, R. Cavallo, S. Lahaie, J. Shneidman and D. C. Parkes (2008) "ICE: An Expressive Iterative Combinatorial Exchange", Volume 33, pages 33-77 For quick access go to Abstract: We present the design and analysis of the first fully expressive, iterative combinatorial exchange (ICE). The exchange incorporates a tree-based bidding language (TBBL) that is concise and expressive for CEs. Bidders specify lower and upper bounds in TBBL on their value for different trades and refine these bounds across rounds. These bounds allow price discovery and useful preference elicitation in early rounds, and allow termination with an efficient trade despite partial information on bidder valuations. All computation in the exchange is carefully optimized to exploit the structure of the bid-trees and to avoid enumerating trades. A proxied interpretation of a revealed-preference activity rule, coupled with simple linear prices, ensures progress across rounds. The exchange is fully implemented, and we give results demonstrating several aspects of its scalability and economic properties with simulated bidding strategies. D. Martinez, O. Lopez de Lacalle and E. Agirre (2008) "On the Use of Automatically Acquired Examples for All-Nouns Word Sense Disambiguation ", Volume 33, pages 79-107 For quick access go to Abstract: This article focuses on Word Sense Disambiguation (WSD), which is a Natural Language Processing task that is thought to be important for many Language Technology applications, such as Information Retrieval, Information Extraction, or Machine Translation. One of the main issues preventing the deployment of WSD technology is the lack of training examples for Machine Learning systems, also known as the Knowledge Acquisition Bottleneck. A method which has been shown to work for small samples of words is the automatic acquisition of examples. We have previously shown that one of the most promising example acquisition methods scales up and produces a freely available database of 150 million examples from Web snippets for all polysemous nouns in WordNet. This paper focuses on the issues that arise when using those examples, all alone or in addition to manually tagged examples, to train a supervised WSD system for all nouns. The extensive evaluation on both lexical-sample and all-words Senseval benchmarks shows that we are able to improve over commonly used baselines and to achieve top-rank performance. The good use of the prior distributions from the senses proved to be a crucial factor. Y. Gal and A. Pfeffer (2008) "Networks of Influence Diagrams: A Formalism for Representing Agents' Beliefs and Decision-Making Processes", Volume 33, pages 109-147 For quick access go to Abstract: This paper presents Networks of Influence Diagrams (NID), a compact, natural and highly expressive language for reasoning about agents' beliefs and decision-making processes. NIDs are graphical structures in which agents' mental models are represented as nodes in a network; a mental model for an agent may itself use descriptions of the mental models of other agents. NIDs are demonstrated by examples, showing how they can be used to describe conflicting and cyclic belief structures, and certain forms of bounded rationality. In an opponent modeling domain, NIDs were able to outperform other computational agents whose strategies were not known in advance. NIDs are equivalent in representation to Bayesian games but they are more compact and structured than this formalism. In particular, the equilibrium definition for NIDs makes an explicit distinction between agents' optimal strategies, and how they actually behave in reality. R. Meir, A. D. Procaccia, J. S. Rosenschein and Aviv Zohar (2008) "Complexity of Strategic Behavior in Multi-Winner Elections", Volume 33, pages 149-178 For quick access go to Abstract: Although recent years have seen a surge of interest in the computational aspects of social choice, no specific attention has previously been devoted to elections with multiple winners, e.g., elections of an assembly or committee. In this paper, we characterize the worst-case complexity of manipulation and control in the context of four prominent multi-winner voting systems, under different formulations of the strategic agent’s goal. ---------------------------------------------------------------- II. Unsubscribing from our Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed at isi.edu. ---------------------------------------------------------------- From www-data@booberry.fetch.com Sun Nov 30 15:46:12 2008 Received: from fetch.com (mail.fetch.com [12.157.138.12]) by gamma.isi.edu (8.13.8/8.13.8) with ESMTP id mAUNjrgD022267 for ; Sun, 30 Nov 2008 15:45:54 -0800 (PST) Received: from booberry.fetch.local ([192.168.219.143]) by fetch.com with Microsoft SMTPSVC(6.0.3790.1830); Sun, 30 Nov 2008 15:45:52 -0800 Received: from www-data by booberry.fetch.local with local (Exim 4.69) (envelope-from ) id 1L6vz6-0004sq-76; Sun, 30 Nov 2008 23:45:52 +0000 To: jairsubscribers@mailman.isi.edu MIME-Version: 1.0 X-Mailer: htmlMimeMail5 From: jair-ed@ISI.EDU Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit Message-ID: Date: Sun, 30 Nov 2008 23:45:52 +0000 X-OriginalArrivalTime: 30 Nov 2008 23:45:52.0358 (UTC) FILETIME=[C79D1860:01C95345] X-TM-AS-Product-Ver: SMEX-7.5.0.1243-5.5.1027-16250.004 X-TM-AS-Result: No--6.615200-5.000000-31 X-TM-AS-User-Approved-Sender: No X-TM-AS-User-Blocked-Sender: No X-ISI-4-43-8-MailScanner: Found to be clean X-MailScanner-From: www-data@booberry.fetch.com Cc: jair-ed@ISI.EDU Subject: [Jairsubscribers] 8 new articles published by JAIR (Sept-Oct 2008) X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.6 Precedence: list Reply-To: jair-ed@isi.edu List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 30 Nov 2008 23:46:13 -0000 Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see instructions at the end of this message.) ---------------------------------------------------------------- I. New JAIR Articles S. Esmeir and S. Markovitch (2008) "Anytime Induction of Low-cost, Low-error Classifiers: a Sampling-based Approach", Volume 33, pages 1-31 For quick access go to Abstract: Machine learning techniques are gaining prevalence in the production of a wide range of classifiers for complex real-world applications with nonuniform testing and misclassification costs. The increasing complexity of these applications poses a real challenge to resource management during learning and classification. In this work we introduce ACT (anytime cost-sensitive tree learner), a novel framework for operating in such complex environments. ACT is an anytime algorithm that allows learning time to be increased in return for lower classification costs. It builds a tree top-down and exploits additional time resources to obtain better estimations for the utility of the different candidate splits. Using sampling techniques, ACT approximates the cost of the subtree under each candidate split and favors the one with a minimal cost. As a stochastic algorithm, ACT is expected to be able to escape local minima, into which greedy methods may be trapped. Experiments with a variety of datasets were conducted to compare ACT to the state-of-the-art cost-sensitive tree learners. The results show that for the majority of domains ACT produces significantly less costly trees. ACT also exhibits good anytime behavior with diminishing returns. B. Lubin, A. I. Juda, R. Cavallo, S. Lahaie, J. Shneidman and D. C. Parkes (2008) "ICE: An Expressive Iterative Combinatorial Exchange", Volume 33, pages 33-77 For quick access go to Abstract: We present the design and analysis of the first fully expressive, iterative combinatorial exchange (ICE). The exchange incorporates a tree-based bidding language (TBBL) that is concise and expressive for CEs. Bidders specify lower and upper bounds in TBBL on their value for different trades and refine these bounds across rounds. These bounds allow price discovery and useful preference elicitation in early rounds, and allow termination with an efficient trade despite partial information on bidder valuations. All computation in the exchange is carefully optimized to exploit the structure of the bid-trees and to avoid enumerating trades. A proxied interpretation of a revealed-preference activity rule, coupled with simple linear prices, ensures progress across rounds. The exchange is fully implemented, and we give results demonstrating several aspects of its scalability and economic properties with simulated bidding strategies. D. Martinez, O. Lopez de Lacalle and E. Agirre (2008) "On the Use of Automatically Acquired Examples for All-Nouns Word Sense Disambiguation ", Volume 33, pages 79-107 For quick access go to Abstract: This article focuses on Word Sense Disambiguation (WSD), which is a Natural Language Processing task that is thought to be important for many Language Technology applications, such as Information Retrieval, Information Extraction, or Machine Translation. One of the main issues preventing the deployment of WSD technology is the lack of training examples for Machine Learning systems, also known as the Knowledge Acquisition Bottleneck. A method which has been shown to work for small samples of words is the automatic acquisition of examples. We have previously shown that one of the most promising example acquisition methods scales up and produces a freely available database of 150 million examples from Web snippets for all polysemous nouns in WordNet. This paper focuses on the issues that arise when using those examples, all alone or in addition to manually tagged examples, to train a supervised WSD system for all nouns. The extensive evaluation on both lexical-sample and all-words Senseval benchmarks shows that we are able to improve over commonly used baselines and to achieve top-rank performance. The good use of the prior distributions from the senses proved to be a crucial factor. Y. Gal and A. Pfeffer (2008) "Networks of Influence Diagrams: A Formalism for Representing Agents' Beliefs and Decision-Making Processes", Volume 33, pages 109-147 For quick access go to Abstract: This paper presents Networks of Influence Diagrams (NID), a compact, natural and highly expressive language for reasoning about agents' beliefs and decision-making processes. NIDs are graphical structures in which agents' mental models are represented as nodes in a network; a mental model for an agent may itself use descriptions of the mental models of other agents. NIDs are demonstrated by examples, showing how they can be used to describe conflicting and cyclic belief structures, and certain forms of bounded rationality. In an opponent modeling domain, NIDs were able to outperform other computational agents whose strategies were not known in advance. NIDs are equivalent in representation to Bayesian games but they are more compact and structured than this formalism. In particular, the equilibrium definition for NIDs makes an explicit distinction between agents' optimal strategies, and how they actually behave in reality. R. Meir, A. D. Procaccia, J. S. Rosenschein and Aviv Zohar (2008) "Complexity of Strategic Behavior in Multi-Winner Elections", Volume 33, pages 149-178 For quick access go to Abstract: Although recent years have seen a surge of interest in the computational aspects of social choice, no specific attention has previously been devoted to elections with multiple winners, e.g., elections of an assembly or committee. In this paper, we characterize the worst-case complexity of manipulation and control in the context of four prominent multi-winner voting systems, under different formulations of the strategic agent’s goal. T. De Laet, J. De Schutter and H. Bruyninckx (2008) "A Rigorously Bayesian Beam Model and an Adaptive Full Scan Model for Range Finders in Dynamic Environments", Volume 33, pages 179-222 For quick access go to Abstract: This paper proposes and experimentally validates a Bayesian network model of a range finder adapted to dynamic environments. All modeling assumptions are rigorously explained, and all model parameters have a physical interpretation. This approach results in a transparent and intuitive model. With respect to the state of the art beam model this paper: (i) proposes a different functional form for the probability of range measurements caused by unmodeled objects, (ii) intuitively explains the discontinuity encountered in te state of the art beam model, and (iii) reduces the number of model parameters, while maintaining the same representational power for experimental data. The proposed beam model is called RBBM, short for Rigorously Bayesian Beam Model. A maximum likelihood and a variational Bayesian estimator (both based on expectation-maximization) are proposed to learn the model parameters. Furthermore, the RBBM is extended to a full scan model in two steps: first, to a full scan model for static environments and next, to a full scan model for general, dynamic environments. The full scan model accounts for the dependency between beams and adapts to the local sample density when using a particle filter. In contrast to Gaussian-based state of the art models, the proposed full scan model uses a sample-based approximation. This sample-based approximation enables handling dynamic environments and capturing multi-modality, which occurs even in simple static environments. T. Grinshpoun and A. Meisels (2008) "Completeness and Performance Of The APO Algorithm", Volume 33, pages 223-258 For quick access go to Abstract: Asynchronous Partial Overlay (APO) is a search algorithm that uses cooperative mediation to solve Distributed Constraint Satisfaction Problems (DisCSPs). The algorithm partitions the search into different subproblems of the DisCSP. The original proof of completeness of the APO algorithm is based on the growth of the size of the subproblems. The present paper demonstrates that this expected growth of subproblems does not occur in some situations, leading to a termination problem of the algorithm. The problematic parts in the APO algorithm that interfere with its completeness are identified and necessary modifications to the algorithm that fix these problematic parts are given. The resulting version of the algorithm, Complete Asynchronous Partial Overlay (CompAPO), ensures its completeness. Formal proofs for the soundness and completeness of CompAPO are given. A detailed performance evaluation of CompAPO comparing it to other DisCSP algorithms is presented, along with an extensive experimental evaluation of the algorithm’s unique behavior. Additionally, an optimization version of the algorithm, CompOptAPO, is presented, discussed, and evaluated. I. Rezek, D. S. Leslie, S. Reece, S. J. Roberts, A. Rogers, R. K. Dash and N. R. Jennings (2008) "On Similarities between Inference in Game Theory and Machine Learning", Volume 33, pages 259-283 For quick access go to Abstract: In this paper, we elucidate the equivalence between inference in game theory and machine learning. Our aim in so doing is to establish an equivalent vocabulary between the two domains so as to facilitate developments at the intersection of both fields, and as proof of the usefulness of this approach, we use recent developments in each field to make useful improvements to the other. More specifically, we consider the analogies between smooth best responses in fictitious play and Bayesian inference methods. Initially, we use these insights to develop and demonstrate an improved algorithm for learning in games based on probabilistic moderation. That is, by integrating over the distribution of opponent strategies (a Bayesian approach within machine learning) rather than taking a simple empirical average (the approach used in standard fictitious play) we derive a novel moderated fictitious play algorithm and show that it is more likely than standard fictitious play to converge to a payoff-dominant but risk-dominated Nash equilibrium in a simple coordination game. Furthermore we consider the converse case, and show how insights from game theory can be used to derive two improved mean field variational learning algorithms. We first show that the standard update rule of mean field variational learning is analogous to a Cournot adjustment within game theory. By analogy with fictitious play, we then suggest an improved update rule, and show that this results in fictitious variational play, an improved mean field variational learning algorithm that exhibits better convergence in highly or strongly connected graphical models. Second, we use a recent advance in fictitious play, namely dynamic fictitious play, to derive a derivative action variational learning algorithm, that exhibits superior convergence properties on a canonical machine learning problem (clustering a mixture distribution). ---------------------------------------------------------------- II. Unsubscribing from our Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed at isi.edu. ---------------------------------------------------------------- From www-data@booberry.fetch.com Fri Jan 23 10:03:14 2009 Received: from booberry.fetch.local ([12.157.138.143]) by gamma.isi.edu (8.13.8/8.13.8) with ESMTP id n0NI2qOs023114 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT) for ; Fri, 23 Jan 2009 10:02:54 -0800 (PST) Received: from www-data by booberry.fetch.local with local (Exim 4.69) (envelope-from ) id 1LQQMm-0006hJ-48; Fri, 23 Jan 2009 10:02:52 -0800 To: jairsubscribers@mailman.isi.edu MIME-Version: 1.0 X-Mailer: htmlMimeMail5 From: jair-ed@ISI.EDU Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit Message-ID: Date: Fri, 23 Jan 2009 10:02:52 -0800 X-ISI-4-43-8-MailScanner: Found to be clean X-MailScanner-From: www-data@booberry.fetch.com Cc: jair-ed@ISI.EDU Subject: [Jairsubscribers] 9 new articles published by JAIR (Nov - Dec 2008) X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.6 Precedence: list Reply-To: jair-ed@isi.edu List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 23 Jan 2009 18:03:15 -0000 Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see instructions at the end of this message.) ---------------------------------------------------------------- I. New JAIR Articles A. Kakas, P. Mancarella, F. Sadri, K. Stathis and F. Toni (2008) "Computational Logic Foundations of KGP Agents", Volume 33, pages 285-348 For quick access go to Abstract: This paper presents the computational logic foundations of a model of agency called the KGP (Knowledge, Goals and Plan model. This model allows the specification of heterogeneous agents that can interact with each other, and can exhibit both proactive and reactive behaviour allowing them to function in dynamic environments by adjusting their goals and plans when changes happen in such environments. KGP provides a highly modular agent architecture that integrates a collection of reasoning and physical capabilities, synthesised within transitions that update the agent's state in response to reasoning, sensing and acting. Transitions are orchestrated by cycle theories that specify the order in which transitions are executed while taking into account the dynamic context and agent preferences, as well as selection operators for providing inputs to transitions. E. Amir and A. Chang (2008) "Learning Partially Observable Deterministic Action Models", Volume 33, pages 349-402 For quick access go to Abstract: We present exact algorithms for identifying deterministic-actions' effects and preconditions in dynamic partially observable domains. They apply when one does not know the action model(the way actions affect the world) of a domain and must learn it from partial observations over time. Such scenarios are common in real world applications. They are challenging for AI tasks because traditional domain structures that underly tractability (e.g., conditional independence) fail there (e.g., world features become correlated). Our work departs from traditional assumptions about partial observations and action models. In particular, it focuses on problems in which actions are deterministic of simple logical structure and observation models have all features observed with some frequency. We yield tractable algorithms for the modified problem for such domains. Our algorithms take sequences of partial observations over time as input, and output deterministic action models that could have lead to those observations. The algorithms output all or one of those models (depending on our choice), and are exact in that no model is misclassified given the observations. Our algorithms take polynomial time in the number of time steps and state features for some traditional action classes examined in the AI-planning literature, e.g., STRIPS actions. In contrast, traditional approaches for HMMs and Reinforcement Learning are inexact and exponentially intractable for such domains. Our experiments verify the theoretical tractability guarantees, and show that we identify action models exactly. Several applications in planning, autonomous exploration, and adventure-game playing already use these results. They are also promising for probabilistic settings, partially observable reinforcement learning, and diagnosis. J. Goldsmith, J. Lang, M. Truszczynski and N. Wilson (2008) "The Computational Complexity of Dominance and Consistency in CP-Nets", Volume 33, pages 403-432 For quick access go to Abstract: We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas. D. Zhang and Y. Zhang (2008) "An Ordinal Bargaining Solution with Fixed-Point Property", Volume 33, pages 433-464 For quick access go to Abstract: Shapley's impossibility result indicates that the two-person bargaining problem has no non-trivial ordinal solution with the traditional game-theoretic bargaining model. Although the result is no longer true for bargaining problems with more than two agents, none of the well known bargaining solutions are ordinal. Searching for meaningful ordinal solutions, especially for the bilateral bargaining problem, has been a challenging issue in bargaining theory for more than three decades. This paper proposes a logic-based ordinal solution to the bilateral bargaining problem. We argue that if a bargaining problem is modeled in terms of the logical relation of players' physical negotiation items, a meaningful bargaining solution can be constructed based on the ordinal structure of bargainers' preferences. We represent bargainers' demands in propositional logic and bargainers' preferences over their demands in total preorder. We show that the solution satisfies most desirable logical properties, such as individual rationality (logical version), consistency, collective rationality as well as a few typical game-theoretic properties, such as weak Pareto optimality and contraction invariance. In addition, if all players' demand sets are logically closed, the solution satisfies a fixed-point condition, which says that the outcome of a negotiation is the result of mutual belief revision. Finally, we define various decision problems in relation to our bargaining model and study their computational complexity. R. Mateescu, R. Dechter and R. Marinescu (2008) "AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Graphical Models", Volume 33, pages 465-519 For quick access go to Abstract: Inspired by the recently introduced framework of AND/OR search spaces for graphical models, we propose to augment Multi-Valued Decision Diagrams (MDD) with AND nodes, in order to capture function decomposition structure and to extend these compiled data structures to general weighted graphical models (e.g., probabilistic models). We present the AND/OR Multi-Valued Decision Diagram (AOMDD) which compiles a graphical model into a canonical form that supports polynomial (e.g., solution counting, belief updating) or constant time (e.g. equivalence of graphical models) queries. We provide two algorithms for compiling the AOMDD of a graphical model. The first is search-based, and works by applying reduction rules to the trace of the memory intensive AND/OR search algorithm. The second is inference-based and uses a Bucket Elimination schedule to combine the AOMDDs of the input functions via the the APPLY operator. For both algorithms, the compilation time and the size of the AOMDD are, in the worst case, exponential in the treewidth of the graphical model, rather than pathwidth as is known for ordered binary decision diagrams (OBDDs). We introduce the concept of semantic treewidth, which helps explain why the size of a decision diagram is often much smaller than the worst case bound. We provide an experimental evaluation that demonstrates the potential of AOMDDs. S. Abdallah and V. Lesser (2008) "A Multiagent Reinforcement Learning Algorithm with Non-linear Dynamics", Volume 33, pages 521-549 For quick access go to Abstract: Several multiagent reinforcement learning (MARL) algorithms have been proposed to optimize agents' decisions. Due to the complexity of the problem, the majority of the previously developed MARL algorithms assumed agents either had some knowledge of the underlying game (such as Nash equilibria) and/or observed other agents actions and the rewards they received. We introduce a new MARL algorithm called the Weighted Policy Learner (WPL), which allows agents to reach a Nash Equilibrium (NE) in benchmark 2-player-2-action games with minimum knowledge. Using WPL, the only feedback an agent needs is its own local reward (the agent does not observe other agents actions or rewards). Furthermore, WPL does not assume that agents know the underlying game or the corresponding Nash Equilibrium a priori. We experimentally show that our algorithm converges in benchmark two-player-two-action games. We also show that our algorithm converges in the challenging Shapley's game where previous MARL algorithms failed to converge without knowing the underlying game or the NE. Furthermore, we show that WPL outperforms the state-of-the-art algorithms in a more realistic setting of 100 agents interacting and learning concurrently. An important aspect of understanding the behavior of a MARL algorithm is analyzing the dynamics of the algorithm: how the policies of multiple learning agents evolve over time as agents interact with one another. Such an analysis not only verifies whether agents using a given MARL algorithm will eventually converge, but also reveals the behavior of the MARL algorithm prior to convergence. We analyze our algorithm in two-player-two-action games and show that symbolically proving WPL's convergence is difficult, because of the non-linear nature of WPL's dynamics, unlike previous MARL algorithms that had either linear or piece-wise-linear dynamics. Instead, we numerically solve WPL's dynamics differential equations and compare the solution to the dynamics of previous MARL algorithms. S. de Jong, S. Uyttendaele and K. Tuyls (2008) "Learning to Reach Agreement in a Continuous Ultimatum Game", Volume 33, pages 551-574 For quick access go to Abstract: It is well-known that acting in an individually rational manner, according to the principles of classical game theory, may lead to sub-optimal solutions in a class of problems named social dilemmas. In contrast, humans generally do not have much difficulty with social dilemmas, as they are able to balance personal benefit and group benefit. As agents in multi-agent systems are regularly confronted with social dilemmas, for instance in tasks such as resource allocation, these agents may benefit from the inclusion of mechanisms thought to facilitate human fairness. Although many of such mechanisms have already been implemented in a multi-agent systems context, their application is usually limited to rather abstract social dilemmas with a discrete set of available strategies (usually two). Given that many real-world examples of social dilemmas are actually continuous in nature, we extend this previous work to more general dilemmas, in which agents operate in a continuous strategy space. The social dilemma under study here is the well-known Ultimatum Game, in which an optimal solution is achieved if agents agree on a common strategy. We investigate whether a scale-free interaction network facilitates agents to reach agreement, especially in the presence of fixed-strategy agents that represent a desired (e.g. human) outcome. Moreover, we study the influence of rewiring in the interaction network. The agents are equipped with continuous-action learning automata and play a large number of random pairwise games in order to establish a common strategy. From our experiments, we may conclude that results obtained in discrete-strategy games can be generalized to continuous-strategy games to a certain extent: a scale-free interaction network structure allows agents to achieve agreement on a common strategy, and rewiring in the interaction network greatly enhances the agents' ability to reach agreement. However, it also becomes clear that some alternative mechanisms, such as reputation and volunteering, have many subtleties i nvolved and do not have convincing beneficial effects in the continuous case. I. Ashlagi, D. Monderer and M. Tennenholtz (2008) "On the Value of Correlation", Volume 33, pages 575-613 For quick access go to Abstract: Correlated equilibrium generalizes Nash equilibrium to allow correlation devices. Correlated equilibrium captures the idea that in many systems there exists a trusted administrator who can recommend behavior to a set of agents, but can not enforce such behavior. This makes this solution concept most appropriate to the study of multi-agent systems in AI. Aumann showed an example of a game, and of a correlated equilibrium in this game in which the agents' welfare (expected sum of players' utilities) is greater than their welfare in all mixed-strategy equilibria. Following the idea initiated by the price of anarchy literature this suggests the study of two major measures for the value of correlation in a game with nonnegative payoffs: 1. The ratio between the maximal welfare obtained in a correlated equilibrium to the maximal welfare obtained in a mixed-strategy equilibrium. We refer to this ratio as the mediation value. 2. The ratio between the maximal welfare to the maximal welfare obtained in a correlated equilibrium. We refer to this ratio as the enforcement value. In this work we initiate the study of the mediation and enforcement values, providing several general results on the value of correlation as captured by these concepts. We also present a set of results for the more specialized case of congestion games, a class of games that received a lot of attention in the recent literature. P. D. Turney (2008) "The Latent Relation Mapping Engine: Algorithm and Experiments", Volume 33, pages 615-655 For quick access go to Abstract: Many AI researchers and cognitive scientists have argued that analogy is the core of cognition. The most influential work on computational modeling of analogy-making is Structure Mapping Theory (SMT) and its implementation in the Structure Mapping Engine (SME). A limitation of SME is the requirement for complex hand-coded representations. We introduce the Latent Relation Mapping Engine (LRME), which combines ideas from SME and Latent Relational Analysis (LRA) in order to remove the requirement for hand-coded representations. LRME builds analogical mappings between lists of words, using a large corpus of raw text to automatically discover the semantic relations among the words. We evaluate LRME on a set of twenty analogical mapping problems, ten based on scientific analogies and ten based on common metaphors. LRME achieves human-level performance on the twenty problems. We compare LRME with a variety of alternative approaches and find that they are not able to reach the same level of performance. ---------------------------------------------------------------- II. Unsubscribing from our Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed at isi.edu. ---------------------------------------------------------------- From www-data@booberry.fetch.com Thu Mar 12 17:37:31 2009 Received: from booberry.fetch.local ([12.157.138.143]) by gamma.isi.edu (8.13.8/8.13.8) with ESMTP id n2D0autY005084 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT) for ; Thu, 12 Mar 2009 17:36:57 -0700 (PDT) Received: from www-data by booberry.fetch.local with local (Exim 4.69) (envelope-from ) id 1LhvOR-0002mq-S2; Thu, 12 Mar 2009 17:36:55 -0700 To: jairsubscribers@mailman.isi.edu MIME-Version: 1.0 X-Mailer: htmlMimeMail5 From: jair-ed@ISI.EDU Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit Message-ID: Date: Thu, 12 Mar 2009 17:36:55 -0700 X-ISI-4-43-8-MailScanner: Found to be clean X-MailScanner-From: www-data@booberry.fetch.com Cc: jair-ed@ISI.EDU Subject: [Jairsubscribers] 5 new articles published by JAIR (Jan-March) X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.6 Precedence: list Reply-To: jair-ed@isi.edu List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 13 Mar 2009 00:37:31 -0000 Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see instructions at the end of this message.) ---------------------------------------------------------------- I. New JAIR Articles S. Chernova and M. Veloso (2009) "Interactive Policy Learning through Confidence-Based Autonomy", Volume 34, pages 1-25 For quick access go to Abstract: We present Confidence-Based Autonomy (CBA), an interactive algorithm for policy learning from demonstration. The CBA algorithm consists of two components which take advantage of the complimentary abilities of humans and computer agents. The first component, Confident Execution, enables the agent to identify states in which demonstration is required, to request a demonstration from the human teacher and to learn a policy based on the acquired data. The algorithm selects demonstrations based on a measure of action selection confidence, and our results show that using Confident Execution the agent requires fewer demonstrations to learn the policy than when demonstrations are selected by a human teacher. The second algorithmic component, Corrective Demonstration, enables the teacher to correct any mistakes made by the agent through additional demonstrations in order to improve the policy and future task performance. CBA and its individual components are compared and evaluated in a complex simulated driving domain. The complete CBA algorithm results in the best overall learning performance, successfully reproducing the behavior of the teacher while balancing the tradeoff between number of demonstrations and number of incorrect actions during learning. N. Meuleau, E. Benazera, R. I. Brafman, E. A. Hansen and Mausam (2009) "A Heuristic Search Approach to Planning with Continuous Resources in Stochastic Domains", Volume 34, pages 27-59 For quick access go to Abstract: We consider the problem of optimal planning in stochastic domains with resource constraints, where the resources are continuous and the choice of action at each step depends on resource availability. We introduce the HAO* algorithm, a generalization of the AO* algorithm that performs search in a hybrid state space that is modeled using both discrete and continuous state variables, where the continuous variables represent monotonic resources. Like other heuristic search algorithms, HAO* leverages knowledge of the start state and an admissible heuristic to focus computational effort on those parts of the state space that could be reached from the start state by following an optimal policy. We show that this approach is especially effective when resource constraints limit how much of the state space is reachable. Experimental results demonstrate its effectiveness in the domain that motivates our research: automated planning for planetary exploration rovers. A. Gershman, A. Meisels and R. Zivan (2009) "Asynchronous Forward Bounding for Distributed COPs", Volume 34, pages 61-88 For quick access go to Abstract: A new search algorithm for solving distributed constraint optimization problems (DisCOPs) is presented. Agents assign variables sequentially and compute bounds on partial assignments asynchronously. The asynchronous bounds computation is based on the propagation of partial assignments. The asynchronous forward-bounding algorithm (AFB) is a distributed optimization search algorithm that keeps one consistent partial assignment at all times. The algorithm is described in detail and its correctness proven. Experimental evaluation shows that AFB outperforms synchronous branch and bound by many orders of magnitude, and produces a phase transition as the tightness of the problem increases. This is an analogous effect to the phase transition that has been observed when local consistency maintenance is applied to MaxCSPs. The AFB algorithm is further enhanced by the addition of a backjumping mechanism, resulting in the AFB-BJ algorithm. Distributed backjumping is based on accumulated information on bounds of all values and on processing concurrently a queue of candidate goals for the next move back. The AFB-BJ algorithm is compared experimentally to other DisCOP algorithms (ADOPT, DPOP, OptAPO) and is shown to be a very efficient algorithm for DisCOPs. D. S. Bernstein, C. Amato, E. A. Hansen and S. Zilberstein (2009) "Policy Iteration for Decentralized Control of Markov Decision Processes", Volume 34, pages 89-132 For quick access go to Abstract: Coordination of distributed agents is required for problems arising in many areas, including multi-robot systems, networking and e-commerce. As a formal framework for such problems, we use the decentralized partially observable Markov decision process (DEC-POMDP). Though much work has been done on optimal dynamic programming algorithms for the single-agent version of the problem, optimal algorithms for the multiagent case have been elusive. The main contribution of this paper is an optimal policy iteration algorithm for solving DEC-POMDPs. The algorithm uses stochastic finite-state controllers to represent policies. The solution can include a correlation device, which allows agents to correlate their actions without communicating. This approach alternates between expanding the controller and performing value-preserving transformations, which modify the controller without sacrificing value. We present two efficient value-preserving transformations: one can reduce the size of the controller and the other can improve its value while keeping the size fixed. Empirical results demonstrate the usefulness of value-preserving transformations in increasing value while keeping controller size to a minimum. To broaden the applicability of the approach, we also present a heuristic version of the policy iteration algorithm, which sacrifices convergence to optimality. This algorithm further reduces the size of the controllers at each step by assuming that probability distributions over the other agents' actions are known. While this assumption may not hold in general, it helps produce higher quality solutions in our test problems. M. Binshtok, R. I. Brafman, C. Domshlak and S. E. Shiomony (2009) "Generic Preferences over Subsets of Structured objects", Volume 34, pages 133-164 For quick access go to Abstract: Various tasks in decision making and decision support systems require selecting a preferred subset of a given set of items. Here we focus on problems where the individual items are described using a set of characterizing attributes, and a generic preference specification is required, that is, a specification that can work with an arbitrary set of items. For example, preferences over the content of an online newspaper should have this form: At each viewing, the newspaper contains a subset of the set of articles currently available. Our preference specification over this subset should be provided offline, but we should be able to use it to select a subset of any currently available set of articles, e.g., based on their tags. We present a general approach for lifting formalisms for specifying preferences over objects with multiple attributes into ones that specify preferences over subsets of such objects. We also show how we can compute an optimal subset given such a specification in a relatively efficient manner. We provide an empirical evaluation of the approach as well as some worst-case complexity results. ---------------------------------------------------------------- II. Unsubscribing from our Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed at isi.edu. ---------------------------------------------------------------- From www-data@booberry.fetch.com Mon May 25 21:14:45 2009 Received: from booberry.fetch.local ([12.157.138.143]) by gamma.isi.edu (8.13.8/8.13.8) with ESMTP id n4Q4ETHc008101 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT) for ; Mon, 25 May 2009 21:14:31 -0700 (PDT) Received: from www-data by booberry.fetch.local with local (Exim 4.69) (envelope-from ) id 1M8o3O-0006pn-7P; Mon, 25 May 2009 21:14:18 -0700 To: jairsubscribers@mailman.isi.edu MIME-Version: 1.0 X-Mailer: htmlMimeMail5 From: jair-ed@ISI.EDU Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit Message-ID: Date: Mon, 25 May 2009 21:14:18 -0700 X-ISI-4-43-8-MailScanner: Found to be clean X-MailScanner-From: www-data@booberry.fetch.com Cc: jair-ed@ISI.EDU Subject: [Jairsubscribers] 15 new articles published by JAIR X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.6 Precedence: list Reply-To: jair-ed@isi.edu List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 26 May 2009 04:14:46 -0000 Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see instructions at the end of this message.) ---------------------------------------------------------------- I. New JAIR Articles S. A. Wallace (2009) "Behavior Bounding: An Efficient Method for High-Level Behavior Comparison", Volume 34, pages 165-208 For quick access go to Abstract: In this paper, we explore methods for comparing agent behavior with human behavior to assist with validation. Our exploration begins by considering a simple method of behavior comparison. Motivated by shortcomings in this initial approach, we introduce behavior bounding, an automated model-based approach for comparing behavior that is inspired, in part, by Mitchell’s Version Spaces. We show that behavior bounding can be used to compactly represent both human and agent behavior. We argue that relatively low amounts of human effort are required to build, maintain, and use the data structures that underlie behavior bounding, and we provide a theoretical basis for these arguments using notions of PAC Learnability. Next, we show empirical results indicating that this approach is effective at identifying differences in certain types of behaviors and that it performs well when compared against our initial benchmark methods. Finally, we demonstrate that behavior bounding can produce information that allows developers to identify and fix problems in an agent’s behavior much more efficiently than standard debugging techniques. R. Jurca and B. Faltings (2009) "Mechanisms for Making Crowds Truthful", Volume 34, pages 209-253 For quick access go to Abstract: We consider schemes for obtaining truthful reports on a common but hidden signal from large groups of rational, self-interested agents. One example are online feedback mechanisms, where users provide observations about the quality of a product or service so that other users can have an accurate idea of what quality they can expect. However, (i) providing such feedback is costly, and (ii) there are many motivations for providing incorrect feedback. Both problems can be addressed by reward schemes which (i) cover the cost of obtaining and reporting feedback, and (ii) maximize the expected reward of a rational agent who reports truthfully. We address the design of such incentive-compatible rewards for feedback generated in environments with pure adverse selection. Here, the correlation between the true knowledge of an agent and her beliefs regarding the likelihoods of reports of other agents can be exploited to make honest reporting a Nash equilibrium. In this paper we extend existing methods for designing incentive-compatible rewards by also considering collusion. We analyze different scenarios, where, for example, some or all of the agents collude. For each scenario we investigate whether a collusion-resistant, incentive-compatible reward scheme exists, and use automated mechanism design to specify an algorithm for deriving an efficient reward mechanism. P. Doshi and P. J Gmytrasiewicz (2009) "Monte Carlo Sampling Methods for Approximating Interactive POMDPs", Volume 34, pages 297-337 For quick access go to Abstract: Partially observable Markov decision processes (POMDPs) provide a principled framework for sequential planning in uncertain single agent settings. An extension of POMDPs to multiagent settings, called interactive POMDPs (I-POMDPs), replaces POMDP belief spaces with interactive hierarchical belief systems which represent an agent’s belief about the physical world, about beliefs of other agents, and about their beliefs about others’ beliefs. This modification makes the difficulties of obtaining solutions due to complexity of the belief and policy spaces even more acute. We describe a general method for obtaining approximate solutions of I-POMDPs based on particle filtering (PF). We introduce the interactive PF, which descends the levels of the interactive belief hierarchies and samples and propagates beliefs at each level. The interactive PF is able to mitigate the belief space complexity, but it does not address the policy space complexity. To mitigate the policy space complexity – sometimes also called the curse of history – we utilize a complementary method based on sampling likely observations while building the look ahead reachability tree. While this approach does not completely address the curse of history, it beats back the curse’s impact substantially. We provide experimental results and chart future work. A. Yates and O. Etzioni (2009) "Unsupervised Methods for Determining Object and Relation Synonyms on the Web", Volume 34, pages 255-296 For quick access go to Abstract: The task of identifying synonymous relations and objects, or synonym resolution, is critical for high-quality information extraction. This paper investigates synonym resolution in the context of unsupervised information extraction, where neither hand-tagged training examples nor domain knowledge is available. The paper presents a scalable, fully-implemented system that runs in O(KN log N) time in the number of extractions, N, and the maximum number of synonyms per word, K. The system, called Resolver , introduces a probabilistic relational model for predicting whether two strings are co-referential based on the similarity of the assertions containing them. On a set of two million assertions extracted from the Web, Resolver resolves objects with 78% precision and 68% recall, and resolves relations with 90% precision and 35% recall. Several variations of resolver's probabilistic model are explored, and experiments demonstrate that under appropriate conditions these variations can improve F1 by 5%. An extension to the basic Resolver system allows it to handle polysemous names with 97% precision and 95% recall on a data set from the TREC corpus. Y. Li, P. Musilek, M. Reformat and L. Wyard-Scott (2009) "Identification of Pleonastic It Using the Web", Volume 34, pages 339-389 For quick access go to Abstract: In a significant minority of cases, certain pronouns, especially the pronoun it, can be used without referring to any specific entity. This phenomenon of pleonastic pronoun usage poses serious problems for systems aiming at even a shallow understanding of natural language texts. In this paper, a novel approach is proposed to identify such uses of it: the extrapositional cases are identified using a series of queries against the web, and the cleft cases are identified using a simple set of syntactic rules. The system is evaluated with four sets of news articles containing 679 extrapositional cases as well as 78 cleft constructs. The identification results are comparable to those obtained by human efforts. F. Bacchus, S. Dalmao and T. Pitassi (2009) "Solving #SAT and Bayesian Inference with Backtracking Search", Volume 34, pages 391-442 For quick access go to Abstract: Inference in Bayes Nets (BAYES) is an important problem with numerous applications in probabilistic reasoning. Counting the number of satisfying assignments of a propositional formula (#SAT) is a closely related problem of fundamental theoretical importance. Both these problems, and others, are members of the class of sum-of-products (SUMPROD) problems. In this paper we show that standard backtracking search when augmented with a simple memoization scheme (caching) can solve any sum-of-products problem with time complexity that is at least as good any other state-of-the-art exact algorithm, and that it can also achieve the best known time-space tradeoff. Furthermore, backtracking’s ability to utilize more flexible variable orderings allows us to prove that it can achieve an exponential speedup over other standard algorithms for SUMPROD on some instances. The ideas presented here have been utilized in a number of solvers that have been applied to various types of sum-of-product problems. These system’s have exploited the fact that backtracking can naturally exploit more of the problem’s structure to achieve improved performance on a range of probleminstances. Empirical evidence of this performance gain has appeared in published works describing these solvers, and we provide references to these works. E. Gabrilovich and S. Markovitch (2009) "Wikipedia-based Semantic Interpretation for Natural Language Processing", Volume 34, pages 443-498 For quick access go to Abstract: Adequate representation of natural language semantics requires access to vast amounts of common sense and domain-specific world knowledge. Prior work in the field was based on purely statistical techniques that did not make use of background knowledge, on limited lexicographic knowledge bases such as WordNet, or on huge manual efforts such as the CYC project. Here we propose a novel method, called Explicit Semantic Analysis (ESA), for fine-grained semantic interpretation of unrestricted natural language texts. Our method represents meaning in a high-dimensional space of concepts derived from Wikipedia, the largest encyclopedia in existence. We explicitly represent the meaning of any text in terms of Wikipedia-based concepts. We evaluate the effectiveness of our method on text categorization and on computing the degree of semantic relatedness between fragments of natural language text. Using ESA results in significant improvements over the previous state of the art in both tasks. Importantly, due to the use of natural concepts, the ESA model is easy to explain to human users. V. Ruiz de Angulo and C. Torras (2009) "Exploiting Single-Cycle Symmetries in Continuous Constraint Problems", Volume 34, pages 499-520 For quick access go to Abstract: Symmetries in discrete constraint satisfaction problems have been explored and exploited in the last years, but symmetries in continuous constraint problems have not received the same attention. Here we focus on permutations of the variables consisting of one single cycle. We propose a procedure that takes advantage of these symmetries by interacting with a continuous constraint solver without interfering with it. A key concept in this procedure are the classes of symmetric boxes formed by bisecting a n-dimensional cube at the same point in all dimensions at the same time. We analyze these classes and quantify them as a function of the cube dimensionality. Moreover, we propose a simple algorithm to generate the representatives of all these classes for any number of variables at very high rates. A problem example from the chemical field and the cyclic n-roots problem are used to show the performance of the approach in practice. T. Rahwan, S. D. Ramchurn, N. R. Jennings and A. Giovannucci (2009) "An Anytime Algorithm for Optimal Coalition Structure Generation", Volume 34, pages 521-567 For quick access go to Abstract: Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques ranging from dynamic programming, to integer programming, to stochastic search all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0.175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution. S. R. K. Branavan, H. Chen, J. Eisenstein and R. Barzilay (2009) "Learning Document-Level Semantic Properties from Free-Text Annotations", Volume 34, pages 569-603 For quick access go to Abstract: This paper presents a new method for inferring the semantic properties of documents by leveraging free-text keyphrase annotations. Such annotations are becoming increasingly abundant due to the recent dramatic growth in semi-structured, user-generated online content. One especially relevant domain is product reviews, which are often annotated by their authors with pros/cons keyphrases such as ``a real bargain'' or ``good value.'' These annotations are representative of the underlying semantic properties; however, unlike expert annotations, they are noisy: lay authors may use different labels to denote the same property, and some labels may be missing. To learn using such noisy annotations, we find a hidden paraphrase structure which clusters the keyphrases. The paraphrase structure is linked with a latent topic model of the review texts, enabling the system to predict the properties of unannotated documents and to effectively aggregate the semantic properties of multiple reviews. Our approach is implemented as a hierarchical Bayesian model with joint inference. We find that joint inference increases the robustness of the keyphrase clustering and encourages the latent topics to correlate with semantically meaningful properties. Multiple evaluations demonstrate that our model substantially outperforms alternative approaches for summarizing single and multiple documents into a set of semantically salient keyphrases. F. Sanchez-Martinez and M. L. Forcada (2009) "Inferring Shallow-Transfer Machine Translation Rules from Small Parallel Corpora", Volume 34, pages 605-635 For quick access go to Abstract: This paper describes a method for the automatic inference of structural transfer rules to be used in a shallow-transfer machine translation (MT) system from small parallel corpora. The structural transfer rules are based on alignment templates, like those used in statistical MT. Alignment templates are extracted from sentence-aligned parallel corpora and extended with a set of restrictions which are derived from the bilingual dictionary of the MT system and control their application as transfer rules. The experiments conducted using three different language pairs in the free/open-source MT platform Apertium show that translation quality is improved as compared to word-for-word translation (when no transfer rules are used), and that the resulting translation quality is close to that obtained using hand-coded transfer rules. The method we present is entirely unsupervised and benefits from information in the rest of modules of the MT system in which the inferred rules are applied. T. A. Cohn and M. Lapata (2009) "Sentence Compression as Tree Transduction", Volume 34, pages 637-674 For quick access go to Abstract: This paper presents a tree-to-tree transduction method for sentence compression. Our model is based on synchronous tree substitution grammar, a formalism that allows local distortion of the tree topology and can thus naturally capture structural mismatches. We describe an algorithm for decoding in this framework and show how the model can be trained discriminatively within a large margin framework. Experimental results on sentence compression bring significant improvements over a state-of-the-art model. O. Gimenez and A. Jonsson (2009) "Planning over Chain Causal Graphs for Variables with Domains of Size 5 Is NP-Hard", Volume 34, pages 675-706 For quick access go to Abstract: Recently, considerable focus has been given to the problem of determining the boundary between tractable and intractable planning problems. In this paper, we study the complexity of planning in the class C_n of planning problems, characterized by unary operators and directed path causal graphs. Although this is one of the simplest forms of causal graphs a planning problem can have, we show that planning is intractable for C_n (unless P = NP), even if the domains of state variables have bounded size. In particular, we show that plan existence for C_n^k is NP-hard for k>=5 by reduction from CNFSAT. Here, k denotes the upper bound on the size of the state variable domains. Our result reduces the complexity gap for the class C_n^k to cases k=3 and k=4 only, since C_n^2 is known to be tractable. A. Singh, A. Krause, C. Guestrin and W. J. Kaiser (2009) "Efficient Informative Sensing using Multiple Robots", Volume 34, pages 707-755 For quick access go to Abstract: The need for efficient monitoring of spatio-temporal dynamics in large environmental applications, such as the water quality monitoring in rivers and lakes, motivates the use of robotic sensors in order to achieve sufficient spatial coverage. Typically, these robots have bounded resources, such as limited battery or limited amounts of time to obtain measurements. Thus, careful coordination of their paths is required in order to maximize the amount of information collected, while respecting the resource constraints. In this paper, we present an efficient approach for near-optimally solving the NP-hard optimization problem of planning such informative paths. In particular, we first develop eSIP (efficient Single-robot Informative Path planning), an approximation algorithm for optimizing the path of a single robot. Hereby, we use a Gaussian Process to model the underlying phenomenon, and use the mutual information between the visited locations and remainder of the space to quantify the amount of information collected. We prove that the mutual information collected using paths obtained by using eSIP is close to the information obtained by an optimal solution. We then provide a general technique, sequential allocation, which can be used to extend any single robot planning algorithm, such as eSIP, for the multi-robot problem. This procedure approximately generalizes any guarantees for the single-robot problem to the multi-robot case. We extensively evaluate the effectiveness of our approach on several experiments performed in-field for two important environmental sensing applications, lake and river monitoring, and simulation experiments performed using several real world sensor network data sets. M. Zaffalon and E. Miranda (2009) "Conservative Inference Rule for Uncertain Reasoning under Incompleteness", Volume 34, pages 757-821 For quick access go to Abstract: In this paper we formulate the problem of inference under incomplete information in very general terms. This includes modelling the process responsible for the incompleteness, which we call the incompleteness process. We allow the process' behaviour to be partly unknown. Then we use Walley's theory of coherent lower previsions, a generalisation of the Bayesian theory to imprecision, to derive the rule to update beliefs under incompleteness that logically follows from our assumptions, and that we call conservative inference rule. This rule has some remarkable properties: it is an abstract rule to update beliefs that can be applied in any situation or domain; it gives us the opportunity to be neither too optimistic nor too pessimistic about the incompleteness process, which is a necessary condition to draw reliable while strong enough conclusions; and it is a coherent rule, in the sense that it cannot lead to inconsistencies. We give examples to show how the new rule can be applied in expert systems, in parametric statistical inference, and in pattern classification, and discuss more generally the view of incompleteness processes defended here as well as some of its consequences. ---------------------------------------------------------------- II. Unsubscribing from our Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed at isi.edu. ---------------------------------------------------------------- From www-data@booberry.fetch.com Fri Jul 17 17:11:51 2009 Received: from booberry.fetch.local ([12.157.138.143]) by gamma.isi.edu (8.13.8/8.13.8) with ESMTP id n6I08Btk017267 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT) for ; Fri, 17 Jul 2009 17:08:12 -0700 (PDT) Received: from www-data by booberry.fetch.local with local (Exim 4.69) (envelope-from ) id 1MRxTH-0005kb-BY; Fri, 17 Jul 2009 17:08:11 -0700 To: jairsubscribers@mailman.isi.edu MIME-Version: 1.0 X-Mailer: htmlMimeMail5 From: jair-ed@ISI.EDU Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit Message-ID: Date: Fri, 17 Jul 2009 17:08:11 -0700 X-ISI-4-43-8-MailScanner: Found to be clean X-MailScanner-From: www-data@booberry.fetch.com Cc: jair-ed@ISI.EDU Subject: [Jairsubscribers] 9 new articles published by JAIR X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.6 Precedence: list Reply-To: jair-ed@isi.edu List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 18 Jul 2009 00:11:53 -0000 Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see instructions at the end of this message.) ---------------------------------------------------------------- I. New JAIR Articles Y. Chali, S. R. Joty and S. A. Hasan (2009) "Complex Question Answering: Unsupervised Learning Approaches and Experiments", Volume 35, pages 1-47 For quick access go to Abstract: Complex questions that require inferencing and synthesizing information from multiple documents can be seen as a kind of topic-oriented, informative multi-document summarization where the goal is to produce a single text as a compressed version of a set of documents with a minimum loss of relevant information. In this paper, we experiment with one empirical method and two unsupervised statistical machine learning techniques: K-means and Expectation Maximization (EM), for computing relative importance of the sentences. We compare the results of these approaches. Our experiments show that the empirical approach outperforms the other two techniques and EM performs better than K-means. However, the performance of these approaches depends entirely on the feature set used and the weighting of these features. In order to measure the importance and relevance to the user query we extract different kinds of features (i.e. lexical, lexical semantic, cosine similarity, basic element, tree kernel based syntactic and shallow-semantic) for each of the document sentences. We use a local search technique to learn the weights of the features. To the best of our knowledge, no study has used tree kernel functions to encode syntactic/semantic information for more complex tasks such as computing the relatedness between the query sentences and the document sentences in order to generate query-focused summaries (or answers to complex questions). For each of our methods of generating summaries (i.e. empirical, K-means and EM) we show the effects of syntactic and shallow-semantic features over the bag-of-words (BOW) features. J. Hoffmann, P. Bertoli, M. Helmert and M. Pistore (2009) "Message-Based Web Service Composition, Integrity Constraints, and Planning under Uncertainty: A New Connection", Volume 35, pages 49-117 For quick access go to Abstract: Thanks to recent advances, AI Planning has become the underlying technique for several applications. Figuring prominently among these is automated Web Service Composition (WSC) at the "capability" level, where services are described in terms of preconditions and effects over ontological concepts. A key issue in addressing WSC as planning is that ontologies are not only formal vocabularies; they also axiomatize the possible relationships between concepts. Such axioms correspond to what has been termed "integrity constraints" in the actions and change literature, and applying a web service is essentially a belief update operation. The reasoning required for belief update is known to be harder than reasoning in the ontology itself. The support for belief update is severely limited in current planning tools. Our first contribution consists in identifying an interesting special case of WSC which is both significant and more tractable. The special case, which we term "forward effects", is characterized by the fact that every ramification of a web service application involves at least one new constant generated as output by the web service. We show that, in this setting, the reasoning required for belief update simplifies to standard reasoning in the ontology itself. This relates to, and extends, current notions of "message-based" WSC, where the need for belief update is removed by a strong (often implicit or informal) assumption of "locality" of the individual messages. We clarify the computational properties of the forward effects case, and point out a strong relation to standard notions of planning under uncertainty, suggesting that effective tools for the latter can be successfully adapted to address the former. Furthermore, we identify a significant sub-case, named "strictly forward effects", where an actual compilation into planning under uncertainty exists. This enables us to exploit off-the-shelf planning tools to solve message-based WSC in a general form that involves powerful ontologies, and requires reasoning about partial matches between concepts. We provide empirical evidence that this approach may be quite effective, using Conformant-FF as the underlying planner. S. D. Ramchurn, C. Mezzetti, A. Giovannucci, J. A. Rodriguez-Aguilar, R. K. Dash and N. R. Jennings (2009) "Trust-Based Mechanisms for Robust and Efficient Task Allocation in the Presence of Execution Uncertainty", Volume 35, pages 119-159 For quick access go to Abstract: Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive compatible, direct mechanisms that are efficient (i.e., maximise social utility) and individually rational (i.e., agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will "always" successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications, where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent's probability of succeeding at a given task are often captured and reasoned about using the notion of "trust". Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called "trust-based mechanisms", that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2x10^5 possible allocations in 40 seconds). V. Conitzer (2009) "Eliciting Single-Peaked Preferences Using Comparison Queries", Volume 35, pages 161-191 For quick access go to Abstract: Voting is a general method for aggregating the preferences of multiple agents. Each agent ranks all the possible alternatives, and based on this, an aggregate ranking of the alternatives (or at least a winning alternative) is produced. However, when there are many alternatives, it is impractical to simply ask agents to report their complete preferences. Rather, the agents' preferences, or at least the relevant parts thereof, need to be elicited. This is done by asking the agents a (hopefully small) number of simple queries about their preferences, such as comparison queries, which ask an agent to compare two of the alternatives. Prior work on preference elicitation in voting has focused on the case of unrestricted preferences. It has been shown that in this setting, it is sometimes necessary to ask each agent (almost) as many queries as would be required to determine an arbitrary ranking of the alternatives. In contrast, in this paper, we focus on single-peaked preferences. We show that such preferences can be elicited using only a linear number of comparison queries, if either the order with respect to which preferences are single-peaked is known, or at least one other agent's complete preferences are known. We show that using a sublinear number of queries does not suffice. We also consider the case of cardinally single-peaked preferences. For this case, we show that if the alternatives' cardinal positions are known, then an agent's preferences can be elicited using only a logarithmic number of queries; however, we also show that if the cardinal positions are not known, then a sublinear number of queries does not suffice. We present experimental results for all elicitation algorithms. We also consider the problem of only eliciting enough information to determine the aggregate ranking, and show that even for this more modest objective, a sublinear number of queries per agent does not suffice for known ordinal or unknown cardinal positions. Finally, we discuss whether and how these techniques can be applied when preferences are almost single-peaked. R. El-Yaniv and D. Pechyony (2009) "Transductive Rademacher Complexity and its Applications", Volume 35, pages 193-234 For quick access go to Abstract: We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in terms of transductive Rademacher complexity, together with a novel bounding technique for Rademacher averages for particular algorithms, in terms of their "unlabeled-labeled" representation. This technique is relevant to many advanced graph-based transductive algorithms and we demonstrate its effectiveness by deriving error bounds to three well known algorithms. Finally, we present a new PAC-Bayesian bound for mixtures of transductive algorithms based on our Rademacher bounds. M. Petrik and S. Zilberstein (2009) "A Bilinear Programming Approach for Multiagent Planning", Volume 35, pages 235-274 For quick access go to Abstract: Multiagent planning and coordination problems are common and known to be computationally hard. We show that a wide range of two-agent problems can be formulated as bilinear programs. We present a successive approximation algorithm that significantly outperforms the coverage set algorithm, which is the state-of-the-art method for this class of multiagent problems. Because the algorithm is formulated for bilinear programs, it is more general and simpler to implement. The new algorithm can be terminated at any time and-unlike the coverage set algorithm-it facilitates the derivation of a useful online performance bound. It is also much more efficient, on average reducing the computation time of the optimal solution by about four orders of magnitude. Finally, we introduce an automatic dimensionality reduction method that improves the effectiveness of the algorithm, extending its applicability to new domains and providing a new way to analyze a subclass of bilinear programs. P. Faliszewski, E. Hemaspaandra, L. A. Hemaspaandra and J. Rothe (2009) "Llull and Copeland Voting Computationally Resist Bribery and Constructive Control", Volume 35, pages 275-341 For quick access go to Abstract: Control and bribery are settings in which an external agent seeks to influence the outcome of an election. Constructive control of elections refers to attempts by an agent to, via such actions as addition/deletion/partition of candidates or voters, ensure that a given candidate wins. Destructive control refers to attempts by an agent to, via the same actions, preclude a given candidate's victory. An election system in which an agent can sometimes affect the result and it can be determined in polynomial time on which inputs the agent can succeed is said to be vulnerable to the given type of control. An election system in which an agent can sometimes affect the result, yet in which it is NP-hard to recognize the inputs on which the agent can succeed, is said to be resistant to the given type of control. Aside from election systems with an NP-hard winner problem, the only systems previously known to be resistant to all the standard control types were highly artificial election systems created by hybridization. This paper studies a parameterized version of Copeland voting, denoted by Copeland^\alpha, where the parameter \alpha is a rational number between 0 and 1 that specifies how ties are valued in the pairwise comparisons of candidates. In every previously studied constructive or destructive control scenario, we determine which of resistance or vulnerability holds for Copeland^\alpha for each rational \alpha, 0 \leq \alpha \leq 1. In particular, we prove that Copeland^{0.5}, the system commonly referred to as ``Copeland voting,'' provides full resistance to constructive control, and we prove the same for Copeland^\alpha, for all rational \alpha, 0 < \alpha < 1. Among systems with a polynomial-time winner problem, Copeland voting is the first natural election system proven to have full resistance to constructive control. In addition, we prove that both Copeland^0 and Copeland^1 (interestingly, Copeland^1 is an election system developed by the thirteenth-century mystic Llull) are resistant to all standard types of constructive control other than one variant of addition of candidates. Moreover, we show that for each rational \alpha, 0 \leq \alpha \leq 1, Copeland^\alpha voting is fully resistant to bribery attacks, and we establish fixed-parameter tractability of bounded-case control for Copeland^\alpha. We also study Copeland^\alpha elections under more flexible models such as microbribery and extended control, we integrate the potential irrationality of voter preferences into many of our results, and we prove our results in both the unique-winner model and the nonunique-winner model. Our vulnerability results for microbribery are proven via a novel technique involving min-cost network flow. R. Sebastiani and M. Vescovi (2009) "Automated Reasoning in Modal and Description Logics via SAT Encoding: the Case Study of K(m)/ALC-Satisfiability", Volume 35, pages 343-389 For quick access go to Abstract: In the last two decades, modal and description logics have been applied to numerous areas of computer science, including knowledge representation, formal verification, database theory, distributed computing and, more recently, semantic web and ontologies. For this reason, the problem of automated reasoning in modal and description logics has been thoroughly investigated. In particular, many approaches have been proposed for efficiently handling the satisfiability of the core normal modal logic K(m), and of its notational variant, the description logic ALC. Although simple in structure, K(m)/ALC is computationally very hard to reason on, its satisfiability being PSPACE-complete. In this paper we start exploring the idea of performing automated reasoning tasks in modal and description logics by encoding them into SAT, so that to be handled by state-of-the-art SAT tools; as with most previous approaches, we begin our investigation from the satisfiability in K(m). We propose an efficient encoding, and we test it on an extensive set of benchmarks, comparing the approach with the main state-of-the-art tools available. Although the encoding is necessarily worst-case exponential, from our experiments we notice that, in practice, this approach can handle most or all the problems which are at the reach of the other approaches, with performances which are comparable with, or even better than, those of the current state-of-the-art tools. R. Daly and Q. Shen (2009) "Learning Bayesian Network Equivalence Classes with Ant Colony Optimization", Volume 35, pages 391-447 For quick access go to Abstract: Bayesian networks are a useful tool in the representation of uncertain knowledge. This paper proposes a new algorithm called ACO-E, to learn the structure of a Bayesian network. It does this by conducting a search through the space of equivalence classes of Bayesian networks using Ant Colony Optimization (ACO). To this end, two novel extensions of traditional ACO techniques are proposed and implemented. Firstly, multiple types of moves are allowed. Secondly, moves can be given in terms of indices that are not based on construction graph nodes. The results of testing show that ACO-E performs better than a greedy search and other state-of-the-art and metaheuristic algorithms whilst searching in the space of equivalence classes. ---------------------------------------------------------------- II. Unsubscribing from our Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed at isi.edu. ---------------------------------------------------------------- From www-data@booberry.fetch.com Fri Oct 30 16:12:48 2009 Received: from booberry.fetch.com (firewall.jair.org [69.175.48.98] (may be forged)) by gamma.isi.edu (8.13.8/8.13.8) with ESMTP id n9UNBuRP004824 for ; Fri, 30 Oct 2009 16:11:56 -0700 (PDT) Received: from www-data by booberry.fetch.com with local (Exim 4.69) (envelope-from ) id 1N40dP-0002bj-Bj; Fri, 30 Oct 2009 18:11:55 -0500 To: jairsubscribers@mailman.isi.edu MIME-Version: 1.0 X-Mailer: htmlMimeMail5 From: jair-ed@ISI.EDU Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit Message-ID: Date: Fri, 30 Oct 2009 18:11:55 -0500 X-ISI-4-43-8-MailScanner: Found to be clean X-MailScanner-From: www-data@booberry.fetch.com Cc: jair-ed@ISI.EDU Subject: [Jairsubscribers] 10 new articles published by JAIR X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.6 Precedence: list Reply-To: jair-ed@isi.edu List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 30 Oct 2009 23:12:49 -0000 Dear JAIR subscriber: This message lists papers that were recently published in JAIR (in volume 35)and describes how to access them. (If you wish to remove yourself from this mailing list, see instructions at the end of this message.) We will also shortly be sending another message with the articles published this last month --- the beginning of volume 36. ---------------------------------------------------------------- I. New JAIR Articles F. Bromberg, D. Margaritis and V. Honavar (2009) "Efficient Markov Network Structure Discovery Using Independence Tests", Volume 35, pages 449-484 For quick access go to Abstract: We present two algorithms for learning the structure of a Markov network from data: GSMN* and GSIMN. Both algorithms use statistical independence tests to infer the structure by successively constraining the set of structures consistent with the results of these tests. Until very recently, algorithms for structure learning were based on maximum likelihood estimation, which has been proved to be NP-hard for Markov networks due to the difficulty of estimating the parameters of the network, needed for the computation of the data likelihood. The independence-based approach does not require the computation of the likelihood, and thus both GSMN* and GSIMN can compute the structure efficiently (as shown in our experiments). GSMN* is an adaptation of the Grow-Shrink algorithm of Margaritis and Thrun for learning the structure of Bayesian networks. GSIMN extends GSMN* by additionally exploiting Pearl's well-known properties of the conditional independence relation to infer novel independences from known ones, thus avoiding the performance of statistical tests to estimate them. To accomplish this efficiently GSIMN uses the Triangle theorem, also introduced in this work, which is a simplified version of the set of Markov axioms. Experimental comparisons on artificial and real-world data sets show GSIMN can yield significant savings with respect to GSMN*, while generating a Markov network with comparable or in some cases improved quality. We also compare GSIMN to a forward-chaining implementation, called GSIMN-FCH, that produces all possible conditional independences resulting from repeatedly applying Pearl's theorems on the known conditional independence tests. The results of this comparison show that GSIMN, by the sole use of the Triangle theorem, is nearly optimal in terms of the set of independences tests that it infers. P. Faliszewski, E. Hemaspaandra and L. A. Hemaspaandra (2009) "How Hard Is Bribery in Elections?", Volume 35, pages 485-532 For quick access go to Abstract: We study the complexity of influencing elections through bribery: How computationally complex is it for an external actor to determine whether by paying certain voters to change their preferences a specified candidate can be made the election’s winner? We study this problem for election systems as varied as scoring protocols and Dodgson voting, and in a variety of settings regarding homogeneous-vs.-nonhomogeneous electorate bribability, bounded-size-vs.-arbitrary-sized candidate sets, weighted-vs.-unweighted voters, and succinct-vs.-nonsuccinct input specification. We obtain both polynomial-time bribery algorithms and proofs of the intractability of bribery, and indeed our results show that the complexity of bribery is extremely sensitive to the setting. For example, we find settings in which bribery is NP-complete but manipulation (by voters) is in P, and we find settings in which bribing weighted voters is NP-complete but bribing voters with individual bribe thresholds is in P. For the broad class of elections (including plurality, Borda, k-approval, and veto) known as scoring protocols, we prove a dichotomy result for bribery of weighted voters: We find a simple-to-evaluate condition that classifies every case as either NP-complete or in P. J. E. Gallardo, C. Cotta and A. J. Fernández (2009) "Solving Weighted Constraint Satisfaction Problems with Memetic/Exact Hybrid Algorithms", Volume 35, pages 533-555 For quick access go to Abstract: A weighted constraint satisfaction problem (WCSP) is a constraint satisfaction problem in which preferences among solutions can be expressed. Bucket elimination is a complete technique commonly used to solve this kind of constraint satisfaction problem. When the memory required to apply bucket elimination is too high, a heuristic method based on it (denominated mini-buckets) can be used to calculate bounds for the optimal solution. Nevertheless, the curse of dimensionality makes these techniques impractical on large scale problems. In response to this situation, we present a memetic algorithm for WCSPs in which bucket elimination is used as a mechanism for recombining solutions, providing the best possible child from the parental set. Subsequently, a multi-level model in which this exact/metaheuristic hybrid is further hybridized with branch-and-bound techniques and mini-buckets is studied. As a case study, we have applied these algorithms to the resolution of the maximum density still life problem, a hard constraint optimization problem based on Conway's game of life. The resulting algorithm consistently finds optimal patterns for up to date solved instances in less time than current approaches. Moreover, it is shown that this proposal provides new best known solutions for very large instances. A. Krause and C. Guestrin (2009) "Optimal Value of Information in Graphical Models", Volume 35, pages 557-591 For quick access go to Abstract: Many real-world decision making tasks require us to choose among several expensive observations. In a sensor network, for example, it is important to select the subset of sensors that is expected to provide the strongest reduction in uncertainty. In medical decision making tasks, one needs to select which tests to administer before deciding on the most effective treatment. It has been general practice to use heuristic-guided procedures for selecting observations. In this paper, we present the first efficient optimal algorithms for selecting observations for a class of probabilistic graphical models. For example, our algorithms allow to optimally label hidden variables in Hidden Markov Models (HMMs). We provide results for both selecting the optimal subset of observations, and for obtaining an optimal conditional observation plan. Furthermore we prove a surprising result: In most graphical models tasks, if one designs an efficient algorithm for chain graphs, such as HMMs, this procedure can be generalized to polytree graphical models. We prove that the optimizing value of information is $NP^{PP}$-hard even for polytrees. It also follows from our results that just computing decision theoretic value of information objective functions, which are commonly used in practice, is a #P-complete problem even on Naive Bayes models (a simple special case of polytrees). In addition, we consider several extensions, such as using our algorithms for scheduling observation selection for multiple sensors. We demonstrate the effectiveness of our approach on several real-world datasets, including a prototype sensor network deployment for energy conservation in buildings. M. Zytnicki, C. Gaspin, S. de Givry and T. Schiex (2009) "Bounds Arc Consistency for Weighted CSPs", Volume 35, pages 593-621 For quick access go to Abstract: The Weighted Constraint Satisfaction Problem (WCSP) framework allows representing and solving problems involving both hard constraints and cost functions. It has been applied to various problems, including resource allocation, bioinformatics, scheduling, etc. To solve such problems, solvers usually rely on branch-and-bound algorithms equipped with local consistency filtering, mostly soft arc consistency. However, these techniques are not well suited to solve problems with very large domains. Motivated by the resolution of an RNA gene localization problem inside large genomic sequences, and in the spirit of bounds consistency for large domains in crisp CSPs, we introduce soft bounds arc consistency, a new weighted local consistency specifically designed for WCSP with very large domains. Compared to soft arc consistency, BAC provides significantly improved time and space asymptotic complexity. In this paper, we show how the semantics of cost functions can be exploited to further improve the time complexity of BAC. We also compare both in theory and in practice the efficiency of BAC on a WCSP with bounds consistency enforced on a crisp CSP using cost variables. On two different real problems modeled as WCSP, including our RNA gene localization problem, we observe that maintaining bounds arc consistency outperforms arc consistency and also improves over bounds consistency enforced on a constraint model with cost variables. H. Palacios and H. Geffner (2009) "Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width", Volume 35, pages 623-675 For quick access go to Abstract: Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state or action effects. The problem has been approached as a path-finding problem in belief space where good belief representations and heuristics are critical for scaling up. In this work, a different formulation is introduced for conformant problems with deterministic actions where they are automatically converted into classical ones and solved by an off-the-shelf classical planner. The translation maps literals L and sets of assumptions t about the initial situation, into new literals KL/t that represent that L must be true if t is initially true. We lay out a general translation scheme that is sound and establish the conditions under which the translation is also complete. We show that the complexity of the complete translation is exponential in a parameter of the problem called the conformant width, which for most benchmarks is bounded. The planner based on this translation exhibits good performance in comparison with existing planners, and is the basis for T0, the best performing planner in the Conformant Track of the 2006 International Planning Competition. K. Su, A. Sattar, G. Lv and Y. Zhang (2009) "Variable Forgetting in Reasoning about Knowledge", Volume 35, pages 677-716 For quick access go to Abstract: In this paper, we investigate knowledge reasoning within a simple framework called knowledge structure. We use variable forgetting as a basic operation for one agent to reason about its own or other agents\' knowledge. In our framework, two notions namely agents\' observable variables and the weakest sufficient condition play important roles in knowledge reasoning. Given a background knowledge base and a set of observable variables for each agent, we show that the notion of an agent knowing a formula can be defined as a weakest sufficient condition of the formula under background knowledge base. Moreover, we show how to capture the notion of common knowledge by using a generalized notion of weakest sufficient condition. Also, we show that public announcement operator can be conveniently dealt with via our notion of knowledge structure. Further, we explore the computational complexity of the problem whether an epistemic formula is realized in a knowledge structure. In the general case, this problem is PSPACE-hard; however, for some interesting subcases, it can be reduced to co-NP. Finally, we discuss possible applications of our framework in some interesting domains such as the automated analysis of the well-known muddy children puzzle and the verification of the revised Needham-Schroeder protocol. We believe that there are many scenarios where the natural presentation of the available information about knowledge is under the form of a knowledge structure. What makes it valuable compared with the corresponding multi-agent S5 Kripke structure is that it can be much more succinct. P. A. Bonatti, C. Lutz and F. Wolter (2009) "The Complexity of Circumscription in DLs", Volume 35, pages 717-773 For quick access go to Abstract: As fragments of first-order logic, Description logics (DLs) do not provide nonmonotonic features such as defeasible inheritance and default rules. Since many applications would benefit from the availability of such features, several families of nonmonotonic DLs have been developed that are mostly based on default logic and autoepistemic logic. In this paper, we consider circumscription as an interesting alternative approach to nonmonotonic DLs that, in particular, supports defeasible inheritance in a natural way. We study DLs extended with circumscription under different language restrictions and under different constraints on the sets of minimized, fixed, and varying predicates, and pinpoint the exact computational complexity of reasoning for DLs ranging from ALC to ALCIO and ALCQO. When the minimized and fixed predicates include only concept names but no role names, then reasoning is complete for NExpTime^NP. It becomes complete for NP^NExpTime when the number of minimized and fixed predicates is bounded by a constant. If roles can be minimized or fixed, then complexity ranges from NExpTime^NP to undecidability. E. Saquete, J. Luis Vicedo, P. Martínez-Barco, R. Muñoz and H. Llorens (2009) "Enhancing QA Systems with Complex Temporal Question Processing Capabilities", Volume 35, pages 775-811 For quick access go to Abstract: This paper presents a multilayered architecture that enhances the capabilities of current QA systems and allows different types of complex questions or queries to be processed. The answers to these questions need to be gathered from factual information scattered throughout different documents. Specifically, we designed a specialized layer to process the different types of temporal questions. Complex temporal questions are first decomposed into simple questions, according to the temporal relations expressed in the original question. In the same way, the answers to the resulting simple questions are recomposed, fulfilling the temporal restrictions of the original complex question. A novel aspect of this approach resides in the decomposition which uses a minimal quantity of resources, with the final aim of obtaining a portable platform that is easily extensible to other languages. In this paper we also present a methodology for evaluation of the decomposition of the questions as well as the ability of the implemented temporal layer to perform at a multilingual level. The temporal layer was first performed for English, then evaluated and compared with: a) a general purpose QA system (F-measure 65.47% for QA plus English temporal layer vs. 38.01% for the general QA system), and b) a well-known QA system. Much better results were obtained for temporal questions with the multilayered system. This system was therefore extended to Spanish and very good results were again obtained in the evaluation (F-measure 40.36% for QA plus Spanish temporal layer vs. 22.94% for the general QA system). T. Janhunen, E. Oikarinen, H. Tompits and S. Woltran (2009) "Modularity Aspects of Disjunctive Stable Models", Volume 35, pages 813-857 For quick access go to Abstract: Practically all programming languages allow the programmer to split a program into several modules which brings along several advantages in software development. In this paper, we are interested in the area of answer-set programming where fully declarative and nonmonotonic languages are applied. In this context, obtaining a modular structure for programs is by no means straightforward since the output of an entire program cannot in general be composed from the output of its components. To better understand the effects of disjunctive information on modularity we restrict the scope of analysis to the case of disjunctive logic programs (DLPs) subject to stable-model semantics. We define the notion of a DLP-function, where a well-defined input/output interface is provided, and establish a novel module theorem which indicates the compositionality of stable-model semantics for DLP-functions. The module theorem extends the well-known splitting-set theorem and enables the decomposition of DLP-functions given their strongly connected components based on positive dependencies induced by rules. In this setting, it is also possible to split shared disjunctive rules among components using a generalized shifting technique. The concept of modular equivalence is introduced for the mutual comparison of DLP-functions using a generalization of a translation-based verification method. ---------------------------------------------------------------- II. Unsubscribing from our Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed at isi.edu. ---------------------------------------------------------------- From www-data@booberry.fetch.com Tue Nov 17 09:32:03 2009 Received: from booberry.fetch.com (firewall.jair.org [69.175.48.98] (may be forged)) by gamma.isi.edu (8.13.8/8.13.8) with ESMTP id nAHHVesH003901 for ; Tue, 17 Nov 2009 09:31:40 -0800 (PST) Received: from www-data by booberry.fetch.com with local (Exim 4.69) (envelope-from ) id 1NARty-0007a1-9t; Tue, 17 Nov 2009 11:31:38 -0600 To: jairsubscribers@mailman.isi.edu MIME-Version: 1.0 X-Mailer: htmlMimeMail5 From: jair-ed@ISI.EDU Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit Message-ID: Date: Tue, 17 Nov 2009 11:31:38 -0600 X-ISI-4-43-8-MailScanner: Found to be clean X-MailScanner-From: www-data@booberry.fetch.com Cc: jair-ed@ISI.EDU Subject: [Jairsubscribers] 6 new articles published by JAIR X-BeenThere: jairsubscribers@mailman.isi.edu X-Mailman-Version: 2.1.6 Precedence: list Reply-To: jair-ed@isi.edu List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 17 Nov 2009 17:32:04 -0000 Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see instructions at the end of this message.) ---------------------------------------------------------------- I. New JAIR Articles A. Artale, D. Calvanese, R. Kontchakov and M. Zakharyaschev (2009) "The DL-Lite Family and Relations", Volume 36, pages 1-69 For quick access go to Abstract: The recently introduced series of description logics under the common moniker `DL-Lite' has attracted attention of the description logic and semantic web communities due to the low computational complexity of inference, on the one hand, and the ability to represent conceptual modeling formalisms, on the other. The main aim of this article is to carry out a thorough and systematic investigation of inference in extensions of the original DL-Lite logics along five axes: by (i) adding the Boolean connectives and (ii) number restrictions to concept constructs, (iii) allowing role hierarchies, (iv) allowing role disjointness, symmetry, asymmetry, reflexivity, irreflexivity and transitivity constraints, and (v) adopting or dropping the unique same assumption. We analyze the combined complexity of satisfiability for the resulting logics, as well as the data complexity of instance checking and answering positive existential queries. Our approach is based on embedding DL-Lite logics in suitable fragments of the one-variable first-order logic, which provides useful insights into their properties and, in particular, computational behavior. M. Bienvenu (2009) "Prime Implicates and Prime Implicants: From Propositional to Modal Logic", Volume 36, pages 71-128 For quick access go to Abstract: Prime implicates and prime implicants have proven relevant to a number of areas of artificial intelligence, most notably abductive reasoning and knowledge compilation. The purpose of this paper is to examine how these notions might be appropriately extended from propositional logic to the modal logic K. We begin the paper by considering a number of potential definitions of clauses and terms for K. The different definitions are evaluated with respect to a set of syntactic, semantic, and complexity-theoretic properties characteristic of the propositional definition. We then compare the definitions with respect to the properties of the notions of prime implicates and prime implicants that they induce. While there is no definition that perfectly generalizes the propositional notions, we show that there does exist one definition which satisfies many of the desirable properties of the propositional case. In the second half of the paper, we consider the computational properties of the selected definition. To this end, we provide sound and complete algorithms for generating and recognizing prime implicates, and we show the prime implicate recognition task to be PSPACE-complete. We also prove upper and lower bounds on the size and number of prime implicates. While the paper focuses on the logic K, all of our results hold equally well for multi-modal K and for concept expressions in the description logic ALC. H. Chen, S.R.K. Branavan, R. Barzilay and D. R. Karger (2009) "Content Modeling Using Latent Permutations", Volume 36, pages 129-163 For quick access go to Abstract: We present a novel Bayesian topic model for learning discourse-level document structure. Our model leverages insights from discourse theory to constrain latent topic assignments in a way that reflects the underlying organization of document topics. We propose a global model in which both topic selection and ordering are biased to be similar across a collection of related documents. We show that this space of orderings can be effectively represented using a distribution over permutations called the Generalized Mallows Model. We apply our method to three complementary discourse-level tasks: cross-document alignment, document segmentation, and information ordering. Our experiments show that incorporating our permutation-based model in these applications yields substantial improvements in performance over previously proposed methods. B. Motik, R. Shearer and I. Horrocks (2009) "Hypertableau Reasoning for Description Logics", Volume 36, pages 165-228 For quick access go to Abstract: We present a novel reasoning calculus for the description logic SHOIQ^+---a knowledge representation formalism with applications in areas such as the Semantic Web. Unnecessary nondeterminism and the construction of large models are two primary sources of inefficiency in the tableau-based reasoning calculi used in state-of-the-art reasoners. In order to reduce nondeterminism, we base our calculus on hypertableau and hyperresolution calculi, which we extend with a blocking condition to ensure termination. In order to reduce the size of the constructed models, we introduce anywhere pairwise blocking. We also present an improved nominal introduction rule that ensures termination in the presence of nominals, inverse roles, and number restrictions---a combination of DL constructs that has proven notoriously difficult to handle. Our implementation shows significant performance improvements over state-of-the-art reasoners on several well-known ontologies. H.L. Chieu and W.S. Lee (2009) "Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem", Volume 36, pages 229-266 For quick access go to Abstract: The survey propagation (SP) algorithm has been shown to work well on large instances of the random 3-SAT problem near its phase transition. It was shown that SP estimates marginals over covers that represent clusters of solutions. The SP-y algorithm generalizes SP to work on the maximum satisfiability (Max-SAT) problem, but the cover interpretation of SP does not generalize to SP-y. In this paper, we formulate the relaxed survey propagation (RSP) algorithm, which extends the SP algorithm to apply to the weighted Max-SAT problem. We show that RSP has an interpretation of estimating marginals over covers violating a set of clauses with minimal weight. This naturally generalizes the cover interpretation of SP. Empirically, we show that RSP outperforms SP-y and other state-of-the-art Max-SAT solvers on random Max-SAT instances. RSP also outperforms state-of-the-art weighted Max-SAT solvers on random weighted Max-SAT instances. F. Hutter, H. H. Hoos, K. Leyton-Brown and T. Stuetzle (2009) "ParamILS: An Automatic Algorithm Configuration Framework", Volume 36, pages 267-306 For quick access go to Abstract: The identification of performance-optimizing parameter settings is an important part of the development and application of algorithms. We describe an automatic framework for this algorithm configuration problem. More formally, we provide methods for optimizing a target algorithm’s performance on a given class of problem instances by varying a set of ordinal and/or categorical parameters. We review a family of local-search-based algorithm configuration procedures and present novel techniques for accelerating them by adaptively limiting the time spent for evaluating individual configurations. We describe the results of a comprehensive experimental evaluation of our methods, based on the configuration of prominent complete and incomplete algorithms for SAT. We also present what is, to our knowledge, the first published work on automatically configuring the CPLEX mixed integer programming solver. All the algorithms we considered had default parameter settings that were manually identified with considerable effort. Nevertheless, using our automated algorithm configuration procedures, we achieved substantial and consistent performance improvements. ---------------------------------------------------------------- II. Unsubscribing from our Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed at isi.edu. ----------------------------------------------------------------