Patent EP0313975A2 successfully refreshed from Google Patents.
EP0313975A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Design and construction of a binary-tree system for language modelling
Assignee: International Business Machines Corp
•
Filing: 1988-10-19
•
Granted: —
•
Expires: 2008-10-19
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 Rai Bahl
- 👤 Peter Fitzhugh Brown
- 👤 Peter Vincent Desouza
- 👤 Robert Leroy Mercer
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-10 02:05
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/18; G06N; G06N5/00; G06N5/02; G06N5/022; G10; G10L; G10L15/00; G06N20/00
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
152 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
152 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
39 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
38 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
36 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 = in H(Y|δ(i,Si), 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
29 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
46 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) + (1-w) Q n′ (Y|T) where n′ is the father node of the respective node.
Claim 9
Dependent Claim
46 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 n (Y|C)=wP n (Y|C) + (1-w) Q n′ (Y|C), where n′ is the father node of the respective node.
Claim 10
Dependent Claim
31 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₁(Y) = wQ₁(Y|T) + (1-w) Q₁ (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
184 words
Method of constructing a binary-tree system according to anyone of the claims 1 to 11 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 one 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)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.