Pattern recognition with criterion for output from selected model to trigger succeeding models

• US 6,871,177 B1
• Filed: 10/27/1998
• Issued: 03/22/2005
• Est. Priority Date: 11/03/1997
• Status: Expired due to Term

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Wright, Mark, Ringland, Simon P. A, Hovell, Simon A
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Storm, Donald L.
• Application Number:
  US09/529,384
• Time in Patent Office: 2,338 Days
• Field of Search: 704/257, 704/255, 704/256, 704/231
• US Class Current: 704/256
• CPC Class Codes: G10L 15/26 Speech to text systems G10L15/08 takes precedence
• CPC Class Codes: G10L 2015/085 Methods for reducing search complexity, pruning

Abstract

A method and apparatus of recognizing a pattern comprising a sequence of sub-patterns includes a set of possible patterns being modelled by a network of sub-pattern models. One or more initial software model objects are instantiated first. As these models produce outputs, succeeding model objects are instantiated if they have not already been instantiated. However, the succeeding model objects are only instantiated if a triggering model output meets a predetermined criterion. This ensures that the processing required is maintained at a manageable level. If the models comprise finite state networks, pruning of internal states may also be performed. The criterion applied to this pruning is less harsh than that applied when determining whether to instantiate a succeeding model.

Claims

1. A method of recognising a pattern comprising a sequence of sub-patterns, the method comprising:

a) generating a data sequence representative of a physical entity;

b) applying the data sequence to a set comprising active models in a network of models including at least one model, wherein each model represents a sub-pattern and comprises a finite state network with a plurality of respective states,

c) assessing each state of members of said set and deactivating those states that do not meet a predetermined first criterion, between the application of successive data elements;

d) selecting a subset of the outputs of the members of said set according to a predetermined second criterion, and

e) adding further models to said set in dependence on the members of said subset when said subset is selected, wherein each further model includes a plurality a respective states, the further models take at least one of the subset members as inputs, and each model represents a sub-pattern and in use outputs an indication of the degree of matching between an input data sub-sequence and the represented sub-pattern.

2. A method according to claim 1, wherein a further model is only added to said set if the set does not already contain that model.

3. A method according to claim 1, wherein the data sequence is applied to the network element-by-element and the selection of a subset of the outputs of the set of models is performed for each of successive applications of data sequence elements.

4. A method according to claim 1, wherein a model is removed from said set if all of its states have been deactivated.

5. A method according to claim 1, wherein the criterion applied to the model outputs is harsher than the criterion applied to states within models.

6. A method according to claim 1, wherein the application of the criterion applied to model outputs comprises creating a histogram of model outputs on the basis of their values and selecting those outputs in the bins of the histogram which contain the outputs having the best m values, wherein m is an integer.

7. A method according to claim 6, wherein model outputs are selected by setting output(s) that are not selected to a predetermined value.

8. A method according to claim 1, wherein the application of the criterion applied to all model states comprises creating a histogram of states on the basis of their values and selecting those states in the bins of the histogram which contain the states having the best n values, where n is an integer, for deactivation.

9. A method according to claim 1, wherein the pattern to be recognized is a speech pattern.

10. A method according to claim 9, wherein the models comprise models of subword vocalisations.

11. A method of generating a speech signal comprising performing a method according to claim 9, and operating a speech synthesizer in dependence on the result of performance of said method.

12. A method of operating a telephone switching centre comprising performing a method according to claim 9 and commanding a telephone switching centre for the purpose of establishing a telephone connection in dependence on the result of the performance of said method.

13. A method of operating a computer so as to recognise a pattern comprising a sequence of sub-patterns the method comprising:

generating a data sequence representative of a physical entity;

applying the data sequence to a set comprising active models in a network of models including at least one model, wherein each model represents a sub-pattern and comprises a finite state network with a plurality of respective states;

assessing each state of members of said set and deactivating those states that do not meet a predetermined first criterion, between the application of successive data elements;

selecting a subset of the outputs of the members of said set according to a predetermined second criterion; and

adding further models to said set in dependence on the members of said subset when said subset is selected, wherein each further model includes a plurality a respective states, the further models take at least one of the subset members as inputs, and each model represents a sub-pattern and in use outputs an indication of the degree of matching between an input data sub-sequence and the represented sub-pattern.

14. A pattern recognition apparatus for recognising a pattern comprising a sequence of sub-patterns, the apparatus comprising:

means for generating a data sequence representative of a physical entity;

means for applying the data sequence to a set comprising active models in a network of models including at least one model, wherein each model represents a sub-pattern and comprises a finite state network with a plurality of respective states;

means for assessing each state of members of said set and deactivating those states that do nor meet a predetermined first criterion, between the application of successive data elements;

means for selecting a subset of the outputs of the members of said set according to a predetermined second criterion; and

means for adding further models to said set in dependence on the members of said subset when said subset is selected, wherein each further model includes a plurality a respective states, the further models take at least one of the subset members as inputs, and each model represents a sub-pattern and in use outputs an indication of the degree of matching between an input data sub-sequence and the represented sub-pattern.

15. An apparatus according to claim 14, wherein a further model is only added to said set if the set does not already contain that model.

16. An apparatus according to claim 14, wherein the data sequence is applied to the network element-by-element and the selection of a subset of the outputs of the first set of models is performed between the applications of successive data sequence elements.

17. An apparatus according to claim 14, wherein a model is removed from said set if all of its states have been deactivated.

18. An apparatus according to claim 14, wherein the criterion applied to the model outputs is harsher than the criterion applied to states within models.

19. An apparatus according to claim 14, wherein the pattern to be recognized is a speech pattern.

20. An apparatus according to claim 19, wherein the models comprise models of sub-word vocalisations.

21. An apparatus for generating speech signal comprising an apparatus according to claim 19, and a speech synthesizer configured for operation in dependence on the operation of the speech recognition apparatus.

22. A telephone network apparatus comprising an apparatus according to claim 19 and a telephone switching centre, wherein the telephone switching centre operates to establish a telephone connection in dependence on the operation of the pattern recognition apparatus.