More Web Proxy on the site http://driver.im/

research-article

Isolation Set-Kernel and Its Application to Multi-Instance Learning

Authors:

Zhi-Hua ZhouAuthors Info & Claims

KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Pages 941 - 949

https://doi.org/10.1145/3292500.3330830

Published: 25 July 2019 Publication History

Abstract

Set-level problems are as important as instance-level problems. The core in solving set-level problems is: how to measure the similarity between two sets. This paper investigates data-dependent kernels that are derived directly from data. We introduce Isolation Set-Kernel which is solely dependent on data distribution, requiring neither class information nor explicit learning. In contrast, most current set-similarities are not dependent on the underlying data distribution. We theoretically analyze the characteristic of Isolation Set-Kernel. As the set-kernel has a finite feature map, we show that it can be used to speed up the set-kernel computation significantly. We apply Isolation Set-Kernel to Multi-Instance Learning (MIL) using SVM classifier, and demonstrate that it outperforms other set-kernels or other solutions to the MIL problem.

References

[1]

Jaume Amores. 2013. Multiple instance classification: Review, taxonomy and comparative study. Artificial Intelligence, Vol. 201, 4 (2013), 81--105.

Digital Library

[2]

Stuart Andrews, Ioannis Tsochantaridis, and Thomas Hofmann. 2003. Support vector machines for multiple-instance learning. In Advances in neural information processing systems. 577--584.

Digital Library

[3]

Franz Aurenhammer. 1991. Voronoi diagrams-a survey of a fundamental geometric data structure. ACM Computing Surveys (CSUR), Vol. 23, 3 (1991), 345--405.

Digital Library

[4]

L. Breiman. 2000. Some infinity theory for predictor ensembles. Technical Report 577 (2000).

[5]

Chih-Chung Chang and Chih-Jen Lin. 2011. LIBSVM: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), Vol. 2, 3 (2011), 27.

Digital Library

[6]

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, Vol. 28, 12 (2006), 1931--1947.

Digital Library

[7]

Y. Chen, J. Li, and J. Z. Wang. 2004. Categorization by Learning and Reasoning with Regions .Springer US. 99--121 pages.

[8]

A. Davies and Z. Ghahramani. 2014. The random forest kernel and creating other kernels for big data from random partitions. arXiv:1402.4293 (2014).

[9]

Thomas G Dietterich, Richard H Lathrop, and Tomás Lozano-Pérez. 1997. Solving the multiple instance problem with axis-parallel rectangles. Artificial intelligence, Vol. 89, 1--2 (1997), 31--71.

Digital Library

[10]

Eibe Frank and Xin Xu. 2003. Applying propositional learning algorithms to multi-instance data. (2003).

[11]

Thomas Gartner, Peter A. Flach, Adam Kowalczyk, and Alex J. Smola. 2002. Multi-Instance Kernels. In Nineteenth International Conference on Machine Learning. 179--186.

Digital Library

[12]

Mehmet Gönen and Ethem Alpaydin. 2011. Multiple kernel learning algorithms. Journal of machine learning research, Vol. 12, Jul (2011), 2211--2268.

Digital Library

[13]

Tommi Jaakkola and David Haussler. 1999. Exploiting generative models in discriminative classifiers. In Advances in neural information processing systems. 487--493.

Digital Library

[14]

Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. 2008. Isolation forest. In 2008 Eighth IEEE International Conference on Data Mining. IEEE, 413--422.

Digital Library

[15]

Xiaoyu Qin, Kai Ming Ting, Ye Zhu, and Vincent Cheng Siong Lee. 2019. Nearest-Neighbour-Induced Isolation Similarity and Its Impact on Density-Based Clustering. In Proceedings of The Thirty-Third AAAI Conference on Artificial Intelligence. www.aaai.org/Papers/AAAI/2019/AAAI-QinX.7564.pdf .

[16]

Alain Rakotomamonjy, Francis R Bach, Stéphane Canu, and Yves Grandvalet. 2008. SimpleMKL. Journal of Machine Learning Research, Vol. 9, Nov (2008), 2491--2521.

[17]

Gerard Salton and Michael J McGill. 1986. Introduction to modern information retrieval. (1986).

Digital Library

[18]

Bernard W Silverman. 2018. Density estimation for statistics and data analysis .Routledge.

[19]

Kai Ming Ting, Yue Zhu, and Zhi-Hua Zhou. 2018. Isolation kernel and its effect on SVM. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2329--2337.

Digital Library

[20]

Fei Wang and Jimeng Sun. 2015. Survey on distance metric learning and dimensionality reduction in data mining. Data Mining & Knowledge Discovery, Vol. 29, 2 (2015), 534--564.

Digital Library

[21]

Xiu-Shen Wei, Jianxin Wu, and Zhi-Hua Zhou. 2017. Scalable algorithms for multi-instance learning. IEEE transactions on neural networks and learning systems, Vol. 28, 4 (2017), 975--987.

[22]

Xin Xu and Eibe Frank. 2004. Logistic regression and boosting for labeled bags of instances. In Pacific-Asia conference on knowledge discovery and data mining. Springer, 272--281.

[23]

Pourya Zadeh, Reshad Hosseini, and Suvrit Sra. 2016. Geometric mean metric learning. In International Conference on Machine Learning . 2464--2471.

Digital Library

[24]

Qi Zhang and Sally A Goldman. 2002. EM-DD: An improved multiple-instance learning technique. In Advances in neural information processing systems. 1073--1080.

Digital Library

[25]

Zhi-Hua Zhou, Yu-Yin Sun, and Yu-Feng Li. 2009. Multi-instance learning by treating instances as non-iid samples. In Proceedings of the 26th annual international conference on machine learning. ACM, 1249--1256.

Digital Library

[26]

Zhi Hua Zhou and Min Ling Zhang. 2007. Solving multi-instance problems with classifier ensemble based on constructive clustering. Knowledge and Information Systems, Vol. 11, 2 (2007), 155--170.

Digital Library

Cited By

Yang MZhang JPan ZMin F(2025)Multi-instance embedding space set-kernel fusion with discriminability metricApplied Intelligence10.1007/s10489-024-06160-z55:6Online publication date: 1-Apr-2025
https://dl.acm.org/doi/10.1007/s10489-024-06160-z
Zhou SShu SWang HWei HXiang TLi B(2024)Multiple-Instance Learning from Pairwise Comparison BagsACM Transactions on Intelligent Systems and Technology10.1145/369646015:6(1-22)Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1145/3696460
Chen WYu ZYang CLu Y(2024)Abnormal Behavior Recognition Based on 3D Dense ConnectionsInternational Journal of Neural Systems10.1142/S012906572450049734:09Online publication date: 16-Jul-2024
https://doi.org/10.1142/S0129065724500497
Show More Cited By

Index Terms

Isolation Set-Kernel and Its Application to Multi-Instance Learning
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Kernel methods
        Support vector machines

Recommendations

Cost‐effective multi‐instance multilabel active learning
Abstract
Multi‐instance multi‐label (MIML) Active Learning (M2AL) aims to improve the learner while reducing the cost as much as possible by querying informative labels of complex bags composed of diverse instances. Existing M2AL solutions suffer high ...
Diversified dictionaries for multi-instance learning

Multiple-instance learning (MIL) has been a popular topic in the study of pattern recognition for years due to its usefulness for such tasks as drug activity prediction and image/text classification. In a typical MIL setting, a bag contains a bag-level ...
Multi-instance clustering with applications to multi-instance prediction

In the setting of multi-instance learning, each object is represented by a bag composed of multiple instances instead of by a single instance in a traditional learning setting. Previous works in this area only concern multi-instance prediction problems ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

July 2019

3305 pages

ISBN:9781450362016

DOI:10.1145/3292500

General Chairs:
Ankur Teredesai
KenSci
,
Vipin Kumar
University of Minnesota
,
Program Chairs:
Ying Li
EV Analysis Corporation
,
Rómer Rosales
LinkedIn
,
Evimaria Terzi
Boston University
,
George Karypis
University of Minnesota

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Asian Office of Aerospace Research and Development (AOARD)
111 Program
NSFC
the National Key R&D Program of China

Conference

KDD '19

Sponsor:

KDD '19: The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 4 - 8, 2019

AK, Anchorage, USA

Acceptance Rates

KDD '19 Paper Acceptance Rate 110 of 1,200 submissions, 9%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
385
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yang MZhang JPan ZMin F(2025)Multi-instance embedding space set-kernel fusion with discriminability metricApplied Intelligence10.1007/s10489-024-06160-z55:6Online publication date: 1-Apr-2025
https://dl.acm.org/doi/10.1007/s10489-024-06160-z
Zhou SShu SWang HWei HXiang TLi B(2024)Multiple-Instance Learning from Pairwise Comparison BagsACM Transactions on Intelligent Systems and Technology10.1145/369646015:6(1-22)Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1145/3696460
Chen WYu ZYang CLu Y(2024)Abnormal Behavior Recognition Based on 3D Dense ConnectionsInternational Journal of Neural Systems10.1142/S012906572450049734:09Online publication date: 16-Jul-2024
https://doi.org/10.1142/S0129065724500497
Wang YZhao YWang ZZhang CWang X(2024)Robust Multi-Graph Multi-Label Learning With Dual-Granularity LabelingIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.338199146:10(6509-6524)Online publication date: Oct-2024
https://doi.org/10.1109/TPAMI.2024.3381991
Jiang XZhang HZhou Y(2024)Multi-Granularity Abnormal Traffic Detection Based on Multi-Instance LearningIEEE Transactions on Network and Service Management10.1109/TNSM.2023.332215221:2(1467-1477)Online publication date: Apr-2024
https://doi.org/10.1109/TNSM.2023.3322152
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
Chan TLi ZU LCheng R(2023)PLAME: Piecewise-Linear Approximate Measure for Additive Kernel SVMIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.325326335:10(9985-9997)Online publication date: 1-Oct-2023
https://doi.org/10.1109/TKDE.2023.3253263
Li SZhang TChen BChen C(2023)MIA-Net: Multi-Modal Interactive Attention Network for Multi-Modal Affective AnalysisIEEE Transactions on Affective Computing10.1109/TAFFC.2023.325901014:4(2796-2809)Online publication date: 1-Oct-2023
https://doi.org/10.1109/TAFFC.2023.3259010
Wang MZhao YWang YXu TSun Y(2023)Image emotion multi-label classification based on multi-graph learningExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.120641231:COnline publication date: 20-Sep-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.120641
Mu XZeng GHuang Z(2023)Federated Learning with Emerging New Class: A Solution Using Isolation-Based SpecificationDatabase Systems for Advanced Applications10.1007/978-3-031-30637-2_48(719-734)Online publication date: 14-Apr-2023
https://doi.org/10.1007/978-3-031-30637-2_48
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten