Learning classifiers from only positive and unlabeled data

ABSTRACT

The input to an algorithm that learns a binary classifier normally consists of two sets of examples, where one set consists of positive examples of the concept to be learned, and the other set consists of negative examples. However, it is often the case that the available training data are an incomplete set of positive examples, and a set of unlabeled examples, some of which are positive and some of which are negative. The problem solved in this paper is how to learn a standard binary classifier given a nontraditional training set of this nature.

Under the assumption that the labeled examples are selected randomly from the positive examples, we show that a classifier trained on positive and unlabeled examples predicts probabilities that differ by only a constant factor from the true conditional probabilities of being positive. We show how to use this result in two different ways to learn a classifier from a nontraditional training set. We then apply these two new methods to solve a real-world problem: identifying protein records that should be included in an incomplete specialized molecular biology database. Our experiments in this domain show that models trained using the new methods perform better than the current state-of-the-art biased SVM method for learning from positive and unlabeled examples.

REFERENCES

• 1: B. Boeckmann, A. Bairoch, R. Apweiler, M. Blatter, A. Estreicher, E. Gasteiger, M. Martin, K. Michoud, C. O'Donovan, I. Phan, et al. The SWISS-PROT protein knowledgebase and its supplement TrEMBL in 2003. Nucleic Acids Research, 31(1):365--370, 2003.
• 2: Sanmay Das , Milton H. Saier, Jr. , Charles Elkan, Finding Transport Proteins in a General Protein Database, Proceedings of the 11th European conference on Principles and Practice of Knowledge Discovery in Databases, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74976-9_9]
• 3: François Denis, PAC Learning from Positive Statistical Queries, Proceedings of the 9th International Conference on Algorithmic Learning Theory, p.112-126, October 08-10, 1998
• 4: François Denis , Rémi Gilleron , Fabien Letouzey, Learning from positive and unlabeled examples, Theoretical Computer Science, v.348 n.1, p.70-83, 2 December 2005 [doi>10.1016/j.tcs.2005.09.007]
• 5: F. Denis, R. Gilleron, and M. Tommasi. Text classification from positive and unlabeled examples. In Proceedings of the Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU 2002), pages 1927--1934, 2002.
• 6: Gabriel Pui Cheong Fung , Jeffrey X. Yu , Hongjun Lu , Philip S. Yu, Text Classification without Negative Examples Revisit, IEEE Transactions on Knowledge and Data Engineering, v.18 n.1, p.6-20, January 2006 [doi>10.1109/TKDE.2006.16]
• 7: M. Galperin. The Molecular Biology Database Collection: 2008 update. Nucleic Acids Research, 36(Database issue):D2, 2008.
• 8: W. S. Lee and B. Liu. Learning with positive and unlabeled examples using weighted logistic regression. In Proceedings of the Twentieth International Conference on Machine Learning (ICML 2003), Washington, DC, pages 448--455, 2003.
• 9: Hsuan-Tien Lin , Chih-Jen Lin , Ruby C. Weng, A note on Platt's probabilistic outputs for support vector machines, Machine Learning, v.68 n.3, p.267-276, October 2007 [doi>10.1007/s10994-007-5018-6]
• 10: Roderick J A Little , Donald B Rubin, Statistical analysis with missing data, John Wiley & Sons, Inc., New York, NY, 1986
• 11: Bing Liu , Yang Dai , Xiaoli Li , Wee Sun Lee , Philip S. Yu, Building Text Classifiers Using Positive and Unlabeled Examples, Proceedings of the Third IEEE International Conference on Data Mining, p.179, November 19-22, 2003
• 12: Z. Liu, W. Shi, D. Li, and Q. Qin. Partially supervised classification - based on weighted unlabeled samples support vector machine. In Proceedings of the First International Conference on Advanced Data Mining and Applications (ADMA 2005), Wuhan, China, volume 3584 of Lecture Notes in Computer Science, pages 118--129. Springer, 2005.
• 13: Larry M. Manevitz , Malik Yousef, One-class svms for document classification, The Journal of Machine Learning Research, 2, 3/1/2002
• 14: J. C. Platt. Probabilities for SV machines. In A. J. Smola, P. Bartlett, B. Schölkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, pages 61--73. MIT Press, 1999.
• 15: M. H. Saier, C. V. Tran, and R. D. Barabote. TCDB: the transporter classification database for membrane transport protein analyses and information. Nucleic Acids Research, 34:D181--D186, 2006.
• 16: Bernhard Schölkopf , John C. Platt , John C. Shawe-Taylor , Alex J. Smola , Robert C. Williamson, Estimating the Support of a High-Dimensional Distribution, Neural Computation, v.13 n.7, p.1443-1471, July 2001 [doi>10.1162/089976601750264965]
• 17: Andrew Smith , Charles Elkan, A Bayesian network framework for reject inference, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014085]
• 18: Andrew T. Smith , Charles Elkan, Making generative classifiers robust to selection bias, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281263]
• 19: David M. J. Tax , Robert P. W. Duin, Support Vector Data Description, Machine Learning, v.54 n.1, p.45-66, January 2004 [doi>10.1023/B:MACH.0000008084.60811.49]
• 20: Chunlin Wang , Chris Ding , Richard F. Meraz , Stephen R. Holbrook, PSoL: a positive sample only learning algorithm for finding non-coding RNA genes, Bioinformatics, v.22 n.21, p.2590-2596, August 2006 [doi>10.1093/bioinformatics/btl441]
• 21: G. Ward, T. Hastie, S. Barry, J. Elith, and J. R. Leathwick. Presence-only data and the EM algorithm. Biometrics, 2008. In press.
• 22: Fei Wu , Daniel S. Weld, Autonomously semantifying wikipedia, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321449]
• 23: Hwanjo Yu, Single-Class Classification with Mapping Convergence, Machine Learning, v.61 n.1-3, p.49-69, November 2005 [doi>10.1007/s10994-005-1122-7]
• 24: Hwanjo Yu , Jiawei Han , Kevin Chen-Chuan Chang, PEBL: Web Page Classification without Negative Examples, IEEE Transactions on Knowledge and Data Engineering, v.16 n.1, p.70-81, January 2004 [doi>10.1109/TKDE.2004.1264823]
• 25: Bianca Zadrozny , Charles Elkan, Transforming classifier scores into accurate multiclass probability estimates, 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.775151]
• 26: D. Zhang and W. S. Lee. A simple probabilistic approach to learning from positive and unlabeled examples. In Proceedings of the 5th Annual UK Workshop on Computational Intelligence (UKCI), pages 83--87, Sept. 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Theory

Keywords:
bioinformatics, supervised learning, text mining, unlabeled examples