Nikolaos Kolokas
email: nikolokas@iti.gr

Anastasios Drosou
email: drosou@iti.gr

Dimitrios Tzovaras
email: dimitrios.tzovaras@iti.gr

Keywords-To-Text Synthesis Using Recurrent Neural Network

Keywords: Synthesis Using Recurrent Neural Network Nikolaos Kolokas, Anastasios Drosou, Dimitrios Tzovaras deep machine learning, sequence modeling, natural language processing, text mining

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Keywords-to-text synthesis appertains to the general field of the well known Natural Language Processing (NLP). NLP regards the understanding of a human language by the computer, and also, conversely, the ability of the computer to synthesize text or speech. Examples of applications include speech recognition, machine translation, text-to-speech synthesis, Parts Of Speech (POS) tagging and text summarization [START_REF] Goodfellow | Deep Learning[END_REF]. NLP research generally started in the 1950's, but machine learning techniques for NLP were firstly employed in the 1980's, when the tasks started to be solved by statistical inference instead of the former disadvantageous handwritten rules. Even more especially, deep learning was involved very recently [START_REF] Goodfellow | Deep Learning[END_REF][START_REF] Goldberg | A Primer on Neural Network Models for Natural Language Processing[END_REF]. Most approaches are supervised, but recently semi-supervised and unsupervised approaches are investigated as well. In this paper the supervised option is preferred, because it demands less data to achieve desirable performance.

In this work the problem of keywords-to-text synthesis is addressed. Especially, our main goal is to provide a tool which, taking a keyword sequence as input, is able to produce a full text containing the keywords, or synonyms of them, in the same order. This synthesis facilitates the text composition, since it demands less typing by the user. The Recurrent Neural Network (RNN) is chosen as such a tool, since RNNs are particularly appropriate for sequence modeling problems and they have many applications related to NLP, knowledge representation, reasoning and question answering [START_REF] Goodfellow | Deep Learning[END_REF][START_REF] Sutskever | Generating Text with Recurrent Neural Networks[END_REF]. This paper concerns a supervised learning method and some full texts are used as a data set. As for the keywords, here they are defined as the least necessary words from which a unique full text can be inferred. Since such words are almost always verbs and nouns, the verbs and nouns are extracted from the texts using an available POS tagging algorithm. Finally, for the automatic synonym matching, a library containing a dictionary which includes synonyms for each of its words is used.

In this paper a relatively simple family (among those presented in [START_REF] Goodfellow | Deep Learning[END_REF][START_REF] Goldberg | A Primer on Neural Network Models for Natural Language Processing[END_REF]) of an RNN is eventually employed. It is empirically confirmed that our text synthesis goal does not demand gated RNNs [e.g. Long Short-Term Memory (LSTM), Gated Recurrent Unit (GRU)], which deal with long-term dependencies, something rather irrelevant to this problem, where for a word production the present and a few neighboring input keywords and full text predicted words obviously suffice, as also shown by the results.

The remainder of the paper is organized as follows. In section 2 related work is cited and the uniqueness of ours is briefly described. In section 3 the preprocessing of our data set before training is presented, and in section 4 our experimental results from several training approaches are shown and discussed. Finally, section 5 summarizes our work and proposes possible next steps.

Previous Work and Motivation

In this section previous work is presented, related to the two coarse phases of ours: the keywords extraction from texts and the reproduction of the texts (text synthesis) from these keywords. Considerable work on keywords extraction and text summarization is found in the bibliography, e.g. in [START_REF] Shah | Information extraction from full text scientific articles: Where are the keywords?[END_REF][START_REF] Andrade | Automatic extraction of keywords from scientific text: application to the knowledge domain of protein families[END_REF][START_REF] Hacohen-Kerner | Automatic Extraction of Keywords from Abstracts[END_REF][START_REF] Litvak | Graph-based keyword extraction for single-document summarization[END_REF][START_REF] Al-Hashemi | Text Summarization Extraction System (TSES) Using Extracted Keywords[END_REF]. The criteria of defining/selecting keywords, or even the goal, differ among references, so the methodologies are not directly linked and comparable with each other and with ours. The work of [START_REF] Shah | Information extraction from full text scientific articles: Where are the keywords?[END_REF] is somehow relevant to ours, because in that paper the keywords are considered as the nouns (as characterized by a POS tagging algorithm) that imply many other nouns in the same sentence. However, the final aim in that work is not the text synthesis from the extracted keywords, which constitute a percentage of the total word number that is too small to serve such a goal. Thus, despite our inspiration by the cited keywords extraction methodology, it needed to be modified in our work. In [START_REF] Andrade | Automatic extraction of keywords from scientific text: application to the knowledge domain of protein families[END_REF] the purpose of keyword extraction is the classification (annotation) of texts, so words are evaluated by the number of families in which they appear and their mean frequency in them. In [START_REF] Hacohen-Kerner | Automatic Extraction of Keywords from Abstracts[END_REF] keywords are defined according to their frequency and extracted from abstracts and titles. Finally, in [START_REF] Litvak | Graph-based keyword extraction for single-document summarization[END_REF][START_REF] Al-Hashemi | Text Summarization Extraction System (TSES) Using Extracted Keywords[END_REF] keywords [START_REF] Litvak | Graph-based keyword extraction for single-document summarization[END_REF] or whole key-sentences [START_REF] Al-Hashemi | Text Summarization Extraction System (TSES) Using Extracted Keywords[END_REF] are extracted from texts according to several criteria, with the purpose of summarization. Particularly, in [START_REF] Litvak | Graph-based keyword extraction for single-document summarization[END_REF] a supervised and an unsupervised approach (both graph-based) are introduced for the extraction.

References about text synthesis regard mainly text-to-speech, speech-to-text and text-to-image synthesis. Regarding keywords-to-text synthesis, there is some work found about text generators based on keywords [START_REF] Kasper | A flexible interface for linking applications to Penman's sentence generator[END_REF][START_REF] Feiner | Automating the generation of coordinated multimedia explanations[END_REF][START_REF] Bernauer | An interactive report generator for bone scan studies[END_REF], where the meaning of the keywords or a categorization of them is necessary for their appropriate mapping to the full texts. Also, in those works the input of the text generator is either too complex for manual assignment [START_REF] Kasper | A flexible interface for linking applications to Penman's sentence generator[END_REF][START_REF] Feiner | Automating the generation of coordinated multimedia explanations[END_REF] or domain-specific [START_REF] Bernauer | An interactive report generator for bone scan studies[END_REF]. In this paper the mapping model has been defined with the help of neural network (especially RNN) training, so that the manual specification of the meaning, category or part of speech of the input keywords is not necessary. In our methodology the input used for text synthesis is very simple; just a sequence of keywords, from the domain used in training, which may be any desired. So, a user may benefit from the provided tool even by assigning the input manually. Also, it is experimentally observed that our goal cannot be addressed by a standard encoder-decoder sequence-to-sequence architecture [START_REF] Goodfellow | Deep Learning[END_REF][START_REF] Goldberg | A Primer on Neural Network Models for Natural Language Processing[END_REF][START_REF] Brownlee | How to Develop an Encoder-Decoder Model for Sequenceto-Sequence Prediction in Keras[END_REF], which is too complex for our problem and not well-suited enough to it. (This is discussed more extensively in section 3.5.) Other pieces of work on RNNs (some of which regard NLP) appear in [START_REF] Goodfellow | Deep Learning[END_REF].

Preprocessing Methodology

Apparently, the first step of the experiment is the definition of the data set. It should consist of texts of similar content, for the sake of sufficient training and appropriate evaluation. A family of steak recipes is constructed according to [START_REF]allrecipes -Beef Steak Recipes[END_REF] and considered as such a data set, but any other content could have been selected. The used texts are 15, with a total length of 761 words. The first 9 of them are treated as the training set and the rest 6 as the test set. Two examples are shown below. Observe similarities and dissimilarities.

 "Mix garlic and oil in a bowl. Pour marinade into a resealable plastic bag over the steaks. Later squeeze excess air and seal bag. Afterwards marinate beef in the refrigerator for 4 hours. Preheat grill for medium-high heat and bribe grate. Then remove meat from the marinade and shake off excess. Later discard marinade and afterwards cook steaks on preheated oven to desired degree for about 8 minutes."  "In a bowl combine garlic, oil, sauce and sugar. Pour marinade into a resealable plastic bag over the beef. Later in the fridge marinate meat for 8 hours. Preheat grill for high heat and then bake steaks to desired degree for about 60 minutes." In the following, the dot and the comma are considered as separate words and all letters are treated as capitals.

In the rest of this section all preprocessing steps, included also in Figure 1, are described in detail, as executed for our recipes data set. As mentioned above, first the verbs and nouns from all texts are extracted with POS tagging [14]. Afterwards, synonyms are detected and unified using an appropriate library containing a dictionary [15], and then some of the remaining verbs/nouns are automatically selected as key-words. Later, according to the extracted keywords, the texts are (also automatically) separated into chunks. Finally, the data are reformulated in a form acceptable by the network, which is taught using the training set. Our trained model is evaluated using mainly the test set.

Detecting Verbs and Nouns with Parts Of Speech Tagging

In any of the employed texts the predicted nouns and verbs by the POS tagging algorithm (which was already available in [14]) plus the adjectives "high", "mediumhigh" and the numerical adjectives are initially treated as keywords. The participles with suffix "-ing" or "-ed" and the indefinite article "a" are prohibited from being considered as keywords, because it has been observed that they do not play a key role in a sentence. Therefore, no stemming by unifying words with the same prefix has been performed.

Unifying Synonyms

The elimination of the vocabulary to be used in the RNN not only may reduce the number of its parameters (weights), but it also decreases the size of the training set that is required for satisfactory results. Furthermore, by reducing the percentage of full text words that are considered as keywords, the mapping tool is rendered smarter, since less words suffice for the full text synthesis. Thus, only one word is attempted to be used for every group of synonyms, both in input and output/target. (The output is the prediction of the target.) The automatic identification of synonyms for the sake of training is subject to a library [15], which consists of a language dictionary providing meanings, translations, synonyms and antonyms of words. In the training scope two words are initially defined as synonyms when at least one of them is proposed by the library as one of the (up to 5) synonyms of the other one. However, this procedure leads to several wrong matches, so then the user is proposed to confirm which of the suggested pairs of words (s)he desires to be considered as synonyms (something sub-jective and dependent on the context, which is not taken into account by the library). This manual verification is practical only for a small training text corpus. Also, there are pairs of synonyms that are not identified, but this is not faced manually for training. For each finally considered group of synonyms, a representative is automatically selected to be used in training.

Other Keyword Elimination Measures

The preprocessing steps of the current and the following sections are programmed mainly from scratch, i.e. without employing some package.

For the further decrease of the number of keywords with respect to the sizes of the full texts, further elimination measures are taken for keywords. Particularly, it has been accepted that when two or more verbs or nouns always coexist in the same sentence, then only one of them implies the existence of the others. (An example is obvious in Figure 2.) So only the first one is considered as keyword. Also, when the presence of a verb/noun always implies the presence of another verb/noun, even without the reverse holding, and the pair of these two words appears at least 5 times (in order to avoid cases of random coexistences), then optionally the second word is not considered as keyword (see also the term "degree of inclusion" in [START_REF] Shah | Information extraction from full text scientific articles: Where are the keywords?[END_REF]). After this last optional measure, the non-distinct keywords constitute 31.8% of the total number of non-distinct words of the full texts. In case it is not applied, the keyword rate is 47.7%. Of course, the above implications depend on the data set. The remaining keywords are inserted into a single list (which will generate the RNN input during the data reformulation), and the extra keyword "." is introduced to separate adjacent recipes.

Segmentation of Texts

In the scope of preprocessing and training all words are replaced by their synonym group representative, and they appear in this way in the next figures.

Definition 1. A "chunk" is defined in this paper as a sequence of words (text segment) ending at a keyword and starting at the word after the previous keyword (or, if not any, at the first word).

According to this definition, a chunk may be seen as a part of a full text which is generated by a single keyword.

Fig. 2. Segmentation of a part of the first recipe shown in the beginning of the section into chunks according to the extracted keywords (colored). The noun "air" is not considered as keyword, because it always coexists with the verb "squeeze" in the same sentence. The word "excess" is an adjective in this context, but it has been mistakenly recognized as noun.

The full texts are divided into chunks. An example is depicted in Figure 2. Our goal is to teach the RNN to map each input keyword to its chunk (with the additional help of the neighboring keywords and the predicted context), so that the full texts are automatically produced by concatenating the learned chunks.

Data Reformulation

Another interesting phase is to reformulate the data so that they suit an RNN.

Fig. 3. Data reformulation corresponding to the first part of the first recipe shown in the beginning of the section. First auxiliary words are added to both the target and the first input column, so that they have the same length. (Empty words are represented as "nan".) Then, the serial numbers of the positions of the data segments defined by the chunks are appended as the second input column, and finally two other input columns are created [START_REF] Sutskever | Generating Text with Recurrent Neural Networks[END_REF][START_REF] Shah | Information extraction from full text scientific articles: Where are the keywords?[END_REF], giving information about the precedent and the upcoming keyword.

The keywords and the corresponding full texts have to serve as input and output respectively in this work. Sequence-to-sequence models with and without attention [START_REF] Goodfellow | Deep Learning[END_REF][START_REF] Brownlee | How to Develop an Encoder-Decoder Model for Sequenceto-Sequence Prediction in Keras[END_REF] were initially employed, but the result was fully unsatisfactory (worse predicted texts than the empty text, according to the measures of section 4.2). A major mistake of such a model was that it was predicting many words multiple times, although these words were related to the respective chunks. This fact indicates that the sequence-to-sequence model is improper for word-to-word mappings, maybe due to the intervention of the context variable between the input and output. Therefore, a more appropriate, tailored idea has been implemented to resolve our problem. The model family used in this paper demands the input and output data sequences to have the same size. However, the keywords of each text are apparently less than all of its words, and also the chunks do not have fixed number of words. The consideration of a chunk as an undivided entity would not be a solution, because then the fact that same words appear in different chunks would not have been taken into account. That is, the output needs to be predicted in the word and not in the chunk level. The above issues are overcome by reformulating the keyword and text sequences, according to the first of the following steps. The second step regards the appending of the previous and the next keyword to each keyword, and the third one converts the words to vectors, so that they can be inserted in the network. All these steps are also executed automatically. The effect of the first two is clear in Figure 3. 1. All training chunks are stored in groups according to their keyword, and empty words are inserted where needed such that all chunks of the same keyword have the same length, and same words are at the same position of the text segment (so that their alignment with the input is more appropriate). Then, the reformulated chunks compose the extended full texts (with the empty words inserted), which are concatenated, forming an undivided sequence, that will be called "verbal target", since it is the verbal form of the network target sequence. In the RNN input the keywords are replicated in order to fit their chunk length. In our application the texts are artificial, and thus there was the possibility to construct a training set containing all the words of the test set. Auxiliary ordinal keywords are also created, indicating the serial numbers of the positions of each chunk, so that the prediction of every word of a chunk at the correct position is facilitated. Optionally, these numbers are bonded with the keywords, forming new words [e.g. the pair (oil, 2) becomes oil2]. 2. As soon as the extended keyword list(s) resulting from the previous step has/have been constructed, two other auxiliary lists of the same length are created for the network's input, informing about the keyword of the previous and the next chunk. This step is based on our observations about the dependence between the current chunk and the neighboring keywords. Its advantage has also been inferred with trials. 3. The words are converted to vectors, so that they can be used by the network. In this step two approaches are examined and compared [START_REF] Goodfellow | Deep Learning[END_REF][START_REF] Goldberg | A Primer on Neural Network Models for Natural Language Processing[END_REF] for the input and/or target words; a. a one-hot and b. a word embedding conversion. a. In the first one, the words are converted to one-hot vectors, (i.e. vectors with all their entries equal to 0 except one, which equals 1). This is applied for every column (i.e. list) separately. Only the empty word is represented as zero vector instead of one-hot. b. In the second approach, the words are represented as vectors of floats instead of one-hot vectors, as obtained by a word embedding (word-to-vector) algorithm [START_REF] Brownlee | How to Develop Word Embeddings in Python with Gensim[END_REF]. In this way, not only the dimension of vectors may be reduced in comparison with the one-hot conversion, but also the distance of representations of all word pairs is determined by the degree of their context relevance.

For the training of the word embedding model, the chunks of the training recipes have been used (since the training set contains all the words of the test set). Another option was to use a pre-trained word embedding model. This was examined with GloVe, which is considered as the most preferred by NLP practitioners [START_REF] Brownlee | How to Develop Word Embeddings in Python with Gensim[END_REF]. As expected, the text synthesis results were remarkably worse, since the word-to-vector training was not based on the domain context. In case the keywords of the first input columns are not bonded with the serial numbers, every input word is also an output word, so word embedding may be applied both to the whole input and to the output/target. With the above reformulation steps, the sequences of the RNN input (x(t)) and target (y(t)) are created. That is, y(t) is the vector representation of the (t + 1)-th word of the verbal target sequence (assuming that t starts from 0), and x(t) is the concatenation of the representations of the (t + 1)-th words of the input sequences. Although the argument t does not really stand for time in our case, it will be mentioned as such, because the data are sequential. The examined RNN predictive models belong to the family

ypred(t) = f({x(t -i) : i ϵ I},{ypred(t -j) : j ϵ J}, ( 1
)
where I, J are finite subsets of {0,1,…}, {1,2,…} respectively. Particular assumptions have been made for the multidimensional function f [17,[START_REF] Atabay | pyrenn: A recurrent neural network toolbox for Python and Matlab[END_REF].

Recurrent Neural Network Training and Results

After the preprocessing of the data so that they suit the network architecture, training is ready to start.

Training Details

The Mean Square Error is used as cost function. It is proportional to the Sum of Square Errors, i.e.

SSE = ΣtϵTtrain[y(t) -ypred(t)] 2 , (2)
where Ttrain denotes the set of "time points" of the training set. A 2nd order iterative optimization algorithm (e.g. Levenberg-Marquardt, Broyden-Fletcher-Goldfarb-Shanno) is practical in our problem only in case of sufficient word embedding, due to its usually extreme memory cost (resulting from the Hessian approximations and the big input and output dimensions). Thus, a 1st order algorithm is employed otherwise.

Better results are achieved by setting the initial values of the model parameters to 0 than with random initialization. This is explained rather in the one-hot approach by the sparsity (big percentage of zeros) of the optimal model, which is anticipated due to the one-hot (or zero) encoding of the input and target.

Evaluation

As follows by the above, this work aims to resolve a classification problem using a regression model, so the continuous output has to be converted to a class (a word of the target vocabulary in our case). In the one-hot approach the output is converted to a one-hot vector by setting the maximum value of the output vector to 1 if the output vector's sum exceeds 0.5 (which indicates that possibly a non-empty word corresponds to that position), and to the zero vector otherwise. In the word embedding approach the output is converted to the closest vector representation of the target vocabulary. The modified output is then compared to the target for the sake of evaluation and text production.

For vocabulary diversity in predictions, each predicted word is randomly mapped to one of its synonyms or itself. For the sake of evaluation, the pairs of synonyms that have not been identified by the library have been manually defined as synonyms.

For the evaluation of the model's performance, the following measures are used for each of the training and the test set. Both aim at quantifying the quality/correctness of the predicted texts, which are compared to the ground truth (i.e. actual) ones. However, these metrics do not consider the case of multiple correct syntaxes of a sentence, so they may admit a bit worse quality than real.  Mean Word Error Rate (MWER): The widely known Word Error Rate (WER), common for NLP problems, is computed for each text (recipe) separately and the mean is taken as the evaluation measure. The WER equals the also well known Levenshtein distance between the ground truth and the predicted text divided by the number of ground truth non-empty text words.  Mistake Rate (MR): This is a simple, heuristic measure similar to WER, but it never rewards the prediction of the correct word in the false position, even if the non-empty words are predicted in the correct order. It is the number of wrong predictions (in terms of time) for all texts divided by the number of ground truth non-empty words of all texts. A mistake is considered as single when an empty word is predicted as non-empty or vice versa, and as double when a non-empty word is predicted as another non-empty word. Apparently, the empty predicted text corresponds to an error of 1, as in the WER case.

Selecting Recurrent Neural Network Mapping Model

With intuitive trial and error and after search of several shallow and deep architectures (including also LSTM and GRU [17]), there is a general conclusion that one of the best models is the linear simple RNN with input delay 0 and output (direct) delays from 1 to 5, i.e. the shallow model

ypred(t) = Ux(t) + Σ 5 j=1Vj ypred(t -j) + b, (3)
where U, Vj, b contain the weights. (The first 5 predictions are set as equal to the target values.) This intuition results from the fact that a word of a full text is dependent on the present and the neighboring keywords, as well as a few previous full text words. The use of even one hidden layer has proven to be completely helpless, since it leads to training and test errors comparable with those of the empty text. Consequently, the best architecture is found very easily. As for shallow gated RNNs, LSTM has comparable, but often slightly poorer performance, whereas GRU is even worse. Maybe LSTM would be the best if the average chunk length were higher (or, in other words, if the keyword rate were smaller). 1 the results of training the selected simple RNN of (3) [START_REF] Atabay | pyrenn: A recurrent neural network toolbox for Python and Matlab[END_REF] are summarized and compared to the best of LSTM [17] (shallow, stateful network with dropout and recurrent dropout equal to 0.01 and no feedforward activation), according to all possible approaches discussed above. In each case, one of the best numbers of iterations has been chosen. The optimization time of these executions ranges from a few seconds to a few minutes, and depends on the RNN type and dimensionality, the optimizer and the chosen number of iterations. It is worth mentioning that there are 66 distinct non-empty full text words after the unification of synonyms among the initial 73 distinct non-empty full text words. Word embedding, especially on the output/target, reduces the number of weights significantly. For example, all shallow simple RNNs have O(n 2 + nm) parameters, where m, n are the input and the output/target dimensions respectively. This would be particularly important in case that more (and more complex) texts were used, where the need to save memory and computational time would emerge. A general remark is that the results worsen as the problem requirements (in terms of keyword rate -resulting from section 3.3-and number of weights) strengthen. It can be subjectively inferred that when the keyword rate is 31.8% (which is the most useful and challenging scenario), the best choice is to apply embedding only on the out-put and not on the input, so that the first two input columns can be bonded (6th row of the table ).

Results and Discussion

Word embedding training with the skip-gram instead of Continuous-Bag-Of-Words algorithm and use of hierarchical softmax yield the best results here.

The results with a Mean WER of about 0.3 can be characterized as quite satisfactory, because the meaning of the text is almost understandable. For an illustrative example, the prediction ". Preheated oven bake meat to desired extent for about 30 minutes." of the text "Preheat oven and then bake beef to desired extent for about 30 minutes." has WER=0.29.

The variety of the keywords' order in some input sequence among recipes not only does not cause significant problem in training, but also results to an aesthetically appealing variety in the chunks order, which changes correspondingly.

Conclusion and Future Work

In this work a tailored and quite simple algorithm which, with a sequence of known keywords as input, is able to produce full text containing these keywords, or synonyms of them, in the same order, has been developed. This automatic mapping relies on an RNN model, based on some training texts, from which the keywords are automatically extracted with the help of a POS tagging algorithm and a dictionary library.

The results, which depend on the problem difficulty, are rather satisfactory, because the meaning of the predicted text is almost clear. So far it seems that the proposed methodology is applicable to any domain/vocabulary, although the used texts have to be quite similar (maybe after deliberate editing), especially if they are few. A basic limitation is that when the test set contains words neither included in the training set nor synonymous of a training word, then the word embedding may be based only on a pre-trained word-to-vector model, which is then necessary to determine the chunk length of a new keyword as that of a training neighboring one. The new words need to belong to the domain of the training texts for effective training as well.

The text synthesis work done for steak recipes is going to be repeated for a data set from another domain, containing much more distinct and non-distinct words. By increasing the amount and diversity of texts, it will be interesting to examine the necessary word embedding size to yield fairly good results. Furthermore, there is an ambition that our program will be useful for everyday applications, like news production.

Fig. 1 .

 1 Fig. 1. Architecture of our work

Table 1 .

 1 Evaluation of best RNNs with test errors. IE/OE = Input/Output Embedding (+size), ICB = Input Columns 1 & 2 bonded, SRNN = Simple RNN with direct delays of orders from 1 to 5. The percentages in the headings denote keyword rate.

	IE OE ICB MWER	MWER	MWER	MWER	MR	MR	MR	MR
		31.8%	31.8%	47.7%	47.7%	31.8%	31.8%	47.7%	47.7%
		SRNN	LSTM	SRNN	LSTM	SRNN	LSTM	SRNN	LSTM
	10 10 no	0.608	0.640	0.375	0.410	0.924	0.892	0.605	0.680
	no 10 no	0.697	0.619	0.285	0.351	1.042	0.917	0.483	0.573
	no 10 yes	0.319	0.311	0.111	0.168	0.378	0.373	0.203	0.220
	20 20 no	0.354	0.489	0.262	0.342	0.479	0.627	0.407	0.515
	no 20 no	0.378	0.501	0.233	0.325	0.484	0.651	0.400	0.494
	no 20 yes	0.239	0.273	0.106	0.163	0.265	0.295	0.186	0.195
	10 no no	0.340	0.403	0.157	0.211	0.423	0.427	0.233	0.203
	no no no	0.295	0.461	0.060	0.212	0.357	0.477	0.075	0.199
	no no yes	0.229	0.335	0.017	0.069	0.232	0.357	0.017	0.071
	In Table

Acknowledgements. This work has been partially supported by the European Commission through project Scan4Reco funded by the European Union Horizon 2020 programme under Grant Agreement No. 665091.


Nikolaos Polatidis
email: n.polatidis@brighton.ac.uk

Stelios Kapetanakis
email: s.kapetanakis@brighton.ac.uk

Elias Pimenidis
email: elias.pimenidis@uwe.ac.uk

Konstantinos Kosmidis
email: konstantinos.kosmidis@uwl.ac.uk

Reproducibility of experiments in recommender systems evaluation

Keywords: Recommender systems, Evaluation, Reproducibility, Replication

Recommender systems evaluation is usually based on predictive accuracy metrics with better scores meaning recommendations of higher quality. However, the comparison of results is becoming increasingly difficult, since there are different recommendation frameworks and different settings in the design and implementation of the experiments. Furthermore, there might be minor differences on algorithm implementation among the different frameworks. In this paper, we compare well known recommendation algorithms, using the same dataset, metrics and overall settings, the results of which point to result differences across frameworks with the exact same settings. Hence, we propose the use of standards that should be followed as guidelines to ensure the replication of experiments and the reproducibility of the results.

1

Introduction

Recommender systems are decision support systems found in online web services, mainly in e-Commerce for movies, music, videos or general item recommendation. During the last few years, research in recommender systems both in academia and in industry counts numerous publications found in the literature [START_REF] Said | Comparative recommender system evaluation[END_REF]. The popularity in recommender systems research has led to the increasingly important problem of reproducibility and replication of experiments during the evaluation of such systems. The valuation of recommendation algorithms is important for measuring the quality of the results and make objective comparisons among algorithms. A positive aspect found in the literature is the availability of papers that describe in detail their proposed recommendation algorithms, the evaluation methods, the settings and datasets used [START_REF] Jannach | Recommender systems: An introduction[END_REF][START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF][START_REF] Polatidis | A multi-level collaborative filtering method that improves recommendations[END_REF].

In the research community, there are different recommendation frameworks that can be used for the evaluation of algorithms. These include, among others, the Apache Mahout [START_REF] Owen | Mahout in Action[END_REF], LensKit [START_REF] Ekstrand | Rethinking the Recommender Research Ecosystem: Reproducibility, Openness, and LensKit[END_REF], MyMediaLite [START_REF] Gantner | MyMediaLite: A free recommender system library[END_REF] and Recommender101 [START_REF] Jannach | What recommenders recommend-an analysis of accuracy, popularity, and sales diversity effects[END_REF]. The first one has been developed by the Apache Foundation whereas the rest have been developed by researchers in academia. All these recommendation frameworks provide essentially the same portfolio of algorithms. However, substantial differences exist in the implementation of the algorithms, data management and evaluation methods and while all frameworks provide the same basic evaluation methods, differences in algorithm implementation makes it difficult to compare results across frameworks [START_REF] Said | Comparative recommender system evaluation[END_REF].

To assist towards the problem of reproducibility and replication of experimental results in recommender systems we:

• Provide a set of standards and best practices that can be used when performing experiments. • Performed different experiments using a real dataset and different recommendation libraries with the results validating our approach.

The rest of the paper is organized as follows: Section 2 provides the required background, section 3 is a comparison between recommendation libraries, real data and different settings, section 4 delivers the proposed approach and section 5 contains the conclusion and future work parts.

2

Background

In the literature, the progress of recommender systems algorithms can be measured using accuracy and classification evaluation methods. The most known and used accuracy methods are the Mean Absolute Error (MAE) and the Root Mean Square Error (RMSE), whereas the most known classification methods are Precision and Recall. State of the art works about the evaluation of recommender systems can be found in [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF] and [START_REF] Shani | Evaluating recommendation systems[END_REF]. Research papers that propose new recommendation algorithms will typically describe the experimental setup, the dataset used and the framework used and by reproducibility is meant the replication and validation of the results by third parties [START_REF] Said | Comparative recommender system evaluation[END_REF].

The four main problems that occur when evaluating recommender systems algorithms are [START_REF] Said | Comparative recommender system evaluation[END_REF][START_REF] Konstan | Toward Identification and Adoption of Best Practices in Algorithmic Recommender Systems Research[END_REF]:

1. The framework used for the generation of the recommendations and the evaluation should be mentioned and it should be publicly available. 2. The details of the algorithms should be clearly mentioned, such as the size of the neighborhood used.

3. The dataset used for the experiments, along with any possible version of it and it should be publicly available. 4. Details of how the dataset has been used. These must include training and test splits and if these have been randomly selected or if parameters have been used to select specific parts that will make the reproduction easier. Moreover, if k-folds have been used for cross-fold validation then details about the number of folds and how these have been selected should be available.

The problem of the replication of experiments and the reproducibility of the results has been an open issue in the research community with a workshop organized in 2013 [START_REF] Bellogin | Workshop on reproducibility and replication in recommender systems evaluation[END_REF]. The outcome of the joint community work identifies the key aspects of the reproducibility problem, although its future direction part is limited [START_REF] Bellogin | Report on the Workshop on Reproducibility and Replication in Recommender Systems Evaluation (RepSys)[END_REF] since future directions are only theoretical towards the need of general guidelines to produce better results [START_REF] Konstan | Toward Identification and Adoption of Best Practices in Algorithmic Recommender Systems Research[END_REF][START_REF] Bellogin | Report on the Workshop on Reproducibility and Replication in Recommender Systems Evaluation (RepSys)[END_REF][START_REF] Beel | Towards reproducibility in recommender-systems research[END_REF][START_REF] Košir | How to improve the statistical power of the 10-fold cross validation scheme in recommender systems[END_REF]. One step further from the theoretical guidelines is RiVal [START_REF] Said | RiVal -A Toolkit to Foster Reproducibility in Recommender System Evaluation[END_REF], a toolkit that provides four stages in the recommendation process, data splitting, item recommendation, candidate item generation and performance evaluation. RiVal is not an evaluation framework since it pertains to three different frameworks, these of Apache Mahout, LensKit and MyMediaLite. The toolkit provides a user interface where the user will input the data splitting, item generation and recommendation and will select which framework will be used for the evaluation. Furthermore, there are different approaches to the problem with one found in [START_REF] Del Olmo | Evaluation of recommender systems: A new approach[END_REF], where the authors propose the use of a general framework for recommender systems and evaluation metric that operates over a set of sessions. Finally, another related metric available is the modified Reciprocal Hit Rand Metric (mRHR) proposed by [START_REF] Peker | mRHR: A Modified Reciprocal Hit Rank Metric for Ranking Evaluation of Multiple Preferences in Top-N Recommender Systems[END_REF], where the use of an alternative hit rank metric is proposed. However, in this work the problem of the average reciprocal hit rank (ARHR) is only tackled in the context of the evaluation of recommender systems.

3

Comparing experimental results using different libraries

In this section we present a comparison of two recommendation libraries. Apache Mahout and Recommender 101 based on the Pearson Correlation Similarity (PCC) and Jaccard similarity measurements and the Mean Absolute Error (MAE) error rating prediction metric.

Settings

The experimental evaluation took place on an Intel i7 with 8GBs of RAM running Windows 10. The dataset used is the MovieLens 1 million [START_REF] Harper | The MovieLens Datasets[END_REF], which contains 3952 movies, 6040 users and 1,000,209 ratings, with each user having at least 20 ratings. The dataset has been split in 80% for training and 20% for testing and the percentages have been randomly selected once for each library.

Recommendation methods

For the experiments we have used PCC and Jaccard. PCC is defined in equation 1. In PCC the sum of ratings between two users is compared. Sim (a, b) is the similarity between users a and b, also r a,p is the rating of user a for product p, r b,p is the rating of user b for product p and and represent the user's average ratings. P is the set ´a r ´b r of all products. Moreover, in PCC the similarity value between users ranges from -1 to 1 and higher values represent a closer similarity between users. Additionally, Jaccard similarity which is defined in equation 2 and in this approach only the number of co-rated items is taken into consideration. In Jaccard a represents a user and b a second user. Then, Jaccard provides a similarity value between -1 and 1 by measuring the co-rated items and dividing the size of the intersection by the size of the union of the sets. Once again higher values represent better similarity.

CC a,

(1)

P b = ∈P (ra,p-r´a)(rb,p-r´b) ∑ p √ ∈P (ra,p-r´a) ∑ p 2 √ ∈P (rb,p-r´b) ∑ p 2 accard a, ( 2
) J b = |IaIb| |IaIb| 3.3

Accuracy measure

For measuring the prediction accuracy, we have used MAE which is defined in equation 3 where pi is the predicted rating and ri is the actual rating in the summation. This method is used for the computation of the deviation between the predicted ratings and the actual ratings. It should also be noted that lower values are better. MAE has been widely used in previous research for predicting the accuracy of recommender systems [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF][START_REF] Polatidis | Privacy-preserving collaborative recommendations based on random perturbations[END_REF][START_REF] Alshammari | A hybrid CBR approach for the long tail problem in recommender systems[END_REF].

AE pi i| (3) M = n 1 ∑ n i=1 | -r

Results

The following tables describe the experimental results. Table 1 presents the results using the Apache Mahout library and table 2 the results using the Recommender101 library. In both tables the values represent the rating prediction errors based on the MAE metric. It is shown in the tables that different values have been derived after using the same settings and evaluation metric for two different recommendation libraries.

Proposed approach

In recommender systems evaluation to reproduce experiments it is recommended to follow a set of guidelines [START_REF] Said | Comparative recommender system evaluation[END_REF]. However, most researchers either do not follow them or do not explain in detail the settings of their research environment. Furthermore, the guidelines may vary across researchers and the need for their standardization in a form of framework is necessary. A major challenge in recommender system evaluation is that there are many different libraries for evaluating algorithms and the possibility of having one single library or making all the current libraries following a universal or standardized approach is rather impossible. Furthermore, scientists might decide they want to develop their own library for performing the evaluations. Thus, we list a set of guidelines in 4.1 that explain the differences in evaluation libraries and why the results are different and in 4.2 we propose how to replicate studies.

Guidelines

The following elements are the ones responsible for the reproducibility of results across libraries and within the same library.

Architecture. By this we mean the architecture of the recommendation library. For example, Apache Mahout has a different architecture when compared to Recommender 101. In the first library the PearsonCorrelationSimilarity class extends an AbstractSimilarity class but it implements Pearson, whereas in the second library there is a NearestNeighbors class implementing AbstractRecommender, which includes different neighborhood-based implementations including both Pearson and Cosine.

Main recommendation algorithm.

The most widely used method for providing recommendations in e-Commerce and other online environments is Collaborative Filtering (CF) [START_REF] Polatidis | A multi-level collaborative filtering method that improves recommendations[END_REF]. In CF, a user neighborhood is created based on previous common history between users based on a similarity function such as Pearson Correlation Coefficient (PCC) or Cosine similarity. However, small alterations on how CF works exist between frameworks.

Evaluation settings. Some frameworks provide different settings whereas others do not.

For example, differences between Recommender101 and Apache Mahout include:

• Recommender101 provides options about the minimum number of ratings per user or per item whereas in Apache Mahout someone will have to manually edit the source code to do that. This parameter could lead to different results. • Recommender101 provides settings for both the minimum and maximum rating value that should be taken into consideration during the evaluation, whereas Apache Mahout does not.

Hence, it is important for each framework to provide the same settings during the evaluation process. We believe that a framework such as Recommender101 that provides more options is more suitable for research and standardization development.

A standard that defines all possible parameters for recommender system evaluation is necessary for reproducibility.

Dataset settings. This is related to the evaluation settings and is necessary for users to follow them to make reproducibility easier. The standard should provide guidelines related to the percentage of training and test set. It should be clearly mentioned which part of the dataset has been used for training and which for testing and while pure random selection makes results more reliable affects the reproducibility. Furthermore, if k-folds have been used for cross-fold evaluation then details about which the folds are should be available. Furthermore, the dataset used should be explained in detail, including any possible version of it, its size and any other available parameters.

Replication

In 4.1 we discussed how the architecture, the algorithm implementation, the evaluation settings and the dataset settings are accountable for different results among different libraries or within the same library. However, the architecture of a library would be very difficult to change as well as the implementation of already established algorithms contained in libraries. Moreover, it would be dreadful to have different libraries behave the same. Thus, the main problem resides in reproducing the results of a study based on a proposed algorithm, the evaluation settings, the data used and the library the researchers have used to run the experiments.

Therefore, it is important to follow a set of guidelines or good practices to make the results reproducible. We have identified the following steps that if followed, will assist people reproducing the results using the same framework.

1. Explanation regarding the library and version you have used. If the library has been self-developed it should be available online.

2.

Step by step explanation of the evaluation settings such as the number of user neighbors used, if ratings below a threshold have been removed, if users that have not rated a certain number of items have been removed, if items with few ratings or too many ratings have been removed and if from the user base satisfying the criteria a sample of the users have been used or if all the users in the dataset have been used. Furthermore, other settings such as if there is a threshold for forming the user neighborhood or a threshold of common rated items should be mentioned. Finally, it should be noted that some of the settings available in a library might not be in another. All available settings of the library used should be mentioned. 3. In the dataset it should be made clear which dataset and version has been used, if the dataset has been split using test/train or whether a cross-fold validation has been used and how many folds have been used. In addition, it should be made clear which exact part has been used for training, which for testing and how the selection has been made to use the same training/testing parts in the reproduction of the experiments. 4. If the proposed algorithm extends a class of the library used or if it is a standalone file using the library for evaluation purposes.

Conclusions and future work

In this paper we have performed a comparative analysis and shown that it is difficult to reproduce evaluation results both across different libraries but also when the same library is used. The use of various settings and algorithm implementations lead to producing different results. For example, the selection of which data from datasets will be used for training and which for testing leads to different results, which in turn has an impact to the overall conclusion. Furthermore, we conclude that there are many different parameters that need to be considered by researchers when performing evaluation that it is very difficult to achieve a complete reproduction. Thus, we proposed a unified approach which can facilitate a common reference baseline for recommendation experiments across different frameworks and a set of guidelines to tackle a cross-industry challenge. This work is the first step towards an extensively broad validation framework for recommender systems and it aims to educate the community while collating feedback towards robust experimentation and comparison across recommender frameworks. The results show that when comparing results using the same settings with different libraries the output is not the same and within the same library small changes affect the output. This paper proposed a set of guidelines that can be followed to solve the problem. Furthermore, the results have been validated using two different libraries and real data.

In the future we aim to work towards the following research directions: Tests for information retrieval metrics such as Precision and Recall. Further validation will be necessary based on information retrieval metrics to examine the behavior of the libraries.

A framework for the reproduction of experiments. A complete framework that will support researchers in the direction of reproducing experiments should be developed, used and possibly standardized. A universal metric. The development of a universal metric that will make results comparable across libraries is essential. Reproducibility in user centric studies. It is essential in the domain of recommender systems to have a set of guidelines in the form of a framework that will assist towards the direction of reproducing results in user centric studies. However, it will be difficult to reproduce studies when humans are involved, since it will be difficult to have the exact number of people with the same background and maintain a similar behavior.

Table 1 .

 1 MAE results for Apache Mahout

		Number of k nearest neighbours used for evaluating MAE
		60	80	100	200	300	400
	PCC	0.843	0.835	0.827	0.802	0.789	0.785
	Jaccard	0.798	0.802	0.775	0.790	0.799	0.786

Table 2 .

 2 MAE results for Recommender101

		Number of k nearest neighbours used for evaluating MAE
		60	80	100	200	300	400
	PCC	0.870	0.862	0.841	0.811	0.785	0.761
	Jaccard	0.724	0.718	0.717	0.715	0.710	0.715
	4

Table 3

 3 presents the results of replicating the tests that are presented in table 2. The first two rows represent the first test where the exact same evaluation settings and data have been used as in table 2. The two rows further down represent the second test run with a different random selection of 80% for training and 20% for testing. Finally, table 4 contains results based on a 5-fold cross-fold validation and not on an 80-20 training/testing scale, which makes a difference because it produces the average of different MAE evaluations and this should be specified in the settings. In table4Recommender101 and PCC have been used with 60 neighbors and with a different minimum number of ratings per user. Moreover, in table 3 the 1st and 2nd tests of each method show that when the exact same settings are used but the training and testing parts of the dataset are randomly selected then there are differences in the output values and in table4we show that if the number of minimum considered ratings that a user has submitted to be taken into consideration for the evaluation process is different then different results are derived.

Table 3 .

 3 Reproducing the MAE results based on Recommender101

		Number of k nearest neighbours used for evaluating MAE
		60	80	100	200	300	400
	PCC (1 st )	0.870	0.862	0.841	0.811	0.785	0.761
	Jaccard (1 st )	0.724	0.718	0.717	0.715	0.710	0.715
	PCC (2 nd )	0.868	0.860	0.841	0.810	0.784	0.760
	Jaccard
	(2 nd )	0.723	0.716	0.716	0.713	0.709	0.710

Table 4 .

 4

	5-fold cross-validation with different settings MAE results based on
		Recommender101
	Method used	Min number of ratings	Min number of ratings
		per user	per user
		(30)	(Not known and not
			specified -Default value
			used by the library)
	PCC	0.872	0.890
	5


Kristiyan Balabanov
email: balabano@stud.fra-uas.de

Doina Logofȃtu

Costin Badica
email: cbadica@software.ucv.ro

Florin Leon
email: florinleon@gmail.com

A Simulation-Based Analysis of Interdependent Populations in a Dynamic Ecological Environment

Keywords: Population dynamics, Ecological simulation, Agent-based modeling, Predator-prey relation, Evolution-inspired optimization

With the ever increasing computational power of computers, simulation-based approaches have become a feasible testing technique that does not require investing valuable resources to create an actual prototype. Thus, design changes can be introduced and design errors can be fixed before it is too late, making simulation a cheaper, safer and often more acceptable from an ethical perspective approach. In our paper we summarize the results from the analysis with the help of a computational simulation of a simple, yet analytically intractable problem scenario from the field of ecology. Our main goal is to confirm that even with a seemingly simple agent-based model and simulation, one could obtain plausible results regarding a system's real life behavior. As a last point we propose a more efficient alternative for analysis, rather than the more expensive simulation.

Introduction

Simulation is a a well-known and wide-spread method of system analysis, and a lot of different branches in industry/science make use of them due to the various advantages that they offer. As an example, it is more economical to test the aerodynamics of a car without the need of an actual prototype [START_REF] Law | Simulation modeling and analysis[END_REF]. On the other hand, in some projects it is simply the most feasible approach with respect to effort-cost ratio, e.g. to simulate a space rover's mission to another planet [START_REF] Norris | Mission-critical development with open source software: lessons learned[END_REF].

Certain phenomena occur at a rate either too fast or too slow to be efficiently observed in real-time, such as explosions or plant growth. Furthermore, a welldesigned simulation can not only save time and money, but also spare lives, for instance when conducting air-bag tests or in any experiments with living organisms. One could refer to the latter as ecological simulation, which has become quite popular recently due to the numerous environmental issues resulting from globalization and industrialization. Despite still existing skepticism, it is evident by now that both have lead to a lot of changes in our environment, mostly negative and often irreversible. Species are becoming endangered or going extinct, which is bound to affect predator/prey chains in the respective ecosystems. With simulation means one could analyze the consequences of the resulting imbalance without involving actual animals and before it is too late.

In this paper we present the results we gathered when simulating a simple marine ecosystem on a micro level. We based our model on the one described in [START_REF] Balabanov | Considerations in Analyzing Ecological Dependent Populations in a Changing Environment[END_REF], but extended and formalized it according to the well known design of cellular systems and more precisely a cellular automaton. The main goals that we set for this project were to further confirm the statement introduced in [START_REF] Balabanov | Considerations in Analyzing Ecological Dependent Populations in a Changing Environment[END_REF] that even somewhat complex real world phenomena/events/scenarios can be simulated with a relatively simple abstract model, that, nevertheless, exhibits authentic behavior. Our emphasis, however, was on proving the strengths of computational simulation when considering analytically intractable problems. The tests that we present served not only the purpose to verify the accuracy of the extended model, but also to deliver useful insights regarding the problem under consideration, such as input/output relation, without the need of a complex formal description. Furthermore, we acknowledge the pitfalls of simulation-based analysis in terms of computational effort needed and shortly discuss a more efficient approach to optimize the given problem scenario with the use of an evolutionary programming technique.

Problem Description

In its core the problem scenario used for the experiments is a relatively simple one: a finite space populated with objects of certain type, that interact with one another according to predefined rules. A less abstract extension of this scenario would be any ecosystem and the species populating it. In our experiments we modeled a sea ecosystem and three marine species forming a food chain. For the concrete design we used the well-known Wa-Tor world described in A. K. Dewdney's work [START_REF] Dewdney | Sharks and fish Wage an ecological War on the toroidal planet Wa-Tor[END_REF]. It is a torus-shaped world with no landmass, but only one great ocean inhabited by marine species. To simulate an actual ecosystem, each species has a specific behavior according to which it interacts with both the environment and members of other species'. The behavior consists of a set of rules, which reflect the real world equivalents of the respective species' to a certain degree. All rules are defined on a micro level, i. e. only an individual's current state and its direct neighbors are considered. Each rule can be easily modified to reflect any introduced change of both internal (evolution) or external (cataclysmic event) nature, as it happens in the real world, and then the potential impact on the environment can be observed. Originally Dewdney described a world inhabited by only two species forming a linear predator-prey relationship -sharks (predator) and fish (prey). Their interaction was pivotal for the environment's fate: sharks can survive only if there are enough fish to hunt, and fish can survive only if there are not too many sharks to hunt them to extinction. Fish feed on infinite plankton, which is not modeled for the sake of simplicity. Following the example of [START_REF] Balabanov | Considerations in Analyzing Ecological Dependent Populations in a Changing Environment[END_REF], we extended Dewdney's idea with an additional third species to create a slightly more complex food chain -whales, which hunt both sharks and fish, but have no enemy. This new species is partially theoretical as it does not depict the actual diet of real world whales.

Such a scenario related to ecology is a perfect example of a problem domain, that is well-nigh impossible to solve using real life resources for two major reasons: a) constructing and populating or isolating an actual ecosystem would be insanely expensive, unless in a very small scale, which might not yield the desired authenticity and/or results; b) experiments with animals in general raise a lot of questions regarding moral principles and are often reproached by modern society. On the other hand, formally specifying a mathematical model of the problem would prove to be as equally difficult simply due to its complexity -thousands of agents, each with its own characteristics, dispersed within the environment, randomly roaming and interacting. In other words, the given problem, although computationally solvable with finite resources in theory, can be seen as analytically intractable in practice. Therefore, developing a computer simulation using a moderately complex model is a viable approach to obtain valuable insights regarding the problem scenario, albeit not necessarily the optimal solution [START_REF] Ulam | Adventures of a Mathematician[END_REF][START_REF] Rédei | John von Neumann: Selected letters[END_REF][START_REF] Farge | Numerical experimentation: A third way to study nature[END_REF]. In our work we strove to confirm the accuracy of the model presented by [START_REF] Balabanov | Considerations in Analyzing Ecological Dependent Populations in a Changing Environment[END_REF] and its ability to self-sustain, but also tried to determine whether a relation between the input parameters and the ecosystem's ability to self-sustain exists. Moreover, we searched for an approach to efficiently find optimal input parameter combinations, i. e. such that do not cause an ecosystem collapse (species becoming extinct).

Implementation of the Problem

To test our ideas we developed a simple and robust software application. As more than 30 years have passed since Dewdney's initial publication, one can easily find various implementations of the Wa-Tor scenario. Proprietary software was excluded from consideration. After a brief evaluation of the open-source solutions according to the criteria maturity (how well developed is the product so far), longevity (what are the prospects of the software being further supported and developed) and flexibility (effort needed to integrate/modify the product) as suggested by [START_REF] Norris | Mission-critical development with open source software: lessons learned[END_REF] showed that neither was adequate enough, hence our initiative to design and implement an entirely new set of tools using Java.

Application Architecture and Representation

For the design of our application we chose a classic bio-inspired approach: an abstract cellular system. The idea is derived from biological tissues, where the fundamental unit is the cell. The cell is, indeed, a quite complex structure by itself [START_REF] Harold | The Way of the Cell[END_REF], but when multiple cells cooperate even on a very basic local level, the outcome is a multicellular organism with unmatched capability compared to that of the individual cells building it. The human body is just one of countless examples in nature. This approach has already been widely used in design leading to the generalization of the resulting system type into the so called cellular systems. Essentially, such a system is a finite collection of basic units building a space. The units can be called cells and the space an organism accordingly. Each cell is identified by specific information about itself (e. g. an n-tuple of numerical values) and this information at a given time is called a state. The dynamics of such a system are expressed with the change in the cells' state depending on various factors. This state transition can depend on the current state of the cell, its past state and/or on the states of the surrounding cells. The collection of cells that can directly influence each other's state is called a neighborhood. Once the system is running, the cells update their states over time according to a predefined set of state transition rules and always reside in one from a finite set of possible states. A more detailed description of cellular systems is offered by [6, chap. 2].

The most prominent advantage of cellular systems is that they offer a simple modeling approach on a micro level, which however, can still yield plausible insights regarding the global behavior of the model. In the case of our problem, it is much easier to model the behavior of separate individuals based on their direct neighbors, rather than model the behavior of the entire population as one complex object.

From the various kinds known today we adopted the relatively simple, but popular cellular automaton (CA), more precisely the 2-dimensional game of life CA, as the base architecture of our application. A vivid example is John Conway's Life Game [START_REF] Gardner | The fantastic combinations of John Conway's new solitaire game "life[END_REF][START_REF] Gardner | On cellular automata, self-reproduction, the Garden of Eden and the game "life[END_REF]. Using Floreano et al.'s [START_REF] Floreano | Bio-inspired artificial intelligence : theories, methods, and technologies[END_REF] decomposition of a cellular automaton into its components and their elaborate description, we modeled the Wa-Tor ecosystem scenario as a cellular automaton as follows:

Base unit. The base unit is the cell represented as a square grid tile of certain color in the cellular space.

Cellular space. The space is a 2-dimensional lattice of cells forming a rectangular grid with size 500 × 300 cells. Time variable. The state transitions in the system unfold along a discrete time axis with cycle as its base unit. One state transition happens per cell per cycle.

State and state set. The state of each cell consists of the animal type that the cell represents together with its respective attributes tuple. Therefore, each cell can reside in one of four major states {F ish, Shark, W hale, Emptycell} and a multiple of sub-states defined by the numerical values of the respective species' attribute tuple.

State transition function.

The transition from one state to another is represented by the actions that an individual can perform, such as moving, feeding, reproducing and dying. Both the major state of the neighbor cells and the instance of the attribute tuple of the considered cell influence the transition. It is not deterministic (e. g. a fish surrounded by empty cells could move to any one of it), and where more choices exist, their probability distribution is uniform.

Neighborhood. The von Neumann neighborhood is implemented, i. e. a cell's state is directly influenced only by neighbors at a Manhattan distance of 1 from it (its direct upward, downward, leftward and rightward neighbors).

Boundary conditions. For practical reasons the cellular space cannot be infinitely large, hence the need of appropriate boundary conditions to ensure that the system has a homogeneous neighborhood (every cell has the same type of neighborhood). We chose periodic boundary conditions by connecting opposite ends of the grid and essentially eliminating the boundaries, i. e. transforming the 2-dimensional grid into a 2-dimensional toroid (torus). Initial conditions. The size of each species' population as well as the initial numerical values for each individual's attribute tuple (equal among all individuals of the same species). Both can be selected by the user before the start of the simulation. The distribution of the individuals over the cellular space is uniform.

Stopping conditions. The simulation stops after 3000 cycles (user adjustable).

Defining the Simulation Model

For the purposes of our study we adopted the simplified model proposed by [START_REF] Dewdney | Sharks and fish Wage an ecological War on the toroidal planet Wa-Tor[END_REF] and further described in [START_REF] Balabanov | Considerations in Analyzing Ecological Dependent Populations in a Changing Environment[END_REF]: the behavior of the animal species consists of the actions moving, feeding, reproducing and dying; an individual is represented as an n-tuple of quantifiable attributes. The fish class is the simplest one modeled as the 2-tuple (C of f s , A repr ), consisting of the reproduction maturity age and the number of offspring created, which are positive natural numbers. Shark and whale objects are further identified by their life energy (a positive real number), that is constantly depleted and can be replenished only by killing prey, and by the energy gain from eating the prey (a positive natural number), which varies according to the prey type. Unlike fish, predators do not reproduce over a constant period, but do so only if a certain life energy level has been reached, thus their reproduction rate is directly related to the presence of prey. The shark class is modeled as the 4-tuple

(C of f s , E repr , E lif e , E eat f ish )
and the whale class as the 5-tuple (C of f s , E repr , E lif e , E eat f ish , E eat shark ), respectively. Each existing individual performs the aforementioned actions as defined in [START_REF] Balabanov | Considerations in Analyzing Ecological Dependent Populations in a Changing Environment[END_REF] in a specified order and a cycle in the simulation ends when all individuals have 'acted', after which the environment is updated. In terms of cellular automata the actions of an individual/cell can be seen as the state transition of that cell or/and one or more of its neighbors, whereas the various instantiations of the respective attribute tuples as the private information about the given individual/cell.

4 Performed Tests and Results Obtained

Model Accuracy

In the previous work on the topic [START_REF] Balabanov | Considerations in Analyzing Ecological Dependent Populations in a Changing Environment[END_REF] the simulation was run with different combinations of initial population sizes, repeating each combination multiple times to account for the not entirely deterministic behavior of the individuals. The obtained results did show similarities with real world population dynamics [START_REF] Begon | Population Ecology: A Unified Study of Animals and Plants[END_REF], e. g. predator overpopulation leads to the prey going extinct, vice versa with prey underpopulation and predators are more vulnerable than prey since they have to roam and search for food. Moreover, by plotting the change in the population sizes over the course of the simulation, it was shown that despite the simplicity of the model, successful initial population size combinations result in the system reaching an equilibrium state, and the populations exhibiting dynamics like those described by the Lotka-Volterra-Model [START_REF] Hoppensteadt | Predator-prey model[END_REF].

Ecosystem's Capability to Self-Sustain

Since not every initial population size combination is favorable regarding the ecosystem's survival, and some combinations have only a partial success rate, a second series of experiments was aimed to a) prove that there is an integral not empty solution space (initial population size combinations) for which the given model of the simulated ecosystem can reach the so called equilibrium state; and 2) to define its boundaries. For that purpose the system was run automatically over a long period of time with randomly generated initial population sizes from a specified domain for the three species. It was shown that the successful input combinations form a set in 3-dimensional space, which with enough runs would resemble an irregular solid. In other words a solution space exists and the ecosystem is with high probability capable to self-sustain given any input from the respective set.

Input/Output Relation

From the results discussed in 4.1 and 4.2 it is clear that the system has a high chance to reach equilibrium for some input combinations, and a very low chance for others, i. e. a relation between the input parameters and the outcome of the simulation presumably exists. This can be proven formally by finding a function f (p 1 , p 2 , ..., p n ) that maps an instance of the input parameters p 1 , ..., p 2 to the respective output. As already stated, however, the problem under consideration is in practice analytically intractable, thus such a function cannot be obtained with a reasonable amount of effort. Instead, in our approach we decided to reuse the empirical formula described in [START_REF] Balabanov | Considerations in Analyzing Ecological Dependent Populations in a Changing Environment[END_REF], which is based on the statistical data gained from the initial tests and on the observations made while analyzing it. The function is defined as

S(P f [n f ], P s [n s ], P w [n w ]
), where S is the dependent variable (ecosystem stability), and P f [n f ], P s [n s ], P w [n w ] are the independent variables representing the probability with which the respective initial population sizes of fish, sharks and whales would survive. Moreover, from the already made conclusions it is known that some species are more vulnerable than others, and so their survival should be weighted more, e. g. sharks. As a result the stability of the system is defined as a function of the survival probability of each species, given its initial size, combined with a weighting factor based on the species' vulnerability:

S(P f [n f ], P s [n s ], P w [n w ]) = P f [n f ] • 0.2 + P s [n s ] • 0.5 + P w [n w ] • 0.3 , (1)
where P x [n x ] is the survival probability of species x with initial size n x in the respective test case. Using this approximation formula the ecosystem's stability factor was calculated for various initial predator population sizes within the range [2 , 50000] and two distinct fish population sizes: 5,000 and 50,000. The results are illustrated in Fig. 1 and show an obvious relation between the starting conditions and the simulation outcome. It is easy to see that an increasing predator population decreases the stability factor rapidly, indicated by the colors becoming darker towards the maximum values of the x-and y-axis. This is especially true for the whale population since the heat map darkens faster vertically (along the y-axis), rather than horizontally (along the x-axis). Ample quantities of fish prey also contribute for a better ecosystem stability (compare the visibly brighter heat map for the test cases involving an initial fish population of 50,000). These results correspond to the conclusions made earlier about the accuracy of the model (see section 4.1). Any combination representing a predator overpopulation resp. prey underpopulation is colored in dark. Additionally, the greater part of both heat maps is in blue/purple hue, indicating a value less than 0.3. In other words, in most test cases both predator species, but especially the sharks, went extinct before the stopping condition of the simulation was met. Nevertheless, a comparison with the results regarding the system's ability to self-sustain documented in [START_REF] Balabanov | Considerations in Analyzing Ecological Dependent Populations in a Changing Environment[END_REF] reveals a partial error in the solution space's bounds. It is our belief that this could be eliminated with a better approximation of the solution space boundaries (by performing more runs) as suggested in the corresponding section or a light modification of the weighting factors used in Eq. 1.

The last set of tests, that we conducted, were to determine a similar relation between the system's stability factor and the initial numerical values of a species' attribute tuple. For that purpose we repeated all test cases illustrated in Fig. 1 (left), while only changing the instance of the fish species' attribute tuple from [START_REF] Begon | Population Ecology: A Unified Study of Animals and Plants[END_REF]20) to [START_REF] Farge | Numerical experimentation: A third way to study nature[END_REF]20), i. e. increasing the maximum number of offspring a fish can spawn from 2 to 5. This yielded a definite increase in the ecosystem's chance to reach equilibrium, as highlighted by the considerably brighter coloring of the heat map even in predator overpopulation/prey underpopulation scenarios (see Fig. 2, right).

Approach to Efficiently Optimize Input Parameters

The final question we would consider during this work is how to optimize the entire set of input parameters, so that the outcome of the simulation is favorable. Up to now only the size of the initial populations was regarded, but when comparing the improvement of the system's stability by changing these as depicted on Fig. 1 with the improvement gained by modifying the attribute tuple of a species (see Fig. 2), one can quickly acknowledge the significantly better results of the latter approach. A major difficulty, however, is again the size of the input space. With sufficient knowledge in combinatorics it is easy to see that using the 3-tuple (F ish, Sharks, W hales) as input, where each element represents the Fig. 1. Relation between the initial predator population sizes and the stability of the ecosystem obtained with Eq. 1. Two different fish population sizes have been used in the experiments: 5,000 (left) and 50,000 (right). Darker/colder colors represent lower stability factor. The stability factor ranges from 0.0 (no species survived any of the test cases) to 1.0 (every species survived all of the test cases). possible input combinations. In a similar way we can count the possible instances I for the attribute n-tuple of each species with Eq. 2:

I = n i=1 |A i |, (2)
where |A i | is the number of distinct numerical values, that attribute A i can take. For instance the 2-tuple of the fish species could have the following ranges for its elements

(C of f s , A reproduce ) ⇒ ([1 , 5], [1 , 100]),
yielding a total of I f ish = 5 • 100 = 500 possible attribute instances. Analogously the shark 4-tuple and the whale 5-tuple could be defined as Even though this number is not much greater than the number of population size combinations, there are 11 input parameters when summing the tuple elements of all three species, yielding an 11-dimensional input space respectively, unlike the 3-dimensional one for the population sizes. Therefore, applying the graphical solution approaches presented so far in the previous sections would be less than feasible. Moreover, the conclusions made were obtained using excessive testing at the cost of hundreds of hours of computational processing, and could be classified as good approximations at best, which is supported by the small contradiction between the results described in sections 4.2 and 4.3. This raises doubts regarding the efficiency of the simulation-based problem solving should problem complexity increase (e. g. more input parameters).

(C of f s , E repr , E lif e , E eat f ish ) ⇒ ([1 , 5], [51 , 100], [1 , 100], [1 , 10]) and (C of f s , E repr , E lif e , E eat f ish , E eat shark ) ⇒ ([1 ,
A more promising approach, that we would like to propose, is to combine the simulation-driven architecture of the cellular automaton as it is with an evolutionary search algorithm to traverse the input space for combinations that yield a stable ecosystem. Essentially, we would transform a simulation problem into an optimization one, where a model consisting of objects with specific characteristics and rules for their interaction is known, a desired output range is specified and the point of interest is the unknown set of input instances that yield an output within the desired range.

Inspired by biological evolution, hence their name, evolutionary algorithms (EA) have gained significant importance in the recent years, especially in the domain of optimization. Their use can be quite rewarding as an efficient alternative to traditional deterministic methods, more so in very complex and intractable problem scenarios. In the following a short summary of the basics is given, as well as an outline of the modifications needed to incorporate the evolutionary optimization technique in our application. It is our strong belief that the integration effort would not be considerable, but the obtained insights might prove to be of value. For a more comprehensive discussion on the topic of EA basics and application refer to [START_REF] Gerdes | Evolutionäre Algorithmen : genetische Algorithmen -Strategien und Optimierungsverfahren -Beispielanwendungen[END_REF][START_REF] Michalewicz | Genetic algorithms + data structures : = evolution programs[END_REF][START_REF] Eiben | Introduction to evolutionary computing[END_REF].

Solution candidate space. As the name implies this is the set of all possible candidate solutions. It can be indefinitely large, but for practical reasons it has to be bounded. Candidate solutions can be anything from numerical values to entire objects. In the case of our Wa-Tor application, the candidate solution space consists of all attribute combinations for the three species (e. g. 6.25 • 10 15 if the aforementioned example is taken). Genetic operators. These operators are functions that randomly modify the existing collection of candidate solutions to increase diversity. Typical operators are a) mutation -changing a random characteristic of a candidate solution; and b) recombination -combining two or more solutions to produce new ones; Integrating this functionality in the existing Wa-Tor simulation can be done quite easily in the reproduction action of the animals, e. g. when offspring are spawned their attribute instance can be created by combining that of the parent with those of other existing individuals. Mutation can be implemented similarly as a random change in a spawned offspring's attribute instance inherited by the parent. Genetic operators modify only the genotype. The phenotype cannot be inherited, but is crucial for the fitness of the respective candidate. Solution candidate encoding. A candidate solution is typically represented as a phenotype-genotype pair. Just like in biology the phenotype is comprised of a candidate's visible attributes that change over its lifespan due to interaction or external events. On the other hand the genotype is the entire information about the core structure of a candidate in some encoded form, e. g. DNA in real life and usually a binary string in software applications. In the Wa-Tor scenario the phenotype of an object would be its actual instance in the simulation, whereas an adequate genotype would be the information about the object's attributes received at its creation, that is immutable during the lifespan of the object, but inheritable by its offspring.

Fitness function. The idea behind the fitness function is to decrease the population diversity by eliminating poor candidate solutions, but thus improve the overall quality of the candidate solution space (called 'survival of the fittest' or ' natural selection' in the field of biology). The fitness function in the Wa-Tor scenario is the simulated interaction between the individuals. Using the predefined interaction rules such as moving and feeding, individuals may survive or get killed by predators/die out of starvation. Certain genotype instances may have higher chances to prevail than others, e. g. individuals that can give birth to multiple offspring are more likely to pass down and spread their genotype in the respective population.

Conclusion and Future Work

The main goal of our project was to design and develop an application to test the strengths of a simulation-based analysis. A relatively simple and well-known problem domain was chosen, which, however, poses multiple challenges regarding its formal specification, hence the need of an alternative approach. An ecosystem and various species inhabiting it were modeled in the fashion of Dewdney's Wa-Tor [START_REF] Dewdney | Sharks and fish Wage an ecological War on the toroidal planet Wa-Tor[END_REF]. Even though the created model is a fairly basic one, including only several interaction rules between the organisms within the simulation, and a handful of attributes to characterize them, no mathematical specification of the system can be derived without a significant amount of effort. Via simulation however, it was possible to define very simple rules on a micro level, and still obtain valuable insights regarding the global behavior of the environment and the populations inhabiting it.

We augmented previous work on the topic by performing extensive testing to gather enough data and visualize the relation between the inputs and the output of the system. For that an empirically derived formula (see Eq. 1) was used to calculate the system's output (stability factor) as a function of the probability that a species with a given population size would survive. The formula uses weight coefficients to discriminate between more robust and more vulnerable species. In Figures 1 and2 we showed the direct dependence of the ecosystem's stability on the initial population sizes and on a specific species' attributethe number of created offspring after reproduction. In the final part of the paper the challenges of extensive testing were discussed and a new approach based on evolutionary programming was proposed as a possible more efficient alternative.

Future work would revolve around the expansion of the application to incorporate the described evolutionary technique and allow for the model (species' attributes) to change over the course of the simulation similar to the evolution of organisms in the real world. The potential optimization benefits of this approach are to be evaluated and compared to those of the extensive testing.

Fig. 2 .

 2 Fig. 2. Relation between the attribute 'offspring count' for the fish species and the stability of the ecosystem obtained with Eq. 1. Two different instances of the maximum offspring count have been used in the experiments: 2 (left) and 5 (right).

  respective species' population size within the range [10 , 50000], yields a total of 44991 3 ≈ 50000 3 = 1.25 • 10 14

  5],[101 , 200],[1 , 200],[1 , 10],[1 , 50]), yielding I shark = 5•50•100•10 = 250000 and I whale = 5•100•200•10•50 = 50000000 possible instances respectively. The total count of input parameter instances I total is then I total = I f ish • I shark • I whale = 500 • 250000 • 50000000 = 6.25 • 10 15 .