Representing defeasibility is an important issue in common sense reasoning. In reasoning about action and change, this issue becomes more difficult because domain and action related defeasible information may conflict with general inertia rules. Furthermore, different types of defeasible information may also interfere with each other during the reasoning. In this paper, we develop a prioritized logic programming approach to handle defeasibilities in reasoning about action. In particular, we propose three action languages AT ^ 0 , AT ^ 1 and AT ^ 2 which handle three types of defeasibilities in action domains named defeasible constraints, defeasible observations and actions with defeasible and abnormal effects respectively. Each language with a higher superscript can be viewed as an extension of the language with a lower superscript. These action languages inherit the simple syntax of A language but their semantics is developed in terms of transition systems where transition functions are defined based on prioritized logic programs. By illustrating various examples, we show that our approach eventually provides a powerful mechanism to handle various defeasibilities in temporal prediction and postdiction. We also investigate semantic properties of these three action languages and characterize classes of action domains that present more desirable solutions in reasoning about action within the underlying action languages.
Although the work presented in @cite_2 provided a natural way to represent causality in reasoning about action, there were several restrictions in this action theory. First, due to technical restrictions, only normal defaults or defaults without justifications are the suitable forms to represent causal rules in problem domains. Second, this action theory did not handle the other two major defeasibilities - defeasible observations and actions with defeasible and abnormal effects.
@cite_2
2017479918 2150014546 204991199 2321919568 2143602574 2040355224 2154988829 1983914828 1961009203 1967802770 2129578857 2050335327 2064134784 1850984366 2072046078 2542071751 2564513914 2100515808 2165352044 2020138862
Recent research on reasoning about action has shown that the traditional logic form of domain constraints is problematic to represent ramifications of actions that are related to causality of domains. To handle this problem properly, as proposed by some researchers, it is necessary to describe causal relations of domains explicitly in action theories. In this paper, we address this problem from a new point of view. Specifically, unlike other researchers viewing causal relations as some kind of inference rules, we distinguish causal relations between defeasible and non-defeasible cases. It turns out that a causal theory in our formalism can be specified by using Reiter's default logic. Based on this idea, we propose a causality-based minimal change approach for representing effects of actions, and argue that our approach provides more plausible solutions for the ramification and qualification problems compared with other related work. We also describe a logic programming approximation to compute causal theories of actions which provides an implementational basis for our approach. Michotte's theory of ampliation suggests that causal relationships are perceived by objects animated under appropriate spatiotemporal conditions. We extend the theory of ampliation and propose that the immediate perception of complex causal relations is also dependent on a set of structural and temporal rules. We designed animated representations, based on Michotte's rules, for showing complex causal relationships or causal semantics. In this paper we describe a set of animations for showing semantics such as causal amplification, causal strength, causal dampening, and causal multiplicity. In a two part study we compared the effectiveness of both the static and animated representations. The first study (N=44) asked participants to recall passages that were previously displayed using both types of representations. Participants were 8 more accurate in recalling causal semantics when they were presented using animations instead of static graphs. In the second study (N=112) we evaluated the intuitiveness of the representations. Our results showed that while users were as accurate with the static graphs as with the animations, they were 9 faster in matching the correct causal statements in the animated condition. Overall our results show that animated diagrams that are designed based on perceptual rules such as those proposed by Michotte have the potential to facilitate comprehension of complex causal relations. We address the problem of visually detecting causal events and fitting them together into a coherent story of the action witnessed by the camera. We show that this can be done by reasoning about the motions and collisions of surfaces, using high-level causal constraints derived from psychological studies of infant visual behavior. These constraints are naive forms of basic physical laws governing substantiality, contiguity, momentum, and acceleration. We describe two implementations. One system parses instructional videos, extracting plans of action and key frames suitable for storyboarding. Since learning will play a role in making such systems robust, we introduce a new framework for higher-order hidden Markov models and demonstrate its use in a second system that segments stereo video into actions in near real-time. Rather than attempt accurate low-level vision, both systems use high-level causal analysis to integrate fast but sloppy pixel-based representations over time. The output is suitable for summary, indexing, and automated editing. Causal reasoning plays an essential role in both informal and formal human decision-making. Causality itself as well as human understanding of causality is imprecise, sometimes necessarily so. A common sense understanding of the world tells us that we have to deal with imprecision, uncertainty and imperfect knowledge. A difficulty is striking a good balance between precise formalism and commonsense imprecise reality. An algorithmic method of accommodating imprecision in causality is needed. Today, data mining holds the promise of extracting unsuspected information from very large databases. However, the most common data mining rule forms do not express a causal relationship. Without understanding the underlying causality, a naive use of data mining rules can lead to undesirable actions. We present a formal framework that combines high-level representation and causality-based reasoning with low-level geometric reasoning and motion planning. The frame-work features bilateral interaction between task and motion planning, and embeds geometric reasoning in causal reasoning, thanks to several advantages inherited from its underlying components. In particular, our choice of using a causality-based high-level formalism for describing action domains allows us to represent ramifications and state transition constraints, and embed in such formal domain descriptions externally defined functions implemented in some programming language (e.g., C++). Moreover, given such a domain description, the causal reasoner based on this formalism (i.e., the Causal Calculator) allows us to compute optimal solutions (e.g., shortest plans) for elaborate planning prediction problems with temporal constraints. Utilizing these features of high-level representation and reasoning, we can combine causal reasoning, motion planning and geometric planning to find feasible kinematic solutions to task-level problems. In our framework, the causal reasoner guides the motion planner by finding an optimal task-plan; if there is no feasible kinematic solution for that task-plan then the motion planner guides the causal reasoner by modifying the planning problem with new temporal constraints. Furthermore, while computing a task-plan, the causal reasoner takes into account geometric models and kinematic relations by means of external predicates implemented for geometric reasoning (e.g., to check some collisions); in that sense the geometric reasoner guides the causal reasoner to find feasible kinematic solutions. We illustrate an application of this framework to robotic manipulation, with two pantograph robots on a complex assembly task that requires concurrent execution of actions. A short video of this application accompanies the paper. Most approaches to representing causality, such as the common causal graph, require a separate and static view, but in many cases it is useful to add the dimension of causality to the context of an existing visualization. Building on research from perceptual psychology that shows the perception of causality is a low-level visual event derived from certain types of motion, we are investigating how to add animated causal representations, called visual causal vectors, onto other visualizations. We refer to these as causal overlays. Our initial experimental results show this approach has great potential but that extra cues are needed to elicit the perception of causality when the motions are overlaid on other graphical objects. In this paper we describe the approach and report on a study that examined two issues of this technique: how to accurately convey the causal flow and how to represent the strength of the causal effect. Attribution theorists typically have conceived the attribution process in terms of universal laws of cognitive functioning, independent of social interaction. In this paper we argue for the notion, grounded in recent ordinary language philosophy, that any consideration of the form of everyday explanation must take into account its function as an answer to a ‘why’ question within a conversational framework. Experiment 1 provides support for the idea that speakers should identify as causally relevant that necessary condition for the occurrence of an event about which the enquirer is ignorant. Experiment 2 replicates this basic finding and further demonstrates that speakers will change their explanations to enquirers believed to be sharing different knowledge about the same target event. Experiment 2 also assessed the role of individual differences in conversational rule-following, and found in apparent contrast some previous predictions that high self-monitoring individuals were no more likely than lows to tailor their explanations to suit the enquirer's knowledge state. If anything, the reverse occurred. Taken together, these experiments support the central contention of the abnormal conditions focus model (Hilton and Slugoski, 1986), that the common sense criterion of causality is that of an ‘abnormal condition’ rather than constant conjunction as instantiated in the ANOVA model of causal attribution (Kelley, 1967, 1973). In this paper we recast the classical Darondeau---Degano's causal semantics of concurrency in a coalgebraic setting, where we derive a compact model. Our construction is inspired by the one of Montanari and Pistore yielding causal automata, but we show that it is instance of an existing categorical framework for modeling the semantics of nominal calculi, whose relevance is further demonstrated. The key idea is to represent events as names, and the occurrence of a new event as name generation. We model causal semantics as a coalgebra over a presheaf, along the lines of the Fiore---Turi approach to the semantics of nominal calculi. More specifically, we take a suitable category of finite posets, representing causal relations over events, and we equip it with an endofunctor that allocates new events and relates them to their causes. Presheaves over this category express the relationship between processes and causal relations among the processes' events. We use the allocation operator to define a category of well-behaved coalgebras: it models the occurrence of a new event along each transition. Then we turn the causal transition relation into a coalgebra in this category, where labels only exhibit maximal events with respect to the source states' poset, and we show that its bisimilarity is essentially Darondeau---Degano's strong causal bisimilarity. This coalgebra is still infinite-state, but we exploit the equivalence between coalgebras over a class of presheaves and History Dependent automata to derive a compact representation, where states only retain the poset of the most recent events for each atomic subprocess, and are isomorphic up to order-preserving permutations. Remarkably, this reduction of states is automatically performed along the equivalence. Mining for association rules in market basket data has proved a fruitful area of research. Measures such as conditional probability (confidence) and correlation have been used to infer rules of the form “the existence of item A implies the existence of item B.” However, such rules indicate only a statistical relationship between A and B. They do not specify the nature of the relationship: whether the presence of A causes the presence of B, or the converse, or some other attribute or phenomenon causes both to appear together. In applications, knowing such causal relationships is extremely useful for enhancing understanding and effecting change. While distinguishing causality from correlation is a truly difficult problem, recent work in statistics and Bayesian learning provide some avenues of attack. In these fields, the goal has generally been to learn complete causal models, which are essentially impossible to learn in large-scale data mining applications with a large number of variables. In this paper, we consider the problem of determining casual relationships, instead of mere associations, when mining market basket data. We identify some problems with the direct application of Bayesian learning ideas to mining large databases, concerning both the scalability of algorithms and the appropriateness of the statistical techniques, and introduce some initial ideas for dealing with these problems. We present experimental results from applying our algorithms on several large, real-world data sets. The results indicate that the approach proposed here is both computationally feasible and successful in identifying interesting causal structures. An interesting outcome is that it is perhaps easier to infer the lack of causality than to infer causality, information that is useful in preventing erroneous decision making. Abstract There are two distinct formalizations for reasoning from observations to explanations, as in diagnostic tasks. The consistency based approach treats the task as a deductive one, in which the explanation is deduced from a background theory and a minimal set of abnormalities. The abductive method, on the other hand, treats explanations as sentences that, when added to the background theory, derive the observations. We show that there is a close connection between these two formalizations in the context of simple causal theories: domain theories in which a set of sentences are singled out as the explanatorily relevant causes of observations. There are two main results, which show that (with certain caveats) the consistency based approach can emulate abductive reasoning by adding closure axioms to a causal theory; and that abductive techniques can be used in place of the consistency based method in the domain of logic based diagnosis. It is especially interesting that in the latter case, the abductive techniques generate only relevant explanations, while diagnoses may have irrelevant elements. Causal relations are present in many application domains. Causal Probabilistic Logic (CP-logic) is a probabilistic modeling language that is especially designed to express such relations. This paper investigates the learning of CP-logic theories (CP-theories) from training data. Its first contribution is SEM-CP-logic, an algorithm that learns CP-theories by leveraging Bayesian network (BN) learning techniques. SEM-CP-logic is based on a transformation between CP-theories and BNs. That is, the method applies BN learning techniques to learn a CP-theory in the form of an equivalent BN. To this end, certain modifications are required to the BN parameter learning and structure search, the most important one being that the refinement operator used by the search must guarantee that the constructed BNs represent valid CP-theories. The paper's second contribution is a theoretical and experimental comparison between CP-theory and BN learning. We show that the most simple CP-theories can be represented with BNs consisting of noisy-OR nodes, while more complex theories require close to fully connected networks (unless additional unobserved nodes are introduced in the network). Experiments in a controlled artificial domain show that in the latter cases CP-theory learning with SEM-CP-logic requires fewer training data than BN learning. We also apply SEM-CP-logic in a medical application in the context of HIV research, and show that it can compete with state-of-the-art methods in this domain. Discovering causal relationships in large databases of observational data is challenging. The pioneering work in this area was rooted in the theory of Bayesian network (BN) learning, which however, is a NP-complete problem. Hence several constraint-based algorithms have been developed to efficiently discover causations in large databases. These methods usually use the idea of BN learning, directly or indirectly, and are focused on causal relationships with single cause variables. In this paper, we propose an approach to mine causal rules in large databases of binary variables. Our method expands the scope of causality discovery to causal relationships with multiple cause variables, and we utilise partial association tests to exclude noncausal associations, to ensure the high reliability of discovered causal rules. Furthermore an efficient algorithm is designed for the tests in large databases. We assess the method with a set of real-world diagnostic data. The results show that our method can effectively discover interesting causal rules in large databases. In this paper we present a language to reason about actions in a probabilistic setting and compare our work with earlier work by Pearl.The main feature of our language is its use of static and dynamic causal laws, and use of unknown (or background) variables - whose values are determined by factors beyond our model - in incorporating probabilities. We use two kind of unknown variables: inertial and non-inertial. Inertial unknown variables are helpful in assimilating observations and modeling counterfactuals and causality; while non-inertial unknown variables help characterize stochastic behavior, such as the outcome of tossing a coin, that are not impacted by observations. Finally, we give a glimpse of incorporating probabilities into reasoning with narratives. The discovery of causal relationships from purely observational data is a fundamental problem in science. The most elementary form of such a causal discovery problem is to decide whether X causes Y or, alternatively, Y causes X, given joint observations of two variables X,Y. An example is to decide whether altitude causes temperature, or vice versa, given only joint measurements of both variables. Even under the simplifying assumptions of no confounding, no feedback loops, and no selection bias, such bivariate causal discovery problems are challenging. Nevertheless, several approaches for addressing those problems have been proposed in recent years. We review two families of such methods: methods based on Additive Noise Models (ANMs) and Information Geometric Causal Inference (IGCI). We present the benchmark CAUSEEFFECTPAIRS that consists of data for 100 different causee ffect pairs selected from 37 data sets from various domains (e.g., meteorology, biology, medicine, engineering, economy, etc.) and motivate our decisions regarding the "ground truth" causal directions of all pairs. We evaluate the performance of several bivariate causal discovery methods on these real-world benchmark data and in addition on artificially simulated data. Our empirical results on real-world data indicate that certain methods are indeed able to distinguish cause from effect using only purely observational data, although more benchmark data would be needed to obtain statistically significant conclusions. One of the best performing methods overall is the method based on Additive Noise Models that has originally been proposed by (2009), which obtains an accuracy of 63 ± 10 and an AUC of 0.74 ± 0.05 on the real-world benchmark. As the main theoretical contribution of this work we prove the consistency of that method. The nonmonotonic causal logic defined in this paper can be used to represent properties of actions, including actions with conditional and indirect effects, nondeterministic actions, and concurrently executed actions. It has been applied to several challenge problems in the theory of commonsense knowledge. We study the relationship between this formalism and other work on nonmonotonic reasoning and knowledge representation, and discuss its implementation, called the Causal Calculator. Motivated by online recommendation and advertising systems, we consider a causal model for stochastic contextual bandits with a latent low-dimensional confounder. In our model, there are @math observed contexts and @math arms of the bandit. The observed context influences the reward obtained through a latent confounder variable with cardinality @math ( @math ). The arm choice and the latent confounder causally determines the reward while the observed context is correlated with the confounder. Under this model, the @math mean reward matrix @math (for each context in @math and each arm in @math ) factorizes into non-negative factors @math ( @math ) and @math ( @math ). This insight enables us to propose an @math -greedy NMF-Bandit algorithm that designs a sequence of interventions (selecting specific arms), that achieves a balance between learning this low-dimensional structure and selecting the best arm to minimize regret. Our algorithm achieves a regret of @math at time @math , as compared to @math for conventional contextual bandits, assuming a constant gap between the best arm and the rest for each context. These guarantees are obtained under mild sufficiency conditions on the factors that are weaker versions of the well-known Statistical RIP condition. We further propose a class of generative models that satisfy our sufficient conditions, and derive a lower bound of @math . These are the first regret guarantees for online matrix completion with bandit feedback, when the rank is greater than one. We further compare the performance of our algorithm with the state of the art, on synthetic and real world data-sets. One of the key uses of causes is to explain why things happen. Explanations of specific events, like an individual's heart attack on Monday afternoon or a particular car accident, help assign responsibility and inform our future decisions. Computational methods for causal inference make use of the vast amounts of data collected by individuals to better understand their behavior and improve their health. However, most methods for explanation of specific events have provided theoretical approaches with limited applicability. In contrast we make two main contributions: an algorithm for explanation that calculates the strength of token causes, and an evaluation based on simulated data that enables objective comparison against prior methods and ground truth. We show that the approach finds the correct relationships in classic test cases (causal chains, common cause, and backup causation) and in a realistic scenario (explaining hyperglycemic episodes in a simulation of type 1 diabetes). We present a novel reasoning calculus for the description logic SHOIQ+--a knowledge representation formalism with applications in areas such as the SemanticWeb. Unnecessary nondeterminism and the construction of large models are two primary sources of inefficiency in the tableau-based reasoning calculi used in state-of-the-art reasoners. In order to reduce nondeterminism, we base our calculus on hypertableau and hyperresolution calculi, which we extend with a blocking condition to ensure termination. In order to reduce the size of the constructed models, we introduce anywhere pairwise blocking. We also present an improved nominal introduction rule that ensures termination in the presence of nominals, inverse roles, and number restrictions--a combination of DL constructs that has proven notoriously difficult to handle. Our implementation shows significant performance improvements over state-of-the-art reasoners on several well-known ontologies. This work shows how to leverage causal inference to understand the behavior of complex learning systems interacting with their environment and predict the consequences of changes to the system. Such predictions allow both humans and algorithms to select the changes that would have improved the system performance. This work is illustrated by experiments carried out on the ad placement system associated with the Bing search engine. This paper shows how action theories, expressed in an extended version of the language , can be naturally encoded using Prioritized Default Theory. We also show how prioritized default theory can be extended to express preferences between rules. This extension provides a natural framework to introduce different types of preferences in action theories—preferences between actions and preferences between final states. In particular, we demonstrate how these preferences can be expressed within extended prioritized default theory. We also discuss how this framework can be implemented in terms of answer set programming.