Abstract
Abstract: Nonlinear empirical models are used in various applications. During model-building, five major steps usually have to be carried out: model structure selection, determination of input variables, complexity adjustment of the model, parameter estimation and model validation. These steps have to be repeated until a satisfactory model is found, which can be very time consuming and may require user interaction. This paper proposes an algorithm based on sparse grid function approximation to incrementally build a nonlinear empirical model. The algorithm exhibits good performance in terms of manual effort and computation time. The method is illustrated by a case study on the identification of a NARX model.
INTRODUCTION
Many important industrial processes exhibit nonlinear behavior. For model-based control and optimization a process model is required. Physicallybased process models are often not available due to development and maintenance cost. Therefore an empirical process model may be identified from experimental or plant data as described by e.g. Henson and Seborg (1997) .
INTRODUCTION
As a typical example, the identification of discretetime, nonlinear, auto-regressive models with exogeneous inputs (NARX models) is considered in this paper, although the methodology presented can easily be applied to other model structures as well. The general formulation of a NARX model for a process with a single input u ∈ R and a single output y ∈ R is y k = f (x k ), where f is a nonlinear function. The input variables of the NARX model (1) are delayed samples of the process input and output, using the notation y k = y(t = t k ). The model order parameters p and q determine how many delayed samples are included in x k .
INTRODUCTION
Given a measurement data set, the NARX model is usually built in an iterative process that consists of five major steps:
INTRODUCTION
(1) Select a model structure: A suitable model structure for the function f has to be selected from the many alternatives that are proposed in literature, such as artificial neural networks or polynomial models (Henson and Seborg, 1997) . The selection is usually strongly influenced by personal preferences and the available software but should be based on the intended application. For instance, Pearson (2003) states four important measures for model utility in process control: approximation accuracy, physical interpretability, ease of controller design and ease of model development.
INTRODUCTION
(2) Determine input variables: The input variables of the NARX model, i.e. the model order, are often assumed to be known. Alternatively, they are determined by building multiple model candidates with different sets of input variables and selecting the best one. This time-consuming search strategy can be avoided by algorithms that suggest a model order prior to the choice of a model structure as was presented by e.g. Feil et al. (2004) .
INTRODUCTION
(3) Adjust the model complexity: The concepts of stepwise model refinement, model pruning, i.e. deleting dispensable parameters, and regularization are frequently employed when model complexity is adjusted, see e.g. Bishop (1995) for artificial neural networks. Model complexity is often expressed by the number of model parameters and is determined by the grade of nonlinearity in the data set as well as the desired model accuracy.
INTRODUCTION
(4) Estimate the model parameters: A parameter estimation problem, which is sometimes also combined with step (3), is set up and solved by an algorithm that is usually tailored to the model structure for numerical efficiency.
INTRODUCTION
(5) Validate the identified model: After a solution has been obtained, the model should be validated, in order to decide if some of the preceding steps have to be repeated to improve the model.
INTRODUCTION
The model-building process can be very timeconsuming if many model candidates with different sets of input variables and model complexities have to be considered. The goal of this paper is to reduce the repetitions of the model-building steps by a systematic model-building strategy that combines all steps into one algorithm. Brendel and Marquardt (2003) noted that sparse grid approximation may find use for structure selection of nonlinear discrete-time models. This is demonstrated in this work. Yserentant (1986) proposed the sparse grid approach for multilevel-splitting of finite-element spaces. It was mainly used for the solution of PDEs (Griebel et al., 1992) . Recently the sparse grid approach has been introduced to the field of function approximation by Garcke et al. (2001) and Brendel and Marquardt (2003) . In this paper the stepwise model refinement algorithm of Brendel and Marquardt (2003) is modified to systematically select input variables and adjust model complexity. Furthermore, an alternative regularization term is proposed. Sparse grid approximation is described briefly in Section 2, which is the basis of the systematic model-building strategy presented in Section 3. This strategy is exemplified in a case study on NARX model identification and the resulting NARX model orders are compared to those found by Feil et al. (2004) . Finally, some conclusion are given in Section 5.
SPARSE GRID FUNCTION APPROXIMATION
Two basic statistical assumptions are commonly made if an output error modelỹ k = f (x k ) + k is used in function approximation: (i) the model structure f is reasonably correct and (ii) the measurements of the input variables x k in the k-th experiment contain negligible errors. All measurement errors and the model mismatch are described by the error term k , which is assumed to have a normal distribution with zero mean and variance σ 2 .
SPARSE GRID FUNCTION APPROXIMATION
The objective is to identify the function f : R d → R of some function space V from measurement data of the output variableỹ and the input variables x. This inverse problem may be ill-posed in the sense of Hadamard and therefore requires regularization (Engl et al., 1996) .
SPARSE GRID FUNCTION APPROXIMATION
The function f is the solution of the regularized least-squares estimation problem
SPARSE GRID FUNCTION APPROXIMATION
The first term measures the average approximation error of the function f to the measured values y k and the second term represents a regularization term to handle the ill-posedness.
SPARSE GRID FUNCTION APPROXIMATION
The following subsections briefly describe how the function f is defined in the sparse grid approach. Since the sparse grid solution is composed of multiple so-called full grid solutions, the function approximation on a full grid is presented first.
Function approximation on a full grid
The function f is represented in the full grid approach by a truncated basis function expansion
Function approximation on a full grid
where θ l,j are parameters to be estimated and The basis functions are created from the piecewise-linear mother function φ(x) by dyadic dilation and translation:
Function approximation on a full grid
The basis functions are centered on the grid points of a grid with a uniform mesh size in each dimension. For instance, two basis functions are shown in Figure 1 for a two-dimensional full grid.
Function approximation on a full grid
The sparse grid approach can be generalized to other basis functions including higher-order polynomials, interpolets, prewavelets and wavelets (Bungartz and Griebel, 2004 ), e.g. if f has to be continuously differentiable.
Function approximation on a full grid
The mesh size determines how accurate the full grid can approximate a given data set. However, the finer the mesh the more parameters have to be estimated. The number of parameters of a full grid with level l is
Function approximation on a full grid
and thus it increases exponentially with both the number of model inputs d and the level l.
Replacement of the full grid by a sparse grid
To cope with the high number of parameters in the full grid approach, Griebel et al. (1992) proposed a combination technique for the solution of sparse grid problems. The solution on a large full grid is approximated by combining solutions on a set of smaller full grids, so-called subgrids. More precisely, the sparse grid solution f (c) l on level l is the weighted sum of all subgrid solutions on levels s that are elements of an index set I l :
Replacement of the full grid by a sparse grid
The superscript (c) denotes the combination of subgrid solutions. Each subgrid f s is a full grid on level s, defined by equation (3) with the level index l being replaced by s.
Replacement of the full grid by a sparse grid
Different subgrid combination techniques were presented by Garcke and Griebel (2002) and Brendel and Marquardt (2003) . Brendel and Marquardt (2004) compare those techniques and state that the anisotropic grid combination technique from Garcke and Griebel (2002) seems to be favorable, therefore it is used in this work.
Replacement of the full grid by a sparse grid
The index set for the anisotropic grid combination technique is defined by
Replacement of the full grid by a sparse grid
With its characteristic function
Replacement of the full grid by a sparse grid
the weights in equation (7) 
Replacement of the full grid by a sparse grid
These weights take integer values. The associated subgrid solution is dispensable if a weight is zero. Table 1 gives an example for the subgrid decomposition of a sparse grid with level (4, 2, 2, 1) along with the number of parameters N s of each subgrid. A full grid on level (4, 2, 2, 1) would contain 1275 parameters, whereas the sparse grid is composed of 10 subgrids with 484 parameters in total. All subgrid solutions are calculated separately, thus the largest parameter estimation problem involves only 136 parameters. 
Estimation of sparse grid parameters
The sparse grid parameter estimation problem is easily solved, when it is expressed as a linear set of equations. Therefore, all parameters θ s,j and basis functions φ s,j (x) of a subgrid with level s are arranged to column vectors θ s and φ s (x) using a bijective mapping function M : R d → R that maps the multi-index j to an element of the column vector. Thus, equation (3) For regression withỹ ∈ R an alternative regularization term is proposed that enforces smoothness of the solution. Since the basis functions are dlinear, the smoothness is evaluated by summing up squared 2nd-order finite differences along all dimensions. The finite differences are evaluated at the basis function centers where the function values are equal to the corresponding parameter values. The regularization term is defined by 
Estimation of sparse grid parameters
which can be done in parallel. M is the number of data points in the estimation data set.
Estimation of sparse grid parameters
The regularization parameter λ can be chosen in different ways. Brendel and Marquardt (2003) apply cross-validation and the L-curve criterion from Hansen (1998) and state that cross-validation renders more reliable estimates of λ. Therefore, the regularization parameter is estimated by 10-fold cross-validation throughout this work. It should be noted here that the sparse grid solution is regularized in two ways. First, the chosen discretization level is an inherent regularization (Kirsch, 1996) . Additionally, the Tikhonov term regularizes the solution, which becomes significant with increasing discretization level.
GRID REFINEMENT ALGORITHM
The preceding section presented the identification of a sparse grid for a given set of input variables x and a specified discretization level l. However, a suitable level is usually not known a-priori. Brendel and Marquardt (2003) proposed a grid refinement algorithm to avoid an exhaustive search through all possibilities. This algorithm is extended for the purpose of input variable selection in the present work. Furthermore, the criterion for selecting the refinement step is modified.
GRID REFINEMENT ALGORITHM
For automatic input variable selection a discretization level of -1 is formally introduced. All input variables that are discretized on level -1 are simply ignored when calculating the sparse grid solution. For example f (c) x 3 ) . If the level is -1 in all dimensions, all input variables are ignored. In this case, the function f is defined as the mean value ofỹ.
GRID REFINEMENT ALGORITHM
The optimal regularization parameter is estimated by cross-validation. The whole data set is split up in N cv parts. N cv -1 parts are used for estimating the parameters and the remaining part for validation of the solution. The superscript r denotes the r-th part, while the superscript [r] denotes all data sets except the r-th part. Accordingly, the parameter vector θ [r] s is the solution of equation (13) on data set (x [r] ,ỹ [r] ).
GRID REFINEMENT ALGORITHM
The cross-validation error 
GRID REFINEMENT ALGORITHM
The grid refinement algorithm starts with an initial grid of level l = {−1, . . . , −1}. Thereafter the grid is successively refined by the algorithm:
GRID REFINEMENT ALGORITHM
(1) Calculate the cross-validation error e cv (l,λ(l)) for the current grid l. (lî,λ(lî) ) > e cv (l,λ(l)) or some other termination criterion is met, then the grid refinement is finished. Otherwise select the extended grid corresponding toî as current grid (lî → l) and proceed with step (2).
GRID REFINEMENT ALGORITHM
During the refinement process equation (13) has to be solved several times for different values of λ. For numerical efficiency the matrices D s and J s are stored and reused.
EXAMPLE
The sparse grid refinement algorithm is exemplified in a case study on the identification of a NARX model. For this model class the set of input variables is usually unknown a-priori. Feil et al. (2004) demonstrated a clustering-based model order selection approach with data sets generated by a simulation model of a continuous polymerization reactor, which is also used for comparison in this work.
First-principles reactor model
The model describes the free-radical polymerization of methyl methacrylate with azobisisobutyronitrile as an initiator and toluene as a solvent. The reaction takes place in a jacketed continuous stirred tank reactor. Under some simplifying assumptions, the first-principle model is given by:
First-principles reactor model
The model input u is the dimensionless volumetric flow rate of the initiator and the model output y is the number-average molecular weight. For further information on this model see (Doyle et al., 1995) .
First-principles reactor model
A uniformly distributed random input u over the range 0.007 -0.0015 with a sampling time of 0.2 s is applied to the model. The output y is scaled to zero mean and unit variance. White noise with a variance of 0.01 is added to y in order to make the subsequent NARX identification task more realistic. Delayed samples of u and y are assembled to two data sets: one for parameter estimation and one for validation, including 2000 and 1000 data points respectively.
Sparse grid NARX reactor models
A NARX one-step-ahead prediction model is identified from the simulated measurement data of the first-principles reactor model. The incremental model building approach is compared to a classical approach in terms of the mean square one-step-ahead prediction error e on the validation data set, the computation time T and the number of model parameters N (c) . It is emphasized that the prediction error e is not the same as the cross-validation error e cv that is used to estimate the optimal regularization parameter. The computation time T is measured in seconds for the current implementation of the algorithm in Matlab (The MathWorks, Inc., 2004) , which is executed on a personal computer (CPU: AMD Athlon XP 2600+, RAM: 1.5 GB). The reported levels correspond to the NARX input variables with the ordering defined in equation (1). For example, the level (2, 1, 0) with model orders p = 2 and q = 1 encode the NARX model
Sparse grid NARX reactor models
, where the sparse grid was discretized on level 2 for u k−1 , on level 1 for u k−2 and on level 0 for y k−1 .
Sparse grid NARX reactor models
In the classical model-building approach a set of NARX model candidates is identified with different model orders and a fixed discretization level. The model with the lowest prediction error on the validation data set is chosen as final model. The input variables to the NARX model have to be defined a-priori, thus all possibilities for selecting delayed process inputs u k−p and delayed process outputs y k−q in equation (1) are taken into account. Here p and q are limited to the interval [0, 3] . In general, different discretization levels can be used for each input variable of the NARX model. In this approach the level is fixed to 2, in order to narrow the set of possible model candidates. It is assumed that this level will ensure a sufficient flexibility of the sparse grid to approximate the data set.
Sparse grid NARX reactor models
The identification results were obtained after 71.9 s of CPU time and are presented in Table 2 . The rigid discretization results in a high number of parameters. However, even for high N (c) the prediction error is close to the variance of 0.01 of the noise that was added to y k . This indicates that the Tikhonov regularization term efficiently prevents the models from overfitting.
Sparse grid NARX reactor models
The model with p = 2 and q = 1 and the level (2, 2, 2) is chosen as final model, because it has a low prediction error e as well as a low number of parameters N (c) . The incremental model-building approach uses the grid refinement algorithm presented in Section 3. The initial level is set to -1 for automatic selection of suitable model inputs. Model complexity is adjusted by the grid refinement algorithm to reflect the characteristics of the given data set. The maximal model order is limited to p = q = 3 to conveniently present the results. Table 3 shows the intermediate best grid refinement levels. The solution with level (2, 1, -1, 0, 0, -1) is obtained after only 10.4 s of CPU time (corresponding to p = q = 2) in refinement step 8 with a prediction error of 0.0107. The refinement level (1, 0, -1, 0, -1, -1) in refinement step 5, which corresponds to p = 2 and q = 1, is almost optimal in terms of the cross-validation error e cv , while only requiring 12 parameters. The user may choose this model if simulation time is essential in the envisioned application. Table 3 . Incremental approach.
Sparse grid NARX reactor models
Step The approach of Feil et al. (2004) indicates, prior to selecting any model structure, a model order of p = 2 and q = 1. However, this model order has still to be validated by identifying a limited number of model candidates. The results of the classical and the incremental approach show that the indicated model order is indeed suitable for this case study.
CONCLUSIONS
Stepwise refinement of a sparse grid was used to automatically select model input variables and to adjust model complexity in an efficient way without requiring any user interaction. The algorithm was exemplified in a case study on NARX model identification. The determined model order is validated by an exhaustive search and compares well to the model order reported by Feil et al. (2004) .
CONCLUSIONS
Future research will focus on:
CONCLUSIONS
• higher-order basis functions to obtain continuously differentiable functions, • locally adaptive sparse grids to further reduce the number of required parameters, • an alternative refinement criterion that also takes the number of parameters into account, • an input design strategy that is integrated in the stepwise model refinement procedure to optimize experimental data acquisition, • more complex case studies on multi-input multi-output (MIMO) processes.

{'paper_id': '14488903', 'title': 'INCREMENTAL IDENTIFICATION OF NARX MODELS BY SPARSE GRID APPROXIMATION', 's2_url': 'https://api.semanticscholar.org/CorpusID:14488903', 'source': 'S2ORC'}