14
$\begingroup$

I have been trying to solve this problem for over a year without much progress. It is part of a research project I'm doing, but I will illustrate it with a story example I made up, because the actual domain of the problem is a bit confusing (eye-tracking).

You are a plane tracking an enemy ship that travels across the ocean, so you have collected a series of (x,y,time) coordinates of the ship. You know that a hidden submarine travels with the ship to protect it, but while there is a correlation between their positions, the submarine often wanders off from the ship, so while it's often near it, it can also be on the other side of the world occasionally. You want to predict the path of the submarine, but unfortunately it is hidden from you.

But one month in April you notice the submarine forgets to hide itself, so you have a series of coordinates for both the submarine and the ship throughout 1,000 trips. Using this data, you'd like to build a model to predict the hidden submarine's path given just the ship's movements. The naive baseline would be to say "submarine position guess = "ship's current position" but from the April data where the submarine was visible, you notice there is a tendency for the submarine to be ahead of the ship a bit, so "submarine position guess = ship's position in 1 minute" is an even better estimate. Furthermore, the April data shows that when the ship pauses in the water for an extended period, the submarine is likely to be far away patrolling the coastal waters. There are other patterns of course.

How would you build this model, given the April data as training data, to predict the submarine's path? My current solution is an ad-hoc linear regression where the factors are "trip time", "ship's x coordinate", "was ship idle for 1 day", etc. and then having R figure out the weights and doing a cross-validation. But I would really love a way to generate these factors automatically from the April data. Also, a model that uses sequence or time would be nice, since the linear regression doesn't and I think it's relevant.

Thanks for reading through all this and I would be happy to clarify anything.

$\endgroup$
  • 5
    $\begingroup$ One way which may make it easier to build your model is to use polar co-ordinates instead of cartesian ones. If you set the origin equal to the enemy ship, and have the ship facing north always, then you could say something like position of the sub at time $t_j$ is $(r(t_j),\theta(t_j))$ with $r$ being distance and $\theta$ being angle. Now we expect $|\theta|$ to be small because the sub is usually in front of the ship, and $r$ should be small but not close to zero (else the sub crashes into the ship). You also have $r$ getting large for ships that pause. $\endgroup$ – probabilityislogic Feb 17 '13 at 12:35
  • 2
    $\begingroup$ I was going to suggest something similar to probabilityislogic - you need a variable that is the distance between the ship and the sub. The nice thing about polar coordinates is that this information, as well as directionality, are included as well. You might then try a linear regression on this new variable. $\endgroup$ – learner Feb 17 '13 at 12:40
  • $\begingroup$ Thanks for the suggestions. One thing I'm struggling with polar coordinates for is that if I try and predict the angle variable, it "loops around" so 0 == 360, which doesn't make sense in a prediction point of view. Any suggestions how to deal with it? $\endgroup$ – Cargoship And Submarine Feb 18 '13 at 5:29
  • $\begingroup$ @probabilityislogic After thinking about this a little bit more, would it make sense to use polar coordinates but use the sin(theta) instead of theta as the variable to predict? Although then it would behave more like a delta_y. $\endgroup$ – Cargoship And Submarine Feb 19 '13 at 22:10
  • $\begingroup$ Regarding use of polar coordinates, you might want to read about Directional Statistics. $\endgroup$ – steadyfish Feb 26 '13 at 2:20
3
$\begingroup$

Here's an approach which doesn't use any "contextual" information i.e. it fails to take into account the fact that "a sub is following a ship". On the other hand it is easy to start with:

Denote by

$x_{sub}(t), y_{sub}(t)$

$x_{ship}(t), y_{ship}(t)$

the coordinates of the submarine and the ship at time $t$, and define the "distance-series" by

$x_{dist} (t) = x_{ship} (t) - x_{sub} (t)$

$y_{dist} (t) = y_{ship} (t) - y_{sub} (t)$

My suggestion is that you predict each of these separately (you can tie them together later).

Let's take a moment to picture what these look like. Let's focus on the $x$-coordinate, and let's say that the ship is moving towards the right with the sub following behind it. Suppose the sub is around 100 meters behind the ship, with a deviation of say 10 meters.

Then

$x_{dist} (t) = 100 \pm 10 \cdot wiggle(t)$

You could then model the "$wiggle$" function as a Gaussian white-noise variable having zero mean and unit variance.

Now (still focussing on the $x$ coordinate, the story for $y$ is the same) if the $wiggle$ function were white noise, you would be able to compute the mean $\mu$ and the standard deviation $\sigma$ of the series $x_{dist}$ and write

$x_{dist}(t) = \mu + \sigma \cdot W_x(t)$

Since you have actual data, you can compute the time-series $W_x(t)$ and see if it follows a Gaussian (i.e. Normal) distribution. If it does, or even if it is any distribution you recognize, you could then generate values and make predictions for $x_{dist}$.

Another strategy people employ (which I think will work for you) is that they break up their series into

Polynomial base + Cyclic pattern + Bounded randomness

In the case of a submarine and a ship, the polynomial part would probably be constant and the cyclic part a sum of sines and cosines (from the waves of the ocean...). This may not be the case for eye-tracking.

There are tools which can figure this out for you. Here are two that I know of:

  1. DTREG (30 day evaluation license)
  2. Microsoft Time Series Algorithm which is part of their SQL Server product. I am currently using their 180-day evaluation edition, it is easy to use.

Here is a screenshot from the SQL Server tool (the dotted part is the prediction):

enter image description here

One algorithm they use is called ARIMA. Wanting to learn how it works, I did some Googling and found this book: First Course on Time Series (and don't worry, you don't need to have SAS to follow along. I don't.). It is very readable.

You don't have to know how ARIMA works to use these tools, but I think it is always easier if you have context, since there are "model parameters" to be set etc.

$\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.