skip to main content
research-article

Multiple-Instance Learning from Pairwise Comparison Bags

Published: 14 December 2024 Publication History

Abstract

Multiple-instance learning (MIL) is a significant weakly supervised learning problem, where the training data consist of bags containing multiple instances and bag-level labels. Most previous MIL research required fully labeled bags. However, collecting such data is challenging due to the labeling costs or privacy concerns. Fortunately, we can easily collect pairwise comparison information, indicating one bag is more likely to be positive than the other. Therefore, we investigate a novel MIL problem about learning a bag-level binary classifier only from pairwise comparison bags. To solve this problem, we display the data generation process and provide a baseline method to train an instance-level classifier based on unlabeled-unlabeled learning. To achieve better performance, we propose a convex formulation to train a bag-level classifier and give a generalization error bound. Comprehensive experiments show that both the baseline method and the convex formulation achieve satisfactory performance, while the convex formulation performs better.

References

[1]
Jaume Amores. 2013. Multiple instance classification: Review, taxonomy and comparative study. Artificial Intelligence 201 (2013), 81–105.
[2]
Martin S. Andersen, Joachim Dahl, and Lieven Vandenberghe. 2013. CVXOPT: Python Software for Convex Optimization. Retrieved from https://cvxopt
[3]
Stuart Andrews, Ioannis Tsochantaridis, and Thomas Hofmann. 2002. Support vector machines for multiple-instance learning. In Proceedings of the 15th International Conference on Neural Information Processing Systems (NIPS ’02). MIT Press, Cambridge, MA, 577–584.
[4]
B. Babenko, M. Yang, and S. Belongie. 2009. Visual tracking with online multiple instance learning. In Proceedings of the 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPR Workshops ’09). IEEE Computer Society, Los Alamitos, CA, 983–990. DOI:
[5]
Boris Babenko, Ming-Hsuan Yang, and Serge J. Belongie. 2011. Robust object tracking with online multiple instance learning. IEEE Transactions on Pattern Analysis and Machine Intelligence 33 (2011), 1619–1632.
[6]
Han Bao, Gang Niu, and Masashi Sugiyama. 2018. Classification from pairwise similarity and unlabeled data. In Proceedings of the 35th International Conference on Machine Learning. Jennifer Dy and Andreas Krause (Eds.), Proceedings of Machine Learning Research, Vol. 80, PMLR, 452–461.
[7]
Han Bao, Tomoya Sakai, Issei Sato, and Masashi Sugiyama. 2018. Convex formulation of multiple instance learning from positive and unlabeled bags. Neural Networks 105 (2018), 132–141.
[8]
Peter L. Bartlett and Shahar Mendelson. 2002. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research 3, 11 (2002), 463–482.
[9]
Forrest Briggs, Balaji Lakshminarayanan, Lawrence Neal, Xiaoli Z. Fern, Raviv Raich, Sarah Hadley, Adam S. Hadley, and Matthew G. Betts. 2012. Acoustic classification of multiple simultaneous bird species: A multi-instance multi-label approach. The Journal of the Acoustical Society of America 131, 6 (2012), 4640–4650.
[10]
Yuzhou Cao, Lei Feng, Yitian Xu, Bo An, Gang Niu, and Masashi Sugiyama. 2021. Learning from similarity-confidence data. In Proceedings of the 38th International Conference on Machine Learning. Marina Meila and Tong Zhang (Eds.), Proceedings of Machine Learning Research, Vol. 139, PMLR, 1272–1282.
[11]
Marc-André Carbonneau, V. Cheplygina, Eric Granger, and Ghyslain Gagnon. 2018. Multiple instance learning: A survey of problem characteristics and applications. Pattern Recognition 77 (2018), 329–353.
[12]
Yixin Chen, Jinbo Bi, and J. Z. Wang. 2006. MILES: Multiple-instance learning via embedded instance selection. IEEE Transactions on Pattern Analysis and Machine Intelligence 28, 12 (2006), 1931–1947. DOI:
[13]
Yixin Chen, Jinbo Bi, and James Ze Wang. 2006. MILES: Multiple-instance learning via embedded instance selection. IEEE Transactions on Pattern Analysis and Machine Intelligence 28 (2006), 1931–1947.
[14]
Yu-Ting Chou, Gang Niu, Hsuan-Tien Lin, and Masashi Sugiyama. 2020. Unbiased risk estimators can mislead: A case study of learning with complementary labels. In Proceedings of the 37th International Conference on Machine Learning (ICML ’20). JMLR.org, Article 180, 10 pages.
[15]
Thomas G. Dietterich, Richard H. Lathrop, and Tomas Lozano-Perez. 1997. Solving the multiple instance problem with axis-parallel rectangles. Artificial Intelligence 89 (1997), 31–71.
[16]
Marthinus Christoffel Du Plessis, Gang Niu, and Masashi Sugiyama. 2015. Convex formulation for learning from positive and unlabeled data. In Proceedings of the 32nd International Conference on International Conference on Machine Learning (ICML’15), Vol. 37, JMLR.org, 1386–1394.
[17]
Lei Feng, Takuo Kaneko, Bo Han, Gang Niu, Bo An, and Masashi Sugiyama. 2020. Learning with multiple complementary labels. In Proceedings of the 37th International Conference on Machine Learning (ICML ’20), JMLR.org, Article 288, 10 pages.
[18]
Lei Feng, Jiaqi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, and Masashi Sugiyama. 2020. Provably consistent partial-label learning. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NIPS ’20). Curran Associates Inc., Red Hook, NY, Article 919, 13 pages.
[19]
Lei Feng, Senlin Shu, Yuzhou Cao, Lue Tao, Hongxin Wei, Tao Xiang, Bo An, and Gang Niu. 2021. Multiple-instance learning from similar and dissimilar bags. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (KDD ’21). ACM, New York, NY, 374–382. DOI:
[20]
Lei Feng, Senlin Shu, Zhuoyi Lin, Fengmao Lv, Li Li, and Bo An. 2020. Can cross entropy loss be robust to label noise? In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI ’20). Christian Bessiere (Ed.), International Joint Conferences on Artificial Intelligence Organization, 2206–2212. DOI:
[21]
Lei Feng, Senlin Shu, Nan Lu, Bo Han, Miao Xu, Gang Niu, Bo An, and Masashi Sugiyama. 2021. Pointwise binary classification with pairwise confidence comparisons. In Proceedings of the 38th International Conference on Machine Learning. Marina Meila and Tong Zhang (Eds.), Proceedings of Machine Learning Research, Vol. 139, PMLR, 3252–3262.
[22]
Thomas Gärtner, Peter A. Flach, Adam Kowalczyk, and Alex J. Smola. 2002. Multi-instance kernels. In Proceedings of the 19th International Conference on Machine Learning (ICML ’02). Morgan Kaufmann Publishers Inc., San Francisco, CA, 179–186.
[23]
Lan-Zhe Guo, Zhi Zhou, and Yu-Feng Li. 2020. RECORD: Resource constrained semi-supervised learning under distribution shift. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD ’20). ACM, New York, NY, 1636–1644. DOI:
[24]
Hayden S. Helm, Amitabh Basu, Avanti Athreya, Youngser Park, Joshua T. Vogelstein, Carey E. Priebe, Michael Winding, Marta Zlatic, Albert Cardona, Patrick Bourke, et al. 2023. Distance-based positive and unlabeled learning for ranking. Pattern Recognition 134 (2023), 109085. DOI:
[25]
Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference for Learning Representations, 13.
[26]
Christian Leistner, Amir Saffari, and Horst Bischof. 2010. MIForests: Multiple-instance learning with randomized trees. In Proceedings of the European Conference on Computer Vision (ECCV ’10). Kostas Daniilidis, Petros Maragos, and Nikos Paragios (Eds.), Springer, Berlin, 29–42.
[27]
Changchun Li, Ximing Li, Lei Feng, and Jihong Ouyang. 2022. Who is your right mixup partner in positive and unlabeled learning. In Proceedings of the 10th International Conference on Learning Representations (ICLR ’22). OpenReview.net. Retrieved from https://openreview.net/forum?id=NH29920YEmj
[28]
Yu-Feng Li and De-Ming Liang. 2019. Frontiers of computer science. Science 13, 4 (2019), 669–676.
[29]
Nan Lu, Gang Niu, Aditya Krishna Menon, and Masashi Sugiyama. 2018. On the minimal supervision for training any binary classifier from only unlabeled data. arXiv:1808.10585. Retrieved from http://arxiv.org/abs/1808.10585
[30]
Nan Lu, Tianyi Zhang, Gang Niu, and Masashi Sugiyama. 2020. Mitigating overfitting in supervised classification from two unlabeled datasets: A consistent risk correction approach. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics. Silvia Chiappa and Roberto Calandra (Eds.), Proceedings of Machine Learning Research, Vol. 108, PMLR, 1115–1125.
[31]
Tingjin Luo, Weizhong Zhang, Shuang Qiu, Yang Yang, Dongyun Yi, Guangtao Wang, Jieping Ye, and Jie Wang. 2017. Functional annotation of human protein coding isoforms via non-convex multi-instance learning. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’17). ACM, 345–354.
[32]
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. 2018. Foundations of Machine Learning. MIT Press.
[33]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. PyTorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems. H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc., 8024–8035.
[34]
Soumya Ray and Mark Craven. 2005. Supervised versus multiple instance learning: An empirical comparison. In Proceedings of the 22nd International Conference on Machine Learning (ICML ’05). ACM, New York, NY, 697–704.
[35]
Soumya Ray and Mark W. Craven. 2005. Learning statistical models for annotating proteins with function information using biomedical text. BMC Bioinformatics 6 (2005), S18.
[36]
Burr Settles, Mark Craven, and Soumya Ray. 2007. Multiple-instance active learning. In Advances in Neural Information Processing Systems. J. Platt, D. Koller, Y. Singer, and S. Roweis (Eds.), Vol. 20. Curran Associates, Inc., 1289–1296. Retrieved from https://proceedings.neurips.cc/paper_files/paper/2007/file/a1519de5b5d44b31a01de013b9b51a80- Paper.pdf
[37]
Jun Wang and Jean-Daniel Zucker. 2000. Solving the multiple-instance problem: A lazy learning approach. In Proceedings of the 17th International Conference on Machine Learning (ICML ’00). Morgan Kaufmann Publishers Inc., San Francisco, CA, 1119–1126.
[38]
H. Wei, L. Feng, X. Chen, and B. An. 2020. Combating noisy labels by agreement: A joint training method with co-regularization. In Proceedings of the 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR ’20). IEEE Computer Society, Los Alamitos, CA, 13723–13732. DOI:
[39]
Dong-Dong Wu, Deng-Bao Wang, and Min-Ling Zhang. 2022. Revisiting consistency regularization for deep partial label learning. In Proceedings of the 39th International Conference on Machine Learning. Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (Eds.), Proceedings of Machine Learning Research, Vol. 162, PMLR, 24212–24225.
[40]
Jia Wu, Shirui Pan, Xingquan Zhu, Chengqi Zhang, and Xindong Wu. 2018. Multi-instance learning with discriminative bag mapping. IEEE Transactions on Knowledge and Data Engineering 30, 6 (2018), 1065–1080.
[41]
Bi-Cun Xu, Kai Ming Ting, and Zhi-Hua Zhou. 2019. Isolation set-kernel and its application to multi-instance learning. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 941–949.
[42]
Xin Xu and Eibe Frank. 2004. Logistic regression and boosting for labeled bags of instances. In Advances in Knowledge Discovery and Data Mining. Honghua Dai, Ramakrishnan Srikant, and Chengqi Zhang (Eds.), Springer, Berlin, 272–281.
[43]
Yang Yi and Maoqing Lin. 2016. Human action recognition with graph-based multiple-instance learning. Pattern Recognition 53 (2016), 148–162. DOI:
[44]
Cha Zhang, John Platt, and Paul Viola. 2005. Multiple instance boosting for object detection. In Advances in Neural Information Processing Systems, Vol. 18, 1417–1424.
[45]
Cha Zhang and Paul Viola. 2007. Multiple-instance pruning for learning efficient cascade detectors. In Proceedings of the 20th International Conference on Neural Information Processing Systems (NIPS ’07). Curran Associates Inc., Red Hook, NY, 1681–1688.
[46]
Qi Zhang and Sally A. Goldman. 2001. EM-DD: An improved multiple-instance learning technique. In Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic (NIPS ’01). MIT Press, Cambridge, MA, 1073–1080.
[47]
Qi Zhang, Sally A. Goldman, Wei Yu, and Jason Fritts. 2002. Content-based image retrieval using multiple-instance learning. In Proceedings of the 19th International Conference on Machine Learning (ICML ’02). Morgan Kaufmann Publishers Inc., San Francisco, CA, 682–689.
[48]
Teng Zhang and Hai Jin. 2020. Optimal margin distribution machine for multi-instance learning. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI ’20). Christian Bessiere (Ed.), International Joint Conferences on Artificial Intelligence Organization, 2383–2389. DOI:
[49]
Zhi-Hua Zhou. 2018. A brief introduction to weakly supervised learning. National Science Review 5 (2018), 44–53.
[50]
Zhi-Hua Zhou, Yu-Yin Sun, and Yu-Feng Li. 2009. Multi-instance learning by treating instances as non-I.I.D. samples. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML ’09). ACM, New York, NY, 1249–1256. DOI:

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Intelligent Systems and Technology
ACM Transactions on Intelligent Systems and Technology  Volume 15, Issue 6
December 2024
727 pages
EISSN:2157-6912
DOI:10.1145/3613712
  • Editor:
  • Huan Liu
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 December 2024
Online AM: 29 September 2024
Accepted: 05 August 2024
Revised: 14 July 2024
Received: 27 February 2024
Published in TIST Volume 15, Issue 6

Check for updates

Author Tags

  1. multiple-instance learning
  2. empirical risk minimization
  3. convex formulation

Qualifiers

  • Research-article

Funding Sources

  • Chongqing Science and Technology Bureau
  • Fundamental Research Program
  • Fundamental Research Funds for the Central Universities

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 134
    Total Downloads
  • Downloads (Last 12 months)134
  • Downloads (Last 6 weeks)20
Reflects downloads up to 12 Feb 2025

Other Metrics

Citations

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Full Text

View this article in Full Text.

Full Text

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media