Abstract Diversity-based semi-supervised learning is the combination of semi-supervised learning and ensemble learning. It is a research focus in machine learning. However, its related theoretical analysis is insufficient, and the presence of distribution noise is not taken into account in these researches. In this paper, according to the characteristic of diversity-based semi-supervised learning, a hybrid classification and distribution (HCAD) noise is defined firstly. Then, probably approximately correct (PAC) analysis for diversity-based semi-supervised learning in the presence of HCAD noise and its application of the theorem are given. Finally, based on the voting margin, an upper bound is developed on the generalization error of multi-classifier systems with theoretic proofs in the presence of HCAD noise. The proposed theorems can be used to design diversity-based semi-supervised learning algorithms and evaluate their generalization ability, and they have a promising application prospect.
[1] d'Alche Buc F, Grandvalet Y, Ambroise C. Semisupervised Marginboost // Dietterich T G, Becker S, Ghahramani Z, eds. Advances in Neural Information Processing Systems. Cambridge, USA: MIT Press, 2001, 14: 553-560 [2] Chen K, Wang S H. Semi-supervised Learning via Regularized Boo- sting Working on Multiple Semi-supervised Assumptions. IEEE Trans on Pattern Analysis and Machine Intelligence, 2011, 33(1): 129-143 [3] Chen K, Wang S H. Regularized Boost for Semi-supervised Learning[EB/OL]. [2013-12-25]. http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2007_164.pdf [4] Blum A, Mitchell T. Combining Labeled and Unlabeled Data with Co-training // Proc of the 11th Annual Conference on Computational Learning Theory. Madison, USA, 1998: 92-100 [5] Jiang Z, Zhang S Y, Zeng J P. A Hybrid Generative/Discriminative Method for Semi-supervised Classification. Knowledge-Based Systems, 2013, 37: 137-145 [6] Brefeld U, Scheffer T. Co-EM Support Vector Learning // Proc of the 21st International Conference on Machine Learning. Banff, Ca-nada, 2004: 16-23 [7] Zhou Z H, Li M. Tri-training: Exploiting Unlabeled Data Using Three Classifiers. IEEE Trans on Knowledge and Data Engineering, 2005, 17(11): 1529-1541 [8] Dasgupta S, Littman M L, McAllester D. PAC Generalization Bou- nds for Co-training // Dietterich T G, Becker S, Ghahramani Z, eds. Advances in Neural Information Processing Systems. Cambridge, USA: The MIT Press, 2001, 14: 375-382 [9] Wang W, Zhou Z H. Analyzing Co-training Style Algorithms // Proc of the 18th European Conference on Machine Learning. Warsaw, Poland, 2007: 454-465 [10] Wang W, Zhou Z H. A New Analysis of Co-training // Proc of the 27th International Conference on Machine Learning. Haifa, Israel, 2010: 1135-1142 [11] Angluin D, Laird P. Learning from Noisy Examples. Machine Lea- rning, 1988, 2(4): 343-370 [12] Decatur S E. Statistical Queries and Faulty PAC Oracles // Proc of the 6th Annual ACM Conference on Computational Learning Theory. Santa Cruz, USA, 1993: 262-268 [13] Schapire R E, Freund Y, Bartlett P, et al. Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods. The Annals of Statistics, 1998, 26(5): 1651-1686 [14] Valiant L G. A Theory of the Learnable. Communications of the ACM, 1984, 27(11): 1134-1142 [15] Blum A, Kalai A, Wasserman H. Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model. Journal of the ACM, 2003, 50(4): 506-519 [16] Decatur S E. PAC Learning with Constant-Partition Classification Noise and Applications to Decision Tree Induction // Proc of the 14th International Conference on Machine Learning. Nashville, USA, 1997: 83-91 [17] Sauer N. On the Density of Families of Sets. Journal of Combinatorial Theory: Series A, 1972, 13(1): 145-147 [18] Ratsch G, Mika S, Schlkopf B, et al. Constructing Boosting Algorithms from SVMs: An Application to One-Class Classification. IEEE Trans on Pattern Analysis and Machine Intelligence, 2002, 24(9): 1184-1199
2014, Vol. 27 
