text:
as well as prior BWE-based models, and acquire the best reported results on both tasks for all three tested language pairs.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {953–994},
numpages = {42}
}

@article{10.5555/3013558.3013582,
author = {Flerova, Natalia and Marinescu, Radu and Dechter, Rina},
title = {Searching for the M Best Solutions in Graphical Models},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {The paper focuses on finding the m best solutions to combinatorial optimization problems using best-first or depth-first branch and bound search. Specifically, we present a new algorithm m-A*, extending the well-known A* to the m-best task, and for the first time prove that all its desirable properties, including soundness, completeness and optimal efficiency, are maintained. Since best-first algorithms require extensive memory, we also extend the memory-efficient depth-first branch and bound to the m-best task.We adapt both algorithms to optimization tasks over graphical models (e.g., Weighted CSP and MPE in Bayesian networks), provide complexity analysis and an empirical evaluation. Our experiments confirm theory that the best-first approach is largely superior when memory is available, but depth-first branch and bound is more robust. We also show that our algorithms are competitive with related schemes recently developed for the m-best task.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {889–952},
numpages = {64}
}

@article{10.5555/3013558.3013581,
author = {Jannach, Dietmar and Schmitz, Thomas and Shchekotykhin, Kostyantyn},
title = {Parallel Model-Based Diagnosis on Multi-Core Computers},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Model-Based Diagnosis (MBD) is a principled and domain-independent way of analyzing why a system under examination is not behaving as expected. Given an abstract description (model) of the system's components and their behavior when functioning normally, MBD techniques rely on observations about the actual system behavior to reason about possible causes when there are discrepancies between the expected and observed behavior. Due to its generality, MBD has been successfully applied in a variety of application domains over the last decades.In many application domains of MBD, testing different hypotheses about the reasons for a failure can be computationally costly, e.g., because complex simulations of the system behavior have to be performed. In this work, we therefore propose different schemes of parallelizing the diagnostic reasoning process in order to better exploit the capabilities of modern multi-core computers. We propose and systematically evaluate parallelization schemes for Reiter's hitting set algorithm for finding all or a few leading minimal diagnoses using two different con flict detection techniques. Furthermore, we perform initial experiments for a basic depth-first search strategy to assess the potential of parallelization when searching for one single diagnosis. Finally, we test the effects of parallelizing "direct encodings" of the diagnosis problem in a constraint solver.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {835–887},
numpages = {53}
}

@article{10.5555/3013558.3013580,
author = {Fang, Zhiwen and Li, Chu-Min and Xu, Ke},
title = {An Exact Algorithm Based on MaxSAT Reasoning for the Maximum Weight Clique Problem},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Recently, MaxSAT reasoning is shown very effective in computing a tight upper bound for a Maximum Clique (MC) of a (unweighted) graph. In this paper, we apply MaxSAT reasoning to compute a tight upper bound for a Maximum Weight Clique (MWC) of a wighted graph. We first study three usual encodings of MWC into weighted partial MaxSAT dealing with hard clauses, which must be satisfied in all solutions, and soft clauses, which are weighted and can be falsified. The drawbacks of these encodings motivate us to propose an encoding of MWC into a special weighted partial MaxSAT formalism, called LW (Literal-Weighted) encoding and dedicated for upper bounding an MWC, in which both soft clauses and literals in soft clauses are weighted. An optimal solution of the LW MaxSAT instance gives an upper bound for an MWC, instead of an optimal solution for MWC. We then introduce two notions called the Top-k literal failed clause and the Top-k empty clause to extend classical MaxSAT reasoning techniques, as well as two sound transformation rules to transform an LW MaxSAT instance. Successive transformations of an LW MaxSAT instance driven by MaxSAT reasoning give a tight upper bound for the encoded MWC. The approach is implemented in a branch-and-bound algorithm called MWCLQ. Experimental evaluations on the broadly used DIMACS benchmark, BHOSLIB benchmark, random graphs and the benchmark from the winner determination problem show that our approach allows MWCLQ to reduce the search space significantly and to solve MWC instances effectively. Consequently, MWCLQ outperforms state-of-the-art exact algorithms on the vast majority of instances. Moreover, it is surprisingly effective in solving hard and dense instances.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {799–833},
numpages = {35}
}

@article{10.5555/3013558.3013579,
author = {Parisi, Francesco and Grant, John},
title = {Knowledge Representation in Probabilistic Spatio-Temporal Knowledge Bases},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {We represent knowledge as integrity constraints in a formalization of probabilistic spatio-temporal knowledge bases. We start by defining the syntax and semantics of a formalization called PST knowledge bases. This definition generalizes an earlier version, called SPOT, which is a declarative framework for the representation and processing of probabilistic spatio-temporal data where probability is represented as an interval because the exact value is unknown. We augment the previous definition by adding a type of non-atomic formula that expresses integrity constraints. The result is a highly expressive formalism for knowledge representation dealing with probabilistic spatio-temporal data. We obtain complexity results both for checking the consistency of PST knowledge bases and for answering queries in PST knowledge bases, and also specify tractable cases. All the domains in the PST framework are finite, but we extend our results also to arbitrarily large finite domains.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {743–798},
numpages = {56}
}

@article{10.5555/3013558.3013578,
author = {Garc\'{\i}a-Dur\'{a}n, Alberto and Bordes, Antoine and Usunier, Nicolas and Grandvalet, Yves},
title = {Combining Two and Three-Way Embedding Models for Link Prediction in Knowledge Bases},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {This paper tackles the problem of endogenous link prediction for knowledge base completion. Knowledge bases can be represented as directed graphs whose nodes correspond to entities and edges to relationships. Previous attempts either consist of powerful systems with high capacity to model complex connectivity patterns, which unfortunately usually end up overfitting on rare relationships, or in approaches that trade capacity for simplicity in order to fairly model all relationships, frequent or not. In this paper, we propose TATEC, a happy medium obtained by complementing a high-capacity model with a simpler one, both pre-trained separately and then combined. We present several variants of this model with different kinds of regularization and combination strategies and show that this approach outperforms existing methods on different types of relationships by achieving state-of-the-art results on four benchmarks of the literature.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {715–742},
numpages = {28}
}

@article{10.5555/3013558.3013577,
author = {De Nijs, Roderick and Landsiedel, Christian and Wollher, Dirk and Buss, Martin},
title = {Quadratization and Roof Duality of Markov Logic Networks},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {This article discusses the quadratization of Markov Logic Networks, which enables efficient approximate MAP computation by means of maximum ows. The procedure relies on a pseudo-Boolean representation of the model, and allows handling models of any order. The employed pseudo-Boolean representation can be used to identify problems that are guaranteed to be solvable in low polynomial-time. Results on common benchmark problems show that the proposed approach finds optimal assignments for most variables in excellent computational time and approximate solutions that match the quality of ILP-based solvers.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {685–714},
numpages = {30}
}

@article{10.5555/3013558.3013576,
author = {Zhu, Xiaoyuan and Yuan, Changhe},
title = {Exact Algorithms for MRE Inference},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Most Relevant Explanation (MRE) is an inference task in Bayesian networks that finds the most relevant partial instantiation of target variables as an explanation for given evidence by maximizing the Generalized Bayes Factor (GBF). No exact MRE algorithm has been developed previously except exhaustive search. This paper fills the void by introducing two Breadth-First Branch-and-Bound (BFBnB) algorithms for solving MRE based on novel upper bounds of GBF. One upper bound is created by decomposing the computation of GBF using a target blanket decomposition of evidence variables. The other upper bound improves the first bound in two ways. One is to split the target blankets that are too large by converting auxiliary nodes into pseudo-targets so as to scale to large problems. The other is to perform summations instead of maximizations on some of the target variables in each target blanket. Our empirical evaluations show that the proposed BFBnB algorithms make exact MRE inference tractable in Bayesian networks that could not be solved previously.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {653–683},
numpages = {31}
}

@article{10.5555/3013558.3013575,
author = {Bredereck, Robert and Faliszewski, Piotr and Niedermeier, Rolf and Talmon, Nimrod},
title = {Large-Scale Election Campaigns: Combinatorial Shift Bribery},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {We study the complexity of a combinatorial variant of the SHIFT BRIBERY problem in elections. In the standard SHIFT BRIBERY problem, we are given an election where each voter has a preference order over the set of candidates and where an outside agent, the briber, can pay each voter to rank the briber's favorite candidate a given number of positions higher. The goal is to ensure the victory of the briber's preferred candidate. The combinatorial variant of the problem, introduced in this paper, models settings where it is possible to affect the position of the preferred candidate in multiple votes, either positively or negatively, with a single bribery action. This variant of the problem is particularly interesting in the context of large-scale campaign management problems (which, from the technical side, are modeled as bribery problems). We show that, in general, the combinatorial variant of the problem is highly intractable; specifically, NP-hard, hard in the parameterized sense, and hard to approximate. Nevertheless, we provide parameterized algorithms and approximation algorithms for natural restricted cases.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {603–652},
numpages = {50}
}

@article{10.5555/3013558.3013574,
author = {Brandt, Felix and Geist, Christian},
title = {Finding Strategyproof Social Choice Functions via SAT Solving},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {A promising direction in computational social choice is to address research problems using computer-aided proving techniques. In particular with SAT solvers, this approach has been shown to be viable not only for proving classic impossibility theorems such as Arrow's Theorem but also for finding new impossibilities in the context of preference extensions. In this paper, we demonstrate that these computer-aided techniques can also be applied to improve our understanding of strategyproof irresolute social choice functions. These functions, however, require a more evolved encoding as otherwise the search space rapidly becomes much too large. Our contribution is two-fold: We present an efficient encoding for translating such problems to SAT and leverage this encoding to prove new results about strategyproofness with respect to Kelly's and Fishburn's preference extensions. For example, we show that no Pareto-optimal majoritarian social choice function satisfies Fishburn-strategyproofness. Furthermore, we explain how human-readable proofs of such results can be extracted from minimal unsatisfiable cores of the corresponding SAT formulas.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {565–602},
numpages = {38}
}

@article{10.5555/3013558.3013573,
author = {Romero, Ana Armas and Kaminski, Mark and Grau, Bernardo Cuenca and Horrocks, Ian},
title = {Module Extraction in Expressive Ontology Languages via Datalog Reasoning},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Module extraction is the task of computing a (preferably small) fragment M of an ontology O that preserves a class of entailments over a signature of interest Σ. Extracting modules of minimal size is well-known to be computationally hard, and often algorithmically infeasible, especially for highly expressive ontology languages. Thus, practical techniques typically rely on approximations, where M provably captures the relevant entailments, but is not guaranteed to be minimal. Existing approximations ensure that M preserves all second-order entailments of O w.r.t. Σ, which is a stronger condition than is required in many applications, and may lead to unnecessarily large modules in practice. In this paper we propose a novel approach in which module extraction is reduced to a reasoning problem in datalog. Our approach generalises existing approximations in an elegant way. More importantly, it allows extraction of modules that are tailored to preserve only specific kinds of entailments, and thus are often significantly smaller. Our evaluation on a wide range of ontologies confirms the feasibility and benefits of our approach in practice.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {499–564},
numpages = {66}
}

@article{10.5555/3013558.3013572,
author = {Dibangoye, Jilles Steeve and Amato, Christopher and Buffet, Olivier and Charpillet, Fran\c{c}ois},
title = {Optimally Solving Dec-POMDPs as Continuous-State MDPs},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Decentralized partially observable Markov decision processes (Dec-POMDPs) provide a general model for decision-making under uncertainty in decentralized settings, but are difficult to solve optimally (NEXP-Complete). As a new way of solving these problems, we introduce the idea of transforming a Dec-POMDP into a continuous-state deterministic MDP with a piecewise-linear and convex value function. This approach makes use of the fact that planning can be accomplished in a centralized offline manner, while execution can still be decentralized. This new Dec-POMDP formulation, which we call an occupancy MDP, allows powerful POMDP and continuous-state MDP methods to be used for the first time. To provide scalability, we refine this approach by combining heuristic search and compact representations that exploit the structure present in multi-agent domains, without losing the ability to converge to an optimal solution. In particular, we introduce a feature-based heuristic search value iteration (FB-HSVI) algorithm that relies on feature-based compact representations, point-based updates and efficient action selection. A theoretical analysis demonstrates that FB-HSVI terminates in finite time with an optimal solution. We include an extensive empirical analysis using well-known benchmarks, thereby demonstrating that our approach provides significant scalability improvements compared to the state of the art.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {443–497},
numpages = {55}
}

@article{10.5555/3013558.3013571,
author = {Bernardi, Raffaella and Cakici, Ruket and Elliott, Desmond and Erdem, Aykut and Erdem, Erkut and Ikizler-Cinbis, Nazli and Keller, Frank and Muscat, Adrian and Plank, Barbara},
title = {Automatic Description Generation from Images: A Survey of Models, Datasets, and Evaluation Measures},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Automatic description generation from natural images is a challenging problem that has recently received a large amount of interest from the computer vision and natural language processing communities. In this survey, we classify the existing approaches based on how they conceptualize this problem, viz., models that cast description as either generation problem or as a retrieval problem over a visual or multimodal representational space. We provide a detailed review of existing models, highlighting their advantages and disadvantages. Moreover, we give an overview of the benchmark image datasets and the evaluation measures that have been developed to assess the quality of machine-generated image descriptions. Finally we extrapolate future directions in the area of automatic image description generation.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {409–442},
numpages = {34}
}

@article{10.5555/3013558.3013570,
author = {Culotta, Aron and Ravi, Nirmal Kumar and Cutler, Jennifer},
title = {Predicting Twitter User Demographics Using Distant Supervision from Website Traffic Data},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Understanding the demographics of users of online social networks has important applications for health, marketing, and public messaging. Whereas most prior approaches rely on a supervised learning approach, in which individual users are labeled with demographics for training, we instead create a distantly labeled dataset by collecting audience measurement data for 1,500 websites (e.g., 50% of visitors to gizmodo.com are estimated to have a bachelor's degree). We then fit a regression model to predict these demographics from information about the followers of each website on Twitter. Using patterns derived both from textual content and the social network of each user, our final model produces an average held-out correlation of .77 across seven different variables (age, gender, education, ethnicity, income, parental status, and political preference). We then apply this model to classify individual Twitter users by ethnicity, gender, and political preference, finding performance that is surprisingly competitive with a fully supervised approach.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {389–408},
numpages = {20}
}

@article{10.5555/3013558.3013569,
author = {Wang, Ziyu and Hutter, Frank and Zoghi, Masrour and Matheson, David and De Freitas, Nando},
title = {Bayesian Optimization in a Billion Dimensions via Random Embeddings},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Bayesian optimization techniques have been successfully applied to robotics, planning, sensor placement, recommendation, advertising, intelligent user interfaces and automatic algorithm configuration. Despite these successes, the approach is restricted to problems of moderate dimension, and several workshops on Bayesian optimization have identified its scaling to high-dimensions as one of the holy grails of the field. In this paper, we introduce a novel random embedding idea to attack this problem. The resulting Random EMbedding Bayesian Optimization (REMBO) algorithm is very simple, has important invariance properties, and applies to domains with both categorical and continuous variables. We present a thorough theoretical analysis of REMBO. Empirical results confirm that REMBO can effectively solve problems with billions of dimensions, provided the intrinsic dimensionality is low. They also show that REMBO achieves state-of-the-art performance in optimizing the 47 discrete parameters of a popular mixed integer linear programming solver.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {361–387},
numpages = {27}
}

@article{10.5555/3013558.3013568,
author = {Ho, Chien-Ju and Slivkins, Aleksandrs and Vaughan, Jennifer Wortman},
title = {Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Crowdsourcing markets have emerged as a popular platform for matching available workers with tasks to complete. The payment for a particular task is typically set by the task's requester, and may be adjusted based on the quality of the completed work, for example, through the use of "bonus" payments. In this paper, we study the requester's problem of dynamically adjusting quality-contingent payments for tasks. We consider a multi-round version of the well-known principal-agent model, whereby in each round a worker makes a strategic choice of the effort level which is not directly observable by the requester. In particular, our formulation significantly generalizes the budget-free online task pricing problems studied in prior work. We treat this problem as a multi-armed bandit problem, with each "arm" representing a potential contract. To cope with the large (and in fact, infinite) number of arms, we propose a new algorithm, AgnosticZooming, which discretizes the contract space into a finite number of regions, effectively treating each region as a single arm. This discretization is adaptively refined, so that more promising regions of the contract space are eventually discretized more finely. We analyze this algorithm, showing that it achieves regret sublinear in the time horizon and substantially improves over non-adaptive discretization (which is the only competing approach in the literature). Our results advance the state of art on several different topics: the theory of crowdsourcing markets, principal-agent problems, multi-armed bandits, and dynamic pricing.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {317–359},
numpages = {43}
}

@article{10.5555/3013558.3013567,
author = {Rupnik, Jan and Muhi\v{c}, Andrej and Leban, Gregor and \v{S}kraba, Primo\v{z} and Fortuna, Bla\v{z} and Grobelnik, Marko},
title = {News across Languages - Cross-Lingual Document Similarity and Event Tracking},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {In today's world, we follow news which is distributed globally. Significant events are reported by different sources and in different languages. In this work, we address the problem of tracking of events in a large multilingual stream. Within a recently developed system Event Registry we examine two aspects of this problem: how to compare articles in different languages and how to link collections of articles in different languages which refer to the same event. Taking a multilingual stream and clusters of articles from each language, we compare different cross-lingual document similarity measures based on Wikipedia. This allows us to compute the similarity of any two articles regardless of language. Building on previous work, we show there are methods which scale well and can compute a meaningful similarity between articles from languages with little or no direct overlap in the training data. Using this capability, we then propose an approach to link clusters of articles across languages which represent the same event. We provide an extensive evaluation of the system as a whole, as well as an evaluation of the quality and robustness of the similarity measure and the linking algorithm.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {283–316},
numpages = {34}
}

@article{10.5555/3013558.3013566,
author = {Khwileh, Ahmad and Ganguly, Debasis and Jones, Gareth J. F.},
title = {Utilisation of Metadata Fields and Query Expansion in Cross-Lingual Search of User-Generated Internet Video},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Recent years have seen significant efforts in the area of Cross Language Information Retrieval (CLIR) for text retrieval. This work initially focused on formally published content, but more recently research has begun to concentrate on CLIR for informal social media content. However, despite the current expansion in online multimedia archives, there has been little work on CLIR for this content. While there has been some limited work on Cross-Language Video Retrieval (CLVR) for professional videos, such as documentaries or TV news broadcasts, there has to date, been no significant investigation of CLVR for the rapidly growing archives of informal user generated (UGC) content. Key differences between such UGC and professionally produced content are the nature and structure of the textual UGC metadata associated with it, as well as the form and quality of the content itself. In this setting, retrieval effectiveness may not only suffer from translation errors common to all CLIR tasks, but also recognition errors associated with the automatic speech recognition (ASR) systems used to transcribe the spoken content of the video and with the informality and inconsistency of the associated user-created metadata for each video. This work proposes and evaluates techniques to improve CLIR effectiveness of such noisy UGC content. Our experimental investigation shows that different sources of evidence, e.g. the content from different fields of the structured metadata, significantly affect CLIR effectiveness. Results from our experiments also show that each metadata field has a varying robustness to query expansion (QE) and hence can have a negative impact on the CLIR effectiveness. Our work proposes a novel adaptive QE technique that predicts the most reliable source for expansion and shows how this technique can be effective for improving CLIR effectiveness for UGC content.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {249–281},
numpages = {33}
}

@article{10.5555/3013558.3013565,
author = {Tiedemann, J\"{o}rg and Agic, \v{Z}eljko},
title = {Synthetic Treebanking for Cross-Lingual Dependency Parsing},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {How do we parse the languages for which no treebanks are available? This contribution addresses the cross-lingual viewpoint on statistical dependency parsing, in which we attempt to make use of resource-rich source language treebanks to build and adapt models for the under-resourced target languages. We outline the benefits, and indicate the drawbacks of the current major approaches. We emphasize synthetic treebanking: the automatic creation of target language treebanks by means of annotation projection and machine translation. We present competitive results in cross-lingual dependency parsing using a combination of various techniques that contribute to the overall success of the method. We further include a detailed discussion about the impact of part-of-speech label accuracy on parsing results that provide guidance in practical applications of cross-lingual methods for truly under-resourced languages.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {209–248},
numpages = {40}
}

@article{10.5555/3013558.3013564,
author = {Helou, Mamoun Abu and Palmonari, Matteo and Jarrar, Mustafa},
title = {Effectiveness of Automatic Translations for Cross-Lingual Ontology Mapping},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Accessing or integrating data lexicalized in different languages is a challenge. Multilingual lexical resources play a fundamental role in reducing the language barriers to map concepts lexicalized in different languages. In this paper we present a large-scale study on the effectiveness of automatic translations to support two key cross-lingual ontology mapping tasks: the retrieval of candidate matches and the selection of the correct matches for inclusion in the final alignment. We conduct our experiments using four different large gold standards, each one consisting of a pair of mapped wordnets, to cover four different families of languages. We categorize concepts based on their lexicalization (type of words, synonym richness, position in a subconcept graph) and analyze their distributions in the gold standards. Leveraging this categorization, we measure several aspects of translation effectiveness, such as word-translation correctness, word sense coverage, synset and synonym coverage. Finally, we thoroughly discuss several findings of our study, which we believe are helpful for the design of more sophisticated cross-lingual mapping algorithms.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {165–208},
numpages = {44}
}

@article{10.5555/3013558.3013563,
author = {Fern\'{a}ndez, Alejandro Moreo and Esuli, Andrea and Sebastiani, Fabrizio},
title = {Distributional Correspondence Indexing for Cross-Lingual and Cross-Domain Sentiment Classification},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Domain Adaptation (DA) techniques aim at enabling machine learning methods learn effective classifiers for a "target" domain when the only available training data belongs to a different "source" domain. In this paper we present the Distributional Correspondence Indexing (DCI) method for domain adaptation in sentiment classification. DCI derives term representations in a vector space common to both domains where each dimension re ects its distributional correspondence to a pivot, i.e., to a highly predictive term that behaves similarly across domains. Term correspondence is quantified by means of a distributional correspondence function (DCF). We propose a number of efficient DCFs that are motivated by the distributional hypothesis, i.e., the hypothesis according to which terms with similar meaning tend to have similar distributions in text. Experiments show that DCI obtains better performance than current state-of-the-art techniques for cross-lingual and cross-domain sentiment classification. DCI also brings about a significantly reduced computational cost, and requires a smaller amount of human intervention. As a final contribution, we discuss a more challenging formulation of the domain adaptation problem, in which both the cross-domain and cross-lingual dimensions are tackled simultaneously.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {131–163},
numpages = {33}
}

@article{10.5555/3013558.3013562,
author = {Mohammad, Saif M. and Salameh, Mohammad and Kiritchenko, Svetlana},
title = {How Translation Alters Sentiment},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Sentiment analysis research has predominantly been on English texts. Thus there exist many sentiment resources for English, but less so for other languages. Approaches to improve sentiment analysis in a resource-poor focus language include: (a) translate the focus language text into a resource-rich language such as English, and apply a powerful English sentiment analysis system on the text, and (b) translate resources such as sentiment labeled corpora and sentiment lexicons from English into the focus language, and use them as additional resources in the focus-language sentiment analysis system. In this paper we systematically examine both options. We use Arabic social media posts as stand-in for the focus language text. We show that sentiment analysis of English translations of Arabic texts produces competitive results, w.r.t. Arabic sentiment analysis. We show that Arabic sentiment analysis systems benefit from the use of automatically translated English sentiment lexicons. We also conduct manual annotation studies to examine why the sentiment of a translation is different from the sentiment of the source word or text. This is especially relevant for building better automatic translation systems. In the process, we create a state-of-the-art Arabic sentiment analysis system, a new dialectal Arabic sentiment lexicon, and the first Arabic-English parallel corpus that is independently annotated for sentiment by Arabic and English speakers.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {95–130},
numpages = {36}
}

@article{10.5555/3013558.3013561,
author = {Tsvetkov, Yulia and Dyer, Chris},
title = {Cross-Lingual Bridges with Models of Lexical Borrowing},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Linguistic borrowing is the phenomenon of transferring linguistic constructions (lexical, phonological, morphological, and syntactic) from a "donor" language to a "recipient" language as a result of contacts between communities speaking different languages. Borrowed words are found in all languages, and--in contrast to cognate relationships--borrowing relationships may exist across unrelated languages (for example, about 40% of Swahili's vocabulary is borrowed from the unrelated language Arabic). In this work, we develop a model of morpho-phonological transformations across languages. Its features are based on universal constraints from Optimality Theory (OT), and we show that compared to several standard--but linguistically more na\"{\i}ve--baselines, our OT-inspired model obtains good performance at predicting donor forms from borrowed forms with only a few dozen training examples, making this a cost-effective strategy for sharing lexical information across languages. We demonstrate applications of the lexical borrowing model in machine translation, using resource-rich donor language to obtain translations of out-of-vocabulary loanwords in a lower resource language. Our framework obtains substantial improvements (up to 1.6 BLEU) over standard baselines.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {63–93},
numpages = {31}
}

@article{10.5555/3013558.3013560,
author = {S\'{a}nchez-Cartagena, V\'{\i}ctor M. and P\'{e}rez-Ortiz, Juan Antonio and S\'{a}nchez-Mart\'{\i}nez, Felipe},
title = {Integrating Rules and Dictionaries from Shallow-Transfer Machine Translation into Phrase-Based Statistical Machine Translation},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {We describe a hybridisation strategy whose objective is to integrate linguistic resources from shallow-transfer rule-based machine translation (RBMT) into phrase-based statistical machine translation (PBSMT). It basically consists of enriching the phrase table of a PBSMT system with bilingual phrase pairs matching transfer rules and dictionary entries from a shallow-transfer RBMT system. This new strategy takes advantage of how the linguistic resources are used by the RBMT system to segment the source-language sentences to be translated, and overcomes the limitations of existing hybrid approaches that treat the RBMT systems as a black box. Experimental results confirm that our approach delivers translations of higher quality than existing ones, and that it is specially useful when the parallel corpus available for training the SMT system is small or when translating out-of-domain texts that are well covered by the RBMT dictionaries. A combination of this approach with a recently proposed unsupervised shallow-transfer rule inference algorithm results in a significantly greater translation quality than that of a baseline PBSMT; in this case, the only hand-crafted resource used are the dictionaries commonly used in RBMT. Moreover, the translation quality achieved by the hybrid system built with automatically inferred rules is similar to that obtained by those built with hand-crafted rules.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {17–61},
numpages = {45}
}

@article{10.5555/3013558.3013559,
author = {Costa-juss\`{a}, Marta R. and Bangalore, Srinivas and Lambert, Patrik and M\`{a}rquez, Llu\'{\i}s and Montiel-Ponsoda, Elena},
title = {Introduction to the Special Issue on Cross-Language Algorithms and Applications},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {With the increasingly global nature of our everyday interactions, the need for multilingual technologies to support efficient and effective information access and communication cannot be overemphasized. Computational modeling of language has been the focus of Natural Language Processing, a subdiscipline of Artificial Intelligence. One of the current challenges for this discipline is to design methodologies and algorithms that are cross-language in order to create multilingual technologies rapidly. The goal of this JAIR special issue on Cross-Language Algorithms and Applications (CLAA) is to present leading research in this area, with emphasis on developing unifying themes that could lead to the development of the science of multi- and cross-lingualism. In this introduction, we provide the reader with the motivation for this special issue and summarize the contributions of the papers that have been included. The selected papers cover a broad range of cross-lingual technologies including machine translation, domain and language adaptation for sentiment analysis, cross-language lexical resources, dependency parsing, information retrieval and knowledge representation. We anticipate that this special issue will serve as an invaluable resource for researchers interested in topics of cross-lingual natural language processing.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–15},
numpages = {15}
}

@article{10.5555/2910557.2910573,
author = {Imai, Tatsuya and Fukunaga, Alex},
title = {On a Practical, Integer-Linear Programming Model for Delete-Free Tasks and Its Use as a Heuristic for Cost-Optimal Planning},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {We propose a new integer-linear programming model for the delete relaxation in cost-optimal planning. While a straightforward IP for the delete relaxation is impractical, our enhanced model incorporates variable reduction techniques based on landmarks, relevance-based constraints, dominated action elimination, immediate action application, and inverse action constraints, resulting in an IP that can be used to directly solve delete-free planning problems. We show that our IP model is competitive with previous state-of-the-art solvers for delete-free problems. The LP-relaxation of the IP model is often a very good approximation to the IP, providing an approach to approximating the optimal value of the delete-free task that is complementary to the well-known LM-cut heuristic. We also show that constraints that partially consider delete effects can be added to our IP/LP models. We embed the new IP/LP models into a forward-search based planner, and show that the performance of the resulting planner on standard IPC benchmarks is comparable with the state-of-the-art for cost-optimal planning.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {631–677},
numpages = {47}
}

@article{10.5555/2910557.2910572,
author = {Strasser, Ben and Botea, Adi and Harabor, Daniel},
title = {Compressing Optimal Paths with Run Length Encoding},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {We introduce a novel approach to Compressed Path Databases, space efficient oracles used to very quickly identify the first edge on a shortest path. Our algorithm achieves query running times on the 100 nanosecond scale, being significantly faster than state-of-the-art first-move oracles from the literature. Space consumption is competitive, due to a compression approach that rearranges rows and columns in a first-move matrix and then performs run length encoding (RLE) on the contents of the matrix. One variant of our implemented system was, by a convincing margin, the fastest entry in the 2014 Grid-Based Path Planning Competition.We give a first tractability analysis for the compression scheme used by our algorithm. We study the complexity of computing a database of minimum size for general directed and undirected graphs. We find that in both cases the problem is NP-complete. We also show that, for graphs which can be decomposed along articulation points, the problem can be decomposed into independent parts, with a corresponding reduction in its level of difficulty. In particular, this leads to simple and tractable algorithms with linear running time which yield optimal compression results for trees.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {593–629},
numpages = {37}
}

@article{10.5555/2910557.2910571,
author = {Steigmiller, Andreas and Glimm, Birte},
title = {Pay-as-You-Go Description Logic Reasoning by Coupling Tableau and Saturation Procedures},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {Nowadays, saturation-based reasoners for the OWL EL profile of the Web Ontology Language are able to handle large ontologies such as SNOMED very efficiently. However, it is currently unclear how saturation-based reasoning procedures can be extended to very expressive Description Logics such as SROIQ--the logical underpinning of the current and second iteration of the Web Ontology Language. Tableau-based procedures, on the other hand, are not limited to specific Description Logic languages or OWL profiles, but even highly optimised tableau-based reasoners might not be efficient enough to handle large ontologies such as SNOMED. In this paper, we present an approach for tightly coupling tableau - and saturation-based procedures that we implement in the OWL DL reasoner Konclude. Our detailed evaluation shows that this combination significantly improves the reasoning performance for a wide range of ontologies.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {535–592},
numpages = {58}
}

@article{10.5555/2910557.2910570,
author = {Aziz, Haris and Brill, Markus and Fischer, Felix and Harrenstein, Paul and Lang, J\'{e}r\^{o}me and Seedig, Hans Georg},
title = {Possible and Necessary Winners of Partial Tournaments},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {We study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts--including the uncovered set, Borda, ranked pairs, and maximin--and show that for most of them, possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference profiles.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {493–534},
numpages = {42}
}

@article{10.5555/2910557.2910569,
author = {Halpern, Joseph Y.},
title = {Weighted Regret-Based Likelihood: A New Approach to Describing Uncertainty},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {Recently, Halpern and Leung suggested representing uncertainty by a set of weighted probability measures, and suggested a way of making decisions based on this representation of uncertainty: maximizing weighted regret. Their paper does not answer an apparently simpler question: what it means, according to this representation of uncertainty, for an event E to be more likely than an event E′. In this paper, a notion of comparative likelihood when uncertainty is represented by a set of weighted probability measures is defined. It generalizes the ordering defined by probability (and by lower probability) in a natural way; a generalization of upper probability can also be defined. A complete axiomatic characterization of this notion of regret-based likelihood is given.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {471–492},
numpages = {22}
}

@article{10.5555/2910557.2910568,
author = {Rochlin, Igor and Sarne, David},
title = {Constraining Information Sharing to Improve Cooperative Information Gathering},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {This paper considers the problem of cooperation between self-interested agents in acquiring better information regarding the nature of the different options and opportunities available to them. By sharing individual findings with others, the agents can potentially achieve a substantial improvement in overall and individual expected benefits. Unfortunately, it is well known that with self-interested agents equilibrium considerations often dictate solutions that are far from the fully cooperative ones, hence the agents do not manage to fully exploit the potential benefits encapsulated in such cooperation. In this paper we introduce, analyze and demonstrate the benefit of five methods aiming to improve cooperative information gathering. Common to all five that they constrain and limit the information sharing process. Nevertheless, the decrease in benefit due to the limited sharing is outweighed by the resulting substantial improvement in the equilibrium individual information gathering strategies. The equilibrium analysis given in the paper, which, in itself is an important contribution to the study of cooperation between self-interested agents, enables demonstrating that for a wide range of settings an improved individual expected benefit is achieved for all agents when applying each of the five methods.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {437–469},
numpages = {33}
}

@article{10.5555/2910557.2910567,
author = {Siddiqui, Fazlul Hasan and Haslum, Patrik},
title = {Continuing Plan Quality Optimisation},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {Finding high quality plans for large planning problems is hard. Although some current anytime planners are often able to improve plans quickly, they tend to reach a limit at which the plans produced are still very far from the best possible, but these planners fail to find any further improvement, even when given several hours of runtime.We present an approach to continuing plan quality optimisation at larger time scales, and its implementation in a system called BDPO2. Key to this approach is a decomposition into subproblems of improving parts of the current best plan. The decomposition is based on block deordering, a form of plan deordering which identifies hierarchical plan structure. BDPO2 can be seen as an application of the large neighbourhood search (LNS) local search strategy to planning, where the neighbourhood of a plan is defined by replacing one or more subplans with improved subplans. On-line learning is also used to adapt the strategy for selecting subplans and subplanners over the course of plan optimisation.Even starting from the best plans found by other means, BDPO2 is able to continue improving plan quality, often producing better plans than other anytime planners when all are given enough runtime. The best results, however, are achieved by a combination of different techniques working together.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {369–435},
numpages = {67}
}

@article{10.5555/2910557.2910566,
author = {Zhou, Yujiao and Grau, Bernardo Cuenca and Nenov, Yavor and Kaminski, Mark and Horrocks, Ian},
title = {PAGOdA: Pay-as-You-Go Ontology Query Answering Using a Datalog Reasoner},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {Answering conjunctive queries over ontology-enriched datasets is a core reasoning task for many applications. Query answering is, however, computationally very expensive, which has led to the development of query answering procedures that sacrifice either expressive power of the ontology language, or the completeness of query answers in order to improve scalability. In this paper, we describe a hybrid approach to query answering over OWL 2 ontologies that combines a datalog reasoner with a fully-fledged OWL 2 reasoner in order to provide scalable 'pay-as-you-go' performance. The key feature of our approach is that it delegates the bulk of the computation to the datalog reasoner and resorts to expensive OWL 2 reasoning only as necessary to fully answer the query. Furthermore, although our main goal is to efficiently answer queries over OWL 2 ontologies and data, our technical results are very general and our approach is applicable to first-order knowledge representation languages that can be captured by rules allowing for existential quantification and disjunction in the head; our only assumption is the availability of a datalog reasoner and a fully-fledged reasoner for the language of interest, both of which are used as 'black boxes'. We have implemented our techniques in the PAGOdA system, which combines the datalog reasoner RDFox and the OWL 2 reasoner HermiT. Our extensive evaluation shows that PAGOdA succeeds in providing scalable pay-as-you-go query answering for a wide range of OWL 2 ontologies, datasets and queries.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {309–367},
numpages = {59}
}

@article{10.5555/2910557.2910565,
author = {Mossakowski, Till and Moratz, Reinhard},
title = {Relations between Spatial Calculi about Directions and Orientations},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {Qualitative spatial descriptions characterize essential properties of spatial objects or configurations by relying on relative comparisons rather than measuring. Typically, in qualitative approaches only relatively coarse distinctions between configurations are made. Qualitative spatial knowledge can be used to represent incomplete and underdetermined knowledge in a systematic way. This is especially useful if the task is to describe features of classes of configurations rather than individual configurations.Although reasoning with them is generally NP-hard (even ∃IR-complete), relative directions are important because they play a key role in human spatial descriptions and there are several approaches how to represent them using qualitative methods. In these approaches directions between spatial locations can be expressed as constraints over infinite domains, e.g. the Euclidean plane. The theory of relation algebras has been successfully applied to this field. Viewing relation algebras as universal algebras and applying and modifying standard tools from universal algebra in this work, we (re)define notions of qualitative constraint calculus, of homomorphism between calculi, and of quotient of calculi. Based on this method we derive important properties for spatial calculi from corresponding properties of related calculi. From a conceptual point of view these formal mappings between calculi are a means to translate between different granularities.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {277–308},
numpages = {32}
}

@article{10.5555/2910557.2910564,
author = {Kalech, Meir and Reches, Shulamit},
title = {Decision Making with Dynamic Uncertain Events},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {When to make a decision is a key question in decision making problems characterized by uncertainty. In this paper we deal with decision making in environments where information arrives dynamically. We address the tradeoff between waiting and stopping strategies. On the one hand, waiting to obtain more information reduces uncertainty, but it comes with a cost. Stopping and making a decision based on an expected utility reduces the cost of waiting, but the decision is based on uncertain information. We propose an optimal algorithm and two approximation algorithms. We prove that one approximation is optimistic - waits at least as long as the optimal algorithm, while the other is pessimistic - stops not later than the optimal algorithm. We evaluate our algorithms theoretically and empirically and show that the quality of the decision in both approximations is near-optimal and much faster than the optimal algorithm. Also, we can conclude from the experiments that the cost function is a key factor to chose the most effective algorithm.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {233–275},
numpages = {43}
}

@article{10.5555/2910557.2910563,
author = {Strass, Hannes},
title = {Expressiveness of Two-Valued Semantics for Abstract Dialectical Frameworks},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {We analyse the expressiveness of Brewka and Woltran's abstract dialectical frameworks for two-valued semantics. By expressiveness we mean the ability to encode a desired set of two-valued interpretations over a given propositional vocabulary A using only atoms from A. We also compare ADFs' expressiveness with that of (the two-valued semantics of) abstract argumentation frameworks, normal logic programs and propositional logic. While the computational complexity of the two-valued model existence problem for all these languages is (almost) the same, we show that the languages form a neat hierarchy with respect to their expressiveness. We then demonstrate that this hierarchy collapses once we allow to introduce a linear number of new vocabulary elements. We finally also analyse and compare the representational succinctness of ADFs (for two-valued model semantics), that is, their capability to represent two-valued interpretation sets in a space-efficient manner.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {193–231},
numpages = {39}
}

@article{10.5555/2910557.2910562,
author = {Formiga, Llu\'{\i}s and Barr\'{o}n-Cede\~{n}o, Alberto and M\`{a}rquez, Llu\'{\i}s and Henr\'{\i}quez, Carlos A. and Mari\~{n}o, Jos\'{e} B.},
title = {Leveraging Online User Feedback to Improve Statistical Machine Translation},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {In this article we present a three-step methodology for dynamically improving a statistical machine translation (SMT) system by incorporating human feedback in the form of free edits on the system translations. We target at feedback provided by casual users, which is typically error-prone. Thus, we first propose a filtering step to automatically identify the better user-edited translations and discard the useless ones. A second step produces a pivot-based alignment between source and user-edited sentences, focusing on the errors made by the system. Finally, a third step produces a new translation model and combines it linearly with the one from the original system. We perform a thorough evaluation on a real-world dataset collected from the Reverso.net translation service and show that every step in our methodology contributes significantly to improve a general purpose SMT system. Interestingly, the quality improvement is not only due to the increase of lexical coverage, but to a better lexical selection, reordering, and morphology. Finally, we show the robustness of the methodology by applying it to a different scenario, in which the new examples come from an automatically Web-crawled parallel corpus. Using exactly the same architecture and models provides again a significant improvement of the translation quality of a general purpose baseline SMT system.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {159–192},
numpages = {34}
}

@article{10.5555/2910557.2910561,
author = {Kiesel, Scott and Burns, Ethan and Ruml, Wheeler},
title = {Achieving Goals Quickly Using Real-Time Search: Experimental Results in Video Games},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {In real-time domains such as video games, planning happens concurrently with execution and the planning algorithm has a strictly bounded amount of time before it must return the next action for the agent to execute. We explore the use of real-time heuristic search in two benchmark domains inspired by video games. Unlike classic benchmarks such as grid pathfinding and the sliding tile puzzle, these new domains feature exogenous change and directed state space graphs. We consider the setting in which planning and acting are concurrent and we use the natural objective of minimizing goal achievement time. Using both the classic benchmarks and the new domains, we investigate several enhancements to a leading real-time search algorithm, LSS-LRTA*. We show experimentally that 1) it is better to plan after each action or to use a dynamically sized lookahead, 2) A*-based lookahead can cause undesirable actions to be selected, and 3) on-line de-biasing of the heuristic can lead to improved performance. We hope this work encourages future research on applying real-time search in dynamic domains.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {123–158},
numpages = {36}
}

@article{10.5555/2910557.2910560,
author = {Izquierdo, Rub\'{e}n and Su\'{a}rez, Armando and Rigau, German},
title = {Word vs. Class-Based Word Sense Disambiguation},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {As empirically demonstrated by the Word Sense Disambiguation (WSD) tasks of the last SensEval/SemEval exercises, assigning the appropriate meaning to words in context has resisted all attempts to be successfully addressed. Many authors argue that one possible reason could be the use of inappropriate sets of word meanings. In particular, WordNet has been used as a defacto standard repository of word meanings in most of these tasks. Thus, instead of using the word senses defined in WordNet, some approaches have derived semantic classes representing groups of word senses. However, the meanings represented by WordNet have been only used for WSD at a very fine-grained sense level or at a very coarse-grained semantic class level (also called SuperSenses). We suspect that an appropriate level of abstraction could be on between both levels. The contributions of this paper are manifold. First, we propose a simple method to automatically derive semantic classes at intermediate levels of abstraction covering all nominal and verbal Word-Net meanings. Second, we empirically demonstrate that our automatically derived semantic classes outperform classical approaches based on word senses and more coarse-grained sense groupings. Third, we also demonstrate that our supervised WSD system benefits from using these new semantic classes as additional semantic features while reducing the amount of training examples. Finally, we also demonstrate the robustness of our supervised semantic class-based WSD system when tested on out of domain corpus.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {83–122},
numpages = {40}
}

@article{10.5555/2910557.2910559,
author = {S\ae{}ther, Sigve Hortemo and Telle, Jan Arne and Vatshelle, Martin},
title = {Solving #SAT and MaxSAT by Dynamic Programming},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {We look at dynamic programming algorithms for propositional model counting, also called #SAT, and MaxSAT. Tools from graph structure theory, in particular treewidth, have been used to successfully identify tractable cases in many subfields of AI, including SAT, Constraint Satisfaction Problems (CSP), Bayesian reasoning, and planning. In this paper we attack #SAT and MaxSAT using similar, but more modern, graph structure tools. The tractable cases will include formulas whose class of incidence graphs have not only unbounded treewidth but also unbounded clique-width. We show that our algorithms extend all previous results for MaxSAT and #SAT achieved by dynamic programming along structural decompositions of the incidence graph of the input formula. We present some limited experimental results, comparing implementations of our algorithms to state-of-the-art #SAT and MaxSAT solvers, as a proof of concept that warrants further research.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {59–82},
numpages = {24}
}

@article{10.5555/2910557.2910558,
author = {Bar-Haim, Roy and Dagan, Ido and Berant, Jonathan},
title = {Knowledge-Based Textual Inference via Parse-Tree Transformations},
year = {2015},
issue_date = {September 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {54},
number = {1},
issn = {1076-9757},
abstract = {Textual inference is an important component in many applications for understanding natural language. Classical approaches to textual inference rely on logical representations for meaning, which may be regarded as "external" to the natural language itself. However, practical applications usually adopt shallower lexical or lexical-syntactic representations, which correspond closely to language structure. In many cases, such approaches lack a principled meaning representation and inference framework. We describe an inference formalism that operates directly on language-based structures, particularly syntactic parse trees. New trees are generated by applying inference rules, which provide a unified representation for varying types of inferences. We use manual and automatic methods to generate these rules, which cover generic linguistic structures as well as specific lexical-based inferences. We also present a novel packed data-structure and a corresponding inference algorithm that allows efficient implementation of this formalism. We proved the correctness of the new algorithm and established its efficiency analytically and empirically. The utility of our approach was illustrated on two tasks: unsupervised relation extraction from a large corpus, and the Recognizing Textual Entailment (RTE) benchmarks.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1–57},
numpages = {57}
}

@article{10.5555/2831071.2831089,
author = {Hunter, Aaron and Delgrande, James P.},
title = {Belief Change with Uncertain Action Histories},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {We consider the iterated belief change that occurs following an alternating sequence of actions and observations. At each instant, an agent has beliefs about the actions that have occurred as well as beliefs about the resulting state of the world. We represent such problems by a sequence of ranking functions, so an agent assigns a quantitative plausibility value to every action and every state at each point in time. The resulting formalism is able to represent fallible belief, erroneous perception, exogenous actions, and failed actions. We illustrate that our framework is a generalization of several existing approaches to belief change, and it appropriately captures the non-elementary interaction between belief update and belief revision.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {779–824},
numpages = {46}
}

@article{10.5555/2831071.2831088,
author = {Lindauer, Marius and Hoos, Holger H. and Hutter, Frank and Schaub, Torsten},
title = {AutoFolio: An Automatically Configured Algorithm Selector},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {Algorithm selection (AS) techniques - which involve choosing from a set of algorithms the one expected to solve a given problem instance most efficiently - have substantially improved the state of the art in solving many prominent AI problems, such as SAT, CSP, ASP, MAXSAT and QBF. Although several AS procedures have been introduced, not too surprisingly, none of them dominates all others across all AS scenarios. Furthermore, these procedures have parameters whose optimal values vary across AS scenarios. This holds specifically for the machine learning techniques that form the core of current AS procedures, and for their hyperparameters. Therefore, to successfully apply AS to new problems, algorithms and benchmark sets, two questions need to be answered: (i) how to select an AS approach and (ii) how to set its parameters effectively. We address both of these problems simultaneously by using automated algorithm configuration. Specifically, we demonstrate that we can automatically configure CLASPFOLIO 2, which implements a large variety of different AS approaches and their respective parameters in a single, highly-parameterized algorithm framework. Our approach, dubbed AUTOFOLIO, allows researchers and practitioners across a broad range of applications to exploit the combined power of many different AS methods. We demonstrate AUTOFOLIO can significantly improve the performance of CLASPFOLIO 2 on 8 out of the 13 scenarios from the Algorithm Selection Library, leads to new state-of-the-art algorithm selectors for 7 of these scenarios, and matches state-of-the-art performance (statistically) on all other scenarios. Compared to the best single algorithm for each AS scenario, AUTOFOLIO achieves average speedup factors between 1:3 and 15:4.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {745–778},
numpages = {34}
}

@article{10.5555/2831071.2831087,
author = {Krysta, Piotr and Telelis, Orestis and Ventre, Carmine},
title = {Mechanisms for Multi-Unit Combinatorial Auctions with a Few Distinct Goods},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {We design and analyze deterministic truthful approximation mechanisms for multiunit Combinatorial Auctions involving only a constant number of distinct goods, each in arbitrary limited supply. Prospective buyers (bidders) have preferences over multisets of items, i.e., for more than one unit per distinct good. Our objective is to determine allocations of multisets that maximize the Social Welfare. Our main results are for multiminded and submodular bidders. In the first setting each bidder has a positive value for being allocated one multiset from a prespecified demand set of alternatives. In the second setting each bidder is associated to a submodular valuation function that defines his value for the multiset he is allocated. For multi-minded bidders, we design a truthful FPTAS that fully optimizes the Social Welfare, while violating the supply constraints on goods within factor (1+ε), for any fixed ε > 0 (i.e., the approximation applies to the constraints and not to the Social Welfare). This result is best possible, in that full optimization is impossible without violating the supply constraints. For submodular bidders, we obtain a PTAS that approximates the optimum Social Welfare within factor (1 + ε), for any fixed ε > 0, without violating the supply constraints. This result is best possible as well. Our allocation algorithms are Maximal-in-Range and yield truthful mechanisms, when paired with Vickrey-Clarke-Groves payments.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {721–744},
numpages = {24}
}

@article{10.5555/2831071.2831086,
author = {Kwisthout, Johan},
title = {Tree-Width and the Computational Complexity of Map Approximations in Bayesian Networks},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {The problem of finding the most probable explanation to a designated set of variables given partial evidence (the MAP problem) is a notoriously intractable problem in Bayesian networks, both to compute exactly and to approximate. It is known, both from theoretical considerations and from practical experience, that low tree-width is typically an essential prerequisite to efficient exact computations in Bayesian networks. In this paper we investigate whether the same holds for approximating MAP. We define four notions of approximating MAP (by value, structure, rank, and expectation) and argue that all of them are intractable in general. We prove that efficient value-approximations, structure-approximations, and rank-approximations of MAP instances with high tree-width will violate the Exponential Time Hypothesis. In contrast, we show that MAP can sometimes be efficiently expectation-approximated, even in instances with high tree-width, if the most probable explanation has a high probability. We introduce the complexity class FERT, analogous to the class FPT, to capture this notion of fixed-parameter expectation-approximability. We suggest a road-map to future research that yields fixed-parameter tractable results for expectation-approximate MAP, even in graphs with high tree-width.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {699–720},
numpages = {22}
}

@article{10.5555/2831071.2831085,
author = {Bloembergen, Daan and Tuyls, Karl and Hennes, Daniel and Kaisers, Michael},
title = {Evolutionary Dynamics of Multi-Agent Learning: A Survey},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {The interaction of multiple autonomous agents gives rise to highly dynamic and nondeterministic environments, contributing to the complexity in applications such as automated financial markets, smart grids, or robotics. Due to the sheer number of situations that may arise, it is not possible to foresee and program the optimal behaviour for all agents beforehand. Consequently, it becomes essential for the success of the system that the agents can learn their optimal behaviour and adapt to new situations or circumstances. The past two decades have seen the emergence of reinforcement learning, both in single and multi-agent settings, as a strong, robust and adaptive learning paradigm. Progress has been substantial, and a wide range of algorithms are now available. An important challenge in the domain of multi-agent learning is to gain qualitative insights into the resulting system dynamics. In the past decade, tools and methods from evolutionary game theory have been successfully employed to study multi-agent learning dynamics formally in strategic interactions. This article surveys the dynamical models that have been derived for various multi-agent reinforcement learning algorithms, making it possible to study and compare them qualitatively. Furthermore, new learning algorithms that have been introduced using these evolutionary game theoretic tools are reviewed. The evolutionary models can be used to study complex strategic interactions. Examples of such analysis are given for the domains of automated trading in stock markets and collision avoidance in multi-robot systems. The paper provides a roadmap on the progress that has been achieved in analysing the evolutionary dynamics of multi-agent learning by highlighting the main results and accomplishments.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {659–697},
numpages = {39}
}

@article{10.5555/2831071.2831084,
author = {Funke, Stefan and Nusser, Andr\'{e} and Storandt, Sabine},
title = {Placement of Loading Stations for Electric Vehicles: No Detours Necessary!},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {Compared to conventional cars, electric vehicles (EVs) still suffer from considerably shorter cruising ranges. Combined with the sparsity of battery loading stations, the complete transition to E-mobility still seems a long way to go. In this paper, we consider the problem of placing as few loading stations as possible so that on any shortest path there are sufficiently many not to run out of energy. We show how to model this problem and introduce heuristics which provide close-to-optimal solutions even in large road networks.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {633–658},
numpages = {26}
}

@article{10.5555/2831071.2831083,
author = {Rankooh, Masood Feyzbakhsh and Ghassem-Sani, Gholamreza},
title = {ITSAT: An Efficient Sat-Based Temporal Planner},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {Planning as satisfiability is known as an efficient approach to deal with many types of planning problems. However, this approach has not been competitive with the state-space based methods in temporal planning. This paper describes ITSAT as an efficient SAT-based (satisfiability based) temporal planner capable of temporally expressive planning. The novelty of ITSAT lies in the way it handles temporal constraints of given problems without getting involved in the difficulties of introducing continuous variables into the corresponding satisfiability problems. We also show how, as in SAT-based classical planning, carefully devised preprocessing and encoding schemata can considerably improve the efficiency of SAT-based temporal planning. We present two preprocessing methods for mutex relation extraction and action compression. We also show that the separation of causal and temporal reasoning enables us to employ compact encodings that are based on the concept of parallel execution semantics. Although such encodings have been shown to be quite effective in classical planning, ITSAT is the first temporal planner utilizing this type of encoding. Our empirical results show that not only does ITSAT outperform the state-of-the-art temporally expressive planners, it is also competitive with the fast temporal planners that cannot handle required concurrency.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {541–632},
numpages = {92}
}

@article{10.5555/2831071.2831082,
author = {Ginsberg, Matthew L.},
title = {Satisfiability and Systematicity},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {We introduce a new notion of systematicity for satisfiability algorithms with restarts, saying that an algorithm is strongly systematic if it is systematic independent of restart policy but weakly systematic if it is systematic for some restart policies but not others. We show that existing satisfiability engines are generally only weakly systematic, and describe FLEX, a strongly systematic algorithm that uses an amount of memory polynomial in the size of the problem. On large number factoring problems, FLEX appears to outperform weakly systematic approaches.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {497–540},
numpages = {44}
}

@article{10.5555/2831071.2831081,
author = {Brandt, Felix and Brill, Markus and Hemaspaandra, Edith and Hemaspaandra, Lane A.},
title = {Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. This paper shows that for voters who follow the most central political-science model of electorates-- single-peaked preferences--those hardness protections vanish. By using single-peaked preferences to simplify combinatorial covering challenges, we for the first time show that NP-hard bribery problems--including those for Kemeny and Llull elections--fall to polynomial time for single-peaked electorates. By using single-peaked preferences to simplify combinatorial partition challenges, we for the first time show that NP-hard partition-of-voters problems fall to polynomial time for single-peaked electorates. We show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Θ2p-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {439–496},
numpages = {58}
}

@article{10.5555/2831071.2831080,
author = {Mann, Timothy A. and Mannor, Shie and Precup, Doina},
title = {Approximate Value Iteration with Temporally Extended Actions},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {Temporally extended actions have proven useful for reinforcement learning, but their duration also makes them valuable for efficient planning. The options framework provides a concrete way to implement and reason about temporally extended actions. Existing literature has demonstrated the value of planning with options empirically, but there is a lack of theoretical analysis formalizing when planning with options is more efficient than planning with primitive actions. We provide a general analysis of the convergence rate of a popular Approximate Value Iteration (AVI) algorithm called Fitted Value Iteration (FVI) with options. Our analysis reveals that longer duration options and a pessimistic estimate of the value function both lead to faster convergence. Furthermore, options can improve convergence even when they are suboptimal and sparsely distributed throughout the state-space. Next we consider the problem of generating useful options for planning based on a subset of landmark states. This suggests a new algorithm, Landmark-based AVI (LAVI), that represents the value function only at the landmark states. We analyze both FVI and LAVI using the proposed landmark-based options and compare the two algorithms. Our experimental results in three different domains demonstrate the key properties from the analysis. Our theoretical and experimental results demonstrate that options can play an important role in AVI by decreasing approximation error and inducing fast convergence.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {375–438},
numpages = {64}
}

@article{10.5555/2831071.2831079,
author = {Bienvenu, Meghyn and Ortiz, Magdalena and \v{S}imkus, Mantas},
title = {Regular Path Queries in Lightweight Description Logics: Complexity and Algorithms},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {Conjunctive regular path queries are an expressive extension of the well-known class of conjunctive queries. Such queries have been extensively studied in the (graph) database community, since they support a controlled form of recursion and enable sophisticated path navigation. Somewhat surprisingly, there has been little work aimed at using such queries in the context of description logic (DL) knowledge bases, particularly for the lightweight DLs that are considered best suited for data-intensive applications. This paper aims to bridge this gap by providing algorithms and tight complexity bounds for answering two-way conjunctive regular path queries over DL knowledge bases formulated in lightweight DLs of the DL-Lite and EL families. Our results demonstrate that in data complexity, the cost of moving to this richer query language is as low as one could wish for: the problem is NL-complete for DL-Lite and P-complete for EL. The combined complexity of query answering increases from NP- to PSPACE-complete, but for two-way regular path queries (without conjunction), we show that query answering is tractable even with respect to combined complexity. Our results reveal two-way conjunctive regular path queries as a promising language for querying data enriched by ontologies formulated in DLs of the DL-Lite and EL families or the corresponding OWL 2 QL and EL profiles.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {315–374},
numpages = {60}
}

@article{10.5555/2831071.2831078,
author = {Figueira, Diego and Figueira, Santiago and Areces, Carlos},
title = {Model Theory of XPath on Data Trees. Part I: Bisimulation and Characterization},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {We investigate model theoretic properties of XPath with data (in)equality tests over the class of data trees, i.e., the class of trees where each node contains a label from a finite alphabet and a data value from an infinite domain.We provide notions of (bi)simulations for XPath logics containing the child, parent, ancestor and descendant axes to navigate the tree. We show that these notions precisely characterize the equivalence relation associated with each logic. We study formula complexity measures consisting of the number of nested axes and nested subformulas in a formula; these notions are akin to the notion of quantifier rank in first-order logic. We show characterization results for fine grained notions of equivalence and (bi)simulation that take into account these complexity measures. We also prove that positive fragments of these logics correspond to the formulas preserved under (non-symmetric) simulations. We show that the logic including the child axis is equivalent to the fragment of first-order logic invariant under the corresponding notion of bisimulation. If upward navigation is allowed the characterization fails but a weaker result can still be established. These results hold both over the class of possibly infinite data trees and over the class of finite data trees.Besides their intrinsic theoretical value, we argue that bisimulations are useful tools to prove (non)expressivity results for the logics studied here, and we substantiate this claim with examples.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {271–314},
numpages = {44}
}

@article{10.5555/2831071.2831077,
author = {Kumar, Akshat and Zilberstein, Shlomo and Toussaint, Marc},
title = {Probabilistic Inference Techniques for Scalable Multiagent Decision Making},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {Decentralized POMDPs provide an expressive framework for multiagent sequential decision making. However, the complexity of these models--NEXP-Complete even for two agents--has limited their scalability. We present a promising new class of approximation algorithms by developing novel connections between multiagent planning and machine learning. We show how the multiagent planning problem can be reformulated as inference in a mixture of dynamic Bayesian networks (DBNs). This planning-as-inference approach paves the way for the application of efficient inference techniques in DBNs to multiagent decision making. To further improve scalability, we identify certain conditions that are sufficient to extend the approach to multiagent systems with dozens of agents. Specifically, we show that the necessary inference within the expectation-maximization framework can be decomposed into processes that often involve a small subset of agents, thereby facilitating scalability. We further show that a number of existing multiagent planning models satisfy these conditions. Experiments on large planning benchmarks confirm the benefits of our approach in terms of runtime and scalability with respect to existing techniques.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {223–270},
numpages = {48}
}

@article{10.5555/2831071.2831076,
author = {Espl\`{a}-Gomis, Miquel and S\'{a}nchez-Mart\'{\i}nez, Felipe and Forcada, Mikel L.},
title = {Using Machine Translation to Provide Target-Language Edit Hints in Computer Aided Translation Based on Translation Memories},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {This paper explores the use of general-purpose machine translation (MT) in assisting the users of computer-aided translation (CAT) systems based on translation memory (TM) to identify the target words in the translation proposals that need to be changed (either replaced or removed) or kept unedited, a task we term as word-keeping recommendation. MT is used as a black box to align source and target sub-segments on the fly in the translation units (TUs) suggested to the user. Source-language (SL) and target-language (TL) segments in the matching TUs are segmented into overlapping sub-segments of variable length and machine-translated into the TL and the SL, respectively. The bilingual subsegments obtained and the matching between the SL segment in the TU and the segment to be translated are employed to build the features that are then used by a binary classifier to determine the target words to be changed and those to be kept unedited. In this approach, MT results are never presented to the translator. Two approaches are presented in this work: one using a word-keeping recommendation system which can be trained on the TM used with the CAT system, and a more basic approach which does not require any training.Experiments are conducted by simulating the translation of texts in several language pairs with corpora belonging to different domains and using three different MT systems. We compare the performance obtained to that of previous works that have used statistical word alignment for word-keeping recommendation, and show that the MT-based approaches presented in this paper are more accurate in most scenarios. In particular, our results confirm that the MT-based approaches are better than the alignment-based approach when using models trained on out-of-domain TMs. Additional experiments were also performed to check how dependent the MT-based recommender is on the language pair and MT system used for training. These experiments confirm a high degree of reusability of the recommendation models across various MT systems, but a low level of reusability across language pairs.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {169–222},
numpages = {54}
}

@article{10.5555/2831071.2831075,
author = {Heule, Marijn and J\"{a}rvisalo, Matti and Lonsing, Florian and Seidl, Martina and Biere, Armin},
title = {Clause Elimination for SAT and QSAT},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {The famous archetypical NP-complete problem of Boolean satisfiability (SAT) and its PSPACE-complete generalization of quantified Boolean satisfiability (QSAT) have become central declarative programming paradigms through which real-world instances of various computationally hard problems can be efficiently solved. This success has been achieved through several breakthroughs in practical implementations of decision procedures for SAT and QSAT, that is, in SAT and QSAT solvers. Here, simplification techniques for conjunctive normal form (CNF) for SAT and for prenex conjunctive normal form (PCNF) for QSAT--the standard input formats of SAT and QSAT solvers--have recently proven very effective in increasing solver efficiency when applied before (i.e., in preprocessing) or during (i.e., in inprocessing) satisfiability search.In this article, we develop and analyze clause elimination procedures for pre- and inprocessing. Clause elimination procedures form a family of (P)CNF formula simplification techniques which remove clauses that have specific (in practice polynomial-time) redundancy properties while maintaining the satisfiability status of the formulas. Extending known procedures such as tautology, subsumption, and blocked clause elimination, we introduce novel elimination procedures based on asymmetric variants of these techniques, and also develop a novel family of so-called covered clause elimination procedures, as well as natural liftings of the CNF-level procedures to PCNF. We analyze the considered clause elimination procedures from various perspectives. Furthermore, for the variants not preserving logical equivalence under clause elimination, we show how to reconstruct solutions to original CNFs from satisfying assignments to simplified CNFs, which is important for practical applications for the procedures. Complementing the more theoretical analysis, we present results on an empirical evaluation on the practical importance of the clause elimination procedures in terms of the effect on solver runtimes on standard real-world application benchmarks. It turns out that the importance of applying the clause elimination procedures developed in this work is empirically emphasized in the context of state-of-the-art QSAT solving.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {127–168},
numpages = {42}
}

@article{10.5555/2831071.2831074,
author = {Grossi, Davide and Lorini, Emiliano and Schwarzentruber, Fran\c{c}ois},
title = {The Ceteris Paribus Structure of Logics of Game Forms},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {The article introduces a ceteris paribus modal logic, called CP, interpreted on the equivalence classes induced by finite sets of propositional atoms. This logic is studied and then used to embed three logics of strategic interaction, namely atemporal STIT, the coalition logic of propositional control (CL--PC) and the starless fragment of the dynamic logic of propositional assignments (DL--PA). The embeddings highlight a common ceteris paribus structure underpinning the key operators of all these apparently very different logics and show, we argue, remarkable similarities behind some of the most in uential formalisms for reasoning about strategic interaction.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {91–126},
numpages = {36}
}

@article{10.5555/2831071.2831073,
author = {Dubba, Krishna S. R. and Cohn, Anthony G. and Hogg, David C. and Bhatt, Mehul and Dylla, Frank},
title = {Learning Relational Event Models from Video},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {Event models obtained automatically from video can be used in applications ranging from abnormal event detection to content based video retrieval. When multiple agents are involved in the events, characterizing events naturally suggests encoding interactions as relations. Learning event models from this kind of relational spatio-temporal data using relational learning techniques such as Inductive Logic Programming (ILP) hold promise, but have not been successfully applied to very large datasets which result from video data. In this paper, we present a novel framework remind (Relational Event Model INDuction) for supervised relational learning of event models from large video datasets using ILP. Efficiency is achieved through the learning from interpretations setting and using a typing system that exploits the type hierarchy of objects in a domain. The use of types also helps prevent over generalization. Furthermore, we also present a type-refining operator and prove that it is optimal. The learned models can be used for recognizing events from previously unseen videos. We also present an extension to the framework by integrating an abduction step that improves the learning performance when there is noise in the input data. The experimental results on several hours of video data from two challenging real world domains (an airport domain and a physical action verbs domain) suggest that the techniques are suitable to real world scenarios.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {41–90},
numpages = {50}
}

@article{10.5555/2831071.2831072,
author = {Shivaswamy, Pannaga and Joachims, Thorsten},
title = {Coactive Learning},
year = {2015},
issue_date = {May 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {53},
number = {1},
issn = {1076-9757},
abstract = {We propose Coactive Learning as a model of interaction between a learning system and a human user, where both have the common goal of providing results of maximum utility to the user. Interactions in the Coactive Learning model take the following form: at each step, the system (e.g. search engine) receives a context (e.g. query) and predicts an object (e.g. ranking); the user responds by correcting the system if necessary, providing a slightly improved - but not necessarily optimal - object as feedback. We argue that such preference feedback can be inferred in large quantity from observable user behavior (e.g., clicks in web search), unlike the optimal feedback required in the expert model or the cardinal valuations required for bandit learning. Despite the relaxed requirements for the feedback, we show that it is possible to adapt many existing online learning algorithms to the coactive framework. In particular, we provide algorithms that achieve O(1/√T) average regret in terms of cardinal utility, even though the learning algorithm never observes cardinal utility values directly. We also provide an algorithm with O(log(T)/T) average regret in the case of λ-strongly convex loss functions. An extensive empirical study demonstrates the applicability of our model and algorithms on a movie recommendation task, as well as ranking for web search.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–40},
numpages = {40}
}

@article{10.5555/2831407.2831421,
author = {Yu, Haonan and Siddharth, N. and Barbu, Andrei and Siskind, Jeffrey Mark},
title = {A Compositional Framework for Grounding Language Inference, Generation, and Acquisition in Video},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {We present an approach to simultaneously reasoning about a video clip and an entire natural-language sentence. The compositional nature of language is exploited to construct models which represent the meanings of entire sentences composed out of the meanings of the words in those sentences mediated by a grammar that encodes the predicate-argument relations. We demonstrate that these models faithfully represent the meanings of sentences and are sensitive to how the roles played by participants (nouns), their characteristics (adjectives), the actions performed (verbs), the manner of such actions (adverbs), and changing spatial relations between participants (prepositions) affect the meaning of a sentence and how it is grounded in video. We exploit this methodology in three ways. In the first, a video clip along with a sentence are taken as input and the participants in the event described by the sentence are highlighted, even when the clip depicts multiple similar simultaneous events. In the second, a video clip is taken as input without a sentence and a sentence is generated that describes an event in that clip. In the third, a corpus of video clips is paired with sentences which describe some of the events in those clips and the meanings of the words in those sentences are learned. We learn these meanings without needing to specify which attribute of the video clips each word in a given sentence refers to. The learned meaning representations are shown to be intelligible to humans.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {601–713},
numpages = {113}
}

@article{10.5555/2831407.2831420,
author = {Dao-Tran, Minh and Eiter, Thomas and Fink, Michael and Krennwallner, Thomas},
title = {Distributed Evaluation of Nonmonotonic Multi-Context Systems},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {Multi-context Systems (MCSs) are a formalism for systems consisting of knowledge bases (possibly heterogeneous and non-monotonic) that are interlinked via bridge rules, where the global system semantics emerges from the local semantics of the knowledge bases (also called "contexts") in an equilibrium. While MCSs and related formalisms are inherently targeted for distributed settings, no truly distributed algorithms for their evaluation were available. We address this shortcoming and present a suite of such algorithms which includes a basic algorithm DMCS, an advanced version DMCSOPT that exploits topology-based optimizations, and a streaming algorithm DMCS-STREAMING that computes equilibria in packages of bounded size. The algorithms behave quite differently in several respects, as experienced in thorough experimental evaluation of a system prototype. From the experimental results, we derive a guideline for choosing the appropriate algorithm and running mode in particular situations, determined by the parameter settings.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {543–600},
numpages = {58}
}

@article{10.5555/2831407.2831419,
author = {Faliszewski, Piotr and Hemaspaandra, Edith and Hemaspaandra, Lane A.},
title = {Weighted Electoral Control},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {Although manipulation and bribery have been extensively studied under weighted voting, there has been almost no work done on election control under weighted voting. This is unfortunate, since weighted voting appears in many important natural settings. In this paper, we study the complexity of controlling the outcome of weighted elections through adding and deleting voters. We obtain polynomial-time algorithms, NP-completeness results, and for many NP-complete cases, approximation algorithms. In particular, for scoring rules we completely characterize the complexity of weighted voter control. Our work shows that for quite a few important cases, either polynomial-time exact algorithms or polynomial-time approximation algorithms exist.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {507–542},
numpages = {36}
}

@article{10.5555/2831407.2831418,
author = {Irissappane, Athirai A. and Zhang, Jie},
title = {A Case-Based Reasoning Framework to Choose Trust Models for Different E-Marketplace Environments},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {The performance of trust models highly depend on the characteristics of the environments where they are applied. Thus, it becomes challenging to choose a suitable trust model for a given e-marketplace environment, especially when ground truth about the agent (buyer and seller) behavior is unknown (called unknown environment). We propose a case-based reasoning framework to choose suitable trust models for unknown environments, based on the intuition that if a trust model performs well in one environment, it will do so in another similar environment. Firstly, we build a case base with a number of simulated environments (with known ground truth) along with the trust models most suitable for each of them. Given an unknown environment, case-based retrieval algorithms retrieve the most similar case(s), and the trust model of the most similar case(s) is chosen as the most suitable model for the unknown environment. Evaluation results confirm the effectiveness of our framework in choosing suitable trust models for different e-marketplace environments.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {477–505},
numpages = {29}
}

@article{10.5555/2831407.2831417,
author = {De Marneffe, Marie-Catherine and Recasens, Marta and Potts, Christopher},
title = {Modeling the Lifespan of Discourse Entities with Application to Coreference Resolution},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {A discourse typically involves numerous entities, but few are mentioned more than once. Distinguishing those that die out after just one mention (singleton) from those that lead longer lives (coreferent) would dramatically simplify the hypothesis space for coreference resolution models, leading to increased performance. To realize these gains, we build a classifier for predicting the singleton/coreferent distinction. The model's feature representations synthesize linguistic insights about the factors affecting discourse entity lifespans (especially negation, modality, and attitude predication) with existing results about the benefits of "surface" (part-of-speech and n-gram-based) features for coreference resolution. The model is effective in its own right, and the feature representations help to identify the anchor phrases in bridging anaphora as well. Furthermore, incorporating the model into two very different state-of-the-art coreference resolution systems, one rule-based and the other learning-based, yields significant performance improvements.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {445–475},
numpages = {31}
}

@article{10.5555/2831407.2831416,
author = {Roijers, Diederik M. and Whiteson, Shimon and Oliehoek, Frans A.},
title = {Computing Convex Coverage Sets for Faster Multi-Objective Coordination},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {In this article, we propose new algorithms for multi-objective coordination graphs (MO-CoGs). Key to the efficiency of these algorithms is that they compute a convex coverage set (CCS) instead of a Pareto coverage set (PCS). Not only is a CCS a sufficient solution set for a large class of problems, it also has important characteristics that facilitate more efficient solutions. We propose two main algorithms for computing a CCS in MO-CoGs. Convex multi-objective variable elimination (CMOVE) computes a CCS by performing a series of agent eliminations, which can be seen as solving a series of local multi-objective subproblems. Variable elimination linear support (VELS) iteratively identifies the single weight vector w that can lead to the maximal possible improvement on a partial CCS and calls variable elimination to solve a scalarized instance of the problem for w. VELS is faster than CMOVE for small and medium numbers of objectives and can compute an ε-approximate CCS in a fraction of the runtime. In addition, we propose variants of these methods that employ AND/OR tree search instead of variable elimination to achieve memory efficiency. We analyze the runtime and space complexities of these methods, prove their correctness, and compare them empirically against a naive baseline and an existing PCS method, both in terms of memory-usage and runtime. Our results show that, by focusing on the CCS, these methods achieve much better scalability in the number of agents than the current state of the art.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {399–443},
numpages = {45}
}

@article{10.5555/2831407.2831415,
author = {Kim, Been and Chacha, Caleb M. and Shah, Julie A.},
title = {Inferring Team Task Plans from Human Meetings: A Generative Modeling Approach with Logic-Based Prior},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {We aim to reduce the burden of programming and deploying autonomous systems to work in concert with people in time-critical domains such as military field operations and disaster response. Deployment plans for these operations are frequently negotiated on-the-fly by teams of human planners. A human operator then translates the agreed-upon plan into machine instructions for the robots. We present an algorithm that reduces this translation burden by inferring the final plan from a processed form of the human team's planning conversation. Our hybrid approach combines probabilistic generative modeling with logical plan validation used to compute a highly structured prior over possible plans, enabling us to overcome the challenge of performing inference over a large solution space with only a small amount of noisy data from the team planning session. We validate the algorithm through human subject experimentations and show that it is able to infer a human team's final plan with 86% accuracy on average. We also describe a robot demonstration in which two people plan and execute a first-response collaborative task with a PR2 robot. To the best of our knowledge, this is the first work to integrate a logical planning technique within a generative model to perform plan inference.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {361–398},
numpages = {38}
}

@article{10.5555/2831407.2831414,
author = {Xue, Shan and Fern, Alan and Sheldon, Daniel},
title = {Scheduling Conservation Designs for Maximum Flexibility via Network Cascade Optimization},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {One approach to conserving endangered species is to purchase and protect a set of land parcels in a way that maximizes the expected future population spread. Unfortunately, an ideal set of parcels may have a cost that is beyond the immediate budget constraints and must thus be purchased incrementally. This raises the challenge of deciding how to schedule the parcel purchases in a way that maximizes the flexibility of budget usage while keeping population spread loss in control. In this paper, we introduce a formulation of this scheduling problem that does not rely on knowing the future budgets of an organization. In particular, we consider scheduling purchases in a way that achieves a population spread no less than desired but delays purchases as long as possible. Such schedules offer conservation planners maximum flexibility and use available budgets in the most efficient way. We develop the problem formally as a stochastic optimization problem over a network cascade model describing a commonly used model of population spread. Our solution approach is based on reducing the stochastic problem to a novel variant of the directed Steiner tree problem, which we call the set-weighted directed Steiner graph problem. We show that this problem is computationally hard, motivating the development of a primal-dual algorithm for the problem that computes both a feasible solution and a bound on the quality of an optimal solution. We evaluate the approach on both real and synthetic conservation data with a standard population spread model. The algorithm is shown to produce near optimal results and is much more scalable than more generic off-the-shelf optimizers. Finally, we evaluate a variant of the algorithm to explore the trade-offs between budget savings and population growth.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {331–360},
numpages = {30}
}

@article{10.5555/2831407.2831413,
author = {Liberatore, Paolo},
title = {Revision by History},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {This article proposes a solution to the problem of obtaining plausibility information, which is necessary to perform belief revision: given a sequence of revisions, together with their results, derive a possible initial order that has generated them; this is different from the usual assumption of starting from an all-equal initial order and modifying it by a sequence of revisions. Four semantics for iterated revision are considered: natural, restrained, lexicographic and reinforcement. For each, a necessary and sufficient condition to the existence of an order generating a given history of revisions and results is proved. Complexity is proved coNP complete in all cases but one (reinforcement revision with unbounded sequence length).},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {287–329},
numpages = {43}
}

@article{10.5555/2831407.2831412,
author = {De Cat, Broes and Denecker, Marc and Stuckey, Peter and Bruynooghe, Maurice},
title = {Lazy Model Expansion: Interleaving Grounding with Search},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {Finding satisfying assignments for the variables involved in a set of constraints can be cast as a (bounded) model generation problem: search for (bounded) models of a theory in some logic. The state-of-the-art approach for bounded model generation for rich knowledge representation languages like Answer Set Programming (ASP) and FO(undefined) and a CSP modeling language such as Zinc, is ground-and-solve: reduce the theory to a ground or propositional one and apply a search algorithm to the resulting theory.An important bottleneck is the blow-up of the size of the theory caused by the grounding phase. Lazily grounding the theory during search is a way to overcome this bottleneck. We present a theoretical framework and an implementation in the context of the FO(undefined) knowledge representation language. Instead of grounding all parts of a theory, justifications are derived for some parts of it. Given a partial assignment for the grounded part of the theory and valid justifications for the formulas of the non-grounded part, the justifications provide a recipe to construct a complete assignment that satisfies the non-grounded part. When a justification for a particular formula becomes invalid during search, a new one is derived; if that fails, the formula is split in a part to be grounded and a part that can be justified. Experimental results illustrate the power and generality of this approach.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {235–286},
numpages = {52}
}

@article{10.5555/2831407.2831411,
author = {De Haan, Ronald and Kanj, Iyad and Szeider, Stefan},
title = {On the Subexponential-Time Complexity of CSP},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {Not all NP-complete problems share the same practical hardness with respect to exact computation. Whereas some NP-complete problems are amenable to efficient computational methods, others are yet to show any such sign. It becomes a major challenge to develop a theoretical framework that is more fine-grained than the theory of NP-completeness, and that can explain the distinction between the exact complexities of various NP-complete problems. This distinction is highly relevant for constraint satisfaction problems under natural restrictions, where various shades of hardness can be observed in practice.Acknowledging the NP-hardness of such problems, one has to look beyond polynomial time computation. The theory of subexponential-time complexity provides such a framework, and has been enjoying increasing popularity in complexity theory. An instance of the constraint satisfaction problem with n variables over a domain of d values can be solved by brute-force in dn steps (omitting a polynomial factor). In this paper we study the existence of subexponential-time algorithms, that is, algorithms running in do(n) steps, for various natural restrictions of the constraint satisfaction problem. We consider both the constraint satisfaction problem in which all the constraints are given extensionally as tables, and that in which all the constraints are given intensionally in the form of global constraints. We provide tight characterizations of the subexponential-time complexity of the aforementioned problems with respect to several natural structural parameters, which allows us to draw a detailed landscape of the subexponential-time complexity of the constraint satisfaction problem. Our analysis provides fundamental results indicating whether and when one can significantly improve on the brute-force search approach for solving the constraint satisfaction problem.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {203–234},
numpages = {32}
}

@article{10.5555/2831407.2831410,
author = {Wiener, Yair and El-Yaniv, Ran},
title = {Agnostic Pointwise-Competitive Selective Classification},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {A pointwise competitive classifier from class F is required to classify identically to the best classifier in hindsight from F. For noisy, agnostic settings we present a strategy for learning pointwise-competitive classifiers from a finite training sample provided that the classifier can abstain from prediction at a certain region of its choice. For some interesting hypothesis classes and families of distributions, the measure of this rejected region is shown to be diminishing at rate β1 undefined O((polylog(m) undefined log(1/δ)/m)beta;2/2), with high probability, where m is the sample size, δ is the standard confidence parameter, and β1, β2 are smoothness parameters of a Bernstein type condition of the associated excess loss class (related to F and the 0/1 loss). Exact implementation of the proposed learning strategy is dependent on an ERM oracle that is hard to compute in the agnostic case. We thus consider a heuristic approximation procedure that is based on SVMs, and show empirically that this algorithm consistently outperforms a traditional rejection mechanism based on distance from decision boundary.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {179–201},
numpages = {23}
}

@article{10.5555/2831407.2831409,
author = {Domshlak, Carmel and Mirkis, Vitaly},
title = {Deterministic Oversubscription Planning as Heuristic Search: Abstractions and Reformulations},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {While in classical planning the objective is to achieve one of the equally attractive goal states at as low total action cost as possible, the objective in deterministic oversubscription planning (OSP) is to achieve an as valuable as possible subset of goals within a fixed allowance of the total action cost. Although numerous applications in various fields share the latter objective, no substantial algorithmic advances have been made in deterministic OSP. Tracing the key sources of progress in classical planning, we identify a severe lack of effective domain-independent approximations for OSP.With our focus here on optimal planning, our goal is to bridge this gap. Two classes of approximation techniques have been found especially useful in the context of optimal classical planning: those based on state-space abstractions and those based on logical landmarks for goal reachability. The question we study here is whether some similar-in-spirit, yet possibly mathematically different, approximation techniques can be developed for OSP. In the context of abstractions, we define the notion of additive abstractions for OSP, study the complexity of deriving effective abstractions from a rich space of hypotheses, and reveal some substantial, empirically relevant islands of tractability. In the context of landmarks, we show how standard goal-reachability landmarks of certain classical planning tasks can be compiled into the OSP task of interest, resulting in an equivalent OSP task with a lower cost allowance, and thus with a smaller search space. Our empirical evaluation confirms the effectiveness of the proposed techniques, and opens a wide gate for further developments in oversubscription planning.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {97–169},
numpages = {73}
}

@article{10.5555/2831407.2831408,
author = {De Cooman, Gert and De Bock, Jasper and Diniz, M\'{a}rcio Alves},
title = {Coherent Predictive Inference under Exchangeability with Imprecise Probabilities},
year = {2015},
issue_date = {January 2015},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {52},
number = {1},
issn = {1076-9757},
abstract = {Coherent reasoning under uncertainty can be represented in a very general manner by coherent sets of desirable gambles. In a context that does not allow for indecision, this leads to an approach that is mathematically equivalent to working with coherent conditional probabilities. If we do allow for indecision, this leads to a more general foundation for coherent (imprecise-)probabilistic inference. In this framework, and for a given finite category set, coherent predictive inference under exchangeability can be represented using Bernstein coherent cones of multivariate polynomials on the simplex generated by this category set. This is a powerful generalisation of de Finetti's Representation Theorem allowing for both imprecision and indecision.We define an inference system as a map that associates a Bernstein coherent cone of polynomials with every finite category set. Many inference principles encountered in the literature can then be interpreted, and represented mathematically, as restrictions on such maps. We discuss, as particular examples, two important inference principles: representation insensitivity--a strengthened version of Walley's representation invariance--and specificity. We show that there is an infinity of inference systems that satisfy these two principles, amongst which we discuss in particular the skeptically cautious inference system, the inference systems corresponding to (a modified version of) Walley and Bernard's Imprecise Dirichlet Multinomial Models (IDMM), the skeptical IDMM inference systems, and the Haldane inference system. We also prove that the latter produces the same posterior inferences as would be obtained using Haldane's improper prior, implying that there is an infinity of proper priors that produce the same coherent posterior inferences as Haldane's improper one. Finally, we impose an additional inference principle that allows us to characterise uniquely the immediate predictions for the IDMM inference systems.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–95},
numpages = {95}
}

@article{10.5555/2750423.2750446,
author = {Bo\v{s}ansk\'{y}, Branislav and Kiekintveld, Christopher and Lis\'{y}, Viliam and P\v{e}chou\v{c}ek, Michal},
title = {An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information},
year = {2014},
issue_date = {September 2014},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {51},
number = {1},
issn = {1076-9757},
abstract = {Developing scalable solution algorithms is one of the central problems in computational game theory. We present an iterative algorithm for computing an exact Nash equilibrium for two-player zero-sum extensive-form games with imperfect information. Our approach combines two key elements: (1) the compact sequence-form representation of extensive- form games and (2) the algorithmic framework of double-oracle methods. The main idea of our algorithm is to restrict the game by allowing the players to play only selected sequences of available actions. After solving the restricted game, new sequences are added by finding best responses to the current solution using fast algorithms.We experimentally evaluate our algorithm on a set of games inspired by patrolling scenarios, board, and card games. The results show significant runtime improvements in games admitting an equilibrium with small support, and substantial improvement in memory use even on games with large support. The improvement in memory use is particularly important because it allows our algorithm to solve much larger game instances than existing linear programming methods.Our main contributions include (1) a generic sequence-form double-oracle algorithm for solving zero-sum extensive-form games; (2) fast methods for maintaining a valid restricted game model when adding new sequences; (3) a search algorithm and pruning methods for computing best-response sequences; (4) theoretical guarantees about the convergence of the algorithm to a Nash equilibrium; (5) experimental analysis of our algorithm on several games, including an approximate version of the algorithm.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {829–866},
numpages = {38}
}

@article{10.5555/2750423.2750445,
author = {Zilli, Davide and Parson, Oliver and Merrett, Geoff V. and Rogers, Alex},
title = {A Hidden Markov Model-Based Acoustic Cicada Detector for Crowdsourced Smartphone Biodiversity Monitoring},
year = {2014},
issue_date = {September 2014},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {51},
number = {1},
issn = {1076-9757},
abstract = {In recent years, the field of computational sustainability has striven to apply artificial intelligence techniques to solve ecological and environmental problems. In ecology, a key issue for the safeguarding of our planet is the monitoring of biodiversity. Automated acoustic recognition of species aims to provide a cost-effective method for biodiversity monitoring. This is particularly appealing for detecting endangered animals with a distinctive call, such as the New Forest cicada. To this end, we pursue a crowdsourcing approach, whereby the millions of visitors to the New Forest, where this insect was historically found, will help to monitor its presence by means of a smartphone app that can detect its mating call. Existing research in the field of acoustic insect detection has typically focused upon the classification of recordings collected from fixed field microphones. Such approaches segment a lengthy audio recording into individual segments of insect activity, which are independently classified using cepstral coefficients extracted from the recording as features. This paper reports on a contrasting approach, whereby we use crowdsourcing to collect recordings via a smartphone app, and present an immediate feedback to the users as to whether an insect has been found. Our classification approach does not remove silent parts of the recording via segmentation, but instead uses the temporal patterns throughout each recording to classify the insects present. We show that our approach can successfully discriminate between the call of the New Forest cicada and similar insects found in the New Forest, and is robust to common types of environment noise. A large scale trial deployment of our smartphone app collected over 6000 reports of insect activity from over 1000 users. Despite the cicada not having been rediscovered in the New Forest, the effectiveness of this approach was confirmed for both the detection algorithm, which successfully identified the same cicada through the app in countries where the same species is still present, and of the crowdsourcing methodology, which collected a vast number of recordings and involved thousands of contributors.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {805–827},
numpages = {23}
}

@article{10.5555/2750423.2750444,
author = {Kissmann, Peter and Hoffmann, J\"{o}rg},
title = {BDD Ordering Heuristics for Classical Planning},
year = {2014},
issue_date = {September 2014},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {51},
number = {1},
issn = {1076-9757},
abstract = {Symbolic search using binary decision diagrams (BDDs) can often save large amounts of memory due to its concise representation of state sets. A decisive factor for this method's success is the chosen variable ordering. Generally speaking, it is plausible that dependent variables should be brought close together in order to reduce BDD sizes. In planning, variable dependencies are typically captured by means of causal graphs, and in preceding work these were taken as the basis for finding BDD variable orderings. Starting from the observation that the two concepts of "dependency" are actually quite different, we introduce a framework for assessing the strength of variable ordering heuristics in sub-classes of planning. It turns out that, even for extremely simple planning tasks, causal graph based variable orders may be exponentially worse than optimal.Experimental results on a wide range of variable ordering variants corroborate our theoretical findings. Furthermore, we show that dynamic reordering is much more effective at reducing BDD size, but it is not cost-effective due to a prohibitive runtime overhead. We exhibit the potential of middle-ground techniques, running dynamic reordering until simple stopping criteria hold.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {779–804},
numpages = {26}
}

@article{10.5555/2750423.2750443,
author = {Shelton, Christian R. and Ciardo, Gianfranco},
title = {Tutorial on Structured Continuous-Time Markov Processes},
year = {2014},
issue_date = {September 2014},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {51},
number = {1},
issn = {1076-9757},
abstract = {A continuous-time Markov process (CTMP) is a collection of variables indexed by a continuous quantity, time. It obeys the Markov property that the distribution over a future variable is independent of past variables given the state at the present time. We introduce continuous-time Markov process representations and algorithms for filtering, smoothing, expected sufficient statistics calculations, and model estimation, assuming no prior knowledge of continuous-time processes but some basic knowledge of probability and statistics. We begin by describing "flat" or unstructured Markov processes and then move to structured Markov processes (those arising from state spaces consisting of assignments to variables) including Kronecker, decision-diagram, and continuous-time Bayesian network representations. We provide the first connection between decision-diagrams and continuous- time Bayesian networks.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {725–778},
numpages = {54}
}

@article{10.5555/2750423.2750442,
author = {\v{C}epek, Ond\v{r}ej and Gursk\'{y}, \v{S}tefan and Ku\v{c}era, Petr},
title = {On Minimum Representations of Matched Formulas},
year = {2014},
issue_date = {September 2014},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {51},
number = {1},
issn = {1076-9757},
abstract = {A Boolean formula in conjunctive normal form (CNF) is called matched if the system of sets of variables which appear in individual clauses has a system of distinct representatives. Each matched CNF is trivially satisfiable (each clause can be satisfied by its representative variable). Another property which is easy to see, is that the class of matched CNFs is not closed under partial assignment of truth values to variables. This latter property leads to a fact (proved here) that given two matched CNFs it is co-NP complete to decide whether they are logically equivalent. The construction in this proof leads to another result: a much shorter and simpler proof of Σ2p-completeness of Boolean minimization for matched CNFs. The main result of this paper deals with the structure of clause minimum CNFs. We prove here that if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF representation of f is matched.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {707–724},
numpages = {18}
}

@article{10.5555/2750423.2750441,
author = {Stefanoni, Giorgio and Motik, Boris and Kr\"{o}tzsch, Markus and Rudolph, Sebastian},
title = {The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases},
year = {2014},
issue_date = {September 2014},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {51},
number = {1},
issn = {1076-9757},
abstract = {OWL 2 EL is a popular ontology language that supports role inclusions--axioms of the form S1...Sn ⊆ S that capture compositional properties of roles. Role inclusions closely correspond to context-free grammars, which was used to show that answering conjunctive queries (CQs) over OWL 2 EL knowledge bases with unrestricted role inclusions is undecidable. However, OWL 2 EL inherits from OWL 2 DL the syntactic regularity restriction on role inclusions, which ensures that role chains implying a particular role can be described using a finite automaton (FA). This is sufficient to ensure decidability of CQ answering; however, the FAs can be worst-case exponential in size so the known approaches do not provide a tight upper complexity bound.In this paper, we solve this open problem and show that answering CQs over OWL 2 EL knowledge bases is PSpace-complete in combined complexity (i.e., the complexity measured in the total size of the input). To this end, we use a novel encoding of regular role inclusions using bounded-stack pushdown automata--that is, FAs extended with a stack of bounded size. Apart from theoretical interest, our encoding can be used in practical tableau algorithms to avoid the exponential blowup due to role inclusions. In addition, we sharpen the lower complexity bound and show that the problem is PSPACE-hard even if we consider only role inclusions as part of the input (i.e., the query and all other parts of the knowledge base are fxed). Finally, we turn our attention to navigational queries over OWL 2 EL knowledge bases, and we show that answering positive, converse-free conjunctive graph XPath queries is PSPACE-complete as well; this is interesting since allowing the converse operator in queries is known to make the problem ExpTime-hard. Thus, in this paper we present several important contributions to the landscape of the complexity of answering expressive queries over description logic knowledge bases.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {645–705},
numpages = {61}
}

@article{10.5555/2750423.2750440,
author = {Nguyen, Phong and Hilario, Melanie and Kalousis, Alexandros},
title = {Using Meta-Mining to Support Data Mining Workflow Planning and Optimization},
year = {20

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr