NEURAL NETWORKS AS QUERIES FOR LINEAR AND NON-LINEAR RETRIEVAL MODELS

Pawan Lingras
Department of Mathematics and Computing Science
Saint Mary's University, Halifax, Nova Scotia, Canada, B3H 3C3
and
Y. Y. Yao
Department of Computer Science
University of Regina, Regina, Saskatchewan, Canada, S4S 0A2

ABSTRACT

This paper outlines a neural network based query formulation designed to simplify the document search process. The proposed approach receives a query involving keywords from the user. A sample of documents is retrieved based on this query. The user is asked to rank the documents from the sample according to the order of relevance. The neural network learns the information needs of the user from the relevance feedback. The documents from the entire collection are then ranked according to the learned information needs. Depending on the type of neural network used, the information needs are represented in linear or non-linear form.

INTRODUCTION

Information retrieval is an important issue in the modern information age. A huge amount of information is now available to the general public through the advent of the Internet and other related technologies. Previously, the information was made available through experts such as librarians, who helped general public analyze their information needs. Because of enhanced communication facilities, the general public can access various documents directly from their desktop computers without having to go through a human expert. The modern information retrieval systems need to assist the general public in locating the relevant documents.

An Information Retrieval (IR) system identifies the relevant documents in response to a user's information request. Many retrieval models [3][4] have been proposed for this purpose. A list of keywords is one of the most primitive representations of information needs. More sophisticated techniques use the Boolean operators such as AND, OR, NOT. Some of the other information retrieval techniques allow the users to attach weights to the keywords based on the level of importance [4]. Among these, the linear models are perhaps best known.  A linear decision function, the cosine similarity measure, was first used in the vector space model [4].  Another linear system is the binary probabilistic independence model [3].  Both of these models and their variants have been studied extensively [2]-[9].  The main advantage of a linear model lies in its simplicity. However, the linear form may not always effectively represent user's information needs.

Use of Boolean operators or linear queries based on keywords can be difficult for a novice user. Some of the research in information retrieval describes various ways of learning the weighted query from a user [7][8]. In particular, Wong and Yao [8] used perceptrons - simple neural networks - for learning linear queries. The present study extends Wong and Yao's approach using multi-layered neural networks. The query learned from the relevance feedback is stored in the form of a trained neural network. 

This paper establishes the basis for the use of neural networks, as representation of the user information needs. The approach expects a user to supply a list of keywords. The user has the option of associating weights with the keywords. The initial query from the user is used to create a sample of documents. The user is expected to browse the sample of documents and rank them based on her information needs. The sample documents are used by a neural network to learn information needs of the user. The trained neural network represents the user query. The trained neural network is applied to all the documents in the collection.

The approach proposed in this paper is a significant variation from the traditional approach, where the user queries are always represented in a simple mathematical form usually obtained from the user. There are two disadvantages to this traditional approach. The user may not be able to specify his information needs in the mathematical form, because he is either not comfortable with the mathematical form or the mathematical form does not provide a good representation of his information needs. Artificial neural networks (ANN), which try to emulate processes in a human brain, may serve as a better representation of user's information needs. Such an approach is particularly useful for the web based client/server architecture, where information agents residing on the clients can personalize themselves based on user needs.

The design of neural networks for information retrieval is outlined in the next section. The distinction between perceptrons and multi-layered neural networks is also elucidated. Perceptrons are shown to represent a linear representation of user's information needs. The multi-layered neural networks, on the other hand, do not provide a simple mathematical representation of the query. A summary and suggestions for future research appears in the last section. 

NEURAL NETWORKS AS QUERIES

The perceptron learning approach proposed by Wong and Yao [8] is theoretically sound adaptive query formulation for linear retrieval models. The users may find it somewhat time consuming to specify the preference relations between every pair of documents. Moreover, the preference relationships specified by the user may not obey the axioms specified by Wong and Yao for the existence of a perceptron. Nonetheless, Wong and Yao's sound theoretical approach provides a basis for further development. 

In the proposed approach, the user is asked to specify a list of keywords. The user has a choice of specifying weights for these keywords. A sample can be retrieved based on this preliminary query. The user then provides a ranking of the documents by attaching a relevance index between 0 and 1. A relevance index of 0 means the document is irrelevant to her. A relevance index of 1 means the document is most suited to her information needs.

A neural network is then trained based on the user supplied relevance indices. A sample neural network is shown in FIG. 1.

Relevance
Index

Web
Search

Information
Retrieval

Intelligent
Agents

Neural
Networks

FIG. 1 Neural Net for a User Query

The neural network consists of input, hidden and output layers of neurons. Input layer neurons correspond to the keywords used in the retrieval. There is one output neuron that outputs the relevance index for a document. The hidden layer is optional. If the hidden layer is omitted, the neural network reduces to a perceptron used by Wong and Yao [8].

The neural network shown in FIG. 1 will be used, if a user were interested in documents related to the four keywords: Web search, Information Retrieval, Intelligent Agents and Neural Networks. These four keywords are used to retrieve a sample of documents from the document collection. Typically, the sample will consist of 10 to 20 documents, . A document  will be represented as a four dimensional vector: 

,	(1)	

where  is the weight of  jth keyword in ith document.

Document vectors  serve as the inputs to the neural network during the training process. For each document , there is a corresponding user supplied relevance index . The relevance index  is the desired output of the neural network for the input vector . During the training process, the neural network adjusts weights of its connections to approximately match the output to  for a given input . The trained network represents the query that is applied to the larger document collection D. Each document , is also represented as a four dimensional vector similar to the documents in the sample. For a given document vector d, the output r of the neural network will be used as the relevance index for ranking d.

The mathematical representation of a trained multi-layer neural network is difficult. However, neural networks were developed with the intentions of emulating human thought process. The user information needs are stored in a biological neural network in his brain. Representing such information needs using an artificial neural network may prove to be an effective information retrieval strategy. 

If one uses a perceptron instead of general multi-layer neural network, a simple mathematical representation of the information needs may be possible. FIG. 2 shows a perceptron that can be used for learning user's information needs. As before, it is assumed that the user has supplied the four keywords: Web search, Information Retrieval, Intelligent Agents and Neural Networks. The weight is the weight of the connection between the output neuron and jth keyword. The process of training such a perceptron is the same as a general neural network. The trained perceptron represents the user query or information needs. The output of the perceptron can be easily represented in terms of a input vector as:
,	
(2)	

where f is a transfer or output function. If , the trained perceptron can be represented by a linear query  that can be used in the vector space model [4].

Relevance
Index

Web
Search

Information
Retrieval

Intelligent
Agents

Neural
Networks

FIG. 2 Perceptron for a User Query

w1

w2

w3

w4

SUMMARY AND FUTURE RESEARCH

This paper describes a neural network based approach for information retrieval. The approach retrieves a sample of documents based on keywords supplied by the user. The user ranks the documents from the sample by associating a relevance index for each document. The sample documents along with the relevance indices provided by the user are used to train a neural network. The trained neural network represents the user query. The input vectors and sample collection are small enough to make the training process reasonably quick. The trained neural network is applied to the rest of the documents in the collection.

The proposed design is intended to be the first step in the development of personal information agents. Since neural networks attempt to mimic processes in a human brain, they may provide better models for representing the user information needs. As World Wide Web and other Internet tools become important (if not primary) sources of information, the proposed neural agents can be further enhanced to track user's information preferences. 

Initial implementation of the proposed approach is currently underway for enhancing the retrieval performance of a search engine. The initial query from the user will be modified based on specification requirements for a search engine such as Altavista [1]. The list of documents obtained from the search engine will be re-indexed based on the keywords supplied by the user. A sample of documents from the list supplied by the search engine will be used to train a neural network. The trained neural network will re-rank the entire list of documents supplied by the search engine. The results of the proposed implementation will be published in a future publication.

REFERENCES

[1]	Altavista: Search Engine,  (1999), http://www.altavista.com.
[2]	Bollmann, P. and Wong, S.K.M., (1987), Adaptive linear information retrieval models, Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval.
[3]	Bookstein, A. (1983), Outline of A General Probabilistic Retrieval Model, Journal of Documentation 39, 63-72.
[4]	Salton, G. and McGill, M.H. (1983), Introduction to Modern Information Retrieval, McGraw-Hill, New York.
[5]	Raghavan, V.V. and Wong, S.K.M. (1986), A critical analysis of vector space model in information retrieval, Journal of the American Society for Information Science 37,  279-287.
[6]	Robertson, S.E. and Sparck Jones, K. (1976), Relevance Weighting of Search Terms, Journal of the American Society for Information Science 27, 129-146.
[7]	Rocchio, Jr. J.J. (1971), Relevance Feedback in Information Retrieval, in: Salton, G. (ed.), The SMART Retrieval System --- Experiments in Automatic Document Processing, Prentice-Hall, Englewood Cliffs, NJ.
[8]	Wong, S.K.M. and Yao, Y.Y. (1990), Query Formulation in Linear Retrieval Models, Journal of the American Society for Information Science 41(5), 334-341.
[9]	Yu, C. T. and Salton, G. (1976), Precision Weighting -- An Effective Automatic Indexing Method, Journal of the Association for Computing Machinery 23(1), 76-88.