Olivier Lézoray
email: olivier.lezoray@unicaen.fr

Hubert Cardot
email: hubert.cardot@univ-tours.fr

Comparing combination rules of pairwise neural networks classifiers

Keywords: Pairwise classifier, combination, stacking

A decomposition approach to multiclass classification problems consists in decomposing a multiclass problem into a set of binary ones. Decomposition splits the complete multiclass problem into a set of smaller classification problems involving only two classes (binary classification: dichotomies). With a decomposition, one has to define a recombination which recomposes the outputs of the dichotomizers in order to solve the original multiclass problem. There are several approaches to the decomposition, the most famous ones being one-againt-all and one-against-one also called pairwise. In this paper, we focus on pairwise decomposition approach to multiclass classification with neural networks as the base learner for the dichotomies. We are primarily interested in the different possible ways to perform the so-called recombination (or decoding). We review standard methods used to decode the decomposition generated by a one-against-one approach. New decoding methods are proposed and compared to standard methods. A stacking decoding is also proposed which consists in replacing the whole decoding or a part of it by a trainable classifier to arbiter among the conflicting predictions of the pairwise classifiers. Proposed methods try to cope with the main problem while using pairwise decomposition: the use of irrelevant classifiers. Substantial gain is obtained on all datasets used in the experiments. Based on the above, we provide future research directions which consider the recombination problem as an ensemble method.

Introduction

Since the advent of data mining in information management systems, the applications of multiclass pattern recognition has covered a very wide range including image or text categorization, object classification, speech recognition. Multiclass pattern recognition aims at building a function F that maps the input feature space to an output space of more than two classes. Each example (x, y) consists of an instance x ∈ X and a label y ∈ {1, ..., K} where X is the feature vector input space and K the number of classes to be discriminated. A general classifier can be considered as a mapping F from instances to labels F : X → {1, ..., K}. There are two ways for a classifier to solve multiclass problems: [START_REF] Allwein | Reducing multiclass to binary: a unifying approach for margin classifiers[END_REF] consider all the data in one optimization problem, (2) construct several binary classifiers and combine them. The first approach formulates the multiclass problem into one single optimization problem (all-at-once). However, the number of samples is the main factor that contributes to the time complexity for training the classifier. Therefore, algorithms of the first category are significantly slower than ones that include several binary classifiers where each classifier classifies only a small portion of the data [START_REF] Furnkranz | Pairwise Classification as an Ensemble Technique[END_REF][START_REF] Furnkranz | Round Robin Classification[END_REF][START_REF] Lezoray | A Neural Network Architecture for Data Classification[END_REF][START_REF] Price | Pairwise neural network classifiers with propabilistic outputs[END_REF]. Moreover, muticlass classification is intrinsically harder than binary classification because the classification algorithm has to learn to construct altogether a high number of separation boundaries whereas binary classifiers have to determine only one appropriate decision function. Therefore, the machine learning community has devoted considerable attention to the latter type of approach the principles of which are the following. A decomposition splits a complete multiclass problem into a set of less complex and independent two-class problems (dichotomies) and a recombination (a decoding) recomposes the outputs of dichotomizers in order to solve the original polychotomy [START_REF] Furnkranz | Pairwise Classification as an Ensemble Technique[END_REF][START_REF] Kressel | Advances in Kernel Methods, Support Vector Learning, Chapt. Pairwise classification and support vector machines[END_REF]. A binary classifier having to face with the classification of data using examples as positive ones and the others as negative ones, there are two schemes to construct several binary classifiers for multiclass problems [START_REF] Ou | Multiclass pattern classification using neural networks[END_REF]. The most traditional scheme [START_REF] Rifkin | In defense of one-vs-all classification[END_REF] splits the original problem into a series of binary problems (one for each class) where the i th classifier is trained while labeling all the samples in the i th class as positive and the rest as negative. This technique is called oneagainst-all since each classifier separates one class from all the others. The drawbacks of this approach is that each binary classifier has to see all the training database instead of a reduced version of it and the training data can be unbalanced which can distort each binary classifier. The second scheme constructs K ×(K -1)/2 classifiers using all the pairwise combinations of the K classes [START_REF] Hastie | Classification by pairwise coupling[END_REF][START_REF] Price | Pairwise neural network classifiers with propabilistic outputs[END_REF][START_REF] Tax | Using two-class classifiers for multiclass classification[END_REF]. This technique is called oneagainst-one (pairwise). The latter approach is very interesting since the binary decision is not only learned on fewer training examples but the decision function of each binary problem can be considerably simpler than in the case of one-against-all [START_REF] Furnkranz | Pairwise Classification as an Ensemble Technique[END_REF][START_REF] Furnkranz | Round Robin Classification[END_REF][START_REF] Lu | Task decomposition and Module Combination based on Class Relations: A modular Neural Network for Pattern Classification[END_REF]. The major advantage of the pairwise approach is that it provides redundancy which can lead to better generalization abilities. Pairwise classification has been tried in the areas of statistics [START_REF] Bradley | The rank analysis of incomplete block designs: I. The method of paired comparisons[END_REF][START_REF] Friedman | Another approach to polychotomous classification[END_REF], neural networks [START_REF] Knerr | Handwritten digit recognition by neural networks with single-layer training[END_REF][START_REF] Lu | Task decomposition and Module Combination based on Class Relations: A modular Neural Network for Pattern Classification[END_REF][START_REF] Masulli | Comparing Decomposition Methods for Classification[END_REF][START_REF] Price | Pairwise neural network classifiers with propabilistic outputs[END_REF], support vector machines [START_REF] Hastie | Classification by pairwise coupling[END_REF][START_REF] Hsu | A comparison of methods for multi-class support vector machines[END_REF][START_REF] Kressel | Advances in Kernel Methods, Support Vector Learning, Chapt. Pairwise classification and support vector machines[END_REF] and others (bioinformatics [START_REF] Ding | Multiclass protein fold recognition using support vector machines and neural networks[END_REF][START_REF] Ie | Multi-class protein fold recognition using adaptive codes[END_REF], speech recognition [START_REF] Klautau | Combined binary classifiers with applications to speech recognition[END_REF], pathology [START_REF] Lezoray | A color object recognition scheme : application to cellular sorting[END_REF]). Typically, this technique learns more accurate concepts than the more commonly used one-againstall classification method with lower computational complexity (see in [START_REF] Furnkranz | Round Robin Classification[END_REF]). Furthermore, the advantage of pairwise classification increases for computationally expensive (super-linear) learning algorithms. The olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.2 reason is that expensive learning algorithms learn many small problems much faster than a few large problems. Pairwise classifiers can also be tuned so as to use a specific subset of features which can be different for each pairwise classification problem. Beside choosing the way to decompose the problem, one also needs to devise a strategy for combining the outputs of binary classifiers and provide a final prediction. Whatever the used decomposition (oneagainst-all and one-against-one), if a simple voting strategy is used, there can be inconsistent regions (less for one-against-one but one still remains, see [START_REF] Tax | Using two-class classifiers for multiclass classification[END_REF]). The problem of combining binary classifiers has therefore been extensively studied and a lot of combining schemes have been proposed but many researchers reported opposing views to which scheme is better in terms of accuracy and speed [START_REF] Allwein | Reducing multiclass to binary: a unifying approach for margin classifiers[END_REF][START_REF] Furnkranz | Pairwise Classification as an Ensemble Technique[END_REF][START_REF] Furnkranz | Round Robin Classification[END_REF][START_REF] Hastie | Classification by pairwise coupling[END_REF][START_REF] Hsu | A comparison of methods for multi-class support vector machines[END_REF][START_REF] Lezoray | Neural network induction graph for pattern recognition[END_REF][START_REF] Mayoraz | Support Vector Machines for Multiclass Classification[END_REF][START_REF] Moreira | Improved pairwise coupling classification with correcting classifiers[END_REF][START_REF] Ou | Multiclass pattern classification using neural networks[END_REF][START_REF] Platt | Large Margin DAGs for multiclass classification[END_REF][START_REF] Rifkin | In defense of one-vs-all classification[END_REF][START_REF] Takahashi | Optimizing directed acyclic graph support vector machines[END_REF][START_REF] Tax | Using two-class classifiers for multiclass classification[END_REF]. Speed issues depend primarily on the different implementations of the basic binary classifier and accuracy issues depend on the nature of the basic learner, the data set and how the basic classifiers are well tuned to achieve maximum performance [START_REF] Rifkin | In defense of one-vs-all classification[END_REF]. Literature being inconclusive (recent papers still claim that there is non clear superiority over the methods [START_REF] Duan | Which is the best Multiclass SVM method ? An empirical study[END_REF]), the best method for combining binary classifiers is an important research issue that remains open. In this paper, we propose to compare several classical combining schemes using Multi Layer Perceptrons (MLP) as the base learner. Moreover, we also propose new combining schemes which outperform the classical ones. We consider only the one-against-one formulation to proceed to the construction of binary neural networks. In Section 2, we present the binary neural networks we used. In section 3, we discuss how to combine binary neural networks. In Section 4, we demonstrate the effectiveness of the proposed combining methods by computer experiments. Last Section draws a conclusion and future research directions which consider the recombination problem as an ensemble method.

Binary Neural Networks

Since we consider the one-against-one decomposition scheme, for a classification problem with K classes, a set of neural networks is built; each one being in charge of separating elements from two distinct classes. The set of different classes is denoted by

C = {C 1 , C 2 , ..., C K } with |C| = K. The set of Binary Neural Networks (BNN) is given by A = {R C 1 ,C 2 ; • • • ; R C K-1 ,C K }.
In the rest of the paper, we will equally use the notation R C i ,C j or R i,j for sake of simplicity. The global training dataset containing patterns of all the different classes is denoted by D T rain . The latter is divided in several subsets for each neural network. D T rain (C i , C j ) is the dataset that corresponds to the neural network which differentiates the classes C i and C j and contains patterns of only those two classes. Then, the initial training data (D T rain (C i , C j )) associated to each neural network is split into two subsets: a learning set (D Learn (C i , C j )) and a validation set (D V alid (C i , C j )). The latter consists in 20% of D T rain (C i , C j ) and the learning set in 80% of D T rain (C i , C j ). The learning of a neural network is performed on D Learn (C i , C j ) and the D V alid (C i , C j ) validation set is used to evaluate the classification rate of the network during the training. Therefore, the validation set is not used to learn the weights of neural networks, but only to tune the hyper-parameters (number of neurons, number of iterations, etc.). The structure of the neural networks used is the following one: a layer of inputs containing as many neurons as the number of features associated with the object to be classified, a hidden layer containing a variable number of neurons and one output neuron. The value of the output neuron is in the interval [-1, 1]. According to the sign of the result associated with this single neuron, an object is classified in one of the two classes that the network separates. The neural networks used are very simple: only one hidden layer, only one neuron of output. This has several advantages [START_REF] Cardot | Graph of neural networks for pattern recognition[END_REF][START_REF] Lezoray | A Neural Network Architecture for Data Classification[END_REF][START_REF] Lezoray | Neural network induction graph for pattern recognition[END_REF]. The simplicity of the task associated to each neural network simplifies the convergence of the training as well as the search for a simple structure. Therefore, an automatic method is used to find the number of hidden neurons that gives the best classification rate [START_REF] Lezoray | A Neural Network Architecture for Data Classification[END_REF][START_REF] Campbell | Constructive Learning Techniques for Designing Neural Network Systems[END_REF][START_REF] Kwok | Constructive Algorithms for Structure Learning in Feedforward Neural Networks for Regression Problems[END_REF]. The output value provided by a BNN when a sample data x has to be classified is denoted by O(x, R C i ,C j ). From this output, x can be classified as C i or C j according to the sign of the output: x is considered as of class C i if O(x, R C i ,C j ) ≥ 0 and C j otherwise. The output can therefore be directly used as an estimate for the class memberships. However, it might be more suitable to have pairwise class probability estimates which can be obtained by [START_REF] Price | Pairwise neural network classifiers with propabilistic outputs[END_REF] r ij (x) = (O(x, R C i ,C j )+1)/2 and r ji (x) = 1-r ij (x). r ij (x) estimates the pairwise posterior probability of the input vector x to belong to the class i and r ji (x) to the class j (according to the single BNN R C i ,C j ).

Combining binary classifiers

Constructing multiclass classifiers from a pairwise decomposition consists in combining the B = (K × (K -1)/2) pairwise classifiers outputs. Each binary classifier is a mapping f b : X → R with b ∈ {1, ..., B}. A vector f (x) = (f 1 (x), ..., f B (x)) is constructed from the outputs of the binary classifiers. A combination rule g can then be applied to combine all the outputs f (x) using a function g : R B → R K which couples the estimates of each binary classifier in order to obtain class membership estimates (which can be probabilities) for the multiclass problem. Once the class memberships µ have been estimated as

g(f (x)) = g(f 1 (x), ..., f B (x)) = (µ(C 1 |x), ..., µ(C K |x)),
a final selection scheme is used to choose the winner class. This is done as a mapping h : R K → {1, ..., K}. The whole K-ary classifier combining all the binary classifiers scores (obtained by pairwise decomposition) is denoted by F (x) = h(g(f (x))) where h is the selection scheme function applied to select the winner class and g the combination rule. h•g defines the complete decoding scheme needed to perform multiclass classification from binary pairwise classifiers.

Standard Decoding

In this Section, we review the standard decoding schemes based on class memberships estimation and propose a new one.

Majority vote

The most commonly used combination rule is probably the Majority Vote (MV) one. With this combination rule [START_REF] Friedman | Another approach to polychotomous classification[END_REF], each class receives votes from individual classifiers. The membership estimates correspond to the number of votes received by each class:

µ(C i |x) = Σ j V (r ij (x) ≥ 0.5) with V (x) = 1 if
x is true and 0 otherwise. The chosen class is the one which receives the largest number of votes and h = argmax.

Hastie

A way to obtain class membership estimates from the pairwise probability estimates r ij (x) has been proposed by Hastie [START_REF] Hastie | Classification by pairwise coupling[END_REF]. To combine all the estimates of the BNN, we would like to obtain a set of class membership probabilities p i (x) = P (C i |x). The r ij estimate class conditional probabilities and are related to the p i according to

r ij (x) = P (C i |x, C i ∨ C j ) = p i (x) p i (x) + p j (x)
In order to find the best approximation r

′ ij (x) = µ i (x) µ i (x)+µ j (x) , the algo- rithm starts with µ i (x) = 2Σ j =i r ij (x) K(K-1)
and computes the corresponding olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.5 r ′ ij (x). The µ i (x) are obtained by minimizing the average Kullback-Leibler distance between r ij (x) and r ′ ij (x):

L(µ) = i<j n ij r ij log r ij r ′ ij + (1 -r ij ) log 1 -r ij 1 -r ′ ij
where n ij is the number of examples of classes i and j in the training set. The associated equations are:

j =i n ij r ′ ij = j =i n ij r ij subject to K k=1 µ k = 1. At convergence, we have the class membership estimates with µ(C i |x) = µ i (x).
The winner class is considered as the most likely one and h = argmax.

Price

Another approach for estimating the class memberships has been proposed by Price [START_REF] Price | Pairwise neural network classifiers with propabilistic outputs[END_REF]. It is based on the fact that neural networks trained to minimize a MSE cost function estimate posterior probabilities. A BNN with sigmoidal transfer function can therefore estimate the posterior probabilities for the two classes (previously denoted by r ij (x) and r ji (x)). One can then obtain the final expression of the class membership estimates by µ( 2) . As for the Hastie combination rule, we have h = argmax.

C i |x) = 1 Σ j =i 1 r ij (x) -(K-

Loss Based Decoding (LBD)

Another interesting combination rule is based on Error Correcting Output Codes (ECOC) [START_REF] Allwein | Reducing multiclass to binary: a unifying approach for margin classifiers[END_REF][START_REF] Crammer | On the Learnability and Design of Output Codes for Multiclass Problems[END_REF][START_REF] Dietterich | Solving Multiclass learning problems via error-coorecting output codes[END_REF]. Different classes are represented by output codes in the output vector space and the prediction of classification is based on the fact that the chosen class has its output code close to the output one of the example to be classified. It has been introduced to combine the outputs of binary Support Vector Machines. For a problem with K classes, it creates a matrix M ∈ {-1, 0, 1} K×B . For a K = 3 classification problem, the matrix is defined as:

f 1 f 2 f 3 C 1 +1 +1 0 C 2 -1 0 +1 C 3 0 -1 -1
A column in the matrix M corresponds to a binary classifier R i,j and a row corresponds to a class. For instance, the first column corresponds to the classifier R C 1 ,C 2 . Therefore, to each class is assigned a binary code vector of length K which makes up the rows of the code matrix. Combining all the binary classifiers to estimate the class memberships consists in comparing the matrix rows with the classifiers outputs expressed by µ(

C k |x) = B b=1 L(M (k, b).f b (x))
. This provides the distortion between the vector of the BNN outputs f (x) and the row M (k, •). For this combination rule, the outputs of the binary classifiers O(x, R ij ) are directly used and not the r ij (x). The original approach to ECOC predicts the class whose corresponding row vector has minimum Hamming distance to the vector of 0/1 predictions obtained from the classifiers [START_REF] Dietterich | Solving Multiclass learning problems via error-coorecting output codes[END_REF]. However, the accuracy can be improved by using Loss Based decoding (LBD) and we have therefore used L(z) = exp(-z). This means using the outputs of the binary classifiers rather than their hard 0/1 predictions [START_REF] Allwein | Reducing multiclass to binary: a unifying approach for margin classifiers[END_REF]. For LBD decoding schemes h = argmin since this leads to finding the row being the most similar to the classifiers outputs [START_REF] Klautau | Combined binary classifiers with applications to speech recognition[END_REF][START_REF] Klautau | On Nearest neighbor Error-Correcting Output Codes with Application to All-Pairs Multiclass Support Vector Machnies[END_REF] (nearest neighbor decoding). Some works consider learning the weights of the code matrix by solving an optimization problem [START_REF] Ie | Multi-class protein fold recognition using adaptive codes[END_REF] but we do not consider that issue in this paper.

Min-Max

For all the previous decoding schemes, the probability estimates of the classifiers obtained by the combination rule g are used to assign to an input pattern the class with the maximal output. Combining all the pairwise classifiers can lead to bad results since if the input x is of class C i , there are only (K -1) relevant classifiers among the (K × (K -1))/2 which have seen the class C i and the remaining ((K -1) × (K -2))/2 irrelevant classifiers have never seen inputs from class C i . While classifying an input, one wishes that relevant classifiers will provide coherent informations to cope with all the irrelevant ones. Moreira has proposed [START_REF] Moreira | Improved pairwise coupling classification with correcting classifiers[END_REF] to estimate the relevance of a binary classifier with correcting classifiers which separate each pair of classes from all the other classes; correcting classifiers being used to weight the pairwise probabilities. This approach is however very expensive and the advantages of the pure pairwise approach are lost. To try to alleviate this problem, we propose to get the minimum value of r ij (x)

for each class C i : µ(C i |x) = K-1 min j r ij (x)
. Finally, we select the class which maximizes this minimum value: h = argmax. The principle of this method consist in choosing the candidate class whose probability is less bad than that for all other candidate classes. The intuitive idea behind is that having a high pairwise probability for a particular pair of classes does not imply a strong decision towards this class because of irrelevant classifiers. However, it can be rejected if the probability is low.

Elimination Decoding

Another decoding scheme is the elimination decoding one. This decoder was originally described by Kressel [START_REF] Kressel | Advances in Kernel Methods, Support Vector Learning, Chapt. Pairwise classification and support vector machines[END_REF] and reintroduced by Platt [START_REF] Platt | Large Margin DAGs for multiclass classification[END_REF] where it was called Directed Acyclic Graph (DAG). One strong argument for using DAG is that it resolves the problem of unclassifiable regions for pairwise classification. The elimination decoding is nothing more than a decision-tree based pairwise classification. The nodes of this tree are binary classifiers. To perform a multiclass classification, an example is presented to each node and follows a path in the tree by eliminating a class at each node. The set of binary classifiers A 0 = {R 1,2 , ..., R K-1,K } contains all the binary classifiers and the set E 0 = {C 1 , ..., C K } contains all the candidate winner classes. Elimination decoding operates iteratively. At each iteration t = {1, ..., K -1}, a binary classifier performs a decision and one class C k is eliminated. The size of E t is then decreased by one and all the classifiers discriminating C k in A t are eliminated [START_REF] Klautau | On Nearest neighbor Error-Correcting Output Codes with Application to All-Pairs Multiclass Support Vector Machnies[END_REF]:

A t+1 = A t -{R i,j : i = C k ∨ j = C k }.
The set A K-2 contains only one binary classifier which determines the winner class. Several problems occur however when using DAGs. First of all, the choice of the winner class depends on the sequence of binary classifiers in nodes which affects the reliability of the algorithm. Moreover, the correct class to be predicted is more or less advantaged according to its distance to the root node (higher risk of being rejected in the nodes near the root). Secondly, since there are a lot of classifiers which are irrelevant for a given classification, using these classifiers can cause severe defects. To overcome this problem, several authors have proposed to use an Adaptive DAG (called ADAG) by optimizing its structure. However, the generalization ability still depends on the structure of the tree [START_REF] Lezoray | Neural network induction graph for pattern recognition[END_REF][START_REF] Cardot | Graph of neural networks for pattern recognition[END_REF][START_REF] Ko | Improved N-division output coding for multiclass learning problems[END_REF][START_REF] Phetkaew | Reordering adaptive directed acyclic graphs: an improved algorithm for multiclass support vector machines[END_REF][START_REF] Vural | A hierarchical method for multi-class support vector machines[END_REF]. We propose a new elimination decoding which takes into account all the outputs of the binary classifiers. When using a classical decoding scheme without elimination, one selects the class with the largest probability (h = argmax). In the case of elimination, we want to eliminate the least credible class and this comes back to eliminate the class having the minimum of probability. The class to be eliminated is deduced from the class membership estimates: C k = h(g(f (x))). g can be any of the previous combination rules (Majority Vote, Hastie, Price, LBD, Max-Min) and since the method eliminates the least probable class at each iteration, we have h = argmin. At the iteration t, the number of candidate classes is |E t | = (K -t) and the number of binary classifiers to be combined is |A t | = (K -t)(K -t -1)/2. This new elimination decoding is different of the Direct Acyclic Graph [START_REF] Platt | Large Margin DAGs for multiclass classification[END_REF] since at each iteration, all the outputs of candidate binary classifiers are combined to determine the class to be eliminated. Indeed, with a DAG, only one classifier output is used for eliminating a class at each iteration. The proposed elimination decoding can be summarized by Algorithm 1. Figure 1 presents an illustration of the algorithm for a 4-class problem.

Algorithm 1

The proposed new elimination decoding.

t ← 0, A t ← {R 0,1 , ..., R K-1,K }, E t ← {C 1 , ..., C K } while |E t | = 1 do C k ← h(g(f (x))) E t+1 ← E t -{C k } A t+1 ← A t -{R i,j : i = C k ∨ j = C k } t ← t + 1 endwhile F (x) = E t

Stacking Decoding

The combination of the class membership estimates can be performed via a separate trainable classifier [START_REF] Klautau | Combined binary classifiers with applications to speech recognition[END_REF][START_REF] Savicky | Combining Pairwise Classifiers with Stacking[END_REF]. This method is referred to as stacking [START_REF] Wolpert | Stacked generalization[END_REF]. Very few works consider this issue for multiclass classification. Klautau [START_REF] Klautau | Combined binary classifiers with applications to speech recognition[END_REF] and Mayoraz [START_REF] Mayoraz | Support Vector Machines for Multiclass Classification[END_REF] both use a neural network to stack the predictions provided by one-versus-all binary classifiers. Savicky combines binary decision trees with a meta decision tree at olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.9 the stacking level [START_REF] Savicky | Combining Pairwise Classifiers with Stacking[END_REF]. This approach seems more suitable than all the previous ones for the following reason. As said before, combining classifiers which have never seen instances from one same class during the training phase results in combining different information sources. The combination of these ignorant classifiers (a binary classifier has seen only two classes among K) with respect to the others can therefore result in almost random classification. Indeed, decoding methods such as voting rely on the assumption that the relevant classifiers mainly predict the correct class and provide more votes to the true class than the irrelevant classifiers to any other class. However, if some of the relevant classifiers predict wrong classes, the final classification can be also wrong. Since we cannot predict the behavior of irrelevant classifiers, more sophisticated decoding schemes are needed. The potential gain of stacking for decoding is evident and it can lead to correct predictions where other methods would fail [START_REF] Savicky | Combining Pairwise Classifiers with Stacking[END_REF][START_REF] Zhou | NeC4.5: Neural Ensemble Based C4.5[END_REF]. Table I illustrates this fact and presents classification results for a 3-class problem (from [START_REF] Savicky | Combining Pairwise Classifiers with Stacking[END_REF]). With a standard decoding such as voting, the decoding will always fail to predict the correct class of the third sample. Indeed, the classifier C 1 vsC 3 makes a mistakes (it predicts class C 3 ) and the classifier C 2 vsC 3 , which is irrelevant for this classification (the input sample is of class C 1 ), predicts the input sample as of class C 3 . This case illustrates all the problems we have to face with when using binary classifiers: some classifiers are irrelevant and the relevant classifiers can make mistakes. Simple standard decoding schemes cannot cope with such cases and one has to learn to recognize such ones: a Meta Classifier can be used to that aim. We therefore propose two approaches to stacking decoding.

Stacking consists in combining the outputs of different classifiers to feed a trainable Meta Classifier. With a pairwise decomposition approach to classification, two approaches to stacking can be consid-olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.10 ered. The first approach to stacking is to learn on all the probabilities estimated by any standard decoding. In standard decoding, the whole K-ary classifier combining all the binary classifiers scores (obtained by pairwise decomposition) is denoted by F (x) = h(g(f (x))). One can replace h by a trainable classifier to cope with irrelevant predictions provided by by some pairwise classifiers. In that case, each feature vector x i of the training set D T rain is used to feed all the binary classifiers and class membership estimates are obtained with a combination rule g. A new example ( xi , y i ) = (g(f (x i )), y i ) is then obtained. The dimension of xi is equal to the number of classes and y i is the known class of x i . A new training set D ′ T rain = {( x1 , y 1 ), ..., ( xN , y N )} = {(g(f (x 1 )), y 1 ), ..., (g(f (x N )), y N )} is generated from the class membership estimates. The new training data set is used to train a Meta Classifier which predicts the final class by F (x) = h(g(f (x))). The function h designs the Meta Classifier to be used. Using a Meta Classifier which performs stacking on the class membership estimates is close to learn the weights of LBD decoding matrix [START_REF] Ie | Multi-class protein fold recognition using adaptive codes[END_REF]. The second approach to stacking is to learn on all the predictions of the binary classifiers [START_REF] Lezoray | Combining multiple pairwise neural networks classifiers: a comparative study[END_REF]. To that aim, a trainable classifier is used with as training input the output vector f (x) of all the binary classifiers. For this approach to stacking, new examples of the meta training set are ( xi , y i ) = (f (x i ), y i ). In that case, the function h • g designs the Meta Classifier to be used. The D ′ T rain = {(f (x 1 ), y 1 ), ..., (f (x N ), y N )} database generated by all the binary classifiers provides valuable information about the possible misleading predictions caused by the irrelevant classifiers.

Experimental results

This Section presents an experimental comparison of the ways to combine binary neural networks according to different combining rules. The databases for which results will be presented here are data bases coming from the Machine Learning Data Repository of the University of California at Irvine (UCI) [START_REF] Hettich | UCI Repository of machine learning databases[END_REF]. Table II describes Tables III, IV and V presents all the classification rates obtained on D T est for the different combining rules (best rates bold faced for each decoding rule family). For the standard decoding (Table III), the results are homogeneous, except for Hastie and Price methods which perform significantly worse on several datasets. As expected from the literature, LBD decoding performs very well and provides results always better than the Majority Vote. One thing to point out with LBD is that it can be a robust combining method as long as the errors of the binary classifiers are not correlated [START_REF] Moreira | Improved pairwise coupling classification with correcting classifiers[END_REF][START_REF] Mayoraz | Support Vector Machines for Multiclass Classification[END_REF]. For this purpose, all the dichotomies must be as distinct as possible, using well-tuned binary classifiers does the matter and explains why LBD works well in our study. When LBD is not best combining method, best results are obtained with the proposed Min-Max method which confirms the intuitive idea that in some cases the irrelevant classifiers have strong influence olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.12 on the final decision. Another advantage of the Min-Max method is its simplicity. One can therefore say that even if the results are very mixed, two standard decoding schemes can be retained as the best ones: LBD and the proposed Min-Max method. If we now have a look at the results obtained with the proposed elimination decoding method (Table IV), the first interesting thing is that the results look much more homogeneous between the different combining rules. As it was noted by Platt with DAGs, using an iterative elimination method reduces the error bound [START_REF] Platt | Large Margin DAGs for multiclass classification[END_REF] since it avoids the problem of irrelevant regions of classification. Table IV presents a comparison for the proposed elimination decoding with an improved ADAG (a Graph of Neural Networks, see in [START_REF] Cardot | Graph of neural networks for pattern recognition[END_REF][START_REF] Lezoray | Neural network induction graph for pattern recognition[END_REF] for details). It can be noted that the elimination method we propose performs in general better than classical DAGs [START_REF] Hsu | A comparison of methods for multi-class support vector machines[END_REF] even of improved structure; proving that using an elimination method based on combining rules is a more robust method than one based on a decision tree of binary classifiers, without the problem of optimizing the structure of the tree. This is all the more interesting since our elimination decoding reduces the error bound whatever the combining rule. As for the standard decoding method, the two best combining rules are LBD and Max-Min (since we perform an elimination we do not have Min-Max: at each iteration the class minimizing the highest pairwise probability is eliminated). Elimination decoding is however in average less good than standard olezoray_NPL_v2.tex; 18/10/2007; 21:36; p. [START_REF] Hastie | Classification by pairwise coupling[END_REF] decoding and it has be preferred only when the latter does not perform well (e.g. for Hastie and Price standard decoding on the PageBlocks data base, see Table III). The inner limitation of elimination decoding is related to the problem of irrelevant classifiers which can predict wrong class with high confidence resulting in their early elimination.

Table V. Classification rates of stacking decoding with as input: class membership estimates by standard decoding (rows 1-4) or all the pairwise predictions (rows 5-6). Finally, we analyze the results of our two proposed approaches to stacking decoding (Table V). We used decision trees (C4.5 [START_REF] Quinlan | C4.5 : programs for machine learning[END_REF]) Meta Classifiers to perform stacking. On all stacking datasets, a 10-fold cross validation is performed. Table V presents the results with, in rows 1-4 the first stacking approach and in rows 5-6 the second stacking approach. If one compares the first stacking approach (which consist in learning on the class memberships estimates provided by any standard decoding) with the standard and elimination decodings (Tables III andIV), stacking enables to improve the decoding for all data bases except one (Optdigits). In some cases, the increase of the recognition rate can be spectacular: for PageBlocks with Price or Hastie decoding, replacing h = argmax (Table III) by a decision tree (Table V) results in a doubly of the recognition rate. It highlights the fact that, in a lot of cases, the class membership estimates of some classes are very close one to another and a simple decision rule such as h = argmax cannot cope with such problems: conflicts between classes have to be learned to be overcome. We can also point out that for this first approach to stacking, the Hastie and the MinMax combination rules seem more appropriate to estimate the class membership estimates. Indeed, among the four stacked combination rules, one of the two above-mentioned always enable to obtain the best results (Table V). If we now consider our second approach to stacking (Table V, rows 5-6) which learns on all the BNN outputs, the performance of stacking depends on the type of predictions provided by the binary classifier (hard or soft predictions). For hard predictions (HP), the prediction of each binary classifier is a 0/1 prediction and for soft predictions (SP), it is the output of each binary classifier. As regards the results of standard decoding (Table IV) and of our first approach to stacking (Table V, rows 5-6), the second approach to stacking using hard predictions (Table V, row 5) does not provide a substantial gain of the recognition rate. On the contrary, using soft predictions (Table V, row 6) enables to obtain better results than standard decoding and than our first approach to stacking on half of the databases. As compared to the work of Savicky [START_REF] Savicky | Combining Pairwise Classifiers with Stacking[END_REF], the use of posterior probabilities instead of hard class decisions of the binary classifiers to feed the stacking Meta Classifier enables substantial gain in the recognition rate.

To conclude these experiments, using binary classifiers is very interesting since it can be viewed as an ensemble method which performs a simplification of the problem by decomposing it, the latter results been easier to classify by stacking than the initial ones all-at-once or even with standard decoding schemes. The question is now which approach to stacking to choose. Indeed, if stacking always provides better results than standard or elimination decoding, the best stacking approach depends on the data bases. Our second approach to stacking has to deal with very large problems since the size of the feature dimension vector is proportional to the number of classes. For example, for the 26-class Letter dataset, there are (26×25)/2 = 325 predictions for each of 16000 examples. This can be a serious drawback. Figure 2 shows the size of the decision tree induced according to the number of classes for our second approach to stacking (dashed lined), one can see that this size rapidly grows with the number of classes and can be very large. This is also the case when using our first approach to stacking whatever the used combination rule (see Figure 2). However, the size of the feature vector is in this case exactly equal to the number of classes. Since no real difference in the size of the induced tree is observed, none of the two approaches to stacking can be preferred, the first being less costly in terms of stacking database size.

Conclusion

In this paper, we reviewed and evaluated classical methods for multiclass classification based on binary neural networks according to the one-against-one formalism. We have also introduced a new standard decoding method (Min-Max) and a new elimination decoding which are both as suitable as the classical methods presented in the literature as proved by the experiments. The LBD and Min-Max decoding methods have appeared to be the best ones among the tested databases. We show that elimination decoding reduces the error bound of standard decoding methods but standard decoding is more suitable in terms of performance. We also evaluated a technique using stacking decoding where the basic idea is to replace either solely the selection scheme or both the combining rule and selection scheme by a single Meta Classifier that combines therefore either the membership class estimates or all the predictions of the binary classifiers. Using stacking decoding leads to substantial gain in the recognition rate. Future work will concern the use of the set of one-against-one classifiers as a new input sample generator [START_REF] Zhou | NeC4.5: Neural Ensemble Based C4.5[END_REF] to increase the size of the training dataset of the Meta Classifier when the latter is unbalanced; preliminary results having also shown a new gain in the recognition rate. As regards the results and as it was stated by Furnkranz [START_REF] Furnkranz | Round Robin Classification[END_REF], binary classifiers have now to be considered as an ensemble method such as boosting. Some works have considered this issue in the case of the elimination decoding: since the structure of a DAG is difficult to optimize, it is worth to try to combine an ensemble of DAG. As stated in [START_REF] Frank | Ensembles of nested dichotomies for multi-class problems[END_REF], since any system of nested dichotomies is biased by imposing a certain order on the set of classes, the class probability estimations will usually differ for two different systems of nested dichotomies. To reduce the error variance, one can build an ensemble of nested dichotomies. A similar work with ensemble of Neural Network Induction Graphs leads to the same results [START_REF] Lezoray | Neural network induction graph for pattern recognition[END_REF]. Pairwise classification has therefore to be considered as an ensemble method and future works will concern this issue: theories from multiple classifier systems have to be used to enhance once again pairwise ensemble classifiers accuracies. Several issues can be considered. First, one can try to combine the outputs of several standard decoding schemes. Second, one can consider the problem as a global optimization one: the tuning of each binary classifier can be performed simultaneously with the optimization of the decoding scheme to cope with the problem of irrelevant classifiers. These research directions place the problem of combining pairwise classifier in the research field of classifier selection and fusion which has not been extensively studied for this particular case.

Figure 1 .

 1 Figure 1. Illustration of the proposed new elimination decoding. At each step, a class is eliminated. The remaining candidate classes are shown on the right of boxes designing a step of the algorithm.

  the different databases showing the variety of training data set sizes (|D T rain |), the number of classes (K), the number of neural networks (B) and the dimensionality of the data input (|x|). The tests are performed on a data set (D T est ) independent of the training set.

Figure 2 .

 2 Figure 2. C4.5 Tree size according to the number of classes for the proposed stacking approach: first approach (Hastie, Price, LBD and Min-Max decoding) and second approach (all the pairwise networks outputs).

Table I .

 I Classification cases to illustrate the advantages of stacking decoding.

		Classifier		Original
	C1vsC2 C1vsC3 C2vsC3	class
	C1	C1	C2	C1
	C2	C3	C2	C2
	C1	C3	C3	C1
	. . .	. . .	. . .	. . .
	C2	C3	C3	C3

Table II .

 II Data bases used for the tests. Database K |DT rain| |DT est | |x| B

	Iris	3	120	30	4	3
	Wine	3	144	34 13	3
	Vehicle	4	679	167 18	6
	PageBlocks	5	4382	1091 10	10
	SatImage	6	4435	2000 36	15
	Shuttle	7	43500	14500	9	21
	PenDigits	10	7494	3498 16	45
	OptDigits	10	3065	760 64	45
	Letter	26	16000	4000 16 325

Table III .

 III Classification rates of one-versus-all and one-against-one standard decoding.

		MLP	MV	Hastie	Price	LBD	MinMax
	Iris	70.00 70.00 63.33	63.33	70.00 70.00
	Wine	97.06 97.06 97.06	97.06 97.06 97.06
	Vehicle	66.67	69.46	68.26	70.06 69.46	69.46
	PageBlocks	84.80	88.27	42.35	46.29	88.45 88.36
	SatImage	80.00	77.90	80.10	79.90	80.10 78.35
	Shuttle	79.15	95.70	95.01	95.18	95.82 95.57
	Pendigits	83.82	89.17	82.19	88.42	89.05	89.22
	Optdigits	90.39	91.70	81.69	87.62	90.91	91.83
	Letter	62.45	78.37	65.50	71.57	78.52 77.72

Table IV .

 IV Classification rates of one-against-one elimination decoding.

		ADAG MV	Hastie	Price	LBD	MaxMin
	Iris	70.00	70.00 70.00	70.00 70.00 70.00
	Wine	97.06	97.06 97.06	97.06 97.06 97.06
	Vehicle	69.46	68.26	68.86	68.86	68.86	69.46
	PageBlocks	88.45	88.36	88.36	88.45 88.45 88.36
	SatImage	78.05	77.85	78.20	78.10	78.20	78.35
	Shuttle	95.64	95.66	95.63	95.62	95.76 95.59
	Pendigits	88.99	89.19	89.14	89.11	89.17	89.28
	Optdigits	88.67	91.04	91.17	91.17	91.17	91.70
	Letter	77.64	78.44	77.54	77.64	78.47 77.67

olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.3

olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.4

olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.6

olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.7

olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.8

olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.11

olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.14

olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.15

olezoray_NPL_v2.tex; 18/10/2007; 21:36; p.16


A Husson

B H Kim

A Welker

M Charlton

J J Choi

M Chung

P Cladé

P Comini

P.-P Crépin

P Crivelli

O Dalkarov

P Debu

L Dodd

A Douillet

S Guellati-Khélifa

N Garroum

P-A Hervieux

L Hilico

P Indelicato

G Janka

S Jonsell

J-P Karr

E-S Kim

S K Kim

Y Ko

T Kosinski

N Kuroda

B Latacz

H Lee

J Lee

A M M Leite

K Lévêque

E Lim

L Liszkay

P Lotrus

T Louvradoux

D Lunney
email: david.lunney@ijclab.in2p3.fr

G Manfredi

B Mansoulié

M Matusiak

G Mornacchi

V V Nesvizhevsky

F Nez

S Niang

R Nishi

S Nourbaksh

K H Park

N Paul

P Pérez

S Procureur

B Radics

C Regenfus

J-M Reymond

S Reynaud

J-Y Roussé

O Rousselle

A Rubbia

J Rzadkiewicz

Y Sacquin

F Schmidt-Kaler

M Staszczak

B Tuchming

B Vallage

A Voronin

D P Van Der Werf

S Wolf

D Won

S Wronka

Y Yamazaki

K-H Yoo

A pulsed

Keywords: Antihydrogen, General Relativity, Charged-particle optics, ion-optic simulations

come   L'archive ouverte pluridisciplinaire

Introduction

The GBAR (Gravitational Behaviour of Antihydrogen at Rest) experiment [START_REF] Pérez | The gbar antimatter gravity experiment[END_REF] at CERN aims at testing the Weak Equivalence Principle (WEP) of General Relativity by measuring the free fall of antihydrogen ( H) in the Earth's gravitational field. The WEP has been stringently tested in different regimes but never using antimatter, which may fall with a different acceleration than for matter. Such an experiment requires extremely well-defined initial conditions, with near-zero initial velocity. While this goal is likewise pursued by the CERN experiments ALPHA [START_REF] Amole | Description and first application of a new technique to measure the gravitational mass of antihydrogen[END_REF] and AEgIS [START_REF] Aghion | A moiré deflectometer for antimatter[END_REF], GBAR will attempt a unique approach by synthesizing antihydrogen ions ( H+ ) that can be sympathetically cooled by coupling to a laser-cooled trapped-Be-ion crystal [START_REF] Monroe | Resolved-sideband raman cooling of a bound atom to the 3d zero-point energy[END_REF][START_REF] Hilico | Preparing single ultra-cold antihydrogen atoms for free-fall in gbar[END_REF][START_REF] Sillitoe | Sympathetic cooling simulations with a variable time step[END_REF], reaching velocities of about 1 m/s (60 µK).

GBAR will fabricate antihydrogen using the electron-positron atomic system, positronium (Ps) created by directing positrons onto a mesoporous sil-Preprint submitted to Nuclear Instruments and Methods in Physics Research Section A: July 21, 2021 ica target [START_REF] Liszkay | Orthopositronium annihilation and emission in mesostructured thin silica and silicalite-1 films[END_REF]. Antiprotons sent through the Ps cloud undergo two successive charge-exchange reactions, forming H and H+ . Producing H+ requires a higher positron flux than achievable with a radioactive source. Therefore, the positrons required to form a Ps cloud of sufficient density are generated using a 9 MeV electron linear accelerator [START_REF] Liszkay | with the GBAR Collaboration, Positron production using a 9 mev electron linac for the GBAR experiment[END_REF], cooled in a buffer-gas magnetic trap and then accumulated in a 5 T Penning-Malmberg trap [START_REF] Niang | Accumulation of positrons from a linac based source[END_REF] before being directed onto the target.

The Ps reaction for the formation of antihydrogen was proposed by Humberston et al. [START_REF] Humberston | On antihydrogen formation in collisions of antiprotons with positronium[END_REF] and first cross-section measurements were performed by Merrison et al. [START_REF] Merrison | Hydrogen formation by proton impact on positronium[END_REF] at energies down to 11.3 keV. The predictions of various atomic-physics models reported in [START_REF] Merrison | Hydrogen formation by proton impact on positronium[END_REF] did not agree on the most favorable energy but more recent calculations [START_REF] Comini | H+ ion production from collisions between antiprotons and excited positronium: cross sections calculations in the framework of the GBAR experiment[END_REF][START_REF] Kadyrov | Antihydrogen formation via antiproton scattering with excited positronium[END_REF] predict that even lower antiproton energies would lead to higher cross sections, hence better H and H+ production rates. Refined calculations are in progress to probe this important question [START_REF] Yamashita | Towards prediction of the rates of antihydrogen positive ion production in collision of antihydrogen with excited positronium[END_REF].

The H+ ions for GBAR will be fabricated using antiprotons delivered by the CERN AD-ELENA facility [START_REF] Bartmann | The ELENA facility[END_REF]. The ELENA synchrotron heralds a new era of antiproton and antimatter physics. Its deceleration of antiprotons from 5.3 MeV to 100 keV bridges an important gap to achieve more efficient antihydrogen fabrication and storage at sub-Kelvin temperatures.

The first capture of antiprotons into a Penning trap was performed by Gabrielse et al. [START_REF] Gabrielse | First capture of antiprotons in a penning trap: A kiloelectronvolt source[END_REF] using a beryllium energy-degrader foil for a 150 ns burst of 10 8 antiprotons delivered at 21.3 MeV by CERN's LEAR facility. CERN's AD facility later provided pulses of 3 × 10 7 antiprotons at 5.3 MeV, allowing the use of thinner foils to achieve rates of about 20000/shot [START_REF] Gabrielse | Stacking of cold antiprotons[END_REF]. The ASACUSA experiment further reduced this energy to below 100 keV, using a radiofrequency quadrupole linear accelerator operated in reverse mode [START_REF] Hori | The asacusa experiment at cern's antiproton decelerator[END_REF][START_REF] Kuroda | Confinement of a large number of antiprotons and production of an ultraslow antiproton beam[END_REF][START_REF] Kuroda | Development of a monoenergetic ultraslow antiproton beam source for high-precision investigation[END_REF]. The lower incident beam energy allowed the use of foils that were 800 times thinner than in [START_REF] Gabrielse | First capture of antiprotons in a penning trap: A kiloelectronvolt source[END_REF] and improved the number of trapped antiprotons by a factor of 50 [START_REF] Kuroda | Confinement of a large number of antiprotons and production of an ultraslow antiproton beam[END_REF].

Using electrostatic deceleration would ideally avoid all losses associated with the use of foils. ELENA now allows using electrostatic retardation and fast switching to reach the energy regime favorable for antihydrogen formation by charge exchange.

This article describes a novel multi-electrode deceleration system that creates a 100 keV particle "elevator". This is accomplished using electrostatic retardation optics and a drift tube that is switched from -99 kV to ground during the short time that the antiproton bunch is inside. Further optics focus the low-energy beam into the Ps reaction chamber. Simulations for the optimization of the potential values are described, as well as the design, construction and preliminary testing of the decelerator device down to -92 kV using H -and antiprotons from ELENA during its commissioning period.

Design and construction of the decelerator

The concept of the decelerator and results from first tests with the prototype have been described in [START_REF] Lunney | Beam preparation for studying the gravitational behavior of antimatter at rest (GBAR)[END_REF][START_REF] Husson | An antiproton deceleration device for the GBAR experiment at CERN[END_REF][START_REF] Husson | Deceleration of antiprotons from cern's elena synchrotron and transport of antimatter beams through the gbar experiment[END_REF]. The principle is to use a static electric field to slow the charged antiprotons into a drift tube, within which there are ideally no potential gradients. Once the antiproton pulse is inside the field-free region, the voltage applied to the tube is switched to ground. If the switching is fast enough, there will be no voltage gradient at the exit of the tube when the antiprotons arrive, so they continue at their decelerated kinetic energy. Of course the use of drift tubes for changing the energy of particle beams is not new. Drift tubes form the heart of linear accelerators using AC voltages, however their use as particle elevators is less common. The so-called pulsed drift tube is used at many nuclear physics facilities where ion species are transported with energies of 30-60 keV and must be slowed to a few eV to be confined in a trap. The deceleration of the ion bunch causes the beam emittance to blow up so that the ions must be cooled to be trapped. The technique was largely developed by the ISOLTRAP experiment at CERN's ISOLDE facility, in conjunction with a device for accumulating ISOLDE beams [START_REF] Herfurth | A linear radiofrequency ion trap for accumulation, bunching, and emittance improvement of radioactive ion beams[END_REF]. In this scheme, the beam is decelerated into a linear radiofrequency trap filled with buffer gas, which cools the large emittance of the decelerated beam to essentially a point-like source. The drift tube is mounted directly downstream of the trap [START_REF] Ghalambor Dezfuli | Injection, cooling and extraction of ions from a very large paul trap[END_REF]. This scheme is now used by several on-line trap facilities.

The main difference with the decelerator presented here is that since antiprotons would annihilate with the buffer gas atoms the deceleration process must include optics to keep the larger emittance within the drift-tube electrode and limit divergence in the region of potential gradients.

A deceleration system for ion beams that did not incorporate a gas-filled cooler buncher was designed for the WITCH experiment at ISOLDE by Coeck et al. [START_REF] Coeck | A pulsed drift cavity to capture 30kev ion bunches at ground potential[END_REF]. The beam was cooled in a gas-filled Penning trap a few meters upstream and reaccelerated. The drift tube was almost 700 mm long and used an intermediate deceleration electrode to limit the beam divergence, decelerating 43 % of the incident 30 keV beam with 24 kV on the drift tube. A similar scheme for 30 keV ions was developed for the TRIGATRAP experiment in Mainz [START_REF] Grund | First online operation of triga-trap[END_REF].

Decelerating 100 keV ELENA beams requires a substantial scaling from the 30 kV systems mentioned above.

ELENA was designed to provide antiproton bunches of 300 ns duration (defined as four times rms value of 75 ns that includes 95% of an approximately Gaussian distribution), 0.25% momentum spread and about 4π mm mrad transverse emittance [START_REF] Bartmann | The ELENA facility[END_REF]. When the 100 keV beam is decelerated to 1 keV, the transverse emittance increases to 40π mm mrad and the 1.3 m pulse length is reduced to about 150 mm. We consequently chose a drift-tube length of 400 mm to allow enough time for switching within a field-free region.

The first consequence of decelerating the beam is a large divergence, which will cause huge losses inside a long drift tube. It is also critical to preserve good focusing properties of the beam by avoiding aberrations during the deceleration. This requires keeping the beam as parallel as possible, especially where the field gradient is large, and necessitates extra degrees of freedom for the optics. The work of C. Smorra for the TRIGATRAP drift tube [START_REF] Smorra | High-precision Q-value and mass measurements for neutrino physics with TRIGA-TRAP and commissioning of an on-line ion source for triga-spec[END_REF] gives an excellent illustration.

Simulations were performed using the ion-optics program SIMION R , starting with three electrodes (in the familiar einzel lens geometry). The decelerated beam developed a rather large diameter, introducing aberrations that prevented good focusing (the GBAR experiment requires directing the decelerated beam into a 1 mm diameter cavity). This solution also led to large variations in divergence for small changes in deceleration voltage. Therefore a second triplet geometry was introduced to provide more flexibility keeping the diameter smaller. We also reasoned that any of the additional lenses could always be grounded if they were not necessary. It is interesting to note that the work of Coeck et al. [START_REF] Coeck | A pulsed drift cavity to capture 30kev ion bunches at ground potential[END_REF] concluded with the proposition of including extra electrodes to improve their decelerator design.

An example of a SIMION R trajectory calculation is shown in Fig. 1, which refocuses the decelerated beam near the entrance of the drift tube. The antiproton beam arrives from the left at 100 keV and exits the drift tube with only 1 keV since the voltage on the tube is switched to ground while the ion bunch is inside. Despite different combinations of the different voltages, the output beam is relatively divergent so that an additional Einzel lens is required downstream.

In addition to steering electrodes, the ELENA LNE50 extraction beamline includes two quadrupole doublets, which can produce a convergent, parallel, or diverging beam at the decelerator entrance. The trajectories shown in Fig. 1 were calculated with the parallel ELENA beam, which was found to be the most favorable. The beam diameter is 18 mm. A drawing of the decelerator system vacuum chambers and electrodes is shown in Fig. 2. The dimensions were chosen so that the electrodes are large enough (100 mm diameter) to accept the beam without difficulty but far enough from the DN250CF chamber walls to avoid sparking. The deceleration electrodes are arranged as triplets, insulated via MACOR R (Machinable glass ceramic by Corning) to a support frame in the chamber. The overall length is 1225 mm with an additional 225 mm chamber housing a low-energy Einzel-lens assembly to focus the decelerated beam into the GBAR reaction chamber downstream.

From the simulations shown in Fig. 1 relatively high voltages are required on the decelerator electrodes, making the geometry and connections nontrivial. It is critical not to place wires near the chamber walls and to avoid any sharp edges. Photographs of the second electrode set and the pulsed drift tube are shown in Fig. 3. The drift tube, required to hold -100 kV, is supported by a specially designed "cradle" (Fig. 3, right) made from MACOR R to avoid the presence of any metallic surfaces. The connection was made using a metal rod, screwed perpendicularly into the drift tube itself. Connecting the power supplies to the high-voltage vacuum feedthroughs required embedding the wire inside a rounded bushing, since the threads on the feedthroughs create corona discharge in air if not covered. Because of the exceptionally high voltage on the drift tube, the air-side feedthrough was connected inside a hollow (brass) metal ball. Connecting the drift tube to the high-voltage switch (150 kV Behlke model HTS 1501-20-LC2) was done through high-voltage resistors, each of which was connected using metallic balls to avoid edges. A photograph of the switching circuit is shown in Fig. 4 along with the schematic diagram. The various elements are clad with teflon for increased protection against discharges (see inset of Fig. 4) and enclosed in a copper box for electromagnetic shielding.

Three high-voltage, non-inductive (Nicrom Electronics, series 500) resistors are visible in Fig. 4. A 1 GΩ resistor (right) avoids short circuiting the power supply while switching and limits the charging current while slowing the charging time to avoid sparking. After discharge damage that prevented applying the full voltage, this resistor was changed to 200 MΩ to compensate for the leakage. The vertical 1 kΩ resistor limits transient currents to the admissible rating of the switch (150 A). Finally, a 120 Ω resistor (left) matches the switch impedance and stray capacitance to the load. We obtained a risetime of roughly 200 ns.

Each electrode lens of the decelerator is connected to a separate power supply, which is controlled via a LabVIEW R program and a National Instruments compact-DAQ interface. An essential step before using the de- celerator is the high-voltage conditioning of each electrode. When applying over 10 kV to an electrode, contamination on the surfaces provokes small discharges which cause spikes in vacuum pressure. The high-voltage conditioning actually cleans and helps outgas the surfaces but must not be rushed since an arc easily leaves a trace that can be impossible to burn away. After mounting and baking the chambers, this process took several hours for each electrode to reach its required voltage.

A photograph of the decelerator system vacuum chambers connected to the ELENA beamline is shown in Fig. 5. A 300 l/s ion pump is mounted under the first set of deceleration electrodes and a vacuum of 1 × 10 -9 mbar was achieved after baking to about 200 degrees Celsius. (Note that neither pump nor port are shown in Fig. 2.)

Commissioning tests

The decelerator system was first tested off-line with a 50 keV proton beam, provided by a Penning discharge source and hydrogen-gas leak. A description of the test bench with results from time-of-flight and energydispersion tests were reported in [START_REF] Husson | An antiproton deceleration device for the GBAR experiment at CERN[END_REF][START_REF] Husson | Deceleration of antiprotons from cern's elena synchrotron and transport of antimatter beams through the gbar experiment[END_REF]. First tests at CERN were carried out using a H -plasma source connected to ELENA. The H -beam was injected into the ring at 85 keV (sparking in the isolation transformer prevented higher beam energy). After several turns in the ring, the beam was kicked into the LNE50 extraction beamline to the decelerator, with its electrodes grounded. A combination of possible beam optics and diagnostic alignment problems seems to have prevented the LNE50 quadrupoles from focusing the beam through the first apertures of the decelerator line. As a result, we were not able to transport the beam to the decelerator with the calculated nominal optical element values.

We also performed tests with antiproton bunches decelerated from 5.3 MeV by the ELENA storage ring and delivered at 100 keV. While the AD cycle for antiprotons is much slower (one pulse every 110 s, compared to about every 5 s using the H -source) the antiproton annihilation detected by scintillators along the beamline provides an excellent diagnostic for beam 2). The 100 kV Behlke switch is located below the system. The beamline connected to the ELENA extraction line (LNE50) is visible on the left side, as is the white wall separating the GBAR and ELENA zones. The high-voltage protection cage is also visible (the foreground panel was removed for the photograph).

losses. The deceleration of ELENA antiprotons is illustrated by the following discussion and figures. First, Fig. 6 illustrates the GBAR beam-line elements, detectors and relative distances after the handover point at the end of the LNE50 beamline (the wall can be seen in the photograph of Fig. 5). The po- 1). The distance from the end of the drift tube to the MCP is 1170 mm and from the upstream scintillator to the MCP is 700 mm. sition marked "p-Quadrupole" in Fig. 6 is a 12 mm horizontal collimation of an electrostatic quadrupole bender used to steer protons in from a 90-degree angle. During beam tuning with the MCP imaging detector, the shadow of this collimator was clearly visible. With antiprotons an additional scintillator (not shown in the figure) recorded a relatively large annihilation signal, the time of which corresponded to the time of flight of the 100 keV antiprotons from the ELENA deflector. We estimated the resulting transmission to be about 25%.

As the tests were performed in parallel with the commissioning of the ELENA machine, it was not possible to perform systematic studies. A critical parameter for successful deceleration of the beam pulse is the timing of the drift-tube switch with respect to the ELENA extraction (an electrostatic septum that is switched from ground to a given extraction voltage). This pulse was fed into a digital delay generator to generate the trigger for the switch.

Fig. 7 shows screen shots of the scintillator and MCP detector oscilloscope traces and MCP antiproton-beam images (inset). The top panel was recorded with the trigger too early and the bottom panel with the trigger too late. An early trigger means that the drift tube is pulsed to ground before the antiproton pulse arrives. Therefore the antiprotons see no potential on the drift tube and experience no deceleration. The late trigger causes the drift tube voltage to remain at its set value (here it was -90 kV) during the transit of the antiproton pulse. This results in an initial deceleration of the pulse and reacceleration to 90 keV after transiting the drift tube at 10 keV. (There were no voltages on the other electrodes for this measurement.) The difference in time of flight between the full-energy beam and slowed/re-accelerated beam is calculated to be about 200 ns, which is visible from the oscilloscope traces.

The scintillator signals in Fig. 7 show a time difference of roughly 150 ns between annihilation of antiprotons hitting the upstream triplet and the downstream MCP. This corresponds quite well to the calculated time of flight of 160 ns for 100 keV antiprotons over the 700 mm separating the detectors.

The (inset) MCP images in Fig. 7 show the beam to be relatively well centered, but when decelerated by the drift tube a vertical shift of about 15 mm is visible (the MCP diameter is 42 mm, inclined by 45 degrees). The beam is somewhat focused by the drift tube since it forms a long Einzel lens. Because of the possible alignment problems (mentioned at the beginning of this section) it seems plausible that the beam was not injected along the decelerator drift-tube axis, which could explain the movement of the beam under deceleration.

Because of the discharge on the drift tube mentioned earlier, we were only able to apply -92 kV before the maximum rated current of the supply was reached. The lowest achievable beam energy was therefore only 8 keV.

In the meantime, we have learned that the drift tube insulator assembly may be insufficiently shielded, forming a so-called triple junction effect at the insulator/conductor interface [START_REF] Faircloth | Technological Aspects: High Voltage[END_REF]. This would explain not only the discharge but also the deflection of the decelerated beam, due to charging on the insulator. The "cradle" is therefore being redesigned.

Fig. 8 illustrates the deceleration of the 100 keV ELENA beam to 8 keV under the aforementioned conditions. On the right side of the figure, the CCD camera image of the MCP shows two distinct beam spots. We believe the upper spot corresponds to the decelerated fraction of the beam pulse and the lower spot corresponds to a "fast" (non-decelerated) fraction. This is corroborated by the static test shown in Fig. 7 where the beams are not seen at the same position because of the early and late triggering. The alignment problem mentioned earlier leads to shifts in beam position and angle which are amplified by the deceleration process. This effect has been reproduced by simulations.

But while the static test might imply that the lower spot corresponds to the decelerated antiprotons, we discovered in subsequent tests that the triple-junction effect explained by Faircloth [START_REF] Faircloth | Technological Aspects: High Voltage[END_REF] can also charge the insulator and slightly deflect the decelerated beam downward. Since the injection conditions were not the same as for the static case, it is not possible to say with absolute certainty.

The MCP signal (red trace in Fig. 8) shows two maxima with a time difference of about 650 ns, corresponding to two groups of antiprotons: one "fast" (non-decelerated) group and one "decelerated" group. As mentioned, the reaction chamber MCP is 1170 mm downstream of the drift tube. The calculated time-of-flight difference for antiprotons at 100 and 8 keV over this distance is 675 ns, in good agreement with the detected MCP pulses shown in Fig. 8 (although the timing resolution is rather limited). There is also a continuum between the two peaks caused by antiprotons that experience the fringe field at the exit of the drift tube, convoluted with the 200 ns switching time. We believe this happens because the ELENA pulse length was likely longer than the 300 ns design value so that the entire pulse could not fit inside the drift tube before switching.

From integrating the areas under the peaks (assuming identical MCP signal response for 100 keV and 8 keV antiprotons) we find the decelerated fraction is about 25% compared to the fast antiprotons. Because of the compressed commissioning schedule of ELENA, it was not possible to test different optical configurations for the decelerating lenses.

To explore the continuum effect visible in Fig. 8, ion trajectory calculations were performed to simulate the MCP signal, with the results shown in Fig. 9. As during the experimental tests, -92 kV was applied to the drift tube with the other decelerating lenses at ground. The three panels show different input pulse durations of 10, 400 and 600 ns (the design value is 300 ns [START_REF] Bartmann | The ELENA facility[END_REF]). The switching pulses were modeled using an exponential decay, with the measured time constant of 200 ns. The switch is always triggered while the beam is centered in the drift tube. For the hypothetical case of 10 ns (top panel), a single decelerated pulse is seen, as expected. The increased width of the peak is due to the large energy spread quoted in the ELENA design [START_REF] Bartmann | The ELENA facility[END_REF]. When the beam occupies the areas near the drift-tube edges (middle panel), the antiprotons experience varying amounts of re-acceleration and "leak out" of the main peak to earlier arrival times. With the pulse protruding even farther out of both ends of the drift tube (bottom panel), the continuum seen in the measurements (Fig. 8, left panel) appears. The recorded MCP signal (slightly shifted in time and scaled in amplitude) is also included in the figure for comparison.

The simulations showing the 100 keV and 8 keV antiproton-deceleration peaks agree with the measured 650 ns time-of-flight difference to within about 25 ns, or better than 4%. The ELENA pulse length was not monitored during the tests. A CERN internal note concerning low-level RF tests during the ELENA commissioning reports a typical pulse of 600 ns that was improved at one stage to 200 ns (see Fig. 34 in [START_REF] Angoletta | New llrf capabilities and beam results for the second year of elenas commissioning[END_REF]). The 600 ns pulse length qualitatively matches our measurements.

Ref. [START_REF] Bartmann | The ELENA facility[END_REF] quotes an estimated momentum spread of 0.25%, which would correspond to a very large 500 eV energy spread. A more optimistic energy spread of only 100 eV was used in the simulations. The simulated peaks have larger widths compared to the measurement, which may indicate that the projected ELENA energy spread of 0.5% is too conservative.

In a final test, the decelerated antiprotons were transported 2 m downstream of the reaction chamber, through a beam switchyard designed to separate unreacted antiprotons from neutral antihydrogen and the antihydrogen ions (see chapter 6 of [START_REF] Husson | Deceleration of antiprotons from cern's elena synchrotron and transport of antimatter beams through the gbar experiment[END_REF]). An antiproton signal was detected with an MCP mounted on the straight section and could be moved laterally by applying the switchyard-electrode voltages (see sections 7.5 and 8.5 of [START_REF] Latacz | Study of the antihydrogen atom and ion production via charge exchange reaction on positronium[END_REF]). Again, due to experimental restrictions, we could not obtain quantitative information.

Summary

We have presented a new scheme using electrostatic optics and fast highvoltage switching for decelerating antiproton bunches down to keV energies for precision experiments such as GBAR at the CERN AD facility. Such a scheme avoids losses associated with passing the beam through thin foils, and should offer increased efficiency. A detailed technical description of the decelerator design and realization has been given. Prior to CERN's second Long Shutdown (LS2) we successfully commissioned the first 100 keV pulsed drift tube and electrostatic-lens system built to decelerate the pulsed antiproton beam from the ELENA storage ring of CERN's AD "antimatter factory". Because the tests were performed during the very short commissioning of ELENA, only limited results could be obtained. Our results give clear evidence of antiproton pulses decelerated to 8 keV. Since the ELENA pulses were longer than the design value of 300 ns, only a fraction of the antiprotons were decelerated. This situation will be improved when CERN restarts in mid-2021.

Figure 1 :

 1 Figure 1: Antiproton trajectories in the decelerator (travelling left to right), calculated by the SIMION R program for the potentials indicated on the six (100 mm diameter) electrodes that slow and focus the beam. The potential on the drift tube (-99 kV) is switched to ground when the antiproton pulse is inside. Input beam parameters are the nominal ELENA values given in the text. The output beam energy is 1 keV.

Figure 2 :

 2 Figure 2: Computer-aided design drawing of the DN250CF vacuum chambers with electrode lengths indicated (all diameters are 100 mm).

Figure 3 :

 3 Figure 3: Photographs of: (left) the second set of decelerating electrodes, mounted in their 250CF vacuum chamber on MACOR R stand-offs; (right) the pulsed drift tube, machined from stainless steel, mounted on a MACOR R "cradle" for stability and insulation.

Figure 4 :

 4 Figure 4: Photograph of the switching circuit, high-voltage connections, resistors (grey) and switch (black). Connection to the 100 kV supply is on the right. Inset photograph shows the resistors with their teflon cladding, installed in a copper Faraday cage. Lower insert shows the circuit diagram (values discussed in the text).

Figure 5 :

 5 Figure5: Photograph of the installed decelerator system and high-voltage connections (see technical drawing in Fig.2). The 100 kV Behlke switch is located below the system. The beamline connected to the ELENA extraction line (LNE50) is visible on the left side, as is the white wall separating the GBAR and ELENA zones. The high-voltage protection cage is also visible (the foreground panel was removed for the photograph).

Figure 6 :

 6 Figure 6: Schematic view of the decelerator optical elements, PbW0 4 scintillator detectors and the MCP detector (lenses and drift tube are as in Figure1). The distance from the end of the drift tube to the MCP is 1170 mm and from the upstream scintillator to the MCP is 700 mm.

Figure 7 :

 7 Figure 7: Static voltage operation showing detector-signal oscilloscope traces: HV-switch trigger (green -the black dotted line is the true switching time, visible from the highamplitude noise); a PbWO 4 crystal located above the quadrupole triplet (yellow); a PbWO 4 crystal located above the MCP (blue); the MCP signal (red). The top panel corresponds to an early trigger (no deceleration) and the bottom to a late trigger (90 keV deceleration and subsequent reacceleration to ground exiting the drift tube). The 200 ns ToF difference between the full-energy and slowed/re-accelerated beam annihilation signals is indicated. Insets show antiproton-beam images recorded by a CCD camera facing upwards to the inclined MCP detector.

Figure 8 :

 8 Figure 8: Demonstration of antiproton deceleration from 100 to 8 keV. As in Fig. 7 the right image was recorded by a CCD camera facing the MCP. The left panel shows recorded oscilloscope traces: Behlke-switch trigger (green); PbWO 4 crystal located above the upstream lenses (yellow); PbWO 4 crystal located above the MCP (blue), and MCP signal (red). The trigger was set to switch the drift-tube voltage while the pulse was inside. The MCP trace shows both the 8 keV decelerated component (later peak) and part of the undecelerated 100 keV beam (earlier peak). The CCD image (right) shows these two components that are spatially distinct, as seen separately in Fig. 7.

  b e r o f p a r t i c l e s t i m e o f f l i g h t ( µs )

Figure 9 :

 9 Figure 9: Simulated time-of-flight histograms (red columns) of antiprotons decelerated from 100 keV to 8 keV with different injected pulse durations. Top panel shows a beam pulse of only 10 ns for reference. The middle panel shows a 400 ns pulse that results in a decelerated pulse of 497 mm in length, which clearly does not fit into the drift tube. The bottom panel shows a 600 ns pulse that produces decelerated and re-accelerated beam components. The recorded MCP pulse is also shown (solid back line).

Acknowledgements

We thank C. Bachelet, J. Bourçois, J. Bui, S. Cabaret, P. Dupré, P. Duarte, S. Hervé, D. Le Du, H. Lefort, A. Limongi, V. Manea, S. Martineau, K. Nguyen, S. Pitrel and H. Ramirijaona from the CSNSM, C. Doré and J.-M. Isac from the LKB, J.-L. Babigeon from the LAL, D. Desforges, Ph. Hardy, S. Javello, D. Pierrepont and C. Vuillemin from the CEA and F. Butin from CERN for their various contributions. We also thank the ELENA team for their help and cooperation during the tests.

The decelerator project was supported by France's IN2P3, by the Agence National de Recherche under project no. ANR-14-CE33-0008 (ANTION), and by the Laboratoire d'Excellence P2IO (ANR-10-LABX-0038) in the framework Investissements d'Avenir (ANR-11-IDEX-0003-01).