Design and construction of a binary-tree system for language modelling

• US 4,852,173 A
• Filed: 10/29/1987
• Issued: 07/25/1989
• Est. Priority Date: 10/29/1987
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bahl, Lalit R., deSouza, Peter V., Brown, Peter F., Mercer, Robert L.
• Primary Examiner(s): Salce, Patrick R.
• Assistant Examiner(s): VOELTZ, EMANUEL T
• Application Number:
  US07/114,892
• Time in Patent Office: 635 Days
• Field of Search: 381/41-43, 364/513, 364/513.5, 382/37-40
• US Class Current: 704/240
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G10L 15/00 Speech recognition G10L17/00 takes precedence

Abstract

In order to determine a next event based upon available data, a binary decision tree is constructed having true or false questions at each node and a probability distribution of the unknown next event based upon available data at each leaf. Starting at the root of the tree, the construction process proceeds from node-to-node towards a leaf by answering the question at each node encountered and following either the true or false path depending upon the answer. The questions are phrased in terms of the available data and are designed to provide as much information as possible about the next unknown event. The process is particularly useful in speech recognition when the next word to be spoken is determined on the basis of the previously spoken words.

Claims

1. In a data processing system for determining an unknown event Y, given input data X(1), X(2) . . . X(N), a method of constructing a binary decision tree comprising the steps of:

defining at least one decision node whereat each decision node has two paths each extending to a succeeding node;

determining a set S(i) for each input datum X(i) by starting with an empty set and adding or deleting one datum item at a time to said set S(i) whenever the changed set reduces the entropy of the unknown event Y;

structuring a decision question at each decision node based upon the input data and in the form "is X(i) a member of set S(i)"; and

creating two additional paths if the entropy of the unknown event Y is reduced, or terminating at the decision node if the entropy is not reduced, whereby each terminated decision node is a leaf of the binary decision tree.

2. A data processing system as set forth in claim 1, wherein training data is applied to the tree to calculate the conditional probabilities at each of said nodes in the form P'"'"'(Y|x_i ε

S(i)) and P"(Y|x_i ε

S(i)).

3. A data processing system as set forth in claim 2 wherein checking data is applied to the tree to calculate a smoothed conditional probability at each of said nodes in the form Q'"'"'(Y|X(i)ε

S(i)) and Q"(Y|X(i)ε

S(i)).

4. A data processing system as set forth in claim 3, wherein a value of w is determined which minimizes the entropy of the checking data according to the formula H_c =min H(Y|δ

(i), Q'"'"', Q").

5. A data processing system as set forth in claim 4 wherein training data is applied to the tree for determining the relative frequency, Pn(Y|T), for each node.

6. A data processing system as set forth in claim 5, wherein checking data is applied to the tree for determining the relative frequency, Pn(Y|C), for each node.

7. A data processing system as set forth in claim 6, wherein the smoothed probability using training data at each node is computed according to the equation Q_n (Y|T)=wP_n (Y|T)+(1l -w) Q_n'"'"' (Y|T), where n'"'"' is the father node of the respective node.

8. A data processing system as set forth in claim 7, wherein the smoothed probability using checking data at each node is computed according to the equation

9. A data processing system as set forth in claim 8, wherein the smoothed probability distribution for each leaf is calculated according to the formula:

space="preserve" listing-type="equation">R.sub.1 (Y)=wQ.sub.1 (Y|T)+(1-w)Q.sub.1 (Y|C).

10. A data processing system as set forth in claim 1, wherein said creating two additional paths is performed if the entropy of unknown event Y is reduced by a predetermined threshold value.

11. A data processing system as set forth in claim 1, wherein said set S(i) is added to or deleted from by a plurality of data items whenever the changed set reduces the entropy of the unknown event Y.

12. In a data processing system, the method of constructing a binary-tree sytem for language modelling in speech recognition in which given the N last spoken words, the next word Y is to be determined, comprising the steps of:

defining at least on decision node whereat each decision node has two paths extending to a succeeding node;

determining a set S(i) of next words for each of the last i words of the N last spoken words by starting with an empty set and adding or deleting one word at a time to said set S(i) whenever the changed set reduces the entropy of the unknown next word Y;

structuring a decision question at each decision node in the form "is the ith last spoken word in the set S(i)";

creating two additional paths if the entropy of the unknown next word is reduced, or terminating at the decision node if the entropy is not reduced;

determining for each terminated node the smoothed probability of an unknown next word Y; and

selecting the next word from the probabilities at each terminated node.