Method for uncovering hidden Markov models

• US 7,912,717 B1
• Filed: 11/18/2005
• Issued: 03/22/2011
• Est. Priority Date: 11/18/2004
• Status: Active Grant

• Current Assignee: Albert Galick
• Original Assignee: Albert Galick
• Inventors: Galick, Albert
• Primary Examiner(s): Wozniak; James S
• Assistant Examiner(s): GUERRA-ERAZO, EDGAR X
• Application Number:
  US11/282,410
• Time in Patent Office: 1,950 Days
• Field of Search: 704/256, 704/254, 704/255, 704/240, 704/251, 704/256.1, 704/256.3, 704/256.5, 704/256.6, 706/20, 706/21
• US Class Current: 704/256
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models

Abstract

The invention uses the ModelGrower program to generate possible candidates from an original or aggregated model. An isomorphic reduction program operates on the candidates to identify and exclude isomorphic models. A Markov model evaluation and optimization program operates on the remaining non-isomorphic candidates. The candidates are optimized and the ones that most closely conform to the data are kept. The best optimized candidate of one stage becomes the starting candidate for the next stage where ModelGrower and the other programs operate on the optimized candidate to generate a new optimized candidate. The invention repeats the steps of growing, excluding isomorphs, evaluating and optimizing until such repetitions yield no significantly better results.

Claims

1. A method for operating a computer to decode a set of data representative of a state machine to estimate the most likely hidden states and transitions, including rates, between said hidden states of the state machine, comprising the steps of:

storing data representative of observations of the state machine including one or more observed states, transitions between observed states, and continuous state dwell times between observed state transitions;

assigning a different code to each observed state, said code representative of a unique characteristic of its observed state that distinguishes it from all other observed states;

identifying an initial, observed graph, having a set of observed states, each occurring uniquely, multiple occurrences being indistinguishable, and having a set of observed transitions between observed states, each likewise occurring uniquely, and including only observed exits and entries among observed states;

generating from the previous graph a set of derived graphs with one additional bidirectional transition in each and every possible instance, namely;

generating first derived graphs by converting an existing state in the previous graph into a connected pair of new states, wherein both new states have the code of the existing state, and reallocating in any possible way the existing transition(s) of the existing state among the pair of new states;

generating second derived graphs by converting an existing state in the previous graph into a connected pair of new states, wherein one new state has the code of the existing state and the other new state has a different code of another different observed state, and reallocating in any possible way the existing transition(s) of the existing state among the pair of new states; and

generating third derived graphs by adding a new bidirectional transition in any possible way between existing states of the previous graph where there was no transition;

removing isomorphic graphs from said set of derived graphs;

using the computer to optimize the rates of all transitions of each remaining derived graph to maximize the likelihood that each of the resulting derived graphs generated the stored data; and

inspecting the likelihood of said resulting derived graphs to identify the one(s) whose underlying derived graph most likely corresponds to the stored data, wherein each resulting derived graph includes at least one hidden state transition.

2. The method of claim 1 wherein the step of identifying an initial, observed graph, consists only of the set of observed states, each occurring uniquely, multiple occurrences being indistinguishable, and consisting of the set of observed transitions between the observed states, each likewise occurring uniquely, and including only observed exits and entries among the observed states.

3. The method of claim 2 wherein the codes are colors.

4. The method of claim 1 further comprising

repeating the steps of claim 8 to find the best graph(s) until the margin of likelihood above the next most likely graph(s) indicates diminishing returns, the comparison of graphs always being done among graphs with the same number of transitions or degrees of freedom, in order to find the simplest possible graph(s) maximizing the likelihood of the observed data, whereby the method generates the best justified estimate of hidden states and transitions of the state machine.

5. The method of claim 4 further identifying a hidden Markov model from a set of observations, to be compared with another hidden Markov model so identified from a different set of observations.

6. A method for operating a computer to decode a set of data representative of a state machine to estimate the most likely hidden states and transitions including rates, between said hidden states for the state machine, comprising the steps of:

storing data representative of the state machine over time including one or more states and transitions between states;

assigning a different code to each state, said code representative of a unique characteristic of its state that distinguishes it from all other states;

identifying an initial graph representative of the state machine, including only those states and transitions justified by experimental evidence; and

generating from the previous graph a set of derived graphs wherein each derived graph emerges from one of a set of operations on the previous graph, said operations performed one way at a time and in all possible ways on only one state or one transition so that each operation results in a derived graph with only one change in the total number of transitions or degrees of freedom relative to the previous graph and the set of derived graphs include each and every possible instance of such single changes;

removing isomorphic graphs from said set of derived graphs;

using the computer to optimize the rates of all transitions of each remaining derived graph to maximize the likelihood that each of the resulting derived graphs generated the stored data; and

inspecting the likelihood of said resulting derived graphs to identify the one(s) whose underlying derived graph most likely corresponds to the stored data wherein each resulting derived graph includes at least one hidden state transition.

7. The method of claim 6 wherein one of the possible instances of such changes includes operating on the previous graph to generate derived graphs one way at a time and in all possible ways by converting one of each existing state in the previous graph into a bidirectionally connected pair of new states, whereinboth new states have the code of the existing state, andthe existing transition(s) of the existing state have been reallocated one way at a time and in all possible ways among the pair of new states.

8. The method of claim 6 wherein one of the possible instances of such changes includes operating on the previous graph to generate derived graphs one way at a time and in all possible ways by converting one of each existing state in the previous graph into a bidirectionally connected pair of new states, whereinone new state has the code of the existing state and the other new state has a different code of another different observed state, andthe existing transition(s) of the existing state have been reallocated one way at a time and in all possible ways among the pair of new states.

9. The method of claim 6 wherein one of the possible instances of such changes includes operating on the previous graph to generate derived graphs one at a time and in all possible ways by adding a single new bidirectional transition between existing states of the previous graph where there was no transition.

10. The method of claim 6 wherein the step of identifying an initial, observed graph, consists only of the set of observed states, each occurring uniquely, multiple occurrences being indistinguishable, and consisting of the set of observed transitions between the observed states, each likewise occurring uniquely, and including only observed exits and entries among the observed states.

11. The method of claim 10 wherein the codes are colors.

12. The method of claim 6 further comprising

repeating the steps of claim 6 to find the best graph(s) until the margin of likelihood above the next most likely graph(s) indicates diminishing returns, the comparison of graphs always being done among graphs with the same number of transitions or degrees of freedom, in order to find the simplest possible graph(s) maximizing the likelihood of the observed data, whereby the method generates the best justified estimate of hidden states and transitions of the state machine.

13. The method of claim 12 further identifying a hidden Markov model from a set of observations, to be compared with another hidden Markov model so identified from a different set of observations.