Philippe Thomas
email: philippe.thomas@univ-lorraine.fr

Marie-Christine Suhner
email: marie-christine.suhner@univ-lorraine.fr

A new multilayer perceptron pruning algorithm for classification and regression applications

Keywords: neural network, multilayer perceptron, pruning, classification, regression, data mining

Optimizing the structure of neural networks remains a hard task. If too small, the architecture does not allow for proper learning from the data, whereas if the structure is too large, learning leads to the well-known overfitting problem. This paper considers this issue, and proposes a new pruning approach to determine the optimal structure. Our algorithm is based on variance sensitivity analysis, and prunes the different types of unit (hidden neurons, inputs, and weights) sequentially. The stop criterion is based on a performance evaluation of the network results from both the learning and validation datasets. Four variants of this algorithm are proposed. These variants use two different estimators of the variance. They are tested and compared with four classical algorithms on three classification and three regression problems. The results show that the proposed algorithms outperform the classical approaches in terms of both computational time and accuracy.

Introduction

From the first works of Rumelhart and McClelland [START_REF] Rumelhart | Parallel distributed processing: Exploration in the microstructure of cognition[END_REF], artificial neural network models have been successfully applied to solve many different problems, including the identification of dynamical systems, pattern classification, adaptive control, and function approximation. Among these artificial neural network models, the multilayer perceptron (MLP) is, by far, the most popular architecture because of its structural flexibility, good representational capabilities, and the availability of a large number of training algorithms [START_REF] Han | A structure optimisation algorithm for feedforward neural network construction[END_REF]. This model is used for both classification and regression tasks. The goal of classification is to map the data into predefined groups or classes. In the regression phase, the aim is to map data items to a real-valued prediction variable [START_REF] Patel | A review on ensemble of diverse artificial neural networks[END_REF].

For both classification and regression, the same question must be addressed: how many nodes should be used in each layer? Despite the wealth of literature on the MLP, defining the optimal architecture remains a hard task. If too small, the architecture cannot learn from the data properly, whereas if the structure is too large, learning leads to the well-known overfitting problem. To avoid overfitting, we can apply early stopping [START_REF] Drucker | Effect of pruning and early stopping on performance of a boosting ensemble[END_REF], a robust minimization criterion [START_REF] Kerlirzin | Robustness in multilayer perceptrons[END_REF][START_REF] Thomas | Neural modeling of an induction furnace using robust learning criteria[END_REF],

regularization approaches [START_REF] Williams | Bayesian regularization and pruning using a Laplace prior[END_REF][START_REF] Bartlett | For valid generalization, the size of the weights is more important than the size of the network[END_REF][START_REF] Cawley | Preventing over-fitting during model selection via Bayesian regularisation of the hyper-parameters[END_REF], or determine the optimal structure of the network.

The latter method allows us to obtain a simpler and smaller model. Hence, a crucial step in designing the MLP is network model selection [START_REF] Bishop | Neural networks for pattern recognition[END_REF]. Many algorithms have been proposed to determine the optimal architecture of the network. However, because this determination is an NP-hard problem, most existing algorithms are approximate and produce near-optimal solutions [START_REF] Beigy | A learning automata-based algorithm for determination of the number of hidden units for three-layer neural networks[END_REF].

These algorithms can be classified into four groups: pruning algorithms, constructive algorithms, hybrid algorithms, and evolutionary algorithms.

Pruning algorithms learn using an over-sized structure, and then, in a second step, eliminate spurious parameters and/or neurons. One of the main advantages of these algorithms is that they are able to perform feature selection simultaneously [START_REF] Kruschke | Improving generalization in backpropagation networks[END_REF][START_REF] Lecun | Optimal brain damage[END_REF][START_REF] Hassibi | Second order derivatives for network pruning: optimal brain surgeon[END_REF][START_REF] Reed | Pruning algorithm -A survey[END_REF][START_REF] Jutten | Pruning methods: a review[END_REF]. Constructive algorithms start from a small initial architecture, and add new hidden units or layers until the results are acceptable [START_REF] Mezard | Learning in feedforward neural networks: the tiling algorithm[END_REF][START_REF] Fahlman | The cascade-correlation learning architecture[END_REF][START_REF] Yeung | Automatic determination of network size for supervised learning[END_REF][START_REF] Chentouf | Combining sigmoids and radial basis function in evolutive neural architecture[END_REF]. Hybrid algorithms combine pruning and constructive approaches [START_REF] Hirose | Back-propagation algorithm which varies the number of hidden units[END_REF][START_REF] Nabhan | Toward generating neural network structures for function approximation[END_REF][START_REF] Narasimha | An integrated growing-pruning method for feedforward network training[END_REF], whereas evolutionary algorithms conduct a search across the parameter space and determine the optimal structure using some performance index [START_REF] Whitley | The evolution of connectivity: pruning neural networks using genetic algorithms[END_REF][START_REF] Angeline | Evolutionary algorithm that construct recurrent neural networks[END_REF].

This paper focuses on pruning algorithms, and proposes a new method based on the variance sensitivity analysis proposed by Engelbrecht [START_REF] Engelbrecht | A new pruning heuristic based on variance analysis of sensitivity information[END_REF]. We prune different types of unit (hidden neurons, inputs, and weights) sequentially, and use a stop criterion based on a performance evaluation of the network results from both the learning and validation datasets. The main goals of this algorithm are to improve structure determination and minimize computational time for both classification and regression. Four variants of this algorithm are proposed.

The remainder of this paper is organized as follows. Section 2 presents a brief overview of structure determination and pruning algorithms, and Section 3 describes the network architecture and learning algorithm. Section 4 introduces the proposed pruning algorithm and its four variants. Sections 5 and 6 present the results obtained from benchmark classification and regression tasks, respectively.

The results given by the proposed algorithms are compared with those obtained by conventional pruning algorithms. Finally, Section 7 concludes the paper.

Brief overview of structure determination 2.1 Problem origination

As explained previously, determining the optimal architecture of a neural network is an NP-hard problem. The original work on this problem is Kolmogorov's theorem, which states that any continuous function on an n-dimensional cube can be represented by the sum and superposition of continuous functions of one variable [START_REF] Kolmogorov | On the representational of continuous functions of many variables by superpositions of continuous functional of one variable and addition[END_REF]. Cybenko [START_REF] Cybenko | Approximation by superposition of a sigmoïdal function[END_REF] and Funahashi [START_REF] Funahashi | On the approximate realisation of continuous mapping by neural networks[END_REF] have proved that sigmoidal functions are suitable for this work, and so neural networks with only one hidden layer that use a sigmoidal function can be seen as universal approximators.

However, these results are not sufficient to determine the size of this hidden layer. Hecht-Nielsen [START_REF] Hecht-Nielsen | Kolmogorov's mapping neural network existence theorem[END_REF] has proved that any continuous function can be represented by a neural network that has only one hidden layer with exactly 2ni+1 neurons, where ni is the number of inputs. However, the activation function used in his work is more complex than the sigmoidal one. Huang [START_REF] Huang | Learning capability and storage capacity of two-hidden-layer feedforward networks[END_REF] has extended this work, and proved that, with two hidden layers, 2 ( 2) o n N + hidden units allocated between the two hidden layers are enough to learn N samples with negligibly small error (no denotes the number of outputs). The problem here is to fit a function with a finite number of (generally noisy) samples. In this case, the network may learn the noise on the function, and not the function itself, leading to an overfitting problem [START_REF] Dreyfus | Réseaux de neurones: méthodologies et applications[END_REF].

Thus, no exact paradigm exists to estimate the optimal neural network, with different approaches and algorithms being used to determine its structure.

Optimal structure determination approaches: a brief overview

The oldest and most primitive approach to determining the optimal structure is simple trial-and-error, which can lead to severely suboptimal structures.

Another approach is to perform an exhaustive search. However, this is not a realistic option for many real applications. Moreover, an exhaustive search will be complicated by the noisy fitness evaluation problem [START_REF] Yao | Evolutionary artificial neural networks[END_REF].

Evolutionary approach

Evolutionary algorithms can be seen as an extension of the exhaustive search using mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Evolutionary approaches have been used in a restrictive way to prune oversized structures [START_REF] Huang | A constructive hybrid structure approach to solve routing problems[END_REF][START_REF] Mantzaris | Genetic algorithm pruning of probabilitic neural networks in medical disease estimation[END_REF]. However, this approach may be used with a hybrid goal (construction and pruning) [START_REF] Stathakis | How many hidden layers and nodes?[END_REF][START_REF] Yang | An evolutionary constructive and pruning algorithm for artificial neural networks and its applications[END_REF]. Evolutionary algorithms may be used to simultaneously optimize the architecture and weights [START_REF] Angeline | Evolutionary algorithm that construct recurrent neural networks[END_REF][START_REF] Maniezzo | Genetic evolution of the topology and weight distribution of neural networks[END_REF][START_REF] Wilamowski | Computing gradient vector and Jacobian matrix in arbitrarily connected neural networks[END_REF] or to concentrate on the structure [START_REF] Mantzaris | Genetic algorithm pruning of probabilitic neural networks in medical disease estimation[END_REF][START_REF] Stathakis | How many hidden layers and nodes?[END_REF][START_REF] Yang | An evolutionary constructive and pruning algorithm for artificial neural networks and its applications[END_REF][START_REF] Puma-Villanueva | Evolving arbitrarily connected feedforward neural networks via genetic algorithm[END_REF].

The use of evolutionary algorithms for structure determination introduces two sources of noise, one from the initialization of weights, and the other from the chosen optimizer. In contrast, the simultaneous evolution of architecture and weights is muddled by the well-known permutation problem. Additionally, the computational cost of implementing evolutionary algorithms, even for structure determination alone, may become prohibitive [START_REF] Puma-Villanueva | A constructive algorithm to synthesize arbitrarily connected feedforward neural networks[END_REF].

Constructive approach

The goal of constructive approaches is to determine the optimal structure of the network by sequentially adding hidden neurons or hidden layers to a small initial structure. Many algorithms have been proposed under this paradigm [START_REF] Kwok | Constructive algorithms for structure learning in feedforward neural networks for regression problems[END_REF]. Among these algorithms, we can cite dynamic node creation and its variants [START_REF] Ash | Dynamic node creation in backpropagation networks[END_REF][START_REF] Setiono | Use of a quasi-Newton method in a feedforward neural network construction algorithm[END_REF], activity-based structure-level adaptation [START_REF] Lee | Neural network systems techniques and applications: Algorithms and architectures[END_REF][START_REF] Weng | An adaptive structural neural network with application to EEG automatic seizure detection[END_REF], cascade correlation [START_REF] Fahlman | The cascade-correlation learning architecture[END_REF][START_REF] Prechelt | Investigation of the CasCor family of learning algorithms[END_REF], and the constructive one-hidden-layer algorithm and its variants [START_REF] Kwok | Constructive algorithms for structure learning in feedforward neural networks for regression problems[END_REF][START_REF] Ma | New training strategies for constructive neural networks with application to regression problems[END_REF][START_REF] Ma | Constructive feedforward neural networks using Hermite polynomial activation functions[END_REF]. Most of these algorithms lead to more complex structures by mixing various activation functions [START_REF] Chentouf | Combining sigmoids and radial basis function in evolutive neural architecture[END_REF][START_REF] Ma | Constructive feedforward neural networks using Hermite polynomial activation functions[END_REF] or adding new hidden layers with connections between neurons that are not in successive layers [START_REF] Fahlman | The cascade-correlation learning architecture[END_REF][START_REF] Puma-Villanueva | A constructive algorithm to synthesize arbitrarily connected feedforward neural networks[END_REF]. Hence, these algorithms lead to neural network structures that are not strictly feedforward, and require specific algorithms to learn parameters while the structure grows [START_REF] Ma | New training strategies for constructive neural networks with application to regression problems[END_REF][START_REF] Islam | A new constructive algorithm for architectural and functional adaptation of artificial neural networks[END_REF]. Moreover, these algorithms can lead to suboptimal networks [START_REF] Kwok | Constructive algorithms for structure learning in feedforward neural networks for regression problems[END_REF], or become trapped in local minima because the error surface of a smaller network is more complicated and includes more local minima than the error surface of a larger network [START_REF] Bebis | Feed-forward neural networks: why network size is so important[END_REF][START_REF] Khosravi | A prediction interval-based approach to determine optimal structures of neural network metamodels[END_REF].

Pruning approach

In pruning approaches, an oversized structure is first learned, before spurious parameters are eliminated in a second step. Many algorithms using this approach have been proposed, and these can be classified into three broad groups: magnitude-based (pruning during learning), brute-force, and sensitivity-based (post-learning pruning) [START_REF] Reed | Pruning algorithm -A survey[END_REF][START_REF] Jutten | Pruning methods: a review[END_REF].

In magnitude-based approaches (pruning during learning), a term is added to the objective function for choosing the most efficient solution. For example, a term proportional to the sum of all weight magnitudes favors a solution with small weights; those that are nearly zero are not likely to influence the output much, and can thus be eliminated [START_REF] Reed | Pruning algorithm -A survey[END_REF]. This approach prunes the network by driving the weights toward zero during learning, and various different penalty terms and weight decays have been proposed and studied [START_REF] Cawley | Preventing over-fitting during model selection via Bayesian regularisation of the hyper-parameters[END_REF][START_REF] Chauvin | A back-propagation algorithm with optimal use of hidden units[END_REF][START_REF] Weigend | Generalization by weight-elimination with application to forecasting[END_REF][START_REF] Nowland | Simplifying neural networks by soft weight-sharing[END_REF][START_REF] Larsen | Generalization performance of regularized neural network models[END_REF][START_REF] Leung | On the selection of weight decay parameter for faulty networks[END_REF][START_REF] Wang | Computational properties and convergence analysis of BPNN for cyclic and almost cyclic learning with penalty[END_REF].

Brute-force pruning methods (post-learning pruning) set the weights to zero oneby-one, and evaluate the change in the error. If it increases too much, then that weight is restored; otherwise, the element is removed. Setiono and Leow [START_REF] Setiono | Pruned neural networks for regression. 6 th Pacific RIM Int[END_REF] used this approach to prune hidden neurons and inputs in two steps.

Sensitivity-based approaches (post-learning pruning) evaluate the sensitivity of the error function to the removal of an element. Some algorithms consider the change in the error function due to small changes in the values of the weights.

Measures of the relative effect of the different weights, or saliencies, can be computed, and weights with low saliencies are deleted. Optimal Brain Damage [START_REF] Lecun | Optimal brain damage[END_REF], Optimal Brain Surgeon (OBS) [START_REF] Hassibi | Second order derivatives for network pruning: optimal brain surgeon[END_REF], and all algorithms derived from these [START_REF] Norgaard | System identification and control with neural networks[END_REF][START_REF] Thomas | Robust pruning for multilayer perceptrons[END_REF] use a second-order Taylor expansion of the error function to estimate how the training error will change as the weights are perturbed. Leung et al. [START_REF] Leung | A pruning method for the recursive least squared algorithm[END_REF] applied the same approach for a recursive least-squares algorithm, whereas Tang et al. [START_REF] Tang | H∞ Filtering method for neural network training and pruning[END_REF] used the error covariance matrix obtained during learning in a similar way to the Hessian matrix in the OBS algorithm.

The output of sensitivity analysis methods is based on a variance analysis of sensitivity information, given by the derivative of the neural network output with respect to the parameters [START_REF] Engelbrecht | A new pruning heuristic based on variance analysis of sensitivity information[END_REF]. These are powerful methods, because the network structure inherently contains all of the information needed to compute these derivatives efficiently [START_REF] Ricotti | Neural network approach to sensitivity and uncertainty analysis[END_REF]. Zeng and Yeung [START_REF] Zeng | Hidden neuron pruning of multilayer perceptrons using a quantified sensitivity measure[END_REF] inserted an input perturbation and studied its effect on the output sensitivity. Chandrasekaran et al. [START_REF] Chandrasekaran | Pruning of basis functions in nonlinear approximators[END_REF] proposed a sensitivity-based method based on linear unit models, and Lauret et al.

[67] used the extended Fourier amplitude test to quantify the relevance of the hidden neurons. Augasta and Kathirvalavakumar [START_REF] Augasta | A Novel Pruning Algorithm for Optimizing Feedforward Neural Network of Classification Problems[END_REF] defined the significance of a neuron as the sum-norm of its output. They then compared this significance to a threshold to determine which neurons must be pruned.

Levin et al. [START_REF] Levin | Fast pruning using principal components[END_REF] applied principal component analysis to select elements for removal, while Medeiro and Barreto [START_REF] Medeiros | A novel weight pruning method for MLP classifiers on the MAXCORE principle[END_REF] determined which weights to prune by evaluating the correlation between error signals associated with the neurons of a given layer and the error signal propagated back to the previous layer. Weights that generate lower correlations are not relevant, and can therefore be pruned. [START_REF] Beigy | A learning automata-based algorithm for determination of the number of hidden units for three-layer neural networks[END_REF] proposed an automaton that can determine whether a hidden neuron should be preserved or pruned. This automaton exploits the variance of the activation of a neuron. Liang [START_REF] Liang | Removal of hidden neurons in MLP by orthogonal projection and weight crosswise propagation[END_REF] developed an orthogonal projection to determine the importance of hidden neurons.

Beigy and Meybodi

Although there are many different pruning methods, the main ideas underlying most of them are similar. They all try to establish a reasonable relevance measure for a specified parameter (input, weight, or neuron), so that the pruning action will hopefully have the least effect on the performance of the network [START_REF] Zeng | Hidden neuron pruning of multilayer perceptrons using a quantified sensitivity measure[END_REF].

One of the disadvantages of pruning algorithms is their heavy computational burden, as the majority of the training time is spent on networks that are larger than necessary [START_REF] Han | A structure optimisation algorithm for feedforward neural network construction[END_REF].

Hybrid approach

Hybrid algorithms combine pruning and constructive approaches. Nabhan and Zomaya [START_REF] Nabhan | Toward generating neural network structures for function approximation[END_REF] exploited an intelligent generate-and-test procedure that evaluates the learning performance of the structure, and then modifies it by exploring different alternatives and selecting the most promising. The algorithm modifies the structure of the neural network by adding or deleting neurons and/or layers. [START_REF] Rivals | Neural network construction and selection in nonlinear modeling[END_REF] associated a constructive approach based on conditioning the Jacobian matrix of the candidate neural models with a pruning phase based on statistical tests. Huang et al. [START_REF] Huang | A generalized growing and pruning RBF (GGAP-RBF) neural network for function approximation[END_REF] have developed an on-line training algorithm for a radial basis function neural network, and Narasimha et al. [START_REF] Narasimha | An integrated growing-pruning method for feedforward network training[END_REF] reported a method that starts with an empty network (no hidden unit) and successively adds hidden units, retraining only these new units. In a second step, an orthonormalization pruning algorithm is used to remove spurious parameters.

Rivals and Personnaz

Hsu [START_REF] Hsu | Adaptive growing and pruning neural network control for a linear piezoelectric ceramic motor[END_REF] has exploited an on-line hybrid algorithm to design a neural network controller for a linear piezo-electric ceramic motor. Han and Qiao [START_REF] Han | A structure optimisation algorithm for feedforward neural network construction[END_REF] optimized the network structure by combining error reparation and sensitivity analysis techniques.

The main drawbacks of these algorithms are similar to those of the constructive approach; i.e., they may require particular learning algorithms and can lead to suboptimal networks [START_REF] Khosravi | A prediction interval-based approach to determine optimal structures of neural network metamodels[END_REF].

Selection criteria

The main risk is that current algorithms may become stuck at local minima. Thus, different sets of initial weights are generally used to avoid the local minima trapping problem [START_REF] Beigy | A learning automata-based algorithm for determination of the number of hidden units for three-layer neural networks[END_REF]. In addition, selection criteria are generally used to determine a suitable structure.

For regression problems, many selection criteria have been proposed, such as Akaike's information criterion (AIC), Bayesian information criterion (BIC), root mean square error (RMSE), and mean absolute percentage error (MAPE). Qi and Zhang [START_REF] Qi | An investigation of model selection criteria for neural network time series forecasting[END_REF] compared these criteria and their extensions, and concluded that there is no best method. Egrioglu et al. [START_REF] Egrioglu | A new model selection strategy in artificial neural networks[END_REF] proposed an association of these different criteria to select the optimal structure. AIC and BIC penalize large models, whereas RMSE and MAPE are measures of the deviation of the predicted values from actual values [START_REF] Egrioglu | A new model selection strategy in artificial neural networks[END_REF]. For regression problems, the goal is to reduce the distance between the model and the data. Hence, the RMSE criterion is suitable, and is used in this work:

2 1 1 ( ) N n n n RMSE y y N = = - ∑ (1)
where N denotes the number of data, yn is the n th actual data point, and ˆn y is the predicted value.

In classification problems, the goal is to reduce the number of misclassified data.

Thus, the classical criterion for classification problems is the misclassification rate (error rate or "zero-one" score function) [START_REF] Hand | Principles of data mining[END_REF]:

01 1 1 ( , ) N n n n S I y y N = = ∑ (2)
where I(a, b) = 1 when a ≠ b and 0 otherwise.

A related difficulty arises if there are different costs associated with different misclassifications. In this case, a general loss matrix should be constructed [START_REF] Bishop | Neural networks for pattern recognition[END_REF]. This problem is not considered here.

Network architecture and learning algorithm

Multilayer perceptron

The works of Cybenko [START_REF] Cybenko | Approximation by superposition of a sigmoïdal function[END_REF] and Funahashi [START_REF] Funahashi | On the approximate realisation of continuous mapping by neural networks[END_REF] have shown that a multilayer neural network consisting of only one hidden layer (using a sigmoidal activation function) and an output layer can approximate all nonlinear functions with the desired accuracy. This result explains the great interest in this type of neural network, the aforementioned MLP.

Its structure is given by: The activation function used for the output layer differs according to the problem under consideration. For regression problems, this function is typically chosen to be linear, whereas for classification problems, the network's output should represent the probability that a pattern belongs to the considered class. In this case, the activation function go(.) is generally chosen to be sigmoidal.

2 1 1 1 1 ˆ. . o i n n o h h hi i h h i y g w g w x b b = =     = + +         ∑ ∑ (3)

Learning algorithm

The MLP's parameters (weights and biases) are determined using supervised learning. This performs a local search for the optimum, which implies that the initial set of parameters has a great influence on the final result.

Weights and biases initialization

Many initialization algorithms have been proposed [START_REF] Thomas | Initialization of one hidden layer feed-forward neural networks for non-linear system identification[END_REF]. We use a modification of the Nguyen and Widrow (NW) algorithm [START_REF] Nguyen | Improving the learning speed of 2-layer neural networks by choosing initial values of the adaptive weights[END_REF], which allows a random initialization of weights and biases to be associated with an optimal placement in the input and output spaces. The NW algorithm has been modified by Demuth and

Beale [START_REF] Demuth | Neural networks toolbox user's guide V2[END_REF] for non-normalized inputs.

For regression problems, the output of the network may be a real value if no normalization occurs. To take this into account, a second modification has been introduced concerning the biases and weights connecting the hidden layer to the output layer to deal with non-normalized outputs [START_REF] Thomas | Initialization of one hidden layer feed-forward neural networks for non-linear system identification[END_REF].

Robust learning algorithm

We use a Levenberg-Marquardt algorithm associated with a robust criterion [START_REF] Thomas | Neural modeling of an induction furnace using robust learning criteria[END_REF].

This algorithm performs a local search for the optimum, and the robust criterion accounts for the presence of outliers in the data and has a regularization effect during learning. The robust criterion is based on Huber's model of measurement noise contaminated by outliers [START_REF] Huber | Robust estimation of a location parameter[END_REF]. This model considers the distribution of the noise e as a mixture of two density functions. The first corresponds to the basic distribution of a measurement noise (e.g., normal, variance 2 1 σ ), whereas the second, corresponding to outliers, is an arbitrary symmetric long-tailed distribution (e.g., normal, but with variance 2

σ such that 2 2 1 2 σ σ < ).

Proposed pruning algorithm

Even if the learning algorithm has a regularization effect, it is useful to determine the optimal structure of the network to simplify the model.

Variance nullity measure

The proposed algorithm uses the variance nullity measure (VNM) [START_REF] Engelbrecht | A new pruning heuristic based on variance analysis of sensitivity information[END_REF][START_REF] Ruck | Feature selection using a multilayer perceptron[END_REF][START_REF] Tarr | Multilayered feedforward networks for image segmentation[END_REF], in which the variance of the sensitivity of an input, a hidden neuron's output, or a parameter (weight or bias) is measured for different patterns. If this variance is not significantly different from zero, and if the average sensitivity is small, the input or the hidden neuron under consideration has no effect on the network output.

Therefore, the VNM can be used in hypothesis testing to determine whether an input, hidden neuron, or parameter has a statistical impact on the network using the χ 2 distribution. If not, it must be pruned. This is repeated for each type of element (input, hidden neuron, weight connecting input to hidden layer, bias of hidden layer), and requires the sensitivity of the network output to be determined for each type of element.

Sensitivity to a hidden neuron

To determine whether a hidden neuron h must be pruned, the VNM of the weight 2 h w (h = 1…nh) that connects this hidden neuron to the output neuron must be calculated. For this, we must determine the sensitivity of the network output ŷ to the parameter 2 h w . This sensitivity corresponds to the contribution of this parameter to the output error. This contribution is determined by the partial derivative of the network output ŷ with respect to the parameter 2 h w being considered:

2 ' 1 2 ˆ( ) ( ) ( ) . ( (

)). ( ) ( )

h o h w h y n z n S n g z n x n z n w ∂ ∂ = = ∂ ∂ ( 4
)
where n is the number of data patterns from the learning database and ' ( ( ))

o g z n
is the derivative of the activation function of the output neuron go(). When this activation function is linear (i.e., for regression problems), its derivative is:

' ( ( )) 1 o g z n = (5)
For classification problems, the activation function is chosen to be sigmoidal, and its derivative becomes:

( ) ' ˆ( ( )) ( ). 1 ( ) o g z n y n y n = - (6)

Sensitivity to an input

Similarly, the sensitivity of the network output ŷ to the input i x (i=1…ni) is obtained by taking the partial derivative of the output with respect to the input i x under consideration:

( ) ( )

1 1 1 1 1 2 ' 2 1 1 1 ˆ( ) ( ) ( ) ( ) ( ) ( ) . . . ( ) ( ) ( ) ( ) ( ) ( ( )). . 1 ( ) . h i h n h h x h i h h i n o h h hi h y n y n z n x n z n S n x n z n x n z n x n g z n w x n w = = ∂ ∂ ∂ ∂ ∂ = = ∂ ∂ ∂ ∂ ∂ = - ∑ ∑ (7)
where ' ( ( )) o g z n is given by ( 5) for regression problems and ( 6) for classification problems.

Sensitivity to a weight connecting the input to the hidden layer

The sensitivity of the network output ŷ to the weights 1 hi w (i = 1..., ni; h = 1..., nh) connecting the input to the hidden layers is obtained by taking the partial derivative of the output with respect to the weight 1 hi w under consideration:

( ) ( )

1 1 1 1 1 1 1 1 2 ' 2 1 1 ˆ( ) ( ) ( ) ( ) ( ) ( ) . . . ( ) ( ) ( ) ( ) ( ) ( ( )). . 1

( ) . ( )

h hi h n h h w h hi h h hi n o h h i h y n y n z n x n z n S n w n z n x n z n w n g z n w x n x n = = ∂ ∂ ∂ ∂ ∂ = = ∂ ∂ ∂ ∂ ∂ = - ∑ ∑ (8)
where ' ( ( )) o g z n is given by ( 5) for regression problems and (6) for classification problems.

Sensitivity to the bias of the hidden layer

The sensitivity of the network output ŷ to the bias 1 ( ) ( )

1 1 1 1 1 1 1 1 2 ' 2 1 1 ˆ( ) ( ) ( ) ( ) ( ) ( ) . . . ( ) ( ) ( ) ( ) ( ) ( ( )). . 1 ( ) h h h n h h b h h h h h n o h h h y n y n z n x n z n S n b n z n x n z n b n g z n w x n = = ∂ ∂ ∂ ∂ ∂ = = ∂ ∂ ∂ ∂ ∂ = - ∑ ∑ (9)
where ' ( ( ))

o g z n is given by ( 5) for regression problems and (6) for classification problems.

Determination of the VNM

The sensitivity of the network output to a hidden neuron, input, weight, or bias of the hidden layer can be explained using the unified notation θ is given by equation ( 4), ( 7), [START_REF] Bartlett | For valid generalization, the size of the weights is more important than the size of the network[END_REF], or [START_REF] Cawley | Preventing over-fitting during model selection via Bayesian regularisation of the hyper-parameters[END_REF].

The VNM is the unknown variance 2 k θ σ of the sensitivity of output to parameter θk. Engelbrecht [START_REF] Engelbrecht | A new pruning heuristic based on variance analysis of sensitivity information[END_REF] used a classical estimator for this variance:

( )

2 2 1 ( ) ˆ1 k k k N n S n S N θ θ θ σ = - = - ∑ (10)
where k S θ is the mean of the sensitivity of the output to θk:

1 ( ) k k N n S n S N θ θ = = ∑ (11)
Another estimation of this variance is given by [84]:

2 ˆ0.7 k MAD θ σ = ( 12
)
where MAD is the median of { } ( )

k k S n S θ θ -ɶ , with k S θ ɶ the median of ( ) k S n θ .
This estimator uses the median instead of the mean, and is more robust to the presence of outliers in the data. These two variants are tested and compared in later sections.

A statistical hypothesis test is used to determine whether the VNM of the considered parameter is null. The null hypothesis 0 H (that the variance in parameter sensitivity is approximately zero) and its alternative 1 H are:

2 2 0 0 2 2 1 0 : : k k θ θ σ σ σ σ  ≤   >   H H ( 13
)
where 2 0 σ is a small positive real number.

Using the fact that, under the null hypothesis, the relation:

2 2 0 ( 1). k k N θ θ σ σ - Γ = ( 14
)
has a χ 2 (v) distribution, with 1 N υ =degrees of freedom in the case of N patterns, the test described by ( 13) is performed by comparing ( 14) with the critical value Γc obtained from χ 2 distribution tables:

( ) 2 ,1 C χ υ α Γ = - ( 15
)
where α is the significance level of the test.

If k C θ Γ ≥ Γ , the element under consideration is retained; if not, it is pruned.
The value of 2 0 σ is crucial to the success of this test. If 2 0 σ is too small, no elements will be pruned, whereas if 2 0 σ is too large, too many inputs or hidden neurons will be discarded. Engelbrecht [START_REF] Engelbrecht | A new pruning heuristic based on variance analysis of sensitivity information[END_REF] advises starting with a small value of 2 0 σ (0.001) and multiplying this value by 10 if nothing is pruned, up to a maximal value of 2 max 0.1 σ = .

Neural network sequential pruning algorithm (NNSP)

The proposed NNSP pruning algorithm uses the VNM described above. The main idea of this algorithm is to evaluate and sequentially prune, if necessary, the different types of elements. Our aim is to improve both the computational time and pruning results. Two variants of this algorithm are proposed, and these will be compared in the two next sections.

NNSP hidden neurons before inputs (NNSP-HI)

This algorithm consists of three steps. In this version, these are the pruning of the hidden neurons, pruning of the inputs, and pruning of the weights and biases of the hidden layer. This algorithm is described in Figure 1.

In each step, two stop criteria are used. The first is when 2 0 σ reaches its maximal value 2 max σ . The second is based on the mean absolute deviation (MAD), which measures the performance of the network [START_REF] Setiono | Pruned neural networks for regression. 6 th Pacific RIM Int[END_REF]. Two MAD values are calculated from the learning dataset (subscript T) and the validation dataset (subscript V):

1 1 1 . ( ) ( ) 1 . ( ) ( ) T V N T T T n T N V V V n V M y n y n N M y n y n N = =  = -     = -   ∑ ∑ (16)
The algorithm is initialized by calculating MT and MV [START_REF] Jutten | Pruning methods: a review[END_REF], and by initializing the

memories best T T M M = , best V V M M = and a threshold { } ( ) max max ; * (1 ) best best T V Er M M δ = +
, where δ (tuned to 0.025) is used to avoid an early termination to the pruning. The pruning phase of the hidden neurons starts by learning the oversized MLP.

First, we initialize 2 0 σ , the MAD values MT and MV, and the threshold Ermax. The algorithm then calculates the VNM measures of all the hidden neurons. Two terminates. The input pruning phase can then start. The pruning phases of the inputs and hidden weights and biases takes the same approach as the hidden neuron pruning phase, using equation ( 7) and equations ( 8) and ( 9), respectively.

M T > Er max M V > Er max ( 16

NNSP inputs before hidden neurons (NNSP-IH)

The second version of the algorithm first prunes the inputs, before eliminating spurious hidden neurons and, finally, the weights and biases of the hidden layer.

This algorithm is described in Figure 2, and is very similar to the first algorithm.

As in the first algorithm, two variants of the VNM measures are determined using equation [START_REF] Bishop | Neural networks for pattern recognition[END_REF] or equation [START_REF] Kruschke | Improving generalization in backpropagation networks[END_REF]. These two variants of the algorithms are denoted as NNSP-IH-mean and NNSP-IH-mad, respectively.

Experimental results on classification examples

In this section, the proposed algorithms (four variants) are implemented and compared with the previous pruning methods of VNP [START_REF] Engelbrecht | A new pruning heuristic based on variance analysis of sensitivity information[END_REF], N2PFA [START_REF] Setiono | Pruned neural networks for regression. 6 th Pacific RIM Int[END_REF], OBS [START_REF] Hassibi | Second order derivatives for network pruning: optimal brain surgeon[END_REF], and N2PS [START_REF] Augasta | A Novel Pruning Algorithm for Optimizing Feedforward Neural Network of Classification Problems[END_REF] on three classification problems. For each problem, 20 initial parameter sets are constructed ( §3.2.1) and learned with the robust algorithm ( §3.2.2). The eight pruning algorithms are applied to the same 20 learned networks.

Pima Indians Diabetes dataset

This dataset is available from WEKA [START_REF] Smith | Using the ADAP learning algorithm to forecast the onset of diabetes mellitus[END_REF][86]. The problem is to predict whether a patient will test positive or negative for diabetes according to the criteria given by the World Health Organization. This is a two-class problem with class values of 0 (500 data) and 1 (268 data) interpreted as negative and positive results for diabetes. There are eight input data for each pattern. This dataset was randomly divided into two datasets for learning (375 data) and validation (393 data). The initial learning was performed with 20 hidden neurons.

Table 1 lists the best results obtained with the eight pruning algorithms, as well as for the learning without pruning. These results show that even when learning is performed on an oversized structure, the use of a robust criterion allows the generalization capabilities of the network to be preserved. :

S S S S =    ≠   H H ( 17
)
The null hypothesis 0 H is rejected with a risk level of 5% if: 1.96

N N U N N - = > + ( 18
)
where N10 is the number of cases where the best classifier gives correct class and the compared classifier gives wrong class and N01 is the number of cases where the best classifier gives wrong class and the compared classifier gives correct class. The results of this test are presented in Table 1. They show that the N2PS and VNP algorithms become trapped at a poor local minimum.

The four proposed algorithms outperformed N2PS and VNP, and gave similar results to the N2PFA and OBS algorithms on the validation dataset. However, the four proposed algorithms pruned more parameters and inputs than N2PFA and OBS without degrading the results, and were less time-consuming (requiring ≈50% of the time of N2PFA). The smallest structure was given by the NNSP-HImean algorithm. dataset, the misclassification rate given by these three algorithms belongs to the best class (0.2-0.25) in more than 50% of cases.

Ionosphere dataset

The second classification problem considered the ionosphere dataset, also available from WEKA [86][START_REF] Sigillito | Classification of radar returns from the ionosphere using neural networks[END_REF]. These radar data were collected by a system in Goose Bay, Labrador, Canada. This is a two-class problem with class values of 0 (225 data) and 1 (126 data) interpreted as bad and good. There are 33 input data for each pattern. The dataset was randomly divided into two datasets, one for learning (186 data) and the other for validation (165 data). The initial learning was performed with 10 hidden neurons.

Table 2 shows the best results obtained with the eight pruning algorithms and for the learning without pruning. As for the diabetes dataset, the use of a robust criterion allowed the generalization capabilities of the network to be preserved.

The OBS algorithm produced the best results on the validation dataset, albeit with a considerable computation time. The other algorithms gave equivalent results for the misclassification rate on the validation dataset. This is confirmed by the results of the statistical hypothesis test [START_REF] Mezard | Learning in feedforward neural networks: the tiling algorithm[END_REF], which are always less than 1.96.

However, three of the four proposed algorithms reached these results with a smaller structure than that of OBS (NNSP-HI-mean; NNSP-HI-mad; NNSP-IHmad). It can be seen that, in many cases, the pruning algorithms were unable to find a better structure than the initial one. N2PFA and the four proposed algorithms did not prune a single parameter in 30% of the cases, and N2PS retained an unaltered structure in 75% of cases.

Quality dataset

The third classification problem considered is a real quality classification problem from a robotic lacquering process [START_REF] Noyel | Improving production process performance thanks to neuronal analysis[END_REF]. In this dataset, one defect (stains on back) is considered. This is a two-class problem with class values of 0 (1997 data) and 1

(273 data) interpreted as having no defects and being defective, respectively.

There are 15 input data for each pattern. The dataset was randomly divided into two for learning (1099 data) and validation (1171 data). The initial learning was performed with 25 hidden neurons.

Table 3 shows the best results obtained with the eight pruning algorithms and for the learning without pruning. The results of the statistical hypothesis test [START_REF] Mezard | Learning in feedforward neural networks: the tiling algorithm[END_REF] show that N2PFA, N2PS, and VNP gave statistically worse results than those obtained by the best algorithm, NNSP-HI-mad. However, the use of a robust criterion during learning was not sufficient to avoid the overfitting problem.

Moreover, the four variants of the proposed algorithm outperformed the other algorithms on the validation dataset and produced the smallest structures. Note that the VNP algorithm gave acceptable results in only one case. All other algorithms gave acceptable results in over 50% of cases. NNSP-HI-mean and NNSP-IH-mean, which use the variance estimation in [START_REF] Bishop | Neural networks for pattern recognition[END_REF], were unable to prune any of the hidden neurons. The smallest structure was given by NNSP-HI-mad.

Experimental results on regression examples

In this section, the proposed algorithms (four variants) are compared with VNP [START_REF] Engelbrecht | A new pruning heuristic based on variance analysis of sensitivity information[END_REF], N2PFA [START_REF] Setiono | Pruned neural networks for regression. 6 th Pacific RIM Int[END_REF], OBS [START_REF] Hassibi | Second order derivatives for network pruning: optimal brain surgeon[END_REF], and N2PS [START_REF] Augasta | A Novel Pruning Algorithm for Optimizing Feedforward Neural Network of Classification Problems[END_REF] with the robust algorithm ( §3.2.2). The eight pruning algorithms are applied to the same 20 learned networks.

Modeling of a static system

The problem considered here is the modeling of a simple nonlinear system [START_REF] Thomas | Elagage d'un perceptron multicouches : utilisation de l'analyse de la variance de la sensibilité des paramètres. 5 ème Conférence Internationale Francophone d[END_REF].

This system is based on a one-hidden-layer perceptron structure with three inputs and one output. This system, supposed to be unknown, is chosen to avoid problems related to the differences between the form of the 'true' model and that of the fitted model. The system is described by: ( ) ( )

1
where e(t) is additive Gaussian noise with mean 0 and standard deviation 0.2.

Two datasets of 500 points were created for learning and validation. These two datasets include five input variables (x1, x2, and x3 and two supplementary ones).

These five inputs are sequences of steps of random length and amplitude. To give each input a different influence, input ranges of [-1; 1], [0; 1.5], [-1; 1.5],

[0; 0.5], and [-1; 0] were applied, respectively. The initial structure of the neural network comprised eight hidden neurons.

Table 4 lists the best results obtained with the eight pruning algorithms and for the learning without pruning.

In regression, the mean of the residual must be null. Thus, a two-tailed statistical hypothesis test can be employed to determine this for the different algorithms.

The null hypothesis 0 H (that the mean of the residuals is null) and its alternative 1 H are:

0 1 : 0 : 0 µ µ =   ≠  H H ( 20
)
where µ is the mean of the residuals population. 0 H is rejected with a risk level of 5% if:

1.96 / 1.96 / U s N or U s N ε ε  = >       = < -   (21)
where N is the size of the validation dataset, and ε , s 2 are the estimated mean and variance of the residuals.

For this simulation example, the true standard deviation of the noise 0 σ is known to be 0.2. Thus, the two-tailed statistical hypothesis test was used to determine whether the variance of the population 2 σ obtained with the different algorithms was statistically different to 2 0 σ . The null hypothesis 0 H and its alternative 1 H were therefore:

2 2 0 0 2 2 1 0 2 2 0 : : σ σ σ σ σ σ  =  >   <  H H (22)
and 0 H can be rejected with a risk level of 5% if:

2 2 1 2 0 2 2 2 2 0 ( 1). , 2 ( 1). ,1 2 c
c N s N s α χ υ σ α χ υ σ  -   Γ = < Γ =        -    Γ = > Γ = -       (23)
where N is the size of the validation dataset, υ is the number of degrees of freedom, and α is the confidence interval. For this example, the two bounds 1 4. This shows that all algorithms gave equivalent results and correctly learned the system. The mean of the residuals is statistically null, and the variance is statistically equal to 2 0 σ for all algorithms.

However, N2PS was not able to prune any parameters, and consistently preserved the initial structure. The best structure obtained with the VNP algorithm includes 49 parameters. The other algorithms gave very similar results. N2PFA and two proposed variants (NNSP-HI-mad and NNSP-IH-mad) found the minimal number of hidden neurons. OBS produced the smallest structure, but required a significant computation time. shows that these six algorithms consistently found satisfactory results.

Modeling of a dynamic system

The second system model is also based on a single-hidden-layer perceptron, but uses delayed inputs [START_REF] Thomas | Elagage d'un perceptron multicouches : utilisation de l'analyse de la variance de la sensibilité des paramètres. 5 ème Conférence Internationale Francophone d[END_REF]. This system is described by: ( ) ( )

1 2 2 1 2 ( ) 1 tanh ( 2) ( ) 3. ( 1) tanh ( 2) ( 2) ( ) y t x t x t x t x t x t e t = + -- + - + -- - + (24)
where e(t) is additive Gaussian noise with mean 0 and standard deviation 0.17 (respectively x2) was randomly chosen between -1 and 1 (respectively 0 and 1.5).

Two datasets of 500 points were created for learning and validation. The input vector used for the learning consisted of the two inputs x1 and x2 and their respective delays t, t- For all algorithms, two statistical hypothesis tests ( 21) and ( 23) were performed to test the mean and variance of the residuals. As in the preceding example, the true standard deviation 0 σ of the noise is known to be 0.17 Γ are 439.0 and 562.8. Table 5 lists the best results obtained with the eight pruning algorithms and for the learning without pruning. This shows that VNP is not able to find a suitable structure because the mean and variance of the residuals are different from 0 and 2 0 σ , respectively. For all other algorithms, the results are equivalent. It can be seen that N2PS was able to prune parameters in only one case. In the 19 other cases, this algorithm preserved the initial structure. OBS determined the best structure, but was again very computationally expensive. N2PFA and the four proposed produced very similar results, but the four proposed algorithms are less time-consuming. NNSP-IH-mad and NNSP-HI-mad, which use the variance estimation in [START_REF] Kruschke | Improving generalization in backpropagation networks[END_REF], were unable to prune the inputs. As for the preceding cases, the use of a robust criterion during learning allows the overfitting problem to be avoided.

Ailerons dataset

The regression problem considered here is also available from WEKA [86]. This dataset addresses a control problem, namely flying an F16 aircraft. The attributes describe the status of the airplane, and the goal is to predict the control action on the ailerons of the aircraft, which comprises 13750 patterns. There are 39 inputs for each pattern. This dataset was randomly divided into two for learning (6868 data) and validation (6882 data). The initial learning was performed with 20 hidden neurons. Because of its computational time requirements, the OBS algorithm was executed only once. For all algorithms, the two statistical hypothesis tests ( 21) and ( 23) were performed to test the mean and variance of the residuals. In this real example, the true variance of the noise 2 0 σ is unknown. In test (23), its value is replaced by the lower variance value obtained on the validation dataset. For this example, the two bounds

1 c
Γ and 2 c Γ are 6690 and 7076. Table 6 presents the results obtained for the different algorithms. This shows that the VNP algorithm could not find a suitable structure, instead pruning all parameters and becoming trapped in a very bad local minimum. N2PS and one variant of the proposed algorithm (NNSP-IH-mean) were unable to prune any parameters, and therefore preserved the initial structure. These two algorithms and OBS gave results that were statistically worse than those of N2PFA, which produced the best results. OBS again required a considerable computation time (more than one day). The results obtained with the other algorithms are statistically equivalent. N2PFA was the only algorithm that was able to prune the inputs. However, NNSP-HI-mean and NNSP-IH-mad pruned more hidden neurons and parameters, and determined equivalent structures quicker than N2PFA. The computational time for N2PFA is four times higher than those for the proposed algorithms.

Conclusions

In this paper, a new pruning algorithm was proposed to determine the optimal structure of a MLP for both classification and regression problems. Four variants of this algorithm were tested and compared with four classical pruning algorithms on three classification problems and three regression problems. The proposed algorithms produced equivalent results or outperformed the four comparative algorithms. Moreover, they required less computational time than the OBS and N2PFA algorithms. Of the four proposed variants, NNSP-HI-mean gave the best results. This variant begins by pruning hidden neurons, then considers the inputs, and finally the parameters. It uses the variance estimator [START_REF] Bishop | Neural networks for pattern recognition[END_REF] proposed by Engelbrecht [START_REF] Engelbrecht | A new pruning heuristic based on variance analysis of sensitivity information[END_REF].

The results have shown that the use of a robust learning algorithm allows the overfitting problem to be avoided in both classification and regression problems.

where i x are the ni inputs of the neural network, 1 hiw

 1 are the weights connecting the input layer to the hidden layer, 1 h b are the biases of the hidden neurons, gh(.) is the activation function of the hidden neurons (here, the hyperbolic tangent for all hidden neurons), 2 h w are the weights connecting the hidden neurons to the output neuron, b is the bias of the output neuron, go(.) is the activation function of the output neuron, and ŷ is the network output.

hb

  (h = 1..., nh) of the hidden neurons is obtained by taking the partial derivative of the output with respect to the bias 1 h b under consideration:

2 hw

 2 and k = 1…K=ni+nh.(ni+2)}, with θk corresponding to xi when considering input i, to when considering hidden neuron h, to 1 hi w when considering the weight connecting input i to hidden neuron h, or to 1 h b when considering the bias of hidden neuron h. Thus,

Fig. 1

 1 Fig. 1 NNSP-HI algorithm

Γ

  VNM measures are determined using equations (4) and[START_REF] Bishop | Neural networks for pattern recognition[END_REF] (NNSP-HI-mean) or equations (4) and (12) (NNSP-HI-mad). The values of k θ Γ for all hidden neurons are compared to the threshold Γc. If none of the measures are lower than the threshold Γc, the corresponding hidden neurons are pruned and the network is retrained. The two MAD values are calculated from[START_REF] Jutten | Pruning methods: a review[END_REF], and compared to the threshold Ermax. If the new structure improves the results, the memories with their improved values. If the resulting network becomes too degraded, the preceding structure is restored and the hidden neuron pruning phase

Fig. 2

 2 Fig. 2 NNSP-IH algorithm

Fig. 3

 3 Fig. 3 Distribution of the misclassification rate on learning and validation datasets Figure 3 presents the distribution of the misclassification rate given by the six best pruning algorithms. These results were obtained over the 20 networks on the learning and validation datasets. This figure shows that NNSP-HI-mean, NNSP-IH-mean, and N2PFA often produced good results. In particular, on the validation

Γ

  were 439.0 and 562.8. The results of this statistical hypothesis test on the validation datasets are presented in Table

Fig. 4

 4 Fig. 4 RMSE distribution on learning and validation datasetsFigure4shows the RMSE distribution of the six best-performing algorithms on the learning and validation datasets for the 20 initial sets of weights. This figure

.

  The delayed inputs x1 and x2 are sequences of steps of random length and amplitude. The duration of the steps of input x1 (respectively x2) was randomly chosen between 5 and 10 (respectively 8 and 15). The amplitude of x1

Table 1 :

 1 Best results obtained on the diabetes dataset

Table 2 :

 2 Best results obtained on the ionosphere dataset

Table 3 :

 3 Best results obtained on the quality dataset

Table 4 :

 4 Best results obtained on the static model dataset

Table 5 :

 5 Best results obtained on the dynamic model dataset

Table 6 :

 6 Best results obtained on the ailerons dataset


Philippe Thomas
email: philippe.thomas@univ-lorraine.fr

William Derigent
email: william.derigent@univ-lorraine.fr

Marie-Christine Suhner
email: marie-christine.suhner@univ-lorraine.fr

Prediction model adaptation thanks to control chart monitoring. Application to pollutants prediction

Keywords: indoor air quality, neural networks, relearning, control charts

Indoor air quality is a major determinant of personal exposure to pollutants in today's world since people spend much of their time in numerous different indoor environments. The Anaximen company develops a smart and connected object named Alima, which can measure every minute several physical parameters: temperature, humidity, concentrations of COV, CO2, formaldehyde and particulate matter (pm). Beyond the measurement aspect, Alima presents some data analysis feature named 'predictive analytics', whose primary aim is to predict the evolution of indoor pollutants in time. In this article, the neural network (NN) model, embedded in this object and designed for pollutant prediction, is presented. In addition with this NN model, this article also details an approach where batch learning is performed periodically when a too important drift between the model and the system is detected. This approach is based on control charts.

INTRODUCTION

Air pollution is now identified as a major international issue. However, in people's mind, it always refers to the quality of outdoor air, whereas the predominant environment in this regard is the residence. Indeed, indoor air quality is a major determinant of personal exposure to pollutants in today's world since people spend much of their time in numerous different indoor environments [START_REF] Walsh | Indoor air quality[END_REF]. During the last two decades there has been increasing concern within the scientific community over the effects of indoor air quality on health. Changes in building design devised to improve energy efficiency have meant that modern homes and offices are frequently more airtight than older structures. Furthermore, advances in construction technology have caused a much greater use of synthetic building materials, which provide indoor pollution [START_REF] Jones | Indoor air quality and health[END_REF]. The known health impacts and corresponding pollutants are numerous. Table 1 is an excerpt taken from [START_REF] Spengler | Indoor air pollution: a public health perspective[END_REF] to illustrate some of the major indoor pollutants. The sources of pollution can be located indoor (building material, furniture, stoves…) or outdoor (air coming through an opened window or via the ventilation system). Symptoms and consequences of exposure to a pollutant can vary depending on the pollutant type and concentration. For example, the carbon dioxide (whose indoor concentrations can vary from 700 to 3000 ppm) is a simple suffocating gas and can also act as a respiratory irritant [START_REF] Maroni | Indoor Air Quality -a Comprehensive Reference Book[END_REF], whereas the exposition to a formaldehyde concentration of 100 ppm can cause death. It thus explains why indoor air quality recently receives much public attention, and people are now eager to measure in their own homes the quality of their indoor air. To answer to this growing need, The Anaximen Company develops a smart and connected object named Alima (Alima, 2013).

In fact, pollutant levels are constantly changing, depending on the tenants' activities. Alima can measure every minute several physical parameters: temperature, humidity, concentrations of COV, CO2, formaldehyde and particulate matter (pm). Data are stored on the object or can be sent to a distant database, and are available for the user online via phone apps or websites. Beyond the measurement aspect, the society currently plans to embed in Alima some data analysis feature named 'predictive analytics', whose primary aim is to predict the evolution of indoor pollutants in time. Anaximen and the CRAN laboratory are associated to develop this leading-edge feature.

In this article, a neural network (NN) model designed for pollutant prediction is presented. However, a drift can appear between the NN model and the system modelled (due to, for example, a modification of the occupant behavior), and forces the NN to do a relearning phase. But this relearning phase is time and resource consuming and should be done sparingly. So, in addition with the NN model for pollutant detection, this article also details an approach where batch learning is performed periodically when a too important drift between the model and the system is detected. This approach is based on control charts. Section 2 presents a short state-of-the-art on neural network modelling, section 3 details the approach used to control the drift and perform the batch learning while section 4 presents the industrial application. Section 5 first exposes the results obtained by the NN model for pollutant prediction (without any relearning phase), and then describes the results obtained when using the drift detection algorithm.

NEURAL NETWORK MODEL

Artificial neural network models have been successfully applied to solve many different problems, including dynamic systems identification, patterns classification, adaptive control, functions approximation and so on.

Among these artificial neural network models, the multilayer perceptron (MLP) is, by far, the most popular architecture due to its structural flexibility, good representational capabilities, and the availability of a large number of training algorithms [START_REF] Han | A structure optimisation algorithm for feedforward neural network construction[END_REF]. This model is used for both classification and regression tasks. Works of [START_REF] Cybenko | Approximation by superposition of a sigmoidal function[END_REF] and [START_REF] Funahashi | On the approximate realization of continuous mapping by neural networks[END_REF] have proved that a MLP with only one hidden layer using a sigmoïdal activation function and an output layer can approximate all non-linear functions with the wanted accuracy. Its structure is given by:

0 1 2 1 0 1 2 1 1 1 . . n n i ih h i i h z g w g w x b b = =     = + +           ∑ ∑ (1)
Where: -0 h

x are the n0 inputs of the neural network, -1 ih w are the weights connecting the input layer to the hidden layer, -1 i b are the biases of the hidden neurons, -g1(.) is the activation function of the hidden neurons (namely the hyperbolic tangent), -2 i w are the weights connecting the hidden neurons to the output one, -b is the bias of the output neuron, -g2(.) is the activation function of the output neuron and, -z is the network output.

Because the problem is a regression problem, g2(.) is chosen linear. Three steps must be performed in order to design the neural model: initialization, learning and pruning. The first one is the determination of the initial set of weights and biases. This step is important because learning algorithm performs a local search of the minimum. So, in order to avoid local minimum trapping, different initial sets must be constructed which allow beginning to learn in different zones of the criteria domain. Different initialization algorithms have been proposed in the literature [START_REF] Thomas | Initialization of one hidden layer feedforward neural networks for non-linear system identification[END_REF]. The initialization algorithm used in this paper is the one proposed by [START_REF] Nguyen | Improving the learning speed of 2-layer neural networks by choosing initial values of the adaptative weights[END_REF] which allows associating a random initialization of weights and biases to an optimal placement in input and output spaces. The second step is performed by the learning algorithm which must fit the network output with the data. In industrial applications, data are noisy and corrupted with many outliers. In order to limit the impact of outliers on the results, a robust Levenberg-Marquardt algorithm is used [START_REF] Thomas | Neural modeling of an induction furnace using robust learning criteria[END_REF]. Levenberg-Marquard algorithm allows associating the speed of the Hessian methods to the stability of the gradient methods. This is performed by adding a parameter multiplied by the identity matrix in order to permit the inversion of the Hessian matrix even if it is singular. The tuning of this parameter during the learning allows the Levenberg-Marquard algorithm to work as a gradient descent algorithm when this parameter is large and as a Gauss-Newton algorithm when this parameter is small. The use of a robust criterion allows to avoid the influence of outliers and provides a regularization effect in order to prevent overfitting. An important issue in neural network design is the determination of its structure. To determine it, two approaches can be used. The first one is constructive, where the hidden neurons are added one after the other [START_REF] Ma | New training strategies for constructive neural networks with application to regression problems[END_REF]. The second approach exploits a structure with too many initial hidden neurons, and then prunes the least significant ones [START_REF] Setiono | Pruned neural networks for regression[END_REF]Leow 2000, Engelbrecht 2001). We focus on the pruning approach that allows a simultaneous selection of the input neurons and the number of hidden neurons. The pruning phase is performed in two steps. First, the Engelbrecht algorithm is used which allows to quickly simplify the structure and second, the Setiono and Leow algorithm is used which is slower but also more efficient [START_REF] Thomas | Variance Sensitivity Analysis of Parameters for Pruning of a Multilayer Perceptron: Application to a Sawmill Supply Chain Simulation Model[END_REF].

ONLINE ADAPTATION OF THE MODEL

Generalities

Ideally, the data collected during the experimentation phase should describe all the states of the system to model. However, it is sometimes not feasible due to the high number of potential situations the system could encounter. Indeed, in our case data collected are different depending on the seasons, the yearly weather, changes in user's habits and so on. Technically, it would thus be highly difficult to obtain an exhaustive data set. As a result, our approach consists in two phases: first, a learning phase is achieved based on a data set obtained via a relatively short experimentation phase (in our case, 1 month, see section 4.1) to construct a first "specific" NN model. Then, a relearning is launched if and only if a significant difference (called "drift") between the system behavior and its corresponding NN model is detected. In many case, a drift may appear between the model constructed and the system studied. This drift may be due to two main reasons. The first one concerns the evolution of input parameters. With a learning approach, the obtained model is valid only on the learned domain. The model is able to provide a valid solution only in this concerned domain. The second reason concerns the uncontrolled modification of the machine or environment behavior. Indeed, A change of a parameter (voluntarily or not, measured or not) which is not an input of the model, can affect the behavior of the machine. In this case, this parameter should be part of the model inputs but, as it was considered constant for the duration of the learning step, it was not retained as such. Due to this change, which may even be unknown to operators and users, the model will therefore provide results out of step with reality.

To take into account these problems, a relearning on new data is needed. There are two practical ways to implement learning in neural networks: batch training and on-line training. Whenever a new data is received, batch learning uses this new data together with the past data to perform a retraining. But this approach is time consuming. The on-line approach uses only new data to adapt the model. However, this approach suffers from slow training error convergence as a large number of training data may be required [START_REF] Liang | A fast and accurate online sequential learning algorithm for feedforward networks[END_REF]). Moreover, different works have shown that on-line training strategy does not converge to the optimal weights [START_REF] Heskes | A theoretical comparison of batch-mode, online, cyclic, and almostcyclic learning[END_REF]Wiegerinck 1996, Nakama 2009). We thus propose here another approach where a batch learning is performed periodically when a drift between the model and the system occurs, in order to synchronize the model with the reality. Because this synchronization is time consuming, the synchronization frequency must be optimized. Rather than consider a resynchronization frequency in response to events (arrival of new information from one of the connected devices, solicitation by an operator…) or a periodically one (every hour, week…), it is better to rely on statistical findings. Among the 7 basic tools for quality control, control charts, also known as Shewhart charts or processbehavior charts [START_REF] Shewhart | Economic Control of Quality of Manufactured Product[END_REF], are interesting Statistical Process Control (SPC) tools useful for our proposed system.

Control charts

Control charts are particularly relevant to the dynamic quality control with the use of time-series [START_REF] Tague | The Quality Toolbox, 2nd Edition[END_REF]. They can determine statistically if a variation is no longer under control. Indeed, it is known that even when a process is under control there is approximately a 0.27% probability of a point exceeding a 3σ control limit (Pareto). These few isolated points should not trigger synchronization. But the detection of too many points above this limit may underlines the presence of a special cause, even if it is not yet known. The Combination of a neural network with the control charts can therefore inherit from the robustness of the statistical analysis and the adaptability of the neural network. [START_REF] Du | The Embedded Quality Control System of Product Manufacturing[END_REF] work on the inverse combination of both tools with a recognition algorithm of control charts using neural networks to get alerts in case of quality problems and to provide clues in defining causes. In our case, when a set of n new data is collected, a performance indicator is calculated and compared to two bounds determined on the initial validation data set. If this indicator is still between the two bounds, the model is always suitable. If the new value of the indicator is outside the bounds, a relearning phase is needed on these new collected data. Figure 1 shows an example of control chart to monitor the accuracy of the model. It presents the evolution of the considered indicator compared to the upper (UCL) and lower bounds (LCL) in function of samples of size n. In this example, the two first samples present acceptable results and the model accuracy is sufficient. For the third sample, the indicator is outside the bounds and a relearning on the n last data is needed to drive the indicator inside the bounds for the next samples. If no relearning occurs, the drift between model and reality stays and may grow.

control bounds

Our control charts (s charts) aim to determine if a process characteristic is stable. The center line (CL) is given by the standard deviation of the considered characteristics. The Upper Control Limit (UCL) and the Lower Control Limit (LCL) are calculated for representing 99.8% of data (NIST/SEMATECH 2012). These limits are given by:

2 4 4 2 4 4 3 1 3 1 s UCL s c c CL s s LCL s c c  = + -    =    = - -  
(2) where: -s stands for the center line (CL) and correspond to the estimated standard deviation of the characteristic monitored, -n is the size of the sample, -c4 is a factor allowing to find an unbiased estimator of the standard deviation σ:

4 . s c σ = (3)
With c4 given by:

4 1 ! 2 2 1 1 1 ! 2 n c n n   -     = - -  -     (4)
where the non-integer factorial is given by: 1

! . 1 . 2 . 2 2 2 2 2 n n n n π           = - -                     ⋯ (5)
In the considered case, the monitored characteristic is the error performed by the network, and so, the parameter to monitor is the sample standard deviation given by: ( )

2 1 1 n i i s n ε ε = - = - ∑ (6)
where εi stands for the error performed on data i and ε stands for the mean of the error.

The value of the estimated standard deviation s is obtained on the validation data set used to validate the initial model.

INDUSTRIAL APPLICATION

Description of the case study

The experimentation site is a single storey dwelling whose floor plan is shown figure 2.

Considered problem

We focus here on the problem of pollutant evolution prediction. As explain previously, each Alima collects, each minute, the values of five parameters (temperature, humidity, CO 2 , COV and particulate matter (pm)). The goal is to predict 30 minutes ahead the level of each pollutant in function of the actual and past level of these pollutants. In order to improve the performance of the model, different situations (cooking, sleeping…) are detected by using a classification model. The output of this classification model is used as an input of the prediction model. The figure 3 presents the principle of the prediction of pollutants. The database collects data from the Alima. These data are use in a first step in order to detect the current situation (cooking, sleeping…) which may have an impact on the pollutant evolution. The design of the classification model has already been submitted to the MOSIM2014 conference. This article is thus entirely focused on the prediction model. This model takes as inputs the 8 actual outputs of the classification model and the 5 past values (t, t-1, t-2, t-3, t-4) of the parameters collected by Alima. Three different models are built for each pollutant (CO 2 , COV, pm). The output of the considered model is the value of the considered pollutant 30 minutes later (t+30). In order to avoid the local minimum trapping, the learning is performed on 20 different initial parameters sets. The data set is divided in two subsets (learning and validation data set) each corresponding to 15 days of collected data. Only data collected by Alima1 are used for the learning and validation. A pruning algorithm is used in order to avoid the overfitting problem. At last, the best resulting model is selected.

RESULTS

Results obtained on the validation data set

In a first step, the results obtained on the validation data set are presented. Figure 4 presents the prediction of CO 2 (in green) to compare to the real values collected (in black). This figure shows that the evolution of CO2 level may be predicted with a good accuracy even if the amplitude of the larger variation can't be predicted.

The figure 5 presents the prediction error for the CO 2 pollutant (for the first 5 days of the validation data set). This figure shows that the model is able to predict the smooth evolution but it is not able to find the total amplitude of greatest variations. For these two figures, the data are normalized due to confidential needing. However, the model works with the true range of variation. The results obtained for the COV pollutant is quite similar and are not presented here. Figure 6 and 7 present the same results obtained for pm pollutants. These two figures shows that pm is corrupted with an important noise. The events to detect have an amplitude of the same order to the noise variance. However, the model is able to predict the evolution of the pm pollutant with a good accuracy.

Adaptation of the models

The main goal of this model is to be suitable even if the conditions change (move in the house, or change of house …) and the model must to be portable from one Alima to another. In order to do that, the model must be adaptable on-line. To do that, we propose to detect if the model varies from the reality, and to perform a relearning only if needed. In order to illustrate this, the preceding models constructed with the data collected by airbox1 are used with the data collected on airbox2. The s-chart described part 3 is used in order to determine if a relearning is needed. The size of the samples is fixed to 240 minutes and so each sample contains 240 patterns. Figure 8 presents the s-chart obtained for the pm model used with data collected by airbox2.

This figure shows that, as awaited, the model is not accurate for the first sample of 240 data. So a relearning occurs on these 240 first data. This relearning allows to fit the model to these new condition and the model accuracy is satisfactory until the sample 25. For this sample, the value of the standard deviation is slightly outside the bounds and a second relearning is needed. So, for the 15 days of the experiments, only 2 relearning are needed to maintain a good accuracy of the model.

CONCLUSIONS

This paper presents a new on-line monitoring strategy conserving the prediction model accuracy. This strategy is based on the use of a control chart to determine if a relearning is needed or not to adapt the model to an evolution of the reality. This approach is tested on a prediction model related to pollutants levels. The results show that neural networks are able to predict the evolution of pollutants. Moreover, the proposed monitoring strategy allows adapting quickly the considered model to new conditions and, in the same time, to limit the number of relearning needed. In future works, this approach will be compared with on-line learning on both accuracy and computational time.

Figure 1 :

 1 Figure 1: Example of control chart used for monitoring accuracy of the model.

Figure 4 :

 4 Figure 2: Implantation of the 5 Alima in a house.

Figure 5 :

 5 Figure 5: prediction error of C0 2 .

  Figure 6: prediction of pm.

  Figure 7: prediction error of pm.

Figure 9

 9 Figure9presents the prediction error for the pm pollutant. This figure shows that this strategy allows maintaining an accurate model even when the conditions change.

Table 1 .

 1 Pollutants and sources

	Pollutant	Major emission sources
	Allergens	House dust, domestic animals,
	Asbestos	Fire retardant materials, insulation
	Carbon dioxide	Metabolic activity, combustion activities,
	Carbon monoxide	Fuel burning, boilers, stoves, gas…
	Formaldehyde	Particleboard, insulation, furnishings
	Micro-organisms	People, animals, plants, air conditioning
	Nitrogen dioxide	Outdoor air, fuel burning, motor vehicles
	Organic substances	Adhesives, solvents, building materials,
	Ozone	Photochemical reactions
	Particles	Tobacco smoke, combustion products...
	Polycyclic aromatic	Fuel combustion, tobacco smoke
	hydrocarbons
	Pollens	Outdoor air, trees, grass, weeds, plants
	Radon	Soil, building construction materials
		(concrete, stone)
	Fungal spores	Soil, plants, foodstuffs, internal surfaces
	Sulfur dioxide	Outdoor air, fuel combustion

ACKNOWLEDGEMENTS

The authors thanks the society Anaximen for their active financial and scientific support for this work.


Philippe Thomas
email: philippe.thomas@univ-lorraine.fr

Marie-Christine Suhner
email: marie-christine.suhner@univ-lorraine.fr

André Thomas
email: andre.thomas@univ-lorraine.fr

CART for supply chain simulation models reduction: application to a sawmill internal supply chain

Keywords: Decision tree, CART, reduced model, simulation, supply chain

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Planning or scheduling scenario evaluation is an important issue for internal/external Supply Chains (SC) control. Simulation is useful to perform this evaluation and allows to highlight evolution of the resources states, work in process and queues. This information allows to perform a "Predictive scheduling" [START_REF] Lopez | Ordonnancement de la production[END_REF] which concerns MPS which is initially established with the Manufacturing Planning and Control System. This first approach must not be confused with "Reactive scheduling" which gives new MPS solution, established after significant events occur on the shop-floor. The real time systems performing production reporting lead to obtain information into the management system very quickly [START_REF] Khouja | An aggregate production planning framework for the evaluation of volume flexibility[END_REF]. However, it is difficult to use this huge of information to take a decision [START_REF] Pritsker | Simulation for planning and scheduling[END_REF][START_REF] Roder | Visibility is the key to scheduling success[END_REF]. At this level of planning, load/capacity balancing is obtained via the "management of critical resource capacity" function or Rough-Cut Capacity Planning which essentially concerns bottlenecks [START_REF] Vollmann | Manufacturing, Planning and Systems Control[END_REF]. Goldratt and Cox [4] propose to manage all the supply chain by bottlenecks control and call it Theory of Constraints (TOC). For this purpose, the use of dynamic discrete event simulation of material flow is helpful [START_REF] Thomas | Reducing simulation models for scheduling manufacturing facilities[END_REF]. Simulation models of real industrial cases are very complex and can lead to problems of scale [START_REF] Page | An aggregate production planning framework for the evaluation of volume flexibility[END_REF] that is why it is interesting to use simplest (reduced/aggregated) models of simulation [START_REF] Brooks | Simplification in the simulation of manufacturing systems[END_REF][START_REF] Chwif | Discret event simulation model reduction: A causal approach[END_REF][START_REF] Ward | Argument for constructively simple models[END_REF]. To design these reduced model, different approaches may be used as using continuous flow model to approximate discrete manufacturing environments [START_REF] Ho | Performance evaluation and perturbation analysis of discrete event dynamics systems[END_REF]15], or using metamodels (linear regression, splines, Kriging…) in order to perform simulation model [START_REF] Kleijnen | A methodology for fitting and validating metamodels in simulation[END_REF]. Neural networks are also been used to perform this task [START_REF] Thomas | Multilayer Perceptron for Simulation Models Reduction: Application to a Sawmill Workshop[END_REF][START_REF] Thomas | A neural network for the reduction of a Product Driven System emulation model[END_REF]. Another tool, regression tree, is able to find a suitable model useful for the model reduction. Classification and regression trees are machine learning methods able to fit a model to data. Models are obtained by partitioning data space and thanks to the association of a simple prediction model to each subspace [START_REF] Breiman | Classification and regression trees[END_REF]. The main goal of this paper is to evaluate the ability of regression trees to be used in order to reduce simulation model. In the second part, the proposed approach of reduction model and the regression trees are presented. The third part will be devoted to the presentation of an industrial application which is a sawmill flow shop case. In order to evaluate the pertinence of the proposition, the reduced simulation model of sawmill internal SC case is presented and, before to conclude, is compared to the same work performed by using neural network in the last part.

The reduced model

The algorithm

Model complexity is relative to the number of elements, connections and model calculations [START_REF] Zeigler | Theory of modelling and simulation[END_REF]. Different approaches have been proposed to reduce model. To see a brief overview, see [START_REF] Thomas | A neural network for the reduction of a Product Driven System emulation model[END_REF]. The proposed reduction algorithm is a modification of those presented by Thomas and Thomas [START_REF] Thomas | Multilayer Perceptron for Simulation Models Reduction: Application to a Sawmill Workshop[END_REF]. The proposed approach is based on the association of discrete event models and continuous models (regression tree) in order to design a simulation model. Our objective is to maximize the bottleneck utilization rate and, at the same time, simplify simulation model design for modelers. Its main steps are recalled and explained below:

1. Identify the structural bottleneck (work center (WC) which for several years has been mainly constrained in capacity). 2. Identify the conjunctural bottleneck for the bundle of Manufacturing Orders (MO) of the MPS under consideration. 3. Among the WC not listed in 1 and 2, identify the one (synchronisation WC) satisfying these two conditions:

(a) present at least in one of the MO using a bottleneck, (b) widely used considering the whole MO. 4. If all MO have been considered go to 5 if not go to 3. 5. Use regression tree for modelling the intervals between WC that have been found during preceding steps (figure 1).

Work Centers (WC) remaining in the model are either conjunctural or structural bottlenecks or WC which are vital to the synchronization of the MO. Other WC are incorporated in "aggregated blocks" upstream or downstream of the bottlenecks [START_REF] Thomas | A neural network for the reduction of a Product Driven System emulation model[END_REF].

Fig. 1. Reduction model algorithm

Regression tree

Decision trees are sequential models, which logically combine a sequence of simple tests. A regression tree looks like a classification tree, except that the output variable is a continuous one and a regression model is fitted to each node to give the predicted value of the output [START_REF] Loh | Classification and regression trees[END_REF]. The first regression tree (AID) has been proposed by Morgan and Sonquist [START_REF] Morgan | Problems in the analysis of survey data, and a proposal[END_REF]. The principle of this regression tree is to begin to the root node, and then, for each node, find the test on the input patterns which minimizes the sum of the node impurities in its two child nodes. Classification and Regression Tree (CART) algorithm works on the same principle [START_REF] Breiman | Classification and regression trees[END_REF]. The main difference between AID and CART relies with the pruning and estimation process. CART is based on the generalization of the binomial variance called Gini index. The growing procedure of the tree is recursive and the process is stopped when [START_REF] Lewis | An introduction to classification and regression tree (CART) analysis[END_REF]:

─ there is only one observation in each of the child nodes, ─ all observations within each child node have the identical distribution of predictor variables, making splitting impossible, ─ an external limit on the number of levels in the tree or on impurity decrease level threshold is reached.

The resulting tree presents generally overfiting problem and needs a pruning phase, based on the impurity term used during the growing phase (Gini) associated to a penalty term corresponding to the number of terminal nodes. The final tree selection is performed by using a cross-validation procedure [START_REF] Breiman | Classification and regression trees[END_REF].

Overview of the sawmill

The proposed approach is applied to build a simulation model of a sawmill workshop. In this actual case, managers need a tool to help them in their weekly decision-making Master Production schedule (MPS) process. They want: ─ to evaluate the effectiveness of its MPS, ─ to maximize its load rate, and so, its global productivity, ─ to explain some unexplained congestion phenomena of the trimmer WC.

A first work [START_REF] Thomas | Reducing simulation models for scheduling manufacturing facilities[END_REF] with a complete model has allowed to represent the congestion phenomena and to use this representation in order to improve the load rate. This model, has showed that a bottleneck load rate too high (higher than 60%) degrades productivity of bottleneck, and so, sawmill productivity. The difficulty is that bottleneck is the last sawmill WC but all influent factors on bottleneck productivity depend of the first WC. However, this complete model is unusable on a real case for the MPS dynamic evaluation because of time needed to modify it. Sawmill can be described from a process point of view. It can be represented by two linear parallel flows for main and secondary products. This fact, associated to variation of log dimensions lead process to be non-linear. Therefore, the physical industrial production system can be divided into three main parts. To explain the process, the trip of a log from its admission into the process to its exit in planks form will be described. The first process part is the Canter line presented figure 2. Dashed arrows indicate the products flow. The considered log is taken into the process by using conveyors RQM1, RQM2, and RQM3. According to its characteristics (determined by scanner MS), the log is driven to conveyors RQM4 or RQM5, which are used as input inventory for the Canter line. After that, logs go on the first canter's machine and later on the CSMK saw, which transforms logs into square-shaped parallelepipeds.

Fig. 2. The Canter line

Fig. 3. The Kockums line

This step gives the two first sides of the parallelepipeds (the added value on the log) and produces two planks (secondary products), which are taken out of the Canter line by the BT4 and BT5 conveyors. The log is then driven on the RQM6 conveyors, rotated 90°, and stored in RQM7 awaiting its second passage on the CSMK saw. After the second passage, the squared is completed, and two other secondary products are taken out of the Canter line by BT4 and BT5 toward the second part of the process, the Kockums line. The squared log is cut on the MKV saw into three planks (called main products). These main products are driven to the third part of the process, the trimmer line.

Fig. 4. The trimmer line

Figure 3 shows the second part of the process, where the main machine is the Kockums saw. Only secondary products are driven on this part. As previously said, the secondary products are taken in the line by the BT4 and BT5 conveyors. They are cut by the QM11 saw, after which they reach the Kockums saw, which optimizes the planks according to the products needed. The alignment table is used as the input inventory of the Kockums saw. The secondary products are finally sent to the third part of the process by the exit conveyor.

The third part of the process is the trimmer line, which is presented in figure 4. This line performs the final operation of cross cutting. This operation consists in cutting up products to length. The inputs of the line are from collectors 1 and 2, which collect the secondary and main products from Kockums and Canter lines respectively. Saw 1 is used to perform default bleeding and Saw 2 cuts up products to length. A previous work [START_REF] Thomas | Reducing simulation models for scheduling manufacturing facilities[END_REF] has shown that this last machine, the trimmer saw, is the bottleneck of the entire process, and, as said previously, the productivity of the trimmer depends to the decisions taken on the canter work center. So, the impact of bad decisions are seen too much late to be corrected. So in order to evaluate decisions, managers need a simulation tool.

The simulation models

As said previously, the bottleneck of this line is the trimmer. Consequently, modeling the function of the inventories RQM4, RQM5, and RQM7, and of the Canter and Kockums lines is unnecessary and gave no direct and useful information for the evaluation of the MPS. In fact, only the arrival times of the products in the trimmer queue are useful for simulating the load of this bottleneck. So, in the complete model presented figure 5, all the parts surrounded with dashed line is unnecessary and may be replaced by a continuous model, here a regression tree.

According to the modeling process recalled in part 2, the specific sawmill model could be designed. To build this model, we need to identify the input variables. Thomas et al. [START_REF] Thomas | A neural network for the reduction of a Product Driven System emulation model[END_REF] collected the available input data which can be classified into three categories: Data related to the products (here the logs), data related to the process and data related to the bill of material or routing (here the cutting plan). The data related to the products are mainly dimensional ones as length (lg) and three values for timber diameters (diaPB, diaGB, and diaMOY). The data related to the process are the process variables collected at the time of log arrival. In particular, we require the input stock and the utilization rate of the bottleneck, here the trimmer (Q_trim, and U_trim, respectively). The number of logs present in the process between the inputs and the exit of the Canter line (Q_RQM) and in the input inventories (Q_RQM4, Q_RQM5 and Q_RQM7) are needed.

Fig. 5. Complete model

The data related to the routing correspond here to the information related to the cutting plan of the logs which must be cut into main and secondary products. This information is given by the type of part (T_piece). Consequently, the model input variables are: Lg, diaGB, diaMOY, diaPB, T_piece, Q_trim, U_trim, Q_RQM, Q_RQM4, Q_RQM5 and Q_RQM7. In our application, 12775 products are simulated with the complete model. These data are used to fit the behavior of the reduced model to the complete one which serve as reference model.

The next step is to identify the output variable. Our objective is to estimate the delay (∆T) corresponding to the duration of the throughput time for the 12775 products. ∆T is measured between the process input time and the trimmer queue input time. For regression problems, the goal is to reduce the distance between the model and the data. Hence, the RMSE criterion is suitable, and is used in this work:

1 ( ) N n n n RMSE y y N = = - ∑ (1)
where N denotes the number of data, yn is the n th actual data point, and ˆn y is the predicted value.

Figure 6 presents the evolution of the RMSE in function of the number of nodes in the tree. This figure shows that classically, even if RMSE always decreases on the learning data set, it is not the same on the validation data set. It begins by decreasing before to increase. This fact illustrates the overfitting problem and the selection of the best model must be performed by using a cross validation strategy. In our case, the selected model comprises 296 nodes.

Fig. 6. Evolution of RMSE in function of nodes number -identification data set in blue dashed -validation data set in red

This best model must be compared with those obtained in preceding work which use neural network model [START_REF] Thomas | A neural network for the reduction of a Product Driven System emulation model[END_REF]. These results are presented table 1. They show that regression tree outperforms neural model and allows to improve results of 20%.

Conclusion

The use of regression tree in order to build a reduced simulation model is investigated here. The regression tree model is used to model the functioning of a part of the process that is not constrained in capacity. This approach has been applied to the modeling of a sawmill workshop. The results show that the complete and reduced models gave similar results even if the log arrival rule is changed. Moreover, the results are compared with results obtained with a neural network model and the comparison shows that regression tree outperforms neural network on this application. This means that it seems efficient to use a regression tree to model a part of a process instead of constructing the complete model. Assuming that the construction of a regression tree is a quasi-automated task, in which the modeler only collects and selects the input data set. It is faster and easier to design this kind of reduced model. This approach allows the modeler to focus on the management of bottlenecks. Our intentions for future works are the validation of this approach on different applications, particularly on several external supply chains, such that at least one particular enterprise belongs to different supply chains.

1

 1

Table 1 .

 1 Comparison of RMSE for Neural network and regression tree models