# Dynamic Programming for Instance Annotation in Multi-instance Multi-label Learning

arXiv: https://arxiv.org/abs/1411.4068 · HTML: https://mlsanity.com/paper/1411.4068/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2014.

## Built on by (most cited first, 2 of 2)

- [Evaluating AI systems under uncertain ground truth: a case study in dermatology](https://mlsanity.com/paper/2307.02191/) (2023)
- [Exploring Partial Multi-Label Learning via Integrating Semantic Co-occurrence Knowledge](https://mlsanity.com/paper/2507.05992/) (2025)

## Abstract (arXiv)

Labeling data for classification requires significant human effort. To reduce labeling cost, instead of labeling every instance, a group of instances (bag) is labeled by a single bag label. Computer algorithms are then used to infer the label for each instance in a bag, a process referred to as instance annotation. This task is challenging due to the ambiguity regarding the instance labels. We propose a discriminative probabilistic model for the instance annotation problem and introduce an expectation maximization framework for inference, based on the maximum likelihood approach. For many probabilistic approaches, brute-force computation of the instance label posterior probability given its bag label is exponential in the number of instances in the bag. Our key contribution is a dynamic programming method for computing the posterior that is linear in the number of instances. We evaluate our methods using both benchmark and real world data sets, in the domain of bird song, image annotation, and activity recognition. In many cases, the proposed framework outperforms, sometimes significantly, the current state-of-the-art MIML learning methods, both in instance label prediction and bag label prediction.