Osman Akin

Cherti Kazakçi

Balázs Mehdi

Kégl

Akın Kazakc
email: akin.kazakci@mines-paristech.fr

Mehdi Cherti
email: mehdi.cherti@gmail.com

Balázs Kégl
email: balazs.kegl@gmail.com

Digits that are not: Generating new types through deep neural nets

published or not. The documents may come

Introduction

It is a widely accepted view in creativity research that creativity is a process by which novel and valuable combinations of ideas are produced [START_REF] Runco | The standard definition of creativity[END_REF]. This view bears a tension, the essence of which can be expressed by the following question: how to determine the value of novelty? If a new object is substantially different of the previous objects in its category, it might be hard to determine its value. On the contrary, if the value of an object can be readily determined, it might be the case that the object is not genuinely new. Indeed, there exist experimental results positing that novelty is a better predictor of creativity than the value [START_REF] Diedrich | Are creative ideas novel and useful? Psychology of Aesthetics[END_REF] and that the brain processes novelty in a particular way [START_REF] Beaucousin | Erp evidence of a meaningfulness impact on visual global/local processing: when meaning captures attention[END_REF], suggesting that the relationship is far from trivial.

In art, the difficulty in determining the value of an object is omnipresent. An emblematic example is Le Grand Verre by Marcel Duchamp. The artist worked on this singular project from 1915 to 1923 and produced a groundbreaking yet enigmatic piece of art, which the critiques still continue to interpret in various ways. In 1934, Duchamp built La boîte verte, a green box containing preparatory material (notes, drawings, photographs) he produced for Le Grand Verre. Considered as a piece of art in its own right, the box was intended to assist and to explain Le Grand Verre, as would an exhibition catalog [START_REF] Breton | Marcel duchamp : The bride stripped bare by her own bachelors[END_REF].

In product design, there exist less enigmatic but still emblematic cases, where the value of an innovation could not be easily determined. For instance, the first smartphone received significant criticism regarding its usability (e.g., no stylus was provided), and it was deemed to be less evolved than its counterparts. Beyond such problems related to the reception of novelty, the sheer difficulty in discovering new value has led companies to seek alternative approaches, such as input from lead users (Von Hippel 1986).

The difficulty in determining the value of novelty has particular implications from a computational perspective. How would a creative agent drive his search process towards novelty if its evaluation function has been predetermined? In practical implementations, we can find various manifestations of such fixed evaluation functions such as fitness functions or quantitative aesthetics criteria. These implementations fixate the kind of value the system can seek, once and for all in the beginning of the process. The creative outcome, if any, comes from an output whose perception was unexpected or unpredictable.

Theoretically, it may be argued that this can be solved by allowing the creative agent to change its own evaluation rules (Wiggins 2006;Jennings 2010). This implies that the system would be able to develop a preference for unknown and novel types of objects (Kazakc ¸ı 2014). In practice, this is implemented by interactive systems that use external feedback (e.g., the preferences of an expert) to guide the search process. Such systems explore user preferences about novelty rather than building their own value system. This is a shortcoming from the point of view of creativity (Kazakc ¸ı 2014).

An alternative approach might be to force the system to systematically explore unknown objects [START_REF] Hatchuel | Ck design theory: an advanced formulation[END_REF]. This requires the system to function in a differential mode, where there is a need to define a reference of known objects. In other words, new kinds of values might be searched by going-out-of-the-box mechanisms which require the system to develop knowledge about a referential set of objects. In the absence of knowledge about such a set, creativity is reduced either to a combinatorial search or to a rule-based generative inference, both of which explore boundaries confined by the creator of the system and not the system itself. When such knowledge exists, the system can explore new types of objects by tapping into the blind spots of the knowledge model [START_REF] Kazakci | Simulation of design reasoning based on ck theory: a model and an example application[END_REF].

In this paper, we use a deep generative neural network In addition, the goal of the little work on generative deep nets is to generate objects of known types, and the quality of the generator is judged by the visual or quantified similarity with existing objects (e.g., an approximate likelihood) (Theis, Oord, and Bethge 2015). In contrast, we use deep nets to explore their generative capacity beyond known types by generating unseen combinations of extracted features, the results of which are symbols that are mostly unrecognizable but seemingly respecting some implicit semantic rules of compositionality (Figure 1). What we mean by features is a key concept of the paper: they are not decided by the (human) designer, rather learned by an autoassociative codingdecoding process.

The novelty of our approach is two-fold. With respect to computational creativity models, our model aims at explicitly generating new types. We provide an experimental framework for studying how a machine can develop its own value system for new types of objects. With respect to statistical sample-based generative models, rather than a technical contribution, we are introducing a new objective: generate objects that are, in a deep sense, similar to objects in of the domain, but which use learned features of these objects to generate new objects which do not have the same type. In our case, we attempt to generate images that could be digits (e.g., in another imaginary culture), but which are not.

The first section, Generative models for computational creativity, describes our positioning with respect to some of the fundamental notions in creativity research in previous works. The section Learning to generate presents details about data-driven generative models and deep neural nets relevant to our implementation. The section Generating from the learned model describes our approach for exploring novelty through generation of new types, presents examples and comments. The section Discussion and perspectives discusses links with related research and points to further research avenues. Finally, section Summary concludes.

Generative models for computational creativity

The purpose of a generative model

In the computational creativity literature, exploration of novelty has often been considered in connection with art [START_REF] Boden | What is generative art?[END_REF][START_REF] Mccormack | Ten questions concerning generative computer art[END_REF]. Despite various debates and nuances on terminology, such work has generally been categorized under the term generative art (or generative models). As defined by [START_REF] Boden | What is generative art?[END_REF]), a generative model is essentially a rulebased system, albeit one whose output is not known in advance, for instance, due to non-determinism or to many degrees of freedom in the parameters of the systems (see also (Galanter 2012)). A large variety of such systems has been built, starting as early as the 90s [START_REF] Todd | Mutator: a subjective human interface for evolution of computer sculptures[END_REF]Sims 1991), based on even earlier foundations (Nees 1969;Edmonds 1969). The definition, the complexity and the capabilities offered by such models evolved consistently. To date, several such models, including L-systems, cellular automata, or artificial life simulations, have been used in various contexts for the generation of new objects (i.e., drawings, sounds, or 3D printings) by machine. Such systems achieve an output perceived as creative by their users by opportunistically exploiting existing formal approaches that have been invented in other disciplines and for other purposes. Within this spirit, computational creativity research has produced a myriad of successful applications on highly complex objects, involving visual and acoustic information content.

In contrast, this work considers much simpler objects since we are interested, above all, in the clarification of notions such as novelty, value, or type, and in linking such notions with the solid foundations of statistics and machine learning. These notions underlie foundational debates on creativity research. Thus, rather than producing objects that might be considered as artistic by a given audience, our purpose is to better define and explicate a minimalist set of notions and principles that would hopefully lead to a better understanding of creativity and enable further experimental studies.

The knowledge of a generative system

The definition of a generative model as a rule-based system [START_REF] Boden | What is generative art?[END_REF]) induces a particular relationship with knowledge. It is fair to state that such formalized rules are archetypes of consolidated knowledge. If such rules are hard-coded into the creative agent by the system designer, the system becomes an inference engine rather than a creativity engine. By their very nature, rules embed knowledge about a domain and its associated value system that comes from the system designer instead of being discovered by the system itself.

Allowing the system to learn its own rule system by examining a set of objects in a given domain resolves part of this problem: the value system becomes dependent on the learning algorithm (instead of the system designer). In our system, we use a learning mechanism where the creative agent is forced to learn to disassemble and reconstruct the examples it has seen. This ensures that the utility of the features and the transformations embedded within the rules learned by the system are directly linked to a capacity to construct objects. As we shall see, the particular deep neural net architecture we are using is not only able to reconstruct known objects: it can also build new and valuable objects using their hierarchically organized set of induced transformations.

Knowledge-driven exploration of value

Today, more often than not, generative models of computational creativity involve some form of a biological metaphor, the quintessence of which is evolutionary computation (Mc-Cormack 2013). Contrary to human artists who are capable of exploring both novelty and the value of novelty, such computational models often consider the generation of novelty for a value function that is independent of the search process. Either they operate based on a fixed set of evaluation criteria or they defer evaluation to outside feedback. For the former case, a typical example would be a traditional fitness function. For the later case, a typical example would be an interactive genetic algorithm (Takagi 2001) where the information about value is provided by an oracle (e.g., a human expert). In both cases, the system becomes a construction machine where the generation of value is handled by some external mechanism and not by the system itself. This can be considered as a fundamental barrier for computational creativity research (Kazakc ¸ı 2014) that we shall call fitness function barrier. (Parikka 2008) summarizes the stagnation that this approach causes for the study of art through computers: ". . . if one looks at several of the art pieces made with genetic algorithms, one gets quickly a feeling of not 'nature at work' but a Designer that after a while starts to repeat himself. There seems to be a teleology anyhow incorporated into the supposed forces of nature expressed in genetic algorithms practice 'a vague feeling of disappointment surrounds evolutionary art'".

The teleology in question is a direct consequence of fitness function barrier and the hard-coded rules. In our system, we avoid both issues by using a simple mechanism that enables the system to explore novel objects with novel values. Given a set of referential objects D = {x 1 , .., x n } whose types T = {t 1 , ..., t k } are known (or can be determined by a statistical procedure such as clustering), the system is built in such a way that it generates objects D = {x 1 , . . . , x m } with types T = {t 1 , . . . , t } such that D ⊂ D and T ⊂ T . In other words, the system builds a set of new objects, some of which have new types. While the current system does not develop a preference function over the novelty it generates, the current setup provides the necessary elements to develop and experiment with what might be a value function for the unknown types. At any rate, the generation of unknown types of objects is an essential first step for a creative system to develop its own evaluation function for novelty and to become a designer itself.

Learning to generate

Data-driven generative models

In contrast to computational creativity research that aims to generate new object descriptions, disciplines such as statistics and machine learning strive to build solid foundations and formal methods for modeling a given set of object descriptions (i.e., data). These disciplines do not consider the generation of data as a scientific question: the data generating process is considered fixed (given) but unknown. Nevertheless, these fields have developed powerful theoretical and practical formal tools that are useful to scientifically and systematically study what it means to generate novelty.

In fact, generative models have a long and rich history in these fields. The goal of generative models in statistics and machine learning is to sample from a fixed but unknown probability distribution p(x). It is usually assumed that the algorithm is given a sample D = {x 1 , . . . , x n }, generated independently (by nature or by a simulator) from p(x). There may be two goals. In classical density estimation the goal is to estimate p in order to evaluate it later on any new object x. Typical uses of the learned density are classification (where we learn the densities p 1 and p 2 from samples D 1 and D 2 of two types of objects, then compare p 1 (x) and p 2 (x) to decide the type of x), or novelty (or outlier) detection (where the goal is to detect objects from a stream which do not look like objects in D by thresholding p(x)).

The second goal of statistical generative models is to sample objects from the generative distribution p. If p is known, this is just random number generation. If p is unknown, one can go through a first density estimation step to estimate p, then sample from p. The problem is that when x is highdimensional (e.g., text, images, music, video), density estimation is a hard problem (much harder than, e.g., classification). A recent line of research (Hinton, Osindero, and Teh 2006;[START_REF] Salakhutdinov | Deep boltzmann machines[END_REF] attempts to generate from p without estimating it, going directly from D to novel examples. In this setup, a formal generative model g is a function that takes, as input, a random seed r, and generates an object x = g(r). The learning (a.k.a, training or building) process is a (computational) function A that takes, as input, a data set D, and outputs the generative model g = A(D).

The fundamental problem of this latter approach is very similar to the main question we raised about computational creativity: what is the value function? When the goal is den-sity estimation, the value of p is formally x∈D log p(x), the so-called log-likelihood, where D is a second data set, independent from D which we used to build (or, in machine learning terminology, to train) p. When p is unknown, evaluating the quality of a generated object x = g(r) or the quality of a sample D = {g(r 1 ), . . . , g(r n )} is an unsolved research question in machine learning as well.

There are a few attempts to formalize a quantitative goal [START_REF] Goodfellow | Generative adversarial nets[END_REF]), but most of the time the sample D is evaluated visually (when x is an image) or by listening to the generated piece of music. And this is tricky: it is trivial to generate exact objects from the training set D (by random sampling), so the goal is to generate samples that are not in D, but which look like coming from the type of objects in D. By contrast, our goal is to generate images that look like digits but which do not come from digit types present in D.

Deep neural networks

In the machine learning literature, the introduction of deep neural networks (DNNs) is considered a major breakthrough (LeCun, Bengio, and Hinton 2015). The fundamental idea of a DNN is to use of several hidden layers. Subsequent layers process the output of previous layers to sequentially transform the initial representation of objects. The goal is to build a specific representation useful for some given task (i.e., classification). Multi-layered learning has dramatically improved the state of the art in many high-impact application domains, such as speech recognition, visual object recognition, and natural language processing.

Another useful attribute of deep neural nets is that they can learn a hierarchy of representations, associated to layers of the net. Indeed, a neural net with L layers can be formalized as a sequence of coders (c 1 , . . . , c L ). The representation in the first layer is y 1 = c 1 (x), and for subsequent layers 1 < ≤ L it is y = c (y -1 ). The role of the output layer is then to map the top representation y L onto a final target y = d(y L ), for example, in the case of classification, onto a finite set of object types. In what follows, we will denote the function that the full net implements by f . With this notation, y = d(y L ) = d c L (y L-1 ) = . . . = f (x).

The formal training setup is the following. We are given a training set D = {x 1 , . . . , x n }, a set of learning targets (e.g., object types) {y 1 , . . . , y n }, and a score function s(y, y) representing the error (negative value) of the prediction y with respect to the real target y. The setup is called supervised because both the targets of the network y i and the value of its output s is given by the designer. We train the network f w , where w is the vector of all the parameters of the net, by classical stochastic gradient descent (modulo technical details): we cycle through the training set, reconstruct y i = f w (x i ), compute the gradient δ i = ∂s(y i , y i )/∂w, and move the weights w by a small step in the direction of -δ i .

Autoassociative neural nets (autoencoders)

Formally, an autoencoder is a supervised neural network whose goal is to predict the input x itself. Such neural networks are composed of an encoder part and a decoder part. In a sense, an autoencoder learns to disassemble then to reassemble the object x. Our approach is based on a particular the technique described in [START_REF] Bengio | Generalized denoising auto-encoders as generative models[END_REF]. We first learn about the input space by training an autoassociative neural net (a.k.a. autoencoder) f using objects D = {x 1 , . . . , x n }, then apply a technique that designs a generative function (simulator) g based on the trained net f . Autoencoders are convenient because they are designed to learn a representation y = c(x) of the object x and a decoder x = d(y) such that x is close to x in some formal sense, and y is concise or simple. In the classical information theoretical paradigm, both criteria can be formalized: we want the code length of y (the number of bits needed to store y) to be small while keeping the distortion (e.g., the Euclidean distance) between x and x also small. In (neural) representation learning, the goals are somewhat softer. The distortion measure is usually the same as in information theory, but simplicity of y is often formalized implicitly by using various regularization operators. The double goal of these operators is to prevent the algorithm to learn the identity function for the coder c, and to learn a y that uses elements ("code snippets") that agree with our intuition of what object components are.

The decoder d takes the top representation y L and reconstructs x = d(y L ). The goal is to minimize a score s(x, x ), also called distortion, that measures how close the input image x is to the reconstructed image x . Throughout this paper, we will use the Euclidean squared distance in the pixel space s(x, x ) = x -x 2 2 . We are using a particular variant of autoencoders, called sparse convolutional autoencoders [START_REF] Makhzani | Winner-take-all autoencoders[END_REF] with L = 3 coding layers and a single decoding layer. Convolutional layers are neural net building blocks designed specifically for images: they are essentially small (e.g., 5 × 5) filters that are repeated on the full image (in other words, they share the same set of weights, representing the filter). The sparse regularizer penalizes dense activations, which results in a sparse representation: at any given layer, for any given image x, only a small number of units ("object parts", elements of y ) are turned on. This results in an interesting structure: lower layer representations are composed of small edgelets (detected by Gabor-filter like coders), followed by small object parts "assembled" from the low-level features. The convolutional filters themselves are object parts that were extracted from the objects of the training set. The sparsity penalty and the relatively small number of filters force the net to extract features that are general across the population of training objects.

Generating from the learned model

In this section we present and comment some experimental results. First, we provide some illustrations providing an insight regarding the usefulness of the representations extracted by a deep net for searching for novelty. Then, we present the method we use to generate novel image objects, based on the formal approach described in the section Learning to generate.

Searching for new types: with and without knowledge

We argued in previous sections that combinatorial search over the objects has disadvantages over a search process driven by a knowledge over the same set of objects obtained by the system itself. When the learning is implemented through a deep neural net, this knowledge is encoded in the form of multiple levels of representations and transformations from layer to layer. To demonstrate the effect of knowledge over these search procedures, instead of searching in the original object space of x, we have applied simple perturbation operations on the representation space y.

Figure 3 illustrates the results of these perturbations. In the original representation space, crossover and mutation operators create noisy artifacts, and the population quickly becomes unrecognizable, which, unless the sought effect is precisely the noise, is not likely to produce novel objects (let alone types) unless a fitness function that drives the search is given (which is what we are trying to avoid). In comparison, the same operators applied to the code y produced by the deep nets produce less noisy and seemingly more coherent forms. In fact, some novel symbols that go beyond the known digits seem to have already emerged and can be consolidated by further iteration through the model. Overall, combinatorial search in the representation space provided by the deep net seems more likely to generate meaningful combinations in the absence of a given evaluation function, thus, making it more suitable for knowledge-driven creativity.

Method for generating new objects from a learned model

To generate new objects in a knowledge-driven fashion, we first train a generative autoencoder to extract features that are useful for constructing such objects. To train the autoencoder f , we use the MNIST (Lecun and Cortes 2012) data set (Figure 4) containing gray-scale hand-written digits. It contains 70 000 images of size 28 × 28. Once the model learned to construct objects it has seen, it has also learned useful transformations that can be queried to generate new objects.

Autoassociative networks exist since the 80s (Rumelhart, Hinton, and Williams 1986;[START_REF] Baldi | Neural networks and principal component analysis: Learning from examples without local minima[END_REF]Kramer 1991), nevertheless, it was discovered only recently that they can be used to generate new objects [START_REF] Bengio | Generalized denoising auto-encoders as generative models[END_REF][START_REF] Kamyshanska | On autoencoder scoring[END_REF]. The procedure is the following. We start from a random image x 0 = r, and reconstruct it x 1 = f (x) using the trained network f . Then we plug the reconstructed image back to the net and repeat x k = f (x k-1 ) until convergence. Figure 2 illustrates the process. At each step, the net is forced to generate an image which is easier to reconstruct than its input. The random seed r initializes the process. From the first iteration on, we can see familiar object parts and compositions rules, but the actual object is new. The net converges to a fixed point (an image that can be reconstructed without an error).

It can be observed that, although this kind of generative procedure generates new objects, the first generation of images obtained by random input (second column of Figure 2) look noisy. This can be interpreted as the model has created a novelty, but has not excelled yet at constructing it adequately. However, feeding this representation back to the model and generating a new version improves the quality. Repeating this step multiple times enables the model to converge effectively towards fixed points of the model, that are more precise (i.e., visually). Their novelty, in terms of typicallity, can be checked using clustering methods and visualised as in Figure 5.

Generating new types

When the generative approach is repeated starting from multiple random images {r 1 , . . . , r n }, the network generates different objects {x 1 , . . . , x n }. When projecting these objects (with the original MNIST images) into a twodimensional space using stochastic neighbor embedding (van der Maaten and Hinton 2008), the space is not filled uniformly: it has dense clusters, meaning that structurally similar objects tend to regroup; see Figure 5. We recover these clusters quantitatively using k-means clustering in the feature space {y 1 , . . . , y n }. Figure 6 contains excerpts from these clusters. They are composed of similar symbols that form a coherent set of objects, which can be perceived as new types.

Discussion and perspectives

It is possible to compare our work with several other published results. To start with, the generation of novelty through the use of neural nets is an old idea (Todd 1992;Todd 1989;Thaler 1998). There are two main differences between our approach and theirs. First, our emphasis is on studying how an artificial agent can generate novelty that Figure 3: The effect of perturbations applied to object representations. On the left, the effect of crossover and mutation on the original representations of MNIST. On the right, the same operators applied to the representations learned by the deep generative net. Visually, this latter category seem less affected by perturbations, and thus is likely to provide a better search space for novelty. does not fit into learned categories, rather than creating objects with artistic value. This experimental setup is intended to provide means for studying how a creative agent can build an evaluation function for new types of objects. Second, we explicitly aim at establishing a bidirectional link between generative models for computational creativity and generative models within statistics and machine learning. Beyond the use of techniques and tools developed in these disciplines, we wish to raise research questions about creative reasoning that would also be interesting in statistics and machine learning.

In fact, some recent work has already started exploring the creative potential of deep neural networks. For instance, [START_REF] Mordvintsev | Inceptionism: Going deeper into neural networks[END_REF] uses a deep net to project the input that would correspond to a maximal activation of a layer back onto an image in an iterative fashion. The images are perceived as dreamy objects that are both visually confusing and appealing. Another work (Gatys, Ecker, and Bethge 2015) uses correlations of activations in multiple layers of a deep net to extract style information from one picture and to transpose it to another. Finally, (Nguyen, Yosinski, and Clune 2015) uses a trained net as a fitness function for an evolutionary approach (see also (Machado, Romero, and Manaris 2008) for a similar application with shallow nets). These successful approaches demonstrate the potential of deep nets as an instrument for creativity research and for generating effects that can be deemed as surprising, even creative. The present approach and the points the paper puts forward are significantly different. Compared to the architectures used in these studies, ours is the only one that uses a generative deep autoassociative net. The reason for this choice is twofold. First, we aim at using and understanding the generative capacity of deep nets. Second, we are interested in the deconstruction and reconstruction our architecture provides since our aim is to build objects through the net (not to create an effect that modifies existing objects). Once again, thinking about and experimenting with these foundational aspects of generative deep nets provide a medium through which notions of creativity research can be clarified through statistical notions. This is not among the declared objectives of previous works.

The novelty-seeking behavior of our system can also be compared to the recent novelty-driven search approaches in the evolutionary computing literature [START_REF] Mouret | Encouraging behavioral diversity in evolutionary robotics: An empirical study[END_REF][START_REF] Lehman | Novelty search and the problem with objectives[END_REF]. These approaches, like ours, seek to avoid objective functions and push the system to systematically generate novelty in terms of system behavior (e.g., novelty in the output). Our system is akin to such methods in spirit with one main difference: we believe that knowledge plays a fundamental role in creative endeavor and the decision of the system regarding the search for novelty should come from its own knowledge model. Note that this does not exclude a more general system where several systems such as ours can compete to differentiate themselves from the observed behavior of others, effectively creating a community of designers.

Our system provides a step towards an experimental study of how an artificial agent can drive its search based on knowledge. Furthermore, it can effectively create new types of objects preserving abstract and semantic properties of a domain. However, we have not fully addressed the question of how such an agent can build its own value function about novelty. Nevertheless, the system enables numerous ways to experiment with various possibilities. An obvious next step would be to hook our system to an external environment, where the system can receive feedback about value [START_REF] Clune | Evolving three-dimensional objects with a generative encoding inspired by developmental biology[END_REF][START_REF] Secretan | Picbreeder: evolving pictures collaboratively online[END_REF]. To avoid the fitness function barrier, this should be done in such a way that the system can build its own value system rather than only learning the ones in its environment.

Summary

We provided an experimental setup based on a set of principles that we have described. The pinnacle of these principles is that artificial creativity can be driven by knowledge that a machine extracts itself from a set of objects defining a domain. Given such knowledge, a creative agent can explore new types of objects and build its own value function about novelty. This principle is in contrast with existing systems where the system designer or audience imposes a value function to the system, for example, by some fitness function.

We argued that when an artificial creative agent extracts its own domain knowledge in the form of features that are useful to reconstruct the objects of the domain, it becomes able to explore novelties beyond the scope of what it has seen by exploring systematically unknown types. We have demonstrated the idea by using a deep generative network trained on a set of digits. We proposed a compositional sampling approach that yielded a number of new types of digits.

While our setup provides a basis for further exploring how an agent can develop its own value function, it is also a bridge with the powerful theories and techniques developed within the statistics and machine learning communities. A colossal amount of work has already been published on deep neural networks with significant breakthroughs in many domains. Deep learning will be all the more valuable if it offers an evolution of the machine learning paradigm towards machine creativity.

Figure 1 :

 1 Figure 1: Digits that are not. Symbols generated using a deep neural net trained on a sample of hand-written digits from 0 to 9. to demonstrate knowledge-driven creativity. Deep nets are powerful tools that have been praised for their capacity of producing useful and hierarchically organized representations from data. While the utility of such representations have been extensively demonstrated in the context of recognition (i.e., classification) far less work exists on exploring the generative capacity of such tools.In addition, the goal of the little work on generative deep nets is to generate objects of known types, and the quality of the generator is judged by the visual or quantified similarity with existing objects (e.g., an approximate likelihood)(Theis, Oord, and Bethge 2015). In contrast, we use deep nets to explore their generative capacity beyond known types by generating unseen combinations of extracted features, the results of which are symbols that are mostly unrecognizable but seemingly respecting some implicit semantic rules of compositionality (Figure1). What we mean by features is a key concept of the paper: they are not decided by the (human) designer, rather learned by an autoassociative codingdecoding process.The novelty of our approach is two-fold. With respect to computational creativity models, our model aims at explicitly generating new types. We provide an experimental framework for studying how a machine can develop its own value system for new types of objects. With respect to statistical sample-based generative models, rather than a technical contribution, we are introducing a new objective: generate objects that are, in a deep sense, similar to objects in of the domain, but which use learned features of these objects to generate new objects which do not have the same type. In our case, we attempt to generate images that could be digits (e.g., in another imaginary culture), but which are not.

Figure 2 :

 2 Figure 2: Four examples illustrating the iterative generative process. At each iteration, the net pushes the input image closer to what it can "understand" (reconstruct easily), converging to a fixed point (an image that can be reconstructed without an error).

Figure 4 :

 4 Figure 4: A subsample of MNIST, the data set we use to train the autoencoder f .

Figure 5 :

 5 Figure 5: A distance-preserving projection of digits to a twodimensional space. Colored clusters are original MNIST types (digit classes from 0 to 9). The gray dots are newly generated objects. Objects from four of the clusters are displayed.

Figure 6 :

 6 Figure 6: A sample of new types discovered by the model

Acknowledgments

We thank our anonymous referees for helpful comments. This work was partially supported by the HPC Center of Champagne-Ardenne ROMEO.This work has been funded by the P2IO LabEx (ANR-10-LABX-0038) in the framework Investissements dAvenir (ANR-11-IDEX-0003-01) managed by the French National Research Agency (ANR).


Mehdi Cherti

Balázs Kégl
email: balazs.kegl@gmail.comakin.kazakci@mines-paristech.fr

Akın Kazakçı

Out-of-class novelty generation: an experimental foundation *

Constructive machine learning aims at finding one or more instances of a domain which will exhibit some desired properties. Such a process bears a strong similarity with a design process where the ultimate objective is the generation of previously unknown and novel objects by using knowledge about known objects. The aim of the present work is to bring ideas from design theory to machine learning and elaborate an experimental procedure allowing the study of design through machine learning approaches. To this end, we propose an actionable definition of creativity as the generation of out-of-distribution novelty. We assess several metrics designed for evaluating the quality of generative models on this new task. Through extensive experiments on various types of generative models, we find architectures and hyperparameter combinations which lead to out-of-distribution novelty. Such generators can then be used to search a semantically richer and broader space than standard generative models would allow.

Introduction

Recent advances in machine learning have renewed interest in artificial creativity. Studies such as deep dream [START_REF] Mordvintsev | Inceptionism: Going deeper into neural networks[END_REF] and style transfer [START_REF] Gatys | A neural algorithm of artistic style[END_REF] have aroused both general public interest and have given strong impetus to use deep learning models in computational creativity research [START_REF]ICCC. Proceedings of the International Conference on Computational Creativity[END_REF]. Although creativity has been a topic of interest on and off throughout the years in machine learning [START_REF] Schmidhuber | Driven by Compression Progress: A Simple Principle Explains Essential Aspects of Subjective Beauty, Novelty, Surprise, Interestingness[END_REF], it has been slowly becoming a legitimate sub-domain with the appearance of dedicated research groups such as Google's Magenta and research work on the topic [START_REF] Nguyen | Innovation engines: Automated creativity and improved stochastic optimization via deep learning[END_REF][START_REF] Lake | Human-level concept learning through probabilistic program induction[END_REF].

Machine learning methods provide an important advantage for studying computational creativity: they enable the study of creativity in relation with knowledge (i.e., knowledge-driven creativity [START_REF] Kazakçı | Digits that are not: Generating new types through deep neural nets[END_REF]). Within the scope of machine learning, generative modeling can provide a way to study and answer quetions about novelty generation. According to [START_REF] Hatchuel | Ck design theory: an advanced formulation[END_REF][START_REF] Kazakçı | Conceptive artificial intelligence: Insights from design theory[END_REF], creativity is about generating previously unknown but meaningful (or valuable) new types of objects using previously acquired knowledge. Under this perspective, the goal of novelty generation is to sample objects from new types. This goal, which we shall call out-of-distribution generation, is beyond what can be formalized within the framework of traditional learning theory.

Arguably, the most important problem is the evaluation of what constitutes a good model for generating out-of-distribution. Traditional metrics based on likelihood are of no use since novelty in the out-of-distribution is unlikely by definition. Indeed, research in generative modeling usually aims at eliminating this possibility as this is seen as a source of instability [START_REF] Goodfellow | Generative adversarial nets[END_REF][START_REF] Salimans | Improved techniques for training GANs[END_REF] leading to spurious samples [START_REF] Bengio | Generalized denoising auto-encoders as generative models[END_REF]. This paper presents a new engineering principle that enables such evaluation, and consequently, rigorous experimental research on the matter: we evaluate the generative potential of models by holding out entire classes, simulating thus unknown but meaningful novelty. The goal of the novelty generator is then to use training classes to build a model that can generate objects from future (hold-out) classes, unknown at training time.

We present three main contributions: First, we design an experimental framework based on hold-out classes to develop and to analyze out-of-distribution generators. Second, we review and analyze the most common evaluation techniques from the point of view of measuring out-of-distribution novelty. We argue that likelihood-based techniques inherently limit exploration and novelty generation. We carefully select a couple of measures and demonstrate their applicability for out-of-distribution novelty detection in experiments. Third, we run a large-scale experimentation to study the ability of novelty generation of a wide set of different autoencoders and generative adversarial networks (GANs).

Probabilistic vs. constructive generative models

The generative process is commonly framed in a probabilistic setup: it is assumed that an underlying unknown likelihood model P (•) should first be learned on an i.i.d. training sample D = {x 1 , . . . , x n }, assumed to be generated from P (•), and then a sampler S should sample from the learned P (•). The first step, estimating P (•) using D, is a classical function learning problem that can be studied through the usual concepts of overfitting and regularization, and algorithms can be designed using the classical train/test principle. The second step, designing S for sampling from P (•) is also a classical domain of random sampling with a conceptual framework and a plethora of methods.

Technically both steps are notoriously hard for the high-dimensional distributions and the complex dependencies we encounter in interesting domains. Hence, most of the recent and successful methods get rid of the two-step procedure at the level of algorithmic design, and short-cut the procedure from the probabilistic D → P → S to the constructive D → A, where A(D) is a generator, tasked to produce sample objects similar to elements of D but not identical to them. A is fundamentally different from ( P , S) in that there is no explicit fitting of a function, we use D to directly design an algorithm or a program.

When the probabilistic setup is still kept for analysis, we face a fundamental problem: if we assume that we are given the true likelihood function P (•), the likelihood of the training sample 1 n n i=1 log P (x i ) is a random variable drawn independently from the distribution of log-likelihoods of i.i.d. samples of size n, so the trivial generator A which resamples D will have the same expected log-likelihood as an optimal i.i.d. sampler. The resampling "bug" is often referred to as "overfitting". While it makes perfect sense to talk about overfitting in the D → P → S paradigm (when P is fitted on D), it is somewhat conceptually misleading when there is no fitting step, we propose to call it "memorizing". When a generator A is trained on D without going through the fitting step D → P , the classical tools for avoiding memorizing (regularization, the train/test framework) may be either conceptually inadequate or they may not lead to an executable engineering design principle.

The conceptual problem of analyzing constructive algorithms in the probabilistic paradigm is not a minor nuisance which can be fixed by augmenting the likelihood to avoid resampling. Rather, it is an inherent property which cannot (or rather, should not) be fixed. The probabilistic framework is designed for generating objects from the distribution of known objects, and this is in an axiomatic contradiction with generating out-of-distribution novelty, objects that are unknown at the moment of assembling a training sample. Resampling (generating exact copies) is only the most glaring demonstration of a deeper problem which is also present in a more subtle way when attempting to generate new types of objects.

We are not arguing that the probabilistic generative framework should be banished, it has a very important role in numerous use cases. Our argument is that it is not adequate for modeling outof-distribution novelty generation. At the algorithmic/computational level the machine learning community has already started to move beyond likelihood. The ingenious idea of using discriminators in GANs [START_REF] Goodfellow | Generative adversarial nets[END_REF][START_REF] Salimans | Improved techniques for training GANs[END_REF] is a concrete example; although the setup can be analyzed through the lens of probabilistic sampling, one does not have to fall back onto this framework. If we drop the underlying conceptual probabilistic framework, the constructive GAN idea may be extended beyond generating from the set which is indistinguishable from the set of existing objects. In the next sections, we will use discriminators to assess the quality of generators whose very goal is to generate novelty: objects that are distinguishable from existing objects.

Evaluation of generative models

In our setup, we simulate existing knowledge and novelty by partitioning existing data sets holding out entire classes. The goal of the novelty generator is then to use training classes to build a model that can generate objects from future (hold-out) classes, unknown at training. The training classes are digits classes from MNIST and the test classes are letters classes from a dataset we constructed from google fonts (Google fonts). We pre-trained a digit discriminator (on MNIST), a letter discriminator (on Google fonts) and a discriminator on a mixture of digits and letters. We used the discriminators to evaluate novelty generators using different metrics which we outline in the following.

Parzen density estimator Parzen density estimators are regularly used for estimating the loglikelihood of a model [START_REF] Breuleux | Unlearning for better mixing[END_REF] when the log-likelihood is not tractable. A kernel density estimator is fit to generated points, and the model is scored by log-likelihood of a hold-out test set under the kernel density. The metrics can be easily fooled [START_REF] Theis | A note on the evaluation of generative models[END_REF], nevertheless, we adopted it in this paper for measuring both the in-distribution and out-of-distributions quality of our generators.

Objectness In [START_REF] Salimans | Improved techniques for training GANs[END_REF], they proposed an entropy-based score to measure the "objectness" of the generated set of objects. This score uses a pre-trained classifier to compute, for each generated object, the confidence of the classifier on each category, then the score is high if the classifier has a highly confident prediction on a category (hence the name objectness), also, the score encourages sets of generated objects which have a diverse set of categories.

Formally, objectness is defined as

1 N n i=1 K =1 p i, log p i, p ,
where K is the number of classes, p i, = P ( |x i ) is the posterior probability of category given the generated object x i , under the discriminator P trained on a set with known labels, and

p = 1 n n i=1 p i, ,
are the class marginals.

Out-of-class count and out-of-class max Naturally, letter discriminators see letters everywhere.

Since letters are all they know, they classify everything into one of the letter classes, quite confidently (this "blind spot" phenomenon is exploited by [START_REF] Nguyen | Innovation engines: Automated creativity and improved stochastic optimization via deep learning[END_REF] for generating "synthetic" novelty), the letter objectness of an in-distribution digit generator can sometimes be high. For example, a lot of 6s were classified as bs. To avoid this "bias", we also trained a discriminator on the union of digits and letters, allowing it to choose digits when it felt that the generated object looked more like a digit. We designed two metrics using this discriminator: out-of-class count measures the frequency of confidently classified letters in a generated set, and out-of-class max is the mean (over the set) of the probability of the most likely letter. None of these metrics penalize "fixated" generators, outputting the same few letters all the time, so we combine both metrics with a diversity term based on the entropy of the letter posterior (conditioned on being a letter).

I * i > K in ∧ p i, * i > θ + λ × diversity, and out-of-class max = (1 -λ) × 1 n n i=1 p i, * out i + λ × diversity.
In our experiments we set the confidence level θ = 0.95 and the mixture coefficient λ = 0.5.

Human evaluation

We assessed the visual quality of the set of generated objects using an in-house annotation tool. We took each model which appeared in the top ten by any of the quantitative metrics described in the previous section, and hand-labeled them into one of the following three categories: i) letters, ii) digits, and iii) bad sample (noise or not-a-symbol).

Each panel consisted 26 × 15 generated objects, the fifteen most probable symbols of each letter according to the classifier trained on both letters and digits (Figure 1). The goal of this annotation exercise was i) to assess the visual quality of the generated symbols and ii) to assess the quality of the metrics in evaluating novelty. 4 Experiments

Hyperparameter search

We considered two kinds of models, autoencoders and generative adversarial networks (GANs). We used three regularization strategies for autoencoders: sparse autoencoders [START_REF] Makhzani | k-sparse autoencoders[END_REF][START_REF] Makhzani | Winner-take-all autoencoders[END_REF], denoising autoencoders [START_REF] Bengio | Generalized denoising auto-encoders as generative models[END_REF] and contractive autoencoders [START_REF] Rifai | Contractive auto-encoders: Explicit invariance during feature extraction[END_REF]. We generated images from autoencoders using a procedure similar to [START_REF] Bahdanau | Smart decisions by small adjust-ments: Iterating denoising autoencoders[END_REF], except that we binarized (deterministically) the images in each iteration. In initial experiments we found that 100 iterations were sufficient for the majority of models to have convergence so we chose to fix the maximum number of iterations to 100. For stochastic gradient optimization of the autoencoder models, we used adadelta [START_REF] Zeiler | Adadelta: an adaptive learning rate method[END_REF] with a learning rate of 0.1 and a batch size of 128. We used rectified linear units as an activation function for hidden layers in all models. We use the sigmoid activation function for output layers.

For GANs, we built upon [START_REF] Radford | Unsupervised representation learning with deep convolutional generative adversarial networks[END_REF] and used their architecture as a basis for hyperparameter search. We modified the code proposed here to sample new combinations of hyperparameters. We ran a large scale hyperparameter optimization search and evaluated the proposed metrics. All the models were trained on MNIST training data. We obtained nearly 1000 models. We generated 1000 samples from each trained model. We then evaluated all the metrics proposed in section 3 on each trained model by using the 1000 generated samples and the pre-trained discriminators (see section 3). Figure 2 shows samples obtained one of our best autoencoders (a sparse autoencoder trained as in [START_REF] Makhzani | k-sparse autoencoders[END_REF]) according to out-of-class count and out-of-class max.

Analysis

First, we found that tuning (selecting) generative models for in-distribution generation will make them "memorize" the classes they are trained to sample from. This is of course not surprising, but it is important to note because it means that out-of-class generation is non-trivial, and the vast majority of architectures designed and tuned in the literature are not generating out-of-class novelty naturally. Second, we did succeed to find architectures and hyperparameter combinations which lead to out-of-class novelty. Most of the generated objects, of course, were neither digits nor letters (Figure 2), which is why we needed the "supervising" discriminators to find letter-like objects among them. The point is not that all new symbols are letters, that would arguably be an impossible task, but to demonstrate that by opening up the range of generated objects, we do not generate noise, rather objects that can be forming new categories.

The quantitative goal of this study was to assess the quality of the defined metrics in evaluating outof-distribution generators. We proceeded in the following way. We selected the top ten autoencoders and GANs according to the five metrics of out-of-class (letters) count, out-of-class max, out-of-class objectness, out-of-class Parzen, and in-class Parzen. We then annotated these models into one of the three categories of "letter" (out), "digit" (in), and "bad" (noise or not-a-symbol). The last three columns of Table 1 show that the out-of-class count and out-of-class max scores work well in selecting good out-of-class generators, especially with respect to in-class generators. They are relatively bad in selecting good generators overall. Symmetrically, out-of-class objectness and the Parzen measures select, with high accuracy, good quality models, but they mix out-of-class and in-class generators (digits and letters). Parzen scores are especially bad at picking good out-of-class generators. Somewhat surprisingly, even out-of-class Parzen is picking digits, probably because in-distribution digit generators generate more regular, less noisy images than out-of-class letter generators. In other words, opening the space towards non-digit like "spurious" symbols come at a price of generating less clean symbols which are farther from letters (in a Parzen sense) than clean digits.

We also computed the inter-score correlations in the following way. We first selected the top 10% models for each score because we were after the correlation of the best-performing models . Then we computed the Spearman rank correlation of the scores (so we did not have to deal with different scales and distributions). The first eight columns of Table 1 show that i) in-class and out-of-class measures are anti-correlated, ii) out-of-class count and max are uncorrelated, and are somewhat anti-correlated with out-of-class objectness.

These results suggest that the best strategy is to use out-of-class objectness for selecting good quality models and out-of-class count and max to select models which generate letters. Figure 3 illustrates the results by pangrams (sentences containing all letters) written using the generated symbols. The models (a)-(d) were selected automatically: these were the four models that appeared in the top ten Figure 3: Pangrams created (a-d) using top models selected automatically, and (e) using letters selected from several models by a human. We note that (b) corresponds to letters selected from the autoencoder in figure 2.

Summary and perspectives

The main focus of this paper was setting up the experimental pipeline and to analyze various quality metrics, designed to measure out-of-distribution novelty of samples and generative models. The immediate next goal is to analyze the models in a systematic way, to understand what makes them "memorizing" classes and what makes them opening up to generate valuable out-of-distribution samples.

Formally, let p i, 1

 1 , . . . , p i,Kin be the in-class posteriors and p i,Kin+1 , . . . , p i,Kin+Kout be the out-of-class posteriors, where K in = 10 is the number of in-class classes (digits), and K out = 26 is the number of out-of-class classes (letters). Let * i = arg max p i, and * outi = arg max Kin< ≤Kin+Kout p i, be the most likely category overall and most likely out-of-class category, respectively. Letp = n i=1 I { = * outi } n i=1 I { * outi > K in }be the normalized empirical frequency of the out-of-class category . We measure the diversity of the generated sample by the normalized entropy of the empirical frequencies diversity

  Figure 1: A couple of the top models according to human assessment. Top left characters of each 4 × 4 panel are the labels, letters coming from the training sample. For each letter we display the fifteen most probable symbols according to the classifier trained on both letters and digits.

Figure 2 :

 2 Figure 2: A random selection of symbols generated by one of our best autoencoders, the same as the one that generated the letters in Figure 3(b).

  both according to out-of-class objectness and out-of-class counts. Letters of the last sentence (e) were hand-picked by us from letters generated by several top models.

Table 1 :

 1 Inter-score correlations among top 10% models per score and human annotation counts among top twenty models per score. out=letters; in=digits.

				inter-score correlations			human counts
		oc	om	oo	op	ic	im	io	ip	out in bad
	out count	1	-0.03 -0.13 0.04 -0.12 0.02 -0.07 -0.11	12	0	l 8
	out max	-0.03	1	-0.07 0.01 -0.16 -0.10 0.03 -0.09	15	0	5
	out objectness -0.13 -0.07	1	0.21 -0.06 0.08	0.02 -0.08	9	10	1
	out Parzen	0.04	0.01	0.21	1	-0.17 0.01 -0.19 -0.20	4	13	3
	in count	-0.12 -0.16 -0.06 -0.17	1	0.30	0.1	0.14	-	-	-
	in max	0.02 -0.10 0.08	0.01	0.30	1	0.03	0.06	-	-	-
	in objectness	-0.07 0.03	0.02 -0.19	0.1	0.03	1	0.00	-	-	-
	in Parzen	-0.11 -0.09 -0.08 -0.20 0.14	0.06	0.00	1	0	17	3

Acknowledgments

This work was partially supported by the HPC Center of Champagne-Ardenne ROMEO.


Alan Ayala

Xavier Claeys

Victorita Dolean

Martin J Gander

Closed Form Inverse of Local Multi-Trace Operators

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Local multi-trace operators arise when one uses a particular integral formulation for a transmission problem. A transmission problem for a second order elliptic operator is a problem defined on a domain which is decomposed into non-overlapping subdomains, but instead of imposing the continuity of the traces of the solution and their normal derivative along the interfaces between the subdomains, given jumps are imposed along the interfaces. The solution of a transmission problem is thus naturally discontinuous along the interfaces, and hence a domain decomposition formulation is imposed by the problem.

A local multi-trace formulation represents the solution in each subdomain using an integral formulation, and couples these solutions imposing the given jumps in the traces of the solution and the normal derivatives along the interfaces (hence the name multi-trace). This formulation was introduced in [START_REF] Hiptmair | Multiple traces boundary integral formulation for Helmholtz transmission problems[END_REF] to tackle transmission problems for the Helmholtz equation, where the material properties are constant in each subdomain, see also [START_REF] Claeys | Electromagnetic scattering at composite objects: a novel multi-trace boundary integral formulation[END_REF][START_REF] Claeys | Multi-trace boundary integral formulation for acoustic scattering by composite structures[END_REF], and [START_REF] Claeys | A second-kind Galerkin boundary element method for scattering at composite objects[END_REF] for associated boundary integral methods. Multi-trace formulations lead naturally to block preconditioners, see [START_REF] Hiptmair | Domain decomposition for boundary integral equations via local multi-trace formulations[END_REF]. In [START_REF] Dolean | Multitrace formulations and Dirichlet-Neumann algorithms[END_REF], a simple introduction to local multitrace formulations is given in the language of domain decomposition, and it is shown that these block preconditioners are equivalent to the simultaneous application of a Dirichlet-Neumann and a Neumann-Dirichlet method to the transmission problem. Block preconditioners based on multi-trace formulations have also the potential to lead to nil-potent iterations, a more recent area of research in domain decomposition [START_REF] Chaouqui | On nilpotent subdomain iterations[END_REF], and it was shown that for two subdomains, they correspond to optimal Schwarz methods, see [START_REF] Claeys | An Introduction to Multitrace Formulations and Associated Domain Decomposition Solvers[END_REF].

Universié Pierre et Marie Curie, and INRIA Paris, France claeys@ann.jussieu.fr • University of Strathclyde, Glasgow, United Kingdom Victorita.Dolean@strath.ac.uk • University of Geneva, Switzerland martin.gander@unige.ch We are interested here in the inverse of local multi-trace operators. We exhibit a closed form of this inverse for a model problem with three subdomains in the special case where the coefficients are homogeneous. An essential ingredient to obtain this closed form inverse are several remarkable identities which were recently discovered, see [START_REF] Claeys | An Introduction to Multitrace Formulations and Associated Domain Decomposition Solvers[END_REF]. We illustrate our findings with a numerical experiment that shows that discretizing the closed form inverse gives indeed and approximate inverse of the discretized local multi-trace operator.

Local Multi-Trace Formulation

We start by introducing the local multi-trace formulation for a model problem. Consider a partition of the space R d = Ω 0 ∪Ω 1 ∪Ω 2 as shown in Figure 1. We assume that Ω j , j = 0, 1, 2 are Lipschitz domains such that Ω j ∩ Ω k = ∅ for j = k. Denoting by Γ j := ∂Ω j , we assume in addition that Γ 1 ∩ Γ 2 = ∅ and Γ 0 = Γ 1 ∪ Γ 2 . Let n j be the unit outer normal for Ω j on its boundary Γ j . For a sufficiently regular function v we denote by v| + Γj the trace of v and by ∂ nj v| + Γj the trace of n j • ∇v on Γ j taken from inside of Ω j . Similarly we define v| - Γj and ∂ nj v| - Γj but with traces from outside of Ω j . The elliptic transmission problem for which we want to study the local multi-trace formulation and its inverse is:

find u ∈ H 1 (R d ) such that -∆u + a 2 j u = 0 in Ω j , j = 0, 1, 2, [u] Γ1 = g 1 , [u] Γ2 = g 2 , [∂ n u] Γ1 = h 1 , [∂ n u] Γ2 = h 2 , (1)
where a j > 0 for j = 0, 1, 2, g j ∈ H +1/2 (Γ j ) and h j ∈ H -1/2 (Γ j ) are given data of the transmission problem, and we used the classical jump notation for the Dirichlet and Neumann traces of the solution across the interfaces

Γ j , j = 1, 2, i.e. [u] Γj := u| + Γj -u| - Γj and [∂ n u] Γj := ∂ nj u| + Γj -∂ nj u| - Γj .
Following [START_REF] Hiptmair | Domain decomposition for boundary integral equations via local multi-trace formulations[END_REF], this problem can be rewritten as a boundary integral local multi-trace formulation, using the Calderón projector: let H(Γ j ) := H 1/2 (Γ j ) × H -1/2 (Γ j ); then for (g, h) ∈ H(Γ j ), the Calderón projector P j : H(Γ j ) → H(Γ j ) interior to Ω j associated to the operator -∆ + a 2 j is defined by

P j (g, h) := (v| + Γj , ∂ nj v| + Γj ) where v satisfies -∆v + a 2 j v = 0 in Ω j and in R d \ Ω j , [v] Γj = g and [∂ n v] Γj = h,
and lim sup |x|→∞ |v(x)| < +∞, and P j is known to be a continuous map, see [START_REF] Sauter | Boundary element methods[END_REF]. The decomposition Γ 0 = Γ 1 ∪ Γ 2 induces a natural decomposition of P 0 in the following manner: for any

U ∈ H(Γ 0 ) set ρ j (U ) := U | Γj ∈ H(Γ j ), j = 1, 2. In addition, for any V ∈ H(Γ j ), j = 1, 2, define ρ * j (V ) ∈ H(Γ 0 ) by ρ * j (V ) = V on Γ j and ρ * j (V ) = 0 on Γ 0 \ Γ j .
Then the projector P 0 can be decomposed as

P 0 = P1 R 1,2 /2 R 2,1 /2 P2 , where Pj := ρ j • P 0 • ρ * j , R j,k /2 := ρ j • P 0 • ρ * k .
The operators Pj :

H(Γ j ) → H(Γ j ) and R j,k : H(Γ k ) → H(Γ j ) are continuous.
Following this decomposition, we identify H(Γ 0 ) with H(Γ 1 )×H(Γ 2 ). We also introduce the sign switching operator X(v, q) := (v, -q), and a relaxation parameter σ ∈ C\{0}. The local multi-trace formulation of problem ( 1) is then: find (U 1 , U

(0) 2 , U 2 ) ∈ H(Γ 1 ) 2 × H(Γ 2 ) 2 such that     (1 + σ)Id -P 1 -σX 0 0 -σX (1 + σ)Id -P1 -R 1,2 /2 0 0 -R 2,1 /2 (1 + σ)Id -P2 -σX 0 0 -σX (1 + σ)Id -P 2     •     U 1 U (0) 1 U (0) 2 U 2     = F, (0) 1 , U
where F ∈ H(Γ 1 ) 2 × H(Γ 2 ) 2 is some right-hand side depending on g j , h j , σ whose precise expression is not important for our present study, where we want to obtain an explicit expression for the operator in (2) and its inverse for the special case

a 0 = a 1 = a 2 . (3)
To simplify the calculations when working with the entries of the operator in (2), we set A j := -Id + 2P j and Ãj := -Id + 2 Pj . The following remarkable identities were established in [3, §4.4] for the special case (3):

P 2 j = P j , P2 j = Pj , P1 R 1,2 = P2 R 2,1 = 0, XP j X = Id -Pj , and finally R 1,2 R 2,1 = R 2,1 R 1,2 = 0.
These five properties can be reformulated in terms of the operators A j , namely

i) A 2 j = Ã2 j = Id, ii) Ã1 R 1,2 = -R 1,2 and Ã2 R 2,1 = -R 2,1 , iii) X • A j • X = -Ãj , iv) R 1,2 R 2,1 = R 2,1 R 1,2 = 0, v) R 1,2 Ã2 = R 1,2 and R 2,1 Ã1 = R 2,1 . (4)
Let us introduce auxiliary operators A, Π : H(Γ 1 ) 2 × H(Γ 2 ) 2 defined by

A :=     A 1 0 0 0 0 Ã1 R 1,2 0 0 R 2,1 Ã2 0 0 0 0 A 2     , Π :=     0 X 0 0 X 0 0 0 0 0 0 X 0 0 X 0     . (5)
According to property i) in ( 4), we have (Id + A) 2 /4 = (Id + A)/2, which implies the well known Calderón identity from the boundary integral equation literature, i.e.

A 2 = Id, (6)
see for example [11, §4.4]. The local multi-trace operator on the left-hand side of Equation ( 2) can then be rewritten as

MTF loc := - 1 2 A -σΠ + (σ + 1 2 )Id. (7)
In ( 2), the terms associated with the relaxation parameter σ, namely Id -Π, enforce the transmission conditions of problem [START_REF] Chaouqui | On nilpotent subdomain iterations[END_REF]. For σ = 0, we have MTF loc = 1 2 (Id -A), which is a projector, and MTF loc is thus not invertible. For σ = 0 however, MTF loc was proved to be invertible in [START_REF] Claeys | Essential spectrum of local multi-trace boundary integral operators[END_REF]Cor. 6.3]. The goal of the present contribution is to derive an explicit formula for the inverse of MTF loc , and we will thus assume σ = 0.

Inverse of the Local Multi-Trace Operator

We now derive a closed form inverse of the local multi-trace operator in [START_REF] Dolean | Multitrace formulations and Dirichlet-Neumann algorithms[END_REF] for the special case [START_REF] Claeys | An Introduction to Multitrace Formulations and Associated Domain Decomposition Solvers[END_REF]. Using that Π 2 = Id and (6), we obtain

[ -A/2 -σΠ + (σ + 1/2)Id ] [ -A/2 -σΠ -(σ + 1/2)Id ] = (A/2 + σΠ) 2 -(σ + 1/2) 2 Id = (σ 2 + 1/4 -σ 2 -σ -1/4)Id + σ(AΠ + ΠA)/2 = -σId + σ(AΠ + ΠA)/2. ( 8
)
Inspired by the calculations in [3, §4.4] as well as [2, Prop. 6.1], we examine more closely AΠ + ΠA. We start by comparing AΠ and ΠA:

AΠ =     0 A 1 X 0 0 Ã1 X 0 0 R 1,2 X R 2,1 X 0 0 Ã2 X 0 0 A 2 X 0     , ΠA =     0 X Ã1 XR 1,2 0 XA 1 0 0 0 0 0 0 XA 2 0 XR 2,1 X Ã2 0     . (9)
According to Property iii) in (4), we have X Ãj +A j X = 0 and XA j + Ãj X = 0, and thus from ( 9) we obtain

ΠA + AΠ =     0 0 XR 1,2 0 0 0 0 R 1,2 X R 2,1 X 0 0 0 0 XR 2,1 0 0     .
Computing the square of this operator, and taking into account Property iv ) from ( 4), we obtain

(ΠA + AΠ) 2 =     XR 1,2 R 2,1 X 0 0 0 0 R 1,2 R 2,1 0 0 0 0 R 2,1 R 1,2 0 0 0 0 XR 2,1 R 1,2 X     = 0.
From this we conclude that (-

Id + (AΠ + ΠA)/2) -1 = -Id -(AΠ + ΠA)/2.
Coming back to [START_REF] Geuzaine | Gmsh: A 3-D finite element mesh generator with built-in pre-and post-processing facilities[END_REF], we obtain a first expression for the inverse of the local multi-trace operator, namely

[ -A/2 -σΠ + (σ + 1/2)Id ] -1 = σ -1 [ A/2 + σΠ + (σ + 1/2)Id ] [Id + (AΠ + ΠA)/2] = σ -1 [ 1 2 (1 + σ)A + (σ + 1/4)Π + (σ + 1/2)(Id + (AΠ + ΠA)/2)] + σ -1 [ σ 2 ΠAΠ + 1 4 AΠA]. (10)
The only terms that are not explicitly known yet in [START_REF] Hiptmair | Domain decomposition for boundary integral equations via local multi-trace formulations[END_REF] are the last two, ΠAΠ and AΠA. Combining (9) with Definition (5), direct calculation yields

ΠAΠ =     -A 1 0 0 XR 1,2 X 0 -Ã1 0 0 0 0 -Ã2 0 XR 2,1 X 0 0 -A 2     ,
and similarly, we also obtain

AΠA =     0 -X XR 1,2 0 -X 0 0 -R 1,2 X -R 2,1 X 0 0 -X 0 XR 2,1 -X 0     .
We have now derived an explicit expression for each term in [START_REF] Hiptmair | Domain decomposition for boundary integral equations via local multi-trace formulations[END_REF], which leads to a close form matrix expression for the inverse of the local multi-trace operator, namely

MTF -1 loc = (1 + 1 2σ )Id + 1 σ     1 2 A 1 σX σ+1 2 XR 1,2 σ 2 XR 1,2 X σX 1 2 Ã1 σ+1 2 R 1,2 σ 2 R 1,2 X σ 2 R 2,1 X σ+1 2 R 2,1 1 2 Ã2 σX σ 2 XR 2,1 X σ+1 2 XR 2,1 σX 1 2 A 2     . (11)
The expression MTF loc •MTF -1 loc = Id should not be mistaken for the Calderón identity [START_REF] Claeys | A second-kind Galerkin boundary element method for scattering at composite objects[END_REF]. The primary difference is that (11) involves coupling terms between Ω 1 and Ω 2 , whereas in [START_REF] Claeys | A second-kind Galerkin boundary element method for scattering at composite objects[END_REF], all three subdomains are decoupled.

Numerical Experiment

We now illustrate the closed form inversion formula [START_REF] Nédélec | Acoustic and electromagnetic equations[END_REF] for the local multitrace formulation by a numerical experiment. We consider a three dimensional version of the geometrical setting described at the beginning in Figure 1.

Here Ω 1 := B(0, 0.5) is the open ball centered at 0 with radius 0.5,

Ω 2 := R 3 \[-1, +1] 3 , and Ω 0 := R 3 \ Ω 1 ∪ Ω 2 , see Figure 2.
For our numerical results, we discretize both MTF loc given by ( 7) leading to a matrix we denote by [MTF loc ], and MTF -1 loc given by ( 11) leading to a matrix denoted by [MTF -1 loc ]. Our discretization using the code bemtool 1 is based on a Galerkin method where both Dirichlet and Neumann traces are approximated by means of continuous piece-wise linear functions on the same mesh. We use a triangulation with a mesh width h = 0.35, and generated the mesh using Gmsh, see [START_REF] Geuzaine | Gmsh: A 3-D finite element mesh generator with built-in pre-and post-processing facilities[END_REF]. Let M h be the mass matrix associated with the duality pairing used to write (2) in variational form. We represent the spectrum of the matrix M 3. We see that the eigenvalues are clustered around 1, which agrees well with our analysis at the continuous level.

-1 h • [MTF loc ]•M -1 h •[MTF -1 loc ] in Figure

Conclusions

We have shown in this paper that it is possible for the local multi-trace operator of a model transmission problem to obtain a closed form for the inverse. This would therefore be an ideal preconditioner for local multi-trace formulations. We are currently investigating if such closed form inverses are also possible for more general situations, where the coefficients are only constant in each subdomain, and in the presence of more subdomains. The closed form inverse seems to be inherent to the formulation, and not dependent on the specific form of the partial differential equation.

Fig. 1

 1 Fig. 1 Geometrical configuration we consider in the analysis

Fig. 2

 2 Fig. 2 3D geometry for the numerical experiment

Fig. 3

 3 Fig. 3 Eigenvalues of the matrix M-1 h • [MTF loc ] • M -1 h • [MTF -1 loc ] for σ = -1 2, with a zoom below around 1.

available on https://github.com/xclaeys/bemtool under Lesser Gnu Public License.

Acknowledgement This work received support from the ANR research Grant ANR-15-CE23-0017-01.


est destinée au dépôt

Introduction

Benoit Gaudin, Bezabeh Wolde

To cite this version:

Benoit Gaudin, Bezabeh Wolde. Introduction . Benoit Gaudin. Kenyan and Ethiopian Athletics -Towards an Alternative Scientific Approach , 2017. hal-01427743

Introduction

Dr. Benoit Gaudin 1 and Dr. Bezabeh Wolde 2

Scientific studies on East-African distance runners usually follow the long tradition of research on "Black" populations, stating in essence that "these people are different from us". Generations of researchers have been basing their works on this undeclared and often unconscious premise, successively in medicine, phrenology, anatomy, physiology and more recently in genetics. And although very few of them would admit it in public, none of these research works has ever found any evidence of a more fundamental difference than the pigmentation of the skin to characterize the difference between these populations and others. Yet this paradigm is still in force, based on the deeply-rooted belief of a biological otherness of "Black" populations.

Challenging this tradition of research, we suggest a paradigm shift. First, discarding the premise of the biological otherness of "these people".Instead, we should study them, and conduct research on them, in just the same way as we would do with "normal" athletes.Is there any serious research team searching for the gene behind the success of Canadian ice-hockey players? Or any researchers measuring the ankle diameter of New-Zealand"s rugby players? This matter is not only scientific, but also political. Only hypocrites deny it. More specifically, the issue is racial, because we never look at "Black" athletes in the same way we look at other athletes. As a consequence, don"t look into this book for revelations on any "mystery" or "secret" behind the success of Kenyan or Ethiopian runners. Simply because there is no "mystery" or "secret" in the East-African athletics, just as there is none in New Zealand rugby or in Canadian ice hockey.

East-African runners, and broadly speaking "Black" sportsmen have to be studied just like other athletes and their performances explained in the same way, by a bundle of arguments dealing with training techniques and programs, psychological motivations, and social and economical determinants. So the second change to be introduced is to open the field to social and human sciences: psychology and economics, but also history, geography, sociology and anthropology.

"But then, what about altitude?" you might ask. "Don"t they get their athletic superiority from living at high altitudes?" Again, we have gone astray: it is not altitude in itself, but the change in altitude which leads to an increase in the number of red blood cells in our blood. This increase is a metabolic reaction to hypoxic stress: going up in altitude, the body encounters an environment with lower barometric pressure and, as a response to this situation, engages in the production of more red blood cells, compensating the decrease in oxygen by an increase in "oxygen carriers". This metabolic mechanism applies to individuals who go up in altitude, but not to people who don"t expose their body to any change of altitude. For individuals who were born at 2 000 meters or more, who grew up there and have spent all their lives at this altitude, there is no change in altitude, thus no hypoxic stress and therefore no additional production of red blood cells. This is confirmed by a piece of research in hematology led by Professor Cynthia Bell on Ethiopian high altitude populations. 3 "What about genetics? Don"t they have any specific genetic traits? Aren"t all from the same tribe?" Indeed, an impressive proportion of Kenyan runners do come from the same tribe, the Kalenjin. And the Ethiopian runners who come from the village of Bekoji in the Arsi region are also overrepresented among the champions of this country. But again, we are misled by simplistic explanations. First, in both countries, several champions come from other regions and other ethnic groups. So the ethnic explanation is, at the very best, insufficient. Second, ethnic groups are neither isolated nor homogeneous genetic entities. So "ethnicity" is not equal to "common genetic features". Third, the link between one gene (or even a combination of genes) and any athletic skill is far from being a scientifically attested reality. Fourth, ethnic groups are cultural and linguistic communities in which solidarity actions occur, such as sharing information that is key to the career of an athlete: the phone number of an agent, contact with a race organizer or more simply a training program for a competition. Ethnicity is, at least, equally related to social and cultural factors as to biological features.

Here we may stop and make a first observation: as scientifically unfounded as they are, the issues of altitude and of genetics -of biological otherness -are indeed widespread and unquestioned beliefs. As such, they are genuine sociological objects of study. And just like any other beliefs, they do have performative effects: motivating some groups -East African runnersandde-motivating others -non-African runners -and thus establishing a line of legitimacy among the competitors of any international athletic event.

A second observation: visiting the Kalenjin area in Kenya and Addis Ababa in Ethiopia, we soon realize the existence of genuine cultures of athletics, taking "culture" in its ethnographic sense. These cultures of athletics are complex and consistent sets of traits, made of complementary components: technical training methods (including warming up, stretching and relaxing exercises); specific tools and objects; peculiar knowledge and know-how; a sufficient critical mass of accumulated and transmitted professional experiences; social and professionals networks with an internal hierarchy; specific values, codes and beliefs; unique routines, timetable and rolemodels, among other specific features. These cultures of athletics are per se objects of ethnographic monographs. To paraphrase Emile Durkheim, we could say that when a young Kalenjin / Oromo arrives into Kenyan / Ethiopian society, (s)he can find an already established athletics universe and does not need to re-invent everything by him/herself. (S)he is benefiting from the existence of this culture of athletics. Such a situation occurs in Ethiopia and Kenya, and nowhere else in the world.

Starting from these observations, a social and human sciences approach to the phenomenon should document the social, cultural, psychological and economic dimensions of the athletic performance of these runners. Following a constructivist perspective, we assume that the current situation is the result of two processes: an historical process of progressive construction of these cultures of athletics in Ethiopia and Kenya since the 1960s; and an anthropological process of individual acquisition, at the scale of a man"s life, of this culture of athletics by some young Ethiopians and Kenyans. The latter process has three dimensions: first, the shaping of the body through exercises and training; second, the social integration into the local world of athletics; and third the mental conversion to the values of professional sport competition. All these dimensions -but not only these -still need to be documented.

Apart from some notable exceptions4 , the study of African Athletics in the social sciences is still a relatively blank field and entire sections are yet to be explored. For instance, the history of athletics in Kenya and Ethiopia, the geography of athletics in these two countries including their internal and external migrations and the economy of these universes including the professional opportunities and their impact in terms of local development. We may add to this the demographics of local athletics, the study of social and professional institutions, the relationships between both athletics and other local sports, and also their position in the international division of athletic work with other nations specialized in athletics, etc.

The nineteen contributions gathered in this collective book aim to fill some of these gaps. They reflect the growing interest of the local and international scientific community in such an approach to the phenomenon. This book intends thus to be the first compilation of research work in the human and social sciences conducted on East-African athletics by scholars from Ethiopia, Kenya and the rest of the world. And indeed the proportion of youngresearchersand/orPhD studentsamong the contributorsholds promiseoffuture publicationson the subject. This is another important and original feature of this book: local researchers are doing the lion"s share of the job, in a rare example of regional scientific cooperation between Ethiopia and Kenya. Through its URMIS "MigrationandSociety" research unit, the French Institut de Recherche pour le Développement, locally known as IRD, has been instrumental in this enterprise, as it is part of its goal to supportresearchers from Southern countries, to promoteinternational scientific cooperation and to develop localresearchthrough research trainingand practice.

All contributions presented in this book feature originalresearch works, rigorously based on fieldwork studies and/or first-hand data, and they all provide new and original knowledge on Ethiopian and Kenyan runners. Not all of these contributions have the same scientific status, ranging from descriptive surveys and case studies to inductive or deductive pieces of works based on theoretical frameworks imported from other fields of study. Mostof these pieces of research were presentedto the scientific communityat the International Symposium on East-AfricanAthletics& SocialSciences held inJune 2015in Addis Ababa.All havebeenreviewed by an international scientificcommittee composed ofexperts inEast African studies, sport scienceand / orsocial sciences.Eachcontributionhas gone througha double-blind peer-reviewed process and only those that successfully passed this review procedure are included in this book.

A couple of contributions are not specifically focused on athletics as they more broadly address some specific aspects of sport in East-Africa. It seemed to us important to include them in this book, as articles on East-African sports are rare. Also, they help contextualize East-African distance runners within their local context, describing the universe in which they live.

Yet none of the contributions of this book will provide any definitive answer to all the questions about East-African distance running. Nor will they fully explore all the dimensions of the issue. At the crossroads of politics with science, but also of life sciences with social sciences, the matter is too broad and too complex to be exhausted in a single book. Still each of these articles casts, in its own way, a light on a part of the phenomenon, bringing a contribution to a deeper knowledge and a better understanding of East-African runners, their motivations and their social, cultural, economic and institutional environment. As a consequence, this book will provide evidence that East-African runners are not as "different" as they are usually perceived to be, helping us to take them for what they are: sportsmen and women like any others.

Senior researcher, IRD-URMIS and Dept of Sport Science, Addis Ababa University, Ethiopia.

Associate Professor, Dept of Sport Science, Addis Ababa University, Ethiopia.

Beall Cynthia et al., "An Ethiopian pattern of human adaptation tohigh-altitude hypoxia", PNASDecember 24, 2002, vol. 99, no.26, pp. 17215-17218.

Bale John et Sang Joe, Kenyan running: movement culture, geography and global change, London: F. Cass, 1996; Bale John, Kenyan running before the 1968 Mexico Olympics, pp. 11-23 and Jarvie Grant, The promise and possibilities of running in and out of east Africa, pp. 24-39 in Pitsiladis Y., Bale J., Sharp C., and Noakes T., East African Running: Toward a Cross-Disciplinary Perspective, Routledge, 2007.