FO(C)

A Knowledge Representation Language of Causality

Bart Bogaerts, Joost Vennekens, Marc Denecker (KU Leuven)
Jan Van den Bussche (Hasselt University & transnational University of Limburg)

Goal

Develop a good modelling language for causality

Overview

  • Principles of Causation
  • CP-Logic
  • C-Log & FO(C)
  • Conclusion & Related Work

Principles of Causation

  • Universal causation: all changes to the state of the domain must be triggered by a causal law whose precondition is satisfied.
  • Sufficient causation: if the precondition for a causal law is satisfied, then the event that it triggers must eventually happen.
  • Independent causation: which event a causal law triggers is not influenced by other causal laws.

CP-Logic

Cause-effect relations

\[ \begin{align} \mathrm{Turn}(\mathrm{BigGear}) &\leftarrow \mathrm{Pedal}. && (1) \\ \mathrm{Turn}(\mathrm{BigGear}) &\leftarrow \mathrm{Turn}(\mathrm{SmallGear}). && (2)\\ \mathrm{Turn}(\mathrm{SmallGear}) &\leftarrow \mathrm{Turn}(\mathrm{BigGear}). && (3) \end{align} \]

\[ \begin{equation}\label{branch} \{\mathrm{P}\} \overset{(1)}{\rightarrow} \{\mathrm{P},\mathrm{T}(\mathrm{B})\} \overset{(3)}{\rightarrow} \{\mathrm{P},\mathrm{T}(\mathrm{B}),\mathrm{T}(\mathrm{S})\} \overset{\text{(2)}}{\rightarrow} \{\mathrm{P},\mathrm{T}(\mathrm{B}),\mathrm{T}(\mathrm{S})\} \end{equation} \]

Non-Determinism

\[\mathrm{Turn}(\mathrm{SmallGear}) \,\mathbf{Or}\, \mathrm{ChainBreaks} \leftarrow \mathrm{Turn}(\mathrm{BigGear})\]

Branching of possibilities

C-Log

  • Extension of CP-Logic
  • Motivation: many things are not naturally expressable in CP-Logic
  • Expressive language for cause-effect relations
    • Non-deterministic choice
      • Dynamic set of alternatives
    • Object creation
    • Arbitrary nesting
    • ...

Dynamic Choice

\[\mathbf{Select}\, x[\varphi(x)]: C\]

Lottery

\[\mathbf{Select}\, x[Plays(x)]: Rich(x)\]

In CP-Logic: only possible if $Plays$ is known statically
\[Rich(Alice)\,\mathbf{Or}\,Rich(Bob)\,\mathbf{Or}\,\dots\]

Robot

\[\left\{\begin{array}{l}Open(x)\leftarrow Open_I(x)\\ \mathbf{Select}\, x[Door(x)]: Open(x)\\ \mathbf{Select}\, x[Door(x)\wedge Open(x)]: Exit(x)\end{array}\right\}\]

Nesting

Arbitrary nesting of effects

Lightning

\[ \left(\mathbf{Select}\, h[House(h)]: (\mathbf{All} \, o[In(o,h)]: Broken(o)) \right)\] \[ \leftarrow Lightning \]

Object Creation

\[\mathbf{New}\, x: C\]
Existence of objects governed by causal rules

Mail Protocol

\[\begin{array}{l}\mathbf{All}\, m, t[HitSend(m,t)]: \mathbf{New}\, p:\\ \quad Pack(p) \,\mathbf{And}\, OnCh(p,t)\,\mathbf{And}\, Cont(p,m) \end{array} \]

Summary: syntax

A Causal Effect Expression (CEE) is one of the following:
(if $C$, $C_1$, $C_2$ are CEEs, $\varphi$ a formula, $A$ an atom, $x$ a variable)
  • $ A $
  • $ C\leftarrow \varphi $
  • $ C_1 \,\mathbf{And}\, C_2 $
  • $ C_1 \,\mathbf{Or}\, C_2 $
  • $ \mathbf{All}\, x[\varphi]: C $
  • $ \mathbf{Select}\, x[\varphi]: C $
  • $ \mathbf{New}\, x: C $

Semantics

Generalisation of instance-based semantics for D-LP
Based on Approximation Fixpoint Theory

FO(C)

First-order logic + C-Log

Related paradigms

  • The logic of cause and change (McCain and Turner 1996)
  • BLOG (Milch et al. 2005)
  • P-Log (Baral, Gelfond, and Rushton 2004)
  • Structural models (Pearl 2000)
  • Representations of causal logics in (D-)ASP (many people)
  • Datalog extensions (Abiteboul, Hull, and Vianu 1995)
  • ...

Conclusions and Future Work

  • FO(C) is a rich modelling language...
  • ...focussing on natural expressivity of causality...
  • ...but is far from finished (we need to study what more to add to FO(C))

References

( B. Bogaerts, J. Vennekens, M. Denecker and J. Van den Bussche )
  • Inference in the FO(C) Modelling Language 
    • European Conference on Artificial Intelligence (ECAI), 2014.
    • 15th International Workshop on Non-Monotonic Reasoning ,  2014 .

  • FO(C) and Related Modelling Paradigms 15th International Workshop on Non-Monotonic Reasoning, 2014.

  • FO(C): A Knowledge Representation Language of Causality International Conference of Logic Programming (ICLP), (Technical communication), 2014.

Thank you!

Questions?