Sequence prediction with unlimited predictions

Question

I have a special kind of prediction problem.

I have observed $M$ sequences $X_m = [x_1, x_2, ..., x_N]$ where the distance $d$ between $x_n$ and $x_{n+1}$ is drawn from the same normal distribution, eg $d \sim N(\mu, \sigma^2)$. I can learn the parameters $\mu, \sigma$.

Now I need to predict/generate a whole sequence at once where a prediction $\hat{x}_n$ is considered correct if it falls within some absolute tolerance of the true data point $x_n$. There is one caveat: I can make as many predictions as I want without penalty but there must always be a minimum distance $\epsilon$ between predictions $\hat{x}_n$ and $\hat{x}_{n+1}$, where we can safely assume $\epsilon << d$. Intuitively, this makes me want to predict a pattern rather than trying to predict each point individually.

To re-iterate: a prediction that is outside the tolerance of a true data point is not penalized. We only need to maximize the number of correct predictions (that fall within the tolerance of a true data point).

Example 1

Prediction:       [10, 20, 30]
True observation: [11, 21, 31]
------------------------------
3 correct predictions if tolerance >= 1, else 0 correct predictions

Example 2

Epsilon = 4 (eg we can predict with a minimum distance 4)

Prediction: [6, 10, 15, 22, 30, 35]
True observation:      [11, 21, 31]
-----------------------------------
tolerance = 1 => 2 correct predictions (10, 30)
tolerance = 2 => 3 correct predictions (10, 22, 30)

What would be a good way to approach this problem? Are there problems that are similar?

Edited for clarity.

Answer 1

Your biggest issue with the evaluation scheme you have - "success" means within tolerance, "failure" means outside tolerance, plus your constraint on model outputs needing to vary per time step - is that it will be hard to extract gradients in order to train the prediction model directly. This rules out many simple and direct regression models, at least if you want to use "maximise number of scores within tolerance" as your objective function. The constraints on sequential predictions and allowing re-tries are also non-differentiable if taken as-is.

I think you have two top level choices:

1. Soften the loss function, and add the hard function as a metric

Use a differentiable loss function that has best score when predictions are accurate and constraints are met. For example your loss function for a single predicted value could be

$$L(\hat{x}_n, \hat{x}_{n+1}, x_{n+1}) = (\hat{x}_{n+1} - x_{n+1})^2 + \frac{a}{1+e^{s(|\hat{x}_n - \hat{x}_{n+1}| - \epsilon)}}$$

the second constraint part is essentially sigmoid with $a$ controlling the relative weight of meeting constraints with accuracy of the prediction and $s$ controlling the steepness of cutoff around the constraint.

a. The weighting between prediction loss and constraint loss will be a hyper-parameter of the model. So you would need to include $a$ and $s$ amongst parameters to search if you used my suggested loss function.

b. You can use your scoring system, not as an objective function, but as a metric to select the best model on a hyper-parameter search.

c. With this approach you can use many standard sequence learning models, such as LSTM (if you have enough data). Or you could just use a single step prediction model that you feed current prediction plus any other features of the sequence that is allowed to know, and generate sequences from it by calling it repeatedly.

This system should encourage re-tries that get closer to the true value.

2. Use your scoring system directly as a learning goal

This will require some alternative optimising framework to gradient descent around the prediction model (although some frameworks can generate gradients internally). Genetic algorithms or other optimisers could be used to manage parameters of your model, and can attempt to change model parameters to improve results.

For this second case, assuming you have some good reason to want to avoid constructing a differentiable loss function at all, then this problem can be framed as Reinforcement Learning (RL):

• State: Current sequence item prediction (or a null entry), as well as any known information such as tolerance, length of sequence, current sequence item value (which may be different from current prediction) $\epsilon$, $d$, $\mu$ or $\sigma$ can be part of the current state.

• The action is to select next sequence value prediction, or probably more usefully, the offset for the next sequence item value. Using offsets allows you easily add constraint for minimum $\epsilon$

• The reward is +1 for being within tolerance or 0 otherwise.

• Time steps match the time steps within a current sequence.

You can use this to build a RL environment and train an agent that will include your prediction/generator model inside it. There are a lot of options within RL for how to manage that. But what RL gives you here is a way to define your goal formally using non-differentiable rewards, whilst internally the model can still be trained using gradient based methods.

The main reason to not use RL here is if the prediction model must be assessed at the end of generating the sequence. In which case the "action" might as well be the whole sequence, and becomes much harder to optimise. It is not 100% clear to me from the question whether this is the case.

Caveat: RL is a large and complex field of study. If you don't already know at least some RL, you can expect to spend several weeks getting to grips with it before starting to make progress on your original problem.

There are alternatives to RL that could equally apply, such as NEAT - deciding which could be best involves knowing far more about the project (e.g. the complexity of the sequences you wish to predict) and practical aspects such as how much time you have available to devote to learning, testing and implementing new techniques.

Have you forgotten something?

If you allow infinite re-tries, then an obvious strategy is to generate a very large sequence moving up and down using different step sizes (all greater than $\epsilon$). This doesn't require any learning model, just a bit of smart coding to cover all integers eventually. Chances are this model is only a few lines of code in most languages.

If this is to be ruled out, then some other rule or constraint is required:

• Perhaps only positive increments are allowed in the predicted sequence (so we cannot re-try by subtracting and trying again)? This conflicts with your "unlimited predictions" statement.

• Perhaps a sub-goal here is to make the guessing efficient? In which case RL could be useful, as you can add a a discount factor to reward processing in order make the model prefer to get predictions correct sooner.

Answer 2

I don't have a proof for this, but I expect the best you can do is estimate the normal distribution of interval times from your training data, and then just predict points at the mean interval time. You don't seem to have any features the would indicate when an interval will be shorter or longer than average, so all you can do is predict the average and let it work out in the long run. Of course, if the mean interval time is longer than double your minimum prediction interval (epsilon), you should insert more predictions in the gap since there is no downside to doing so.