CHAPTER 4

Loose ends

The original proposal for this project contained a number of suggestions fortheoretical work, some of which resulted in fruitful developments such as
experimetal investigations, and some of which did not. The reasons for thelatter were various, including lack of time, ideas being superseded by thework of others, and unforeseen or underestimated theoretical problems. We
feel that such occurrences are inevitable in a project with a strong
theoretical element such as this. But we also feel that these dead or loose
ends should be recorded, for the benefit of anyone who wishes to reopen themor pursue the ideas further.
The suggestions in the original proposal which have not been followed up forlack of time are: the incorporation of document length (i.e. number of indexterms) into the probabilistic models; the use of information from manuallyproduced thesauri, and also from previous queries, in such models; and thebuilding of a spanning tree on the document collection (as a development of
the idea of document clustering). Those to which we have given someconsideration are discussed in the remainder of this chapter.

1 Harter-dependence models
We originally hoped to take the work on the Harter model a stage further
than described in Chapter 3 and incorporate some ideas of dependence between
terms such as those already considered for the binary case by vanRijsbergen. This idea was not pursued for the following reasons:a) The development of a Harter-independence model proved rather moredifficult, and the model itself proved rather more elaborate, thanoriginally foreseen.
b) The number of dependencies that one might have to consider in a Harterdependence model is alarming, as can be seen from the diagram in Chapter 3para. 4.2.
c) Work on dependence models generally can develop in two directions: theexplicit estimation and use of dependencies in a relevance feedback strategy(which was perhaps the original aim of the work), or the use of global (notrelevance-related) dependencies for query expansion. Recent work hasconcentrated on the latter (see Chapter 2 ) . Harper's (1980) investigationsof the former produced disappointing results. But in the latter case, thedependence model can be treated separately from the weighting model.

-63-d) One overriding problem which has beset probabilistic IRf and which ismentioned on more than one occasion in this report, is the problem ofestimation. We have the strong feeling that it will now be more fruitful toconcentrate on the estimation problem in the context of the probabilistic
models that we now have, than to develop yet more complex probabilistic
models.

2 Relevance weights and term frequency
It was suggested in the original proposal that one might seek to formalise
the relationship which we know to exist between term frequency and term
value, by means of a regression model which would allow the prediction ofrelevance weights from term frequencies in the absence of relevance feedback
information. Subsequently, Croft and Harper (1979) proposed a very simple
no-relevance-information model, as discussed in Chapter 3. More recently,
Yu, Lam and Salton (in press) have suggested a somewhat more elaboratemodel.
Neither of these is, strictly speaking, a regression model, and there may
still be room for such a model. But it now seems that the problem may bebetter treated as part of the estimation problem, with the aim of producing
a Bayesian estimator which would start from some initial estimate based onterm frequency, and incorporate relevance information as it became
available. As with the general estimation problem, this would require morestatistical expertise than is available on the present project. It is hoped
to pursue this idea in the future.

3 Statistical structure of indexed collections
As part of the background to probabilistic models in general and dependence
models in particular, it was hoped to investigate the overall statisticalstructure of indexed document collections. The aim was to develop models
which would predict or generate the kinds of structure observed in realcollections, and to test them by simulation. For this purpose, sometheoretical background was required.
A predominant feature of the statistical structure of collections is themanner in which term-document assignments are far from uniformly or randomlydistributed. This fact is reflected in the way in which we can find (byalmost any clustering method) clusters of terms which tend to occur in thesame documents. Conversely, one can find clusters of documents which tend tocontain the same terms. The relationships between these tendencies tocluster and retrieval have been formulated as the Association Hypothesis(Chapter 2) and the Cluster Hypothesis (van Rijsbergen and Sparck Jones,
1973) respectively.
It was hypothesised that these clustering tendencies (of both documents andterms) were in some way logically connected: that is, that a collection-64-exhibiting one type of clustering would have to exhibit the other as well.
Preliminary investigation showed this hypothesis to be false, as can be seenfrom the following argument.
We can define a pseudo-collection which exhibits neither type of clustering
as follows:Termsa b e dDocuments

101010ABCDEF

100
10
101
100
10
10
1
10

The term-term co-occurrence matrix is:bc
1

1dso there is certainly no clustering of terms. The document-document matrix
is:
A0
1
1
1
1

B
1
11
1

C0
1
1

D
11E0F

which also does not allow any clustering of documents.
Can we therefore similarly construct a collection which exhibits one form ofclustering but not the other? Yes we can, by a very simple modification ofthe above. If we introduce new terms e, ff g, h which exactly duplicate a,b f c, d respectively:

AB
CDE
F

10
1
0
1
0

1
00
1
0
10
1
100
1

0
10
1
10

1
0
10
10fg

h1
00
1
0
1

0
1
10
0
1

0
1
0
1
10-65-

then the co-occurrence matrices become:
a1
11

3
1
11

b1
11

3
1
1c111d113 1
1 3e
111f
1
1g
1

A
0
2222B2222C022D22E0h

Thus the document-document matrix has the same structure as before, with noclustering. The term-term matrix on the other hand, shows clear clustering:
Cluster 1 : a, e
Cluster 2 : b, f
Cluster 3 : c, g
Cluster 4 : d, h
as might be expected from the way e, f, g, h were defined.
So the hypothesis is invalid. This does not imply that a particular model
will not generate or explain both types of clustering simultaneously, but it
does make the specific assumptions on which such a model might be based morecritical. This line of work has not progressed beyond this point, but could
usefully be pursued in the future. Following earlier work by Cooper (1973)
and Griffiths (1978), a simulation model which may have some bearing onthese problems is being developed by Tague and Nelson (in press).

-66-

REFERENCES
CROFT, W.B. and HARPER, D.J. [1979] Using probabilistic models of document
retrieval without relevance information. Journal of Documentation, 35 no. 4
Dec 1979, pp. 285-295.
HARPER, D.J. [1980] Relevance feedback in document retrieval. Ph.D. Thesis,
University of Cambridge.
YU, C.T., LAM, K. and SALTON, G. [in press] Term weighting in information
retrieval using the term precision model. Journal of the A . C M .
VAN RIJSBERGEN, C.J. and SPARCK JONES, K. [1973] A test for the separationof relevant and non-relevant documents in experimental retrieval
collections.Journal of Documentation, 29 no. 3 Sept 1973, pp. 251-257.
COOPER, M.D. [1973] A simulation model of an information retrieval system.
Information Storage and Retrieval, £ pp. 13-32.
GRIFFITHS, J.M. [1978] The computer simulation of information retrieval
systems. Ph.D. Thesis, University of London.
TAGUE, J. and NELSON, M. [in press] Problems in the simulation of document
retrieval systems. Paper presented at BCS-ACM Conference, Research andDevelopment in Information Retrieval, Cambridge, June 23-27, 1980.

-67-