#  CLEVR_HYP: A Challenge Dataset and Baselines for
Visual Question Answering with Hypothetical Actions over Images

Shailaja Keyur Sampat, Akshay Kumar, Yezhou Yang and Chitta Baral
Arizona State Universiy, USA
{ssampa17,akuma216,yz.yang<EMAIL_ADDRESS>$\frac{}{}$ corresponding author

###### Abstract

Most existing research on visual question answering (VQA) is limited to
information explicitly present in an image or a video. In this paper, we take
visual understanding to a higher level where systems are challenged to answer
questions that involve mentally simulating the hypothetical consequences of
performing specific actions in a given scenario. Towards that end, we
formulate a vision-language question answering task based on the CLEVR Johnson
et al. (2017a) dataset. Wethen modify the best existing VQA methods and
propose baseline solvers for this task. Finally, we motivate the development
of better vision-language models by providing insights about the capability of
diverse architectures to perform joint reasoning over image-text
modality111Dataset setup scripts and code for baselines are made available at
https://github.com/shailaja183/clevr_hyp. For additional details about the
dataset creation process, refer supplementary material..

##  1 Introduction

In 2014, Michael Jordan, in an interview Gomes (2014) said that “Deep learning
is good at certain problems like image classification and identifying objects
in the scene, but it struggles to talk about how those objects relate to each
other, or how a person/robot would interact with those objects. For example,
humans can deal with inferences about the scene: what if I sit down on that?,
what if I put something on top of something? etc. There exists a range of
problems that are far beyond the capability of today’s machines."

While this interview was six years ago, and since then there has been a lot of
progress in deep learning and its applications to visual understanding.
Additionally, a large body of visual question answering (VQA) datasets Antol
et al. (2015); Ren et al. (2015); Hudson and Manning (2019) have been compiled
and many models have been developed over them, but the above mentioned
“inferences about the scene” issue stated by Jordan remains largely
unaddressed.

In most existing VQA datasets, scene understanding is holistic and questions
are centered around information explicitly present in the image (i.e. objects,
attributes and actions). As a result, advanced object detection and scene
graph techniques have been quite successful in achieving good performance over
these datasets. However, provided an image, humans can speculate a wide range
of implicit information. For example, the purpose of various objects in a
scene, speculation about events that might have happened before, consider
numerous imaginary situations and predicting possible future outcomes,
intentions of a subject to perform particular actions, and many more.

Figure 1: Motivation for the proposed CLEVR_HYP dataset: an example
demonstrating how humans can do mental simulations and reason over resulting
scenario.

Among the above, an ability to imagine taking specific actions and simulating
probable results without actually acting or experiencing is an important
aspect of human cognition (Figure 1 gives an example of this). Thus, we
believe that having autonomous systems equipped with a similar capability will
further advance AI research. This is particularly useful for robots performing
on-demand tasks in safety-critical situations or navigating through dynamic
environments, where they imagine possible outcomes for various situations
without executing instructions directly.

Motivated by the above, we propose a challenge that attempts to bridge the gap
between state-of-the-art AI and human-level cognition. The main contributions
of this paper222Our work focuses on the capability of neural models to reason
about the effects of actions given a visual-linguistic context and not on
models that deal with intuitive physics. are as follows;

  * •

We formalize a novel question answering task with respect to a hypothetical
state of the world (in a visual form) when some action (described in a textual
form) is performed.

  * •

We create a large-scale dataset for this task, and refer it as CLEVR_HYP i.e.
VQA with hypothetical actions performed over images in CLEVR Johnson et al.
(2017a) style.

  * •

We first evaluate the direct extensions of top VQA and NLQA (Natural language
QA) solvers on this dataset. Then, we propose new baselines to solve CLEVR_HYP
and report their results.

  * •

Through analysis and ablations, we provide insights about the capability of
diverse architectures to perform joint reasoning over image-text modality.

I:

  1. 1.

TA: Paint the small green ball with cyan color.
QH: Are there equal yellow cubes on left of purple object and cyan spheres?
(A: yes)

  2. 2.

TA: Add a brown rubber cube behind the blue sphere that inherits its size from
the green object.
QH: How many things are either brown or small? (A: 6)

  3. 3.

TA: John moves the small red cylinder on the large cube that is to the right
of purple cylinder.
QH: What color is the object that is at the bottom of the small red cylinder?
(A: yellow)

Figure 2: Three examples from CLEVR_HYP dataset: given image (I), action text
(TA), question about hypothetical scenario (QH) and corresponding answer (A).
The task is to understand possible perturbations in I with respect to various
action(s) performed as described in TA. Questions test various reasoning
capabilities of a model with respect to the results of those action(s).

##  2 Related Work

In this section we situate and compare our work with related areas such as
implicit text generation/retrieval for a visual, visual question answering
(VQA) over synthetic images, question answering (QA) involving hypothetical
reasoning, and language-based manipulation in visual domains closest to
CLEVR_HYP.

#### Implicit Text Generation for a Visual:

VisualComet Park et al. (2020) and Video2Commonsense Fang et al. (2020) have
made initial attempts to derive implicit information about images/videos
contrary to traditional factual descriptions which leverage only visual
attributes. VisualComet aims to generate commonsense inferences about events
that could have happened before, events that can happen after and people’s
intents at present for each subject in a given image. They use a vision-
language transformer that takes a sequence of inputs (image, event, place,
inference) and train a model to predict inference in a language-model style.
Video2Commonsense focuses on generating video descriptions that can
incorporate commonsense facts related to intentions, effects, and implicit
attributes about actions being performed by a subject. They extract top-ranked
commonsense texts from the Atomic dataset and modify training objective to
incorporate this information.

While both involve a visual-textual component and actions, their key focus is
about generating plausible events and commonsense respectively. Whereas, our
work is related to performing certain actions and reasoning about its effect
on the overall visual scene.

#### Language-based Manipulation in Visual Domain:

Learning a mapping from natural language instructions to a sequences of
actions to be performed in a visual environment is a common task in robotics
Kanu et al. (2020); Gaddy and Klein (2019); Shridhar et al. (2020). Another
relevant task is vision-and-language navigation Anderson et al. (2018); Chen
et al. (2018); Nguyen et al. (2019), where an agent navigates in a visual
environment to find goal location by following natural language instructions.
Both above works include visuals, natural language instructions and a set of
actions that can be performed to achieve desired goals. In this way, it is
similar to our CLEVR_HYP, but in our case, models require reasoning about the
effect of actions performed rather than determining which action to perform.
Also, we frame this in a QA style evaluation rather than producing
instructions for low-level controls.

Manipulation of natural images with language is an emerging research direction
in computer vision. Teney et al. (2020) proposed a method for generating
counterfactual of VQA samples using image in-painting and masking. Also, there
are works Dong et al. (2017); Nam et al. (2018); Reed et al. (2016) which use
Generative Adversarial Networks (GANs) Goodfellow et al. (2014) for language
conditioned image generation and manipulation. However, both the above tasks
are more focused at object and attribute level manipulation rather than at
action level.

#### VQA over Synthetic Images:

While natural images-based VQA datasets reflect challenges one can encounter
in real-life situations, the requirement of costlier human annotations and
vulnerability to biases are two major drawbacks. Contrary to them, synthetic
datasets allow controlled data generation at scale while being flexible to
test specific reasoning skills.

For the above reasons, following benchmark VQA datasets have incorporated
synthetic images; COG Yang et al. (2018) and Shapes Andreas et al. (2016)
contain images with rendered 2D shapes; SHRDLU Winograd (1971), CLEVR Johnson
et al. (2017a), and CLEVR-dialog Kottur et al. (2019) have rendered scenes
with 3D objects; DVQA Kafle et al. (2018) and FigureQA Kahou et al. (2017)
have synthetically generated charts (bar chart, pie chart, dot-line etc.);
VQA-abstract Antol et al. (2015) and IQA Gordon et al. (2018) involves
question-answering over synthetically rendered clipart-style scenes and
interactive environments respectively. Our proposed dataset CLEVR_HYP uses
CLEVR Johnson et al. (2017a) style rendered scenes with 3D objects as a visual
component. It is distinct from all other synthetic VQA datasets for two key
reasons; first, integration of action domain in synthetic VQA and second, the
requirement of mental simulation in order to answer the question.

#### QA involving Hypothetical Reasoning:

In the language domain, WIQA Tandon et al. (2019) dataset tests the model’s
ability to do what-if reasoning over procedural text as a 3-way classification
(the influence between pair of events as positive, negative or no-effect). In
vision-language domains, a portion of TQA Kembhavi et al. (2017) and VCR
Zellers et al. (2019) are relevant. Questions in TQA and VCR involve
hypothetical scenarios about multi-modal science contexts and movie scenes
respectively. However, none of the above two datasets’ key focus is on the
model’s capability to imagine changes performed over the image.

As shown in Figure 3, the setting of TIWIQ (a benchmark dataset for “physical
intelligence”) Wagner et al. (2018) has some similarity with ours. It has
synthetically rendered table-top scenes, four types of actions (push, rotate,
remove and drop) being performed on an object and what-if questions.

Figure 3: Example from TIWIQ Wagner et al. (2018).

To our best knowledge, TIWIQ dataset is not publicly available. Based on our
understanding from their manuscript, we observe following important
distinction with this work. Our questions focus on the impact of actions on
the whole image, while in TIWIQ questions are about impact of actions on a
specific object in the image. Moreover, we frame CLEVR_HYP as a classification
task, contrary to TIWIQ which is a generative task. Our CLEVR_HYP dataset has
175k automatically generated image-action text-question samples which is much
larger compared to TIWIQ which has only 1020 samples and manually crafted
ground-truths.

##  3 CLEVR_HYP Task and Dataset

Figure 2 gives a glimpse of CLEVR_HYP task. We opt for synthetic dataset
creation as it allows automated and controlled data generation at scale with
minimal biases. More details are described below.

####  3 Inputs: Image(I), Action Text (TA) and Hypothetical Question (QH)

#### 1\. Image(I):

It is a given visual for our task. Each image in the dataset contains 4-10
randomly selected 3D objects rendered using Blender Blender Online Community
(2019) in CLEVR Johnson et al. (2017a) style. Objects have 4 attributes listed
in the Table 1. Additionally, these objects can be referred using 5 relative
spatial relations (left, right, in front, behind and on). We provide scene
graphs333Scene graphs and Functional Programs (for action text and question)
are not provided at the test-time. containing all ground-truth information
about a scene, that can be considered as a visual oracle for a given image.

Attr. | Possible values in CLEVR_HYP
---|---
Color | gray, blue, brown, yellow,
| red, green, purple, cyan
Shape | cylinder, sphere or cube
Size | small or big
Material | metal (shining) or rubber (matte)
Table 1: Object attributes in CLEVR_HYP scenes.

(a) Function Catalog for CLEVR_HYP, extended from CLEVR Johnson et al. (2017a)
(b) Dataset creation pipeline

Figure 4: CLEVR_HYP dataset creation process with example and function catalog
used for ground-truth answer generation. (for more details, see Appendix A.4)

#### 2\. Action Text (TA):

It is a natural language text describing various actions performed over the
current scene. The action can be one of four:

  1. (i)

Add new object(s) to the scene

  2. (ii)

Remove object(s) from the scene

  3. (iii)

Change attributes of the object(s)

  4. (iv)

Move object(s) within scene (might be in plane i.e. left/right/front/back or
out of plane i.e. move one object on top of another object444For simplicity,
we assume that any object can be put on another object regardless of its size,
material or shape.)

To generate action text, we start with manually written templates involving
the aforementioned actions. For example, action involving change in the
attribute of object(s) to a given value, we have a template of the following
kind; ‘Change the $<$A$>$ of $<$Z$><$C$><$M$><$S$>$ to $<$V$>$’. Where
$<$A$>$, $<$Z$>$, $<$C$>$,$<$M$>$,$<$S$>$,$<$V$>$ are placeholders for the
attribute, size, color, material, shape and a value of attribute respectively.
Each action text in the CLEVR_HYP is associated with a functional program
which if executed on an image’s scene graph, yields the new scene graph that
simulates the effects of actions.

Functional programs for action texts3 are built from the basic functions that
correspond to elementary action operations (right part of Figure 4a). For the
above mentioned ‘change’ attribute action template, the equivalent functional
program can be written as; ‘change_attr($<$A$>$,filter_size($<$Z$>$,filter
_color($<$C$>$, filter_material($<$M$>$filter_ shape($<$S$>$,
scene())))),$<$V$>$)’. It essentially means, first filter out the objects with
desired attributes and then update the value of their current attribute A to
value V.

#### 3\. Question about Hypothetical Situation (QH):

It is a natural language query that tests various visual reasoning abilities
after simulating the effects of actions described in TA. There are 5 possible
reasoning types similar to CLEVR;

  1. (i)

Counting objects fulfilling the condition

  2. (ii)

Verify existence of certain objects

  3. (iii)

Query attribute of a particular object

  4. (iv)

Compare attributes of two objects

  5. (v)

Integer comparison of two object sets (same, larger or smaller)

Similar to action texts, we have templates and corresponding programs for
questions. Functional programs for questions3 are executed on the image’s
updated scene graph (after incorporating effects of the action text) and
yields the ground-truth answer to the question. Functional programs for
questions are made of primitive functions shown in left part of the Figure
4a).

Paraphrasing: In order to create a challenging dataset from linguistic point
of view and to prevent models from overfitting on templated representations,
we leverage noun synonyms, object name paraphrasing and sentence-level
paraphrasing. For noun synonyms, we use a pre-defined dictionary (such as
cubeb̃lock, sphereb̃all and so on). We programmatically generate all
possibilities to refer to an object in the image (i.e. object name
paraphrasing) and randomly sample one among them. For sentence level
paraphrasing, we use Text-To-Text Transfer Transformer (T5) Raffel et al.
(2020) fine-tuned over positive samples from Quora Question Pairs (QQP)
dataset Iyer et al. (2017) for question paraphrasing. We use Fairseq Ott et
al. (2019) for action text paraphrasing which uses round-trip translation and
mixture of experts Shen et al. (2019).

Note that we keep the action text and question as separate inputs for the
purpose of simplicity and keeping our focus on building solvers that can do
mental simulation. One can create a simple template like “$<$QH$>$ if
$<$proper-noun/pronoun$>$ $<$TA$>$?" or “If $<$proper-noun/pronoun$>$
$<$TA$>$, $<$QH$>$?" if they wish to process action and question as a single
text input. For example, “How many things are the same size as the cyan
cylinder if I add a large brown rubber cube behind the blue object." or “If I
add a large brown rubber cube behind the blue object, how many things are the
same size as the cyan cylinder?". However, having them together adds further
complexity on the solver side as it first has to figure out what actions are
performed and what is the question.

By providing ground-truth object information (as a visual oracle) and machine-
readable form of questions & action texts (oracle for linguistic components).
This information can be used to develop models which can process semi-
structured representations of image/text or for the explainability purposes
(to precisely know which component of the model is failing).

#### Output:

Answer (A) to the Question (QH), which can be considered as a 27-way
classification over attributes (8 colors + 3 shapes + 2 sizes + 2 material),
numeric (0-9) and boolean (yes/no).

Dataset Partitions and Statistics: We create CLEVR_HYP dataset containing 175k
image-action text-question samples using the process mentioned in Figure 4b.
For each image, we generate 5 kinds of action texts (one for each add, remove,
move in-plane and move out-of-plane and change attribute). For each action
text type, we generate 5 questions (one for each count, exist, compare
integer, query attribute and compare attribute). Hence, we get 5*5 unique
action text-question pairs for each image, covering all actions and reasoning
types in a balanced manner as shown in Figure 5a (referred as Original
partition). However, it leads to a skewed distribution of answers as observed
from 5b. Therefore, we curate a version of the dataset (referred as Balanced
partition) consisting of 67.5k samples where all answer choices are equally-
likely as well.

(a) Distribution based on Action Text types and Question types  (b)
Distribution of Answer types

Figure 5: Visualization of distributions for actions, questions and answers in
Original_Train partition of CLEVR_HYP.

Additionally, we create two small challenge test sets (1500 image-action text-
question samples each)- 2HopActionText (2HopTA) and 2HopQuestion (2HopQH) to
test generalization capability of the trained models. In 2HopTA, we create
action text which requires model to understand two different actions being
taken on the scene. For example, ‘Add a small blue metal cylinder to the right
of large yellow cube and remove the large cylinder from the scene.’ and ’Move
the purple object on top of small red cube then change its color to cyan.’. In
2HopQH, we create questions which require model to understand logical
combinations of questions using ‘and’, ‘or’ and ‘not’. For example, ‘How many
objects are either red or cylinder?’ and ‘Are there any rubber cubes that are
not green?’.

In Table 2, we provide size of the various partitions and measure the
diversity of the dataset in various aspects. For images, we calculate average
number of objects present in the scene from the length of scene graph. For
balanced partition, the number of images are much less compared to original,
but more average number of objects per image. This is most likely due to the
need to accommodate integers 4-9 more frequently as ground-truth answers. For
textual components, we show average lengths (number of tokens separated by
whitespaces) and count unique utterances as a measure of diversity. The
original partition of the resulting dataset has 80% and 83% unique action text
and questions respectively. For balanced partition, length and unique
utterances for action text are nearly same as the original partition but for
questions, it decreases. Questions in the original partition have been
observed to enforce more strict and specific object references (such as small
red metal cubes) compared to balanced partition (small cubes, red metal
objects etc.), reducing the average length and uniqueness. It is intuitive for
2Hop partitions to have higher average length and uniqueness for $T_{A}$ and
$Q_{H}$ respectively. This shows that despite having created this dataset from
templates and rendered images with a limited set of attributes, it is still
fairly challenging.

Split | #I |  | Avg.
---
#Obj
#TA |  | Unique
---
#TA
| Avg.
---
$T_{A}$ Len.
#QH |  | Unique
---
#QH
| Avg.
---
QH Len.
Original_Train | 5k | 6.4 | 25k | 20.7k | 12.8 | 125k | 103.7k | 22.6
Original_Val | 1k | 6.7 | 5k | 3.8k | 12.8 | 25k | 20.9k | 23.1
Original_Test | 1k | 6.4 | 5k | 3.6k | 12.6 | 25k | 20.7k | 22.8
Balanced_Train | 5k | 7.6 | 25k | 21.1k | 12.8 | 67.5k | 58.2k | 20.3
Balanced_Val | 1k | 7.6 | 5k | 3.9k | 12.7 | 13.5k | 11.5k | 20.7
Balanced_Test | 1k | 7.5 | 5k | 3.7k | 12.6 | 13.5k | 11.4k | 20.4
2Hop$T_{A}$_Test | 1k | 6.4 | 3k | 2.6k | 18.6 | 15k | 12.5k | 22.8
2Hop$Q_{H}$_Test | 1k | 6.4 | 3k | 2.2k | 12.6 | 15k | 13.7k | 29.3
Table 2: CLEVR_HYP dataset splits and statistics (# represents number of, k
represents thousand).

##  4 Models that we experiment with

Models trying to tackle CLEVR_HYP dataset have to address four key challenges;

  1. (i)

understand hypothetical actions and questions in complex natural language,

  2. (ii)

correctly disambiguate the objects of interest and obtain the structured
representation (i.e. scene graphs or functional programs) of various
modalities if required by the solver,

  3. (iii)

understand the dynamics of the world based on the various actions performed
over it,

  4. (iv)

perform various kind of reasoning to answer the question.

###  4.1 Random

The QA task in CLEVR_HYP dataset can be considered as a 27-class
classification problem. Each answer choice is likely to be picked with a
probability of 1/27. Therefore, the performance of the random baseline is
3.7%.

###  4.2 Human Performance

We performed human evaluation with respect to 500 samples from the CLEVR_HYP
dataset. Accuracy of human evaluations on original test, 2Hop$A_{T}$ and
2Hop$Q_{H}$ are 98.4%, 96.2% and 96.6% respectively.

###  4.3 Transformer Architectures

Pre-trained transformer-based architectures have been observed Li et al.
(2020) to capture a rich hierarchy of language-structures (text-only models)
and effectively map entities/words with corresponding image regions (vision-
language models). We experiment with various transformer-based models to
understand their capability to understand the effects of actions on a visual
domain.

#### Baseline 1- Machine Comprehension using RoBERTa:

To evaluate the hypothetical VQA task through the text-only model, we convert
images into the templated text using scene graphs. The templated text contains
two kind of sentences; one describing properties of the objects i.e. “There is
a $<$Z$>$ $<$C$>$ $<$M$>$ $<$S$>$", the other one describing the relative
spatial location i.e. “The $<$Z$>$ $<$C$>$ $<$M$>$ $<$S$>$ is $<$R$>$ the
$<$Z1$>$ $<$C1$>$ $<$M1$>$ $<$S1$>$". For example, “There is a small green
metal cube." and “The large yellow rubber sphere is to the left of the small
green metal cube". Then we concatenate templated text with the action text to
create a reading comprehension passage. We use state-of-the-art machine
comprehension baseline RoBERTa Liu et al. (2019) finetuned on the RACE dataset
Lai et al. (2017)555architecture=roberta large, epochs=5, learning
rate=$1\mathrm{e}{-05}$, batch size=2, update frequency=2, dropout=0.1,
optimizer=adam with eps=$1\mathrm{e}{-06}$.. Finally, we predict an answer to
the question using this reading comprehension passage.

#### Baseline 2- Visual Question Answering using LXMERT

Proposed by Tan and Bansal (2019), LXMERT is one of the best transformer based
pre-trainable visual-linguistic representations which supports VQA as a
downstream task. Typical VQA systems take an image and a language input.
Therefore, to evaluate CLEVR_HYP in VQA style, we concatenate action text and
question to form a single text input. Since LXMERT is pre-trained on the
natural images, we finetune it over CLEVR_HYP dataset666epochs=4, learning
rate=$5\mathrm{e}{-05}$, batch size=8 and then use it to predict answer.

Nomenclature I: Image, SG: Scene Graph, TT: Templated Text, $T_{A}$: Action
Text, $Q_{H}$: Hypothetical Question, A: Answer, FP: Functional Program, ’:
Updated Modality

Baseline 1:

${I}$${SG}$${TT+T_{A}}$${RoBERTa_{RACE}}$${A}$${\qquad Q_{H}}$ Baseline 3:

${I}$${I^{\prime}}$${LXMERT_{CLEVR}}$${A}$${P}$${FP}$${Q}$ Baseline 2:

${\qquad I}$${LXMERT_{CLEVR\\_HYP}}$${A}$${T_{A}+Q_{H}}$ Baseline 4:

${I}$${SG}$${SG^{\prime}}$${\longrightarrow}$${Symbolic}$${A}$${P}$${FP}$${Q}$${FP}$

Figure 6: Graphical visualization of baseline models over CLEVR_HYP described
above.

###  4.4 Systematically incorporating effects of actions into neural models

#### Baseline 3- Text-editing Image Baseline:

In this method, we break-down the QA task with mental simulation in two parts;
first, learn to generate an updated image (such that it has incorporated the
effects of actions) and then perform visual question answering with respect to
the updated image. We use the idea from Text Image Residual Gating proposed in
Vo et al. (2019) to implement the first part. However there are two important
distinctions; Their focus is on the retrieval from the given database. We
modify their objective and develop text-adaptive encoder-decoder with residual
connections to generate new image. Also, editing instructions in their CSS
dataset Vo et al. (2019) were quite simple. For example, ‘add red cube’ and
‘remove yellow sphere’. In this case, one can add the red cube anywhere in the
scene. We modify their architecture to precisely place objects to their
relative spatial references (on left/right/front/ behind). Once we get the
updated image, we feed it to the LXMERT Tan and Bansal (2019) finetuned over
the CLEVR Johnson et al. (2017a) dataset along with the question and predict
the answer.

#### Baseline 4- Scene Graph Update Model:

Instead of directly manipulating images, in this method, we leverage image
scene graphs to convert image-editing problem into graph-editing problem,
conditioned on the action text. This is an emerging research direction to deal
with changes in the visual modality over time or with new sources of
information, as observed from recent parallel works Chen et al. (2020); He et
al. (2020).

We first use Mask R-CNN He et al. (2017) to get the segmentation mask of the
objects and predict attributes (color, material, size, and shape) with an
acceptance threshold of 0.9. Segmentation mask of each object along with
original image is then passed through ResNet-34 He et al. (2016) to extract
precise 3D coordinates of the object. We get the structured scene graph for
the image. Then we use seq2seq with attention model originally proposed in
Johnson et al. (2017b) to generate functional programs (FP) for action text
and question. The execution engine executes programs on scene graph,
implemented as a neural module network Andreas et al. (2017) to update the
scene representation and answer questions.

We learn to update scene graphs according to functional program for the action
text using reinforcement learning777finetuning learning
rate=$1\mathrm{e}{-05}$, 1M iterations with early stopping, batch size=32. The
reward function is associated with our ground-truth program executor and
generates reward if prediction exactly matches with ground-truth execution.
Once we get the updated scene representation, we use neural-symbolic
model888supervised pretraining learning rate=$7\mathrm{e}{-04}$, num
iterations=20k, batch size=32 and then finetuning $1\mathrm{e}{-05}$, at most
2M iterations with early stopping, batch size=32 proposed by Yi et al. (2018)
to obtain the final answer. It is notable that Yi et al. (2018) achieved near-
perfect performance on the CLEVR QA task in addition to being fully
explainable.

##  5 Baseline Results

In this section, we benchmark models described above on the CLEVR_HYP. The
dataset is formulated as a classification task with exactly one correct
answer, so we use standard accuracy as evaluation metric. We then analyze
their performance according to question and action types.

Overall Baseline Performance for Various Test Sets of CLEVR_HYP
---
Original Test | Balanced Test | 2HopTA Test | 2HopQH Test
BL1 | BL2 | BL3 | BL4 | BL1 | BL2 | BL3 | BL4 | BL1 | BL2 | BL3 | BL4 | BL1 | BL2 | BL3 | BL4
57.2 | 63.9 | 64.7 | 70.5 | 55.3 | 65.2 | 69.5 | 68.6 | 53.3 | 49.2 | 55.6 | 64.4 | 55.2 | 52.9 | 58.7 | 66.5

$\frac{}{}$

Performance break-down by Action Types and Reasoning Types for Baseline 3 and
4
---
| Original Test |  |  | 2Hop$A_{T}$ Test |  |  | Original Test |  |  | 2Hop$Q_{H}$ Test
| BL3 | BL4 |  |  | BL3 | BL4 |  |  | BL3 | BL4 |  |  | BL3 | BL4
Add | 58.2 | 65.9 |  | Add+Remove | 53.6 | 63.2 |  | Count | 60.2 | 74.3 |  | And | 59.2 | 67.1
Remove | 89.4 | 88.6 |  | Add+Change | 55.4 | 64.7 |  | Exist | 69.6 | 72.6 |  | Or | 58.8 | 67.4
Change | 88.7 | 91.2 |  | Add+Move | 49.7 | 57.5 |  | CompInt | 56.7 | 67.3 |  | Not | 58.1 | 65.0
Move(in-plane) | 61.5 | 69.4 |  | Remove+Change | 82.1 | 85.5 |  | CompAttr | 68.7 | 70.5 |  |  |  |
Move(on) | 53.3 | 66.1 |  | Remove+Move | 52.6 | 66.4 |  | QueryAttr | 65.4 | 68.1 |  |  |  |
|  |  |  | Change+Move | 53.8 | 63.3 |  |  |  |  |  |  |  |

Table 3: Baseline performance over CLEVR_HYP (BLx represents one of the four
Baselines described above).

Quantitative results from above experiments can be visualized in top part of
the Table 3. Among the methods described above, the scene graph update model
has the best overall performance 70.5% on original test data. Text-editing
model is best over balanced set, but observed to have the poor generalization
capability when two actions or reasoning capabilities have to be performed.
CLEVR_HYP requires models to reason about effect of hypothetical actions taken
over images. LXMERT is not directly trained for this objective therefore, it
struggles to do well on this task. The reason behind the poor performance of
text-only baseline is due to its limitation to incorporate detailed spatial
locations into the templates that we use to convert image into a machine
comprehension passage.

Two of our models (scene graph update and text-editing image) are transparent
to visualize intermediate changes in the scene after performing actions. We
analyse their ability to understand actions and make appropriate changes as
shown in below part of Table 3. For the scene graph method, we compare the
ground-truth functional program with the generated program and measure their
exact-match accuracy. For the text-editing image method, we generate scene
graphs for both images (original image and image after text-editing) and
compare them. For attributes, we do exact-match, whereas for location
information we consider matching only on the basis of relative spatial
location.

Both scene graph and text-editing models do quite well on ‘remove’ and
‘change’ actions whereas struggle when new objects are added or existing
objects are moved around. The observation is consistent when multiple actions
are combined. Therefore, actions remove+change can be performed with maximum
accuracy whereas other combinations of actions accomplish relatively lower
performance. It leads to the conclusion that understanding the effect of
different actions are of varied complexity. Most models demonstrate better
performance over counting, existence and attribute query type of questions
than comparison questions. The scene graph update and text-editing methods
show a performance drop of 6.1% and 9.1% respectively when multiple actions
are performed on the scene. However, there is less of a performance gap for
models on 2HopQH compared to the test set, suggesting that models are able to
better generalize with respect to multiple reasoning skills than complex
actions.

##  6 Conclusion

We introduce CLEVR_HYP, a dataset to evaluate the ability of VQA systems after
hypothetical actions are performed over the given image. We create this
dataset by extending the data generation framework of CLEVR Johnson et al.
(2017a) that uses synthetically rendered images and templates for reasoning
questions. Our dataset is challenging because rather than asking to reason
about objects already present in the image, it asks about what would happen in
an alternative world where changes have occurred. We provide ground-truth
representations for images, hypothetical actions and questions to facilitate
the development of models that systematically learn to reason about underlying
process. We create several baseline models to benchmark CLEVR_HYP and report
their results. Our analysis shows that the models are able to perform
reasonably well (70.5%) on the limited number of actions and reasoning types,
but struggle with complex scenarios. While neural models have achieved almost
perfect performance on CLEVR and considering human performance as upperbound
(98%), there is a lot of room for improvement on CLEVR_HYP. Our future work
would include relaxing constraints by allowing a larger variety of actions,
attributes and reasoning types. By extending this approach further for natural
images, we aim to contribute in the development of better vision+language
models.

## Acknowledgements

We are thankful to the anonymous reviewers for the constructive feedback. This
work is partially supported by the grants NSF 1816039, DARPA W911NF2020006 and
ONR N00014-20-1-2332.

## References

  * Anderson et al. (2018) Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian Reid, Stephen Gould, and Anton van den Hengel. 2018.  Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments.  In _Proceedings of the IEEE CVPR_.
  * Andreas et al. (2016) Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. 2016.  Neural module networks.  In _Proceedings of IEEE conference on CVPR_ , pages 39–48.
  * Andreas et al. (2017) Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. 2017.  Neural module networks.
  * Antol et al. (2015) Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C. Lawrence Zitnick, and Devi Parikh. 2015.  VQA: Visual Question Answering.  In _ICCV_.
  * Blender Online Community (2019) Blender Online Community. 2019.  _Blender - a 3D modelling and rendering package_.  Blender Foundation, Blender Institute, Amsterdam.
  * Chen et al. (2018) Howard Chen, Alane Suhr, Dipendra Misra, Noah Snavely, and Yoav Artzi. 2018.  Touchdown: Natural language navigation and spatial reasoning in visual street environments.
  * Chen et al. (2020) Lichang Chen, Guosheng Lin, Shijie Wang, and Qingyao Wu. 2020.  Graph edit distance reward: Learning to edit scene graph.  _arXiv preprint arXiv:2008.06651_.
  * Dong et al. (2017) Hao Dong, Simiao Yu, Chao Wu, and Yike Guo. 2017.  Semantic image synthesis via adversarial learning.  In _Proceedings of the IEEE ICCV_ , pages 5706–5714.
  * Fang et al. (2020) Zhiyuan Fang, Tejas Gokhale, Pratyay Banerjee, Chitta Baral, and Yezhou Yang. 2020\.  Video2commonsense: Generating commonsense descriptions to enrich video captioning.
  * Gaddy and Klein (2019) David Gaddy and Dan Klein. 2019.  Pre-learning environment representations for data-efficient neural instruction following.
  * Gomes (2014) Lee Gomes. 2014.  Machine-learning maestro michael jordan on the delusions of big data and other huge engineering efforts.
  * Goodfellow et al. (2014) Ian J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014.  Generative adversarial networks.  _arXiv preprint arXiv:1406.2661_ , 4(5):6.
  * Gordon et al. (2018) Daniel Gordon, Aniruddha Kembhavi, Mohammad Rastegari, Joseph Redmon, Dieter Fox, and Ali Farhadi. 2018.  Iqa: Visual question answering in interactive environments.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 4089–4098.
  * He et al. (2017) Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. 2017.  Mask r-cnn.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2961–2969.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016.  Deep residual learning for image recognition.  In _Proceedings of IEEE conference on computer vision and pattern recognition_ , pages 770–778.
  * He et al. (2020) Xuanli He, Quan Hung Tran, Gholamreza Haffari, Walter Chang, Trung Bui, Zhe Lin, Franck Dernoncourt, and Nhan Dam. 2020.  Scene graph modification based on natural language commands.
  * Hudson and Manning (2019) Drew A. Hudson and Christopher D. Manning. 2019.  Gqa: A new dataset for real-world visual reasoning and compositional question answering.
  * Iyer et al. (2017) Shankar Iyer, Nikhil Dandekar, and Kornél Csernai. 2017.  First quora dataset release: Question pairs.  _data. quora. com_.
  * Johnson et al. (2017a) Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. 2017a.  Clevr: A diagnostic dataset for compositional language and elementary visual reasoning.  In _Proceedings of IEEE Conference on Computer Vision and Pattern Recognition_ , pages 2901–2910.
  * Johnson et al. (2017b) Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Judy Hoffman, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. 2017b.  Inferring and executing programs for visual reasoning.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 2989–2998.
  * Kafle et al. (2018) Kushal Kafle, Brian Price, Scott Cohen, and Christopher Kanan. 2018.  Dvqa: Understanding data visualizations via question answering.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5648–5656.
  * Kahou et al. (2017) Samira Ebrahimi Kahou, Vincent Michalski, Adam Atkinson, Ákos Kádár, Adam Trischler, and Yoshua Bengio. 2017.  Figureqa: An annotated figure dataset for visual reasoning.  _arXiv preprint arXiv:1710.07300_.
  * Kanu et al. (2020) John Kanu, Eadom Dessalene, Xiaomin Lin, Cornelia Fermuller, and Yiannis Aloimonos. 2020.  Following instructions by imagining and reaching visual goals.  _arXiv preprint arXiv:2001.09373_.
  * Kembhavi et al. (2017) Aniruddha Kembhavi, Minjoon Seo, Dustin Schwenk, Jonghyun Choi, Ali Farhadi, and Hannaneh Hajishirzi. 2017.  Are you smarter than a sixth grader? textbook question answering for multimodal machine comprehension.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 4999–5007.
  * Kottur et al. (2019) Satwik Kottur, José M. F. Moura, Devi Parikh, Dhruv Batra, and Marcus Rohrbach. 2019.  Clevr-dialog: A diagnostic dataset for multi-round reasoning in visual dialog.
  * Lai et al. (2017) Guokun Lai, Qizhe Xie, Hanxiao Liu, Yiming Yang, and Eduard Hovy. 2017.  Race: Large-scale reading comprehension dataset from examinations.  _arXiv preprint arXiv:1704.04683_.
  * Li et al. (2020) Liunian Harold Li, Mark Yatskar, Da Yin, Cho-Jui Hsieh, and Kai-Wei Chang. 2020\.  What does BERT with vision look at? In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 5265–5275, Online. Association for Computational Linguistics.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Nam et al. (2018) Seonghyeon Nam, Yunji Kim, and Seon Joo Kim. 2018.  Text-adaptive generative adversarial networks: Manipulating images with natural language.  In _Advances in NIPS_ , pages 42–51.
  * Nguyen et al. (2019) Khanh Nguyen, Debadeepta Dey, Chris Brockett, and Bill Dolan. 2019.  Vision-based navigation with language-based assistance via imitation learning with indirect intervention.  In _The IEEE Conference on Computer Vision and Pattern Recognition_.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  fairseq: A fast, extensible toolkit for sequence modeling.  In _Proceedings of NAACL-HLT 2019: Demonstrations_.
  * Park et al. (2020) Jae Sung Park, Chandra Bhagavatula, Roozbeh Mottaghi, Ali Farhadi, and Yejin Choi. 2020.  Visualcomet: Reasoning about the dynamic context of a still image.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Reed et al. (2016) Scott Reed, Zeynep Akata, Xinchen Yan, Lajanugen Logeswaran, Bernt Schiele, and Honglak Lee. 2016.  Generative adversarial text to image synthesis.  _arXiv preprint arXiv:1605.05396_.
  * Ren et al. (2015) Mengye Ren, Ryan Kiros, and Richard Zemel. 2015.  Exploring models and data for image question answering.
  * Shen et al. (2019) Tianxiao Shen, Myle Ott, Michael Auli, and Marc’Aurelio Ranzato. 2019.  Mixture models for diverse machine translation: Tricks of the trade.  _International Conference on Machine Learning_.
  * Shridhar et al. (2020) Mohit Shridhar, Jesse Thomason, Daniel Gordon, Yonatan Bisk, Winson Han, Roozbeh Mottaghi, Luke Zettlemoyer, and Dieter Fox. 2020.  ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks.  In _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Tan and Bansal (2019) Hao Tan and Mohit Bansal. 2019.  Lxmert: Learning cross-modality encoder representations from transformers.  _arXiv preprint arXiv:1908.07490_.
  * Tandon et al. (2019) Niket Tandon, Bhavana Dalvi Mishra, Keisuke Sakaguchi, Antoine Bosselut, and Peter Clark. 2019.  Wiqa: A dataset for "what if…" reasoning over procedural text.
  * Teney et al. (2020) Damien Teney, Ehsan Abbasnedjad, and Anton van den Hengel. 2020.  Learning what makes a difference from counterfactual examples and gradient supervision.  _arXiv preprint arXiv:2004.09034_.
  * Vo et al. (2019) Nam Vo, Lu Jiang, Chen Sun, Kevin Murphy, Li-Jia Li, Li Fei-Fei, and James Hays. 2019.  Composing text and image for image retrieval-an empirical odyssey.  In _CVPR_.
  * Wagner et al. (2018) Misha Wagner, Hector Basevi, Rakshith Shetty, Wenbin Li, Mateusz Malinowski, Mario Fritz, and Ales Leonardis. 2018.  Answering visual what-if questions: From actions to predicted scene descriptions.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 0–0.
  * Winograd (1971) Terry Winograd. 1971.  Procedures as a representation for data in a computer program for understanding natural language.  Technical report, MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC.
  * Yang et al. (2018) Guangyu Robert Yang, Igor Ganichev, Xiao-Jing Wang, Jonathon Shlens, and David Sussillo. 2018.  A dataset and architecture for visual reasoning with a working memory.
  * Yi et al. (2018) Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Josh Tenenbaum. 2018.  Neural-symbolic vqa: Disentangling reasoning from vision and language understanding.  In _Advances in NIPS_ , pages 1031–1042.
  * Zellers et al. (2019) Rowan Zellers, Yonatan Bisk, Ali Farhadi, and Yejin Choi. 2019.  From recognition to cognition: Visual commonsense reasoning.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 6720–6731.

##  Appendix A Appendix

###  A.1 Relation of CLEVR_HYP dataset with real-world situations

Teaching methodologies leverage our ability to mentally simulate scenarios
along with the metaphors to aid understanding about new concepts. In other
words, to explain unfamiliar concepts, we often reference familiar concepts
and provide additional clues to establish mapping between them. This way, a
person can create a mental simulation about unfamiliar concept and aid basic
understanding about it.

For example, we want to explain a person how a ‘zebra’ looks like, who has
previously seen a ‘horse’, we can do so using example in Figure 7a. This
naturally follows for more complex concepts. Let say, one wants to describe
the structure of an atom to someone, he might use the analogy of a planetary
system, where the components (planets $\sim$ electrons) circulate around a
central entity (sun $\sim$ nucleus). One more such example is provided in
Figure 7b.

(a) learning the concept ‘zebra’ from the ‘horse’

(b) learning about ‘animal cell’ by comparison with ‘plant cell’

Figure 7: Extension of CLEVR_HYP for more complex real-world scenarios.

For humans, learning new concepts and performing mental simulations is
omnipresent in day-to-day life. Therefore, CLEVR_HYP dataset is very much
grounded in the real world. Models developed on this dataset can serve a broad
range of applications, particularly the ones where possible outcomes have to
be predicted without actually executing the actions. For example, robots
performing on-demand tasks in safety-critical situations or self-driving
vehicles. In addition, these models can be an important component for other
vision and language tasks such as automatic expansion of existing knowledge
bases, zero shot learning and spatio-temporal visual reasoning.

###  A.2 Rejecting Bad Samples in CLEVR_HYP

Automated methods of question generation sometimes create invalid items,
classified as ‘ill-posed’ or ‘degenerate’ by CLEVR Johnson et al. (2017a)
dataset generation framework. They consider question “What color is the cube
to the right of the sphere?" as ill-posed if there were many cubes right of
the sphere, or degenerate if there is only one cube in the scene and reference
to the sphere becomes unnecessary. In addition to this, we take one more step
of quality control in order to prevent ordinary VQA models from succeeding
over CLEVR_HYP without proper reasoning.

In CLEVR_HYP, one has to perform actions described in T over image I and then
answer question Q with respect to the updated scenario. Therefore, to prevent
ad-hoc models from exploiting biases in CLEVR_HYP, we pose the requirement
that a question must have different ground-truth answers for CLEVR_HYP and
image-only model. One such example is shown in Figure 8. For image (I), Q1
leads to different answers for CLEVR and CLEVR_HYP, making sure that one needs
to correctly incorporate the effect of T. Q2 is invalid for a given image-
action text pair in the CLEVR_HYP as one can answer it correctly without
understanding T.

###  A.3 More Examples from CLEVR_HYP

Beyond Figure 10, all rest of the pages show more examples from our CLEVR_HYP
dataset. Each dataset item has 4 main components- image(I), action text (TA),
question about the hypothetical states (QH) and answer (A). We classify
samples based on what actions are taken over the image and the kind of
reasoning is required to answer questions.

I:

Image-only model:
Q1: Is there any large sphere? A: Yes
Q2: Is there any large cube? A: Yes

CLEVR_HYP:
T: Remove all matte objects from the scene.

I’:

Q1: Is there any large sphere? A: No ✓
Q2: Is there any large cube? A: Yes ✗

Figure 8: Validity of questions in CLEVR_HYP

###  A.4 Function Catalog

As described in Section 3 and shown in Figure 4, each action text and question
is associated with a functional program. We provide more details about these
basic functions in Table 4 that was used to generate ground-truth answers for
our dataset. Each function has input and output arguments, which are limited
to following data types:

  * •

object: a single object in the scene

  * •

objset: a set of zero or more objects in scene

  * •

integer: an integer in [0,10]

  * •

boolean: ‘yes’ or ‘no’

  * •

values: possible attribute values mentioned in Table 1

###  A.5 Paraphrasing

In order to create a challenging dataset from the linguistic point of view and
to prevent models from overfitting on templated representations, we leverage
word synonyms and paraphrasing methods. This section provides more details
about paraphrasing methods used in our dataset.

Function | Input Type → Output Type | Return Value
---|---|---
scene |  $\phi$ → objset | Set of all objects in the scene
unique |  objset → object |  | Object if objset is singleton; else raise exception
---
(to verify whether the input is unique or not)
relate |  object × relation → objset | Objects satisfying given spatial relation for input object
count |  objset → integer | Size of the input set
exist |  objset → boolean | ‘Yes’ if the input set is non-empty and ‘No’ otherwise
filter_size |  objset × size → objset | Subset of input objects that match the given size
filter_color |  objset × color → objset | Subset of input objects that match the given color
filter_material |  objset × material → objset | Subset of input objects that match the given material
filter_shape |  objset × shape → objset | Subset of input objects that match the given shape
query_size |  object → size | Size of the input object
query_color |  object → color | Color of the input object
query_material |  object → material | Material of the input object
query_shape |  object → shape | Shape of the input object
same_size |  object → objset | Set of objects that have same size as input (excluded)
same_color |  object → objset | Set of objects that have same color as input (excluded)
same_material |  object → objset | Set of objects that have same material as input(excluded)
same_shape |  object → objset | Set of objects that have same shape as input (excluded)
equal_size |  size × size → boolean | ‘Yes’ if inputs are equal, ‘No’ otherwise
equal_color |  color × color → boolean | ‘Yes’ if inputs are equal, ‘No’ otherwise
equal_material |  material × material → boolean | ‘Yes’ if inputs are equal, ‘No’ otherwise
equal_shape |  shape × shape → boolean | ‘Yes’ if inputs are equal, ‘No’ otherwise
equal_integer |  integer × integer → boolean | ‘Yes’ if two integer inputs are equal, ‘No’ otherwise
less_than |  integer × integer → boolean | ‘Yes’ if first integer is smaller than second, else ‘No’
greater_than |  integer × integer → boolean | ‘Yes’ if first integer is larger than second, else ‘No’
and |  objset × objset → objset | Intersection of the two input sets
or |  objset × objset → objset | Union of the two input sets.
not_size |  object → objset | Subset of input objects that do not match given size
not_color |  object → objset | Subset of input objects that do not match given color
not_material |  object → objset | Subset of input objects that do not match given material
not_shape |  object → objset | Subset of input objects that do not match given shape
add |  objset × object → objset | Input set with input object added to it
remove |  objset × object → objset | Input set with input object removed from it
add_rel |  |  objset × object x object
---
x relation → objset
| Input set with new object (first input) added at the
---
given spatial location relative to second input object
remove_rel |  |  objset × object x object
---
x relation → objset
| Input set with object (first input) removed from the
---
given spatial location relative to second input object
change_loc |  |  objset × object x object
---
x relation → objset
| Input set with object (first input) location changed to a
---
given spatial location relative to second input object
change_size |  objset × size → objset | Input set with size updated to the given value
change_color |  objset × color → objset | Input set with color updated to the given value
change_material |  objset × material → objset | Input set with material updated to the given value
change_shape |  objset × shape → objset | Input set with shape updated to the given value
Table 4: (upper) Original function catalog for CLEVR proposed in Johnson et
al. (2017a), which we reuse in our data creation process (lower) New functions
added to the function catalog for the CLEVR_HYP dataset.

#### small gray metal cube:

[small gray object, small metal object, small cube, small gray cube, small
gray metal object, gray metal cube, small gray metal cube]

#### large brown rubber cylinder:

[brown object, large brown object, large cylinder, brown rubber object, brown
cylinder, large brown rubber object, large brown cylinder, brown rubber
cylinder, large brown rubber cylinder]

Figure 9: Object paraphrases for 2 objects in the scene

#### Object Name Paraphrasing

There can be many ways an object can be referred in the scene. For example,
‘large purple metal sphere’ in image below can also be referred to as ‘sphere’
as there is no other sphere present in the image. In order to make templates
more challenging, we use these alternative expressions to refer objects in the
action text or question. We wrote a python script that takes scene graph of
the image and generates all possible names one can uniquely refer for each
object in the scene. When paraphrasing is performed, one of the generated
names is randomly chosen and replaced. Figure 9 demonstrates list of all
possible name variants for two objects in the given image.

#### Synonyms for Paraphrasing

We use word synonyms file provided with CLEVR dataset generation code.

#### Sentence/Question Level Paraphrasing

For action text paraphrasing, we use Fairseq Ott et al. (2019) based
paraphrasing tool which uses round-trip translation and mixture of experts
Shen et al. (2019). Specifically, we use pre-trained round-trip models (En-Fr
and Fr-En) and choose top-5 paraphrases manually for each template. For
question paraphrasing, the quality of round-trip translation and mixture of
experts was not satisfactory. Therefore, we use Text-To-Text Transfer
Transformer (T5) Raffel et al. (2020) fine-tuned over positive samples from
Quora Question Pairs (QQP) dataset Iyer et al. (2017) and choose top-5 per
template.

###  A.6 Computational Resources

All of our experiments are performed over Tesla V100-PCIE-16GB GPU.

[1]

TA: A small red sphere is added to the right of the green object.

QH: There is a gray cylinder; how many spheres are to the right of it?

A: 2

Classification: Add action, Counting question

Split: val

[2]

TA: All the purple objects become metallic.

QH: What number of shiny things are to the left of the small yellow sphere?

A: 3

Classification: Change action, Counting question

Split: val

[3]

TA: John puts a large red metal cube behind the blue rubber cylinder.

QH: There is a small green cylinder that is in front of the gray thing; are
there any large red things behind it?

A: Yes

Classification: Add action, Existence question

Split: val

[4]

TA: Remove all matte objects from the scene.

QH: Is there any large sphere?

A: No

Classification: Remove action, Existence question

Split: val

[5]

TA: The large cylinder behind the red shiny sphere is moved in front of the
green sphere.

QH: Is there a purple object that is to the right of the big yellow cube that
is behind the cyan rubber sphere?

A: No

Classification: Move (in-plane) action, Existence question

Split: val

[6]

TA: A small green metal sphere is added behind the small red cube.

QH: What color is the large cylinder that is to the right of the green object?

A: Brown

Classification: Add action, Query Attribute question

Split: val

[7]

TA: The purple cylinder behind the cube disappers from the scene.

QH: What material is the object on the left of brown metal cylinder?

A: Rubber

Classification: Remove action, Query Attribute question

Split: val

[8]

TA: There is a sphere that is to the left of the gray cylinder; it shrinks in
size.

QH: What size is the blue object?

A: Small

Classification: Change action, Query Attribute question

Split: val

[9]

TA: The brown thing is moved in front of the pink rubber cube.

QH: What shape is the object that is in front of the pink rubber cube?

A: Cylinder

Classification: Move (in-plane) action, Query Attribute question

Split: val

Figure 10: More examples from the CLEVR_HYP dataset

[10]

TA: The small red sphere is moved onto the small cube that is in front of the
gray sphere.

QH: What material is the object that is below the small metal sphere?

A: Rubber

Classification: Move (out-of-plane) action, Query Attribute question

Split: val

[11]

TA: A small yellow metal object is placed to the right of red cylinder; it
inherits its shape from the blue object.

QH: Are there any other things that have the same shape as the blue matte
object?

A: Yes

Classification: Add action, Compare Attribute question

Split: val

[12]

TA: Hide all the cylinders from the scene.

QH: Are there any other things that have the same size as the gray sphere?

A: No

Classification: Remove action, Compare Attribute question

Split: val

[13]

TA: The small block is displaced and put on the left of the blue cube.

QH: Is there anything else on the right of the cyan sphere that has the same
color as the large metal cylinder?

A: No

Classification: Move (in-plane) action, Compare Attribute question

Split: val

[14]

TA: Jill places the small cube on the large cube that is to the left of cyan
cylinder.

QH: There is an object below the brown cube; does it have the same shape as
the green object?

A: Yes

Classification: Move (out-of-plane) action, Compare Attribute question

Split: val

[15]

TA: A small brown cube is added to the scene which is made of same material as
the golden block.

QH: Are there an equal number of green objects and brown cubes?

A: Yes

Classification: Add action, Compare Integer question

Split: val

[16]

TA: The tiny cylinder is withdrawn from the scene.

QH: Is the number of rubber objects greater than the number of shiny objects?

A: No

Classification: Remove action, Compare Integer question

Split: val

[17]

TA: All small metal spheres are transformed into cylinders.

QH: Are there fewer brown objects that are to the right of the red sphere than
the cylinders?

A: Yes

Classification: Change action, Compare Integer question

Split: val

[18]

TA: The sphere is placed in front of the large blue cube that is to the left
of the yellow shiny object.

QH: Are there an equal number of gray things to the right of the brown rubber
cube and cylinders?

A: No

Classification: Move (in-plane) action, Compare Integer question

Split: val

Figure 11: More examples from the CLEVR_HYP dataset


# Linear and Nonlinear MMSE Estimation in One-Bit Quantized Systems under a
Gaussian Mixture Prior

Benedikt Fesl, and Wolfgang Utschick  The authors are with Chair of Signal
Processing, Technical University of Munich, Munich, Germany (e-mail:
<EMAIL_ADDRESS>utschick@tum.de).

###### Abstract

We present new fundamental results for the mean square error (MSE)-optimal
conditional mean estimator (CME) in one-bit quantized systems for a Gaussian
mixture model (GMM) distributed signal of interest, possibly corrupted by
additive white Gaussian noise (AWGN). We first derive novel closed-form
analytic expressions for the Bussgang estimator, the well-known linear minimum
mean square error (MMSE) estimator in quantized systems. Afterward, closed-
form analytic expressions for the CME in special cases are presented,
revealing that the optimal estimator is linear in the one-bit quantized
observation, opposite to higher resolution cases. Through a comparison to the
recently studied Gaussian case, we establish a novel MSE inequality and show
that that the signal of interest is correlated with the auxiliary quantization
noise. We extend our analysis to multiple observation scenarios, examining the
MSE-optimal transmit sequence and conducting an asymptotic analysis, yielding
analytic expressions for the MSE and its limit. These contributions have broad
impact for the analysis and design of various signal processing applications.

###### Index Terms:

One-bit quantization, Bussgang, conditional mean estimator, mean square error,
Gaussian mixture, MMSE.

©This work has been submitted to the IEEE for possible publication. Copyright
may be transferred without notice, after which this version may no longer be
accessible.

##  I Introduction

Bayesian estimators are a cornerstone in classical estimation theory,
affecting many signal processing applications. In particular, the CME as the
optimal estimator for all Bregman loss functions, with the MSE as the most
prominent representative [1], is of great importance. This has led to the
analysis of the CME and its properties under various conditions, e.g., in an
AWGN channel [2] or with different noise models [3]. In particular, the cases
where the CME is linear are of great interest due to the practical
implications [4].

Despite its great importance in signal processing, the CME lacks theoretical
understanding in quantized systems, which, e.g., occur in the modeling of
analog-to-digital converters (ADCs), imposing a nonlinear inverse problem.
Natural fields of application are, e.g, lossy compression [5], wireless sensor
networks [6], audio coding [7], control theory [8], positioning [9], or
channel estimation [10, 11]. Recently, the CME was examined in case of one-bit
quantization in a jointly Gaussian setting [12], [13]; it was shown that the
CME is linear in the quantized observation in many special cases, although it
necessitates an elaborate numerical evaluation in general.

A viable alternative, in general, is the linear MMSE estimator, which can be
derived via the Bussgang decomposition [14, 11, 15], motivated by Bussgang’s
theorem [16], or, alternatively, the additive quantization noise model [17].
Moreover, the statistically equivalent linear model via the Bussgang
decomposition allows for theoretical system analysis, e.g., spectral
efficiency [11], capacity [18], nonideal hardware effects [19, 20], or
nonlinear system characterization [21, 22, 23]. However, similar to the
analysis of the CME, the Bussgang estimator was mainly investigated for the
case of a zero-mean Gaussian distributed signal, allowing for closed-form
solutions of the Bussgang gain [24, Sec. 9.2] and the covariance matrix of the
quantized observation via the arcsine law [25, 26].

A natural generalization of the zero-mean Gaussian case is the zero-mean GMM,
which covers a wide class of probability density functions (PDFs) that can be
reasonably approximated, especially in wireless communications [27, 28]. This
has motivated the analysis of the Bussgang gain for GMM distributed signals
[29, 30]. However, the Bussgang decomposition has not been fully investigated
for the general multivariate case for one-bit quantization. More importantly,
the linear MMSE and the CME for a GMM prior are not investigated thus far.

The contributions of this letter are as follows: We generalize the analytic
expressions for the Bussgang gain and the arcsine law from the Gaussian case
to the general GMM case, which is important for the evaluation of the linear
MMSE estimator. Afterward, we study the CME estimator in different special
cases. We derive a novel closed-form solution for the CME in the univariate
case, which turns out to be linear in the observation and thus equal to the
Bussgang estimator. This allows for finding an analytic expression of the
cross-correlation between the signal of interest and the auxiliary
quantization noise from the Bussgang decomposition, which is vanishing in both
the low and high signal-to-noise ratio (SNR) regimes or in the degenerate
Gaussian case. Furthermore, we derive a novel MSE inequality, revealing that
the GMM distribution leads to a consistently higher MSE than the Gaussian
distribution under a fixed global variance constraint.

Subsequently, we investigate a multiple observation scenario, where the MSE-
optimal observation sequence and two equivalent expressions of the CME for the
noiseless case are derived. Subsequent to finding analytic expressions of the
MSE and its limit, the MSE inequality is shown to also hold for this case. All
theoretical results are validated with numerical experiments. In addition,
more general cases are evaluated, highlighting the strong impact of stochastic
resonance.

##  II System Model

We consider the generic system equation
${\bm{R}}=Q({\bm{Y}})=Q({\bm{h}}{\bm{a}}^{\operatorname{T}}+{\bm{N}})\in\mathbb{C}^{N\times
M}$ where ${\bm{R}}=[{\bm{r}}_{1},{\bm{r}}_{2},\dots,{\bm{r}}_{M}]$ contains
$M$ quantized observations of the vector of interest
${\bm{h}}\in\mathbb{C}^{N}$ with the known vector ${\bm{a}}\in\mathbb{C}^{M}$
that fulfills the power constraint $\|{\bm{a}}\|_{2}^{2}=M$. Let the vector
${\bm{h}}\sim p({\bm{h}})$ be a zero-mean GMM random variable (RV), i.e.,

$\displaystyle
p({\bm{h}})=\sum_{k=1}^{K}p_{k}\mathcal{N}_{\mathbb{C}}({\bm{h}};{\bm{0}},{\bm{C}}_{k})$
(1)

with the global covariance matrix
${\bm{C}}_{{\bm{h}}}=\sum_{k=1}^{K}p_{k}{\bm{C}}_{k}$. Further,
${\bm{N}}=[{\bm{n}}_{1},\dots,{\bm{n}}_{M}]$ where
${\bm{n}}_{i}\sim\mathcal{N}_{\mathbb{C}}({\bm{0}},\eta^{2}\operatorname{\mathbf{I}})$
is AWGN and
$Q(\cdot)=\frac{1}{\sqrt{2}}\left(\operatorname{sign}(\Re(\cdot))+{\operatorname{j}}\operatorname{sign}(\Im(\cdot))\right)$
is the complex-valued one-bit quantization function, which is applied element-
wise to the input vector/matrix. The system model can be equivalently
described in its (column-wise) vectorized form as

${\bm{r}}=Q({\bm{y}})=Q({\bm{A}}{\bm{h}}+{\bm{n}})\in\mathbb{C}^{NM}$ (2)

with ${\bm{A}}={\bm{a}}\otimes\operatorname{\mathbf{I}}$,
${\bm{r}}=\operatorname{vec}({\bm{R}})$,
${\bm{y}}=\operatorname{vec}({\bm{Y}})$, and
${\bm{n}}=\operatorname{vec}({\bm{N}})$.

##  III The Bussgang Estimator

In the context of quantization, the linear MMSE estimator is referred to as
the Bussgang estimator [11], as it is motivated by Bussgang’s theorem [16]. In
particular, the Bussgang decomposition implies that the system (2) can be
linearized as the statistically equivalent model

$\displaystyle{\bm{r}}=Q({\bm{y}})={\bm{B}}{\bm{y}}+{\bm{q}},$ (3)

where ${\bm{B}}$ is the Bussgang gain, enforcing that ${\bm{q}}$ is
uncorrelated (but not independent) of ${\bm{y}}$. The Bussgang estimator reads
as

$\displaystyle\hat{{\bm{h}}}_{\text{LMMSE}}={\bm{C}}_{{\bm{h}}{\bm{r}}}{\bm{C}}_{{\bm{r}}}^{-1}{\bm{r}}=({\bm{C}}_{{\bm{h}}}{\bm{A}}^{\operatorname{H}}{\bm{B}}^{\operatorname{H}}+{\bm{C}}_{{\bm{h}}{\bm{q}}}){\bm{C}}_{{\bm{r}}}^{-1}{\bm{r}}.$
(4)

In the case of jointly zero-mean Gaussian quantizer input, it is well-known
that ${\bm{B}}$ and ${\bm{C}}_{{\bm{r}}}$ can be computed in closed-form, and
${\bm{C}}_{{\bm{h}}{\bm{q}}}={\bm{0}}$, cf. [11], [24, Sec. 9.2]. Although the
zero-mean GMM is a natural generalization, covering a much larger class of
PDFs that can be approximated, the expressions for
${\bm{C}}_{{\bm{h}}{\bm{r}}}$, ${\bm{B}}$, and ${\bm{C}}_{{\bm{r}}}$ in case
of one-bit quantization are not fully investigated thus far. This motivates
the derivation of these expressions in the following.

######  Theorem 1.

The involved quantities for the linear MMSE estimator (4) are computed as

$\displaystyle{\bm{B}}$
$\displaystyle=\sqrt{\frac{2}{\pi}}\sum_{k=1}^{K}p_{k}\operatorname{diag}({\bm{C}}_{{\bm{y}}|k})^{-\frac{1}{2}}{\bm{C}}_{{\bm{y}}|k}{\bm{C}}_{{\bm{y}}}^{-1},$
(5) $\displaystyle{\bm{C}}_{{\bm{h}}{\bm{r}}}$
$\displaystyle=\sqrt{\frac{2}{\pi}}\sum_{k=1}^{K}p_{k}{\bm{C}}_{k}{\bm{A}}^{\operatorname{H}}\operatorname{diag}({\bm{C}}_{{\bm{y}}|k})^{-\frac{1}{2}},$
(6) $\displaystyle{\bm{C}}_{{\bm{r}}}$
$\displaystyle=\frac{2}{\pi}\sum_{k=1}^{K}p_{k}(\sin^{-1}(\Re(\bar{{\bm{C}}}_{{\bm{y}}|k}))+{\operatorname{j}}\sin^{-1}(\Im(\bar{{\bm{C}}}_{{\bm{y}}|k})))$
(7)

with
$\bar{{\bm{C}}}_{{\bm{y}}|k}=\operatorname{diag}({\bm{C}}_{{\bm{y}}|k})^{-\frac{1}{2}}{\bm{C}}_{{\bm{y}}|k}\operatorname{diag}({\bm{C}}_{{\bm{y}}|k})^{-\frac{1}{2}}$
and ${\bm{C}}_{{\bm{y}}}=\sum_{k=1}^{K}p_{k}{\bm{C}}_{{\bm{y}}|k}$ where
${\bm{C}}_{{\bm{y}}|k}={\bm{A}}{\bm{C}}_{k}{\bm{A}}^{\operatorname{H}}+\eta^{2}\operatorname{\mathbf{I}}$.

Proof: See Appendix -A.

######  Remark 1.

The Bussgang gain (5) is in accordance with the findings in [30]; however, the
authors only discuss the univariate case, and one-bit quantization is not
analyzed. In contrast to the Gaussian case, the Bussgang gain (5) is not a
diagonal matrix in general, which aligns with the statement in [14]. The
expression (7) can be interpreted as a weighted version of the arcsine law
[25, 26]. Since GMMs are universal approximators [31], a straightforward
application of the above results is to approximate an unknown density with a
GMM, allowing to compute the linear MMSE estimator. A similar approach was
adopted in [27].

######  Corollary 1.

Based on the results of Theorem 1, the cross-covariance matrix
${\bm{C}}_{{\bm{h}}{\bm{q}}}={\bm{C}}_{{\bm{h}}{\bm{r}}}-{\bm{C}}_{{\bm{h}}}{\bm{A}}^{\operatorname{H}}{\bm{B}}^{\operatorname{H}}$
of the signal of interest ${\bm{h}}$ and the auxiliary quantization noise
${\bm{q}}$ in (3) is

$\displaystyle\begin{aligned}
{\bm{C}}_{{\bm{h}}{\bm{q}}}=\sqrt{\frac{2}{\pi}}\sum_{k=1}^{K}p_{k}&\left({\bm{C}}_{k}{\bm{A}}^{\operatorname{H}}\operatorname{diag}({\bm{C}}_{{\bm{y}}|k})^{-\frac{1}{2}}\right.\\\
&\left.-{\bm{C}}_{{\bm{h}}}{\bm{A}}^{\operatorname{H}}\operatorname{diag}({\bm{C}}_{{\bm{y}}|k})^{-\frac{1}{2}}{\bm{C}}_{{\bm{y}}|k}{\bm{C}}_{{\bm{y}}}^{-1}\right),\end{aligned}$
(8)

contrary to the Gaussian case, where ${\bm{C}}_{{\bm{h}}{\bm{q}}}={\bm{0}}$
[11].

After deriving the linear MMSE estimator for the general case, we investigate
the CME in the following, where we particularly discuss special cases in which
it is linear.

##  IV The Conditional Mean Estimator

In the general case, the CME is not analytically tractable, necessitating a
numeric approach to solve the involved integral expressions. However, when
rewriting the CME as

$\displaystyle\operatorname{\mathbb{E}}[{\bm{h}}|{\bm{r}}]$
$\displaystyle=\sum_{k=1}^{K}p(k|{\bm{r}})\operatorname{\mathbb{E}}[{\bm{h}}|{\bm{r}},k]$
(9)
$\displaystyle=\sum_{k=1}^{K}\frac{p_{k}}{\sum_{i=1}^{K}p_{i}p({\bm{r}}|i)}\int{\bm{h}}p({\bm{h}}|k)p({\bm{r}}|{\bm{h}})\operatorname{d}{\bm{h}},$
(10)

utilizing the law of total expectation and Bayes’ rule, all involved densities
are conditioned on a GMM component. This allows for effectively treating them
as in the Gaussian case, directly enabling simplified numerical evaluations
discussed in [12, 13], whose discussion is left out due to space limitations.
However, we derive novel closed-form analytic solutions of the CME for special
cases in the following, accompanied by comparisons to the Gaussian case
analyzed in [12, 13].

###  IV-A Univariate Case with a Single Observation

We consider the case of a scalar system $r=Q(h+n)$ with
$h\sim\sum_{k=1}^{K}p_{k}\mathcal{N}_{\mathbb{C}}(0,\sigma_{k}^{2})$ and
$n\sim\operatorname{\mathcal{N}_{\mathbb{C}}}(0,\eta^{2})$.

######  Theorem 2.

The CME for the scalar system is computed as

$\displaystyle\operatorname{\mathbb{E}}[h|r]=\sqrt{\frac{2}{\pi}}\sum_{k=1}^{K}p_{k}\frac{\sigma_{k}^{2}}{\sqrt{\sigma_{k}^{2}+\eta^{2}}}r.$
(11)

Proof: See Appendix -B.

######  Remark 2.

Remarkably, in contrast to the high-resolution case, the CME is linear in the
quantized observation, i.e., the optimal estimator becomes linear through the
specific nonlinearity of the quantization process. Furthermore, the jointly
Gaussian case is not unique for the CME to be linear, in contrast to linear
AWGN channels [4]. The result can be immediately extended to a multivariate
zero-mean GMM with diagonal covariances.

The MSE of the CME is then computed to

$\displaystyle\text{MSE}_{\textup{GMM}}=\sigma_{\text{glob}}^{2}-\frac{2}{\pi}\left(\sum_{k=1}^{K}p_{k}\frac{\sigma_{k}^{2}}{\sqrt{\sigma_{k}^{2}+\eta^{2}}}\right)^{2}$
(12)

where $\sigma^{2}_{\text{glob}}=\sum_{k=1}^{K}p_{k}\sigma_{k}^{2}$ is the
global variance.

An interesting analysis is a comparison to the case of a Gaussian distributed
RV with the same global variance, i.e.,
$h\sim\operatorname{\mathcal{N}_{\mathbb{C}}}(0,\sigma_{\text{glob}}^{2})$,
for which the closed-form MSE of the corresponding CME is given as, cf. [12],

$\displaystyle\textup{MSE}_{\textup{Gauss}}=\sigma_{\text{glob}}^{2}-\frac{2}{\pi}\frac{\sigma_{\text{glob}}^{4}}{\sigma_{\text{glob}}^{2}+\eta^{2}}.$
(13)

This allows to compare the estimation performance of the CMEs when changing
the distribution of the RV of interest from a Gaussian to a GMM while keeping
the global variance fixed. We note that both estimators are optimal with
respect to the considered distribution.

######  Theorem 3.

For the considered scalar system, under a fixed global variance
$\sigma_{\textup{glob}}^{2}$, it holds for all SNRs that

$\displaystyle\textup{MSE}_{\textup{Gauss}}\leq\textup{MSE}_{\textup{GMM}}.$
(14)

Proof: See Appendix -C.

######  Remark 3.

In the high SNR regime, we get

$\displaystyle\lim_{\eta^{2}\to
0}\textup{MSE}_{\textup{GMM}}=\sigma_{\textup{glob}}^{2}-\frac{2}{\pi}\bar{\sigma}^{2}$
(15)

with $\bar{\sigma}=\sum_{k=1}^{K}p_{k}\sigma_{k}$, and the inequality (14)
directly follows from the weighted Cauchy-Schwarz inequality

$\displaystyle\bar{\sigma}^{2}\leq\sigma_{\textup{glob}}^{2}$ (16)

with equality if and only if $\sigma_{k}^{2}=\sigma^{2}$ for all
$k=1,\dots,K$, i.e., when the GMM degenerates to a Gaussian. The observation
that a GMM distribution leads to a strictly higher MMSE than the Gaussian
distribution under a fixed global variance constraint is not stated in the
literature so far.

Due to the linearity of the CME, it is equal to the Bussgang estimator,
representing the linear MMSE, cf. Section III. Using the result of Corollary
1, we can further compute

$\displaystyle\operatorname{\mathbb{E}}[hq^{*}]=\sqrt{\frac{2}{\pi}}\sum_{k=1}^{K}p_{k}\left(\frac{\sigma_{k}^{2}}{\sqrt{\sigma_{k}^{2}+\eta^{2}}}-\frac{\sigma_{\text{glob}}^{2}\sqrt{\sigma_{k}^{2}+\eta^{2}}}{\sigma_{\text{glob}}^{2}+\eta^{2}}\right),$
(17)

which is in contrast to the Gaussian case where
$\operatorname{\mathbb{E}}[hq^{*}]~{}=~{}0$ [11, Appendix A]. Moreover, the
correlation $\operatorname{\mathbb{E}}[hq^{*}]$ vanishes in both the low and
high SNR regime, i.e.,

$\displaystyle\lim_{\eta\to\infty}\operatorname{\mathbb{E}}[hq^{*}]=\lim_{\eta\to
0}\operatorname{\mathbb{E}}[hq^{*}]=0.$ (18)

###  IV-B Univariate Noiseless Case with Multiple Observations

We consider the noiseless case with multiple pilot observations
${\bm{r}}=Q({\bm{a}}h)$, for which the closed-form CME together with the
optimal pilot sequence was derived in [12] for the Gaussian case. First, we
show that the pilot sequence for the Gaussian case is also MSE-optimal for the
GMM case.

######  Theorem 4.

The MSE-optimal pilot sequence for the considered system contains equidistant
phase shifts $\psi_{m}=\frac{\pi(m-1)}{2M}$ for all $m=1,\dots,M$, such that
$[{\bm{a}}]_{m}=\exp({\operatorname{j}}\psi_{m})$.

Proof: See Appendix -D.

######  Remark 4.

In contrast to the Gaussian case, the amplitudes of the GMM are not Rayleigh
distributed, which does not impact the design of the optimal pilot sequence
since the amplitude information is lost through the one-bit quantization, and
the circular symmetry property is not affected [32].

######  Theorem 5.

The CME for the considered system has the two equivalent expressions

$\displaystyle\operatorname{\mathbb{E}}[h|{\bm{r}}]$
$\displaystyle=\sqrt{\frac{2}{\pi}}\sum_{k=1}^{K}p_{k}\sigma_{k}{\bm{a}}^{\operatorname{H}}{\bm{C}}_{{\bm{r}}}^{-1}{\bm{r}}$
(19)
$\displaystyle=\sum_{k=1}^{K}p_{k}\frac{2M\sigma_{k}}{\sqrt{\pi}}\sin\left(\frac{\pi}{4M}\right)\exp\left({\operatorname{j}}\varphi({\bm{r}})\right)$
(20)

where ${\bm{C}}_{{\bm{r}}}^{-1}$ is equivalent to the analytic expression that
solely depends on the number of pilots from the Gaussian case [12, Lemma 1],
and
$\varphi({\bm{r}})=\angle(\frac{1}{M}\sum_{m=1}^{M}[{\bm{r}}]_{m})-\frac{(M-1)\pi}{4M}$
[12].

Proof: See Appendix -E.

######  Remark 5.

The result of Theorem 5 is interesting since it leads to two equivalent
formulations of the CME, one being linear and one being nonlinear in the
observation. This allows for different but equivalent implementations of the
optimal estimator in a practical system. Moreover, the expression (20) allows
for a simplified formulation of the closed-form analytic MSE in the following.

The MSE of the CME (20) is computed to

$\displaystyle\text{MSE}_{\text{GMM}}$
$\displaystyle=\sigma_{\text{glob}}^{2}-\frac{4M^{2}}{\pi}\sin^{2}\left(\frac{\pi}{4M}\right)\bar{\sigma}^{2}.$
(21)

Thus, we get in the limit of infinitely many pilots, cf. [12],

$\displaystyle\lim_{M\to\infty}\text{MSE}_{\text{GMM}}=\sigma_{\text{glob}}^{2}-\frac{\pi}{4}\bar{\sigma}^{2}.$
(22)

Observing the MSE expression for the Gaussian case in [12], under a fixed
global variance $\sigma_{\text{glob}}^{2}$, we directly see by the weighted
Cauchy-Schwarz inequality (16) that

$\displaystyle\text{MSE}_{\text{Gauss}}\leq\text{MSE}_{\text{GMM}}$ (23)

holds for all numbers of observations $M$, generalizing the result from (14).

##  V Numerical Results

For each simulation, we draw $10{,}000$ samples from a GMM for estimating the
normalized MSE
$\operatorname{\mathbb{E}}[\|{\bm{h}}-\hat{{\bm{h}}}\|_{2}^{2}]/\operatorname{\mathbb{E}}[\|{\bm{h}}\|_{2}^{2}]$.

In Fig. 1, we choose a ground-truth GMM with $K=2$ components with the weights
$p_{1}=0.8$ and $p_{2}=0.2$ and $N=64$-dimensional randomly chosen covariances
following to the procedure in [12], which are afterward scaled with a factor
of $0.1$ and $10$ for $k=1$ and $k=2$, respectively. This resembles a simple
GMM where the differences to the Gaussian case are evident. We compare the
linear MMSE estimator (4) with the quantities derived in Theorem 1 to the
suboptimal linear Bussgang estimator assuming a Gaussian prior
$\operatorname{\mathcal{N}_{\mathbb{C}}}({\bm{0}},{\bm{C}}_{{\bm{h}}})$ (mism.
Gauss) for $M\in\\{1,8,16,32\\}$ with the pilot sequence from Theorem 4. The
Gaussian approximation is tight in the low SNR regime but shows a considerable
gap for medium and high SNRs, highlighting the importance of the novel derived
linear MMSE estimator for the GMM case.

In the following, we consider the same GMM but for $N=1$, where we choose
$\sigma_{1}^{2}=0.1$ and $\sigma_{2}^{2}=10$, which are afterward normalized
such that $\sigma_{\text{glob}}^{2}=1$. This ensures that the inequality (16)
has a non-negligible gap.

Figure 1: Comparison of the linear MMSE estimator with the suboptimal
estimator assuming a Gaussian prior for $N=64$ and $M\in\\{1,8,16,32\\}$.
Figure 2: MSE results of the CME from Theorem 2 for the univariate case
$r=Q(h+n)$ in comparison with the Gaussian case, validating Theorem 3.

We first verify the result of Theorem 2 for the univariate case with $N=M=1$
in Fig. 2. It can be seen that the analytic MSE expression (12) is on par with
the evaluation of the CME (11), converging to the noiseless case (15).
Additionally, we have evaluated the estimator where the cross-correlation
$\operatorname{\mathbb{E}}[hq^{*}]$ is neglected (mism. corr.), which shows a
performance loss in the medium SNR regime, being in accordance with (18); the
estimator that erroneously assumes a Gaussian distributed input, evaluating
the CME from [12] (mism. Gauss) deteriorates from the CME with a considerable
gap. The CME when the distribution is changed to a Gaussian and its limit show
a clearly lower MSE over the whole SNR range, validating Theorem 3 and Remark
3.

Fig. 3 assesses the CME from Theorem 5 for the MSE-optimal pilot sequence in
Theorem 4 in the noiseless case. It can be observed that the limit is achieved
already with a few observations, similar to the Gaussian case [12], which
yields a lower MSE for all observations, cf. (23).

Finally, Fig. 4 evaluates the CME for the noisy case with multiple
observations, i.e., ${\bm{r}}=Q({\bm{a}}h+{\bm{n}})$, which has no analytic
expression and is computed numerically via the algorithm from [33],
implemented in [34], cf. [12]. It can be seen that the MSE limit for
infinitely many observations without AWGN is drastically outperformed with
only a few observations and finite SNRs. This behavior is attributed to the
fundamental effect of stoachstic resonance [35], where noise can improve the
performance in a quantized system. In comparison to the Gaussian case with the
same global variance $\sigma_{\text{glob}}^{2}=1$ (CME Gauss), the stochastic
resonance effect seems to be more pronounced, and the MSE inequality does not
hold anymore, especially with more observations and in the low SNR regime.
Moreover, the sub-optimal low-complexity linear MMSE estimator (4) (LMMSE GMM)
degrades from the CME, especially for higher numbers of observations.

Further results are shown in Appendix -F.

Figure 3: Performance of the CME from Theorem 5 for the MSE-optimal pilot
sequence from Theorem 4 in comparison to the Gaussian case. Figure 4:
Comparison of the CME with the MSE-optimal transmit sequence to the Gaussian
case for ${\bm{r}}=Q({\bm{a}}h+{\bm{n}})$ with $M\in\\{1,5,10\\}$.

##  VI Conclusion

We have presented novel fundamental results for the linear MMSE estimator and
the CME in one-bit quantized systems for GMM distributed inputs. In addition
to novel closed-form solutions for the CME, highlighting its linearity in
special cases, a new MSE inequality regarding the Gaussian and GMM case was
established, which also holds in the analyzed asymptotic regime. However, this
inequality does not hold in the general case as the GMM shows a more
pronounced stochastic resonance effect. The presented results are of use for
various signal processing applications.

###  -A Proof of Theorem 1

###### Proof.

We first observe that
${\bm{y}}\sim\sum_{k=1}^{K}p_{k}\operatorname{\mathcal{N}_{\mathbb{C}}}({\bm{y}};{\bm{0}},{\bm{C}}_{{\bm{y}}|k})$
with
${\bm{C}}_{{\bm{y}}|k}={\bm{A}}{\bm{C}}_{k}{\bm{A}}^{\operatorname{H}}+\eta^{2}\operatorname{\mathbf{I}}$
due to the Gaussianity of the noise. Thus,
${\bm{y}}|k\sim\operatorname{\mathcal{N}_{\mathbb{C}}}({\bm{y}};{\bm{0}},{\bm{C}}_{{\bm{y}}|k})$,
which is used in the following. Utilizing the law of total expectation for the
definition of the Bussgang gain, cf. [14], yields

$\displaystyle{\bm{B}}$
$\displaystyle=\operatorname{\mathbb{E}}[Q({\bm{y}}){\bm{y}}^{\operatorname{H}}]\operatorname{\mathbb{E}}[{\bm{y}}{\bm{y}}^{\operatorname{H}}]^{-1}$
(24)
$\displaystyle=\sum_{k=1}^{K}p_{k}\operatorname{\mathbb{E}}[Q({\bm{y}}){\bm{y}}^{\operatorname{H}}|k]\operatorname{\mathbb{E}}[{\bm{y}}{\bm{y}}^{\operatorname{H}}]^{-1}.$
(25)

The solution of
$\operatorname{\mathbb{E}}[Q({\bm{y}}){\bm{y}}^{\operatorname{H}}|k]=\sqrt{\frac{2}{\pi}}\operatorname{diag}({\bm{C}}_{{\bm{y}}|k})^{-\frac{1}{2}}{\bm{C}}_{{\bm{y}}|k}$
is known from the Gaussian case, cf., e.g., [24, Sec. 9.2], yielding the
result in (5). Similarly, the cross-covariance matrix (6) is computed as

$\displaystyle{\bm{C}}_{{\bm{h}}{\bm{r}}}$
$\displaystyle=\operatorname{\mathbb{E}}[{\bm{h}}{\bm{r}}^{\operatorname{H}}]=\sum_{k=1}^{K}p_{k}\operatorname{\mathbb{E}}[{\bm{h}}Q({\bm{y}})^{\operatorname{H}}|k]$
(26)

where
$\operatorname{\mathbb{E}}[{\bm{h}}Q({\bm{y}})^{\operatorname{H}}]=\sqrt{\frac{2}{\pi}}{\bm{C}}_{k}{\bm{A}}^{\operatorname{H}}\operatorname{diag}({\bm{C}}_{{\bm{y}}|k})^{-\frac{1}{2}}$
is known from the Gaussian case, cf., e.g., [11]. Finally, the computation of
the covariance matrix ${\bm{C}}_{{\bm{r}}}$ is a direct consequence of the law
of total expectation, i.e.,

$\displaystyle\operatorname{\mathbb{E}}[{\bm{r}}{\bm{r}}^{\operatorname{H}}]=\operatorname{\mathbb{E}}[Q({\bm{y}})Q({\bm{y}})^{\operatorname{H}}]=\sum_{k=1}^{K}p_{k}\operatorname{\mathbb{E}}[Q({\bm{y}})Q({\bm{y}})^{\operatorname{H}}|k]$
(27)

and the known solution for the Gaussian case, known as the arcsine law, cf.
[25, 26]. ∎

###  -B Proof of Theorem 2

###### Proof.

We observe that $p(k|{\bm{r}})=p_{k}$ for all $k=1,\dots,K$ in (9) since the
zero-mean GMM is symmetric around the origin, and thus, the quantized
observation is uninformative for evaluating the responsibility. The solution
of

$\displaystyle\operatorname{\mathbb{E}}[h|r,k]=\sqrt{\frac{2}{\pi}}\frac{\sigma_{k}^{2}}{\sqrt{\sigma_{k}^{2}+\eta^{2}}}r$
(28)

is known from the Gaussian case, see, e.g., [12]. ∎

###  -C Proof of Theorem 3

###### Proof.

Comparing (12) and (13), after removing the equivalent terms and taking the
square root on both sides, we need to show that

$\displaystyle\sum_{k=1}^{K}p_{k}\frac{\sigma_{k}^{2}}{\sqrt{\sigma_{k}^{2}+\eta^{2}}}\leq\frac{\sum_{k=1}^{K}p_{k}\sigma_{k}^{2}}{\sqrt{\sum_{k=1}^{K}p_{k}\sigma_{k}^{2}+\eta^{2}}}.$
(29)

Since the weights $p_{k}$ form a convex combination, (29) holds if
$f(x)=\frac{x}{\sqrt{x+\eta^{2}}}$ is a concave function for all $x>0$ based
on the definition of concave functions [36, Sec. 3.1.8]. Since

$\displaystyle\frac{\partial^{2}}{\partial
x^{2}}f(x)=-\frac{x+4\eta^{2}}{4\sqrt{(\eta^{2}+x)^{5}}}<0\text{ for all
}x,\eta^{2}>0,$ (30)

it follows that $f(x)$ is a concave function for all $x>0$. Thus, (29) is
fulfilled, finishing the proof. ∎

###  -D Proof of Theorem 4

###### Proof.

As a direct consequence of the circular symmetry of the individual Gaussians,
it immediately follows that the zero-mean GMM distribution is also circularly
symmetric and thus has uniformly distributed phases [32]. Based on this, the
same proof holds as in [12, Appendix B], yielding the same MSE-optimal
sequence. ∎

###  -E Proof of Theorem 5

###### Proof.

Similar to Theorem 2, the responsibility $p(k|{\bm{r}})=p_{k}$ since the pilot
observations contain no amplitude information. The solution
$\operatorname{\mathbb{E}}[h|{\bm{r}},k]$ is given in [12]. Since
$\bar{{\bm{C}}}_{{\bm{y}}|k}={\bm{a}}{\bm{a}}^{\operatorname{H}}$ for all
$k=1,\dots,K$, the computation of ${\bm{C}}_{{\bm{r}}}$ in (7) degenerates to
the Gaussian case. As both functions (19) and (20) lead to the same MSE [12],
they are equivalent on the discrete input domain by the uniqueness of the CME
[1, Th. 1]. ∎

###  -F Additional Numerical Results

Fig. 5 shows the correlation $\operatorname{\mathbb{E}}[hq^{*}]$ from (17)
over the SNR for the same setting as in Fig. 2, which is vanishing in the low
and high SNR regime in accordance with (18) and the performance loss in Fig.
2.

Figure 5: Correlation of the RV of interest $h$ with the quantization noise
$q$, cf. Corollary 1, for the univariate case $r=Q(h+n)$.

Fig. 6 evaluates the same setting as in Fig. 4 but compares the MSE-optimal
sequence for the noiseless case derived in Theorem 4 with the all-ones
sequence ${\bm{a}}={\bm{1}}$. It can be observed that the pilot sequence from
Theorem 4 outperforms the all-ones sequence in medium to high SNRs,
highlighting its superiority also in the non-asymptotic SNR regime.

Figure 6: Comparison of the CME with the MSE-optimal and the all-ones sequence
for the case ${\bm{r}}=Q({\bm{a}}h+{\bm{n}})$ with $M\in\\{1,2,5,10\\}$ and
$\sigma_{\text{glob}}^{2}=1$.

## References

  * [1] A. Banerjee, X. Guo, and H. Wang, “On the optimality of conditional expectation as a Bregman predictor,” _IEEE Trans. Inf. Theory_ , vol. 51, no. 7, pp. 2664–2669, 2005.
  * [2] D. Guo, Y. Wu, S. S. Shitz, and S. Verdú, “Estimation in Gaussian noise: Properties of the minimum mean-square error,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 4, pp. 2371–2385, 2011.
  * [3] A. Dytso and H. V. Poor, “Properties of the conditional mean estimator in Poisson noise,” in _IEEE Inf. Theory Workshop (ITW)_ , 2019, pp. 1–5.
  * [4] E. Akyol, K. Viswanatha, and K. Rose, “On conditions for linearity of optimal estimation,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 6, pp. 3497–3508, 2012\.
  * [5] A. Kipnis, Y. C. Eldar, and A. J. Goldsmith, “Fundamental distortion limits of analog-to-digital compression,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 9, pp. 6013–6033, 2018.
  * [6] S. Khobahi and M. Soltanalian, “Signal recovery from 1-bit quantized noisy samples via adaptive thresholding,” in _52nd Asilomar Conf. Signals, Syst., Comput._ , 2018, pp. 1757–1761.
  * [7] Y. You, _Audio Coding: Theory and Applications_. Springer NY, 2010.
  * [8] R. E. Curry, _Estimation and Control with Quantized Measurements_. MIT Press, 1970.
  * [9] F. Wendler, M. Stein, A. Mezghani, and J. A. Nossek, “Quantization-loss reduction for 1-bit BOC positioning,” in _ION Int. Tech. Meeting (ITM)_ , 2013, pp. 509–518.
  * [10] M. Ivrlac and J. Nossek, “On MIMO channel estimation with single-bit signal-quantization,” in _ITG Workshop Smart Antennas_ , 2007.
  * [11] Y. Li, C. Tao, G. Seco-Granados, A. Mezghani, A. L. Swindlehurst, and L. Liu, “Channel estimation and performance analysis of one-bit massive MIMO systems,” _IEEE Trans. Signal Process._ , vol. 65, no. 15, pp. 4075–4089, 2017.
  * [12] B. Fesl, M. Koller, and W. Utschick, “On the mean square error optimal estimator in one-bit quantized systems,” _IEEE Trans. Signal Process._ , vol. 71, pp. 1968–1980, 2023.
  * [13] M. Ding, I. Atzeni, A. Tölli, and A. L. Swindlehurst, “On the optimal MMSE channel estimation for one-bit quantized MIMO systems,” 2024, arXiv preprint: 2404.05536.
  * [14] O. T. Demir and E. Bjornson, “The Bussgang decomposition of nonlinear systems: Basic theory and MIMO extensions [lecture notes],” _IEEE Signal Process. Mag._ , vol. 38, no. 1, pp. 131–136, 2021.
  * [15] Q. Wan, J. Fang, H. Duan, Z. Chen, and H. Li, “Generalized Bussgang LMMSE channel estimation for one-bit massive MIMO systems,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 6, pp. 4234–4246, 2020.
  * [16] J. J. Bussgang, “Crosscorrelation functions of amplitude-distorted Gaussian signals,” MIT Res. Lab. Electron., Tech. Rep. 216, 1952.
  * [17] A. K. Fletcher, S. Rangan, V. K. Goyal, and K. Ramchandran, “Robust predictive quantization: Analysis and design via convex optimization,” _IEEE J. Sel. Topics Signal Process._ , vol. 1, no. 4, pp. 618–632, 2007.
  * [18] A. Mezghani and J. Nossek, “Capacity lower bound of MIMO channels with output quantization and correlated noise,” in _Int. Symp. Inf. Theory_ , 2012\.
  * [19] E. Björnson, J. Hoydis, M. Kountouris, and M. Debbah, “Massive MIMO systems with non-ideal hardware: Energy efficiency, estimation, and capacity limits,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 11, pp. 7112–7139, 2014\.
  * [20] E. Björnson, L. Sanguinetti, and J. Hoydis, “Hardware distortion correlation has negligible impact on UL massive MIMO spectral efficiency,” _IEEE Trans. Commun._ , vol. 67, no. 2, pp. 1085–1098, 2019.
  * [21] P. Banelli and S. Cacopardi, “Theoretical analysis and performance of OFDM signals in nonlinear AWGN channels,” _IEEE Trans. Commun._ , vol. 48, no. 3, pp. 430–441, 2000.
  * [22] D. Dardari, V. Tralli, and A. Vaccari, “A theoretical characterization of nonlinear distortion effects in OFDM systems,” _IEEE Trans. Commun._ , vol. 48, no. 10, pp. 1755–1764, 2000.
  * [23] A. Fakhrizadeh Esfahani, J. Schoukens, and L. Vanbeylen, “Using the best linear approximation with varying excitation signals for nonlinear system characterization,” _IEEE Trans. Instrum. Meas._ , vol. 65, no. 5, pp. 1271–1280, 2016.
  * [24] A. Papoulis and S. U. Pillai, _Probability, Random Variables and Stochastic Processes_. McGraw-Hill Education, 2002.
  * [25] J. Van Vleck and D. Middleton, “The spectrum of clipped noise,” _Proc. IEEE_ , vol. 54, no. 1, pp. 2–19, 1966.
  * [26] G. Jacovitti and A. Neri, “Estimation of the autocorrelation function of complex Gaussian stationary processes by amplitude clipped signals,” _IEEE Trans. Inf. Theory_ , vol. 40, no. 1, pp. 239–245, 1994.
  * [27] B. Fesl, N. Turan, B. Böck, and W. Utschick, “Channel estimation for quantized systems based on conditionally Gaussian latent models,” _IEEE Trans. Signal Process._ , vol. 72, pp. 1475–1490, 2024.
  * [28] B. Böck, M. Baur, N. Turan, D. Semmler, and W. Utschick, “A statistical characterization of wireless channels conditioned on side information,” 2024, arXiv preprint: 2406.04282.
  * [29] S. Zhidkov, “Performance analysis and optimization of OFDM receiver with blanking nonlinearity in impulsive noise environment,” _IEEE Trans. Veh. Technol._ , vol. 55, no. 1, pp. 234–242, 2006.
  * [30] P. Banelli, “Non-linear transformations of Gaussians and Gaussian-mixtures with implications on estimation and information theory,” 2013, arXiv preprint: 1111.5950.
  * [31] T. T. Nguyen, H. D. Nguyen, F. Chamroukhi, and G. J. McLachlan, “Approximation by finite mixtures of continuous density functions that vanish at infinity,” _Cogent Math. Statist._ , vol. 7, no. 1, p. 1750861, 2020.
  * [32] B. Picinbono, “On circularity,” _IEEE Trans. Signal Process._ , vol. 42, no. 12, pp. 3473–3482, 1994.
  * [33] A. Genz, “Numerical computation of multivariate normal probabilities,” _J. Comput. Graph. Statist._ , vol. 1, no. 2, pp. 141–149, 1992.
  * [34] P. Virtanen _et al._ , “SciPy 1.0: Fundamental algorithms for scientific computing in Python,” _Nat. Methods_ , vol. 17, pp. 261–272, 2020.
  * [35] M. D. McDonnell, N. G. Stocks, C. E. M. Pearce, and D. Abbott, _Stochastic Resonance: From Suprathreshold Stochastic Resonance to Stochastic Signal Quantization_. Cambridge University Press, 2008.
  * [36] S. P. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge University Press, 2014.