# Detect Every Thing with Few Examples

Xinyu Zhang, Yuting Wang & Abdeslam Boularias
Department of Computer Science
Rutgers University
<EMAIL_ADDRESS>
###### Abstract

Open-set object detection aims at detecting arbitrary categories beyond those
seen during training. Most recent advancements have adopted the open-
vocabulary paradigm, utilizing vision-language backbones to represent
categories with language. In this paper, we introduce DE-ViT , an open-set
object detector that employs vision-only DINOv2 backbones and learns new
categories through example images instead of language. To improve general
detection ability, we transform multi-classification tasks into binary
classification tasks while bypassing per-class inference, and propose a novel
region propagation technique for localization. We evaluate DE-ViT on open-
vocabulary, few-shot, and one-shot object detection benchmark with COCO and
LVIS. For COCO, DE-ViT outperforms the open-vocabulary SoTA by 6.9 AP50 and
achieves 50 AP50 in novel classes. DE-ViT surpasses the few-shot SoTA by 15
mAP on 10-shot and 7.2 mAP on 30-shot and one-shot SoTA by 2.8 AP50. For LVIS,
DE-ViT outperforms the open-vocabulary SoTA by 2.2 mask AP and reaches 34.3
mask APr. Code is available at https://github.com/mlzxy/devit.

##  1 Introduction

Object recognition and localization are two of the core tasks in computer
vision. In this work, we present a novel generic object detector that detects
objects of arbitrary categories, a paradigm commonly referred to as _open-set
object detection_ 111Some recent studies use _open-set_ as a synonym for
_open-vocabulary_ , whereas we view _open-set object detection_ as the general
objective, _i.e._ , the capability to detect objects of arbitrary classes.
Both _open-vocabulary_ and _few-shot_ belong to _open-set_ except their
category representations, _i.e._ , language versus images. . Following recent
advances in vision-language models (Radford et al., 2021), _open-vocabulary
object detection_ achieved a remarkable success by representing each class
with language embeddings of its category names (Zhong et al., 2022). However,
we argue that there exist fundamental limitations in using language for
category representation. First, certain objects are difficult to accurately
describe with only language, or lack concise denomination (Landau et al.,
2009; Pires et al., 2019). Second, the association between visual concepts and
language is constantly evolving and not static (Dorogovtsev & Mendes, 2001),
while an open-vocabulary model can only link objects and names that were
previously connected in the corpus. Third, language-based categorization does
not exploit image annotations when they are available.

_Few-shot object detection_ , albeit receiving far less recent research
attention, directly uses images instead of language to describe categories,
bypassing the above limitations. However, most recent few-shot methods focus
on finetuning-based strategies (Köhler et al., 2023), which requires further
training on the novel categories, a complicated and tedious procedure that
restricts the practical use of these methods (Zhao et al., 2022b). Moreover,
despite overcoming these limitations in principle, the accuracy of few-shot
methods falls behind that of the open-vocabulary solutions in practice,
especially in large-scale datasets such as COCO and LVIS (Ma et al., 2023; Wu
et al., 2023c).

In this paper, we introduce DE-ViT , an open-set object detector that uses
representative images to categorize objects. We adopt an RCNN framework
(Girshick, 2015) and use pretrained vision-only backbones, specifically DINOv2
ViT (Oquab et al., 2023), to extract image features and build prototype
vectors, _i.e._ , class representatives. We use off-the-shelf region proposal
networks (RPN) and design novel classification and refined localization
architectures for generic object detection, which exclusively relies on
similarity maps between image features and the constructed prototypes. New
classes can be added with a few example images in an ad-hoc manner without any
finetuning. The DINOv2 backbones are kept frozen and only our detection-
related layers are trained. The overall architecture is illustrated in Fig. 2.
A demonstration of detecting YCB objects is shown in Fig. 1.

Figure 1:  Demonstration of the proposed method on YCB objects (Calli et al.,
2015). DE-ViT with ViT-L/14 is used for prediction. Note that our model is
trained on only the base categories of LVIS. Example images of YCB objects are
provided only during inference to represent novel categories.

We evaluate DE-ViT on open-vocabulary, few-shot, and one-shot object detection
benchmarks with COCO (Lin et al., 2014) and LVIS (Gupta et al., 2019)
datasets. Our method establishes new state-of-the-art (SoTA) results on all
benchmarks. For COCO, DE-ViT outperforms the existing open-vocabulary SoTA
CORA+ (Wu et al., 2023c) by 6.9 AP50 and establishes a new SoTA at 50 AP50.
DE-ViT surpasses the few-shot SoTA LVC (Kaul et al., 2022) by 15 mAP on
10-shot and 7.2 mAP on 30-shot and one-shot SoTA BHRL (Yang et al., 2022) by
2.8 AP50. For LVIS, DE-ViT outperforms the open-vocabulary SoTA Ro-ViT (Kim et
al., 2023) by 2.2 mask AP, reaching 34.3 mask AP in novel categories. Our
method only trains on the corresponding dataset, i.e., COCO or LVIS, without
leveraging extra datasets for training, or distillation. Our contributions are
summarized as follows: (1) We show and verify the potential of employing
images as category representations for performing open-set object detection.
(2) We introduce DE-ViT , an example-driven open-set object detector based on
frozen vision-only DINOv2 backbones. (3) We demonstrate that DE-ViT
establishes state-of-the-art performance over open-vocabulary, few-shot, and
one-shot benchmarks on both COCO and LVIS.

Figure 2: Overview of the proposed method. Our approach uses DINOv2 ViT to
encode the image into a feature map, from which proposal features are
extracted using ROIAlign. Proposals are generated via an off-the-shelf RPN.
Prototype projection transforms proposal features into similarity maps based
on prototypes derived from ViT features of support images. Multi-class
classification of proposals is recast as a series of one-vs-rest binary
classification tasks without the need for costly per-class inference. Refined
localization is accomplished by our novel region propagation module. Both
classification and refined localization rely exclusively on the computed
similarity maps.

##  2 Related work

Few-shot Object Detection (FSOD) aims at detecting objects of novel classes by
utilizing a few support images from novel classes as training examples (Köhler
et al., 2023). Existing approaches can be broadly classified into finetuning-
based (Wang et al., 2020; Fan et al., 2021; Sun et al., 2021; Xiao et al.,
2022; Kaul et al., 2022; Ma et al., 2023; Guirguis et al., 2023) and meta-
learning-based strategies (Yan et al., 2019; Han et al., 2021; 2022b; 2022a).
Finetuning-based methods, despite their prevalence, suffer from a large
accuracy gap between the base and the novel classes, as well as practical
limitations due to redundant two-stage procedures (Zhao et al., 2022b). Meta-
learning methods avoid finetuning by online adaptation, but exhibit inferior
accuracy (Köhler et al., 2023). One-shot Object Detection (OSOD) is an extreme
case of FSOD with only one exemplar for each novel class. OSOD simplifies the
setting to single-class detection without finetuning. Prior approaches
primarily focus on designing interaction mechanisms of dense spatial features
between support and target images (Antonelli et al., 2022). However, the OSOD
formulation restricts the use of additional support, if available, and
requires a separate inference per class. Compared with existing work, our
method does not use finetuning or per-class inference, and only utilizes
class-level prototypes without dense feature interactions, while outperforming
SoTA methods in both few-shot and one-shot settings.

Open-Vocabulary Object Detection (OVD) aims at detecting objects of novel
classes based on their category names (Zareian et al., 2021). The prevalent
paradigm generally consists of two stages: image-text pretraining and
downstream detector training. OWL-ViT (Minderer et al., 2022) and Ro-ViT (Kim
et al., 2023) redesign the first stage for OVD tasks and do not rely on
publicly available models. Due to the high computational cost of the initial
stage, building such a framework can be challenging. RegionCLIP (Zhong et al.,
2022) and VL-PLM (Zhao et al., 2022a) propose image-text finetuning with
pseudo bounding boxes to enhance the alignment between image regions and text
features. CORA (Wu et al., 2023c) introduces region prompting techniques as an
alternative to full finetuning. Detic (Zhou et al., 2022b) and MEDet (Chen et
al., 2022) blur the boundaries between the two stages by simultaneously
training on both image-text pairs and bounding boxes. ViLD (Gu et al., 2021)
and BARON (Wu et al., 2023b) focus on the downstream detector training with
distillation. OV-DETR (Zang et al., 2022) proposes DETR-based detectors
(Carion et al., 2020) but suffers from inefficient per-class inference.
Compared with OVD methods, we represent each class with a prototype vector
derived from support images instead of a text embedding vector. Our method
surpasses state-of-the-art OVD methods on both LVIS and COCO. Remarkably, we
achieve these results by designing a novel architecture on top of frozen
pretrained DINOv2 backbones without employing any form of distillation or
alignment training.

##  3 Method

The major challenge in both FSOD and OVD is to generalize to classes that are
unseen during training. However, despite numerous attempts to address this
issue, through margin-based regularization (Ma et al., 2023) or extra
supervision from captions (Zhou et al., 2022b), for example, there still
persists a considerable accuracy gap between base and novel classes. This
disparity indicates that a network trained with base classes would inevitably
fixate on patterns that are only present among a few base classes, which does
not align with the objective of detecting arbitrary classes.

To address this challenge, we propose to learn not only backbone features, but
also maps of similarities between the features and a set of prototypes.
Specifically, let $\mathbf{f}\in\mathbb{R}^{H\times W\times D}$ be the
features of an image where $D$ represents the channel dimension and $(H,W)$
represent spatial dimensions, let $\mathbf{p}\in\mathbb{R}^{(C+B)\times D}$ be
the prototypes where $C$ is the number of classes and $B$ is the number of
class-agnostic background prototypes. Similarity map
$\mathbf{s}\in\mathbb{R}^{H\times W\times(C+B)}$ is calculated using Eq. 1.
This procedure is referred to in Fig. 3 as prototype projection. We use
$[C+B]$ to denote $\\{1,...,C+B\\}$.

$\mathbf{s}_{ijc}=\sum_{d=1}^{D}\mathbf{f}_{ijd}\,\,\mathbf{p}_{cd}\,,\,\text{where}\,\,(i,j,c)\in[H]\times[W]\times[C+B]$
(1)

We adopt a standard two-stage object detection framework, _e.g._ , Mask R-CNN
(He et al., 2017), which detects objects through RPN and RCNN stages. Existing
literature has demonstrated that class-agnostic RPN proposals generalize well
to novel classes (Gu et al., 2021). We use off-the-shelf RPNs to propose
object regions and extract proposal features from DINOv2 ViT backbones.
Similarity maps are computed between proposal features and prototypes, which
are then fed to our architectures for classification and refined localization.
Prototypes are constructed offline from support images with the procedures
detailed in Sec. 3.3. The ViT backbones, prototypes, and resulting the
similarity maps are kept frozen during detector training.

###  3.1 Classification with an Unknown Number of Classes

Unlike supervised learning, the number of classes in FSOD and OVD is
indeterminate. The common strategy in FSOD is to extend the final linear layer
with finetuning. The prevailing practice in OVD is to compose the last linear
layer with text embedding vectors of category names (Wu et al., 2023a). In
contrast with these existing approaches, we transform the multi-classification
of $C$ classes into $C$ one-vs-rest binary classification tasks. The overall
classification architecture is illustrated in Fig. 3.

Figure 3: Overview of our classification architecture. Class pre-selection
chooses the top-$K$ classes based on the dot product similarity between the
average feature of each proposal and class-level prototypes. The class score
of each selected class $c_{k}$ is predicted through a binary classification
network, shared by all the classes, in a one-vs-rest manner. The input to this
classification network is the similarity map that results from the prototype
projection, after rearranging it for each class.

Let
$\bar{\mathbf{f}}=\frac{\sum_{i,j=1}^{H,W}\mathbf{f}_{ij}}{HW}\in\mathbb{R}^{D}$
be the average feature of a proposal. The class pre-selection procedure
returns the top-$K$ mostly likely classes
$\mathcal{C}_{K}=\text{top\\_indices}_{K}(\mathbf{h})$.
$\mathbf{h}\in\mathbb{R}^{C}$ is the dot-product similarity between
$\bar{\mathbf{f}}$ and class prototypes, defined as
$\mathbf{h}_{c}=\sum_{d=1}^{D}\bar{\mathbf{f}}_{d}\,\,\mathbf{p}_{cd},\forall
c\in[C]$. The average feature $\bar{\mathbf{f}}$ is only used to select top
classes $\mathcal{C}_{K}$. For each class $c_{k}$ in $\mathcal{C}_{K}$, the
similarity map $\mathbf{s}\in\mathbb{R}^{H\times W\times(C+B)}$ (computed in
Eq. 1) is rearranged into a class-specific map
$\mathbf{s}_{c_{k}}\in\mathbb{R}^{H\times W\times(1+T+B)}$, which consists of
the similarities between the input image’s features and the prototype for
$c_{k}$, as well as the prototypes for the classes in $[C]/c_{k}$, and the
background, as shown in Eq. 2, where $[C]/c_{k}$ is defined as
$\\{1,..,c_{k}-1,c_{k}+1,...,C\\}$.

$\mathbf{s}_{c_{k}}=\text{concat}(\mathbf{s}[:,:,c_{k}],F_{\text{rearrange}}(\mathbf{s}_{[C]/c_{k}}),\mathbf{s}[:,:,C:C+B])$
(2)

where
$\mathbf{s}_{[C]/c_{k}}=\text{concat}(\mathbf{s}[:,:,:c_{k}-1],\mathbf{s}[:,:,c_{k}+1:])$,
and $F_{\text{rearrange}}(\mathbf{x})$ is defined in Eq. 3. $T$ is a constant
hyper-parameter.

$F_{\text{rearrange}}(\mathbf{x})=\begin{cases}\text{upsample}(\text{sort}(\mathbf{x}),T)&\text{if
}T\geq C-1\\\ \text{sort}(\mathbf{x})[:,:,:T]&\text{otherwise}\end{cases}$ (3)

$F_{\text{rearrange}}(\mathbf{x})$ first ranks $[C]/c_{k}$ by sorting
$\mathbf{s}_{[C]/c_{k}}$ along the channel dimension in similarity magnitude.
Next, either the similarities to the top $T$ classes are kept or the
similarities to all $C-1$ classes are linearly upsampled to $T$. In doing so,
$\mathbf{s}_{[C]/c_{k}}$ is transformed from a non-deterministic size of
$H\times W\times(C-1)$ into a fixed size $H\times W\times T$. Note that the
listed functions, _i.e._ , sort, concat and upsample, are applied along the
channel dimension, and sort works in descending order. Finally, the class-
specific similarity map $\mathbf{s}_{c_{k}}$ is given as input to a binary
classification network that returns the class score for $c_{k}$. Our method
only predicts class scores for $\mathcal{C}_{K}$ and sets the others to 0. As
shown in Sec. 4.2, our method surpasses SoTA even when $K=3$ on both COCO (80
classes) and LVIS (1203 classes), eliminating the need for costly per-class
inference.

###  3.2 Localization with Region Propagation.

Despite their rich semantics information, ViT features lack the coordinates
information required for bounding boxe regression. As shown in Sec. 4.2,
naively applying a conventional regression on ViT features yields poor
localization results. A natural solution is to learn this localization
capability by finetuning the ViT backbone during detector training. This
finetuning strategy has demonstrated success in OVD for vision-language
backbones, _e.g._ , CLIP (Zhong et al., 2022). However, we observed that
finetuning results in an accuracy collapse on novel classes when text
embeddings are replaced with prototypes, which indicates a loss of
generalization power. While this phenomenon is intriguing, the practical
question is how to produce accurate localization using frozen visual features.

Figure 4: Overview of our refined localization architecture. Proposal
expansion enlarges each proposal by a fixed ratio to cover more object area.
The spatial relationship between the original and expanded proposal is
described via a heatmap. The segmentation network navigates the initial
heatmap toward accurate object regions. The propagated heatmap is converted
into bounding box coordinates through our spatial integral layer.

Our intuition is that only proposals that overlap with objects are important
because others would be rejected by the classification network. If we expand
such proposals, they would possibly cover the entire region of underlying
objects. Therefore, original proposals can be refined by predicting object
regions within the expanded proposals. We model this procedure as propagating
original proposals to object areas in the form of heatmaps. The heatmaps can
be projected into box coordinates through integral over spatial dimensions.
The overall refined localization architecture is illustrated in Fig. 4.

As shown in Fig. 4, the propagation procedure is implemented through binary
segmentation. We convert groundtruth bounding boxes to heatmaps that we use to
train this segmentation network. Inspired by unsupervised keypoint estimation,
particularly the works of IMM (Jakab et al., 2018) and Transporter (Kulkarni
et al., 2019), we devise a spatial integral layer to project the propagated
heatmap to box. The idea is to learn a transformation that translates the
heatmap to a box
$(c^{\text{rel}}_{w},c^{\text{rel}}_{h},w^{\text{rel}},h^{\text{rel}})\in[0,1]^{4}$
in coordinates that are relative to the expanded proposal. Relative
coordinates can be simply mapped back to absolute coordinates. Let
$\mathbf{g}\in\mathbb{R}^{H\times W}$ denote the logits of the propagated
heatmap, the relative box
$(c^{\text{rel}}_{w},c^{\text{rel}}_{h},w^{\text{rel}},h^{\text{rel}})$ can be
estimated using Eq. LABEL:eq:spatial-int.

$\displaystyle\begin{split}&(c^{\text{rel}}_{w},c^{\text{rel}}_{h})=\sum_{i,j=1}^{H,W}\left(\frac{i}{H},\frac{j}{W}\right)*\text{softmax}(\mathbf{g})_{ij}\\\
&(w^{\text{rel}},h^{\text{rel}})=\left(\sum_{i=1}^{H}\sum_{j=1}^{W}\frac{\sigma(\mathbf{g})_{(i)j}}{W}\mathbf{\theta^{w}}_{i},\,\,\sum_{j=1}^{W}\sum_{i=1}^{H}\frac{\sigma(\mathbf{g})_{i(j)}}{H}\mathbf{\theta^{h}}_{j}\right)\\\
\end{split}$ (4)

Eq. LABEL:eq:spatial-int estimates the box center as the center of the spatial
distribution of the propagated heatmap. Note that the softmax is applied over
both spatial dimensions. The notation $\sigma$ represents elementwise sigmoid,
$\mathbf{\theta^{h}}\in\mathbb{R}^{W},\mathbf{\theta^{w}}\in\mathbb{R}^{H}$
are learnable parameters, $(i)$ and $(j)$ denote order statistics, _i.e._ ,
$\sigma(\mathbf{g})_{i(j)}$ stands for the $j$-th largest value at $i$-th row
of $\sigma(\mathbf{g})$. Take $w^{\text{rel}}$ as an example, the inner
summation $\sum_{j=1}^{W}\sigma(\mathbf{g})_{(i)j}$ produces a width estimate
at each row. Then, the final estimate is the ensemble of row-level estimates
weighted by order statistics. The rationale is that a larger estimate is
likely to be located at the object area and therefore matters more. Finally,
the relative coordinates are mapped to absolute ones by Eq. 5, where
$(c^{\text{exp}}_{w},c^{\text{exp}}_{h},w^{\text{exp}},h^{\text{exp}})$ is the
expanded proposal.

$\displaystyle\begin{split}&(w^{\text{out}},h^{\text{out}})=(w^{\text{exp}}\,w^{\text{rel}},h^{\text{exp}}\,h^{\text{rel}})\\\
&(c^{\text{out}}_{w},c^{\text{out}}_{h})=(c_{w}^{\text{exp}}-0.5w^{\text{exp}},c_{h}^{\text{exp}}-0.5h^{\text{exp}})+(c^{\text{rel}}_{w}\,w^{\text{exp}},c^{\text{rel}}_{h}\,h^{\text{exp}})\end{split}$
(5)

During training, we use groundtruth bounding boxes as regression targets for
the output of spatial integral layer. Similar to our classification pipeline,
the localization procedure is applied for each class in $\mathcal{C}_{K}$ to
produce class-specific boxes. For each class $c_{k}$, only the similarity map
of $c_{k}$ and the background will be selected as input. We omit this detail
in Fig. 4 for visual clarity.

###  3.3 Building Prototypes

While OVD uses text embeddings of category names to represent classes, our
method represents classes with prototype vectors constructed from visual
features of given support images. Fig. 5 shows the process of building
instance-level prototypes. For each object instance, its prototype is computed
as the mean ViT feature from corresponding regions defined by either a
segmentation mask or bounding box. Next, class-representing prototypes are
obtained by averaging the cluster centroids of instance-level prototypes for
each class. We use the online clustering method proposed by SwAV (Caron et
al., 2020), though we find that simply averaging all instance prototypes for
each class achieves similar results. Prototypes of base classes are built from
the entire training set instead of support images, which are used only for
novel classes.

Figure 5: Overview of building instance prototypes.

y

To build background prototypes, we start from the obervation that backgrounds
typically share similar visual attributes, such as uniform motion, smooth
texture, static color tone, _etc_. Moreover, the ability to capture and
thereby separate background from foreground is crucial. Because of the lack of
visual diversity yet the importance of background semantics, we use masks for
a fixed list of background classes, _e.g._ , sky, wall, road, and apply a
similar prototype-building procedure. The idea of using background information
for few-shot performance is similarly explored in IPRNet (Okazawa, 2022). In
contrast with class-level prototypes that change upon class configurations,
background prototypes are always fixed as a part of the network’s parameters.
All the prototypes are built offline and frozen during training and inference.

##  4 Experiments

We comprehensively evaluate our method on few-shot, one-shot, and open-
vocabulary object detection benchmarks. Furthermore, we compare the efficiency
of our method against SoTA solutions and conduct ablations to study different
components of the proposed technique.

Table 1: Results on COCO OVD benchmark. We report AP50 as the evaluation metric and list the extra dataset requirement. $\dagger$: Customized pretrained model is used instead of public models. Method | Backbone | Use Extra | Generalized (17 + 48)
---|---|---|---
Training Set | Novel | Base | All
OVR-CNN (Zareian et al., 2021) | RN50 | ✓ | 22.8 | 46.0 | 39.9
ViLD (Gu et al., 2021) | ViT-B/32 | ✗ | 27.6 | 59.9 | 51.3
RegionCLIP (Zhong et al., 2022) | RN50x4 | ✓ | 39.3 | 61.6 | 55.7
OV-DETR (Zang et al., 2022) | ViT-B/32 | ✗ | 29.4 | 61.0 | 52.7
VL-PLM (Zhao et al., 2022a) | RN50 | ✗ | 34.4 | 60.2 | 53.5
Detic (Zhou et al., 2022b) | RN50 | ✓ | 27.8 | 47.1 | 45.0
MEDet (Chen et al., 2022) | RN50 | ✓ | 32.6 | 54.0 | 49.4
BARON (Wu et al., 2023b) | RN50 | ✗ | 34 | 60.4 | 53.5
Ro-ViT (Kim et al., 2023) | ViT-L/16$\dagger$ | ✗ | 33 | - | 47.7
CORA (Wu et al., 2023c) | RN50x4 | ✗ | 41.7 | 44.5 | 43.8
CORA+ (Wu et al., 2023c) | RN50x4 | ✓ | 43.1 | 60.9 | 56.2
DE-ViT (Ours) | ViT-S/14 | ✗ | 39.5 | 42.3 | 41.5
ViT-B/14 | ✗ | 45.4 | 51.8 | 50.1
ViT-L/14 | ✗ | 50.0 | 54.0 | 52.9

Datasets and Evaluation. For open-vocabulary detection, we evaluate our method
on COCO-2017 (Lin et al., 2014) and LVIS-v1 (Gupta et al., 2019). Following
the convention (Zhong et al., 2022), the 80 classes of COCO are divided into
48 base classes and 17 novel classes. On LVIS, 866 common categories are used
for base classes and 337 rare categories are novel classes. We report AP50 for
COCO, and both mask and box AP for LVIS. Unlike most existing OVD work, our
method does not require extra data for multi-stage pretraining or
distillation. For few-shot learning, we evaluate on COCO-2014 and LVIS-v1. The
80 classes of COCO are divided into 60 base classes and 20 novel classes. LVIS
shares the same base/novel split between OVD and FSOD (Wang et al., 2020). We
report mAP, AP50, and AP75. For one-shot learning, we follow the convention
(Yang et al., 2022) to equally split the 80 classes of COCO-2017 into four
parts and alternately take three parts (60 classes) as base classes and one
part (20 classes) as novel classes, and we report AP50.

Model Specifications. We use DINOv2 (Oquab et al., 2023) ViT as the feature
extractor, and report results in ViT-S/B/L (small, base, large) model sizes.
We train a ResNet50 RPN separately for each dataset configuration using only
base classes and use 1000 proposals in all settings. We use lightweight CNNs
for both binary classification and segmentation networks, which we detail in
Sec. A.3. Class prototypes are built upon instance masks in support images
unless specified. We use the same support images as sampled by previous work
(Wang et al., 2020; Yang et al., 2022) for few-shot and one-shot settings. For
the open-vocabulary setting, we sample 30 instances per class (30-shot) using
the protocol of Wang et al. (2020). Background prototypes are extracted from
background classes, _e.g._ , sky, road, by the semantic masks in COCOStuff
(Caesar et al., 2018).

###  4.1 Main Results

Tab. 1 and 2 show our results on open-vocabulary COCO and LVIS. We list
whether extra datasets are required for training. DE-ViT outperforms the
previous SoTA CORA+ by 6.9 AP50. Our method only trains on COCO while CORA+
uses ImageNet-21K (Krizhevsky et al., 2012) and COCO Captions (Chen et al.,
2015) with generated pseudo detection labels as extra datasets. When only
using COCO, DE-ViT outperforms CORA by 8.3 AP50. In LVIS, DE-ViT outperforms
the previous SoTA on both mask APr (+2.2 over Ro-ViT) and box APr (+2.4 over
OWL-ViT). Our method only trains on LVIS and uses frozen public models while
OWL-ViT trains on an aggregation of detection datasets, and both Ro-ViT and
OWL-ViT train their own ViT backbones with customized vision-language
pertaining pipelines. We use “-” to indicate work that does not report mask or
box APs. We follow a conventional multi-scale instance segmentation head
design, as detailed in Sec. A.3.

Table 2: Results on LVIS OVD benchmark. We report both mask and box AP. *: Use a larger image size. $\dagger$: Customized pretrained model is used instead of public models. Method | Backbone | Use Extra | mask | box | mask | box
---|---|---|---|---|---|---
Training Set | APr | APr | AP | AP
ViLD (Gu et al., 2021) | EffNet-B7 | ✗ | 26.3 | 27 | 29.3 | 31.8
RegionCLIP (Zhong et al., 2022) | RN50x4 | ✓ | - | 22 | - | 32.3
OV-DETR (Zang et al., 2022) | ViT-B/32 | ✗ | - | 17.4 | - | 26.6
VL-PLM (Zhao et al., 2022a) | RN50 | ✗ | - | 17.2 | - | 27.0
Detic (Zhou et al., 2022b) | RN50 | ✓ | 17.8 | - | 26.8 | -
MEDet (Chen et al., 2022) | RN50 | ✓ | 22.4 | - | 34.4 | -
OWL-ViT (Minderer et al., 2022) | ViT-L/14$\dagger$ | ✗ | - | 25.6 | - | 34.7
OWL-ViT (Minderer et al., 2022) | ViT-L/14$\dagger$ | ✓ | - | 31.2 | - | 34.6
GroundingDINO (Liu et al., 2023) | Swin-L | ✓ | - | 22.2 | - | 33.9
CORA+ (Wu et al., 2023c) | RN50x4 | ✓ | - | 28.1 | - | -
PCL (Cho et al., 2023) | Swin-L | ✓ | - | 30.6 | - | 34.5
Ro-ViT (Kim et al., 2023) | ViT-L/14$\dagger$ | ✗ | 31.4 | - | 34.0 | -
Ro-ViT (Kim et al., 2023)* | ViT-L/16$\dagger$ | ✗ | 32.1 | - | 34.0 | -
DE-ViT (Ours) | ViT-S/14 | ✗ | 24.2 | 23.4 | 23.1 | 22.8
ViT-B/14 | ✗ | 28.5 | 26.8 | 27.6 | 26
ViT-L/14 | ✗ | 34.3 | 33.6 | 31.5 | 30.9
Table 3: Results on COCO few-shot benchmark.

Method | 10-shot | 30-shot
---|---|---
| bAP | nAP | nAP50 | nAP75 | bAP | nAP | nAP50 | nAP75
FSRW (Kang et al., 2019) | - | 5.6 | 12.3 | 4.6 | - | 9.1 | 19 | 7.6
Meta R-CNN (Yan et al., 2019) | 5.2 | 6.1 | 19.1 | 6.6 | 7.1 | 9.9 | 25.3 | 10.8
TFA (Wang et al., 2020) | 33.9 | 10 | 19.2 | 9.2 | 34.5 | 13.5 | 24.9 | 13.2
FSCE (Sun et al., 2021) | - | 11.9 | - | 10.5 | - | 16.4 | - | 16.2
Retentive RCNN (Fan et al., 2021) | 39.2 | 10.5 | 19.5 | 9.3 | 39.3 | 13.8 | 22.9 | 13.8
HeteroGraph (Han et al., 2021) | - | 11.6 | 23.9 | 9.8 | - | 16.5 | 31.9 | 15.5
FsDetView (Xiao et al., 2022) | 6.4 | 7.6 | - | - | 9.3 | 12 | - | -
Meta Faster R-CNN (Han et al., 2022a) | - | 12.7 | 25.7 | 10.8 | - | 16.6 | 31.8 | 15.8
LVC (Kaul et al., 2022) | 28.7 | 19 | 34.1 | 19 | 34.8 | 26.8 | 45.8 | 27.5
Cross-Transformer (Han et al., 2022b) | - | 17.1 | 30.2 | 17 | - | 21.4 | 35.5 | 22.1
NIFF (Guirguis et al., 2023) | 39 | 18.8 | - | - | 39 | 20.9 | - | -
DiGeo (Ma et al., 2023) | 39.2 | 10.3 | 18.7 | 9.9 | 39.4 | 14.2 | 26.2 | 14.8
DE-ViT (Ours) | ViT-S/14 | 24 | 27.1 | 43.1 | 28.5 | 24.2 | 26.9 | 43.1 | 28.4
ViT-B/14 | 28.3 | 33.2 | 51.4 | 35.5 | 28.5 | 33.4 | 51.4 | 35.7
ViT-L/14 | 29.4 | 34.0 | 53.0 | 37.0 | 29.5 | 34.0 | 52.9 | 37.2

Tab. 4.1 shows our results on few-shot COCO. DE-ViT outperforms the previous
SoTA LVC by a significant margin (+15 nAP on 10-shot, +7.2 nAP on 30-shot).
nAP represents mAP in novel classes. LVC applies finetuning and pseudo-
labeling on novel classes, while our method does not require finetuning. Our
method shows no accuracy difference between 10-shot and 30-shot. Tab. 8 shows
that similar accuracy can be obtained at even 5-shot. It is possible that the
representation power of DINOv2, despite being strong, already saturates upon a
few images when using a single prototype per class. LVIS has been regarded as
a highly challenging dataset in FSOD (Wang et al., 2020) and only DiGeo
reports few-shot results on LVIS v1, the comparison is reported in Appendix
Tab. A.4 to save space.

Table 4: Results on COCO one-shot benchmark. | Seen | Unseen
---|---|---
| Split-1 | Split-2 | Split-3 | Split-4 | Avg | Split-1 | Split-2 | Split-3 | Split-4 | Avg
SiamMask (Michaelis et al., 2018) | 38.9 | 37.1 | 37.8 | 36.6 | 37.6 | 15.3 | 17.6 | 17.4 | 17 | 16.8
CoAE (Hsieh et al., 2019) | 42.2 | 40.2 | 39.9 | 41.3 | 40.9 | 23.4 | 23.6 | 20.5 | 20.4 | 22
AIT (Chen et al., 2021) | 50.1 | 47.2 | 45.8 | 46.9 | 47.5 | 26 | 26.4 | 22.3 | 22.6 | 24.3
SaFT (Zhao et al., 2022b) | 49.2 | 47.2 | 47.9 | 49 | 48.3 | 27.8 | 27.6 | 21 | 23 | 24.9
BHRL (Yang et al., 2022) | 56 | 52.1 | 52.6 | 53.4 | 53.6 | 26.1 | 29 | 22.7 | 24.5 | 25.6
DE-ViT (Ours, ViT-L/14) | 59.4 | 57.0 | 61.3 | 60.7 | 59.6 | 27.4 | 33.2 | 27.1 | 26.1 | 28.4

Tab. 4 shows our results on one-shot COCO. DE-ViT outperforms the previous
SoTA BHRL by 2.8 and 6 AP50 on unseen and seen classes. Note that one-shot
detection follows a single-class object detection formulation. We adapt our
method to this setting by detecting each class separately. Notice that the gap
between seen and unseen classes is much larger in one-shot than few-shot
setting. This shows that a single image may be insufficient to describe
categories with high intra-variance. OWL-ViT also reports one-shot results on
COCO. However, OWL-ViT’s results are obtained with an ensemble of open-
vocabulary and one-shot pipelines without providing implementation or isolated
measurements. Therefore, we only compare against OWL-ViT in open-vocabulary
benchmarks.

###  4.2 Analysis

Table 5: Efficiency comparison against existing state-of-the-art on COCO OVD benchmark. Method | Backbone | top $K$ | Novel AP50 | Secs/Img
---|---|---|---|---
DE-ViT | ViT-L/14 | 1 | 47.7 | 0.22
3 | 50.0 | 0.33
(Ours) | 10 | 50.0 | 0.83
CORA | RN50x4 | - | 41.7 | 0.5

Table 6: Efficiency comparison against existing state-of-the-art on LVIS OVD benchmark. Method | Backbone | top $K$ | box APr | Secs/Img
---|---|---|---|---
DE-ViT | ViT-L/14 | 1 | 25.4 | 0.35
3 | 32.6 | 0.5
(Ours) | (pytorch) | 10 | 33.6 | 1.58
OWL-ViT | ViT-L/14 (jax) | - | 31.2 | 0.42

Efficiency. In Tab. 6 and 6, we compare the efficiency of DE-ViT against
previous SoTA open-vocabulary methods. We study the effects of selecting
different numbers of classes ($K$) during class preselection. The inference
speed is measured under PyTorch 1.13 with one A100 GPU, except for OWL-ViT
which is implemented in JAX framework (Frostig et al., 2018). DE-ViT
outperforms SoTA while being much faster at COCO and slightly slower at LVIS
when $K=3$. Note that JAX is commonly known as faster than pytorch (Phan et
al., 2019). Our main results are obtained using $K=10$. We select CORA instead
of CORA+ and OWL-ViT rather than Ro-ViT for comparison because the latter
implementations have not been released at the moment this paper is written.
Note that we use half-precision for ViT inference as the standard practice for
vision transformers, and full precision for other layers. We choose open-
vocabulary over few-shot methods for comparison because of their superior
accuracy.

Feature Visualization of DINOv2 and CLIP. The critical distinction between DE-
ViT and OVD methods is that DE-ViT uses visual features and represents each
class by the center of visual features, while OVD methods represent each class
with text features, mostly from CLIP. Therefore, we sample and visualize
DINOv2 and CLIP features in Fig. A2 using UMap (McInnes et al., 2018). CLIP
visual features also show excellent intra-class compactness. However, there is
a huge vacuum between CLIP text and visual features, and text features are
almost overlapped with each other. This indicates that the distances between
text and visual features may be more susceptible to noises. This further
suggests that using images to represent classes could be more promising than
only using texts.

Table 7: Ablation studies on the classification architecture.

Conventional | Prototype | Background | Class | Novel | Base
---|---|---|---|---|---
CLS Head | Projection | Tokens | Rearrange | AP50 | AP75 | AP50 | AP75
✓ |  |  |  | 4.5 | 2.2 | 48.9 | 22.5
| ✓ |  |  | 26.2 | 9.7 | 29.3 | 12
| ✓ | ✓ |  | 38.4 | 23 | 43.4 | 26.8
| ✓ | ✓ | ✓ | 39.5 | 24.1 | 42.3 | 25.9

Table 8: Ablation studies on annotation types used to build prototypes. Support Images | nAP50
---|---
Annotation | 5-shot | 10-shot | 30-shot
mask | 43.1 | 43.1 | 43.1
bbox | 43 | 42.6 | 43.1

###  4.3 Ablation Study

Classification. We examine the component effects for classification in Tab. 8.
For the conventional CLS head, we follow an architecture similar to RegionCLIP
that inputs features to the RCNN head and composes the last linear layer with
class prototypes. Tab. 8 shows that the model completely overfits base classes
without our proposed components. By learning from similarity maps from
prototype projection, general detection ability emerges, and then improves
after adding the background prototypes and the class rearrange module. Results
in Tab. 8, 4.3 and 8 are obtained with ViT-S/14.

Table 9: Ablation studies on the refined localization pipeline. Conventional
Expanded Spatial Integral Novel Base REG Head Proposal over Heatmap AP50 AP75
AP50 AP75 ✓ 37.7 14.6 46.5 23.9 ✓ ✓ 35.6 12.5 41.3 19.8 ✓ ✓ 39.5 24.1 42.3
25.9

y

Refined Localization. We study the impacts of region propagation in Tab. 4.3.
For the conventional REG head, we use a CNN with both features and similarity
maps as input. Novel classes have poor localization (14.6 AP75) without our
proposed architecture, and simply expanding proposals even lowers the
performance. The localization accuracy jumps to 24.1 AP75 when the heatmap
representation is used with spatial integrals to produce bounding boxes.

Using Boxes or Masks to Build Prototypes. In Tab. 8, we study the effects of
annotation types, _i.e._ , bounding boxes or masks, in constructing
prototypes. We observe that using bounding boxes to build prototypes yields
almost indistinguishable performance compared to using instance masks at even
5-shot. Our main results use prototypes built from instance masks.

##  5 Conclusion

Our method has shown positive results in using images as the category
representation in an open-set object detector. Since our method detects
objects using only frozen visual features, it is straightforward to integrate
DE-ViT with more backbones or co-exist with networks for other downstream
tasks. Some limitations are still to be investigated. (1) Using only one
prototype per class is a bottleneck representation and prohibits complex
spatial reasoning. (2) We apply a hybrid ViT and RCNN structure while a full
transformer network could be conceptually more scalable and performant. (3)
The ViT backbone is frozen to retain generalization power that would be lost
otherwise. This issue remains unresolved. (4) Our implementation depends on a
ResNet RPN, which introduces extra computation costs and may limit detection
recall. This issue could be solved with some engineering efforts, e.g.,
training RPN on top of ViT, or re-purposing our localization module for RPN.
We hope that our work will be useful in downstream tasks such as robotic
manipulation, and help other researchers develop better methods for open-
vocabulary and few-shot object detection.

## References

  * Antonelli et al. (2022) Simone Antonelli, Danilo Avola, Luigi Cinque, Donato Crisostomi, Gian Luca Foresti, Fabio Galasso, Marco Raoul Marini, Alessio Mecca, and Daniele Pannone.  Few-shot object detection: A survey.  _ACM Computing Surveys (CSUR)_ , 54(11s):1–37, 2022.
  * Caesar et al. (2018) Holger Caesar, Jasper Uijlings, and Vittorio Ferrari.  Coco-stuff: Thing and stuff classes in context.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 1209–1218, 2018.
  * Calli et al. (2015) Berk Calli, Arjun Singh, Aaron Walsman, Siddhartha Srinivasa, Pieter Abbeel, and Aaron M Dollar.  The ycb object and model set: Towards common benchmarks for manipulation research.  In _International Conference on Advanced Robotics (ICAR)_ , pp. 510–517. IEEE, 2015.
  * Carion et al. (2020) Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In _European Conference on Computer Vision_ , pp. 213–229. Springer, 2020.
  * Caron et al. (2020) Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  _Advances in Neural Information Processing Systems_ , 33:9912–9924, 2020.
  * Chen et al. (2021) Ding-Jie Chen, He-Yen Hsieh, and Tyng-Luh Liu.  Adaptive image transformer for one-shot object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 12247–12256, 2021.
  * Chen et al. (2022) Peixian Chen, Kekai Sheng, Mengdan Zhang, Yunhang Shen, Ke Li, and Chunhua Shen.  Open vocabulary object detection with proposal mining and prediction equalization.  _arXiv preprint arXiv:2206.11134_ , 2022.
  * Chen et al. (2015) Xinlei Chen, Hao Fang, Tsung-Yi Lin, Ramakrishna Vedantam, Saurabh Gupta, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco captions: Data collection and evaluation server.  _arXiv preprint arXiv:1504.00325_ , 2015.
  * Cho et al. (2023) Han-Cheol Cho, Won Young Jhoo, Wooyoung Kang, and Byungseok Roh.  Open-vocabulary object detection using pseudo caption labels.  _arXiv preprint arXiv:2303.13040_ , 2023.
  * Cuturi (2013) Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Dorogovtsev & Mendes (2001) Sergey N Dorogovtsev and José Fernando F Mendes.  Language as an evolving word web.  _Proceedings of the Royal Society of London. Series B: Biological Sciences_ , 268(1485):2603–2606, 2001.
  * Fan et al. (2021) Zhibo Fan, Yuchen Ma, Zeming Li, and Jian Sun.  Generalized few-shot object detection without forgetting.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 4527–4536, 2021.
  * Frostig et al. (2018) Roy Frostig, Matthew James Johnson, and Chris Leary.  Compiling machine learning programs via high-level tracing.  _Systems for Machine Learning_ , 4(9), 2018.
  * Girshick (2015) Ross Girshick.  Fast r-cnn.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 1440–1448, 2015.
  * Gu et al. (2021) Xiuye Gu, Tsung-Yi Lin, Weicheng Kuo, and Yin Cui.  Open-vocabulary object detection via vision and language knowledge distillation.  In _International Conference on Learning Representations_ , 2021.
  * Guirguis et al. (2023) Karim Guirguis, Johannes Meier, George Eskandar, Matthias Kayser, Bin Yang, and Jürgen Beyerer.  Niff: Alleviating forgetting in generalized few-shot object detection via neural instance feature forging.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 24193–24202, 2023.
  * Gupta et al. (2019) Agrim Gupta, Piotr Dollar, and Ross Girshick.  Lvis: A dataset for large vocabulary instance segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 5356–5364, 2019.
  * Han et al. (2021) Guangxing Han, Yicheng He, Shiyuan Huang, Jiawei Ma, and Shih-Fu Chang.  Query adaptive few-shot object detection with heterogeneous graph convolutional networks.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 3263–3272, 2021.
  * Han et al. (2022a) Guangxing Han, Shiyuan Huang, Jiawei Ma, Yicheng He, and Shih-Fu Chang.  Meta faster r-cnn: Towards accurate few-shot object detection with attentive feature alignment.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pp. 780–789, 2022a.
  * Han et al. (2022b) Guangxing Han, Jiawei Ma, Shiyuan Huang, Long Chen, and Shih-Fu Chang.  Few-shot object detection with fully cross-transformer.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 5321–5330, 2022b.
  * He et al. (2017) Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 2961–2969, 2017.
  * Hsieh et al. (2019) Ting-I Hsieh, Yi-Chen Lo, Hwann-Tzong Chen, and Tyng-Luh Liu.  One-shot object detection with co-attention and co-excitation.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Hu et al. (2018) Jie Hu, Li Shen, and Gang Sun.  Squeeze-and-excitation networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 7132–7141, 2018.
  * Jakab et al. (2018) Tomas Jakab, Ankush Gupta, Hakan Bilen, and Andrea Vedaldi.  Unsupervised learning of object landmarks through conditional image generation.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Kang et al. (2019) Bingyi Kang, Zhuang Liu, Xin Wang, Fisher Yu, Jiashi Feng, and Trevor Darrell.  Few-shot object detection via feature reweighting.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 8420–8429, 2019.
  * Kaul et al. (2022) Prannay Kaul, Weidi Xie, and Andrew Zisserman.  Label, verify, correct: A simple few shot object detection method.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 14237–14247, 2022.
  * Kim et al. (2023) Dahun Kim, Anelia Angelova, and Weicheng Kuo.  Region-aware pretraining for open-vocabulary object detection with vision transformers.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 11144–11154, 2023.
  * Köhler et al. (2023) Mona Köhler, Markus Eisenbach, and Horst-Michael Gross.  Few-shot object detection: a comprehensive survey.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2023\.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  _Advances in Neural Information Processing Systems_ , 25, 2012.
  * Kulkarni et al. (2019) Tejas D Kulkarni, Ankush Gupta, Catalin Ionescu, Sebastian Borgeaud, Malcolm Reynolds, Andrew Zisserman, and Volodymyr Mnih.  Unsupervised learning of object keypoints for perception and control.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Landau et al. (2009) Barbara Landau, Lila R Gleitman, and Barbara Landau.  _Language and experience: Evidence from the blind child_ , volume 8.  Harvard University Press, 2009.
  * 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 _European Conference on Computer Vision_ , pp. 740–755. Springer, 2014.
  * Liu et al. (2022) Qin Liu, Zhenlin Xu, Gedas Bertasius, and Marc Niethammer.  Simpleclick: Interactive image segmentation with simple vision transformers.  _arXiv preprint arXiv:2210.11006_ , 2022.
  * Liu et al. (2023) Shilong Liu, Zhaoyang Zeng, Tianhe Ren, Feng Li, Hao Zhang, Jie Yang, Chunyuan Li, Jianwei Yang, Hang Su, Jun Zhu, et al.  Grounding dino: Marrying dino with grounded pre-training for open-set object detection.  _arXiv preprint arXiv:2303.05499_ , 2023.
  * Ma et al. (2023) Jiawei Ma, Yulei Niu, Jincheng Xu, Shiyuan Huang, Guangxing Han, and Shih-Fu Chang.  Digeo: Discriminative geometry-aware learning for generalized few-shot object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 3208–3218, 2023.
  * McInnes et al. (2018) Leland McInnes, John Healy, and James Melville.  Umap: Uniform manifold approximation and projection for dimension reduction.  _arXiv preprint arXiv:1802.03426_ , 2018.
  * Michaelis et al. (2018) Claudio Michaelis, Ivan Ustyuzhaninov, Matthias Bethge, and Alexander S Ecker.  One-shot instance segmentation.  _arXiv preprint arXiv:1811.11507_ , 2018.
  * Minderer et al. (2022) Matthias Minderer, Alexey Gritsenko, Austin Stone, Maxim Neumann, Dirk Weissenborn, Alexey Dosovitskiy, Aravindh Mahendran, Anurag Arnab, Mostafa Dehghani, Zhuoran Shen, et al.  Simple open-vocabulary object detection.  In _European Conference on Computer Vision_ , pp. 728–755. Springer, 2022.
  * Okazawa (2022) Atsuro Okazawa.  Interclass prototype relation for few-shot segmentation.  In _European Conference on Computer Vision_ , pp. 362–378. Springer, 2022.
  * Oquab et al. (2023) Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo, Marc Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, et al.  Dinov2: Learning robust visual features without supervision.  _arXiv preprint arXiv:2304.07193_ , 2023.
  * Phan et al. (2019) Du Phan, Neeraj Pradhan, and Martin Jankowiak.  Composable effects for flexible and accelerated probabilistic programming in numpyro.  _arXiv preprint arXiv:1912.11554_ , 2019.
  * Pires et al. (2019) Telmo Pires, Eva Schlinger, and Dan Garrette.  How multilingual is multilingual bert?  _arXiv preprint arXiv:1906.01502_ , 2019.
  * 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, et al.  Learning transferable visual models from natural language supervision.  In _International Conference on Machine Learning_ , pp. 8748–8763. PMLR, 2021.
  * Sudre et al. (2017) Carole H Sudre, Wenqi Li, Tom Vercauteren, Sebastien Ourselin, and M Jorge Cardoso.  Generalised dice overlap as a deep learning loss function for highly unbalanced segmentations.  In _Deep Learning in Medical Image Analysis and Multimodal Learning for Clinical Decision Support: Third International Workshop_ , pp. 240–248. Springer, 2017.
  * Sun et al. (2021) Bo Sun, Banghuai Li, Shengcai Cai, Ye Yuan, and Chi Zhang.  Fsce: Few-shot object detection via contrastive proposal encoding.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 7352–7362, 2021.
  * Villani et al. (2009) Cédric Villani et al.  _Optimal transport: old and new_ , volume 338.  Springer, 2009.
  * Wang et al. (2022) Wenguan Wang, Cheng Han, Tianfei Zhou, and Dongfang Liu.  Visual recognition with deep nearest centroids.  _arXiv preprint arXiv:2209.07383_ , 2022.
  * Wang et al. (2020) Xin Wang, Thomas E Huang, Trevor Darrell, Joseph E Gonzalez, and Fisher Yu.  Frustratingly simple few-shot object detection.  _arXiv preprint arXiv:2003.06957_ , 2020.
  * Wu et al. (2023a) Jianzong Wu, Xiangtai Li, Shilin Xu Haobo Yuan, Henghui Ding, Yibo Yang, Xia Li, Jiangning Zhang, Yunhai Tong, Xudong Jiang, Bernard Ghanem, et al.  Towards open vocabulary learning: A survey.  _arXiv preprint arXiv:2306.15880_ , 2023a.
  * Wu et al. (2023b) Size Wu, Wenwei Zhang, Sheng Jin, Wentao Liu, and Chen Change Loy.  Aligning bag of regions for open-vocabulary object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 15254–15264, 2023b.
  * Wu et al. (2023c) Xiaoshi Wu, Feng Zhu, Rui Zhao, and Hongsheng Li.  Cora: Adapting clip for open-vocabulary detection with region prompting and anchor pre-matching.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 7031–7040, 2023c.
  * Xiao et al. (2022) Yang Xiao, Vincent Lepetit, and Renaud Marlet.  Few-shot object detection and viewpoint estimation for objects in the wild.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(3):3090–3106, 2022.
  * Yan et al. (2019) Xiaopeng Yan, Ziliang Chen, Anni Xu, Xiaoxi Wang, Xiaodan Liang, and Liang Lin.  Meta r-cnn: Towards general solver for instance-level low-shot learning.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 9577–9586, 2019.
  * Yang et al. (2022) Hanqing Yang, Sijia Cai, Hualian Sheng, Bing Deng, Jianqiang Huang, Xian-Sheng Hua, Yong Tang, and Yu Zhang.  Balanced and hierarchical relation learning for one-shot object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 7591–7600, 2022.
  * Zang et al. (2022) Yuhang Zang, Wei Li, Kaiyang Zhou, Chen Huang, and Chen Change Loy.  Open-vocabulary detr with conditional matching.  In _European Conference on Computer Vision_ , pp. 106–122. Springer, 2022.
  * 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_ , pp. 14393–14402, 2021.
  * Zhao et al. (2022a) Shiyu Zhao, Zhixing Zhang, Samuel Schulter, Long Zhao, BG Vijay Kumar, Anastasis Stathopoulos, Manmohan Chandraker, and Dimitris N Metaxas.  Exploiting unlabeled data with vision and language models for object detection.  In _European Conference on Computer Vision_ , pp. 159–175. Springer, 2022a.
  * Zhao et al. (2022b) Yizhou Zhao, Xun Guo, and Yan Lu.  Semantic-aligned fusion transformer for one-shot object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 7601–7611, 2022b.
  * Zhong et al. (2022) Yiwu Zhong, Jianwei Yang, Pengchuan Zhang, Chunyuan Li, Noel Codella, Liunian Harold Li, Luowei Zhou, Xiyang Dai, Lu Yuan, Yin Li, et al.  Regionclip: Region-based language-image pretraining.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 16793–16803, 2022.
  * Zhou et al. (2022a) Tianfei Zhou, Wenguan Wang, Ender Konukoglu, and Luc Van Gool.  Rethinking semantic segmentation: A prototype view.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 2582–2593, 2022a.
  * Zhou et al. (2022b) Xingyi Zhou, Rohit Girdhar, Armand Joulin, Philipp Krähenbühl, and Ishan Misra.  Detecting twenty-thousand classes using image-level supervision.  In _European Conference on Computer Vision_ , pp. 350–368. Springer, 2022b.

##  Appendix A Appendix

###  A.1 Visualization Details

Demonstration on YCB Objects. Fig. 1 shows the detection results of DE-ViT on
YCB objects, a standard set of objects widely used in robotic manipulation
benchmark (Calli et al., 2015). There are misclassifications and inaccurate
boxes, _e.g._ , the white skillet is mistaken as a can, all round-shape fruits
are recognized as orange, while the red one is clearly an apple. However, we
believe the overall result is encouraging. The specification of YCB objects at
the time this paper is written includes 72 categories. We use a total of 33 by
selecting and merging certain categories. The categories in use are apple,
ball, banana, bowl, brick, can, cheez-it, chips, clamp, cleanser bottle,
coffee jar, comet pine, cups, drill, glass, lego, lemon, marker, mug, mustard,
orange, peach, pear, peg-hole, pitcher, plate, screwdriver, skillet, spray
bottle, sugar box, toy airplane box, utensil, wood blocks jar. The source
image in Fig. 1 is taken from the banner picture of ycbbenchmarks.com. For
each category, we use google image search to collect a few sample images.
Fewer than four images on average are gathered per category. We annotate the
corresponding objects by instance masks in each image using the software
provided by SimpleClick (Liu et al., 2022). Similar to SAM, SimpleClick
generates instance masks automatically from user clicks, which significantly
simplifies and accelerates the annotation procedure. Our annotator feedback
indicates that annotating masks with SimpleClick is even easier and more
accurate than drawing bounding boxes. An NVIDIA 3060 GPU is used for
SimpleClick software. Class prototypes for YCB objects are built from the
annotated example images. During DE-ViT inference, we replace prototypes of
LVIS categories with those of YCB objects in order to detect these new
categories. During postprocessing, We apply class-agnostic NMS and filter
small bounding boxes. The full code and data for this demonstration will be
released in our repository.

(a) Proposal

(b) Initial Heatmap

(c) Propagated Heatmaps

(d) Final Prediction

(e) Proposal

(f) Initial Heatmap

(g) Propagated Heatmaps

(h) Final Prediction

Figure A1: Examples of heatmaps in region propagation. The proposal, expanded
proposal, and final prediction box are colored in red, pink, and yellow,
respectively. The initial heatmap encodes the spatial relationship between
proposals and expanded proposals in binary masks. Propagated heatmaps are
softmax predictions sampled from the binary segmentation network in our region
propagation architecture.

Figure A2: Visualization of DINOv2 and CLIP (RN50x4) features in 2d plane.
From visual features (✖), both DINOv2 and CLIP show good concentration within
each class. However, CLIP text features (◆) locate much further from visual
features. In contrast to centers of visual features (⚫), text features of
different classes overlap each other, showing much smaller inter-class
distances.

Feature Visualization of DINOv2 and CLIP. Fig. A2 visualizes the features of
DINOv2 and CLIP, as we discussed in Sec. 4.2. Visual features of DINOv2 are
extracted using groundtruth bounding boxes with the procedure shown in Fig. 5.
For CLIP, we follow the standard text and region visual features extraction
procedure (Zhong et al., 2022; Wu et al., 2023c). Specifically, visual
features are obtained by applying ROIAlign on the output of res4 block. The
ROIAlign outputs are fed into res5 and attention pooling blocks to produce the
final feature vector. Text features are extracted with CLIP text encoders with
category names. We randomly sample 30 instances per class for visualization,
_i.e._ , each node (✖) represents an instance of the corresponding class. The
UMap dimension reduction transformation is learned with a larger set of
instances with both visual and text features.

Region Propagation. Fig. A1 visualizes the heatmap changes of sampled
detection results during region propagation. A clear mapping can be found
between the detection bounding boxes and the corresponding salient regions
within the expanded proposal. The softmax predictions are normalized by
dividing mean values in order to enhance the visual quality.

###  A.2 Discussion

We highlight that the parameters introduced by our classification and
localization network only occupy a small fraction compared to the ViT
backbone, _e.g._ , 7.7M versus 304M for COCO ViT-L/14. Moreover, the similar
visual feature distribution of DINOv2 and CLIP shown in Fig. A2 also suggests
that our method may apply to other backbones besides DINOv2 ViTs. Considering
that our method detects objects from frozen visual features, it could be seen
as a pipeline that extracts object information from visual features, similar
to the linear probe protocol for semantic segmentation (Oquab et al., 2023).

Despite having strong results, one limitation of DE-ViT is the bottlenecked
representation of one prototype per class. In contrast to some recent few-shot
methods like CrossTransformer (Han et al., 2022b) that applies dense feature
interaction between support and input images, our method represents each class
by a single prototype vector, which enables a simplified framework and better
efficiency. However, there are cases when more expensive spatial reasoning
becomes necessary, such as when certain categories share a similar appearance
or have specific shapes. This further leads to the architectural limitation of
DE-ViT . Our method uses a hybrid structure with ViT backbone and RCNN head,
while a full transformer network shall be conceptually more performant and
scalable. Moreover, as mentioned in Sec. 3.2 and shown in Tab. 8, the ViT
backbone is kept frozen to retain the generalization power which would be lost
otherwise during finetuning. This could be viewed as our unresolved issue for
using images as category representation.

Another limitation is that our current implementation relies on a ResNet50 RPN
network, which introduces extra computational overhead and may even limit the
detection recall. This issue should be able to resolve with some engineering
efforts, such as training an RPN head on top of the ViT backbone or
repurposing our localization architectures for RPN by doing refined
localizations over a set of pre-defined boxes. The anchor pre-matching
technique in the framework of CORA is similar to the latter strategy.

###  A.3 Implementation Details

####  A.3.1 Network Architecture

Figure A3: Basic building block for our RCNN networks.

y

Fig. A3 illustrates the network building block used in our convolution neural
networks for classification, localization, and instance segmentation branches.
Sigmoid cross entropy loss and dice loss (Sudre et al., 2017) are applied on
the mask output at each layer in the localization and segmentation branch. The
red blocks are only used in the classification branch. For the classification
branch, the mask prediction serves as spatial attention and receives no
supervision, similar to the squeeze-and-excitation block in SENet (Hu et al.,
2018) but at spatial dimensions. The input to both classification and
localization branches is the similarity map between proposal features and
prototypes, while the input to the instance segmentation branch for LVIS is
the concatenation of similarity maps and multi-scale ViT features. For models
trained with COCO, we use 3 blocks for classification and 5 blocks for
localization. For LVIS, we use 5 blocks for all branches. The 3$\times$3 conv,
256 denotes a convolution layer with kernel size 3 and 256 output channels. We
use $T=128$ in the class rearrange module for both COCO and LVIS.

####  A.3.2 Operations

Proposal Expansion. Eq. 6 explains the proposal expansion block in Fig. 4.
$(c_{w},c_{h},w,h)$ and
$(c^{\text{exp}}_{w},c^{\text{exp}}_{h},w^{\text{exp}},h^{\text{exp}})$
represent the original the expanded proposal.

$\begin{split}&m=\min(0.4w,0.4h)\\\
&(w^{\text{exp}},h^{\text{exp}})=(w,h)+m\\\
&(c_{w}^{\text{exp}},c_{h}^{\text{exp}})=(c_{w},c_{h})\end{split}$ (6)

Box2Heatmap. Eq. 7 explains the Box2Heatmap block in Fig. 4.
$\mathbf{H}\in\mathbb{R}^{H\times W}$ represents the output heatmap.
$(x_{0},y_{0})$ and $(x_{1},y_{1})$ denotes the coordinates of the left top
and right bottom point of the original proposal, where
$(x_{0},y_{0})=(c_{w},c_{h})-(w,h)/2$ and
$(x_{1},y_{1})=(c_{w},c_{h})+(w,h)/2$ .

$\mathbf{H}_{ji}=\begin{cases}1&(x_{0}^{\text{exp}}+\frac{i}{W}w^{\text{exp}},y_{0}^{\text{exp}}+\frac{j}{H}h^{\text{exp}})\in[x_{0},x_{1}]\times[y_{0},y_{1}]\\\
0&\text{otherwise}\end{cases}$ (7)

Clustering. The clustering algorithm used in building prototypes is initially
proposed by SwAV (Caron et al., 2020) and based on optimal transport (Villani
et al., 2009). The optimal transport problem is an optimization problem that
aims to find an optimal mapping $\gamma^{*}\in\mathbb{R}_{+}^{n\times m}$ from
a source distribution $\mathbf{a}=[a_{1},...,a_{n}],\sum_{i=1}^{n}a_{i}=1$ to
target distribution $\mathbf{b}=[b_{1},...,b_{n}],\sum_{i=1}^{m}b_{i}=1$,
which minimizes the overall transport cost. Let
$\mathbf{M}\in\mathbb{R}^{n\times m}$ denote the cost matrix, where
$\mathbf{M}_{ij}$ denote the cost of moving mass from $a_{i}$ to $b_{j}$. This
problem is formulated in Eq. 8.

$\begin{split}&\gamma^{*}=\arg\min_{\gamma\in\mathbb{R}_{+}^{n\times
m}}\sum_{i,j}\gamma_{ij}\mathbf{M}_{ij}\\\ &\text{ s.t.
}\gamma\mathbf{1}=\mathbf{a};\gamma^{T}\mathbf{1}=\mathbf{b};\gamma\geq
0\end{split}$ (8)

The clustering procedure consists of the iterations of two steps. First, an
optimal transport $\gamma^{*}$ is computed between a set of centroids
$\mathbf{C}\in\mathbb{R}^{c\times d}$ and instance-level prototypes
$\mathbf{Q}\in\mathbb{R}^{q\times d}$, where $c$ represents the number of
centroids and $q$ represents the number of instance-level prototypes for a
given class in a mini-batch. Note that we apply data augmentation to generate
more instance-level prototypes from a limited set of support images. The
negative dot similarity $\mathbf{M}=-\mathbf{C}\mathbf{Q}^{\top}$ is used as
the cost matrix, and $\mathbf{a},\mathbf{b}$ are set as uniform. The solution
$\gamma^{*}$ is estimated from the sinkhorn knopp algorithm (Cuturi, 2013).
Second, a momentum update is made to the centroids with
$\mathbf{C}=(1-\beta)\mathbf{C}+\beta\gamma^{*}\mathbf{Q}$, where $\beta$ is
the momentum parameter. Clustering is applied on instance prototypes per
class. We use $c=10$ and $\beta=0.002$ for all experiments and compute the
average of the 10 centroids as the prototype for each class. For background
prototypes, we directly use centroids without averaging. This optimal-
transport-based online clustering procedure is commonly used in prototype
learning (Zhou et al., 2022a; Wang et al., 2022). In hindsight, we also try
directly setting class-level prototypes as the mean of instance prototypes for
each class without augmentation. This yields almost identical results on open-
vocabulary experiments for both COCO and LVIS with ViT-L/14, other settings
are not tested. This suggests that the details of the clustering procedure may
not be a critical element within our method.

###  A.4 Comparison of LVIS Results in Few-Shot Object Detection

Table A1: Performance comparison with existing few-shot object methods on LVIS
dataset. We report box AP as evaluation metrics.

Method | APr | APc | APf | AP
---|---|---|---|---
DiGeo (Ma et al., 2023) | 16.6 | 22.8 | 28 | 24.4
DE-ViT (Ours) | ViT-S/14 | 23.4 | 22.8 | 22.5 | 22.8
ViT-B/14 | 26.8 | 26.5 | 25.3 | 26
ViT-L/14 | 33.6 | 30.1 | 30.7 | 30.9

LVIS has been regarded as a highly challenging dataset for few-shot object
detection (Wang et al., 2020). To the best of our knowledge, only DiGeo
reports few-shot results on LVIS v1. Note that TFA (Wang et al., 2020) reports
their results on LVIS v0.5, which is deprecated and no longer distributed.
Tab. A.4 shows that our method outperforms DiGeo in all metrics.


# Tensor Products and Hyperdimensional Computing

Frank Qiu Statistics Department; University of California, Berkeley

###### Abstract

Following up on a previous analysis of graph embeddings, we generalize and
expand some results to the general setting of vector symbolic architectures
(VSA) and hyperdimensional computing (HDC). Importantly, we explore the
mathematical relationship between superposition, orthogonality, and tensor
product. We establish the tensor product representation as the central
representation, with a suite of unique properties. These include it being the
most general and expressive representation, as well as being the most
compressed representation that has errorrless unbinding and detection.

##  1 Intro

This is a brief note following up on a previous analysis of graph embeddings
[3]. We generalize some of the results in that analysis to a general vector
symbolic architecture (VSA) or hyperdimensional computing (HDC) scheme, and we
also establish some new results along the way. More specifically, we analyze
the interplay between superposition, orthogonality, and the tensor product.
Importantly, we that show that the tensor product representation are the
central representation among bound representations that use superposition.

##  2 The Tensor Product and the Superposition Principle

Many, if not all, VSA/HDC schemes make use of a bundling operator to represent
a set of elements. In a majority of cases, this bundling operator is addition,
and a set is represented by the superposition, or sum, of its elements. We
precisely define the superposition principle.

######  Definition 2.1 (The Superposition Principle).

Given an embedding space $V$ for objects $\boldsymbol{V}$, we embed a set
$\boldsymbol{S}=\\{\boldsymbol{v_{1}},\cdots,\boldsymbol{v_{n}}\\}$ as the
superposition, or sum, of its elements’ embeddings:

$S=\sum_{i=1}^{n}v_{i}$

Similarly, given a set of weights $\\{\alpha_{1},\cdots,\alpha_{n}\\}$ for
elements of $\boldsymbol{S}$, the weighted set $\boldsymbol{S_{\alpha}}$ is
embedded as the weighted superposition of elements’ embeddings:

$S_{\alpha}=\sum_{i=1}^{n}\alpha_{i}v_{i}$

###  2.1 Superposition and Multilinearity

The superposition principle requires sets of objects to be linear functions of
their weights and elements’ embeddings. This immediately establishes an
important property of binding operations that respect, or satisfy,
superposition.

######  Lemma 2.1 (Binding and Superposition).

Let $V$ and $W$ be embedding vector spaces. For any $n\in\mathbb{N}$, let
$\psi$ be a $n$-ary binding operation from $V$ to $W$:

$\psi:V_{1}\times\cdots\times V_{n}\rightarrow W$

where $V_{1}=\cdots=V_{n}=V$. If $\psi$ respects the superposition principle,
then $\psi$ is a multilinear map.

###### Proof.

Consider a finite set $S_{i}$ of $n$-tuples that only differ in their $i^{th}$
entries. For some finite index $J$, $S_{i}$ can be expressed as:

$S_{i}=\bigcup_{j\in J}(v_{1},\cdots,v_{i-1},v_{i_{j}},v_{i+1},\cdots,v_{n})$

By the superposition principle, the equivalent embedding of $S_{i}$ under
$\psi$ must be:

$\psi(S_{i})=\sum_{j\in
J}\psi(v_{1},\cdots,v_{i-1},v_{i_{j}},v_{i+1},\cdots,v_{n})$

Similarly, consider the embedding of the weighted tuple $(v_{1},\cdots,\alpha
v_{i},\cdots,v_{n})$. The superposition principle requires that:

$\psi(v_{1},\cdots,\alpha
v_{i},\cdots,v_{n})=\alpha\psi(v_{1},\cdots,v_{i},\cdots,v_{n})$

Hence, we see that $\psi$ is linear in the $i^{th}$ argument. Repeating this
analysis for each argument gives the result. ∎

In fact, we may repeat the argument of Lemma 2.1 for any function that
respects superposition, establishing a link between multilinearity and the
superposition principe.

######  Lemma 2.2 (Multilinearity and Superposition).

Let $V_{1},\cdots,V_{n}$ and $W$ be embedding spaces. Let $Q$ be a $n$-ary
function:

$Q:V_{1}\times\cdots\times V_{n}\rightarrow W$

If $Q$ respects superposition, then $Q$ is a multilinear function.

###  2.2 Generality and Expressivity of the Tensor Product

The superposition principle constrains all functions to be multilinear.
Applying this to binding, every binding operation has a unique linear
derivation from the tensor product,:

######  Theorem 2.1 (Generality of the Tensor Product).

Let $V$ and $W$ be embedding spaces. Every $n$-order binding operation $\psi$
has a unique linear derivation $\psi^{*}$ from the $n$-order tensor product
$\overset{n}{\otimes}V$ that makes the following diagram commute:

${V_{1}\times\cdots\times
V_{n}}$${\overset{n}{\otimes}V}$${W}$$\scriptstyle{\phi}$$\scriptstyle{\psi}$$\scriptstyle{\psi^{*}}$

where $V_{1}=\cdots=V_{n}=V$ and $\phi$ is the canonical map to the tensor
product.

###### Proof.

By Lemma 2.1, every $n$-order binding operation $\psi$ is a $n$-multilinear
map from $V$ to $W$. By the universality of the tensor product [2], there
exists a unique linear map $\psi^{*}:\overset{n}{\otimes}V\rightarrow W$ that
makes the diagram commute. ∎

The tensor product is the most general binding operation that respects
superposition, and every bound representation can be linearly derived from the
corresponding tensor product representation. In light of this, can a bound
representation possess functionality the corresponding tensor product
representation does not? The answer is no, and any operation that respects
superposition has an equivalent form involving the tensor product.

######  Theorem 2.2 (Expressivity of the Tensor Product).

Let $V$ and $W$ be embeddings spaces, with a $n$-order binding operation
$\psi$ from $V$ to $W$. Let $Q$ be a query function whose results are in
vector space $X$ and whose arguments are the embeddings $\psi(V)$, $V$, and
$W$ with multiplicities $m_{1}$, $m_{2}$, and $m_{3}$ respectively (zero
multiplicity included). If $Q$ respects superposition, then there exists a
unique corresponding query function $Q^{*}$ whose arguments are
$\overset{n}{\otimes}V$, $V$, and $W$ with multiplicities $m_{1}$,$m_{2}$, and
$m_{3}$ respectively that gives the same results as $Q$. $Q^{*}$ also respects
superposition and makes the following diagram commute:

${(\overset{n}{\otimes}V)^{m_{1}}\times V^{m_{2}}\times
W^{m_{3}}}$${\psi(V)^{m_{1}}\times V^{m_{2}}\times
W^{m_{3}}}$${X}$$\scriptstyle{\psi^{*}\times id\times
id}$$\scriptstyle{Q^{*}}$$\scriptstyle{Q}$ (1)

###### Proof.

Let us fix the arguments involving $V$ and $W$ to $v$ and $w$ respectively. We
first assume that $m_{1}=1$. Consider the following diagram:

${\prod_{i=1}^{n}V}$${\overset{n}{\otimes}V}$${\psi(V)}$${\overset{n}{\otimes}V}$${X}$$\scriptstyle{\phi}$$\scriptstyle{\psi}$$\scriptstyle{Q_{v,w}}$$\scriptstyle{Q_{v,w}^{*}}$$\scriptstyle{\psi^{*}}$

Since $Q_{v,w}\circ\psi$ is a multilinear map, by the universal property of
the tensor product there exists a linear map $Q^{*}_{v,w}$ such that
$Q^{*}_{v,w}\circ\phi=Q_{v,w}\circ\psi$. By Theorem 2.1, there exists a linear
map $\psi^{*}$ such that $\psi=\psi^{*}\circ\phi$. Putting everything together
gives:

$Q^{*}_{v,w}\circ\phi=Q_{v,w}\circ\psi=Q_{v,w}\circ\psi^{*}\circ\phi$

The map $Q^{*}_{v,w}\circ\phi$ is multilinear map and so has a unique linear
map $\tilde{Q}$ such that $Q^{*}_{v,w}\circ\phi=\tilde{Q}\circ\phi$. By
uniqueness of this induced map:

$\tilde{Q}=Q^{*}_{v,w}=Q_{v,w}\circ\psi^{*}$

Repeating this for every $v$ and $w$ uniquely determines a multilinear map
$Q^{*}$ that makes Diagram 1 commute. For the case where $m_{1}>1$, we can
repeat the previous procedure by fixing all arguments except a single copy of
$\psi(V)$ (fixing all other $m_{1}-1$ copies) in order to construct $Q^{*}$. ∎

###  2.3 Summary

In this section, we showed that the superposition principle constrains all
functions, including binding operations, to be multilinear functions. This
immediately allowed us to derive two important properties of the tensor
product:

  1. 1.

The tensor product is the most general binding operation.

  2. 2.

The tensor product is the most expressive binding operation.

From the first property, for any binding operator its bound representation can
be expressed as a linear function of the corresponding tensor product
representation. Hence, all bound representations are derivatives of the tensor
product representation, the most general representation. From the second
property, we see that any operation on a bound representation has an
equivalent form involving the corresponding tensor product representation. In
other words, the tensor product can do anything another bound representation
does, and it is the most expressive representation.

##  3 Superposition, Unbinding, and Orthogonality

A suite of operations fundamental to VSA/HDC schemes are the (partial)
unbinding operations. This is, given the bound representation
$\psi(v_{1},\cdots,v_{n})$, we wish to unbind one or multiple elements from
it. For example, say we represent the directed edge $(v,w)$ by the bound
representation $\psi(v,w)$. If we wish to identify the terminal vertex of this
edge, we would unbind $v$ from $\psi(v,w)$ to return $w$. Our edge unbinding
operation takes the form:

$\psi^{-1}:V\times\psi(V,V)\rightarrow V\qquad;\qquad\psi^{-1}(v,\psi(v,w))=w$

On the other hand, consider the case where we unbind by an unrelated vertex
$u$. In this case, we are unbinding by a spurious vertex and therefore the
unbinding result will be noise. Ideally, this noise should be $0$, but there
is one more problem. Consider the orthogonal decomposition of the spurious
vertex $u$ onto $v$:

$u=\alpha v+u_{v}^{\perp}$

If our unbinding procedure respects superposition, we can decompose the
unbinding result as:

$\displaystyle\psi^{-1}(u,\psi(v,w))$ $\displaystyle=\psi^{-1}(\alpha
v,\psi(v,w))+\psi^{-1}(u_{v}^{\perp},\psi(v,w))$ $\displaystyle=\alpha
w+\psi^{-1}(u_{v}^{\perp},\psi(v,w))$

The first term follows by linearity, and we cannot get rid of it without
violating $\psi^{-1}(v,\psi(v,w))=w$. The best we can do is to make the second
term 0.

The above example showcases an interesting interaction between superposition,
unbinding, and orthogonality. The superposition principle constrains the
unbinding operations to be multilinear by Lemma 2.2. While we wish spurious
unbindings to be zero, by multilinearity we will always have a non-zero error
term proportional to the spurious object’s projection onto an involved object
and can only zero out the orthogonal portion. This suggests that object
embeddings be orthogonal, or nearly so, to accurate distinguish between them
when performing unbinding operations. This also suggests that in order for a
bound representation to have accurate unbinding operations, the bound
representation needs to preserve the geometric information of its bound
objects. We shall show that the tensor product representation is the most
compressed representation that preserves all geometric information and has
perfectly accurate unbinding operations.

###  3.1 Unbinding and Orthogonality

In the edge example, we assumed the existence of orthogonal projections. This
is a mild assumption, since in all practical settings the embeddings spaces
are the usual finite-dimensional real vector spaces $\mathbb{R}^{n}$ or
complex vector spaces $\mathbb{C}^{n}$. These are inner product spaces and
hence equipped with orthogonal projection. Therefore, we shall continue
assuming the existence of orthogonal projection.

Consider a binary binding operation $\psi:V\times V\rightarrow W$. We wish any
left-unbinding operation $\psi^{-1}$ to satisfy the following criteria:

  1. 1.

$\psi_{L}^{-1}(v,\psi(v,w)))=w$. (Correct Unbinding)

  2. 2.

$\psi_{L}^{-1}(u,\psi(v,w))\approx 0$ for any $u\neq v$. (Small Error Terms)

Assuming $\psi_{L}^{-1}$ correctly unbinds elements (Criteria 1), orthogonal
decomposition shows that object embeddings must be orthogonal to have zero
error terms.

######  Lemma 3.1.

For a binary binding operation $\psi:V\times V\rightarrow W$, let
$\psi_{L}^{-1}$ be any left-unbinding operation $\psi_{L}^{-1}:V\times
W\rightarrow V$ that respects superposition and correctly unbinds a set of
objects $S=\\{v_{1},\cdots,v_{d}\\}$. If $\psi_{L}^{-1}$ has zero error for
mismatching pairs from $S$, then $S$ must be an orthogonal set.

###### Proof.

WLOG, let us assume that $S$ spans $V$, or else we can restrict ourselves to
the span of $S$. Since $\psi_{L}^{-1}$ correctly unbinds elements of
$\\{v_{1},\cdots,v_{d}\\}$, we have:

$\psi_{L}^{-1}(v_{i},\psi(v_{i},w))=w$

for all $v_{i}\in S$ and any $w$. Suppose for some $i\neq j$, $v_{i}$ had non-
zero projection onto $v_{j}$, with the orthogonal decomposition $v_{i}=\alpha
v_{j}+v_{i}^{\perp}$ where $\alpha\neq 0$. Since $\psi$ accurately unbinds
elements of $S$, by Lemma 2.2 we have:

$\psi_{L}^{-1}(v_{i},\psi(v_{i},w))=\psi_{L}^{-1}(\alpha
v_{j}+v_{i}^{\perp},\psi(v_{i},w))=\alpha
w+\psi_{L}^{-1}(v_{i}^{\perp},\psi(v_{i},w))$

If the above expression is non-zero, we violate the assumption that unbinding
is errorless. Otherwise, the second term must equal $-\alpha w$. Since $S$
spans $V$, we can express $v_{i}^{\perp}=\sum_{k\neq i}\beta_{k}v_{k}$.
Plugging this into the second term and using linearity gives:

$0\neq-\alpha w=\psi_{L}^{-1}(v_{i}^{\perp},\psi(v_{i},w))=\sum_{k\neq
i}\beta_{k}\psi_{L}^{-1}(v_{k},\psi(v_{i},w))$

Since we assumed the second term is non-zero, at least one of the error terms
in the sum is non-zero. In either case, at least one mismatch term must be
non-zero. ∎

Now consider a right-unbinding operation $\psi_{R}^{-1}$, which takes the
form:

$\psi_{R}^{-1}:W\times V\rightarrow
V\qquad;\qquad\psi_{R}^{-1}(\psi(v,w),w)=v$

A similar argument establishes the same orthogonality requirement on the
object embeddings for right-unbinding operations that correctly unbind. These
two results can be summarized in the following result.

######  Theorem 3.1.

(Unbinding and Orthogonality) For a binary binding operation $\psi:V\times
V\rightarrow W$, let $\psi^{-1}$ be left or right-unbinding operation that
respects superposition and correctly unbinds a set $S$ of objects. $\psi^{-1}$
can have zero error only if $S$ is an orthogonal set.

###  3.2 Effect of the Binding Operator

In the previous section, we fixed the bound representation and looked at the
properties of unbinding operators. In this section, we ask the reverse
question: what bound representations allow for correct and noiseless
unbinding? We first show that for second order bound representations, only the
tensor product representation has correct and zero-error unbinding (up to
linear isomorphism).

######  Theorem 3.2 (Binary Errorless Unbinding).

Let $S$ be a set of $d$ orthonormal embeddings. Up to linear isomorphism, the
tensor product representation is the unique second order representation with
minimum dimension that has left and right unbinding operations that respect
superposition, correctly unbind, and have zero error.

###### Proof.

First, we show that the tensor product satisfies the statement’s conditions.
WLOG, assume $S$ is a basis for the embedding space $V$. Otherwise, we can
restrict ourselves to the span of $S$. Fixing a basis, the tensor product in
coordinates is the outer product of the coordinate vectors:

$v\otimes w=vw^{T}$

We define left(right) unbinding by left(right) multiplication:

$\psi_{L}^{-1}(v,v\otimes
w)=v^{T}(vw^{T})=w\qquad;\qquad\psi_{R}^{-1}(v\otimes w,w)=(vw^{T})w=v$

By orthonormality of $S$, it is easy to see that these unbinding operations
satisfy the statement’s conditions.

Now, suppose we have a bound representation $\psi(V,V)$ that satisfies the
statement’s condition. Consider the set of $d^{2}$ elements
$\\{\psi(v_{i},v_{j})|v_{i},v_{j}\in S\\}$. Consider unbinding on the left by
$v_{1}$. Since unbinding is errorless, we see the elements $\psi(v_{1},v_{j})$
are sent to non-zero values while the elements $\psi(v_{i},v_{j})$ are sent to
0 for $i>1$. Hence, each $\psi(v_{1}.v_{j})$ is linearly independent from
$\psi(v_{i},v_{j})$ for $i>1$. Unbinding on the left by each $v_{i}$, we see
the elements $\psi(v_{i},v_{j})$ are linearly independent if they differ in
the first argument. Repeating the same argument for unbinding the right, we
also see that two elements are linearly independent if their second arguments
differ. Hence, the set $\\{\psi(v_{i},v_{j})|v_{i},v_{j}\in S\\}$ is linearly
independent and the bound representation space $\psi(V)$ (the span of the
elements $\psi(v_{i},v_{j})$) has dimension $d^{2}$. By Theorem 2.1, there is
a unique linear map $\psi^{*}$ from the tensor product $V\otimes V$ into the
bound representation space. Since both are finite-dimensional spaces with the
same dimension, $\psi^{*}$ is a linear isomorphism and the bound
representation is linearly equivalent to the tensor product. ∎

###  3.3 Generalizing to Iterated Representations

The previous results can be generalized to a special class of $n$-order bound
representation.

######  Definition 3.1.

We say an $n$-order bound representation $\psi_{n}(v_{1},\cdots,v_{n})$ is an
iterated representation if it can be expressed as:

$\psi_{n}(v_{1},\cdots,v_{n})=\psi(v_{1},\psi(v_{2},\psi(\cdots,\psi(v_{n-1},v_{n})))$

for some binary binding operation $\psi:V\times V\rightarrow V$.

An iterated representation is one that is the result of iteratively binding
each element via a binary binding $\psi$. These include the bound
representations generated by the Hadamard product, convolution, circular
correlation, and any of their variants. For an iterated representation
generated by binding $\psi$, unbinding multiple elements amounts to repeated
application of an unbinding operation $\psi^{-1}$ for the generator $\psi$.
Therefore, the results of the previous subsection apply to iterated
representation. In particular, Theorem 3.1 applies and object embeddings need
to be orthogonal for iterated representations.

######  Theorem 3.3.

Consider a set of $d$ objects $S$. For an $n$-order iterated representation
generated by binary binding $\psi$, let $\psi^{-1}$ be a left(right)-unbinding
operation. If $\psi^{-1}$ is correct and errorless, then $S$ must be an
orthogonal set.

###### Proof.

Unbinding the iterated representation by the elements $(u_{1},\cdots,u_{k})$
means iteratively unbinding each $u_{i}$ by repeated application of
$\psi^{-1}$.Restricting ourselves to the first application and applying
Theorem 3.1 suffices. ∎

Similarly, we can generalize Theorem 3.2 to give a negative result for
iterated representations.

######  Theorem 3.4.

No iterated representation has correct and errorless unbinding.

###### Proof.

Let assume the order $n=2$, and let $dim(V)=d$. Since the generating binding
operator $\psi:V\times V\rightarrow V$ preserves the embedding space, we see
the second order bound representation has dimension $d$ while the tensor
product has $d^{2}$. The bound representation cannot be equivalent to the
tensor product representation, and by Theorem 3.2 it cannot have correct and
errorless unbinding. For the case of $n>2$, unbinding by two elements is
equivalent to the above situation. ∎

Intuitively, we see errorless unbinding requires that the embeddings be
orthgonal. Assuming that, for errorless unbinding requires a bound
representation to preserve the geometric information of its bound pairs. For
$d$ elements, there are $d^{2}$ unique pairs, and so we need at least $d^{2}$
parameters to encode their geometric information. This means that compressed
bindings like the Hadamard, convolution, and circular correlation are
necessarily lossy and cannot have errorless unbinding. Only the tensor product
preserves all geometric information and has errorless unbinding.

###  3.4 The Detection Operation

A related operation to unbinding is detecting the presence of a bound tuple.
For a $n$-order bound representation $\psi:\prod\limits_{i=1}^{n}V\rightarrow
W$, the detection operation is a map
$D:\prod\limits_{i=1}^{n}V\times\psi(V)\rightarrow\mathbb{R}$. Simplifying
notation by denoting $n$-tuples with bold symbols, the detection operation has
the following behavior:

$D((\boldsymbol{v},\psi(\boldsymbol{w}))=\begin{cases}1&\boldsymbol{v}=\boldsymbol{w}\\\
0&\boldsymbol{v}\neq\boldsymbol{w}\end{cases}$

Given $n$-tuples of the embedding space $V$, we intuitively want embed each
distinct tuples of element to distinct bound representations. By
superposition, these bound representations need to be linearly independent.
This implies we need a $d^{n}$-dimensional space to embed $n$-tuples of $d$
things in such a way that we can accurately detect each distinct tuple. This
is formalized in the following statement.

######  Theorem 3.5 (Minimum Dimension for Accurate Detection).

Let $\psi$ be a $n$-order binding operation of $V$ into $W$. For a set of $d$
objects $S=\\{v_{1},\cdots,v_{d}\\}$, suppose there exists an accurate
detection function $D$ that respects superposition and can identify every
$n$-tuple of $S$. Then, the bound representation needs to have at least
dimension $d^{n}$.

###### Proof.

The detection function is a multilinear map:

$D:\prod\limits_{i=1}^{n}S\times\psi(V)\rightarrow\mathbb{R}$

For each $\boldsymbol{s}\in\prod\limits_{i=1}^{n}S$, consider the induced
linear function where we fix the query element $\boldsymbol{s}$:

$D_{\boldsymbol{s}}(\cdot)=D(\boldsymbol{s},\cdot)$

There are a total of $d^{n}$ such maps, one for each $n$-tuple in $S$. Since
$D$ is accurate, each functional $D_{\boldsymbol{s}}$ is a linearly
independent element of the dual space $W^{*}$, since for every
$\boldsymbol{s}$ we have:

$D_{\boldsymbol{s}}(\psi(\boldsymbol{v}))=\begin{cases}1&\boldsymbol{s}=\boldsymbol{v}\\\
0&\boldsymbol{s}\neq\boldsymbol{v}\end{cases}$

Therefore $W^{*}$ has dimension at least $d^{n}$. For finite dimensional
vector spaces, the dual space is isomorphic to the original space and $W$ also
has dimension at least $d^{n}$. ∎

######  Corollary 3.5.1 (Tensor Product and Detection).

Given a set $S$ of $d$ orthonormal object embeddings, the $n$-order tensor
product is the unique $n$-order representation with minimal dimension that
accurately detects $n$-tuples of $S$ (up to linear isomorphism).

###### Proof.

The $n$-order tensor product has dimension $d^{n}$. By orthonormality,
successive multiplication on the left or right yields an accurate detection
function. Together with Theorem 3.5, the tensor product is a representation
with minimum dimension equipped with an accurate detection function. If
$\psi(V)$ is any other such representation, by Theorem 2.1 there exists a
linear map $\psi^{*}$ from the tensor product to $\psi(V)$. Since both
representations have the same dimension, they must be linearly isomorphic. ∎

###  3.5 Summary

In this section, we saw that object embeddings need to be orthogonal in order
to have correct and errorless unbinding. Conversely, we saw that given a set
of orthonormal embeddings, the tensor product is the unique second order
representation with minimal dimension that has errorless left and right
unbinding operations. This is because errorless unbinding requires a bound
representation to preserve the geometric information of all bound pairs. Given
$d$ elements, there are $d^{2}$ possible bound pairs, and we intuitively need
$d^{2}$ parameters to encode every pairs’ geometric data. This implies that
compressed representations via the Hadamard product, convolution, circular
correlation, and their analogues cannot have errorless unbinding. Indeed, we
established two more properties of the tensor product in the case of
orthonormal embeddings:

  1. 1.

The tensor product is the most compressed representation that has errorless
unbinding.

  2. 2.

The tensor product is the most compressed representation that has an accurate
detection function.

##  4 Brief Capacity Analysis

Here, we briefly compare the effects of the previous sections on the capacity
of bound representations. We focus on the bound representations of the tensor
product and the Hadamard product, with object embeddings generated by
normalized Rademacher codes, which are vector whose entries are independent
Rademacher random variables. We first state some basic results concerning
Rademacher codes from [3]:

######  Theorem 4.1.

Let $Z=\frac{1}{d}\langle u,v\rangle$, where $u,v$ are $d$-dimensional
Rademacher vectors. Then,

  1. 1.

$\frac{d(Z+1)}{2}\sim Binonmial(d,\frac{1}{2})$.

  2. 2.

$E(Z)=0$ and $Var(Z)=\frac{1}{d}$

  3. 3.

$P(\max_{i\neq j}\limits|\langle x_{i},x_{j}\rangle|>\epsilon)\geq
1-2\binom{k}{2}e^{-\frac{d}{4}\epsilon^{2}}$

  4. 4.

$Z$ is sub-Gaussian with parameter $\frac{1}{\sqrt{d}}$.

  5. 5.

Let $Z_{1},\cdots,Z_{n}$ be iid copies of $Z$. Then $Z^{n}$ is sub-Gaussian
with parameter $d^{-n/2}$.

###### Proof.

We have $Z=\frac{1}{d}\sum u_{i}v_{i}$ where $u_{i},v_{i}$ are independent
Rademacher. The product of two independent Rademacher random variables is also
a Rademacher random variable, so $dZ$ is the sum of $d$ Rademacher random
variables. If $B$ = Bernoulli($\frac{1}{2}$), then $2B-1$ is a Rademacher
random variable. Hence, $d(Z+1)/2$ is $Binomial(d,\frac{1}{2})$. The second
statement follows from the first. For the third, we use the classic
concentration inequality for averages of Rademachers [1]:

$P(|Z|>\epsilon)\leq\exp{-\frac{d\epsilon^{2}}{2(1+\epsilon/3)}}\leq\exp{-\frac{d\epsilon^{2}}{4}}$

Using a union bound over all pairs proves the third claim.

It is well-known a Rademacher random variable is sub-Gaussian with parameter
1:

$E(\exp{\lambda X})\leq\exp{\lambda^{2}/2}$

Hence, as $Z$ is the average of $d$ independent Rademachers:

$\displaystyle E(\exp{\lambda Z})$
$\displaystyle=E(\exp{\lambda\sum\frac{X_{i}}{d}})$ $\displaystyle=\prod
E(\exp{\frac{\lambda}{d}X_{i}})$
$\displaystyle=E(\exp{\frac{\lambda}{d}X_{i}})^{d}$
$\displaystyle\leq\exp{\lambda^{2}/(2d)}$

Hence, $Z$ is sub-Gaussian with parameter $\frac{1}{\sqrt{d}}$.

We consider the product $\prod\limits^{n}Z_{i}$ of $n$ iid copies of $Z$, and
can be written as:

$\frac{1}{d^{n}}\prod^{n}_{i=1}(\sum_{j=1}^{d}X_{ij})$

where each $X_{[}ij]$ is an independent Rademacher. Expanding the product:

$\frac{1}{d^{n}}\sum_{i=1}^{d^{n}}X^{\prime}_{i}$

where each $X^{\prime}_{i}$ is an independent Rademacher. Repeating the same
calculation as above yields:

$E(\exp{\lambda\prod\limits^{n}Z_{i}})\leq\exp{\lambda^{2}/(2d^{n})}$

Hence, $\prod\limits^{n}Z_{i}$ is sub-Gaussian with parameter $d^{-n/2}$. ∎

###  4.1 Capacity of Hadamard Representations

We analyze the $n$-order Hadamard representation, using $d$-dimensional
normalized Rademacher codes. All operations will be scaled by a common factor,
and for clarity we suppress this factor. For the $n$-tuple
$\boldsymbol{v}=(v_{1},\cdots,v_{n})$, let us denote its bound representation
by $\boldsymbol{v}^{\odot}$. Consider the superposition of $k$ distinct
$n$-tuples:

$W=\sum_{i=1}^{k}\boldsymbol{v}^{\odot}$

For this iterated representation, ignoring a scaling factor the unbinding
operator is just the Hadamard product again. That is:

$v_{1}\odot(v_{1}\odot v_{2})=v_{2}$

Suppose we unbind the first element $v_{11}$ of the first $n$-tuple in the
superposition. By the distributivity of the Hadamard product, we have:

$v_{11}\odot
W=v_{11}\odot\sum_{i=1}^{k}\boldsymbol{v}^{\odot}=v_{12}\odot\cdots\odot
v_{1n}+\sum_{i=2}^{k}v_{11}\odot\boldsymbol{v}^{\odot}$

The second term is our noise term, and since the Hadamard product of
Rademacher vectors is Rademacher again, we see the signal term is a Rademacher
vector and the noise term is the sum of $k-1$ Rademacher vectors. Notice that
unbinding did not shrink the mismatch terms, even though the embeddings are
pseudo-orthogonal. This is expected, since by Theorem 3.2 only the tensor
product has errorless unbinding. Similarly, let us consider accurately
detecting the first $n$-tuple $\boldsymbol{v_{1}}$. This amounts to unbinding
by each entry of $\boldsymbol{v_{1}}$, resulting in:

$\boldsymbol{v_{1}}\odot(\sum_{i=1}^{k}\boldsymbol{v}^{\odot})=\boldsymbol{1}+\sum_{i=2}^{k}\boldsymbol{v_{1}}\odot\boldsymbol{v_{i}}^{\odot}$

where $\boldsymbol{1}$ denotes the vector whose entries are 1. We then sum the
result, which gives:

$d+\sum_{i=1}^{d(k-1)}r_{i}$

where each $r_{i}$ is an independent Rademacher random variable. On the other
hand, unbinding by a spurious $n$-tuple $\boldsymbol{u}$ results in the sum of
$k$ Rademacher random vectors. Summing this result gives:

$\sum_{i=1}^{(k-1)}r_{i}$

We have the following result:

######  Theorem 4.2.

For the $n$-order Hadamard representation, let $A$ denote event where the
above detection procedure returns the highest score for the correct tuple
$\boldsymbol{v}$ relative to $m$ other spurious tuples
$\boldsymbol{u_{1}}\cdots,\boldsymbol{u_{n}}$. Then, for some constant $C$ we
have:

$P(A)\geq 1-m\exp{-\frac{Cd}{k-1}}$

###### Proof.

Note that the event $A$ is the intersection of the individual events
$A_{i}=\\{D(\boldsymbol{v})>D(\boldsymbol{u_{i}})\\}$, where the correct
$\boldsymbol{v}$ has higher detection score than the spurious
$\boldsymbol{u_{i}}$. Then,

$P(A)=P(\cap A_{i})=1-P(\cup\\{A_{i}^{c}\\})$

Each $A_{i}^{c}$ has the same probability, and let $\epsilon_{1}$ and
$\epsilon_{2}$ denote the error terms for the correct and spurious cases
respectively. Since the entire result will be scaled by a factor of
$\frac{1}{d^{n}}$, we ignore it in the following computation:

$\displaystyle P(\cup A_{i}^{c})$
$\displaystyle\leq\sum_{i=1}^{M}P(A_{i}^{c})$ $\displaystyle=mP(A_{1}^{c})$
$\displaystyle=mP(d+\epsilon_{1}\leq\epsilon_{2})$
$\displaystyle=mP(\epsilon_{2}-\epsilon_{1}\geq d)$

A difference of Rademacher sums is still a Rademacher sum, so
$\epsilon_{2}-\epsilon_{1}$ is a sum of $(k-1)d+kd=2(k-1)d$ Rademachers.
Hence, using the standard Rademacher concentration inequality:

$\displaystyle P(\epsilon_{2}-\epsilon_{1}\geq d)$ $\displaystyle\leq
e^{-\frac{d/(2k-1)}{2(1+(3((2k-1))^{2})^{-1})}}$ $\displaystyle\leq
e^{-\frac{Cd}{k}}$

for a sufficiently large constant $C$. Plugging this in gives:

$P(A)\geq 1-me^{-\frac{Cd}{k}}$

∎

Thus, relative to any fixed number of altnerate queries $m$, we see that the
capacity of Hadamard representations need to scale as $O(d)$ in order to
retain accurate detection.

###  4.2 Capacity of Tensor Representations

We now analyze the same situation for tensor product representations. For the
$n$-tuple $\boldsymbol{v}=(v_{1},\cdots,v_{n})$, we us denote its tensor
representation by $\boldsymbol{v}^{\otimes}$. Consider the same superposition
of $k$ distinct $n$-tuples:

$W=\sum_{i=1}^{k}\boldsymbol{v}^{\otimes}$

Unbinding amounts to multiplying by the corresponding embedding, and consider
again unbinding on the left by the first entry of $\boldsymbol{v_{1}}$:

$v_{11}^{T}W=\boldsymbol{v_{-11}}+\sum_{i=2}^{k}\langle
v_{11},v_{i1}\rangle\boldsymbol{v_{-i1}}^{\otimes}$

In particular, note that each summand in the error term is now weighted by
$\langle v_{11},v_{i1}\rangle$, which by Theorem 4.1 has mean 0 and variance
$\frac{1}{d}$. Unlike Hadamard representation, tensor representations leverage
orthgonality to shrink their error terms. This is expected from Theorem 3.4,
since tensor product is the unique binding that preserves all geometric
information. Similarly, let us consider the detecting the first tuple
$\boldsymbol{v_{1}}$, which amounts to multiplication by each of its entries.
This results in:

$1+\sum_{i=2}^{k}(\prod_{j=1}^{n}\langle v_{1j},v_{ij}\rangle)$

Each summand in the error term is the product of $n$ iid random variables that
have mean 0 and variance $\frac{1}{d}$ by Theorem 4.1. Hence, each summand has
mean 0 and variance $\frac{1}{d^{n}}$. Similarly, unbding by a spurious tuple
$\boldsymbol{u}$ results in:

$\sum_{i=1}^{k}(\prod_{j=1}^{n}\langle v_{1j},v_{ij}\rangle)$

which is now the sum of $k$ such summands. We have the corresponding result:

######  Theorem 4.3.

For the $n$-order tensor representation, let $A$ denote event where the above
detection procedure returns the highest score for the correct tuple
$\boldsymbol{v}$ relative to $m$ other spurious tuples
$\boldsymbol{u_{1}}\cdots,\boldsymbol{u_{n}}$. Then, for some constant $C$ we
have:

$P(A)\geq 1-m\exp{-\frac{d^{n}}{2k-1}}$

###### Proof.

We follow the proof of Theorem 4.2 until we need to bound $P(A_{i}^{c})$. Let
$\epsilon_{1}$ and $\epsilon_{2}$ denote the error terms for a correct and
spurious detection respectively:

$\displaystyle P(A_{i}^{c})$ $\displaystyle=P(1+\epsilon_{1}\leq\epsilon_{2})$
$\displaystyle=P(\epsilon_{2}-\epsilon_{1}\geq 1)$

Each summand in $\epsilon_{1}$ and $\epsilon_{2}$ is a product of $n$ dot
products, which by Theorem 4.1 is sub-Gaussian with parameter $d^{-n/2}$.
Since the sum of $n$ independent sub-Gaussian random variables with parameter
$\sigma$ is sub-Gaussian with parameter $\sqrt{n}\sigma$, we see
$\epsilon_{2}-\epsilon_{1}$ is sub-Gaussian with parameter
$\sqrt{2k-1}d^{-n/2}$. Hence, using the standard sub-Gaussian concentration
inequality gives:

$P(A_{i}^{c})=P(\epsilon_{2}-\epsilon_{1}\geq 1)\leq\exp{-\frac{d^{n}}{2k-1}}$

∎

##  5 Memory and Capacity Comparison

The $n$-order Hadamard representation uses $d$ parameters with a capacity
scaling of $O(d)$ from Theorem 4.2, while the $n$-order tensor representation
uses $d^{n}$ parameters with a capacity of $O(d^{n})$. The two have the same
memory-capacity ratio. While we use many more parameters with the tensor
product representation, it can store proportionately more elements accurately
in superposition. This is partly because the tensor product encodes all the
geometric information and can leverage this information when performing
unbinding and detection operations. The Hadamard, as a compressed
representation, cannot preserve all geometric data and leverage it to control
noise terms.

This memory-capacity comparison is especially relevant for applications where
the complexity of the representation scales with the order of the binding:
complex bindings means the complicated superposition, where many things are
stored together. One point where this analysis fails is where the number of
bound elements is high but the number of superimposed elements is low. This is
relevant for sparse representations of complex objects.

##  6 Conclusion

We established some theoretical properties relating superposition, the tensor
product, and orthgonality. Importantly, we saw the tensor product is
especially unique among all bound representations that respect superposition.
Theorems 2.1 and 2.2 show tensor representation are the most general and
expressive representation: any bound representations and its suite of
operations can be derived from the tensor product. Theorems 3.4, 3.2, 3.5.1
show that the tensor product is the most compressed representation that can
perform errorless unbinding and detection. We hope that the analysis and
results in the paper prove useful for the VSA/HDC community, giving some
insight into the mathematical consequences of the binding operation choice.

## References

  * [1] Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet.  Concentration Inequalities, pages 208–240.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2004.
  * [2] Serge Lang.  Algebra.  Springer, New York, NY, 2002.
  * [3] Frank Qiu.  Graph embeddings via tensor products and approximately orthonormal codes, 2023.