Application of aboutness to functional benchmarking in information retrieval.
Experimental approaches are widely employed to benchmark the performance of an information retrieval (IR) system. Measurements in terms of recall and precision are computed as performance indicators. Although they are good at assessing the retrieval effectiveness of an IR system, they fail to explore deeper aspects such as its underlying functionality and explain why the system shows such performance. Recently, inductive (i.e., theoretical) evaluation of IR systems has been proposed to circumvent the controversies of the experimental methods. Several studies have adopted the inductive approach, but they mostly focus on theoretical modeling of IR properties by using some metalogic. In this article, we propose to use inductive evaluation for functional benchmarking of IR models as a complement of the traditional experiment-based performance benchmarking. We define a functional benchmark suite in two stages: the evaluation criteria based on the notion of "aboutness," and the formal evaluation methodology using the criteria. The proposed benchmark has been successfully applied to evaluate various well-known classical and logic-based IR models. The functional benchmarking results allow us to compare and analyze the functionality of the different IR models.
Summary

In summary, the probabilistic model has the highest degree of potential precision,
followed by the threshold vector space model, then the Boolean model and the nave
vector space model. This conclusion is consistent with the experimental results. The
motivation for this judgment lies in the varying degrees to which they respectively
support (or don't support) conservative monotonicity.
4. Inductive Evaluation of Logical IR Models
In the past decade, a number of logic based IR models have been proposed (see
[Bruza and Lalmas 1996; Lalmas 1998; Lalmas and Bruza 1998] for detailed
surveys). These models can be generally classified into three types: Situation Theory
based, Possible World based, and other types. In what follows, we investigate three
well-known logic IR models.
In the following analyses, the fact of a document D consisting of information
~
carrier i is represented by Dfi i. For example, Guarded Left Compositional
Monotonicity (i.e., postulate 7) means that if a document consisting of i is about k (i.e.
under the guarded condition that i doesn't preclude j (i ^/ j), we can conclude
that a document consisting of i j is about k (i j |= k). In the following
benchmarking exercise, we adopt this interpretation for logical IR models for reasons
of simplicity. For the classical models, we treated the document and the query as
information carriers directly, for there are no term semantic relationships involved in
classical models.
4.1 Situation theory based model
4.1.1 Background
Rijsbergen and Lalmas developed a situation theory based model [Lalmas 1996;
Rijsbergen and Lalmas 1996]. In their model, a document and the information it
contains are modeled as a situation and types. A situation s supports the type j,
denoted by s|=j, means that j is a part of the information content of the situation.
The flow of information is modeled by constraints (fi ). Here, we assume jfi j. A
query is one type (single type query) or a set of types (complex query), e.g., a query f
For a situation s and a set of types f, there are two methods to determine whether d
supports f. The first is that d supports f if and only if s supports j for all types j f
[Barwise 1989]. Later Lalmas relaxed the condition to represent partial relevance: any
situation supports f if it supports at least one type in f [Lalmas 1996].
IR system is to determine to which extent a document d supports the query f,
denoted by d|=f. If d|=f, then the document is relevant to the query with certainty.
Otherwise, constraints from the knowledge set will be used to find the flow that lead
to the information f. The uncertainty attached to this flow is used to compute the
degree of relevance.
A channel is to link situations. The flow of information circulates in the channel,
where the combination of constraints in sequence (c ;c ) and in parallel (c ||c ) can
be represented. Given two situations s1, s2, s1| cfi s2 means that s1 contains the
information about s2 due to the existence of the channel c. A channel c supports
constraint jfi y, denoted c|=jfi y, if and only if for all situations s1 and s2, if s1|=j,
s1|fi s2, and jfi y, then s2|=y. The notation s1|=j | cfi s2|=y stands for c|=jfi y
and s1|fi s2, which means that s1|=j carries the information that s2|=y, due to
channel c. If s1|=j | cfi s2|=y and s1=s2, then c is replaced by a special channel 1,
and j logically entails y.
4.1.2 Situation Theory Based Aboutness (|= )
Let U be the set of documents, S be the set of situations, T be the set of types, C be
the set of channels. Furthermore, let DU is a document, and Q is a query. Then,
D is modeled as a situation.
Q is modeled as a set of types
Given two set of types f1 and f2:
Dfi~ f1 iff ("jf1)(D|=j).
f1 |= f2 iff ($ c C) ("D|Dfi~ f1) ($jf1) ($yf2) (D |=j | cfi D'
|=y). Note that D' could be D itself, i.e. c=1. A more special case is D |=y
| 1fi D |=y.
(Aboutness)
f1 |=/ ST f2 iff ($/ c C) ("D|Dfi~ f1) ($jf1) ($yf2) (D |=j | cfi D'
|=y).
f1 sfi f2 iff f1  f2 (Surface
f1 d fi f2 iff ($y1f1) ($y2 f2) (jfi y). (Deep
f1 f2  f1 f2 (Composition)
precludes its negation, e.g., (s| s|=<<hit, john,
john, x; 0>>).
Suppose the negation of a set of types Q is the set of the negations of every
component type, then Q^Q.
4.1.3 Inductive Evaluation
Situation theory based IR model supports R, C, LM, RM, M, C-FA, GLM, GRM,
QLM and QRM. The proofs are provided as follows:
1. R: Reflexivity is supported.
Given Dfi~ f, Q=f
($ c C and c=1) ("D|Dfi~ f) ($jf) (D |=j | 1fi D |=y).
2. C: Containment is supported.
Surface containment is supported.
Given f1 sfi f2
f1  f2
($ c C and c=1) ("D|Dfi~ f1) ($jf1) ($jf2) (D |=j | 1fi D |=j).
Deep containment is supported.
Given f1 d fi f2
($ c C) ("D|Dfi~ f1) ($y1f1) ($y2 f2) (D |=y1 | cfi D' |=y2).
3. RCM: Right Containment Monotonicity is not supported.
Surface containment:
Given f1 |= f2 and f2 sfi f3
($ c1 C)("D|Dfi~ f1)($y1f1)($y2 f2) (D |=y1 | c1fi D' |=y2) and
But it not necessary that y2 f3
It is not necessary that f1 |= f3.
Deep containment:
Given f1 |= f2 and f2 d fi f3
($ c1 C)("D|Dfi~ f1)($y1f1)($y2 f2) (D |=y1 | c1fi D' |=y2) and
But it is not necessary that j1=y2
It is not necessary that ($c2C) ("D|Dfi~ f1) ($y1f1) ($j2f3)
(D|=y1
| c1fi D' |=j2)
It is not necessary that f1 |= f3.
4. LM: Left Compositional Monotonicity is supported.
Given f1 |= f2
($ c1 C) ("D|Dfi~ f1) ($y1f1) ($y2 f2) (D |=y1 | c1fi D' |=y2), f1
f3  f1 f3, and {"D| D ~ f1 f3} {"D| D fi~ f1}
("D|Dfi~ f1 f3) ($y1f1 f3) ($y2 f2) (D |=y1 | c1fi D' |=y2),
5. RM: Right Compositional Monotonicity is supported.
Given f1 |= f2
($ c1 C) ("D|Dfi~ f1) ($y1f1) ($y2 f2) (D |=y1 | c1fi D' |=y2), f2
f3  f2 f3, and {"D| D ~ f2 f3} {"D| D fi~ f2}
("D|Dfi~ f1) ($y1f1) ($y2 f2 f3) (D |=y1 | c1fi D' |=y2),
6. Mix (M) is supported.
Given f1 |= f2 and f3 |= f2
($ c1 C) ("D|Dfi~ f1) ($y1f1) ($y2 f2) (D |=y1 | c1fi D' |=y2) and
Recall f1 f3  f1 f3
(D |=y1 | c1fi D' |=y2) and
(D |=j1 | c2fi D' |=j2)
6 If Q1 and Q2 are single types, RCM would be supported. Here, however, we consider Q as a set of
types, which is a more general case.
7. C-FA: Context Free And is supported.
Given f1 |= f2 and f1 |= f3
($ c1 C) ("D|Dfi~ f1) ($y1f1) ($y2 f2) (D |=y1 | c1fi D' |=y2) and
($ c2 C) ("D|Dfi~ f1) ($j1f1) ($j2 f3) (D |=j1 | c2fi D' |=j2)
Recalling f1 f2  f1 f1
($ c1 C) ("D|Dfi~ f1) ($y1f1) ($y2 f2 f3) (D |=y1 | c1fi D' |=y2)
and
($ c2 C) ("D|Dfi~ f1) ($j1f1) ($j2 f2 f3) (D |=j1 | c2fi D' |=j2)
8. GLM: Guarded Left Compositional Monotonicity is trivially supported, as LM is
supported.
9. GRM: Guarded Right Compositional Monotonicity is trivially supported, as RM is
supported.
10. QLM: Qualified Left Monotonicity is trivially supported, as LM is supported.
11. QRM: Qualified Right Monotonicity is trivially supported, as RM is supported.
12. NR: Negation Rational is not supported.
Given f1|=/ ST f2
($/ c C) ("D|Dfi~ f1) ($jf1) ($yf2) (D |=j | cfi D' |=y)
This does not imply that
($/ c C) ("D|Dfi~ f1) ($jf1) ($yf2 f3) (D |=j | cfi D' |=y)
\ f1|=/ ST f2 f3 can not be guaranteed.
13. CWA: Close World Assumption is not supported.
Given f1|=/ ST f2, f2^f2
($/ c C) ("D|Dfi~ f1) ($jf1) ($yf2) (D |=j | cfi D' |=y)
But it doesn't mean it is necessary that ($ c C) ("D|Dfi~ f1) ($jf1)
(D |=j | cfi D' |= y)
\ We cannot conclude f1|= f2.
4.2 Terminological Logic based model
4.2.1 Background
Meghini, et al. proposed an IR model based on Terminological Logic (TL) [Meghini
et al. 1993]. An object-oriented approach is used to represent documents, queries, and
lexical, thesaural knowledge. The representations are not confined to describing the
content by a set of keywords. Instead, the contextual attributes, the layout
characterizations, the structure organizations and the information contents of the
documents are also taken into account. uses terms as the primary syntactic
expressions, which are concepts (monadic relations), roles (dyadic relations), and
individuals (see [Meghini et al. 1993] for formal definitions). Documents are
modeled as individual constants and a query is a concept entailing a class of
individuals, while a document can be an instance of a set of concepts describing the
properties of the document. The assertion C(i) means that an individual i is an
instance of a concept C. Concepts can be partially ordered by subsumption  which
is specified by terminological postulates comprising the thesaural knowledge base W.
A terminological postulate is an expression of the form connotation (<.) or definition
.
(= ). The semantics of TL is defined by the interpretation I over the nonempty set of
individuals U  i.e., the domain of discourse. I is a function that maps individual
constants into elements of U such that I(i )I(i
subsets of D and roles into subsets of U.U (see (Meghini et al. 1993) for details). An
algorithm called constraint propagation is also proposed for reasoning the complete
constraint set on the knowledge base by using a set of completion rules. This
inference is performed at KB construction time rather than at query time. When a
query C is formulated, it is added to the constraint set and the completion rules are
applied; then for every individual constant i occurring in the set, C(i) is checked by
simple table lookup techniques.
4.2.2
Let U be the set of all the documents, C be an alphabet of concepts. Furthermore, let
DU be a document, and QC be a query, then the aboutness in Terminological
Logic is defined as follows:
D is modeled as an individual constant.
Q is modeled as a concept.
For C1, C2 C,
Dfi~ C1 implies that C1(D) is satisfied, i.e. DI(C1).
C1fi C2 implies C1 is subsumed by C2, i.e. I(Q1) I(Q2). (Containment)
Note that if there are no terminological postulates involved, they are surface
containment. Otherwise, they are deep containment. As the surface containment
and deep containment have the same semantics under the interpretation I, we
need not distinguish them in the following proofs.
C1|= C2  Given any Dfi~ C1 and Q=C2, Q(D) is satisfied, i.e. D I(Q).
(Aboutness)
C1|=/ For every D such that Dfi~ C1 and Q=C2, Q(D) is unsatisfied, i.e.
D I(Q).
C1^C1. Note that I(a-not
4.2.3 Inductive Evaluation
based model supports R, C, RCM, C-FA, LM, M, GLM, QLM, NR and CWA.
The proofs are shown as follows:
7 (and C1 C2  Cn) denotes the set of those individuals that are denoted by C1 and C2 and  Cn.
I(and C1 C2
8 (a-not C) denotes the set of all individuals that are not denoted by C. I(a-not C)=U\I(C).
1. R: Reflexivity is supported.
~
Given Dfi C1 and Q=C1
D I(C1)
D I(Q)
C1|= C1
2. C: Containment is supported.
~
Given C1 fi C2, Dfi C1 and Q=C2
D I(C1)  I(C2)
D I(C2)
C1|= C2
3. RCM: Right Containment Monotonicity is supported.
Given C1|= C2, and C2fi C3
C1|= C2  For every D such that D fi~ C1, there is D I(C2)
D I(C3)
4. LM is supported.
Given C1|= C2
C1|= C2  For every D such that D fi~ C1, there is D I(C2)
\ For every D such that D fi~ C1 C3, there is D I(C2)
C1 C3|= C2.
5. RM: Right Compositional Monotonicity is not supported.
Given C1|= C2
C1|= C2  For every D such that D fi~ C1, there is D I(C2). But it is not
necessary that D I(C2 C3), as I(C2 C3) is a subset of I(C2).
\It is not necessary that C1 |= C2 C3.
6. Mix (M) is supported.
Given C1|= C2 and C3|= C2
C1|= C2  For every D such that D fi~ C1, there is D I(C2)
C3|= C2  For every D such that D fi~ C3, there is D I(C2)
\ For every D such that D fi~ C1 C3, there is D I(C2)
C1 C3|= C2.
7. C-FA is supported.
Given C1|= C2, C1|= C3
C1|= C2  For every D such that D fi~ C1, there is D I(C2)
C1|= C3  For every D such that D fi~ C1, there is D I(C3)
\ For every D such that D fi~ C1, there is D I(C2). I(C3), i.e. D I(C2 C3)
C1 |= C2 C3.
8. GLM: Guarded Left Compositional Monotonicity is trivially supported, as LM is
supported.
9. GRM: Guarded right Compositional Monotonicity is not supported for the similar
reason of RM.
10. QLM: Qualified Left Monotonicity is trivially supported as LM is supported.
11. QRM: Qualified Right Monotonicity is not supported for the similar reason of
RM.
12. NR: Negation Rational is supported.
C1|=/ For every D such that D fi~ C1, there is D I(C2)
D I(C2 C3)
13. CWA: Close World Assumption is supported.
Given C1 | C2, C2^C2
C1|=/ For every D such that D fi~ C1, there is D I(C2)
C2^C2  I(a-not Q1)=U\I(Q1)
D I(not Q1)
4.3 Possible world based model
4.3.1 Background
A number of possible world based logical IR models have been proposed. As stated in
[Lalmas and Bruza 1998], these systems are founded on a structure <W, R>, where W
is the set of worlds and R W.W is the accessibility relation. They can be classified
according to the choice made for the worlds wW and accessibility relation R. For
example, w can be a document (or its variation) and R is the similarity between two
documents w1 and w2 [Nie 1989; Nie 1992], or w is a term and R is the similarity
between two terms w1 and w2 [Crestani and van Rijsbergen 1995(a); Crestani and
van Rijsbergen 1995(b); Crestani and Van Rijsbergen 1998], or w is the retrieval
situation and R is the similarity between two situations w1 and w2 [Nie et al. 1995],
etc.
Most of these systems use a technique called imaging. To obtain P(dfi q), where
the connective fi represents conditional, we can move the probability from non-d-
world to d-world by a shift from the original probability distribution P of the world w
to a new probability distribution Pd of its closest world wd where d is true. This
process is called deriving P from P by imaging on d. The truth of dfi q at w will
d
then be measured by the truth of q at wd . To simplify the analysis, let's suppose that
the truth of q in a world is binary and the closest world of a world w is unique .
P(dfi q) can be computed as follows:
P(d
1, if q is true in w
0, otherwise
0, otherwise
wd is the closest world of w where d is true
Now, we study in detail Crestani and van Rijsbergen's model which models the terms
as possible worlds to see some properties of the possible world based approach. In
this model, term is considered as vector of documents, while the document and query
are vectors of terms. The accessibility relations between terms are estimated by the
co-occurrence of terms. P(dfi q) can be computed as:
P(d
occurs in q
0, otherwise
0, otherwise
td is the closest term of t where d is true(td occurs in d) (12)
Generally, d is deemed relevant to q when P(dfi q) is greater than a threshold value,
e.g., a positive real number . Similar to the vector space model (see section 3.3.2),
the simplest case is that at least one term which occurs in both d and q, or it is also the
closest term of some other terms occurring in d and q. This case is referred to as nave
possible world based model and the general case as threshold possible world based
model.
9 Actually, it can be multi-valued in an interval.
There is also an approach called General Logical Imaging that does not rely on this assumption.
4.3.2 Nave Possible World Aboutness Based on Crestani and van Rijsbergen's
Model (|=NAIVE-PW -CV )
Let U be the set of all the documents, T be the set of all the index terms, Furthermore,
let DU be a document, Q be a query, and t be a term. The aboutness in the nave
Possible World based models is defined as follows:
D and Q are sets of terms
(Surface containment)
is the closest term of t2 (Deep containment)
Q1 Q2  Q1  Q2
Preclusion is foreign to this model.
4.3.3 Inductive evaluation
This model supports R, C (surface containment), LM, RM, M and C-FA. Proofs are
given as follows:
1. R: Reflexivity is supported.
Given
P(D fi
2. C:
Surface containment is supported.
Given DQ
Deep containment is not supported.
Given t1 D, t2 Q, and t1fi t2
t2 can be imaged to its closest D-world  t1
But this cannot imply P(D fi Q may not occur in Q.
\D|= Q cannot be guaranteed.
3. RCM: Right Containment Monotonicity is not supported.
For surface containment:
Given D|= Q1, and Q1fi Q2
P(D fi
But it does not imply ($t  Q2) ($t'   T)  (I(t  ,t' ) =1)
It is not necessary that P(D fi
\ It is not necessary that D|= Q2
For deep containment: Given P(D fi Q1) > 0, t1 occurs in Q1, t1fi t2, and t2
occurs in Q2. This does not mean that there must exist a term which is the
closest term of some terms where D is true, and occurs in Q2. Thus, it is not
necessary that D|= Q2
4. LM: Left Compositional Monotonicity is supported.
Given D1|= Q, and D= D1 D2
At least one term t is the closest term of some terms where
is true and t  Q, and D1 D2=D1 D2
t is also true in D1 D2, and t  Q
5. RM: Right Compositional Monotonicity is supported.
Given D|= Q1, and
P(D fi
($t  Q1) ($t'  T) (I(t  ,t' )=1) and t  Q
P(D fi Q1
\D|= Q1 Q2
trivially supported, as LM is supported.
7. C-FA: Context Free And is trivially supported, as RM is supported.
8. GLM: Guarded Left Compositional Monotonicity is inapplicable, as preclusion is
foreign to this model.
9. GRM: Guarded Right Compositional Monotonicity is inapplicable, as preclusion
is foreign to this model.
10. QLM: Qualified Left Monotonicity is inapplicable, as preclusion is foreign to this
model.
11. QRM: Qualified Right Monotonicity is inapplicable, as preclusion is foreign to
this model.
12. NR: Negation Rational is not supported.
Given D|NAIVE-PW -CV Q1,
P(D fi
($t  Q1) ($t'   T) (I(t  ,t' )=1), and Q =Q1 Q2
But it is possible that ($t  Q) ($t'  T) ( I(t  ,t' )=1),
It is possible that P(D fi Q1
\ It's possible that D|= Q1 Q2.
13. CWA: Close World Assumption is inapplicable, as preclusion is foreign to this
model.
4.3.4 Threshold Possible World Aboutness Based on Crestani and van
Rijsbergen's Model (|=T -PW -CV )
Let U be the set of all the documents, T be the set of all the index terms, Furthermore,
let DU be a document, Q be a query, and t be a term. The aboutness in this models is
then defined as follows:
D and Q are sets of terms
D|=T -PW -CV Q iff P(Dfi Q), where  is a positive real number in the interval (0,
1]. (aboutness)
The mappings of containment, composition and preclusion are same as those in
Section 4.3.2.
4.3.5 Inductive evaluationThis model supports R, LM, RM, M, C-FA, and conditionally supports C, RCM and
NR. Proofs are given as follows:
1. R: Reflexivity is supported. The proof is the same as that of R for |=Z -PW -CV .
2. C:
Surface containment is conditionally supported.
Given DQ,
This does not imply P(D fi Q It depends on the sum of
probability of the index terms shared by D and Q and the index terms which
11 The comparison between nave and threshold PW based models are similar to that between nave
and threshold vector space models.
can be imaged to those shared terms. Only under the condition that the
threshold  is not greater than that sum, P(D fi Q
D|=T -PW -CV Q) can be guaranteed.
Deep containment is conditionally supported.
Given t1 D, t2 Q, and t1fi t2
t2 can be imaged to its closest D-world  t1
But this cannot imply P(D fi Q . Only under the condition
that the threshold  is not greater than the probability of the index terms
shared by D and Q and the index terms which can be imaged to those shared
can be guaranteed.
3. RCM: Right Containment Monotonicity is conditionally supported.
For surface containment:
Given D|=T -PW -CV Q1, and Q1fi Q2
P(D fi
But this does not imply enough index terms shared by D and Q1 and the index
terms which can be imaged to those shared terms to make
Only under the condition that the threshold  is set to be not greater than the
sum of probability of the index terms shared by D and Q and the index terms
which can be imaged to those shared terms, P(D fi
(i.e. D|=T -PW -CV Q2) can be guaranteed.
For deep containment: The proof and the condition are similar to those of
surface containment.
4. LM: Left Compositional Monotonicity is supported.
Given D1|=T -PW -CV Q, and D= D1 D2
The number of index terms which are the closest terms of certain terms where
true must be not less than that of index terms which are the closest
terms of certain terms where D1 is true. This implies that P (t)  P (t) .
5. RM: Right Compositional Monotonicity is supported. The proof is similar to that
of C-FA.
6. Mix (M) is supported.
Given D1|=T -PW -CV Q, D2|=T -PW -CV Q
7. C-FA: Context Free And is supported.
Given D|=T -PW -CV Q1, D|=T -PW -CV Q2, and
P(D fi
Q=Q1 Q2=Q1 Q2 (Q1 Q and Q2 Q),
P(D fi
P(D fi Q1
\D|=T -PW -CV Q1 Q2
8. GLM: Guarded Left Compositional Monotonicity is inapplicable, as preclusion is
foreign to this model.
9. GRM: Guarded right Compositional Monotonicity is inapplicable, as preclusion is
foreign to this model.
10. QLM: Qualified Left Monotonicity is inapplicable, as preclusion is foreign to this
model.
11. QRM: Qualified Right Monotonicity is inapplicable, as preclusion is foreign to
this model.
12. NR: Negation Rational is conditionally supported.
Given D|T -PW -CV Q1,
P(D fi
But it's possible that ($ t  Q) ($ t'  T) ( I(t ,t' )=1) and the number of
t is large
It's possible that P(D fi Q1
\ It's possible that D|=T -PW -CV Q1 Q2.
Only under the condition that the threshold  is set to be greater than the sum of
probability of the index terms shared by D and Q and the index terms which can
be imaged to those shared terms, P(D fi
D|T -PW -CV Q) can be guaranteed.
13. CWA: Close World Assumption is inapplicable, as preclusion is foreign to this
model.
4.4 Discussion
Deep containment is not relevant to classical models, unless they are augmented
by thesauri from which deep containment relationships like penguin ELUG can
be extracted. Logical models, by their very nature, directly handle deep
containment relationships. This means logical models are able to capture
information transformation e.g., logical imaging in the possible world models.
This is a major advantage of logical models. Moreover, they provide stronger
expressive power, e.g. based model provides the structured representation of
information, while concepts such as situation, type and channel, etc. in situation
theory based model make it more flexible.
The properties of an IR model are largely determined by the matching function it
supports. Two classes of matching function are widely used: containment andoverlapping (nave and non-zero threshold). The Boolean and based models
have similar properties (except that some properties inapplicable to Boolean
model are supported by based model), due to their common retrieval
mechanism, namely containment, which requires that all the information of the
query must be contained in or can be transformed to the information of the
document. The nave vector space model and nave possible world based model
have similar properties (except that deep containment is applicable to possible
world based model only) due to their simple overlapping retrieval mechanism
(i.e., a document is judged to be relevant if it shares at least one term with the
query). Compared with Boolean and based models, the nave vector space and
the nave possible world based model support Left and Right Compositional
Monotonicity, which causes imprecision. The Boolean and based models
support Right Containment Monotonicity, which promotes recall and supports the
Negation Rationale, which can improve precision. In the nave vector space and
possible world based models, Right Containment Monotonicity and Negation
rational are not supported. In summary, there is evidence to support the
assumption that the Boolean and based models are more effective models than
the nave vector space and the nave possible world based model.
The nave possible world model uses imaging (i.e., imaging from non-D world to
D-world) besides simple overlapping. Even though there may exist a containment
relation between a term t1 in the document and another one t2 in the query, if t1 is
not shared by the document and the query, then this transformation from t2 to t1 is
ineffective to establish the relevance. This explains why nave possible world
model does not support Containment (deep). The mechanics of imaging is
dependent on a notion of similarity between worlds. Experimental evidence shows
12 The discussion of Boolean model is based on the assumption that the information composition is
modeled by logical AND as we adopted in 3.1.
a relation between retrieval performance and the way in which the relationship
between worlds is defined [Crestani and Van Rijsbergen 1998]. As the underlying
framework for inductive evaluation presented in this paper does not explicitly
support a concept of similarity, it can be argued that the mapping of the possible
worlds based model into the inductive framework is incomplete. More will be said
about this point in the conclusions.
The threshold possible world model is (surprisingly) both left and right
monotonic. As a consequence there is some grounds to conclude that this model
would be imprecise in practice, and also be insensitive to document length. As
mentioned in the previous point, retrieval performance depends on how the
similarity between worlds is defined. As both LM and RM are supported, it can be
hypothesized that the baseline performance for the threshold possible world model
would be similar to the nave overlap model. More sophisticated similarity metrics
between worlds would improve performance above this baseline. Crestani and
Rijsbergen allude to this point as follows: . it is possible to obtain higher
levels of retrieval effectiveness by taking into consideration the similarity between
the objects involved in the transfer of probability. However, the similarity
information should not be used too drastically since similarity is often based on
cooccurrence and such a source of similarity information is itself uncertain
[Crestani and Van Rijsbergen 1998]. When the threshold possible world model
judges a document D relevant to the query Q, this implies that D shares a number
of terms with Q or a number of terms can be transformed to the shared terms so
that P(Dfi Q) is not less than the threshold . The expansion of D or Q can only
increase P(Dfi Q). This judgment is not true for threshold vector space model, for
after the expansion of D (or Q), the increase of the space of D (or Q), i.e. number
of terms in D and Q, may be much more than the increase of the shared terms.
Thus the degree of overlapping may be decreased.
The threshold possible worlds model and situation theory using Lalmas' relaxed
condition support LM and RM, and based model supports LM. This implies
that these models turn out to be less precise than probabilistic and threshold vector
space models. This in turn reflects the fact that logical models have not yet shown
the performance hoped for since their inception.
5. Results Summary and Conclusions

Table

1: Summary of the results of the evaluation.
Models
Postulates
Boolean
Nave
Vector Space
Threshold
Vector
Space
Probabilistic
Model
Situation
Theory
Based
Terminological
Logic Based
Nave
Possible
World
Threshold
Possible
World
R    CS
C (Deep) NA NA NA NA   . CS
RCM
(Surface)  . CS CS .  . CS
RCM (Deep) NA NA NA NA .  . CS
RM .  CS CS  .
C-FA   CS CS
GLM NA NA NA NA   NA NA
GRM . NA NA NA  . NA NA
QLM NA NA NA NA   NA NA
QRM . NA NA NA  . NA NA
NR  . CS CS .  . CS
CWA  NA NA NA .  NA NA
Note: NA means not applicable, CS means conditionally support,  means support;
and . means not support.
5.2 Conclusion
The functional benchmarking exercise presented in this paper indicates that functional
benchmarking is both feasible and useful. It has been used to analyze and compare the
functionality of various classical and logical IR models. Through the functional
benchmarking, phenomenaoccurring in the experimental IR research can be explained
from a theoretical view. The theoretical analysis could in turn help us better
understand IR and provide guideline to investigate more effective IR models.
A major point could be drawn here is that IR is conservatively monotonic in nature. It
is important that the conservatively monotonic model be studied and developed, as it
would help get an optimal tradeoff between precision and recall. The postulates GLM,
GRM, QLM, QRM, etc. guarantee the conservatively monotonic properties, but they
are foreign to some models. Even in those models, which support some of
conservatively monotonic properties, preclusion is only based on the assumption that
an information carrier precludes its negation. Moreover, GLM, QLM and MIX are the
special cases of LM, and GRM, QRM and C-FA are the special case of RM. As such,
if a model supports LM, and GLM and CautM are applicable, then it must also
support GLM and CautM. In this case, these conservative monotonicity properties
have no effect. Therefore, a model supporting conservative monotonicity should
embody conservatively monotonic properties and without also supporting LM and
RM. The probabilistic model and threshold vector space model show the good
performance in practice because they mimic the conservatively monotonicity.
However, they are dependant of factors set extraneously, e.g. the threshold value. This
is undesirable from theoretical point of view.
Current logical IR models have advantage of modeling information transformation
and their expressive power, however, they are still insufficient to model conservative
monotonicity. A primary reason is that the important concepts, such as (deep and
containment, information preclusion, etc., upon which conservative
monotonicity is based, are not sufficiently modeled. For example, semantics of
information preclusion is not explicitly defined in current logical models. We just
simply assume that an information carrier precludes its negation during the
benchmarking. It is interesting to show that if we add some kind of semantics of
preclusion to the logical IR models, the conservative monotonicity could be partially
realized. For example, we could add the following definition to the model:
Preclusion:
Given two types j1 and j2, j1^j2, s1|=j1 and s2|=j2, there does not exist any
channel between s1 and s2.
The Left composition monotonicity (LM) is no longer supported:
Given f1 |= f2
($ c1 C) ("D|Dfi~ f1) ($y1f1) ($y2 f2) (D |=y1 | c1fi D' |=y2),
Assume LM is supported, i.e. ("D|Dfi~ f1 f3) ($y1f1 f3) ($y2f2) (D
|=y1 | c1fi D' |=y2).
Consider the case of f2^f3. This implies for D|=f3 and D' |=f2, there does not
exist a channel between D and D'. This contradicts the above assumption,
because {"D|D~ f1 f3}  {"D| D|=f3}.
\ It is not necessary that f1 f2 |= f2.
On the other hand, RM is not supported for the similar reason of LM. However,
by applying the conservative forms of monotonicity, QLM and QRM, with the
qualifying non-preclusion conditions, the above-like counter example will no
longer exist.
The above definition of preclusion is simple and just for the purpose of illustration. It
is true that current IR systems are not defined in terms of these concepts mainly
because they do not view retrieval as an aboutness reasoning process. However
informational concepts are in the background. Preclusion relationships can be derived
via relevance feedback [Amati and Georgatos 1996, Bruza et al.1998]. For restricted
domains, information containment relationships can be derived from ontologies, and
the like. For example, we have been investigating automatic knowledge discovery
from text corpus based on Barwise and Seligman's theory of information flow
[Barwise and Seligman 1997, Bruza and song 2001; Song and Bruza 2001]. When
language processing tools have advanced further, the concepts under the aboutness
theory could be applied to IR more easily and more directly. More sensitive IR
systems would then result; in particular those which are conservatively monotonic
with respect to composition. Therefore, more investigations about how to achieve
conservative monotonicity in current logical IR models are necessary.
Finally, we reflect on the strengths and weaknesses of the inductive theory of
information retrieval evaluation. The strengths are summarized below:
Enhanced perspective: Matching functions can be characterized qualitatively in
terms of aboutness properties that are, or are not implied, by the matching
function in question. It may not be obvious what the implications are of a given
numeric formulation of a matching function. The inductive analysis allows some
of these implications to be teased out. By way of illustration, models based on
overlap may imply monotonicity (left or right), which is precision degrading. In
addition, inductive analysis allows one to compute under what conditions a
particular aboutness property is supported. It has been argued that a conservatively
monotonic aboutness relationship promotes effective retrieval. The analysis in
this paper revealed that although both of these models support conservative
monotonicity, the fundaments of this support are very different: The thresholded
vector space model support for conservative monotonicity depends on overlap
between document and query terms modulo the size of the document [check this
because our formulations don't include document length normalization]. Support
for conservative monotonicity in the probabilistic model depends on whether the
terms being added have a high enough probability of occurring in relevant
documents. Form an intuitive point of view, the latter condition would seem a
more sound basis for support because it is directly tied to relevance.
Transparency: One may disagree with a given functional benchmark (as
represented by a set of aboutness properties), or with how a given matching
function has been mapped into the inductive framework, however, the
assumptions made have been explicitly stated. This differs from some
experimental studies where the underlying assumptions (e.g., the import of certain
constants) are not, or insufficiently, motivated.
New insights: The use of an abstract framework allows new insights to be
gleaned. Inductive evaluation has highlighted the import of monotonicity in
retrieval functions, and its affect on retrieval performance. Designers of new
matching functions should provide functions that are conservatively monotonic
with respect to the composition of information. More sensitive IR systems would
then result. The lack of such systems currently can be attributed in part to the
inability to effectively "operationalize" information preclusion. Most common IR
models are either monotonic or non-monotonic - another class of IR models,
namely those that are conservatively monotonic is missing. Such models are
interesting for purposes for producing symbolic inference foundation to query
expansion and perhaps even relevance feedback.
The weaknesses of an inductive theory for evaluation are:
Difficulty in dealing with weights: Much of the subtlety of IR models remains
buried in different weighting schemes. Due to its symbolic nature, the inductive
approach can abstract too much, thereby losing sensitivity in the final analysis.
For example, the nuances of document length normalization, term independence
assumptions, probabilistic weighting schemes are difficult, if not impossible, to
map faithfully into a symbolic, inductive framework
Difficulties with mapping: For an arbitrary model, it may not be obvious how to
map the model into an inductive framework. This is particularly true for heavily
numeric models such as probabilistic models. It is often the case that such models
do not support many symbolic properties - they are like black holes defying
analysis [Bruza, Song & Wong 2000]. However, by analysing the conditions
under which given properties are supported allow us to peak at the edges of the
black hole.
Incompleteness of framework: In order to pursue functional benchmarking, a
sufficiently expressive framework is necessary in order to represent salient aspects
of the model in question. This is an issue of completeness. In the inductive
analysis of the possible worlds based models presented in this paper, we have seen
that the notion of similarity inherent to these models cannot be directly translated
into the underlying inductive framework. This suggests that the framework
presented in this paper should be extended. One could also argue that not all
salient aspects of aboutness have been captured by the properties used for the
benchmark. These are not criticisms of inductive evaluation, but of the tools being
used.
It is noteworthy that conventional experimental IR evaluation approaches are good
performance indicators but fail to reflect the functionality of an IR system, i.e. which
types of IR operation the system supports. From an application point of view, the
experimental approaches could serve as the performance benchmark (e.g. TREC).
Practically, it is complementary to the functional benchmark proposed in this paper.

Acknowledgement

This project is partially supported by the Chinese University of Hong Kong's strategic
grant (project ID: 44M5007), and by the Cooperative Research Centres Program
through the Department of the Prime Minister and Cabinet of Australia.


--R

Information Retrieval and Hypertext.
Relevance as deduction: A logical view of information retrieval.
Modern Information Retrieval.
The Situation in Logic.

Investigating aboutness axioms using information fields.

Logic based information retrieval: Is it really worth it?
Preferential models of query by navigation.
Informational Inference Via Information Flow.
Commonsense aboutness for information retrieval.
Fundamental properties of aboutness.




Information Retrieval
An Axiomatic Theory for Information Retrieval.

Information retrieval and situation theory.
Using default logic in information retrieval.
Intelligent text handling using default logic
On the problem of 'aboutness' in document analysis.

Theories of Information and Uncertainty for the Modeling of Information Retrieval: An Application of Situation Theory and Dempster-Shafer's Theory of Evidence
Information retrieval and Dempster-Shafer's theory of evidence
Logical models in information retrieval: Introduction and overview.
The use of logic in information retrieval modeling.
Towards a theory of information.
Comparing boolean and probabilistic information retrieval systems across queries and disciplines.
Text Retrieval and Filtering: Analytic Models of Performance.
On indexing
A model of information retrieval based on terminological logic.
A relevance terminological logic for information retrieval.
An information retrieval model based on modal logic.
Towards a probabilistic modal logic for semantic-based information retrieval
Information retrieval as counterfactual.
What is information discovery about?

A new theoretical framework for information retrieval.
The state of information retrieval: logic and information.
An information calculus for information retrieval.
Retrieval of complex objects using a four-valued logic

A probabilistic terminological logic for modeling information retrieval.
On the role of logic in information retrieval.
Discovering Information Flow using a High Dimensional Conceptual Space.
Fundamental properties of the core matching functions for information retrieval.
Towards a commonsense aboutness theory for information retrieval modeling.
A comparison of text retrieval models.
--TR
Automatic text processing
Towards an information logic
Nonmonotonic reasoning, preferential models and cumulative logics
Information retrieval
Towards a probabilistic modal logic for semantic-based information retrieval
A comparison of text retrieval models
Investigating aboutness axioms using information fields
Probability kinematics in information retrieval
Information calculus for information retrieval
Query expansion using local and global document analysis
Pivoted document length normalization
Retrieval of complex objects using a four-valued logic
A study of aboutness in information retrieval
Comparing Boolean and probabilistic information retrieval systems across queries and disciplines
(invited paper) A new theoretical framework for information retrieval
Information flow
On the role of logic in information retrieval
Logical models in information retrieval
A study of probability kinematics in information retrieval
Text retrieval and filtering
What is information discovery about?
Fundamental properties of aboutness (poster abstract)
Aboutness from a commonsense perspective
Information retrieval and situation theory
Discovering information flow suing high dimensional conceptual space
Information Retrieval
Modern Information Retrieval
Informal Inference via Information Flow
Information retrieval and Dempster-Shafer''s theory of evidence
Using Default Logic in Information Retrieval
Towards Functional Benchmarking of Information Retrieval Models
Fundamental Properties of the Core Matching Functions for Information Retrieval
Intelligent Text Handling Using Default Logic
A commonsense aboutness theory for information retrieval modeling

--CTR
Tobias Blanke , Mounia Lalmas, Theoretical benchmarks of XML retrieval, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Dawei Song , Jian-Yun Nie, Introduction to special issue on reasoning in natural language information processing, ACM Transactions on Asian Language Information Processing (TALIP), v.5 n.4, p.291-295, December 2006
D. Song , P. D. Bruza, Towards context sensitive information inference, Journal of the American Society for Information Science and Technology, v.54 n.4, p.321-334, February 15,
Fang , ChengXiang Zhai, An exploration of axiomatic approaches to information retrieval, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
Raymond Y.K. Lau , Peter D. Bruza , Dawei Song, Belief revision for adaptive information retrieval, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
Jian-Yun Nie , Guihong Cao , Jing Bai, Inferential language models for information retrieval, ACM Transactions on Asian Language Information Processing (TALIP), v.5 n.4, p.296-322, December 2006
functional benchmarking;inductive evaluation;aboutness;logic-based information retrieval