A fast Markov chain based algorithm for MIML learning

Kwok Po NG, Qingyao Wu, Chenyang Shen*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

3 Citations (Scopus)


Multi-instance multi-label (MIML) learning is one of challenging research problems in machine learning. In the literature, there are several methods for solving MIML problems. However, they may take a long computational time and have a huge storage cost for large MIML data sets. The main aim of this paper is to propose and develop an efficient Markov Chain learning algorithm for MIML problems, especially for data represented by non-negative features. Our idea is to perform labels classification iteratively through two Markov chains constructed by using objects and features respectively. The classification of objects can be obtained by using labels propagation via training data in the iterative method. Moreover, we demonstrate that the proposed method can be formulated by considering normalized linear kernel. Because linear kernel function is explicit and separable, it is not necessary to compute and store a huge affinity matrix among objects/instances compared with the use of other kernel functions. Therefore, both the storage and computational time of the proposed algorithm are very efficient. Experimental results are presented to show that the classification performance of the proposed method using normalized linear kernel function is about the same as those using the other kernel functions, while the required computational time is much less, which together suggest that the linear kernel can be good enough for MIML problem. Also experimental results on some benchmark data sets are reported to illustrate the effectiveness of the proposed method in one-error, ranking loss, coverage and average precision, and show that it is competitive with the other MIML methods.

Original languageEnglish
Pages (from-to)763-777
Number of pages15
Publication statusPublished - 5 Dec 2016

Scopus Subject Areas

  • Computer Science Applications
  • Cognitive Neuroscience
  • Artificial Intelligence

User-Defined Keywords

  • Iterative Method
  • Labels Propagation
  • Markov Chains
  • Multi-Instance Multi-Label Learning


Dive into the research topics of 'A fast Markov chain based algorithm for MIML learning'. Together they form a unique fingerprint.

Cite this