# Improved Visual Grounding through Self-Consistent Explanations

Ruozhen He$1$ Paola Cascante-Bonilla$1$ Ziyan Yang$1$ Alexander C. Berg$2$
Vicente Ordonez$1$
$1$Rice University $2$University of California, Irvine
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Vision-and-language models trained to match images with text can be combined
with visual explanation methods to point to the locations of specific objects
in an image. Our work shows that the localization –“grounding”– abilities of
these models can be further improved by finetuning for self-consistent visual
explanations. We propose a strategy for augmenting existing text-image
datasets with paraphrases using a large language model, and SelfEQ, a weakly-
supervised strategy on visual explanation maps for paraphrases that encourages
self-consistency. Specifically, for an input textual phrase, we attempt to
generate a paraphrase and finetune the model so that the phrase and paraphrase
map to the same region in the image. We posit that this both expands the
vocabulary that the model is able to handle, and improves the quality of the
object locations highlighted by gradient-based visual explanation methods
(e.g. GradCAM). We demonstrate that SelfEQ improves performance on Flickr30k,
ReferIt, and RefCOCO+ over a strong baseline method and several prior works.
Particularly, comparing to other methods that do not use any type of box
annotations, we obtain 84.07% on Flickr30k (an absolute improvement of 4.69%),
67.40% on ReferIt (an absolute improvement of 7.68%), and 75.10%, 55.49% on
RefCOCO+ test sets A and B respectively (an absolute improvement of 3.74% on
average).

##  1 Introduction

Vision-and-language models that are trained to associate images with text have
shown to be effective for many tasks and benchmarks [43, 28, 22, 33],
including object detection [56, 19] and image segmentation [52, 38, 16]. Since
these models are typically trained with in-the-wild data from the web, they
can handle a wide range of vocabulary for objects as long as they are well
represented in the training data. These models are often remarkably accurate
[23, 49, 29, 17] even without tuning them to perform well in any particular
downstream task [54, 34, 15]. The ALBEF model [28] was particularly capable of
visual “grounding” – or in other words – the ability to localize objects in
images by simply using it in conjunction with a visual explanation method such
as GradCAM [45]. This capability is particularly remarkable given that this
model was only supervised with images and text but no object location
annotations of any type.

Figure 1:  Previous models can localize the word _frisbee_ , but struggle with
equivalent but more uncommon referents such as _disc_. A model tuned with our
proposed SelfEQ objective encourages consistent visual explanations for
paraphrased prompts and performs well on both examples. SelfEQ not only
enables a larger working vocabulary but also improves overall localization
performance.

In order to improve the ability of vision-and-language models to perform
localization, many methods have incorporated further finetuning with either
box or segment annotations, or rely on pretrained object detectors or box
proposal networks [6, 13, 20, 53, 32, 24]. Our work instead aims to improve
the localization capabilities of models trained only on image-text pairs
through weak supervision. But, how can we improve the ability of a model to
localize objects without access to object location annotations? Consider the
example in Figure 1 where a model is tasked with pointing to the location of
the object _frisbee_ in this image. The baseline model succeeds at finding the
object but is unsuccessful at locating the object when prompted with the
equivalent but more generic name _disc_. Regardless of the ability for the
base model to find either of these, the visual explanations for these two
prompts should be the same since the query refers to the very same object in
both cases. Our work exploits this property by first generating paraphrases
using a large language model and then proposing a weakly-supervised Self-
consistency EQuivalence Tuning (SelfEQ) objective that encourages consistent
visual explanations between paraphrased input text pairs that refer to the
same object or region in a given image.

Given a base pre-trained vision-and-language model purely trained on image-
text pairs such as ALBEF [28], SelfEQ tunes the model so that for a given
input image and text pair, the visual attention map extracted using GradCAM
[45] produces a similar visual attention map when provided with the same image
and a text paraphrase. Figure 2 provides an overview of our method. Another
contribution of our work consists in exploiting a large language model (LLM)
to automatically generate paraphrases for existing datasets such as Visual
Genome [27] that contains textual descriptions of individual objects and
regions, or MS-COCO [35] and CC3M [48] that contain global image descriptions.
We find that SelfEQ not only expands the vocabulary of objects that the base
model is able to localize but more importantly, improves the visual grounding
capabilities of the model on standard benchmarks such as referring expression
comprehension on the ReferIt benchmark [25] and region-phrase grounding in the
Flickr30K Entities benchmark [42]. In summary, our key contributions are as
follows:

  * •

We design a novel objective, SelfEQ, to encourage vision-and-language models
to generate self-consistent visual explanations for equivalent text phrases,
thereby improving grounding capabilities while expanding the working
vocabulary of the model.

  * •

We propose to prompt large language models for generating paraphrased image
descriptions of individual objects or regions. Particularly, we adopt
Vicuna-13B [7] and design text prompts to obtain high quality paraphrases.

  * •

We demonstrate the effectiveness of our method by outperforming previous
methods, leading to $4.69\%$ improvement on Flickr30k, $7.68\%$ improvement on
ReferIt, and $3.74\%$ improvement on RefCOCO+.

Finally, we plan to release our code, generated paraphrases and model
checkpoints upon publication.

##  2 Related Work

Our work is related to previous methods on visual grounding, especially those
that are trained under weak supervision understood as without the use of
bounding box or segment annotations and relying only on image-text pairs. From
a technical perspective our work is related to methods that optimize visual
explanations to improve the underlying model.

Visual grounding consists of localizing an input textual description in an
image. Supervised methods are provided with text-image pairs and corresponding
bounding boxes [9, 13, 10, 53, 24]. Other supervised methods leverage
pretrained object detectors to obtain a region of interest and then identify
the region that aligns most closely under their textual representations [8,
20, 50, 37, 18, 6]. In both cases, these methods use some form of box
supervision during pre-training or at test time by relying on a pre-trained
object detector. In contrast, our work focuses exclusively in the scenario
where no bounding boxes or segment annotations are available at any stage.

Weakly-Supervised Grounding. Our setup is similar to that of Arbelle et al [3]
where no box annotations or object detectors are used for grounding. This work
proposes Grounding by Separation (GbS) where a model is trained on randomly
alpha-blended pairs of images and the goal is to separate them conditioned on
text prompts. Our method instead relies on data augmentation on the text side
and while our method shows favorable results, our contribution is orthogonal.
Shaharabany et al [47] builds a weakly-supervised phrase grounding model by
creating a large amount of data by combining region boxes with a BLIP
captioning model. Later work by Shaharabany and Wolf [46] employs layer-wise
relevance propagation [40] to integrate relevancy and gradient information
with the scores computed from each attention head in the transformer layers
[5], or residual connections [1]. Our work compares favorably or on par with
these methods but since we rely on gradient-based explanations, our work does
not require making any modifications to the base network.

Visual Explanation Tuning. Related to our method is the strategy used by ALBEF
[28] where the model is only supervised on image-text pairs and performs
grounding through GradCAM [45], a gradient-based visual explanation method
that outputs a heatmap indicating spatial relevance. Earlier, Xiao et al [51]
used a similar strategy but further optimized gradient-based explanations
using structural constraints derived from text. Recently, AMC [53] follows
this strategy but further adds box supervision on the output maps using a
margin-based loss. We adopt ALBEF [28] as our base model and also adopt a
gradient-based explanation strategy but unlike AMC [53] we do not rely on box
annotations for tuning this model and use our proposed SelfEQ objective
instead. Javed et al [21] proposed an objective function that encourages
consistent representations in embedding space for the same input prompt on
different images. In contrast SelfEQ encourages consistent visual explanations
for different prompts on the same image by relying on automatically generated
paraphrases. Akbari et al [2] also optimizes attention maps but in their
formulation the model backbone is modified to explicitly incorporate attention
instead of relying on gradient-based attention maps.

##  3 Method

Figure 2: Overview of our proposed weakly-supervised Self-consistency
EQuivalence tuning objective. We input image-text and image-paraphrase pairs
$\langle V,T\rangle$ and $\langle V,T^{e}\rangle$ to our base pre-trained
vision-and-language model. We then obtain gradient-based visual explanations
$\langle G,G^{e}\rangle$ and compute a similarity loss between them. We also
define an overlapping region of interest mask and encourage the model to
predict consistently high saliency scores within this mask for each input
pair.

We start from a base vision-language model composed of a text decoder
$\phi_{t}$ , an image encoder $\phi_{v}$ , and a multimodal fusion encoder
$\phi_{f}$, along with a dataset $D$ to finetune this model consisting of
image-text pairs $\langle T,V\rangle$. Section 3.1, introduces the training
objectives for the base model which we also adopt for finetuning our baseline
and are also used in conjunction with SelfEQ to finetune our final model.
Section 3.2 introduces in detail SelfEQ, our self-consistency equivalence
tuning objective that assumes the existence of paraphrases $T^{e}$ for each
input image-text pair $\langle T,V\rangle$, and Section 3.3 describes our
approach for automatically generating paraphrases $T^{e}$ using LLM-prompting.
Figure 2 presents an overview of our proposed method.

###  3.1 Base Model: Preliminaries

Our base vision-and-language model is ALBEF [28] which relies on three widely
used objectives for visual and textual representation learning: image-text
matching, masked language modeling and a contrastive loss. We describe them
here briefly as they are also re-used during fine-tuning.

#### Image-Text Matching Loss (ITM).

This loss is calculated using the output of the [CLS] token to predict if the
input image and the input text are matching or not and is defined as follows:

$\small\mathcal{L}_{\mathrm{itm}}=\;\mathbb{E}_{(V,T)\sim
D}\;\mathcal{H}\left(\vec{y},\phi_{f}^{\mathrm{cls}}\left(\phi_{v}\left(V\right),\phi_{t}\left(T\right)\right)\right),$
(1)

where $\vec{y}$ denotes a two-dimensional one-hot vector, indicating whether
the sample $\langle V,T\rangle$ constitutes a match, $\phi_{f}^{\mathrm{cls}}$
represents a linear layer followed by a softmax function, and $\mathcal{H}$ is
the cross entropy loss function.

#### Masking Language Modeling Loss (MLM).

This loss has been applied for various vision-language pretraining models [28,
6, 31, 36]. It integrates the contextual text and the input image to infer
masked words in the input text. After utilizing a linear layer and a softmax
activation function $\phi_{f}^{\mathrm{m}}$ to individual output embeddings,
the objective is expressed as:

$\small\mathcal{L}_{\mathrm{mlm}}=\;\mathbb{E}_{(V,T^{\mathrm{-m}})\sim
D}\;\mathcal{H}\left(\vec{t}^{\mathrm{m}},\phi_{f}^{\mathrm{m}}\left(\phi_{v}\left(V\right),\phi_{t}\left(T^{\mathrm{-m}}\right)\right)\right),$
(2)

where the one-hot vector $\vec{t}^{\mathrm{m}}$ denotes the masked token, and
$T^{\mathrm{-m}}$ represents the input masked text.

#### Image-Text Contrastive Loss (ITC).

It improves the alignment between visual and textual representations by
bringing closer the representations for corresponding text-image pairs
relative to text-image pairs that do not correspond. This objective can be
defined as follows:

$\displaystyle\mathcal{L}_{\mathrm{itc}}=\mathbb{E}_{(V,T)\sim
D}\frac{1}{2}\biggl{[}\mathcal{H}\biggl{(}\vec{y},\frac{\mathrm{exp}\left(\phi_{v}(V)\cdot\phi_{t}(T)\right)/\tau}{\sum_{b=1}^{B}\mathrm{s}\left(V,T_{b}\right)}\biggr{)}$
(3)
$\displaystyle+\mathcal{H}\biggl{(}\vec{y},\frac{\mathrm{exp}\left(\phi_{t}(T)\cdot\phi_{v}(V)\right)/\tau}{\sum_{b=1}^{B}\mathrm{s}\left(T,V_{b}\right)}\biggr{)}\biggr{]},$

where $B$ is the number of negative sample pairs, and $\tau$ is a temperature
parameter for the softmax function.

The training objective for the base model is a combination of the previous
three loss functions:

$\small\mathcal{L}_{\mathrm{vl}}=\mathcal{L}_{\mathrm{itm}}+\mathcal{L}_{\mathrm{mlm}}+\mathcal{L}_{\mathrm{itc}}.$
(4)

This loss $\mathcal{L}_{\mathrm{vl}}$ will also be used to tune our baseline
model.

###  3.2 Self-Consistency Equivalence Tuning

SelfEQ assumes that the model has access to paraphrases $T^{e}$ for each input
image-text pair $\langle V,T\rangle$ or, in practice, for a subset of those
samples. Therefore we assume a finetuning dataset $D^{\prime}$ with triplets
$\langle V,T,T^{e}\rangle$ such that $T_{e}$ exists for a corresponding input
text $T$. The first step to define our SelfEQ objective is to generate the
explanation heatmaps (i.e., attention maps) through GradCAM [45] conditioned
on the input text. We extract intermediate feature maps from the multimodal
interactive encoder $\phi_{f}$ for input pairs $\langle V,T\rangle$ and
$\langle V,T^{e}\rangle$ as follows:

$\small
F=\phi\left(\phi_{v}(V),\phi_{t}(T)\right),F^{e}=\phi\left(\phi_{v}(V),\phi_{t}(T^{e})\right),$
(5)

where $\phi$ denotes the feature map extraction operation. We then proceed to
calculate the gradient of $F$ and $F^{e}$ related to the image-text matching
score $\mathcal{L}_{\mathrm{itm}}$. This computation yields the attention maps
for the original text and paraphrased text, referred to as $G$ and $G^{e}$,
respectively:

$\displaystyle G$
$\displaystyle=\mathrm{ReLU}\left(F\odot\triangledown\mathcal{H}\left(\vec{y},\phi_{f}^{cls}\left(\phi_{v}(V),\phi_{t}(T)\right)\right)\right),$
(6) $\displaystyle G^{e}$
$\displaystyle=\mathrm{ReLU}\left(F^{e}\odot\triangledown\mathcal{H}\left(\vec{y},\phi_{f}^{cls}\left(\phi_{v}(V),\phi_{t}(T^{e})\right)\right)\right).$

Our SelfEQ tuning is based on the premise that if a vision-language model is
identified as self-consistent, the attention maps produced for both the text
and its equivalent paraphrase should yield nearly identical results. To
achieve this, we first apply a simple mean squared error loss over the
produced heatmaps so that their $\ell_{2}$ distance is minimized and thus
become more similar.

$\small\mathcal{L}_{\mathrm{sim}}=\\\ \mathbb{E}_{(V,T,T^{e})\sim
D^{\prime}}\biggl{[}\frac{1}{N}\sum_{i,j}(G_{i,j}-G^{e}_{i,j})^{2}\biggr{]}.$
(7)

Nevertheless, while minimizing a sum of pixel-wise distances contributes to
self-consistency, without a regularization term this loss can easily fall into
a trivial solution. For instance, it could lead to attention maps with
uniformly negative or positive predictions, or just really small values. To
address this limitation, we propose to integrate these heatmaps by defining a
Region of Interest (RoI) mask. This mask is designed to preserve regions
within the attention maps that possibly contain correct predictions. Our
approach hinges on the observation that, despite the predictions of equivalent
textual inputs being inconsistent, sometimes regions with large values or
regions that overlap between the two heatmaps tend to be correct. As such, we
assume that if the sum of attention scores at a given position $(i,j)$ exceeds
a certain threshold $k$, it is likely indicative of a correct prediction. We
formalize the condition as follows:

$\small M_{i,j}=\begin{cases}1,(G_{i,j}+G^{e}_{i,j})\geq k\\\
0,(G_{i,j}+G^{e}_{i,j})<k\end{cases}.$ (8)

The attention maps within RoI masks are obtained by element-wise
multiplication as follows:

$\small R=G\odot M,\quad R^{e}=G^{e}\odot M.$ (9)

The integration of RoI masks allows us to use equivalent texts for mutual
supervision, refining and improving the accuracy and providing regularization
for the previously defined distance-based loss. Moreover, it could potentially
address errors owing to unknown or less common words by vocabulary expansion.
Presuming one of the textual expressions is known and correctly understood,
the model could extrapolate the meaning of the other equivalent expression via
weak supervision. To implement it, we first compute the mean
$\mu_{RoI},\mu_{RoI}^{e}$ and the standard deviation
$\sigma_{RoI},\sigma_{RoI}^{e}$ within the RoI as follows:

$\small\mu_{RoI}=\frac{\sum_{i,j}R_{i,j}}{\sum_{i,j}M_{i,j}},\mu_{RoI}^{e}=\frac{\sum_{i,j}R^{e}_{i,j}}{\sum_{i,j}M_{i,j}},$
(10)

$\displaystyle\sigma_{RoI}$
$\displaystyle=\sqrt{\frac{\sum_{i,j}M_{i,j}\cdot(R_{i,j}-\mu_{RoI})^{2}}{\sum_{i,j}M_{i,j}}},$
(11) $\displaystyle\sigma_{RoI}^{e}$
$\displaystyle=\sqrt{\frac{\sum_{i,j}M_{i,j}\cdot(R^{e}_{i,j}-\mu_{RoI}^{e})^{2}}{\sum_{i,j}M_{i,j}}}.$

We propose a consistency loss ($\mathcal{L}_{\mathrm{cst}}$), expecting the
RoI regions of attention maps to achieve consistently high scores, further
reinforcing self-consistency, accuracy, and potential vocabulary expansion.
This objective is formulated as follows:

$\displaystyle\mathcal{L}_{\mathrm{cst}}=$
$\displaystyle\mathbb{E}_{(V,T,T^{e})\sim
D^{\prime}}\biggl{[}\sigma_{RoI}+\sigma_{RoI}^{e}+$ (12)
$\displaystyle\mathrm{max}(0,{k}/{2}-\mu_{RoI})+\mathrm{max}(0,{k}/{2}-\mu_{RoI}^{e})\biggr{]}.$

Finally, the objective of our self-consistency equivalence tuning is expressed
as:

$\small\mathcal{L}_{\mathrm{SelfEQ}}=\mathcal{L}_{\mathrm{sim}}+\lambda\cdot\mathcal{L}_{\mathrm{cst}},$
(13)

where $\lambda$ is a hyperparameter to control the relative influence of each
loss.

###  3.3 Self-Consistency Data Augmentation

In this section we define a function $\mathcal{F}$ that can automatically map
input textual phrases $T$ as paraphrases $T^{e}$ without the need to rely on
human annotations such that $T^{e}\sim\mathcal{F}(T)$. We achieve this goal
through a two-level prompting approach using a large language model which we
describe in detail below.

Phrase Chunking:  Using our first-level prompts, we aim to augment the
original text using phrase chunking to encourage global captions to
concentrate on more specific regions. Visual grounding seeks to localize
objects in images based on textual inputs. In contrast, global captions
usually describe the entire image, typically describing several objects. While
training on global captions could be beneficial for learning cross-modal
information, it may lead the model to predict a broader region (i.e., global
context) rather than a specific region. Phrase chunking (i.e., shallow parsing
[57]) aims to identify continuous sequences of tokens representing syntactic
units, enabling the extraction of phrases from unstructured text. We leverage
an LLM to segment global captions into object-centric short phrases. During
training, we use these image-chunk pairs instead of global captions,
effectively guiding the model attention toward localized regions of interest.
We _refer the reader to the supplementary material for prompting details and
generated examples._

Paraphrase Generation:  Our SelfEQ approach involves feeding the model with
pairs of textual descriptions that refer to the same underlying concept, with
the expectation that the model can make similar predictions for these
equivalent description pairs $\langle T,T^{e}\rangle$. We augment our dataset
by transforming the region-based captions (i.e., text that only refers to a
region in the image) and the object-centric short phrases we obtained from
phrase chunking into equivalent paraphrases referring to the same concept
through our second-level LLM-prompts.

There are many ways to paraphrase, including substituting words, altering
sentence structures, and rewriting sentences based on semantics. However,
considering that self-consistency in vision and language is relatively under-
explored, we adopt a straightforward strategy: Replacing the primary object in
the sentence while retaining all other attributes. This strategy yields
several benefits. First, it provides a consistent context, which serves as a
reference for the model to identify equivalent descriptions. This enables the
equivalent relationships of paraphrases to be learned intuitively. Second, it
simplifies prompt designing and post-processing by detecting the primary
object and generating its synonym.

To generate paraphrases for the dataset consisting of region-based captions,
we select four textual descriptions in which the primary noun plays different
syntactic roles. We further select two non-sentence phrases as examples of
query texts in our prompts. We show an example of a region-based caption and a
non-sentence phrase in Figure 3. To design our prompt, we identify the primary
object in the query text Q. Then we use WordNet [39] to obtain synonyms
automatically and further remove inaccurate or invalid words. We add A to
indicate the expected answer and include other relationships such as antonym,
hypernym and meronym to provide richer contexts for LLM in-context learning.
_Additional prompting details and paraphrase samples are provided in the
supplementary material._

This two-level prompt-based LLM augmentation approach ensures that our model
is exposed to textual inputs that share the same concept while varying in
linguistic representation, thereby promoting self-consistency and working
vocabulary expansion.

Figure 3:  Two samples from our LLM-prompt for paraphrase generation. The first set showcases an example of a region-based caption, and the second set shows a non-sentence phrase. Q is the query text and A is the expected answer.  | Method | Training | Flickr30k | ReferIt
---|---|---|---|---
Box Supervision | Align2Ground [8] | VG-boxes | 71.00 | -
12-in-1 [37] | VG-boxes | 76.40 | -
InfoGround [20] | VG-boxes | 76.74 | -
VMRM [13] | VG-boxes | 81.11 | -
AMC [53] | VG-boxes | 86.59 | 73.17
Without Box Supervision |  TD [58] | VG | 42.40 | 31.97
SSS [21] | VG | 49.10 | 39.98
MG-BiLSTM [2] | VG | 57.91 | 62.76
MG-ELMo [2] | VG | 60.08 | 60.01
GbS [3] | VG | 73.39 | 62.24
g [47] | VG | 75.63 | 65.95
g++ [46] | VG | 79.95 | 70.25
$\mathrm{SelfEQ}$ (ours) | VG | 81.90 | 67.40
FCVC [14] | MS-COCO | 29.03 | 33.52
MG-BiLSTM [2] | MS-COCO | 53.29 | 47.89
MG-ELMo [2] | MS-COCO | 61.66 | 47.52
GbS [3] | MS-COCO | 74.50 | 49.26
g [47] | MS-COCO | 75.43 | 61.03
g++ [46] | MS-COCO | 78.10 | 61.53
$\mathrm{SelfEQ}$ (ours) | MS-COCO | 84.07 | 62.75
Table 1: Visual Grounding results on two benchmarks using pointing game
accuracy with two training datasets. SelfEQ yields generally the best overall
performance among weakly-supervised methods, and comes second to g++ on the
ReferIt benchmark when trained using VG. We also show at the top the results
of methods using additional box supervision from Visual Genome (VG) either
directly or through an object detector.

##  4 Experimental Settings

#### Training.

We use ALBEF [28] as our base model in all our experiments, given its reported
off-the-shelf visual grounding performance via GradCAM [45]. ALBEF combines a
ViT-B [12] model for encoding images and a BERTbase [11] model for encoding
text. It is pre-trained on a range of datasets, including ImageNet-1K [44],
Conceptual Captions [48], SBU Captions [41], MS-COCO [35], and Visual Genome
(VG) [27] excluding box annotations. We finetune ALBEF with image-text pairs
from VG and MS-COCO without any type of box supervision (i.e., no bounding
boxes or object detectors), following prior work [2]. We further leverage
Vicuna-13B [7] as our LLM-prompting model to generate the object-centric short
phrases (via shallow parsing or chunking) and the equivalent paraphrases for
our self-consistency data augmentation. Additionally, we validate the
effectiveness of our SelfEQ tuning and self-consistency data augmentation
method by training on a preprocessed subset of the Conceptual Captions 3M
(CC3M) dataset [48], which contains many noisy or unaligned web-crawled
AltText-image pairs. With this subset, we achieve an absolute improvement of
2.15% on Flickr30k, 3.32% on ReferIt, and 1.33% on RefCOCO+; _refer to the
supplementary material for detailed CC3M experiments._

#### Evaluation.

We conduct evaluations using Flickr30k [42] and ReferIt [25] under pointing
game accuracy following previous weakly-supervised visual grounding works [2,
3]. To underscore the competitive edge of our method, we also present its
performance on RefCOCO+ [55], a challenging benchmark more commonly used for
testing box-supervised methods [8, 37, 13, 20, 53].

###  4.1 Implementation Details

Our experiments are conducted on a single computing node with 8 NVIDIA A40
GPUs. During the training phase, input images are resized to $256\times 256$
and augmented with horizontal flipping, color jittering, and random grayscale
conversion. We set up an Adam optimizer [26] with a learning rate of 1e-5 and
a batch size of 448 across all experiments. We empirically set the RoI
threshold $k$ to 0.8 and the hyperparameter $\lambda$ to 1.0. For training
with raw image-text pairs from the datasets, we employ the vision-language
objective $\mathcal{L}_{\mathrm{vl}}$ (Sec. 3.1), while for the subset with
equivalent paraphrases, we use our self-consistency equivalence tuning
objective $\mathcal{L}_{\mathrm{SelfEQ}}$ (Sec. 3.2) and corresponding vision-
language objective $\mathcal{L}_{\mathrm{vl}}^{e}$. The composite objective
function is given by
$\mathcal{L}=\alpha\cdot\mathcal{L}_{\mathrm{vl}}+(1-\alpha)\cdot(\mathcal{L}_{\mathrm{SelfEQ}}+\mathcal{L}_{\mathrm{vl}}^{e})$,
where $\alpha$ is initially set to 0 and increments to 1, remaining constant
after the second epoch. Our hyperparameter values and schedules were
determined empirically on a small validation subset.

Method | Box Supervision | RefCOCO+
---|---|---
Test A | Test B
InfoGround [20] | Yes | 39.80 | 41.11
VMRM [13] | Yes | 58.87 | 50.32
AMC [53] | Yes | 80.34 | 64.55
ALBEF [28] | No | 69.35 | 53.77
$\mathrm{SelfEQ}$ (ours) | No | 75.10 | 55.49
Table 2: Results on RefCOCO+ pointing game accuracy. SelfEQ shows significant
improvements over off-the-shelf ALBEF and competitive results compared to box-
supervised methods.

##  5 Experimental Results

Our resulting model obtains the best performance on the task of weakly-
supervised visual grounding compared to most methods under this setting and is
comparable to several prior works that rely on some of box supervision.
Moreover, our qualitative results show that our method can handle paraphrases
and a larger vocabulary without the needed to increment the training dataset
significantly.

Flickr30k and ReferIt. We evaluate the effectiveness of our proposed SelfEQ
method in Table 1, demonstrating its substantial lead over GradCAM-based
weakly-supervised approaches. Our self-consistency equivalent tuning adapts
well for both region-based (i.e.,, VG) and global-based (i.e.,, COCO) image-
text pairs, yielding a performance gain of 4.69% on Flickr30k and 7.68% on
ReferIt, compared to our base model ALBEF (see first row in Table 3). Notably,
our method outperforms almost all box-supervised methods on Flickr30k [8, 37,
20, 13]. In the weakly-supervised setting, our method only comes second on
ReferIt compared to g++[46] when trained on Visual Genome image-text pairs.
This method leverages a custom architecture to produce a mask and uses heatmap
supervision from a CLIP [43] model as pseudo-labels during training. We posit
that our contribution is orthogonal and our approach would likely also benefit
from similar supervision, since CLIP is trained in a much larger image-text
pair dataset. Despite differences, our method still obtains higher performance
when trained on MS-COCO and the best performance compared to all weakly-
supervised methods on Flickr30K region-phrase grounding.

Figure 4: Qualitative results of our method in challenging visual grounding
scenarios compared to prior works. On top of each row we show the reference
text, the first column shows the image, then we show our base model ALBEF, the
SotA box-supervised method AMC, and finally we show results with our method
SelfEQ.

RefCOCO+. RefCOCO+ [55] serves as a rigorous benchmark for visual grounding,
typically used to evaluate box-supervised techniques. In Table 2, we present
the performance of our weakly-supervised method (VG trained) against box-
supervised methods. Our results indicate that our approach is competitive
without reliance on any form of box annotations and significantly improves
over the base ALBEF model.

Visual Grounding Analysis. Figure 4 provides qualitative results of our method
in challenging scenarios, including occluded objects (row 1), small objects
within complex scenes (row 2), objects partially shown in the corner of the
image (row 3), multiple similar objects (row 4), and abbreviated text inputs
(row 5). Our self-consistency equivalency tuning approach exhibits substantial
improvements in the grounding capability of the base ALBEF [28] model.
Remarkably, our approach even outperforms the state-of-the-art box-supervised
method AMC [53] in multiple scenarios.

Self-Consistency Analysis. Figure 5 demonstrates qualitative results for the
self-consistency capability across different equivalent paraphrases,
encompassing terminology (row 1), synonym substitutions (row 2), and regional
slang combining with different sentence structures (row 3). Although other
methods succeed in localizing certain phrases, they demonstrate
inconsistencies for the equivalent paraphrases. In contrast, our model
finetuned with SelfEQ effectively establishes connections between semantically
equivalent paraphrases, thereby enhancing the model self-consistency ability
and potentially expanding its vocabulary.

Figure 5: Qualitative results of self-consistency across different equivalent paraphrases among different methods. For each image, we show a text caption referring to an object in the first row and an equivalent paraphrase in the second row. Each column shows the results of our base model ALBEF, the SotA box-supervised method AMC, and our SelfEQ method. Data | Objective | RefCOCO+ | Flickr30k | ReferIt
---|---|---|---|---
Test A | Test B
- | $\mathcal{L}_{\mathrm{vl}}$ | 69.35 | 53.77 | 79.38 | 59.72
$T$ | $\mathcal{L}_{\mathrm{vl}}$ | 72.30 | 54.22 | 78.75 | 65.86
$T$ \+ $T^{e}$ | $\mathcal{L}_{\mathrm{vl}}$ | 71.55 | 53.51 | 78.05 | 64.57
$T$ \+ $T^{e}$ | $\mathcal{L}_{\mathrm{SelfEQ}}$ | 75.10 | 55.49 | 81.90 | 67.40
Table 3: Ablation studies on different ways to utilize extra equivalent
paraphrased data. The first row is off-the-shelf ALBEF performance before
tuning. $T$ denotes the textual captions from the dataset, and $T^{e}$
corresponds to the associated equivalent paraphrases.
$\mathcal{L}_{\mathrm{vl}}$ is the vision-language objective, and
$\mathcal{L}_{\mathrm{SelfEQ}}$ is our self-consistency equivalence tuning
objective.

###  5.1 Ablation Studies

Data Quantity. We conduct experiments to investigate the impact of the data
quantity of our generated equivalent paraphrases and compare our self-
consistency equivalence tuning strategy against vision-language objectives. We
randomly sample portions of data from VG by 10% associated with our augmented
equivalent paraphrases three times. To compare, we use the vision-language
objective with VG text-image pairs as baselines. In Figure 6, we show the mean
and standard deviation pointing game accuracy. The performance of the base
vision-language objective does not exhibit a steady improvement with more
text-image pairs. Although ReferIt performance increases, the performance on
RefCOCO+ Test A remains mostly unchanged. Additionally, the performance on
Flickr30k notably decreases, and there is a mixed effect on RefCOCO+ Test B,
with half of the accuracy falling below the off-the-shelf ALBEF performance of
53.77%.

Figure 6: Tuning performance with different data quantities on Flickr30k,
ReferIt, RefCOCO+ Test A and Test B. The purple and cyan lines represent
SelfEQ (ours) and ALBEF baseline losses (vision-language objective),
respectively. We show the impact of progressively augmenting captions via LLM-
prompting for generating equivalent paraphrases tuned with our SelfEQ
objective. Best viewed in color.

In contrast, SelfEQ consistently leads to performance enhancements with more
equivalent paraphrases. Clear upward trends are observed on Flickr30k,
ReferIt, and RefCOCO+ Test A as more data with corresponding equivalent
paraphrases are added, meanwhile the gaps between the baselines generally
widen. Notably, SelfEQ tuning maintains performance gains on Flickr30k,
whereas the baselines performances drop. Although the trend on RefCOCO+ Test B
is not consistently increasing, it is essential to emphasize that RefCOCO+
Test B is only a subset, and SelfEQ illustrates more stable and effective
tuning performance on it, compared to the base vision-language objective.

These observations indicate that more equivalent paraphrases connecting with
associated text phrases enable the model to acquire more valuable information
during tuning. SelfEQ proves to be an effective and robust strategy for
consistently improving performance with our generated paraphrases. With
increased self-consistency augmented data, SelfEQ guides the model toward
better grounding performance by enhancing its self-consistency capabilities.

Our method generates equivalent paraphrases for self-consistency enhancement,
but it also contributes additional data for training. To ascertain the
specific impact of our SelfEQ tuning strategy, we run a control experiment on
this variable. As shown in Table 3, we assess the model’s performance when
equivalent paraphrases are integrated as regular image-text pairs with vision-
language objectives (Sec. 3.1). This comparison reveals that merely augmenting
the dataset with extra image-paraphrase pairs, without forming explicit
linkages between the original text and its paraphrases, does not yield
performance improvements.

Format | Objective | Flickr30k | ReferIt
---|---|---|---
- | $\mathcal{L}_{\mathrm{vl}}$ | 79.38 | 59.72
$C$ | $\mathcal{L}_{\mathrm{vl}}$ | 79.90 | 60.64
$C$ | $\mathcal{L}_{\mathrm{SelfEQ}}$ | 81.28 | 62.04
$P$ | $\mathcal{L}_{\mathrm{vl}}$ | 81.18 | 61.18
$P$ | $\mathcal{L}_{\mathrm{SelfEQ}}$ | 84.07 | 62.75
Table 4: Comparisons on data augmentation strategy for global-based captions
in MS-COCO with or without the paraphrases. $C$ is the global-based captions
from MS-COCO, and $P$ is our Vicuna-13B processed object-centric phrases
separately. The first row is the off-the-shelf ALBEF performance before
tuning.

Data Augmentation. For global-based captions in MS-COCO, we preprocess the
captions $C$ to object-centric short phrases $P$ via LLM-prompting. As shown
in Table 4, tuning with phrases $P$ leads to better performance, benefiting
both the vision-language objective ($\mathcal{L}_{\mathrm{vl}}$) and our self-
consistency equivalence tuning objective ($\mathcal{L}_{\mathrm{SelfEQ}}$).
This improvement is probably attributed to short phrases allowing the model to
focus on a specific region rather than the entire scene, aligning more closely
with the objective of visual grounding. By utilizing equivalent paraphrases
with our SelfEQ objective (row 3 and 5), phrase chunking helps SelfEQ even
more, indicating the important role of equivalent paraphrases in promoting
self-consistency and grounding ability.

Objective. Table 5 evaluates each component within our self-consistency
equivalence tuning objective. The $\mathcal{L}_{\mathrm{sim}}$ loss targets
pixel-wise similarity, ensuring that maps for a caption and its equivalent
paraphrase are identical. However, focusing solely on pixel-level similarity
may neglect the precise spatial positioning of objects. To address this, the
$\mathcal{L}_{\mathrm{cst}}$ loss is proposed to identify the most likely
correct object positions within the two maps (i.e., RoI). It then encourages
the model to yield consistently high attention scores within the RoI. By
integrating both $\mathcal{L}_{\mathrm{sim}}$ and
$\mathcal{L}_{\mathrm{cst}}$, self-consistency equivalence tuning objective
fosters the model to not only align global similarities but also to pinpoint
accurate object locations through the mutual supervision provided by a caption
and its paraphrase, thereby enhancing self-consistency and accuracy.

$\mathcal{L}_{\mathrm{sim}}$ | $\mathcal{L}_{\mathrm{cst}}$ | RefCOCO+ | Flickr30k | ReferIt
---|---|---|---|---
Test A | Test B
✓ |  | 66.42 | 47.21 | 68.26 | 55.96
| ✓ | 73.33 | 55.88 | 80.94 | 66.57
✓ | ✓ | 75.10 | 55.49 | 81.90 | 67.40
Table 5: Ablation studies on objective components of self-consistency
equivalence tuning objective $\mathcal{L}_{\mathrm{SelfEQ}}$.

##  6 Conclusion

In this paper, we propose a novel weakly-supervised tuning approach coupled
with a data augmentation strategy to enhance the localization capabilities of
a purely image-text pair supervised model through self-consistency. Using an
open-source LLM, we expand a dataset with equivalent paraphrases tailored to
be object-centric. The augmented data is used to finetune a base model
employing our novel self-consistency equivalence tuning objective. Our
approach has been rigorously validated across pretraining on diverse datasets,
ranging from region-based captions (i.e., VG) to global-based captions (i.e.,
COCO). Our method achieves superior and self-consistent performance on three
benchmarks and is even competitive with some box-supervised methods.

## References

  * Abnar and Zuidema [2020] Samira Abnar and Willem Zuidema.  Quantifying attention flow in transformers.  _arXiv preprint arXiv:2005.00928_ , 2020.
  * Akbari et al. [2019] Hassan Akbari, Svebor Karaman, Surabhi Bhargava, Brian Chen, Carl Vondrick, and Shih-Fu Chang.  Multi-level multimodal common semantic space for image-phrase grounding.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 12476–12486, 2019.
  * Arbelle et al. [2021] Assaf Arbelle, Sivan Doveh, Amit Alfassy, Joseph Shtok, Guy Lev, Eli Schwartz, Hilde Kuehne, Hila Barak Levi, Prasanna Sattigeri, Rameswar Panda, et al.  Detector-free weakly supervised grounding by separation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 1801–1812, 2021.
  * Brown et al. [2020] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Chefer et al. [2021] Hila Chefer, Shir Gur, and Lior Wolf.  Transformer interpretability beyond attention visualization.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 782–791, 2021.
  * Chen et al. [2020] Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu.  Uniter: Universal image-text representation learning.  In _European conference on computer vision_ , pages 104–120. Springer, 2020.
  * Chiang et al. [2023] Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, Ion Stoica, and Eric P. Xing.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, 2023.
  * Datta et al. [2019] Samyak Datta, Karan Sikka, Anirban Roy, Karuna Ahuja, Devi Parikh, and Ajay Divakaran.  Align2ground: Weakly supervised phrase grounding guided by image-caption alignment.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 2601–2610, 2019.
  * Deng et al. [2018] Chaorui Deng, Qi Wu, Qingyao Wu, Fuyuan Hu, Fan Lyu, and Mingkui Tan.  Visual grounding via accumulated attention.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 7746–7755, 2018.
  * Deng et al. [2021] Jiajun Deng, Zhengyuan Yang, Tianlang Chen, Wengang Zhou, and Houqiang Li.  Transvg: End-to-end visual grounding with transformers.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 1769–1779, 2021.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Dou and Peng [2021] Zi-Yi Dou and Nanyun Peng.  Improving pre-trained vision-and-language embeddings for phrase grounding.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 6362–6371, 2021.
  * Fang et al. [2015] Hao Fang, Saurabh Gupta, Forrest Iandola, Rupesh K Srivastava, Li Deng, Piotr Dollár, Jianfeng Gao, Xiaodong He, Margaret Mitchell, John C Platt, et al.  From captions to visual concepts and back.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 1473–1482, 2015.
  * Gao et al. [2022] Yuting Gao, Jinfeng Liu, Zihan Xu, Jun Zhang, Ke Li, and Chunhua Shen.  Pyramidclip: Hierarchical feature alignment for vision-language model pretraining.  _arXiv preprint arXiv:2204.14095_ , 2022.
  * Ghiasi et al. [2022] Golnaz Ghiasi, Xiuye Gu, Yin Cui, and Tsung-Yi Lin.  Scaling open-vocabulary image segmentation with image-level labels.  In _European Conference on Computer Vision_ , pages 540–557. Springer, 2022.
  * Goel et al. [2022] Shashank Goel, Hritik Bansal, Sumit Bhatia, Ryan A Rossi, Vishwa Vinay, and Aditya Grover.  Cyclip: Cyclic contrastive language-image pretraining.  _arXiv preprint arXiv:2205.14459_ , 2022.
  * Gomel et al. [2023] Eyal Gomel, Tal Shaharbany, and Lior Wolf.  Box-based refinement for weakly supervised and unsupervised localization tasks.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 16044–16054, 2023.
  * Gu et al. [2021] Xiuye Gu, Tsung-Yi Lin, Weicheng Kuo, and Yin Cui.  Open-vocabulary object detection via vision and language knowledge distillation.  _arXiv preprint arXiv:2104.13921_ , 2021.
  * Gupta et al. [2020] Tanmay Gupta, Arash Vahdat, Gal Chechik, Xiaodong Yang, Jan Kautz, and Derek Hoiem.  Contrastive learning for weakly supervised phrase grounding.  In _European Conference on Computer Vision_ , pages 752–768. Springer, 2020.
  * Javed et al. [2019] Syed Ashar Javed, Shreyas Saxena, and Vineet Gandhi.  Learning unsupervised visual grounding through semantic self-supervision.  _Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI)_ , 2019.
  * Jia et al. [2021a] Chao Jia, Yinfei Yang, Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoc Le, Yun-Hsuan Sung, Zhen Li, and Tom Duerig.  Scaling up visual and vision-language representation learning with noisy text supervision.  In _International conference on machine learning_ , pages 4904–4916. PMLR, 2021a.
  * Jia et al. [2021b] Chao Jia, Yinfei Yang, Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoc V. Le, Yun-Hsuan Sung, Zhen Li, and Tom Duerig.  Scaling up visual and vision-language representation learning with noisy text supervision.  In _International Conference on Machine Learning_ , 2021b.
  * Kamath et al. [2021] Aishwarya Kamath, Mannat Singh, Yann LeCun, Gabriel Synnaeve, Ishan Misra, and Nicolas Carion.  Mdetr-modulated detection for end-to-end multi-modal understanding.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 1780–1790, 2021.
  * Kazemzadeh et al. [2014] Sahar Kazemzadeh, Vicente Ordonez, Mark Matten, and Tamara Berg.  Referitgame: Referring to objects in photographs of natural scenes.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 787–798, 2014.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Krishna et al. [2017] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, et al.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  _International journal of computer vision_ , 123:32–73, 2017.
  * Li et al. [2021a] Junnan Li, Ramprasaath Selvaraju, Akhilesh Gotmare, Shafiq Joty, Caiming Xiong, and Steven Chu Hong Hoi.  Align before fuse: Vision and language representation learning with momentum distillation.  _Advances in Neural Information Processing Systems_ , 34, 2021a.
  * Li et al. [2022a] Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi.  Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.  _arXiv preprint arXiv:2201.12086_ , 2022a.
  * Li et al. [2023] Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi.  Blip-2: Bootstrapping language-image pre-training with frozen image encoders and large language models.  _arXiv preprint arXiv:2301.12597_ , 2023.
  * Li et al. [2019] Liunian Harold Li, Mark Yatskar, Da Yin, Cho-Jui Hsieh, and Kai-Wei Chang.  Visualbert: A simple and performant baseline for vision and language.  _arXiv preprint arXiv:1908.03557_ , 2019.
  * Li et al. [2022b] Liunian Harold Li, Pengchuan Zhang, Haotian Zhang, Jianwei Yang, Chunyuan Li, Yiwu Zhong, Lijuan Wang, Lu Yuan, Lei Zhang, Jenq-Neng Hwang, et al.  Grounded language-image pre-training.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10965–10975, 2022b.
  * Li et al. [2022c] Liunian Harold Li, Pengchuan Zhang, Haotian Zhang, Jianwei Yang, Chunyuan Li, Yiwu Zhong, Lijuan Wang, Lu Yuan, Lei Zhang, Jenq-Neng Hwang, et al.  Grounded language-image pre-training.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10965–10975, 2022c.
  * Li et al. [2021b] Yangguang Li, Feng Liang, Lichen Zhao, Yufeng Cui, Wanli Ouyang, Jing Shao, Fengwei Yu, and Junjie Yan.  Supervision exists everywhere: A data efficient contrastive language-image pre-training paradigm.  _arXiv preprint arXiv:2110.05208_ , 2021b.
  * Lin et al. [2014] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13_ , pages 740–755. Springer, 2014.
  * Lu et al. [2019] Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee.  Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks.  _Advances in neural information processing systems_ , 32, 2019.
  * Lu et al. [2020] Jiasen Lu, Vedanuj Goswami, Marcus Rohrbach, Devi Parikh, and Stefan Lee.  12-in-1: Multi-task vision and language representation learning.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 10437–10446, 2020.
  * Lüddecke and Ecker [2022] Timo Lüddecke and Alexander Ecker.  Image segmentation using text and image prompts.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 7086–7096, 2022.
  * Miller [1995] George A Miller.  Wordnet: a lexical database for english.  _Communications of the ACM_ , 38(11):39–41, 1995.
  * Montavon et al. [2017] Grégoire Montavon, Sebastian Lapuschkin, Alexander Binder, Wojciech Samek, and Klaus-Robert Müller.  Explaining nonlinear classification decisions with deep taylor decomposition.  _Pattern recognition_ , 65:211–222, 2017.
  * Ordonez et al. [2011] Vicente Ordonez, Girish Kulkarni, and Tamara Berg.  Im2text: Describing images using 1 million captioned photographs.  _Advances in neural information processing systems_ , 24, 2011.
  * Plummer et al. [2015] Bryan A Plummer, Liwei Wang, Chris M Cervantes, Juan C Caicedo, Julia Hockenmaier, and Svetlana Lazebnik.  Flickr30k entities: Collecting region-to-phrase correspondences for richer image-to-sentence models.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2641–2649, 2015.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.  Learning transferable visual models from natural language supervision.  In _Proceedings of the 38th International Conference on Machine Learning_ , pages 8748–8763. PMLR, 2021.
  * Russakovsky et al. [2015] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  _International journal of computer vision_ , 115:211–252, 2015.
  * Selvaraju et al. [2017] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In _Proceedings of the IEEE international conference on computer vision_ , pages 618–626, 2017.
  * Shaharabany and Wolf [2023] Tal Shaharabany and Lior Wolf.  Similarity maps for self-training weakly-supervised phrase grounding.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6925–6934, 2023.
  * Shaharabany et al. [2022] Tal Shaharabany, Yoad Tewel, and Lior Wolf.  What is where by looking: Weakly-supervised open-world phrase-grounding without text inputs.  _Advances in Neural Information Processing Systems_ , 35:28222–28237, 2022.
  * Sharma et al. [2018] Piyush Sharma, Nan Ding, Sebastian Goodman, and Radu Soricut.  Conceptual captions: A cleaned, hypernymed, image alt-text dataset for automatic image captioning.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2556–2565, 2018.
  * Singh et al. [2022] Amanpreet Singh, Ronghang Hu, Vedanuj Goswami, Guillaume Couairon, Wojciech Galuba, Marcus Rohrbach, and Douwe Kiela.  Flava: A foundational language and vision alignment model.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 15638–15650, 2022.
  * Wang and Specia [2019] Josiah Wang and Lucia Specia.  Phrase localization without paired training examples.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 4663–4672, 2019.
  * Xiao et al. [2017] Fanyi Xiao, Leonid Sigal, and Yong Jae Lee.  Weakly-supervised visual grounding of phrases with linguistic structures.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5945–5954, 2017.
  * Xu et al. [2022] Jiarui Xu, Shalini De Mello, Sifei Liu, Wonmin Byeon, Thomas Breuel, Jan Kautz, and Xiaolong Wang.  Groupvit: Semantic segmentation emerges from text supervision.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 18134–18144, 2022.
  * Yang et al. [2023] Ziyan Yang, Kushal Kafle, Franck Dernoncourt, and Vicente Ordonez.  Improving visual grounding by encouraging consistent gradient-based explanations.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 19165–19174, 2023.
  * Yao et al. [2021] Lewei Yao, Runhui Huang, Lu Hou, Guansong Lu, Minzhe Niu, Hang Xu, Xiaodan Liang, Zhenguo Li, Xin Jiang, and Chunjing Xu.  Filip: Fine-grained interactive language-image pre-training.  _arXiv preprint arXiv:2111.07783_ , 2021.
  * Yu et al. [2016] Licheng Yu, Patrick Poirson, Shan Yang, Alexander C Berg, and Tamara L Berg.  Modeling context in referring expressions.  In _Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part II 14_ , pages 69–85. Springer, 2016.
  * Zareian et al. [2021] Alireza Zareian, Kevin Dela Rosa, Derek Hao Hu, and Shih-Fu Chang.  Open-vocabulary object detection using captions.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 14393–14402, 2021.
  * Zhai et al. [2017] Feifei Zhai, Saloni Potdar, Bing Xiang, and Bowen Zhou.  Neural models for sequence chunking.  In _Proceedings of the AAAI conference on artificial intelligence_ , 2017.
  * Zhang et al. [2018] Jianming Zhang, Sarah Adel Bargal, Zhe Lin, Jonathan Brandt, Xiaohui Shen, and Stan Sclaroff.  Top-down neural attention by excitation backprop.  _International Journal of Computer Vision_ , 126(10):1084–1102, 2018.

## Appendix

We present details about our two-level LLM prompts to obtain high-quality
paraphrases for region-centric phrases, provide examples of such extracted
paraphrases, conduct additional evaluations on in-the-wild captions on CC3M,
justify our selection of ALBEF as our base model, evaluate in more detail the
choice of object-centric captions, and provide additional qualitative results.

##  Appendix A LLM-Prompting Details

This section presents prompting details and generated examples of our proposed
two-level self-consistency data augmentation method (refer to Section 3.3 in
the main text). As shown in Figure 7, we classify textual annotations from
existing datasets into global-based captions that describe the entire image,
and region-based captions that describe a specific region within the image. In
our experiments, we identify captions from Visual Genome (VG) [27] as region-
based captions, while captions from MS-COCO [35] and Conceptual Captions 3M
(CC3M) [48] are referred to as global-based captions.

Figure 7: An overview of our two-level self-consistency data augmentation
approach. For global-based captions, we use an LLM to chunk object-centric
phrases $T$ with our first-level prompting. The obtained phrases or region-
based captions $T$ are further input to an LLM in the second-level prompting
to obtain equivalent paraphrases $T^{e}$.

###  A.1 Prompt Design

We adopt an in-context learning [4] strategy in our LLM-prompt design. Each
pair of our prompts encompasses a query text Q and an expected answer A. The
query texts Q were selected and modified based on generation quality and
successful rate on a small validation subset.

#### Phrase Chunking.

To obtain object-centric phrases, we prompt an LLM for global-based captions
as shown in Figure 8. Compared to previous phrase chunking methods [57], this
LLM-prompt-based approach aligns more closely with our objective. In
conventional phrase chunking, the output chunks include nouns, verbs, and
prepositional phrases. However, our SelfEQ method focuses on object-centric
phrases rather than verbs or prepositions. Additionally, there are some
abstract nouns such as “photo”, “image” and “scene” that are commonly used in
annotations but do not benefit visual grounding. We select several captions
containing abstract nouns, verbs, and prepositions as our query texts in our
prompts to guide the LLM to generate the chunks in a task-specific way.

Figure 8: In-context few-shot LLM-Prompt for our first-level self-consistency
data augmentation. We leverage an LLM for phrase chunking to obtain object-
centric captions from captions that describe images globally. $[T]$ is the
query text. A in the last row is followed by the output.

#### Paraphrase Generation.

Our second-level prompts aim to generate paraphrased captions through
substitute words and for this purpose we use an in-context few-shot prompt
with an LLM. Figure 9 shows the specific prompt we use for input region-based
captions. As in-context examples, we select four captions with different
sentence structures or where the primary object is playing different syntactic
roles: A complex noun phrase (set 1), an existential structure (set 3), a
subject followed by a passive verb phrase (set 4), and a noun phrase modified
by a prepositional phrase (set 6). We also add two short noun phrases (sets 2,
5) to represent relevant captions. For the expected output A, we first detect
the primary object (_i.e_., the “group” field) in the query text, then use
WordNet synsets [39] to generate relationships (_i.e_., the “synonym”,
“antonym”, “hypernym”, and “meronym” fields) for the primary object. We
further remove inaccurate words as the final expected output A in our LLM-
prompt.

Figure 9: In-context few-shot LLM-Prompt for our second-level self-consistency
data augmentation on Visual Genome (VG). We leverage an LLM to generate
paraphrases for the given textual descriptions (region-based captions). $[T]$
is the regional-based caption, and A in the last row is followed by the
expected output.

Figure 10 shows our in-context few-shot LLM-prompt for object-centric phrases
obtained from our first-level data augmentation. It is based on our LLM-prompt
for region-based captions (Figure 9), but we further chunk the query texts
into object-centric phrases for adaption and modify them (_e.g_., articles,
pronouns) empirically on a small validation subset.

Figure 10: In-context few-shot LLM-Prompt for our second-level self-
consistency data augmentation on MS-COCO. We leverage an LLM to generate
paraphrases for the given textual descriptions (object-centric phrases). $[T]$
is the object-centric phrase obtained from the first-level phrase chunking. A
in the last row is followed by the expected output.

###  A.2 Generated Data Examples

This section presents generated examples from our two-level self-consistency
augmentation approach. We apply paraphrase generation for VG and both phrase
chunking and paraphrase generation for MS-COCO and CC3M.

#### Visual Genome.

Figure 11 shows generated example paraphrases for VG. Since our LLM-prompt
contains various sentence structures in the provided in-context examples, the
generated data showcases the successful detection of primary objects (“group”)
for a variety of input captions. To ensure the quality of equivalent
paraphrases, we allow the LLM to leave blanks in relevant fields if no
appropriate words are available. In total, the LLM generates equivalent
paraphrases for 74.56% of captions for VG. The different types of equivalent
paraphrases include general synonyms (_e.g_., “bicycle”, “sofa”), formal or
technical terms (_e.g_., “pedal cycle”), colloquial or regional variants
(_e.g_., “pushbike”, “settee”) and descriptive synonyms (_e.g_., “scattered
trees”).

Figure 11: LLM generated examples for VG. Q represents the query text
associated with the image. A corresponds to the output of our second-level
self-consistency data augmentation. “group” denotes the detected primary
object, and it further generates relationships such as “synonym,” “antonym,”
“meronym,” and “hypernym” regarding with the identified “group.”

Figure 12: LLM generated examples for MS-COCO. Q represents the query text
associated with the image. A1 is the object-centric phrase obtained from the
first-level self-consistency data augmentation, while A2 corresponds to the
second level. For each object-centric phrase in A1, LLM detects primary
objects “group” and generates relevant relationships in A2.

Figure 13: LLM generated examples for CC3M. Q represents the query text
associated with the image. A1 is the object-centric phrase obtained from the
first-level self-consistency data augmentation, while A2 corresponds to the
second level. For each object-centric phrase in A1, LLM detects primary
objects “group” and generates relevant relationships in A2.

#### MS-COCO.

Generated examples for MS-COCO are shown in Figure 12. Captions in MS-COCO
describe the entire images, so we augment them with our two-level phrase
augmentation: Phrase chunking and equivalent paraphrase generation. In the
first level, we prompt an LLM to generate object-centric phrases A1. In this
way, we separate a broad descriptive region into several specific object-
centric regions in a scenario, aligning more closely with the objective of
visual grounding. Additionally, it may fix small issues with grammar and typos
(_e.g_., “siting at there desks”), potentially providing higher quality
textual descriptions. Similar to VG, the second level prompting leads to
equivalent paraphrases A2, including diverse types for 84.47% of object-
centric phrases.

#### CC3M.

Figure 13 showcases generated data from two-level self-consistency data
augmentation for CC3M. Compared to manually annotated data from VG and MS-COCO
(See Figures 11 and 12), web-crawled Alt-Text-image pairs in CC3M are noisier
and potentially unaligned. We apply our first-level augmentation, phrase
chunking A1, not only for object-centric phrases, but also as a filtering
strategy to extract meaningful words from likely ambiguous sentences. The
second-level augmentation further generates equivalent paraphrases A2 for our
SelfEQ tuning.

##  Appendix B Effectiveness on Noisy Web-Crawled Data

We run additional experiments using two different subsets of data from the
CC3M dataset, each containing $\sim$$200k$ image-text pairs. The first subset,
which we refer to as ranked, corresponds to a set of high-quality image-text
pairs filtered using the image-text matching score yield by the base ALBEF
model. The second subset, which we refer to as random, corresponds to a
randomly selected set of arbitrary image-text pairs. We further generate
paraphrases for each text caption using our two-level LLM-based augmentation
and train our base model using the ALBEF baseline losses and our SelfEQ
approach. Table 6 shows the effectiveness of our method with noisy web-crawled
data.

Objective |  Data Selection | RefCOCO+ | Flickr30k | ReferIt
---|---|---|---|---
Test A | Test B
$\mathcal{L}_{\mathrm{vl}}$ | - | 69.35 | 53.77 | 79.38 | 59.72
$\mathcal{L}_{\mathrm{vl}}$ | ranked | 68.51 | 52.23 | 78.61 | 59.48
$\mathcal{L}_{\mathrm{vl}}$ | random | 69.40 | 52.83 | 79.76 | 60.78
$\mathcal{L}_{\mathrm{SelfEQ}}$ | ranked | 70.21 | 53.75 | 80.91 | 61.00
$\mathcal{L}_{\mathrm{SelfEQ}}$ | random | 71.59 | 54.19 | 81.53 | 63.04
Table 6:  Visual Grounding results when training with a subset of Conceptual
Captions 3M (CC3M). The ranked subset corresponds to a set of image-text pairs
filtered using the image-text matching score yielded by the base ALBEF. The
random subset corresponds to a randomly selected subset. Applying SelfEQ on a
random but relatively more noisy subset yields the best results.

##  Appendix C Base Model Selection

We choose ALBEF [28] as our base model based on the off-the-shelf visual
grounding ability through GradCAM under the pointing game setting as reported
in the original work. We further compare it with the off-the-shelf performance
of BLIP [29] and BLIP-2 [30] for reference. As shown in Table 7, ALBEF
outperforms other methods by a large margin on visual grounding.

Method | RefCOCO+ | Flickr30k | ReferIt
---|---|---|---
Test A | Test B
BLIP [29] | 61.23 | 41.07 | 60.56 | 45.81
BLIP-2 [30] | 50.09 | 42.26 | 64.86 | 45.34
ALBEF [28] | 69.35 | 53.77 | 79.38 | 59.72
Table 7: Pointing game accuracy comparisons with other pre-trained vision-
language models on off-the-shelf visual grounding via GradCAM.

##  Appendix D Object-Centric vs. Global-Based Captions

Table 8 shows the effect of different ways of chunking global-based captions.
In our main paper, we demonstrate that shorter captions that are more object-
specific lead to better results. Here we provide an additional chunking
strategy that leads to captions that have a length between our short object-
centric phrases $P$ and the original long captions $C$, showing the benefits
of gradually using shorter captions that are more likely to be object-centric.
Specifically, we compare MS-COCO captions $C$ and object-centric phrases $P$
with long phrases $P^{\prime}$ whose length is between global captions and
object-centric phrases. As shown in Figure 14, long phrases $P^{\prime}$
shorten the captions $C$ by removing compound or descriptive sentences, while
they still remain simple compositions compared to object-centric phrases $P$.
Rows 4 and 5 in Table 8 supplement experiments in Table 4 in the main paper,
demonstrating an increasing trend when more object-centric (_i.e_., shorter).
Notably, SelfEQ improves all formats of input text ($C$, $P^{\prime}$, $P$)
compared to the base model and the vision-and-language objective
($\mathcal{L}_{\mathrm{vl}}$).

Figure 14: LLM-Prompt for an alternative first-level self-consistency data augmentation (i.e., phrase chunking) strategy. In contrast to object-centric phrases, the expected answer A further includes simple compositions. Format | Objective | Flickr30k | ReferIt
---|---|---|---
- | $\mathcal{L}_{\mathrm{vl}}$ | 79.38 | 59.72
$C$ | $\mathcal{L}_{\mathrm{vl}}$ | 79.90 | 60.64
$C$ | $\mathcal{L}_{\mathrm{SelfEQ}}$ | 81.28 | 62.04
$P^{\prime}$ | $\mathcal{L}_{\mathrm{vl}}$ | 80.42 | 60.83
$P^{\prime}$ | $\mathcal{L}_{\mathrm{SelfEQ}}$ | 82.09 | 62.12
$P$ | $\mathcal{L}_{\mathrm{vl}}$ | 81.18 | 61.18
$P$ | $\mathcal{L}_{\mathrm{SelfEQ}}$ | 84.07 | 62.75
Table 8: Trade-off between object-centric and rich context. The first row is
the off-the-shelf base model performance. $C$ is the caption, $P$ is the
object-centric phrase. $P^{\prime}$ is the long phrase, which can be defined
as a shortened caption or an object-centric phrase with simple compositions.

###  D.1 Qualitative Results

Figure 15: Qualitative comparisons on visual grounding. The reference text is
on the top of each row. From left to right, it presents the image, our base
model ALBEF, SotA box-supervised method AMC, and our method SelfEQ. Figure 16:
Qualitative comparisons on self-consistency. For each image, the first row is
the reference text, and the second row is the equivalent paraphrase. Each
column presents our base model ALBEF, SotA box-supervised method AMC, and our
method SelfEQ.

#### Visual Grounding.

Figure 15 presents more qualitative results for visual grounding than those
shown in the main paper. SelfEQ excels in localizing input textual
descriptions across a variety of challenging scenarios, including objects with
prepositions (rows 1 to 4), intricate background context (row 5), numerical
answers (row 6), distinguishing a single descriptive object from multiple
similar ones (rows 7 and 8), dealing with occluded objects (row 9), and
handling tiny objects (row 10). SelfEQ improves visual grounding through self-
consistency tuning without any bounding boxes, while still achieving
competitive performance compared to the state-of-the-art box-supervised method
AMC.

#### Self-Consistency.

Figure 16 shows more qualitative results, showcasing that our method generates
more consistent results for paraphrases. SelfEQ leads to consistent results
for various challenging scenarios such as handling general synonyms (row 1),
synonym substitution (row 2), terminology and sentence extension (row 3),
attributive and head noun substitution (row 4), multiple synonym substitution
(row 5), and phrase-to-word transformation (row 6). Although our self-
consistency data augmentation concentrates on synonym substitution, SelfEQ
shows robust self-consistency in dealing with some non-trivial equivalent
paraphrases.

##  Appendix E Limitations and Future Work

We demonstrate that generating paraphrases based on noun substitutions leads
to relatively reliable paraphrases. However, paraphrases generated in this way
can be limited in terms of their diversity and complexity. Although our work
shows encouraging results even for more complex forms of paraphrases at test
time, investigating more reliable ways of generating visual paraphrases could
lead to further gains. In addition, consistency can be imposed based on
relations other than equivalence but also inclusion and exclusion relations.
Generating automatic phrases that describe objects or regions with
superordinate referring expressions or referring expressions that exclude
content are possible paths for future work.


University of Technology Nuremberg, Germany and https://stoianmihail.github.io
mihail.stoian@utn.dehttps://orcid.org/0000-0002-8843-3374 Mihail Stoian
<ccs2012> <concept>
<concept_id>10003752.10003809.10011254.10011258</concept_id>
<concept_desc>Theory of computation Dynamic programming</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
</ccs2012> [500]Theory of computation Dynamic programming

###### Acknowledgements.

# Did Fourier Really Meet Möbius? Fast Subset Convolution via FFT

Mihail Stoian

###### Abstract

In their seminal work on subset convolution, Björklund, Husfeldt, Kaski and
Koivisto introduced the now well-known $O(2^{n}n^{2})$-time evaluation of the
subset convolution in the sum-product ring. This sparked a wave of remarkable
results for fundamental problems, such as the minimum Steiner tree and the
chromatic number. However, in spite of its theoretical improvement, large
intermediate outputs and floating-point precision errors due to alternating
addition and subtraction in its set function transforms make the algorithm
unusable in practice.

We provide a simple FFT-based algorithm that completely eliminates the need
for set function transforms and maintains the running time of the original
algorithm. This makes it possible to take advantage of nearly sixty years of
research on efficient FFT implementations.

###### keywords:

fast subset convolution, dynamic programming, simple algorithms

###### category:

##  1 Introduction

Subset convolution is one of the few examples of tools that need no
introduction – at least in exact or parameterized algorithms. As a sign for
its importance, it even made it into the prominent book on Parameterized
Algorithms [6]. Its popularity is also due to the suite of applications in
which is used, such as the minimum Steiner tree, the chromatic number, and
many more, even outside theoretical computer science (see Ref. [1] for further
applications).

Namely, given $f$ and $g$ two set functions defined on the subset lattice of
order $n$, their subset convolution on the sum-product ring is defined as

$(f\ast g)(S)=\displaystyle\sum_{T\subseteq S}f(T)g(S\setminus T),$ (1)

for any $S\subseteq[n]$. The naïve evaluation takes $O(3^{n})$-time as for
each cardinality we need to iterate all the subsets of that cardinality. In
their seminal work, Björklund et al. [1] showed that there is a faster way:
They introduced an $O(2^{n}n^{2})$-time algorithm, using the zeta and Möbius
transform, a faster algorithm for these being already due to Yates [17].

Motivation. As it stands now, the algorithm is far from being used smoothly in
practice. For instance, Kohonen and Corander [11] refrained from using it in
their application, and instead used the naïve evaluation. Their reason was
rounding errors in floating-point arithmetic, due to alternating additions and
subtractions in the Möbius transform. Another problem we encountered ourselves
was the magnitude of the values in the intermediate outputs, which are
themselves zeta transforms of the final convolution. In contrast, the well-
known $O(n\log n)$-time algorithm of the fast Fourier transform (FFT) [5] is
well-understood and has witnessed a rich line of research on practical
implementations, e.g., the FFTW library [8]; see Ref. [9] for a recent survey.

Contribution. We provide a simple algorithm for the subset convolution in the
$(+,\times)$-ring that does not rely on set function transforms. Notably, our
FFT-based algorithm maintains the running time of $O(2^{n}n^{2})$ of the
original algorithm proposed by Björklund et al. [1]. This makes it possible to
take advantage of nearly sixty years of research on efficient FFT
implementations.

##  2 Algorithm

Most importantly, our algorithm eliminates the need for set function
transforms. Instead, we interpret the set functions as vectors indexed by the
natural binary representation of subsets, and transform them via FFT. We
outline the pseudocode in Alg. 1.

Algorithm 1 $\textsc{SubsetConvolutionViaFFT}(f,g)$

1:$\\{\hat{f}^{(0)},\ldots,\hat{f}^{(n)}\\}\leftarrow\textsc{FFT}(\textsc{Chop}(f))$

2:$\\{\hat{g}^{(0)},\ldots,\hat{g}^{(n)}\\}\leftarrow\textsc{FFT}(\textsc{Chop}(g))$

3:$h^{(k)}\leftarrow\textsc{IFFT}(\sum_{i=0}^{k}\hat{f}^{(i)}\hat{g}^{(k-i)})$,
for any $0\leq k\leq n$.

4:$h^{(k)}[\\{S\subseteq[n]\mid|S|\neq k\\}]\leftarrow 0$, for any $0\leq
k\leq n$.

5:return $\sum_{k=0}^{n}h^{(k)}$

Let us analyze the algorithm. First, we “chop” the set functions into $n+1$
set functions and transform them via FFT.111In the pseudocode,
$\textsc{FFT}(\cdot)$ maps the “chopped” functions to their FFT counterpart. A
chopped function $f^{(i)}$ is a copy of the original function $f$ that takes
values only for sets $S\subseteq[n]$ with $|S|=i$; the rest is set to 0. This
is similar to ranked set functions in Björklund et al. [1]. Most importantly,
we do _not_ transform these via the zeta transform, but rather directly via
FFT. Next, we fix a cardinality $0\leq k\leq n$ and compute the convolution in
the frequency domain. This step resembles the ranked convolution in Ref. [1].
We can then apply the inverse FFT on this output. At this step, the previous
algorithm would have applied the Möbius transform.222The zeta and Möbius
transform are the inverse of each other. At this point, the “vanilla”
$h^{(k)}$’s in line 3 may have values for sets of cardinality other than $k$.
These need to be set to 0 (line 4) before we assemble the final output (line
5).

######  Theorem 2.1.

Algorithm 1 correctly computes the subset convolution in the
$(+,\times)$-ring.

######  Proof 2.2.

The fine work goes into line 3 of the algorithm. First, note that this step is
equivalent to computing
$\sum_{i=0}^{k}\textsc{IFFT}(\hat{f}^{(i)},\hat{g}^{(k-i)})$, due to the
linearity of the (inverse) Fourier transform. Since we remove the contribution
of sets with cardinality different $k$ in the next line, we only need to
analyze the correctness of the values of those set $S\subseteq[n]$ with
$|S|=k$. To this end, we use the following equivalence for two integers
$a,b\in[2^{n}]$:

$a+b=(a\>|\>b)+(a\>\&\>b),$

where “$|$” and “$\&$” are the well-known bit operations, which have the
natural interpretation in the set operations “$\cup$” and “$\cap$”,
respectively. Thus, multiplying $\hat{f}^{(i)}$ and $\hat{g}^{(k-i)}$ enforces
that the sets to be multiplied are _disjoint_ since their cardinalities sum up
to $k$. In other words, their “$\&$”-result is 0, i.e., the empty set. Summing
over all possible cardinalities $0\leq i\leq k$ ensures that all subsets are
considered, analogous to Björklund et al. [1].

Running Time. The chopped functions can be computed in $O(2^{n}n)$-time.
Applying FFT on these takes time $O(n\cdot 2^{n}\log 2^{n})=O(2^{n}n^{2})$.
For any $0\leq k\leq n$, the evaluation of $h^{(k)}$ can be done in time
$O(2^{n}n+2^{n}\log 2^{n})=O(2^{n}n)$, hence $O(2^{n}n^{2})$ for this step.
Finally, “cleaning up” the $h^{(k)}$’s and summing them runs in
$O(2^{n}n)$-time. The total running time thus reads $O(2^{n}n^{2})$,
maintaining the running time of the original algorithm [1]. On a practical
note, the input does not need any zero-padding as the size itself is always a
power of two.

##  3 Discussion

Implications. While our work shows that subset convolution does not require
any specialized set function transforms, this does not make them redundant:
They are relevant by themselves in order theory [2, 4, 10, 14], Bayesian
networks [13], and in reinterpreting dynamic programming recursions of well-
known problems to obtain polynomial-space algorithms [12]. Beyond simplicity,
our work enables the use of efficient FFT libraries. This is particularly
relevant for practical implementations of dynamic programs on tree
decompositions [16], which are widely used in algorithm engineering; see, for
instance, the PACE 2018 challenge [3].

Related Work. To ensure that our algorithm has not appeared as a by-product of
a previous work, we have examined the articles citing Björklund et al. [1]
that contain the terms “Fourier” and “FFT” in their text.333This is easily
done using Google Scholar’s feature of searching for a pattern within citing
articles. In particular, Cygan and Pilipczuk’s work on exact and approximate
bandwidth [7] comes the closest: They solve the Disjoint Set Sum problem using
both the standard fast subset convolution algorithm and a custom FFT solution
(see their Sec. 2.2). While they do not solve the fast subset convolution via
FFT, their algorithm for this particular problem bears similarity with ours.
Interestingly enough, at a closer inspection, we can even improve their
$O(2^{n}n^{3})$-time algorithm for the Disjoint Set Sum problem by a linear
factor, since they do not exploit the linearity of the (inverse) Fourier
transform and simply perform $n^{2}$ sequence convolutions.

On a final note, our work further “sinks” the recently uncovered algorithmic
isthmus between sequence convolution and subset convolution [15].

## References

  * [1] Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto.  Fourier meets möbius: Fast subset convolution.  In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 67–74, New York, NY, USA, 2007. Association for Computing Machinery.  doi:10.1145/1250790.1250801.
  * [2] Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka Parviainen.  Fast zeta transforms for lattices with few irreducibles.  ACM Transactions on Algorithms (TALG), 12(1):1–19, 2015.
  * [3] Edouard Bonnet and Florian Sikora.  The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration.  In IPEC 2018, Helsinki, Finland, August 2018.  URL: https://hal.science/hal-01991645, doi:10.4230/LIPIcs.IPEC.2018.26.
  * [4] Maxime Chaveroche, Franck Davoine, and Véronique Cherfaoui.  Focal points and their implications for möbius transforms and dempster-shafer theory.  Information Sciences, 555:215–235, 2021.
  * [5] James W Cooley and John W Tukey.  An algorithm for the machine calculation of complex fourier series.  Mathematics of computation, 19(90):297–301, 1965.
  * [6] Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Algebraic techniques: sieves, convolutions, and polynomials, pages 321–355.  Springer International Publishing, Cham, 2015.  doi:10.1007/978-3-319-21275-3_10.
  * [7] Marek Cygan and Marcin Pilipczuk.  Exact and approximate bandwidth.  Theoretical Computer Science, 411(40-42):3701–3713, 2010.
  * [8] Matteo Frigo.  A fast fourier transform compiler.  In Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, pages 169–180, 1999.
  * [9] Mario Garrido.  A survey on pipelined fft hardware architectures.  Journal of Signal Processing Systems, 94(11):1345–1364, 2022.
  * [10] Petteri Kaski, Jukka Kohonen, and Thomas Westerbäck.  Fast möbius inversion in semimodular lattices and u-labelable posets.  arXiv preprint arXiv:1603.03889, 2016.
  * [11] Jukka Kohonen and Jukka Corander.  Computing exact clustering posteriors with subset convolution.  Communications in Statistics-Theory and Methods, 45(10):3048–3058, 2016.
  * [12] Jesper Nederlof.  Fast polynomial-space algorithms using möbius inversion: Improving on steiner tree and related problems.  In International Colloquium on Automata, Languages, and Programming, pages 713–725. Springer, 2009.
  * [13] Pekka Parviainen and Mikko Koivisto.  Bayesian structure discovery in bayesian networks with less space.  In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 589–596. JMLR Workshop and Conference Proceedings, 2010.
  * [14] Tommaso Pegolotti, Bastian Seifert, and Markus Püschel.  Fast möbius and zeta transforms.  arXiv preprint arXiv:2211.13706, 2022.
  * [15] Mihail Stoian.  Sinking an algorithmic isthmus: (1+$\varepsilon$)-approximate min-sum subset convolution.  arXiv preprint arXiv:2404.11364, 2024.
  * [16] Johan MM Van Rooij, Hans L Bodlaender, and Peter Rossmanith.  Dynamic programming on tree decompositions using generalised fast subset convolution.  In Algorithms-ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings 17, pages 566–577. Springer, 2009.
  * [17] Frank Yates.  The design and analysis of factorial experiments.  1937\.