unl/Csce810Chapter2

Chapter 1 + Section 2.1 Introduction

Information Retrieval Process

• Three Models of Browsing
  • Flag
  • Structure guided
  • Hypertext

Section 2.2 A taxonomy of Information Retrieval Models

• Predicting which documents are relevant is usaually dependent on a ranking algorithm.

• The three classic models in information retreival are:

  • Boolean Model: In the boolean model documents and queries are represented as sets of index terms, thus we say this model is a set theoretic model

  • Vector Model: In the vector model documents and queries are represented as vectors in a t-dimensional space, thus we say that the model is algebraic.

  • Probabilistic Model: The framework for modeling document and query representations is based on probability theory, and thus we sat that the model is prababilistic.

Section 2.3 Retrieval: Ad hoc and Filtering

The following is the formal definition for IR from MIR p 23.

Definition An information retrieval model is a quadruple where

• is a set composed of logical views (or representations) for the documents in the collection.

• is a set composed of logical views (or representations) for the user information needs. Such representations are called queries

• is a framework for modeling document representations, queries and their relationships.

• is a ranking function which associates a real number with a query and a document representation . Such ranking defines an ordering among the documents with regard to the query .

Section 2.5.1 Basic Concepts of Classic IR

• Each document is described by a set of representative key workds calle index terms.

• Index terms are usually nouns. Why? Because verbs, adjectives connectives etc. have little meaning on their own.
• Index terms have weights described as follows:

Definition Let be the number of index terms in the system and be a generic index term. is the set of all index terms. A weight is associated with each index term of a document . For an index term which does not appear in the document text, . With document is associated an index term vector . Further, let be a function that returns the weight associated with the index term in any -dimensional vector (i.e., ).

Section 2.5.2 Boolean Model

• index terms are weighted either 0 or 1.

• Queries are expressed in DisjunctiveNormalForm of the can be written in disjunctive

normal form as .

Definition For the Boolean model, the index term weight variables are all binary ie.e, . A query is a conventional boolean expression. Let be the disjunctive normal form for the query . further, let be any of the conjunctive components of . The similarity of a document to the query is defined as

If then the Boolean model predicts that the document is relevant to the query (it might not be). Otherwise, the prediction is that the document is not relevant.

Section 2.5.3 Vector Model

• Weights are non-binary that is real numbers
• This allows us to calculate a degree of similarity.

Definition For the vector model, the weight $w_{i,j}$ associated with a pair is positive and non-binary. Further, the index terms in the query are also weighted. Let $w_{i,q}$ be the weight associated with the pair , where . Then, the query vector is defined as where is the total number of index terms in the system. As before, the vector for a document is represented by .

Thus we have a document and user query represented as -dimensional vectors. Similarity is defined cosine of the angle between the document vector and the query vector as follows:

attachment:csce810_2_2.png

Figure 2

Having defined similarity the we now have a method for ranking and we can determine what is relevant by setting a threshold on the degree of similarity. This is essentially a clustering algorithm that clusters documents similar to the query in one set and documents dissimilar to the query in the other set. We say the IR problem can be reduced to a clustering problem determining what documents belong to the relevant set A and which do not. There are two main issues to resolved in a clustering problem:

1. intra-cluster similarity --> term frequency (tf): One needs to determine what are the features which better describe the objects in set A.

2. intra-cluster dissimilarity --> inverse document frequency (idf): One needs to determine what are the features which better distinguish the objects in set A from the remaining objects in collection C (the set of all documents).

Definition

Let be the total number of documents in the system and be the number of documents in which the index term appears. Let be the raw frequency of term in the document (i.e., the number of times the term $k_i$ is mentioned in the text of the document $d_j$). Then, the {\bf normalized} frequency $f_{i,j}$ of term $k_i$ in document $d_j$ is given by:

where the maximum is computed over all terms which are mentioned in the text of the document . If the term does not appear in the document then . Further, let , inverse document frequency for given by:

The best known term weighting schemes use weights which are given by

or by a variation of this formula. Such term-weighting strategies are called - schemes.

One such term wights formula was given by Salton and Buckley as

Advantages

1. Term-weighting scheme improves retrieval performance
2. Partial matching allows retrieval of documents that approximate the query conditions
3. The cosine ranking formula sorts the documents according th their degree of similarity

Disadvantages

1. Does not account for term dependencies
2. Answer sets are difficult to improve without query expansion or relevance feedback.

Section 2.5.4 Probabilistic Model

Main Idea: Given a user query there is a set of documents which contains exactly the relevant documents and no other.

1. There exists an ideal answer set to a query.

Given a set of index terms we guess at the properties of the ideal set and retrieve that set. This becomes the guess or initial set of documents.

Assumption (Prababilistic Principle):

Given a user query and a document in the collection, the probabilistic model tries to estimate the probability that the user will find teh document interesting (i.e. relevant). The model assumes that this probability of relevance depends on the query and the document representations only. Further, the model assumes that there is a subset of all documents which the user prefers as the answer set for the query . Such an ideal answer set is labeled and should maximized the overall probability of relevance to the user. Documents in the set are predicted to be relevant to the query. Documents not in this set are predicted to be non-relevant.

Given a query , the probabilistic model assigns to each document , as a measure of its similarity to the query, the ratio:

which computes the odds of the document being relevant to the query . Taking the odds of relevance as the rank minimizes the probability of an erroneous judgement.

Definition

For the probabilistic mode, the index term weight variables are all binary i.e., , . A query is a subset of index terms. Let be the set of documents known (or initially guessed}) to be relevant. Let be the complement of (i.e. the set of initially guessed non-relevant documents). Let be the probability that the document is relevant to the query and be the probability that is non-relevant to . The similarity of the document to the query $q$ is defined as the ratio:

Using Bayes' rule,

For more info see P32 MIR. They assume that and are the same for all the documents in the collection. This doesn't make sense to me unless we assume that about of the documents that are relevant. The other option is to say that a few are definitely relevant and a few are definitely irrelevant, and the rest are in a different category of quasi-relevant. Even this doesn't make sense though because we named the two sets and . Big question!

If we leave off and we get:

Assuming independence of index terms,

where: means the weight of query keyword of document is and stands for the probability that the index term is present in a document randomly selected from the set . stands for the probability that the index term is not present in a document randomly selected from the set . And of course is the initial guess at the relevant set. With some massaging of the above equation, we can get:

In the very beginning (i.e. immediately after the query specification), there are no retrieved documents. Thus, one has to make simplifying assumptions such as

• assume that is constant for all index terms
• assume that the distribution of index terms among the non-relevant documents can be approximated by the distribution of index terms among all the docuemnts in the collection.

From these two assumptions we get:

where is the number of documents that contain the keyword and is the total number of documents in the collection. Now that we have initial values for the probabilities we can use (previous equation) to rank the documents and determine our first guess at the set of document that belong in call this initial set determined by the top ranked documents. Define to be the subset of containing keyword . Now we are ready to improve our guesses for and . We accomplish this with the following assumptions

• We can approximate by the distribution of index term among the documents retrieved so far
• We can approximate by considering all the non-retrieved documents as not relevant.

From these two assumptions we get:

This process can be repeated without any human intervention to improve our guesses for the probabilities. For small values of we in practice make the above two equations:

or