Journal Cover
Artificial Intelligence
Journal Prestige (SJR): 0.88
Citation Impact (citeScore): 4
Number of Followers: 187  
 
  Hybrid Journal Hybrid journal (It can contain Open Access articles)
ISSN (Print) 0004-3702
Published by Elsevier Homepage  [3161 journals]
  • Gelfond–Zhang aggregates as propositional formulas
    • Abstract: Publication date: Available online 15 February 2019Source: Artificial IntelligenceAuthor(s): Pedro Cabalar, Jorge Fandinno, Torsten Schaub, Sebastian Schellhorn Answer Set Programming (ASP) has become a popular and widespread paradigm for practical Knowledge Representation thanks to its expressiveness and the available enhancements of its input language. One of such enhancements is the use of aggregates, for which different semantic proposals have been made. In this paper, we show that any ASP aggregate interpreted under Gelfond and Zhang's (GZ) semantics can be replaced (under strong equivalence) by a propositional formula. Restricted to the original GZ syntax, the resulting formula is reducible to a disjunction of conjunctions of literals but the formulation is still applicable even when the syntax is extended to allow for arbitrary formulas (including nested aggregates) in the condition. Once GZ-aggregates are represented as formulas, we establish a formal comparison (in terms of the logic of Here-and-There) to Ferraris' (F) aggregates, which are defined by a different formula translation involving nested implications. In particular, we prove that if we replace an F-aggregate by a GZ-aggregate in a rule head, we do not lose answer sets (although more can be gained). This extends the previously known result that the opposite happens in rule bodies, i.e., replacing a GZ-aggregate by an F-aggregate in the body may yield more answer sets. Finally, we characterise a class of aggregates for which GZ- and F-semantics coincide.
       
  • Foundations of Ontology-Based Data Access under Bag Semantics
    • Abstract: Publication date: Available online 15 February 2019Source: Artificial IntelligenceAuthor(s): Charalampos Nikolaou, Egor V. Kostylev, George Konstantinidis, Mark Kaminski, Bernardo Cuenca Grau, Ian Horrocks Ontology-based data access (OBDA) is a popular approach for integrating and querying multiple data sources by means of a shared ontology. The ontology is linked to the sources using mappings, which assign to ontology predicates views over the data. The conventional semantics of OBDA is set-based—that is, the extension of the views defined by the mappings does not contain duplicate tuples. This treatment is, however, in disagreement with the standard semantics of database views and database management systems in general, which is based on bags and where duplicate tuples are retained by default. The distinction between set and bag semantics in databases is very significant in practice, and it influences the evaluation of aggregate queries.In this article, we propose and study a bag semantics for OBDA which provides a solid foundation for the future study of aggregate and analytic queries. Our semantics is compatible with both the bag semantics of database views and the set-based conventional semantics of OBDA. Furthermore, it is compatible with existing bag-based semantics for data exchange recently proposed in the literature. We show that adopting a bag semantics makes conjunctive query answering in OBDA coNP-hard in data complexity. To regain tractability of query answering, we consider suitable restrictions along three dimensions, namely, the query language, the ontology language, and the adoption of the unique name assumption. Our investigation shows a complete picture of the computational properties of query answering under bag semantics over ontologies in the DL-Lite family.
       
  • Clustering ensemble based on sample's stability
    • Abstract: Publication date: Available online 14 February 2019Source: Artificial IntelligenceAuthor(s): Feijiang Li, Yuhua Qian, Jieting Wang, Chuangyin Dang, Liping Jing The objective of clustering ensemble is to find the underlying structure of data based on a set of clustering results. It has been observed that the samples can change between clusters in different clustering results. This change shows that samples may have different contributions to the detection of the underlying structure. However, the existing clustering ensemble methods treat all sample equally. To tackle this deficiency, we introduce the stability of a sample to quantify its contribution and present a methodology to determine this stability. We propose two formulas accord with this methodology to calculate sample's stability. Then, we develop a clustering ensemble algorithm based on the sample's stability. With either formula, this algorithm divides a data set into two classes: cluster core and cluster halo. With the core and halo, the proposed algorithm then discovers a clear structure using the samples in the cluster core and assigns samples in the cluster halo to the clear structure gradually. The experiments on eight synthetic data sets illustrate how the proposed algorithm works. This algorithm statistically outperforms twelve state-of-the-art clustering ensemble algorithms on ten real data sets from UCI and six document data sets. The experimental analysis on the case of image segmentation shows that cluster cores discovered by the stability are rational.
       
  • Toward any-language zero-shot topic classification of textual documents
    • Abstract: Publication date: Available online 13 February 2019Source: Artificial IntelligenceAuthor(s): Yangqiu Song, Shyam Upadhyay, Haoruo Peng, Stephen Mayhew, Dan Roth In this paper, we present a zero-shot classification approach to document classification in any language into topics which can be described by English keywords. This is done by embedding both labels and documents into a same semantic space that allows one to compute meaningful semantic similarity between a document and a potential label. The embedding space can be done by either mapping into a Wikipedia-based semantic representation or learning cross-lingual embeddings. Consequently, performance could suffer when Wikipedia in the target language is small or there is no enough training corpus to train a good embedding space for low-resource languages. Thus, for the low-resource languages, we further use a word-level dictionary to convert documents into a high-resource language, and then perform classification based on the high-resource language. This approach can be applied to thousands of languages, which can be contrasted with machine translation, which is a supervision-heavy approach and can be done for about 100 languages. We also develop a ranking algorithm that makes use of language similarity metrics to automatically select a good pivot or bridging high-resource language, and show that this significantly improves classification of low-resource language documents, performing comparably to the best bridge possible.
       
  • Learning Tractable Bayesian Networks in the Space of Elimination Orders
    • Abstract: Publication date: Available online 12 February 2019Source: Artificial IntelligenceAuthor(s): Marco Benjumeda, Concha Bielza, Pedro Larrañaga The computational complexity of inference is now one of the most relevant topics in the field of Bayesian networks. Although the literature contains approaches that learn Bayesian networks from high dimensional datasets, traditional methods do not bound the inference complexity of the learned models, often producing models where exact inference is intractable. This paper focuses on learning tractable Bayesian networks from data. To address this problem, we propose strategies for learning Bayesian networks in the space of elimination orders. In this manner, we can efficiently bound the inference complexity of the networks during the learning process. Searching in the combined space of directed acyclic graphs and elimination orders can be extremely computationally demanding. We demonstrate that one type of elimination trees, which we define as valid, can be used as an equivalence class of directed acyclic graphs and elimination orders, removing redundancy. We propose methods for incrementally compiling local changes made to directed acyclic graphs in elimination trees and for searching for elimination trees of low width. Using these methods, we can move through the space of valid elimination trees in polynomial time with respect to the number of network variables and in linear time with respect to treewidth. Experimental results show that our approach successfully bounds the inference complexity of the learned models, while it is competitive with other state-of-the-art methods in terms of fitting to data.
       
  • Rendezvous in Planar Environments with Obstacles and Unknown Initial
           Distance
    • Abstract: Publication date: Available online 10 February 2019Source: Artificial IntelligenceAuthor(s): Deniz Ozsoyeller, Andrew Beveridge, Volkan Isler In the rendezvous search problem, two or more robots at unknown locations should meet somewhere in the environment as quickly as possible. We study the symmetric rendezvous search problem in unknown planar environments with polygonal obstacles. In the symmetric version of the problem, the robots must execute the same rendezvous strategy. We consider the case where the initial distance between the robots is unknown, and the robot is unaware of its and the other robots' locations in the environment. We first design a symmetric rendezvous strategy for two robots and perform its theoretical analysis. We prove that the competitive ratio of our strategy is O(d/D). Here, d is the initial distance between the robots and D is the length of the sides of the square robots. In unknown polygonal environments, robots should explore the environment to achieve rendezvous. Therefore, we propose a coverage algorithm that guarantees the complete coverage of the environment. Next, we extend our symmetric rendezvous strategy to n robots and prove that its competitive ratio is O(d/(nD)). Here, d is the maximal pairwise distance between the robots. Finally, we validate our algorithms in simulations.
       
  • Distributional semantics of objects in visual scenes in comparison to text
    • Abstract: Publication date: Available online 7 February 2019Source: Artificial IntelligenceAuthor(s): Timo Lüddecke, Alejandro Agostini, Michael Fauth, Minija Tamosiunaite, Florentin Wörgötter The distributional hypothesis states that the meaning of a concept is defined through the contexts it occurs in. In practice, often word co-occurrence and proximity are analyzed in text corpora for a given word to obtain a real-valued semantic word vector, which is taken to (at least partially) encode the meaning of this word. Here we transfer this idea from text to images, where pre-assigned labels of other objects or activations of convolutional neural networks serve as context. We propose a simple algorithm that extracts and processes object contexts from an image database and yields semantic vectors for objects. We show empirically that these representations exhibit on par performance with state-of-the-art distributional models over a set of conventional objects. For this we employ well-known word benchmarks in addition to a newly proposed object-centric benchmark.
       
  • Complexity Results for Preference Aggregation over (m)CP-nets:
           Pareto and Majority Voting
    • Abstract: Publication date: Available online 31 January 2019Source: Artificial IntelligenceAuthor(s): Thomas Lukasiewicz, Enrico Malizia Aggregating preferences over combinatorial domains has many applications in artificial intelligence (AI). Given the inherent exponential nature of preferences over combinatorial domains, compact representation languages are needed to represent them, and (m)CP-nets are among the most studied ones. Sequential and global voting are two different ways of aggregating preferences represented via CP-nets. In sequential voting, agents' preferences are aggregated feature-by-feature. For this reason, sequential voting may exhibit voting paradoxes, i.e., the possibility to select sub-optimal outcomes when preferences have specific feature dependencies. To avoid paradoxes in sequential voting, one has often assumed the (quite) restrictive constraint of O-legality, which imposes a shared common topological order among all the agents' CP-nets. On the contrary, in global voting, CP-nets are considered as a whole during the preference aggregation process. For this reason, global voting is immune from the voting paradoxes of sequential voting, and hence there is no need to impose restrictions over the CP-nets' structure when preferences are aggregated via global voting. Sequential voting over O-legal CP-nets received much attention, and O-legality of CP-nets has often been required in other studies. On the other hand, global voting over non-O-legal CP-nets has not carefully been analyzed, despite it was explicitly stated in the literature that a theoretical comparison between global and sequential voting was highly promising and a precise complexity analysis for global voting has been asked for multiple times. In quite a few works, only very partial results on the complexity of global voting over CP-nets have been given. In this paper, we start to fill this gap by carrying out a thorough computational complexity analysis of global voting tasks, for Pareto and majority voting, over not necessarily O-legal acyclic binary polynomially connected (m)CP-nets. We show that all these problems belong to various levels of the polynomial hierarchy, and some of them are even in P or LOGSPACE. Our results are a notable achievement, given that the previously known upper bound for most of these problems was the complexity class EXPTIME. We provide various exact complexity results showing tight lower bounds and matching upper bounds for problems that (up to now) did not have any explicit non-obvious lower bound.
       
  • ALC +Ontologies&rft.title=Artificial+Intelligence&rft.issn=0004-3702&rft.date=&rft.volume=">Query Inseparability for ALC Ontologies
    • Abstract: Publication date: Available online 30 January 2019Source: Artificial IntelligenceAuthor(s): Elena Botoeva, Carsten Lutz, Vladislav Ryzhikov, Frank Wolter, Michael Zakharyaschev We investigate the problem whether two ALC ontologies are indistinguishable (or inseparable) by means of queries in a given signature, which is fundamental for ontology engineering tasks such as ontology versioning, modularisation, update, and forgetting. We consider both knowledge base (KB) and TBox inseparability. For KBs, we give model-theoretic criteria in terms of (finite partial) homomorphisms and products and prove that this problem is undecidable for conjunctive queries (CQs), but 2ExpTime-complete for unions of CQs (UCQs). The same results hold if (U)CQs are replaced by rooted (U)CQs, where every variable is connected to an answer variable. We also show that inseparability by CQs is still undecidable if one KB is given in the lightweight DL EL and if no restrictions are imposed on the signature of the CQs. We also consider the problem whether two ALC TBoxes give the same answers to any query over any ABox in a given signature and show that, for CQs, this problem is undecidable, too. We then develop model-theoretic criteria for HornALC TBoxes and show using tree automata that, in contrast, inseparability becomes decidable and 2ExpTime-complete, even ExpTime-complete when restricted to (unions of) rooted CQs.
       
  • Computing programs for generalized planning using a classical planner
    • Abstract: Publication date: Available online 30 January 2019Source: Artificial IntelligenceAuthor(s): Javier Segovia-Aguas, Sergio Jiménez Celorrio, Anders Jonsson Generalized planning is the task of generating a single solution (a generalized plan) that is valid for multiple planning instances. In this paper we introduce a novel formalism for representing generalized plans that borrows two mechanisms from structured programming: control flow and procedure calls. On one hand, control flow structures allow to compactly represent generalized plans. On the other hand, procedure calls allow to represent hierarchical and recursive solutions as well as to reuse existing generalized plans. The paper also presents a compilation from generalized planning into classical planning which allows us to compute generalized plans with off-the-shelf planners. The compilation can incorporate prior knowledge in the form of auxiliary procedures which expands the applicability of the approach to more challenging tasks. Experiments show that a classical planner using our compilation can compute generalized plans that solve a wide range of generalized planning tasks, including sorting lists of variable size or DFS traversing variable-size binary trees. Additionally the paper presents an extension of the compilation for computing generalized plans when generalization requires a high-level state representation that is not provided a priori. This extension brings a new landscape of benchmarks to classical planning since classification tasks can naturally be modeled as generalized planning tasks, and hence, as classical planning tasks. Finally the paper shows that the compilation can be extended to compute control knowledge for off-the-shelf planners and solve planning instances that are difficult to solve without such additional knowledge.
       
  • Ridesharing car detection by transfer learning
    • Abstract: Publication date: Available online 30 January 2019Source: Artificial IntelligenceAuthor(s): Leye Wang, Xu Geng, Xiaojuan Ma, Daqing Zhang, Qiang Yang Ridesharing platforms like Uber and Didi are getting more and more popular around the world. However, unauthorized ridesharing activities taking advantages of the sharing economy can greatly impair the healthy development of this emerging industry. As the first step to regulate on-demand ride services and eliminate black market, we design a method to detect ridesharing cars from a pool of cars based on their trajectories. Since licensed ridesharing car traces are not openly available and may be completely missing in some cities due to legal issues, we turn to transferring knowledge from public transport open data, i.e, taxis and buses, to ridesharing detection among ordinary vehicles. We propose a novel two-stage transfer learning framework, called CoTrans. In Stage 1, we take taxi and bus data as input to learn a random forest (RF) classifier using trajectory features shared by taxis/buses and ridesharing/other cars. Then, we use the RF to label all the candidate cars. In Stage 2, leveraging the subset of high confident labels from the previous stage as input, we further learn a convolutional neural network (CNN) classifier for ridesharing detection, and iteratively refine RF and CNN, as well as the feature set, via a co-training process. Finally, we use the resulting ensemble of RF and CNN to identify the ridesharing cars in the candidate pool. Experiments on real car, taxi and bus traces show that CoTrans, with no need of a pre-labeled ridesharing dataset, can outperform state-of-the-art transfer learning methods with an accuracy comparable to human labeling.
       
  • First-order stable model semantics with intensional functions
    • Abstract: Publication date: Available online 26 January 2019Source: Artificial IntelligenceAuthor(s): Michael Bartholomew, Joohyung Lee In classical logic, nonBoolean fluents, such as the location of an object, can be naturally described by functions. However, this is not the case in answer set programs, where the values of functions are pre-defined, and nonmonotonicity of the semantics is related to minimizing the extents of predicates but has nothing to do with functions. We extend the first-order stable model semantics by Ferraris, Lee, and Lifschitz to allow intensional functions – functions that are specified by a logic program just like predicates are specified. We show that many known properties of the stable model semantics are naturally extended to this formalism and compare it with other related approaches to incorporating intensional functions. Furthermore, we use this extension as a basis for defining Answer Set Programming Modulo Theories (ASPMT), analogous to the way that Satisfiability Modulo Theories (SMT) is defined, allowing for SMT-like effective first-order reasoning in the context of ASP. Using SMT solving techniques involving functions, ASPMT can be applied to domains containing real numbers and alleviates the grounding problem. We show that other approaches to integrating ASP and CSP/SMT can be related to special cases of ASPMT in which functions are limited to non-intensional ones.
       
 
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
 
Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs
Your IP address: 54.226.23.160
 
About JournalTOCs
API
Help
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-