US5615286A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for determining a most likely sequence of states
Assignee: Nytell Software LLC
•
Filing: 1995-05-05
•
Granted: 1997-03-25
•
Expires: 2015-05-05
Abstract
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.
Inventors
- 👤 Sarvar M. Patel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 22:56
CPC Classifications
G; G10; G10L; G10L15/00; G10L15/08; G06; G06V; G06V10/00; G06V10/70; G06V10/74; G06V10/75; G10L15/14; G10L15/142
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
166 words
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.
Claim 2
Independent Claim
166 words
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.
Claim 3
Dependent Claim
37 words
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.
Claim 4
Dependent Claim
77 words
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.
Claim 5
Dependent Claim
42 words
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.
Claim 6
Dependent Claim
27 words
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.
Claim 7
Independent Claim
169 words
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.
Claim 8
Independent Claim
169 words
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.
Claim 9
Dependent Claim
24 words
The method of claim 6, further comprising the step of multiplying the final maxvalue by an observation probability for state s at time t.
Claim 10
Dependent Claim
16 words
The method of claim 6, wherein steps d-h are repeated from each of the N states.
Claim 11
Dependent Claim
20 words
The method of claim 6, further including the step of choosing k to be an inteqer solution close to √N.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-03-24 | 2000-09-23 | 2001-03-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-03-24 | 2004-09-23 | 2005-03-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-03-24 | 2008-09-23 | 2009-03-25 | $7700.00 | Window Closed / Lapsed |