The performance of an information retrieval system is usually measured in terms of two di erent criteria, precision and recall. This way, the optimization of any of its components is a clear example of a multiobjective problem. However, although evolutionary programming have been widely applied in the information retrieval area, in all of these applications both criteria have been combined in a single scalar tness function by means of a weighting scheme. In this paper, we deal with using of Genetic Programming in Information retrieval specially in optimizing of a Boolean query.
Ever since the advent of the public network Internet, the quantity of available information is rapidly rising. One of the most important uses of this public network is to nd suitable information for such user query request. In such a huge and unstable information collection, todays greatest problem is to nd relevant information to the user query.
Information ltering is concerned with nding information from unstable collections of documents such as the Internet. In the information ltering domain, the user query does not consists of a list of words or terms (word and term have the same meaning in our work) to search for but rather of combinations of words extracted from various examples. The most important problem to solve is to optimize the signi cance of the user query and obtaining accurate collection statistics for calculating the term arity.
After using evolutionary techniques for single-objective optimization during
more than two decades, the incorporation of more than one objective in the
tness function has become a popular area of research for multiobjective problems.
The use of evolutionary algorithms to solve problems with multiple objectives
(known as Multi-objective Optimization Problems) has attracted much attention
[
An information retrieval system is basically constituted of three main
components: documentary database, query subsystem and matching or evaluation
mechanism [
Evaluation of the information retrieval system, measured by e ectiveness, two
statistics are used precision and recall, where these measures are evaluated over
a set of documents called a collection of documents. All documents in this
collection of documents are divided into four subsets: Relevant set "set of documents
that are relevant to the user query"; Retrieved set "set of documents that are
returned to the user"; and Relevant-Retrieved set "set of documents that are
retrieved and relevant to the user query"; and nally the rest set of documents
"set of documents that are not relevant and not retrieved". Where precision is
the percentage of the retrieved documents that are relevant to the user query
and recall is the percentage of the relevant documents that are retrieved for the
requested query [
Recall = RelevantRetrieved
Relevant
P recision = RelevantRetrieved
Retrieved
In our work we introduce to use Genetic Programming for implementing the Information Retrieval system with Boolean queries, trying to evolve Boolean queries by genetic programming. 3
Most of the search engines in the internet depend on the user query and operate
an information retrieval system to get the response of the user query request.
Where the user query consists of set of terms and set of logical operators;
especially and, or, of, and not operator see [
Genetic Algorithm is an algorithm that used to nd approximate solutions
to problems that were di cult to solve it through set of methods or techniques
inheritance or crossover, mutation, natural selection, and tness function that
are principles of evolutionary biology in computer science. For more detail about
Genetic Algorithms see [
This section will present the implementation of information retrieval using
genetic programming (for SQL we can see [
F : D
T ! [0; 1]
De ning a query will be combination from set of terms and set of Boolean
operators and, or, of and not. The query set Q is de ned as set of queries for
documents, de ne the query processing mechanism by which documents can be
evaluated in terms of their relevance to a given query [
Note: The of operator has the following general form:
N of(w1; w2; w3; : : : ; wM ); M
N and works like this: the document will be retrieved when it contains at least N terms from the list of M terms. For an example,
2 of(w1; w2; w3) = ((w1 and w2) or(w1 and w3) or(w2 and w3))
In this work, we develop genetic programming for implementing GA operators with variable length of chromosomes and mixture symbolic of information, like real values and Boolean queries values.
Each chromosome from the initial population represented a tree structure for one query; an index was de ned for each node in the tree. Genetic operators were operated over individuals. Queries will be encoded as trees, where each chromosome contains set of genes, and each gene mention to be a node in a tree and the value for each node known as allele. An example that show query encoding for chromosome in the population shown in Figure 1.
Genetic operators used in our work to evolve Boolean queries. Presenting for these operators Fitness, Selection, Crossover, and Mutation follows:
For each individual the value of precision and recall will be computed and known
as tness values see RecallF itness and P recisionF itness respectively, this
depends on the number of relevance documents rd in the collection of documents
to the user query, number of retrieved document fd, and and are arbitrary
weights. Where and are added specially to precision tness function [
ReallF itness =
Pd[rd
fd]
Pd[rd] P recisionF itness =
Pd[rd
Pd[rd] fd] +
Pd[rd
Pd[fd] fd]
Two individuals with best tness values are chosen from a population, but if there are more than two individuals with the same highest tness values, then two of them will be chosen randomly. The two selected chromosomes will be called parents and they will be used to produce two new o springs.
O springs must have some inheritance from the two parents; single point crossover will do that by exchange subtree from parent1 with subtree from parent2. Positions for exchanging subtree1 and subtree2 will be select randomly. In our work we de ne the selection of the position for subtree to be: 1. The root node of the tree. 2. Each Boolean operator node. 3. Each leaf from the tree.
Producing two new o springs from implementation of a single point crossover
was shown as an example in Figure 2.
Mutation, random perturbation in the chromosome representation, is necessary
to assure that the current generation is connected to the entire search space,
and it is necessary to introduce new genetic material into a population that has
stabilized level [
Each node from the new o springs may be mutated; that depends on mutation value (by default 0:2). And we work with di erent type of mutations shown below: { Mutation on Boolean operator: randomly exchanging one operator to another but both must be from the same arity, such as any exchange in ( and, or, of and not) are allowed. { Mutation on term node or leaf node: changing one term selected randomly from the o spring by any another one but the other one will be one from: The terms in a given collection of documents The terms in an initial population.
A speci ed list of terms.
The terms appeared in the user query. { Mutation by inserting or deleting unary operator between two nodes in the o spring.
Where mutation was implemented on this way: For generated o spring select one node randomly and for this node we have two possibilities to mutate into another one or to apply insert an unary operator before it or delete it if and only if this node is an unary operator. Some examples were shown for mutations in Figure 3. Presenting our work now to show how our research processed for Boolean queries evolutionary learning was done. We developed a genetic programming to process some experiments over a set of Boolean queries and various collections of documents; the documents are with various number of words or terms. All collections used in our experiments are described in Table 1, where collection 'Collection-1' consists of 10 di erent documents and 30 di erent words, where each document includes some of these words (one, two or more of them).
For all of our experiments were used the following ten Boolean queries as an initial population for processing our genetic programming: 2 of(w2; w8) 1 of(w1; w2; w8) not(not w13 and not w8) (w1 and(w2 and w8)) or not(w4 or w2) not(w1 or w2) and((w5 or w4) and(w3 and w6)) (w9 and w14) (not w14) and w1 (w2 or w6) or(w8 and w13) (w3 and w4) or((w12 xor w15) and w8) (w2 or w8) or(w1 and w2)
The Genetic programming execution was terminated when one or more chromosomes from the population reached the highest value of the selected tness function, or when reaching a maximum number of generations, where the highest values for precision and recall are + and 1 respectively.
All experiments were done multiple times with the same options to see the di erences in the results, because of probability used during genetic programming process. In all experiments were used following xed options: { the arbitrary weights for { crossover value = 0.8 = 0:25, and = 1:0 6.2
Mutation value is probability of applying mutation operator on o springs. In these experiments we observed how the changes of mutation value a ect the result of genetic programming process, where we used di erent types of mutation as described above and two di erent sets of options where implemented on our experiments.
{ User query is:- (w6 and w8) and not w10 { Collection name is:- Collection-1 { Used tness measures are:- precision or recall { Highest number of generations are: - 200 generations.
All terms from the initial population were used for mutation on leaves, the results were shown in table 2. Where in all experiments the chromosomes tness values in the nal population reached to be highest value, and the same for recall tness value is the highest too, where the number of generations was variant.
All terms from the user query were used for mutation on leaves, and the results were shown in Table 3. In this case, mostly maximum number of generations were reached to obtain the optimized query, because of not reaching the highest value on the selected tness function, when the highest values for recall were reached.
All terms form the whole collection were used for mutation of leaves, and the results were shown in Table 4. Where in some experiments the termination of the program execution was done because of reaching the maximum number of generations or reaching the highest precision tness value, where mostly in all experiments we reached the highest values for recall tness values. All chromosomes in the nal population had approximately the same highest value of recall, but mostly the values of precision are various, some of these results are shown in tables bellow. Table 5 shows the results when the mutation over leaves used terms from user query only, table 6 shows the results when the mutation over leaves used terms from initial population, and table 7 shows the results when the mutation over leaves used terms from whole population.
From these results shown in tables 5, 6 and 7 the executions of program were terminated when the highest recall tness function values of chromosomes were reached within few number of generations.
Some experiments were done using the second set of options with the following results shown in Table 8 and 9.
{ User query is:- ((not w10) and(w6 and w8)) { Collection name is:- Collection-2 { Used tness measures are:- precision or recall { Highest number of generations are: - 1200 generations.
After increasing number of generations and experiments were done on Collection2, there were a di erences in the results because in some cases we reached the best solution depends on precision tness function as shown in table 8 before, where the results in table 9 shown before mostly all experiments were reached the highest value of recall within a few number of generations.
The goal of optimization process of a Boolean query is to get a query with highest possible values of precision or recall depends on chosen tness function. Results shown above demonstrate, that when we used recall as the tness function, the program terminated within few number of generations because of reaching the highest value of recall as a tness function, and when using precision as the tness function recall has reached the highest value mostly in all experiments, where some of precision values were not high. 7
In this paper, an optimization of Boolean query over a collection of documents is presented. We focused especially on di erent types of mutation and on comparison of two di erent tness measures, precision and recall. Experiments were done over various types of document collections and di erent types of mutation and two types of tness functions. So we obtained the following conclusions:
First, when applying mutation operator on terms in the chromosomes from the initial population, it is necessary to have all the terms from the search space at disposal for mutation. If only terms from user query or initial population were used for mutation, the results were worse than when terms from whole collection were used. Only then there can come into existence new queries, describing the same documents as user query, but containing terms not included into user query or initial population.
Second, recall seems to be more e cient than precision when chosen as a tness function to reach an optimized query within less number of generations than when precision was chosen as a tness function. So we retrieved all relevant documents with few number of non-relevant documents. But on choosing precision as a tness function, we reached mostly the highest values of recall before program termination when the highest values of precision were mostly not reached and the process terminated after reaching maximum number of generations.
Third, in some cases, especially when we used for mutation over leaves the terms from collection or from initial population on two di erent types of tness functions an optimized query was reached within few number of generations, but on chosen recall as tness function the results were reached within less number of generations than when precision was used as a tness function. But for mutation over leaves the terms from user query only and the tness function was precision there were worse results than in other cases.
We will focus in our future work on weighted terms and weighted Boolean operators for implementing the fuzzy logic over terms and Boolean operators weights for optimizing user query in information retrieval systems, and also on using di erent methods for evaluating the performance of information retrieval such as Harmonic mean measure (F-score). We also want to consider the number of Boolean operators and the number of terms as the objectives for query optimization.