Today's systems are highly complex and often appear as black-box systems because of unknown internal functionalities. Thus, retrieving a model of a system is possible only based on observations of the system. We explore the usage of regression trees to learn a model of a complex system with continuous signals. Our approach for learning a regression tree uses observed inputs and outputs of a system from bounded history. We describe how to construct such a model and analyze the accuracy of predictions. Results show the applicability of regression tree models for continuous systems.
approximation. In this paper, we consider systems with real-valued input and output signals as [11], but examine capabilities of regression trees as system models.
Definition 1 (Regression Tree). A regression tree is a tree = (, ) consisting of a set of nodes and a set of edges . The regression tree represents a function : → R that maps a feature vector f = [1, ..., ] from the domain to a real number. The set of nodes without outgoing edges are called leaf nodes or leaves. All other nodes ∖ are inner nodes [12].
We assume a binary regression tree where each inner node has exactly two outgoing edges. A regression tree is built based on a learning set ℒ consisting of a set of labeled feature vectors (f , ) with f ∈ and ∈ R. Every node in the tree represents a subset ⊆ ℒ where each inner node splits its set into disjoint subsets 1 , 2 associated to the successors 1, 2 of . The leaf nodes have a label representing the output of the regression function . The label is calculated as the mean value over all labels in the set as follows = 1
∑︁ | | (f,)∈ .
(
Regression trees tend to overfit the learning data. To overcome overfitting, there exist multiple strategies. Here, we apply a binning step before tree learning as part of the algorithm – meaning that equidistant discretization intervals (bins) are used for all real-valued features. 2.2. Learning Regression Tree Models of Systems We consider a black-box system that receives a possibly multi-dimensional input i of dimension and outputs a one-dimensional output ∈ R. This is a valid assumption, as usually a single value of interest is observed at a time. If several outputs are considered, multiple regression tree models can be learned in parallel. Inputs are categorical or real-valued. The observation of a system results in sequences ˜s = ⟨(i0, 0), (i1, 1), . . . ⟩ representing sampled inputs and outputs over discrete time points. We assume to observe the system with bounded history, which is a practical requirement assuming that limited memory is available. Thus, the learning data results in observations s = ⟨(i0, 0), . . . , (iN, )⟩ of length + 1 with ∈ N. The regression tree requires a learning set ℒ consisting of tuples (f , ). Given a sequence s, we map to an observation for the learning set as follows f = ⟨11, . . . , , 1, 21, . . . , 2, . . . , 1 , . . . , ⟩, = .
1
(
With this mapping, the learned regression tree represents the prediction of the next output based on the knowledge about all previous in- and outputs of the last time steps. The regression tree’s prediction accuracy is validated on an evaluation set ℰ consisting of tuples of 4 E (a) Example of a Discrete System (b) Example of a Continuous Signal feature vectors and a known next output (f , ). We use the mean prediction error (Eq. 3) as a quality metric for the learned regression tree model.
= 1
∑︁
|ℰ | (f,)∈ℰ
| − (f )|
(
For an optimal model, the prediction (f ) always perfectly matches the exact output . Regression tree models according to our approach have some theoretical limitations introducing approximations that lead to imperfect predictions. A first reason for approximations is the usage of bounded history, because the information from previous time steps might not be suficient to fully determine the system’s status and, thus, determine an upcoming output. Example 1. Consider that Fig. 1a shows a valid, discrete abstraction of a system, where circles 1 to 4 represent states of the system, while arrows are transitions labeled with observations from the alphabet {, , , , }. Because of the two self-loops with observation at state 1 and 3, bounded history does not always allow to clearly determine, in which of these states the system is and, thus, what the next observed symbol will be.
Further limitations result from the sampling of the time-continuous signals and the fact that
a regression tree has a finite set of results – thus, approximating the actual real-valued output.
Example 2. Considering a system with an output signal as in Fig. 1b, we could achieve optimal
predictions under the following conditions (
In the following, we present an empirical evaluation on example systems. For all examples 150 simulation runs are used for learning, while 50 additional simulation runs provide evaluation data. Sampling periods are provided with respect to the simulation time unit and, thus, come without physical unit. The number of bins for regression tree learning is set to 30 which was empirically found suitable within the interval of 10 to 100 bins.
Water Reservoir A water reservoir with one tank. The input signals are the flow rates at inflow and outflow valves while the output is the water level of the reservoir. The input and output flow rates are alternating, periodic rectangular functions describing modes of inflow and outflow. The system is modeled in Matlab and the total duration of one simulation run is 50 time units.
Boiler A temperature control system based on [13]. The input signal is the reference temperature which changes every 50 time units randomly to values from the set {18 ∘ C, 19 ∘ C, . . . , 25 ∘ C}. The output signal is the water temperature of the boiler starting at 15 ∘ C. The overall simulation time of one run is 1400 time units.
0.006 0.004 0.002 0 2 4 6 8
10 (a) Waterreservoir
We presented an approach to model complex systems using regression trees allowing to include continuous signals from observations of bounded history without resetting the system to an initial state. We introduced a mapping from system observations to labeled feature vectors for regression tree learning. The resulting regression tree model represents a decision rule that predicts a next output signal based on previous behavior of the system. Future work considers to evaluate further strategies for regression tree pruning and analysis of the influence of the sampling frequency as well as discretization-related approximations in modeling. This work is partially funded by BMBF project AGenC no. 01IS22047A.