nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Multiple Instance Learning with Bag-Level Randomized Trees

verfasst von : Tomáš Komárek, Petr Somol

Erschienen in: Machine Learning and Knowledge Discovery in Databases

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Knowledge discovery in databases with a flexible structure poses a great challenge to machine learning community. Multiple Instance Learning (MIL) aims at learning from samples (called bags) represented by multiple feature vectors (called instances) as opposed to single feature vectors characteristic for the traditional data representation. This relaxation turns out to be useful in formulating many machine learning problems including classification of molecules, cancer detection from tissue images or identification of malicious network communications. However, despite the recent progress in this area, the current set of MIL tools still seems to be very application specific and/or burdened with many tuning parameters or processing steps. In this paper, we propose a simple, yet effective tree-based algorithm for solving MIL classification problems. Empirical evaluation against 28 classifiers on 29 publicly available benchmark datasets shows a high level performance of the proposed solution even with its default parameter settings. Data related to this paper are available at: https://github.com/komartom/MIDatasets.jl. Code related to this paper is available at: https://github.com/komartom/BLRT.jl.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Pedestrian Trajectory Prediction with Structured Memory Hierarchies

Nächstes Kapitel One-Class Quantification

Technically, the value of \(0.\bar{9}\) should be 1 minus the smallest representable value.

If \(x^{\text {min}}_f\) equals to \(x^{\text {max}}_f\), no splitting rules are generated on feature f.

Term extremely corresponds to setting \(T=1\).

When bags are of size one (i.e. \(N_I=N_\mathcal {B}=N\)) and \(T=1\), the complexity is equivalent to the complexity of Extremely randomized trees \(\varTheta (MKN \log N)\).

Area Under a ROC Curve showing the true positive rate as a function of the false positive rate. AUC is agnostic to class imbalance and classifier’s threshold setting.

Except for Newsgroup3 where the proposal is competitive with the best prior art.

The sum in Eq. 2 is not normalized by bag size \(|\mathcal {B}|\) and parameter r can take values from interval \([1,\text {argmax}_{\mathcal {B}\in \mathcal {S}} |\mathcal {B}|)\).

Source codes are accessible at https://github.com/komartom/BLRT.jl.

Amores, J.: Multiple instance classification: review, taxonomy and comparative study. Artif. Intell. 201, 81–105 (2013). https://doi.org/10.1016/j.artint.2013.06.003MathSciNetCrossRefMATH

Andrews, S., Tsochantaridis, I., Hofmann, T.: Support vector machines for multiple-instance learning. In: Proceedings of the 15th International Conference on Neural Information Processing Systems, NIPS 2002, pp. 577–584. MIT Press, Cambridge (2002). http://dl.acm.org/citation.cfm?id=2968618.2968690

Babenko, B., Yang, M.H., Belongie, S.: Visual tracking with online multiple instance learning. In: 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 983–990, June 2009. https://doi.org/10.1109/CVPR.2009.5206737

Blockeel, H., Page, D., Srinivasan, A.: Multi-instance tree learning. In: Proceedings of the 22nd International Conference on Machine Learning, ICML 2005, pp. 57–64. ACM, New York (2005). http://doi.acm.org/10.1145/1102351.1102359

Breiman, L.: Random forests. Mach. Learn. 45(1), 5–32 (2001). https://doi.org/10.1145/1102351.1102359CrossRefMATH

Breiman, L., Friedman, J., Stone, C.J., Olshen, R.A.: Classification and Regression Trees. CRC Press, Boca Raton (1984)MATH

Chen, Y., Bi, J., Wang, J.Z.: Miles: multiple-instance learning via embeddedinstance selection. IEEE Trans. Pattern Anal. Mach. Intell. 28(12), 1931–1947 (2006). https://doi.org/10.1109/TPAMI.2006.248CrossRef

Cheplygina, V., Tax, D.M.J.: Characterizing multiple instance datasets. In: Feragen, A., Pelillo, M., Loog, M. (eds.) SIMBAD 2015. LNCS, vol. 9370, pp. 15–27. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-24261-3_2CrossRef

Cheplygina, V., Tax, D.M., Loog, M.: Multiple instance learning with bag dissimilarities. Pattern Recogn. 48(1), 264–275 (2015). https://doi.org/10.1016/j.patcog.2014.07.022. http://www.sciencedirect.com/science/article/pii/S0031320314002817CrossRef

10.

Demšar, J.: Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res. 7, 1–30 (2006). http://dl.acm.org/citation.cfm?id=1248547.1248548MathSciNetMATH

11.

Dietterich, T.G., Lathrop, R.H., Lozano-Prez, T.: Solving the multiple instance problem with axis-parallel rectangles. Artif. Intell. 89(1), 31–71 (1997). https://doi.org/10.1016/S0004-3702(96)00034-3. http://www.sciencedirect.com/science/article/pii/S0004370296000343CrossRefMATH

12.

Fernández-Delgado, M., Cernadas, E., Barro, S., Amorim, D.: Do we need hundreds of classifiers to solve real world classification problems? J. Mach. Learn. Res. 15(1), 3133–3181 (2014). http://dl.acm.org/citation.cfm?id=2627435.2697065MathSciNetMATH

13.

Gärtner, T., Flach, P.A., Kowalczyk, A., Smola, A.J.: Multi-instance kernels. In: Proceedings of the Nineteenth International Conference on Machine Learning, ICML 2002, pp. 179–186. Morgan Kaufmann Publishers Inc., San Francisco (2002). http://dl.acm.org/citation.cfm?id=645531.656014

14.

Gehler, P.V., Chapelle, O.: Deterministic annealing for multiple-instance learning. In: Artificial Intelligence and Statistics, pp. 123–130 (2007)

15.

Geurts, P., Ernst, D., Wehenkel, L.: Extremely randomized trees. Mach. Learn. 63(1), 3–42 (2006)CrossRef

16.

Kohout, J., Komárek, T., Čech, P., Bodnár, J., Lokoč, J.: Learning communication patterns for malware discovery in https data. Expert Systems with Applications 101, 129–142 (2018). https://doi.org/10.1016/j.eswa.2018.02.010. http://www.sciencedirect.com/science/article/pii/S0957417418300794CrossRef

17.

Leistner, C., Saffari, A., Bischof, H.: MIForests: multiple-instance learning with randomized trees. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010. LNCS, vol. 6316, pp. 29–42. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15567-3_3CrossRef

18.

Quinlan, J.R.: Induction of decision trees. Mach. Learn. 1(1), 81–106 (1986). https://doi.org/10.1023/A:1022643204877CrossRef

19.

Ruffo, G.: Learning single and multiple instance decision trees for computer security applications. University of Turin, Torino (2000)

20.

Stiborek, J., Pevný, T., Rehák, M.: Multiple instance learning for malware classification. Expert Syst. Appl. 93, 346–357 (2018). https://doi.org/10.1016/j.eswa.2017.10.036. http://www.sciencedirect.com/science/article/pii/S0957417417307170CrossRef

21.

Straehle, C., Kandemir, M., Koethe, U., Hamprecht, F.A.: Multiple instance learning with response-optimized random forests. In: 2014 22nd International Conference on Pattern Recognition, pp. 3768–3773, August 2014. https://doi.org/10.1109/ICPR.2014.647

22.

Tax, D.M.J.: A matlab toolbox for multiple-instance learning, version 1.2.2, Faculty EWI, Delft University of Technology, The Netherlands, April 2017

23.

Zhang, C., Platt, J.C., Viola, P.A.: Multiple instance boosting for object detection. In: Weiss, Y., Schölkopf, B., Platt, J.C. (eds.) Advances in Neural Information Processing Systems, vol. 18, pp. 1417–1424. MIT Press (2006). http://papers.nips.cc/paper/2926-multiple-instance-boosting-for-object-detection.pdf

24.

Zhang, J., Marszałek, M., Lazebnik, S., Schmid, C.: Local features and kernels for classification of texture and object categories: a comprehensive study. Int. J. Comput. Vision 73(2), 213–238 (2007)CrossRef

25.

Zhang, Q., Goldman, S.A.: Em-dd: an improved multiple-instance learning technique. In: Advances in Neural Information Processing Systems, pp. 1073–1080. MIT Press (2001)

Titel: Multiple Instance Learning with Bag-Level Randomized Trees
verfasst von: Tomáš Komárek
Petr Somol
Verlag: Springer International Publishing
Buch: Machine Learning and Knowledge Discovery in Databases
Print ISBN: 978-3-030-10924-0

Electronic ISBN: 978-3-030-10925-7

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-10925-7_16

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner