Detecting instabilities in time series forecasting

• US 7,617,010 B2
• Filed: 12/28/2005
• Issued: 11/10/2009
• Est. Priority Date: 12/28/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chickering, David M., Heckerman, David E., Bocharov, Alexei V.
• Primary Examiner(s): DeCady; Albert
• Assistant Examiner(s): Gami; Tejal
• Application Number:
  US11/319,894
• Publication Number:
  US 20070150077A1
• Time in Patent Office: 1,413 Days
• Field of Search: 700/29, 700/30, 703/2, 703/6
• US Class Current: 700/29
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases

Abstract

A predictive model analysis system comprises a receiver component that receives predictive samples created by way of forward sampling. An analysis component analyzes a plurality of the received predictive samples and automatically determines whether a predictive model is reliable at a time range associated with the plurality of predictive sample, wherein the determination is made based at least in part upon an estimated norm associated with a forward sampling operator.

Claims

1. A data monitoring system embodied on a computer readable storage medium that comprises the following computer-executable components:

a receiver component that receives a plurality of predictive samples from a predictive model created by way of forward sampling of one or more previously made predicted samples from the predictive model, the forward sampling creating the one or more previously made predicted samples by;

generating, by the predictive model, a first probability distribution to make a first prediction for a variable at a first instance in time in a future;

randomly drawing a sample from the probability distribution that is treated as an observed value for the variable at the first instance in time;

using the observed value to create a second probability distribution for the variable at a second instance in time in the future; and

continuing the generating, the randomly drawing, and the using the observed value until a subsequent probability distribution is obtained for the variable at a predetermined instance in time in the future; and

an analysis component that analyzes a plurality of the received predictive samples and automatically determines whether the predictive model is reliable at a time range associated with the plurality of received predictive samples, the determination is based at least in part upon a rate of change of divergence of a forward sampling operator (FS) associated with the predictive model based upon the plurality of received predictive samples, the determination further analyzing the rate of change of divergence with respect to a threshold, wherein the analysis component;

determines that the predictive model is outputting reliable predictions at a certain instance of time in the future and allowing the predictive model to continue outputting predictions when the rate of change of divergence is below the threshold;

determines that the predictive model is not outputting reliable predictions at a certain instance of time in the future and halts the predictive model from outputting predictions subsequent to that certain instance of time when the rate of change of divergence is above the threshold; and

determines that the predictive model is outputting reliable predictions at a first instance of time in the future and allowing the predictive model to continue outputting predictions when the rate of change of divergence is above the threshold at the first instance of time and when the rate of change of divergence is below the threshold at a certain consecutive number of instances of time subsequent to the first instance of time.

2. The system of claim 1, wherein the analysis component comprises a measuring component that determines the forward sampling operator (FS).

3. The system of claim 2, wherein the analysis component further comprises a derivative component that creates a derivative of FS, (FS′

).

4. The system of claim 3, wherein the analysis component derives an estimated norm in closed form.

5. The system of claim 4, wherein the analysis component further comprises an estimation component that estimates the rate of change of divergence by determining an expectation of |FS′

|, where

$E<br><br>\left(<br><br>{\mathrm{FS}}^{\mathrm{\prime <br><br>}}<br><br>\right)=\frac{\sum <br><br>{<br><br>{\mathrm{FS}}^{\mathrm{\prime <br><br>}}<br><br>}_s}{N},$

where E(|FS′

|) is an expectation of |FS′

| and N is a number of the received predictive samples.

6. The system of claim 5, wherein the estimation component creates a sequence of norm estimates through creation of a vector of norm estimates, {right arrow over (v)}[j], where {right arrow over (v)}[j]=E(|FS(j)′

|), 1≦

j<

k, where j relates to a time associated with a prediction and k is a constant.

7. The system of claim 6, further comprising an evaluation component that determines whether one or more entries in the vector of norm estimates are less than a predefined norm estimate threshold.

8. The system of claim 7, wherein the evaluation component determines that an entry in the vector of norm estimates is greater than the norm estimate threshold and monitors entries following the entry that is greater than the norm estimate threshold to ensure that a pre-defined threshold number of entries subsequent the entry are below the pre-defined norm estimate threshold, wherein the evaluation component allows the model to continue making subsequent predictions if the number of acceptable vector entries subsequent the entry are below the predefined threshold number of entries, and wherein the evaluation component deems a forward sampling prediction unstable and halts the model from making subsequent predictions if the number of acceptable vector entries subsequent the entry are below the predefined threshold number of entries.

9. The system of claim 1, further comprising a selection component that selects a number of predictive samples to be provided to the analysis component based upon inference of the current state of the system in order to meet speed requirements for the predictive model.

10. The system of claim 1, wherein the predictive model is an autoregressive predictive model.

11. The system of claim 1, further comprising a selection component that selects a number of predictive samples to be provided to the analysis component.

12. The system of claim 11, further comprising a calculator component that generates a joint distribution estimate with respect to time-series data at a future point in time, the predictive model comprises the calculator component.

13. The system of claim 1, further comprising a data store that includes time-series data, the predictive model accesses the time-series data and utilizes forward sampling to create the predictive samples.

14. The system of claim 1, wherein a server comprises the receiver component and the analysis component.

15. The system of claim 1, wherein a client comprises the receiver component and the analysis component.

16. A computer-implemented method for determining operability of a predictive model with respect to predicted values of variables at future instances in time, comprising the following computer-executable acts:

receiving predictive values for a variable from a predictive model that are determined based upon forward sampling, wherein forward sampling comprises employing at least one previously predicted value from the predictive model as an observed value in predicting one or more additional values for the variable, the forward sampling creating the at least one previously predicted value by;

generating, by the predictive model, a first probability distribution to make a first prediction for the variable at a first instance in time in a future;

randomly drawing a sample from the probability distribution that is treated as the observed value for the variable at the first instance in time;

using the observed value to create a second probability distribution for the variable at a second instance in time in the future; and

continuing the generating, the randomly drawing, and the using the observed value until a subsequent probability distribution is obtained for the variable at a predetermined instance in time in the future; and

automatically determining a distance in time in the future that the predictive model will reliably predict values for the variable based at least in part upon an estimated rate of change of divergence of the received predictive values the automatically determining further comprising;

determining that the predictive model is outputting reliable predictions at a certain instance of time in the future and allowing the predictive model to continue outputting predictions when the rate of change of divergence is below the threshold;

determining that the predictive model is not outputting reliable predictions at a certain instance of time in the future and halts the predictive model from outputting predictions subsequent to that certain instance of time when the rate of change of divergence is above the threshold; and

determining that the predictive model is outputting reliable predictions at a first instance of time in the future and allowing the predictive model to continue outputting predictions when the rate of change of divergence is above the threshold at the first instance of time and when the rate of chance of divergence is below the threshold at a certain consecutive number of instances of time subsequent to the first instance of time.

17. The method of claim 16, further comprising measuring a norm of a forward sampling operator that relates to a subset of the received predictive values, the automatic determination of the distance in time in the future is based at least in part upon the measured norm.

18. The method of claim 17, further comprising estimating a rate of change of divergence based at least in part upon the measured norm.

19. The method of claim 16, further comprising preventing the predictive model from making predictions when the rate of change of divergence is above a predefined threshold.

20. A system embodied on a computer readable storage medium that facilitates monitoring of a predictive model, comprising:

computer-implemented means for receiving predicted values for at least one variable, the received predicted values obtained by way of forward sampling, wherein forward sampling comprises employing at least one previously predicted value from the predictive model as an observed value in determining one or more future predicted values for the at least one variable, the forward sampling creating the at least one previously predicted value by;

generating, by the predictive model, a first probability distribution to make a first prediction for the at least one variable at a first instance in time in a future;

randomly drawing a sample from the probability distribution that is treated as the observed value for the at least one variable at the first instance in time;

using the observed value to create a second probability distribution for the at least one variable at a second instance in time in the future; and

continuing the generating, the randomly drawing, and the using the observed value until a subsequent probability distribution is obtained for the at least one variable at a predetermined instance in time in the future;

computer-implemented means for estimating a rate of change of divergence of a forward sampling operator (FS) associated with the predictive model based at least in part upon the received predicted values, wherein the rate of change of divergence is determined by an expectation of |FS′

|, where E(|FS′

|)=Σ

|FS′

|_s/N, where E(|FS′

|) is an expectation of |FS′

| and N is a number of the received predicted samples; and

computer-implemented means for determining a received predicted value from the predictive model that is not accurate based at least in part upon the estimated rate of change of divergence exceeding a predefined threshold, the computer-implemented means for determining further comprising;

determining that the predictive model is outputting reliable predictions at a certain instance of time in the future and allowing the predictive model to continue outputting predictions when the estimated rate of change of divergence is below the predefined threshold;

determining that the predictive model is not outputting reliable predictions at a certain instance of time in the future and halts the predictive model from outputting predictions subsequent to that certain instance of time when the estimated rate of change of divergence is above the predefined threshold; and

determining that the predictive model is outputting reliable predictions at a first instance of time in the future and allowing the predictive model to continue outputting predictions when the estimated rate of change of divergence is above the predefined threshold at the first instance of time and when the estimated rate of change of divergence is below the predefined threshold at a certain consecutive number of instances of time subsequent to the first instance of time.