4.2 Semantics

Now that we have completely detailed the syntax of the probabilistic features of -MIRTL, we may switch to discussing its semantics (a semantics that will follow the guidelines of Halpern's logic [4]). As previously hinted, a denotational semantics for a logical language is obtained by postulating the existence of a number of ``ways the world could be''; these are usually called interpretations. In our case, these will exactly be the ``interpretations'' of MIRTL as defined and characterised in Definitions 15 of [8]. Such interpretations consist of mappings of individual constants into individuals of the domain, and of predicate symbols into relations on the domain, that are ``well-behaved'' with respect to the intuitive meaning of the operators of the language (i.e. the term-forming operators, the assertion operator ``[ ]'' and the axiom operators ``'' and ``''.).

In order to give semantics to the probabilistic features of -MIRTL, we will adopt a version of ``possible world semantics'' (PWS); as in all versions of PWS, we will see the set of interpretations as partitioned into structures, that we will call PTL structures. A PTL structure is a 4-uple , where is a nonempty set of individuals, is a set of MIRTL interpretations on , is a discrete probability distribution on the domain , and is a discrete probability distribution on the set of interpretations.

The notion of extension of a probabilistic term in an interpretation of , written , and the notion of truth of a formula in an interpretation of , written , are defined, in a mutually recursive way (this is obvious, given that the syntax of probabilistic terms and formulae is also mutually recursively defined), by means of the following clauses:

We will now comment on the meaning of each of these clauses and then give a comprehensive example of their use. Clause 1 simply states that the extension of a rational constant is always (i.e. in any interpretation of any PTL structure ) the rational number it obviously represents (e.g. the constants , and all represent the number 0.25). Analogously, Clause 5 states that the extension of a term is always obtained by the application of the real-valued operation mathop which the symbol ``'' obviously represents (e.g. the ``+'' symbol representing addition), to the extensions of the two terms involved; similar considerations apply to Clause 8.

Probabilities come in with Clause 2: in order to compute the extension, at a given interpretation of , of the probability that a randomly picked be a , we first check what individuals belong to the interpretation of under , and then sum up the probabilities that the distribution attributes to them. The case of Clause 3 is completely analogous, the only difference being that pairs of individuals (and, consequently, the product of their probabilities) have to be considered instead of single individuals.

Things are quite different with Clause 4; this clause aims to specify the semantics of formulae involving the system's degrees of belief, so a reference must be made to the interpretations that the system ``believes in principle possible'' and to their respective probabilities. In order to compute the system's degree of belief in a formula, we first check what are the interpretations in which that formula is true, and then sum up the probabilities that the distribution attributes to them.

Finally, things are quite simple for Clauses 6 and 7; MIRTL assertions and axioms are true in an interpretation just if they are satisfied by in the sense of Definitions 2 and 3 of [8].

Let us now work out a simple example in order to see how all this works.

Similarly to what happens in all applications of logical reasoning, we are hardly interested in what is the truth value of a given formula, or the extension of a given term, at a particular interpretation ; loosely speaking, we cannot know which interpretation is the correct one, i.e. the one that corresponds to the ``real world'', since we always have partial (and often erroneous) knowledge about the real world (in our case: about the documents in our collection and about what they are about), and much of what is true in the real world is unknown to us. Because of this, we are rather interested in what is the truth value of a given formula, or the extension of a given term, at all those interpretations that are ``consistent'' with our partial and erroneous knowledge about the world; this corresponds to the logical process of inferring those formulae whose truth is a consequence of the truth of the formulae that constitute our knowledge about the world. As in all other logics, in -MIRTL this is formalised by the notion of validity in a theory.

Note that the above observations on partial and erroneous knowledge apply to probability distributions too. By relying on the notion of validity in a theory , we free ourselves from the problem of knowing, in all details, which probability distribution on the domain (resp. on possible worlds) is the correct one. This is reasonable, as we could not hope to know the truth value of every (probabilistic) formula expressible in our language: also our probabilistic knowledge is partial, and often erroneous too! A set of formulae does not specify a probability distribution in full detail, but has the effect of putting a number of constraints on how probability distributions ``consistent'' with should be; these constraints identify a whole family of distributions, and the formulae valid in are exactly those formulae that are true in all the interpretations characterised by these distributions.

An interesting side-effect of introducing the notion of probability distribution into the semantics of our logic is that our logic will obey the familiar laws of the probability calculus; this will be true both for formulae representing information about degrees of belief, and for formulae representing statistical information. For example, Bayes' Theorem is valid in our logic, i.e. all formulae of type

or of type

will be valid in any theory , as can easily be seen by applying our definition of conditional probability.

According to the model of IR that we are proposing in this paper, a document is then deemed to be relevant to an information need with probability , with a real number, iff the formula is valid in , where is the (consequential closure of) the set of formulae representing the documents in the collection and the lexical, ``thesaural'' knowledge of the system.