This edition is still being built. The reference list, the symbol glossary, the acronym list and the subject index are not published yet, so some links do not lead anywhere. The twelve chapters are complete.

Parametric Uniformity and Conditional Structures

1 Introduction

1.1 Overview and Structure

For a relational probabilistic conditional knowledge base the characteristic of being parametrically uniform is of advantage e.g. when making use of certain probabilistic entailment relations. It has been shown in [2] that every consistent probabilistic conditional knowledge base can be transformed into a parametrically uniform version.

Conditional Structures can be derived from such knowledge bases and are used e.g. to solve optimization problems when performing logical reasoning in relational probabilistic conditional frameworks.

The goal of this thesis is to investigate relationships between parametric uniformity (PU) and the Conditional Structure (CS) of a relational probabilistic conditional knowledge base. The main focus for this work was initially to find out if it can be read from a CS whether the related knowledge base is parametrically uniform. We will show that this is only possible for very specific cases of knowledge bases. Another objective was to find out the influence of the PU transformations of a knowledge base on the CS.

The generation of a CS has a high demand on computing resources as it involves processing of all possible worlds of the related knowledge base. This generation mechanism was found as extremely inefficient during the work on this thesis and therefore one of the initial side-goals was to find a more efficient way for CS generation. It became clear that such mechanisms were also useful for the investigation of the main objectives of the thesis.

After a summary of the theoretical background in chapter 2, section 3.1 introduces a set of functions or methods which will allow us to differentiate between the different types of relationships between PU and CS. We will narrow the focus to the following aspects:

  • how to either calculate or generate the CS of a knowledge base more efficiently than currently done; and
  • whether a transformation of a non-parametrically uniform knowledge base into its parametrically uniform version is possible on the level of the related conditional structures.

Already in sections 3.2 and 3.3 we will see that at least the transformation between the non-parametrically uniform knowledge base into the parametrically uniform version is not possible on the CS-level, at least not for cases of an imbalance with respect to usage of ground atoms. Due to this observation the focus of this thesis has been shifted more towards the investigation of efficient calculation and generation of conditional structures out of a given knowledge bases.

Due to the complexity of the generation of the CS of a relational probabilistic conditional knowledge base we will only look at a very specific subset of such knowledge bases, namely those which only involve atomic conditionals. Atomic conditionals only include a single predicate in the conclusion part and either none or at maximum one predicate in the antecedence part. They are defined in detail in chapter 4, along with several related concepts which are used in later parts of this thesis.

We further distinguish ca-conditionals, which are those atomic conditionals which have exactly one predicate in the antecedence and for which the conclusion predicate and the antecedence predicate are different. Whenever possible, we will first proof new findings for ca-conditionals and then generalize these findings to atomic conditionals.

The segmentation of possible worlds is another new concept introduced by this thesis in section 4.7. It allows us to split up possible worlds into c-segments, i.e. those partial possible worlds which are instantiations of the ground atoms of the conclusion predicate, and into a-segments, i.e. those of the antecedence predicate. For the a-segments we will further distinguish those which verify only one ground atom (the canonical a-segments) and those which verify several ground atoms (the composed a-segments).

In section 4.3 we introduce the concept of conditional contributions, which is the CS of a single atomic conditional. Chapters 4 to 8 will investigate how the conditional contribution of individual atomic conditionals can be either calculated or generated. In chapter 9 we will then show a way how the individual conditional contributions can be combined to the CS of the knowledge base they belong to. Unfortunately this combination process is only efficient under certain preconditions.

After the basic concepts have been introduced, chapter 5 shows how the conditional contribution of ca-conditionals can be constructed by counting only those vf-pairs which relate to canonical a-segments. The remaining vf-pairs of the conditional contribution, i.e. those vf-pairs of the composed a-segments, can then be calculated by summing up the counted vf-pairs of their respective canonical a-segments. The whole process is rather sophisticated when described in theory. In order to make the handling easier we will introduced reduced vf truth tables, which represent the achieved results in a way that makes it more approachable for the reader.

With these basic results we then can show in chapter 6 how the conditional contribution of certain atomic conditionals can be calculated. Unfortunately this mechanism does not work for all types of atomic conditionals and depends heavily on the the relation of the conclusion and the antecedence predicate as well as on the type of instantiation restrictions used. Nevertheless, given these side conditions the calculation is an extremely efficient mechanism to gain the conditional contribution without even looking into possible worlds.

In chapter 7 we will introduce the method of c-segment reduction, which can be regarded as the major result of this thesis. The method reduces more or less drastically the number of possible worlds which need to be investigated for the generation of the conditional contribution. Again, this method is first introduced for ca-conditionals, for which it works most efficiently. How efficiently it works depends on the types of instantiation restrictions of the conditional. In chapter 8 we will generalize this methods and apply it to all types of atomic conditionals. We will also discuss the efficiency and restrictions of this method in more detail.

Chapter 9 shows how conditional contributions can be combined to CSs. The combination works by first looking into two conditionals and their conditional contributions. The so-called common appearance table indicates which of the vf-pairs of these two conditional contributions appear commonly within one line of the final CS. For many types of conditionals these tables can be created without further effort.

Once we have constructed all common appearance tables we then can combine them to the CS by processing them one-by-one and looking at every commonly used vf-pair. This process however can turn out to be rather resource consuming and might in the end eat-up the efficiency gained by the results of the previous chapters. How extensive this process is depends on the number of conditionals, i.e. the size of the knowledge base. We were not able to run reliable tests on resource and time usage of this method.

The final chapters will focus on the interpretation and transformation of conditional structures.

In chapter 10 we will restrict our investigations to knowledge bases which are balanced with respect to the usage of ground atoms. This is necessary due to the findings in section 3.3 where it is shown that an imbalanced usage cannot be determined from a CS. Nevertheless, for atomic conditionals it seems possible, under certain circumstances, to determine from the CS whether the related atomic knowledge base holds a imbalanced sharing of ground atoms. In order to find such a imbalanced sharing we will look at certain patterns within the common antecedence tables of the related conditionals.

In chapter 11 the impact of the application of the parametric uniformity transformation rules on the CS will be investigated based on a simple example. Again we will assume that the related knowledge base is balanced with respect to the usage of ground atoms for the same reasons as outlined above. We will see that those vf-pairs which change due to the transformation are affected in a way which could be interpreted as a rule. Nevertheless, the conditions of the given example are far too restrictive to be applicable in general cases.

The thesis ends with a summary and discussion of the findings.

1.2 Definitions, Proofs and Assumptions

One of the challenges of this thesis was to find a terminology and notation that allow the transcription of the findings. Whilst the basic findings, such as the method of c-segment reduction, can be applied rather easily by using reduced vf truth tables, it was complicated to come up with formal approaches which enabled us to express the findings by means of definitions, propositions and proofs.

Chapters 4 and 5 are therefore groundwork where basic definitions and initial findings are introduced. The main propositions are then developed in chapters 6 and 7. Until the end of chapter 7 all propositions relating to ca-conditionals are proven and rest on related definitions. This already takes far more than half of the size of this thesis.

It did therefore not seem practical to further extend and modify the existing definitions in order to allow for formal notation and deduction of strict proofs for the findings of the later chapters of this thesis. The material in chapters 9, 10 and 11 is therefore more a rough outline of the related findings. Whenever we came across a general rule we stated it as an assumption rather than a proposition, in order to indicate the missing formalism in description and deduction.