PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Multi-Instance Multi-Label Learning

Sheng-Jun Huang, Zhi-Hua Zhou

arXiv:1310.2049v1cs.LG

TL;DR

MIML tasks involve objects represented by multiple instances and associated with multiple labels, while existing approaches have difficulty scaling to large data. MIMLfast uses a shared space and stochastic optimization, and on data with 20,000 bags and 180,000 instances it is more than 100 times faster than existing MIML approaches.

  • Problem

    MIML covers objects represented by multiple instances and labels, but existing approaches’ complexity and low efficiency limit their application to large-scale data.

    Source: §1 · p. 2, §5 · p. 21

  • Method

    MIMLfast exploits label relations in a shared space and uses stochastic gradient descent to optimize an approximated ranking loss.

    Source: §1 · p. 2, §5 · p. 21

  • Results

    On data with 20,000 bags and 180,000 instances, MIMLfast is more than 100 times faster than existing MIML approaches.

    Source: §3.3 · p. 15

  • Takeaways & Limitations

    MIMLfast combines shared-space label-relation exploitation with discovery of sub-concepts for complicated labels.

    Source: §5 · p. 21

    The conclusion identifies optimizing losses other than ranking loss as future work.

    Source: §5 · p. 21

Abstract

from arXiv · show

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.

1. Introduction

MIML addresses objects represented by multiple instances and associated with multiple labels, but existing approaches struggle with large-scale data. MIMLfast combines a shared label space with efficient linear models, while identifying representative instances and sub-concepts.

1. Introduction

  • MIML represents objects with multiple instances and labels, while existing approaches’ complexity and low efficiency limit their use on large-scale data.The introduction frames these objects as a motivation for the MIML framework.Source: §1 · p. 2
  • MIMLfast learns a shared space for all labels, then trains label-specific linear models as an efficient approximation of the MIML problem.The shared space uses relations among labels.Source: §1 · p. 2
  • Stochastic gradient descent optimizes an approximated ranking loss by sampling a bag, a relevant label, and an irrelevant label, and ranking the relevant label first.The desired ordering is optimized when the relevant label does not already rank ahead.Source: §1 · p. 2
  • MIMLfast identifies a representative instance for each label, offering a way to examine relations between input patterns and label semantics.The model is trained at the instance level, and selects the instance with the maximum prediction for a label.Source: §1 · pp. 2–3
  • For complicated labels, MIMLfast also proposes discovering sub-concepts.The introduction presents sub-concept discovery as another contribution alongside representative-instance identification.Source: §1 · p. 3

2. The MIMLfast Approach

MIMLfast combines a low-dimensional space shared across labels with label-specific models and sub-concepts, training them with an approximated ranking loss optimized by stochastic gradient descent. For multi-label prediction, it scores bags through their highest-scoring instances and uses a dummy label to select labels scoring above it.

2. The MIMLfast Approach

  • A shared low-dimensional mapping and label-specific models let examples across labels jointly shape the representation, preserving label relations ignored by independent models.The two components are optimized interactively, so labels with strong relations can help each other.Source: §2 · p. 3
  • For complicated labels, MIMLfast learns multiple sub-concept models and assigns an example to the sub-concept with the highest prediction.The approach assumes K sub-concepts per label but permits empty sub-concepts, including cases where examples occupy only one.Source: §2 · p. 4
  • A bag’s score for a label is the maximum score among its instances, making the highest-scoring instance the key instance for that label.This follows the assumption that a bag is positive if and only if it contains at least one positive instance.Source: §2 · p. 4
  • To optimize ranking loss, MIMLfast uses a hinge-loss surrogate and stochastic gradient descent on sampled bag, relevant-label, and irrelevant-label triplets.Rather than compare a relevant label against every irrelevant label, it samples irrelevant labels until finding one ranked ahead, then estimates the ranking count from the sampling step.Source: §2 · p. 5
  • The ranking-count approximation samples irrelevant labels until a violated label is found, then estimates the count using the number of sampling steps.A violated label is ranked before the relevant label; the estimate is the floor of the number of irrelevant labels divided by the step at which the first violation appears.Source: §2 · p. 6

The MIMLfast Approach

  • Because a multi-label test bag may have multiple relevant labels, its relevant-label count is unknown when choosing from the ranked list.The passage frames this as the difficulty that the dummy-label procedure addresses.Source: §2 · p. 10
  • The dummy label is trained to rank after relevant labels and before irrelevant labels, addressing the unknown number of relevant labels in a test bag.When sampling a dummy label, the irrelevant set contains all irrelevant labels; otherwise, it also includes the dummy label.Source: §2 · p. 10
  • At test time, MIMLfast ranks labels by prediction value and selects as relevant those scoring above the dummy label.The test bag's label scores produce a ranked list.Source: §2 · p. 10

3. Experiments

The experiments assess MIMLfast across datasets and settings, examining performance and scalability alongside key-instance detection, sub-concept discovery, and variant comparisons. They also illustrate discovered sea concepts, with reported benefits varying by comparison and setting.

3.1. Settings

  • The experiments compare six state-of-the-art MIML methods across six moderate-sized and two large datasets, evaluating five commonly used criteria.The criteria are hamming loss, one error, coverage, ranking loss, and average precision; data partitions are repeated 30 times and results averaged.Source: §3.1 · pp. 10, 11, 14

3.2. Performance Comparison

  • On six moderate-sized data sets, MIMLfast achieves the best performance in most cases; it outperforms DBA on all data sets, while KISAR is comparable on Scene and less effective elsewhere.RankLossSIM is comparable to MIMLfast on 4 of 6 data sets and achieves better coverage and ranking loss on Bird Song.Source: Table 2 · p. 12, §3.2 · p. 14
  • At 25,000 bags, only MIMLfast works on Corel5K and MSRA, and it performs better than the other methods on both large datasets.The comparison varies Corel5K from 1,000 to 5,000 bags and MSRA from 5,000 to 30,000 bags; MIMLBoost [26] returns no result within 24 hours at even the smallest size.Source: Figure 1 · p. 13, Figure 2 · p. 13, §3.1 · p. 13

3.3. Efficiency Comparison

  • At 20,000 bags and 180,000 instances, MIMLfast is more than 100 times faster than the most efficient existing approach; on larger data, no existing approach returns a result within 24 hours, while MIMLfast takes 12 minutes.Source: §3.3 · p. 15

3.4. Key Instance Detection

  • Assuming each label is triggered by its most positive instance, MIMLfast identifies reasonable key instances for labels.Examples on MSRA illustrate detected instances, with image regions highlighted; an instance may correspond to multiple clustered regions rather than one region.Source: Figure 5 · p. 16, §3.4 · pp. 16–17
  • MIMLfast detects key instances better than RankLossSIM on two larger datasets, comparably on Letter Carroll, and slightly worse on the remaining dataset; KISAR is less accurate.The comparison evaluates key-instance detection on four datasets with available instance labels.Source: §3.4 · p. 17

3.5. Sub-Concept Discovery

  • Compared with neglecting sub-concepts (K = 1), exploiting sub-concepts yields better performance at K = 5, 10, and 15; differences among larger K values are not very significant.Source: §3.5 · p. 18
  • Overly large K does not degrade performance too much because some sub-concepts may capture no examples, but it can hamper efficiency.The paper notes that differences among results at different K values are not very significant.Source: §3.5 · p. 18
  • An illustration of the sea label shows distinct sub-concepts, including sea with beach and blue sky and big waves.Figure 6 presents example images for the top four discovered sea sub-concepts.Source: §3.5 · p. 18, Figure 6 · p. 19

3.6. Comparison with Variants

  • MIMLfast is significantly better than V1 on all criteria, supporting shared-space learning over independent label models.V1 omits W0 and learns a linear model for each label; Table 5 reports the comparison on two benchmark datasets.Source: Table 5 · p. 19, §3.6 · p. 20
  • MIMLfast significantly outperforms V2 on hamming loss and is comparable on the other four criteria, suggesting the dummy label separates relevant from irrelevant labels without changing their rank.V2 selects the top r labels as relevant, where r is the average number of relevant labels in the training data.Source: Table 5 · p. 19, §3.6 · p. 20

4. Related Work

Existing MIML approaches have been useful in applications but are computationally demanding on larger data. MIMLfast combines a shared-space approach with supervised sub-concept discovery, unlike related single-label or clustering approaches.

4. Related Work

  • Prior work includes approaches that reduce MIML to single-instance multi-label or multi-instance single-label learning, as well as generative, nearest-neighbor, neural-network, and image-annotation methods.The cited examples include MIMLBoost, a generative model, nearest-neighbor and neural-network approaches and, and a hidden conditional random field.Source: §4 · p. 20
  • Ranking-loss optimization for MIML instance annotation and clustering-based label prototypes are among related approaches.A WARP-loss technique for image annotation addressed a different single-instance single-label problem.Source: §4 · p. 20
  • Existing MIML approaches were successful in applications but mostly handled moderate-sized data because of high computational load.The paper identifies efficiency as a need for large-scale MIML.Source: §4 · p. 20
  • Unlike clustering-based sub-concept discovery for single-label learning, MIMLfast uses label information and a supervised model to discover sub-concepts for MIML.The cited clustering approach was focused on single-label learning.Source: §4 · pp. 20–21

5. Conclusion

MIMLfast addresses the computational demands of applying MIML to large-scale problems with a two-level linear model and approximated ranking-loss optimization. It exploits label relations and sub-concepts, and can detect key instances for labels.

5. Conclusion

  • MIMLfast targets large-scale MIML, where existing approaches are usually too time-consuming.The paper describes MIML as effective in many applications but existing methods as too slow for large-scale problems.Source: §5 · p. 21
  • MIMLfast optimizes an approximated ranking loss with SGD using a two-level linear model.The model learns a shared space and then trains label-specific models.Source: §5 · p. 21
  • MIMLfast exploits label relations in a shared space and discovers sub-concepts for complicated labels.These are the paper's stated routes to effectiveness.Source: §5 · p. 21
  • MIMLfast can detect a key instance for each label, offering a chance to discover relations between input patterns and label semantics.The paper presents this as an opportunity to understand the relation between inputs and output labels.Source: §5 · p. 21
  • The authors identify optimizing loss functions other than ranking loss as future work.The conclusion states that they will try to optimize other loss functions.Source: §5 · p. 21
Loading 1310.2049v1…