System and Method of Using Multi Pattern Viterbi Algorithm for Joint Decoding of Multiple Patterns

• US 20110125701A1
• Filed: 01/05/2010
• Published: 05/26/2011
• Est. Priority Date: 11/20/2009
• Status: Active Grant

• Current Assignee: Indian Institute of Science
• Original Assignee: Indian Institute of Science
• Inventors: Sreenivas, Thippur Venkatanarasaiah, Nair, Nishanth Ulhas
• Granted Patent: US 8,630,971 B2
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06F 18/256 of results relating to different input data, e.g. multimodal recognition
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G10L 15/02 Feature extraction for speech recognition; Selection of recognition unit
• CPC Class Codes: G10L 15/14 using statistical models, e.g. Hidden Markov Models [HMMs] G10L15/18 takes precedence
• CPC Class Codes: G10L 15/144 Training of HMMs
• CPC Class Codes: G10L 15/20 Speech recognition techniques specially adapted for robustness in adverse environments, e.g. in noise, of stress induced speech G10L21/02 takes precedence
• CPC Class Codes: G10L 2015/081 Search algorithms, e.g. Baum-Welch or Viterbi

Abstract

Systems, devices, and methods for using Multi-Pattern Viterbi Algorithm for joint decoding of multiple patterns are disclosed. An exemplary method may receive a plurality of sets of time-sequential signal observations for each of a number K of signal repetitions. Further, each set of signal observations is associated with a respective dimension of a K-dimensional time grid having time-indexed points. Moreover, at each of a plurality of the time-indexed points, a state cost metric is calculated with a processor for each state in a set of states of a hidden Markov model (HMM). In addition, each state in the set of states and for a given time-indexed point, the state cost metric calculation provides a most-likely predecessor state and a corresponding most-likely predecessor time-indexed point. The exemplary method may also determine a sequence of states using the calculated state cost metrics and determine a corresponding cumulative probability measure for the HMM.

Claims

13. An article of manufacture including a computer-readable medium having instructions stored thereon that, if executed by a computing device, cause the computing device to perform operations comprising:

retrieving from memory a number K sets of time-sequential signal observations for each of a number K of signal repetitions, wherein each set of signal observations is associated with a respective dimension of a K-dimensional time grid having time-indexed points;

retrieving from memory a set of parameters for each of a plurality of hidden Markov models (HMM);

calculating a state cost metric for each state in a set of states of a given HMM at each of a plurality of the time-indexed points, wherein for each state in the set of states and for a given time-indexed point, the state cost metric calculation provides a most-likely predecessor state and a corresponding most-likely predecessor time-indexed point;

determining a cumulative probability measure for each of the plurality of HMMs; and

,

determining a most likely HMM from the plurality of HMMs.

14. An apparatus comprising:

a processor executing software applications stored in memory, the software instructions that include;

calculating a state cost metric for each state in a set of states of a given HMM at each of a plurality of the time-indexed points, wherein for each state in the set of states and for a given time-indexed point, the state cost metric calculation provides a most-likely predecessor state and a corresponding most-likely predecessor time-indexed point,

determining a sequence of states using the calculated state cost metrics and determining a corresponding cumulative probability measure for each of the plurality of HMMs, and

determining a most likely HMM from the plurality of HMMs.

1. A method comprising:

receiving a plurality of sets of time-sequential signal observations for each of a number K of signal repetitions, wherein each set of signal observations is associated with a respective dimension of a K-dimensional time grid having time-indexed points;

at each of a plurality of the time-indexed points, calculating with a processor a state cost metric for each state in a set of states of a hidden Markov model (HMM), wherein for each state in the set of states and for a given time-indexed point, the state cost metric calculation provides a most-likely predecessor state and a corresponding most-likely predecessor time-indexed point;

determining a sequence of states using the calculated state cost metrics and determining a corresponding cumulative probability measure for the HMM.

2. The method of claim 1 further comprising:

repeating calculating the state cost metric for each state in the set of states for the plurality of time-indexed points and determining a most likely sequence and corresponding cumulative probability measure for a plurality of HMMs; and

,

identifying a most likely HMM based on the corresponding cumulative probability measures for the plurality of HMMs.

3. The method of claim 1 wherein for a given one of the plurality of time-indexed points, the state cost metric for each state in the set of states is determined by:

calculating a cost metric associated with each possible prior state at each possible predecessor time-indexed point; and

,

selecting the lowest cost metric for each state.

4. The method of claim 3 wherein for a given possible predecessor state, the state cost metrics are based only on observations associated with dimensions that are incremented when moving from the given predecessor time-index point to the given one of the plurality of time-indexed points.

5. The method of claim 1 wherein determining a most likely sequence of states comprises identifying a lowest state cost metric at a final state at a terminal time-indexed point.

6. The method of claim 1 wherein the signal observations are signal feature vectors.

7. The method of claim 6 wherein the feature vectors are selected from the group consisting of Mel-Frequency Cepstral Coefficients feature vectors, Linear Predictive Coding Coefficients, spectral density, spectral energy, noise ratios, length of sounds, relative power, and filter matches

8. The method of claim 1 wherein the plurality of time-indexed points are determined with respect to a predetermined distance from a diagonal line through the K-dimensional space.

9. The method of claim 8 wherein each set of observations has a respective time duration, and the predetermined distance is based on differences in the respective time durations.

10. The method of claim 1 wherein determining the sequence of states using the calculated state cost metrics comprises backtracking through the time-indexed points based on the state cost metrics.

11. The method of claim 1 wherein calculating a given state cost metric for a given state is based on state cost metrics for all states associated with all candidate predecessor time-indexed points, the probability of transitioning from each state of each candidate predecessor time-indexed point to the given state, the respective probability of transitioning from the respective candidate predecessor time-indexed point, and the joint probability of the observations being emitted from the state in the set of states.

12. The method of claim 1 wherein the determined sequence of states determines an alignment of the sets of observations.

15. The apparatus of claim 14, further comprising a memory that stores:

a digital representation of a plurality of sets of time-sequential signal observations for each of a number K of signal repetitions, wherein each set of signal observations is associated with a respective dimension of a k-dimensional time grid having time-indexed points, and

a set of parameters for each of a plurality of hidden Markov models (HMM).

16. The apparatus of claim 14, further comprising an audio receiver that:

receives a plurality of sets time-sequential audio signal observations for each of a number K of signal repetitions, wherein each set of audio signal observations is associated with a respective dimension of a k-dimensional time grid having time-indexed points, and

converts the plurality of sets time-sequential audio signal observations for each of a number K of signal repetitions into a plurality of sets time-sequential analog electrical signal observations for each of a number K of signal repetitions.

17. The apparatus of claim 14, wherein the processor computes a plurality of sets of features vectors based on the digital representation of a plurality of sets of time-sequential signal observations for each of a number K of signal repetitions.

18. The apparatus of claim 14, wherein the processor transforms the sequence of states using the calculated state cost metrics into a digital representation of the sequence of states.

19. The apparatus of claim 14, further comprising a digital-to-analog converter that transforms the digital representation of the sequence of states into an output analog electrical signal.

20. The apparatus of claim 14, further comprising a system output interface that transforms the output analog electrical signal into an output audio signal.

16-1. The apparatus of claim 14, further comprising an analog-to-digital converter that transforms the plurality of sets time-sequential analog electrical signal observations for each of a number K of signal repetitions into the digital representation of a plurality of sets of time-sequential signal observations for each of a number K of signal repetitions.