PRESY: A Context Based Query Reformulation Tool for Information Retrieval on the Web

Problem Statement: The huge number of information on the web as well as the growth of new inexperienced users creates new challenges for information retrieval. It has become increasingly difficult for these users to find relevant documents that satisfy their individual needs. Certainly the current search engines (such as Google, Bing and Yahoo) offer an efficient way to browse the web content. However, the result quality is highly based on uses queries which need to be more precise to find relevant documents. This task still complicated for the majority of inept users who cannot express their needs with significant words in the query. For that reason, we believe that a reformulation of the initial user's query can be a good alternative to improve the information selectivity. This study proposes a novel approach and presents a prototype system called PRESY (Profile-based REformulation SYstem) for information retrieval on the web. Approach: It uses an incremental approach to categorize users by constructing a contextual base. The latter is composed of two types of context (static and dynamic) obtained using the users' profiles. The architecture proposed was implemented using .Net environment to perform queries reformulating tests. Results: The experiments gives at the end of this article show that the precision of the returned content is effectively improved. The tests were performed with the most popular searching engine (i.e. Google, Bind and Yahoo) selected in particular for their high selectivity. Among the given results, we found that query reformulation improve the first three results by 10.7% and 11.7% of the next seven returned elements. So as we can see the reformulation of users' initial queries improves the pertinence of returned content.

INTRODUCTION
The Information Retrieval (IR) can be defined as an activity whose purpose is to locate and deliver a set of documents to a user according to his needs. To improve the performance of such systems, the contextual information retrieval has recently emerged as a priority (Allan, 2003); its goal is to place the user at the core of models by making certain elements of context which can influence systems performance more explicit.
On the other hand, users of information retrieval system are not professionals in the documentation (Lin and Wang, 2006). They do not know choosing the right words that best express their information needs, so query reformulation is needed. This reformulation is motivated by the fact that the initial query returns a result that rarely meets the user's need, that means to modify the original user's query by adding significant terms to give back a more relevant result.
In this study we propose a contextual query reformulation system; this reformulation is called contextual because it takes into account the context via the user's profiles to change his initial query. By adding the notion of the context during the reformulation, we aim to increase the effectiveness of IRS by improving their relevance and allow the consideration of the user's personal characteristics, his interests, his preferences and the historic of his interactions with a system. These elements are capitalized in our system as a static and dynamic context for later use in the contextual reformulation.
Classic query reformulation approach: The user is often unable to express his exact need of information. Therefore, among the documents returned, some are more interesting than others. Given the increasing volumes of information bases, to find those that are relevant by using only the initial user's query is an almost impossible task.
The query reformulation is to modify the user's query by adding significant terms. The idea of query refinement is not new; several approaches use different techniques for select terms to be added to the initial query. We distinguish three types of query reformulation approaches and the deference between them lies on the one hand in the source of terms used in the reformulation that may come from results of previous research (relevance feedback) or from an external resource (semantic networks, thesauri or ontology). On the other hand, it lies in the method used for selecting terms to be added to the initial query.
The first type of the approaches is based on a global analysis of the considered collection of documents and the most commonly among them is based on statistical analysis of document corpus (Cui et al., 2002). The objective is to increase the frequency of words appearing together in one document and select the terms with the highest coefficient. The information thus obtained is used to reformulate query automatically by adding terms related to the terms already used in the query. The terms added from the documents give a better adequacy between the need for information and the document collection.
The second type of approaches based on the principle of relevance feedback aims to reformulate the initial query to correspond better to the content of the documents collection. The principle is as follows; the user submits his initial query and the system returns an initial set of documents that the user has to judge (relevant, irrelevant). Knowing the relevance of initially returned documents is used for selecting terms to be added to the initial query. We quote in this category the work of (Winograd, 2001) in which the system offers, based on the first query, a set of documents and according to those viewed by the user, the system updates its terms index in concordance with automatic learning methods.
The last type of the approaches, described in the literature, uses external resources of terms such as thesauri or ontology that contain the vocabulary used in the query enrichment, such approaches use ontology with equivalence and subsumption relations (Navigli and Velardi, 2003) in order to extract the terms to be added to the initial query.
The reformulation approach proposed in this study is based on taking into consideration the user's context using his profile. It offers a double benefit comparing to the above presented approaches. On the one hand and contrary to the first two classes of approaches, it is used directly without a phase of analysis or of learning, on the other hand it is not constrained by the problem of the third class of the approaches that use only equivalence and subsumption relations and do not take advantage of all semantic relations provided by the ontology.

Context for information retrieval:
The context is not a new notion in computer science: from the sixties, operating systems, language theory and artificial intelligence already exploited this concept. With the emergence of information retrieval systems, the term was rediscovered and placed at the core of the debates without making subject of a consensus, clear and definitive definition. However, analysis of existing definitions in the literature leads to two conclusions: • "There is no context without context" (Brezillon, 2003). In other words, the context does not exist as such. It is defined or it emerges for a purpose or precise utility • "The context is a set of information. This set is structured, it is shared, it evolves and serves the interpretation" (Winograd, 2001). The nature of information and interpretations got from it depend on the purpose In information retrieval, the context is defined as "All cognitive and social factors as well as the user's aims and intentions during a search session", (Belkin et al., 2004). Generally speaking, the context includes elements of various natures that delimit the understanding, the application fields or the possible choice. The most commonly cited elements concern the spatiotemporal data (location, time, date) or specific knowledge in relation to the studied area. But rarely we see the use of elements concerning the emotions, state of mind cultural information (Brezillon, 2003). Thus some elements of context can be difficult to identify because we use them unconsciously, others are out of reach of machines input devices and therefore they are difficult to be implemented in information retrieval systems.

Aspects of profile relevant to context capturing:
A user profile is defined as "A source of knowledge that includes all the acquisition about the user's aspects that may be useful for the system behavior" (Wahlster and Kobsa, 1986). This proposal, although general, corresponds better to our orientation; it highlights three aspects of profile which are exploited as follows: • Source of knowledge: The user profile may include a variety of information according to the considered task. In information retrieval the content of a user's profile can be summarized in his personal characteristics, his interests and preferences, his competence, his current goal and the historic of his interactions with the system (Belkin et al., 2004). We note that the notion of context, previously presented, is an extension of the user's profile. The context contains complementary information allowing a better adaptation of the profile • Acquisitions: The content of the user's profile is knowledge to recover. Depending on the system adaptation degree, the user's profile data can be informed by the user, or recovered by selecting a preexisting profile created by experts in the domain, or captured by the information retrieval system during use • Useful for the system behavior: In information retrieval the role of the user's profile is to allow personalization or adaptation of services to improve the system performance, or to filter the results returned by a search engine

Classification of profiles and their use in IR:
Different types of profiles are associated with the task of information retrieval. We defined four classes of profile based on grouping criteria, these criteria are the degree of the user's involvement, the moment to use the profile for reformulation, the complexity of information accumulated by the profile and the nature of information that composes the profile.
According to the user's involvement: It is to measure the degree of the user's involvement in the process of his profile catching. In (Benammar et al., 2002), the author distinguishes two types of profiles management: • Indirect: It's the case where the profile management is transparent to the user, in the sense that the user does not intervene in the management of its profiles • Direct: In contrast, in the direct management of profiles, the user must intervene in all stages of the research process to manage his profiles According to the reformulation moment: Here we look at the moment to use the profile in information retrieval system; two possibilities are to retain: • Pre-research: A profile can be used in a preresearch stage to help the user to formulate or reformulate his information need. It can be for example to refine the expression of a query proposed by the user according to his profile • Post-research: A profile can also be used in a postresearch stage to filter the search results According to the complexity: In this category, we focus on the degree of the complexity of the information contained in the profile. Different formats of this type of profile have been studied in (Korfhage, 1997), the most important ones are: • Simple: Simple profile is presented as a set of keywords and eventually an associated coefficient to measure the importance of each term in the profile • Extended: Extended profile includes, in addition to keywords and their coefficient, a set of information that describes the research context According to the nature of information: The last class distinct user's profiles based on the nature of information they contain, the work of (Benammar et al., 2002) exploits the following profiles: • Identification profile: This component of the profile is used to identify the user through a set of information. It is defined in the first connection to the profiles system and is updated at each increment by creating a querying profile • Querying profile: It can be likened to a query. It reflects the user's information needs and facilitates the association of the research made by the user to his context The different classes of profiles that we identified can be used simultaneously in the same system and the usage of a profile type does not mean the isolation of the others. However, a profile based system must define the characteristics of each type of used profiles and the links that connect them. In the rest of this study we present our system and justify the choice of its parameters in terms of profile, we also describe the proposed architecture and the developed prototype.

Choice of system parameters:
We have previously prepared a comparative study of the elements needed to the development of our system. They are the reformulation, the context and the use of profiles in information retrieval systems. This study has allowed us to categorize separately the characteristics of these elements and identify the limits of each category. We present here the different parameters characterizing our proposal and describe our choices compared to the approaches previously studied.
In terms of query reformulation: The reformulation approach that we propose in this study is based on taking user's context into consideration via his profile. The contextual reformulation system proceeds an automatic refinement or extension of the initial query by adding or substituting words. The terms of reformulation are extracted from the user's profile depending on the context of the underway research session. Table 1, locates our approach compared to the approaches previously studied.
In terms of the profile use: Our choice was fixed on the use of context for the user's query reformulation. We presented previously the different classes of profiles and the specific aspects of each class. Table 2, presents the parameters characterizing our system in terms of user's profile. Table 2 shows our choices concerning the user's profiles and therefore the manner in which the context is used to help the contextual query reformulation. These choices are interpreted as follows: • User involvement: In our system the user intervenes partially to define his profile, so the involvement is direct; the system automatically recovers the supposed relevant information to enrich the user's context for possible future research and provides them to the user, who will validate those he deems truly relevant among all proposals • Moment of reformulation: In our case it is a preresearch profile. The system reformulates the user's need by refining the expression of his query according to his context • Degree of complexity: The profile is extended. It includes, in addition to keywords, a set of information describing the research context. This information is stored in a table as an attribute-value pairs, where each pair represents a property of profile • Nature of Information: We use at the same time and in a complementary manner identification and querying profiles. The first to identify a user using a set of information defined in the first connection to the system and the second is recovered from the historic search of the same user in the subsequent sessions, so its content increases every time the user makes a new search.

Summary:
We group our choices in terms of profile use for the context modeling into two major classes: • Static Context: It is defined from an identification profile with an extended degree of complexity, an indirect involvement of the user and a pre-research moment of use • Dynamic Context: It is defined from a querying identification profile with an extended degree of complexity and an indirect involvement of the user and a Pre-research moment of use: Static Context = (Identification profile + Extended +Pre-research + direct) Dynamic Context = (Querying profile + Extended +Preresearch + direct) System architecture: We propose a contextual query reformulation system for information retrieval on the web. This reformulation is called contextual because it is based on coupling between the static and the dynamic user's context that are modeled by using the user's profiles to allow the expansion of the initial query. The goal is to return a result more relevant than the one returned by a search without reformulation. Figure 1, shows the general architecture of our system and illustrates how static and dynamic contexts are caught to be used later in the contextual reformulation process. Calculates the frequency of terms in a document Requires a analysis phase Selects the terms with the highest coefficient Based on relevance feedback Performs a first search using initial query terms Requires a learning phase Relevant documents returned by using the first query are used to refine the search Based on terms of external resources Uses ontology or thesauri containing the Does not take advantage of all semantic vocabulary used in the enrichment of query relations provided by ontology Our approach Based on static and dynamic context Uses the context via the user's profile to reformulate automatically the initial query by adding terms extracted from the context of current research  Fig. 1: General architecture of the system for the contextual query reformulation Before formulating his query, the user must be identified in the system which proceeds to the recovery of its static context that consists of the user's personal characteristics that may influence the research context (age, sex and language), his interests and preferences related to the research task (domains of competence and specialty) and his competence level or his expertise (profession and level of study). This information is stored in the user's context base during the first connection to the system. In case of a user who does not have a profile, the system asks him to complete his preference and the user's context base will be updated in order to use it in any future search sessions.
After having recovered the static context, the user can formulate his query and the system takes charge of his reformulation automatically. It generates the new query by selecting terms related to the context of the current research session. This selection is made from the user's context base. Both types of context (static and dynamic) mutually contribute to the operation of reformulation. Thereafter the system proceeds to an open search on the web by using the reformulated query and calling, according to the user's choice, one of the three search engines that suggests (google, yahoo or bing). The search result is finally returned to the user and it will also be stored in the historic search base in order to be used later in the catching of the dynamic context.
At the end of each search session and based on the historic search base, the system automatically retrieves the information that supposed relevant to enrich the dynamic context of the user (contextual elements). The system suggests this information to the user to validate those he considers truly relevant among all proposals and increases the content of the dynamic context.

RESULTS
To prove the applicability of the proposed architecture, we implemented a prototype of a system for contextual query reformulation. PRESY is a .Net application using a Microsoft Access data base which manages the users' profiles. This database contains two tables, the first serves to save the user's preferences (static context) and the contextual elements (dynamic context) and the second table contains the historic of the user's research that is used to catch the dynamic context.

General description:
The system displays two results. The first without reformulation (Fig. 2, area A) and the second with reformulation (Fig. 2, area B). The aim is to compare the scores of relevance in terms of page number returned in the two situations; we note that these scores are calculated by the selected search engine. The interface also offers the possibility to choose the desired search engine (Fig. 2, area C) and gives the score of relevance in terms of number of pages returned in both cases, research with and without and reformulation (Fig. 2, area D). Finally the system captures and offers the contextual elements witches are used to enrich the dynamic context of the user (Fig. 2, area E). Figure 2 presents the main interface of the developed prototype.
Catching of dynamic context: To catch the dynamic context, the system automatically analyzes the content of the returned web page and proceeds as follows: • Retrieves the title of each result and proceeds to its segmentation into a set of words • It eliminates the empty words using an antidictionary • It proposes the obtained words witches are supposed relevant to enrich the dynamic context to the user • Finally the user validates terms those he considers truly relevant among all proposals and the system increases the content of the dynamic context User's query reformulation: To ensure the reformulation of the initial user's query, the system retrieves the user's input and compares it with the contents of its context database, after the system retrieves all attribute-value pairs whose left side is identical to the initial query and offers the right side as opportunities of reformulation proper to the current context search. The content of the list of proposals is updated as the user progresses through the seizure of his query. Finally, the best form of reformation is used and the search result is displayed. The Fig. 4 presents the user's query reformulation process.

DISCUSSION
To carry out the evaluation of our system we performed the same set of 15 queries, both on Google, yahoo and Bing. These queries were made up of 10 simple scenarios covering the range of current needs of a user (they were simple applications of thematic travel, consumption, news and culture) and 5 complex scenarios (rare word or specialized search). Each time, the first ten results displayed have been examined and evaluated for both research, with and without reformulation.
We evaluated the performance of our system according to the relevance of the top 10 results in the three following criteria: • Criterion 1 (C1): the relevance of the first three results • Criterion 2 (C2): the relevance of the last seven results   Each criterion (Cwas rated on 10. Each query received an overall rating out of 30 (3 criteria rated on 10). Each search engine has received-in both cases of research, with and without reformulation-a note on 450 points (30×15 scenarios) reduced to a note on 10. Table 3 shows the results of this evaluation. Table 3 shows that for the relevance of the first three results with the three search engines, searching with reformulation gives a higher score than that obtained without reformulation. We also note that google tops the list with an improvement of 1.07 point where the query is reformulated.
On the relevance of the last seven results, the two search engines Google and Bing are better adapted to our reformulation system by giving a score higher with the use of a reformulated query, the score increases by 1.17 point in the case of google and by 0.68 in the case of Bing. In contrast the reformulation of query decreases the score of relevance in the case of yahoo by -0.24, this decrease is because the search algorithm used by yahoo works better with a query containing fewer keywords.
Finally, with regard to the rate of redundant results, the three search engines have achieved a higher score after query reformulation. The gap between research without reformulation and with reformulation is respectively 0.79 in the case of google, 0.99 in the case of yahoo and 0.69 in the case of Bing.

CONCLUSION
The aim of this research is to investigate and discuss the consideration of user's context in information retrieval. In this study we proposed a contextual query reformulation system that catches the user's context according to his profile to modify his initial query. First, we presented the notion of context for information retrieval system. After that, to clarify the concept of user's profile, we defined and classified the user's profiles according to their use in the information retrieval domain. During the presentation of our system, we justified our choice of system parameters, presented our architecture, showed how the static and the dynamic contexts are caught and illustrated the manner in which these two contexts are mutually used in our proposal. Finally, we described a scenario of a contextual reformulation as processed by our system. This study paves the way for diverse perspectives that are located on two levels: deepening of realized research and enlargement of its application field. With regard to the deepening of the proposed work, it would be interesting to improve the developed prototype in the sense that catching the elements related to the user's dynamic context is done without his intervention and in terms of the application field expansion, it would be interesting to test the proposed architecture on several search engines to measure the contribution of contextual reformulation on each of them and focus the prototype on the search engine that adapts best to our proposal.


Pattern-Based Ontology Construction from Selected Wikipedia Pages

In this paper, we describe how ontologies can be built automatically from definitions obtained by searching Wikipedia for lexico-syntactic patterns based on the hyponymy relation. First, we describe how definitions are retrieved and processed while taking into account both recall and precision. Further, concentrating only on precision, we show how a consistent and useful domain ontology can be created with a beneficial precision of 80%.

Introduction
Knowledge bases are created to depict models of the world in the way we perceive it (Lacy, 2005). Nowadays, the general concern about the representation and communication of information increases the need to do the latter in a more meaningful and structured way (Brachman, 1983). Natural Language Processing (NLP) is a task, which is relatively easy for humans, but presents a complex computational challenge, as machines need carefully structured and well-designed content to unambiguously interpret information (Lacy, 2005). Ideally, one creates hand-crafted thesauri, such as WordNet 1 , which are more reliable, but with information constantly changing, their coverage falls behind and costs of maintenance remain high. Thus, the possibility of creating knowledge bases from regularly updated knowledge sources, such as Wikipedia 2 , which offers a vast amount of information on a wide variety of topics, seems to be a desirable solution for this difficult situation.
In this paper, we present the Ontology creator (Oc) 3 , which extracts articles from Wikipedia, searches them for definitions and transfers the results into an appropriate knowledge representation using the ontology language OWL 4 . For this purpose, we use lexico-syntactic patterns that were reported to enable successful extraction of semantic relations (Hearst, 1992;Hearst, 1998;Mititelu, 2006;Mititelu, 2008). We evaluate the overall system performance and concentrate on successful hyponymy patterns in order to improve the resulting ontology's precision. Our hypothesis is that, by searching Wikipedia for the hyponymy relation, one can create consistent domain ontologies that can be easily used as good knowledge bases.
Thus, section 2 gives an overview of related projects. In section 3 we introduce the Ontology creator and describe how patterns are built and represented in the knowledge base. Further, in section 4 we evaluate the system performance and describe the most common errors that we observed. Section 5 closes with a concluding comment.

Related Work
In order to be able to extract definitions from domain-independent, unrestricted text, methods for discovering lexico-syntactic patterns are generally used, employing English corpora (Hearst, 1992;Hearst, 1998;Mititelu, 2006;Mititelu, 2008), such as the British National Corpus. Lexico-syntactic patterns can model semantic relations, such as hyponymy (the notion of hyponym-hypernym in the sense that if L 0 is a (kind of) L 1 , then L 1 is hypernym to L 0 (Hearst, 1992)). As reported by Mititelu (2008), some patterns' success rates reach 100%. Suchanek et al. (2008) also used Wikipedia as the information base. The authors extract facts from Wikipedia's infoboxes and combine these with the category structure of WordNet into an ontology. In this way, they maintain a clearly-structured hierarchy of word senses, enriched by Wikipedia's vast amount of information with a final precision of 95%.

Ontology Creation
In order to examine our hypothesis, we designed a system, the Ontology creator, that extracts definition relations from Wikipedia and converts them into a representation in OWL. Thus, in section 3.1 we introduce the system module that collects the articles. Further, in section 3.2, we introduce the parser that is used to assign grammatical structure to the individual sentences. Section 3.3 focuses on the lexico-syntactic patterns and section 3.4 explains how a pattern match is represented in OWL.

Extracting from Wikipedia
For the purpose of building a domain-specific ontology that concentrates on only one area of knowledge, it is necessary to collect articles that are highly topically-interlinked. Consequently, for the acquisition of articles from Wikipedia, we use a webcrawler, that starts with a given article and collects pages that have a referring link to it. We employ the open-source webcrawler JSpider 5 , which is a highly configurable Web Spider engine. It allows to limit the search to only one website, to set the depth into its structure as well as the MIME type and to restrict the number of resources to be fetched per site. These features are all important to keep the articles' topics as closely related as possible. Currently, the depth level is set to two, which will produce a fair number of connected pages.

Parsing Articles
To gain a more accurate basis for the pattern search, the Oc uses the Stanford parser (Klein and Manning, 2003) to derive grammatical structures for each sentence. To bridge the stages from the HTML article to a usable list representation for the parser, we used the DocumentPreprocessor 6 .

Building Lexico-Syntactic Patterns
For extracting definitions from text, we make use of lexico-syntactic patterns indicative of the hyponymy relation. Since definitions represent statements about the world, they are often expressed in terms of each other, where one concept is used to define another one (Brachman, 1983). Hyponymy, or the IS-A link, is one of the most basic types of conceptual relations for categorising classes of things in the world represented, carrying with it the notion of an explicit taxonomic hierarchy (Brachman, 1983). One deterministic characteristic of a taxonomic hierarchy is that all members inherit the properties of their respective superclass by virtue of being an instance of that class (inheritance of properties) (Brachman, 1983). Classes can be made up of subclasses or individuals. Classes may be viewed as classifying types, since they are abstract concepts of physical or virtual objects in the world. If a class is a subclass to another one, it will introduce a more specific concept than its superclass. Members of a class are instantiations of a particular class concept. (1) An apple is a fruit.
Example (1) is the explicit version of ordinary hyponymy, which allows the inheritance of lexical semantic properties. There are lexico-syntactic patterns for different semantic relations, although hyponymy seems to yield the most accurate results. Yet, in order to use a specific pattern, one has to define how its variables are realised in natural language (exemplified in (2)) (Hearst, 1992): (2) N P0 such as N P1, N P2..., (and | or)N Pn Building a search pattern for the above example is realised when an N P 0 (indicating the superclass) is represented by a single noun phrase consisting of a proper noun or a determiner, a noun and an optional adverbial phrase, whereas N P 1 , N P 2 ..., (and | or)N P n may consist of more than one of the above noun phrases. Using these specifications to search for definitions in the sentence: "Other forms of deception, such as disguises or forgeries, are generally not considered lies, though the underlying intent may be the same.", one obtain matches as: hyponym("forgery","deception"), hyponym("disguise","deception").
The patterns that were integrated into the Oc (listed in table 1) were suggested by Hearst (1992) and extended by Mititelu (2008). We used a subset of them, consisting of those rated the highest (discarding patterns for lack of results or for performance reasons). We also modify pattern 11 to admit plural matches and synonyms. In order to optimise the pattern search, we use the JRegex 7 li-

Data Processing
In order to depict obtained definitions, we use an ontology representation. In the context of computer and information sciences, ontologies are meant to formally describe the terminological concepts and relationships that constitute a domain and generally provide a more common understanding of it as well as one that can be communicated between humans and machines. Thus, an ontology is a formally described, machine-readable collection or vocabulary of terms and their relationships and is used for knowledge sharing and reuse. Ontologies are encoded into files using ontology languages. A taxonomical ontology is the most common form of an ontology. It consists of a hierarchy of concepts which are related with specialisation IS-A relationships (Lacy, 2005). OWL is one of the languages that can be used to define ontologies and the associated individual data.
For this project, we use the OWL DL dialect, as it supports consistency checks and reasoning and thus allows us to infer new facts from existing ones. The hyponymy relation in OWL can be expressed through the use of the relation between a superclass and its subclasses or members. Since we have only general indications of what the various matches can look like, we use a processing approach that is appropriate for most entities. The first decision to be taken is whether to make a noun phrase into a new class or an individual. This, however, is only relevant for N P 1+i since N P 0 always has instances and therefore always constitutes a class.  Figure 1: Complex subclass example in OWL wise the current string is processed as a subclass. All modifiers are set to become subclasses of the predefined characteristicValues class and are linked to the respective class through the hasCharacteristic property. The number of superclasses/subclasses in a match is also dependent on the number of modifiers of both N P 0 and N P 1+i . If we consider as an example the following: "... primitive animals, such as starfish ..." that leads to the relation: hyponym("starfish"-N P 1 ,"primitive animal"-N P 0 ), where a modifier of N P 0 is present , there will be a class Animal, which will be superclass to PrimitiveAnimal in an intersection with hasCharacteristic some Primitive and Animal. This in turn will be superclass to the Starfish class. We assume that nouns that are modified by some adjective would constitute an own concept and will only be more specific through this addition.
Superclasses that consist of multiple nouns will not be subdivided any further, since one cannot assume that each noun by itself will actually constitute an own class or convey a separate concept in the same way. Figure 1 depicts the conversion of N P 0 featuring a head with an of-complement as in "... flavour of substance, such as vanilla,...". In this case Flavour is made into a class with subclasses: Vanilla,...etc. and linked through a new property called hasFlavour, which has Flavour as its range, to the new SubstanceWithFlavour class, which will be subclass to a general Substance class.
This representation may not always be the most suitable, but concepts introduced by an ofcomplement 9 do present a difficult case. The processing of N P 1+i featuring an of-complement cannot be done in the same way, since there is no range for a possible property relation as in the previous example. Furthermore, the concept introduced by it is usually already rather specific. Although OWL allows defining distinct members and disjoint classes to mark mutual distinctness, we cannot in general make all classes or individuals

Experiments
In order to investigate the system performance in regard to recall and precision, in section 4.1, we look at the performance overall and in section 4.2, we attempt to fine-tune the system to obtain the highest possible results in regard to precision.

System Evaluation
For the purpose of evaluating Oc's performance, its final output was compared to a gold-standard. Therefore, we let the program process 20 topically-related Wikipedia article extracts (a total of 641 sentences) and compare the results to the gold-standard analysis of the same sentences. The manual analysis was subject to various criteria. A definition relation was only recognised as relevant or correct if the subclass/individual clearly translated into a sub-concept/instance of the superclass. Moreover, it was also evaluated how useful or appropriate the match is. We do not count more complex concepts that consist of a head with more than one of-complement or relations where subclass and superclass are separated by extra nested relative clauses. A match, whether successful or not, consists of a superclass and its subclass/individual. Relations that are obtained by simple derivation of the system are not counted, for example "... snacks such as nuts, dried fruit, ..." results in: hyponym("Nut","Snack"), hyponym("DriedFruit","Snack") and hyponym("DriedFruit","Fruit").
Yet, the third relation is derivative from the entity itself and is therefore not counted.  were matched ideally, 7 incompletely (parts were missing) and 6 incorrectly. We also show the various categories of relations that were not found. 73 are not retrieved because there is no appropriate capturing pattern yet, 2 are due to incorrectlyassigned parser tags and 47 matches are not found because of missing patterns. Thus, the Oc manages to reach a recall of 32% and precision of 80%. The F 1 measure with recall and precision weighed equally lies at 46%. Yet, using an abundant source, such as Wikipedia, takes the burden from the general lack of data, which allows us to rate precision twice as high as recall. Thus, F 0.5 marks a 62% overall system performance. A more systematic representation of the figures is shown in table 3. Missing Patterns: If we consider the sentence: "Piquance is considered another such basic taste in the East.", we see that a pattern, such as N P1 V P * another such N P0 is needed. Similarly, in 73 of the 122 cases where relations are not captured a new pattern can be added.

Reasons for Non-Retrieval
Ambigious Patterns: Further, in 39% of the cases the appropriate pattern was also missing, but not as easy to replace as in the aforementioned scenario. For example in: "Couverture is a term used for chocolates rich in cocoa butter..." the range, "term used for chocolates rich in cocoa butter", is a complex concept that is difficult to convert into one distinct superclass. An additional problem is that the mechanism would go as far as "term" and then stop, resulting only in Couverture ⊂ Term. Although it is technically possible to check that there is no identifying clause following the prospective superclass, this has proved even for smaller cases to be extremely time-consuming and since the classic IS-A pattern did not account for many cases, it seemed wiser to forgo this option and leave out the pattern entirely. An even more difficult matter is presented by "The word cacao itself derives from the Nahuatl, Aztec Food,Poison ⊂ Flavour SubstanceWithFlavour:hasFlavour some Flavour ∩ Substance Figure 2: False processing example language, word cacahuatl..." leading to hyponym("Nahuatl","Aztec language"). There is little in regard to distinguishing environment to seperate results of mere enumerations from one of two terms that are in a hyponymy relationship and separated by a comma. Such examples lead to a drastic reduction in precision. Thus, it seemed sensible to process more articles on the topic to compensate for potential matches of these cases.

Captured Relations Issues
Having described frequent issues connected to definitions that were not captured, we now examine the ones that were retrieved. Even though with 80% the overall precision is reasonably satisfactory, we now also consider whether the respectively assigned representation in OWL is appropriate.
Patterns not Exclusive to Hyponymy: In some cases incorrect processing is due to the fact that the pattern is not exclusive to hyponymy, but covers simple non-hyponymy sentences as well, as in "The majority of the Mesoamerican people made chocolate beverages, including Aztecs, who made..." Yet, there are patterns that are more reliable to produce hyponymy and for the benefit of higher precision, one can concentrate on those.
Incomplete: The question of the appropriate representation in OWL is more difficult to evaluate. Most issues concern heads with an ofcomplement as superclass, where it is not clear what the subsequent clause is referring to. In most cases the OWL results are not wrong, but in at least 2 cases they seem awkward. For example: "It refers to the ability to detect the flavour of substances such as food, certain minerals, and poisons, etc." results in the structure in figure 2, while it should have processed as Food, Poison... ⊂ Substance. This is partly due to the ambiguity resulting from the scope of the noun phrase referenced, for which the parser did not make any difference in structure. Thus, it is worthwhile to reconsider the way the of-complement is processed.
Creating an ontology from a small set of sen-  tences, as was done here, is bound not to yield a large ontology. Our system obtained a total of 52 correct relations from searching 641 sentences. Most relations are topically-related, although there are some which are not, since referring links sometimes bear only a remote relation. In this ontology, which started on the term "chocolate", we also find facts about dialectologists. Creating larger ontologies may circumvent such problems which Wikipedia's ample resources would also allow. Yet, what is essential and of primary interest to us, is the ontology's correctness and appropriateness.

Ontology Evaluation
After both a quantitative and qualitative analysis of the Oc, which were able to highlight the more frequent issues in connection to pattern-based ontology construction, we now concentrate on further enhancing precision. Recall can be increased by adding new patterns or widen the scope of the existing ones, although in our case it is essential not to compromise precision in any way. In this context, we choose to give precision a clear priority, since we are not looking for as many relations as possible, but for as many correct ones as possible. In order to further precision we concentrate on more successful hyponymy patterns and use a larger sample to obtain more accurate results. The articles were collected across a couple of different topics to also test for the patterns' suitability independent of the genre. Since this is a larger sample, we are not able to make a close analysis of whether the match yielding a relation is appropriate, as we had done during the first test. Important is only whether the final relation in the ontology is correct and appropriate in terms of content, superclass/subclass relation and processing, as we aim to determine the usefulness of the ontology overall. For the current experiment, we retained patterns: 2, 3, 4, 5, 8 and 9 (table 1).   19%). The of-complement matches appeared in 6% of all matched relations. The final system precision based on the ontology evaluation is slightly higher than the precision we achieved by evaluating the general system performance, which is not surprising since building larger ontologies also leads to a more accurate evaluation as well as to more overlaps of facts, where incorrect ones sometimes compromise correct ones. In the following part, we look at the different issues the resulting ontology poses and how they can be addressed in future research.
General Issues One of the general issues that can be observed is a classification problem. A specific entity is sometimes classified as two slightly controversial things. The facts in figure 3 both appear in the ontology, resulting from a more biological classification of tomato (fruit) and a maybe slightly more practical one (vegetable). Both facts are correct for their scope, but e.g. make it impossible to have fruit and vegetable as disjoint classes. At the moment, there is no component that deals with this issue, as a relative correctness would maybe also depend on the application area. Issues with of-complements, as have already been described in 4.1, remain. In the current set, 6% of the matches had an of-complement. In general, the easiest option is to disregard matches with these grammatical structures completely, however, if genuine they do express a particular kind of relationship that would not be captured in quite the same way otherwise.
Necessary Additions Until now, we had not included past participle in verb phrases. However, there are examples which show that this decision should be re-assessed: "...NP JJ alcoholic NNS beverages, RB especially NP VBN distilled NNS beverages...". Since "distilled" is disregarded, this yields the relations hyponym("alcoholic beverage","beverage"), which is derived from the superclass: "alcoholic" modifying "beverage", and hyponym("beverage","alcoholic beverage") and consequently, every "beverage" is also per definition an "alcoholic beverage". In addition, it would be beneficial to create more disjunct members or disjoint classes which would provide a possibility for a self-check in the Oc. Although, as has already been pointed out, classification issues may render this difficult.

Conclusion and Future Work
The overall aim of this project is to build consistent domain ontologies from facts obtained from websources, such as Wikipedia. In our work, a large number of relations remained unmatched, but the high precision encourages further research in this area. Since Wikipedia is an extremely big resource, one can afford losing prospective facts for the benefit of obtaining a more correct and hence more useful knowledge base. In order to enhance the Oc, it would be necessary to put more work towards the idea of disjointness and disjunct members in OWL. This way the resulting ontology would be more alert to irregularities. Further, one could evaluate the different patterns in regard to their respective ambiguity dimensions.


extfieldsofstudy:
Mathematics
Computer Science

text:
A Solution to the Crucial Problem of Population Degeneration in High-Dimensional Evolutionary Optimization

Three popular evolutionary optimization algorithms are tested on high-dimensional benchmark functions. An important phenomenon responsible for many failures - “population degeneration” - is discovered. That is, through evolution, the population of searching particles degenerates into a subspace of the search space, and the global optimum is exclusive from the subspace. Subsequently, the search will tend to be confined to this subspace and eventually miss the global optimum. Principal components analysis (PCA) is introduced to discover population degeneration and to remedy its adverse effects. The experiment results reveal that an algorithm's efficacy and efficiency are closely related to the population degeneration phenomenon. Guidelines for improving evolutionary algorithms for high-dimensional global optimization are addressed. An application to highly nonlinear hydrological models demonstrates the efficacy of improved evolutionary algorithms in solving complex practical problems.

I. INTRODUCTION
E VOLUTIONARY optimization algorithms for unconstrained optimization attempt to discover the value and location for the global optimum of an -dimensional function: In the search, the solution vector is solely derived from the values of the function without the use of the function's derivatives. The objective function can be in the form of either a mathematical expression or a physical model's computer program, which makes the optimization algorithms a variety of applications in science, engineering, and business [1]- [10]. Current evolutionary algorithms are mostly featured with particle-based evolution processes: the algorithm first randomly distributes a "population" of "particles" (or members, points) ,with and is the size of population (number of samples), to sample the objective function in the search space, then sequentially evolve the population by substituting the existing particles (as parents) with new ones having better function values (as offspring). After many generations of evolution, the population is expected (but not guaranteed) to have at least a particle reaching the global optimum.
Recently, a large number of evolutionary algorithms or algorithm modifications have been developed using genetic-, swarm-, annealing-, and hybrid-based mechanisms to enhance the reliability and efficiency of the evolution processes. These algorithms supported by powerful computation capability have shown good performances in global optimization and become popular increasingly. However, even with these algorithms, global optimization can still be problematic or computationally demanding for high-dimensional cases ( ). High-dimensional problems challenge evolutionary algorithms because the feasible space grows exponentially with increase in dimensionality and the impracticality of increasing the population size in the same manner. Many existing evolutionary algorithms do not pay enough attention to this aspect and sacrifice efficacy due to implementing searches of high computational demand. Therefore, understanding the mechanisms of algorithms that cause success (or failure) and efficiency (or inefficiency) of searching in high-dimensional spaces, is a prerequisite to overcome the theoretical barriers. In this study, we use high-dimensional benchmark functions to test three popular evolutionary algorithms. The selected algorithms are the Shuffled Complex Evolution (SCE-UA)-an algorithm based on simplex scheme, the Particle Swarm Optimizer (PSO)-an algorithm simulating the social activity of animal groups; and the Deferential Evolution (DE)-an algorithm using genetic hybridization.
Although the search strategies of each of these algorithms originate from distinct scientific fields, we show that they all possess two opposite functionalities: 1) exploitation: the process of making particles converge to the global optimum, and 2) exploration: the process to enable particles to explore the feasible space of parameters. The exploitation process tends to drive particles to the most prominent region in the feasible space and speed up the search. Meanwhile, this process increases the risk of missing the global optimum. The exploration process attempts to overcome this problem by diversifying the search directions. This process increases robustness of the search, but at the expense of dragging down the speed of convergence. Detailed analysis of the selected algorithms' processes and performances on high-dimensional benchmark functions revealed that the barriers which keep each algorithm from success of efficient optimization on high-dimensional problems are closely related 1932-8184/$26.00 © 2011 IEEE  TABLE I  PSEUDO CODES FOR STUDIED ALGORITHMS to implementations of these two functionalities. Balancing these two functionalities is a key aspect of constructing a successful algorithm.
In this paper, we report the results of our study which reveals that in high-dimensional searches, some exploitation processes tend to drive particles into a subspace of the feasible space. In other words, at certain stages during the evolution, all the particles in the population move into a subspace, which has smaller dimensionality than that of the search space. Subsequently, the search will tend to be confined to the subspace and eventually fail if the global optimum is excluded from the subspace. We refer to this phenomenon as "population degeneration." Principal components analysis (PCA) [11] of particle population is used to detect the occurrence of degeneration. Furthermore, principal components (PCs) can provide information useful to remedy the adverse effects of population degeneration.
II. SELECTED ALGORITHMS Three among the most popular evolutionary optimization algorithms are investigated in this study. The pseudo codes for the selected algorithms are summarized in Table I. The algorithms all start from an initial population (first-generation) of randomly sampled particles within the search range in the feasible space. Afterwards, the offspring replacements with different mechanisms are initiated in order to evolve the population.

A. Shuffled Complex Evolution (SCE-UA)
The SCE-UA algorithm [12], [13] employs the Nelder-Mead simplex scheme [14], [15] to make particle replacements for population evolution. An -simplex is an -dimensional "pyramid" (convex hull) in with affinely independent vertices and edges (e.g., 1-D simplex is a line segment; 2-D simplex is a triangle; 3-D simplex is a tetrahedron.). Starting with a simplex located inside the search domain, the scheme first ranks the vertices according to their function values, so that then it attempts to replace the worst vertex with a new point on the line between and the centroid of the rest vertices, . Parameter determines the location of the new point on the line and several values (in SCE-UA,  for reflection,  and for contraction) will be tried to find a new point having If successful, the worst vertex is replaced by the new point, otherwise, is replaced by a random point (mutation) in the search domain. In this scheme, information from a simplex's vertices on the response surface of the benchmark function is used to approximate the direction for steepest descent. Driven by the direction of steepest descent, the simplex can effectively find a better offspring . To prevent simplexes from converging to local optima and to enhance the chances of finding the global optimum, SCE-UA utilizes the shuffled-complex process. At the start, the particle population is partitioned into complexes. Each complex includes particles and evolves independently using the simplex method. At the beginning of every iteration of evolution, a simplex is formed within each complex by randomly selected out of the particles in order to perform simplex search. Once a worst vertex is replaced, the simplex will be broken down and its particles return to the complex. We refer to this procedure as simplex subroutine. After each complex completes a certain number ( in this study) of simplex subroutine, particles in all complexes are mixed, sorted and re-divided into new complexes through the shuffling procedure (see Table I), and one iteration ends. By shuffling, the new complex is likely to contain particles from all the previous complexes, hence having information about the function over the region covered by the entire population instead of a single complex. This gathering of information from all the previous complexes results in a better chance for the new complexes moving towards the global optimum.

B. Particle Swarm Optimizer (PSO)
The concept of PSO [16], [17] originates from the computer simulation of the social activities of a bird flock or fish school in which individual members can benefit from its own experience and other members' best discovery during their search for food, mates, or better living conditions. The algorithm starts from a randomly selected initial population and evolves individual particles successively. Each particle's position is updated by trying a displacement (velocity) based on three sources: (1) the particle's velocity in the previous evolution ( ), (2) the particle's best ever position ( ), and (3) the population's current best position ( ): where , , and are the significance coefficients and are random vectors with uniformly generated components is defined as producing a new vector having components . If , otherwise no replacement occurs. A particle's velocity is bounded by the maximum velocity . In the algorithm, taking the displacement with reference to the best point in the population makes a particle have better chance to find an offspring and drives particles moving towards a convergence. In contrast, the particle movements will diverge strongly by historical and current information ( and ) from individual particle's path and the random vectors that alter the component magnitudes of the displacements.

C. Differential Evolution (DE)
The DE algorithm [18] uses the so-called "greedy" scheme to generate offspring. Similar to the PSO algorithm, it attempts to replace the population's particles one-by-one with an offspring. In the DE algorithm, for a particle , the candidate offspring has hybridized components from and another random variable according to a randomly generated number : where is the crossover constant, is the scaling factor and is the component index. If , otherwise the parent survives to the next evolution.
In DE algorithm, the use of random vector is a loose process that tends to have the offspring generated along random directions. The hybridization process also helps making population evolve randomly.
SCE-UA, PSO, and DE are three very typical methods and posse distinct search strategies. The SCE-UA algorithm is a steepest descent method, employing particles (i.e., the simplex vertices) to approximate slope of the objective function's response surface in order to speed the evolution. On the other hand, the DE algorithm is an method heavily relying on randomness such that the discovery of an offspring relies on a randomly selected set of three particles from the population. As for PSO, its search strategy falls somewhere between SCE-UA and DE. In SCE-UA, the divergence process (the shuffled-complex procedure) is at the particle level while in both PSO and DE algorithms, the particles are broken into components for more diverse searches. Those differences in search strategy significantly affect their global optimization performances on high-dimensional problems, as demonstrated through the benchmark function tests

ALGORITHM EFFICIENCY AND ROBUSTNESS D. Benchmark Functions
We chose two benchmark test functions that represent two major types of test functions: classical and compositional. The first one is the popular Griewank function. Like many classical benchmark functions, Griewank function has a regular and symmetrical shape. As shown in Table II, this function is constructed with two components: 1) an -D sphere function that gives the global minimum at the origin, and 2) an -D wave function that overlies on the trend function, , and creates many local minima surrounding the global minimum (see the 2D response surface in Table II). This feature makes the Griewank function serve well for testing an algorithm's capability of escaping local minimums and converging to the global minimum.
The second benchmark function is a composition function (CF1) suggested by Liang et al. [19]. As shown in Table II, the composition function is a weighted summation of ten sphere functions: By changing vector and scalar the sphere functions can have variable magnitudes and can be located at different positions in the feasible space. Weight functions are used to em- phasize the impact of the corresponding sphere function in the region around its sphere center. Unlike most traditional benchmark functions, the CF function's response surface is characterized with multiple irregular attractive regions (with distinct shapes and sizes) converging to individual minimums at different levels. The lowest one is the global minimum. This irregularity poses a great challenge for evolutionary algorithms, especially when the global minimum is located within a small convergence zone close to the border.
Noticeably, both the benchmark functions are continuous and smooth (differentiable everywhere). The points where the function reaches either local or the global minimums have zero gradient ( ). These points are identified as the stationary points.

E. Experimental Setup
The SCE-UA, PSO and DE algorithms are compared on both benchmark functions of 30-D and 100-D. The maximum number of function evaluation is set at 500 000 for the 30-D experiments and 1 000 000 for the 100-D experiments, respectively. Each of the experiments is run 30 times with different random seeds. All algorithms' runs start with an initial population of particles, where is the dimensionality of the benchmark function.
Parameters in each algorithm are specified to their default or popular values: 1) SCE-UA: The number of complex ( ): . Each complex has particle. Therefore, the population size is particles.
2) PSO: The significant coefficients: the inertia weight is held as a constant . (Based on preliminary experiments, we did not found noticeable difference in performance between the use of an annealed and a constant . This is in accord with the study of [20]) and are set at 2.
is half of the search range.
3) DE: The crossover constant ; the scaling factor . As reported in [21], bound handling is critical to the performance of PSO. The widely used random and absorbing bound handling schemes may paralyze PSO when applied to high-dimensional problems. The difference in effects from different bound handling on SCE-UA and DE are not as evident as on PSO. Therefore, in this study, we adopt reflecting bound handling method for all three algorithms. In this method, when a particle flies outside a bound in one of the dimensions, the bound will act like a mirror and reflect the projection of the particle's displacement. These results indicate that, in the case of Griewank function, the increase in dimensionality causes the efficiencies of PSO and DE to drop more significantly than that of SCE-UA.

1) Results for the Griewank Function: As illustrated in
2) Results for the CF1 Function: In Fig. 1(c) (the 30-D experiments), for SCE-UA, all the runs reach the close vicinity of global minimum, but are unable to converge to the global minimum. As geometric sizes of populations become very small, all of the optimization runs terminate prematurely as though they had converged to a minimum point. These termination points randomly distributes around with mean BFV of 1.3295 and mean distance to of 0.1943. Most PSO runs succeed while only 6 runs converge to one of the local minima and are trapped there within the given maximum number of function evaluations. The DE runs unanimously achieve the global minimum. Similar to the results on the Griewank function, SCE-UA shows the fastest BFV decrease rate; BFVs in the successful PSO runs drop faster than those in DE runs, where as in the failed PSO runs, BFV drops even slower than in DE runs.
The results from the 100-D experiments ( Fig. 1(d)) show the problems more clearly. All the SCE-UA runs quickly stop at some points that are still away from the global minimum. The majority of PSO runs succeed in converging to the solution with nine runs are trapped to a local minimum. The DE algorithm exhibit its robustness and discover the global minimum without  exception. The BFV decreasing speeds of individual algorithms express the similar patterns as in the 30-D experiments. To understand the algorithms' different behaviors, we investigated the results further. The questions posed were as follows.
• Where do all the SCE-UA runs stop at?
• What impede the SCE-UA algorithm from converging to the global minimum? • Why DE is so robust that it succeed in every scenario?

A. Stagnation of the SCE-UA Algorithm
As described earlier, the SCE-UA algorithm employs the Nelder-Mead simplex scheme to move the offspring along the function's steepest descent direction. Ideally, if the function is continuous and smooth, the scheme will eventually drive the simplex's vertices converge to a stationary point. However, it has been reported that even for lower-dimensional problems, Nelder-Mead simplexes can sometimes stagnate at non-stationary points, a phenomenon named "stagnation" [22]. Our tests using the CF1 function reveal that incidents of stagnation increase when the function dimensionality increases. To illustrate where the SCE-UA runs stop, we examine the function gradients (numerically estimated with ) at the final points of SCE-UA runs in both 30-D and 100-D cases. We find that all the final points are non-stationary ( ). Fig. 2 shows the histograms of gradient norms at the final points: all the points possess significant gradients.
To identify if these final points are located inside the attractive region of the global minimum, we further examine the geometric relationship between the normalized negative gradient and the normalized direction vector from the final point to the global minimum for each final point. Given the fact that the CF1 function over the attractive region of the global minimum is a weighted sphere function, at any point in this region the negative gradient vector should point towards the global minimum. As illustrated in Fig. 3, for 30-D runs, the corresponding components of these two normalized vectors at all the final points are highly correlated. This indicates that these points are already close to the global minimum with negative gradients pointing towards it. For 100-D runs, the final points are still located inside the attractive region but the correlations are not as high as in the 30-D  cases because these final points are relatively farther away from the global minimum.
A key question here is: what make the SCE-UA algorithm lose its capability to fully converge? A possible reason is that the particles which are randomly selected from a complex to form a simplex have already lost some properties necessary for achieving the global optimum. We hypothesized that after generations of evolution the population might have degenerated to a subspace of the feasible space. In order to test this hypothesis, we need to examine the geometric structure of the population in a way which illustrates the faults of the particle collection. For this, we used the principal components analysis.

B. Principal Components Analysis (PCA)
Principal Components Analysis (PCA) is a multivariate analysis tool that transforms a given dataset to a new orthogonal independent coordinate system so that the first coordinate (called the first principal component PC ) has the largest variance of projections from the dataset; the second coordinate has the second largest variance and so on. In certain cases, some lower-rank PCs will have negligible variances, which means the dataset having "dimensionality reduction". In our case, the population's particles are transformed to the PC coordinate system : where matrix has PCs ( : ) as its columns, is the covariance matrix of the particle population in the original coordinate system, and eigenvalue is the data variance along . If we have , the vector component constant for every . This indicates that the dataset is located within a subspace spanned by ( ) independent orthogonal vectors (PCs) denoted as . By applying the PCA procedure to a population and checking the PC's relative variance we can identify if the dimensionality reduction has happened in the population. If it has happened, we need to be aware of two issues: 1) Given the global optimum location of the benchmark function , it is easy to detect if is inside the subspace. If is outside of the subspace, the particle population may lose the ability to converge to or may even converge to a non-stationary point. Sketchy plots in Fig. 4 provide visualization of reduced dimensionality of particle population in 2-D and 3-D scenarios and the consequences. 2) If vectors and , then too. It means that theoretically, offspring generation mechanism based on linear operations on parents in degenerated population cannot restore the lost dimensions. In high-dimensional optimization problems, one can not ensure that particle population is able to maintain it dimensionality throughout the whole search. Actually, we discovered that in each of the SCE-UA failed runs and most of PSO problematic . From top to bottom, the row panels are for the results after the first iteration, after one-third of the total iterations, after two-thirds of the total iterations, and after the last iteration, respectively. runs, the population degenerated: all particles spanned a subspace with a reduced dimensionality and the benchmark function's global minimum point was excluded from the subspace. Detailed results are illustrated in the following section.

C. PCA Results of the Three Algorithms
In the experiments, we applied the PCA procedure to the particle populations every time a generation of evolution (iteration) is completed. Due to the characteristics of the PSO algorithm, the best historical position of each particle is also included in the PSO population. Fig. 5 illustrates how the relative variances on PCs varies from the early population to the final one for median runs of three algorithms on the 100-D CF1 function (results from other 100-D runs and the 30-D runs are similar). Since all algorithms start with a randomly sampled initial population, after the first iteration, the populations of all three algorithms still maintain comparable variances for each individual PC (the top panels). However, with continuing evolution, the PCA results for the three algorithms diverge.
For SCE-UA (the panels on the left column), the population finally generates so much that only one PC has dominant amount of variance, 99.5% of the total, after 74 iterations (about 4.5 function evaluations). In fact, after one third of the total iterations, only four PCs have significant variances. This means that the population is confined in a 4-D subspace of the 100-D search space. Because the SCE-UA algorithm generates the candidate offspring along the steepest descent direction -a difference vector between a simplex's worst vertex and the centroid of the rest vertices, if all the vertex particles are within the same subspace, the new offspring will be confined in the same subspace. The population continues reducing its dimensionality until quits at a 1-D subspace and the final point is not even a stationary point.
For PSO (the panels in the middle column), the degeneration of particle population is less severe than in SCE-UA. After twothird of the total iterations (2120 iterations with about 8.6 function evaluations), the last 28 PCs out of all 100 PCs have only 1% of the total variance, which means that the capability of searching over directions of these 28 PCs is greatly reduced. In other words, the algorithm lost the capability of searching through the full 100-D parameter space. For the same reason as in the case of SCE-UA, it is difficult for the PSO algorithm to restore the lost dimensions in the following iterations. For this PSO run, it is lucky that the population degeneration happens because the particles have reached the attractive region of the global minimum and, hence, the subspace contains the global minimum point. However, in all the failed PSO runs, the population degeneration occurs due to the attractive region of a local minimum and the subspace spanned by the population excludes the global minimum. Consequently, the particles lose their capability to approach the global minimum and finally are trapped to the local minimum.
For DE (the panels on the right column), throughout all of the 2500 iterations, every PC remains comparable variance. This means that the searches are always conducted in the 100-D full search space, which contributes to the robust performances of DE in the experiments. In fact, if the degeneration had happened, the way of DE to generate the offspring would not be able to get it recovered too, like in the cases of the other two algorithms.

D. Geometrical Study of the Experiment Results
It is also of great interest to show how the relationship between the global minimum and the subspace spanned by the population changes during the course of evolution for all three algorithms. To do this, we must define some numerical thresholds. The first one is how to define a dimension being reduced numerically. Since the dimensionality of the experiment is 100, for random generated populations, the expected percentage of total variance projected on each dimension is 1%. Therefore, if one dimension has variance projection less than of its expectation (0.01% of the total variance), it is numerically defined as reduced. Second, it is important to define if the global minimum is within a subspace? In this experiment, if the distance  from the global minimum to the subspace, which is also a hyperplane, is less than , is treated as being on the super plane, namely within the subspace.
If we put results of the 30 runs in parallel, after each iteration, we can determine in how many runs (out of the 30 runs) the global minimum is remaining in the subspace spanned by the particle population. Illustrated in Fig. 6, in all SCE-UA runs, the global minimum is excluded from the population space after a few early iterations. In contrast, for all DE runs, the global minimum always remains in the subspace of the population which is actually because the population does not degenerate, as revealed by Fig. 5. From Fig. 5, it is clear that PSO runs all have population degeneration occurring. However, Fig. 7 shows that if the population degeneration is caused by the attractive region of the global minimum ( ), is still contained in the subspace of the population. However, if the degeneration is caused by the attractive region of the local minimum, is very likely to be excluded from the population subspace and when it happens, the search is doomed to fail.

E. Interpretation
Population degeneration cannot be addressed by the population diversity measures, that are proposed by many recent studies in evolutionary algorithms. In general, these reported measures fall into two categories: 1) Population diversity in the objective space [23]- [26]; and 2) Population diversity in the parameter space [27]- [30]. Furthermore, the measures in the parameter space are based on the particle-dimension-distance to quantify population diversity. These distance-based measures cannot identify population degeneration. For instance, in another study [21], we demonstrate that one of the most popular diversity measures cannot reflect the population degeneration that leads the PSO algorithm to fail on some complex test functions.
The difference in the severity of population degeneration between the three algorithms is closely related to the offspring generating mechanisms used by the algorithms. To keep the population spanning the full parameter space through the optimization, offspring should be generated in "all directions" during evolution. Here, "all directions" mean linearly independent directions in an -D search space.
In the SCE-UA algorithm, offspring are generated (using the Nelder-Mead simplex scheme) along the steepest descent direction of a benchmark function. The steepest descent direction represents the most promising searching direction, which makes the search effective. Meanwhile the population converges and possesses orientations in accordance to the function features. The complex shuffling scheme and mutation procedure alter the search directions but are not strong enough to prevent the convergence trend in the high-dimensional space. Therefore, the SCE-UA search during the evolution is in "very selective directions," not in all directions.
The scheme employed by PSO generates the offspring in a direction with three components: the direction of the last displacement, the direction toward the best position of the population, and the direction toward the particle's best historical position. The first and last components help maintaining the spatial diversity since each particle's path is independent at the beginning. However, if the similarity among particles' paths emerges, for example the whole population moves from one region to another more promising region during evolution, the spatial diversity of search direction will also be compromised.
In contrast, the DE algorithm generates offspring along directions that are defined by two randomly selected particles and diverted by the hybridization process. These mechanisms tend to generate offspring in all directions and greatly reduce the possibility of population degeneration but cost inefficient searches.

IV. REMEDY FOR POPULATION DEGENERATION
Because efficiency is essential in high-dimensional optimization, the parsimonious slope-approximation processes of generating offspring, such as the simplex scheme in the SCE-UA method, are preferable in developing evolutionary optimization algorithms for high-dimensional applications. However, the potential risk from population degeneration must be properly controlled. In addition to its capability of discovering population degeneration, PCA also can help remedy the adverse effects of population degeneration. PCA can identify all of the reduced PCs, on which the population variance projections are trivial. Then, extra offspring can be generated along these PCs complementing the offspring generated routinely. In this manner, the offspring is generated in all directions and can span the full parameter space.
As a demonstration, we modified the SCE-UA algorithm [31], [32], by applying PCA to the population at the end of each iteration and generating additional offspring along all reduced PCs. This modified SCE-UA algorithm not only performs properly on the 100-D CF1 function with all runs successfully converging to the global minimum, but also demonstrates its efficiency and effectiveness on a suite of very complex compositional functions. As a general tool, PCA can also be applied to remedy population degeneration associated with PSO. The above experiments show that population degeneration also occurs in the PSO runs on 100-D CF1, but not causing stagnation of the swarm. However, as reported by Chu et al. [33], population degeneration triggered by one of the most popular bound-handling schemes, absorbing scheme, does drive the swarm to stagnate at the boundary of the searching space. The absorbing scheme is necessary in exploring the global optima that are close to the boundary in many practical problems. In fact, adding a PCA scheme to PSO, in the same manner as how we apply PCA to SCE-UA, can prevent PSO from stagnation caused by population degeneration when using absorbing bound-handling scheme. This can be demonstrated through a test using the composition function,CF4, in Liang et al. [19]. The CF4 function (Fig. 8) constructs a dominant attractive region which converges to a local minimum (at the center of the search space), whereas the global minimum and other better local minima hide in a narrow area close to the boundary.
For comparison, we run PSO 30 times on CF4 with each of the four settings: 1) with reflecting bound-handling: relocating an outside offspring particle inside at the symmetric position by the boundary, 2) with random bound-handling: randomly relocating the outside particles within the search domain, 3) with absorbing bound-handling: setting the outside offspring particles onto the boundary, and 4) with absorbing bound-handling and PCA scheme. Results show that PSO is consistently trapped by the local minimum at the center of the search space ( Fig. 9(a)-(c)) with settings 1-3. Only with PCA as in setting 4, PSO can escape the trapping by this local minimum and obtain much better final function values.

V. PRACTICAL APPLICATION
With remedy of population degeneration, evolutionary algorithms are capable of solving high-dimensional and complex practical problems. As an example, we present some results from our recent study of improving the parameter estimation and calibration of the highly nonlinear hydrologic models used for flood forecasting [34]. In specific, the SACramento Soil-Moisture Accounting Model (SAC-SMA), which is the major component of the U.S. National Weather Service (NWS) River Forecast System and is currently serving as the operational model for flood and river flow forecasting over the United States, was used to examine the SP-UCI method, a SCE-UA variant integrating PCA. The SAC-SMA model has 13 parameters which need to be obtained through parameter estimation.
Simulating the rainfall-runoff process, the SAC-SMA model represents a complex system involving physical components (different soil layers) and water movement (infiltration, percolation). Since many parts of this system are underground and unobservable, it utilizes a series of conceptual water storages to approximate the soil moisture conditions and to control the production of streamflow (Fig. 10). Therefore, the skill of this model relies on how well the model parameters are calibrated.
To demonstrate effectiveness of SP-UCI, we applied it to the calibration of SAC-SMA over the Leaf River basin located in the State of Mississippi. This watershed has an area of 1944 (Fig. 11) and is an intensively studied watershed, and therefore has abundant and easily accessible hydrological data. We obtained 11 years (January 1, 1953 to December 31, 1963) of observation time series from the Hydrologic Research Laboratory at NWS. The data set includes mean areal precipitation (mm/6 h), potential evapotranspiration (mm/day), and streamflow (m3/s). The mean annual precipitation for the entire period is 1323.7 mm and the mean runoff is 27.14 m3/s. For comparison, both SP-UCI and SCE-UA were applied 50 independent times, with objective function defined as the daily root-mean-square error (DRMS) of the simulated runoff against the observation. Final DRMS values are presented in Fig. 12, along with results reported by some previous studies [35], [36]. It is evident that SP-UCI elevates SAC-SMA to a record high level in terms of its ability to predict the daily runoff of the basin. SP-UCI not only retrieves the optimal parameter values    responsible for more accurate runoff simulation, but also provides consistent (narrow ranges) model parameter distributions, which leads to correct understanding of the model's behavior and the watershed's hydrologic features [34].

VI. SUMMARY AND DISCUSSIONS
In this study, we compare three evolutionary algorithms using two typical benchmark functions, each of which is tested in 30-D and 100-D cases and each test included 30 runs. From the experiments we conclude the following.
1) All the failed global optimizations are unanimously in company with population degeneration in which the population degenerated into a subspace embedded inside the search space and the global minimum is outside of the subspace. This population degeneration is in general irrecoverable by the algorithms themselves.
2) The possibility of the occurrence of population degeneration is closely related to the algorithm's mechanism used to generate offspring. The SCE-UA algorithm has the most effective and efficient scheme to discover better offspring among the three algorithms, but it is most vulnerable to population degeneration. The DE algorithm shows robustness in global optimizations by employing diverse search during the evolution, which, in turn, decreases its inefficiency. 3) DE showed its robustness in this study, but the low efficiency diminishes its application to high-dimensional optimization. On the other hand, in all the succeeded runs, SCE-UA consistently exhibits remarkable efficiency compared with the other two algorithms which suggests that it will have great potential for high-dimensional optimization if the population degeneration can be controlled, as reported in [31], [32]. When using evolutionary algorithms to solve real-world problems, the location of the global optimum (if it exists) is generally unknown. As the searching dimensionality increases, the response surface of the test function becomes much more complicated. Particle population gets less capable to explore the high-dimensional landscape and more susceptible to degeneration. Therefore, the results of this study recommend: 1) An algorithm should maintain the dimensionality of the space spanned by particle population during evolution, because even if only one dimension is reduced, the succeeding search will possibly be restricted to the subspace missing the opportunity to achieve the global minimum.
2) The PCA procedure is a powerful tool of not only discerning population degeneration but also identifying reduced PCs. Hence it can be used to remedy population degeneration and diverse the search directions. 3) As a practical instance of the No Free Lunch Theorems [37], efficiency and robustness are often uncongenial. To be able to work on a wide range of real-world problems, an algorithm should enable users to control the balance between efficiency and robustness. How to realize this through designing an efficient and flexible mechanisms of generating offspring will be one of the foci for our future study.