Abstract
The multiple instance classification problem (Dietterich et al., Artif. Intell. 89:31–71, [1998]; Auer, Proceedings of 14th International Conference on Machine Learning, pp. 21–29, Morgan Kaufmann, San Mateo, [1997]; Long et al., Mach. Learn. 30(1):7–22, [1998]) is formulated using a linear or nonlinear kernel as the minimization of a linear function in a finite-dimensional (noninteger) real space subject to linear and bilinear constraints. A linearization algorithm is proposed that solves a succession of fast linear programs that converges in a few iterations to a local solution. Computational results on a number of datasets indicate that the proposed algorithm is competitive with the considerably more complex integer programming and other formulations. A distinguishing aspect of our linear classifier not shared by other multiple instance classifiers is the sparse number of features it utilizes. In some tasks, the reduction amounts to less than one percent of the original features.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Dietterich, T.G., Lathrop, R.H., Lozano-Perez, T.: Solving the multiple-instance problem with axis-parallel rectangles. Artif. Intell. 89, 31–71 (1998)
Auer, P.: On learning from multi-instance examples: empirical evaluation of a theoretical approach. In: Proceedings of 14th International Conference on Machine Learning, pp. 21–29. Morgan Kaufmann, San Mateo (1997)
Long, P.M., Tan, L.: PAC learning axis aligned rectangles with respect to product distributions from multiple instance examples. Mach. Learn. 30(1), 7–22 (1998)
Andrews, S., Tsochantaridis, I., Hofmann, T.: Support vector machines for multiple-instance learning. In: Becker, S., Thrun, S., Obermayer, K. (eds.) Advances in Neural Information Processing Systems 15, pp. 561–568. MIT Press, Cambridge (2003)
Zhang, Q., Goldman, S.A.: EM-DD: an improved multiple-instance learning technique. In: Neural Information Processing Systems 2001, pp. 1073–1080. MIT Press, Cambridge (2002)
Gartner, T., Flach, P.A., Kowalczyk, A., Smola, A.J.: Multi-instance kernels. In: Sammut, C., Hoffmann, A. (eds.) Proceedings of 19th International Conference on Machine Learning, pp. 179–186. Morgan Kaufmann, San Mateo (2002)
Ray, S., Craven, M.: Supervised versus multiple instance learning: an empirical comparison. In: Proceedings of 22nd International Conference on Machine Learning, Bonn, Germany, vol. 119, pp. 697–704. Assoc. Comput. Mach., New York (2005)
Schölkopf, B., Smola, A.: Learning with Kernels. MIT Press, Cambridge (2002)
Cortes, C., Vapnik, V.: Support vector networks. Mach. Learn. 20, 273–279 (1995)
Mangasarian, O.L.: Generalized support vector machines. In: Smola, A., Bartlett, P., Schölkopf, B., Schuurmans, D. (eds.) Advances in Large Margin Classifiers, pp. 135–146. MIT Press, Cambridge (2000). ftp://ftp.cs.wisc.edu/math-prog/tech-reports/98-14.ps
Vapnik, V.N.: The Nature of Statistical Learning Theory, 2nd edn. Springer, New York (2000)
Bradley, P.S., Mangasarian, O.L.: Feature selection via concave minimization and support vector machines. In: Shavlik, J. (ed.) Proceedings of 15th International Conference on Machine Learning, San Francisco, California, pp. 82–90. Morgan Kaufmann, San Mateo (1998). ftp://ftp.cs.wisc.edu/math-prog/tech-reports/98-03.ps
Zhu, J., Rosset, S., Hastie, T., Tibshirani, R.: 1-norm support vector machines. In: Thrun, S., Saul, L.K., Schölkopf, B. (eds.) Advances in Neural Information Processing Systems 16–NIPS2003, pp. 49–56. MIT Press, Cambridge (2004)
Mangasarian, O.L.: Arbitrary-norm separating plane. Oper. Res. Lett. 24, 15–23 (1999). ftp://ftp.cs.wisc.edu/math-prog/tech-reports/97-07r.ps
Murphy, P.M., Aha, D.W.: UCI Machine Learning Repository (1992). www.ics.uci.edu/~mlearn/MLRepository.html
Bouckaert, R.R.: Choosing between two learning algorithms based on calibrated tests. In: Proceedings of 20th International Conference on Machine Learning, pp. 51–58 (2003)
Friedman, M.: The use of ranks to avoid the assumption of normality implicit in the analysis of variance. J. Am. Stat. Assoc. 32, 675–701 (1937)
Dunn, O.J.: Multiple comparisons among means. J. Am. Stat. Assoc. 56, 52–64 (1961)
Demšar, J.: Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res. 7, 1–30 (2006)
MATLAB: User’s Guide. The MathWorks, Inc., Natick, MA 01760 (1994–2006). http://www.mathworks.com
ILOG: Incline Village, Nevada, ILOG CPLEX 9.0 User’s Manual (2003). http://www.ilog.com/products/cplex/
Lee, Y.-J., Mangasarian, O.L.: RSVM: reduced support vector machines. In: Proceedings of First SIAM International Conference on Data Mining, Chicago, 5–7 April 2001. CD-ROM (2001). ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/00-07.ps
Maron, O., Ratan, A.L.: Multiple-instance learning for natural scene classification. In: 15th International Conference on Machine Learning, San Francisco, CA. Morgan Kaufmann, San Mateo (1998)
Ramon, J., De Raedt, L.: Multi-instance neural networks, In: Proceedings of ICML-2000. Workshop on Attribute-Value and Relational Learning (2000)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by National Science Foundation Grants CCR-0138308 and IIS-0511905.
Rights and permissions
About this article
Cite this article
Mangasarian, O.L., Wild, E.W. Multiple Instance Classification via Successive Linear Programming. J Optim Theory Appl 137, 555–568 (2008). https://doi.org/10.1007/s10957-007-9343-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-007-9343-5