Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Previous studies on multi-instance learning typically treated instances in the bags as independently and identically distributed. The instances in a bag, however, are rarely independent in real tasks, and a better performance can be expected if the instances are treated in an non-i.i.d. way that exploits relations among instances. In this paper, we propose two simple yet effective methods. In the first method, we explicitly map every bag to an undirected graph and design a graph kernel for distinguishing the positive and negative bags. In the second method, we implicitly construct graphs by deriving affinity matrices and propose an efficient graph kernel considering the clique information. The effectiveness of the proposed methods are validated by experiments.

REFERENCES

• 1: Robert Amar , Daniel R. Dooly , Sally A. Goldman , Qi Zhang, Multiple-Instance Learning of Real-Valued Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.3-10, June 28-July 01, 2001
• 2: Andrews, S., Tsochantaridis, I., & Hofmann, T. (2003). Support vector machines for multiple-instance learning. In Adv. Neural Inf. Process. Syst. 15, 561--568. Cambridge, MA: MIT Press.
• 3: Auer, P., & Ortner, R. (2004). A boosting approach to multiple instance learning. Proc. 15th Eur. Conf. Mach. Learn. (pp. 63--74).
• 4: Hendrik Blockeel , David Page , Ashwin Srinivasan, Multi-instance tree learning, Proceedings of the 22nd international conference on Machine learning, p.57-64, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102359]
• 5: Karsten M. Borgwardt , Hans-Peter Kriegel, Shortest-Path Kernels on Graphs, Proceedings of the Fifth IEEE International Conference on Data Mining, p.74-81, November 27-30, 2005 [doi>10.1109/ICDM.2005.132]
• 6: Yixin Chen , Jinbo Bi , James Z. Wang, MILES: Multiple-Instance Learning via Embedded Instance Selection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.12, p.1931-1947, December 2006 [doi>10.1109/TPAMI.2006.248]
• 7: Yixin Chen , James Z. Wang, Image Categorization by Learning and Reasoning with Regions, The Journal of Machine Learning Research, 5, p.913-939, 12/1/2004
• 8: Pak-Ming Cheung , James T. Kwok, A regularization framework for multiple-instance learning, Proceedings of the 23rd international conference on Machine learning, p.193-200, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143869]
• 9: Yann Chevaleyre , Jean-Daniel Zucker, A Framework for Learning Rules from Multiple Instance Data, Proceedings of the 12th European Conference on Machine Learning, p.49-60, September 05-07, 2001
• 10: Csurka, G., Bray, C., Dance, C., & Fan, L. (2004). Visual categorization with bags of keypoints. ECCV Workshop on Statistical Learning in Computer Vision (pp. 59--74).
• 11: 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]
• 12: Fung, G., Dundar, M., Krishnappuram, B., & Rao, R. B. (2007). Multiple instance learning for computer aided diagnosis. In Adv. Neural Inf. Process. Syst. 19, 425--432. Cambridge, MA: MIT Press.
• 13: Thomas Gärtner, A survey of kernels for structured data, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959248]
• 14: 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
• 15: Kwok, J. T., & Cheung, P.-M. (2007). Marginalized multi-instance kernels. Proc. 20th Intl. J. Conf. Artif. Intell. (pp. 901--906).
• 16: 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
• 17: McGovern, A., & Jensen, D. (2003). Identifying predictive structures in relational data using multiple instance learning. Proc. 20th Intl. Conf. Mach. Learn. (pp. 528--535).
• 18: Neuhaus, M., & Bunke, H. (2007). A quadratic programming approach to the graph edit distance problem. Proc. 6th IAPR Workshop on Graph-based Represent. in Patt. Recogn. (pp. 92--102).
• 19: Rouhollah Rahmani , Sally A. Goldman, MISSL: multiple-instance semi-supervised learning, Proceedings of the 23rd international conference on Machine learning, p.705-712, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143933]
• 20: Soumya Ray , Mark Craven, Supervised versus multiple instance learning: an empirical comparison, Proceedings of the 22nd international conference on Machine learning, p.697-704, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102439]
• 21: Soumya Ray , David Page, Multiple Instance Regression, Proceedings of the Eighteenth International Conference on Machine Learning, p.425-432, June 28-July 01, 2001
• 22: Ruffo, G. (2000). Learning single and multiple instance decision trees for computer security applications. Doctoral dissertation, CS Dept., Univ. Turin, Torino, Italy.
• 23: Scott, S. D., Zhang, J., & Brown, J. (2003). On generalized multiple-instance learning (Technical Report UNL-CSE-2003-5). CS Dept., Univ. Nebraska, Lincoln, NE.
• 24: Settles, B., Craven, M., & Ray, S. (2008). Multiple-instance active learning. In Adv. Neural Inf. Process. Syst. 20, 1289--1296. Cambridge, MA: MIT Press.
• 25: Craig Stanfill , David Waltz, Toward memory-based reasoning, Communications of the ACM, v.29 n.12, p.1213-1228, Dec. 1986 [doi>10.1145/7902.7906]
• 26: Tenenbaum, J. B., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319--2323.
• 27: Viola, P., Platt, J., & Zhang, C. (2006). Multiple instance boosting for object detection. In Adv. Neural Inf. Process. Syst. 18, 1419--1426. Cambridge, MA: MIT Press.
• 28: Hua-Yan Wang , Qiang Yang , Hongbin Zha, Adaptive p-posterior mixture-model kernels for multiple instance learning, Proceedings of the 25th international conference on Machine learning, p.1136-1143, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390299]
• 29: 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
• 30: Weidmann, N., Frank, E., & Pfahringer, B. (2003). A two-level learning method for generalized multi-instance problem. Proc. 14th Eur. Conf. Mach. Learn. (pp. 468--479).
• 31: Xu, X., & Frank, E. (2004). Logistic regression and boosting for labeled bags of instances. Proc. 8th Pac.-Asia Conf. Knowl. Discov. Data Min. (pp. 272--281).
• 32: Zhang, C., & Viola, P. (2008). Multiple-instance pruning for learning efficient cascade detectors. In Adv. Neural Inf. Process. Syst. 20, 1681--1688. Cambridge, MA: MIT Press.
• 33: Min-Ling Zhang , Zhi-Hua Zhou, Adapting RBF Neural Networks to Multi-Instance Learning, Neural Processing Letters, v.23 n.1, p.1-26, February 2006 [doi>10.1007/s11063-005-2192-z]
• 34: Zhang, Q., & Goldman, S. A. (2002). EM-DD: An improved multi-instance learning technique. In Adv. Neural Inf. Process. Syst. 14, 1073--1080. Cambridge, MA: MIT Press.
• 35: 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
• 36: Zhi-Hua Zhou , Jun-Ming Xu, On the relation between multi-instance learning and semi-supervised learning, Proceedings of the 24th international conference on Machine learning, p.1167-1174, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273643]
• 37: Zhou, Z.-H., & Zhang, M.-L. (2007). Multi-instance multi-label learning with application to scene classification. In Adv. Neural Inf. Process. Syst. 19, 1609--1616. Cambridge, MA: MIT Press.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory