Learner for resource constrained devices

• US 8,504,606 B2
• Filed: 03/28/2006
• Issued: 08/06/2013
• 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
• Primary Examiner(s): Ashraf, Waseem
• Application Number:
  US11/392,186
• Publication Number:
  US 20070106785A1
• Time in Patent Office: 2,688 Days
• Field of Search: 709/202
• US Class Current: 709/202
• 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 for performing a learning process in an application for a mobile phone device comprising:

creating, by a server, an instance set that includes one or more entries from a database of entries stored in a memory of said server;

wherein said entries comprise a plurality of attributes with corresponding attribute values, and the one or more entries included in the instance set include a value for a target field;

randomly selecting one or more entries from the instance set by the server, wherein the number of entries chosen is less than number of entries in the instance set;

generating, by the server, one or more rules of variable length by randomly selecting attribute values corresponding to one or more field attributes of the randomly selected one or more entries;

wherein said rules are constructed using at least one field attribute as a logical antecedent and at least one additional field attribute as a logical consequent;

storing the generated rules in a rule set;

retrieving the rule set by the mobile phone device;

receiving at least one additional entry by the mobile phone device;

registering one or more votes to predict an unknown field attribute value for said at least one additional received entry, the registering being performed in a weighted manner based at least in part on a weight and predicted target field values associated with a logical consequent of at least one of the one or more selected rules from said rule set whose logical antecedent has been determined to have been met, the logical meeting of the antecedent having been determined based at least in part on one or more field attributes values of the at least one additional received entry by said mobile phone;

determining whether the predicted target field value, for which one or more votes are registered, correctly predicted the field attribute value of the received entry by said mobile phone; and

adjusting the associated weight of the rule, incrementing the weight if the predicted target field value for which the one or more votes are registered correctly predicted the field attribute value of the received entry, and decrementing the weight if the predicted target field value for which the one or more votes are registered incorrectly predicted the field attribute value of the received entry by said mobile phone.

2. The method of claim 1, further comprising assigning, by said mobile phone, each of the one or more rules a weight, and wherein each of the one or more rules are initially assigned the same weight.

3. The method of claim 1, further comprising updating the one or more rules based on one or more additional entries, by the server.

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

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

6. The method of claim 1, further comprising predicting, by a computer processor, the field value for the attribute of the received entry based on an aggregation of the votes registered, and wherein the predicted field value is the same as a target field value that received the highest plurality of votes.

7. The method of claim 1, further comprising predicting, by said mobile phone, a plurality of field values for the attribute of the received entry based on an aggregation of the votes registered, and wherein the predicted plurality of field values includes a plurality of target field values receiving the highest pluralities of votes, and wherein a size of the plurality of target field values corresponds to a threshold.

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

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

10. A mobile phone configured to learn rules regarding field attribute values and configured to use learned rules to predict field attribute values comprising:

a hardware processor; and

a computing engine coupled to the hardware processor and adapted to communicate with a server;

wherein the server creates an instance set that includes one or more entries from a database of entries stored in a memory of the server;

wherein said entries comprise a plurality of attributes with corresponding attribute values, and the one or more entries included in the instance set include a value for a target field;

wherein the server randomly selects one or more entries from the instance set, wherein the number of entries chosen is less than number of entries in the instance set;

generate one or more rules of variable length by randomly selecting attribute values corresponding to one or more field attributes of the randomly selected one or more entries, wherein said rules are constructed using at least one field attribute as a logical antecedent and at least one additional field attribute as a logical consequent;

retrieving the rule set by the mobile phone device from the server;

receive at least one additional entry at the mobile device;

register one or more votes to predict an unknown field attribute value for said at least one additional received entry, the registering being performed in a weighted manner based at least in part on a weight and predicted target field values associated with a logical consequent of at least one of the one or more selected rules from said rule set whose logical antecedent has been determined to have been met, the logical meeting of the antecedent having been determined based at least in part on one or more attributes values of the at least one additional received entry;

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

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

11. The mobile phone of claim 10, 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.

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

13. The mobile phone of claim 10, wherein the computing engine is further adapted to predict a plurality of field values for the field attribute of the received entry based on an aggregation of the votes registered, and the predicted plurality of values includes a plurality of target field values receiving the highest pluralities of votes, and a size of the plurality of target field values corresponds to a threshold metric.

14. The mobile phone of claim 10, 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.