The pattern satisfiability is a fundamental problem for SPARQL. This paper provides a complete analysis of decidability/undecidability of satisfiability problems for SPARQL 1.1 patterns. A surprising result is the undecidability of satisfiability for SPARQL 1.1 patterns when only AND and MINUS are expressible. Also, it is shown that any fragment of SPARQL 1.1 without expressing both AND and MINUS is decidable. These results provide a guideline for future SPARQL query language design and implementation.

We investigate the relationship between conditional independence (CI) x ⊥  y | Z and the independence of two residuals x – E ( x | Z ) ⊥  –E ( y | Z ), where x and y are two random variables, and Z is a set of random variables. We show that if x, y and Z are generated by following linear structural equation model and all external influences follow Gaussian distributions, then x ⊥  y | Z if and only if x – E ( x | Z ) ⊥ y – E ( y | Z ). That is, the test of x ⊥  y | Z can be relaxed to a simpler unconditional independence test of x – E ( x | Z ) ⊥  y – E ( y | Z ). Furthermore, if all these external influences follow non-Gaussian distributions and the model satisfies structural faithfulness condition, then we have x ⊥  y | Z ⇔ x – E ( x | Z ) ⊥  y – E ( y | Z ). We apply the results above to the causal discovery problem, where the causal directions are generally determined by a set of V -structures and their consistent propagations, so CI test-based methods can return a set of Markov equivalence classes. We show that in linear non-Gaussian context, x – E ( x | Z ) ⊥  y – E ( y | Z ) ⇒ x – E ( x | Z ) ⊥  z or y – E ( y | Z ⊥  z (∀ z ∈  Z ) if Z is a minimal d -separator, which implies z causes x (or y ) if z directly connects to x (or y ). Therefore, we conclude that CIs have useful information for distinguishing Markov equivalence classes. In summary, compared with the existing discretization-based and kernel-based CI testing methods, the proposed method provides a simpler way to measure CI, which needs only one unconditional independence test and two regression operations. When being applied to causal discovery, it can find more causal relationships, which is experimentally validated.

We define a consensus postulate in the propositional belief merging setting. In a nutshell, this postulate imposes the merged base to be consistent with the pieces of information provided by each agent involved in the merging process. The interplay of this new postulate with the IC postulates for belief merging is studied, and an incompatibility result is proved. The maximal sets of IC postulates which are consistent with the consensus postulate are exhibited. When satisfying some of the remaining IC postulates, consensus operators are shown to suffer from a weak inferential power. We then introduce two families of consensus operators having a better inferential power by setting aside some of these postulates.

Causal discovery without intervention is well recognized as a challenging yet powerful data analysis tool, boosting the development of other scientific areas, such as biology, astronomy, and social science. The major technical difficulty behind the observation-based causal discovery is to effectively and efficiently identify causes and effects from correlated variables given the existence of significant noises. Previous studies mostly employ two very different methodologies under Bayesian network framework, namely global likelihood maximization and locally complexity analysis over marginal distributions. While these approaches are effective in their respective problem domains, in this paper, we show that they can be combined to formulate a new global optimization model with local statistical significance, called structural equational likelihood framework (or SELF in short). We provide thorough analysis on the soundness of the model under mild conditions and present efficient heuristic-based algorithms for scalable model training. Empirical evaluations using XGBoost validate the superiority of our proposal over state-of-the-art solutions, on both synthetic and real world causal structures.

Rienstra 2012) to indicate whether all and only these arguments Within the field of artificial intelligence, abstract argumentation are active, or with each spanning subtree of the argument frameworks have emerged as a useful methodology graph (Hunter 2014) to indicate that all and only the to represent and evaluate nonmonotonic logics. They allow attacks contained in that subtree are active. In all these models, to create a simple, directed graph from a defeasible knowledge an interesting question is to determine the probability base that consists of only arguments (nodes) and attacks for a set of arguments to be acceptable. A different branch (directed edges), then to identify sets of "acceptable" of research on probabilistic argumentation uses probabilities arguments in that graph, and finally to interpret these arguments' to represent the epistemic state of arguments, attacks, or sets conclusions as models in the knowledge base. In this of arguments, i.e., the belief in those elements (in terms of framework, when evaluating which arguments are acceptable acceptance). Although technically similar, this approach has in the graph, the internal structure of arguments is neglected, a completely different purpose than ours, which is the representation which accounts for the simplicity of the formalism.

Answer Set Programming (ASP) is a well-established formalism for nonmonotonic reasoning.While incoherence, the non-existence of answer sets for some programs, is an important feature of ASP, it has frequently been criticised and indeed has some disadvantages, especially for query answering.Paracoherent semantics have been suggested as a remedy, which extend the classical notion of answer sets to draw meaningful conclusions also from incoherent programs. In this paper we present an alternative characterization of the two major paracoherent semantics in terms of (extended) externally supported models. This definition uses a transformation of ASP programs that is more parsimonious than the classic epistemic transformation used in recent implementations.A performance comparison carried out on benchmarks from ASP competitions shows that the usage of the new transformation brings about performance improvements that are independent of the underlying algorithms.

We propose AutoID, a human identification system that leverages the measurements from existing WiFi-enabled Internet of Things (IoT) devices and produces the identity estimation via a novel sparse representation learning technique. The key idea is to use the unique fine-grained gait patterns of each person revealed from the WiFi Channel State Information (CSI) measurements, technically referred to as shapelet signatures, as the "fingerprint" for human identification. For this purpose, a novel OpenWrt-based IoT platform is designed to collect CSI data from commercial IoT devices. More importantly, we propose a new optimization-based shapelet learning framework for tensors, namely Convex Clustered Concurrent Shapelet Learning (C3SL), which formulates the learning problem as a convex optimization. The global solution of C3SL can be obtained efficiently with a generalized gradient-based algorithm, and the three concurrent regularization terms reveal the inter-dependence and the clustering effect of the CSI tensor data. Extensive experiments are conducted in multiple real-world indoor environments, showing that AutoID achieves an average human identification accuracy of 91% from a group of 20 people. As a combination of novel sensing and learning platform, AutoID attains substantial progress towards a more accurate, cost-effective and sustainable human identification system for pervasive implementations.

We introduce a novel model-agnostic system that explains the behavior of complex models with high-precision rules called anchors, representing local, "sufficient" conditions for predictions. We propose an algorithm to efficiently compute these explanations for any black-box model with high-probability guarantees. We demonstrate the flexibility of anchors by explaining a myriad of different models for different domains and tasks. In a user study, we show that anchors enable users to predict how a model would behave on unseen instances with less effort and higher precision, as compared to existing linear explanations or no explanations.

We consider a market setting in which buyers are individuals of a population, whose relationships are represented by an underlying social graph. Given buyers valuations for the items being sold, an outcome consists of a pricing of the objects and an allocation of bundles to the buyers. An outcome is social envy-free if no buyer strictly prefers the bundles of her neighbors in the social graph. We focus on the revenue maximization problem in multi-unit markets, in which there are multiple copies of a same item being sold and each buyer is assigned a set of identical items. We consider the four different cases arising by considering different buyers valuations, i.e., single-minded or general, and by adopting different forms of pricing, that is item- or bundle-pricing. For all the above cases we show the hardness of the revenue maximization problem and give corresponding approximation results. All our approximation bounds are optimal or nearly optimal. Moreover, we provide an optimal allocation algorithm for general valuations with item-pricing, under the assumption of social graphs of bounded treewidth. Finally, we determine optimal bounds on the corresponding price of envy-freeness, that is on the worst case ratio between the maximum revenue that can be achieved without envy-freeness constraints, and the one obtainable in case of social relationships. Some of our results close hardness open questions or improve already known ones in the literature concerning the classical setting without sociality.

Leadership games provide a powerful paradigm to model many real-world settings. Most literature focuses on games with a single follower who acts optimistically , breaking ties in favour of the leader. Unfortunately, for real-world applications, this is unlikely. In this paper, we look for efficiently solvable games with multiple followers who play either optimistically or pessimistically , i.e., breaking ties in favour or against the leader. We study the computational complexity of finding or approximating an optimistic or pessimistic leader-follower equilibrium in specific classes of succinct games—polymatrix like—which are equivalent to 2-player Bayesian games with uncertainty over the follower, with interdependent or independent types. Furthermore, we provide an exact algorithm to find a pessimistic equilibrium for those game classes. Finally, we show that in general polymatrix games the computation is harder even when players are forced to play pure strategies.