Information Theoretic Approach to Relevance
Julian Satchell, QinetiQ

I will describe a simple way of think of about relevance. Some definitions are needed first. 

A document means a retrievable item of information; it need not map to a file or conventional URL but can include items like a database record or a set of email account details. A document has features; these may be internal (for example, the presence of certain words, or meta-data held within the document) or external (perhaps some meta-data about the document held in a database, or Nautilus emblems). For simplicity, I am going to start off just considering simple documents (rather than composite ones that contain others), and simple discrete features (with binary values – the feature is either there or it is not). Let N be the total number of documents and M be the total number of distinct features. Each feature i has a probability Pi which can be estimated from the number of documents ni with feature i by Pi =  ni /N. The standard Shannon information measure associated with this feature is just loge(Pi ). The total information content of document j is just the sum of the information content of its features. An obvious and valid objection to the last sentence is that there is usually a lot more information in a document than the features; for example if we restrict ourselves to features corresponding to single word occurrence, we can sort the words in a document into alphabetical order without making any difference! Clearly, additional, subtle features are needed that capture semantics in useful way. Furthermore, feature occurrence is usually highly correlated, while the Shannon information measure is only appropriate if they are random. These are well known objections to the "naive Bayes" approach; it can only be defended on the basis that it often works quite well empirically.

In this naive world view, relevance is easy to define – it is the cross information. That is, the relevance of document j to document k is just the sum of the information measures of the features that are shared. This is a surprisingly powerful unifying concept; it allows many different types of document properties to be combined. For example, the fact that two files are both jpeg images is probably a very weak similarity, assuming you have lots of jpegs. The fact that two files have the same creator may be a very powerful similarity, if very few files come from that source.

Big documents (with many features) are favoured by this approach, as a sufficiently big document is likely to be moderately similar to a lot of different queries. It is common practise in the related problem of text classification to use length normalisation; in our case simply dividing the cross-information by the total number of features would help, but may be too fierce – I feel some mathematical carpentry coming on. It may be worth making this user configurable - with settings for "favour small", "favour big" or  "size neutral", corresponding to linear normalisation, no normalisation or some intermediate function (perhaps logarithmic or square root).

Continuous meta-data types (single dimensional like times, or higher dimensional like geographic position) are easy to accommodate in this framework. We need to have a model of the probability density for each type of meta-data.  In the absence of other information we can start off by assuming a uniform distribution of documents over the range. The probability (and hence contribution to cross information) associated with a target document is the integral of the probability density over a region centred on the query document that just includes the target document. This probability falls off as the separation of values increases. A uniform probability density on one dimension would give a probability that is proportional to separation; in two dimensions with a Euclidean metric it would be proportional to separation squared.

In many cases it will be possible to greatly improve the estimate of probability density from a uniform one; for example one could look at the time of day or day of the week and refine the estimate on that basis. For this to work, we need to have some basis for being able to factorise the probability distribution. 

A sane starting point for geographic data is to say that documents are uniformly distributed over the globe; the differences in lat/long can (with a bit of spherical trig) be translated into a fraction of the earth's surface. Of course, many documents have no geographic meta-data at all; this reduces the overall probabilities, and increases the information content of any geographic meta-data. The effect of this will be to favour documents that share rare meta-data types, even if the values are quite different. The alternative normalisation is to only consider those documents that express a value for a particular meta-data type, which raises the probabilities, and greatly discounts the effect of rare meta-data types. Experiments will be needed to see which normalisation works best for users in practise.

Dashboard could adopt a strategy based on this information theoretic approach, if indices of features record the probabilities associated with the feature values, or at least provide an estimate. For example, the document back-end would need to keep track of the total number of documents that contain each word. If Redland (or, in the future, Storage) allows meta-data based searches, it would be great if it maintained at least simple probabilities for the meta-data values.

I have no idea yet how to do any of the following:

1)	Associate probabilities with resources off the machine – I don’t see what the set of documents is, and I have no idea how to estimate probabilities for them. The only thing I can think of is to say the document set is the set of URLs indexed by Google. Then the probability would be based on the (wildly inaccurate) estimates of numbers of documents returned.  There are all sorts of legal problems with using Google this way.
2)	There are two ways of thinking about derived clues – either it is just a search strategy and you look at the simple minded relevance of all the results, or you use Baye’s theorem to quantify the relevance at multiple steps. 
3)	Composite documents are too hard for me just now; if we can work out the right definition of cross-information for them it would then be possible to think about returning a directory rather just a single document. I am not clear if one just aggregates all the features of the contained documents, or if you should discount child features in some way. The choice of size normalisation will greatly effect how composite documents behave – no normalisation at all will tend to favour the selection of things far up the hierarchy, while normalisation by total number of features means that leaf documents will always win. Alternatively, you could perform no automatic aggregation of child features at all, which results in preferential selection of leaf documents.
4)	I have no idea yet how to build a sorting engine to do any of this with acceptable performance. A simplified version of this algorithm has been implemented using a relational database (Postgres). The queries involve aggregate sums over self joins – only fairly advanced databases can perform queries like this at all; for example older versions of mysql and MS Access can't do it. Performance was fine on small document sets (say a few thousand), but was pretty slow on systems with say 50,000 documents. Pruning the query to remove low information features vastly improved performance - common features make little or no difference to the sort order but pull in vast numbers of weakly related items, which are of no use. 
5)	The approach sketched above has no provision for user feedback to allow machine learning. This has proved vital for spam filtering,  and may turn out to be needed if  dashboard is to optimise its behaviour. Autonomy use reinforcement on the basis of the documents that are selected – the learning context for a specific task is called an agent. Over time, the agents place more and more weight on fewer data items, and the system degenerates into a form of keyword search.

I am told that are relationships between what I am proposing and Breiman decision trees, but I have not read that stuff yet.