CAKE System

Computer Aided Knowledge Engineering

based on: P. Doherty, W. Łukaszewicz, A. Skowron, A. Szałas: Knowledge Representation Techniques: A Rough Set Approach, Springer-Verlag, 2006.

• Goal: reasoning in the framework of distributed and incomplete information.

• Basis: a rough relation paradigm.

More specifically, a rough relation R is a triple ⟨R^{+} , R^{−}, R^{±}⟩, where R^{+} denotes a set of tuples known to satisfy R, R^{−} denotes a set of tuples known not to satisfy R and R^{±} denotes a set of remaining tuples.

• Visualization: diagrams representing rough relations.

• Implementation: Department of Computer and Information Science of Linköping University.

The basic notion of CAKE is that of an information granule. Any granule contains information concerning a single rough relation.

Diagram representing a CAKE granule.

Negative knowledge Context b̄_{1}, …,b̄_{l} l_{1} : LCC_{1}, …, l_{m}: LCC_{m} Positive knowledge ā_{1}, …, ā_{k} N : R(x̄)  } } } +−

If a relation is given by many sources, it should be distributed among many granules. To point out the source of information, any relation is prefixed by a name of a granule.

Diagram representing input relations for a CAKE granule.

[figure: N_{1}:R_{1}; N_{l}:R_{l}; …; N: R; N_{2}:R_{2}; +; +; +; +; −; −; −; −]

Formally, an information granule can be viewed as a set of facts and rules allowing to compute the relation the granule is responsible for.

Example 1 We are given two databases, DB_{1} and DB_{2}, containing information about a relation C(x, y) meaning that a place x is directly connected with a place y.

DB_{1} contains C(j, m), C(m, r) and DB_{2} contains C(m, k), C(j, l).

Let D_{1} and D_{2} be names of information granules representing these databases. D_{1} consists of D_{1}.C^{+} (j, m), D_{1}.C^{+} (m, r), D_{2} consists of D_{2}.C^{+} (m, k), D_{2}.C^{+} (j, l).^{∗}

∗Only positive and negative parts of relation are explicitly represented in facts and rules.

Now we want to combine information from D_{1} and D_{2} and to represent indirect connections too. We introduce a new granule, D, provided with the following rules.

Diagram of Example 1.

[figure: A_{2}:C(x, y); A_{1}:C(x, y); ⟨J, M⟩; ⟨J, L⟩; [C^{+} (x, z)∧C^{+} (z, y)]; A_{2}.C^{+} (x, y); A_{1}.C^{+} (x, y); AG : C(x, y); ⟨M, K⟩; +; +; +; −; −; −; ⟨M, R⟩]

and the set of rules defined by this diagram.

D_{1}.C^{+} (x, y) ∧ ¬D_{2}.C^{−}(x, y) ⇒ D.C^{+} (x, y)  (1)
D_{1}.C^{−}(x, y) ∧ ¬D_{2}.C^{+} (x, y) ⇒ D.C^{−}(x, y)  (2)
D_{2}.C^{+} (x, y) ∧ ¬D_{1}.C^{−}(x, y) ⇒ D.C^{+} (x, y)  (3)
D_{2}.C^{−}(x, y) ∧ ¬D_{1}.C^{+} (x, y) ⇒ D.C^{−}(x, y)  (4)
D.C^{+} (x, z) ∧ D.C^{+} (z, y) ⇒ D.C^{+} (x, y).  (5)

The rules (1)-(4) import consistent information from D_{1} and D_{2}.

¬D_{i}.C^{+} (x, y) is equivalent to D_{i}.C^{−}(x, y) ∨ D_{i}.C^{±}(x, y) ¬D_{i}.C^{−}(x, y) is equivalent to D_{i}.C^{+} (x, y) ∨ D_{i}.C^{±}(x, y).

Using the facts stored by D_{1} and D_{2}, together with the rules (1)-(5), we can infer D.C^{+} (j, k).

We say that the granule D answers “yes” to the query whether there is a connection between j and k.

Syntax of CAKE

Alphabet of classical first-order logic containing an enumerable set of individual variables and finite sets of individual constants and relation symbols^{∗}.

An atomic formula, C-atom for short, – expression of the form A.R^{+} (u) or A.R^{−}(u), where A – a name of an information granule, R – a relation name, u – a tuple of individual variables and/or constant symbols.

A literal is a C-atom or an expression of the form ¬α, where α is a C-atom.

∗Note that CAKE does not permit function symbols.

A CAKE rule – any expression of the form

α_{1} ∧ … ∧ α_{n} ⇒ α (n ≥ 0) (6)

where α_{1}, …, α_{n} are literals and α is C-atom. α – the head of the rule, α_{1} ∧ … ∧ α_{n} – its body.

A rule with the empty body is called a fact. In the sequel, we shall write α instead of ⇒ α.

Any finite set of rules and facts is called a CAKE program.

Definition 1 Let (x_{1}, …, x_{n}) be a tuple of all free variables occurring in a rule (6). A ground instance of (6) is any rule obtainable from (6) by uniformly replacing each occurrence of x_{i} by c_{i}, where c_{i} is an individual constant, for 1 ≤ i ≤ n. A set of all ground instances of all rules from a program Π is called the ground instance of Π.

Voting

Problem: different granules may provide contradictory information about a particular relation. A granule which combines information from contradictory sources (as D in Example 1) has to solve the inconsistency problem. In Example 1 the problem is solved by the rules (1)-(4).

In general case, i.e. if there are many different granules responsible for a relation, an additional granule, called voting granule, is introduced and equipped with rules solving inconsistencies.

The standard voting mechanism is based on the following idea.

• if at least one granule responsible for relation R answers True to the query and none of the granules answers False , the final answer to the query is True

• if at least one granule answers False to the query and none answers True , the final answer to the query is False .

• otherwise, the answer to the query is Unknown .

Formalization

M – the set of all granules delivering the relation R. V – the CAKE voting granule attached to relation R

_{N∈M}^{⋁} N.R^{+} (x) ∧ _{N∈M}^{⋀} ¬N.R^{−}(x) ⇒ V.R^{+} (x)
_{N∈M}^{⋁} N.R^{−}(x) ∧ _{N∈M}^{⋀} ¬N.R^{+} (x) ⇒ V.R^{−}(x)

The standard voting policy may be changed, for instance, by providing priorities among granules.

Semantics of CAKE

Stratified semantics (fixpoint semantics) of CAKE programs.

Definition 2 A CAKE program Π is said to be semi-positive if, whenever a literal l occurs negatively in the body of a rule of Π, then the relation symbol of l occurs in facts only.

Π – a semi-positive CAKE program, K – a set of ground C-atoms.

Definition 3 A ground C-atom α is an immediate consequence of Π and K if either α ∈ K or α_{1} ∧ … ∧ α_{n} ⇒ α is a ground instance of a rule from Π such that

1. if α_{i} is a positive literal, then α_{i} ∈ K and

2. if α_{i} is negative literal of the form ¬β_{i}, then β_{i} ∉ K.

operator C_{Π} : C_{Π} (K) – the set of all immediate consequences of Π and any set of ground C-atoms K.

Let Π be a semi-positive CAKE program. The set of consequences of Π is the smallest fixpoint, written lfp, of the operator C_{Π} . For a semi-positive CAKE program Π, lfp(C_{Π}) always exists and is given by the following construction:

X:=K, where K is the set of all facts from Π;

while X≠ C_{Π} (X) do X:=C_{Π} (X).

The above semantics can be generalized to stratified CAKE programs.

Definition 4 By a stratification of a CAKE program Π we mean a sequence of CAKE programs Π^{1}, …, Π^{n}, with Π^{1} possibly empty, such that

• Π^{1} ∪ … ∪ Π^{n} = Π and for all 1 ≤ i ≠ j ≤ n, Π^{i} ∩ Π^{j} = ∅

• for any relation X of Π and 1 ≤ i ≤ n:

– if X occurs positively in a rule’s body in Π^{i}, then all the rules with X in their heads are in Π^{1} ∪ … ∪ Π^{i}

– if X occurs in a rule’s body in Π^{i} under negation, then all the rules with X in their heads are in Π^{1} ∪ … ∪ Π^{i−1}.

Given a stratification Π^{1}, …, Π^{n} of Π, each Π^{i} is called a stratum of the stratification. A program is called stratified if it has a stratification.

Let Π be a stratified CAKE program and let Π^{1}, …, Π^{n} be its stratification. We define an operator CS_{Π} (X) by

CS_{Π} (X) = CS_{Π}^{n}(X), where
CS_{Π}^{1} (X) = C_{Π^{1}} (X)
CS_{Π}^{i} (X) = C_{Π^{i}∪lfp(CS_{Π}^{i−1})} (X).

The set of consequences of Π is the smallest fixpoint of an operator CS_{Π} . Its existence follows from the fact that, for 1 < i ≤ n, the program Π^{i} ∪ lfp(CS_{Π}^{i−1}) is semi-positive.

Well-founded Semantics for CAKE Programs

Well-founded semantics is based on a notion of three-valued interpretation, in which the truth value of facts can be True , False or Unknown . In the sequel, we shall consider only finite interpretations, i.e. interpretations providing truth values to all ground C-atoms in a given CAKE program Π.

Three-valued interpretations.

Definition 5 Let AT M(Π) be a set of all ground C-atoms in a CAKE program Π. A 3-valued interpretation S of (Π) is a mapping from AT M(Π) into the set {True ,Unknown ,False }.

We denote by S^{0}, S^{1/2} , S^{1} the set of C-atoms in AT M(Π) whose truth value is False , Unknown and True respectively.

Representation of a 3-valued interpretation – the list of the positive and negative facts only. For instance, if S (P^{+} (a)) = True , S (P^{+} (b)) = Unknown , S (P^{−}(b)) = Unknown and S (P^{−}(a)) = False then it may be represented as S ={P^{+} (a), ¬P^{−}(a)}.

There is a natural ordering ≺ among 3-valued interpretations of a program (Π) defined by

S ≺ T iff S^{1} ⊆ T ^{1} and T ^{0} ⊆ S^{0}.

The least element wrt ≺, denoted by ⊥, is the interpretation where all atoms are false.

Given a 3-valued interpretation S we can extend it in a standard way to Boolean combinations of atoms:

S (A ∧ B) = min (S (A), S (B))
S (A ∨ B) = max (S (A), S (B)),
S (¬A) = \{ \begin{matrix}True & if S (A) = False \\ Unknown & if S (A) = Unknown \\ False & if S (A) = True \end{matrix}

where min , max are defined according to the truth ordering False < Unknown < True .

Definition 6 Given a CAKE program Π and an interpretation S of Π, the positivized version of Π wrt S is the program obtained from ground instance of Π by replacing each negative literal ¬A by S (¬A) (i.e. False , True or Unknown ). Such program will be called a 3-CAKE program.^{∗}

Example 2 Consider a ground CAKE program Π given by

¬R^{+} (a) ⇒ P^{+} (a)
¬R^{+} (a) ∧ P^{+} (a) ⇒ Q^{+} (a)
¬T^{+} (a) ⇒ S^{+} (a)
Q^{+} (a) ∧ ¬S^{+} (a) ⇒ T^{+} (a)
¬T^{+} (a) ∧ P^{+} (a) ∧ S^{+} (a) ⇒ U^{+} (a)

∗Note that 3-CAKE programs do not contain negation symbols.

and the interpretation ⊥ = {¬P^{+} (a), ¬Q^{+} (a), ¬R^{+} (a), ¬S^{+} (a), ¬T^{+} (a), ¬U^{+} (a)}. The positivized version of Π wrt ⊥ is the 3-CAKE program, Π_{+} , given by

True ⇒ P^{+} (a)
True ∧ P^{+} (a) ⇒ Q^{+} (a)
True ⇒ S^{+} (a)
Q^{+} (a) ∧ True ⇒ T^{+} (a)
True ∧ P^{+} (a) ∧ S^{+} (a) ⇒ U^{+} (a).

Computing well-founded semantics

Definition 7 Let Π be a 3-CAKE program. The 3-valued immediate consequence operator, 3-C_{Π} , on an interpretation S of Π is a mapping defined as follows, where A ∈ AT M(Π):

3 − C_{Π} (A) =^{def} \{ \begin{matrix}True & if A is a fact or there is a rule \\ of the form & R_{1} ∧ ⋯ ∧ R_{k} ⇒ A \\ & such that S (R_{1} ∧ … ∧ R_{k}) = 1 \\ False & if there is no rule with A in its \\ head or, & for each & rule of the form \\ & R_{1} ∧ ⋯ ∧ R_{k} ⇒ A, S (R_{1} ∧ … ∧ R_{k}) = 0 \\ Unknown & otherwise. \end{matrix} The immediate consequence operator 3-C_{Π} has following property.

Theorem 1 Let Π be a 3-CAKE program. Then the sequence {(3-C_{Π} )^{i}(⊥)}_{i>0} is non-decreasing and converges to the least fixpoint of 3-C_{Π} .

Let Π be a CAKE program and let S be a 3-valued interpretation. We write 3-CS _{Π} (S ) to denote the least fixpoint of 3-C_{Π_{+}} , where Π_{+} is the positivized version of the ground instance of the program Π wrt S .

Example 2 (continued) We compute 3-CS _{Π} (⊥). 3- C_{Π_{+}} (⊥) = {P^{+} (a), S^{+} (a), ¬Q^{+} (a), ¬T^{+} (a), ¬U^{+} (a), ¬R^{+} (a)} (3- C_{Π_{+}} )^{2}(⊥) = {P^{+} (a), S^{+} (a), Q^{+} (a), ¬T^{+} (a), U^{+} (a), ¬R^{+} (a)} (3- C_{Π_{+}} )^{3}(⊥) = {P^{+} (a), S^{+} (a), Q^{+} (a), T^{+} (a), U^{+} (a), ¬R^{+} (a)} (3- C_{Π_{+}} )^{4}(⊥) = (3- C_{Π_{+}} )^{3}(⊥). Thus, 3-CS _{Π} (⊥) = {R^{+} (a), S^{+} (a), Q^{+} (a), T^{+} (a), U^{+} (a), ¬R^{+} (a)}.

Definition of well-founded semantics of a CAKE program.

Let Π be a ground CAKE program. We define the following sequence of interpretations:

S_{0} = ⊥
S_{i+1} = 3-CS _{Π} (S_{i}).

It can be shown that, for all i > 0,

S_{0} ≺ S_{2} … ≺ S_{2i} ≺ S_{2i+2} ≺ … ≺ S_{2i+1} ≺ S_{2i−1} ≺ … ≺ S_{1}.

The even subsequence is non-decreasing and the odd one is non-increasing. Since there are finitely many three-valued interpretations for a given program, each of those subsequences becomes constant at some point.

Let S_{∗} denote the limit of the subsequence {S_{2i}}_{i≥0} and let S^{∗} denote the limit of the subsequence {S_{2i+1} }_{i≥0}. A threevalued interpretation of P, denoted by S _{∗}^{∗}(A), is defined by

S _{∗}^{∗}(A) = \{ \begin{matrix}True & if S_{∗}(A) = S^{∗}(A) = 1 \\ False & if S_{∗}(A) = S^{∗}(A) = 0 \\ Unknown & otherwise \end{matrix}

The above interpretation is called the well-founded model of a program Π. The well-founded semantics assigns to a given CAKE program Π the well-founded model of Π.

Example 2 (continued) We now compute the well-founded model for the program Π.

S_{1} = 3-CS _{Π} (⊥) = {P^{+} (a), S^{+} (a), Q^{+} (a), T^{+} (a), U^{+} (a),
¬R^{+} (a)}
S_{2} = 3-CS _{Π} (S_{1}) = {P^{+} (a), Q^{+} (a), ¬R^{+} (a), ¬S^{+} (a),
¬T^{+} (a), ¬U^{+} (a)}
S_{3} = 3-CS _{Π} (S_{2}) = S_{1}
S_{4} = 3-CS _{Π} (S_{3}) = S_{2}.

S_{∗} = S_{4} = {P^{+} (a), Q^{+} (a), ¬R^{+} (a), ¬S^{+} (a), ¬T^{+} (a), ¬U^{+} (a)}

and

S^{∗} = S_{3} = {P^{+} (a), S^{+} (a), Q^{+} (a), T^{+} (a), U^{+} (a), ¬R^{+} (a)}. Thus, S _{∗}^{∗} = {P^{+} (a), Q^{+} (a), ¬R^{+} (a)}.