PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Instance Multi-Label Learning

Zhi-Hua Zhou, Min-Ling Zhang, Sheng-Jun Huang, Yu-Feng Li

arXiv:0808.3231v4cs.LGcs.AI

TL;DR

Many real-world problems do not fit prevailing learning frameworks, motivating MIML, which represents examples with multiple instances and class labels. The paper develops MIML algorithms and reports good performance, including direct Svm outperforming indirect Svm.

  • Problem

    Many real-world problems do not fit prevailing learning frameworks, motivating a representation for complicated objects with multiple semantic meanings.

  • Method

    The paper proposes the MIML framework and algorithms including degeneration-based methods, direct regularization, InsDif, and clustering-based representation transformation.

  • Results

    MIML can lead to good performance on problems involving complicated objects with multiple semantic meanings, and direct Svm outperforms indirect Svm.

  • Takeaways & Limitations

    MIML provides a framework for learning from examples represented with multiple instances and multiple labels.

  • Takeaways & Limitations

    The regularization assumption simplifies realization but over-simplifies the real scenario, where all class labels rarely share the same condition.

Abstract

from arXiv · show

In this paper, we propose the MIML (Multi-Instance Multi-Label learning) framework where an example is described by multiple instances and associated with multiple class labels. Compared to traditional learning frameworks, the MIML framework is more convenient and natural for representing complicated objects which have multiple semantic meanings. To learn from MIML examples, we propose the MimlBoost and MimlSvm algorithms based on a simple degeneration strategy, and experiments show that solving problems involving complicated objects with multiple semantic meanings in the MIML framework can lead to good performance. Considering that the degeneration process may lose information, we propose the D-MimlSvm algorithm which tackles MIML problems directly in a regularization framework. Moreover, we show that even when we do not have access to the real objects and thus cannot capture more information from real objects by using the MIML representation, MIML is still useful. We propose the InsDif and SubCod algorithms. InsDif works by transforming single-instances into the MIML representation for learning, while SubCod works by transforming single-label examples into the MIML representation for learning. Experiments show that in some tasks they are able to achieve better performance than learning the single-instances or single-label examples directly.

1 Introduction

Many real-world objects have multiple semantic meanings, making it difficult to choose appropriate labels when traditional single-instance representations are used. The paper proposes MIML, which represents examples with multiple instances and multiple labels, and develops algorithms for learning in or transforming into this framework.

  • Motivation: Objects such as images, documents, and web pages may simultaneously belong to multiple semantic concepts.Examples include images associated with grasslands, lions, and Africa, and web pages associated with news, sports, and soccer.
  • Problem: Choosing the appropriate semantic meaning or labels for objects involving multiple concepts is a fundamental difficulty.The paper describes both selecting the relevant meaning for a scenario and assigning proper class labels as challenging.
  • MIML framework: MIML represents each example with multiple instances and associates it with multiple class labels.The representation is intended for complicated objects whose relevant patterns may become more explicit through multiple instances.
  • Algorithms: MimlBoost and MimlSvm learn from MIML examples through a degeneration strategy, while D-MimlSvm tackles MIML problems directly in a regularization framework.The direct algorithm is motivated by the possibility that degeneration loses information and is reported to outperform the indirect MimlSvm algorithm.
  • Learning without real objects: When real objects are unavailable, InsDif transforms single instances into MIML examples and can outperform direct single-instance learning in some tasks.The paper attributes this potential benefit to detaching label-related information mixed within a single-instance representation.
  • Learning without real objects: SubCod discovers sub-concepts before transforming single-label data into MIML examples and can outperform direct single-label learning in some tasks.The approach targets high-level concepts whose lower-level concepts may otherwise be mixed together.

2 Related Work

Related work covers multi-label and multi-instance learning as distinct frameworks, along with algorithms that adapt common learning methods to each setting. The paper targets their combination, whose greater generality makes learning more difficult.

  • Multi-label learning: Multi-label learning studies objects associated with multiple valid class labels rather than a single label.Existing approaches include binary decompositions, label ranking, label-correlation methods, and classifiers based on trees, neural networks, neighbors, and SVMs.
  • Relation to MIML: Combining multiple instances with multiple labels increases generality and consequently makes the learning problem more difficult.The paper positions MIML as the intersection of the two learning settings rather than as a restriction to one label per instance.
  • Multi-label learning: Multi-label learning has been applied mainly to text categorization and also to scene classification, image and video annotation, bioinformatics, and association rule mining.The related work emphasizes substantial activity in text applications while listing several additional application areas.
  • Multi-instance learning: Multi-instance learning represents each real-world object as a bag of instances associated with one class label.A bag is positive when it contains at least one positive instance, while instance-level labels remain unknown during training.
  • Multi-instance learning: Multi-instance learning has developed algorithms based on diverse density, nearest neighbors, trees, neural networks, rules, SVMs, kernels, ensembles, and logistic regression.Many methods adapt single-instance supervised learning by shifting discrimination from instances to bags.
  • Multi-instance learning: Standard multi-instance learning often assumes a key positive instance, although later work considers alternatives to that assumption.Several methods define a positive bag through its most positive instance or identify a key instance explicitly.

3 The MIML Framework

MIML represents each example with multiple instances and multiple labels, addressing ambiguity in both input and output spaces. This representation is intended for complicated objects with multiple semantic meanings and can also support learning through transformed sub-concepts.

  • MIML definition: MIML describes examples as sets of instances associated with sets of class labels.Its target function maps 2X to 2Y.
  • Framework comparison: Multi-instance learning models input ambiguity, multi-label learning models output ambiguity, and MIML considers both simultaneously.The paper contrasts these frameworks as alternative ways of representing real-world objects.
  • Motivation: MIML is presented as more natural and convenient for objects with input and output ambiguity.The paper argues that meaningful representations can make learning tasks easier to tackle.
  • Representation benefits: Transforming multi-label examples into MIML examples may increase the training instances available for each label.The paper also states that relations between input patterns and semantic meanings may become easier to discover.
  • Representation benefits: MIML can help learn complicated single-label concepts by exploiting lower-level sub-concepts that are less ambiguous and easier to learn.The paper illustrates this idea with the concept Africa and sub-concepts such as trees, lions, elephants, and grassland.

4 Solving MIML Problems by Degeneration

The paper develops two degeneration strategies that convert MIML problems into multi-instance or multi-label learning tasks before applying existing learning methods. Experiments report good performance for simple MIML algorithms, with MIML methods outperforming non-MIML methods on the reported tasks.

  • General degeneration solutions: MIML can be transformed into multi-instance learning or multi-label learning, which can then be connected to traditional supervised learning.These are presented as two general degeneration solutions.
  • General degeneration solutions: Solution A uses multi-instance learning as a bridge, while Solution B uses multi-label learning as a bridge.Each solution specifies a representation transformation followed by a corresponding learning task.
  • MimlBoost: MimlBoost decomposes MIML into a series of multi-instance tasks by treating each label as a task.Its construction creates |Y| labeled multi-instance bags for each original MIML example, yielding m × |Y| bags.
  • Assumptions: MimlBoost assumes that labels are independent and that all instances in a bag contribute independently and equally to its label.These assumptions arise from the MiBoosting implementation used in the degeneration approach.
  • MimlSvm: MimlSvm uses clustering-based representation transformation followed by multi-label SVM learning.The paper presents MimlBoost and MimlSvm as simple illustrations of the two degeneration solutions.
  • Experimental results: On scene classification, all MIML algorithms achieved the best performance on every evaluation criterion, and reported pairwise tests found broad significant advantages over non-MIML methods.The comparisons include significant improvements over AdtBoost.MH, MlSvm, RankSvm, and Ml-knn on varying subsets of criteria.
  • Experimental results: On text categorization, the best performance on all evaluation criteria was always attained by MIML algorithms.MimlSvm and MimlSvmmi were significantly better than all non-MIML algorithms, while MimlNn and MimlBoost also showed broad advantages.

5 Solving MIML Problems by Regularization

D-MimlSvm addresses information loss from degeneration by learning MIML problems directly in a regularization framework. It models label relatedness, bag–instance predictions, and class imbalance, then uses an efficient optimization procedure with reported advantages over degeneration-based methods.

  • 5 Solving MIML Problems by Regularization: D-MimlSvm is proposed as a direct regularization-based MIML method because degeneration may lose information.It is developed directly from the regularization framework rather than through the earlier degeneration methods.
  • 5 Solving MIML Problems by Regularization: The method assumes labels attached to the same example are related and combines label-set loss with losses on bags and constituent instances.Its bag–instance relationship uses the common multi-instance assumption that bag strength equals the maximum instance strength for a label.
  • 5 Solving MIML Problems by Regularization: Its empirical loss uses two terms: ground-truth versus predicted label-set loss and bag versus instance-prediction loss, balanced by λ.The paper uses hinge loss for the first term and sets the comparison loss l(v1, v2) to l1 loss.
  • 5 Solving MIML Problems by Regularization: A regularizer controls the trade-off between discrepancy and commonness among label-specific functions through μ.Large μ makes discrepancy more important, while small μ makes commonness more important.
  • 5 Solving MIML Problems by Regularization: An efficient algorithm makes the large quadratic program tractable by exploiting redundant constraints and solving a smaller quadratic program.The optimization problem contains many constraints and variables, while the resulting procedure is guaranteed to converge to a local minimum.

6 Solving Single-Instance Multi-Label Problems through MIML Transformation

InsDif makes MIML useful for single-instance multi-label data by transforming each example into label-specific instances before applying an MIML learner. On Yeast and web-page categorization, InsDif and variants generally outperform or compete strongly with standard multi-label methods.

  • Motivation and approach: InsDif addresses single-instance multi-label data when the original objects are unavailable by transforming examples into MIML bags.The transformation creates one instance per class label to make label-specific information more explicit.
  • First-stage transformation: Each class label receives a prototype vector obtained by averaging its associated training instances.The prototype approximates a profile of common characteristics for that class.
  • First-stage transformation: Each example becomes a bag whose instances encode differences between the example and class prototypes, with bag size equal to the number of labels.The difference vector is treated as a distance-like representation related to spatial distribution.
  • Second-stage learning: InsDif then applies an MIML algorithm to the transformed training set and transforms test examples before prediction.MimlNn is the default second-stage learner, while other MIML algorithms produce evaluated variants.
  • Results: On Yeast, InsDif is significantly better than all compared multi-label algorithms on every criterion except coverage, where it is not significantly different from Ml-knn.InsDifMIMLSVMmi is significantly better in more than 65% of cases and never significantly inferior.
  • Results: On eleven web-page categorization data sets, InsDif is significantly better than compared algorithms in more than 79% of cases, while InsDifMIMLSVM leads average recall and average F1.The paper concludes that MIML can be useful for observational objects already represented by a single instance.

7 Solving Multi-Instance Single-Label Problems through MIML Transformation

SubCod makes MIML applicable to multi-instance single-label data by discovering sub-concepts, learning their multi-label representation, and mapping predictions back to original labels. Experiments find SubCod and its variants competitive with multi-instance learners, especially on Musk2.

  • Motivation and approach: SubCod addresses multi-instance single-label data without access to the original objects by transforming each example into an MIML example.It discovers sub-concepts from the instances and uses them as multiple labels.
  • Sub-concept discovery: SubCod discovers sub-concepts by clustering all instances with a Gaussian mixture model and treating mixture components as sub-concepts.The Gaussian mixture model is learned with EM.
  • Derived multi-labels: For each bag, SubCod assigns a derived label to a sub-concept when at least one instance in the bag belongs to that component.Bags with the same original single label may receive different derived multi-labels.
  • Label polishing: A maximum-margin optimization polishes the derived multi-labels using their relation to the original labels before producing the MIML training set.The optimization alternates between solving for classifier parameters and label-adjustment variables.
  • Two-stage prediction: SubCod applies an MIML learner to the transformed bags, then trains a supervised classifier to map predicted sub-concepts back to original labels.At test time, predictions pass through the MIML learner and then the traditional classifier.
  • Results: Across the experiments, the results suggest that MIML can be useful for observational data represented as multi-instance single-label examples.The evaluation uses Musk1, Musk2, Elephant, Tiger, and Fox data sets.
  • Results: SubCod and its variants are competitive with state-of-the-art multi-instance learners, with much better performance than other algorithms on Musk2.The authors associate this result with Musk2 being favorable to SubCod’s sub-concept discovery process.

8 Conclusion

The paper presents MIML as a representation for complicated objects with ambiguous input and output semantics, develops indirect and direct learning algorithms, and reports useful performance in several settings.

  • The paper formalizes MimlBoost and MimlSvm using a simple degeneration strategy for learning from MIML examples.
  • MIML represents each example with multiple instances and multiple class labels, targeting objects with multiple semantic meanings.
  • Experiments on scene classification and text categorization show that learning complicated objects under MIML can lead to good performance.
  • Because degeneration may lose information, D-MimlSvm tackles MIML problems directly in a regularization framework and outperforms indirect MimlSvm.
  • InsDif transforms single-instance data into MIML examples and achieves better performance than direct single-instance learning in some tasks.
  • The paper notes that MIML may make collapsed structure easier to exploit and increase training instances available for each label.
  • SubCod discovers sub-concepts, transforms single-label data into MIML examples, and achieves better performance than direct single-label learning in some tasks.
  • MIML may also support understanding why an object receives a label, although identifying connections between atomic input and output patterns remains unrealized in this paper.

A Pseudo-codes of the Learning Algorithms

The appendix lists pseudo-code tables and procedural steps for MimlBoost, MimlSvm, an efficient algorithm for Eq. 24, InsDif, and SubCod.

  • The appendix provides dedicated pseudo-code tables for MimlBoost, MimlSvm, InsDif, and SubCod.
  • The iterative procedure samples constraints, computes their losses, finds a cutting plane, and repeats until the constraint set stops changing.
  • The boosting procedure computes bag-level error rates and updates weights using exp[(2e(i) − 1)c_t] before renormalization.
  • The appendix also includes an efficient algorithm for Eq. 24 alongside the SubCod algorithm table.
  • One degeneration-based learning step assigns each bag label to its instances, weights instances by W(i)/n_i, and builds an instance-level predictor.

B Parameter Settings of the Learning Algorithms

The appendix includes parameter-sensitivity figures for MimlBoost, MimlSvm, InsDif, and AdtBoost.MH across scene and Yeast data.

  • Figure B.1 compares MimlBoost and AdtBoost.MH performance across different boosting rounds on scene classification data.
  • Figure B.2 examines MimlSvm performance under different k values on scene classification data.
  • Figure B.3 examines InsDif performance under different M settings on the Yeast gene data set.
  • Figure B.4 compares AdtBoost.MH performance across different boosting rounds on the Yeast gene data set.

C Web Page Data Sets

This appendix section describes the web-page data sets and points to results on eleven Yahoo data sets.

  • Table C.1 describes web-page data-set characteristics after term selection.
  • The table defines PMC as the percentage of documents with multiple categories, ANL as average labels per document, and PRC as the percentage of rare categories.
  • Figure C.1 presents results on the eleven Yahoo data sets.
Loading 0808.3231v4…