Ranked Retrieval With Semantic Networks And Vector Spaces

Kulyukin

Ranked Retrieval with Semantic Networks and Vector Spaces

Vladimir A. Kulyukin[(] and Amber Settle

School of Computer Science, Telecommunications, and Information Systems,

DePaul University, 243 South Wabash Avenue, Chicago, IL 60604

(312) 362-5173, Fax: (312) 362-6116

{vkulyukin, asettle}@cs.depaul.edu

The equivalence of semantic networks with spreading activation and vector spaces with dot product is investigated under ranked retrieval. Semantic networks are viewed as networks of concepts organized in terms of abstraction and packaging relations. It is shown that the two models can be effectively constructed from each other. A formal method is suggested to analyze the models in terms of their relative performance in the same universe of objects.

1. Introduction

Ranked retrieval plays an important role in information retrieval (IR) and natural language processing (NLP). In IR, the closest match to a query is often chosen by ranking the database objects by their similarity to the query (Aalbersberg, 1994; Salton & McGill, 1983). Many IR systems retrieve objects from a universe represented as a vector space whose dimensions are the features of the retrievable objects, e.g., terms found in document collections (Salton & McGill, 1983). The ranking functions in these systems utilize feature frequency counts (Salton & Buckley, 1991), boolean feature combinations (Bradshaw, 1998), or probabilistic feature distributions (Bookstein, Klein, & Raita, 1998; Kulyukin, 1998). In NLP, the best interpretation of an input is frequently selected by ranking the interpretations induced by the input in the available knowledge base (Riesbeck, 1983; Norvig, 1986; Martin, 1993; Kulyukin, 1998). Many NLP systems retrieve objects from a universe represented as a semantic network (Quillian, 1969). The ranking functions in these systems utilize numerical spreading activation levels (Charniak, 1983), shapes of activation paths (Quillian, 1969; Norvig, 1986), or node activation sequences (Martin, 1993; Fitzgerald, 1995).

The rapid proliferation of electronic data prompted numerous empirical comparisons of semantic networks and vector spaces under ranked retrieval. However, the existing empirical results are frequently inconsistent with each other. While some studies show semantic networks outperforming vector spaces (Chakravarthy & Haase, 1995), other studies argue the opposite (Salton & Buckley, 1991). While some studies find that combining vector spaces with semantic networks leads to improved performance (Kulyukin, 1998; Kulyukin, 1999), others either claim that performance worsens (Voorhees, 1994) or report no significant differences (Ruge, 1995).

Since in many empirical investigations performance takes priority over deliberation and analysis, little light is shed on the fundamental retrieval capabilities of semantic networks and vector spaces under ranked retrieval. The focus on performance leads to the treatment of both models as black boxes mapping inputs to outputs. Consequently, it is hard to decide whether a given difference in performance is attributable to a property of one model and lack thereof in the other or to a property of the evaluation data sets and relevance judgments.

To complement the results of empirical studies, the authors have developed a framework for analyzing the fundamental capabilities of retrieval models under ranked retrieval. The framework is presented in four steps. First, a formalism is presented for ranked retrieval from a universe of objects. Second, the formalism is applied to the semantic network model with spreading activation and the vector space model with dot product. Third, it is shown that the two types of models can be effectively constructed from each other in the same universe of objects. Fourth, a formal method is suggested to analyze the two models in terms of their relative performance in the same universe of objects.

2. Formalism

In this section, a formalism is presented for ranked retrieval from a universe of objects. The presentation is arranged as a sequence of definitions so that the reader, if necessary, can come back to this section in order to clarify statements in the subsequent sections of the paper.

2.1. Basic definitions

Let ? and à denote real and natural numbers, respectively. All subscripts are in à, unless otherwise specified.

If S is a set, 2 S denotes its power set, i.e., the set of all subsets of S, and |S| denotes its cardinality. The subset relationship is denoted by í. The logical if is denoted by T; the logical if and only if is denoted by ? or iff.

If V is a vector space, dim(V) denotes the dimension of V. For example, if V is a plane, dim(V) = 2.

Elements forming a sequence are written inside a pair of matching square brackets: [e0, ..., en]. The empty sequence is written as [].

Elements forming a set are written inside curly braces: {e0,...,en}. The empty set is written as {} or ?.

Elements forming a vector are written inside angular brackets: <e0,...,en>.

Thus, [0,1,2], {0,1,2}, <0,1,2> denote a sequence, a set, and a vector, respectively.

If v is a variable, {v}, [v], , v denote that v is bound to a set, a sequence, a vector, and an element, respectively. For example, {v} = {0,1,2}; [v] = [0,1,2]; = <0,1,2>; v = 1. Furthermore, {v i} denotes a set of one element v i; {v}i denotes the i-th set of elements; [v i] denotes a sequence with one element v i; [v]i denotes the i-th sequence of elements.

If S is a set, [S] is the set of all possible sequences over S such that no sequence in [S] contains duplicate elements. For example, if S = {0, 1}, [S] = {[0], [1], [0, 1], [1, 0]}. The sequences [0, 0] and [1, 1] are not in the set, because they contain duplicates. If S is finite, the length of the longest sequences is equal to |S|. If S is infinite, each sequence in [S] is still finite. In other words, [S] contains all sequences of length 1, 2, 3, etc.

If S is a set, [S]+ is the set of all possible sequences over S. The difference between [S] and [S]+ is that the latter contains sequences with duplicates, while the former does not.

A sequence [s]0 completes another sequence [s]1 = [e0, ..., en] iff [s]0 = [v]0 + [e0] + [v]1 + [e1 ] + … + [v]n + [en] + [v]n+1, where [v]j are subsequences of [s]0, where 0 ￡ j ￡ n+1 and the + operator denotes string concatenation. For example, if [s]0 = [e0, e1, e2, e3], [s]1 = [e0, e2], and [s]2 = [e2, e1], then [s]0 completes [s]1, but does not complete [s]2.

2.2 Ranked retrieval definitions

An object is a 2-tuple [o i, ], where o i ? I = {o j | j ? à} is the object's unique id, and is the object's set of representations. The definition of representation depends on specific retrieval tasks. For example, objects can be represented as vectors of reals or as nodes in a semantic network.

A retrieval model M operates in a universe of objects. The universe is the set of all objects, and is denoted by W.

M's primitives are called tokens. The definition of token is context-sensitive. For example, tokens can be keywords, keyword collocations, or nodes in a semantic network. The set of all possible tokens is denoted by T.

M's representation function is a one-to-one function l: I x 2 T ? 2R, where R is M's set of representations. It is certainly possible to define many-to-one representation functions[1]. For example, in the vector space context, one can define functions that map several different document identifiers to the same vector of weights constructed from the documents’ texts. Such many-to-one representational functions can be used in, for example, document clustering. However, many-to-one functions are not suited for ranked retrieval due to the representational ambiguity they generate. For, if several documents are mapped into the same representation, there is no principled way to rank the documents in response to a given query that matches the shared representation.

Formally, one can ensure that M’s representation function is one-to-one through the uniqueness of object ids, i.e., elements of I. Given a representation function l1, it is possible to define a one-to-one representation function l2 such that l1 and l2 are representationally equivalent, i.e., they map the same object ids to the same representations. The construction is suggested in the following lemma.

Lemma. Let l1 be a representation function. There exists a one-to-one function l2 representationally equivalent to l1.

Proof. Let oi ? I and P í T. Let l1(oi, P) = S í R. Define l2: I x 2 T ? I x 2R such that

l2(oi, P) = [oi , S]. By definition, l2 is one-to-one, and is representationally equivalent to l1. ?

The finite set of objects retrievable by M is denoted by L ì W. Formally, L = {[oi, S] | l(oi, T) = S, S í R}. When the second element of every object in L is a singleton, i.e., a set of one element, the set notation is dropped for the sake of simplicity. Thus, L = {[oi, r] | l(oi, T) = r}.

While an object's id is unique in the universe, the object's representation is unique only within a model. Two different models may represent the same object differently.

Let LI = {oi | [oi, ri] ? L}. Since there is a bijection between L and LI, L and LI are used interchangeably, and the objects are referred to by their ids, i.e., the elements of LI.

The token weight function w: I x I è T ? ? assigns weights to tokens in objects.

The object similarity function s: W x W ? ? computes the similarity between two objects in W. The object similarity function operates on the representations of objects. For example, when two different retrieval models receive a free-text input, they use their representation function to construct the representation of the input and to match that representation against the representations of the retrievable objects.

The rank function r: W x W ? à imposes an ordering on L's objects. The rank of oi ? L with respect to oq ? W is denoted by r(oi, oq).

An object ok has a smaller rank than an object oi with respect to a query object oq if either the similarity between ok and oq is greater than the similarity between oi and oq or if the similarities between oi and oq and ok and oq are the same, but k is less than i. Formally, if r(oi, oq) = x ? à, then " ok ? L {{r(ok, oq) < x} ? {s(ok,oq) > s(oi,oq)} ú {s(ok,oq) = s(oi,oq) ù k < i}}, and " oj ? L {{r(oj, oq) > x} ? {s(oj,oq) < s(oi,oq)} ú {s(oj,oq) = s(oi,oq) ù i < j}. Thus, the ranking of the objects in L is determined by s, i.e., their similarity to the query object oq, and their initial ordering in L. Note that, since L ì W, the definition of the rank function does not assume that the query object comes from the same set as the retrievable objects being ranked with respect to it. The set of query objects and the set of retrievable objects may overlap, but they are not the same.

Given the above definitions, the formal definition of the retrieval model M is as follows: M = [W, L, T, l, w, s].

N-ary relations on objects are represented as n-dimensional bit arrays. For example, a binary relation is represented as a matrix whose rows and columns are objects and whose entries are 0's and 1's, depending on whether the relation holds between a given pair of objects.

A retrieval sequence returned by M in response to oq ? W is denoted by M(oq), and is a permutation [,, ..., ] of the ids of objects in L such that p(i) < p (j) ? r(oi, oq) < r (oj, oq).

Two retrieval models M0 = [L0, T 0, l0, w 0, s0] and M1 = [L1, T 1, l1, w 1, s1] are comparable iff L0 = L1 and T 0 = T 1. Otherwise, M0 and M1 are incomparable.

The intuition behind the requirements L0 = L1 and T 0 = T 1 is best explained with an example. Suppose one wishes to compare two implemented retrieval models under ranked retrieval. A commonly accepted way of comparison is to select a database of retrievable objects, e.g., documents or images, and to compare the performance of the two models on the same set of query objects (Harman, 1993). The requirement L0 = L1 ensures that the models retrieve from the same set of retrievable objects. The requirement T 0 = T 1 ensures that the models operate on the same set of tokens, e.g., terms found in the database documents. The models will, of course, build different representations from the same token set. One model may, for example, eliminate from consideration all tokens found on a precompiled stoplist, while the other model may eliminate tokens on the basis of their frequencies or distribution patterns in a given collection. Furthermore, both models can, through their representation functions, extend the original set of tokens with additional tokens, e.g., phrases or term collocations found in the test documents. However, these extensions do not change the fact that both models are exposed to the same token set both when building representations for retrievable objects and when matching query objects against those representations. To summarize, comparisons of different models are meaningful only when made with respect to the same universe over the same inputs.

Let M0 = [L0, T 0, l0, w 0, s0] and M1 = [L1, T 1, l1, w 1, s1]. M0 and M1 are equivalent under ranked retrieval, M0 M1, iff they are comparable and " oq ? W {M0(oq) = M1(oq)}. In other words, two models defined over the same set of objects and tokens are equivalent under ranked retrieval if and only if they retrieve identical sequences of objects in response to every query. Since the standard precision and recall metrics are functions of the ranked retrieval lists, the definition of model equivalence implies that equivalent models have the same precision and recall.

A common evaluation technique used on implemented retrieval models is the retrieval time over a given test collection. However, the retrieval time is a derivative of a particular implementation, and, as a consequence, is not a good measure of model equivalence. Retrieval models can be implemented in different ways and on different hardware platforms. While the retrieval times of different implementations may well vary, the fundamental retrieval capabilities of the models realized in the implementations will remain the same under ranked retrieval.