Saving Evaluation Time for the Decision Function in Boosting: Representation and Reordering Base Learner

Peng Sun, Jie Zhou
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):933-941, 2013.

Abstract

For a well trained Boosting classifier, we are interested in how to save the testing time, i.e., to make the decision without evaluating all the base learners. To address this problem, in previous work the base learners are sequentially calculated and early stopping is allowed if the decision function has been confident enough to output its value. In such a chain structure, the order of base learners is critical: better order can lead to less evaluation time. In this paper, we present a novel method for ordering. We base our discussion on the data structure representing Boosting’s decision function. Viewing the decision function a boolean expression, we propose a Binary Valued Tree for its representation. As a secondary contribution, such a representation unifies the work by previous researchers and helps devise new representation. Also, its connection to Binary Decision Diagram(BDD) is discussed.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-sun13, title = {Saving Evaluation Time for the Decision Function in Boosting: Representation and Reordering Base Learner}, author = {Sun, Peng and Zhou, Jie}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {933--941}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/sun13.pdf}, url = {https://proceedings.mlr.press/v28/sun13.html}, abstract = {For a well trained Boosting classifier, we are interested in how to save the testing time, i.e., to make the decision without evaluating all the base learners. To address this problem, in previous work the base learners are sequentially calculated and early stopping is allowed if the decision function has been confident enough to output its value. In such a chain structure, the order of base learners is critical: better order can lead to less evaluation time. In this paper, we present a novel method for ordering. We base our discussion on the data structure representing Boosting’s decision function. Viewing the decision function a boolean expression, we propose a Binary Valued Tree for its representation. As a secondary contribution, such a representation unifies the work by previous researchers and helps devise new representation. Also, its connection to Binary Decision Diagram(BDD) is discussed.} }
Endnote
%0 Conference Paper %T Saving Evaluation Time for the Decision Function in Boosting: Representation and Reordering Base Learner %A Peng Sun %A Jie Zhou %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-sun13 %I PMLR %P 933--941 %U https://proceedings.mlr.press/v28/sun13.html %V 28 %N 3 %X For a well trained Boosting classifier, we are interested in how to save the testing time, i.e., to make the decision without evaluating all the base learners. To address this problem, in previous work the base learners are sequentially calculated and early stopping is allowed if the decision function has been confident enough to output its value. In such a chain structure, the order of base learners is critical: better order can lead to less evaluation time. In this paper, we present a novel method for ordering. We base our discussion on the data structure representing Boosting’s decision function. Viewing the decision function a boolean expression, we propose a Binary Valued Tree for its representation. As a secondary contribution, such a representation unifies the work by previous researchers and helps devise new representation. Also, its connection to Binary Decision Diagram(BDD) is discussed.
RIS
TY - CPAPER TI - Saving Evaluation Time for the Decision Function in Boosting: Representation and Reordering Base Learner AU - Peng Sun AU - Jie Zhou BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-sun13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 933 EP - 941 L1 - http://proceedings.mlr.press/v28/sun13.pdf UR - https://proceedings.mlr.press/v28/sun13.html AB - For a well trained Boosting classifier, we are interested in how to save the testing time, i.e., to make the decision without evaluating all the base learners. To address this problem, in previous work the base learners are sequentially calculated and early stopping is allowed if the decision function has been confident enough to output its value. In such a chain structure, the order of base learners is critical: better order can lead to less evaluation time. In this paper, we present a novel method for ordering. We base our discussion on the data structure representing Boosting’s decision function. Viewing the decision function a boolean expression, we propose a Binary Valued Tree for its representation. As a secondary contribution, such a representation unifies the work by previous researchers and helps devise new representation. Also, its connection to Binary Decision Diagram(BDD) is discussed. ER -
APA
Sun, P. & Zhou, J.. (2013). Saving Evaluation Time for the Decision Function in Boosting: Representation and Reordering Base Learner. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):933-941 Available from https://proceedings.mlr.press/v28/sun13.html.

Related Material