Method for determining a most likely sequence of states

• US 5,615,286 A
• Filed: 05/05/1995
• Issued: 03/25/1997
• Est. Priority Date: 05/05/1995
• Status: Expired due to Term

• Current Assignee: TTI Inventions A LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Patel, Sarvar M.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Tadayon, Bijan
• Application Number:
  US08/436,059
• Time in Patent Office: 690 Days
• Field of Search: 382/155, 382/156, 382/157, 382/158, 382/159, 382/160, 382/190, 382/209, 382/217, 382/218, 382/224, 382/226, 382/227, 382/228, 382/229, 382/230, 382/231, 382/181, 382/182 , 382/185, 382/186, 382/187, 382/195, 382/198, 382/202, 382/203, 382/219, 382/220, 382/221, 382/225, 382/310, 381/43, 381/41, 395/22, 395/2, 395/2.41, 395/2.65, 395/23, 395/2.53, 395/2.54, 395/2.49
• US Class Current: 382/224
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
• CPC Class Codes: G10L 15/08 Speech classification or search
• CPC Class Codes: G10L 15/142 Hidden Markov Models [HMMs]

Abstract

The number of calculations to determine the most likely path is reduced by eliminating a number of paths that are impossible to provide an optimal result. How to eliminate these non-optimal paths, thus greatly reducing the number of calculations performed by a signal processor. The determination of the probability score of the best path to state s at time t may be found as follows. First, transition probabilities to state s are sorted in order of descending probability. Second, the k highest probability scores at time t-1 are identified. Third, the highest transition probability associated with the k highest probability scores at t-1 is identified and designated maxrank. Fourth, the k highest probability scores at t-1 are multiplied with their associated transition probabilities with the highest product being designated maxvalue. Fifth, all transition probabilities higher than maxrank are multiplied with their associated probability scores at t-1. If the product of one of these multiplications is greater than the current maxvalue, this product becomes the new maxvalue. The final maxvalue is multiplied by an observation probability to determine a most likely path sequence to state s at time-1. K is chosen to be √N, where N is the total number of possible states.

Claims

1. A method for determining the most likely state sequence ending in a state s at a time t corresponding to a sequence of observations from an initial time interval to time t, comprising the steps of:

a. receiving the sequence of observations;

b. comparing the observations to known parameters for N number of states;

c. determining a best state sequence for each of the N number of states at time t-1 based on this comparison;

d. identifying a first number of the best state sequences at t-1, the first number being less than N, one of which sequences will provide an optimal state sequence to s at time t;

e. processing only the first number of the best state sequences; and

f. selecting an optimal state sequence from the processed best state sequences; and

wherein the step of determining comprises determining the best state sequences by iteratively calculating the most likely state sequences for each of the N states from the initial time to time t-1.

2. The method of claim 1, wherein the step of comparing further comprises comparing each observation to an observation probability function for each of the N states to determine an observation probability for each state for each observation.

3. The method of claim 1, wherein the step of identifying comprises the steps of:

a. sorting transition probabilities to state s in order of descending probability;

b. selecting k highest probability state sequences from the best state sequences of the N states at time t-1;

c. designating as maxrank the highest rank of the transition probabilities associated with the k highest probability best state sequences at time t-1; and

d. identifying all transition probabilities higher than maxrank.

4. The method of claim 3, wherein the step of processing comprises:

a. multiplying the k highest probability state sequences at t-1 with their associated transition probabilities; and

b. multiplying all transition probabilities higher than maxrank with their associated state sequences at t-1.

5. The method of claim 4, wherein the step of selecting comprises selecting a final state sequence associated with a highest product after all multiplications have been performed.

6. A method for determining a most likely state sequence at a time t for a state s in a system having N possible states, comprising the steps of:

a. receiving a number of observations from an initial time to time t;

b. sorting a plurality of transition probabilities to state s associated with the N states in order of descending probability;

c. identifying k highest state probability scores among the N states at a time t - 1;

d. designating as maxrank a highest transition probability associated with the k highest state probability scores at time t-1;

e. multiplying the k highest state probability scores at time t-1 with their associated transition probabilities;

f. designating as a current maxvalue a highest product of this multiplication;

g. multiplying all transition probabilities higher than maxrank with their associated state probability scores;

h. replacing the current maxvalue with a new maxvalue if a product of one of the multiplications of a transition probability higher than maxrank is greater than the current maxvalue.

7. The method of claim 6, further comprising the step of multiplying the final maxvalue by an observation probability for state s at time t.

8. The method of claim 6, wherein steps d-h are repeated from each of the N states.

9. The method of claim 6, further including the step of choosing k to be an inteqer solution close to √

N.