US4852173A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Design and construction of a binary-tree system for language modelling
Assignee: International Business Machines Corp
•
Filing: 1987-10-29
•
Granted: 1989-07-25
•
Expires: 2007-10-29
Abstract
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.
Inventors
- 👤 Lalit R. Bahl
- 👤 Peter F. Brown
- 👤 Peter V. deSouza
- 👤 Robert L. Mercer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 03:51
CPC Classifications
G; G10; G10L; G10L15/00; G06; G06F; G06F17/00; G06F17/10; G06F17/18; G06N; G06N5/00; G06N5/02; G06N5/022; G06N20/00
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
156 words
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.
Claim 2
Dependent Claim
156 words
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.
Claim 3
Dependent Claim
38 words
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)).
Claim 4
Dependent Claim
35 words
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)).
Claim 5
Dependent Claim
35 words
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").
Claim 6
Dependent Claim
27 words
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.
Claim 7
Dependent Claim
27 words
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.
Claim 8
Dependent Claim
45 words
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.
Claim 9
Dependent Claim
40 words
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 Q.sub.n (Y|C)=wP.sub.n (Y|C)+(1-w)Q.sub.n' (Y|C), where n' is the father node of the respective node.
Claim 10
Dependent Claim
28 words
A data processing system as set forth in claim 8, wherein the smoothed probability distribution for each leaf is calculated according to the formula: R.sub.1 (Y)=wQ.sub.1 (Y|T)+(1-w)Q.sub.1 (Y|C).
Claim 11
Dependent Claim
32 words
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.
Claim 12
Dependent Claim
38 words
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.
Claim 13
Dependent Claim
181 words
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.
Claim 14
Dependent Claim
181 words
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.
References Cited (Backward Citations)
US3883847A
Cited
US3918047A
Cited
US4468728A
Cited
US4466060A
Cited
US4654875A
Cited
US4589142A
Cited
US4593367A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-07-24 | 1993-01-23 | 1993-07-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-07-24 | 1997-01-23 | 1997-07-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-07-24 | 2001-01-23 | 2001-07-25 | $7700.00 | Window Closed / Lapsed |