Banzhaf random forests: cooperative game theory based random forests with consistency. (English) Zbl 1440.62345
Summary: Random forests algorithms have been widely used in many classification and regression applications. However, the theory of random forests lags far behind their applications. In this paper, we propose a novel random forests classification algorithm based on cooperative game theory. The Banzhaf power index is employed to evaluate the power of each feature by traversing possible feature coalitions. Hence, we call the proposed algorithm Banzhaf random forests (BRFs). Unlike the previously used information gain ratio, which only measures the power of each feature for classification and pays less attention to the intrinsic structure of the feature variables, the Banzhaf power index can measure the importance of each feature by computing the dependency among the group of features. More importantly, we have proved the consistency of BRFs, which narrows the gap between the theory and applications of random forests. Extensive experiments on several UCI benchmark data sets and three real world applications show that BRFs perform significantly better than existing consistent random forests on classification accuracy, and better than or at least comparable with Breiman’s random forests, support vector machines (SVMs) and \(k\)-nearest neighbors (KNNs) classifiers.
MSC:
| 62M45 | Neural nets and related approaches to inference from stochastic processes |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 91A12 | Cooperative games |
References:
| [1] | Amit, Y.; Geman, D., Shape quantization and recognition with randomized trees, Neural Computation, 9, 7, 1545-1588 (1997) |
| [2] | Amozegar, M.; Khorasani, K., An ensemble of dynamic neural network identifiers for fault detection and isolation of gas turbine engines, Neural Networks, 76, 106-121 (2016) |
| [3] | Ayerdi, B.; Grana, M., Hybrid extreme rotation forest, Neural Networks, 52, 33-42 (2014) · Zbl 1308.68089 |
| [4] | Banzhaf III, J. F., Weighted voting doesn’t work: A mathematical analysis, Rutgers Law Review, 19, 317-343 (1964) |
| [5] | Biau, G., Analysis of a random forests model, Journal of Machine Learning Research (JMLR), 13, 1, 1063-1095 (2012) · Zbl 1283.62127 |
| [6] | Biau, G.; Devroye, L.; Lugosi, G., Consistency of random forests and other averaging classifiers, Journal of Machine Learning Research (JMLR), 9, 2015-2033 (2008) · Zbl 1225.62081 |
| [7] | Bosch, A.; Zisserman, A.; Muoz, X., Image classification using random forests and ferns, (IEEE conference on computer vision (2007), IEEE), 1-8 |
| [8] | Breiman, L., Bagging predictors, Machine Learning, 24, 2, 123-140 (1996) · Zbl 0858.68080 |
| [9] | Breiman, L., Random forests, Machine Learning, 45, 1, 5-32 (2001) · Zbl 1007.68152 |
| [10] | Breiman, L. (2004). Consistency for a simple model of random forests. Technical report 670.; Breiman, L. (2004). Consistency for a simple model of random forests. Technical report 670. |
| [11] | Breiman, L., Friedman, J., Stone, C. J., & Olshen, R. A. (1984). Classification and regression trees; Breiman, L., Friedman, J., Stone, C. J., & Olshen, R. A. (1984). Classification and regression trees · Zbl 0541.62042 |
| [12] | Bulo, S. R.; Kontschieder, P., Neural decision forests for semantic image labelling, (Computer vision and pattern recognition (2014)), 81-88 |
| [13] | Chalkiadakis, G.; Elkind, E.; Wooldridge, M., Computational aspects of cooperative game theory, Synthesis Lectures on Artificial Intelligence and Machine Learning, 5, 6, 1-168 (2011) |
| [14] | Chang, C. C.; Lin, C. J., LIBSVM: a library for support vector machines, ACM Transactions on Intelligent Systems and Technology, 2, 3, 389-396 (2007) |
| [15] | Cormen, T.; Leiserson, C.; Rivest, R.; Stein, C., Introduction to algorithms (2009), The MIT Press · Zbl 1187.68679 |
| [16] | Criminisi, A., & Shotton, J. (2013). Decision forests for computer vision and medical image analysis; Criminisi, A., & Shotton, J. (2013). Decision forests for computer vision and medical image analysis |
| [17] | Criminisi, A.; Shotton, J.; Konukoglu, E., Decision forests: A unified framework for classification, regression, density estimation, manifold learning and semi-supervised learning, Foundations and Trends in Computer Graphics and Vision, 7, 81-227 (2012) · Zbl 1243.68235 |
| [18] | Cutler, D. R.; Edwards Jr., T. C.; Beard, K. H.; Cutler, A.; Hess, K. T.; Gibson, J.; Lawler, J. J., Random forests for classification in ecology, Ecology, 88, 11, 2783-2792 (2007) |
| [19] | Demsar, J., Statistical comparisons of classifiers over multiple data sets, Journal of Machine Learning Research (JMLR), 7, 1, 1-30 (2006) · Zbl 1222.68184 |
| [20] | Denil, M.; Matheson, D.; De Freitas, N., Narrowing the gap: random forests in theory and in practice, (International conference on machine learning (2013)), 665-673 |
| [21] | Denil, M.; Matheson, D.; de Freitas, N., Consistency of online random forests, (International conference on machine learning (2013)), 1256-1264 |
| [22] | Dietterich, T. G., An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization, Machine Learning, 40, 2, 139-157 (2000) |
| [23] | Dollar, P.; Zitnick, C. L., Fast edge detection using structured forests, IEEE Transactions on Pattern Analysis and Machine Intelligence, 37, 1, 1558-1570 (2014) |
| [24] | Feltkamp, V., Alternative axiomatic characterizations of the Shapley and Banzhaf values, International Journal of Game Theory, 24, 2, 179-186 (1995) · Zbl 0838.90146 |
| [25] | Friedman, J. H., Greedy function approximation: a gradient boosting machine, Annals of Statistics, 1189-1232 (2001) · Zbl 1043.62034 |
| [26] | Fung, W. K.; Liu, Y. H., Adaptive categorization of ART networks in robot behavior learning using game-theoretic formulation, Neural Networks, 16, 10, 1403 (2003) |
| [27] | Geurts, P.; Ernst, D.; Wehenkel, L., Extremely randomized trees, Machine Learning, 63, 1, 3-42 (2006) · Zbl 1110.68124 |
| [28] | Goodfellow, I. J.; Pouget-Abadie, J.; Mirza, M.; Xu, B.; Warde-Farley, D.; Ozair, S.; Courville, A.; Bengio, Y., Generative adversarial networks, Advances in Neural Information Processing Systems, 3, 2672-2680 (2014) |
| [29] | Györfi, L., Devroye, L., & Lugosi, G. (1996). A probabilistic theory of pattern recognition; Györfi, L., Devroye, L., & Lugosi, G. (1996). A probabilistic theory of pattern recognition · Zbl 0853.68150 |
| [30] | Hallman, S.; Fowlkes, C. C., Oriented edge forests for boundary detection, (IEEE conference on computer vision and pattern recognition (2015)), 1732-1740 |
| [31] | He, X.; Yu, J.; Huang, T.; Li, C.; Li, C., Neural network for solving nash equilibrium problem in application of multiuser power control, Neural Networks, 57, 9, 73-78 (2014) · Zbl 1325.90102 |
| [32] | Ho, T. K., The random subspace method for constructing decision forests, IEEE Transactions on Pattern Analysis and Machine Intelligence, 20, 8, 832-844 (1998) |
| [33] | Ishwaran, H.; Kogalur, U. B., Consistency of random survival forests, Statistics & Probability Letters, 80, 13, 1056-1064 (2010) · Zbl 1190.62177 |
| [34] | Kim, J.; Jang, G. J.; Lee, M., Fast learning method for convolutional neural networks using extreme learning machine and its application to lane detection, Neural Networks, 87, 109-121 (2016) |
| [35] | Mcquoid, M. R.J., Neural ensembles: Simultaneous recognition of multiple 2-D visual objects, Neural Networks, 6, 7, 907-917 (1993) |
| [36] | Meinshausen, N., Quantile regression forests, Journal of Machine Learning Research (JMLR), 7, 983-999 (2006) · Zbl 1222.68262 |
| [37] | Pavel, M. S.; Schulz, H.; Behnke, S., Object class segmentation of RGB-D video using recurrent convolutional neural networks, Neural Networks, 88, 105-113 (2017) |
| [38] | Prasad, A. M.; Iverson, L. R.; Liaw, A., Newer classification and regression tree techniques: bagging and random forests for ecological prediction, Ecosystems, 9, 2, 181-199 (2006) |
| [39] | Ristin, M.; Guillaumin, M.; Gall, J.; Van Gool, L., Incremental learning of random forests for large-scale image classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, 38, 3, 490-503 (2016) |
| [40] | Roy, A.; Todorovic, S., Monocular depth estimation using neural regression forest, (Computer vision and pattern recognition (2016)), 5506-5514 |
| [41] | Saad, W.; Han, Z.; Debbah, M.; Hjorungnes, A., Coalitional game theory for communication networks, Signal Processing Magazine IEEE, 26, 5, 77-97 (2009) |
| [42] | Salzberg, S. L., C4.5: programs for machine learning by J. Ross Quinlan. Morgan kaufmann Publishers, Inc., 1993, Machine Learning, 16, 3, 235-240 (1994) |
| [43] | Scardapane, S.; Di, L. P., A framework for parallel and distributed training of neural networks, Neural Networks, 91, 42-54 (2017) · Zbl 1434.68523 |
| [44] | Shotton, J.; Johnson, M.; Cipolla, R., Semantic texton forests for image categorization and segmentation, (IEEE conference on computer vision and pattern recognition (2008), IEEE), 1-8 |
| [45] | Shotton, J.; Sharp, T.; Kipman, A.; Fitzgibbon, A.; Finocchio, M.; Blake, A.; Cook, M.; Moore, R., Real-time human pose recognition in parts from single depth images, Communications of the ACM, 56, 1, 116-124 (2013) |
| [46] | Svetnik, V.; Liaw, A.; Tong, C.; Culberson, J. C.; Sheridan, R. P.; Feuston, B. P., Random forest: a classification and regression tool for compound classification and qsar modeling, Journal of Chemical Information and Computer Sciences, 43, 6, 1947-1958 (2003) |
| [47] | Yin, P.; Criminisi, A.; Winn, J.; Essa, M. S., Tree-based classifiers for bilayer video segmentation, (IEEE conference on computer vision and pattern recognition (2007), IEEE), 18-23 |
| [48] | Zhang, L.; Suganthan, P. N., Random forests with ensemble of feature spaces, Pattern Recognition, 47, 10, 3429-3437 (2014) |
| [49] | Zikic, D.; Glocker, B.; Criminisi, A., Atlas encoding by randomized forests for efficient label propagation, (Medical image computing and computer-assisted intervention (2013), Springer), 66-73 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
