# Ergodicity and totality of partitions associated with the RSK correspondence

A. M. Vershik St. Petersburg Department of Steklov Institute of Mathematics;
St. Petersburg State University; Institute for Information Transmission
Problems. E-mail<EMAIL_ADDRESS>N. V. Tsilevich St. Petersburg
Department of Steklov Institute of Mathematics. E-mail<EMAIL_ADDRESS>
###### Abstract

We study asymptotic properties of sequences of partitions ($\sigma$-algebras)
in spaces with Bernoulli measures associated with the Robinson–Schensted–Knuth
correspondence.

Key words: RSK correspondence, youngization, ergodicity of a sequence of
partitions, totality of a sequence of partitions.

##  1 Introduction

We study dynamic properties of the Robinson–Schensted–Knuth correspondence
(RSK) when it is successively applied to growing sequences of symbols. In
particular, we are interested in asymptotic properties of this correspondence.
Apparently, the “dynamic” approach to the RSK correspondence first appeared in
[3], where it was discovered that applying the RSK algorithm to an infinite
sequence of independent symbols from a linearly ordered set defines a
correspondence between Bernoulli measures (i.e., ensembles of independent
sequences of symbols) and central (Markov) measures on the path space of a
certain graph (the Young graph). In other words, the RSK correspondence
defines measure-preserving homomorphisms from Bernoulli spaces to Markov path
spaces. Thus, the question inevitably arises of whether or not this
homomorphism is an isomorphism $\bmod\,0$. The affirmative answer to this
question was obtained in the relatively recent important papers [4, 5]; their
approach relies on the Schützenberger’s jeu de taquin and is rather
technically involved.

The first author [10] suggested a program for solving these problems for a
certain class of graphs, including an elaboration of the ergodic method [7]
for finding invariant measures and the so-called bernoullization of graphs.
This approach uses techniques of the theory of filtrations (decreasing
sequences of $\sigma$-algebras) [8]; in particular, it has led to a new
problem of characterization of de Finetti-like filtrations, i.e., filtrations
for which every ergodic central measure is a Bernoulli measure. Note in this
regard that this paper (as well as [5]) deals with the properties and
structure of some ergodic central measures, those originating from Bernoulli
measures; the fact that they exhaust all central measures with finitely many
frequencies for the Young graph does by no means follow from these
considerations. However, the methods suggested in [10] allowed the authors to
prove, in a paper in preparation, that every central measure of this type is
associated with a Bernoulli measure in the above sense. This is how a long
awaited purely combinatorial proof of Thoma’s theorem (see [9]) should appear.

In this paper, we study only a part of the general problem in the simplest
case of a linearly ordered set with finitely many symbols, and prove two facts
in a sense dual to each other: the totality of the coplactic (= dual Knuth)
equivalence and the ergodicity of the so-called Young filtration, i.e., the
tail filtration determined by the $Q$-tableaux in the RSK corresponcence. Our
arguments, on the one hand, give another proof of the corresponding results
from [5] and, on the other hand, can be applied in a much more general
situation. We consider separately the case of two letters, because it is
illustrative and serves as the base case for an induction in the general case.

The reader is assumed to be familiar with the RSK correspondence and its basic
properties (see, e.g., [1]); for background on the representation theory of
the infinite symmetric group (the Young graph, central measures, Thoma
parameters, etc.), see, e.g., [2]; for that on the theory of measurable
partitions and filtrations, see, e.g., [8].

##  2 Youngization

Let ${\cal A}=\\{1,2,\ldots,k\\}$ be a finite alphabet. Consider the space
$X={\cal A}^{\infty}$ of infinite words in the alphabet ${\cal A}$ with
Bernoulli measure $m_{p}^{\infty}$, where $p=(p_{1},p_{2},\ldots,p_{k})$,
$p_{i}=\operatorname{Prob}(i)$, and $p_{1}\geq p_{2}\geq\ldots\geq p_{k}>0$.

Let ${\cal T}$ be the set of infinite standard Young tableaux (or, which is
the same, the set of infinite paths in the Young graph ${\mathbb{Y}}$) and
$\mu_{p}$ be the central measure on ${\cal T}$ with Thoma parameters
$(p,0,0)$. Note that the measure $\mu_{p}$ is supported by the subset of
tableaux with at most $k$ rows.

By $\operatorname{RSK}(w)=(P(w),Q(w))$ we denote the result of applying the
RSK algorithm to a finite sequence (word) $w$ in the alphabet ${\cal A}$.
Thus, $P(w),Q(w)$ is a pair of Young tableaux of the same shape (with at most
$k$ rows), which will be denoted by $\operatorname{sh}(w)$; the tableau $P(w)$
is semistandard, while the tableau $Q(w)$ is standard. Given an infinite
sequence $x\in X$, denote by $[x]_{n}=(x_{1},\ldots,x_{n})\in{\cal A}^{n}$ its
initial segment of length $n$, and let
$\\{x\\}_{n+1}:=(x_{n+1},x_{n+2},\ldots)\in{\cal A}^{\infty}$ be its
$(n+1)$-tail. Also, denote by $P_{n}(x)$ and $Q_{n}(x)$ the tableaux obtained
by applying the RSK algorithm to the initial segment of length $n$ of a
sequence $x$: $\operatorname{RSK}([x]_{n})=(P_{n}(x),Q_{n}(x))$.

Following [3], we introduce a map from the space of infinite sequences to the
space of infinite Young tableaux.

######  Definition 1.

Successively apply the RSK algorithm to the initial segments $[x]_{n}$ of a
sequence $x\in X$. It is clear from the construction of the algorithm that
$\lim\limits_{n\to\infty}Q_{n}(x)=:Q(x)$ is an infinite standard Young
tableau; denote it by $\pi(x)$. The resulting map

$\pi:(X,m_{p}^{\infty})\to({\cal T},\mu_{p})$ (1)

is called the _youngization_.

In [3] it is proved that the youngization (1) is a homomorphism of measure
spaces.

##  3 The sequences of Young partitions on a Bernoulli space. The main
theorems

The following measurable partitions are defined in a natural way on the space
$(X,m_{p}^{\infty})$ of infinite Bernoulli sequences:

  * •

the cylinder partition $\sigma_{n}$ of level $n$, whose element is a set (of
finite measure) of sequences with a fixed initial segment of length $n$ and
arbitrary tail;

  * •

the tail partition $\tau_{n}$ of level $n$, whose element is a (finite) set of
sequences with a fixed $(n+1)$-tail and arbitrary beginning.

We will call them the Bernoulli cylinder and tail partitions. They have the
following properties:

  * •

the sequence of partitions $\sigma_{n}$ is monotonely increasing and converges
in the weak topology to the partition $\varepsilon$ into separate points;

  * •

the sequence of partitions $\tau_{n}$ is monotonely decreasing and converges
in the weak topology to the trivial partition $\nu$;

  * •

for every $n$, the partitions $\tau_{n}$ and $\sigma_{n}$ are independent with
respect to the Bernoulli measure $m_{p}^{\infty}$.

Now consider the following measurable partitions on the space ${\cal T}$ of
infinite Young tableaux:

  * •

the cylinder partition $\xi_{n}$ of level $n$, whose element is a set (of
finite measure) of infinite paths in the Young graph (i.e., infinite Young
tableaux) with a fixed initial segment of length $n$ and arbitrary tail.

  * •

the tail partition $\eta_{n}$ of level $n$, whose elements is a (finite) set
of infinite paths in the Young graph with a fixed $n$-tail and arbitrary
beginning.

######  Definition 2.

The Young cylinder partition and Young tail partition of the space $X$ of
infinite sequences are the partitions $\bar{\xi}_{n}:=\pi^{-1}\xi_{n}$ and
${\bar{\eta}_{n}:=\pi^{-1}\eta_{n}}$, respectively, i.e., the preimages of the
cylinder and tail partitions on Young tableaux under the youngization $\pi$.
The decreasing sequence of partitions $\\{\bar{\eta}_{n}\\}$ will also be
called the Young filtration.

Thus, $x\sim_{\bar{\xi}_{n}}y$ $\iff$ $Q([x]_{n})=Q([y]_{n})$, and
$x\sim_{\bar{\eta}_{n}}y$ $\iff$
$\operatorname{sh}([x]_{N})=\operatorname{sh}([y]_{N})$ for $N\geq n$.
Obviously, $\bar{\xi}_{n}\prec\sigma_{n}$.

To begin with, we describe the structure of Young partitions. Recall (see,
e.g., [1]) that the Knuth equivalence (or plactic) class ${\cal P}_{t}$ and
the dual Knuth equivalence (or coplactic) class ${\cal C}_{t}$ corresponding
to a given Young tableau $t$ of size $n$ is the set of all words $u$ of length
$n$ such that $P(u)=t$ and $Q(u)=t$, respectively.

######  Theorem 1.

The Young partitions on the space $X$ can be described as follows.

  * •

The elements of $\bar{\xi}_{n}$ are indexed by the standard Young tableaux $t$
of size $n$ and coincide with the coplactic classes ${\cal C}_{t}$.

  * •

The elements of $\bar{\eta}_{n}$ are indexed by the pairs $(t,y)$ where $t$ is
a semistandard Young tableau of size $n$ and $y$ is an infinite word in the
alphabet ${\cal A}$ and have the form

$\\{x\in X:[x]_{n}\in{\cal P}_{t},\,\\{x\\}_{n+1}=y\\};$

in other words, this is the set of all sequences whose initial segment of
length $n$ belongs to a given plactic class and the tail coincides with a
given infinite sequence.

The first assertion of this theorem is obvious, and the second one will be
proved in the next section (see Lemma 3).

Recall that a decreasing sequence of partitions (filtration) in a measure
space is said to be ergodic if it converges in the weak topology to the
trivial partition $\nu$ (into a single nonempty set). In turn, an increasing
sequence of partitions in a measure space is said to be total if it converges
in the weak topology to the partition $\varepsilon$ into separate points.
Thus, the ergodicity of a sequence of partitions means that there is no
nonconstant measurable function that is constant on the elements of all
partitions, while the totality of a sequence of partitions means that for
almost all pairs $x,y$ of different points, $x$ and $y$ will eventually fall
in different elements of partitions.

Clearly, the sequence of partitions $\bar{\xi}_{n}$ is increasing, while the
sequence of partitions $\bar{\eta}_{n}$ is decreasing. Our purpose is to study
the limiting partitions $\bar{\xi}:=\lim\limits_{n\to\infty}\bar{\xi}_{n}$ and
$\bar{\eta}:=\lim\limits_{n\to\infty}\bar{\eta}_{n}$, namely, to prove the
following theorem.

######  Theorem 2.

The Young partitions on the space $X$ of infinite Bernoulli sequences have the
following properties:

  * •

the sequence of partitions $\bar{\xi}_{n}$ is total;

  * •

the sequence of partitions $\bar{\eta}_{n}$ is ergodic.

As a corollary, we obtain the result proved (for an arbitrary central measure)
in [5].

######  Corollary 1.

The youngization map (1) is an isomorphism of measure spaces between
$(X,m_{p}^{\infty})$ and $({\cal T},\mu_{p})$.

Note that the space $({\cal T},\mu_{p})$ of infinite paths in the Young graph
with the central measure $\mu_{p}$ can be identified with the space of
trajectories of a Markov random walk on the “Weyl chamber”

${\cal W}_{k}=\\{(x_{1},\ldots,x_{k}):x_{i}\in\mathbb{Z},\,x_{1}\geq
x_{2}\geq\ldots\geq x_{k}\geq 0\\},$

where for a path ${\cal T}\ni t=(\lambda^{(1)},\lambda^{(2)},\ldots)$ we set
$\lambda^{(n)}=(\lambda_{1}^{(n)},\ldots,\lambda_{k}^{(n)})\in{\cal W}_{k}$
(thus, at each step, one of the coordinates is increased by $1$). So, the
youngization map (1) establishes an isomorphism between the space
$(X,m_{p}^{\infty})$ of trajectories of a Bernoulli process and the space of
trajectories of a Markov process. For example, in the case of $k=2$ and the
uniform measure $p=(\frac{1}{2},\frac{1}{2})$, the transition probabilities of
the Markov process are given by the following formula (see [11]): if
$j=\lambda_{1}-\lambda_{2}$ is the difference of the row lengths of a diagram,
then

$\operatorname{Prob}(j,j+1)=\frac{j+2}{2(j+1)},\qquad\operatorname{Prob}(j,j-1)=\frac{j}{2(j+1)}.$

We also introduce another family of partitions $\zeta_{n}$. Namely, on the
space $X$ of infinite sequences there is a natural action of the infinite
symmetric group ${\mathfrak{S}}_{\infty}$ by permutations of elements. Denote
by $\zeta_{n}$ the partition of $X$ into the orbits of the finite subgroup
${{\mathfrak{S}}_{n}\subset{\mathfrak{S}}_{\infty}}$. In other words, two
sequences $x,y\in X$ belong to the same element of $\zeta_{n}$ if and only if
$\\{x\\}_{n+1}=\\{y\\}_{n+1}$ and in $[x]_{n},[y]_{n}$ all elements occur with
the same multiplicity. The partitions $\zeta_{n}$ will be called the de
Finetti partitions. Note that $\lim\limits_{n\to\infty}\zeta_{n}=\nu$ by the
Hewitt–Savage zero–one law.

##  4 Proofs of the main theorems

###  4.1 The case $k=2$

In this section, we analyze the case of the two-letter alphabet ${\cal
A}_{2}=\\{1,2\\}$. Note that the space $X_{2}={\cal A}_{2}^{\infty}$ with
Bernoulli measure $m^{\infty}$, where $m=(p_{1},p_{2})$, can be naturally
regarded as the space of trajectories of the random walk on the one-
dimensional lattice with probability $p_{1}$ of moving right and probability
$p_{2}$ of moving left. Recall that we assume that $p_{1}\geq p_{2}>0$.

Consider a sequence from ${\cal A}_{2}^{n}$ as a word $w=x_{1}\ldots x_{n}$.
Bracket every factor $21$ in $w$. The remaining letters constitute a subword
$w_{1}$ in $w$. Bracket every factor $21$ in $w_{1}$. We are left with a word
$w_{2}$. Continue the procedure until we are left with a word of the form
$w_{k}=1^{a}2^{b}=x_{i_{1}}\ldots x_{i_{a+b}}$ with $a,b\geq 0$. The elements
$x_{i_{1}},\ldots,x_{i_{a+b}}$ of the sequence $w$ will be called free, and
all the other elements will be called paired. The number of brackets will be
called the rank of $w$ and denoted by $r(w)$.

Note that it follows from the properties of the random walk on the one-
dimensional lattice with $p_{1}\geq p_{2}$ that a.e. sequence $x\in X_{2}$ has
an initial segment with more $1$’s than $2$’s. This means that $x$ contains
infinitely many free $1$’s and each $2$ gets paired in a sufficiently long
initial segment.

The following lemma is an obvious consequence of the RSK construction.

######  Lemma 1.

Let $\operatorname{sh}([x]_{n})=(\lambda_{1},\lambda_{2})$. Then
$\lambda_{2}=r([x]_{n})$. Namely, the second row of $Q([x]_{n})$ contains the
indices of the free $1$’s, while its first row contains the indices of all the
other elements.

Now we can obtain an explicit description of the partitions $\bar{\xi}_{n}$
and $\bar{\eta}_{n}$, which, in particular, implies Theorem 1 in the two-
letter case.

######  Proposition 1.

The Young partitions on the set $X_{2}={\cal A}_{2}^{\infty}$ can be described
as follows:

  * •

$x\sim_{\bar{\xi}_{n}}y$ $\iff$ all paired coordinates in $[x]_{n},[y]_{n}$
coincide;

  * •

$x\sim_{\bar{\eta}_{n}}y$ $\iff$ $[x]_{n},[y]_{n}$ have the same rank and
$1$’s and $2$’s occur in them with the same multiplicity (these two conditions
amount to the condition that $P_{n}(x)=P_{n}(y)$) and
${\\{x\\}_{n+1}=\\{y\\}_{n+1}}$.

###### Proof.

The first assertion is obvious. To prove the second one, we first show that
$\bar{\eta}_{n}\succ\tau_{n}$. Let $x\sim_{\bar{\eta}_{n}}y$. We must prove
that $x\sim_{\tau_{n}}y$, i.e., $x_{N}=y_{N}$ for $N\geq n+1$. Assume the
contrary and let $m$ be the index of the first coordinate that differs in $x$
and $y$. Without loss of generality, $x_{m}=1$, $y_{m}=2$. But $y_{m}=2$ is a
free element in $[y]_{m}$, hence $x_{m}=1$ is a free element in $[x]_{m}$
(otherwise, $\operatorname{sh}([x]_{m})\neq\operatorname{sh}([y]_{m})$). Then
the tail $\\{y\\}_{m+1}$ contains no free $1$’s, which, as we have noted
above, has probability $0$. So, $\bar{\eta}_{n}\succ\tau_{n}$. The coincidence
of ranks is obvious. It remains to show that in $[x]_{n}$ and $[y]_{n}$ the
elements $1$ and $2$ occur with the same multiplicitiy. Assume to the contrary
that, say, $[y]_{n}$ has more free $2$’s than $[x]_{n}$. Since, almost surely,
each $2$ becomes paired in a sufficiently long initial segment, at the moment
when the “extra” $2$ gets paired, the condition
$\operatorname{sh}([x]_{N})=\operatorname{sh}([y]_{N})$ fails. ∎

######  Corollary 2.

The three (Bernoulli, Young, and de Finetti) tail filtrations on $X_{2}$
satisfy the relation

$\tau_{n}\prec\zeta_{n}\prec\bar{\eta}_{n}.$

######  Proposition 2.

For the two-letter alphabet, Theorem 2 holds, i.e., the sequence of Young
cylinder partitions is total and the Young filtration is ergodic.

###### Proof.

Let $x\sim_{\bar{\xi}}y$ and $x\neq y$. Then there exists $n$ such that
$[x]_{n-1}=[y]_{n-1}$ and $x_{n}\neq y_{n}$. But $x\sim_{\bar{\xi}_{n}}y$,
hence all paired coordinates in $[x]_{n}$ and $[y]_{n}$ coincide, so only free
ones may differ. Without loss of generality, let $x_{n}$ be a free $1$ and
$y_{n}$ be a free $2$. Almost surely, there exists $N>n$ such that this $2$
gets paired in $[y]_{N}$. But the element $x_{n}=1$ remains free in $[x]_{N}$.
Then $x\nsim_{\bar{\xi}_{N}}y$, a contradiction. This proves that
$\bar{\xi}=\varepsilon$.

Now we prove that $\bar{\eta}=\nu$. Consider the de Finetti partitions
$\zeta_{n}$; we will prove that if $x\sim_{\zeta_{n}}y$, then there exists $N$
such that $x\sim_{\bar{\eta}_{N}}y$. Since
$\lim\limits_{n\to\infty}\zeta_{n}=\nu$ by the Hewitt–Savage zero–one law,
this implies that ${\lim\limits_{n\to\infty}\bar{\eta}_{n}=\nu}$, as required.

So, let $x\sim_{\zeta_{n}}y$ but $x\nsim_{\bar{\eta}_{n}}y$, i.e.,
$\\{x\\}_{n+1}=\\{y\\}_{n+1}=:z$, the multiplicities of $1$’s and $2$’s in
$[x]_{n},[y]_{n}$ coincide, but $r([x]_{n})\neq r([y]_{n})$. Consider the
common tail $z$ of $x$ and $y$. As free $1$’s appear in $z$, they get paired
with free $2$’s in $[x]_{n}$ and $[y]_{n}$. Let $N$ be the moment when the
last of the free $2$’s in $[x]_{n},[y]_{n}$ gets paired. It is easy to see
that $\operatorname{sh}([x]_{N})=\operatorname{sh}([y]_{N})$ and,
consequently, $x\sim_{\bar{\eta}_{N}}y$. As discussed above, this completes
the proof. ∎

###  4.2 The general case

In this section, we prove Theorems 1 and 2 in full generality. Recall that
${p_{1}\geq p_{2}\geq\ldots\geq p_{k}>0}$. We need the following lemma, which
shows that, almost surely, each element $a>1$ eventually gets bumped from the
first row of the $P$-tableau.

######  Lemma 2.

Fix $\ell=2,\ldots,k$ and denote by $m_{n}=m_{n}(\ell,x)$ the number of
elements equal to $\ell$ in the first row of the tableau $P_{n}(x)$ for a
random sequence $x\in X$. Then for every $q\in{\mathbb{N}}$, almost surely,
there exists $N\geq q$ such that $m_{N}=0$.

###### Proof.

If $m_{q}=0$, there is nothing to prove. Let $m_{q}\neq 0$. Denote by $a_{n}$
the greatest element less than $\ell$ in the first row of $P_{n}(x)$ (or $1$
if there is no such element). Clearly,

$m_{n+1}=\begin{cases}m_{n}+1&\text{if }x_{n+1}=\ell,\\\ m_{n}-1&\text{if
}a_{n}\leq x_{n+1}<\ell,\\\ m_{n}&\text{if }x_{n+1}>\ell\text{ or
}x_{n+1}<a_{n}.\end{cases}$

The first event has probability $p_{\ell}$, while the second one has
probability ${r_{n}:=p_{a_{n}}+\ldots+p_{\ell-1}\geq p_{\ell-1}}$. If
$p_{\ell-1}>p_{\ell}$, then the desired assertion is obvious. Otherwise, let
$p_{\ell-1}=p_{\ell}=p$ and consider the random walk $\\{z_{n}\\}$ on
$\mathbb{Z}$ with transition probabilities

$z_{n+1}=\begin{cases}z_{n}+1&\text{with probability }p,\\\ z_{n}-1&\text{with
probability }p,\\\ z_{n}&\text{with probability }1-2p.\end{cases}$

Now we use the well-known recurrence criterion for a random walk with step $d$
(see, e.g., [6]): it is recurrent if and only if $\lim\limits_{t\nearrow
1}\int_{-\pi}^{\pi}\frac{dx}{1-t\phi(x)}=\infty$, where
$\phi(x)={\mathbb{E}}e^{ixd}$. In our case, $\phi(x)=2p\cos x+1-2p$; it easily
follows that the criterion is satisfied and the random walk is recurrent.
Hence, by the properties of a recurrent random walk, the random walk
$\\{z_{n}\\}$ starting from $m_{q}$ will reach $0$ with probability $1$. Now
we apply coupling. Namely, consider the random process
$\\{z^{\prime}_{n}\\}_{n\geq q}$ on $(X,m_{p}^{\infty})$ defined as follows.
Take a random variable $\varepsilon_{n}$ independent of all the other ones
that is equal to $1$ with probability $\frac{p}{r_{n}}$ and $0$ with
probability $1-\frac{p}{r_{n}}$. Set

$z^{\prime}_{n+1}=\begin{cases}z^{\prime}_{n}+1&\text{if }x_{n+1}=\ell,\\\
z^{\prime}_{n}-1&\text{if }a_{n}\leq x_{n+1}<\ell\text{ and
}\varepsilon_{n}=1,\\\ z^{\prime}_{n}&\text{otherwise}.\end{cases}$

Clearly, on the one hand, $\\{z^{\prime}_{n}\\}$ has the same distribution as
$\\{z_{n}\\}$ and, consequently, reaches $0$ with probability $1$. On the
other hand, for every $n\geq q$ we have $m_{n}\leq z_{n}^{\prime}$. It follows
that the original process $\\{m_{n}\\}$ also reaches $0$ with probability $1$.
∎

The following lemma completes the proof of Theorem 1.

######  Lemma 3.

Two sequences $x,y\in X$ belong to the same element of the Young tail
partition $\bar{\eta}_{n}$ if and only if their initial segments $[x]_{n}$ and
$[y]_{n}$ belong to the same plactic class and the tails $\\{x\\}_{n+1}$ and
$\\{y\\}_{n+1}$ coincide.

###### Proof.

We argue by induction on the number $k$ of letters in the alphabet ${\cal A}$.
The base case $k=2$ is proved in Proposition 1. We now prove the induction
step $k-1\mapsto k$. Consider the subtableaux $P^{\prime}([x]_{i})$ and
$P^{\prime}([y]_{i})$ in $P([x]_{i})$ and $P([y]_{i})$, respectively,
consisting of all rows except the first one (and filled with $2,\ldots,k$).
Then
$\operatorname{sh}(P^{\prime}([x]_{i}))=\operatorname{sh}(P^{\prime}([y]_{i}))$
for $i\geq n$, hence, by the induction hypothesis,
$P^{\prime}([x]_{n})=P^{\prime}([y]_{n})$ and the sequences of elements bumped
into the second row in $\\{x\\}_{n+1}$ and $\\{y\\}_{n+1}$ coincide. We claim
that $m_{n}(k,x)=m_{n}(k,y)$ in the notation of Lemma 2. Assume to the
contrary that, say, $m_{n}(k,x)>m_{n}(k,y)$. Since the shapes of the growing
tableaux coincide, it is clear that the difference $m_{i}(k,x)-m_{i}(k,y)$ can
decrease only if $k$ gets bumped from the first row of $P([x]_{i})$ and a
smaller element gets bumped from the first row of $P([y]_{i})$, which, as
noted above, cannot happen. However, it follows from Lemma 2 that there exists
$j>n$ such that $m_{j}(k,x)=0$, a contradiction. Hence,
$m_{n}(k,x)=m_{n}(k,y)$, and it follows from the above considerations that
elements equal to $k$ occupy the same positions in $\\{x\\}_{n+1}$ and
$\\{y\\}_{n+1}$. Now note that these elements do not affect the growth of the
subtableaux filled with the smaller elements. Denote by $x^{\prime}$ and
$y^{\prime}$ the subsequences in $x$ and $y$, respectively, obtained by
discarding the elements equal to $k$. It follows from what we have proved that
$x^{\prime}\sim_{\bar{\eta}_{n^{\prime}}}y^{\prime}$, where $n^{\prime}$ is
the number of elements less than $k$ in $[x]_{n}$ and $[y]_{n}$. It remains to
apply the induction hypothesis to $x^{\prime}$ and $y^{\prime}$. ∎

######  Corollary 3.

$\bar{\xi}_{n}\prec\sigma_{n},\qquad\bar{\eta}_{n}\succ\zeta_{n}\succ\tau_{n}.$

Now we turn to the proof of Theorem 2.

1\. If $x\sim_{\bar{\xi}}y$, then
$\operatorname{sh}([x]_{n})=\operatorname{sh}([y]_{n})$ for all $n$, and it
follows from Lemma 3 with $n=0$ that $x=y$.

2\. As in Proposition 2, we want to use the de Finetti partitions and the
Hewitt–Savage law. Namely, the desired result follows by the Hewitt–Savage law
from the following lemma.

######  Lemma 4.

If $x\sim_{\zeta_{n}}y$, then there exists $N\geq n$ such that
$x\sim_{\bar{\eta}_{N}}y$.

###### Proof.

Since $\zeta_{n}$ is the orbit partition for an action of the symmetric group
${\mathfrak{S}}_{n}$, it suffices to prove the assertion in the case where $x$
and $y$ are obtained from each other by the action of a Coxeter generator
$\sigma_{i}=(i,i+1)$, i.e., by a transposition of $x_{i}$ and $x_{i+1}$.
Assume without loss of generality that $x_{i}=u<v=x_{i+1}$. Then $y_{i}=v$,
$y_{i+1}=u$, and $y_{j}=x_{j}$ for $j\neq i,i+1$.

Denote by $R^{(j)}(x)$ and $R^{(j)}(y)$ the first rows of the tableaux
$P_{j}(x)$ and $P_{j}(y)$, respectively (as multisets). We claim that almost
surely there exists $N\geq i+1$ such that $R^{(N)}(x)=R^{(N)}(y)$. If
$R^{(i+1)}(x)=R^{(i+1)}(y)$, there is nothing to prove. Otherwise, $\max
R^{(i)}(x)=u$. Set $v_{i+1}:=v$. Then
$R^{(i+1)}(x)=R^{(i+1)}(y)\cup\\{v_{i+1}\\}$.

Assume that at the $j$th step

$R^{(j)}(x)=R^{(j)}(y)\cup\\{v_{j}\\}.$ (2)

Set $A_{j}:=\\{d\in R^{(j)}(x):d<v_{j}\\}$ and ${B_{j}:=\\{d\in
R^{(j)}(x):d\geq v_{j}\\}\setminus\\{v_{j}\\}}$ (multisets) and denote
$u_{j}:=\max A_{j}$. In particular, $u_{i+1}=u$ and $B_{i+1}=\emptyset$. Look
at the insertion of an element $x_{j+1}$ with $j>i$. Clearly, if
$x_{j+1}<u_{j}$ or $x_{j+1}\geq v_{j}$, then $R^{(j)}(x)$ and $R^{(j)}(y)$
undergo the same changes; in this case, we set $v_{j+1}=v_{j}$, and (2)
remains valid.

If ${u_{j}\leq x_{j+1}<v_{j}}$, then
$R^{(j+1)}(x)=R^{(j)}(x)\setminus\\{v_{j}\\}\cup\\{x_{j+1}\\}$ and two cases
are possible. If $B_{j}\neq\emptyset$, then
${R^{(j+1)}(y)=R^{(j)}(y)\setminus\\{\min B_{j}\\}\cup\\{x_{j+1}\\}}$, and (2)
remains valid with $v_{j+1}=\min B_{j}$. Finally, if ${B_{j}=\emptyset}$, then
$R^{(j+1)}(y)=R^{(j)}(y)\cup\\{x_{j+1}\\}$ and $R^{(j)}(x)=R^{(j)}(y)$.

We claim that this will eventually happen with probability $1$. Assume the
contrary. Note that $v_{j}$ never decreases and can increase only finitely
many times, because the alphabet ${\cal A}$ is finite. Let $v_{j}=v$ for all
sufficiently large $j$. By Lemma 2, almost surely there are infinitely many
$j$ such that $m_{j}(v,y)=0$, i.e., $v\notin B_{j}$. Hence, almost surely one
of them is succeeded by the event $u_{j}\leq x_{j+1}<v$ (which has probability
$\geq p_{v-1}>0$). If at this moment $B_{j}\neq\emptyset$, then $v_{j+1}=\min
B_{j}>v$, a contradiction. Therefore, $B_{j}=\emptyset$ and, as shown earlier,
$R^{(j)}(x)=R^{(j)}(y)$.

So, we have proved that if $x\sim_{\zeta_{n}}y$, then with probability $1$
there exists $N$ such that $P_{N}(x)$ and $P_{N}(y)$ have the same first row.
But then the sequences of elements bumped into the second row in these
tableaux also differ only by a permutation, hence, we obtain by induction that
all rows (there are finitely many of them) eventually become equal. The lemma
is proved. ∎

As we have discussed earlier, the second assertion of Theorem 2 follows from
Lemma 4 by the Hewitt–Savage zero–one law. The theorem is proved.

## References

  * [1] W. Fulton, Young Tableaux With Applications to Representation Theory and Geometry, Cambridge University Press, 1997.
  * [2] S. V. Kerov, Asymptotic Representation Theory of the Symmetric Group and its Applications in Analysis, Amer. Math. Soc., Providence, RI, 2003.
  * [3] S. V. Kerov and A. M. Vershik, The characters of the infinite symmetric group and probability properties of the Robinson–Schensted–Knuth algorithm, SIAM J. Algebraic Discrete Methods 7, No. 1, 116–124 (1986).
  * [4] D. Romik and P. Śniady, Jeu de taquin dynamics on infinite Young tableaux and second class particles, Ann. Probab. 43, No. 2, 682–737 (2015).
  * [5] P. Śniady, Robinson–Schensted–Knuth algorithm, jeu de taquin, and Kerov–Vershik measures on infinite tableaux, SIAM J. Discrete Math. 28, No. 2, 598–630 (2014).
  * [6] F. Spitzer, Principles of Random Walk, Springer-Verlag, New York–Heidelberg, 1976.
  * [7] A. M. Vershik, Description of invariant measures for the actions of some infinite-dimensional groups, Sov. Math. Dokl. 15, 1396–1400 (1974).
  * [8] A. M. Vershik, The theory of filtrations of subalgebras, standardness, and independence, Russian Math. Surveys 72, No. 2, 257–333 (2017).
  * [9] A. M. Vershik, Three theorems on the uniqueness of the Plancherel measure from different viewpoints, Proc. Steklov Inst. Math. 305, 63–77 (2019).
  * [10] A. M. Vershik, On the justification of the ergodic method for describing central measures, to appear in Dokl. Akad. Nauk.
  * [11] A. M. Vershik and N. V. Tsilevich, Markov measures on Young tableaux and induced representations of an infinite symmetric group, Theory Probab. Appl. 51, No. 1, 211–223 (2006).


# Filtered-Guided Diffusion: Fast Filter Guidance for Black-Box Diffusion
Models

Zeqi Gu
Cornell Tech
<EMAIL_ADDRESS>Abe Davis
Cornell University
<EMAIL_ADDRESS>
###### Abstract

Recent advances in diffusion-based generative models have shown incredible
promise for Image-to-Image translation and editing. Most recent work in this
space relies on additional training or architecture-specific adjustments to
the diffusion process. In this work, we show that much of this low-level
control can be achieved without additional training or any access to features
of the diffusion model. Our method simply applies a filter to the input of
each diffusion step based on the output of the previous step in an adaptive
manner. Notably, this approach does not depend on any specific architecture or
sampler and can be done without access to internal features of the network,
making it easy to combine with other techniques, samplers, and diffusion
architectures. Furthermore, it has negligible cost to performance, and allows
for more continuous adjustment of guidance strength than other approaches. We
show FGD offers a fast and strong baseline that is competitive with recent
architecture-dependent approaches. Furthermore, FGD can also be used as a
simple add-on to enhance the structural guidance of other state-of-the-art I2I
methods. Finally, our derivation of this method helps to understand the impact
of self attention, a key component of other recent architecture-specific I2I
approaches, in a more architecture-independent way.

Figure 1: We present Filter-Guided Diffusion (FGD), a novel approach to
guiding black-box diffusion processes based on an adaptive filter. Our method
is fast, architecture-independent, and allows for continuous control over the
strength of guidance. Here we use a filter derived from the guide image on the
top left to guide the structure of images produced by Stable Diffusion [27].
Increasing the strength of the filter preserves more of the guide image’s
structure. The middle grid of results shows the same guide filter used with
three different text prompts. The grid on the right shows the same text prompt
sampled with three different seeds. All of the results here show FGD as
standalone guidance approach. It can also be combined with existing methods to
offer finer control over the preservation of guide structure.

##  1 Introduction

Image-to-Image translation (I2I) is the task of transforming a given image
from one domain to another target domain. Since the advent of diffusion
models, the most prevalent way to specify the target domain is through text
prompts. However, as target contents described by language can be realized
without sticking to the original image, one of the most important question
regarding translation consistency is how to maintain the original layout and
structure. Many methods have been proposed recently, and they are often
dependent upon model tuning [14, 35], model architecture [32], sampling
methods [32, 23], or prompting scheme [9, 15], etc. We present Filter-Guided
Diffusion (FGD), a simple strategy for guiding diffusion processes by making
adaptive adjustments to the mean values produced at each diffusion step. FGD
guides the structure of generated outputs without additional training or
access to internal features of the diffusion network, making it highly
portable to different architectures and complementary to other guidance
strategies.

At the core of our approach are three observations. First, we can limit the
diffusion process to specific frequencies by selectively replacing frequency
content at each diffusion step. Second, we can adjust the amount of
replacement at each step based on how likely the process is to converge on a
result with desired structure, which lets us control the overall strength of
guidance while keeping the diffusion process as close as possible to its
training distribution. Finally, we can fit our guidance in the frequency
domain to the structure of an example image using a fast linearization of the
joint bilateral filter. We derive each of these observations and show that
they bring the performance of black-box diffusion guidance much closer to that
of the architecture-aware ones. In summary, our key contributions include:

  1. 1.

We derive an black-box guidance strategy from the frequency analysis of a
general diffusion process.

  2. 2.

We show how the amount of guidance can be varied smoothly with our method.

  3. 3.

We show quantitatively and qualitatively that our method provides a strong,
fast baseline for guidance, and that it can also be used as a plug-in for
various other I2I diffusion methods offering improved structural control.

##  2 Related Work

###  2.1 Image-to-Image Translation

I2I has been an active area of research for long. Early work on Laplacian
Pyramid Blending [2] focused on applying transferring detail from a target
image to the structure of a source, where detail and structure were
distinguished by respective bands in the frequency domain. Later work used
generative adversarial networks to learn translation mappings from
distributions of training data, but such methods usually required images from
both domains [11, 36, 21], training on the specific tasks [13], or difficult
inversion to the latent space [34, 12, 3, 22].

Besides image-based guidance, many approaches now use text to guide the
translation. Diffusion models have proven especially powerful when combined
with LLMs [27, 19, 26, 28], replacing the need for image data representing the
target domain at runtime. Our work builds on this approach by adding a
convenient and very general way to condition on the structure of a guide
image. Some methods, like DiffEdit [6], focus on deriving and using masks
(e.g., from text prompts) to determine what parts of an image the diffusion
process should be allowed to change. Their direction of localizing editing
region and preserving the background is somewhat orthogonal to ours.

###  2.2 Architecture-Independent Guided Diffusion

As pre-trained large diffusion models often lack guidance besides text, finer
control over the generation process has become an important goal. One of the
earliest works in this space was SDEdit [18], which starts the reverse
diffusion process from the result of applying a partial forward process to
some guide image. Like our approach, SDEdit is architecture-independent, which
has made it a common baseline for guided diffusion. Another architecture-
independent approach is ILVR [4], which effectively conditions the generation
of new images on a downsampled version of the guidance image. Our method can
be seen as an extension of this approach where we condition on the edge-aware
structure of an image and make the strength of this conditioning adaptive.

###  2.3 Architecture-Dependant Guided Diffusion

Recent and concurrent methods have explored architecture-dependent strategies
for guidance. Namely, Plug-and-Play (PnP) [33] and P2P0 [23], which are very
similar approaches based on the attention modules of Stable Diffusion [27].
They first invert the guide image back to noise via DDIM [29] to acquire the
features of the guide image in the diffusion process. They then inject these
features into the model when generating the final output for a given text
prompt. This approach preserves structure better than SDEdit, but is tied to a
specific architecture and sampling method (Stable Diffusion and DDIM). The use
of DDIM also limits the ability to sample from diverse results, as the
sampling strategy itself is used as a key component of guidance. In terms of
preserving structure, this kind of architecture-aware approach has a distinct
advantage over methods like ours that treat the network as a black box, yet
our results suggest this advantage may be smaller than previously assumed.

Figure 2: FGD on GLIDE Our method allows one to control the amount of
guidance. Here we see results for different text prompts and guidance detail
parameters. These results were produced with GLIDE using DDPM and
$t_{stop}=50$. We notice that when the text prompt is less likely given a
guidance image, this tends to result in more modal, less continuous variation
with $\delta$. We observe this in the case of the rabbit, which is expected to
have much larger ears, and the frog. In the case of the frog, the mode
switches suddenly when the mouse’s ears can be explained as eyes. The bear and
tiger have more continuous transitions, as they are more visually similar to
begin with.

##  3 Diffusion Background

We begin with a review of the general diffusion process on which our approach
is based. Our approach should work on any model using a similar process—even,
as we show, models like Stable Diffusion [27] that operate on a latent image
space.

Forward Process: The forward diffusion process takes a sample $x_{0}\sim
q(x_{0})$ from our data distribution and iteratively mixes it with Gaussian
noise. We can describe this process in terms of consecutive steps $x_{t-1}$
and $x_{t}$:

$q(x_{t}|x_{t-1}):=\mathcal{N}(\sqrt{\alpha_{t}}x_{t-1},\beta_{t})$ (1)

where $\alpha_{t}=1-\beta$. Unrolling this equation gives:

$q(x_{t}|x_{0}):=\mathcal{N}(\sqrt{\tilde{\alpha}_{t}}x_{0},1-\tilde{\alpha}_{t})$
(2)

where $\tilde{\alpha}_{t}=\prod_{i=1}^{t}\alpha_{i}$. We can interpret Eq. 2
as a linear combination of the initial data sample and noise
$\mathbf{z}\sim\mathcal{N}(0,1){}$ drawn from a standard normal distribution:

$x_{t}=\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}\underbrace{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\sqrt{\tilde{\alpha}_{t}})}_{\begin{subarray}{c}\text{\footnotesize
signal}\\\ \text{\footnotesize
strength}\end{subarray}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\overbrace{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x_{0}}^{\text{\footnotesize\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}signal}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}+\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}\underbrace{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\sqrt{1-\tilde{\alpha}_{t}})}_{\text{\footnotesize
noise
strength}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\overbrace{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{z}}^{\text{\footnotesize\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}noise}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$
(3)

Eq. 3 lets us interpret $x_{t}$ as a noisy measurement of a signal $x_{0}$,
where our signal strength is $\sqrt{\tilde{\alpha}_{t}}$ and our noise
strength is $\sqrt{1-\tilde{\alpha}_{t}}$. This interpretation helps to frame
the reverse process in terms of denoising.

Reverse Process: The reverse process is meant to approximate repeated sampling
from the posterior distribution $q{}(x_{t-1}|x_{t})$, which we approximate as
Gaussian:

$q(\bar{x{}}_{t-1}|\bar{x{}}_{t})\approx\mathcal{N}(\mathbf{\mu}_{\theta}(\bar{x{}}_{t}),\sigma_{t}^{2})$
(4)

To perform this sampling, we need to estimate the means
$\mathbf{\mu}_{\theta}(\bar{x{}}_{t})$ (and optionally, variances
$\sigma_{t}^{2}$) associated with each reverse step. These estimates are
derived from a network $\mathbf{\epsilon}_{\theta}{}$, which is usually
trained to estimate the noise $\mathbf{\epsilon}_{\theta}{}(\bar{x{}}_{t})$
associated with a given $\bar{x{}}_{t}$ (i.e., the value of $\mathbf{z}{}$
from Eq. 3 corresponding to input $\bar{x{}}_{t}$)111Some variations of
diffusion predict the means $\mathbf{\mu}_{\theta}{}(\bar{x{}})$ or denoised
images $s_{0}$ directly. Here we follow the approach described in [10].. Taken
together with the input $\bar{x{}}_{t}$, this also yields a prediction $s_{t}$
of the denoised input signal $\bar{x{}}_{0}$ at each step. Here, writing out
the connection between our network’s input $\bar{x{}}_{t}$, its output
$\mathbf{\epsilon}_{\theta}{}(\bar{x{}}_{t})$, and the intermediate denoised
predictions $s_{t}$ helps to connect our reverse process with the forward one:

$\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\overbrace{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\bar{x{}}_{t}}^{\text{\footnotesize\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}observation}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}=\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}\underbrace{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\sqrt{\tilde{\alpha}_{t}})}_{\begin{subarray}{c}\text{\footnotesize
signal}\\\ \text{\footnotesize
strength}\end{subarray}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\overbrace{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}s_{t}}^{\begin{subarray}{c}\text{\scriptsize{\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}signal}}\\\
\text{\scriptsize{\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}estimate}}\end{subarray}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}+\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}\underbrace{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\sqrt{1-\tilde{\alpha}_{t}})}_{\text{\footnotesize
noise
strength}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\overbrace{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{\epsilon}_{\theta}{}(\bar{x{}}_{t})}^{\begin{subarray}{c}\text{\scriptsize{\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}estimated}}\\\
\text{\scriptsize{\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}noise}}\end{subarray}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$
(5)

This connection informs how $\mathbf{\epsilon}_{\theta}$ is usually trained—by
applying Eq. 3 to training data and predicting $\mathbf{z}$. In practice, an
iterative approach to estimating $\bar{x{}}_{0}$ performs better, where the
network is used to approximate the means
$\mathbf{\mu}_{\theta}(\bar{x{}}_{t})$ of Eq. 4 at each step:

$\mathbf{\mu}_{\theta}{}(\bar{x{}}_{t})=\frac{1}{\sqrt{\alpha_{t}}}\left(\bar{x{}}_{t}-\frac{\beta_{t}}{\sqrt{1-\tilde{\alpha}_{t}}}\mathbf{\epsilon}_{\theta}{}(\bar{x{}}_{t},t)\right)$
(6)

We refer to [10] for the derivation of Eq. 6, which is combined with Eq. 4 to
compute $\bar{x{}}_{t-1}$ at each step.

###  3.1 Black-Box Diffusion

The training distribution for a given diffusion model is determined by the
forward process used in training. We derive our approach directly from this
process, which is what makes it so transferable to different architectures. We
assume only that the variance schedule used in training (i.e., the
$\alpha_{i}$’s and $\beta_{i}$’s) is either known or that it can be estimated
at run time, and that we are free to observe and modify the input to
$\mathbf{\epsilon}_{\theta}{}$ at each step of our guided reverse process.
These are very general assumptions, which makes our method widely applicable.

Figure 3: Signal Strength, Diffusion, & Filtering Our guide filter
$\mathbf{f}$ separates images into guided structure frequencies and unguided
detail frequencies. Column (b) shows the filtered structure of a guide image,
which is dominated by low frequencies, while column (c) shows the residual
detail. Forward diffusion mixes broad-spectrum Gaussian noise (d) with images.
Natural images statistics have higher energy at low frequencies, resulting in
higher SnR at these frequencies of our mixture (e). For this reason, we see
the structure component of our mixture (f) change much less than our detail
component (g). Our method takes advantage of this observation to guide
diffusion without directing network inputs away from the training
distribution.

##  4 Method

We begin by proposing a definition of guidance in terms of some input guide
image $x_{g}$ and filter $\mathbf{f}$. At a high level, the guide filter
$\mathbf{f}$ defines the properties we want to guide, and the filtered guide
image $\mathbf{f}(x_{g})$ tells us what values those properties should take.
More specifically, we formulate guidance as control over generated sample
images $\hat{x{}}_{0}$ such that:

$\mathbf{f}(\hat{x{}}_{0})\approx\mathbf{f}(x_{g})$ (7)

A trivial solution to this guidance criteria would be to set
$\hat{x{}}_{0}=x_{g}{}$. However, this solution leaves no room for variation
that can be used to satisfy other goals (e.g., diverse results and text-based
guidance). To be useful, we need to balance our guidance goal against the
decisions of our diffusion model. Our approach will follow one basic design
principle: to intervene in the diffusion process as little and gradually as
possible such that Eq. 7 is satisfied. This principle ensures that we keep our
guided process as close to our original training distribution as possible. We
derive our method from this principle under the limiting assumption that
$\mathbf{f}$ can be approximated as a linear function.

###  4.1 Adaptive Filtering

If the guide filter $\mathbf{f}$ is linear then variation within its null
space will have no effect on Eq. 7. As such, a less trivial solution to Eq. 7
replaces only those parts of our unguided result $\bar{x{}}_{0}$ that fall
outside of this null space:

$\hat{x{}}_{0}=\bar{x{}}_{0}-\mathbf{f}(\bar{x{}}_{0})+\mathbf{f}(x_{g})$ (8)

Here it is worth noting that, given appropriate choices of $\mathbf{f}$, Eq. 8
can be reduced to older training-free I2I methods like Laplacian blending [2]
or Hybrid Images [20].222Here, these methods would be blending the output of
unguided diffusion with our guide image. The downside to this kind of solution
is that it offers no opportunity for the diffusion process to compensate or
adapt to our added guidance. We can provide such an opportunity by enforcing
guidance more gradually at each step of the reverse process. We first define
the guidance vector $\mathbf{d}_{t}$ associated with step $t$ as the filtered
difference between $\mathbf{\mu}_{\theta}{}(\hat{x{}}_{t})$ and our target:

$\mathbf{d}_{t}=\mathbf{f}(x_{g})-\mathbf{f}(\mathbf{\mu}_{\theta}{}(\hat{x{}}_{t}))$
(9)

Adding $\mathbf{d}_{t}$ to each $\hat{x{}}_{t}$ results in a much more gradual
application of guidance, as the magnitude of $\mathbf{d}_{t}$ at each step is
limited by the scheduled variance associated with that step. We scale
$\mathbf{d}_{t}$ by an adjustable factor $\lambda_{t}$ to further control the
strength of guidance.

$\hat{x{}}_{t-1}=\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}\underbrace{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{\mu}_{\theta}{}(\hat{x{}}_{t})+\sigma_{t}^{2}\mathbf{z}{}}_{\text{\footnotesize
same as
Eq.~{}\ref{eq:reversediffusionstep}}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}+\color[rgb]{0.2,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.5,1.0}\overbrace{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\lambda_{t}\mathbf{d}_{t}}^{\begin{subarray}{c}\text{\scriptsize
adaptive}\\\ \text{\scriptsize
adjustment}\end{subarray}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$
(10)

Here, setting $\lambda_{t}=1$ would fix the filtered frequencies to their
value in the guide image, effectively removing control of all filtered
frequencies from the network. This has two problems. The first is that
$\mathbf{d}_{t}$ is likely to push our diffusion process away from its
training distribution for most diffusion steps. To see this, note from Eq. 3
that each $x_{t}$ is itself distributed with variance no less than
$1-\tilde{\alpha}_{t}$, which is likely much higher than the variance of our
filtered guide image for most of the diffusion process. The second problem
with setting $\lambda_{t}=1$ is that it places rather strict limits on the
network’s ability to synthesize new content. To deal with the first problem we
let $\lambda_{t}$ scale with the expected signal strength
$\sqrt{\tilde{\alpha}_{t}}$ from Eq. 3, which helps ensure that any signal we
add at a given step will be of magnitude less than or equal to that of a
plausible training image. This keeps our filtered frequencies in-distribution,
but does not yet address the second problem; simply setting
$\lambda_{t}=\sqrt{\tilde{\alpha}_{t}}$ would still effectively treat Eq. 7 as
a hard constraint by the end of the diffusion process. To relax this, we let
$\lambda_{t}$ scale with $\hat{\mathbf{d}}_{t}$, the mean pixel magnitude in
$\mathbf{d}_{t}$:

$\lambda_{t}=\text{min}\left(\frac{\hat{\mathbf{d}}_{t}}{\delta{}},1\right)\cdot\sqrt{\tilde{\alpha}_{t}}$
(11)

This results in gradually reducing guidance when the process appears on track
to match our guide image. The detail parameter $\delta{}$ controls how much
freedom we give the network to wander from the guide structure throughout this
process. We typically stop applying guidance some number of steps $t_{stop}$
before the end of inference, after which the network has usually settled into
a new mode. Fig. 4 shows the behavior of different $\delta{}$ applied to
GLIDE, as well as the convergence of the network after step $t_{stop}$. Fig. 1
shows results with Stable Diffusion [27], with all filter parameters fixed
except for $\delta{}$, which decreases from left to right for each example.

###  4.2 Filter Design

The success of our approach hinges on guiding the diffusion process while also
keeping it close to its training distribution. Our adaptive scaling of
adjustments helps to balance these goals, but if we interpret the values being
adjusted as a product of the process described in Eq. 3, our strategy still
assumes that each adjustment $\lambda_{t}\mathbf{d}_{t}$ will impact the
“signal” signal portion of these values more than the corresponding “noise”
portion. Put another way, it assumes that the signal-to-noise ratio (SNR) of
our filtered content should be higher than that of the content we leave for
the network to generate. Fortunately, natural image statistics make this
simple to achieve. Gaussian noise is broad spectrum, while natural images have
have an amplitude spectrum that scales roughly with inverse frequency [8, 30].
This means that, in general, low-pass filters (e.g., a Gaussian blur) make
good guide filters. An even better choice of filter is one based on the joint
bilateral [7, 24], which yields a low-pass filter that preserves edges from a
guide image (see Fig. 3). The results shown in this paper and most of the
results in our supplemental use a joint bilateral filter based on the guide
image $x_{g}$.

Figure 4: $\hat{\mathbf{d}}_{\hat{x{}}_{t}}$ with Different $\delta$
$\hat{\mathbf{d}}_{\hat{x{}}_{t}}$ over different time steps for GLIDE
diffusion guided by the mouse image using our method with the text prompt
”bear”. Each line shows the adaptive behavior with a different value of
$\delta{}$. Guidance stops at $t=40$, after which we see the network converge
on a mode that has adopted much of the guide image’s structure. Higher values
of $\delta{}$ let results differ more from the guide image, which tends to
result in more detail added by the network.

###  4.3 Fast Bilateral Tensor

Running a joint bilateral filter on 3-4 channel images can be slow in general.
There are various approximations that decrease computation time, but the small
image size of current diffusion models (e.g., $64\times 64\times c$ for GLIDE
and Stable Diffusion) makes it possible to compute the exact filter extremely
efficiently by packing the filter coefficients into a single tensor operation
that can be applied to the entire image. The size of this tensor does not
scale with the number of channels, making it suitable for latent spaces like
the one used in Stable Diffusion [27], and the time to evaluate does not
depend on kernel size, so arbitrary spatial and value standard deviations are
equally fast. Computing the filter this way takes milliseconds in our
implementation, adding negligible cost to the diffusion process.

Recap of Changes: Note that the only actual change we have made to the
diffusion process is that Eq. 4 from the unguided process is replaced with Eq.
10, which adds a scaled update at each step. This can be implemented with few
lines of code.

Figure 5: Qualitative Comparison We use Wild Web, AFHQ and Landscape to
compare with 3 groups of methods: (1) strong GAN benchmark – VQ+CLIP, (2)
diffusion baselines – DDIM and SDEdit with different hyper-parameters, and (3)
latest state-of-the-art diffusion methods – PnP and DiffuseIT. As seen on the
right, our simple method (FGD with PLMS and DDIM inversion; FGD plugged into
SDEdit of strength 0.6) is comparable with strong, architecture and sampling
dependent ones such as PnP.

##  5 Implementation & Test Parameters

To use FGD, we only need access to the inputs and outputs of each step, as
well as the $\sqrt{\tilde{\alpha}_{t}}$ used to train the model. At each step,
we take the current means, apply our joint bilateral tensor, and measure
$\mathbf{d}_{t}$, the difference of this result with the filtered guide image.
$\hat{\mathbf{d}}_{\hat{x{}}_{t}}$ is just the $L_{1}$ norm of this difference
normalized by the number of pixel values in our image. We then use Eq. 11 to
calculate $\lambda$ and Eq. 10 to update our means.

Current top-performing Text-to-Image diffusion models can be divided into 2
types based on what space the diffusion is done in: pixel space or some latent
space. The former includes the series of GLIDE [19] and DALL-E [26], and the
latter includes Stable Diffusion [27]. We test our method with models of both
types that have publicly available pre-trained weights, namely GLIDE and
Stable Diffusion v1–4. Both models perform diffusion in a $64\times 64$
resolution image space, then upsample to $256\times 256$ and $512\times 512$
respectively. We also tested FGD with different sampling methods: DDPM [10],
DDIM [29] and PLMS [17]. As shown in other works, DDIM and PLMS tend to result
in structure closer to the guide image, while DDPM and SDEdit [18] offer more
diverse results. Most of our experiments were run on an NVIDIA RTX A6000.
Default parameters used for testing each method are given in Table 1, but as
we show in our results and supplemental, changing $t_{stop}$ and $\delta$
allows one to explore different balances of network-provided detail and guide
image structure.

Method | Model | $t_{start}$ | $t_{stop}$ | $\delta$ | $\sigma$
---|---|---|---|---|---
DDIM | SD v1–4 | 50 | 10 | 0.05 | 5, 0.35
PLMS | SD v1–4 | 50 | 10 | 0.05 | 5, 0.35
SDEdit | SD v1–4 | 50 | 10 | 0.05 | 5, 0.35
DDPM | SD v1–4 | 50 | 25 | 0.2 | 5, 0.35
DDPM | GLIDE | 100 | 50 | 0.6 | 3, 0.2
Table 1: Hyper-parameters. Our method needs tuning on 5 variables: the start ($t_{start}$) and end time ($t_{stop}$) of the filtering, the structure difference control ($\delta$), and the spatial and value standard deviation of the bilateral filter (the first value in $\sigma$ is for spatial and the second is for value). Since PLMS [17] is the default sampler of Stable Diffusion [27], we call its combination with our method as “FGD” or “FGD (stand)alone”. Base Method | Sampling w/o FGD | Sampling w/ FGD | Sampling Diff | Total w/o FGD | Total w/ FGD | Total Diff
---|---|---|---|---|---|---
DDIM | 4.314 | 4.376 | 0.062 | 21.165+52.013 | 21.616+52.013 | 0.451
PLMS | 4.332 | 4.475 | 0.143 | 19.239+52.013 | 22.056+52.013 | 2.817
SDEdit .6 | 2.602 | 2.676 | 0.074 | 17.193 | 19.861 | 2.668
SDEdit .75 | 3.185 | 3.273 | 0.088 | 17.863 | 20.471 | 2.608
SDEdit .85 | 3.594 | 3.675 | 0.081 | 18.179 | 20.953 | 2.774
Table 2: Added Computation Cost of FGD (in seconds). FGD adds negligible time
to most of the methods. While “Sampling” refers to only the generation
process, “Total” includes not only that but also all pre-computations such as
loading required information. The 52.013s added in the first two rows is the
time of using DDIM to invert the image back to the latent space. Note that
DDIM inversion is optional for all samplers and we chose to use them for more
deterministic evaluation. As SDEdit encodes the image stochastically, it does
not have this overhead. The largest computational cost added by FGD comes from
the construction of the fast bilateral tensor, which makes the “Total Diff” a
larger value than “Sampling Diff”. Figure 6: Results of Standalone FGD Our
method by itself is able to translate images to different styles, objects, and
even allows satisfactory local editing. Figure 7: Diversity Comparison FGD
produces diverse results when used with nondeterministic methods, such as
SDEdit as shown above. Although one hyper-parameter of PnP, the feature
injection threshold, controls the translation similarity to some degree, it
essentially lacks the versatility due to being bounded with DDIM.

##  6 Evaluation

We conduct extensive experiments on 2 existing datasets well suited for I2I
translation tasks: Animal Faces-HQ (AFHQ) [5] and Landscape Pictures [1]. AFHQ
consists of faces of various animals including cats, dogs, tigers, foxes,
etc., and Landscape consists of 6 types of natural scenes: mountain, desert,
sea, beach, island and Japan. For source (required by DiffuseIT [15]) and
target text prompts we automatically generated by concatenating category words
with the template phrase ”a photo of”. To further diversify test cases, we
created Wild Web that comprises of 168 diverse text-image pairs. All images
were collected from the Internet with manually added captions. For more
details please refer to the supplemental.

###  6.1 Qualitative Results

We first demonstrate that our method can help guide generation in the pixel
space, as shown in Fig. 2, the mouse guide image is successfully transformed
into different animals with different extent of structure similarity guided by
$\delta$. Then we show that joint bilateral guide filter has a similar effect
even when applied in the encoded feature space of Stable Diffusion [27], which
makes sense as the latent space still preserves spatial information such as
structure and layout of the input image. As shown in Fig. 5, our method alone,
or a bare minimum of it plugged into SDEdit [18], already match or surpass
many benchmarks with minimum time cost. In Fig. 6 we show more results of both
content and style translation with FGD alone. Our method can also be combined
with nondeterministic samplers to provide plausible results of great variety.
As shown in Fig. 1 and 7, with different $\delta$ the images can fall into
different modes that preserve different amounts of guide structure.

###  6.2 Quantitative Results

Figure 8: Numerical Evaluation The goal is to balance achieving higher CLIP
similarity score with as small Structure Difference. There is no perfect
metric for evaluating this balance, but methods that perform well should be
near the bottom right corner of each. FGD successfully “pulls down” weaker
methods for all 3 datasets. We connect the results of FGD using $\delta$ 0.05,
0.2, and 0.5 with dash lines and show that our $\delta$ indeed provides an
effective control over image structure. The number right after “SDEdit”
represents the value of its “strength” hyperparameter. Note DiffuseIT does
directly optimization on the 2 metrics shown, therefore it achieves top
numerical results yet is not qualitatively as satisfactory (e.g. Fig. 5).
Figure 9: FGD as a Lightweight Plug-In The technique of our method is parallel
with many existing I2I diffusion-based methods and thus FGD can be plugged
into them to further control the strength of imposing structure information
from the guide image.

For quantitative measurements, we randomly select 335 text-images pairs from
Landscape [1], 48 from AFHQ cat subset [5] (with the text prompt always being
”a photo of a dog”), and use all 168 from the Wild Web. We evaluate along 2
competing dimensions: (1) whether text guidance was satisfied, and (2) whether
the structure of the input image is preserved. We measure text guidance with
CLIP cosine similarity [25], which is the cosine distance between the feature
of the edited results and the feature of the text prompt. A higher value
suggest a more complete translation. We measure structure preservation
Structure Dist [31] with a pre-trained vision transformer. A lower score on
Structure Dist means that the structure of the edited image is more similar to
the input image.

As shown in Fig. 8, our method always significantly reduces the structure
difference between the guide image and the output, at sometimes a small
sacrifice of text alignment. However, the improvement on structure
consistently outweighs the semantic misalignment when added to weaker
baselines like SDEdit. For stronger architecture-dependent baselines like PnP,
our method tends to bring the generation distribution to a different mode that
preserves more structure. Fig. 9 further illustrates these effects. It is not
surprising that the improvement of one metric would lead to worse behavior on
the other since these two metrics are generally at odds. In this scenario, our
model’s contribution is the ability to provide diverse alternative without any
training and almost no overhead.

In Table 2 we compare the runtime of different existing methods with and
without FGD, averaged over all quantitative comparison data. Averaging over
all 5 variations, our method adds 0.089 seconds to the sampling and 2.263
seconds to the entire generation process. The total time of PnP [32]
(including DDIM inversion, feature saving and reading, and sampling) is
193.917 seconds, which is 9.763$\times$ that of SDEdit 0.6 with FGD, and
2.618$\times$ that of PLMS with DDIM inversion and FGD.

###  6.3 Ablation

To study how our results are influenced by different parameters, we conduct
ablation studies on different filter setups as shown in Fig. 10. The
superiority of our chosen values is supported by the fact that their results
(shown in black) are closest to the bottom right. The comparison with ILVR [4]
here shows that a bilateral filter indeed preserves the structure better than
a gaussian filter. We will provide ablations on other hyperparameters in the
supplemental.

Figure 10: Ablations On a 125 image-text pair subset of Wild Web, we compare
results of using bilateral filter with combinations of spatial standard
deviation 3, 5, 11 and value standard deviation 0.1, 0.35, 0.5. We also
compare with variations of ILVR [4], which could on a high level be understood
as replacing our bilateral filter with a gaussian filter. Following the
original paper, we set downsampling factor N to be 4, 8, 16, and 32, and the
conditioning step range to be 10 and 20. We also show the result of DiffEdit
[6] with auto-generated prompts via BLIP [16]. As in Fig. 8, the star,
triangle, and square of the same color represent respectively results with
$\delta$ value 0.05, 0.2, 0.5 under the same setup. Figure 11: Limitations:
FGD guides a purely signal-based notion of structure that does not understand
the semantics of an image. We can see this, for example, when a text prompt
tends toward images with different composition from our guide image. Here, the
prompt ”a portrait of a lady on fire” transitions from a portrait of a woman’s
face to that of a standing woman with a silhouette that looks roughly like the
guide image. This is an advantage for architecture-aware methods, which have
access to network features that carry more of this information.

##  7 Discussion

###  7.1 Relation to Attention Map Replacement

Other concurrent strategies [33, 23] have shown empirically that replacing the
attention map used in a diffusion architecture with that of the guide image
(self-attention) can serve to guide the generated structure. Here we see an
interesting connection with our approach. The joint bilateral, which we use as
our primary guide filter, is designed to estimate local means for edge-aware
denoising by mixing pixels in a target image that share similar values in a
guide image. This builds on the assumption that neighboring pixels with
similar values can be treated as noisy measurements of the same mean. Self-
attention works in a similar manner when attention maps are derived from a
denoising network. Recall that our network is trained to estimate $x_{0}$ (or
a quantity analogous to it) from a noisy measurement $x_{t}$ at each step,
where $x_{t}$ is modeled as normally distributed according to Eq 2. This
amounts to estimating the mean of a noisy measurement at each pixel. We can
therefore think of the maps used in self-attention as a learned variant of the
joint bilateral. Or, similarly, we can think of FGD with a bilateral tensor as
a more tunable fast linear architecture-independent approximation of self-
attention.

###  7.2 Limitations

When designing this approach we took care to ensure that guided inputs to our
network had variance similar to the training distribution. However, there is
no guarantee that a supplied guide image will have structure that is in-
distribution for the network, or that in-distribution images with the supplied
structure will be able to satisfy other objectives (e.g., a text prompt). This
is most noticeable when the given objective makes explaining the guide
structure difficult. When the filter strength is set to be high (i.e.,
$\delta$ is very low) the likelihood of this happening increases, as the
notion of structure becomes much more specific. In practice this can lead to
over-smoothing, and in extreme cases slight halos in the shape of the guide
image.

The use of a simple linear filter in FGD also lacks understanding of semantics
in an image. This can lead to results that preserve the overall geometric
structure of the guide image, but with different meaning to different parts.
For example, in Fig. 11, decreasing the filter strength eventually causes a
portrait of a face to turn into a portrait of a body with a similar silhouette
to the guide image. Here, architecture-aware approaches would have a
fundamental advantage over black-box methods like FGD if the goal is to
preserve the original semantics of a face portrait, since internal features of
the network may capture some of this information, making it possible to
incorporate in the notion of guide structure.

###  7.3 Conclusion

This work presents a simple, efficient, and general approach to guiding
diffusion models. Our work achieves results that are much closer to state-of-
the-art architecture-specific methods while treating the diffusion network as
a black box, and can easily be combined with others methods to allow finer
control of structure guidance. These qualities make it a convenient and fast
add-on to diffusion-based applications looking to add image-based control.

## References

  * [1] Mahmoud Afifi, Marcus A Brubaker, and Michael S Brown.  Histogan: Controlling colors of gan-generated and real images via color histograms.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 7941–7950, 2021.
  * [2] Peter J. Burt and Edward H. Adelson.  The Laplacian Pyramid as a Compact Image Code, page 671–679.  Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1987.
  * [3] Tao Chen, Ming-Ming Cheng, Ping Tan, Ariel Shamir, and Shi-Min Hu.  Sketch2photo: Internet image montage.  ACM transactions on graphics (TOG), 28(5):1–10, 2009.
  * [4] Jooyoung Choi, Sungwon Kim, Yonghyun Jeong, Youngjune Gwon, and Sungroh Yoon.  Ilvr: Conditioning method for denoising diffusion probabilistic models, 2021.
  * [5] Yunjey Choi, Youngjung Uh, Jaejun Yoo, and Jung-Woo Ha.  Stargan v2: Diverse image synthesis for multiple domains.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 8188–8197, 2020.
  * [6] Guillaume Couairon, Jakob Verbeek, Holger Schwenk, and Matthieu Cord.  Diffedit: Diffusion-based semantic image editing with mask guidance.  arXiv preprint arXiv:2210.11427, 2022.
  * [7] Elmar Eisemann and Frédo Durand.  Flash photography enhancement via intrinsic relighting.  ACM Trans. Graph., 23(3):673–678, aug 2004.
  * [8] David J. Field.  Relations between the statistics of natural images and the response properties of cortical cells.  J. Opt. Soc. Am. A, 4(12):2379–2394, Dec 1987.
  * [9] Amir Hertz, Ron Mokady, Jay Tenenbaum, Kfir Aberman, Yael Pritch, and Daniel Cohen-Or.  Prompt-to-prompt image editing with cross attention control.  arXiv preprint arXiv:2208.01626, 2022.
  * [10] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  Advances in Neural Information Processing Systems, 33:6840–6851, 2020.
  * [11] Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A Efros.  Image-to-image translation with conditional adversarial networks.  CVPR, 2017.
  * [12] Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen.  Progressive growing of gans for improved quality, stability, and variation.  arXiv preprint arXiv:1710.10196, 2017.
  * [13] Tero Karras, Samuli Laine, and Timo Aila.  A style-based generator architecture for generative adversarial networks.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4401–4410, 2019.
  * [14] Bahjat Kawar, Shiran Zada, Oran Lang, Omer Tov, Huiwen Chang, Tali Dekel, Inbar Mosseri, and Michal Irani.  Imagic: Text-based real image editing with diffusion models.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6007–6017, 2023.
  * [15] Gihyun Kwon and Jong Chul Ye.  Diffusion-based image translation using disentangled style and content representation.  arXiv preprint arXiv:2209.15264, 2022.
  * [16] Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi.  Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.  In International Conference on Machine Learning, pages 12888–12900. PMLR, 2022.
  * [17] Luping Liu, Yi Ren, Zhijie Lin, and Zhou Zhao.  Pseudo numerical methods for diffusion models on manifolds.  arXiv preprint arXiv:2202.09778, 2022.
  * [18] Chenlin Meng, Yang Song, Jiaming Song, Jiajun Wu, Jun-Yan Zhu, and Stefano Ermon.  Sdedit: Image synthesis and editing with stochastic differential equations.  arXiv preprint arXiv:2108.01073, 2021.
  * [19] Alex Nichol, Prafulla Dhariwal, Aditya Ramesh, Pranav Shyam, Pamela Mishkin, Bob McGrew, Ilya Sutskever, and Mark Chen.  Glide: Towards photorealistic image generation and editing with text-guided diffusion models.  arXiv preprint arXiv:2112.10741, 2021.
  * [20] Aude Oliva, Antonio Torralba, and Philippe G. Schyns.  Hybrid images.  ACM Trans. Graph., 25(3):527–532, jul 2006.
  * [21] Taesung Park, Alexei A Efros, Richard Zhang, and Jun-Yan Zhu.  Contrastive learning for unpaired image-to-image translation.  In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part IX 16, pages 319–345. Springer, 2020.
  * [22] Gaurav Parmar, Yijun Li, Jingwan Lu, Richard Zhang, Jun-Yan Zhu, and Krishna Kumar Singh.  Spatially-adaptive multilayer selection for gan inversion and editing.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11399–11409, 2022.
  * [23] Gaurav Parmar, Krishna Kumar Singh, Richard Zhang, Yijun Li, Jingwan Lu, and Jun-Yan Zhu.  Zero-shot image-to-image translation.  arXiv preprint arXiv:2302.03027, 2023.
  * [24] Georg Petschnigg, Richard Szeliski, Maneesh Agrawala, Michael Cohen, Hugues Hoppe, and Kentaro Toyama.  Digital photography with flash and no-flash image pairs.  ACM Trans. Graph., 23(3):664–672, aug 2004.
  * [25] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In International conference on machine learning, pages 8748–8763. PMLR, 2021.
  * [26] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents.  arXiv preprint arXiv:2204.06125, 2022.
  * [27] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10684–10695, 2022.
  * [28] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, S Sara Mahdavi, Rapha Gontijo Lopes, et al.  Photorealistic text-to-image diffusion models with deep language understanding.  arXiv preprint arXiv:2205.11487, 2022.
  * [29] Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising diffusion implicit models.  arXiv preprint arXiv:2010.02502, 2020.
  * [30] Antonio Torralba and Aude Oliva.  Statistics of natural image categories.  Network: Computation in Neural Systems, 14:391 – 412, 2003.
  * [31] Narek Tumanyan, Omer Bar-Tal, Shai Bagon, and Tali Dekel.  Splicing vit features for semantic appearance transfer.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10748–10757, 2022.
  * [32] Narek Tumanyan, Michal Geyer, Shai Bagon, and Tali Dekel.  Plug-and-play diffusion features for text-driven image-to-image translation.  arXiv preprint arXiv:2211.12572, 2022.
  * [33] Narek Tumanyan, Michal Geyer, Shai Bagon, and Tali Dekel.  Plug-and-play diffusion features for text-driven image-to-image translation.  arXiv preprint arXiv:2211.12572, 2022.
  * [34] Tianyi Wei, Dongdong Chen, Wenbo Zhou, Jing Liao, Weiming Zhang, Lu Yuan, Gang Hua, and Nenghai Yu.  A simple baseline for stylegan inversion.  arXiv preprint arXiv:2104.07661, 9:10–12, 2021.
  * [35] Lvmin Zhang and Maneesh Agrawala.  Adding conditional control to text-to-image diffusion models.  arXiv preprint arXiv:2302.05543, 2023.
  * [36] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In Computer Vision (ICCV), 2017 IEEE International Conference on, 2017.


# Survey on Self-supervised Representation Learning Using Image
Transformations

Muhammad Ali∗ Sayed Hashim
Mohamed Bin Zayed University of Artificial Intelligence, UAE
{muhammad.ali<EMAIL_ADDRESS>

First authors

###### Abstract

Deep neural networks need huge amount of training data, while in real world
there is a scarcity of data available for training purposes. To resolve these
issues, self-supervised learning (SSL) methods are used. SSL using geometric
transformations (GT) is a simple yet powerful technique used in unsupervised
representation learning. Although multiple survey papers have reviewed SSL
techniques, there is none that only focuses on those that use geometric
transformations. Furthermore, such methods have not been covered in depth in
papers where they are reviewed. Our motivation to present this work is that
geometric transformations have shown to be powerful supervisory signals in
unsupervised representation learning. Moreover, many such works have found
tremendous success, but have not gained much attention. We present a concise
survey of SSL approaches that use geometric transformations. We shortlist six
representative models that use image transformations including those based on
predicting and autoencoding transformations. We review their architecture as
well as learning methodologies. We also compare the performance of these
models in the object recognition task on CIFAR-10 [8] and ImageNet [1]
datasets. Our analysis indicates the AETv2 [10] performs the best in most
settings. Rotation with feature decoupling [4] also performed well in some
settings. We then derive insights from the observed results. Finally, we
conclude with a summary of the results and insights as well as highlighting
open problems to be addressed and indicating various future directions.

Keywords: deep learning, self-supervised learning, geometric transformations,
autoencoding, rotation, representation learning

##  1 Introduction

###  1.1 Background

Deep neural networks, especially convolutional neural networks (CNNs) has led
to big accomplishments in the computer vision field [5]. For real-world
problems, there is a scarcity of data for training purposes, so expensive
efforts concerning time and resources are required to provide these labelled
training data. This problem led to a big increase in the interest of
researchers in using unsupervised feature learning for solving visual
understanding tasks with lack of availability of labelled data [16]. The basic
idea in SSL is to produce some supervisory signals to solve assigned tasks.
This task may include representation of the data or auto labelling of the
data. SSL provides us with the advantage of training networks without
requiring extensive labelling of the images. In order to utilize the strengths
of SSL techniques over the period of time, major area of work has been done in
the domain of developing various pretext tasks.

###  1.2 Previous studies

Multiple survey and review papers on self-supervised techniques have been
published. One such work [7] describes deep learning-based self-supervised
general visual feature learning methods from images or videos.A survey on
augmentation techniques was published in late 2019 but it majorly focused on
application of augmentation techniques including geometric transformation,
color space augmentations, filters and feature space augmentations. Another
paper [11] explained self-supervised learning technique in various fields
including computer vision,graph learning and natural language processing based
on generative, contrastive and mix of generative and contrastive objectives .
Another paper [6] discusses the use of contrastive learning approach with self
supervised methods.Basic idea in this technique is to assemble similar samples
near each other in relevant to other samples with dissimilarities.

###  1.3 Problem statement and motivation

To the best of our ability, we were unable to find a review or survey paper
that solely focuses on self-supervised learning (SSL) techniques that use
geometric transformations (GT). Although many such works have been reviewed in
review papers, these have not been covered in depth. For instance, one of the
review papers [7] talks about the popular rotation prediction SSL technique,
but doesn’t go into the details of it and doesn’t mention works which have
improvised on the method. Also, it doesn’t talk about the much successful work
of autoencoding geometric transformations [16]. This lack of extensive review
of geometric transformations based SSL techniques show a gap in the literature
which we aim to fill.

We believe an extensive review that purely focuses on geometric transformation
based self-supervised techniques is necessary due to 2 reasons. (1) Geometric
transformations have proved to be simple yet powerful supervisory signals in
unsupervised representation learning. (2) Many successful works have used
geometric transformations from different paradigms such as autoencoding and
classification. To enable a detailed and in-depth understanding of SSL with
geometric transformations we present a concise survey encompassing multiple
aspects including algorithmic details as well as futuristic unresolved
problems.

###  1.4 Proposed approach and contributions

This work contains thorough review and comparison of 6 SSL models that use GT.
Multiple avenues including preprint servers, conference proceedings and
journals were searched for shortlisting relevant papers. Our contributions can
be summarized in 4 points. (1) Provide the reader with an in-depth review of
geometric transformation based SSL techniques. (2) Highlight the importance
and success of using such methods. (3) Discuss the shortcomings in such
techniques and the relevant problems. (4) Explain trend setting research as
well as future direction.

We organize the rest of the paper as follows. In section 3 we briefly discuss
overview of existing methods in detail, where we describe methods that are
based on image rotation prediction as well as using auto encoding
transformations. In section 4 we present results along with qualitative and
quantitative comparison of the performance of the techniques on CIFAR-10 [8]
and ImageNet [1] datasets. In section 5 we derive insights and explain the
results of comparing the different approaches. Section 6 contains conclusion
and future directions.

##  2 Overview of existing methods

###  2.1 Methods based on predicting geometric transformations

In order to extract useful features from images in unsupervised fashion,
RotNet [5] is trained to predict the rotation by multiples of 90 degrees
applied to the input images. Features learned through this method are capable
of generalizing well in various tasks. But the features learned are biased
with regards to rotation transformation and does not help in various tasks
which are in favour of invariance in rotation. Also, rotation is not
determinable for all images in practice and therefore this method does not
perform well with orientation agnostic images. To address these shortcomings,
an SSL technique [4] that decouples the learned features using the task of
predicting rotation along with the task of task discriminating the instances
was presented. The learned representations comprises of 2 parts in which one
is discriminative to rotation and other is unrelated to rotation as shown in
Figure 1. In another work called ExemplarCNN [3], authors trained the CNN to
differentiate among a group of surrogate classes. To create such classes,
various transformations are applied picture patch sampled randomly. This
algorithm strikingly performed well.

Figure 1: Depiction of the rotation feature decoupling method. The ouput from
neural network is a decoupled meaningful feature representation comprising
sections that are related and unrelated to rotation. The rotation related part
is trained by predicting rotations applied to image. A PU learning problem is
modelled here with using the noisy rotation labels, that is trained to learn
instance weights in order to decrease the impact of pictures that are rotation
ambiguous. The second part is trained using loss that penalises distance in
order to impose rotation irrelevance along with a task of discriminating
instances by the use of classification without parameters

[width=13cm]images/decoupling.png

###  2.2 Methods based on autoencoding geometric transformations

For a randomly sampled transformation, the self-supervised learning technique
of Auto-Encoding Transformation (AET) [16] attempts to quantify it just using
the learned features precisely as the output. The main theory here is that the
transformation can be quantified if the learned features are able store the
important characteristics of original images and images after transformation.
A variant of this approach is Autoencoding Variational Transformations (AVT)
[14]. Provided images after transformation, AVT trains the autoencoder by
increasing the shared features between learned representations and
transformations.

In order to quantify the divergence of predicted transformations from their
labelled equivalents, deterministic and probabilistic AETs depend upon
Euclidean distance. But, this is a contentious assumption as a set of
transformations usually stay on a curved manifold instead of residing in a
flat Euclidean space. To solve this issue, the authors developed AETv2 [10],
which uses the geodesic distance to distinguish the way in which an image is
transformed towards the manifold of a set of transformations, and use its
length to quantify the difference between transformations.

Figure 2: Depiction of the way in which AETv2 [10] is trained from start to
finish. In order to make the output matrix $\mathbf{T}^{-1}\hat{\mathbf{T}}$
from the decoder of transformation possess a unit determinant, it is
normalized, and it should be noted that the projection of
$\mathbf{T}^{-1}\hat{\mathbf{T}}$ onto $\mathbf{SO}(3)$ is followed in order
to calculate the geodesic distance and also the loss of projection in order
for the model to be trained

[height=7cm]images/aetv2.png

##  3 Results

###  3.1 CIFAR-10

Comparison of the performance of the models in the downstream task of object
recognition on CIFAR-10 [8] measured by error rates produced interesting
results, as shown in Table 1. AETv2 [10] model produced best results with an
error rate of 7.44. It can also be seen that RotNet [5] was a breakthrough
work, that made much progress compared to previous traditional methods,
bringing down the error rate to 8.84. While rotation provides a simple, yet
powerful supervisory signal, autoencoding multiple transformations has proved
to be a slightly better method in feature representation learning.

Table 1:  Comparative study between various selected methods using self supervised technique on CIFAR-10 [8] data set.Two supervised methods including NIN and random Init along with conv contains same architecture with only difference that one is supervised where as the other one is trained in such a way that first two blocks are initialized and kept frozen in training process. Model | Error rate
---|---
NIN-Supervised (Lower Bound) | 7.20
Random Init. + conv (Upper Bound) | 27.50
Roto-Scat + SVM [13] | 17.7
DCGAN [15] | 17.2
ExamplarCNN [3] | 15.7
Scattering [12] | 15.3
RotNet + conv [5] | 8.84
AETv1 + conv [16] | 7.82
AVT + conv [14] | 7.75
AETv2 + conv [10] | 7.44

###  3.2 ImageNet

Some interesting insights could be derived from the results of the methods’
performance in the image classification task on ImageNet [1] compared using
top-1 accuracy, as presented in Table 2. While AETv2 performed better when the
network was trained with up to 3 convolutional blocks, RotNet performed better
with more than 3 convolutional blocks. This could be due to the simplicity of
the RotNet model. Generally, using more than 3 convolutional blocks produced a
gradual decrease in object recognition accuracy, which we believe is because
the feature learnt in these layers start to become more specific on the
pretext task. Furthermore, we see that increased depth of models led to better
performance in object recognition with regards to the feature maps produced by
earlier layers. We believe this is because a deeper model enables the features
of layers early on to be less peculiar to the pretext task.

Table 2: Comparison of Top-1 accuracy using linear layers on ImageNet [1] data set. For comparison of self supervised models Alex Net is used. This classifier is trained with various depth of convolution layers containing features maps with 9000 elements finally.Upper bound and lower bounds of self supervised model’s performances for supervised and random models are also shown for comparison. Model | Conv1 | Conv2 | Conv3 | Conv4 | Conv5
---|---|---|---|---|---
ImageNet Labels (Upper Bound) [5] | 19.3 | 36.3 | 44.2 | 48.3 | 50.5
Random (Lower Bound) [5] | 11.6 | 17.1 | 16.9 | 16.3 | 14.1
Random rescaled [9] (Lower Bound) | 17.5 | 23.0 | 24.5 | 23.2 | 20.6
BiGAN [2] | 17.7 | 24.5 | 31.0 | 29.9 | 28.0
RotNet [5] | 18.8 | 31.7 | 38.7 | 38.2 | 36.5
Rotation feature decoupling [4] | 19.3 | 33.3 | 40.8 | 41.8 | 44.3
AETv1 [16] | 19.2 | 32.8 | 40.6 | 39.7 | 37.7
AVT [14] | 19.5 | 33.6 | 41.3 | 40.3 | 39.1
AETv2 [10] | 19.6 | 34.1 | 41.9 | 40.4 | 37.9

##  4 Discussion

A thorough comparison of the methods have shown that AETv2 [10] performs best
in terms of learning relevant features from images, and being able to
contribute to lower error rates in object recognition on ImageNet [1] and
CIFAR-10 [8] datasets. As shown in Figure 5, it can be seen that the path of
loss of prediction of transformation follows a similar path of that of error
of classification and top-1 accuracy on CIFAR-10 [8] and ImageNet [1]. This
indicates that predicting transformations better implies better result of
classification making use of learned representations. This validates the
choice of AET and its variants for the supervision of learning feature
representations.

One downside of using transformations is that they might leave behind any low-
level visual artifacts that are easily detectable which will lead the CNN to
learn easy features without practical value in the tasks of vision perception,
e.g., to implement scale and aspect ratio image transformations, image
resizing routines that leave easily detectable image artifacts would have to
be used. The models’ performance on the CIFAR-10 [8] and ImageNet [1] datasets
can still be improved. More combinations of transformations could be
experimented with to improve performance. Moreover, attention based models
could be coupled with the transformations to facilitate better feature
learning.

[b]0.48 [width=]images/aetcifar.png [b]0.48 [width=]images/aetimagenet.png

Figure 3: CIFAR-10 [1] Figure 4: ImageNet [1] Figure 5: The two plots show the
change in error rate and top-1 accuracy with the change in AET [16] loss as
training progressed on the CIFAR-10 [1] and ImageNet [1] datasets.

##  5 Conclusion

Although multiple papers have reviewed contrastive and generative SSL
techniques there is none that solely focuses on SSL techniques that use GT.
Also, such methods have not been covered in depth in papers where they have
been reviewed. This is a gap in the literature which we aim to fill through
this work. Our motivation to present this work is that GT have shown to be
powerful supervisory signals in unsupervised representation learning.
Moreover, many works which used GT in SSL techniques have found tremendous
success, but have not gained much attention. The work has extensively reviewed
6 approaches on self-supervised representation learning using image
transformations that are based on predicting rotation as well as auto encoding
transformations. We compared the models based on their performance in the
downstream task of object recognition on CIFAR-10 [8] and ImageNet [1]
datasets, measured by their error rates and top-1 accuracy. The review
provided insights as to which models worked better and why. It has also showed
that image transformations are powerful supervisory signals for feature
representation learning. We also believe this paper will help researchers in
inventing new GT based SSL techniques.

## References

  * [1] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [2] J. Donahue, P. Krähenbühl, and T. Darrell.  Adversarial feature learning.  CoRR, abs/1605.09782, 2016.
  * [3] A. Dosovitskiy, J. T. Springenberg, M. Riedmiller, and T. Brox.  Discriminative unsupervised feature learning with convolutional neural networks.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
  * [4] Z. Feng, C. Xu, and D. Tao.  Self-supervised representation learning by rotation feature decoupling.  2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [5] S. Gidaris, P. Singh, and N. Komodakis.  Unsupervised representation learning by predicting image rotations, 2021\.
  * [6] A. Jaiswal, A. R. Babu, M. Z. Zadeh, D. Banerjee, and F. Makedon.  A survey on contrastive self-supervised learning, 2021.
  * [7] L. Jing and Y. Tian.  Self-supervised visual feature learning with deep neural networks: A survey.  CoRR, abs/1902.06162, 2019.
  * [8] A. Krizhevsky.  Learning multiple layers of features from tiny images.  University of Toronto, 05 2012.
  * [9] P. Krähenbühl, C. Doersch, J. Donahue, and T. Darrell.  Data-dependent initializations of convolutional neural networks, 2016\.
  * [10] F. Lin, H. Xu, H. Li, H. Xiong, and G.-J. Qi.  Aetv2: Autoencoding transformations for self-supervised representation learning by minimizing geodesic distances in lie groups, 2019.
  * [11] X. Liu, F. Zhang, Z. Hou, Z. Wang, L. Mian, J. Zhang, and J. Tang.  Self-supervised learning: Generative or contrastive, 2021.
  * [12] E. Oyallon, E. Belilovsky, and S. Zagoruyko.  Scaling the scattering transform: Deep hybrid networks.  In 2017 IEEE International Conference on Computer Vision (ICCV), pages 5619–5628, 2017.
  * [13] E. Oyallon and S. Mallat.  Deep roto-translation scattering for object classification.  CoRR, abs/1412.8659, 2014.
  * [14] G.-J. Qi, L. Zhang, C. W. Chen, and Q. Tian.  Avt: Unsupervised learning of transformation equivariant representations by autoencoding variational transformations, 2019.
  * [15] A. Radford, L. Metz, and S. Chintala.  Unsupervised representation learning with deep convolutional generative adversarial networks, 2016.
  * [16] L. Zhang, G.-J. Qi, L. Wang, and J. Luo.  Aet vs. aed: Unsupervised representation learning by auto-encoding transformations rather than data, 2021.