Orthogonal Negation in Vector Spaces for Modelling Word-Meanings and Document Retrieval

Orthogonal Negation in Vector Spaces for Modelling Word-Meanings and Document Retrieval Dominic Widdows ∗ Stanford University dwiddows@csli.stanford.edu Abstract Standard IR systems can process queries such as “web NOT internet”, enabling users who are interested in arachnids to avoid documents about computing. The docu- ments retrieved for such a query should be irrelevant to the negated query term. Most systems implement this by reprocessing re- sults after retrieval to remove documents containing the unwanted string of letters. This paper describes and evaluates a the- oretically motivated method for removing unwanted meanings directly from the orig- inal query in vector models, with the same vector negation operator as used in quan- tum logic. Irrelevance in vector spaces is modelled using orthogonality, so query vec- tors are made orthogonal to the negated term or terms. As well as removing unwanted terms, this form of vector negation reduces the occur- rence of synonyms and neighbours of the negated terms by as much as 76% compared with standard Boolean methods. By alter- ing the query vector itself, vector negation removes not only unwanted strings but un- wanted meanings. 1 Introduction Vector spaces enjoy widespread use in information retrieval (Salton and McGill, 1983; Baeza-Yates and ∗This research was supported in part by the Research Collaboration between the NTT Communication Science Laboratories, Nippon Telegraph and Telephone Corpo- ration and CSLI, Stanford University, and by EC/NSF grant IST-1999-11438 for the MUCHMORE project. Ribiero-Neto, 1999), and from this original appli- cation vector models have been applied to seman- tic tasks such as word-sense acquisition (Landauer and Dumais, 1997; Widdows, 2003) and disambigua- tion (Sch¨utze, 1998). One benefit of these models is that the similarity between pairs of terms or between queries and documents is a continuous function, au- tomatically ranking results rather than giving just a YES/NO judgment. In addition, vector models can be freely built from unlabelled text and so are both entirely unsupervised, and an accurate reflection of the way words are used in practice. In vector models, terms are usually combined to form more complicated query statements by (weighted) vector addition. Because vector addition is commutative, terms are combined in a “bag of words” fashion. While this has proved to be effective, it certainly leaves room for improvement: any gen- uine natural language understanding of query state- ments cannot rely solely on commutative addition for building more complicated expressions out of primi- tives. Other algebraic systems such as Boolean logic and set theory have well-known operations for building composite expressions out of more basic ones. Set- theoretic models for the logical connectives ‘AND’, ‘NOT’ and ‘OR’ are completely understood by most researchers, and used by Boolean IR systems for as- sembling the results to complicated queries. It is clearly desirable to develop a calculus which com- bines the flexible ranking of results in a vector model with the crisp efficiency of Boolean logic, a goal which has long been recognised (Salton et al., 1983) and attempted mainly for conjunction and disjunc- tion. This paper proposes such …

Content truncated to 500 words