FPS 1.0 Manual

Table of Contents

Given a collection of (ideally sparsely correlated) time series, this software provides functions to make fast and accurate predictions of the future value of a particular time series by using the l1-regularized least squares model and cholesky decomposition and cholesky update. Interested users should carefully read the documentations and integrate our functions to their Matlab projects.

Problem statement

s1, ..., sn -- n time series that all start (at t0) and end (at t1) at the same time.
the series number i that will be predicted.
a data source that constantly provide the new values of s1, ..., sn at the next time step.
the size of a sliding window.
the factor mu in the optimization problem |Ax-b|_2^2+mu*|x|_1.

At every future time point t (t>=t1) where we know the values of series s1, ..., sn from t0 to t, return the predicted value of series i at time step t+1.

FPS operates with a reasonable number (between 10 and 100) of series and possibly a large number (>10000) of time steps, in an efficient and incremental fashion, so that as new points are appended to the timeseries, the value of series i at next time step can be predicted in real time.

Running the system

Install Matlab on your computer, and then download our software in the download page and unzip it into a directory of your choice.

Next set up Matlab PATH variable as described in the download page

Note that FPS is not an executable project. Instead FPS is a package that contains a function to train our l1-regularized least squares model, and a Matlab object that performs predictions on a particular time series given other time series and itself.

There are two Matlab programs that should be of interest to you. train_model.m is the function that suggests the user possibly good parameters to use in actual predictions., and IncrementalPredict.m is a Matlab object that makes future predictions on a particular time series.

We assume that the user already have some initial data for each series so that we can first run train_model.m on these data to obtain some parameters before we any actual prediction. We also assume that the user will constantly obtain new values for each series from some data source. Both the initial data and the incoming new data are likely to be part of a large system, so we expect that both of train_model.m and IncrementalPredict.m will be imbeded in that system. In fact there's no "main" method in this package. We only provide a Matlab class IncrementalPredict.m for doing prediction and a Matlab function train_model.m that output suggested parameters based on the training_data. We assume that interested user will imbed this class and this function into a larger Matlab project.

To get a feeling of how to use IncrementalPredict.m and train_model.m, see the file sample_run.m. The default parameters to run this program should be appropriate for a start.

This sample program will make predictions for a particular series in a given time interval. The program assumes that the input data is volatile; therefore, it revokes the train_model function every 100 time steps to get the most up-to-date parameters for actual predictions.

We suggest that interested users carefully read the documentations in sample_run.m, IncrementalPredict.m and train_model.m to understand how IncrementalPredict.m and train_model.m may be applied to their Matlab project.

WARNING: This demo program is going to take a long time (a few hours to about a day) to finish if the difference of start_time and end_time is large (say larger than 3000).

Send your feedback

If you have any question or feedback, please let us know. Email: shasha@cs.nyu.edu or jjx203@cs.nyu.edu.

Maintained by jjx203@cs.nyu.edu

Last Updated Dec 17th, 2009