Fast Multi-Instance Multi-Label Learning
  In many real-world tasks, particularly those involving data objects with
complicated semantics such as images and texts, one object can be represented
by multiple instances and simultaneously be associated with multiple labels.
Such tasks can be formulated as multi-instance multi-label learning (MIML)
problems, and have been extensively studied during the past few years. Existing
MIML approaches have been found useful in many applications; however, most of
them can only handle moderate-sized data. To efficiently handle large data
sets, in this paper we propose the MIMLfast approach, which first constructs a
low-dimensional subspace shared by all labels, and then trains label specific
linear models to optimize approximated ranking loss via stochastic gradient
descent. Although the MIML problem is complicated, MIMLfast is able to achieve
excellent performance by exploiting label relations with shared space and
discovering sub-concepts for complicated labels. Experiments show that the
performance of MIMLfast is highly competitive to state-of-the-art techniques,
whereas its time cost is much less; particularly, on a data set with 20K bags
and 180K instances, MIMLfast is more than 100 times faster than existing MIML
approaches. On a larger data set where none of existing approaches can return
results in 24 hours, MIMLfast takes only 12 minutes. Moreover, our approach is
able to identify the most representative instance for each label, and thus
providing a chance to understand the relation between input patterns and output
label semantics.
