Information theoretic regularization for semi-supervised boosting

ABSTRACT

We present novel semi-supervised boosting algorithms that incrementally build linear combinations of weak classifiers through generic functional gradient descent using both labeled and unlabeled training data. Our approach is based on extending information regularization framework to boosting, bearing loss functions that combine log loss on labeled data with the information-theoretic measures to encode unlabeled data. Even though the information-theoretic regularization terms make the optimization non-convex, we propose simple sequential gradient descent optimization algorithms, and obtain impressively improved results on synthetic, benchmark and real world tasks over supervised boosting algorithms which use the labeled data alone and a state-of-the-art semi-supervised boosting algorithm.

REFERENCES

• 1: Kristin P. Bennett , Ayhan Demiriz , Richard Maclin, Exploiting unlabeled data in ensemble methods, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775090]
• 2: D. Bertsekas. Nonlinear Programming, 2nd Edition, Athena Scientific, 1999.
• 3: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 4: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 5: Leo Breiman, Prediction games and arcing algorithms, Neural Computation, v.11 n.7, p.1493-1517, Oct. 1, 1999 [doi>10.1162/089976699300016106]
• 6: V. Castelli and T. Cover. The relative value of labeled and unlabeled samples in pattern recognition with an unknown mixing parameter. IEEE Trans. on Information Theory, 42(6):2102--2117, 1996.
• 7: Gilles Celeux , Gérard Govaert, A Classification EM algorithm for clustering and two stochastic versions, Computational Statistics & Data Analysis, v.14 n.3, p.315-332, Oct. 1992 [doi>10.1016/0167-9473(92)90042-E]
• 8: O. Chapelle, B. Scholköpf and A. Zien. Semi-Supervised Learning, MIT Press, 2006.
• 9: K. Chen and S. Wang. Regularized boost for semi-supervised learning. Advances in Neural Information Processing Systems 20, 2007.
• 10: I. Cohen and F. Cozman. Risks of semi-supervised learning. Semi-Supervised Learning, O. Chapelle, B. Scholköpf and A. Zien,55--70, MIT Press, 2006.
• 11: Michael Collins , Robert E. Schapire , Yoram Singer, Logistic Regression, AdaBoost and Bregman Distances, Machine Learning, v.48 n.1-3, p.253-285, 2002 [doi>10.1023/A:1013912006537]
• 12: A. Corduneanu and T. Jaakkola. Data dependent regularization. Semi-Supervised Learning, O. Chapelle, B. Scholköpf and A. Zien, 163--182, MIT Press, 2006.
• 13: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 14: F. d'Alché-Buc, Y. Grandvalet and C. Ambroise. Semi-supervised marginBoost. Advances in Neural Information Processing Systems 14, 553--560, 2002.
• 15: Stephen Della Pietra , Vincent Della Pietra , John Lafferty, Inducing Features of Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.4, p.380-393, April 1997 [doi>10.1109/34.588021]
• 16: Y. Freund and R. Schapire. Experiments with a new boosting algorithm. The Thirteenth International Conference on Machine Learning, 148--156, 1996.
• 17: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 18: J. Friedman, T.Hastie and R. Tibshirani. Additive logistic regression: A statistical view of boosting. The Annals of Statistics, 28(2):337--407, 2000.
• 19: Y. Grandvalet and Y. Bengio. Semi-supervised learning by entropy minimization. Advances in Neural Information Processing Systems, 17:529--536, 2004.
• 20: Gholamreza Haffari , Yang Wang , Shaojun Wang , Greg Mori , Feng Jiao, Boosting with incomplete information, Proceedings of the 25th international conference on Machine learning, p.368-375, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390203]
• 21: T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd Edition, Springer, 2009.
• 22: Jean-Christophe Janodet , Richard Nock , Marc Sebban , Henri-Maxime Suchier, Boosting grammatical inference with confidence oracles, Proceedings of the twenty-first international conference on Machine learning, p.54, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015336]
• 23: Feng Jiao , Shaojun Wang , Chi-Hoon Lee , Russell Greiner , Dale Schuurmans, Semi-supervised conditional random fields for improved sequence segmentation and labeling, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, p.209-216, July 17-18, 2006, Sydney, Australia [doi>10.3115/1220175.1220202]
• 24: G. Lebanon and J. Lafferty. Boosting and maximum likelihood for exponential models. Advances in Neural Information Processing Systems 14, 447--454, 2002.
• 25: C. Lee, S. Wang, F. Jiao, D. Schuurmans and R. Greiner. Learning to model spatial dependency: Semi-supervised discriminative random fields. Advances in Neural Information Processing, 19, 793--800, 2007.
• 26: L. Mason, J. Baxter, P. Bartlett and M. Frean. Functional gradient techniques for combining hypotheses. In Advances in Large Margin Classifiers, A. Smola, P. Bartlett, B. Scholköpf and D. Schuurmans, editors, 221--246, MIT Press, 2000.
• 27: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000 [doi>10.1023/A:1007692713085]
• 28: S. Roberts, R. Everson and I. Rezek. Maximum certainty data partitioning. Pattern Recognition, 33(5):833--839, 2000.
• 29: Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
• 30: Hamed Valizadegan , Rong Jin , Anil K. Jain, Semi-Supervised Boosting for Multi-Class Classification, Proceedings of the European conference on Machine Learning and Knowledge Discovery in Databases - Part II, September 15-19, 2008, Antwerp, Belgium [doi>10.1007/978-3-540-87481-2_34]
• 31: Y. Wang, G. Haffari, S. Wang and G. Mori. Rate distortion based semi-supervised discriminative learning. Technical Report, 2009.
• 32: D. Zhou, O. Bousquet, T. Navin Lal, J. Weston and B. Schölkopf. Learning with local and global consistency. Advances in Neural Information Processing Systems, 16:321--328, 2004.
• 33: J. Zhu, S. Rosset, H. Zhou and T. Hastie. Multiclass AdaBoost. Technical Report, 2005.
• 34: X. Zhu, Z. Ghahramani and J. Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. The 20th International Conference on Machine Learning, 912--919, 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Experimentation, Performance

Keywords:
ensemble, semi-supervised learning