System and method for signal prediction

• US 20060241927A1
• Filed: 04/25/2005
• Published: 10/26/2006
• Est. Priority Date: 04/25/2005
• Status: Active Grant

• Current Assignee: GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: GM Global Technology Operations LLC (General Motors Company)
• Inventors: Barajas, Leandro G., Cho, Youngkwan, Bandyopadhyay, Pulak, Kadambe, Shubha
• Granted Patent: US 7,899,761 B2
• Time in Patent Office: Days
• US Class Current: 703/20
• CPC Class Codes: G05B 23/0232 based on qualitative trend analysis, e.g. system evolution
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models

Abstract

Disclosed herein are a system and method for trend prediction of signals in a time series using a Markov model. The method includes receiving a plurality of data series and input parameters, where the input parameters include a time step parameter, preprocessing the plurality of data series according to the input parameters, to form binned and classified data series, and processing the binned and classified data series. The processing includes initializing a Markov model for trend prediction, and training the Markov model for trend prediction of the binned and classified data series to form a trained Markov model. The method further includes deploying the trained Markov model for trend prediction, including outputting trend predictions. The method develops an architecture for the Markov model from the data series and the input parameters, and disposes the Markov model, having the architecture, for trend prediction.

Claims

1. A method for trend prediction, the method comprising:

receiving a plurality of data series and input parameters, the input parameters comprising a time step parameter;

preprocessing the plurality of data series according to the input parameters, to form binned and classified data series;

processing the binned and classified data series, the processing comprising;

initializing a Markov model for trend prediction; and

training the Markov model for trend prediction of the binned and classified data series to form a trained Markov model; and

deploying the trained Markov model for trend prediction, the deploying comprising;

outputting trend predictions.

2. The method of claim 1, wherein preprocessing comprises:

sorting the plurality of data series to form a sorted plurality of data series.

3. The method of claim 2, wherein preprocessing further comprises:

selecting data series from the sorted plurality of data series to form selected data series.

4. The method of claim 3, wherein preprocessing further comprises:

developing a plurality of classes from the selected data series and input parameters.

5. The method of claim 4, wherein preprocessing comprises:

binning and classifying the selected data series according to the time step parameter and the plurality of classes.

6. The method of claim 4, wherein developing a plurality of classes comprises:

adopting a priori class definitions;

initially classifying data of the data series according to the a priori class definitions, to form classified data; and

applying an agglomerative clustering process to the classified data, to obtain the plurality of classes.

7. The method of claim 1, wherein the Markov model comprises state probabilities and transition probabilities, and wherein training the Markov model for trend prediction comprises:

supplying a metric for determining goodness of the Markov model;

applying the metric to the Markov model; and

adjusting the state probabilities and transition probabilities of the Markov model to obtain substantially optimal performance of the Markov model according to the metric.

8. The method of claim 7, wherein supplying a metric for determining goodness of the Markov model comprises:

from the data series, choosing a set of performance paths;

generating predicted paths with the Markov model;

sorting the predicted paths according to likelihood, to obtain a sorted set of predicted paths; and

summing the ranks of the performance paths in the sorted list of predicted paths, to obtain the total predicted performance path rank for the Markov model;

wherein the metric for determining the goodness of the Markov model is the value of the total predicted performance path rank.

9. A system for trend prediction with a Markov model, the system comprising:

an input module for receiving a plurality of data series and input parameters;

a sort module for sorting the plurality of data series to form a sorted plurality of data series;

a selection module for selecting data series from the sorted plurality of data series to form selected data series;

a class development module for developing a plurality of classes from the selected data series and input parameters; and

a binning and classification module for binning and classifying the selected data series according to an input parameter and the plurality of classes;

a Markov model initialization module for initializing the Markov model for trend prediction;

a Markov model training module for training the Markov model for trend prediction of the binned and classified data series to form a trained Markov model; and

an output module for outputting trend predictions upon deployment of the trained Markov model.

10. The system of claim 9, wherein the sorting module is adapted to sort the plurality of data series according to at least one signal characteristic.

11. The system of claim 9, wherein a state of the Markov model corresponds to a class of the plurality of classes.

12. The system of claim 9, wherein:

the Markov model comprises state probabilities and transition probabilities;

the training module applies a metric to the Markov model for determining goodness of the Markov model; and

training the Markov model for trend prediction comprises adjusting the state probabilities and transition probabilities to obtain substantially optimal performance of the Markov model according to the metric.

13. The system of claim 12, wherein adjusting the state probabilities and transition probabilities comprises:

choosing a plurality of state probabilities and transition probabilities according to a search algorithm;

evaluating a value of the metric for each of the plurality of state probabilities and transition probabilities; and

selecting state probabilities and transition probabilities from the plurality of state probabilities and transition probabilities that provide an optimal value of the metric, among the evaluated values.

14. A method for trend prediction, comprising:

receiving a data series and input parameters;

developing an architecture for a Markov model from the data series and the input parameters; and

disposing a Markov model having the architecture for trend prediction.

15. The method of claim 14, wherein the input parameters comprise a time step parameter, and wherein developing an architecture for a Markov model from the data series and the time step parameter comprises:

partitioning the data series according to the time step parameter to form time partitioned data;

developing a plurality of classes from the time partitioned data and the input parameters; and

associating a state of the Markov model with a class of the plurality of classes.

16. The method of claim 15, wherein developing a plurality of classes comprises:

adopting a priori class definitions;

initially classifying the time partitioned data according to the a priori class definitions, to form classified data; and

applying an agglomerative clustering process to the classified data, to obtain the plurality of classes.

17. The method of claim 15, wherein the time partitioned data comprise binned data, the method further comprising:

classifying the time partitioned data according to the plurality of classes, to form binned and classified data.

18. The method of claim 17, wherein disposing a Markov model having the architecture, for trend prediction, comprises:

initializing the Markov model, comprising;

determining initial state probabilities by applying a counting method to the binned and classified data; and

determining initial transition probabilities by applying a counting method to the binned and classified data;

training the Markov model; and

deploying the Markov model.

19. The method of claim 18, wherein the Markov model comprises state probabilities and transition probabilities, and wherein training the Markov model for trend prediction comprises:

supplying a metric for determining goodness of the Markov model;

applying the metric to the Markov model; and

adjusting the state probabilities and transition probabilities of the Markov model to obtain substantially optimal performance of the Markov model according to the metric.

20. The method of claim 19, wherein supplying a metric for determining goodness of the Markov model comprises:

from the binned and classified data, choosing a set of performance paths;

generating predicted paths with the Markov model;

sorting the predicted paths according to likelihood, to obtain a sorted set of predicted paths; and

summing the ranks of the performance paths in the sorted list of predicted paths, to obtain the total predicted performance path rank for the Markov model;

wherein the metric for determining the goodness of the Markov model is the value of the total predicted performance path rank.