Skip to page content
USDA Forest Service

Research & Development Treesearch

Treesearch Home
About Treesearch
Contact Us
Research & Development
Forest Products Lab
International Institute of Tropical Forestry
Pacific Northwest
Pacific Southwest
Rocky Mountain
Southern Research Station
Help - We Participate  Government Made Easy

Global Forest Information Service

US Forest Service
P.O. Box 96090
Washington, D.C.

(202) 205-8333

You are here: Home / Search / Publication Information
Bookmark and Share

Publication Information

View PDF (2.1 MB)

Title: Instance annotation for multi-instance multi-label learning

Author: Briggs, F.; Fern, X.Z.; Raich, R.; Lou, Q.;

Date: 2013

Source: ACM Transactions on Knowledge Discovery from Data,

Publication Series: Scientific Journal (JRNL)

Description: Multi-instance multi-label learning (MIML) is a framework for supervised classification where the objects to be classified are bags of instances associated with multiple labels. For example, an image can be represented as a bag of segments and associated with a list of objects it contains. Prior work on MIML has focused on predicting label sets for previously unseen bags. We instead consider the problem of predicting instance labels while learning from data labeled only at the bag level. We propose a regularized rank-loss objective designed for instance annotation, which can be instantiated with different aggregation models connecting instance-level labels with bag-level label sets. The aggregation models that we consider can be factored as a linear function of a “support instance” for each class, which is a single feature vector representing a whole bag. Hence we name our proposed methods rank-loss Support Instance Machines (SIM). We propose two optimization methods for the rank-loss objective, which is nonconvex. One is a heuristic method that alternates between updating support instances, and solving a convex problem in which the support instances are treated as constant. The other is to apply the constrained concave-convex procedure (CCCP), which can also be interpreted as iteratively updating support instances and solving a convex problem. To solve the convex problem, we employ the Pegasos framework of primal subgradient descent, and prove that it finds an ε-suboptimal solution in runtime that is linear in the number of bags, instances, and 1 ε. Additionally, we suggest a method of extending the linear learning algorithm to nonlinear classification, without increasing the runtime asymptotically. Experiments on artificial and real-world datasets including images and audio show that the proposed methods achieve higher accuracy than other loss functions used in prior work, e.g., Hamming loss, and recent work in ambiguous label classification.

Keywords: algorithms, performance, experimentation, instance annotation, image annotation, multi-instance, multi-label, support vector machine, subgradient, bioacoustics

Publication Notes:

  • We recommend that you also print this page and attach it to the printout of the article, to retain the full citation information.
  • This article was written and prepared by U.S. Government employees on official time, and is therefore in the public domain.



Briggs, F.; Fern, X.Z.; Raich, R.; Lou, Q. 2013. Instance annotation for multi-instance multi-label learning. ACM Transactions on Knowledge Discovery from Data. 7(3): Art 14. 30 p.


 [ Get Acrobat ]  Get the latest version of the Adobe Acrobat reader or Acrobat Reader for Windows with Search and Accessibility

USDA logo which links to the department's national site. Forest Service logo which links to the agency's national site.