# Boundedness properties of modified averaging operators and geometrically
doubling metric spaces

J. M. Aldaz and A. Caldera  Instituto de Ciencias Matemáticas (CSIC-UAM-
UC3M-UCM) and Departamento de Matemáticas, Universidad Autónoma de Madrid,
Cantoblanco 28049, Madrid, Spain<EMAIL_ADDRESS><EMAIL_ADDRESS>Departamento de Matemáticas, Universidad de Oviedo,
33007, Oviedo, Spain<EMAIL_ADDRESS>
###### Abstract.

We characterize the geometrically doubling condition of a metric space in
terms of the uniform $L^{1}$-boundedness of superaveraging operators, where
uniform refers to the existence of bounds independent of the measure being
considered.

2020 Mathematical Subject Classification. 30L99

Key words and phrases: _metric measure spaces, geometrically dobuling metric
spaces, superaveraging operators._

The first named author was partially supported by Grant PID2019-106870GB-I00
of the MICINN of Spain, by V PRICIT (Comunidad de Madrid - Spain), and also by
ICMAT Severo Ochoa project CEX2019-000904-S (MICINN)

The second named author was supported by ICMAT Severo Ochoa project
CEX2019-000904-S (MICINN)

##  1\. Introduction

It is shown in [Al1] that averaging operators are $L^{1}$-bounded on
geometrically doubling metric measure spaces. We complement this result, by
presenting a sharp variant of it. Call an operator superaveraging (cf.
Definition 2.3) if integration is performed over balls larger than the ones
appearing in the denominators. On geometrically doubling spaces,
superaveraging operators are always $L^{1}$-bounded, with bounds that depend
on the geometrically doubling constant of the space and on the expansion
factor $t$, but can be taken to be independent of the measure $\mu$, cf.
Theorem 4.7. Furthermore, for any expansion factor $t>1$, this type of
boundedness entails that the space is geometrically doubling, so in fact we
have an operator-theoretic characterization of the geometrically doubling
condition.

Boundedness on $L^{1}(\mu)$ of a superaveraging operator does not in general
imply boundedness on $L^{p}(\mu)$ for $p>1$, cf. Example 4.9, so to apply
interpolation arguments, it is interesting to know when boundedness on
$L^{\infty}(\mu)$ holds. We shall see that $L^{\infty}(\mu)$-boundedness of
the superaveraging operators for every $r>0$ and every $t>1$, is equivalent to
$\mu$ being doubling almost everywhere, cf. Corollary 4.12. But in that case
the $L^{p}$ boundedness for $1\leq p\leq\infty$ follows directly from doubling
a.e.; thus, $L^{1}$-$L^{\infty}$ interpolation is not useful in this context.

##  2\. Definitions and notation

We will use $B^{\operatorname{o}}(x,r):=\\{y\in X:d(x,y)<r\\}$ to denote
metrically open balls, and $B^{\operatorname{cl}}(x,r):=\\{y\in X:d(x,y)\leq
r\\}$ to refer to metrically closed balls (“open balls” and “closed balls”
will always be understood in the metric, not the topological sense). If we do
not want to specify whether balls are open or closed, we write $B(x,r)$. But
when we utilize $B(x,r)$, we assume that all balls are of the same kind, i.e.,
all open or all closed. To avoid trivialities, we will always suppose that
measures are not identically zero and that metric spaces contain at least two
points.

######  Definition 2.1.

A Borel measure is $\tau$-additive or $\tau$-smooth, if for every collection
$\\{U_{\alpha}:\alpha\in\Lambda\\}$ of open sets,

$\mu(\cup_{\alpha}U_{\alpha})=\sup_{\mathcal{F}}\mu(\cup_{i=1}^{n}U_{\alpha_{i}}),$

where the supremum is taken over all finite subcollections
$\mathcal{F}=\\{U_{\alpha_{1}},\dots,U_{\alpha_{n}}\\}$ of
$\\{U_{\alpha}:\alpha\in\Lambda\\}$. We say that $(X,d,\mu)$ is a metric
measure space if $\mu$ is a $\tau$-additive Borel measure on the metric space
$(X,d)$, such that $\mu$ assigns finite measure to bounded Borel sets.

We are only interested in locally bounded Borel measures, since we want balls
to have finite measure, so from now on we assume that this is always the case.
Next we present some motivation regarding our use of $\tau$-additive measures.
Trivially all Borel measures on a separable metric space are $\tau$-additive,
and likewise all Radon measures (that is, measures that are inner regular with
respect to the compact sets) on arbitrary metric spaces. In fact, if the
standard axioms ZFC for set theory are consistent, then it is consistent to
assume that all locally finite measures are $\tau$-additive (see [Bo,
Proposition 7. 2. 10] for more details).

All of this means that the assumption of $\tau$-additivity does not rule out
from the definition of metric measure spaces any metric space that can be
proven to exist using ZFC. Note, for instance, that the requirement of
separability excludes spaces such as $X=L^{\infty}([0,1],\lambda)$, where
$\lambda$ is the one-dimensional Lebesgue measure, and
$d(f,g)=\|f-g\|_{\infty}$. For us this is a perfectly good metric space. Note
also that in the theory of stochastic processes, probabilities on spaces of
functions come up naturally. So there is no a priori reason to remove from
consideration “large” metric spaces of functions endowed with locally finite
measures, or even just probabilities.

Next we recall the standard example of a measure that is not $\tau$-additive,
under the assumption that measurable cardinals do exist (measurable cardinals
are so large that their existence cannot be proven from the standard axioms
ZFC of set theory, unless these axioms are inconsistent; more precisely,
measurable cardinals serve as models of ZFC, therefore proving ZFC’s
consistency, so Gödel’s Second Incompleteness Theorem applies). Let $X$ have
measurable cardinality, and let $d$ be the standard $\\{0,1\\}$-valued
discrete metric, so all subsets are open. By definition of measurable cardinal
there exists a $\\{0,1\\}$-valued Borel measure that takes the value 0 on each
singleton, and assigns measure 1 to $X$. Clearly all finite unions of
singletons have measure zero and the union of all singletons has measure 1.

Recall that the complement of the support
$(\operatorname{supp}\mu)^{\operatorname{c}}:=\cup\\{B^{\operatorname{o}}(x,r):x\in
X,\mu(B^{\operatorname{o}}(x,r))=0\\}$ of a Borel measure $\mu$, is an open
set, and hence measurable.

######  Definition 2.2.

Let $(X,d)$ be a metric space and let $\mu$ be a locally finite Borel measure
on $X$. If $\mu(X\setminus\operatorname{supp}\mu)=0$, we say that $\mu$ has
full support.

By $\tau$-additivity, if $(X,d,\mu)$ is a metric measure space, then $\mu$ has
full support, since $X\setminus\operatorname{supp}\mu$ is a union of open
balls of measure zero. Actually, the other implication also holds, for the
support is always separable, so having full support is equivalent to
$\tau$-additivity (cf. [Bo, Proposition 7. 2. 10] for more details).

######  Definition 2.3.

Let $(X,d,\mu)$ be a metric measure space and let $g$ be a locally integrable
function on $X$. The modified averaging operators $A_{t,r,\mu}$ acting on $g$
are defined as follows: for each pair of positive numbers $t,r>0$ and each
$x\in\operatorname{supp}\mu$, set

(1) $A_{t,r,\mu}g(x):=\frac{1}{\mu(B(x,r))}\int_{B(x,tr)}g(y)\ d\mu(y).$

We shall speak of superaveraging operators if $t>1$, and of subaveraging
operators when $t<1$.

######  Remark 2.4.

Note that modified averaging operators $A_{t,r,\mu}$ acting on, say $g$, yield
functions defined almost everywhere, by $\tau$-additivity: if for some $y\in
X$ the function $A_{t,r,\mu}g$ is not defined at $y$, it is because
$\mu(B(y,r))=0$, from whence it follows that
$\mu(B^{\operatorname{o}}(y,r))=0$, and thus $y\in
X\setminus\operatorname{supp}\mu$.

Sometimes it is convenient to specify whether balls are open or closed; in
that case, we use $A_{t,r,\mu}^{\operatorname{o}}$ and
$A_{t,r,\mu}^{\operatorname{cl}}$ for the corresponding operators.
Furthermore, when we are considering only one measure $\mu$ we often omit it,
writing $A_{t,r}$ instead of the longer $A_{t,r,\mu}$.

##  3\. Some background results

######  Definition 3.1.

Let $t>0$. We call

$a_{t,r,\mu}(y):=\int_{X}\frac{\mathbf{1}_{B(y,tr)}(x)}{\mu(B(x,r))}\ d\mu(x)$

the conjugate function to the modified averaging operator $A_{t,r,\mu}$.

As before, when we consider only one measure $\mu$, we will often write
$a_{t,r}$ instead of $a_{t,r,\mu}$.

Averaging operators are bounded on $L^{1}(\mu)$ if and only if the
corresponding conjugate functions $a_{r,\mu}\in L^{\infty}(\mu)$, by [Al1,
Theorem 3.3]. The same argument (which we include for the reader’s
convenience) shows that this characterization also holds for the modified
averaging operators.

######  Theorem 3.2.

Let $t>0$ and let $(X,d,\mu)$ be a metric measure space. The averaging
operator $A_{t,r}$ is bounded on $L^{1}(\mu)$ if and only if $a_{t,r}\in
L_{\infty}(\mu)$, in which case $\left\|A_{t,r}\right\|_{L^{1}(\mu)\rightarrow
L^{1}(\mu)}=\left\|a_{t,r}\right\|_{\infty}$.

###### Proof.

Let $0\leq f\in L^{1}(\mu)$, and suppose $a_{t,r}\in L^{\infty}(\mu)$. Since
by Fubini-Tonelli

$\|A_{t,r}f\|_{L^{1}}=\int_{X}A_{t,r}f(x)\
d\mu(x)=\int_{X}\int_{X}\frac{\mathbf{1}_{B(x,rt)}(y)}{\mu(B(x,r))}f(y)\
d\mu(y)\ d\mu(x)$
$=\int_{X}f(y)\int_{X}\frac{\mathbf{1}_{B(y,rt)}(x)}{\mu(B(x,r))}\ d\mu(x)\
d\mu(y)=\int_{X}f(y)\ a_{t,r}(y)\ d\mu(y),$

it follows from Hölder’s inequality that $\|A_{t,r}\|_{L^{1}(\mu)\to
L^{1}(\mu)}\leq\|a_{t,r}\|_{\infty}.$

On the other hand, we claim that if $\|A_{t,r}\|_{L^{1}(\mu)\to
L^{1}(\mu)}\leq C$, then $\|a_{t,r}\|_{\infty}\leq C.$ Towards a
contradiction, suppose $C<\|a_{t,r}\|_{\infty}$ (including the case
$\|a_{t,r}\|_{\infty}=\infty$). Then there is a $\lambda>C$ and a measurable
set $A_{\lambda}$ such that $A_{\lambda}\subset\\{a_{t,r}>\lambda\\}$ and
$0<\mu(A_{\lambda})<\infty$. Let $f:=\mathbf{1}_{A_{\lambda}}\in L^{1}(\mu)$.
Then

$\|A_{t,r}f\|_{L^{1}}=\int_{X}f(y)\ a_{t,r}(y)\
d\mu(y)>\int_{A_{\lambda}}\lambda\
d\mu(y)=\lambda\mu(A_{\lambda})>C\|f\|_{L^{1}},$

thereby contradicting the assumption $\|A_{t,r}\|_{L^{1}(\mu)\to
L^{1}(\mu)}\leq C$. ∎

######  Corollary 3.3.

Let $t\in(0,1/2]$ and let $(X,d)$ be a metric space. Then for every locally
finite, $\tau$-additive Borel measure $\mu$ on $X$, the subaveraging operator
$A_{t,r,\mu}$ satisfies $\left\|A_{t,r,\mu}\right\|_{L^{1}(\mu)\rightarrow
L^{1}(\mu)}\leq 1$.

###### Proof.

Note that if $\mathbf{1}_{B(y,rt)}(x)=1$, then $B(y,rt)\subset B(x,r)$, since
$t\leq 1/2$. Thus, for every $y\in X$, we have $a_{t,r,\mu}(y)\leq 1$. ∎

##  4\. Geometrically doubling metric spaces

######  Definition 4.1.

Let $(X,d)$ be a metric space. A strict $r$-net (resp. non-strict $r$-net) in
$X$ is a subset $S\subset X$ such that for any pair of distinct points $x,y\in
S$, we have $d(x,y)>r$ (resp. $d(x,y)\geq r$).

We speak of an $r$-net if we do not want to specify whether it is strict or
not. To ensure disjointness of the balls $B(x,r/2)$, $r$-nets are always taken
to be strict when working with closed balls; otherwise, we assume $r$-nets are
non-strict.

######  Definition 4.2.

A metric space is geometrically doubling if there exists a positive integer
$D$ such that every ball of radius $r$ can be covered with no more than $D$
balls of radius $r/2$. We call the smallest such $D$ the geometrically
doubling constant of the space.

We use $D^{\operatorname{o}}$ and $D^{\operatorname{cl}}$ to refer to the
geometrically doubling constants for open and for closed balls. It is easy to
see, by enlarging balls slightly, that the geometrically doubling condition is
satisfied for open balls if and only if it is satisfied for closed balls, but
the constants will in general be different. By analogy with previous notation,
we use $M^{\operatorname{cl}}$ and $M^{\operatorname{o}}$ for the maximum
sizes of strict and non-strict $r$-nets respectively, in balls of radius $r$.

######  Remark 4.3.

Let $X$ be geometrically doubling with constant $D$, and let $M_{2}$ be the
maximum cardinality of an $r/2$-net in $B(x,r)$, taken over all $x\in X$ and
all $r>0$. It easily follows from a maximality argument that $D\leq M_{2}$:
the balls of radius $r/2$ centered at each of the points of a maximal
$r/2$-net must cover all of $B(x,r)$, for any point not covered could be added
to the supposedly maximal $r/2$-net. On the other hand, if $M$ is the maximum
cardinality of an $r$-net in $B(x,r)$, taken over all $x\in X$ and all $r>0$,
then $M\leq D$: a ball of radius $r/2$ can contain at most one point of an
$r$-net.

######  Example 4.4.

With the preceding notation, it may happen that $D<M_{2}$. Consider the open
balls case on $\mathbb{R}$. Note that $D^{\operatorname{o}}=3$, since
$(-1,1)=\\{0\\}\cup(-1,0)\cup(0,1)$, so $(-1,1)$ can be covered with 3 balls
of radius $1/2$, and no less than 3. However, $M^{\operatorname{o}}_{2}>3$:
the set $\\{-6/10,-1/10,4/10,9/10\\}$ is a $1/2$-net in $(-1,1)$, and the
balls of radius 1/2 centered at these points give us a cover of $(-1,1)$ for
which the minimal cardinality is not obtained.

######  Example 4.5.

To clarify the meaning of the geometrically doubling constant $D$, note first
that if $D=1$ then $X$ has only one point, a case excluded by assumption, so
$D\geq 2$.

Consider the special case $X=\mathbb{R}^{d}$ with the euclidean distance, and
$\mu=\lambda^{d}$, the $d$-dimensional Lebesgue measure. By translation and
dilation invariance, it is enough to consider collections of translates of
$B(0,1)$, such that the said collections cover $B(0,2)$. When $d=1$, it has
already been noted in the previous example that $D^{\operatorname{o}}=3$. On
the other hand, for closed balls clearly $[-2,2]=[-2,0]\cup[0,2]$, so
$D^{\operatorname{cl}}=2$.

When $d\geq 2$ we have that $2^{d}<D<5^{d}$. The inequalities $2^{d}<D<5^{d}$
follow from well known volumetric arguments. Since
$\lambda^{d}(B(0,2))=2^{d}\lambda^{d}B(0,1)$, at least $2^{d}$ translates of
$B(0,1)$ are needed to cover $B(0,2)$. Furthermore, since there must be some
overlap among the covering balls, we get $2^{d}<D$.

To see why $D<5^{d}$, let $\\{v_{1},\dots,v_{N}\\}$ be a maximal 1-net in
$B(0,2)\subset\mathbb{R}^{d}$. The maximality of $\\{v_{1},\dots,v_{N}\\}$
entails that $B(0,2)\subset\cup_{1}^{N}B(v_{i},1)$, so $D\leq N$. Since the
balls $B(v_{i},1/2)$ are disjoint, contained in $B(0,5/2)$, and do not form a
packing of $B(0,5/2)$, we conclude that $N<(5/2)^{d}/(1/2)^{d}=5^{d}$.

If we consider the $\ell^{\infty}$ norm on $\mathbb{R}^{d}$ instead of the
euclidean norm when $d\geq 2$, so balls are cubes with sides parallel to the
axes, it is clear that $D^{\operatorname{cl}}=2^{d}$, and not difficult to see
(for instance, by an induction argument) that $D^{\operatorname{o}}=3^{d}$.

Statements 1) and 2) of the next lemma can be found as part of [Hy, Lemma
2.3]. For ease in the applications we have added statements 3) and 4). The
ceiling function $\lceil t\rceil$ is defined as the least integer $n$
satisfying $t\leq n$.

######  Lemma 4.6.

Let $(X,d)$ be a metric space and let $N$ be a fixed positive integer. Each of
the following statements implies the next:

1) Every ball $B(x,r)\subset X$ can be covered with at most $N$ balls of
radius $r/2$.

2) For all $t\in(0,1)$, every ball $B(x,r)\subset X$ can be covered with at
most $N^{\lceil-\log_{2}t\rceil}$ balls of radius $tr$.

3) There exists a $t\in(1/2,1)$ such that every ball $B(x,r)\subset X$ can be
covered with at most $N$ balls of radius $tr$.

4) With $t\in(1/2,1)$ as in the preceding statement, every ball $B(x,r)\subset
X$ can be covered with at most $N^{\lceil-1/\log_{2}t\rceil}$ balls of radius
$r/2$.

###### Proof.

Let us check that 1) implies 2). For $0<t<1$, let $k$ be the unique positive
integer that satisfies $2^{-k}\leq t<2^{-k+1}$. By an inductive argument,
every ball $B(x,r)$ can be covered with at most $N^{k}$ balls of radius
$2^{-k}r\leq tr$. Since $k\geq-\log_{2}t>k-1$, we have that
$k=\lceil-\log_{2}t\rceil$.

Part 3) is a special case of part 2), since for $t\in(1/2,1)$, we have
$1=\lceil-\log_{2}t\rceil$. We mention that part 3) is also immediate from
part 1), just take a cover by balls of radius $r/2$ and enlarge the radii to
$tr$.

Finally, for 3) implies 4) we argue as in 1) implies 2): let $k$ be the unique
positive integer that satisfies $t^{k}\leq 1/2<t^{k-1}$, or equivalently, let
$k:=\lceil-1/\log_{2}(t)\rceil$. After covering $B(x,r)$ with at most $N$
balls of the form $B(w,tr)$, by hypothesis each one of these can also be
covered by at most $N$ balls of the form $B(v,t^{2}r)$. Iterating, we find
that $B(x,r)$ can be covered by at most $N^{\lceil-1/\log_{2}(t)\rceil}$ balls
of radius $rt^{k}\leq r/2$. ∎

Of course, part 4) is an immediate consequence of part 1); deriving part 4)
directly from the information given in part 3) yields the same qualitative
information (the space is geometrically doubling) but quantitatively weaker
bounds.

The subaveraging operators are pointwise dominated by the averaging operators,
and these are uniformly (on $r>0$ and on $\mu$) bounded when the metric space
is geometrically doubling by Theorem [Al1, 3.5], so the next result deals only
with values of $t>1$. Essentially it says that the uniform boundedness of the
superaveraging operators for some $t>1$, or for all $t>1$, is equivalent to
the geometrically doubling condition. This is not the case for the averaging
operators, where the equivalence is given by a weaker property of Besicovitch
type, cf. [Al2, Theorem 4.7].

######  Theorem 4.7.

Let $(X,d)$ be a metric space, let $t>1$ and let $M_{t}$ be the supremum of
all cardinalities of $r$-nets in $B(x,tr)$, where the supremum is taken over
all $x\in X$ and all $r>0$.

Each of the following statements implies the next one:

1) The metric space $(X,d)$ is geometrically doubling, with geometrically
doubling constant $D$.

2) For every locally bounded $\tau$-additive Borel measure $\mu$, every $t>1$
and every $s>0$, the bound $\|A_{t,s,\mu}\|_{L^{1}(\mu)\to L^{1}(\mu)}\leq
M_{t}\leq D^{\lceil\log_{2}2t\rceil}$ holds.

3) There exist a $t\in(1,2)$ and a $C=C(t)>0$ such that for every $s>0$ and
every finite weighted sum of Dirac deltas
$\mu:=\sum_{i=1}^{N}c_{i}\delta_{x_{i}}$, the bound
$\|A_{t,s,\mu}\|_{L^{1}(\mu)\to L^{1}(\mu)}\leq C$ holds.

4) With $t$ and $C$ as in the previous statement, the metric space $(X,d)$ is
geometrically doubling, with geometrically doubling constant bounded by
$C^{\lceil 1/\log_{2}(t)\rceil}$.

###### Proof.

For 1) implies 2) we present only a sketch of the proof, referring the
interested reader to the almost identical proof of Theorem [Al1, 3.5], where a
more complete argument can be found. The only difference lies in the fact that
since $t>1$, instead of the bound $M\leq D$ one obtains $M_{t}\leq
D^{\lceil\log_{2}2t\rceil}$. Some details follow.

Without loss of generality suppose that $X=(\operatorname{supp}\mu)$. Fix
$y\in X$, and let $0<\varepsilon\ll 1$. We show that $a_{t,s}(y)\leq M_{t}$.
Noticing that $b_{1}\coloneqq\text{inf}\\{\mu(B(x,s)):x\in B(y,ts)\\}>0$, we
choose $u_{1}\in B(y,ts)$ such that $\mu(B(u_{1},s))<(1+\varepsilon)b_{1}$.
Let $b_{2}\coloneqq\text{inf}\\{\mu(B(x,s)):x\in B(y,ts)\setminus
B(u_{1},s)\\}$, and select $u_{2}\in B(y,ts)\setminus B(u_{1},s)$ so that
$\mu(B(u_{2},s))<(1+\varepsilon)b_{2}$; repeat until the process cannot be
continued. This happens in at most $M_{t}$ steps, since the selected centers
$u_{k}$ form an $s$-net $S$ in $B(y,ts)$. Denote by $m$ the cardinality of
$S$. For every $x\in B(y,ts)$ we have

$\frac{\mathbf{1}_{B(y,ts)}(x)}{\mu(B(x,s))}\leq(1+\varepsilon)\sum_{i=1}^{m}\frac{\mathbf{1}_{B(y,ts)\cap
B(u_{i},s)}(x)}{\mu(B(u_{i},s))}.$

Integrating,

$a_{t,s}(y)=\int_{X}\frac{\mathbf{1}_{B(y,ts)}(x)}{\mu(B(x,s))}\hskip
2.0ptd\mu(x)\leq\int_{X}(1+\varepsilon)\sum_{i=1}^{m}\frac{\mathbf{1}_{B(u_{i},s)}(x)}{\mu(B(u_{i},s))}\hskip
2.0ptd\mu(x)\leq(1+\varepsilon)M_{t}.$

Letting $\varepsilon\downarrow 0$, we conclude from Theorem 3.2 that
$\left\|A_{t,s}\right\|_{L^{1}(\mu)\rightarrow L^{1}(\mu)}\leq M_{t}$. As in
Remark 4.3, we recall that each ball of radius $s/2$ can contain at most one
point of an $s$-net, so to bound $M_{t}$ from above it is enough to estimate
the number of balls of radius $s/2$ needed to cover $B(y,ts)$. But by part 2)
of Lemma 4.6, we know that $D^{\lceil\log_{2}2t\rceil}$ balls of radius $s/2$
suffice.

Since 2) implies 3) is trivial, with $C=M_{t}$, we only need to show that 3)
implies 4), so suppose there is a $t\in(1,2)$ such that for all discrete
measures $\mu$ with finite support, and all $s>0$, we have
$\|A_{t,s,\mu}\|_{L^{1}(\mu)\to L^{1}(\mu)}\leq C$. By part 3) of Lemma 4.6,
to obtain the geometrically doubling condition it is enough to show that one
can cover the large ball with a fixed number of smaller balls, where the
radius is contracted not necessarily by 1/2, but by any number strictly less
than 1. The assumption $t<2$ is for mere convenience: of course, if we have
boundedness for some $t\geq 2$, we also have it for $t<2$.

Note that before we can take an $s$-net of maximal cardinality, we need to
show that it is not possible to have an infinite $s$-net inside a ball. To
this end, select a ball $B(x,r)$ and a finite $r/t$-net
$S:=\\{y_{1},\dots,y_{m}\\}\subset B(x,r)$. For $0<c\ll 1$ define
$\mu_{c}:=c\delta_{x}+\sum_{i=i}^{m}\delta_{y_{i}}$, and set
$f_{c}:=c^{-1}\mathbf{1}_{\\{x\\}}$. Then $\|f_{c}\|_{L^{1}(\mu_{c})}=1$. Next
we use the bounds satisfied by the superaveraging operators, for the given
value of $t\in(1,2)$ and $s=r/t$, so by hypothesis
$\|A_{t,r/t,\mu_{c}}f\|_{L^{1}(\mu_{c})}\leq C.$ Since $S$ is an $r/t$-net,
any ball of radius $r/t$ centered at a point of $S$ contains only one point of
$S$, namely its center. These balls also might contain $x$, so for all
$j=1,\dots,m$, we have $1\leq\mu_{c}(B(y_{j},r/t))\leq 1+c$. On the other
hand, when we apply the expansion factor $t$ to the radius $r/t$, we find that
for every $y_{j}$, $j=1,\dots,m$, we do have $x\in B(y_{j},r)$. Thus

$1\geq A_{t,r/t,\mu_{c}}f(y_{j})\geq\frac{1}{1+c},$

so

$\frac{m}{1+c}\leq\|A_{t,r/t,\mu_{c}}f_{c}\|_{L^{1}(\mu_{c})}\leq C,$

and we conclude that $m\leq C$ by letting $c\to 0$. Now every finite $r/t$-net
in $B(x,r)$ has cardinality bounded by $C$, so there are no $r/t$-nets of
infinite cardinality contained in $B(x,r)$. Choose a maximal $r/t$-net
$S^{\prime}$ of points in $B(x,r)$, with respect to the partial order given by
inclusion. By maximality of $S^{\prime}$ we conclude that $\\{B(w,r/t):w\in
S^{\prime}\\}$ is a cover of $B(x,r)$, of cardinality bounded by $C$. Using
part 4) of Lemma 4.6, we see that the geometrically doubling constant of the
space is bounded by $C^{\lceil 1/\log_{2}(t)\rceil}$. ∎

The next corollary restates the “extrapolation” part of the preceding result:
boundedness of the superaveraging operators for one single $t>1$ implies the
boundedness for all $t>1$, thought of course the bounds will be larger for
larger values of $t$.

######  Corollary 4.8.

Let $(X,d)$ be a metric space. If there exist a $t>1$ and a $C=C(t)>0$ such
that for every $s>0$ and every finite weighted sum of Dirac deltas
$\nu:=\sum_{i=1}^{N}c_{i}\delta_{x_{i}}$, the bound
$\|A_{t,s,\nu}\|_{L^{1}(\nu)\to L^{1}(\nu)}\leq C$ holds, then for every $t>1$
there exists a constant $C(t)>0$ such that for every locally bounded
$\tau$-additive Borel measure $\mu$ and every $s>0$, the bound
$\|A_{t,s,\mu}\|_{L^{1}(\mu)\to L^{1}(\mu)}\leq C(t)$ holds.

######  Example 4.9.

Let $p>1$. The boundedness on $L^{1}(\mu)$ of a superaveraging operator does
not imply the boundedness on $L^{p}(\mu)$, as the following example shows.

It is immediate from the characterization using $r$-nets that every subset of
a geometrically doubling metric space is geometrically doubling. Let $(X,d)$
be the following subset (hence geometrically doubling) of the euclidean plane
with the inherited distance: define $X:=\\{0,1/2\\}\times\mathbb{N}$. Let
$\mu$ be the counting measure on $\\{1/2\\}\times\mathbb{N}$, and on
$\\{0\\}\times\mathbb{N}$, set $\mu\\{(0,n)\\}=1/n$. Writing
$f_{n}:=\mathbf{1}_{\\{(1/2,n)\\}}$, for all $p\in[1,\infty]$ we have
$\|f_{n}\|_{p}=1$. For convenience we shall use closed balls, with $r=1/4$ and
$t=2$, so when $n>0$, we have $A_{2,1/4,\mu}^{\operatorname{cl}}f_{n}(0,n)\geq
n/2$. Clearly $A_{2,1/4,\mu}^{\operatorname{cl}}$ is not bounded on
$L^{\infty}(\mu)$, and for $1<p<\infty$,

$\|A_{2,1/4,\mu}^{\operatorname{cl}}f_{n}\|_{L^{p}(\mu)}\geq\left(\frac{n^{p}}{2^{p}n}\right)^{1/p},$

so $A_{2,1/4,\mu}^{\operatorname{cl}}$ is not bounded on $L^{p}(\mu)$ either.

On the other hand, if $r\geq 1/2$, then $\mu(B^{\operatorname{cl}}(x,r))\geq
1$ for all $x\in X$, so it easily follows that for every $t>1$ and every
$p\geq 1$ we have boundedness of $A_{t,r,\mu}^{\operatorname{cl}}$ on
$L^{p}(\mu)$.

In view of the preceding example, it is natural to ask under which conditions
is $A_{t,r,\mu}$ bounded on $L^{\infty}(\mu)$, so that interpolation can be
carried out. Next we show that boundedness for all $t$ and $r$ is equivalent
to $\mu$ being doubling almost everywhere.

######  Theorem 4.10.

Let $(X,d,\mu)$ be a metric measure space. Fix $t>0$ and $r>0$. Then
$\|A_{t,r,\mu}\|_{L^{\infty}(\mu)\to
L^{\infty}(\mu)}=\left\|\dfrac{\mu(B(\cdot,tr))}{\mu(B(\cdot,r))}\right\|_{L^{\infty}(\mu)}$.

###### Proof.

To see that

$\left\|\dfrac{\mu(B(\cdot,tr))}{\mu(B(\cdot,r))}\right\|_{L^{\infty}(\mu)}\leq\|A_{t,r,\mu}\|_{L^{\infty}(\mu)\to
L^{\infty}(\mu)},$

just take $f\equiv 1$ and note that for every $x\in\operatorname{supp}\mu$, we
have

$A_{t,r,\mu}f(x)=\dfrac{\mu(B(x,tr))}{\mu(B(x,r))}.$

In order to prove

$\left\|\dfrac{\mu(B(\cdot,tr))}{\mu(B(\cdot,r))}\right\|_{L^{\infty}(\mu)}\geq\|A_{t,r,\mu}\|_{L^{\infty}(\mu)\to
L^{\infty}(\mu)},$

select $f\in L^{\infty}(\mu)$ and note that for every
$x\in\operatorname{supp}\mu$ we have

$|A_{t,r}f(x)|\leq\frac{1}{\mu(B(x,r))}\int_{B(x,tr)}|f|\
d\mu\leq\frac{\mu(B(x,tr))}{\mu(B(x,r))}\|f\|_{L^{\infty}(\mu)}\leq\left\|\dfrac{\mu(B(\cdot,tr))}{\mu(B(\cdot,r))}\right\|_{L^{\infty}(\mu)}\|f\|_{L^{\infty}(\mu)}.$

∎

######  Definition 4.11.

Let $(X,d,\mu)$ be a metric measure space. Then $\mu$ is doubling if there
exists a constant $C>1$ such that for all $x\in X$ and all $r>0$, we have
$\mu(B(x,2r))\leq C\mu(B(x,r))$. If there is a measure zero set $A$ such that
the restriction of $\mu$ to $X\setminus A$ is doubling, we say that $\mu$ is
doubling almost everywhere.

Examples of measures $\mu$ that are doubling almost everywhere but not
doubling are easy to find: just take one Dirac delta $\delta_{x}$ at any point
$x\in X$, or let $\lambda$ be the linear Lebesgue measure on the $x$-axis of
$\mathbb{R}^{2}$. It is clear from the definition that $\mu$ is doubling
almost everywhere if and only if

$\left\|\
\underset{r>0}{\sup}\left\\{\dfrac{\mu(B(\cdot,2r))}{\mu(B(\cdot,r))}\right\\}\
\right\|_{L^{\infty}(\mu)}<\infty,$

and by a standard iteration argument, the $2r$ in the numerator can be
replaced by any $tr$, provided $t>1$. Hence the following result is immediate
from Theorem 4.10.

######  Corollary 4.12.

Let $(X,d,\mu)$ be a metric measure space. Then the superaveraging operators
$A_{t,r,\mu}$ are bounded on $L^{\infty}(\mu)$ for all $r>0$ and all $t>1$, if
and only if $\mu$ is doubling almost everywhere.

## References

  * [Al1] Aldaz, J. M. Boundedness of averaging operators on geometrically doubling metric spaces. Ann. Acad. Sci. Fenn. Math. 44 (1) (2019), 497–503. Available at the Mathematics ArXiv.
  * [Al2] Aldaz, J. M. Kissing numbers and the centered maximal operator. J. Geom. Anal. 31 (2021), no. 10, 10194–10214. Available at the Mathematics ArXiv.
  * [Bo] Bogachev, V. I. Measure Theory. (2007), Springer-Verlag.
  * [Hy] Hytönen, Tuomas A framework for non-homogeneous analysis on metric spaces, and the RBMO space of Tolsa. Publ. Mat. 54 (2010), no. 2, 485–504.


# ACAV100M: Automatic Curation of Large-Scale Datasets for
Audio-Visual Video Representation Learning

Sangho Lee11footnotemark: 1, Jiwan Chung11footnotemark: 1, Youngjae Yu, Gunhee
Kim
Seoul National University Equal Contribution Thomas Breuel, Gal Chechik
NVIDIA Research  Yale Song
Microsoft Research  https://acav100m.github.io

###### Abstract

The natural association between visual observations and their corresponding
sound provides powerful self-supervisory signals for learning video
representations, which makes the ever-growing amount of online videos an
attractive source of training data. However, large portions of online videos
contain irrelevant audio-visual signals because of edited/overdubbed audio,
and models trained on such uncurated videos have shown to learn suboptimal
representations. Therefore, existing approaches rely almost exclusively on
datasets with predetermined taxonomies of semantic concepts, where there is a
high chance of audio-visual correspondence. Unfortunately, constructing such
datasets require labor intensive manual annotation and/or verification, which
severely limits the utility of online videos for large-scale learning. In this
work, we present an automatic dataset curation approach based on subset
optimization where the objective is to maximize the mutual information between
audio and visual channels in videos. We demonstrate that our approach finds
videos with high audio-visual correspondence and show that self-supervised
models trained on our data achieve competitive performances compared to models
trained on existing manually curated datasets. The most significant benefit of
our approach is scalability: We release ACAV100M that contains 100 million
videos with high audio-visual correspondence, ideal for self-supervised video
representation learning.

##  1 Introduction

Our long-term objective is learning to recognize objects, actions, and sound
in videos without the need for manual ground-truth labels. This is not only a
theoretically interesting problem, since it mimics the development of auditory
and visual perception by infants [22], it is also of immense practical
importance, since accurate manual labeling of audio-visual data is
impractical. Compared to self-supervised learning on static images [55, 30,
26, 13], audio-visual inputs pose additional challenges: large portions of a
video may contain no relevant information, and auditory and visual inputs may
not always be in correspondence. Consequently, existing self-supervised
methods on audio-visual data either start with datasets for which there is a
high probability of audio-visual correspondence, or they learn audio-visual
properties corresponding only to short-term statistical regularities. The
necessary datasets are usually manually created or rely on domain-specific
properties (e.g., [9, 21] and below). If we want to carry out self-supervised
learning on full length (minutes, hours) of video without manually generating
and/or selecting video clips, we need automated ways of curating such
collections of audio/video clips from diverse collections of full length
video.

Figure 1: We address the challenge of constructing a large-scale audio-visual
dataset from uncurated Internet videos without relying on manual annotation or
verification. We solve a constrained optimization problem that finds a subset
maximizing the mutual information between audio and visual signals in videos.
The result is a new 100M video dataset with high audio-visual correspondence,
ideal for self-supervised video representation learning.

We consider self-supervised learning from unlabeled videos as a two-step
process: (1) an automatic dataset curation process that generates short,
relevant clips with useful self-supervisory signals, e.g., audio-visual
correspondence, and (2) a self-supervised learning approach that operates on
the collection of short clips. This paper focuses on step (1) and not on step
(2), providing an automated way of taking a collection of general or domain-
specific videos of arbitrary length and reducing it to a collection of shorter
clips containing a high portion of relevant audio-video correspondences. The
output of this step is a dataset, which can be used as input to existing self-
supervised algorithms on audio-visual data [37, 3, 59], as well as the
development of novel self-supervised techniques.

To achieve step (1), we assume access to a large collection of unconstrained
videos and solve a subset selection problem with an information-theoretic
measure of audio-visual correspondence as a selection criterion. Specifically,
we find a subset that maximizes mutual information (MI) between audio and
visual channels of videos. This is a necessary condition for self-supervised
learning approaches that rely on audio-visual correspondence [18]. The main
technical challenge we address is how to efficiently measure the audio-visual
MI and find a subset that maximizes the MI in a scalable manner. Given that
video processing is notoriously compute and storage intensive, we put a
particular emphasis on scalability, i.e., we want an approach that can easily
handle hundreds of millions of video clips.

MI estimation has a long history of research [58, 38], including the recent
self-supervised approaches [55, 30, 13] that use noise contrastive estimation
[24] as the learning objective. While it is tempting to use such approaches to
estimate MI in our work, we quickly encounter the “chicken-and-egg” problem:
to obtain such models for estimating audio-visual MI, we need a training
dataset where we can reliably construct positive pairs with a high probability
of audio-visual correspondence; but that is what we are set out to find in the
first place! One might think that randomly chosen videos from the Internet
could be sufficient, but this has shown to produce suboptimal representations
[3]; our empirical results also show that self-supervised models indeed suffer
from noisy real-world audio-visual correspondences.

In this work, we turn to a clustering-based solution that estimates the MI by
measuring the agreement between two partitions of data [46, 72]. To circumvent
the “chicken-and-egg” issue, we use off-the-shelf models as feature extractors
and obtain multiple audio and visual clusters to estimate the MI. The use of
off-the-shelf models is a standard practice in video dataset generation.
Unlike existing approaches that use them as concept classifiers [8, 1, 47, 51,
12], here we use them as generic feature extractors. To avoid estimating the
MI based on a restricted set of concepts the off-the-shelf models are trained
on, we perform clustering over features computed across multiple layers
(instead of just the penultimate layers), which has been shown to provide
general feature descriptors not tied to specific concepts [81].

To make our approach scalable, we avoid using memory-heavy components such as
the Lloyd’s algorithm [57] and instead use SGD [7] to perform K-means
clustering. Further, we approximately solve the subset maximization objective
with a mini-batch greedy method [14]. Through controlled experiments with
ground-truth and noisy real-world correspondences, we show that our
clustering-based approach is more robust to the real-world correspondence
patterns, leading to superior empirical performances than the contrastive MI
estimation approaches.

We demonstrate our approach on a large collection of videos at an
unprecedented scale: We process 140 million full-length videos (total duration
1,030 years) and produce a dataset of 100 million 10-second clips (31 years)
with high audio-visual correspondence. We call this dataset ACAV100M (short
for automatically curated audio-visual dataset of 100M videos). It is two
orders of magnitude larger than the current largest video dataset used in the
audio-visual learning literature, i.e., AudioSet [21] (8 months), and twice as
large as the largest video dataset in the literature, i.e., HowTo100M [48] (15
years).

To evaluate the utility of our approach in self-supervised audio-visual
representation learning, we produce datasets at varying scales and compare
them with existing datasets of similar sizes that are frequently used in the
audio-visual learning literature, i.e., Kinetics-Sounds [4] at 20K-scale, VGG-
Sound [12] at 200K-scale, and AudioSet [21] at 2M-scale. Under the linear
evaluation protocol with three downstream datasets, UCF101 [67], ESC-50 [61],
and Kinetics-Sounds [4], we demonstrate that models pretrained on our datasets
perform competitively or better than the ones pretrained on the baseline
datasets, which were constructed with careful annotation or manual
verification.

To summarize, our main contributions are: 1) We propose an information-
theoretic subset optimization approach to finding a large-scale video dataset
with a high portion of relevant audio-visual correspondences. 2) We evaluate
different components of our pipeline via controlled experiments using both the
ground-truth and the noisy real-world correspondence patterns. 3) We release
ACAV100M, a large-scale open-domain dataset of 100M videos for future research
in audio-visual representation learning.

##  2 Related Work

Large-Scale Data Curation. Several different types of audio-visual video
datasets have been collected: (1) manually labeled, e.g., AudioSet [21], AVE
[70], (2) domain specific, e.g., AVA ActiveSpeaker [63], AVA Speech [11],
Greatest Hits [56], FAIR-Play [20], YouTube-ASMR-300K [80], and (3) unlabeled,
unrestricted collections from consumer video sites, e.g., Flickr-SoundNet [5,
4].

AudioSet [21] contains about 2M clips corresponding to audio events retrieved
from YouTube by keyword search; human raters verified the presence of audio
events in the candidate videos. Moments in Time [50] contains over one million
clips of diverse visual and auditory events; video clips were selected using
keywords (verbs) and manually reviewed for high correspondence between the
clips and the keywords. HowTo100M [48] contains 136M clips segmented from
1.22M narrated instructional web videos retrieved by text search from YouTube,
with an additional filtering step based on metadata. Web Videos and Text (WVT)
[69] contains 70M clips obtained by searching the web with keywords based on
the Kinetics-700 [9] categories and retaining both the video and the
associated text. Chen _et al_. [12] created a dataset of 200K clips for audio-
visual research; clips were originally obtained by keyword search on YouTube
and frames were classified with pretrained visual classifiers. Since keywords
and visual classes do not perfectly correspond, such correspondences needed to
be manually reviewed and corrected on randomly sampled clips in an iterative
and interactive process.

We are building systems for learning audio-visual correspondence on diverse,
unrestricted inputs. This requires large amounts of training data, making
manual collection and labeling costly and impractical. Unlike previous dataset
curation processes that involve costly human intervention, we introduce an
automatic and scalable data curation pipeline for large-scale audio-visual
datasets.

Subset Selection. Our work focuses on data subset selection; extensive prior
work exists in supervised [71, 77, 66, 76], unsupervised [25, 78], and active
learning settings [42, 65]. Different criteria for subset selection have been
explored in the literature. Submodular functions naturally model notions of
information, diversity and coverage [75], and can be optimized efficiently
using greedy algorithms [49, 53]. Geometric criteria like the coreset [2] aim
to approximate geometric extent measures over a large dataset with a
relatively small subset.

Mutual-information (MI) between input feature values and/or labels has been
used successfully [23, 43, 68] as a probablistically motivated criterion. We
propose to use MI as an objective function for subset selection and make the
following two unique contributions: First, we use MI to measure audio-visual
correspondence within videos by formulating MI between the audio and visual
features. Second, we apply MI for the large-scale video dataset curation
problem. In case of clustering-based MI estimation, we demonstrate that
optimizing MI objective with a greedy algorithm is a practical solution for
building a large-scale pipeline.

##  3 Data Collection Pipeline

Our pipeline consists of four steps: (i) acquiring raw videos from the web and
filtering them based on metadata, (ii) segmenting the videos into clips and
extracting features with pretrained extractors, (iii) estimating mutual
information (MI) between audio and visual representations, and (iv) selecting
a subset of clips that maximizes the MI.

###  3.1 Obtaining Candidate Videos

We crawl YouTube to download videos with a wide variety of topics. Unlike
previous work that use a carefully curated set of keywords [12], which could
inadvertently introduce bias, we aim for capturing the natural distribution of
topics present in the website. To ensure the diversity in topics, cultures and
languages, we create combinations of search queries with diverse sets of
keywords, locations, events, categories, etc., to obtain an initial video
list.

Before downloading videos, we process the search results using metadata
(provided by YouTube API) to filter out potentially low quality / low audio-
visual correspondence videos. We use the duration to exclude videos shorter
than 30 seconds (to avoid low quality videos) and longer than 600 seconds (to
avoid large storage costs). We also exclude videos that contain selected
keywords (in either title or description) or from certain categories – i.e.,
gaming, animation, screencast, and music videos – because most videos exhibit
non-natural scenes (computer graphics) and/or low audio-visual correspondence.
Finally, we detect language from the titles and descriptions using fastText
[33, 34] and keep the ones that constitute a cumulative ratio of $0.9$,
resulting in eight languages (English, Spanish, Portuguese, Russian, Japanese,
French, German, and Korean).

The result is 140 million full-length videos with a total duration of 1,030
years (median: 198 seconds). To minimize the storage cost we download 360p
resolution videos; this still consumes 1.8 petabytes of storage. Handling such
large-scale data requires a carefully designed data pipeline. We discuss our
modularized pipeline below.

###  3.2 Segmentation & Feature Extraction

Clip Segmentation. To avoid redundant clips, we extract up to three 10-second
clips from each full-length video. We do this by detecting shot boundaries
(using the scdet filter in FFmpeg) and computing pairwise clip similarities
based on the MPEG-7 video signatures (using the signature filter in FFmpeg).
We then select up to 3 clips that give the minimum total pairwise scores using
local search [32]. This gives us about 300M clips.

Feature Extraction. To measure correspondence between audio and visual
channels of the 300M clips, we need good feature representations. An ideal
representation would capture a variety of important aspects from low-level
details (e.g., texture and flow) to high-level concepts (e.g., semantic
categories). However, such an oracle extractor is hard to obtain, and the
sheer scale of data makes it impractical to learn optimal feature extractors
end-to-end. Therefore, we use the “off-the-shelf” pretrained models to extract
features, i.e., SlowFast [16] pretrained on Kinetics-400 [35] and VGGish [28]
pretrained on YouTube-8M [1] for visual and audio features, respectively.

###  3.3 Subset Selection via MI Maximization

Next, we select clips that exhibit strong correspondence between visual and
audio channels. To this end, we estimate the mutual information (MI) between
audio and visual signals. Computing the exact MI is infeasible because it
requires estimating the joint distribution of high dimensional variables, but
several approximate solutions do exist [73]. Here we implement and compare two
approaches: a noise-contrastive estimator (NCE) [24], which measures MI in a
continuous feature space, and a clustering-based estimator that computes MI in
a discrete space via vector quantization. The former estimates MI for each
video clip, while the latter estimates MI for a set of video clips. As we show
later in our experiments, we find the clustering-based MI estimator to be more
robust to real-world noise.

####  3.3.1 NCE-based MI Estimation

Contrastive approaches have become a popular way of estimating MI between
different views of the data [55, 30]. We add linear projection heads over the
precomputed audio/visual features and train them using the contrastive loss
[13]. From a mini-batch $\\{(v_{i},a_{i})\\}_{i=1}^{N_{b}}$ where $v_{i}$ and
$a_{i}$ are visual and audio features, respectively, we minimize

$l(v_{i},{a_{i})}=-\log\frac{\exp(S(\mathbf{z}_{i}^{v},\mathbf{z}_{i}^{a})/\tau)}{\sum_{j=1}^{N_{b}}\exp(S(\mathbf{z}_{i}^{v},\mathbf{z}_{j}^{a})/\tau)},$
(1)

where $\mathbf{z}_{i}^{v}$ and $\mathbf{z}_{i}^{a}$ are embeddings from the
linear projection heads, $S(\cdot,\cdot)$ measures the cosine similarity, and
$\tau$ is a temperature term (we set $\tau=0.1$). For each mini-batch we
compute $l(v_{i},a_{i})$ and $l(a_{i},v_{i})$ to make the loss symmetric.

Once trained, we can directly use $S(\mathbf{z}^{v},\mathbf{z}^{a})$ to
estimate audio-visual MI and find a subset by taking the top $N$ candidates
from a ranked list of video clips.

####  3.3.2 Clustering-based MI Estimation

MI Estimation. Clustering is one of the classical ways of estimating MI [46,
72]. Given two partitions of a dataset $\mathbf{X}$ w.r.t. audio and visual
features, $\mathcal{A}=\\{\mathbf{A}_{1},\cdots,\mathbf{A}_{|\mathcal{A}|}\\}$
and $\mathcal{V}=\\{\mathbf{V}_{1},\cdots,\mathbf{V}_{|\mathcal{V}|}\\}$, we
estimate their MI as:

$\mbox{MI}(\mathcal{A},\mathcal{V})=\sum_{i=1}^{|\mathcal{A}|}\sum_{j=1}^{|\mathcal{V}|}\frac{|\mathbf{A}_{i}\cap\mathbf{V}_{j}|}{|\mathbf{X}|}\log\frac{|\mathbf{X}||\mathbf{A}_{i}\cap\mathbf{V}_{j}|}{|\mathbf{A}_{i}||\mathbf{V}_{j}|}.$
(2)

This formulation estimates MI in a discrete (vector-quantized) space induced
by clustering, and thus the quality of clustering affects the quality of the
estimator. A straightforward approach to obtaining $\mathcal{A}$ and
$\mathcal{V}$ is to cluster videos using the output from the penultimate
layers of the pretrained networks. However, this can introduce distributional
bias specific to the datasets on which the networks are pretrained [81, 74].
To address this issue, we cluster samples over each output space induced by
different layers of the networks. This allows the MI estimator to consider a
wide range of abstract concepts, from low-level (such as textures) to high-
level (such as object parts) [6].

Specifically, we use the feature spaces induced by the five convolutional
blocks from each of the SlowFast and VGGish feature extractors. We then
compute the average MI between all pairs of clusterings as our MI estimator.
Let
$\mathcal{CV}_{\mathbf{X}}^{(i)}=\\{\mathbf{V}_{1}^{(i)},\cdots,\mathbf{V}_{n_{i}}^{(i)}\\}$
and
$\mathcal{CA}_{\mathbf{X}}^{(i)}=\\{\mathbf{A}_{1}^{(i)},\cdots,\mathbf{A}_{m_{i}}^{(i)}\\}$
denote the clustering results induced by the $i$-th convolutional block of the
visual and audio feature extractors, respectively. We compute:

$F(\mathbf{X})=\sum_{(\mathcal{X},\mathcal{Y})\in\mathcal{C}_{\mathbf{X}}}\frac{\mbox{MI}(\mathcal{X},\mathcal{Y})}{{{}_{10}C_{2}}},$
(3)

where $\mathcal{C}_{\mathbf{X}}$ denotes the combination of two elements from
$\\{\mathcal{CV}_{\mathbf{X}}^{(i)}\\}_{i=1}^{5}\cup\\{\mathcal{CA}_{\mathbf{X}}^{(j)}\\}_{j=1}^{5}$
and ${}_{10}C_{2}$ denotes the number of 2-combinations out of 10 elements,
which equals to 45. This computes MI between layers from both within and
across the extractors of different modalities (referred to as combination
pairing scheme in Section 4.2).

Input: initial dataset $\mathbf{D}$, MI estimator $F$, target subset size $M$,
batch size $b$, selection size $s$

Output: $\mathbf{X}\subseteq\mathbf{D},|\mathbf{X}|=M$

$\mathbf{X}_{0}\leftarrow\emptyset,i\leftarrow 0$

while  _$|X_{i}| <M$_ do

Randomly sample
$\mathbf{B}\subseteq\mathbf{D}\backslash\mathbf{X}_{i},|\mathbf{B}|=b$

$\mathbf{Y}_{0}\leftarrow\emptyset,j\leftarrow 0$

while  _$j <s$_ do

$x\leftarrow\operatornamewithlimits{argmax}_{x\in\mathbf{B}\backslash\mathbf{Y}_{j}}F(\mathbf{X}_{i}\cup\mathbf{Y}_{j}\cup\\{x\\})$

$\mathbf{Y}_{j+1}\leftarrow\mathbf{Y}_{j}\cup\\{x\\},j\leftarrow j+1$

if  _$|\mathbf{X}_{i}\cup\mathbf{Y}_{j}|=M$_ then break

end while

$\mathbf{X}_{i+1}\leftarrow\mathbf{X}_{i}\cup\mathbf{Y}_{j},i\leftarrow i+1$

end while

$\mathbf{X}\leftarrow\mathbf{X}_{i}$

Return $\mathbf{X}$

Algorithm 1 Batch Greedy Subset Selection

Batch Greedy Subset Selection. Since the MI estimator $F(\cdot)$ is a function
of $\mathbf{X}$, we can formulate an optimization problem where the goal is to
find a subset $\mathbf{X}$ that maximizes $F(\mathbf{X})$. In general, finding
a global solution to problems such as ours is NP-hard and thus greedy
heuristic solutions are used instead [54]. However, they typically select one
sample in each iteration and re-evaluate the goodness function, e.g.,
$F(\cdot)$, on all the remaining candidates. This introduces a challenge to
our setting because the time complexity is quadratic to the size of the
population; this is clearly not scalable to 300 million instances.

Therefore, we approximate the typical greedy solution using the batch greedy
algorithm [14], as shown in Algorithm 1. It randomly samples a batch
$\mathbf{B}$ from the remaining pool of candidates, and searches for the next
element to be included in the active solution set only within $\mathbf{B}$.
This batch trick reduces the time complexity down to linear, i.e.,
$O(N\times|\mathbf{B}|)$, where $N$ is the size of the input dataset. We
demonstrate the efficacy of the algorithm in Section 4.

Stochastic Clustering. One missing piece in this pipeline is an efficient
clustering algorithm scalable to hundreds of millions of instances. The most
popular choice among various clustering methods is K-means clustering [79],
which is a special case of mixture density estimation for isotropic normal and
other densities. Typically, an expectation-maximization (EM) algorithm, such
as Lloyd’s [57], is used to find the cluster centers. Such algorithms require
repeated computation of the distances of all samples from all $k$ cluster
centers, followed by cluster assignment, until convergence. Lloyd’s algorithm
updates cluster centers only after each pass through the entire dataset. But
for very large datasets (like ours), a small subset usually contains enough
information to obtain good estimates of the cluster centers, meaning that EM-
style algorithms tend to take (perhaps too) many epochs to converge.

There are different strategies for addressing this issue, including random
sampling and subsetting, but a straightforward approach is to replace EM
algorithm with an SGD [45, 7, 64]. In such an approach, for large datasets,
convergence rate and final accuracy of the cluster centers are determined not
by the total dataset size, but by the learning rate schedule. A
straightforward SGD update rule is to compute the nearest cluster centers for
each sample in a batch and then update the cluster centers using a convex
combination of the cluster centers and their nearest samples, weighting the
samples with a learning rate $\lambda$ and the cluster centers with
$(1-\lambda)$. However, mixture density estimators in general suffer from the
problem that adding mixture components with zero probability does not change
the mixture density; in practice, this means EM and SGD-based algorithms may
end up with cluster centers that stop receiving updates at some point during
the optimization.

We address this problem by estimating the mixture component utilization rate
as the ratio of the total number of updates to the cluster center divided by
the total number of estimation steps, and reinitializing cluster centers when
that probability falls below $(1/k)^{2}$. In Section 4.2, we demonstrate that
our mini-batch SGD update shows comparable accuracy to batch update in
correspondence retrieval tasks.

| Natural Class Correspondence | Arbitrary Class Correspondence | Audio-Visual
---|---|---|---
Method | CIFAR10-Rotation | CIFAR10-Flip | MNIST-CIFAR10 | MNIST-FSDD | Kinetics-Sounds
Ranking-inner |  87.872 $\pm$ 0.002 |  87.044 $\pm$ 0.001 |  63.076 $\pm$ 0.001 |  64.453 $\pm$ 0.003 |  52.558 $\pm$ 0.002
Ranking-cos |  87.872 $\pm$ 0.002 |  87.044 $\pm$ 0.001 |  67.600 $\pm$ 0.002 |  61.893 $\pm$ 0.004 |  60.108 $\pm$ 0.001
Ranking-$l_{2}$ |  87.872 $\pm$ 0.002 |  87.044 $\pm$ 0.001 |  66.796 $\pm$ 0.001 |  62.933 $\pm$ 0.003 |  51.236 $\pm$ 0.001
Ours-Contrastive |  99.395 $\pm$ 0.000 |  99.480 $\pm$ 0.001 |  73.252 $\pm$ 0.040 |  73.733 $\pm$ 0.027 |  73.066 $\pm$ 0.036
Ours-Clustering |  87.292 $\pm$ 0.014 |  87.248 $\pm$ 0.010 |  77.224 $\pm$ 0.009 |  69.440 $\pm$ 0.049 |  88.705 $\pm$ 0.004
Table 1: Correspondence retrieval results. We conduct a total of five runs and
report the precision with the 99% confidence interval. We use the clustering
pairing scheme which gives the highest score in each configuration:
combination, except diagonal for Ranking-inner, Ranking-cos and Rank-$l_{2}$
on CIFAR10-Rotation and CIFAR10-Flip.

##  4 Evaluation on Correspondence Retrieval

We systematically evaluate different components of our pipeline with synthetic
correspondence-retrieval tasks, where we generate corresponding and non-
corresponding pairs using CIFAR-10 [39], MNIST [41] and FSDD [31]. In each
correspondence retrieval task, the goal is to discover the known corresponding
samples among the non-corresponding pairs. To show the generality of the
findings, we also experiment with Kinetics-Sounds [4] which exhibit real-world
audio-visual correspondence.

###  4.1 Experimental Setting

##### Datasets

We construct five datasets where each instance is a pair of samples with
different correspondence types.

1/2) CIFAR10-Rotation/Flip. We use images from five randomly selected
categories to construct a “positive pair” set, and use the rest for a
“negative pair” set. For the positive set, we create pairs of images by
sampling two different images from the same category (e.g., two images of a
bird), and apply a geometric transformation to one of them; we apply either a
90° CCW rotation (CIFAR10-Rotation) or a horizontal flip (CIFAR10-Flip). The
negative set follows the same process but each pair contains images from
different categories. We categorize this type of correspondence as “Natural
Class Correspondence” because pairings are made over natural semantic
categories.

3/4) MNIST-CIFAR10/FSDD. We use images from five digit categories to construct
a positive set and use the rest for a negative set. Different from above,
correspondence is defined via an arbitrary class-level mapping, e.g., “digit
0” images map to the “car” images in CIFAR-10 or “digit 0” audio samples in
FSDD. We take samples from the same categories to construct the positive set
and samples from different categories for the negative set. We call these
“Arbitrary Class Correspondence” to differentiate from above.

5) Kinetics-Sounds. Unlike the above datasets where the correspondence is
defined over class categories, here the correspondence is defined at the
sample level, i.e., a positive set contains pairs of audio and visual channels
of the same video, and a negative set contains randomly permuted pairs. We do
not utilize class labels to construct the dataset.

##### Methods

We compare our pipeline (both contrastive-based and clustering-based) to three
ranking-based approaches. All the methods use the same precomputed features.
For images, we use ResNet-50 [27] pretrained on ImageNet [15]. For videos, we
use SlowFast [16] pretrained on Kinetics-400 [35] and VGGish [28] pretrained
on YouTube-8M [1] for visual and audio features, respectively. For the ranking
baselines, we apply PCA [60] to reduce the feature dimensionality to 64 and
rank the instances based on three similarity metrics: inner product, cosine
similarity, and (negative) $l_{2}$ distance. Because all our datasets have an
equal number of positive and negative instances, we simply select the top 50%
instances as the retrieval result.

##### Protocol

We split each dataset into train and test partitions of the same size. We
conduct a total of five runs for each of the five datasets and report results
on the test splits. We use train sets only for the contrastive estimator to
train the projection heads. When constructing each dataset, we sample at most
$n=1000$ instances from each category of the source datasets. For the noise
contrastive estimator, we train the linear projection heads for 100 epochs
using the AMSGrad of Adam optimizer [62] with a learning rate of 2e-4. We
randomly take one sample from each class to build a mini-batch for class-level
correspondence datasets, and sample random $N_{b}=10$ clips to build a mini-
batch for the sample-level correspondence dataset. When applying our
clustering-based method, we perform the SGD K-means clustering with the
“ground-truth” number of centroids as the number of classes in each source
dataset; we use the batch greedy algorithm with a batch size $b=100$ and a
selection size $s=25$.

###  4.2 Ablation Results & Discussion

Table 1 shows that the two variants of our approach – contrastive and
clustering – achieve overall higher precision rates than the ranking
baselines. The contrastive approach performs well on the two datasets with the
“natural class correspondence,” conforming to the previous results that shows
contrastive learning is robust to geometric transformations [13]. The
clustering approach excels on Kinetics-Sounds that contains natural audio-
visual correspondence, which is closer to our intended scenario. Therefore, we
conduct various ablation studies on Kinetics-Sounds to validate different
components of our clustering-based approach.

Layers | Method | Precision
---|---|---
Single | Layer1 |  50.820 $\pm$ 0.014
Layer2 |  51.412 $\pm$ 0.011
Layer3 |  52.659 $\pm$ 0.012
Layer4 |  54.422 $\pm$ 0.012
Layer5 |  58.418 $\pm$ 0.030
Multiple | Diagonal |  71.450 $\pm$ 0.005
Bipartite |  76.969 $\pm$ 0.005
Combination |  88.705 $\pm$ 0.004
Table 2: Correspondence retrieval results on Kinetics-Sounds with different
clustering pairing schemes. We conduct a total of five runs and report the
precision with the 99% confidence interval.

Multi-Layer Clustering. All the feature extractors that we use consist of five
convolutional blocks. As discussed in Section 3.3.2, we cluster samples over
each of the five output spaces to capture a wide range of abstract concepts.
This raises a question: How should we combine audio-visual clusters for MI
estimation? Table 2 compares the single-layer approaches to multi-layer
approaches. Each of the single-layer approach estimates the audio-visual MI
based on a single pair of clustering results. We can see that the precision
increases as we use clustering results from higher layers. However, all
single-layer methods perform significantly worse than multi-layer variants.

We explore three options to select pairs of clusterings for MI estimation.
Diagonal computes an average MI across all five single-layer scores (with $L$
layers, this computes MI $L$ times), Bipartite computes an average MI between
all possible combinations of audio-visual clustering results ($L^{2}$ times),
and Combination (ours) computes an average MI between all possible
combinations of clustering results, regardless of modalities (${}_{2L}C_{2}$
times). We observe that the performance increases with the number of
connections as shown in the bottom rows of Table 2. This positive relationship
suggests that the consensus between layers from the same extractor, as well as
that across extractors, contributes to the clarity of correspondence signal.
We further experimented with different layer weights for the Combination
approach and found it to be robust to different weight distributions; we
provide the results in the supplementary material.

Figure 2: Greedy vs. batch greedy algorithms with varying selection-to-batch
size ratios, $s/b$. The shaded regions show 99% confidence intervals obtained
by five runs on Kinetics-Sounds. The batch greedy algorithm is robust when the
ratio is $\leqslant$ 25%. Figure 3: Sensitivity analysis on the number of
centroids. We determine under/over-clustering based on the ground-truth number
of class categories in Kinetics-Sounds ($c=32$). The shaded regions show 99%
confidence intervals over five runs.

Mini-Batch SGD K-means Clustering. We compared mini-batch SGD K-means [7] to
the standard EM (Lloyd’s) approach [57] and obtained very similar results on
Kinetics-Sounds: 88.705 $\pm$ 0.004 (SGD) versus 88.732 $\pm$ 0.005 (EM). This
shows that our SGD solution has negligible performance degradation while
enjoying a significantly less memory requirement than the standard EM
approach.

Batch Greedy Subset Selection. We explore how the use of mini-batches affects
the quality of the selected subsets. We compare the greedy algorithm and the
batch greedy algorithm with a batch size $b=160$ and varying selection sizes
$s=\\{5,10,20,40,80\\}$. As shown in Figure 2, the performance gap between the
greedy algorithm and the batch greedy algorithm is marginal (greedy: 98.970
vs. batch greedy with $(b,s)=(160,5)$: 98.020), which validates our use of the
batch greedy algorithm. While the batch size itself does not have a large
impact on the subset quality, the ratio of selection size to batch size
($s/b$) highly affects the retrieval performance; the performance drops
sharply as the ratio exceeds 0.25 in several ($b$, $s$) configurations. This
is mainly dataset-dependent: by construction, there is a 50% chance that a
sample will be a positive. We believe that the constructed dataset contains
roughly 25% easy positives, i.e., videos with very high correspondence. When
the selection ratio $s/b$ does not exceed the easy positive ratio, the batch
greedy algorithm finds those videos without introducing false positives,
providing robustness. We found similar patterns with other ratios of
$s/b>25\%$.

Number of Centroids. We vary the number of centroids
$k\in\\{8,16,32,64,128\\}$ to see how sensitive our approach is to the
parameter. We apply the batch greedy algorithm with a batch size $b=100$ and a
selection size $s=25$ on Kinetics-Sounds. Figure 3 shows that, although the
final performance is similar across different number of centroids, they show
different trends: underclustering ($k=\\{8,16\\}$) shows high precision in
early iterations while overclustering ($k=\\{64,128\\}$) shows slower drop in
the later stage.

Figure 4: Linear evaluation on downstream tasks. The top-1/5 accuracy (%) of
video classification on UCF101 [67], audio classification on ESC-50 [61] and
audio-visual classification on Kinetics-Sounds (KS) [4]. We group the results
by the downstream tasks and by the scale of the pretrain datasets. Baselines
are Kinetics-Sounds [4] (20K), VGG-Sound [12] (200K), and AudioSet [21] (2M).

##  5 Large-Scale Evaluation

We construct datasets at varying scales (20K, 200K, 2M) and compare them to
existing datasets often used in the audio-visual learning literature:
Kinetics-Sounds [4] (20K), VGG-Sound [12] (200K), and AudioSet [21] (2M). Note
that all three datasets involve either human annotation [4, 21] or manual
verification [12]. To demonstrate the scalable nature of our approach, we also
generate datasets with 10M and 100M videos and evaluate their performance.

For the contrastive approach, we train linear projection heads on a batch size
of 1024 from a randomly drawn set of 100M videos. Note that these additional
videos are only used to train projection heads for MI estimation (Sec. 3.3.1),
which is discarded once dataset curation is finished; all approaches use the
same number of videos under the same evaluation protocol on all downstream
tasks. We train the model for three epochs and rank the entire video set
(300M) based on the cosine similarity [13]. We then take top
$N\in\\{20\text{K},200\text{K},2\text{M}\\}$ ranked videos for the final
dataset. For the clustering-based variant, we vary the number of clusters
$C\in\\{100,200,500,1000,2000\\}$ for each size of the datasets.

###  5.1 Linear Evaluation on Downstream Tasks

To assess the quality of the datasets, we pretrain identical models on
different datasets and evaluate their performance on downstream tasks. The
idea is that if a model performed particularly better than the others, the
dataset used to train that model must be superior to the other datasets. We
pretrain audio-visual CNNs from scratch using the self-supervised objective of
SimCLR [13]; we use 3D ResNet-50 [17] and ResNet-50 [27] as the visual and
audio CNNs, respectively. We follow the linear evaluation protocol [13] by
adding a linear classifier on top of the learned and frozen models. We test on
three downstream tasks: visual action recognition on UCF101 [67], sound
classification on ESC-50 [61], and audio-visual action recognition on
Kinetics-Sounds [4] (we concatenate audio-visual features for the linear
classifier). Note that the training procedures are identical for all the
models except for the datasets used to train them. We report mean accuracy
across the official splits of UCF101 and ESC-50. We provide details of these
experimental settings in the supplementary material.

Figure 4 shows that models pretrained on our dataset (green bars) achieve
similar, or even slightly better, performances compared to the baseline
datasets (pink bars) at 20K, 200K, and 2M scales. The significant gap between
ours vs. random set (yellow bars) shows the improvement does not come from the
initial pool we crawl (the 300M set) but rather come from higher portion of
audio-visual correspondence in the resulting dataset. Our clustering approach
to MI estimation (green bars) generally outperforms the contrastive approach
(blue bars), suggesting its robustness to noisy real-world audio-visual
correspondences. Finally, we report the results obtained from 10M and 100M
datasets produced with our clustering-based MI estimation module (we omit the
baseline results at these scales due to computational reasons). The
significant performance boost from the 10M and 100M models reaffirms the
importance of large-scale training. Considering our data curation process does
not involve human intervention (i.e., no manual annotation and verification)
this is a promising result showing the potential for large-scale self-
supervised learning: one can obtain datasets of arbitrary scales and develop
self-supervised models by leveraging high portion of audio-visual
correspondences provided in the datasets.

###  5.2 Human Evaluation

We conduct a user study to assess the perceived presence/absence of audio-
visual correspondence in video clips. We compare clips from four datasets:
AudioSet [21], VGG-Sound [12], ours with clustering (2M scale, 1K clusters),
and random (drawn from the 300M set). We prepare 100 randomly sampled clips
from each of these datasets, for a total of 400 clips. We recruit 12
participants and present each with 100 clips (25 clips per dataset), and ask
them whether audio and visual are corresponding or not. This provides us with
3 votes per video (we provide the details of the questionnaire in the
supplementary material).

Table 3 shows the majority voting accuracy and inter-rater agreement (measured
by Fleiss’ Kappa [19]). Every dataset has Fleiss’ Kappa greater than 0.4,
verifying the reliability of the accuracy statistics [40]. Ours significantly
improves audio-visual correspondence over a random subset (69% vs. 44%), and
is even rated slightly higher than AudioSet. The annotation process for
AudioSet has focused on audio events so we suspect that several of videos do
not contain visible sound sources. There is still a significant gap between
ours and VGG-Sound; we note that our process finds audio-visual correspondence
without relying on manual verification as was done in VGG-Sound.

Dataset | Majority Vote (%) | Fleiss’ Kappa
---|---|---
AudioSet | 65.66 | 0.4385
VGG-Sound | 84.00 | 0.4634
Ours (2M) | 69.00 | 0.5110
Random | 44.00 | 0.6112
Table 3: Human evaluation results assessing the perceived audio-visual
correspondence in videos from different datasets.

##  6 Conclusion

This work complements existing line of research on self-supervised
representation learning with three main contributions: i) proposing an
automatic and scalable data collection pipeline for audio-visual
representation learning, ii) demonstrating that the MI-based subset selection
can retrieve correspondence in both artificial and practical settings, and
iii) releasing a large-scale open-domain video dataset consisting of 100M
clips curated with our pipeline.

Acknowledgements. Authors in Seoul National University are supported by
Institute of Information & communications Technology Planning & Evaluation
(IITP) grant funded by the Korea government (MSIT) (No.2017-0-01772, Video
Turing Test, No.2019-0-01082, SW StarLab).

Figure 5: Histograms of cluster IDs from our curated subsets and randomly
sampled subsets (with 100 cluster centroids). The blue histograms represent
the case where samples are drawn uniformly random and thus is the unbiased
representation of the concepts naturally appearing in the entire population.

##  Appendix A On the Diversity of Concepts in Sampled Clips

###  A.1 Histogram of Cluster IDs

To analyze the diversity of concepts contained in our curated dataset, we
examine the histograms of cluster IDs from the chosen videos. Figure 5 shows
audio and visual histograms obtained from either our curated subsets or
randomly sampled subsets at varying scales (20K, 200K, and 2M). To obtain
these, we cluster the features from the last layer of audio and visual feature
extractors, respectively, and plot the histograms of cluster IDs. For the
purpose of visualization we sort the cluster indices by the cluster size in a
decreasing order (and thus the cluster IDs do not match between “Random” and
“Ours” in each of the plots). The histograms from random subsets represent the
natural distribution of the entire video population.

In the visual domain, the curated datasets (green histograms) mostly follow
the original cluster distributions (which is reflected in the blue histogram
in each subplot). This indicates that the visual concept distribution largely
follows the natural distribution in the entire population, suggesting that our
subset contains visual concepts that are as diverse as the entire set.

On the other hand, the audio clusters show noticeable concentration in
distribution after subset selection. Upon close inspection of videos from the
largest audio clusters, we observe that our curated datasets tend to choose
videos from clusters with high audio-visual correspondence (e.g., videos of a
single person speaking with no other sound in background) while random
sampling tend to choose videos from clusters with no apparent audio-visual
correspondence (e.g., videos of multiple people taking with background
music/noise). This shows that the concentration in the audio histograms is
caused by filtering out videos of low audio-visual correspondence, which is a
highly desirable artifact in the curated subset.

###  A.2 Qualitative Analysis of Audio-Visual Clustering Results

To further investigate the diversity of concepts appearing in our subsets, we
manually inspect audio and visual clustering results in the 2M dataset and
compare the concepts appearing in the largest clusters to those in the
smallest ones. Figure 6 and Figure 7 show representative videos from the five
largest and five smallest clusters obtained from audio and visual clustering
results, respectively. Figure 6 (from audio clusters) suggests that our
curated dataset contains diverse concepts including general sound categories
(e.g., voice and objects sounds) as well as specific topics (e.g., outdoor
interview and cooking). Similarly, Figure 7 (from visual clusters) also
suggests that our dataset contains diverse concepts including both natural
(e.g., animals and fire) and human sounds (e.g., makeup and playing guitar).
Clips from larger clusters (depicted in the left column of Figure 6 and Figure
7) contain clear and isolated sound sources, while sounds of smaller clusters
(the right column) are less distinguishable due to multiple sound sources or
background noise. Our dataset also captures several audio-visual concepts that
existing datasets (such as VGG-Sound [12] and AudioSet [21]) do not offer. For
instance, in Figure 6, the 77th cluster contains videos recorded from a front-
facing camera with voice recordings from a phone mic, and the 46th cluster
contains videos of comedians performing exaggerated body actions with the
sound of crowd (cheering and laughter). The 88th cluster in Figure 7 contains
shoes unboxing videos.

Figure 6: Representative samples and concepts derived from a manual inspection
of 100 audio clusters of the 2M subset. We show samples from the five largest
clusters on the left column and those from the five smallest clusters on the
right. Each cluster captures distinctive audio-visual concepts, indicating
that our curated subset contains various concepts with high audio-visual
correspondence. Figure 7: Representative samples and concepts derived from a
manual inspection of 100 visual clusters of the 2M subset. We show samples
from the five largest clusters on the left column and those from the five
smallest clusters on the right. Each cluster captures distinctive audio-visual
concepts, indicating that our curated subset contains various concepts with
high audio-visual correspondence.

##  Appendix B Weighted Summation of Layer Scores (Section 4.2)

Table 4 compares different layer weighting schemes in clustering-based MI
estimation, which shows that our multi-layer approach is generally robust to
weight distributions. We explored two alternative weighting schemes: a
linear($k$) function with slope $k$ and an exp($k$) function with slope
$e^{k}$; we used uniform weights in the main paper. We can see that precision
is stable under a linear weighting scheme; the robustness comes from the
Combination pairing approach which computes an average MI between all possible
combinations across layers. However, precision drops significantly when the
weights have a steep slope (e.g., exp(-10)), which is a degenerate case
similar to the single-layer approach reported in Table 2 of the main paper.

Method | Layer Weights | Precision
---|---|---
1 | 2 | 3 | 4 | 5
exp(-10) | 5e+10 | 2e+04 | 1 | 5e-05 | 2e-09 | 50.791
exp(-1) | 7.4 | 2.7 | 1 | 0.4 | 0.1 | 65.374
exp(1) | 0.1 | 0.4 | 1 | 2.7 | 7.4 | 79.858
exp(10) | 2e-09 | 5e-05 | 1 | 2e+04 | 5e+10 | 57.880
linear(-0.50) | 1.9 | 1.5 | 1 | 0.5 | 0.1 | 88.018
linear(-0.25) | 1.5 | 1.2 | 1 | 0.8 | 0.5 | 88.673
linear(0.25) | 0.5 | 0.8 | 1 | 1.2 | 1.5 | 88.777
linear(0.50) | 0.1 | 0.5 | 1 | 1.5 | 1.9 | 87.997
Uniform (Ours) | 1 | 1 | 1 | 1 | 1 | 88.705
Table 4: Different layer weighting schemes in clustering-based MI estimation
using Kinetics-Sounds with Combination pairing.

##  Appendix C Details of Linear Evaluation on Downstream Tasks (Section 5.1)

Size | Pretrain | UCF101 | ESC-50 | Kinetics-Sounds
---|---|---|---|---
top-1 | top-5 | top-1 | top-5 | top-1 | top-5
- | Random Init | 11.48 | 29.21 | 8.35 | 34.85 | 20.31 | 47.03
20K | Kinetics-Sounds | 33.51 | 64.47 | 49.40 | 81.85 | 49.98 | 82.15
Random Set | 36.34 | 66.59 | 46.95 | 79.30 | 45.19 | 77.25
Clustering (Ours) | 46.28 | 75.24 | 50.55 | 81.30 | 55.78 | 85.15
200K | VGG-Sound | 49.55 | 78.60 | 65.55 | 90.95 | 55.59 | 86.46
Random Set | 34.33 | 63.92 | 45.80 | 78.45 | 44.15 | 76.88
Contrastive | 45.10 | 76.46 | 56.90 | 85.00 | 53.80 | 85.26
Clustering (Ours) | 50.19 | 78.89 | 62.80 | 89.50 | 56.12 | 84.10
2M | AudioSet | 55.54 | 83.94 | 65.05 | 90.70 | 57.46 | 86.72
Random Set | 41.12 | 72.24 | 52.75 | 83.55 | 48.30 | 79.54
Contrastive | 45.87 | 75.80 | 58.85 | 87.10 | 53.68 | 83.05
Clustering (Ours) | 55.63 | 83.92 | 65.10 | 90.50 | 57.48 | 87.19
10M | Clustering (Ours) | 74.21 | 93.82 | 74.20 | 93.40 | 67.71 | 92.14
100M | Clustering (Ours) | 86.10 | 97.94 | 86.95 | 97.45 | 75.42 | 95.88
Table 5: Linear evaluation of representations pretrained on different
datasets. We report the top-1/5 accuracies (%) of video classification on
UCF101 [67], audio classification on ESC-50 [61] and audio-visual
classification on Kinetics-Sounds [4]. We average the accuracies across the
official splits of UCF101 (three splits) and ESC-50 (five splits).

Table 5 shows the results of liner evaluation on downstream tasks, which were
also shown in the bar chart of the main paper, Figure 4; we reproduced here to
compensate for the lack of readability of the bar chart.

###  C.1 Experimental Settings

We pretrain audio-visual models in a contrastive manner [13] on different
datasets. Specifically, we attach MLP projection heads on top of audio and
visual feature extractors, respectively, and train the whole model end-to-end
using the noise-contrastive loss (see Eqn. 1 of the main paper). As for the
visual and audio backbone feature extractors, we use 3D ResNet-50 [10] and
ResNet-50 [27], respectively. Each of the MLP projection head is composed of
two fully-connected layers with ReLU [52] activation, and produces the
embeddings of dimension 128. We pretrain the model for 50 epochs with a batch
size 64. We use the AMSGrad variant [62] of AdamW [44] optimizer with a
learning rate 1e-3, $\beta_{1}=0.9$, $\beta_{2}=0.999$ and an L2 weight decay
of 1e-5. We apply learning rate warm-up for the first 20,000 iterations
followed by a linear decay of learning rate.

For linear evaluation on downstream tasks, we attach a linear classifier on
top of the pretrained feature extractors and train it from scratch while
fixing the parameters of the feature extractors. We use only the visual CNN
for action recognition on UCF101 [67] and only the audio CNN for sound
classification on ESC50 [61]. For audio-visual action recognition on Kinetics-
Sounds [4], we concatenate audio-visual features before feeding them as input
to the linear classifier. We apply dropout [29] with a 50% rate before the
linear classifier. We train the model for 30 epochs with a batch size of 1024
on ESC-50 [61], for 10 epochs with a batch size of 64 on UCF101 [67] and for 5
epochs with a batch size of 64 on Kinetics-Sounds. We use the Adam [36]
optimizer with a learning rate 1e-2, $\beta_{1}=0.9$, $\beta_{2}=0.999$ and an
L2 weight decay of 5e-6.

###  C.2 Impact of the Number of Centroids

To visualize the impact of the number of clusters in our clustering-based
approach, we group the results by the number of clusters as shown in Figure 8.
Notice that the number of clusters is not positively correlated with
downstream task performance. Instead, clustering with about 500 clusters seems
to yield the best performance. Also, experiments using the largest number of
centroids ($C=2000$) show low accuracy consistently across all datasets and
subset sizes. This confirms our findings in Section 4.2 of the main paper:
over-clustering tends to have a negative impact on the quality of the selected
subset. We believe that this happens because, as the number of clusters
increases, samples with homogeneous concepts in large clusters are scattered
into small clusters sharing similar concepts. When we do not have many
references to compare as in the early stage of subset selection, this
fragmentation effect inhibits sample count sharing between conceptually
similar small clusters, complicating the clustering-based MI estimation.

Figure 8: Linear evaluation of representations pretrained on the datasets that
are constructed by our clustering-based approach. We report the top-1 accuracy
(%) on UCF101 [67], ESC-50 [61], and Kinetics-Sounds [4], grouped by the
number of cluster centroids. The shaded regions show 99% confidence intervals
obtained by runs over the official splits of UCF101 (3 splits) and ESC-50 (5
splits).

##  Appendix D More Discussion on Subset Selection (Section 3.3.2)

###  D.1 Greedy Algorithm

We provide the details of the greedy algorithm [54] that is approximated using
the batch greedy algorithm [14]. As shown in Algorithm 2, the greedy algorithm
needs to re-evaluate the clustering-based MI estimator $F$ on all the
remaining candidates in each iteration. Thus, the time complexity is
$O(N^{2})$ where $N$ is the size of the initial dataset $\mathbf{D}$.

On the other hand, the batch greedy algorithm approximates this by selecting
the next element to be included in the solution within only a randomly chosen
batch, not the entire candidates. This is shown in Algorithm 3 below (same as
Algorithm 1 of the main paper; reproduced here for easy comparison).

###  D.2 Batch Greedy Subset Selection

When using the batch greedy algorithm for subset selection, the batch size $b$
and the selection size $s$ affect the quality of the selected subsets. We
explore various $(b,s)$ configurations on Kinetics-Sounds [4], as shown in
Figure 9. Note that the performance gap between different batch sizes is
small. The precision 93.9%, 94.3% and 94.6% are respectively obtained when
using batch sizes $b=40,80,160$ with the same ratio of selection size to batch
size $s/b=12.5\%$. On the contrary, the value of $s/b$ highly affects the
retrieval performance across all the batch sizes examined; the performance
drops sharply as the ratio exceeds 25% regardless of the batch size. As stated
in Section 4.2 of the main paper, we construct the dataset to have an equal
number of positive and negative pairs and the drop in robustness manifests
itself when the selection ratio $s/b$ exceeds the easy positive ratio of 25%.

##  Appendix E Details of Automatic Dataset Curation

Here, we describe the details of subset selection via (i) NCE-based MI
estimation and (ii) clustering-based MI estimation. To construct datasets, we
vary scales of 20K, 200K and 2M. Based on the results at the three scales, we
also generate a version with 10M videos using the clustering-based approach.

Input: initial dataset $\mathbf{D}$, clustering-based MI estimator $F$, target
subset size $M$

Output: $\mathbf{X}\subseteq\mathbf{D},|\mathbf{X}|=M$

$\mathbf{X}_{0}\leftarrow\emptyset$

for  _$i=0$ to $M-1$_ do

$x\leftarrow\operatornamewithlimits{argmax}_{x\in\mathbf{D}\backslash\mathbf{X}_{i}}F(\mathbf{X}_{i}\cup\\{x\\})$

$\mathbf{X}_{i+1}\leftarrow\mathbf{X}_{i}\cup\\{x\\}$

end for

$\mathbf{X}\leftarrow\mathbf{X}_{M}$

Return $\mathbf{X}$

Algorithm 2 Greedy Algorithm

Input: initial dataset $\mathbf{D}$, clustering-based MI estimator $F$, target
subset size $M$, batch size $b$, selection size $s$

Output: $\mathbf{X}\subseteq\mathbf{D},|\mathbf{X}|=M$

$\mathbf{X}_{0}\leftarrow\emptyset,i\leftarrow 0$

while  _$|X_{i}| <M$_ do

Randomly sample
$\mathbf{B}\subseteq\mathbf{D}\backslash\mathbf{X}_{i},|\mathbf{B}|=b$

$\mathbf{Y}_{0}\leftarrow\emptyset,j\leftarrow 0$

while  _$j <s$_ do

$x\leftarrow\operatornamewithlimits{argmax}_{x\in\mathbf{B}\backslash\mathbf{Y}_{j}}F(\mathbf{X}_{i}\cup\mathbf{Y}_{j}\cup\\{x\\})$

$\mathbf{Y}_{j+1}\leftarrow\mathbf{Y}_{j}\cup\\{x\\},j\leftarrow j+1$

if  _$|\mathbf{X}_{i}\cup\mathbf{Y}_{j}|=M$_ then break

end while

$\mathbf{X}_{i+1}\leftarrow\mathbf{X}_{i}\cup\mathbf{Y}_{j},i\leftarrow i+1$

end while

$\mathbf{X}\leftarrow\mathbf{X}_{i}$

Return $\mathbf{X}$

Algorithm 3 Batch Greedy Algorithm (reproduced from the main paper for easy
comparison) Figure 9: Precisions of Batch greedy algorithm with varying ratios
of selection size to batch size, $s/b$ (x axis: iterations, y axis:
precision). We group the plots by the batch size: $b=40,80,160$ from left to
right. The shaded regions show 99% confidence intervals obtained by five runs
on Kinetics-Sounds. The batch greedy algorithm is robust when the ratio is
$\leqslant$ 25%, regardless of the batch size.

###  E.1 NCE-Based MI Estimation

We use the linear projection heads that transform audio and visual features
into 128-dimension embeddings. We randomly sample a subset of 100M clips from
the initial 300M set that we crawl, and train on the subset for three epochs
with a batch size $N_{b}=1,024$. We use the AMSGrad variant of Adam optimizer
[62] with a learning rate 2e-4, $\beta_{1}=0.9$ and $\beta_{2}=0.999$. We
apply learning rate warm-up for the first 3 epochs followed by a linear decay
of learning rate.

###  E.2 Clustering-Based MI Estimation

For SGD K-Means clustering, we train the cluster centroids with a mini-batch
of size 100K for 100 epochs using a learning rate $\lambda=\textrm{1e-2}$.
When applying the batch greedy algorithm, we use the fixed batch size
$b=10,000$ and the selection size $s=500$ (with a ratio of $s/b=0.05$), but
vary the number of clusters $C\in\\{100,200,500,1000,2000\\}$ for each size of
the datasets, except the dataset of 10M scale (we generate the dataset only
with $C=500$ for computational reasons).

##  Appendix F Human Evaluation Interface (Section 5.2)

Figure 10: Screenshots of the human evaluation interface. The introduction
page (top) provides instructions to the annotators, and the test page (bottom)
shows clips to the raters and receives the corresponding Yes/No responses.

Figure 10 shows the user interface we developed for human evaluation. We
provide guidelines on how to assess audio-visual correspondence:

> You will watch a video clip for 10 seconds. Please determine whether there
> is audio-visual correspondence in the video. In other words, decide whether
> the sound source is visible or can be inferred from visual context.

After a pilot study we gathered feedback from experts and added additional
guidelines to help disambiguate common edge scenarios (shown in Figure 10).
Annotators are given one 10-second clip at a time and asked to provide a
Yes/No answer judging whether or not there is audio-visual correspondence in
the given clip. We do not provide a replay interface to collect intuitive
response from the raters.

## References

  * [1] Sami Abu-El-Haija, Nisarg Kothari, Joonseok Lee, Paul Natsev, George Toderici, Balakrishnan Varadarajan, and Sudheendra Vijayanarasimhan.  Youtube-8M: A Large-Scale Video Classification Benchmark.  arXiv preprint arXiv:1609.08675, 2016.
  * [2] Pankaj K Agarwal, Sariel Har-Peled, and Kasturi R Varadarajan.  Geometric Approximation via Coresets.  Combinatorial and Computational Geometry, 52:1–30, 2005.
  * [3] Humam Alwassel, Dhruv Mahajan, Lorenzo Torresani, Bernard Ghanem, and Du Tran.  Self-Supervised Learning by Cross-Modal Audio-Video Clustering.  arXiv preprint arXiv:1911.12667, 2019.
  * [4] Relja Arandjelovic and Andrew Zisserman.  Look, Listen and Learn.  In ICCV, 2017.
  * [5] Yusuf Aytar, Carl Vondrick, and Antonio Torralba.  SoundNet: Learning Sound Representations from Unlabeled Video.  In NeurIPS, 2016.
  * [6] David Bau, Bolei Zhou, Aude Oliva, and Antonio Torralba.  Interpreting Deep Visual Representations via Network Dissection.  PAMI, 41(9):2131–2145, 2019.
  * [7] Leon Bottou and Yoshua Bengio.  Convergence Properties of the K-Means Algorithms.  In NeurIPS, 1995.
  * [8] Fabian Caba Heilbron, Victor Escorcia, Bernard Ghanem, and Juan Carlos Niebles.  ActivityNet: A Large-Scale Video Benchmark for Human Activity Understanding.  In CVPR, 2015.
  * [9] João Carreira, Eric Noland, Chloe Hillier, and Andrew Zisserman.  A Short Note on the Kinetics-700 Human Action Dataset.  arXiv preprint arXiv:1907.06987, 2019.
  * [10] Joao Carreira and Andrew Zisserman.  Quo Vadis, Action Recognition? A New Model and the Kinetics Dataset.  In CVPR, 2017.
  * [11] Sourish Chaudhuri, Joseph Roth, Daniel P. W. Ellis, Andrew Gallagher, Liat Kaver, Radhika Marvin, Caroline Pantofaru, Nathan Reale, Loretta Guarino Reid, Kevin Wilson, and Zhonghua Xi.  AVA-Speech: A Densely Labeled Dataset of Speech Activity in Movies.  In Interspeech, 2018.
  * [12] Honglie Chen, Weidi Xie, Andrea Vedaldi, and Andrew Zisserman.  VGGSound: A Large-Scale Audio-Visual Dataset.  In ICASSP, 2020.
  * [13] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A Simple Framework for Contrastive Learning of Visual Representations.  In ICML, 2020.
  * [14] Yuxin Chen and Andreas Krause.  Near-optimal Batch Mode Active Learning and Adaptive Submodular Optimization.  ICML, 2013.
  * [15] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  ImageNet: A Large-Scale Hierarchical Image Database.  In CVPR, 2009.
  * [16] Christoph Feichtenhofer, Haoqi Fan, Jitendra Malik, and Kaiming He.  SlowFast Networks for Video Recognition.  In ICCV, 2019.
  * [17] Christoph Feichtenhofer, Axel Pinz, and Richard Wildes.  Spatiotemporal Residual Networks for Video Action Recognition.  In NeurIPS, 2016.
  * [18] John W Fisher and Trevor Darrell.  Probabalistic Models and Informative Subspaces for Audiovisual Correspondence.  In ECCV, 2002.
  * [19] Joseph L Fleiss.  Measuring Nominal Scale Agreement Among Many Raters.  Psychological Bulletin, 76(5):378, 1971.
  * [20] Ruohan Gao and Kristen Grauman.  2.5D Visual Sound.  In CVPR, 2019.
  * [21] Jort F. Gemmeke, Daniel P. W. Ellis, Dylan Freedman, Aren Jansen, Wade Lawrence, R. Channing Moore, Manoj Plakal, and Marvin Ritter.  Audio Set: An Ontology and Human-Labeled Dataset for Audio Events.  In ICASSP, 2017.
  * [22] Eleanor Jack Gibson.  Principles of Perceptual Learning and Development.  Appleton-Century-Crofts, 1969.
  * [23] Yuhong Guo.  Active Instance Sampling via Matrix Partition.  In NeurIPS, 2010.
  * [24] Michael Gutmann and Aapo Hyvärinen.  Noise-Contrastive Estimation: A New Estimation Principle for Unnormalized Statistical Models.  In AISTATS, 2010.
  * [25] Sariel Har-Peled and Soham Mazumdar.  On Coresets for K-Means and K-Median Clustering.  In STOC, 2004.
  * [26] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum Contrast for Unsupervised Visual Representation Learning.  In CVPR, 2020.
  * [27] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep Residual Learning for Image Recognition.  In CVPR, 2016.
  * [28] Shawn Hershey, Sourish Chaudhuri, Daniel PW Ellis, Jort F Gemmeke, Aren Jansen, R Channing Moore, Manoj Plakal, Devin Platt, Rif A Saurous, Bryan Seybold, et al.  CNN Architectures for Large-Scale Audio Classification.  In ICASSP, 2017.
  * [29] Geoffrey E Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan R Salakhutdinov.  Improving Neural Networks by Preventing Co-Adaptation of Feature Detectors.  arXiv preprint arXiv:1207.0580, 2012.
  * [30] R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio.  Learning Deep Representations by Mutual Information Estimation and Maximization.  In ICLR, 2019.
  * [31] Zohar Jackson, César Souza, Jason Flaks, Yuxin Pan, Hereman Nicolas, and Adhish Thite.  Free Spoken Digit Dataset: v1.0.8, Aug. 2018.
  * [32] David S Johnson, Christos H Papadimitriou, and Mihalis Yannakakis.  How Easy Is Local Search?  Journal of computer and system sciences, 37(1):79–100, 1988.
  * [33] Armand Joulin, Edouard Grave, Piotr Bojanowski, Matthijs Douze, Hérve Jégou, and Tomas Mikolov.  FastText.zip: Compressing Text Classification Models.  arXiv preprint arXiv:1612.03651, 2016.
  * [34] Armand Joulin, Edouard Grave, Piotr Bojanowski, and Tomas Mikolov.  Bag of Tricks for Efficient Text Classification.  In EACL, 2017.
  * [35] Will Kay, Joao Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijayanarasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, et al.  The Kinetics Human Action Video Dataset.  arXiv preprint arXiv:1705.06950, 2017.
  * [36] Diederik P Kingma and Jimmy Ba.  Adam: A Method for Stochastic Optimization.  In ICLR, 2015.
  * [37] Bruno Korbar, Du Tran, and Lorenzo Torresani.  Cooperative Learning of Audio and Video Models from Self-Supervised Synchronization.  In NeurIPS, 2018.
  * [38] Alexander Kraskov, Harald Stögbauer, and Peter Grassberger.  Estimating Mutual Information.  Physical review E, 69(6), 2004.
  * [39] Alex Krizhevsky and Geoffrey Hinton.  Learning Multiple Layers of Features from Tiny Images.  Technical report, University of Toronto, 2009.
  * [40] J Richard Landis and Gary G Koch.  The Measurement of Observer Agreement for Categorical Data.  Biometrics, pages 159–174, 1977.
  * [41] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-Based Learning Applied to Document Recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [42] David D Lewis and William A Gale.  A Sequential Algorithm for Training Text Classifiers.  In SIGIR, 1994.
  * [43] Xin Li and Yuhong Guo.  Adaptive Active Learning for Image Classification.  In CVPR, 2013.
  * [44] Ilya Loshchilov and Frank Hutter.  Decoupled Weight Decay Regularization.  In ICLR, 2019.
  * [45] Thomas Martinetz and Klaus Schulten.  A “Neural-Gas” Network Learns Topologies.  In ICANN, 1991.
  * [46] Marina Meilă.  Comparing Clusterings—An Information Based Distance.  Journal of multivariate analysis, 98(5), 2007.
  * [47] N Michele Merler, Khoi-Nguyen C. Mac, Dhiraj Joshi, Quoc-Bao Nguyen, Stephen Hammer, John Kent, Jinjun Xiong, Minh N. Do, John R. Smith, and Rogerio Schmidt Feris.  Automatic Curation of Sports Highlights Using Multimodal Excitement Features.  IEEE Trans Multimedia, 21(5), 2019.
  * [48] Antoine Miech, Dimitri Zhukov, Jean-Baptiste Alayrac, Makarand Tapaswi, Ivan Laptev, and Josef Sivic.  HowTo100M: Learning a Text-Video Embedding by Watching Hundred Million Narrated Video Clips.  In ICCV, 2019.
  * [49] Michel Minoux.  Accelerated Greedy Algorithms for Maximizing Submodular Set Functions.  In Optimization techniques, pages 234–243. Springer, 1978.
  * [50] Mathew Monfort, Alex Andonian, Bolei Zhou, Kandan Ramakrishnan, Sarah Adel Bargal, Tom Yan, Lisa Brown, Quanfu Fan, Dan Gutfruend, and Carl Vondrick.  Moments in Time Dataset: One Million Videos for Event Understanding.  PAMI, pages 1–8, 2019.
  * [51] Arsha Nagrani, Joon Son Chung, Weidi Xie, and Andrew Zisserman.  Voxceleb: Large-scale speaker verification in the wild.  Computer Science and Language, 2019.
  * [52] Vinod Nair and Geoffrey E Hinton.  Rectified Linear Units Improve Restricted Boltzmann Machines.  In ICML, 2010.
  * [53] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher.  An Analysis of Approximations for Maximizing Submodular Set Functions–I.  Mathematical Programming, 14(1):265–294, 1978.
  * [54] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher.  An Analysis of Approximations for Maximizing Submodular Set Functions—I.  Mathematical programming, 14(1):265–294, 1978.
  * [55] Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation Learning with Contrastive Predictive Coding.  arXiv preprint arXiv:1807.03748, 2018.
  * [56] Andrew Owens, Phillip Isola, Josh McDermott, Antonio Torralba, Edward H Adelson, and William T Freeman.  Visually Indicated Sounds.  In CVPR, 2016.
  * [57] Stuart P. Lloyd.  Least Squares Quantization in PCM.  IEEE Transactions on Information Theory, 28(2):129–137, 1982.
  * [58] Liam Paninski.  Estimation of Entropy and Mutual Information.  Neural computation, 15(6):1191–1253, 2003.
  * [59] Mandela Patrick, Yuki M Asano, Ruth Fong, João F Henriques, Geoffrey Zweig, and Andrea Vedaldi.  Multi-modal Self-Supervision from Generalized Data Transformations.  arXiv preprint arXiv:2003.04298, 2020.
  * [60] Karl Pearson.  LIII. On Lines and Planes of Closest Fit to Systems of Points in Space.  The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(11):559–572, 1901.
  * [61] Karol J. Piczak.  ESC: Dataset for Environmental Sound Classification.  In ACM-MM, 2015.
  * [62] Sashank J Reddi, Satyen Kale, and Sanjiv Kumar.  On the Convergence of Adam and Beyond.  In ICLR, 2018.
  * [63] Joseph Roth, Sourish Chaudhuri, Ondrej Klejch, Radhika Marvin, Andrew Gallagher, Liat Kaver, Sharadh Ramaswamy, Arkadiusz Stopczynski, Cordelia Schmid, Zhonghua Xi, and Caroline Pantofaru.  AVA-ActiveSpeaker: An Audio-Visual Dataset for Active Speaker Detection.  arXiv preprint arXiv:1901.01342, 2019.
  * [64] David Sculley.  Web-Scale K-Means Clustering.  In WWW, 2010.
  * [65] Burr Settles.  Active Learning Literature Survey.  Science, 10(3):237–304, 1995.
  * [66] Yusuke Shinohara.  A Submodular Optimization Approach to Sentence Set Selection.  In ICASSP, 2014.
  * [67] Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah.  UCF101: A Dataset of 101 Human Actions Classes From Videos in The Wild.  arXiv preprint arXiv:1212.0402, 2012.
  * [68] Jamshid Sourati, Murat Akcakaya, Jennifer G Dy, Todd K Leen, and Deniz Erdogmus.  Classification Active Learning Based on Mutual Information.  Entropy, 18(2):51, 2016.
  * [69] Jonathan C Stroud, David A Ross, Chen Sun, Jia Deng, Rahul Sukthankar, and Cordelia Schmid.  Learning Video Representations from Textual Web Supervision.  arXiv preprint arXiv:2007.14937, 2020.
  * [70] Yapeng Tian, Jing Shi, Bochen Li, Zhiyao Duan, and Chenliang Xu.  Audio-Visual Event Localization in Unconstrained Videos.  In ECCV, 2018.
  * [71] Ivor W Tsang, James T Kwok, and Pak-Ming Cheung.  Core Vector Machines: Fast SVM Training on Very Large Data Sets.  Journal of Machine Learning Research, 6(Apr):363–392, 2005.
  * [72] Nguyen Xuan Vinh, Julien Epps, and James Bailey.  Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance.  Journal of Machine Learning Research, 11, 2010.
  * [73] Janett Walters-Williams and Yan Li.  Estimation of Mutual Information: A Survey.  In RSKT, 2009.
  * [74] Mei Wang and Weihong Deng.  Deep Visual Domain Adaptation: A Survey.  Neurocomputing, 312:135–153, 2018.
  * [75] Kai Wei, Rishabh Iyer, and Jeff Bilmes.  Submodularity in Data Subset Selection and Active Learning.  In ICML, 2015.
  * [76] Kai Wei, Yuzong Liu, Katrin Kirchhoff, Chris Bartels, and Jeff Bilmes.  Submodular Subset Selection for Large-Scale Speech Training Data.  In ICASSP, 2014.
  * [77] Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes.  Using Document Summarization Techniques for Speech Data Subset Selection.  In NAACL, 2013.
  * [78] Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes.  Unsupervised Submodular Subset Selection for Speech Data.  In ICASSP, 2014.
  * [79] Xindong Wu, Vipin Kumar, J Ross Quinlan, Joydeep Ghosh, Qiang Yang, Hiroshi Motoda, Geoffrey J McLachlan, Angus Ng, Bing Liu, S Yu Philip, et al.  Top 10 Algorithms in Data Mining.  Knowledge and Information Systems, 14(1):1–37, 2008.
  * [80] Karren Yang, Bryan Russell, and Justin Salamon.  Telling Left From Right: Learning Spatial Correspondence of Sight and Sound.  In CVPR, 2020.
  * [81] Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson.  How Transferable are Features in Deep Neural Networks?  In NeurIPS, 2014.