Method for building linguistic models from a corpus

[0002] This application benefits from the priority of U.S. patent application Ser. No. 60/111,631, entitled “Automatic Acquisition of Phrase Grammars for Stochastic Language Modeling,” filed Dec. 9, 1998.

[0003] The present invention relates to a method that builds phrase grammars from a corpus of speech, text, phonemes or any kind of symbolic input (herein “the corpus”).

[0004] It has long been a goal of computing systems to interact with human users using natural language from the users. That is, rather than restricting the user to predetermined syntactic commands, it would be preferable to have the user express a command in the most natural way for the user and to have a computer comprehend the command. Although modern computing systems have improved remarkably in their ability to recognize spoken words, comprehension of speech still is limited because these system cannot ascribe meanings to the commands.

[0005] Significant advances have been made in the ability of modern computing systems to acquire phrases from a corpus. For example, acquisition techniques are disclosed in U.S. patent application Ser. No. 08/960,291, entitled “Automatic Generation of Superwords,” filed Oct. 29, 1997. Other examples may be found in E. Giachin, “Phrase Bigram for Continuous Speech Recognition,” Proc. ICASSP, pp. 225-228, (1995), K. Ries, et al., “Improved Language Modeling by Unsupervised Acquisition of Structure,” Proc. ICASSP, pp. 193-196 (1995).

[0006] Additionally, advances have been made in the ability of such systems to classify words that possess similar lexical significance. The inventors, for example, have developed a clustering technique as disclosed in co-pending U.S. patent application Ser. No. 207,326 entitled “Automatic Clustering of Tokens from a Corpus of Speech,” the disclosure of which is incorporated herein. Clustering processing also is disclosed in Kneser, et al., “Improved Clustering Techniques for Class-Based Statistical Language Modeling,” Eurospeech (1993) and in McCandless, et al., “Empirical Acquisition of Word and Phrase Classes in the Atis Domain,” Third European Conf. Speech Comm. Tech. (1993).

[0007] While phrase acquisition and clustering techniques improve the ability of a computing system to comprehend speech, neither technique alone can build a structure model from a corpus of speech or text. Accordingly, there is a need in the art for a method for building a linguistic model from a corpus of speech or text.

[0008] The present invention provides a method that combines clustering techniques with phrase acquisition techniques with a closed-loop optimization method 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.

[0009] FIG. 1 illustrates a method in accordance with an embodiment of the present invention.

[0010] FIG. 2 is a flow diagram of a method of an embodiment of the present invention.

[0011] FIG. 3 illustrates mapping frequency vectors that may be obtained during operation of the present invention.

[0012] FIG. 4 illustrates an exemplary cluster tree.

[0013] The present invention provides a method that combines clustering techniques with phrase acquisition techniques within a closed-loop optimization method 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.

[0014] FIG. 1 illustrates a method 1000 of operation according to an embodiment of the present invention. The method operates on a set of “features” that initially comprises the set of words in the corpus of text (Step 1010). According to the embodiment, the method determines whether to perform phrase clustering or phrase grammar learning (Step 1020). If the method determines to perform phrase clustering, the method identifies new classes of features from the initialized set of features (Step 1030). Thereafter, if the method determines to perform phrase grammar learning at step 1020, the method performs phrase grammar learning from the features available at that step (Step 1040). Note that the features available to the phrase grammar learning step may include additional new classes if the method advances to step 1040 from step 1030. At the conclusion of step 1040, the method may re-index the set of features output from the phrase grammar learning step as the set of features for a subsequent iteration (Step 1050).

[0015] As the method 1000 operates upon the features, features can include words as well as phrases and classes. As is known, a “phrase” is a group or words and/or classes that operates as a single lexical unit and a “class” is a collection of words and/or phrases that possess similar lexical significance in the language model. The present invention builds phrases and classes from the features and integrates the phrases and classes into the set of features.

[0016] Phrase grammar learning may be performed in accordance with the techniques noted above for phrase acquisition. “Phrase grammar learning” differs from phrase acquisition in the types of inputs upon which the processing may be performed. Whereas phrase acquisition is performed typically only upon terminal symbols in a corpus (i.e. “words”), phrase grammar learning implies that the phrase acquisition techniques of the prior art are applied not only to the terminal symbols but also to non-terminal symbols such as the previously identified phrases and classes. By applying these techniques to classes, the method builds the linguistic relationships inherent in the corpus. The method builds hierarchical relationships over several iterations as a result of the construction of classes and the iterative nature of the method itself.

[0017] At step 1020, the decision to perform clustering or not may be driven by any number of cost functions. A cost function may indicate which of the two options is likely to be more advantageous toward building a language model from the present set of features. In essence, it indicates which option will result in “faster learning.”

[0018] In a first embodiment, the cost function is based on an entropy variation principle. Let V_irepresent the whole symbol space of features at a given iteration i. The search for the optimal set of V may be designed to maximize the entropy variation ΔH(f) over a set of features f_i={f₂, . . . , f_m}. In V_i: $\begin{array}{cc}{\max }_{f_i}\Delta H\left(f_i\right)={\max }_{f_i}{\hat{H}}_{{\lambda }_0}\left(T\right)-{\hat{H}}_{{\lambda }_{f_i}}\left(T\right)& \left(1\right)\\ {\max }_{f_i}{\hat{H}}_{{\lambda }_0}\left(T\right)-{\hat{H}}_{{\lambda }_{f_i}}\left(T\right)={\max }_{f_i}\frac{1}{n}\log \frac{P_{{\lambda }_{f_i}}\left(T\right)}{P_{{\lambda }_0}\left(T\right)}& \left(2\right)\end{array}$

[0019] where Ĥλ_fi(T) is the entropy of the corpus T based on the phrase n-gram model λ_fiand λ₀is the initial model. Eq. (1) follows from Eq. (2) in the sense of the law of large numbers. The search space over all possible features f in Eq. (1) is built upon the notion of phrase-ranking according to the p measure and phrase clustering rate. By varying these two parameters, one can search for the best learning strategies following the method 1000.

[0020] Other cost functions may be used. For example, the minimum distortion test described in McCandless, et al. (1993) above or the perplexity minimization test described in Kneser (1993) also above may be used as cost function indicators in Step 1020.

[0021] Phrase-grammars allow for an increased generalization power, since they can generate similar phrases that may never have been observed in a training corpus. This generalization property may be used additionally for smoothing the word probabilities in the context of stochastic language modeling for speech recognition and understanding. Standard class-based models smooth the word n-gram probability P(w_i|w_i-n+1, . . . , w_i-1) in the following way:

[0022] P(w_i|w_i-n+1, . . . , w_i-1)=P(C_i|C_i-n+1, . . . , C_i-1)*P(w_i|C_i)  (3)

[0023] where P(C_i|C_i-n+1, . . . , C_i-1) is the class n-gram probability and P(w_i|C_i) is the class membership probability. However, phrases recognized by the same phrase-grammar can actually occur within different syntactic context but their similarity is based on their most likely lexical context. Considered in the context of Riccardi, et al. (1996) above, a context dependent training algorithm of the phrase class probabilities becomes available. In particular,

[0024] P(w_i|w_i-n+1, . . . , w_i-1)=P(C_i|C_i-n+1, . . . , C_i-1; S) P(w_i|C_i; S)  (5)

[0025] where S is the state of the language model assigned by Riccardi, et al. (1996). In particular, S=S(w_i-n+1, . . . , w_i-1, λ_f) is determined by a word history w_i-n+1, . . . , w_i-1and the phrase-grammar model λ_f.

[0026] For example, the method 1000 has acquired the conjunction cluster {but, and, because} that leads to generate phrases like “A T and T” or “A T because T”, the latter clearly an erroneous generalization. However, training context dependent probabilities in T may establish a stochastic separation between the correct and incorrect phrases: $\begin{array}{cc}\log \frac{\text{P(A T and T)}}{\text{P(A T because T)}}=5.7& \left(6\right)\end{array}$

[0027] Given a set of phrases containing terminal and non terminal symbols, the goal of large vocabulary stochastic language modeling for speech recognition and understanding is to assign a probability to all terminal symbol sequences. One of the main motivation for learning phrase-grammars is to decrease the local uncertainty in decoding spontaneous speech by embedding tightly constrained structure in the large vocabulary automaton. The language models trained on the acquired phrase-grammars give a slight improvement in perplexity (average measure of uncertainty). An other figure of merit in evaluating a stochastic language model is its local entropy $\left(-\sum _{i}P\left(s_i\left|s\right)\log P(s_i|s\right)\right)$

[0028] which is related to the notion of the branching factor of a language model state s.

[0029] The present invention provides advantages over known language building models. The order of processing permits classes to be used as a basis for phrase acquisition. The iterative nature of the processing permits phrases that are built upon classes to be clustered themselves into further classes. Thus, the present invention provides for complex linguistic models to be built from a corpus of text in a manner that is not achieved by either clustering processing or phrase acquisition processing per se.

[0030] FIG. 2 illustrates a clustering method 2000 according to an embodiment of the present invention. The method 2000 operates upon input text, a set of symbols from which the grammar model shall be constructed. While in a first iteration, the input text may comprise a set of words or phonemes, during subsequent iterations the input text also may include non-terminal symbols such as classes, phrases and other tokens. From the input text, the method identifies context symbols (Step 2010). Context symbols are those symbols in the input text that occur with the highest frequency. The method 2000 may cause a predetermined number of symbols (say, 50) that occur with the highest frequency to be identified as context symbols.

[0031] The method 2000 determines relationships that may exist between the context symbols and the remaining symbols, called “input symbols” herein, in the input text. For example, the method 2000 may determine how many times and in which positions an input symbol appears adjacent to a context symbol. Table 1 below illustrates relationships that may exist between certain exemplary input symbols and exemplary context symbols.

[0032] Each entry of the table, f_ijkrepresents, for a given input symbol i; how many times a context symbol C; and non-context symbol i; appears within a predetermined relationship. Thus f₁₁₁-F₁₁₁₄each represent the number of time the input symbol “Chicago” and the context symbol “to” appear within adjacencies of −2 symbols, −1 symbol, +1 symbol and +2 symbols respectively.

[0033] Based upon the frequencies, an N dimensional vector may be built for each input symbol (step 2020). The number of dimensions N of the frequency vector is a multiple of the total number of context symbols, the total number of input symbols and the total number of relations identified by the method 2000 The vector represents grammatical links that exist between the input symbols and the context symbols. Thus, each input symbol maps to an N dimensional frequency space. A representative frequency space is shown in FIG. 3 (N=3).

[0034] The method 2000 builds clusters of input symbols (Step 2030). According to the principles of the present invention, input symbols having the same lexical significance should possess similar vectors in the frequency space. Thus, it is expected that city names will exhibit frequency characteristics that are similar to each other but different from other input symbols having a different lexical significance. They will be included in a cluster (say, cluster 10, FIG. 3). So, too, with colors. They will be included in another cluster (say, cluster 20). Where symbols exhibit similar frequency significance, they are included within a single cluster.

[0035] As is known, a cluster may be represented in an N-dimensional frequency space by a centroid coordinate and a radius indicating the volume of the cluster. The radius indicates the “compactness” of the elements within a cluster. Where a cluster has a small radius, it indicates that the elements therein exhibit a very close relationship to each other in the frequency space. A larger radius indicates less similarities between elements in the frequency space.

[0036] The similarity between two symbols may be measured using the Manhattan distance metric between their feature vectors. Manhattan distance is based on the sum of the absolute value of the differences among the vector's coordinates. Alternatively, Euclidean and maximum metrics may be used to measure distances. Experimentally, the Manhattan distance metric was shown to provide better results than the Euclidean or maximum distance metrics.

[0037] Step 2030 may be applied recursively to grow clusters from clusters. That is, when two clusters are located close to one another in the N dimensional space, the method 2000 may enclose them in a single cluster having its own centroid and radius. The method 2000 determines a distance between two clusters by determining the distance between their centroids using one of the metrics discussed above with respect to the vectors of input symbols. Thus, the Manhattan, Euclidean and maximum distance metrics may be used.

[0038] A hierarchical “cluster tree” is grown representing a hierarchy of the clusters. At one node in the tree, the centroid and radius of a first cluster is stored. Two branches extend from the node to other nodes where the centroids and radii of subsumed clusters are stored. Thus, the tree structure maintains the centroid and radius of every cluster built according to Step 2030. Step 2030 recurs until a single, all encompassing cluster encloses all clusters and input symbols. This cluster is termed the “root cluster” because stored as the root node of the cluster tree. An exemplary cluster tree is shown in FIG. 4.

[0039] As will be appreciated, the root cluster N13 has a radius large enough to enclose all clusters and input symbols. The root cluster, therefore, possesses very little lexical significance. By contrast, “leaf clusters,” those provided at the ends of branches in the cluster tree, possess very strong lexical significance.

[0040] At Step 2040, the method 2000 cuts the cluster tree along a predetermined line in the tree structure. The cutting line separates large clusters from smaller clusters. The large clusters are discarded. What remains are smaller clusters, those with greater lexical significance.

[0041] The cutting line determines the number of clusters that will remain. One may use the median of the distances between clusters merged at the successive stages as a basis for the cutting line and prune the cluster tree at the point where cluster distances exceed this median value. Clusters are defined by the structure of the tree above the cutoff point.

[0042] Finally, the method 2000 ranks the remaining clusters (Step 2050). The lexical significance of a particular cluster is measured by its compactness value. The compactness value of a cluster simply may be its radius or an average distance of the members of the cluster from the centroid of the cluster. Thus, the tighter clusters exhibiting greater lexical significance will occur first in the ranked list of clusters and those exhibiting lesser lexical significance will occur later in the list. The list of clusters obtained from Step 2050 is a grammatical model of the input text.

[0043] The method 2000 is general in that it can be used to either cluster “tokens” at any lexical level. For example, it may be applied to symbols and/or phrases. Table 2 illustrates the result of clustering symbols and Table 3 illustrates the result of clustering phrases as performed on an experimental set of training data taken from the How May I Help You? Training corpus disclosed in Gorin, et al., “How May I Help You?,” vol. 23, Speech Communication, pp. 113-127 (1997). Other lexical granularities (syllables, phonemes) also may be used.

[0044] Adjacency of symbols is but one relationship that the method 2000 may be applied to recognize from a corpus. More generally, however, the method 2000 may be used to recognize predetermined relationships among tokens of the corpus. For example, the method 2000 can be configured to recognize symbols that appear together in the same sentences or symbols that appear within predetermined positional relationships with punctuation. Taken even further, the method 2000 may be configured to recognize predetermined grammatical constructs of language, such as subjects and/or objects of verbs. Each of these latter examples of relationships may require that the method be pre-configured to recognize the grammatical constructs.

[0045] Several embodiments of the present invention are specifically illustrated and described herein. However, it will be appreciated that modifications and variations of the present invention are covered by the above teachings and within the purview of the appended claims without departing from the spirit and intended scope of the invention.