text:
with these new classes. Theoretical results are validated in experiments.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {471–511},
numpages = {41}
}

@article{10.5555/1734953.1734963,
author = {Domshlak, Carmel and Hoffmann, J\"{o}rg and Sabharwal, Ashish},
title = {Friends or Foes? On Planning as Satisfiability and Abstract CNF Encodings},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {Planning as satisfiability, as implemented in, for instance, the SATPLAN tool, is a highly competitive method for finding parallel step-optimal plans. A bottleneck in this approach is to prove the absence of plans of a certain length. Specifically, if the optimal plan has n steps, then it is typically very costly to prove that there is no plan of length n-1. We pursue the idea of leading this proof within solution length preserving abstractions (over-approximations) of the original planning task. This is promising because the abstraction may have a much smaller state space; related methods are highly successful in model checking. In particular, we design a novel abstraction technique based on which one can, in several widely used planning benchmarks, construct abstractions that have exponentially smaller state spaces while preserving the length of an optimal plan.Surprisingly, the idea turns out to appear quite hopeless in the context of planning as satisfiability. Evaluating our idea empirically, we run experiments on almost all benchmarks of the international planning competitions up to IPC 2004, and find that even handmade abstractions do not tend to improve the performance of SATPLAN. Exploring these findings from a theoretical point of view, we identify an interesting phenomenon that may cause this behavior. We compare various planning-graph based CNF encodings Φ of the original planning task with the CNF encodings Φσ of the abstracted planning task. We prove that, in many cases, the shortest resolution refutation for Φσ can never be shorter than that for Φ. This suggests a fundamental weakness of the approach, and motivates further investigation of the interplay between declarative transition-systems, over-approximating abstractions, and SAT encodings.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {415–469},
numpages = {55}
}

@article{10.5555/1734953.1734962,
author = {Feldman, Michal and Tamir, Tami},
title = {Approximate Strong Equilibrium in Job Scheduling Games},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {A Nash Equilibrium (NE) is a strategy profile resilient to unilateral deviations, and is predominantly used in the analysis of multiagent systems. A downside of NE is that it is not necessarily stable against deviations by coalitions. Yet, as we show in this paper, in some cases, NE does exhibit stability against coalitional deviations, in that the benefits from a joint deviation are bounded. In this sense, NE approximates strong equilibrium.Coalition formation is a key issue in multiagent systems. We provide a framework for quantifying the stability and the performance of various assignment policies and solution concepts in the face of coalitional deviations. Within this framework we evaluate a given configuration according to three measures: (i) IRmin: the maximal number α, such that there exists a coalition in which the minimal improvement ratio among the coalition members is α, (ii) IRmax: the maximal number α, such that there exists a coalition in which the maximal improvement ratio among the coalition members is α, and (iii) DRmax: the maximal possible damage ratio of an agent outside the coalition.We analyze these measures in job scheduling games on identical machines. In particular, we provide upper and lower bounds for the above three measures for both NE and the well-known assignment rule Longest Processing Time (LPT).Our results indicate that LPT performs better than a general NE. However, LPT is not the best possible approximation. In particular, we present a polynomial time approximation scheme (PTAS) for the makespan minimization problem which provides a schedule with IRmin of 1 + undefined for any given undefined. With respect to computational complexity, we show that given an NE on m ≤ 3 identical machines or m ≤ 2 unrelated machines, it is NP-hard to determine whether a given coalition can deviate such that every member decreases its cost.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {387–414},
numpages = {28}
}

@article{10.5555/1734953.1734961,
author = {Naseem, Tahira and Snyder, Benjamin and Eisenstein, Jacob and Barzilay, Regina},
title = {Multilingual Part-of-Speech Tagging: Two Unsupervised Approaches},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {We demonstrate the effectiveness of multilingual learning for unsupervised part-of-speech tagging. The central assumption of our work is that by combining cues from multiple languages, the structure of each becomes more apparent. We consider two ways of applying this intuition to the problem of unsupervised part-of-speech tagging: a model that directly merges tag structures for a pair of languages into a single sequence and a second model which instead incorporates multilingual context using latent variables. Both approaches are formulated as hierarchical Bayesian models, using Markov Chain Monte Carlo sampling techniques for inference. Our results demonstrate that by incorporating multilingual evidence we can achieve impressive performance gains across a range of scenarios. We also found that performance improves steadily as the number of available languages increases.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {341–385},
numpages = {45}
}

@article{10.5555/1734953.1734960,
author = {Pad\'{o}, Sebastian and Lapata, Mirella},
title = {Cross-Lingual Annotation Projection of Semantic Roles},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {This article considers the task of automatically inducing role-semantic annotations in the FrameNet paradigm for new languages. We propose a general framework that is based on annotation projection, phrased as a graph optimization problem. It is relatively inexpensive and has the potential to reduce the human effort involved in creating role-semantic resources. Within this framework, we present projection models that exploit lexical and syntactic information. We provide an experimental evaluation on an English-German parallel corpus which demonstrates the feasibility of inducing high-precision German semantic role annotation both for manually and automatically annotated English data.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {307–340},
numpages = {34}
}

@article{10.5555/1734953.1734959,
author = {Hutter, Frank and Hoos, Holger H. and Leyton-Brown, Kevin and St\"{u}tzle, Thomas},
title = {ParamILS: An Automatic Algorithm Configuration Framework},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {The identification of performance-optimizing parameter settings is an important part of the development and application of algorithms. We describe an automatic framework for this algorithm configuration problem. More formally, we provide methods for optimizing a target algorithm's performance on a given class of problem instances by varying a set of ordinal and/or categorical parameters. We review a family of local-search-based algorithm configuration procedures and present novel techniques for accelerating them by adaptively limiting the time spent for evaluating individual configurations. We describe the results of a comprehensive experimental evaluation of our methods, based on the configuration of prominent complete and incomplete algorithms for SAT. We also present what is, to our knowledge, the first published work on automatically configuring the CPLEX mixed integer programming solver. All the algorithms we considered had default parameter settings that were manually identified with considerable effort. Nevertheless, using our automated algorithm configuration procedures, we achieved substantial and consistent performance improvements.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {267–306},
numpages = {40}
}

@article{10.5555/1734953.1734958,
author = {Chieu, Hai Leong and Lee, Wee Sun},
title = {Relaxed Survey Propagation for the Weighted Maximum Satisfiability Problem},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {The survey propagation (SP) algorithm has been shown to work well on large instances of the random 3-SAT problem near its phase transition. It was shown that SP estimates marginals over covers that represent clusters of solutions. The SP-y algorithm generalizes SP to work on the maximum satisfiability (Max-SAT) problem, but the cover interpretation of SP does not generalize to SP-y. In this paper, we formulate the relaxed survey propagation (RSP) algorithm, which extends the SP algorithm to apply to the weighted Max-SAT problem. We show that RSP has an interpretation of estimating marginals over covers violating a set of clauses with minimal weight. This naturally generalizes the cover interpretation of SP. Empirically, we show that RSP outperforms SP-y and other state-of-the-art Max-SAT solvers on random Max-SAT instances. RSP also outperforms state-of-the-art weighted Max-SAT solvers on random weighted Max-SAT instances.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {229–266},
numpages = {38}
}

@article{10.5555/1734953.1734957,
author = {Motik, Boris and Shearer, Rob and Horrocks, Ian},
title = {Hypertableau Reasoning for Description Logics},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {We present a novel reasoning calculus for the description logic SHOIQ+--a knowledge representation formalism with applications in areas such as the SemanticWeb. Unnecessary nondeterminism and the construction of large models are two primary sources of inefficiency in the tableau-based reasoning calculi used in state-of-the-art reasoners. In order to reduce nondeterminism, we base our calculus on hypertableau and hyperresolution calculi, which we extend with a blocking condition to ensure termination. In order to reduce the size of the constructed models, we introduce anywhere pairwise blocking. We also present an improved nominal introduction rule that ensures termination in the presence of nominals, inverse roles, and number restrictions--a combination of DL constructs that has proven notoriously difficult to handle. Our implementation shows significant performance improvements over state-of-the-art reasoners on several well-known ontologies.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {165–228},
numpages = {64}
}

@article{10.5555/1734953.1734956,
author = {Chen, Harr and Branavan, S. R. K. and Barzilay, Regina and Karger, David R.},
title = {Content Modeling Using Latent Permutations},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {We present a novel Bayesian topic model for learning discourse-level document structure. Our model leverages insights from discourse theory to constrain latent topic assignments in a way that reflects the underlying organization of document topics. We propose a global model in which both topic selection and ordering are biased to be similar across a collection of related documents. We show that this space of orderings can be effectively represented using a distribution over permutations called the Generalized Mallows Model. We apply our method to three complementary discourse-level tasks: cross-document alignment, document segmentation, and information ordering. Our experiments show that incorporating our permutation-based model in these applications yields substantial improvements in performance over previously proposed methods.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {129–163},
numpages = {35}
}

@article{10.5555/1734953.1734955,
author = {Bienvenu, Meghyn},
title = {Prime Implicates and Prime Implicants: From Propositional to Modal Logic},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {Prime implicates and prime implicants have proven relevant to a number of areas of artificial intelligence, most notably abductive reasoning and knowledge compilation. The purpose of this paper is to examine how these notions might be appropriately extended from propositional logic to the modal logic κ. We begin the paper by considering a number of potential definitions of clauses and terms for κ. The different definitions are evaluated with respect to a set of syntactic, semantic, and complexity-theoretic properties characteristic of the propositional definition. We then compare the definitions with respect to the properties of the notions of prime implicates and prime implicants that they induce. While there is no definition that perfectly generalizes the propositional notions, we show that there does exist one definition which satisfies many of the desirable properties of the propositional case. In the second half of the paper, we consider the computational properties of the selected definition. To this end, we provide sound and complete algorithms for generating and recognizing prime implicates, and we show the prime implicate recognition task to be Pspace-complete. We also prove upper and lower bounds on the size and number of prime implicates. While the paper focuses on the logic κ, all of our results hold equally well for multi-modal κ and for concept expressions in the description logic ALC.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {71–128},
numpages = {58}
}

@article{10.5555/1734953.1734954,
author = {Artale, Alessandro and Calvanese, Diego and Kontchakov, Roman and Zakharyaschev, Michael},
title = {The DL-Lite Family and Relations},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {The recently introduced series of description logics under the common moniker 'DL-Lite' has attracted attention of the description logic and semantic web communities due to the low computational complexity of inference, on the one hand, and the ability to represent conceptual modeling formalisms, on the other. The main aim of this article is to carry out a thorough and systematic investigation of inference in extensions of the original DL-Lite logics along five axes: by (i) adding the Boolean connectives and (ii) number restrictions to concept constructs, (iii) allowing role hierarchies, (iv) allowing role disjointness, symmetry, asymmetry, reflexivity, irreflexivity and transitivity constraints, and (v) adopting or dropping the unique name assumption. We analyze the combined complexity of satisfiability for the resulting logics, as well as the data complexity of instance checking and answering positive existential queries. Our approach is based on embedding DL-Lite logics in suitable fragments of the one-variable first-order logic, which provides useful insights into their properties and, in particular, computational behavior.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1–69},
numpages = {69}
}

@article{10.5555/1641503.1641522,
author = {Janhunen, Tomi and Oikarinen, Emilia and Tompits, Hans and Woltran, Stefan},
title = {Modularity Aspects of Disjunctive Stable Models},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {Practically all programming languages allow the programmer to split a program into several modules which brings along several advantages in software development. In this paper, we are interested in the area of answer-set programming where fully declarative and nonmonotonic languages are applied. In this context, obtaining a modular structure for programs is by no means straightforward since the output of an entire program cannot in general be composed from the output of its components. To better understand the effects of disjunctive information on modularity we restrict the scope of analysis to the case of disjunctive logic programs (DLPs) subject to stable-model semantics. We define the notion of a DLP-function, where a well-defined input/output interface is provided, and establish a novel module theorem which indicates the compositionality of stable-model semantics for DLP-functions. The module theorem extends the well-known splitting-set theorem and enables the decomposition of DLP-functions given their strongly connected components based on positive dependencies induced by rules. In this setting, it is also possible to split shared disjunctive rules among components using a generalized shifting technique. The concept of modular equivalence is introduced for the mutual comparison of DLP-functions using a generalization of a translation-based verification method.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {813–857},
numpages = {45}
}

@article{10.5555/1641503.1641521,
author = {Saquete, Estela and Vicedo, Jose L. and Mart\'{\i}nez-Barco, Patricio and Mu\~{n}oz, Rafael and Llorens, Hector},
title = {Enhancing QA Systems with Complex Temporal Question Processing Capabilities},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {This paper presents a multilayered architecture that enhances the capabilities of current QA systems and allows different types of complex questions or queries to be processed. The answers to these questions need to be gathered from factual information scattered throughout different documents. Specifically, we designed a specialized layer to process the different types of temporal questions. Complex temporal questions are first decomposed into simple questions, according to the temporal relations expressed in the original question. In the same way, the answers to the resulting simple questions are recomposed, fulfilling the temporal restrictions of the original complex question. A novel aspect of this approach resides in the decomposition which uses a minimal quantity of resources, with the final aim of obtaining a portable platform that is easily extensible to other languages. In this paper we also present a methodology for evaluation of the decomposition of the questions as well as the ability of the implemented temporal layer to perform at a multilingual level. The temporal layer was first performed for English, then evaluated and compared with: a) a general purpose QA system (F-measure 65.47% for QA plus English temporal layer vs. 38.01% for the general QA system), and b) a well-known QA system. Much better results were obtained for temporal questions with the multilayered system. This system was therefore extended to Spanish and very good results were again obtained in the evaluation (F-measure 40.36% for QA plus Spanish temporal layer vs. 22.94% for the general QA system).},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {755–811},
numpages = {57}
}

@article{10.5555/1641503.1641520,
author = {Bonatti, Piero A. and Lutz, Carsten and Wolter, Frank},
title = {The Complexity of Circumscription in Description Logic},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {As fragments of first-order logic, Description logics (DLs) do not provide nonmonotonic features such as defeasible inheritance and default rules. Since many applications would benefit from the availability of such features, several families of nonmonotonic DLs have been developed that are mostly based on default logic and autoepistemic logic. In this paper, we consider circumscription as an interesting alternative approach to nonmonotonic DLs that, in particular, supports defeasible inheritance in a natural way. We study DLs extended with circumscription under different language restrictions and under different constraints on the sets of minimized, fixed, and varying predicates, and pinpoint the exact computational complexity of reasoning for DLs ranging from ALC to ALCIO and ALCQO. When the minimized and fixed predicates include only concept names but no role names, then reasoning is complete for NEXPNP. It becomes complete for NPNEXP when the number of minimized and fixed predicates is bounded by a constant. If roles can be minimized or fixed, then complexity ranges from NEXPNP to undecidability.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {717–773},
numpages = {57}
}

@article{10.5555/1641503.1641519,
author = {Su, Kaile and Sattar, Abdul and Lv, Guanfeng and Zhang, Yan},
title = {Variable Forgetting in Reasoning about Knowledge},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we investigate knowledge reasoning within a simple framework called knowledge structure. We use variable forgetting as a basic operation for one agent to reason about its own or other agents' knowledge. In our framework, two notions namely agents' observable variables and the weakest sufficient condition play important roles in knowledge reasoning. Given a background knowledge base Γ and a set of observable variables Oi for each agent i, we show that the notion of agent i knowing a formula ϕ can be defined as a weakest sufficient condition of ϕ over Oi under Γ Moreover, we show how to capture the notion of common knowledge by using a generalized notion of weakest sufficient condition. Also, we show that public announcement operator can be conveniently dealt with via our notion of knowledge structure. Further, we explore the computational complexity of the problem whether an epistemic formula is realized in a knowledge structure. In the general case, this problem is PSPACE-hard; however, for some interesting subcases, it can be reduced to co-NP. Finally, we discuss possible applications of our framework in some interesting domains such as the automated analysis of the well-known muddy children puzzle and the verification of the revised Needham-Schroeder protocol. We believe that there are many scenarios where the natural presentation of the available information about knowledge is under the form of a knowledge structure. What makes it valuable compared with the corresponding multi-agent S5 Kripke structure is that it can be much more succinct.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {677–716},
numpages = {40}
}

@article{10.5555/1641503.1641518,
author = {Palacios, Hector and Geffner, Hector},
title = {Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state or action effects. The problem has been approached as a path-finding problem in belief space where good belief representations and heuristics are critical for scaling up. In this work, a different formulation is introduced for conformant problems with deterministic actions where they are automatically converted into classical ones and solved by an off-the-shelf classical planner. The translation maps literals L and sets of assumptions t about the initial situation, into new literals KL/t that represent that L must be true if t is initially true. We lay out a general translation scheme that is sound and establish the conditions under which the translation is also complete. We show that the complexity of the complete translation is exponential in a parameter of the problem called the conformant width, which for most benchmarks is bounded. The planner based on this translation exhibits good performance in comparison with existing planners, and is the basis for T0, the best performing planner in the Conformant Track of the 2006 International Planning Competition.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {623–675},
numpages = {53}
}

@article{10.5555/1641503.1641517,
author = {Zytnicki, Matthias and Gaspin, Christine and de Givry, Simon and Schiex, Thomas},
title = {Bounds Arc Consistency for Weighted CSPs},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {The Weighted Constraint Satisfaction Problem (WCSP) framework allows representing and solving problems involving both hard constraints and cost functions. It has been applied to various problems, including resource allocation, bioinformatics, scheduling, etc. To solve such problems, solvers usually rely on branch-and-bound algorithms equipped with local consistency filtering, mostly soft arc consistency. However, these techniques are not well suited to solve problems with very large domains. Motivated by the resolution of an RNA gene localization problem inside large genomic sequences, and in the spirit of bounds consistency for large domains in crisp CSPs, we introduce soft bounds arc consistency, a new weighted local consistency specifically designed for WCSP with very large domains. Compared to soft arc consistency, BAC provides significantly improved time and space asymptotic complexity. In this paper, we show how the semantics of cost functions can be exploited to further improve the time complexity of BAC. We also compare both in theory and in practice the efficiency of BAC on a WCSP with bounds consistency enforced on a crisp CSP using cost variables. On two different real problems modeled as WCSP, including our RNA gene localization problem, we observe that maintaining bounds arc consistency outperforms arc consistency and also improves over bounds consistency enforced on a constraint model with cost variables.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {593–621},
numpages = {29}
}

@article{10.5555/1641503.1641516,
author = {Krause, Andreas and Guestrin, Carlos},
title = {Optimal Value of Information in Graphical Models},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {Many real-world decision making tasks require us to choose among several expensive observations. In a sensor network, for example, it is important to select the subset of sensors that is expected to provide the strongest reduction in uncertainty. In medical decision making tasks, one needs to select which tests to administer before deciding on the most effective treatment. It has been general practice to use heuristic-guided procedures for selecting observations. In this paper, we present the first efficient optimal algorithms for selecting observations for a class of probabilistic graphical models. For example, our algorithms allow to optimally label hidden variables in Hidden Markov Models (HMMs). We provide results for both selecting the optimal subset of observations, and for obtaining an optimal conditional observation plan.Furthermore we prove a surprising result: In most graphical models tasks, if one designs an efficient algorithm for chain graphs, such as HMMs, this procedure can be generalized to poly-tree graphical models. We prove that the optimizing value of information is NPPP-hard even for polytrees. It also follows from our results that just computing decision theoretic value of information objective functions, which are commonly used in practice, is a #P-complete problem even on Naive Bayes models (a simple special case of polytrees).In addition, we consider several extensions, such as using our algorithms for scheduling observation selection for multiple sensors. We demonstrate the effectiveness of our approach on several real-world datasets, including a prototype sensor network deployment for energy conservation in buildings.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {557–591},
numpages = {35}
}

@article{10.5555/1641503.1641515,
author = {Gallardo, Jos\'{e} E. and Cotta, Carlos and Fern\'{a}ndez, Antonio J.},
title = {Solving Weighted Constraint Satisfaction Problems with Memetic/Exact Hybrid Algorithms},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {A weighted constraint satisfaction problem (WCSP) is a constraint satisfaction problem in which preferences among solutions can be expressed. Bucket elimination is a complete technique commonly used to solve this kind of constraint satisfaction problem. When the memory required to apply bucket elimination is too high, a heuristic method based on it (denominated mini-buckets) can be used to calculate bounds for the optimal solution. Nevertheless, the curse of dimensionality makes these techniques impractical on large scale problems. In response to this situation, we present a memetic algorithm for WCSPs in which bucket elimination is used as a mechanism for recombining solutions, providing the best possible child from the parental set. Subsequently, a multi-level model in which this exact/metaheuristic hybrid is further hybridized with branch-and-bound techniques and mini-buckets is studied. As a case study, we have applied these algorithms to the resolution of the maximum density still life problem, a hard constraint optimization problem based on Conway's game of life. The resulting algorithm consistently finds optimal patterns for up to date solved instances in less time than current approaches. Moreover, it is shown that this proposal provides new best known solutions for very large instances.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {533–555},
numpages = {23}
}

@article{10.5555/1641503.1641514,
author = {Faliszewski, Piotr and Hemaspaandra, Edith and Hemaspaandra, Lane A.},
title = {How Hard is Bribery in Elections?},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {We study the complexity of influencing elections through bribery: How computationally complex is it for an external actor to determine whether by paying certain voters to change their preferences a specified candidate can be made the election's winner? We study this problem for election systems as varied as scoring protocols and Dodgson voting, and in a variety of settings regarding homogeneous-vs.-nonhomogeneous electorate bribability, bounded-size-vs.-arbitrary-sized candidate sets, weighted-vs.-unweighted voters, and succinct-vs.-nonsuccinct input specification. We obtain both polynomial-time bribery algorithms and proofs of the intractability of bribery, and indeed our results show that the complexity of bribery is extremely sensitive to the setting. For example, we find settings in which bribery is NP-complete but manipulation (by voters) is in P, and we find settings in which bribing weighted voters is NP-complete but bribing voters with individual bribe thresholds is in P. For the broad class of elections (including plurality, Borda, k- approval,and veto) known as scoring protocols, we prove a dichotomy result for bribery of weighted voters: We find a simple-to-evaluate condition that classifies every case as either NP-complete or in P.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {485–532},
numpages = {48}
}

@article{10.5555/1641503.1641513,
author = {Bromberg, Facundo and Margaritis, Dimitris and Honavar, Vasant},
title = {Efficient Markov Network Structure Discovery Using Independence Tests},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {We present two algorithms for learning the structure of a Markov network from data: GSMN* and GSIMN. Both algorithms use statistical independence tests to infer the structure by successively constraining the set of structures consistent with the results of these tests. Until very recently, algorithms for structure learning were based on maximum likelihood estimation, which has been proved to be NP-hard for Markov networks due to the difficulty of estimating the parameters of the network, needed for the computation of the data likelihood. The independence-based approach does not require the computation of the likelihood, and thus both GSMN* and GSIMN can compute the structure efficiently (as shown in our experiments). GSMN* is an adaptation of the Grow-Shrink algorithm of Margaritis and Thrun for learning the structure of Bayesian networks. GSIMN extends GSMN* by additionally exploiting Pearl's well-known properties of the conditional independence relation to infer novel independences from known ones, thus avoiding the performance of statistical tests to estimate them. To accomplish this efficiently GSIMN uses the Triangle theorem, also introduced in this work, which is a simplified version of the set of Markov axioms. Experimental comparisons on artificial and real-world data sets show GSIMN can yield significant savings with respect to GSMN*, while generating a Markov network with comparable or in some cases improved quality. We also compare GSIMN to a forward-chaining implementation, called GSIMN-FCH, that produces all possible conditional independences resulting from repeatedly applying Pearl's theorems on the known conditional independence tests. The results of this comparison show that GSIMN, by the sole use of the Triangle theorem, is nearly optimal in terms of the set of independences tests that it infers.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {449–484},
numpages = {36}
}

@article{10.5555/1641503.1641512,
author = {Daly, R\'{o}n\'{a}n and Shen, Qiang},
title = {Learning Bayesian Network Equivalence Classes with Ant Colony Optimization},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {Bayesian networks are a useful tool in the representation of uncertain knowledge. This paper proposes a new algorithm called ACO-E, to learn the structure of a Bayesian network. It does this by conducting a search through the space of equivalence classes of Bayesian networks using Ant Colony Optimization (ACO). To this end, two novel extensions of traditional ACO techniques are proposed and implemented. Firstly, multiple types of moves are allowed. Secondly, moves can be given in terms of indices that are not based on construction graph nodes. The results of testing show that ACO-E performs better than a greedy search and other state-of-the-art and metaheuristic algorithms whilst searching in the space of equivalence classes.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {391–447},
numpages = {57}
}

@article{10.5555/1641503.1641511,
author = {Sebastiani, Roberto and Vescovi, Michele},
title = {Automated Reasoning in Modal and Description Logics via SAT Encoding: The Case Study of K<sub>m</sub>ALC-Satisfiability},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {In the last two decades, modal and description logics have been applied to numerous areas of computer science, including knowledge representation, formal verification, database theory, distributed computing and, more recently, semantic web and ontologies. For this reason, the problem of automated reasoning in modal and description logics has been thoroughly investigated. In particular, many approaches have been proposed for efficiently handling the satisfiability of the core normal modal logic Km, and of its notational variant, the description logic ALC. Although simple in structure, Km/ALC is computationally very hard to reason on, its satisfiability being PSpace-complete.In this paper we start exploring the idea of performing automated reasoning tasks in modal and description logics by encoding them into SAT, so that to be handled by state-of-the-art SAT tools; as with most previous approaches, we begin our investigation from the satisfiability in Km. We propose an efficient encoding, and we test it on an extensive set of benchmarks, comparing the approach with the main state-of-the-art tools available. Although the encoding is necessarily worst-case exponential, from our experiments we notice that, in practice, this approach can handle most or all the problems which are at the reach of the other approaches, with performances which are comparable with, or even better than, those of the current state-of-the-art tools.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {343–389},
numpages = {47}
}

@article{10.5555/1641503.1641510,
author = {Faliszewski, Piotr and Hemaspaandra, Edith and Hemaspaandra, Lane A. and Rothe, J\"{o}rg},
title = {Llull and Copeland Voting Computationally Resist Bribery and Constructive Control},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {Control and bribery are settings in which an external agent seeks to influence the outcome of an election. Constructive control of elections refers to attempts by an agent to, via such actions as addition/deletion/partition of candidates or voters, ensure that a given candidate wins. Destructive control refers to attempts by an agent to, via the same actions, preclude a given candidate's victory. An election system in which an agent can sometimes affect the result and it can be determined in polynomial time on which inputs the agent can succeed is said to be vulnerable to the given type of control. An election system in which an agent can sometimes affect the result, yet in which it is NP-hard to recognize the inputs on which the agent can succeed, is said to be resistant to the given type of control.Aside from election systems with an NP-hard winner problem, the only systems previously known to be resistant to all the standard control types were highly artificial election systems created by hybridization. This paper studies a parameterized version of Copeland voting, denoted by Copelandα, where the parameter α is a rational number between 0 and 1 that specifies how ties are valued in the pairwise comparisons of candidates. In every previously studied constructive or destructive control scenario, we determine which of resistance or vulnerability holds for Copelandα for each rational α, 0 ≤ α ≤ 1. In particular, we prove that Copeland0.5, the system commonly referred to as "Copeland voting," provides full resistance to constructive control, and we prove the same for Copelandα, for all rational α, 0 < α < 1. Among systems with a polynomial-time winner problem, Copeland voting is the first natural election system proven to have full resistance to constructive control. In addition, we prove that both Copeland0 and Copeland1 (interestingly, Copeland1 is an election system developed by the thirteenth-century mystic Llull) are resistant to all standard types of constructive control other than one variant of addition of candidates. Moreover,we show that for each rational α, 0 ≤ α ≤ 1, Copelandα voting is fully resistant to bribery attacks, and we establish fixed-parameter tractability of bounded-case control for Copelandα.We also study Copelandα elections under more flexible models such as microbribery and extended control, we integrate the potential irrationality of voter preferences into many of our results, and we prove our results in both the unique-winner model and the nonunique-winner model. Our vulnerability results for microbribery are proven via a novel technique involving min-cost network flow.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {275–341},
numpages = {67}
}

@article{10.5555/1641503.1641509,
author = {Petrik, Marek and Zilberstein, Shlomo},
title = {A Bilinear Programming Approach for Multiagent Planning},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {Multiagent planning and coordination problems are common and known to be computationally hard. We show that a wide range of two-agent problems can be formulated as bilinear programs. We present a successive approximation algorithm that significantly outperforms the coverage set algorithm, which is the state-of-the-art method for this class of multiagent problems. Because the algorithm is formulated for bilinear programs, it is more general and simpler to implement. The new algorithm can be terminated at any time and-unlike the coverage set algorithm-it facilitates the derivation of a useful online performance bound. It is also much more efficient, on average reducing the computation time of the optimal solution by about four orders of magnitude. Finally, we introduce an automatic dimensionality reduction method that improves the effectiveness of the algorithm, extending its applicability to new domains and providing a new way to analyze a subclass of bilinear programs.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {235–274},
numpages = {40}
}

@article{10.5555/1641503.1641508,
author = {El-Yaniv, Ran and Pechyony, Dmitry},
title = {Transductive Rademacher Complexity and Its Applications},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in terms of transductive Rademacher complexity, together with a novel bounding technique for Rademacher averages for particular algorithms, in terms of their "unlabeled-labeled" representation. This technique is relevant to many advanced graph-based transductive algorithms and we demonstrate its effectiveness by deriving error bounds to three well known algorithms. Finally, we present a new PAC-Bayesian bound for mixtures of transductive algorithms based on our Rademacher bounds.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {193–234},
numpages = {42}
}

@article{10.5555/1641503.1641507,
author = {Conitzer, Vincent},
title = {Eliciting Single-Peaked Preferences Using Comparison Queries},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {Voting is a general method for aggregating the preferences of multiple agents. Each agent ranks all the possible alternatives, and based on this, an aggregate ranking of the alternatives (or at least a winning alternative) is produced. However, when there are many alternatives, it is impractical to simply ask agents to report their complete preferences. Rather, the agents' preferences, or at least the relevant parts thereof, need to be elicited. This is done by asking the agents a (hopefully small) number of simple queries about their preferences, such as comparison queries, which ask an agent to compare two of the alternatives. Prior work on preference elicitation in voting has focused on the case of unrestricted preferences. It has been shown that in this setting, it is sometimes necessary to ask each agent (almost) as many queries as would be required to determine an arbitrary ranking of the alternatives. In contrast, in this paper, we focus on single-peaked preferences. We show that such preferences can be elicited using only a linear number of comparison queries, if either the order with respect to which preferences are single-peaked is known, or at least one other agent's complete preferences are known. We show that using a sublinear number of queries does not suffice. We also consider the case of cardinally single-peaked preferences. For this case, we show that if the alternatives' cardinal positions are known, then an agent's preferences can be elicited using only a logarithmic number of queries; however, we also show that if the cardinal positions are not known, then a sublinear number of queries does not suffice. We present experimental results for all elicitation algorithms. We also consider the problem of only eliciting enough information to determine the aggregate ranking, and show that even for this more modest objective, a sublinear number of queries per agent does not suffice for known ordinal or unknown cardinal positions. Finally, we discuss whether and how these techniques can be applied when preferences are almost single-peaked.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {161–191},
numpages = {31}
}

@article{10.5555/1641503.1641506,
author = {Ramchurn, Sarvapali D. and Mezzetti, Claudio and Giovannucci, Andrea and Rodriguez-Aguilar, Juan A. and Dash, Rajdeep K. and Jennings, Nicholas R.},
title = {Trust-Based Mechanisms for Robust and Efficient Task Allocation in the Presence of Execution Uncertainty},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive compatible, direct mechanisms that are efficient (i.e., maximise social utility) and individually rational (i.e., agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will always successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications, where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent's probability of succeeding at a given task are often captured and reasoned about using the notion of trust. Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks.Specifically, we develop a new class of mechanisms, called trust-based mechanisms, that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2\texttimes{}105 possible allocations in 40 seconds).},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {119–159},
numpages = {41}
}

@article{10.5555/1641503.1641505,
author = {Hoffmann, J\"{o}rg and Bertoli, Piergiorgio and Helmert, Malte and Pistore, Marco},
title = {Message-Based Web Service Composition, Integrity Constraints, and Planning under Uncertainty: A New Connection},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {Thanks to recent advances, AI Planning has become the underlying technique for several applications. Figuring prominently among these is automated Web Service Composition (WSC) at the "capability" level, where services are described in terms of preconditions and effects over ontological concepts. A key issue in addressing WSC as planning is that ontologies are not only formal vocabularies; they also axiomatize the possible relationships between concepts. Such axioms correspond to what has been termed "integrity constraints" in the actions and change literature, and applying a web service is essentially a belief update operation. The reasoning required for belief update is known to be harder than reasoning in the ontology itself. The support for belief update is severely limited in current planning tools.Our first contribution consists in identifying an interesting special case of WSC which is both significant and more tractable. The special case, which we term forward effects, is characterized by the fact that every ramification of a web service application involves at least one new constant generated as output by the web service. We show that, in this setting, the reasoning required for belief update simplifies to standard reasoning in the ontology itself. This relates to, and extends, current notions of "message-based" WSC, where the need for belief update is removed by a strong (often implicit or informal) assumption of "locality" of the individual messages. We clarify the computational properties of the forward effects case, and point out a strong relation to standard notions of planning under uncertainty, suggesting that effective tools for the latter can be successfully adapted to address the former.Furthermore, we identify a significant sub-case, named strictly forward effects, where an actual compilation into planning under uncertainty exists. This enables us to exploit off-the-shelf planning tools to solve message-based WSC in a general form that involves powerful ontologies, and requires reasoning about partial matches between concepts. We provide empirical evidence that this approach may be quite effective, using Conformant-FF as the underlying planner.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {49–117},
numpages = {69}
}

@article{10.5555/1641503.1641504,
author = {Chali, Yllias and Joty, Shafiq R. and Hasan, Sadid A.},
title = {Complex Question Answering: Unsupervised Learning Approaches and Experiments},
year = {2009},
issue_date = {May 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {35},
number = {1},
issn = {1076-9757},
abstract = {Complex questions that require inferencing and synthesizing information from multiple documents can be seen as a kind of topic-oriented, informative multi-document summarization where the goal is to produce a single text as a compressed version of a set of documents with a minimum loss of relevant information. In this paper, we experiment with one empirical method and two unsupervised statistical machine learning techniques: K-means and Expectation Maximization (EM), for computing relative importance of the sentences. We compare the results of these approaches. Our experiments show that the empirical approach outperforms the other two techniques and EM performs better than K-means. However, the performance of these approaches depends entirely on the feature set used and the weighting of these features. In order to measure the importance and relevance to the user query we extract different kinds of features (i.e. lexical, lexical semantic, cosine similarity, basic element, tree kernel based syntactic and shallow-semantic) for each of the document sentences. We use a local search technique to learn the weights of the features. To the best of our knowledge, no study has used tree kernel functions to encode syntactic/semantic information for more complex tasks such as computing the relatedness between the query sentences and the document sentences in order to generate query-focused summaries (or answers to complex questions). For each of our methods of generating summaries (i.e. empirical, K-means and EM) we show the effects of syntactic and shallow-semantic features over the bag-of-words (BOW) features.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–47},
numpages = {47}
}

@article{10.5555/1622716.1622736,
author = {Zaffalon, Marco and Miranda, Enrique},
title = {Conservative Inference Rule for Uncertain Reasoning under Incompleteness},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {In this paper we formulate the problem of inference under incomplete information in very general terms. This includes modelling the process responsible for the incompleteness, which we call the incompleteness process. We allow the process' behaviour to be partly unknown. Then we use Walley's theory of coherent lower previsions, a generalisation of the Bayesian theory to imprecision, to derive the rule to update beliefs under incompleteness that logically follows from our assumptions, and that we call conservative inference rule. This rule has some remarkable properties: it is an abstract rule to update beliefs that can be applied in any situation or domain; it gives us the opportunity to be neither too optimistic nor too pessimistic about the incompleteness process, which is a necessary condition to draw reliable while strong enough conclusions; and it is a coherent rule, in the sense that it cannot lead to inconsistencies. We give examples to show how the new rule can be applied in expert systems, in parametric statistical inference, and in pattern classification, and discuss more generally the view of incompleteness processes defended here as well as some of its consequences.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {757–821},
numpages = {65}
}

@article{10.5555/1622716.1622735,
author = {Singh, Amarjeet and Krause, Andreas and Guestrin, Carlos and Kaiser, William J.},
title = {Efficient Informative Sensing Using Multiple Robots},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {The need for efficient monitoring of spatio-temporal dynamics in large environmental applications, such as the water quality monitoring in rivers and lakes, motivates the use of robotic sensors in order to achieve sufficient spatial coverage. Typically, these robots have bounded resources, such as limited battery or limited amounts of time to obtain measurements. Thus, careful coordination of their paths is required in order to maximize the amount of information collected, while respecting the resource constraints. In this paper, we present an efficient approach for near-optimally solving the NP-hard optimization problem of planning such informative paths. In particular, we first develop eSIP (efficient Single-robot Informative Path planning), an approximation algorithm for optimizing the path of a single robot. Hereby, we use a Gaussian Process to model the underlying phenomenon, and use the mutual information between the visited locations and remainder of the space to quantify the amount of information collected. We prove that the mutual information collected using paths obtained by using eSIP is close to the information obtained by an optimal solution. We then provide a general technique, sequential allocation, which can be used to extend any single robot planning algorithm, such as eSIP, for the multi-robot problem. This procedure approximately generalizes any guarantees for the single-robot problem to the multi-robot case. We extensively evaluate the effectiveness of our approach on several experiments performed infield for two important environmental sensing applications, lake and river monitoring, and simulation experiments performed using several real world sensor network data sets.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {707–755},
numpages = {49}
}

@article{10.5555/1622716.1622734,
author = {Gim\'{e}nez, Omer and Jonsson, Anders},
title = {Planning over Chain Causal Graphs for Variables with Domains of Size 5 Is NP-Hard},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {Recently, considerable focus has been given to the problem of determining the boundary between tractable and intractable planning problems. In this paper, we study the complexity of planning in the class Cn of planning problems, characterized by unary operators and directed path causal graphs. Although this is one of the simplest forms of causal graphs a planning problem can have, we show that planning is intractable for Cn (unless P = NP), even if the domains of state variables have bounded size. In particular, we show that plan existence for Ckn is NP-hard for k ≥ 5 by reduction from CNF-SAT. Here, k denotes the upper bound on the size of the state variable domains. Our result reduces the complexity gap for the class Ckn to cases k = 3 and k = 4 only, since C2n is known to be tractable.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {675–706},
numpages = {32}
}

@article{10.5555/1622716.1622733,
author = {Cohn, Trevor and Lapata, Mirella},
title = {Sentence Compression as Tree Transduction},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {This paper presents a tree-to-tree transduction method for sentence compression. Our model is based on synchronous tree substitution grammar, a formalism that allows local distortion of the tree topology and can thus naturally capture structural mismatches. We describe an algorithm for decoding in this framework and show how the model can be trained discriminatively within a large margin framework. Experimental results on sentence compression bring significant improvements over a state-of-the-art model.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {637–674},
numpages = {38}
}

@article{10.5555/1622716.1622732,
author = {S\'{a}nchez-Mart\'{\i}nez, Felipe and Forcada, Mikel L.},
title = {Inferring Shallow-Transfer Machine Translation Rules from Small Parallel Corpora},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {This paper describes a method for the automatic inference of structural transfer rules to be used in a shallow-transfer machine translation (MT) system from small parallel corpora. The structural transfer rules are based on alignment templates, like those used in statistical MT. Alignment templates are extracted from sentence-aligned parallel corpora and extended with a set of restrictions which are derived from the bilingual dictionary of the MT system and control their application as transfer rules. The experiments conducted using three difierent language pairs in the free/open-source MT platform Apertium show that translation quality is improved as compared to word-for-word translation (when no transfer rules are used), and that the resulting translation quality is close to that obtained using hand-coded transfer rules. The method we present is entirely unsupervised and benefits from information in the rest of modules of the MT system in which the inferred rules are applied.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {605–635},
numpages = {31}
}

@article{10.5555/1622716.1622731,
author = {Branavan, S. R. K. and Chen, Harr and Eisenstein, Jacob and Barzilay, Regina},
title = {Learning Document-Level Semantic Properties from Free-Text Annotations},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {This paper presents a new method for inferring the semantic properties of documents by leveraging free-text keyphrase annotations. Such annotations are becoming increasingly abundant due to the recent dramatic growth in semi-structured, user-generated online content. One especially relevant domain is product reviews, which are often annotated by their authors with pros/cons keyphrases such as "a real bargain" or "good value." These annotations are representative of the underlying semantic properties; however, unlike expert annotations, they are noisy: lay authors may use different labels to denote the same property, and some labels may be missing. To learn using such noisy annotations, we find a hidden paraphrase structure which clusters the keyphrases. The paraphrase structure is linked with a latent topic model of the review texts, enabling the system to predict the properties of unannotated documents and to effectively aggregate the semantic properties of multiple reviews. Our approach is implemented as a hierarchical Bayesian model with joint inference. We find that joint inference increases the robustness of the keyphrase clustering and encourages the latent topics to correlate with semantically meaningful properties. Multiple evaluations demonstrate that our model substantially outperforms alternative approaches for summarizing single and multiple documents into a set of semantically salient keyphrases.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {569–603},
numpages = {35}
}

@article{10.5555/1622716.1622730,
author = {Rahwan, Talal and Ramchurn, Sarvapali D. and Jennings, Nicholas R. and Giovannucci, Andrea},
title = {An Anytime Algorithm for Optimal Coalition Structure Generation},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques -- ranging from dynamic programming, to integer programming, to stochastic search -- all of which suffer from major limitations relating to execution time, solution quality, and memory requirements.With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0.175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {521–567},
numpages = {47}
}

@article{10.5555/1622716.1622729,
author = {de Angulo, Vicente Ruiz and Torras, Carme},
title = {Exploiting Single-Cycle Symmetries in Continuous Constraint Problems},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {Symmetries in discrete constraint satisfaction problems have been explored and exploited in the last years, but symmetries in continuous constraint problems have not received the same attention. Here we focus on permutations of the variables consisting of one single cycle. We propose a procedure that takes advantage of these symmetries by interacting with a continuous constraint solver without interfering with it. A key concept in this procedure are the classes of symmetric boxes formed by bisecting a n-dimensional cube at the same point in all dimensions at the same time. We analyze these classes and quantify them as a function of the cube dimensionality. Moreover, we propose a simple algorithm to generate the representatives of all these classes for any number of variables at very high rates. A problem example from the chemical field and the cyclic n-roots problem are used to show the performance of the approach in practice.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {499–520},
numpages = {22}
}

@article{10.5555/1622716.1622728,
author = {Gabrilovich, Evgeniy and Markovitch, Shaul},
title = {Wikipedia-Based Semantic Interpretation for Natural Language Processing},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {Adequate representation of natural language semantics requires access to vast amounts of common sense and domain-specific world knowledge. Prior work in the field was based on purely statistical techniques that did not make use of background knowledge, on limited lexicographic knowledge bases such as WordNet, or on huge manual efforts such as the CYC project. Here we propose a novel method, called Explicit Semantic Analysis (ESA), for fine-grained semantic interpretation of unrestricted natural language texts. Our method represents meaning in a high-dimensional space of concepts derived from Wikipedia, the largest encyclopedia in existence. We explicitly represent the meaning of any text in terms of Wikipedia-based concepts. We evaluate the effectiveness of our method on text categorization and on computing the degree of semantic relatedness between fragments of natural language text. Using ESA results in significant improvements over the previous state of the art in both tasks. Importantly, due to the use of natural concepts, the ESA model is easy to explain to human users.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {443–498},
numpages = {56}
}

@article{10.5555/1622716.1622727,
author = {Bacchus, Fahiem and Dalmao, Shannon and Pitassi, Toniann},
title = {Solving #SAT and Bayesian Inference with Backtracking Search},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {Inference in Bayes Nets (BAYES) is an important problem with numerous applications in probabilistic reasoning. Counting the number of satisfying assignments of a propositional formula (#SAT) is a closely related problem of fundamental theoretical importance. Both these problems, and others, are members of the class of sum-of-products (SUMPROD) problems. In this paper we show that standard backtracking search when augmented with a simple memoization scheme (caching) can solve any sum-of-products problem with time complexity that is at least as good any other state-of-the-art exact algorithm, and that it can also achieve the best known time-space tradeoff. Furthermore, backtracking's ability to utilize more flexible variable orderings allows us to prove that it can achieve an exponential speedup over other standard algorithms for SUMPROD on some instances.The ideas presented here have been utilized in a number of solvers that have been applied to various types of sum-of-product problem's. These system's have exploited the fact that backtracking can naturally exploit more of the problem's structure to achieve improved performance on a range of problem instances. Empirical evidence of this performance gain has appeared in published works describing these solvers, and we provide references to these works.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {391–442},
numpages = {52}
}

@article{10.5555/1622716.1622726,
author = {Li, Yifan and Musilek, Petr and Reformat, Marek and Wyard-Scott, Loren},
title = {Identification of Pleonastic It Using the Web},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {In a significant minority of cases, certain pronouns, especially the pronoun it, can be used without referring to any specific entity. This phenomenon of pleonastic pronoun usage poses serious problems for systems aiming at even a shallow understanding of natural language texts. In this paper, a novel approach is proposed to identify such uses of it : the extrapositional cases are identified using a series of queries against the web, and the cleft cases are identified using a simple set of syntactic rules. The system is evaluated with four sets of news articles containing 679 extrapositional cases as well as 78 cleft constructs. The identification results are comparable to those obtained by human efforts.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {339–389},
numpages = {51}
}

@article{10.5555/1622716.1622725,
author = {Doshi, Prashant and Gmytrasiewicz, Piotr J.},
title = {Monte Carlo Sampling Methods for Approximating Interactive POMDPs},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {Partially observable Markov decision processes (POMDPs) provide a principled framework for sequential planning in uncertain single agent settings. An extension of POMDPs to multiagent settings, called interactive POMDPs (I-POMDPs), replaces POMDP belief spaces with interactive hierarchical belief systems which represent an agent's belief about the physical world, about beliefs of other agents, and about their beliefs about others' beliefs. This modification makes the difficulties of obtaining solutions due to complexity of the belief and policy spaces even more acute. We describe a general method for obtaining approximate solutions of I-POMDPs based on particle filtering (PF). We introduce the interactive PF, which descends the levels of the interactive belief hierarchies and samples and propagates beliefs at each level. The interactive PF is able to mitigate the belief space complexity, but it does not address the policy space complexity. To mitigate the policy space complexity - sometimes also called the curse of history - we utilize a complementary method based on sampling likely observations while building the look ahead reachability tree. While this approach does not completely address the curse of history, it beats back the curse's impact substantially. We provide experimental results and chart future work.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {297–337},
numpages = {41}
}

@article{10.5555/1622716.1622724,
author = {Yates, Alexander and Etzioni, Oren},
title = {Unsupervised Methods for Determining Object and Relation Synonyms on the Web},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {The task of identifying synonymous relations and objects, or synonym resolution, is critical for high-quality information extraction. This paper investigates synonym resolution in the context of unsupervised information extraction, where neither hand-tagged training examples nor domain knowledge is available. The paper presents a scalable, fully-implemented system that runs in O(KN log N) time in the number of extractions, N, and the maximum number of synonyms per word, K. The system, called RESOLVER, introduces a probabilistic relational model for predicting whether two strings are co-referential based on the similarity of the assertions containing them. On a set of two million assertions extracted from the Web, RESOLVER resolves objects with 78% precision and 68% recall, and resolves relations with 90% precision and 35% recall. Several variations of RESOLVER's probabilistic model are explored, and experiments demonstrate that under appropriate conditions these variations can improve F1 by 5%. An extension to the basic RESOLVER system allows it to handle polysemous names with 97% precision and 95% recall on a data set from the TREC corpus.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {255–296},
numpages = {42}
}

@article{10.5555/1622716.1622723,
author = {Jurca, Radu and Faltings, Boi},
title = {Mechanisms for Making Crowds Truthful},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {We consider schemes for obtaining truthful reports on a common but hidden signal from large groups of rational, self-interested agents. One example are online feedback mechanisms, where users provide observations about the quality of a product or service so that other users can have an accurate idea of what quality they can expect. However, (i) providing such feedback is costly, and (ii) there are many motivations for providing incorrect feedback.Both problems can be addressed by reward schemes which (i) cover the cost of obtaining and reporting feedback, and (ii) maximize the expected reward of a rational agent who reports truthfully. We address the design of such incentive-compatible rewards for feedback generated in environments with pure adverse selection. Here, the correlation between the true knowledge of an agent and her beliefs regarding the likelihoods of reports of other agents can be exploited to make honest reporting a Nash equilibrium.In this paper we extend existing methods for designing incentive-compatible rewards by also considering collusion. We analyze different scenarios, where, for example, some or all of the agents collude. For each scenario we investigate whether a collusion-resistant, incentive-compatible reward scheme exists, and use automated mechanism design to specify an algorithm for deriving an efficient reward mechanism.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {209–253},
numpages = {45}
}

@article{10.5555/1622716.1622722,
author = {Wallace, Scott},
title = {Behavior Bounding: An Efficient Method for High-Level Behavior Comparison},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we explore methods for comparing agent behavior with human behavior to assist with validation. Our exploration begins by considering a simple method of behavior comparison. Motivated by shortcomings in this initial approach, we introduce behavior bounding, an automated model-based approach for comparing behavior that is inspired, in part, by Mitchell's Version Spaces. We show that behavior bounding can be used to compactly represent both human and agent behavior. We argue that relatively low amounts of human effort are required to build, maintain, and use the data structures that underlie behavior bounding, and we provide a theoretical basis for these arguments using notions of PAC Learnability. Next, we show empirical results indicating that this approach is efiective at identifying differences in certain types of behaviors and that it performs well when compared against our initial benchmark methods. Finally, we demonstrate that behavior bounding can produce information that allows developers to identify and fix problems in an agent's behavior much more efficiently than standard debugging techniques.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {165–208},
numpages = {44}
}

@article{10.5555/1622716.1622721,
author = {Binshtok, Maxim and Brafman, Ronen I. and Domshlak, Carmel and Shimony, Solomon E.},
title = {Generic Preferences over Subsets of Structured Objects},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {Various tasks in decision making and decision support systems require selecting a preferred subset of a given set of items. Here we focus on problems where the individual items are described using a set of characterizing attributes, and a generic preference specification is required, that is, a specification that can work with an arbitrary set of items. For example, preferences over the content of an online newspaper should have this form: At each viewing, the newspaper contains a subset of the set of articles currently available. Our preference specification over this subset should be provided offline, but we should be able to use it to select a subset of any currently available set of articles, e.g., based on their tags. We present a general approach for lifting formalisms for specifying preferences over objects with multiple attributes into ones that specify preferences over subsets of such objects. We also show how we can compute an optimal subset given such a specification in a relatively efficient manner. We provide an empirical evaluation of the approach as well as some worst-case complexity results.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {133–164},
numpages = {32}
}

@article{10.5555/1622716.1622720,
author = {Bernstein, Daniel S. and Amato, Christopher and Hansen, Eric A. and Zilberstein, Shlomo},
title = {Policy Iteration for Decentralized Control of Markov Decision Processes},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {Coordination of distributed agents is required for problems arising in many areas, including multi-robot systems, networking and e-commerce. As a formal framework for such problems, we use the decentralized partially observable Markov decision process (DECPOMDP). Though much work has been done on optimal dynamic programming algorithms for the single-agent version of the problem, optimal algorithms for the multiagent case have been elusive. The main contribution of this paper is an optimal policy iteration algorithm for solving DEC-POMDPs. The algorithm uses stochastic finite-state controllers to represent policies. The solution can include a correlation device, which allows agents to correlate their actions without communicating. This approach alternates between expanding the controller and performing value-preserving transformations, which modify the controller without sacrificing value. We present two efficient value-preserving transformations: one can reduce the size of the controller and the other can improve its value while keeping the size fixed. Empirical results demonstrate the usefulness of value-preserving transformations in increasing value while keeping controller size to a minimum. To broaden the applicability of the approach, we also present a heuristic version of the policy iteration algorithm, which sacrifices convergence to optimality. This algorithm further reduces the size of the controllers at each step by assuming that probability distributions over the other agents' actions are known. While this assumption may not hold in general, it helps produce higher quality solutions in our test problems.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {89–132},
numpages = {44}
}

@article{10.5555/1622716.1622719,
author = {Gershman, Amir and Meisels, Amnon and Zivan, Roie},
title = {Asynchronous Forward Bounding for Distributed COPs},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {A new search algorithm for solving distributed constraint optimization problems (DisCOPs) is presented. Agents assign variables sequentially and compute bounds on partial assignments asynchronously. The asynchronous bounds computation is based on the propagation of partial assignments. The asynchronous forward-bounding algorithm (AFB) is a distributed optimization search algorithm that keeps one consistent partial assignment at all times. The algorithm is described in detail and its correctness proven. Experimental evaluation shows that AFB outperforms synchronous branch and bound by many orders of magnitude, and produces a phase transition as the tightness of the problem increases. This is an analogous effect to the phase transition that has been observed when local consistency maintenance is applied to MaxCSPs. The AFB algorithm is further enhanced by the addition of a backjumping mechanism, resulting in the AFB-BJ algorithm. Distributed backjumping is based on accumulated information on bounds of all values and on processing concurrently a queue of candidate goals for the next move back. The AFB-BJ algorithm is compared experimentally to other DisCOP algorithms (ADOPT, DPOP, OptAPO) and is shown to be a very efficient algorithm for DisCOPs.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {61–88},
numpages = {28}
}

@article{10.5555/1622716.1622718,
author = {Meuleau, Nicolas and Benazera, Emmanuel and Brafman, Ronen I. and Hansen, Eric A. and Mausam},
title = {A Heuristic Search Approach to Planning with Continuous Resources in Stochastic Domains},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {We consider the problem of optimal planning in stochastic domains with resource constraints, where the resources are continuous and the choice of action at each step depends on resource availability. We introduce the HAO* algorithm, a generalization of the AO* algorithm that performs search in a hybrid state space that is modeled using both discrete and continuous state variables, where the continuous variables represent monotonic resources. Like other heuristic search algorithms, HAO* leverages knowledge of the start state and an admissible heuristic to focus computational effort on those parts of the state space that could be reached from the start state by following an optimal policy. We show that this approach is especially effective when resource constraints limit how much of the state space is reachable. Experimental results demonstrate its effectiveness in the domain that motivates our research: automated planning for planetary exploration rovers.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {27–59},
numpages = {33}
}

@article{10.5555/1622716.1622717,
author = {Chernova, Sonia and Veloso, Manuela},
title = {Interactive Policy Learning through Confidence-Based Autonomy},
year = {2009},
issue_date = {January 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {34},
number = {1},
issn = {1076-9757},
abstract = {We present Confidence-Based Autonomy (CBA), an interactive algorithm for policy learning from demonstration. The CBA algorithm consists of two components which take advantage of the complimentary abilities of humans and computer agents. The first component, Confident Execution, enables the agent to identify states in which demonstration is required, to request a demonstration from the human teacher and to learn a policy based on the acquired data. The algorithm selects demonstrations based on a measure of action selection confidence, and our results show that using Confident Execution the agent requires fewer demonstrations to learn the policy than when demonstrations are selected by a human teacher. The second algorithmic component, Corrective Demonstration, enables the teacher to correct any mistakes made by the agent through additional demonstrations in order to improve the policy and future task performance. CBA and its individual components are compared and evaluated in a complex simulated driving domain. The complete CBA algorithm results in the best overall learning performance, successfully reproducing the behavior of the teacher while balancing the tradeoff between number of demonstrations and number of incorrect actions during learning.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–25},
numpages = {25}
}

@article{10.5555/1622698.1622715,
author = {Turney, Peter D.},
title = {The Latent Relation Mapping Engine: Algorithm and Experiments},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {Many AI researchers and cognitive scientists have argued that analogy is the core of cognition. The most influential work on computational modeling of analogy-making is Structure Mapping Theory (SMT) and its implementation in the Structure Mapping Engine (SME). A limitation of SME is the requirement for complex hand-coded representations. We introduce the Latent Relation Mapping Engine (LRME), which combines ideas from SME and Latent Relational Analysis (LRA) in order to remove the requirement for hand-coded representations. LRME builds analogical mappings between lists of words, using a large corpus of raw text to automatically discover the semantic relations among the words. We evaluate LRME on a set of twenty analogical mapping problems, ten based on scientific analogies and ten based on common metaphors. LRME achieves human-level performance on the twenty problems. We compare LRME with a variety of alternative approaches and find that they are not able to reach the same level of performance.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {615–655},
numpages = {41}
}

@article{10.5555/1622698.1622714,
author = {Ashlagi, Itai and Monderer, Dov and Tennenholtz, Moshe},
title = {On the Value of Correlation},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {Correlated equilibrium generalizes Nash equilibrium to allow correlation devices. Correlated equilibrium captures the idea that in many systems there exists a trusted administrator who can recommend behavior to a set of agents, but can not enforce such behavior. This makes this solution concept most appropriate to the study of multi-agent systems in AI. Aumann showed an example of a game, and of a correlated equilibrium in this game in which the agents' welfare (expected sum of players' utilities) is greater than their welfare in all mixed-strategy equilibria. Following the idea initiated by the price of anarchy literature this suggests the study of two major measures for the value of correlation in a game with nonnegative payoffs: 1. The ratio between the maximal welfare obtained in a correlated equilibrium to the maximal welfare obtained in a mixed-strategy equilibrium. We refer to this ratio as the mediation value. 2. The ratio between the maximal welfare to the maximal welfare obtained in a correlated equilibrium. We refer to this ratio as the enforcement value. In this work we initiate the study of the mediation and enforcement values, providing several general results on the value of correlation as captured by these concepts. We also present a set of results for the more specialized case of congestion games, a class of games that received a lot of attention in the recent literature.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {575–613},
numpages = {39}
}

@article{10.5555/1622698.1622713,
author = {de Jong, Steven and Uyttendaele, Simon and Tuyls, Karl},
title = {Learning to Reach Agreement in a Continuous Ultimatum Game},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {It is well-known that acting in an individually rational manner, according to the principles of classical game theory, may lead to sub-optimal solutions in a class of problems named social dilemmas. In contrast, humans generally do not have much difficulty with social dilemmas, as they are able to balance personal benefit and group benefit. As agents in multi-agent systems are regularly confronted with social dilemmas, for instance in tasks such as resource allocation, these agents may benefit from the inclusion of mechanisms thought to facilitate human fairness. Although many of such mechanisms have already been implemented in a multi-agent systems context, their application is usually limited to rather abstract social dilemmas with a discrete set of available strategies (usually two). Given that many real-world examples of social dilemmas are actually continuous in nature, we extend this previous work to more general dilemmas, in which agents operate in a continuous strategy space. The social dilemma under study here is the well-known Ultimatum Game, in which an optimal solution is achieved if agents agree on a common strategy. We investigate whether a scale-free interaction network facilitates agents to reach agreement, especially in the presence of fixed-strategy agents that represent a desired (e.g. human) outcome. Moreover, we study the influence of rewiring in the interaction network. The agents are equipped with continuous-action learning automata and play a large number of random pairwise games in order to establish a common strategy. From our experiments, we may conclude that results obtained in discrete-strategy games can be generalized to continuous-strategy games to a certain extent: a scale-free interaction network structure allows agents to achieve agreement on a common strategy, and rewiring in the interaction network greatly enhances the agents' ability to reach agreement. However, it also becomes clear that some alternative mechanisms, such as reputation and volunteering, have many subtleties involved and do not have convincing beneficial effects in the continuous case.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {551–574},
numpages = {24}
}

@article{10.5555/1622698.1622712,
author = {Abdallah, Sherief and Lesser, Victor},
title = {A Multiagent Reinforcement Learning Algorithm with Non-Linear Dynamics},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {Several multiagent reinforcement learning (MARL) algorithms have been proposed to optimize agents' decisions. Due to the complexity of the problem, the majority of the previously developed MARL algorithms assumed agents either had some knowledge of the underlying game (such as Nash equilibria) and/or observed other agents actions and the rewards they received.We introduce a new MARL algorithm called theWeighted Policy Learner (WPL), which allows agents to reach a Nash Equilibrium (NE) in benchmark 2-player-2-action games with minimum knowledge. Using WPL, the only feedback an agent needs is its own local reward (the agent does not observe other agents actions or rewards). Furthermore, WPL does not assume that agents know the underlying game or the corresponding Nash Equilibrium a priori. We experimentally show that our algorithm converges in benchmark two-player-two-action games. We also show that our algorithm converges in the challenging Shapley's game where previous MARL algorithms failed to converge without knowing the underlying game or the NE. Furthermore, we show that WPL outperforms the state-of-the-art algorithms in a more realistic setting of 100 agents interacting and learning concurrently.An important aspect of understanding the behavior of a MARL algorithm is analyzing the dynamics of the algorithm: how the policies of multiple learning agents evolve over time as agents interact with one another. Such an analysis not only verifies whether agents using a given MARL algorithm will eventually converge, but also reveals the behavior of the MARL algorithm prior to convergence. We analyze our algorithm in two-player-two-action games and show that symbolically proving WPL's convergence is difficult, because of the non-linear nature of WPL's dynamics, unlike previous MARL algorithms that had either linear or piece-wise-linear dynamics. Instead, we numerically solve WPL's dynamics differential equations and compare the solution to the dynamics of previous MARL algorithms.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {521–549},
numpages = {29}
}

@article{10.5555/1622698.1622711,
author = {Mateescu, Robert and Dechter, Rina and Marinescu, Radu},
title = {AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Graphical Models},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {Inspired by the recently introduced framework of AND/OR search spaces for graphical models, we propose to augment Multi-Valued Decision Diagrams (MDD) with AND nodes, in order to capture function decomposition structure and to extend these compiled data structures to general weighted graphical models (e.g., probabilistic models). We present the AND/OR Multi-Valued Decision Diagram (AOMDD) which compiles a graphical model into a canonical form that supports polynomial (e.g., solution counting, belief updating) or constant time (e.g. equivalence of graphical models) queries. We provide two algorithms for compiling the AOMDD of a graphical model. The first is search-based, and works by applying reduction rules to the trace of the memory intensive AND/OR search algorithm. The second is inference-based and uses a Bucket Elimination schedule to combine the AOMDDs of the input functions via the the APPLY operator. For both algorithms, the compilation time and the size of the AOMDD are, in the worst case, exponential in the treewidth of the graphical model, rather than pathwidth as is known for ordered binary decision diagrams (OBDDs). We introduce the concept of semantic treewidth, which helps explain why the size of a decision diagram is often much smaller than the worst case bound. We provide an experimental evaluation that demonstrates the potential of AOMDDs.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {465–519},
numpages = {55}
}

@article{10.5555/1622698.1622710,
author = {Zhang, Dongmo and Zhang, Yan},
title = {An Ordinal Bargaining Solution with Fixed-Point Property},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {Shapley's impossibility result indicates that the two-person bargaining problem has no non-trivial ordinal solution with the traditional game-theoretic bargaining model. Although the result is no longer true for bargaining problems with more than two agents, none of the well known bargaining solutions are ordinal. Searching for meaningful ordinal solutions, especially for the bilateral bargaining problem, has been a challenging issue in bargaining theory for more than three decades. This paper proposes a logic-based ordinal solution to the bilateral bargaining problem. We argue that if a bargaining problem is modeled in terms of the logical relation of players' physical negotiation items, a meaningful bargaining solution can be constructed based on the ordinal structure of bargainers' preferences. We represent bargainers' demands in propositional logic and bargainers' preferences over their demands in total preorder. We show that the solution satisfies most desirable logical properties, such as individual rationality (logical version), consistency, collective rationality as well as a few typical game-theoretic properties, such as weak Pareto optimality and contraction invariance. In addition, if all players' demand sets are logically closed, the solution satisfies a fixed-point condition, which says that the outcome of a negotiation is the result of mutual belief revision. Finally, we define various decision problems in relation to our bargaining model and study their computational complexity.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {433–464},
numpages = {32}
}

@article{10.5555/1622698.1622709,
author = {Goldsmith, Judy and Lang, J\'{e}r\^{o}me and Truszczynski, Miroslaw and Wilson, Nic},
title = {The Computational Complexity of Dominance and Consistency in CP-Nets},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {403–432},
numpages = {30}
}

@article{10.5555/1622698.1622708,
author = {Amir, Eyal and Chang, Allen},
title = {Learning Partially Observable Deterministic Action Models},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {We present exact algorithms for identifying deterministic-actions' effects and preconditions in dynamic partially observable domains. They apply when one does not know the action model (the way actions affect the world) of a domain and must learn it from partial observations over time. Such scenarios are common in real world applications. They are challenging for AI tasks because traditional domain structures that underly tractability (e.g., conditional independence) fail there (e.g., world features become correlated). Our work departs from traditional assumptions about partial observations and action models. In particular, it focuses on problems in which actions are deterministic of simple logical structure and observation models have all features observed with some frequency. We yield tractable algorithms for the modified problem for such domains.Our algorithms take sequences of partial observations over time as input, and output deterministic action models that could have lead to those observations. The algorithms output all or one of those models (depending on our choice), and are exact in that no model is misclassified given the observations. Our algorithms take polynomial time in the number of time steps and state features for some traditional action classes examined in the AI-planning literature, e.g., STRIPS actions. In contrast, traditional approaches for HMMs and Reinforcement Learning are inexact and exponentially intractable for such domains. Our experiments verify the theoretical tractability guarantees, and show that we identify action models exactly. Several applications in planning, autonomous exploration, and adventure-game playing already use these results. They are also promising for probabilistic settings, partially observable reinforcement learning, and diagnosis.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {349–402},
numpages = {54}
}

@article{10.5555/1622698.1622707,
author = {Kakas, Antonis and Mancarella, Paolo and Sadri, Fariba and Stathis, Kostas and Toni, Francesca},
title = {Computational Logic Foundations of KGP Agents},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {This paper presents the computational logic foundations of a model of agency called the KGP (Knowledge, Goals and Plan) model. This model allows the specification of heterogeneous agents that can interact with each other, and can exhibit both proactive and reactive behaviour allowing them to function in dynamic environments by adjusting their goals and plans when changes happen in such environments. KGP provides a highly modular agent architecture that integrates a collection of reasoning and physical capabilities, synthesised within transitions that update the agent's state in response to reasoning, sensing and acting. Transitions are orchestrated by cycle theories that specify the order in which transitions are executed while taking into account the dynamic context and agent preferences, as well as selection operators for providing inputs to transitions.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {285–348},
numpages = {64}
}

@article{10.5555/1622698.1622706,
author = {Rezek, Iead and Leslie, David S. and Reece, Steven and Roberts, Stephen J. and Rogers, Alex and Dash, Rajdeep K. and Jennings, Nicholas R.},
title = {On Similarities between Inference in Game Theory and Machine Learning},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we elucidate the equivalence between inference in game theory and machine learning. Our aim in so doing is to establish an equivalent vocabulary between the two domains so as to facilitate developments at the intersection of both fields, and as proof of the usefulness of this approach, we use recent developments in each field to make useful improvements to the other. More specifically, we consider the analogies between smooth best responses in fictitious play and Bayesian inference methods. Initially, we use these insights to develop and demonstrate an improved algorithm for learning in games based on probabilistic moderation. That is, by integrating over the distribution of opponent strategies (a Bayesian approach within machine learning) rather than taking a simple empirical average (the approach used in standard fictitious play) we derive a novel moderated fictitious play algorithm and show that it is more likely than standard fictitious play to converge to a payoff-dominant but risk-dominated Nash equilibrium in a simple coordination game. Furthermore we consider the converse case, and show how insights from game theory can be used to derive two improved mean field variational learning algorithms. We first show that the standard update rule of mean field variational learning is analogous to a Cournot adjustment within game theory. By analogy with fictitious play, we then suggest an improved update rule, and show that this results in fictitious variational play, an improved mean field variational learning algorithm that exhibits better convergence in highly or strongly connected graphical models. Second, we use a recent advance in fictitious play, namely dynamic fictitious play, to derive a derivative action variational learning algorithm, that exhibits superior convergence properties on a canonical machine learning problem (clustering a mixture distribution).},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {259–283},
numpages = {25}
}

@article{10.5555/1622698.1622705,
author = {Grinshpoun, Tal and Meisels, Amnon},
title = {Completeness and Performance of the APO Algorithm},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {Asynchronous Partial Overlay (APO) is a search algorithm that uses cooperative mediation to solve Distributed Constraint Satisfaction Problems (DisCSPs). The algorithm partitions the search into different subproblems of the DisCSP. The original proof of completeness of the APO algorithm is based on the growth of the size of the subproblems. The present paper demonstrates that this expected growth of subproblems does not occur in some situations, leading to a termination problem of the algorithm. The problematic parts in the APO algorithm that interfere with its completeness are identified and necessary modifications to the algorithm that fix these problematic parts are given. The resulting version of the algorithm, Complete Asynchronous Partial Overlay (CompAPO), ensures its completeness. Formal proofs for the soundness and completeness of CompAPO are given. A detailed performance evaluation of CompAPO comparing it to other DisCSP algorithms is presented, along with an extensive experimental evaluation of the algorithm's unique behavior. Additionally, an optimization version of the algorithm, CompOptAPO, is presented, discussed, and evaluated.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {223–258},
numpages = {36}
}

@article{10.5555/1622698.1622704,
author = {De Laet, Tinne and De Schutter, Joris and Bruyninckx, Herman},
title = {A Rigorously Bayesian Beam Model and an Adaptive Full Scan Model for Range Finders in Dynamic Environments},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {This paper proposes and experimentally validates a Bayesian network model of a range finder adapted to dynamic environments. All modeling assumptions are rigorously explained, and all model parameters have a physical interpretation. This approach results in a transparent and intuitive model. With respect to the state of the art beam model this paper: (i) proposes a different functional form for the probability of range measurements caused by unmodeled objects, (ii) intuitively explains the discontinuity encountered in the state of the art beam model, and (iii) reduces the number of model parameters, while maintaining the same representational power for experimental data. The proposed beam model is called RBBM, short for Rigorously Bayesian Beam Model. A maximum likelihood and a variational Bayesian estimator (both based on expectation-maximization) are proposed to learn the model parameters.Furthermore, the RBBM is extended to a full scan model in two steps: first, to a full scan model for static environments and next, to a full scan model for general, dynamic environments. The full scan model accounts for the dependency between beams and adapts to the local sample density when using a particle filter. In contrast to Gaussian-based state of the art models, the proposed full scan model uses a sample-based approximation. This sample-based approximation enables handling dynamic environments and capturing multimodality, which occurs even in simple static environments.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {179–222},
numpages = {44}
}

@article{10.5555/1622698.1622703,
author = {Meir, Reshef and Procaccia, Ariel D. and Rosenschein, Jeffrey S. and Zohar, Aviv},
title = {Complexity of Strategic Behavior in Multi-Winner Elections},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {Although recent years have seen a surge of interest in the computational aspects of social choice, no specific attention has previously been devoted to elections with multiple winners, e.g., elections of an assembly or committee. In this paper, we characterize the worst-case complexity of manipulation and control in the context of four prominent multiwinner voting systems, under different formulations of the strategic agent's goal.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {149–178},
numpages = {30}
}

@article{10.5555/1622698.1622702,
author = {Gal, Ya'akov and Pfeffer, Avi},
title = {Networks of Influence Diagrams: A Formalism for Representing Agents' Beliefs and Decision-Making Processes},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {This paper presents Networks of Influence Diagrams (NID), a compact, natural and highly expressive language for reasoning about agents' beliefs and decision-making processes. NIDs are graphical structures in which agents' mental models are represented as nodes in a network; a mental model for an agent may itself use descriptions of the mental models of other agents. NIDs are demonstrated by examples, showing how they can be used to describe conflicting and cyclic belief structures, and certain forms of bounded rationality. In an opponent modeling domain, NIDs were able to outperform other computational agents whose strategies were not known in advance. NIDs are equivalent in representation to Bayesian games but they are more compact and structured than this formalism. In particular, the equilibrium definition for NIDs makes an explicit distinction between agents' optimal strategies, and how they actually behave in reality.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {109–147},
numpages = {39}
}

@article{10.5555/1622698.1622701,
author = {Martinez, David and de Lacalle, Oier Lopez and Agirre, Eneko},
title = {On the Use of Automatically Acquired Examples for All-Nouns Word Sense Disambiguation},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {This article focuses on Word Sense Disambiguation (WSD), which is a Natural Language Processing task that is thought to be important for many Language Technology applications, such as Information Retrieval, Information Extraction, or Machine Translation. One of the main issues preventing the deployment of WSD technology is the lack of training examples for Machine Learning systems, also known as the Knowledge Acquisition Bottleneck. A method which has been shown to work for small samples of words is the automatic acquisition of examples. We have previously shown that one of the most promising example acquisition methods scales up and produces a freely available database of 150 million examples from Web snippets for all polysemous nouns in WordNet. This paper focuses on the issues that arise when using those examples, all alone or in addition to manually tagged examples, to train a supervised WSD system for all nouns. The extensive evaluation on both lexical-sample and all-words Senseval benchmarks shows that we are able to improve over commonly used baselines and to achieve top-rank performance. The good use of the prior distributions from the senses proved to be a crucial factor.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {79–107},
numpages = {29}
}

@article{10.5555/1622698.1622700,
author = {Lubin, Benjamin and Juda, Adam I. and Cavallo, Ruggiero and Lahaie, S\'{e}bastien and Shneidman, Jeffrey and Parkes, David C.},
title = {ICE: An Expressive Iterative Combinatorial Exchange},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {We present the design and analysis of the first fully expressive, iterative combinatorial exchange (ICE). The exchange incorporates a tree-based bidding language (TBBL) that is concise and expressive for CEs. Bidders specify lower and upper bounds in TBBL on their value for different trades and refine these bounds across rounds. These bounds allow price discovery and useful preference elicitation in early rounds, and allow termination with an efficient trade despite partial information on bidder valuations. All computation in the exchange is carefully optimized to exploit the structure of the bid-trees and to avoid enumerating trades. A proxied interpretation of a revealed-preference activity rule, coupled with simple linear prices, ensures progress across rounds. The exchange is fully implemented, and we give results demonstrating several aspects of its scalability and economic properties with simulated bidding strategies.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {33–77},
numpages = {45}
}

@article{10.5555/1622698.1622699,
author = {Esmeir, Saher and Markovitch, Shaul},
title = {Anytime Induction of Low-Cost, Low-Error Classifiers: A Sampling-Based Approach},
year = {2008},
issue_date = {September 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {33},
number = {1},
issn = {1076-9757},
abstract = {Machine learning techniques are gaining prevalence in the production of a wide range of classifiers for complex real-world applications with nonuniform testing and misclassification costs. The increasing complexity of these applications poses a real challenge to resource management during learning and classification. In this work we introduce ACT (anytime cost-sensitive tree learner), a novel framework for operating in such complex environments. ACT is an anytime algorithm that allows learning time to be increased in return for lower classification costs. It builds a tree top-down and exploits additional time resources to obtain better estimations for the utility of the different candidate splits. Using sampling techniques, ACT approximates the cost of the subtree under each candidate split and favors the one with a minimal cost. As a stochastic algorithm, ACT is expected to be able to escape local minima, into which greedy methods may be trapped. Experiments with a variety of datasets were conducted to compare ACT to the state-of-the-art cost-sensitive tree learners. The results show that for the majority of domains ACT produces significantly less costly trees. ACT also exhibits good anytime behavior with diminishing returns.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1–31},
numpages = {31}
}

@article{10.5555/1622673.1622697,
author = {Gerding, Enrico H. and Dash, Rajdeep K. and Byde, Andrew and Jennings, Nicholas R.},
title = {Optimal Strategies for Bidding Agents Participating in Simultaneous Vickrey Auctions with Perfect Substitutes},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {We derive optimal strategies for a bidding agent that participates in multiple, simultaneous second-price auctions with perfect substitutes. We prove that, if everyone else bids locally in a single auction, the global bidder should always place non-zero bids in all available auctions, provided there are no budget constraints. With a budget, however, the optimal strategy is to bid locally if this budget is equal or less than the valuation. Furthermore, for a wide range of valuation distributions, we prove that the problem of finding the optimal bids reduces to two dimensions if all auctions are identical. Finally, we address markets with both sequential and simultaneous auctions, non-identical auctions, and the allocative efficiency of the market.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {939–982},
numpages = {44}
}

@article{10.5555/1622673.1622696,
author = {Moore, Neil C. A. and Prosser, Patrick},
title = {The Ultrametric Constraint and Its Application to Phylogenetics},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {A phylogenetic tree shows the evolutionary relationships among species. Internal nodes of the tree represent speciation events and leaf nodes correspond to species. A goal of phylogenetics is to combine such trees into larger trees, called supertrees, whilst respecting the relationships in the original trees. A rooted tree exhibits an ultrametric property; that is, for any three leaves of the tree it must be that one pair has a deeper most recent common ancestor than the other pairs, or that all three have the same most recent common ancestor. This inspires a constraint programming encoding for rooted trees. We present an efficient constraint that enforces the ultrametric property over a symmetric array of constrained integer variables, with the inevitable property that the lower bounds of any three variables are mutually supportive. We show that this allows an efficient constraint-based solution to the supertree construction problem. We demonstrate that the versatility of constraint programming can be exploited to allow solutions to variants of the supertree construction problem.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {901–938},
numpages = {38}
}

@article{10.5555/1622673.1622695,
author = {Wang, Yi and Zhang, Nevin L. and Chen, Tao},
title = {Latent Tree Models and Approximate Inference in Bayesian Networks},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {We propose a novel method for approximate inference in Bayesian networks (BNs). The idea is to sample data from a BN, learn a latent tree model (LTM) from the data offline, and when online, make inference with the LTM instead of the original BN. Because LTMs are tree-structured, inference takes linear time. In the meantime, they can represent complex relationship among leaf nodes and hence the approximation accuracy is often good. Empirical evidence shows that our method can achieve good approximation accuracy at low online computational cost.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {879–900},
numpages = {22}
}

@article{10.5555/1622673.1622694,
author = {Coghill, George M. and Srinivasan, Ashwin and King, Ross D.},
title = {Qualitative System Identification from Imperfect Data},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {Experience in the physical sciences suggests that the only realistic means of understanding complex systems is through the use of mathematical models. Typically, this has come to mean the identification of quantitative models expressed as differential equations. Quantitative modelling works best when the structure of the model (i.e., the form of the equations) is known; and the primary concern is one of estimating the values of the parameters in the model. For complex biological systems, the model-structure is rarely known and the modeler has to deal with both model-identification and parameter-estimation. In this paper we are concerned with providing automated assistance to the first of these problems. Specifically, we examine the identification by machine of the structural relationships between experimentally observed variables. These relationship will be expressed in the form of qualitative abstractions of a quantitative model. Such qualitative models may not only provide clues to the precise quantitative model, but also assist in understanding the essence of that model. Our position in this paper is that background knowledge incorporating system modelling principles can be used to constrain effectively the set of good qualitative models. Utilising the model-identification framework provided by Inductive Logic Programming (ILP) we present empirical support for this position using a series of increasingly complex artificial datasets. The results are obtained with qualitative and quantitative data subject to varying amounts of noise and different degrees of sparsity. The results also point to the presence of a set of qualitative states, which we term kernel subsets, that may be necessary for a qualitative model-learner to learn correct models. We demonstrate scalability of the method to biological system modelling by identification of the glycolysis metabolic pathway from data.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {825–877},
numpages = {53}
}

@article{10.5555/1622673.1622693,
author = {Miclet, Laurent and Bayoudh, Sabri and Delhay, Arnaud},
title = {Analogical Dissimilarity},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {This paper defines the notion of analogical dissimilarity between four objects, with a special focus on objects structured as sequences. Firstly, it studies the case where the four objects have a null analogical dissimilarity, i.e. are in analogical proportion. Secondly, when one of these objects is unknown, it gives algorithms to compute it. Thirdly, it tackles the problem of defining analogical dissimilarity, which is a measure of how far four objects are from being in analogical proportion. In particular, when objects are sequences, it gives a definition and an algorithm based on an optimal alignment of the four sequences. It gives also learning algorithms, i.e. methods to find the triple of objects in a learning sample which has the least analogical dissimilarity with a given object. Two practical experiments are described: the first is a classification problem on benchmarks of binary and nominal data, the second shows how the generation of sequences by solving analogical equations enables a handwritten character recognition system to rapidly be adapted to a new writer.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {793–824},
numpages = {32}
}

@article{10.5555/1622673.1622692,
author = {Delgrande, James and Jin, Yi and Pelletier, Francis Jeffry},
title = {Compositional Belief Update},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {In this paper we explore a class of belief update operators, in which the definition of the operator is compositional with respect to the sentence to be added. The goal is to provide an update operator that is intuitive, in that its definition is based on a recursive decomposition of the update sentence's structure, and that may be reasonably implemented. In addressing update, we first provide a definition phrased in terms of the models of a knowledge base. While this operator satisfies a core group of the benchmark Katsuno-Mendelzon update postulates, not all of the postulates are satisfied. Other Katsuno-Mendelzon postulates can be obtained by suitably restricting the syntactic form of the sentence for update, as we show. In restricting the syntactic form of the sentence for update, we also obtain a hierarchy of update operators withWinslett's standard semantics as the most basic interesting approach captured. We subsequently give an algorithm which captures this approach; in the general case the algorithm is exponential, but with some not-unreasonable assumptions we obtain an algorithm that is linear in the size of the knowledge base. Hence the resulting approach has much better complexity characteristics than other operators in some situations. We also explore other compositional belief change operators: erasure is developed as a dual operator to update; we show that a forget operator is definable in terms of update; and we give a definition of the compositional revision operator. We obtain that compositional revision, under the most natural definition, yields the Satoh revision operator.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {757–791},
numpages = {35}
}

@article{10.5555/1622673.1622691,
author = {Petcu, Adrian and Faltings, Boi and Parkes, David C.},
title = {M-DPOP: Faithful Distributed Implementation of Efficient Social Choice Problems},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {In the efficient social choice problem, the goal is to assign values, subject to side constraints, to a set of variables to maximize the total utility across a population of agents, where each agent has private information about its utility function. In this paper we model the social choice problem as a distributed constraint optimization problem (DCOP), in which each agent can communicate with other agents that share an interest in one or more variables. Whereas existing DCOP algorithms can be easily manipulated by an agent, either by misreporting private information or deviating from the algorithm, we introduce M-DPOP, the first DCOP algorithm that provides a faithful distributed implementation for efficient social choice. This provides a concrete example of how the methods of mechanism design can be unified with those of distributed optimization. Faithfulness ensures that no agent can benefit by unilaterally deviating from any aspect of the protocol, neither information-revelation, computation, nor communication, and whatever the private information of other agents. We allow for payments by agents to a central bank, which is the only central authority that we require. To achieve faithfulness, we carefully integrate the Vickrey-Clarke-Groves (VCG) mechanism with the DPOP algorithm, such that each agent is only asked to perform computation, report information, and send messages that is in its own best interest. Determining agent i's payment requires solving the social choice problem without agent i. Here, we present a method to reuse computation performed in solving the main problem in a way that is robust against manipulation by the excluded agent. Experimental results on structured problems show that as much as 87% of the computation required for solving the marginal problems can be avoided by re-use, providing very good scalability in the number of agents. On unstructured problems, we observe a sensitivity of M-DPOP to the density of the problem, and we show that reusability decreases from almost 100% for very sparse problems to around 20% for highly connected problems. We close with a discussion of the features of DCOP that enable faithful implementations in this problem, the challenge of reusing computation from the main problem to marginal problems in other algorithms such as ADOPT and OptAPO, and the prospect of methods to avoid the welfare loss that can occur because of the transfer of payments to the bank.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {705–755},
numpages = {51}
}

@article{10.5555/1622673.1622690,
author = {Ross, St\'{e}phane and Pineau, Joelle and Paquet, S\'{e}bastien and Chaib-draa, Brahim},
title = {Online Planning Algorithms for POMDPs},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {Partially Observable Markov Decision Processes (POMDPs) provide a rich framework for sequential decision-making under uncertainty in stochastic domains. However, solving a POMDP is often intractable except for small problems due to their complexity. Here, we focus on online approaches that alleviate the computational complexity by computing good local policies at each decision step during the execution. Online algorithms generally consist of a lookahead search to find the best action to execute at each time step in an environment. Our objectives here are to survey the various existing online POMDP methods, analyze their properties and discuss their advantages and disadvantages; and to thoroughly evaluate these online approaches in different environments under various metrics (return, error bound reduction, lower bound improvement). Our experimental results indicate that state-of-the-art online heuristic search methods can handle large POMDP domains efficiently.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {663–704},
numpages = {42}
}

@article{10.5555/1622673.1622689,
author = {Yang, Fan and Culberson, Joseph and Holte, Robert and Zahavi, Uzi and Felner, Ariel},
title = {A General Theory of Additive State Space Abstractions},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {Informally, a set of abstractions of a state space S is additive if the distance between any two states in S is always greater than or equal to the sum of the corresponding distances in the abstract spaces. The first known additive abstractions, called disjoint pattern databases, were experimentally demonstrated to produce state of the art performance on certain state spaces. However, previous applications were restricted to state spaces with special properties, which precludes disjoint pattern databases from being defined for several commonly used testbeds, such as Rubik's Cube, TopSpin and the Pancake puzzle. In this paper we give a general definition of additive abstractions that can be applied to any state space and prove that heuristics based on additive abstractions are consistent as well as admissible. We use this new definition to create additive abstractions for these testbeds and show experimentally that well chosen additive abstractions can reduce search time substantially for the (18,4)-TopSpin puzzle and by three orders of magnitude over state of the art methods for the 17-Pancake puzzle. We also derive a way of testing if the heuristic value returned by additive abstractions is provably too low and show that the use of this test can reduce search time for the 15-puzzle and TopSpin by roughly a factor of two.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {631–662},
numpages = {32}
}

@article{10.5555/1622673.1622688,
author = {Bordeaux, Lucas and Cadoli, Marco and Mancini, Toni},
title = {A Unifying Framework for Structural Properties of CSPs: Definitions, Complexity, Tractabilit},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {Literature on Constraint Satisfaction exhibits the definition of several "structural" properties that can be possessed by CSPs, like (in)consistency, substitutability or interchangeability. Current tools for constraint solving typically detect such properties efficiently by means of incomplete yet effective algorithms, and use them to reduce the search space and boost search.In this paper, we provide a unifying framework encompassing most of the properties known so far, both in CSP and other fields' literature, and shed light on the semantical relationships among them. This gives a unified and comprehensive view of the topic, allows new, unknown, properties to emerge, and clarifies the computational complexity of the various detection problems.In particular, among the others, two new concepts, fixability and removability emerge, that come out to be the ideal characterisations of values that may be safely assigned or removed from a variable's domain, while preserving problem satisfiability. These two notions subsume a large number of known properties, including inconsistency, substitutability and others.Because of the computational intractability of all the property-detection problems, by following the CSP approach we then determine a number of relaxations which provide sufficient conditions for their tractability. In particular, we exploit forms of language restrictions and local reasoning.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {607–629},
numpages = {23}
}

@article{10.5555/1622673.1622687,
author = {Xu, Lin and Hutter, Frank and Hoos, Holger H. and Leyton-Brown, Kevin},
title = {SATzilla: Portfolio-Based Algorithm Selection for SAT},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {It has been widely observed that there is no single "dominant" SAT solver; instead, different solvers perform best on different instances. Rather than following the traditional approach of choosing the best solver for a given class of instances, we advocate making this decision online on a per-instance basis. Building on previous work, we describe SATzilla, an automated approach for constructing per-instance algorithm portfolios for SAT that use so-called empirical hardness models to choose among their constituent solvers. This approach takes as input a distribution of problem instances and a set of component solvers, and constructs a portfolio optimizing a given objective function (such as mean runtime, percent of instances solved, or score in a competition). The excellent performance of SATzilla was independently verified in the 2007 SAT Competition, where our SATzilla07 solvers won three gold, one silver and one bronze medal. In this article, we go well beyond SATzilla07 by making the portfolio construction scalable and completely automated, and improving it

license_type: permissive

branch_name: refs/heads/main

extension: bib