Method for building linguistic models from a corpus

• US 6,415,248 B1
• Filed: 11/19/1999
• Issued: 07/02/2002
• Est. Priority Date: 12/09/1998
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Bangalore, Srinivas, Riccardi, Giuseppe
• Primary Examiner(s): Edouard, Patrick N.
• Application Number:
  US09/443,891
• Time in Patent Office: 956 Days
• Field of Search: 704/1, 704/8-10, 704/255, 704/256, 704/257
• US Class Current: 704/1
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G10L 15/183 using context dependencies, e.g. language models
• CPC Class Codes: G10L 15/19 Grammatical context, e.g. disambiguation of the recognition hypotheses based on word sequence rules

Abstract

A method iteratively integrates clustering techniques with phrase acquisition techniques to build complex linguistic models from a corpus. A set of features is initialized by the corpus. Thereafter, the method determines, according to a predetermined cost function, to process the features by one of phrase clustering processing or phrase grammar learning processing. If phrase clustering processing is performed, the method processes an interstitial set of features comprising both the old features and newly established clusters by phrase grammar learning processing. The features obtained as an output of phrase grammar learning is re-indexed as a set of features for a subsequent iteration. The method may be repeated over several iterations to build a hierarchical linguistic model.

Claims

1. A method of building a linguistic model from a corpus of features, comprising:

determining whether to perform clustering based upon a cost function

2. A method of building a linguistic model from a corpus of features, comprising:

determining whether to perform clustering based upon a predetermined cost function;

if so, clustering upon the features into classes;

thereafter, performing phrase acquisition upon the features and the classes; and

storing the acquired phrases in a computer readable medium;

wherein the clustering step comprises;

identifying context symbols within the features,

for each non-context symbol in the features, counting occurrences of predetermined relationships between the non-context symbol and a context symbol,

generating frequency vectors for each non-context symbol based upon the counted occurrences, and

clustering non-context symbols based upon the frequency vectors.

3. The method of claim 2, wherein the clustering is performed based on Euclidean distances between frequency vectors.

4. The method of claim 2, wherein the clustering is performed based on Manhattan distances between frequency vectors.

5. The method of claim 2, wherein the clustering is performed based on maximum distance metrics between frequency vectors.

6. The method of claim 2, wherein the frequency vectors of a non-context symbol is normalized based upon the number of occurrences of the non-context symbol in the features.

7. The method of claim 2, wherein the frequency vectors are multi dimensional vectors, the number of dimensions determined by the number of context symbols and different levels of adjacency identified in the counting step.

8. The method of claim 2, wherein clusters may be represented by a centroid vector.

9. A method of building a linguistic model from a set of features, the features initially constituting text from an input corpus, comprising:

applying a cost function to the set of features, the cost function defined by

10. A method of building a linguistic model from a set of features, the features initially constituting text from an input corpus, comprising:

applying a cost function to the set of features, based upon the results of the cost function, performing clustering on the set of features, the clustering resulting in classes that are included in the set of features;

performing phrase acquisition on the set of features; and

storing the acquired phrases in a computer readable medium;

wherein the clustering step comprises;

identifying context tokens within the set of features,

for each non-context token in the set of features, counting occurrences of predetermined relationships between the non-context token and a context token,

generating frequency vectors for each non-context token based upon the counted occurrences, and

clustering non-context tokens based upon the frequency vectors.

11. The method of claim 10, wherein the clustering is performed based on Euclidean distances between frequency vectors.

12. The method of claim 10, wherein the clustering is performed based on Manhattan distances between frequency vectors.

13. The method of claim 10, wherein the clustering is performed based on maximum distance metrics between frequency vectors.

14. The method of claim 10, wherein the frequency vectors of a non-context token is normalized based upon the number of occurrences of the non-context token in the set of features.

15. The method of claim 10, wherein the frequency vectors are multi dimensional vectors, the number of dimensions determined by the number of context tokens and different level of adjacency identified in the counting step.

16. The method of claim 10, wherein clusters may be represented by a centroid vector.

17. A method of building a linguistic model from a corpus, comprising:

initializing a set of features based upon the corpus, iteratively;

determining, based upon a predetermined cost function, whether to perform clustering upon the set of features and, if so, performing clustering on the set of features to identify classes therefrom,

performing phrase acquisition on the set of features and any classes that exist to obtain phrases therefrom,

re-initializing the set of features for a subsequent iteration to include the set of features, the classes and the phrases; and

storing the set of features, the classes, and the phrases in a computer readable medium;

wherein the cost function is;

18. A method of building a linguistic model from a corpus, comprising:

initializing a set of features based upon the corpus, iteratively;

determining, based upon a predetermined cost function, whether to perform clustering upon the set of features and, if so, performing clustering on the set of features to identify classes therefrom,

performing phrase acquisition on the set of features and any classes that exist to obtain phrases therefrom,

re-initializing the set of features for a subsequent iteration to include the set of features, the classes and the phrases; and

storing the set of features, the classes, and the phrases in a computer readable medium;

wherein the clustering step comprises;

identifying context tokens within the set of features,

for each non-context token in the set of features, counting occurrences of predetermined relationships between the non-context token and a context token,

generating frequency vectors for each non-context token based upon the counted occurrences, and

clustering non-context tokens based upon the frequency vectors.

19. The method of claim 18, wherein the clustering is performed based on Euclidean distances between frequency vectors.

20. The method of claim 18, wherein the clustering is performed based on Manhattan distances between frequency vectors.

21. The method of claim 18, wherein the clustering is performed based on maximum distance metrics between frequency vectors.

22. The method of claim 18, wherein the frequency vectors of a non-context token is normalized based upon the number of occurrences of the non-context token in the set of features.

23. The method of claim 18, wherein the frequency vectors are multi dimensional vectors, the number of dimensions determined by the number of context tokens and different level of adjacency identified in the counting step.

24. The method of claim 18, wherein clusters may be represented by a centroid vector.

25. A machine-readable medium having stored thereon executable instructions that when executed by a processor, cause the processor to build a linguistic model from a corpus of features by:

determining whether to perform clustering based upon a cost function

26. A machine-readable medium having stored thereon executable instructions that when executed by a processor, cause the processor to build a linguistic model from a corpus of features, by:

determining whether to perform clustering based upon a predetermined cost function;

if so, clustering upon the features into classes;

thereafter, performing phrase acquisition upon the features and the classes; and

storing the acquired phrases in a computer readable medium;

wherein the clustering step comprises;

identifying context symbols within the features,

for each non-context symbol in the features, counting occurrences of predetermined relationships between the non-context symbol and a context symbol,

generating frequency vectors for each non-context symbol based upon the counted occurrences, and

clustering non-context symbols based upon the frequency vectors.

27. A machine-readable medium having stored thereon a linguistic model generated from a corpus of features according to the process of:

determining whether to perform clustering based upon a cost function

28. A machine-readable medium having stored thereon a linguistic model generated from a corpus of features according to the process of:

determining whether to perform clustering based upon a predetermined cost function;

if so, clustering upon the features into classes;

thereafter, performing phrase acquisition upon the features and the classes; and

storing the acquired phrases in a computer readable medium;

wherein the clustering step comprises;

identifying context symbols within the features,

for each non-context symbol in the features, counting occurrences of predetermined relationships between the non-context symbol and a context symbol,

generating frequency vectors for each non-context symbol based upon the counted occurrences, and

clustering non-context symbols based upon the frequency vectors.