System and method for combining multiple learning agents to produce a prediction method

• US 6,449,603 B1
• Filed: 11/19/1998
• Issued: 09/10/2002
• Est. Priority Date: 05/23/1996
• Status: Expired due to Term

• Current Assignee: The United States of America, as represented by the Secretary, Department of Health and Human Services, The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: United States Department Of Health And Human Services (Government of the United States of America)
• Inventors: Hunter, Lawrence E.
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/180,998
• Time in Patent Office: 1,391 Days
• Field of Search: 706/15, 706/21
• US Class Current: 706/15
• CPC Class Codes: G06F 18/2111 by using evolutionary computational techniques, e.g. genetic algorithms
• CPC Class Codes: G06N 3/004 Artificial life, i.e. computing arrangements simulating life
• CPC Class Codes: G06N 5/043 Distributed expert systems; Blackboards

Abstract

System and method for improving the performance of learning agents such as neural networks, genetic algorithms and decision trees that derive prediction methods from a training set of data. In part of the method, a population of learning agents of different classes is trained on the data set, each agent producing in response a prediction method based on the agent'"'"'s input representation. Feature combinations are extracted from the prediction methods produced by the learning agents. The input representations of the learning agents are then modified by including therein a feature combination extracted from another learning agent. In another part of a method, the parameter values of the learning agents are changed to improve the accuracy of the prediction method. A fitness measure is determined for each learning agent based on the prediction method the agent produces. Parameter values of a learning agent are then selected based on the agent'"'"'s fitness measure. Variation is introduced into the selected parameter values, and another learning agent of the same class is defined using the varied parameter values. The learning agents are then again trained on the data set to cause a learning agent to produce a prediction method based on the derived feature combinations and varied parameter values.

Claims

1. A computer-implemented method of producing a computer-executable prediction method, the computer-implemented method comprising:

providing training data related to a problem for which a computer-executable prediction method is sought, the training data comprising multiple empirical observations represented by features with values and values for observed event outcomes associated with the feature values stored in a computer-readable medium;

providing at least two software-based computer-executable learning agents, the software-based computer-executable agents including initial input representations of the training data;

training the software-based computer-executable learning agents on the initial input representations of the training data, the software-based computer-executable agents producing in response to the data an initial population of computer-executable prediction methods based on the agents'"'"' initial input representations of the training data;

extracting one or more features from the initial population of computer-executable prediction methods produced by the learning agents for combination into one or more feature combinations;

modifying the input representation of at least one of the software-based computer-executable learning agents by including in the input representation at least one of the feature combinations originating from the prediction method of another software-based computer-executable learning agent; and

again training the software-based computer-executable learning agents on the modified input representations of the training data to cause the software-based computer-executable learning agents to produce at least one next generation computer-executable prediction method based on the modified agents'"'"' input representations, wherein the next generation computer-executable prediction method comprises a set of computer-executable instructions stored in a computer-readable medium and returns a result.

2. The method of claim 1 wherein the extracting comprises:

analyzing a prediction method to identify which features of an agent'"'"'s input representation are more important and less important to the prediction method; and

combining at least two more important of the features to produce a feature combination.

3. The method of claim 1 further comprising:

collecting feature combinations extracted from the prediction methods; and

determining a fitness measure for each of the collected feature combinations, wherein the modifying includes selecting a feature combination for an agent'"'"'s input representation based on the feature combination'"'"'s fitness measure.

4. The method of claim 3 wherein the determining a fitness measure for a feature combination comprises:

globally assigning a fitness value to each feature combination; and

combining the combination'"'"'s fitness value with a preference value to produce the fitness measure.

5. The method of claim 1 wherein the learning agents are of two different types.

6. The method of claim 1 wherein the learning agents are of the same type but have different parameter values.

7. The method of claim 1 wherein the learning agents have a same list of parameters but different parameter values, the method including:

determining a fitness measure for each learning agent based on the prediction method the agent produces;

selecting the parameter values of at least one of the learning agents based on the agent'"'"'s fitness measure;

introducing variation into the selected parameter values; and

defining another learning agent using the varied parameter values.

8. The method of claim 7 wherein determining a fitness measure comprises determining an accuracy of the prediction method and a completion time for the learning agent.

9. A computer-readable medium on which is stored a computer program comprising instructions which, when executed, perform the method of claim 1.

10. The method of claim 1 wherein the method is applied to the technical field of data mining.

11. The method of claim 1 wherein the method is applied to the technical field of weather forecasting.

12. The method of claim 1 wherein the method is applied to the technical field of data analysis.

13. The method of claim 1 wherein the software-based computer-executable learning agents are chosen from the following classes:

a neural network; and

a decision tree.

14. The method of claim 1 wherein the software-based computer-executable

learning agents are chosen from the following classes:

a neural network;

a decision tree;

a statistical/Bayesian inference; and

a genetic algorithm.

15. A computer-implemented method of producing a prediction method, the method comprising:

providing training data related to a problem for which a prediction method is sought, the training data represented by features with values stored in a computer-readable medium;

providing at least two learning agents having a same parameter list but different parameter values;

training the learning agents on the training data, each agent producing in response to the data a prediction method based on the agent'"'"'s parameter values;

determining a fitness measure for each learning agent based on the prediction method the agent produces;

selecting the parameter values of at least one of the learning agents based on the agent'"'"'s fitness measure;

introducing variation into the selected parameter values;

defining another learning agent using the varied parameter values; and

again training the learning agents on the training data to cause a learning agent to produce a prediction method based on the varied parameter values, wherein the prediction method comprises a set of computer-executable instructions stored in a computer-readable medium and returns a result.

16. A computer-implemented method of producing a prediction method, the method comprising the following steps:

providing training data related to a problem for which a prediction method is sought, the training data represented by features with values stored in a computer-readable medium;

providing a plurality of learning agents of which at least two have a same parameter list but different parameter values, the learning agents including input representations;

training the learning agents on the training data, each agent producing in response to the data a prediction method based on the agent'"'"'s parameter values and input representation;

determining a fitness measure for each learning agent based on the prediction method the agent produces;

selecting the parameter values of at least one of the learning agents based on the agent'"'"'s fitness measure;

introducing variation into the selected parameter values;

defining another learning agent using the varied parameter values;

extracting feature combinations from the prediction methods produced by the learning agents, wherein the extracting comprises combining at least two of the features;

modifying the input representation of a learning agent by including in the input representation a feature combination extracted from another learning agent; and

again training the learning agents on the training data to cause a learning agent to produce a prediction method based on the varied parameter set and the modified input representation, wherein the prediction method comprises a set of computer-executable instructions stored in a computer-readable medium and returns a result.

17. A computer-implemented system for producing a prediction method for a problem, comprising:

a training data set related to a problem for which a prediction method is sought, the training data set represented by features with values stored in a computer-readable medium;

at least two learning agents, the agents including input representations; and

at least one computer programmed for;

training the learning agents on the data set, each agent producing in response to the data a prediction method based on the agent'"'"'s input representation;

extracting feature combinations from the prediction methods produced by the learning agents, wherein the extracting comprises combining at least two of the features;

modifying the input representation of a learning agent by including in the input representation a feature combination extracted from another learning agent; and

again training the learning agents on the data set to cause a learning agent to produce a prediction method based on the agent'"'"'s modified input representation, wherein the prediction method comprises a set of computer-executable instructions stored in a computer-readable medium and returns a result.

18. The system of claim 17 wherein at least two learning agents have a same parameter list but different parameter values, and the computer is further programmed for:

training the learning agents on the data set, each agent producing in response to the data a prediction method based on the agent'"'"'s parameter values;

determining a fitness measure for each learning agent based on the prediction method the agent produces;

selecting the parameter values of a learning agent based on the agent'"'"'s fitness measure;

introducing variation into the selected parameter values;

defining another learning agent using the varied parameter values; and

again training the learning agents on the data set to cause a learning agent to produce a prediction method based on the varied parameter values, wherein the prediction method comprises a set of computer-executable instructions stored in a computer-readable medium.

19. A general purpose computer for producing a prediction method for a problem, the system comprising:

computer processor means for processing data;

storage means for storing data in a storage medium, wherein the stored data comprises training data related to a problem for which a prediction method is sought, the training data represented by features with values, and the stored data further comprises at least two learning agents, the learning agents including input representations;

first means for training the learning agents on the data set, at least two of the agents producing in response to the data a prediction method based on the agent'"'"'s input representation;

second means for extracting feature combinations from the prediction methods produced by the learning agents;

third means for modifying the input representation of a learning agent by including in the input representation a feature combination extracted from another learning agent; and

fourth means for again training the learning agents on the data set to cause a learning agent to produce a computer-executable prediction method based on the agent'"'"'s modified input representation.

20. A computer-readable medium comprising computer-executable instructions for performing at least the following:

for training data comprising a set of features and indicating a set of observations comprising values for the features and values indicating observations of results related to the feature values, training a plurality of software-based learning agents to generate a plurality of computer-executable functions, wherein the computer-executable functions provide predicted values given a set of values for at least a subset of the features;

selecting a subset of the features incorporated into a first of the computer-executable functions generated by a first software-based learning agent and combining the features into a feature combination;

based on the feature combination and the training data, generating modified training data comprising the feature combination and values for the feature combination; and

training the software-based learning agents on the modified training data to generate a plurality of second-generation computer-executable functions, wherein the second-generation computer-executable functions provide predicted values given a set of values for at least the feature combination;

wherein the features of the feature combination are extracted from the first computer-executable function originating from a first software-based learning agent and the feature combination is incorporated into training data from which a second software-based learning agent generates a second, second-generation, computer-executable function.

21. The computer-readable medium of claim 20 wherein the first and second software-based learning agents are of different classes.

22. The computer-readable medium of claim 20 wherein:

the first software-based learning agent is associated with a neural network; and

the second software-based learning agent is associated with a decision tree.