# In-N-Out Generative Learning for Dense Unsupervised Video Segmentation

Xiao Pan1,2, Peike Li2,3, Zongxin Yang1, Huiling Zhou2, Chang Zhou2,
Hongxia Yang2, Jingren Zhou2, Yi Yang1 1ReLER Lab, CCAI, Zhejiang University
China
2Alibaba DAMO Academy China
3Australian Artificial Intelligence Institute, University of Technology Sydney
Australia

(2022)

###### Abstract.

In this paper, we focus on unsupervised learning for Video Object Segmentation
(VOS) which learns visual correspondence (i.e., the similarity between pixel-
level features) from unlabeled videos. Previous methods are mainly based on
the contrastive learning paradigm, which optimize either in image level or
pixel level. Image-level optimization (e.g., the spatially pooled feature of
ResNet) learns robust high-level semantics but is sub-optimal since the pixel-
level features are optimized implicitly. By contrast, pixel-level optimization
is more explicit, however, it is sensitive to the visual quality of training
data and is not robust to object deformation. To complementarily perform these
two levels of optimization in a unified framework, we propose the In-aNd-Out
(INO) generative learning from a purely generative perspective with the help
of naturally designed class tokens and patch tokens in Vision Transformer
(ViT). Specifically, for image-level optimization, we force the out-view
imagination from local to global views on class tokens, which helps capture
high-level semantics, and we name it as out-generative learning. As to pixel-
level optimization, we perform in-view masked image modeling on patch tokens,
which recovers the corrupted parts of an image via inferring its fine-grained
structure, and we term it as in-generative learning. To discover the temporal
information better, we additionally force the inter-frame consistency from
both feature and affinity matrix levels. Extensive experiments on DAVIS-2017
val and YouTube-VOS 2018 val show that our INO outperforms previous state-of-
the-art methods by significant margins. Code:
https://github.com/pansanity666/INO_VOS

unsupervised video object segmentation, self-supervised learning, dense
prediction, generative learning

††journalyear: 2022††copyright: acmlicensed††conference: Proceedings of the
30th ACM International Conference on Multimedia ; October 10–14, 2022; Lisboa,
Portugal.††booktitle: Proceedings of the 30th ACM International Conference on
Multimedia (MM ’22), October 10–14, 2022, Lisboa, Portugal††price:
15.00††isbn: 978-1-4503-9203-7/22/10††doi:
https://doi.org/10.1145/3503161.3547909††submissionid: 666††ccs: Computing
methodologies Video segmentation††ccs: Computing methodologies Image
segmentation††ccs: Computing methodologies Image representations

##  1\. Introduction

Figure 1. Idea illustration for In-N-Out generative learning. In-generative
learning is the in-view recovery of masked patches, while out-generative
learning is the out-view imagination from local to global views.

Video Object Segmentation (Wang et al., 2021b; Araslanov et al., 2021; Miao et
al., 2020; Oh et al., 2019; Yang et al., 2020, 2019b) (VOS) is a fundamental
video understanding task having a wide range of real-world applications, e.g.,
augmented reality (Xiong et al., 2021), and video editing (Lin et al., 2021).
In this task, we aim to segment a specified object instance throughout the
entire video sequence, given only the ground-truth object mask on the first
frame. Although the development of convolutional neural networks (CNNs) (He et
al., 2016) has significantly advanced the VOS task, the success of these
approaches highly relies on the cost-intensive and time-consuming dense mask
annotations to train the networks. Moreover, the fully-supervised VOS is also
largely limited by the diversity and scale of the annotated datasets. To
relieve such limitations, recently unsupervised/self-supervised methods for
VOS (Araslanov et al., 2021; Jabri et al., 2020; Lai et al., 2020) have drawn
considerable attention, which can completely liberate the request for mask
annotations.

However, the previous approaches still suffer from the following perspectives:
(i)Image-level vs. pixel-level. Several existing methods (Jabri et al., 2020;
Xu and Wang, 2021) perform self-supervised learning on the image-level
features, e.g., the spatially pooled feature of ResNet (He et al., 2016). Such
optimization can learn robust high-level semantics, however, it is sub-optimal
since the pixel-level features used for calculating the final correspondence
are learned implicitly. Another line of works (Araslanov et al., 2021; Lai et
al., 2020; Wang et al., 2019) explicitly optimize on the pixel-level features,
however, such paradigm may be sensitive to the visual quality of training data
and is lack of the high-level semantic scope which may reduce the robustness
toward deformation. We believe that these two levels of optimization are
complementary to each other and can be integrated into a unified framework;
(ii) CNN vs. ViT. Previous unsupervised methods (Araslanov et al., 2021; Jabri
et al., 2020; Xu and Wang, 2021) for VOS adopt the convolutional networks
(CNNs) (He et al., 2016) as the backbone model. However, we propose that
Vision Transformer (ViT) (Dosovitskiy et al., 2020; Touvron et al., 2021) is a
better choice for unifying these two levels of optimization. Specifically,
different from the CNNs which obtain the image-level features via the average
pooling of pixel-level features, the naturally designed class tokens and patch
tokens of ViT have their own semantic meanings, i.e., class tokens capture the
high-level semantics which are suitable for image-level optimization, while
patch tokens represent fine-grained details, which are appropriate for pixel-
level optimization. (iii) Contrastive vs. generative. Previous self-supervised
methods for VOS (Araslanov et al., 2021; Jabri et al., 2020; Xu and Wang,
2021) employ a self-training objective mainly based on contrastive formulation
(He et al., 2020). However, their experimental results show unsatisfactory
scalability toward the training data scales, especially for the pixel-level
methods (Araslanov et al., 2021). On the other hand, the recent success of the
generative learning paradigm (He et al., 2021) shows its better scalability
and robustness. Therefore, we propose that solving the VOS task from the
generative learning perspective is promising, yet unexplored.

To tackle the aforementioned issues, we present a simple yet effective
framework called In-aNd-Out (INO) generative learning from a novel fully
generative learning perspective. As opposed to the previous methods (Araslanov
et al., 2021; Jabri et al., 2020; Xu and Wang, 2021) (detailed in Table 1),
INO integrates image-level and pixel-level optimization in a unified framework
with the help of naturally designed high-level class tokens and fine-grained
patch tokens in ViT.

More concretely, as illustrated in Fig. 1, our INO framework contains two
generative objectives, i.e., in-generative learning and out-generative
learning. (i) Out-generative learning is the out-view imagination from local
views to global views on class tokens, which corresponds to the image-level
optimization. We aim to learn high-level visual semantics via imagining the
global visual information given only a portion of the local visual part, which
may improve the robustness toward deformation and occlusion. (ii) In-
generative learning is the in-view recovery of randomly masked patch tokens in
the feature embedding space, which belongs to the pixel-level optimization.
The goal of in-generative learning is to capture fine-grained structural
information, which is beneficial for recognizing the gradually appearing parts
of a semantic object given incomplete labels in the first frame. In this way,
both in-and-out generative objectives complement each other towards better
visual representation learning. To better discover the temporal information,
we additionally equip INO with temporally-persistent constraints, by forcing
the inter-frame consistency from both feature level and affinity matrix level.
Extensive experiments on DAVIS-2017 val and YouTube-VOS 2018 val show that our
INO outperforms previous methods by significant margins. Our main
contributions are summarized as follows,

  * •

We propose a simple yet effective framework INO to tackle the challenging
unsupervised learning for VOS, which integrates image-level and pixel-level
optimization in a unified framework by leveraging the structural superiority
of ViT.

  * •

To the best of our knowledge, we make the first attempt to conduct
unsupervised learning for VOS from a novel fully generative learning
perspective based on the idea of masked image modeling.

  * •

We attain a new state-of-the-art performance on unsupervised learning for VOS.

Table 1. Comparisons between different state-of-the-art VOS methods. Method |  Self- supervised |  Transformer- based |  Unified optimization |  Generative learning
---|---|---|---|---
AOT (NIPS 2021) (Yang et al., 2021a) | ✗ | ✓ | ✗ | ✗
CRW (NIPS 2020) (Jabri et al., 2020) | ✓ | ✗ | ✗ | ✗
VFS (ICCV 2021) (Xu and Wang, 2021) | ✓ | ✗ | ✗ | ✗
DUL (NIPS 2021) (Araslanov et al., 2021) | ✓ | ✗ | ✗ | ✗
INO (Ours) | ✓ | ✓ | ✓ | ✓

##  2\. Related Work

Vision Transformers for Dense Prediction. Most previous VOS methods (Araslanov
et al., 2021; Jabri et al., 2020; Lai et al., 2020; Wang et al., 2019; Xu and
Wang, 2021) adopt convolutional neural networks (CNNs) as the architectures to
learn the visual representations. Recently, the development (Dosovitskiy et
al., 2020; Touvron et al., 2021) of Vision Transformer (ViT) architecture
shows overwhelming success over CNNs. Beyond the simple image classification
tasks (Liu et al., 2021), researchers have successfully adopted the ViT
architecture in several dense prediction tasks, e.g., object detection (Carion
et al., 2020), semantic segmentation (Wang et al., 2021a), etc. However, these
works mainly focus on still images and study the fully-supervised settings. In
contrast, our INO is specially designed to solve the video object segmentation
via self-supervised training. We exploit the architecture privilege of ViT by
using the naturally designed high-level class tokens and fine-grained patch
tokens.

VOS via Self-supervised Learning. Some previous approaches (Liang et al.,
2021; Miao et al., 2020; Oh et al., 2019; Yang et al., 2019a, 2021b) learn
visual representation fully supervised by annotated datasets with pixel-wise
labels. However, these fully-supervised VOS methods are highly restricted by
the diversity of annotated categories and the scale of the annotated dataset.
In this work, we explore a more promising and efficient way which is to
leverage self-supervised learning (Caron et al., 2021; He et al., 2020) to
conduct VOS. Previous self-supervised works either only consider the high-
level global representations (Xu and Wang, 2021; Jabri et al., 2020), or
directly perform the contrastive learning on the fine-grained pixel-wise
features (Araslanov et al., 2021). Benefiting from the flexibility of vision
transformer-based architecture, we optimize both high-level semantics on class
tokens and fine-grained semantics on patch tokens, which brings better
correspondence learning.

Figure 2. Overview of INO framework. For illustration, we assume that the
video length $L=2$, and for each frame we crop $1$ global crop and $2$ local
crops. (i) _Out-generative learning_ is the _out-view_ mapping between high-
level class tokens, which is composed of $\mathcal{L}_{out\\_g2g}$ and
$\mathcal{L}_{out\\_l2g}$. Concisely, $\mathcal{L}_{out\\_g2g}$ is cross-frame
calculated between global crop outputs, while $\mathcal{L}_{out\\_l2g}$ is all
the possible local-to-global mappings. (ii) _In-generative learning_ is the
_in-view_ recovery on fine-grained patch tokens of global crops, which is
composed of $\mathcal{L}_{in\\_mim}$ and $\mathcal{L}_{in\\_aff}$. In detail,
$\mathcal{L}_{in\\_mim}$ is the mapping between mask tokens and the
corresponding teacher patch tokens, while $\mathcal{L}_{in\\_aff}$ improves
the inter-frame correspondence via bootstrapping.

From Contrastive Learning to Generative Learning. Recently, contrastive
learning (Grill et al., 2020; He et al., 2020) has been popular for self-
supervised learning, which models image similarity and dissimilarity between
different views. Although migrating these methods on VOS tasks (Araslanov et
al., 2021; Jabri et al., 2020; Xu and Wang, 2021; Jeon et al., 2021; Zhao et
al., 2021) has achieved a preliminary success, the contrastive-based methods
strongly depend on data augmentation (Jabri et al., 2020), and may also suffer
the scalability problem (Araslanov et al., 2021; Jabri et al., 2020). Inspired
by masked language modeling (Devlin et al., 2018) in NLP, recent attempts (Bao
et al., 2021; He et al., 2021) learn representations by masked image modeling.
However, these methods either reconstruct the original images in original
pixels (He et al., 2021), or predict the quantized discrete tokens (Bao et
al., 2021). As illustrated in Fig. 1, we discover more abundant supervised
signals directly in feature embedding space, by recovering masked patch tokens
(in-generative) and imagining global information (out-generative). To the best
of our knowledge, we make the first attempt to address self-supervised
learning for VOS from a fully generative learning perspective based on the
idea of masked image modeling.

##  3\. Method

Overview. Unsupervised learning for video object segmentation targets on
achieving semantically discriminative representations via training on
unlabeled videos. During the inference stage, given the mask annotation of the
first frame, the label propagation is performed via the correspondence
(similarity) between the extracted feature maps (Araslanov et al., 2021; Jabri
et al., 2020; Lai et al., 2020; Xu and Wang, 2021). As illustrated in Fig. 2,
we introduce the proposed In-N-Out generative learning framework for the
unsupervised learning for VOS, which is composed of out-generative learning on
high-level class tokens and in-generative learning on fine-grained patch
tokens. In § 3.1 we first introduce the generic teacher-student framework. §
3.2 demonstrates the proposed out-generative learning targets on mining high-
level semantic consistency via the imagination between augmented crops. § 3.3
introduces the proposed in-generative learning which focuses on achieving
fine-grained semantics via the recovery of the corrupted semantic structure.
We present the brief training and inference pipeline of the proposed INO in §
3.4.

###  3.1. Generative Learning Framework

We use the commonly used teacher-student framework (Caron et al., 2021; Zhou
et al., 2021) for self-supervised learning. The teacher $\mathcal{T}$ and
student $\mathcal{S}$ share the same architecture which includes a backbone
(e.g., ViT (Dosovitskiy et al., 2020; Touvron et al., 2021)) and a projection
head. Without loss of generality, we directly adopt the original ViT
implementation. The improvement of the backbone model is not the focus of this
paper. The teacher parameters are the Exponentially Moving Average (EMA) of
the student parameters. To avoid collapse, a stop-gradient operator is applied
to the teacher, and the teacher output is centered by the computed batch mean
(Caron et al., 2021). Then, each network outputs (including both class tokens
and patch tokens) are normalized with a temperature softmax to get the final
categorical distributions (Zhou et al., 2021). The output categorical
distributions of the teacher are taken as the generation target of the student
output and their similarity is measured with a standard cross-entropy loss.
Notably, the class tokens mainly capture the high-level semantic information,
while the patch tokens focus more on the fine-grained details. Therefore, we
choose class tokens for out-generative learning and patch tokens for in-
generative learning, respectively.

###  3.2. Out-generative Learning

Given the $i$-th frame in a video clip of length $L$, we first achieve one
global crop $\textbf{g}^{i}$ and $M$ local crops
$\\{\textbf{l}^{ij}\\}_{j=1}^{M}$ via random resized cropping under different
scales. Then, flipping and color jitter are randomly applied for each crop.
The augmented crops from frames of the same video clip may be quite different
in low-level vision due to the performed augmentation and the motion nature of
videos. However, since they are from the same semantic scene, they share
similar high-level semantic meaning. We intend to leverage such high-level
semantic consistency as the supervision signal for out-generative learning,
which can be further divided into global-to-global and local-to-global
generation, as illustrated in the lower-left part of Fig. 2.

Temporal Consistency via Global-to-global Generation. Considering the
consecutive nature of video sequences, the global crops from different frames
of a certain sequence may share most of the semantic objects when the scale
range for cropping is large. In this case, the most salient difference may
come from the motion of objects, which should be recognized for better
segmentation label propagation, e.g., the person with different poses in
different frames should be recognized as the same person. Therefore, we
propose to perform generation between these inter-frame global crops to
capture such temporal semantic consistency in the presence of motion.

Specifically, for a sequence of length $L$, we empirically split the sequence
into halves and then zip them as frame pairs
$\mathcal{P}=\\{(n,L/2+n)\\}_{n=1}^{L/2}$. Taking $L=6$ as an example, the
formulated pairs are $\\{(1,4),(2,5),(3,6)\\}$. Given a frame pair
$(i_{1},i_{2})\in\mathcal{P}$, all the global crops
$\\{\textbf{g}^{i_{1}},\textbf{g}^{i_{2}}\\}$ are sent to the student together
with the teacher, and the global-to-global out-generative learning is
performed as:

(1)
$\mathcal{L}_{out\\_g2g}=\frac{1}{|\mathcal{P}|}\sum_{(i_{1},i_{2})\in\mathcal{P}}\sum_{\textbf{t}\in\mathbbm{T}}\sum_{\textbf{s}\in\mathbbm{S}\backslash\\{\textbf{t}\\}}-\mathcal{T}^{[cls]}(\textbf{t})^{T}log\mathcal{S}^{[cls]}(\textbf{s}),$

where $\mathbbm{T}=\\{\textbf{g}^{i_{1}},\textbf{g}^{i_{2}}\\}$,
$\mathbbm{S}=\\{\textbf{g}^{i_{1}},\textbf{g}^{i_{2}}\\}$.

Semantic Correlation via Local-to-global Generation. Compared with the global-
to-global generation, local-to-global generation solves a harder task, which
is to imagine the complete scene given limited information from random
semantic fragments. In this scenario, not only motion consistency, but also
the inference of the high-level semantic correlation is required. For example,
given the fragment of a motorcross and a part of the human leg, the model is
required to infer that “a rider is riding a motorcross”, as illustrated in
Fig. 1. Such high-level inference helps the model to capture more robust and
complete semantics, which is beneficial to the stable propagation of masks.

Specifically, for frame pair $(i_{1},i_{2})\in\mathcal{P}$, all the local
crops are sent to the student and calculated with the previous teacher outputs
of global crops. Similar to Eq 1, the local-to-global generative learning is
performed as:

(2)
$\mathcal{L}_{out\\_l2g}=\frac{1}{|\mathcal{P}|}\sum_{(i_{1},i_{2})\in\mathcal{P}}\sum_{\textbf{t}\in\mathbbm{T}}\sum_{\textbf{s}\in\mathbbm{S}}-\mathcal{T}^{[cls]}(\textbf{t})^{T}log\mathcal{S}^{[cls]}(\textbf{s}),$

where $\mathbbm{T}=\\{\textbf{g}^{i_{1}},\textbf{g}^{i_{2}}\\}$,
$\mathbbm{S}=\\{\textbf{l}^{{i_{1}}j},\textbf{l}^{{i_{2}}j}\\}_{j=1}^{M}$.

Table 2. Comparisons with state-of-the-art methods on DAVIS-2017 val. RN-18 and ViT-S/8 represent for ResNet-18 and Vit-Small with a patch size of 8, separately. “†” means using 2 times larger resolution for inference. We also report the number of video sequences (N) and the total video duration (T) for each dataset.  Method | Arch | Dataset | N/T | $\mathcal{J}\&\mathcal{F}_{m}$ | $\mathcal{J}_{m}$ | $\mathcal{J}_{r}$ | $\mathcal{F}_{m}$ | $\mathcal{F}_{r}$
---|---|---|---|---|---|---|---|---
TimeCycle (Wang et al., 2019) | RN-18 | VLOG | 114K / 344h | - | 40.1 | - | 38.3 | -
TimeCycle (Wang et al., 2019) | RN-50 | VLOG | 114K / 344h | - | 41.9 | - | 39.4 | -
CorrFlow†(Lai and Xie, 2019) | RN-18 | Kinetics | 300K / 833h | 49.5 | 47.7 | 53.2 | 51.3 | 56.5
CorrFlow†(Lai and Xie, 2019) | RN-18 | OxUvA | 366 / 14h | 50.3 | 48.4 | 53.2 | 52.2 | 56.0
ContCorr (Wang et al., 2020) | RN-18 | TrackingNet | 30K / 140h | 63.0 | 60.5 | - | 65.5 | -
MAST†(Lai et al., 2020) | RN-18 | OxUvA | 366 / 14h | 63.7 | 61.2 | 73.2 | 66.3 | 78.3
MAST†(Lai et al., 2020) | RN-18 | YT-VOS | 4.5K / 5h | 65.5 | 63.3 | 73.2 | 67.6 | 77.7
CRW (Jabri et al., 2020) | RN-18 | Kinetics | 300K / 833h | 67.6 | 64.8 | 76.1 | 70.2 | 82.1
JSTG (Zhao et al., 2021) | RN-18 | Kinetics | 300K / 833h | 68.7 | 65.8 | 77.7 | 71.6 | 84.3
DUL (Araslanov et al., 2021) | RN-18 | OxUvA | 366 / 14h | 65.3 | 63.4 | 76.1 | 67.2 | 79.7
DUL (Araslanov et al., 2021) | RN-18 | Kinetics | 300K / 833h | 68.7 | 66.7 | 81.4 | 70.7 | 84.1
DUL (Araslanov et al., 2021) | RN-18 | YT-VOS | 4.5K / 5h | 69.3 | 67.1 | 81.2 | 71.6 | 84.9
DUL (Araslanov et al., 2021) | RN-18 | TrackingNet | 30K / 140h | 69.4 | 67.1 | 80.9 | 71.7 | 84.8
VFS (Xu and Wang, 2021) | RN-18 | Kinetics | 300K / 833h | 67.6 | 64.8 | - | 70.2 | -
VFS (Xu and Wang, 2021) | RN-50 | Kinetics | 300K / 833h | 69.4 | 66.7 | - | 72.0 | -
INO (Ours) | ViT-S/8 | Charades | 10K / 82h | 67.0 | 63.7 | 72.7 | 70.4 | 82.9
INO (Ours) | ViT-S/8 | Kinetics | 300K / 833h | 72.5 | 68.7 | 82.0 | 76.3 | 89.0
Table 3.  Comparisons with state-of-the-art methods on YouTube-VOS 2018 val benchmark. The object classes in the val set are partly overlapped with the _training_ set, therefore the performance is distinguished as “seen” and “unseen” categories. All results are evaluated and reported through the online testing server (Xu et al., 2018). |  |  | Seen | Unseen
---|---|---|---|---
Method | Dataset | Mean | $\mathcal{J}_{m}$ | $\mathcal{F}_{m}$ | $\mathcal{J}_{m}$ | $\mathcal{F}_{m}$
Colorize (Vondrick et al., 2018) | Kinetics | 38.9 | 43.1 | 38.6 | 36.6 | 37.4
CorrFlow†(Lai and Xie, 2019) | OxUvA | 46.6 | 50.6 | 46.6 | 43.8 | 45.6
MAST†(Lai et al., 2020) | YT-VOS | 64.2 | 63.2 | 64.9 | 60.3 | 67.7
CRW (Jabri et al., 2020) | Kinetics | 69.9 | 68.7 | 70.2 | 65.4 | 75.2
DUL (Araslanov et al., 2021) | YT-VOS | 69.9 | 69.6 | 71.3 | 65.0 | 73.5
DUL (Araslanov et al., 2021) | Kinetics | 70.6 | 69.9 | 71.3 | 66.5 | 74.8
DUL (Araslanov et al., 2021) | TrackingNet | 70.7 | 70.2 | 71.9 | 66.3 | 74.5
INO (Ours) | Kinetics | 71.3 | 70.7 | 73.2 | 65.6 | 75.6

###  3.3. In-generative Learning

The out-generative learning leverages the class tokens to capture the high-
level semantic consistency, however, the dense segmentation task requires more
fine-grained semantic information to precisely capture the correspondence.
Therefore, we introduce the in-generative learning on patch tokens of global
crops, which is composed of intra-frame masked image modeling and inter-frame
affinity consistency, as shown in the lower-right part of Fig. 2.

Intra-frame Masked Image Modeling. Inspired by (Bao et al., 2021; Zhou et al.,
2021), we first perform blockwise masking on the input global crops of the
_student_ module (as illustrated in Fig. 2). Specifically, assuming that a
global crop from the $i$-th frame $\textbf{g}^{i}$ is split into $P$ tokens
$\textbf{g}^{i}=\\{g_{j}^{i}\\}_{j=1}^{P}$, we then randomly choose a ratio
$r$ as the proportion of masked tokens and get a random mask
$\textbf{m}\in\\{0,1\\}^{P}$. According to m, the picked $K=P\cdot r$ tokens
$\\{g_{i}|m_{i}=1\\}$ are replaced with a global learnable mask token and get
a corrupted token sequence $\hat{\textbf{g}}^{i}$. After that,
$\hat{\textbf{g}}^{i}$ is sent to the following attention module and
prediction head for categorical distributions output. For the _teacher_
module, the original unmasked token sequence $\textbf{g}^{i}$ is kept as
input. Finally, similar as Eq. 2, we take the corresponding teacher outputs of
the masked tokens as the generation target and calculate the cross-entropy
between them for each global crop in a video clip:

(3)
$\mathcal{L}_{in\\_mim}=\frac{1}{L}\sum_{i=1}^{L}\sum_{j=1}^{P}m_{j}\cdot-\mathcal{T}^{[patch]}_{j}(\textbf{g}^{i})^{T}log\mathcal{S}^{[patch]}_{j}(\hat{\textbf{g}}^{i}).$

Intuitively, with Eq. 3, we force the model to generate the corrupted patches
based on the limited semantic information from the reserved patches. Such
supervision forces the model to achieve the complete and fine-grained
semantics, which is important for recognizing the gradually appearing parts
given incomplete labels in the first frame. For example, the figure of the
person may be incomplete (i.e., corrupted) at the first time of appearance due
to the occlusion or limited shooting angle. The model should possess the
ability to recognize the rest part of a person which may gradually appear in
the following frames, and this is in line with the target of
$\mathcal{L}_{in\\_mim}$.

Inter-frame Affinity Consistency. $\mathcal{L}_{in\\_mim}$ explores the fine-
grained semantic information spatially for each global crop, however, the
temporal fine-grained semantic consistency between frames should also be
considered, therefore, we propose the affinity consistency constrain as
follows.

Given the $i$-th global crop in a video sequence of length $L$, we represent
the $l_{2}$-normalized $d$-dimensional distribution matrix of the masked
tokens from the teacher module as $Q^{i}_{t}\in\mathbbm{R}^{K\times d}$.
Similarly, the corresponding distribution matrix for the student module is
represented as $Q^{i}_{s}\in\mathbbm{R}^{K\times d}$. Then, the affinity
matrix from timestep $i$ to $i+1$ for the teacher outputs is calculated as:

(4) $A_{t}^{i,i+1}=softmax({(Q^{i}_{t}}{Q^{i+1}_{t}}^{T})/\tau_{t}),$

where $A_{t}^{i,i+1}\in\mathbbm{R}^{K\times K}$ and $\tau_{t}$ is the
temperature. Similarly, the corresponding affinity matrix and temperature for
the student outputs are $A_{s}^{i,i+1}$ and $\tau_{s}$, respectively. Then, we
calculate the cross-entropy between these two affinity matrices as follows:

(5)
$\mathcal{L}_{in\\_aff}=\frac{1}{L-1}\sum_{i=1}^{L-1}\sum_{j=1}^{K}-{A_{t}^{i,i+1}[j,:]}^{T}logA_{s}^{i,i+1}[j,:],$

where $A_{s}^{i,i+1}[j,:]$ represents for the $j$-th row vector of the matrix,
which is the softmax normalized cosine similarity between the $j$-th mask
token of frame $i$ and all the $K$ masked tokens of frame $i+1$, i.e., the
correspondence. Intuitively, we intend to learn the fine-grained temporal
correspondence via bootstrapping, which is beneficial for the ultimate goal of
propagating segmentation labels.

###  3.4. Training & Inference Pipeline

In this subsection, we introduce the whole pipeline for INO to achieve
unsupervised learning for VOS.

During the training stage, we start by training the ViT backbone with the raw
data from video recognition datasets Kinetics-400 (Kay et al., 2017) and
Charades (Sigurdsson et al., 2016) without using any human annotation labels.
Our network is trained in a self-supervised manner with learning objectives:

(6)
$\mathcal{L}_{INO}=\mathcal{L}_{out\\_g2g}+\mathcal{L}_{out\\_l2g}+\mathcal{L}_{in\\_mim}+\mathcal{L}_{in\\_aff}.$

To maintain simplicity, here we treat all these terms with equal
contributions. Once the backbone model is trained, we can evaluate directly on
the DAVIS-2017 val (Pont-Tuset et al., 2017) and YouTube-VOS 2018 val (Xu et
al., 2018) without fine-tuning.

During inference, the segmentation label of the first frame is provided and
then propagated toward the following frames based on the similarity between
extracted feature maps. For fair comparison, we use the same label propagation
strategy as (Araslanov et al., 2021; Caron et al., 2021; Jabri et al., 2020;
Xu and Wang, 2021), detailed in the supplementary material.

##  4\. Experiment

Figure 3. Qualitative comparisons on DAVIS-2017 val. We also display the
examples of DUL (Araslanov et al., 2021) and CRW (Jabri et al., 2020). The
frame number is illustrated in the upper-right corner. We mark the salient
parts where our method performs better with red dotted boxes.  Figure 4.
Qualitative comparisons on YouTube-VOS 2018 val. Notably, in the second “hat-
trick” case, we illustrate a hard scenario where the hat is rapidly moving
with highly blurry. CRW (Jabri et al., 2020) lost the hat gradually, while DUL
(Araslanov et al., 2021) mistracks toward the human face. Only our INO
succeeds to track the hat in motion, which shows that our method can precisely
capture the fine-grained correspondence.

###  4.1. Experimental Settings

Datasets. In order to validate the scalability of the proposed INO, we conduct
experiments on two large-scale datasets, including Charades (Sigurdsson et
al., 2016) and Kinetics-400 (Kay et al., 2017). Charades (Sigurdsson et al.,
2016) dataset spans 9848 videos with an average length of 30s and records the
causal everyday activities at home. Kinetics (Kay et al., 2017) dataset
contains significantly more video sequences (around 230K videos with 10s per
video on average). Note that we directly use raw data from the video dataset,
no human annotations are involved during the training process.

Evaluation Metrics. To verify the generalization ability of INO, we benchmark
on two challenging video object segmentation benchmarks: DAVIS-2017 val (Pont-
Tuset et al., 2017) and YouTube-VOS 2018 val (Xu et al., 2018). DAVIS-2017 val
contains $30$ videos in 480p, and YouTube-VOS 2018 val spans 474 videos, and
over $90\%$ of them are in 720p. Following previous works (Araslanov et al.,
2021; Xu and Wang, 2021; Jabri et al., 2020), we use region similarity
($\mathcal{J}$) and contour accuracy ($\mathcal{F}$) as the evaluation metric
(Perazzi et al., 2016).

Implementation Details. Our INO framework adopts ViT as the backbone model.
For fair comparison with the competing methods (Araslanov et al., 2021; Jabri
et al., 2020; Xu and Wang, 2021) that downsample the input resolution for 8
times during inference, we use the ViT-S/8 configuration by default, which
possesses comparable parameters as ResNet-50 (He et al., 2016). For each
iteration, we do in-generative learning with a random probability of $0.5$,
and $r$ is randomly sampled from a uniform distribution from $0.1$ to $0.5$.
The temperature is set as $\tau_{s}=0.1$ and $\tau_{t}=0.04$, separately. The
scale range for global and local crops are $(0.05,0.8)$ and $(0.8,0.95)$,
respectively. The global crops are resized to $224\times 224$ while the local
crops are resized to $64\times 64$. The number of local crops $M$ is set as
$8$, and the video length $L$ is set as $4$. We train INO for 25 epochs on
both Charades and Kinetics-400 with 4 and 8 V100 (16GB) GPUs, respectively.
Previous works (Araslanov et al., 2021; Jabri et al., 2020; Xu and Wang, 2021)
use the last-block output of ResNet for training, while the middle-block
output (e.g., _res 3_ block in (Jabri et al., 2020)) for inference. Similarly,
we use the output of the last layer (i.e., the $12$-th layer) of ViT for
training and empirically use the output of the $7$-th layer for inference.
More implementation details can be found in the supplementary material.

###  4.2. Quantitative Comparisons with State-of-the-art

Results on DAVIS-2017 benchmark. In Table 2, we report the performance
comparisons between our INO and other competing state-of-the-art methods on
DAVIS-2017 val benchmark. In a fair comparison where all the methods use the
large-scale Kinetics dataset for training, our INO significantly outperforms
other state-of-the-art methods by a large margin. For instance, we outperform
the second best VFS (Xu and Wang, 2021) by $3.1\%$ in terms of
$\mathcal{J}\&\mathcal{F}_{m}$( $72.5\%$ vs. $69.4\%$). Notably, MAST (Lai et
al., 2020) and CorrFlow (Lai and Xie, 2019) adopt $2$ times larger image
resolution than ours during inference, which leads to larger memory footprint.
However, our INO still outperforms MAST (Lai et al., 2020) by $7\%$ on
$\mathcal{J}\&\mathcal{F}_{m}$(72.5% vs. 65.5%).

Better Scalability. Scalability is an important criterion for self-supervised
learning methods. However, as shown in Table 2, the performance of CorrFlow,
MAST, and DUL is not positively correlated with the scale of the training
dataset. And the best performance is not achieved on the largest dataset. For
instance, even though the dataset size is two orders of magnitude smaller
($300k$ vs. $4.5k$), the performance of DUL trained with YouTube-VOS is still
higher than Kinetics by $0.6\%$ in $\mathcal{J}\&\mathcal{F}_{m}$score (68.7 %
vs. 69.3 %). Actually, for such methods, the best performance are achieved on
the datasets with higher visual quality and cleaner background, e.g., YouTube-
VOS (Xu et al., 2018), TrackingNet (Muller et al., 2018), and OxUvA (Valmadre
et al., 2018). This demonstrates that the previous methods are sensitive to
the dataset quality and lack of scalability. In contrast, our INO exhibits
strong scalability and robustness owing to the generative learning paradigm,
e.g., the performance boosts by $5.5$% from Charades to Kinetics.

Results on YouTube-VOS 2018 benchmark. Following (Araslanov et al., 2021; Lai
et al., 2020), we additionally evaluate INO on YouTube-VOS 2018 val dataset in
Table 3, which is a more challenging benchmark. Our INO reaches a new state-
of-the-art which improves over DUL (Araslanov et al., 2021) by 1.3% in
$\mathcal{F}_{m}$of the “seen” category and 0.6% in mean score. Compared with
CRW (Jabri et al., 2020) which is also trained on Kinetics, our INO
outperforms by 1.4% in the mean score. As to MAST (Lai et al., 2020) which
adopts 2 times larger resolution and a more advanced two-stage inference
pipeline, i.e., detecting a ROI first and then considering the correspondence
bounded by the ROI, our INO still outperforms by a significant margin ($71.3$%
vs. $64.2$%).

###  4.3. Qualitative Analysis

We visualize the mask propagation results in Fig. 3 and Fig. 4 for DAVIS-2017
val and YouTube-VOS 2018 val, respectively. For better comparison, we also
illustrate the results for DUL (Araslanov et al., 2021) and CRW (Jabri et al.,
2020). We observe that our INO achieves better qualitative results and is
superior in the following aspects:

Robust to Unseen Parts. As illustrated in the first “motorcross-jump” scenario
of Fig. 3, the right leg and back view of the rider is unseen in the given
label of the first frame. The contrastive learning based methods CRW (Jabri et
al., 2020) and DUL (Araslanov et al., 2021) fail to track such unseen parts in
the following sequences, while our INO tracks them successfully (see frame
$15$ and $35$). We attribute this superiority mainly to the in-generative
learning objective, which helps capture the complete semantic structure of the
corrupted parts.

Robust to Deformation. Our INO shows better robustness to deformation compared
with previous methods. For instance, in the “motorcross-jump” scenario of Fig.
3, the back wheel deforms significantly during the motion process, while only
our INO can consistently identify the entire back wheel. The out-generative
learning process fully exploits the semantic consistency between deformed
objects from different frames during training. Intuitively, this supervised
signal improves the robustness of features toward the deformation.

Less Artifacts. During the mask propagation process, the label may shift
toward the background which shares a similar pattern with the target object,
and this is termed as the “bleeding” artifacts in (Araslanov et al., 2021). As
illustrated in the first “motorcycle” case in Fig. 4, both CRW (Jabri et al.,
2020) and DUL (Araslanov et al., 2021) suffer this issue in frame 65 and 85,
while our INO gives a more complete and stable mask even under a noisy
background.

Fine-grained Correspondence. In the second “hat-trick” case of Fig. 4, we
illustrate an extremely hard scenario that requires the ability to precisely
capture the fine-grained details. Specifically, a small hat in high motion is
thrown by the actor. As the label propagates, CRW (Jabri et al., 2020) lost
the hat gradually, and DUL (Araslanov et al., 2021) shifts to the actor’s face
immediately, while only our INO tracks the hat consistently and precisely.

Table 4. Effectiveness of In-N-Out generative learning objectives. All results are evaluated on DAVIS-2017 val benchmark.  | Objective | $\mathcal{J}\&\mathcal{F}_{m}$ | $\mathcal{J}_{m}$ | $\mathcal{J}_{r}$ | $\mathcal{F}_{m}$ | $\mathcal{F}_{r}$
---|---|---|---|---|---|---
Out | $\mathcal{L}_{out\\_g2g}$ | 45.6 | 43.4 | 46.3 | 47.7 | 54.8
$+\mathcal{L}_{out\\_l2g}$ | 54.2 | 51.0 | 56.1 | 57.4 | 64.0
In | $+\mathcal{L}_{in\\_mim}$ | 65.4 | 62.4 | 71.6 | 68.3 | 80.1
$+\mathcal{L}_{in\\_aff}$ | 67.0 | 63.7 | 72.7 | 70.4 | 82.9

###  4.4. Ablation Studies

We investigate the effectiveness of learning objectives in Table 4, and the
influence of training parameters in Fig. 5. The performance trained on
Charades and evaluated on DAVIS-2017 val is reported.

Effectiveness of In-N-Out Generative Learning. In Table 4, we investigate the
effectiveness of In-N-Out generative learning objectives. We set the out-
generative learning between global crops as the baseline configuration and
then add each term gradually. With only out-generative learning between global
crops ($\mathcal{L}_{out\\_g2g}$), the model can achieve 45.6% in
$\mathcal{J}\&\mathcal{F}_{m}$. After adding the out-generative learning
between local and global crops ($\mathcal{L}_{out\\_l2g}$), the
$\mathcal{J}\&\mathcal{F}_{m}$score boosts for 8.6%, which shows that the
high-level semantic inference from local to global crops can significantly
help to improve the performance. With out-generative learning only, the model
achieves a performance of 54.2%. Notably, the performance is further improved
significantly by 11.2% in $\mathcal{J}\&\mathcal{F}_{m}$score after including
the in-generative learning via masked image modeling
($\mathcal{L}_{in\\_mim}$), which shows the importance of fine-grained
structural semantic. Finally, the best performance is achieved after
$\mathcal{L}_{in\\_aff}$ is introduced, which improves the temporal
correspondence via bootstrapping.

Figure 5. Ablation study of training parameters. We report the
$\mathcal{J}\&\mathcal{F}_{m}$score evaluated on DAVIS-2017 val. Our baseline
configuration (the centered one) is: $M=8,L=4,\tau_{t}=0.04,s=0.8$.

Temperature of Affinity Constrain. In $\mathcal{L}_{in\\_aff}$, we use
$\tau_{s}$ and $\tau_{t}$ as the temperature for student and teacher affinity
matrix, separately. We fix the student temperature $\tau_{s}$ as $0.1$ and
change $\tau_{t}$ as $\\{0.02,0.04,0.06\\}$, where smaller $\tau_{t}$ gives
sharper target distributions. As illustrated by the yellow one in Fig. 5,
$\tau_{t}=0.04$ gives a moderate sharpness and performs best.

Sequence Length. We increase the sequence length $L$ as $\\{2,4,6\\}$, and
find that $L=4$ performs best, as illustrated by the orange one in Fig. 5.
Longer sequence length brings larger difference between the paired frames,
however, too much difference (e.g., the object may disappear in the later
frames) incurs the mismatch between the source and target views, which
increases the training noise. Therefore, a moderate sequence length ($L=4$)
gives the best performance.

Number of Local Crops. We vary the local crops number $M$ as $\\{6,8,10\\}$.
More local crops bring more radical high-level semantic inference. As
illustrated by the green one in Fig. 5, $M=8$ gives the best performance,
which is tangibly better than $M=6$ and $M=10$, e.g., $M=10$ leads to a drop
in $\mathcal{J}\&\mathcal{F}_{m}$score by 2.1%. We infer that too many local
crops may lead to overfitting toward the noise, and a moderate $M=8$ is
sufficient.

Scale Threshold for Random Resized Cropping. We use the random resized
cropping which first samples views with scale range $(0.05,s)$ for local crops
and $(s,0.95)$ for global crops, and then resized them to $64\times 64$ and
$224\times 224$, respectively. We vary the threshold $s$ as
$\\{0.4,0.6,0.8\\}$. Larger $s$ leads to more diverse local crops and more
stable global crops containing richer information about the scene. By
observing the gray one in Fig. 5, we find that the performance becomes better
as $s$ increases from $0.4$ to $0.8$. We infer that the global crops with rich
global information are more helpful to the semantic inference from local to
global.

Flipping and Color Jitter.

Table 5. Influence of different configurations of operating _flipping_ and _color jitter_ (F&C).  | Global? | Local? | $\mathcal{J}\&\mathcal{F}_{m}$ | $\mathcal{J}_{m}$ | $\mathcal{J}_{r}$ | $\mathcal{F}_{m}$ | $\mathcal{F}_{r}$
---|---|---|---|---|---|---|---
F&C | - | - | 66.6 | 63.5 | 74.7 | 69.7 | 82.4
✓ | - | 63.6 | 60.8 | 69.5 | 66.5 | 77.9
- | ✓ | 67.0 | 63.7 | 72.7 | 70.4 | 82.9
✓ | ✓ | 66.2 | 63.3 | 73.3 | 69.1 | 82.1

After obtaining global and local crops via _random resized cropping_ , we
empirically perform _flipping_ and _color jitter_ (F&C) randomly only for
local crops. We investigate $4$ configurations in Table 5. We observe that
operating F&C on global crops will reduce the performance. For instance,
compared with not using F&C, the $\mathcal{J}\&\mathcal{F}_{m}$score drops by
3.0% from 66.6% to 63.6% after performing F&C on global crops. We infer that
more stable global crops are preferred for the generation process. Performing
F&C only on local crops provides the best performance on average (67.0% in
$\mathcal{J}\&\mathcal{F}_{m}$score), therefore we take it as the default
configuration.

Figure 6. Failure cases on DAVIS-2017 val (upper) and YouTube-VOS 2018 val
(bottom).

###  4.5. Limitation

We provide failure cases on DAVIS-2017 val and YouTube-VOS 2018 val in Fig. 6.
We observe that the performance tends to be unsatisfactory under the following
challenging scenarios: (i) _Multiple extremely similar instances._ For
instance, the two dogs in case 1 of Fig. 6 are very similar in low-level
vision, therefore the labels are confused during the later time steps. (ii)
_Long-term and large-area occlusion._ As illustrated by case 2 of Fig. 6, the
labels tend to lose the object after the long-term and large-area occlusion.
We can observe that there is still room for improvement in the aforementioned
challenging cases.

##  5\. Conclusion

In this paper, to tackle the challenging unsupervised learning for VOS, we
proposed a simple yet effective framework called In-N-Out (INO) generative
learning. The proposed INO is a novel fully-generative learning framework via
in-view image recovery and out-view image imagination, which integrates both
pixel-level and image-level optimization in a unified framework. Without any
annotation data, we effectively learn robust visual representations in a self-
supervised manner and achieve the new state-of-the-art performance among
unsupervised learning methods for VOS. However, there is still a long way to
go considering the analyzed limitations in § 4.5 and the performance gap
between the unsupervised and the supervised methods. Thus, more effective
algorithms are still required to alleviate this gap. We hope that our efforts
will motivate more researchers and ease future research.

###### Acknowledgements.

Xiao Pan and Zongxin Yang were in part supported by the Fundamental Research
Funds for the Central Universities (No. 226-2022-00087).

## References

  * (1)
  * Araslanov et al. (2021) Nikita Araslanov, Simone Schaub-Meyer, and Stefan Roth. 2021\.  Dense Unsupervised Learning for Video Segmentation.  _Advances in Neural Information Processing Systems_ 34 (2021).
  * Bao et al. (2021) Hangbo Bao, Li Dong, and Furu Wei. 2021.  Beit: Bert pre-training of image transformers.  _arXiv preprint arXiv:2106.08254_ (2021).
  * Carion et al. (2020) Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. 2020.  End-to-end object detection with transformers. In _European conference on computer vision_. Springer, 213–229.
  * Caron et al. (2021) Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. 2021\.  Emerging properties in self-supervised vision transformers. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 9650–9660.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ (2018).
  * Dosovitskiy et al. (2020) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. 2020\.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ (2020).
  * Goyal et al. (2017) Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. 2017.  Accurate, large minibatch sgd: Training imagenet in 1 hour.  _arXiv preprint arXiv:1706.02677_ (2017).
  * Grill et al. (2020) Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. 2020\.  Bootstrap your own latent-a new approach to self-supervised learning.  _Advances in Neural Information Processing Systems_ 33 (2020), 21271–21284.
  * He et al. (2021) Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. 2021\.  Masked autoencoders are scalable vision learners.  _arXiv preprint arXiv:2111.06377_ (2021).
  * He et al. (2020) Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. 2020.  Momentum contrast for unsupervised visual representation learning. In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_. 9729–9738.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep residual learning for image recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 770–778.
  * Jabri et al. (2020) Allan Jabri, Andrew Owens, and Alexei Efros. 2020\.  Space-time correspondence as a contrastive random walk.  _Advances in neural information processing systems_ 33 (2020), 19545–19560.
  * Jeon et al. (2021) Sangryul Jeon, Dongbo Min, Seungryong Kim, and Kwanghoon Sohn. 2021.  Mining better samples for contrastive learning of temporal correspondence. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 1034–1044.
  * Kay et al. (2017) Will Kay, Joao Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijayanarasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, et al. 2017\.  The kinetics human action video dataset.  _arXiv preprint arXiv:1705.06950_ (2017).
  * Lai et al. (2020) Zihang Lai, Erika Lu, and Weidi Xie. 2020.  MAST: A memory-augmented self-supervised tracker. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 6479–6488.
  * Lai and Xie (2019) Zihang Lai and Weidi Xie. 2019.  Self-supervised learning for video correspondence flow.  _arXiv preprint arXiv:1905.00875_ (2019).
  * Liang et al. (2021) Chen Liang, Yu Wu, Tianfei Zhou, Wenguan Wang, Zongxin Yang, Yunchao Wei, and Yi Yang. 2021.  Rethinking cross-modal interaction from a top-down perspective for referring video object segmentation.  _arXiv preprint arXiv:2106.01061_ (2021).
  * Lin et al. (2021) Qin Lin, Nuo Pang, and Zhiying Hong. 2021.  Automated Multi-Modal Video Editing for Ads Video. In _Proceedings of the 29th ACM International Conference on Multimedia_. 4823–4827.
  * Liu et al. (2021) Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. 2021.  Swin transformer: Hierarchical vision transformer using shifted windows. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 10012–10022.
  * Loshchilov and Hutter (2016) Ilya Loshchilov and Frank Hutter. 2016.  Sgdr: Stochastic gradient descent with warm restarts.  _arXiv preprint arXiv:1608.03983_ (2016).
  * Loshchilov and Hutter (2018) Ilya Loshchilov and Frank Hutter. 2018.  Fixing weight decay regularization in adam.  (2018).
  * Miao et al. (2020) Jiaxu Miao, Yunchao Wei, and Yi Yang. 2020.  Memory aggregation networks for efficient interactive video object segmentation. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 10366–10375.
  * Muller et al. (2018) Matthias Muller, Adel Bibi, Silvio Giancola, Salman Alsubaihi, and Bernard Ghanem. 2018.  TrackingNet: A Large-Scale Dataset and Benchmark for Object Tracking in the Wild. In _The European Conference on Computer Vision (ECCV)_.
  * Oh et al. (2019) Seoung Wug Oh, Joon-Young Lee, Ning Xu, and Seon Joo Kim. 2019\.  Video object segmentation using space-time memory networks. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 9226–9235.
  * Perazzi et al. (2016) Federico Perazzi, Jordi Pont-Tuset, Brian McWilliams, Luc Van Gool, Markus Gross, and Alexander Sorkine-Hornung. 2016.  A benchmark dataset and evaluation methodology for video object segmentation. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 724–732.
  * Pont-Tuset et al. (2017) Jordi Pont-Tuset, Federico Perazzi, Sergi Caelles, Pablo Arbeláez, Alex Sorkine-Hornung, and Luc Van Gool. 2017.  The 2017 davis challenge on video object segmentation.  _arXiv preprint arXiv:1704.00675_ (2017).
  * Sigurdsson et al. (2016) Gunnar A Sigurdsson, Gül Varol, Xiaolong Wang, Ali Farhadi, Ivan Laptev, and Abhinav Gupta. 2016.  Hollywood in homes: Crowdsourcing data collection for activity understanding. In _European Conference on Computer Vision_. Springer, 510–526.
  * Touvron et al. (2021) Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. 2021.  Training data-efficient image transformers & distillation through attention. In _International Conference on Machine Learning_. PMLR, 10347–10357.
  * Valmadre et al. (2018) Jack Valmadre, Luca Bertinetto, Joao F Henriques, Ran Tao, Andrea Vedaldi, Arnold WM Smeulders, Philip HS Torr, and Efstratios Gavves. 2018\.  Long-term tracking in the wild: A benchmark. In _Proceedings of the European conference on computer vision (ECCV)_. 670–685.
  * Vondrick et al. (2018) Carl Vondrick, Abhinav Shrivastava, Alireza Fathi, Sergio Guadarrama, and Kevin Murphy. 2018\.  Tracking emerges by colorizing videos. In _Proceedings of the European conference on computer vision (ECCV)_. 391–408.
  * Wang et al. (2020) Ning Wang, Wengang Zhou, and Houqiang Li. 2020.  Contrastive transformation for self-supervised correspondence learning.  _arXiv preprint arXiv:2012.05057_ (2020).
  * Wang et al. (2021b) Wenguan Wang, Tianfei Zhou, Fatih Porikli, David Crandall, and Luc Van Gool. 2021b.  A survey on deep learning technique for video segmentation.  _arXiv preprint arXiv:2107.01153_ (2021).
  * Wang et al. (2019) Xiaolong Wang, Allan Jabri, and Alexei A Efros. 2019\.  Learning correspondence from the cycle-consistency of time. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 2566–2576.
  * Wang et al. (2021a) Yuqing Wang, Zhaoliang Xu, Xinlong Wang, Chunhua Shen, Baoshan Cheng, Hao Shen, and Huaxia Xia. 2021a.  End-to-end video instance segmentation with transformers. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 8741–8750.
  * Xiong et al. (2021) Jianghao Xiong, En-Lin Hsiang, Ziqian He, Tao Zhan, and Shin-Tson Wu. 2021.  Augmented reality and virtual reality displays: emerging technologies and future perspectives.  _Light: Science & Applications_ 10, 1 (2021), 1–30.
  * Xu and Wang (2021) Jiarui Xu and Xiaolong Wang. 2021.  Rethinking self-supervised correspondence learning: A video frame-level similarity perspective. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 10075–10085.
  * Xu et al. (2018) Ning Xu, Linjie Yang, Yuchen Fan, Jianchao Yang, Dingcheng Yue, Yuchen Liang, Brian Price, Scott Cohen, and Thomas Huang. 2018.  Youtube-vos: Sequence-to-sequence video object segmentation. In _Proceedings of the European conference on computer vision (ECCV)_. 585–601.
  * Yang et al. (2019b) Yanchao Yang, Antonio Loquercio, Davide Scaramuzza, and Stefano Soatto. 2019b.  Unsupervised moving object detection via contextual information separation. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 879–888.
  * Yang et al. (2019a) Zongxin Yang, Peike Li, Qianyu Feng, Yunchao Wei, and Yi Yang. 2019a.  Going deeper into embedding learning for video object segmentation. In _Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops_. 0–0.
  * Yang et al. (2020) Zongxin Yang, Yunchao Wei, and Yi Yang. 2020.  Collaborative video object segmentation by foreground-background integration. In _European Conference on Computer Vision_. Springer, 332–348.
  * Yang et al. (2021a) Zongxin Yang, Yunchao Wei, and Yi Yang. 2021a.  Associating objects with transformers for video object segmentation.  _Advances in Neural Information Processing Systems_ 34 (2021), 2491–2502.
  * Yang et al. (2021b) Zongxin Yang, Yunchao Wei, and Yi Yang. 2021b.  Collaborative video object segmentation by multi-scale foreground-background integration.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ (2021).
  * Zhao et al. (2021) Zixu Zhao, Yueming Jin, and Pheng-Ann Heng. 2021.  Modelling neighbor relation in joint space-time graph for video correspondence learning. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 9960–9969.
  * Zhou et al. (2021) Jinghao Zhou, Chen Wei, Huiyu Wang, Wei Shen, Cihang Xie, Alan Yuille, and Tao Kong. 2021.  ibot: Image bert pre-training with online tokenizer.  _arXiv preprint arXiv:2111.07832_ (2021).

##  Appendix A Additional Implementation Details

We provide more training and inference details in this section. The code will
be released upon acceptance.

###  A.1. Training Details

After achieving global and local views via random resized cropping, we
empirically perform random flip and random color jitter only for local crops,
which leads to more stable global crops. Learnable position embedding is
initialized with the resolution of $64\times 64$ and resized to the needed
resolution (determined by the input resolution) with bicubic interpolation.
The architecture of the projection head is the same as (Caron et al., 2021)
and its layer number and output dimension are set as $3$ and $4096$,
respectively. We train our network with adamw optimizer (Loshchilov and
Hutter, 2018) and the weight decay follows the cosine schedule (Loshchilov and
Hutter, 2016) from 0.04 to 0.4. The momentum of EMA is set as $0.996$. We use
the same video data loader as the released code of (Jabri et al., 2020) and
set the frameskip interval for each clip as $8$. Considering the significant
scale difference between these two datasets, we employ different learning rate
schedules. Specifically, for Charades, we linearly warmup the learning rate
for the first 5 epochs till the base value before decaying with a cosine
schedule. The base value is determined by the linear scaling rule (Goyal et
al., 2017): $lr=0.003*batchsize*L/1024$. While for Kinetics-400, we reduce the
linear warmup epochs to $2$ and the learning rate is reduced to
$lr=0.0003*batchsize*L/1024$ since it has significantly more iterations. By
default, we train on 4 V100 (16GB) GPUs with a batchsize of $16$ ($4$ clips
per GPU) for Charades, and a batchsize of $32$ on 8 V100 (16GB) GPUs for
Kinetics-400.

###  A.2. Inference Details

During inference, the given segmentation labels of the first frame are
propagated toward the following frames via the label propagation algorithm.
For fair comparison, we employ the same algorithm as previous methods (Caron
et al., 2021; Araslanov et al., 2021; Jabri et al., 2020; Xu and Wang, 2021).
Specifically, given a $d$-dimensional feature embedding of the target pixel in
the current frame, its cosine similarity w.r.t the first frame and the $N_{c}$
previous context frames is calculated. For each frame, restrict attention (Lai
et al., 2020), which means to only consider the pixels around the target pixel
location with a radius of $N_{r}$, is applied. Then, for all the included
reference pixels, the most similar $N_{k}$ pixels are normalized with a
temperature softmax. The final propagated label for the target pixel is the
weighted combination of the reference pixel labels.

Same as previous works (Araslanov et al., 2021; Xu and Wang, 2021; Lai et al.,
2020), the original image size is kept for inference. The label propagation is
calculated via the patch tokens. The parameters of the label propagation
algorithm on DAVIS-2017 val are $N_{k}=5,N_{c}=10,N_{r}=40$. As to YouTube-VOS
2018 val, we adopt longer context ($N_{c}=20$) and larger radius ($N_{r}=50$)
considering its longer video length in average and larger resolution (720p vs.
480p).

##  Appendix B Additional Ablation Studies

We supplement more detailed ablation studies in this section. The performance
trained on Charades and benchmarked on DAVIS-2017 val is reported.

###  B.1. Ablation of Training Parameters

Figure 7. Additional ablation studies of training parameters. We report the
$\mathcal{J}\&\mathcal{F}_{m}$score evaluated on DAVIS-2017 val. Our baseline
configuration (the centered one) is: $m=0.996,k=4096,N_{l}=3,r_{h}=0.5,PE=64$.

####  B.1.1. Mask Ratio

We perform masked image modeling at ratio $r$. Similar as (Zhou et al., 2021),
we randomly sample $r$ from a uniform distribution from $r_{l}$ to $r_{h}$ at
each iteration. We empirically fix $r_{l}$ as 0.1 and vary $r_{h}$ as
$\\{0.25,0.5,0.75\\}$. As illustrated by the yellow one in Fig. 7, $r_{h}=0.5$
performs better than the rest ones. Larger $r_{h}$ makes the recovery task
harder, but may also include more noise. Therefore a moderate $r_{h}=0.5$ is
sufficient.

####  B.1.2. Position Embedding Resolution

As in (Caron et al., 2021), the learnable position embedding (PE) is
initialized with a fixed resolution, and interpolated to the target input
resolutions. We tried two initial resolutions based on the used global and
local crop size, i.e., $224\times 224$ and $64\times 64$. As shown by the blue
one in Fig. 7, we find that $64\times 64$ gives better performance. This is
reasonable considering that there are much more local crops (8 per frame) than
global clops (1 per frame) during training. Initializing with $64\times 64$
resolution ensures that all the parameters in position embedding are fully
optimized, while initializing with $224\times 224$ leads to the downsampling
of position embedding in most cases (i.e., when forwarding local crops),
therefore the initialized parameters may be optimized in bias.

####  B.1.3. EMA Momentum

In the generic student-teacher framework, the teacher parameter is the
Exponentially Moving Average (EMA) of the student parameters. We investigate
the influence of the momentum $m$ by varying it as $\\{0.996,0.9995\\}$. As
illustrated by the purple one in Fig. 7, we find that $m=0.996$ performs
significantly better.

####  B.1.4. Projection Head Layer Number

We employ the same projection head architecture as (Caron et al., 2021), which
is composed of a $N_{l}$-layer multi-layer perceptron (MLP) and a final fully
connected layer with $k$ dimensions output. We test the influence of the layer
number $N_{l}$ via changing it as $\\{1,2,3,4\\}$. We empirically find that
$N_{l}=1$ gives significantly lower performance, while $N_{l}=2,3,4$ performs
similarly, and $N_{l}=3$ provides the best performance, as shown by the gray
one in Fig. 7.

####  B.1.5. Projection Head Output Dimension

We investigate the influence of projection head output dimension $k$ via
varying it as $\\{2048,4096,8192\\}$ (the orange one in Fig. 7). We observe
that $k=4096$ performs best.

###  B.2. Ablation of Backbone Architecture

Table 6. Influence of backbone architectures. All results are evaluated on DAVIS-2017 val benchmark.  Arch | $\mathcal{J}\&\mathcal{F}_{m}$ | $\mathcal{J}_{m}$ | $\mathcal{J}_{r}$ | $\mathcal{F}_{m}$ | $\mathcal{F}_{r}$
---|---|---|---|---|---
ViT-T/8 | 65.7 | 62.8 | 73.0 | 68.7 | 81.6
ViT-S/8 | 67.0 | 63.7 | 72.7 | 70.4 | 82.9

We investigate the influence of backbones in Table 6. We additionally test
ViT-T/8, which shares comparable parameters as ResNet-18 (He et al., 2016). We
observe that the performance can benefit from the increase of backbone
parameters, _e.g._ , (67.0% _vs._ 65.7% in
$\mathcal{J}\&\mathcal{F}_{m}$score).

##  Appendix C Analysis of Efficiency

Table 7. Comparison of efficiency when training on Kinetics-400. Method | Arch | Param | GPUs | Time
---|---|---|---|---
VFS (Xu and Wang, 2021) | RN-50 | 23M | $8\times 24GB$ | 1week
INO (ours) | ViT-S/8 | 21M | $8\times 16GB$ | 1week

In Table 7, we compare the efficiency of our INO with the second best method
VFS (Xu and Wang, 2021), which belongs to the image-level optimization using
contrastive learning. As illustrated, with the similar training time, our INO
employs a more light-weight backbone (21M _vs._ 24M) and requires less GPU
memories ($8\times 16GB$ _vs._ $8\times 24GB$), while achieves significantly
better performance, _e.g._ , 72.5% _vs._ 69.4% in
$\mathcal{J}\&\mathcal{F}_{m}$score (see Table 2).

##  Appendix D Additional Visualization Examples

We provide more visualization examples of our INO on DAVIS-2017 val and
YouTube-VOS 2018 val in Fig. 8 and Fig. 9, respectively.

Figure 8. Supplemented visualization examples of our INO on DAVIS-2017 val.
Figure 9. Supplemented visualization examples of our INO on YouTube-VOS 2018
val.


# Comparison of Lexical Alignment with a Teachable Robot in Human-Robot and
Human-Human-Robot Interactions

Yuya Asano  Intelligent Systems Program, University of Pittsburgh, USA  Diane
Litman  Intelligent Systems Program, University of Pittsburgh, USA  Department
of Computer Science, University of Pittsburgh, USA  Learning Research and
Development Center, University of Pittsburgh, USA  Mingzhi Yu  Department of
Computer Science, University of Pittsburgh, USA  Nikki Lobczowski  Learning
Research and Development Center, University of Pittsburgh, USA  Timothy Nokes-
Malach  Learning Research and Development Center, University of Pittsburgh,
USA  Department of Psychology, University of Pittsburgh, USA
Adriana Kovashka  Intelligent Systems Program, University of Pittsburgh, USA
Department of Computer Science, University of Pittsburgh, USA  Erin Walker
Intelligent Systems Program, University of Pittsburgh, USA  Department of
Computer Science, University of Pittsburgh, USA  Learning Research and
Development Center, University of Pittsburgh, USA

###### Abstract

Speakers build rapport in the process of aligning conversational behaviors
with each other. Rapport engendered with a teachable agent while instructing
domain material has been shown to promote learning. Past work on lexical
alignment in the field of education suffers from limitations in both the
measures used to quantify alignment and the types of interactions in which
alignment with agents has been studied. In this paper, we apply alignment
measures based on a data-driven notion of shared expressions (possibly
composed of multiple words) and compare alignment in one-on-one human-robot
(H-R) interactions with the H-R portions of collaborative human-human-robot
(H-H-R) interactions. We find that students in the H-R setting align with a
teachable robot more than in the H-H-R setting and that the relationship
between lexical alignment and rapport is more complex than what is predicted
by previous theoretical and empirical work.

##  1 Introduction and Related Work

Alignment is the convergence of behavior among speakers and plays an important
role in designing the strategies of dialogue systems because it is associated
with user engagement (Campano et al., 2015) and task success (Nenkova et al.,
2008; Callejas et al., 2011; Lubold et al., 2018; Kory-Westlund and Breazeal,
2019). However, few studies have looked at how this relationship differs in
multi-party versus dyadic task-oriented dialogues involving humans and a
dialogue agent. This gap prevents us from inferring appropriate alignment
strategies for dialogue agents across different group sizes.

Teachable agents act as peers that learners teach via dialogue. These agents
have been shown to facilitate learning due to the effect of learning by
teaching (Leelawong and Biswas, 2008) and the rapport the agents build with
learners (Gulz et al., 2011). Inspired by theories suggesting that rapport is
tied to verbal and non-verbal alignment (Lubold et al., 2019; Tickle-Degnen
and Rosenthal, 1990), prior educational research has explored relationships
between rapport with agents and various forms of alignment such as lexical
(Rosenthal-von der Pütten et al., 2016; Lubold, 2018) and acoustic-prosodic
(Lubold, 2018; Kory-Westlund and Breazeal, 2019) alignment.

While lexical alignment (the focus of this paper) in educational dialogue has
been an active research area, prior studies are limited by 1) alignment
measures (repetition of single words (Ai et al., 2010; Friedberg et al., 2012;
Lubold, 2018) or manual annotations of semantics (Rosenthal-von der Pütten et
al., 2016)) or 2) dialogue settings (they studied only dyadic interactions
with an agent (Rosenthal-von der Pütten et al., 2016; Lubold, 2018; Sinclair
et al., 2019), dyadic interactions between humans (Michel and Smith, 2017;
Michel and Cappellini, 2019; Michel and O’Rourke, 2019; Sinclair and
Schneider, 2021), or multi-party human interactions (Friedberg et al., 2012)).
Multi-party interactions involving an agent remain to be explored with more
sophisticated automated measures that can deal with the alignment of a
sequence of words.

Therefore, we extend the past work on lexical alignment in educational
dialogue in two ways. First, we view lexical alignment as initiation and
repetition of shared lexical expressions, which are automatically extracted
from dialogue excerpts and can consist of multiple words (Dubuisson Duplessis
et al., 2021). Along with these metrics, we propose another viewpoint,
activeness, which quantifies to what extent a speaker is involved in the
establishment of shared expressions independent of their partner. Second, we
investigate collaborative teaching where two learners co-teach a teachable NAO
robot named Emma. We compare how individual learners align with Emma and how
alignment relates to rapport with her in this human-human-robot (H-H-R)
setting versus in a one-on-one human-robot (H-R) setting. Although, outside of
education, some researchers have also investigated H-H-R interactions (e.g.,
Kimoto et al., 2019), exploring alignment specifically in educational settings
is useful because optimal alignment strategies differ from task to task
(Dubuisson Duplessis et al., 2021). Through our comparisons, this paper
provides the groundwork for designing different alignment strategies for
teachable agents in the H-R and H-H-R settings.

##  2 Methodology

###  2.1 Data Collection

Figure 1: Screenshot of students and Emma in the H-H-R condition.

We recruited 40 undergraduate students from Pittsburgh, USA for an online
study (due to COVID) over Zoom. Emma and the student(s) each had their own
Zoom window (Figure 1) and conversed via speech. Students saw ratio word
problems on a web application and taught them to Emma for 30 minutes. Each
problem consisted of multiple steps, and students had to teach her step-by-
step. Emma was designed to guide them by asking a question or making a
statement relevant to their response even when they made a mistake. Her
responses were pre-authored in Artificial Intelligence Markup Language and
were selected based on pattern matching with students’ utterances. All
students were initially assigned to the H-H-R condition, but they were
assigned to the H-R condition if their partner did not show up. We ended up
with 12 students in the H-R condition and the remaining 28 in the H-H-R
condition to form 14 pairs. In both conditions, students freely interacted
with Emma by pressing and holding a “push to speak” button on the application.
In the H-H-R condition, students were also expected to discuss the problems
with their partners while teaching Emma, while, in the H-R condition, students
had to keep talking to Emma without any discussions with others. An example
H-H-R interaction can be found in Appendix A. We excluded one H-H-R pair from
our analysis because one of the students did not talk to either Emma or the
partner while working on the problems.

After teaching, learners individually answered survey questions about their
perceived rapport with Emma on a six-point Likert scale, ranging from strongly
disagree to strongly agree. The survey used four types of rapport measures
created by Lubold (2018): general rapport measures (three items) based on the
sense of connection from Gratch et al. (2007) and positivity, attention, and
coordination rapport measures (four items each, twelve in total) from Sinha
and Cassell (2015) and Tickle-Degnen and Rosenthal (1990). The latter twelve
items had a higher Cronbach’s $\alpha$ (.856) than the general rapport items
(.839); thus, we used the average of the positivity, attention, and
coordination items to create our rapport metric. The means and standard
deviations of our rapport metric were 4.36 and .882 in the H-R condition, and
4.55 and .572 in the H-H-R condition. One-way ANOVA showed no effect of
conditions on rapport ($F=.704,p=.407,df=36$).

###  2.2 Computing Lexical Alignment

Mean (SD) | H-R (n=12) | H-H-R (n=26)
---|---|---
Utterances |  |
both speakers | 174.8 (27.5) | 59.1 (20.0)
student | 81.3 (13.1) | 27.7 (9.80)
Emma | 93.5 (14.4) | 31.5 (10.4)
Tokens |  |
both speakers | 2919.0 (466.3) | 1147.0 (388.1)
student | 921.0 (228.7) | 473.0 (227.2)
Emma | 1998.0 (335.9) | 673.0 (210.2)
Table 1: Descriptive statistics for H-R dialogues and the two Emma-student
portions of H-H-R dialogues.

We manually transcribed all conversations, instead of using Emma’s automated
speech recognition, because she recorded only while students were holding the
“push to speak” button. Then, because the measures of lexical alignment below
are defined only for dyadic conversations, we manually identified the
responder of each utterance in the H-H-R condition (see Appendix A) to split
each conversation into two Emma-student dialogues and one student-student
dialogue. Table 1 describes the Emma-student dialogue data. Although
individuals in the H-H-R condition spoke less to Emma than in the H-R
condition due to the fixed experiment duration and the dialogue split, this
does not affect our measures because they are normalized by the number of
shared expressions or tokens.

The quantification of lexical alignment in the dialogues111The original
dialogues in the H-R condition and the Emma-student dialogue splits in the
H-H-R condition. in this paper relies on a shared expression, which is “a
surface text pattern at the utterance level that has been produced by both
speakers in a dialogue” (Dubuisson Duplessis et al., 2017). A shared
expression is initiated by speaker $S$ when used by $S$ first and adapted
(thus established as a shared expression) by the dialogue partner later. We
used the alignment measures derived from shared expressions because
mathematical expressions often consist of more than one token, other existing
measures compute only repetition, and these measures are shown to be
predictive of educational outcomes. Our ratio problems contained fractions and
decimals, which cannot be expressed by one word. Indeed, the average lengths
of shared expressions were $1.47\pm.076$ and $1.44\pm.101$ for the H-R and
H-H-R conditions, respectively. Word-based measures such as counting (Nenkova
et al., 2008; Friedberg et al., 2012; Wang et al., 2014), Spearman’s
correlation coefficient (Huffaker et al., 2006), regression models (Reitter et
al., 2006; Ward and Litman, 2007), and vocabulary overlap (Campano et al.,
2014) fail to represent the alignment of phrases containing more than one
word. Other measures address this issue by leveraging n-grams (Michel and
Smith, 2017; Duran et al., 2019) or cross-recurrence quantification analysis
(Fusaroli and Tylén, 2016) but consider only repetitions in the alignment
process as opposed to the measures used in this work (Dubuisson Duplessis et
al., 2017, 2021). Furthermore, Sinclair and Schneider (2021) have found these
measures are correlated with learning and collaboration between human students
in collaborative learning.

We employed the set of speaker-dependent alignment measures out of the ones
proposed by Dubuisson Duplessis et al. (2017, 2021)222We used the associated
tool available at https://github.com/GuillaumeDD/dialign.: Initiated
Expression (IE) and Expression Repetition (ER). IE of speaker $S$ (IE_S)
measures orientation (i.e., (a)symmetry) in the alignment process and is
defined as $\frac{\textrm{\\# expr. initiated by }S}{\textrm{\\# expr.}}$. In
a dialogue between speakers $S1$ and $S2$, the alignment process is symmetric
if $\textrm{IE\\_S1}\approx\textrm{IE\\_S2}\approx.5$ because
$\textrm{IE\\_S1}+\textrm{IE\\_S2}=1$. ER of speaker $S$ (ER_S) captures the
strength of repetition and is defined as $\frac{\textrm{\\# tokens from
}S\textrm{ in new or existing expr.}}{\textrm{\\# tokens from }S}$.

However, IE cannot measure asymmetry or establishment independent of another
speaker because, by definition, if IE_S1 increases, IE_S2 decreases. This
dependence prevents us from observing increased establishment by both
speakers. Therefore, we calculated Expression Initiator Difference (IED)
(Sinclair and Schneider, 2021), which is given by IED
$=|\textrm{IE\\_S1}-\textrm{IE\\_S2}|$. In addition, we propose a new measure:

Expression Establishment by Speaker $S$ (EE_S) measures the activeness of $S$
in the alignment process in terms of the establishment of new shared
expressions. It is given by EE_S $=\frac{\textrm{\\# tokens from }S\textrm{
used to establish new expr.}}{\textrm{\\# tokens from }S}$.

In the example dialogue in Appendix A, there are ten shared expressions in the
Emma-StudentA dialogue split: “that”, “can you”, “can”333Although the
expression “can” is part of the longer expression “can you”, it is counted as
a shared expression because it appeared as a free form in Emma’s last turn
(Dubuisson Duplessis et al., 2017). I.e., it was not part of “can you”.,
“convert”, “the”, “days to”, “days”, “to”, “hours”, and “hours?”. Of those,
Emma started to use three expressions that Student A reused later: “that”,
“can you”, and “can”. Thus, IE_Emma $=\frac{3}{10}$ and IE_student
$=\frac{7}{10}$. These are used to compute IED in the Emma-StudentA dialogue:
IED $=|\frac{3}{10}-\frac{7}{10}|=\frac{2}{5}$. ER_student means the number of
tokens in Student A’s turns that are taken from Emma’s previous turns and
therefore parts of shared expressions (these tokens are italicized in Appendix
A) divided by the total number of tokens Student A spoke to Emma including
punctuations. Student A spoke 33 tokens to Emma and devoted four italicized
tokens—“can you” and two “that”s—to shared expressions. Thus, for Student A,
ER_student $=\frac{4}{33}$. Out of the four, Student A used three tokens to
establish new shared expressions “that” and “can you”, so EE_student
$=\frac{3}{33}=\frac{1}{11}$.

###  2.3 Alignment Hypotheses

This study investigates the following hypotheses:

H1: Individuals in the H-H-R condition align less with Emma than in the H-R
condition. Brennan and Clark (1996) formulated lexical alignment as the
establishment of a shared conceptualization, a conceptual pact. In the H-R
condition, individuals establish conceptual pacts only with Emma, but, in the
H-H-R condition, individuals do so between them through discussion before
talking to Emma (see the discussion between students before talking to her in
Appendix A). This may mean these conceptual pacts are likely to be different
from what Emma initially suggested because humans keep updating them, but Emma
is not accessible to the updated conceptual pacts (in our case, Emma does not
have an ability to intentionally align with humans). Therefore, individuals in
the H-H-R condition may tend to use lexicons outside of shared expressions
with Emma.

H2: Students feel more rapport with Emma when they align with Emma more
(H2-a), she aligns with them more (H2-b), and alignment is more symmetric
(H2-c). Human-human interactions show positive correlations between alignment
and rapport (Lubold et al., 2019; Tickle-Degnen and Rosenthal, 1990; Sinha and
Cassell, 2015). These are bi-directional; people feel a rapport when aligning
with their partners and being aligned by their partners (Chartrand and van
Baaren, 2009). In human-robot interactions, positive relationships between
rapport and non-lexical alignments such as acoustic-prosodic (Lubold, 2018;
Kory-Westlund and Breazeal, 2019) and movement (Choi et al., 2017) have also
been found. We thus expect lexical alignment positively correlates with
rapport in both conditions. We also anticipate a symmetric alignment process
positively correlates with rapport because human-human interactions are more
symmetric than human-agent ones (Dubuisson Duplessis et al., 2021) and past
work increased rapport by imitating human alignment behavior.

H3: Lexical alignment is more strongly correlated with rapport with Emma in
the H-R condition than in the H-H-R condition. As shown in Yu et al. (2019),
Levitan et al. (2012), and Namy et al. (2002), the alignment process in H-H-R
dialogues may also depend on other factors including the gender diversity of
the party. Thus, in the H-H-R condition, lexical alignment alone may not be as
predictive of rapport as in the H-R condition.

##  3 Results and Discussion

Mean (SD) | H-R (n=12) | H-H-R (n=26)
---|---|---
ER_student** | .594 (.052) | .462 (.077)
EE_student | .189 (.033) | .171 (.050)
ER_Emma** | .494 (.031) | .421 (.079)
EE_Emma* | .087 (.024) | .119 (.037)
IED | .155 (.111) | .158 (.127)
Table 2: Descriptive statistics of lexical alignment measures. Measures marked
with * and ** are significantly different across conditions at $p<.05$ and
$p<.01$ (two-tailed), respectively.

#### Individual alignment across H-R and H-H-R conditions (H1).

We tested H1 by comparing means of ER_student and EE_student across conditions
with one-way ANOVA. Table 2 partly supports H1. Individuals in the H-R
condition repeated shared expressions (i.e., higher ER_student) more than in
the H-H-R condition, but they were equally likely to establish shared
expressions (i.e., no difference in EE_student) across conditions.

Estimate of $\beta_{3}$ (p-value) | ER_student | EE_student | ER_Emma | EE_Emma | IED
---|---|---|---|---|---
Rapport | -0.54 (.901) | 9.09 (.171) | 3.10 (.652) | -0.83 (.928) | 3.72 (.057)
Table 3: Coefficients of interaction terms ($\beta_{3}$). Pearson’s r (p-value) | ER_student | EE_student | ER_Emma | EE_Emma | IED
---|---|---|---|---|---
Rapport | -.315 (.054) | -.331* (.043) | .214 (.198) | .343* (.035) | -.573** (.000)
Table 4: Pearson’s correlations between alignment measures and rapport. Correlations marked with * and ** are significant at $p<.05$ and $p<.01$ (2-tailed), respectively. Pearson’s r | H-R (n=12) | H-H-R (n=26)
---|---|---
ER_student | -.145 | -.406
EE_student | -.457 | -.285
ER_Emma | .008 | .461
EE_Emma | .195 | .407
IED | -.723 | -.529
Table 5: Comparison of Pearson’s correlations between alignment measures and
rapport across conditions.

#### Correlations of alignment with rapport across conditions (H2 and H3).

To test H2 and H3, first, we fit the regression equation with an interaction
between the conditions and an alignment measure:
$R=\beta_{0}+\beta_{1}*HHR+\beta_{2}*A+\beta_{3}*HHR*A$ where R is the rapport
measure, A is an alignment measure, and HHR is 1 for students in the H-H-R
condition; otherwise 0. Table 3 shows that $\beta_{3}$ is not significant for
none of the alignment measures, meaning that the correlations between rapport
and alignment are in the same direction regardless of the conditions.

Therefore, we used all data to compute Pearson’s correlations between rapport
and alignment (see Table 4). The significant negative correlation between
rapport and IED supports H2-c. H2-b is not fully supported because, although
EE_Emma is correlated positively with rapport, ER_Emma is not. In addition,
surprisingly, we found evidence for the opposite of H2-a; EE_student has a
negative correlation with rapport. Further analysis revealed IE_Emma is
significantly negatively correlated with rapport ($r=-.490,p=.002$). This
means students felt less rapport when they established more shared expressions
relative to Emma and aligns with the findings on EE.

Finally, we compared Pearson’s r between lexical alignment and rapport in the
two conditions using Fisher transformation (Snedecor and Cochran, 1980) to
test H3. It was not validated because there was no significant difference
between the two conditions in Table 5.

These results may be because perceived success in communication with Emma
characterized by her accidental alignment leads to high rapport and low
alignment by students. As Branigan et al. (2010) and Dubuisson Duplessis et
al. (2017) reported, students might have (either consciously or unconsciously)
expected they should establish shared expressions more than Emma due to her
limited linguistic capacity. Thus, they might have started with an asymmetric
alignment process. When Emma was stuck, they might have kept this strategy
because they thought she did not understand them, resulting in decreased
rapport. In contrast, as Emma established new shared expressions by accident,
students might have thought she was following new information like humans,
that she cared what they said, and that they were in sync, leading to more
positivity, attention, and coordination rapport, respectively Tickle-Degnen
and Rosenthal (1990). They may have also changed their alignment strategy to a
more symmetric one (i.e., decreased alignment by students) that they usually
use while interacting with humans.

###  3.1 Limitations

This study has several limitations. First, the limited number of participants
(38 in total) might limit the detection of all correlations. Moreover, the
comparison between the H-R and H-H-R conditions has low statistical power
because the H-R condition had fewer than half of the participants in the H-H-R
condition. It might have been biased because the assignment to the conditions
was not fully random as well. Next, alignment measures may need contextual
adjustments. For example, one math problem included both “three hours” and
“three-fortieths of battery”. Although “three” in these numbers refers to
different entities, our measures saw it as a shared expression. Finally, some
lexicons came from the problem prompt rather than the group conversation.

##  4 Conclusion

We examined relationships between lexical alignment and rapport with a
teachable agent in one-on-one (H-R) and collaborative (H-H-R) teaching. Our
methods expand prior literature by comparing alignment behavior in H-R and
H-H-R settings and extending recent work by Dubuisson Duplessis et al. (2021)
to the speaker-level act of activeness in the alignment process. Our results
imply learners’ lexical alignment with teachable agents may not always
increase rapport with a teachable agent, unlike predictions from alignment
theories (Lubold et al., 2019; Tickle-Degnen and Rosenthal, 1990) largely
based on human-human interactions. Future work can expand our work by looking
at the role of H-H portions of H-H-R interactions in their H-R portion and the
effect of miscommunication as an intermediate variable on the negative
correlations between rapport and learners’ alignment and by extending the
measures to multi-party settings without disentanglement.

## Acknowledgements

We would like to thank anonymous reviewers for their thoughtful comments on
this paper. This work was supported by Grant No. 2024645 from the National
Science Foundation, Grant No. 220020483 from the James S. McDonnell
Foundation, and a University of Pittsburgh Learning Research and Development
Center internal award.

## References

  * Ai et al. (2010) Hua Ai, Rohit Kumar, Dong Nguyen, Amrut Nagasunder, and Carolyn P. Rosé. 2010\.  Exploring the effectiveness of social capabilities and goal alignment in computer supported collaborative learning.  In _Proceedings of the 10th International Conference on Intelligent Tutoring Systems - Volume Part II_ , ITS’10, page 134–143, Berlin, Heidelberg. Springer-Verlag.
  * Branigan et al. (2010) Holly P. Branigan, Martin J. Pickering, Jamie Pearson, and Janet F. McLean. 2010\.  Linguistic alignment between people and computers.  _Journal of Pragmatics_ , 42(9):2355–2368.  How people talk to Robots and Computers.
  * Brennan and Clark (1996) Susan E. Brennan and Herbert H. Clark. 1996.  Conceptual pacts and lexical choice in conversation.  _Journal of Experimental Psychology: Learning, Memory, and Cognition_ , 22:1482–1493.
  * Callejas et al. (2011) Zoraida Callejas, David Griol, and Ramón López-Cózar. 2011.  Predicting user mental states in spoken dialogue systems.  _EURASIP Journal on Advances in Signal Processing_ , 2011(1):1–21.
  * Campano et al. (2014) Sabrina Campano, Jessica Durand, and Chloé Clavel. 2014.  Comparative analysis of verbal alignment in human-human and human-agent interactions.  In _Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14)_ , pages 4415–4422, Reykjavik, Iceland. European Language Resources Association (ELRA).
  * Campano et al. (2015) Sabrina Campano, Caroline Langlet, Nadine Glas, Chloé Clavel, and Catherine Pelachaud. 2015.  An eca expressing appreciations.  In _2015 International Conference on Affective Computing and Intelligent Interaction (ACII)_ , pages 962–967.
  * Chartrand and van Baaren (2009) Tanya L. Chartrand and Rick van Baaren. 2009.  Chapter 5 human mimicry.  volume 41 of _Advances in Experimental Social Psychology_ , pages 219–274. Academic Press.
  * Choi et al. (2017) Mina Choi, Rachel Kornfield, Leila Takayama, and Bilge Mutlu. 2017.  Movement matters: Effects of motion and mimicry on perception of similarity and closeness in robot-mediated communication.  In _Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems_ , CHI ’17, page 325–335, New York, NY, USA. Association for Computing Machinery.
  * Dubuisson Duplessis et al. (2017) Guillaume Dubuisson Duplessis, Chloé Clavel, and Frédéric Landragin. 2017.  Automatic measures to characterise verbal alignment in human-agent interaction.  In _Proceedings of the 18th Annual SIGdial Meeting on Discourse and Dialogue_ , pages 71–81, Saarbrücken, Germany. Association for Computational Linguistics.
  * Dubuisson Duplessis et al. (2021) Guillaume Dubuisson Duplessis, Caroline Langlet, Chloé Clavel, and Frédéric Landragin. 2021.  Towards alignment strategies in human-agent interactions based on measures of lexical repetitions.  _Language Resources and Evaluation_ , 55(2):353–388.
  * Duran et al. (2019) Nicholas Duran, Alexandra Paxton, and Riccardo Fusaroli. 2019.  Align: Analyzing linguistic interactions with generalizable tech niques-a python library.  _Psychological Methods_ , 24(4):419–438.
  * Friedberg et al. (2012) Heather Friedberg, Diane Litman, and Susannah B. F. Paletz. 2012.  Lexical entrainment and success in student engineering groups.  In _2012 IEEE Spoken Language Technology Workshop (SLT)_ , pages 404–409.
  * Fusaroli and Tylén (2016) Riccardo Fusaroli and Kristian Tylén. 2016.  Investigating conversational dynamics: Interactive alignment, interpersonal synergy, and collective task performance.  _Cognitive science_ , 40(1):145–171.
  * Gratch et al. (2007) Jonathan Gratch, Ning Wang, Jillian Gerten, Edward Fast, and Robin Duffy. 2007.  Creating rapport with virtual agents.  In _Intelligent Virtual Agents_ , pages 125–138, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * Gulz et al. (2011) Agneta Gulz, Magnus Haake, and Annika Silvervarg. 2011.  Extending a teachable agent with a social conversation module: Effects on student experiences and learning.  In _Proceedings of the 15th International Conference on Artificial Intelligence in Education_ , AIED’11, page 106–114, Berlin, Heidelberg. Springer-Verlag.
  * Huffaker et al. (2006) David Huffaker, Joseph Jorgensen, Francisco Iacobelli, Paul Tepper, and Justine Cassell. 2006.  Computational measures for language similarity across time in online communities.  In _Proceedings of the Analyzing Conversations in Text and Speech_ , pages 15–22, New York City, New York. Association for Computational Linguistics.
  * Kimoto et al. (2019) Mitsuhiko Kimoto, Takamasa Iio, Michita Imai, and Masahiro Shiomi. 2019.  Lexical entrainment in multi-party human–robot interaction.  In _Social Robotics_ , pages 165–175, Cham. Springer International Publishing.
  * Kory-Westlund and Breazeal (2019) Jacqueline M. Kory-Westlund and Cynthia Breazeal. 2019.  Exploring the effects of a social robot’s speech entrainment and backstory on young children’s emotion, rapport, relationship, and learning.  _Frontiers in Robotics and AI_ , 6.
  * Leelawong and Biswas (2008) Krittaya Leelawong and Gautam Biswas. 2008.  Designing learning by teaching agents: The betty’s brain system.  _Int. J. Artif. Intell. Ed._ , 18(3):181–208.
  * Levitan et al. (2012) Rivka Levitan, Agustín Gravano, Laura Willson, S̆tefan Beŭus̆, Julia Hirschberg, and Ani Nenkova. 2012.  Acoustic-prosodic entrainment and social behavior.  In _Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 11–19, Montréal, Canada. Association for Computational Linguistics.
  * Lubold (2018) Nichola Lubold. 2018.  _Producing Acoustic-Prosodic Entrainment in a Robotic Learning Companion to Build Learner Rapport_.  Ph.D. thesis, Arizona State University.
  * Lubold et al. (2018) Nichola Lubold, Erin Walker, Heather Pon-Barry, and Amy Ogan. 2018.  Automated pitch convergence improves learning in a social, teachable robot for middle school mathematics.  In _Artificial Intelligence in Education_ , pages 282–296, Cham. Springer International Publishing.
  * Lubold et al. (2019) Nichola Lubold, Erin Walker, Heather Pon-Barry, and Amy Ogan. 2019.  Comfort with robots influences rapport with a social, entraining teachable robot.  In _Artificial Intelligence in Education_ , pages 231–243, Cham. Springer International Publishing.
  * Michel and Cappellini (2019) Marije Michel and Marco Cappellini. 2019.  Alignment during synchronous video versus written chat l2 interactions: A methodological exploration.  _Annual Review of Applied Linguistics_ , 39:189–216.
  * Michel and O’Rourke (2019) Marije Michel and Breffni O’Rourke. 2019.  What drives alignment during text chat with a peer vs. a tutor? insights from cued interviews and eye-tracking.  _System_ , 83:50–63.  Special Edition on the Work of Professor Stephen Bax.
  * Michel and Smith (2017) Marije Michel and Bryan Smith. 2017.  _Measuring lexical alignment during L2 chat interaction: An eye-tracking study_, pages 244–267. Taylor and Francis.
  * Namy et al. (2002) Laura L. Namy, Lynne C. Nygaard, and Denise Sauerteig. 2002.  Gender differences in vocal accommodation:: The role of perception.  _Journal of Language and Social Psychology_ , 21(4):422–432.
  * Nenkova et al. (2008) Ani Nenkova, Agustín Gravano, and Julia Hirschberg. 2008.  High frequency word entrainment in spoken dialogue.  In _Proceedings of ACL-08: HLT, Short Papers_ , pages 169–172, Columbus, Ohio. Association for Computational Linguistics.
  * Reitter et al. (2006) David Reitter, Frank Keller, and Johanna D. Moore. 2006.  Computational modelling of structural priming in dialogue.  In _Proceedings of the Human Language Technology Conference of the NAACL, Companion Volume: Short Papers_ , pages 121–124, New York City, USA. Association for Computational Linguistics.
  * Rosenthal-von der Pütten et al. (2016) Astrid M. Rosenthal-von der Pütten, Carolin Straßmann, and Nicole C. Krämer. 2016.  Robots or agents – neither helps you more or less during second language acquisition.  In _Intelligent Virtual Agents_ , pages 256–268, Cham. Springer International Publishing.
  * Sinclair et al. (2019) Arabella Sinclair, Kate McCurdy, Christopher G Lucas, Adam Lopez, and Dragan Gaševic. 2019.  Tutorbot corpus: Evidence of human-agent verbal alignment in second language learner dialogues.  _International Educational Data Mining Society_.
  * Sinclair and Schneider (2021) Arabella J Sinclair and Bertrand Schneider. 2021.  Linguistic and gestural coordination: Do learners converge in collaborative dialogue?.  _International Educational Data Mining Society_.
  * Sinha and Cassell (2015) Tanmay Sinha and Justine Cassell. 2015.  We click, we align, we learn: Impact of influence and convergence processes on student learning and rapport building.  In _Proceedings of the 1st Workshop on Modeling INTERPERsonal SynchrONy And InfLuence_ , INTERPERSONAL ’15, page 13–20, New York, NY, USA. Association for Computing Machinery.
  * Snedecor and Cochran (1980) G.W. Snedecor and W.G. Cochran. 1980.  _Statistical Methods_ , seventh edition.  Iowa State University Press.
  * Tickle-Degnen and Rosenthal (1990) Linda Tickle-Degnen and Robert Rosenthal. 1990.  The nature of rapport and its nonverbal correlates.  _Psychological Inquiry_ , 1(4):285–293.
  * Wang et al. (2014) Yafei Wang, David Reitter, and John Yen. 2014.  A model to qualify the linguistic adaptation phenomenon in online conversation threads: Analyzing priming effect in online health community.  In _Proceedings of the Fifth Workshop on Cognitive Modeling and Computational Linguistics_ , pages 55–62, Baltimore, Maryland, USA. Association for Computational Linguistics.
  * Ward and Litman (2007) Arthur Ward and Diane J Litman. 2007.  Automatically measuring lexical and acoustic/prosodic convergence in tutorial dialog corpora.
  * Yu et al. (2019) Mingzhi Yu, Diane Litman, and Susannah Paletz. 2019.  Investigating the relationship between multi-party linguistic entrainment, team characteristics and the perception of team social outcomes.  In _The Thirty-Second International Flairs Conference_.

##  Appendix A Sample Dialogue and Lexical Alignment

Speaker |  Utterance | Responder
---|---|---
Emma: |  Now that I know how long one battery will last, can you help me figure out how many batteries I need total? | Student A
Student B: |  Oh, okay. | Student A
Student A: |  Okay. Next … | Student B
Student B: |  Okay. | Student A
Student A: |  So one whole battery lasts three and three quarters of an hour. | Student B
Student B: |  Three and three quarters of an hour. Oh my gosh. Emma, you’re making this difficult on us. | Student A
Student A: |  I think we need her… Oh man. | Student B
Student B |  Because it’s in days now. So she has to figure out… | Student A
Student A: |  You have to do like dimensional analysis. | Student B
Student B |  I think she… Yeah. She has to convert days to hours. I think that might be the easiest thing for her. | Student A
Student A: |  Okay. | Student B
Student B: |  So she has to divide… | Student A
Student A: |  Wait, is she going to remember that? | Student B
Student B: |  Oh, I don’t know. | Student A
Student A: |  Okay. I’m going to ask if she knows how to convert days to hours. | Student B
Student B: |  Okay. | Student A
Student A: |  Okay, Emma. Can you convert the number of days to the number of hours? | Emma
Emma: |  So I know how long I’ll be gone in days, but how long the battery lasts is in hours. So first I should change the days to hours? | Student A
Student A: |  Yes, Emma. That’s correct. | Emma
Emma: |  So I can convert two and three quarters to an improper fraction, eleven over four. And then I can multiply it by twenty four hours? | Student A
Student B: |  She did all the work. | Student A
Student A: |  Yes, Emma. That’s correct. | Emma
Table 6: Lexical alignment in the Emma-studentA portion of the dialogue
(bolded utterances). A responder is a speaker who responded to the utterance.
Speakers initiated colored but not italicized expressions and repeated the
italicized ones. Contractions were tokenized as two tokens (e.g., That’s to
“That” and “’s”). Punctuation was treated as one token but did not constitute
a shared expression by itself.