S Barrat
email: barrat@loria.fr

S Tabbone
email: tabbone@loria.fr

Classification and automatic annotation extension of images using Bayesian network

Keywords: probabilistic graphical models, Bayesian networks, image classification, image annotation

In many vision problems, instead of having fully annotated training data, it is easier to obtain just a subset of data with annotations, because it is less restrictive for the user. For this reason, in this paper, we consider especially the problem of classifying weakly-annotated images, where just a small subset of the database is annotated with keywords. In this paper we present and evaluate a new method which improves the effectiveness of content-based image classification, by integrating semantic concepts extracted from text, and by automatically extending annotations to the images with missing keywords. Our model is inspired from the probabilistic graphical model theory: we propose a hierarchical mixture model which enables to handle missing values. Results of visualtextual classification, reported on a database of images collected from the Web, partially and manually annotated, show an improvement by 32.3% in terms of recognition rate against only visual information classification. Besides the automatic annotation extension with our model for images with missing keywords outperforms the visual-textual classification by 6.8%. Finally the proposed method is experimentally competitive with the state-of-art classifiers.

Introduction

The rapid growth of internet and multimedia information has shown a need in the development of multimedia information retrieval techniques, especially the image retrieval. We can distinguish two main trends. The first one, called "text-based image retrieval", consists in applying textretrieval techniques from fully annotated images. The text describes high-level concepts but this technique requires a tedious work of annotation. The second approach, called "content-based image retrieval" is a more young field. These methods rely on visual features (color, texture or shape) computed automatically, and retrieve images using a similarity measure. However the obtained performances are not really acceptable, except in the case of well-focused corpus.

In order to improve the recognition, a solution consists in combining visual and semantic informations. Some researchers have already explored this possibility [START_REF] Barnard | matching words and pictures[END_REF][START_REF] Benitez | Perceptual knowledge construction from annotated image collections[END_REF][START_REF] Grosky | Negotiating the semantic gap: From feature maps to semantic landscapes[END_REF][START_REF] Kherfi | Combining visual features with semantics for a more effective image retrieval[END_REF]. Finally, automatic image annotation can be used in image retrieval systems to organize and locate images of interest from a database, or to perform visualtextual classification. This method can be regarded as a type of multi-class image classification with a very large number of classes, as large as the vocabulary size. Typically, image analysis in the form of extracted feature vectors and the training annotation words are used by machine learning techniques to attempt to automatically apply annotations to new images. Many works have been proposed in this sense [START_REF] Blei | Modeling annotated data[END_REF][START_REF] Gao | Automatic image annotation by incorporating feature hierarchy and boosting to scale up svm classifiers[END_REF][START_REF] Yang | Region-based image annotation using asymmetrical support vector machine-based multiple-instance learning[END_REF][START_REF] Wang | Image annotation refinement using random walk with restarts[END_REF][START_REF] Rui | Bipartite graph reinforcement model for web image annotation[END_REF][START_REF] Feng | Multiple bernoulli relevance models for image and video annotation[END_REF]. In this perspective, the contribution of this paper is to propose a scheme for image classification optimization, by using a joint visual-text clustering approach and automatically extending image annotations.

Motivations

The motivation of the model presented here is to use it for the both tasks of weakly-annotated image classification and annotation. In fact the classification methods before mentionned are efficient but they requires that all image, or image blobs are annotated. Moreover the annotation models are not enable to classify images. The proposed model does not require that all images be annotated: when an image is weakly annotated, the missing keywords are considered as missing values. Besides it enables to automattically extend existing annotations to weaklyannotated images, without User intervention. The model [START_REF] Blei | Modeling annotated data[END_REF] is the most related to our approach, because it enables to classify images based on visual and textual features and to automatically annotate new images. However our model is less restrictive for the user. In fact our classifier does not need that all images be annotated, and the existing keywords are associated to the whole images, not to image regions. The proposed approach is derived from the probabilistic graphical model theory. We introduce a method to deal with missing data in the context of text annotated images as defined in [START_REF] Blei | Modeling annotated data[END_REF][START_REF] Kherfi | Combining visual features with semantics for a more effective image retrieval[END_REF]. The uncertainty around the association between a set of keywords and an image is tackled by a joint probability distribution over the dictionary of keywords and the numerical features extracted from our collection of grey-level and color images. The rest of this paper is organized as follows: Section 3 decribes the probabilistic model of weakly-annotated image representation and how to use it to classify and extend existing annotations to images. Section 4 presents the experimental results. Finally conclusions and future works are given in Section 5.

Representation and classification of weakly-annotated images

Our work is focused on weakly-annotated image modelling and classification. Now visual descriptors often provide vectors of continuous values, and the associated keywords often correspond to discrete variables. So we have chosen to construct a Bayesian classifier which allows for the discrete and continuous variable combination and the problem of missing values handling. Let f j be a query image characterized by a set of features F . F is composed of:

m visual features, denoted v 1 , ..., v m , -n possible keywords, denoted KW 1, ..., KW n.

The chosen visual features are issued from one color descriptor, a color histogram [START_REF] Swain | Color indexing[END_REF], and one shape descriptor based on the Fourier/Radon transform [START_REF] Tabbone | Technical Symbols Recognition Using the Twodimensional Radon Transform[END_REF]. We are interested in the probability distributions of these features and their conditional dependence relations. Let us consider the visual features as continuous random variables and theirs associated keywords as discrete variables. This model is too big to be represented as a unique joint probability distribution, therefore it is required to introduce some sparse and structural a priori knowledge. The probabilistic graphical models, and especially Bayesian networks, are a good way to solve this kind of problem. In fact within Bayesian networks the joint probability distribution is replaced by a sparse representation only among the variables directly influencing one another. Interactions among indirectly-related variables are then computed by propagating inference through a graph of these direct connections. Consequently the Bayesian networks are a simple way to represent a joint probability distribution over a set of random variables, to visualize the conditional properties and to compute complex operations like probability learning and inference, with graphical manipulations. Then a Bayesian network seems to be appropriate to represent and classify images and associated keywords.

A Gaussian-Mixtures and Multinomial mixture model

We present a hierarchical probabilistic model of multiple-type data (images and associated keywords) in order to classify large annotated image databases. A Gaussian Mixtures and Multinomial Mixture model is proposed. In fact, the observation of some peaks on the different histograms of the feature variables, has led us to consider that the visual features can be estimated by mixtures of Gaussian densities. The discrete variables corresponding to the possible keywords are assumed to be distributed as a multinomial distribution over the vocabulary of keywords. Now let F be the training set composed of m instances f 1i , ..., f mi , ∀i ∈ {1, ..., n}, where n is the dimension of the signatures provided by the concatenation of the feature vectors issued from the computation of all the descriptors on each image on the training set. Each instance f j , ∀j ∈ {1, ..., m} is then characterized by n continuous variables. A supervised classification is considered then F instances are divided into k classes c 1 , ..., c k . Let G 1 , ..., G g be g groups whose each has a Gaussian density with a mean µ l , ∀l ∈ {1, ..., g} and a covariance matrix l . Besides, let π 1 , ..., π g be the proportions of the different groups, θ l = (µ l , l ) the parameter of each Gaussian and Φ = (π 1 , π 1 , ..., π g , θ 1 , ..., θ g ) the global mixture parameter. Then the probability density of F conditionally to the class c i , ∀i ∈ {1, ..., k} can be defined by

P (f, Φ) = g l=1 π l p(f, θ l )
where p(f, θ l ) is the multivariate Gaussian defined by the parameter θ l .

Then, we have one Gaussian Mixture Model per class. This problem can be represented by the probabilistic graphical model in Figure 1, where:

-The "Class" node is a discrete node, which can take k values corresponding to the pre-defined classes c 1 , ..., c k . -The "Component" node is a discrete node which corresponds to the components (i.e the groups G 1 , ..., G g ) of the mixtures. This variable can take g values, i.e the number of Gaussians used to compute the mixtures. It's an hidden variable which represents the weight of each group (i.e the π l , ∀l ∈ {1, ..., g}). -The "Gaussian"node is a continuous variable which represents each Gaussian G l , ∀ ∈ {l = 1, ..., g} with its own parameter (θ l = (µ l , l )). It corresponds to the set of feature vectors in each class. -Finally the edges represent the effect of the class on each Gaussian parameter and its associated weight. The green circle is just used to show the relation between the proposed probabilistic graphical model and GMMs: we have one GMM (encircled in green), composed of Gaussians and their associated weight, per class.

Now the model can be completed by the discrete variables, denoted KW 1, ..., KW n, corresponding to the possible keywords associated to the images. Dirichlet priors [START_REF] Robert | A decision-Theoretic Motivation[END_REF], have been used for the probability estimation of the variables KW 1, ..., KW n. That is we introduce additional pseudo counts at every instance in order to ensure that they are all "virtually" represented in the training set. Therefore every instance, even if it is not represented in the training set, will have a not null probability. Like the continuous variables corresponding to the visual features, the discrete variables corresponding to the keywords are included in the graphical model by connecting them to the class variable.

Then our classifier can be depicted by the Figure 2. The hidden variable "α" shows that a Dirichlet prior is used. The box around the variable KW denotes n repetitions of KW , for each keyword. This Bayesian classifier means that each image and its keywords are assumed to have been generated conditional on the same class. Therefore the resulting multinomial and Gaussian mixture parameters should correspond: concretely if an image, represented by visual descriptors, has an high probability under a certain class, then its keywords should have an high probability under the same class.

Gaussian Class Component GMM Fig. 1. A Probabilistic graphical model as GMMs

Parameter learning and inference

The EM algorithm has been used to learn the Gaussian mixture parameters. But our major problem deals with missing values. Indeed only some data are fully observed. It's the case of all visual features for color images or just shape features for grey-level images. On the contrary the color features for grey-level images, and especially some keywords for a large subset of images, are missing. Concerning the visual features, the missing values are clearly homogeneously distributed (because they correspond to grey-level images). But the missing values are randomly distributed for the variables KW i, ∀i ∈ {1, ..., n}. This kind of problem can be tackled with the EM algorithm too. The general purpose of this algorithm, explained in detail in [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF] consists in computing, in an iterative way, the likelihood maximum when the instances can be viewed as incomplete data: each iteration consists of an Expectation computation step before a Maximization step. This algorithm has been chosen for its simplicity and generality. Applied to the parameter learning problem, the EM algorithm starts off with the random model initialisation, then, at each iteration, the parameters are updated in order to obtain a local optimal of the maximum-likelihood. An inference algorithm is required to compute the expected sufficient statistics in the expectation step. Then, in the maximization step, the parameters of the model are adjusted to fit the data.

An inference algorithm is also necessary to classify new images. Indeed, the inference process consists in computing posterior probability distributions of one or several other subsets of nodes. In the case of classification, the class node is inferred. According to our Bayesian network topology, the inference process propagates the values from the image feature level represented by the "Gaussian" A message passing algorithm [START_REF] Kim | A computational model for combined causal and diagnostic reasoning in inference systems[END_REF] is applied to the network. In this technique, each node is associated to a processor, which can send some messages to its neighbors, in an asynchronous way, until it reaches a stability.

Thus a query image f j , characterized by its visual features v j1 , ..., v jm and its possible keywords KW 1 j , ..., KW n j is considered as an "evidence" represented by: P (f j ) = P (v j1 , ..., v jm , KW 1 j , ..., KW n j ) = 1 when the network is evaluated. Thanks to the inference algorithm, the probabilities of each node are updated in function of this evidence. After the belief propagation, we know, ∀i ∈ {1, ..., k}, the posterior probability P (c i |f j ) = P (c i |v j1 , ..., v jm , KW 1 j , ..., KW n j ). The query f j is assigned to the class c i which maximizes this probability.

Annotation extension of images

Given an image without keyword, or a weakly annotated image, the proposed Bayesian model before described can be used to compute a distribution over words conditionally to the image and its possible existing keywords. In fact, for a query image f j annotated by k, ∀k ∈ {0, ..., n} keywords, where n is the maximum keyword number per image, the inference algorithm enables to compute the posterior probability P (KW ij |f j , KW 1 , ..., KW k), ∀i ∈ {k + 1, ..., n}. This distribution represents a prediction of the missing keywords for that image.

For example, let us consider Table 1 which presents 3 images with possible keywords and the keywords obtained after automatic annotation extension. The first image, without annotation, has been annotated by 2 suitable keywords. In the same way, the second image annotation, composed at the beginning of 2 keywords, has been extended to 3 keywords. The added keyword, "sunset" is image initial possible keywords keywords after annotation extension bridge water bridge bridge cloud cloud sunset bridge bridge cloud sunset Table 1. Examples of images and possible keywords before and after annotation extension suitable. On the contrary, the third image, initially annotated by 1 keyword, has obtained 2 other keywords after the automatic extension. But the second new keyword, "sunset" is wrong. This mistake is probably due to the large number of database images annotated by these 3 keywords "bridge", "cloud" and "sunset", and the inference algorithm.

Experimental results

In this section, we present an evaluation of our model on more than 3000 free images collected from the Web, and kindly provided by Kherfi et al. [START_REF] Kherfi | Combining visual features with semantics for a more effective image retrieval[END_REF]. These images are split up into 16 classes. For example, 4 images of the class "horse" are given in Figure 3. 65% of the image database have been manually annotated by 1 keyword, 28% by 2 keywords and 6% by 3 keywords, using a vocabulary set of 39 keywords. For example, among the 4 images from the Figure 3, the first image is annotated by the 2 keywords "animal" and "horse". The second is only annotated by one keyword: "animal". The others have not been annotated. We have evaluated our method by performing 5 cross validations whose each proportion of the training set is 25%, 35%, 50%, 65% and 75% of the database, the remaining respectively 75%, 65%, 50%, 35% and 25% are hold for test set. In each case the tests are repeated 10 times in order that each database instance would be used for the training and the test. For each training set size, the recognition rate is obtained by taking the mean recognition rate of the 10 tests. Since we want to improve the recognition rate by introducing semantics, and automatically extending image annotations, we limit ourselves to the experiments comparing:

the visual-textual classification to the only visual information classification, -the visual-textual classification before and after automatic annotation extension of all images, -the proposed model of visual-textual classification to two state-of-art classifiers

Let us consider Table 2. The notation "C + S" means that the color and shape descriptors ("C" for Color, "S" for Shape) have been combined. The notation "C + S + KW" indicates that both visual descriptors and textual information ("KW" for Keywords) have been combined. The recognition rates confirm that combining visual with semantic features performs always better than any of them alone. In fact we observe that the combination of our visual features and keywords (when they are available) increases the recognition rate by 38.5% compared to the results of color information alone, 58% compared to the shape information classification and 37% compared to the only textual information classification. Besides we can notice that for all experiments, combining the both visual descriptors is better, by 16% on average, to use just one of them. Finally, the visual-textual classification shows an improvement by 32.3% in terms of recognition rate against only visual information classification. Then, Table 3 shows the effectiveness of our approach (GM-M mixture) compared to the SVM and FKNN classifiers. The results have been obtained by using the visual features and theirs possible associated keywords. It appears that the GM-M mixture results are always better than the ones of SVM and FKNN results.

Finally, annotations have been extended to all images of the database in order that each would be annotated by 3 keywords. Then, to evaluate the quality of this annotation extension, the visual-textual classification has been re-done, with the same specifications as in Table 2. Table 4 shows the efficiency of our automatic annotation extension. In fact, the recognition rates after automatic annotation extension are always better than before. Moreover the automatic annotation extension outperforms the recognition by 6.8% on average. 4. Recognition rates (in %), obtained by the GM-M model, of visual-textual classification before and after automatic annotation extension

Conclusion and future works

We have proposed an efficient model which enables to combine visual and textual information, handle missing values and extend image annotations to other images. Our experiments have been done on a partially annotated Web image database. The results show that our visual-textual classification method improves the recognition rate compared to the only visual information classification. Moreover our Bayesian network can be used to extend image annotations, what outperforms the recognition rate. Finally the proposed method is competitive with state-of-art classifiers. Further works will be devoted to capture the user's preference by considering a relevance feedback process. More precisely, the user's preference can be represented by the network parameter update (i.e the probabilities of each variable in function of the new classified instance) during the inference process.

Fig. 2 .

 2 Fig. 2. The Gaussian-Mixtures and Multinomial mixture model

Fig. 3 .

 3 Fig. 3. Examples of horse-class images

Table 2 .

 2 Recognition rates (in %), obtained by the GM-M model, of only visual classification vs. visual-textual classification

	Specifications training part test part	Color Shape Keywords C + S C + S + KW
	25%	75%	35	17.8	36.6	39.4	69.7
	35%	65%	36.9 18.1	38.9	42.2	74.4
	50%	50%	38.7 18.5	41.1	45	79.1
	65%	35%	41.1 20.6	41.5	46.6	81.7
	75%	25%	43.5 21.8	45.1	52.9	82.9


Tim Krake

Malte Von Scheven

Jan Gade

Moataz Abdelaal

Daniel Weiskopf

Manfred Bischoff

Alexander Popp

Review of łEfficient update of redundancy matrices for truss and frame structuresž

Reviewer 1 (Anonymous)

Reviewer The article presents an interesting calculation procedure of the so called žredundancy distributionž by assigning a significance rating to all members in frame or truss structures with respect to their significance for the structure stability. Moreover, an appropriate constitutive transformation renders the assessment of the redundancy distribution less computationally intensive. In the reviewer's opinion this can be of advantage especially in the application of active adaptive structures reacting to abrupt extreme loading events (which is also related to the work of the authors in the funding research programs). It is overall well-structured and the methodology is demonstrated with adequate explanations and examples. The following comments should be taken into consideration prior to approval for publication, which are provided in good faith and with the hope to improve the manuscript.

Reviewer As currently formulated, the title may be misguiding: it implies that other possible updating procedures are łinefficientž. This should be revised. The novelty of the study should also be demonstrated in a more specific manner.

Authors We agree with the reviewer that the novelty of the study should be presented more specifically. Therefore, we added a statement in Section 1 (second last paragraph and in the bullet point list).

Concerning the title, however, we partly disagree with the reviewer's opinion and argue that the current title is appropriate because there is no generic, efficient update procedure for the redundancy matrix at all; besides the work of Chen et al. (2010), where a formula is presented that only addresses the removing of single elements from truss structures and that does not provide a framework for multiple, interchangeable (with adding and exchanging) updates. Hence, the only łcomparablež procedure is to compute the redundancy matrix from scratch (after updating the matrices A and C), resulting in an inefficient updating procedure.

Reviewer The limitations of the proposed methodology and analysis technique are not clarified. The examples claim that the analysis is done for a high-rise building (4.2), but essentially the examples presents 4-storey 2-dimensional frames. This is an oversimplification, since 3-D effects are not accounted for, whereas the building typology is not one of a high-rise and the design situations do not account for transverse loads and second-order phenomena. These are distinctive characteristics of high-rise buildings and the example should be enriched accordingly or the example description should be rephrased (e.g. the authors may wish to use the definition łmulti-storey frame structurež or similar).

Authors The redundancy matrix as defined by Bahndorf 1991, Ströbel 1997, and von Scheven et al. 2021 is independent of the loading situation and in this contribution only applied to linear problems. These limitations are stated in Section 2.2. Therefore, łtransverse loads and second-order effectsž are not relevant for this contribution.

We agree with the reviewer that the name of example 2 (see Section 4.2) is not appropriate. To be able to visualize the results, the łhigh-rise buildingž became smaller and smaller during discussions and ended up being only a multi-storey frame structure. We have adapted the heading and captions accordingly.

Reviewer Also, the connections of the members are modelled as idealised hinges or rigid connections, which is also rarely the case in reality. In any case, the limitations of applicability should be noted.

Authors The redundancy matrix and our proposed update procedures can also be applied to more complex connections including, e.g., spring elements. In our examples, we restricted ourselves to simple connections to enable a good comprehensibility. We have added a comment about this simplification in the introduction of example 2 (see Section 4.2).

Reviewer The model assumptions (matrix symmetry, regularity, Pellegrino criterion) should be justified further.

Authors We have further clarified the explanation of the symmetry of the stiffness matrix in Equation ( 2). The scope of this paper is limited to statically indeterminate and kinematically determinate structures. For kinematically indeterminate structures the the definition of the redundancy matrix in Equation ( 4) cannot be used directly due to the inverse of K. There exist contributions about the calculation of the redundancy matrix for kinematically indeterminate structures, and the application of our update procedures to those problems could be possible. We consider this as future work and have added a respective remark in the conclusions.

Reviewer In continuation of the above, the sensitivity of the model in changes e.g. in stiffness of the joints, defects or deterioration of the member materials should be discussed, as it may influence the redundancy distribution dramatically, e.g. even in terms of failure sequences.

Authors The scope of this paper is the efficient update procedure for the redundancy matrix. The mechanical interpretation and application of the redundancy matrix are beyond the scope and can be found in Linkwitz 1961, Bahndorf 1991, Ströbel 1997, von Scheven et al. 2021, and Gade et al. 2021. We have added a comment about this restriction in the introduction of the paper (see Section 1).

Reviewer Without having rerun the calculations independently, the results of the model are to some extend counter-intuitive, e.g. in Figure 5, top left segment: Failure of the horizontal element / beam would lead to immediate collapse of the vertical element / column due to their hinged connections; in fact failure of the outer left column does not lead to collapse, as the beam is a fixed cantilever ś it would hence be expected that the redundancy index of the member would be different. Perhaps it is also necessary to elaborate further on the physical meaning and possible ranges of the redundancy indices.

Authors The at first sight strange redundancy distribution in Figure 5 appears due to the differences in the bending and elongation stiffness and the higher number of load-carrying mechanisms in the beam compared to the truss element. However, the mechanical interpretation of the redundancy matrix is beyond the scope of this paper.

Reviewer Previous studies on system redundancy and its association to codified robustness-based structural design are presented by Spyridis and Strauss (MDPI Buildings, 2020) and Strauss et al. (Beton Kalender 2022). These also describe probabilistic elaboration of redundancy calculations, progressive collapse criteria and possible applicability on adaptive structures. They authors may wish to draw references from these documents with regard to the above issues. Authors Thank you for pointing to these references. We have included the reference by Spyridis and Strauss (MDPI Buildings, 2020) in the introduction as it is more focused on the redundancy matrix compared to Strauss et al. (Beton Kalender 2022).

Review of version 2

Permalink: arXiv:2205.12264v2

Reviewer 1 (Anonymous)

Reviewer No further comment, the responses justify my recommendation for acceptance with the 2d submitted version.

Editor's assessment (Alexander Popp)

Two independent reviews by expert referees had been requested and agreed upon for the given paper. The first review, as printed above, evaluated the contribution very positively asides a few minor comments. Unfortunately, the second reviewer did not provide a report as promised and the search for another second reviewer was not successful over a period of several months. Since the first review has been positive from the beginning, and since the authors had provided a convincing response on the few minor comments, the editor exceptionally moved on and reached an editorial decision with just one external review. To further support this decision, a few editorial comments are collected in the following, which are meant to complement the external review report.

With their focus on redundancy matrices for truss and frame structures, the authors address a fundamental, yet often overlooked topic in structural design and analysis, particularly with respect to a structure's load carrying behavior. The characteristic feature of redundancy matrices is their ability to provide a meaningful description of the spatial distribution of the degree of state indeterminacy, and not just an aggregated global number. Seemingly forgotten for quite a while, the authors have successfully revisited the topic in recent years and have added valuable continuum-mechanical insights. If a structure is modified, as is typical for iterative design processes, the computational complexity associated with the (re)computation of the modified redundancy matrix can become prohibitive. The present paper proposes, outlines and quantitatively assesses a new strategy for efficiently updating redundancy matrices for the most typical structural design modifications. At its methodological core, new algebraic procedures are provided for the three exemplary scenarios of adding elements to a structural design, removing elements or exchanging elements. The work is limited to statically indeterminate but kinematically determinate structures, where the stiffness matrix K is invertible. All numerical examples are clearly presented and convincingly illustrate the applicability of the proposed methods to structures of practical interest. Numerical performance tests give first insights into the efficiency gains and simulation speedups that can possibly be achieved.

Open Access This review is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the authorsśthe copyright holder. To view a copy of this license, visit creativecommons.org/licenses/by/4.0.


𝑎,𝑏 Olga Chuchuk
email: olga.chuchuk@cern.ch

Giovanni Neglia
email: giovanni.neglia@inria.fr

Markus Schulz
email: markus.schulz@cern.ch

Dirk Duellmann
email: dirk.duellmann@cern.ch

PoS(ISGC2022)

Caching can effectively reduce the cost of serving content and improve the user experience. In this paper, we explore the benefits of caching for existing scientific workloads, taking the Worldwide LHC (Large Hadron Collider) Computing Grid as an example. It is a globally distributed system that stores and processes multiple hundred petabytes of data and serves the needs of thousands of scientists around the globe. Scientific computation differs from other applications like video streaming as file sizes vary from a few bytes to terabytes and logical links between the files affect user access patterns. These factors profoundly influence caches' performance and, therefore, should be carefully analyzed to select which caching policy to deploy or to design new ones. In this work, we study how the hierarchical organization of the LHC physics data into files and groups of files called datasets affects the request patterns. We then propose new caching policies that exploit dataset-specific knowledge and compare them with file-based ones. Moreover, we show that limited connectivity between the computing and storage sites leads to the delayed hits phenomenon and estimate the consequent reduction in the potential benefits of caching.

Introduction

The term caching covers an array of solutions at different levels of computing/communication architectures, ranging from microprocessor caches to local disk caches, to storage clusters in geographically distributed content delivery networks. The core concept is to place separate storage media closer to the end user (either an actual user or a processing unit), to reduce the time to serve user requests and/or the amount of data flowing between the main storage and the user.

In this paper, we study cache management in large, geographically distributed systems used for scientific computation. In particular, we consider as a use-case the Large Hadron Collider (LHC) located at CERN (the European Center of Nuclear Research), which is the world's largest particle accelerator. This unique and complex facility allows scientists to study elementary particles and fundamental laws of physics while posing specific storage and computing challenges. To solve them, scientists and engineers have developed the Worldwide LHC Computing Grid (WLCG), which is a federation of large and small computing centers distributed around the globe (in total, around 170 sites located on 5 different continents). The WLCG resources are predominantly shared by four large detector-experiments: LHCb, CMS, ATLAS, and ALICE, each of which is carried out by an international consortium.

The optimal use of the WLCG is crucial for the success of the whole LHC program, especially in light of the ongoing upgrade of the accelerator toward the new High Luminosity LHC (HL-LHC). This will make it possible to obtain higher energies and a much greater number of collisions, which may lead physicists to new scientific discoveries. The consequent increase in data volume and data access rates is expected to outpace the gain from upgrading the infrastructure with next-generation hardware: improving storage resource efficiency is necessary.

Contributions. We extracted a three-month trace of user accesses of the ATLAS experiment at the CERN data center (the largest of the WLCG sites). We analyze this trace, highlighting key findings relevant to the analysis and design of caching systems. Besides a highly heterogeneous distribution of file sizes (spanning 11 orders of magnitude), we note a strong request correlation across certain groups of files (called datasets), which are related to the same physics analyses. We then compare the performance on this trace of widely used caching policies, like LRU, 2-LRU [START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF][START_REF] Mattson | Evaluation techniques for storage hierarchies[END_REF][START_REF] Montazeri | LRU-2 vs 2-LRU: An Analytical Study[END_REF] and clairvoyant optimal policies [START_REF] Berger | Practical bounds on optimal caching with variable object sizes[END_REF] that minimize either the File Miss Ratio (FMR) or the Byte Miss Ratio (BMR). We do so by estimating lower bounds for the minimum FMR achievable by clairvoyant reactive policies with the PFOO-L algorithm [START_REF] Berger | Practical bounds on optimal caching with variable object sizes[END_REF], and for the BMR with the new modified algorithm we propose (PFOO-L.Bytes). We observe abundant space for improvement between the standard techniques and the optimal performance.

Motivated by these findings, we propose simple modifications to LRU that evict or prefetch files based on dataset membership information (Dataset Evict LRU and Dataset LRU). Dataset LRU achieves a significant improvement and, thanks to prefetching, can even outperform clairvoyant reactive, i.e., non-prefetching, policies. Unfortunately, the improvement comes at the cost of increased load on the links connecting the cache to the main data store, in comparison to the classic LRU-like policies.

We study then the effect of limited connectivity between the cache and the main data store, which is particularly relevant in WLCG's remote computation setting, where CPU resources are geographically decoupled from the data storage. In this scenario, the increased latency to fetch the

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes Olga Chuchuk data leads to the phenomenon called 'delayed hits' [START_REF] Atre | Caching with delayed hits[END_REF], or also 'virtual hits' [START_REF] Dai | Analysis of tandem PIT and CS with non-zero download delay[END_REF]. We observe that delayed hits negatively impact all caching policies (as expected) and Dataset LRU in particular, to the point that its performance gain may disappear in small cache size and/or small bandwidth settings. We characterize experimentally the regime where the adoption of Dataset LRU is beneficial.

Roadmap. The paper is organized as follows. Section 2 describes the WLCG architecture, reviews previous work on caching, and defines metrics of interest and known bounds for the performance of caching policies. In Sec. 3 we present our algorithm to evaluate the minimum achievable BMR for reactive policies. We describe the WLCG file access trace in Sec. 4. In Sec. 5 we compare the performance of file-based and dataset-based caching policies and evaluate the influence of delayed hits. Conclusions and future research directions are discussed in Sec. 6.

Background and Related Work

The WLCG as a use case for scientific workloads

Since the start of the Large Hadron Collider (LHC) in 2008, the Worldwide LHC Computing Grid (WLCG) has been serving the needs of the largest LHC experiments' detectors, i.e., ATLAS, CMS, LHCb, and ALICE. Yearly, the LHC generates more than 90 PB of data, with raw data rates up to 100 GB/s. Managing such data volumes requires the best approaches in computing and storage system architectures. Today, the WLCG appears as a system of interconnected smaller and larger computing facilities, fully or partially dedicated to the storage and computing tasks of the LHC experiments. Appendix A provides additional information about the WLCG architecture.

The typical WLCG data processing workflow can be roughly divided into reconstruction and analysis activities. The reconstruction activities are aimed at preparing the raw data coming from the LHC detectors for the physics users, and they are run through large data processing campaigns according to a precise schedule. On the contrary, analysis tasks work with the previously generated analysis files and are relatively sporadic, as they are independently triggered by different users according to their needs. In our studies, we concentrate on the analysis activities, which are less predictable and, therefore, not amenable to planned resources provisioning.

Currently, most of such analysis is performed in the so-called "local grid analysis" mode, where data expected to be processed is moved/replicated to the processing site before the computation starts. This mode requires manual intervention of the physics groups to curate the data transfer process and leads to an abundance of data replicas throughout the WLCG, which is incompatible with large data volumes generated by the future HL-LHC. For these reasons, in this paper, we evaluate a remote computation model, in which the processing unit automatically fetches data over the WLCG network based on users' requests. In this way, there is no need to couple the CPU resources with large (and expensive) permanent storage systems. Instead, working data can be placed in small-size caches, implemented through simple storage systems with a low level of service. With the introduction of such caching layer, more and more WLCG sites could be operated in this mode, reducing hardware and operation costs.

Another characteristic of the WLCG use case is that the analysis data formats have a particular hierarchical structure. The analyses process independent physics events, which are described as distinct records. Together, all the records meaningful for the same physics analysis form a logical

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes Olga Chuchuk entity called a dataset. Each dataset was divided into files based mainly on the storage and network system requirements and out of convenience for the users to process the data. As physics events are independent, records in the same file, as well as files in the same dataset, could be processed in any order, leading to embarrassingly parallel workloads.

Caching Policies

Caching policies determine which files should be stored or evicted from the cache. When the request process is stationary and file sizes are equal, LFU (Least Frequently Used) algorithm is the optimal non-anticipative reactive policy [START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF][START_REF] Lee | LRFU: A spectrum of policies that subsumes the least recently used and least frequently used policies[END_REF]. At the same time, real workloads often exhibit non-stationary request processes with short-term correlations (often referred to as temporal locality [START_REF] Traverso | Temporal locality in today's content caching: Why it matters and how to model it[END_REF]), which are present also in our trace (see Sec. 4). In these cases, LRU (Least Recently Used) policy often outperforms LFU. Up to this day, LRU is probably the most popular caching policy in production systems due to its low time and space complexity and significant improvement of system performance even for relatively small cache sizes [START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF][START_REF] Mattson | Evaluation techniques for storage hierarchies[END_REF]. 2-LRU algorithm is similar to LRU, but only stores files after at least two requests, which helps to reduce cache pollution by unpopular files [START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF][START_REF] Montazeri | LRU-2 vs 2-LRU: An Analytical Study[END_REF]. Some algorithms that take into account both recency and frequency of file requests, for example, the Adaptive Replacement Cache policy (ARC) [START_REF] Megiddo | {ARC}: A {Self-Tuning}, Low Overhead Replacement Cache[END_REF].

Caching with non-zero download delay. The actual time to retrieve files is usually discarded under the assumption that the throughput between the remote storage and the local cache is high enough to fetch each file before the next request arrives. In reality, the retrieval time might exceed the time difference between consecutive requests for the same file (the so-called reuse distance), which would cause a 'delayed hit' [START_REF] Atre | Caching with delayed hits[END_REF][START_REF] Dai | Analysis of tandem PIT and CS with non-zero download delay[END_REF]. Paper [START_REF] Atre | Caching with delayed hits[END_REF] demonstrates that the hit rate maximization does not necessarily lead to latency minimization when some hits are delayed, which shows the need for new latency-sensitive caching algorithms. In particular, they propose two LRU variants and showed how to compute analytically their relevant metrics of interest.

In our work, we evaluate the effect of delayed hits in the WLCG by including fetching delays in the performance evaluation.

Caching for heterogeneous file sizes. Existing literature on caches mostly considers the case of equal-sized files [1-3, 5-7, 9], often under the justification that files may be split into chunks with a given maximum size, and caching policies may work at the chunk level. In practice, the overhead of chunk management may be unacceptable and, even when it is not the case, chunks can still exhibit heterogeneous sizes, when file sizes vary from a few bytes to terabytes, as is the case in the WLCG. In this paper, we consider files as atomic cacheable units. LFU, LRU, and 2-LRU can also operate with heterogeneous file sizes with minor changes, but more sophisticated policies, in general, require a non-straightforward adaptation, e.g., in the case of ARC.

We dedicate part of our paper studying how to combine LRU with prefetching techniques to exploit available dataset information (Sec. 5.3). The existing policies that were specifically conceived to take into account file size, such as AdaptSize [START_REF] Berger | Adaptsize: Orchestrating the hot object memory cache in a content delivery network[END_REF], GDSF [START_REF] Cherkasova | Improving WWW proxies performance with greedy-dual-size-frequency caching policy[END_REF], GD-Wheel [START_REF] Li | Gd-wheel: a cost-aware replacement policy for key-value stores[END_REF]), and DynqLRU [START_REF] Neglia | Cache policies for linear utility maximization[END_REF], could be extended in a similar manner.

Caching with prefetching. All policies described above are reactive, as they can only update the cache upon a miss by inserting the corresponding file. Existing correlations in the request process could be used to forecast which content will be requested in the near future and prefetch

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes Olga Chuchuk it.1 This approach has been investigated especially for video streaming [START_REF] Rossini | Multi-terabyte and multi-gbps information centric routers[END_REF][START_REF] Biersack | Open-loop video distribution with support of VCR functionality[END_REF], as chunks of video files are mostly read sequentially with the few exceptions of pausing, fast-forward, and rewind. As we show in Sec. 4, requests for files in the same dataset are highly correlated, but those files are read in arbitrary order, depending on the user and system software.

Caching for scientific workloads. Previous studies on caching for scientific computation often focus on the design and deployment of the caching infrastructure [START_REF] Weitzel | Data Access for LIGO on the OSG[END_REF][START_REF] Li | A data caching model for Tier 2 WLCG computing centres using XCache[END_REF][START_REF] Alekseev | Evaluation of the Impact of Various Local Data Caching Configurations on Tier2/Tier3 WLCG Sites[END_REF], rather than on the selection of well-suited caching algorithms. For example, in [START_REF] Weitzel | Data Access for LIGO on the OSG[END_REF], the authors simply rely on XCache [START_REF] Bauerdick | XRootd, disk-based, caching proxy for optimization of data access, data placement and data replication[END_REF] and its internal implementation of the LRU policy. To the best of our knowledge, only paper [START_REF] Heidsieck | Efficient execution of scientific workflows in the cloud through adaptive caching[END_REF] explores the usage of a caching technique significantly different from LRU for scientific workloads. The authors propose an adaptive caching solution that is only suitable for tasks with high re-execution rates, which are not present in the WLCG.

Alternatively, some works that explore how effectively the WLCG storage is used: at individual grid sites [START_REF] Chuchuk | Access Pattern Analysis in the EOS Storage System at CERN[END_REF], or throughout the whole WLCG in a context of a single LHC experiment [START_REF] Beermann | Methods of Data Popularity Evaluation in the ATLAS Experiment at the LHC[END_REF]. These papers also describe data access patterns potentially relevant for caching, but they do not directly investigate caching strategies.

In our paper, we also study data access patterns in the WLCG but focus on those characteristics that directly influence cache performance. Additionally, we propose new caching policies and compare their behavior with the existing ones under different scenarios (cache size, network connectivity throughput).

Metrics of interest. The standard metric used to evaluate the cache performance is the hit/miss ratio, but it fails to capture the different costs of different misses when file sizes are heterogeneous. Therefore, we distinguish the hit ratio, also called File Hit Ratio (FHR), and the Byte Hit Ratio (BHR). They can be defined as follows:

FHR = 𝑁 𝑐𝑎𝑐ℎ𝑒 𝑁 , BHR = 𝑉 𝑐𝑎𝑐ℎ𝑒 𝑉 , ( 1
)
where 𝑁 is the total number of requests (or the trace length), 𝑉 is the total volume of the catalog, i.e., the total size in bytes of all files which have been requested at least once, 𝑁 𝑐𝑎𝑐ℎ𝑒 is the number of files retrieved from the cache (the total number of hits), and 𝑉 𝑐𝑎𝑐ℎ𝑒 is the total number of bytes served by the cache. Respectively, File Miss Ratio (FMR) and Byte Miss Ratio (BMR) are calculated as:

FMR = 1 -FHR, BMR = 1 -BHR. ( 2
)
Under different scenarios, one of these metrics can play a more important role than the other. For example, FMR is more relevant if the objective is to minimize the user delay and the retrieval time under a miss is almost constant (latency dominates the retrieval time). At the same time, BMR is more important for assessing the data volume transfer between the sites. From the definition, when the files have the same size, FMR and BMR coincide.

Lower bound for FMR of reactive policies. In the case of homogeneous file sizes, Belady's offline algorithm [START_REF] Belady | A study of replacement algorithms for a virtual-storage computer[END_REF] achieves optimal FMR amongst reactive policies [START_REF] Mattson | Evaluation techniques for storage hierarchies[END_REF]. At each step, this algorithm evicts the file that will be requested the furthest in the future. Since it can only be

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes Olga Chuchuk calculated post-factum, practical implementation is not possible. However, in studies like ours, it can serve as a lower bound for the performance of practical reactive policies.

In the case of heterogeneous file sizes, let us denote the reactive caching policy that minimizes FMR (resp. BMR) as OPT (resp. OPT.Bytes). Both minimization problems are NP-hard [START_REF] Chrobak | Caching is hard-even in the fault model[END_REF], which means that in practice, finding the exact optimal policies is not feasible.

A simple lower bound for both FMR and BMR of reactive policies can be computed by simulating an infinite size cache [START_REF] Huang | An analysis of Facebook photo caching[END_REF]. This approach only quantifies cold compulsory misses, which inevitably occur when a file is requested for the first time. Instead, paper [START_REF] Berger | Practical bounds on optimal caching with variable object sizes[END_REF] proposes several algorithms to calculate lower and upper bounds for FMR of OPT. The flow-based offline optimal (FOO) lower and upper bounds presented by the authors are very accurate but computationally expensive; the practical FOO lower and upper bounds (PFOO-L and PFOO-U) work for hundreds of millions of requests, while still providing tight upper and lower bounds for OPT performance. Paper [START_REF] Panigrahy | A New Upper Bound on Cache Hit Probability for Non-anticipative Caching Policies[END_REF] presents yet another lower bound for FMR of non-anticipative policies, but only under some statistical assumptions on the request process. In our work, we use the PFOO-L lower bound and extend it to be able to compute a lower bound for OPT.Bytes' BMR.

Lower bound for BMR of reactive policies

While there are bounds for the optimal FMR of reactive policies, we are not aware of similar bounds for BMR. In this section, we propose a modification of PFOO-L, the PFOO-L.Bytes algorithm, which computes a lower bound for BMR of OPT.Bytes.

Remember that 𝑁 denotes the total number of requests in the trace. The trace contains 𝑀 unique files 𝑓 1 , 𝑓 2 , . . . , 𝑓 𝑀 with sizes 𝑠 1 , 𝑠 2 , . . . , 𝑠 𝑀 , respectively. The 𝑖-th request can be represented by the pair {𝑖, 𝑓 𝑗 𝑖 }, where 𝑗 𝑖 is the identifier of the requested file. Let 𝑇 𝑑𝑖 𝑓 [𝑖] denote the reuse distance, i.e., the difference between the order of the future request for the same file and the current request.

𝐶 denotes the cache capacity in bytes.

Similarly to [START_REF] Berger | Practical bounds on optimal caching with variable object sizes[END_REF], we represent the total cache resource by an initially empty rectangle with sizes N and C (the resources are limited in time and space). We can associate to each request {𝑖, 𝑓 𝑗 𝑖 } a rectangle with height 𝑠 𝑗 𝑖 and width 𝑇 𝑑𝑖 𝑓 [𝑖] and place it between 𝑖 and 𝑖 + 𝑇 𝑑𝑖 𝑓 [𝑖] on the time axis. Its area 𝑠 𝑗 𝑖 × 𝑇 𝑑𝑖 𝑓 [𝑖] corresponds to the total amount of cache resources that should be allocated to file 𝑗 𝑖 to avoid the following request (at time 𝑖 + 𝑇 𝑑𝑖 𝑓 [𝑖]) producing a miss.

The PFOO-L algorithm greedily picks the rectangles with the smallest area until all cache resources are consumed (the sum of the areas of the placed rectangles exceeds the global rectangle size, regardless of the overlaps). It, therefore, finds a lower bound for FMR of reactive policies, since no other reactive caching algorithm can get fewer misses using 𝑁 × 𝐶 total resources. In particular, the rectangles selected by PFOO-L may overlap in such a way that the required instantaneous capacity (the sum of the rectangles' heights) exceeds the constraint 𝐶.

We now describe how to adapt PFOO-L to find a lower bound for the minimum BMR (PFOO-L.Bytes). While in PFOO-L every selected rectangle brings a gain equal to 1 as it prevents a miss, in PFOO-L.Bytes, the rectangle corresponding to the request {𝑖, 𝑓 𝑗 𝑖 } has associated gain 𝑠 𝑗 𝑖 , i.e., equal to the bytes it prevents from downloading. This leads us to a knapsack problem, where each file is associated with a cost to store it and a potential gain. We can then lower-bound BMR by greedily selecting the rectangles with the best gain/cost ratio until we run out of caching resources.

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes

Olga Chuchuk

The complete algorithm PFOO-L.Bytes is presented in Algorithm 1. Arrays 𝑅, 𝑇 and 𝑆 and initialized with the request sequence, the order or requests (or request time), and the sizes of the request files, correspondingly. The first step is to find the order of the next request 𝑇 𝑛𝑒𝑥𝑡 [𝑖] for the same file 𝑓 𝑗 𝑖 for each request {𝑖, 𝑓 𝑗 𝑖 } of the trace (line 7). If the file 𝑓 𝑗 𝑖 is accessed for the last time, 𝑇 𝑛𝑒𝑥𝑡 [𝑖] = ∞. Next, the reuse distance between consecutive requests 𝑇 𝑑𝑖 𝑓 [𝑖] to the same file 𝑓 𝑗 𝑖 is calculated (line 8). We then find the rectangles' sizes (line 9), sort them by density, i.e., the gain/cost ratio (line 10), and add them to the cache while there are enough caching resources (lines 11-17). Since Alg. 1 is not an actual caching algorithm, but only finds a lower bound of the optimal performance, we allow caching fractions of the files. In the function cache_file, the second argument indicates the fraction of the file that needs to be cached. The final step is to add a fraction of the first rectangle that did not fit (lines [START_REF] Alekseev | Evaluation of the Impact of Various Local Data Caching Configurations on Tier2/Tier3 WLCG Sites[END_REF][START_REF] Bauerdick | XRootd, disk-based, caching proxy for optimization of data access, data placement and data replication[END_REF][START_REF] Heidsieck | Efficient execution of scientific workflows in the cloud through adaptive caching[END_REF]. Note how we are implicitly solving the fractional knapsack problem, and then we either match or exceed the optimal solution of the original knapsack problem [START_REF] Goodrich | Algorithm design and applications[END_REF]Sec. 5.1.1].

Algorithm 1 PFOO-L.Bytes 1: 𝑅 = [], 𝑇 = [], 𝑆 = [] 2: for 𝑖 = 1..𝑁 do 3: append(𝑅, 𝑓 𝑗 𝑖 ) 4:
append(𝑇, 𝑖)

cache_file(𝑖, 𝑃/𝐼 [𝑖]) 20: end if

Both PFOO-L and PFOO-L.Bytes can be constructed through a single pass over the trace for different cache sizes. In this case, the preprocessing steps (finding the time of the next access and sorting the intervals accordingly) take 𝑂 (𝑁 log 𝑁) time and 𝑂 (𝑁) space, and iterating over the trace takes 𝑂 (𝑁) both in time and space.

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes Olga Chuchuk

Workload Characteristics

In this paper, we consider the local grid analysis workflow of ATLAS, the largest LHC experiment, at the CERN data center, the largest WLCG site. From the storage logs, we generated a trace of all read file accesses for a period of three months (01/01/2020-31/03/2020). We intend to make these data publicly available later this year.

Table 1 provides an overview of this trace by comparing the analysis and the total read workloads. Analysis files represent only 25% of the files/operations in the catalog but contribute around 60% to the catalog volume and the total read workload (the sum of requested bytes). Figure 1 shows the file size distributions for the complete catalog and for the set of analysis files. Both distributions peak at around 1 GB and have very large support spanning 11 and 10 orders of magnitude, respectively. File sizes extend to 470.73 GB, with the median of 40.78 MB. In comparison, the maximum size of analysis files is lower (67.16 GB), but the median is higher (824.38 MB). Additionally, we plot the distribution of the analysis file popularity (the number of accesses) (Fig. 2) and estimate to which extent files with a given size contribute to the system workload (Fig. 3). By comparing them, we observe that very small files (<10 kB) tend to be accessed more often than the rest, while the system workload is almost entirely determined by the files in the range 100 MB-10 GB.

Total

We conclude that the file size cannot be neglected: while very small files contribute the most to the number of accesses, most of the system load originates from the larger files.

Another important characteristic of the trace is the request load variability over time (Fig. 4). The byte rate averaged over one second varies from a few bytes to several terabytes per second (the mode of the distribution is around 20 GB/s), with an average request rate over the whole period equal to 9.91 GB/s.

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes The three-month trace exhibits temporal locality (Fig. 5). The distribution appears multimodal. Even though the average time between two consecutive read requests for the same file is around 3 days, 27.44% of consecutive accesses happen within a minute, and 6.47% happen within one second.

Remember that all the records meaningful for the same physics analysis are spread across different files and together form a logical entity called a dataset. We studied the properties of datasets and their access patterns. The distribution of dataset sizes is more heterogeneous than that of individual files (Fig. 6). The most common dataset size is around 1 MB, while the average is almost 80 GB. On average, there is a modest number of files in a dataset (the mean is 38, and the median is only 3).

To understand if files within the same dataset tend to be accessed together, we performed the following analysis. First, we looked at the fraction of each dataset (in terms of the number of files) accessed over the whole three-month period. For 75% of the datasets, all files were accessed; on average this fraction is 83%. Moreover, we quantified the variability of the number of accesses for files within the same dataset. For most datasets (92% of them), the standard deviation of the

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes number of file accesses is at most 1. We conclude that when a user accesses a dataset file, (s)he is also likely to access all other files in the same dataset.

The order of the individual file accesses is difficult to reconstruct since log files only show the aggregate request process, where multiple users may access the same dataset simultaneously, and the same user can access different parts of the same dataset in parallel (for example, when the data being processed is coordinated by Rucio, the distributed data management system widely used in the WLCG [START_REF] Barisits | Rucio: Scientific data management[END_REF]).

From all of the above, we conclude that when a dataset is accessed, most of its files are read, while not necessarily in any specific order.

Caching for the WLCG

Caching policies

In this section, we evaluate the performance (FMR and BMR) of an array of different caching policies. We consider the classic LRU, as well as its 2-LRU variant, which has been shown to outperform LRU in many cases [START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF][START_REF] Ricardo | Caching policies for delay minimization in small cell networks with coordinated multi-point joint transmissions[END_REF]. Both policies can profit from the high level of temporal locality present in the trace (Fig. 5).

In addition, we propose and evaluate new caching policies that take advantage of some specifics of the WLCG workload. In particular, these policies rely on the dataset membership information, which was reconstructed for each file using an additional data source, Rucio metadata. As datasets are mostly read entirely, if some files in the dataset are currently in use, one may expect that the other files within the same dataset will be accessed in the near future. In particular, we propose the following policies, which preserve LRU's low complexity and are then particularly suited to serve high-rate request processes.

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes Dataset Evict LRU/MRU. These policies insert a file into the cache only upon a miss for that file (as LRU does). They maintain information about the last access to a dataset and, when the space is needed, they start evicting files belonging to the least recently accessed dataset. Among the files within this dataset, Dataset Evict LRU first evicts the least recently accessed files, while Dataset Evict MRU evicts the most recently accessed ones. We stress that both policies operate on the file level.

Dataset LRU. This policy relies on prefetching, as, upon a file miss, all files belonging to the accessed dataset are retrieved from the remote server and stored in the cache. Similarly, when cache space is needed, all files of the least recently accessed dataset are evicted. In short, this policy operates on individual files (remember that datasets are only logical entities unknown to the underlying file system), but practically behaves as LRU would if datasets were the atomic cacheable units.

We have also tested a variant of Dataset LRU that is less aggressive upon eviction. This policy does not evict entirely the least recently accessed dataset, but only as many of its files as needed. While this variant better uses the available storage space and achieves smaller FMR and BMR, the improvement is negligible (in the order of 10 -4 ).

Performance comparison

We evaluated the performance of the caching policies by simulating the cache behavior using the same three-month trace reflecting the request process. In each case, the initial state of the system is an empty cache.

Figures 7a and7b compare how FMR and BMR change depending on the cache size, which is measured as a percentage of the total volume of unique files seen in the trace. PFOO-U and PFOO-U.Bytes algorithms provide lower bounds for the performance of any reactive caching policy. Dataset Evict LRU and Dataset Evict MRU show a negligible difference in performance in the order of 10 -3 , so we show results only for the first of them.

These plots show that among the reactive techniques we considered, LRU remains the best option. Differently from what was observed in many previous studies [START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF][START_REF] Ricardo | Caching policies for delay minimization in small cell networks with coordinated multi-point joint transmissions[END_REF], 2-LRU results in significantly worse BMR and almost the same FMR. Curves for LRU and Dataset Evict LRU almost coincide. As most of the files in the same dataset are accessed consecutively, files in the least

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes Olga Chuchuk recently accessed dataset are to a large extent also the least recently accessed files. Cache states are then almost identical for LRU and Dataset Evict LRU.

Even though we have not found a reactive technique that performs better than LRU, the comparison with the optimal bounds suggests that there is a large room for potential improvement. For example, for the 5-10% cache sizes, the miss ratios could be reduced by a factor of 1.5.

As expected, all the reactive techniques (LRU, 2-LRU, Dataset Evict LRU, PFOO-U, PFOO-U.Bytes) provide the same performance when the cache can store the whole catalog. In these cases, the misses occur only the first time a file is requested (cold misses) and are not due to space constraints. In contrast, thanks to prefetching, Dataset LRU can avoid most of the cold misses. It results in the lower miss ratios in general (starting from the cache size around 1%), and specifically for the 100% cache size. Dataset LRU performs better than the lower bounds of reactive policies performance even for 3-5% cache sizes; this suggests that the total volume of the active datasets at any particular moment in time is low. At the same time, the miss ratio reduction comes at the price of increased accumulated transfer volume (Fig. 8).

Limited connectivity throughput

So far, we have been assuming that the throughput between the processing grid site and the data source is large enough to make the content retrieval time negligible in comparison to the interrequest arrival times. In reality, as described in Sec. 2.2, limited connectivity could lead to delayed hits and significantly influence the cache performance. To estimate this effect, we conducted an array of experiments that emulate the retrieval process under throughput constraints and compare the performance of LRU, as the best reactive policy, and Dataset LRU, which showed the best performance previously. We expect delayed hits to penalize Dataset LRU more, as prefetching leads to retrieving larger volumes of data.

The backhaul link and the main storage are modeled as a single-server FIFO queue [START_REF] Harchol-Balter | Performance modeling and design of computer systems: queueing theory in action[END_REF] with a constant service rate (corresponding to the throughput) and customers in the queue are the objects to be retrieved (a file in the case of LRU, a dataset in the case of Dataset LRU). We refer to such a queue as the 'loading queue.' Upon a miss for an object, the retrieving job is added to the queue if not already present, i.e., if there is not already a pending request for that object. Objects are inserted into the cache when their service is completed.

Figure 9 shows how the size of the queue changes over time under LRU and a 100 Gbit/s network throughput. With this level of connectivity, the network is rarely congested: the queue

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes Olga Chuchuk occupancy is close to zero most of the time, with some peaks appearing only for small cache sizes like those reported in Fig. 9. Such peaks correspond to clusters of misses which require the retrieval of large volumes of data. As we decrease the throughput or switch to Dataset LRU, there are settings for which requests would require to retrieving content at a rate that constantly exceeds the connectivity throughput: the queue occupancy keeps increasing over time. In these pathological cases, the numerical values for FMR and BMR are not representative (e.g., they heavily depend on the trace length) and are then represented through dashed lines in the BMR plots (Fig. 11a and11b).

Figure 10 shows how the hit rate changes over time for different cache sizes. The squares on the curve designate the first time instant when the cache is full. Lower throughput and larger cache sizes shift these points further to the right. In order to eliminate the effect of the initial transient, we considered the first 40% of the trace as a warm-up period and evaluated the metrics of interest only on the final 60%. In this manner, we guarantee that the cache is full for all the considered set-ups (different throughputs, cache sizes, caching policies), but for the cache sizes closely approaching 100%. The effect of throughput constraints on LRU performance is illustrated in Fig. 11a. We observe that as far as the system provides a throughput of at least 50 Gbit/s, delayed hits have little effect on BMR, which is very close to the ideal case of infinite throughput. At the same time, the throughput of 30 Gbit/s shows a significant difference in performance with small cache sizes (20% and less). For 20 Gbit/s the miss ratio is larger for all cache sizes.

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes In contrast, the effect of the limited throughput on the performance of Dataset LRU-the best policy in the infinite throughput regime (Fig. 7b)-is more profound (Fig. 11b). In fact, upon a miss, Dataset LRU retrieves a much larger amount of data than LRU (compare dataset sizes to file sizes, Fig. 1 and6). With a 13% cache size, even a 100 Gbit/s throughput, which had virtually no influence on LRU performance, leads Dataset LRU to experience 0.15 BMR from just 0.01 for the infinite throughput case. Dataset LRU still outperforms LRU in this scenario, but the relative performance improvement is significantly reduced. For even smaller throughputs and/or smaller cache sizes, the effect of delayed hits annihilates the advantage from prefetching, and Dataset LRU starts performing worse than LRU. From these results, we conclude that the throughput must be taken into account when developing cache eviction policies for the remote computations model. The limited throughput worsens the performance of cache algorithms, not proportional to the results under the infinite throughput assumption. Figure 12 shows which caching policy should be preferred, depending on the throughput and the cache size.

Conclusions and Future Work

In this work, we studied the existing scientific workloads of the CERN data center in the context of caching. Specifically, we analyzed the access patterns of a three-month trace of ATLAS, the

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes Olga Chuchuk largest of the LHC experiments. We focused on the user read requests for analysis data, as they correspond to the most unpredictable part of the storage accesses. We explored request rates, time locality, file popularity, and system load in relation to the file size, as well as intra-dataset access patterns.

Trace analysis motivated the selection of existing caching policies (LRU, 2-LRU) that can take advantage of temporal locality characteristics and operate with heterogeneous file sizes. We compared them to the new cache policies specifically tailored for dataset-based workloads (Dataset Evict LRU and Dataset LRU). We evaluated the cache performance with respect to FMR and BMR, and proposed the PFOO.Bytes algorithm to compute a lower bound for the Byte Miss Ratio for any reactive caching policy.

Dataset LRU heavily relies on prefetching and provides significant improvements in terms of both FMR and BMR compared to the other policies but raised our concerns about the possible high number of delayed hits. To estimate their influence, we ran simulations of LRU and Dataset LRU policies with network throughput values from 20 to 100 Gbit/s. We showed that Dataset LRU loses its advantage over LRU when the throughput is not sufficient to sustain the higher data volumes retrieved by Dataset LRU. In the future, we plan to study a new variant of Dataset LRU where the amount of prefetching is dynamically adapted as a function of the observed retrieval time.

Our research investigates a three-month period, which is enough to capture the lifespan of individual files but is not representative of yearly data access from the physics community (for example, massive preparation for big physics conferences, end-of-the-year closure of CERN, etc.). Notably, a tangible change in data access patterns happens when the LHC starts running, and the WLCG enters a so-called 'data-taking' period, the next of which is foreseen to start in late spring/summer of 2022. We plan to move to these data as soon as they become available. Moreover, on a longer time horizon, we want to develop a model to evaluate the global cost of caching (storage, latency, network) and inform future storage architectural design and deployment.

A. The WLCG Architecture

The WLCG is a three-tier hierarchical global federation of computing centres. Tier 0 (or T0), is the CERN data center-the largest facility within the network. Tier 1 consists of 13 computer centres located in Europe, Asia, and North America. Each of them has a direct high-capacity connection to T0 using the LHCOPN (LHC Optical Private Network) [START_REF] Martelli | LHCOPN and LHCONE: status and future evolution[END_REF]. T0 and T1 provide data stewardship and processing. There are about 155 Tier 2 sites around the globe. They vary in size from a dozen of servers to data centres. T2 and T1 sites are connected using public networks and LHCONE (LHC Open Network Environment) [START_REF] Martelli | LHCOPN and LHCONE: status and future evolution[END_REF], which provides dynamic point-to-point virtual connections. In this way, each T1 is connected to T0, and each T2 is connected to one or more T1s, but there are also connections between some sites belonging to the same Tier. Roughly 1/5th of the resources are at the T0, 1/5th at the T1 level, and 3/5th are provided by the T2. Furthermore, there are additional compute resources, which range from small clusters to large national analysis facilities, that are not curated by the WLCG community. These are often referred to as Tier 3 and are almost exclusively used for physics analysis.

Data serving and computing tasks are distributed within the whole WLCG network, depending on the specific needs of each of the large LHC experiments. However, only T0 and T1 sites are

PoS(ISGC2022)009

Caching for dataset-based workloads with heterogeneous file sizes Olga Chuchuk responsible for data archiving: T0 maintains one copy of the data and all T1 sites together provide a second copy. T0 and T1s share the load of operating the centralized coordination services at a high service level.

PoS(ISGC2022)009

Figure 1 :

 1 Figure 1: File size distribution.

Figure 2 :

 2 Figure 2: File popularity distribution.

Figure 3 :

 3 Figure 3: System load distribution.

Figure 4 :

 4 Figure 4: Distribution of byte request rate averaged per second.

Figure 5 :

 5 Figure 5: Distribution of time intervals between consecutive requests for the same file.

Figure 6 :

 6 Figure 6: Dataset size distribution.

( a )

 a File Miss Ratio (b) Byte Miss Ratio

Figure 7 :

 7 Figure 7: Miss ratios vs cache size for different caching policies.

Figure 8 :

 8 Figure 8: Ratio between accumulated transferred volumes of Dataset LRU and LRU (prefetching overhead).

Figure 9 :

 9 Figure 9: Queue size over time (requests) for 100 Gbit/s throughput and LRU.

Figure 10 :

 10 Figure 10: Hit ratio over time (requests) for 30 Gbit/s throughput and LRU. A square indicates the first time instant when the cache is full.

( a )Figure 11 :

 a11 Figure 11: BMR vs cache size for different throughput values (miss ratios are computed on the final 60% of the trace). Points connected by dashed lines correspond to the settings where the loading queue is constantly growing.

Figure 12 :

 12 Figure 12: Caching policy minimizing BMR for different throughputs and cache size values.

5 :

 5 append(𝑆, 𝑠 𝑗 𝑖 ) 6: end for 7: 𝑇 𝑛𝑒𝑥𝑡 ← find_next_access(𝑅) 8: 𝑇 𝑑𝑖 𝑓 = 𝑇 𝑛𝑒𝑥𝑡 -𝑇 9: 𝐼 = 𝑆 × 𝑇 𝑑𝑖 𝑓 10: 𝐼 ← sort_by_density(𝐼, 𝑆) 11: 𝑖 = 1 12: 𝑃 = 𝑁 × 𝐶 13: while 𝑖 ≤ 𝑁 and 𝐼 [𝑖] ≤ 𝑃 do

	14:	cache_file(𝑖, 1)
	15:	𝑃 = 𝑃 -𝐼 [𝑖]
	16:	𝑖 = 𝑖 + 1
	17: end while
	18: if 𝑖 ≤ 𝑁 then
	19:

Table 1 :

 1 Comparison of the total and analysis read workloads

	Analysis

1Sometimes, the literature uses the expressions "caching policies" and "prefetching policies" to distinguish what we call "reactive caching policies" and "caching policies with prefetching," respectively.


Sabine Barrat
email: barrat@loria.fr

Salvatore Tabbone
email: tabbone@loria.fr

Modeling, classifying and annotating weakly annotated images using Bayesian network

We propose a probabilistic graphical model to represent weakly annotated images 1 . This model is used to classify images and automatically extend existing annotations to new images by taking into account semantic relations between keywords. The proposed method has been evaluated in classification and automatic annotation of images. The experimental results, obtained from a database of more than 30000 images, by combining visual and textual information, show an improvement by 50.5% in terms of recognition rate against only visual information classication. Taking into account semantic relations between keywords improves the recognition rate by 10.5% and the mean rate of good annotations by 6.9%. The proposed method is experimentally competitive with the state-of-art classifiers.

Introduction

The rapid growth of Internet and multimedia information has shown a need in the development of multimedia information retrieval techniques, especially the image retrieval. We can distinguish two main trends. The first one, called "text-based image retrieval", consists in applying text-retrieval techniques to fully annotated images. The second approach, called "content-based image retrieval" is a more young field. These methods rely on visual features (color, texture or shape) computed automatically, and retrieve images using a similarity measure. In order to improve the recognition, a solution consists in combining visual and semantic information. Some researchers have already explored this possibility [START_REF] Barnard | matching words and pictures[END_REF][START_REF] Kherfi | Combining visual features with semantics for a more effective image retrieval[END_REF]. Automatic image annotation can be used in image retrieval systems to organize and locate images of interest from a database, or to perform visual-textual classification. This 1 we consider an image as weakly annotated if the number of keywords defined for it is less than the maximum defined in the ground truth method can be seen as a kind of multi-class image classification with a very large number of classes, as large as the vocabulary size. Many works have been proposed in this direction and we can cite, without being exhaustive, classification-based methods [START_REF] Gao | Automatic image annotation by incorporating feature hierarchy and boosting to scale up svm classifiers[END_REF], probabilistic modelingbased methods [START_REF] Blei | Modeling annotated data[END_REF] and annotation refinement [START_REF] Wang | Image annotation refinement using random walk with restarts[END_REF]. The contribution of this paper is to propose a scheme for image classification optimization, by using a joint visualtext clustering approach and automatically extending image annotations. The model presented here is dedicated for both tasks: weakly-annotated image classification and annotation. In fact the classification methods before mentioned are efficient but they require that all images, or image regions are annotated. Moreover, most existing annotation models are not able to classify images. The proposed approach is derived from the probabilistic graphical model theory. We introduce a method to deal with missing data in the context of text annotated images as defined in [START_REF] Blei | Modeling annotated data[END_REF][START_REF] Kherfi | Combining visual features with semantics for a more effective image retrieval[END_REF]. The uncertainty around the association between a set of keywords and an image is tackled by a joint probability distribution over a dictionary of keywords and the numerical features extracted from our collection of images (grey-level and color). The Gaussian-multinomial Mixture model [START_REF] Blei | Modeling annotated data[END_REF] is the most related to our approach. However our model is less restrictive for the user. In fact, our classifier does not need that all images be annotated. Moreover, our model has the advantage to take into account the possible semantic relations between keywords, contrary to the model [START_REF] Blei | Modeling annotated data[END_REF] which assumes that the keywords are independent given its parents. Section 2 describes the probabilistic model of weaklyannotated image representation and how to use it to classify and extend existing annotations to images. Section 3 presents the experimental results. Finally, conclusions and future works are given in Section 4.

Representation and classification of weakly-annotated images

Our work is focused on weakly-annotated image modeling and classification. Now visual descriptors often provide vectors of continuous values, and the associated keywords often correspond to discrete variables. So we have chosen to construct a Bayesian classifier which combines discrete and continuous variables and takes into account the problem of missing values. Let f j be a query image characterized by a set of features F . F is composed of m visual features, denoted v 1 , ..., v m and n possible keywords, denoted KW 1, ..., KW n. The chosen visual features are issued from one color descriptor, a color histogram, and one shape descriptor based on the Fourier/Radon transform. We are interested in the probability distributions of these features and their conditional dependence relations. Let us consider the visual features as continuous random variables and theirs associated keywords as discrete variables. This model is too big to be represented as a unique joint probability distribution, therefore it is required to introduce some sparse and structural a priori knowledge. The probabilistic graphical models, and especially Bayesian networks, are a good way to solve this kind of problem. In fact within Bayesian networks the joint probability distribution is replaced by a sparse representation only among the variables directly influencing one another. Interactions among indirectly-related variables are then computed by propagating inference through a graph of these direct connections. Consequently, Bayesian networks are a simple way to represent a joint probability distribution over a set of random variables, to visualize the conditional properties and to compute complex operations like probability learning and inference, with graphical manipulations. Then, a Bayesian network seems to be appropriate to represent and classify images and associated keywords. We have to manage continuous variables (corresponding to visual features) and discrete variables (corresponding to keywords). Therefore a Bayesian classifier, which involves both types of variables, is proposed. We present a hierarchical probabilistic model of multiple-type data (images and associated keywords) in order to classify large databases of weakly annotated images. A Gaussian-Mixtures and Bernoulli Mixture model is proposed. In fact, the observation of some peaks on the different histograms of the feature variables, has led us to consider that the visual features can be estimated by mixtures of Gaussian densities. The discrete variables corresponding to the words of the vocabulary have a Bernoulli distribution: in fact, for a given image, each keyword variable can take two states: "true" when the word annotates the given image, or "false", when the word can't belong to the given image annotation. Now let F be the training set composed of m instances f 1i , ..., f mi , ∀i ∈ {1, ..., n}, where n is the dimension of the signatures provided by the concatenation of the feature vectors issued from the computation of all the descriptors on each image on the training set. Each instance f j , ∀j ∈ {1, ..., m} is then characterized by n continuous variables. A supervised classification is considered then F instances are divided into k classes c 1 , ..., c k . Let G 1 , ..., G g be g groups whose each has a Gaussian density with a mean µ l , ∀l ∈ {1, ..., g} and a covariance matrix l . Besides, let π 1 , ..., π g be the proportions of the different groups, θ l = (µ l , l ) the parameter of each Gaussian and Φ = (π 1 , π 1 , ..., π g , θ 1 , ..., θ g ) the global mixture parameter. Then the probability density of F conditionally to the class c i , ∀i ∈ {1, ..., k} can be defined by

P (f, Φ) = g l=1 π l p(f, θ l )
where p(f, θ l ) is the multivariate Gaussian defined by the parameter θ l .

Then, we have one Gaussian Mixture Model per class. This problem can be represented by a probabilistic graphical model (see Figure 1), where:

• The "Class" node is a discrete node, which can take k values corresponding to the pre-defined classes c 1 , ..., c k .

• The "Component" node is a discrete node which corresponds to the components (i.e. the groups G 1 , ..., G g ) of the mixtures. This variable can take g values, i.e. the number of Gaussians used to compute the mixtures. It's an hidden variable which represents the weight of each group (i.e. the π l , ∀l ∈ {1, ..., g}).

• The "Gaussian" node is a continuous variable which represents each Gaussian G l , ∀ ∈ {l = 1, ..., g} with its own parameter (θ l = (µ l , l )). It corresponds to the set of feature vectors in each class.

• Finally, the edges represent the effect of the class on each Gaussian parameter and its associated weight. We have one GMM, composed of Gaussians and their associated weight, per class. Now the model can be completed by the discrete variables, denoted KW 1, ..., KW n, where n is the size of the vocabulary, and KW i represents each keyword of the vocabulary. Dirichlet priors [START_REF] Robert | A decision-Theoretic Motivation[END_REF], have been used for the probability estimation of the variables KW 1, ..., KW n. That is we introduce additional pseudo counts at every instance in order to ensure that they are all "virtually" represented in the training set. Therefore every instance, even if it is not represented in the training set, will have a not null probability. Like the continuous variables corresponding to the visual features, the discrete variables corresponding to the keywords are included in the graphical model by connecting them to the class variable. Finally, some edges are added to represent semantic relations between keywords of the vocabulary. For example, the keywords "dog" and "animal" are clearly dependent. In fact these two keywords belong to the same concept group. This dependence is represented by a directed edge from the node "dog" to the node "animal". Then our classifier can be depicted by the Figure 1. The hidden variable "α" shows that a Dirichlet prior is used. The box around the variable KW denotes n repetitions of KW , for each keyword of the vocabulary. n is the size of the vocabulary. The edges representing semantic relations between keywords are not drawn in the box, to keep more clarity. But, Figure 2 represents more precisely the keyword variables and theirs potential dependences. The n nodes correspond to the n keywords of the vocabulary: KW 1, ..., KW n. Only some keyword dependences are represented. For example "bird" and "animal" have a semantic relation, which is represented by a directed edge from the node "bird" to the node "animal". In the same way an edge is observed between the nodes "duck" and "animal" and the nodes "duck" and bird".

Figure 1. The Gaussian-Mixtures and Bernoulli mixture model

This Bayesian classifier means that each image and its keywords are assumed to have been generated conditional on the same class. Therefore the resulting multinomial and Gaussian mixture parameters should correspond: concretely if an image, represented by visual descriptors, has an high probability under a certain class, then its keywords should have an high probability under the same class. Thus a query image f j , characterized by its visual features v j1 , ..., v jm and its possible keywords KW 1 j , ..., KW k j is considered as an "evidence" represented by P (f j ) = 1 when the network is evaluated. After the belief propagation, we know, ∀i ∈ {1, ..., k}, the posterior probability P (c i |f j ) = P (c i |v j1 , ..., v jm , KW 1 j , ..., KW n j ). The query f j is assigned to the class c i which maximizes this probability.

Annotation extension of images

Given an image without keyword, or a weakly annotated image, the proposed Bayesian model described before can be used to compute a distribution over words conditionally to the image and its possible existing keywords. In fact, for a query image f j annotated by a set of k, ∀k ∈ {0, ..., n} keywords, denoted EKW (for Existing KeyWords) where n is the size of the vocabulary, the inference algorithm enables to compute the posterior probability P (KW ij |f j , EKW ) ∀KW ij / ∈ EKW . This distribution represents a prediction of the missing keywords for that image. For example, let us consider Table 1 which presents 2 images with possible keywords and the keywords obtained after automatic annotation extension with (column 3) or without (column 2) considering potential semantic relations between keywords. The first image annotation, composed of 3 keywords at the beginning, has been extended by one wrong keyword. In fact, the good missing keyword is "shrubs". This mistake is probably due to the large number of database images annotated by these 4 keywords "bear", "black", "water" and "grass", which generates a hight joint probability of this keyword set. Considering the second image, its annotation has not been extended without taking into account semantic relations between keywords. It is probably due to the threshold used to select keywords. In fact, a keyword is selected as annotation if the probability of this keyword as annotation is strictly greater than a threshold. On the contrary, by taking into account semantic relations between keywords, the second image has been annotated by a correct keyword "water", thanks to the existing semantic relation between the keywords "river" and "water".

Experimental results

We present an evaluation of our model on more than 30000 weakly annotated images from the Corel image libraries and kindly provided by Vasconcelos and al. [START_REF] Carneiro | Supervised learning of semantic classes for image annotation and retrieval[END_REF]. These images are split up into 306 classes. For example, 4 images of the class "arabian horses" are given in Figure 3.

Table 1. Examples of images and possible keywords before and after annotation extension with or without taking into account semantic relations

First of all, some dependences between keywords have been established from the vocabulary. We define the dependence relation between two keywords of the same synset (semantic group), as defined in Wordnet [START_REF] Fellbaum | WordNet -An Electronic Lexical Database (Language, Speech, and Communication)[END_REF]. Wordnet is a large lexical database of English language, where the words (nouns, verbs, adjectives and adverbs) are grouped into sets of cognitive (denoted synsets), each expressing a distinct concept. That is two keywords having a semantic relation would be grouped in the same synset. These semantic relations are represented by dependences in our model, i.e. by links in the Bayesian network.

We have evaluated our method by performing 6 cross validations whose each proportion of the training set is 25%, 35%, 50%, 65%, 75% and 90% of the database, the remaining respectively 75%, 65%, 50%, 35% and 10% are hold for test set. In each case the tests are repeated 10 times in order that each database instance would be used for the training and the test. For each training set size, the recognition rate is obtained by taking the mean recognition rate of the 10 tests. For each test, the recognition rate corresponds to the ratio between the number of good classified images and the number of images in the training set. In all the tests, our Gaussian-Mixtures and Bernoulli mixture model (denoted GM-B) has been performed with mixtures of 2 Gaussians and diagonal covariance matrices.

Let us consider Table 2. Our GM-B model has been used to combine different types of information. The notation "C + S" means that the color and shape descriptors ("C" for Color, "S" for Shape) have been combined and "C + S + KW" adds textual information (KW for keywords).

The recognition rates confirm that combining visual with semantic features performs always better than any of them

GM-B model with semantic relations

Table 3 shows the recognition rates obtained with our GM-B model, by taking into account semantic relations between keywords (column "with SR", SR for semantic relations), or not (column "without"). These results show that taking into account semantic relations between keywords improves the recognition by 10.5%. Moreover, Table 3 shows the effectiveness of our approach (GM-B model) compared to the Gaussian-multinomial mixture model (GM-Mixture) [START_REF] Blei | Modeling annotated data[END_REF]. The GM-Mixture model has been used without image segmentation, as in our approach: the color and shape descriptors have been computed on the whole images and the keywords are associated to the whole images too. Moreover, as a supervised classification problem is considered in this paper, the discrete variable z used to represent a joint clustering of an image and its caption, in the GM-Mixture model, is not hidden for the images of the training set. Actually, this discrete variable corresponds to our class variable and the number of clusters is known (it is our number of classes). The results have been obtained by using the visual features and theirs possible associated keywords. It appears that with the semantic relations between keywords, our GM-B model has a better mean recognition rate than the GM-Mixture. Now, let us consider the annotation extension problem. At least a keyword annotation per image is needed to compare the annotations after automatic annotation extension to the ground truth annotations. Then 99.5% of the database images, annotated by at least 1 keyword, have been selected as ground truth. Like for the classification evaluation, 6 cross validations have been performed. The tests are repeated 10 times in order that each database instance would be used for the training and the test. For each test, the test images have been automatically annotated by 4 keywords. For each training set size, the rate of good annotations is obtained by taking the mean rate of the 10 tests. For each test, the rate of good annotations corresponds to the ratio between the number of annotations obtained automatically which corresponds to the ground truth and the number of keywords obtained automatically. The threshold used for annotation has been fixed at 0.5. That is to say, for a given image, a keyword is selected as annotation if his probability to annotate this image, knowing the visual features and possible existing keywords of this image, is strictly greater than 0.5. Table 4 compares the rate of good annotations obtained by taking into account semantic relations between keywords. We can observe that taking into account semantic relations between keywords improves the rate of good annotations by 6.9%. We can also see that our model is better than the GM-Mixture model, even if we do not take into account semantic relations between keywords.

Conclusion and future works

We have proposed a method for modeling, classifying and annotating weakly annotated images, which has the advantage to take into account semantic relations between annotations. Experimental results have demonstrated that semantic relation representation improves the recognition rate and the mean rate of good annotations. Moreover the evaluation has shown promising performance improvements with state-of-art classifiers. Further works will be devoted to capture the user's preference by considering a relevance feedback process. More precisely, the user's preference can be represented by the network parameter update (i.e. the probabilities of each variable in function of the new classified instance) during the inference process.

Figure 3 .

 3 Figure 3. Examples of "arabian horse" class images

Figure 2 .

 2 Figure 2. Dependences between keywordsimage initial possible keywords keywords after annotation extension keywords after annotation extension without taking into account semantic relations by using semantic relations bear bear bear black black black water water water grass grass bear bear bear black black black river river river water

Table 2 . Mean recognition rates (in %) of our

 2

	alone.
	training part	C	S	KW C + S C + S + KW
	25%	20.6 16.5 48.3 23.6	68.7
	35%	22.8 16.8 54.5	24	69.5
	50%	23.4 18.4 61.4 24.3	76.2
	65%	24.1 19.1 62.4	26	75.4
	75%	26	19.9 67.8 26.4	80.4
	90%	26	24	69.2 28.8	84

Table 3 . Mean recognition rates (in %) of the GM-Mixture model vs. our GM-B model

 3

	Training part GM-Mixture	GM-B without with SR
	25%	61	58,5	68,7
	35%	62,4	59	69,5
	50%	67,2	64,2	76,2
	65%	67,7	65,6	75,4
	75%	72,2	69,8	80,4
	90%	78,6	76	86

Table 4 . Mean rate (in %) of good annotations of the GM-Mixture model vs. our GM-B model

 4

	Training part GM-Mixture	GM-B without with SR
	25%	40	52	71
	35%	56,2	72,6	78,9
	50%	60	72,8	79,6
	65%	61,7	77,1	79,7
	75%	66	78,9	82,3
	90%	68,7	79	82,4