Self-adaptive LSH encoding for multi-instance learning

Dongkuan Xu, Jia Wu*, Dewei Li, Yingjie Tian, Xingquan Zhu, Xindong Wu

*Corresponding author for this work

Research output: Contribution to journalArticle

6 Citations (Scopus)


Multi-instance learning (MIL) is commonly used to classify a set of instances, also known as a bag, where labels for the training set are only available for each bag. Many MIL methods exist, but they often suffer from high computation complexity and the key information from MIL being ignored, which deteriorates the classification performance. Recently, locality-sensitive hashing (LSH), with its high scalability, has shown the ability in enhancing MIL performance. However, for these LSH-based methods, the fixed number of bits is used to represent each projected dimension, resulting in subtle information loss and the algorithm performance reduction. In this paper, we propose a self-adaptive LSH encoding method for MIL, termed as SALE. SALE uses LSH to generate the primary batches, followed by a self-adaptive process for reconstruction. Reconstructed bags are transformed into random super histograms (RSH) using an incomplete coding method, and then weighted through a scheme that takes advantage of key instances. These weighted RSHs are used to train the learning model. SALE efficiently deals with large MIL problems, due to its low complexity and RSH's ability to exploit key information of MIL. Experiments demonstrate SALE's good performance compared to state-of-the-art MIL methods.

Original languageEnglish
Pages (from-to)460-482
Number of pages23
JournalPattern Recognition
Publication statusPublished - 1 Nov 2017
Externally publishedYes


  • Locality-sensitive hashing
  • Machine learning
  • Multi-instance learning
  • Self-adaptive learning

Fingerprint Dive into the research topics of 'SALE: Self-adaptive LSH encoding for multi-instance learning'. Together they form a unique fingerprint.

Cite this