# Learning a function “online” as data arrives

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$$
• Whats the input dimension? (length of $x$). Also do you think $f$ is quite smooth or perhaps more rough? – jcken Apr 13 at 19:29
• @jcken $f$ should be smooth! – Physics_Student Apr 13 at 19:53
• @jcken and should be a univariate function! So $\text{dim}(x) =1$ – Physics_Student Apr 13 at 19:54

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!)