extfieldsofstudy:
Computer Science
Medicine

text:
Is searching full text more effective than searching abstracts?

Background With the growing availability of full-text articles online, scientists and other consumers of the life sciences literature now have the ability to go beyond searching bibliographic records (title, abstract, metadata) to directly access full-text content. Motivated by this emerging trend, I posed the following question: is searching full text more effective than searching abstracts? This question is answered by comparing text retrieval algorithms on MEDLINE® abstracts, full-text articles, and spans (paragraphs) within full-text articles using data from the TREC 2007 genomics track evaluation. Two retrieval models are examined: bm25 and the ranking algorithm implemented in the open-source Lucene search engine. Results Experiments show that treating an entire article as an indexing unit does not consistently yield higher effectiveness compared to abstract-only search. However, retrieval based on spans, or paragraphs-sized segments of full-text articles, consistently outperforms abstract-only search. Results suggest that highest overall effectiveness may be achieved by combining evidence from spans and full articles. Conclusion Users searching full text are more likely to find relevant articles than searching only abstracts. This finding affirms the value of full text collections for text retrieval and provides a starting point for future work in exploring algorithms that take advantage of rapidly-growing digital archives. Experimental results also highlight the need to develop distributed text retrieval algorithms, since full-text articles are significantly longer than abstracts and may require the computational resources of multiple machines in a cluster. The MapReduce programming model provides a convenient framework for organizing such computations.

Background
The exponential growth of peer-reviewed literature and the breakdown of disciplinary boundaries heralded by genome-scale instruments have made it harder than ever for scientists to find and assimilate all the publications important to their research [1]. Thus, tools such as search engines are becoming indispensable. Motivated by the desire to develop more effective text retrieval algorithms for consumers of the life sciences literature, this study poses a straightforward question: Is searching full text more effective than searching abstracts? That is, given a particular information need expressed as a query, is the user more likely to find relevant articles searching the full text or searching only the abstracts? This question is highly relevant today due to the growing availability of full-text articles. In the United States, the NIH Public Access Policy now requires that all research published with NIH funding be made publicly accessible. More broadly, the Open Access movement for the dissemination of scientific knowledge has gained significant traction worldwide. These trends have contributed to the accumulation of full-text articles in public archives such as PubMed Central and on the websites of Open Access journal publishers. The growth of freely-available content represents a significant opportunity for scientists, clinicians, and other users of online retrieval systems -it is now possible to go beyond searching bibliographic data (abstract, title, metadata) in sources such as MEDLINE to directly search contents of the full text. Indeed, Zweigenbaum et al. [2,3] identified analysis of full-text articles as one of the frontiers in biomedical text mining.
To be clear, I refer to full-text search as the ability to perform retrieval on the entire textual content of an article (including its title and abstract), whereas abstract search refers to retrieval based only on abstract and title (similar to what is available in PubMed ® today). This work focuses on content-based searching only; experiments do not take advantage of metadata (e.g., authors, journal titles, MeSH ® descriptors), since they would presumably be available for both full-text and abstract searches.
Not surprisingly, there isn't a straightforward answer to the question posed in this study. I describe experiments with MEDLINE abstracts, full-text articles, and spans (paragraphs) within full-text articles using data from the TREC 2007 genomics track evaluation. The experiments examined two retrieval models: bm25 and the ranking algorithm implemented in the open-source Lucene search engine. Results show that treating an entire article as an indexing unit does not consistently yield higher effectiveness compared to abstract search. However, retrieval based on spans, or paragraphs-sized segments of full-text articles, consistently outperforms abstract search. Results suggest that highest overall effectiveness may be achieved by combining evidence from spans and full articles. These findings affirm the value of full text collections for text retrieval and provide a starting point for future work in exploring algorithms that take advantage of full text.
One important implication of this work is the need to develop scalable text retrieval algorithms, since full-text articles are significantly longer than abstracts. In the near future, the amount of available content will likely outgrow the capabilities of individual machines, thus requiring the use of clusters for basic processing tasks. I explore this issue with Ivory, a toolkit for distributed text retrieval built on top of Hadoop, an open-source implementation of the MapReduce programming model [4].

Related Work
Despite much optimism among researchers about the potential of full-text articles, it is not completely clear how present techniques for mining the biomedical literature, primarily developed for title, abstract, and metadata (e.g., MeSH descriptors), can be adapted to full text. For some tasks, full text does not appear to offer much beyond title and abstract. For example, consider the Medical Text Indexer (MTI), a production tool at the National Library of Medicine (NLM) that assists human indexers in assigning MeSH descriptors to MEDLINE citations based on title and abstract. Gay et al. [5] reported their experiences on extending MTI to base MeSH recommendations on full text. After much tuning and careful selection of article sections, a modest gain in effectiveness was achieved. However, the improvements were most likely "not worth the extra effort" (personal communication, Alan Aronson) and there are currently no plans to integrate full-text capabilities into the NLM article processing pipeline. Furthermore, it is unclear whether the particular treatment of article sections is generalizable beyond the relatively small set of articles examined in the study.
Other researchers have also tried to exploit information in full-text articles for various text mining tasks. For example, Yu et al. [6] used surface patterns to extract synonyms for gene and protein names, and reported higher precision on full text than on abstracts. More recently, Seki and Mostafa [7] explored an "inference network" approach to mining gene-disease associations. Taking advantage of full text yields a small gain in effectiveness (consistent with the MTI findings). However, the results were based on a small collection of articles and can only be characterized as preliminary. As with the MTI experiments, there remain questions about the generalizability of the results beyond those articles examined.
There is no doubt that a significant amount of information is contained in well-written abstracts. Journal requirements for structured abstracts assist authors in crafting highly-informative prose that covers the key aspects of their work. In the clinical domain, for example, Demner-Fushman et al. [8] showed that information in abstracts is sufficient to identify articles that are potentially useful for clinical decision support. In the biomedical domain, Yu [9] examined text associated with images in articles and concluded that sentences in the abstract suffice to summarize image content. In fact, she suggested that abstract sentences may actually be superior, since associated text in the article typically describes only experimental procedures and often does not include the findings or conclusions of an experiment. In a related study, Yu and Lee [10] discovered that 88% of s and 85% of tables can be summarized by sentences in the abstract, and that 67% of abstract sentences correspond to images in the full-text articles. These results demonstrate that, at least for some tasks, it is unclear what additional value full-text content adds beyond title, abstract, and metadata.
Additionally, researchers have compared the term content of abstracts with that of full text. Shah et al. [11] examined a collection of articles and found that abstracts were the richest source of relevant keywords. This finding was echoed by Schuemie et al. [12], who concluded that the density of useful information is highest in the abstract, but information coverage in full text is greater than that of abstracts. However, the practicality of mining full-text articles is unclear due to increased computational requirements. Both these articles focused on characterizing texts and did not examine the impact of abstract vs. full text on a text-mining task.
There has been much work on processing full-text content, for example, the automatic extraction of gene names and protein interactions in the BioCreative evaluations [13,14]. However, that body of research differs significantly from the goals of this study in that I am primarily interested in differences between full text and abstracts, and the impact of these differences on effectiveness in text retrieval. In gene identification and related information extraction tasks, the text collection is fixed, while researchers attempt to develop effective algorithms (as determined by some standard metric such as F-measure). Specifically, the tasks are designed in a manner such that the source of the text is not a relevant factor. Experiments in this article, on the other hand, focus both on algorithms and data.
The problem of retrieving sub-document segments of text has previously been explored in the information retrieval literature [15][16][17][18][19][20][21][22][23][24]; the task is often called passage retrieval. Recently, there has been substantial interest in XML retrieval, which shares many of the same issues as passage retrieval since XML documents naturally support retrieval at different granularities (i.e., every XML element is a potential result). The locus of research activity resides in the INitiative for Evaluation of XML Retrieval (INEX), an annual evaluation forum that began in 2002 [25]. For several years, the evaluation used a collection of XMLencoded journal articles from the IEEE Computer Society. Most relevant to this work, the genomics "track" at the 2007 Text Retrieval Conference (TREC) has explored passage retrieval in the life sciences domain. The overview paper [26] provides an entry point into that literature (also see Section 5.1). Experiments reported in this article used the test collection from the TREC 2007 evaluation.
There is one important difference between this work and the research discussed above. Whereas I ask the question "Is searching full text more effective than searching abstracts?", previous work simply assumes that the answer is yes. Research papers on passage retrieval often take for granted that retrieving passages provides value to the user. The INEX evaluations implicitly assume that retrieving XML fragments is desirable (although there have been studies that explore the validity of this assumption [27,28]). Since widespread availability of full text is a relatively recent phenomenon in the life sciences, and searching abstracts has been available for decades (and shown to be reasonably effective), it is worth questioning the premise that searching full text is inherently superior. Focusing on this question, however, certainly does not diminish the contributions of previous work: to the extent that full text is shown to be valuable for text retrieval in this specific domain, findings from related work can be leveraged to inform the development of full-text retrieval algorithms for the life sciences literature.

Comparison of Full Text and Abstracts
In comparing search effectiveness on full-text articles and abstracts, it makes sense to begin by discussing their characteristics and enumerating potential advantages and disadvantages. Such an analysis could guide the interpretation of experimental results.
Length is the most obvious difference between full-text articles and abstracts -the former provides systems with significantly more text to process. Most information retrieval algorithms today build on "bag of words" representations, where text is captured as a weighted feature vector with each term as a feature [29], or as a probability distribution over terms in the case of language modeling approaches [30,31]. These models derive from statistical properties such as term frequency and document frequency. More text could yield a more robust characterization of these statistics (for example, in the language modeling framework, longer documents require less smoothing). However, the potential downside is that full text may introduce noise. For example, an article may contain an elaborate discussion about related work that does not directly pertain to the article's main focus. Articles often contain conjectures (that turn out to be incorrect) or future work (which may or may not be fruitful lines of inquiry). In these cases, term statistics may be misleading due to the presence of "distractors" that dilute the impact of important terms. In contrast, abstracts focus on the key ideas presented in the articles and little else. Similar observations have been made with respect to collections of newswire documents (e.g., [17]). Many news stories are written about one central topic, but contain many aspects that are only loosely connected -in these cases, a global characterization of the entire document may not accurately capture what the article is "about".
Another challenge with full-text articles is the variety of formats in which they are distributed. Whereas there is a small number of formats for encoding MEDLINE abstracts, full-text collections can be found in XML, SGML, PDF, and even raw HTML (e.g., the result of Web crawls). Each format is associated with idiosyncrasies that make pre-processing a challenge. Just to give one example, there are numerous ways to encode Greek symbols (α, β, ...) -sometimes, they are directly encoded in extended character sets (e.g., Unicode); often, they are "written-out" (e.g., alpha, beta, ...); in other cases, they are encoded as HTML entities (e.g., α). The prevalence of special characters in the literature complicates seemingly simple tasks such as tokenization. The problem is further exacerbated when one tries to combine full-text collections from different sources (in different formats).
Access to full text is necessary for certain fine-grained retrieval tasks, e.g., image search [3]. Recently, there has been substantial interest in this problem [32][33][34], based on both image features and features derived from text associated with images, e.g., captions and sentences in which the figures are referenced. Full text is obviously essential for extracting these features. For other tasks, access to full text may be desirable, e.g., question answering. Unlike a search engine, a question answering system attempts to return a response that directly answers the user's question. Due to their specificity, users' questions sometimes may not be sufficiently addressed by abstracts -often, useful nuggets of information may be found in parts of articles that are not well reflected in the abstract (e.g., in the related work or discussion sections).
However, it is also important to take into account other considerations in information seeking. Since many users are uncomfortable reading large amounts of text on screen, they often print out journal articles first before reading them in detail. In these cases, finer-grained passage and image access capabilities are most useful in helping users decide what articles they want to read, rather than directly answering users' questions. Often, complex information needs such as those faced by biologists cannot be answered with a paragraph or an image -instead, information returned by the system must be considered in the context of the entire article from which the segment was extracted (for example, so that the scientist can verify the experimental procedure, consider alternative hypotheses mentioned in the discussion section, etc.). For this reason, I focus on a system's ability to identify relevant articles. This corresponds to ad hoc retrieval, a task that has been well studied by information retrieval researchers in large-scale evaluations such as TREC.
Based on this discussion, it is clear that there are advantages and disadvantages to full-text retrieval. However, the extent to which these various factors balance out and affect search effectiveness can only be determined empiri-cally. The next section presents a series of experiments that explore these issues.

Test Collection
Retrieval experiments in this article were conducted with data from the TREC 2007 genomics track evaluation [26], which used a collection of 162,259 full-text articles from Highwire Press. MEDLINE records that correspond to the full-text articles were also provided as supplementary data. To standardize system output, the organizers of the evaluation divided up the entire collection into 12.6 million "legal spans" (i.e., paragraphs) that represent the basic units of retrieval. The test collection contains 36 information needs, called "topics", and relevance judgments, which are lists of legal spans that were assessed by humans to be relevant for each topic. Despite the availability of relevance judgments at the level of spans, I focused on article-level relevance in order to support a meaningful comparison of abstract and full-text search. Section 5.1 describes this test collection in more detail.

Retrieval Conditions
A matrix experiment was devised with two different retrieval models (in three separate implementations) and three different data conditions. The goal was to compare the effectiveness of different experimental settings, as quantified by standard retrieval metrics (see Section 2.4). The retrieval models examined were: • The Okapi bm25 ranking algorithm [35,36] (described in Section 5.2), as implemented in Ivory, a toolkit for distributed text retrieval. Ivory was developed with Hadoop, an open-source implementation of the MapReduce programming model (see Section 5.3 for details).
• The ranking algorithm implemented in the open-source search engine Lucene, which represents a modified tf.idf retrieval model (described in Section 5.2). Due to its popularity and ease of use, Lucene provides a good baseline for comparison. This ranking algorithm was also implemented in Ivory, primarily for evaluation of efficiency and scalability (see Section 2.6).
The matrix design consisted of three different data conditions. The following indexes were built (one set of indexes for Lucene, another set of indexes for Ivory): • Abstract index, built on the abstracts and titles of articles in the Highwire collection, taken from the MEDLINE records. Each abstract was considered a "document" for retrieval purposes.
• Article index, built on the full-text articles in the Highwire collection (which include abstracts and titles). The entire text of each article was considered a "document" for retrieval purposes.
• Span index, built on the legal spans in the Highwire collection. In this experimental condition, each of the 12.6 million spans in the collection was treated as if it were a "document".
For each cell in the matrix experiment, I performed a retrieval run with 36 queries, taken verbatim from the TREC 2007 genomics track test data (see Section 5.1 for examples). With the abstract and article indexes, retrieval results consisted of 1000 article ids in rank order. For the span index, the ranked results consisted of span ids. As a post-processing step, I applied a script to create a ranking of articles from a ranking of spans, using two different methods described by Hearst and Plaunt [17]: • Maximum of supporting spans (max): the score for an article is computed as the maximum of scores for all spans contained in that article. Article ids were sorted by this score in descending order. This method favors articles that have a single high-scoring span.
• Sum of supporting spans (sum): the score for an article is computed as the sum of scores for all spans contained in that article. Article ids were sorted by this score in descending order. This method favors articles that have many potentially-relevant spans.
In order to ensure that the post-processing script generated a ranked list of 1000 articles (same as the abstract and article conditions), 5000 spans were retrieved initially.

Evidence Combination
An obvious extension to the matrix experiment discussed in the previous section is to integrate evidence from multiple sources. As an initial exploration, I conducted a series of experiments that combined the results of span retrieval with either article or abstract retrieval. In both cases, runs were combined by first normalizing each set of scores and then averaging scores from the different runs. The goal of this experiment was to examine the effect of combining content representations at different granularities. Note that in principle a simple average of the scores could be replaced with weighted linear interpolation (or some other evidence combination technique), but in absence of a principled approach to determining parameters, I opted not to explore this option for fear of overtraining on limited data.

Evaluation Metrics
For all experimental conditions, I arrived at a ranking of 1000 articles, which supported a meaningful comparison across all data conditions. To evaluate effectiveness, three different metrics were collected: • Mean average precision (MAP), the single-point metric of effectiveness most widely accepted by the information retrieval community. The standard cutoff of 1000 hits was used.
• Precision at 20 (P20), the fraction of articles in the top twenty results that are relevant. The cutoff of twenty equals the number of hits on a result page in the present PubMed interface. In a Web environment, many searchers only focus on the first page of results.
• Interpolated precision at recall of 50% (IP@R50), which attempts to capture the experience of a dedicated, recalloriented searcher (e.g., scientist conducting a literature search). This metric quantifies the amount of irrelevant material a user must tolerate in order to find half of the relevant articles -the higher the IP@R50, the less "junk" a user must sort through. In this study, I characterize IP@R50 as a "recall-oriented" metric. The recall level of 50% was arbitrarily selected. Section 2.5 focuses on retrieval effectiveness with Ivory, comparing bm25 and the implementation of Lucene's ranking algorithm. Section 2.6 focuses on efficiency, comparing Lucene with the implementation of its ranking algorithm in Ivory.

Retrieval Effectiveness
Results of the matrix experiment described in Section 2.2 with Ivory are presented in Table 1. The three parts of the table show effectiveness in terms of MAP, P20, and IP@R50. The columns report figures for the two retrieval models: bm25 and the Ivory implementation of Lucene's ranking algorithm. Abstract retrieval (i.e., retrieval using the abstract index) is taken as the baseline, and the table provides relative differences with respect to this condition. The Wilcoxon signed-rank test was applied in all cases to assess the statistical significance of the results.
Results show that for abstract retrieval, bm25 is significantly more effective in terms of MAP than the Lucene ranking algorithm (p < 0.01). Comparing abstract retrieval with article retrieval (i.e., retrieval using the article index), MAP is significantly higher (p < 0.01) for Lucene but differences are not statistically significant for bm25. For the Lucene ranking algorithm, article retrieval significantly outperforms abstract retrieval for the other two metrics as well. On the other hand, for bm25, article retrieval either hurts (P20), or doesn't have a significant impact (IP@P50). Article retrieval, which simply treats full-text articles as longer "documents", does not appear to yield consistent gains in effectiveness.
For retrieval using the span index, the "max" strategy for generating article rankings appears to be more effective than the "sum" strategy. In terms of MAP and IP@R50, both span retrieval strategies significantly outperform retrieval with the abstract index, for both bm25 and the Lucene ranking algorithm. For IP@R50, in particular, the gains are quite substantial. However, span retrieval does not appear to have a significant impact on P20 compared to the abstract retrieval baseline. Table 2 shows the results of significance testing between article retrieval and span retrieval with the "max" strategy (the more effective, and thus more interesting, of the two strategies). For bm25, article retrieval is significantly worse in terms of MAP and P20. None of the differences are significant for the Lucene ranking algorithm. Note that for these comparisons, there are often large differences in pertopic scores, but in many cases one run does not consistently outperform another -for this reason, substantial differences in the mean may not necessarily yield statistical significance. These results suggest that span retrieval is at least as effective as treating the entire article as an index-ing unit, and at least in a few cases, span retrieval is superior.
Results for the evidence combination experiments are shown in Table 3, where span retrieval is combined with abstract and article retrieval. In the interest of space, effectiveness metrics are only shown for the "max" strategy. Relative differences are shown with respect to the span retrieval baseline. As with before, the Wilcoxon signedrank test was applied in all cases to assess the statistical significance of the results. For the Lucene ranking algorithm, combining span retrieval with article retrieval yields significant gains for all three metrics. Other differences are not statistically significant. Table 4 attempts to summarize findings from all these experiments by establishing a partial rank order of different experimental conditions (based on significance testing), in terms of each effectiveness metric and retrieval model. The "sum" strategy for span retrieval is not considered since the alternative "max" strategy appears to be more effective. In all cases, integrating span-level evidence with article-level evidence either yields the highest effectiveness or is not significantly worse than the condition that yields the highest effectiveness. This suggests that combining article content and span-level analysis is an effective approach to exploiting full text in the life sciences.

Retrieval Efficiency
Given that there is value in searching full text, the question of efficiency must be addressed. The potential effectiveness gains of full text come at a significant cost in terms of dataset size. In its compressed form as distributed, the collection of 162,259 full-text articles from Highwire Press occupies 3.28 GB (12.6 GB uncompressed). The corresponding MEDLINE abstracts, also in compressed form, take up only 139 MB (502 MB uncompressed). The difference in size is more than an order of magnitude -which means that algorithms must process significantly more data to realize the potential gains of full-text content. Articles in the Highwire collection contain on average 4148 terms (after stopword removal), while abstracts contain on average only 142 terms. For reference, spans average 66 terms, or a bit less than half the length of abstracts.   Open-source text retrieval systems available today, designed to run on individual machines, would have no difficulty handling the Highwire collection and even collections that are much larger. However, these articles represent only a small fraction of the material already available or soon to be available. Based on recent estimates, records are added to MEDLINE at a rate of approximately 65 k per month. A lower bound on the growth of available full-text content can be estimated by examining the growth of PubMed Central. Over the past two years, the digital archive has grown by approximately 40 k articles per month. However, the growth rate is uneven due to retrospective conversion; more recently, this figure is closer to 20 k articles per month. Nevertheless, full-text collections will inevitably outgrow the capabilities of individual machines -the only practical recourse is to distribute computations across multiple machines in a cluster.
I have been exploring the requirements of scaling to larger datasets with Ivory, a toolkit for distributed text retrieval implemented in Java using Hadoop, which is an opensource implementation of the MapReduce framework [4]. Section 5.3 describes Ivory in more detail, but an evaluation of its efficiency is presented here. Specifically, I compare the original implementation of Lucene with the Ivory implementation of the Lucene ranking algorithm (to factor out the effects of different retrieval algorithms).
All experiments were conducted with Amazon's Elastic Compute Cloud (EC2) service, which allows one to dynamically provision clusters of different sizes. EC2 is an example of a "utility computing" service, where anyone can "rent" computing cycles at a reasonable cost. For this work, EC2 provided a homogeneous computing environment that supports easy comparison of different cluster configurations. The basic unit of computing resource in EC2 is the small instance-hour, the virtualized equivalent of a processor core with 1.7 GB of memory, running for an hour. I experimented with the following configurations: • Lucene (version 2.0), running on a single EC2 instance. Default settings "out of the box" were used for all experiments.
• Ivory (with Hadoop version 0.17.0), running on an EC2 cluster with 10 slave instances (plus 1 instance for the master). This is comparable to a cluster with 10 cores.
• Same as above, except with 20 slave instances, comparable to a cluster with 20 cores.
As an aside, note that physical equivalents of these clusters are quite modest by today's standards. Quad-core processors are widely available in server-class machines, and  with dual processor packages, a 20-core cluster is within the means of most research groups.
Running times for index construction for the three different configurations are shown in Table 5. Lucene, which was not designed to run on a cluster, takes over a day to build the span index (containing 12.6 million spans). With either cluster configurations, indexing takes less than an hour. These figures should be interpreted with the caveat that Lucene builds a richer index that supports complex query operators and that I am comparing a single core to clusters. However, the point is that Lucene cannot be easily adapted to run on multiple machines and thus indexing speed is fundamentally bound by the disk bandwidth of one machine. A cluster can take advantage of the aggregate disk bandwidth of many machines, and MapReduce provides a convenient model for organizing these disk operations (see Section 5.3).
The speedup demonstrated by Ivory is important because time for inverted index construction places an upper bound on how fast a researcher can explore the solution space for algorithms that require manipulating the index. Since research in information retrieval is fundamentally empirical in nature, progress is driven by iterative experimentation. Thus, exceedingly long experimental cycles represent a potential impediment to advances in the state of the art.
In terms of retrieval, running times on the entire set of 36 topics from the TREC 2007 genomics track are shown in Table 6. The gains in efficiency are not quite as dramatic, but still substantial. In its present implementation, Ivory was designed for batch-style experiments, not real-time retrieval (see Section 5.3 for more discussion). These numbers are therefore only presented for reference, and should not be taken as indicative of efficiency in operational settings (where techniques such as caching can greatly reduce retrieval latency). My experiments primarily focus on indexing efficiency, which is more important for the issues explored in this study.
Taking advantage of full-text content requires more computational resources to cope with the increased quantities of data. Inevitably, full-text collections will outgrow retrieval systems designed to run on single machines -necessitating the development of distributed algorithms. The MapReduce framework provides a practical solution for distributed text retrieval.

Discussion
Is searching full text more effective than searching abstracts? The answer appears to be yes. Furthermore, experimental results suggest that span-level analysis provides a promising strategy for taking advantage of full-text content. Whereas simply treating entire articles as indexing units yields mixed results, span retrieval consistently outperforms abstract retrieval. Combining span-and article-level evidence yields the highest effectiveness across a range of experimental conditions.
Why does span retrieval work? Further analysis of results in Section 2.5 reveals some interesting observations. Focusing on the "max" strategy, Table 1 shows that, overall, span retrieval has a relatively small effect on precision (seen in the P20 scores), but a large impact on recall (seen in the IP@R50 scores). This makes sense: key ideas in an article are likely reinforced multiple times, often in slightly different ways. This potentially alleviates mismatches between query terms and terms used by authors -in essence, span indexing gives a retrieval algorithm multiple opportunities to identify a relevant article. This enhanced recall leads to higher overall effectiveness in terms of MAP.
In general, the "max" strategy for generating article rankings from span rankings appears to be more effective than the "sum" strategy. Why is this so? One possibility is the issue of length normalization. In the current implementation, longer articles tend to have higher scores simply because they contain more spans; thus, there is an inherent bias in the "sum" strategy. Length normalization plays an important role in text retrieval [37,38], but I leave a thorough exploration of this issue for future work.
The findings in this article pave the way for future advances in full-text retrieval algorithms for the life sciences, which can draw from a wealth of previous work in the information retrieval literature on passage retrieval, XML retrieval, etc. In fact, the effectiveness of span retrieval confirms a well-known finding: ranking algorithms benefit from techniques that exploit document structure, particularly for longer documents.
Remaining focused on the problem of using full-text content to improve article ranking, how in general can article structure be exploited? Within the space of "bag of words" models, strategies can be organized in terms of two questions: • At what levels of granularity should retrieval algorithms build representations of full-text content?
• How should evidence from multiple representations be combined to rank articles?
These two questions provide context for future work. As a start, I have experimented with two different indexing granularities (full articles and spans), but alternative approaches include sliding windows [18,20], multi-paragraph segments [19], hierarchically-overlapping segments [38,39], and segments based on topic shifts [17]. There are many strategies for integrating evidence from multiple content representations and representations at different granularities (e.g., [40]). I have begun to examine some of these strategies, but there are many more possibilities yet to be explored. For example, differential treatment of article sections may improve effectiveness since some sections are more important than others, i.e., more likely to contain relevant information. Earlier work on a smaller collection of documents from the Federal Register illustrated the potential of assigning weights to different section types [19]. More recently, Tbahriti et al. [41] found section-specific weights to be helpful for retrieval in the context of structured abstracts in the life sciences. However, one challenge that must be overcome for this strategy to work on a large scale is the lack of standardized section headings -both across journals and different types of articles (e.g., research vs. review articles).
In this work I have focused on exploiting full-text content to better rank articles. Alternatively, one could leverage full text to directly return relevant information, i.e., with passage retrieval techniques. This was, in fact, the original design of the TREC 2007 genomics track evaluation. Of course, this begs the question: How are they related? In the information retrieval literature, a distinction is made between passage retrieval and document retrieval that exploits passage-level evidence. This exactly parallels the present discussion about retrieving segments of full-text content versus leveraging full-text content to enhance article retrieval. However, I argue that the two are complementary from a user interface point of view.
Leaving aside non-traditional search interfaces, a retrieval system must ultimately present users with lists of results.
Consider the two approaches to exploiting full text in this context: Even if the primary goal of a system is to leverage full-text content to enhance article retrieval, results have to be presented in a manner that suggests the relevance of an article. This necessarily involves creating some type of surrogate for the article, which can either be indicative or informative. Common techniques for generating such surrogates include displaying titles and metadata (as with the current PubMed interface) and short keyword-in-context extracts (as with Google Scholar). The first is primarily indicative, while the second aims to be informative. Extraction of informative text segments from articles is essentially a passage retrieval task -and in some cases, this information may already be available as a natural byproduct of the article ranking process. For example, in algorithms that integrate evidence from multiple spans within an article, those salient spans might form the basis of generating article surrogates.
Even if the primary goal of a system is to directly retrieve relevant passages, the passages must still be couched within the context of the article containing the passages (to provide users with pointers back to the original content). In addition, there will be cases where a passage retrieval algorithm suggests multiple passages extracted from the same article (unless this is explicitly suppressed, which may lead to loss of potentially-important information). To facilitate result presentation, it would be desirable to group passages by the articles that contain themwhich essentially involves article ranking.
In other words, the distinction between retrieving passages and retrieving articles becomes blurred when one considers elements of the user interface. Both approaches must grapple with the same issues, thus creating synergies where algorithms specifically developed for one purpose may be useful for the other.

Conclusion
Experiments in this article with the TREC 2007 genomics track test collection illustrate that there is significant value in searching full-text articles. Given the rapidly growing availability of full text in online digital archives, this is a positive development for scientists who depend on access to the literature for their research. Results show that retrieval at the level of paragraphs within full text is significantly more effective than searching abstracts only. Combining span-and article-level evidence appears to yield the best results. However, much work remains in developing effective full-text retrieval algorithms for the life sciences literature: toward that end, this work presents a first step.
One important issue in moving from searching abstracts to searching full text is that of scalability. Gains in effectiveness come at a cost -algorithms must process significantly more text. Although currently-available tools designed to run on single machines suffice to handle present test collections, it is clear that future systems must distribute computations across multiple machines to cope with ever-growing quantities of text. As illustrated by Ivory, MapReduce provides a convenient framework for distributed text retrieval. The combination of greater effectiveness enabled by full text and greater efficiency enabled by cluster computing paves the way for exciting future developments in information access tools for the life sciences.

Test Collection
Experiments reported in this article were conducted with the test collection from the TREC 2007 genomics track evaluation [26]. A test collection is a standard laboratory tool for evaluating text retrieval systems, which consists of three components: • a collection -documents on which retrieval is performed, • a set of information needs -written statements describing the desired information (called "topics"), which are usually provided as queries to the system, and • relevance judgments -records specifying the documents that should be retrieved in response to each information need (i.e., which documents are relevant to each topic).
The use of test collections to assess the effectiveness of text retrieval algorithms is a well-established methodology in the information retrieval literature, dating back to the Cranfield experiments in the 60's [42]. These tools enable rapid, reproducible experiments in a controlled setting without requiring manual assessment. In modern information retrieval research, test collections are created through large-scale evaluations, such as the Text Retrieval Conferences (TRECs) sponsored by the U.S. National Institute of Standards and Technology (NIST) [43]. TREC is an annual evaluation forum that draws together researchers from around the world to work on shared problems in different "tracks". Over the years, TREC has explored a wide variety of problems ranging from multimedia retrieval to spam detection. The genomics track was dedicated to exploring biomedical text retrieval.
The TREC 2007 genomics track used a collection of 162,259 full-text articles assembled in 2006. These articles came from the electronic distribution of 49 genomicsrelated journals from Highwire Press. The articles were distributed in HTML, which preserved formatting, structure, table and figure legends, etc. In addition, the organizers gathered MEDLINE records corresponding to each of the full-text articles, which were also made available to participants in the evaluation.
The test collection contains 36 official topics in the form of questions that asked for specific entities such as proteins and drugs -the first five topics are shown in Table 7.
Entities of interest are denoted in square brackets and correspond to controlled terminologies from various sources (e.g., MeSH). The topics were created after surveying biologists about recent information needs, and hence can be considered representative for an important group of users who regularly depend on access to the literature.
Relevance judgments consist of lists of legal spans that were determined to contain an answer, based on the opinion of human assessors with significant domain knowledge (Ph.D. in the life sciences). A legal span is a prescribed unit of retrieval that corresponds to a paragraph in the full-text article. The notion of a legal span evolved out of an attempt to standardize system output.
Since systems varied in their processing of article text (in terms of segmentation, tokenization, etc.), a prescriptively-defined unit of retrieval made results easier to compare. In total, there are 12.6 million legal spans in the collection; a list of all legal spans was distributed along-

Retrieval Models
Most modern text retrieval systems adopt a "bag of words" model, in which documents are treated as unordered collections of terms. Although such a model ignores the richness and complexity of natural language -disregarding syntax, semantics, and even word order -this simplification has proven to be effective in practice. In one standard formulation of the retrieval problem, a document d is represented as a vector W d of term weights w t, d , which reflect the importance of each term t in the document. A document vector has dimensions |V|, the size of the vocabulary in the entire collection. As a matter of convenience, "document" generically refers to the unit of indexing (which may in actuality be an abstract, a paragraph, etc.) A query q is represented in the same manner, and the score of a document with respect to the query is computed as follows: This inner-product formulation is sufficiently general to capture a wide range of retrieval models. Note that since queries are often very short, w t, q is generally less important than w t, d .
Given a query, a text retrieval system returns a list of documents with respect to a particular retrieval model. In the inner-product formulation, ranking algorithms vary in how term weights are computed. This work explores two different ranking algorithms: the algorithm implemented in the open-source Lucene search engine and Okapi bm25.
Lucene is best described as a modified tf.idf ranking algorithm. Given a query q, the score of a document is computed as the sum of contributions from individual query terms: For each term t that appears in the query q, tf is the term frequency in the document, N is the number of documents in the collection, n is the number of documents containing t (its document frequency), and dl is the document length. The first term inside the summation is the tf component, the second is the idf component, and the third is a length normalization component. On top of a standard inner-product formulation, Lucene introduces c, a "coordination factor", defined as the fraction of query terms found in the document. This factor rewards documents that have many matching terms.
Okapi bm25 [35,36] models documents as a mixture of two Poisson processes. One process generates so-called elite terms, corresponding to those that an author uses in writing about the topic of a particular document. The other process generates non-elite terms, corresponding to those that the author uses in passing (i.e., words whose appearance is incidental to the topic of the document).
Due to the complexity of parameter estimation for the full two-Poisson formulation, bm25 uses an empiricallyderived approximation [44]. Given a query q, bm25 computes the score of a document as the sum of contributions from individual query terms: For each term t, tf and qtf are term frequencies in the document and query, respectively; N is the number of documents in the collection; and n is the number of documents containing the term. K, a length normalization factor, is defined as follows: where dl is the document length and avdl is the average length of all documents. The constants k 1 , b, and k 3 are tunable parameters. In my experiments, I used k 1 = 1.2, b = 0.75, and k 3 = 1000, which are typical settings recommended in the literature.

Ivory: A Toolkit for Distributed Text Retrieval
Ivory is a toolkit for distributed text retrieval being developed at the University of Maryland to explore scalable algorithms [45]. The software was created using Hadoop, which is an open-source Java implementation of the MapReduce programming model [4] originally developed by Google. Ivory supports the large class of retrieval mod- els that can be expressed as an inner product of term weights (see Section 5.2), and currently implements both bm25 and the Lucene ranking algorithm (with a special extension to handle the coordination factor).
Certainly, distributed retrieval systems are not new -Web search engines have been in existence for over a decade. However, the exact architectures of these systems are guarded as commercial secrets. Even though outsiders are occasionally offered glimpses into their design [46,47] MapReduce draws inspiration from higher-order functions in functional programming and builds on the observation that many information processing tasks have the same basic structure: a computation is applied over a large number of records (e.g., Web pages, nodes in a graph) to generate partial results, which are then aggregated in some fashion. In MapReduce, the programmer defines a "mapper" and a "reducer" with the following signatures: Key-value pairs form the basic data structure in MapReduce. The mapper is applied to every input key-value pair to generate an arbitrary number of intermediate key-value pairs (I adopt the convention of [...] to denote a list). The reducer is applied to all values associated with the same intermediate key to generate output key-value pairs. This two-stage processing structure is illustrated in Figure 1.
In MapReduce, a programmer need only provide implementations of the mapper and reducer. On top of a dis-Illustration of the MapReduce framework: the "mapper" is applied to all input records, which generates results that are aggre-gated by the "reducer" Figure 1 Illustration of the MapReduce framework: the "mapper" is applied to all input records, which generates results that are aggregated by the "reducer". The runtime groups together values by keys. The pseudo-code for Ivory's indexing algorithm is shown in Figure 2. Like nearly all text retrieval systems, Ivory builds a data structure called an inverted index, which given a term provides access to the list of documents that contain the term. An inverted index consists of postings lists, one associated with each term in the collection. A postings list is comprised of individual postings, each of which represents a (document id, term frequency) pair. This information is used to compute term weights during retrieval.
Input to the indexer consists of document ids (keys) and associated document content (values). In each mapper, the document text is tokenized and stemmed term occurrences are first stored in a histogram H (implemented as an associative array). After this histogram has been built, the mapper then iterates over all terms. For each term, a pair consisting of the document id (k) and the frequency of the term in the document (f) is created. Each pair, denoted by Όk, f in the pseudo-code, represents an individual posting.
The mapper then emits an intermediate key-value pair with the term as the key and the posting as the value. MapReduce guarantees that all values associated with the same key will be sent to the same reducer; the reducer gathers up all postings, sorts them by descending term frequency, and emits the complete postings list, which is then written out to the distributed file system. The final key-value pairs (terms and associated postings lists) make up the inverted index.
Typically, computing term weights requires information about document lengths. This is straightforwardly expressed as another MapReduce algorithm: each mapper counts up the number of terms in a document and emits the term count as a value with the associated document id as the key. In this case, there is no need for a reducer -document lengths are directly written to disk. The table of document lengths is relatively compact, and is read into memory by each mapper in the retrieval phase.
Retrieval with an inverted index involves fetching postings lists that correspond to query terms, and then scoring documents based on term weights computed from postings information. For real-time applications, this requires low-latency access to the inverted index. However, Hadoop was primarily designed for high-throughput batch computations, not computations for which low latency is desired. Presently, Hadoop does not provide a mechanism for low-latency random access to the distributed file system. To work around this limitation, Ivory's retrieval algorithm was designed for parallel query execution.
The pseudo-code for Ivory's retrieval algorithm is shown in Figure 3. The input to each mapper is a term t (the key) and its associated postings list P (the value). The mapper loads up all the queries at once and processes each query in turn. If the query does not contain t, no action is performed. If the query contains t, then the corresponding postings must be traversed to compute the partial contributions to the query-document score. For each posting element, the partial contribution to the score (w t, q ·w t, d ) is computed based on the actual ranking algorithm. For example, bm25 requires the document frequency of t (known by the length of the postings list), term frequency of t in the document (stored in the posting), query frequency (loaded by the mapper), document length (stored separately and loaded by the mapper; see above), and average document length (same). With all the necessary components, computing the partial score contribution is simply a matter of arithmetic. Each partial score is stored in an associative array H, indexed by the document id kthis structure serves the same functionality as accumulators in a traditional retrieval engine.  Initialize.AssociativeArray(H) 3: for all t ∈ d do 4: H{t} ← H{t} + 1 5: for all t ∈ H do 6: Emit(t, k, H{t} ) 1: procedure Reduce(t, [ k 1 , f 1 , k 2 , f 2 . . .])

5:
Sort(P ) 6: Emit(t, P ) partial query-document scores associated with term t for all queries that contain the term.
In the reduce phase, all associative arrays belonging to the same query are brought together by the runtime. The reducer performs an element-wise sum of all the associative arrays (denoted by the MERGE function in the pseudocode): this adds up the contributions for each query term across all documents. The final result is an associative array containing scores for all documents that have at least one query term. This structure is then sorted (outside MapReduce by a separate process) to generate the final ranked list for fixed cutoff.
Note that this retrieval algorithm replaces random access of the postings with a parallel scan of all postings -this modification was necessary due to limitations of Hadoop. However, since disk scans are distributed across the entire cluster, it is possible to exploit the aggregate disk bandwidth of all available machines. In processing a set of queries, each postings list is accessed only once -each mapper computes partial score contributions for all queries that contain the query term. It should be emphasized that this algorithm is not meant for real-time retrieval applications, but rather is intended for running batch-style experiments in a research context. Figure 3 Pseudo-code of Ivory's retrieval algorithm in MapReduce. The mapper processes the postings lists in parallel. For each query term, the mapper initializes accumulators to hold partial score contributions from all documents containing the term. The reducer adds up partial scores to produce the final results. [Q 1 , Q 2 , . . . Q n ] ← LoadQueries() 3: for all Q i ∈ [Q 1 , Q 2 , . . . Q n ] do 4: if t ∈ Q i then 5: Initialize.AssociativeArray(H) 6: for all k, f ∈ P do 7: H{k} ← w t,q · w t,d 8:


A Two-Tier User Simulation Model for Reinforcement Learning of Adaptive Referring Expression Generation Policies

We present a new two-tier user simulation model for learning adaptive referring expression generation (REG) policies for spoken dialogue systems using reinforcement learning. Current user simulation models that are used for dialogue policy learning do not simulate users with different levels of domain expertise and are not responsive to referring expressions used by the system. The two-tier model displays these features, that are crucial to learning an adaptive REG policy. We also show that the two-tier model simulates real user behaviour more closely than other baseline models, using the dialogue similarity measure based on Kullback-Leibler divergence.

Introduction
We present a new user simulation model for learning adaptive referring expression generation (REG) policies for spoken dialogue systems using reinforcement learning methods. An adaptive REG policy equips a dialogue system to dynamically modify its utterances in order to adapt to user's domain knowledge level. For instance, to refer to domain objects, the system might use simple descriptive expressions with novices and technical jargon with experts. Such adaptations help grounding between the dialogue partners (Issacs and Clark, 1987). Since the user's knowledge level is unknown, the system must be able to adapt dynamically during the conversation. Handcoding such a policy could be extremely difficult. (Janarthanam and Lemon, 2009b) have shown that such policies can be learned using simulation based reinforcement learning (RL) methods.
The quality of such learned policies is directly dependent on the performance of the user simulations used to train them. So far, only hand-coded user simulations have been employed. In contrast, we now present a data driven two-tier user simulation model trained on dialogue data collected from real users. We also show that the two-tier model simulates real users more faithfully than other data driven baseline n-gram models (Eckert et al., 1997).
In section 2 we briefly discuss other work related to user simulations for dialogue policy learning using RL. In section 3 we describe the data used to build the simulation. Section 4 describes the simulation models in detail. In section 5 and 6 we present the evaluation metrics used and the results.

Related work
Several user simulation models have been proposed for dialogue management policy learning (Schatzmann et al., 2006;Schatzmann et al., 2007). However, these models cannot be directly used for REG policy learning because they interact with the dialogue system only using high-level dialogue acts. Also, they do not simulate different user groups like experts, novices, etc. In order to learn adaptive REG policies, user simulations need to respond to the system's choice of referring expressions and simulate user groups with different knowledge levels. We propose a two-tier simulation which simulates users with different knowledge levels and is sensitive to the system's choice of referring expressions.

Corpus
The "Wizard-of-Oz" (WOZ) methodology is a widely accepted way of collecting dialogue data for user simulation modeling (Whittaker et al., 2002). In this setup, real users interact with a human wizard disguised as a dialogue system. The wizard interprets the users responses and passes them on to the dialogue system. The dialogue system updates the dialogue state and decides the responses to user's moves. The task of the participant is to interact with the dialogue system to get instructions to setup a broadband Internet connection. The referring expression generation strategy is chosen before the dialogue starts and stays the same for the whole session. The strategies used were "jargon", "descriptive" and "tutorial". In the jargon strategy the system instructs the user using technical terms (e.g. "Plug the broadband filter into the phone socket."). In the descriptive strategy, it uses descriptive terms (e.g. "Plug the small white box into the square white box on the wall."). In the tutorial strategy, the system uses both jargon and descriptive terms together. The system provides clarifications on referring expressions when users request them. The participant's domain knowledge is also recorded during the task. Please refer to (Janarthanam and Lemon, 2009a) for a more details on our Wizard-of-Oz environment for data collection. The dialogues were collected from 17 participants (one dialogue each) with around 24 to 35 turns per dialogue depending on the strategy and user's domain knowledge.

User Simulation models
The dialogue data and knowledge profiles were used to build user simulation models. These models take as input the system's dialogue act A s,t (at turn t) and choice of referring expressions REC s,t and output the user's dialogue A u,t and environment EA u,t acts. User's observation and manipulation of the domain objects is represented by the environment act.

Advanced n-gram model
A simple approach to model real user behaviour is to model user responses (dialogue act and environment act) as advanced n-gram models (Georgila et al., 2006) based on many context variables -all referring expressions used in the utterance (REC s,t ), the user's knowledge of the REs (DK u ), history of clarification requests on the REs (H), and the system's dialogue act (A s,t ), as defined below: Although this is an ideal model of the real user data, it covers only a limited number of contexts owing to the limited size of the corpus. Therefore, it cannot be used for training as there may be a large number of unseen contexts which the model needs to respond to. For example, this model cannot respond when the system uses a mix of jargon and descriptive expressions in its utterance because such a context does not exist in our corpus.

A Two-tier model
Instead of using a complex context model, we divide the large context in to several sub-contexts and model the user's response based on them. We propose a two-tier model, in which the simulation of a user's response is divided into two steps. First, all the referring expressions used in the system's utterance are processed as below: This step is repeated for each expression RE s,t separately. The above model returns a clarification request based on the referring expression RE s,t used, the user's knowledge of the expression DK RE,u , and previous clarification requests on the expression H RE and the system dialogue act A s,t . A clarification request is highly likely in case of the jargon strategy and less likely in other strategies. Also, if a clarification has already been issued, the user is less likely to issue another request for clarification. In such cases, the clarification request model simply returns none.
In the next step, the model returns a user dialogue act A u,t and an environment act EA u,t based on the system dialogue act A s,t and the clarification request CR u,t , as follows: By dividing the complex context into smaller sub-contexts, the two-tier model simulates real users in contexts that are not directly observed in the dialogue data. The model will therefore respond to system utterances containing a mix of REG strategies (for example, one jargon and one descriptive expression in the same utterance).

Baseline Bigram model
A bigram model was built using the dialogue data by conditioning the user responses only on the system's dialogue act (Eckert et al., 1997).
Since it ignores all the context variables except the system dialogue act, it can be used in contexts that are not observed in the dialogue data.

Trigram model
The trigram model is similar to the bigram model, but with the previous system dialogue act A s,t−1 as an additional context variable.

Equal Probability model baseline
The equal probability model is similar to the bigram model, except that it is not trained on the dialogue data. Instead, it assigns equal probability to all possible responses for the given system dialogue act.

Smoothing
We used Witten-Bell discounting to smooth all our models except the equal probability model, in order to account for unobserved but possible responses in dialogue contexts. Witten-Bell discounting extracts a small percentage of probability mass, i.e. number of distinct responses observed for the first time (T ) in a context, out of the total number of instances (N ), and redistributes this mass to unobserved responses in the given context (V − T ) (where V is the number of all possible responses) . The discounted probabilities P * of observed responses (C(e i ) > 0) and unobserved responses (C(e i ) = 0) are given below.
On analysis, we found that the Witten-Bell discounting assigns greater probability to unobserved responses than to observed responses, in cases where the number of responses per context is very low. For instance, in a particular context, the possible responses, their frequencies and their original probabilities wereprovide info (3, 0.75), other (1, 0.25), request clarification (0, 0). After discounting, the revised probabilities P * are 0.5, 0.167 and 0.33. request clarification gets the whole share of extracted probability as it is the only unobserved response in the context and is more than the other responses actually observed in the data. This is counter-intuitive for our application. Therefore, we use a modified version of Witten-Bell discounting (given below) to smooth our models, where the extracted probability is equally divided amongst all possible responses. Using the modified version, the revised probabilities for the illustrated example are 0.61, 0.28 and 0.11 respectively.

Metrics for evaluation of simulations
While there are many proposed measures to rank user simulation models with respect to real user data (Schatzmann et al., 2005;Georgila et al., 2006;Rieser and Lemon, 2006a;Williams, 2008), we use the Dialogue Similarity measure based on Kullback-Leibler (KL) (Cuayahuitl et al., 2005;Cuayahuitl, 2009) divergence to measure how similar the probability distributions of the simulation models are to the original real human data.

Dialogue Similarity
Dialogue Similarity is a measure of divergence between real and simulated dialogues and can measure how similar a model is to real data. The measure is based on Kullback-Leibler (KL) divergence and is defined as follows: The metric measures the divergence between distributions P and Q in N different contexts with M responses per context. Ideally, the dialogue similarity between two similar distributions is close to zero.

Evaluation results
We consider the Advanced N-gram model to be a realistic model of the real human dialogue corpus, as it takes into account all context variables and is reasonably smoothed to account for unobserved user responses. Therefore, we compare the probability distributions of all the other models to The results show that the two-tier model is much closer (0.078, 0.018) to the Advanced Ngram model than the other models. This is due to the fact that the bigram and trigram models don't take into account factors like the user's knowledge, the strategy used, and the dialogue history. By effectively dividing the RE processing and the environment interaction, the two-tier simulation model is not only realistic in observed contexts but also usable in unobserved contexts (unlike the Advanced N-gram model).

Conclusion
We have presented a data driven user simulation model called the two-tier model for learning REG policies using reinforcement learning. We have also shown that the two-tier model is much closer to real user data than the other baseline models. We will now train REG policies using the two-tier model and test them on real users in the future.


Genetic Programming Method of Evolving the Robotic Soccer Player Strategies with Ant Intelligence

This paper presents the evolved soccer player strategies with ant-intelligence through genetic programming. To evolve the code for players we used the Evolutionary Computation tool (ECJ simulator-Evolutionary Compuation in Java). We tested the evolved player strategies with already existing teams in soccerbots of teambots. This paper presents brief information regarding learning methods and ant behaviors. Experimental results depicts the performance of the evolved player strategies.

Introduction
Many people discovered the variety of the interesting insect or animal behaviors in the nature. A flock of birds sweeps across the sky. A group of ants forages for food. A school of fish swims, turns, flees together [1]. Hive's of bee communicates using dance language. In fact the honeybee dance language has been called one of the seven wonders of animal behaviors and is considered among the greatest discoveries of behavioral science [2]. Termites are small in size, completely blind and wingless -yet they have been known to build mounds 30 meters in diameter and several meters high [3]. We call this kind of aggregate motion "swarm behavior". Recently biologists and computer scientists in the field of "artificial life" have studied how to model biological swarms to understand how such "social animals" interact, achieve goals, and evolve. Moreover, engineers are increasingly interested in this kind of swarm behaviors since the resulting "swarm intelligence" can be applied in optimization, robotics, traffic patterns in transportation systems, and military applications etc. In our work we used Genetic programming to evolve the code for player strategies. Genetic Programming (GP) is considered to be a domain independent problem solving approach in which computer programs are automatically evolved to solve problems. The idea of mapping ant behaviors especially foraging and nest protecting behaviors to Robotic Soccer is presented in this paper. This paper will highlight the important points of robotic soccer, genetic programming, and simulation tool used, in the subsequent sections. Finally it presents experimental results and conclusion.

Robotic Soccer
Robot Soccer Competition give an opportunity to foster intelligent techniques and intelligent robotic research by providing a standard problem where a wide spectrum of technologies such as collaborative multiple agent robotics, autonomous computing, real-time reasoning and sensor fusion can be developed, tested and integrated.

Research Issues And Approaches
Several research issues are involved in the development of real robots and software agents for RoboCup. One of the major reasons why RoboCup attracts so many researchers is that it requires the integration of a broad range of technologies into a team of complete agents, as opposed to a task-specific functional module. The following is a partial list of research areas, which RoboCup covers [7]: -Agent architecture in general; -Combining reactive approaches and modeling/ planning approaches; -Real-time recognition, planning, and reasoning; -Reasoning and action in a dynamic environment; -Sensor fusion; -Multi-agent systems in general; -Behavior learning for complex tasks; -Strategy acquisition; -Cognitive modeling in general.
More strategic issues are dealt with in the simulation league and in the small-size real robot league while acquiring more primitive behaviors of each player is the main concern of the middle-size real robot league. Since Open Access Database www.intechweb.org Source the simulation league is well suited for testing the various multi agent strategies without bothering about the hardware and the electrical and mechanical aspects, a number of multi agent learning methods are applied to it. Next section gives a survey of the multi agent learning methods that are applied for developing the player strategies for robotic soccer simulation.

Learning Methods
Learning methods play an important role in robotic soccer. A team's success in robotic soccer will depend on how efficient it can react to the uncertain environment, which in turn depends on the learning ability of the agent. In the pre RoboCup which was held in 1996, the participated teams were having fixed hand coded strategies. But in the following years the researchers found more and more efficient strategies for their teams by incorporating learning abilities to the soccer-playing agents. Some of the important methods among them are discussed below.

Reinforcement Learning
Reinforcement learning is learning what to do or how to map situations to actions, so as to maximize a numerical reward signal.
[9] The learner is not told which actions to take, but instead must discover which actions yield the most reward by trying them. In the most interesting and challenging cases, actions may affect not only the immediate reward but also the next situation and, through that, all subsequent rewards. These two characteristics--trial-and-error search and delayed reward--are the two most important distinguishing features of reinforcement learning. One of the major challenges in managing a robot-soccer team is the design of methods to assign roles to the agents dynamically. Roles have to be assigned to the agents according to some metrics like the distance between the agent and the ball. A static assignment is not usually a good practice, but it can be used effectively for the goalkeeper agent. For other agents, a dynamic scheme is needed. One such approach is to choose the agent closest to the ball as the attacker, and the agent that is closest to the own goal among the unassigned agents as the defender. Other agents can help the attacker by holding strategic positions behind the attacker. As another efficient strategy for the role assignment problem, the Reinforcement Learning (RL) is used to learn the role assignment process.
[10] RL is a learning method, which can be used when the agent is only informed about the consequences of a sequence of its actions. The reinforcement measures chosen for the soccer problem were the goals scored by the team or the opponent team. The results showed that reinforcement learning is a good solution for role assignment problem in robot soccer. The solution can also be used in other highly dynamic environments where it is possible to introduce some reinforcement measures for the team.

Inductive Learning
Inductive learning is a machine-learning framework, which is based on generalization of examples. The concept of Inductive Logic Programming (ILP) has been used for soccer agents' inductive learning. A framework for inductive learning soccer agents (ILSAs) had been proposed [10] in which the agents acquire knowledge from their own past behavior and behave based on the acquired knowledge. The inductive learning soccer agents decides each action taken in the game to be good or bad according to the examples which are classified as positive or negative. Also the agents themselves classify their past states during the learning process. In the framework the agent is given an action strategy, ie, a state checker and an action-command translator. An inductive learning soccer agent acquires a rule from examples whose positive examples consist of states in which the agent failed an action, and uses the acquired rule as the state checker to avoid taking actions in states similar to the positive examples. Based on this work, another agent architecture that adapts its own behavior by avoiding actions, which are predicted to be failure, is proposed in [11]. The inductive learning agent used first-order formalism and inductive logic programming (ILP) to acquire rules to predict failures. First, the ILA collects examples of actions and classifies them. Then the prediction rules are formed using ILP and uses them for their behavior. This was implemented in soccer using parts of the RoboCup-1999 competition champion CMUnited-99 [12] and an ILP system Progol [13]. It was shown that agents could acquire prediction rules and could adapt their behavior using the rules. It was found that the agents used actions of CMUnited-99 more effectively after they acquired prediction rules. Another research has been reported, which uses ILP systems for verifying and validating multi-agents for RoboCup [14]. This concentrates on verification and validation of knowledge based system, not but prediction or discovery of new knowledge. Consequently, agents cannot adapt their own behavior using rules or knowledge acquired by ILP.

Memory Based Supervised Learning
A memory-based supervised learning strategy was introduced, which enables an agent to choose to pass or shoot in the presence of a defender.
[15] Learning how to adjust to an opponent's position can be critical to the success of having intelligent agents collaborating towards the achievement of specific tasks in unfriendly environments. Based on the position of an opponent indicated by a continuous-valued state attribute the agent learns to choose an action. A memory-based supervised learning strategy, which enables an agent to choose to pass or shoot in the presence of a defender, was attempted. In the memory model, training examples affect neighboring generalized learned instances with different weights. Each soccer agent stores its experiences in an adaptive memory and is able to retrieve them in order to decide upon an action. It has been seen that using an appropriate memory size, the adaptive memory made it possible for the agent to learn both time-varying and nondeterministic concepts. Also short-term performance was shown to be better when acting with a memory.

Neural Networks
The Artificial Neural Network (ANN) is an informationprocessing paradigm that is inspired by the way biological nervous systems, such as the brain, process information. The network is composed of a large number of highly interconnected processing elements or neurons working in parallel to solve a specific problem. Neural networks learn by example. They cannot be programmed to perform a specific task. An ANN is configured for a specific application through a learning process. Neural networks had been successfully used for learning low-level behaviors of soccer agents.
[16] This learned behavior, namely shooting a moving ball, equips the clients with the skill necessary to learn higher-level collaborative and adversarial behaviors. The learned behavior enabled the agent to redirect a moving ball with varying speeds and trajectories into specific parts of the goal. By carefully choosing the input representation to the neural networks so that they would generalize as much as possible, the agent was able to use the learned behavior in all quadrants of the field even though it was trained in a single quadrant. In another work, neural networks were used to learn turn angles based on balls distance and angle as a part of a hierarchical layered learning approach.

Neuro-Evolution
A neuro-evolutionary algorithm, which was successfully used in simulated ice hockey, was employed to evolve a player who can execute a dribble the ball to the goal and score behavior in the environment of robot soccer. Both goal-only and composite fitness functions were tried. The evolved players developed rudimentary skills; however it appeared that considerably more computation time is required to get competent players. The fitness of the individuals increases with generations. Also, the goalonly fitness was found more likely to lead to success than the composite fitness function Using this approach, some of the evolved players exhibited rudimentary dribble and score skills, but the overall results were not very good considering the lengths of the runs. More complex networks with more input variables may lead to the evolution of better players more quickly.

Layered Learning
Layered Learning [17] allows the programmer to provide a hierarchical, bottom up decomposition of the problem to be learnt. Each layer is a separate skill which is learnt and then used as a component in the learning of a future layer. Layered learning is a machine independent and problem independent learning scheme and as such there is some variation in what is considered to constitute a layer. Applied to soccer, three distinct layers at differing abstraction levels within a multi-agent soccer domain is defined.
[18] The first is the individual skill of intercepting the ball, learnt by training a neural network. The second is ball passing skills and evaluation, learnt by a decision tree, which requires the ability of ball interception. The third layer was pass selection, learnt by reinforcement learning, which utilizes both the previous skills. Each of these layers are encapsulated and do not change during further learning. The technique of layered learning has been applied to the evolution of goal scoring behavior in soccer players.
[17] It was found that the solutions evolved with layers have a higher accuracy but do not make as many goal attempts as other methods like standard genetic programming technique.

Hybrid Approaches
There have been approaches, which combines various multi agent methods for developing agent strategies for soccer agents. One of the significant works, which combines several multi agent strategies in order to arrive at efficient soccer team, was the CMUnited teams which participated in the RoboCup simulation league form the first RoboCup. The CMUnited 97 team used layered learning approach with locker room agreement as their strategy.
[19] Improving upon that, the CMUnited-98 simulator team used the following multi-agent techniques to achieve adaptive coordination among team members. Hierarchical machine learning (Layered learning): Three learned layers were linked together for layered learning.
[20] Neural networks were used by individual players to learn how to intercept a moving ball. With the receivers and opponents using this first learned behavior to try to receive or intercept passes, a decision tree was used to learn the likelihood that a given pass would succeed. This learned decision tree was used to abstract a very highdimensional state-space into one manageable for the multi-agent reinforcement learning technique TPOT-RL The low-level skills were improved and updated to deal with server changes, the use of opponent and teammate models was introduced, and some coordination procedures were improved, and a development paradigm called layered disclosure [26] was introduced, by which autonomous agents include in their architecture the foundations necessary to allow a person to probe into the specific reasons for an agent's action. It can be seen that hybrid approaches were effective in the soccer domain. Hybrid-methods may be able to capture the complexity of the soccer domain better because the problem itself demands solution to a combination of different multi-agent issues. Also the evolutionary approach genetic programming is also found to evolve good and effective strategies through automatically. This approach has the advantage of giving multiple strategies, which are equally good. A detailed overview of the genetic programming technique is presented in the next section.

Genetic Programming
Genetic Programming (GP) is a subset of Evolutionary Computing that follows the Darwinian theory of natural selection, "survival of fittest" [4]. It is considered to be a domain independent problem solving approach in which computer programs are automatically evolved to solve problems. This is achieved by genetically breeding a population of computer programs using the principles of natural selection and biologically inspired operations like crossover and mutation [4][5]. The first step in GP is initial population generation [4] [5]. The success of GP depends on the trees generated in the initial population [27]. The components of GP are given below. The terminal set: The terminal set consists of the variables and constants of the programs.
The function set: A set of domain specific functions used in conjunction with the terminal set to construct potential solutions to a given problem. For symbolic regression this could consist of a set of basic mathematical functions, while Boolean and conditional operators could be included for classification problems. The fitness function: Fitness is a numeric value assigned to each member of a population to provide a measure of the appropriateness of a solution to the problem in question. The termination criterion: This is generally a predefined number of generations or an error tolerance on the fitness. Selection Methods: There are three selection methods namely Fitness Proportionate selection, Tournament selection and Roulett wheel selection methods. The algorithm control parameters: The genetic programming paradigm is controlled by 19 control parameters, including two major numerical parameters, 11 minor numerical parameters, and six qualitative variables that select among various alternative ways of executing a run. The Table 1

Six qualitative variables
Generative method for initial random population is ramped half-and-half. Basic selection method is fitness proportionate. Spousal selection method is fitness proportionate. Adjusted fitness is used. Over-selection is not used for populations of 500 and below and is used for Populations of 1,000 and above Elitist strategy is not used. Tree Generation Algorithms for GP At the beginning of the evolution process, initial individuals must be generated at random. Genetic programming creates these individuals' trees by applying a tree generation algorithm to each tree's function set. Tree generation algorithms work by selecting and copying nodes from the templates in the function set, then hanging the copied nodes together to form the tree. The three traditional tree-generation algorithms are GROW, FULL, and RAMPED HALF-AND-HALF. GROW begins with a set of functions F to place as nodes in the GROW randomly selects a root from the full set of functions (both terminals and non terminals), then fills the root's arguments with random functions, then their arguments with random functions, and so on. GROW's companion algorithm (FULL) is used to generate full trees. RAMPED HALF-AND-HALF randomly does either FULL or GROW.

GP Breeding
In standard genetic programming, the breeding procedure picks from among the three breeding strategies reproduction, mutation, and crossover then applies one strategy to selected individuals and returns the results.
Reproduction and mutation will return one individual, while crossover returns two. Traditionally, genetic programming chooses reproduction 10% of the time and crossover 90% of the time. The mutation operator, which is a secondary operator, is not used usually. The other secondary operators can also be used along with these three operators. To perform crossover and mutation, genetic programming must implement 'recombine' and 'modify'. The standard recombination method in genetic programming, sub-tree crossover, starts with two individuals selected and copied from the old population. Classically, a random point is selected within one tree of each copied individual with non terminals selected 90% of the time and terminals selected 10% of the time. Then crossover swaps the sub-trees rooted at these two nodes and returns the modified copies. If the crossover process results in a tree greater than a maximum depth bound (except where noted, the bound is 17), then the modified child is discarded and its parent (the tree into which a sub-tree was inserted to form the child) is simply copied through reproduction. Crossover may only occur if two trees share the same function set. This process is illustrated in Fig. 1. and Fig. 2.   The most common 'modify' step uses mutation operator, shown in Figure 3. Point mutation starts with a single individual selected and copied from the old population. One node is selected from among of the copied individual's trees, using the same node-selection technique as described for sub-tree crossover. The subtree rooted at this node is removed and replaced with a randomly-generated sub-tree, using the GROW algorithm and the appropriate function set for the tree. If mutation results in a tree greater than the maximum depth, then the copy is discarded and its parent is reproduced instead. Checks whether an opponent is near the goal post. If so return v1 else return v2. Table 3. The functions used for evolving the robotic soccer player strategies.

Ant Behaviors in Robotic Soccer
As in many other multi agent systems, the soccer robots might benefit from some of the insights from social ants to model their strategies of play. For instance the tendency of nest protecting exhibited by ants can be a strategy for the goalkeeper robot in robotic soccer. Also if an opponent player tries to go near the goal post, the players should try to prevent the attempt. Likewise the division of labor among ants can be imitated by the robots for dividing the various sub tasks among themselves in a coordinated way. The ants follow the pheromone paths to find shortest path to food sources. This pheromone laying behavior may be applied to the robotic soccer game in another sense so as to help the players to disperse throughout the field or to communicate some other information.
A swarm of small ants will be able to defeat a larger ant and make it their food. But a large ant can catch a small ant as food. In the game of soccer, to deal with a quick and strong opponent player, two or more players will be needed. Analogous to ants rearing insects without eating, in-order to get sweet sap from them, a weak player among the opponents may be given access to the ball in the hope that he will play badly always. These are some of the examples, which show that the ant behaviors may be helpful in soccer domain also. We attempted to use one of these concepts while evolving the player strategies for robotic soccer.

Evolving Soccer Players strategies with Real Ant Behaviors
The technique behind the foraging behavior of real ants is the use of a chemical called pheromone, which was laid by the ants while coming from a food source. Ants from the same nest recognize this and follow the trail to arrive at the food source. This also enables them to find the shortest route to the nest from the food source. This concept of applying the pheromone to convey some information to the nest mates is adapted to the soccerplaying agents. The agent when perceives the ball which is near it as well as near the opponent goal may put some pheromone in its position to enable other teammates to know that there is a good chance of putting goal. If the other teammates also come near the pheromone, one of them may get a chance to put the ball to the opponent goal. This may help the forwarder agent to score more goals against the opponent. The persistence of the pheromone is for only one timestep, within which all the robots execute one command each. By using a function to check the presence of pheromone, the strategy to be followed when the pheromone is present in the field may be evolved through genetic programming. The revised function set and terminal set are given in the table 4 and table 5. Checks whether an opponent is near the goal post. If so return v1 else return v2. IfPhNew() 2 The function checks the presence of pheromone and executes the child trees according to whether pheromone is present in the field or not. Vector to the Opponent1 Opp2 Vector to the Opponent1 Opp3 Vector to the Opponent1 Opp4 Vector to the Opponent1 Goal Vector to the Goal OppGoal Vector to the Opponent Goal Rand A random Vector GoToPh The terminal directs the agent to move to the location of pheromone Table 5. Revised Terminal set of Genetic Programming to adopt the real ant behavior in player strategies.
Other than this method, this concept of the real ants behavior may be used in various other senses also. An ant usually identifies the pheromone laid by its nest-mates. Pheromone lay by other types of ants or ants from some other nest will be ignored. Like wise, while adopting this concept to soccer, different kinds of pheromone can be used to flag different situations or the forwarder and defender agents may use different types of pheromone, the meaning of which may be different to them. In order to test our work we used a simulation tool called Evolutionary Computation in Java tool. Next section gives details about the simulation tool and the modifications made to the tool.

ECJ Simulator
ECJ is a Java-based evolutionary computation research system.
[31] It comes with a comprehensive suite of libraries for doing Java-based genetic programming. ECJ 4 was the first most full-featured genetic programming distribution, which was made publicly available.
[32] It provides -Multithreaded and multi process evolution, -Both steady-state and generational evolutionary computation, -Multiple populations, inter-population exchanges, and co-evolutionary hooks, -Set-based strongly-typed genetic programming, -Automatically defined functions and macros, -Ephemeral random constants, -Check-pointing, logging, and reading populations from files, -Hooks for evolution with multi-objective fitness, -A highly flexible breeding architecture with six selection methods, twelve breeding operators, and four tree-generation algorithms, -Customizable individuals with multiple trees, -Pre-done problem domains (Artificial Ant, Multiplexer, Symbolic Regression, Parity, Lawnmower, Edge Encoding), -Abstractions for many evolutionary computation approaches, apart from genetic programming. ECJ was designed to have the features like extensibility, portability, and also to execute reasonably fast. It has also got rich set of features for doing evolutionary computation. Inorder to evolve the code for roboti soccer players, we coded an application package (Robotic Soccer) in ECJ Simulator. The formulated application package comprises of java and class files of the above said function sets and terminal sets referred in Table 4 and Table 5. The fitness of the individuals (Robotic Soccer Player Strategies) is evaluated against the teams in soccerbots of Teambots. Next section gives information regarding Teambots package.

TeamBots
TeamBots is a Java-based collection of application programs and Java packages for multi agent mobile robotics research.
[33] The TeamBots distribution is a full source-code release, in which the simulation environment is written in Java. One of the most important features of the TeamBots environment is that it supports prototyping in simulation of the same control systems that can be run on mobile robots. TeamBots supports prototyping, simulation and execution of multi robot control systems. Robot control systems developed in TeamBots can run in simulation using the TBSim simulation application, and on mobile robots using the TBHard robot execution environment. The TeamBots simulation environment is extremely flexible. It supports multiple heterogeneous robot hardware running heterogeneous control systems. Complex or simple experimental environments can be designed with walls, roads, opponent robots and circular obstacles. All of these objects may be included in a simulation by editing an easily understandable humanreadable description file. Four application programs are included in the TeamBots distribution to aid the deployment of a multi agent system: • TBSim: the TeamBots simulator.
• TBHard: the real robot execution environment for control systems developed using TeamBots.
• RoboComm: RoboComm simplifies asynchronous robot to robot communication. Any Java object can be sent from one robot to another. The RoboComm server forwards messages between agents.
• JCye: These programs demonstrate how to use our Java package to control a Cye robot.
• The TeamBots distribution includes several example systems that can run in simulation. The following are the domains which are included in the teambots package.
• Cye: this is a simulation of Probotic's Cye robot.
• SoccerBots: this is a simulation of RoboCup F-180 league soccer.
• Book: includes example exercises being developed for the book Designing Robot Behavior by Tucker Balch. These primarily illustrates principles of behaviorbased control.
• CTF: an implementation of Capture-The-Flag, a multi agent adversarial game.
• Forage: a basic implementation of multi agent foraging.
• ForageAAAI97: the actual source code used to win the AAAI-97 mobile robot competition. • Roads: two example uses of simulation environments including roads. One example includes two different types of roads and a bridge. The other is an entire city map. Any arbitrarily complex environment including different traversablility constraints can be built. • Walls: an example simulation environment with walls.
Out of these domains, the one which supports soccer domain is the soccer bots. Brief overview of SoccerBots is given below.

SoccerBots
SoccerBots is a simulation of RoboCup soccer. SoccerBots simulates the dynamics and dimensions of a regulation RoboCup small size robot league game. Two teams of five robots compete on a ping-pong table by pushing and kicking an orange golf ball into the opponent's goal. SoccerBots runs in the TBSim application using a configuration file that tailors it for soccer games. The same control systems that run in simulation can also operate real robot hardware using the TBHard application. SoccerBots has 20 soccer teams with different strategies in the teams package. The following table depicts the list of teams in teambots. The soccer games conducted among the set of teams has identified AIKHomoG, DoogHeteroG, DoogHomoG, MattiHeteroG as the top 4 leading teams. Among these 4 teams AIKHomoG is the never outbeaten by other teams and hence its the best team in soccerbots. Next section presents experimental results obtained through genetic programming.

Experimental Results
The genetic programming system for evolving the player strategies with ant intelligence was designed and implemented. The evolutionary computation system ECJ simulator was used for this purpose. The genetic programming parameters for this robotic soccer application are fine tuned by conducting a series of test runs with various parameters. The following experiments were conducted for finding the suitable genetic programming parameter setting for evolving the better strategies for the agent. Here we tested the evolved team with four top leading teams in soccerbots of teambots by varying the genetic programming parameters. The corresponding results obtained are shown: Through the experimental results it can be seen that when the concept of real ant food foraging behavior were applied in evolving the player strategies, the results obtained are quite promissing. At the outset the evolved player strategies are caplable of winning against the best team in soccerbots (AIKHomoG).

Conclusion and Future Work
This paper made an attempt to evolve the robotic soccer player strategies with ant intelligence through genetic