Waldo Cancino
email: waldo.cancino@inria.fr

Nadia Boukhelifa
email: nadia.boukhelifa@inria.fr

Evelyne Lutton
email: evelyne.lutton@inria.fr

EvoGraphDice : Interactive Evolution for Visual Analytics

Visualization of large and complex datasets is a research challenge, especially in frameworks like industrial design, decision making and visual analytics. Interactive Evolution, used not only as an optimisation tool, but also as an exploration tool may provide some versatile solutions to this challenge. This paper presents an attempt in this direction with the EvoGraphDice prototype, developed on top of GraphDice, a general purpose visualization freeware for multidimensional visualization based on scatterplot matrices. EvoGraphDice interactively evolves compound additional dimensions, that provide new viewpoints on a multidimensional dataset. Compound dimensions are linear combination of the initial data dimensions, they are initialised with a Principal Component Analysis (PCA), and modified progressively by the interactive evolution process. Various interactions are available to the user, either in a transparent way, via a capture of mouse-clicks, or in a fully controlled manner, where the user has the opportunity to modify or include his own compound dimension in the evolved population, control the search space, or do some interactive queries. EvoGraphDice is tested on a synthetic dataset of dimension 6, where a known dependency is rediscovered via interactive manipulation. A second example is presented, based on a real dataset of dimension 13, provided by an industrial partner. Our experiments prove the potential of this interactive approach, and allow us to sketch future directions of development for the EvoGraphDice prototype.

I. INTRODUCTION

Visual analytics can be defined as "the science of analytical reasoning facilitated by visual interactive interfaces" [START_REF] Thomas | A visual analytics agenda[END_REF]. Research in this domain is trying to produce the most versatile and adapted tools for users to be able to visualize, understand, manipulate or transform multidimensional complex data for various tasks. In doing this, however, the designer of visual analytics systems is faced with the problem of finding the most appropriate methodological and parametric choices for the comfort and freedom of use. Additionally, the variety of end user needs, capabilities and cultural habits, make this problem even more complex. Consequently, current developed systems tend to provide more and more freedom and flexility to the user, potentially at the cost of overwhelming him with a maze of possible exploration paths.

Interactive Evolutionary Algorithms (IEA), i.e. optimisation algorithms that are able to optimise subjective data [START_REF] Sims | Interactive evolution of dynamical systems[END_REF]- [START_REF] Lutton | An interactive ea for multifractal bayesian denoising[END_REF], may be an attractive solution to this paradox. The purpose of this paper, is to develop a prototype of interactive evolution aimed at helping users explore complex datasets. The idea is to let the IEA propose smaller sets of potential viewpoints for the user, based on past interactions.

There are many important issues to consider for proposing such a guiding system, among which: efficient and transparent use of interaction data, simultaneous visualization of different potential solutions, and management of diversity.

We feel that Interactive Evolutionary Algorithms (IEA) are convenient for guiding the user in a complex dataset without too many constrains. This opinion is founded by the following characteristics of simulated evolution:

• focus: by nature artificial evolution is a stochastic optimisation tool: IEA optimises a fitness function that aggregates some measures of comfort or satisfaction of the user, i.e. it has the ability to focus the attention of the user toward some "interesting" area of the search space, • diversity preservation: diversity comes from two sources:

(a) stochasticity of the elementary mechanisms, that usually makes EA robust for optimisation tasks, and (b) population-based scheme, that allows to display a variety of solutions to the user at any stage of the process, Interactive design, or exploration, is not only an optimisation task, diversity management needs special attention, and is an important component that deals with user's creativity [START_REF] Chapuis | Artie-fract : Interactive evolution of fractals[END_REF], [START_REF] Lutton | Evolution of fractal shapes for artists and designers[END_REF],

• adaptation: it is also known that EA are able to deal with varying environment; IEA have been proven to be able to follow change of user focus, see for instance [START_REF] Lutton | Evolution of fractal shapes for artists and designers[END_REF].

Let us note, finally, that the focus of current research in interactive evolution seems to be more on industrial or artistic design tasks, than on data exploration tasks [START_REF] Giacobini | Applications of Evolutionary Computing, ser. EvoWorkshops 2007: EvoCoMnet, EvoFIN, EvoIASP,EvoINTERACTION, Evo-MUSART, EvoSTOC and EvoTransLog[END_REF]. Our current work can be placed in the latter category and is strongly related to the field of diversity management [START_REF] Landrin-Schweitzer | Introducing lateral thinking in search engines[END_REF].

The work described in this paper is part of the CSDL project (Complex Systems Design Lab, 2009-2012), a project funded by the French "System@tic pole" whose main contractor is an industrial partner, Dassault Aviation, and that involves 27 partners both from academy and industry. The objectives of the CSDL project is to set up a complete collaborative decision making framework for complex systems design purposes 1 . The role of our team in this project is to deal with the Visual Analytics issues. In the framework of computer simulation of very complex systems, interactive evolution is considered as a mean to :

• improve exploration in very large parameter spaces, while controlling the computational power allocated to simulation calculations (refinement on demand for some areas of the parameter space), • improve the understanding of some design compromises (Pareto front visualization), • validate or reconsider intuitive or classical design choices,

• discover optimal and/or unconventional parameters setting. Our prototype is based on a visualization tool developed in the AVIZ team of INRIA [START_REF] Elmqvist | Rolling the Dice: Multidimensional Visual Exploration using Scatterplot Matrix Navigation[END_REF], GraphDice, to which we added evolutionary capabilities. The paper is organized as follows: related work in data visualization are presented in sections II-A and II-B, while previous work involving interactive evolution and visual analytics is discussed in section II-C. The prototype is presented in section III, and tested on two datasets (synthetic and real data) in section IV. Conclusions and future work are sketched in section V.

II. RELATED WORK

A. Multidimensional Data Visualization and SPLOMs

Multidimensional visualization is concerned with providing visual tools to explore high-dimensional datasets and to reveal aspects of this data that are not, or at least not easily, revealed by standard statistical methods [START_REF] Loftus | A picture is worth a thousand p values: On the irrelevance of hypothesis testing in the microcomputer age[END_REF]. Here, each data attribute represents a dimension and thus the challenge is to map n-D data space onto a 2-D screen space. Beyond the problem of mapping and projections, there are issues of occlusion, dimension ordering and navigation. Many multidimensional visualization techniques have been proposed and classified; Keim [START_REF] Keim | Information Visualization and Visual Data Mining[END_REF] gives a taxonomy of primarily multidimensional visualization techniques. More specifically, Ward [START_REF] Ward | A taxonomy of glyph placement strategies for multidimensional data visualization[END_REF] describes a taxonomy for glyph placement strategies, and Valiati et al. [START_REF] Valiati | A taxonomy of tasks for guiding the evaluation of multidimensional visualizations[END_REF] propose a task taxonomy for guiding evaluations of multidimensional visualizations.

In this paper, we use Scatter Plot Matrices (SPLOMs) [START_REF] Andrews | Plots of high-dimensional data[END_REF], [START_REF] Cleveland | Dynamic Graphics for Statistics, ser. Statistics/Probability Series[END_REF] as our primary multidimensional visualization method. SPLOMs, sometimes referred to as draftsman's plots, are well known for visualizing high-dimensional data and can be found in many statistical packages. Here, data dimensions are assigned to both rows and columns of a matrix; each cell in the matrix is a 2-D projection of the data depicted as a scatter plot. The method builds on user familiarity with scatter plots; known for their simplicity and high visual clarity [START_REF] Tufte | The Visual Display of Quantitative Information[END_REF]. The matrix itself is useful for quickly assessing bivariate combinations of interest. Thus, dependencies, clusters and outliers can be quickly identified. However, even with a small number of dimensions, scatter plot matrices can grow large in size resulting in thumbnail cells that are difficult to examine in detail. To deal with issues of high-dimensionality many systems offer SPLOM interactivity whereby, the overview matrix becomes the interface to drive the exploration of the 2-D bivariate space, and detailed views of the scatter plots are coordinated with the main display via brushing-andlinking [START_REF] Becker | Brushing scatterplots[END_REF], [START_REF] Seo | Rank-by-feature framework for interactive exploration of multidimensional data[END_REF]. ScatterDice [START_REF] Elmqvist | Rolling the Dice: Multidimensional Visual Exploration using Scatterplot Matrix Navigation[END_REF] is one such system but it differs from similar systems in that it offers a coherent and structured navigation through the n-dimensional space, as described in the next section.

B. ScatterDice and GraphDice Systems

ScatterDice [START_REF] Elmqvist | Rolling the Dice: Multidimensional Visual Exploration using Scatterplot Matrix Navigation[END_REF] is an interactive visual tool for exploring multidimensional data sets. Users navigate the multidimensional space via simple 2-D projections, organised in a scatterplot matrix. This overview of thumbnail satterplots is linked to a detailed view where bivariate projections can be further investigated. One of the core features of the tool is that navigation in the multidimensional space, thus the transitions between scatterplots in the matrix, is performed as animated rotations in the 3-D space analogous to rolling a dice. Other features of the system include dimension reordering, visual queries and various interaction techniques for controlling transitions between scatterplots.

ScatterDice was further extended to support multivariate network visualization tasks, and the new system was called GraphDice [START_REF] Bezerianos | GraphDice: A System for Exploring Multivariate Social Networks[END_REF]. It uses the main multidimensional navigation paradigm of ScatterDice but extends it with novel mechanisms to support network exploration in general and Social Network Analysis (SNA) tasks in particular. 2 We have chosen to work with GraphDice as our Visual Analytics (VA) tool for rapid prototyping and convenient access to expert users. GraphDice is an inhouse tool built by our research team and is already used by a number of research projects for visual exploration of multidimensional data sets (for instance, for visual analysis of evolutionary algorithms behavior, see [START_REF] Lutton | Visual Analytics of EA Data[END_REF]). The advantage is that users who are familiar with the GraphDice system, do not have to go through the steep learning curve of the new system.

C. Visual Analytics Meets Interactive Evolutionary Algorithms

Interactive Evolutionary Computation describes evolutionary computational models where humans, via suitable user interfaces, play an active role, implicitly or explicitly, in evaluating the outputs evolved by the evolutionary computation. Applications of IEC are varied ranging from art to science [START_REF] Takagi | Interactive evolutionary computation : System optimisation based on human subjective evaluation[END_REF], [START_REF] Lutton | Evolution of fractal shapes for artists and designers[END_REF], [START_REF] Fukumoto | Extended interactive evolutionary computation using heart rate variability as fitness value for composing music chord progression[END_REF]. IEC lands itself very well to art applications such as for melody or graphic art generation where creativity is essential, due to the subjective nature of the fitness evaluation function. For scientific and engineering applications, IEC is interesting when the exact form of a more generalised fitness function is not known or is difficult to compute, say for producing a visual pattern that would interest a particular user. Here, the human visual system, together with the emotional and psychological responses of the user in question are far more superior than any pattern detection or learning algorithm.

Visual Analytics (VA) is a multidisciplinary field that integrates various sophisticated computational tools with innovative interactive techniques and visual representations to facilitate human interpretation of raw data [START_REF] Thomas | Illuminating the Path: The Research and Development Agenda for Visual Analytics[END_REF]. Thus, VA can provide both the depiction techniques and the exploration tools necessary to help the user better evaluate the output of interactive evolutionary algorithms. Beyond works on visualizing the IEC search space [START_REF] Hayashida | Visualized IEC: interactive evolutionary computation with multidimensional data visualization[END_REF], [START_REF] Llorà | Analyzing active interactive genetic algorithms using visual analytics[END_REF], to our knowledge, there has not been much work to marry efforts of the two communities; i.e. the VA and the IEC communities.

Moreover, despite efforts to design good user interfaces for IEC, human interaction with these systems, usually raises several problems, mainly linked to the "user bottleneck" [START_REF] Poli | Genetic programming with user-driven selection: Experiments on the evolution of algorithms for image enhancement[END_REF], human fatigue and slowness. Various solutions have been considered [START_REF] Banzhaf | Handbook of Evolutionary Computation[END_REF], [START_REF] Poli | Genetic programming with user-driven selection: Experiments on the evolution of algorithms for image enhancement[END_REF], [START_REF] Takagi | Interactive Evolutionary Computation: System Optimization Based on Human Subjective Evaluation[END_REF] to deal with this issue, let us mention:

• the reduction of the size of the population and the number of generations, i.e. running a micro-EA, • the use of specific models to constrain the research in a priori "interesting" areas of the search space, • the use of a approximate user model (based on a limited number of characteristic quantities) that is used to filter obvious bad solutions and only present to the user the most interesting individuals of the population. The model can be learned, based on past interaction (see for instance [START_REF] Lutton | The fitness map scheme. application to interactive multifractal image denoising[END_REF]). In what follows, we have chosen to run a micro-EA, with a population size constrained by the dimensionality of the dataset. Genetic diversity is thus an important issue, for avoiding uniformisation of the population (premature convergence) as well as user disinterest or fatigue: the algorithm has been tuned to display a set of diverse solutions at each generation. We will also see below that a variety of interactions are available with EvoGraphDice (query selection, direct interaction with the genome, search space modification).

Multiple interactions with the evolutionary mechanisms have been proven to be very efficient in an artistic application [START_REF] Lutton | Evolution of fractal shapes for artists and designers[END_REF], these ideas have been adapted here to the multidimensional data exploration task.

III. THE EVOGRAPHDICE PROTOTYPE

We choose to run an Interactive EA on a population made of additional, compound dimensions, in order to match the structure of GraphDice that provides a variety of efficient and smooth visualization mechanisms.

A. Individual Initialization

The EA manipulates a population of dimensions of the same size to the number of variables in the data to be analysed (i.e. n individuals for n dimensions or variables).

Internally, the dimensions (i.e. the genomes) are represented as a linear combination of term, see [START_REF] Thomas | A visual analytics agenda[END_REF], that allow the representation of linear combinations as well as more complex combinations of dimensions.

y = n i=1 w i × term i + K, (1)
where term i is a mathematical expression containing the i-th variable of the dataset (noted as x i ). term i represents raw, quadratic, logarithm, or exponential of x i (x i , x 2 i , log(x i ), e xi , respectively) or a combination of these expression (for instance x i × log(x i )). The w i refers to the weight of the term i and K is a constant. term i and K are real values.

The initial dimensions proposed by the EA should be interesting to the users in order to motivate them to explore the new alternatives. It was assumed that interesting solutions should show relations among variables which are not evident in the original data.

In order to generate the initial dimensions, a PCA analysis [START_REF] Smith | A tutorial on principal component analysis[END_REF] is performed on the original data. Thus, the n linear dependencies found by PCA conform the initial EA population.

These solutions are showed in EvoGraphDice as additional dimensions in the scatter plot matrix. Fig. 1(a) shows and example of the new dimensions suggested. Each dimension y i found by the EA correspond to the n+i-th row and column of the scatter plot matrix. The additional n rows and columns are color highlighted in order to distinguish them from the ones belonging to the original data.

B. Fitness Evaluation

Evaluating the fitness of the suggested visualization requires taking into account user interactions and internal metrics. The user interaction criterion tries to adapt user preferences in the fitness function while the internal metrics evaluate the relations between variables. We use four criteria to build the fitness of each solutions: number of clicks, variance, complexity and significance.

All the interactions of the user with the SPLOM, both with the original dimensions (x i ) and the suggested ones (y i ), are recorded. Each time the user clicks on a cell of the scatter plot, the click counter of the corresponding original dimension (denoted by f req(x i )) or additional dimension (denoted by nclicks(y i )) is increased. These values are then normalized between 0 and 1.

The variance criterion, denoted by vc(y i ), is based on the variance of the new dimension, as follows:

vc(y i ) = 1 1 + V ar(y i ) , (2)
where V ar(y i ) is the variance of the dimension y i . The term vc(y i ) will prefer individuals with lesser variance and will mitigate the effects when working with variables of different scales. The criterion vc(y i ) is intended to favour individuals (compound dimensions) that depict a dependency, i.e. corresponding to an approximation of an equation like

y i = constant
The complexity criterion, denoted by comp(y i ), is related to the number of variables being represented in the genome:

comp(y i ) = n j=1 comp j (y i ) n , comp j (y i ) = 1, w j = 0 0, otherwise (3)
Finally, the significance criterion, denoted by sig(y i ), is the sum of the frequencies of the variables that are represented in the terms of y i , as can be seen in. (4):

sig(y

i ) = n j=1 sig j (y i ), sig j (y i ) = f req(x j ), w j = 0 0, otherwise (4)
The fitness of an individual results from the weighted sum of the four criteria described above as showed in (5):

f it(y i ) = W 1 × nclicks(y i ) + W 2 × vc(y i ) +W 3 × (1 -comp(y i )) + W 4 × sig(y i ) (5)
where the default weights of each criterion (W i , i = 1 . . . 4) are set to 1, although they can be adjusted by the user. The interactive part of the fitness function (significance sig(y i ) and number of clicks nclicks(y i )) rely on the hypothesis that the number of clicks on the cells are proportional to the interest of the user. This is of course a strong assumption, as the user may click for various reasons on a given cell other than for data exploration. Our experiments show that our current scheme is able to capture a reasonable approximation of the user's interest, enough to guide the evolution of the IEA.

New individuals are generated by tournament selection, barycentric crossover and Gaussian mutation. Additionally, a mutation that reduces the complexity of the expression is used: if the weight w i of the i-the term is less than a weight threshold, w i is set to zero. This way, an additional pressure toward low complexity individual is added.

C. Preserving Diversity

As the proposed EA deals with small population, the loss of diversity of solutions should be avoided. Each time a new dimension y i generated, the following conditions should satisfied:

• the distance between y i and all the individuals of the current population y i , i = 1 . . . n should be greater than a threshold. We use the Euclidean distance between the weights of the y i terms and the weights from the y i terms.

• the variance of the new individual is smaller than at least one of the individuals of the previous population.

While the first condition is important to maintain the diversity of the population, the latter condition allows to introduce new individuals with lower variance. If no solution satisfies these conditions, a random individual is generated. This operation is repeated, until λ new individuals replace the worst solutions of the previous population.

D. EvoGraphDice User Interface

EvoGraphDice also displays the current population as a table in a new window, see Fig. 1(g). Each line of this table corresponds to a compound dimension displayed in the SPLOM, columns give the identifier of the dimension (a number), a binary template that shows which primal dimension is used in the compound, the mathematical expression, the four fitness components (number of clicks, variance, complexity and significance) and the resulting fitness of each individual. The user can trigger an iteration of the algorithm ("Suggest new dimensions" button), configure the EA parameters ("Configure EA" button), restart the EA with a PCA analysis ("Restart EA with PCA" button), edit and alter any dimension ("Edit dimension" button) and replace the current dimension by a random one ("Replace by Random" button).

Dimensions can be edited using a simple expression builder window as showed in Fig. 2. The term expressions, their corresponding weights and the numerical constant can be changed at any time during EA execution. Moreover, EvoGraphDice allows to fully configure the relevant EA parameters as showed in Fig. 1(h). These parameters are:

• crossover rate and mutation rate, that sets the probabilities for the barycentric crossover, the Gaussian mutation and reduce complexity mutation operators, • replacement rate, that refers to the proportion of individuals to be replaced at each EA iteration, • fitness threshold, that corresponds to the minimal fitness difference between two individuals of the population. The individuals of a population are sorted according to their fitness. If the fitness difference between two successive individuals is smaller than the fitness threshold, both individuals are considered as equal. Then, the complexity of the two individuals are compared and the less complex one is ranked first, • weight threshold, that defines the threshold under which the value of weights is set to 0, when applying the complexity reduction mutation, • sigma parameter, the σ parameter of the Gaussian mutation, • fitness criteria weights, that allow to tune the weights of each criterion (W 1 , W 2 , W 3 , and W 4 ), • search variable and dimension space, whose options are used to edit the expression associated to each variable. For instance, the user can associate the expression x 2 i to the variable x i such that all the individuals generated will have this term for the variable x i . Moreover, the user can restrict the search to a subset of variable so the dimensions will contain only terms associated to the relevant variables, • work with query values, that is used to restrict the set of points of the scatter plot on which the fitness is calculated.

The search can thus be performed only on a subset of the data corresponding to a query set by the user. Finally, the user can store the dimensions he feels are noteworthy or interesting in an "album" (the favorite cells widget, see Fig. 1(f). These dimensions can be re-inserted in the population at any time.

IV. EXAMPLE OF USE ON SAMPLE DATASETS

A. Visualization of a synthetic dataset

A first experiment has been run on a synthetic dataset, in which an interesting dependency has been set explicitly. The aim is to verify if the system is able to emerge dimensions that make the known dependency visually obvious.

The data set is made of 100 points in 6 dimensions, the first 5 dimensions have been randomly generated in the interval [-1, 1] with a uniform distribution, the 6th dimension is generated according to the following equation :

x 5 = exp(x 0 ) + exp(x 1 ) -x 2 (6)
We thus have an artificial dataset that has two fully random dimensions (x 3 and x 4 ) and four dimensions that are linked by the above formula. This non-linear formula has been chosen on purpose, as linear dependencies would have been immediately found by the PCA initialization.

The initial state of Fig. 4 provides a PCA analysis, where no interesting feature is visible, even in the first compound dimension (tagged "1"), that corresponds to the lowest variance principal component. The population content is presented on Fig. 3.

Using our a priori knowledge on the dataset, we can decide to restrict the search space to compound dimensions that involves x 0 and x 1 as exponentials (see Fig. 8). Then in a dozen of generations, we get a dimension that resembles to the x 5 line of the scatter plot matrix (see Fig. 6). Fig. 5 shows that a dimension (the "1" dimension) has been evolved, making the dependency between x 0 , x 1 , x 2 and x 5 visually obvious. For comparison, Fig. 7 has been generated by artificially introducing the true dependency formula in the population.

B. Visualization of a real dataset

A second experiment has been ran on a real dataset 3 , that represents simulation results of an aircraft model. In the dataset, displayed on Figs. 9-11, the 4 first parameters are input parameters (surf , phi0, alt, and Coef-Fuel) and the 9 left are output parameters. There are some obvious dependencies that are visible directly on the plain parameter view, like between phi0 and Cz-buf (see Fig. 1-b), and that exhibit two regimes (the dependency is linear by parts).

Our partner engineers are however interested in the behavior of parameters settings corresponding to Pareto frontiers, like 3 Dataset courtesy of Dassault Systems (CSDL project partner).

for instance on Fig. 11 for compromises that minimise BF L while maximising the Range parameter.

A first query has thus been sculpted on data corresponding to this Pareto set (in red on Fig. 11): it is used to restrict the fitness calculation. Additionally, the search has been restricted to formulas involving entry dimensions (surf , phi0, alt, and Coef-Fuel). The idea is to try to find if there may exist an approximative linear representation of the points of the Pareto front.

After a few experiments and a number of observations on the data, it has been noticed that a second query for low altitude points (alt < 3900, in green), that yields by intersection a of the previous Pareto front for low altitude, was enough to evolve in a few generations a dimension that provides a view where green points are aligned (see Fig. 9).

In this process, the red points have been used for the computed evaluation (with the aim of minising the variance), and the green ones are used for visual evaluation. A setting in GraphDice allows visualizing only the points of a query, via a transparency tuning for the unselected point (green points on Fig. 9). Fig. 10 gives the same view with all the points of the dataset, the Pareto front is in black.

V. CONCLUSION AND FUTURE WORK

The EvoGraphDice prototype has been experimentally shown to be able to evolve characteristics that are not visible in views based on the primary set of dimension (upper left quartile of the SPLOM matrix, see for instance Fig. 1), thus successfully fulfilling the main objective of this work. Additionally, no user-fatigue effects were reported during the experimental analysis, our intuition is that the variety of user interaction possibilities offered by GraphDice (i.e. not only related to the IEA process) is enough to maintain a good level of attention from the user.

A more precise evaluation of the added value due to interactive evolution will evidently need precise user-studies and statistical analysis. We intend to do this for future developments of the prototype. User-studies are important, no only for evaluation purposes but also to inform the default tuning of the internal parameters and strategies. The EvoGraphDice prototype is still in a preliminary stage; we currently propose ad-hoc tuning and give free access to parameter settings. Ideally, when addressed to people who do not currently practice EA, the system will need robust parameter settings, hidden away from the user. Decisions on default settings will be made on the basis of specific user studies focused on well defined characteristics, for instance, speed of emergence of an interesting view and diversity preservation.

Future developments of EvoGraphDice will also consider the following issues:

• preliminary experiments have shown the potential benefit of a more sophisticated encoding of compound dimensions: we intend to develop the next prototype on the basis of a Genetic Programming engine, in order to be able to smoothly evolve linear and non-linear compound dimensions within a single population, • For the current version of EvoGraphDice we chose the number of mouse clicks as our metric for characterising user interest. We accounted for clicks on the SPLOM that result in a transition between views. Thus this metric corresponds more precisely to the number of times a cell was visited during an exploration session. Other metrics have been proposed in the literature; for example, in the context of web page browsing Claypool et al. [START_REF] Claypool | Implicit interest indicators[END_REF] found that visiting time was a good indicator of user's interest. We intend to carry out a user study to compare various implicit interest indicators with explicit user ratings in the context of visual analytics and multidimensional data exploration.

• the relationship between internal (computed) fitness and interactive fitness (capture of interaction events like mouse clicks) may be based on a learning step, in the same way as in [START_REF] Lutton | The fitness map scheme. application to interactive multifractal image denoising[END_REF], in order to be able to manipulate a large population, while displaying for interactive evaluation only the best individuals, • engineer end-users were frustrated by the lack of an output interface, for instance with MatLab or SciLab, in order to be able to re-use the evolved dimension formulas, or to use the data subsets built by an interactive query. This function will be integrated in a future version of EvoGraphDice.

Fig. 1 .

 1 Fig. 1. EvoGraphDice prototype showing an exploration session of an aircraft simulation dataset: new extensions to the GraphDice system are indicated by coloured label arrows. (a) an overview scatter plot matrix showing the original data set of 13 dimensions and 13 new dimensions (numbered 1 to 13) as suggested by the evolutionary algorithm. (b) main plot view showing a linear correlation between two dimensions (weight and affinity) and a selected subset of points in red. (c) the selection history tool. (d) selection query window. (f) toolbar with "favourite" toggle button. (f) favourite cells manager stores interesting scatter plots. The user can bring a favourite cell back into the overview matrix. (g) the evolutionary algorithm main control window. (h) advanced configuration options for the evolutionary algorithm.

Fig. 2 .

 2 Fig. 2. EvoGraphDice suggestion dimension builder.

Fig. 4 .

 4 Fig. 4. Experiment with synthetic data : initial state.

Fig. 3 .

 3 Fig. 3. Initial population content.

Fig. 5 .

 5 Fig. 5. Population content after a dozen of generations.

Fig. 6 .

 6 Fig. 6. Evolved state after a dozen of generations. Fig. 7. Verification: visualization of the true formula by interactive modification of a genome.

Fig. 8 . 1 Fig. 9 .

 819 Fig. 8. Restriction of the search space to exponential values for x 0 and x 1

Fig. 10 .

 10 Fig. 10. Zoom on the evolved view : the black points are the one of the BF L-Range Pareto set (Fig. 11).

Fig. 11 .

 11 Fig. 11. Primary query, used for the calculation of the internal fitness: selection of the non-dominated points on the BLF -Range view.

http://www.teratec.eu/activites/projetsR\ D\ Csdl.html

A demo of GraphDice can be launched from http://www.aviz.fr/graphdice/, it accepts standard .csv files (although it may be necessary to add a second line after the header giving the data type for each column -INT, STR, REAL, etc).

ACKNOWLEDGMENT

The authors would like to thank Michel Ravachol, from the Dassault Aviation company, for providing the dataset used in section IV-B , for his kind help, and fruitful discussions. We would also like to thank Jean-Daniel Fekete and Anastasia Bezerianos for their useful feedback and discussions.


Dominique Guégan
email: dguegan@univ-paris1.fr.

Dr Bertrand K Hassani
email: bertrand.hassani@malix.univ-paris1.fr.

Operational risk: A Basel II++ step before Basel III

Keywords:

Following the Banking Committee on Banking Supervision, operational risk quantification is based on the Basel matrix which enables sorting incidents. In this paper we analyze these incidents in depth and propose strategies for carrying out the supervisory guidelines proposed by the regulators. The objectives are as follows:

• On the first hand, banks need to provide a univariate capital charge for each cell of the Basel matrix. That requires constructing Loss Distribution Functions (LDFs), which implies estimating a frequency and a severity distribution. We show that the choice of the theoretical distributions to build the LDFs has a tremendous impact on the capital charges, especially if we do not take into account extreme losses.

• On the other hand, banks also need to provide a global capital charge corresponding to the whole matrix. We highlight that a lack of consideration or a poor appreciation of the dependence structure may lead to incorrect capital charges.

• Finally, we draw the attention of regulators and managers to two crucial points:

1. The necessity of splitting information sets in two parts while adjusting the severity distribution. The first covering small and medium losses, and the latter containing extreme losses (this point implies problems of granularity mentioned in the last Basel II guidelines), 2. The choice of the risk measure which provides the capital amount. We emphasize that the expected shortfall measure enables a better anticipation of large incidents pertaining to operational risks.

Introduction

In 2001, the Basel Committee on Banking Supervision provided a set of principles [START_REF] Bcbs | Working paper on the regulatory treatment of operational risk[END_REF] for the effective management and supervision of operational risks, designed for banks and domestic authorities. According to these principles, banks could either use a basic, standard or advanced approach to calculate their capital charges. The last approach known as advanced measurement approach (AMA) requires banks to develop internal models.

However, at that time, operational risks management was a very young topic and due to its absence in the Basel I accords [START_REF] Bcbs | Basel committee: International convergence of capital measurement and capital standards[END_REF], the level of maturity was not the same as for credit risk.

Therefore, Basel II initial requirements were very brief. They bound banks and financial institutions to use internal and external data, scenarios and qualitative criteria. They required banks to compute capital charges on a yearly basis and at a "99.9% confidence level". Therefore, at this time domestic authorities had no real experience of what would be a good approach to model the operational risks.

It was only after banks initial attempt to comply with the regulatory requirements that the BCBS started to be more precise on the kind of models they where expecting ( [START_REF] Bcbs | International convergence of capital measurement and capital standards[END_REF][START_REF] Bcbs | Observed range of practice in key elements of advanced measurement approach (ama)[END_REF][START_REF] Bcbs | Basel iii: A global regulatory framework for more resilient banks and banking systems[END_REF]). New proposals have been done, they correspond to what we could refer to as Basel II++ principles which have to be monitored by the banks for the next few years. The purpose of this article is to analyse the effects of these Basel II principles, to discuss the strategy before the deployment of the next Basel system and to anticipate the applications of these new principles with respect to the data on which these principles have been applied. The results presented in this paper have been obtained using Caisse d'Epargne data sets (2006)(2007)(2008)(2009)(2010), except the results presented in Table 2, which have been obtained on a Banques Populaires data set (2008-2010) 1 .

Initial principles in Basel II proposals

In the second part of the 80's when the regulators decided to establish rules to strengthen the banking system there was nothing concerning operational risks. It was only in 2001 that supervisors and the banking industry recognized the importance of operational risk in shaping 1 The data sets used in this paper were sampled from Bertrand HASSANI's PhD thesis financed by BPCE.

the risk profile of financial institutions. Thus, the Basel Committee on Banking Supervision in their first Pillar about minimum regulatory capital charge for risks, required banks to take into account operational risks. As a result the Risk Management Group of the Basel Committee introduced a new regulatory capital approach based on banks' internal risk estimates called the "Advanced Measurement Approach" (AMA). The principle of this regulatory capital charge for operational risks was based on the following definition of operational risk: "the risk of loss resulting from inadequate or failed internal processes, people and systems or from external events". This definition includes legal risks, but not the strategic, reputational or systemic risks. At the time, the biggest challenge in applying the recommended guidelines stood in collecting and analysing loss data sets, because this assumed efficient risk management devices and materials.

Collection system have been deployed in the past ten years. In this paper we will further discuss data collection (in particular the granularity issue) and organisation as part of calculating the minimum regulatory capital charge required from banks and insurance companies, in particular the problem of granularity.

The first Pillar proposal was established in close collaboration with the banking industry. It categorised operational risk exposures and losses into a series of standardised business lines and events types. Table 1 provides an example of the matrix on which the supervisor worked to provide the notorious capital requirement. This matrix was likely responsible for errors in the calculation of the capital requirement due to the excessive aggregation of the data collected. This was reflected in the guidelines for future Basel accords, and we will show in this paper the impact of the level of granularity of matrix and the importance of taking heed of this point.

We mentioned earlier data collection specific to AMA to evaluate capital charges, which lead to inquest another problem concerning the regulatory capital. The Committees's preliminary assessments of the possible level of operational risk regulatory capital was 20% of the current regulatory capital (CRM). Practitioners thought that a 20% figure should be lowered, and that 12% of minimum regulatory capital would provide a more reasonable cushion and produce required capital amounts more in line with the operational risks faced by large, complex banking organisations. However, it seems in reality that these first assesments (20% to 12%) were calibrated at a too low level. The first evaluation of operational risk capital requirements was used to define the Basic approach, and induced the weights of the standard approach. Since the banks' incentive to adopt the AMA was a 25% capital allocation reduction compared to the standard approach disregarding their risk profile, it produced a modelling bias. It could be argued that the capital reduction was driven by better risks management within the banks, which is not entirely false, nevertheless the inital lack of experience led to too low forfaitary capital charges which were used as a benchmark for the AMA. Besides, and we would like to emphasize this point, loss data sets (internal or external) are not used in the basic and the standard approach to compute capital requirements. The regulatory capital in those cases is evaluated as a fraction of the net banking income. Therefore, we cannot compare these approaches with the AMA. We

show with empirical studies the difficulty to assess a correct level of charges. Therefore, after suggesting higher risk levels for the basic and the standard approach, we provide conservative and accurate solutions to model operational risks. The choice of methodologies is crucial and we detail those evidences at different steps of the calibration process.

The basic tools: LDA and VaR

A traditional way to deal with operational risks is the Loss Distribution Approach (LDA) [START_REF] Frachot | Loss distribution approach for operational risk[END_REF].

This aims at building a Loss Distribution Function (LDF) ( [START_REF] Guégan | A modified panjer algorithm for operational risk capital computation[END_REF] for instance) G which is the mixture of a frequency distribution p(k) and a severity distribution F (x) (whose density is given by f ), thus

G = ∞ γ=1 p(k)F * γ (x), x > 0, G b,e = 0, x = 0, (1.1)
where * denotes the convolution operator and F * γ the γ-fold convolution of F with itself. We denote g the density of G, and

g = ∞ k=γ p(k)f * γ (x), x > 0. (1.2)
Experts working on operational risks agree on the fact that the frequency distribution has a negligible impact on the LDF's quantile which provides in fine the regulatory capital. However, the choice of the severity distribution has a tremendous impact on this because it is the most pertinent information in terms of level of loss. The capital charge pertaining to G is obtained, at the request of the regulators, through a 99.9% Value-at-Risk (VaR) -a quantile computed from this LDF. We recall now the definition of the VaR measure, Definition 1.1. Given a confidence level α ∈ [0, 1], the VaR associated to a random variable X is given by the smallest number x such that the probability that X exceeds x is not larger than

(1 -α) V aR (1-α)% = inf(x ∈ R : P (X > x) ≤ (1 -α)). (1.3)
Here, the random variable X is associated to a cell of the Basel matrix (Table 1). To compute P (X > x) we need to determine the LDF associated with this random variable, thus the choice of the severity distribution which constitutes this LDF will have a tremendous impact on the final capital allocation. The table presents very poor goodness-of-fit tests results. In this case it is not possible to state which distribution is better than the others. The fifth column presents the capital charges we would have using these distributions, and the sixth the Expected Shortfall. These results are compared to 95% confidence level risk measures.

For instance to model the severities of a sample representing the External Fraud event on the Retail Banking business line, we have fitted by maximum likelihood estimation and tested the following distributions (for which we provide the densities in appendix B): the lognormal distribution, the Weibull distribution, the Gumbel distribution, the Generalized Pareto distribution (GPD) [START_REF] Pickands | Statistical inference using extreme order statistics[END_REF][START_REF] Embrechts | Modelling Extremal Events: for Insurance and Finance[END_REF], the GB2 distribution ( [START_REF] Gupta | Handbook of Beta Distribution and Its Applications[END_REF], [START_REF] Rigby | Generalized additive models for location, scale and shape,(with discussion)[END_REF]), and the g-and-h distribution ( [START_REF] Hoaglin | Summarizing shape numerically: the g-and-h distributions[END_REF], [START_REF] Buch-Kroman | Comparison of tail performance of the champernowne transformed kernel density estimator, the generalized pareto distribution and the g-and-h distribution[END_REF]). For the choosen sample, we provide, for each distribution the corresponding capital requirement computed using the 95% and 99.9% Value-at-Risk (VaR) introduced in (1.3). The second column of Table 2 provides the result of an adequacy test based on the Kolmogorov-Smirnov distance to check the quality of the fit of these statistical distributions to the data sets. They all failed, thus statistically we cannot accept any of these distributions. Nevertheless if we continue the exercise 2 columms 3 and 5 contain the capital computed using the VaR for two values of α.

Colums 4 and 6 exhibit the capital requirements that the banks need if we use another measure named Expected Shortfall given by (3.1). Looking at these four columns we observe that the choice of the distribution has a tremendous impact on the capital allocation. Thus at this point, there is a trade-off between the choice of a distribution that minimises the capital allocation (here the Gumbel one), or a distribution which provides a more conservative capital (here the GB2). We also observe large differences with respect to the choice of the so-called risk measure.

Thus, besides the calibration problem, the choice of risk measure is crucial. We will now expand these points more in details.

In the first part of section 2, we will discuss estimation of the LDF for each cell of the matrix, and provide the corresponding regulatory capital with respect to the corresponding LDF and the chosen risk measure. In section 3 we introduce a dependence structure between the cells, and for the different risk measures we will produce several capital charges. Finally the last section concludes with some important remarks focusing on the impact of the distribution families, the parameter estimation procedures and the risk measures on the regulatory capital. To complete our analysis, Appendixes provide statistics of the data sets used (Appendix A), exact densities of the distribution considered in this paper (Appendix B) and a comparison of estimation methods for the GPD parameters (Appendix C).

Estimation of the severities in each cell: the importance of the tail distribution

Before providing a capital associated with the global matrix, we need to analyse the behavior of each cell. We need to know the correct distribution that characterizes each cell. It is now recognised that for a proper statistical adjustment of the severity distribution, we must take into account the existence of extreme values in the analysis of the loss data sets (Table 2). There are 2 To continue this exercise is not unrealistic as soon as severity distributions like the lognormal distribution is commonly used in banks to compute the LDF several approaches to consider which are all part of the extreme value theory [START_REF] Leadbetter | Extremal theory for stochastic processes[END_REF]. Following this theory in a recent paper, we have proposed a flexible approach [START_REF] Guégan | A efficient peak-over-threshold implementation for operational risk capital computation[END_REF] to model the severity distributions. Our approach is a mixture of two distributions: one characterizing the most important losses (the tail) using the Generalized Pareto Distribution (GPD), and the latter modelling the remaining data (the central part of the distribution or corpus). We used a GPD on the right tail for which we provided innovative theoretical and practical solutions, and fit a lognormal3 distribution on the remaining data via an EM algorithm. Figure 1 illustrates the approach. Then, to build the final LDF, we applied an adapted Monte Carlo algorithm. Once the threshold of the GPD has been found, the method chosen to estimate GPD's parameters tremendously impacts the VaR: it seems that the influence of the estimation procedure on the computation of the capital allocation has never been discussed before and we provide some details in Appendix C.

The estimation procedure for the GPD we selected in this paper is based on the maximization of the Anderson-Darling statistic [START_REF] Luceno | Fitting the generalized pareto distribution to data using maximum goodness-offit estimators[END_REF].

Thus, we define the severity distribution as a mixture of a lognormal distribution on the corpus, and a GPD on the right tail (cauda,) whose density f (x; u, β, ξ) is :

f (x; u, β, ξ, µ, σ) =      f (corpus) (x; µ, σ), if x < u f (cauda) = 1 1- u 0 f (center) (x;µ,σ)dx × f GP D (x; u, β, ξ)), if x ≥ u , ( 2.1)
where, µ and σ are the lognormal distribution parameters, and f GP D the density of the GPD given in Appendix B.

In Table 3, we provide the capital requirements computed using different distributions for the cell associated with the business line "Payment & Settlement" and the event type "Delivery, Execution and Process Management" for the year 2006. We observed that by using the lognormal distribution only provides a very less conservative regulatory capital than using the POT method we introduced above. Note that when we adjusted only a GPD on the data set, we did not obtain workable results because either the parameters could not be properly estimated, or we faced an infinite mean model (ξ > 1). for the year 2006, comparing different hypothesis for the severity distribution. We cannot provide a GPD estimation on the whole data set as the shape parameter is superior to 1, and therefore we face an infinite mean model.

POT method implementation

We also observed large amount differences with respect to the choice of the risk measure: the VaR or the ES. This is discussed in more detail below.

Capital charge associated with a coherent risk measure

The regulator imposed a confidence level of 99.9% for the capital charge, therefore if we use the VaR measure, we have α = 0.1% in (1.3). Nevertheless, using this risk measure, we face several problems, especially while computing a global capital charge. Indeed, the sum of the VaRs may be lower than the VaR of the sum i.e. the VaR is known not to be subadditive, and the result is questionnable as soon as several loss distributions are aggregated. On the other hand, this measure -by definition-does not take into account the large losses. However, the Conditional VAR (CVaR) or Expected Shortfall (ES) is a coherent measure [START_REF] Artzner | Coherent measures of risk[END_REF] and therefore it is more appropriate to work with it. We recall its definition:

Definition 3.1. For a given α in [0, 1], η the V aR (1-α)%
, and X a random variable which represents losses during a prespecified period (such as a day, a week, or some other chosen time period) then,

ES (1-α)% = E(X|X > η) (3.1)
The ES measure which is subadditive takes into account the information contained in the distribution tail contrary to the VaR measure. Therefore, some extremal event exposures are captured by the ES measure. However in practice the ES value may be much higher than the corresponding VaR value, therefore, a lower confidence level could be used when considering the ES measure compared to the VaR measure.

As illustrated in Table 2, it might be judicious to use a GB2 distribution to model the severity and to compute a 95% ES than to use a lognormal distribution at a 99.9% VaR. Thus, we see that, to take into account very large losses, it could be more appropriate to associate at the same time the use of extreme distributions and the ES measure. In this case the result is closer to reality, and more effective to help banks understanding extremal events and by the way preventing them. In Tables 2 and3, we illustrate these facts. We observed a large difference between the capital computed with the VaR and the ES measures. Thus, a trade-off between a VaR at 99.9% and an ES at 95% should be considered .

In these two tables we have seen the impact of the choice of risk measure on the capital computation. Now this impact can also be illustrated if we study the composition of the matrix and its granularity. Indeed, until now we used collected data organised into the Basel Matrix [START_REF] Bcbs | Working paper on the regulatory treatment of operational risk[END_REF]. The first level of granularity is made up of 56 cases -8 business lines ("b") × 7 event types ("e") 4 .

Nevertheless, each event type might be further broken down into several elements. For example, the "external fraud" event may be shared in two items -"Theft and Fraud" and "Systems Security" (second level of granularity). In a third level, the element "Theft and Fraud" may be split in several components: "Theft/Robbery", "Forgery" and "Check kiting". After a deep analysis, we observe that the kind of losses expected from a fraud with a credit card does not correspond to losses caused by someone hacking the system for instance. Nevertheless these two different kinds of losses are in the same cell. Therefore, considering the largest level of granularity, we could face multimodal empirical distributions. Consequently, the methods used to model the losses depend on the choice of granularity of the Basel matrix. This choice might have a tremendous impact on capital requirement computations. Besides, there is a trade-off between the quantity of data and the robustness of the estimations. Indeed, if the quantity of data is not sufficient, we cannot go to a more granular level; on the other hand the empirical distribution is therefore an aggregate of various types of data and the estimation of this last empirical distribution can be source of unusable results.

For the moment, we cannot empirically illustrate these remarks because we do not have the appropriate information set. Nevertheless it seems reasonable, in order to be close to reality, to introduce the computation of the distributions associated to the second or even third level of data granularity in order not to bias the LDF, as long as this information exists.

Influence of the dependence structure between the cells on the regulatory capital computation

Banks need to have in fine an amount calculated using the global matrix. This means that, as soon as the LDFs have been determined for each cell, the next question is the best way to combine these distributions to provide a global regulatory capital i.e. corresponding to the whole matrix.

Traditionally the experts computed the global capital requirement summing the capital calculated in each cell. This procedure does not take into account the true dependence which exists within the cells. One way to bypass this problem is to use a copula distribution which is a multivariate distribution permitting to link a huge number of distributions. During recent years some experts used the Gaussian copula to take these dependences into account, claiming inability to perform calculations using other copulas in high dimensions. The well-known Gaussian structure is not adapted to loss data sets (indeed, the Gaussian structure is elliptical, and does not capture tail dependence), and since 2005 it is now possible to work with copulas in high dimensions using nested copulas or vines [START_REF] Aas | Pair copula constructions of multiple dependence[END_REF]. Recently, we used this last methodology and adapted it to compute the capital requirement associated with operational risks in high dimensions [START_REF] Guégan | n-dimensional copula contributions to multivariate operational risk capital computations[END_REF].

Extending this work the main improvements for practitioners are the following:

• Firstly, this methodology enables the use of numerous classes of copulas without restricting to the elliptic domain. One can consider copulas which focus on information contained in the tails, where we find the large losses.

• Secondly, this approach allows several combinations of margins (corresponding to the dis-tributions computed for each cell) to derive robust adjustments in the statistical sense.

• Thirdly, even working in the highest dimension, the procedure is easy to implement and is not too time consuming.

• Finally, this method complies with the lastest Basel Committee [START_REF] Bcbs | Basel iii: A global regulatory framework for more resilient banks and banking systems[END_REF] requirements.

Below, the results obtained considering several cells of the Basel matrix5 are provided. In Table 4 we introduce some notations corresponding to the losses we have studied. ) and (F 3 , F 6 , F 7 , F 10 ) as single data sets. In this case, our aggregation is "Business Line" oriented (Table 1).

BUSINESS

In a first exercise, we show how to compute the amount corresponding to these four cells. The diagram is provided in Figure 2. We begin by estimating the margins associated with the cells B 1 , B 2 , B 3 and B 4 . Thus, in a first step, we link the couples (B 1 , B 2 ), (B 1 , B 4 ) and (B 3 , B 4 ) with a copula whose parameter is estimated by maximum likelihood (and sense checked using the Kendall τ ). In a second step we link the copulas previously obtained by other copulas and so on. The choice of the cells to find the copula results from a sharp analysis of the data sets (cells). Nevertheless, some statistical studies enabling the decision of which links are appropriate can be found in ( [START_REF] Guégan | New prospects on vines[END_REF] and [START_REF] Guégan | n-dimensional copula contributions to multivariate operational risk capital computations[END_REF]). In Table 5 we provide the amount computed using VaR and ES measures. The results given in the first line correspond to the global amounts obtained summing the VaR provided by the four margins B 1 , ..., B 4 , considering different distributions to model the severities: 1 corresponds to a non parametric estimation procedure, 2 corresponds to the lognormal distribution estimated and 3 corresponds to the Gumbel adjustment. In the second line we provide the results obtained linking the marginal distributions with the Gumbel copula with a parameter θ = 5.34 obtained applying the previous vine methodology presented above; 1, 2 and 3 correspond to the same distributions for the margins as before. Looking at the third column we observe that we do not have the same amount if we sum the four cells (methodology based on a univariate approach) or if we use a copula methodology. The capital charges are very similar, but bigger in the first case.

C 1234 (C 124 , C 134 ) C 124 (C 12 , C 14 ) C 134 (C 14 , C 34 ) C 12 (B 1 , B 2 ) C 14 (B 1 , B 4 ) C 34 (B 3 , B 4 ) B 2 B 1 B 4 B 3
As a result, not taking into account the dependencies at all may lead to over conservative capital charges, even more conservative than using an extreme value copula (for instance a Gumbel one). The similar results between the two aggregation methodologies is a coincidence due to the fact that a simple sum of high quantiles (VaR) intuitively implies a strong dependence of large losses and the Gumbel copula we obtained mimics this behaviour. If we compare the third and the fourth column we observe that the capital charges are always bigger using the ES measure:

this confirms comments made previously. When a Gumbel distribution is used on the margins, the two methods are competitive, indeed, the results are nearly similar. The use of lognormal distribution provides more conservative results. The use of nonparametric modelling provides a value between the two previous situations. It seems to us that obtaining a very good fit on the margins is conducive with providing a realistic amount of capital. The modelling of the margins can be more influential than the fit of the copula, nevertheless, using upper tail dependence copula structures allows a more conservative capital charge for banks. the lognormal approach and 3 the Gumbel one.) and two classes of dependence. Univariate corresponds to the VaRs sum of each LDF. The alternative corresponds to an aggregation using a Gumbel copula.

C 1234 (B 1 ,B 2 ,B
We now propose another exercise. In Table 1 we consider the cell F 9 corresponding to Business

Disruption & System Failure events in the Retail Banking business unit and the distribution associated to the cell F 6 characterizing the same events in the Payment & Settlement business unit. For the distribution F 9 we estimate a Gumbel distribution or a lognormal distribution, for the distribution F 6 we estimate a Generalized Pareto distribution (GPD) or a lognormal distribution. Tables 6 and7 provide the capital values when we link these two distributions with a Gumbel copula on one hand and with a Clayton copula on another hand. In columns 4 and 5

we provide the capital computed using the VaR and the ES measures respectively. Columns 2 and 3 gives the amount corresponding to each cell obtained by projection from the fourth column.

The results of these tables show that depending on the way we model the margins, we have tremendous differences between the VaRs. For example, we would have a VaR equal to 117 207 402 euros if F 9 is modeled with a lognormal distribution and F 6 with a GPD distribution versus a VaR equal to 2 037 655 euros if F 9 is modeled with a lognormal distribution and F 6 with a Gumbel one. Depending on the way we model the LDFs, the aggregated VaR may be multiplied by 57.52. The same behavior is observable when we project the corresponding values on the cells. For example, the multivariate VaR projection on F 9 is e 2 655 055 if F 6 is modeled using a lognormal distribution, and is equal to e 15 405 192 if F 6 is modeled using a GPD distribution.

The peak for the VaR observed in that latter case is due to the capture of extreme events through the choice of the margins: the Gumbel one. Finally, using at the same time copula and severity distributions, which take into account information in the tail, provides very accurate results.

Indeed, when we model F 6 using a GPD associated with a Gumbel copula, we provide a larger VaR than with the Clayton one. The differences are observed comparing the amounts e 105 422 356 with e 103 249 260 on the one hand, and e 117 207 402 with e 107 807 238 on the other.

In Table 6 we see that the capital requirements obtained using a Gumbel copula are bigger than those obtained with a Clayton one, thus the choice of the dependence structure also has an impact on the computation of the capital charges. Now, if we use the VaR measure the difference is not significant for a bank (columns 4 in Tables 6 and7), but if we compare the results obtained with the ES measure (columns 5 in Tables 6 and7) the difference is tremendous (up to almost a billion euros). Nevertheless, choosing the ES measure at a 99.9% confidence level induces a much larger capital amount considering an upper tail depencence structure (Gumbel copula) than an lower tail dependence (Clayton copula). For instance, "Gumbel-GPD" means that we have chosen a Gumbel distribution to model F 9

Model

and a mix of a lognormal and a GPD to model F 6 .

Finally, another exercise allows us to see the influence of the dependence structure on the cells for which we need to know the capital allocation. Applying a vine approach, we obtained a Gumbel copula to model the dependence between several LDFs. Computing the corresponding multivariate VaR, we derived a global capital charge. In Table 11, we projected from the multivariate VaR given in column 7, the amount corresponding to each cell (axis). For example, for the second line corresponding to the "Retail Banking", we can provide the amounts pertaining independently to the "External Fraud", the "Clients, Products & Business Practices", the "Damage to Physical Assets" and the "Business Disruption & System Failures" event types (Table 1 line 3, column 2, 5, 8, 9). Our approach is interesting because it provides the capital for each cell through the dependence structure between the cells. This approach is totally different from the approach mainly used by practitioners who directly compute the capital associated with each cell without taking into account the information given by any other cell.

Table 11 highlights the fact that an upper tail dependence structure (line 3) always provides larger capital charges than the sum of the univariate VaRs. We can also say that the larger the tail of the theoretical distribution, the larger the gap between the ES and the VaR.

Conclusion: New Proposals

In this paper, we discussed a range of options for assessing Basel Pillar 1's capital charges for operational risk. We have expanded them and increased both reliability and precision in our considering three classes of severities (1 denotes the non parametric approach of the LDF, 2 the lognormal approach and 3 the Gumbel one.).

measurement, management and control of operational risks. As we had the opportunity to experiment the methods suggested in literature using real data sets, we found various drawbacks and pitfalls, and we proposed solutions to bypass them.

We suggested the use of a Peak-over-Threshold method to thicken the right tail of the loss distribution function. Presenting this solution, we suggested an efficient way to obtain generalized Pareto distribution parameters which is accurate regarding goodness-of-fit tests, and therefore compliant regarding the regulator. Furthermore, our methods have shown conservative results

and quantitatively supported the idea that some data sets might be badly built.

We provided an innovative solution to compute aggregated risk measures (VaR and ES), dealing with dependences between Basel categories. This solution is based on nested structures and vine architectures. Carrying out this methodology, we were able to take into account specific dependences (upper tail etc.) between many margins with Archimedean and extreme value copulas.

We also studied the sensitivity of multivariate VaRs to modeled LDFs (margins), to dependence architectures and to copulas parameters.

In addition of these results, we observed that estimating dynamically the parameter of the de-pendence structure creates important variations in the values of the Gumbel copula parameter.

We illustrated this fact in Table 9. We computed the parameter of the Gumbel copula linking the LDFs of the cells F 9 and F 6 . This parameter θ varied with respect to the information set used for its estimation. The parameters' value obtained using the year 2006, was different when we used the year 2007 or the year 2008, or the whole sample. We noticed that the upper tail dependence was larger when we used this last data set. This will have an impact on the computation of capital requirements. Thus, with the information set we use, the capital requirement appeared to be more or less conservative, and notion of dynamics inside the data needs to be taken into account. Therefore, we suggest to work dynamically and therefore measure the impact of the time passing on the distribution shapes. This idea led us to challenge the 5 years data sets required by the authorities. Indeed, these data sets may include outdated data -for example, a incident occurred in a department that does not exist anymore -or not old enough and some long memory process should be involved.

Last but not least, we suggested to compute capital charges considering another risk measure than the VaR measure, say the expected shortfall. This measure is coherent and also take into account the whole information contained in the tail. Computing a Capital allocation from a 99.9% ES is not realistic as it appears to be too conservative, but a lower critical threshold could be considered. For example one could consider a 95% ES instead of a 99.9% VaR (Table 2) as we illustrate in the previous exercises.

A Appendix: Distributions statistics

Next table provides the four first moments of the empirical severities corresponding to the cells of the Basel matrix (

B Appendix: Distributions for the severities

We provide the densities of the main severity distributions we used along this paper.

• lognormal distribution: • GB2 distribution ( [START_REF] Gupta | Handbook of Beta Distribution and Its Applications[END_REF], [START_REF] Rigby | Generalized additive models for location, scale and shape,(with discussion)[END_REF]):

f b,e (x; α, β, p, q) = αx αp-1

β αp B(p, q) 1 + x β p+q (B.5)
where α, β, p, q, x >, B(u, v) = Γ(u)Γ(v)Γ(u + v) is the Beta function, and Γ(.) is the Gamma function.

• g-and-h distribution ( [START_REF] Hoaglin | Summarizing shape numerically: the g-and-h distributions[END_REF], [START_REF] Buch-Kroman | Comparison of tail performance of the champernowne transformed kernel density estimator, the generalized pareto distribution and the g-and-h distribution[END_REF]):

f b,e (x; g, h) = exp ((g * x)-1) * exp when g = 0 and h = 0, the g-and-h distribution reduces to a standard normal distribution.

C Appendix: Influence of estimation methods on the amount of regulatory capital

We show the influence of the estimation procedures of GPD's parameters used in section 2 on capital requirements. Assuming a bootstrap method to estimate the threshold ( [START_REF] Hall | Using the bootstrap to estimate mean squared error and select smoothing parameter in nonparametric problems[END_REF], [START_REF] Danielsson | Using a bootstrap method to choose the sample fraction in tail index estimation[END_REF]), we estimate the remaining ξ and β parameters of the GPDs defined in (2.1) using the method introduced by [START_REF] Luceno | Fitting the generalized pareto distribution to data using maximum goodness-offit estimators[END_REF], denoting this method M1. We also consider three other alternative estimation methods to estimate these parameters in order to check their impact on VaR computations.

These ones are respectively the Pickands method (M2) [START_REF] Pickands | Statistical inference using extreme order statistics[END_REF], the Hill method (M3) [START_REF] Hill | A simple general approach to inference about the tail of a distribution[END_REF], and the Maximum Likelihood method (M4). We provide in Table 11 the estimations of GDPs parameters (with their standard deviation in brackets) obtained for both sets, using these four methods and the corresponding capital charges.

Note that a shape parameter ξ > 1 in ( for the year 2006, given estimations of the GPD's parameters ξ and β (Appendix B) using four methods for û = 179. M1 is the method introduced by Luceno [START_REF] Luceno | Fitting the generalized pareto distribution to data using maximum goodness-offit estimators[END_REF], M2 is the Pickands method, M3 is the Hill method, and M4 is the Maximum Likelihood method. We provide in brackets the standard deviations computed by bootstrapping. The third column gives the 99.9% VaR (regulatory capital allocation) pertaining to these estimates (µ = 3.593098, σ = 1.510882). The fourth column presents the corresponding expected shortfall capital value.

Figure 2 : 4 -

 24 Figure 2: 4-dimensional vine estimation to obtain the dependence structure for the whole Basel Matrix.

Table 9 :

 9 Parameter estimation of Gumbel copulas estimated on F 9 and F 6 for each year 2006, 2007 and 2008 (second column). These parameters are compared to a Gumbel copula parameter estimated on the entire time series (third column). The corresponding standard deviation are provided in brackets.

•

  0, µ ∈ R, σ ∈ R + * . Weibull distribution: f b,e (x; β, ξ) x > 0, β > 0, ξ > 0.• Gumbel distribution: f b,e (x; u, β) u ∈ R and β > 0.• Generalized Pareto distribution (GPD) ([START_REF] Pickands | Statistical inference using extreme order statistics[END_REF][START_REF] Embrechts | Modelling Extremal Events: for Insurance and Finance[END_REF]):f b,e (x; u, β, ξ) β > 0 and ξ = 0 (or f b,e (x; u, β, ξ) = 1 β -(x-ξ) β if u = 0).

Table 1 :

 1 Basel Matrix for operational risks: each cell represents Business line/event types classification. F

	(1) Internal Fraud (2) External Fraud (3) Employment Practices & (4) Clients, Products (5) Damage to Physical Assets (6) Business Disruption (7)Execution, Delivery	Workplace Safety & System Failures & Process Management & Business Practices				F1	F8 F5 F9 F2		F10 F6 F7 F3			F4
	BUSINESS LINES	LEVEL 1	(1) Corporate Finance	(including Municipal/Gov.t	Finance & merchant banking)	(2) Trading & Sales	(3) Retail Banking	(4) Commercial Banking	(5) Payment & Settlement	(6) Agency Services & Custody	(7) Asset Management	(8) Retail Brokerage
	BUSINESS	UNITS		INVESTMENT BANKING				BANKING			OTHERS

i , i ∈

[START_REF] Aas | Pair copula constructions of multiple dependence[END_REF][START_REF] Danielsson | Using a bootstrap method to choose the sample fraction in tail index estimation[END_REF]

denotes the distribution associated to each cell for which data is available.

Table 2 :

 2 Several theoretical distributions have been fitted from a data set representing the External Fraud events of the Retail Banking business line of the Banques Populaire perimeter.

	Severity distribution K-S test VaR (95%)	ES (95%)	VaR (99.9%)	ES (99.9%)
	Lognormal	<2.2 e-16 6 448 883	7 531 208	13 354 724	17 863 146
	Weibull	<2.2 e-16 4 081 999	4 204 917	4 530 362	4 631 586
	GPD	<2.2 e-16 33 512 000 192 902 521 1 009 472 708 4 865 819 191
	Gumbel	<2.2 e-16 4 247 871	4 336 857	4 597 061	4 669 047
	GB2	<2.2 e-16 9 321 772	19 497 566	76 326 374	253 422 675
	g-and-h	<2.2 e-16 6 030 146	6 289 353	6 940 614	7 231 981

Table 3 :

 3 Method Illustration: This figure presents the histogram (in grey) of the Historical LDF. The black line corresponds to a LDF mixing a Poisson and a lognormal distribution. The 99.9% quantile represnting the VaR is pointed out by ∆. The dash line represents a LDF mixing a Poisson distribution and a multiple pattern severity (lognormal-GPD). + indicates the location of the VaR. The right graph focuses on the right tail of the LDFs described above. This figure highlights the fact that this method enables thickening up the right tail of the LDF. We provide risk measures on the data set which represents the severity of the business line "Payment & Settlement" and the event type "Delivery, Execution and Process Management"

	Data

Table 4 :

 4

		BUSINESS LINES	Loss Distributions
	UNITS	LEVEL 1
	INVESTMENT BANKING	(2) Trading & Sales	B 1
	BANKING	(3) Retail Banking	B 2
		(5) Payment & Settlement	B 3
	OTHERS	(8) Retail Brokerage	B 4

Restricted Basel Matrix used to compute operational risk global capital allocation. B 1 , B 2 , B 3 , B 4 are the four loss distributions used in the vine methodology. B 2 and B 3 are built considering respectively (F 2 , F 5 , F 8 , F 9

Table 5 :

 5 This table provides the capital allocation (VaR) and the ES for the whole data set, considering three classes of severities (1 denotes the non parametric approach of the LDF, 2

	3 ,B 4 ) Margins	VaR	ES
		1	68 468 561 71 030 541
	Univariate	2	76 817 362 94 196 483
		3	48 113 918 48 244 680
		1	68 517 234 71 028 526
	Gumbel Copula	2	76 564 982 93 187 912
		3	48 112 494 48 241 814

Table 6 :

 6 For the LDF corresponding to F 9 and F 6 we provide the VaRs and the ES computed from a Gumbel copula for the year 2006. They are given respectively for three classes of severities.For instance, "Gumbel-GPD" means that we have chosen a Gumbel distribution to model F 9 and a mix of a lognormal and a GPD to model F 6 .

			Gumbel Copula
		LDF 9	LDF 6	VaR	ES
	Gumbel-GPD	2 322 782 103 099 574 105 422 356 1 603 169 459
	Gumbel-lognormal 1 471 343	566 312	2 037 655	3 091 139
	lognormal-GPD	15 405 192 101 802 210 117 207 402 1 904 323 684

Table 7 :

 7 For the LDF corresponding to F 9 and F 6 we provide the VaRs and the ES computed from a Clayton copula for the year 2006. They are given respectively for three classes of severities.

Table 8 :

 8 This table provides the VaRs and ES associated with each LDF of the set LDF 2 , LDF 5 , LDF 8 and LDF 9 when we decompose the dependence structure of the 4-dimensional set C 2589 ,

		LDF	LDF 2	LDF 5	LDF 8	LDF 9	VaR	ES
		1	19 650 986 3 182 731 14 212 411 2 241 011 39 287 139 40 899 526
	Univariate	2	6 240 984 2 151 627 11 676 534 4 049 831 24 118 976 32 957 873
		3	13 599 313 2 478 087 8 599 313	1 087 410 25 764 123 25 887 436
		1	20 578 056 3 300 471 15 191 828 2 386 106 41 456 461 43 024 128
	Gumbel Copula	2	10 732 933 2 310 337 29 525 155 13 608 000 56 176 425 79 500 929
		3	13 617 419 2 486 453 8 603 916	1 095 587 25 803 375 25 927 487

Table 1 )

 1 used in this paper.

	Distributions	Mean	Variance	Skewness Kurtosis
	F 1	195.37	292732.86	7.31	71.69
	F 2	1522.83 372183311.54	27.57	910.13
	F 3	175.42	3804557.63	30.03	956.75
	F 4	1805.81 93274002.03	18.74	457.58
	F 5	1824.95 189175093.33	17.79	354.00
	F 6	1200.08 438224165.80	23.69	563.48
	F 7	800.14	24268504.39	10.88	139.39
	F 8	1779	1602373386	19.27	435.88
	F 9	1824.95 189175093.3	17.79	354.00
	F 10	12104	519962084.2	108.03	11806.23

Table 10 :

 10 Statistics of the data sets used. The distributions are right skewed and present large kurtosis.

Table 11 :

 11 2.1) induce an infinite mean model which naturally provides very high VaRs. Nevertheless, non-parametric estimator such as Pickands might provide this kind of value and by the way unusable models. We provide risk measures on the data set which represents the severity of the business line "Payment & Settlement" and the event type "Delivery, Execution and Process Management"

	Method	β	ξ	VaR	ES
	M1	932.854	0.767	15 700 112	34 215 896
		(83.71) (0.101)
	M2	682.615	1.144	538 480 990	∞
		(160.70) (0.266)
	M3	1007	0.66	5 725 341	14 780 214
		(214.36) (0.228)
	M4	904.087	0.827	27 944 558 125 019 034
		(92.31) (0.097)

The lognormal assumption was the best on our data sets, but one can fit any other distributions.

The business lines are corporate finance, trading & sales, retail banking, commercial banking, payment and settlement, agency services, asset management and retail brokerage. The event types are internal fraud, external fraud, employment practices & workplace safety, clients, products & business practices, damage to physical assets, business disruption & system failures and execution, delivery & process management.

Nevertheless the complete Basel matrix could contain more than 250 cells, and thus more research will be necessary to work with such a large matrix, mainly to limit the time of computation. Recent improvements using parallel computing, seem to provide interesting solutions to achieve this purpose[START_REF] Brechmann | Truncated regular vines in high dimensions with applications to financial data[END_REF].