System and method of epsilon removal of weighted automata and transducers

• US 7,634,408 B1
• Filed: 04/28/2008
• Issued: 12/15/2009
• Est. Priority Date: 07/20/2001
• 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: Mohri, Mehryar
• Primary Examiner(s): Wozniak; James S
• Application Number:
  US12/110,920
• Time in Patent Office: 596 Days
• Field of Search: 704/257, 704/255, 704/251, 704/256, 704/1, 704/9, 704/10
• US Class Current: 704/251
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G10L 15/16 using artificial neural networks

Abstract

An improved ε-removal method is disclosed that computes for any input weighted automaton A with ε-transitions an equivalent weighted automaton B with no ε-transitions. The method comprises two main steps. The first step comprises computing for each state “p” of the automaton A its ε-closure. The second step in the method comprises modifying the outgoing transitions of each state “p” by removing those labeled with ε. The method next comprises adding to the set of transitions leaving the state “p” non-ε-transitions leaving each state “q” in the set of states reachable from “p” via a path labeled with ε with their weights pre-{circle around (x)}multiplied by the ε-distance from state “p” to state “q” in the automaton A. State “p” is a final state if some state “q” within the set of states reachable from “p” via a path labeled with ε is final and the final weight

$\rho \left[p\right]=\underset{q\in \varepsilon \left[p\right]\bigcap F}{\oplus }\left(d\left[p,q\right]\otimes p\left[q\right]\right).$

Claims

1. A method of processing an automaton A, the method comprising:

computing via a processor of ε

-closure C of an automaton as follows;

C[p]={(q,w);

q∈

ε

[p],d[p,q]=w∈

K−

{Ō

}}

where ε

[p] represents a set of states reachable from “

p”

via a path labeled with ε

, d[p,g] represents an ε

-distance from p to q in the automaton A, K is a semiring, and w represents weights;

modifying outgoing transitions of each state “

p”

by;

removing each of the outgoing transitions labeled with an empty string; and

adding to each of the outgoing transitions leaving ones of the set of states “

p”

a non-empty-string transition, wherein each of the set of states “

q”

is left with its weights pre-{circle around (x)}-multiplied by an ε

-distance from a corresponding one of the set of states “

p”

to a respective one of the set of states “

q”

in the automaton A; and

applying the modified automaton A to process information in a field of at least one of;

speech recognition, speech synthesis and text processing.

2. The method of claim 1, wherein in removing each of the outgoing transitions labeled with an empty string comply with the following pseudocode:

1 for each p ∈

Q 2  

do E[p] ←

(e ∈

E [p] ;

i[e] ≠

ε

) 3  

 

for each (q,w) ∈

C[p] 4  

 

 

do E[p] ←

E[p] U ((p,a,w  

w′

,r) ;

(q, a, w′

, r) ∈

E[q],a ≠

ε

) 5  

 

 

 

if q ∈

F 6  

 

 

 

 

then if p ∈

F 7  

 

 

 

 

 

then F ←

F U (p) 8  

 

 

 

 

 

 

p[p] ←

p[p] ⊕

(ω

⊕

p[q])

where E[p] represents outgoing transitions of each state p, Q is a finite set of states, and F is a finite set of states.

3. The method of claim 2, wherein states “

p”

is a final state if some state q∈

ε

[p] is final, and if so, then a final weight is;

$\mathrm{\rho <br><br>}<br><br>\left[p\right]=\underset{q\in <br><br>e<br><br>\left[p\right]\bigcap <br><br>F}{\oplus <br><br>}<br><br>\left(d<br><br>\left[p,q\right]\otimes <br><br>\mathrm{\rho <br><br>}<br><br>\left[q\right]\right).$

4. A method of processing an automaton A, the method comprising:

computing via a processor an ε

-closure for each state “

p”

of the automaton A;

modifying outgoing transitions of each state “

p”

by;

removing each of the outgoing transitions labeled with an empty string; and

adding to each of the outgoing transitions leaving ones of the set of states “

p”

a non-empty-string transition, wherein each of the set of states “

q”

is left with its weights pre-{circle around (x)}-multiplied by an ε

-distance from a corresponding one of the set of states “

p”

to a respective one of the set of states “

q”

in the automaton A; and

applying the modified automaton A to process information in a field of at least one of;

speech recognition, speech synthesis and text processing.

5. The method of claim 4, further comprising:

removing inaccessible ones of the states using a depth-first search of the automaton A.

6. The method of claim 4, wherein adding to each of the outgoing transitions leaving ones of the set of states “

p”

a non-empty-string transition, further comprises leaving each of the states “

q”

with weights (d[p,q]{circle around (x)}w[e]).

7. The method claim 4, wherein computing an ε

-closure for each one of the set of states “

p”

of an input automaton A further comprises;

removing all transitions not labeled with an empty string from the automaton A to produce an automaton A_ε

;

decomposing A_ε

into its strongly connected components; and

computing all-pairs shortest distances in each component visited in reverse topological order.

8. A computer-readable medium storing instructions for controlling a computing device to process automaton A, the instructions comprising:

computing of ε

-closure C[p] of an automaton as follows;

C[p]={(q,w);

q∈

ε

[p],d[p,q]=w∈

K−

{Ō

}}

where ε

[p] represents the set of states reachable from “

p”

via a path labeled with ε

, d[p,g] represents an ε

-distance from p to q in the automaton A, K is a semiring, and w represents weights;

modifying outgoing transitions of each state “

p”

by;

removing each of the outgoing transitions labeled with an empty string; and

adding to each of the outgoing transitions leaving ones of the set of states “

p”

a non-empty-string transition, wherein each of the set of states “

q”

is left with its weights pre-{circle around (x)}-multiplied by an ε

-distance from a corresponding one of the set of states “

p”

to a respective one of the set of states “

q”

in the automaton A; and

applying the modified automaton A to process information in a field of at least one of;

speech recognition, speech synthesis and text processing.

9. The computer-readable medium of claim 8, wherein removing each of the outgoing transitions labeled with an empty string complies with the following pseudocode:

1 for each p ∈

Q 2  

do E[p] ←

{e ∈

E [p] ;

i[e] ≠

ε

} 3  

 

for each (q,w) ∈

C[p] 4  

 

 

do E[p] ←

E[p] ∪

{(p,a,w  

w′

, r) ;

 

 

 

(q, a, w′

,r) ∈

E[q].a ≠

ε

} 5  

 

 

 

if q ∈

F 6  

 

 

 

 

then if p ∉

F 7  

 

 

 

 

 

then F ←

F ∪

{p} 8  

 

 

 

 

 

 

ρ

[p] ←

p[p] ⊕

(ω

⊕

ρ

[q])

where E[p] represents outgoing transitions of each state p, Q is a finite set of states, and F is a finite set of states.

10. The computer-readable medium of claim 9, wherein state “

p”

is a final state if some state q∈

ε

[p] is final, and if so, then a final weight is;

$\mathrm{\rho <br><br>}<br><br>\left[p\right]=\underset{q\in <br><br>e<br><br>\left[p\right]\bigcap <br><br>F}{\oplus <br><br>}<br><br>\left(d<br><br>\left[p,q\right]\otimes <br><br>\mathrm{\rho <br><br>}<br><br>\left[q\right]\right).$