Adv Syst Sci Appl 2017; 3:58–66 Published online at http://ijassa.ipu.ru/ojs/ijassa/article/view/499 Regression Tree Control of Multidimensional Static Object Ekaterina Mangalova1∗ 1System Analysis and Control Department, Siberian State Aerospace University, Krasnoyarsk, Russia Abstract: In this paper the control problem of a static system under incomplete information is discussed. A nonparametric control algorithm based on Classification and Regression Tree is proposed and evaluated for different task formulations: controlled inputs – one-dimensional output, controlled and observed uncontrolled inputs – one-dimensional output, controlled and observed uncontrolled inputs – multi-dimensional outputs. Keywords: control, regression tree, machine learning, optimization 1. INTRODUCTION The modeling of technical systems and processes is the essentially important tool used in engineering to design, improve, optimize and control systems. Using simulation modeling is generally cheaper, safer and faster than conducting real-world experiments. This allows to use modeling for different alternatives analyses. There are two different ways to create simulation models: • Manually built models. A specialist builds the simulation model manually based on his theoretical knowledge and technical experience. This method is the most useful and imminent for systems that do not yet exist. • Statistical modeling. Statistical modeling is based on generating models by observations. This method can be useful for complicated systems when input-output relationships are not evident or are unknown, internals are not essential for the technical problem. Statistical models are used to detect a deviation of the normal behavior of a system and to control. Model Predictive Control is a family of controllers in which there is a direct use of an explicit and separately identifiable model. Control algorithms based on Model Predictive Control concept have found wide acceptance in practical applications and have been studied by researchers. In [1] one of the first successful applications of Model Predictive Heuristic Control is described. There are two commonly used and well studied approaches to Model Predictive Control: based on Artificial Neural Networks and based on Fuzzy Logic. The use of artificial neural networks in model based control, both as process models and as controllers, is investigated by D. C. Psichogios and L. H. Ungar [2]. A. Draeger, S. Engell, H. Ranke [3] implemented a feed-forward neural network as the nonlinear prediction model in an extended DMC-algorithm to control. H. Sarimveis and G. Bafas [4] introduceed the method based on a dynamic fuzzy model of the process to be controlled, which is used for predicting the future behavior of the output variables. In the paper [5] J. M da Costa Sousa and U. Kaymak investigated the use of fuzzy decision making in model predictive control. ∗Corresponding author: e.s.mangalova@hotmail.com http://ijassa.ipu.ru/ojs/ijassa/article/view/499 REGRESSION TREE CONTROL OF MULTIDIMENSIONAL STATIC OBJECT 59 In contrast to neural network and fuzzy logic approaches, in [6] a control algorithm based on the Nadaraya-Watson estimator [7] (as a predictive model) and their sequence is proposed. However, there are major problems with this approach in the case of a multidimensional control task. On the one hand, it is connected with observations distribution in a high- dimensional feature space (especially in the case of small number of observations). On the other hand, the Nadaraya-Watson estimator has the high computational complexity. The bigger feature space dimension, the harder to optimize the vector of bandwidths. Decision trees are used for solving such regression tasks [8]. To avoid these problems it is suggested to use a decision tree instead of the Nadaraya-Watson estimator. In this paper an approach based on Classification and Regression Tree (CaRT) is proposed to solve control tasks. The paper is organized as follows: in the second section, statements of the modeling and control problems are introduced; in the third section, the nonparametric modeling and control algorithm based on the Nadaraya-Watson estimator is presented; the fourth section is devoted to Classification and Regression Tree (CaRT) and the control algorithm based on CaRT with its variants for different control task statements. 2. MODELING AND CONTROL TASKS The block scheme of the control process is shown in Figure 1. The following designations are taken: x̄ is the vector of output variables, x̄∗ is the vector of the desired output x̄ values, ū is the vector of controlled inputs, v̄ is the vector of observed uncontrolled inputs, ξ is the unobserved input (noise). Fig.1 The block scheme of the control process It is evident from Figure 1 that the output variables x̄ depend on the inputs ū, v̄, ξ. The control task is to build a control unit which generates ū such that E (x̄, x̄∗) is minimized, where E is some error measurement. The modeling (regression) and control tasks are adjacent. If a system reaction to an input (prediction) is known, it is possible to get the desired outputs by identifying the controlled inputs [9]. The forward model (regression model) x̂ (ū, v̄) is fit using the training set (ūi, v̄i, x̄i, i = 1, ..., n), where n is the observations number (Figure 2). Using the forward model x̂ (ū, v̄) the reactions to a given input can be predicted. For control task solving, it is necessary to invert the model x̂ (ū, v̄). It means that we should find controlled inputs ū∗ that could result in the desired outputs x̄∗ in the case of estimated Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) 60 E. MANGALOVA Fig.2 Forward model scheme (regression task) uncontrolled inputs v̄predicted (Figure 3). In contrast to the forward model, the backward model û ( x̄∗, v̄predicted ) is fit using the training set (ūi, v̄i, x̄i, i = 1, ..., n) such that the outputs are given, uncontrolled inputs are predicted and we need to determine an appropriate controlled input. Fig.3 Backward model scheme (control task) 3. NADARAYA-WATSON ESTIMATOR APPROACH The Nadaraya-Watson estimator approach was proposed to solve control tasks in such forward-backward models statement [6]. 3.1. Modeling The Nadaraya-Watson estimator has been widely applied for the nonparametric regression, using the weighted average observations output in the neighborhood around (ū, v̄): x̂k (ū, v̄) = ∑n i=1 xi ∏mu j=1K ( uj, uji , c j u )∏mv j=1K ( vj, vji , c j v )∑n i=1 ∏mu j=1K ( uj, uji , c j u )∏mv j=1K ( vj, vji , c j v ) , k = 1, ...,mx, (3.1) where the kernel function K is a non-negative function that integrates to one and has zero mean, c̄u, c̄v are the vectors of bandwidths, mx is the number of output variables. To identify the forward models x̂k (ū, v̄), the bandwidths c̄u, c̄v should be optimized according to the selected accuracy measurement. 3.2. Control Backward models of Nadaraya-Watson estimators have the following form: Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) REGRESSION TREE CONTROL OF MULTIDIMENSIONAL STATIC OBJECT 61 ûm ( u1, ..., um−1, x̄, v̄ ) =∑n i=1 u m i ∏m−1 j=1 K ( uj, uji , c j u )∏mv j=1K ( vj, vji , c j v )∏mx j=1K ( xj∗, xji , c j x )∑n i=1 ∏m−1 j=1 K ( uj, uji , c j u )∏mv j=1K ( vj, vji , c j v )∏mx j=1K ( xj∗, xji , c j x ) , m = 1, ...,mu, (3.2) the bandwidths c̄u, c̄v in the equations (3.1) and (3.2) are not identical. There are some important limitations on the Nadaraya-Watson algorithm implementation: • Ranking input features. The controlled input variables ū should be ranked by their importance. The process (3.2) starts from the most important controlled input feature and continues with less and less important ones. • Bijective relationship. The forward models (the true relationships between input features and output features) should be bijective functions. Suppose there are two significantly different controlled inputs ū∗1 and ū∗2 that produce the desired output. The result of the algorithm is a controlled input values between ū∗1 and ū∗2 (this control does not lead to the desired output) instead of choosing one of them. • Curse of dimensionality. It is connected with observations distribution in a high dimensional feature space (especially in the case of a small number of observations). Suppose, there are n = 1000 points uniformly distributed over the ten dimensional unit cube [0, 1]10. An average over the neighborhood of diameter 0.25 (in each coordinate) results in the volume of 0.2510 ≈ 0.00000095 for the corresponding ten-dimensional cube. Hence, the expected number of observations in this cube will be 0.00095 and any averaging can not be expected. If we fix the count k = 1 of observations over which to average, the diameter of the typical neighborhood will be larger than 0.5. It means that the average is calculated over at least one-half of the range along each coordinate [10]. 4. DECISION TREE APPROACH Decision trees are commonly used for solving regression tasks in multidimensional cases and allow preventing the Nadaraya-Watson algorithm limitations described in section 3. 4.1. Modeling Decision tree is a piecewise constant nonparametric model. The most popular decision tree model is Classification and Regression Tree (CaRT) [8]. CaRT is a binary tree where each root node represents an input variable ujr and a split point br. Let us aggregate controlled and observed uncontrolled inputs to make the description easier: ū = {u1, ..., umu , v1, ..., vmv}. Each leaf node contains values of the output variable x which is used to make a prediction. CaRT fitting involves input variables and split points selection until a suitable tree is constructed. Input variables and split points are chosen using a greedy algorithm to minimize the: min j min b ∑ i:uj ib L ( xi, x̂ + (ūi, j, b) ) (4.3) where x̂− (ūi, j, b) or x̂+ (ūi, j, b) is the prediction in the point ūi based on the subspaces after splitting: Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) 62 E. MANGALOVA x̂− (ūi, j, b) = ∑ i:uj ib xi∑ i:uj i>b 1 . (4.4) The tree construction ends using a predefined stopping criterion, such as the minimum number of observations assigned to each leaf node of the tree or the maximum depth of the tree. Each node in the tree corresponds to a rectangular region of the predictor space Sk, a subset of the observations lying in the region Sk, a constant x̂k which is the average response of the observations in k-th rectangular region. Thus, the binary tree model can be formalized as follows: x̂ (ū) = { x̂k : ū ∈ Sk, k = 1, 2, ..., K } . (4.5) 4.2. Control Control tasks can be solved using the regression trees in different formulations depending on the number of input and output values, presence of observed uncontrolled input variables. Consider the basic formulation of the problem. 4.2.1. Controlled inputs - one-dimensional output. Assume there are only controlled variables ū and one output variable x. Decision tree is fit using the training dataset containing simultaneous observations of ū and x. The control algorithm: 1. Set the control target x∗. 2. Search for such leaf node that k∗ = arg min k D1 (x̂k, x ∗) , (4.6) where D1 is a one-dimensional distance measurement. Call k∗-th node ”target node”. 3. Find control ū∗ contained in the region Sk∗ . There are different ways to choose this control: • The center of the rectangle guaranties the most accurate forward model prediction (decision tree prediction). • Points on the rectangle boundary allow to explore object and collect more information. • Also the distance between the previous control and the current control can be minimized to reduce interference in the system. The experimental result. Suppose the object is represented by the equation: x = sin (2πu1) + √ u2 − u3 + ξ . This equation is used in the computational experiment to simulate a real process. Input variables u1, u2, u3, u4 are bounded by [0, 1]. The initial dataset contains 10 points distributed uniformly. Control is selected as the center of the target node. Figure 4 illustrates the desired outputs and the reactions to a generated control. Figure 5 shows the initial dataset and the observations obtained during the simulation process. 4.2.2. Controlled and observed uncontrolled inputs - one-dimensional output. Assume there are controlled and observed uncontrolled variables ū and one output variable x. The decision tree is fit using the training dataset containing simultaneous observations of ū and x. The control algorithm: 1. Set the control target x∗. Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) REGRESSION TREE CONTROL OF MULTIDIMENSIONAL STATIC OBJECT 63 Fig.4 Simulation of a process. Desired outputs and reactions to a generated control Fig.5 Simulation of a process. Initial dataset and generated dataset 2. Predict the uncontrolled input variables uj,predicted, j = mu + 1, ...,mu +mv. 3. Cut nodes which can not be achieved with the predicted uncontrolled input variables. 4. Search for a leaf node such that k∗ = arg min k,ū′∈Sk D1 (x̂k, x ∗) , (4.7) where ū′ is the input values such that u′j ,j = 1, ...,mu can take any value and u′j = uj,predicted,j = mu + 1, ...,mu +mv. 5. Find a control ū∗ contained in the region Sk∗ . The experimental result. Suppose now that u2 is uncontrolled and changed as follows u2 i = sin (πi/25). The previous value of u2 i−1 is used as a prediction for the next step u2,prediction. Figure 6 illustrates the desired outputs and the reactions to a generated control. Figure 7 shows the initial dataset and the observations obtained during the simulation process. 4.3. Multi-dimensional output, controlled and observed uncontrolled inputs Assume there are controlled and observed uncontrolled variables ū and the vector of output variables x̄. Decision trees are fit using the training dataset containing simultaneous observations of ū and x̄. The control algorithm: 1. Set the control targets x̄∗. 2. Predict the uncontrolled input variables uj,predicted, j = mu + 1, ...,mu +mv. 3. Find intersections of nodes which contain the predicted uncontrolled variables Sk 1,...,mu , k = 1, ..., K ′ and the output values associated with these intersections x̂1 k,..., x̂mx k . Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) 64 E. MANGALOVA Fig.6 Simulation of a process with uncontrolled input. The desired outputs and the reactions to the generated control Fig.7 Simulation of a process with uncontrolled input. The initial dataset and the generated dataset 4. Search for a leaf node such that k∗ = arg min k Dmx ( x̂1 k, ...x̂ mx k , x̄∗ ) , (4.8) where Dmx is a multi-dimensional distance measurement. 5. Find a control ū∗ contained in the region Sk∗ 1,...,mu . The experimental result. Suppose now there are two outputs x1 = sin (2πu1) + √ u2 − u3 + ξ and x2 = √ u2 − u3 + ξ. Figure 8 illustrates the desired outputs and the reactions to a generated control. The desired outputs for x1 and x2 are the same. Figure 9 shows the initial dataset and the observations obtained during the simulation process. Fig.8 Simulation of a multidimensional process. The desired outputs and the reactions to a generated control Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) REGRESSION TREE CONTROL OF MULTIDIMENSIONAL STATIC OBJECT 65 Fig.9 Simulation of a multidimensional process. The initial dataset and the generated dataset) CONCLUSION In this paper a control task of a multidimensional static system is discussed. The paper presents the advantages and disadvantages of the nonparametric algorithm based on the Nadaraya-Watson estimator and their sequence. In order to avoid the disadvantages of this nonparametric algorithm, the modification with piecewise constant approximation of the nonparametric estimator is put forward. In the proposed algorithm Classification and Regression trees are used as a predictive model instead of the Nadaraya-Watson estimator. The control algorithm based on CaRT is tested for different task formulations: controlled inputs and one-dimensional output, controlled and observed uncontrolled inputs and one- dimensional output, controlled and observed uncontrolled inputs and multi-dimensional outputs. REFERENCES 1. Richalet J., Rault A., Testud J.L. & Papon J. (1978). Model predictive heuristic control: Applications to industrial processes, Automatica, 14 (5), 413–428. 2. Psichogios D. C. & Ungar L. H. (1991). Direct and indirect model based control using artificial neural networks, Industrial & engineering chemistry research, 30 (12), 2564– 2573. 3. Draeger A., Engell S. & Ranke H. (1995). Model predictive control using neural networks, IEEE Control Systems Magazine, 15 (5), 61–66. 4. Sarimveis H. & Bafas G. (2003). Fuzzy model predictive control of non-linear processes using genetic algorithms, Fuzzy sets and systems, 139 (1), 59–80. 5. da Costa Sousa J.M. & Kaymak U. (2001). Model predictive control using fuzzy decision functions, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 31 (1), 54–65. 6. Medvedev A.V., & Raskina A.V. (2017). On the Nonparametric Identification and Dual Adaptive Control of Dynamic Processes, Journal of Siberian Federal University. Mathematics & Physics, 10 (1), 96–107. Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) 66 E. MANGALOVA 7. Nadaraya E. A. (1964). On estimating regression, Theory of Probability and Its Applications, 9, 141–142. 8. Breiman L., Friedman J., Stone C. J. & Olshen, R. A. (1984). Classification and regression trees. CRC press. 9. Kunh S. & Guhmann C. (2008) Modeling and Control with Local Linearizing Nadaraya Watson Regression, arXiv:0809.3690. 10. Härdle W. (1990) Applied nonparametric regression. Cambridge University Press. Copyright c© 2017 ASSA. Adv Syst Sci Appl (2017) https://arxiv.org/abs/0809.3690 Introduction Modeling and control tasks Nadaraya-Watson estimator approach Modeling Control Decision Tree approach Modeling Control Controlled inputs - one-dimensional output. Controlled and observed uncontrolled inputs - one-dimensional output. Multi-dimensional output, controlled and observed uncontrolled inputs Bibliography