Brief paperIdentification of piecewise affine systems based on statistical clustering technique☆
Introduction
Hybrid systems are composed of both continuous dynamics governed by physical laws and discrete-event dynamics driven by logic and rules. Recently, much attention has been paid to hybrid systems from various viewpoints (van der Schaft & Schumacher, 2000).
This paper deals with a system representation of hybrid systems called a piecewise affine (PWA) system. A number of research works on PWA systems (Imura & van der Schaft, 2000, Johansson, 2003, Johansson & Rantzer, 1998, Nakada & Takaba, 2003) have been reported. Recently, it has been proved by Bemporad, Ferrari-Trecate, and Morari (2000) and by Heemels, De Schutter, and Bemporad (2001) that the PWA system is equivalent to the other hybrid system models such as mixed logical dynamical systems, linear complementarity systems, extended linear complementarity systems and max–min-plus-scaling systems.
The identification of PWA systems is quite important, because there are many linear systems with PWA nonlinearities such as saturation or relay elements, and a general nonlinear system can be treated as a PWA system by approximating a nonlinear function by a PWA one with arbitrary accuracy. There are some applications to the identification of real systems, e.g. a nonlinear electrical circuit (Ferrari-Trecate, Muselli, Liberati, & Morari, 2003), a fermentation process (Fantuzzi, Simani, Beghelli, & Rovatti, 2002) and a pick-and-place machine (Juloski, Heemels, & Ferrari-Trecate, 2004).
In the identification of PWA systems, a piecewise affine autoregressive exogenous (PWARX) model (Amaldi and Mattavelli, 2002, Bemporad et al., 2003, Ferrari-Trecate et al., 2003, Ragot et al., 2003, Roll et al., 2004, Vidal et al., 2003) is used as a typical model of PWA systems. The identification based on the PWARX model includes the estimation of both polyhedral partition on the regression space and the parameter of the ARX sub-model corresponding to each polyhedral region. In the case where the partition of the regression space is known a priori, the parameters of ARX sub-models can be estimated almost straightforwardly by the least squares method. However, the necessity of estimating the partition of the regression space as well as system parameters in the identification of PWA systems makes the development of identification methods extremely difficult. Jordan and Jacobs (1994) proposed an EM algorithm for hierarchical models that could be exploited for identifying PWARX models. Amaldi and Mattavelli (2002) considered a combinatorial optimization problem called the MIN PFS problem to estimate a piecewise linear model, which was approximately solved by a greedy method. Their result was applied by Bemporad et al. (2003) to the identification of the PWARX models with estimation of the number of sub-models. Ferrari-Trecate et al. (2003) developed an identification method by clustering parameter vectors, each of which is locally estimated from several data neighboring to each data. The optimality of the data classification utilized in this method was shown by Ferrari-Trecate and Schinkel (2003). Recently, Ragot et al. (2003) have proposed a method for identifying the parameter of sub-models when choosing an adapted weighting function, which allows one to select the data for which each sub-model is active. Vidal et al. (2003) have taken an algebraic geometric approach, in which the problem of estimating both the parameters and the number of sub-models is casted as a polynomial factorization problem. Moreover, Roll et al. (2004) have reduced the identification problem of a special class of PWARX models to a mixed-integer programming problem.
In this paper, we present a new method for the identification of a PWARX model based on a statistical clustering of measured data via a Gaussian mixture model and support vector classifiers (SVCs). A major advantage of the statistical clustering technique is that the statistical information such as the log-likelihood function enables us to estimate the number of sub-models of a PWARX model. We show how to estimate the number of sub-models based on the statistical information criteria such as the consistent Akaike's information criterion (CAIC) (Bozdogan, 1987), and the minimum description length (MDL) criterion (Rissanen, 1978), after discussing the case where the number of sub-models is available in the identification procedure. We also verify the applicability of the present identification method to a Hammerstein model, which is a popular model of nonlinear systems and composed of a linear system with a static nonlinearity. If the nonlinearity is a PWA function, the present method can be easily applied to Hammerstein models.
The organization of this paper is as follows. In Section 2, we formulate the identification problem of a PWARX model. The measured data are classified into clusters based on a Gaussian mixture model in Section 3. Sections 4 and 5 are, respectively, devoted to estimating boundary hyperplanes between two adjacent polyhedral regions on the regression space and the parameters of local sub-models. In Section 6, the two criteria CAIC and MDL are introduced to estimate the number of sub-models. We apply the present identification method to a Hammerstein model in Section 7. Finally, we conclude this paper in Section 8.
Section snippets
Piecewise affine autoregressive exogenous (PWARX) model
In this paper, we consider the identification problem of a PWA system. We introduce a useful model called a PWARX model (Bemporad et al., 2003, Ferrari-Trecate et al., 2003, Roll et al., 2004) for the identification of a PWA system.
A PWARX model is given byThe vectors , and are the input, the output and the noise at time k, respectively. The regression vector is denoted by where
Clustering of the measured data
We wish to classify the data in into s clusters. For this purpose, we classify the set of the time indices into s non-empty disjoint clusters . In this section, we employ a statistical clustering method based on a Gaussian mixture model (Alpaydın, 1998, Dempster et al., 1977, Jordan and Jacobs, 1994, Mitra et al., 2003, Miyamoto, 1999, Redner and Walker, 1984).
We assume that the probability density of the data is given by a Gaussian mixture model
Estimation of the boundary hyperplanes on the regression space
We describe a method for classifying two adjacent clusters in the regression space with a hyperplane based on SVCs (Vapnik, 1998, Boyd and Vandenberghe, 2003). The simplest version of SVC is used by Bemporad et al. (2003), while the similar technique is also utilized by Ferrari-Trecate et al. (2003).
Before estimating the partition of the regression space, we need to check the adjacency of the clusters. We employ the so-called Delaunay graph (Edelsbrunner, 1987) for this purpose. This graph
Parameter estimation of each sub-model
Based on the data classified in the previous section, we estimate the parameter by the LS method (Söderström and Stoica, 1989, Ljung, 1999). For each , the parameter can be estimated by the formulaHere, the quantity denotes the cardinality of which is assumed to satisfy so that we can estimate . Obviously, holds.
We compute the parameter
Estimation of the number of sub-models
In this section, we discuss how to estimate the number of sub-models. Since the number of clusters is equal to that of sub-models, we show how to estimate the number of clusters based on the information criteria associated with the maximum-likelihood estimation in Section 3 (Hu and Xu, 2003, Jain et al., 2000).
Firstly, we fix two positive integers and so that the true number of sub-models s is assumed to be in the interval . Next, for all , we compute the
Application to Hammerstein model
A Hammerstein model in Fig. 7 is a popular model used in the nonlinear system identification, which is composed of a linear time-invariant (LTI) system and a static nonlinearity. If the static nonlinearity is a static PWA function, we can easily apply the present identification method to the Hammerstein model as shown below. Example 2 We consider an SISO Hammerstein model. The plant is an LTI system given by where , and are scalar constants, and is a saturation
Conclusion
In this paper, we have developed a new identification method of PWARX models. More specifically, our method consists of the following three techniques: the statistical clustering based on a Gaussian mixture model with the EM algorithm, the estimation of the regression space partition via soft margin support vector classifiers, and the least squares estimation of the parameter of the ARX sub-models. The advantage of the present identification method is that the information criteria such as CAIC
Acknowledgements
The authors would like to thank Dr. Hideyuki Tanaka, Kyoto University, and the anonymous referees for their helpful advice on this work.
Hayato Nakada received B.Eng. degree in informatics and mathematical science and M.Inf. (Master of Informatics) degree in applied mathematics and physics from Kyoto University, Japan in 2000 and 2002, respectively. He is currently a doctoral student at the Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University. His current research interests include analysis, control and identification of hybrid systems and saturating systems.
References (33)
Soft vector quantization and the EM algorithm
Neural Networks
(1998)- et al.
The MIN PFS problem and piecewise linear model estimation
Discrete Applied Mathematics
(2002) - et al.
A clustering technique for the identification of piecewise affine systems
Automatica
(2003) - et al.
Equivalence of hybrid dynamical models
Automatica
(2001) - et al.
Non-convex clustering using expectation maximization algorithm with rough set initialization
Pattern Recognition Letters
(2003) Modeling by shortest data description
Automatica
(1978)- et al.
Identification of piecewise affine systems via mixed-integer programming
Automatica
(2004) - et al.
Observability and controllability of piecewise affine and hybrid systems
IEEE Transactions on Automatic Control
(2000) - Bemporad, A., Garulli, A., Paoletti, S., & Vicino, A. (2003). A greedy approach to identification of piecewise affine...
- et al.
A hierarchical latent variable model for data visualization
IEEE Transactions on Pattern Analysis and Machine Intelligence
(1998)
Convex optimization
Model selection and akaike's information criterion (AIC)the general theory and its analytical extensions
Psychometrika
Multicategory classification by support vector machines
Computational Optimization and Applications
Maximum likelihood from incomplete data via the EM algorithm
Journal of the Royal Statistical Society B
Algorithms in combinatorial geometry
Identification of piecewise affine models in noisy environment
International Journal of Control
Cited by (0)
Hayato Nakada received B.Eng. degree in informatics and mathematical science and M.Inf. (Master of Informatics) degree in applied mathematics and physics from Kyoto University, Japan in 2000 and 2002, respectively. He is currently a doctoral student at the Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University. His current research interests include analysis, control and identification of hybrid systems and saturating systems.
Kiyotsugu Takaba received B.Eng. degree in applied mathematics and physics, M.Eng. degree in applied systems science and Dr.Eng. degree in applied mathematics and physics all from Kyoto University in 1989, 1991 and 1996, respectively. Since 1991, he has been with the Department of Applied Mathematics and Physics in Kyoto University, where he is presently an Associate Professor. His research interest includes robust and optimal control for multi-variable dynamical systems. He is a member of IEEE, ISCIE and SICE.
Tohru Katayama received B.E., M.E. and Ph.D. degrees all in applied mathematics and physics from Kyoto University, Kyoto, in 1964, 1966 and 1969, respectively. Since 1986, he has been in the Department of Applied Mathematics and Physics, Kyoto University. He had visiting positions at UCLA from 1974 to 1975, and at University of Padova in 1997. He was an Associate Editor of IEEE Transactions on Automatic Control from 1996 to 1998, and is now a Subject Editor of International Journal of Robust and Nonlinear Control, and the Chair of IFAC Technical Committee of Stochastic Systems for 1999–2002, and the Chair of IFAC Coordinating Committee of Signals and Systems for 2002–2005. His research interests include estimation theory, stochastic realization, subspace method of identification, blind identification, and control of industrial processes.
- ☆
This paper was presented at IFAC Workshop on Adaptation and Learning in Control and Signal Processing (ALCOSP 04) and IFAC Workshop on Periodic Control Systems (PSYCO 04), Yokohama, Japan, August, 2004. This paper was recommended for publication in revised form by Associate Editor Antonio Vicino under the direction of Editor T. Söderström.