Arbor: When Labels Are Not Coarsened at Random
Organizations: University of Maryland, Baltimore County · Johns Hopkins University Applied Physics Laboratory
Abstract
Merging datasets labelled at different levels of a taxonomy leaves some images with only a coarse label, and some classes with no fine-grained label at all. Standard training scores a coarse label by the total probability of the classes under it. Coarse labels name superclasses, and the standard objective is exact only when every class within a superclass is equally likely to receive a coarse label. We call a class novel if it is never labelled finely, and known otherwise. A novel class violates the assumption, and the classifier assigns its images to a known sibling. We propose Arbor, which models how labels become coarse. In each superclass with a novel class, Arbor adds a virtual novel class, and a logistic gate divides the superclass's probability between it and the known classes. The gate is trained with the likelihood of the observed labels under this model, the coarsening likelihood. We prove that at its population optimum the gate equals the Elkan-Noto correction of positive-unlabelled learning, and show that training the correction into the classifier improves on applying it after training. Across Cars, CUB and Aircraft with 90% coarse labels, Arbor correctly assigns 76-85% of novel-class images to their superclass, more than hierarchical classifiers, hierarchical novelty detection and the Elkan-Noto correction. Its top-1 accuracy over the leaf classes on known-class images is within 1.6 points of the best baseline, although its final predictions return the superclass more often. On the more challenging iNaturalist-2019 benchmark, Arbor improves novel-class accuracy from 46% (uniform target, the strongest baseline) to 68%.
Figures & tables
| Cars | CUB | CIFAR-100 | Aircraft | iNat-2019 | ||||||
| method | novel | known | novel | known | novel | known | novel | known | novel | known |
| Flat softmax + HSC [ 26 ] | 6 | .844 | 12 | .715 | 17 | .888 | 7 | .791 | 34 | .639 |
| Conditional softmax [ 52 , 63 ] | 6 | .814 | 14 | .745 | 81 | .876 | 8 | .768 | 29 | .622 |
| Per-node sigmoids [ 63 ] | 14 | .826 | 17 | .757 | 56 | .893 | 17 | .762 | 28 | .598 |
| Per-level + fallback [ 47 , 21 , 12 ] | 6 | .839 | 10 | .759 | 34 | .908 | 6 | .780 | 30 | .646 |
| Hierarchical CE [ 6 ] | 10 | .804 | 14 | .707 | 36 | .873 | 11 | .762 | 30 | .607 |
| Cars | CUB | CIFAR-100 | Aircraft | |
| exact-class rate on known-class images (%) | ||||
| best classification baseline | 77 | 63 | 78 | 73 |
| best novelty baseline | 64 | 54 | 61 | 68 |
| Arbor | 61 | 58 | 68 | 62 |
| incorrect predictions over all test images (%) | ||||
| best classification baseline | 22 | 23 | 6 | 23 |
| Cars | CUB | CIFAR-100 | Aircraft | |
| novel-class accuracy (%) | ||||
| Elkan–Noto correction | 77 | 68 | 78 | 78 |
| two-stage | 66 | 72 | 75 | 76 |
| Arbor | 85 | 76 | 80 | 83 |
| Arbor , matched to Elkan–Noto | 87 | 86 | 82 | 83 |
| incorrect predictions, all test images (%) | ||||
| Cars | CUB | CIFAR-100 | Aircraft | |||||
|---|---|---|---|---|---|---|---|---|
| variant | K | N | K | N | K | N | K | N |
| Arbor | .846 | 85 | .742 | 76 | .876 | 80 | .784 | 83 |
| no virtual novel class | .866 | 0 | .754 | 3 | .895 | 1 | .804 | 1 |
| gate everywhere | .843 | 74 | .734 | 74 | .876 | 80 | .774 | 53 |
| per-class | .695 | 64 | .527 | 46 | .837 | 33 | .690 | 63 |
| .813 | 75 | .709 | 54 | .872 | 83 | .769 | 79 | |
Appendix figures & tables24 assets
Supplementary material from the paper’s appendix.
Appendix
| CUB | Cars | CIFAR-100 | Aircraft | iNat-2019 | |
|---|---|---|---|---|---|
| median training images per class | (min ) | ||||
| superclasses with a virtual novel class, predicted (%) | |||||
| superclasses with a virtual novel class, measured (%) |
| Cars | CUB | CIFAR-100 | Aircraft | iNat-2019 | |||||||||||
| method | novel | leaf | known | novel | leaf | known | novel | leaf | known | novel | leaf | known | novel | leaf | known |
| Flat softmax + HSC [ 26 ] | 6 | 83 | .844 | 12 | 85 | .715 | 17 | 75 | .888 | 7 | 82 | .791 | 34 | 61 | .639 |
| Conditional softmax [ 52 , 63 ] | 6 | 83 | .814 | 14 | 83 | .745 | 81 | 12 | .876 | 8 | 77 | .768 | 29 | 65 | .622 |
| Per-node sigmoids [ 63 ] | 14 | 70 | .826 | 17 | 82 | .757 | 56 | 37 | .893 | 17 | 74 | .762 | 28 | 70 | .598 |
| Per-level + fallback [ 47 , 21 , 12 ] | 6 | 81 | .839 | 10 | 86 | .759 | 34 | 56 | .908 | 6 | 83 | .780 | 30 | 65 | .646 |
| Hierarchical CE [ 6 ] | 10 | 80 | .804 | 14 | 83 | .707 | 36 | 56 | .873 | 11 | 80 | .762 | 30 | 66 | .607 |
| baseline | how it uses the taxonomy |
|---|---|
| classification | |
| flat softmax + HSC [ 26 ] | flat softmax; thresholded node probabilities |
| hierarchical CE [ 6 ] | loss weighted along the path |
| soft labels [ 6 ] | targets softened by tree distance |
| conditional softmax [ 52 , 63 ] | one softmax per internal node |
| per-node sigmoids [ 63 ] | one sigmoid per node |
| Cars | CUB | C100 | Aircraft | ||||||
|---|---|---|---|---|---|---|---|---|---|
| variant | F | PN | F | PN | F | PN | F | PN | score |
| Arbor (novelty gate, pooled ) | .890 | 87 | .732 | 83 | .890 | 89 | .815 | 84 | 84.6 |
| virtual novel class in the softmax, pooled | .889 | 34 | .764 | 48 | .895 | 76 | .834 | 77 | 71.6 |
| virtual novel class in the softmax, on untrained leaves | .890 | 71 | .756 | 74 | .897 | 76 | .815 | 39 | 74.4 |
| pooled without the restriction to gated superclasses | .892 | 30 | .752 | 64 | .895 | 76 | .809 | 40 | 68.1 |
| pooled per superclass | .877 | 82 | .768 | 43 | .894 | 75 | .825 | 53 | 73.7 |
| protocol | Cars | CUB | C100 | Air. |
|---|---|---|---|---|
| coarse, one novel class | .03 | .01 | .01 | .01 |
| coarse, two novel classes | .03 | .03 | .01 | .03 |
| coarse, one novel class | .03 | .03 | .03 | .03 |
| all labels fine | .03 | .03 | .03 | .03 |
| coarse, no novel class | .01 | .01 | .01 | .03 |
| only novel classes coarse | .01 | .01 | .03 | .01 |
| Cars | CUB | CIFAR-100 | Aircraft | |
| one novel class per superclass ( Tab. 1 ) : Arbor / best classification baseline | ||||
| exact class, known-class images | 60.5 / 77.0 | 58.1 / 62.7 | 68.3 / 78.4 | 61.7 / 72.8 |
| in superclasses with a novel class | 37.4 / 72.7 | 48.7 / 56.3 | 68.3 / 78.4 | 14.1 / 51.5 |
| in the other superclasses | 92.3 / 83.4 | 95.0 / 92.7 | none | 88.2 / 86.4 |
| incorrect, known-class images | 9.4 / 7.2 | 14.5 / 10.2 | 8.3 / 3.2 | 11.9 / 11.5 |
| incorrect, all images | 10.7 / 22.4 | 16.2 / 23.3 | 10.4 / 6.0 | 12.3 / 23.0 |
| Cars | CUB | C100 | Air. | |
| Elkan–Noto correction / Arbor, each at its own operating point | ||||
| known-class acc. | .738 / .846 | .637 / .742 | .816 / .876 | .708 / .784 |
| novel-class acc. | 77 / 85 | 68 / 76 | 78 / 80 | 78 / 83 |
| exact-class rate | 57 / 61 | 48 / 58 | 61 / 68 | 62 / 62 |
| Elkan–Noto correction / Arbor at the correction’s exact-class rate | ||||
| novel-class acc. | 77 / 87 | 68 / 86 | 78 / 82 | 78 / 83 |
| third of : low / middle / high | Cars | CUB | CIFAR-100 | Aircraft | |
|---|---|---|---|---|---|
| virtual-novel-class probability | predicted | 0 / .09 / .60 | 0 / .09 / .58 | 0 / .08 / .58 | 0 / .07 / .59 |
| measured | .40 / .50 / .72 | .24 / .36 / .51 | .11 / .22 / .46 | .38 / .50 / .59 | |
| superclass predictions | Arbor | 36 / 50 / 80 | 20 / 43 / 68 | 7 / 28 / 79 | 43 / 59 / 76 |
| novelty detection | 21 / 30 / 53 | 21 / 36 / 56 | 18 / 33 / 56 | 26 / 37 / 48 | |
| no virtual novel class | 0 / 0 / 0 | 3 / 6 / 9 | 0 / 0 / 0 | 3 / 1 / 3 |
| Cars | CUB | CIFAR-100 | Aircraft | |||||
| method | K | N | K | N | K | N | K | N |
| Flat + HSC | .824 | 6 | .730 | 17 | .865 | 31 | .763 | 5 |
| Conditional | .788 | 17 | .748 | 18 | .860 | 55 | .775 | 9 |
| Per-node sigmoids | .761 | 12 | .732 | 20 | .872 | 60 | .727 | 22 |
| Per-level | .822 | 5 | .718 | 13 | .873 | 38 | .764 | 5 |
| Uniform target | .778 | 48 | .645 | 35 | .686 | 76 | .778 | 37 |
| Cars | CUB | CIFAR-100 | Aircraft | |||||||||
| count-informed baseline | base. | Arbor | Arbor † | base. | Arbor | Arbor † | base. | Arbor | Arbor † | base. | Arbor | Arbor † |
| Flat + HSC | 66 / 35 | 64 / 81 | 64 / 81 | 58 / 21 | 61 / 70 | 61 / 70 | 68 / 30 | 70 / 79 | 69 / 82 | 66 / 53 | 65 / 71 | 65 / 71 |
| Conditional | 64 / 40 | 64 / 80 | 62 / 80 | 60 / 20 | 61 / 69 | 61 / 69 | 68 / 87 | 69 / 79 | 68 / 83 | 64 / 47 | 62 / 77 | 62 / 78 |
| Per-node sigmoids | 63 / 35 | 65 / 79 | 64 / 79 | 59 / 17 | 61 / 68 | 61 / 68 | 67 / 64 | 68 / 80 | 68 / 83 | 64 / 48 | 63 / 77 | 63 / 77 |
| Per-level | 62 / 43 | 64 / 81 | 63 / 81 | 61 / 15 | 63 / 66 | 63 / 66 | 68 / 63 | 70 / 79 | 70 / 82 | 65 / 57 | 63 / 77 | 63 / 77 |
| Hier. CE | 62 / 40 | 64 / 80 | 63 / 80 | 57 / 19 | 60 / 72 | 60 / 72 | 69 / 53 | 69 / 80 | 69 / 83 | 66 / 46 | 62 / 78 | 62 / 79 |
| Cars | CUB | CIFAR-100 | Aircraft | |||||||||
| method | novel | leaf | known | novel | leaf | known | novel | leaf | known | novel | leaf | known |
| Flat softmax + HSC [ 26 ] | 4 | 86 | .917 | 13 | 82 | .903 | 11 | 79 | .919 | 8 | 83 | .840 |
| Conditional softmax [ 52 , 63 ] | 23 | 66 | .896 | 41 | 54 | .899 | 83 | 8 | .915 | 11 | 80 | .829 |
| Per-node sigmoids [ 63 ] | 12 | 76 | .891 | 29 | 68 | .887 | 86 | 8 | .919 | 27 | 64 | .831 |
| Per-level + fallback [ 47 , 21 , 12 ] | 6 | 80 | .915 | 18 | 76 | .908 | 34 | 55 | .919 | 8 | 80 | .839 |
| Hierarchical CE [ 6 ] | 11 | 80 | .913 | 26 | 70 | .906 | 22 | 69 | .917 | 10 | 81 | .843 |
| Cars | CUB | CIFAR-100 | Aircraft | |||||||||
| method | novel | leaf | known | novel | leaf | known | novel | leaf | known | novel | leaf | known |
| Flat softmax + HSC [ 26 ] | 5 | 87 | .818 | 11 | 86 | .714 | 27 | 65 | .884 | 9 | 83 | .794 |
| Conditional softmax [ 52 , 63 ] | 11 | 84 | .806 | 18 | 80 | .744 | 51 | 42 | .874 | 15 | 74 | .790 |
| Per-node sigmoids [ 63 ] | 10 | 77 | .797 | 11 | 87 | .740 | 49 | 44 | .888 | 18 | 74 | .744 |
| Per-level + fallback [ 47 , 21 , 12 ] | 6 | 83 | .827 | 11 | 84 | .745 | 42 | 49 | .905 | 9 | 81 | .786 |
| Uniform target | 35 | 61 | .764 | 21 | 79 | .647 | 66 | 30 | .749 | 46 | 48 | .787 |
| Cars | CUB | CIFAR-100 | Aircraft | |||||||||
| method | novel | leaf | known | novel | leaf | known | novel | leaf | known | novel | leaf | known |
| Flat softmax + HSC [ 26 ] | 6 | 84 | .833 | 21 | 76 | .752 | 19 | 73 | .893 | 11 | 79 | .763 |
| Conditional softmax [ 52 , 63 ] | 14 | 79 | .823 | 27 | 70 | .769 | 75 | 19 | .893 | 21 | 67 | .784 |
| Per-node sigmoids [ 63 ] | 13 | 72 | .815 | 27 | 72 | .758 | 44 | 48 | .906 | 30 | 59 | .743 |
| Per-level + fallback [ 47 , 21 , 12 ] | 6 | 83 | .840 | 19 | 75 | .778 | 26 | 65 | .919 | 11 | 77 | .762 |
| Hierarchical CE [ 6 ] | 6 | 84 | .792 | 20 | 78 | .742 | 32 | 60 | .890 | 23 | 64 | .764 |
| method | known | novel | leaf | incorrect, all |
| Per-level + fallback | .646 | 30 | 65 | 23.7 |
| Flat softmax + HSC | .639 | 34 | 61 | 22.7 |
| Uniform target | .467 | 46 | 52 | 33.8 |
| Hierarchical novelty detection | .441 | 43 | 55 | 39.4 |
| Arbor | .594 | 68 | 31 | 28.1 |
| diagnostic variants, seed 0 | ||||
| method | known | known: CUB / NABirds | novel | exact | AUROC |
|---|---|---|---|---|---|
| Arbor | .839 | 87.8 / 82.1 | 94.1 | 49.6 | .818 |
| Elkan–Noto correction | .799 | 84.8 / 77.7 | 93.2 | 48.3 | .822 |
| two-stage (best classifier + Elkan–Noto) | .883 | 91.1 / 87.0 | 92.6 | 50.0 | .822 |
| hierarchical novelty detection | .799 | 84.8 / 77.7 | 92.2 | 46.2 | .775 |
| uniform target | .755 | 84.7 / 71.3 | 93.2 | 50.3 | .767 |
| per-level + fallback | .883 | 91.1 / 87.0 | 40.2 | 69.1 | .627 |
| method | known | novel | leaf |
| Flat softmax + HSC | .760 | 31 | 52 |
| Conditional softmax | .752 | 43 | 43 |
| Per-node sigmoids | .704 | 18 | 81 |
| Per-level + fallback | .758 | 40 | 44 |
| Soft labels | .752 | 50 | 39 |
| HypStructure | .758 | 40 | 46 |
| held class at ; siblings at | 2 | 5 | 20 | all |
|---|---|---|---|---|
| CIFAR-100 | 60 / 30 / 0 | 79 / 11 / 0 | 88 / 0 / 0 | 89 / 0 / 0 |
| Cars | 26 / 63 / 0 | 48 / 41 / 0 | 63 / 26 / 0 | 65 / 25 / 0 |
| CUB | 28 / 65 / 0 | 64 / 26 / 0 | 77 / 14 / 0 | 77 / 15 / 0 |
| Aircraft | 41 / 44 / 0 | 76 / 10 / 0 | 87 / 0 / 0 | 89 / 0 / 0 |
| Cars, CLIP | 24 / 68 / 0 | 61 / 31 / 0 | 71 / 20 / 0 | 74 / 18 / 0 |
| CUB, CLIP | 34 / 59 / 0 | 63 / 27 / 0 | 70 / 21 / 0 | 68 / 25 / 0 |
| full labels | coarse | novel classes (%) | fine classes | ||
|---|---|---|---|---|---|
| method (CUB official split) | acc. | acc. | superclass | leaf | exact leaf (%) |
| Free-grained H-ViT + text attributes [ 48 ] (official code) | – | .488 | 24.9 | 62.6 | – |
| Flat softmax + HSC | .891 | .614 | 20.1 | 72.2 | 77.0 |
| Conditional softmax | .888 | .637 | 42.5 | 51.2 | 76.6 |
| Per-level + fallback | .890 | .634 | 20.1 | 71.5 | 75.6 |
| Uniform target | .891 | .590 | 81.7 | 10.0 | 75.6 |
| Cars | CUB | CIFAR-100 | Aircraft | iNat-2019 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| method | full | coarse | novel | full | coarse | novel | full | coarse | novel | full | coarse | novel | full | coarse | novel |
| Flat softmax + HSC [ 26 ] | .910 | .785 | 4 | .903 | .689 | 22 | .914 | .888 | 28 | .836 | .696 | 5 | .781 | .632 | 38 |
| Hierarchical CE [ 6 ] | .910 | .736 | 21 | .902 | .693 | 40 | .914 | .859 | 51 | .830 | .692 | 21 | – | – | – |
| Conditional softmax [ 52 , 63 ] | .893 | .754 | 20 | .901 | .704 | 45 | .912 | .858 | 81 | .823 | .716 | 9 | .776 | .614 | 57 |
| Per-level + fallback [ 47 , 21 , 12 ] | .910 | .783 | 9 | .904 | .727 | 24 | .913 | .893 | 33 | .832 | .694 | 9 | .779 | .637 | 39 |
| HypStructure [ 57 ] | .907 | .775 | 5 | .903 | .679 | 22 | .914 | .876 | 11 | .829 | .687 | 7 | – | – | – |
| vs per-level + fallback | vs flat softmax over all nodes | vs flat softmax + HSC | |
|---|---|---|---|
| Cars | (min ) | (min ) | (min ) |
| CUB | (min ) | (min ) | (min ) |
| CIFAR-100 | (min ) | (min ) | (min ) |
| Aircraft | (min ) | (min ) | (min ) |
| Cars | CUB | |||||||
|---|---|---|---|---|---|---|---|---|
| method | novel | leaf | novel | leaf | ||||
| Flat softmax + HSC [ 26 ] | .910 0.002 | .785 0.004 | 4 1 | 87 1 | .903 0.006 | .689 0.012 | 22 1 | 71 0 |
| Deep ensemble ( ) + HSC | .921 0.001 | .814 0.003 | 13 1 | 77 1 | .909 0.008 | .727 0.005 | 30 3 | 63 3 |
| Hierarchical CE [ 6 ] | .910 0.000 | .736 0.005 | 21 1 | 72 1 | .902 0.009 | .693 0.019 | 40 0 | 56 1 |
| Soft labels [ 6 ] | .910 0.002 | .786 0.009 | 8 1 | 84 1 | .900 0.008 | .693 0.013 | 20 1 | 77 1 |
| Conditional softmax [ 52 , 63 ] | .893 0.002 | .754 0.009 | 20 1 | 69 1 | .901 0.007 | .704 0.008 | 45 1 | 49 2 |
Fine-Grained Image Classification
Fine-grained image classification distinguishes visually similar categories, such as species, product varieties, and medical findings.
See all 89 papers