Method and system for pattern recognition based on tree organized probability densities

• US 5,857,169 A
• Filed: 08/28/1996
• Issued: 01/05/1999
• Est. Priority Date: 08/28/1995
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Seide, Frank
• Primary Examiner(s): Knepper, David D.
• Assistant Examiner(s): SOFOCLEOUS, MICHAEL D
• Application Number:
  US08/704,199
• Time in Patent Office: 860 Days
• Field of Search: 704/255, 704/256, 704/231, 704/251, 704/243
• US Class Current: 704/256.7
• CPC Class Codes: G10L 15/14 using statistical models, e.g. Hidden Markov Models [HMMs] G10L15/18 takes precedence
• CPC Class Codes: G10L 15/142 Hidden Markov Models [HMMs]

Abstract

A time-sequential input pattern (20), which is derived from a continual physical quantity, such as speech is recognized. The system includes input means (30), which accesses the physical quantity and therefrom generates a sequence of input observation vectors. The input observation vectors represent the input pattern. A reference pattern database (40) is used for storing reference patterns, which consist of a sequence of reference units. Each reference unit is represented by associated reference probability densities. A tree builder (60) represents for each reference unit the set of associated reference probability densities as a tree structure. Each leaf node of the tree corresponds to a reference probability density. Each non-leaf node corresponds to a cluster probability density, which is derived from all reference probability densities corresponding to leaf nodes in branches below the non-leaf node. A localizer (50) is used for locating among the reference patterns stored in the reference pattern database (40) a recognised reference pattern, which corresponds to the input pattern. The locating includes, for each input observation vector, searching each tree structure for reference probability densities which give a high likelihood for the observation vector. Each tree is searched by selecting at the level immediately below the root node a number of nodes for which the corresponding cluster probability densities give an optimum cluster likelihood. This is repeated at successively lower levels of the tree by using each selected node as a root node, until the selected node is a leaf node. For each selected leaf node, the corresponding reference probability density is used to calculate the likelihood of the input observation vector. These likelihoods are combined per reference pattern to give a pattern similarity score. The recognised pattern is one of the reference patterns for which an optimum of the pattern similarity scores is calculated. Output means (70) are used for outputting the recognised pattern.

Claims

1. A method for recognising an input pattern which is derived from a continual physical quantity, said method comprising the steps of:

accessing said physical quantity and therefrom generating a sequence of input observation vectors, representing said input pattern;

locating among a plurality of reference patterns a recognised reference pattern, which corresponds to said input pattern;

at least one reference pattern being a sequence of reference units;

each reference unit being represented by at least one associated reference probability density in a set of reference probability densities;

representing a selection of the reference probability densities as a tree structure, where each leaf node corresponds to a reference probability density, and where each non-leaf node corresponds to a cluster probability density, which is derived from reference probability densities corresponding to leaf nodes in branches of said non-leaf node;

said locating comprising for each input observation vector o;

selecting a plurality of leaf nodes by searching said tree structure via non-leaf nodes for which the corresponding cluster probability density gives an optimum cluster likelihood for said input observation vector o; and

calculating an observation likelihood of said input observation vector o for each reference probability density which corresponds to a selected leaf node,

said method comprising representing the reference probability densities associated with each reference unit as a separate tree structure, and

said locating comprising selecting leaf nodes of each separate tree structure by performing said searching for each separate tree structure.

2. A method as claimed in claim 1, wherein searching said tree structure via non-leaf nodes includes searching at at least one level of said tree structure a path via one non-leaf node for which an optimum of said cluster likelihood is calculated, supplemented by paths via non-leaf nodes for which said cluster likelihood is within a predetermined range of said optimum cluster likelihood.

3. A method as claimed in claim 1, wherein said tree structure is a quaternary tree, in which each non-leaf node is hierarchically one level above a maximum of four nodes and at least one non-leaf node is hierarchically one level above four nodes.

4. A method as claimed in claim 1, wherein

searching said tree structure via said non-leaf nodes comprises, for a group of non-leaf nodes within a same branch of said tree structure and at a same level of said tree structure:

calculating for a selected pair of said non-leaf nodes a cluster comparison score between the two corresponding cluster probability densities and said input observation vector o;

said cluster comparison score indicating which of the two corresponding cluster probability densities gives the highest likelihood for the input observation vector o;

repeating calculating said cluster comparison score for the non-leaf node, for which the previously calculated cluster comparison score indicated the highest likelihood, and another non-leaf node of said group for which no cluster comparison score has been calculated yet, until a cluster comparison score has been calculated for all non-leaf nodes of said group; and

including in said searching, a path via the non-leaf node for which the cluster comparison score indicated the highest likelihood.

5. A method as claimed in claim 1, wherein:

the probability densities are derived from a sequence of training observation vectors, representing known input patterns;

said representing said set of reference probability densities as a tree structure comprises;

clustering said training observation vectors into a hierarchical set of clusters and calculating for each cluster a cluster probability density

segmenting said sequence of training observation vectors into a sequence of corresponding reference patterns and corresponding reference units; and

iteratively;

clustering for each reference unit the corresponding training observation vectors into a hierarchical set of clusters, forming separate tree structures, each of which corresponds to a separate reference unit; and

time aligning said sequence of training observation vectors according to said sequence of reference units by;

determining for each training observation vector a corresponding reference unit, which according to a predetermined optimality criterion is most likely, and

assigning each training observation vector to one of said clusters by searching the tree structure of the corresponding reference unit for the cluster with an optimum cluster likelihood.

6. A system for recognising a time-sequential input pattern, which is derived from a continual physical quantity, said system comprising:

input means for accessing said physical quantity and therefrom generating a sequence of input observation vectors, representing said input pattern;

a tree builder for representing a selection of reference probability densities from a set of reference probabilities as a tree structure, where each leaf node corresponds to a reference probability density, and where each non-leaf node corresponds to a cluster probability density, which is derived from all reference probability densities corresponding to leaf nodes in branches below said non-leaf node;

a reference pattern database for storing a plurality of reference patterns, at least one reference pattern being a sequence of reference units;

each reference unit being represented by at least one associated reference probability density in said set of reference probability densities, said selection of reference probability densities being stored as said tree structure;

a localizer for locating among the reference patterns stored in said reference pattern database a recognised reference pattern, which corresponds to said input pattern, said locating comprising for each input observation vector o;

selecting a plurality of leaf nodes by searching said tree structure via non-leaf nodes for which the corresponding cluster probability density gives an optimum cluster likelihood for said input observation vector o, and

calculating an observation likelihood of said input observation vector o for each reference probability density which corresponds to a selected leaf node; and

output means for outputting said recognised pattern;

wherein;

said tree builder is conceived to for each reference unit represent the associated reference probability densities as a separate tree structure,

said reference pattern database further stores for each reference unit said separate tree structure, and

said locating comprises selecting leaf nodes of each separate tree structure by performing said searching for each separate tree structure.

7. A system as claimed in claim 6, wherein searching said tree structure via non-leaf nodes includes searching at at least one level of said tree structure a path via one non-leaf node for which an optimum of said cluster likelihood is calculated, supplemented by paths via non-leaf nodes for which said cluster likelihood is within a predetermined range of said optimum cluster likelihood.

8. A system as claimed in claim 6, wherein said tree structure is a quaternary tree, in which each non-leaf node is hierarchically one level above a maximum of four nodes and at least one non-leaf node is hierarchically one level above four nodes.

9. A system as claimed in claim 6, wherein searching said tree structure via said non-leaf nodes comprises for a group of non-leaf nodes within a same branch of said tree structure and at a same level of said tree structure:

calculating for a selected pair of said non-leaf nodes a cluster comparison score between the two corresponding cluster probability densities and said input observation vector o;

said cluster comparison score indicating which of the two corresponding cluster probability densities gives the highest likelihood for the input observation vector o;

repeating calculating said cluster comparison score for the non-leaf node, for which the previously calculated cluster comparison score indicated the highest likelihood, and another non-leaf node of said group for which no cluster comparison score has been calculated yet, until a cluster comparison score has been calculated for all non-leaf nodes of said group; and

including in said searching a path via the non-leaf node for which the cluster comparison score indicated the highest likelihood.

10. A system as claimed in claim 6, wherein:

the probability densities are derived from a sequence of training observation vectors, representing known input patterns;

said representing said set of reference probability densities as a tree structure comprises;

clustering said training observation vectors into a hierarchical set of clusters and calculating for each cluster a cluster probability density

segmenting said sequence of training observation vectors into a sequence of corresponding reference patterns and corresponding reference units; and

iteratively;

clustering for each reference unit the corresponding training observation vectors into a hierarchical set of clusters, forming separate tree structures, each of which corresponds to a separate reference unit; and

time aligning said sequence of training observation vectors according to said sequence of reference units by;

determining for each training observation vector a corresponding reference unit, which according to a predetermined optimality criterion is most likely, and

assigning each training observation vector to one of said clusters by searching the tree structure of the corresponding reference unit for the cluster with an optimum cluster likelihood.