Method of autonomous machine learning

• US 5,781,698 A
• Filed: 10/31/1995
• Issued: 07/14/1998
• Est. Priority Date: 10/31/1995
• Status: Expired due to Term

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Veloso, Manuela, Teller, Astro (Eric)
• Primary Examiner(s): Hafiz, Tariq R.
• Application Number:
  US08/551,154
• Time in Patent Office: 987 Days
• Field of Search: 395/13, 395/50-51, 395/64, 395/900
• US Class Current: 706/13
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A classifier for signal classification based on a plurality of classification signals can be generated in three phases: a training phase, an orchestration phase, and a final classifier phase. In the training phase, genetic programming techniques are used to evolve a population of classification programs to produce a series of groups within the population, each of which is the best able to classify one type of input signal from all other signals. In the orchestration phase, the best programs from each group are selected and placed in a hierarchy of systems, wherein each system contains the best programs that are able to classify one type of input signal from all other signals. Default weights are assigned to each system and each program within a system. Training signals are input into the selected programs, output values for each program and system are generated, and the weights associated with the programs and systems are adjusted. The final classifier is the final hierarchy of systems of selected programs used for the classification of signals with unknown labels. The genetic programming techniques used in the training phase can also be applied to populations of computer programs other than signal classification programs such as operator programs.

Claims

1. A method of generating a classifier for signal classification based on a plurality of classification programs, comprising the steps of:

(a) operating on a plurality of C types of input signals, each having a known label, with a plurality of classification programs from a population of classification programs to produce a plurality of output values classifying said C types of input signals;

(b) measuring errors in said plurality of output values relative to said known labels;

(c) distributing said plurality of classification programs among C groups where each of said C groups is the best able to classify one of the C types of input signals from other of the C types of input signals;

(d) placing said distributed classification programs into a new population of classification programs in accordance with a first predetermined function;

(e) modifying certain of said plurality of classification programs in said new population;

(f) repeating steps (a) through (e) for a predetermined number of iterations based on predetermined criteria;

(g) selecting those programs from each group that are the best able to classify said input signals associated with said group from all other input signals for inclusion in a hierarchy of C systems, default weights being assigned to each of said selected programs and each of the C systems;

(h) operating on an input signal having a known label with said selected programs to produce a plurality of output values;

(i) determining an output value for each of said C systems by combining the output values from said selected programs within each of said C systems according to a second predetermined function of said output values and the weights of said selected programs;

(j) determining a signal classification output value by combining each of said output values from each of said C systems according to a third predetermined function of said output values and the weights of said C systems;

(k) measuring errors in the output values of said selected programs and said output values of said C systems relative to said known label;

(l) adjusting the weights assigned to each of said selected programs and each of said systems in accordance with the errors relative to said known labels; and

(m) repeating steps (h) through (l) for a number of iterations based on predetermined criteria to generate a classifier.

2. The method of claim 1 wherein said step (c) of distributing said plurality of classification programs includes the steps of:

(i) ranking each classification program according to its ability to discriminate an input signal from all other input signals;

(ii) assigning the classification program having the highest rank corresponding to said input signal to the group corresponding to said input signal; and

(iii) repeating steps (i) and (ii) until all of the classification programs are assigned to one of said C groups.

3. The method of claim 1 wherein said step (d) of placing said plurality of classification programs in a new population of classification programs includes the steps of:

(i) ranking each classification program according to its ability to discriminate an input signal from all other input signals; and

(ii) determining the number of each of said plurality of classification programs in the new population as a function of each program'"'"'s rank within its group.

4. The method of claim 1 wherein said step (d) of placing said plurality of classification programs in a new population of classification programs includes the steps of:

(i) ranking each classification program according to its ability to discriminate an input signal from all other input signals; and

(ii) determining the number of each of said plurality of classification programs in the new population as a function of each program'"'"'s rank within a set comprising a number of classification programs.

5. The method of claim 1 wherein said step (e) of modifying certain of said plurality of classification programs includes the steps of:

(i) selecting a plurality of classification programs from the population of classification programs; and

(ii) adding a fragment to said plurality of classification programs.

6. The method of claim 1 wherein said step (e) of modifying certain of said plurality of classification programs includes the steps of:

(i) selecting a plurality of classification programs from the population of classification programs; and

(ii) removing a fragment from said plurality of classification programs.

7. The method of claim 1 wherein said step (e) of modifying certain of said plurality of classification programs includes the steps of:

(i) selecting a plurality of classification programs from the population of classification programs; and

(ii) removing portions from each of said selected classification programs and replacing said portions with other portions of classification programs.

8. The method of claim 1 wherein said step (e) of modifying certain of said plurality of classification programs includes the steps of:

(i) selecting a plurality of classification programs from the population of classification programs; and

(ii) operating on said selected classification programs with operator programs to produce modified programs.

9. The method of claim 8 additionally comprising the steps of:

(i) measuring fitness of the operator programs as a function of the errors in the output values generated by the selected classification programs and the modified programs relative to the known labels; and

(ii) placing the operator programs in a new population of operator programs in accordance with a predetermined operator function, wherein the number of each of the operator programs in the new population is a function of its fitness.

10. The method of claim 9 additionally comprising the step of modifying certain of the operator programs.

11. The method of claim 1 wherein said step (i) of determining an output value for each of said C systems includes the step of determining an output value for each of said C systems by combining the output values from said selected programs within each of said C systems according to a weighted average of said output values using the weights of said selected programs.

12. The method of claim 1 wherein said step (j) of determining a signal classification output value includes the step of determining the signal classification output value to be a value assigned to the type of signal corresponding to one of the C systems, wherein the product of the output value and weight of said one of the C systems is greater than the product of the output value and weight of every other of the C systems.

13. The method of claim 1 wherein said step (j) of determining a signal classification output value includes the steps of:

(i) storing output values of each of the C systems in response to input signals having known labels of each of the C types of input signals;

(ii) for each of the C systems, determining a first value comprising the difference between the output value of the system and the output value of said system in response to one of the input signals of one of the C types of input signals;

(iii) determining a second value comprising the sum of all of the first values for each of the C systems corresponding to one of the input signals of one of the C types of input signals;

(iv) repeating steps (ii) and (iii) for each of the C types of input signals;

(v) determining the signal classification output value to be a value assigned to one of the C types of input signal, wherein the second value corresponding to said one of the C types of input signal is less than the second values corresponding to every other of the C types of input signal.

14. A method of classifying signals using the method of claim 1 to generate a classifier for signal classification based on a plurality of classification programs, and additionally comprising the steps of:

(i) operating on an input signal with the selected programs comprising the classifier to produce a plurality of output values;

(ii) determining the output value for each of the C systems by combining the output values from said selected programs within each of said C systems according to the second predetermined function of said output values and the weights of said selected programs; and

(iii) determining the signal classification output value by combining each of said output values from each of said C systems according to the third predetermined function of said output values and the weights of said C systems.

15. The method of claim 14 additionally comprising the step of determining a confidence value by combining each of said output values from each of said C systems according to a fourth predetermined function of said output values and the weights of said C systems.

16. A method of generating a population of operator programs to optimize the functioning of computer programs on which said operator programs operate, comprising the steps of:

(a) operating on a plurality of input computer programs, said input computer programs being from a population of computer programs, with a plurality of operator programs, said operator programs being from a population of operator programs, to produce a plurality of output computer programs;

(b) measuring fitness values of said input and output computer programs as a function of the errors in output values of said input and output computer programs relative to known reference values;

(c) measuring fitness values for each of said operator programs, said fitness values being a function of said fitness values of said input and output computer programs;

(d) placing said operator programs in a new population of operator programs in accordance with a predetermined function, wherein the number of each operator program in the new population is related to its fitness value;

(e) modifying certain of said operator programs; and

(f) repeating steps (a) through (e) for a number of iterations based on predetermined criteria.

17. The method of claim 16 wherein said step (a) of operating on a plurality of input computer programs with a plurality of operator programs includes the step of operating on a plurality of operator programs with a plurality of other operator programs.

18. The method of claim 16 wherein said step (a) of operating on a plurality of input computer programs with a plurality of operator programs includes the step of adding a fragment to one of the input computer programs such that pointers from the fragment are directed to random locations in said input computer program.

19. The method of claim 16 wherein said step (a) of operating on a plurality of input computer programs with a plurality of operator programs includes the step of removing a fragment of one of the input computer programs such that pointers directed to said fragment are redirected to locations to which pointers in said fragment had been directed.

20. The method of claim 16 wherein said step (a) of operating on a plurality of input computer programs with a plurality of operator programs includes the step of replacing a fragment from one of the input computer programs with another fragment.

21. The method of claim 16 wherein said step (a) of operating on a plurality of input computer programs with a plurality of operator programs includes the step of operating on two input computer programs with one of said operator programs by:

(i) removing a fragment from each of the input computer programs; and

(ii) placing the fragment removed from one of the input computer programs into the other of the input computer programs such that pointers from the fragment are directed to random locations in said other program.

22. The method of claim 21 wherein said step (i) of removing a fragment from each of the input computer programs includes the step of removing a randomly-chosen fragment from each of the plurality of input computer programs.

23. The method of claim 21 wherein said step (i) of removing a fragment from each of the input computer programs includes the step of removing a fragment from each of the plurality of input computer programs wherein said fragment is chosen by other operator programs within the population containing said plurality of operator programs.

24. The method of claim 21 wherein said step (i) of removing a fragment from each of the input computer programs includes the step of removing a fragment from each of the plurality of input computer programs wherein said fragment is chosen by other operator programs within a separate population of operator programs.

25. The method of claim 16 wherein said step (c) of measuring fitness values for each of said operator programs includes the steps of:

(i) measuring a first sum of the fitness value of the output computer program and the maximum possible fitness value for said output computer program;

(ii) measuring a second sum of the fitness value of the input computer program and the maximum possible fitness value for said input computer program;

(iii) determining a ratio of the first sum to the second sum minus one (1); and

(iv) summing all of said ratios.

26. The method of claim 16 wherein said step (c) of measuring fitness values for each of said operator programs includes the step of measuring the percentage of time that the fitness value of one of the output computer programs generated by one of the operator programs is greater than the fitness values of the input computer program it replaces in the population of computer programs.

27. An apparatus for generating a classifier for signal classification based on a plurality of classification programs, comprising:

(a) means for operating on a plurality of C types of input signals, each having a known label, with a plurality of classification programs from a population of classification programs to produce a plurality of output values classifying said C types of input signals;

(b) means for measuring errors in said plurality of output values relative to said known labels;

(c) means for distributing said plurality of classification programs among C groups where each of said C groups is the best able to classify one of the C types of input signals from other of the C types of input signals;

(d) means for placing said distributed classification programs into a new population of classification programs in accordance with a first predetermined function;

(e) means for modifying certain of said plurality of classification programs in said new population;

(f) means for selecting those programs from each group that are the best able to classify said input signals associated with said group from all other input signals for inclusion in a hierarchy of C systems, default weights being assigned to each of said selected programs and each of the C systems;

(g) means for operating on an input signal having a known label with said selected programs to produce a plurality of output values;

(h) means for determining an output value for each of said C systems by combining the output values from said selected programs within each of said C systems according to a second predetermined function of said output values and the weights of said selected programs;

(i) means for determining a signal classification output value by combining each of said output values from each of said C systems according to a third predetermined function of said output values and the weights of said C systems;

(j) means for measuring errors in the output values of said selected programs and said output values of said C systems relative to said known label; and

(k) means for adjusting the weights assigned to each of said selected programs and each of said systems in accordance with the errors relative to said known labels.

28. An apparatus for generating a population of operator programs to optimize the functioning of computer programs on which said operator programs operate, comprising:

(a) means for operating on a plurality of input computer programs within a population of computer programs with a plurality of operator programs from a population of operator programs to produce a plurality of output computer programs;

(b) means for measuring fitness values of said input and output computer programs as a function of the errors in output values of said input and output computer programs relative to known reference values;

(c) means for measuring fitness values for each of said operator programs, said fitness values being a function of said fitness values of said input and output computer programs;

(d) means for placing said operator programs in a new population of operator programs in accordance with a predetermined function, wherein the number of each operator program in the new population is related to its fitness value; and

(e) means for modifying certain of said operator programs.