Classification method and apparatus based on boosting and pruning of multiple classifiers

• US 6,456,991 B1
• Filed: 09/01/1999
• Issued: 09/24/2002
• Est. Priority Date: 09/01/1999
• Status: Expired due to Fees

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Srinivasa, Narayan, Owechko, Yuri
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/388,858
• Time in Patent Office: 1,119 Days
• Field of Search: 706/20, 706/16, 706/25, 704/9
• US Class Current: 706/20
• CPC Class Codes: G06F 18/23211 with adaptive number of clusters
• CPC Class Codes: G06N 3/0409 Adaptive resonance theory [ART] networks
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/082 modifying the architecture, e.g. adding, deleting or silencing nodes or connections

Abstract

A boosting and pruning system and method for utilizing a plurality of neural networks, preferably those based on adaptive resonance theory (ART), in order to increase pattern classification accuracy is presented. The method utilizes a plurality of N randomly ordered copies of the input data, which is passed to a plurality of sets of booster networks. Each of the plurality of N randomly ordered copies of the input data is divided into a plurality of portions, preferably with an equal allocation of the data corresponding to each class for which recognition is desired. The plurality of portions is used to train the set of booster networks. The rules generated by the set of booster networks are then pruned in an intra-booster pruning step, which uses a pair-wise Fuzzy AND operation to determine rule overlap and to eliminate rules which are sufficiently similar. This process results in a set of intra-booster pruned booster networks. A similar pruning process is applied in an inter-booster pruning process, which eliminates rules from the intra-booster pruned networks with sufficient overlap. The final, derivative booster network captures the essence of the plurality of sets of booster networks and provides for higher classification accuracy than available using a single network.

Claims

1. A neural network classifier boosting and pruning method including the steps of:

(a) providing a set of training data having inputs with correct classifications corresponding to the inputs;

(b) ordering the set of training data into a plurality Y of differently ordered data sets, where Y is the total number of differently ordered data sets and y represents a particular one of the Y differently ordered data sets;

(c) dividing each of the Y differently ordered data sets into a set of N particular data portions D_n,y where N represents the total number of data portions into which the particular data set y was divided and n identifies a particular data portion among the N data portions derived from a particular data set y;

(d) associating a plurality X,y of booster classifiers B_x,y for each particular data set y, where X represents the total number of booster types associated with each particular data set y and x represents a particular booster type, the plurality X,y of booster classifiers B_x,y for each particular data set y including a terminal booster;

(e) training one of each plurality X,y of booster classifiers B_x,y with a particular data portion D_n,y, resulting in a plurality of rules;

(f) testing the booster classifier B_x,y, trained in step (e) utilizing another particular data portion, D_n,y, said testing resulting in correctly classified data and mistakenly classified data;

(g) creating a particular training data set T_x,y corresponding to each particular data set y, the contents of which are defined by;

$T_{x,y}=\left(w_{1,x,y}\right)<br><br>M<br><br>\left(B_{x,y}<br><br>\left(D_{x+1,y}\right)\right)+\left(w_{2,x,y}\right)<br><br>C<br><br>\left(B_{1,y}<br><br>\left(D_{1,y}\right)\right)+\underset{j=1}{\overset{x-1<br><br>\left(x-1><br><br>0\right)}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(w_{2+j,x,y}\right)<br><br>C<br><br>\left(B_{x-j+1,y}<br><br>\left(D_{x-j+1,y}\right)\right)$

 

where M(B_x,y (•

)) identifies data upon which mistakes were made by the associated booster classifier B_x,y, C(B_x,y (•

)) identifies data for which correct classifications were made by the associated booster classifier B_x,y, and w represents independently selectable apportionment factors which apportion the amount of mistakenly classified data and the amount of correctly classified data, and j is a summation index which ranges from 1 to x−

1 where x−

1>

0 and represents the total number booster classifiers B_x,y from which correct examples are used for the particular training set T_x,y;

(h) training one of the plurality X,y of booster classifiers B_x,y associated with each particular data set y with the particular training data set T_x,y created in step (g) which corresponds to the same particular data set y, resulting in a plurality of rules;

(i) testing the booster classifier B_x,y trained in step (h) utilizing another particular data portion D_n,y from the same particular data set y, said testing resulting in correctly classified data and mistakenly classified data;

(j) repeating steps (g) through (i) X−

3 additional times until a total of X−

1 booster classifiers B_x,y have been trained and tested for each particular data set y;

(k) testing the X−

1 booster classifiers B_x,y trained in steps (e) through (j) for each particular data set y utilizing the particular data portion y associated with each X−

1 booster classifiers B_x,y, said testing resulting in correctly classified data and mistakenly classified data;

(l) creating a residual training set T_R,y for each particular data set y including the mistakenly classified data resulting from step (k);

(m) training the terminal booster for each particular data set y utilizing the residual training set T_R,y created in step (l);

resulting in a plurality of rules for use in a classification apparatus for receiving data for classification and, based on the classficiation data, outputting classfications.

2. A neural network classifier boosting and pruning method as set forth in claim 1, further including the steps of:

(n) pruning the rules of all of the booster classifiers B_x,y of a particular booster type x by eliminating those rules which are sufficiently similar in an intra-booster pruning stage, and resulting in a series of intra-booster pruned classifiers B_x;

(o) pruning the rules of all of the intra-booster pruned classifiers Bby eliminating those rules which are sufficiently similar in an inter-booster pruning stage, resulting in a single residual booster B.

3. A neural network classifier boosting and pruning method as set forth in claim 2, wherein the intra-booster pruning step (n) and the inter-booster pruning step (o) utilize the operation,

4. A neural network classifier boosting and pruning apparatus created by the method of claim 2.

5. A neural network classifier boosting and pruning method as set forth in claim 3, wherein the user-chosen constant β

is independently selectable for the inter-booster pruning step (n) and the inter-booster pruning step (o).

6. A neural network classifier boosting and pruning apparatus created by the method of claim 3.

7. A neural network classifier boosting and pruning method as set forth in claim 5, wherein the booster classifiers B_x,y are M-PROBART neural networks.

8. A neural network classifier boosting and pruning apparatus created by the method of claim 5.

9. A classifier boosting and pruning apparatus created by the method of claim 7.

10. A neural network classifier boosting and pruning method as set forth in claim 1, further including the steps of:

(n) pruning the rules of all of the classifier boosters B_x,y for each particular data set y by eliminating those rules which are sufficiently similar in an inter-booster pruning stage, resulting in a series of inter-booster pruned classifiers B_y,

(o) pruning the rules of all of the inter-booster pruned classifiers B_y by eliminating those rules which are sufficiently similar in an intra-booster pruning stage, resulting in a single residual booster B.

11. A neural network classifier boosting and pruning method as set forth in claim 10, wherein the inter-booster pruning step (n) and the intra-booster pruning step (o) utilize the operation,

12. A neural network classifier boosting and pruning apparatus created by the method of claim 10.

13. A neural network classifier boosting and pruning method as set forth in claim 11, wherein the booster classifiers B_x,y are M-PROBART neural networks.

14. A neural network classifier boosting and pruning apparatus created by the method of claim 11.

15. A neural network classifier boosting and pruning apparatus created by the method of claim 13.

16. A neural network classifier boosting and pruning apparatus created by the method of claim 1.

17. A neural network classifier boosting and pruning method for position and recognition sensing and classification including the steps of:

(a) providing a set of training data having inputs with correct classifications corresponding to the inputs;

(b) ordering the set of training data into a plurality Y of differently ordered data sets, where Y is the total number of differently ordered data sets and y represents a particular one of the Y differently ordered data sets;

(c) dividing each of the Y differently ordered data sets into a set of N particular data portions D_n,y, where N represents the total number of data portions into which the particular data set y was divided and n identifies a particular data portion among the N data portions derived from a particular data set y;

(d) associating a plurality X,y of booster classifiers B_x,y for each particular data set y, where X represents the total number of booster types associated with each particular data set y and x represents a particular booster type, the plurality X,y of booster classifiers B_x,y for each particular data set y including a terminal booster;

(e) training one of each plurality X,y of booster classifiers B_x,y with a particular data portion D_n,y resulting in a plurality of rules;

(f) testing the booster classifier B_x,y trained in step (e) utilizing another particular data portion D_x,y, said testing resulting in correctly classified data and mistakenly classified data;

(g) creating a particular training data set T_x,y corresponding to each particular data set y, the contents of which are defined by;

$T_{x,y}=\left(w_{1,x,y}\right)<br><br>M<br><br>\left(B_{x,y}<br><br>\left(D_{x+1,y}\right)\right)+\left(w_{2,x,y}\right)<br><br>C<br><br>\left(B_{1,y}<br><br>\left(D_{1,y}\right)\right)+\underset{j=1}{\overset{x-1<br><br>\left(x-1><br><br>0\right)}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(w_{2+j,x,y}\right)<br><br>C<br><br>\left(B_{x-j+1,y}<br><br>\left(D_{x-j+1,y}\right)\right)$

 

where M(B_x,y (•

)) identifies data upon which mistakes were made by the associated booster classifier B_x,y, C(B_x,y (•

)) identifies data for which correct classifications were made by the associated booster classifier B_x,y, and w represents independently selectable apportionment factors which apportion the amount of mistakenly classified data and the amount of correctly classified data, and j is a summation index which ranges from 1 to x−

1 where x−

1>

0 and represents the total number booster classifiers B_x,y from which correct examples are used for the particular training set T_x,y;

(h) training one of the plurality X,y of booster classifiers B_x,y associated with each particular data set y with the particular training data set T_x,y created in step (g) which corresponds to the same particular data set y, resulting in a plurality of rules;

(i) testing the booster classifier B_x,y trained in step (h) utilizing another particular data portion D_n,y from the same particular data set y, said testing resulting in correctly classified data and mistakenly classified data;

(j) repeating steps (g) through (i) X−

3 additional times until a total of X−

1 booster classifiers B_x,y have been trained and tested for each particular data set y;

(k) testing the X−

1 booster classifiers B_x,y trained in steps (e) through (j) for each particular data set y utilizing the particular data portion y associated with each X−

1 booster classifiers B_x,y said testing resulting in correctly classified data and mistakenly classified data;

(l) creating a residual training set T_R,y for each particular data set y including the mistakenly classified data resulting from step (k);

(m) training the terminal booster for each particular data set y utilizing the residual training set T_R,y created in step (l);

resulting in a plurality of rules for receiving position and recognition related data and outputting highly accurate recognition and position sensing and classification information.

18. A neural network classifier boosting and pruning method as set forth in claim 17, further including the steps of:

(n) pruning the rules of all of the booster classifiers B_x,y of a particular booster type x by eliminating those rules which are sufficiently similar in an intrabooster pruning stage, and resulting in a series of intra-booster pruned classifiers B_x;

(o) pruning the rules of all of the intra-booster pruned classifiers B_x by eliminating those rules which are sufficiently similar in an inter-booster pruning stage, resulting in a single residual booster B.

19. A neural network classifier boosting and pruning method as set forth in claim 18, wherein the intra-booster pruning step (n) and the inter-booster pruning step (o) utilize the operation,

20. A neural network classifier boosting and pruning apparatus created by the method of claim 18, for use in highly accurate recognition and position sensing and classification of occupants in an automotive airbag system.

21. A neural network classifier boosting and pruning method as set forth in claim 19, wherein the user-chosen constant β

is independently selectable for the inter-booster pruning step (n) and the inter-booster pruning step (o).

22. A neural network classifier boosting and pruning apparatus created by the method of claim 19, for use in highly accurate recognition and position sensing and classification of occupants in an automotive airbag system.

23. A neural network classifier boosting and pruning method as set forth in claim 21, wherein the booster classifiers B_x,y are M-PROBART neural networks.

24. A neural network classifier boosting and pruning apparatus created by the method of claim 21, for use in highly accurate recognition and position sensing and classification of occupants in an automotive airbag system.

25. A neural network classifier boosting and pruning apparatus created by the method of claim 23, for use in highly accurate recognition and position sensing and classification of occupants in an automotive airbag system.

26. A neural network classifier boosting and pruning method as set forth in claim 17, further including the steps of:

(n) pruning the rules of all of the classifier boosters B_x,y for each particular data set y by eliminating those rules which are sufficiently similar in an interbooster pruning stage, resulting in a series of inter-booster pruned classifiers B_y,

(o) pruning the rules of all of the inter-booster pruned classifiers B_y by eliminating those rules which are sufficiently similar in an intra-booster pruning stage, resulting in a single residual booster B.

27. A neural network classifier boosting and pruning method as set forth in claim 26, wherein the inter-booster pruning step (n) and the intra-booster pruning step (o) utilize the operation,

28. A neural network classifier boosting and pruning apparatus created by the method of claim 26, for use in highly accurate recognition and position sensing and classification of occupants in an automotive airbag system.

29. A neural network classifier boosting and pruning method as set forth in claim 27, wherein the booster classifiers B_x,y are M-PROBART neural networks.

30. A neural network classifier boosting and pruning apparatus created by the method of claim 27, for use in highly accurate recognition and position sensing and classification of occupants in an automotive airbag system.

31. A neural network classifier boosting and pruning apparatus created by the method of claim 29, for use in highly accurate recognition and position sensing and classification of occupants in an automotive airbag system.

32. A neural network classifier boosting and pruning apparatus created by the method of claim 17, for use in highly accurate recognition and position sensing and classification of occupants in an automotive airbag system.