Followed Journals
Similar Journals
HOME > Journal Current TOC
Artificial Intelligence
Journal Prestige (SJR): 0.88 Citation Impact (citeScore): 4 Number of Followers: 232 Hybrid journal (It can contain Open Access articles) ISSN (Print) 0004-3702 Published by Elsevier [3181 journals] |
- Preference elicitation and robust winner determination for single- and
multi-winner social choice- Abstract: Publication date: Available online 12 November 2019Source: Artificial IntelligenceAuthor(s): Tyler Lu, Craig Boutilier The use of voting schemes based on rankings of alternatives to solve social choice problems can often impose significant burden on voters, both in terms of communication and cognitive requirements. In this paper, we develop techniques for preference elicitation in voting settings (i.e., vote elicitation) that can alleviate this burden by minimizing the amount of preference information needed to find (approximately or exactly) optimal outcomes. We first describe robust optimization techniques for determining winning alternatives given partial preference information (i.e., partial rankings) using the notion of minimax regret. We show that the corresponding computational problem is tractable for some important voting rules, and intractable for others. We then use the solution to the minimax-regret optimization as the basis for vote elicitation schemes that determine appropriate preference queries for voters to quickly reduce potential regret. We apply these techniques to multi-winner social choice problems as well, in which a slate of alternatives must be selected, developing both exact and greedy robust optimization procedures. Empirical results on several data sets validate the effectiveness of our techniques.
- Abstract: Publication date: Available online 12 November 2019Source: Artificial IntelligenceAuthor(s): Tyler Lu, Craig Boutilier The use of voting schemes based on rankings of alternatives to solve social choice problems can often impose significant burden on voters, both in terms of communication and cognitive requirements. In this paper, we develop techniques for preference elicitation in voting settings (i.e., vote elicitation) that can alleviate this burden by minimizing the amount of preference information needed to find (approximately or exactly) optimal outcomes. We first describe robust optimization techniques for determining winning alternatives given partial preference information (i.e., partial rankings) using the notion of minimax regret. We show that the corresponding computational problem is tractable for some important voting rules, and intractable for others. We then use the solution to the minimax-regret optimization as the basis for vote elicitation schemes that determine appropriate preference queries for voters to quickly reduce potential regret. We apply these techniques to multi-winner social choice problems as well, in which a slate of alternatives must be selected, developing both exact and greedy robust optimization procedures. Empirical results on several data sets validate the effectiveness of our techniques.
- Recursively modeling other agents for decision making: A research
perspective- Abstract: Publication date: Available online 12 November 2019Source: Artificial IntelligenceAuthor(s): Prashant Doshi, Piotr Gmytrasiewicz, Edmund Durfee Individuals exhibit theory of mind, attributing beliefs, intent, and mental states to others as explanations of observed actions. Dennett's intentional stance offers an analogous abstraction for computational agents seeking to understand, explain, or predict others' behaviors. These recognized theories provide a formal basis to ongoing investigations of recursive modeling. We review and situate various frameworks for recursive modeling that have been studied in game- and decision- theories, and have yielded methods useful to AI researchers. Sustained attention given to these frameworks has produced new analyses and methods with an aim toward making recursive modeling practicable.Indeed, we also review some emerging uses and the insights these yielded, which are indicative of pragmatic progress in this area. The significance of these frameworks is that higher-order reasoning is critical to correctly recognizing others' intent or outthinking opponents. Such reasoning has been utilized in academic, business, military, security, and other contexts both to train and inform decision-making agents in organizational and strategic contexts, and also to more realistically predict and best respond to other agents' intent.
- Abstract: Publication date: Available online 12 November 2019Source: Artificial IntelligenceAuthor(s): Prashant Doshi, Piotr Gmytrasiewicz, Edmund Durfee Individuals exhibit theory of mind, attributing beliefs, intent, and mental states to others as explanations of observed actions. Dennett's intentional stance offers an analogous abstraction for computational agents seeking to understand, explain, or predict others' behaviors. These recognized theories provide a formal basis to ongoing investigations of recursive modeling. We review and situate various frameworks for recursive modeling that have been studied in game- and decision- theories, and have yielded methods useful to AI researchers. Sustained attention given to these frameworks has produced new analyses and methods with an aim toward making recursive modeling practicable.Indeed, we also review some emerging uses and the insights these yielded, which are indicative of pragmatic progress in this area. The significance of these frameworks is that higher-order reasoning is critical to correctly recognizing others' intent or outthinking opponents. Such reasoning has been utilized in academic, business, military, security, and other contexts both to train and inform decision-making agents in organizational and strategic contexts, and also to more realistically predict and best respond to other agents' intent.
- Mind the Gaps: Assuring the Safety of Autonomous Systems from an
Engineering, Ethical, and Legal Perspective- Abstract: Publication date: Available online 9 November 2019Source: Artificial IntelligenceAuthor(s): Simon Burton, Ibrahim Habli, Tom Lawton, John McDermid, Phillip Morgan, Zoe Porter This paper brings together a multi-disciplinary perspective from systems engineering, ethics, and law to articulate a common language in which to reason about the multi-faceted problem of assuring the safety of autonomous systems. The paper's focus is on the “gaps” that arise across the development process: the semantic gap, where normal conditions for a complete specification of intended functionality are not present; the responsibility gap, where normal conditions for holding human actors morally responsible for harm are not present; and the liability gap, where normal conditions for securing compensation to victims of harm are not present. By categorising these “gaps” we can expose with greater precision key sources of uncertainty and risk with autonomous systems. This can inform the development of more detailed models of safety assurance and contribute to more effective risk control.
- Abstract: Publication date: Available online 9 November 2019Source: Artificial IntelligenceAuthor(s): Simon Burton, Ibrahim Habli, Tom Lawton, John McDermid, Phillip Morgan, Zoe Porter This paper brings together a multi-disciplinary perspective from systems engineering, ethics, and law to articulate a common language in which to reason about the multi-faceted problem of assuring the safety of autonomous systems. The paper's focus is on the “gaps” that arise across the development process: the semantic gap, where normal conditions for a complete specification of intended functionality are not present; the responsibility gap, where normal conditions for holding human actors morally responsible for harm are not present; and the liability gap, where normal conditions for securing compensation to victims of harm are not present. By categorising these “gaps” we can expose with greater precision key sources of uncertainty and risk with autonomous systems. This can inform the development of more detailed models of safety assurance and contribute to more effective risk control.
- Representing and Planning with Interacting Actions and Privacy
- Abstract: Publication date: Available online 5 November 2019Source: Artificial IntelligenceAuthor(s): Shashank Shekhar, Ronen I. Brafman Interacting actions – actions whose joint effect differs from the union of their individual effects – are challenging both to represent and to plan with due to their combinatorial nature. So far, there have been few attempts to provide a succinct language for representing them that can also support efficient centralized planning and distributed privacy preserving planning. In this paper we suggest an approach for representing interacting actions succinctly and show how such a domain model can be compiled into a standard single-agent planning problem as well as to privacy preserving multi-agent planning. We test the performance of our method on a number of novel domains involving interacting actions and privacy.
- Abstract: Publication date: Available online 5 November 2019Source: Artificial IntelligenceAuthor(s): Shashank Shekhar, Ronen I. Brafman Interacting actions – actions whose joint effect differs from the union of their individual effects – are challenging both to represent and to plan with due to their combinatorial nature. So far, there have been few attempts to provide a succinct language for representing them that can also support efficient centralized planning and distributed privacy preserving planning. In this paper we suggest an approach for representing interacting actions succinctly and show how such a domain model can be compiled into a standard single-agent planning problem as well as to privacy preserving multi-agent planning. We test the performance of our method on a number of novel domains involving interacting actions and privacy.
- Realizability of Three-Valued Semantics for Abstract Dialectical
Frameworks- Abstract: Publication date: Available online 4 November 2019Source: Artificial IntelligenceAuthor(s): Jörg Pührer We investigate fundamental properties of three-valued semantics for abstract dialectical frameworks (ADFs). In particular, we deal with realizability, i.e., the question whether there exists an ADF that has a given set of interpretations as its semantics. We provide necessary and sufficient conditions that hold for a set of three-valued interpretations whenever there is an ADF realizing it under admissible, complete, grounded, or preferred semantics. Moreover, we show how to construct such an ADF in case of realizability. Our results lay the ground for studying the expressiveness of ADFs under three-valued semantics. Since ADFs generalize many existing approaches, our results have immediate impact on many argumentation formalisms including abstract argumentation frameworks. As first applications, we study implications of our results on the existence of certain join operators on ADFs. Furthermore, we exploit our (exact) characterizations to obtain realizability results also for a more relaxed setting, where realizing ADFs may contain hidden statements.
- Abstract: Publication date: Available online 4 November 2019Source: Artificial IntelligenceAuthor(s): Jörg Pührer We investigate fundamental properties of three-valued semantics for abstract dialectical frameworks (ADFs). In particular, we deal with realizability, i.e., the question whether there exists an ADF that has a given set of interpretations as its semantics. We provide necessary and sufficient conditions that hold for a set of three-valued interpretations whenever there is an ADF realizing it under admissible, complete, grounded, or preferred semantics. Moreover, we show how to construct such an ADF in case of realizability. Our results lay the ground for studying the expressiveness of ADFs under three-valued semantics. Since ADFs generalize many existing approaches, our results have immediate impact on many argumentation formalisms including abstract argumentation frameworks. As first applications, we study implications of our results on the existence of certain join operators on ADFs. Furthermore, we exploit our (exact) characterizations to obtain realizability results also for a more relaxed setting, where realizing ADFs may contain hidden statements.
- Probabilistic Sentence Satisfiability: An Approach to PSAT
- Abstract: Publication date: Available online 4 November 2019Source: Artificial IntelligenceAuthor(s): T.C. Henderson, R. Simmons, B. Serbinowski, M. Cline, D. Sacharny, X. Fan, A. Mitiche Information analysis often involves heterogeneous sources expressed as logical sentences, numerical models, sensor data, etc. Each of these has its own way to describe uncertainty or error; e.g., frequency analysis, algorithmic truncation, floating point roundoff, Gaussian distributions, etc. A unifying framework is proposed here to represent this information as logical sentences with associated probabilities in order to allow the inference of the probability of a query sentence.Given such a knowledge base in Conjunctive Normal Form (CNF) for use by an intelligent agent, with probabilities assigned to the conjuncts, the probability of any new query sentence can be determined by solving the Probabilistic Satisfiability Problem (PSAT). This involves finding a consistent probability distribution over the atoms (if they are independent) or complete conjunction set of the atoms. For each sentence in the knowledge base, we propose to produce an equation in terms of atoms and conditional probabilities. This system of equations is then solved numerically to get a solution consistent with the sentence probabilities. Finding such a solution is called the Probabilistic Sentence Satisfiability (PS-SAT) problem. In particular, findings include:1.For independent logical variables:(a)atom probabilities which solve PS-SAT also provide a PSAT solution.(b)numerical experiments demonstrate a q-superlinear convergence rate for most test cases.(c)problems with up to 1,000 variables and 300 sentences are solved.2.For general knowledge bases (i.e., variables not independent):(a)both atom and a subset of conditional probabilities must be found,(b)a solution to PS-SAT does not guarantee a solution to PSAT, but most empirical results provide such a solution.(c)The convergence rate for equations with non-independent variables also appears q-superlinear.
- Abstract: Publication date: Available online 4 November 2019Source: Artificial IntelligenceAuthor(s): T.C. Henderson, R. Simmons, B. Serbinowski, M. Cline, D. Sacharny, X. Fan, A. Mitiche Information analysis often involves heterogeneous sources expressed as logical sentences, numerical models, sensor data, etc. Each of these has its own way to describe uncertainty or error; e.g., frequency analysis, algorithmic truncation, floating point roundoff, Gaussian distributions, etc. A unifying framework is proposed here to represent this information as logical sentences with associated probabilities in order to allow the inference of the probability of a query sentence.Given such a knowledge base in Conjunctive Normal Form (CNF) for use by an intelligent agent, with probabilities assigned to the conjuncts, the probability of any new query sentence can be determined by solving the Probabilistic Satisfiability Problem (PSAT). This involves finding a consistent probability distribution over the atoms (if they are independent) or complete conjunction set of the atoms. For each sentence in the knowledge base, we propose to produce an equation in terms of atoms and conditional probabilities. This system of equations is then solved numerically to get a solution consistent with the sentence probabilities. Finding such a solution is called the Probabilistic Sentence Satisfiability (PS-SAT) problem. In particular, findings include:1.For independent logical variables:(a)atom probabilities which solve PS-SAT also provide a PSAT solution.(b)numerical experiments demonstrate a q-superlinear convergence rate for most test cases.(c)problems with up to 1,000 variables and 300 sentences are solved.2.For general knowledge bases (i.e., variables not independent):(a)both atom and a subset of conditional probabilities must be found,(b)a solution to PS-SAT does not guarantee a solution to PSAT, but most empirical results provide such a solution.(c)The convergence rate for equations with non-independent variables also appears q-superlinear.
- Variable Neighborhood Search for Graphical Model Energy Minimization
- Abstract: Publication date: Available online 31 October 2019Source: Artificial IntelligenceAuthor(s): Abdelkader Ouali, David Allouche, Simon de Givry, Samir Loudni, Yahia Lebbah, Lakhdar Loukil, Patrice Boizumault Graphical models factorize a global probability distribution/energy function as the product/ sum of local functions. A major inference task, known as MAP in Markov Random Fields and MPE in Bayesian Networks, is to find a global assignment of all the variables with maximum a posteriori probability/minimum energy. A usual distinction on MAP solving methods is complete/incomplete, i.e. the ability to prove optimality or not. Most complete methods rely on tree search, while incomplete methods rely on local search. Among them, we study Variable Neighborhood Search (VNS) for graphical models. In this paper, we propose an iterative approach above VNS that uses (partial) tree search inside its local neighborhood exploration. The proposed approach performs several neighborhood explorations of increasing search complexity, by controlling two parameters, the discrepancy limit and the neighborhood size. Thus, optimality of the obtained solutions can be proven when the neighborhood size is maximal and with unbounded tree search. We further propose a parallel version of our method improving its anytime behavior on difficult instances coming from a large graphical model benchmark. Last we experiment on the challenging minimum energy problem found in Computational Protein Design, showing the practical benefit of our parallel version. A solver is available at https://github.com/toulbar2/toulbar2.
- Abstract: Publication date: Available online 31 October 2019Source: Artificial IntelligenceAuthor(s): Abdelkader Ouali, David Allouche, Simon de Givry, Samir Loudni, Yahia Lebbah, Lakhdar Loukil, Patrice Boizumault Graphical models factorize a global probability distribution/energy function as the product/ sum of local functions. A major inference task, known as MAP in Markov Random Fields and MPE in Bayesian Networks, is to find a global assignment of all the variables with maximum a posteriori probability/minimum energy. A usual distinction on MAP solving methods is complete/incomplete, i.e. the ability to prove optimality or not. Most complete methods rely on tree search, while incomplete methods rely on local search. Among them, we study Variable Neighborhood Search (VNS) for graphical models. In this paper, we propose an iterative approach above VNS that uses (partial) tree search inside its local neighborhood exploration. The proposed approach performs several neighborhood explorations of increasing search complexity, by controlling two parameters, the discrepancy limit and the neighborhood size. Thus, optimality of the obtained solutions can be proven when the neighborhood size is maximal and with unbounded tree search. We further propose a parallel version of our method improving its anytime behavior on difficult instances coming from a large graphical model benchmark. Last we experiment on the challenging minimum energy problem found in Computational Protein Design, showing the practical benefit of our parallel version. A solver is available at https://github.com/toulbar2/toulbar2.
- Scalable Constraint-based Virtual Data Center Allocation
- Abstract: Publication date: Available online 31 October 2019Source: Artificial IntelligenceAuthor(s): Sam Bayless, Nodir Kodirov, Syed M. Iqbal, Ivan Beschastnikh, Holger H. Hoos, Alan J. Hu Constraint-based techniques can solve challenging problems arising in highly diverse applications. This paper considers the problem of virtual data center (VDC) allocation, an important, emerging challenge for modern data center operators. To address this problem, we introduce Netsolver, a system for VDC allocation that is based on constraint solving. Netsolver represents a major improvement over existing approaches: it is sound, complete, and scalable, providing support for end-to-end, multi-path bandwidth guarantees across all the layers of hosting infrastructure, from servers to top-of-rack switches to aggregation switches to access routers. Netsolver scales to realistic data center sizes and VDC topologies, typically requiring just seconds to allocate VDCs of 5–15 virtual machines to physical data centers with 1000+ servers, maintaining this efficiency even when the data center is nearly saturated. In many cases, Netsolver can allocate 150%−300% as many total VDCs to the same physical data center as previous methods. Finally, we show how Netsolver can be extended with additional optimization constraints, such as VM affinity and hotspot minimization, demonstrating the flexibility of our approach.The performance and flexibility of Netsolver is made possible by our formalization of the VDC allocation problem in terms of multi-commodity flows, and the corresponding efficient handling of network flow problems in the underlying constraint solvers. This shows the importance of supporting flow-based constraints, which are more mature in ILP- vs. SMT-based constraint solving.
- Abstract: Publication date: Available online 31 October 2019Source: Artificial IntelligenceAuthor(s): Sam Bayless, Nodir Kodirov, Syed M. Iqbal, Ivan Beschastnikh, Holger H. Hoos, Alan J. Hu Constraint-based techniques can solve challenging problems arising in highly diverse applications. This paper considers the problem of virtual data center (VDC) allocation, an important, emerging challenge for modern data center operators. To address this problem, we introduce Netsolver, a system for VDC allocation that is based on constraint solving. Netsolver represents a major improvement over existing approaches: it is sound, complete, and scalable, providing support for end-to-end, multi-path bandwidth guarantees across all the layers of hosting infrastructure, from servers to top-of-rack switches to aggregation switches to access routers. Netsolver scales to realistic data center sizes and VDC topologies, typically requiring just seconds to allocate VDCs of 5–15 virtual machines to physical data centers with 1000+ servers, maintaining this efficiency even when the data center is nearly saturated. In many cases, Netsolver can allocate 150%−300% as many total VDCs to the same physical data center as previous methods. Finally, we show how Netsolver can be extended with additional optimization constraints, such as VM affinity and hotspot minimization, demonstrating the flexibility of our approach.The performance and flexibility of Netsolver is made possible by our formalization of the VDC allocation problem in terms of multi-commodity flows, and the corresponding efficient handling of network flow problems in the underlying constraint solvers. This shows the importance of supporting flow-based constraints, which are more mature in ILP- vs. SMT-based constraint solving.
- New models for generating hard random boolean formulas and disjunctive
logic programs- Abstract: Publication date: Available online 30 October 2019Source: Artificial IntelligenceAuthor(s): Giovanni Amendola, Francesco Ricca, Miroslaw Truszczynski We propose two models of random quantified boolean formulas and their natural random disjunctive logic program counterparts. The models extend the standard models of random k-CNF formulas and the Chen-Interian model of random 2QBFs. The first model controls the generation of programs and QSAT formulas by imposing a specific structure on rules and clauses, respectively. The second model is based on a family of QSAT formulas in a non-clausal form. We provide theoretical bounds for the phase transition region in our models, and show experimentally the presence of the easy-hard-easy pattern and its alignment with the location of the phase transition. We show that boolean formulas and logic programs from our models are significantly harder than those obtained from the standard k-CNF and Chen-Interian models, and that their combination yields formulas and programs that are “super-hard” to evaluate. We also provide evidence suggesting that formulas from one of our models are well suited for assessing solvers tuned to real-world instances. Finally, it is noteworthy that, to the best of our knowledge, our models and results on random disjunctive logic programs are the first of their kind.
- Abstract: Publication date: Available online 30 October 2019Source: Artificial IntelligenceAuthor(s): Giovanni Amendola, Francesco Ricca, Miroslaw Truszczynski We propose two models of random quantified boolean formulas and their natural random disjunctive logic program counterparts. The models extend the standard models of random k-CNF formulas and the Chen-Interian model of random 2QBFs. The first model controls the generation of programs and QSAT formulas by imposing a specific structure on rules and clauses, respectively. The second model is based on a family of QSAT formulas in a non-clausal form. We provide theoretical bounds for the phase transition region in our models, and show experimentally the presence of the easy-hard-easy pattern and its alignment with the location of the phase transition. We show that boolean formulas and logic programs from our models are significantly harder than those obtained from the standard k-CNF and Chen-Interian models, and that their combination yields formulas and programs that are “super-hard” to evaluate. We also provide evidence suggesting that formulas from one of our models are well suited for assessing solvers tuned to real-world instances. Finally, it is noteworthy that, to the best of our knowledge, our models and results on random disjunctive logic programs are the first of their kind.
- Algorithms for estimating the partition function of restricted Boltzmann
machines- Abstract: Publication date: Available online 30 October 2019Source: Artificial IntelligenceAuthor(s): Oswin Krause, Asja Fischer, Christian Igel Accurate estimates of the normalization constants (partition functions) of energy-based probabilistic models (Markov random fields) are highly important, for example, for assessing the performance of models, monitoring training progress, and conducting likelihood ratio tests. Several algorithms for estimating the partition function (in relation to a reference distribution) have been introduced, including Annealed Importance Sampling (AIS) and Bennett's Acceptance Ratio method (BAR). However, their conceptual similarities and differences have not been worked out so far and systematic comparisons of their behavior in practice have been missing. We devise a unifying theoretical framework for these algorithms, which comprises existing variants and suggests new approaches. It is based on a generalized form of Crooks' equality linking the expectation over a distribution of samples generated by a transition operator to the expectation over the distribution induced by the reversed operator. The framework covers different ways of generating samples, such as parallel tempering and path sampling. An empirical comparison revealed the differences between the methods when estimating the partition function of restricted Boltzmann machines and Ising models. In our experiments, BAR using parallel tempering worked well with a small number of bridging distributions, while path sampling based AIS performed best when many bridging distributions were available. Because BAR gave the overall best results, we favor it over AIS. Furthermore, the experiments showed the importance of choosing a proper reference distribution.
- Abstract: Publication date: Available online 30 October 2019Source: Artificial IntelligenceAuthor(s): Oswin Krause, Asja Fischer, Christian Igel Accurate estimates of the normalization constants (partition functions) of energy-based probabilistic models (Markov random fields) are highly important, for example, for assessing the performance of models, monitoring training progress, and conducting likelihood ratio tests. Several algorithms for estimating the partition function (in relation to a reference distribution) have been introduced, including Annealed Importance Sampling (AIS) and Bennett's Acceptance Ratio method (BAR). However, their conceptual similarities and differences have not been worked out so far and systematic comparisons of their behavior in practice have been missing. We devise a unifying theoretical framework for these algorithms, which comprises existing variants and suggests new approaches. It is based on a generalized form of Crooks' equality linking the expectation over a distribution of samples generated by a transition operator to the expectation over the distribution induced by the reversed operator. The framework covers different ways of generating samples, such as parallel tempering and path sampling. An empirical comparison revealed the differences between the methods when estimating the partition function of restricted Boltzmann machines and Ising models. In our experiments, BAR using parallel tempering worked well with a small number of bridging distributions, while path sampling based AIS performed best when many bridging distributions were available. Because BAR gave the overall best results, we favor it over AIS. Furthermore, the experiments showed the importance of choosing a proper reference distribution.
- Computing AES related-key differential characteristics with constraint
programming- Abstract: Publication date: Available online 22 October 2019Source: Artificial IntelligenceAuthor(s): David Gerault, Pascal Lafourcade, Marine Minier, Christine Solnon Cryptanalysis aims at testing the properties of encryption processes, and this usually implies solving hard optimization problems. In this paper, we focus on related-key differential attacks for the Advanced Encryption Standard (AES), which is the encryption standard for block ciphers. To mount these attacks, cryptanalysts need to solve the optimal related-key differential characteristic problem. Dedicated approaches do not scale well for this problem, and need weeks to solve its hardest instances.In this paper, we improve existing Constraint Programming (CP) approaches for computing optimal related-key differential characteristics: we add new constraints that detect inconsistencies sooner, and we introduce a new decomposition of the problem in two steps. These improvements allow us to compute all optimal related-key differential characteristics for AES-128, AES-192 and AES-256 in a few hours.
- Abstract: Publication date: Available online 22 October 2019Source: Artificial IntelligenceAuthor(s): David Gerault, Pascal Lafourcade, Marine Minier, Christine Solnon Cryptanalysis aims at testing the properties of encryption processes, and this usually implies solving hard optimization problems. In this paper, we focus on related-key differential attacks for the Advanced Encryption Standard (AES), which is the encryption standard for block ciphers. To mount these attacks, cryptanalysts need to solve the optimal related-key differential characteristic problem. Dedicated approaches do not scale well for this problem, and need weeks to solve its hardest instances.In this paper, we improve existing Constraint Programming (CP) approaches for computing optimal related-key differential characteristics: we add new constraints that detect inconsistencies sooner, and we introduce a new decomposition of the problem in two steps. These improvements allow us to compute all optimal related-key differential characteristics for AES-128, AES-192 and AES-256 in a few hours.
- Gradient conjugate priors and multi-layer neural networks
- Abstract: Publication date: Available online 18 October 2019Source: Artificial IntelligenceAuthor(s): Pavel Gurevich, Hannes Stuke The paper deals with learning probability distributions of observed data by artificial neural networks. We suggest a so-called gradient conjugate prior (GCP) update appropriate for neural networks, which is a modification of the classical Bayesian update for conjugate priors. We establish a connection between the gradient conjugate prior update and the maximization of the log-likelihood of the predictive distribution. Unlike for the Bayesian neural networks, we use deterministic weights of neural networks, but rather assume that the ground truth distribution is normal with unknown mean and variance and learn by the neural networks the parameters of a prior (normal-gamma distribution) for these unknown mean and variance. The update of the parameters is done, using the gradient that, at each step, directs towards minimizing the Kullback–Leibler divergence from the prior to the posterior distribution (both being normal-gamma). We obtain a corresponding dynamical system for the prior's parameters and analyze its properties. In particular, we study the limiting behavior of all the prior's parameters and show how it differs from the case of the classical full Bayesian update. The results are validated on synthetic and real world data sets.
- Abstract: Publication date: Available online 18 October 2019Source: Artificial IntelligenceAuthor(s): Pavel Gurevich, Hannes Stuke The paper deals with learning probability distributions of observed data by artificial neural networks. We suggest a so-called gradient conjugate prior (GCP) update appropriate for neural networks, which is a modification of the classical Bayesian update for conjugate priors. We establish a connection between the gradient conjugate prior update and the maximization of the log-likelihood of the predictive distribution. Unlike for the Bayesian neural networks, we use deterministic weights of neural networks, but rather assume that the ground truth distribution is normal with unknown mean and variance and learn by the neural networks the parameters of a prior (normal-gamma distribution) for these unknown mean and variance. The update of the parameters is done, using the gradient that, at each step, directs towards minimizing the Kullback–Leibler divergence from the prior to the posterior distribution (both being normal-gamma). We obtain a corresponding dynamical system for the prior's parameters and analyze its properties. In particular, we study the limiting behavior of all the prior's parameters and show how it differs from the case of the classical full Bayesian update. The results are validated on synthetic and real world data sets.
- The complexity of exact learning of acyclic conditional preference
networks from swap examples- Abstract: Publication date: Available online 10 October 2019Source: Artificial IntelligenceAuthor(s): Eisa Alanazi, Malek Mouhoub, Sandra Zilles Learning of user preferences, as represented by, for example, Conditional Preference Networks (CP-nets), has become a core issue in AI research. Recent studies investigate learning of CP-nets from randomly chosen examples or from membership and equivalence queries. To assess the optimality of learning algorithms as well as to better understand the combinatorial structure of classes of CP-nets, it is helpful to calculate certain learning-theoretic information complexity parameters. This article focuses on the frequently studied case of exact learning from so-called swap examples, which express preferences among objects that differ in only one attribute. It presents bounds on or exact values of some well-studied information complexity parameters, namely the VC dimension, the teaching dimension, and the recursive teaching dimension, for classes of acyclic CP-nets. We further provide algorithms that exactly learn tree-structured and general acyclic CP-nets from membership queries. Using our results on complexity parameters, we prove that our algorithms, as well as another query learning algorithm for acyclic CP-nets presented in the literature, are near-optimal.
- Abstract: Publication date: Available online 10 October 2019Source: Artificial IntelligenceAuthor(s): Eisa Alanazi, Malek Mouhoub, Sandra Zilles Learning of user preferences, as represented by, for example, Conditional Preference Networks (CP-nets), has become a core issue in AI research. Recent studies investigate learning of CP-nets from randomly chosen examples or from membership and equivalence queries. To assess the optimality of learning algorithms as well as to better understand the combinatorial structure of classes of CP-nets, it is helpful to calculate certain learning-theoretic information complexity parameters. This article focuses on the frequently studied case of exact learning from so-called swap examples, which express preferences among objects that differ in only one attribute. It presents bounds on or exact values of some well-studied information complexity parameters, namely the VC dimension, the teaching dimension, and the recursive teaching dimension, for classes of acyclic CP-nets. We further provide algorithms that exactly learn tree-structured and general acyclic CP-nets from membership queries. Using our results on complexity parameters, we prove that our algorithms, as well as another query learning algorithm for acyclic CP-nets presented in the literature, are near-optimal.
- Grounded Language Interpretation of Robotic Commands through Structured
Learning- Abstract: Publication date: Available online 7 October 2019Source: Artificial IntelligenceAuthor(s): Andrea Vanzo, Danilo Croce, Emanuele Bastianelli, Roberto Basili, Daniele Nardi The presence of robots in everyday life is increasing day by day at a growing pace. Industrial and working environments, health-care assistance in public or domestic areas can benefit from robots' services to accomplish manifold tasks that are difficult and annoying for humans. In such scenarios, Natural Language interactions, enabling collaboration and robot control, are meant to be situated, in the sense that both the user and the robot access and make reference to the environment. Contextual knowledge may thus play a key role in solving inherent ambiguities of grounded language as, for example, the prepositional phrase attachment.In this work, we present a linguistic pipeline for semantic processing of robotic commands, that combines discriminative structured learning, distributional semantics and contextual evidence extracted from the working environment. The final goal is to make the interpretation process of linguistic exchanges depending on physical, cognitive and language-dependent aspects. We present, formalize and discuss an adaptive Spoken Language Understanding chain for robotic commands, that explicitly depends on the operational context during both the learning and processing stages. The resulting framework allows to model heterogeneous information concerning the environment (e.g., positional information about the objects and their properties) and to inject it in the learning process. Empirical results demonstrate a significant contribution of such additional dimensions, achieving up to a 25% of relative error reduction with respect to a pipeline that only exploits linguistic evidence.
- Abstract: Publication date: Available online 7 October 2019Source: Artificial IntelligenceAuthor(s): Andrea Vanzo, Danilo Croce, Emanuele Bastianelli, Roberto Basili, Daniele Nardi The presence of robots in everyday life is increasing day by day at a growing pace. Industrial and working environments, health-care assistance in public or domestic areas can benefit from robots' services to accomplish manifold tasks that are difficult and annoying for humans. In such scenarios, Natural Language interactions, enabling collaboration and robot control, are meant to be situated, in the sense that both the user and the robot access and make reference to the environment. Contextual knowledge may thus play a key role in solving inherent ambiguities of grounded language as, for example, the prepositional phrase attachment.In this work, we present a linguistic pipeline for semantic processing of robotic commands, that combines discriminative structured learning, distributional semantics and contextual evidence extracted from the working environment. The final goal is to make the interpretation process of linguistic exchanges depending on physical, cognitive and language-dependent aspects. We present, formalize and discuss an adaptive Spoken Language Understanding chain for robotic commands, that explicitly depends on the operational context during both the learning and processing stages. The resulting framework allows to model heterogeneous information concerning the environment (e.g., positional information about the objects and their properties) and to inject it in the learning process. Empirical results demonstrate a significant contribution of such additional dimensions, achieving up to a 25% of relative error reduction with respect to a pipeline that only exploits linguistic evidence.
- Coalitional Games Induced by Matching Problems: Complexity and Islands of
Tractability for the Shapley Value- Abstract: Publication date: Available online 3 October 2019Source: Artificial IntelligenceAuthor(s): Gianluigi Greco, Francesco Lupia, Francesco Scarcello The paper focuses on cooperative games where the worth of any coalition of agents is determined by the optimal value of a matching problem on (possibly weighted) graphs. These games come in different forms that can be grouped in two broad classes, namely of matching and allocation games, and they have a wide spectrum of applications, ranging from two-sided markets where buyers and sellers are encoded as vertices in a graph, to allocation problems where indivisible goods have to be assigned (matched) to agents in a fair way, possibly using monetary compensations.The Shapley value and the related notion of Banzhaf value have often been identified as appropriate solution concepts for many applications of matching/allocation games, but their computation is intractable in general. It is known that these concepts can be computed in polynomial time for matching games on unweighted trees and on graphs having degree at most two. However, it was open whether or not such positive results could be extended to the more general case of graphs having bounded treewidth, and to the case of allocation problems on weighted graphs.The paper provides a positive answer to these questions, by showing that computing the Shapley value and the Banzhaf value is feasible in polynomial time for the following classes of games: matching games over unweighted graphs having bounded treewidth, allocation games over weighted graphs having bounded treewidth, and allocation games over weighted graphs and such that each good is of interest for two agents at most. Without such structural restrictions, computing these solution concepts on allocation games is instead shown to be #P-hard, even in the case of unweighted graphs.
- Abstract: Publication date: Available online 3 October 2019Source: Artificial IntelligenceAuthor(s): Gianluigi Greco, Francesco Lupia, Francesco Scarcello The paper focuses on cooperative games where the worth of any coalition of agents is determined by the optimal value of a matching problem on (possibly weighted) graphs. These games come in different forms that can be grouped in two broad classes, namely of matching and allocation games, and they have a wide spectrum of applications, ranging from two-sided markets where buyers and sellers are encoded as vertices in a graph, to allocation problems where indivisible goods have to be assigned (matched) to agents in a fair way, possibly using monetary compensations.The Shapley value and the related notion of Banzhaf value have often been identified as appropriate solution concepts for many applications of matching/allocation games, but their computation is intractable in general. It is known that these concepts can be computed in polynomial time for matching games on unweighted trees and on graphs having degree at most two. However, it was open whether or not such positive results could be extended to the more general case of graphs having bounded treewidth, and to the case of allocation problems on weighted graphs.The paper provides a positive answer to these questions, by showing that computing the Shapley value and the Banzhaf value is feasible in polynomial time for the following classes of games: matching games over unweighted graphs having bounded treewidth, allocation games over weighted graphs having bounded treewidth, and allocation games over weighted graphs and such that each good is of interest for two agents at most. Without such structural restrictions, computing these solution concepts on allocation games is instead shown to be #P-hard, even in the case of unweighted graphs.
- Artificial systems with moral capacities' A research design and its
implementation in a geriatric care system- Abstract: Publication date: Available online 1 October 2019Source: Artificial IntelligenceAuthor(s): Catrin Misselhorn The development of increasingly intelligent and autonomous technologies will eventually lead to these systems having to face morally problematic situations. This gave rise to the development of artificial morality, an emerging field in artificial intelligence which explores whether and how artificial systems can be furnished with moral capacities. This will have a deep impact on our lives. Yet, the methodological foundations of artificial morality are still sketchy and often far off from possible applications. One important area of application of artificial systems with moral capacities is geriatric care. The goal of this article is to afford the methodological foundations for artificial morality, i.e., for implementing moral capacities in artificial systems in general, and to discuss them with respect to an assistive system in geriatric care which is capable of moral learning.
- Abstract: Publication date: Available online 1 October 2019Source: Artificial IntelligenceAuthor(s): Catrin Misselhorn The development of increasingly intelligent and autonomous technologies will eventually lead to these systems having to face morally problematic situations. This gave rise to the development of artificial morality, an emerging field in artificial intelligence which explores whether and how artificial systems can be furnished with moral capacities. This will have a deep impact on our lives. Yet, the methodological foundations of artificial morality are still sketchy and often far off from possible applications. One important area of application of artificial systems with moral capacities is geriatric care. The goal of this article is to afford the methodological foundations for artificial morality, i.e., for implementing moral capacities in artificial systems in general, and to discuss them with respect to an assistive system in geriatric care which is capable of moral learning.
- Leadership in Singleton Congestion Games: What is Hard and What is Easy
- Abstract: Publication date: Available online 27 September 2019Source: Artificial IntelligenceAuthor(s): Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, Stefano Coniglio We study the problem of computing Stackelberg equilibria in Stackelberg games whose underlying structure is a congestion game, focusing on singleton congestion games, i.e., on congestion games where each player can choose a single resource, and assuming that one of them acts as leader while the other ones act as followers. We provide a comprehensive picture of the computational complexity of finding equilibria in these games, investigating different forms of commitment (pure-strategy and mixed-strategy) and followers' tie-breaking rules (optimistic and pessimistic). We identify two features of such games, namely, identical/different action spaces and monotonic/generic cost functions, by which we provide a complete characterization of the cases in which the equilibrium-finding problem is either easy or hard. In particular, we show that, in the case where the action spaces are different, the cost the leader incurs in an optimistic or pessimistic Stackelberg equilibrium cannot be approximated in polynomial time up to any polynomial factor in the size of the game unless P=NP, independently of the cost functions being monotonic or generic. This result holds even when the commitment is restricted to pure strategies. For general mixed-strategy commitments, we show that a similar result also holds when the players have generic cost functions, even if their action spaces are identical. Furthermore, we prove that the case with identical action spaces and monotonic cost functions is easy. We also improve the efficiency of a polynomial-time algorithm available in the literature for the computation of a socially optimal Nash equilibrium in non-Stackelberg singleton congestion games with identical action spaces and generic cost functions, and we extend it to the computation of a Stackelberg equilibrium for the case where the leader is restricted to playing pure strategies. For the cases in which the problem of finding an equilibrium is hard, we show how, in the optimistic setting where the followers break ties in favor of the leader, the problem can be formulated via mixed-integer linear programming techniques. We also provide an experimental evaluation of our algorithms both on random instances and on instances generated from our inapproximability reductions.
- Abstract: Publication date: Available online 27 September 2019Source: Artificial IntelligenceAuthor(s): Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, Stefano Coniglio We study the problem of computing Stackelberg equilibria in Stackelberg games whose underlying structure is a congestion game, focusing on singleton congestion games, i.e., on congestion games where each player can choose a single resource, and assuming that one of them acts as leader while the other ones act as followers. We provide a comprehensive picture of the computational complexity of finding equilibria in these games, investigating different forms of commitment (pure-strategy and mixed-strategy) and followers' tie-breaking rules (optimistic and pessimistic). We identify two features of such games, namely, identical/different action spaces and monotonic/generic cost functions, by which we provide a complete characterization of the cases in which the equilibrium-finding problem is either easy or hard. In particular, we show that, in the case where the action spaces are different, the cost the leader incurs in an optimistic or pessimistic Stackelberg equilibrium cannot be approximated in polynomial time up to any polynomial factor in the size of the game unless P=NP, independently of the cost functions being monotonic or generic. This result holds even when the commitment is restricted to pure strategies. For general mixed-strategy commitments, we show that a similar result also holds when the players have generic cost functions, even if their action spaces are identical. Furthermore, we prove that the case with identical action spaces and monotonic cost functions is easy. We also improve the efficiency of a polynomial-time algorithm available in the literature for the computation of a socially optimal Nash equilibrium in non-Stackelberg singleton congestion games with identical action spaces and generic cost functions, and we extend it to the computation of a Stackelberg equilibrium for the case where the leader is restricted to playing pure strategies. For the cases in which the problem of finding an equilibrium is hard, we show how, in the optimistic setting where the followers break ties in favor of the leader, the problem can be formulated via mixed-integer linear programming techniques. We also provide an experimental evaluation of our algorithms both on random instances and on instances generated from our inapproximability reductions.
- On rational entailment for propositional typicality logic
- Abstract: Publication date: Available online 27 September 2019Source: Artificial IntelligenceAuthor(s): Richard Booth, Giovanni Casini, Thomas Meyer, Ivan Varzinczak Propositional Typicality Logic (PTL) is a recently proposed logic, obtained by enriching classical propositional logic with a typicality operator capturing the most typical (alias normal or conventional) situations in which a given sentence holds. The semantics of PTL is in terms of ranked models as studied in the well-known KLM approach to preferential reasoning and therefore KLM-style rational consequence relations can be embedded in PTL. In spite of the non-monotonic features introduced by the semantics adopted for the typicality operator, the obvious Tarskian definition of entailment for PTL remains monotonic and is therefore not appropriate in many contexts. Our first important result is an impossibility theorem showing that a set of proposed postulates that at first all seem appropriate for a notion of entailment with regard to typicality cannot be satisfied simultaneously. Closer inspection reveals that this result is best interpreted as an argument for advocating the development of more than one type of PTL entailment. In the spirit of this interpretation, we investigate three different (semantic) versions of entailment for PTL, each one based on the definition of rational closure as introduced by Lehmann and Magidor for KLM-style conditionals, and constructed using different notions of minimality.
- Abstract: Publication date: Available online 27 September 2019Source: Artificial IntelligenceAuthor(s): Richard Booth, Giovanni Casini, Thomas Meyer, Ivan Varzinczak Propositional Typicality Logic (PTL) is a recently proposed logic, obtained by enriching classical propositional logic with a typicality operator capturing the most typical (alias normal or conventional) situations in which a given sentence holds. The semantics of PTL is in terms of ranked models as studied in the well-known KLM approach to preferential reasoning and therefore KLM-style rational consequence relations can be embedded in PTL. In spite of the non-monotonic features introduced by the semantics adopted for the typicality operator, the obvious Tarskian definition of entailment for PTL remains monotonic and is therefore not appropriate in many contexts. Our first important result is an impossibility theorem showing that a set of proposed postulates that at first all seem appropriate for a notion of entailment with regard to typicality cannot be satisfied simultaneously. Closer inspection reveals that this result is best interpreted as an argument for advocating the development of more than one type of PTL entailment. In the spirit of this interpretation, we investigate three different (semantic) versions of entailment for PTL, each one based on the definition of rational closure as introduced by Lehmann and Magidor for KLM-style conditionals, and constructed using different notions of minimality.
- Representation learning with extreme learning machines and empirical mode
decomposition for wind speed forecasting methods- Abstract: Publication date: Available online 25 September 2019Source: Artificial IntelligenceAuthor(s): Hao-Fan Yang, Yi-Ping Phoebe Chen Time series analysis has become more accurate with the emergence of powerful modelling methods based on machine learning development. Prediction models use historical time series to predict future conditions that occur over periods of time. However, most of these models are shallow models, only containing a small number of non-linear operations and without the ability or the capacity to extract underlying features from complex time series accurately. Moreover, deep learning approaches outperform statistical and computational approaches if a large amount of data and/or hidden layers are involved in the development of a forecasting model, but they are criticized for their relatively slow learning speeds. Therefore, this research proposes a hybrid model, which is hybridized by empirical mode decomposition, stacked auto-encoders, and extreme learning machines, aiming to forecast wind speed accurately and efficiently. The evaluation is undertaken by conducting extensive experiments using real-world data. The results show that the proposed E-S-ELM can accurately and efficiently forecast wind speed, and the effectiveness of the shared-hidden-layer approach for deep networks is also demonstrated.
- Abstract: Publication date: Available online 25 September 2019Source: Artificial IntelligenceAuthor(s): Hao-Fan Yang, Yi-Ping Phoebe Chen Time series analysis has become more accurate with the emergence of powerful modelling methods based on machine learning development. Prediction models use historical time series to predict future conditions that occur over periods of time. However, most of these models are shallow models, only containing a small number of non-linear operations and without the ability or the capacity to extract underlying features from complex time series accurately. Moreover, deep learning approaches outperform statistical and computational approaches if a large amount of data and/or hidden layers are involved in the development of a forecasting model, but they are criticized for their relatively slow learning speeds. Therefore, this research proposes a hybrid model, which is hybridized by empirical mode decomposition, stacked auto-encoders, and extreme learning machines, aiming to forecast wind speed accurately and efficiently. The evaluation is undertaken by conducting extensive experiments using real-world data. The results show that the proposed E-S-ELM can accurately and efficiently forecast wind speed, and the effectiveness of the shared-hidden-layer approach for deep networks is also demonstrated.
- From Iterated Revision to Iterated Contraction: Extending the Harper
Identity- Abstract: Publication date: Available online 20 September 2019Source: Artificial IntelligenceAuthor(s): Richard Booth, Jake Chandler The study of iterated belief change has principally focused on revision, with the other main operator of AGM belief change theory, namely contraction, receiving comparatively little attention. In this paper we show how principles of iterated revision can be carried over to iterated contraction by generalising a principle known as the ‘Harper Identity’. The Harper Identity provides a recipe for defining the belief set resulting from contraction by a sentence A in terms of (i) the initial belief set and (ii) the belief set resulting from revision by ¬A. Here, we look at ways to similarly define the conditional belief set resulting from contraction by A. After noting that the most straightforward proposal of this kind leads to triviality, we characterise a promising family of alternative suggestions that avoid such a result. One member of that family, which involves the operation of rational closure, is noted to be particularly theoretically fruitful and normatively appealing.
- Abstract: Publication date: Available online 20 September 2019Source: Artificial IntelligenceAuthor(s): Richard Booth, Jake Chandler The study of iterated belief change has principally focused on revision, with the other main operator of AGM belief change theory, namely contraction, receiving comparatively little attention. In this paper we show how principles of iterated revision can be carried over to iterated contraction by generalising a principle known as the ‘Harper Identity’. The Harper Identity provides a recipe for defining the belief set resulting from contraction by a sentence A in terms of (i) the initial belief set and (ii) the belief set resulting from revision by ¬A. Here, we look at ways to similarly define the conditional belief set resulting from contraction by A. After noting that the most straightforward proposal of this kind leads to triviality, we characterise a promising family of alternative suggestions that avoid such a result. One member of that family, which involves the operation of rational closure, is noted to be particularly theoretically fruitful and normatively appealing.
- A general framework for reordering agents asynchronously in distributed
CSPs- Abstract: Publication date: Available online 20 September 2019Source: Artificial IntelligenceAuthor(s): Younes Mechqrane, Mohamed Wahbi, Christian Bessiere, Kenneth N. Brown Distributed constraint satisfaction problems (DisCSPs) can express decision problems where physically distributed agents control different decision variables, but must coordinate with each other to agree on a global solution. Asynchronous Backtracking (ABT) is a pivotal search procedure for DisCSPs. ABT requires a static total ordering on the agents. However, reordering agents during search is an essential component for efficiently solving a DisCSP. All polynomial space algorithms proposed so far to improve ABT by reordering agents during search only allow a limited amount of reordering. In this paper, we propose AgileABT, a general framework for reordering agents asynchronously that is able to change the ordering of all agents. This is done via the original notion of termination value, a label attached to the orders exchanged by agents during search. We prove that AgileABT is sound and complete. We show that, thanks to termination values, our framework allows us to implement the main variable ordering heuristics from centralized CSPs, which until now could not be applied to the distributed setting. We prove that AgileABT terminates and has a polynomial space complexity in all these cases. Our empirical study shows the significance of our framework compared to state-of-the-art asynchronous dynamic ordering algorithms for solving distributed CSP.
- Abstract: Publication date: Available online 20 September 2019Source: Artificial IntelligenceAuthor(s): Younes Mechqrane, Mohamed Wahbi, Christian Bessiere, Kenneth N. Brown Distributed constraint satisfaction problems (DisCSPs) can express decision problems where physically distributed agents control different decision variables, but must coordinate with each other to agree on a global solution. Asynchronous Backtracking (ABT) is a pivotal search procedure for DisCSPs. ABT requires a static total ordering on the agents. However, reordering agents during search is an essential component for efficiently solving a DisCSP. All polynomial space algorithms proposed so far to improve ABT by reordering agents during search only allow a limited amount of reordering. In this paper, we propose AgileABT, a general framework for reordering agents asynchronously that is able to change the ordering of all agents. This is done via the original notion of termination value, a label attached to the orders exchanged by agents during search. We prove that AgileABT is sound and complete. We show that, thanks to termination values, our framework allows us to implement the main variable ordering heuristics from centralized CSPs, which until now could not be applied to the distributed setting. We prove that AgileABT terminates and has a polynomial space complexity in all these cases. Our empirical study shows the significance of our framework compared to state-of-the-art asynchronous dynamic ordering algorithms for solving distributed CSP.
- Proving semantic properties as first-order satisfiability
- Abstract: Publication date: Available online 20 September 2019Source: Artificial IntelligenceAuthor(s): Salvador Lucas The semantics of computational systems (e.g., relational and knowledge data bases, query-answering systems, programming languages, etc.) can often be expressed as (the specification of) a logical theory Th. Queries, goals, and claims about the behavior or features of the system can be expressed as formulas φ which should be checked with respect to the intended model of Th, which is often huge or even incomputable. In this paper we show how to prove such semantic properties φ of Th by just finding a model A of Th∪{φ}∪Zφ, where Zφ is an appropriate (possibly empty) theory depending on φ only. Applications to relational and deductive databases, rewriting-based systems, logic programming, and answer set programming are discussed.
- Abstract: Publication date: Available online 20 September 2019Source: Artificial IntelligenceAuthor(s): Salvador Lucas The semantics of computational systems (e.g., relational and knowledge data bases, query-answering systems, programming languages, etc.) can often be expressed as (the specification of) a logical theory Th. Queries, goals, and claims about the behavior or features of the system can be expressed as formulas φ which should be checked with respect to the intended model of Th, which is often huge or even incomputable. In this paper we show how to prove such semantic properties φ of Th by just finding a model A of Th∪{φ}∪Zφ, where Zφ is an appropriate (possibly empty) theory depending on φ only. Applications to relational and deductive databases, rewriting-based systems, logic programming, and answer set programming are discussed.
- The Book of Why.
- Abstract: Publication date: Available online 20 September 2019Source: Artificial IntelligenceAuthor(s): Joseph Y. Halpern
- Abstract: Publication date: Available online 20 September 2019Source: Artificial IntelligenceAuthor(s): Joseph Y. Halpern
- Job sequencing with one common and multiple secondary resources: An
A⁎/Beam search based anytime algorithm- Abstract: Publication date: Available online 12 September 2019Source: Artificial IntelligenceAuthor(s): Matthias Horn, Günther Raidl, Christian Blum We consider a sequencing problem that arises, for example, in the context of scheduling patients in particle therapy facilities for cancer treatment. A set of non-preemptive jobs needs to be scheduled, where each job requires two resources: (1) a common resource that is shared by all jobs and (2) a secondary resource, which is shared with only a subset of the other jobs. While the common resource is only required for a part of the job's processing time, the secondary resource is required for the whole duration. The objective is to minimize the makespan. First we show that the tackled problem is NP-hard and provide three different lower bounds for the makespan. These lower bounds are then exploited in a greedy construction heuristic and a novel exact anytime A⁎ algorithm, which uses an advanced diving mechanism based on Beam Search and Local Search to find good heuristic solutions early. For comparison we also provide a basic Constraint Programming model solved with the ILOG CP optimizer. An extensive experimental evaluation on two types of problem instances shows that the approach works even for large instances with up to 2000 jobs extremely well. It typically yields either optimal solutions or solutions with an optimality gap of less than 1%.
- Abstract: Publication date: Available online 12 September 2019Source: Artificial IntelligenceAuthor(s): Matthias Horn, Günther Raidl, Christian Blum We consider a sequencing problem that arises, for example, in the context of scheduling patients in particle therapy facilities for cancer treatment. A set of non-preemptive jobs needs to be scheduled, where each job requires two resources: (1) a common resource that is shared by all jobs and (2) a secondary resource, which is shared with only a subset of the other jobs. While the common resource is only required for a part of the job's processing time, the secondary resource is required for the whole duration. The objective is to minimize the makespan. First we show that the tackled problem is NP-hard and provide three different lower bounds for the makespan. These lower bounds are then exploited in a greedy construction heuristic and a novel exact anytime A⁎ algorithm, which uses an advanced diving mechanism based on Beam Search and Local Search to find good heuristic solutions early. For comparison we also provide a basic Constraint Programming model solved with the ILOG CP optimizer. An extensive experimental evaluation on two types of problem instances shows that the approach works even for large instances with up to 2000 jobs extremely well. It typically yields either optimal solutions or solutions with an optimality gap of less than 1%.
- Approximate verification of strategic abilities under imperfect
information- Abstract: Publication date: Available online 11 September 2019Source: Artificial IntelligenceAuthor(s): Wojciech Jamroga, Michał Knapik, Damian Kurpiewski, Łukasz Mikulski Model checking of strategic ability under imperfect information is known to be hard. The complexity results range from NP-completeness to undecidability, depending on the precise setup of the problem. No less importantly, the usual fixpoint equivalences do not hold for imperfect information strategies, which seriously hampers incremental synthesis of winning strategies. In this paper, we propose translations of ATLir formulae that provide lower and upper bounds for their truth values, and are cheaper to verify than the original specifications. Most interestingly, the lower approximation is provided by a fixpoint expression that uses a nonstandard variant of the next-step ability operator. We show the correctness of the translations, establish their computational complexity, and validate the approach by experiments with several benchmarks, including a scalable scenario of Bridge play. We also demonstrate that the approximations leave much room for optimizations; in particular, optimizing the data structures can produce a significant speedup. Finally, we show that our fixpoint approximations of ATLir formulae can be combined with under- and overapproximations of models in the vein of may/must abstractions, providing very promising experimental results.
- Abstract: Publication date: Available online 11 September 2019Source: Artificial IntelligenceAuthor(s): Wojciech Jamroga, Michał Knapik, Damian Kurpiewski, Łukasz Mikulski Model checking of strategic ability under imperfect information is known to be hard. The complexity results range from NP-completeness to undecidability, depending on the precise setup of the problem. No less importantly, the usual fixpoint equivalences do not hold for imperfect information strategies, which seriously hampers incremental synthesis of winning strategies. In this paper, we propose translations of ATLir formulae that provide lower and upper bounds for their truth values, and are cheaper to verify than the original specifications. Most interestingly, the lower approximation is provided by a fixpoint expression that uses a nonstandard variant of the next-step ability operator. We show the correctness of the translations, establish their computational complexity, and validate the approach by experiments with several benchmarks, including a scalable scenario of Bridge play. We also demonstrate that the approximations leave much room for optimizations; in particular, optimizing the data structures can produce a significant speedup. Finally, we show that our fixpoint approximations of ATLir formulae can be combined with under- and overapproximations of models in the vein of may/must abstractions, providing very promising experimental results.
- Natural Strategic Ability
- Abstract: Publication date: Available online 4 September 2019Source: Artificial IntelligenceAuthor(s): Wojciech Jamroga, Vadim Malvone, Aniello Murano In game theory, as well as in the semantics of game logics, a strategy can be represented by any function from states of the game to the agent's actions. That makes sense from the mathematical point of view, but not necessarily in the context of human behavior. This is because humans are quite bad at executing complex plans, and rather unlikely to come up with such plans in the first place. A similar concern applies to artificial agents with limited memory and/or computational power. In this paper, we adopt the view of bounded rationality, and look at “simple” strategies in specification of agents' abilities. We formally define what “simple” means, and propose a variant of alternating-time temporal logic that takes only such strategies into account. We also study the model checking problem for the resulting semantics of ability.After that, we turn to the broader issue of natural strategic abilities in concurrent games with LTL-definable winning conditions, and study a number of decision problems based on surely winning and Nash equilibrium. We show that, by adopting the view of bounded rationality based on natural strategies, we significantly decrease the complexity of rational verification for multi-agent systems.
- Abstract: Publication date: Available online 4 September 2019Source: Artificial IntelligenceAuthor(s): Wojciech Jamroga, Vadim Malvone, Aniello Murano In game theory, as well as in the semantics of game logics, a strategy can be represented by any function from states of the game to the agent's actions. That makes sense from the mathematical point of view, but not necessarily in the context of human behavior. This is because humans are quite bad at executing complex plans, and rather unlikely to come up with such plans in the first place. A similar concern applies to artificial agents with limited memory and/or computational power. In this paper, we adopt the view of bounded rationality, and look at “simple” strategies in specification of agents' abilities. We formally define what “simple” means, and propose a variant of alternating-time temporal logic that takes only such strategies into account. We also study the model checking problem for the resulting semantics of ability.After that, we turn to the broader issue of natural strategic abilities in concurrent games with LTL-definable winning conditions, and study a number of decision problems based on surely winning and Nash equilibrium. We show that, by adopting the view of bounded rationality based on natural strategies, we significantly decrease the complexity of rational verification for multi-agent systems.
- Exploiting Reverse Target-Side Contexts for Neural Machine Translation via
Asynchronous Bidirectional Decoding- Abstract: Publication date: Available online 4 September 2019Source: Artificial IntelligenceAuthor(s): Jinsong Su, Xiangwen Zhang, Qian Lin, Yue Qin, Junfeng Yao, Yang Liu Based on a unified encoder-decoder framework with attentional mechanism, neural machine translation (NMT) models have attracted much attention and become the mainstream in the community of machine translation. Generally, the NMT decoders produce translation in a left-to-right way. As a result, only left-to-right target-side contexts from the generated translations are exploited, while the right-to-left target-side contexts are completely unexploited for translation. In this paper, we extend the conventional attentional encoder-decoder NMT framework by introducing a backward decoder, in order to explore asynchronous bidirectional decoding for NMT. In the first step after encoding, our backward decoder learns to generate the target-side hidden states in a right-to-left manner. Next, in each timestep of translation prediction, our forward decoder concurrently considers both the source-side and the reverse target-side hidden states via two attention models. Compared with previous models, the innovation in this architecture enables our model to fully exploit contexts from both source side and target side, which improve translation quality altogether. We conducted experiments on NIST Chinese-English, WMT English-German and Finnish-English translation tasks to investigate the effectiveness of our model. Experimental results show that (1) our improved RNN-based NMT model achieves significant improvements over the conventional RNNSearch by 1.44/-3.02, 1.11/-1.01, and 1.23/-1.27 average BLEU and TER points, respectively; and (2) our enhanced Transformer outperforms the standard Transformer by 1.56/-1.49, 1.76/-2.49, and 1.29/-1.33 average BLEU and TER points, respectively. We released our code at https://github.com/DeepLearnXMU/ABD-NMT.
- Abstract: Publication date: Available online 4 September 2019Source: Artificial IntelligenceAuthor(s): Jinsong Su, Xiangwen Zhang, Qian Lin, Yue Qin, Junfeng Yao, Yang Liu Based on a unified encoder-decoder framework with attentional mechanism, neural machine translation (NMT) models have attracted much attention and become the mainstream in the community of machine translation. Generally, the NMT decoders produce translation in a left-to-right way. As a result, only left-to-right target-side contexts from the generated translations are exploited, while the right-to-left target-side contexts are completely unexploited for translation. In this paper, we extend the conventional attentional encoder-decoder NMT framework by introducing a backward decoder, in order to explore asynchronous bidirectional decoding for NMT. In the first step after encoding, our backward decoder learns to generate the target-side hidden states in a right-to-left manner. Next, in each timestep of translation prediction, our forward decoder concurrently considers both the source-side and the reverse target-side hidden states via two attention models. Compared with previous models, the innovation in this architecture enables our model to fully exploit contexts from both source side and target side, which improve translation quality altogether. We conducted experiments on NIST Chinese-English, WMT English-German and Finnish-English translation tasks to investigate the effectiveness of our model. Experimental results show that (1) our improved RNN-based NMT model achieves significant improvements over the conventional RNNSearch by 1.44/-3.02, 1.11/-1.01, and 1.23/-1.27 average BLEU and TER points, respectively; and (2) our enhanced Transformer outperforms the standard Transformer by 1.56/-1.49, 1.76/-2.49, and 1.29/-1.33 average BLEU and TER points, respectively. We released our code at https://github.com/DeepLearnXMU/ABD-NMT.
- Democratic Fair Allocation of Indivisible Goods
- Abstract: Publication date: Available online 3 September 2019Source: Artificial IntelligenceAuthor(s): Erel Segal-Halevi, Warut Suksompong We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused on unanimous fairness, in which all agents in each group must agree that their group's share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. For two groups with arbitrary monotonic valuations, we give an efficient protocol that guarantees envy-freeness up to one good for at least 1/2 of the agents in each group, and prove that the 1/2 fraction is optimal. We also present other protocols that make weaker fairness guarantees to more agents in each group, or to more groups. Our protocols combine techniques from different fields, including combinatorial game theory, cake cutting, and voting.
- Abstract: Publication date: Available online 3 September 2019Source: Artificial IntelligenceAuthor(s): Erel Segal-Halevi, Warut Suksompong We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused on unanimous fairness, in which all agents in each group must agree that their group's share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. For two groups with arbitrary monotonic valuations, we give an efficient protocol that guarantees envy-freeness up to one good for at least 1/2 of the agents in each group, and prove that the 1/2 fraction is optimal. We also present other protocols that make weaker fairness guarantees to more agents in each group, or to more groups. Our protocols combine techniques from different fields, including combinatorial game theory, cake cutting, and voting.
- Optimal cruiser-drone traffic enforcement under energy limitation
- Abstract: Publication date: Available online 2 September 2019Source: Artificial IntelligenceAuthor(s): Ariel Rosenfeld, Oleg Maksimov Drones can assist in mitigating traffic accidents by deterring reckless drivers, leveraging their flexible mobility. In the real-world, drones are fundamentally limited by their battery/fuel capacity and have to be replenished during long operations. In this article, we propose a novel approach where police cruisers act as mobile replenishment providers in addition to their traffic enforcement duties. We propose a binary integer linear program for determining the optimal rendezvous cruiser-drone enforcement policy, which guarantees that all drones are replenished on time and minimizes the likelihood of accidents. In an extensive empirical evaluation, we first show that human drivers are expected to react to traffic enforcement drones similar to how they react to police cruisers, using a first-of-its-kind human study in realistic simulated driving. Then, we show that our proposed approach significantly outperforms the common practice of constructing stationary replenishment installations using both synthetic and real-world road networks. Finally, we propose and evaluate a novel optimization speedup method for mitigating the increased runtime of our proposed approach.
- Abstract: Publication date: Available online 2 September 2019Source: Artificial IntelligenceAuthor(s): Ariel Rosenfeld, Oleg Maksimov Drones can assist in mitigating traffic accidents by deterring reckless drivers, leveraging their flexible mobility. In the real-world, drones are fundamentally limited by their battery/fuel capacity and have to be replenished during long operations. In this article, we propose a novel approach where police cruisers act as mobile replenishment providers in addition to their traffic enforcement duties. We propose a binary integer linear program for determining the optimal rendezvous cruiser-drone enforcement policy, which guarantees that all drones are replenished on time and minimizes the likelihood of accidents. In an extensive empirical evaluation, we first show that human drivers are expected to react to traffic enforcement drones similar to how they react to police cruisers, using a first-of-its-kind human study in realistic simulated driving. Then, we show that our proposed approach significantly outperforms the common practice of constructing stationary replenishment installations using both synthetic and real-world road networks. Finally, we propose and evaluate a novel optimization speedup method for mitigating the increased runtime of our proposed approach.
- Coevolutionary systems and PageRank
- Abstract: Publication date: Available online 30 August 2019Source: Artificial IntelligenceAuthor(s): S.Y. Chong, P. Tiňo, J. He Coevolutionary systems have been used successfully in various problem domains involving situations of strategic decision-making. Central to these systems is a mechanism whereby finite populations of agents compete for reproduction and adapt in response to their interaction outcomes. In competitive settings, agents choose which solutions to implement and outcomes from their behavioral interactions express preferences between the solutions. Recently, we have introduced a framework that provides both qualitative and quantitative characterizations of competitive coevolutionary systems. Its two main features are: (1) A directed graph (digraph) representation that fully captures the underlying structure arising from pairwise preferences over solutions. (2) Coevolutionary processes are modelled as random walks on the digraph. However, one needs to obtain prior, qualitative knowledge of the underlying structures of these coevolutionary digraphs to perform quantitative characterizations on coevolutionary systems and interpret the results. Here, we study a deep connection between coevolutionary systems and PageRank to address this issue. We develop a principled approach to measure and rank the performance (importance) of solutions (vertices) in a given coevolutionary digraph. In PageRank formalism, B transfers part of its authority to A if A dominates B (there is an arc from B to A in the digraph). In this manner, PageRank authority indicates the importance of a vertex. PageRank authorities with suitable normalization have a natural interpretation of long-term visitation probabilities over the digraph by the coevolutionary random walk. We derive closed-form expressions to calculate PageRank authorities for any coevolutionary digraph. We can precisely quantify changes to the authorities due to modifications in restart probability for any coevolutionary system. Our empirical studies demonstrate how PageRank authorities characterize coevolutionary digraphs with different underlying structures.
- Abstract: Publication date: Available online 30 August 2019Source: Artificial IntelligenceAuthor(s): S.Y. Chong, P. Tiňo, J. He Coevolutionary systems have been used successfully in various problem domains involving situations of strategic decision-making. Central to these systems is a mechanism whereby finite populations of agents compete for reproduction and adapt in response to their interaction outcomes. In competitive settings, agents choose which solutions to implement and outcomes from their behavioral interactions express preferences between the solutions. Recently, we have introduced a framework that provides both qualitative and quantitative characterizations of competitive coevolutionary systems. Its two main features are: (1) A directed graph (digraph) representation that fully captures the underlying structure arising from pairwise preferences over solutions. (2) Coevolutionary processes are modelled as random walks on the digraph. However, one needs to obtain prior, qualitative knowledge of the underlying structures of these coevolutionary digraphs to perform quantitative characterizations on coevolutionary systems and interpret the results. Here, we study a deep connection between coevolutionary systems and PageRank to address this issue. We develop a principled approach to measure and rank the performance (importance) of solutions (vertices) in a given coevolutionary digraph. In PageRank formalism, B transfers part of its authority to A if A dominates B (there is an arc from B to A in the digraph). In this manner, PageRank authority indicates the importance of a vertex. PageRank authorities with suitable normalization have a natural interpretation of long-term visitation probabilities over the digraph by the coevolutionary random walk. We derive closed-form expressions to calculate PageRank authorities for any coevolutionary digraph. We can precisely quantify changes to the authorities due to modifications in restart probability for any coevolutionary system. Our empirical studies demonstrate how PageRank authorities characterize coevolutionary digraphs with different underlying structures.
- Determining Inference Semantics for Disjunctive Logic Programs
- Abstract: Publication date: Available online 23 August 2019Source: Artificial IntelligenceAuthor(s): Yi-Dong Shen, Thomas Eiter In a seminal paper, Gelfond and Lifschitz (New Generation Computing 9, 365–385, 1991) introduced simple disjunctive logic programs, where in rule heads the disjunction operator “ ” is used to express incomplete information, and defined the answer set semantics (called GL-semantics for short) based on a program transformation (called GL-reduct) and the minimal model requirement. Our observations reveal that the requirement of the GL-semantics, i.e., an answer set should be a minimal model of rules of the GL-reduct, may sometimes be too strong a condition and exclude some answer sets that would be reasonably acceptable. To address this, we present an alternative, more permissive answer set semantics, called the determining inference (DI) semantics. Specifically, we introduce a head selection function to formalize the operator and define answer sets as follows: (i) Given an interpretation I and a selection function sel, we transform a disjunctive program Π into a normal program ΠselI, called a disjunctive program reduct; (ii) given a base answer set semantics X for normal programs, we define I to be a candidate answer set of Π w.r.t. X if I is an answer set of ΠselI under X; and (iii) we define I to be an answer set of Π w.r.t. X if I is a minimal candidate answer set. The DI-semantics is general and applicable to extend any answer set semantics X for normal programs to disjunctive programs. By replacing X with the GLnlp-semantics defined by Gelfond and Lifschitz (1988), we induce a DI-semantics for simple disjunctive programs, and by replacing X with the well-justified semantics defined by Shen et al. (2014), we further induce a DI-semantics for general disjunctive programs. We also establish a novel characterization of the GL-semantics in terms of a disjunctive program reduct, which reveals the essential difference of the DI-semantics from the GL-semantics and leads us to giving a satisfactory solution to the open problem presented by Hitzler and Seda (1999) about characterizing split normal derivatives of a simple disjunctive program Π such that answer sets of the normal derivatives are answer sets of Π under the GL-semantics. Finally we give computational complexity results; in particular we show that in the propositional case deciding whether a simple disjunctive program Π has some DI-answer set is NP-complete. This is in contrast to the GL-semantics and equivalent formulations such as the FLP-semantics (Faber et al., 2011), where deciding whether Π has some answer set is Σ2p-complete, while brave and cautious reasoning are Σ2p- and Π2p-complete, respectively, for both GL- and DI-answer sets. For general disjunctive programs with compound formulas as building blocks, the complexity of brave and cautious reasoning increases under DI-semantics by one level of the polynomial hierarchy, which thus offers higher problem solving capacity.
- Abstract: Publication date: Available online 23 August 2019Source: Artificial IntelligenceAuthor(s): Yi-Dong Shen, Thomas Eiter In a seminal paper, Gelfond and Lifschitz (New Generation Computing 9, 365–385, 1991) introduced simple disjunctive logic programs, where in rule heads the disjunction operator “ ” is used to express incomplete information, and defined the answer set semantics (called GL-semantics for short) based on a program transformation (called GL-reduct) and the minimal model requirement. Our observations reveal that the requirement of the GL-semantics, i.e., an answer set should be a minimal model of rules of the GL-reduct, may sometimes be too strong a condition and exclude some answer sets that would be reasonably acceptable. To address this, we present an alternative, more permissive answer set semantics, called the determining inference (DI) semantics. Specifically, we introduce a head selection function to formalize the operator and define answer sets as follows: (i) Given an interpretation I and a selection function sel, we transform a disjunctive program Π into a normal program ΠselI, called a disjunctive program reduct; (ii) given a base answer set semantics X for normal programs, we define I to be a candidate answer set of Π w.r.t. X if I is an answer set of ΠselI under X; and (iii) we define I to be an answer set of Π w.r.t. X if I is a minimal candidate answer set. The DI-semantics is general and applicable to extend any answer set semantics X for normal programs to disjunctive programs. By replacing X with the GLnlp-semantics defined by Gelfond and Lifschitz (1988), we induce a DI-semantics for simple disjunctive programs, and by replacing X with the well-justified semantics defined by Shen et al. (2014), we further induce a DI-semantics for general disjunctive programs. We also establish a novel characterization of the GL-semantics in terms of a disjunctive program reduct, which reveals the essential difference of the DI-semantics from the GL-semantics and leads us to giving a satisfactory solution to the open problem presented by Hitzler and Seda (1999) about characterizing split normal derivatives of a simple disjunctive program Π such that answer sets of the normal derivatives are answer sets of Π under the GL-semantics. Finally we give computational complexity results; in particular we show that in the propositional case deciding whether a simple disjunctive program Π has some DI-answer set is NP-complete. This is in contrast to the GL-semantics and equivalent formulations such as the FLP-semantics (Faber et al., 2011), where deciding whether Π has some answer set is Σ2p-complete, while brave and cautious reasoning are Σ2p- and Π2p-complete, respectively, for both GL- and DI-answer sets. For general disjunctive programs with compound formulas as building blocks, the complexity of brave and cautious reasoning increases under DI-semantics by one level of the polynomial hierarchy, which thus offers higher problem solving capacity.