Detecting key sentences for automatic assistance in peer reviewing research articles in educational sciences

The evaluation of scientific performance is gaining importance in all research disciplines. The basic process of the evaluation is peer reviewing, which is a time-consuming activity. In order to facilitate and speed up peer reviewing processes we have developed an exploratory NLP system in the field of educational sciences. The system highlights key sentences, which are supposed to reflect the most important threads of the article The highlighted sentences offer guidance on the content-level while structural elements -- the title, abstract, keywords, section headings -- give an orientation about the design of the argumentation in the article. The system is implemented using a discourse analysis module called concept matching applied on top of the Xerox Incremental Parser, a rule-based dependency parser. The first results are promising and indicate the directions for the future development of the system.

Introduction
With the increase of centrally allocated research funding, the growing number of conferences, workshops and journals, the evaluation of scientific articles has become a central problem of the scientific community (see for example Whitley and Gläser, 2007). The evaluation of articles consists in peer reviewing, i.e. peers' reading, understanding and commenting the articles. The peer reviewing process is a matter of extensive research (e.g. Bornmann 2003, Lu 2005 discussing its reliability and evaluation methods. Peer reviewing is a very time-consuming assignment, and Natural Language Processing (NLP) technologies might provide tools that could shorten the time that peer reviewers take to process the articles.
Within the 7 th framework EU project, European Educational Research Quality Indicators (http://www.eerqi.eu), we have set up this goal, and are developing a tool for providing assistance to peer reviewers in educational sciences. We do not know of any other work with this perspective.
Our approach consists in highlighting key sentences in the articles that can be regarded as the logical backbone of the article. Our tool does not evaluate, but aims at focusing the evaluator's attention on the parts of the texts that are relevant as a basis for his/her judgment. Nor does this tool check if the texts conform to some formal norms of scientific writing.
We regard highlighting key sentences as a complement to the processing guidance that the structural layout of the articles provides. The structural layout of scientific articles -title, abstract, keywords, section headings -guide the reader in processing the logical, argumentative and content-wise development of the article at different levels: The title is the brief indication of the topic, the keywords yield the conceptual context of the topic, the abstract provides a concise summary of the problems and results, and the section headings guide the reader step by step in the development of the article. Besides these waymarkers, the highlighted key sentences are meant to be an intermediary representation of content development between the title, the keywords, the abstract and the section headings on the one hand and the whole article on the other hand.
Since we define key sentences as those sentences that sum up the main messages of the articles, and since peer reviewing consists in judging the scientific value of the main messages, we assume that highlighting key sentences both helps understanding and provides evidence for the peer reviewer's evaluation. By highlighting we intend to add a relevant and coherent dimension of the representation of the flow of the article, which is otherwise hidden, and which the reader has to discover in order to understand the article.
Highlighting is carried out using the Xerox Incremental Parser (XIP), a rule-based dependency parser (Ait-Mokhtar et al., 2002).
We will first provide a brief review of related work. This is followed by the description of the role of structural layout in educational research articles, which we wish to complement by highlighting sentences. In the subsequent sections we define the attributes of key sentences that serve as a basis for their detection and describe the natural language processing system. In the succeeding section we present our first tests for validating our approach, and finally we draw some conclusions and indicate the directions in which we plan to carry on this work.

Related work
Our work is in line with the growing amount of research in documentation sciences and natural language processing that takes into account the argumentative structure of research articles in tasks such as information retrieval, information extraction, navigation within documents and summarization.
In the domain of information retrieval as far back as the beginning of the 1990's Liddy (1991) claimed that additional functions for search instruments could benefit from including the discourse-level context of the retrieved search terms in the interpretation of the results. Liddy stressed the "semantic roles" of concepts in a document as opposed to the simple occurrence of search terms. Oddy et al. (1992) proceed in this line of research and state that discourse-level structures in research texts could be useful to support retrieval for the user because they represent structural qualities recognized by the reader independent of the topic of the research. Both concentrate on the analysis of abstracts of research articles and propose a system to combine topical with structural information in the retrieval process. Kando (1997) also emphasizes the importance of the discourse-level context of search terms in the retrieved documents. The allocation of retrieved passages to functional units and thus the possibility to gain information about article structures provides a valuable opportunity to improve the user's assessment of the retrieved documents. A similar method of annotating text passages according to their function in the text is conducted by Mizuta et al. (2006) with the objective of categorizing articles in different document genres. Teufel and Moens (2002) base automatic summarization on extracting sentences annotated with respect to their discourse function in the text. Lisacek et al (2005) detect sentences in biomedical articles that describe substantially new research based on analyzing discourse functions.
Another line of research to exploit the argumentative structure for navigation and information extraction is inspired by the semantic web. Instead of automatically discovering argument structures in texts, the approach aims at creating conceptually motivated processing editors in which the users insert content according to its argumentative function. (see for example Uren et al., 2007, Couto andMinel, 2007.)

The structure of educational research articles
Research articles in the educational sciences tend to display a very heterogeneous structure, like articles in many other fields in social sciences and humanities. While the thematic contents of the articles are structured according to the requirements of the topic, frequent occurrences of a unifying structure are introductory and concluding chapters. However, where these chapters appear they do not display uniform headings (cf. Fiedler, 1991:98). Likewise Ruiying and Allison (2004) show, for example, that the structure of research articles in linguistics is does not conform to a common model, and section headings in many cases do not refer to the function of the chapter but to the thematic contents. Brett (1994) and Holmes (1997) observe basic structural features in the articles in political sciences and sociology. They state, however, that the section headings are usually not standardized. In contrast to the heterogeneity of the structure and section headings of research articles in social sciences and humanities those in the hard sciences show a relatively uniform structure, and often follow the well-known pattern of Introduction -Methods -Results -Discussion, which renders their reading easier.
The structural heterogeneity of social science and humanities research articles, and particularly those within educational sciences, derives from the coverage of a wide range of research problems and the consequential variation the methods applied. This discipline includes theoretically embedded discussions as well as empirical studies or material for school praxis. These differences in the referenced subjects are reflected in the way the research articles are organized and presented. Montesi and Owen (2008:151) notice a high grade of liberty granted by the educational sciences journals for the presentation of submitted papers. They also describe a clear distinction between qualitative and quantitative approaches in research articles, the latter displaying a closer connection in structural aspects to the exact sciences than the former.
In the framework of this study we compared the structural properties of fifteen articles from three journals: the British Journal of Educational Studies (BJES), the Educational Psychology Review (EPR) and the International Journal of Educational Research (IJER). These are educational research journals covering a wide variety of topics from educational psychology to school instruction. We have made the following observations: a) Some section headings follow the functional structuring of natural science articles, some do not. About half of the articles contain an 'Introduction' and/or a 'Conclusion', one third has a 'Methods' section and 26% of the articles has a section entitled 'Results', 'Findings' or 'Conclusion'. Thus a basis for a functionally orientated article structure can be perceived in the first and last chapters of most of the articles. Nearly 60% of the section headings, however, are oriented towards aspects of the content of the articles and show no predefined form. b) All of the articles are preceded by an abstract and eleven of them have keywords assigned to them. The keywords play an important role in our highlighting approach, since they are supposed to convey the basis for topical relevance. The number of keywords assigned per article is between two and nine. While some keywords are applied only a few times in the article, others are used 60 or even over 100 times. In some cases the keywords are very common words ('teachers', 'education') and they are used frequently throughout the text. In these cases the highlighted sentences are supposed to indicate relevant, terminological uses of those common, non-specialised words. In other cases the keywords are rare, but they are terms used in reduced contexts, for example, terminological expressions related to the field of research. Those are very useful for a quick overview over the research topic. Keywords appearing very rarely or not at all often belong to a more general level of terminology.
From an information extraction point of view the importance of the terms in the thread of the article is known to be related to their places of occurrence: in the title, the abstract, the section headings or even in the titles of the bibliography terms have more significance than in the rest of the article. This property of terms is used in search options in digital libraries. An appearance of the query term in the introduction or conclusion could also be a hint for the term being relevant for the scientific context or the results of the study whereas terms referring to the methodology or rather non-specific terms do not convey much information about the central contents of the text. c) The abstract is supposed to sum up the most important aspects of a research article. The articles analyzed show that in general the sentences in the abstract correspond to assertions made throughout the articles in most of the different sections. In a few cases most sentences of the abstract were also taken up in the introductory or concluding part of the article with a summarizing function. In this section we have shown that owing to the large number of research fields in educational sciences there is a high variety in the structural design and organisation of the contents of educational science research articles. In contrast to research literature in the natural sciences, the understanding of educational sciences articles is not promoted by predefined structuring of the contents. Additionally, a terminological vagueness sometimes stands in the way of using keywords as reliable content indicators. In our approach we therefore aim at a representation of article contents independent of the structural properties of the articles.

The detection of key sentences
In defining the characteristic features of key sentences that serve as a basis for their detection we rely on the kinds of judgments peer review evaluations are supposed to make (Bridges 2008). 1 We have summed up these judgments as follows: the relevance of the topic, the clarity of the problem statement, the coherence of the argumentation and the well-foundedness of the conclusions. These criteria of judgment are often presented as questions in the evaluation forms that peer reviewers are asked to fill in. Based on these evaluation criteria we define key sentences as sentences that describe research problems, purposes and conclusions related to the topic of the articles as indicated by the keywords.
The key sentences receive two types of labels in our system: SUMMARY -the sentences that convey either the goal or the conclusion -or PROBLEM -the sentences that mention research problems. Some sentences get both labels. Labeling is carried out by rules, which rely on the conceptual definition of SUMMARY and PROBLEM sentences as we show below.
In order to explain the conceptual definition we present a series of examples. The following SUMMARY and PROBLEM sentences are the first and last three key sentences detected in the same article (Barrow, 2008). In the first series of examples the keywords are underlined: Beginning: (1) PROBLEM: The most challenging questions concern whether the body provides an alternative route to knowledge, if so of what.
(2) PROBLEM_SUMMARY I do not question this belief, but in this paper I shall try to differentiate between and evaluate a number of quite distinct claims about the importance of the body in relation to schooling in general and education in particular. (3) PROBLEM: However, to assume, as some philosophers would, that acceptance of that premise concludes the debate on the question of education and the body, by implicitly claiming that education has nothing to do with the body per se, would be absurd. End: (4) SUMMARY: Do I therefore conclude, as rationalist philosophers of education are generally supposed to conclude, that education has nothing to do with the body?
(5) PROBLEM: Second, while most of the claims made about the body and knowledge are variously opaque, suspect, or clearly wrong, it remains true that to be fully aware of or to fully understand an art form such as ballet, you need to engage in it. (6) PROBLEM: More generally, let us attempt to articulate more straightforward arguments for the inclusion of sports and other forms of bodily activity in the school curriculum than obscure and unconvincing claims to the effect that they are necessary, sufficient or even directly relevant to welldeveloped and well-rounded educational understanding.
It is apparent from these sentences that approaching the task by providing a normalized factual extraction related to the keywords as in traditional information extraction would be both very problematic -even in an intellectual (as opposed to automatic) way -and may also be useless in the case of an article whose discipline is not related to describing facts, but rather to arguing about concepts. On the other hand, the human reader clearly seizes that these sentences do describe problems, aims and conclusions related to the underlined keywords. 2 In the next step we define the characteristic features of SUMMARY and PROBLEM sentences as being conveyed independently of the factual propositions.
The features of the key sentences are assigned by applying the concept-matching framework described in the following series of examples. This framework had previously been successfully used in revealing argumentative functions of research articles in a text-mining application of biomedical abstracts (Lisacek et al., 2005) and in citation-type analysis (Sándor et al., 2006). (Besides processing scientific articles, concept matching has also been used in risk detection in Sándor, 2009.) The features of key sentences are determined by the argumentative expressions in the sentences, which in some way comment on the core factual propositions. In the next series of examples we have underlined these argumentative expressions in the same set of sentences: Beginning: (1) PROBLEM: The most challenging questions concern whether the body provides an alternative route to knowledge, if so of what.
(2) PROBLEM_SUMMARY I do not question this belief, but in this paper I shall try to differentiate between and evaluate a number of quite distinct claims about the importance of the body in relation to schooling in general and education in particular. (3) PROBLEM: However to assume, as some philosophers would, that acceptance of that premise concludes the debate on the question of education and the body, by implicitly claiming that education has nothing to do with the body per se, would be absurd. End: (4) SUMMARY: Do I therefore conclude, as rationalist philosophers of education are generally supposed to conclude, that education has nothing to do with the body? (5) PROBLEM: Second, while most of the claims made about the body and knowledge are variously opaque, suspect, or clearly wrong, it remains true that to be fully aware of or to fully understand an art form such as ballet, you need to engage in it. (6) PROBLEM: More generally, let us attempt to articulate more straightforward arguments for the inclusion of sports and other forms of bodily activity in the school curriculum than obscure and unconvincing claims to the effect that they are necessary, sufficient or even directly relevant to welldeveloped and well-rounded educational understanding.
The detection is based on the words underlined. The system recognizes them since they belong to a database of previously compiled sets of words. The sets correspond to more or less loosely understood semantic fields that have been found to be relevant in scholarly argumentation in the previous applications of the conceptmatching framework. The compilation of the lists has been entirely manual. Starting from a small number of seed words we incrementally extend the list over subsequent analyses and testing. Having worked out a first concept-matching system, its modification for a new scholarly domain takes some weeks provided that a sufficiently large corpus is available. We are carrying out experiments for automatic enrichment with the help of Wordnet, but the results have not been satisfactory up to this point. However, since the semantic fields concerned contain a relatively well-identifiable vocabulary within the genre of scholarly writing, most of these words can be obtained from textbooks on academic writing.
In the concept-matching framework these sets of words and expressions are called constituent concepts. In previous applications nine constituent concepts have been identified for labeling argumentative sentences (Sándor, 2007). Out of these we use five here: MENTAL, IDEA, PUB-LICATION, DEICTIC, CONTRAST.
In the present system we have used all the words that have been compiled for labeling argumentative functions of biomedical research abstracts, and we have added a few others after having studied some educational research articles. Augmenting the list of words in the constituent concepts undoubtedly increases the coverage of the system, although we have found that the words already compiled yield fairly large coverage.
In terms of the constituent concepts we define PROBLEMs as CONTRASTed IDEAs or CON- It is apparent that the words that represent the constituent concepts in these sentential skeletons constitute purely argumentative expressions and are void of any factual proposition.
However, not all sentences containing these words convey the target concepts. Consider for example the following sentence from a research article (Meinberg and Stern, 2003.): (7) Only 1.8% of the claims were attributed to wrong-site surgery, but 84% of the claims due to wrong-site surgery resulted in payment to the plaintiff compared ...
In order to differentiate between relevant and irrelevant ways of combining the constituent concepts in a sentence our framework proposes syntactic criteria: sentences are labeled in case the constituent concepts are in syntactic dependency relationship with each other. The kind of syntactic relationship is not specified.
The restriction of syntactic dependencies is especially relevant in the case when the constituent concepts are function words (like e.g. not) or have a general sense (like e.g. work). At this point we have not measured the impact of this restriction on recall and precision. We have built the concept-matching grammar for labeling argumentation types on top of a general-purpose dependency grammar developed in XIP. In the concept-matching grammar we define the argumentative expressions as those syntactic dependencies where both words belong to the particular concepts that constitute the target concepts as defined above. The only exceptions to the syntactic constraint are sentential adverbs (like "however"), for which the XIP grammar does not extract any syntactic dependencies. The highlighted sentences are those that contain the labeled argumentative expressions.

First tests
Our exploratory system is based on several consecutive hypotheses, the validity of which should be tested incrementally.
The first hypothesis is that the key sentences relevant for peer reviewing are those that describe the problems, aims and results in the articles, and that these sentences contain the keywords provided with the articles. The second hypothesis is that these sentences can be detected using the concept-matching grammar. Finally the third hypothesis is that highlighting these sentences can save peer reviewers' time evaluating articles.
Owing to the complexity and relative vagueness of the task, we have not been able to set up either a formal or a statistically significant evaluation up to now. For this article we have carried out an initial internal test 3 towards the validation of the first two hypotheses.
In a test corpus of five articles from the three educational research journals mentioned in Section 3 (BJES, EPR, IJES) we checked if the sentences highlighted by the system convey relevant information in the argumentative development of the paper and if we find other key sentences that are not highlighted. Next we analyzed the causes of silence and noise in order to evaluate our basic assumptions. Table 1 summarizes the results of the test over the five articles in terms of recall and precision of the key sentences, and also indicates the percentage of key sentences out of all the sentences in the articles. Recall is defined as the number of correct sentences highlighted divided by the total number of sentences that we considered to be key sentences. Precision is defined as the number of correct sentences highlighted divided by the total number of sentences highlighted. Table 2 shows if the missing sentences identified as key sentences by the evaluator contain keywords or not. It also displays the number of missing sentences in each article by type of error. Table 3 shows the number of false positive sentences according to the types of the causes of the error.

Article
Recall Precision Key sentences  Table 3. Causes of noise: 1.The sentence matches the rules but is not important enough; 2.Incorrect analysis by the parser 3.Inadequacy of the framework for the task We can observe significant differences according to the journals with respect to both hypotheses that we have tested. The three journals deal with rather different research topics ranging from theoretical discussions to empirical studies of students´ behavior. According to our results the important passages of these articles are characterized by different attributes: while in empirical studies more or less definite results can be presented, theoretical discussions rest more on a discursive level offering less clear conclusions to be identified as SUMMARY or PROBLEM sentences. This is reflected on the one hand in the differences in recall and precision among the journals and on the other hand in the differences in the number of sentences missing due to errortype 3 in Table 2.
In the EPR and in the IJER we found more key sentences that are neither SUMMARY nor PROBLEM sentences according to our definition than in the BJES. Most of these sentences convey definitions related to the key concept. Thus our first hypothesis seems to hold more for empirical studies than for theoretical ones. In order to increase the coverage of key sentences the system should be completed so that it also detects definitions, especially in the case of theoretical articles.
As for the presence of keywords in the key sentences, our results show that this is a relevant condition, however not necessary since a number of key sentences identified do not contain keywords. Further study is needed to identify the characteristic features of key sentences without keywords. We have carried out an additional test to see if the correct key sentences cover all the keywords in the list. In the five articles we have only found one keyword that was not present in any of the key sentences, but this word appeared only once in the whole article. The fact that relatively few sentences are detected in the articles and that in these sentences all the keywords are covered supports the hypothesis that the key sentences do play an important role in the thread of the article.
Among the errors leading to both silence and noise we have found a number of cases where the concept-matching framework in its present form is not convenient for the task of detecting key sentences that satisfy the conditions or filtering erroneous sentences. The reason for this in both cases is that the unit of concept-matching is the sentence, whereas in these cases a single sentence does not provide enough context for identifying or for specifying the target concepts respectively. Since the number of errors due to this reason is not very high we do not consider that these results invalidate the second hypothesis. The number of such false positives is quite significant, however, which might be disturbing for the user of the system. This kind of error could be overcome by enlarging the scope of conceptmatching beyond the sentence. In this way we could filter out these false positives.
In a significant number of cases noise is not due to an error in the system but to the fact that the sentence is not important enough with respect to the development of the whole article. Whether this kind of noise is a significant disturbing factor for the user is to be tested in subsequent evaluation by users.
Finally, we have found few errors due to bugs in the grammar, which indicates that the recognition of SUMMARY and PROBLEM sentences is relatively reliable. These results also contribute to suggesting that the second hypothesis seems to hold.

Conclusion
In this article we have presented an exploratory system for highlighting key sentences containing keywords in order to support peer review. The selected sentences are supposed to help peer reviewers of articles in educational sciences to focus their attention on some relevant textual evidence for formulating their judgments. We have argued that even if the structural characteristics-the abstract, the keywords and the section headings-guide the reader in following the development of the article, content-oriented highlighting of key sentences might enhance the quick understanding of the core contents.
Although the subjects of educational science research articles display very heterogeneous structures and contents, the system could identify a number of sentences containing the main statements of the articles. Text-inherent developments not accompanied by structural signs like the outcomes of empirical studies or the contents of a theoretical discussion about abstract terms could be identified using automatic text analysis, which can possibly save intellectual effort of scientists. The time-consuming task of reviewing a growing number of research publications, hardly manageable when studying each submitted manuscript thoroughly, could thus be facilitated and supported and less threatened to be replaced by wholly automatic metric systems when time constraints become more severe.
The method we have developed is implemented in XIP, a rule-based dependency parser. It uses pre-existing lexical resources and applies the concept-matching framework.
The results of our first tests suggest that two of our three initial hypotheses are partially valid. According to our first hypothesis the key sentences relevant for peer reviewing are those that describe the problems, aims and results in the articles. We have found that sentences conveying definitions, especially in theoretical articles, should also be highlighted as key sentences. The second hypothesis is that these sentences can be detected using the concept-matching grammar. We have found in the majority of cases that this hypothesis is valid, however, enlarging the unit of concept-matching to multiple sentences would improve the performance.
Based on this result we are undertaking a user evaluation to measure the time needed to peer review these articles with and without highlighting. We are also planning to extend the system in the two directions suggested by the test results.
Besides providing assistance to peer reviewers the system presented here could be used in other applications, which we would like to explore in future projects. The possibilities include improving search functionalities in digital libraries, displaying electronic documents by linking keywords to key sentences and discourse-based navigation.


extfieldsofstudy:
Computer Science
Engineering

text:
A Syllable-based Name Transliteration System

This paper describes the name entity transliteration system which we conducted for the "NEWS2009 Machine Transliteration Shared Task" (Li et al 2009). We get the transliteration in Chinese from an English name with three steps. We syllabify the English name into a sequence of syllables by some rules, and generate the most probable Pinyin sequence with the mapping model of English syllables to Pinyin (EP model), then we convert the Pinyin sequence into a Chinese character sequence with the mapping model of Pinyin to characters (PC model). And we get the final Chinese character sequence. Our system achieves an ACC of 0.498 and a Mean F-score of 0.786 in the official evaluation result.

Introduction
The main subject of shared task is to translate English names (source language) to Chinese names (target language). Firstly, we fix some rules and syllabify the English names into a sequence of syllables by these rules, in the meanwhile, we convert the Chinese names into Pinyin sequence. Secondly, we construct an EP model referring to the method of phrase-based machine translation. In the next, we construct a 2-gram language model on characters and a chart reflecting the using frequency of each character with the same pronunciation, both of which constitute the PC model converting Pinyin sequence into character sequence. When a Pinyin is mapped to several different characters, we can use them to make a choice. In our experiment, we adopt the corpus provided by NEWS2009 (Li et al 2004) and the LDC Name Entity Lists 1 respectively to conduct two EP models, while the NEWS2009 corpus for the PC model. The experiment indicates that the larger a training corpus is, the more precise the transliteration is.

Transliteration System Description
Knowing from the definition of transliteration, we must make the translating result maintain the original pronunciation in source language. We found that most English letters and letter compositions" pronunciation are relatively fixed, so we can take a syllabification on an English name, therefore the syllable sequence can represent its pronunciation. In Chinese, Pinyin is used to represent a character"s pronunciation. Based on these analyses, we transliterate the English syllable sequence into a Pinyin sequence, and then translate the Pinyin sequence into characters. We suppose that the probability of a transliteration from an English name to a Chinese name is denoted by P(Ch|En), the probability of a translation from an English syllable sequence to a Pinyin sequence is denoted by P(Py|En), and the probability of a translation from a Pinyin sequence to a characters is denoted by P(Ch|Py), then we can get the formula: The character sequence in candidates having the max value of P(Ch|En) is the best transliteration (Wan and Verspoor, 1998).

Syllabification of English Names
English letters can be divided into vowel letters (VL) and consonant letters (CL). Usually, in a word, a phonetic syllable can be constructed in a structure of CL+VL, CL+VL+CL, CL+VL+NL. To adapt for Chinese phonetic rule, we divide the continuous CLs into independent CLs(IC) and divide structure of CL+VL+CL into CL+VL and an IC. Take "Ronald" as an example, it can be syllabified into "Ro/na/l/d", "Ro" is CL+VL, "nal" is CL+VL+CL, and is divided into CL+VL and IC. "d" is an independent CL (KUO et al. 2007). Of course there are some English names more complex to be syllabified, so we define seven rules for syllabification (JIANG et al. 2006): (1) Define English letter set as O, vowel set as V={a, e, i, o, u}, consonant set as C=O-V.
(2) Replace all "x" in a name with "ks" before syllabification because it"s always pronounced as "ks". ( 3) The continuous VLs should be regarded as one VL.
(4) There are some special cases in rule (3), the continuous VLs like "oi", "io", "eo" are pronounced as two syllables, so they should be cut into two parts, so "Wilhoit" will be syllabifyd into "wi/l/ho/i/t".
(5) The continuous CLs should be cut into several independent CLs. If the last one is followed by some VLs, they will make up a syllable.
(6) Some continuous CLs are pronounced as a syllable, such as "ck", "th", these CLs will not be syllabifyd and be regarded as a single CL, "Jack" is syllabifyd into "Ja/ck".
(7) There are some other composition with the structure of VL+CL, such as "ing", "er", "an" and so on. If it"s a consonant behind these compositions in the name, we can syllabify it at the end of the composition, while if it"s a vowel behind them, we should double write the last letter and syllabify the word between the two same letters.
After syllabicating English names, we convert corresponding Chinese names into Pinyin. There are a few characters with multiple pronunciations in the training data, we find them out and ensure its pronunciation in a name manually.
We record all of these syllables got from the training data set, if we meet a syllable out of vocabulary when transliterating an English name, we will find a similar one with the shortest editdistance in the vocabulary to replace that.

Mapping Model of English Syllables to Pinyins
The EP model consists of a phrase-based machine translation model with a trigram language model. Given an English name f, we want to find its Chinese translation e, which maximize the conditional probability  | ( e f lex  phrase penalty (always exp(1) = 2.718)  word penalty (target name length)  target language model, trigram The first five features can be seen as a whole phrase translation cost and used as one during decoding. In general, the translation process can be described as follows: (1). Segmenting input English syllable se- We use SRI toolkit to train our trigram language model with modified Kneser-Ney smoothing (Chen and Goodman 1998). In the standard experiment, we use training data set provided by NEWS2009 (Li et al 2004) to train this language model, in the nonstandard one, we use that and the LDC Name Entity Lists to train this language model.

Mapping Model of Pinyins to Chinese Characters
Since the Chinese characters used in people names are limited, most of the conversions from Pinyin to character are fixed. But some Pinyins still have several corresponding characters, and we should make a choice among these characters.
To solve this problem, we conduct a PC model consisting a frequency chart which reflects the using frequency of each character at different positions in the names and a 2-gram language model with absolute discounting smoothing. A Chinese name is represented as C 1 C 2 … C n ，C i (1≤i≤n) is a Chinese character. C 1 is at the first position, we call it FW; C 2 …C n-1 are in the middle, we call them MW; C n is at the last position, we call it LW. Usually, each character has different frequencies at these three positions. In the training data set of NEWS2009, Pinyin "luo" can be mapped to three characters: "罗", "洛", and "萝", each of them has different frequencies at different positions. From this table, we can see that at FW and MW position, "罗" is more probable to be chosen than the others, but sometimes "洛" or "萝" is the correct one. In order to ensure characters with lower frequency like "洛" and "萝" can be chosen firstly in a certain context, we conduct a 2-gram language model. If a Pinyin can be mapped to several characters, the condition probability (P(Ch i |py)) indicating that how possible a character should be chosen is determined by the weighted average of its position frequency (P(Ch i |pos)) and its probability in the 2-gram language model (P(Ch i |Ch i-1 )). P(Ch i |py) = a*P(Ch i |pos)+(1-a)*P(Ch i |Ch i-1 ) (4) 0 < a < 1. In our experiments, we set a = 0.1.

Experiments and Results
We carried out two experiments. The difference between them is the training data for EP model. The standard experiment adopts corpus provided by NEWS2009, while the nonstandard one adopts LDC Name Entity Lists.

Corpora
Name Num LDC2005T34 572213 NEWS09_train_ench_31961 31961 Considering that an English name may be translated to different Chinese names in different corpora, so we established a unique PC model with the training data set provided by NEWS2009 to avoid the model"s deviation caused by different corpora.
The experimenting data is the development data set provided by NEWS2009 (Li et al 2004), testing script is also provided by NEWS2009.
First, we take a syllabification on testing names. Then we use the EP model to generate 5best Pinyin sequences and their probabilities. For each Pinyin sequence, the PC model gives 3best character sequences and their probabilities. In the end, we sort the results by probabilities of character sequences and corresponding Pinyin sequences.
The evaluation results are shown below. It"s easy to see that nonstandard test is better than standard one on each metric. A larger corpus does make a contribution to a more accurate model.

Metrics
For the official evaluation, we make two tests on the testing data set provided by NEWS2009 (Li et al 2004

Conclusion
We construct a name entity transliteration system based on syllable. This system syllabifies English names by rules, then translates the syllables to Pinyin and Chinese characters by statistics model. We found that a larger corpus may improve the transliteration. Besides, we can do something else to improve that. We need to fix more complex rules for syllabification. If we can get the name user"s gender from some features of the name itself, then translate the male and female names on different Chinese character sets, the results may be more precise.


Ranking Help Message Candidates Based on Robust Grammar Verification Results and Utterance History in Spoken Dialogue Systems

We address an issue of out-of-grammar (OOG) utterances in spoken dialogue systems by generating help messages for novice users. Help generation for OOG utterances is a challenging problem because language understanding (LU) results based on automatic speech recognition (ASR) results for such utterances are always erroneous as important words are often misrecognized or missed from such utterances. We first develop grammar verification for OOG utterances on the basis of a Weighted Finite-State Transducer (WFST). It robustly identifies a grammar rule that a user intends to utter, even when some important words are missed from the ASR result. We then adopt a ranking algorithm, RankBoost, whose features include the grammar verification results and the utterance history representing the user's experience.

Introduction
Studies on spoken dialogue systems have recently proceeded from in-laboratory systems to ones deployed to the open public (Raux et al., 2006;Komatani et al., 2007;Nisimura et al., 2005). Accordingly, opportunities are increasing as general citizens use the systems. This situation means that novice users directly access the systems with no instruction, which is quite different from inlaboratory experiments where some instructions can be given. In such cases, users often experience situations where their utterances are not correctly recognized. This is because of a gap between the actual system and a user's mental model, that is, a user's expectation of the system. Actually, a user's utterance often cannot be interpreted by the system because of the system's limited grammar for language understanding (LU). We call such an unacceptable utterance an "outof-grammar (OOG) utterance." When users' utterances are OOG, they cannot change their utterances into acceptable ones unless they are informed what expressions are acceptable by the system.
We aim to manage the problem of OOG utterances by providing help messages showing an example of acceptable language expressions when a user utterance is not acceptable. We prepare help messages corresponding to each grammar rule the system has. We therefore assume that appropriate help messages can be provided if a user's intention, i.e., a grammar rule the user originally intends to use by his utterance, is correctly estimated.
Issues for generating such help messages include: 1. Estimating a grammar rule corresponding to user intention even from OOG utterances, and 2. Complementing missing information in a single utterance.
The first issue focuses on the fact that automatic speech recognition (ASR) results, used as main input data, are erroneous for OOG utterances. Estimating a grammar rule that the user intends to use becomes accordingly difficult especially when content words, which correspond to database entries such as place names and their attributes, are not correctly recognized. That is, any type of ASR error in any position should be taken into consideration in ASR results of OOG utterances. On the other hand, the second issue focuses on the fact that an ASR result for an OOG utterance does not necessarily contain sufficient information to estimate the user intention. This is because of ASR errors or that users may omit some elements from their utterances because they are in context. We develop a grammar verification method based on Weighted Finite-State Transducer (WFST) as a solution to the first issue. The grammar verification method robustly estimates which a grammar rule is intended to use by a user's utterance. The WFST is automatically generated to represent an ASR result in which any possibility of error is taken into consideration. We furthermore adopt a boosting algorithm, Rank-Boost (Freund et al., 2003), to put help messages in order of probability to address the second issue. Because it is difficult even for human annotators to uniquely determine which help message should be provided for each case, we adopt an algorithm that can be used for training on several data examples that have a certain order of priority. We also incorporate features representing the user's utterance history for preventing message repetition.

Related Work
Various studies have been done on generating help messages in spoken dialogue systems. Gorrell et al. (2002) trained a decision tree to classify causes of errors for OOG utterances. Hockey et al. (2003) also classified OOG utterances into the three categories of endpointing errors, unknown vocabulary, and subcategorization mistakes, by comparing two kinds of ASR results. This was called Targeted Help and provided a user with immediate feedback tailored to what the user said. Lee et al. (2007) also addressed error recovery by generating help messages in an example-based dialog modeling framework. These studies, however, determined what help messages should be provided mainly on the basis of literal ASR results. Therefore, help messages would be degraded by ASR results in which a lot of information was missing, especially for OOG utterances. The same help messages would be repeated when the same ASR results were obtained.
An example dialogue enabled by our method, especially the part of the method described in Section 4, is shown in Figure 1. Here, user utterances are transcriptions, and utterance numbers [] denotes grammar rules.
Figure 1: Example dialogue enabled by our method start with "S" and "U" denote system and user utterances, respectively. In this example, ASR results for the user utterances (U1 and U2) do not contain sufficient information because the utterances are short and contain out-of-vocabulary words. These two results are similar, and accordingly, the help message after U2 provided by methods like Targeted Help (Gorrell et al., 2002;Hockey et al., 2003) is the same as Utterance S1 because they are only based on ASR results. Our method can provide different help messages as Utterance S2 after ranking candidates by considering the utterance history and grammar verification results. Because the candidates are arranged in the order of probability, the most appropriate help message can be provided in fewer attempts. This ranking method for help message candidates is also useful in multimodal interfaces with speech input. Help messages are necessary when ASR is used as its input modality, and such messages were actually implemented in City Browser (Gruenstein and Seneff, 2007), for example. This system lists template-based help messages on the screen by using ASR results and internal states of the system. The order of help messages is important, especially in portable devices with a small screen, on which the number of help messages dis-played at one time is limited, as Hartmann and Schreiber (2008) pointed out. Even in cases where sufficiently large screens are available, too many help messages without any order will distract the user's attention and thus spoil its usability.

Grammar Verification based on WFST
We estimate a user's intention even from OOG utterances as a grammar rule that the user intends to use by his utterance. We call this estimation grammar verification. This process is applied to ASR outputs based on a statistical language model (LM) in this paper. We use two transducers: a finite-state transducer (FST) representing the task grammar, and weighted FST (WFST) representing an ASR result and its confidence score. Hereafter, we denote these two as "grammar FST" and "input WFST" and depict examples in Figure 2.
A strong point of our method is that it takes all three types of ASR error into consideration. The input WFST is designed to represent all cases where any word in an ASR result is an inserted or substituted error, or any word is deleted. Its weight is designed to reflect confidence scores of ASR results. By composing this WFST and the grammar FST, we can obtain all possible sequences and their accumulated weights when arbitrary sequences represented by the input WFST are input into the grammar FST. The optimal results having the maximum accumulated weight consist of the LU result and the grammar rule that is the nearest to the ASR result. The result can be obtained even when any element in it is misrecognized or absent from the ASR result.
An LU result is a set of concepts that consist of slots and their values corresponding to database entries the system handles. For example, an LU result "month=2, day=22" consists of two concepts, such as the value of slot month is 2, and the value of slot day is 22.

Design of input WFST and grammar FST
In input WFSTs and grammar FSTs, each arc representing state transitions has a label in the form of "a:b/c" denoting its input symbol, output symbol, and weight, in this order. Input symbol ε means a state transition without any input symbol, that is, an epsilon transition. Output symbol ε means no output in the state transition. For example, a state transition "please:ε/1.0" is executed when an input symbol is "please," no output symbol is gen-erated, and 1.0 is added to the accumulated weight. Weights are omitted in the grammar FST because no weight is given in it.
An input WFST is automatically constructed from an ASR result. Sequential state transitions are assigned to each word in the ASR result, and each of them is paralleled by filler transitions, as shown in Figure 2 where the ASR result was "Every Monday please" for example. Filler transitions such as INS, DEL, and SUB are assigned to each state for representing every kind of error such as insertion, deletion, and substitution errors. All input symbols in the input WFST are ε, by which the WFST represents all possible sequences containing arbitrary errors. For example, the input WFST in Figure 2 represents all possible sequences such as "Every Monday please," "Every Monday F," "F Monday F," and so on. Here, every word can be replaced by the symbol F that represents an insertion or substitution error. Moreover, the error symbol DEL can be inserted into its output symbol sequence at any position, which corresponds to deletion errors in ASR results. Each weight per state transition is summed up and then the optimal result is determined. The weights will be explained in Section 3.2.
A grammar FST is generated from a task grammar, which is written by a system developer for each task. It determines whether an input sequence conforms to the task grammar. We also assign filler transitions to each state for handling each type of error of ASR results considered in the input WFST. A filler transition, either of INS, DEL, or SUB, is added to each state in the FST except for states within keyphrases, which are explicitly indicated by a system developer. In the example shown in Figure 2, "SUB $ Monday date-repeat=Mon please" is output for an input sequence "SUB Monday please". Here, date-repeat=Mon denotes an LU result, and $ is a symbol for marking words corresponding to a concept.

Weights assigned to input WFST
We defined two kinds of weights: 1. Rewards for accepted words (w acc ), and 2. Penalties for each kind of error (w sub , w del , w ins ).
An accumulated weight for a single utterance is defined as the sum of these weights as shown be- Here, E accepted denotes a set of accepted words corresponding to elements of each grammar rule, and E error denotes a set of words that are not accepted and that have either error symbol. Note that the weights are not given beforehand but are calculated and given to the input WFST in runtime according to each ASR result. A weight for an accepted word e asr is defined by using its confidence score CM (e asr ) (Lee et al., 2004) and its word length. A word length in mora is denoted as l(·), which is normalized by that of the longest word in the vocabulary.
w acc = CM (e asr )l(e asr ) This weight w acc gives preference to sequences containing longer words with higher confidence scores.
Weights for each type of error have negative values because they are penalties: where l(e) is the average word length in the vocabulary and e gram is a grammar element i.e., either a word or a class. A deletion error is a case when a grammar element does not correspond to any word in the ASR result. A substitution error is a case when an element is replaced by another word in the ASR result. An insertion error is a case when no grammar element corresponds to the ASR result. Every weight is defined as an average of a word length of a grammar element and the corresponding one in the ASR result multiplied by its confidence score. When correspondences cannot be defined in insertion and deletion errors, l(e) is used instead. In the case when e gram is a class in the grammar, the average word length in that class is used as l(e gram ).

Example of calculating the weights
We show how a weight is calculated by using the example in Figure 3. In this example, the user utterance was "Tell me a liaison of Koetsu-ji (a temple name)." The word "liaison" was not in the system vocabulary. The ASR result accordingly contained errors for that part; the result was "Tell me all Sakyo-ward Koetsu-ji." Weights are calculated for each grammar rule the system has. This example shows calculations for two grammar rules: [get info] accepting "Tell me item name of temple name ," and [search ward] accepting "Tell me facility name of ward name ." Here, [] and denote a grammar rule and a class in grammars. Two alignment results are also shown for grammar [get info] in this example. Weights are calculated for any alignment as shown here, and the alignment result with the largest weight is selected. In this example, weight +0.16 for the grammar [get info] was the largest.
We consequently obtained the result that grammar rule [get info] had the highest score for this OOG utterance and its accumulated weight was  Figure 3: Example of calculating weights in our grammar verification +0.16. The result also indicated each type of error as a result of the alignment: item name was substituted by "Sakyo-ward", "of" in the grammar [get info] was deleted, and "all" in the ASR result was inserted.

Ranking Help Message Candidates by Integrating Dialogue Context
We furthermore develop a method to rank help message candidates per grammar rule by integrating the grammar verification result and the user's utterance history. This complements information that is often absent from utterances or misrecognized in ASR and prevents that the same help messages are repeated. An outline of the method is depicted in Figure 4.

Features used in Ranking
Features used in our methods are listed in Table  1. These features are calculated for each help message candidate corresponding to each grammar rule. Features H1 to H5 represent how reliable a grammar verification result is. Feature H1 is a grammar verification score, that is, the resulting accumulated weight described in Section 3. Feature H2 is calculated by normalizing H1 by the total score of all grammar rules. This represents how reliable the grammar verification result is relatively compared to others. Features H3 to H5 represent how partially the user utterance matches with the grammar rule. Features H6 and H7 correspond to a dialogue context. Feature H6 reflects the case in which users tend to repeat similar utterances when their utterances were not understood by the system. Feature H7 represents whether and how the user knows about the language expression of the grammar rule. This feature corresponds to the known degree we previously proposed (Fukubayashi et  H1: accumulated weight of GV (GV score) H2: GV score normalized by the total GV score of other instances H3: ratio of # of accepted words in GV result to # of all words H4: maximum number of successively accepted words in GV result H5: number of accepted slots in GV result H6: how before the grammar rule was selected as GV result (in # of utterances) H7: maximum GV score for the grammar rule until then H8: whether it belongs to the "command" class H9: whether it belongs to the "query" class H10: whether it belongs to the "request-info" class H11-H17: products of H8 and each of H1 to H7 H18-H24: products of H9 and each of H1 to H7 H25-H31: products of H10 and each of H1 to H7 GV: grammar verification al., 2006), and prevents a help message the user already knows from being provided repeatedly.
Features H8 to H10 represent properties of utterances corresponding to the grammar rules, which are categorized into three classes such as "command," "query," and "request-info." In the sightseeing task, the numbers of grammar rules for the three classes were 8, 4, and 11, respectively. More specifically, utterances in either "query" or "request-info" class tend to appear successively because they are used when users try and compare several query conditions; on the other hand, utterances in "command" class tend to appear independently of the context. Features H11 to H31 are the products of features H8, H9, and H10 and each feature from H1 to H7. These were defined to consider combinations of properties of utterances represented by H8, H9, and H10 and their reliability represented by H1 to H7, because RankBoost  Figure 4: Outline of our ranking method for help message candidates does not consider them.

Ranking Algorithm
We adopt RankBoost (Freund et al., 2003), a boosting algorithm based on machine learning, to rank help message candidates. This algorithm can be used for training on several data examples having a certain order of priority. This attribute fits for the problem in this paper; it is difficult even for human annotators to determine the unique appropriate help message to be provided. Target instances x of the algorithm are help message candidates corresponding to grammar rules in this paper.
RankBoost trains a score function H(x) and arranges instances x in the order. Here, H(x ′ ) < H(x ′′ ) means x ′′ is ranked higher than x ′ . This score function is defined as a linear combination of weak rankers giving partial information regarding the order: where T , h t (), and α t denote the number of boosting iterations, a weak ranker, and its associated weight, respectively. The weak ranker h t is defined by comparing the value of a feature f i of an instance x with a threshold θ. That is, where q def ∈ {0, 1}. Here, f i (x) denotes the value of the i-th feature of instance x, and ⊥ denotes that no value is given in f i (x).

Target Data
Data were collected by 30 subjects in total by using a multi-domain spoken dialogue system that handles five domains such as restaurant, hotel, sightseeing, bus, and weather (Komatani et al., 2008). The data consisted of 180 dialogues and 11,733 utterances. Data from five subjects were used to determine the number of boosting iterations and to improve LMs for ASR. We used utterances in the restaurant, hotel, and sightseeing domains because the remaining two, bus and weather, did not have many grammar rules. We then extracted OOG utterances on the basis of the grammar verification results to evaluate the performance of our method for such utterances. We regarded an utterance whose accumulated weight was negative as OOG. As a result, 1,349 OOG utterances by 25 subjects were used for evaluation, hereafter. These consisted of 363 utterances in the restaurant domain, 563 in the hotel domain, and 423 in the sightseeing domain. These data were collected under the following conditions: subjects were given no instructions on concrete language expressions the system accepts. System responses were made only by speech, and no screen for displaying outputs was used. Subjects were given six scenarios describing tasks to be completed.
We used Julius 1 that is a statistical-LM-based ASR engine. We constructed class 3-gram LMs for ASR by using 10,000 sentences generated from the task grammars and the 600 utterances collected by the five subjects. The vocabulary sizes for the restaurant, hotel, and sightseeing domains were 3,456, 2,625, and 3,593, and ASR accuracies for them were 45.8%, 57.1%, and 43.5%, respectively. These ASR accuracies were not very high because the target utterances were all OOG. A set of possible thresholds in the weak rankers described in Section 4.2 consisted of all feature values that appeared in the training data. The numbers of boosting iterations were determined on the basis of accuracies for the data by the five sub- jects. The numbers were 400, 100, and 500 for the restaurant, hotel, and sightseeing domains.

Evaluation Criterion
We manually gave five help messages corresponding to grammar rules as reference labels per utterance in the order of having a strong relation to the utterance. The numbers of candidate help messages were 28, 27, and 23 for the restaurant, hotel and sightseeing domains, respectively. We evaluated our ranking method as the accuracy where at least one of the reference labels was contained in its top N candidates. This corresponds to a probability where at least one appropriate help message was contained in a list of N candidates. The accuracy was calculated by 5-fold cross validation. In the baseline method we set, help messages were provided only by using the grammar verification scores.

Results
Results in the sightseeing domain are plotted in Figure 5. We can see that our method outperformed the baseline in the accuracies for all N values. All these differences were statistically significant (p < 0.05) by the McNemar test. The accuracies were also better in the other two domains for all N values, and the average differences for the three domains were 11.7 points for N =1, 9.7 points for N =2, and 6.7 points for N =3. The differences were large especially for small N values. This result indicates that we can successfully reduce the number of help messages when providing several ones for users. The improvements were derived from the features we incorporated such as the estimated user knowledge in addition to grammar verification results. The baseline method was only based on grammar verification results for single utterances, which contained insufficient information because OOG utterances were often misrecognized or misunderstood. We also investigated dominant features by calculating the sum of absolute values of final weight α for each feature in RankBoost. Five dominant features based on the sums are shown in Table  2. These five features include a feature obtained from grammar verification result (H2), a feature about the user's utterance history (H6), a feature representing estimated user knowledge (H7), and features representing properties of the utterances. The most dominant feature was H7, which appeared twice in this table. This was because user utterances were not likely to be OOG utterances again after the user had already known an expression corresponding to the grammar rule, which can be detected when user utterances for it were correctly accepted, that is, its grammar verification score was high. The second dominant feature was H2, which showed that grammar verification results worked effectively.

Conclusion
We addressed an issue of OOG utterances in spoken dialogue systems by generating help messages. To manage situations when a user utterance could not be accepted, we robustly estimated a user's intention as a grammar rule that the user intends to use. We furthermore integrated various information as well as the grammar verification results for complementing missing information in single utterances, and then ranked help message candidates corresponding to the grammar rules for efficiently providing them.
Our future work includes the following. The evaluation in this paper was taken place only on the basis of utterances collected beforehand. Providing help messages itself should be evaluated by another experiment through dialogues. Furthermore, we assumed that language expressions of help messages to show an example language expression were fixed. We also need to investigate what kind of expression is more helpful to novice users.


extfieldsofstudy:
Computer Science
Physics

text:
Robustness of"cut and splice"genetic algorithms in the structural optimization of atomic clusters

We return to the geometry optimization problem of Lennard-Jones clusters to analyze the performance dependence of"cut and splice"genetic algorithms (GAs) on the employed population size. We generally find that admixing twinning mutation moves leads to an improved robustness of the algorithm efficiency with respect to this a priori unknown technical parameter. The resulting very stable performance of the corresponding mutation+mating GA implementation over a wide range of population sizes is an important feature when addressing unknown systems with computationally involved first-principles based GA sampling.

INTRODUCTION
Small clusters of less than a hundred atoms are an increasingly studied class of materials exhibiting unique optical, magnetic and chemical properties [1]. Due to the intricate relationship between the geometric and electronic structure of clusters in this size range a reliable determination of the ground-state and energetically lowlying metastable geometric structures is a prerequisite. Two crucial aspects of the corresponding global geometry optimization problem are the reliable sampling of the high-dimensional potential-energy surface (PES) to identify the low-lying minima, and the accuracy with which this PES is provided [2]. When aiming at a quantitative, material-specific theory the high computational cost to evaluate the PES with first-principles electronic structure methods adds another practical aspect, namely that the sampling strategies be as efficient as possible. High efficiency is in this respect often solely equated with a minimum number of PES evaluations required until the relevant structures are found. This neglects that sophisticated sampling algorithms are usually based on a manifold of technical parameters which sensitively determine this efficiency and which can mostly only be optimized through either a detailed knowledge of the PES topography or repeated sampling runs with different settings. Again, for numerically undemanding model PES the latter is not an issue, but instead done routinely. However, for costly first-principles sampling of unknown systems, where every single energy and force evaluation may take say several hours of CPU time, this is clearly not possible and it thus becomes equally important that the efficiency is robust, namely that the algorithm exhibits a similar performance as long as the chosen parameter settings are in a reasonable range.

THEORY
With this motivation we return to an algorithm that is widely used for geometry optimization problems, the genetic algorithm (GA) [3,4], and analyze its robustness with respect to a central technical parameter, the population size. In the context of structure optimization GAs explore the PES landscape through a sequence of trial structures that each time correspond to local PES minima. Such trial structures are generated by randomly modifying a given cluster structure in a so-called move and an ensuing local geometry optimization. The central idea of GAs is thereby to run several such trial structure sequences in parallel, exploiting this population to also create new trial structures by mating the different current configurations and thereby potentially combining information from disparate parts of the high-dimensional PES. Replacing old members of the population with newly obtained more stable candidates, the generation update procedure is repeated until the global optimized and other low-lying structures are found. A plethora of subtle modifications of this basic principle has been suggested, including parameter settings and move types tailored for specific applications (e.g. [4,5,6,7,8,9]). With the goal of a robust general-purpose methodology with a minimum number of technical parameters we only return to these ramifications below, and focus instead here on a classic move type originally suggested by Deaven and Ho [5,6]. Such "cut and splice" moves are generically applicable and by their very construction enable huge jumps in configuration space, thus promising a decent sampling. As the name suggests, a new trial structure is generated by suitably cutting an existing cluster geometry into two halves along an arbitrarily oriented plane and then splicing two halves together. This can either be done by recombining the two halves of the same cluster after rotation by a random angle, thus making it a so-called twinning mutation [7], or by recombining the halves of different configurations in the current population, thereby creating a mating or crossover operation.
While such mating moves appear most natural within the GA philosophy of mixing "genetic" information in the population, the beneficial effect of mutation moves in preventing premature convergence is well established [7,8,9]. This is hitherto primarily discussed with respect to an improved sampling efficiency, whereas our analysis below in fact demonstrates that it also has important bearings on the robustness of the approach.
With such move type fixed, the only algorithmic parameters left are the size of the population and the way how trial structures replace current members of the population if they are more "fit", i.e. energetically more stable. In a corresponding periodic population update a large number of new trial structures is first created by taking all possible pairings within the existing population and only doing the replacement step afterwards. Particularly for larger populations this bears the danger of creating a lot of new trial structures out of members that still have a low fitness. This can be circumvented by always allowing only a certain fraction of the most stable clusters in the population to mate, which comes at the price of adding with this fraction another unknown technical parameter with impact on the algorithm efficiency. Another alternative that gets away without this is a dynamic population update [3], which we indeed verified to be much more efficient than a periodic population update for all systems and settings discussed below. In this procedure new trial structures are still created by sequentially taking all possible pairings within the population, which then automatically includes twinning mutations in form of the self-pairings. However, in contrast to a periodic update the fitness of a new trial structure is immediately evaluated. If it is more stable than any of the two parent structures (one parent structure in case of the mutations), it directly replaces the highest energy member of the entire population, thereby quickly eliminating the least fit configurations. In the conceptual idea of a genetic algorithm genetic diversity is hereby enforced by rejecting trial structures that correspond to local PES minima that are already represented in the current population.
This leaves as the sole undetermined technical parameter of the present GA implementation the size of the population, the optimum value of which is a priori unknown for an unknown system. In order to arrive at a trend understanding of how much the algorithm efficiency depends on a judicious choice of this parameter we resort to the well-studied problem of the structural optimization of Lennard-Jones (LJ) clusters, i.e. clusters of atoms interacting with each other via the well-known LJ pair potential, where r is the interparticle distance, σ LJ is the effective particle diameter, ε LJ sets the energy scale of the short-ranged soft core repulsion, and we use reduced units σ LJ = ε LJ = 1 throughout. This simple model potential is chosen for a number of reasons: First, the global minima of LJ clusters in the targeted size range of up to 100 atoms are all well established [10,11], thus providing a well-defined criterion for the efficiency of a sampling run, namely the number of trial moves N until this global minimum is found. Second, the ease with which this model potential can be evaluated computationally allows us to average over a sufficiently large number of runs starting from different initial geometries and with different random number sequences to be able to report statistically relevant numbers N av on the efficiency for a wide range of cluster and GA population sizes. Last, not least, despite the simplicity of the LJ potential the resulting PESs for different cluster sizes range from easy to quite hard with respect to the global optimization problem [12]. This enables a systematic analysis of the algorithm performance not only over the relevant cluster size range, but also for both simple and complex PES topographies. Specifically, we therefore focus on the series of single-funnel LJ clusters with 10, 15, 20, 25, . . ., 65, and 70 atoms for the prior aspect and contrast this with an investigation of the double-funnel LJ 38 cluster for the latter. The random structures to initialize the sampling runs are created by randomly placing atoms inside a sphere of radius 5 with the constraint that the distance between any pairs of atoms is more than 0.5. The reported values for N av are then obtained by averaging over many runs starting from different random structures and random number seeds. The targeted convergence of N av within 5 percent was usually achieved after about 100 different runs, and only for the largest clusters an averaging over up to 175 runs was required. For the local geometry optimization ensuing each move we employ the FIRE algorithm [13] and consider the structure relaxed when all forces fall below 10 −3 . Correspondingly optimized cluster structures are identified as belonging to the same local PES minimum, if their relative energies differ by less than 10 −3 .

RESULTS
With equivalent results obtained for all single-funnel clusters, Fig. 1 summarizes the performance data for the selected clusters LJ 10 , LJ 45 and LJ 65 spanning the studied size range. Separately analyzed is the efficiency of the algorithm when allowing for only mutation or only mating moves, as well as for both. Intriguingly, it is primarily in the latter case that the algorithm exhibits an unusual robustness in the sense that the overall performance varies over less than a factor of two for a wide range of population sizes and for all cluster sizes studied. Recalling that the essential idea to employ a population was to potentially combine information from disparate parts of the high-dimensional PES through the mating of different cluster configurations, the large influence of the twinning mutations obtained particularly for the larger cluster sizes, e.g. LJ 65 in Fig. 1, is counterintuitive at first sight. In order to rationalize it, let us first further qualify what is meant with disparate parts. "Disparate" in this context does not exclusively refer to the PES topography, but also to the move types used. Any area of the PES is "disparate" from a current configuration, if it cannot be efficiently reached by the employed moves, and areas that are "disparate" for one move type may actually be quite "close" for another. The almost equal performance of the GA when using either only mutation or additionally mating moves for the smallest clusters like LJ 10 thus reflects that already the mutation moves alone enable quite efficient jumps everywhere on the corresponding PES of still rather limited dimensionality. In this situation there is no added value when enabling a mating of different members of the population. On the contrary, a larger population creates an increasing overhead as it takes more trial moves until the loop over all population members is completed. Especially when only enabling mutation moves, a larger population then primarily means that for a given number of trial moves every single cluster configuration is less often subject to a change and the algorithm needs overall a larger N av to more or less optimize all population members in parallel. Correspondingly and as illustrated by Fig. 1, for all cluster sizes the performance of a GA based exclusively on mutation moves decreases monotonously with population size. It is only for the larger cluster sizes that mating different population members starts to pay off, cf. Fig. 1. In the increasingly higher-dimensional PESs these moves are now apparently able to reach areas that can not be accessed that efficiently by mutations anymore. In the sense of genetic diversity this feature will be the better the larger the population. On the other hand, also here the increasing overhead argument applies, rationalizing why the performance curves for the mating-only GA in Fig. 1 start to develop a minimum at an optimum population size that gets more pronounced the larger the cluster size. From the simplistic perspective of an increasing value brought about by mating in increasingly higher-dimensional PESs, the shift of this minimum to larger optimum population sizes for the larger clusters visible in Fig. 1 is also quite intuitive. While this view furthermore rationalizes the poor performance of mating-only GA at very small population sizes, the then much higher efficiency of the GA based solely on mutations is quite surprising. Analyzing the energies of the most and least favorable population member, as well as the average energy within the population during the sampling run we can nevertheless trace it back to limitations of small-population mating-only GA in bringing the system down through the lowest part of the PES funnel. Figure 2 illustrates this for the LJ 65 cluster for both a very small population of 5, for which matingonly is much less efficient than mutation-only GA, and a larger population of 30, for which mating-only is more efficient than mutation-only GA, cf. Fig. 1. For the small population, the energy of the most stable cluster in the population decreases in both algorithm variants almost equally quickly in the initial 250 trial moves. At the same time the wider jumps in configuration space enabled by mating moves eliminate much more effectively the highest-energy members in the population and the average energy in the mating-only GA is brought down more rapidly than in the mutation-only variant. However, exactly this tendency of mating moves to induce more drastic changes to the cluster structure turns into a disadvantage in the continued sampling run, when in particular for the close-packed LJ clusters often only minor modifications to e.g. erase remaining dislocations or coordination faults are required to bring the system through the end of the PES funnel towards the global minimum. Correspondingly, Fig. 2 shows a saturation of the mating-only GA run at higher energies than the mutation-only GA, where in the latter e.g. twinning mutations with small rotational angle can efficiently induce possibly required small structural modifications. This limitation is lifted in larger populations which now contain sufficiently many and diverse configurations that also mating moves inducing smaller structural modifications occur with sufficient probability. This is reflected in Fig.  2, where the lowest-energy curves for the population of 30 decrease now similarly for both algorithm variants, and the mating-only GA ultimately results as the more efficient approach.
We therefore arrive at an interesting performance crossover between mating-only and mutation-only GA as a function of population size. For large and therewith diverse enough populations the added value brought about by mating kicks in and mating-only GA is preferred. On the contrary, if the population is too small this diversity bonus no longer applies. While still not as efficient as mating-only GA at optimum population size, mutationonly GA is then the more robust approach as it is better able to cope with the possible requirement of subtle structural modifications when already close to the optimum geometry. Most intriguingly, yet with the presented understanding also quite naturally, Fig. 1 shows that these two effects are to some degree additive in the sense that the GA implementation allowing both mutation and mating exhibits a performance that in the two extremes of very small and very large populations is virtually identical to the performance of mutation-only and mating-only GA, respectively. In the end, this leads to an efficiency that is very robust with respect to the employed population size for all cluster sizes studied and varies by less than a factor of two for the wide range of populations shown in Fig. 1.
This result largely carries over to the more complex PES topography of the double-funnel LJ 38 cluster. As shown in Fig. 3, also here the mutation-only GA is most efficient at small population sizes. That this efficiency is in this case so pronounced compared to the mating-only GA nicely corroborates the interpretation developed from the single-funnel cluster data. As discussed in detail by Wolf and Landman [7], there are a multitude of structures in the energetic neighborhood of the LJ 38 global minimum, a fcc truncated octahedron, that essentially correspond to multitwinned fcc crystallites. With the initial trial moves likely to bring the system into one of these low-energy configurations, it is particularly twinning mutation moves that can then very efficiently reach the optimum pure fcc structure. In the present GA implementation applying both mating and mutation, these twinning mutations do not occur too often in the loop over all pairings, which is why the performance of this variant in this regime is still worse than mutation-only, albeit significantly improved compared to mating-only GA. Obviously, this suggests that the actual degree to which mutation moves are admixed may be optimized for specific systems, yet what we consider the more important conclusion from our work is that whatever the percentage, mutation admixture seems to generally improve the robustness of the GA algorithm with respect to the employed population size. From the presented understanding of enabling small structural modifications we believe that this feature is in fact not restricted to the actual twinning mutations used here, but should equally hold for e.g. single or collective particle moves in which one or several atoms of the cluster are randomly displaced, as well when using more sophisticated crossover operations.

CONCLUSIONS
In conclusion, we have investigated the performance dependence of a "cut and splice" genetic algorithm on the employed population size. Focusing on the geometry optimization of both a series of single-funnel LJ clusters up to 70 atoms and the double-funnel LJ 38 cluster we generally obtain that admixing twinning mutation moves leads to an improved robustness of the algorithm. Here, improved robustness denotes an efficiency in finding the global minimum that varies less over a wide range of population sizes studied and that in particular for small populations is significantly improved compared to a matingonly GA. The latter is traced back to an enhanced possibility of small structural modifications offered by mutation moves. Especially for systems favoring close-packed structures like the LJ clusters this is essential to erase remaining dislocations or coordination faults and to bring the system through the end of the PES funnel towards the global minimum. Within this understanding we believe that this finding is not specific to LJ interactions, nor is it restricted to the "cut and splice" mutation and mating moves studied here. This suggests that is is in general recommended to admix mutation moves, not only because of their well-known beneficial effect on the sampling [7], but also to increase the robustness of the GA algorithm with respect to the a priori unknown parameter population size.
The latter feature is particularly important for firstprinciples GA sampling, and in this respect the very stable performance of the present mating+mutation GA implementation, achieved without any system-specific tuning, is very promising. To set this into perspective, one should compare the about 2000 moves required to find the ground state of the complex LJ 38 PES with any reasonable population size to the roughly equal number of moves needed by the classic basin-hopping (BH) scheme [14], when its central technical parameter, the effective temperature, is specifically optimized to the doublefunnel PES topography [15]. Latest reports indicate that more sophisticated GA [16] or BH [15] schemes (including the recently introduced minima-hopping [17]) may reduce this number by a factor ∼ 2, but at the expense of introducing a manifold of technical parameters. While not large, such a reduction would still be highly desirable in view of the high computational cost incurred by firstprinciples based sampling. Not withstanding, it would not be of much use if only achieved after excessive parameter optimization for a specific PES landscape. Consequently, we believe that further progress in this direction requires revisiting the global optimization problem from the perspective of algorithmic robustness as done in the present work.

ACKNOWLEDGMENTS
Funding within the MPG Innovation Initiative "Multiscale Materials Modeling of Condensed Matter" is grate-fully acknowledged.