# Improving Vision-and-Language Navigation by Generating
Future-View Image Semantics

Jialu Li Mohit Bansal
UNC Chapel Hill
{jialuli<EMAIL_ADDRESS>
https://jialuli-luka.github.io/VLN-SIG

###### Abstract

Vision-and-Language Navigation (VLN) is the task that requires an agent to
navigate through the environment based on natural language instructions. At
each step, the agent takes the next action by selecting from a set of
navigable locations. In this paper, we aim to take one step further and
explore whether the agent can benefit from generating the potential future
view during navigation. Intuitively, humans will have an expectation of how
the future environment will look like, based on the natural language
instructions and surrounding views, which will aid correct navigation. Hence,
to equip the agent with this ability to generate the semantics of future
navigation views, we first propose three proxy tasks during the agent’s in-
domain pre-training: Masked Panorama Modeling (MPM), Masked Trajectory
Modeling (MTM), and Action Prediction with Image Generation (APIG). These
three objectives teach the model to predict missing views in a panorama (MPM),
predict missing steps in the full trajectory (MTM), and generate the next view
based on the full instruction and navigation history (APIG), respectively. We
then fine-tune the agent on the VLN task with an auxiliary loss that minimizes
the difference between the view semantics generated by the agent and the
ground truth view semantics of the next step. Empirically, our VLN-SIG
achieves the new state-of-the-art on both Room-to-Room dataset and CVDN
dataset. We further show that our agent learns to fill in missing patches in
future views qualitatively, which brings more interpretability over agents’
predicted actions. Lastly, we demonstrate that learning to predict future view
semantics also enables the agent to have better performance on longer paths.

##  1 Introduction

Figure 1: Overview of our proposed method VLN-SIG. We obtain the semantics of
an image with a pre-trained image tokenizer, and use codebook selection (Sec.
3.4) and patch semantic calculation (Sec. 3.3) to adapt it to efficient in-
domain VLN learning. We pre-train the agent on three proxy tasks (Sec. 3.5)
and fine-tune the agent using Action Prediction with Image Generation (APIG)
as the additional auxiliary task (Sec. 3.6).

In Vision-and-Language Navigation, the agent needs to navigate through the
environment based on natural language instructions. Many datasets have been
proposed to solve this challenging task [2, 23, 34, 42, 5]. Based on these
datasets, previous works aim to strengthen the navigation model or agent from
several aspects: understanding long and detailed instructions in different
languages, inferring and locating target objects based on common knowledge,
navigating in diverse and potentially unseen environments, and learning better
alignment between the environment and the instructions. However, most previous
work simplifies the navigation process as an action selection process, where
at each time step, the agent picks the action from a set of pre-defined
candidates. This simplification does not take advantage of human’s ability to
expect what scene will be more likely to happen next during navigation. For
example, given the instruction “Walk through the bedroom into the hallway.
Turn right and wait in the kitchen doorway.”, before walking out of the
bedroom, humans will expect the hallway to be a long passage with doors, and
the kitchen probably contains objects like a kitchen island and sink. Humans
have these expectations based on common sense knowledge and use them to select
candidates during navigation. Thus, in this paper, we explore whether AI
agents could also benefit from the ability to generate future scenes for
action selection during navigation.

[22] first explores the useful idea of generating future scenes with high
quality, based on history observations on an indoor Vision-and-Language
Navigation dataset. Furthermore, they adapt their synthetic future scenes for
VLN by replacing the original observations with the generated observations.
However, their replacement method did not enhance the agents’ performance on
the VLN task. The potential of using semantic information from generated
future observations is still underexplored. Thus, in this paper, we aim to
equip the agent with both the ability to predict future scenes and also
benefit from learning semantics in future generated observations.

We propose VLN-SIG: Vision-and-Language Navigation with Image Semantics
Generation. As shown in Figure 1, to first calculate the overall image
semantics, we tokenize the view images into visual tokens with a pre-trained
discrete variational autoencoder (dVAE). While the pre-trained dVAE has a
large vocabulary of 8192, we propose and compare static and dynamic codebook
selection processes to optimize a subset of the codebook at one time during
training. This helps the agent to learn the more important tokens and focus on
optimizing more difficult tokens. Then, we propose and compare three ways
based on mean value, block-wise weighted value, and sampling to represent the
semantics of all patches for efficient image semantics learning. In the pre-
training stage, we propose three tasks: Masked Panorama Modeling (MPM), Masked
Trajectory Modeling (MTM) and Action Prediction with Image Generation (APIG).
In Masked Panorama Modeling, the agent learns to predict the semantics of
multiple missing views in a full panorama. In Masked Trajectory Modeling, the
agent learns to predict the semantics of multiple steps in the full
trajectory. MPM and MTM together give the agent the ability to understand the
semantics in each visual token and learn to recognize the semantics contained
in each view. In Action Prediction with Image Generation, the agent mimics the
navigation process to predict the next step by generating the visual tokens
contained in the next navigation view. This task enables the agent to imagine
the next step view semantics before making actions. We then fine-tune the
agent on the step-by-step Vision-and-Language Navigation task. We further
enhance agents’ ability to predict future views by optimizing an auxiliary
task during navigation, which minimizes the difference between predicted
observations and the target observation. Though this task does not help the
agent make navigation decision directly, the future visual semantics injected
by this task helps the agent understand the environment better.

We conduct experiments on Room-to-Room (R2R) datasets [2] and Cooperative
Vision-and-Dialog Navigation (CVDN) dataset [42]. Empirical results show that
our proposed VLN-SIG outperforms the strong SotA agents [8, 10] by a relative
gain of 4.5% in goal progress (meters) on CVDN test leaderboard, and 3%
absolute gain in success rate on Room-to-Room test leaderboard. We further
demonstrate that our proposed codebook selection methods and patch semantic
calculation methods are crucial for learning to generate image semantics with
ablation studies. Besides, we show that our agent achieves better performance
for longer paths. Lastly, we show that our agent learns to fill in missing
patches in the future views, which brings more interpretability over agents’
predictions.

##  2 Related Work

Vision-and-Language Navigation. Vision-and-Language Navigation requires an
agent to navigate based on natural language instructions. The navigation
environment can be indoor [2, 23, 34, 42], outdoor [5, 32] or synthetic [30,
33, 39]. Previous work improves agents’ navigation performance from several
aspects. [27, 46, 25, 38, 44, 46, 24, 18] aim to learn better alignment
between language, environment and actions, while [41, 45, 26] improve agents’
generalization to unseen environments. Besides, graph information is
incorporated as additional signals for pre-exploration or back-tracking to aid
navigation [10, 47, 11, 15, 6, 7]. Furthermore, pre-training techniques have
been widely applied in VLN tasks, where [31, 17, 19, 8, 16, 35, 9] adapt pre-
trained cross-modal representations or perform in-domain VLN pretraining to
learn a better uni-modal and cross-modal representations. Different from
previous agents which make action solely by picking from a set of candidates,
we aim to equip the agent with the ability to generate semantics in future
views to aid decision making. [22] proposes a separate image generation model
to generate future scenes based on history observation in VLN. However, they
use the generated future scenes as a substitution for the original
environments, and their agent does not benefit from learning to navigate given
generated scenes. Differently, we propose three new pre-training tasks that
guide the agent to learn and generate the visual semantics in the
observations, and further enhance the agent’s ability to imagine the next step
view semantics by optimizing an auxiliary task during fine-tuning.

Vision-and-Language Pre-training. Pre-training has been a popular technique to
learn better uni-modal or multi-modal representations from large datasets.
Many tasks have been proposed. For example, Masked Language Modeling (MLM)
[12, 28] is used for language-only pre-training, and Masked Region Modeling
(MRM), and Image Text Matching (ITM) [40, 29] have been proposed for Vision-
and-Language pre-training. Recently, [3] proposes Masked Image Modeling (MIM)
for vision-only pre-training, where they mask several patches in an image and
predict their corresponding visual tokens. MIM has been extended successfully
to Vision-and-Language pre-training [4] and Video-and-Language pre-training
[14]. Inspired by them, we propose three VLN specific tasks based on MIM. To
effectively and efficiently adapt MIM to VLN pre-training, we change the task
objective to mask full images instead of patches in the image, and propose two
ways for visual token codebook selection and three methods to represent
overall image semantics.

##  3 Method

Figure 2: Illustration of the target semantics calculation process and our
proposed three proxy tasks.

###  3.1 Problem Setup

Vision-and-Language Navigation (VLN) requires an agent to navigate through the
environment based on natural language instructions. Formally, the agent
navigates from start location $B$ towards target location $C$ based on
language instructions $I$. At each navigation step, the agent has access to
the panorama view $P$ of the current location, which is discretized into 36
view images, and the agent will pick the next step from a set of $K$ navigable
locations $\\{C_{i}\\}_{i=1}^{K}$. The agent should predict a “STOP” action
when it reaches the target location $C$.

###  3.2 Pre-training Overview

In the pre-training stage, the agent is pre-trained on six proxy tasks as in
[8] and the three proxy tasks we propose in this paper. Specifically, the six
tasks we adopt are Masked Language Modeling (MLM), Masked Region Modeling
(MRM), Instruction Trajectory Matching (ITM), Single-step Action
Prediction/Regression (SAP/SAR), and Spatial Relationship Prediction (SPREL).
Details of these tasks can be found in Appendix.

Besides these, we further propose three tasks to help the agent learn to
generate image semantics based on multi-modal information to aid decision
making during navigation (Figure 2). Formally, given an image
$v_{i}\in\mathbb{R}^{H\times W\times C}$, we tokenize the image into $N$
visual tokens $\\{m_{ij}\\}_{j=1}^{N}$ with an image tokenizer, where each
visual token $m_{ij}$ belongs to the vocabulary $T=\\{1,...,|T|\\}$, and
$N=HW/P^{2}$, $P$ is the patch size. Following [3], we adopt the pre-trained
discrete variational autoencoder (dVAE) from [37] to compute the probability
$p_{ij}\in\mathbb{R}^{|T|}$ ($\sum_{k=1}^{|T|}p_{ijk}=1$) for each visual
token:

$p_{ij1},...,p_{ij|T|}=\mathrm{dVAE\\_Enc}(v_{i})$ (1)

#### Improving Efficiency by Generating Overall Image Semantics.

Each visual token contains specific semantic information in the image. In
Masked Image Modeling used in previous vision transformer pre-training [3, 4],
the model learns to predict the visual token for each masked patch in an image
to learn the semantics for each patch. Different from them, we directly mask
the full image and predict the overall semantics of the image. Our approach is
better in both memory cost and speed for VLN tasks. First, by masking the full
image, we are able to directly use the pre-extracted features and eliminate
the need to tune the visual backbone that encodes images with masked patches.
Our approach is more than two times faster than [8], which tunes the visual
backbone end-to-end to enhance the agents’ performance. Second, directly
masking the full image and generating the overall semantics saves memory. It
does not need to load the visual backbone in memory, and it takes the image
representation as input, shrinking the input sequence length from $N*A$ (since
previous MIM work [3] takes the patch representation as input) to $A$, where
$A$ is the sequence length of navigation history, and $N$ is the number of
patches in one image. To use our approach, it’s important to have a good
representation of the overall semantics of the image as the target. Thus, we
explore and compare three ways to represent the probability of generating the
overall semantics of the image in Sec. 3.3.

Furthermore, since the discrete variational autoencoder is learned from a
large amount of text-image pairs collected from the internet, not every
learned visual token in the vocabulary is of equal importance for the views in
the Vision-and-Language Navigation environment. Thus, we propose two ways to
optimize over a subset of visual tokens $S\subseteq T$ in Sec. 3.4.

Finally, we describe our three newly proposed pre-training proxy tasks that
help the agent learn to generate the semantics of an image Sec. 3.5.

###  3.3 Overall Image Semantics Generation

In Vision-and-Language Navigation pre-training, the vision-modality input
contains navigation history, which is represented as a sequence of $A$ views.
If we predict the generation of all masked patches in one image, it results in
an input sequence length of $A*N$, which makes it computationally infeasible
for VLN pre-training. Thus, we propose and compare three ways to efficiently
predict overall image semantics generation probabilities.

#### Mean Patch Probability.

The easiest way to represent the overall generation probability is to take the
mean of all patches’ probabilities. Specifically, given an image $v_{i}$, we
represent the generation probability $p^{o_{m}}_{ik}$ as:

$p^{o_{m}}_{ik}=\frac{1}{N}\sum_{j=1}^{N}{p_{ijk}}$ (2)

where $o$ indicates overall generation probability and $m$ indicates mean
patch probability.

#### Sample Patch Probability.

Using the mean patch probability has one main drawback: when we optimize the
KL-divergence loss between the predicted probability $\hat{p}^{o_{m}}_{ik}$
and the ground truth probability $p^{o_{m}}_{ik}$, it does not guarantee that
the agent learns the semantics of every patch ($p_{ijk}$) correctly. Formally,
after optimization, our goal is that for every patch $j$ in image $v_{i}$,
$p_{ijk}-\hat{p}_{ijk}<\epsilon$, where $\epsilon$ is as small as possible.
Directly optimizing the mean patch probability only minimizes the difference
between $p^{o_{m}}_{ik}$ ($\frac{1}{N}\sum_{j=1}^{N}{p_{ijk}}$) and
$\hat{p}^{o_{m}}_{ik}$ ($\frac{1}{N}\sum_{j=1}^{N}{\hat{p}_{ijk}}$), but for
each patch $j$, $p_{ijk}$ and $\hat{p}_{ijk}$ can still be different. Besides,
as the model only learns to predict the mean patch probability, it cannot
actually predict the token for each patch and generate the real images. To
mitigate this problem, we propose sample patch probability. We sample one
patch from $N$ patches in an image, and use the semantics in the sampled patch
to represent the image:

$p^{o_{s}}_{ik}=p_{ijk}$ (3)

where $j$ is the sampled patch. We predict $p^{o_{s}}_{ik}$ based on encoded
image inputs and sampled patch $j$’s position. We encode the position of the
patch with a learned position embedding, and add it to the encoded inputs.

#### Weighted Patch Probability.

Sample patch probability aims to minimize the differences between $p_{ijk}$
and $\hat{p}_{ijk}$ for every patch $j$ in the image. However, minimizing the
difference between $p_{ij_{1}k}$ and $\hat{p}_{ij_{1}k}$ for patch $j_{1}$
might push $p_{ij_{2}k}$ and $\hat{p}_{ij_{2}k}$ away for patch $j_{2}$, which
makes the convergence harder. Thus, we further propose weighted patch
probability. Formally, we represent image semantics generation probability
$p^{o_{w}}_{ik}$ as:

$p^{o_{w}}_{ik}=\sum_{j=1}^{N}{w_{j}p_{ijk}}$ (4)

where $w_{j}$ is a randomly sampled weight for patch $j$, and
$\sum_{j=1}^{N}{w_{j}}=1$. Since we randomly sample $\\{w_{j}\\}_{j=1}^{N}$
during training, after optimization, $\forall\\{w_{j}\\}_{j=1}^{N}$,
$p^{o_{w}}_{ik}-\hat{p}^{o_{w}}_{ik}<\epsilon$. This constraint guarantees
that for every patch $j$ in the image $v_{i}$,
$p_{ijk}-\hat{p}_{ijk}<\epsilon$ after optimization. Detailed proof can be
found in Appendix. Furthermore, we propose block-wise weighted patch
probability, where at each optimization step, we randomly sample a block which
contains $B$ patches, and the weights for the patches in the block are higher
than other patches. The block-wise weights help the model learn to predict the
richer semantics in the block compared with single token. We predict the
weighted patch probability based on encoded image inputs and sampled weights,
where we encode the sampled weights $\\{w_{j}\\}_{j=1}^{N}$ with fully-
connected layers.

###  3.4 Visual Token Codebook Selection

Since the discrete variational autoencoder (dVAE) [37] is trained on image-
text pairs from the web, not all the 8192 classes are of equal importance for
the environment in VLN. Besides, it’s hard to adapt 8192 classes to the VLN
domain at the same time. Thus, we propose two ways to learn a subset of the
vocabulary at each iteration during optimization.

#### Static Codebook Selection.

We first propose a simple static codebook selection method, where we select a
fixed set of $|S|$ visual tokens from the vocabulary $T$. Specifically, we
calculate the visual token frequency in the training environment, and pick the
$|S|$ visual tokens that have the highest frequency. During training, we only
predict the generation probability of these static $|S|$ visual tokens. This
static codebook selection filters out tokens that are rarely appeared in the
dataset. Thus the agent could focus more on the frequent tokens.

#### Dynamic Codebook Selection.

We propose a novel dynamic codebook selection method, where we dynamically
select a set of $S$ visual tokens from the vocabulary $T$. Specifically, the
$S$ tokens are initialized to be the tokens that have the highest frequency in
the environments. During training, we update the frequency score $s_{f}$ based
on visual tokens that appear in the current training batch. Besides, we add a
difficulty score $s_{d}$ based on the difference of the agents’ predicted
probability $\hat{p}^{o}_{ik}$ and the ground truth probability $p^{o}_{ik}$
($p^{o}_{ik}\in\\{p^{o_{m}}_{ik},p^{o_{s}}_{ik},p^{o_{w}}_{ik}\\}$). We pick
the $S$ tokens that have the highest score $s_{t}$ at training step $t$:

$\displaystyle s_{d}$ $\displaystyle=|\hat{p}^{o}_{ik}-p^{o}_{ik}|$ (5)
$\displaystyle s_{t}$ $\displaystyle=\lambda s_{t-1}+(1-\lambda)(s_{f}+\gamma
s_{d})$ (6)

The score $s_{t}$ takes both token frequency and learning difficulty into
consideration. The agent learns to focus on more frequent visual tokens and
also puts more effort into learning the more difficult tokens.

###  3.5 Pre-training Tasks

We propose three proxy tasks for the agent to learn to generate image
semantics calculated with the codebook selection (Sec. 3.4) and patch semantic
calculation (Sec. 3.3). We directly adopt the history-aware transformer model
HAMT [8] as our base agent, and pre-train it from scratch with the 6 tasks
proposed by [8] and our proposed 3 tasks.

Model | R2R | CVDN
---|---|---
| Val Unseen | Test | Val Unseen | Test
| SR$\uparrow$ | SPL$\uparrow$ | SR$\uparrow$ | SPL$\uparrow$ | GP$\uparrow$ | GP$\uparrow$
PREVALENT [17] | 58 | 53 | 54 | 51 | 3.15 | 2.44
$\circlearrowright$BERT [19] | 63 | 57 | 63 | 57 | - | -
HOP [35] | 64 | 57 | 64 | 59 | 4.41 | 3.31
HAMT [8] | 66 | 61 | 65 | 60 | 5.13 | 5.58
Ours | 68 | 62 | 65 | 60 | 5.52 | 5.83
SSM [43]♠ | 62 | 45 | 61 | 46 | - | -
DUET [10]♠ | 72 | 60 | 69 | 59 | - | -
Ours♠ | 72 | 62 | 72 | 60 | - | -

Table 1: Comparison with state-of-the-art agents on Room-to-Room (R2R) and
Cooperative Vision-and-Dialog Navigation (CVDN) validation unseen set and test
leaderboard. ${\spadesuit}$ denotes agent that utilizes graph information
during navigation.

#### Masked Trajectory Modeling (MTM).

In Masked Trajectory Modeling (MTM) (Top Left in Fig. 2), we randomly mask out
$r\%$ of the steps in the full navigation trajectory, and aim to recover those
views based on language instructions and other views in the trajectory.
Specifically, given language instruction $\\{w_{1},...,w_{L}\\}$ and
navigation trajectory $\\{v_{1},...,v_{M}\\}$, we randomly replace some steps
$v_{i}$ with a $\langle MASK\rangle$ token. We predict
$\hat{p}^{o}_{ik_{MTM}}$
($\hat{p}^{o}_{ik_{MTM}}\in\\{\hat{p}^{o_{m}}_{ik_{MTM}},\hat{p}^{o_{s}}_{ik_{MTM}},\hat{p}^{o_{w}}_{ik_{MTM}}\\}$)
with a multi-layer fully-connected network:
$\hat{p}^{o}_{ik_{MTM}}=f_{MTM}(h_{i}+E_{p})$, where $h_{i}$ is the model
output of the masked step $v_{i}$. $E_{p}$ is zeros when we use mean patch
probability, $E_{p}$ is the position encoding of the sampled patch when using
sample patch probability, and $E_{p}$ is encoded sampled weights when using
weighted patch probability. We optimize the KL-divergence loss between the two
distributions:

$L_{MTM}=-\sum_{k\in S}{p^{o}_{ik}log\hat{p}^{o}_{ik_{MTM}}}$ (7)

#### Masked Panorama Modeling (MPM).

At each time step, the agent observes a panorama of the current location. The
panorama is discretized into 36 views. In Masked Panorama Modeling (Top Right
in Fig. 2), we randomly mask out $u$% of the views in the panorama, and aim to
predict the masked views based on language instructions, navigation history
and surrounding views in the panorama. Specifically, given language
instruction $\\{w_{1},...,w_{L}\\}$, navigation history
$\\{v_{1},...,v_{M}\\}$, and current panorama view
$\\{v_{{M+1}_{i}}\\}_{i=1}^{36}$, we randomly replace some views
$v_{{M+1}_{i}}$ with a $<$MASK$>$ token. We predict $\hat{p}^{o}_{ik_{MPM}}$
with a multi-layer fully-connected network:
$\hat{p}^{o}_{ik_{MPM}}=f_{MPM}(o_{i}+E_{p})$, where $o_{i}$ is the output of
the masked discretized view. We optimize the KL-divergence loss between two
distributions:

$L_{MPM}=-\sum_{k\in S}{p^{o}_{ik}log\hat{p}^{o}_{ik_{MPM}}}$ (8)

#### Action Prediction with Image Generation (APIG).

Previous work picks the next action of the agent by directly selecting from a
set of candidates. In this task, the agent mimics the action prediction
process by generating the future scenes and picking the candidates that are
closest to the generated images. In Action Prediction with Image Generation,
we aim to generate semantics of the views at the next step, based on language
instruction $\\{w_{1},...,w_{L}\\}$ and navigation history
$\\{v_{1},...,v_{M}\\}$. We predict $\hat{p}^{o}_{ik_{APIG}}$ with a multi-
layer fully connected network:
$\hat{p}^{o}_{ik_{APIG}}=f_{APIG}(w_{0}+E_{p})$, where $w_{0}$ is the output
of the $<$CLS$>$ token in the instructions. The $<$CLS$>$ token contains state
information of the agent after cross-modality attention layers between the
instructions and the navigation history. We optimize the KL-divergence loss
between two distributions:

$L_{APIG}=-\sum_{k\in S}{p^{o}_{ik}log\hat{p}^{o}_{ik_{APIG}}}$ (9)

###  3.6 Fine-tuning on Navigation Task

We fine-tune the agent on the navigation task with a mixture of imitation
learning (IL) and reinforcement learning (RL) as in [8]. To fully utilize
agents’ ability to generate semantics in future scenes, we further train the
agent with APIG as an auxiliary task. We initialize the model weights for this
task with $f_{APIG}$ learned in pre-training. Since it’s computationally
inefficient to compute the ground truth generation probability for an image
during VLN fine-tuning, we pre-extract the mean patch probability
$p^{o_{m}}_{ik}$ of an image $v_{i}$ and the target visual token
($m_{ij}=argmax_{k}(p_{ijk})$) for every patch $j$ in an image $v_{i}$. For
$p_{ik}^{o_{m}}$, we optimize the KL-divergence loss between two
distributions: $L_{AT}=-\sum_{k\in S}{p_{ik}^{o_{m}}log\hat{p}^{o_{m}}_{ik}}$.
For $p_{ik}^{o_{s}}$, since we don’t pre-extract the visual token probability
$p_{ijk}$, we optimize the cross-entropy loss between predicted generation
probability $\hat{p}^{o_{s}}_{ik}$ and the sampled visual token class $m_{ij}$
instead: $L_{AT}=-m_{ij}log\hat{p}^{o_{s}}_{im_{ij}}$. For $p_{ik}^{w}$, we
fix the weights $w_{j}$ to be $1/N$ to generate mean patch probability
instead, and optimize the KL-divergence loss as: $L_{AT}=-\sum_{k\in
S}{p_{ik}^{o_{w}}log\hat{p}^{o_{w}}_{ik}}$.

No. | Pre-Training Tasks | Validation Unseen
---|---|---
| MTM | MPM | APIG | NE$\downarrow$ | SR$\uparrow$ | SPL$\uparrow$ | nDTW$\uparrow$ | sDTW$\uparrow$ | CLS$\uparrow$
1 | ✗ | ✗ | ✗ | - | 64.4 | 58.8 | - | - | -
2 | ✓ | ✗ | ✗ | 3.52 | 66.7 | 61.3 | 68.7 | 57.3 | 67.3
3 | ✗ | ✓ | ✗ | 3.68 | 65.5 | 59.4 | 68.2 | 56.5 | 66.8
4 | ✗ | ✗ | ✓ | 3.58 | 66.3 | 60.9 | 68.6 | 57.2 | 67.0
5 | ✓ | ✓ | ✓ | 3.37 | 68.1 | 62.3 | 69.6 | 58.7 | 67.7

Table 2: Ablation results for our proposed three proxy tasks on Room-to-Room
validation unseen set.

No. | PT Tasks | Codebook Selection | Validation Unseen
---|---|---|---
|  | Static | Dynamic | NE$\downarrow$ | SR$\uparrow$ | SPL$\uparrow$ | nDTW$\uparrow$ | sDTW$\uparrow$ | CLS$\uparrow$
1 | Baseline |  |  | - | 64.4 | 58.8 | - | - | -
2 | MTM | ✗ | ✗ | 3.66 | 65.1 | 59.8 | 68.5 | 56.7 | 66.5
3 | MTM | ✓ | ✗ | 3.65 | 66.2 | 60.3 | 67.5 | 56.7 | 66.3
4 | MTM | ✗ | ✓ | 3.52 | 66.7 | 61.3 | 68.7 | 57.3 | 67.3
5 | MPM | ✗ | ✗ | 3.89 | 64.8 | 59.0 | 68.0 | 55.4 | 65.3
6 | MPM | ✓ | ✗ | 3.68 | 65.5 | 59.4 | 68.2 | 56.5 | 66.8
7 | MPM | ✗ | ✓ | 3.64 | 65.1 | 59.8 | 68.0 | 56.3 | 66.2
8 | APIG | ✗ | ✗ | 3.87 | 64.4 | 59.2 | 67.1 | 55.4 | 65.6
9 | APIG | ✓ | ✗ | 3.76 | 65.9 | 60.3 | 67.4 | 56.1 | 65.6
10 | APIG | ✗ | ✓ | 3.58 | 66.3 | 60.9 | 68.6 | 57.2 | 67.0

Table 3: Comparison of training without codebook selection, training with
static codebook selection method and dynamic codebook selection method on
Room-to-Room validation unseen set.

##  4 Experimental Setup

###  4.1 Dataset

We evaluate our agent on the Room-to-Room (R2R) dataset [2] and Cooperative
Vision-and-Dialog Navigation (CVDN) dataset [42]. Both datasets are split into
training, seen validation, unseen validation and test set. The environments in
unseen validation and test set are not appeared in the training set. We focus
on agents’ performance on the unseen validation set and the test set, since
they measure agents’ ability to generalize to unseen environments.

###  4.2 Evaluation Metrics

We evaluate our model on the following metrics: (1) Success Rate (SR), whether
the agent stops within 3 meters to the target. (2) Success Rate Weighted by
Path Length (SPL) [1], which penalizes long paths that randomly explore the
environment. (3) normalized Dynamic Time Warping (nDTW) [20], measures how
well the agent follows the ground truth path. (4) success rate weighted by
normalized Dynamic Time Warping (sDTW), which considers nDTW score for success
cases. (5) Coverage weighted by Length Score (CLS) [21], measures how well the
agent follows the reference path. (6) Navigation Error (NE), the distance
between the stop location and the target. (7) Trajectory Length (TL), the
total navigation length of the agent. We consider success rate as the main
evaluation metric.

###  4.3 Implementation Details

We adopt the model architecture from [8]. For the image tokenizer, the input
image size is 224, and the patch size is 16. We set 1.0 for $\gamma$ and 0.5
for $\lambda$ in dynamic codebook selection, and $|S|$ to be 1000 for both
codebook selection methods. In pre-training, the ratio to select tasks is set
to be 3 for MTM and 1 for others. The mask ratio $r$ is 0.5 for MTM and $u$ is
0.3 for MPM. In fine-tuning, $L_{AT}$ is added to the IL loss with ratio 1.
The ratio to combine IL and RL is 0.15 when adding $L_{AT}$ and 0.2 otherwise.
We use weighted patch probability with block-wise sampling for Room-to-Room
dataset and base weighted patch probability for CVDN dataset. CLIP-ViT/16 [36]
is used to extract the features for HAMT and ViT [13] pretrained on ImageNet
is used for DUET (CLIP-ViT/16 results for DUET are in Appendix). Other
hyperparameters are the same as in [8] for fair comparison.

##  5 Results and Analysis

###  5.1 Test Set Results

We show our method’s performance on both the Room-to-Room (R2R) and the
Cooperative Vision-and-Dialog Navigation (CVDN) dataset. As shown in Table 1,
our agent outperforms previous SotA agent HAMT [8] which utilizes
computational expensive end-to-end visual backbone tunning by 0.25 in GP on
CVDN test leaderboard, and shows competitive performance on R2R test
leaderboard. This demonstrates that our agent benefits from imagining the
future view semantics during navigation. Furthermore, we demonstrate that our
proposed methods generalize well to graph-based VLN agent DUET [10], where the
agent encodes the current location with neighboring nodes representation and
makes action conditioned on both coarse-scale topological map encoding and
fine-scale current step encoding. Specifically, we pre-train the agent with
Masked Pano Modeling (MPM) and Action Prediction with Image Generation (APIG).
Our method outperforms DUET [10] by 3% in success rate and 1% in SPL,
achieving the new state-of-the-art on Room-to-Room test leaderboard.

No. | PT Tasks | Semantic Calculation | Validation Unseen
---|---|---|---
|  | Mean | Sample | Weighted | Weighted-Block | NE$\downarrow$ | SR$\uparrow$ | SPL$\uparrow$ | nDTW$\uparrow$ | sDTW$\uparrow$ | CLS$\uparrow$
1 | Baseline |  |  |  |  | - | 64.4 | 58.8 | - | - | -
2 | ALL | ✓ | ✗ | ✗ | ✗ | 3.66 | 65.5 | 60.3 | 68.8 | 56.4 | 67.4
3 | ALL | ✗ | ✓ | ✗ | ✗ | 3.67 | 65.9 | 60.2 | 68.0 | 56.6 | 66.5
4 | ALL | ✗ | ✗ | ✓ | ✗ | 3.43 | 66.9 | 61.8 | 69.7 | 58.2 | 68.4
5 | ALL | ✗ | ✗ | ✗ | ✓ | 3.37 | 68.1 | 62.3 | 69.6 | 58.7 | 67.7

Table 4: Comparison of different ways to calculate image semantics on Room-to-
Room validation unseen set. “Weighted” indicates using weighted patch
probability without block-wise sampled weights, and “Weighted-Block” samples
block-wise weights when calculating weighted patch probability.

No. | PT Tasks | Codebook Selection | FT Tasks | Validation Unseen
---|---|---|---|---
|  | Static | Dynamic | APIG | NE$\downarrow$ | SR$\uparrow$ | SPL$\uparrow$ | nDTW$\uparrow$ | sDTW$\uparrow$ | CLS$\uparrow$
1 | Baseline |  |  |  | - | 64.4 | 58.8 | - | - | -
2 | APIG | ✓ | ✗ | ✗ | 3.64 | 64.9 | 60.4 | 67.9 | 56.2 | 66.7
3 | APIG | ✓ | ✗ | ✓ | 3.76 | 65.9 | 60.3 | 67.4 | 56.1 | 65.6
4 | APIG | ✗ | ✓ | ✗ | 3.53 | 66.1 | 60.7 | 68.1 | 56.9 | 66.5
5 | APIG | ✗ | ✓ | ✓ | 3.58 | 66.3 | 60.9 | 68.6 | 57.2 | 67.0

Table 5: Ablation results for adding Action Prediction with Image Generation
(APIG) as auxiliary task during fine-tuning on Room-to-Room validation unseen
set.

###  5.2 Effectiveness of Pre-training Tasks

In this section, we demonstrate the effectiveness of our proposed three tasks
for VLN in-domain pre-training. We show the ablation performance of using one
of the tasks in pre-training in Table 2. Specifically, the baseline model is
HAMT pre-trained on 6 proxy tasks: MLM, MRM, ITM, SAP/SAR, and SPREL without
end-to-end vision-backbone tunning (details in [8]). The performance shown in
this table is the best model picked among the different combinations of
codebook selection methods and patch probability calculation methods. As shown
in Table 2, adding any of our proposed tasks improves the performance by a
large margin in both success rate (SR) and success rate weighted by path
length (SPL). Specifically, adding Masked Trajectory Modeling (MTM) brings the
largest improvement, outperforms the baseline by 2.3% in SR and 2.5% in SPL.
Furthermore, pre-training on all the tasks achieves the best performance,
improving the baseline by 3.7% in SR and 3.5% in SPL, demonstrating our
approach’s effectiveness.

###  5.3 Effectiveness of Codebook Selection

We demonstrate that it’s important to select a subset of visual tokens either
statically or dynamically for the agent to effectively learn the large visual
token vocabulary extracted with pre-trained dVAE. We show the ablation
performance in Table 3. First, we observe that the agent cannot learn useful
image semantics when training on MTM or APIG without codebook selection (Model
1 vs. 2,8), but using dynamic codebook selection could significantly improve
the performance, outperforming the model without codebook selection by 1.6% in
SR for MTM (Model 2 vs. 4) and 1.9% in SR for APIG (Model 8 vs. 10). For MPM,
using static codebook selection slightly outperforms the model that directly
learns from all visual tokens in the vocabulary. We attribute this to that
reasoning the masked view in a panorama is easier than generating the
semantics in a masked step or next view. The agent could easily infer
semantics from the overlaps between continuous views, and thus codebook
selection benefits less for MPM.

###  5.4 Comparison of Image Semantic Representation Methods

We compare the three ways of representing the overall image semantics in Table
4. First, we observe that the agent benefits from pre-training with our
proposed three tasks, regardless of how we calculate the image semantics
(Model 1 vs. 2,3,4,5). Then, we observe that using sample patch probability,
weighted patch probability without block-wise sampling, and weighted patch
probability with block-wise sampling outperforms the mean patch probability
(Model 2 vs. 3,4,5) by more than 0.5%, 1.4%, and 2.6% in SR respectively. This
demonstrates that our proposed sample patch probability and weighted patch
probability (with and without block-wise sampling) help the agent learn from
semantics in each patch better, while saving the memory by $O(N)$ compared
with traditional Masked Image Modeling method [3] which generates the
probability for all masked patches in an image. Lastly, we demonstrate that
adding block-wise sampling for the weights during training (Model 4 vs. 5)
further improves the performance by 1.2% in success rate, demonstrating the
importance of learning semantics in a block instead of sparsely at each
optimization step.

###  5.5 Effectiveness of Auxiliary Task during Fine-tuning

We demonstrate the effectiveness of utilizing future semantics generation as
auxiliary task during fine-tuning in this section. We use mean patch
probability to represent the image semantics in these experiments. As shown in
Table 5, adding APIG as auxiliary task during fine-tuning improves the
performance by 1.0% in SR when using static codebook selection, and 0.2% in SR
when using dynamic codebook selection. This shows that the agent can benefit
from generating semantics in future views during navigation.

Figure 3: Qualitative analysis of images generated with our agent. Given 90%/
80%/ 70% ground truth tokens, the rest tokens predicted by our model contain
closer semantic information compared with randomly filled tokens.

###  5.6 Ability to Generate Future Views

We demonstrate that our model could reasonably generate future semantics and
reconstruct future images. We generate the token for each patch in the image
with our APIG head learned with weighted patch probability. We set the weight
vector to be an indicator vector, where the weight for the target patch is 1
and the others are 0. We use $x$% ($x\in{70,80,90}$) of the patches with
ground truth tokens encoded with pre-trained dVAE, the rest patches with the
tokens generated by our APIG head, and then use the dVAE decoder to decode the
image. As shown in Figure 3, our generated image could almost reconstruct the
beds and pictures in the original image with small vague areas when given 70%
of the ground truth tokens. In comparison, filling the 30% patches with random
tokens will generate distorted images with large white parts, and the beds and
pictures information cannot be identified. We also notice that our model still
fails to generate the full image when all the tokens in the image are
predicted by our APIG head, and needs at least 70% of the ground truth tokens
to generate images of reasonable quality. More examples in appendix.

Path Length | 3 | 4 | 5 | 6
---|---|---|---|---
HAMT [8] | 66.7 | 65.8 | 67.5 | 62.3
Ours | 66.7 | 67.7 | 70.3 | 66.5

Table 6: Success rate of our method and the baseline method for navigation
trajectories with different lengths on Room-to-Room validation unseen set. Our
method achieves larger improvement for longer paths.

###  5.7 Better Performance for Longer Trajectories

We show that our model is better at navigating longer paths on validation
unseen set. Room-to-Room validation unseen set contains path lengths ranging
from 3 to 6. As shown in Table 6, our model improves the baseline by 4.2% in
success rate for paths with length 6, 2.8% for paths with length 5, and 1.9%
for paths with length 4, demonstrating that learning to predict future view
semantics can help the agent to learn to navigate longer paths better.

##  6 Conclusion

In this paper, we propose VLN-SIG, which explores whether navigation agents
can benefit from imagining semantics in future views. We first propose novel
codebook selection and image semantic calculation methods to efficiently learn
the image semantics. We then design Masked Trajectory Modeling and Masked
Panorama Modeling to help the agent to understand semantics in each visual
token and learn to recognize the semantics contained in each view. We further
use Action Prediction with Image Generation to enhance agents’ ability to
predict future views in both pre-training and fine-tuning. Our VLN-SIG
achieves the new SotA on both CVDN dataset and R2R dataset.

## Acknowledgements

We thank the reviewers for their helpful comments. This work was supported by
ARO Award W911NF2110220 and DARPA MCS N66001-19-2-403. The views contained in
this article are of the authors and not of the funding agency.

## References

  * [1] Peter Anderson, Angel Chang, Devendra Singh Chaplot, Alexey Dosovitskiy, Saurabh Gupta, Vladlen Koltun, Jana Kosecka, Jitendra Malik, Roozbeh Mottaghi, Manolis Savva, et al.  On evaluation of embodied navigation agents.  arXiv preprint arXiv:1807.06757, 2018.
  * [2] Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian Reid, Stephen Gould, and Anton Van Den Hengel.  Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3674–3683, 2018.
  * [3] Hangbo Bao, Li Dong, and Furu Wei.  Beit: Bert pre-training of image transformers.  ICLR, 2022.
  * [4] Hangbo Bao, Wenhui Wang, Li Dong, and Furu Wei.  Vl-beit: Generative vision-language pretraining.  arXiv preprint arXiv:2206.01127, 2022.
  * [5] Howard Chen, Alane Suhr, Dipendra Misra, Noah Snavely, and Yoav Artzi.  Touchdown: Natural language navigation and spatial reasoning in visual street environments.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12538–12547, 2019.
  * [6] Kevin Chen, Junshen K Chen, Jo Chuang, Marynel Vázquez, and Silvio Savarese.  Topological planning with transformers for vision-and-language navigation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11276–11286, 2021.
  * [7] Peihao Chen, Dongyu Ji, Kunyang Lin, Runhao Zeng, Thomas H Li, Mingkui Tan, and Chuang Gan.  Weakly-supervised multi-granularity map learning for vision-and-language navigation.  arXiv preprint arXiv:2210.07506, 2022.
  * [8] Shizhe Chen, Pierre-Louis Guhur, Cordelia Schmid, and Ivan Laptev.  History aware multimodal transformer for vision-and-language navigation.  Advances in Neural Information Processing Systems, 34, 2021.
  * [9] Shizhe Chen, Pierre-Louis Guhur, Makarand Tapaswi, Cordelia Schmid, and Ivan Laptev.  Learning from unlabeled 3d environments for vision-and-language navigation.  In Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXXIX, pages 638–655. Springer, 2022.
  * [10] Shizhe Chen, Pierre-Louis Guhur, Makarand Tapaswi, Cordelia Schmid, and Ivan Laptev.  Think global, act local: Dual-scale graph transformer for vision-and-language navigation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16537–16547, 2022.
  * [11] Zhiwei Deng, Karthik Narasimhan, and Olga Russakovsky.  Evolving graphical planner: Contextual global planning for vision-and-language navigation.  Advances in Neural Information Processing Systems, 33:20660–20672, 2020.
  * [12] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  NAACL, 2019.
  * [13] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [14] Yuying Ge, Yixiao Ge, Xihui Liu, Alex Jinpeng Wang, Jianping Wu, Ying Shan, Xiaohu Qie, and Ping Luo.  Miles: Visual bert pre-training with injected language semantics for video-text retrieval.  arXiv preprint arXiv:2204.12408, 2022.
  * [15] Georgios Georgakis, Karl Schmeckpeper, Karan Wanchoo, Soham Dan, Eleni Miltsakaki, Dan Roth, and Kostas Daniilidis.  Cross-modal map learning for vision and language navigation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15460–15470, 2022.
  * [16] Pierre-Louis Guhur, Makarand Tapaswi, Shizhe Chen, Ivan Laptev, and Cordelia Schmid.  Airbert: In-domain pretraining for vision-and-language navigation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1634–1643, 2021.
  * [17] Weituo Hao, Chunyuan Li, Xiujun Li, Lawrence Carin, and Jianfeng Gao.  Towards learning a generic agent for vision-and-language navigation via pre-training.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13137–13146, 2020.
  * [18] Yicong Hong, Cristian Rodriguez, Yuankai Qi, Qi Wu, and Stephen Gould.  Language and visual entity relationship graph for agent navigation.  Advances in Neural Information Processing Systems, 33:7685–7696, 2020.
  * [19] Yicong Hong, Qi Wu, Yuankai Qi, Cristian Rodriguez-Opazo, and Stephen Gould.  A recurrent vision-and-language bert for navigation.  CVPR, 2021.
  * [20] Gabriel Ilharco, Vihan Jain, Alexander Ku, Eugene Ie, and Jason Baldridge.  General evaluation for instruction conditioned navigation using dynamic time warping.  Neural Information Processing Systems (NeurIPS), 2019.
  * [21] Vihan Jain, Gabriel Magalhaes, Alexander Ku, Ashish Vaswani, Eugene Ie, and Jason Baldridge.  Stay on the path: Instruction fidelity in vision-and-language navigation.  ACL, 2019.
  * [22] Jing Yu Koh, Honglak Lee, Yinfei Yang, Jason Baldridge, and Peter Anderson.  Pathdreamer: A world model for indoor navigation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 14738–14748, 2021.
  * [23] Alexander Ku, Peter Anderson, Roma Patel, Eugene Ie, and Jason Baldridge.  Room-Across-Room: Multilingual vision-and-language navigation with dense spatiotemporal grounding.  In Conference on Empirical Methods for Natural Language Processing (EMNLP), 2020.
  * [24] Federico Landi, Lorenzo Baraldi, Marcella Cornia, Massimiliano Corsini, and Rita Cucchiara.  Multimodal attention networks for low-level vision-and-language navigation.  Computer Vision and Image Understanding, 210:103255, 2021.
  * [25] Jialu Li, Hao Tan, and Mohit Bansal.  Improving cross-modal alignment in vision language navigation via syntactic information.  NAACL, 2021.
  * [26] Jialu Li, Hao Tan, and Mohit Bansal.  Envedit: Environment editing for vision-and-language navigation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15407–15417, 2022.
  * [27] Bingqian Lin, Yi Zhu, Zicong Chen, Xiwen Liang, Jianzhuang Liu, and Xiaodan Liang.  Adapt: Vision-language navigation with modality-aligned action prompts.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15396–15406, 2022.
  * [28] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  arXiv preprint arXiv:1907.11692, 2019.
  * [29] Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee.  Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks.  Advances in neural information processing systems, 32, 2019.
  * [30] Matt MacMahon, Brian Stankiewicz, and Benjamin Kuipers.  Walk the talk: Connecting language, knowledge, and action in route instructions.  Def, 2(6):4, 2006.
  * [31] Arjun Majumdar, Ayush Shrivastava, Stefan Lee, Peter Anderson, Devi Parikh, and Dhruv Batra.  Improving vision-and-language navigation with image-text pairs from the web.  In European Conference on Computer Vision, pages 259–274. Springer, 2020.
  * [32] Harsh Mehta, Yoav Artzi, Jason Baldridge, Eugene Ie, and Piotr Mirowski.  Retouchdown: Adding touchdown to streetlearn as a shareable resource for language grounding tasks in street view.  Proceedings of the Third International Workshop on Spatial Language Understanding, 2020.
  * [33] Dipendra Misra, Andrew Bennett, Valts Blukis, Eyvind Niklasson, Max Shatkhin, and Yoav Artzi.  Mapping instructions to actions in 3d environments with visual goal prediction.  EMNLP, 2018.
  * [34] Yuankai Qi, Qi Wu, Peter Anderson, Xin Wang, William Yang Wang, Chunhua Shen, and Anton van den Hengel.  Reverie: Remote embodied visual referring expression in real indoor environments.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9982–9991, 2020.
  * [35] Yanyuan Qiao, Yuankai Qi, Yicong Hong, Zheng Yu, Peng Wang, and Qi Wu.  Hop: History-and-order aware pre-training for vision-and-language navigation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15418–15427, 2022.
  * [36] 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, pages 8748–8763. PMLR, 2021.
  * [37] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever.  Zero-shot text-to-image generation.  In International Conference on Machine Learning, pages 8821–8831. PMLR, 2021.
  * [38] Sonia Raychaudhuri, Saim Wani, Shivansh Patel, Unnat Jain, and Angel X Chang.  Language-aligned waypoint (law) supervision for vision-and-language navigation in continuous environments.  EMNLP, 2021.
  * [39] Mohit Shridhar, Jesse Thomason, Daniel Gordon, Yonatan Bisk, Winson Han, Roozbeh Mottaghi, Luke Zettlemoyer, and Dieter Fox.  Alfred: A benchmark for interpreting grounded instructions for everyday tasks.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10740–10749, 2020.
  * [40] Hao Tan and Mohit Bansal.  Lxmert: Learning cross-modality encoder representations from transformers.  EMNLP, 2019.
  * [41] Hao Tan, Licheng Yu, and Mohit Bansal.  Learning to navigate unseen environments: Back translation with environmental dropout.  NAACL, 2019.
  * [42] Jesse Thomason, Michael Murray, Maya Cakmak, and Luke Zettlemoyer.  Vision-and-dialog navigation.  In Conference on Robot Learning, pages 394–406. PMLR, 2020.
  * [43] Hanqing Wang, Wenguan Wang, Wei Liang, Caiming Xiong, and Jianbing Shen.  Structured scene memory for vision-language navigation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8455–8464, 2021.
  * [44] Xin Wang, Qiuyuan Huang, Asli Celikyilmaz, Jianfeng Gao, Dinghan Shen, Yuan-Fang Wang, William Yang Wang, and Lei Zhang.  Reinforced cross-modal matching and self-supervised imitation learning for vision-language navigation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6629–6638, 2019.
  * [45] Xin Eric Wang, Vihan Jain, Eugene Ie, William Yang Wang, Zornitsa Kozareva, and Sujith Ravi.  Environment-agnostic multitask learning for natural language grounded navigation.  In European Conference on Computer Vision, pages 413–430. Springer, 2020.
  * [46] Yue Zhang and Parisa Kordjamshidi.  Explicit object relation alignment for vision and language navigation.  In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics: Student Research Workshop, pages 322–331, 2022.
  * [47] Fengda Zhu, Xiwen Liang, Yi Zhu, Qizhi Yu, Xiaojun Chang, and Xiaodan Liang.  Soon: Scenario oriented object navigation with graph-based exploration.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12689–12699, 2021.

##  Appendix A Appendix Overview

In this appendix, we provide the following:

  * •

Detailed description of the architecture of the baseline method we use in Sec.
B.

  * •

Detailed description of the pre-training tasks used in the baseline method in
Sec. C, and more implementation details in Sec. D.

  * •

Performance of our method on R4R and RxR validation unseen set in Sec. E, and
performance of our method on graph based navigation agents on R2R validation
set in Sec. F.

  * •

Proof that demonstrates weighted patch probability could learn a better
optimal value than mean patch probability in Sec. G.

  * •

More examples of the future views generated by our APIG head in Sec. H, and
quantitative analysis of the semantics underlying our generated tokens in Sec.
I.

##  Appendix B HAMT Model Architecture

HAMT [8] utilizes a transformer-based architecture to encode the instructions,
navigation history, and current step observation. Specifically, the
instructions are encoded with a BERT architecture.

As the navigation history is a sequence of panorama observations, HAMT encodes
the navigation history with a hierarchical architecture. It first uses a
panorama encoder to encode panorama into view representation, and uses
multiple transformer layers as the temporal encoder to encode the observations
on the trajectory. Formally, given the encoded history observation $v_{i}$,
which is the output of the panorama encoder, the output of the temporal
encoder is $h_{i}=LN(W_{t}v_{i})+LN(W_{a}a_{i})+E_{i}^{S}+E_{2}^{T}$, where
$a_{i}$ is the action embedding at step $i$, $E_{i}^{S}$ is the step encoding,
and $E_{2}^{T}$ is the token type encoding which indicates the input is
history views.

The current step observation is represented as 36 discretized views. Each view
is passed through the transformer encoder to learn the view representation:
$o_{i}=LN(W_{o}v_{i}^{o})+LN(W_{a}^{o}a_{i}^{o})+E_{i}^{O}+E_{1}^{T}$, where
$v_{i}^{o}$ is the encoding of view $i$, $a_{i}^{o}$ is the action embedding
for view $i$, $E_{i}^{O}$ is the embedding indicating whether the current view
is navigable, and $E_{1}^{T}$ is the token type encoding which indicates the
input is current step observation.

The agent predicts the next step by comparing the similarity between the
observation encoding $o_{i}$ and the $<$CLS$>$ token which contains
instruction-trajectory information.

More implementation details can be found in [8].

##  Appendix C Pre-training Tasks in HAMT

In this section, we describe the six pre-training tasks we adopted from [8].
Specifically, the six tasks are Masked Language Modeling (MLM), Masked Region
Modeling (MRM), Instruction Trajectory Matching (ITM), Single-step Action
Prediction/Regression (SAP/SAR), and Spatial Relationship Prediction (SPREL).

In Masked Language Modeling, we randomly masked out 15% of the words in the
instructions, and predict the masked words given surrounding words and the
full trajectory, which improves agents’ language understanding. We optimize
the negative log-likelihood of the original words:
$L_{MLM}=-logp(w_{i}|I_{lang\setminus{i}},I_{visual})$, where
$I_{lang\setminus{i}}$ is the language input without masked words $w_{i}$ and
$I_{visual}$ is the visual input.

In Masked Region Modeling, the agent learns to predict the objects in the
masked views in the trajectory. The target is the object detection probability
$p_{i}$ predicted by an image classification model pre-trained on ImageNet. We
optimize a KL-divergence between the target probability and predicted
probability: $L_{MRM}=-p_{i}log\hat{p}_{i}$, where $\hat{p}_{i}$ is the
predicted probability.

In Instruction Trajectory Matching, the agent learns the alignment between the
language instructions and the environment by picking the correct instruction-
trajectory pairs from one positive pair and four negative pairs. The four
negative pairs are created by randomly sampling two trajectories from the same
batch, and shuffling the order of views in the correct trajectory. The agent
optimizes a noisy contrastive loss:
$L_{ITM}=-log\frac{exp(f_{ITM}(h_{lang}*h_{visual}))}{exp(f_{ITM}(h_{lang}*h_{visual}))+\sum^{4}{exp(f_{ITM}(h_{lang}*h_{visual}^{neg}))}}$,
where $h_{lang}$ and $h_{visual}$ are the outputs of the $<$CLS$>$ token of
the instructions and the trajectories separately.

In Single-step Action Prediction and Single-step Action Regression, the agent
needs to select the next step from a set of candidates. Specifically, the
agent optimizes a negative log probability of the target view action in
Single-step Action Prediction, and predicts the heading and elevation of the
target view action by optimizing the L2 loss.

In Spatial Relationship Prediction, the agent learns to predict the relative
spatial position of two views in a panorama. Specifically, it optimizes a L2
loss between the predicted heading and elevation difference and ground truth
heading and elevation difference between two views.

More implementation details can be found in [8].

Figure 4: Qualitative analysis of images generated with our agent. Given 90%/
80%/ 70% ground truth tokens, the rest tokens predicted by our model contain
closer semantic information compared with randomly filled tokens.

##  Appendix D Implementation Details

We adopt the model architecture from [8]. For the image tokenizer, the input
image size is 224, and the patch size is 16. We set 1.0 for $\gamma$ and 0.5
for $\lambda$ in dynamic codebook selection, and $|S|$ to be 1000 for both
codebook selection methods. In pre-training, the ratio to select tasks is set
to be 3 for MTM and 1 for others. The mask ratio $r$ is 0.5 for MTM and $u$ is
0.3 for MPM. In fine-tuning, $L_{AT}$ is added to the IL loss with ratio 1.
The ratio to combine IL and RL is 0.15 when adding $L_{AT}$ and 0.2 otherwise.
We use weighted patch probability with block-wise sampling for Room-to-Room
dataset and base weighted patch probability for CVDN dataset. Other
hyperparameters are the same as in [8] for fair comparison. For training time,
our model takes 30 hours to converge on 2 NIVIDIA A6000 GPU, while HAMT full
model takes 20 hours training on 20 NVIDIA V100 GPUs in addition to initial
pre-training for 1 day on 4 NVIDIA Tesla. For model parameters updated during
pre-training, our model updates 191M parameters while HAMT full model updates
260M, saving 27% parameters.

Model | R4R | RxR
---|---|---
| Val Unseen | Val Unseen
| SR$\uparrow$ | nDTW$\uparrow$ | sDTW$\uparrow$ | CLS$\uparrow$ | SR$\uparrow$ | nDTW$\uparrow$ | sDTW$\uparrow$
HAMT [8] | 44.6 | 50.3 | 31.8 | 57.7 | 56.5 | 63.1 | 48.3
Ours | 45.8 | 52.9 | 33.6 | 59.1 | 60.0 | 65.3 | 51.4

Table 7: Comparison with state-of-the-art agents on R4R and RxR validation
unseen set.

##  Appendix E Performance on R4R and RxR Dataset

In this section, we show our agents’ performance on R4R and RxR dataset. As
shown in Table 7, our model surpasses the HAMT full model by 2.6% in nDTW and
1.8% in sDTW on R4R validation unseen set. Besides, we show that our model
achieves significantly better performance on RxR unseen set, improving the
HAMT method by 2.1% in nDTW and 3.1% in sDTW.

Model | Val Seen | Val Unseen
---|---|---
| SR$\uparrow$ | SPL$\uparrow$ | nDTW$\uparrow$ | sDTW$\uparrow$ | SR$\uparrow$ | SPL$\uparrow$ | nDTW$\uparrow$ | sDTW$\uparrow$
DUET-CLIP [10] | 75.2 | 69.1 | 76.0 | 66.5 | 72.8 | 63.4 | 69.3 | 60.6
Ours | 78.6 | 74.8 | 81.8 | 73.2 | 72.2 | 63.7 | 70.2 | 61.4

Table 8: Comparison with state-of-the-art agents on R2R validation set with
CLIP-ViT/16 features.

##  Appendix F Performance with DUET on R2R Dataset with CLIP Features

We also show the performance of our proposed methods when generalized to
graph-based VLN agent DUET [10] with CLIP-ViT/16 features (instead of ViT
features as in the main paper). Specifically, we pre-train the agent with
Masked Pano Modeling (MPM) and Action Prediction with Image Generation (APIG).
As shown in Table 8, when using CLIP-ViT/16 features, our method outperforms
DUET [10] by 3.4% in success rate and 5.7% in SPL in validation seen
environment, and 0.3% in success rate and 0.9% in nDTW in validation unseen
environment, demonstrating the effectiveness of our approach.

##  Appendix G Weighted Patch Probability Proof

In weighted patch probability calculation, we represent image semantics
generation probability $p^{o_{w}}_{ik}$ as:

$p^{o_{w}}_{ik}=\sum_{j=1}^{N}{w_{j}p_{ijk}}$ (10)

where $w_{j}$ is a randomly sampled weight for patch $j$, and
$\sum_{j=1}^{N}{w_{j}}=1$.

During training, we randomly sample $\\{w_{j}\\}_{j=1}^{N}$ for each example,
and minimize the differences between $\sum_{j=1}^{N}{w_{j}p_{ijk}}$ and
predicted $\hat{p}^{o_{w}}_{ik}$. We hypothesize that the agent learns to
predict $\hat{p}^{o_{w}}_{ik}$ by predicting
$\sum_{j=1}^{N}{w_{j}\hat{p}_{ijk}}$ as we conditioned the prediction based on
sampled weights $\\{w_{j}\\}_{j=1}^{N}$.

We want to reach the optimal where:

$p^{o_{w}}_{ik}=\hat{p}^{o_{w}}_{ik}$ (11)

$\sum_{j=1}^{N}{w_{j}p_{ijk}}=\sum_{j=1}^{N}{w_{j}\hat{p}_{ijk}}$ (12)

Since we randomly sample $\\{w_{j}\\}_{j=1}^{N}$ during training, this
guarantees that for every patch $j$ in the image $v_{i}$,
$p_{ijk}=\hat{p}_{ijk}$, otherwise $\exists\\{w_{j}\\}_{j=1}^{N}$ that makes
$\sum_{j=1}^{N}{w_{j}p_{ijk}}\neq\sum_{j=1}^{N}{w_{j}\hat{p}_{ijk}}$.

##  Appendix H Future View Generation Examples

We demonstrate that our model could reasonably generate future semantics and
reconstruct future images with more examples. As shown in Figure 4, our
generated image could almost reconstruct the doors and the overall layout of
the room when given 70% of the ground truth tokens. In comparison, filling the
30% patches with random tokens will produce distorted images which are hard to
infer how does the original images look like.

##  Appendix I Analysis of Generated Semantics

In this section, we compare the generated semantics with the ground truth
semantics quantitatively to demonstrate that the semantic information
underlying them is similar. Specifically, we represent the semantics of each
visual token as the output of the first embedding layer in the dVAE decoder
(which maps each token to a 128 dimension representation space). We calculate
the distance between generated semantics and ground truth semantics, and
compare it with the distance between the ground truth semantics and all other
tokens in the vocabulary (i.e., the distance between the ground truth token
and other 8191 tokens for each patch). We normalize each semantic
representation and use l2-norm as the distance. Our method has a distance of
0.95, while the baseline is 1.31. This shows that the distance between our
generated semantics and ground truth semantics is closer.


# Experimental nonlocality-based randomness generation with non-projective
measurements

S. Gómez  Departamento de Física, Universidad de Concepción, 160-C Concepción,
Chile  Center for Optics and Photonics, Universidad de Concepción, 160-C
Concepción, Chile  MSI-Nucleus for Advanced Optics, Universidad de Concepción,
160-C Concepción, Chile  A. Mattar  ICFO-Institut de Ciencies Fotoniques, The
Barcelona Institute of Science and Technology, 08860 Castelldefels, Barcelona,
Spain  E. S. Gómez  Departamento de Física, Universidad de Concepción, 160-C
Concepción, Chile  Center for Optics and Photonics, Universidad de Concepción,
160-C Concepción, Chile  MSI-Nucleus for Advanced Optics, Universidad de
Concepción, 160-C Concepción, Chile  D. Cavalcanti  ICFO-Institut de Ciencies
Fotoniques, The Barcelona Institute of Science and Technology, 08860
Castelldefels, Barcelona, Spain  O. Jiménez Farías  ICFO-Institut de Ciencies
Fotoniques, The Barcelona Institute of Science and Technology, 08860
Castelldefels, Barcelona, Spain  A. Acín  ICFO-Institut de Ciencies
Fotoniques, The Barcelona Institute of Science and Technology, 08860
Castelldefels, Barcelona, Spain  ICREA-Institució Catalana de Recerca i
Estudis Avançats, Lluis Companys 23 Barcelona, 08010, Spain  G. Lima
Departamento de Física, Universidad de Concepción, 160-C Concepción, Chile
Center for Optics and Photonics, Universidad de Concepción, 160-C Concepción,
Chile  MSI-Nucleus for Advanced Optics, Universidad de Concepción, 160-C
Concepción, Chile

###### Abstract

We report on an optical setup generating more than one bit of randomness from
one entangled bit (i.e. a maximally entangled state of two-qubits). The amount
of randomness is certified through the observation of Bell non-local
correlations. To attain this result we implemented a high-purity entanglement
source and a non-projective three-outcome measurement. Our implementation
achieves a gain of 27% of randomness as compared with the standard methods
using projective measurements. Additionally we estimate the amount of
randomness certified in a one-sided device independent scenario, through the
observation of EPR steering. Our results prove that non-projective quantum
measurements allows extending the limits for nonlocality-based certified
randomness generation using current technology.

The existence of random processes, besides having philosophical consequences,
has applications in many disciplines such as cryptography and simulations of
physical, biological, and social phenomena. Mismatches between the modelling
and the actual working of random number generators (RNGs) may lead to wrong
conclusions. Quantum technologies provide a solution to this problem through
device-independent (DI) randomness generation protocols Colbeck (2006);
Pironio et al. (2010); Acín and Masanes (2016) built from Bell nonlocal
correlations Bell (1964); Brunner et al. (2014). To date, all implementations
of DIRNGs used projective measurements on quantum bits Pironio et al. (2010);
Christensen et al. (2013); Bierhorst et al. (2017), thus being limited to one
random bit per round and particle. Here, we report on an optical setup
providing more than one random bit per round from one entangled bit Acín et
al. (2016). To attain this result we implement a Bell test involving a non-
projective measurement on an entangled state of high purity. Our work
demonstrates the importance of non-projective measurements to attain the
ultimate limits for DIRNG.

Figure 1: Device-independent randomness generation scenario: a user applies
uncharacterised measurements $x$ and $y$ to two devices A and B, obtaining
outcomes $a$ and $b$ respectively. In the experiment, the user assumes that
the state of the two devices A and B is the reduced state of a pure tripartite
quantum state $|\Psi\rangle$ correlated with an adversarial party, Eve, who
holds device $E$. No further assumption is made on Eve, who could have a
complete description not only of this quantum state, but also of all the
measurements performed on it. In order to guess the outcomes produced in the
experiment, Eve applies a measurement to her device $E$ that produces outcomes
$e$. Without loss of generality, this outcome can be seen as Eve’s guess on
the user’s results.

The standard scenario for non-locality-based randomness generation consists of
a user, who has access to two quantum measurement devices, A and B, which have
input choices and provide outputs Acín and Masanes (2016), see Fig.1. The
user’s goal is to certify that the outcomes produced in the experiment are
random. We consider the strongest definition of randomness in which the user’s
outcomes are demanded to be unpredictable not only to her, but to any other
observer Acín and Masanes (2016). This, besides being fundamentally important,
guarantees that the obtained randomness is private, a requirement for
cryptographic applications Colbeck (2006); Pironio et al. (2010); Colbeck and
Kent (2011). In the device-independent scenario nothing is assumed on the
inner working of the measurement devices, which are treated as quantum black
boxes fed with classical inputs $x$ and $y$ \- the measurement choices - and
producing classical outputs $a$ and $b$ \- the measurement results. After
collecting enough statistics, the user’s description of the devices is given
by the set of conditional probabilities $P(ab|xy)$.

In randomness certification protocols it is assumed that the AB state is the
reduced state of a tripartite state $|\Psi\rangle_{ABE}$ produced by an
outsider, Eve, who holds a device E. Moreover, Eve could have prepared the
measurement devices, and thus has a complete description of the measurements
in A and B. The randomness in user’s outcome $a$ for a particular measurement
$x=x^{*}$ can be estimated through the so-called guessing probability Nieto-
Silleras et al. (2014); Bancal et al. (2014):

$\displaystyle
P_{\text{guess}}=\max_{\\{|\Psi\rangle,\Pi_{a|x},\Pi_{b|y},\Pi_{e}\\}}\sum_{a}\langle\Psi|\Pi_{a|x^{*}}\otimes\mathbb{I}\otimes\Pi_{e=a}|\Psi\rangle$
(1) such that $\displaystyle
P(ab|xy)=\langle\Psi|\Pi_{a|x}\otimes\Pi_{b|y}\otimes\mathbb{I}|\Psi\rangle.$
(2)

This quantity gives the maximum probability that E’s outcome $e$ matches the
user’s outcome $a$ for measurement $x^{*}$ over all possible quantum
realisations, described by a tripartite quantum state $|\Psi\rangle$ and
measurements $\Pi_{a|x}$, $\Pi_{b|y}$ and $\Pi_{e}$ for devices A, B and E,
compatible with the observed distribution $P(ab|xy)$. The guessing probability
can be upper bounded by semi-definite programming (SDP) techniques Nieto-
Silleras et al. (2014); Bancal et al. (2014). The estimated randomness can be
expressed in bits through $R=-\log_{2}(P_{\text{guess}})$. In order to
guarantee some amount of randomness the user’s observed correlations must be
nonlocal, that is, violate a Bell inequality. If this is not the case, they
can be reproduced by a local and deterministic model and therefore
$P_{\text{guess}}=1$ Acín and Masanes (2016).

The main motivation of this work is to probe the ultimate limits for
randomness certification using quantum resources. In order to observe a Bell
violation between A and B, the user’s state must be entangled. If the state is
of two qubits and the measurements are projective, as in standard Bell
experiments, one cannot certify more than one random bit from each qubit.
However, this is no longer the case if one uses non-projective measurements
Acín et al. (2016). We report here a photonic experiment demonstrating how
non-projective measurements offer a significant advantage in a Bell scenario
and allow one to certify more than one random bit from a qubit.

Figure 2: (Color Online) a) Our experimental setup is composed by an ultra-
bright parametric down-conversion source (see main text) generating a near-
perfect $|\psi^{-}\rangle=(|HV\rangle-|VH\rangle)/\sqrt{2}$ polarization
state, followed by polarization measurements in each photon. The measurements
$x,y=1,2,3$ have binary outcomes and are implemented using a quarter-wave
plate (QWP), a HWP and a PBS, followed by avalanche photodiode detectors
(APD). A removable mirror (RM) allows to select between measurements $x=1,2,3$
and $x=4$. The fourth and non-projective measurement, $x=4$, performed by
device A is implemented by a double path Sagnac-interferometer. b) Bloch
sphere representation of the measurements performed in A and B. The
measurements labeled by $x,y=1,2,3$ are given by symmetrically spaced two-
outcome (projective) measurements in the x-z plane, and correspond to the
settings required to maximally violate the chained Bell inequality Pearle
(1970). Measurement $x=4$ has three outcomes, corresponding to Bloch vectors
equally spaced in the x-z plane.

Our experiment is similar to a standard Bell test using photons entangled in
polarization (see Figure 2a). However we need to solve two experimental
challenges that make it unique with respect to previous experiments and that
are crucial to achieve the certification of more than one random bit. First,
we need to prepare a highly entangled state providing a very high two-photon
visibility. To achieve this, we use an ultra-bright spontaneous parametric
down-conversion source, where a type-II non-linear periodically poled
potassium titanyl phosphate (PPKTP) crystal is pumped by a continuous wave 405
nm laser to generate 810 nm polarization-entangled photons Kim et al. (2006);
Wong et al. (2007); Fedrizzi et al. (2007); Ljunggren and Tengner (2005). The
non-linear crystal is placed inside an intrinsically phase-stable Sagnac
interferometer, which is composed of two laser mirrors, a half-wave plate
(HWP), and a polarizing beamsplitter (PBS) cube. The clockwise and counter-
clockwise propagating modes of the generated pair of photons overlap inside
the interferometer resulting in the bi-photon Bell state
$|\psi^{-}\rangle=(|HV\rangle-|VH\rangle)/\sqrt{2}$. We carefully control the
spatial and spectral modes of the generated photons. Semrock high-quality
(peak transmission $>$ $90\%$) narrow bandpass (FWHM -full width at half
maximum - of 0.5 nm) filters centered at $810$ nm are used to ensure that
phase-matching conditions are achieved with the horizontal and vertical
polarization modes at degenerated frequencies. Then, we enforce path
indistinguishability of the photon pair modes (“HV” and “VH”) by coupling the
generated down-converted photons into single mode fibers (SMF) after being
transmitted by the PBS. We also adopt high-quality polarizing optics
components to ensure a polarization extinct ratio greater than $10^{7}$:1.
This guarantees that the two-photon visibility is not limited by the
polarization contrast of the detection apparatuses. Last, we use a high-
resolution coincidence field programmable gate array electronics to implement
500 ps coincidence windows, thus drastically reducing the accidental
coincidence count probability to less than $10^{-5}$ (PerkinElmer single-
photon avalanche detectors with an overall detection efficiency of $15\%$ were
used). Thanks to these measures, we attain a high overall two-photon
visibility of ($99.7\pm 0.2$)%.

Second, and contrary to standard Bell tests, our experiment consists not only
of projective measurements, but involves a non-projective measurement defined
by a Positive-Operator-Valued Measure (POVM). Indeed, while device B applies 3
projective measurements (labeled by $y$=1,2,3), device A can implement 3
projective measurements ($x$=1,2,3) plus a POVM measurement ($x$=4) of three
outcomes. All projective measurements are implemented by usual polarization
analyzers. The non-projective measurement used in our experiment consists of
three outcomes, associated with POVM elements
$\Pi_{i}=\frac{2}{3}|\psi_{i}\rangle\langle\psi_{i}|$, where

$\displaystyle|\psi_{0}\rangle=|V\rangle,$
$\displaystyle|\psi_{1}\rangle=-\frac{1}{2}(|V\rangle+\sqrt{3}|H\rangle),$ (3)
$\displaystyle|\psi_{2}\rangle=-\frac{1}{2}(|V\rangle-\sqrt{3}|H\rangle).$

This measurement is obtained in our setup by coherently coupling the
polarisation of photons with additional spatial modes in a a double-path
Sagnac interferometer (see Fig. 2a), similar to the one reported in Gómez et
al. (2016). The propagation modes of a photon within this interferometer are
not co-propagating and depend on the polarization state, which allows for
conditional polarization transformation through HWPs at angles $\theta_{1}=0$
and $\theta_{2}=2\sin^{-1}(\sqrt{2/3})$. These two propagation modes are then
superposed again in the PBS generating two new outcome modes. The first is
sent directly to the detector (first outcome), while the other experience an
additional HWP with $\theta_{3}=\pi/2$ and is split by a PBS to generate two
modes representing the second and third outcomes of the non-projective
measurement. The Bloch sphere representation of these measurements are shown
in Fig. 2b.

We also notice that in our work we invoke the fair-sampling assumption Brunner
et al. (2014), which we use to discard the no-detection events. This
assumption is highly debatable in DI cryptographic applications, in which two
distant users are connected by a channel whose losses can be simulated by an
eavesdropper. But note that it is less critical in DIRNGs protocols in which
the two devices are in the same location and under control of a honest user.

Using the estimated visibilities we first run a numerical search to find
measurements that maximise the amount of randomness generated in our scenario.
This search led us to the measurement settings shown in Fig. 2b. By
implementing these measurements we obtained a collection of observed
experimental frequencies $f(ab|xy)$ that we use to estimate randomness in the
following way (see Supp. Mat. for more details). The raw data obtained from
measurements is avilable in gitrep. We first used a regularization method Lin
et al. (2017) based on the Collins-Gisin parametrization Collins and Gisin
(2004) of the space of probabilities to generate a set of no-signaling
probability distributions $P_{NS}=\\{P_{NS}(ab|xy)\\}$. By considering
marginal probabilities $P(a|x,y=1)$ and $P(b|x=1,y)$, the Collins-Gisin
representation enforces no-signaling constraints of $P$ by dropping all
probabilities involving the last outcome of all measurements. For instance,
for the POVM that has 3 outcomes, the probability $P_{NS}(a=3,b|xy)$ is
implicitly set by imposing
$P_{NS}(a=3,b|xy)=P(a=3|x,y=1)-P(a=2,b|xy)-P(a=1|xy)$.

With $P_{NS}$ we run the semidefinite (SDP) program proposed in Refs. Nieto-
Silleras et al. (2014); Bancal et al. (2014), that provides an upper bound to
the guessing probability (S7). The solution of this SDP optimisation provides
a linear function $S(P)$ whose value is a lower bound on the amount of
randomness of any set of distributions $P$. We finally rewrite $S$ in terms of
expected values and use it to estimate the amount of randomness in our
experiment. The errors of the recorded probabilities are calculated assuming
fair samples from Poissonian distributions and Gaussian error propagation.
Notice that our statistical analysis is done under the assumption of
independent and identical distributed (iid) copies of the same experiment, for
which the guessing probability (S7) is well defined. Other statistical methods
are available Pironio et al. (2010); Zhang et al. (2011); Bierhorst et al.
(2017), but this is beyond the scope of this work.

After these steps we were able to certify

$R_{povm}^{DI}=1.18\pm{0.08}$ (4)

bits of randomness per use of the devices. As a matter of comparison we also
performed the same analysis in the case Alice and Bob use only the projective
measurements $x,y=1,2,3$ and randomness is obtained from the setting $x=1$. In
this case $R_{proj}^{DI}=0.93\pm 0.08$. Thus, the addition of a 3-outcome non-
projective measurement provided a gain of 27% of randomness.

In our setup, we can also certify randomness in a semi-device independent
scenario in which device B is assumed to be fully characterised. In this
scenario randomness can be certified by the presence of quantum steering
Wiseman et al. (2007), a situation where the box A is still treated as black
boxes with inputs $x$ and outputs $a$, while B is assumed to be able to make
tomography of the conditional states $\rho_{a|x}^{B}$. The information the
user has in this situation can be summarized in the set of unnormalized
quantum sates $\\{\sigma_{a|x}^{B}\\}_{a,x}$, where
$\sigma_{a|x}^{B}=p(a|x)\rho_{a|x}^{B}$. Notice that, in order to obtain a set
$\\{\sigma_{a|x}^{B}\\}_{a,x}$ that satisfy the no-signalling conditions
$\sum_{a}\sigma_{a|x}^{B}=\sum_{a}\sigma_{a|x^{\prime}}^{B}$ we also need to
resort on the distributions $P_{NS}$ obtained through the Collins-Gisin
parametrization. Given the knowledge of $\\{\sigma_{a|x}^{B}\\}_{a,x}$, the
guessing probability of the outcome $a$ of the measurement $x^{\prime}$ can
also be estimated through a semi-definite program Passaro et al. (2015). The
amount of randomness can be calculated in a similar manner as in (S7) Passaro
et al. (2015) and, in this case, we were able to certify
$R^{St}_{povm}=1.27\pm 0.14$.

In the context of certified RNG protocols, our work is relevant both from a
fundamental and applied perspective, as it demonstrates how the more general
class of non-projective quantum measurements allows extending the limits for
nonlocality-based certified randomness generation using current technology. In
the scenario of device-independent quantum information processing, we show
that a gain of 27$\%$ in the rate of random bit string generation is possible.
In the case of semi-device independent RNG protocols, we demonstrate that this
gain can be improved to $36\%$.

We thank A. Cabello, T. Vértesi, and M. Pawlowski for discussions. This work
was supported by the Ramón y Cajal fellowship, Spanish MINECO (QIBEQI
FIS2016-80773-P and Severo Ochoa SEV-2015-0522), the AXA Chair in Quantum
Information Science, Generalitat de Catalunya (SGR875 and CERCA Programme),
Fundació Privada Cellex, Fondecyt 1160400, CONICYT PFB08-024,and Milenio
RC130001. E.S.G. acknowledges support from Fondecyt 11150325. S.G.
acknowledges CONICYT.

## References

  * Colbeck (2006) R. Colbeck, Ph.D. thesis, University of Cambridge (2006).
  * Pironio et al. (2010) S. Pironio, A. Acín, S. Massar, B. de la Giroday, D. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. Manning, et al., Nature 464, 1021 (2010), ISSN 0028-0836.
  * Acín and Masanes (2016) A. Acín and L. Masanes, Nature 540, 213 (2016).
  * Bell (1964) J. S. Bell, Physics 1, 195 (1964).
  * Brunner et al. (2014) N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Reviews of Modern Physics 86, 419 (2014), eprint 1303.2849.
  * Christensen et al. (2013) B. G. Christensen, K. T. McCusker, J. B. Altepeter, B. Calkins, T. Gerrits, A. E. Lita, A. Miller, L. K. Shalm, Y. Zhang, S. W. Nam, et al., Physical Review Letters 111, 130406 (2013), eprint 1306.5772.
  * Bierhorst et al. (2017) P. Bierhorst, E. Knill, S. Glancy, A. Mink, S. Jordan, A. Rommal, Y.-K. Liu, B. Christensen, S. W. Nam, and L. K. Shalm, ArXiv e-prints (2017), eprint 1702.05178.
  * Acín et al. (2016) A. Acín, S. Pironio, T. Vértesi, and P. Wittek, Phys. Rev. A 93, 040102 (2016), eprint 1505.03837.
  * Colbeck and Kent (2011) R. Colbeck and A. Kent, Journal of Physics A Mathematical General 44, 095305 (2011), eprint 1011.4474.
  * Nieto-Silleras et al. (2014) O. Nieto-Silleras, S. Pironio, and J. Silman, New Journal of Physics 16, 013035 (2014), eprint 1309.3930.
  * Bancal et al. (2014) J.-D. Bancal, L. Sheridan, and V. Scarani, New Journal of Physics 16, 033011 (2014), eprint 1309.3894.
  * Pearle (1970) P. M. Pearle, Phys. Rev. D 2, 1418 (1970), URL https://link.aps.org/doi/10.1103/PhysRevD.2.1418.
  * Kim et al. (2006) T. Kim, M. Florentino, and F. N. C. Wong, Phys. Rev. A 73 (2006).
  * Wong et al. (2007) F. N. C. Wong, J. H. Shapiro, and T. Kim, Laser physics 16 (2007).
  * Fedrizzi et al. (2007) A. Fedrizzi, T. Herbst, A. Poppe, T. Jennewein, and A. Zeilinger, Optics Express 15 (2007).
  * Ljunggren and Tengner (2005) D. Ljunggren and M. Tengner, Phys. Rev. A 72 (2005).
  * Gómez et al. (2016) E. S. Gómez, S. Gómez, P. González, G. Cañas, J. F. Barra, A. Delgado, G. B. Xavier, A. Cabello, M. Kleinmann, T. Vértesi, et al., Physical Review Letters 117, 260401 (2016).
  * Lin et al. (2017) P.-S. Lin, D. Rosset, Y. Zhang, J.-D. Bancal, and Y.-C. Liang, ArXiv e-prints (2017), eprint 1705.09245.
  * Collins and Gisin (2004) D. Collins and N. Gisin, Journal of Physics A: Mathematical and General 37, 1775 (2004), URL http://stacks.iop.org/0305-4470/37/i=5/a=021.
  * Zhang et al. (2011) Y. Zhang, S. Glancy, and E. Knill, Phys. Rev. A 84, 062118 (2011).
  * Wiseman et al. (2007) H. M. Wiseman, S. J. Jones, and A. C. Doherty, Physical Review Letters 98, 140402 (2007), eprint quant-ph/0612147.
  * Passaro et al. (2015) E. Passaro, D. Cavalcanti, P. Skrzypczyk, and A. Acín, New Journal of Physics 17, 113010 (2015), eprint 1504.08302.
  * Navascués et al. (2007) M. Navascués, S. Pironio, and A. Acín, Physical Review Letters 98, 010401 (2007), eprint quant-ph/0607119.

##  I Supplemental Material

##  II Optical Implementation of a 3-element POVM

In order to implement a generalized measurement of more than two outcomes in
the 2 dimensional polarization degree of freedom, we adopt the strategy of
coupling to additional spatial modes through the Sagnac intereferometer in fig
S1a).

Figure S1: In fig. $1a)$ the Sagnac interferometer used to implement the
3-outcome POVM. Fig. $1b)$ shows the corrersponding quantum circuit.

We consider the polarization basis for the single photon
$\\{|H\rangle,|V\rangle\\}$ and two spatial modes $\\{|0\rangle,|1\rangle\\}$
created by the Polarizing Beam Splitter (PBS) which defines the Sagnac
interferometer. The action of the interferometer can be better understood by
the quantum circuit in fig S1 b): A single photon with polarization
$|\psi\rangle$, enters the through port $|0\rangle$ of the PBS and populates
the spatial modes according to

$\displaystyle|H\rangle|0\rangle\rightarrow|H\rangle|0\rangle$
$\displaystyle|V\rangle|0\rangle\rightarrow|V\rangle|1\rangle$ (S1)

The input port $|1\rangle$ is fed with vacuum, but an analogous analysis of
its working completes de specification of the $CNOT$ gate implemented by the
PBS. Once inside the interferometer, half wave plates at angles $\theta_{1}$
and $\theta_{2}$ rotate polarization depending on the spatial mode the photon.
That is, internal half wave plates implement controlled operations,
$C_{1}(\theta_{1})$ controlled by the state $|0\rangle$ and
$C_{2}(\theta_{2})$. A new passage through the same PBS implements a second
$CNOT$ gate, controlled by the polarization. Finally we insert a half wave
plate on output mode $|0\rangle$ at $\theta_{3}$ implementing the controlled
operation $C_{3}(\theta_{3})$.

The total unitary transformation which couples polarization with spatial modes
is given

$\displaystyle
U=C_{3}(\theta_{3})*CNOT*C_{2}(\theta_{2})*C_{1}(\theta_{1})*CNOT$ (S2)

The coupling matrix (S2) followed by detection in spatial modes, defines a
family of POVM’s in polarization parametrized by $\theta_{1}$, $\theta_{2}$
and $\theta_{3}$ . In order to obtain this extremal POVM we chose the settings
$\theta_{1}=0,\theta_{2}=2\rm{sin}\sqrt{2/3},\theta_{3}=\pi/2$. In this
situation, our interferometer works as selective attenuator of the $|V\rangle$
component, the part that has been attenuated, goes to output mode $|1\rangle$.
As an example, we consider the effect of $U$ on the states
$\\{|\psi_{0}\rangle,|\psi_{1}\rangle,|\psi_{2}\rangle\\}$ of Eq.3 in the main
text:

$\displaystyle\begin{array}[]{l}|\psi_{0}\rangle\rightarrow\sqrt{1/6}|0\rangle|H\rangle+\sqrt{1/6}|0\rangle|V\rangle+\sqrt{2/3}|1\rangle|V\rangle\\\
|\psi_{1}\rangle\rightarrow\sqrt{2/3}|0\rangle|H\rangle+\sqrt{1/6}|0\rangle|V\rangle+\sqrt{1/6}|1\rangle|V\rangle\\\
|\psi_{2}\rangle\rightarrow\sqrt{1/6}|0\rangle|H\rangle+\sqrt{2/3}|0\rangle|V\rangle+\sqrt{1/6}|1\rangle|V\rangle.\end{array}$
(S6)

By inserting a PBS in the outcome mode $|0\rangle$ we obtain the three outcome
ports with the measurement statistics defining the POVM
$\\{\frac{2}{3}|\psi_{0}\rangle\langle\psi_{0}|,\frac{2}{3}|\psi_{1}\rangle\langle\psi_{1}|,\frac{2}{3}|\psi_{2}\rangle\langle\psi_{2}|\\}$.

##  III Device-independent randomness certification

In our experiment we obtain a collection of observed experimental frequencies
$f(ab|xy)$. Retrieving the amount of randomness from this data is not
straightforward because the probability distributions $P(ab|xy)$ obtained upon
normalizing these frequencies are ill defined due to the finite statistics
regime intrinsic of any implementation. For instance they do not satisfy the
no-signaling conditions (satisfied in quantum mechanics) defined by
$\sum_{b}P(ab|xy)=\sum_{b}P(ab|xy^{\prime})$ (no-signaling from B to A) and
$\sum_{a}P(ab|xy)=\sum_{a}P(ab|x^{\prime}y)$ (no-signaling from A to B).

In order to circumvent this problem we use the following steps. From the
experimental frequencies $f(ab|xy)$ we generated a set of no-signaling
probability distributions $P_{NS}=\\{P_{NS}(ab|xy)\\}$ through the Collins-
Gisin parametrization of the space of probabilities Collins and Gisin (2004).
By considering marginal probabilities $P(a|x,y=1)$ and $P(b|x=1,y)$, the
Collins-Gisin representation enforces no-signaling constraints of $P$ by
dropping all probabilities involving the last outcome of all measurements. For
instance, for the POVM that has 3 outcomes, the probability $P_{NS}(a=3,b|xy)$
is implicitly set by imposing
$P_{NS}(a=3,b|xy)=P(a=3|x,y=1)-P(a=2,b|xy)-P(a=1|xy)$.

With $P_{NS}$ we run the semidefinite (SDP) program proposed in Refs. Nieto-
Silleras et al. (2014); Bancal et al. (2014), that provides an upper bound to
the guessing probability (S7):

$\displaystyle P_{guess}=\max_{\\{P(abe|xy)\\}}P(a=e|x^{*})$ (S7) such that
$\displaystyle P(ab|xy)=\sum_{e}P(a,b,e|x,y)\quad\forall~{}a,b,x,y$ (S8)
$\displaystyle P(abe|xy)\geq 0\quad\forall~{}a,b,e,x,y$ (S9)
$\displaystyle\sum_{abe}P(abe|xy)=1\quad\forall~{}x,y$ (S10)
$\displaystyle\\{P(a,b,e|x,y)\\}_{a,b,e,x,y}\in\mathcal{Q}_{2}.$ (S11)

This expression gives the maximum probability that Eve’s outcomes match
Alice’s, given that the distributions observed are marginals of a joint
tripartite distribution with Eve (constraints (2) and (3)). The last
constraint (4) means that the joint distributions lie into the set
$\mathcal{Q}_{2}$, an outer approximation to the set of quantum probability
distributions $\mathcal{Q}$ proposed in Navascués et al. (2007).

The solution of this SDP optimization provides a linear function $S(P)$ whose
value is a lower bound on the amount of randomness of any set of distributions
$P$. We finally rewrite $S$ in terms of expected values and use it to estimate
the amount of randomness in our experiment. The errors of the recorded
probabilities are calculated assuming fair samples from Poissonian
distributions and Gaussian error propagation. We note that our statistical
analysis considers the asymptotic limit of many experimental runs. A more
detailed statistical methods considering finite statistic Pironio et al.
(2010); Zhang et al. (2011); Bierhorst et al. (2017) is beyond the scope of
this work.

##  IV Randomness certification in the steering scenario

The steering scenario refers to the situation where the box A is still treated
as black boxes with inputs $x$ and outputs $a$, while B is assumed to be able
to make tomography of the conditional states $\rho_{a|x}^{B}$. The information
the user has in this situation can be summarized in the set of unnormalized
quantum sates $\\{\sigma_{a|x}^{B}\\}_{a,x}$, where
$\sigma_{a|x}=p(a|x)\rho_{a|x}^{B}$. Given the knowledge of
$\\{\sigma_{a|x}\\}_{a,x}$, Alice and Bob can estimate the amount of
randomness in Alice’s outcomes through the following semi-definite program
Passaro et al. (2015):

$\displaystyle
P_{guess}(x^{*})=\max_{\\{\sigma_{a|x}^{e}\\}}\quad\operatorname{Tr}\sum_{e}\sigma_{a=e|x^{*}}^{e}$
(S12) such that
$\displaystyle\sum_{e}\sigma_{a|x}^{e}=\sigma_{a|x}\quad\forall a,x,$ (S13)
$\displaystyle\sum_{a}\sigma_{a|x}^{e}=\sum_{a}\sigma_{a|x^{\prime}}^{e}\quad\forall
e,x,x^{\prime},$ (S14) $\displaystyle\sigma_{a|x}^{e}\geq 0\quad\forall
a,x,e.$ (S15)

Once more, the solution of this program gives a linear function (a quantum
steering inequality) of the experimental data that can be used to calculate a
the guessing probability and appropriate errors.