Intelligenza Artificiale - Volume 12, issue 2

Authors: Filice, Simone | Moschitti, Alessandro

Article Type: Research Article

Abstract: In recent years, forums offering community Question Answering (cQA) services gained popularity on the web, as they offer a new opportunity for users to search and share knowledge. In fact, forums allow users to freely ask questions and expect answers from the community. Although the idea of receiving a direct, targeted response from other users is very attractive, it is not rare to see long threads of comments, where only a small portion of them are actually valid answers. In many cases users start conversations, ask for other information, and discuss about things, which are not central to the original …topic. Therefore, finding the desired information in a long list of answers might be very time-consuming. Designing automatic systems to select good answers is not an easy task. In many cases the question and the answer do not share a large textual content, and approaches based on measuring the question-answer similarity will often fail. A more intriguing and promising approach would be trying to define valid question-answer templates and use a system to understand whether any of these templates is satisfied for a given question-answer pair. Unfortunately, the manual definition of these templates is extremely complex and requires a domain-expert. In this paper, we propose a supervised kernel-based framework that automatically learns from training question-answer pairs the syntactic/semantic patterns useful to recognize good answers. We carry out a detailed experimental evaluation, where we demonstrate that the proposed framework achieves state-of-the-art results on the Qatar Living datasets released in three different editions of the Community Question Answering Challenge of SemEval. Show more

Keywords: Community Question Answering, Kernel methods, Structured Language Learning

DOI: 10.3233/IA-170034

Citation: Intelligenza Artificiale, vol. 12, no. 2, pp. 49-65, 2018

Authors: Fioretto, Ferdinando | Dovier, Agostino | Pontelli, Enrico

Article Type: Research Article

Abstract: Distributed Constraint Optimization Problems (DCOPs) have emerged as one of the prominent multi-agent architectures to govern the agents’ autonomous behavior in a cooperative multi-agent system (MAS) where several agents coordinate with each other to optimize a global cost function taking into account their local preferences. They represent a powerful approach to the description and resolution of many practical problems. However, typical MAS applications are characterized by complex dynamics and interactions among a large number of entities, which translate into hard combinatorial problems, posing significant challenges from a computational and coordination standpoints. This paper reviews two methods to promote …a hierarchical parallel model for solving DCOPs, with the aim of improving the performance of the DCOP algorithm. The first is a Multi-Variable Agent (MVA) DCOP decomposition, which exploits co-locality of an agent’s variables allowing the adoption of efficient centralized techniques to solve the subproblem of an agent. The second is the use of Graphics Processing Units (GPUs) to speed up a class of DCOP algorithms. Finally, exploiting these hierarchical parallel model, the paper presents two critical applications of DCOPs for demand response (DR) program in smart grids. The Multi-agent Economic Dispatch with Demand Response (EDDR), which provides an integrated approach to the economic dispatch and the DR model for power systems, and the Smart Home Device Scheduling (SHDS) problem, that formalizes the device scheduling and coordination problem across multiple smart homes to reduce energy peaks. Show more

Keywords: DCOP, GPUs, smart grid, smart homes

DOI: 10.3233/IA-180037

Citation: Intelligenza Artificiale, vol. 12, no. 2, pp. 67-87, 2018

Authors: Celli, Andrea | Marchesi, Alberto

Article Type: Research Article

Abstract: In imperfect-information games, a common assumption is that players can perfectly model the strategic interaction and always maintain control over their decision points. We relax this assumption by introducing the notion of limited-control repeated games. In this setting, two players repeatedly play a zero-sum extensive-form game and, at each iteration, a player may lose control over portions of her game tree. Intuitively, this can be seen as the chance player hijacking the interaction and taking control of certain decision points. What subsequently happens is no longer controllable–or even known–by the original players. We introduce pruned fictitious play, a …variation of fictitious play that can be employed by the players to reach an equilibrium in limited-control repeated games. We motivate this technique with the notion of limited best response, which is the key step of the learning rule we employ. We provide a general result on the probabilistic guarantees of a limited best response with respect to the original game model. Then, we experimentally evaluate our technique and show that pruned fictitious play has good convergence properties. Show more

Keywords: Repeated games, equilibrium computation, fictitious play, multi-agent learning, imperfect information

DOI: 10.3233/IA-180006

Citation: Intelligenza Artificiale, vol. 12, no. 2, pp. 89-101, 2018

Authors: Ferilli, Stefano | Lisi, Francesca Alessandra

Article Type: Editorial

DOI: 10.3233/IA-181002

Citation: Intelligenza Artificiale, vol. 12, no. 2, pp. 105-107, 2018

Authors: Alviano, Mario | Dodaro, Carmine | Maratea, Marco

Article Type: Research Article

Abstract: The goal of the Nurse Scheduling Problem is to find an assignment of nurses to shifts according to specific requirements. Frequently, a computed schedule may become not usable because of sudden absences of some nurses. In this cases, Nurse Rescheduling amounts to the computation of a new schedule, which has to satisfy the original requirements and the new absences. Additionally, a good solution to the Nurse Rescheduling Problem must be as similar as possible to the original schedule, which practically means that the number of changes has to be minimized. This paper focuses on the requirements specified by an Italian …hospital, and recently addressed by an approach based on Answer Set Programming (ASP). Even if promising results have been obtained with ASP, the original encoding presents some intrinsic weaknesses, which are identified and eventually circumvented in this paper. The new encoding is designed by taking into account both intrinsic properties of Nurse Scheduling and internal details of ASP solvers, such as cardinality and weight constraint propagators. The performance gain of clingo and wasp is empirically verified on instances from ASP literature. As an additional contribution, the performance of clingo and wasp is compared to other declarative frameworks, namely SAT and ILP; the best performance is obtained by clingo running the new ASP encoding. The advanced ASP encodings are then extended to solve Nurse Rescheduling, and an empirical evaluation is conducted with clingo and wasp . Show more

DOI: 10.3233/IA-170030

Citation: Intelligenza Artificiale, vol. 12, no. 2, pp. 109-124, 2018

Authors: Basile, Pierpaolo | Greco, Claudio | Suglia, Alessandro | Semeraro, Giovanni

Article Type: Research Article

Abstract: In this paper, we propose a framework based on Hierarchical Reinforcement Learning for dialogue management in a Conversational Recommender System scenario. The framework splits the dialogue into more manageable tasks whose achievement corresponds to goals of the dialogue with the user. The framework consists of a meta-controller, which receives the user utterance and understands which goal should pursue, and a controller, which exploits a goal-specific representation to generate an answer composed by a sequence of tokens. The modules are trained using a two-stage strategy based on a preliminary Supervised Learning stage and a successive Reinforcement Learning …stage. Show more

Keywords: Conversational Recommender Systems, Deep Learning, Hierarchical Reinforcement Learning, Conversational Agents

DOI: 10.3233/IA-170031

Citation: Intelligenza Artificiale, vol. 12, no. 2, pp. 125-141, 2018

Authors: Di Mauro, Nicola | Esposito, Floriana | Ventola, Fabrizio Giuseppe | Vergari, Antonio

Article Type: Research Article

Abstract: Sum-Product Networks (SPNs) are recently introduced deep probabilistic models providing exact and tractable inference. SPNs have been successfully employed in several application domains, from computer vision to natural language processing, as accurate density estimators. However, learning their structure and parameters from high dimensional data poses a challenge in terms of time complexity. Classical SPNs structure learning algorithms work by repeating several times two high cost operations: determining independencies among random variables (RVs)–introducing product nodes–and finding sub-populations among samples–introducing sum nodes. Even one of the simplest greedy structure learner, LearnSPN , scales quadratically in the number of the variables to determine …RVs independencies. In this work, we investigate the trade-off between accuracy and efficiency when employing approximate but fast procedures to determine independencies among RVs. We introduce and evaluate sub-quadratic procedures based on a random subspace approach and leveraging entropy as a proxy criterion to split independent RVs. Experimental results on many benchmark datasets for density estimation show that LearnSPN -like structure learners, when equipped by our splitting procedures, provide reduced learning and/or inference times, generally containing the degradation of inference accuracy. Ultimately, we provide an empirical confirmation of a “no free lunch” when learning the structure of SPNs. Show more

Keywords: Machine learning, deep learning, structure learning, probabilistic models, density estimation, Sum-Product Networks

DOI: 10.3233/IA-170032

Citation: Intelligenza Artificiale, vol. 12, no. 2, pp. 143-159, 2018

Authors: Cornia, Marcella | Abati, Davide | Baraldi, Lorenzo | Palazzi, Andrea | Calderara, Simone | Cucchiara, Rita

Article Type: Research Article

Abstract: Estimating the focus of attention of a person looking at an image or a video is a crucial step which can enhance many vision-based inference mechanisms: image segmentation and annotation, video captioning, autonomous driving are some examples. The early stages of the attentive behavior are typically bottom-up; reproducing the same mechanism means to find the saliency embodied in the images, i.e. which parts of an image pop out of a visual scene. This process has been studied for decades both in neuroscience and in terms of computational models for reproducing the human cortical process. In the last few years, …early models have been replaced by deep learning architectures, that outperform any early approach compared against public datasets. In this paper, we discuss the effectiveness of convolutional neural networks (CNNs) models in saliency prediction. We present a set of Deep Learning architectures developed by us, which can combine both bottom-up cues and higher-level semantics, and extract spatio-temporal features by means of 3D convolutions to model task-driven attentive behaviors. We will show how these deep networks closely recall the early saliency models, although improved with the semantics learned from the human ground-truth. Eventually, we will present a use-case in which saliency prediction is used to improve the automatic description of images. Show more

Keywords: Saliency, Human Attention, Neuroscience, Vision, Deep Learning

DOI: 10.3233/IA-170033

Citation: Intelligenza Artificiale, vol. 12, no. 2, pp. 161-175, 2018

Authors: Bistarelli, Stefano | Giacomin, Massimiliano | Pazienza, Andrea

Article Type: Editorial

DOI: 10.3233/IA-181001

Citation: Intelligenza Artificiale, vol. 12, no. 2, pp. 179-180, 2018

Authors: Fazzinga, Bettina | Flesca, Sergio | Furfaro, Filippo

Article Type: Research Article

Abstract: Probabilistic abstract argumentation combines Dung’s abstract argumentation framework with probability theory in order to model uncertainty in argumentation. In this setting, we address the fundamental problem of computing the probability that an argument is credulously or skeptically acceptable according to a given semantics. Specifically, we focus on the most popular semantics (i.e., admissible , stable , semi-stable , complete , grounded , preferred , ideal , ideal-set ), and show that computing the probability that an argument is credulously or skeptically accepted is FP # P -complete independently from the adopted semantics, in the cases when computing it is not …trivial (i.e., when skeptical acceptance is assumed under the admissible and ideal-set semantics). Show more

Keywords: Acceptability, probabilistic abstract argumentation, complexity

DOI: 10.3233/IA-180041

Citation: Intelligenza Artificiale, vol. 12, no. 2, pp. 181-191, 2018