Classification method and apparatus based on boosting and pruning of multiple classifiers
First Claim
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 Dn,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 Bx,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 Bx,y for each particular data set y including a terminal booster;
(e) training one of each plurality X,y of booster classifiers Bx,y with a particular data portion Dn,y, resulting in a plurality of rules;
(f) testing the booster classifier Bx,y, trained in step (e) utilizing another particular data portion, Dn,y, said testing resulting in correctly classified data and mistakenly classified data;
(g) creating a particular training data set Tx,y corresponding to each particular data set y, the contents of which are defined by;
where M(Bx,y (•
)) identifies data upon which mistakes were made by the associated booster classifier Bx,y, C(Bx,y (•
)) identifies data for which correct classifications were made by the associated booster classifier Bx,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 Bx,y from which correct examples are used for the particular training set Tx,y;
(h) training one of the plurality X,y of booster classifiers Bx,y associated with each particular data set y with the particular training data set Tx,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 Bx,y trained in step (h) utilizing another particular data portion Dn,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 Bx,y have been trained and tested for each particular data set y;
(k) testing the X−
1 booster classifiers Bx,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 Bx,y, said testing resulting in correctly classified data and mistakenly classified data;
(l) creating a residual training set TR,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 TR,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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
32 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 Dn,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 Bx,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 Bx,y for each particular data set y including a terminal booster;
(e) training one of each plurality X,y of booster classifiers Bx,y with a particular data portion Dn,y, resulting in a plurality of rules;
(f) testing the booster classifier Bx,y, trained in step (e) utilizing another particular data portion, Dn,y, said testing resulting in correctly classified data and mistakenly classified data;
(g) creating a particular training data set Tx,y corresponding to each particular data set y, the contents of which are defined by;
where M(Bx,y (•
)) identifies data upon which mistakes were made by the associated booster classifier Bx,y, C(Bx,y (•
)) identifies data for which correct classifications were made by the associated booster classifier Bx,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 Bx,y from which correct examples are used for the particular training set Tx,y;
(h) training one of the plurality X,y of booster classifiers Bx,y associated with each particular data set y with the particular training data set Tx,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 Bx,y trained in step (h) utilizing another particular data portion Dn,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 Bx,y have been trained and tested for each particular data set y;
(k) testing the X−
1 booster classifiers Bx,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 Bx,y, said testing resulting in correctly classified data and mistakenly classified data;
(l) creating a residual training set TR,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 TR,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.- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
(n) pruning the rules of all of the booster classifiers Bx,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 Bx;
(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 Bx,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 Bx,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 By, (o) pruning the rules of all of the inter-booster pruned classifiers By 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 Bx,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 Dn,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 Bx,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 Bx,y for each particular data set y including a terminal booster;
(e) training one of each plurality X,y of booster classifiers Bx,y with a particular data portion Dn,y resulting in a plurality of rules;
(f) testing the booster classifier Bx,y trained in step (e) utilizing another particular data portion Dx,y, said testing resulting in correctly classified data and mistakenly classified data;
(g) creating a particular training data set Tx,y corresponding to each particular data set y, the contents of which are defined by;
where M(Bx,y (•
)) identifies data upon which mistakes were made by the associated booster classifier Bx,y, C(Bx,y (•
)) identifies data for which correct classifications were made by the associated booster classifier Bx,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 Bx,y from which correct examples are used for the particular training set Tx,y;
(h) training one of the plurality X,y of booster classifiers Bx,y associated with each particular data set y with the particular training data set Tx,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 Bx,y trained in step (h) utilizing another particular data portion Dn,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 Bx,y have been trained and tested for each particular data set y;
(k) testing the X−
1 booster classifiers Bx,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 Bx,y said testing resulting in correctly classified data and mistakenly classified data;
(l) creating a residual training set TR,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 TR,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.- View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
(n) pruning the rules of all of the booster classifiers Bx,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 Bx;
(o) pruning the rules of all of the intra-booster pruned classifiers Bx 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 Bx,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 Bx,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 By, (o) pruning the rules of all of the inter-booster pruned classifiers By 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 Bx,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.
Specification