Clément Chadebec
email: clement.chadebec@inria.fr

Stéphanie Allassonnière
email: stephanie.allassonniere@inria.fr

Data Augmentation with Variational Autoencoders and Manifold Sampling

Keywords: Data Augmentation, VAE, Latent space modelling

We propose a new efficient way to sample from a Variational Autoencoder in the challenging low sample size setting 1 . This method reveals particularly well suited to perform data augmentation in such a low data regime and is validated across various standard and real-life data sets. In particular, this scheme allows to greatly improve classification results on the OASIS database where balanced accuracy jumps from 80.7% for a classifier trained with the raw data to 88.6% when trained only with the synthetic data generated by our method. Such results were also observed on 3 standard data sets and with other classifiers.

Introduction

Despite the apparent availability of always bigger data sets, the lack of data remains a key issue for many fields of application. One of them is medicine where practitioners have to deal with potentially very high dimensional data (e.g. functional Magnetic Resonance Imaging for neuroimaging) along with very low sample sizes (e.g. rare diseases or heterogeneous cancers) which make statistical analysis challenging and unreliable. In addition, the wide use of algorithms heavily relying on the deep learning framework [START_REF] Goodfellow | Deep learning[END_REF] and requiring a large amount of data has made the need for data augmentation (DA) crucial to avoid poor performance or over-fitting [START_REF] Shorten | A survey on Image Data Augmentation for Deep Learning[END_REF]. As an example, a classic way to perform DA on images consists in applying simple transformations such as adding random noise, rotations etc. However, it may be easily understood that such augmentation techniques are strongly data dependent2 and may still require the intervention of an expert assessing the relevance of the augmented samples. The recent development of generative models such as Generative Adversarial Networks (GAN) [START_REF] Goodfellow | Generative adversarial nets[END_REF] or Variational AutoEncoders (VAE) [START_REF] Kingma | Auto-encoding variational bayes[END_REF][START_REF] Rezende | Stochastic backpropagation and approximate inference in deep generative models[END_REF] paves the way for consideration of another way to augment the training data. While GANs have already seen some success [START_REF] Calimeri | Biomedical data augmentation using generative adversarial neural networks[END_REF][START_REF] Zhu | Data augmentation in emotion classification using generative adversarial networks[END_REF][START_REF] Antoniou | Data augmentation generative adversarial networks[END_REF] and even for medical data [START_REF] Liu | Wasserstein gan-based small-sample augmentation for new-generation artificial intelligence: a case study of cancer-staging data in biology[END_REF][START_REF] Sandfort | Data augmentation using generative adversarial networks (CycleGAN) to improve generalizability in CT segmentation tasks[END_REF] VAEs have been of least interest. One limitation of the use of both generative models relies in their need of a large amount of data to be able to generate faithfully. In this paper, we argue that VAEs can actually be used to perform DA in challenging contexts provided that we amend the way we generate the data. Hence, we propose:

-A new non prior-dependent generation method using the learned geometry of the latent space and consisting in exploring it by sampling along geodesics. -To use this method to perform DA in the small sample size setting on standard data sets and real data from OASIS database [START_REF] Marcus | Open access series of imaging studies (OASIS): Cross-sectional MRI data in young, middle aged, nondemented, and demented older adults[END_REF] where it allows to remarkably improve classification results.

Variational Autoencoder

Given a set of data x ∈ X , a VAE aims at maximizing the likelihood of the associated parametric model {P θ , θ ∈ Θ}. Assuming that there exist latent variables z ∈ Z living in a lower dimensional space Z, the marginal distribution writes

p θ (x) = Z p θ (x|z)q(z)dz , (1)
where q is a prior distribution over the latent variables and p θ (x|z) is most of the time a simple distribution and is referred to as the decoder. A variational distribution q ϕ (often taken as Gaussian) aiming at approximating the true posterior distribution and referred to as the encoder is then introduced. Using Importance Sampling allows to derive an unbiased estimate of p θ (x) such that E z∼qϕ pθ = p θ (x). Therefore, a lower bound on the logarithm of the objective function of Eq. ( 1) can be derived using Jensen's inequality:

log p θ (x) ≥ E z∼qϕ log p θ (x, z) -log q ϕ (z|x) = ELBO . (2)
Using the reparametrization trick makes the ELBO tractable and so can be optimised with respect to both θ and ϕ, the encoder and decoder parameters.

Once the model is trained, the decoder acts as a generative model and new data can be generated by simply drawing a sample using the prior q and feeding it to the decoder. Several axes of improvement of this model were recently explored. One of them consists in trying to bring geometry into the model by learning the latent structure of the data seen as a Riemannian manifold [START_REF] Arvanitidis | Latent space oddity: On the curvature of deep generative models[END_REF][START_REF] Chadebec | Geometry-aware hamiltonian variational auto-encoder[END_REF].

Some Elements on Riemannian Geometry

In the framework of differential geometry, one may define a Riemannian manifold M as a smooth manifold endowed with a Riemannian metric G which is a smooth inner product G : p → •|• p on the tangent space T p M defined at each point p of the manifold. The length of a curve γ between two points of the manifold z 1 , z 2 ∈ M and parametrized by t

∈ [0, 1] such that γ(0) = z 1 and γ(1) = z 2 is given by L(γ) = 1 0 γ(t) γ(t) dt = 1 0 γ(t)| γ(t) γ(t) dt .
Curves minimizing such a length are called geodesics. For any p ∈ M, the exponential map at p, Exp p , maps a vector v of the tangent space T p M to a point of the manifold p ∈ M such that the geodesic starting at p with initial velocity v reaches p at time 1.

In particular, if the manifold is geodesically complete, then Exp p is defined on the entire tangent space T p M.

The Proposed Method

We propose a new sampling method exploiting the structure of the latent space seen as a Riemannian manifold and independent from the choice of the prior distribution. The view we adopt is to consider the VAE as a tool to perform dimensionality reduction by extracting the latent structure of the data within a lower dimensional space. Having learned such a structure, we propose to exploit it to enhance the data generation process. This differs from the fully probabilistic view which uses the prior to generate. We believe that this is far from being optimal since the prior appears quite strongly data dependent. We will adopt the same setting as [START_REF] Chadebec | Geometry-aware hamiltonian variational auto-encoder[END_REF] and so use a RHVAE since the metric used by the authors is easily computable, constraints geodesic path to travel through most populated areas of the latent space and the learned Riemannian manifold is geodesically complete. Nonetheless, the proposed method can be used with different metrics as well as long as the exponential map remains computable. We now assume that we are given a latent space with a Riemannian structure where the metric has been estimated from the input data.

The Wrapped Normal Distribution

The notion of normal distribution may be extended to Riemannian manifolds in several ways. One of them is the wrapped normal distribution. The main idea is to define a classic normal distribution N (0, Σ) on the tangent space T p M for any p ∈ M and pushing it forward to the manifold using the exponential map. This defines a probability distribution on the manifold N W (p, Σ) called the wrapped normal distribution. Sampling from this distribution is straight forward and consists in drawing a velocity in the tangent space from N (0, Σ) and mapping it onto the manifold using the exponential map [START_REF] Mallasto | Wrapped gaussian process regression on riemannian manifolds[END_REF]. Hence, the wrapped normal allows for a latent space prospecting along geodesic paths. Nonetheless, this requires to compute Exp p which can be performed with a numerical scheme (see. App. C). On the left of Fig. 1 are displayed some geodesic paths with respect to the metric and different starting points (red dots) and initial velocities (orange arrows). Samples from N W (p, I d ) are also presented in the middle and the right along with the encoded input data. As expected this distribution takes into account the local geometry of the manifold thanks to the geodesic shooting steps. This is a very interesting property since it encourages the samples to remain close to the data as geodesics tend to travel through locations with the lowest volume element det G(z) and so avoid areas with very poor information.

Riemannian Random Walk

A natural way to explore the latent space of a VAE consists in using a random walk like algorithm which moves from one location to another with a certain probability. The idea here is to create a geometry-aware Markov Chain (z t ) t∈N where z t+1 is sampled using the wrapped normal z t+1 ∼ N W (z t , Σ). However, a drawback of such a method is that every sample of the chain is accepted regardless of its relevance. Nonetheless, by design, the learned metric is such that it has a high volume element far from the data [START_REF] Chadebec | Geometry-aware hamiltonian variational auto-encoder[END_REF]. This implies that it encodes in a way the amount of information contained at a specific location of the latent space. The higher the volume element, the less information we have.

The same idea was used in [START_REF] Lebanon | Metric learning for text documents[END_REF] where the author proposed to see the inverse metric volume element as a maximum likelihood objective to perform metric learning. In our case the likelihood definition writes

L(z) = ρ S (z) det G -1 (z) R d ρ S (z) det G -1 (z)dz , (3)
where ρ S (z) = 1 if z ∈ S, 0 otherwise, and S is taken as a compact set so that the integral is well defined. Hence, we propose to use this measure to assess the samples quality as an acceptance-rejection rate α in the chain where α( z, z) = min 1,

√ det G -1 ( z) √ det G -1 (z)
, z is the current state of the chain and z is the proposal obtained by sampling from the wrapped Gaussian N W (z, Σ). The idea is to compare the relevance of the proposed sample to the current one. The ratio is such that any new sample improving the likelihood metric L is automatically accepted while a sample degrading the measure is more likely to be rejected in the spirit of Hasting-Metropolis sampler. A pseudo-code is provided in Alg. 1.

Algorithm 1 Riemannian random walk

Input: z0, Σ for t = 1 → T do Draw vt ∼ N (0, Σ) zt ← Exp z t-1 (vt)
Accept the proposal zt with probability α end for

Discussion

It may be easily understood that the choice of the covariance matrix Σ in Alg. 1 has quite an influence on the resulting sampling. On the one hand, a Σ with strong eigenvalues will imply drawing velocities of potentially high magnitude allowing for a better prospecting but proposals are more likely to be rejected. On the other hand, small eigenvalues involve a high acceptance rate but it will take longer to prospect the manifold. An adaptive method where Σ depends on G may be considered and will be part of future work.

Remark 1 If Σ has small enough eigenvalues then Alg. 1 samples from Eq. (3)

For the following DA experiments we will assume that Σ has small eigenvalues and so will sample directly using this distribution. See app. A for sampling results using the aforementioned method.

Data Augmentation Experiments For Classification

In this section, we explore the ability of the method to enrich data sets to improve classification results.

Augmentation Setting

We first test the augmentation method on three reduced data sets extracted from well-known databases MNIST and EMNIST. For MNIST, we select 500 samples applying either a balanced split or a random split ensuring that some classes are far more represented. For EMNIST, we select 500 samples from 10 classes such that they are composed of both lowercase and uppercase characters so that we end up with a small database with strong variability within classes. These data sets are then split such that 80% is allocated for training (referred to as the raw data) and 20% for validation. For a fair comparison, we use the original test set (e.g. ∼1000 samples per class for MNIST) to test the classifiers. This ensures statistically meaningful results while assessing the generalisation power on unseen data. We also validate the proposed DA method on the OASIS database which represents a nice example of day-to-day challenges practitioners have to face and is a benchmark database. We use 2D gray scale MR Images (208x176) with a mask notifying brain tissues and are referred to as the masked T88 images in [START_REF] Marcus | Open access series of imaging studies (OASIS): Cross-sectional MRI data in young, middle aged, nondemented, and demented older adults[END_REF]. We refer the reader to their paper for further image preprocessing details. We consider the binary classification problem consisting in trying to detect MRI of patients having been diagnosed with Alzheimer Disease (AD). We split the 416 images into a training set (70%) (raw data), a validation set (10%) and a test set (20%). A summary of demographics, mini-mental state examination (MMSE) and global clinical dementia rating (CDR) is made available in Table . 1. On the one hand, for each data set, the train set (raw data) is augmented by a factor 5, 10 and 15 using classic DA methods (random noise, cropping etc.). On the other hand, VAE models are trained individually on each class of the raw data. The generative models are then used to produce 200, 500, 1k or 2k synthetic samples per class with either the classic generation scheme (i.e. the prior) or the proposed method. We then train classifiers with 5 independent runs on 1) the raw data; 2) the augmented data using basic transformations; 3) the augmented data using the VAE models; 4) only the synthetic data generated by the VAEs. A DenseNet model3 [START_REF] Huang | Densely connected convolutional networks[END_REF] is used for the toy data while we also train hand made MLP and CNN models on OASIS (See App. E).

The main metrics obtained on the test set are reported in Tables. 2 and 3.

Results

Toy Data As expected generating new samples using the proposed method improves their relevance. The method indeed allows for a quite impressive gain in the model accuracy when synthetic samples are added to the real ones (leftmost column of Table . 2). This is even more striking when looking at the rightmost column where only synthetic samples are used to train the classifier. For instance, when only 200 synthetic samples per class for MNIST are generated with a VAE and used to train the classifier, the classic method fails to produce meaningful samples since a loss of 20 pts in accuracy is observed when compared to the raw data. Interestingly, our method seems to avoid such an effect. Even more impressive is the fact that we are able to produce synthetic data sets on which the classifier outperforms greatly the results observed on the raw data (3 to 6 pts gain in accuracy) while keeping a relatively low standard deviation (see gray cells). Secondly, this example also shows why geometric DA is still questionable and remains data dependent. For instance, augmenting the raw data by a factor 10 (including flips and rotations) does not seem to have a notable effect on the MNIST data sets but still improves results on EMNIST. On the contrary, our method seems quite robust to data set changes.

OASIS Balanced accuracy obtained on OASIS with 3 classifiers is made available in Table . 3. In this experiment, using the new generation scheme again improves overall the metric for each classifier when compared to the raw data and other augmentation methods. Moreover, the strong relevance of the created samples is again supported by the fact that the classifiers are again able to strongly outperform the results on the raw data even when trained only with synthetic ones. Finally, the method appears robust to classifiers and can be used with high-dimensional complex data such as MRI.

Conclusion

In this paper, we proposed a new way to generate new data from a Variational Autoencoder which has learned the latent geometry of the input data. This method was then used to perform DA to improve classification tasks in the low sample size setting on both toy and real data and with different kind of classifiers. In each case, the method allows for an impressive gain in the classification metrics (e.g. balanced accuracy jumps from 80.7 to 88.6 on OASIS). Moreover, the relevance of the generated data was supported by the fact that classifiers were able to perform better when trained with only synthetic data than on the raw data in all cases. Future work would consist in using the method on even more challenging data such as 3D volumes and using smaller data sets.

Standard Data Sets

The method is first validated on a hand-made synthetic data set composed of 180 binary images of circles and rings of different diameters and thicknesses (see training samples in Fig. 3). We then train a VAE with a normal prior, a VAE with a VAMP prior [START_REF] Tomczak | Vae with a vampprior[END_REF] and a RHVAE until the ELBO does not improve for 50 epochs. Any relevant parameters setting is stated in App. D. Fig. 2 highlights the obtained samplings with each model using either the prior-based generation procedure or the one proposed in this paper. The first row presents the learned latent space along with the means of the posteriors associated to the training data (crosses) and 100 latent space samples for each generation method (blue dots). The second row displays the corresponding decoded images. The first outcome of such a study is that sampling from the prior distribution N (0, I d ) leads to a poor latent space prospecting. Therefore, even with balanced training classes, we end up with a model over-representing certain elements of a given class (rings). This is even more striking with the RHVAE since it tends to stretch the resulting latent space. This effect seems nonetheless mitigated by the use of a multimodal prior such as the VAMP. However, another limitation of prior-based methods is that they may sample in locations of the latent space potentially containing very few information (i.e. where no data is available). Since the decoder appears to interpolate quite linearly, the classic scheme will generate images which mainly correspond to a superposition of samples (see an example with the red dots in Fig. 2 and the corresponding samples framed in red). Moreover, there is no way to assess a sample quality before decoding it and assessing visually its relevance. These limitations may lead to a (very) poor representation of the actual data set diversity while presenting quite a few irrelevant samples. Impressively, sampling along geodesic paths leads to far more diverse and sharper samples. The new sampling scheme avoids regions that have been poorly prospected so that almost every decoded sample is visually satisfying and accounts for the data set diversity. In Fig. 3, we also compare the models on a reduced MNIST [START_REF] Lecun | The MNIST database of handwritten digits[END_REF] data set composed of 120 samples of 3 different classes and a reduced FashionMNIST [START_REF] Xiao | Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms[END_REF] data set composed again of 120 samples from 3 distinct classes. The models are trained with the same neural network architectures, batch size and learning rate. An early stopping strategy is adopted and consists in stopping training if the ELBO does not improve for 50 epochs. As discussed earlier, changing the prior may indeed improve the model generation capacity. For instance samples from the VAE with the VAMP prior (3 rd row of Fig. 3) are closer to the training data (1 st row of Fig. 3) than with the Gaussian prior (2 nd and 4 th row). The model is for instance able to generate circles when trained with the synthetic data while models using a standard normal prior are not. Nonetheless, a non negligible part of the generated samples are degraded (see saturated images for the reduced MNIST data for instance). This aspect is mitigated with the proposed generation method which generates more diverse and sharper samples.

OASIS Database

The new generation scheme is then assessed on the publicly available OASIS database composed of 416 patients aged 18 to 96, 100 of whom have been diagnosed with very mild to moderate Alzheimer disease (AD). A VAE and a RHVAE are then trained to generate either cognitively normal (CN) or AD patients with the same early stopping criteria as before. Fig. 4 shows samples extracted from the training set (top), MRI generated by a vanilla VAE (2 nd row) and images from the Riemannian random walk we propose (3 rd row). For each method, the upper row shows images of patients diagnosed CN while the bottom row presents an AD diagnosis. Again the proposed sampling seems able to generate a wider range of sharp samples while the VAE appears to produce non-realistic degraded images which are very similar (see red frames). For example, the proposed scheme allows us to generate realistic old 4 patients with no AD (blue frames) or younger patients with AD (orange frames) even though they are under-represented in the training set. Generating 100 images of 3) from the VAMP prior VAE ; 4) from a RHVAE and the prior-based generation scheme; 5) from a RHVAE and using the proposed Riemannian random walk. All the models are trained with the same encoder and decoder networks and identical latent space dimension. An early stopping strategy is adopted and consists in stopping training if the ELBO does not improve for 50 epochs.

OASIS database takes 1 min. with the proposed method and 40 sec. 5 with Intel Core i7 CPU (6x1.1GHz) and 16 GB RAM. Therefore, q( z, z) = q(z, z) .

Finally, the ratio α in the Riemannian random walk may be seen as a Hasting-Metropolis ratio where the target density is given by Eq. ( 3) and so the algorithm samples from such a distribution.

Fig. 1 :

 1 Fig. 1: Left: Geodesic shooting in a latent space learned by a RHVAE with different starting points (red dots) and initial velocities (orange arrows). Middle and right: Samples from the wrapped normal N W (p, I d ). The log metric volume element log det G(z) is presented in gray scale.

Fig. 2 :

 2 Fig. 2: Comparison between prior-based generation methods and the proposed Riemannian random walk (ours). Top: the learned latent space with the encoded training data (crosses) and 100 samples for each method (blue dots). Bottom: the resulting decoded images. The models are trained on 180 binary circles and rings with the same neural network architectures.

4Fig. 3 :

 3 Fig.3: Comparison of 4 sampling methods on the reduced MNIST, reduced Fashion and the synthetic data sets. From top to bottom: 1) samples extracted from the training set; 2) samples generated with a Vanilla VAE and using the prior; 3) from the VAMP prior VAE ; 4) from a RHVAE and the prior-based generation scheme; 5) from a RHVAE and using the proposed Riemannian random walk. All the models are trained with the same encoder and decoder networks and identical latent space dimension. An early stopping strategy is adopted and consists in stopping training if the ELBO does not improve for 50 epochs.

Fig. 4 :

 4 Fig.4: Generation of CN or AD patients from the OASIS database. Training samples (top), generation with a VAE and normal prior (2 nd row) and with the Riemannian random walk (bottom). Generating using the prior leads to either unrealistic images or similar samples (red frames) while the proposed method generates sharper and more diverse samples. For instance, it is able to generate CN older patients (blue frames) or younger AD (orange frames) even though they are under-represented within the training set.

Table 1 :

 1 Summary of OASIS database demographics, mini-mental state examination (MMSE) and global clinical dementia rating (CDR) scores.

	Data set Label Obs.	Age	Sex M/F	MMSE	CDR
	OASIS	CN AD	316 45.1 ± 23.9 119/197 29.1 ± 1.1 0: 316 100 76.8 ± 7.1 41/59 24.3 ± 4.1 0.5: 70 , 1: 28, 2: 2
	Train	CN AD	220 45.6 ± 23.6 70 77.4 ± 6.8	86/134 29/41	29.1 ± 1.2 0: 220 23.7 ± 4.3 0.5: 47 , 1: 21, 2: 2
	Val	CN AD	30 12	48.9 ± 24.1 75.4 ± 7.2	11/19 4/8	29.2 ± 0.8 0: 30 25.8 ± 4.2 0.5: 7 , 1: 5, 2: 0
	Test	CN AD	66 18	41.7 ± 24.3 75.1 ± 7.5	22/44 8/10	29.0 ± 1.0 0: 66 25.8 ± 2.7 0.5: 16 , 1: 2, 2: 0

Table 2 :

 2 DA on toy data sets. Mean accuracy and standard deviation across 5 independent runs are reported. In gray are the cells where the accuracy is higher on synthetic data than on the raw data.

	Data sets	MNIST	MNIST** EMNIST** MNIST	MNIST** EMNIST**
	Raw data 89.9 (0.6) 81.6 (0.7) 82.6 (1.4)	-	-	-
		Raw + Synthetic		Synthetic only
	Aug. (X5) 92.8 (0.4) 86.5 (0.9) 85.6 (1.3)	-	-	-
	Aug. (X10) 88.3 (2.2) 82.0 (2.4) 85.8 (0.3)	-	-	-
	Aug. (X15) 92.8 (0.7) 85.9 (3.4) 86.6 (0.8)	-	-	-
	VAE-200* 88.5 (0.9) 84.1 (2.0) 81.7 (3.0) 69.9 (1.5) 64.6 (1.8) 65.7 (2.6)
	VAE-500* 90.4 (1.4) 87.3 (1.2) 83.4 (1.6) 72.3 (4.2) 69.4 (4.1) 67.3 (2.4)
	VAE-1k* 91.2 (1.0) 86.0 (2.5) 84.4 (1.6) 83.4 (2.4) 74.7 (3.2) 75.3 (1.4)
	VAE-2k* 92.2 (1.6) 88.0 (2.2) 86.0 (0.2) 86.6 (2.2) 79.6 (3.8) 78.9 (3.0)
	RHVAE-200*	89.9 (0.5) 82.3 (0.9) 83.0 (1.3) 76.0 (1.8) 61.5 (2.9) 59.8 (2.6)
	RHVAE-500*	90.9 (1.1) 84.0 (3.2) 84.4 (1.2) 80.0 (2.2) 66.8 (3.3) 67.0 (4.0)
	RHVAE-1k*	91.7 (0.8) 84.7 (1.8) 84.7 (2.4) 82.0 (2.9) 69.3 (1.8) 73.7 (4.1)
	RHVAE-2k*	92.7 (1.4) 86.8 (1.0) 84.9 (2.1) 85.2 (3.9) 77.3 (3.2) 68.6 (2.3)
	Ours-200* 91.0 (1.1) 84.1 (2.0) 85.1 (1.1) 87.2 (1.1) 79.5 (1.6) 77.1 (1.6)
	Ours-500* 92.3 (1.1) 87.7 (0.9) 85.1 (1.1) 89.1 (1.3) 80.4 (2.1) 80.2 (2.0)
	Ours-1k* 93.3 (0.8) 89.7 (0.8) 87.0 (1.0) 90.2 (1.4) 86.2 (1.8) 82.6 (1.3)
	Ours-2k* 94.3 (0.8) 89.1 (1.9) 87.6 (0.8) 92.6 (1.1) 87.6 (1.3) 86.0 (1.0)

* Number of generated samples ** Unbalanced data sets

Table 3 :

 3 DA on OASIS data base. Mean balanced accuracy on independent 5 runs with several classifiers.

	Networks	MLP		CNN	Densenet
	Raw data 80.7 (4.1)	-	72.5 (3.5)	-	77.4 (3.3)	-
	Raw +	Synthetic	Raw +	Synthetic	Raw +	Synthetic
	Synthetic	Only	Synthetic	Only	Synthetic	Only
	Aug. (X5) 84.3 (1.3)	-	80.0 (3.5)	-	73.9 (5.1)	-
	Aug. (X10) 76.0 (2.8)	-	82.8 (3.7)	-	78.3 (4.1)	-
	Aug. (X15) 78.7 (5.3)	-	80.3 (3.7)	-	76.6 (1.1)	-
	VAE-200 * 80.7 (1.5) 77.8 (1.3) 79.4 (3.6) 65.0 (12.3) 76.5 (3.2) 74.0 (3.0) VAE-500 * 79.7 (1.4) 77.4 (1.5) 72.6 (7.0) 70.2 (5.0) 74.9 (4.3) 72.8 (1.8) VAE-1000 * 81.3 (0.0) 76.5 (0.6) 74.4 (9.4) 73.0 (3.3) 73.5 (1.3) 74.9 (2.6) VAE-2000 * 80.7 (0.3) 78.1 (1.6) 71.1 (4.9) 76.9 (2.6) 74.0 (4.9) 73.3 (3.4)
	Ours-200 * 84.3 (0.0) 86.7 (0.4) 76.4 (5.0) 75.4 (6.6) 78.2 (3.0) 74.3 (4.8) Ours-500 * 87.2 (1.2) 88.6 (1.1) 81.8 (4.6) 81.8 (3.7) 80.2 (2.8) 84.2 (2.8) Ours-1000 * 84.2 (0.3) 84.4 (1.8) 83.5 (3.2) 79.8 (2.8) 82.2 (4.7) 76.7 (3.8) Ours-2000 * 85.3 (1.9) 84.2 (3.3) 84.5 (1.9) 83.9 (1.9) 82.9 (1.8) 73.6 (5.8)

* Number of generated samples

A code is available at https://github.com/clementchadebec/Data Augmentation with VAE-DALI

Think of digits where rotating a 6 gives a 9 for example.

We use the code in[START_REF] Amos | bamos/densenet.pytorch[END_REF] (See App. E).

Depends on the chains' length (here 200 steps per image).

Acknowledgment

The research leading to these results has received funding from the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute) and reference ANR-10-IAIHU-06 (Agence Nationale de la Recherche-10-IA Institut Hospitalo-Universitaire-6). Data were provided in part by OA-SIS: Cross-Sectional: Principal Investigators: D. Marcus, R, Buckner, J, Csernansky J. Morris; P50 AG05681, P01 AG03991, P01 AG026276, R01 AG021910, P20 MH071616, U24 RR021382

Appendix A: Comparison with Prior-Based Methods

In this section, we compare the samples quality between prior-based methods and ours on various standard and real-life data sets.

Appendix B: Discussion of Remark. 1

Remark 2 If Σ has small enough eigenvalues then Alg. 1 samples from

where ρ S (z) = 1 if z ∈ S, 0 otherwise, and S is taken as a compact set so that the integral is well defined.

If Σ has small enough eigenvalues, it means that the initial velocity v ∼ N (0, Σ) will have a low magnitude with high probability. In such a case, we can show with some approximation that the ratio α in the Riemannian random walk is a Hasting-Metropolis ratio with target density given by Eq. ( 4). We recall that the classic Hasting-Metropolis ratio writes

where π is the target distribution and q a proposal distribution. In the case of small magnitude velocities, one may show that q is symmetric that is q(x, y) = q(y, x) .

In our setting, a proposal z is made by computing the geodesic γ starting at γ(0) = z with initial velocity γ(0) = v where v ∼ N (0, Σ) and evaluating it at time 1. First, we remark that γ is well defined since the Riemnanian manifold M = (R, g) is geodesically complete and γ is unique. Moreover, we have that ←γ is the unique geodesic with initial position ←γ (0) = z = γ(1) and initial velocity ← γ (0) = -γ(1) and we have

In the case of small enough initial velocity, a taylor expansion of the exponential may be performed next to 0 ∈ T z M and consists in approximating geodesic curves with straight lines. That is, for t

In such a case we have

Moreover, we have on the one hand

On the other hand

Appendix C: Computing the Exponential map

To compute the exponential map at any given point p ∈ M and for any tangent vector v ∈ T p M we rely on the Hamiltonian definition of geodesic curves. First, for any given v ∈ T p M, the linear form:

is called a moment and is a representation of v in the dual space. In short, we may write q v (u) = u Gv. Then, the definition of the Hamiltonian follows

where g * p is the dual metric whose local representation is given by G -1 (p), the inverse of the metric tensor. Finally, all along geodesic curves the following equations hold

Such a system of differential equations may be integrated pretty straight forwardly using simple numerical schemes such as the second order Runge Kutta integration method and Alg. 2 as in [START_REF] Louis | Computational and statistical methods for trajectory analysis in a Riemannian geometry setting[END_REF]. Noteworthy is the fact that such an algorithm only involves one metric tensor inversion at initialization to recover the initial moment from the initial velocity. Moreover, it involves closed form operations since the inverse metric tensor G -1 is known (in our case) and so the gradients in Eq. ( 5) can be easily computed.

Algorithm 2 Computing the Exponential map

Appendix D: VAEs Parameters Setting

Table . 4 summarizes the main hyper-parameters we use to perform the experiments presented in the paper while Table . 5 shows the neural networks architectures employed. As to training parameters, we use a Adam optimizer [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] with a learning of 10 -3 . For the augmentation experiments, we stop training if the ELBO does not improve for 20 epochs for all data sets except for OASIS where the learning rate is decreased to 10 -4 and training is stopped if the ELBO does not improve for 50 epochs. As to the models used as benchmark for data augmentation, the DenseNet implementation we use is the one in [START_REF] Amos | bamos/densenet.pytorch[END_REF] with a growth rate equals to 10, depth of 20 and 0.5 reduction and is trained with a learning rate of 10 -3 . For OASIS, the MLP has 400 hidden units and relu activation function and the CNN is as follows For the toy data, the DenseNet is trained until the loss does not improve on the validation set for 50 epochs. On OASIS, we make a random search on the learning rate for each model chosen in the range [10 -1 , 10 -2 , 10 -3 , 10 -4 , 10 -5 , 10 -6 ]. The model is trained on 5 independent runs with the same learning rate and keep the model achieving the best mean balanced accuracy on the validation set. For the CNN and MLP, we stop training if the validation loss does not improve for 20 epochs and for the densenet training is stopped if no improvement is observed on the validation loss for 10 epochs. Each model is trained with an Adam optimizer.


Simon-Martin Schröder

Rainer Kiko
email: rkiko@geomar.de

Jean-Olivier Irisson
email: irisson@obs-vlfr.fr

Reinhard Koch

Low-Shot learning of plankton categories

The size of current plankton image datasets renders manual classification virtually infeasible. The training of models for machine classification is complicated by the fact that a large number of classes consist of only a few examples. We employ the recently introduced weight imprinting technique in order to use the available training data to train accurate classifiers in absence of enough examples for some classes. The model architecture used in this work succeeds in the identification of plankton using machine learning with its unique challenges, i.e. a limited number of training examples and a severely skewed class size distribution. Weight imprinting enables a neural network to recognize small classes immediately without re-training. This permits the mining of examples for novel classes.

(a) UVP5 (b) ZooScan

Introduction

Planktonic organisms -drifters in the ocean -cover a large size range from nanometer-sized bacteria to meter-sized jellyfishes. While some of these organisms such as the planktonic copepods can be observed nearly everywhere, others occupy only small niches. Past observations allow an overview of the most abundant groups but we can expect that the number of classes will keep increasing with increasing sampling effort.

Current imaging systems (e.g. UVP5, ZooScan, ISIIS, FlowCytoBot [START_REF] Picheral | The Underwater Vision Profiler 5: An advanced instrument for high spatial resolution studies of particle size spectra and zooplankton[END_REF][START_REF] Gorsky | Digital zooplankton image analysis using the ZooScan integrated system[END_REF][START_REF] Cowen | In situ Ichthyoplankton Imaging System (ISIIS): system design and preliminary results[END_REF][START_REF] Olson | A submersible imaging-in-flow instrument to analyze nano-and microplankton: Imaging FlowCytobot[END_REF]) that target the micro to macroplankton size range (approx. 10 µm to 10 cm) yield large amounts of image data every day. The size of the resulting datasets renders manual classification virtually infeasible. Therefore, accurate machine classification is a critical step in the processing of these data. Usually, the result is later verified by human experts. Even the annotation of pre-classified data is still labor-intensive [START_REF] Culverhouse | An empirical assessment of the consistency of taxonomic identifications[END_REF][START_REF] Faillettaz | Imperfect automatic image classification successfully describes plankton distribution patterns[END_REF], which is why maximally accurate models are crucial.

This work is part of a larger undertaking with the aim of continually monitoring newly acquired data for classes that have been overlooked so far. The observation of new kinds of objects means that the machine classification models need to be updated to incorporate these novel classes. In addition, plankton image datasets typically consist of few classes with many examples and many classes with only a few examples. A major problem is therefore the scarcity of training data for a large number of classes.

Here we tackle the question of how available labeled data can be used to train accurate machine classifiers when some class sizes in the training data set are very small, which is known as low-shot learning. We employ a recently presented method for low-shot learning called weight imprinting [START_REF] Qi | Low-shot learning with imprinted weights[END_REF] that is able to incorporate new classes into a model without re-training it from scratch.

The contribution of this present paper is a rigorous evaluation of whether weight imprinting works satisfactorily for two plankton image datasets. We also examine the necessity of the architectural choices made in [START_REF] Qi | Low-shot learning with imprinted weights[END_REF].

Our hypothesis is that once we have trained a classifier, we can use it to find more examples for underrepresented and novel classes within a large set of unlabeled data. In this current work, we therefore focus on the smaller classes instead of maximizing overall accuracy.

The remaining part of this paper is structured as follows. In section 2 we introduce two plankton image datasets. Then we review the related work in section 3. Section 4 reproduces the most important aspects of the weight imprinting technique. In section 5 we apply weight imprinting to both plankton datasets. Subsequently, we report and discuss our results in section 6 and draw a conclusion in section 7.

Datasets

We evaluate the approach on two datasets extracted from the plankton image database EcoTaxa [START_REF] Picheral | EcoTaxa[END_REF]. The objects were sampled on numerous cruises in many parts of the world's oceans. The first dataset (UVP5) consists of 588,121 pelagic underwater images acquired with the UVP5 [START_REF] Picheral | The Underwater Vision Profiler 5: An advanced instrument for high spatial resolution studies of particle size spectra and zooplankton[END_REF]. The images were sorted by experts into 65 classes. The dataset is available from the authors upon reasonable request. The second dataset (ZooScan) [START_REF] Elineau | Zooscannet: plankton images captured with the zooscan[END_REF] 16) othertocheck_darksphere ( 16) Thaliacea_Salpida ( 13) Annelida_Polychaeta [START_REF] Faillettaz | Imperfect automatic image classification successfully describes plankton distribution patterns[END_REF] Solmundella_Solmundella bitentaculata (8) temporary_t003 ( 8) temporary_t015 ( 8) Terebellida_Flota ( 7) Mollusca_Cephalopoda ( 6) Appendicularia_body ( 6) Diplostraca_Cladocera ( 5) Euopisthobranchia_Gymnosomata ( 5) digitized with the ZooScan system [START_REF] Gorsky | Digital zooplankton image analysis using the ZooScan integrated system[END_REF] and sorted into 93 classes. We use a subset of 1,146,684 images for training and validation. Both datasets are severely imbalanced, as shown in Figure 2 for the UVP5 dataset. The 10 % most populated classes contain more than 77 % of all objects and the class sizes span multiple orders of magnitude. Figure 1 shows some exemplary objects from both datasets.

Euopisthobranchia_Thecosomata (4) temporary_t002 (4) temporary_t009 (3) temporary_t005 (2)

Related Work

One-shot and low-shot learning One-shot and low-shot learning is concerned with training a model with only one or a few training examples for each class.

Low-shot learning using neural networks usually incorporates two phases [START_REF] Hariharan | Low-Shot Visual Recognition by Shrinking and Hallucinating Features[END_REF]. In the representation learning phase, the learner finds a suitable feature space, usually guided by a set of base classes with abundant examples. In the lowshot learning phase, a classifier is trained that incorporates both base and lowshot classes. Different approaches emphasize different aspects of the process [START_REF] Choe | Face Generation for Lowshot Learning using Generative Adversarial Networks[END_REF]: the discriminative approach is concerned with learning powerful features, the generative approach enlarges the training set by augmentation or generation and the network structural approach utilizes new types of classifiers.

Weight imprinting [START_REF] Qi | Low-shot learning with imprinted weights[END_REF], label diffusion [START_REF] Douze | Low-shot learning with large-scale diffusion[END_REF], and metric learning [START_REF] Mensink | Distance-Based Image Classification: Generalizing to New Classes at Near-Zero Cost[END_REF] belong to the third category. They provide low-shot learning without having to retrain the whole model from scratch.

Classification of plankton images

Classification of plankton images is traditionally performed using shallow models, like Support Vector Machines or Random Forests, trained with handcrafted local features measured on the image (e.g. size, grey level distribution, etc.) [START_REF] Culverhouse | Automatic classification of field-collected dinoflagellates by artificial neural network[END_REF][START_REF] Blaschko | Automatic In Situ Identification of Plankton[END_REF][START_REF] Sosik | Automated taxonomic classification of phytoplankton sampled with imaging-in-flow cytometry[END_REF][START_REF] Gorsky | Digital zooplankton image analysis using the ZooScan integrated system[END_REF][START_REF] Ellen | Quantifying California current plankton samples with efficient machine learning techniques[END_REF].

Since Kaggle's National Data Science Bowl competition to sort data from ISIIS [START_REF] Cowen | In situ Ichthyoplankton Imaging System (ISIIS): system design and preliminary results[END_REF], there has been a slow transition towards deep models [START_REF] Py | Plankton classification with deep convolutional neural networks[END_REF][START_REF] Lee | Plankton classification on imbalanced large scale database via convolutional neural networks with transfer learning[END_REF][START_REF] Graham | Submanifold Sparse Convolutional Networks[END_REF][START_REF] Orenstein | Transfer Learning and Deep Feature Extraction for Planktonic Image Data Sets[END_REF][START_REF] Christiansen | Particulate matter flux interception in oceanic mesoscale eddies by the polychaete Poeobius sp[END_REF].

In the representation learning phase, we rely on the observations of [START_REF] Orenstein | Transfer Learning and Deep Feature Extraction for Planktonic Image Data Sets[END_REF] regarding the classification of plankton images with deep learning models, i.e. that the initialization with pre-trained weights outperforms random initialization.

Weight imprinting

In this section, we outline the most important aspects of weight imprinting as introduced by [START_REF] Qi | Low-shot learning with imprinted weights[END_REF].

The technique follows the two-phase paradigm of [START_REF] Hariharan | Low-Shot Visual Recognition by Shrinking and Hallucinating Features[END_REF]: The set of all classes C is partitioned into base classes C 0 with enough training data and the smaller low-shot classes C + , i.e. C = C 0 ∪ C + .

In the representation learning phase, a convolutional neural network (CNN) is trained to distinguish the base classes with enough training data C 0 . In the low-shot learning phase, the classifier is then updated with calculated weights (see section 4.2 for details) to also to distinguish the smaller low-shot classes C + . Finally, the whole model can be fine-tuned to further increase its predictive power.

Neural network model

The model consists of two stages: A feature extractor network f : I → R d maps an input image x ∈ I to an L 2 -normalized d-dimensional feature vector ŷ. The second stage is a modified softmax classifier g : R d → [0, 1] |C| that maps the feature activations to a discrete probability distribution of |C| classes.

g i (y) = exp(s • ŵT i ŷ) j∈C exp(s • ŵT j ŷ) (1)
ŵi is the the weight vector corresponding to class i and is normalized to unit length as well. The scalar product ŵT i ŷ is the angle or cosine similarity [START_REF] Luo | Cosine Normalization: Using Cosine Similarity Instead of Dot Product in Neural Networks[END_REF] between the feature vector and the weight vector. A weight vector ŵi therefore acts as a template for class i. s is a learnable scale factor that allows the probabilities to match the one-hot encoding of classes [START_REF] Wang | NormFace: L2 Hypersphere Embedding for Face Verification[END_REF].

Low-shot learning

To learn a new class c + ∈ C + , the weight matrix is extended by a column w + . It follows from the above characterization of weight vectors ŵi and image feature vectors ŷ that they are interchangeable. Therefore, w + can be calculated directly from the feature vectors of the examples of class c + . In the simplest case, if only

Experiments

This section describes the experiments to evaluate the ability of weight imprinting to incorporate new classes into a plankton classification model without completely re-training from scratch.

Network architecture

The model architecture is summarized in table 1. The feature extractor network is based on the ResNet18 architecture, as it has a favorable accuracy-speed tradeoff [START_REF] Canziani | An Analysis of Deep Neural Network Models for Practical Applications[END_REF]. It is initialized with weights pre-trained on the ImageNet dataset [START_REF] Deng | ImageNet: A largescale hierarchical image database[END_REF]. The grayscale plankton images are converted to color images to fit the pretrained model. We use 512-dimensional embeddings as we observed that the 64-dimensional embeddings from the original paper delayed the convergence of the training and did not bring an advantage. The last three layers implement the operations required for the weight imprinting as described in section 4.1 and are initialized randomly.

The whole model is fine-tuned to the task at hand, following the common practice [START_REF] Chu | Best Practices for Fine-Tuning Visual Classifiers to New Domains[END_REF]. Each experiment is carried out with three-fold cross-validation. To counter the class imbalance in the dataset we randomly subsample 1000 samples from the larger classes for each training epoch independently. Early stopping is used to avoid overfitting to the training split. To treat all classes equally, we weight the validation loss by the inverse class size. The initial learning rate is set to 1 × 10 -4 and decreased whenever the validation loss plateaus until it reaches 1 × 10 -8 . The Adam algorithm [START_REF] Kingma | Adam: A Method for Stochastic Optimization[END_REF], an extension to stochastic gradient descent, is used for parameter optimization. The batch size is set to 128 images. The images are cropped to their tight bounding box and padded to a square with a minimum edge length of 128px. Images larger than 128px are shrunken to this size. The grey values are scaled to the [0, 1] range. We perform training-time augmentation using random rotations in 90 • steps, random horizontal and vertical flips and Gaussian noise with σ = 0.001. The models are trained using the PyTorch deep learning library [START_REF] Paszke | Automatic differentiation in PyTorch[END_REF] on an NVIDIA GeForce GTX 1070 GPU.

Baselines

As a baseline (bl), we train the whole network on all classes C = C 0 ∪ C + jointly and without altering the weights in a separate step. Larger classes are subsampled, smaller classes oversampled. We also conduct an ablation experiment to examine the necessity of the architectural choices made in [START_REF] Qi | Low-shot learning with imprinted weights[END_REF] by comparing the original architecture to two modified versions where we removed the weight normalization (bl-w) and subsequently the feature normalization as well (bl-wf).

Representation learning

In the first phase of model training, the model learns the base classes C 0 . For the UVP5 dataset, we selected the classes with more than 1000 members in the training split (22 classes out of 65) as base classes. For the ZooScan dataset, the classes with more than 1500 members in the training split (44 classes out of 93) were selected as base classes.

The network is trained until the validation loss does not decrease for 25 epochs. No oversampling is performed because the minimum class size (1000 or 1500) is equal to or larger than the number of images needed per epoch (1000).

Low-shot learning

Now, the low-shot weights of the base network are set to their calculated values. For this purpose, we apply the feature extractor part of the network to every image. For each low-shot class c i ∈ C + , we calculate the mean feature vector, re-normalize it, and write it into the entry ŵi of the weight matrix in the classifier part of the network corresponding to the respective class. We compare the described mean imprinting (mi) to random imprinting (ri), where ŵi is initialized randomly.

Fine-tuning

Finally, the imprinted networks are fine-tuned (mi+ft, ri+ft). Classes with less than 1000 examples are oversampled to counteract the class imbalance.

Results and Discussion

Tables 2 and3 list the evaluation results for the UVP5 and ZooScan datasets, respectively. Both datasets behave comparably regarding the success of weight imprinting. We show the arithmetic average and standard deviation of three validation splits. Macro precision and macro recall are reported for base and low-shot classes separately. We do not report accuracy as it is mainly influenced by the base classes that contain most of the examples. Bold entries are global maxima, italic entries are maximal among their respective group.

Low-shot learning

For both datasets, mean imprinting (mi) leads to a better precision for the base classes than random imprinting (ri) and to a nonzero recall and precision of the low-shot classes. However, recall for the base classes is impaired. This was expected because as the low-shot classes are initialized with plausible locations in the feature space, they will draw off objects from the base classes.

As apparent in table 4, the time to calculate the weights is negligible. This is a huge advantage of weight-imprinting compared to other training methods when speed is important, e.g. when a user iteratively trains a model.

Figures 5 and6 show the confusion matrices for both datasets averaged over all three splits and examples images for the three or four most often misclassifications of existing classes as novel. The entries of the matrices are ordered by ascending class size and the low-shot classes are separated by red lines.

In the UVP5 dataset, images of a few of the more abundant base classes contaminate the predictions of low-shot classes (lower left rectangle in fig. 5). In the ZooScan this behavior is less pronounced and the confusion matrix has a stronger diagonal and looks more uniform (fig. 6), i.e. the model is more accurate. The images representative of true and falsely predicted classes are very similar in most cases. In fact, several of the smaller classes were defined only recently and accordingly, many of their belonging images were assigned to more general classes in earlier days. We therefore suspect that some of the "errors" made by the models originate from an incoherent labeling of the data. Another type of error is the confusion of classes that differ only by a minuscule feature, for example the missing tail of the Cladocera in fig. 5 or the regular shape of the Ephyra in fig. 6.

Fine-tuning

Fine-tuning (mi+ft) always improves over mean imprinting alone (mi). This is in agreement with [START_REF] Qi | Low-shot learning with imprinted weights[END_REF]. However, fine-tuning a mean imprinted model does not yield better results than fine-tuning a randomly initialized model (ri+ft). In fact, both perform in a very similar way, while most scores are slightly higher for random initialization. Here, our results differ from [START_REF] Qi | Low-shot learning with imprinted weights[END_REF]. The reason is presumably overfitting of the weight imprinted models to too few samples in the training split.

Finetuning a mean imprinted model roughly halves the training time compared to the baseline.

Baselines

When comparing the baseline models amongst each other, it is apparent that the best scores are achieved with weight normalization and feature normalization (bl).

Taking away weight normalization (bl-w) and subsequently feature normalization (bl-wf), the scores get worse. One exception is the recall of the low-shot classes which is maximal for minimal restrictions (bl-wf). We assume that feature and weight normalization have a regularizing effect that leads to a better generalization of the model. Regarding the low-shot classes, a model trained from scratch (bl) leads to a significantly higher precision and recall than an imprinted model (mi) and to a better or equal recall than a fine-tuned model (mi+ft).

For the base classes, all three conditions behave roughly similarly, although the precision of bl is slightly worse than of mi and mi+ft. This can be explained by the fact that during the representation learning phase of mi and mi+ft, the models learn features that are explicitly adapted to the base classes. Fine-tuning does not seem to destroy this advantage. Conversely, when training on all classes jointly (bl), the features are adapted to all classes equally (and not primarily to the base classes). This also explains the better scores of bl concerning the low-shot classes.

The negative slope of the recall of the base classes in the ZooScan dataset can be explained by the decreasing sampling rate of the base classes, where down to 1 % (for the largest classes) of the available examples are used in each training epoch. Therefore, the model may not be able to capture the full variability of the data.

Training a model from scratch takes roughly twice as long as finetuning a mean imprinted model.

Dataset maintenance

When collecting plankton images, it is important to constantly monitor the newly acquired data for previously overlooked classes and to update the models accordingly. When a dataset is extended by a novel class, more examples of this novel class have to be found among a large number of images. These examples can be found in new unlabeled data and may also hide in existing labeled data, as in some cases they might have been assigned to a more general class before the introduction of the novel class.

Figures 3 and4 show how precision and recall are linked to the class size for all models (bl, mi, and mi+ft). Although the imprinting of weights (mi) does not achieve the best scores, its huge advantage is the instant integration of novel data.

Correspondingly, the model may serve as a tool to quickly build up a collection of images in order to train a more powerful classifier later. As weight imprinting allows instant (i.e. in less than one second) re-training for every additional training example without much overhead (see section 4.2), it can be used during a process of iterative example mining: The model is initialized using one or few examples of a class. It is then used to classify unlabeled data and a human operator validates these classifications. The positive examples are used to improve the classifier. In this way, the suggestions will get increasingly better in every iteration.

For the suggestions to be useful, they have to contain positive examples at all, which manifests in a non-zero recall. In the ZooScan dataset, the recall is stable at an average of approx. 0.2 for even the smallest classes. In the UVP5 dataset, the recall is low for most classes. However, there are notable outliers with a recall of up to 1.0. Further research is needed to figure out what makes these outliers special.

As a result, weight imprinting is useful in the mining of additional examples for small and novel classes in both plankton image datasets. The actual implementation of the described procedure will be a task for the future.

The incoherent labeling of novel low-shot classes and existing base classes apparent in the evaluation underlines the usefulness of weight imprinting to keep a dataset consistently labeled when the set of classes evolves.

Conclusion

Deep learning models often fail when it comes to training classifiers with very little training data. This is the case for a considerable number of classes in both plankton image datasets. We therefore employed weight imprinting [START_REF] Qi | Low-shot learning with imprinted weights[END_REF], a lowshot learning method. When applying this method to plankton image datasets, it allows a model to incorporate underrepresented classes without overly impairing the performance on the base classes.

Weight imprinting resulted in an acceptable recall for the low-shot classes immediately without re-training the neural network. This permits the extension of a training set by examples of a novel class as soon as a single example of this class is observed.

Even when training from scratch, the underlying network architecture performs better than a model without normalization of features and weights in most cases. Apart from a reduced training time, we observed no significant advantage of an imprinted and fine-tuned model over a model trained from scratch.

In summary, the techniques in question, i.e. normalization of features and weights and weight imprinting, are able to advance the identification of plankton using machine learning with its unique challenges, i.e. a limited number of training examples, a severely skewed class size distribution and ever-emerging novel classes.

Fig. 1 :

 1 Fig. 1: Example images from both datasets.

Fig. 2 :

 2 Fig. 2: UVP5 dataset: Classes ordered by their size in the training set. The class sizes span five orders of magnitude.

Figures 3 and 4

 4 Figures 3 and 4 show how precision and recall of individual classes depend on the size of the respective class. The vertical line divides low-shot classes (left) and base classes (right). To show the general tendency, the graphs contain a LOWESS fit for each set of classes. The figures compare mi, mi+ft, and bl. They are best viewed in color.

Fig. 3 :

 3 Fig. 3: UVP5: Comparison of per-class precision and recall for mean imprinting (mi), fine-tuning (mi+ft), and training from scratch (bl).

Fig. 4 :

 4 Fig. 4: Comparison of per-class precision and recall for mean imprinting (mi), fine-tuning (mi+ft), and training from scratch (bl).

Fig. 5 :

 5 Fig. 5: Mean imprinting: Confusion matrices and failure cases (UVP5, validation set). Four of the entries with the most objects from a base class falsely predicted as a low-shot class are numbered. Representative images of the true base class (B) and the predicted low-shot class (LS), as well as two confused images (B falsely predicted as LS) are shown for each entry. 1: Copepoda vs. Cladocera, 2: fluffy dark vs. t003, 3: Collodaria solitary black vs. other dark sphere, 4: fluffy dark vs. t015. See the electronical version for a magnified view.

Fig. 6 :

 6 Fig. 6: Mean imprinting: Confusion matrices and failure cases (ZooScan, validation set). Three of the entries with the most objects from a base class falsely predicted as a low-shot class are numbered. Representative images of the true base class (B) and the predicted low-shot class (LS), as well as two confused images (B falsely predicted as LS) are shown for each entry. 1: Detritus vs. Ephyra, 2: Calanoida vs. Calocalanus pavo, 3: Detritus vs. scale. See the electronical version for a magnified view.

  consists of 1,433,282 wet net samples

	fluffy_dark (116,090) fluffy_light (57,199) Trichodesmium_tuff (45,485) Trichodesmium_puff (44,786) detritus_compact (41,202) Maxillopoda_Copepoda (15,790) Collodaria_solitaryblack (10,300) detritus_fiber (8,470) not-living_feces (6,416) temporary_t011 (5,968) Mollusca_veliger (5,072) Malacostraca_Eumalacostraca (4,464) detritus_light (3,246) fiber_fluffy (3,150) detritus_ovoid (2,762) Collodaria_solitaryglobule (2,762) Phaeosphaerida_Aulosphaeridae (2,558) artefact_badfocus (2,210) Retaria_Acantharea (2,100) temporary_t010 (1,517) temporary_t012 (1,491) Aulacanthidae_Aulacantha (1,208) artefact_bubble (987) Metazoa_Chaetognatha (981) artefact_turbid (944) Metazoa_Annelida (766) Phaeodaria_leg (704) Collodaria_solitarygrey (576) Collodaria_collonial (456) Collodaria_solitaryfuzzy (393) Terebellida_Poeobius (335) Cnidaria_Hydrozoa (223) temporary_t001 (213) Retaria_Foraminifera (196) Metazoa_Cnidaria (190) Oligostraca_Ostracoda (96) Vertebrata_Gnathostomata (95) temporary_t006 (77) Metazoa_Mollusca (60) Appendicularia_house (59) Hydrozoa_Cnidaria (57) Metazoa_Ctenophora (52) Arthropoda_Crustacea (48) Munididae_Pleuroncodes (43) Hydroidolina_Siphonophorae (43) Crustacea_leg (36) Tunicata_Appendicularia (24) Pyrosomatida_Pyrosoma (21) Trachylina_Narcomedusae (17) temporary_t004 (

Table 1 :

 1 Network architecture.

	Layer	#Parameters Output shape
	Input		128 × 128 × 3
	ResNet18	11 M	4 × 4 × 512
	Global Average Pooling		512
	Linear Layer (Embedding)	262 k	512
	Normalization		512
	Linear Layer ( ŵi)i∈C	512 • |C|	|C|
	Scale	1	|C|

one single training example x + belongs to c + , the weight vector is equal to its feature vector, i.e. w + = f (x + ). In the general case, if c + consists of multiple examples (|c + | ≥ 1), the weight vector is calculated as the arithmetic average of the image features, i.e. w + = 1 |c+| x+∈c+ f (x + ), and renormalized. The scalar product ŵT + ŷ then acts as a nearest mean classifier

[START_REF] Mensink | Distance-Based Image Classification: Generalizing to New Classes at Near-Zero Cost[END_REF]

using the cosine similarity. The underlying assumption is that the distribution of the examples is unimodal for each new class c + .

Table 2 :

 2 Macro precision and recall (UVP5).

		Base classes	Low-shot classes
		Macro precision Macro recall Macro precision Macro recall
	mi	0.569 ± 0.019 0.466 ± 0.051 0.030 ± 0.001 0.149 ± 0.023
	mi+ft 0.581 ± 0.001 0.644 ± 0.002 0.121 ± 0.035 0.296 ± 0.035
	ri	0.538 ± 0.024 0.675 ± 0.015	0
	ri+ft 0.593 ± 0.008 0.642 ± 0.005 0.163 ± 0.026 0.299 ± 0.022
	bl	0.539 ± 0.004 0.689 ± 0.003 0.366 ± 0.049 0.265 ± 0.022
	bl-w	0.489 ± 0.006 0.634 ± 0.015 0.212 ± 0.033 0.289 ± 0.014
	bl-wf 0.487 ± 0.017 0.555 ± 0.087 0.157 ± 0.010 0.302 ± 0.006

Table 3 :

 3 Macro precision and recall with standard deviation (ZooScan).

		Base classes	Low-shot classes
		Macro precision Macro recall Macro precision Macro recall
	mi	0.701 ± 0.001 0.716 ± 0.006 0.066 ± 0.008 0.205 ± 0.010
	mi+ft 0.724 ± 0.005 0.771 ± 0.002 0.174 ± 0.010 0.650 ± 0.010
	ri	0.663 ± 0.006 0.823 ± 0.003	0
	ri+ft 0.731 ± 0.005 0.775 ± 0.003 0.187 ± 0.003 0.664 ± 0.003
	bl	0.627 ± 0.008 0.812 ± 0.005 0.459 ± 0.019 0.614 ± 0.002
	bl-w	0.544 ± 0.010 0.793 ± 0.007 0.350 ± 0.025 0.675 ± 0.021
	bl-wf 0.502 ± 0.019 0.747 ± 0.028 0.242 ± 0.013 0.709 ± 0.012

Table 4

 4 lists the amount of time required to train a model to convergence in each condition, respectively.

Table 4 :

 4 Training times (s).

Acknowledgements

Rainer Kiko was supported by the Deutsche Forschungsgemeinschaft (DFG) as part of the Collaborative Research Centre (SFB) 754 "Climate-Biogeochemistry Interactions in the Tropical Ocean." Rainer Kiko, Reinhard Koch and Simon-Martin Schröder were furthermore supported by grants CP1650 and CP1733 of the Cluster of Excellence 80 "The Future Ocean." "The Future Ocean" is funded within the framework of the Excellence Initiative by the Deutsche Forschungsgemeinschaft (DFG) on behalf of the German federal and state governments. Jean-Olivier Irisson was supported by CNRS LEFE-MANU through project DL-PIC.


Fodil Benali
email: fbenali@adwanted.com

Damien Bodénès
email: dbodenes@adwanted.com

Cyril De Runz
email: cyril.derunz@univ-tours.fr

Nicolas Labroche
email: nicolas.labroche@univ-tours.fr

An Enhanced R-NSGA-II For Multiple Brands Advertising Campaign Allocation Problem

Keywords: Advertising, scheduling problems, evolutionary algorithms, many-objective optimization

This paper deals with the Campaign Allocation Problem of commercial Ads in TV breaks that we formalize as a multi-stakeholders multiobjective problem with highly competing objectives for different brands and numerous constraints. The problem is NP-hard with a high dimensional objective space and scalability issues in terms of the number of breaks. Moreover, the expected solution should be able to focus on a sub-part of the Pareto front according to decision maker's (DM) knowledge. To tackle these challenges, we propose to use R-NSGA-II, a Many-Objective Evolutionary Algorithm (MaOEA), combined with a novel gene encoding/decoding process. Experiments show that this approach obtains better results than usual MaOEA (NSGA-II, NSGA-III) according to industrial performance criteria, scales to large instances, and incorporates decision maker's preferences during the optimization process.

I. INTRODUCTION

The TV advertisements scheduling problem is defined as follows: given a set of advertisers' campaigns and a set of commercial breaks with air times (slots), the Campaign Allocation Problem (CAP) [START_REF] Mihiotis | A mathematical programming study of advertising allocation problem[END_REF] is to determine how campaigns' spots (brands messages) should be allocated to a subset of breaks in order to maximize the total revenue of the TV networks and evenness with respect to the advertisers' requirements and limited advertising inventory restrictions. It is an NP-hard combinatorial multiobjective optimization problem that involves conflicting objectives and complicated constraints [START_REF] Benoist | The TVbreak packing problem[END_REF]. One approach to solve this problem is to consider 2 sub-problems: [START_REF] Mihiotis | A mathematical programming study of advertising allocation problem[END_REF] determining the best assignment of concurrent brands' spots to available breaks, (2) inside each break, optimizing the sequence of spots, by taking into account the importance of the first and last slots of a break.

This paper deals with Problem (1) for which there already exists an extensive literature, noticeably in the operation research community such as [START_REF] Zhang | Mathematical models for the television advertising allocation problem[END_REF]. These approaches tend to formulate the problem based on a single objective with a large number of constraints and in the case of multi-campaigns, they treat the campaigns either sequentially or by considering an aggregated objective. Another approach [START_REF] Fleming | Optimal advertising campaign generation for multiple brands using MOGA[END_REF] considers the use of a multi-objective evolutionary algorithm by searching to optimize one objective per campaign (audience coverage) but it This work is funded by the ANRT CIFRE Program (2019/0877).

does not consider the other objectives to reach for a campaign nor the TV networks objectives for instance.

Contrary to previous works, in our context, we consider several stakeholders: advertisers, and TV networks, each with its own objectives. We also consider the size of the problem instance, all breaks from several months, that may not be appropriate for an exact resolution based on solvers. Therefore, there is a need for a multi-objective optimization algorithm that would provide the Decision Maker (DM), i.e. planner, with a set of Pareto-optimal solutions to decide which one should be used as the best solution. Evolutionary algorithms (EAs) [START_REF] Chand | Evolutionary many-objective optimization: A quick-start guide[END_REF] is well-suited to solve multi-objective problems [START_REF] Ghambari | An Enhanced NSGA-II for Multiobjective UAV Path Planning in Urban Environments[END_REF] thanks to their ability to provide a set of trade-off solutions in addition to their insensitivity to the geometrical features of the objective space. However, in our context, using an EA still raises challenges:

• Many-objective problem: as we consider a large number of objectives, most solutions become equivalent to each other. Therefore, finding solutions that are better compared to others according to the whole set of objectives is really challenging and requires adapted techniques to support the optimization. • Constrained problem: our EA should search for solutions in the decision space while respecting a set of predefined constraints so that it outputs a set of feasible non-dominated solutions. • Semi-supervised context: we propose to take advantage of any a priori preferences on the objectives. In this paper, we focus on a specific subset of the Pareto-optimal set according to a reference point that drives the convergence of the EA.

To address the aforementioned challenges, this paper: (i) proposes a formalization of this optimization problem to be solved by an evolutionary algorithm, (ii) introduces a preliminary encoding / decoding of solutions, represented as assignments of spots to breaks, that manages some of our constraints and can scale to large problem instances, and finally (iii) describes experiments that validate our formalization, the use of a reference based evolutionary algorithm, and the solution scalability.

II. PROBLEM DESCRIPTION AND FORMALIZATION

Scheduling TV advertisements involves two types of participants that are television networks (channels) and advertisers. After announcing TV shows programs, the TV networks finalize their rating forecasts and set the rate cards for the available advertising breaks. The rate cards contain for each break:

• The gross price for 1-second of message broadcasting.

• Whether it is a Prime break, i.e. an audience peak period.

• Expected gross rating point (GRP), which estimates the percentage of the audience during the commercial break. • The date and the timing of the break. Once rate cards are ready, the commercial break slots are exposed for selling. Then, the advertisers buy the slots in order to obtain the most efficient ad campaign. An advertiser's request corresponds to one brand's advertising campaign containing:

• The budget to invest for one brand's ad campaign.

• The cost per one GRP (CPP).

• Percentage of budget to invest in Prime breaks.

• The advertising spot duration (e.g., 15 seconds).

• The brand's competition code, which allows to avoid slot allocation of competitive brands in the same break. The advertising campaign optimization consists in obtaining a distribution of the available commercial break slots that maximize the invested budget allocation and achieves the best GRP for each brand while maximizing the revenue of the TV networks and maintaining the clients' loyalty. Moreover, for each campaign, there is a rate of Prime breaks to reach. This leads to a multi-stakeholders many-objective setting with competing objectives for different brands and various constraints.

The obtained distribution must take into account clients' constraints and TV networks' inventory restrictions. The major clients' requests constraints are the maximum budget allowed to spend, and the list of brands' commercials that are allowed to be exposed in the same break based on competitive exclusion rules. Besides, the sum of advertised spot duration cannot exceed the break length capacity.

In order to formally present the problem, the following notation is used. The mathematical problem can be formulate as follows:

min | m i=1 x ij * grp ij -GRP j |, j ∈ 1; n (1) min | m i=1 x ij * c ij * t j * f p (i) -P RIM E j |, j ∈ 1; n (2) max m i=1 n j=1 x ij * c ij * t j (3) max m i=1 n j=1 x ij * P RIORIT Y j (4)
Subject To:

m i=1 x ij * c ij * t j ≤ BU DGET j , j ∈ 1; n (5) n j=1 x ij * t j ≤ T i , i ∈ 1; m (6) m i=1 n j1=1 n j2=1 (x ij1 * x ij2 * f c (j 1 , j 2 )) = 0, j 1 = j 2 (7)
1) Client Side: Optimize for each client's brand r j , a set of objectives defined as follows:

• Objective function (1) consists in maximizing the GRP goal attainment, by minimizing the absolute difference between the achieved GRP and the aimed GRP (GRP j ). • Objective function (2) maximizes budget invested in prime breaks, by minimizing the absolute difference between the allocated prime breaks budget and the invested prime breaks budget (P RIM E j ). In the context of media planning, we have to maximize the budget allocation for the clients' requirement satisfaction, without exceeding the maximal budget allowed of each client. Hence, a budget constraint ( 5) is needed for each brand.

2) TV Networks Side: a global optimization is required:

• Objective function (3), maximizes the total revenue of the TV Networks. • Objective function (4), maximizes slots allocation based on client's potential and loyalty (P RIORIT Y j ). Finally, the solutions must respect the Commercial break length constraint [START_REF] Ghambari | An Enhanced NSGA-II for Multiobjective UAV Path Planning in Urban Environments[END_REF] and not allowing competing brands to be advertised in the same break [START_REF] Schaffer | Multiple objective optimization with vector evaluated genetic algorithms[END_REF].

III. MANY-OBJECTIVE EVOLUTIONARY ALGORITHMS

There are two main approaches to deal with Multi-Objective Problems (MOP) with EAs. First, approaches that consider each objective individually as in Vector Evaluated Genetic Algorithm (VEGA) [START_REF] Schaffer | Multiple objective optimization with vector evaluated genetic algorithms[END_REF], , or the well-known NSGA-III [START_REF] Deb | An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints[END_REF], However, they are sub-optimal as VEGA does not promote the survival of good trade-off solutions while NSGA-III relies on multiple parameters.

Second, evolutionary methods that deal with all objectives at the same time. Among them, the Non-dominated Sorting Genetic Algorithm (NSGA-II) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] is the most well-known. NSGA-II is an elitist algorithm that uses two types of fitness functions. Although NSGA-II has demonstrated to be one of the most competitive MOEAs [START_REF] Chand | Evolutionary many-objective optimization: A quick-start guide[END_REF] as it is simple, parameterless, and has a low computational complexity of O(M N 2 )) with elitist approach. However, it faces difficulties when dealing with a large objective number [START_REF] Ishibuchi | Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems[END_REF] due to dimensionality.

Nevertheless, recent studies [START_REF] Ishibuchi | Many-objective problems are not always difficult for pareto dominance-based evolutionary algorithms[END_REF] have shown that NSGA-II can be improved in many-objective contexts by focusing on a smaller subset of the Pareto optimal solutions close to a supplied set of reference points. For instance, in the Reference point-based NSGA-II algorithm (R-NSGA-II) [START_REF] Deb | Reference point based multiobjective optimization using evolutionary algorithms[END_REF], a set of DM's specified reference points can be used in a semisupervised way to guide the search in the objective space and to control the diversity of the focused Pareto-set.

IV. PROPOSED SOLUTION

A. Solution Encoding

The most challenging task in campaign allocation optimization for multiple brands requests is the effective constraints handling in a high dimensional search space context. As a consequence, our solution proposes an encoding phase encompassing the handling of hard and computational consuming constraints such as commercial break length constraint [START_REF] Ghambari | An Enhanced NSGA-II for Multiobjective UAV Path Planning in Urban Environments[END_REF] and brands competition constraint [START_REF] Schaffer | Multiple objective optimization with vector evaluated genetic algorithms[END_REF] before the search space exploration. For this reason, the encoding process is done in three steps:

1) Break allocation combinations generation: for each break b i , we generate all possible break allocation combinations. Then, we filter solutions that violate the constraints. 2) Break allocation combinations sorting based on the rate of completeness: for each break combination, we calculate its rate of completeness by dividing the sum of allocated spots in the combination by the break length.

After that, the combinations are sorted based on their rate of completeness. 3) Break allocation combinations encompassing into state based representations: for each break b i , we map the list of combinations to a list of states, where each state is defined as the index of the combination.

To include the previous encoding in R-NSGA-II algorithm, the following notation is used: This implies that advertisements for the break b i are coded in the gene gn i by a break state index z. There is a bijective mapping between the break-state and actual break spots.

G the chromosome
The major advantage of this encoding is the search space dimensionality reduction. In fact, the usual representation of chromosomes represents each solution vector by m * n variables, which becomes rapidly intractable: for m=100k breaks, and n=10 brands requests, solution vectors of 1 million variables are required which conducts us to the curse of dimensionality and search space sparsity. However, using our representation, we reduce the search space dimensionality to m variables only. Moreover, since our representation does not depend on the clients' requests, obtained solutions could be used as an initial population for future brand request handling.

B. Population Initialization

To generate the initial population, we propose to initialize the population with individuals of empty break states. The idea behind is that the genetic algorithm principle consists in building optimal solutions by assembling small building blocks. As building blocks are brought together, we get closer to this optimal solution. Consequently, initializing the population with empty breaks will allow the heuristic to progress incrementally towards the optimal solution.

C. Crossover and Mutation

We perform the mutation of the solution G = {gn 1 , gn 2 , . . . , gn m } on state-wise basis, with all genes having an equiprobability p m (p m = 1 m ). If the gene gn i is selected for the mutation, we suggest two options:

• The first option consists in randomly changing its value to one of the equiprobable states {0, 1, 2, . . . , st i }. • The second option considers a mutation mechanism which favors the states which fill or maximize the completeness of the breaks in the beginning and have small broadcasts at the end. One of the most challenging tasks in CAP is the TV networks' revenue management. In fact, optimizing revenue requires minimizing losses resulting from small residual durations in TV breaks due to partial reservation: if we assign a 25second spot to a 30-second TV break, the residual 5 seconds will be difficult to sell. As a consequence, our technique will allow to control the breaks allocations completeness rate and reduce the number of breaks partially reserved.

We use a single-point crossover consisting in picking randomly a crossover point after that the two parent solutions are swapped before and after the single point. The advantage of this step is to exploit the search space between the two given solutions.

D. Solution Decoding

To evaluate candidate solutions, chromosomes need to be decoded. For that, we use the sets of mapping from the encoding step. Since the sets of the possible states W i are computed prior to the EA starts, having a set of such mappings for each break enables fast coding and decoding of the solutions during the algorithm run.

E. Evaluation and Selection

Once the population of solutions is decoded, for each nonevaluated-yet solution, we evaluate:

• For each brand request, the GRP attainment objective (1), and the prime budget objective (2). • The revenue optimization objective (3), and the priority objective (4) for the TV networks.

After the solution evaluation, the selection process is done in 4 steps:

• Infeasible solutions, i.e., solutions that violate the budget constraint [START_REF] Chand | Evolutionary many-objective optimization: A quick-start guide[END_REF], are removed from the population. • A non-dominated sorting is performed to classify the population into different levels of non-domination. • Solutions from the best non-domination levels are chosen front-wise. • For solutions from the last front which cannot be entirely chosen to maintain the population size of the next population, the preference based distance [START_REF] Deb | Reference point based multiobjective optimization using evolutionary algorithms[END_REF] is used to select a subset of diverse solutions based on the reference point selected by the DM.

V. COMPUTATIONAL EXPERIMENTS

In this section, we report the experiments that were conducted to show the applicability and validity of the proposed approach and mathematical modeling to solve the campaign allocation problem.

In order to evaluate our approach, we answer the following research questions:

1) How does our model R-NSGA-II deal with many objectives, and how beneficial is the reference point in our context? 2) To which extent the proposed encoding of solutions is efficient for handling constraints in high dimensional search space?

A. Experimentation Design

We generate 2 synthetic datasets based on confidential French advertising data and using a the synthetic data generation framework based on copula called, M T Copula [START_REF] Benali | MTCopula: Synthetic Complex Data Generation Using Copula[END_REF]. The first dataset contains 1000 breaks (m = 1000, i.e., low DSS) and the second dataset contains 10000 breaks (m = 10000, i.e., high DSS). The experiment parameter configuration is set as follows: the population size is set to 40, the time budget (stopping criterion) is set to 180 sec. Together, these two parameters imply a fair and objective evaluation of the algorithms. EA operators parameters are set to standard configurations: the mutation probability p m = 1/m and the crossover probability p c = 1. To assess the performance, we evaluate the objective functions using 6 randomly generated client requests. Finally, due to the stochastic nature of evolutionary algorithms, each experiment has been repeated 20 times. As the obtained results are comparable, we only report one result for each experiment for the sake of readability.

B. R-NSGA-II Vs NSGA-II and NSGA-III

To validate the choice of R-NSGA-II algorithm in our approach, we study the performance of the proposed solution pipeline using three algorithms R-NSGA-II, NSGA-II, and NSGA-III. Each time, we evaluate the absolute percentage error of the GRP attainment (1) and the Prime budget achieved (2) for the 6 brand request competing over a pool of 1000 commercial breaks (m = 1000). Noticeably, reference directions in NSGA-III have been generated using Das-Dennis method. The reference point in R-NSGA-II is defined by the optimal value for each objective function.

Fig. 1 presents the evaluation of clients' criterion optimization based on the percentage absolute error. We observe clearly that clients' requirements (GRP and Prime budget) are better respected using the R-NSGA-II with a small variation error that does not exceed 0.05 for the GRP attainment and 0.14 for the P rime budget, when they are large GRP and Prime errors for both NSGA-II and NSGA-III with a variation that exceeds 50% in the case of NSGA-III. This is because NSGA-II behaves like a random search in high DSS, and NSGA-III requires many parameters setting (population size and reference directions) to be set cautiously on a case-by-case basis.

C. Interest Of Encoding Process

In order to show the utility of the proposed encoding process for handling hard constraints such as break length constraints (6) and competing constraint [START_REF] Schaffer | Multiple objective optimization with vector evaluated genetic algorithms[END_REF], we evaluate our approach by activating and deactivating the process of encoding. Each time, the absolute error of the clients objective functions (1)-( 2) is used to assess efficiency of this process. We have to mention here that the deactivation of the process implies checking the constraints during the optimization process and high DSS to represent solutions (n*m). Fig. 2 shows the impact of activating and deactivating the process of encoding on the quality of the optimization. Deactivating the process of encoding decreases the overall performance of the approach because, due to the high number of constraints, a lot of otherwise rejected solutions are kept, and as evolutionary heuristics build solutions incrementally based on last identified feasible solutions. As a consequence, we notice a variation of errors between 0.60 and 1.0 for both of the GRP and Prime budget for all client requests. This shows that this encoding is efficient to simultaneously handle efficiently multiple constraints.

VI. CONCLUSION

In this paper, we proposed a new optimization approach for concurrent brand spots assignment to available breaks in TV networks. This industrial goal led us to first propose a multistakeholders many-objective formalization of the problem with numerous constraints and highly competing brand objectives. In order to tackle this latter, we proposed an enhanced R-NSGA-II which incorporates DM's preferences and uses custom operators with an efficient problem encoding. Several experiments validate the interest of the proposal.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Absolute percentage error evaluation for the GRP and Prime Budget of 6 requests using R-NSGA-II, NSGA-II, and NSGA-III.

  (candidate solution) of the algorithm G = {gn 1 , gn 2 , . . . , gn m } gn i the gene that corresponds to the commercial break b i , gn i ∈ {0, 1, 2, . . . , st i -1} st i the number of possible states for the gene gn i W i the set of possible states for the gene gn i , |W i | =

		s i , W i = {w z i |z = 0, 1, . . . , st i -1}
	z	the break state index
	w z i u z	the z th state of the gene gn i , w z i {u z i1 , . . . , u z ij , . . . , u z in }	=

ij

= r j if the state z of the gene gn i contain the brand r j , otherwise 0


Angélique Villière

Catherine Fillonneau

Carole Prost

Fabrice Guillet

Sketchoscent

SketchOscent: towards a knowledge-based model and interactive visualization of the odour space

come   L'archive ouverte pluridisciplinaire

SketchOscent :

Towards a knowledge-based model and interactive visualization of the odour space 1 ONIRIS -College of Veterinary Medicine and Food Science, GEPEA UMR CNRS 6144 MAPS2, Flavour group -Nantes, France The representation of an odour space is a challenging issue for scientists and professionals working in odour-related activities. Such an odour representation has to tackle the issues of a large amount of odors, dealing with subjectivity and uncertainty, a meaningful categorization for a knowledge map, and a readable and interactive visualization. Many representations of the odorant space have been proposed like : Field of odors [START_REF] Jaubert | The Field of Odors: Toward a Universal Language for Odor Relationships[END_REF], ScenTree [2], SensoryMap [3], Flavor network [START_REF] Ahn | Flavor network and the principles of food pairing[END_REF]. These initiatives turn the odorant space into easy-to-digest representations but the odour set is often restricted, and does not reflect the overlapping of categories. Thus, the related visualizations, face with difficulties to represent such odour relationships.

This work based on knowledge graphs from semantic web aims to propose a readable, interactive and publicly available representation of the aroma space, relying on a large set of odors and on overlapping categories, dedicated to olfactory and sensory practices.

  Scents Company Information System -Flavornet https://oniris-polytech.univ-nantes.io/sketchoscent Semantic web and data mining technologies -Public odour model in RDF language -Graph drawing with Gephi software

  2 Polytech Nantes, graduate school of engineering of the University of Nantes, LS2N CNRS 6241, Nantes, France Angélique VILLIÈRE 1 , Catherine FILLONNEAU 1 , Carole PROST 1, Fabrice GUILLET 2

angelique.villiere@oniris-nantes.fr