# Resolving Label Uncertainty with Implicit Posterior Models

Esther Rolf University of California, Berkeley, CA, USA  Microsoft Research,
Redmond, WA, USA  Nikolay Malkin  Mila and Université de Montréal, Montréal,
QC, Canada  Microsoft Research, Redmond, WA, USA  Alexandros Graikos  Stony
Brook University, Stony Brook, NY, USA  Microsoft Research, Redmond, WA, USA
Ana Jojic  Paul G. Allen School of Computer Science and Engineering,
University of Washington, Seattle, WA, USA  Caleb Robinson  Microsoft AI for
Good, Redmond, WA, USA  Nebojsa Jojic  Microsoft Research, Redmond, WA, USA

###### Abstract

We propose a method for jointly inferring labels across a collection of data
samples, where each sample consists of an observation and a _prior belief_
about the label. By implicitly assuming the existence of a generative model
for which a differentiable predictor is the posterior, we derive a training
objective that allows learning under weak beliefs. This formulation unifies
various machine learning settings; the weak beliefs can come in the form of
noisy or incomplete labels, likelihoods given by a different prediction
mechanism on auxiliary input, or common-sense priors reflecting knowledge
about the structure of the problem at hand. We demonstrate the proposed
algorithms on diverse problems: classification with negative training
examples, learning from rankings, weakly and self-supervised aerial imagery
segmentation, co-segmentation of video frames, and coarsely supervised text
classification.

##  1 Introduction

In prediction problems, coarse and imprecise sources of input can provide rich
information about labels. Negative labels (what an instance is _not_),
rankings (which of two instances is larger), or coarse labels (aggregated by
taxonomy or geography) give clues on what the ground truth label of an
instance _might_ be, but not what it _is_ directly. We consider a collection
of data samples, indexed by $i$, consisting of observations (features) $x_{i}$
and corresponding sample-specific _prior beliefs_ about their latent label
variables, $p_{i}(\ell)$. This paper proposes algorithms to resolve the
uncertainty in these prior beliefs by jointly inferring an assignment of
target labels $\ell_{i}$ and a model that predicts $\ell_{i}$ given $x_{i}$.

Partial or aggregate annotations and auxiliary data sources are often more
widely available and convenient to collect than “ground-truth" or high-
resolution labels, but they are not readily used by discriminative learners.
Supervision from probabilistic targets can result in uncertain predictions
(§2). Most approaches to resolve these uncertainties involve iterative
generation of hard pseudolabels [Zhang et al., 2021] or loss functions
promoting low entropy of predictions [Nguyen and Caruana, 2008, Yu and Zhang,
2016, Zou et al., 2020, Yao et al., 2020]. Typically, these approaches are
application-specific [Han et al., 2014, Zheng et al., 2021, Bao et al., 2021,
Li et al., 2021]. In many settings, fusing weak input data into a probability
distribution over classes is a more natural alternative to transforming the
weak input into hard labels [Mac Aodha et al., 2019]. Further connections and
comparisons to prior work are made throughout this paper and synthesized in
§B, §C.

Our key modeling insight (§2.1) is to identify the output distribution of a
discriminative model, a feed-forward neural network $q$, with an approximate
posterior over latent variables in an _generative_ model of features, of which
the given prior belief is a part. Bayesian reasoning about the generative
model and its posterior makes it possible to learn the inference network
_without instantiating the full generative model_ , while reaping the benefits
of generative modeling: high certainty in the posterior under soft priors and
rich opportunities to model structure in the prior beliefs.

Prior beliefs about labels can arise from many sources (§3). We validate the
effectiveness of our approach with experiments (§4, §E) on multiple domains
and data modalities that highlight: prior beliefs as a natural way to fuse
weak inputs, graceful degradation of performance with increasingly noisy or
incomplete inputs, and comparison with explicitly generative modeling
approaches.

$x_{i}$ $x_{i}$ $x_{i}$
$x_{i}$ (a) $\\{x_{i}\\}$: Le séducteur, René Magritte (b) $p_{i}(\ell)$: Boat
Prior, anonymous artist (c) $q_{i}(\ell)$: Inferred segmentation

Figure 1: Above: Inference of latent MNIST digit classes with negative label
supervision using a small CNN trained on the RQ criterion (§2.1). Below: (a)
Joint inference of latent pixel classes in an image. (b) Prior beliefs
$p_{i}(\ell)$ over three classes – sky (red), boat (green), water (blue) – are
manually set. (c) A small CNN trained on $(x_{i},p_{i}(\ell))_{i}$ infers the
posterior classes.

##  2 Background and approach

##### Two motivating examples.

Two illustrative examples are shown in Fig. 1. In the first example, the
$x_{i}$ are 784-dimensional vectors representing 28$\times$28 MNIST digits. We
aim to infer the digit classes $\ell_{i}\in\\{0,1,...,9\\}$ for all images in
the given collection based on data in which we are given just one _negative_
label per sample, i.e., the prior beliefs $p_{i}(\ell)$ (top row) are uniform
over all classes except for one incorrect class. The procedure described in
this paper produces inferred distributions over labels (bottom row) that are
usually peaky and place the maximum at the correct digit 97% of the time (see
Fig. 3 and §4.1).

In the second example, the observations $\\{x_{i}\\}_{i\in\textrm{pixels}}$
are image patches centered around each pixel coordinate $i$ in a Surrealist
painting, with patch size ($11\times 11$) equal to the receptive field of a
5-layer convolutional neural network used in our inference procedure. The
prior beliefs $p_{i}(\ell)$ are distributions over 3 classes (sky, boat,
water) depending on the coordinate $i$. The joint inference of all labels in
this image yields a feasible segmentation despite the high similarity in
colors and textures (see §E.4 for more details).

These examples illustrate the problem of training on weak beliefs, which is
often encountered in some form in machine learning. Weak supervision, semi-
supervised learning, domain transfer, and integration of modalities are all
settings where coarse, partial, or inexact sources of data can provide rich
information about the state of a prediction instance, though not always a
“ground truth” label for each instance. An inference technique that uses weak
beliefs as the sole source of supervision needs to estimate statistical links
between observations $x_{i}$ and corresponding latents $\ell_{i}$. These links
should simultaneously be highly confident (i.e., lead to low entropy in the
posterior distributions) and explain the varying prior beliefs, which
typically have low confidence (high entropy in the prior distributions).

##### Supervised learning on prior beliefs.

Supervised learning models, including many neural nets, are typically trained
to minimize the cross-entropy $-\sum_{i}\sum_{\ell}p_{i}^{d}(\ell)\log
q_{i}(\ell)$ between a “hard" distribution over labels with
$p_{i}^{d}(\ell)\in\\{0,1\\}$ and the distribution
$q_{i}(\ell)=q(\ell|x_{i};\theta)$ output by a predictor $q$ using data
features $x_{i}$. This is equivalent to minimizing the KL divergence
$\sum_{i}\operatorname{KL}(p^{d}_{i}\|q_{i})$, minimized when the two
distributions $p^{d}_{i}(\ell)$ and $q_{i}(\ell)$ are equal. Thus, when
$p^{d}_{i}(\ell)$ is a “softer" prior over latent labels, $p_{i}(\ell)$, the
trained model $q$ will reflect this, and also be highly uncertain.

Transforming soft labels into hard training targets, (e.g. training on
$\mathbbm{1}[\ell=\operatorname*{arg\ max}_{\ell}p^{d}_{i}(\ell)]$ ), can
introduce the opposite bias. In these cases, the cost would be minimized by
predictions with zero entropy, but learning such a prediction function faces
difficulty with overconfident labels which are often wrong, and the
possibility that certain labels often receive substantial weight in the prior,
but never the maximum. These issues are illustrated in Fig. D.3.

##### Generative modeling resolves the prior’s uncertainty.

The approach to classification problems through _generative_ modeling, instead
of targeting the conditional probability of latents given the data features,
assumes that there is a forward (generative) distribution $p(x_{i}|\ell)$ and
optimizes the log-likelihood of the observed features,
$\sum_{i}\log(x_{i})=\sum_{i}\log\sum_{\ell}p(x_{i}|\ell)p_{i}(\ell)$, with
respect to the parameters of that distribution. The posterior under the model
$q(\ell|x_{i})\propto p(x_{i}|\ell)p_{i}(\ell)$ is then used to infer latent
labels for individual data points [Seeger, 2002]. The generative modeling
approach does not suffer from uncertainty in the posterior distribution over
latents given the input features, even when the priors $p_{i}(\ell)$ are soft.
(Recall that the posterior distributions in a mixture of high-dimensional
Gaussians are often peaky even when the priors are flat.)

However, expressive generative models are typically harder and more expensive
to train compared to supervised neural networks, as they often require
sampling (e.g., sampling of the posterior in variational auto-encoders [VAEs;
Kingma and Welling, 2014] and sampling of the generator in GANs [Goodfellow et
al., 2014]). Furthermore, the modeling often requires doubling of parameters
to express both the forward (generative) model _and_ the reverse (posterior)
model. And, in case of GANs, the learning algorithms may not even cover all
modes in the data, which would prevent joint inference for _all_ data points.
(See §C for further discussion.)

###  2.1 Optimizing implicit posterior models

Suppose that there exists a generative model $p(x|\ell)$ of observed features
conditioned on latent labels. Optimization of the log-likelihood of observed
features, $\sum_{i}\log
p(x_{i})=\sum_{i}\log(\sum_{\ell}p(x_{i}|\ell)p_{i}(\ell))$, can be achieved
by introducing a variational posterior distribution $q(\ell|x_{i})$ over the
latent variable for each instance $x_{i}$ and minimizing the free energy (a
negated evidence lower bound (ELBO)), defined as

$-\sum_{i}\sum_{\ell}q(\ell|x_{i})\log\frac{p(x_{i}|\ell)p_{i}(\ell)}{q(\ell|x_{i})}\geq-\sum_{i}\log
p(x_{i}).$ (1)

Minimizing the free energy involves estimating both the forward distributions
$p(x_{i}|\ell)$ and the posteriors $q(\ell|x_{i})$.

One could parametrize both $p(x|\ell)$ and $q(\ell|x)$ as functions
$p(x|\ell,\theta_{p})$ and $q(\ell|x,\theta_{q})$ using neural networks, as
done by VAEs (although VAEs use continuous latent variables $\ell$ and do not
involve sample-specific priors). However, in our algorithms, we only
parametrize $q(\ell|x;\theta)$ as a neural network taking input $x$ and
producing a distribution over $\ell$. The generative conditional
$p(x_{i}|\ell)$ is defined only on data points $x_{i}$ and is calculated by
minimizing (1) for fixed $q(\ell|x)$, subject to the constraint that
$\sum_{i}p(x_{i}|\ell)=1$ for all $\ell$. The optimum is achieved by:

$p(x_{i}|\ell)=a_{i,\ell}=\frac{q(\ell|x_{i})}{\sum_{j}q(\ell|x_{j})}\leavevmode\nobreak\
.$ (2)

Here the generative conditional $p(x|\ell)$ is not fully specified for all
values $x$. Rather, it is represented as a matrix of numbers $a_{i,\ell}$
describing the conditional probabilities of different values of $x_{i}$ given
different latent labels $\ell$. The probabilities $p(x_{i}|\ell)$ are greater
for the data points $i$ for which $q(\ell|x_{i})$ is more certain, relative to
how popular assignment to class $\ell$ is across data points (denominator in
(2)).

In our formulation, $q$ plays the role of a variational posterior, but
_implicitly_ , in a generative model consisting of varying instance-specific
priors $p_{i}(\ell)$ and a complex conditional $p(x|\ell)$ that is never fully
estimated, but is instead maximized for the data points studied. The full link
between $x$ and $\ell$ is left entirely to the neural network $q$ to capture
explicitly.

In variational methods, the free energy (1) is usually rewritten as
$\sum_{i}{\rm KL}(q(\ell|x_{i})\|r_{i}(\ell)))-\log p(x_{i})$, where $r$ is
the posterior of the forward model, i.e., for the points $i$,
$r_{i}(\ell)\propto p_{i}(\ell)p(x_{i}|\ell)$. The minimization of free energy
then reduces to minimizing the KL divergence between $r$ and $q$.

We define $q_{i}(\ell)=q(\ell|x_{i};\theta)$. After our reduction of
$p(x_{i}|\ell)$ to the auxiliary matrix in (2), the posterior $r$ has the form

$r_{i}(\ell)=c_{i}\cdot
p_{i}(\ell)p(x_{i}|\ell)=c_{i}\frac{p_{i}(\ell)q_{i}(\ell)}{\sum_{j}q_{j}(\ell)}\leavevmode\nobreak\
,$ (3)

where $c_{i}$ are scalars making $\sum_{\ell}r_{i}(\ell)=1$. For each instance
$i$ we have two outputs: the direct model outputs of the variational posterior
$q_{i}$ and their _implied posterior_ $r_{i}$, which is computed by
multiplying the renormalized model outputs with the provided prior at each
instance as in (3). Using these two outputs, we can optimize a single set of
model parameters $\theta$ to minimize (1):

$\displaystyle\min_{\theta}\sum_{i}\text{KL}(q_{i}\|r_{i})=$ (4)
$\displaystyle\min_{\theta}\sum_{i}\text{KL}\bigg{(}\underbracket{\Big{(}q(\ell|x_{i};\theta)\Big{)}_{\ell}}_{\begin{subarray}{c}\text{model
output }\\\ \text{with input
$x_{i}$}\end{subarray}}\Big{\|}\Big{(}c_{i}\cdot\overbracket{p_{i}(\ell)\vphantom{\dfrac{q(|)}{\sum_{j}q(|)}}}^{\begin{subarray}{c}\text{per-}\\\
\text{\phantom{p}instance\phantom{p}}\\\
\text{priors}\end{subarray}}\overbracket{\frac{q(\ell|x_{i};\theta)}{\sum_{j}q(\ell|x_{j};\theta)}}^{\begin{subarray}{c}\text{model
output}\\\ \text{\phantom{p}normalized\phantom{p}}\\\ \text{per-class}\\\
\text{as in Eq.\leavevmode\nobreak\
\eqref{eq:aux_p}}\end{subarray}}\Big{)}_{\ell}\bigg{)}\leavevmode\nobreak\ .$

While (4) optimizes the free energy (1) by minimizing
$\textrm{KL}(q_{i}\|r_{i})$, minimizing $\textrm{KL}(r_{i}\|q_{i})$ would also
find solutions for which the direct model and its implied posterior are close.
We propose to optimize either of these two objectives with respect to the
model parameters $\theta$ by gradient steps. We iterate over data instances
$x_{i}$ with priors $p_{i}(\ell)$:

  1. (1)

Calculate the distributions $r_{i}$ in terms of $q_{i}$ as in (3).

  2. (2)

Update the parameters of $q$ with a gradient step:
$\bullet$ Option QR:
$\theta\leftarrow\theta-\eta\nabla_{\theta}\sum_{i}\operatorname{KL}(q_{i}\|r_{i})$.
$\bullet$ Option RQ:
$\theta\leftarrow\theta-\eta\nabla_{\theta}\sum_{i}\operatorname{KL}(r_{i}\|q_{i})$.

Gradients of the objectives are propagated to the expression of $r_{i}$
through $q_{i}$ (see (4) and Fig. 2). Both losses have a stable point when
$q_{i}=r_{i}$, and RQ reduces to the cross-entropy loss in the case of priors
which put all mass on one label (e.g.
$p_{i}(\ell)=\mathbbm{1}[\ell=\ell_{i}]$). A discussion of the relative
benefits and limitations of the QR and RQ losses is given in §A, along with
practical considerations for implementation.

Figure 2: Cross-entropy and implicit QR / RQ losses in PyTorch. The
normalization in (2) is done within batches, rather than across the entire
dataset. In practice, this may be sufficient if batches are large and
representative of the diversity in the data. Otherwise, the denominator in (3)
may need to be updated in an online fashion.

By defining the conditional model $p(x|\ell)$ as an auxiliary matrix of
probabilities $a_{i,\ell}$ that is fit to the reverse model $q$ during
learning, we avoid parametrizing both directions of the link $\ell-x$ with
highly nonlinear models.111Note that the use of an auxiliary matrix
$a_{i,\ell}$ is also found in expectation-maximization [EM; Dempster et al.,
1977], which also minimizes the free energy. However, in EM, it is the
variational posterior $q(\ell|x_{i})$ which is optimized as a matrix of
numbers $a_{i,\ell}$ only on data points, while the _generative_ model $p$ is
fully parametrized (see Table C.1). We thus manage to keep the problem in the
realm of training a single feed-forward network $q$ as a predictor of
variables $\ell$, but in a way that treats the instance-specific priors
$p_{i}(\ell)$ as they would be in generative modeling.

Next, we discuss the consequences of implicitly modeling the generative model
$p$ with an auxiliary distribution. Option QR uses the KL distance in the
direction it appears in (1) and thus guarantees continual improvements in free
energy and convergence to a local minimum (with the exception for the effects
of stochasticity in minibatch sampling). Substituting $r_{i}$ from (3), the
free energy (1) becomes:

$F=\sum_{i,\ell}q_{i}(\ell)\log\left(\sum_{j}q_{j}(\ell)\right)-\sum_{i,\ell}q_{i}(\ell)\log\left(p_{i}(\ell)\right)$
(5)

This criterion does not encourage entropy of individual $q_{i}$ distributions,
but of their _average_. The second term alone would be minimized if $q$ could
put all the mass on $\operatorname*{arg\ max}_{\ell}p_{i}(\ell)$ for each data
point, but the first term promotes diversity in assignment of latents (labels)
$\ell$ across the entire dataset. Thus a network $q$ can optimize (5) if it
makes different confident predictions for different data points.

To illustrate this, consider the case when all data points have the _same_
prior, $p_{i}(\ell)=p(\ell)$. Then (5) and the RQ objective are minimized when
$\frac{1}{N}\sum_{i}q_{i}(\ell)=p(\ell)$. This can be achieved when $q$ learns
a constant distribution $q(\ell|x_{i};\theta)=p(\ell)$. But both objectives
are also minimized if $q$ predicts only a single label for each data point
with high certainty, but it varies in predictions so that the counts of label
predictions match the prior.

As demonstrated in Fig. 1 and in our experiments, avoiding degenerate
solutions is not hard. We attribute this to two factors. First, the situations
of interest typically involve uncertain, but varying priors $p_{i}(\ell)$
which break symmetries that could lead to predictors ignoring the data
features $x_{i}$. Second, the neural networks used to model $q$, and their
training algorithms, come with their own constraints and inductive biases. In
fact, as discussed in §3 and §E.1, even unsupervised clustering is possible
with suitably chosen priors that break symmetry, allowing this approach to be
used for self-supervised training. See also §B, §C for more on relationships
with other approaches.

##  3 Sources of label priors

Having detailed our approach for learning from prior beliefs as weak
supervision in §2, we now describe a range of machine learning settings where
priors $p_{i}(\ell)$ emerge. These settings are illustrated in experiments in
§4 and §E.

##### Negative or partial labels (§4.1).

When we are given a set of equally possible labels $L_{i}$ for each point data
point $i$, instead of a single label $\ell_{i}$, then we set the prior
$p_{i}(\ell)=\frac{1}{|L_{i}|}\mathbbm{1}[\ell\in L_{i}]$. An extreme example
is when one negative label is given and hence can be “ruled out" (Fig. 1).

##### Joint labels and learning from rankings (§4.2).

Priors may also come in the form of joint distributions over labels of
multiple instances. For example, ranking supervision – the knowledge of which
example in a pair is greater with respect to an ordering of the labels – gives
prior beliefs about _pairs_ of labels. Suppose our data is organized into
pairs of images of digits $T_{j}=\\{x_{j,1},x_{j,2}\\}$, and for each pair we
are told which image represents the digit (0–9) which is greater (or equal).
This sets a prior $p(\ell_{1},\ell_{2})$ over pairs of labels in each pair,
represented by either an upper or a lower triangular matrix, depending on
which digit in the pair is known to be greater, with all nonzero entries equal
to $\nicefrac{{1}}{{55}}$.

We assume the underlying generative model has the form
$p(x_{1},x_{2}|\ell_{1},\ell_{2})=p(x_{1}|\ell_{1})p(x_{2}|\ell_{2})$. We aim
to fit its posterior model $q(\ell|x;\theta)$. For each pair $T_{j}$, we have
two outputs of the predictor network, $q(\ell_{1}|x_{j,1})$ and
$q(\ell_{2}|x_{j,2})$, for the two images in the pair. The joint posterior
under the generative model is

$\displaystyle r_{j}(\ell_{1},\ell_{2})$ $\displaystyle\propto
p(\ell_{1},\ell_{2})p(x_{j,1}|\ell_{1})p(x_{j,2}|\ell_{2})$
$\displaystyle\propto\frac{p(\ell_{1},\ell_{2})q(\ell_{1}|x_{j,1})q(\ell_{2}|x_{j,2})}{\sum_{j}q(\ell_{1}|x_{j,1})\sum_{j}q(\ell_{2}|x_{j,2})},$
(6)

and we can now use QR or RQ loss to fit $q(\ell_{1}|x_{j,1})$ to the marginal
$r_{j}(\ell_{1})$ and $q(\ell_{2}|x_{j,2})$ to $r_{j}(\ell_{2})$.

##### Coarse data in weakly supervised segmentation (§4.3, §E.2, §E.4).

We often have side information $z$ associated to each instance $i$ that allows
setting the priors $p_{i}(\ell)=p(\ell|z_{i})$ for each point directly by
hand. These include situations when we have beliefs about labels for different
points, as in the _Seducer_ example (Fig. 1). Interesting weak supervision
settings also arise in remote sensing (§4.3) and medical pathology (§E.2)
applications. For example, in a task of segmenting aerial imagery into land
cover classes, we often have coarse labels $c$ associated to large _blocks_ of
pixels, but not the target labels $\ell$ for individual pixels. If the
conditional $p(\ell|c)$ is known, it sets a belief about the high-resolution
labels $\ell$ for pixels in a block of class $c$.

##### Fusing models and data sources (§4.4, S4.5).

Auxiliary information $z$ may not always come with a known correspondence
$p(\ell|z)$. In the land cover mapping problem, auxiliary information includes
different modalities and resolutions (road maps, sparse point labels, etc.).
While these sources can be fused into a prior by hand-coded rules, the prior
may be more accurately set as the output of a model $p(\ell|z_{i})$ _trained_
on a separate dataset of points $(\ell_{i},z_{i})$. This is especially useful
when the data $x_{i}$ (imagery) is informative about the latents $\ell_{i}$
but is prone to domain shift problems, while the auxiliary data $z_{i}$ does
not suffer from domain shift issues but is not sufficient on its own to
predict the labels. In a text classification problem, $z_{i}$ might be the
encoding of text $x_{i}$ by a pretrained language model, and $p(\ell|z_{i})$ a
noisy distribution over labels given by their likelihoods under the language
model as continuations of a prompt.

##### Priors for self-supervision (§E.1).

In §2.1 we discussed the pitfalls of using a constant prior
$p_{i}(\ell)=p(\ell)$ for all data points in training models under the QR loss
as a potential method for unsupervised clustering. However, in §E.1 we give an
example of _joint_ learning of the posterior model $q$ and an energy model
(Markov random field) on the latent labels $\ell_{i}$ that expresses local
structure of labels in an image. This results in unsupervised clusterings that
are useful in downstream segmentation tasks. Such an approach is an example of
a benefit of generative modeling – the possibility of learning of a
parametrized distribution over latents – being inherited by implicit posterior
models.

##### Priors with latent structure (§E.3).

Implicit posterior modeling allows building hierarchical latent structure into
the prior (another benefit of classical generative models), as we demonstrate
in §E.3 on a video segmentation task. The prior is an admixture of possible
segmentations with a structure similar to Jojic et al. [2009], but using a set
of mask proposals $p(\ell_{i}|m)$ from a Mask R-CNN model [He et al., 2017],
indexed by a latent $m$. The prior is $p_{i}(\ell)=\sum_{m}p(\ell_{i}|m)p(m)$,
where $p(m)$, a probabilistic selection of the masks for the admixture in the
given frame, is estimated by minimizing the free energy.

##  4 Experiments

###  4.1 Partial labels in MNIST and CIFAR-10

Figure 3: Accuracies of MNIST and CIFAR-10 classifiers trained with varying
numbers of negative labels per example; the lighter variant of each color and
marker shows the peak accuracy over 300 training epochs. (Average of 10 runs
with standard error region.)

In this experiment, we compare algorithms for learning with partial labels on
two 10-class image classification datasets, MNIST and CIFAR-10. To each
training example $x_{i}$, we randomly assign a set $N_{i}$ of $k$ negative
labels, chosen from the 9 labels distinct from the ground truth. The prior
$p_{i}(\ell)$ is set to be uniform over $\ell\notin N_{i}$ and 0 for $\ell\in
N_{i}$. We vary $k$ from 1 (one negative label per example) to 9 (one-hot
prior, full supervision). The data of $k$ negative labels carries
$-\log_{2}(1-k/10)$ bits of label information; if $k=1$, $22\times$ less label
information than in the fully supervised setting.

For both datasets, the base model $q$ is taken to be a small convolutional
network, with four layers of ReLU-activated $3\times 3$ convolutions with
stride 2 and a linear map to the 10 output logits ($\sim$33k learnable
parameters for MNIST, $\sim$34k for CIFAR-10). We experiment with four
training losses:

  * •

CE: cross-entropy between predictions $q(\ell|x_{i};\theta)$ and the prior
$p_{i}(\ell)$.

  * •

NLL (union): negative logarithm of the sum of likelihoods assigned by $q$ to
labels in $\ell\notin N_{i}$, or, equivalently,
$\log\sum_{\ell}p_{i}(\ell)q(\ell|x_{i};\theta)$, as done, e.g., by Jin and
Ghahramani [2002], Kim et al. [2019].

  * •

The QR and RQ losses defined in §2.1.

The CE, NLL (union), and RQ loss objectives are equivalent when $k=9$. The RQ
and NLL (union) losses are equivalent when $\sum_{i}q_{i}(\ell)$ is uniform
over $\ell$, which approximately holds after a sufficient number of training
epochs.

All models are trained for 300 epochs on batches of 256 images with the Adam
optimizer [Kingma and Ba, 2014] and a learning rate of $10^{-4}$. After each
epoch, we compute the accuracy of the predictor $q$ on the ground truth labels
in the train and test sets. Fig. 4 shows the final train and test set
accuracies, as well as the maximum accuracies achieved at any epoch. Reported
results are averaged over 10 choices of partial label sets and random
initializations.

Models trained on RQ loss perform best, with the greatest benefit over CE seen
for very few negative labels. As expected, the performance of RQ and NLL
(union) is very similar across $k$. We hypothesize that the small advantage of
RQ over NLL (union) loss can be attributed to regularization in early
training. Meanwhile, QR performs as well as CE for very uncertain priors at
the peak epoch (light curves), but its predictions degenerate – usually toward
uniform predictions – with longer training.

###  4.2 Multiple-instance supervision: Learning from ranks

Figure 4:  Confusion matrices of MNIST classifiers in the course of training
on batches of 128 ranked pairs of digits. The trajectory of convergence to the
diagonal shows that uncertainty is first resolved for the digits 0/9, then
1/8, etc.

We train a CNN of the same architecture as in §4.1 on MNIST, but with the only
supervision coming in the form of pairs of images in which it is known which
image represents the greater digit. The training set of 60k images is divided
into pairs that are fixed throughout the training procedure; each digit
appears in exactly one pair. We optimize to match the predictor $q$ with the
implicit posterior model (6) using the RQ loss. Fig. 4 shows the confusion
matrices at initial iterations of training. The learned classifier has 97%
accuracy on both training and testing sets, which means that from pairwise
comparisons alone, we can group the digit images and place them in order.

###  4.3 Label super-resolution

We benchmark our method’s performance on the Chesapeake Land Cover dataset
222https://lila.science/datasets/chesapeakelandcover, a large 1m-resolution
land cover dataset used previously for label super-resolution [Robinson et
al., 2019, Malkin et al., 2019]. It consists of several aligned data layers,
including: NAIP (4-channel high-resolution aerial imagery at about 1m/px),
NLCD (16-class, 30m-resolution coarse land cover labels), and high-resolution
land cover labels (LC) in four classes. The task is to train high-resolution
segmentation models, in the four target classes, using only NLCD labels as
supervision. The NLCD layer is at 30$\times$ lower resolution than the imagery
and target labels and follows a different class scheme. Cooccurrence
statistics of NLCD classes $c$ and LC labels $\ell$ are assumed to be known
(Fig. D.1).

To form a prior over land cover classes $\ell$ at each pixel position, we map
the NLCD classes to probabilities over the target LC classes using these known
cooccurrence counts and apply a spatial blur to reduce low-resolution block
artifacts (Fig. 5, “Prior"). We then train small convolutional networks
(receptive field $11\times 11$) to predict high-resolution land cover from
input imagery. We evaluate both the QR and RQ variants of our approach on the
two states that comprise the “Chesapeake North" test set: Pennsylvania (PA)
and New York (NY), and the two states combined, after picking hyperparameters
based on an independent validation set in Delaware (details in §D.1.3). A
depiction of the data and prediction results is given in Fig. 5.

Table 1 compares our algorithms against the algorithmic technique with the
best published performance on the Chesapake dataset, self-epitomic LSR [Malkin
et al., 2020] and the hard naïve baseline from Malkin et al. [2019]. Self-
epitomic LSR, a generative modeling approach that explicitly produces
likelihoods $p(x|\ell)$, analyzes small patches of data by making a large
number of comparisons between sampled $7\times 7$ image patches and _all
other_ image patches. It does not produce a trained feedforward inference
model, and the inference procedure is at least an order of magnitude slower
than evaluation of our convolutional model. The hard naïve baseline maps the
NLCD classes to LC classes based on a given concurrence matrix, then trains a
standard semantic segmentation model on these pseudo-labels.

Training on the QR loss outperforms (in once case, matches) performance of
self-epitomic LSR (Table 1), and the generative model for $p(x|c)$ from (2) is
largely consistent with the epitomic generative model (Fig. D.4). Moreover,
our methods handle _batched input_ , where self-epitomic LSR trains on one
data tile at a time. Similar per-tile approaches have been shown to degrade in
performance and exhaust computation capacity when training on multiple tiles
[Malkin et al., 2020]). Optimization under an implied generative model has the
computational advantage of scaling naturally to large training data while
maintaining the benefits of leading generative modeling approaches. (See also
§E.2.)

Table 1: Pixel accuracy and class mean intersection over union on the Chesapeake Land Cover dataset. All models use only coarse NLCD labels as supervision. For our proposed methods, we evaluate both the trained predictor ($q_{i}$) and the posterior under the generative model ($r_{i}$). The score of the best overall model is bolded.  | PA | NY | Chesapeake
---|---|---|---
Model | acc % | IoU % | acc % | IoU % | acc % | IoU %
Self-epitomic [Malkin et al., 2020] | 86.2 | 67.6 | 86.4 | 70.5 | 86.3 | 69.7
Hard naïve [Malkin et al., 2019] | 85.3 | 63.0 | 83.6 | 59.8 | 83.6 | 59.7
QR ($q$) | 85.9 | 69.3 | 87.3 | 73.0 | 86.4 | 71.1
QR ($r$) | 86.2 | 69.9 | 87.9 | 74.4 | 86.8 | 72.1
RQ ($q$) | 81.5 | 63.1 | 77.4 | 60.2 | 79.8 | 62.2
RQ ($r$) | 81.5 | 63.2 | 77.5 | 60.3 | 79.8 | 62.4
Figure 5: Predictions of models trained with QR loss on the NLCD-only prior in
the Chesapeake region, shown on regions of 1000$\times$1000 pixels in
Pennsylvania and 500$\times$500 pixels in New York.

###  4.4 Data fusion and learned priors

In this set of experiments, we augment NLCD with information about the
presence of buildings, road networks, and waterbodies/waterways from public
sources (see Fig. 6 and §D.1.1). To evaluate the ability of models to
generalize to across regions, we use 1m 5-class land cover labels from the
geographically diverse EnviroAtlas dataset [Pickard et al., 2015] in four
cities in the US: Pittsburgh, PA, Durham, NC, Austin, TX, and Phoenix, AZ. The
NLCD-based prior model from §4.3 is augmented with the auxiliary information
to obtain a hand-coded prior for each image (see §D.1.2). These types of
priors can be made everywhere in the United States, while hard 1m-resolution
labels are rarely available.

An alternative to performing local inference under such priors is to simply
apply supervised models trained on hard labels elsewhere, hoping that the
domain shift is tolerable. Table 2 compares the performance of a model (of the
same architecture as in §4.3) trained on Pittsburgh high-resolution data (HR)
in each of the three other cities with that of models tuned on the hand-coded
prior in each other city. The QR method trained on the local handmade prior
outperforms the HR model in each evaluation city. This may be attributed to
the extra data in each city given to our method in the form of prior beliefs.
To isolate this effect, we also compare to a high-resolution model that
consumes the prior belief to _input_ data, concatenated with the NAIP imagery
(HR + aux). While the HR + aux model does increase performance substantially
from the HR model with NAIP imagery alone as input, the QR model remains the
highest-fidelity approach in two of the three cities. These results illustrate
that information that generalizes across domains may find its best use within
a separate model – to build a prior in our setting – and then used to
supervise local inference.

In practice, prior beliefs could be crafted by a domain expert to reflect the
uniquities in geographic and structural features for each city. We emulate
incorporating such context-specific knowledge by training (on a disjoint set
of instances) a neural network that consumes the inputs to the handmade prior
function (NLCD and auxiliary map data), and predicts high-resolution labels
(Fig. 6, “Learned prior"). Alongside structural interactions between the
inputs that generalize across cities (e.g., tree canopy supersedes rivers,
roads supersede water), the learned prior captures region-specific knowledge
(e.g., buildings in Durham tend to have grass surrounding them and trees
farther out, while in Austin, this is reversed, and in Phoenix, riverbeds
surrounded by barren land are likely to be dry). Using these tailored prior
beliefs during QR training tends to increase scores (Table 2).

The final row in Table 2 benchmarks the performance of a high-resolution land
cover model trained on imagery and labels over the entire contiguous US
[Robinson et al., 2019]. This large model takes NAIP, Landsat 8 satellite
imagery, and building footprints as inputs. Small, local models with priors
created from only weak supervision outperform the US-wide model in all cities.
(See §D.1.4 for details.)

Figure 6: Prior generation for land cover mapping: “NLCD only prior" (§4.3) and “$\\{$Hand-coded, Learned$\\}$ prior" (§4.4).  Table 2: Land cover classification experiments for generalizing across cities. In each column, the score of the best model not depending on auxiliary data as input is italicized and the score of the best overall model is bolded. (A larger set of experimental results is given in Table D.1.) |  | Durham, NC | Austin, TX | Phoenix, AZ
---|---|---|---|---
Train region | Model | acc | IoU | acc | IoU | acc | IoU
Pittsburgh | HR | 74.2 | 35.9 | 71.9 | 36.8 | 6.7 | 13.4
(supervised) | HR + aux | 78.9 | 47.9 | 77.2 | 50.5 | 62.8 | 24.2
Local |  QR ($q$) | 78.9 | 47.7 | 76.6 | 49.1 | 75.8 | 45.4
(hand-coded prior) |  QR ($r$) | 79.0 | 48.4 | 76.6 | 49.5 | 76.2 | 46.0
Local |  QR ($q$) | 79.0 | 48.7 | 79.4 | 51.3 | 73.4 | 42.8
(learned prior) |  QR ($r$) | 79.2 | 49.5 | 79.1 | 51.9 | 73.6 | 43.1
Full US [Robinson et al., 2019] | U-Net Large | 77.0 | 49.6 | 76.5 | 51.8 | 24.7 | 23.6

###  4.5 Text classification

This experiment follows the recent work of Mekala et al. [2021] and
illustrates the effectiveness of learning on prior beliefs beyond computer
vision. We work with a dataset of $\sim$12k New York Times news articles. Each
article belongs to one of 20 fine categories (e.g., ‘energy companies’,
‘tennis’,‘golf’), which are grouped into 5 coarse categories (e.g.,
‘business’, ‘sports’). The goal is to train text classifiers that predict fine
labels, but only the coarse label for each article is available in training.

Some external knowledge about the fine categories is necessary to resolve the
coarse labels into fine labels. Past work on this problem [Meng et al., 2018,
Mekala and Shang, 2020, Meng et al., 2020, Wang et al., 2021] has trained
supervised models on pseudolabels created by mechanisms such as propagation of
seed words and querying large pretrained models. On the other hand, Mekala et
al. [2021] create training data by sampling additional _features_ (articles)
from a finetuned version of the large generative language model GPT-2 [Radford
et al., 2019] conditioned on fine categories, then tune a classifier based on
the almost equally large model BERT [Devlin et al., 2019] in a supervised
manner.

We obtain comparable results using an elementary predictor, far less
computation, and no finetuning of massive language models (Table 3). We form a
prior $p_{i}(\ell)$ on the fine class $\ell$ of each article $x_{i}$ by
querying GPT-2 for the likelihood of each fine category name $\ell$ compatible
with the known coarse label following the prompt “[article text] Topic: ” and
normalizing over $\ell$. We then divide $p_{i}(\ell)$ by the mean likelihood
of $\ell$ over all articles $x_{i}$ and renormalize. We represent each article
as a vector of alphabetic trigram counts ($26^{3}$ features, of which only 8k
are ever nonzero) and train a logistic regression with the RQ objective
against this ‘GPT-2 prior’. After ten epochs of training ($\sim$10s on a Tesla
K80 GPU), the trained classifier nears or exceeds the performance of models
requiring at least $100\times$ longer to train, even excluding the time to
generate any pseudo-training data.

Table 3: F1-scores of various models on the coarsely supervised text classification task. The first five rows are taken from Mekala et al. [2021]. The last two rows use the GPT-2 prior defined in §4.5 as weak supervision with cross-entropy and RQ loss, respectively (mean of 10 random trials). | Algorithm | Micro-F1 % | Macro-F1 %
---|---|---|---
pseudolabeling | WeSTClass [Meng et al., 2018] | 76.23 | 69.82
ConWea [Mekala and Shang, 2020] | 73.96 | 65.03
LOTClass [Meng et al., 2020] | 15.00 | 20.21
X-Class [Wang et al., 2021] | 91.16 | 81.09
pseudodata | C2F [Mekala et al., 2021] | 92.62 | 87.01
GPT-2 prior (trigram features) | prior argmax | 86.33 | 77.61
CE | 87.18 | 77.90
RQ | 93.18 | 84.26

##  5 Discussion and conclusion

In summary, we found that the generative distribution in a free energy
criterion can be left implicit to the minimization process in posterior
(discriminative) model training. This allowed us to unite the training of
neural networks $q(\ell|x_{i};\theta)$ for prediction of labels $\ell$ from
features $x$ with the modeling of the prior $p_{i}(\ell)$, possibly with its
own latent structure. Implicit modeling of the conditional generative
distributions removes the burden of training accurate (and therefore large or
deep) generative models, but still allows natural generative approaches to
modeling priors.

Learning a discriminative network $q$ and its implicit posterior model $r$ via
the QR and RQ methods can unify common supervised learning paradigms with
realistic label supervision settings, enabling high-fidelity predictions from
weak supervision sources carrying far less information. The additional
experimental results in §E detail further results for weakly supervised image
segmentation, self-supervised learning, and co-segmentation in video data.

Altogether, our results expose promising future work on exploring more
creative data sources that can be cast as prior beliefs for downstream
training. We expect interesting new modeling paradigms that integrate
different modalities and models to arise from our formulation.

##### Code.

This paper is accompanied by a code repository at
github.com/estherrolf/implicit-posterior. The repository contains three
directories. Two of them illustrate our algorithms for partial-label learning
and weakly supervised segmentation and are sufficient to reproduce predictions
resembling those in Fig. 1. The third directory contains code for the land
cover mapping experiments (§4.3, §4.4) and instructions for reproducing the
results.

## References

  * Bao et al. [2021] Qianyue Bao, Yang Liu, Zixiao Zhang, Dafan Chen, Yuting Yang, Licheng Jiao, and Fang Liu.  Mrta: Multi-resolution training algorithm for multitemporal semantic change detection.  _International Geoscience and Remote Sensing Symposium (IGARSS)_ , 2021.
  * Boeing [2017] Geoff Boeing.  Osmnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks.  _Computers, Environment and Urban Systems_ , 65:126--139, 2017.
  * Caelles et al. [2017] S. Caelles, K.K. Maninis, J. Pont-Tuset, L. Leal-Taixé, D. Cremers, and L. Van Gool.  One-shot video object segmentation.  _Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * Cheng et al. [2021] Ho Kei Cheng, Yu-Wing Tai, and Chi-Keung Tang.  Rethinking space-time networks with improved memory coverage for efficient video object segmentation.  _Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Cheng et al. [2018] J. Cheng, Y.-H. Tsai, W.-C. Hung, S. Wang, and M.-H. Yang.  Fast and accurate online video object segmentation via tracking parts.  _Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * Dempster et al. [1977] A. P. Dempster, N. M. Laird, and D. B. Rubin.  Maximum likelihood from incomplete data via the EM algorithm.  _Journal of the Royal Statistical Society B_ , 39(1):1--38, 1977.
  * Devlin et al. [2019] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  _North American Chapter of the Association for Computational Linguistics (NAACL)_ , 2019.
  * Goodfellow et al. [2014] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  _Neural Information Processing Systems (NeurIPS)_ , 2014.
  * Haklay and Weber [2008] Mordechai Haklay and Patrick Weber.  OpenStreetMap: User-generated street maps.  _IEEE Pervasive Computing_ , 7(4):12--18, 2008\.
  * Han et al. [2014] Junwei Han, Dingwen Zhang, Gong Cheng, Lei Guo, and Jinchang Ren.  Object detection in optical remote sensing images based on weakly supervised learning and high-level feature learning.  _IEEE Transactions on Geoscience and Remote Sensing_ , 53(6):3325--3337, 2014.
  * He et al. [2017] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask R-CNN.  _International Conference on Computer Vision (ICCV)_ , 2017.
  * Hinton et al. [1995] Geoffrey E. Hinton, Peter Dayan, Brendan J. Frey, and R M Neal.  The "wake-sleep" algorithm for unsupervised neural networks.  _Science_ , 268 5214:1158--61, 1995.
  * Hou et al. [2019] Le Hou, Vu Nguyen, Ariel B Kanevsky, Dimitris Samaras, Tahsin M Kurc, Tianhao Zhao, Rajarsi R Gupta, Yi Gao, Wenjin Chen, David Foran, et al.  Sparse autoencoder for unsupervised nucleus detection and representation in histopathology images.  _Pattern Recognition_ , 2019.
  * Jean et al. [2019] Neal Jean, Sherrie Wang, Anshul Samar, George Azzari, David Lobell, and Stefano Ermon.  Tile2vec: Unsupervised representation learning for spatially distributed data.  _Association for the Advancement of Artificial Intelligence (AAAI)_ , 2019.
  * Jin and Ghahramani [2002] Rong Jin and Zoubin Ghahramani.  Learning with multiple labels.  _Neural Information Processing Systems (NeurIPS)_ , 2002.
  * Johnander et al. [2019] Joakim Johnander, Martin Danelljan, Emil Brissman, Fahad Shahbaz Khan, and Michael Felsberg.  A generative appearance model for end-to-end video object segmentation.  _Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * Jojic et al. [2009] Nebojsa Jojic, Alessandro Perina, Marco Cristani, Vittorio Murino, and Brendan Frey.  Stel component analysis: Modeling spatial correlations in image class structure.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 2044--2051. IEEE, 2009.
  * Khoreva et al. [2017] A. Khoreva, R. Benenson, E. Ilg, T. Brox, and B. Schiele.  Lucid data dreaming for object tracking.  _The 2017 DAVIS Challenge on Video Object Segmentation - CVPR Workshops_ , 2017.
  * Kim et al. [2019] Youngdong Kim, Junho Yim, Juseung Yun, and Junmo Kim.  NLNL: Negative learning for noisy labels.  _International Conference on Computer Vision (ICCV)_ , 2019.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kingma and Welling [2014] Diederik P. Kingma and Max Welling.  Auto-encoding variational bayes.  _International Conference on Learning Representations (ICLR)_ , 2014\.
  * Li et al. [2021] Zhuohong Li, Fangxiao Lu, Hongyan Zhang, Guangyi Yang, and Liangpei Zhang.  Change cross-detection based on label improvements and multi-model fusion for multi-temporal remote sensing images.  _International Geoscience and Remote Sensing Symposium (IGARSS)_ , 2021.
  * Lin et al. [2014] Tsung-Yi Lin, Michael Maire, Serge J. Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick.  Microsoft COCO: common objects in context.  _European Conference on Computer Vision (ECCV)_ , 2014.
  * Loshchilov and Hutter [2017] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_ , 2017.
  * Luiten et al. [2018] Jonathon Luiten, Paul Voigtlaender, and Bastian Leibe.  Premvos: Proposal-generation, refinement and merging for video object segmentation.  _Asian Conference on Computer Vision (ACCV)_ , 2018.
  * Mac Aodha et al. [2019] Oisin Mac Aodha, Elijah Cole, and Pietro Perona.  Presence-only geographical priors for fine-grained image classification.  _International Conference on Computer Vision (ICCV)_ , 2019.
  * Malkin et al. [2019] Nikolay Malkin, Caleb Robinson, Le Hou, Rachel Soobitsky, Jacob Czawlytko, Dimitris Samaras, Joel Saltz, Lucas Joppa, and Nebojsa Jojic.  Label super-resolution networks.  _International Conference on Learning Representations (ICLR)_ , 2019\.
  * Malkin et al. [2020] Nikolay Malkin, Anthony Ortiz, and Nebojsa Jojic.  Mining self-similarity: Label super-resolution with epitomic representations.  _European Conference on Computer Vision (ECCV)_ , 2020.
  * Maninis et al. [2018] Kevis-Kokitsi Maninis, Sergi Caelles, Yuhua Chen, Jordi Pont-Tuset, Laura Leal-Taixé, Daniel Cremers, and Luc Van Gool.  Video object segmentation without temporal information.  _IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI)_ , 2018.
  * Meinhardt and Leal-Taixe [2020] Tim Meinhardt and Laura Leal-Taixe.  Make one-shot video object segmentation efficient again.  _Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Mekala and Shang [2020] Dheeraj Mekala and Jingbo Shang.  Contextualized weak supervision for text classification.  _Association for Computational Linguistics (ACL)_ , 2020.
  * Mekala et al. [2021] Dheeraj Mekala, Varun Gangal, and Jingbo Shang.  Coarse2Fine: Fine-grained text classification on coarsely-grained annotated data.  _Empirical Methods in Natural Language Processing (EMNLP)_ , 2021\.
  * Meng et al. [2018] Yu Meng, Jiaming Shen, Chao Zhang, and Jiawei Han.  Weakly-supervised neural text classification.  _International Conference on Information and Knowledge Management_ , 2018.
  * Meng et al. [2020] Yu Meng, Yunyi Zhang, Jiaxin Huang, Chenyan Xiong, Heng Ji, Chao Zhang, and Jiawei Han.  Text classification using label names only: A language model self-training approach.  _Empirical Methods in Natural Language Processing (EMNLP)_ , 2020\.
  * Mohamed and Lakshminarayanan [2017] Shakir Mohamed and Balaji Lakshminarayanan.  Learning in implicit generative models.  _International Conference on Learning Representations (ICLR)_ , 2017\.
  * Nguyen and Caruana [2008] Nam Nguyen and Rich Caruana.  Classification with partial labels.  _Knowledge Discovery and Data Mining (KDD)_ , 2008.
  * Oh et al. [2019] Seoung Wug Oh, Joon-Young Lee, Ning Xu, and Seon Joo Kim.  Video object segmentation using space-time memory networks.  _International Conference on Computer Vision (ICCV)_ , 2019.
  * Perazzi et al. [2016] F. Perazzi, J. Pont-Tuset, B. McWilliams, L. Van Gool, M. Gross, and A. Sorkine-Hornung.  A benchmark dataset and evaluation methodology for video object segmentation.  _Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * Perazzi et al. [2017] Federico Perazzi, Anna Khoreva, Rodrigo Benenson, Bernt Schiele, and Alexander Sorkine-Hornung.  Learning video object segmentation from static images.  _Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * Pickard et al. [2015] Brian R Pickard, Jessica Daniel, Megan Mehaffey, Laura E Jackson, and Anne Neale.  EnviroAtlas: A new geospatial tool to foster ecosystem services science and resource management.  _Ecosystem Services_ , 14:45--55, 2015.
  * Pilant et al. [2020] Andrew Pilant, Keith Endres, Daniel Rosenbaum, and Gillian Gundersen.  US EPA EnviroAtlas meter-scale urban land cover (MULC): 1-m pixel land cover class definitions and guidance.  _Remote Sensing_ , 12(12), 2020.
  * Radford et al. [2019] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  2019\.
  * Robinson et al. [2019] Caleb Robinson, Le Hou, Nikolay Malkin, Rachel Soobitsky, Jacob Czawlytko, Bistra Dilkina, and Nebojsa Jojic.  Large scale high-resolution land cover mapping with multi-resolution data.  _Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * Robinson et al. [2020] Caleb Robinson, Anthony Ortiz, Nikolay Malkin, Blake Elias, Andi Peng, Dan Morris, Bistra Dilkina, and Nebojsa Jojic.  Human-machine collaboration for fast land cover mapping.  _Association for the Advancement of Artificial Intelligence (AAAI)_ , 2020.
  * Seeger [2002] Matthias Seeger.  Learning with Labeled and Unlabeled Data.  2002\.  URL https://infoscience.epfl.ch/record/161327/files/review.pdf.
  * Shwartz-Ziv and Tishby [2017] Ravid Shwartz-Ziv and Naftali Tishby.  Opening the black box of deep neural networks via information.  _arXiv preprint arXiv:1703.00810_ , 2017.
  * Stewart et al. [2021] Adam J Stewart, Caleb Robinson, Isaac A Corley, Anthony Ortiz, Juan M Lavista Ferres, and Arindam Banerjee.  Torchgeo: deep learning with geospatial data.  _arXiv preprint arXiv:2111.08872_ , 2021.
  * Tancik et al. [2020] Matthew Tancik, Pratul P. Srinivasan, Ben Mildenhall, Sara Fridovich-Keil, Nithin Raghavan, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan T. Barron, and Ren Ng.  Fourier features let networks learn high frequency functions in low dimensional domains.  _Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Voigtlaender and Leibe [2017] Paul Voigtlaender and Bastian Leibe.  Online adaptation of convolutional neural networks for video object segmentation.  _British Machine Vision Conference (BVMC)_ , 2017.
  * Voigtlaender et al. [2019] Paul Voigtlaender, Yuning Chai, Florian Schroff, Hartwig Adam, Bastian Leibe, and Liang-Chieh Chen.  FEELVOS: Fast end-to-end embedding learning for video object segmentation.  _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019\.
  * Wang et al. [2021] Zihan Wang, Dheeraj Mekala, and Jingbo Shang.  X-Class: Text classification with extremely weak supervision.  _North American Chapter of the Association for Computational Linguistics (NAACL)_ , 2021.
  * Yang et al. [2018] Linjie Yang, Yanran Wang, Xuehan Xiong, Jianchao Yang, and Aggelos K. Katsaggelos.  Efficient video object segmentation via network modulation.  _Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * Yang et al. [2020] Zongxin Yang, Yunchao Wei, and Yi Yang.  Collaborative video object segmentation by foreground-background integration.  _European Conference on Computer Vision (ECCV)_ , 2020.
  * Yao et al. [2020] Yao Yao, Jiehui Deng, Xiuhua Chen, Chen Gong, Jianxin Wu, and Jian Yang.  Deep discriminative CNN with temporal ensembling for ambiguously-labeled image classification.  _Association for the Advancement of Artificial Intelligence (AAAI)_ , 2020.
  * Yu and Zhang [2016] Fei Yu and Min-Ling Zhang.  Maximum margin partial label learning.  In _Asian conference on machine learning_ , pages 96--111. PMLR, 2016\.
  * Zhang et al. [2021] Xiao Zhang, Yixiao Ge, Yu Qiao, and Hongsheng Li.  Refining pseudo labels with clustering consensus over generations for unsupervised object re-identification.  _Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * Zheng et al. [2021] Zhuo Zheng, Yinhe Liu, Shiqi Tian, Junjue Wang, Ailong Ma, and Yanfei Zhong.  Weakly supervised semantic change detection via label refinement framework.  _International Geoscience and Remote Sensing Symposium (IGARSS)_ , 2021.
  * Zhou et al. [2017] Naiyun Zhou, Xiaxia Yu, Tianhao Zhao, Si Wen, Fusheng Wang, Wei Zhu, Tahsin Kurc, Allen Tannenbaum, Joel Saltz, and Yi Gao.  Evaluation of nucleus segmentation in digital pathology images through large scale image synthesis.  In _Medical Imaging 2017: Digital Pathology_ , volume 10140. International Society for Optics and Photonics, 2017.
  * Zou et al. [2020] Yuliang Zou, Zizhao Zhang, Han Zhang, Chun-Liang Li, Xiao Bian, Jia-Bin Huang, and Tomas Pfister.  Pseudoseg: Designing pseudo labels for semantic segmentation.  _arXiv preprint arXiv:2010.09713_ , 2020.

##  Appendix A Practical Considerations

##### Mini-batches:

Figure 2 shows a PyTorch implementation of the QR and RQ loss functions, where
loss is computed over _batches_ of training data. Our experiments validate
that so long as these batches are large enough to include enough diversity of
$(x_{i},p_{i}(l))$ pairs, our method works when Equation 2 and Equation 3 are
applied directly to batches. As discussed in §4.4, handling batched input is
important for leveraging the scale of large training datasets. As discussed in
the caption of Figure 2, should mini-batch training become an issue in future
implementations, it may be beneficial to estimate the denominator of Equation
2 across multiple batches.

##### Relative benefits/limitations of the QR and RQ loss formulations:

The algorithm presented in §2.1 details two loss options: a QR option and an
RQ option, both with unique strengths. The QR algorithm is guaranteed to
converge as each step reduces loss (except for randomness in the learning
algorithm). The RQ algorithm, on the other hand, has the appealing property
that it reduces to standard minimization of cross entropy loss in the case of
hard labels. In §C, we discuss connections between QR option and variational
auto-encoders (VAEs), and between the RQ option and the wake-sleep algorithm.
Ultimately, though, we find that which option works better may depend on the
application, with RQ working across all applications we tried but sometimes
being slightly beaten by QR.

Comparing performance across these varied learning settings can shed light on
the performance of the proposed QR and RQ methods under different conditions.
Future research could systematize and formalize settings where one variant
would be superior to the other; results in this work show that both can be
effective ways to resolve uncertainty in non-‘‘ground-truth" labels.

##### Simple ways to avoid degenerate solutions

As discussed in §2.1, minimizing Equation 1 can lead to degenerate solutions.
However, avoiding these solutions can be quite simple, and in most of our
experiments we did not make any interventions to explicitly avoid such local
minima. In a targeted experiment in Table D.1 we show that pre-training on
hard labels (even out-of-domain) or using sharper learned priors can help
break symmetries during early training phases. When hard labels are not
available, one could similarly start the training process with a cross-entropy
loss on the prior belief, and then switch to RQ or QR loss. The intuition is
that first training to minimize cross-entropy breaks the symmetry at the
start, while implicit posterior modeling sharpens the predictions in later
iterations.

##  Appendix B Additional Related Work

There are several approaches to learning with uncertain, weak, or coarse
labels under different assumptions and settings. Work on partial-label
learning often employs loss functions that aim to decrease prediction entropy
[Nguyen and Caruana, 2008, Yao et al., 2020, Yu and Zhang, 2016]. These
approaches do not use a generative formulation in these loss functions, makes
them less suitable for problems with more varied forms of uncertainty encoded
in priors. Another line of work studies the generation and use of pseudo
labels in learning settings. Specifically, Zou et al. [2020] relies on a
domain-specific augmentation procedure for semantic segmentation with image-
level labels, and, Zhang et al. [2021] studies unsupervised clustering applied
to object re-identification. Application-specific solutions also include
object detection in remote sensing images [Han et al., 2014] and change
detection with temporal satellite imagery [Zheng et al., 2021, Bao et al.,
2021, Li et al., 2021].

In our experimental setups, we chose a mix of baselines to both compare
algorithm design and benchmark performance on certain tasks. To compare our
approach on an _algorithmic basis_ , we compare to the negative logarithm of
the sum of likelihoods (NLL), which is used in prior works to handle multiple
ambiguous labels [Jin and Ghahramani, 2002] and negative labels [Kim et al.,
2019]. As discussed in §4.1, NLL and RQ are equivalent when
$\sum_{i}q_{i}(\ell)$ is uniform over $\ell$, evidenced by the comparable
performance between the two in Figure 3. We compare to self-epitomic LSR
[Malkin et al., 2020] as an algorithmic comparison by which to contrast our
method with an ‘‘explicit" generative modeling approach. Our similar
performance to self-epitomic LSR in regimes where self-epitomic LSR has been
shown to perform well (super-resolution in land cover mapping (§4.3) and the
tumor-infiltrating lymphocytes task (§E.2)) is an important validation of our
motivation in §2.

To benchmark _performance_ of our approach across tasks, we compare to state-
of-the-art pseudo-labeling methods in supervised text classification (see
§4.5), an established 1m resolution map of land cover predictions across the
United States [Robinson et al., 2019] and best-performing published results
for the land cover mapping tasks we study [Malkin et al., 2020] [Robinson et
al., 2020], the best known published results for the tumor-infiltrating
lymphocyte segmentation task [Malkin et al., 2019, 2020], and a host of
comparisons for the video instance segmentation task (see Table E.3 for a full
list).

Lastly, it is worth noting that the similar term ‘‘implicit generative model"
has been used in prior literature to refer to amortized sampling procedures
for nonparametric (or not specified) energy functions, such as generative
adversarial models (e.g., Mohamed and Lakshminarayanan [2017]). Although we do
not make an explicit connection with such models, our formulation also does
not assume a parametrization of the data distribution, and one can understand
the term ‘‘implicit posterior’’ as referring to a function that is a posterior
for an implicit (i.e., uninstantiated, unparametrized) generative model.
However, we assume tractability of sampling from a posterior over certain
distinguished latents (classes) conditioned on observed data (features, e.g.,
images), rather than directly sampling latents.

##  Appendix C Relationships with EM, VAE, and wake-sleep algorithm

Table C.1:  Comparison of modeling forms for variational auto-encoders (VAE), wake-sleep algorithms (WS), expectation-maximization (EM), and our proposed implicit posterior (IP). Variational auto-encoders parametrize both a generative model $p$ and a posterior model $q$. Here we distinguish between $\theta_{p}$ and $\theta_{q}$ as these models can differ in both architecture and parameters. The EM formulation parametrizes the generative model $p(x_{i}|\ell;\theta_{p})$ and the posterior is instantiated as auxiliary matrix with entries $a_{i,\ell}$ calculated to maximize the objective given the estimated $p(x_{i}|\ell;\theta_{p})$ on the observed instances $i$. In implicit posterior modeling, the posterior $q(\ell|x_{i};\theta_{q})$ is modeled and parametrized directly, with the generative link $p$ instantiated as an auxiliary matrix with entries of the form $a_{i,\ell}$. Combining this auxiliary matrix with the prior beliefs $p_{i}(\ell)$ at each instance as in Eq. (3) yields a posterior model $r_{i}$ _implied_ by forward model $q(\ell;x_{i},\theta_{q})$ and weak prior beliefs on each instance $p_{i}(\ell)$. | VAE/WS | EM | IP
---|---|---|---
generative $p$ | $p(x|\ell;\theta_{p})$ | $p(x|\ell;\theta_{p})$ | $a_{i,\ell}$
posterior $q$ | $q(\ell|x;\theta_{q})$ | $a_{i,\ell}$ | $q(\ell|x;\theta_{q})$

As discussed in §2.1, the QR loss guarantees continual improvements in the
free energy (1). On the other hand, option RQ is equivalent to performing a
gradient step on the cross-entropy of $q_{i}$ and $r_{i}$ and a gradient step
on the _negative_ entropy of $r_{i}$. In the case that the priors
$p_{i}(\ell)$ are hard (supported only on one ground truth label), the same is
true of $r_{i}$, and the RQ loss is equivalent to cross-entropy. This option
reverses the KL distance in a manner reminiscent of the training procedure in
the wake-sleep algorithm [Hinton et al., 1995], where parameter updates for
the forward and reverse models are iterated, but the KL distance optimized
always places the probabilities under the model being optimized in the second
position in the KL distance (inside the logarithm), so that the generative and
the inference models each optimize log-likelihoods of their predictions. The
wake-sleep algorithm, however, also trains a generative model rather than
treating it as an auxiliary distribution as we do, and that requires sampling.
As opposed to VAEs, the wake-sleep algorithm samples the generative model, not
the posterior.

It is interesting to contrast our approach to the expectation-maximization
(EM) formulation. In standard EM, the $q$ distributions are considered
auxiliary, rather than parametrized as direct functions of the inputs $x$. The
$q_{i}(\ell)=a_{i,\ell}$ is simply a matrix of numbers normalized across
$\ell$. Its dependence on the data $x$ arises through the iterative re-
estimation of the minimum of the free energy, where the link $x-\ell$ is
modeled directly in the parametrized forward distribution $p(x|\ell)$ (see
Table C.1). We instead model forward probabilities $p(x_{i}|\ell)$ as
auxiliary parameters, a matrix of numbers $a_{i,\ell}$ normalized across $i$
that we fit to minimize the free energy at each data point, and optimize only
the parameters of the $q$ model which explicitly models the link $x-\ell$.
This allows us to capture nonlinear (and ‘deep’) structure and benefit from
inductive biases inherent to training deep models with SGD, but without the
cost of training an actual parametrized generative model and other problems
associated with deep generative model fitting. The resulting $q$ network
approximates the posterior in a generative model -- which (locally) maximizes
the log likelihood of the data -- and it is usually highly confident (as seen
in Fig. 1).

The implicit modeling of the posterior in EM does not lead to overfitting of
the generative model. But, given that degenerate solutions to optimization
with implicit posterior models are possible when the prior is constant across
all data points (§2.1), we can imagine that our approach of implicit posterior
modeling might lead to degenerate solutions. As demonstrated in Fig. 1 and in
our experiments, avoiding degenerate solutions is not too hard. We address
this point further in §A.

##  Appendix D Experiment details

###  D.1 Land cover mapping

####  D.1.1 Datasets

##### Imagery Data

Our land cover mapping experiments use imagery from the National Agriculture
Imagery Program (NAIP), which is 4-channel aerial imagery at a $\leq 1$m/px
resolution taken in the United States (US).

##### Chesapeake Conservancy land cover dataset

The Chesapeake Conservancy land cover dataset consists of several raster
layers of both imagery and labels covering parts of 6 states in the
Northeastern United States: Maryland, Delaware, Virginia, West Virginia,
Pennsylvania, and New York [Robinson et al., 2019]333Dataset can be downloaded
from: https://lila.science/datasets/chesapeakelandcover.. The raster layers
include: high resolution (1m/px) NAIP imagery, high resolution (1m/px) land
cover labels created semi-autonomously by the Chesapeake Conservancy, low
resolution (30m/px) Landsat-8 mosaics imagery, low resolution (30m/px) land
cover labels from the National Land Cover Database (NLCD), and building
footprint masks from the Microsoft Building Footprint dataset. The dataset is
partitioned into train, validation, and test splits per-state, where each
split is a set of $\approx 7\text{km}\times 6\text{km}$ tiles containing the
aligned raster layers.

##### EPA EnviroAtlas data

The EnviroAtlas land cover data consists of high resolution (1m/px) land cover
maps over 30 cities in the US, and is collected and hosted by the US
Environmental Protection Agency (EPA) [Pickard et al., 2015]. A detailed
description of the dataset and its land cover definitions is provided by
Pilant et al. [2020]. As with most high-resolution land cover datasets
(including the Chesapeake Conservancy land cover labels), the EnviroAtlas land
cover labels are themselves derived by remote sensing and learning procedures,
and thus are not themselves a perfect ‘‘ground truth’’ representation of land
cover. For example, the estimated accuracy of the provided labels is 86.5% in
Pittsburgh, PA, 83.0% in Durham, NC, 86.5% in Austin, TX, and 69.2% in
Phoenix, AZ [Pilant et al., 2020].

The high-resolution label files were aligned to match the extent of the NAIP
tiles from the closest available years to the years that the EnviroAtlas
labels were collected: for Pittsburgh, PA and Phoenix, AZ, we used data from
2010 and for Durham, NC and Austin, TX, we used data from 2012. We chose these
four cities to get a wide coverage across the United States (US), and due to a
mostly consistent set of classes being used between the four cities.

##### National Land Cover Database (NLCD)

The National Land Cover Database is produced by the United States Geological
Survey (USGS) and uses 16 land cover classes. Maps are generated every 2-3
years, with spatial resolution of 30m/px. Data and more information can be
found at: https://www.usgs.gov/centers/eros/science/national-land-cover-
database.

##### Microsoft Building Footprint dataset

The Microsoft Building Footprint dataset consists of predicted building
polygons over the continental US from Bing Maps imagery. As of the time of
writing, the most updated Microsoft Building Footprints dataset in the US can
be accessed at: https://github.com/Microsoft/USBuildingFootprints.

##### Open Street Map (OSM) data

Open Street Map (https://www.openstreetmap.org/) is an ongoing effort to make
publicly available and editable map of the world, generated largely from
volunteer efforts. The data is available under the Open Database License. From
the many different sources of information provided by OSM [Haklay and Weber,
2008], we download raster data for road networks, waterways, and water bodies,
using the OSMnx python package [Boeing, 2017].

##### Data splits and data processing

For experiments using the Chesapeake Conservancy dataset (Table 1), we used
established train, test, and validation splits. In particular, we used the 20
test tiles in New York (NY) and the 20 test tiles in Pennsylvania (PA) on
which to conduct our experiments. Here a _tile_ matches the extent of a NAIP
tile, roughly 7km $\times$ 6km. To facilitate comparison of our results with
previous published results on this dataset, we condensed the labels into four
classes: (1) water, (2) impervious surfaces (roads, buildings, barren land),
(3) grass/field, and (4) tree canopy.

For experiments with the EnviroAtlas dataset (Table 2), we aligned the high
resolution land cover data, NLCD, OSM, and Microsoft Building Footprints data
with NAIP imagery tiles, matching years as closely as possible to the
EnviroAtlas data collection year for NLCD and NAIP. We instantiated a split of
10 train, 8 validation, and 10 test tiles in Pittsburgh, and 10 test tiles in
Durham, NC, Austin, TX, and Phoenix, AZ. For Pittsburgh we assigned tiles to
splits randomly from the set of 28 tiles that had no missing labels. There
were not enough such tiles in Durham to follow the same procedure, so we chose
the ten evaluation tiles at random from a set with no number of missing labels
per tile. For Austin and Phoenix, we chose the 10 evaluation tiles at random
from the tiles in each city that had no agriculture class (as it is not
present in Pittsburgh or Durham) and no missing labels. We set aside 5
separate tiles in each city for use in ‘‘learning the prior’’ (in Pittsburgh
these 5 tiles are a subset of the 8 validation tiles). As above, each tile
corresponds to one NAIP tile. The tiles in these constructed sets for
Pittsburgh, Durham, and Austin contain five unique labels: (1) water, (2)
impervious surfaces (roads, buildings), (2) barren land, (4) grass/field, and
(5) trees. Phoenix additionally has a ‘‘shrub’’ class; when forming the prior
we merge this class with trees, and we ignore the shrub class when evaluating
in Phoenix. We cropped all data tiles to ensure no spatial overlap in any
tiles between or within the train/val/test splits.

####  D.1.2 Forming the priors

To form the priors for the land cover classification tasks, we first spatially
smooth the NLCD labels by applying a 2D Gaussian filter (with a standard
deviation of 31 pixels) across every channel in a one-hot representation of
the NLCD classes. The main reason for applying this smoothing is to reduce
artifacts due to the 30m2 boundaries of the NLCD data, to undo the blocking
procedure induced by the aggregation to 30m $\times$ 30m extents, to
incorporate the spatial correlations between nearby NLCD blocks, and to remove
erroneous sharp differentials between inputs that can cause artifacts during
later training stages.

We then remap the blurred NLCD layers to the classes of interest by
multiplying by a matrix of cooccurrence counts between the (unblurred) NLCD
data and the high resolution labels in each region. For the Chesapeake region,
we use the train tiles provided with the Chesapeake Conservancy land cover
dataset to define cooccurrence matrices in NY and PA. For EnviroAtlas, we
compute cooccurrences using the entire city (excluding tiles with agriculture
in Phoenix AZ, and Austin, TX). The cooccurrence matrices for each region we
study are shown in Figure D.1.

Figure D.1: Cooccurrence matrices between NLCD classes and high resolution
land cover labels for each region we study.

The priors for the Chesapeake Conservancy dataset are then generated by
normalizing the blurred and remapped NLCD data so that summing over all five
classes gives probability 1 for each pixel.

For the EnviroAtlas data, we augment this prior with publicly available data
on buildings, road networks, water bodies, and waterways. We obtain building
maps from the Microsoft Buildings Footprint database and road, water bodies,
and waterways data from Open Street Map, using the OSMnx tool [Boeing, 2017]
to download the data (see Section D.1.1). We apply a small spatial blur to
each of these input sources to account for (a) vector representation of roads
and waterways being unrealistically thin, and (b) possible data-image
misalignment on the order of pixels. Where this results in probability mass on
impervious surfaces or water, we add these probability masses to the blurred
NLCD prior, and then renormalize to obtain a valid set of probabilities for
each pixel.

In §4.4, we describe a method for ‘‘learning the prior,’’ which uses a more
sophisticated process to aggregate the individually weak and coarse inputs
that we use in the handmade prior. In this method, we train a neural net to
take as input the blurred, remapped NLCD representation (5 classes)
concatenated with the 4 classes of additional data: buildings, roads,
waterways, water bodies, and to predict high-resolution labels in each city.
We train these networks using 5 tiles of imagery and high-resolution labels
from the EnviroAtlas Dataset in each city which are distinct from the 10 test
tiles in each city. The training procedure for these prior generation networks
is described in in §D.1.3. To create the priors that we then train our method
on (‘learned prior’ rows in Table 2) we ran these learned models forward on
(blurred and remapped NLCD, buildings, roads, waterways, and waterbodies)
input for each of the 10 evaluation tiles in each city.

####  D.1.3 Experimental procedure

We use priors generated as described in Section D.1.2, with Gaussian spatial
smoothing with standard deviation of 31 pixels, and cooccurrence matrix
determined via the training splits in each city/state. We apply a pixel-wise
additive smoothing constant of 1e-4 to the probability vectors output by the
neural network as well as to the prior probability vectors used as the model
supervision data. This additive smoothing constant ensures that there are no
extremely low probability classes in either the prior or the predicted outputs
during training.

Experiments summarized in Table 1 and Table 2 use a 5-layer fully connected
network with kernel sizes of 3 at each layer, 128 filters per layer, and leaky
ReLUs between layers. Note that the receptive field of this model is only
$11\times 11$ pixels. We use batch sizes of 128 instances during training,
where each image instance is a cropped 128 $\times$ 128 pixels from a larger
tile. Training and model evaluation is done within the torchgeo framework for
geo-spatial machine learning [Stewart et al., 2021]. All models use the AdamW
optimizer [Loshchilov and Hutter, 2017] during training and torchgeo defaults
unless otherwise noted.

##### Comparison to previous label super-resolution for LC mapping

To obtain the parameter setting used for the runs in New York (NY) and
Pennsylvania (PA) in Table 1, we first perform a hyperparameter search with
the 20 tiles test set in Delaware (DE) from the same overall dataset. We use a
learning rate schedule that decreases learning rate when the validation loss
plateaus, as well as early stopping to prevent over training of models. Of the
grid of learning rates in {1e-3, 1e-4,1e-5}, we describe below, we pick
learning rate as 1e-4 for both QR and RQ variants of our method, as this is
the setting that minimizes the IoU of the $q$ output on the 20 DE tiles for
both variants.

When training on NY and PA jointly (‘‘Chesapeake" in Table 1), we use the per-
state cooccurrence matrices. This ensure that the cooccurrence matrices used
are consistent between our method and the self-epitomic LSR benchmark across
all columns in Table 1.

##### Generalization across cities.

For the high-resolution model with NAIP imagery from Pittsburgh as input, we
consider learning rates in $\\{10^{-2},10^{-3},10^{-4},10^{-5}\\}$ and pick
based on the best validation performance on the validation set in Pittsburgh.
The chosen learning rate is 1e-3. We search over the same set of learning
rates for the model with NAIP imagery and the prior concatenated as input; the
chosen learning rate is also 1e-3. For this model with concatenated image and
prior as input, only the number of input channels changes in the fully
connected network model architecture. When training on the high-resolution
land cover labels, we use a very small additive constant (1e-8) for the last
layer of the model.

When training our methods, we initialize model weights using the best NAIP
image input model from the Pittsburgh validation set runs, and then train
using the priors and the training procedure described in the main text. We
pick the learning rate for this training step using again the validation set
in Pittsburgh; we search learning rates in $\\{10^{-3},10^{-4},10^{-5}\\}$,
and pick 1e-5 as the learning rate for QR and 1e-3 as the learning rate for
RQ, since these resulted in the best performance for the Pittsburgh validation
set with the randomly initialized model. We discuss the results of a similar
procedure using randomly initialized model weights in Section D.1.4.

For the learned prior, we use a 3 layer fully connected network is kernel
sizes of 11,7, 5 respectively, 128 filters per layer and leaky ReLUs between
layers. For each city, we train this model on the prior inputs (blurred and
remapped NLCD, roads, buildings, waterways, and water bodies) using a
validation set of 5 tiles separate from from the 10 evaluation tiles in each
city. We considered learning rates in $\\{10^{-3},10^{-4},10^{-5}\\}$ for
learning the prior in each city, and chose 1e-4 as it gave most often resulted
in the highest accuracies of each validation set. For learning _on_ this
learned prior, we again initialize model weights using the best NAIP image
input model from the Pittsburgh validation set runs, and set the learning rate
to 1e-5 for QR evaluation runs and 1e-3 for RQ evaluation runs to match the
other variants of the experiment.

Table D.1: Supplementary results to accompany Table 2.

|  | Pittsburgh, PA | Durham, NC | Austin, TX | Phoenix, AZ
---|---|---|---|---|---
Train region | Model | acc % | IoU % | acc % | IoU % | acc % | IoU % | acc % | IoU %
Pittsburgh | HR | 89.3 | 69.3 | 74.2 | 35.9 | 71.9 | 36.8 | 6.7 | 13.4
(supervised) | HR + aux | 89.5 | 70.5 | 78.9 | 47.9 | 77.2 | 50.5 | 62.8 | 24.2
Same as test |  QR ($q$) | 80.5 | 56.8 | 78.3 | 44.4 | 79.2 | 50.5 | 75.2 | 29.5
(random |  QR ($r$) | 80.7 | 57.5 | 78.5 | 46.4 | 79.7 | 52.0 | 75.9 | 33.8
initialization) |  RQ ($q$) | 77.6 | 53.3 | 65.8 | 23.3 | 73.8 | 43.0 | 61.8 | 18.6
|  RQ ($r$) | 77.6 | 53.3 | 65.8 | 23.3 | 73.8 | 43.1 | 61.8 | 18.6
Same as test |  QR ($q$) | 80.6 | 58.5 | 78.9 | 47.7 | 76.6 | 49.1 | 75.8 | 45.4
(pretrained |  QR ($r$) | 80.6 | 58.7 | 79.0 | 48.4 | 76.6 | 49.5 | 76.2 | 46.0
in Pittsburgh) |  RQ ($q$) | 84.3 | 59.6 | 75.6 | 28.6 | 76.5 | 47.5 | 63.7 | 19.5
|  RQ ($r$) | 84.3 | 59.6 | 75.4 | 31.5 | 76.5 | 47.5 | 63.7 | 19.5
Same as test |  QR ($q$) | 82.4 | 63.7 | 79.0 | 48.7 | 79.4 | 51.3 | 73.4 | 42.8
(learned prior ) |  QR ($r$) | 82.4 | 64.0 | 79.2 | 49.5 | 79.1 | 51.9 | 73.6 | 43.1
Full US* Robinson et al. [2019] | U-Net Lrg. | 79.0 | 61.5 | 77.0 | 49.6 | 76.5 | 51.8 | 24.7 | 23.6

####  D.1.4 Additional Results

Table D.2: Comparison of the Full US* U-Net Large [Robinson et al., 2019] map predictions when evaluated on the full 5 classes considered in Table 2 (water, grass/field, trees/shrub, impervious surfaces, and barren land) and evaluated on the four prediction classes predicted by the model (where barren land and impervious surfaces are merged as a single class), and when barren is post-facto assigned whenever the predicted class is ‘‘impervious surfaces" and the label class is ‘‘barren land".  | Pittsburgh, PA | Durham, NC | Austin, TX | Phoenix, AZ
---|---|---|---|---
Classication Scheme | acc % | IoU % | acc % | IoU % | acc % | IoU % | acc % | IoU %
5 Classes | 78.8 | 55.1 | 76.6 | 43.4 | 76.2 | 49.1 | 18.2 | 18.8
4 Classes | 79.0 | 68.7 | 77.0 | 54.1 | 76.5 | 60.4 | 24.7 | 16.8
Barren reassigned | 79.0 | 61.5 | 77.0 | 49.6 | 76.5 | 51.8 | 24.7 | 23.6

##### Extended results for generalizing across EnviroAtlas cities.

Figure D.2: Example predictions on the hand-coded and learned prior in each
EnviroAtlas city we study.

The extended results for generalizing across cities with the EnviroAtlas
datasets in Table D.1 contain the results of the RQ runs trained on the
handmade prior in each city. Evaluation results in Pittsburgh, PA give further
context for comparison of generalization across cities by each method.

Table D.1 also details the result of initializing the model weights randomly
for the QR method. Table D.1 shows that the choice of model initialization can
be important for our method -- this is most apparent in Pittsburgh, PA
(unsurprisingly since the high-resolution model was trained in Pittsburgh) and
Phoenix, AZ. In Phoenix, much of the handmade prior is consistent across
geographies and the randomly initialized model has trouble distinguishing
between infrequent classes that most often occur together in the handmade
prior. The results in Table D.1 suggest that using pre-trained models as a
starting point for our method can help to break some of these symmetry issues
in resolving the information in the prior. Results in Table 2 suggest that
using a more detailed prior map may help with this as well.

##### Evaluating the Full US map from Robinson et al. [2019].

Recall that the row for the full US Map [Robinson et al., 2019] in Table 2
reflects the performance of the model evaluated on all 5 classes we consider
in our experiments, where we give the map predictions the ‘‘benefit of the
doubt" in that any prediction of ‘‘impervious surfaces" where the true label
is ‘‘barren land" gets assigned a correct classification of ‘‘barren land."
The results reported in Table 2 are thus a sort of upper bound on the
predictive performance of the method that generated the predictive maps. It
was important for us to keep the barren class while evaluating across cities,
as it is the dominant class in Phoenix, AZ. In the remaining three cities, the
barren class is challenging to predict as it is infrequent. In Table D.2, we
compare this classification scheme with two alternatives: a 5 class scheme
that will penalizes the map predictions for never predicts the barren class,
and a 4 class scheme that merges the barren land and impervious surfaces
classes in evaluation. Table D.2 shows that while the choice of evaluation
scheme does not greatly effect accuracy (outside of Phoenix, AZ, where the
accuracy of the Full US Map is low for both classification schemes), the
average IoU drops significantly for all cities apart from Phoenix.

##### Comparing loss functions: qualitative results with land cover mapping.

Figure D.3 compares predictions under different loss functions with an
illustrative example. Here the prior is similar to the ‘‘hand-coded" prior
described in Section D.1.2, but with the prior defined over all NLCD classes.
We train each model (a slight variant on the network used in experimental
results) on the single NAIP tile region encompassing the zoom-in in the figure
for 2000 iterations with the Adam algorithm [Kingma and Ba, 2014], a batch
size of 64, and a learning rate fixed at 1e-4 during training. Qualitative
comparisons show that predictions made by the QR and RQ loss functions are
more certain (sharper colors in plots) than training with cross entropy or
squared-error loss on the soft priors, and, in in most places, arrive at
better solutions than training with a standard cross entropy loss on the
argmax of the prior.

Figure D.3: Comparison of different loss functions on hard and soft prior.
Figure D.4: Comparison of forward model likelihoods under the generative model
trained with QR loss (above) and the likelihood under an epitome model [Malkin
et al., 2020] for part of a test tile from §4.3.

##  Appendix E Additional experiments

###  E.1 Self-supervision for unsupervised image clustering

Neural networks are usually trained on large amounts of hard-labeled data
$\\{x_{i},\ell_{i}\\}$, yet, due to the biases induced by the typical
architectures and learning algorithms, much of the modeling power of these
networks seem to focus on correlations in the input space [Shwartz-Ziv and
Tishby, 2017]. This means that a network trained for one application, i.e.,
for one label space $\ell\in L_{1}$, can be adopted to another application,
i.e., a different labels space $\ell\in L_{2}$, as long as the input features
are in a similar domain. The canonical example of this is the use of lower
levels of the networks pre-trained on ImageNet as part of the networks solving
a completely different set of image classification problems. Pretrained
networks require smaller training sets in fine tuning, as long as they have
learned to represent the variation in the input space well. Self-supervised
models attempt to go a step further and learn these representations without
_any_ labels. In our framework, self-supervision can simply be seen as the
appropriate choice of subset priors $p(\ell_{T})$ over appropriately chosen
tuples of labels.

To discuss the pitfalls and opportunities, consider again the QR loss (5)

$F=-\sum_{i,\ell}q_{i}(\ell)\log
p_{i}(\ell)+\sum_{i,\ell}q_{i}(\ell)\log\left(\sum_{j}q_{j}(\ell)\right)\leavevmode\nobreak\
.$ (7)

If we were to simply set $p_{i}(\ell)$ to a constant (e.g., uniform)
distribution $p(\ell)$ for all data points $i$, then the optimal solution
would be any function $q_{i}(\ell)=q(\ell|x_{i})$ such that
$\frac{1}{N}\sum_{i}q(\ell|x_{i})=p(\ell)$. Thus simply using the uniform
prior may not lead to appropriate unsupervised clustering (or self-supervised
learning of the network $q$). The inductive biases in the network architecture
and training may not help, because one solution is $q(\ell|x)=p(\ell)$, which
can be achieved by zeroing out all weights except for biases in a final
softmax layer that outputs probabilities for labels $\ell$. As the softmax
bias vector is the closest to the top in back-propogation with gradient
descent, it will quickly be learned to match $\log p(\ell)$. This will not
only slow down the propagation of gradients into the network, but could
eventually stop it completely, as this solution is a global optimum. Another
optimal solution would be a function satisfying
$\frac{1}{N}\sum_{i}q(\ell|x_{i})=p(\ell)$, but where individual entropies for
each data point are small: $-\sum_{\ell}q(\ell|x_{i})\log
q(\ell|x_{i})<\epsilon$, which motivates an alternative cost criterion:

$F=-\sum_{i,\ell}q_{i}(\ell)\log
q_{i}(\ell)+\sum_{i,\ell}q_{i}(\ell)\log\left(\sum_{j}q_{j}(\ell)\right)\leavevmode\nobreak\
.$ (8)

where the first term promotes certainty in predictions $q(\ell|x_{i})$ for
each point $i$ and the second is promoting the diversity of the predictions
across the different inputs, i.e., a high entropy of the average
$\frac{1}{N}\sum_{h}q_{i}(h)$. This prevents learning a network with a
constant output $q(h)=p(h)$ and forces the model to find some statistics in
the input data that break it into clusters indexed by labels $\ell$. The
result will be highly dependent on the inductive biases associated with the
network architecture and SGD method used, as we can imagine degenerate
solutions here as well. For example, we can ignore completely some subset of
features and still train a network that is certain in its modeling of the
remaining ones, and achieves a high diversity of predicted classes across the
dataset. This may be dangerous if the features omitted end up being the most
important ones for the downstream task. However, due to the stochastic
gradient descent training as well as their architecture, it has been difficult
to prevent neural networks from learning statistics involving all the input
features. For example, training a neural network using a weak generative model
as a teacher corresponds to using a simpler mixture model, whose posterior is
used as a target $p_{i}(\ell)$ and then learning a neural network that can
approximate it. The inductive bias then leads to networks that do not match
$p_{i}(\ell)$ exactly but learn more complex statistics instead.

Equation (8) can be seen as a degenerate example of using a tuple prior where
the tuple has the same data point repeated and the prior simply expects the
two predictions to be the same. In many applications, there are natural
constraints involving multiple data points that are easily modeled with priors
over tuples or over the entire collection of labels. Consider unsupervised
image segmentation, for an example. It is usually expected that nearby pixels
should belong to the same class (or a small subset of classes), and that
faraway pixels are more likely to belong to a different subset of classes.
This belief is typically modeled in terms of Markov random field models of
joint probabilities of labels in the image,

$p(\\{\ell_{i}\\})\propto\exp\sum_{i}\phi(\ell_{i},\\{\ell_{j}\\}_{j\in
N_{j}}).$ (9)

We experimented with potentials of the form

$\phi(\ell_{i}=\ell,\\{\ell_{j}\\}_{j\in
N_{j}})=\gamma_{\ell}+\alpha_{\ell}\frac{1}{|S_{i}|}\sum_{j\in
S_{i}}\mathbbm{1}[\ell=\ell_{j}]+\beta_{\ell}\frac{1}{|L_{i}|}\sum_{j\in
L_{i}}\mathbbm{1}[\ell=\ell_{j}],$ (10)

where for pixel $i$, $S_{i}$ is a small ($5\times 5$) neighborhood around it
and $L_{i}$ is a larger ($50\times 50$) neighborhood. If we set
$\alpha_{\ell}=1$, $\beta_{\ell}=-1$ for all $\ell$, then we consider this a
contrastive prior, as it favors labels $\ell_{i}$ to match the labels found
more concentrated in its immediate neighborhood than in the larger scope. On
the other hand $\alpha_{\ell}$, and $\beta_{\ell}$ can be estimated based on
the current statistics in the label distribution using logistic regression. We
refer to this as a self-similarity prior
$p(\\{\ell_{i}\\};\alpha_{\ell},\beta_{\ell},\gamma_{\ell})$ with parameters
which are periodically fit to the current statistics in the predictions
$\sum_{j\in S_{i}}q(\ell|x_{j})$, and $\sum_{j\in L_{i}}q(\ell|x_{j})$ to
promote similar label patterns across the image. The criterion (8) can also be
seen as a degenerate version of this setting with $S$ being $1\times 1$ and
$L$ being infinite (or the whole image).

The contrastive version of this prior relies on the insight previously pursued
in image self-supervision, e.g., Jean et al. [2019]. In our formulation,
contrasting is accomplished without sampling triplets, but considering all the
data jointly, by expressing the goal of contrasting with far away regions
within the prior in our framework.

As an example of self-supervised pretraining in our framework, in Fig. E.1 we
show an example of clustering a large tile of aerial imagery into 12 classes
using 5 layer FCN as network $q$ of the architecture used in §4.4. The
clustering is achieved by updating the prior every 50 steps of gradient
descent on batches of $200$ $256\times 256$px patches. The prior is
initialized to a contrasting prior, and then updated through gradient descent.
After 7 iterations, the result is sharpened by continuing training using (8).

Figure E.1: Unsupervised clustering using implicit QR loss (middle) of a NAIP
tile (left). On the right, we show the assignment of the 12 clusters to 4 land
cover labels: water (blue), tall vegetation (darker green), low vegetation
(lighter green) and impervious/barren (gray).

This tile was recently used in testing the fine-tuning of a pretrained model
with minimal amount of new labels in a new region [Robinson et al., 2020].
Both the pre-training region, the state of Maryland, and the testing region,
the tiles in New York State, come from the 4-class Chesapeake Land Cover
dataset (§4.3). Yet, the slight shift in geography results in reduction of
accuracy from around $90\%$ in Maryland down to around $72.5\%$ in New York.
In Robinson et al. [2020], various techniques for quick model adaptation are
studied, on labels acquirable in up to 15 minutes of human labeling effort per
tile. In Table E.1 we compare the tunability of our self-supervised models on
the four 85km2 regions tested in Robinson et al. [2020] with active learning
approaches to tuning a pre-trained Maryland model with 400 labeled points. We
show in the table the accuracy and mean intersection over union from Robinson
et al. [2020] for tuning the pretrained model’s last $64\times 4$ layer with
different active learning strategies for selecting points to be labeled. For
example, random selection of 400 points for which the labels are provided
yields an average accuracy improvement from $72.5\%$ to $80.6\%$.

On the other hand, recall that we have created an unsupervised segmentation
into 12 clusters, with posteriors over the clusters $q_{i}(\ell)$. To
investigate how well these clusters align with ground truth land cover labels,
we compute a simple assignment of clusters to land cover labels. Given a set
of labeled points $\\{(i,c_{i})\\}_{i\in I}$, we infer a mapping from clusters
to four target labels,

$p(c|\ell)\propto\sum_{i\in I:c_{i}=c}q_{i}(\ell).$

The label of any point $j$ can now be inferred as
$\hat{\ell}_{j}=\operatorname*{arg\ max}_{c}\sum_{\ell}q_{i}(\ell)p(c|\ell)$.
This procedure, using 400 randomly selected labeled points, yields an average
accuracy of $81.1\%$ (averaged over 50 random collections of labeled points),
which is above the performance of the pretrained model tuned on as many
randomly selected points, and on par with the more sophisticated methods for
point selection and the use of the pretrained model (Table E.1). (Note that
the large model pretrained was trained on a large similar dataset in a nearby
state).

Table E.1: Finetuning a pre-trained model by gradient descent [Robinson et al., 2020] versus implicit QR clustering + label assignment in low-label regimes. |  pretrained model in Robinson et al. [2020] | Implicit QR
---|---|---
Query method | No tuning | Random | Entropy | Min-margin | Random
Tuned parameters | 0 |  64$\times$4 |  64$\times$4 |  64$\times$4 |  12$\times$4
Accuracy % | 72.5 | 80.6 | 73.6 | 81.1 | 81.1
IoU % | 51.0 | 60.8 | 50.1 | 60.8 | 59.8

###  E.2 Tumor-infiltrating lymphocyte segmentation

The setup of this experiment mimics that of the land cover label super-
resolution experiment in §4.3. The training data consists of 50,000 $240\times
240$px crops of H&E-stained histological imagery at 0.5$\mu$m/px resolution,
paired with coarse estimates of the density of tumor-infiltrating lymphocytes
(TILs) created by a simple classifier, at the resolution of $100\times 100$
blocks. The goal is to produce models for high-resolution TIL segmentation.
Models are evaluated on a held-out set of 1786 images with high-resolution
point labels for the center pixel.

The coarse density estimates $c$ belong to one of 10 classes, from 0 (no TILs)
to 9 (highest estimated TIL density). We use an estimated conditional
likelihood $p(\ell|c)$ of the likelihood of the positive TIL label at pixels
with each low-resolution class $c$ to construct a prior $p_{i}(\ell)$ over the
TIL label probability. Notice that this prior is the same for all pixels in
any given low-resolution, coarsely labeled block.444We experimented with
setting $p_{i}(\ell|c)$ to conditional likelihoods estimated from a held-out
set and with simply setting $p_{i}(\ell=1|c=0)=0.05$,
$p_{i}(\ell=1|c=1)=0.15$, …, $p_{i}(\ell=1|c=9)=0.95$. The latter gave better
results, perhaps due to the bias of the evaluation set, in which every image
is known to be centered on a cell of some kind.

We train a small CNN with receptive field $11\times 11$ (five ReLU-activated
convolutional layers with 64 filters) under the RQ loss against this prior for
200 epochs with learning rate $10^{-5}$, then evaluate on the held-out testing
set. Inspired by Malkin et al. [2020], we apply a spatial blur of 11 pixels to
the predicted log-likelihoods (again correcting for the model’s small
receptive field and the dataset bias).

The AUC scores of this model and of the baselines are shown in Table E.2.
Interestingly, the best-performing models -- RQ and epitomic super-resolution
(a generative model) -- both have receptive fields of $11\times 11$, much
smaller than those of the U-Net and fully supervised CNNs. This means that
prediction of TIL likelihood is possible using only _local_ image data, but
the challenge is learning to resolve highly uncertain label information.
Unlike U-Nets and deep CNN autoencoders, small models are not able to learn
and overfit to _distant_ spurious clues to the classes of nearby pixels.

Table E.2: Area under ROC curve for various predictors on the TIL segmentation
task.

| fully supervised | weakly supervised
---|---|---
Model |  SVa,b |  CNNb |  CSP-CNN Hou et al. [2019] |  U-Netc |  Epitomed | RQ
AUC | 0.713 | 0.494 | 0.786 | 0.783 | 0.801 | 0.802

aZhou et al. [2017] bHou et al. [2019] cMalkin et al. [2019] dMalkin et al.
[2020]

###  E.3 Video segmentation with a structured prior

To demonstrate the use of priors with latent structure, we set up the problem
of video segmentation as follows. Given a frame $t$, we tune networks
$q_{t}(\ell_{i,t}|x_{i,t})$ predicting one of $L$ pixel classes for a pixel at
coordinate $i$ in frame $t$. The prior in each frame comes from a Mask R-CNN
model [He et al., 2017] pre-trained on still images in the COCO dataset [Lin
et al., 2014]. The Mask R-CNN model finds several possible instances of
objects of different categories and outputs the soft object masks in form of
confidence scores for each pixel. We convert this into a probability
distribution over the index $f$ (foreground/background) of the form
$p(f_{i,t}|m_{t})$, where $m_{t}$ are different detected instances by the
model, and the distributions $p(f_{i,t}|m_{t})$ are the soft masks for these
instances converted to probability distributions, i.e. value of the
probability of foreground differs for each pixel and each instance based on
the Mask R-CNN confidence scores. Although the COCO dataset may not have had
instances of object of interest in our frame $x_{t}$, we assume that some
admixture (i.e., mixture with sample-dependent weights) of detected instances
(likely involving unrelated types of objects) does model reasonably well the
foreground segmentation in the frame. Mathematically,
$p(f_{i,t})=\sum_{m_{t}}p(f_{i,t}|m_{t})p(m_{t})$, where $p(m_{t})$ expresses
the probabilistic selection of the foreground masks for different instances
from which the foreground is constructed. (One can think of instances $m_{t}$
as akin to topics in topic models, which are also admixture models). To
complete the prior, we fix the distribution $p(\ell|f)$ as fixed binary
$L\times 2$ matrix assigning a subset of $L$ pixel classes to foreground and
the rest to the background. (For example, we assign first 3 classes to
foreground and the remaining 5 to the background for a total of L=8 pixel
classes). Therefore,

$p(\ell_{i,t}=\ell)=\sum_{f}p(\ell|f)\sum_{m_{t}}p(f_{i,t}=f|m_{t})p(m_{t})\leavevmode\nobreak\
.$ (11)

We can now select the instances $m_{t}$ in each frame by optimizing the free
energy with this prior over $p(m_{t})$. The procedure involves standard
variational inference of the posterior distribution over possible instances
$m_{t}$ for each pixel $i$ in frame $t$ which involves the posterior
$q_{t}(\ell_{i,t}|x_{i,t})$. In practice we found that it is enough to do this
inference once, using the network $q_{t-1}$ estimated in the previous frame.

This requires the inference of $m_{t}$ for each pixel $i$:

$s_{i}(m_{t})\propto\exp\left(\sum_{i}\sum_{\ell,f}p(\ell|f)q_{t}(\ell_{i,t}=\ell|x_{i,t})\log
p(f_{i,t}=f|m_{t})p(m_{t})\right),$ (12)

and then optimizing $p_{m_{t}}$ as the count of times each instance is used,

$p(m_{t})\propto\sum_{i}s_{i}(m_{t})\leavevmode\nobreak\ .$ (13)

Selection of instances $m_{t}$ in frame $t$ therefore involves comparing the
predictions from the network $q_{t}(\ell_{i,t}=\ell|x_{i,t})$ grouped into
foreground/background segmentation with the foreground/background segmentation
for different instances from Mask R-CNN, and making a selection of a subset
(probabilistically in $p(m_{t})$) based on which instances most overlap with
the predictions from network $q_{t}$. While the above two equations should in
principle be iterated, and iterated with updates to network
$q_{t}(\ell_{i,t}=\ell|x_{i,t})$, we found that in practice it is sufficient
to just select the instances $m_{t}$ based on their intersection with the
network predictions once, at the very beginning, to make a soft fixed prior,
and leave it to optimizing the prediction network with the RQ loss to find
confident segmentation (Fig. E.2).

We tested the approach on the DAVIS 2016 dataset [Perazzi et al., 2016]. The
dataset is comprised of 50 unique scenes, accompanied by per-pixel
foreground/background segmentation masks. The objective is to produce
foreground segmentation masks for all frames in a scene, given only the ground
truth annotations of the first frame (Semi-Supervised). We evaluated our
method on the 20-scene validation set at 480p resolution.

The network $q$ used in this experiment combines both the pixel intensities
and spatial position information for its predictions. At each pixel location
$i,j$, we augment the intensity information with learned Fourier features
$[\sin(W[i,j]^{T}),\ \cos(W[i,j]^{T})]^{T}$ [Tancik et al., 2020]. The image
and spatial position are first processed separately; A 4-layer, 64-channel,
fully-convolutional network with $3\times 3$ kernels, ReLU activations and
Batch Normalization produces the image features. A 3-layer, 16-channel, pixel-
wise MLP with ReLU activations and Batch Normalization processes the learned
Fourier features. These two are concatenated and passed through a single
$3\times 3$ convolution-ReLU-Batch Normalization layer before being mapped to
output predictions. We also experimented with adding optical flow as another
auxiliary input to the network.

For each scene, the network $q_{0}$ is trained on the first frame, using the
given ground truth annotations split uniformly between 3 foreground and 5
background classes as prior, for 300 iterations. This network is then used to
predict the foreground pixels in the next frame and after computing the
intersection over union between the predicted foreground pixels and the Mask
R-CNN output masks, we select masks that overlap more than a pre-specified
threshold. The chosen masks are then summated, weighted by their Mask R-CNN
confidence scores (0-1), to form the prior for the next frame. The process of
selecting masks from the Mask-RCNN predictions and forming the prior for a
frame is showcased in Figure E.3. The network $q_{0}$ is then fine-tuned for
10 iterations to obtain $q_{1}$ and this process repeats for all subsequent
frames. We used the Adam optimizer, with a starting learning rate of $10^{-3}$
for the first frame, reduced to $10^{-5}$ for fine-tuning, and trained with
batches of 128 64$\times$64 patches.

To infer the foreground pixels we start with a Mask R-CNN pre-trained on the
COCO dataset. Then, for each scene we only require $\sim$1min of training time
on the ground truth-annotated first frame and $\sim$3s per every following
frame for the entire process of forming the prior and inferring the foreground
pixels. We do not train on any video data, in contrast to most video object
segmentation methodologies that rely on both a pre-trained network on static
image datasets (such as COCO) and additionally on offline training on video
sequences. In Table E.3 we compare our results on the DAVIS 2016 validation
set to other video object segmentation algorithms from 2017 - present.

Table E.3: Jaccard and F1 measures for various algorithms on the video
instance segmentation task.

|  | J | F |
---|---|---|---|---
Model |  J&F $\uparrow$ |  Mean $\uparrow$ |  Recall $\uparrow$ |  Decay $\downarrow$ |  Mean $\uparrow$ |  Recall $\uparrow$ |  Decay $\downarrow$ | Year
OSVOS [Caelles et al., 2017] | 80.2 | 79.8 | 93.6 | 14.9 | 80.6 | 92.6 | 15 | 2017
MSK [Perazzi et al., 2017] | 77.55 | 79.7 | 93.1 | 8.9 | 75.4 | 87.1 | 9 | 2017
OnAVOS [Voigtlaender and Leibe, 2017] | 85.5 | 86.1 | 96.1 | 5.2 | 84.9 | 89.7 | 5.8 | 2017
Lucid [Khoreva et al., 2017] | 82.95 | 83.9 | 95 | 9.1 | 82 | 88.1 | 9.7 | 2017
OSVOS-S [Maninis et al., 2018] | 86.55 | 85.6 | 96.8 | 5.5 | 87.5 | 95.9 | 8.2 | 2018
FAVOS [Cheng et al., 2018] | 80.95 | 82.4 | 96.5 | 4.5 | 79.5 | 89.4 | 5.5 | 2018
PReMVOS [Luiten et al., 2018] | 86.75 | 84.9 | 96.1 | 8.8 | 88.6 | 94.7 | 9.8 | 2018
OSMN [Yang et al., 2018] | 73.45 | 74 | 87.6 | 9 | 72.9 | 84 | 10.6 | 2018
AGAME [Johnander et al., 2019] | 81.85 | 81.5 | 93.6 | 9.4 | 82.2 | 90.3 | 9.8 | 2019
STM [Oh et al., 2019] | 89.4 | 88.7 | 97.4 | 5 | 90.1 | 95.2 | 4.2 | 2019
FEELVOS [Voigtlaender et al., 2019] | 81.65 | 81.1 | 90.5 | 13.7 | 82.2 | 86.6 | 14.1 | 2019
CFBI [Yang et al., 2020] | 89.4 | 88.3 | - | - | 90.5 | - | - | 2020
e-OSVOS [Meinhardt and Leal-Taixe, 2020] | 86.8 | 86.6 | - | - | 87 | - | - | 2020
STCN [Cheng et al., 2021] | 91.7 | 90.4 | 98.1 | 4.1 | 93 | 97.1 | 4.3 | 2021
Ours | 83.8 | 84 | 96.2 | 8.4 | 83.6 | 94.2 | 10.2 |
Ours (+flow) | 83.9 | 83.2 | 95.5 | 9.5 | 84.6 | 93.3 | 9.1 |

|  |
---|---|---
Figure E.2: Example of inferring the foreground mask for a single frame.

|
---|---

|  |
---|---|---
|  |

|  |
---|---|---

Figure E.3: Video frame segmentation procedure. Starting with a network
$q_{t-1}$ trained on frame $t-1$, we apply $q_{t-1}$ on frame $t$ to get a
rough foreground estimation (top). By running the pre-trained Mask R-CNN model
on frame $t$ and selecting only the masks that overlap with the $q_{t-1}$
prediction we get the candidate object masks (middle). The prior is
constructed as the sum of the candidate masks, weighted by their corresponding
Mask R-CNN scores (bottom), and $q_{t-1}$ is finetuned on frame $t$ with this
prior to produce the predictions (bottom).

###  E.4 In-collection inference for multi-domain learning: return to Le
Séducteur

One of the conclusions from our experiments on the EnviroAtlas landcover
mapping task (§4.4) is that training a network with the goal of generalizing
to new input data is often inferior to simply performing in-collection
inference for each domain . In other words, given the collection of pairs
$x_{i},p_{i}(\ell)$, learning the posterior $q$ under the implicit posterior
model is optimized for resolving ambiguities in that collection, and possibly
that collection alone. As pointed out in Malkin et al. [2020], which performs
collection inference using large generative models to mine self-similarity
among the examples in the collection, this is appropriate when we can expect
our data $x_{i}$ to always come paired with prior beliefs $p(\ell_{i})$. It is
interesting to reconsider the Seducer example from Fig. 1. The artist created
several versions of that painting in differing styles. Fig. E.4 shows that
collection inference applied separately to each of these paintings works
equally well. However, using a learned $q$ network from one image onto others
yields inferior segmentations (Fig. E.5), as the learned network specialized
for inference in the data it saw. (A fully generative model would be expected
to similarly overtrain on the input data features $x_{i}$, as would a
supervised neural network trained on hard-labeled pairs $(x_{i},\ell_{i})$ due
to the domain shift.) Yet, if we know we will always be given collections with
beliefs in the form of priors $p_{i}(\ell)$, local (collection) inference may
be all we need.

|  |
---|---|---
|  |
Figure E.4: Two additional versions of Le séducteur (left), hand-made priors (middle) and inferred segmentations (right). |  |
---|---|---
(a) | (b) | (c)
Figure E.5: Result of applying a network $q$ trained to infer (b), on all
three Le séducteur versions.