Learner for resource constrained devices

• US 20070106785A1
• Filed: 03/28/2006
• Published: 05/10/2007
• Est. Priority Date: 11/09/2005
• Status: Active Grant

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Tegic Communications, Inc. (Microsoft Corporation)
• Inventors: Tandon, Gaurav
• Granted Patent: US 8,504,606 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

Methods, apparatuses, and articles for registering votes to predict an attribute value for a received instance are described herein. In one embodiment, the registering is performed in a weighted manner based at least on a weight and predicted target values associated with at least one of one or more rules whose antecedent has been met. The meeting of the antecedent is determined based at least on one or more attributes values of one or more other attributes of the received instance. Further, determining whether the predicted target value for which votes are registered correctly predicted the attribute value of the received instance is performed. The associated weight of the rule is adjusted accordingly, for instance, by incrementing the weight if the predicted target value correctly predicted the attribute value of the received instance, and by decrementing the weight if the predicted target value incorrectly predicted the attribute value of the received instance.

Claims

1. A method comprising:

registering one or more votes to predict a value for an attribute of a received instance, the registering being performed in a weighted manner based at least in part on a weight and predicted target values associated with at least one of one or more rules whose antecedent has been determined to have been met, the meeting of the antecedent having been determined based at least in part on one or more attributes values of one or more other attributes of the received instance;

determining whether the predicted target value for which one or more votes are registered correctly predicted the attribute value of the received instance; and

adjusting the associated weight of the rule, incrementing the weight if the predicted target value for which the one or more votes are registered correctly predicted the attribute value of the received instance, and decrementing the weight if the predicted target value for which the one or more votes are registered incorrectly predicted the attribute value of the received instance.

2. The method of claim 1, wherein the one or more rules are variable length rules.

3. The method of claim 1, further comprising generating the one or more rules by randomly selecting matching attribute values of one or more instances, the one or more instances randomly chosen based on matching target values.

4. The method of claim 3, further comprising assigning each of the one or more rules a weight, and each of the one or more rules are initially assigned the same weight.

5. The method of claim 3, further comprising updating the one or more rules based on one or more additional instances.

6. The method of claim 1, wherein registering the one or more votes comprises registering a number of votes equal to the weight of each of the one or more rules, and the one or more votes of each rule are registered for a most frequent target value of each rule.

7. The method of claim 1, wherein registering the one or more votes comprises registering a number of votes equal to the weight of each of the one or more rules, and the one or more votes of each rule are registered for each of one or more target values of each rule, each vote for each target value equal to the weight of each rule multiplied by a fractional frequency of that target value.

8. The method of claim 1, further comprising predicting the value for the attribute of the received instance based on an aggregation of the votes registered, and the predicted value is the same as a target value that received the highest plurality of votes.

9. The method of claim 1, further comprising predicting a plurality of values for the attribute of the received instance based on an aggregation of the votes registered, and the predicted plurality of values includes a plurality of target values receiving the highest pluralities of votes, and a size of the plurality of target values corresponds to a threshold.

10. The method of claim 1, wherein determining whether the predicted target value for which one or more votes are registered correctly predicted the attribute value of the received instance comprises presenting the predicted value to a user, and facilitating the user in selecting the predicted value or in entering a different value.

11. The method of claim 1, further comprising eliminating one of the one or more rules if the weight of the rule has decreased below a threshold metric.

12. An apparatus comprising:

a processor; and

a computing engine coupled to the processor and adapted to

register one or more votes to predict a value for an attribute of a received instance, the registering being performed in a weighted manner based at least in part on a weight and predicted target values associated with at least one of one or more rules whose antecedent has been determined to have been met, the meeting of the antecedent having been determined based at least in part on one or more attributes values of one or more other attributes of the received instance;

determine whether the predicted target value for which one or more votes are registered correctly predicted the attribute value of the received instance; and

adjust the associated weight of the rule, incrementing the weight if the predicted target value for which the one or more votes are registered correctly predicted the attribute value of the received instance, and decrementing the weight if the predicted target value for which the one or more votes are registered incorrectly predicted the attribute value of the received instance.

13. The apparatus of claim 12, wherein the one or more rules are variable length rules.

14. The apparatus of claim 12, wherein the computing engine is further adapted to generate the one or more rules by randomly selecting matching attribute values of one or more instances, the one or more instances randomly chosen based on matching target values.

15. The apparatus of claim 12, wherein the computing engine is further adapted to register the one or more votes, and the registering comprises registering a number of votes equal to a weight of each of the one or more rules.

16. The apparatus of claim 12, wherein the computing engine is further adapted to predict the value for the attribute of the received instance based on an aggregation of the votes registered, and the predicted value is the same as a target value that received the highest plurality of votes.

17. The method of claim 12, wherein the computing engine is further adapted to predict a plurality of values for the attribute of the received instance based on an aggregation of the votes registered, and the predicted plurality of values includes a plurality of target values receiving the highest pluralities of votes, and a size of the plurality of target values corresponds to a threshold metric.

18. The apparatus of claim 12, wherein the computing engine is further adapted to eliminate one of the one or more rules if the weight of the rule has decreased below a threshold metric.

19. An article of manufacture comprising:

a storage medium having a plurality of programming instructions stored therein, the plurality of programming instructions adapted to program an apparatus to enable the apparatus to

register one or more votes to predict a value for an attribute of a received instance, the registering being performed in a weighted manner based at least in part on a weight and predicted target values associated with at least one of one or more rules whose antecedent has been determined to have been met, the meeting of the antecedent having been determined based at least in part on one or more attributes values of one or more other attributes of the received instance;

determine whether the predicted target value for which one or more votes are registered correctly predicted the attribute value of the received instance; and

adjust the associated weight of the rule, incrementing the weight if the predicted target value for which the one or more votes are registered correctly predicted the attribute value of the received instance, and decrementing the weight if the predicted target value for which the one or more votes are registered incorrectly predicted the attribute value of the received instance.

20. The article of claim 19, wherein the one or more rules are variable length rules.

21. The article of claim 19, wherein the plurality of programming instructions are further adapted to generate the one or more rules by randomly selecting matching attribute values of one or more instances, the one or more instances randomly chosen based on matching target values.

22. The article of claim 19, wherein the plurality of programming instructions are further adapted to predict the value for the attribute of the received instance based on an aggregation of the votes registered, and the predicted value is the same as a target value that received the highest plurality of votes.

23. The article of claim 19, wherein the plurality of programming instructions are further adapted to predict a plurality of values for the attribute of the received instance based on an aggregation of the votes registered, and the predicted plurality of values includes a plurality of target values receiving the highest pluralities of votes, and a size of the plurality of target values corresponds to a threshold metric.

24. The article of claim 19, wherein the plurality of programming instructions are further adapted to eliminate one of the one or more rules if the weight of the rule has decreased below a threshold metric.