Modou Gueye

Hubert Naacke

A cluster-based matrix-factorization for online integration of new ratings

Les techniques de factorisation de matrice offrent une bonne qualité de prédiction pour les systèmes de recommandation, ce qui explique l'engouement qu'elles succitent depuis quelques années. Cependant, leur coût de calcul élevé constitue un obstacle à leur utilisation dans des contextes dynamiques, où les avis des utilisateurs sur des produits sont générés de façon continue. L'integration de nouvelles évaluations de produits est nécéssaire pour maintenir une bonne qualité de prédiction. Mais, ceci nécessite une refactorisation de la matrice à chaque fois que de nouvelles évaluations sont disponibles, ce qui est impossible de faire. Ce papier propose une solution qui permet de ralentir la dégradation des prédictions entre deux factorisations, en gérant des biais par utilisateur. La prise en compte de nouvelles évaluations se fait au niveau des biais avec un coût assez faible. Les expériences menées sur des jeux de données réels confirment notre analyse et montrent l'efficacité de notre solution.

It is today accepted that matrix factorization models allow a high quality of rating prediction in recommender systems. However, a major drawback of matrix factorization is its static nature that results in a progressive declining of the accuracy of the predictions after each factorization. This is due to the fact that the new obtained ratings are not taken into account until a new factorization is computed, which can not be done very often because of the high cost of matrix factorization. In this paper, aiming at improving the accuracy of recommender systems, we propose a cluster-based matrix factorization technique that enables online integration of new ratings. Thus, we significantly enhance the obtained predictions between two matrix factorizations. The experiments we did on a large dataset demonstrated the efficiency of our approach. Furthermore, we devise an experimental protocol that allows for identifying the optimal number of ratings to take into account for factorization. This contributes as a practical solution addressing the tradeoff between taking into account more ratings into factorization for better quality, versus missing fewer ratings during factorization.

Introduction

Due to their great commercial value, recommender systems attract a lot of attention [START_REF] Dias | The value of personalised recommender systems to e-business: a case study[END_REF][START_REF] Jannach | A case study on the effectiveness of recommendations in the mobile internet[END_REF][START_REF] Linden | Industry report: Amazon.com recommendations: Itemto-item collaborative filtering[END_REF][START_REF] Fleder | Recommender systems and their impact on sales diversity[END_REF]. Their purpose is to predict user preferences on a huge selection of items, i.e. find items that are likely to be of interest for the user. Because the user is often overwhelmed for facing the considerable amount of items provided by electronic retailers, the predictions are a salient function of all types of e-commerce [START_REF] Schafer | Recommender systems in e-commerce[END_REF][START_REF] Bell | The million dollar programming prize[END_REF]. Collaborative filtering is a widely used category of recommender systems. It consists in analyzing relationships between users and interdependencies among items to identify new user-item associations [START_REF] Su | A survey of collaborative filtering techniques[END_REF][START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF][START_REF] Paterek | Improving regularized singular value decomposition for collaborative filtering[END_REF]. Based on these associations, recommendations are inferred.

One of the most successful collaborative filtering algorithms is matrix factorization (MF), which has proved its good scalability and predictive accuracy [START_REF] Takács | Scalable collaborative filtering approaches for large recommender systems[END_REF][START_REF] Koren | The bellkor solution to the netflix grand prize[END_REF]. In its basic form, matrix factorization profiles both items and users by vectors of factors inferred from rating patterns. High correspondence between item and user factors leads to a recommendation. Although matrix factorization is very popular because of its proven qualities, some shortcomings remain. One of these is the fact that the model generated by MF is static. Once it has been generated the model delivers recommendations based on a snapshot of the incoming ratings frozen at the beginning of the generation. To take into account the missing ratings (those arrived after the last model generation), the model have to be computed periodically. However, it is not realistic to carry it out frequently, because of the high cost of model recomputation. Therefore, the quality of the recommendations will decrease gradually until a new model is computed.

In real-world context where new ratings happen continuously, users profile evolve dynamically. Consider, for instance, a costumer of an online music-store looking for good pop songs. He asks the application for some recommendations and the system proposes to him a short list of songs with high probability of interest (based on the latest available model). The costumer selects and rates the songs he already knows or he just listened to, and asks for new recommendations. Since the preferences of the customers evolve accordingly to the songs they have listened to, it is important to be able to integrate the new ratings for the subsequent recommendations (including those provided for the customers having a similar profile). Otherwise, the following recommendations will be unnecessary.

In this paper, we propose a solution that reduces the mitigation of the quality of the recommendations over time. It combines clustering, matrix factorization and bias adjustment [START_REF] Paterek | Improving regularized singular value decomposition for collaborative filtering[END_REF][START_REF] Takács | Investigation of various matrix factorization methods for large recommender systems[END_REF], in order to startup with a high quality model. The biases are continuously updated with the new ratings, to maintain a satisfactory quality of recommendations for a longer time. Our solution is based on the observation that the rating tendency of a user is not uniform, and can change from one set of items to another. A list of biases is then associated to each user, one bias for each set of items holding some similarities in common. Thus, the integration of a new rating is provided by recomputing a local user bias (a bias of a user for a specific cluster of items), which may be done very quickly. Our approach improves the scalability of recommender systems by reducing the frequency of model recomputations. The experiments we conducted on the MovieLens dataset [3] confirmed that our technique is well adapted for dynamic environments where ratings happen continuously. The cost of the integration of new ratings is very low, and the quality of our recommendations doesn't decrease very fast between two successive matrix factorizations.

The remainder of this paper is organized as follows. In Section 2 we present some preliminary notions and requirements. Section 3 details our cluster-based matrix fac-torization solution. In Section 4, we present an experimental analysis of our proposal. Section 5 summarizes the related work, and Section 6 concludes the paper.

Preliminaries

The principal purpose of recommender systems is to predict the interest of a user for a given item, e.g. to determine how much the user would like the item. Most of the time, this interest is represented by numerical values from a fixed range (one to five stars, for example).

Prediction issue

Consider a set U of users and a set I of items. User ratings can be seen as tuples (u, i, r ui , t ui ), where u denotes a user, i denotes an item, r ui the rating of user u for the item i, and t ui is a timestamp. We assume that a user rates an item at most once.

The problem is to predict the future ratings such that the difference between an estimated rating rui and its true value r ui is the lowest possible. In order to build the estimator, the set of existing ratings is split in two parts: the first part is used for the training step and the second part for the evaluation of the accuracy of the estimator.

The quality of a recommender system can be decided on the accuracy of its predictions. The Mean Absolute Error (MAE), which computes the average of the absolute difference between the predictions and true ratings, is the most widely used metric for the evaluation of recommender systems [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF][START_REF] Su | A survey of collaborative filtering techniques[END_REF]. In this paper we use the MAE metric to compare our proposition to traditional systems.

M AE = 1 n u,i |r ui -rui | (1)
where n is overall number of ratings. The lower the MAE, the better is the prediction.

Matrix factorization

In the recommender systems using matrix factorization, the ratings are arranged into a matrix R. The columns of R represent the users where its rows represent the items. The value of each not empty cell c ui of R, corresponding to user u and item i, is a pair of values (r ui , t ui ). r ui is the rating given by u for the item i at time t ui . An empty, i.e. missing, cell c ui in R indicates that user u has not yet rated item i. Hence, the task of recommender system is to predict these missing rating values.

In its basic form (Basic MF), matrix factorization techniques try to capture the interactions between users and items that produce the different rating values. They try to approximate the matrix R of existing ratings as a product of two matrices:

R = P.Q (2)
P and Q are called matrices of factors since they contain vectors of factors for the profiling of the users and the items, respectively. These matrices of factors are much more smaller than R. Thus, we gain in dimension reduction while getting predictive ratings simply by the following formula rui = p u .q T i (3) where p u and q i are the vectors of factors, respectively in P and Q, corresponding to user u and item i.

In practice, it is almost not possible to obtain exactly R with the product of P and Q. Usually, some residuals remain. These latter constitute the error of prediction, i.e. its inaccuracy, which can be represented by a matrix E of errors having the same size than R. So, the previous equation can be changed to

R = P.Q + E (4)
We can see that more the matrix E is close to a zero matrix, and more accurate will be the prediction. The process of training looks for the better values of P and Q such that the matrix E is the closest possible to a zero matrix. Thus, it tries to adjust all the values e ui of the matrix E to zero using an expectation-maximization (EM) algorithm [START_REF] Dempster | Maximum Likelihood from Incomplete Data via the EM Algorithm[END_REF]. The EM algorithm computes a local minimum wherein the total sum of error values is one of the lowest according to initial ratings. In other words, it tries to minimize as good as possible the sum of quadratic errors ui e 2 ui between the predictive ratings rui and the real ones r ui . Errors are squared in order to avoid the effects of negative values in the sum, and minimizing ui e 2 ui amounts to minimize each e 2 ui .

We have e ui def = r ui -rui . By using the vectors of factors p u and q i , we obtain that e ui def = r ui -p u .q T i . If we denote by K the number of considered factors, we have

ui e 2 ui = ui (r ui -p u .q T i ) 2 = ui (r ui - K k p uk .q ki ) 2 (5)
To minimize the quadratic errors, we compute the differential (i.e., the gradients) of the above formula 5 to determine the part of change due to each factor (p uk and q ki ):

∂e 2 ui ∂p uk = -2.e ui .q ki , ∂e 2 ui ∂q ki = -2.e ui .p uk [START_REF] Berry | Using linear algebra for intelligent information retrieval[END_REF] We update p uk and q ki in the opposite direction of the gradients in order to decrease the errors and thus obtain a better approximation of the real ratings.

p uk ← p uk + λ.(2.e ui .q ki -β.p uk ) (7)

q ki ← q ki + λ.(2.e ui .p uk -β.q ki ) ( 8
)
Here λ is the learning rate used to avoid overfitting and β is a regularization factor which serves to prevent large values of p uk and q ki . The EM algorithm iterates on equations 5, 7 and 8 until the sum of the quadratic errors does not decrease any more. This process corresponds to the training step. After this training, the predictions rui are computed through the products p u .q T i of both vectors of factors. A sorting step allows to find the most relevant items to recommend to each user, i.e. the items with the greatest product values.

Biased MF

Several improvements to the above matrix factorization technique are proposed in the literature. One of these assumes that much of the observed variations in the rating values is due to some effects associated with either the users or the items, independently of any interactions [START_REF] Takács | Scalable collaborative filtering approaches for large recommender systems[END_REF][START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF][START_REF] Paterek | Improving regularized singular value decomposition for collaborative filtering[END_REF]. Indeed, there are always some users who tend to give higher (or lower) ratings than others, and some items may be higher (or lower) rated than others, because they are widely perceived as better (or worse) than the others. Basic MF can not capture these tendencies, thus some biases are introduced to highlight this rating variations. We call such techniques Biased MF. The biases reflect users or items tendencies. A first-order approximation of the biases involved in rating r ui is as follows:

b ui = µ + b u + b i ( 9
)
b ui is the global effect of the considered biases, it takes into account users tendencies and items perceptions. µ denotes the overall average rating (for all the items, by all the users). b u and b i indicate the observed deviations of user u, respectively item i, from the average. Hence, the equation 3 becomes rui = p u .q

T i + µ + b u + b i (10)
Since biases tend to capture much of the observed variations and can bring significant improvements, we consider that their accurate modeling is crucial [START_REF] Paterek | Improving regularized singular value decomposition for collaborative filtering[END_REF][START_REF] Koren | The bellkor solution to the netflix grand prize[END_REF]. As for the factors p uk and q ki (equations 7 and 8), the biases have to be refined through a training step using the following equations:

b i ← b i + λ.(2.e ui -γ.(b u + b i )) (11) b u ← b u + λ.(2.e ui -γ.(b u + b i )) ( 12
)
where γ is another regularization factor. It plays the same role than β in equations 7 and 8.

Dynamicity and performance requirements

Dynamicity problem As told above, once a model is carried out, it remains static unless a new MF is computed. In real-world context, where new ratings happen continuously, the user interests evolve dynamically. Thus, the accuracy of the predictions decreases gradually and the computed profiles become obsolete after some time, since they do not take into account the new additions of ratings. To face this problem, recommender systems must regularly recompute their models, which represents an expensive task in terms of computation time. Hence, the dynamicity problem can be defined as follows: how to integrate the new ratings in the predictions without recomputing the model ? The goal is to maintain the accuracy of the predictions at a good level and postpone as far as possible the recomputation of the model. We present in the following some important performance aspects, attempting to identify the requirements that the solutions for the dynamicity problem must satisfy.

Recommendation quality Assuming some fixed sets of users and items. We consider users continuously asking for items, and rating them. More precisely, a user asks for a short list of items with high probability of interest (i.e. high predicted rating), then selects and rates some of them, and so on. In such online recommendation scenario, the user expects the recommended items to be of high interest. We measure the quality of service in terms of the Mean Absolute Error (MAE) between the predicted and the real ratings. We express the user requirement for quality, as a constraint on the MAE, which value must be greater than a given threshold ǫ.

M AE < ǫ (13)

Response time Another requirement for online recommendation is the response time tolerated by the end users. When a user asks for a recommendation, he expects to receive it almost immediately. Such requirement for online user demand is usually described by an upper bound along with a ratio of appliance [30]: 90% of the demands must be served in less than 5 seconds. This response time constraint forces us (1) to generate the model in advance, in order to anticipate the future demands, and (2) to limit the computational cost needed for the integration of the ratings arrived after the model generation.

Limited resource computation

The last requirement concerns the overall computation cost of the recommendation. The solution must limit computations as much as possible. For instance, we could think of the model regeneration each time a new rating arrives, provided that we have unlimited computation resource. This will lead to a solution that meets the above requirements but that is not scalable. Therefore, we focus on solutions that take into account resource consumption in order to reduce it. We can summarize the performance requirements into the following challenge: design a recommendation solution which provides sufficient quality, when generating the "topquality" model takes a long time, when the model quality is decreasing over time, featuring fast recommendation delivery on user demand, and reducing the overall computation cost. In the following, we detail our method to tackle this challenge:

1. Combine clustering, MF and bias adjustment, in order to startup with a high quality model.

2. Continuous update of the biases in order to maintain satisfactory quality longer.

Online integration of new ratings

In this section, we present our regularized cluster-based matrix factorization. We start from the fact that many users tend to underestimate (or overestimate) the items they rate.

A user exposes a tendency to rate above (or beyond) the average. We aim to quantify such tendency. A simple way to take this into account is to assign a single bias per user (see section 2.3). However, we observed that user tendency is not fixed: it depends on the items they rate. For some groups of items, the users tend to rate close to the average. While for some other groups (e.g., the items he really likes/dislikes), the users fail to rate objectively, either using extreme ratings, or keeping moderated ratings. To take into account this discrepancy, we define several biases per user, instead of a single one. We assign one bias per user per set of similar items, relying on existing clustering techniques to group similar items together. We expect that handling finer-grained biases will lead to more accurate recommendation. Another expected outcome is a lower update cost while integrating the new ratings, because the update implies only the items inside one group. In our context, the only information we known about the items is their ratings.

Having additional information such as the item category is not the focus of this paper. Thus, we carry out groups of similar items through a clustering process that classifies the items according to their ratings. We use a K-means algorithm for the clustering phase.

Once the clusters are built, we assign a vector of biases to each user. Then, we apply a cluster-based MF on the ratings to generate the recommendation model. We now describe in more details the architecture of our solution, and the steps of the model generation process.

Architecture for online rating management

We detail the three layers of our recommendation system in Figure 1. First, the storage layer (lower layer) is responsible for storing the ratings and the generated model durably and efficiently. It manages two databases having different access patterns.

• The database of ratings assigned by users. It requires fast insert of new ratings (append only data structure) and point queries to retreive all the ratings of a given user, for a given group.

• The database of factors and biases generated by the factorization. It requires fast update of biases, and fast access to the factors and the biases of a given user.

Second, the recommendation processing layer (middle layer) has the following functions:

• Offline factorization and clustering: it generates the model, i.e., computes the factors in P and Q, and the biases of users. Then, it stores the model in the database of factors and biases. It reads the ratings in the database of ratings. It also runs the clustering procedure.

• an items recommendation: it provides recommendations upon user request. It queries the database of factors and biases to estimate the rui values. Then, it sorts them to keep the most relevant items to recommand. The item recommendation runs either on user demand, or precomputes recommandation in advance, for better response time.

• a new ratings manager : it handles the online integration of new ratings. Upon the arrival of a new rating, the online integration handles dynamic bias update. The new rating is also stored for subsequent model generation.

Third, the recommendation requests and the new ratings submissions (upper layer) represent the system workload.

We devise this architecture to better decouple the three main patterns that create (factorization), update (online integration) an read (item recommendation) the model respectively. This allows to control and postpone the factorization, depending on the quality of the item recommendation.

K-means clustering

The purpose of the K-means clustering algorithm (denoted KCA here after) is to divide pdimensional items into K clusters C k such that intra-cluster variance is the lowest possible. In other words, we minimize the next function

θ K = K k=1 i∈C k dist(r i , c k ) ( 14
)
Figure 1: Architecture of our recommender system

Where dist is a metric of distance between two items and c k the centroid, i.e. the mean item in C k . The squared Euclidean distance is generally used as metric of distance.

dist(r i , c k ) = j∈J i (r ij -c kj ) 2 (15)
In this formula, J i represents the set of defined dimensions for item r i , which corresponds in our case to the total number of users having rated the item r i . Different implementations of the KCA can be found in the literature [START_REF] Macqueen | Some methods of classification and analysis of multivariate observations[END_REF][START_REF] Hartigan | Algorithm as 136: A k-means clustering algorithm[END_REF][START_REF] Lloyd | Least squares quantization in pcm[END_REF]. The one proposed by Hartigan and Wong (see Algorithm 1) is well know as having a particular appeal because of its simplicity and computational speed. We choose this algorithm as the basis of our implementation.

Initializing the K-means clustering

One identified shortcoming of the K-means clustering is that it is very influenced by the starting centroids. Indeed, the K-means does not ensure that we have the best clustering but permits to get only one of the best possibilities. The choice of the starting centroids determines the quality of the clustering. Thus, it is very important to choose them. This issue is known as the K-means clustering initialization. Different methods are proposed in the literature [START_REF] Bradley | Refining initial points for k-means clustering[END_REF][START_REF] Mirkin | Clustering for data mining : a data recovery approach[END_REF][START_REF] Arthur | k-means++: the advantages of careful seeding[END_REF]. We used the one proposed in [START_REF] Mirkin | Clustering for data mining : a data recovery approach[END_REF] in our implementation,

Algorithm 1 K-means clustering algorithm Require: K ∈ N, R = {r i ∈ N p } 1: Take randomly an initial set of K centroids c (0) 1 , c (0) 2 ,... c (0) k 2: repeat 3: Let C (t)
k be the state of cluster C k at the time t and c (t)

k its cendroid at this time.

4:

Assignment step: assign each observation in R to the cluster with the closest centroid 5:

C (t) k = r i : dist(r i , c (t) k ) ≤ dist(r i , c (t)
l ), l = 1, 2, ...K

6:

Update step: calculate the new mean to be the centroid of the observations in the cluster.

7:

c (t+1) k = 1 |C (t) k | r i ∈C (t) k r i 8:
until Assignments no longer change 9: return C 1 , C 2 , ...C K because it presents good performances in terms of minimizing the intra-cluster variance and does not seem to be statistically influenced by data dimension [START_REF] Maitra | A systematic evaluation of different methods for initializing the k-means clustering algorithm[END_REF]. It attempts to get the initial centroids from observed data so that they are well separated from each other. Algorithm 2 describes this initialization method.

Algorithm 2 Initializing K-means clustering algorithm Require: K ∈ N, R = {r i ∈ N p } 1: Find all distances dist(r i , r j ) between each pair of items in the observed data R.

2: Denote c 1 and c 2 as the items with the largest distance.

3: repeat

4:

Let K * be the number of current centroids.

5:

For all r i / ∈ {c k , k = 1, 2, ...K * }, compute dist(r i , c k ) for k = 1, 2, ...K * . Keep the minimum dist min (r i ) = min {dist(r i , c k ), k = 1, 2, ...K * } 6:

Set centroid c K * +1 = max dist min (r i ) 7: until we have reached the number K of wanted centroids 8: return c 1 , c 2 , ...c K

Cluster-based MF

After having carried out the groups of items C through clustering, i.e. the clusters, a vector of biases is allocated to each user. One bias for each group of items. Thus, we come down to observe local/group ratings variation in place of a single global ratings variation as used in previous approaches [START_REF] Paterek | Improving regularized singular value decomposition for collaborative filtering[END_REF][START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF][START_REF] Takács | Investigation of various matrix factorization methods for large recommender systems[END_REF]. Our formula of prediction is as follows:

rui = p u .q T i + µ C G(i) + b u,C G(i) + b i (16)
where G(i) is a function which returns for any item i its group identifier. We denote by µ C G(i) the average ratings in C G(i) and by b u,C G(i) the bias of user u for the group of items C G(i) . We call b u,C G(i) the local user's bias, i.e. the observed local deviation of user u. b i represents the observed deviation of item i.

The bias b u,C G(i) of user u for the cluster G(i), to which the item i belongs, is derived from the existing ratings of item i in the group C G(i) . For each rated item j in the cluster C G(i) , we calculate the deviation of user u for this item by r uj -µ C G(i) . The local bias of the user is obtained by taking its average deviation:

b u,C G(i) = 1 |C G(i) | j∈C G(i) r uj -µ C G(i) ∀j ∈ C G(i) , s.t. r uj > 0 (17)
The algorithm 3 details the steps of our model generation process. Line 1 corresponds to the clustering phase. It is done by applying the algorithms 2 and 1 given before. Line 2 computes the bias of each item and the vector of biases of each user (as shown in equation 17). Lines 4 to 11 correspond to the most important part of the learning process. Lines 7, 8 and 9 update respectively the vectors of factors, the biases of the items and the biases of the users, using equations 7, 8, 11, and 12. They consider the error calculated in Line 6. Line 11 measures the global error. These steps are repeated until the global error given in equation 5 does not decrease any more or a certain number of iterations is met. for all r ui > 0 ∈ R do

6:

Compute e ui 7:

Update p uk ∈ P , q ki ∈ Q Calculate the global error r ui >0∈R e 2 ui 12: until terminal condition is met

13: return P , Q, µ G = µ C G(i) , G(i) ∈ 1, 2, ...K , b i , b u
After the generation of the model, the integration of additional ratings (those obtained after the MF) is obtained by adjusting local user bias b u,C G(i) . This is done by the execution of the instructions 4 to 12 in algorithm 3, except the lines 7 and 8 to keep unchanged the initial vectors of factors in P and Q.

Evaluation of the proposed technique 4.1 Complexity analysis

Let us denote by V the set of (existing) ratings in R.

V = {r ui ∈ R/r ui > 0} ( 18
)
The cost of our cluster-based matrix factorization solution (Algorithm 3) can be separated in two parts: the cost of matrix factorization and the cost of the clustering step. The time complexity of the training of the whole model (matrix factorization

) is O(|V | .k.t),
where k is the number of factors and t the maximum number of iterations (see Section 3.4). The clustering step is done using the algorithms 1 and 2. Its time complexity is O(n.N c .t) for the K-means clustering (Algorithm 1), and O( n 2 (N c + n)) for the initialization of the k-means (Alrorithm 2). n is the number of items to cluster, and N c the number of clusters.

The online integration of new ratings is done in our approach simply by updating user biases. When a user u 1 rates by r u 1 i an item i, we update the bias of u 1 for only the group/cluster to which the item i belongs. Hence, we define the ratings of user u 1 as

V (u, .) = {r uj ∈ V /u = u 1 } ( 19
)
and all its ratings in the cluster G(i) as

V (u, G(i)) = r uj ∈ V (u, .)/j ∈ C G(i) (20)
Thus the time complexity of the integration of a new rating r ui is O(|V (u, G(i))| .t). Note that in the worst case this cost is equal to O(|V (u, .)| .t), when all the ratings of the considered user belong to the same cluster. Let us stress that V (u, .) is usually small. For instance, for Netflix the average size of V (u, .) is 200 [1].The more the user ratings are distributed in different clusters, the more the cost of updating the user bias is small.

Experimental evaluation

In Section 2.4 we proposed to enhance the widely used MF model, coupling it with two techniques that tend to improve the quality of predictions: the preliminary clustering of the ratings before factorization, and the final adjustment of the predicted ratings using biases. This section presents the experiments we settled, in order to validate our approach. We remind that our approach consists of generating a high quality recommendation model based on incoming ratings. Then, we use that model for recommending items, as long as possible (provided that quality remains sufficient) up to next generated model is ready, and so on. Thus, the quality of our approach depends on two factors (i) the initial quality of the generated model, and (ii) the quality mitigation over time. Accordingly, we validate each factor independently, proceeding in two separated steps. Step 1 focuses on the initial quality of the model that has just been generated. Step 2 focuses on the quality mitigation, of our approach, over time.

Step 1: Validation of the initial quality We plan to show that our model yields good initial predictions compared to other commonly used models. We setup a fully informed environment, meaning that the model is aware of all the ratings that precede the prediction. This environment is optimal since it provides the maximal input to the model generation. Although this environment is rarely met in practice (it implies that no new ratings have occurred during the model generation), it ensures the most favorable conditions for every model. Thus it allows us for comparing several models when they expose their best strength. Our objective is to quantify the quality of our model that combines factorization with clustering and bias adjustment. To this end; we compare the accuracy of our model with two commonly used models: (i) the MF alone, and (ii) the biased MF (see Section 2.3). Note that, we do not compare our solution with the case of MF preceded by clustering without bias adjustment, since clustering does not improve the accuracy directly in its own. Actually, clustering allows for finer biases (one bias per cluster), which in turns yields better accuracy.

Step 2: Validation of the quality mitigation over time In the second validation step, we will check that the accuracy of prediction is actually decreasing over time. This aims to justify the relevance of our investigation to provide predictions which accuracy lasts longer. Then, we will measure the benefits of our approach (continuous bias update, based on new ratings) for keeping up the accuracy of prediction longer than others. In other words, our solution should expose a smaller quality decrease (i.e. a flatter slope) than other solutions. In consequence, it will imply less frequent model re-regeneration, saving a lot of computation work.

Implementation and Experimental setup

We implemented our proposition in python language (approximatively 4000 lines of code). Python is a powerful dynamic programming language that is well suited for rapid prototype developement Its standard library is large and very comprehensive. We used the NumPy package [2] for matrix manipulation. We ran our experiments on a linux computer (Intel/Xeon x 8 threads, 2.66 Ghz, 16 GB).

Datasets

The experiments use the publicly available MovieLens data sets [3]. These datasets are widely used by the recommendation system community [START_REF] Su | A survey of collaborative filtering techniques[END_REF]. They contain real ratings about movies, collected from MovieLens recommendation website since September 97. We use the dataset which contains 100K ratings for 1682 movies (i.e. items) by 943 users.

A rating is an integer in [1][2][3][START_REF] Arthur | k-means++: the advantages of careful seeding[END_REF][START_REF] Bell | The million dollar programming prize[END_REF]. Each user has rated at least 20 movies. We made preliminary tests to calibrate the four parameters of the model: λ = 0.001, β = 0.02, γ = 0.025 and the number K = 2 of clusters. The λ, β, and γ values are close to the ones suggested in [START_REF] Paterek | Improving regularized singular value decomposition for collaborative filtering[END_REF].

Experiment 1: Initial quality

The objective of the experiment 1 is to measure the initial quality of the model. We check the intuitive rule stating that the more ratings we take as input, the more quality we get. We split the dataset at date d 0 : the training set ends at d 0 , the test set starts at d 0 . We choose d 0 such that the test set represents the last 20% of the dataset. We are varying the training set cardinality from 10K to 80K ratings by varying the start date of the training set. More precisely, for the i th run, we select the ratings in [d i , d 0 ], choosing d i such that the training set contains (10000*i) ratings. Note that every training set ends at d 0 , this ensures we always use the most recent ratings to generate the model at date d 0 . We take the quality of the i th run as the ratio of the calculated MAE to the best one obtained from all. Let us note that this best MAE (i.e. smallest MAE) is given by our solution and its value equals 0.706.

Figure 2 shows that the quality is increasing almost linearly up to 50K ratings, this confirms our intuitions. Beyond that point, adding more rating into the training set does not bring much quality improvement as before: old ratings appear to be less relevant, this is possibly due to mind-changing users. On this figure, we also plot the respective quality of the models that we are comparing with: basic MF and biased MF. Hopefully, our model always make progress better than the two other models, thanks to finer-grain cluster based bias adjustment. Although our model begins with the lowest quality, it ends with the best quality. Indeed, with the first training sets we have'nt enough data to make goods clusters. Combined to the fact that the users haven't yet rated a lot of items which harms the adjustment of biases, we expected these cases. But from 50K ratings as training set, we remark an improvement with our model. It is not only our model which is affected by the smallness of training set, the biased MF suffers from that also. This explains why the basic MF presents the best quality for the two smallest training sets (under 30K ratings). Let us note that our model has the highest relative progression in quality with an average of 3.92% when the biased MF has 3.42% and the basic MF 1.74% benefit. The objective is to show that our model is robust to time, i.e., it still yields rather good quality predictions even when the model becomes out-of-date. We define the test set and the training set as follows. The test set remains identical; it contains all the ratings since date d 0 , up to the end of the dataset. The training set size is fixed to 30K ratings, because in the previous experiment, the positive effect of adding biases (i.e. the biased MF over-performs the basic MF) appeared with a training set containing that number of ratings. Then, we define several training sets, such that the model becomes increasingly out-of-date. To this end, we are varying the end date (named d end ) of the training sets, in order to increase the gap between the model generation (at d end ) and the model use (starting at d 0 ). More precisely, for each training set, we set the number of missed ratings (named M ) that must occur during [d end , d 0 ]. Then, according to M , we set the start/end date of each training set. On Figure 3, M is varying from 0 to 50K, along the x-axis. We report, on the y-axis the quality expressed as a ratio relative to the minimal MAE, M AE min , obtained for M = 0 (M AE min equals 0.791 for our model, and 0.781 for the biased MF). We see that the quality of the biased MF is decreasing over time as we expected. For our model, the quality also follows a decreasing tendency, but with some fluctuations. Such oscillations in quality are due to the non-uniform distribution of the ratings for each item, that is quite accentuated by our training set size. We expect that our cluster-based approach better captures this non-uniformity for larger training sets.

Furthermore, we also show the importance of taking into account the new ratings. ), as said in Section 3.4. Accordingly, we also consider the missed ratings to adjust the single bias of the biased MF solution we are comparing with. We check that such adjustement is fast enough (from milliseconds to few seconds) to add neglectible overhead on the online recommandation task. On Figure 4, we report the relative quality improvement, in comparison with Figure 3, for the same x values. We see that our model performs up to twice better than biased MF. On average, we get 2.42% of quality improvement, while biased MF yields only 1.47% improvement. This confirms the benefit and the feasability of online integration of new ratings. In this section, we generalize from the results of Sections 4.2.3 and , and explain the dependency between the training set size (T S) and the number of missed ratings (M ). Then, we investigate the combined influence of both T S and M on the quality, in the case of intensive new ratings arrival. Finally, we devise a method to assess the optimal T S. Experiment 1 showed that taking into account more rating in the training set, improves the recommendation quality. However, to highlight the effect of the training set size on the quality, we assumed that no ratings arrived during the factorization. In other words, we assumed that the factorization time is smaller than the rating inter-arrival time. We now relax this assumption to better reflect the general case, and we quantify the factorization time T f act. It depends on the training set size as follows: T f act = f (T S) where f is monotonic and increasing. In our context, we observed that T f act is actually longer than the inter-arrival time, thus several ratings arrived during the factorization, before the recommender is ready for use. We get: M = T f act * T h where T h is the input throughput. In experiment 2, we showed that a large M tends to decrease the quality of a given training set. Intuitively, the impact of M on the quality depends on how much the test set relies on recent ratings rather than on older ratings. For instance, most users rate movies soon after their release date. In consequence, increasing the training set size is influencing the resulting quality on two opposite directions since T S and M are increasing all together. On one side, a small T S does not rely on enough ratings to make factorization relevant, thus it yields poor quality. On the other side, a large T S implies a large M , that makes factorization out-of-date, thus yields poor quality as well.

In between, there exists an optimal T S value (called T S opt ) that yields optimal quality. A practical method to assess T S opt is to process a set of runs for several T S growing values. For each run, one fix the bounds of the training set such that it precedes the test set with a delay of M/T h. Then, plotting the meassured quality should highlight the T S opt point. Depending on the context, the relative impact of the growing delay (M ) vs. the growing T S might be low. In that case, which is that of MovieLens, instead of figuring out T S opt , one fall back to figure out the minimal TS value that is close enough (wrt. the required quality of service) to the maximal quality obtained with the largest available T S.

Related work

Previous research on online integration of new ratings focused particularly on the "new user/item" problem, in order to let the recommender system able to propose predictions for new registered users and items [START_REF] Chakraborty | A scalable collaborative filtering based recommender system using incremental clustering[END_REF][START_REF] Sarwar | Incremental singular value decomposition algorithms for highly scalable recommender systems[END_REF][START_REF] Rendle | Online-updating regularized kernel matrix factorization models for large-scale recommender systems[END_REF].

In [START_REF] Chakraborty | A scalable collaborative filtering based recommender system using incremental clustering[END_REF], the author proposes an incremental clustering solution to tackle the new user problem. He performs an initial K-medoids clustering with the PAM (Partitioning Around Medoids) algorithm. Then, for the integration of new users, he developed a clusterupdating algorithm capable of swapping the medoids and producing new clusters. Sarwar et al. [START_REF] Sarwar | Incremental singular value decomposition algorithms for highly scalable recommender systems[END_REF] adapted the Latent Semantic Indexing (LSI) technique, applied in information retrieval (IR) to solve the problem of synonymy and polysemy. They used this technique to reduce the dimensionality of the user-item ratings matrix. The proposed Foldingin technique uses a projection method to fold the new users and items in the already computed model. This solution is very efficient in terms of computational time, but its quality have to be compared to similar techniques used in IR, like SVD-updating [START_REF] Berry | Using linear algebra for intelligent information retrieval[END_REF].

Rendle et al. [START_REF] Rendle | Online-updating regularized kernel matrix factorization models for large-scale recommender systems[END_REF] extend the "new user/item" problem to focus on users (and items) with a small rating profile. They propose an approximization method that updates the matrices of an existing model (previously generated by MF). The UserUpdate algorithm they propose retrains the factor vector for the concerned user and keeps all other entries in the matrix unchanged. Its time complexity is O(|V (u, .)| .k.t), where k is the given number of factors and t the number of iterations. In contrast with our solution, the whole factor vector of the user is retrained (i.e. his rating profile for all the items), which makes their solution more time consuming than ours (O(|V (u, G(i))| .t), see Section 4.1). They also not consider user biases, which might be very important for the accuracy of the predictions.

Cao et al. [START_REF] Cao | Detect and track latent factors with online nonnegative matrix factorization[END_REF] point the problem of data dynamicity in latent factors detection approaches. They propose an online nonnegative matrix factorization (ONMF) algorithm that detects latent factors and tracks their evolution when the data evolve. Let us remind that a nonnegative matrix factorization is a factorization where all the factors in both matrices P and Q are positive. They base their solution on the Full-Rang Decomposition Theorem, which states that: for two full rank decompositions P 1 .Q 1 and P 2 .Q 2 of a matrix R, there exists one invertible matrix X satisfying P 1 = X.P 2 and Q 1 = X -1 .Q 2 . They use this relation to integrate the new ratings. Although the process seems to be relatively fast, its computation time is greater than ours. This is due to the fact that their technique updates the whole profiles of all the users where our solution limits the computations to the bias of the concerned user.

Conclusion

In this paper, we have presented a cluster-based matrix factorization (MF) approach which aims to overcome a major drawback of existing MF solutions: their inability to deal with dynamicity in a real-world context. To this end, we have introduced a multi-biases model that leverages clustering to capture fine-grained users' profiles more accurately than the existing single bias approach. We have proposed a detailed algorithm to generate our model, then to dynamically incorporate new ratings without regenerating the whole model. We have implemented our solution, as well as two other related ones. We have performed extensive experiments on the widely used MovieLens datasets, in order to validate both quality and performance. Qualitative results place our solution close to its competitors, while offering better quality preservation over time. Performance results expose fast integration of new ratings; that makes our solution viable for online recommendation systems. Finally, we have devised a practical method to tune the training set size in case of intensive arrival of new ratings. This is a first step towards quality aware cost based optimization of online recommendation.

Algorithm 3

 3 Cluster-based MF algorithm Require: K: the number of wanted clusters, R: the matrix N m * n of ratings, k: the number of factors to consider, λ, β and γ 1: Compute the clusters C 1 , C 2 , ...C K from the observed data R 2: For each item i and each user u, calculate the bias b i of item i and the vector of biases b u = b u,C G(i) , G(i) ∈ 1, 2, ...K 3: Initialize randomly, or with fixed values, the two matrices P and Q, respectively of dimensions m * k and k * n. 4: repeat 5:

8 :b i 9 :

 89 UpdateUpdate also b u,C G(i)

Figure 2 :

 2 Figure 2: Quality increases with the amount of ratings

Figure 3 :

 3 Figure 3: Quality over time

Figure 4 :

 4 Figure 4: Quality's improvement by new ratings


Gustave Cortal

Alain Finkel

Patrick Paroubek

Lina Ye

Natural Language Processing for Cognitive Analysis of Emotions

Introduction

Emotion analysis in texts suffers from two major limitations: annotated gold-standard corpora are mostly small and homogeneous, and emotion identification is often simplified as a sentence-level classification problem. To address these issues, we introduce a new annotation scheme for exploring emotions and their causes, along with a new French dataset composed of autobiographical accounts of emotional scenes. The texts were collected by applying the Cognitive Analysis of Emotions (CAE) [START_REF] Finkel | Manuel d'analyse cognitive des émotions: Théorie et applications[END_REF] to help people improve on their emotion management. We present a rule-based approach to automatically annotate emotions and their semantic roles (e.g. emotion causes). We investigate future directions for emotion analysis using graph structures.

Cognitive Analysis of Emotions

• A method to help people improve on their emotion management. It studies how primary emotions appear in autobiographical accounts of emotional scenes.

• An emotion arises when we evaluate a situation that invalidates or confirms our model of the world, made up of territories associated with our needs to be satisfied (e.g. physiological, safety, love and belonging needs, etc.). My territories can be: my body, my home, my professional values, my beliefs, my selfimage, my time, etc.

• A coach trained in Cognitive Analysis aims to understand emotion causes (e.g. by identifying the territories involved) and suggests corrective actions to better handle situations.

We propose to automate an important step of CAE analysis, namely the identification of emotions and their causes.

Limitations in Emotion Analysis

• Emotion analysis in texts rarely considers psychological theories to really understand emotions and their causes.

• It is often simplified as a sentence-level classification problem.

• Annotated corpora are mostly small and limited to a few domains (reviews, social media) and languages (English, Chinese) [START_REF] Poria | Beneath the tip of the iceberg: Current challenges and new directions in sentiment analysis research[END_REF].

Annotation scheme for Aspect-Based Emotion Analysis

Goal: Deeply understand a written emotional scene by automatically identifying who feels an emotion, what drives an entity to express an emotion toward a certain aspect and why.

Semantic roles: cue (a marker indicating the presence of an emotion), experiencer (the author who feels an emotion), target (an entity or a person targeted by an emotion) and cause (an event that triggers an emotion). These roles are employed by [START_REF] Campagnano | SRL4E -Semantic Role Labeling for Emotions: A unified evaluation framework[END_REF] to unify several gold but heterogeneous datasets that contain annotations for both emotions and their semantic roles.

Example: "Gustave loves carnivorous plants because they are beautiful", Gustave (experiencer) exposes his joy (cue) towards carnivorous plants (target) because they are beautiful (cause).

Extended annotation scheme

Goal: Extend the previous annotation scheme with new semantic roles based on CAE to better understand emotion causes.

Added semantic roles: territory (corresponding to the notion of territory in CAE), attack (expressions related to the act of attacking or being attacked) and attacker (an entity that attacks a territory).

Example: "My skills are attacked by Marc", "My skills" are a territory related to the author's professional values and competent self-image attacked by the attacker "Marc".

The dataset, composed of autobiographical accounts of emotional scenes, will indicate emotions and their semantic roles according to our extended annotation scheme. Note that the annotation process

has not yet been performed, nor has the evaluation of our rule-based prototype.

Rule-based method

Goal: Manual creation of rules with linguistic features (using dependency parsing, co-reference resolution and part-of-speech tagging) and semantic features (using sentiment and emotion lexicons [START_REF] Saif | Crowdsourcing a word-emotion association lexicon[END_REF]) to automatically identify emotions and their semantic roles.

Example: territory is found if it is the subject of an attack in passive voice: "My skills are attacked by Marc".

Graph structure

Goal: Represent emotion expressions by a graph structure that can be visualized.

A

  sentence or a whole text corresponds to a graph in which nodes are words and edges indicate relations of various kinds between words. The application can display different levels of text analysis (e.g. dependency parsing, our emotion analysis, etc.) in a single plane. Visualization of the French sentence: "Mes compétences sont attaquées par Marc" (translated "My skills are attacked by Marc"). Edge colors indicate different types of relations, e.g. noun chunk membership is in green and sequential relation is in pink. Node colors indicate semantic roles, e.g. experiencer is in red, territory is in purple, attacker is in brown and attack is in yellow.


Iván García-Magariño

Sylvain Rougemaille
email: rougemai@irit.fr

Rubén Fuentes Fernández

Frédéric Migeon
email: migeon@irit.fr

Juan Pavón Mestras

Marie-Pierre Gleizes
email: marie-pierre.gleizes@irit.fr

Towards Agent-Oriented Model Driven Engineering

This work gathers the experience of two different research groups that developed the agent-oriented methodologies INGENIAS and ADELFE. The particular features of the agent paradigm makes that the application of MDE approaches to it has to consider certain issues that are not common in mainstream Software Engineering. In particular, MAS methodologies usually consider several abstraction levels and perspectives, producing a richer modelling than for instance object-oriented approaches. Besides, the agent research is still object of important evolution with changing and growing conceptual frameworks. The view of these MAS research groups is promoting model transformations to bridge these gaps between perspectives in modelling, and to support the change in the modelling languages and their corresponding tools. This focus on transformations should also allow taking advantage of the semantic richness of MAS concepts in code generation, producing software that is closer to the final product since the meaning of the concept and its related behaviour are more precise.

Introduction

Developing Multi-Agent Systems (MAS) in the scope of modern information systems is a complex activity. Different proposals have been made to alleviate the designer's work, mainly through methodologies and their support tools. Among them, we are particularly involved in the methodologies INGENIAS [START_REF] Pavón | Agent Oriented Software Engineering with INGENIAS[END_REF] and ADELFE [START_REF] Bernon | Engineering Adaptive Multi-Agent Systems: The ADELFE Methodology[END_REF]. Both of them share a software engineering approach based on Model Driven Engineering (MDE). We have gathered our experience in the definition of each methodology and the development of their tools in order to highlight the benefits and challenges of this approach for MAS development. Of course, synthesis presented here gains also from related works which are quickly surveyed before conclusion. However, our true background, and precise technical use of MDE, is limited to the scope of INGENIAS and ADELFE, which therefore constitute the focus of the paper.

The paper analyzes the particular requirements of Agent Oriented Model Driven Engineering (AOMDE), term that we propose to express the application of MDE to the development of MAS. These requirements mainly rise from the need of dealing with rich, heterogeneous, and changing conceptual frameworks, which makes necessary to consider the evolution of the modelling languages and their related tools, the links between different perspectives, and also the possibility of carrying out sophisticated processes over the models that take advantage of that conceptual richness.

The organization of the paper is as follows. Section 2 describes the works that have been used as the basis for this paper. It begins describing the principles of MDE and then introduces the INGENIAS and ADELFE agent-oriented methodologies. Section 3 discusses the application of MDE in the scope of our methodologies by focusing on meta-modelling and model transformations. This application has shown benefits of the approach but also limitations that Section 4 discusses. Section 5 broadens the discussion about agent-oriented methodologies and MDE with some related work, the methodologies Tropos [START_REF] Bresciani | Tropos: An agentoriented software development methodology[END_REF] and Prometheus [START_REF] Padgham | Prometheus: A methodology for developing intelligent agents[END_REF], that also adopts a model-driven approach. Finally, Section 6 draws some conclusions about the concept of AOMDE and the future work that agent researchers must consider in its application.

Background

Model Driven Approach

Model Driven Engineering (MDE) [START_REF]Object Management Group[END_REF] is a software development approach that considers models as first class citizens. Model transformations are the means to automate the life-cycle from early design tasks to the implementation. Likewise, maintenance of systems can benefit from keeping a correlation between models and code.

Specifically, the OMG Model Driven Architecture (MDA) [START_REF]Object Management Group[END_REF] is one of the most broadly promoted model-driven approaches. Its principles involve the UML standard [START_REF]Object Management Group[END_REF] and a set of automatic processing languages to produce code. Starting with a requirements model called the Computation Independent Model (CIM), an abstract Platform Independent Model (PIM) is created. The idea is to produce automatically a Platform Specific Model (PSM) thanks to model transformations. A mapping between the PIM and the PSM is created according to the Platform Model (PM) and implemented as a transformation. The specific model is then used to generate the application code.

The main advantage of the MDA approach is that whenever the platform supporting the application changes, the abstracts models do not have to be modified. The transformations between PIM and PSM are the only part that have to be specified again.

As a recent initiative, Model transformation By-Example (MTBE) [START_REF] Varró | Automating model transformation by example using inductive logic programming[END_REF] is defined as the automatic generation of transformations from source and target model pairs. The common steps of MTBE are the following:

1. Manual set-up of prototype mapping models. The transformation designer assembles an initial set of interrelated source and target model pairs. 2. Automated derivation of rules. Based upon the available prototype mapping models, the transformation framework should synthesize (see Figure 1 The MTBE approach overcomes the hard-coding of transformations, which frequently hinders the principles of MDE. MTBE follows MDE principles because its main products are models and transformations. In addition, transformation designers in MTBE do not need to learn a new model transformation language; instead they only use the concepts of the source and target modelling languages.

INGENIAS and the IDK

The INGENIAS methodology for the development of MAS was founded on the use of meta-modelling technique [START_REF] Pavón | Agent Oriented Software Engineering with INGENIAS[END_REF]. It covers the whole development cycle, from analysis to implementation, and provides tool support with the INGENIAS Development Kit (IDK). The user defines with the IDK the specification of the MAS, which is the basis of its development. Figure 2 shows some relevant elements of the INGENIAS notation. To create this specification, the user has the specification editor of the IDK. This editor works as a host for plugins that format documentation, verify specifications and generate code. The key plugin for code generation is the INGENIAS Agent Framework (IAF) that produces code for the JADE platform [START_REF] Bellifemine | Developing multi-agent systems with a FIPAcompliant agent framework[END_REF] according to an architecture designed in INGENIAS that supports, among several features, deliberative and reactive agents, and a simplified management of protocols. This code generator has been introduced previously in the literature in [START_REF] Gómez-Sanz | Defining coordination in multi-agent systems within an agent oriented software engineering methodology[END_REF][START_REF] Gómez-Sanz | Enabling Rapid Prototyping using Decoupling of Code Skeletons and Code generation Process[END_REF]. Therefore the IDK provides a way to develop MAS following the principles of Model-Driven Development [START_REF] Pavón | Model Driven Development of Multi-Agent Systems[END_REF]. The user defines the specification with the IDK Editor. This specification represents the model, which is the basis for developing the MAS.

This MDE approach provides to the INGENIAS methodology a robust and quick technique for the development of MAS. As a matter of fact, INGENIAS and the IDK have been applied successfully in several areas; for instance, in surveillance [START_REF] Pavón | Development of intelligent multisensor surveillance systems with agents[END_REF], knowledge management system [START_REF] Soto | Modelling a Knowledge Management System Architecture with INGENIAS Methodology[END_REF] and social simulation [START_REF] Pavon | Agent-based modelling and simulation for the analysis of social patterns[END_REF].

ADELFE

ADELFE 3 defines an agent-oriented methodology for designing Adaptive Multi-Agent Systems (AMAS) [START_REF] Capera | The AMAS Theory for Complex Problem Solving Based on Self-organizing Cooperative Agents[END_REF]. ADELFE is mainly involved in the specification of systems intended to deal with complex environment dynamics and self-adaptation. The ADELFE methodology [START_REF] Bernon | Engineering Adaptive Multi-Agent Systems: The ADELFE Methodology[END_REF] aims at guiding AMAS designers through a development process based on the standard Unified Process (UP) [START_REF] Jacobson | The Unified Software Development Process[END_REF] for object-oriented methodologies.

ADELFE has been recently improved with the use of UML 2.0 for the specification of interactions [START_REF] Bauer | Uml 2.0 and agents: how to build agent-based systems with the new uml standard[END_REF]. It also integrates a new model-driven implementation phase based on specific modelling languages and model transformations [START_REF] Rougemaille | ADELFE Design, AMAS-ML in Action[END_REF]. Therefore, the last ADELFE version covers the whole software development process, from early requirements to the implementation.

AMAS-ML (AMAS Modelling Language) is used in several steps of the ADELFE design phase, from the detailed agent structure design to the definition of its cooperative behaviour. The resulting model is used as an input for the implementation phase. By means of several model transformations, this phase allows generating the code of both the agents behaviour and the specific API supporting them [START_REF] Rougemaille | Model Driven Engineering for Designing Adaptive Multi-Agent Systems[END_REF]. Therefore, ADELFE provides a MDE process : from an abstract model defined with AMAS-ML it generates the application code.

3 Model-Driven from experience 3.1 Meta-modelling MDE is based on models. Models have to be specified conforming to one meta-model. This meta-model could be considered as the abstract syntax of a modelling language. Both INGENIAS and ADELFE defines their own meta-models and each one are used as a basis for Domain Specific Modelling Languages (DSML).

ADELFE proposes two meta-models corresponding to specific modelling languages : AMAS-ML and μADL. AMAS-ML focuses on general AMAS specification and μADL in a specific architecture.

AMAS-ML formalizes concepts of the AMAS theory. It provides modelling elements to support the design of cooperative agents. A cooperative agent is specified as made up of various modules. Each module manage an aspect of its activities and life-cycle. Typically, the AMAS agent life-cycle is defined according to three main phases: perception, decision and action. The AMAS-ML meta-model considers the needs in these stages in terms of environmental interactions, knowledge, representation, noncooperative situations avoidance, etc. For example, to carry out its perception and action phases, an AMAS agent requires environmental interactions. They are represented by perception and action on entities (elements of the environment) as well as the means to carry them out (actuator and sensor). These concepts appear in specific modules of the agent and are mandatory elements of AMAS-ML models. Thus, it ensures that designed agents are aware of their execution environment.

One important point for AMAS agents is their cooperative behaviour. In AMAS-ML, the decision module is a container for rules that describe the agent behaviour. Each rule is triggered by a particular state of the agent and implies several actions. The states are defined as logical conditions expressed over the agent knowledge. With AMAS-ML designer, the user can define the behaviour of cooperative agents and consequently, the emergent behaviour of the system.

μADL defines a flexible agent architectural style [START_REF] Leriche | AGENTφ: A Tool for Modeling Composite Self-Adaptive Agents[END_REF]. An architectural style [START_REF] Medvidovic | A classification and comparison framework for software architecture description languages[END_REF] of a software unit is a set of rules and constraints that specifies its composition and evolution features. Here, software units are agents. These agents conform to an architectural style derived from the architecture of the agents in JAVACT, which is a Java middleware for programming adaptive mobile agents 4 developed by the SMAC research team. Its main characteristic is the separation of concerns between the functional level related with the agents' behaviour and the operating level related with the internal mechanisms necessary for the execution of the functional code. This separation of concerns is provided at the operating level via fine-grained software components called micro-components. Those micro-components are connected to a mediator in a star-like topology according to the design pattern Mediator [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF]. μADL is a language for micro-architecture modelling based on the architectural concepts previously explained. It guaranties several structural properties at design time, like consistency of service invocation between components or respect of the topology. It provides concepts such as micro-architecture, micro-component and interfaces for the connection between the micro-components and the Mediator. Thus, a micro-architecture consists in a microcomponents assembly defined by means of the interfaces they provide to the Mediator. Any μADL model is an abstraction of a micro-architecture, that is, a type of agent, and is the source of a code generation process.

The INGENIAS meta-model was originally defined with the Graph Object Property Relationship Role (GOPRR) [START_REF] Kelly | GOPRR Description[END_REF] meta-modelling language, which was supported by the MetaEdit+ tool. However, GOPRR did not have a standard notation and its support has decreased in comparison with other meta-modelling alternatives. For this reason, the INGENIAS meta-model was migrated to ECore. Since the INGENIAS meta-model is large, it contains 88 objects, 89 relationships and 98 roles, the Grasia group defined an automatic translation GOPRR-to-ECore for the meta-modelling support in the IDK. The remaining drawback, is that existing models that are conform to the GOPRR version of the INGENIAS meta-model, have to be also translated. An experimental implementation of the IDK 2.7 can serialize with instances of both GOPRR and ECore meta-models enabling model transformations according to the meta-model translation.

The use of meta-models in these methodologies facilitates the creation and the maintenance of design tools; either by being a preliminary tool architecture definition (in the scope of INGENIAS) or by being the basis for editors generation (in the scope of ADELFE). This point is specially significant in MAS domain. As a matter of fact, MAS concepts are still evolving, since no consensus has been yet reached on what should be called an agent or not. Meta-models constitute a flexible means to integrate new concepts in the design without changing the whole tool.

Meta-modelling helps to define precisely some concepts that are parts of modelling languages. Moreover, we have defined our meta-models using the wide spread Eclipse meta-modelling language ECore. It constitutes a "de facto standard" with many model driven tools compliant with it (ATL, GMF, GEF, EMF, etc.).

Although meta-models facilitate the evolution of design tools, maintaining models conformance whenever the meta-models change is still a challenging problem. In our experience, this constitutes a problem that is not well solved in MDE. Both INGENIAS and ADELFE meta-models are starting points for tool definition or generation. However, some parts have to be manually developed because of the advanced functionality they imply.

Model to Model transformations

Model-to-model transformations can be useful for different tasks in the Agent Oriented Software Engineering. Some of these usages currently done in ADELFE are:

-To integrate various modelling languages in the same frame. In particular, ADELFE uses the UML sequence diagram for the design of interaction protocols. The messages exchanged in these protocols are automatically integrated to the AMAS-ML model within the cooperative agent specification by means of a transformation. -To separate different concerns. The ADELFE implementation uses a specific language, μADL (micro-Architecture Description Language) [START_REF] Rougemaille | Model Driven Engineering for Designing Adaptive Multi-Agent Systems[END_REF] to express operating mechanisms of agents (similar to non-functional concerns). The behaviour of cooperative agents, defined in the the AMAS-ML model, is separated of the operating concern. This concern consists in all the concepts that are involved in the creation and maintenance of the agent knowledge (perceptions, actions over environmental entities, and so on).

Model-to-model transformations are useful to gather good practises or designer experience. They allow to automate processes that have to be done by domain experts, as the translation of UML sequence diagrams into AMAS-ML communication actions. Designers who are not familiar with both domains can benefit from the knowledge embodied within this transformation. Moreover, these transformations guaranty that tasks are done in the way they have to be. For instance, ADELFE proposes to transform the AMAS-ML model into a specific μADL model. This transformation is the result of our experience on programming cooperative agents. We propose to separate the behavioural concerns (all that is related to the decision process) from the other part of the cooperative agents [START_REF] Rougemaille | Model Driven Engineering for Designing Adaptive Multi-Agent Systems[END_REF]. On one hand, it provides an abstraction level to the AMAS developer who can focus on the cooperative behaviour of the agent without getting involved, for instance, in the communication mechanisms. On the other hand, it allows assigning the development of fundamental services, such as communications, to developers who are not necessary AMAS experts. Therefore, this separation task is enforced within a model-to-model transformation that ensure the respect of our proposition. In INGE- NIAS, model-to-model transformations are still not used. Currently, the code generation process uses templates. However, model-to-model transformations could be used as intermediate steps in the INGENIAS code generation. The Grasia research group is working on the application of model transformations for the improvement of meta-models, model transformations are planned to be created with an MTBE generator tool, whose prototype is available for practitioners (in Grasia web 5 ). The application of this MTBE tool for INGENIAS is described later in this paper.

In the context of MAS, transforming agent concepts is more efficient because of the semantic of agent, MAS concepts raise the level of abstraction over implementation concepts or even Object Oriented concepts. The abstraction gap between Agent Oriented Modelling and Object Oriented Modelling makes difficult to map these two technical spaces. In our experience, model-to-model transformations are used to narrow this gap in several steps. Moreover, the automation of this task increase the productivity because model transformations are defined once and used several times.

Model to Text transformations

Model-to-text transformations make it possible to generate the programming code of systems from models. In the experience of both agent-oriented methodologies INGE-NIAS and ADELFE, these transformations have saved time and effort in academic and industrial projects. However, these transformations also have some drawbacks, such as maintaining the consistency between models and code.

There is a part of code that is very similar from one MAS to another and can constitute an architecture. For instance, the code related to triggering agents or the communication among them is very similar and frequently part of a platform. Although the extension of this code, varies from one platform to another, the automatization of this task has saved time and effort in all the agent-oriented technologies (JADE, JavaLeap, web services, etc. for INGENIAS; Java classes for ADELFE).

In INGENIAS, code templates are linked to the key concepts of INGENIAS metamodel. The information of models instantiates code-templates for the code generation. For some years, IDK generates code for several platforms: JADE, JavaLeap, Prolog, Servlets Soar. However, the improvements in both INGENIAS meta-model and the code generator, made it expensive to maintain the support for all the platforms. For this reason, at the current version of INGENIAS, only the JADE platform is supported.

In ADELFE, there are two different code generation aspects. The first one is providing a specific platform for the execution of the application code. This platform is based on flexible agent principles [START_REF] Leriche | Adaptive Autonomous Agent Models for Open Distributed Systems[END_REF]. The generation of this platform takes as input the μADL model (arrows numbered 3 in the figure 3) and is performed by the MAY Eclipse plugin (Make Agents Yourself) [START_REF] Rougemaille | ADELFE Design, AMAS-ML in Action[END_REF]. MAY involves several phases of generation in which user's intervention is required, for example to choose pre-existing implementations of micro-components. The result of these generations is a platform consisting in a Java archive containing classes (factories, agents type, etc.) to create and support agents whose architectures were defined with μADL. Moreover, the resulting library is compliant with the standard JRE. The second aspects aims at providing the behavioural code of agents (arrow number 2 in the figure 3). This generation is achieved thanks to model to text ATL queries. From the decision module of each AMAS-ML agent, it generates Java conditional instructions which represent the different situations that the agent have to face and the actions that have to be performed in each situations. This portion of code is contained by a Java class which extends the agent type generated by MAY with the corresponding μADL model (see section 3.2).

The consistency between models and code is critical in MDE. In the INGENIAS methodology, the MAS designers agree that the best mechanism for the consistency is to keep some programming code at the model. Otherwise, the code would be overwritten each time the code is generated. This programmers' code is inserted in the model by means of a modelling concept called INGENIAS CodeComponent. The CodeUploader tool performs the reverse engineering. This tool receives the programmers' code that is embedded in the system code, and the tool inserts back this code in the model. The maintenance of models consistency is summarised with the following steps.

1. Developers design models expressed with the INGENIAS modelling language, by means of the IDK editor. 2. The IAF generates the system code from the models. 3. Developers write code within the systems code. 4. The CodeUploader tool uploads the written code in the models. 5. The cycle comes back to first step, if necessary.

In ADELFE, a reverse-engineering text-to-model transformation has been defined to maintain the consistency between μADL models and the agents of the generated platform. Technically, it uses the Java Development Tool (JDT) Eclipse plugin to navigate Java source code and the μADL plugin based on the Eclipse Modeling Framework (EMF) to create the model. The result is a plugin that contains the algorithm written in Java to maintain the consistency between μADL models and the platform code.

A key advantage of the model-to-text transformations is that they reduce the coupling between models and their implementation. Whatever are the changes made in the code generation it is still possible to regenerate the code with the same models. For example, migration from a platform to another only implies to modify the transformation, the models do not have to be modified. A drawback is that the consistency between the generated code and the models has to be managed. For this purpose INGENIAS use the Code Up-loader and ADELFE the reverse engineering. It is also important to notice that enabling source code modification is often a matter of efficiency for developpers. As long as MAS developers are computer scientits, they prefer to describe behaviours or algorithms in programming languages , which therefore require text-tomodel loader. However, when MDE users would be business specialists, the odds are that they will prefer to integrate this precise part within the model, even thought it requires to use graphical algorithmic language (like NXT-G graphical language of the LEGO R Mindstorms R NXT system) 6 .

Challenges for Agent-Oriented Model Driven Engineering

AOMDE faces some challenges that researchers need to address. Some of them are the model transformation by-example and the model upgrade.

Model Transformation By Example

The application of MTBE to agent-oriented software engineering can improve and fasten the AOMDE. MAS designers are hardly never used to model-transformation languages. Existing agent-oriented tools can be used to specify MAS models from which a MTBE approach can generate model transformations.

In particular, this work proposes that model transformations can be generated from examples in INGENIAS modelling. The MTBE approach is specially useful for generating these model transformations, because both source and target model examples can be defined with INGENIAS. Figure 4 shows some pairs of models, from which model transformations can be generated for INGENIAS methodology. The generated model transformation creates the agent specification (AgentModel diagram) from use cases (UseCase diagrams). As one can observe, this example needs to transform patterns of several modelling elements instead of simple one-to-one transformations. Existing MTBE algorithms and tools [START_REF] Varró | Automating model transformation by example using inductive logic programming[END_REF][START_REF] Wimmer | Towards Model Transformation Generation By-Example[END_REF] are only able to generate one-to-one transformations. For this reason, Grasia research group has defined an algorithm for MTBE that overcomes this limitation. This algorithm can generate many-to-many transformations and, in addition, it can create the appropriate mapping of attributes so the generated transformation propagate the information from the source to the target. A prototype tool (see Figure 5) implements this algorithm for generating ATL transformations from INGENIAS model, this tool is called MTGenerators.

The tool provides an interface (GUI) in which the user can select the input and output meta-models of the transformation. The user must define the meta-models with the ECore language and select the corresponding location paths in the top-left area of the GUI. The user can add the pairs of model with the top-right area of the generator tool, by selecting the corresponding location paths and adding them. After the automatic generation, the tool shows some logs in the Logs text area, confirming that the generation has finished successfully. The generated model transformation is shown in the bottom text area of Figure 5. In this manner, the user can examine the generated transformation.

In brief, the presented MTGenerator tool automatically generates a model transformation. Even if the user wants to manually improve the generated transformation, the tool saves time for the user because it provides a generated transformation as a basis for the final model transformation. First model upgrade relates to the multiplicity of the agent interactions in INGE-NIAS. IDK 2.6 interactions among agents were only one-to-one. IDK 2.7 supported one-to-many and one to one. In the update, the old interactions added a new attribute indicating their multiplicity. This kind of model update could be manually defined or generated with MTBE.

The second upgrade to introduce the notation for iterative interactions will soon be necessary. Currently, IDK 2.8 iterative interactions are not supported with a specific notation. In the IDK 2.8 models, the FrameFacts are used to repeat an interaction. A new IDK version will include soon the specification of iterative interactions without any ad-hoc mechanism. A transformation can achieve the mentioned update detecting a pattern of an iterative interaction and, substituting the mentioned patter with the new representation.

In INGENIAS, the kinds of diagram slightly evolves over time. Therefore, the models must change according to the new set of diagram types. The diagrams of the removed types must change to another similar diagram types. These transformations depend on the differences between the old and new sets of diagram types. For instance, if no diagram type is removed then, likely, no transformation is needed. If the diagram types are renamed or changed, a simple transformation is needed. If the diagrams types become more restricted (less entity or relationship types are allowed in a diagram type), then a more complex transformation is needed since some elements of the diagrams must be changed to other diagrams. The transformation must decide which diagram contains the changed elements or create a new diagram if necessary.

Related Work

The MDE principles are spreading in the AOSE community. This section presents some works that are particularly representative of this spread. However, it is not intended to present an exhaustive survey of the domain.

Tropos7 is a agent oriented development process [START_REF] Bresciani | Tropos: An agentoriented software development methodology[END_REF] that emphasis the expression of requirements. It is divided into five phases covering the whole life-cycle from the definition of early requirements to the implementation. Tropos is associated with a design tool called TAOM4E (Tool for visual Agent Oriented Modelling for the Eclipse platform) and based on the Eclipse plugins EMF and GEF (Graphical Editing Framework) [START_REF] Bertolini | A tropos model-driven development environment[END_REF]. TAOM4E uses a specific modelling language which was previously defined in the TAOM tool. Tropos also introduces a model driven approach based on the MDA principles proposed by the OMG (see section 2.1). [START_REF] Perini | Automating model transformations in agent-oriented modelling[END_REF] presents the different types of transformation which were implemented in Tropos for model refinement and translation of preliminary UML2.0 models into Tropos models. TAOM4E offers additional code generation tool 8 for the agent platform JADEX [START_REF] Penserini | A design framework for generating bdi-agents from goal models[END_REF]. However, for the moment TAOM4E do not provide means to keep model and code consistent.

Prometheus is a agent oriented methodology [START_REF] Padgham | Prometheus: A methodology for developing intelligent agents[END_REF] which is related to a specific design environment : the Prometheus Design Tool (PDT)9 [START_REF] Padgham | Tool support for agent development using the prometheus methodology[END_REF]. Prometheus covers all phases since the specifications of the system to test or debugging. However, PDT provides means to achieve the three main phases related to system design: the system specification, the architectural design and the detailed design. In the first step designers determine system scenarios, actors interacting with the system in these scenarios, goals of the system, the different roles, their perceptions, their actions, data, etc. The system specification is a preliminary view of the system focussing on goals, roles and scenarios. This first modelling phase is followed by a more precise design that leads to the definition of the agent playing as well as their relationship. Finally, the last step describes the internal structure of the agents in terms of capability, behaviour and protocols in which they play a role. PDT allows cross-checking model verification to ensure the consistency of its models (system specification, architectural and detailed design). Moreover, a mapping between the Prometheus models and the JACK platform has been defined [START_REF] Sudeikat | Evaluation of agent-oriented software methodologies -examination of the gap between modeling and platform[END_REF]. This mapping is implemented in the PDT to generate code [START_REF] Padgham | AUML protocols and code generation in the Prometheus design tool[END_REF].

MDAD (Model Driven Agent Development) is a development process that applies MDA principles (see section 2.1) for the development of MAS [START_REF] Jarraya | Towards a model driven process for multi-agent system[END_REF]. The PIM is defined thanks to UML based meta-models (profile), covering aspects such as the domain, the agents and the organisation. In MDAD the PIM is transformed into a PSM conforming to the INteractive Agent Framework (INAF) meta-model. Jarraya in [START_REF] Jarraya | Towards a model driven process for multi-agent system[END_REF] presents imperative rules to generate the code of the application from the PSM. The generated code is compliant with the INAF architecture.

ASPECS is a model driven methodology based on PASSI and dedicated to the development of complex systems [START_REF] Cossentino | A holonic metamodel for agent-oriented analysis and design[END_REF]. It is specially dedicated to the design of holonic systems. It proposes a meta-model separated in three related viewpoints, inherited from PASSI, the problem, the agency and the solution domain. The application of the process result in a specific model (PSM) that can be use to generate the code of the application. The code is compliant to the Janus execution platform 10 which shared the same holonic system principles that the solution domain meta-model.

All the aforementioned projects adopt a Model Driven approach to facilitate MAS development. Most of them used model-to-text transformations and some of them define model-to-model transformations to refine PIM into PSM. However, INGENIAS and ADELFE propose to deal with a wide range of abstraction levels, reverse engineering, re-factoring and are initiating works on MTBE to automate the definition of model transformations. We advocate that these issues that led us to AOMDE should profit to all the MAS methodologies and design tools.

Conclusion

Agent-Oriented Model-Driven Engineering (AOMDE) proposes the application of Model-Driven Engineering principles to MAS development. AOMDE is grounded in the following statements. First of all, MAS deals with a wide range of abstraction levels, model transformations can bridge the gap between these levels. Secondly, MAS concepts are continually evolving, meta-models can precisely describe this evolution and support the maintenance of design tool. Finally MAS languages are semantically richer than object oriented languages for instance. Thus, code generation result is larger than the code generate from UML model and the productivity is higher.

Nevertheless, there is still some challenges in AOMDE to cope with. The MTBE is the process of generating model transformations from examples, which is specially relevant for AOMDE since this approach deals with complex transformations between patterns of model elements. The model upgrade is also a mandatory challenge of AOMDE because of the frequent changes in MAS modelling languages. AOMDE rises specifics needs for which specific solutions are required. These solutions can also profit the whole model-driven community.

3 .Fig. 1 :

 31 Fig. 1: Description of the Model Transformation By-Example (MTBE)

Fig. 2 :

 2 Fig. 2: The Most Relevant INGENIAS Notation.

Fig. 3 :

 3 Fig. 3: General overview of ADELFE model driven implementation phase. Each arrow represents either a transformation or a generation step.

Fig. 4 :

 4 Fig. 4: Model transformations for generating the Specification of Roles. Each square represent a model example for MTBE. Each pair of models is related with an arrow and a number, in which the source model and target model are respectively situated at both sides of the arrow.

Fig. 5 :

 5 Fig. 5: Model-Transformation Generator Tool

ADELFE ("Atelier de Développement de Logiciels à Fonctionnalité Emergente") is toolkit for designing softwares with emergent functionalities. It was a French RNTL-funded project(2000)(2001)(2002)(2003)

http://www.irit.fr/PERSONNEL/SMAC/arcangeli/JavAct.html

http://grasia.fdi.ucm.es

http://www.ortop.org/NXT_Tutorial/

http://www.troposproject.org/

http://se.itc.it/morandini/home.html

http://www.cs.rmit.edu.au/agents/pdt/

http://www.janus-project.org