Method of developing a classifier using adaboost-over-genetic programming

• US 20080126275A1
• Filed: 09/27/2006
• Published: 05/29/2008
• Est. Priority Date: 09/27/2006
• Status: Abandoned Application

• Current Assignee: Delphi Technologies, Inc. (BorgWarner Incorporated)
• Original Assignee: Delphi Technologies, Inc. (BorgWarner Incorporated)
• Inventors: Crnojevic, Vladimir S., Schubert, Peter J., Kisacanin, Branislav
• Application Number:
  US11/528,087
• Publication Number:
  US 20080126275A1
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G08B 21/06 indicating a condition of sleep, e.g. anti-dozing alarms

Abstract

An iterative process involving both genetic programming and adaptive boosting is used to develop a classification algorithm using a series of training examples. A genetic programming process is embedded within an adaptive boosting loop to develop a strong classifier based on combination of genetically produced classifiers.

Claims

1. A method of developing a classification algorithm based on classification training examples, each training example including training input data and a desired classification label, the method comprising the steps of:

(a) performing a genetic programming (GP) process in which a prescribed number of GP classification programs are formed and evolved over a prescribed number of generations, and the classification error of each GP classification program is evaluated with respect to the training examples;

(b) saving the GP classification program whose classification outputs most closely agree with the desired classification labels;

(c) repeating steps (a) and (b) to form a set of saved GP classification programs; and

(d) forming a classification algorithm for classifying non-training input data based on the saved GP classification programs and an output combination function, where the non-training input data is applied to each of the saved GP classification programs, and their classification outputs are combined by the output combination function to determine an overall classification of the non-training input data.

2. The method of claim 1, including the steps of:

applying the training input data of each classification training example to the classification algorithm to determine an overall classification for each training example; and

repeating steps (a) and (b) until the overall classifications determined for the training examples agree with the respective desired classification labels.

3. The method of claim 1, where the GP process includes determining a classification fitness of the GP classification programs, and the method includes the steps of:

establishing a weight for each classification training example;

using the established weights to determine the classification error of the GP classification programs in step (a);

determining a classification error of the GP classification program saved in step (b); and

updating the established weights for the classification training examples based on the determined classification error in a manner to give increased weight to classification training examples that were incorrectly classified by the GP classification program saved in step (b).

4. The method of claim 1 wherein:

the output combination function of step (d) includes a weight for each of the saved GP classification programs, such weights being applied to the classification outputs of respective saved GP classification programs; and

the weight for each saved GP classification program is determined based on a classification error of that saved GP classification program to give increased emphasis to saved GP classification programs whose classification outputs most closely agree with the desired classification labels.

5. A method of developing a classification algorithm based on classification training examples, each training example including training input data and a desired classification label, the method comprising the steps of:

(a) performing a genetic programming (GP) process in which a prescribed number of GP classification programs are formed and evolved over a prescribed number of generations, and the classification error of each GP classification program is evaluated with respect to the training examples;

(b) saving the GP classification program whose determined classification error is lowest;

(c) applying the training input data of each classification training example to each saved GP classification program to form classification outputs, combining the classification outputs to determine an overall classification of each classification training example, and computing a performance metric based on a comparison of the overall classifications with the desired classification labels;

(d) repeating steps (a), (b) and (c) to form and save additional GP classification programs until the performance metric reaches or exceeds a threshold; and

(e) forming a classification algorithm for classifying non-training input data based on the saved GP classification programs and an output combination function, where the non-training input data is applied to each of the saved GP classification programs, and their classification outputs are combined by the output combination function to determine an overall classification of the non-training input data.