×

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
First Claim
Patent Images

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.

View all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×