# Improving Label Quality by Jointly Modeling
Items and Annotators

Tharindu Cyril Weerasoriya
Department of Computer Science
Rochester Institute of Technology
Rochester, NY, 14623
<EMAIL_ADDRESS>
&Alexander G. Ororbia
Department of Computer Science
Rochester Institute of Technology
Rochester, NY, 14623
<EMAIL_ADDRESS>
Christopher M. Homan
Department of Computer Science
Rochester Institute of Technology
<EMAIL_ADDRESS>

###### Abstract

We propose a fully Bayesian framework for learning ground truth labels from
noisy annotators. Our framework ensures scalability by factoring a generative,
Bayesian soft clustering model over label distributions into the classic David
and Skene joint annotator-data model. Earlier research along these lines has
neither fully incorporated label distributions nor explored clustering by
annotators only or data only. Our framework incorporates all of these
properties as: (1) a graphical model designed to provide better ground truth
estimates of annotator responses as input to _any_ black box supervised
learning algorithm, and (2) a standalone neural model whose internal structure
captures many of the properties of the graphical model. We conduct supervised
learning experiments using both models and compare them to the performance of
one baseline and a state-of-the-art model.

##  1 Introduction

The recent interest in few- and zero-shot learning and the re-emergence of
weakly supervised learning speaks to the reality that ground truth labels are
a limited resource and that, in many common situations, obtaining them remains
a major challenge. Multiple sources estimate the the global costs of human
annotators (only one of many sources of labels) to be approaching $1–3 billion
by $2026$ and growing [Met19, Res20]. Among the cost-driving challenges is the
noise associated with many of the most common processes for obtaining labels.

In this paper, we explore novel graphical and neural models that tie together
two rather successful approaches, item-annotators tableaus [DS79], and label
distribution learning (LDL) [Gen16], based on converging studies in later
research [VGK+14, LVBH19] on the use of clustering to boost the signal of
noisy data. We adopt a theoretical framework motivated by the anthropologist
Malinowski [Mal67] and first used by Aroyo and Welty [AW14] in the context of
machine learning to characterize meaning as a function of three components: 1)
an act (represented by the learning task), 2) the symbols (the labels), and,
3) the referent (the annotators). Human labeling is a special challenge not
only due to its great expense but also due to the fact that humans often
disagree over the labels that they provide. In fact, it is precisely the
problems where disagreement is most common that human input is hardest to
replace through automation or sensing.

This paper specifically addresses the following research questions:

RQ1:

Do predictive graphical models for LDL that cluster on both item AND annotator
distributions outperform those that do not?

RQ2:

Do predictive neural models for LDL outperform graphical models?

RQ3:

Do predictive neural models for LDL that cluster on both item AND annotator
distributions outperform those that do not?

To help us answer these questions, we contribute two new models. The first is
a generative graphical model that boosts conventional label distribution
learning by clustering label distributions jointly in item and annotator label
distribution spaces. Previous approaches have studied clustering in one space
or the other. This is, to our knowledge, the first time that clustering has
been applied simultaneously to both. Our second model is a neural-based
adaptation of the graphical model. While the graphical model has a sound
theoretical foundation, it is somewhat unwieldy from a computational
perspective. The neural model sacrifices some rigor for more flexibility and
algorithmic efficiency.

##  2 Related Work

The study of annotator disagreement has a long history, coincident with the
emergence of data-driven behavioral research [Coh60]. As mentioned in the
introduction, our approach factors a generative, fully Bayesian soft
clustering model over label distributions into the classic David and Skene
joint annotator-data model. We thus join two streams of loosely related
research.

The earliest of these, by the aforementioned David and Skene [DS79], all use
the multiple labels associated with each data item and each annotator to
jointly estimate the (binary) ground truth label of each item and the error
rate of each annotator, usually via an EM algorithm that alternates between
estimates of ground truth (as hidden variables) and maximizing the error rate.

Later researchers put this model on a fully Bayesian foundation [RYZ+10,
KG12], and consider more complex models of annotator or ground truth, or both
[WWB+09, NJC19]. Notably, (as spam is a common problem in crowdsourced label
sets) several investigators distinguish between honest and dishonest
annotators [RY12, HBKVH13]. More recently, investigators have studied
clustering as an unsupervised approach to discover annotators with similar
behavior [VGK+14]. Yet all of the these approaches are based on the assumption
that each item is associated with a single ground truth label. As a
consequence, the more advanced models tend to represent annotators as a
distribution over a confusion matrix and data items as a single distribution
(sometimes conditioned on input features).

Label distribution learning, by contrast, assumes that ground truth itself is
a distribution. However, the distribution does not necessarily come from a
population of annotators [Gen16, GXX+17, WG19, ZHXM20]. It has found
application in a diverse range of settings [GWX14, GH15, RG17, LG18, SDA+19,
YWZT20]. Here, the goal to predict the distribution of labels associated with
an item, rather than a single ground truth label. It is relatively natural, in
this setting, to consider clustering together related data items to improve
ground truth estimates of label distributions, as several researchers have
done, either in the feature space of the items [ZJL18, ZCX+20] or directly in
the label space of the items themselves [LVSBH19, LVBH19, WLH20].

##  3 Problem Statement

Let $\boldsymbol{X}$ be an $M$-element collection of (unlabeled) _data items_
and $\boldsymbol{Y}\in\mathbb{N}^{M\times N}$ a matrix of _annotator labels_
for some $N$, where each row of $\boldsymbol{Y}$ corresponds to a data item
and each column to an _annotator_. Ideally, we would regard each entry
$\boldsymbol{Y}_{m,n}$ as a probably distribution over a set of labels
$\\{1,\ldots,P\\}$ for some fixed $P$, where the distribution represents
uncertainty about what label annotator $n$ would provide to item $m$. But here
we simplify the model under the assumption that each annotator either provides
a single label or none at all.

So for our purposes, $\boldsymbol{Y}$ is a sparse matrix, where
$\boldsymbol{Y}_{m,n}\in\\{0,\ldots,P\\}$ and $\boldsymbol{Y}_{m,n}=0$
indicates that annotator $n$ did not label item $m$. Crucially, we assume that
each annotator _could_ label the item if asked; however, we have no
information about that particular annotator. As this is a sparse matrix, it is
convenient to let $A=\\{(m,n)~{}|~{}\boldsymbol{Y}_{m,n}\neq 0\\}$ and
$A_{p}=\\{(m,n)~{}|~{}\boldsymbol{Y}_{m,n}=p\\}$.

We consider two gold standards: $f_{\rm dist}$ and $f_{\rm max}$, defined for
data item $\boldsymbol{X}_{m}$ as $f_{\rm dist}(\boldsymbol{X}_{m})=_{\rm
def}\mathrm{P}(p=Y_{m,n}~{}|~{}m,Y_{m,n}>0)$, for $m,n$ chosen uniformly at
random and $f_{\rm max}(\boldsymbol{X}_{m})=_{\rm
def}\arg\max_{p}\mathrm{P}(p=Y_{m,n}~{}|~{}m,Y_{m,n}>0)$. In other words,
$f_{\rm dist}(\boldsymbol{X}_{m})$ represents the gold standard _label
distribution_ associated with each data item and $f_{\rm max}$ is the gold
standard single label that is most likely, according to $f_{\rm dist}$. Note
that $f_{\rm max}$ is more commonly used than $f_{\rm dist}$.

Our learning goals, then, are to produce hypotheses $h_{\rm dist}$ and $h_{\rm
max}$ that approximate $f_{\rm dist}$ and $f_{\rm max}$, respectively, given
$\boldsymbol{X}$ and $\boldsymbol{Y}$. Most learning settings tacitly assume
that annotator disagreement is a sign of _noise_ or _error_ and ignore $d_{\rm
dist}$ entirely. _Label distribution learning_ does the opposite: it assumes
that annotator disagreement is _meaningful_ and specifically seeks to minimize
the loss between $h_{\rm dist}$ and $f_{\rm dist}$. Obviously, both approaches
rely on extreme assumptions that, in practice, are never entirely true.
However, research has shown that even when $f_{\rm max}$ is the goal learning
$h_{\rm dist}$ then taking $h_{\rm max}(\boldsymbol{X}_{m})=_{\rm
def}\arg\max_{p}\mathrm{P}(h_{\rm dist}(\boldsymbol{X}_{m})=p)$ often provides
better results than learning $h_{\rm max}$ directly [VGK+14, LVBH19, WLH20],
and this is what we do here.

##  4 The Probabilistic Graph Model

We call $f_{\rm dist}$ and $f_{\rm max}$ gold standards, not ground truth,
because of the sparseness of $\boldsymbol{Y}$. Although several researchers
have shown that, for the purpose estimating $f_{\rm max}$, three to ten
annotators is sufficient [CB09, DL10], those numbers are far too small to
provide reliable samples of the true distributions of annotator opinions. In
this section, we introduce a new graphical model estimating the ground truth
label distribution, i.e., the distribution of labels from the entire
population of annotators, of each item (which we normally do not have). This
model is based on the assumptions that: (1) all data items (respectively,
annotators) are drawn from one of $K$ (respectively, $L$) latent
classes111Hereafter, to reduce confusion, we reserve “class” to refer only to
the different label choices, as they typically represent an observable class
to which the data item belongs, even though the idea of labels as indivisible
classes runs contrary to the spirit of LDL. or _clusters_ , (2) the label
distribution for each item is strictly a function of the cluster to which it
belongs, (3) the sample of labels given for each item is strictly a function
of the distribution of the cluster to which each annotator belongs, and (4)
the items and annotators are identically and independently sampled (i.i.d.)
and matched uniformly at random.

We then use the graphical model $h_{G}$ to guide supervised learning as a
means of data regularization. See Figure 1. We first use it as a preprocessing
step to supervised learning on our label matrix $Y$, by snapping each input
label distribution $\boldsymbol{Y}_{m}$ to the generating distribution of the
most likely item cluster before training. Note that any supervised learning
method can work as long as it can use a distribution of labels and the
supervising signal. For instance, in our experiments (see Section 6) we use a
combination of deep language models and simple dense networks. Next, after the
predictive model $h_{\rm dist}$ is learned, we postprocess each prediction by,
snapping each output $h_{\rm dist}(\boldsymbol{X}_{m})$ again to the most
likely item cluster.

Figure 1: This workflow diagram shows the dual roles of the graphical model
$h_{G}$, as the output of a supervised learning process $\mathcal{U}$ on the
training labels, which is used to improve the ground truth estimations
$\boldsymbol{Y}^{\prime}$ of the gold standard training label distributions
$\boldsymbol{Y}_{\rm train}$ for supervised learning $\mathcal{S}$, and, once
the model $h_{\rm raw}$ is learned, as a post-processing step after prediction
to generate final hypotheses $h_{\rm dist}$ and $h_{\rm max}$. We use as our
evaluation metrics the accuracy on the most likely label for single label
prediction $h_{\rm max}$ and KL divergence for label distribution learning
$h_{\rm dist}$.

Algorithm 1 describes the model from a generative perspective. See also Figure
2. In addition to the numbers of item and annotator clusters $K$ and $L$, the
model takes three hyperparameters, $\alpha\in\mathbb{R}^{P}$ (recall that $P$
is the number of label classes), $\gamma\in\mathbb{R}^{K}$, and
$\tau\in\mathbb{R}^{L}$, each of which represents a Dirichlet prior on a
categorical distribution. It produces $\boldsymbol{\Theta}_{k,l}$, the label
distribution for each item cluster $k$ and annotator cluster $l$,
$\boldsymbol{\psi}$, the marginal class distribution of items,
$\boldsymbol{\Omega}$, the marginal class distribution of annotators,
$\boldsymbol{w}_{n}$ is the hidden variable representing the class of item
$m$, and $\boldsymbol{z}_{n}$, the hidden variable representing the class of
annotator $n$. Each of these objects is a categorical distribution, and so for
convenience we use subscripts to indicate individual categorical
probabilities. E.g., $\boldsymbol{\Theta}_{k,l,p}=\mathrm{P}(\mbox{The
category is }p)$ and $\boldsymbol{\Omega}_{l}=\mathrm{P}(\mbox{The category is
}l)$.

Algorithm 1 The generative process for $h_{G}$.

Input: Integers $K$, $L$, $M$, $N$, and $P$; Dirichlet hyperparameters
$\alpha\in\mathbb{R}^{P}$, $\gamma\in\mathbb{R}^{K}$, and
$\tau\in\mathbb{R}^{L}$, assignments $A\subseteq\\{1,\ldots
M\\}\times\\{1,\ldots N\\}$

function GenGraph($K$, $L$, $M$, $N$, $P$, $\alpha$, $\gamma$, and $\tau$)

Choose $\boldsymbol{\Theta}\sim{\rm Dir}_{P}(\alpha)^{K\times L}$,
$\triangleright$ One distribution for each item/annotator cluster pair $(k,l)$

Choose $\boldsymbol{\psi}\sim{\rm Dir}_{K}(\gamma)$, $\triangleright$
Distribution of item clusters

Choose $\boldsymbol{\Omega}\sim{\rm Dir}_{L}(\tau)$, $\triangleright$
Distribution of annotator clusters

Choose $\boldsymbol{w}\sim{\rm Cat}_{K}(\boldsymbol{\psi})^{M}$,
$\triangleright$ Assign one latent cluster to each item

Choose $\boldsymbol{z}\sim{\rm Cat}_{L}(\boldsymbol{\Omega})^{N}$,
$\triangleright$ Assign one latent cluster to each annotator

Choose $\boldsymbol{Y}\sim\bigtimes_{(m,n)\in\boldsymbol{A}}{\rm
Cat}_{P}(\boldsymbol{\Theta}_{\boldsymbol{w}_{m},\boldsymbol{z}_{n}})$.
$\triangleright$ Assign labels according to each annotator, item assignment

Figure 2: Plate diagram for the generative graph model.

The joint distribution, under the independence assumptions implied in the
algorithm above, is

$\displaystyle\mathrm{P}_{\alpha,\gamma,\tau}\left(\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y}~{}|~{}\boldsymbol{A}\right)$
$\displaystyle=\mathrm{P}_{\alpha}(\boldsymbol{\Theta})\mathrm{P}_{\gamma}(\boldsymbol{\psi})\mathrm{P}(\boldsymbol{w}|\boldsymbol{\psi})\mathrm{P}_{\tau}(\boldsymbol{\Omega})\mathrm{P}(\boldsymbol{z}|\boldsymbol{\Omega})\prod_{(m,n)\in\boldsymbol{A}}\mathrm{P}(\boldsymbol{Y}_{m,n}|\boldsymbol{\Theta}_{\boldsymbol{w}_{m},\boldsymbol{z}_{n}})$
$\displaystyle=\mathrm{P}_{\alpha}(\boldsymbol{\Theta})\mathrm{P}_{\gamma}(\boldsymbol{\psi})\prod_{m}\mathrm{P}(\boldsymbol{w}_{m}|\boldsymbol{\psi})\mathrm{P}_{\tau}(\boldsymbol{\Omega})\prod_{n}\mathrm{P}(\boldsymbol{z}_{n}|\boldsymbol{\Omega})\prod_{(m,n)\in\boldsymbol{A}}\mathrm{P}(\boldsymbol{Y}_{m,n}|\boldsymbol{\Theta}_{\boldsymbol{w}_{m},\boldsymbol{z}_{n}})$

Note that our distributions are conditioned on $\boldsymbol{A}$. That is, we
always know beforehand which annotators are assigned to which items.
Unfortunately, the coupling between items and annotators makes exact inference
hard, and even resistant to variational approximation. It is, however,
relatively easy to perform simulated annealing over the parameters
$\boldsymbol{\Theta}$, $\boldsymbol{\psi}$, $\boldsymbol{\Omega}$ and hidden
variables $\boldsymbol{w}$, and $\boldsymbol{z}$ as well as EM, using belief
propagation to estimate probability distributions of $\boldsymbol{w}$ and
$\boldsymbol{z}$ during the expectation phase. We explore both learning
algorithms here.

We now describe in more detail how we use the model. We partition our data
into training $(\boldsymbol{X}_{\rm train},\boldsymbol{Y}_{\rm train})$,
development $(\boldsymbol{X}_{\rm dev},\boldsymbol{Y}_{\rm dev})$, and test
$(\boldsymbol{X}_{\rm test},\boldsymbol{Y}_{\rm test})$ splits. During
training, we first apply one of our two unsupervised learning algorithms
$h_{G}=\mathcal{U}(\boldsymbol{Y}_{\rm train})$ to learn a graphical model
$h_{G}=(\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{w},\boldsymbol{z})$
from $\boldsymbol{Y}_{\rm train}$. Note that this provides estimates
$\boldsymbol{w}$ of the latent item cluster to which each item belongs
(simulated annealing provides a hard clustering, EM a soft clustering, but
with EM we consider only the most likely cluster). Then, before supervised
learning, we replace row $\boldsymbol{Y}_{{\rm test},m}$ with the marginal
label distribution associated with item cluster $\boldsymbol{w}_{m}$,

$\displaystyle\boldsymbol{Y}^{\prime}_{m}=\sum_{l}\boldsymbol{\Omega}_{l}\boldsymbol{\Theta}_{\boldsymbol{w}_{m}l},$
(1)

And perform supervised learning $h_{\rm raw}=\mathcal{S}(\boldsymbol{X}_{\rm
train},\boldsymbol{Y}^{\prime})$, yielding a raw label distribution learning
predictor. Note that $\boldsymbol{Y}^{\prime}$ is not a matrix of annotator
labels, as $\boldsymbol{Y}_{\rm train}$ is, but a vector of probability
distributions over labels.

For inference AFTER training (i.e., we do not perform this step during
training), for any input $\boldsymbol{x}$ we project the output of $h_{\rm
raw}(\boldsymbol{x})$ onto our graph model $h_{G}$ to predict the item cluster
membership of item $x$, i.e., let $\mathrm{w}(\boldsymbol{x})$ denote a random
variable for the item cluster assignment of $\boldsymbol{x}$. Then

$\displaystyle\mathrm{P}(\mathrm{w}(\boldsymbol{x})=k)\sim\sum_{l}\boldsymbol{\psi}_{k}\boldsymbol{\Omega}_{l}\mathrm{P}\left(h_{\rm
raw}(\boldsymbol{x})\sim{\rm Cat}_{P}(\boldsymbol{\Theta}_{k,l})\right)$ (2)

We then assign to $x$ the item cluster
$\arg\max_{k}\mathrm{P}(\mathrm{w}(\boldsymbol{x})=k)$, using Equation (1) to
compute $h_{\rm dist}(\boldsymbol{x})$ and define $h_{\rm
max}(\boldsymbol{x})=_{\rm def}\arg\max_{p}\mathrm{P}\left(h_{\rm
dist}(\boldsymbol{x})=p\right)$.

###  4.1 Equations for the Graphical Model

Both the simulated annealing and EM algorithms studied here are based on the
log likelihood formulation of the graphical model:

$\displaystyle\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y}~{}|~{}\boldsymbol{A}\right)$
$\displaystyle=\sum_{k,l}\log p_{\alpha}(\boldsymbol{\Theta}_{k,l})+\log
p_{\gamma}(\boldsymbol{\psi})+\sum_{m}\log
p(\boldsymbol{w}_{m}|\boldsymbol{\psi})$ $\displaystyle\hskip
7.11317pt+p_{\tau}(\boldsymbol{\Omega})+\sum_{n}\log
p(\boldsymbol{z}_{n}|\boldsymbol{\Omega})+\sum_{(m,n)\in\boldsymbol{A}}\log
p(\boldsymbol{Y}_{m,n}|\boldsymbol{\Theta}_{\boldsymbol{w}_{m},\boldsymbol{z}_{n}})$
$\displaystyle=(\alpha-1)\sum_{k,l,p}\log\boldsymbol{\Theta}_{k,l,p}+(\gamma-1)\sum_{k}\log\boldsymbol{\psi}_{k}+\sum_{m}\log\boldsymbol{\psi}_{\boldsymbol{w}_{m}}$
$\displaystyle\hskip
7.11317pt+(\tau-1)\sum_{l}\log\boldsymbol{\Omega}_{l}+\sum_{n}\log\boldsymbol{\Omega}_{\boldsymbol{z}_{n}}+\sum_{(m,n)\in\boldsymbol{A}}\log\boldsymbol{\Theta}_{\boldsymbol{w}_{m},\boldsymbol{z}_{n},\boldsymbol{Y}_{m,n}}.$
(3)

####  4.1.1 Simulated Annealing Equations

Algorithm 2 shows pseudocdoe for performing simulated annealing on the graph
model, where the update probabilities are derived from the log-likelihood
function as follows (note that we iterate over both the parameters and hidden
variables).

Algorithm 2 The simulated annealing process for $h_{G}$.

Input: Integers $K$, $L$, $M$, $N$, and $P$; Dirichlet hyperparameters
$\alpha\in\mathbb{R}^{P}$, $\gamma\in\mathbb{R}^{K}$, and
$\tau\in\mathbb{R}^{L}$, assignments $A\subseteq\\{1,\ldots
M\\}\times\\{1,\ldots N\\}$

function SAGraph($K$, $L$, $M$, $N$, $P$, $\alpha$, $\gamma$, and $\tau$, $A$)

Randomly initialize $\boldsymbol{\Theta}$, $\boldsymbol{\psi}$,
$\boldsymbol{w}$, $\boldsymbol{\Omega}$, $\boldsymbol{z}$

for $t\leftarrow 0,1,\ldots$ do $\triangleright$ Repeat until convergence

Compute
$\textbf{P}_{\alpha,\gamma,\tau}(\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z}~{}|~{}A)$

Store parameters in a priority queue keyed on
$\textbf{P}_{\alpha,\gamma,\tau}(\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z}~{}|~{}A)$

for $k\leftarrow 1,\ldots,K$ do

for $l\leftarrow 1,\ldots,L$ do

Sample a new $\boldsymbol{\Theta}^{\rm new}_{k,l}$

if log-prob w/ $\boldsymbol{\Theta}^{\rm new}_{k,l}>\boldsymbol{\Theta}^{\rm
old}_{k,l}$ then

$\boldsymbol{\Theta}_{k,l}\leftarrow\boldsymbol{\Theta}^{\rm new}_{k,l}$

else

$\boldsymbol{\Theta}_{k,l}\leftarrow\boldsymbol{\Theta}^{\rm new}_{k,l}$ with
prob $e^{\delta_{\boldsymbol{\Theta}_{i,j}}(t+1)}$

Sample a new $\boldsymbol{\psi}^{\rm new}$

if log-prob w/ $\boldsymbol{\psi}^{\rm new}>\boldsymbol{\psi}^{\rm old}$ then

$\boldsymbol{\psi}\leftarrow\boldsymbol{\psi}^{\rm new}$

else

$\boldsymbol{\psi}\leftarrow\boldsymbol{\psi}^{\rm new}$ with prob
$e^{\delta_{\boldsymbol{\psi}}(t+1)}$

Sample a new $\boldsymbol{\Omega}^{\rm new}$

if log-prob w/ $\boldsymbol{\Omega}^{\rm new}>\boldsymbol{\Omega}^{\rm old}$
then

$\boldsymbol{\Omega}\leftarrow\boldsymbol{\Omega}^{\rm new}$

else

$\boldsymbol{\Omega}\leftarrow\boldsymbol{\Omega}^{\rm new}$ with prob
$e^{\delta_{\boldsymbol{\Omega}}(t+1)}$

for $n\in 1,\ldots,M$ do

Sample a new $\boldsymbol{w}^{\rm new}_{m}$

if log-prob w/ $\boldsymbol{w}^{\rm new}_{m}>\boldsymbol{w}^{\rm old}_{m}$
then

$\boldsymbol{w}_{m}\leftarrow\boldsymbol{w}^{\rm new}_{m}$

else$\boldsymbol{w}_{m}\leftarrow\boldsymbol{w}^{\rm new}_{m}$ with prob
$e^{\delta_{\boldsymbol{w}_{m}}(t+1)}$

for $n\in N$ do

Sample a new $\boldsymbol{z}^{\rm new}_{n}$

if the log-prob w/ $\boldsymbol{z}^{\rm new}_{n}>\boldsymbol{z}^{\rm old}_{n}$
then

$\boldsymbol{z}_{n}\leftarrow\boldsymbol{z}^{\rm new}_{n}$

else

$\boldsymbol{z}_{n}\leftarrow\boldsymbol{z}^{\rm new}_{n}$ with prob
$e^{\delta_{\boldsymbol{z}_{n}}(t+1)}$ return the parameters that maximize
$\textbf{P}_{\alpha,\gamma,\tau}(\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z}~{}|~{}A)$.

$\displaystyle\delta_{\boldsymbol{\Theta}_{i,j}}=\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{\Theta}^{\rm
NEW}_{k,l}~{}|~{}\boldsymbol{\Theta}_{-k,-l},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y},\boldsymbol{A}\right)-\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{\Theta}^{\rm
OLD}_{k,l}~{}|~{}\boldsymbol{\Theta}_{-k,-l},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y},\boldsymbol{A}\right)$
$\displaystyle=(\alpha-1)\sum_{p}\log\frac{\boldsymbol{\Theta}^{\rm
NEW}_{k,l,p}}{\boldsymbol{\Theta}^{\rm
OLD}_{k,l,p}}+\sum_{(m,n)\in\boldsymbol{A}:(\boldsymbol{w}_{m},\boldsymbol{z}_{n})=(k,l)}\log\frac{\boldsymbol{\Theta}^{\rm
NEW}_{k,l,\boldsymbol{Y}_{m,n}}}{\boldsymbol{\Theta}^{\rm
OLD}_{k,l,\boldsymbol{Y}_{m,n}}}$
$\displaystyle\delta_{\boldsymbol{\psi}}=\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{\psi}^{\rm
NEW}~{}|~{}\boldsymbol{\Theta},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y},\boldsymbol{A}\right)-\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{\psi}^{\rm
OLD}~{}|~{}\boldsymbol{\Theta},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y},\boldsymbol{A}\right)$
$\displaystyle=(\gamma-1)\sum_{k}\log\frac{\boldsymbol{\psi}^{\rm
NEW}_{k}}{\boldsymbol{\psi}^{\rm OLD}_{k}}$
$\displaystyle\delta_{\boldsymbol{\Omega}}=\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{\Omega}^{\rm
NEW}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{z},\boldsymbol{Y},\boldsymbol{A}\right)-\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{\Omega}^{\rm
OLD}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\
\boldsymbol{z},\boldsymbol{Y},\boldsymbol{A}\right)$
$\displaystyle=(\tau-1)\sum_{l}\log\frac{\boldsymbol{\Omega}^{\rm
NEW}_{l}}{\boldsymbol{\Omega}^{\rm OLD}_{l}}$
$\displaystyle\delta_{\boldsymbol{w}_{m}}=\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{w}^{\rm
NEW}_{m}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w}_{-m},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y},\boldsymbol{A}\right)-\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{w}^{\rm
OLD}_{m}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w}_{-m},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y},\boldsymbol{A}\right)$
$\displaystyle=\log\frac{\boldsymbol{\psi}_{\boldsymbol{w}^{\rm
NEW}_{m}}}{\boldsymbol{\psi}_{\boldsymbol{w}^{\rm
OLD}_{m}}}+\sum_{n:(m,n)\in\boldsymbol{A}}\log\frac{\boldsymbol{\Theta}_{\boldsymbol{w}^{\rm
NEW}_{m},\boldsymbol{z}_{n},\boldsymbol{Y}_{m,n}}}{\boldsymbol{\Theta}_{\boldsymbol{w}^{\rm
OLD}_{m},\boldsymbol{z}_{n},\boldsymbol{Y}_{m,n}}}$
$\displaystyle\delta_{\boldsymbol{z}_{n}}=\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{z}^{\rm
NEW}_{m}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z}_{-m},\boldsymbol{Y},\boldsymbol{A}\right)-\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{z}^{\rm
OLD}_{m}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z}_{-m},\boldsymbol{Y},\boldsymbol{A}\right)$
$\displaystyle=\log\frac{\boldsymbol{\Omega}_{\boldsymbol{z}^{\rm
NEW}_{n}}}{\boldsymbol{\Omega}_{\boldsymbol{z}^{\rm
OLD}_{n}}}+\sum_{m:(m,n)\in\boldsymbol{A}}\log\frac{\boldsymbol{\Theta}_{\boldsymbol{w}_{m},\boldsymbol{z}^{\rm
NEW}_{n},\boldsymbol{Y}_{m,n}}}{\boldsymbol{\Theta}_{\boldsymbol{w}_{m},\boldsymbol{z}^{\rm
OLD}_{n},\boldsymbol{Y}_{m,n}}}$

####  4.1.2 EM Equations

The expectation formulation of equation (4.1) is

$\displaystyle
E_{\hat{\boldsymbol{w}},\hat{\boldsymbol{z}}}\left[\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y}~{}|~{}\boldsymbol{A}\right)\right]$
$\displaystyle=\sum_{k,l}\log p_{\alpha}(\boldsymbol{\Theta}_{k,l})+\log
p_{\gamma}(\boldsymbol{\psi})+\sum_{m}E_{\hat{\boldsymbol{w}},\hat{\boldsymbol{z}}}\left[\log
p(\boldsymbol{w}_{m}|\boldsymbol{\psi})\right]$ $\displaystyle\hskip
7.11317pt+p_{\tau}(\boldsymbol{\Omega})+\sum_{n}E_{\hat{\boldsymbol{w}},\hat{\boldsymbol{z}}}\left[\log
p(\boldsymbol{z}_{n}|\boldsymbol{\Omega})\right]+\sum_{(m,n)\in\boldsymbol{A}}E_{\hat{\boldsymbol{w}},\hat{\boldsymbol{z}}}\left[\log
p(\boldsymbol{Y}_{m,n}|\boldsymbol{\Theta}_{\boldsymbol{w}_{m},\boldsymbol{z}_{n}})\right]$
$\displaystyle=(\alpha-1)\sum_{k,l,p}\log\boldsymbol{\Theta}_{k,l,p}+(\gamma-1)\sum_{k}\log\boldsymbol{\psi}_{k}+\sum_{m}\sum_{k}\boldsymbol{w}_{mk}\log\boldsymbol{\psi}_{k}$
$\displaystyle\hskip
7.11317pt+(\tau-1)\sum_{l}\log\boldsymbol{\Omega}_{l}+\sum_{n}\sum_{l}\boldsymbol{z}_{nl}\log\boldsymbol{\Omega}_{l}+\sum_{(m,n)\in\boldsymbol{A}}\sum_{k}\sum_{l}\boldsymbol{w}_{mk}\boldsymbol{z}_{nl}\log\boldsymbol{\Theta}_{k,l,\boldsymbol{Y}_{m,n}}.$
(4)

Algorithm 3 summarizes the process. Note that we perform the “M” step before
the “E” step in each round. This is arbitrary. Also, though we perform at most
ten rounds of belief propagation at each outer iteration, in practice it we
usually get convergence within two rounds, which we define as

$\displaystyle\sum_{n}KL(\boldsymbol{w}^{\rm NEW}_{n}||\boldsymbol{w}^{\rm
OLD}_{n})+\sum_{m}KL(\boldsymbol{z}^{\rm NEW}_{m}||\boldsymbol{z}^{\rm
OLD}_{m}).$ (5)

Algorithm 3 The EM process for $h_{G}$.

Input: Integers $K$, $L$, $M$, $N$, and $P$; Dirichlet hyperparameters
$\alpha\in\mathbb{R}^{P}$, $\gamma\in\mathbb{R}^{K}$, and
$\tau\in\mathbb{R}^{L}$, assignments $A\subseteq\\{1,\ldots
M\\}\times\\{1,\ldots N\\}$

function SAGraph($K$, $L$, $M$, $N$, $P$, $\alpha$, $\gamma$, and $\tau$, $A$)

Randomly initialize $\boldsymbol{\Theta}$, $\boldsymbol{\psi}$,
$\boldsymbol{w}$, $\boldsymbol{\Omega}$, $\boldsymbol{z}$

loop$\triangleright$ Repeat until convergence

Compute $\boldsymbol{\Theta}$, $\boldsymbol{\psi}$, and $\boldsymbol{\Omega}$,
according to the maximization equations given in Section 4.1.3.

loop$\triangleright$ Do ten times or until convergence

Update $\boldsymbol{w}$ according to the belief propagation equation given in
Section 4.1.4

Update $\boldsymbol{z}$ according to the belief propagation equation given in
Section 4.1.4 return
$\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z}$.

####  4.1.3 Maximization Equations for Model Parameters

Subject to the constraints

$\displaystyle\boldsymbol{\Lambda}_{\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega}}$
$\displaystyle=\sum_{k,l}\lambda_{\boldsymbol{\Theta}_{k,l}}\left(1-\sum_{p}\boldsymbol{\Theta}_{k,l,p}\right)+\lambda_{\boldsymbol{\psi}}\left(1-\sum_{k=1}^{K}\boldsymbol{\psi}_{k}\right)+\lambda_{\boldsymbol{\Omega}}\left(1-\sum_{l=1}^{L}\boldsymbol{\Omega}_{l}\right),$

we can maximize the parameters
$\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega}$ by take partial
derivatives and setting to zero. Thus,

$\displaystyle\frac{\partial
E_{\hat{\boldsymbol{w}},\hat{\boldsymbol{z}}}\left[\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y}~{}|~{}\boldsymbol{A}\right)\right]+\Lambda}{\partial\Theta_{k,l,p}}$
$\displaystyle=\frac{\alpha-1}{\boldsymbol{\Theta}_{k,l,p}}+\sum_{(m,n)\in\boldsymbol{A}_{\cdot,\cdot,p}}\frac{\boldsymbol{w}_{mk}\boldsymbol{z}_{nl}}{\boldsymbol{\Theta}_{k,l,\boldsymbol{Y}_{m,n}}}-\lambda_{\boldsymbol{\Theta}_{k,l}}=0$
$\displaystyle\alpha-1+\sum_{(m,n)\in\boldsymbol{A}_{\cdot,\cdot,p}}\boldsymbol{w}_{mk}\boldsymbol{z}_{nl}-\lambda_{\boldsymbol{\Theta}_{k,l}}\boldsymbol{\Theta}_{k,l,p}$
$\displaystyle=0$ $\displaystyle
P\alpha-P+\sum_{(m,n)\in\boldsymbol{A}}\boldsymbol{w}_{mk}\boldsymbol{z}_{nl}-\lambda_{\boldsymbol{\Theta}_{k,l}}$
$\displaystyle=0$ $\displaystyle\boldsymbol{\Theta}_{k,l,p}$
$\displaystyle=\frac{\alpha-1+\sum_{(m,n)\in\boldsymbol{A}_{\cdot,\cdot,p}}\boldsymbol{w}_{mk}\boldsymbol{z}_{nl}}{P\alpha-P+\sum_{(m,n)\in\boldsymbol{A}}\boldsymbol{w}_{mk}\boldsymbol{z}_{nl}}$
$\displaystyle\frac{\partial
E_{\hat{\boldsymbol{w}},\hat{\boldsymbol{z}}}\left[\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y}~{}|~{}\boldsymbol{A}\right)\right]+\Lambda}{\partial\boldsymbol{\psi}_{k}}$
$\displaystyle=\frac{\gamma-1}{\boldsymbol{\psi}_{k}}+\sum_{m}\frac{\boldsymbol{w}_{mk}}{\boldsymbol{\psi}_{k}}-\lambda_{\boldsymbol{\psi}}=0$
$\displaystyle\gamma-1+\sum_{m}\boldsymbol{w}_{mk}-\lambda_{\boldsymbol{\psi}}\boldsymbol{\psi}_{k}$
$\displaystyle=0$ $\displaystyle K\gamma-K+M-\lambda_{\boldsymbol{\psi}}$
$\displaystyle=0$ $\displaystyle\boldsymbol{\psi}_{k}$
$\displaystyle=\frac{\gamma-1+\sum_{m}\boldsymbol{w}_{mk}}{K\gamma-K+M}$
$\displaystyle\frac{\partial
E_{\hat{\boldsymbol{w}},\hat{\boldsymbol{z}}}\left[\ell_{\alpha,\gamma,\tau}\left(\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y}~{}|~{}\boldsymbol{A}\right)\right]+\Lambda}{\partial\boldsymbol{\Omega}_{l}}$
$\displaystyle=\frac{\tau-1}{\boldsymbol{\Omega}_{l}}+\sum_{n}\frac{\boldsymbol{z}_{nl}}{\boldsymbol{\Omega}_{l}}-\lambda_{\boldsymbol{\Omega}}=0$
$\displaystyle\tau-1+\sum_{n}\boldsymbol{z}_{nl}-\lambda_{\boldsymbol{\Omega}}\boldsymbol{\Omega}_{l}$
$\displaystyle=0$ $\displaystyle L\tau-L+N-\lambda_{\boldsymbol{\Omega}}$
$\displaystyle=0$ $\displaystyle\boldsymbol{\Omega}_{l}$
$\displaystyle=\frac{\tau-1+\sum_{n}\boldsymbol{z}_{nl}}{L\tau-L+N}$
$\displaystyle\sum_{p}\boldsymbol{\Theta}_{k,l,p}$ $\displaystyle=1$
$\displaystyle\sum_{k=1}^{K}\boldsymbol{\psi}_{k}$ $\displaystyle=1$
$\displaystyle\sum_{l=1}^{L}\boldsymbol{\Omega}_{l}$ $\displaystyle=1$

####  4.1.4 Belief Propagation Equations for EM

Note that the hidden variables $\boldsymbol{w}$ and $\boldsymbol{z}$ have a
bipartite dependency structure, where (conditioned on all of the model
parameters and observed variables) the class of any hidden variable is
independent of all other hidden variables, given only the hidden variables it
is assigned to:

$\displaystyle\hat{p}_{\alpha,\gamma,\tau}\left(\boldsymbol{w}_{m^{\prime}}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},(\boldsymbol{z}_{n}:(n,m)\in\boldsymbol{A}),\boldsymbol{Y},\boldsymbol{A}\right)$
$\displaystyle=p_{\alpha,\gamma,\tau}\left(\boldsymbol{w}_{m^{\prime}}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{w}_{-m^{\prime}},\boldsymbol{\Omega},\boldsymbol{z},\boldsymbol{Y},\boldsymbol{A}\right)$

(likewise for $\boldsymbol{z}_{n^{\prime}}$). According to this observation,

$\displaystyle
p_{\alpha,\gamma,\tau}\left(\boldsymbol{w}_{m^{\prime}}=k^{\prime}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y},\boldsymbol{A}\right)$
$\displaystyle=\sum_{(\boldsymbol{z}_{n}:n\in\boldsymbol{A}_{m^{\prime},\cdot})\in\mathbb{Z}_{L}^{\|\boldsymbol{A}{m^{\prime},\cdot}\|}}\frac{p_{\alpha,\gamma,\tau}\left(\boldsymbol{w}_{m^{\prime}},(\boldsymbol{z}_{n}:n\in\boldsymbol{A}_{m^{\prime},\cdot}),\boldsymbol{Y}_{m^{\prime},\cdot}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y}_{-m^{\prime},\cdot},\boldsymbol{A}\right)}{p_{\alpha,\gamma,\tau}\left(\boldsymbol{Y}_{m^{\prime},\cdot}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y}_{-m^{\prime},n},\boldsymbol{A}\right)}.$
$\displaystyle=\sum_{(\boldsymbol{z}_{n}:n\in\boldsymbol{A}_{m^{\prime},\cdot})\in\mathbb{Z}_{L}^{\|\boldsymbol{A}_{m^{\prime},\cdot}\|}}\frac{p(\boldsymbol{w}_{m^{\prime}}|\boldsymbol{\psi})\prod_{n\in\boldsymbol{A}_{m^{\prime},\cdot}}p(\boldsymbol{Y}_{m^{\prime},n}|{\boldsymbol{\Theta},\boldsymbol{w}_{m},\boldsymbol{z}_{n}})\hat{p}_{\alpha,\gamma,\tau}\left(\boldsymbol{z}_{n}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y}_{-m^{\prime},\cdot},\boldsymbol{A}\right)}{p_{\alpha,\gamma,\tau}\left(\boldsymbol{Y}_{m^{\prime},\cdot}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y}_{m^{\prime},\cdot},\boldsymbol{A}\right)}$
$\displaystyle=\frac{p(\boldsymbol{w}_{m^{\prime}}|\boldsymbol{\psi})\prod_{n\in\boldsymbol{A}_{m^{\prime},\cdot}}\sum_{l\in\mathbb{Z}_{L}}p(\boldsymbol{Y}_{m^{\prime},n}|{\boldsymbol{\Theta},\boldsymbol{w}_{m},\boldsymbol{z}_{n}})\hat{p}_{\alpha,\gamma,\tau}\left(\boldsymbol{z}_{n}=l~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y}_{-m^{\prime},n},\boldsymbol{A}\right)}{p_{\alpha,\gamma,\tau}\left(\boldsymbol{Y}_{m^{\prime},\cdot}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y}_{-m,n},\boldsymbol{A}\right)}$
$\displaystyle=p(\boldsymbol{w}_{m^{\prime}}|\boldsymbol{\psi})\prod_{n\in\boldsymbol{A}_{m^{\prime},\cdot}}\sum_{l\in\mathbb{Z}_{L}}p(\boldsymbol{Y}_{m^{\prime},n}|{\boldsymbol{\Theta},\boldsymbol{w}_{m},\boldsymbol{z}_{n}})\hat{p}_{\alpha,\gamma,\tau}\left(\boldsymbol{z}_{n}=l~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y},\boldsymbol{A}\right)$
$\displaystyle=\boldsymbol{\psi}_{\boldsymbol{w}_{m^{\prime}}}\prod_{n\in\boldsymbol{A}_{m^{\prime},\cdot}}\sum_{l\in\mathbb{Z}_{L}}\boldsymbol{\Theta}_{\boldsymbol{w}_{m^{\prime}},\boldsymbol{z}_{n},\boldsymbol{Y}_{m^{\prime},n}}\hat{p}_{\alpha,\gamma,\tau}\left(\boldsymbol{z}_{n}=l~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y}_{-(m^{\prime},n)},\boldsymbol{A}\right)$
$\displaystyle=\hat{p}_{\alpha,\gamma,\tau}\left(\boldsymbol{w}_{m^{\prime}},(\boldsymbol{Y}_{m^{\prime},n}:n\in\boldsymbol{A}_{m^{\prime},\cdot})~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},(\boldsymbol{Y}_{m,n}:n\not\in\boldsymbol{A}_{m^{\prime},\cdot}),\boldsymbol{A}\right)$

And so:

$\displaystyle
p_{\alpha,\gamma,\tau}\left(\boldsymbol{w}_{m^{\prime}}=k^{\prime}~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y},\boldsymbol{A}\right)$
$\displaystyle=\frac{p_{\alpha,\gamma,\tau}\left(\boldsymbol{w}_{m^{\prime}}=k^{\prime},(\boldsymbol{Y}_{m^{\prime},n}:n\in\boldsymbol{A}_{m^{\prime},\cdot})~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{A},(\boldsymbol{Y}_{m,n}:n\not\in\boldsymbol{A}_{m^{\prime},\cdot})\right)}{\sum_{k\in\mathbb{Z}_{K}}p_{\alpha,\gamma,\tau}\left(\boldsymbol{w}_{m^{\prime}}=k,(\boldsymbol{Y}_{m^{\prime},n}:n\in\boldsymbol{A}_{m^{\prime},\cdot})~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{A},(\boldsymbol{Y}_{m,n}:n\not\in\boldsymbol{A}_{m^{\prime},\cdot})\right)}$
$\displaystyle=\frac{\boldsymbol{\psi}_{\boldsymbol{w}_{m^{\prime}}}\prod_{n\in\boldsymbol{A}_{m^{\prime},\cdot}}\sum_{l\in\mathbb{Z}_{L}}\boldsymbol{\Theta}_{\boldsymbol{w}_{m},\boldsymbol{z}_{n},\boldsymbol{Y}_{m^{\prime},n}}\hat{p}_{\alpha,\gamma,\tau}\left(\boldsymbol{z}_{n}=l~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y}_{-(m^{\prime},n)},\boldsymbol{A}\right)}{\sum_{k\in\mathbb{Z}_{K}}\boldsymbol{\psi}_{k}\prod_{n\in\boldsymbol{A}_{m^{\prime},\cdot}}\sum_{l\in\mathbb{Z}_{L}}\boldsymbol{\Theta}_{k,\boldsymbol{z}_{n},\boldsymbol{Y}_{m^{\prime},n}}\hat{p}_{\alpha,\gamma,\tau}\left(\boldsymbol{z}_{n}=l~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y}_{-(m^{\prime},n)},\boldsymbol{A}\right)}$

Note that this requires us to use
$\hat{p}_{\alpha,\gamma,\tau}\left(\boldsymbol{z}_{n}=l~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y}_{-(m^{\prime},n)},\boldsymbol{A}\right)$
for each $n\in\boldsymbol{A}_{m^{\prime}}$. Anticipating its use the analogous
message passing formula for $\boldsymbol{z}_{n^{\prime}}$, we can calculate
$\hat{p}_{\alpha,\gamma,\tau}\left(\boldsymbol{w}_{m^{\prime}}=k~{}|~{}\boldsymbol{\Theta},\boldsymbol{\psi},\boldsymbol{\Omega},\boldsymbol{Y}_{-(m^{\prime},n^{\prime})},\boldsymbol{A}\right)$
for each $n^{\prime}\in\boldsymbol{A}_{m^{\prime}}$ by removing the
$n^{\prime}$th term in each of the products above.

##  5 A Neural Probabilistic Model for Estimating Label Distributions

Figure 3: Block diagram showing the main components/parameters of the proposed
LDL-NM.

The design of our proposed neural model was inspired/motivated by the
structure of the graphical models presented in the last section. Specifically,
we envisioned the model as forming a type of generative process that could
generate item label, annotator label, and full ground-truth distributions over
classes. We furthermore opted to craft an encoder-decoder design for the
underlying artificial neural network (ANN) in order to facilitate tractable
inference and parameter learning.

Our probabilistic neural model (LDL-NM) is defined by a set of synaptic weight
parameter matrices housed in two constructs
$\Theta_{e}=\\{\mathbf{W}_{I},\mathbf{W}_{A},\mathbf{W}_{P},\mathbf{W}_{E}\\}$
and $\Theta_{d}=\\{\mathbf{W}_{yI},\mathbf{W}_{yA},\mathbf{W}_{y}\\}$ (bias
vectors omitted for clarity), where $\Theta_{e}$ contains the encoder
parameters and $\Theta_{d}$ contains the decoder parameters. The model is
designed, for each data item feature vector $\mathbf{x}_{i}$ and annotator
(index) $a$ pair, to estimate the values of a set of target label
distributions, i.e., the item label distribution $\mathbf{y}_{I}$ the
annotator label distribution $\mathbf{y}_{A}$, and the (ground-truth) label
distribution $\mathbf{y}$.

The output of the encoder is the latent representation of data items and
annotators – note that the data item is projected to the space
$\mathbf{z}_{I}$ while the annotator identification integer is embedded into
the space $\mathbf{z}_{A}$. As a result, the encoder, which takes in as input
the data item feature vector $\mathbf{x}_{I}\in\mathcal{R}^{J\times 1}$ ($J$
is the dimensionality of the feature space) and the annotator identifier
$a\in\mathbb{N}_{0}$ (the set of natural numbers including zero), computes the
following output:

$\displaystyle\mathbf{z}_{I}$
$\displaystyle=\mathbf{W}_{I}\cdot\mathbf{x}_{I},\;\mbox{and},\;\mathbf{z}_{A}=\mathbf{W}_{A}\cdot\text{enc}(a)$
(6) $\displaystyle\mathbf{z}_{P}$
$\displaystyle=\phi(\mathbf{W}_{P}\cdot\phi([\mathbf{z}_{I},\mathbf{z}_{A}])),\;\mbox{and},\;\mathbf{z}_{E}=\phi\big{(}(\mathbf{W}_{E}\cdot\mathbf{z}_{P})+\mathbf{z}_{P}\big{)}$
(7)

where $\cdot$ denotes matrix multiplication, $[\mathbf{a},\mathbf{b}]$
represents vector combination operation applied to input vectors $\mathbf{a}$
and $\mathbf{b}$ (such as concatenation or element-wise summation), and
$\text{enc}(a)$ is a function to convert integer $a$ to a corresponding one-
hot encoding binary vector. $\phi(\mathbf{v})=1/|1+\mathbf{v}|$ is the
softsign elementwise activation function.
$\mathbf{z}_{I}\in\mathcal{R}^{J_{I}\times 1}$ and
$\mathbf{z}_{A}\in\mathcal{R}^{J_{A}\times 1}$ where $J_{I}$ and $J_{A}$ are
their respective embedding dimensionalities. An additional linear projection
is applied to the combined item and annotator embeddings via matrix
$\mathbf{W}_{P}$ to reduce the dimesionality further to
$\mathbf{z}_{E}\in\mathcal{R}^{J_{P}\times 1}$ before running the
representation through one more non-linear transform (to obtain encoder output
$\mathbf{z}_{E}$).

The decoder, which takes in as input the latent code produced by the encoder
$\mathbf{z}_{E}$, computes its outputs (three different label distribution
estimates) as follows:

$\displaystyle\mathbf{z}_{y}$
$\displaystyle=\sigma(\mathbf{W}_{y}\cdot\mathbf{z}_{E}),\;\mathbf{z}_{yI}=\sigma(\mathbf{W}_{yI}\cdot\mathbf{z}_{E}),\;\mathbf{z}_{yA}=\sigma(\mathbf{W}_{yA}\cdot\mathbf{z}_{E})$
(8)

where $\sigma(\mathbf{v})=\exp(\mathbf{v})/\sum_{j}\exp(\mathbf{v})[j]$ is the
softmax function ($\mathbf{v}[j]$ retrieves the $j$the value/element of the
vector $\mathbf{v}$). Notice that a residual connection has been introduced in
Equation 7 to improve gradient flow during model training. Note that, under
our proposed LDL-NM, $\mathbf{z}_{y}$ is interpreted as
$p(\mathbf{y}|\mathbf{x}_{i},a)$, $\mathbf{z}_{yI}$ is interpreted as
$p(\mathbf{y}_{I}|\mathbf{x}_{i},a)$, and $\mathbf{z}_{yA}$ is interpreted as
$p(\mathbf{y}_{A}|\mathbf{x}_{i},a)$.

###  5.1 Parameter Optimization

To train model parameters $\Theta=\\{\Theta_{e},\Theta_{d}\\}$, we propose the
following multi-objective function:

$\displaystyle\mathcal{L}(\Theta)=-\sum_{j}\big{(}\mathbf{y}\otimes\log(\mathbf{z}_{y})\big{)}[j]+\text{KL}(\mathbf{y}_{I}||\mathbf{z}_{yI})+\text{KL}(\mathbf{y}_{A}||\mathbf{z}_{yA})$
(9)

where the first term is the negative Categorical log likelihood of the target
one-hot encoded label $\mathbf{y}$ and the second and third terms measure the
Kullback-Leibler (KL) divergence of between the decoder’s estimate of the item
label distribution $\mathbf{y}_{i}$ and annotator label distribution
$\mathbf{y}_{a}$, respectively. Specifically, the form of the KL divergence we
use compares two multinomial/multinoulli distributions222The forms of these KL
divergences were derived by exploiting Stirling’s approximation [Jay03] to
deal with the factorial that appears in the definition of the multinomial
likelihood. Full derivation included in AppendixA. :

$\displaystyle-\text{KL}(\mathbf{y}_{I}||\mathbf{z}_{yi};\Theta)$
$\displaystyle=-\sum_{j}\big{(}\mathbf{y}_{I}\otimes\log\mathbf{y}_{I}\big{)}[j]+\sum_{j}\big{(}\mathbf{y}_{I}\otimes\log\mathbf{z}_{yI}\big{)}[j]$
(10) $\displaystyle-\text{KL}(\mathbf{y}_{A}||\mathbf{z}_{yA};\Theta)$
$\displaystyle=-\sum_{j}\big{(}\mathbf{y}_{A}\otimes\log\mathbf{y}_{A}\big{)}[j]+\sum_{j}\big{(}\mathbf{y}_{A}\otimes\log\mathbf{z}_{yA}\big{)}[j]$
(11)

where $\otimes$ denotes the Hadamard product and unit of measurement for each
KL divergence is the nat. The LDL-NM parameters are adjusted to minimize the
function defined in Equation 9 by calculating the gradients with respect to
both the encoder and decoder weights, i.e.,
$\frac{\partial\mathcal{L}(\Theta_{e},\Theta_{d})}{\partial\Theta_{e}}$ and
$\frac{\partial\mathcal{L}(\Theta_{e},\Theta_{d})}{\partial\Theta_{d}}$. The
resultant partial derivatives are then used to change the current values in
$\Theta_{e}$ and $\Theta_{d}$ via stochastic gradient descent or with a more
advanced adaptive learning rate rule such as Adam [KB14].

###  5.2 Test-Time Usage

While the LDL-NM is a rather general-purpose neural model and can be used in a
variety of interesting ways when it comes to modeling items and annotators, in
this study, there are two particular use-cases of the LDL-NM we are interested
in.

Algorithm 4 The iterative inference process for the LDL-NM.

Input: Sample $(\mathbf{x}_{I},\mathbf{y}_{I})$, $\beta$, $\gamma$, $K$,
$\sigma_{a}$, and $\Theta=\\{\Theta_{e},\Theta_{d}\\}$

function InferA($\mathbf{x}_{I},\mathbf{y}_{I},\Theta$) $\triangleright$ Run
$K$-step inference to find $\mathbf{z}_{A}$

$\mathbf{z}_{A}\sim\mathcal{N}(\mu=0,\sigma_{a})$, or,
$\mathbf{z}_{A}=\mathbf{0}$$\triangleright$ Initialize annotator embedding(s)

for $k=0$ to $K$ do

Run Equations 6-7 and then $\mathbf{z}_{yI}=\sigma(W_{yI}\cdot\mathbf{z}_{E})$

Calculate $\text{KL}(\mathbf{y}_{I}||\mathbf{z}_{yI};\Theta)$

if Termination criterion not met then

$\mathbf{z}_{A}\leftarrow\mathbf{z}_{A}-\beta\frac{\partial\text{KL}(\mathbf{y}_{I}||\mathbf{z}_{yI};\Theta)}{\partial\mathbf{z}_{A}}-\gamma\mathbf{z}_{A}$

Return $\mathbf{z}_{A}$ and
$\text{KL}(\mathbf{y}_{I}||\mathbf{z}_{yI};\Theta)$

The first involves using the model to make a prediction of the label for item
feature vector $\mathbf{x}_{i}$ given only its particular item label
distribution $\mathbf{y}_{i}$. In this case, the LDL-NM makes multiple
predictions of the possible label, one per annotator embedding stored in its
internal memory. This inference is done by first modifying Equation 7 as
follows:

$\displaystyle\mathbf{z}=\phi(\mathbf{W}_{A}+\mathbf{z}_{I}),\;\mbox{and},\;\mathbf{z}_{e}=\phi\big{(}(\mathbf{W}_{E}\cdot\mathbf{z})+\mathbf{z}\big{)}$
(12)

where $\mathbf{z}_{I}$ is added to each column of $\mathbf{W}_{A}$. When using
Equation 12, the resulting outputs $\mathbf{z}_{y}$, $\mathbf{z}_{yi}$, and
$\mathbf{z}_{ya}$ will each contain $A$ columns (one per annotator) so in
order to compute the final prediction for each distribution, one could compute
the expectation across columns or compute the $\arg\max$ of each column and
compute the mode across the full set of guessed class integers.

The second case involves conducting iterative inference to find an annotator
embedding(s) when no annotator identifier is provided, i.e., the model is
given only the item feature vector and item label distribution. Specifically,
the iterative inference process proceeds as depicted in Algorithm 4. Note that
$\gamma$ is a decay factor to smooth and regularize the values of the
resulting embeddings.

##  6 Experiments

###  6.1 Data

| # annotators | # label | mean | # of
---|---|---|---|---
dataset | per item | classes | entropy | annotators
JQ1 [LHOA+16] | 10 | 5 | $0.746$ | 1185
JQ2 [LHOA+16] | 10 | 5 | $0.586$ | 1185
JQ3 [LHOA+16] | 10 | 12 | $0.993$ | 1185
Table 1: Summary of datasets on which we conduct our experiments. Each of
these contain 2,000 items.

We conducted our experiments on publicly available human annotated datasets.
Each dataset consists of 2,000 social media posts and employs a 50/25/25
percent for train/dev/test split.

Liu et al [LHOA+16] asked five annotators each from MTurk and FigureEight to
label work related tweets according to three questions and associated multiple
choice responses: point of view of the tweet (JQ1: _1st person_ , _2nd person_
, _3rd person_ , _unclear_ , or _not job related_), subject’s employment
status (JQ2: _employed_ , _not in labor force_ , _not employed_ , _unclear_ ,
and _not job-related_), and employment transition event (JQ3: _getting
hired/job seeking_ , _getting fired_ , _quitting a job_ , _losing job some
other way_ , _getting promoted/raised_ , _getting cut in hours_ , _complaining
about work_ , _offering support_ , _going to work_ , _coming home from work_ ,
_none of the above but job related_ , and _not job-related_).

We train and test on the following models. For natural language data, in order
to generate item feature vectors ($\mathbf{x}_{i}$) for LDL-NM, we used
sentence embeddings from [RG19] using the pretrained paraphrase-MiniLM-L6-v2
model.

PD

is a baseline supervised model with no unsupervised graphical model. It is The
supervised model (CNN) is a 1D convolutional neural network [Kim14], with
three convolution/max pool layers followed by a dropout and softmax layer,
implemented in TensorFlow [AAB+15]. It uses KL divergence for the cost
function. The model has a 20,000-word lexicon at the input layer, transforms
each word into a 100-dimension vector via the Glove 2B-tweet corpus [PSM14],
and admits text sequences of up to 1,000 tokens per data item.

FMM

is the baseline model, with the best-performing graph-based model from
Weerasooriya et al. [WLH20] used as a guiding model, in a manner analogous to
how the graph model introduced in this paper is used. The main difference
between their model and ours is that it only performs item label distribution
clustering; there are no annotator clusters.

PGM

is the proposed baseline supervised Bayesian model, with the graph model
introduced here for guidance. We set all of the Dirichlet parameters $\alpha$,
$\gamma$, and $\tau$ to $2$. We consider two different learning algorithms:
simulated annealing (with temperature schedule $T(t)=1/(t+1)$) and expectation
maximization (EM) with belief propagation.

LDL-NM

is the neural model described earlier. The item ($\mathbf{z}_{I}$) and
annotator ($\mathbf{z}_{A}$) embeddings were combined by setting the
$[\mathbf{a},\mathbf{b}]$ to be vector concatenation. We furthermore
regularized model parameters during training by applying drop-out, with a drop
probability of $p=0.5$, to the output activity of $\mathbf{z}_{P}$ and
$\mathbf{z}_{E}$. The Adam adaptive learning rate [KB14] was used to optimize
parameters by using gradients calculated over mini-batches of $256$ samples
for $200$ epochs. Model parameters were initialized from random orthogonal
matrices [SMG13].

For each of the the graphical models and LDL-NM we performed parameter search
on the number of item and annotator clusters (or, analogously, the hidden
layer sizes of the item and annotator encoders) $K,L\in\\{3,\ldots,20\\}$ and
report the results on the best performing model on development data. We
evaluate these models using two different metrics. To evaluate label
distribution prediction we report over the test set the mean KL divergence
between each gold standard label distribution and the predicted label
distribution $\mathrm{KL}(h_{\rm dist}(x)\|y)$. To evaluate single label
prediction, we report the accuracy measured over the test set.

Our experiments were conducted on; #1 - Local machine with Intel i6-7600k (4
cores) at 4.20GHz, 32GB RAM, and nVidia GeForce RTX 2070 Super 8GB VRAM and #2
Internal cluster with Intel(R) Xeon E7 v4, 264GB RAM, and GPU Tesla P4 8GB.
Our worst case scenario was machine #1 in our setup and dataset JQ3. The
runtime for a single pass of experiments on a single dataset for PD took 2
minutes, FMM took 2 hours, PGM (annealing) took 9 hours, PGM (BP) took 7
hours, and the LDL-NM took 1 hour.

###  6.2 Results

Table 3 shows the main results. We first note that all models outperform PD,
i.e., supervised learning with no clustering. For RQ1, both PGM models
slightly underperform FMM on both tasks and on all datasets. Since the PGM can
be seen as a finer-grained version of FMM (i.e., one that clusters in
annotator space in addition to item space), we suspect this is due to
overfitting that we have, thus far been, unable to control. For RQs 2 and 3,
LDL-NM outperforms all other models, including PD and all models with
graphical clustering. Additionally, the neural model has the advantage of
running as a single stage process, without the unsupervised clustering stage
that the graphical models require (and which is often much slower than
backpropagation).

We repeated experiments for LDL-NM to include error bars for KL-divergence and
accuracy, included in Table 3. In case of PD, FMM, PGM (annealing), and PGM
(BP), final supervised learning classification piece was repeated 100 times
(trained and evaluated) to calculate error bars. For LDL-NM, evaluation piece
was repeated 100 times by adding dropout layer for analysis.

Table 2: Experimental parameters of our unsuperivsed learning models. $K$ is the number of item classes, $L$ is the number of annotator classes, and $D_{KL}$ is the KL divergence when evaluated against empirical ground truth. *FMM model is clustered only on item classes. Dataset |  | FMM* | PGM (Annealing) | PGM (BP)
---|---|---|---|---
JQ1 | $D_{KL}$ | 0.193 | 0.651 | 0.523
| $L$ | - | 4 | 12
| $K$ | 14 | 4 | 10
JQ2 | $D_{KL}$ | 0.170 | 0.889 | 0.906
| $L$ | - | 5 | 12
| $K$ | 7 | 6 | 8
JQ3 | $D_{KL}$ | 0.269 | 1.389 | 1.190
| $L$ | - | 9 | 11
| $K$ | 35 | 14 | 12
Table 3: Experimental results for classification task. New methods (PGM, LDL-NM) using development set for each dataset. PD is a baseline where only a CNN classification is run and FMM is clustering only on the labels. The predictions are compared against the empirical ground truth. | KL-Divergence
---|---
Dataset | PD | FMM | PGM (Annealing) | PGM (BP) | LDL-NM
JQ1 | 1.092$\pm$0.004 | 0.460$\pm$0.001 | 0.652$\pm$0.005 | 0.538$\pm$0.010 | 0.408$\pm$0.004
JQ2 | 1.088$\pm$0.003 | 0.514$\pm$0.002 | 0.884$\pm$0.004 | 0.624$\pm$0.017 | 0.501$\pm$0.024
JQ3 | 1.462$\pm$0.004 | 0.888$\pm$0.001 | 1.201$\pm$0.005 | 0.951$\pm$0.016 | 0.864$\pm$0.001
| Accuracy
JQ1 | 0.494$\pm$0.001 | 0.892$\pm$0.000 | 0.730$\pm$0.000 | 0.727$\pm$0.007 | 0.915$\pm$0.001
JQ2 | 0.475$\pm$0.001 | 0.873$\pm$0.001 | 0.579$\pm$0.041 | 0.663$\pm$0.013 | 0.910$\pm$0.001
JQ3 | 0.284$\pm$0.020 | 0.880$\pm$0.001 | 0.290$\pm$0.002 | 0.250$\pm$0.007 | 0.923$\pm$0.0015

##  7 Qualitative Results for LDL-NM: t-SNE Visualization

We generated t-SNE visualizations for our experiments using the LDL-NM models,
plots show label class separation. Label classes for Jobs dataset by
[LHOA+16], point of view of the tweet (JQ1: _1st person_ , _2nd person_ , _3rd
person_ , _unclear_ , or _not job related_), subject’s employment status (JQ2:
_employed_ , _not in labor force_ , _not employed_ , _unclear_ , and _not job-
related_), and employment transition event (JQ3: _getting hired/job seeking_ ,
_getting fired_ , _quitting a job_ , _losing job some other way_ , _getting
promoted/raised_ , _getting cut in hours_ , _complaining about work_ ,
_offering support_ , _going to work_ , _coming home from work_ , _none of the
above but job related_ , and _not job-related_). Figures are included in
Figure 4.

Figure 4: t-SNE plot for training set from LDL-NM models. Each color
represents a label class. (Top Left) Plot for JQ1 dataset, which has five
label classes ($C$). (Top Right) Plot for JQ2 dataset, which also has five
label classes ($C$). (Bottom) Plot for JQ3 dataset, which has 12 label classes
($C$).

##  8 Discussion

##### Limitations.

We would have liked to test our model on more datasets, however, there are
very few multiclass, publicly available datasets that include information
about annotator assignments. This information is either discarded or withheld.
Without annotator assignments, it is impossible to perform clustering. We hope
that these results encourage more researchers to share this information
(though see caveats below).

In our graphical models we could have performed more extensive parameter
search on the Dirichlet hyperparameters. Although early in our research we
explored using the graphical model to predict soft clusters, we found that we
obtain better results with hard clusters. Nonetheless, a soft inference model
is probably a better for the purpose of comparing performance to the neural
model, because the neural model is effectively performing soft prediction in
it internal layers.

Although we directly compared our model’s performance to those of Weearsooriya
et al. [WLH20], who represent clustering in item label space only, we did not
perform head-to-head comparisons to Venanzi et al’s [VGK+14] model, which
represents clustering in annotator label space only. This is due in part to do
the data from their studies no longer being available. We nonetheless intend
to run their models our the data we do have in our next study.

##### Ethics review.

Before conducting the research described here, we consulted with our
institutional review board(s). They determined it did not constitute human
subjects research, primarily because the data was publicly available and
secondary. Beyond that, all authors have basic training on conducting human
subjects research from CITI333https://about.citiprogram.org/en/series/human-
subjects-research-hsr/. Moreover, we do not report on any of the details of
the data we used.

##### Potential societal impact.

Our involvement in label distribution learning came from a community based
participatory research group we belonged to on the use of AI technology in
vulnerable communities as a means of preserving in AI pipelines minority
perspectives that would otherwise be erased when annotator disagreement is
resolved, usually in favor of the plurality label, as is common practice
today. We believe these methods, coupled with demographic information on
annotators and reliable confidence estimates, can lead to annotated data that
is more representative of the true values within a society.

However, all statistical methods are double-edged swords. Used dishonestly,
these methods could be used to misrepresent social values and opinions.
Moreover, while these methods would be more informative with demographic
information on the annotators, that incurs on the privacy of annotators, a
group of workers who are often treated unfairly.

##  9 Conclusion

We introduced to two new models for improving the quality of annotator labels,
both from the perspective of the conventional problem of predicting the most
common label and the emerging problem of predicting the distribution of labels
provided. Our methods combine label distribution learning with clustering
jointly in the item and annotator label distribution spaces. Our first model
was an unsupervised-based graphical model that can be used as a black-box
guiding model for supervised learning by replacing the given small-sample
labels with ones designed to better capture the ground truth label
distributions, which are unobserved. The second model was a neural model
designed to capture internally the main features of the graphical model and
provide an all-in-one supervised model that can be reconfigured to infer
various aspects of the problem domain.

## References

  * [AAB+15] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015\.  Software available from tensorflow.org.
  * [AW14] Lora Aroyo and Chris Welty.  The Three Sides of CrowdTruth.  In Journal of Human Computation, volume 1, pages 31–34, 2014.
  * [CB09] Chris Callison-Burch.  Fast, cheap, and creative: Evaluating translation quality using amazon’s mechanical turk.  In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1 - Volume 1, EMNLP ’09, pages 286–295, Stroudsburg, PA, USA, 2009. Association for Computational Linguistics.
  * [Coh60] Jacob Cohen.  A coefficient of agreement for nominal scales.  Educational and psychological measurement, 20(1):37–46, 1960.
  * [Cov99] Thomas M Cover.  Elements of information theory.  John Wiley & Sons, 1999.
  * [DL10] Michael Denkowski and Alon Lavie.  Exploring normalization techniques for human judgments of machine translation adequacy collected using amazon mechanical turk.  In Proceedings of the NAACL HLT 2010 Workshop on Creating Speech and Language Data with Amazon’s Mechanical Turk, CSLDAMT ’10, pages 57–61, Stroudsburg, PA, USA, 2010. Association for Computational Linguistics.
  * [DS79] A. P. Dawid and A. M. Skene.  Maximum likelihood estimation of observer error-rates using the em algorithm.  28(1):20–28, 1979.
  * [Dut91] Jacques Dutka.  The early history of the factorial function.  Archive for history of exact sciences, 43(3):225–249, 1991.
  * [Gen16] Xin Geng.  Label Distribution Learning.  In IEEE Transactions on Knowledge and Data Engineering, volume 28, pages 1734–1748, 2016.
  * [GH15] Xin Geng and Peng Hou.  Pre-release prediction of crowd opinion on movies by label distribution learning.  In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15, 2015.
  * [GWX14] Xin Geng, Qin Wang, and Yu Xia.  Facial age estimation by adaptive label distribution learning.  In Proceedings - International Conference on Pattern Recognition, 2014.
  * [GXX+17] Bin-Bin Gao, Chao Xing, Chen-Wei Xie, Jianxin Wu, and Xin Geng.  Deep label distribution learning with label ambiguity.  volume 26, pages 2825–2838. IEEE Press, June 2017.
  * [HBKVH13] Dirk Hovy, Taylor Berg-Kirkpatrick, Ashish Vaswani, and Eduard Hovy.  Learning whom to trust with MACE.  In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1120–1130, Atlanta, Georgia, June 2013. Association for Computational Linguistics.
  * [Jay03] Edwin T Jaynes.  Probability theory: The logic of science.  Cambridge university press, 2003.
  * [KB14] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [KG12] Hyun-Chul Kim and Zoubin Ghahramani.  Bayesian classifier combination.  In Artificial Intelligence and Statistics, pages 619–627. PMLR, 2012.
  * [Kim14] Yoon Kim.  Convolutional neural networks for sentence classification.  In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1746–1751, Doha, Qatar, October 2014. Association for Computational Linguistics.
  * [LG18] Miaogen Ling and Xin Geng.  Soft video parsing by label distribution learning.  In Frontiers of Computer Science, pages 1331–1337, 2018.
  * [LHOA+16] Tong Liu, Christopher Homan, Cecilia Ovesdotter Alm, Megan Lytle, Ann Marie White, and Henry Kautz.  Understanding discourse on work and job-related well-being in public social media.  In Proceedings of the 54th Annual Meeting of the ACL, 2016.
  * [LVBH19] Tong Liu, Akash Venkatachalam, Pratik Sanjay Bongale, and Christopher M. Homan.  Learning to Predict Population-Level Label Distributions.  In Seventh AAAI Conference on Human Computation and Crowdsourcing, volume 7, pages 68–76, 2019.  A preliminary version appears in [LVSBH19].
  * [LVSBH19] Tong Liu, Akash Venkatachalam, Pratik Sanjay Bongale, and Christopher Homan.  Learning to predict population-level label distributions.  In Companion Proceedings of The 2019 World Wide Web Conference, WWW ’19, pages 1111–1120. ACM, 2019.
  * [Mal67] Bronislaw Malinowski.  The problem of meaning in primitive languages.  Meaning in Meaning, 1967.
  * [Met19] Cade Metz.  A.i. is learning from humans. many humans.  New York Times, August 16 2019.  https://www.nytimes.com/2019/08/16/technology/ai-humans.html, retrieved 5/21/2021.
  * [NJC19] Curtis G Northcutt, Lu Jiang, and Isaac L Chuang.  Confident learning: Estimating uncertainty in dataset labels.  arXiv preprint arXiv:1911.00068, 2019.
  * [PSM14] Jeffrey Pennington, Richard Socher, and Christopher D. Manning.  Glove: Global vectors for word representation.  In Empirical Methods in Natural Language Processing (EMNLP), pages 1532–1543, 2014.
  * [Res20] KBV Research.  Global Data Collection and Labeling Market By Data type By End User By Region, Industry Analysis and Forecast, 2020 - 2026.  2020\.
  * [RG17] Yi Ren and Xin Geng.  Sense beauty by label distribution learning.  In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, 2017.
  * [RG19] Nils Reimers and Iryna Gurevych.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019\.
  * [RY12] Vikas C Raykar and Shipeng Yu.  Eliminating spammers and ranking annotators for crowdsourced labeling tasks.  The Journal of Machine Learning Research, 13(1):491–518, 2012.
  * [RYZ+10] Vikas C Raykar, Shipeng Yu, Linda H Zhao, Gerardo Hermosillo Valadez, Charles Florin, Luca Bogoni, and Linda Moy.  Learning from crowds.  Journal of Machine Learning Research, 11(4), 2010.
  * [SDA+19] Amirreza Shirani, Franck Dernoncourt, Paul Asente, Nedim Lipka, Seokhwan Kim, Jose Echevarria, and Thamar Solorio.  Learning Emphasis Selection for Written Text in Visual Media from Crowd-Sourced Label Distributions.  pages 1167–1172, jul 2019.
  * [SFG+06] Jonathon Shlens, Greg D Field, Jeffrey L Gauthier, Matthew I Grivich, Dumitru Petrusca, Alexander Sher, Alan M Litke, and EJ Chichilnisky.  The structure of multi-neuron firing patterns in primate retina.  Journal of Neuroscience, 26(32):8254–8266, 2006.
  * [SMG13] Andrew M Saxe, James L McClelland, and Surya Ganguli.  Exact solutions to the nonlinear dynamics of learning in deep linear neural networks.  arXiv preprint arXiv:1312.6120, 2013.
  * [VGK+14] Matteo Venanzi, John Guiver, Gabriella Kazai, Pushmeet Kohli, and Milad Shokouhi.  Community-based bayesian aggregation models for crowdsourcing.  In Proceedings of the 23rd international conference on World wide web, pages 155–164, 2014.
  * [WG19] Jing Wang and Xin Geng.  Theoretical analysis of label distribution learning.  pages 5256–5263, 2019.
  * [WLH20] Tharindu Cyril Weerasooriya, Tong Liu, and Christopher M. Homan.  Neighborhood-based Pooling for Population-level Label Distribution Learning.  In Twenty Fourth European Conference on Artificial Intelligence, 2020.
  * [WWB+09] Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier Movellan, and Paul Ruvolo.  Whose vote should count more: Optimal integration of labels from labelers of unknown expertise.  Advances in neural information processing systems, 22:2035–2043, 2009.
  * [YWZT20] Xuebing Yang, Yajing Wu, Wensheng Zhang, and Wei Tang.  Label distribution learning with climate probability for ensemble forecasting.  Intelligent Data Analysis, 24(1):69–82, 2020.
  * [ZCX+20] Xue Qiang Zeng, Su Fen Chen, Run Xiang, Guo Zheng Li, and Xue Feng Fu.  Incomplete label distribution learning based on supervised neighborhood information.  International Journal of Machine Learning and Cybernetics, 11(1):111–121, 2020.
  * [ZHXM20] Heng Ru Zhang, Yu Ting Huang, Yuan Yuan Xu, and Fan Min.  COS-LDL: Label Distribution Learning by Cosine-Based Distance-Mapping Correlation.  IEEE Access, 8:63961–63970, 2020.
  * [ZJL18] Xiang Zheng, Xiuyi Jia, and Weiwei Li.  Label Distribution Learning by Exploiting Label Correlations.  In The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), number 1, pages 3310–3317, 2018.

##  Appendix A Deriving the Kullback-Leibler Divergence Terms for the LDL-NM

If we were to perform an experiment, measuring a discrete variable, and take
$N$ measurements, we would obtain a histogram $c=\\{c_{i}\\}$ where
$N=\sum_{i}c_{i}$ (we measures the number of times that we see each possible
value that the discrete variable could take on). If $N\rightarrow\infty$ (the
experiment is infinitely long), then the normalized histogram counts $c_{i}/N$
approach $p_{i}=\frac{c_{i}}{N}$ (a target distribution). If we had a
distribution $q$, we seek to answer the question: What is the probability of
observing the histogram counts $c$ if $q$ generated the observations?444For
$C$ distinct, discrete values (or classes),
$p=\mathbf{p}=\\{p_{1},p_{2},...,p_{C}\\}$ and
$q=\mathbf{q}=\\{q_{1},q_{2},...,q_{C}\\}$.

We start from the defnition of the multinomial likelihood [Cov99, SFG+06],
which expresses the probability of observing a histogram $c=\\{c_{i}\\}$ given
that model $q=\\{q_{i}\\}$ is true:

$\displaystyle\mathcal{F}(c|q)=\frac{N!}{\Pi_{i}c_{i}!}\Pi_{i}(q_{i})^{c_{i}}$
(13)

where $\frac{N!}{\Pi_{i}c_{i}!}$ is the normalization constant that counts the
number of combinations that could give rise to histogram $c$
($N=\sum_{i}c_{i}$ is the total number of measurements). To compute the joint
probability of all measurements under the multinomial likelihood, we
ultimately multiply the independent observations (of the histogram) together
thus resulting in the geometric mean of the multinomial likelihood
$\mathcal{F}(c|q)^{\frac{1}{N}}$ (which is an invariant likelihood across
histogram counts). We then take the natural logarithm of the average
likelihood and plug in Equation 13 to obtain:

$\displaystyle\log\mathcal{F}(c|q)^{\frac{1}{N}}$
$\displaystyle=\frac{1}{N}\log\bigg{(}\frac{N!}{\Pi_{i}c_{i}!}\Pi_{i}(q_{i})^{c_{i}}\bigg{)}$
(14) $\displaystyle=\frac{1}{N}\log N!-\frac{1}{N}\sum_{i}\log
c_{i}!+\sum_{i}\frac{c_{i}}{N}\log q_{i}\mbox{.}$ (15)

To remove the factorial in the above expression, we utilize Stirling’s
numerical approximation for factorials, i.e., $\log N!\simeq N\log N-N$, an
approximation that becomes quite good for reasonably large $N$ [Dut91].
Replacing all of the $\log N!$ in Equation 15 with this approximation results
in:

$\displaystyle\log\mathcal{F}(c|q)^{\frac{1}{N}}$
$\displaystyle=\frac{1}{N}\big{(}N\log N-N)-\frac{1}{N}\sum_{i}(c_{i}\log
c_{i}-c_{i})+\sum_{i}\frac{c_{i}}{N}\log q_{i}$ (16) $\displaystyle=\log
N-\sum_{i}\frac{c_{i}}{N}\log c_{i}+\sum_{i}\frac{c_{i}}{N}\log q_{i}$ (17)
$\displaystyle=\sum_{i}\frac{c_{i}}{N}\log N-\sum_{i}\frac{c_{i}}{N}\log
c_{i}+\sum_{i}\frac{c_{i}}{N}\log q_{i}$ (18)

where the bottom expression is obtained by noting that the coefficient of $1$
that multiplies the first term $\log N$ (in Equation 17) can be re-written as
$\frac{N}{N}=\frac{1}{N}\sum_{i}c_{i}=\sum_{i}\frac{c_{i}}{N}$. The derivation
then continues with the applications of the rules of logarithms:

$\displaystyle=\sum_{i}\Big{(}\frac{c_{i}}{N}\log N-\frac{c_{i}}{N}\log
c_{i}\Big{)}+\sum_{i}\frac{c_{i}}{N}\log q_{i}$ (19)
$\displaystyle=\sum_{i}\Big{(}-\frac{c_{i}}{N}\big{(}-\log N+\log
c_{i}\big{)}\Big{)}+\sum_{i}\frac{c_{i}}{N}\log q_{i}$ (20)
$\displaystyle=-\sum_{i}\Big{(}\frac{c_{i}}{N}\big{(}\log\frac{1}{N}+\log
c_{i}\big{)}\Big{)}+\sum_{i}\frac{c_{i}}{N}\log q_{i}$ (21)
$\displaystyle=-\sum_{i}\frac{c_{i}}{N}\log\frac{c_{i}}{N}+\sum_{i}\frac{c_{i}}{N}\log
q_{i}\mbox{.}$ (22)

Note that, as described at the start of this section, when
$N\rightarrow\infty$ then $p_{i}\equiv\frac{c_{i}}{N}$, we finally arrive at
the (negative) Kullback-Leibler (KL) divergence:

$\displaystyle=-\sum_{i}p_{i}\log p_{i}+\sum_{i}p_{i}\log
q_{i}=-\text{KL}(p||q)\mbox{.}$ (23)

This result implies that KL divergence in our case is the negative logarithm
of the (geometric) mean of the multinomial likelihood (the first term of
Equation 23 is also known as the entropy of the target distribution $p$
[Jay03]). Since the LDL-NM model proposed in this paper already produces the
values $q_{i}$ for each $i$th dimension of the count histogram and we already
have an estimated target $p_{i}$ from the annotator and/or item distributions
(which are normalized to lie in the range of $[0,1]$ in the pre-processing
stage, thus mimicking the required $p_{i}\equiv\frac{c_{i}}{N}$), we may
directly utilize the negative of the result in Equation 23. Note that to
recover the exact form of the KL terms presented in the main paper, one must,
for $C$ classes, set either $\mathbf{p}=\mathbf{y}_{I}$ or
$\mathbf{p}=\mathbf{y}_{A}$ and either $\mathbf{q}=\mathbf{z}_{yI}$ or
$\mathbf{q}=\mathbf{z}_{yA}$.