capbtabboxtable[][] figuret

# Neural Expectation Maximization

Klaus Greff
IDSIA
<EMAIL_ADDRESS>
&Sjoerd van Steenkiste††footnotemark:
IDSIA
<EMAIL_ADDRESS>
&Jürgen Schmidhuber
IDSIA
<EMAIL_ADDRESS>
Both authors contributed equally to this work.

###### Abstract

Many real world tasks such as reasoning and physical interaction require
identification and manipulation of conceptual entities. A first step towards
solving these tasks is the automated discovery of distributed symbol-like
representations. In this paper, we explicitly formalize this problem as
inference in a spatial mixture model where each component is parametrized by a
neural network. Based on the Expectation Maximization framework we then derive
a differentiable clustering method that simultaneously learns how to group and
represent individual entities. We evaluate our method on the (sequential)
perceptual grouping task and find that it is able to accurately recover the
constituent objects. We demonstrate that the learned representations are
useful for next-step prediction.

##  1 Introduction

Learning useful representations is an important aspect of unsupervised
learning, and one of the main open problems in machine learning. It has been
argued that such representations should be distributed [13, 37] and
disentangled [1, 31, 3]. The latter has recently received an increasing amount
of attention, producing representations that can disentangle features like
rotation and lighting [4, 12].

So far, these methods have mostly focused on the single object case whereas,
for real world tasks such as reasoning and physical interaction, it is often
necessary to identify and manipulate multiple entities and their
relationships. In current systems this is difficult, since superimposing
multiple distributed and disentangled representations can lead to ambiguities.
This is known as the Binding Problem [21, 37, 13] and has been extensively
discussed in neuroscience [33]. One solution to this problem involves learning
a separate representation for each object. In order to allow these
representations to be processed identically they must be described in terms of
the same (disentangled) features. This would then avoid the binding problem,
and facilitate a wide range of tasks that require knowledge about individual
objects. This solution requires a process known as _perceptual grouping_ :
dynamically splitting (segmenting) each input into its constituent conceptual
entities.

In this work, we tackle this problem of learning how to group and efficiently
represent individual entities, in an unsupervised manner, based solely on the
statistical structure of the data. Our work follows a similar approach as the
recently proposed Tagger [7] and aims to further develop the understanding, as
well as build a theoretical framework, for the problem of _symbol-like
representation learning_. We formalize this problem as inference in a spatial
mixture model where each component is parametrized by a neural network. Based
on the Expectation Maximization framework we then derive a differentiable
clustering method, which we call _Neural Expectation Maximization_ (N-EM). It
can be trained in an unsupervised manner to perform perceptual grouping in
order to learn an efficient representation for each group, and naturally
extends to sequential data.

##  2 Neural Expectation Maximization

The goal of training a system that produces separate representations for the
individual conceptual entities contained in a given input (here: image)
depends on what notion of _entity_ we use. Since we are interested in the case
of unsupervised learning, this notion _can only_ rely on statistical
properties of the data. We therefore adopt the intuitive notion of a
conceptual entity as being a common cause (the object) for multiple
observations (the pixels that depict the object). This common cause induces a
dependency-structure among the affected pixels, while the pixels that
correspond to different entities remain (largely) independent. Intuitively
this means that knowledge about some pixels of an object helps in predicting
its remainder, whereas it does not improve the predictions for pixels of other
objects. This is especially obvious for sequential data, where pixels
belonging to a certain object share a common fate (e.g. move in the same
direction), which makes this setting particularly appealing.

We are interested in representing each entity (object) $k$ with some vector
$\bm{\theta}_{k}$ that captures all the structure of the affected pixels, but
carries no information about the remainder of the image. This modularity is a
powerful invariant, since it allows the same representation to be reused in
different contexts, which enables generalization to novel combinations of
known objects. Further, having all possible objects represented in the same
format makes it easier to work with these representations. Finally, having a
separate $\bm{\theta}_{k}$ for each object (as opposed to for the entire
image) allows $\bm{\theta}_{k}$ to be distributed and disentangled without
suffering from the binding problem.

We treat each image as a composition of $K$ objects, where each pixel is
determined by exactly one object. Which objects are present, as well as the
corresponding assignment of pixels, varies from input to input. Assuming that
we have access to the family of distributions $P(\bm{x}|\bm{\theta}_{k})$ that
corresponds to an object level representation as described above, we can model
each image as a mixture model. Then Expectation Maximization (EM) can be used
to simultaneously compute a Maximum Likelihood Estimate (MLE) for the
individual $\bm{\theta}_{k}$-s and the grouping that we are interested in.

The central problem we consider in this work is therefore how to learn such a
$P(\bm{x}|\bm{\theta}_{k})$ in a completely unsupervised fashion. We
accomplish this by parametrizing this family of distributions by a
differentiable function $f_{\phi}(\bm{\theta})$ (a neural network with weights
$\phi$). We show that in that case, the corresponding EM procedure becomes
fully differentiable, which allows us to backpropagate an appropriate outer
loss into the weights of the neural network. In the remainder of this section
we formalize and derive this method which we call _Neural Expectation
Maximization_ (N-EM).

###  2.1 Parametrized Spatial Mixture Model

We model each image $\bm{x}\in\mathbb{R}^{D}$ as a spatial mixture of $K$
components parametrized by vectors
$\bm{\theta}_{1},\dots,\bm{\theta}_{K}\in\mathbb{R}^{M}$. A differentiable
non-linear function $f_{\phi}$ (a neural network) is used to transform these
representations $\bm{\theta}_{k}$ into parameters
$\psi_{i,k}=f_{\phi}(\bm{\theta}_{k})_{i}$ for separate pixel-wise
distributions. These distributions are typically Bernoulli or Gaussian, in
which case $\psi_{i,k}$ would be a single probability or a mean and variance
respectively. This parametrization assumes that given the representation, the
pixels are independent but _not_ identically distributed (unlike in standard
mixture models). A set of binary latent variables
$\bm{\mathcal{Z}}\in[0,1]^{D\times K}$ encodes the unknown true pixel
assignments, such that $z_{i,k}=1$ iff pixel $i$ was generated by component
$k$, and $\sum_{k}z_{i,k}=1$. A graphical representation of this model can be
seen in Figure 1, where $\bm{\pi}=(\pi_{1},\dots\pi_{K})$ are the mixing
coefficients (or prior for $\bm{z}$). The full likelihood for $\bm{x}$ given
$\bm{\theta}=(\bm{\theta}_{1},\dots,\bm{\theta}_{K})$ is given by:

$P(\bm{x}|\bm{\theta})=\prod_{i=1}^{D}\sum_{\bm{z}_{i}}P(x_{i},\bm{z}_{i}|\bm{\psi}_{i})=\prod_{i=1}^{D}\sum_{k=1}^{K}\underbrace{P(z_{i,k}=1)}_{\pi_{k}}P(x_{i}|\psi_{i,k},z_{i,k}=1).$
(1)

Figure 1: left: The probabilistic graphical model that underlies N-EM. right:
Illustration of the computations for two steps of N-EM.

###  2.2 Expectation Maximization

Directly optimizing $\log P(\bm{x}|\bm{\psi})$ with respect to $\bm{\theta}$
is difficult due to marginalization over $\mathbf{z}$, while for many
distributions optimizing $\log P(\bm{x},\mathbf{z}|\bm{\psi})$ is much easier.
Expectation Maximization (EM; [6]) takes advantage of this and instead
optimizes a lower bound given by the expected log likelihood:

$\mathcal{Q}(\bm{\theta},\bm{\theta}^{\text{old}})=\sum_{\mathbf{z}}P(\mathbf{z}|\bm{x},\bm{\psi}^{\text{old}})\log
P(\bm{x},\mathbf{z}|\bm{\psi}).$ (2)

Iterative optimization of this bound alternates between two steps: in the _E-
step_ we compute a new estimate of the posterior probability distribution over
the latent variables given $\bm{\theta}^{\text{old}}$ from the previous
iteration, yielding a new soft-assignment of the pixels to the components
(clusters):

$\gamma_{i,k}:=P(z_{i,k}=1|x_{i},\psi_{i}^{\text{old}}).$ (3)

In the M-step we then aim to find the configuration of $\bm{\theta}$ that
would maximize the expected log-likelihood using the posteriors computed in
the E-step. Due to the non-linearity of $f_{\phi}$ there exists no analytical
solution to
$\operatorname*{arg\,max}_{\bm{\theta}}\mathcal{Q}(\bm{\theta},\bm{\theta}^{\text{old}})$.
However, since $f_{\phi}$ is differentiable, we can improve
$\mathcal{Q}(\bm{\theta},\bm{\theta}^{\text{old}})$ by taking a gradient
ascent step:111Here we assume that $P(x_{i}|z_{i,k}=1,\psi_{i,k})$ is given by
$\mathcal{N}(x_{i};\mu=\psi_{i,k},\sigma^{2})$ for some fixed $\sigma^{2}$,
yet a similar update arises for many typical parametrizations of pixel
distributions.

$\bm{\theta}^{\text{new}}=\bm{\theta}^{\text{old}}+\eta\frac{\partial\mathcal{Q}}{\partial\bm{\theta}}\qquad\qquad\text{
where
}\qquad\frac{\partial\mathcal{Q}}{\partial\bm{\theta}_{k}}\propto\sum_{i=1}^{D}\gamma_{i,k}(\psi_{i,k}-x_{i})\frac{\partial\psi_{i,k}}{\partial\bm{\theta}_{k}}.$
(4)

The resulting algorithm belongs to the class of _generalized EM algorithms_
and is guaranteed (for a sufficiently small learning rate $\eta$) to converge
to a (local) optimum of the data log likelihood [42].

###  2.3 Unrolling

In our model the information about statistical regularities required for
clustering the pixels into objects is encoded in the neural network $f_{\phi}$
with weights $\phi$. So far we have considered $f_{\phi}$ to be fixed and have
shown how we can compute an MLE for $\bm{\theta}$ alongside the appropriate
clustering. We now observe that by unrolling the iterations of the presented
generalized EM, we obtain an end-to-end differentiable clustering procedure
based on the statistical model implemented by $f_{\phi}$. We can therefore use
(stochastic) gradient descent and fit the statistical model to capture the
regularities corresponding to objects for a given dataset. This is implemented
by back-propagating an appropriate loss (see Section 2.4) through “time”
(BPTT; [39, 41]) into the weights $\phi$. We refer to this trainable procedure
as _Neural Expectation Maximization_ (N-EM), an overview of which can be seen
in Figure 1.

Figure 2: RNN-EM Illustration. Note the changed encoder and recurrence
compared to Figure 1.

Upon inspection of the structure of N-EM we find that it resembles $K$ copies
of a recurrent neural network with hidden states $\bm{\theta}_{k}$ that, at
each timestep, receive $\bm{\gamma}_{k}\odot(\bm{\psi}_{k}-\bm{x})$ as their
input. Each copy generates a new $\bm{\psi}_{k}$, which is then used by the
E-step to re-estimate the soft-assignments $\bm{\gamma}$. In order to
accurately mimic the M-Step (4) with an RNN, we must impose several
restrictions on its weights and structure: the “encoder” must correspond to
the Jacobian $\partial\bm{\psi}_{k}/\partial\bm{\theta}_{k}$, and the
recurrent update must linearly combine the output of the encoder with
$\bm{\theta}_{k}$ from the previous timestep. Instead, we introduce a new
algorithm named RNN-EM, when substituting that part of the computational graph
of N-EM with an actual RNN (without imposing any restrictions). Although RNN-
EM can no longer guarantee convergence of the data log likelihood, its
recurrent weights increase the flexibility of the clustering procedure.
Moreover, by using a fully parametrized recurrent weight matrix RNN-EM
naturally extends to sequential data. Figure 2 presents the computational
graph of a single RNN-EM timestep.

###  2.4 Training Objective

N-EM is a differentiable clustering procedure, whose outcome relies on the
statistical model $f_{\phi}$. We are interested in a particular unsupervised
clustering that corresponds to grouping entities based on the statistical
regularities in the data. To train our system, we therefore require a loss
function that teaches $f_{\phi}$ to map from representations $\bm{\theta}$ to
parameters $\bm{\psi}$ that correspond to pixelwise distributions for such
objects. We accomplish this with a two-term loss function that guides each of
the $K$ networks to model the structure of a single object independently of
any other information in the image:

$L(\bm{x})=-\sum_{i=1}^{D}\sum_{k=1}^{K}\underbrace{\gamma_{i,k}\log
P(x_{i},z_{i,k}|\psi_{i,k})}_{\text{intra-cluster
loss}}-\underbrace{(1-\gamma_{i,k})D_{KL}[P(x_{i})||P(x_{i}|\psi_{i,k},z_{i,k})]}_{\text{inter-
cluster loss}}.$ (5)

The intra-cluster loss corresponds to the same expected data log-likelihood
$\mathcal{Q}$ as is optimized by N-EM. It is analogous to a standard
reconstruction loss used for training autoencoders, weighted by the cluster
assignment. Similar to autoencoders, this objective is prone to trivial
solutions in case of overcapacity, which prevent the network from modelling
the statistical regularities that we are interested in. Standard techniques
can be used to overcome this problem, such as making $\bm{\theta}$ a
bottleneck or using a noisy version of $\bm{x}$ to compute the inputs to the
network. Furthermore, when RNN-EM is used on sequential data we can use a
next-step prediction loss.

Weighing the loss pixelwise is crucial, since it allows each network to
specialize its predictions to an individual object. However, it also
introduces a problem: the loss for out-of-cluster pixels ($\gamma_{i,k}=0$)
vanishes. This leaves the network free to predict anything and does not yield
specialized representations. Therefore, we add a second term (inter-cluster
loss) which penalizes the KL divergence between out-of-cluster predictions and
the pixelwise prior of the data. Intuitively this tells each representation
$\bm{\theta}_{k}$ to contain no information regarding non-assigned pixels
$x_{i}$: $P(x_{i}|\psi_{i,k},z_{i,k})=P(x_{i})$.

A disadvantage of the interaction between $\bm{\gamma}$ and $\bm{\psi}$ in (5)
is that it may yield conflicting gradients. For any $\bm{\theta}_{k}$ the loss
for a given pixel $i$ can be reduced by better predicting $x_{i}$, or by
decreasing $\gamma_{i,k}$ (i.e. taking less responsibility) which is (due to
the E-step) realized by being worse at predicting $x_{i}$. A practical
solution to this problem is obtained by stopping the $\bm{\gamma}$ gradients,
i.e. by setting $\partial L/\partial\bm{\gamma}=0$ during backpropagation.

##  3 Related work

The method most closely related to our approach is Tagger [7], which similarly
learns perceptual grouping in an unsupervised fashion using $K$ copies of a
neural network that work together by reconstructing different parts of the
input. Unlike in case of N-EM, these copies additionally learn to output the
grouping, which gives Tagger more direct control over the segmentation and
supports its use on complex texture segmentation tasks. Our work maintains a
close connection to EM and relies on the posterior inference of the E-Step as
a grouping mechanism. This facilitates theoretical analysis and simplifies the
task for the resulting networks, which we find can be markedly smaller than in
Tagger. Furthermore, Tagger does not include any recurrent connections on the
level of the hidden states, precluding it from next step prediction on
sequential tasks.222RTagger [15]: a recurrent extension of Tagger that does
support sequential data was developed concurrent to this work.

The Binding problem was first considered in the context of Neuroscience [21,
37] and has sparked some early work in oscillatory neural networks that use
synchronization as a grouping mechanism [36, 38, 24]. Later, complex valued
activations have been used to replace the explicit simulation of oscillation
[25, 26]. By virtue of being general computers, any RNN can in principle learn
a suitable mechanism. In practice however it seems hard to learn, and adding a
suitable mechanism like competition [40], fast weights [29], or perceptual
grouping as in N-EM seems necessary.

Unsupervised Segmentation has been studied in several different contexts [30],
from random vectors [14] over texture segmentation [10] to images [18, 16].
Early work in unsupervised video segmentation [17] used generalized
Expectation Maximization (EM) to infer how to split frames of moving sprites.
More recently optical flow has been used to train convolutional networks to do
figure/ground segmentation [23, 34]. A related line of work under the term of
multi-causal modelling [28] has formalized perceptual grouping as inference in
a generative compositional model of images. Masked RBMs [20] for example
extend Restricted Boltzmann Machines with a latent mask inferred through
Block-Gibbs sampling.

Gradient backpropagation through inference updates has previously been
addressed in the context of sparse coding with (Fast) Iterative
Shrinkage/Tresholding Algorithms ((F)ISTA; [5, 27, 2]). Here the unrolled
graph of a fixed number of ISTA iterations is replaced by a recurrent neural
network that parametrizes the gradient computations and is trained to predict
the sparse codes directly [9]. We derive RNN-EM from N-EM in a similar fashion
and likewise obtain a trainable procedure that has the structure of iterative
pursuit built into the architecture, while leaving tunable degrees of freedom
that can improve their modeling capabilities [32]. An alternative to further
empower the network by untying its weights across iterations [11] was not
considered for flexibility reasons.

##  4 Experiments

We evaluate our approach on a perceptual grouping task for generated static
images and video. By composing images out of simple shapes we have control
over the statistical structure of the data, as well as access to the ground-
truth clustering. This allows us to verify that the proposed method indeed
recovers the intended grouping and learns representations corresponding to
these objects. In particular we are interested in studying the role of next-
step prediction as a unsupervised objective for perceptual grouping, the
effect of the hyperparameter $K$, and the usefulness of the learned
representations.

In all experiments we train the networks using ADAM [19] with default
parameters, a batch size of 64 and $50\,000$ train + $10\,000$ validation +
$10\,000$ test inputs. Consistent with earlier work [8, 7], we evaluate the
quality of the learned groupings with respect to the ground truth while
ignoring the background and overlap regions. This comparison is done using the
Adjusted Mutual Information (AMI; [35]) score, which provides a measure of
clustering similarity between 0 (random) and 1 (perfect match). We use early
stopping when the validation loss has not improved for 10 epochs.333Note that
we do not stop on the AMI score as this is not part of our objective function
and only measured to evaluate the performance _after_ training. A detailed
overview of the experimental setup can be found in Appendix A. All reported
results are averages computed over five runs.444Code to reproduce all
experiments is available at https://github.com/sjoerdvansteenkiste/Neural-EM

Figure 3: Groupings by RNN-EM (bottom row), N-EM (middle row) for six input
images (top row). Both methods recover the individual shapes accurately when
they are separated (a, b, f), even when confronted with the same shape (b).
RNN-EM is able to handle most occlusion (c, d) but sometimes fails (e). The
exact assignments are permutation invariant and depend on $\bm{\gamma}$
initialization; compare (a) and (f).

###  4.1 Static Shapes

To validate that our approach yields the intended behavior we consider a
simple perceptual grouping task that involves grouping three randomly chosen
regular shapes ($\triangle\raisebox{1.99997pt}{$\bigtriangledown$}\square$)
located in random positions of $28\times 28$ binary images [26]. This simple
setup serves as a test-bed for comparing N-EM and RNN-EM, before moving on to
more complex scenarios.

We implement $f_{\phi}$ by means of a single layer fully connected neural
network with a sigmoid output $\psi_{i,k}$ for each pixel that corresponds to
the mean of a Bernoulli distribution. The representation $\bm{\theta}_{k}$ is
a real-valued 250-dimensional vector squashed to the $(0,1)$ range by a
sigmoid function before being fed into the network. Similarly for RNN-EM we
use a recurrent neural network with 250 sigmoidal hidden units and an
equivalent output layer. Both networks are trained with $K=3$ and unrolled for
15 EM steps.

As shown in Figure 3, we observe that both approaches are able to recover the
individual shapes as long as they are separated, even when confronted with
identical shapes. N-EM performs worse if the image contains occlusion, and we
find that RNN-EM is in general more stable and produces considerably better
groupings. This observation is in line with findings for Sparse Coding [9].
Similarly we conclude that the tunable degrees of freedom in RNN-EM help
speed-up the optimization process resulting in a more powerful approach that
requires fewer iterations. The benefit is reflected in the large score
difference between the two: $0.826\pm 0.005$ AMI compared to $0.475\pm 0.043$
AMI for N-EM. In comparison, Tagger achieves an AMI score of $0.79\pm 0.034$
(and $0.97\pm 0.009$ with layernorm), while using about twenty times more
parameters [7].

###  4.2 Flying Shapes

We consider a sequential extension of the _static shapes_ dataset in which the
shapes ($\triangle\raisebox{1.99997pt}{$\bigtriangledown$}\square$) are
floating along random trajectories and bounce off walls. An example sequence
with 5 shapes can be seen in the bottom row of Figure 4. We use a
convolutional encoder and decoder inspired by the discriminator and generator
networks of infoGAN [4], with a recurrent neural network of 100 sigmoidal
units (for details see Section A.2). At each timestep $t$ the network receives
$\bm{\gamma}_{k}(\bm{\psi}_{k}^{(t-1)}-\bm{\tilde{x}}^{(t)})$ as input, where
$\bm{\tilde{x}}^{(t)}$ is the current frame corrupted with additional bitflip
noise ($p=0.2$). The next-step prediction objective is implemented by
replacing $\bm{x}$ with $\bm{x}^{(t+1)}$ in (5), and is evaluated at each
time-step.

Figure 4: A sequence of 5 shapes flying along random trajectories (bottom
row). The next-step prediction of each copy of the network (rows 2 to 5) and
the soft-assignment of the pixels to each of the copies (top row). Observe
that the network learns to separate the individual shapes as a means to
efficiently solve next-step prediction. Even when many of the shapes are
overlapping, as can be seen in time-steps 18-20, the network is still able to
disentangle the individual shapes from the clutter.

Table 1 summarizes the results on flying shapes, and an example of a sequence
with 5 shapes when using $K=5$ can be seen in Figure 4. For 3 shapes we
observe that the produced groupings are close to perfect (AMI: $0.970\pm
0.005$). Even in the very cluttered case of 5 shapes the network is able to
separate the individual objects in almost all cases (AMI: $0.878\pm 0.003$).

These results demonstrate the adequacy of the next step prediction task for
perceptual grouping. However, we find that the converse also holds: the
corresponding representations are useful for the prediction task. In Figure 6
we compare the next-step prediction error of RNN-EM with $K=1$ (which reduces
to a recurrent autoencoder that receives the difference between its previous
prediction and the current frame as input) to RNN-EM with $K=5$ on this task.
To evaluate RNN-EM on next-step prediction we computed its loss using
$P(x_{i}|\bm{\psi}_{i})=P(x_{i}|\max_{k}\psi_{i,k})$ as opposed to
$P(x_{i}|\bm{\psi}_{i})=\sum_{k}\gamma_{i,k}P(x_{i}|\psi_{i,k})$ to avoid
including information from the next timestep. The reported BCE loss for RNN-EM
is therefore an _upperbound_ to the true BCE loss. From the figure we observe
that RNN-EM produces significantly lower errors, especially when the number of
objects increases.

Finally, in Table 1 we also provide insight about the impact of choosing the
hyper-parameter $K$, which is unknown for many real-world scenarios.
Surprisingly we observe that training with too large $K$ is in fact
favourable, and that the network learns to leave the excess groups empty. When
training with too few components we find that the network still learns about
the individual shapes and we observe only a slight drop in score when
correctly setting the number of components at test time. We conclude that RNN-
EM is robust towards different choices of $K$, and specifically that choosing
$K$ to be too high is not detrimental.

[.41] [.55]

Figure 5: Binomial Cross Entropy Error obtained by RNN-EM and a recurrent autoencoder (RNN-EM with $K=1$) on the denoising and next-step prediction task. RNN-EM produces significantly lower BCE across different numbers of objects. Figure 6: Average AMI score (blue line) measured for RNN-EM (trained for 20 steps) across the flying MNIST test-set and corresponding quartiles (shaded areas), computed for each of 50 time-steps. The learned grouping dynamics generalize to longer sequences and even further improve the AMI score. Table 1: AMI scores obtained by RNN-EM on _flying shapes_ when varying the number of objects and number of components $K$, during training and at test time. Train |  | Test |  | Test Generalization
---|---|---|---|---
# obj. | K | AMI |  | # obj. | K | AMI |  | # obj. | K | AMI
3 | 3 | 0.969 $\pm$ 0.006 |  | 3 | 3 | 0.970 $\pm$ 0.005 |  | 3 | 5 | 0.972 $\pm$ 0.007
3 | 5 | 0.997 $\pm$ 0.001 |  | 3 | 5 | 0.997 $\pm$ 0.002 |  | 3 | 3 | 0.914 $\pm$ 0.015
5 | 3 | 0.614 $\pm$ 0.003 |  | 5 | 3 | 0.614 $\pm$ 0.003 |  | 3 | 3 | 0.886 $\pm$ 0.010
5 | 5 | 0.878 $\pm$ 0.003 |  | 5 | 5 | 0.878 $\pm$ 0.003 |  | 3 | 5 | 0.981 $\pm$ 0.003

###  4.3 Flying MNIST

In order to incorporate greater variability among the objects we consider a
sequential extension of MNIST. Here each sequence consists of gray-scale
$24\times 24$ images containing two down-sampled MNIST digits that start in
random positions and float along randomly sampled trajectories within the
image for $T$ timesteps. An example sequence can be seen in the bottom row of
Figure 7.

We deploy a slightly deeper version of the architecture used in flying shapes.
Its details can be found in Appendix A.3. Since the images are gray-scale we
now use a Gaussian distribution for each pixel with fixed $\sigma^{2}=0.25$
and $\mu=\psi_{i,k}$ as computed by each copy of the network. The training
procedure is identical to flying shapes except that we replace bitflip noise
with masked uniform noise: we first sample a binary mask from a multi-variate
Bernoulli distribution with $p=0.2$ and then use this mask to interpolate
between the original image and samples from a Uniform distribution between the
minimum and maximum values of the data (0,1).

We train with $K=2$ and $T=20$ on flying MNIST having two digits and obtain an
AMI score of $0.819\pm 0.022$ on the test set, measured across 5 runs.

In early experiments we observed that, given the large variability among the
$50\,000$ unique digits, we can boost the model performance by training in
stages using $20,500,50\,000$ digits. Here we exploit the generalization
capabilities of RNN-EM to quickly transfer knowledge from a less varying set
of MNIST digits to unseen variations. We used the same hyper-parameter
configuration as before and obtain an AMI score of $0.917\pm 0.005$ on the
test set, measured across 5 runs.

Figure 7: A sequence of 3 MNIST digits flying across random trajectories in
the image (bottom row). The next-step prediction of each copy of the network
(rows 2 to 4) and the soft-assignment of the pixels to each of the copies (top
row). Although the network was trained (stage-wise) on sequences with two
digits, it is accurately able to separate three digits.

We study the generalization capabilities and robustness of these trained RNN-
EM networks by means of three experiments. In the first experiment we evaluate
them on flying MNIST having three digits (one extra) and likewise set $K=3$.
Even without further training we are able to maintain a high AMI score of
$0.729\pm 0.019$ (stage-wise: $0.838\pm 0.008$) on the test-set. A test
example can be seen in Figure 7. In the second experiment we are interested in
whether the grouping mechanism that has been learned can be transferred to
static images. We find that using 50 RNN-EM steps we are able to transfer a
large part of the learned grouping dynamics and obtain an AMI score of
$0.619\pm 0.023$ (stage-wise: $0.772\pm 0.008$) for two static digits. As a
final experiment we evaluate the directly trained network on the same dataset
for a larger number of timesteps. Figure 6 displays the average AMI score
across the test set as well as the range of the upper and lower quartile for
each timestep.

The results of these experiments confirm our earlier observations for flying
shapes, in that the learned grouping dynamics are robust and generalize across
a wide range of variations. Moreover we find that the AMI score further
improves at test time when increasing the sequence length.

##  5 Discussion

The experimental results indicate that the proposed Neural Expectation
Maximization framework can indeed learn how to group pixels according to
constituent objects. In doing so the network learns a useful and localized
representation for individual entities, which encodes only the information
relevant to it. Each entity is represented separately in the same space, which
avoids the binding problem and makes the representations usable as efficient
symbols for arbitrary entities in the dataset. We believe that this is useful
for reasoning in particular, and a potentially wide range of other tasks that
depend on interaction between multiple entities. Empirically we find that the
learned representations are already beneficial in next-step prediction with
multiple objects, a task in which overlapping objects are problematic for
standard approaches, but can be handled efficiently when learning a separate
representation for each object.

As is typical in clustering methods, in N-EM there is no preferred assignment
of objects to groups and so the grouping numbering is arbitrary and only
depends on initialization. This property renders our results permutation
invariant and naturally allows for _instance segmentation_ , as opposed to
semantic segmentation where groups correspond to pre-defined categories. RNN-
EM learns to segment in an unsupervised fashion, which makes it applicable to
settings with little or no labeled data. On the downside this lack of
supervision means that the resulting segmentation may not always match the
intended outcome. This problem is inherent to this task since in real world
images the notion of an object is ill-defined and task dependent. We envision
future work to alleviate this by extending unsupervised segmentation to
hierarchical groupings, and by dynamically conditioning them on the task at
hand using top-down feedback and attention.

##  6 Conclusion

We have argued for the importance of separately representing conceptual
entities contained in the input, and suggested clustering based on statistical
regularities as an appropriate unsupervised approach for separating them. We
formalized this notion and derived a novel framework that combines neural
networks and generalized EM into a trainable clustering algorithm. We have
shown how this method can be trained in a fully unsupervised fashion to
segment its inputs into entities, and to represent them individually. Using
synthetic images and video, we have empirically verified that our method can
recover the objects underlying the data, and represent them in a useful way.
We believe that this work will help to develop a theoretical foundation for
understanding this important problem of unsupervised learning, as well as
providing a first step towards building practical solutions that make use of
these symbol-like representations.

## Acknowledgements

The authors wish to thank Paulo Rauber and the anonymous reviewers for their
constructive feedback. This research was supported by the Swiss National
Science Foundation grant 200021_165675/1 and the EU project “INPUT”
(H2020-ICT-2015 grant no. 687795). We are grateful to NVIDIA Corporation for
donating us a DGX-1 as part of the Pioneers of AI Research award, and to IBM
for donating a “Minsky” machine.

## References

  * [1] H.B. Barlow, T.P. Kaushal, and G.J. Mitchison.  Finding Minimum Entropy Codes.  Neural Computation, 1(3):412–423, September 1989.
  * [2] Amir Beck and Marc Teboulle.  A fast iterative shrinkage-thresholding algorithm with application to wavelet-based image deblurring.  In Acoustics, Speech and Signal Processing, 2009. ICASSP 2009. IEEE International Conference On, pages 693–696. IEEE, 2009.
  * [3] Yoshua Bengio.  Deep learning of representations: Looking forward.  In International Conference on Statistical Language and Speech Processing, pages 1–37. Springer, 2013.
  * [4] Xi Chen, Yan Duan, Rein Houthooft, John Schulman, Ilya Sutskever, and Pieter Abbeel.  InfoGAN: Interpretable Representation Learning by Information Maximizing Generative Adversarial Nets.  arXiv:1606.03657 [cs, stat], June 2016.
  * [5] Ingrid Daubechies, Michel Defrise, and Christine De Mol.  An iterative thresholding algorithm for linear inverse problems with a sparsity constraint.  Communications on pure and applied mathematics, 57(11):1413–1457, 2004.
  * [6] 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., pages 1–38, 1977.
  * [7] Klaus Greff, Antti Rasmus, Mathias Berglund, Tele Hotloo Hao, Jürgen Schmidhuber, and Harri Valpola.  Tagger: Deep Unsupervised Perceptual Grouping.  arXiv:1606.06724 [cs], June 2016.
  * [8] Klaus Greff, Rupesh Kumar Srivastava, and Jürgen Schmidhuber.  Binding via Reconstruction Clustering.  arXiv:1511.06418 [cs], November 2015.
  * [9] Karol Gregor and Yann LeCun.  Learning fast approximations of sparse coding.  In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 399–406, 2010.
  * [10] Jose A. Guerrero-Colón, Eero P. Simoncelli, and Javier Portilla.  Image denoising using mixtures of Gaussian scale mixtures.  In Image Processing, 2008. ICIP 2008. 15th IEEE International Conference On, pages 565–568. IEEE, 2008.
  * [11] John R. Hershey, Jonathan Le Roux, and Felix Weninger.  Deep unfolding: Model-based inspiration of novel deep architectures.  arXiv preprint arXiv:1409.2574, 2014.
  * [12] Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner.  Beta-VAE: Learning basic visual concepts with a constrained variational framework.  In In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
  * [13] Geoffrey E. Hinton.  Distributed representations.  1984\.
  * [14] Aapo Hyvärinen and Jukka Perkiö.  Learning to Segment Any Random Vector.  In The 2006 IEEE International Joint Conference on Neural Network Proceedings, pages 4167–4172. IEEE, 2006.
  * [15] Alexander Ilin, Isabeau Prémont-Schwarz, Tele Hotloo Hao, Antti Rasmus, Rinu Boney, and Harri Valpola.  Recurrent Ladder Networks.  arXiv:1707.09219 [cs, stat], July 2017.
  * [16] Phillip Isola, Daniel Zoran, Dilip Krishnan, and Edward H. Adelson.  Learning visual groups from co-occurrences in space and time.  arXiv:1511.06811 [cs], November 2015.
  * [17] Nebojsa Jojic and Brendan J. Frey.  Learning flexible sprites in video layers.  In Computer Vision and Pattern Recognition, 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference On, volume 1, pages I–I. IEEE, 2001.
  * [18] Anitha Kannan, John Winn, and Carsten Rother.  Clustering appearance and shape by learning jigsaws.  In Advances in Neural Information Processing Systems, pages 657–664, 2007.
  * [19] Diederik Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [20] Nicolas Le Roux, Nicolas Heess, Jamie Shotton, and John Winn.  Learning a generative model of images by factoring appearance and shape.  Neural Computation, 23(3):593–650, 2011.
  * [21] P. M. Milner.  A model for visual shape recognition.  Psychological review, 81(6):521, 1974.
  * [22] Augustus Odena, Vincent Dumoulin, and Chris Olah.  Deconvolution and Checkerboard Artifacts.  Distill, 2016.
  * [23] Deepak Pathak, Ross Girshick, Piotr Dollár, Trevor Darrell, and Bharath Hariharan.  Learning Features by Watching Objects Move.  arXiv:1612.06370 [cs, stat], December 2016.
  * [24] R. A. Rao, G. Cecchi, C. C. Peck, and J. R. Kozloski.  Unsupervised segmentation with dynamical units.  Neural Networks, IEEE Transactions on, 19(1):168–182, 2008.
  * [25] R. A. Rao and G. A. Cecchi.  An objective function utilizing complex sparsity for efficient segmentation in multi-layer oscillatory networks.  International Journal of Intelligent Computing and Cybernetics, 3(2):173–206, 2010.
  * [26] David P. Reichert and Thomas Serre.  Neuronal Synchrony in Complex-Valued Deep Networks.  arXiv:1312.6115 [cs, q-bio, stat], December 2013.
  * [27] Christopher J. Rozell, Don H. Johnson, Richard G. Baraniuk, and Bruno A. Olshausen.  Sparse coding via thresholding and local competition in neural circuits.  Neural computation, 20(10):2526–2563, 2008.
  * [28] E. Saund.  A multiple cause mixture model for unsupervised learning.  Neural Computation, 7(1):51–71, 1995.
  * [29] J. Schmidhuber.  Learning to control fast-weight memories: An alternative to dynamic recurrent networks.  Neural Computation, 4(1):131–139, 1992.
  * [30] Jürgen Schmidhuber.  Learning Complex, Extended Sequences Using the Principle of History Compression.  Neural Computation, 4(2):234–242, March 1992.
  * [31] Jürgen Schmidhuber.  Learning Factorial Codes by Predictability Minimization.  Neural Computation, 4(6):863–879, November 1992.
  * [32] Pablo Sprechmann, Alexander M. Bronstein, and Guillermo Sapiro.  Learning efficient sparse and low rank models.  IEEE transactions on pattern analysis and machine intelligence, 37(9):1821–1833, 2015.
  * [33] Anne Treisman.  The binding problem.  Current Opinion in Neurobiology, 6(2):171–178, April 1996.
  * [34] Sudheendra Vijayanarasimhan, Susanna Ricco, Cordelia Schmid, Rahul Sukthankar, and Katerina Fragkiadaki.  SfM-Net: Learning of Structure and Motion from Video.  arXiv:1704.07804 [cs], April 2017.
  * [35] N. X. Vinh, J. Epps, and J. Bailey.  Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance.  JMLR, 11:2837–2854, 2010.
  * [36] C. von der Malsburg.  Binding in models of perception and brain function.  Current opinion in neurobiology, 5(4):520–526, 1995.
  * [37] Christoph von der Malsburg.  The Correlation Theory of Brain Function.  Departmental technical report, MPI, 1981.
  * [38] D. Wang and D. Terman.  Locally excitatory globally inhibitory oscillator networks.  Neural Networks, IEEE Transactions on, 6(1):283–286, 1995.
  * [39] Paul J. Werbos.  Generalization of backpropagation with application to a recurrent gas market model.  Neural networks, 1(4):339–356, 1988.
  * [40] H. Wersing, J. J. Steil, and H. Ritter.  A competitive-layer model for feature binding and sensory segmentation.  Neural Computation, 13(2):357–387, 2001.
  * [41] Ronald J. Williams.  Complexity of exact gradient computation algorithms for recurrent neural networks.  Technical report, Technical Report Technical Report NU-CCS-89-27, Boston: Northeastern University, College of Computer Science, 1989.
  * [42] CF Jeff Wu.  On the convergence properties of the EM algorithm.  The Annals of statistics, pages 95–103, 1983.

##  Appendix A Experiment Details

The following subsections provide detailed information about the experimental
setup of our empirical evaluation.

In all experiments we train the networks using ADAM [19] with default
parameters, a batch size of 64 and $50\,000$ train + $10\,000$ validation +
$10\,000$ test inputs. The quality of the learned groupings is evaluated by
computing the Adjusted Mutual Information (AMI; [35]) with respect to the
ground truth, while ignoring the background and overlap regions (as is
consistent with earlier work [8, 7]). We use early stopping when the
validation loss has not improved for 10 epochs.

###  A.1 Experiments on Static Shapes

Each input consists of a $28\times 28$ binary image containing three regular
shapes ($\triangle\raisebox{1.99997pt}{$\bigtriangledown$}\square$) located in
random positions [26].

For N-EM we implement $f_{\phi}$ by means of a single layer fully connected
neural network with a sigmoid activation function. It receives a real-valued
250-dimensional vector $\bm{\theta}$ as input and outputs for each pixel a
value that parameterizes a Bernoulli distribution. We squash $\bm{\theta}$
with a Sigmoid before passing it to the network and train an additional weight
to implement the learning rate that is used to combine the gradient ascent
updates into the current parameter estimate.

Similarly for RNN-EM we use a recurrent neural network with 250 Sigmoidal
hidden units and an fully-connected output-layer with a sigmoid activation
function that parametrizes a Bernoulli distribution for each pixel in the same
fashion.

We train both networks with $K=4$ for 15 EM steps and add bitflip noise with
probability 0.1 to each of the pixels. The prior for each pixel in the data is
set to a Bernoulli distribution with $p=0$. The outer-loss is only injected at
the final EM-step.

###  A.2 Experiments on Flying Shapes

Each input consists of a sequence of binary $28\times 28$ images containing a
fixed number of shapes
($\triangle\raisebox{1.99997pt}{$\bigtriangledown$}\square$) that start in
random positions and float along randomly sampled trajectories within the
image for 20 steps.

We use a convolutional encoder-decoder architecture inspired by recent GANs
[4] with a recurrent neural network as bottleneck:

  1. 1.

$4\times 4$ conv. 32 ELU. stride 2. layer norm

  2. 2.

$4\times 4$ conv. 64 ELU. stride 2. layer norm

  3. 3.

fully connected. 512 ELU. layer norm

  4. 4.

recurrent. 100 Sigmoid. layer norm on the output

  5. 5.

fully connected. 512 RELU. layer norm

  6. 6.

fully connected. $7\times 7\times 64$ RELU. layer norm

  7. 7.

$4\times 4$ reshape 2 nearest-neighbour, conv. 32 RELU. layer norm

  8. 8.

$4\times 4$ reshape 2 nearest-neighbour, conv. 1 Sigmoid

Instead of using transposed convolutions (to implement the "de-convolution")
we first reshape the image using the default nearest-neighbour interpolation
followed by a normal convolution in order to avoid frequency artifacts [22].
Note that we do not add layer norm on the recurrent connection.

At each timestep $t$ we feed
$\bm{\gamma}_{k}(\bm{\psi}_{k}^{(t-1)}-\bm{\tilde{x}}^{(t)})$ as input to the
network, where $\bm{\tilde{x}}$ is the input with added bitflip noise
($p=0.2$). RNN-EM is trained with a next-step prediction objective implemented
by replacing $\bm{x}$ with $\bm{x}^{(t+1)}$ in (5), which we evaluate at each
time-step. A single RNN-EM step is used for each timestep. The prior for each
pixel in the data is set to a Bernoulli distribution with $p=0$. We prevent
conflicting gradient updates by not back-propagating any gradients through
$\bm{\gamma}$.

###  A.3 Experiments on Flying MNIST

Each input consists of a sequence of gray-scale $24\times 24$ images
containing a fixed number of down-sampled (by a factor of two along each
dimension) MNIST digits that start in random positions and “fly” across
randomly sampled trajectories within the image for $T$ timesteps.

We use a slightly deeper version of the architecture used for flying shapes:

  1. 1.

$4\times 4$ conv. 32 ELU. stride 2. layer norm

  2. 2.

$4\times 4$ conv. 64 ELU. stride 2. layer norm

  3. 3.

$4\times 4$ conv. 128 ELU. stride 2. layer norm

  4. 4.

fully connected. 512 ELU. layer norm

  5. 5.

recurrent. 250 Sigmoid. layer norm on the output

  6. 6.

fully connected. 512 RELU. layer norm

  7. 7.

fully connected. $3\times 3\times 128$ RELU. layer norm

  8. 8.

$4\times 4$ reshape 2 nearest-neighbour, conv. 64 RELU. layer norm

  9. 9.

$4\times 4$ reshape 2 nearest-neighbour, conv. 32 RELU. layer norm

  10. 10.

$4\times 4$ reshape 2 nearest-neighbour, conv. 1 linear

The training procedure is largely identical to the one described for flying
shapes except that we replace the bitflip noise with masked uniform noise: we
first sample a binary mask from a multi-variate Bernoulli distribution with
$p=0.2$ and then use this mask to interpolate between the original image and
samples from a Uniform distribution between the minimum $(0.0)$ and maximum
$(1.0)$ values of the data. We use a learning rate of $0.0005$ (from the
second stage onwards in case of stage-wise training), scale the second-loss
term by a factor of 0.2 and find it beneficial to normalize the masked
differences between the prediction and the image (zero mean, standard
deviation one) before passing it to the network.


# Sentiment Tagging with Partial Labels using Modular Architectures

Xiao Zhang
Purdue University
<EMAIL_ADDRESS>
&Dan Goldwasser
Purdue University
<EMAIL_ADDRESS>

###### Abstract

Many NLP learning tasks can be decomposed into several distinct sub-tasks,
each associated with a partial label. In this paper we focus on a popular
class of learning problems, sequence prediction applied to several sentiment
analysis tasks, and suggest a modular learning approach in which different
sub-tasks are learned using separate functional modules, combined to perform
the final task while sharing information. Our experiments show this approach
helps constrain the learning process and can alleviate some of the supervision
efforts.

##  1 Introduction

Many natural language processing tasks attempt to replicate complex human-
level judgments, which often rely on a composition of several sub-tasks into a
unified judgment. For example, consider the Targeted-Sentiment task Mitchell
et al. (2013), assigning a sentiment polarity score to entities depending on
the context that they appear in. Given the sentence “according to a CNN poll,
Green Book will win the best movie award”, the system has to identify both
entities, and associate the relevant sentiment value with each one (neutral
with CNN, and positive with Green Book). This task can be viewed as a
combination of two tasks, entity identification, locating contiguous spans of
words corresponding to relevant entities, and sentiment prediction, specific
to each entity based on the context it appears in. Despite the fact that this
form of functional task decomposition is natural for many learning tasks, it
is typically ignored and learning is defined as a monolithic process,
combining the tasks into a single learning problem.

Our goal in this paper is to take a step towards modular learning
architectures that exploit the learning tasks’ inner structure, and as a
result simplify the learning process and reduce the annotation effort. We
introduce a novel task decomposition approach, learning with partial labels,
in which the task output labels decompose hierarchically, into partial labels
capturing different aspects, or sub-tasks, of the final task. We show that
learning with partial labels can help support weakly-supervised learning when
only some of the partial labels are available.

Given the popularity of sequence labeling tasks in NLP, we demonstrate the
strength of this approach over several sentiment analysis tasks, adapted for
sequence prediction. These include target-sentiment prediction Mitchell et al.
(2013), aspect-sentiment prediction Pontiki et al. (2016) and subjective text
span identification and polarity prediction Wilson et al. (2013). To ensure
the broad applicability of our approach to other problems, we extend the
popular LSTM-CRF Lample et al. (2016) model that was applied to many sequence
labeling tasks111We also provide analysis for NER in the apendix.

The modular learning process corresponds to a task decomposition, in which the
prediction label, $y$, is deconstructed into a set of partial labels
$\\{y^{0},..,y^{k}\\}$, each defining a sub-task, capturing a different aspect
of the original task. Intuitively, the individual sub-tasks are significantly
easier to learn, suggesting that if their dependencies are modeled correctly
when learning the final task, they can constrain the learning problem, leading
to faster convergence and a better overall learning outcome. In addition, the
modular approach helps alleviate the supervision problem, as often providing
full supervision for the overall task is costly, while providing additional
partial labels is significantly easier. For example, annotating entity
segments syntactically is considerably easier than determining their
associated sentiment, which requires understanding the nuances of the context
they appear in semantically. By exploiting modularity, the entity segmentation
partial labels can be used to help improve that specific aspect of the overall
task.

Our modular task decomposition approach is partially inspired by findings in
cognitive neuroscience, namely the two-streams hypothesis, a widely accepted
model for neural processing of cognitive information in vision and hearing
Eysenck and Keane (2005), suggesting the brain processes information in a
modular way, split between a “where” (dorsal) pathway, specialized for
locating objects and a “what” (ventral) pathway, associated with object
representation and recognition Mishkin et al. (1983); Geschwind and Galaburda
(1987); Kosslyn (1987); Rueckl et al. (1989). Jacobs et al. Jacobs et al.
(1991) provided a computational perspective, investigating the “what” and
“where” decomposition on a computer vision task. We observe that this task
decomposition naturally fits many NLP tasks and borrow the notation. In the
target-sentiment tasks we address in this paper, the segmentation tagging task
can be considered as a “where”-task (i.e., the location of entities), and the
sentiment recognition as the “what”-task.

Our approach is related to multi-task learning Caruana (1997), which has been
extensively applied in NLP Toshniwal et al. (2017); Eriguchi et al. (2017);
Collobert et al. (2011); Luong (2016); Liu et al. (2018). However, instead of
simply aggregating the objective functions of several different tasks, we
suggest to decompose a single task into multiple inter-connected sub-tasks and
then integrate the representation learned into a single module for the final
decision. We study several modular neural architectures, which differ in the
way information is shared between tasks, the learning representation
associated with each task and the way the dependency between decisions is
modeled.

Our experiments were designed to answer two questions. First, can the task
structure be exploited to simplify a complex learning task by using a modular
approach? Second, can partial labels be used effectively to reduce the
annotation effort?

To answer the first question, we conduct experiments over several sequence
prediction tasks, and compare our approach to several recent models for deep
structured prediction Lample et al. (2016); Ma and Hovy (2016); Liu et al.
(2018), and when available, previously published results Mitchell et al.
(2013); Zhang et al. (2015); Li and Lu (2017); Ma et al. (2018) We show that
modular learning indeed helps simplify the learning task compared to
traditional monolithic approaches. To answer the second question, we evaluate
our model’s ability to leverage partial labels in two ways. First, by
restricting the amount of full labels, and observing the improvement when
providing increasing amounts of partial labels for only one of the sub-tasks.
Second, we learn the sub-tasks using completely disjoint datasets of partial
labels, and show that the knowledge learned by the sub-task modules can be
integrated into the final decision module using a small amount of full labels.

Our contributions: (1) We provide a general modular framework for sequence
learning tasks. While we focus on sentiment analysis task, the framework is
broadly applicable to many other tagging tasks, for example, NER Carreras et
al. (2002); Lample et al. (2016) and SRL Zhou and Xu (2015), to name a few.
(2) We introduce a novel weakly supervised learning approach, learning with
partial labels, that exploits the modular structure to reduce the supervision
effort. (3) We evaluated our proposed model, in both the fully-supervised and
weakly supervised scenarios, over several sentiment analysis tasks.

##  2 Related Works

From a technical perspective, our task decomposition approach is related to
multi-task learning Caruana (1997), specifically, when the tasks share
information using a shared deep representation Collobert et al. (2011); Luong
(2016). However, most prior works aggregate multiple losses on either
different pre-defined tasks at the final layer Collobert et al. (2011); Luong
(2016), or on a language model at the bottom level Liu et al. (2018). This
work suggests to decompose a given task into sub-tasks whose integration
comprise the original task. To the best of our knowledge, Ma et al. Ma et al.
(2018), focusing on targeted sentiment is most similar to our approach. They
suggest a joint learning approach, modeling a sequential relationship between
two tasks, entity identification and target sentiment. We take a different
approach viewing each of the model components as a separate module, predicted
independently and then integrated into the final decision module. As we
demonstrate in our experiments, this approach leads to better performance and
increased flexibility, as it allows us to decouple the learning process and
learn the tasks independently. Other modular neural architectures were
recently studied for tasks combining vision and language analysis Andreas et
al. (2016); Hu et al. (2017); Yu et al. (2018), and were tailored for the
grounded language setting. To help ensure the broad applicability of our
framework, we provide a general modular network formulation for sequence
labeling tasks by adapting a neural-CRF to capture the task structure. This
family of models, combining structured prediction with deep learning showed
promising results Gillick et al. (2015); Lample et al. (2016); Ma and Hovy
(2016); Zhang et al. (2015); Li and Lu (2017), by using rich representations
through neural models to generate decision candidates, while utilizing an
inference procedure to ensure coherent decisions. Our main observation is that
modular learning can help alleviate some of the difficulty involved in
training these powerful models.

##  3 Architectures for Sequence Prediction

Using neural networks to generate emission potentials in CRFs was applied
successfully in several sequence prediction tasks, such as word segmentation
Chen et al. (2017), NER Ma and Hovy (2016); Lample et al. (2016), chunking and
PoS tagging Liu et al. (2018); Zhang et al. (2017). A sequence is represented
as a sequence of $L$ tokens: $\bm{x}=[x_{1},x_{2},\dots,x_{L}]$, each token
corresponds to a label $y\in\mathcal{Y}$, where $\mathcal{Y}$ is the set of
all possible tags. An inference procedure is designed to find the most
probable sequence $\bm{y}^{*}=[y_{1},y_{2},\dots,y_{L}]$ by solving, either
exactly or approximately, the following optimization problem:

$\bm{y}^{*}=\arg\max_{\bm{y}}P(\bm{y}|\bm{x}).$

Despite the difference in tasks, these models follow a similar general
architecture: (1) Character-level information, such as prefix, suffix and
capitalization, is represented through a character embedding layer learned
using a bi-directional LSTM (BiLSTM). (2) Word-level information is obtained
through a word embedding layer. (3) The two representations are concatenated
to represent an input token, used as input to a word-level BiLSTM which
generates the emission potentials for a succeeding CRF. (4) The CRF is used as
an inference layer to generate the globally-normalized probability of possible
tag sequences.

###  3.1 CRF Layer

A CRF model describes the probability of predicted labels $\bm{y}$, given a
sequence $\bm{x}$ as input, as

$P_{\bm{\Lambda}}(\bm{y}|\bm{x})=\frac{e^{\Phi(\bm{x},\bm{y})}}{Z},$

where $Z=\sum\limits_{\tilde{\bm{y}}}e^{\Phi(\bm{x},\tilde{\bm{y}})}$ is the
partition function that marginalize over all possible assignments to the
predicted labels of the sequence, and $\Phi(\bm{x},\bm{y})$ is the scoring
function, which is defined as:

$\Phi(\bm{x},\bm{y})=\sum\limits_{t}\phi(\bm{x},y_{t})+\psi(y_{t-1},y_{t}).$

The partition function $Z$ can be computed efficiently via the forward-
backward algorithm. The term $\phi(\bm{x},y_{t})$ corresponds to the score of
a particular tag $y_{t}$ at position $t$ in the sequence, and
$\psi(y_{t-1},y_{t})$ represents the score of transition from the tag at
position $t-1$ to the tag at position $t$. In the Neural CRF model,
$\phi(\bm{x},y_{t})$ is generated by the aforementioned Bi-LSTM while
$\psi(y_{t-1},y_{t})$ by a transition matrix.

##  4 Functional Decomposition of Composite Tasks

To accommodate our task decomposition approach, we first define the notion of
partial labels, and then discuss different neural architectures capturing the
dependencies between the modules trained over the different partial labels.

Partial Labels and Task Decomposition: Given a learning task, defined over an
output space $y\in\mathcal{Y}$, where $\mathcal{Y}$ is the set of all possible
tags, each specific label $y$ is decomposed into a set of partial labels,
$\\{y^{0},..,y^{k}\\}$. We refer to $y$ as the full label. According to this
definition, a specific assignment to all $k$ partial labels defines a single
full label. Note the difference between partially labeled data Cour et al.
(2011), in which instances can have more than a single full label, and our
setup in which the labels are partial.

In all our experiments, the partial labels refer to two sub-tasks, (1) a
segmentation task, identifying Beginning, Inside and Outside of an entity or
aspect. (2) one or more type recognition tasks, recognizing the aspect type
and/or the sentiment polarity associated with it. Hence, a tag $y_{t}$ at
location $t$ is divided into $y_{t}^{seg}$ and $y_{t}^{typ}$, corresponding to
segmentation and type (sentiment type here) respectively. Fig. 1 provides an
example of the target-sentiment task. Note that the sentiment labels do not
capture segmentation information.

Figure 1: Target-sentiment decomposition example.

Modular Learning architectures:  We propose three different models, in which
information from the partial labels can be used. All the models have similar
modules types, corresponding to the segmentation and type sub-tasks, and the
decision module for predicting the final task. The modules are trained over
the partial segmentation ($\bm{y}^{seg}$) and type ( $\bm{y}^{typ}$) labels,
and the full label $\bm{y}$ information, respectively.

These three models differ in the way they share information. Model 1, denoted
Twofold Modular, LSTM-CRF-T, is similar in spirit to multi-task learning
Collobert et al. (2011) with three separate modules. Model 2, denoted Twofold
modular Infusion, (LSTM-CRF-TI) and Model 3, denoted Twofold modular Infusion
with guided gating, (LSTM-CRF-TI(g)) both infuse information flow from two
sub-task modules into the decision module. The difference is whether the
infusion is direct or goes through a guided gating mechanism. The three models
are depicted in Fig. 2 and described in details in the following paragraphs.
In all of these models, underlying neural architecture are used for the
emission potentials when CRF inference layers are applied on top.

(a) LSTM-CRF-T

(b) LSTM-CRF-TI

(c) LSTM-CRF-TI (G)

Figure 2: Three modular models for task decomposition. In them, blue blocks
are segmentation modules, detecting entity location and segmentation, and
yellow blocks are the type modules, recognizing the entity type or sentiment
polarity. Green blocks are the final decision modules, integrating all the
decisions. (G) refers to “Guided Gating”

###  4.1 Twofold Modular Model

The twofold modular model enhances the original monolithic model by using
multi-task learning with shared underlying representations. The segmentation
module and the type module are trained jointly with the decision module, and
all the modules share information by using the same embedding level
representation, as shown in Figure 2(a). Since the information above the
embedding level is independent, the LSTM layers in the different modules do
not share information, so we refer to these layers of each module as private.

The segmentation module predicts the segmentation BIO labels at position $t$
of the sequence by using the representations extracted from its private word
level bi-directional LSTM (denoted as $\mathcal{H}^{seg}$) as emission for a
individual CRF:

$\displaystyle\bm{h}_{t}^{seg}=\mathcal{H}^{seg}(\bm{e}_{t},\overrightarrow{\bm{h}}_{t-1}^{seg},\overrightarrow{\bm{h}}_{t+1}^{seg}),$
$\displaystyle\phi(\bm{x},y^{seg}_{t})=\bm{W}^{seg\intercal}\bm{h}^{seg}_{t}+\bm{b}^{seg},$

where $\bm{W}^{seg}$ and $\bm{b}^{seg}$ denote the parameters of the
segmentation module emission layer, and $\mathcal{H}^{seg}$ denotes its
private LSTM layer.

This formulation allows the model to forge the segmentation path privately
through back-propagation by providing the segmentation information
$\bm{y}^{seg}$ individually, in addition to the complete tag information
$\bm{y}$.

The type module, using $\bm{y}^{typ}$, is constructed in a similar way. By
using representations from the its own private LSTM layers, the type module
predicts the sentiment (entity) type at position $t$ of the sequence :

$\displaystyle\bm{h}^{typ}_{t}=\mathcal{H}^{typ}(\bm{e}_{t},\overrightarrow{\bm{h}}_{t-1}^{typ},\overrightarrow{\bm{h}}_{t+1}^{typ}),$
$\displaystyle\phi(\bm{x},y^{typ}_{t})=\bm{W}^{typ\intercal}\bm{h}^{typ}_{t}+\bm{b}^{typ}.$

Both the segmentation information $\bm{y}^{seg}$ and the type information
$\bm{y}^{typ}$ are provided together with the complete tag sequence $\bm{y}$,
enabling the model to learn segmentation and type recognition simultaneously
using two different paths. Also, the decomposed tags naturally augment more
training data to the model, avoiding over-fitting due to more complicated
structure. The shared representation beneath the private LSTMs layers are
updated via the back-propagated errors from all the three modules.

###  4.2 Two-fold Modular Infusion Model

The twofold modular infusion model provides a stronger connection between the
functionalities of the two sub-tasks modules and the final decision module,
differing from multi-task leaning.

In this model, instead of separating the pathways from the decision module as
in the previous twofold modular model, the segmentation and the type
representation are used as input to the final decision module. The model
structure is shown in Figure 2(b), and can be described formally as:

$\displaystyle\bm{I}_{t}^{seg}=\bm{W}^{seg\intercal}\bm{h}_{t}^{seg}+\bm{b}^{seg},$
$\displaystyle\bm{I}_{t}^{typ}=\bm{W}^{typ\intercal}\bm{h}_{t}^{typ}+\bm{b}^{typ},$
$\displaystyle
S_{t}=\bm{W}^{\intercal}[\bm{h}_{t};\bm{I}_{t}^{seg};\bm{I}_{t}^{typ}]+\bm{b},$

where $S_{t}$ is the shared final emission potential to the CRF layer in the
decision module, and ; is the concatenation operator, combining the
representation from the decision module and that from the type module and the
segmentation module.

The term “Infusion” used for naming this module is intended to indicate that
both modules actively participate in the final decision process, rather than
merely form two independent paths as in the twofold modular model. This
formulation provides an alternative way of integrating the auxiliary sub-tasks
back into the major task in the neural structure to help improve learning.

###  4.3 Guided Gating Infusion

In the previous section we described a way of infusing information from other
modules naively by simply concatenating them. But intuitively, the hidden
representation from the decision module plays an important role as it is
directly related to the final task we are interested in. To effectively use
the information from other modules forming sub-tasks, we design a gating
mechanism to dynamically control the amount of information flowing from other
modules by infusing the expedient part while excluding the irrelevant part, as
shown in Figure 2(c). This gating mechanism uses the information from the
decision module to guide the information from other modules, thus we name it
as guided gating infusion, which we describe formally as follows:

$\displaystyle\bm{I}_{t}^{seg}=$
$\displaystyle\sigma(\bm{W_{1}}h_{t}+\bm{b_{1}})\otimes(\bm{W}^{seg\intercal}\bm{h}_{t}^{seg}+\bm{b}^{seg}),$
$\displaystyle\bm{I}_{t}^{typ}=$
$\displaystyle\sigma(\bm{W_{2}}h_{t}+\bm{b_{2}})\otimes(\bm{W}^{typ\intercal}\bm{h}_{t}^{typ}+\bm{b}^{typ}),$
$\displaystyle S_{t}=$
$\displaystyle\bm{W}^{\intercal}[\bm{h}_{t};\bm{I}_{t}^{seg};\bm{I}_{t}^{typ}]+\bm{b},$

where $\sigma$ is the logistic sigmoid function and $\otimes$ is the element-
wise multiplication. The $\\{W_{1},W_{2},b_{1},b_{2}\\}$ are the parameters of
these guided gating, which are updated during the training to maximize the
overall sequence labeling performance.

##  5 Learning using Full and Partial Labels

Our objective naturally rises from the model we described in the text.
Furthermore, as our experiments show, it is easy to generalize this objective,
to a “semi-supervised” setting, in which the learner has access to only a few
fully labeled examples and additional partially labeled examples. E.g., if
only segmentation is annotated but the type information is missing. The loss
function is a linear combination of the negative log probability of each sub-
tasks, together with the decision module:

$\displaystyle\mathcal{J}=$ $\displaystyle-\sum\limits_{i}^{N}\log
P(\bm{y}^{i}|\bm{x}^{i})+\alpha\log P(\bm{y}^{seg(i)}|\bm{x}^{(i)})$
$\displaystyle+\beta\log P(\bm{y}^{typ(i)}|\bm{x}^{(i)}),$ (1)

where $N$ is the number of examples in the training set, $\bm{y}^{seg}$ and
$\bm{y}^{typ}$ are the decomposed segmentation and type tags corresponding to
the two sub-task modules, and $\alpha$ and $\beta$ are the hyper-parameters
controlling the importance of the two modules contributions respectively.

If the training example is fully labeled with both segmentation and type
annotated, training is straightforward; if the training example is partially
labeled, e.g., only with segmentation but without type, we can set the log
probability of the type module and the decision module $0$ and only train the
segmentation module. This formulation provides extra flexibility of using
partially annotated corpus together with fully annotated corpus to improve the
overall performance.

##  6 Experimental Evaluation

Our experimental evaluation is designed to evaluate the two key aspects of our
model:

(Q1) Can the modular architecture alleviate the difficulty of learning the
final task? To answer this question, we compare our modular architecture to
the traditional neural-CRF model and several recent competitive models for
sequence labeling combining inference and deep learning. The results are
summarized in Tables 1-3.

(Q2) Can partial labels be used effectively as a new form of weak-supervision?
To answer this question we compared the performance of the model when trained
using disjoint sets of partial and full labels, and show that adding examples
only associated with partial labels, can help boost performance on the final
task. The results are summarized in Figures 3-5.

###  6.1 Experimental Settings

####  6.1.1 Datasets

We evaluated our models over three different sentiment analysis tasks adapted
for sequence prediction. We included additional results for multilingual NER
in the Appendix for reference.

##### Target Sentiment Datasets

We evaluated our models on the targeted sentiment dataset released by Mitchell
et al. Mitchell et al. (2013), which consists of entity and sentiment
annotations on both English and Spanish tweets. Similar to previous studies
Mitchell et al. (2013); Zhang et al. (2015); Li and Lu (2017), our task
focuses on people and organizations (collapsed into volitional named entities
tags) and the sentiment associated with their description in tweets. After
this processing, the labels of each tweets are composed of both segmentation
(entity spans) and types (sentiment tags).

We used the original 10-fold cross validation splits to calculate averaged F1
score, using 10% of the training set for development. We used the same metrics
in Zhang et al. Zhang et al. (2015) and Li and Lu Li and Lu (2017) for a fair
comparison.

##### Aspect Based Sentiment Analysis Datasets

We used the Restaurants dataset provided by SemEval 2016 Task 5 subtask 1,
consisting of opinion target (aspect) expression segmentation, aspect
classification and matching sentiment prediction. In the original task
definition, the three tasks were designed as a pipeline, and assumed gold
aspect labels when predicting the matching sentiment labels. Instead, our
model deals with the challenging end-to-end setting by casting the problem as
a sequence labeling task, labeling each aspect segment with the aspect label
and sentiment polarity222using only the subset of the data containing sequence
information.

##### Subjective Polarity Disambiguation Datasets

We adapted the SemEval 2013 Task 2 subtask A as another task to evaluate our
model. In this task, the system is given a marked phrase inside a longer text,
and is asked to label its polarity. Unlike the original task, we did not
assume the sequence is known, resulting in two decisions, identifying
subjective expressions (i.e., a segmentation task) and labeling their
polarity, which can be modeled jointly as a sequence labeling task.

####  6.1.2 Input Representation and Model Architecture

Following previous studies Ma and Hovy (2016); Liu et al. (2018) showing that
the word embedding choice can significantly influence performance, we used the
pre-trained GloVe 100 dimension Twitter embeddings only for all tasks in the
main text. All the words not contained in these embeddings (OOV, out-of-
vocabulary words) are treated as an “unknown” word. Our models were deployed
with minimal hyper parameters tuning, and can be briefly summarized as: the
character embeddings has dimension 30, the hidden layer dimension of the
character level LSTM is 25, and the hidden layer of the word level LSTM has
dimension 300. Similar to Liu et al. Liu et al. (2018), we also applied
highway networks Srivastava et al. (2015) from the character level LSTM to the
word level LSTM. In our pilot study, we shrank the number of parameters in our
modular architectures to around one third such that the total number of
parameter is similar as that in the LSTM-CRF model, but we did not observe a
significant performance change so we kept them as denoted. The values of
$\alpha$ and $\beta$ in the objective function were always set to 1.0.

####  6.1.3 Learning

We used BIOES tagging scheme but only during the training and convert them
back to BIO2 for evaluation for all tasks333Using BIOES improves model
complexity in Training, as suggested in previous studies. But to make a fair
comparison to most previous work, who used BIO2 for evaluation, we converted
labels to BIO2 system in the testing stage. (To be clear, using BIOES in the
testing actually yields higher f1 scores in the testing stage, which some
previous studies used unfairly). Our model was implemented using pytorch
Paszke et al. (2017). To help improve performance we parallelized the forward
algorithm and the Viterbi algorithm on the GPU. All the experiments were run
on NVIDIA GPUs. We used the Stochastic Gradient Descent (SGD) optimization of
batch size 10, with a momentum 0.9 to update the model parameters, with the
learning rate 0.01, the decay rate 0.05; The learning rate decays over epochs
by $\eta/(1+e*\rho)$, where $\eta$ is the learning rate, $e$ is the epoch
number, and $\rho$ is the decay rate. We used gradient clip to force the
absolute value of the gradient to be less than 5.0. We used early-stop to
prevent over-fitting, with a patience of 30 and at least 120 epochs. In
addition to dropout, we used Adversarial Training (AT) Goodfellow et al.
(2014), to regularize our model as the parameter numbers increase with
modules. AT improves robustness to small worst-case perturbations by computing
the gradients of a loss function w.r.t. the input. In this study, $\alpha$ and
$\beta$ in Eq. 1 are both set to $1.0$, and we leave other tuning choices for
future investigation.

###  6.2 Q1: Monolithic vs. Modular Learning

Our first set of results are designed to compare our modular learning models,
utilize partial labels decomposition, with traditional monolithic models, that
learn directly over the full labels. In all three tasks, we compare with
strong sequence prediction models, including LSTM-CRF Lample et al. (2016),
which is directly equivalent to our baseline model (i.e., final task decision
without the modules), and LSTM-CNN-CRF Ma and Hovy (2016) and LSTM-CRF-LM Liu
et al. (2018) which use a richer latent representation for scoring the
emission potentials.

##### Target Sentiment task

The results are summarized in Tab. 1. We also compared our models with
recently published state-of-the-art models on these datasets. To help ensure a
fair comparison with Ma et al. which does not use inference, we also included
the results of our model without the CRF layer (denoted LSTM-Ti(g)). All of
our models beat the state-of-the-art results by a large margin. The source
code and experimental setup are available
online444https://github.com/cosmozhang/Modular_Neural_CRF.

System | Architecture | Eng. | Spa.
---|---|---|---
Zhang et al. Zhang et al. (2015) | Pipeline | 40.06 | 43.04
Joint | 39.67 | 43.02
Collapsed | 38.36 | 40.00
Li and Lu Li and Lu (2017) | SS | 40.11 | 42.75
+embeddings | 43.55 | 44.13
+POS tags | 42.21 | 42.89
+semiMarkov | 40.94 | 42.14
Ma et al. Ma et al. (2018) | HMBi-GRU | 42.87 | 45.61
baseline | LSTM-CRF | 49.89 | 48.84
This work | LSTM-Ti(g) | 45.84 | 46.59
LSTM-CRF-T | 51.34 | 49.47
LSTM-CRF-Ti | 51.64 | 49.74
LSTM-CRF-Ti(g) | 52.15 | 50.50
Table 1: Comparing our models with the competing models on the target
sentiment task. The results are on the full prediction of both segmentation
and sentiment.

##### Aspect Based Sentiment

We evaluated our models on two tasks: The first uses two modules, for
identifying the position of the aspect in the text (i.e., chunking) and the
aspect category prediction (denoted E+A). The second adds a third module that
predicts the sentiment polarity associated with the aspect (denoted E+A+S).
I.e., for a given sentence, label its entity span, the aspect category of the
entity and the sentiment polarity of the entity at the same time. The results
over four languages are summarized in Tab. 2. In all cases, our modular
approach outperforms all monolithic approaches.

Models | English | Spanish | Dutch | Russian
---|---|---|---|---
E+A | E+A+S | E+A | E+A+S | E+A | E+A+S | E+A | E+A+S
LSTM-CNN-CRFMa and Hovy (2016) | 58.73 | 44.20 | 64.32 | 50.34 | 51.62 | 36.88 | 58.88 | 38.13
LSTM-CRF-LMLiu et al. (2018) | 62.27 | 45.04 | 63.63 | 50.15 | 51.78 | 34.77 | 62.18 | 38.80
LSTM-CRF | 59.11 | 48.67 | 62.98 | 52.10 | 51.35 | 37.30 | 63.41 | 42.47
LSTM-CRF-T | 60.87 | 49.59 | 64.24 | 52.33 | 52.79 | 37.61 | 64.72 | 43.01
LSTM-CRF-TI | 63.11 | 50.19 | 64.40 | 52.85 | 53.05 | 38.07 | 64.98 | 44.03
LSTM-CRF-TI(g) | 64.74 | 51.24 | 66.13 | 53.47 | 53.63 | 38.65 | 65.64 | 45.65
Table 2: Comparing our models with recent results on the Aspect Sentiment
datasets.

##### Subjective Phrase Identification and Classification

This dataset contains tweets annotated with sentiment phrases, used for
training the models. As in the original SemEval task, it is tested in two
settings, in-domain, where the test data also consists of tweets, and out-of-
domain, where the test set consists of SMS text messages. We present the
results of experiments on these data set in Table 3.

Models | Tweets | SMS
---|---|---
LSTM-CNN-CRF | 35.82 | 23.23
LSTM-CRF-LM | 35.67 | 23.25
LSTM-CRF | 34.15 | 26.28
LSTM-CRF-T | 35.37 | 27.11
LSTM-CRF-Ti | 36.52 | 28.05
LSTM-CRF-Ti(g) | 37.71 | 29.24
Table 3: Comparing our models with competing models on the subjective
sentiment task.

###  6.3 Q2: Partial Labels as Weak Supervision

Our modular architecture is a natural fit for learning with partial labels.
Since the modular architecture decomposes the final task into sub-tasks, the
absence of certain partial labels is permitted. In this case, only the module
corresponding to the available partial labels will be updated while the other
parts of the model stay fixed.

This property can be exploited to reduce the supervision effort by defining
semi-supervised learning protocols that use partial-labels when the full
labels are not available, or too costly to annotate. E.g., in the target
sentiment task, segmentation labels are significantly easier to annotate.

To demonstrate this property we conducted two sets of experiments. The first
investigates how the decision module can effectively integrate the knowledge
independently learned by sub-tasks modules using different partial labels. We
quantify this ability by providing varying amounts of full labels to support
the integration process. The second set studies the traditional semi-
supervised settings, where we have a handful of full labels, but we have a
larger amount of partial labels.

##### Modular Knowledge Integration

The modular architecture allows us to train each model using data obtained
separately for each task, and only use a handful of examples annotated for the
final task in order to integrate the knowledge learned by each module into a
unified decision. We simulated these settings by dividing the training data
into three folds. We associated each one of the first two folds with the two
sub-task modules. Each one of the these folds only included the partial labels
relevant for that sub-task. We then used gradually increasing amounts of the
third fold, consisting of the full labels, for training the decision module.

Fig. 3 describes the outcome for target-sentiment, comparing a non-modular
model using only the full labels, with the modular approach, which uses the
full labels for knowledge integration. Results show that even when very little
full data is available results significantly improve. Additional results show
the same pattern for subjective phrase identification and classification are
included in the Appendix.

(a) Spanish

(b) English

Figure 3: Modular knowledge integration results on the Target Sentiment
Datasets. The x-axis is the amount of percentage of the third fold of full
labels. The “non-modularized” means we only provide fully labeled data from
the third fold.

##### Learning with Partially Labeled Data

Partially-labeled data can be cheaper and easier to obtain, especially for
low-resource languages. In this set of experiments, we model these settings
over the target-sentiment task. The results are summarized in Fig. 4. We fixed
the amount of full labels to $20\%$ of the training set, and gradually
increased the amount of partially labeled data. We studied adding segmentation
and type separately. After the model is trained in this routine, it was tested
on predicting the full labels jointly on the test set.

(a) Spanish

(b) English

Figure 4: The fully labeled data was fixed to $20\%$ of the whole training
set, and gradually adding data with only segmentation information (Magenta),
or with only type information (Orange), and test our model on the full
prediction test. The LSTM-CRF model can only use fully labeled data as it does
not decompose the task.

##### Domain Transfer with Partially Labeled Data

In our final analysis we considered a novel domain-adaptation settings, where
we have a small amount of fully labeled in-domain data from aspect sentiment
and more out-of-domain data from target sentiment. However unlike the
traditional domain-adaptation settings, the out-of-domain data is labeled for
a different task, and only shares one module with the original task.

In our experiments we fixed $20\%$ of the fully labeled data for the aspect
sentiment task, and gradually added out-of-domain data, consisting of partial
sentiment labels from the target sentiment task. Our model successfully
utilized the out-of-domain data and improved performance on the in-domain
task. The results are shown on Fig 5.

Figure 5: Domain Transfer experiments results with fixed $20\%$ in-domain data
from aspect sentiment and varying amounts of out-of-domain data from target
sentiment, shown on the x-axis.

##  7 Conclusions

We present and study several modular neural architectures designed for a novel
learning scenario: learning from partial labels. We experiment with several
sentiment analysis tasks. Our models, inspired by cognitive neuroscience
findings Jacobs et al. (1991); Eysenck and Keane (2005) and multi-task
learning, suggest a functional decomposition of the original task into two
simpler sub-tasks. We evaluate different methods for sharing information and
integrating the modules into the final decision, such that a better model can
be learned, while converging faster555Convergence results are provided in the
Appendix. As our experiments show, modular learning can be used with weak
supervision, using examples annotated with partial labels only.

The modular approach also provides interesting directions for future research,
focusing on alleviating the supervision bottleneck by using large amount of
partially labeled data that are cheaper and easy to obtain, together with only
a handful amount of annotated data, a scenario especially suitable for low-
resource languages.

## Acknowledgements

We thank the reviewers for their insightful comments. We thank the NVIDIA
Corporation for their GPU donation, used in this work. This work was partially
funded by a Google Gift.

## References

  * Agerri and Rigau (2016) Rodrigo Agerri and German Rigau. 2016.  Robust multilingual named entity recognition with shallow semi-supervised features.  _Artificial Intelligence_.
  * Andreas et al. (2016) Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. 2016.  Learning to compose neural networks for question answering.  In _Proc. of the Annual Meeting of the North American Association of Computational Linguistics (NAACL)_.
  * Carreras et al. (2002) Xavier Carreras, Lluís Màrquez, and Lluís Padró. 2002.  Named entity extraction using adaboost.  In _Proc. of the Annual Conference on Computational Natural Language Learning (CoNLL)_.
  * Caruana (1997) Rich Caruana. 1997.  Multitask Learning.  _Machine Learning_ , 28(1):41–75.
  * Chen et al. (2017) Chen, Shi, Qiu, and Huang. 2017.  Adversarial multi-criteria learning for chinese word segmentation.  In _Proc. of the Annual Meeting of the Association Computational Linguistics (ACL)_.
  * Collobert et al. (2011) Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa. 2011.  Natural Language Processing (Almost) from Scratch.  _J. Mach. Learn. Res._ , 12.
  * Cour et al. (2011) Timothee Cour, Ben Sapp, and Ben Taskar. 2011.  Learning from partial labels.  _Journal of Machine Learning Research_ , 12(May).
  * Eriguchi et al. (2017) Eriguchi, Tsuruoka, and Cho. 2017.  Learning to parse and translate improves neural machine translation.  In _Proc. of the Annual Meeting of the Association Computational Linguistics (ACL)_.
  * Eysenck and Keane (2005) M.W. Eysenck and M.T. Keane. 2005.  _Cognitive Psychology: A Student’s Handbook_.  Psychology Press.
  * Geschwind and Galaburda (1987) Norman. Geschwind and Albert M. Galaburda. 1987.  _Cerebral lateralization : biological mechanisms, associations, and pathology_.  MIT Press.
  * Gillick et al. (2015) Gillick, Brunk, Vinyals, and Subramanya. 2015.  Multilingual Language Processing From Bytes.  _ArXiv_.
  * Goodfellow et al. (2014) I. J. Goodfellow, J. Shlens, and C. Szegedy. 2014.  Explaining and Harnessing Adversarial Examples.  _ArXiv e-prints_.
  * Hu et al. (2017) Ronghang Hu, Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Kate Saenko. 2017\.  Learning to reason: End-to-end module networks for visual question answering.  In _Proc. of the International Conference on Computer Vision (ICCV)_.
  * Jacobs et al. (1991) Jacobs, Jordan, and Barto. 1991.  Task decomposition through competition in a modular connectionist architecture: The what and where vision tasks.  _Cognitive Science_ , 15(2).
  * Kosslyn (1987) Stephen M. Kosslyn. 1987.  Seeing and Imagining in the Cerebral Hemispheres: A Computational Approach.  _Psychological Review_ , 94(2):148–175.
  * Lample et al. (2016) Guillaume Lample, Miguel Ballesteros, Kazuya Kawakami, Sandeep Subramanian, and Chris Dyer. 2016.  Neural architectures for named entity recognition.  In _Proc. of the Annual Meeting of the North American Association of Computational Linguistics (NAACL)_.
  * Li and Lu (2017) Hao Li and Wei Lu. 2017.  Learning latent sentiment scopes for entity-level sentiment analysis.  In _Proc. of the National Conference on Artificial Intelligence (AAAI)_.
  * Liu et al. (2018) Liyuan Liu, Jingbo Shang, Frank F. Xu, Xiang Ren, Huan Gui, Jian Peng, and Jiawei Han. 2018.  Empower sequence labeling with task-aware neural language model.  In _Proc. of the National Conference on Artificial Intelligence (AAAI)_.
  * Luong (2016) Minh-Thang Luong. 2016.  Multi-Task Sequence To Sequence Learning.  In _Proc. International Conference on Learning Representation (ICLR)_.
  * Ma et al. (2018) Dehong Ma, Sujian Li, and Houfeng Wang. 2018.  Joint learning for targeted sentiment analysis.  In _Proc. of the Conference on Empirical Methods for Natural Language Processing (EMNLP)_.
  * Ma and Hovy (2016) Xuezhe Ma and Eduard Hovy. 2016.  End-to-end sequence labeling via bi-directional lstm-cnns-crf.  In _Proc. of the Annual Meeting of the Association Computational Linguistics (ACL)_.
  * Mishkin et al. (1983) Mortimer Mishkin, Leslie G. Ungerleider, and Kathleen A. Macko. 1983.  Object vision and spatial vision: two cortical pathways.
  * Mitchell et al. (2013) Margaret Mitchell, Jacqui Aguilar, Theresa Wilson, and Benjamin Van Durme. 2013\.  Open domain targeted sentiment.  In _Proc. of the Conference on Empirical Methods for Natural Language Processing (EMNLP)_.
  * Nothman et al. (2013) Joel Nothman, Nicky Ringland, Will Radford, Tara Murphy, and James R. Curran. 2013\.  Learning multilingual named entity recognition from wikipedia.  _Artif. Intell._ , 194:151–175.
  * Paszke et al. (2017) Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017.  Automatic differentiation in pytorch.  In _NIPS-W_.
  * Pontiki et al. (2016) Maria Pontiki, Dimitris Galanis, Haris Papageorgiou, Ion Androutsopoulos, Suresh Manandhar, AL-Smadi Mohammad, Mahmoud Al-Ayyoub, Yanyan Zhao, Bing Qin, Orphée De Clercq, et al. 2016.  Semeval-2016 task 5: Aspect based sentiment analysis.  In _Proceedings of the 10th international workshop on semantic evaluation (SemEval-2016)_.
  * Ratinov and Roth (2009) L. Ratinov and D. Roth. 2009.  Design challenges and misconceptions in named entity recognition.  In _Proc. of the Annual Conference on Computational Natural Language Learning (CoNLL)_.
  * Rueckl et al. (1989) Rueckl, Cave, and Kosslyn. 1989.  Why are ”What” and ”Where” Processed by Separate Cortical Visual Systems? A Computational Investigation.  _cognitive neuroscience_.
  * Sang and F. (2002) Tjong Kim Sang and Erik F. 2002.  Introduction to the conll-2002 shared task: Language-independent named entity recognition.  In _Proc. of the Annual Conference on Computational Natural Language Learning (CoNLL)_.
  * Sang et al. (2003) Tjong Kim Sang, Erik F., and Fien De Meulder. 2003.  Introduction to the conll-2003 shared task: Language-independent named entity recognition.  In _Proc. of the Annual Conference on Computational Natural Language Learning (CoNLL)_.
  * dos Santos and Guimarães (2015) dos Santos and Guimarães. 2015.  Boosting named entity recognition with neural character embeddings.  In _Proc. of the Annual Meeting of the Association Computational Linguistics (ACL)_.
  * Srivastava et al. (2015) Rupesh Kumar Srivastava, Klaus Greff, and Jürgen Schmidhuber. 2015.  Highway Networks.  _ArXiv e-prints_.
  * Toshniwal et al. (2017) Shubham Toshniwal, Hao Tang, Liang Lu, and Karen Livescu. 2017.  Multitask learning with low-level auxiliary tasks for encoder-decoder based speech recognition.  In _INTERSPEECH_.
  * Wilson et al. (2013) Theresa Wilson, Zornitsa Kozareva, Preslav Nakov, Alan Ritter, Sara Rosenthal, and Stoyanov Veselin. 2013.  Semeval-2013 task 2: Sentiment analysis in twitter.
  * Yu et al. (2018) Licheng Yu, Zhe Lin, Xiaohui Shen, Jimei Yang, Xin Lu, Mohit Bansal, and Tamara L Berg. 2018.  Mattnet: Modular attention network for referring expression comprehension.  _arXiv_.
  * Zhang et al. (2015) Meishan Zhang, Yue Zhang, and Duy Tin Vo. 2015.  Neural networks for open domain targeted sentiment.  In _Proc. of the Conference on Empirical Methods for Natural Language Processing (EMNLP)_.
  * Zhang et al. (2017) Xiao Zhang, Yong Jiang, Hao Peng, Kewei Tu, and Dan Goldwasser. 2017.  Semi-supervised structured prediction with neural crf autoencoder.  In _Proc. of the Conference on Empirical Methods for Natural Language Processing (EMNLP)_.
  * Zhou and Xu (2015) Jie Zhou and Wei Xu. 2015.  End-to-end learning of semantic role labeling using recurrent neural networks.  In _Proc. of the Annual Meeting of the Association Computational Linguistics (ACL)_.

##  Appendix A Examples of Task Decomposition

In Figure 6, we show an example of task decomposition for standard NER.

Figure 6: An example of NER decomposition.

In Figure 7, we show another example of task decomposition for target
sentiment, in addition to the one in the main text.

Figure 7: An extra example of target sentiment decomposition.

##  Appendix B Full Experimental Results on Target Sentiment

The complete results of our experiments on the target sentiment task are
summarized in Tab. 4. Our LSTM-CRF-TI(g) model outperforms all the other
competing models in Precision, Recall and the F1 score.

System | Architecture | English | Spanish
---|---|---|---
Pre | Rec | F1 | Pre | Rec | F1
Zhang, Zhang and Vo (2015) | Pipeline | 43.71 | 37.12 | 40.06 | 45.99 | 40.57 | 43.04
Joint | 44.62 | 35.84 | 39.67 | 46.67 | 39.99 | 43.02
Collapsed | 46.32 | 32.84 | 38.36 | 47.69 | 34.53 | 40.00
Li and Lu (2017) | SS | 44.57 | 36.48 | 40.11 | 46.06 | 39.89 | 42.75
+embeddings | 47.30 | 40.36 | 43.55 | 47.14 | 41.48 | 44.13
+POS tags | 45.96 | 39.04 | 42.21 | 45.92 | 40.25 | 42.89
+semiMarkov | 44.49 | 37.93 | 40.94 | 44.12 | 40.34 | 42.14
Base Line | LSTM-CRF | 53.29 | 46.90 | 49.89 | 51.17 | 46.71 | 48.84
This work | LSTM-CRF-T | 54.21 | 48.77 | 51.34 | 51.77 | 47.37 | 49.47
LSTM-CRF-Ti | 54.58 | 49.01 | 51.64 | 52.14 | 47.56 | 49.74
LSTM-CRF-Ti(g) | 55.31 | 49.36 | 52.15 | 52.82 | 48.41 | 50.50
Table 4: Performance on the target sentiment task

##  Appendix C Experiments on Named Entity Recognition

##### NER datasets

We evaluated our models on three NER datasets, the English, Dutch and Spanish
parts of the 2002 and 2003 CoNLL shared tasks Sang and F. (2002); Sang et al.
(2003). We used the original division of training, validation and test sets.
The task is defined over four different entity types: PERSON, LOCATION,
ORGANIZATION, MISC. We used the BIOES tagging scheme during the training, and
convert them back to original tagging scheme in testing as previous studies
show that using this tagging scheme instead of BIO2 can help improve
performance Ratinov and Roth (2009); Lample et al. (2016); Ma and Hovy (2016);
Liu et al. (2018). As a result, the segmentation module had $5$ output labels,
and the entity module had $4$. The final decision task, consisted of the
Cartesian product of the segmentation set (BIES) and the entity set, plus the
“O” tag, resulting in $17$ labels.

##### Results on NER

We compared our models with the state-of-the-art systems on English666Liu et
al.’s results are different since their implementation did not convert the
predicted BIOES tags back to BIO2 during evaluation. For fair comparison, we
only report the results of the standard evaluation., Dutch and Spanish. For
Dutch and Spanish, we used cross-lingual embedding as a way to exploit lexical
information. The results are shown in Tab. 5 and Tab. 6777We thank reviewers
for pointing out a paper Agerri and Rigau (2016) obtains the new state-of-the-
art result on Dutch with comparable results on Spanish.. Our best-performing
model outperform all the competing systems.

Model | English
---|---
LSTM-CRF Lample et al. (2016) | 90.94
LSTM-CNN-CRF Ma and Hovy (2016) | 91.21
LM-LSTM-CRF Liu et al. (2018) | 91.06
LSTM-CRF-T | 90.8
LSTM-CRF-TI | 91.16
LSTM-CRF-TI(g) | 91.68
Table 5: Comparing our models with several state-of-the-art systems on the CoNLL 2003 English NER dataset. Model | Dutch | Spanish
---|---|---
Carreras et al. Carreras et al. (2002) | 77.05 | 81.39
Nothman et al. Nothman et al. (2013) | 78.60 | N/A
dos Santos and Guimarães dos Santos and Guimarães (2015) | N/A | 82.21
Gillick et al. Gillick et al. (2015) | 82.84 | 82.95
Lample et al. Lample et al. (2016) | 81.74 | 85.75
LSTM-CRF-T | 83.91 | 84.89
LSTM-CRF-TI | 84.12 | 85.28
LSTM-CRF-TI(g) | 84.51 | 85.92
Table 6: Comparing our models with recent results on the 2002 CoNLL Dutch and
Spanish NER datasets.

##  Appendix D Additional Experiments on Knowledge Integration

We conducted additional experiments on knowledge integration in the same
setting as in the main text to investigate the properties of the modules.
Figure 8 shows the results for Dutch and Spanish NER datasets, while Figure 9
shows the results for the Subjective Polarity Disambiguation Datasets using
the in-domain data.

(a) Dutch NER

(b) Spanish NER

Figure 8: Experimental results on modular knowledge integration on the Dutch
and Spanish NER datasets. Figure 9: Experimental results on modular knowledge
integration on the Subjective Polarity Disambiguation Datasets.

##  Appendix E Convergence Analysis

The proposed twofold modular infusion model (with guided gating as an option)
breaks the complex learning problem into several sub-problems and then
integrate them using joint training. The process defined by this formulation
has more parameters and requires learning multiple objectives jointly. Our
convergence analysis intends to evaluate whether the added complexity leads to
a harder learning problem (i.e., slower to converge) or whether the tasks
constrain each other and as a result can be efficiently learned.

We compare between our LSTM-CRF-TI(g) model and recent published top models on
the English NER dataset in Figure 10 and on the subjective polarity
disambiguation datasets in Figure 11. The curve compares convergence speed in
terms of learning epochs. Our LSTM-CRF-TI(g) model has a much faster
convergence rate compared to the other models.

Figure 10: Comparing convergence over the development set on the English NER
dataset. The x-axis is number of epochs and the y-axis is the F1-score. Figure
11: Comparing convergence over the development set on the subjective polarity
disambiguation datasets. The x-axis is number of epochs and the y-axis is the
F1-score.