# MILDMS: Multiple Instance Learning via DD Constraint and Multiple Part Similarity

^{1}

^{2}

^{*}

## Abstract

**:**

## 1. Introduction

- We made the first attempt to convert MIL to multiple part similarity problem and analyzed their relationships.
- Our most positive and negative instance similarity with multiple part similarities combination method has shown to achieve significant improvements in robust MIL where noisy labels are provided.
- The one target concept and multiple target concepts problems in MIL can be tackled in one framework. Meanwhile, we combine the hand-crafted and CNN features into our framework, which can provide more powerful feature representation ability.
- Experiments on MIL dataset MUSK, PASCAL VOC, and COREL, etc., show that our proposal can outperform the state-of-the-art baselines including traditional MIL and deep MIL algorithms.

## 2. Related Works

## 3. Algorithm Overview

#### 3.1. The Analysis of MIL and Multiple Part Similarity

#### 3.2. Overview of Our Proposed MILDMS Algorithm

## 4. MILDMS Algorithm

#### 4.1. Review of Diverse Density (DD) Algorithm

#### 4.2. Target Concept Locating

#### 4.3. De-Noising Mislabeled Instances

#### 4.4. Multiple Part Similarity Kernel Construction

#### 4.5. MIL Kernel Construction

_{i}and B

_{j}, C

_{i}and C

_{j}are two sets that satisfy ${B}_{i}={C}_{i}\cup \left\{{x}_{i{h}_{i}^{+}},{x}_{i{h}_{i}^{-}}\right\}$ and ${B}_{j}={C}_{j}\cup \left\{{x}_{j{h}_{i}^{+}},{x}_{j{h}_{i}^{-}}\right\}$, ${k}_{p}({x}_{i{h}_{i}^{+}},{x}_{j{h}_{j}^{+}})$ and ${k}_{n}({x}_{i{h}_{i}^{-}},{x}_{j{h}_{j}^{-}})$ are the kernel functions used to compute the most positive and negative instance similarity, and ${k}_{o}({C}_{i},{C}_{j})$ is the predefined multiple part similarity kernel.

#### 4.6. Feature Extraction

#### 4.7. Algorithm View

Algorithm 1. Learning MIL Classifier |

Repeat iterationsFork^{+} = 1: MFor k^{−} = 1: M - Step 1:
- Solve the optimization (Equation (10)) to obtain potential target concepts P, Q and indicator matrix δ, ξ
- Step 2:
- Use C3 in Equation (13) to select the most positive and negative target concepts ${\left\{{t}_{i}\right\}}_{i=1}^{2}$
- Step 3:
- Denoise the mislabeled instance by applying Equation (12)
- Step 4:
- Compute the DD function using Equation (12) to check the constraints C4 in Equation (8)
EndEndUntil the constraint C4 is metFor (each training bag B_{i} in set B)
- Step 1:
- Choose the most positive and negative instances ${x}_{{ih}^{+}}$, ${x}_{{ih}^{-}}$ using Equation (13)
- Step 2:
- Optimize Equation (14) to obtain optimal flow and construct multiple part kernel using Equation (15)
EndOptimize Equation (18) to obtain the decision variables ${\alpha}^{\ast},{d}^{\ast}\mathrm{and}{b}^{\ast}$ |

Algorithm 2. Classifying MIL Bag |

For (each unknown bag B_{i} in set U)- Step 1:
- Choose the most positive and negative instances ${x}_{{ih}^{+}}$, ${x}_{{ih}^{-}}$ using Equation (13))
- Step 2:
- Optimize Equation (14) to obtain optimal flow and construct multiple part kernel using Equation (15))
- Step 3:
- Use Equation (19) to predict Bag B
_{i}’s label)
End |

## 5. Experiments

#### 5.1. Standard MIL Dataset

#### 5.2. Object Detection

#### 5.3. Image Classification Application

#### 5.4. Sensitivity to Labeling Noise

## 6. Conclusions

## Author Contributions

## Funding

## Conflicts of Interest

## References

- Liu, B.; Xiao, Y.; Hao, Z. A Selective Multiple Instance Transfer Learning Method for Text Categorization Problems. Knowl. Based Syst.
**2018**, 141, 178–187. [Google Scholar] [CrossRef] - Hu, K.; He, W.; Ye, J.; Zhao, L.; Peng, H.; Pi, J. Online Visual Tracking of Weighted Multiple Instance Learning via Neutrosophic Similarity-Based Objectness Estimation. Symmetry
**2019**, 11, 832. [Google Scholar] [CrossRef] - Yuan, C.H.; Xu, C.Y.; Wang, T.J.; Liu, F.; Zhao, Z.; Feng, P.; Guo, J. Deep multi-instance learning for end-to-end person re-identification. Multimed. Tools Appl.
**2018**, 77, 12437–12467. [Google Scholar] [CrossRef] - Manivannan, S.; Cobb, C.; Burgess, S.; Trucco, E. Subcategory Classifiers for Multiple-Instance Learning and Its Application to Retinal Nerve Fiber Layer Visibility Classification. IEEE Trans. Med. Imaging
**2017**, 36, 1140–1150. [Google Scholar] [CrossRef] [PubMed] [Green Version] - Dietterich, T.G.; Lathrop, R.H.; Lozano-Perez, T. Solving the multiple instance problem with axis-parallel retangles. Artif. Intell.
**1997**, 89, 31–71. [Google Scholar] [CrossRef] - Maron, O. Learning from Ambiguity. Ph.D. Thesis, MIT, Cambridge, MA, USA, 1998. [Google Scholar]
- Wang, J.; Zucker, J.D. Solving the multiple instance problem: A lazy learning approach. In Proceedings of the International Conference on Machine Learning (ICML), Stanford, CA, USA, 28 June–1 July 2001; pp. 1119–1126. [Google Scholar]
- Zhang, Q.; Goldman, S.A. Em-dd: An improved multiple-instance learning. In Proceedings of the Advances in Neural Information Processing Systems (NIPS), Vancouver, BC, Canada, 3–8 December 2001; pp. 1073–1080. [Google Scholar]
- Gartner, T.; Flach, P.A.; Kowalczyk, A.; Smola, A.J. Multi-instance kernels. In Proceedings of the International Conference on Machine Learning (ICML), Sydney, Australia, 8–12 July 2002; pp. 179–186. [Google Scholar]
- Andrews, S.; Tsochantaridis, I.; Hofmann, T. Support vector machines for multiple-instance learning. In Proceedings of the Advances in Neural Information Processing Systems (NIPS), Vancouver and Whistler, British Columbia, BC, Canada, 8–13 December 2003; pp. 561–568. [Google Scholar]
- Chen, Y.; Wang, J.Z. Image categorization by learning and reasoning with regions. J. Mach. Learn. Res.
**2004**, 5, 913–939. [Google Scholar] - Chen, Y.; Bi, J.; Wang, J. Miles: Multiple-instance learning via embedded instance selection. IEEE Trans. Pattern Anal. Mach. Intell.
**2006**, 28, 1931–1947. [Google Scholar] [CrossRef] - Zhou, Z.H.; Xu, J.M. On the relation between multi-instance learning and semi supervised learning. In Proceedings of the International Conference on Machine Learning (ICML), Corvallis, OR, USA, 20–24 June 2007; pp. 1167–1174. [Google Scholar]
- Zhou, Z.H.; Sun, Y.Y.; Li, Y.F. Multi-instance learning by treating instances as non-i.i.d. samples. In Proceedings of the International Conference on Machine Learning (ICML), Montreal, QC, Canada, 14–18 June 2009; pp. 1249–1256. [Google Scholar]
- Fu, Z.; Robles-Kelly, A.; Zhou, J. MILIS: Multiple instance learning with instance selection. IEEE Trans. Pattern Anal. Mach. Intell.
**2011**, 33, 958–977. [Google Scholar] - Erdem, A.; Erdem, E. Multiple-instance learning with instance selection via dominant sets. Lect. Notes Comput. Sci. SIMBAD
**2011**, 7005, 177–191. [Google Scholar] - Zhang, D.; He, J.R.; Si, L.; Lawrence, R. MILEAGE: Multiple Instance Learning with Global Embedding. In Proceedings of the International Conference on Machine Learning (ICML), Atlanta, GA, USA, 16–21 June 2013; pp. 82–90. [Google Scholar]
- Nguyen, D.T.; Nguyen, C.D.; Hargraves, R.; Kurgan, L.A.; Cios, K.J. mi-DS: Multiple-Instance Learning Algorithm. IEEE Trans. Cybern.
**2013**, 43, 143–154. [Google Scholar] [CrossRef] - Li, Z.; Geng, G.H.; Feng, J.; Peng, J.Y.; Wen, C.; Liang, J.L. Multiple instance learning based on positive instance selection and bag structure construction. Pattern Recogn. Lett.
**2014**, 40, 19–26. [Google Scholar] [CrossRef] - Xiao, Y.; Liu, B.; Hao, Z.; Cao, L. Smile: A similarity-based approach for multiple instance learning. IEEE Trans. Cybern.
**2014**, 44, 500–515. [Google Scholar] [CrossRef] [PubMed] - Zhang, Y.L.; Zhou, Z.H. Multi-instance learning with key instance shift. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Melbourne, Australia, 19–25 August 2017; pp. 3441–3447. [Google Scholar]
- Küçükaşcı, E.S.; Baydoğan, M.G. Bag encoding strategies in multiple instance learning problems. Inform. Sci.
**2018**, 32, 654–669. [Google Scholar] [CrossRef] - Wu, J.; Pan, S.; Zhu, X.; Zhang, C.; Wu, X. Multi-instance learning with discriminative bag mapping. IEEE Trans. Knowl. Data Eng.
**2018**, 30, 1065–1080. [Google Scholar] [CrossRef] - Wang, X.; Yan, Y.; Tang, P.; Bai, X.; Liu, W. Revisiting Multiple Instance Neural Networks. Pattern Recogn
**2016**, 74, 15–24. [Google Scholar] [CrossRef] - Maximilian, I.; Jakub, M.T.; Max, W. Attention-based Deep Multiple Instance Learning. In Proceedings of the International Conference on Machine Learning (ICML), Stockholm, Sweden, 10–15 July 2018; pp. 2127–2136. [Google Scholar]
- Liu, X.; Jiao, L.; Zhao, J.; Zhao, J.; Zhang, D.; Liu, F.; Yang, S.; Tang, X. Deep Multiple Instance Learning-Based Spatial–Spectral Classification for PAN and MS Imagery. IEEE Trans. Geosci. Remote. Sens.
**2018**, 56, 461–473. [Google Scholar] [CrossRef] - Li, X.; Zhang, Y.; Cui, Q.; Yi, X.; Zhang, Y. Tooth-Marked Tongue Recognition Using Multiple Instance Learning and CNN Features. IEEE Trans. Cybern.
**2019**, 49, 380–387. [Google Scholar] [CrossRef] - Wu, J.J.; Yu, Y.N.; Huang, C.; Yu, K. Deep multiple instance learning for image classification and auto-annotation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Boston, MA, USA, 7–12 June 2015; pp. 3460–3469. [Google Scholar]
- Lowe, G.D. Distinctive Image Features from Scale-Invariant Interest Points. Int. J. Comput. Vis.
**2004**, 60, 91–110. [Google Scholar] [CrossRef] - Grauman, K.; Darrell, T. The pyramid match kernel: Efficient learning with sets of features. J. Mach. Learn. Res.
**2007**, 8, 725–760. [Google Scholar] - Rubner, Y.; Tomasi, C.; Guibas, L. The Earth Mover’s Distance as a Metric for Image Retrieval. Int. J. Comput. Vis.
**2000**, 40, 99–121. [Google Scholar] [CrossRef] - Rakotomamonjy, A.; Bach, Y.; Grandvalet, Y. SimpleMKL. J. Mach. Learn. Res.
**2008**, 9, 2491–2521. [Google Scholar] - Holzinger, A.; Plass, M.; Kickmeier-Rust, M.; Holzinger, K.; Crişan, G.C.; Pintea, C.-M.; Palade, V. Interactive machine learning: Experimental evidence for the human in the algorithmic loop. Appl. Intell.
**2019**, 49, 2401–2414. [Google Scholar] [CrossRef] - Norouzi, M.; Fleet, D. Cartesian k-means. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Portland, OR, USA, 23–28 June 2013; pp. 3017–3024. [Google Scholar]
- Everingham, M.; Van Gool, L.; Williams, C.K.; Winn, J.; Zisserman, A. The pascal visual object classes (VOC) challenge. Int. J. Comput. Vis.
**2010**, 88, 303–338. [Google Scholar] [CrossRef]

**Table 1.**Multiple instance learning (MIL) data sets, with the respective number of positive and negative bags, features, and instances.

Data Set | Positive Bags | Negative Bags | Features | Instances |
---|---|---|---|---|

MUSK1 | 47 | 45 | 166 | 476 |

MUSK2 | 39 | 63 | 166 | 6598 |

Elephant | 100 | 100 | 230 | 1391 |

Fox | 100 | 100 | 230 | 1220 |

Tiger | 100 | 100 | 230 | 1320 |

**Table 2.**Results (in %) of proposed MILDMS, and many of the MIL algorithms available in the literature, with results provided for both MUSK and Images data sets.

Algorithm/Data Set | MUSK1 | MUSK2 | Elephant | Tiger | Fox | Average |
---|---|---|---|---|---|---|

MILDMS | 91.9 | 92.2 | 84.40 | 87.10 | 66.80 | 84.48 |

APR [5] | 92.4 | 89.2 | / | / | / | 90.80 |

SMILE [20] | 91.3 | 91.6 | 84.30 | 86.50 | 65.90 | 83.92 |

MILES [12] | 87.7 | 86.3 | 84.10 | 80.70 | 63.00 | 80.54 |

DD [6] | 84.8 | 84.9 | 84.80 | 81.50 | 64.30 | 81.52 |

DD-SVM [11] | 85.8 | 91.3 | 82.90 | 75.80 | 55.00 | 77.76 |

Attention [25] | 89.1 | 84.1 | 83,20 | 73,40 | 49,10 | 77.28 |

Gated-Attention [25] | 89.8 | 86.2 | 81.45 | 72.20 | 59.40 | 78.23 |

MI-Net with DS [24] | 89.8 | 85.1 | 78.30 | 72.10 | 56.10 | 75.24 |

**Table 3.**Results (in %) for COREL 2000: average accuracy, and the 95%-confidence interval (in brackets).

© 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

## Share and Cite

**MDPI and ACS Style**

Wen, C.; Li, Z.; Qu, J.; Fan, Q.; Li, A.
MILDMS: Multiple Instance Learning via DD Constraint and Multiple Part Similarity. *Symmetry* **2019**, *11*, 1080.
https://doi.org/10.3390/sym11091080

**AMA Style**

Wen C, Li Z, Qu J, Fan Q, Li A.
MILDMS: Multiple Instance Learning via DD Constraint and Multiple Part Similarity. *Symmetry*. 2019; 11(9):1080.
https://doi.org/10.3390/sym11091080

**Chicago/Turabian Style**

Wen, Chao, Zhan Li, Jian Qu, Qingchen Fan, and Aiping Li.
2019. "MILDMS: Multiple Instance Learning via DD Constraint and Multiple Part Similarity" *Symmetry* 11, no. 9: 1080.
https://doi.org/10.3390/sym11091080