Machine learning for regression of a function that is dependent on its own previous state?

Question

I've been taking a machine learning class, and we learned various techniques for machine learning regression. The examples we considered were typically simple functions, such as a linear function $f(x) = ax+b$. But I'm thinking about how to apply machine learning to my own research, and a question that I have been wondering is, are there techniques to perform regression on functions of the form:

$$x_{k+1} = f(x_k)?$$

This would be something like a discretization of a differential equation, where you have, for example,

$$x_{k+1} = x_k + h f(x_k).$$

I've thought about this idea for a while, and I've even tried to apply methods such as decision trees and SVR to this kind of problem, but I am concerned that I'm doing something that is just ridiculous and mathematically incorrect. I also recognize that there is a problem because in order to have a training set, we would need pairs such as $(x_k,x_{k+1})$, $(x_\ell,x_{\ell+1})$, which is unlikely to happen in any real data collection method. But, I'm interested in looking for into this idea and I'm hoping that it is viable and that someone has already written about it in a paper so I can learn more about it.

Thanks!

Answer 1

First thing to notice it that you are talking about time-series data, so good thing to start would be to start would be some handbook on this topic like Forecasting: principles and practice by Rob Hyndman and George Athanasopoulos that is freely available online.

As about your question, ordinary regression for time-series data is rather a bad idea since regression assumes independence of errors and in case of time-series data they would be auto-correlated. But there are models designed especially for time-series.

Your description of model fits AR(1) model

$$ X_t = c + \varphi X_{t-1}+\varepsilon_t $$

Of course, you can apply machine learning methods for such data, but the "traditional" time-series methods often outperform them (e.g. check Timeseries forecasting using extreme gradient boosting post recently linked on r-bloggers.com)

As about validating the model, using classic cross-validation is a bad idea because it destroys the structure of the data, so you should rather think of sampling whole blocks of data, or techniques as one-step-ahead forecast to estimate errors (i.e. $x_1,\dots,x_t$ data to predict $x_{t+1}$, next using $x_1,\dots,x_t, x_{t+1}$ to predict $x_{t+2}$ etc.).

Answer 2

What you are asking for is a stochastic process. You should specifically look for Gaussian processes. A Gaussian process is an ensemble of signals such that at every finitely many instance; the values constitute a multivariate Gaussian random variable,i.e., $x_t \sim \mathcal{GP}(\mu(t),k(t,t^{\prime}))$ implies $(x(t_1),x(t_2),\dots,x(t_n))\sim \mathcal{N}(\mu,\mathbf{K})$. After determining a proper kernel you might extrapolate adequately, see this classical example.

GP regression is actually a general regression tool and can be applied to high-dimensional regression problems, but for your time-series application; it actually has desirable properties, i.e. for specific kernels the GP regression model can be reduced to a Kalman filtering model, see this.

For your specific problem, a GP state space model can also be a proper fit. In the case of GP-SSMs, your transition and observation functions are being learned nonparametrically through data.

Answer 3

The linear case has been extremely well studied in econometrics, and is known as an autoregressive model. This is probably the most highly developed sub-topic in terms of model estimation, and is typically expanded to include the ARIMA framework.

For the nonlinear case, iterated nonlinear maps such as the logistic map have historically been popular in the "nonlinear dynamics/chaos" physics community, but to my knowledge most of these efforts use existing models (commonly "toy" heuristic models intended to distill known dynamics). There has been a bit of work on "attractor reconstruction" via delay-embedding, which can apply to arbitrary data (i.e. it is "model free"), but this has not developed very much in practical applications to my knowledge.

For most of these classical approaches, the forward-model part is well summarized at Wikipedia here. One other branch of "classical" approaches is state space modeling, which has been highly developed in engineering and robotics, including recursive Bayesian estimation (Kalman/Particle filters) for data assimilation, feedback control, and system identification. These classical approaches have generally focused on estimation of a known (and commonly very sophisticated) model, rather than black box "machine learning". However the sub-field of Hidden Markov Models (HMMs) has perhaps more of a machine learning flavor, including estimation methods.

Among newer "black box" techniques, Recurrent Neural Networks (RNNs) are fairly well developed. Recently the "deep" variants have shown very good results in diverse application domains, and are starting to displace some of the classical approaches such as HMMs (similar to ConvNets in Computer Vision).