<제 2장 정보검색 모델>

* Vector space

A vector space is a mathematical structure formed by a collection of elements called vectors, which may be added together and multiplied ("scaled") by numbers, called scalars in this context. Scalars are often taken to be real numbers, but there are also vector spaces with scalar multiplication by complex numbers, rational numbers, or generally any field. The operations of vector addition and scalar multiplication must satisfy certain requirements, called axioms, listed below. An example of a vector space is that of Euclidean vectors, which may be used to represent physical quantities such as forces: any two forces (of the same type) can be added to yield a third, and the multiplication of a force vector by a real multiplier is another force vector. In the same vein, but in a more geometric sense, vectors representing displacements in the plane or in three-dimensional space also form vector spaces. Vectors in vector spaces do not necessarily have to be arrow-like objects as they appear in the mentioned examples: vectors are best thought of as abstract mathematical objects with particular properties, which in some cases can be visualized as arrows.

Vector spaces are the subject of linear algebra and are well understood from this point of view, since vector spaces are characterized by their dimension, which, roughly speaking, specifies the number of independent directions in the space. A vector space may be endowed with additional structure, such as a norm or inner product. Such spaces arise naturally in mathematical analysis, mainly in the guise of infinite-dimensional function spaces whose vectors are functions. Analytical problems call for the ability to decide whether a sequence of vectors converges to a given vector. This is accomplished by considering vector spaces with additional structure, mostly spaces endowed with a suitable topology, thus allowing the consideration of proximity and continuity issues. These topological vector spaces, in particular Banach spaces and Hilbert spaces, have a richer theory.

Historically, the first ideas leading to vector spaces can be traced back as far as 17th century's analytic geometry, matrices, systems of linear equations, and Euclidean vectors. The modern, more abstract treatment, first formulated by Giuseppe Peano in 1888, encompasses more general objects than Euclidean space, but much of the theory can be seen as an extension of classical geometric ideas like lines, planes and their higher-dimensional analogs.

Today, vector spaces are applied throughout mathematics, science and engineering. They are the appropriate linear-algebraic notion to deal with systems of linear equations; offer a framework for Fourier expansion, which is employed in image compression routines; or provide an environment that can be used for solution techniques for partial differential equations. Furthermore, vector spaces furnish an abstract, coordinate-free way of dealing with geometrical and physical objects such as tensors. This in turn allows the examination of local properties of manifolds by linearization techniques. Vector spaces may be generalized in several ways, leading to more advanced notions in geometry and abstract algebra.

# First example: arrows in the plane

The concept of vector space will first be explained by describing two particular examples. The first example of a vector space consists of arrows in a fixed plane, starting at one fixed point. This is used in physics to describe forces or velocities. Given any two such arrows, v and w, the parallelogram spanned by these two arrows contains one diagonal arrow that starts at the origin, too. This new arrow is called the sum of the two arrows and is denoted v + w. Another operation that can be done with arrows is scaling: given any positive real number a, the arrow that has the same direction as v, but is dilated or shrunk by multiplying its length by a, is called multiplication of v by a. It is denoted av. When a is negative, av is defined as the arrow pointing in the opposite direction, instead.

The following shows a few examples: if a = 2, the resulting vector aw has the same direction as w, but is stretched to the double length of w (right image below). Equivalently 2w is the sum w + w. Moreover, (−1)v = −v has the opposite direction and the same length as v (blue vector pointing down in the right image).

Vector addition and scalar multiplication: a vector v (blue) is added to

another vector w (red, upper illustration). Below, w is stretched by a

factor of 2, yielding the sum v + 2·w

* Probabilistic relevance model

The probabilistic relevance model was devised by Robertson and Jones as a framework for probabilistic models to come.

It makes an estimation of the probability of finding if a document dj is relevant to a query q. This model assumes that this probability of relevance depends on the query and document representations. Furthermore, it assumes that there is a portion of all documents that is preferred by the user as the answer set for query q. Such an ideal answer set is called R and should maximize the overall probability of relevance to that user. The prediction is that documents in this set R are relevant to the query, while documents not present in the set are non-relevant.

# Related models

There are some limitations to this framework that need to be addressed by further development:

#There is no accurate estimate for the first run probabilities

#Index terms are not weighted

#Terms are assumed mutually independent

To address these and other concerns there are some developed models from the probabilistic relevance framework. The Binary Independence Model for one, as it is from the same author. The most known derivative of this framework is the Okapi(BM25) weighting scheme and it's BM25F brother.

1) The Binary Independence Model (BIM)

A probabilistic information retrieval technique that makes some simple assumptions to make the estimation of document/query similarity probability feasible.

* Definitions

The Binary Independence Assumption is that documents are binary vectors. That is, only the presence or absence of terms in documents are recorded. Terms are independently distributed in the set of relevant documents and they are also independently distributed in the set of irrelevant documents. The representation is an ordered set of Boolean variables. That is, the representation of a document or query is a vector with one Boolean element for each term under consideration. More specifically, a document is represented by a vector d = (x1, ..., xm) where xt=1 if term t is present in the document d and xt=0 if it's not. Many documents can have the same vector representation with this simplification. Queries are represented in a similar way. "Independence" signifies that terms in the document are considered independently from each other and no association between terms is modeled.     This assumption is very limiting, but it has been shown that it gives good enough results for many situations. This independence is the "naive" assumption of a Naive Bayes classifier, where properties that imply each other are nonetheless treated as independent for the sake of simplicity. This assumption allows the representation to be treated as an instance of a Vector space model by considering each term as a value of 0 or 1 along a dimension orthogonal to the dimensions used for the other terms.

The probability P(R|d,q) that a document is relevant derives from the probability of relevance of the terms vector of that document P(R|x,q). By using the Bayes rule we get:

where P(x|R=1,q) and P(x|R=0,q) are the probabilities of retrieving a relevant or nonrelevant document, respectively. If so, then that document's representation is x. The exact probabilities can not be known beforehand, so use estimates from statistics about the collection of documents must be used.

P(R=1|q) and P(R=0|q) indicate the previous probability of retrieving a relevant or nonrelevant document respectively for a query q. If, for instance, we knew the percentage of relevant documents in the collection, then we could use it to estimate these probabilities. Since a document is either relevant or nonrelevant to a query we have that:

* Query Terms Weighting

Given a binary query and the dot product as the similarity function between a document and a query, the problem is to assign weights to the terms in the query such that the retrieval effectiveness will be high. Let  and  be the probability that a relevant document and an irrelevant document has the  term respectively. Yu and Salton, who first introduce BIM, propose that the weight of the  term is an increasing function of . Thus, if  is higher than , the weight of term  will be higher than that of term . Yu and Salton showed that such a weight assignment to query terms yields better retrieval effectiveness than if query terms are equally weighted. Robertson and Sparck later showed that if the  term is assigned the weight of , then optimal retrieval effectiveness is obtained under the Binary Independence Assumption.

The Binary Independence Model was introduced by Yu and Salton. The name Binary Independence Model was coined by Robertson and Sparck.

2)) Okapi BM25

Okapi BM25 is a ranking function used by search engines to rank matching documents according to their relevance to a given search query. It is based on the probabilistic retrieval framework developed in the 1970s and 1980s by Stephen E. Robertson, Karen Spärck Jones, and others.

The name of the actual ranking function is BM25. To set the right context, however, it usually referred to as "Okapi BM25", since the Okapi information retrieval system, implemented at London's City University in the 1980s and 1990s, was the first system to implement this function.

BM25, and its newer variants, e.g. BM25F (a version of BM25 that can take document structure and anchor text into account), represent state-of-the-art TF-IDF-like retrieval functions used in document retrieval, such as Web search.

* The ranking function

BM25 is a bag-of-words retrieval function that ranks a set of documents based on the query terms appearing in each document, regardless of the inter-relationship between the query terms within a document (e.g., their relative proximity). It is not a single function, but actually a whole family of scoring functions, with slightly different components and parameters. One of the most prominent instantiations of the function is as follows.

Given a query , containing keywords , the BM25 score of a document  is:

where  is 's term frequency in the document ,  is the length of the document  in words, and  is the average document length in the text collection from which documents are drawn.  and  are free parameters, usually chosen, in absence of an advanced optimization, as  and .[1]  is the IDF (inverse document frequency) weight of the query term . It is usually computed as:

where  is the total number of documents in the collection, and  is the number of documents containing .

There are several interpretations for IDF and slight variations on its formula. In the original BM25 derivation, the IDF component is derived from the Binary Independence Model.

Please note that the above formula for IDF shows potentially major drawbacks when using it for terms appearing in more than half of the corpus documents. These terms' IDF is negative, so for any two almost-identical documents, one which contains the term and one which does not contain it, the latter will possibly get a larger score. This means that terms appearing in more than half of the corpus will provide negative contributions to the final document score. This is often an undesirable behavior, so many real-world applications would deal with this IDF formula in a different way:

Each summand can be given a floor of 0, to trim out common terms;

The IDF function can be given a floor of a constant , to avoid common terms being ignored at all;

The IDF function can be replaced with a similarly shaped one which is non-negative, or strictly positive to avoid terms being ignored at all.

* IDF Information Theoretic Interpretation

Here is an interpretation from information theory. Suppose a query term  appears in  documents. Then a randomly picked document  will contain the term with probability  (where  is again the cardinality of the set of documents in the collection). Therefore, the information content of the message " contains " is:

Now suppose we have two query terms  and . If the two terms occur in documents entirely independently of each other, then the probability of seeing both  and  in a randomly picked document  is:

and the information content of such an event is:

With a small variation, this is exactly what is expressed by the IDF component of M25.