Background

2.1 Probabilistic Conditional Knowledge Base

The framework for probabilistic conditionals with instantiation restrictions (PCI), as described in [4], provides different options for syntactical expressions of probabilistic knowledge bases. The option we will use as a base for this thesis is the firt order probabilistic conditional language (FOPCL), which is an extension of the probabilistic conditional logic to the relational case.

Let $\L$ be a quantifier-free first-order language defined over a many sorted first order signature $\Sigma = (Sort,Const,Pred)$ , where $Sort$ is a set of sorts, $Const$ is a finite set of constants, and $Pred$ is a set of predicates, each having a specific arity of the form $s_1 \times \cdots s_n \in Sort^n$ , indicating the required sorts for the arguments. Individual variables are used within the predicates, whereby each variable ranges over a unique sort $s\in Sort$ . The language $(\L|\L)^{prob}$ consists of FOPCL conditionals of the form $\R$ $= \big<~\big(~\phi~|~\psi~\big)[\rho],~\xi~\big>$ , where $\phi$ , $\psi$ $\in \L$ are first-order formulas, $\rho$ $\in [0..1]$ is a probability and $\xi$ is a set of instantiation restrictions, which are formulas of $\L$ using only the equality predicate. We call $\phi$ the conclusion and $\psi$ the antecedence of $\R$ . The set of all FOPCL conditionals is denoted by $\allR$ . A FOPCL knowledge base is a set of FOPCL conditionals and is denoted by $\kb$ .

In this thesis we will only make use of FOPCL knowledge bases and FOPCL conditionals and therefore will simply refer to them as knowledge bases and conditionals.

A ground instance is an instance of a conditional in which all variables in the conclusion and antecedence formulas are substituted with a dedicated set of elements of the sorts over which the respective variables are defined. An admissible ground instance of a conditional is a ground instance which is not restricted by a formula within the instantiation restrictions of the conditional. The grounding of a knowledge base is the set of all admissible ground instances which can be generated from a knowledge base. A ground atom is the instance of a predicate within a grounding of a knowledge base.

Example 1 (Grounding of a Knowledge Base)

Let $s_1 = \{~a,~b~\}$ and $s_2 = \{~x,~y~\}$ be two sorts, $C$ be a predicate with arity $s_1 \times s_2$ and $A$ be a predicate with arity $s_2 \times s_2$ .

Let $\R = \big<~\big(~C(V_1,V_2)~|~A(V_2,W_1)~\big)[0.42],~V_1 \neq b,~V_2 \neq W_1~\big>$ be a FOPCL conditional with $V_1$ being a variable over $s_1$ and $V_2, W_1$ being variables over $s_2$ . Let $\kb = \{~\R~\}$ be a knowledge base.

Then the admissible ground instances of $\R$ are

r_1 = \big<\big(C(a,x)|A(x,y)\big)\big>,

r_2 = \big<\big(C(a,y)|A(y,x)\big)\big>.

All other groundings are restricted by the instantiation restrictions of $\R$ , i.e. by either $V_1 \neq b$ or $V_2 \neq W_1$ or the mandated equality of the second variable in predicate $C$ and the first variable in predicate $A$ .

The grounding of $\kb$ is the set $\{~r_1,~r_2~\}$ .

The ground atoms of $\kb$ are $C(a,x),~C(a,y),~A(x,y)$ and $A(y,x)$ .

In this thesis we assume all knowledge bases to be consistent and therefore also each conditional to be self-consistent, i.e. for every conditional $R$ within a knowledge base $\kb$ there must exist at least one model $M$ for which it holds that $M \models R$ and $M \models \kb$ , whereby $\models$ is the propositional entailment function. Furthermore we only assume conditionals which have consistent constraint formulas, i.e. which are constraint-consistent. Finally we assume all conditionals to be in constraint normal form as defined by definition 1 in [2].

As this thesis focuses on conditional structures, it is not necessary to take into account the probabilities of conditionals. The next definition therefore allows us an easier notation.

Definition 1 (OP-Conditionals)

An op-conditional is a FOPCL conditional for which the assigned probability $\rho$ is omitted (e.g. in order to simplify notation).

Throughout this thesis we will only make use of op-conditionals. It is important that nevertheless all material in this paper is still based on FOPCL, although the related results are independent of probabilities. This paper does not investigate any applicability of the achieved results outside the PCI framework.

The following sets are defined in a similar way as in [2].

Definition 2 (Sets of Groundings and Ground Atoms)

Let $\kb$ be an FOPCL knowledge base, with $\R\in\kb$ a conditional and $P_1,\cdots, P_n$ being predicate symbols occurring in $\R$ .

$\gnd(R)$ is the set of admissible ground instances of a conditional $R$ - this set will also be called groundings of $R$ .¹

$\at(r) := \{~c_1,~\cdots,~c_n,~a_1,~\cdots,~a_m~~\}$ is the set of ground atoms occurring in a specific grounding $r$ of a conditional $\R$ .

$\at_R(P_1,\cdots,P_n) := \{~p_{1_1},~\cdots,~p_{1_k},\cdots,~p_{n_l}~\}$ is the set of ground atoms of predicate symbols $P_1,~\cdots,~P_n$ , whereby the ground atoms occur within the admissible ground instances of conditional $\R$ .

$\herbrand(\kb) := \bigcup_{\R\in\kb}~\bigcup_{r\in\gnd(\R)} \at(r)$ is the Herbrand base of the conditional knowledge base $\kb$ , i.e. the set of all ground atoms occurring in the admissible ground instances of conditionals in $\kb$ . We write $\herbrand(R_1)$ if the knowledge base consists only of a single conditional.

$|p|_{gnd(\R)} = \{~r~|~p\in\at(r),~r\in\gnd(\R)~\}$ is the grounding sum of ground atom $p$ , i.e. the number of groundings of conditional $R$ in which the grounded atom $p$ occurs.²

$|(p,q)|_{gnd(\R)} = \{~r~|~p\in\at(r),~ q\in\at(r),~r\in\gnd(r)~\}$ is the common grounding sum of ground atoms $p$ and $q$ , i.e. the number of groundings of conditional $R$ in which the grounded atoms $p$ and $q$ both occur.³

Example 2 (Sets of Groundings and Ground Atoms)

Let $R_1 = \big<\big(C(V) | A(W)\big), V \neq a\big>$ and $R_2 = \big<\big(C(V)\big)\big>$ be two atomic conditionals, with variable $V$ ranging over sort $s_1 = \{~a,~b~\}$ and variable $W$ ranging over sort $s_2 = \{~x,~y~ \}$ . Let $\kb = \{~R_1,~R_2~\}$ .

Then we get:

$\gnd(R_1) = \{~\big<~\big(C(b)|A(x)\big)~\big>,~\big<~\big(C(b)|A(y)\big)~\big>~\}$ ;
$\gnd(R_2) = \{~\big<~\big(C(a)\big)~\big>,~\big<~\big(C(b)\big)~\big>~\}$ ;
$\herbrand(\kb) = \{~C(a),~C(b),~A(x),~A(y)~\}$ ;
$\at(A) = \{~A(x),~A(y)~\}$ ;
$\at(C) = \{~C(a),~C(b)~\}$ ;
$\at_{\R_1}(C) = \{~C(b)~\}$ ;
$\at_{\R_1}(A) = \{~A(x),~A(y)~\}$ ;
$\at_{\R_2}(C) = \{~C(a),~C(b)~\}$ ;
$\at_{\R_2}(A) = \emptyset$ ;
$\at(\big<\big(~C(b)~|~A(x)~\big>\big) = \{~C(b),~A(x)~\}$ ;
$|C(a)|_{\gnd(\R_1)} = 0$ , $|C(b)|_{\gnd(\R_1)} = 2$ ;
$|A(x)|_{\gnd(\R_1)} = 1$ , $|A(y)|_{\gnd(\R_1)} = 1$ ;
$|C(a)|_{\gnd(\R_2)} = 1$ , $|C(b)|_{\gnd(\R_2)} = 1$ ;
$|A(x)|_{\gnd(\R_2)} = 0$ , $|A(y)|_{\gnd(\R_2)} = 0$ ;
$|(C(b), A(y))|_{\gnd{\R_1}} = 1$ .

2.2 Parametric Uniformity

In this section we give an introduction to the semantical concepts which require a knowledge base to be parametrically uniform. We then look at the balanced criteria, which allows us to determine on a syntactical level whether a knowledge base is parametrically uniform. We will furthermore describe how on the level of conditionals any knowledge base can be transformed so that it becomes parametrically uniform. All this will be done in a very brief way and it is assumed that the reader is familiar with the related concepts. The material offered here is mostly a summary from [2]. Only those propositions from [2] which are essential to understand the material in this paper have been repeated.

There are different ways to interpret and model probabilistic knowledge bases on the semantical level. One of the goals is usually to find a probability distribution which fits the conditional probabilities. Logical reasoning is then done based on such a probability distribution. Usually there is not only one, but many probability distributions which fit the conditional probabilities of a knowledge base. One very successful way to do so is the maximum entropy model as e.g. defined in [10] and [8]. The maximum entropy model is optimal in the sense that it is the most unbiased one.

In order to compute the maximum entropy model, a transformed version of the Gibbs distribution (as described in [9]) has proven to be most effective, which requires a knowledge base to have the property of parametric uniformity as described in [2].

Definition 3 (Parametric Uniformity Function)

Let $\kb$ be an knowledge base.

It is $\isPU(\kb)$ the function which indicates whether the FOPCL knowledge base $\kb$ is parametrically uniform.

Parametric uniformity can also be investigated on a pure syntactical level. For this, the concepts of balanced sharing and balanced usage of ground atoms is used.

Definition 4 (Imbalanced Sharing (from [2]))

Let $R_1, R_2 \in \kb$ be two different conditionals, and let $P_{R_1} \in at(R_1)$ and $P_{R_2} \in at(R_2)$ .

There is an imbalanced sharing of ground atoms by $R_1$ and $R_2$ (with respect to $P_{R_1}$ and $P_{R_2}$ ), iff $at_{R_1}(P_{R_1}) \cap at_{R_2}(P_{R_2}) \neq \emptyset$ and $at_{R_1}(P_{R_1}) \neq at_{R_2}(P_{R_2})$ .
Let $Q_{R_1} \in at(R_1)$ and $Q_{R_2} \in at(R_2)$ be atoms different from $P_{R_1}$ and $P_{R_2}$ , respectively. There is an imbalanced sharing of combinations of ground atoms by $R_1$ and $R_2$ (with respect to $P_{R_1}, Q_{R_1}$ and $P_{R_2},Q_{R_2}$ ) iff $at_{R_1}(P_{R_1}, Q_{R_1}) \cap at_{R_2}(P_{R_2}, Q_{R_2}) \neq \emptyset$ and $\at_{R_1}(P_{R_1}, Q_{R_1}) \neq \at_{R_2}(P_{R_2}, Q_{R_2})$ .
There is an imbalanced sharing in $\kb$ iff there are conditionals in $\kb$ such that (1) or (2) is the case.

Definition 5 (Imbalanced Use (from [2]))

Let $R \in \kb$ and $P_R \in at(R)$ .

There is an imbalanced use of ground atoms by $R$ (with respect to $P_R$ ) iff there are $p, p' \in \at_R(P)$ such that $|p|_{gnd(R)} < |p'|_{gnd(R)}$ .
Let ${Q_R \in at(R)}$ be different from $P_R$ . There is an imbalanced use of combinations of ground atoms by $R$ (with respect to $P_R$ and $Q_R$ ) iff there are ${p, p' \in \at_R(P)}$ and ${q,q' \in \at_R(Q)}$ , such that ${|(p,q)|_{gnd(R)} < |(p',q')|_{gnd(R)}}$ .
There is an imbalanced use in in $\kb$ iff there is a conditional in $R$ such that (1) or (2) is the case.

Definition 6 (Balanced and imbalanced knowledge base (from [2]))

$\kb$ is imbalanced iff there is an imbalanced sharing or an imbalanced use in $\kb$ , otherwise $\kb$ is balanced.

Example 3 (Imbalanced Sharing)

Continuing from example 2.

There is an imbalanced sharing between $R_1$ and $R_2$ , as $at_{R_1}(C) \cap at_{R_2}(C) \neq \emptyset$ and $at_{R_1}(C) \neq at_{R_2}(C)$ .

There is no imbalanced usage within $\R_1$ or $\R_2$ .

As there are conditionals which are not balanced it follows that $\kb$ is not balanced.

Definition 7 (Balanced Functions)

Let $\kb$ be an knowledge base. Let $\R_1, \R_2\in\kb$ .

Then

$\isBU(\kb)$ is the function which indicates whether the FOPCL knowledge base $\kb$ is balanced with respect to the usage of ground atoms;
$\isBU(\R_1,\cdots,\R_n)$ is the function which indicates whether the set of conditionals $\R_1,\cdots,\R_n$ is balanced with respect to the usage of ground atoms;
$\isBS(\kb)$ is the function which indicates, whether the FOPCL knowledge base $\kb$ is balanced with respect to the sharing of ground atoms; and
$\isBS(\R_1,\cdots,\R_n)$ is the function which indicates, whether the set of conditionals $\R_1,\cdots,\Re_n$ is balanced with respect to the sharing of ground atoms.

We usually write $\isBU(\R)$ instead of $\isBU(\R)=true$ and $\neg\isBU(\R)$ instead of ${\isBU(\R)=false}$

Example 4 (Balanced Functions)

Continuing from example 3.

We get $\isBU(\R_1)$ , $\isBU(\R_2)$ and $\neg\isBS(\R_1,R_2)$ and therefore it holds that $\isBU(\kb)$ and $\neg\isBS(\kb)$ .

Proposition 4 in [2] states that a knowledge base is parametrically uniform iff it is balanced. Based on this a set of transformation rules is derived in [2], which remove all imbalances from a given consistent knowledge base. With these rules, any given consistent knowledge base $\kb$ can be transformed into a parametrically uniform version of $\kb$ . The set of transformation rules is shown in table 2.1, whereby $\nu$ indicates the constraint normal form operator, which is also defined in [2], but will not further be explained here.

Definition 8 (Parametric Uniformity Function (from [2]))

Let $\kb$ be an knowledge base.

Then $\PU(\kb)$ is the parametrically uniform version of knowledge base $\kb$ after all applicably transformation rules as shown in table 2.1 have been exhaustively applied to $\kb$ .

$(TE_1)$	$\frac{\R \cup \{R_1, R_2\}}{\R \cup \{R_1\} \cup \nu\{\sigma(R_2), \bar{\sigma}(R_2) \}}$	$R_1 \leftarrow \big<P\big>_{V,c}\rightarrow R_2, \sigma=\{V/c\}$
$(TE_2)$	$\frac{\R \cup \{R_1, R_2\}}{\R \cup \{R_1\} \cup \nu\{\sigma(R_2), \bar{\sigma}(R_2) \}}$	$R_1 \leftarrow \big<P\big>_{V,Z}\rightarrow R_2, \sigma=\{V/Z\}$
$(TE_3)$	$\frac{\R \cup \{R_1, R_2\}}{\R \cup \{R_1\} \cup \nu\{\sigma(R_2), \bar{\sigma}(R_2) \}}$	$R_1 \leftarrow \big<P,Q\big>_{V,Z}\rightarrow R_2, \sigma=\{V/Z\}$
$~$
$(TA_1)$	$\frac{\R \cup \{R\}}{\R \nu\{\sigma(R), \bar{\sigma}(R) \}}$	$\big<Q\big>_{V,c} \rightarrow R, \sigma=\{V/c\}$
$(TA_2)$	$\frac{\R \cup \{R\}}{\R \nu\{\sigma(R), \bar{\sigma}(R) \}}$	$\big<Q\big>_{V,Z} \rightarrow R, \sigma=\{V/Z\}$
$(TA_1)$	$\frac{\R \cup \{R\}}{\R \nu\{\sigma(R), \bar{\sigma}(R) \}}$	$\big<Q,S\big>_{V,Z} \rightarrow R, \sigma=\{V/Z\}$

Transformation rules $\PU$ yielding parametric uniformity.

Figure 2.1 Transformation rules

\mathcal {PU}

yielding parametric uniformity.

Example 5 (Transformation Rules)

Continuing from example 4.

We make use of the transformation rules to resolve the imbalanced sharing and therefore replace $R_2$ with the two atomic conditionals ${R_{2-1} = \big<~\big(C(V)\big),~V\neq a~\big>}$ and ${R_{2-2} = \big<~\big(C((a)\big)~\big>}$ .

Then we have

$\gnd(\R_{2-1}) = \{~\big<c(b)\big>~\}$ ;
$\gnd(\R_{2-2}) = \{~\big<c(a)\big>~\}$ ;
$\at_{\R_{2-1}}(C) = \{~c(b)~\}$
$\at_{\R_{2-2}}(C) = \{~c(a)~\}$

The knowledge base ${\kb' = \{\R_1, \R_{2-1}, \R_{2-2}\}}$ is balanced with respect to sharing as ${at_{\R_1}(C) = at_{\R_{2-1}}(C)}$ and ${at_{R_1}(C) \cap at_{R_{2-2}}(C) = \emptyset}$ and ${at_{R_{2-1}}(C) \cap at_{R_{2-2}}(C) = \emptyset}$ and $at_{R_1}(A)$ also does not share any atoms with the other sets.

2.3 Conditional Structure

In this section we will show how the conditional structure (CS) of a knowledge base can be derived from the ground atoms of its conditionals. We will therefore treat the ground atoms as truth variables which form the base for a set of possible worlds. Within each world we will count for every conditional the verified and falsified ground atoms and combine these two numbers to a vf-pair. The vf-pairs of all conditionals for a specific possible world is then called the conditional impact and the set of all conditional impacts is the CS.

In the upcoming chapters we will need to create subsets of certain types of ground atoms and will therefore need quite some flexibility in the derivation of possible worlds. The first definition in this section therefore defines a possible world in a very generic way.

Definition 9 (Possible Worlds)

Let $\{~ga_1,~\cdots,~ga_n~\}$ be a set of ground atoms. Let $\kb$ be a FOPCL knowledge base.

Then a possible world $\omega$ is a specific assignment of truth values to a n-tuple of ground atoms.

The set of all possible worlds which can be derived from the ground atoms ${ga_1,~\cdots,~ga_n}$ is denoted by $\Omega(\{~ga_1,\cdots,ga_n~\})$ .

The set of all possible worlds which can be derived from the conditionals of a knowledge base $\kb$ is denoted by $\Omega(\kb) := \Omega(\herbrand(\kb))$ .

Note that we will use the term "derived" in order to express how the possible worlds are generated by assigning all possible combinations of truth values to the ground atoms of a knowledge base.

We will say that $\omega$ is a possible world of $\kb$ or $\R$ if $\omega$ is derived from the ground of atoms of the knowledge base $\kb$ or the conditional $\R$ respectively.

The following example will also introduce two styles of notation for possible worlds.

Example 6 (Possible Worlds)

Continuing from example 5.

Table 2.1 shows all possible worlds generated by the groundings of $R_1$ as well as $R_2$ and $R_1$ , $R_{2-1}$ and $R_{2-2}$ .

Table 2.1
$\Omega(\kb)$	$c(a)$	$c(b)$	$a(x)$	$a(y)$
$\omega_{0}$	$0$	$0$	$0$	$0$
$\omega_{1}$	$0$	$0$	$0$	$1$
$\omega_{2}$	$0$	$0$	$1$	$0$
$\omega_{3}$	$0$	$0$	$1$	$1$
$\omega_{4}$	$0$	$1$	$0$	$0$
$\omega_{5}$	$0$	$1$	$0$	$1$
$\omega_{6}$	$0$	$1$	$1$	$0$
$\omega_{7}$	$0$	$1$	$1$	$1$
$\omega_{8}$	$1$	$0$	$0$	$0$
$\omega_{9}$	$1$	$0$	$0$	$1$
$\omega_{10}$	$1$	$0$	$1$	$0$
$\omega_{11}$	$1$	$0$	$1$	$1$
$\omega_{12}$	$1$	$1$	$0$	$0$
$\omega_{13}$	$1$	$1$	$0$	$1$
$\omega_{14}$	$1$	$1$	$1$	$0$
$\omega_{15}$	$1$	$1$	$1$	$1$

Table 2.1: Truth Table of Example 6

It follows that $\Omega(\kb) = \{ \omega_0, \cdots, \omega_{15} \}$ .

We can denote specific possible worlds in two different styles, i.e. we can either write the content of $\omega_2$ as ${\omega_2 = \{~0010~\}}$ , which in most cases is sufficient, or we can write ${\omega_2=\{~c(a)=0,~c(b)=0,~a(x)=1,~a(y)=0~\}}$

The following is a different formulation of the related definition given [5]. ⁴

Definition 10 (vf-Pair, Counting Functions)

Let $\R_i \in \kb$ be an conditional with $\R_i = \big<~(~\phi~|~\psi~),~\xi~\big>$ and $\omega_j \in \Omega(\kba)$ and $\phi, \psi\in\L$ .

Then

$\verij := \big|\{~\big<(c|a)\big>\in\gnd(\R_i)~|~\omega_j \models c \wedge a~\}\big|$ is the counting function which counts the number of ground instances of conditional $R_i$ of which the related ground atoms are verified by a possible world $\omega_j$ ;
$\falij := \big|\{~\big<(c|a)\big>\in\gnd(\R_i)~|~\omega_j \models \neg c \wedge a~\}\big|$ is the counting function which counts the number of ground instances of conditional $R_i$ for which the related ground atoms in the conclusion are falsified by possible world $\omega_j$ and the related ground atoms in the antecedence are verified by a possible world $\omega_j$ ;
$\vf_{i,j} = \vf_{\R_i}(\omega_j) := (\verij, \falij)$ , is a vf-pair, i.e. the tuple consisting of the numbers counted by the counting functions; and
$\VF$ is the set of all $\vf$ -pairs.

In section 4.8 we will introduce alternative counting functions which are defined based on the different influence of conclusion and antecedence ground atoms. Due to this we will refer to the above defined functions also as traditional counting functions.

Within the following example we will informally define the vf truth table. Note that the definition of the table is not fixed, i.e. we will sometimes modify this (or other) tables in order to underline certain aspects of the individual example cases.

Example 7 (vf-Pairs)

Continuing from example 6.

Table 2.2 shows the vf truth table of $\kb$ and $\kb'$ , i.e. it lists all $vf$ -pairs which are generated by the conditionals of $\kb$ and $\kb'$ .

Table 2.2
$\Omega(\kb)$	$c(a)$	$c(b)$	$a(x)$	$a(y)$	$R_1$	$R_2$	$R_{2-1}$	$R_{2-2}$
$\omega_{0}$	$0$	$0$	$0$	$0$	$(0,0)$	$(0,2)$	$(0,1)$	$(0,1)$
$\omega_{1}$	$0$	$0$	$0$	$1$	$(0,1)$	$(0,2)$	$(0,1)$	$(0,1)$
$\omega_{2}$	$0$	$0$	$1$	$0$	$(0,1)$	$(0,2)$	$(0,1)$	$(0,1)$
$\omega_{3}$	$0$	$0$	$1$	$1$	$(0,2)$	$(0,2)$	$(0,1)$	$(0,1)$

$\omega_{4}$	$0$	$1$	$0$	$0$	$(0,0)$	$(1,1)$	$(1,0)$	$(0,1)$
$\omega_{5}$	$0$	$1$	$0$	$1$	$(1,0)$	$(1,1)$	$(1,0)$	$(0,1)$
$\omega_{6}$	$0$	$1$	$1$	$0$	$(1,0)$	$(1,1)$	$(1,0)$	$(0,1)$
$\omega_{7}$	$0$	$1$	$1$	$1$	$(2,0)$	$(1,1)$	$(1,0)$	$(0,1)$

$\omega_{8}$	$1$	$0$	$0$	$0$	$(0,0)$	$(1,1)$	$(0,1)$	$(1,0)$
$\omega_{9}$	$1$	$0$	$0$	$1$	$(0,1)$	$(1,1)$	$(0,1)$	$(1,0)$
$\omega_{10}$	$1$	$0$	$1$	$0$	$(0,1)$	$(1,1)$	$(0,1)$	$(1,0)$
$\omega_{11}$	$1$	$0$	$1$	$1$	$(0,2)$	$(1,1)$	$(0,1)$	$(1,0)$

$\omega_{12}$	$1$	$1$	$0$	$0$	$(0,0)$	$(2,0)$	$(1,0)$	$(1,0)$
$\omega_{13}$	$1$	$1$	$0$	$1$	$(1,0)$	$(2,0)$	$(1,0)$	$(1,0)$
$\omega_{14}$	$1$	$1$	$1$	$0$	$(1,0)$	$(2,0)$	$(1,0)$	$(1,0)$
$\omega_{15}$	$1$	$1$	$1$	$1$	$(2,0)$	$(2,0)$	$(1,0)$	$(1,0)$

Table 2.2: vf Truth Table of Example 7

The lines in a vf truth table indicate all vf-pairs which the conditionals of a FOPCL knowledge base generate for a specific possible world. The following definition introduces these sets of vf-pairs as conditional impacts.

Definition 11 (Conditional Impact (from [7]))

Let $\kb$ be an FOPCL knowledge base and let $\omega \in \Omega(\kb)$ be a possible world..

Then the conditional impact of possible world $\omega$ is defined as

\gammaci(\omega) := \{~\vf_{R}(\omega)~|~R \in \kb ~\text{\it and} ~0 \leq i \leq |\kb|~\}

the set of vf-pairs generated by possible world $\omega$ for all atomic conditional $R \in \kb$ .

Example 8 (Conditional Impact)

Continuing from example 7.

The conditional impacts of the different possible worlds $\omega_i \in \Omega$ can be read from the vf truth table in table 2.2.

For example the conditional impact of $\omega_1$ for $\kb$ is $\gammaci(\omega_1) = (~(0,1), (0,2)~)$ and for $\kb'$ it is $\gammaci(\omega_1) = (~(0,1), (0,1), (0,1)~)$ .

The conditional structure of a knowledge base is now defined as the set of the conditional impacts over all possible worlds of the knowledge base.

Definition 12 (Conditional Structure ( $\gamma _{tab}$ ) (from [5]))

Let $\kb$ be a knowledge base.

Then the conditional structure (CS) of $\kb$ is the set of all conditional impacts of knowledge base $\kb$ , i.e.

\gfull := \bigcup_{\omega\in\Omega(\kb)} \gammaci(\omega).

The set of all conditional structures is denoted by $\allCS$ .

In order to construct the CS of a knowledge base we need to collect all conditional impacts of all possible worlds which can be derived from that knowledge base. We therefore need the complete vf truth table of the knowledge base, including all possible worlds and all conditionals. This thesis will investigate some alternative ways to generate the CS of a knowledge base, which is why we called the function in definition 12 $\gfull$ , i.e. to show that it is makes use of the vf truth table to construct the CS.

The following definition introduces a general notation for CSs, regardless of which method was used to construct them.

Definition 13 (Conditional Structure ( $\gamma$ ))

Let $\kb$ be a knowledge base.

We denote the conditional structure of $\kb$ as $\gamma(\kb)$ .

So basically we will refer to the CS as $\gamma(\kb)$ and only in cases when it is necessary to mention a specific construction mechanism we will use a different notation, e.g. we will denote the CS as $\gfull(\kb)$ if it is relevant that it was created as defined by definition 12.

Example 9 (Conditional Structure)

Continuing from example 8.

The CSs of $\kb$ and $\kb'$ can be read from the vf truth table as shown in table 2.2.

$\gamma(\kb) = \gfull(\kb)$	$= \{$	$(~(0,0),~(0,2)~),$	$(~(0,0),~(1,1)~),$	$(~(0,0),~(2,0)~),$
		$(~(0,1),~(0,2)~),$	$(~(0,1),~(1,1)~),$
		$(~(1,0),~(1,1)~),$	$(~(1,0),~(2,0)~),$
		$(~(0,2),~(0,2)~),$	$(~(0,2),~(1,1)~),$
		$(~(2,0),~(1,1)~),$	$(~(2,0),~(2,0)~)$		$\}$

$\gamma(\kb) = \gfull(\kb')$	$= \{$	$(~(0,0),~(0,1),~(0,1)~),$	$(~(0,0),~(0,1),~(1,0)~),$
		$(~(0,0),~(1,0),~(0,1)~),$	$(~(0,0),~(1,0),~(1,0)~),$
		$(~(0,1),~(0,1),~(0,1)~),$	$(~(0,1),~(0,1),~(1,0)~),$
		$(~(1,0),~(1,0),~(0,1)~),$	$(~(1,0),~(1,0),~(1,0)~),$
		$(~(0,2),~(0,1),~(0,1)~),$	$(~(0,2),~(0,1),~(1,0)~),$
		$(~(2,0),~(1,0),~(0,1)~),$	$(~(2,0),~(1,0),~(1,0)~)$	$\}$

Definition 14 (Common Method)

Let $\kb$ be a FOPCL knowledge base.

Then the method by which the CS of $\kb$ is determined by applying the function $\gfull$ is called the common method.

Note that all the CSs of all examples in this thesis have been constructed with the common method. We will see several examples in later chapters, where different methods are used, nevertheless for all these examples we also used the common method to check for the correctness of the results.

One of the main applications of CSs is for the generalized interactive scaling (GIS) which is used to apply maximum entropy reasoning under the so-called aggregation semantics. GIS is defined in [3] and [5]. GIS does not make directly use of the CS, but of the equivalence classes (EC) of possible worlds, i.e. the set of all possible worlds which generate the same conditional impact.

Definition 15 (Equivalence Classes of Possible Worlds (from [5]))

Let $\kb$ be a FOPCL knowledge base. Let $\omega\in\Omega(\kb)$ be a possible world.

Then the equivalence class of possible world $\omega$ is defined as

\omegaEC := \{~\omega'~|~\gamma(\omega) = \gamma(\omega'),~\omega'\in\Omega(\kb)~\}.

The the equivalence classes of possible worlds of $\kb$ is defined as

\OmegaEC := \bigcup\limits_{\omega\in\Omega(\kb)} \omegaEC.

Example 10 (Equivalence Classes of Possible Worlds)

Continuing from example 7.

We can read the equivalence classes of possible worlds of $\kb$ from the vf truth table in table 2.2, so that we have

$\omega_{0_{/\equiv}}$	$=$	$\{~\omega_0~\}$	$~~~~~~~~$	$\omega_{1_{/\equiv}}$	$=$	$\{~\omega_1,~\omega_2~\}$
$\omega_{3_{/\equiv}}$	$=$	$\{~\omega_3~\}$		$\omega_{4_{/\equiv}}$	$=$	$\{~\omega_4,~\omega_8~\}$
$\omega_{5_{/\equiv}}$	$=$	$\{~\omega_5,~\omega_6~\}$		$\omega_{7_{/\equiv}}$	$=$	$\{~\omega_7~\}$
$\omega_{9_{/\equiv}}$	$=$	$\{~\omega_9,~\omega_{10}$		$\omega_{11_{/\equiv}}$	$=$	$\{~\omega_11~\}$
$\omega_{12_{/\equiv}}$	$=$	$\{~\omega_{12}~\}$		$\omega_{13_{/\equiv}}$	$=$	$\{~\omega_{13},~\omega_{14}~\}$
$\omega_{15_{/\equiv}}$	$=$	$\{~\omega_{15}~\}.$

2.4 Related Work

In this section we give a brief summary of the material used for this paper and how within them the ideas of parametric uniformity and conditional structures were developed.

[10] introduces the concept of CS for a probabilistic conditional logic (PCL), based on propositional logic;
[10] describes a probabilistic conditional logic semantics based on the principle of maximum entropy (ME);
[8] extends the probabilistic conditional logic to the relational case, i.e. it describes an approach for a first-order probabilistic logic (FOPCL), which makes use of ME based semantics;
[11] introduces aggregation semantics (AGG) as an alternative approach to a first-order probabilistic logic which also employs an ME based semantics;
[4] extends AGG with the concept of instantiation restrictions (AGG-IR) and embeds both the AGG-IR approach as well as the FOPCL approach in the probabilistic conditionals with instantiation restrictions (PCI) framework;
[2] shows the importance of the property of parametric uniformity (PU) and introduces a mechanism to transform a FOPCL knowledge base into a parametrically uniform knowledge base (which was shown in section 2.2);
[4] introduces the proposition that if a knowledge base $\kb$ is parametrically uniform, then the two probability distributions $P_{\kb}^{AGG}$ and $P_{\kb}^{FOPCL}$ are identical (this proposition has not been proved);
[3] employs the generalized interactive scaling (GIS) algorithm in order to solve the optimization problem for the ME-distribution for aggregation semantics, the GIS thereby takes into account all possible worlds $\omega$ of the related knowledge base;
[5] introduces the concept of a vf-pair, which is the base for conditional structures in the relational case;
[5] as well introduces the concept of equivalence classes of possible worlds $[\omega_{/\equiv}]$ , based on identical CSs;
[5] finally shows how equivalence classes of possible worlds can be used to make the GIS algorithm more efficient for the purpose of ME interference;
[6] introduces (based on vf-pairs and CS) the concept of the weighted conditional impact (WCI) and employs it to make the GIS algorithm even more efficient;
[7] introduces the concept of the conditional impact (CI).

In addition to the above listed material we extensively used the integrated development environment for relational probabilistic logic KReator, which is e.g. capable of transforming a FOPCL knowledge base into its parametrically uniform version, as described in [1].⁵

Notes

see definition of $\gnd(\R)$ in [2].

see definition of $|p|^R_{\gnd(\R)}$ in [2].

see definition of $|\big<p,q\big>|^R_{\gnd(\R)}$ in [2].

In [5] we $\ver$ is defined as follows:

\ver_i(\omega):=\big|\big\{~{\boldsymbol{a}}_i\in\mathcal{H}^{\boldsymbol{x}(A_i,B_i)}~|~\omega\models A_i(\boldsymbol{a})B_i(\boldsymbol{a})~\}\big|

Though the notation is significantly different from the one chosen in definition 10 they both encompass the same sets. We will not detail how the notation of [5] and the notation chosen for this thesis can be transformed into each other in order to avoid introducing all symbols and terminology which [5] uses. It is believed that the readers who are familiar with [5] can see the equivalence.

Source code of KReator can be found at http://kreator-ide.sourceforge.net/.