Learning a function "online" as data arrives

Question

I have a function $f: \mathbb{R} \to \mathbb{R}$ and as time goes by I get an input $x_t$ and, by feeding it through $f$ I obtain an output $y_t = f(x_t)$. There is no noise, this is a deterministic function.

How can I approximate this function at time step $\tau$? What is this task called? (online regressio?). What are some example algorithms to perform this and what is the current state of the art?

I would like to find a method that can be udated at each time step.This is what I mean:

• $t=1$: I receive $x_1$ and I obtain $y_1 = f(x_1)$. I use the pair $(x_1, y_1)$ to learn a first approximation $\hat{f}_1$
• $t=2$: I receive $x_2$ and I obtain $y_2 = f(x_2)$. I use $\{(x_1, y_1), (x_2, y_2)\}$ to update $\hat{f}_1$ to $\hat{f}_2$.
• $t=\tau$: I receive $x_\tau$ and I obtain $y_\tau = f(x_\tau)$. I use $\{(x_t, y_t)\}_{t=1}^{\tau}$ to update $\hat{f}_{\tau-1}$ to $\hat{f}_\tau$

Answer 1

One of the most popular ways to learn a (deterministic) function is Gaussian Process (GP) regression. It is commonly phrased in the Bayesian framework so that our 'prior beliefs' are

$$ f(\cdot) \sim GP(m(\cdot), C(\cdot, \cdot))$$ where $m(\cdot)$ represents our prior expected value of $f(x)$ for any $x$. It's usually a 'rough and ready' approximation. E.g. you might be able to say $f(\cdot)$ is approximately linear over the domain of interest. Or perhaps a quadratic. Nothing too fancy here.

The powerful component is $C(\cdot, \cdot)$ - the covariance function. By definition,

$$Cov( f(x), f(x')) = C(x, x')$$

that is $C$ tells us about how correlated $f(x)$ is with $f(x')$. A very common covariance function is $$ C(x, x') = \sigma^2 \exp \left\{ -\frac{(x - x')^2}{\theta^2} \right\}$$ which is commonly called the 'squared exponential' covariance function. It's useful when $f$ is thought to be very smooth (in fact, the squared exponential covariance implies $f$ is infinitely mean square differentiable.). The GP (with this covariance function) also has the nice property that if you observe $f(x_0) = y_0$ the GP predicition at $x_0$ will be exactly $y_0$. It is an interpolator.

Now, suppose I have observed outputs $y_i = f(x_i)$: $y = (y_1, y_2,\ldots, y_n)^T$ at $x = (x_1, x_2, \ldots, x_n)^T$. Denote the dataset $D_n = (x, y)$. Suppose I want to predict $y_0 = f(x_0)$ for some 'unseen' $x_0$.

Under these GP assumptions, any finite collection of $y$s will be multivariate normal:

$$ \begin{pmatrix} y \\ f(x_0) \end{pmatrix} \sim N \left\{\begin{pmatrix} m(x) \\ m(x_0) \end{pmatrix} , \begin{pmatrix} \Sigma_{yy} & \Sigma_{yy_0}\\ \Sigma_{y y} & \Sigma_{y_0 y_0 }\end{pmatrix} \right\}$$

Now the $\Sigma$ terms contain $C(x,x')$ for the various choices of $x_i$ we have observed. Then, conditional on $D_n$ we have $f(x_0) \sim N(m^*, v^*)$ with \begin{align} m^{*} &= m(x_0)- \Sigma_{y_0 y}\Sigma_{y y}^{-1}(y - m(x))\\ v^{*} & = \Sigma_{y_0 y_0} - \Sigma_{y_0 y}\Sigma_{y y}^{-1}\Sigma_{y y_0} \end{align} This is just a bit of simple matrix computation (can be a bit fiddly in practice though). Using some nice formulae, these predictions update nicely. See the equations between (8) and (9) here - this allows for 'online' prediction.

Let's wrap it up with a nice little picture of a prediction, given some data:

I'd also like to suggest Bobby Gramacy's textbook, Surrogates for further reading. It's geared specifically towards learning functions, it's quite new and a really nice read. There's also GPML an older textbook that is very popular (because it's very good!)