Experiment and Evaluation in Information Retrieval Models

K. Latha

• Publisher: Chapman and Hall/CRC
• Year: 2017
• ISBN:
  9781315392608
• Edition: 1
• Topic: Computer Science
• Subtopic: Databases
• Index: Computer Science

Experiment and Evaluation in Information Retrieval Models explores different algorithms for the application of evolutionary computation to the field of information retrieval (IR). As well as examining existing approaches to resolving some of the problems in this field, results obtained by researchers are critically evaluated in order to give readers a clear view of the topic.

In addition, this book covers Algorithmic Solutions to the Problems in Advanced IR Concepts, including Feature Selection for Document Ranking, web page classification and recommendation, Facet Generation for Document Retrieval, Duplication Detection and seeker satisfaction in question answering community Portals.

Written with students and researchers in the field on information retrieval in mind, this book is also a useful tool for researchers in the natural and social sciences interested in the latest developments in the fast-moving subject area.

Key features:

Focusing on recent topics in Information Retrieval research, Experiment and Evaluation in Information Retrieval Models explores the following topics in detail:

• 
  
  

• Searching in social media

• 
  
  

• Using semantic annotations

• 
  
  

• Ranking documents based on Facets

• 
  
  

• Evaluating IR systems offline and online

• 
  
  

• The role of evolutionary computation in IR

• 
  
  

• Document and term clustering,

• 
  
  

• Image retrieval

• 
  
  

• Design of user profiles for IR

• 
  
  

• Web page classification and recommendation

• 
  
  

• Relevance feedback approach for Document and image retrieval

Section IV

Model Formulations of Information Retrieval Techniques

8

TABU Annealing: An Efficient and Scalable Strategy for Document Retrieval*

This chapter presents a new method, TABU annealing, which reduces the limitations of TABU and simulated annealing (SA) and shows the results of some comparative studies that evaluated the relative performance of different optimization techniques on the same problem.

8.1Simulated Annealing

Simulated annealing allows moves in less good goal directions once in a while to escape local minima. Annealing is the process of cooling material in a heat bath. If the solid material is heated past its melting point and then cooled down in a solid state, the structural properties of the cooled solid depend on the rate of cooling. Slow cooling leads to strong, large crystals. Fast cooling results in imperfections.

We have a problem with maximization over a set of feasible solutions and a relevancy function f calculated for all feasible solutions. The optimal solution could be calculated by exhaustively searching the space, calculating f(s), and selecting the maximum. In practice, the feasible solution space is often too large for this to be practical. Local optimization solves this by searching only a small subset of the solution space. This can be achieved by defining a neighborhood structure on the space and searching only the neighborhood of the current solution for an improvement. If there is no improvement, the current solution is an approximate optimal solution. If there is an improvement, the current solution is replaced by the improvement, and then the process is repeated. In simulated annealing, the neighborhood is searched in a random way. Accept a neighbor whose relevancy is worse than the current solution depending on a control parameter called a temperature.

Metropolis Monte Carlo et al. (1953) first proposed the standard simulated annealing approach. Metropolis proposed the equation of state calculations by fast computing machines. Then the Metropolis Monte Carlo integration algorithm was generalized by the algorithm of Kirkpatrick et al. (1982) to include a temperature schedule for efficient searching. It is reported that SA is very useful for several types of combinatorial optimization to reduce the computation time. The minimum temperature is generally determined by the acceptance ratio during the SA process—that is, the temperature is decreased until the system freezes. Jonathan Rose et al. (1990) proposed a new method for estimating the maximum temperature by using equilibrium dynamics, and Romeo et al. proposed an efficient cooling method, but these methods use experimental parameters, and tuning of these parameters is necessary.

An annealing algorithm needs four basic components:

1.Configurations: A model of what a legal selection (configuration) is. These represent the possible problem solutions over which we will search for a good answer.

2.Move set: A set of allowable moves that will permit us to reach all feasible patterns and one that is easy to compute. These moves are the computations we must perform to move from pattern to pattern as annealing proceeds.

3.Fitness function: To measure how well any given pattern is.

4.Cooling schedule: To anneal the problem from a random solution to a good, frozen placement; specifically, we need a starting hot temperature (or a heuristic for determining a starting temperature for the current problem) and rules to determine when the current temperature is low, by how much to decrease the temperature to low, and when annealing should be terminated.

8.1.1The Simulated Annealing Algorithm

1.Select an initial temperature t0 (a large number).

2.Select an ...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Contents
• Preface
• Acknowledgments
• About the Author
• Section I: Foundations
• Section II: Preliminaries
• Section III: Demand of Evolutionary Algorithms in IR
• Section IV: Model Formulations of Information Retrieval Techniques
• Section V: Algorithmic Solutions to the Problems in Advanced IR Concepts
• Section VI: Findings and Summary
• Appendix: Abbreviations, Acronyms and Symbols
• Bibliography
• Index