text:
of the auction process. We have experimentally identified the conditions under which our new strategy works well, as well as how well it works in comparison to the optimal performance the agent could have achieved had it known the future. Our results show that our new strategy in general performs well, outperforming other tractable heuristic strategies in a majority of experiments, and is particularly effective in a "seller's market," where many buy offers are available.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {175–214},
numpages = {40}
}

@article{10.5555/1622487.1622493,
author = {Goldman, Claudia V. and Zilberstein, Shlomo},
title = {Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {143–174},
numpages = {32}
}

@article{10.5555/1622487.1622492,
author = {Derbeko, Philip and El-Yaniv, Ran and Meir, Ron},
title = {Explicit Learning Curves for Transduction and Application to Clustering and Compression Algorithms},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {117–142},
numpages = {26}
}

@article{10.5555/1622487.1622491,
author = {Chockler, Hana and Halpern, Joseph Y.},
title = {Responsibility and Blame: A Structural-Model Approach},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {93–115},
numpages = {23}
}

@article{10.5555/1622487.1622490,
author = {Meek, Colin J. and Birmingham, William P.},
title = {A Comprehensive Trainable Error Model for Sung Music Queries},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
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 error or variation between target and query: cumulative and noncumulative 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.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {57–91},
numpages = {35}
}

@article{10.5555/1622487.1622489,
author = {Dubois, Didier and Fargier, Helene and Prade, Henri},
title = {Ordinal and Probabilistic Representations of Acceptance},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
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 Gauml;rdenfors and colleagues. Our view considers the acceptance relation as a primitive object from which belief sets are derived in various contexts.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {23–56},
numpages = {34}
}

@article{10.5555/1622487.1622488,
author = {Cohen, David and Cooper, Martin and Jeavons, Peter and Krokhin, Andrei},
title = {A Maximal Tractable Class of Soft Constraints},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {1–22},
numpages = {22}
}

@article{10.5555/1622467.1622486,
author = {Felner, Ariel and Stern, Roni and Ben-Yair, Asaph and Kraus, Sarit and Netanyahu, Nathan},
title = {PHA*: Finding the Shortest Path with A* in an Unknown Physical Environment},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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 a 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 dose 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.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {631–670},
numpages = {40}
}

@article{10.5555/1622467.1622485,
author = {Babaioff, Moshe and Nisan, Noam},
title = {Concurrent Auctions across the Supply Chain},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {595–629},
numpages = {35}
}

@article{10.5555/1622467.1622484,
author = {Borodin, Allan and El-Yaniv, Ran and Gogan, Vincent},
title = {Can We Learn to Beat the Best Stock},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {579–594},
numpages = {16}
}

@article{10.5555/1622467.1622483,
author = {Liberatore, Paolo},
title = {On Polynomial Sized MDP Succinct Policies},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {551–577},
numpages = {27}
}

@article{10.5555/1622467.1622482,
author = {Keppens, Jeroen and Shen, Qiang},
title = {Compositional Model Repositories via Dynamic Constraint Satisfaction with Order-of-Magnitude Preferences},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {499–550},
numpages = {52}
}

@article{10.5555/1622467.1622481,
author = {Zhang, Weixiong},
title = {Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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 π26 as 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.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {471–497},
numpages = {27}
}

@article{10.5555/1622467.1622480,
author = {Gorniak, Peter and Roy, Deb},
title = {Grounded Semantic Composition for Visual Scenes},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
abstract = {We present a visually-grounded language understanding model based on a study of how people verbally describe objects in scenes. The emphasis of the model is on the combination of individual word meanings to produce meanings for complex referring expressions. The model has been implemented, and it is able to understand a broad range of spatial referring expressions. We describe our implementation of word level visually-grounded semantics and their embedding in a compositional parsing framework. The implemented system selects the correct referents in response to natural language expressions for a large percentage of test cases. In an analysis of the system's successes and failures we reveal how visual context influences the semantics of utterances and propose future extensions to the model that take such context into account.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {429–470},
numpages = {42}
}

@article{10.5555/1622467.1622479,
author = {Thompson, Cynthia A. and G\"{o}ker, Mehmet H. and Langley, Pat},
title = {A Personalized System for Conversational Recommendations},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {393–428},
numpages = {36}
}

@article{10.5555/1622467.1622477,
author = {Halpern, Joseph Y. and Koller, Daphne},
title = {Representation Dependence in Probabilistic Inference},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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 entropy has 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.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {319–356},
numpages = {38}
}

@article{10.5555/1622467.1622476,
author = {Nederhof, Mark-Jan and Satta, Giorgio},
title = {IDL-Expressions: A Formalism for Representing and Parsing Finite Languages in Natural Language Processing},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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 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.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {287–317},
numpages = {31}
}

@article{10.5555/1622467.1622475,
author = {Arieli, Ofer and Denecker, Marc and Van Nuffelen, Bert and Bruynooghe, Maurice},
title = {Coherent Integration of Databases by Abductive Logic Programming},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
abstract = {We introduce an abductive method for a coherent integration of independent datasources. 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 A system, 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.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {245–286},
numpages = {42}
}

@article{10.5555/1622467.1622478,
author = {Hnich, Brahim and Smith, Barbara M. and Walsh, Toby},
title = {Dual Modelling of Permutation and Injection Problems},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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 represemts one of the primal variables. Alternatively, by means of channelling constraints to link the primal and dual variables, we can have a combines model with both sets of variables. In this paper, we perform an extensive theoretical and empirical study of such primal, dual and combines models for two classes of problems: permutation problems and injection problems. Our results show that if 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.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {357–391},
numpages = {35}
}

@article{10.5555/1622467.1622474,
author = {Dixon, Heidi E. and Ginsberg, Matthew L. and Parkes, Andrew J.},
title = {Generalizing Boolean Satisfiability I: Background and Survey of Existing Work},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {193–243},
numpages = {51}
}

@article{10.5555/1622467.1622473,
author = {Boutilier, Craig and Brafman, Ronen I. and Domshlak, Carmel and Hoos, Holger H. and Poole, David},
title = {CP-Nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {135–191},
numpages = {57}
}

@article{10.5555/1622467.1622472,
author = {Park, James D. and Darwiche, Adnan},
title = {Complexity Results and Approximation Strategies for MAP Explanations},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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 NPPP 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.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {101–133},
numpages = {33}
}

@article{10.5555/1622467.1622471,
author = {Stanley, Kenneth O. and Miikkulainen, Risto},
title = {Competitive Coevolution through Evolutionary Complexification},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {63–100},
numpages = {38}
}

@article{10.5555/1622467.1622470,
author = {Monderer, Dov and Tennenholtz, Moshe},
title = {K-Implementation},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {37–62},
numpages = {26}
}

@article{10.5555/1622467.1622469,
author = {Wellman, Michael P. and Reeves, Daniel M. and Lochner, Kevin M. and Vorobeychik, Yevgeniy},
title = {Price Prediction in a Trading Agent Competition},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {19–36},
numpages = {18}
}

@article{10.5555/1622467.1622468,
author = {Zhang, Nevin L. and Ko\v{c}ka, Tom\'{a}\v{s}},
title = {Effective Dimensions of Hierarchical Latent Class Models},
year = {2004},
issue_date = {January 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {21},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–17},
numpages = {17}
}

@article{10.5555/1622434.1622451,
author = {Nigenda, Romeo Sanchez and Kambhampati, Subbarao},
title = {AltAlt<sup>p</sup>: Online Parallelization of Plans with Heuristic State Search},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {631–657},
numpages = {27}
}

@article{10.5555/1622434.1622450,
author = {Price, Bob and Boutilier, Craig},
title = {Accelerating Reinforcement Learning through Implicit Imitation},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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 difierent 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.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {569–629},
numpages = {61}
}

@article{10.5555/1622434.1622449,
author = {Walsh, William E. and Wellman, Michael P.},
title = {Decentralized Supply Chain Formation: A Market Protocol and Competitive Equilibrium Analysis},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {513–567},
numpages = {55}
}

@article{10.5555/1622434.1622448,
author = {Console, Luca and Picardi, Claudia and Dupr\'{e}, Daniele Theseider},
title = {Temporal Decision Trees: Model-Based Diagnosis of Dynamic Systems on-Board},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {469–512},
numpages = {44}
}

@article{10.5555/1622434.1622447,
author = {Guestrin, Carlos and Koller, Daphne and Parr, Ronald and Venkataraman, Shobha},
title = {Efficient Solution Algorithms for Factored MDPs},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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 1040 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.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {399–468},
numpages = {70}
}

@article{10.5555/1622434.1622446,
author = {Wray, Robert E. and Laird, John E.},
title = {An Architectural Approach to Ensuring Consistency in Hierarchical Execution},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {355–398},
numpages = {44}
}

@article{10.5555/1622434.1622445,
author = {Weiss, Gary M. and Provost, Foster},
title = {Learning When Training Data Are Costly: The Effect of Class Distribution on Tree Induction},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {315–354},
numpages = {40}
}

@article{10.5555/1622434.1622444,
author = {Lin, Fangzhen},
title = {Compiling Causal Theories to Successor State Axioms and STRIPS-like Systems},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {279–314},
numpages = {36}
}

@article{10.5555/1622434.1622443,
author = {Gr\"{u}nwald, Peter D. and Halpern, Joseph Y.},
title = {Updating Probabilities},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {243–278},
numpages = {36}
}

@article{10.5555/1622434.1622442,
author = {Stone, Peter and Schapire, Robert E. and Littman, Michael L. and Csirik, J\'{a}nos A. and McAllester, David},
title = {Decision-Theoretic Bidding Based on Learned Density Models in Simultaneous, Interacting Auctions},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {209–242},
numpages = {34}
}

@article{10.5555/1622434.1622441,
author = {Wiewiora, Eric},
title = {Potential-Based Shaping and Q-Value Initialization Are Equivalent},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {205–208},
numpages = {4}
}

@article{10.5555/1622434.1622440,
author = {Maynard-Zhang, Pedrito and Lehmann, Daniel},
title = {Representing and Aggregating Conflicting Beliefs},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {155–203},
numpages = {49}
}

@article{10.5555/1622434.1622439,
author = {Leisink, Martijn and Kappen, Bert},
title = {Bound Propagation},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {139–154},
numpages = {16}
}

@article{10.5555/1622434.1622438,
author = {Finkelstein, Lev and Markovitch, Shaul and Rivlin, Ehud},
title = {Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {73–138},
numpages = {66}
}

@article{10.5555/1622434.1622437,
author = {Eiter, Thomas and Faber, Wolfgang and Leone, Nicola and Pfeifer, Gerald and Polleres, Axel},
title = {Answer Set Planning under Action Costs},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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 κc, which extends the declarative planning language κ by action costs. κc 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 κc 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.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {25–71},
numpages = {47}
}

@article{10.5555/1622434.1622436,
author = {Brafman, Ronen I. and Tennenholtz, Moshe},
title = {Learning to Coordinate Efficiently: A Model-Based Approach},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {11–23},
numpages = {13}
}

@article{10.5555/1622434.1622435,
author = {Zanuttini, Bruno},
title = {New Polynomial Classes for Logic-Based Abduction},
year = {2003},
issue_date = {July 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {19},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {1–10},
numpages = {10}
}

@article{10.5555/1622420.1622433,
author = {Reiter, Ehud and Sripada, Somayajulu G. and Robertson, Roma},
title = {Acquiring Correct Knowledge for Natural Language Generation},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {491–516},
numpages = {26}
}

@article{10.5555/1622420.1622432,
author = {Acid, Silvia and de Campos, Luis M.},
title = {Searching for Bayesian Network Structures in the Space of Restricted Acyclic Partially Directed Graphs},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {445–490},
numpages = {46}
}

@article{10.5555/1622420.1622431,
author = {Lang, J\^{o}me and Liberatore, Paolo and Marquis, Pierre},
title = {Propositional Independence: Formula-Variable Independence and Forgetting},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {391–443},
numpages = {53}
}

@article{10.5555/1622420.1622430,
author = {Patel-Schneider, Peter F. and Sebastiani, Roberto},
title = {A New General Method to Generate Random Modal Formulae for Testing Decision Procedures},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {351–389},
numpages = {39}
}

@article{10.5555/1622420.1622429,
author = {Brafman, Ronen I. and Domshlak, Carmel},
title = {Structure and Complexity in Planning with Unary Operators},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
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.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {315–349},
numpages = {35}
}

@article{10.5555/1622420.1622428,
author = {Poole, David and Zhang, Nevin Lianwen},
title = {Exploiting Contextual Independence in Probabilistic Inference},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
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 nonquery 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.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {263–313},
numpages = {51}
}

@article{10.5555/1622420.1622427,
author = {Wilkins, David E. and Lee, Thomas J. and Berry, Pauline},
title = {Interactive Execution Monitoring of Agent Teams},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
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% of alerts are unwanted, as judged by domain experts).},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {217–261},
numpages = {45}
}

@article{10.5555/1622420.1622426,
author = {Tan, Kay Chen and Khor, Eik Fun and Lee, Tong Heng and Sathikannan, Ramasubramanian},
title = {An Evolutionary Algorithm with Advanced Goal and Priority Specification for Multi-Objective Optimization},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
abstract = {This paper presents an evolutionary algorithm with a new goal-sequence domination scheme for better decision support in multi-objective optimization. The approach allows the inclusion of advanced hard/soft priority and constraint information on each objective component, and is capable of incorporating multiple specifications with overlapping or non-overlapping objective functions via logical "OR" and "AND" connectives to drive the search towards multiple regions of trade-off. In addition, we propose a dynamic sharing scheme that is simple and adaptively estimated according to the on-line population distribution without needing any a priori parameter setting. Each feature in the proposed algorithm is examined to show its respective contribution, and the performance of the algorithm is compared with other evolutionary optimization methods. It is shown that the proposed algorithm has performed well in the diversity of evolutionary search and uniform distribution of non-dominated individuals along the final trade-offs, without significant computational effort. The algorithm is also applied to the design optimization of a practical servo control system for hard disk drives with a single voice-coil-motor actuator. Results of the evolutionary designed servo control system show a superior closed-loop performance compared to classical PID or RPT approaches.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {183–215},
numpages = {33}
}

@article{10.5555/1622420.1622425,
author = {Lerman, Kristina and Minton, Steven N. and Knoblock, Craig A.},
title = {Wrapper Maintenance: A Machine Learning Approach},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
abstract = {The proliferation of online information sources has led to an increased use of wrappers for extracting data from Web sources. While most of the previous research has focused on quick and efficient generation of wrappers, the development of tools for wrapper maintenance has received less attention. This is an important research problem because Web sources often change in ways that prevent the wrappers from extracting data correctly. We present an efficient algorithm that learns structural information about data from positive examples alone. We describe how this information can be used for two wrapper maintenance applications: wrapper verification and reinduction. The wrapper verification system detects when a wrapper is not extracting correct data, usually because the Web source has changed its format. The reinduction algorithm automatically recovers from changes in the Web source by identifying data on Web pages so that a new wrapper may be generated for this source. To validate our approach, we monitored 27 wrappers over a period of a year. The verification algorithm correctly discovered 35 of the 37 wrapper changes, and made 16 mistakes, resulting in precision of 0.73 and recall of 0.95. We validated the reinduction algorithm on ten Web sources. We were able to successfully reinduce the wrappers, obtaining precision and recall values of 0.90 and 0.80 on the data extraction task.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {149–181},
numpages = {33}
}

@article{10.5555/1622420.1622424,
author = {Peral, Jes\'{u} and Ferr\'{a}ez, Antonio},
title = {Translation of Pronominal Anaphora between English and Spanish: Discrepancies and Evaluation},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
abstract = {This paper evaluates the different tasks carried out in the translation of pronominal anaphora in a machine translation (MT) system. The MT interlingua approach named AGIR (Anaphora Generation with an Interlingua Representation) improves upon other proposals presented to date because it is able to translate intersentential anaphors, detect co-reference chains, and translate Spanish zero pronouns into English--issues hardly considered by other systems. The paper presents the resolution and evaluation of these anaphora problems in AGIR with the use of different kinds of knowledge (lexical, morphological, syntactic, and semantic). The translation of English and Spanish anaphoric third-person personal pronouns (including Spanish zero pronouns) into the target language has been evaluated on unrestricted corpora. We have obtained a precision of 80.4% and 84.8% in the translation of Spanish and English pronouns, respectively. Although we have only studied the Spanish and English languages, our approach can be easily extended to other languages such as Portuguese, Italian, or Japanese.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {117–147},
numpages = {31}
}

@article{10.5555/1622420.1622423,
author = {Grumberg, Orna and Livne, Shlomi and Markovitch, Shaul},
title = {Learning to Order BDD Variables in Verification},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
abstract = {The size and complexity of software and hardware systems have significantly increased in the past years. As a result, it is harder to guarantee their correct behavior. One of the most successful methods for automated verification of finite-state systems is model checking. Most of the current model-checking systems use binary decision diagrams (BDDs) for the representation of the tested model and in the verification process of its properties. Generally, BDDs allow a canonical compact representation of a boolean function (given an order of its variables). The more compact the BDD is, the better performance one gets from the verifier. However, finding an optimal order for a BDD is an NP-complete problem. Therefore, several heuristic methods based on expert knowledge have been developed for variable ordering.We propose an alternative approach in which the variable ordering algorithm gains "ordering experience" from training models and uses the learned knowledge for finding good orders. Our methodology is based on offine learning of pair precedence classifiers from training models, that is, learning which variable pair permutation is more likely to lead to a good order. For each training model, a number of training sequences are evaluated. Every training model variable pair permutation is then tagged based on its performance on the evaluated orders. The tagged permutations are then passed through a feature extractor and are given as examples to a classifier creation algorithm. Given a model for which an order is requested, the ordering algorithm consults each precedence classifier and constructs a pair precedence table which is used to create the order.Our algorithm was integrated with SMV, which is one of the most widely used verification systems. Preliminary empirical evaluation of our methodology, using real benchmark models, shows performance that is better than random ordering and is competitive with existing algorithms that use expert knowledge. We believe that in sub-domains of models (alu, caches, etc.) our system will prove even more valuable. This is because it features the ability to learn sub-domain knowledge, something that no other ordering algorithm does.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {83–116},
numpages = {34}
}

@article{10.5555/1622420.1622422,
author = {Cemgil, Ali Taylan and Kappen, Bert},
title = {Monte Carlo Methods for Tempo Tracking and Rhythm Quantization},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
abstract = {We present a probabilistic generative model for timing deviations in expressive music performance. The structure of the proposed model is equivalent to a switching state space model. The switch variables correspond to discrete note locations as in a musical score. The continuous hidden variables denote the tempo. We formulate two well known music recognition problems, namely tempo tracking and automatic transcription (rhythm quantization) as filtering and maximum a posteriori (MAP) state estimation tasks. Exact computation of posterior features such as the MAP state is intractable in this model class, so we introduce Monte Carlo methods for integration and optimization. We compare Markov Chain Monte Carlo (MCMC) methods (such as Gibbs sampling, simulated annealing and iterative improvement) and sequential Monte Carlo methods (particle filters). Our simulation results suggest better results with sequential methods. The methods can be applied in both online and batch scenarios such as tempo tracking and transcription and are thus potentially useful in a number of music applications such as adaptive automatic accompaniment, score typesetting and music information retrieval.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {45–81},
numpages = {37}
}

@article{10.5555/1622420.1622421,
author = {Thompson, Cynthia A. and Mooney, Raymond J.},
title = {Acquiring Word-Meaning Mappings for Natural Language Interfaces},
year = {2003},
issue_date = {January 2003},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {18},
number = {1},
issn = {1076-9757},
abstract = {This paper focuses on a system, WOLFIE (WOrd Learning From Interpreted Examples), that acquires a semantic lexicon from a corpus of sentences paired with semantic representations. The lexicon learned consists of phrases paired with meaning representations. WOLFIE is part of an integrated system that learns to transform sentences into representations such as logical database queries.Experimental results are presented demonstrating WOLFIE's ability to learn useful lexicons for a database interface in four different natural languages. The usefulness of the lexicons learned by WOLFIE are compared to those acquired by a similar system, with results favorable to WOLFIE. A second set of experiments demonstrates WOLFIE's ability to scale to larger and more difficult, albeit artificially generated, corpora.In natural language acquisition, it is difficult to gather the annotated data needed for supervised learning; however, unannotated data is fairly plentiful. Active learning methods attempt to select for annotation and training only the most informative examples, and therefore are potentially very useful in natural language applications. However, most results to date for active learning have only considered standard classification tasks. To reduce annotation effort while maintaining accuracy, we apply active learning to semantic lexicons. We show that active learning can significantly reduce the number of annotated examples required to achieve a given level of performance.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–44},
numpages = {44}
}

@article{10.5555/1622810.1622825,
author = {Gamberger, Dragan and Lavrac, Nada},
title = {Expert-Guided Subgroup Discovery: Methodology and Application},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {This paper presents an approach to expert-guided subgroup discovery. The main step of the subgroup discovery process, the induction of subgroup descriptions, is performed by a heuristic beam search algorithm, using a novel parametrized definition of rule quality which is analyzed in detail. The other important steps of the proposed subgroup discovery process are the detection of statistically significant properties of selected subgroups and subgroup visualization: statistically significant properties are used to enrich the descriptions of induced subgroups, while the visualization shows subgroup properties in the form of distributions of the numbers of examples in the subgroups. The approach is illustrated by the results obtained for a medical problem of early detection of patient risk groups.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {501–527},
numpages = {27}
}

@article{10.5555/1622810.1622824,
author = {Bui, Hung H. and Venkatesh, Svetha and West, Geoff},
title = {Policy Recognition in the Abstract Hidden Markov Model},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we present a method for recognising an agent's behaviour in dynamic, noisy, uncertain domains, and across multiple levels of abstraction. We term this problem on-line plan recognition under uncertainty and view it generally as probabilistic inference on the stochastic process representing the execution of the agent's plan. Our contributions in this paper are twofold. In terms of probabilistic inference, we introduce the Abstract Hidden Markov Model (AHMM), a novel type of stochastic processes, provide its dynamic Bayesian network (DBN) structure and analyse the properties of this network. We then describe an application of the Rao-Blackwellised Particle Filter to the AHMM which allows us to construct an efficient, hybrid inference method for this model. In terms of plan recognition, we propose a novel plan recognition framework based on the AHMM as the plan execution model. The Rao-Blackwellised hybrid inference for AHMM can take advantage of the independence properties inherent in a model of plan execution, leading to an algorithm for online probabilistic plan recognition that scales well with the number of levels in the plan hierarchy. This illustrates that while stochastic models for plan execution can be complex, they exhibit special structures which, if exploited, can lead to efficient plan recognition algorithms. We demonstrate the usefulness of the AHMM framework via a behaviour recognition system in a complex spatial environment using distributed video surveillance data.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {451–499},
numpages = {49}
}

@article{10.5555/1622810.1622823,
author = {Fern, Alan and Givan, Robert and Siskind, Jeffrey Mark},
title = {Specific-to-General Learning for Temporal Events with Application to Learning Event Definitions from Video},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {We develop, analyze, and evaluate a novel, supervised, specific-to-general learner for a simple temporal logic and use the resulting algorithm to learn visual event definitions from video sequences. First, we introduce a simple, propositional, temporal, event-description language called AMA that is sufficiently expressive to represent many events yet sufficiently restrictive to support learning. We then give algorithms, along with lower and upper complexity bounds, for the subsumption and generalization problems for AMA formulas. We present a positive-examples-only specific-to-general learning method based on these algorithms. We also present a polynomial-time-computable "syntactic" subsumption test that implies semantic subsumption without being equivalent to it. A generalization algorithm based on syntactic subsumption can be used in place of semantic generalization to improve the asymptotic complexity of the resulting learning algorithm. Finally, we apply this algorithm to the task of learning relational event definitions from video and show that it yields definitions that are competitive with hand-coded ones.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {379–449},
numpages = {71}
}

@article{10.5555/1622810.1622822,
author = {Tennenholtz, Moshe},
title = {Competitive Safety Analysis: Robust Decision-Making in Multi-Agent Systems},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {Much work in AI deals with the selection of proper actions in a given (known or unknown) environment. However, the way to select a proper action when facing other agents is quite unclear. Most work in AI adopts classical game-theoretic equilibrium analysis to predict agent behavior in such settings. This approach however does not provide us with any guarantee for the agent. In this paper we introduce competitive safety analysis. This approach bridges the gap between the desired normative AI approach, where a strategy should be selected in order to guarantee a desired payoff, and equilibrium analysis. We show that a safety level strategy is able to guarantee the value obtained in a Nash equilibrium, in several classical computer science settings. Then, we discuss the concept of competitive safety strategies, and illustrate its use in a decentralized load balancing setting, typical to network problems. In particular, we show that when we have many agents, it is possible to guarantee an expected payoff which is a factor of 8/9 of the payoff obtained in a Nash equilibrium. Our discussion of competitive safety analysis for decentralized load balancing is further developed to deal with many communication links and arbitrary speeds. Finally, we discuss the extension of the above concepts to Bayesian games, and illustrate their use in a basic auctions setup.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {363–378},
numpages = {16}
}

@article{10.5555/1622810.1622820,
author = {Gao, Yong and Culberson, Joseph},
title = {An Analysis of Phase Transition in NK Landscapes},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we analyze the decision version of the NK landscape model from the perspective of threshold phenomena and phase transitions under two random distributions, the uniform probability model and the fixed ratio model. For the uniform probability model, we prove that the phase transition is easy in the sense that there is a polynomial algorithm that can solve a random instance of the problem with the probability asymptotic to 1 as the problem size tends to infinity. For the fixed ratio model, we establish several upper bounds for the solubility threshold, and prove that random instances with parameters above these upper bounds can be solved polynomially. This, together with our empirical study for random instances generated below and in the phase transition region, suggests that the phase transition of the fixed ratio model is also easy.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {309–332},
numpages = {24}
}

@article{10.5555/1622810.1622819,
author = {Bod, Rens},
title = {A Unified Model of Structural Organization in Language and Music},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {Is there a general model that can predict the perceived phrase structure in language and music? While it is usually assumed that humans have separate faculties for language and music, this work focuses on the commonalities rather than on the differences between these modalities, aiming at finding a deeper "faculty". Our key idea is that the perceptual system strives for the simplest structure (the "simplicity principle"), but in doing so it is biased by the likelihood of previous structures (the "likelihood principle"). We present a series of data-oriented parsing (DOP) models that combine these two principles and that are tested on the Penn Treebank and the Essen Folksong Collection. Our experiments show that (1) a combination of the two principles outperforms the use of either of them, and (2) exactly the same model with the same parameter setting achieves maximum accuracy for both language and music. We argue that our results suggest an interesting parallel between linguistic and musical structuring.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {289–308},
numpages = {20}
}

@article{10.5555/1622810.1622818,
author = {Chan, Hei and Darwiche, Adnan},
title = {When Do Numbers Really Matter?},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {Common wisdom has it that small distinctions in the probabilities (parameters) quantifying a belief network do not matter much for the results of probabilistic queries. Yet, one can develop realistic scenarios under which small variations in network parameters can lead to significant changes in computed queries. A pending theoretical question is then to analytically characterize parameter changes that do or do not matter. In this paper, we study the sensitivity of probabilistic queries to changes in network parameters and prove some tight bounds on the impact that such parameters can have on queries. Our analytic results pinpoint some interesting situations under which parameter changes do or do not matter. These results are important for knowledge engineers as they help them identify influential network parameters. They also help explain some of the previous experimental results and observations with regards to network robustness against parameter changes.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {265–287},
numpages = {23}
}

@article{10.5555/1622810.1622817,
author = {Darwiche, Adnan and Marquis, Pierre},
title = {A Knowledge Compilation Map},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {We propose a perspective on knowledge compilation which calls for analyzing different compilation approaches according to two key dimensions: the succinctness of the target compilation language, and the class of queries and transformations that the language supports in polytime. We then provide a knowledge compilation map, which analyzes a large number of existing target compilation languages according to their succinctness and their polytime transformations and queries. We argue that such analysis is necessary for placing new compilation approaches within the context of existing ones. We also go beyond classical, flat target compilation languages based on CNF and DNF, and consider a richer, nested class based on directed acyclic graphs (such as OBDDs), which we show to include a relatively large number of target compilation languages.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {229–264},
numpages = {36}
}

@article{10.5555/1622810.1622816,
author = {Scerri, Paul and Pynadath, David V. and Tambe, Milind},
title = {Towards Adjustable Autonomy for the Real World},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {Adjustable autonomy refers to entities dynamically varying their own autonomy, transferring decision-making control to other entities (typically agents transferring control to human users) in key situations. Determining whether and when such transfers-of-control should occur is arguably the fundamental research problem in adjustable autonomy. Previous work has investigated various approaches to addressing this problem but has often focused on individual agent-human interactions. Unfortunately, domains requiring collaboration between teams of agents and humans reveal two key shortcomings of these previous approaches. First, these approaches use rigid one-shot transfers of control that can result in unacceptable coordination failures in multiagent settings. Second, they ignore costs (e.g., in terms of time delays or effects on actions) to an agent's team due to such transfers-of-control.To remedy these problems, this article presents a novel approach to adjustable autonomy, based on the notion of a transfer-of-control strategy. A transfer-of-control strategy consists of a conditional sequence of two types of actions: (i) actions to transfer decision-making control (e.g., from an agent to a user or vice versa) and (ii) actions to change an agent's pre-specified coordination constraints with team members, aimed at minimizing miscoordination costs. The goal is for high-quality individual decisions to be made with minimal disruption to the coordination of the team. We present a mathematical model of transfer-of-control strategies. The model guides and informs the operationalization of the strategies using Markov Decision Processes, which select an optimal strategy, given an uncertain environment and costs to the individuals and teams. The approach has been carefully evaluated, including via its use in a real-world, deployed multi-agent system that assists a research group in its daily activities.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {171–228},
numpages = {58}
}

@article{10.5555/1622810.1622815,
author = {Nock, Richard},
title = {Inducing Interpretable Voting Classifiers without Trading Accuracy for Simplicity: Theoretical Results, Approximation Algorithms, and Experiments},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {Recent advances in the study of voting classification algorithms have brought empirical and theoretical results clearly showing the discrimination power of ensemble classifiers. It has been previously argued that the search of this classification power in the design of the algorithms has marginalized the need to obtain interpretable classifiers. Therefore, the question of whether one might have to dispense with interpretability in order to keep classification strength is being raised in a growing number of machine learning or data mining papers. The purpose of this paper is to study both theoretically and empirically the problem. First, we provide numerous results giving insight into the hardness of the simplicity-accuracy tradeoff for voting classifiers. Then we provide an efficient "top-down and prune" induction heuristic, WIDC, mainly derived from recent results on the weak learning and boosting frameworks. It is to our knowledge the first attempt to build a voting classifier as a base formula using the weak learning framework (the one which was previously highly successful for decision tree induction), and not the strong learning framework (as usual for such classifiers with boosting-like approaches). While it uses a well-known induction scheme previously successful in other classes of concept representations, thus making it easy to implement and compare, WIDC also relies on recent or new results we give about particular cases of boosting known as partition boosting and ranking loss boosting. Experimental results on thirty-one domains, most of which readily available, tend to display the ability of WIDC to produce small, accurate, and interpretable decision committees.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {137–170},
numpages = {34}
}

@article{10.5555/1622810.1622814,
author = {Kaminka, Gal A. and Pynadath, David V. and Tambe, Milind},
title = {Monitoring Teams by Overhearing: A Multi-Agent Plan-Recognition Approach},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {Recent years are seeing an increasing need for on-line monitoring of teams of cooperating agents, e.g., for visualization, or performance tracking. However, in monitoring deployed teams, we often cannot rely on the agents to always communicate their state to the monitoring system. This paper presents a non-intrusive approach to monitoring by overhearing, where the monitored team's state is inferred (via plan-recognition) from team-members' routine communications, exchanged as part of their coordinated task execution, and observed (overheard) by the monitoring system. Key challenges in this approach include the demanding run-time requirements of monitoring, the scarceness of observations (increasing monitoring uncertainty), and the need to scale-up monitoring to address potentially large teams. To address these, we present a set of complementary novel techniques, exploiting knowledge of the social structures and procedures in the monitored team: (i) an efficient probabilistic plan-recognition algorithm, well-suited for processing communications as observations; (ii) an approach to exploiting knowledge of the team's social behavior to predict future observations during execution (reducing monitoring uncertainty); and (iii) monitoring algorithms that trade expressivity for scalability, representing only certain useful monitoring hypotheses, but allowing for any number of agents and their different activities to be represented in a single coherent entity. We present an empirical evaluation of these techniques, in combination and apart, in monitoring a deployed team of agents, running on machines physically distributed across the country, and engaged in complex, dynamic task execution. We also compare the performance of these techniques to human expert and novice monitors, and show that the techniques presented are capable of monitoring at human-expert levels, despite the difficulty of the task.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {83–135},
numpages = {53}
}

@article{10.5555/1622810.1622813,
author = {Halpern, Joseph Y. and Pucella, Riccardo},
title = {A Logic for Reasoning about Upper Probabilities},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {We present a propositional logic to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability to each event. We give a sound and complete axiomatization for the logic, and show that the satisfiability problem is NP-complete, no harder than satisfiability for propositional logic.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {57–81},
numpages = {25}
}

@article{10.5555/1622810.1622812,
author = {Barzilay, Regina and Elhadad, Noemie and McKeown, Kathleen R.},
title = {Inferring Strategies for Sentence Ordering in Multidocument News Summarization},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {The problem of organizing information for multidocument summarization so that the generated summary is coherent has received relatively little attention. While sentence ordering for single document summarization can be determined from the ordering of sentences in the input article, this is not the case for multidocument summarization where summary sentences may be drawn from different input articles. In this paper, we propose a methodology for studying the properties of ordering information in the news genre and describe experiments done on a corpus of multiple acceptable orderings we developed for the task. Based on these experiments, we implemented a strategy for ordering information that combines constraints from chronological order of events and topical relatedness. Evaluation of our augmented algorithm shows a significant improvement of the ordering over two baseline strategies.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {35–55},
numpages = {21}
}

@article{10.5555/1622810.1622821,
author = {Al-Ani, Ahmed and Deriche, Mohamed},
title = {A New Technique for Combining Multiple Classifiers Using the Dempster-Shafer Theory of Evidence},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {This paper presents a new classifier combination technique based on the Dempster-Shafer theory of evidence. The Dempster-Shafer theory of evidence is a powerful method for combining measures of evidence from different classifiers. However, since each of the available methods that estimates the evidence of classifiers has its own limitations, we propose here a new implementation which adapts to training data so that the overall mean square error is minimized. The proposed technique is shown to outperform most available classifier combination methods when tested on three different classification problems.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {333–361},
numpages = {29}
}

@article{10.5555/1622810.1622811,
author = {Howe, Adele E. and Dahlman, Eric},
title = {A Critical Assessment of Benchmark Comparison in Planning},
year = {2002},
issue_date = {July 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {17},
number = {1},
issn = {1076-9757},
abstract = {Recent trends in planning research have led to empirical comparison becoming commonplace. The field has started to settle into a methodology for such comparisons, which for obvious practical reasons requires running a subset of planners on a subset of problems. In this paper, we characterize the methodology and examine eight implicit assumptions about the problems, planners and metrics used in many of these comparisons. The problem assumptions are: PR1) the performance of a general purpose planner should not be penalized/biased if executed on a sampling of problems and domains, PR2) minor syntactic differences in representation do not affect performance, and PR3) problems should be solvable by STRIPS capable planners unless they require ADL. The planner assumptions are: PL1) the latest version of a planner is the best one to use, PL2) default parameter settings approximate good performance, and PL3) time cut-offs do not unduly bias outcome. The metrics assumptions are: M1) performance degrades similarly for each planner when run on degraded runtime environments (e.g., machine platform) and M2) the number of plan steps distinguishes performance. We find that most of these assumptions are not supported empirically; in particular, that planners are affected differently by these assumptions. We conclude with a call to the community to devote research resources to improving the state of the practice and especially to enhancing the available benchmark problems.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {1–33},
numpages = {33}
}

@article{10.5555/1622407.1622419,
author = {Baget, Jean-Fran\c{c}s and Mugnier, Marie-Laure},
title = {Extensions of Simple Conceptual Graphs: The Complexity of Rules and Constraints},
year = {2002},
issue_date = {January 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {16},
number = {1},
issn = {1076-9757},
abstract = {Simple conceptual graphs are considered as the kernel of most knowledge representation formalisms built upon Sowa's model. Reasoning in this model can be expressed by a graph homomorphism called projection, whose semantics is usually given in terms of positive, conjunctive, existential FOL. We present here a family of extensions of this model, based on rules and constraints, keeping graph homomorphism as the basic operation. We focus on the formal definitions of the different models obtained, including their operational semantics and relationships with FOL, and we analyze the decidability and complexity of the associated problems (consistency and deduction). As soon as rules are involved in reasonings, these problems are not decidable, but we exhibit a condition under which they fall in the polynomial hierarchy. These results extend and complete the ones already published by the authors. Moreover we systematically study the complexity of some particular cases obtained by restricting the form of constraints and/or rules.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {425–465},
numpages = {41}
}

@article{10.5555/1622407.1622418,
author = {Pynadath, David V. and Tambe, Milind},
title = {The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models},
year = {2002},
issue_date = {January 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {16},
number = {1},
issn = {1076-9757},
abstract = {Despite the significant progress in multiagent teamwork, existing research does not address the optimality of its prescriptions nor the complexity of the teamwork problem. Without a characterization of the optimality-complexity tradeoffs, it is impossible to determine whether the assumptions and approximations made by a particular theory gain enough efficiency to justify the losses in overall performance. To provide a tool for use by multiagent researchers in evaluating this tradeoff, we present a unified framework, the COMmunicative Multiagent Team Decision Problem (COM-MTDP). The COM-MTDP model combines and extends existing multiagent theories, such as decentralized partially observable Markov decision processes and economic team theory. In addition to their generality of representation, COM-MTDPs also support the analysis of both the optimality of team performance and the computational complexity of the agents' decision problem. In analyzing complexity, we present a breakdown of the computational complexity of constructing optimal teams under various classes of problem domains, along the dimensions of observability and communication cost. In analyzing optimality, we exploit the COM-MTDP's ability to encode existing teamwork theories and models to encode two instantiations of joint intentions theory taken from the literature. Furthermore, the COM-MTDP model provides a basis for the development of novel team coordination algorithms. We derive a domain-independent criterion for optimal communication and provide a comparative analysis of the two joint intentions instantiations with respect to this optimal policy. We have implemented a reusable, domain-independent software package based on COM-MTDPs to analyze teamwork coordination strategies, and we demonstrate its use by encoding and evaluating the two joint intentions strategies within an example domain.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {389–423},
numpages = {35}
}

@article{10.5555/1622407.1622417,
author = {Wolpert, David H. and Tumer, Kagan},
title = {Collective Intelligence, Data Routing and Braess' Paradox},
year = {2002},
issue_date = {January 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {16},
number = {1},
issn = {1076-9757},
abstract = {We consider the problem of designing the the utility functions of the utility-maximizing agents in a multi-agent system (MAS) so that they work synergistically to maximize a global utility. The particular problem domain we explore is the control of network routing by placing agents on all the routers in the network. Conventional approaches to this task have the agents all use the Ideal Shortest Path routing Algorithm (ISPA). We demonstrate that in many cases, due to the side-effects of one agent's actions on another agent's performance, having agents use ISPA's is suboptimal as far as global aggregate cost is concerned, even when they are only used to route infinitesimally small amounts of traffic. The utility functions of the individual agents are not "aligned" with the global utility, intuitively speaking. As a particular example of this we present an instance of Braess' paradox in which adding new links to a network whose agents all use the ISPA results in a decrease in overall throughput. We also demonstrate that load-balancing, in which the agents' decisions are collectively made to optimize the global cost incurred by all traffic currently being routed, is suboptimal as far as global cost averaged across time is concerned. This is also due to "side-effects", in this case of current routing decision on future traffic. The mathematics of Collective Intelligence (COIN) is concerned precisely with the issue of avoiding such deleterious side-effects in multi-agent systems, both over time and space. We present key concepts from that mathematics and use them to derive an algorithm whose ideal version should have better performance than that of having all agents use the ISPA, even in the infinitesimal limit. We present experiments verifying this, and also showing that a machine-learning-based version of this COIN algorithm in which costs are only imprecisely estimated via empirical means (a version potentially applicable in the real world) also outperforms the ISPA, despite having access to less information than does the ISPA. In particular, this COIN algorithm almost always avoids Braess' paradox.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {359–387},
numpages = {29}
}

@article{10.5555/1622407.1622416,
author = {Chawla, Nitesh V. and Bowyer, Kevin W. and Hall, Lawrence O. and Kegelmeyer, W. Philip},
title = {SMOTE: Synthetic Minority over-Sampling Technique},
year = {2002},
issue_date = {January 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {16},
number = {1},
issn = {1076-9757},
abstract = {An approach to the construction of classifiers from imbalanced datasets is described. A dataset is imbalanced if the classification categories are not approximately equally represented. Often real-world data sets are predominately composed of "normal" examples with only a small percentage of "abnormal" or "interesting" examples. It is also the case that the cost of misclassifying an abnormal (interesting) example as a normal example is often much higher than the cost of the reverse error. Under-sampling of the majority (normal) class has been proposed as a good means of increasing the sensitivity of a classifier to the minority class. This paper shows that a combination of our method of oversampling the minority (abnormal)cla ss and under-sampling the majority (normal) class can achieve better classifier performance (in ROC space)tha n only under-sampling the majority class. This paper also shows that a combination of our method of over-sampling the minority class and under-sampling the majority class can achieve better classifier performance (in ROC space)t han varying the loss ratios in Ripper or class priors in Naive Bayes. Our method of over-sampling the minority class involves creating synthetic minority class examples. Experiments are performed using C4.5, Ripper and a Naive Bayes classifier. The method is evaluated using the area under the Receiver Operating Characteristic curve (AUC)and the ROC convex hull strategy.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {321–357},
numpages = {37}
}

@article{10.5555/1622407.1622415,
author = {Walker, Marilyn A. and Langkilde-Geary, Irene and Hastie, Helen Wright and Wright, Jerry and Gorin, Allen},
title = {Automatically Training a Problematic Dialogue Predictor for a Spoken Dialogue System},
year = {2002},
issue_date = {January 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {16},
number = {1},
issn = {1076-9757},
abstract = {Spoken dialogue systems promise efficient and natural access to a large variety of information sources and services from any phone. However, current spoken dialogue systems are deficient in their strategies for preventing, identifying and repairing problems that arise in the conversation. This paper reports results on automatically training a Problematic Dialogue Predictor to predict problematic human-computer dialogues using a corpus of 4692 dialogues collected with the How May I Help YouSM spoken dialogue system. The Problematic Dialogue Predictor can be immediately applied to the system's decision of whether to transfer the call to a human customer care agent, or be used as a cue to the system's dialogue manager to modify its behavior to repair problems, and even perhaps, to prevent them. We show that a Problematic Dialogue Predictor using automatically-obtainable features from the first two exchanges in the dialogue can predict problematic dialogues 13.2% more accurately than the baseline.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {293–319},
numpages = {27}
}

@article{10.5555/1622407.1622414,
author = {Xu, Xin and He, Han-gen and Hu, Dewen},
title = {Efficient Reinforcement Learning Using Recursive Least-Squares Methods},
year = {2002},
issue_date = {January 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {16},
number = {1},
issn = {1076-9757},
abstract = {The recursive least-squares (RLS) algorithm is one of the most well-known algorithms used in adaptive filtering, system identification and adaptive control. Its popularity is mainly due to its fast convergence speed, which is considered to be optimal in practice. In this paper, RLS methods are used to solve reinforcement learning problems, where two new reinforcement learning algorithms using linear value function approximators are proposed and analyzed. The two algorithms are called RLS-TD(λ) and Fast-AHC (Fast Adaptive Heuristic Critic), respectively. RLS-TD(λ) can be viewed as the extension of RLS-TD(0) from λ =0 to general 0≤ λ ≤1, so it is a multi-step temporal-difference (TD) learning algorithm using RLS methods. The convergence with probability one and the limit of convergence of RLS-TD(λ) are proved for ergodic Markov chains. Compared to the existing LS-TD(λ) algorithm, RLS-TD(λ) has advantages in computation and is more suitable for online learning. The effectiveness of RLS-TD(λ) is analyzed and verified by learning prediction experiments of Markov chains with a wide range of parameter settings.The Fast-AHC algorithm is derived by applying the proposed RLS-TD(λ) algorithm in the critic network of the adaptive heuristic critic method. Unlike conventional AHC algorithm, Fast-AHC makes use of RLS methods to improve the learning-prediction efficiency in the critic. Learning control experiments of the cart-pole balancing and the acrobot swing-up problems are conducted to compare the data efficiency of Fast-AHC with conventional AHC. From the experimental results, it is shown that the data efficiency of learning control can also be improved by using RLS methods in the learning-prediction process of the critic. The performance of Fast-AHC is also compared with that of the AHC method using LS-TD(λ). Furthermore, it is demonstrated in the experiments that different initial values of the variance matrix in RLS-TD(λ) are required to get better performance not only in learning prediction but also in learning control. The experimental results are analyzed based on the existing theoretical work on the transient phase of forgetting factor RLS methods.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {259–292},
numpages = {34}
}

@article{10.5555/1622407.1622413,
author = {Di Sciascio, Eugenio and Donini, Francesco M. and Mongiello, Marina},
title = {Structured Knowledge Representation for Image Retrieval},
year = {2002},
issue_date = {January 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {16},
number = {1},
issn = {1076-9757},
abstract = {We propose a structured approach to the problem of retrieval of images by content and present a description logic that has been devised for the semantic indexing and retrieval of images containing complex objects.As other approaches do, we start from low-level features extracted with image analysis to detect and characterize regions in an image. However, in contrast with feature-based approaches, we provide a syntax to describe segmented regions as basic objects and complex objects as compositions of basic ones. Then we introduce a companion extensional semantics for defining reasoning services, such as retrieval, classification, and subsumption. These services can be used for both exact and approximate matching, using similarity measures.Using our logical approach as a formal specification, we implemented a complete client-server image retrieval system, which allows a user to pose both queries by sketch and queries by example. A set of experiments has been carried out on a testbed of images to assess the retrieval capabilities of the system in comparison with expert users ranking. Results are presented adopting a well-established measure of quality borrowed from textual information retrieval.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {209–257},
numpages = {49}
}

@article{10.5555/1622407.1622412,
author = {Shatkay, Hagit and Kaelbling, Leslie Pack},
title = {Learning Geometrically-Constrained Hidden Markov Models for Robot Navigation: Bridging the Topological-Geometrical Gap},
year = {2002},
issue_date = {January 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {16},
number = {1},
issn = {1076-9757},
abstract = {Hidden Markov models (HMMs) and partially observable Markov decision processes (POMDPs) provide useful tools for modeling dynamical systems. They are particularly useful for representing the topology of environments such as road networks and office buildings, which are typical for robot navigation and planning. The work presented here describes a formal framework for incorporating readily available odometric information and geometrical constraints into both the models and the algorithm that learns them. By taking advantage of such information, learning HMMs/POMDPs can be made to generate better solutions and require fewer iterations, while being robust in the face of data reduction. Experimental results, obtained from both simulated and real robot data, demonstrate the effectiveness of the approach.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {167–207},
numpages = {41}
}

@article{10.5555/1622407.1622411,
author = {Blockeel, Hendrik and Dehaspe, Luc and Demoen, Bart and Janssens, Gerda and Ramon, Jan and Vandecasteele, Henk},
title = {Improving the Efficiency of Inductive Logic Programming through the Use of Query Packs},
year = {2002},
issue_date = {January 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {16},
number = {1},
issn = {1076-9757},
abstract = {Inductive logic programming, or relational learning, is a powerful paradigm for machine learning or data mining. However, in order for ILP to become practically useful, the efficiency of ILP systems must improve substantially. To this end, the notion of a query pack is introduced: it structures sets of similar queries. Furthermore, a mechanism is described for executing such query packs. A complexity analysis shows that considerable efficiency improvements can be achieved through the use of this query pack execution mechanism. This claim is supported by empirical results obtained by incorporating support for query pack execution in two existing learning systems.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {135–166},
numpages = {32}
}

@article{10.5555/1622407.1622410,
author = {Singh, Satinder and Litman, Diane and Kearns, Michael and Walker, Marilyn},
title = {Optimizing Dialogue Management with Reinforcement Learning: Experiments with the NJFun System},
year = {2002},
issue_date = {January 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {16},
number = {1},
issn = {1076-9757},
abstract = {Designing the dialogue policy of a spoken dialogue system involves many nontrivial choices. This paper presents a reinforcement learning approach for automatically optimizing a dialogue policy, which addresses the technical challenges in applying reinforcement learning to a working dialogue system with human users. We report on the design, construction and empirical evaluation of NJFun, an experimental spoken dialogue system that provides users with access to information about fun things to do in New Jersey. Our results show that by optimizing its performance via reinforcement learning, NJFun measurably improves system performance.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {105–133},
numpages = {29}
}

@article{10.5555/1622407.1622409,
author = {Drummond, Chris},
title = {Accelerating Reinforcement Learning by Composing Solutions of Automatically Identified Subtasks},
year = {2002},
issue_date = {January 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {16},
number = {1},
issn = {1076-9757},
abstract = {This paper discusses a system that accelerates reinforcement learning by using transfer from related tasks. Without such transfer, even if two tasks are very similar at some abstract level, an extensive re-learning effort is required. The system achieves much of its power by transferring parts of previously learned solutions rather than a single complete solution. The system exploits strong features in the multi-dimensional function produced by reinforcement learning in solving a particular task. These features are stable and easy to recognize early in the learning process. They generate a partitioning of the state space and thus the function. The partition is represented as a graph. This is used to index and compose functions stored in a case base to form a close approximation to the solution of the new task. Experiments demonstrate that function composition often produces more than an order of magnitude increase in learning rate compared to a basic reinforcement learning algorithm.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {59–104},
numpages = {46}
}

@article{10.5555/1622407.1622408,
author = {Baader, Franz and Lutz, Carsten and Sturm, Holger and Wolter, Frank},
title = {Fusions of Description Logics and Abstract Description Systems},
year = {2002},
issue_date = {January 2002},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {16},
number = {1},
issn = {1076-9757},
abstract = {Fusions are a simple way of combining logics. For normal modal logics, fusions have been investigated in detail. In particular, it is known that, under certain conditions, decidability transfers from the component logics to their fusion. Though description logics are closely related to modal logics, they are not necessarily normal. In addition, ABox reasoning in description logics is not covered by the results from modal logics.In this paper, we extend the decidability transfer results from normal modal logics to a large class of description logics. To cover different description logics in a uniform way, we introduce abstract description systems, which can be seen as a common generalization of description and modal logics, and show the transfer results in this general setting.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–58},
numpages = {58}
}

@article{10.5555/1622845.1622858,
author = {Sato, Taisuke and Kameya, Yoshitaka},
title = {Parameter Learning of Logic Programs for Symbolic-Statistical Modeling},
year = {2001},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
abstract = {We propose a logical/mathematical framework for statistical parameter learning of parameterized logic programs, i.e. definite clause programs containing probabilistic facts with a parameterized distribution. It extends the traditional least Herbrand model semantics in logic programming to distribution semantics, possible world semantics with a probability distribution which is unconditionally applicable to arbitrary logic programs including ones for HMMs, PCFGs and Bayesian networks.We also propose a new EM algorithm, the graphical EM algorithm, that runs for a class of parameterized logic programs representing sequential decision processes where each decision is exclusive and independent. It runs on a new data structure called support graphs describing the logical relationship between observations and their explanations, and learns parameters by computing inside and outside probability generalized for logic programs.The complexity analysis shows that when combined with OLDT search for all explanations for observations, the graphical EM algorithm, despite its generality, has the same time complexity as existing EM algorithms, i.e. the Baum-Welch algorithm for HMMs, the Inside-Outside algorithm for PCFGs, and the one for singly connected Bayesian networks that have been developed independently in each research field. Learning experiments with PCFGs using two corpora of moderate size indicate that the graphical EM algorithm can significantly outperform the Inside-Outside algorithm.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {391–454},
numpages = {64}
}

@article{10.5555/1622845.1622857,
author = {Meek, Christopher},
title = {Finding a Path is Harder than Finding a Tree},
year = {2001},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
abstract = {I consider the problem of learning an optimal path graphical model from data and show the problem to be NP-hard for the maximum likelihood and minimum description length approaches and a Bayesian approach. This hardness result holds despite the fact that the problem is a restriction of the polynomially solvable problem of finding the optimal tree graphical model.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {383–389},
numpages = {7}
}

@article{10.5555/1622845.1622856,
author = {Baxter, Jonathan and Bartlett, Peter L. and Weaver, Lex},
title = {Experiments with Infinite-Horizon, Policy-Gradient Estimation},
year = {2001},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
abstract =

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr