Supervised versus multiple instance learning: an empirical comparison

ABSTRACT

We empirically study the relationship between supervised and multiple instance (MI) learning. Algorithms to learn various concepts have been adapted to the MI representation. However, it is also known that concepts that are PAC-learnable with one-sided noise can be learned from MI data. A relevant question then is: how well do supervised learners do on MI data? We attempt to answer this question by looking at a cross section of MI data sets from various domains coupled with a number of learning algorithms including Diverse Density, Logistic Regression, nonlinear Support Vector Machines and FOIL. We consider a supervised and MI version of each learner. Several interesting conclusions emerge from our work: (1) no MI algorithm is superior across all tested domains, (2) some MI algorithms are consistently superior to their supervised counterparts, (3) using high false-positive costs can improve a supervised learner's performance in MI domains, and (4) in several domains, a supervised algorithm is superior to any MI algorithm we tested.

REFERENCES

• 1: Andrews, S., Tsochantaridis, I., & Hofmann, T. (2003). Support vector machines for multiple-instance learning. In Advances in neural information processing systems, vol. 15. MIT Press.
• 2: Auer, P., & Ortner, R. (2004). A boosting approach to multiple instance learning. Proc. of the 15th European Conf. on Machine Learning (pp. 63--74). Springer-Verlag.
• 3: Blaschke, C., Andres Leon, E., Krallinger, M., & Valencia, A. (2005). Evaluation of BioCreAtIvE assessment of task 2. BMC Bioinformatics, 6(Suppl. 1).
• 4: Avrim Blum , Adam Kalai, A Note on Learning from Multiple-Instance Examples, Machine Learning, v.30 n.1, p.23-29, Jan. 1998 [doi>10.1023/A:1007402410823]
• 5: Bradley, A. P. (1997). The use of the area under the roc curve in the evaluation of machine learning algorithms. Pattern Recognition, 30, 1145--1159.
• 6: Thomas G. Dietterich , Richard H. Lathrop , Tomás Lozano-Pérez, Solving the multiple instance problem with axis-parallel rectangles, Artificial Intelligence, v.89 n.1-2, p.31-71, Jan. 1997 [doi>10.1016/S0004-3702(96)00034-3]
• 7: Fletcher, R. (1980). Practical methods of optimization, vol. 1: Unconstrained Optimization, chapter 3. Wiley.
• 8: Thomas Gärtner , Peter A. Flach , Adam Kowalczyk , Alex J. Smola, Multi-Instance Kernels, Proceedings of the Nineteenth International Conference on Machine Learning, p.179-186, July 08-12, 2002
• 9: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 10: Nada Lavrac , Saso Dzeroski, Inductive Logic Programming: Techniques and Applications, Routledge, New York, NY, 1993
• 11: Yuh-Jye Lee , O. L. Mangasarian, SSVM: A Smooth Support Vector Machine for Classification, Computational Optimization and Applications, v.20 n.1, p.5-22, October 2001 [doi>10.1023/A:1011215321374]
• 12: Oded Maron , Tomas Lozano-Perez, Learning from ambiguity, 1998
• 13: Oded Maron , Tomás Lozano-Pérez, A framework for multiple-instance learning, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.570-576, July 1998, Denver, Colorado, United States
• 14: Oded Maron , Aparna Lakshmi Ratan, Multiple-Instance Learning for Natural Scene Classification, Proceedings of the Fifteenth International Conference on Machine Learning, p.341-349, July 24-27, 1998
• 15: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 16: J. R. Quinlan, Learning Logical Definitions from Relations, Machine Learning, v.5 n.3, p.239-266, Aug. 1990 [doi>10.1023/A:1022699322624]
• 17: Ruffo, G. (2000). Learning single and multiple instance decision trees for computer security applications. Doctoral dissertation, Università di Torino, Torino, Italy.
• 18: Qingping Tao , Stephen Scott , N. V. Vinodchandran , Thomas Takeo Osugi, SVM-based generalized multiple-instance learning via approximate box counting, Proceedings of the twenty-first international conference on Machine learning, p.101, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015405]
• 19: Jun Wang , Jean-Daniel Zucker, Solving the Multiple-Instance Problem: A Lazy Learning Approach, Proceedings of the Seventeenth International Conference on Machine Learning, p.1119-1126, June 29-July 02, 2000
• 20: Xu, X., & Frank, E. (2004). Logistic regression and boosting for labeled bags of instances. Proc. of the Pacific Asia Conf. on Knowledge Discovery and Data Mining. Springer--Verlag.
• 21: Qi Zhang , Sally A. Goldman , Wei Yu , Jason Fritts, Content-Based Image Retrieval Using Multiple-Instance Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.682-689, July 08-12, 2002