# Learning Audio-Visual Dereverberation

Changan Chen1,2 Wei Sun1 David Harwath1 Kristen Grauman1,2
1UT Austin 2Facebook AI Research

###### Abstract

Reverberation from audio reflecting off surfaces and objects in the
environment not only degrades the quality of speech for human perception, but
also severely impacts the accuracy of automatic speech recognition. Prior work
attempts to remove reverberation based on the audio modality only. Our idea is
to learn to dereverberate speech from audio-visual observations. The visual
environment surrounding a human speaker reveals important cues about the room
geometry, materials, and speaker location, all of which influence the precise
reverberation effects in the audio stream. We introduce Visually-Informed
Dereverberation of Audio (VIDA), an end-to-end approach that learns to remove
reverberation based on both the observed sounds and visual scene. In support
of this new task, we develop a large-scale dataset that uses realistic
acoustic renderings of speech in real-world 3D scans of homes offering a
variety of room acoustics. Demonstrating our approach on both simulated and
real imagery for speech enhancement, speech recognition, and speaker
identification, we show it achieves state-of-the-art performance and
substantially improves over traditional audio-only methods. Project page:
http://vision.cs.utexas.edu/projects/learning-audio-visual-dereverberation.

##  1 Introduction

Audio reverberation occurs when multiple reflections from surfaces and objects
in the environment build up then decay, altering the original audio signal.
While reverberation bestows a realistic sense of spatial context, it also can
degrade a listener’s experience. In particular, the quality of human speech is
greatly affected by reverberant environments—as illustrated by how difficult
it can be to parse the words of a family member speaking loudly from another
room in the house, a tour guide describing the artwork down the hall of a
magnificent cavernous cathedral, or a colleague participating in a Zoom call
from a cafe. Consistent with the human perceptual experience, automatic speech
recognition (ASR) systems noticeably suffer when given reverberant speech
input [32, 69, 60, 24, 65, 14]. Thus there is great need for intelligent
_dereverberation_ algorithms that can strip away reverb effects for speech
enhancement, recognition, and other downstream tasks, which could in turn
benefit many applications in teleconferencing, assistive hearing devices,
augmented reality, and video indexing.

The audio community has made steady progress devising machine learning
solutions to tackle speech dereverberation [14, 29, 54, 24, 66, 70, 59]. The
general approach is to take a reverberant speech signal, usually represented
with a Short-Time Fourier Transform (STFT) spectrogram, and feed it as input
to a model that estimates a clean version of the signal with the reverberation
removed. Past approaches have tackled this problem with signal processing and
statistical techniques [45, 46], while many modern approaches are based on
neural networks that learn a mapping from reverberant to clean spectrograms
[24, 14, 15]. To our knowledge, all existing models for dereverberation rely
purely on audio. Unfortunately this often underconstrains the dereverberation
task since the latent parameters of the recording space are not discernible
from the audio alone.

However, we observe that in many practical settings of interest—video
conferencing, augmented reality, Web video indexing—reverberant audio is
naturally accompanied by a visual (video) stream. Importantly, the visual
stream offers valuable cues about the room acoustics affecting reverberation:
where are the walls, how are they shaped, where is the human speaker, what is
the layout of major furniture, what are the room’s dominant materials (which
affect absorption), and even what is the facial appearance and/or body shape
of the person speaking (since body shape determines the acoustic properties of
a person’s speech, and reverb time is frequency dependent). For example,
reverb is typically stronger when the speaker is further away; speech is more
reverberant in a large church or hallway; heavy carpet absorbs more sound. See
Figure 1.

Figure 1: Visual cues reveal key factors influencing reverb effects on human
speech audio. For example, these audio speech samples (depicted as waveforms
and spectrograms) are identical lexically, but have very different
reverberation properties owing to their differing environments. In the church,
reverb is strong, in the classroom it is less, and when the speaker is distant
from the camera it is again more evident. We propose _audio-visual
dereverberation_ to learn from both modalities how to strip away reverb
effects, thereby enhancing speech quality, recognition, and speaker
identification.

Our idea is to learn to dereverberate speech from audio-visual observations.
In this task, the input is reverberant speech and visual observations of the
environment surrounding the human speaker, and the output is a prediction of
the clean source audio. To tackle this problem, there are two key technical
challenges. First, how to model the multi-modal dereverberation process in
order to infer the latent clean audio. Second, how to secure appropriate
training data spanning a variety of physical environments for which we can
sample speech with known ground truth (non-reverberant, anechoic) audio. The
latter is also non-trivial because ordinary audio/video recordings are
themselves corrupted by reverberation but lack the ground truth source signal
we wish to recover.

For the modeling challenge, we introduce an end-to-end approach called
Visually-Informed Dereverberation of Audio (VIDA). VIDA consists of a Visual
Acoustics Network (VAN) that learns reverberation properties of the room
geometry, object locations, and speaker position. Coupled with a multi-modal
UNet dereverberation module, it learns to remove the reverberations from a
single-channel audio stream. In addition, we propose an audio-visual (AV)
matching loss to enforce consistency between the visually-inferred
reverberation features and those inferred from the audio signal. We leverage
the outputs of our model for multiple downstream tasks: speech enhancement,
speech recognition, and speaker identification.

Next, to address the training data challenge, we develop a new large-scale
audio-visual dataset using SoundSpaces [7], a 3D simulator for real-world
scanned environments that allows both visual and acoustic rendering. Our data
approach inserts “clean" audio voices together with a 3D humanoid model at
various positions within an array of indoor environments, then samples the
images and properly reverberating audio when placing the receiver microphone
and camera at other positions in the same house. This strategy allows sampling
realistic audio-visual instances coupled with ground truth raw audio to train
our model, and it has the added benefit of allowing controlled studies that
vary the parameters of the capture setting. As we will show, the data also
supports sim2real transfer for applying our model to real audio-visual
observations.

Our main contributions are to 1) present the task of audio-visual
dereverberation, 2) address it with a new multi-modal modeling approach and a
novel reverb-visual matching loss, 3) provide a benchmark evaluation framework
built on SoundSpaces as well as real data, and 4) demonstrate the utility of
AV dereverberation for multiple practical tasks. We first train and evaluate
our model on 82 large-scale real-world environments—each a multi-room home
containing a variety of objects—coupled with speech samples from the
LibriSpeech dataset [49]. We consider both near-field and far-field settings
where the human speaker is in-view or quite far from the camera, respectively.
The proposed model outperforms methods restricted to the audio stream, and
improves the state of the art for multiple tasks with speech enhancement. We
also show that our model trained in simulation can transfer directly to real-
world data. Overall, our work shows the potential for speech enhancement
models to leverage room acoustics by seeing the 3D environment.

##  2 Related Work

#### Audio dereverberation and speech enhancement.

Audio dereverberation and speech enhancement have a long and rich literature
[47, 39, 46, 32, 4]. While dereverberation can be done with microphone arrays,
we focus on single audio channel approaches, which require fewer assumptions
about the input data. Recent deep learning methods achieve promising results
to dereverberate [24, 66, 70, 14, 69, 59], denoise [67, 15, 59], or separate
[26, 56] the audio stream using audio input alone, and such enhancements can
improve downstream speech recognition [33, 32] and speaker recognition [54].
Acoustic simulations can provide data augmentation during training [32, 24,
33, 69]. Accounting for environmental effects on reverb, some work targets
“room-aware" deep audio features capturing reverberation properties (e.g.,
RT60) [29], or injects reverberation effects from a different room via
acoustic matching [58]. To our knowledge, the only prior work drawing on the
_visual_ stream to infer dereverberated audio is limited to using lip regions
on near-field faces to first separate out distractor sounds [61], and does not
model anything about the visual scene for dereverberation purposes. In
contrast, our model accounts for the full visual scene, far-field speech
sources, and even out-of-view speakers. Our approach is the first to learn
visual room acoustics for dereverberation, and it yields state-of-the-art
results with direct benefits for multiple downstream tasks.

#### Visual understanding of room acoustics.

The room impulse response (RIR) is the transfer function capturing the room
acoustics for arbitrary source stimuli; once convolved with a sound waveform,
it produces the sound of that source in the context of the particular physical
space. While traditionally measured with specialized equipment in the room
itself [55, 27] or else simulated with sound propagation models (e.g.,
geometric [2, 7] or wave-based [42]), recent work explores estimating an RIR
from an input image using CNNs [34] or conditional GANs [53] in order to
simulate reverberant sound for a given environment. Video-based methods have
also explored ways to lift monaural audio into its spatialized (binaural,
ambisonic) counterpart in order to create an immersive audio experience for
human listeners [41, 18, 36]. Such methods share our interest in learning
visual properties of a scene that influence the audio channel. However, unlike
any of the above methods, rather than generate spatialized audio to benefit
human listeners in augmented or virtual reality, our goal is to dereverberate
audio—removing the effects of the room acoustics— to benefit automatic speech
analysis. In addition, prior methods use imagery taken at camera positions at
an unknown offset from the microphone, i.e., conflating all RIRs for a scene
with one image, which limits them to a coarse characterization of the
environment [38, 30, 43]. In contrast, our data and model align the camera and
microphone to capture novel fine-grained audio-visual properties, including
the human speaker’s location with respect to the microphone when the speaker
is in view.

#### Audio-visual navigation and realistic simulations.

Recent work in embodied AI explores how vision and sound together can help
agents move intelligently in 3D environments. Driven in part by new tools for
audio-visual (AV) simulations in realistic scanned environments [7], new
research develops deep reinforcement learning approaches to train agents to
navigate to sounding objects [7, 17, 6, 8], explore unmapped environments
[10], or move around to better separate multiple overlapping sounds in a house
[37]. Our work also leverages state-of-the-art AV simulations for learning,
but our objective and models are entirely different. Rather than train virtual
robots to move intelligently, our aim is to clean reverberant audio for better
speech analysis.

#### Audio-visual learning from video.

Multi-modal video understanding has experienced a resurgence of work in the
vision, audio, and machine learning literature in recent years. This includes
exciting advances in self-supervised cross-modal feature learning from video
[40, 3, 35, 20], localizing objects in video with both sight and sound [28],
and audio-visual source separation [13, 48, 21, 68, 1, 19]. None of these
methods address speech deverberation.

##  3 The Audio-Visual Dereverberation Task

We introduce the novel task of audio-visual dereverberation. In this task, a
speaker (or other sound source) and a listener are situated in a 3D
environment, such as the interior of a house. The speaker—whose location is
unknown to the listener—produces a speech waveform $A_{s}$. A superposition of
the direct sound and the reverb is captured by the listener, denoted $A_{r}$.
The reverberant speech $A_{r}$ can be modeled as the convolution of the
anechoic source waveform $A_{s}$ with the room impulse response (RIR) $R$,
i.e. $A_{r}(t)=A_{s}(t)*R(t)$ [47]. $R$ is a function of the environment’s
geometry, the materials that make up the environment, and the relative
positioning of the speaker and the listener. It is possible in principle to
measure the RIR $R$ for a real-world environment, but doing so can be
impractical when the source and listener are able to move around or must cope
with different environments. Furthermore, in the common scenario where we want
to process video captured in environments to which we have no physical access,
measuring the RIR is simply impossible.

Crucially to our task, we consider an alternative source of information about
the environment: vision. We assume the listener has an RGB-D observation of
its surroundings, obtained from a RGB-D camera or an RGB camera coupled with
single-image depth estimation [12, 22]. Intuitively, we should be able to
leverage the information about the environment’s geometry and material
composition that is implicit in the visual stream—as well as the location of
the speaker (if visible)—to estimate its reverberant characteristics. We
anticipate that these cues can inform an estimate of the room acoustics, and
thus the clean source waveform. Given the RGB $I_{r}$ and depth image $I_{d}$
captured by the listener from its current vantage point, the task is to
predict the source waveform $A_{s}$ from the images and reverberant audio:
$\hat{A_{s}}(t)=f_{p}([I_{r},I_{d},A_{r}(t)])$. This setting represents common
real-world scenarios previously discussed, and poses new challenges for speech
enhancement and recognition.

##  4 Dataset Curation

For the proposed task, obtaining the right training data is itself a
challenge. Existing video data contains reverberant audio but lacks the ground
truth anechoic audio signal, and existing RIR datasets [38, 30, 43] do not
have images paired with the microphone position. We introduce both real and
simulated datasets to enable reproducible research on audio-visual
deverberation.

#### 3D environments and audio simulator.

First we introduce a large-scale dataset in which we couple real-world visual
environments with state-of-the-art audio simulations accurately capturing the
environments’ spatial effects on real samples of recorded speech. We want our
dataset to allow control of a variety of physical environments, the positions
of the listener/camera and sources, and the speech content of the sources—all
while maintaining both the observed reverberant $A_{r}(t)$ and ground truth
anechoic $A_{s}(t)$ sounds. To this end, we leverage the audio-visual
simulator SoundSpaces [7], which provides precomputed RIRs $R(t)$ on a uniform
grid of resolution 1 m for the real-world environment scans in Replica [57]
and Matterport3D [5]. We use 82 Matterport environments due to their greater
scale and complexity; each environment has multiple rooms spanning on average
517 m2.

Figure 2: Audio-visual rendering for a Matterport environment. Left:
bird’s-eye view of the 3D environment. Right: panorama image rendered at the
camera location and the corresponding received spectrogram.

#### Reverberant speech in 3D visual environments.

We extend SoundSpaces to construct reverberant speech. As the source speech
corpus we use LibriSpeech [49], which contains 1,000 hours of 16kHz read
English speech from audio books, and is widely used in the speech recognition
literature. We train our models with the train-clean-360 split, and use the
dev-clean and test-clean sets for validation and test splits, respectively.
Note that these splits have non-overlapping speaker identities. Similarly, we
use the standard disjoint train/val/test splits for the Matterport 3D visual
environments [7]. Thus, neither the houses nor speaker voices observed at test
time are ever observed during training.

For each source utterance, we randomly sample a source-receiver location pair
in a random environment, then convolve the speech waveform $A_{s}(t)$ with the
associated SoundSpaces RIR $R(t)$ to obtain the reverberant $A_{r}(t)$. To
augment the visual stream, we insert a 3D humanoid of the same gender as the
real speaker at the speaker location and render RGB and depth images at the
listener location. We consider two types of image: panorama and normal field
of view (FoV). For the panorama image, we stitch 18 images each having a
horizontal FoV of 20 degrees, for a full image resolution of $192\times 756$.
For the normal FoV, we render images with a 80 degree FoV, at a resolution of
$384\times 256$. While the panorama gives a fuller view of the environment and
thus should allow the model to better estimate the room acoustics, the normal
FoV is more common in existing video and thus will facilitate our model’s
transfer to real data. See Fig. 2. We generate 49,430/2,700/2,600 such samples
for the train/val/test splits, respectively. See Supp. materials for examples
and details.

#### Real data collection.

To explore whether models trained in simulation can also work in the real
world, we also collect a set of real images and speech recordings while
preserving the ground truth anechoic audio.

To collect image data, we use an iPhone 11 camera to capture a panoramic RGB
image and a monocular depth estimation algorithm [22] to generate the
corresponding depth image.

To record the audio, we use a ZYLIA ZM-1 microphone. We place both the camera
and microphone at the same height (1.5m) as the SoundSpaces RIRs. For the
source speech, we play utterances from the LibriSpeech test set through a
loudspeaker held by a person facing the camera. We collect data from varying
environments, including auditoriums, meeting rooms, atriums, corridors, and
classrooms. For each environment, we vary the speaker location from near-field
to mid-field to far-field. For each location, we play around 10 utterances.
During data collection, the microphone also records ambient sounds like people
chatting, door opening, AC humming, etc. In total, we collect 200 recordings.
Please see the Supp. for audio-visual examples. We will publicly share all
data and code.

##  5 Approach

We propose the Visually-Informed Dereverberation of Audio (VIDA) model, which
leverages visual cues to learn representations of the environmental acoustics
and sound source locations to dereverberate audio. While our model is agnostic
to the audio source type, we focus on speech due to the importance of
dereverberating speech for downstream analysis. VIDA consists of two main
components (Figure 3): 1) a Visual Acoustics Network (VAN), which learns to
map RGB-D images of the environment to features useful for dereverberation,
and 2) the dereverberation module itself, which is based on a UNet encoder-
decoder architecture. The UNet encoder takes as input a reverberant
spectrogram, while the decoder takes the encoder’s output along with the
visual dereverberation features produced by the VAN and reconstructs a
dereverberated version of the audio.

Figure 3: VIDA model architecture. We convert the input speech to a
spectrogram and use overlapping sliding windows to obtain 2.56 second
segments. For visual inputs, we use separate ResNet18 networks to extract
features $e^{r}$ and $e^{d}$, which are fused to obtain $e^{c}$. We feed the
spectrogram segment $S_{r}^{i}$ to a UNet encoder, tile and concatenate
$e^{c}$ with the encoder’s output, then use the UNet decoder to predict the
clean spectrogram $\hat{S}_{s}^{i}$. During inference, we stitch the predicted
spectrogams back into a full spectrogram and use Griffin-Lim [23] to
reconstruct the output dereverberated waveform.

#### Visual Acoustics Network.

Visual observations of a scene reveal information about room acoustics,
including room geometry, materials, object locations, and the speaker
position. We devise the VAN to capture all these cues into a latent embedding
vector, which is subsequently used to remove reverb. This network takes as its
input an RGB image $I_{r}$ and a depth image $I_{d}$, captured from the
listener’s current position within the environment. The depth image contains
information about the geometry of the environment and arrangement of objects,
while the RGB image contains more information about their material
composition. To better model these different information sources, we use two
separate ResNet18 [25] networks to extract their features, i.e.
$e_{r}=f_{r}(I_{r})$ and $e_{d}=f_{d}(I_{d})$. We concatenate $e_{r}$ and
$e_{d}$ channel-wise and feed the result to a 1x1 convolution layer
$f_{c}(\cdot)$ to reduce the number of total channels to 512 followed by a
subsequent pooling layer $f_{l}(\cdot)$ to reduce the spatial dimension,
resulting in the output vector $e_{c}=f_{l}(f_{c}([e_{r};e_{d}]))$.

#### Dereverberation Network.

To recover the clean speech audio, we use the UNet [52] architecture, a fully
convolutional network often used for image segmentation. We first use the
Short-Time Fourier Transform (STFT) to convert the reverberant input audio
$A_{r}$ to a complex spectrogram $S_{r}$. We treat $S_{r}$ as a 2-dimensional,
2-channel image, where the horizontal dimension represents time, the vertical
dimension represents frequency, and the two channels represent the log-
magnitude and phase angle. Our UNet takes spectrograms of a fixed size of
$256\times 256$ as input, but in general the duration of the speech audio we
wish to dereverberate will be variable. Therefore, the model processes the
full input spectrogram using a series of overlapping, sliding windows.
Specifically, we segment the spectrogram along the time dimension into a
sequence of fixed-size chunks
$S_{r}^{seg}=\\{S_{r}^{1},S_{r}^{2},...,S_{r}^{n}\\}$ using a sliding window
of length $s$ frames and 50% overlap between consecutive windows to avoid
boundary artifacts. To derive the ground-truth target spectrograms used in
training, we perform the exact same segmentation operation on the clean source
audio $A_{s}$ to obtain $S_{s}^{seg}=\\{S_{s}^{1},S_{s}^{2},...,S_{s}^{n}\\}$.

During training, when a particular waveform $S_{r}$ is selected for inclusion
in a data batch, we randomly sample one of its segments $S_{r}^{i}$ to be the
input to the model, and choose the corresponding $S_{s}^{i}$ as the target. We
first compute the output of the VAN, $e_{c}$, for the environment image
associated with $S_{r}$. Next, $S_{r}^{i}$ is fed to the UNet’s encoder to
extract the intermediate feature map $e^{s}=f_{enc}(S_{r}^{i})$. We then
spatially tile and concatenate $e^{c}$ depth-wise with $e^{s}$, and feed the
fused features to the UNet decoder, which predicts the source spectrogram
segment $\hat{S_{s}^{i}}=f_{dec}([e^{s},e^{c}])$.

#### Spectrogram prediction loss.

The primary loss function we use to train our model is the Mean-Squared Error
(MSE) between the predicted and ground-truth spectrograms, treating the
magnitude and phase separately. For a given predicted spectrogram segment
$\hat{S_{s}^{i}}$, let $\hat{M_{s}^{i}}$ denote the predicted log-magnitude
spectrogram, $\hat{P_{s}^{i}}$ denote the predicted phase spectrogram, and
$M_{s}^{i}$ and $P_{s}^{i}$ denote the respective ground-truth magnitude and
phase spectrograms. We define the magnitude loss as:

$L_{magnitude}=||M_{s}^{i}-\hat{M_{s}^{i}}||_{2}.$ (1)

To address the issue of phase wraparound, we map the phase angle to its
corresponding rectangular coordinates on the unit circle and then compute the
MSE loss for the phase:

$L_{phase}=||\sin(P_{s}^{i})-\sin(\hat{P_{s}^{i}})||_{2}+||\cos(P_{s}^{i})-\cos(\hat{P_{s}^{i}})||_{2}.$
(2)

#### Reverb-visual matching loss.

To reinforce the consistency between the visually-inferred room acoustics and
the reverberation characteristics learned by the UNet encoder, we also employ
a contrastive reverb-visual matching loss:

$L_{matching}(e^{c},e^{s},e^{s}_{n})=\max\\{d(f_{n}(e^{c}),f_{n}(e^{s}))-d(f_{n}(e^{c}),f_{n}(e^{s}_{n}))+m,0\\}.$
(3)

Here, $d(x,y)$ represents L2 distance, $f_{n}(\cdot)$ applies L2
normalization, $m$ is a margin, and $e^{s}_{n}$ is a random speech embedding
sampled from the data batch. This loss forces the embeddings output by the VAN
and the UNet encoder to be consistent, which we empirically show to be
beneficial.

#### Training.

Our overall training objective (for a single training example) is as follows:

$L_{total}=L_{magnitude}+\lambda_{1}L_{phase}+\lambda_{2}L_{matching},$ (4)

where $\lambda_{1}$ and $\lambda_{2}$ are weighting factors for the phase and
matching losses. To augment the data, we further choose to rotate the image
view for a random angle for each input during training. This is possible
because our audio recording is omni-directional and is independent of camera
pose. This data augmentation strategy prevents the model from overfitting;
without it our model fails to converge. This strategy creates a one-to-many
mapping between reverb and views, forcing the model to learn a viewpoint-
invariant representation of the room acoustics.

#### Testing.

At test time, we wish to re-synthesize the entire clean waveform instead of a
single fixed-length segment. In this case, we feed all of the segments for a
waveform $S_{r}$ into the model and temporally concatenate all of the output
segments. Because consecutive segments overlap by 50%, during the
concatenation step we only retain the middle 50% of the frames from each
segment and discard the rest. Finally, to re-synthesize the waveform we use
the Griffin-Lim algorithm [23] to iteratively improve the predicted phase for
30 iterations, which we find works better than directly using the predicted
phase or using Griffin-Lim with a randomly initialized phase.

##  6 Experiments

We evaluate our model by dereverberating speech for three downstream tasks:
speech enhancement (SE), automatic speech recognition (ASR), and speaker
verification (SV). We evaluate using both real scanned Matterport3D
environments with sim audio as well as real-world data collected with a camera
and mic. Please see Supp. for all hyperparameter settings and data
preprocessing details.

#### Evaluation tasks and metrics.

We report the standard metrics Perceptual Evaluation of Speech Quality (PESQ)
[51], Word Error Rate (WER), and Equal Error Rate (EER) for the three tasks,
respectively. For ASR and SV, we use pretrained models from the SpeechBrain
[50] toolkit. We evaluate these models off-the-shelf on our (de)reverberated
version of the LibriSpeech test-clean set, and also explore finetuning the
model on the (de)reverberated LibriSpeech train-clean-360 data. For performing
speaker verification, we evaluate the model on a set of 80k randomly sampled
utterance pairs from the test-clean set. Please see Supp. for more details.

#### Baseline models.

In addition to evaluating the the clean and reverberant audio (with no
enhancement), we compare against multiple baseline dereverberation models:

  1. 1.

MetricGAN+ [16]: a recently proposed state-of-the-art model for speech
enhancement; we use the public implementation from SpeechBrain [50], trained
on our dataset. Following the original paper, we optimize for PESQ during
training, then choose the best-performing model snapshot (on the validation
data) specific to each of our downstream tasks.

  2. 2.

WPE [45]: A statistical speech dereverberation model that is commonly used for
comparison.

  3. 3.

Audio-only dereverb: An ablation of our proposed VIDA model that does not use
any visual input or the proposed matching loss (i.e., the VAN is removed). It
uses only the UNet encoder-decoder trained with the MSE loss for
dereverberation; a similar model is proposed by [14].

We emphasize that all baselines are audio-only models, as opposed to our
proposed audio-visual model. Our multimodal dereverberation technique could
extend to work in conjunction with other newly-proposed audio-only models,
i.e., ongoing architecture advances are orthogonal to our idea.

| Speech Enhancement | Speech Recognition | Speaker Verification
---|---|---|---
|  PESQ $\uparrow$ |  WER (%) $\downarrow$ |  WER-FT (%) $\downarrow$ |  EER (%) $\downarrow$ |  EER-FT (%) $\downarrow$
Clean (Upper bound) | 4.64 | 2.50 | 2.50 | 1.62 | 1.62
Reverberant | 1.54 | 8.86 | 4.62 | 4.69 | 4.57
MetricGAN+ [16] |  2.33 (+51%) |  7.49 (+15%) |  4.86 (-5%) |  4.67 (+0.4%) |  2.75 (+39%)
WPE [45] |  1.63 (+6%) |  8.18 (+8%) |  4.30 (+7%) |  5.19 (-11%) |  4.48 (+2%)
Audio-only dereverb. |  2.32 (+51%) |  4.92 (+44%) |  3.76 (+19%) |  4.67 (+0.4%) |  2.61 (+43%)
VIDA w/ normal FoV |  2.33 (+51%) |  4.85 (+45%) |  3.73 (+19%) |  4.53 (+3%) |  2.79 (+39%)
VIDA w/o matching loss | 2.38 (+55%) |  4.59 (+48%) |  3.72 (+19%) |  4.02 (+14%) |  2.62 (+43%)
VIDA w/o human mesh |  2.31 (+50%) |  4.57 (+48%) |  3.72 (+19%) |  4.00 (+15%) |  2.52 (+45%)
VIDA |  2.37 (+54%) | 4.44 (+50%) | 3.66 (+21%) | 3.99 (+15%) | 2.40 (+47%)
Table 1: Results on multiple speech analysis tasks, evaluated on the
LibriSpeech test-clean set that is reverberated with our environmental
simulator (with the exception of the “Clean (Upper bound)” setting, which is
evaluated on the original audio). WER-FT and EER-FT refer to tests where the
ASR and verification models are finetuned with the audio-enhanced data,
respectively. The relative improvement compared to Reverberant is included in
parentheses.

#### Results in scanned environments.

Table 1 shows the results for all models on SE, ASR, and SV. First, since
existing methods report results on clean non-reverberant audio, we note the
pretrained SpeechBrain model applied to clean audio (first row) yields errors
competitive with the SoTA [9], meaning we have a solid experimental testbed.
Comparing the results on clean vs. reverberated speech, we see that
reverberation significantly degrades performance on all tasks. Our VIDA model
outperforms all other models, and by a large margin on the ASR and SV tasks:
without finetuning, we achieve absolute improvements of 0.04 PESQ (1.71%
relative improvement), 0.48% WER (9.75% relative improvement), and 0.68% EER
(14.56% relative improvement) over the _best baseline_ in each case (which
happens to be the audio-only version of VIDA for both the ASR and SV tasks).
After finetuning the ASR and SV models, the gains are still largely preserved
at 0.1% WER (2.66% relative), and 0.21% EER (8.03% relative), although it is
important to note that finetuning the downstream models on the enhanced speech
is not always feasible. Our results demonstrate that learning the acoustic
properties of an environment from visual signals is very helpful for
dereverberating speech, enabling the model to leverage information about the
environment unavailable in the audio alone.

To understand how the WER of our model changes as the input difficulty
increases, we plot the cumulative WER against (a) the PESQ of the input speech
and (b) the speaker distance from the camera in Fig. 4(a) and Fig. 4(b),
respectively. Our VIDA model consistently outperforms the Audio-only baseline
on all difficulty levels. Importantly, when the input sample is more difficult
(low PESQ or far distance), our model shows a greater performance gain.

#### Ablations.

To understand how well VIDA works with a normal field-of-view (FoV) camera, we
replace the panorama image input with a FoV of 80 degrees randomly sampled
from the current view. Table 1 shows the results. All metrics drop compared to
using a panorama. This is expected, because the model is limited in what it
can see with a narrower field of view; the inferred room acoustics are
impaired by not seeing the full environment or missing where the speaker is.
Compared to the audio-only dereverberation model, however, VIDA applied to
narrow FoV data still performs better; even a partial view of the environment
helps the model understand the scene and dereverberate the audio. The fact the
two variants (panorama vs. reduced FoV) perform differently also reinforces
that our model is learning meaningful visual representations.

Next, we ablate the proposed reverb-visual matching loss (“w/o matching
loss"). Without it, VIDA’s performance declines on all metrics. This shows by
forcing the visual feature to agree with the reverberation feature, our model
learns a better representation of room acoustics.

To examine how much the model leverages the human speaker cues, we evaluate
our trained VIDA model on the same test data but with the 3D humanoid removed
(“w/o human mesh"). All three metrics become worse. This shows our model pays
attention to the location of the human speaker to learn a better
representation of the anticipated reverberation.

| Speech Enhancement | Speech Recognition | Speaker Verification
---|---|---|---
|  PESQ $\uparrow$ |  WER (%) $\downarrow$ |  EER (%) $\downarrow$
Clean (Upper bound) | 4.64 | 2.52 | 1.42
Reverberant | 1.22 | 18.39 | 3.91
MetricGAN+ [16] | 1.62 (+33%) |  21.42 (-16%) |  5.70 (-46%)
Audio-only dereverb. |  1.41 (+16%) |  15.18 (+17%) |  4.24 (-8%)
VIDA w/ normal FoV |  1.44 (+18%) |  14.71 (+20%) |  3.79 (+3%)
VIDA |  1.49 (+22%) | 13.02 (+29%) | 3.75 (+4%)
Table 2: Results on real data demonstrating sim2real transfer. | Atrium | Auditorium | Meeting Room | Classroom | Corridor
---|---|---|---|---|---
Near-field |  14.10 / 8.97 |  0.91 / 0.91 |  4.98 / 6.47 |  6.14 / 5.26 |  2.15 / 1.79
Mid-field |  21.78 / 18.94 |  5.06 / 6.32 |  7.67 / 7.67 |  2.56 / 1.47 |  7.27 / 4.36
Far-field |  52.38 / 50.52 |  10.44 / 7.46 |  21.95 / 6.71 |  5.91 / 6.82 |  25.23 / 21.10
Table 3: Breakdown of word error rate (WER) for Audio-only dereverb. / VIDA on
real test data.

#### Robustness to noise and ambient sounds.

We next test the robustness of our model by adding ambient sounds from urban
environments such as coffee shops, restaurants, and bars using the WHAM
dataset [64]. We add them to the reverberant test waveform with a SNR of 20,
following [14, 45]. We show our model is robust to this noise; see Supp. for
details.

#### Results on real data.

Next, we deploy our model in the real world. We use all models trained in
simulation to dereverberate the real-world dataset (cf. Sec. 4) before using
the finetuned ASR/SV models to evaluate the enhanced speech. Table 2 shows the
results of all models on real data. Reverberation does more damage to the WER
compared to in simulation. Although MetricGAN+ [16] has surprisingly better
PESQ, it has a weak WER score. Our VIDA model again outperforms all baselines
on ASR and SV. This demonstrates the realism of the simulation and the
capability of our trained model to directly transfer to real-world data, a
promising step for VIDA’s wider applicability.

Table 3 breaks down the ASR performance for Audio-only dereverb. (the best
baseline) and our VIDA model by environment type and speaker distance. The
atrium is quite reverberant due to the large space. Although the auditorium is
similarly large, the space is designed to reduce reverberation and thus both
models have lower WER. The meeting room and the classroom have smaller sizes
and are comparatively less reverberant. The corridor only becomes reverberant
when the speaker is far away. VIDA outperforms the Audio-only dereverb.
baseline in most cases, especially in highly reverberant ones. See the Supp.
video for examples.

#### Analyzing learned features.

Figure 4(c) and 4(d) analyze our model’s learned audio and visual features via
2D TSNE projections [62]. For each sample, we color the point according to
either (c) the ground truth distance between the camera/microphone and the
human speaker or (d) the reverberation time for the audio signal to decay by
60 dB (known as the RT60). Neither of these variables are available to our
model during training, yet when learning to perform deverberation, our model
exposes these high-level properties relevant to the audio-visual task.
Consistent with the quantitative results above, this analysis shows how our
model captures elements of the visual scene, room geometry, and speaker
location that are valuable to proper dereverberation.

(a) WER vs PESQ (b) WER vs distance

(c) Audio TSNE (d) Visual TSNE

Figure 4:  Left: Cumulative WER against PESQ of the input speech (a) and the
speaker distance from the camera (b). Right: TSNE of audio and visual features
colored by distance (c) and RT60 (d).

#### Qualitative examples.

Figure 5 shows a simulated and real-world example. As we can see, the
reverberant spectrogram is much blurrier compared to the clean spectrogram,
while our predicted spectrogram removes those reverberations by leveraging the
visual cues of room acoustics.

Figure 5: Example input images, clean spectrograms, reverberant spectograms
and spectrograms dereverberated by VIDA (top is from a scan, bottom is a real
pano). The speaker is out of view in the first case and distant in the second
case (back of the classroom). Though both received audio inputs are quite
reverberant, our model successfully removes the reverb and restores the clean
source speech.

##  7 Conclusion

We introduced the novel task of audio-visual dereverberation. The proposed
VIDA approach learns to remove reverb by attending to both the audio and
visual streams, recovering valuable signals about room geometry, materials,
and speaker locations from visual encodings of the environment. In support of
this task, we develop a large-scale dataset providing realistic, spatially
registered observations of speech and 3D environments. Our results show VIDA
successfully dereverberates novel voices in novel environments more accurately
than an array of baselines, improving multiple downstream tasks. Furthermore,
having trained in the realistic simulator, our model also has promise to
enhance speech in real-world data, although more work is needed to bring down
the absolute error rates. In future work, we plan to explore temporal models
for audio-visual dereverberation with video and introduce active perception
for camera control.

## References

  * [1] Triantafyllos Afouras, Andrew Owens, Joon-Son Chung and Andrew Zisserman  “Self-Supervised Learning of Audio-Visual Objects from Video”  In _ECCV_ , 2020
  * [2] Jont B. Allen and David A. Berkley  “Image method for efficiently simulating small-room acoustics”  In _The Journal of the Acoustical Society of America_ 65.4, 1979, pp. 943–950
  * [3] Humam Alwassel, Dhruv Mahajan, Bruno Korbar, Lorenzo Torresani, Bernard Ghanem and Du Tran  “Self-Supervised Learning by Cross-Modal Audio-Video Clustering”  In _NeurIPS_ , 2020
  * [4] Jacob Benesty, Shoji Makino and Jingdong Chen  “Speech Enhancement”  Springer Publishing Company, Incorporated, 2010
  * [5] Angel Chang, Angela Dai, Thomas Funkhouser, Maciej Halber, Matthias Niessner, Manolis Savva, Shuran Song, Andy Zeng and Yinda Zhang  “Matterport3D: Learning from RGB-D Data in Indoor Environments” MatterPort3D dataset license available at: http://kaldir.vc.in.tum.de/matterport/MP_TOS.pdf In _3DV_ , 2017
  * [6] Changan Chen, Ziad Al-Halah and Kristen Grauman  “Semantic Audio-Visual Navigation”  In _CVPR_ , 2021
  * [7] Changan Chen, Unnat Jain, Carl Schissler, Sebastia Vicenc Amengual Gari, Ziad Al-Halah, Vamsi Krishna Ithapu, Philip Robinson and Kristen Grauman  “SoundSpaces: Audio-Visual Navigation in 3D Environments”  In _ECCV_ , 2020
  * [8] Changan Chen, Sagnik Majumder, Ziad Al-Halah, Ruohan Gao, Santhosh Kumar Ramakrishnan and Kristen Grauman  “Learning to Set Waypoints for Audio-Visual Navigation”  In _ICLR_ , 2021  URL: http://arxiv.org/abs/2008.09622
  * [9] “Conformer: Convolution-augmented Transformer for Speech Recognition”  In _Interspeech_ , 2020
  * [10] Victoria Dean, Shubham Tulsiani and Abhinav Gupta  “See, Hear, Explore: Curiosity via Audio-Visual Association”  In _NeurIPS_ , 2020
  * [11] Brecht Desplanques, Jenthe Thienpondt and Kris Demuynck  “ECAPA-TDNN: Emphasized Channel Attention, Propagation and Aggregation in TDNN Based Speaker Verification”  In _Interspeech 2020_ ISCA, 2020, pp. 3830–3834
  * [12] David Eigen, Christian Puhrsch and Rob Fergus  “Depth Map Prediction from a Single Image using a Multi-Scale Deep Network”  In _NIPS_ , 2014
  * [13] Ariel Ephrat, Inbar Mosseri, Oran Lang, Tali Dekel, Kevin Wilson, Avinatan Hassidim, William T Freeman and Michael Rubinstein  “Looking to listen at the cocktail party: A speaker-independent audio-visual model for speech separation”  In _SIGGRAPH_ , 2018
  * [14] Ori Ernst, Shlomo E. Chazan, Sharon Gannot and Jacob Goldberger  “Speech Dereverberation Using Fully Convolutional Networks”  In _arXiv:1803.08243 [cs, eess]_
  * [15] Szu-Wei Fu, Chien-Feng Liao, Yu Tsao and Shou-De Lin  “MetricGAN: Generative Adversarial Networks based Black-box Metric Scores Optimization for Speech Enhancement”  In _arXiv:1905.04874_
  * [16] Szu-Wei Fu, Cheng Yu, Tsun-An Hsieh, Peter Plantinga, Mirco Ravanelli, Xugang Lu and Yu Tsao  “MetricGAN+: An Improved Version of MetricGAN for Speech Enhancement”  In _arXiv:2104.03538_
  * [17] Chuang Gan, Yiwei Zhang, Jiajun Wu, Boqing Gong and Joshua B Tenenbaum  “Look, Listen, and Act: Towards Audio-Visual Embodied Navigation”  In _ICRA_ , 2020
  * [18] R. Gao and K. Grauman  “2.5D Visual Sound”  In _CVPR_ , 2019
  * [19] R. Gao and K. Grauman  “VisualVoice: Audio-Visual Speech Separation with Cross-Modal Consistency”  In _CVPR_ , 2021
  * [20] Ruohan Gao, Changan Chen, Ziad Al-Halah, Carl Schissler and Kristen Grauman  “VisualEchoes: Spatial Image Representation Learning through Echolocation”  In _ECCV_ , 2020
  * [21] Ruohan Gao, Rogerio Feris and Kristen Grauman  “Learning to Separate Object Sounds by Watching Unlabeled Video”  In _ECCV_ , 2018
  * [22] Clément Godard, Oisin Mac Aodha, Michael Firman and Gabriel J. Brostow  “Digging into Self-Supervised Monocular Depth Prediction”  In _ICCV_ , 2019
  * [23] Daniel Griffin and Jae Lim  “Signal estimation from modified short-time Fourier transform”  In _IEEE Transactions on acoustics, speech, and signal processing_ 32.2 IEEE, 1984, pp. 236–243
  * [24] K. Han, Y. Wang, D. Wang, W.. Woods, I. Merks and T. Zhang  “Learning Spectral Mapping for Speech Dereverberation and Denoising”  In _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 2015
  * [25] Kaiming He, Xiangyu Zhang, Shaoqing Ren and Jian Sun  “Deep residual learning for image recognition”  In _CVPR_ , 2016, pp. 770–778
  * [26] John R Hershey, Zhuo Chen, Jonathan Le Roux and Shinji Watanabe  “Deep clustering: Discriminative embeddings for segmentation and separation”  In _ICASSP_ , 2016
  * [27] Martin Holters, Tobias Corbach and Udo Zölzer  “Impulse Response Measurement Techniques and their Applicability in the Real World”  In _Proceedings of the 12th International Conference on Digital Audio Effects, DAFx 2009_ , 2009
  * [28] Di Hu, Rui Qian, Minyue Jiang, Xiao Tan, Shilei Wen, Errui Ding, Weiyao Lin and Dejing Dou  “Discriminative Sounding Objects Localization via Self-supervised Audiovisual Matching”  In _NeurIPS_ , 2020
  * [29] “Improving speech recognition in reverberation using a room-aware deep neural network and multi-task learning”  In _2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2015
  * [30] Marco Jeub, Magnus Schäfer, Hauke Krüger, Christoph Matthias Nelke, Christophe Beaugeant and Peter Vary  “Do We Need Dereverberation for Hand-Held Telephony?”  In _International Congress on Acoustics_ , 2010
  * [31] Diederik P Kingma and Jimmy Ba  “Adam: A method for stochastic optimization”  In _ICLR_ , 2015
  * [32] Keisuke Kinoshita, Marc Delcroix, Sharon Gannot, Emanuël Habets, Reinhold Haeb-Umbach, Walter Kellermann, Volker Leutnant, Roland Maas, Tomohiro Nakatani, Bhiksha Raj, Armin Sehr and Takuya Yoshioka  “A Summary of the REVERB Challenge: State-of-the-Art and Remaining Challenges in Reverberant Speech Processing Research”  In _EURASIP Journal on Advances in Signal Processing_ , 2016
  * [33] Tom Ko, Vijayaditya Peddinti, Daniel Povey, Michael L Seltzer and Sanjeev Khudanpur  “A study on data augmentation of reverberant speech for robust speech recognition”  In _2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2017, pp. 5220–5224  IEEE
  * [34] Homare Kon and Hideki Koike  “Estimation of Late Reverberation Characteristics from a Single Two-Dimensional Environmental Image Using Convolutional Neural Networks”  In _Journal of the Audio Engineering Society_ , 2019
  * [35] Bruno Korbar, Du Tran and Lorenzo Torresani  “Cooperative Learning of Audio and Video Models from Self-Supervised Synchronization”  In _NeurIPS_ , 2018
  * [36] Dingzeyu Li, Timothy R Langlois and Changxi Zheng  “Scene-aware audio for 360 videos”  In _ACM Transactions on Graphics (TOG)_ 37.4 ACM New York, NY, USA, 2018, pp. 1–12
  * [37] Sagnik Majumder, Ziad Al-Halah and Kristen Grauman  “Move2Hear: Active Audio-Visual Source Separation”, 2021  arXiv:2105.07142 [cs.CV]
  * [38] Peter Vary Marco Jeub  “A binaural room impulse response database for the evaluation of dereverberation algorithms”  In _Proceedings of International Conference on Digital Signal Processing_ , 2009
  * [39] M. Miyoshi and Y. Kaneda  “Inverse filtering of room acoustics”  In _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , 1988
  * [40] Pedro Morgado, Yi Li and Nuno Vasconcelos  “Learning Representations from Audio-Visual Spatial Alignment”  In _NeurIPS_ , 2020
  * [41] Pedro Morgado, Nono Vasconcelos, Timothy Langlois and Oliver Wang  “Self-supervised generation of spatial audio for 360 video”  In _NeurIPS_ , 2018
  * [42] D.T. Murphy, Antti Kelloniemi, Jack Mullen and Simon Shelley  “Acoustic Modeling Using the Digital Waveguide Mesh”  In _Signal Processing Magazine, IEEE_ 24, 2007, pp. 55–66
  * [43] Damian T Murphy and Simon Shelley  “Openair: An interactive auralization web resource and database”  In _Audio Engineering Society Convention 129_ , 2010
  * [44] A. Nagrani, J.. Chung and A. Zisserman  “VoxCeleb: a large-scale speaker identification dataset”  In _INTERSPEECH_ , 2017
  * [45] Tomohiro Nakatani, Takuya Yoshioka, Keisuke Kinoshita, Masato Miyoshi and Biing-Hwang Juang  “Speech dereverberation based on variance-normalized delayed linear prediction”  In _IEEE Transactions on Audio, Speech, and Language Processing_ , 2010
  * [46] Patrick A. Naylor and Nikolay D. Gaubitch  “Speech Dereverberation”  Springer Publishing Company, Incorporated, 2010
  * [47] Stephen T. Neely and Jont B. Allen  “Invertibility of a room impulse response”  In _Journal of the Acoustical Society of America_ , 1979
  * [48] Andrew Owens and Alexei A Efros  “Audio-visual scene analysis with self-supervised multisensory features”  In _ECCV_ , 2018
  * [49] Vassil Panayotov, Guoguo Chen, Daniel Povey and Sanjeev Khudanpur  “Librispeech: an asr corpus based on public domain audio books”  In _2015 IEEE international conference on acoustics, speech and signal processing (ICASSP)_ , 2015, pp. 5206–5210  IEEE
  * [50] Mirco Ravanelli, Titouan Parcollet, Aku Rouhe, Peter Plantinga, Elena Rastorgueva, Loren Lugosch, Nauman Dawalatabad, Chou Ju-Chieh, Abdel Heba, Francois Grondin, William Aris, Chien-Feng Liao, Samuele Cornell, Sung-Lin Yeh, Hwidong Na, Yan Gao, Szu-Wei Fu, Cem Subakan, Renato De Mori and Yoshua Bengio  “SpeechBrain”  In _GitHub repository_ GitHub, https://github.com/speechbrain/speechbrain, 2021
  * [51] A.. Rix, J.. Beerends, M.. Hollier and A.. Hekstra  “Perceptual evaluation of speech quality (PESQ)-a new method for speech quality assessment of telephone networks and codecs”  In _2001 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings_ , 2001
  * [52] Olaf Ronneberger, Philipp Fischer and Thomas Brox  “U-net: Convolutional networks for biomedical image segmentation”  In _International Conference on Medical image computing and computer-assisted intervention_ , 2015, pp. 234–241  Springer
  * [53] Nikhil Singh, Jeff Mentch, Jerry Ng, Matthew Beveridge and Iddo Drori  “Image2Reverb: Cross-Modal Reverb Impulse Response Synthesis”  In _arXiv preprint arXiv:2103.14201_ , 2021
  * [54] David Snyder, Daniel Garcia-Romero, Gregory Sell, Daniel Povey and Sanjeev Khudanpur  “X-vectors: Robust DNN embeddings for speaker recognition”  In _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2018, pp. 5329–5333  IEEE
  * [55] Guy-Bart Stan, Jean-Jacques Embrechts and Dominique Archambeau  “Comparison of Different Impulse Response Measurement Techniques”  In _journal of the audio engineering society_ 50.4, 2002, pp. 249–262
  * [56] Daniel Stoller, Sebastian Ewert and Simon Dixon  “Adversarial semi-supervised audio source separation applied to singing voice extraction”  In _ICASSP_ , 2018
  * [57] Julian Straub, Thomas Whelan, Lingni Ma, Yufan Chen, Erik Wijmans, Simon Green, Jakob J Engel, Raul Mur-Artal, Carl Ren and Shobhit Verma  “The Replica Dataset: A Digital Replica of Indoor Spaces”  In _arXiv preprint arXiv:1906.05797_ , 2019
  * [58] Jiaqi Su, Zeyu Jin and Adam Finkelstein  “Acoustic matching by embedding impulse responses”  In _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2020, pp. 426–430  IEEE
  * [59] Jiaqi Su, Zeyu Jin and Adam Finkelstein  “HiFi-GAN: High-Fidelity Denoising and Dereverberation Based on Speech Deep Features in Adversarial Networks”  In _arXiv:2006.05694 [cs, eess]_ , 2020  arXiv:2006.05694
  * [60] Igor Szöke, Miroslav Skácel, Ladislav Mošner, Jakub Paliesek and Jan Černocký  “Building and evaluation of a real room impulse response dataset”  In _IEEE Journal of Selected Topics in Signal Processing_ , 2019
  * [61] Ke Tan, Yong Xu, Shi-Xiong Zhang, Meng Yu and Dong Yu  “Audio-Visual Speech Separation and Dereverberation with a Two-Stage Multimodal Network”  In _IEEE Journal of Selected Topics in Signal Processing_ , 2020
  * [62] L.J.P. van der Maaten and G.E. Hinton  “Visualizing High-Dimensional Data Using t-SNE”  In _Journal of Machine Learning Research_ 9, 2008, pp. 2579–2605
  * [63] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser and Illia Polosukhin  “Attention is all you need”  In _NeurIPS_ , 2017
  * [64] Gordon Wichern, Joe Antognini, Michael Flynn, Licheng Richard Zhu, Emmett McQuinn, Dwight Crow, Ethan Manilow and Jonathan Le Roux  “WHAM!: Extending Speech Separation to Noisy Environments”  In _Proc. Interspeech_ , 2019
  * [65] B. Wu, K. Li, F. Ge, Z. Huang, M. Yang, S.. Siniscalchi and C. Lee  “An End-to-End Deep Learning Approach to Simultaneous Speech Dereverberation and Acoustic Modeling for Robust Speech Recognition”  In _IEEE Journal of Selected Topics in Signal Processing_ , 2017
  * [66] B. Wu, K. Li, M. Yang and C.-H. Lee  “A reverberation-time-aware approach to speech dereverberation based on deep neural networks”  In _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 2016
  * [67] Ruilin Xu, Rundi Wu, Yuko Ishiwaka, Carl Vondrick and Changxi Zheng  “Listening to Sounds of Silence for Speech Denoising”  In _NeurIPS_ , 2019
  * [68] Hang Zhao, Chuang Gan, Wei-Chiu Ma and Antonio Torralba  “The Sound of Motions”  In _ICCV_ , 2019
  * [69] Y. Zhao, D. Wang, B. Xu and T. Zhang  “Monaural Speech Dereverberation Using Temporal Convolutional Networks With Self Attention”  In _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 2020
  * [70] Y. Zhao, Z.-Q. Wang and D.. Wang  “Two-stage deep learning for noisy-reverberant speech enhancement”  In _IEEE/ACM Trans. on Audio, Speech, and Language Processing_ , 2019

##  8 Supplementary Materials

In this supplementary material, we provide additional details about:

  1. 1.

Video (with audio) for demos of the collected data as well as qualitative
assessment of VIDA’s performance.

  2. 2.

Implementation details of our model and data pre-processing.

  3. 3.

Evaluation details of downstream tasks and corresponding metrics.

  4. 4.

Robustness to noise and ambient sound.

  5. 5.

Ablation on visual sensors.

###  8.1 Qualitative Video

This video includes examples for audio-visual data in simulation and in the
real-world. We demonstrate examples of our dereverbration model applied to
these inputs. The video is available at https://youtu.be/zPeAjlwo6XA.

###  8.2 Implementation Details

For the STFT calculation, we sample the input audio at 16 kHz and use a
Hamming window of size 400 samples (25 milliseconds), a hop length of 160
samples (10 milliseconds), and a 512-point FFT. By retaining only the positive
frequencies and segmenting the spectrograms into 256-frame chunks
(corresponding to approximately 2.5 seconds of sound), the final audio input
size to our UNet is 256x256. We use the Adam optimizer [31] to train our model
with $lr=0.001$. We decay the learning rate exponentially to $lr=0.0001$ in
150 epochs. We set the batch size to 96 and train all models for 150 epochs,
which is long enough to reach convergence. We set the margin $m$ to 0.5, phase
loss weight $\lambda_{1}$ to 0.08 and matching loss weight $\lambda_{2}$ to
0.001.

###  8.3 Evaluation Details

We evaluate our model on three tasks: speech enhancement (SE), automatic
speech recognition (ASR), and speaker verification (SV).

  * •

For SE, the goal is to improve the overall sonic quality of the speech signal,
which we measure automatically using the standard Perceptual Evaluation of
Speech Quality (PESQ) [51] metric.

  * •

For ASR, the goal is to automatically transcribe the sequence of words that
were spoken in the audio recording. For this task, we report the Word Error
Rate (WER), which is the standard metric used in ASR and reflects a word-level
edit distance between a recognizer’s output and the ground-truth
transcription.

  * •

For SV, the goal is to detect whether or not two different spoken utterances
were spoken by the same speaker. For SV, we report the Equal Error Rate (EER),
a standard metric in the SV field indicating the point on the Detection Error
Tradeoff (DET) curve where the false alarm and missed detection probabilities
are equivalent.

Since the spectrogram MSE loss we optimize during training does not perfectly
correlate with these three task-specific metrics, we perform model selection
(across snapshots saved each training epoch) by computing the task-specific
evaluation metric on 500 validation samples. We then select the best model
snapshot independently for each downstream task and evaluate on the held-out
test set; the same model selection procedure is also used for all of our
baseline models.

For the ASR and SV tasks, we use the SpeechBrain [50] toolkit. For ASR, we use
the HuggingFace Transformer [63] \+ Transformer LM model pre-trained on
LibriSpeech [49]. We evaluate this model off-the-shelf on our (de)reverberated
version of the LibriSpeech test-clean set, and also explore fine-tuning the
model on the (de)reverberated LibriSpeech train-clean-360 data. For the SV
task, we use SpeechBrain’s ECAPA-TDNN embedding model [11], pre-trained on
VoxCeleb [44]. For performing verification, we evaluate the model on a set of
80k randomly sampled utterance pairs from the test-clean set (40k same-speaker
pairs, 40k different-speaker pairs) using the cosine similarity-based scoring
pipeline from SpeechBrain’s VoxCeleb recipe. In the verification task, we use
the clean (non-reverberated) speech as the reference utterance, and the
reverberant speech as the test utterance. As in the ASR task, we evaluate this
model on our dereverberation model’s outputs both off-the-shelf, as well as
after fine-tuning on the (de)reverberated train-clean-360 set.

###  8.4 Robustness to Noisy Audio

We test the robustness of our model by adding ambient sounds from urban
environments such as coffee shops, restaurants, and bars using the WHAM
dataset [64]. We add them to the reverberant test waveform with a SNR of 20,
following [14, 45]. Table 4 shows the results on three downstream tasks. As
expected, all models’ performance drop compared to the results in the noise-
free test setting (Table 1), but our VIDA model still significantly
outperforms the baselines on ASR. For speaker verification, WPE [45] is
reported to be robust to noisy input and thus has lower EER while using the
pretrained model, but it underperforms VIDA when the SV model is finetuned on
the enhanced speech. Noise has less impact on the performance on
MetricGAN+[16] likely because it directly optimizes PESQ.

| Speech Enhancement | Speech Recognition | Speaker Verification
---|---|---|---
|  PESQ $\uparrow$ |  WER (%) $\downarrow$ |  WER-FT (%) $\downarrow$ |  EER (%) $\downarrow$ |  EER-FT (%) $\downarrow$
Clean (Upper bound) | 4.64 | 2.50 | 2.50 | 1.62 | 1.62
Reverberant | 1.36 | 12.27 | 6.38 | 4.69 | 5.10
MetricGAN+ [16] | 2.12 (+57%) |  9.40 (+23%) |  7.09 (-11%) |  4.94 (-5%) |  3.38 (+34%)
WPE [45] |  1.39 (+2%) |  11.32 (+8%) |  7.00 (-10%) | 4.48 (+4%) |  4.95 (+3%)
Audio-only dereverb. |  1.76 (+29%) |  7.37 (+40%) |  5.52 (+14%) |  5.75 (-23%) |  3.58 (+30%)
VIDA w/ normal FoV |  1.76 (+29%) |  7.51 (+39%) |  5.51 (+14%) |  5.54 (-18%) |  3.40 (+33%)
VIDA w/o matching loss |  1.81 (+33%) |  6.76 (+45%) |  5.31 (+17%) |  4.95 (-6%) |  3.26 (+36%)
VIDA |  1.82 (+34%) | 6.53 (+47%) | 5.29 (+17%) |  4.83 (-3%) | 3.13 (+39%)
Table 4: Results on the LibriSpeech test-clean set mixed with ambient sounds
at a 20 dB signal-to-noise ratio.

###  8.5 Ablation on Visual Sensors

To understand the importance of each input sensor, we ablate the RGB and depth
input as shown in Table 5. Dropping either RGB or depth makes the WER worse.
We hypothesize that this is because they contain distinct information for the
learning of room acoustics. The depth image is better for capturing room
geometry, while the RGB image is better for capturing material and speaker
location information.

In addition, we perform early fusion of RGB and Depth images by stacking them
along the channel dimension (w/ early fusion in Table 5) and use one ResNet18
[25] model instead of two. This method also has worse WER, which validates our
design choice of extracting RGB and depth features separately.

| Speech Enhancement | Speech Recognition | Speaker Verification
---|---|---|---
|  PESQ $\uparrow$ |  WER (%) $\downarrow$ |  EER (%) $\downarrow$
Reverberant | 1.54 | 8.86 | 4.69
Audio-only dereverb. |  2.32 (+51%) |  4.92 (+44%) |  4.67 (+0.4%)
VIDA w/o RGB | 2.38 (+55%) |  4.76 (+46%) | 3.82 (+19%)
VIDA w/o depth | 2.38 (+55%) |  4.52 (+49%) |  3.99 (+15%)
VIDA w/ early fusion | 2.38 (+55%) |  4.56 (+48.5%) |  3.94 (+16%)
VIDA |  2.37 (+54%) | 4.44 (+50%) |  3.99 (+15%)
Table 5: Ablations on visual sensors. Percentages in parenthesis represent
relative improvements over the reverberant baseline.


††thanks: The author expresses her thanks to A. S. Oliynyk for introducing her
to the topic of automata transformations

# Non-paradoxical action of automata groups on infinite words

Victoriia Korchemna

(28.10.2018)

###### Abstract

We show, that groups, defined by wide class of automata, including all
polynomial ones, act on the set of infinite words not paradoxical.

##  1 Introduction and definitions

###  1.1 Rooted tree of words and it’s isomorphisms

Let $X$ be a finite set, which will be called alphabet with elements called
letters. We always suppose $|X|>1$ (here $|X|$ denotes the cardinality of
$X$). Let $X^{*}$ be the free monoid generated by $X$. The elements of this
monoid are finite words $x_{1}x_{2}...x_{n}$, $x_{i}\in X$, including the
empty word $\emptyset$. Denote by $X^{w}$ the set of all infinite words
$x_{1}x_{2}...x_{n}...$, $x_{i}\in X$. For each $l\in\mathbb{N}$ and
$w=w_{1}...w_{l}...\in X^{w}$ set $w[:l]:=w_{1}...w_{l}$. In other words,
$w[:l]$ is a finite word, formed by first $l$ letters of $w$.

The set $X^{*}$ is naturally a vertex set of a rooted tree, in which two words
are connected by an edge if and only if they are of the form $v$ and $vx$,
where $v\in X^{*}$, $x\in X.$ The empty word $\emptyset$ is the root of the
tree $X^{*}$.

A map $f:X\to X$ is an endomorphism of the tree $X$, if for any two adjacent
vertices $v$, $vx\in X^{*}$ the vertices $f(v)$ and $f(vx)$ are also adjacent,
so that there exist $u\in X^{*}$ and $y\in X$ such that $f(v)=u$ and
$f(vx)=uy$. An automorphism is a bijective endomorphism.

###  1.2 Automata and automorphisms of rooted trees

An automaton A is a quadruple $(X,Q,\pi,\lambda)$, where:

  * •

$X$ is an alphabet;

  * •

$Q$ is a set of states of the automaton;

  * •

$\pi:Q\times X\to X$ is a map, called the transition function of the
automaton;

  * •

$\lambda:Q\times X\to X$ is a map, called the output function of the
automaton.

An automaton is finite if it has a finite number of states. The maps
$\pi,\lambda$ can be extended on $Q\times X^{*}$ by the following recurrent
formulas:

$\pi(q,\emptyset)=q,\;\;\pi(q,xw)=\pi(\pi(q,x),w)$
$\lambda(q,\emptyset)=\emptyset,\;\;\lambda(q,xw)=\lambda(q,x)\lambda(\pi(q,x),w),$

where $x\in X$, $q\in Q$, and $w\in X^{*}$ are arbitrary elements. Similarly,
the maps $\pi,\lambda$ are extended on $Q\times X^{w}$.

An automaton $A$ with a fixed state $q$ is called initial and is denoted by
$A_{q}$. Every initial automaton defines the automorphism $\lambda(q,\cdot)$
of the rooted tree $X^{*}$, which we also denote by
$A_{q}(\cdot)=\lambda(q,\cdot)$ (or q($\cdot$) if it is clear, which automaton
it belongs to). We denote by $e$ a trivial state of automaton, i.e., such a
state that defines a trivial automorphism of $X^{*}$. The action of an initial
automaton $A_{q}$ can be interpret as the work of a machine, which being in
the state $q$ and reading on the input tape a letter $x$, goes to the state
$\pi(q,x)$, types on the output tape the letter $\lambda(q,x)$, then moves
both tapes to the next position and proceeds further.

###  1.3 Moore diagrams

An automaton $A$ can be represented (and defined) by a labelled directed
graph, called the Moore diagram, in which the vertices are the states of the
automaton and for every pair $(q,x)\in Q\times X$ there is an edge from $q$ to
$\pi(q,x)$ labelled by $x|\lambda(q,x)$.

Here is the Moore diagram of automaton, called the adding machine. Consider a
word of length $l\in\mathbb{N}$ as a binary number, with lower digits on the
left side. If the automaton gets the word in state q, it adds 1 modulo $2^{l}$
to it.

###  1.4 Inverse automaton. Composition of automata

An automaton is called invertible, if for each $q\in Q$ the mapping
$\lambda(q,\cdot)$ is a bijection. Suppose that we have the Moore diagram of
invertible automaton $A$. Let us swap all the left labels with right ones that
correspond to them. After renaming the states $q\to q^{-1}$ we get a Moore
digram of some automaton $A^{-1}$, which is called the inverse automaton of
$A$. Notice that for each $q\in Q$ the state $q^{-1}$ of $A^{-1}$ defines the
automorphism of a rooted tree which is inverse to $q$.

Further in the article we omit the word ”invertible” and consider only
invertible automata.

By giving the output of $A=(X,Q,\pi,\lambda)$ to the input of another
automaton $B=(X,S,\alpha,\beta)$, we get an application which corresponds to
the automaton called the composition of $A$ and $B$ and is denoted by $A*B$.
This automaton is formally described as the automaton with the set of the
states $Q\times S$ and the transition and output functions $\phi,\psi$ defined
by

$\phi((q,s),x)=(\pi(q,x),\alpha(s,\lambda(q,x)))$
$\psi((q,s),x)=\beta(s,\lambda(q,x))$

Notice that a state $(q,s)$ of $Q\times S$ defines the automorphism of a
rooted tree which is a superposition of ones defined by $q$ and $s$.

###  1.5 Paradoxical actions of groups

Let $G$ be a group acting on a set $X$ and suppose $E\subseteq X$. $G$ acts on
$E$ paradoxically ($E$ is $G$-paradoxical) if for some positive integers $m,n$
there are pairwise disjoint subsets $A_{1},...,A_{n}$, $B_{1},...,B_{n}$ of
$E$ and $g_{1},...,g_{n},\;h_{1},...,h_{n}\in G$ such that $E=\bigcup
g_{i}(A_{i})=\bigcup h_{i}(B_{i}).$ Loosely speaking, the set $E$ has two
disjoint subsets, each of which can be taken apart and rearranged via $G$ to
cover all of $E$. Well known example is Banach-Tarski paradox, where subgroup
of isometries of $R^{3}$ act’s on a sphere.

##  2 Automata, that ”almost always” move to the trivial state

In the article we fix some alphabet $X$ and consider words over $X$ only. For
arbitrary automata transformation $g$ denote by $NS(g,l)$ the number of words
of length $l$ which move $g$ to the non-trivial state.

######  Proposition 1.

$NS(\bullet,\bullet)$ has the following properties:
(1): $NS(g,l)=NS(g^{-1},l)$
(2): $NS(gh,l)\leq NS(g,l)+NS(h,l)$,
where $g,h$ are arbitrary automata transformations, $l\in\mathbb{N}$

###### Proof.

$(1)$ Let $w$ be a word with a length $l$ that doesn’t move $g$ to the trivial
state. Then $g(w)$ is a word with a length $l$ that doesn’t move $g^{-1}$ to
the trivial state. Since $g$ is a bijective mapping on $X^{l}$, $g(w)$ are
different for different $w$. Therefore, $NS(g^{-1},l)\leq NS(g,l).$. After
replacing $g\to g^{-1}$, we get the opposite inequality.

$(2)$ For arbitrary automata transformation $q$ denote by $\textbf{S}(q,l)$
the set of words of length $l$ that move $q$ to the trivial state;
$\textbf{NS}(q,l):=X^{l}\setminus\textbf{S}(q,l)$. Then
$|\textbf{NS}(q,l)|=NS(q,l)$, $|\textbf{S}(q,l)|=|X|^{l}-NS(q,l)$.

As $g$ is a bijection on $X^{l}$, we have
$|g(\textbf{NS}(g,l))|=|\textbf{NS}(g,l)|=NS(g,l)$. If a word $w\in X^{l}$
moves $g$ to the trivial state and so does $g(w)$ with $h$, then $w$ moves
$gh$ to the trivial state. Therefore:

$\textbf{S}(gh,l)\supseteq
g(\textbf{S}(g,l))\cap\textbf{S}(h,l)=X^{l}\setminus(g(\textbf{NS}(g,l))\cup\textbf{NS}(h,l))$
$|\textbf{S}(gh,l)|\geq|X|^{l}-(NS(g,l)+NS(h,l))$
$NS(g,l)=|\textbf{NS}(gh,l)|\leq NS(g,l)+NS(h,l)$

∎

Denote by $G_{0}$ the set of all automata transformations $g$ for which the
following holds:

$NS(g,l)=o(|X|^{l}),l\to\infty$

To put it simply, ”almost” all the words move the transformations to the
trivial state.

$(1)$ and $(2)$ imply that $G_{0}$ is a group. Notice that $G_{0}$ includes
all the polynomial automata. What do we know about it’s action on $X^{w}$?

######  Theorem 1.

$X^{w}$ is not $G_{0}$-paradoxical.

###### Proof.

Assume that $X^{w}$ is $G_{0}$-paradoxical. Then there are the elements
$h_{1},...,h_{d}$ of $G_{0}$ and the partition $X^{w}=A_{1}\sqcup...\sqcup
A_{d}$ with such property:  Let initially every word from $X^{w}$ have 1 coin.
Then $h_{i}$ moves a coin from every $a_{i}\in A_{i}$ to $h_{i}(a_{i})$,
$1\leq i\leq d$. After that every word from $X^{w}$ has at least 2 coins.

For arbitrary $l,s\in\mathbb{N}$, $s\geq 8$ consider the set of
$s\cdot|X|^{l}$ consecutive words
$F:=\\{w+1,...,w+s|X|^{l}\\}\subset X^{w}$ and its superset of $(s+2)|X|^{l}$
consecutive words
$F^{\prime}:=\\{w+1-|X|^{l},...,w+(s+1)|X|^{l}\\}$, put $\neg
F^{\prime}:=X^{w}\setminus F^{\prime}$. Split $F$ into subsets of $|X|^{l}$
consecutive words $F=F_{1}\sqcup...\sqcup F_{s}$. Notice that in every such
subset the beginnings (first $l$ letters) of words form the set $X^{l}$. Fix
an arbitrary $i\in\\{1...d\\}$. Denote $g_{i}=h_{i}^{-1}$ The number of words,
which are moved by $g_{i}$ from $F$ to $\neg F^{\prime}$ is not greater then
$s\cdot NS(h_{i},l)$. Actually, consider arbitrary $F_{j}\subset F$, $1\leq
j\leq s$. If for some $v\in F_{j}$, $g_{i}(v)$ is in $\neg F^{\prime}$, then
$g_{i}$ changes a letter with position number greater then $l$ in word $v$. It
means that if $g_{i}$ receives $v[:l]$ it doesn’t move to trivial state after
reading it. As $\\{v[:l]|v\in F_{j}\\}=X^{l}$, number of such words in $F_{j}$
is not greater then $NS(g_{i},l)=NS(h_{i},l)$. So in $F$ this number is not
greater then $s\cdot NS(h_{i},l)$.

The result can be reworded: the number of words in $\neg F^{\prime}$, from
which $h_{i}$ brings coins to $F$, is not greater then $s\cdot NS(h_{i},l)$.
So, for each $i\in\\{1,...,d\\}$, $h_{i}$ brings not more then $s\cdot
NS(h_{i},l)$ coins to $F$ from $\neg F^{\prime}$. Then all $h_{i}$ bring at
most $s\cdot\sum_{i=1}^{d}NS(h_{i},l)$ coins. As
$NS(h_{i},l)=o(|X|^{l}),l\to\infty$, we can get

$s\cdot\sum_{i=1}^{d}NS(h_{i},l)\leq\frac{1}{4}s|X|^{l}$

by choosing large $l$. Therefore, if $|F|$ is quiet large, then the number of
coins, which are moved from $\neg F^{\prime}$ to $F$ is not greater then
$\frac{1}{4}|F|$. Since $s\geq 8$, $2\leq\frac{1}{4}s$, then at most
$(s+2)|X|^{l}\leq\frac{5}{4}s|X|^{l}=\frac{5}{4}|F|$ coins are moved to $F$
from $F^{\prime}$ (in particular from $F$). Together, the number of coins at
$F$ becomes at most $\frac{5}{4}|F|+\frac{1}{4}|F|=\frac{3}{2}|F|<2|F|$. It
means then some words of $F$ get less then 2 coins. Contradiction. ∎

######  Remark 1.

There are transformations, defined by infinite and not polynomial automata,
which satisfy conditions of Theorem 1. For example, all non-trivial states of
the following automaton define such transformations:

Each finite word without $0$ and $1$ moves $q_{i},i\geq 1$ to non-trivial
state. On the other hand, every word that contains $0$ moves them to the
trivial state. Therefore,
$2^{l}\leq NS(q_{i},l)\leq 3^{l}$, where $2^{l}$ is a number of words without
$1$ and $0$, $3^{l}$ \- without $0$ only. Since $\frac{3^{l}}{4^{l}}\to 0$,
$l\to\infty$, all the states $q_{i},i\geq 1$ are acceptable.

##  3 Automata, that ”almost always” move to cycles

Theorem 1 doesn’t cover some simple automata transformations, which act on
$X^{w}$ non-paradoxically, such as pictured below:

In theorem 1, ”most” of words must move the automaton to the trivial state. In
fact, we can generalise the condition.

######  Definition 1.

the states $g_{1},...,g_{n}$ of the same automaton form an unconditional cycle
(UC), if the transition functions $\pi(g_{i},\cdot),1\leq i\leq n$ don’t
depend of input data and have the form $g_{1}\to...\to g_{n}\to g_{1}$.

Apparently, a trivial state is an instance of UC. We will say that a word
$w\in X^{w}\cup X^{*}$ moves the automata transformation $g$ of the automaton
$A$ to a UC in $s$ steps, if $A$, receiving $w$ in $g$, gets into one of the
states of the UC after processing first $s$ letters. Notice the following:

######  Proposition 2.

Assume that $w\in X^{l}$ moves $g$ to an UC of length $n$ and $g(w)$ moves $h$
to an UC of length $m$. Then $w$ moves $gh$ to some UC of length $LCM(n,m)$.

###### Proof.

We consider $gh$ as a state $(g,h)$ of $A*B$. Let $w$ move $g$ to the UC
$g_{1},...,g_{n}$ in $s$ steps and $g(w)$ move $h$ to the UC $h_{1},...,h_{m}$
in $t$ steps. Then after processing first $max\\{s,t\\}$ letters of $w$ the
state $(g,h)$ moves to the UC $(g_{1},h_{1}),...,(g_{n},h_{m})$ of length
$LCM(n,m)$. ∎

For arbitrary automata transformation $g$ denote by $NC_{g}(l)$ a number of
words with length $l$ which don’t move $g$ to any UC, and by
$\mathbb{NC}(g,l)$ \- a set of infinite words that start from them. In other
words, $\mathbb{NC}(g,l)\subset X^{w}$ consists of words that don’t move $g$
to any UC while processing the first $l$ letters.

######  Proposition 3.

$NC(g,l)$ has the following properties:
$(1^{\prime}):\;\;NC(g,l)=NC(g^{-1},l)$
$(2^{\prime}):\;\;NC(gh,l)\leq NC(g,l)+NC(h,l)$,
where $g,h$ are arbitrary automata transformations, $l\in\mathbb{N}$

###### Proof.

$(1^{\prime})$ We are going to show that if $w\in X^{l}$ moves $g$ to the UC
$g_{1},...,g_{n}$ then $g(w)\in X^{l}$ moves $g^{-1}$ to the UC
$g_{1}^{-1},...,g_{n}^{-1}$. Consider the Moore diagram of some automaton $A$,
that contains $g$. Starting from $g$ and moving along left labels that form
the word $w$, we achieve the UC $g_{1},...,g_{n}$ in $k\leq l$ steps. Let us
swap all the left labels with right ones that correspond to them. After
renaming the states $h\to h^{-1}$ we get a Moore digram of the automaton
$A^{-1}$. This transformation keeps UC, moreover, starting from $g^{-1}$ and
moving along left labels that form $g(w)$, we achieve the UC
$g_{1}^{-1},...,g_{n}^{-1}$ in $k$ steps. So if $w\in X^{l}$ moves $g$ to the
UC $g_{1},...,g_{n}$ then $g(w)\in X^{l}$ moves $g^{-1}$ to the UC
$g_{1}^{-1},...,g_{n}^{-1}$. As $g$ is a bijection, we have $NC(g^{-1},l)\leq
NC(g,l)$. Similarly an opposite inequality can be gotten.

$(2^{\prime})$ Assume that $w\in X^{l}$ moves $g$ to some UC and $g(w)$ moves
$h$ to some (maybe another) UC. Then according to proposition 1 $w$ moves $gh$
to an $UC$. The rest of the proof is similar to one of $(2)$. We just have to
replace $NS\to NC$, $\mathbb{NS}\to\mathbb{NC}$, $\mathbb{S}\to\mathbb{C}$. ∎

Now we can see that automata transformations $g$ for which
$NC(g,l)=o(|X|^{l}),l\to\infty\\\ $ form a group. Denote it by $G_{1}$.
Generalising theorem 1, we are going to prove the next statement:

######  Theorem 2.

$X^{w}$ is not $G_{1}$-paradoxical.

We need two auxiliary lemmas. Let us say that a word $w\in X^{w}$ is
$l-$almost periodic if it has the form $w=uv$ where $u\in X^{l}$ is arbitrary
and $v$ is periodic. Mentioning the period, we mean the shortest repeating
word from $X^{*}$, that starts from $(l+1)th$ position of $w$. For example,
word $123010101$ as a $3-$almost periodic word has period $01$. But as a
$4-$almost periodic word it has period $10$.

######  Lemma 1.

Let $w$ be $l-$almost periodic word with a period of length $t$. Assume that
$w$ moves an automata transformation $g$ to UC of length $c$ in at most $l$
steps. Then $g(w)$ is $l-$almost periodic and the length of it’s period
divides $LCM(t,c)$.

###### Proof.

When the automaton has already processed the first $l$ letters of $w$, the
following holds:

  * •

Every $c$ steps the automaton moves to the same state.

  * •

Every $t$ steps the automaton receives the same letter.

Therefore, every $LCM(t,c)$ steps it receives the same letter in the same
state, so gives the same data to the output. ∎

Denote by $P_{n}^{l}$ the set of all $l-$almost periodic infinite words with
the length of period dividing $n!$.

######  Lemma 2.

Let $g$ be an automata transformation. Denote by $n(l)$ the maximal length of
UC $g$ can move to after processing a word of length $l$. For arbitrary $c\geq
n(l)$ there holds:

$g(P_{c}^{l}\setminus\mathbb{NC}(g,l))\subseteq P_{c}^{l}$

###### Proof.

Consider an arbitrary word $w\in P_{c}^{l}\setminus\mathbb{NC}(g,l)$. Let the
automaton $A$, containing $g$, receive $w$ in the state $g$. After processing
the first $l$ symbols by $A_{g}$, the periodic part of $w$ has already
started. Besides that, $A_{g}$ has already moved to the UC (by definition of
$\mathbb{NC}(g,l)$). Since $w\in P_{c}^{l}$, then the length of it’s period
divides $c!$. A length of the UC is not greater then $n(l)\leq c$, so it also
divides $c!$. According to lemma 1, $g(w)$ is $l-$almost periodic and length
of it’s period divides $LCM(c!,c!)=c!$. Therefore, $g(w)\in P_{c}^{l}$. ∎

Now we are ready to start the proof of theorem 2.

###### Proof.

Assume that $X^{w}$ is $G_{1}$-paradoxical. Then there are the elements
$h_{1},...,h_{d}$ of $G_{1}$ and the partition $X^{w}=A_{1}\sqcup...\sqcup
A_{d}$ with such property:  Let initially every word from $X^{w}$ has 1 coin.
Then $h_{i}$ moves a coin from every $a_{i}\in A_{i}$ to $h_{i}(a_{i})$,
$1\leq i\leq d$. After that every word from $X^{w}$ has at least 2 coins.

Consider the set $P_{N}^{l}$, where $l$ will be defined later and $N=N(l)$ is
the maximal length of UC that $h_{1},...h_{d}$ can move to while processing
words of length $l$. Fix an arbitrary $i\in\\{1,...,d\\}$. Denote
$g_{i}=h_{i}^{-1}$. According to lemma 2,
$g_{i}(P_{N}^{l}\setminus\mathbb{NC}_{g_{i}(l)})\subseteq P_{N}^{l}$. So
$g_{i}$ can move at most $|P_{N}^{l}\cap\mathbb{NC}_{g_{i}(l)}|$ words from
$P_{N}^{l}$ outside it. Estimate the number. Let $\mathbb{T}_{N}$ be the set
of all periods $T\in X^{*}$ with length dividing $N!$. For each
$T\in\mathbb{T}_{N}$ denote by $P_{(T)}^{l}$ the set of $l-$almost periodic
infinite words with period $T$. Then we have:

$P_{N}^{l}=\bigsqcup_{T\in\mathbb{T}_{N}}P_{(T)}^{l}$
$P_{N}^{l}\cap\mathbb{NC}(g_{i},l)=\bigsqcup_{T\in\mathbb{T}_{N}}(P_{(T)}^{l}\cap\mathbb{NC}(g_{i},l))$

Notice that for each $v\in X^{l}$ there is exactly 1 word starting from $v$ in
every $P_{(T)}^{l},T\in\mathbb{T}_{N}$. Therefore $|P_{(T)}^{l}|=|X|^{l}$, in
particular

$|P_{(T)}^{l}\cap\mathbb{NC}(g_{i},l)|=NC(g_{i},l)$
$|P_{N}^{l}\cap\mathbb{NC}(g_{i},l)|=\sum_{T\in\mathbb{T}_{N}}|P_{(T)}^{l}\cap\mathbb{NC}(g_{i},l)|=|\mathbb{T}_{N}|\cdot
NC(g_{i},l)$

So, $g_{i}$ moves $|\mathbb{T}_{N}|\cdot NC(g_{i},l)$ words from $P_{N}^{l}$
outside it. It means that $h_{i}$ brings $|\mathbb{T}_{N}|\cdot NC(g_{i},l)$
coins from $X^{w}\setminus P_{N}^{l}$ to $P_{N}^{l}$. Then all
$h_{1},...,h_{d}$ bring at most $|\mathbb{T}_{N}|\sum_{i=1}^{d}NC(g_{i},l)$
coins from $X^{w}\setminus P_{N}^{l}$ to $P_{N}^{l}$. As there are
$|\mathbb{T}_{N}|\cdot|X|^{l}$ words in $P_{N}^{l}$ and
$NC(g_{i},l)=o(|X|^{l}),l\to\infty$, similarly to theorem 1 we have that
$h_{1},...h_{d}$ don’t bring enough coins to $P_{N}^{l}$ for large $l$. ∎

## References

  * [1] Stan Wagon. The Banach-Tarski Paradox. Cambridge University Press, 1985.
  * [2] R. I. Grigorchuk, V. V. Nekrashevich, V. I. Sushchanskii. Automata, dynamical systems, and groups. Grigorchuk R. I. (ed.), Dynamical systems, automata, and infinite groups. Proc. Steklov Inst. Math. 231 (2000), 128-203.
  * [3] V. Nekrashevych. Self-similar groups. Math. Surveys and Monographs 117. Amer. Math. Soc., Providence, RI, 2005.
  * [4] I. Bondarenko. Groups Generated by Bounded Automata and Their Schreier Graphs. PhD Dissertation (Texas $A\&M$ Univ., College Station, TX, 2007).
  * [5] Andrzej Zuk. Automata groups. Paris 7