Regression analysis is the statistical process used to estimate the relationship between a dependent variable and one or more independent variables. In machine learning, typical statistical approaches to regression such as linear regression are often replaced with symbolic learning, such as decision tree regression, to capture non-linear behaviour while keeping the interpretability of the results. For temporal series, regression is sometimes enhanced by using historical values of the independent variables. In this paper, we show how temporal regression can be handled by a symbolic learner based on interval temporal logic decision trees.
A multivariate time series [
Regression is the statistical process used to capture the parameters that influence the relationship between independent and dependent variables. In the context of temporal regression with machine learning, temporal regression autoregression ex.: Arima functional regr. symbolic regr. exa.a:aaaaaaaaaaaaaaaaaaaaaaaaaaaaRaaeagaraaeasasaiaoaanaatrees
Linear regr ex.: | via lagged tr{aznsformation } there are three main categories of approach. Autoregression is a set of statistical techniques developed mainly to model the idea that past values of the independent variable may influence, in several different ways, future values. These are techniques originally developed for univariate series, and later extended to the multivariate case. Lagged variables is the machine learning generalization to the latter idea, so to say, and it consists of transforming the original data set by adding virtual variables that represent the past values. For example, for a independent variable Ai(t) (in which we make it explicit the temporal parameter), one adds the lagged variable Ai(t − 1) and Ai(t − 2), . . ., that correspond, respectively, to the value of Ai one, two, . . . , units of time before. In this way, a static learner (where each instance of the data set is independent from any other) can be used on the transformed data set, giving rise to the possibility of using functional regression algorithms, such as linear regression and neural networks, among others, and symbolic regression algorithms, such as regression tree learning algorithms. While certain classical regression algorithms, such as linear regression or decision trees are interpretable by nature (that is, they return an explicit model), the possibility of understanding the underlying process may be hampered by the presence of lagged variables.
Regression trees were introduced in the CART (classification and regression trees) system in [
Time Series and Interval Temporal Logic
Let [N ] an initial subset of N of length N . An interval over [N ] is an ordered pair [x, y], where x, y ∈ [N ]
and x < y, and we denote by I([N ]) the set of all intervals over [N ]. If we exclude the identity relation,
there are 12 different Allen’s relations between two intervals in a linear order [
HS hAi hLi hBi hEi hDi hOi
Allen’s relations [x, y]RA[x0, y0] ⇔ y = x0 [x, y]RL[x0, y0] ⇔ y < x0 [x, y]RB[x0, y0] ⇔ x = x0, y0 < y [x, y]RE[x0, y0] ⇔ y = y0, x < x0 [x, y]RD[x0, y0] ⇔ x < x0, y0 < y [x, y]RO[x0, y0] ⇔ x < x0 < y < y0
Graphical representation x y
ϕ ::= p | ¬ϕ | ϕ ∨ ϕ | hXiϕ | hX¯ iϕ, where p ∈ AP and X ∈ X . The other Boolean connectives and the logical constants, e.g., → and >, as well as the universal modalities [X], can be defined in the standard way, i.e., [X]p ≡ ¬hXi¬p. For each ¯ X ∈ X , the modality hXi (corresponding to the inverse relation RX¯ of RX ) is said to be the transpose of the modalities hXi, and vice versa. The semantics of HS formulas is given in terms of timelines T = hI([N ]), V i, where V : AP → 2I([N]) is a valuation function which assigns to each atomic proposition p ∈ AP the set of intervals V (p) on which p holds. The truth of a formula ϕ on a given interval [x, y] in an interval model T is defined by structural induction on formulas as follows:
T, [x, y] T, [x, y] T, [x, y] T, [x, y] T, [x, y] p ¬ψ ψ ∨ ξ hXiψ hX¯ iψ if [x, y] ∈ V (p), for p ∈ AP; if T, [x, y] 6 ψ; if T, [x, y] ψ or T, [x, y] ξ; if there is [w, z] s.t [x, y]RX [w, z] and T, [w, z] if there is [w, z] s.t [x, y]RX¯ [w, z] and T, [w, z] ψ; ψ.
A time series can be described by formulas of HS, in which propositional letters represent decisions of
the type Ai ./ k (./ ∈ {≤, =, >}) for some value k. We can arbitrarily impose that a decision Ai ./ k is
true on an interval [x, y] if and only if the ratio between number of time points between x and y having a
value that satisfies ./ k and the quantity y − x is at least α, for a fixed α. From there, we can lift the
evaluation to a formula. For example, in Fig. 3, the series T is such that T, [
Interval Temporal Logic Regression Trees
Static regression learning is exemplified in Fig. 3, middle, left. If we want to construct a static regression
model for the values of B, say, from the time point 3 to the time point 8, we build a data set with
the values of A1, A2 at each of such points associated with the corresponding value of B. Static lagged
regression improves upon static learning by associating also the values of A1 and A2 at t − 3, t − 2, and
so on; a multivariate linear regression algorithm, or a regression tree, may benefit from this historical
information to build a model for B. Since a static regression tree is an NP-hard problem, the most popular
solution is to use a sub-optimal greedy strategy based on the following principles [
Ij
Ai ./ k to decide if Ij belongs to D1 or D2. Then, D, D1, and D2 are compared against each other establish the amount of information conveyed by that split; in regression problems, the information can simply be the (1) (2) 35 120 42 30 115 41 25 110 40 A2 • 20 105 39 15 100 38 B • 10 95 37 5 90 36 A1 • A1 A2 B variance of the predicted attribute in each data set. So, a simple greedy strategy can be devised: (i) at each step, if the stopping condition is not reached, find the attribute Ai and the value k that maximize the information conveyed by a split on that decision; (ii) split the current data set on the basis of the decision taken at the previous step; (iii) perform two recursive calls on the obtained data sets. At the end of this process, the entire model is described by a tree whose edges are labeled by decisions, and each branch can be seen as a propositional formula.
Here, we propose to design an algorithm capable to extract a regression tree after a transformation as
in Fig. 3, bottom. For a fixed lag l, to each value B(t), we associate the finite time series described by
Ai(t − l), Ai(t − l + 1), . . . for each i, and each represented by a string. We define a split based on a HS
formula of the type hXi(Ai ./ k ), which we call atomic HS formulas, where decisions have taken the place
of propositional letters. Thus, fixed a lag l, at the beginning, the time series T with N points is replaced
by a data set T = {T1, . . . , TN−l+1} in which each instance is, itself, a multivariate time series labelled by
a value of B and encompassing l points. Each of such series is initially associated to a reference interval
generically denoted [
Tj , [x, y]
hXi(Ai ./ k ).
By applying the same learning algorithm, then, one obtains a tree whose edges are labeled with atomic HS formulas instead of propositional formulas, and whose branches, then, can be read as formulas of HS. In this way, the obtained regression tree keeps the original non-linear (step-type) behaviour, but takes into account the recent history of a value to perform the prediction, and it does so natively. Initial experiments on real data sets seem to offer encouraging results. 4
We have sketched the theoretical bases for a temporal regression tree learning algorithm, based on the interval temporal logic HS, which allows us to natively take into account the past values of the independent variables and their mutual relationships.