Capacity and Error Estimates for Boolean Classifiers with Limited Complexity
作者： Judea Pearl
DOI: 10.1109/TPAMI.1979.4766943
关键词:
摘要: This paper extends the notions of capacity and distribution-free error estimation to nonlinear Boolean classifiers on patterns with binary-valued features. We establish quantitative relationships between dimensionality feature vectors (d), combinational complexity decision rule (c), number samples in training set (n), classification performance resulting classifier. Our results state that discriminating is given by product dc, probability ambiguous generalization asymptotically (n/dc-1)-1 0(log d)/d) for large d, n=0(dc). In addition we show if a fraction ? misclassified then (?) subsequent satisfies P(|?-?| ?) m=<2.773 exp (dc-e2n/8) all distributions, regardless how classifier was discovered.
computer.org
sci-hub.se 参考文章(8)
Nicholas Pippenger, Information theory and the complexity of boolean functions Theory of Computing Systems \/ Mathematical Systems Theory. ,vol. 10, pp. 129- 167 ,(1976) , 10.1007/BF01683269
V. N. Vapnik, A. Ya. Chervonenkis, On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities Measures of Complexity. ,vol. 16, pp. 11- 30 ,(2015) , 10.1007/978-3-319-21852-6_3
L. Devroye, T. Wagner, A distribution-free performance bound in error estimation (Corresp.) IEEE Transactions on Information Theory. ,vol. 22, pp. 586- 587 ,(1976) , 10.1109/TIT.1976.1055604
G. Hughes, On the mean accuracy of statistical pattern recognizers IEEE Transactions on Information Theory. ,vol. 14, pp. 55- 63 ,(1968) , 10.1109/TIT.1968.1054102
Wassily Hoeffding, Probability Inequalities for sums of Bounded Random Variables Journal of the American Statistical Association. ,vol. 58, pp. 13- 30 ,(1963) , 10.1007/978-1-4612-0865-5_26
Jan M. Van Campenhout, On the Peaking of the Hughes Mean Recognition Accuracy: The Resolution of an Apparent Paradox IEEE Transactions on Systems, Man, and Cybernetics. ,vol. 8, pp. 390- 395 ,(1978) , 10.1109/TSMC.1978.4309980
B. Chandrasekaran, Anil K. Jain, Independence, Measurement Complexity, and Classification Performance IEEE Transactions on Systems, Man, and Cybernetics. ,vol. SMC-5, pp. 240- 244 ,(1975) , 10.1109/TSMC.1975.5408477
Thomas M. Cover, Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition IEEE Transactions on Electronic Computers. ,vol. EC-14, pp. 326- 334 ,(1965) , 10.1109/PGEC.1965.264137