Gautier Bideault

Luc Mioulet

Clément Chatelain

Thierry Paquet

Spotting Handwritten Words and REGEX using a two stage BLSTM-HMM architecture

Keywords: Regular Expression Spotting, REGEX, Handwritten Document, Handwriting Recognition, BLSTM, Word Spotting

In this article, we propose a hybrid model for spotting words and regular expressions (REGEX) in handwritten documents. The model is made of the state-of-the-art BLSTM (Bidirectional Long Short Time Memory) neural network for recognizing and segmenting characters, coupled with a HMM to build line models able to spot the desired sequences. Experiments on the Rimes database show very promising results.

INTRODUCTION

Regular expression (REGEX) spotting consists in detecting patterns sequence of characters that obey certain rules described using meta models such as lower cases (#[a-z]#), upper cases (#[A-Z]#) or Digits (#[0-9]#). Detecting such regular expression in handwritten documents can be useful for finding sub-string which are relevant for a further higher level information extraction task. For example, a system of that kind could spot entities. For example, spotting date (#[0-9]{2}/[0-9]{2}/[0-9]{4}#), first name (#[A-Z][a-z]*#), ZIP code and city name of a french postal address (#[0-9]{5} [A-Z]*#). The extraction of these informations allow to consider high level processing stages such as document categorisation, customer identification, Named Entity detection, etc. Some REGEX spotting systems have been designed for electronical documents, using Natural Language Processing methods. [START_REF] Dengel | smartfix: A requirements-driven system for document analysis and understanding[END_REF][START_REF] Holzinger | Using ontologies for extracting product features from web pages[END_REF] In this case, the REGEX spotting is rather straightforward as it consists in applying exact string matching methods on the ASCII text. When dealing with document images, a recognition step is needed in order to produce the ASCII transcription before processing the input data. The trouble is that this recognition step is subject to errors and uncertainty, making the string matching problematic. Some attempts have been made on printed documents. 3,4 In these works, an OCR is applied on the whole document before applying the regular expression spotting step based on a set of rules that performs an exact matching. In spite of OCR errors, the system provides acceptable performance * .

To the best of our knowledge, there are only a few works concerning REGEX spotting in handwritten documents. The reason is that exact matching methods can not overcome the frequent recognition errors due to the intrinsic difficulties of recognizing handwriting. Therefore, in order to cope with these errors, inexact matching method should be carried out. This can be performed using statistical sequence models such as HMM. Some works have been published within this framework, proposing pattern spotting such as dates 5 and numerical fields 6, 7 that involve meta models of characters, namely digits. However, these HMM based approach are limited to very specific fields. A more generic approach for REGEX spotting in handwritten documents has been addressed using pure HMM approach 8 , but led to moderate results (see section 5 for detailed results and comparison).

In this paper, a REGEX spotting system for handwritten documents is proposed based on a combination of HMM statistical sequence model with the state-of-the-art BLSTM neural network. Our alternative hybrid BLSTM/HMM model enables us to benefit from both strong local discrimination, and the generative sequence ability of the HMM. This paper is organized as follows: first a review of word and REGEX spotting is given in section 2, then we present our REGEX spotting system based on a hybrid BLSTM/HMM in section 3. Section 4 is devoted to the experimental setup and results on both word spotting and regular expression spotting tasks carried out on the RIMES database. 9

RELATED WORK

As a REGEX can match sequences with variable length and characters, a REGEX spotting task can be assimilated to a word spotting task where the word belongs to a lexicon which contains all the character string variations admissible by the REGEX. The less constrained the REGEX, the larger the size of the lexicon. Relaxing those constraints makes the REGEX spotting task more complex especially when considering handwritten document images. As regular expression spotting shares many aspects in common with word spotting we now briefly introduce the related works concerning word spotting approaches.

Word spotting in document images has received a lot of attention these last years. Systems proposed in the literature are divided into two main categories : Image based and recognition based systems. The first one, also known as query-by-example, operates through the image representation of the keywords. 10-14 Such systems are therefore limited to deal with omni-writer handwriting and require to get an image of the query. The second kind of approaches, also known as query-by-string methods, deals with the ASCII representation of the keywords. [START_REF] Rodríguez-Serrano | Handwritten word-spotting using hidden markov models and universal vocabularies[END_REF][START_REF] Frinken | A novel word spotting method based on recurrent neural networks[END_REF][START_REF] Thomas | An information extraction model for unconstrained handwritten documents[END_REF][START_REF] Fischer | Lexicon-free handwritten word spotting using character hmms[END_REF][START_REF] Wshah | Script independent word spotting in offline handwritten documents based on hidden markov models[END_REF] Moving from the image representation to the ascii representation of the query is performed through a recognition stage. These systems are suitable for omni-writer handwriting and can be used with any string query of any size. In this context, many works have focused on several variants of Hidden Markov Models (HMMs) to process this intrinsically sequential problem. [START_REF] Wshah | Script independent word spotting in offline handwritten documents based on hidden markov models[END_REF] State-of-the-art recognition-based approaches are based on a line of text models. [START_REF] Thomas | An information extraction model for unconstrained handwritten documents[END_REF][START_REF] Fischer | Lexicon-free handwritten word spotting using character hmms[END_REF][START_REF] Wshah | Script independent word spotting in offline handwritten documents based on hidden markov models[END_REF] The line model generally contains a model of the target word, combined with filler models that describe the out-of-vocabulary words. For example in Thomas et al., [START_REF] Thomas | An information extraction model for unconstrained handwritten documents[END_REF] the authors present an alpha-numerical information extraction system on handwritten unconstrained documents. It relies on a global line modeling allowing a dual representation of the relevant and the irrelevant information. The acceptation or rejection of the matched keyword is controlled by the variation of a hyper-parameter in the HMM line model. A similar approach is presented in Fisher et al. [START_REF] Fischer | Lexicon-free handwritten word spotting using character hmms[END_REF] The line model is made of a left and right filler models surrounding the word model. The acceptation or rejection of the matched keyword is controlled by a text line score based on the likelihood ratio of the word text line and the filler text line model. However we know that HMM rely on strong observation independence assumptions and they perform poorly on high dimensional observations. Moreover, they have low discrimination capabilities between character classes due to their inherently generative modelization framework.

Recently a new approach based on recurrent neural networks has overcome these shortcomings. Bilateral Long Short Term Memory (BLSTM) architecture has demonstrated impressive capabilities for omni-writer handwriting recognition. 20 Some primary applications of BLSTM to word spotting have also demonstrated promising results. [START_REF] Frinken | A novel word spotting algorithm using bidirectional long shortterm memory neural networks[END_REF][START_REF] Wöllmer | A tandem blstm-dbn architecture for keyword spotting with enhanced context modeling[END_REF] In this system, the BLSTM is combined with the CTC layer which provides character class posterior probabilities. Then a token passing algorithm allows efficient decoding of the spotting line model. Very interesting results have been reported on the IAM Database 21 † .

In this paper, we combine the BLSTM-CTC architecture with a HMM based spotting line model. This two stage architecture is first evaluated for hadnwritten word spotting on the RIMES database. Then we explore some extensions of the system to Regular Expression spotting (REGEX Spotting). This model is described in the following section.

A TWO STAGE BLSTM-CTC HMM FOR INFORMATION SPOTTING

In this section, we describe our hybrid model for word and REGEX spotting. We first describe the BLSTM-HMM architecture that has been retained, then we present our word spotting model, based on standard state-of-the-art word spotting framework. And finally, we propose the adaptation of this model for REGEX spotting. † Average Precision of 88.15% and R-precision of 84.34%

BLSTM-CTC for character recognition and segmentation

The BLSTM-CTC is a complex Recurrent Neural Network able to manage long term dependencies thanks to its internal buffer structure. Each neuron is specialized to stop a specific character in the input signal. The recurrent architecture allows each neuron to take account of the previous activated neurons (character), possibly at multiple time step earlier in the input signal (thus modeling long term dependencies). This typical architecture allows to take account of character bigrams in addition to the input signal to compute the activation of each neuron. The BLSTM is composed of two recurrent neural networks with Long Short Term Memory neural units. The first one processes the data from left to right whereas the second one proceeds in the reverse order. For each time step, decision is taken combining the two networks output, taking advantage of both left and right context. Such context is essential to have a certain knowledge of the surounding characters, because in most cases sequences of letters are constrained by the properties of the lexicon. The outputs of these two networks are then combined through a Softmax decision layer that provides character posterior probabilities in addition to a non decision class. This decision stage is called the Connectionist Temporal Classification (CTC) [START_REF] Graves | Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks[END_REF] that enables the labelling of unsegmented data.

These networks integrate special neural network units : Long Short Term Memory 23 (LSTM). LSTM neurons is composed of a memory cel, an input and three control gates. Each gates control the memory of the cell, i.e how a given input will affect the memory (input gates), if a new input should reset the memory cell (forget gate) and if the memory of the network should be presented to the following neuron (output gate). This system of control gates allows a very accurate control of the memory cell during the training step. A LSTM layer is fully recurrent, that is to say, the input and the three gates receive at each instant t the input signal at time t and the previous outputs (at time (t -1)). This architecture has shown very impressive results on challenging data-sets dedicated to word recognition 9, 24 due to its efficient classification and segmentation ability. For these reasons, its efficiency to cope with the low level character identification appears also very promising for handwritten words and REGEX spotting, since such scenario is less contrained by lexicon properties.

The proposed BLSTM/HMM architecture has been chosen in order to take advantage of both generative and discriminative frameworks. As shown on Figure 3.1, the input sequence is processed by a BLSTM-CTC network in order to compte character posterior probabilities at every step. Then the probabilities of each labels are fed to the HMM stage (using class posteriors in place of the character likelihood computed by Gaussian Mixtures Models in the traditionnal HMM framework) to perform the alignment of the spotting model. We now describe the HMM line spotting models which enable us to spot either words (cf section 3.2) or REGEX (cf section 3.3).

Lexicon

Handwritten word spotting model

Our word spotting model describes a line of text that may contain the word to spot. As it is classically proposed in the literature, it is made of the HMM word model surrounded by filler models that represent any other sequence of characters. Figure 2 shows an example of a word spotting model for the word "Madame". The space model is directly integrated into the filler. By constraining the whole model, we can locate the word at the beginning, in the middle or at the end of the line. The filler model is basically an ergodic model made of every character model. In our problem, we use 99 models corresponding to lower and upper cases, digits, punctuations and space. Decoding a text line is classically achieved using the Viterbi algorithm, the system will outputs the character sequence with the maximum likelihood P (X|λ). In order to accept the spotted word or reject it, decoding is generally performed twice: a first pass using the spotting model, and a second pass using a filler model. The likelihood ratio of the two models serves generally as a score for accepting or rejecting the spotted hypothesis. Using the BLSTM-CTC architecture, posterior probabilities are computed that can directly serve as a score for accepting/rejecting the hypothesis, without the need for a filler model. The score of each spotted hypothesis is computed by the average character posteriors over the number of frames spanning the hypothesis. This score is then normalised by the number of characters of the spotted word. Doing this, we choose to rely on the strong discriminative decisions of the BLSTM-CTC and use the HMM only as a sequence model constrained by high level information such as lexicons and/or language models. The graphical representation of the whole word spotting system is shown on Figure 3 We now show how this model can be adapted to REGEX spotting.

Regular expression spotting model

As previously mentionned, REGEX spotting is a generalisation of the word spotting task, the difference is that the sequences to spot are less constrained and more variable, thus leading to a larger lexicon of admissible expressions.

In order to cope with REGEX queries, we use the HMM stage to model a regular expression with a stochastic model of character sequences. Each meta model is an ergodic model of characters implied in the query, e.g, Lower Cases (#[a-z]#), Upper Cases (#[A-Z]#) or Digits (#[0-9]#), as it is the case for the Filler models. Figure 4 shows examples of meta models for these three examples.

We also need to model the variable length of the queries, which may occurs when using * or + operators (spotting between 0 and ∞ times a character, or spotting between 1 and ∞ times a character) such as in #[0-9]+# which stands for any sequence of at least 1 digit. This is simply modeled by allowing auto transitions over the desired character meta model. Figure 5 shows an example of a model for spotting variable length sequences. The query taken is the sub-string agr following by an unconstrained sequence of lower cases (#[a-z]*#), in this example we hope that the system will spot the word agréer correctly. As the transitions in the HMM meta models are ergodic, the Viterbi alignment will only be driven by the local classification of BLSTM-CTC. The spotting model depends on its discriminant capacity to feed the higher HMM stage with accurate information from the local character recognition stage.

The graphical representation of the whole REGEX spotting system is shown on Figure 6.

Finally, the integration of meta models and auto transitions into the line model allows spotting of handwritten REGEX. Practically, the line model is build on the fly at the time of querying the data-set, by rewriting the REGEX into a HMM line spotting model. At this time, the "translation" is manually done, but an automatization of this task can be performed for industrial purpose.

EXPERIMENTS

In this section, we give some details about the implementation of the system, starting with a description of the preprocessing stage in section 4.1 and the features extraction in section 4.2. The performance of the system are

Details of Preprocessing

The preprocessing of images consist in a simple three step image correction over the whole line. First a Sauvola binarisation by thresholding is applied. Then a deslanting process is carried out according to the following method: the image is rotated between [-Θ; Θ] and for each angle the histogram of vertical continuous traits H Θ is measured. Finally, a height normalisation is applied to center the baseline and normalize the heights of the ascenders and descenders.

Features Set

Our feature vector is based on Histograms of Oriented Gradient (HOG) [START_REF] Rodrıguez | Local gradient histogram features for word spotting in unconstrained handwritten documents[END_REF] extracted from windows of 8×64 pixels.

During the extraction, the window is dividing into sub-windows of n×m pixels. For each sub-window a histogram is computed, representing the distribution of the local intensity gradients (edge direction). The histograms of every windows are then merged to obtain the final representation of our feature vector representation. We used 8 × 8 non-overlapping sub-windows using 8 directions, this produces a 64 dimensional feature vector.

Results and discussion

To evaluate the performance of our system, all the experiments have been performed on the RIMES database used for the 2011 ICDAR handwriting recognition competitions. [START_REF] Grosicki | Icdar 2011-french handwriting recognition competition[END_REF] The training database is composed of 1.500 documents, the validation and test sets are composed respectively of 100 documents. In order to evaluate the spotting system, we compute recall (R) and precision measures (P). To do this, the number of true positives (TP), false positives (FP), and false negatives (FN) are evaluated for all possible threshold values. From these values, a recall-precision curve is computed by accumulating these values over all word queries. R = T P T P + F N P = T P T P + F P

(1)

Word spotting results

Word spotting systems are generally evaluated by spotting one word in a collection of documents. We have decided to evaluate our framework by searching a set of words (a lexicon) at the same time, allowing to deal with confusion between words. 8 Spotting a lexicon of keyword instead of a single word is well-suited for document categorization. [START_REF] Paquet | A categorization system for handwritten documents[END_REF] We evaluate the performance of our system on lexicon of size 25, 50 and 100 words respectively, following the same data-set and protocol as in Kessentini et al. 8 The recall-precision curves are obtained by varying the threshold applied on line scores (see section 3.2).

Figure 7 presents the recall-precision curves obtained by our BLSTM-HMM hybrid model for each lexicon (25, 50 and 100). It is compared with the results obtained by the standard HMM method developed in Kessentini et al. 8 As expected, the performance drop when the size of the lexicon increase. The BLSTM/HMM provides very interesting results, since the mean average precision ‡ is greater than 80% for 25-lexicon and 50-lexicon queries. When compared with the pure HMM approach, results show that adding the discriminative stage has drastically improve the performance of the whole system. Indeed, we can observe a significant gap of at least 20% between the mean average precision of the two systems, for each lexicon size. This is certainly due to the fact, that the local decision of the BLSTM are far more discriminative than Gaussian Mixtures.

Regular expression results

To evaluate the performance of our system on a regular expression spotting task we performed exactly the same experiments as in. 8 In this study the authors were interested in spotting 4 different REGEX queries corresponding to the the search for the sub-strings "effe", "pa", "com" and "cha" at the beginning of a word (#effe[a-z]*#, #pa[a-z]*#, #com[a-z]*#, #cha[a-z]*#). As for word spotting experiments, results of the HMM system have been added too in order to provide a precise comparison between those systems (cf Figure 8).

A first observation is that the system achieves good performance, since most of the REGEX queries lead to a mean-average precision of nearly 75%, whereas the queries involve many fewer constraints than for word spotting. Moreover, our results are far beyond the standard HMM approach. We can observe a gap of more than 40% in the difficult cases (#com[a-z]*#) and (#cha[a-z]*#) and 20% in easier ones (#effe[a-z]*# and #pa[a-z]*#). We have also tested less constrained queries, with the search for REGEX containing any sequence of upper cases characters (#[A-Z]*#), and any sequence of digits (#[0-9]#). This problem is by far more difficult than the previous queries since the corresponding sequences may have variable contents and lengths. For example the digit query should detect the sequence "1" as well as sequence "0123456789". Results are presented in Figure 9.

Knowing the difficulty of the problem, the performance are still interesting. Note that digit characters are not very frequent in the database. An interesting fact is that the Uppercase query can reach interesting precision scores, whereas the digit query can reach very high recall scores.

CONCLUSION

In this paper, we have proposed a hybrid system BLSTM-CTC/HMM able to spot any word of REGEX. We have shown that the hybrid system exhibits interesting results, even on weakly constrained queries such as the search for sequences of digits of arbitrary length. We have compared our system for REGEX spotting with some recent work carried out on the same data-set and using the standard HMM framework. Our approach outperforms this system by more than 30% on the standard word spotting task and by more than 40% on REGEX spotting. These very promising results allow to envisage the application of higher level spotting systems such as addresses, named entities for which a combination of specific markers (keywords and alpha numerical expressions) is generally used to detect the relevant information.

Figure 1 .

 1 Figure 1. Hybrid structure BLSTM/HMM : Detail of the communication between both stages. The BLSTM/CTC outputs a posteriori probabilities for HMM decoding.

Figure 2 .

 2 Figure 2. HMM line model : Detail of every component of the line model

Figure 3 .

 3 Figure 3. Hybrid structure BLSTM/HMM : Details of every step of the word spotting task from feature extraction to position of the word Madame in the sentence.

Figure

  Figure 4. HMM MetaModels

Figure 5 .

 5 Figure 5. HMM stage : Spotting of regular expressions #agr[a-z]*# (i.e every word beginning by the sub-string agr followed by any number of lower case characters)

Figure 6 .

 6 Figure 6. Hybrid structure BLSTM/HMM : Details of every step of the REGEX spotting task from feature extraction to position of the REGEX #Ma[a-z]*# in the sentence.

Figure 7 .

 7 Figure 7. Word spotting performance with different lexicons of words

Figure 8 .

 8 Figure 8. Regular expression spotting performance with different queries (#effe[a-z]*#, #pa[a-z]*#, #com[a-z]*# and #cha[a-z]*#)

‡ or break-even point: the point where Recall=Precision


Gautier Bideault

Luc Mioulet

Clément Chatelain

Thierry Paquet

A hybrid CRF/HMM approach for handwriting recognition

In this article, we propose an original hybrid CRF-HMM system for handwriting recognition. The main idea is to benefit from both the CRF discriminative ability and the HMM modeling ability. The CRF stage is devoted to the discrimination of low level frame representations, while the HMM performs a lexicon-driven word recognition. Low level frame representations are defined using n-gram codebooks and HOG descriptors. The system is trained and tested on the public handwritten word database RIMES.

Introduction

Handwriting Recognition (HWR) is a difficult problem due to the high variability of the data. Currently, the most widely used probabilistic models for handwriting modeling are Hidden Markov Model (HMM) [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF]. Multiple training frameworks have been proposed to train these generative models. The original generative framework relies on a Maximum Likelihood (ML) criterion [START_REF] Ara | Maximum likelihood training of the embedded hmm for face detection and recognition[END_REF], but it has been shown that a discriminative framework based on a Maximum Mutual Information (MMI) criterion [START_REF] Gauvain | Maximum a posteriori estimation for multivariate gaussian mixture observations of markov chains[END_REF] could lead to some improvement. Regardless of the criterion, HMM rely on strong observation independence assumptions and they perform poorly on high dimensional observations. Conditional Random Fields (CRF) [START_REF] Sutton | Introduction to conditional random fields for relational learning[END_REF] became more and more popular models during the last decade for sequence modeling because they are discriminative models and they do not rely on the same restrictive assumptions. The original CRF framework [START_REF] Sutton | Introduction to conditional random fields for relational learning[END_REF] was proposed to process symbolic data in the field of automatic language processing [START_REF] Gunawardana | Hidden conditionnal random fields for phone classification[END_REF]. A major drawback concerning CRF is there inability to process numerical data, they only process discrete values. When facing numerical data, they are generally introduced at a second stage of the model in order to model the dependency between classes, while raw numerical data are analyzed through a classification stage such as Artificial Neural Networks (ANN) for example in the field of Automatic Speech Recognition (ASR) [START_REF] Mohamed | Investigation of full-sequence training of deep belief networks for speech recognition[END_REF][START_REF] Zweig | A segmental crf approach to large vocabulary continuous speech recognition[END_REF].

Despite their ability to deal with symbolic data, CRF models are limited to label the observation sequence, i.e. to provide a label to each frame of the sequence. As a consequence, the CRF is not able to integrate high level knowledge through the integration of lexicons and/or language models, as it is whith HMMs. A second limitation of CRF, as opposed to HMMs, is the requirement of having groundtruthed data at frame level in order to train the models, thus preventing using embedded training afforded within the HMM framework.

In this paper, we propose a hybrid model that takes advantage of both generative and discriminative models in order to tackle Off-Line omni-writer handwriting recognition. The paper is organized as follows: first a review of the related works is given in section 2, then we present the hybrid model devoted to handwriting modeling in section 3. Experimental setup and results reported using the RIMES database [START_REF] Grosicki | Icdar 2009 handwriting recognition competition[END_REF] are presented in section 4.

Related Work

In the early nineties, hybrid architectures have been proposed to combine the advantages of both discriminative and generative models. They were initially designed for ASR by combining ANN (mostly Multi Layer Perceptron) with HMM [START_REF] Stephenson | Automatic speech recognition using dynamic bayesian networks with both acoustic and articulatory variables[END_REF]. Such hybrid models have also been proposed for HWR [START_REF] Bengio | Ann/hmm hybrid for on-line handwriting recognition[END_REF].

In general, these models use the ANN discriminative stage to analyse and classify local observations at frame level, whereas the HMM generative stage is devoted to the integration of higher level information such as lexicon, language models, . . . More precisely, the Gaussian Mixture Models (GMM) of the HMM stage are substituted for local posteriors computed by the ANN stage.

Recently, the Bilateral Long Short Term Memory (BLSTM) neural networks combined with a Connectionist Temporal Classification (CTC) stage [START_REF] Graves | Unconstrained online handwriting recognition with recurrent neural networks[END_REF] has proven to be a powerful alternative hybrid structure for sequence classification. Such a structure combines an efficient low level frame modeling stage with the ability to model long time dependencies, with a discriminative classification stage made of a simple logistic classifier. This structure has proven to perform extremely well for ASR and HWR [START_REF] Graves | A novel connectionist system for unconstrained handwriting recognition[END_REF].

CRFk [START_REF] Lafferty | Conditional random fields: Probabilistic models for segmenting and labeling sequence data[END_REF] were originally formulated for language processing tasks, due to their interesting theoretical properties they have also been applied in fields in which the ability to process numerical data is important. Hence, in order to process this data the CRF model has been adapted to be applied to applications fields such as Gesture Recognition (GR) [START_REF] Morency | Latten-dynamic discriminative models for continuous gesture recognition[END_REF] or ASR [START_REF] Quattoni | Conditional random fields for object recognition[END_REF].

In the field of HWR, some attempts have been reported on using CRF models. In [START_REF] Shetty | Handwritten word recognition using conditional random fields[END_REF], the authors introduce a CRF model to perform character sequences recognition. However, this method is applied on an already segmented character sequence consequently the segmentation is not modeled by the CRF stage. In order to perform both segmentation and recognition of characters [START_REF] Vinel | Joint optimization of hidden conditional random fields and non linear feature extraction[END_REF] introduced a non linear HCRF model that consists in a Deep Neural Network (DNN) and a CRF. The deep structure improves the discrimination at the low level while the HCRF allows high level modeling.

Most of the previous works of the literature that have developed hybrid models introduce a discriminative stage that deals with the low level input observable raw data. Neural Networks such as MLP, BLSTM or DNN are suitable models that provide higher level informative features (e.g class conditional probabilities) to the second stage of the hybrid architecture. This second stage is most of the time devoted to the contextual analysis of the hypothesis given by the first stage. It is generally based on a generative model that can introduce constraints such as lexicons and/or language models. In most cases, HMMs are implemented, but dynamic programming stages, such as CTC, have proved to be a possible alternative architecture.

HCRF have the specificity to be discriminative at both low and high level stages. But they are limited to the task of sequence labelling they have been trained for. Moreover, they cannot embed higher level information such as lexicon or language model at decoding time.

The following section presents the proposed hybrid model.

A CRF-HMM hybrid Approach

Overview of the proposed approach

The proposed CRF / HMM architecture has been chosen in order to take advantage of both generative and discriminative frameworks. As described on Figure 1, the CRF stage performs the discrimination of the low level frame representation. It extracts the local posterior probabilities of every character at every time using a forward-backward inference :

p(s t = q k |O (n) ) = α t (j)β t (j) N i=1 α t (i)β t (i) (1)
The forward α t (j) and backward variable β t (j) are defined as :

α t (j) = P (O 1 O 2 ...O t , q t = S i |λ) (2)
i.e the probability of the partial observation sequence, O 1 O 2 ...O t and state S i at time t, given the model λ.

The backward variable β t (j) is defined as :

β t (j) = P (O t+1 O t+2 ...O T |q t = S i , λ) (3)
i.e the probability of the partial observation sequence O t+1 O t+2 ...O T , given the state S i and the model λ.

In order to use the discriminative and highly contextual information of the CRF, the GMM of the HMM stage are substituted for these local posteriors, as it is traditionally the case for hybrid Neuro-HMM structures. Doing this, we can use the HMM generative stage to analyze the information in context with the possibility to introduce lexical and language constraints.

As CRFs are not able to cope well with numerical data, we propose an unsupervised classification stage based on k-means devoted to the discretization of the numerical Histograms of Oriented Gradient (HOG) feature vector (

CRF-HMM training

In order to train our hybrid CRF/HMM structure, we have to train both CRF stage and the transition probabilities of the HMM stage. An important issue when training a discriminative model, such as CRF, is that it requires a labelled training set at the frame level, whereas the groundtruth of handwriting databases is generally given at the word level. In order to get this frame level segmentation, we need to use first a standard HMM model trained on the same learning dataset, and used in a forced Viterbi alignment mode of the frame data on the word character sequence groundtruth. Following this frame labelling stage, the CRF is trained using Stochastic Gradient Descent (SGD). The convergence and the overfit of the training is controlled on a validation dataset during training. The HMM parameters (the conditional transition probabilities) are also computed on the labelled dataset.

N -gram data representation

CRF have been originally proposed to deal with high dimensional discrete symbolic features (words) for automatic language processing tasks. Therefore, HCRF have been introduced to deal with real valued raw data, in a way similar to neural networks or deep neural networks can do. Deep architectures have the ability to learn high level features from the raw numerical data an unsupervised training , whereas HCRFs introduce a fixed number of hidden states that act as sequentially structured features optimized during training.

The drawback of these architectures is their very long training time and their sensitivity to the initial conditions, which make them difficult to optimize with standard computational resources. The use of GPU is recommended to learn the model under a reasonable time.

Taking advantage of the ability of CRFs to deal with very large discrete features (several thousands in the case of language processing), which can even be extended to n-gram features as a result we use n-gram feature codebooks. In a way similar to the pre-training stage of a DNN, feature codebooks are trained in an unsupervised manner, so as to minimize the mean square error of the training set, using k-means, or LindeBuzoGray clustering for example.

This stage provides a high dimensional symbolic feature codebook representation of the data (see Fig. 2). In the experiments described below, we explore the use of uni-gram, bi-gram and tri-gram feature codebooks.

Experiments

Discretization of frame level numerical features

An initial 70 continuous feature set has been designed, based on Histograms of Oriented Gradient (HOG) [START_REF] Rodriguez | Local gradient histogram features for word spotting in unconstrained handwritten documents[END_REF] extracted from each frame using a 8-pixels width sliding window. It is composed of 64 HOG features (8 directions from the frame divided into 2 columns × 4 rows), and 6 high level information features: the position of the vertical and horizontal centroids, the position of the highest and lowest black pixels in the frame, the distance between them, and the number of black pixels in the frame. This continuous representation is fed to the unsupervised clustering stage allowing the definition of a discrete codebook. In our experiments, we explore the use of uni-gram, bi-gram and tri-gram codebooks extracted respectively from 1, 2 and 3 consecutive frames. Using KMeans clustering, three different codebooks are generated, providing three discrete representation levels of the input numerical data (see Fig. 2). After a validation step, 1000, 2000 and 5000 clusters has been determined to be the optimal size for 1, 2 and 3 consecutive frames.

Finally, the CRF is fed with uni-gram, bi-gram and tri-gram codebooks in context:

-The unigram representation is composed of 9 cluster numbers (symbols): the current symbol and its 4 previous and next neighbours (I) -The bigram representation is composed of 3 cluster numbers (symbols) computed from frames [t, t + 1] and frames [t -1, t] (II) -The trigram representation is composed of 1 cluster numbers (symbols) computed from frames [t -1, t, t + 1] (III) We evaluated the following configurations: (I), (I+II) and (I+II+III) (see Table 1).

Results and Discussion

The CRF training converged in 80 iterations of 135s each (average value). We carried out the experiments on the public RIMES 2009 database of isolated words [START_REF] Grosicki | Icdar 2009 handwriting recognition competition[END_REF]. The participants were given about 43000 words snippets to train their system, and a validation database of more than 7000 words to test them. The unknown test dataset is composed of 7464 snippets. The system is evaluated on this test dataset with a lexicon of 1600 entries. The results of our experiment are summarized in Table 1. We provide the frame error rate (FER) in Top 1, and the word error rate (WER) in Top 1, Top 2, Top 3 and Top 5 of the whole system. It can be seen that the multi-scale feature set improves the performance of our system at frame and word level. We observe an enhancement of 1.6% at frame level and 6% at word level between the set of features without multiscaling information (I) and the set of features adding the bi-grams and tri-grams information. Figure 3 presents an example showing the ability of the model to perform a frame level recognition, and to retrieve the correct character alignment (shown in red) thanks to the HMM lexicon-driven decoding. Our best system achieves 69% word recognition (Top 1) which is under the best performance reported on this database. However, these are promising results if we look at the potential improvements of the method. From our point of view, one of the main limitation of the system is that the CRF is trained on a frame-labelled dataset obtained from an initial Viterbi forced-alignment using an initial trained HMM. This means that the CRF is trained to recognize characters, but not to segment them. Some improvements are expected by introducing a lexicon-based training procedure of the proposed hybrid architecture. As a result, recognition and segmentation could be trained in conjunction. In addition, such scheme would allow to avoid training an initial HMM. In order to avoid similar wrong recognition events, we have to keep working on our features, try to find a better representation of our data. A major uncertainty we are faced with, is that we do not know if the segmentation performed by the HMM is suitable for the CRF. This is why we intend to design a system in which the CRF could impact the labelling processing of each frame during the learning stage.In order to achieve this we could introduce a joint training of the whole system CRF/HMM. After training the CRF a first time, the HMM produces a new alignment on the learning database using the CRF outputs. This new labelled database is used to retrain a new CRF. This two step learning method is repeated until the system stops improving the word recognition rate. By using this training method, the CRF outputs impact the global result of the system, and are not a simple byproduct of it, therefore improving the recognition of the CRF/HMM system.

Last but not least, in our CRF training the criterion is based on frame recognition rate, they are not trained to perform word recognition directly. To infer this information we have to add the word level information of the HMM stage in the training criterion of the standard CRF.

Conclusion and future work

In this paper, we have proposed a hybrid CRF/HMM model to perform off-line omni-writer handwriting recognition. We showed the architecture has promising performance even if the recognition rate is still below the best performance of the literature obtained on the same database.

Further improvements are expected by introducing embedded training of the hybrid model allowing joint training of the CRF and the HMM stage to perform both segmentation and character recognition, bypassing the need of an initial labelling.

Another expected improvement lies in the optimization of the HMM structure including character duration.

Fig. 1 .

 1 Fig. 1. Hybrid structure CRF/HMM : Detail of every step of the whole hybrid structure from feature extraction to word recognition for the word et.

Fig. 2 .

 2 Fig. 2. Feature Extraction : Detail of every step during the feature extraction from the initial image to the final feature vector with multi-scale information of the word et.

Fig. 3 .

 3 Fig.3. Posteriors probabilities given by the CRF on the word "vos" and the alignment provide by the HMM.

  for further details see section 3.3 and 4.1).

	HMM			e	t
	Lexical and Language Constraints	e0	e1	e2	t0	t1	t2	t3
	CRF
	Posterior Probabilities	e : 0.8	e : 0.4	e : 0.5	t : 0.1	t : 0.1	t : 0.6	t : 0.6
	Extraction
	Clustering			xC1	...	xCn
	Feature
	Discretisation
				x1	...	xn
	HoG
	Feature
	Extraction

Table 1 .

 1 Results on Rimes database

	Features	FER Top 1 WER Top 1 WER Top 2 WER Top3 WER Top5
	HMM (standard HOG)	88.6 %	36 %	32 %	30 %	25 %
	CRF-HMM (I)	53.8 %	38 %	33 %	29 %	21 %
	CRF-HMM (I+II)	52.5 %	34 %	29%	25 %	18 %
	CRF-HMM (I+II+III)	51.2 %	31 %	29%	23 %	18 %
	BLSTM-HMM [4]	33.93	12.19%	x	x	x


Roberto Amadini

Maurizio Gabbrielli

Jacopo Mauro

An Enhanced Features Extractor for a Portfolio of Constraint Solvers

Keywords: I.2 [Computing Methodologies]: Artificial Intelligence-Constraint Programming, Machine Learning, Algorithm Portfolios

Recent research has shown that a single arbitrarily efficient solver can be significantly outperformed by a portfolio of possibly slower on-average solvers. The solver selection is usually done by means of (un)supervised learning techniques which exploit features extracted from the problem specification. In this paper we present an useful and flexible framework that is able to extract an extensive set of features from a Constraint (Satisfaction/Optimization) Problem defined in possibly different modeling languages: MiniZinc, FlatZinc or XCSP.

INTRODUCTION

It is well recognized within the field of Constraint Programming that different solvers are better when solving different problem instances, even within the same problem class [START_REF] Gomes | Algorithm portfolios[END_REF]. It has also been shown in other areas, such as SATisfiability testing and Integer Linear Programming that the best on-average solver can be out performed by a portfolio of possibly slower on-average solvers. A portfolio approach [START_REF] Gomes | Algorithm portfolios[END_REF] for constraint solving can be seen as a methodology that exploits the significant variety in performances observed in different algorithms and combines them in order to create a globally better solver, dubbed a portfolio solver. A crucial step for the performance of a portfolio solver is the selection of one or more solvers composing the portfolio for solving a specific problem instance. Such a selection process is usually performed by using Machine Learning techniques based on features extracted from the instances that need to be solved.

Although several portfolio approaches have been extensively studied and used in the SAT solving field (e.g. [START_REF] Xu | Evaluating Component Solver Contributions to Portfolio-Based Algorithm Selectors[END_REF][START_REF] Malitsky | Instance-Specific Algorithm Configuration as a Method for Non-Model-Based Portfolio Generation[END_REF]) to the best of our knowledge the only Constraint Satisfaction Problems (CSP) portfolio solver is CPHydra [START_REF] O'mahony | Using case-based reasoning in an algorithm portfolio for constraint solving[END_REF].

CPHydra deals with problems expressed only in the XCSP format [START_REF] Roussel | XML Representation of Constraint Networks: Format XCSP 2[END_REF], it uses a rather small portfolio (just 3 solvers) and exploits only a limited number of features (36 to be exact, extracted by using Mistral solver [START_REF] Mistral | [END_REF]). Even worse, we are not aware of a single portfolio solver for Constraint Optimization Problems (COPs). There are several reasons for the lack of CSP/COP portfolio solvers. First of all, the CSP/COP solving fields are more complex than SAT: constraints can be arbitrary complex (e.g. global constraints like regular or bin-packing) and some of them are supported by only a few solvers. Moreover, no standard input language nor immediately available big dataset exists for CSPs or COPs.

We deem that, at least from the implementation and tool development point of view, there is still a big gap between CSP/COP w.r.t. the SAT field. In this paper we then address this problem by presenting a framework that is able to extract an exhaustive set of 155 features from a CSP/COP instance specified in the MiniZinc format [START_REF] Nethercote | MiniZinc: Towards a Standard CP Modelling Language[END_REF] but supporting also other formats like XCSP and FlatZinc [START_REF] Becket | Specification of FlatZinc -Version 1[END_REF] through a simple pre-processing phase. Hopefully this framework will be the starting point for the development of future CSP/COP portfolio solvers that rely on the extracted features for their solver selection procedure.

FRAMEWORK

In this section we present the technical details of our framework by introducing its main ingredients: the compiler xcsp2mzn and the features extractor mzn2feat (which includes the parser fzn2feat). Moreover, we provide a summary of the set of features that mzn2feat can extract.

Note that we decided to use MiniZinc as primary source format of our tool because it is nowadays the most used, supported and general language to specify constraint problems. MiniZinc supports also optimization problems and is the source format used in the MiniZinc challenge [START_REF]MiniZinc Challenge[END_REF], the only surviving international competition to evaluate the performances of constraint solvers. Our framework however offers full compatibility with XCSP and FlatZinc. Indeed, on one hand, we developed a compiler xcsp2mzn for converting problem instances from XCSP to MiniZinc by preserving the most important global constraints. On the other hand, the feature extractor tool called mzn2feat supports natively the FlatZinc format and can extract the features from every FlatZinc model.

xcsp2mzn

While MiniZinc is nowadays the most used language to encode CSPs, XCSP was mainly used in the past for the International Constraint Solver Competition (ICSC) [START_REF]Third International CSP Solver Competition[END_REF], which ended in 2009. Nevertheless, the ICSC dataset is by far the biggest dataset of CSP instances existing today. Hence, in order to exploit such a dataset for building better portfolios, we developed a compiler from XCSP to MiniZinc. xcsp2mzn was developed by adapting x4g [START_REF] Morara | Solving XCSP problems by using Gecode[END_REF], a converter from XCSP to Gecode [START_REF]GECODE flatzinc[END_REF] used in particular to support the XCSP abridged notation. Since we focused mainly on CSP we did not consider XCSP extensions like weighted constraints or quantifiers over constraints. All the code is written in C++ using the well known libxml2 libraries. Exploiting the fact that MiniZinc is more expressive than XCSP (i.e. the majority of the primitive constraint of XCSP are also primitive constraints of MiniZinc) the translation was straightforward. The only notable difference was the compilation of extensional constraints (i.e. relations explicitly expressed in terms of all the allowed or not allowed tuples) which are a native feature in XCSP only. To overcome this limitation we used the table global constraint for encoding the allowed set of tuples and a conjunction of disjunctions of inequalities for mapping the forbidden set of tuples. As far as global constraints are concerned, XCSP supports the majority of the global constraints defined in the Global Constraint Catalog [START_REF] Beldiceanu | Global Constraint Catalogue: Past, Present and Future[END_REF]. Since in this catalog there are hundreds of global constraints, for simplicity we decided to support only the subset of the global constraints used in the ICSC.

mzn2feat

The tool mzn2feat allows to extract from a MiniZinc model a set of 155 features: 144 are static features obtained by parsing the source problem instance, while 11 are dynamic and are obtained by running the Gecode solver for a short run. Since the complexity of the MiniZinc language (in particular the possibility of using control flow statements) makes the extraction of the syntactical features quite difficult, we decided to not process directly the MiniZinc instances. We instead compile them to FlatZinc [START_REF] Nethercote | Converting MiniZinc to FlatZinc[END_REF], a lower level language having a syntax that is mostly a subset of MiniZinc and that can be obtained from MiniZinc by using the mzn2fzn tool provided by the MiniZinc suite. The compilation to FlatZinc was performed using the Gecode redefinitions for global constraints. This allowed us to keep track of how and what global constraints are used without decomposing them. 1 To extract the static features we developed a parser, called fzn2feat, using the standard Flex and Bison tools. The dynamic features were collected instead launching Gecode interpreter fz for 2 seconds runs.

Summarizing, given a generic MiniZinc model M in input, mzn2feat does the following: i) first, translates M into the corresponding FlatZinc FM specification by using Gecode global redefinitions; ii) extracts static features from FM by means of fzn2feat; iii) extracts dynamic features from FM by running the fz interpreter of Gecode for 2 seconds. We remark that step ii) is applicable to every FlatZinc model F (possibly ignoring the unknown solver-specific redefinitions). Moreover, steps ii) and iii) are totally inde-pendent and therefore they could be parallelized or done in reverse order. For instance, it could be useless to compute the static features if the given instance is solved by Gecode while trying to compute the dynamic features.

Features description

In this section we present an overview of the numeric features extracted by mzn2feat; for a more detailed description we defer the interested reader to [START_REF] Amadini | Features for Building CSP Portfolio Solvers[END_REF]. mzn2feat tries to collect a set of features as exhaustive and general as possible, taking inspiration from and adapting those presented in [START_REF] Hutter | Algorithm Runtime Prediction: The State of the Art[END_REF][START_REF] Arbelaez | Continuous Search in Constraint Programming[END_REF]. Although some of these features are quite generic (e.g., the number of variables or constraints), others are specific to FlatZinc (e.g. search annotations) or to Gecode (the global constraints features). For more details about these technicalities please see [START_REF] Nethercote | Converting MiniZinc to FlatZinc[END_REF][START_REF] Becket | Specification of FlatZinc -Version 1[END_REF][START_REF]GECODE flatzinc[END_REF].

Static Features

Thanks to fzn2feat we are able to extract 144 static features grouped in the different categories listed below. In the following we will denote with N V the number of variables and with N C the number of constraints of a given problem. Moreover, we will denote respectively by min, max, avg, CV, and H the minimum, maximum, average, variation coefficient and entropy of a set of values.

Variables (27): the number of variables N V ; the number cv of constants; the number av of aliases; the ratio av+cv N V ; the ratio N V N C ; the number of defined variables (i.e. defined as a function of other variables); the number of introduced variables (i.e. auxiliary variables introduced during the FlatZinc conversion); sum, min, max, avg, CV, and H of the: variables domain size, variables degree, domain size to degree ratio.

Domains [START_REF] Roussel | XML Representation of Constraint Networks: Format XCSP 2[END_REF]: the number of: boolean variables bv and the ratio bv N V ; float variables f v and the ratio f v N V ; integer variables iv and the ratio iv N V ; set variables sv and the ratio sv N V ; array constraints ac and the ratio ac N C ; boolean constraints bc and the ratio bc N C ; int constraints ic and the ratio ic N C ; float constraints f c and the ratio f c N C ; set constraints sc and the ratio sc N C . Constraints (27): the total number of constraints N C, the ratio N C N V , the number of constraints using specific FlatZinc annotations; the logarithm of the product of the: constraints domain2 and constraints degree; sum, min, max, avg, CV, and H of the: constraints domain, constraints degree, domain to degree ratio.

Global Constraints (29): the total number gc of global constraints, the ratio gc N C and the number of global constraints for each one of the 27 equivalence classes in which we have grouped the 47 global constraints that Gecode natively supports.

Graphs (20): once built the Constraint Graph CG and the Variable Graph VG we compute min, max, avg, CV, and H of the: CG nodes degree, CG nodes clustering coefficient, VG nodes degree, VG nodes diameter.

Dynamic features

For each problem we extract the following 11 dynamic features: the number of solutions found; the number p of propagations performed; the ratio p N C ; the number e of nodes expanded in the search tree; the number f of failed nodes in the search tree; the ratio f e ; the maximum depth of the search stack; the peak memory allocated; the CPU time needed for converting from MiniZinc to FlatZinc; the CPU time required for static features computation; the total CPU time needed for extracting all the features.

The first 8 features are collected by mzn2feat executing short runs (2 seconds) of Gecode fz interpreter with default parameters and -s and -time options. The last 3 are instead timing features computed by means of the time command of the Unix Bash shell.

CONCLUSIONS AND EXTENSIONS

In this work we presented a framework that is able to extract an extensive set of features from both satisfaction and optimization problems defined in possibly different modeling languages: MiniZinc, FlatZinc or XCSP. We deem that our work could serve as a building block for the creation of a modern constraint solver adopting a portfolio approach.

Indeed, it should be pretty straightforward to build a CSP portfolio solver exploiting the features extracted by mzn2feat: the only requirement is that each constituent solver of the portfolio must support MiniZinc format.

The set of features we propose was tested using the best CSP portfolio approaches [START_REF] Amadini | An Empirical Evaluation of Portfolios Approaches for Solving CSPs[END_REF]. Preliminary empirical results presented in [START_REF] Amadini | Features for Building CSP Portfolio Solvers[END_REF] show that portfolio techniques exploiting the new set of features are effective and competitive with state of the art CSP portfolio techniques.

An interesting future direction of this work concerns the improvement of the quality of the features, possibly though appropriate feature filtering techniques. Our framework is flexible enough to allow without a great effort to add new features (e.g. dynamic features computed using local search algorithm as done by SATzilla [START_REF] Xu | SATzilla-07: The Design and Analysis of an Algorithm Portfolio for SAT[END_REF]) as well as to select a proper subset of them as done in [START_REF] Kroer | Feature filtering for instance-specific algorithm configuration[END_REF] for SAT and CP problems.

Since mzn2feat is able to process COPs encoded in MiniZinc format, one of the most promising extension of our work is to assemble and analyze portfolios of COP solvers. In our opinion the effectiveness of portfolios in the satisfaction field can also be reflected in the world of combinatorial optimization. Of course, in order to evaluate a COP solver new metrics should also be considered. In fact, often in real world

3

  Solving (11): the number of labeled variables (i.e. the variables to be assigned); the solve goal; the number of search annotations; the number of variable choice heuristics; the number of value choice heuristics.Objective (12): 4 the domain dom, the degree deg, the ratios dom deg and deg N C of the variable v that has to be optimized; the degree de of v in the variable graph, its diameter di, de di , and di de . Moreover, named µ dom and σ dom the mean and the standard deviation of the variables domain size and µ deg and σ deg the mean and the standard deviation of the variables degree, we compute dom µ dom , deg µ deg , dom-µ dom

		σ dom	, and
	deg-µ deg σ deg	.

Without using solver specific redefinitions, during the compilation process some global constraints are indeed decomposed into basic constraints. For instance the alldifferent global constraint is decomposed by default into a conjunction of inequalities, from which it is impossible to uniquely recover the original global constraint.

We define the domain of a constraint as the product of the domains size of each variable that occurs in such constraint.

With diameter of a node x we mean the maximum among the minimum distances between x and each other different node y = x.

These features make sense only for optimization problems, a default value is given in case of satisfaction problems.it is better to get a good solution in a short time rather than consume too much time to find the optimal value. Starting from this assumption, it may be reasonable to develop new kinds of portfolio approaches that take into consideration also the solution quality.


Mila Dalla Preda

Saverio Giallorenzo

Ivan Lanese

Jacopo Mauro

Maurizio Gabbrielli

AIOCJ: A Choreographic Framework for Safe Adaptive Distributed Applications

We present AIOCJ, a framework for programming distributed adaptive applications. Applications are programmed using AIOC, a choreographic language suited for expressing patterns of interaction from a global point of view. AIOC allows the programmer to specify which parts of the application can be adapted. Adaptation takes place at runtime by means of rules, which can change during the execution to tackle possibly unforeseen adaptation needs. AIOCJ relies on a solid theory that ensures applications to be deadlock-free by construction also after adaptation. We describe the architecture of AIOCJ, the design of the AIOC language, and an empirical validation of the framework.

Introduction

Adaptation is a main feature of current distributed applications, that should live for a long time in a continuously changing environment. Anticipating all the possible adaptation needs when designing an application is very difficult, thus the approaches able to cope with unforeseen adaptation needs are the most interesting. Also, for distributed applications like the ones that we consider, it is important to ensure deadlock-freedom (according to [START_REF] Lu | Learning from mistakes: a comprehensive study on real world concurrency bug characteristics[END_REF] about one third of concurrency bugs in real applications are deadlocks). While many techniques ensuring deadlock freedom exist in the literature, e.g., [START_REF] Carbone | Deadlock-Freedom-by-Design: Multiparty Asynchronous Global Programming[END_REF][START_REF] Gößler | Component-Based Construction of Deadlock-Free Systems[END_REF][START_REF] Naik | Effective static deadlock detection[END_REF], to the best of our knowledge, none of them deals with adaptive applications. Indeed, most of the approaches to adaptation offer no guarantee on the behaviour of the application after adaptation [START_REF] Lanese | A Framework for Rule-Based Dynamic Adaptation[END_REF][START_REF] Bucchiarone | Dynamic Adaptation of Fragment-Based and Context-Aware Business Processes[END_REF][START_REF] Chen | Constructing Adaptive Software in Distributed Systems[END_REF], or they assume to know all the possible adaptations in advance [START_REF] Zhang | Modular Verification of Dynamically Adaptive Systems[END_REF], thus failing to cope with unforeseen adaptation needs.

Here we present AIOCJ, a prototype implementation of a framework for programming adaptive distributed applications that guarantees deadlock-freedom by construction (the theoretical foundations ensuring this property are discussed in [START_REF] Dalla Preda | Deadlock Freedom by Construction for Distributed Adaptative Applications[END_REF]). AIOCJ is composed of two parts: (i) a domain-specific language, called Adaptive Interaction-Oriented Choreographies (AIOC) and (ii) an adaptation middleware that supports adaptation of AIOC programs.

The AIOC language describes applications from a global point of view following the choreography paradigm. This paradigm has been applied in different contexts, see, e.g., [START_REF] Carbone | Deadlock-Freedom-by-Design: Multiparty Asynchronous Global Programming[END_REF][START_REF] Carbone | Structured communication-centered programming for web services[END_REF][START_REF]Scribble website[END_REF][START_REF] Lanese | Bridging the Gap between Interactionand Process-Oriented Choreographies[END_REF][START_REF]World Wide Web Consortium, Web Services Choreography Description Language Version 1.0[END_REF]], but we are not aware of other tools based on it and targeting adaptive applications. A choreography defines the interactions among the processes of a distributed application. AIOC main innovation consists in two constructs supporting adaptation: scopes and adaptation rules. A scope delimits code that may be adapted in the future. An adaptation rule provides new code to replace the one in a given scope. Interestingly, in AIOCJ, adaptation rules can be defined and inserted in the framework while the application is running, to cope with adaptation needs which were not foreseen when the application was designed or even started.

The code below shows a toy AIOC program (left) and an adaptation rule applicable to it (right). On the left, Lines 2-4 define a scope in which the local variable msg of process user is set to "Hello World". The keyword prop defines properties of the scope (prefixed by N). In this case, the name property is set to "hello_world". At Line 5 user sends the content of msg to a second process (display), that stores it in its local variable msg. On the right, Lines 2-3 define the applicability condition of the rule, i.e., the name property of the scope should be set to "hello_world", and the environmental property E.lang should be equal to "it". Line 4 shows the code that will replace the one of the scope, i.e., variable msg of user will be set to "Ciao Mondo" (Italian for "Hello World").

1 aioc { 2 scope @ user { 3 msg @ user = " Hello World " 4 } prop { N. name = " hello_world " } ; 5 send : user ( msg ) -> display ( msg ) } 1 rule { 2 on { N. name == " hello_world " 3 and E. lang == " it " } 4 do { msg @ user = " Ciao Mondo " } 5 }
An AIOC program describes a full distributed application. AIOCJ generates, for each distributed process, a service written in Jolie [START_REF]Jolie website[END_REF][START_REF] Montesi | Composing services with JOLIE[END_REF], a Service-Oriented orchestration language.

The adaptation middleware consists of a set of adaptation rules stored in multiple, possibly distributed, adaptation servers, and of an adaptation manager that mediates the interactions between the adaptive application and the various adaptation servers.

Structure of the paper. Section 2 presents an overview of the AIOCJ framework, while Section 3 describes its implementation. Section 4 shows a preliminary validation of the framework, with tests on the performances of AIOCJ. In Section 5 we discuss related work and future directions of research. A short demo of the use of the framework is available in the companion technical report [START_REF] Dalla Preda | AIOCJ: A Choreographic Framework for Safe Adaptive Distributed Applications[END_REF].

2 Overview: The AIOCJ framework This section first defines the architectural model that supports adaptation of AIOCJ applications and then it introduces the syntax of the AIOC language via an example (for a formal presentation of AIOC syntax and semantics see [START_REF] Dalla Preda | Deadlock Freedom by Construction for Distributed Adaptative Applications[END_REF]). The AIOCJ middleware. We consider applications composed of processes deployed as services on different localities, including local state and computational resources. Each process has a specific duty in the choreography and follows a given protocol. Processes interact via synchronous message passing over channels, also called operations. Adaptation is performed by an adaptation middleware including an adaptation manager and some, possibly distributed, adaptation servers. The latter are services that act as repositories of adaptation rules and may be (manually) added or removed at runtime. Running adaptation servers register themselves on the adaptation manager. The running application may interact with the adaptation manager to look for applicable adaptation rules. The effect of an adaptation rule is to replace a scope with new code that answers a given adaptation need. The adaptation manager checks the rules according to the registration order of the adaptation servers, returning the first applicable rule, if any. The AIOC Language. The language relies on a set of roles that identify the processes in the choreography. Let us introduce the syntax of the language using an example where Bob invites Alice to see a film. end @ bob = false ; while ( ! end ) @ bob { scope @ bob { free_day @ bob = getInput ( " Insert your free day " ) ; proposal : bob ( free_day ) -> alice ( bob_free_day ) ; is_free @ alice = isFreeDay ( bob_free_day ); } prop { N. scope_name = " matching day " } ; if ( is_free ) @ alice { scope @ bob { proposal : bob ( " cinema " ) -> alice ( event ) ; agreement @ alice = getInput ( " Bob proposes " + event + " , do you agree ?[ y / n ] " ) ; if ( agreement == " y " ) @ alice { end @ bob = true ; book : bob ( bob_free_day ) -> cinema ( book_day ) ; ticket @ cinema = getTicket ( book_day ); { notify : cinema ( ticket ) -> bob ( ticket ) | notify : cinema ( ticket ) -> alice ( ticket ) }} } prop { N. scope_name = " event selection " } } ; if ( ! end )@ bob { _r @ bob = getInput ( " Alice refused . Try another date ?[ y / n ] " ) ; if ( _r != " y " ) @ bob { end @ bob = true }}} Listing 1.1: Appointment program.

The code starts with some deployment information (Lines 1-7), discussed later on. The behaviour starts at Line 9. The program is made by a cycle where Bob first checks when Alice is available and then invites her to the cinema. Before starting the cycle, Bob initialises the variable end, used in the guard of the cycle, to the boolean value false (Line 9). Note the annotation @bob meaning that end is local to Bob. The first instructions of the while are enclosed in a scope (Lines 11-15), meaning that they may be adapted in the future. The first operation within the scope is the call to the primitive function getInput that asks to Bob a day where he is free and stores this date into the local variable free_day. At Line 13 the content of free_day is sent to Alice via operation proposal. Alice stores it in its local variable bob_free_day. Then, at Line 14, Alice calls the external function isFreeDay that checks whether she is available on bob_free_day. If she is available (Line 16) then Bob sends to her the invitation to go to the cinema via the operation proposal (Line 18). Alice, reading from the input, accepts or refuses the invitation (Line 19). If Alice accepts then Bob first sets the variable end to true to end the cycle. Then, he sends to the cinema the booking request via operation book. The cinema generates the tickets using the external function getTicket and sends them to Alice and Bob via operation notify. The two notifications are done in parallel using the parallel operator | (until now we composed statements using the sequential operator ;). Lines 18-26 are enclosed in a second scope with property N.scope_name = "event selection". If the agreement is not reached, Bob decides, reading from the input, if he wants to stop inviting Alice. If so, the program exits.

We remark the different meanings of the annotations @bob and @alice. When prefixed by a variable, they identify the owner of the variable. Prefixed by the boolean guard of conditionals and cycles, they identify the role that evaluates the guard. Prefixed by the keyword scope, they identify the process coordinating the adaptation of that scope. A scope, besides the code, may also include some properties describing the current implementation. These can be specified using the keyword prop and are prefixed by N. For instance, each scope of the example includes the property scope_name, that can be used to distinguish its functionality.

AIOCJ can interact with external services, seen as functions. This allows both to interact with real services and to have easy access to libraries from other languages. To do that, one must specify the address and protocol used to interact with them. For instance, the external function isFreeDay used in Line 14 is associated to the service deployed at the domain "calendar.org", reachable though port 80, and that uses http as serialisation protocol (Line 1). External functions are declared with the keyword include. To preserve deadlock freedom, external services must be non-blocking. After function declaration, in a preamble section, it is possible to declare the locations where processes are deployed. The keyword starter is mandatory and defines which process must be started first. The starter makes sure all other processes are ready before the execution of the choreography begins. Now suppose that Bob, during summer, prefers to invite Alice to a picnic more than to the cinema, provided that the weather forecasts are good. This can be obtained by adding the following adaptation rule to one of the adaptation servers. This may even be done while the application is running, e.g., while Bob is sending an invitation. In this case, if the first try of Bob is unsuccessful, in the second try he will propose a picnic. eventProposal : bob ( " picnic " ) -> alice ( event ) 7

} else { eventProposal : bob ( " cinema " ) -> alice ( event ) } ; 8 agreement @ alice = getInput ( " Bob proposes " + event + 9 " , do you agree ?[ y / n ] " ) ; if ( agreement == " y " ) @ alice { end @ bob = true | if ( event == " cinema " ) @ alice { / / c i n e m a t i c k e t s p u r c h a s e p r o c e d u r e }}}} Listing 1.2: Event selection adaptation rule.

A rule specifies its applicability condition and the new code to execute. In general, the applicability condition may depend only on properties of the scope, environment variables, and variables belonging to the coordinator of the scope. In this case, the condition, introduced by the keyword on (Line 3), makes the rule applicable to scopes having the property scope_name equal to the string "event selection" and only during summer. This last check relies on an environment variable month that contains the current month. Environment variables are prefixed by E.

When the rule applies, the new code to execute is defined using the keyword do (Line 4). In this case, the forecasts can be retrieved calling an external function getWeather (Line 4) that queries a weather forecasts service. This function is declared in Line 2. If the weather is clear, Bob proposes to Alice a picnic, the cinema otherwise. Booking (as in Listing 1.1, Lines 23-26) is needed only if Alice accepts the cinema proposal.

As detailed in [START_REF] Dalla Preda | Deadlock Freedom by Construction for Distributed Adaptative Applications[END_REF], to obtain a deadlock-free application, we require the code of choreographies and rules to satisfy a well-formedness syntactic condition called connectedness. Intuitively, connectedness ensures that sequences of actions are executed in the correct order and avoids interference between parallel interactions. Requiring this condition does not hamper programmability, since it naturally holds in most of the cases, and it can always be enforced automatically via small patches to the choreography which preserve the behaviour of the program, as discussed in [START_REF] Lanese | Amending choreographies[END_REF]. Also, checking connectedness is efficient, i.e., polynomial w.r.t. the size of the code [START_REF] Dalla Preda | Deadlock Freedom by Construction for Distributed Adaptative Applications[END_REF].

Implementation

Our prototype implementation of AIOCJ is composed of two elements: the AIOCJ Integrated Development Environment (IDE), named AIOCJ-ecl, and the adaptation middleware that enables AIOC programs to adapt, called AIOCJ-mid.

AIOCJ-ecl is a plug-in for Eclipse [START_REF]Eclipse website[END_REF] based on Xtext [START_REF]Xtext website[END_REF]. Xtext provides features such as syntax highlighting, syntax checking, and code completion, which help developers in writing choreographies and adaptation rules. Also, starting from a grammar, Xtext generates the parser for programs written in the AIOC language. Result of the parsing is an abstract syntax tree (AST) we use to implement (i) the checker for connectedness for choreographies and rules and (ii) the generation of Jolie code for each role. The connectedness check has polynomial computational complexity [START_REF] Dalla Preda | Deadlock Freedom by Construction for Distributed Adaptative Applications[END_REF] thus making it efficient enough to be performed on-the-fly while editing the code.

The target language of code generation is Jolie [START_REF]Jolie website[END_REF]. Jolie supports architectural primitives such as dynamic embedding, aggregation, and redirection that we exploit to implement the adaptation mechanisms. Moreover, Jolie supports a wide range of communication technologies (TCP/IP sockets, local memory, Bluetooth) and of data formats (e.g., HTTP, SOAP, JSON). AIOCJ inherits this ability. The compilation generates a Jolie service for each role. The execution of scopes is delegated to sub-services accessed using Jolie redirection facility. Adaptation is enacted by disabling the current sub-service and replacing it with a new one, obtained from the adaptation server.

To grant to all the sub-services access to variables, the state is stored by a dedicated sub-service local to the role. Auxiliary messages are exchanged to ensure that both the adaptation and the choices taken by the if and while constructs are done in a coordinated way. In particular, the scope execution not only requires interaction with the adaptation manager, but also communications among the different roles, ensuring that they all agree on whether adaptation is needed or not, and, in case, on which rule to apply. Indeed, the decision is taken by the role coordinating the adaptation and then communicated to other roles. Note that the different roles cannot autonomously take the decision, since if they take it at different times, changes in the environment or in the sets of available rules may lead to inconsistent decisions.

Synchronous message exchange is implemented on top of an asynchronous communication middleware by a sub-service that works as a message handler. The message handler of the starter role also ensures that, before the actual communication in the choreography starts, all the roles are ready.

AIOCJ-mid is implemented in Jolie and it includes:

many, possibly distributed, adaptation servers where rules are published. Adaptation servers can be deployed and switched on and off at runtime; an adaptation manager that acts as a registry for adaptation servers and clients; an environment service that stores and makes available environment information.

Environment information can change at any moment.

When an AIOCJ program reaches a scope, it queries the adaptation manager for a rule matching that scope. The adaptation manager queries each adaptation server sequentially, based on their order of registration. Each server checks the applicability condition of each of its rules. The first rule whose applicability condition holds is applied. In particular, the code of the rule is sent to the role coordinating the adaptation (via the adaptation manager) which distributes it to the involved roles. In each role, the new code replaces the old one. The study of more refined policies for rule selection, e.g., based on priorities, is a topic for future work.

Validation

In this section, we give a preliminary empirical validation of our implementation. The main aim is to test how our mechanisms for adaptation impact on performances.

In the literature, to the best of our knowledge, there is no approach to adaptation based on choreography programming. Thus, it is difficult to directly compare our results with other existing approaches. Moreover, we are not aware of any established benchmark to evaluate adaptive applications. For this reason, we tested AIOCJ performances by applying it to two typical programming patterns: pipes and fork-joins. Since we are interested in studying the cost of adaptation, our scenarios contain minimal computation and are particularly affected by the overhead of the adaptation process. Clearly, the percentage of the overhead due to adaptation will be far lower in real scenarios, which are usually more computationally intensive. In the first scenario, we program a pipe executing n tasks (in a pipe, the output of task t i is given as input to task t i+1 , for i ∈ {1, . . . , n -1}). To keep computation to a minimum, each task simply computes the increment function. In the fork-join scenario, n tasks are computed in parallel. Each task processes one character of a message of length n, shifting it by one position. The message is stored in an external service. 3 To enable adaptation, each task is enclosed in a scope. We test both scenarios with an increasing number of tasks n ∈ {10, 20, . . . , 100} to study how performances scale as the number of adaptation scopes increases. We evaluate performances in different contexts, thus allowing us to understand the impact of different adaptation features, such as scopes, adaptation servers, and adaptation rules. 3 The code of both scenarios is in the companion technical report [START_REF] Dalla Preda | AIOCJ: A Choreographic Framework for Safe Adaptive Distributed Applications[END_REF]. q q q q q q q q q q 0 20000 40000 60000 80000 q q q q q q q q q q 0 1000 3000 5000 7000 Context 1: no scopes, no adaptation servers, no rules; Context 2: each task is enclosed in a scope, no adaptation servers, no rules; Context 3: each task is enclosed in a scope, one adaptation server, no rules; Context 4: as Context 3, but now the adaptation server contains 50 rules. Each rule is applicable to a unique scope i, and no rule is applicable to scopes with i > 50. The rules are stored in random order. Context 5: as Context 4, but with 100 rules, one for each scope.

Pipe

Fork-Join

Each rule in Contexts 4 and 5 is applicable to one specific scope only (through a unique property of the scope), hence when testing for 50 rules, only the first 50 scopes adapt.

We repeated every test 5 times. We performed our tests on a machine equipped with a 2.6GHz quad-core Intel Core i7 processor and 16GB RAM. The machine runs Mavericks 10.9.3, Java 1.7.55, and Jolie r.2728. Figure 1 shows the tests for the pipe (left) and the fork-join (right). Both charts display on the x-axis the number of tasks/scopes and on the y-axis the execution time in milliseconds.

As expected, in both scenarios there is a significant gap between Contexts 1 and 2. In words, the introduction of scopes has a strong effect on performances. The ratio is 1:13 for the pipe scenario and 1:5.5 for the fork-join scenario. This is due to the auxiliary communications needed to correctly execute a scope. The observed overhead is higher in the pipe scenario, since different scopes check for adaptation in sequence, while this is done in parallel for the fork-join scenario.

Adding an adaptation server (from Context 2 to Context 3) has little impact on performances: 19% of decay for pipe, and 17% for fork-join. The figures are reasonable, considered that Context 3 adds only one communication w.r.t. Context 2.

On the contrary, there is a notable difference when adding rules to the adaptation server (Context 4 is 1.4 times slower than Context 3 for the pipe scenario, 2.9 for the fork-join scenario). In Contexts 4 and 5, performances are really close up to 50 scopes (in the pipe scenario they almost overlap) although Context 5 has twice the rules of Context 4. This illustrates that the time to test for applicability of rules is negligible.

Hence, the highest toll on performances is related to actual adaptation, since it requires to transfer and embed the new code. This is particularly evident in the fork-join scenario where multiple adaptations are executed in parallel and the adaptation server becomes a bottleneck. This problem can be mitigated using multiple distributed adaptation servers.

The fact that the most expensive operations are scope execution and actual adaptation is highlighted also by the results below. The table shows the cost of different primitives, including scopes in different contexts. Times are referred to 5 executions of the sample code in the companion technical report [START_REF] Dalla Preda | AIOCJ: A Choreographic Framework for Safe Adaptive Distributed Applications[END_REF]. As future work we will exploit these results to increase the performances of our framework, concentrating on the bottlenecks highlighted above. For instance, scope execution (as well as conditionals and cycles) currently requires many auxiliary communications ensuring that all the processes agree on the chosen path. In many cases, some of these communications are not needed, since a process will eventually discover the chosen path from the protocol communications. Static analysis can discover redundant communications and remove them. Another improvement is letting the adaptation server send the new code directly to the involved roles, skipping the current forward chain.

Related Work & Conclusion

This paper presented a framework for programming rule-based adaptation of distributed applications. Its distinctive trait is that, being based on a choreographic approach, it guarantees deadlock-freedom by construction for the running distributed application, even in presence of adaptation rules which were unknown when the application was started, and for any environment condition. Adaptation is a hot topic, and indeed there is a plethora of approaches in the literature, see, e.g., the surveys [START_REF] Ghezzi | An evaluation of the adaptation capabilities in programming languages[END_REF][START_REF] Leite | A systematic literature review of service choreography adaptation[END_REF]. However, approaches based on formal methods are only emerging recently and few of them have been implemented in a working tool. In particular, the use of choreographies to capture and define adaptive applications is a novel idea. For a discussion of works on adaptation with formal bases, but which have not been implemented, we refer to [START_REF] Dalla Preda | Deadlock Freedom by Construction for Distributed Adaptative Applications[END_REF]. Here, we just recall [START_REF] Coppo | Self-adaptive monitors for multiparty sessions[END_REF], which exploits a choreographic approach for self-adaptive monitoring of distributed applications.

Among the implemented approaches, the most related to ours is JoRBA [START_REF] Lanese | A Framework for Rule-Based Dynamic Adaptation[END_REF]. JoRBA features scopes and adaptation rules similar to ours. However, JoRBA applications are not distributed and JoRBA does not guarantee any property of the adapted application.

In [START_REF] Rinderle | Evolution of Process Choreographies in DY-CHOR[END_REF] choreographies are used to propagate protocol changes to the other peers, while [START_REF] Wombacher | Alignment of choreography changes in BPEL processes[END_REF] presents a test to check whether a set of peers obtained from a choreography can be reconfigured to match a second one. Differently from ours, these works only provide change recommendations for adding and removing message sequences.

Various tools [START_REF] Cugola | DSOL: a declarative approach to self-adaptive service orchestrations[END_REF][START_REF] Baresi | Corrective Evolution of Adaptable Process Models[END_REF][START_REF] Bucchiarone | On-the-Fly Adaptation of Dynamic Service-Based Systems: Incrementality, Reduction and Reuse[END_REF] exploit automatic planning techniques in order to elaborate, at runtime, the best sequence of activities to achieve a given goal. These techniques are more declarative than ours, but, to the best of our knowledge, they are not guaranteed to always find a plan to adapt the application.

Among the non-adaptive languages, Chor [START_REF] Carbone | Deadlock-Freedom-by-Design: Multiparty Asynchronous Global Programming[END_REF] is the closest to ours. Indeed, like ours, Chor is a choreographic language that compiles to Jolie. Actually, AIOCJ shares part of the Chor code base. However, due to the different semantics of the sequential operator and the lack of the parallel composition in Chor, a faithful encoding of the scenarios in Section 4 is not possible, especially for the fork-join scenario. On an almost equivalent implementation of the pipe scenario, Chor proves to be more efficient than AIOCJ.

In the future, we would like to test the expressive power of our language, trying to encode patterns of adaptation from existing approaches. An obvious benefit of such an encoding is that it will capture patterns of adaptation used in real-case scenarios, guaranteeing also deadlock freedom, which is not provided by other approaches. This task is cumbersome, due to the huge number and heterogeneity of those approaches. Nevertheless, we already started it. In particular, in the website [START_REF]AIOCJ website[END_REF], we show how to encode examples coming from distributed [START_REF] Pawlak | JAC: an aspect-based distributed dynamic framework[END_REF] and dynamic [START_REF] Yang | An aspect-oriented approach to dynamic adaptation[END_REF] Aspect-Oriented Programming (AOP) and from Context-Oriented Programming (COP) [START_REF] Hirschfeld | Context-oriented Programming[END_REF]. In general, we can deal with cross-cutting concerns like logging and authentication, typical of AOP, viewing point-cuts as empty scopes and advices as adaptation rules. Layers, typical of COP, can instead be defined by adaptation rules which can fire according to contextual conditions captured by the environment. Possible extensions of our framework include the use of asynchronous communications in the AIOC language and the introduction of mechanisms to deal with exceptions and failures. Finally, we would like to pursue a systematic analysis of the workflow change patterns like the ones presented in [START_REF] Weber | Change Patterns and Change Support Features in Process-Aware Information Systems[END_REF][START_REF] Casati | Workflow Evolution[END_REF], showing how these patterns are captured by AIOCJ.

Fig. 1 :

 1 Fig. 1: Times of execution of the pipe (left) and the fork-join (right) scenarios