HOME > Journal Current TOC
Artificial Intelligence
Journal Prestige (SJR): 0.88 Citation Impact (citeScore): 4 Number of Followers: 174 Hybrid journal (It can contain Open Access articles) ISSN (Print) 0004-3702 Published by Elsevier [3162 journals] |
- Optimizing positional scoring rules for rank aggregation
- Abstract: Publication date: Available online 13 November 2018Source: Artificial IntelligenceAuthor(s): Ioannis Caragiannis, Xenophon Chatzigeorgiou, George A. Krimpas, Alexandros A. Voudouris Nowadays, several crowdsourcing projects exploit social choice methods for computing an aggregate ranking of alternatives given individual rankings provided by workers. Motivated by such systems, we consider a setting where each worker is asked to rank a fixed (small) number of alternatives and, then, a positional scoring rule is used to compute the aggregate ranking. Among the apparently infinite such rules, what is the best one to use' To answer this question, we assume that we have partial access to an underlying true ranking. Then, the important optimization problem to be solved is to compute the positional scoring rule whose outcome, when applied to the profile of individual rankings, is as close as possible to the part of the underlying true ranking we know. We study this fundamental problem from a theoretical viewpoint and present positive and negative complexity results and, furthermore, complement our theoretical findings with experiments on real-world and synthetic data.
- Abstract: Publication date: Available online 13 November 2018Source: Artificial IntelligenceAuthor(s): Ioannis Caragiannis, Xenophon Chatzigeorgiou, George A. Krimpas, Alexandros A. Voudouris Nowadays, several crowdsourcing projects exploit social choice methods for computing an aggregate ranking of alternatives given individual rankings provided by workers. Motivated by such systems, we consider a setting where each worker is asked to rank a fixed (small) number of alternatives and, then, a positional scoring rule is used to compute the aggregate ranking. Among the apparently infinite such rules, what is the best one to use' To answer this question, we assume that we have partial access to an underlying true ranking. Then, the important optimization problem to be solved is to compute the positional scoring rule whose outcome, when applied to the profile of individual rankings, is as close as possible to the part of the underlying true ranking we know. We study this fundamental problem from a theoretical viewpoint and present positive and negative complexity results and, furthermore, complement our theoretical findings with experiments on real-world and synthetic data.
- Explanation in artificial intelligence: Insights from the social sciences
- Abstract: Publication date: Available online 27 October 2018Source: Artificial IntelligenceAuthor(s): Tim Miller There has been a recent resurgence in the area of explainable artificial intelligence as researchers and practitioners seek to provide more transparency to their algorithms. Much of this research is focused on explicitly explaining decisions or actions to a human observer, and it should not be controversial to say that looking at how humans explain to each other can serve as a useful starting point for explanation in artificial intelligence. However, it is fair to say that most work in explainable artificial intelligence uses only the researchers' intuition of what constitutes a ‘good’ explanation. There exists vast and valuable bodies of research in philosophy, psychology, and cognitive science of how people define, generate, select, evaluate, and present explanations, which argues that people employ certain cognitive biases and social expectations to the explanation process. This paper argues that the field of explainable artificial intelligence can build on this existing research, and reviews relevant papers from philosophy, cognitive psychology/science, and social psychology, which study these topics. It draws out some important findings, and discusses ways that these can be infused with work on explainable artificial intelligence.
- Abstract: Publication date: Available online 27 October 2018Source: Artificial IntelligenceAuthor(s): Tim Miller There has been a recent resurgence in the area of explainable artificial intelligence as researchers and practitioners seek to provide more transparency to their algorithms. Much of this research is focused on explicitly explaining decisions or actions to a human observer, and it should not be controversial to say that looking at how humans explain to each other can serve as a useful starting point for explanation in artificial intelligence. However, it is fair to say that most work in explainable artificial intelligence uses only the researchers' intuition of what constitutes a ‘good’ explanation. There exists vast and valuable bodies of research in philosophy, psychology, and cognitive science of how people define, generate, select, evaluate, and present explanations, which argues that people employ certain cognitive biases and social expectations to the explanation process. This paper argues that the field of explainable artificial intelligence can build on this existing research, and reviews relevant papers from philosophy, cognitive psychology/science, and social psychology, which study these topics. It draws out some important findings, and discusses ways that these can be infused with work on explainable artificial intelligence.
- Probably Bounded Suboptimal Heuristic Search
- Abstract: Publication date: Available online 25 October 2018Source: Artificial IntelligenceAuthor(s): Roni Stern, Gal Dreiman, Richard Valenzano Finding an optimal solution to a search problem is often desirable, but can be too difficult in many cases. A common approach in such cases is to try to find a solution whose suboptimality is bounded, where a parameter ϵ defines how far from optimal a solution can be while still being acceptable. A scarcely studied alternative is to try to find a solution that is probably optimal, where a parameter δ defines the confidence required in the solution's optimality. This paper explores this option and introduces the concept of a probably bounded-suboptimal search (pBS search) algorithm. Such a search algorithm accepts two parameters, ϵ and δ, and outputs a solution that with probability at least 1−δ costs at most 1+ϵ times the optimal solution. A general algorithmic framework for pBS search algorithms is proposed. Several instances of this framework are described and analyzed theoretically and experimentally on a range of search domains. Results show that pBS search algorithms are often faster than a state-of-the-art bounded-suboptimal search algorithm. This shows in practice that finding solutions that satisfy a given suboptimality bound with high probability can be done faster than finding solutions that satisfy the same suboptimality bound with certainty.
- Abstract: Publication date: Available online 25 October 2018Source: Artificial IntelligenceAuthor(s): Roni Stern, Gal Dreiman, Richard Valenzano Finding an optimal solution to a search problem is often desirable, but can be too difficult in many cases. A common approach in such cases is to try to find a solution whose suboptimality is bounded, where a parameter ϵ defines how far from optimal a solution can be while still being acceptable. A scarcely studied alternative is to try to find a solution that is probably optimal, where a parameter δ defines the confidence required in the solution's optimality. This paper explores this option and introduces the concept of a probably bounded-suboptimal search (pBS search) algorithm. Such a search algorithm accepts two parameters, ϵ and δ, and outputs a solution that with probability at least 1−δ costs at most 1+ϵ times the optimal solution. A general algorithmic framework for pBS search algorithms is proposed. Several instances of this framework are described and analyzed theoretically and experimentally on a range of search domains. Results show that pBS search algorithms are often faster than a state-of-the-art bounded-suboptimal search algorithm. This shows in practice that finding solutions that satisfy a given suboptimality bound with high probability can be done faster than finding solutions that satisfy the same suboptimality bound with certainty.
- Forgetting in multi-agent modal logics
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Liangda Fang, Yongmei Liu, Hans van Ditmarsch In the past decades, forgetting has been investigated for many logics and has found many applications in knowledge representation and reasoning. In this paper, we study forgetting in multi-agent modal logics. We adopt the semantic definition of existential bisimulation quantifiers as that of forgetting. We resort to canonical formulas of modal logics introduced by Moss. An arbitrary modal formula is equivalent to the disjunction of a unique set of satisfiable canonical formulas. We show that, for the logics of Kn, Dn, Tn, K45n, KD45n and S5n, the result of forgetting an atom from a satisfiable canonical formula can be computed by simply substituting the literals of the atom with ⊤. Thus we show that these logics are closed under forgetting, and hence have uniform interpolation. Finally, we generalize the above results to include common knowledge of propositional formulas.
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Liangda Fang, Yongmei Liu, Hans van Ditmarsch In the past decades, forgetting has been investigated for many logics and has found many applications in knowledge representation and reasoning. In this paper, we study forgetting in multi-agent modal logics. We adopt the semantic definition of existential bisimulation quantifiers as that of forgetting. We resort to canonical formulas of modal logics introduced by Moss. An arbitrary modal formula is equivalent to the disjunction of a unique set of satisfiable canonical formulas. We show that, for the logics of Kn, Dn, Tn, K45n, KD45n and S5n, the result of forgetting an atom from a satisfiable canonical formula can be computed by simply substituting the literals of the atom with ⊤. Thus we show that these logics are closed under forgetting, and hence have uniform interpolation. Finally, we generalize the above results to include common knowledge of propositional formulas.
- On Coarser Interval Temporal Logics
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Emilio Muñoz-Velasco, Mercedes Pelegrín, Pietro Sala, Guido Sciavicco, Ionel Eduard Stan The primary characteristic of interval temporal logic is that intervals, rather than points, are taken as the primitive ontological entities. Given their generally bad computational behavior of interval temporal logics, several techniques exist to produce decidable and computationally affordable temporal logics based on intervals. In this paper we take inspiration from Golumbic and Shamir's coarser interval algebras, which generalize the classical Allen's Interval Algebra, in order to define two previously unknown variants of Halpern and Shoham's logic (HS) based on coarser relations. We prove that, perhaps surprisingly, the satisfiability problem for the coarsest of the two variants, namely HS3, not only is decidable, but PSpace-complete in the finite/discrete case, and PSpace-hard in any other case; besides proving its complexity bounds, we implement a tableau-based satisfiability checker for it and test it against a systematically generated benchmark. Our results are strengthened by showing that not all coarser-than-Allen's relations are a guarantee of decidability, as we prove that the second variant, namely HS7, remains undecidable in all interesting cases.
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Emilio Muñoz-Velasco, Mercedes Pelegrín, Pietro Sala, Guido Sciavicco, Ionel Eduard Stan The primary characteristic of interval temporal logic is that intervals, rather than points, are taken as the primitive ontological entities. Given their generally bad computational behavior of interval temporal logics, several techniques exist to produce decidable and computationally affordable temporal logics based on intervals. In this paper we take inspiration from Golumbic and Shamir's coarser interval algebras, which generalize the classical Allen's Interval Algebra, in order to define two previously unknown variants of Halpern and Shoham's logic (HS) based on coarser relations. We prove that, perhaps surprisingly, the satisfiability problem for the coarsest of the two variants, namely HS3, not only is decidable, but PSpace-complete in the finite/discrete case, and PSpace-hard in any other case; besides proving its complexity bounds, we implement a tableau-based satisfiability checker for it and test it against a systematically generated benchmark. Our results are strengthened by showing that not all coarser-than-Allen's relations are a guarantee of decidability, as we prove that the second variant, namely HS7, remains undecidable in all interesting cases.
- Privacy preserving region optimal algorithms for symmetric and asymmetric
DCOPs- Abstract: Publication date: Available online 11 October 2018Source: Artificial IntelligenceAuthor(s): Tal Grinshpoun, Tamir Tassa, Vadim Levit, Roie Zivan Region-optimal algorithms are local search algorithms for solving Distributed Constraint Optimization Problems (DCOPs). In each iteration of the search in such algorithms, every agent selects a group of agents that comply with some selection criteria (each algorithm specifies different criteria). Then, the agent who selected the group, called the mediator, collects assignment information from the group and neighboring agents outside the group, in order to find an optimal set of assignments for its group's agents. A contest between mediators of adjacent groups determines which groups will replace their assignments in that iteration to the found optimal ones. In this work we present a framework called RODA (Region Optimal DCOP Algorithm) that encompasses the algorithms in the region optimality family, and in particular any method for selecting groups. We devise a secure implementation of RODA, called P-RODA, which preserves constraint privacy and partial decision privacy. Our discussion covers both symmetric and asymmetric DCOPs. The two main cryptographic means that enable this privacy preservation are secret sharing and homomorphic encryption. We estimate the computational overhead of P-RODA with respect to RODA and give an upper bound that depends on the group and domain sizes and on the graph topology, but not on the number of agents. The estimations are substantiated with experimental results, including experiments on a simulator, that compare the performance of P-RODA to that of its competing algorithm, P-Max-Sum.
- Abstract: Publication date: Available online 11 October 2018Source: Artificial IntelligenceAuthor(s): Tal Grinshpoun, Tamir Tassa, Vadim Levit, Roie Zivan Region-optimal algorithms are local search algorithms for solving Distributed Constraint Optimization Problems (DCOPs). In each iteration of the search in such algorithms, every agent selects a group of agents that comply with some selection criteria (each algorithm specifies different criteria). Then, the agent who selected the group, called the mediator, collects assignment information from the group and neighboring agents outside the group, in order to find an optimal set of assignments for its group's agents. A contest between mediators of adjacent groups determines which groups will replace their assignments in that iteration to the found optimal ones. In this work we present a framework called RODA (Region Optimal DCOP Algorithm) that encompasses the algorithms in the region optimality family, and in particular any method for selecting groups. We devise a secure implementation of RODA, called P-RODA, which preserves constraint privacy and partial decision privacy. Our discussion covers both symmetric and asymmetric DCOPs. The two main cryptographic means that enable this privacy preservation are secret sharing and homomorphic encryption. We estimate the computational overhead of P-RODA with respect to RODA and give an upper bound that depends on the group and domain sizes and on the graph topology, but not on the number of agents. The estimations are substantiated with experimental results, including experiments on a simulator, that compare the performance of P-RODA to that of its competing algorithm, P-Max-Sum.