On-demand language processing system and method

• US 6,278,973 B1
• Filed: 12/12/1995
• Issued: 08/21/2001
• Est. Priority Date: 12/12/1995
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Chung, Pi-Yu, Pereira, Fernando Carlos, Riley, Michael Dennis, Mohri, Mehryar
• Primary Examiner(s): Tsang, Fan
• Assistant Examiner(s): Opsasnick, Michael N.
• Application Number:
  US08/570,788
• Time in Patent Office: 2,079 Days
• Field of Search: 395/2.66, 395/2.65, 395/2.215
• US Class Current: 704/257
• CPC Class Codes: G10L 15/08 Speech classification or search
• CPC Class Codes: G10L 15/183 using context dependencies, e.g. language models

Abstract

A language recognition methodology is provided whereby any finite-state model of context may be used in a very general class of decoding cascades, and without requiring specialized decoders or full network expansion. The methodology includes two fundamental improvements: (1) a simple generalization, weighted finite-state transducers, of existing network models, and (2) a novel on-demand execution technique for network combination. With the methodology of the invention one or more of the network cascades are formulated as a finite state transducer, and is composed, for a selected portion of the network, with a next successively higher level of the network cascade to prescribe a mapped portion of that next successively higher level corresponding to the portion of the network cascade selected to be expanded.

Claims

1. In a speech processing system wherein predetermined linguistic information is represented in a hierarchal cascade of network models and a linkage between successive levels of said network models is defined by a mapping function, and wherein at least one path within each said network model is defined by connections among a plurality of predetermined states, a method for input speech evaluation by on-demand expansion of a selected portion of at least one of said network models comprising the steps of:

formulating said at least one of said network models as a finite state transducer, said transducer representing said mapping function between said at least one network model and an adjacent one of said cascaded network models;

selecting a state in a one of said at least one transducers having a correspondence to said selected portion of said at least one network model;

composing said one of said at least one transducers with a next successively higher level of said network models to prescribe a mapped portion of said next successively higher level corresponding to said selected portion of said at least one network model;

iteratively repeating said selecting step and said composing step for each successively higher level network model representing said selected portion; and

evaluating an input speech signal against a candidate speech segment provided by one of said network models.

2. The method for on-demand expansion of claim 1 wherein at least one of said levels of said network cascade is represented in terms of context dependent units.

3. The method for on-demand expansion of claim 1 wherein said selecting step and said composing step are implemented as a generalized state machine C, said machine being created as a composition of a generalized state machine A, corresponding to said one of said at least one transducers, with a generalized state machine B, corresponding to said next successively higher level of said network cascade.

4. The method for on-demand expansion of claim 3 wherein said generalized state machine C supports the functions:

C.start;

=returns A.start paired with B.start

C.final((s1,s2));

=for state s1,s2, returns A.final(s1) Ù

B.final(s2)

C.arcs((s1,s2));

=for state s1,s2, returns Merge(A.arcs(s1), B.arcs(s2))

where merged arcs are defined as;

(label 1, label 3, x+y, (next state 1, next state 2)) Î

Merge(A.arcs(s1), B.arcs(s2))

iff

(label 1, label 2, x, next state 1) Î

A.arcs(s1) and (label 2, label 3, y, next state 2) Î

B.arcs(s2);

where, using M to represent any of generalized state machines C, A or B;

M.start returns, on request, the start state for machine M;

M.final(state) represents probability of accepting at a given state; and

M.arcs(state) returns, for a given state, transitions (a₁, a₂, . . . a_N) leaving the given

state, where a_i=(input label, output label, weight &

next state).

5. The method for on-demand expansion of claim 1 further including a step of storing at least a part of said on-demand expansion of said selected portion of said network cascade in a storage cache.

6. The method for on-demand expansion of claim 5 wherein said storage cache is implemented as a generalized state machine of the form:

N.start;

=M.start

N.final(state);

=M.final(state)

N.arcs(state);

=M.arcs(state)

where;

M represents an input machine and N represents said cache machine;

M.start returns, on request, the start state for machine M;

M.final(state) represents probability of accepting at a given state; and

M.arcs(state) returns, for a given state, transitions (a₁, a₂, . . . a_N) leaving the given state, where a_i=(input label, output label, weight &

next state); and

corresponding functions of generalized state machine N are equivalently defined.

7. The method for on-demand expansion of claim 1 wherein said selected portion of said network cascade corresponds to an unknown speech fragment of interest.

8. The method for on-demand expansion of claim 1 further including the step of inserting a filter in said composition of said one of said at least one transducers with said next successively higher level, wherein said filter operates to remove redundant paths occurring between a pair of states in said composition.

9. The method for on-demand expansion of claim 8 wherein said filter is manifested as a finite state transducer.

10. A speech processing system operable to provide on-demand expansion of a selected portion of a linguistic model, wherein predetermined linguistic information established for training said system is represented in a hierarchal cascade of network models and a linkage between successive levels of said network models is defined by a mapping function, and wherein at least one path within each said network model is defined by connections among a plurality of predetermined states, said system comprising:

decoding means for evaluating input speech signals against a candidate speech segment provided by one of said network models;

a finite state transducer operable to represent said mapping function between at least one of said network models and an adjacent one of said cascaded network models;

means for selecting a state in said transducer having a correspondence to said selected portion of said network model;

means for composing said transducer with a next successively higher level of said network model to prescribe a mapped portion of said next successively higher level corresponding to said selected portion of said network model; and

means for iteratively applying said transducer and said composing means to successively higher level network models representing said selected portion.

11. The speech processing system of claim 10 further characterized in that at least one of said levels of said network cascade is represented in terms of context dependent units.

12. The speech processing system of claim 10 further characterized in that said selecting step and said composing step are implemented as a generalized state machine C, said machine being created as a composition of a generalized state machine A, corresponding to said one of said at least one transducers, with a generalized state machine B, corresponding to said next successively higher level of said network cascade.

13. The speech processing system of claim 12 wherein said generalized state machine C supports the functions:

C.start;

=returns A.start paired with B.start

C.final((s1,s2));

=for state s1,s2, returns A.final(s1) Ù

B.final(s2)

C.arcs((s1,s2));

=for state s1,s2, returns Merge(A.arcs(s1), B.arcs(s2))

where merged arcs are defined as;

(label 1, label 3, x+y, (next state 1, next state 2)) Î

Merge(A.arcs(s1), B.arcs(s2))

iff

(label 1, label 2, x, next state 1) Î

A.arcs(s1) and (label 2, label 3, y, next state 2) Î

B.arcs(s2);

where, using M to represent any of generalized state machines C, A or B;

M.start returns, on request, the start state for machine M;

M.final(state) represents probability of accepting at a given state; and

M.arcs(state) returns, for a given state, transitions (a₁, a₂, . . . a_N) leaving the given state, where a_i=(input label, output label, weight &

next state).

14. The speech processing system of claim 10 further including a storage cache for storing at least a part of said on-demand expansion of said selected portion of said network cascade.

15. The speech processing system of claim 14 wherein said storage cache is implemented as a generalized state machine of the form:

N.start;

=M.start

N.final(state);

=M.final(state)

N.arcs(state);

=M.arcs(state)

where;

M represents an input machine and N represents said cache machine;

M.start returns, on request, the start state for machine M;

M.final(state) represents probability of accepting at a given state; and

M.arcs(state) returns, for a given state, transitions (a₁, a₁, . . . a_N) leaving the given state, where a_i=(input) label, output label, weight &

next state); and

corresponding functions of generalized state machine N are equivalently defined.

16. The speech processing system of claim 10 further characterized in that said selected portion of said network cascade corresponds to an unknown speech fragment of interest.

17. The speech processing system of claim 10 further including a filter means operative to remove redundant paths occurring between a pair of states in a composition created by said means for composing.

18. In a system for recognition of an unknown pattern in an input signal, said pattern being indicative of underlying information content, wherein data applied to train said system are represented in a hierarchal cascade of network models and a linkage between successive levels of said network models is defined by a mapping function, and wherein at least one path within each said network model is defined by connections among a plurality of predetermined states, a method for input pattern evaluation by on-demand expansion of a selected portion of at least one of said network models comprising the steps of:

formulating said at least one of said network models as a finite state transducer, said transducer representing said mapping function between said at least one network model and an adjacent one of said cascaded network models;

selecting a state in a one of said at least one transducers having a correspondence to said selected portion of said at least one network model;

composing said one of said at least one transducers with a next successively higher level of said network models to prescribe a mapped portion of said next successively higher level corresponding to said selected portion of said at least one network model;

iteratively repeating said selecting step and said composing step for each successively higher level network model representing said selected portion; and

evaluating an input signal pattern against a candidate pattern segment provided by one of said network models.

19. The method for on-demand expansion of claim 18 wherein at least one of said levels of said network cascade is represented in terms of context dependent units.

20. In a system for processing linguistic information in an input signal, wherein predetermined linguistic information established for training said system is represented in a hierarchal cascade of network models and a linkage between successive levels of said network models is defined by a mapping function, and wherein at least one path within each said network model is defined by connections among a plurality of predetermined states, a method for evaluation of input linguistic information by on-demand expansion of a selected portion of at least one of said network models comprising the steps of:

formulating said at least one of said network models as a finite state transducer, said transducer representing said mapping function between said at least one network model and an adjacent one of said cascaded network models;

selecting a state in a one of said at least one transducers having a correspondence to said selected portion of said at least one network model;

composing said one of said at least one transducers with a next successively higher level of said network models to prescribe a mapped portion of said next successively higher level corresponding to said selected portion of said at least one network model;

iteratively repeating said selecting step and said composing step for each successively higher level network model representing said selected portion; and

evaluating an input linguistic-information signal against a candidate linguistic-information segment provided by one of said network models.

21. In a system for processing linguistic information, wherein predetermined linguistic information established for training said system is represented in a hierarchal cascade of network models and a linkage between successive levels of said network models is defined by a mapping function, and wherein at least one path within each said network model is defined by connections among a plurality of predetermined states, a sub-system for providing on-demand expansion of a selected portion of at least one of said network models, comprising:

decoding means for evaluating an input linguistic-information signal against a candidate linguistic-information segment provided by one of said network models

means for formulating said at least one of said network models as a finite state transducer, said transducer representing said mapping function between said at least one network model and an adjacent one of said cascaded network models;

means for selecting a state in a one of said at least one transducers having a correspondence to said selected portion of said at least one network model;

means for composing said one of said at least one transducers with a next successively higher level of said network models to prescribe a mapped portion of said next successively higher level corresponding to said selected portion of said at least one network model; and

means for iteratively applying said means for selecting and said means for composing for successively higher level network models representing said selected portion.