Grammar fragment acquisition using syntactic and semantic clustering

• US 8,666,744 B1
• Filed: 09/21/2000
• Issued: 03/04/2014
• Est. Priority Date: 09/15/1995
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.), Nippon Telegraph and Telephone Corporation
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Arai, Kazuhiro, Gorin, Allen L., Riccardi, Giuseppe, Wright, Jeremy H.
• Primary Examiner(s): Armstrong, Angela A
• Application Number:
  US09/666,563
• Time in Patent Office: 4,912 Days
• Field of Search: 704 2- 10, 704/257, 704/245
• US Class Current: 704/257
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G10L 15/063 Training
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks
• CPC Class Codes: G10L 2015/0631 Creating reference templates; Clustering

Abstract

A method and apparatus are provided for automatically acquiring grammar fragments for recognizing and understanding fluently spoken language. Grammar fragments representing a set of syntactically and semantically similar phrases may be generated using three probability distributions: of succeeding words, of preceding words, and of associated call-types. The similarity between phrases may be measured by applying Kullback-Leibler distance to these three probability distributions. Phrases being close in all three distances may be clustered into a grammar fragment.

Claims

1. A method comprising:

selecting candidate multi-word phrases from a set of words, wherein a maximum number of candidate multi-word phrases is based on a highest of a number of preceding contexts, a number of candidate fragments, and a number of call-types;

using a semantic similarity and a syntactic similarity in the candidate multi-word phrases to generate semantic measurements and syntactic measurements associated with a succeeding context of a succeeding phrase and a preceding context of a preceding phrase; and

clustering, via a processor, the candidate multi-word phrases into a grammar fragment based on the semantic measurements and the syntactic measurements, to yield a clustered grammar fragment representing similar phrases that are both syntactically and semantically coherent.

2. The method of claim 1, wherein each candidate phrase has both semantic associations and syntactic associations.

3. The method of claim 2, wherein the syntactic associations are syntactic probabilistic distributions of the succeeding context and syntactic probabilistic distributions of the preceding context.

4. The method of claim 3, wherein the semantic associations are semantic probabilistic distributions.

5. The method of claim 4, wherein the semantic similarity and syntactic similarity are measured by applying distance measurements between the syntactic probabilistic distributions of the succeeding context, the syntactic probabilistic distributions of the preceding context, and the semantic probabilistic distributions.

6. The method of claim 5, wherein the semantic probability distributions are combined with the syntactic probabilistic distributions of the succeeding context and the syntactic probabilistic distributions of the preceding context.

7. The method of claim 6, wherein the method is recursive.

8. The method of claim 5, wherein the semantic measurements and the syntactic measurements are calculated using Kullback-Leibler distance measurements.

9. A method comprising:

selecting a set of candidate multi-word phrases from a database of utterances based on a frequency of occurrence of the candidate phrases, wherein a maximum number of candidate multi-word phrases is based on a highest of a number of preceding contexts, a number of candidate fragments, and a number of call-types;

forming, via a processor, a measurement of similarity between the selected candidate phrases, wherein the measurement of similarity is associated with a succeeding context of a succeeding phrase and a preceding context of a preceding phrase; and

based on the measurement, clustering a plurality of the set of candidate phrases into a grammar fragment to yield a cluster grammar fragment representing similar phrases that are both syntactically coherent and semantically coherent.

10. The method of claim 9, wherein the measurement is based on a probability distribution of contextual phrases of the candidate phrases.

11. The method of claim 10, wherein a contextual phrase precedes a candidate phrase.

12. The method of claim 10, wherein a contextual phrase succeeds a candidate phrase.

13. The method of claim 9, further comprising:

selecting a reference phrase from the set of candidate phrases;

ranking others of the candidate phrases based on a similarity to the reference phrase; and

merging one of the others of the candidate phrases with the reference phrase based on respective ranks.

14. The method of claim 9, further comprising using the grammar fragment for call-type classification.

15. A method comprising:

(1) processing an utterance associated with a call by applying a grammar fragment to the utterance, the grammar fragment being formed by;

(a) selecting a set of candidate multi-word phrases from a database of utterances based on a frequency of occurrence of the candidate phrases, wherein a maximum number of candidate multi-word phrases is based on a highest of a number of preceding contexts, a number of candidate fragments, and a number of call-types;

(b) forming, via a processor, a measurement of similarity between the selected candidate phrases, the measurement being associated with a succeeding context of a succeeding phrase and a preceding context of preceding phrase; and

(c) based on the measurement, clustering a plurality of the selected candidate phrases into a grammar fragment to yield a cluster grammar fragment representing similar phrases that are both syntactically coherent and semantically coherent;

and

(2) determining, based on the processing, an appropriate handling for the call.

16. The method of claim 15, wherein the handling comprises classifying the call according to type.