2
$\begingroup$

Context

I have two related time series, I want to learn to produce one from the other. However, they aren't synchronous, and the lag between the two does not revert to the mean, it accumulates.


Known relationship, dynamic programming

I am given two, random, ergodic, time series $X = (x_1, \ldots, x_t, \ldots, x_N)$ and $Y = (y_1, \ldots, y_t, \ldots, y_N)$

Given two time series, a classic dynamic programming problem consists in minimizing an edit distance between the two. For instance, we can assign a cost $c(X,X') = \frac{1}{2}\lambda(|X|-|X'|)$ to removing some elements in $X$, forming $X'$, and likewise a cost $c(Y,Y') = \frac{1}{2}\lambda(|Y|-|Y'|)$ to removing elements from $Y$, forming $Y'$. We impose $|X'| = |Y'| = N - P$.

We then minimize $\lambda P + \frac{1}{2}||X'-Y'||_2^2$

Once again, so far this is vanilla dynamic programming.


Unknown relationship

Suppose however that we want to minimize

$$\min_{\theta} \left(\lambda P + \sum_{t=1}^{N-P} (y'_t - f_{\theta}(x'_t))^2\right)$$

where $f_{\theta}$ is a parametric function (think neural-net or Gaussian process)

This is a trickier situation because we do not know in advance what the cost function is going to be.


First idea: iterative optimization

My first idea is to iteratively optimize for $\theta$ and then solve the dynamic programming problem. However, unless I start with a good idea of $\theta$, this is unlikely to converge.

Consider indeed the following example $X=(451,5,3,1,7,9,\ldots,N)$, $Y=(25,9,1,49,81,\ldots,N^2,-238)$.

A very good fit is to drop the first element of $X$ and the last element of $Y$ and just let $f(x) = x^2$. However, unless I first discover this relationship, I am unlikely to ever come up with removing the first element of $X$ and the last element of $Y$. I need a good initialization of $X'$ and $Y'$.


Second idea: initialization with K-mean

My second idea is to use K-means to initialize $X'$ and $Y'$. The idea would be as follow.

  1. Perform K-means clustering on the values taken by X, and K-means clustering on Y
  2. Minimize $$\min_{\sigma \in S(K)} \lambda P + \sum_{t=1}^{N-P} \delta(k_y(y'_t),\sigma(k_x(x'_t)))$$ where $\sigma$ is taken over the set of permutations of $K$ elements, $k$ represents the cluster number of an element.

The hope here is that enough datapoints will be correctly matched between $X$ and $Y$ and I can then iteratively learn $\theta$.


The question

My question is two-fold:

  1. Is there a nicer approach with stronger theoretical guarantees?
  2. Are there parametric functions which are somewhat generic enough for this to be solvable exactly or for convergence to be guaranteed? For instance, if $f$ is a linear transform, is there an exact solution?
$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.