2
$\begingroup$

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

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:enter image description here

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.