System and method for signal prediction

• US 7,899,761 B2
• Filed: 04/25/2005
• Issued: 03/01/2011
• 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
• Primary Examiner(s): Dorvil; Richemond
• Assistant Examiner(s): BORSETTI, GREG
• Application Number:
  US11/113,962
• Publication Number:
  US 20060241927A1
• Time in Patent Office: 2,136 Days
• Field of Search: 704/256, 704/256.1, 704/E11.197, 706/20, 706/12, 706/14, 714/E11.014
• US Class Current: 706/12
• 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 system for identifying trends of fault occurrences in a manufacturing process, the system including computer-readable medium tangibly embodying computer-executable instructions for:

receiving a plurality of data series and input parameters, the input parameters comprising a time step parameter, said data series including discrete data elements that identify the fault occurrences in the manufacturing process;

preprocessing the plurality of data series according to the input parameters, to form binned and classified data series, where the discrete data elements in each of the data series are classified into a particular bin depending on when they occurred per the time parameter, wherein preprocessing the plurality of data series includes clustering the classified data series to iteratively arrange the data elements into clusters to provide a predetermined criteria, and wherein preprocessing the plurality of data series includes classifying the data elements that identify the fault occurrences according to frequency of occurrence, mean time to repair and/or duration of downtime and selecting the most frequently occurring fault occurrences and/or the fault occurrences resulting in the longest downtime duration;

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

initializing a model for trend prediction including determining the number of known states in the model based on the data series and associating a state of the model for each class of data determined by the binned and classified data series;

training the model for trend prediction of the binned and classified data series to form a trained model, said model being trained to predict trends of the data series by determining the probability of states of the data as classified and binned and the probability of transition of the data from state to state where the state probabilities are calculated for the data series by evaluating a probability in a training window, wherein training the model includes training the model to predict the frequency of occurrence, the mean time to repair and/or the downtime duration of the fault occurrences, using the model to predict frequency and/or duration of the fault occurrences during a testing period that immediately succeeds a training period of the model to identify trend predictions of the fault occurrences, and evaluating the accuracy of the trend predictions by comparing the trend predictions during the testing period with actual data obtained during the testing period; and

deploying the trained model for trend prediction in the manufacturing process, the deploying comprising;

outputting trend predictions that identify predictions of fault occurrences that may occur during the manufacturing process; and

updating training of the model when new data is obtained during the manufacturing process.

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

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

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

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

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

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

5. The method of claim 3, 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.

6. The method of claim 1, wherein training the model for trend prediction comprises:

supplying a metric for determining goodness of the model;

applying the metric to the model; and

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

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

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

generating predicted paths with the 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 model;

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

8. The method according to claim 1 wherein the model is a Markov model.

9. A system for identifying trends of fault occurrences in a manufacturing process with a Markov model, the system comprising:

a plurality of modules wherein each module includes non-transitory computer-readable medium with an executable program stored thereon, the plurality of modules including;

an input module configured to receive a plurality of data series and input parameters;

a sort module configured to sort the plurality of data series to form a sorted plurality of data series, said data series including discrete data elements that identify the fault occurrences in the manufacturing process;

a selection module configured to select data series from the sorted plurality of data series to form selected data series;

a class development module configured to develop a plurality of classes from the selected data series and input parameters; and

a binning and classification module configured to bin and classify the selected data series according to an input parameter and the plurality of classes, where the discrete data elements in each of the data series are classified into a particular bin depending on when they occurred, wherein the binning and classification module clusters the classified data series to iteratively arrange the data elements into clusters to meet a predetermined criteria, and wherein classifying the selected data series includes identifying the fault occurrences according to frequency of occurrence, mean time to repair and/or duration of downtime and selecting the most frequently occurring fault occurrences and/or the fault occurrences resulting in the longest downtime duration;

a Markov model initialization module configured to initialize the Markov model for trend prediction including determining the number of known states in the Markov model based on the data series and associating a state of the Markov model for each class of data determined by the binned and classified data series;

a Markov model training module configured to train the Markov model for trend prediction of the binned and classified data series to form a trained Markov model, said Markov model being trained to predict trends of the data series by determining the probability of states of the data as classified and binned and the probability of the transition of data from state to state where the state probabilities are calculated for the data series by evaluating a probability in a training window, wherein training the Markov model includes training the model to predict the frequency of occurrence, the mean time to repair and/or the downtime duration of the fault occurrences, using the model to predict frequency and/or duration of the fault occurrences during a testing period immediately succeeding a training period of the model, and evaluating the accuracy of the trend predictions by comparing the trend predictions during the testing period with actual data obtained during the testing period;

an output module configured to output trend predictions upon deployment of the trained Markov model that identify predictions of fault occurrences that may occur during the manufacturing process; and

updating the training of the model when new data is obtained during the manufacturing process.

10. The system of claim 9, wherein the sorting module is configured 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 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 system for identifying trends of fault occurrences in a manufacturing process, the system including computer-readable medium tangibly embodying computer-executable instructions for:

receiving a data series and input parameters, said data series including discrete data elements that identify the fault occurrences in the manufacturing process;

classifying the discrete data elements in each of the data series into a predetermined bin depending on when they occurred, wherein classifying the discrete data elements of data series includes clustering the classified data series to iteratively arrange the data elements into clusters to meet a predetermined criteria, and wherein classifying the discrete data elements includes classifying the fault occurrences according to frequency of occurrence, mean time to repair and/or duration of downtime and selecting the most frequently occurring fault occurrences and/or the fault occurrences resulting in the longest downtime duration;

developing an architecture for a Markov model from the data series and the input parameters including determining the number of known states in the Markov model based on the data series and associating a state of the Markov model for each class of data determined by the binned and classified data series, wherein developing an architecture for a Markov model includes training the model to predict the frequency of occurrence, the mean time to repair and/or the downtime duration of the fault occurrences, using the model to predict frequency and/or duration of the fault occurrences during a testing period immediately succeeding a training period of the model, and evaluating the accuracy of the trend predictions by comparing the trend predictions during the testing period with actual data obtained during the testing period;

disposing a Markov model having the architecture for trend prediction, said Markov model being trained to predict trends of the data series by determining the probability of states of the data as classified and binned and the probability of the transition of data from state to state where the state probabilities are calculated for the data series by evaluating a probability in a training window that identify predictions of fault occurrences that may occur during the manufacturing process; and

updating the training of the model when new data is obtained during the manufacturing process.

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