Patent US6456993B1 successfully refreshed from Google Patents.
US6456993B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Alternating tree-based classifiers and methods for learning them
Assignee: AT&T Inc
•
Filing: 1999-12-28
•
Granted: 2002-09-24
•
Expires: 2019-12-28
Abstract
Abstract This invention provides methods and systems for classification of data instances using tree-based classifiers. Tree-based classifiers are first built according to a particular structure using a technique known as “boosting” wherein simple rules are successively added to the tree-based classifier until the unit tree-based classifier exhibits satisfactory error performance. The resulting classifier can then accurately classify an instance of data submitted to it and the classifier can optionally provide a measure of confidence for the classification result produced by the tree-based classifier.
Inventors
- 👤 Yoav Freund
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:55
CPC Classifications
G; G06; G06N; G06N3/00; G06N3/02; G06N3/08; G06N3/082; G06F; G06F18/00; G06F18/20; G06F18/24; G06F18/243; G06F18/24323
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
114 words
A method for building a general alternating decision tree classifier for classifying instances of data, comprising: determining a root prediction node; adding an initial rule having a decision node, a first prediction node and a second prediction node to the root prediction node using a boosting technique to form a general alternating decision tree classifier, the boosting technique being a technique for combining rules to form a more complex rule; and adding another rule having another decision node, another first prediction node and another second prediction node to one of the root prediction node and any existing prediction node of the general alternating decision tree classifier for forming the general alternating decision tree classifier.
Claim 2
Independent Claim
114 words
A method for building a general alternating decision tree classifier for classifying instances of data, comprising: determining a root prediction node; adding an initial rule having a decision node, a first prediction node and a second prediction node to the root prediction node using a boosting technique to form a general alternating decision tree classifier, the boosting technique being a technique for combining rules to form a more complex rule; and adding another rule having another decision node, another first prediction node and another second prediction node to one of the root prediction node and any existing prediction node of the general alternating decision tree classifier for forming the general alternating decision tree classifier.
Claim 3
Dependent Claim
51 words
The method of claim 1 , further comprising: testing the general alternating decision tree to determine an error condition; determining the error condition is satisfactory; and repeating then steps of adding another rule, testing the general alternating decision tree and determining the error condition if the error condition is not satisfactory.
Claim 4
Dependent Claim
33 words
The method of claim 1 , wherein the step of adding another a rule includes adding a rule to a prediction node having at least one preexisting rule appended to the prediction node.
Claim 5
Independent Claim
88 words
A apparatus for building a general alternating decision tree classifier comprising: a root prediction node device that determines a root prediction node of the general alternating decision tree classifier; a rule adding device that adds one or more rules, each rule having a decision node, a first prediction node and a second prediction node, wherein each rule is added to one of the root prediction node and a prediction node of another rule on the general alternating decision tree classifier for forming the general alternating decision tree classifier.
Claim 6
Independent Claim
88 words
A apparatus for building a general alternating decision tree classifier comprising: a root prediction node device that determines a root prediction node of the general alternating decision tree classifier; a rule adding device that adds one or more rules, each rule having a decision node, a first prediction node and a second prediction node, wherein each rule is added to one of the root prediction node and a prediction node of another rule on the general alternating decision tree classifier for forming the general alternating decision tree classifier.
Claim 7
Dependent Claim
23 words
The apparatus of claim 4 , further comprising a testing device that determines an error criteria of the general alternating decision tree classifier.
Claim 8
Dependent Claim
30 words
The apparatus of claim 4 , wherein the rule adding device uses a boosting technique, the boosting technique being a technique for combining rules to form a more complex rule.
Claim 9
Dependent Claim
30 words
The apparatus of claim 4 , wherein the rule adding device can add a rule to a prediction node having at least one preexisting rule appended to the prediction node.
Claim 10
Dependent Claim
117 words
A classifying method in a general alternating decision tree with a root prediction node and a plurality of rules, wherein each rule has a decision node, a first prediction node and a second prediction node and wherein the root prediction node and each of the first prediction nodes and the second prediction nodes has a prediction value, comprising: mapping at least one path in the general alternating decision tree using at least one element of a data instance and at least one rule of the plurality of rules; adding the prediction values of the prediction nodes along each path mapped to produce a sum; and classifying the data instance based on the sum of the prediction values.
Claim 11
Dependent Claim
117 words
A classifying method in a general alternating decision tree with a root prediction node and a plurality of rules, wherein each rule has a decision node, a first prediction node and a second prediction node and wherein the root prediction node and each of the first prediction nodes and the second prediction nodes has a prediction value, comprising: mapping at least one path in the general alternating decision tree using at least one element of a data instance and at least one rule of the plurality of rules; adding the prediction values of the prediction nodes along each path mapped to produce a sum; and classifying the data instance based on the sum of the prediction values.
Claim 12
Dependent Claim
17 words
The method of claim 8 , wherein the step of mapping includes mapping a plurality of paths.
Claim 13
Dependent Claim
94 words
A general alternating decision tree classifier for classifying instances of data, comprising: a root prediction node; a first rule with a decision node, a first prediction node and a second prediction node, wherein the decision node to the first rule is connected to the first prediction node; and a second rule with a decision node, a first prediction node and a second prediction node, wherein the decision node to the second rule is attached to one of the first prediction node of the first rule and the second prediction node of the first rule.
Claim 14
Dependent Claim
94 words
A general alternating decision tree classifier for classifying instances of data, comprising: a root prediction node; a first rule with a decision node, a first prediction node and a second prediction node, wherein the decision node to the first rule is connected to the first prediction node; and a second rule with a decision node, a first prediction node and a second prediction node, wherein the decision node to the second rule is attached to one of the first prediction node of the first rule and the second prediction node of the first rule.
Claim 15
Dependent Claim
43 words
The classifier of claim 10 , further comprising a third rule with a decision node, a first prediction node and a second prediction node, wherein the decision node of the third rule is attached to the first prediction node of the first rule.
Claim 16
Dependent Claim
39 words
The classifier according to claim 11 , further comprising a fourth rule with a decision node, a first prediction node and a second prediction node, wherein the decision node to the fourth rule is connected to the root node.
References Cited (Backward Citations)
US4719571A
Cited
US5806056A
Cited
US6321217B1
Cited
US5819247A
Cited
US6230151B1
Cited
US6260042B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-09-23 | 2006-03-25 | 2006-09-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-09-23 | 2010-03-25 | 2010-09-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-09-23 | 2014-03-25 | 2014-09-24 | $7700.00 | Window Closed / Lapsed |