In this paper we propose a new algorithm for solving general two-player turn-taking games that performs symbolic search utilizing binary decision diagrams (BDDs). It consists of two stages: First, it determines all breadth-first search (BFS) layers using forward search and omitting duplicate detection, next, the solving process operates in backward direction only within these BFS layers thereby partitioning all BDDs according to the layers the states reside in. We provide experimental results for selected games and compare to a previous approach. This comparison shows that in most cases the new algorithm outperforms the existing one in terms of runtime and used memory so that it can solve games that could not be solved before with a general approach.
One of the most essential parts of any recommender system is personalization how acceptable the recommendations are from the user's perspective. However, in many real-world applications, there are multiple objectives often from multiple stakeholders that need to be incorporated into the recommendation generation. In this work, we define the problem of multi-stakeholder recommendation and we focus on finding algorithms for a special case where the recommender system itself is also a stakeholder. We also define different types of system-level objectives and find algorithmic solutions for each of them such that similar problems can be solved by the same class of algorithms. Finally, we will explore the idea of incremental incorporation of system-level objectives into recommender systems to tackle the existing problems with the optimization techniques which only look for optimizing the individual users' lists rather than looking at the whole picture of system performance over time. With autonomous robots being exposed to unstructured environments, they inevitably run across cases in which they stand unable to overcome their limitations, such as removing objects in their path, or location uncertainty. These limitations can be overcome when robots obtain help from humans. We are investigating how robots can effectively interact and request help from human. We test a scenario where the robot needs a door to be opened by a human, so the robot could complete its other tasks. The robot is too short to reach the door handle himself. In the polite request, the robot may say "Can you open the door please?", while in the indirect request, the robot may say "I cannot open the door and it is blocking my way". In the friendly way, the robot asks with less formal tones like "You seem taller than me. Would you open the door for me?". The robot can point its hand to the door that it needs opened. Later humans were interviewed as to why they did or did not take the robot seriously. The polite interaction manner was significantly more efficient. We show how to factor the situational awareness effects (whether participants realize the nature of the experiment) in the analysis. The proposed evaluation procedure allows identifying promising mechanisms for such human-robot interactions.
Deep convolutional sum-product networks (DCSPNs) have very recently been introduced and shown to yield state-of-the-art results in image completion tasks. A DCSPN consists of a tree structure (a directed acyclic graph) coupled with parameters of the structure. Given that DCSPNs are in their infancy, many open questions remain regarding the properties and topology of its tree structure. In this paper, we undertake three investigations pertaining to the DCSPN structure. The first two studies revolve around the original structure put forth in the seminal paper. These studies increase the number of pooling layers and vary the hyperparameters in attempts to improve accuracy. The third inquiry suggests a new DCSPN tree structure that significantly lowers the training time at some modest expense of accuracy.
The principle of maximum entropy (MaxEnt) provides a well-founded methodology for commonsense reasoning based on probabilistic conditional knowledge. We show how to calculate MaxEnt distributions in a first-order setting by using typed model counting and condensed iterative scaling. Further, we discuss the connection to Markov Logic Networks for drawing inferences.
In this work is proposed a method for Hierarchical Classification, which takes advantage of the hierarchical structure to influence the prediction of local classifiers with their neighbors. To achieve this, two strategies are combined. The first is to represent the hierarchical structure as a Bayesian network, and the second is to build chained classifiers that feed the Bayesian network as local classifiers. The proposed method was tested in several datasets of functional genomics, which consist of tree-structured hierarchies. The results of several variants of the proposed method are compared to the standard methods, Flat and Top-Down, as well as with a start of the art technique, showing superior performance under several metrics.
This paper proposes a highly efficient exact dynamic programming algorithm for computing all the conditionals generated from consonant belief functions. The time and space complexities of this novel algorithm are linear for computing all the conditional beliefs, and hence it significantly outperforms the exponential time and space complexity requirements of the brute force approach and the currently available conditional computation strategies. We provide a thorough analysis and experimental validation of the utility, efficiency, and implementation of the proposed algorithm for carrying out the Fagin-Halpern conditional. A new computational library is developed and harnessed in the simulations.
Laaziz, Safia (Université des Sciences et Technologie Houari Boumediene) | Zeboudj, Younes (Université des Sciences et Technologie Houari Boumediene) | Benferhat, Salem (Université des Sciences et Technologie Houari Boumediene) | Haned, Faiza (Université des Sciences et Technologie Houari Boumediene)
Belief revision consists in modifying an epistemic state in the light of a new information. In this paper, we focus on the so-called multiple iterated belief revision process called C-revision. Epistemic states are represented in terms of Ordinal Conditional Functions OCF and penalty knowledge bases. The input is a set of consistent weighted formulas. We show that C-revision, defined at a semantic level using OCF, has a very natural counterpart in penalty logic.
Forgetting as a knowledge management operation has received much less attention than operations like inference, or revision. It was mainly in the area of logic programming that techniques and axiomatic properties have been studied systematically. However, at least from a cognitive view, forgetting plays an important role in restructuring and reorganizing a human's mind, and it is closely related to notions like relevance and independence which are crucial to knowledge representation and reasoning. In this paper, we propose axiomatic properties of (intentional) forgetting for general epistemic frameworks which are inspired by those for logic programming, and we evaluate various forgetting operations which have been proposed recently by Beierle et al. according to them. The general aim of this paper is to advance formal studies of (intentional) forgetting operators while capturing the many facets of forgetting in a unifying framework in which different forgetting operators can be contrasted and distinguished by means of formal properties.