From jair-ed@isi.edu Wed Jan 22 01:07:48 2003
From: jair-ed@isi.edu (JAIRMAIL)
Date: Tue, 21 Jan 2003 17:07:48 -0800 (PST)
Subject: [Jairsubscribers] Welcome JAIR Subscribers
Message-ID: <200301220107.h0M17mF22876@nitro.isi.edu>
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 jair-ed@isi.edu Sat Mar 1 01:36:26 2003
From: jair-ed@isi.edu (JAIRMAIL)
Date: Fri, 28 Feb 2003 17:36:26 -0800 (PST)
Subject: [Jairsubscribers] Recent JAIR articles
Message-ID: <200303010136.h211aQE18356@nitro.isi.edu>
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 jair-ed@isi.edu Sat Mar 1 02:06:42 2003
From: jair-ed@isi.edu (JAIRMAIL)
Date: Fri, 28 Feb 2003 18:06:42 -0800 (PST)
Subject: [Jairsubscribers] Correction! New articles...
Message-ID: <200303010206.h2126gj06603@nitro.isi.edu>
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 jair-ed@isi.edu Tue Apr 1 17:23:30 2003
From: jair-ed@isi.edu (JAIRMAIL)
Date: Tue, 1 Apr 2003 09:23:30 -0800 (PST)
Subject: [Jairsubscribers] Announcement: JMLG
Message-ID: <200304011723.h31HNU311650@nitro.isi.edu>
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 jair-ed@isi.edu Thu May 1 01:46:02 2003
From: jair-ed@isi.edu (JAIRMAIL)
Date: Wed, 30 Apr 2003 17:46:02 -0700 (PDT)
Subject: [Jairsubscribers] JAIR News
Message-ID: <200305010046.h410k2u07498@nitro.isi.edu>
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 jair-ed@isi.edu Wed Jul 2 00:53:36 2003
From: jair-ed@isi.edu (JAIRMAIL)
Date: Tue, 1 Jul 2003 16:53:36 -0700 (PDT)
Subject: [Jairsubscribers] JAIR update
Message-ID: <200307012353.h61NraF26381@nitro.isi.edu>
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 jair-ed@isi.edu Tue Oct 7 23:02:18 2003
From: jair-ed@isi.edu (JAIRMAIL)
Date: Tue, 7 Oct 2003 15:02:18 -0700 (PDT)
Subject: [Jairsubscribers] JAIR update
Message-ID: <200310072202.h97M2I218182@nitro.isi.edu>
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 jair-ed@isi.edu Wed Dec 31 09:00:27 2003
From: jair-ed@isi.edu (JAIRMAIL)
Date: Wed, 31 Dec 2003 01:00:27 -0800 (PST)
Subject: [Jairsubscribers] JAIR Update
Message-ID: <200312310900.hBV90RT08306@nitro.isi.edu>
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.