System and method of word graph matrix decomposition

• US 7,603,272 B1
• Filed: 06/19/2007
• Issued: 10/13/2009
• Est. Priority Date: 04/02/2003
• Status: Expired due to Term

• Current Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Riccardi, Giuseppe, Hakkani-Tur, Dilek Z.
• Primary Examiner(s): ABEBE, DANIEL DEMELASH
• Application Number:
  US11/765,008
• Time in Patent Office: 847 Days
• Field of Search: 704/232, 704/243, 704/244, 704/256
• US Class Current: 704/232
• CPC Class Codes: G10L 15/083 Recognition networks G10L15/142, G10L15/16 take precedence

Abstract

Disclosed is a system and method of decomposing a lattice transition matrix into a block diagonal matrix. The method is applicable to automatic speech recognition but can be used in other contexts as well, such as parsing, named entity extraction and any other methods. The method normalizes the topology of any input graph according to a canonical form.

Claims

1. A system for generating a block diagonal matrix from a lattice, the system comprising:

(1) a processor;

(2) a module configured to control the processor to compute posterior probability of all transitions T in a graph, if a lattice having transitions T is weighted;

(3) a module configured to control the processor to extract a pivot baseline path from the lattice; and

(4) a module configured to control the processor to align the transitions T in the lattice with the transitions in the pivot baseline path.

2. The system of claim 1, wherein the graph is a word graph.

3. The system of claim 2, wherein the module configured to control the processor to align the transitions T further, for all transitions T in the topological ordered lattice, further performs the following:

A. using time slots of transitions T, finding the most overlapping location on the pivot baseline;

B. if there is no transition at that location that precedes T in the lattice, performing the following;

i. if a transition with the same label already occurs at that location, adding posterior probability of T to the posterior probability of that transition;

ii. if a transition with the same label does not already occur at that location, inserting a new transition to that location with the label and posterior probability of T;

C. if there is a transition at that location that precedes T in the lattice, performing the following;

i. inserting a new state S_n to the pivot alignment;

ii. assigning that state a time information;

iii. changing the destination state of all transitions originating from state S_s to S_n; and

iv. inserting a transition between states S_n and S_e and assigning it the label and posterior of T, wherein the lattice is transformed into a block diagonal matrix.

4. The system of claim 3, wherein the module configured to control the processor to compute posterior probabilities of all transitions T in a word graph further performs a forward and a backward pass through the word graph.

5. The system of claim 3, wherein if the lattice is not weighted, the system skips the step of computing posterior probabilities of all transitions.

6. The system of claim 3, wherein the module configured to control the processor to extract the pivot baseline further extracts the best path from the lattice.

7. The system of claim 3, wherein the module configured to control the processor to extract the pivot baseline further extracts the longest path from the lattice.

8. The system of claim 3, wherein the time slots of transition T comprise a speech interval between starting and ending time frames of T.

9. The system of claim 3, further comprising a module configured to control the processor to apply the probabilities of the block diagonal matrix confidence scores to spoken language understanding.

10. The system of claim 3, further comprising a module configured to control the processor to apply the probabilities of the block diagonal matrix confidence scores to machine translation.

11. The system of claim 3, further comprising a module configured to control the processor to apply the probabilities of the block diagonal matrix confidence scores to named entity extraction.

12. The system of claim 1, wherein the module configured to control the processor to extract the pivot baseline further extracts a random path from the lattice.

13. The system of claim 1, wherein the block diagonal matrix preserves the accuracy of the lattice.

14. The system of claim 1, wherein the block diagonal matrix has the computational property.

15. The system of claim 1, wherein if the lattice is weighted, the system uses the probabilities of the block diagonal matrix as word confidence scores.

16. The system of claim 1, further comprising a module configured to control the processor to use the probabilities of the most probable path of the block diagonal matrix as confidence scores for unsupervised learning of language models.

17. The system of claim 1, further comprising a module configured to control the processor to use the probabilities of the most probable path of the block diagonal matrix as confidence scores for unsupervised learning for automatic speech recognition.

18. The system of claim 1, wherein the block diagonal matrix is smaller in size than the lattice.

19. A system of linearizing a lattice, the system comprising:

(1) a processor;

(2) a module configured to control the processor to compute posterior probabilities of all transitions T in a graph, if a lattice having transitions T is weighted;

(3) a module configured to control the processor to extract a pivot baseline path from the lattice; and

(4) a module configured to control the processor to linearize the lattice by aligning the transitions T in the lattice with the transitions in the pivot baseline path, wherein the linearized lattice can be visualized.

20. A tangible computer readable medium storing instructions for generating a block diagonal matrix from a lattice, the instructions comprising:

(1) computing posterior probability of all transitions T in a graph, if a lattice having transitions T is weighted;

(2) extracting a pivot baseline path from the lattice; and

(3) aligning the transitions T in the lattice with the transitions in the pivot baseline path.

21. A tangible computer readable medium storing a computer program having instructions for linearizing a lattice, the instructions comprising:

(1) computing posterior probabilities of all transitions T in a graph, if a lattice having transitions T is weighted;

(2) extracting a pivot baseline path from the lattice; and

(3) linearizing the lattice by aligning the transitions T in the lattice with the transitions in the pivot baseline path, wherein the linearized lattice can be visualized.