research-article

MILES: Multiple-Instance Learning via Embedded Instance Selection

Authors:

James Z. WangAuthors Info & Claims

IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 28, Issue 12

Pages 1931 - 1947

https://doi.org/10.1109/TPAMI.2006.248

Published: 01 December 2006 Publication History

Abstract

Multiple-instance problems arise from the situations where training class labels are attached to sets of samples (named bags), instead of individual samples within each bag (called instances). Most previous multiple-instance learning (MIL) algorithms are developed based on the assumption that a bag is positive if and only if at least one of its instances is positive. Although the assumption works well in a drug activity prediction problem, it is rather restrictive for other applications, especially those in the computer vision area. We propose a learning method, MILES (Multiple-Instance Learning via Embedded instance Selection), which converts the multiple-instance learning problem to a standard supervised learning problem that does not impose the assumption relating instance labels to bag labels. MILES maps each bag into a feature space defined by the instances in the training bags via an instance similarity measure. This feature mapping often provides a large number of redundant or irrelevant features. Hence, 1-norm SVM is applied to select important features as well as construct classifiers simultaneously. We have performed extensive experiments. In comparison with other methods, MILES demonstrates competitive classification accuracy, high computation efficiency, and robustness to labeling uncertainty.

References

[1]

S. Agarwal and D. Roth, “Learning a Sparse Representation for Object Detection,” Proc. Seventh European Conf. Computer Vision, vol. 4, pp. 113-130, 2002.

Digital Library

[2]

S. Andrews, I. Tsochantaridis, and T. Hofmann, “Support Vector Machines for Multiple-Instance Learning,” Advances in Neural Information Processing Systems 15, pp. 561-568, 2003.

[3]

S. Andrews and T. Hofmann, “Multiple-Instance Learning via Disjunctive Programming Boosting,” Advances in Neural Information Processing Systems 16, pp. 65-72, 2004.

[4]

P. Auer, “On Learning from Mult-Instance Examples: Empirical Evaluation of a Theoretical Approach,” Proc. 14th Int'l Conf. Machine Learning, pp. 21-29, 1997.

Digital Library

[5]

Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 702-709, 2005.

[6]

J. Machine Learning Research, vol. 3, pp. 1107-1135, 2003.

[7]

K.P. Bennett, “Combining Support Vector and Mathematical Programming Methods for Classification,” Advances in Kernel Methods-Support Vector Machines, B. Schölkopf, C. Burges, and A.Smola, eds., pp. 307-326, 1999.

Digital Library

[8]

J. Machine Learning Research, vol. 3, pp. 1229-1243, 2003.

[9]

C.L. Blake and C.J. Merz, UCI Repository of Machine Learning Databases,

[10]

A. Blum, and A. Kalai, “A Note on Learning from Multiple-Instance Examples,” Machine Learning, vol. 30, no. 1, pp. 23-29, 1998.

Digital Library

[11]

L. Breiman, “Bagging Predictors,” Machine Learning, vol. 24, pp.123-140, 1996.

[12]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 10, pp. 1312-1317, Oct. 2003.

Digital Library

[13]

B.G. Buchanan and T.M. Mitchell, “Model-Directed Learning of Production Rules,” Pattern-Directed Inference Systems, pp. 297-312, Academic Press, 1978.

[14]

SIAM J. Scientific Computing, vol. 20, no. 1, pp. 33-61, 1998.

Digital Library

[15]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 9, pp. 1252-1267, Sept. 2002.

Digital Library

[16]

Y. Chen and J.Z. Wang, “Image Categorization by Learning and Reasoning with Regions,” J. Machine Learning Research, vol. 5, pp.913-939, 2004.

Digital Library

[17]

G. Csurka, C. Bray, C. Dance, and L. Fan, “Visual Categorization with Bags of Keypoints,” Proc. ECCV '04 Workshop Statistical Learning in Computer Vision, pp. 59-74, 2004.

[18]

L. De Raedt, “Attribute-Value Learning versus Inductive Logic Programming: The Missing Links,” Lecture Notes in Artificial Intelligence, vol. 1446, pp. 1-8, 1998.

Digital Library

[19]

Artificial Intelligence, vol. 89, nos. 1-2, pp. 31-71, 1997.

[20]

G. Dorkó and C. Schmid, “Selection of Scale-Invariant Parts for Object Class Recognition,” Proc. IEEE Int'l Conf. Computer Vision, vol. 1, pp. 634-639, 2003.

Digital Library

[21]

R. Fergus, P. Perona, and A. Zisserman, “Object Class Recognition by Unsupervised Scale-Invariant Learning,” Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, vol. 2, pp. 264-271, 2003.

[22]

T. Gärtner, A. Flach, A. Kowalczyk, and A.J. Smola, “Multi-Instance Kernels,” Proc. 19th Int'l Conf. Machine Learning, pp. 179-186, 2002.

Digital Library

[23]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 6, pp.779-783, June 2003.

Digital Library

[24]

ILOG, ILOG CPLEX 6.5 Reference Manual, ILOG CPLEX Division, Incline Village, NV, 1999.

[25]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 2, pp. 153-158, Feb. 1997.

Digital Library

[26]

T. Kadir and M. Brady, “Scale, Saliency and Image Description,” Int'l J. Computer Vision, vol. 45, no. 2, pp. 83-105, 2001.

Digital Library

[27]

T. Kadir, A. Zisserman, and M. Brady, “An Affine Invariant Salient Region Detector,” Proc. Eighth European Conf. Computer Vision, pp. 404-416, 2004.

[28]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1105-1111, Sept. 2004.

Digital Library

[29]

Artificial Intelligence, vol. 97, nos. 1-2, pp. 273-324, 1997.

[30]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 12, pp. 1667-1671, Dec. 2002.

Digital Library

[31]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp.1154-1166, Sept. 2004.

Digital Library

[32]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 9, pp. 1075-1088, Sept. 2003.

Digital Library

[33]

P.M. Long and L. Tan, “PAC Learning Axis-Aligned Rectangles with Respect to Product Distribution from Multiple-Instance Examples,” Machine Learning, vol. 30, no. 1, pp. 7-21, 1998.

Digital Library

[34]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 8, pp. 837-842, Aug. 1996.

Digital Library

[35]

O. Maron and T. Lozano-Pérez, “A Framework for Multiple-Instance Learning,” Advances in Neural Information Processing Systems 10, pp. 570-576, 1998.

Digital Library

[36]

O. Maron, “Learning from Ambiguity,” Dept. of Electrical and Computer Science, Massachusetts Inst. of Technology, Cambridge, 1998.

[37]

O. Maron and A.L. Ratan, “Multiple-Instance Learning for Natural Scene Classification,” Proc. 15th Int'l Conf. Machine Learning, pp. 341-349, 1998.

Digital Library

[38]

Int'l J. Computer Vision, vol. 60, no. 1, pp. 63-86, 2004.

Digital Library

[39]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 3, pp. 301-312, Mar. 2002.

Digital Library

[40]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 4, pp. 349-361, Apr. 2001.

Digital Library

[41]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 2, pp. 218-223, Feb. 1996.

Digital Library

[42]

A. Opelt, M. Fussenegger, A. Pinz, and P. Auer, “Weak Hypotheses and Boosting for Generic Object Detection and Recognition,” Proc. Eighth European Conf. Computer Vision, vol. 2, pp. 71-84, 2004.

[43]

J. Ramon and L. De Raedt, “Multi Instance Neural Networks,” Proc. ICML-2000 Workshop Attribute-Value and Relational Learning, 2000.

[44]

S. Ray and M. Craven, “Supervised versus Multiple Instance Learning: An Empirical Comparison,” Proc. 22nd Int'l Conf. Machine Learning, pp. 697-704, 2005.

Digital Library

[45]

F. Rothganger, S. Lazebnik, C. Schmid, and J. Ponce, “3D Object Modeling and Recognition Using Affine-Invariant Patches and Multi-View Spatial Constraints,” Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, vol. 2, pp. 272-277, 2003.

[46]

G. Ruffo, “Learning Single and Multiple Decision Trees for Security Applications,” PhD Dissertation, Dept. of Computer Science, Univ. of Turin, Italy, 2000.

[47]

S.D. Scott, J. Zhang, and J. Brown, “On Generalized Multiple-Instance Learning,” Int'l J. Computational Intelligence and Applications, vol. 5, no. 1, pp. 21-35, 2005.

[48]

J. Sivic, B.C. Russell, A.A. Efros, A. Zisserman, and W.T. Freeman, “Discovering Object Categories in Image Collections,” Proc. Int'l Conf. Computer Vision, vol. I, pp. 370-377, 2005.

Digital Library

[49]

A.J. Smola, B. Schölkopf, and G. Gätsch, “Linear Programs for Automatic Accuracy Control in Regression,” Proc. Int'l Conf. Artificial Neural Networks, pp. 575-580, 1999.

[50]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 7, pp. 900-912, July 2004.

Digital Library

[51]

R. Tibshirani, “Regression Shrinkage and Selection via the LASSO,” J. Royal Statistical Soc., Series B, vol. 58, pp. 267-288, 1996.

[52]

T. Tuytelaars and L. Van Gool, “Matching Widely Separated Views Based on Affine Invariant Regions,” Int'l J. Computer Vision, vol. 59, no. 1, pp. 61-85, 2004.

Digital Library

[53]

J. Wang and J.-D. Zucker, “Solving the Multiple-Instance Problem: A Lazy Learning Approach,” Proc. 17th Int'l Conf. Machine Learning, pp. 1119-1125, 2000.

Digital Library

[54]

IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 9, pp. 947-963, Sept. 2001.

Digital Library

[55]

N. Weidmann, E. Frank, and B. Pfahringer, “A Two-Level Learning Method for Generalized Multi-Instance Problems,” Proc. European Conf. Machine Learning, pp. 468-479, 2003.

Digital Library

[56]

Proc. IEEE Int'l Conf. Data Eng., pp. 233-243, 2000.

[57]

L. Yu and H. Liu, “Efficient Feature Selection via Analysis of Relevance and Redundancy,” J. Machine Learning Research, vol. 5, pp. 1205-1224, 2004.

Digital Library

[58]

X. Xu and E. Frank, “Logistic Regression and Boosting for Labeled Bags of Instances,” Proc. Pacific-Asia Conf. Knowledge Discovery and Data Mining, pp. 272-281, 2004.

[59]

Neural Processing Letters, vol. 19, no. 1, pp. 1-10, 2004.

[60]

Q. Zhang, S.A. Goldman, W. Yu, and J. Fritts, “Content-Based Image Retrieval Using Multiple-Instance Learning,” Proc. 19th Int'l Conf. Machine Learning, pp. 682-689, 2002.

Digital Library

[61]

Q. Zhang and S.A. Goldman, “EM-DD: An Improved Multiple-Instance Learning Technique,” Advances in Neural Information Processing Systems 14, pp. 1073-1080, 2002.

[62]

Y. Zhang, H. Zha, C. Chu, and X. Ji, “Towards Inferring Protein Interactions: Challenges and Solutions,” EURASIP J. Applied Signal Processing, special issue on advanced signal/image processing techniques for bioinformatics, 2006.

Digital Library

[63]

Z.-H. Zhou and M.-L. Zhang, “Ensembles of Multi-Instance Learners,” Lecture Notes in Artificial Intelligence, vol. 2837, pp.492-502, 2003.

[64]

J. Zhu, S. Rosset, T. Hastie, and R. Tibshirani, “1-Norm Support Vector Machines,” Advances in Neural Information Processing Systems 16, pp. 49-56, 2004.

[65]

J.-D. Zucker and Y. Chevaleyre, “Solving Multiple-Instance and Multiple-Part Learning Problems with Decision Trees and Rule Sets, Application to the Mutagenesis Problem,” Lecture Notes in Artificial Intelligence, vol. 2056, pp. 204-214, 2001.

Digital Library

Cited By

Luan TGu STang XZhuge WHou C(2024)Multi-Instance Learning with One Side Label NoiseACM Transactions on Knowledge Discovery from Data10.1145/364407618:5(1-24)Online publication date: 7-Feb-2024
https://dl.acm.org/doi/10.1145/3644076
Shu SWang DYuan SWei HJiang JFeng LZhang M(2024)Multiple-instance Learning from Triplet Comparison BagsACM Transactions on Knowledge Discovery from Data10.1145/363877618:4(1-18)Online publication date: 12-Feb-2024
https://dl.acm.org/doi/10.1145/3638776
Huang SLiu ZJin WMu Y(2024)Superpixel-based multi-scale multi-instance learning for hyperspectral image classificationPattern Recognition10.1016/j.patcog.2024.110257149:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.patcog.2024.110257
Show More Cited By

Index Terms

MILES: Multiple-Instance Learning via Embedded Instance Selection
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision problems
        Object recognition
      2. Computer vision representations
  2. Machine learning
    1. Machine learning algorithms
      1. Feature selection

Recommendations

MILD: Multiple-Instance Learning via Disambiguation

In multiple-instance learning (MIL), an individual example is called an instance and a bag contains a single or multiple instances. The class labels available in the training set are associated with bags rather than instances. A bag is labeled positive ...
An automatic feature generation approach to multiple instance learning and its applications to image databases

Automatic content-based image categorization is a challenging research topic and has many practical applications. Images are usually represented as bags of feature vectors, and the categorization problem is studied in the Multiple-Instance Learning (MIL)...
Multiple-Instance Active Learning for Image Categorization
MMM '09: Proceedings of the 15th International Multimedia Modeling Conference on Advances in Multimedia Modeling

Both multiple-instance learning and active learning are widely employed in image categorization, but generally they are applied separately. This paper studies the integration of these two methods. Different from typical active learning approaches, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Pattern Analysis and Machine Intelligence

IEEE Transactions on Pattern Analysis and Machine Intelligence Volume 28, Issue 12

December 2006

149 pages

ISSN:0162-8828

Issue’s Table of Contents

Copyright © 2006.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 December 2006

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

201
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Luan TGu STang XZhuge WHou C(2024)Multi-Instance Learning with One Side Label NoiseACM Transactions on Knowledge Discovery from Data10.1145/364407618:5(1-24)Online publication date: 7-Feb-2024
https://dl.acm.org/doi/10.1145/3644076
Shu SWang DYuan SWei HJiang JFeng LZhang M(2024)Multiple-instance Learning from Triplet Comparison BagsACM Transactions on Knowledge Discovery from Data10.1145/363877618:4(1-18)Online publication date: 12-Feb-2024
https://dl.acm.org/doi/10.1145/3638776
Huang SLiu ZJin WMu Y(2024)Superpixel-based multi-scale multi-instance learning for hyperspectral image classificationPattern Recognition10.1016/j.patcog.2024.110257149:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.patcog.2024.110257
Zhang JWu YHao FLiu XLi MZhou DZheng W(2024)Double similarities weighted multi-instance learning kernel and its applicationExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.121900238:PBOnline publication date: 27-Feb-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.121900
Park SKim JWang XLim J(2024)Variable selection in Bayesian multiple instance regression using shotgun stochastic searchComputational Statistics & Data Analysis10.1016/j.csda.2024.107954196:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.csda.2024.107954
Rico-Juan JSánchez-Cartagena VValero-Mas JGallego A(2023)Identifying Student Profiles Within Online Judge Systems Using Explainable Artificial IntelligenceIEEE Transactions on Learning Technologies10.1109/TLT.2023.323911016:6(955-969)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TLT.2023.3239110
Feng LShu SCao YTao LWei HXiang TAn BNiu G(2023)Multiple-Instance Learning From Unlabeled Bags With Pairwise SimilarityIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.323214135:11(11599-11609)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3232141
Jiao CYang BLiu LChen CChen XYang WJiao L(2023)Semantic modeling of hyperspectral target detection with weak labelsSignal Processing10.1016/j.sigpro.2023.109016209:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.sigpro.2023.109016
Zhang YMeng HCao XZhou ZYang MAdhikary A(2023)Interpreting vulnerabilities of multi-instance learning to adversarial perturbationsPattern Recognition10.1016/j.patcog.2023.109725142:COnline publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1016/j.patcog.2023.109725
Huang SLiu ZJin WMu Y(2023)A deep multi-instance neural network for dyeing-free inspection of yarn dyeing uniformityEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.106159123:PAOnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.engappai.2023.106159
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents