[datatype=bibtex] [fieldset=doi,null] [fieldset=url,null] [fieldset=isbn,null]
[fieldset=issn,null] [fieldset=note,null] [fieldset=pagetotal,null]

# Isosingular loci of algebraic varieties

Christopher Chiu  Fakultät für Mathematik
Universität Wien
Oskar-Morgenstern-Platz 1
A-1090 Wien (Österreich<EMAIL_ADDRESS>and  Herwig
Hauser  Fakultät für Mathematik
Universität Wien
Oskar-Morgenstern-Platz 1
A-1090 Wien (Österreich<EMAIL_ADDRESS>
###### Abstract.

We define the notion of isosingular loci of algebraic varieties, following the
analytic case first studied by Ephraim. In particular, we give a partial
extension of his main result in arbitrary characteristic and a full extension
assuming characteristic $0$. One of the main obstructions in the positive
characteristic case is the non-separability of the orbit map associated to the
contact group, as first observed by Greuel and Pham for isolated
singularities.

###### Key words and phrases:

Isosingular loci, contact equivalence.

###### 2020 Mathematics Subject Classification:

Primary 13A50, 14B05, 14B20.

The research of the first and the second author were supported by project
P-31338 of the Austrian Science Fund (FWF)

Let $X$ be a complex analytic space and $p\in X$. In [2] the _isosingular
locus_ of $X$ at $p$ was defined to be the subset of $X$ with a prescribed
singularity type, that is,

$\operatorname{Iso}(X,p)=\\{q\in X\mid X_{q}\simeq X_{p}\\},$

where $X_{p}$ and $X_{q}$ denote the analytic germs of $X$ at $p$ and $q$. The
main result of [2] asserts the following:

######  Theorem ([2, Theorem 0.2, Observation 2.5]).

For a complex analytic space $X$ and $p\in X$ the set
$\operatorname{Iso}(X,p)$ is locally closed and smooth as a (reduced) analytic
subspace of $X$. Furthermore, there exists a germ of an analytic space $Y_{y}$
such that $X_{p}\simeq Y_{y}\times\operatorname{Iso}(X,p)_{p}$, with $Y_{y}$
having the additional property that there does not exist an isomorphism of
germs $Y_{y}\simeq Y^{\prime}_{y^{\prime}}\times{\mathbb{C}}_{0}$.

Generalizations of this result to the relative case of morphisms between
analytic spaces were obtained in [8, 9]. We call an analytic germ $(X,p)$
_harmonic_ if
$\operatorname{Iso}(X,p)=\operatorname{Iso}(\operatorname{Sing}X,p)$. In [4]
the classical Mather–Yau theorem (see [10]) was extended from the isolated
singularity case to general harmonic singularities. Results in a very similar
spirit appeared recently in the preprint [3].

In this paper, our main goal is to study isosingular loci of an algebraic
variety $X$ over an arbitrary algebraically closed field $k$. As we do not
have the analytic topology at our disposal, we will replace it by considering
the corresponding _formal neighborhoods_ instead. That is, for any $x\in X(k)$
the _isosingular locus_ of $X$ at $x$ is defined to be the set

$\operatorname{Iso}(X,x):=\\{x^{\prime}\in
X\mid\widehat{X}_{x^{\prime}}\simeq\widehat{X}_{x}\\},$

where $\widehat{X}_{x}$ denotes the formal completion of $X$ along the
singleton $\\{x\\}$. Note that any isomorphism of such formal completions
induces an isomorphism of residue fields and thus
$\operatorname{Iso}(X,x)\subset X(k)$. Our first main result is an extension
of the first part of the above theorem in [2].

######  Theorem A.

Let $X$ be a variety over an algebraically closed field $k$.

  1. (1)

For each $x\in X(k)$ the subset $\operatorname{Iso}(X,x)$ is locally closed in
$X(k)$ (endowed with the Zariski topology).

  2. (2)

Denote by $X^{(x)}$ the unique reduced subscheme of $X$ whose $k$-points agree
with $\operatorname{Iso}(X,x)$. Then $X^{(x)}$ is smooth.

The proof follows the analytic case and uses the action of the contact group
$\mathcal{K}$ as well as a version of Artin’s celebrated approximation result
in [1]. As for remaining part of [2, Theorem 0.2], assuming characteristic $0$
we obtain the following result:

######  Theorem B.

Let $X$ be a variety over an algebraically closed field of characteristic $0$.
For each $x\in X(k)$ there exists a scheme $Y$ of finite type over $k$, a
point $y\in Y(k)$ and an isomorphism

$\widehat{X}_{x}\simeq\widehat{(X^{(x)})}_{x}\times\widehat{Y}_{y},$

such that $\widehat{Y}_{y}$ has _no smooth factors_ , that is, there does not
exist an isomorphism
$\widehat{Y}_{y}\simeq\widehat{Z}_{z}\times\widehat{({\mathbb{A}}^{1})}_{0}$.

The assertion of Theorem B fails in positive characteristics, as can be seen
in the example of the Whitney umbrella $f=x^{p}+y^{p}z$ in characteristic
$p>0$, c.f. Example 2.6. Let us mention that the proof of Theorem B crucially
relies on the characteristic $0$ assumption in two separate places. First, it
makes use of the Nagata–Zariski-Lipman criterion (see Theorem 2.4), which
expresses the existence of smooth factors in terms of the existence of
_regular_ derivations. This part of the argument could potentially be extended
to positive characteristics by means of _Hasse–Schmidt derivations_. The
second important assumption which holds only in characteristic $0$ is that the
orbit map associated to the (truncated) contact group $\mathcal{K}_{\beta}$ is
separable for all $\beta$ large enough. In fact, the fact that this fails in
positive characteristic was first exhibited by Greuel and Pham in [6, 5] for
certain isolated singularities. As we will see in Example 2.7, the results of
Section 2 give new examples of this phenomenon, including the singularity
$f=x^{p}+y^{p}z$ mentioned above. Moreover, it prompts the following question:

######  Question C.

Let $k$ be an algebraically closed field and $0\in X\subset{\mathbb{A}}^{N}$ a
hypersurface singularity given by $f\in k[x_{1},\ldots,x_{N}]$. Assume that
there exists $\beta_{0}>0$ such that the orbit map $\mathcal{K}_{\beta}\to
o(f_{\beta})$ is separable for $\beta\geq\beta_{0}$ (see Section 2). Does the
conclusion of Theorem B hold in this case?

Note that we restrict the question to the hypersurface case as even then we do
not know of any counterexample.

### Conventions

Throughout this paper we always assume $X$ to be an algebraic variety, that
is, a separated scheme of finite type over an algebraically closed field $k$.
For any point $x\in X(k)$ we denote by $\widehat{X}_{x}$ the formal
neighborhood of $X$ at $x$. That is, $\widehat{X}_{x}$ is given by the formal
completion of $X$ along the closed subscheme $\\{x\\}$ and is thus isomorphic
to $\operatorname{Spf}(\widehat{\mathcal{O}_{X,x}})$.

##  1\. Contact equivalence and proof of Theorem A

Let $k$ be an algebraically closed field. We start by repeating the main
definition: for any point $x\in X(k)$ the _isosingular locus_ of $X$ at $x$ is
defined to be the set

$\operatorname{Iso}(X,x):=\\{x^{\prime}\in
X\mid\widehat{X}_{x}\simeq\widehat{X}_{x^{\prime}}\\}.$

If $X$ is smooth at $x$, then $\operatorname{Iso}(X,x)$ is clearly an open
subset of $X(k)$.

######  Remark 1.1.

Let us briefly discuss the situation when $k$ is not algebraically closed.
Assume $\operatorname{char}k=0$ and consider the Whitney umbrella $X$ defined
by $x^{2}+y^{2}z$ in ${\mathbb{A}}^{3}_{k}$. Clearly $\operatorname{Sing}X$ is
just given by the $z$-axis. Taking any point of the form $x=(0,0,t)$ for
$t\neq 0$, we see that the formal completion $\widehat{X}_{x}$ is isomorphic
to the union of two hyperplanes if and only if $\sqrt{t}\in k$. Thus the
isosingular loci of $X$ might not even be constructible as subsets of $X(k)$.

Since both Theorems A and B are local statements on $X$, we may assume for the
rest of this paper that $X\subset{\mathbb{A}}^{N}$ is affine, given by
polynomials $f_{1},\ldots,f_{n}\in k[x_{1},\ldots,x_{N}]$. To simplify
notation, let us write $\underline{x}=(x_{1},\ldots,x_{N})$ and
$f=(f_{1},\ldots,f_{n})$.

Let us start by recalling a general version of the formal inverse function
theorem:

######  Lemma 1.2.

Let $R$ be any ring and $S=R[[\underline{x}]]$ or
$S=R[\underline{x}]/(\underline{x})^{\beta}$ for some $\beta>0$. Let
$\varphi:S\to S$ be a map of $R$-algebras given by
$\varphi_{i}:=\varphi(x_{i})$ and satisfying $\varphi_{i}(0)=0$. Then
$\varphi$ is an isomorphism if and only if
$\det(\frac{\partial\varphi_{i}}{\partial x_{j}}(0))_{i,j\leq N}\in R^{*}$.

###### Proof.

Follows from considering the maps on the associated graded rings. ∎

To describe the action of the contact group we fix some notation. All schemes
are considered relative to the base field $k$; in particular, $R$ will always
denote a $k$-algebra. By $\mathcal{O}_{N}$ we denote the (infinite-
dimensional) scheme whose $R$-points are formal series in
$R[[\underline{x}]]$. Similarly, for $\beta\geq 0$ we define the (finite-
dimensional) scheme $\mathcal{O}_{N,\beta}$ via
$\mathcal{O}_{N,\beta}(R):=R[\underline{x}]/(\underline{x})^{\beta+1}$.
Clearly we have $\mathcal{O}_{N}=\varprojlim_{\beta}\mathcal{O}_{N,\beta}$ via
the natural maps.

For any ring $R$ we consider the group
$\operatorname{Aut}_{R}(R[[\underline{x}]])$ of local $R$-automorphisms. By
Lemma 1.2 we have

(1a) $\operatorname{Aut}_{R}(R[[\underline{x}]])=\\{\varphi\in
R[[\underline{x}]]^{N}\mid\varphi(0)=0,\>\det(\frac{\partial\varphi_{i}}{\partial
x_{j}}(0))_{i,j\leq N}\in R^{*}\\}.$

Thus the assignment $R\mapsto\operatorname{Aut}_{R}(R[[\underline{x}]])$
defines a group scheme $\operatorname{Aut}\mathcal{O}_{N}$. Similarly, for
each $\beta\geq 0$ we obtain an algebraic group
$\operatorname{Aut}\mathcal{O}_{N,\beta}$ whose $R$-points are elements of
$\operatorname{Aut}_{R}(R[\underline{x}]/(\underline{x})^{\beta+1})$.

For any $n>0$ the group scheme $\operatorname{Aut}\mathcal{O}_{N}$ acts on
$\mathcal{O}_{N}^{n}$ as follows: given $f\in R[[\underline{x}]]^{n}$ and
$\varphi\in\operatorname{Aut}_{R}(R[[\underline{x}]])$, we define
$\varphi\cdot f:=f\circ\varphi=f(\varphi_{1},\ldots,\varphi_{N})$. For
$\beta\geq 0$ an action of $\operatorname{Aut}\mathcal{O}_{N,\beta}$ on
$\mathcal{O}_{N,\beta}^{n}$ is defined in the same way. These actions are
compatible via the diagram

(1b)
$\textstyle{\operatorname{Aut}\mathcal{O}_{N}\times\mathcal{O}_{N}^{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathcal{O}_{N}^{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\operatorname{Aut}\mathcal{O}_{N,\beta}\times\mathcal{O}_{N,\beta}^{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathcal{O}_{N,\beta}^{n}.}$

######  Definition 1.3.

For $N,n>0$ the _contact group_ $\mathcal{K}=\mathcal{K}_{N,n}$ is defined as
the group scheme
$\operatorname{GL}_{n}(\mathcal{O}_{N})\rtimes\operatorname{Aut}\mathcal{O}_{N}$.
That is, for each $R$ we have

$\mathcal{K}(R)=\operatorname{GL}_{n}(R[[\underline{x}]])\rtimes\operatorname{Aut}_{R}(R[[\underline{x}]]),$

where the semidirect product is taken with respect to the group homomorphism
$\operatorname{Aut}_{R}(R[[\underline{x}]])\to\operatorname{Aut}\operatorname{GL}_{n}(R[[\underline{x}]])$
given by

$\varphi\mapsto(M=(m_{i,j})_{i,j}\mapsto
M\circ\varphi=(m_{i,j}(\varphi_{1},\ldots,\varphi_{N}))_{i,j}).$

Similarly, for $\beta\geq 0$ the _truncated contact group_
$\mathcal{K}_{\beta}$ is defined as the algebraic group
$\operatorname{GL}_{n}(\mathcal{O}_{N,\beta})\rtimes\operatorname{Aut}\mathcal{O}_{N,\beta}$
and we have $\mathcal{K}=\varprojlim_{\beta}\mathcal{K}_{\beta}$.

The action of $\operatorname{Aut}\mathcal{O}_{N}$ on $\mathcal{O}^{n}_{N}$
together with the natural action of $\operatorname{GL}_{n}(\mathcal{O}_{N})$
defines an action
$\rho:\mathcal{K}\times\mathcal{O}_{N}^{n}\to\mathcal{O}_{N}^{n}$ which is
given by

$\rho:(M,\varphi;f)\mapsto M\cdot(f\circ\varphi).$

Similarly we obtain an action $\rho_{\beta}$ of $\mathcal{K}_{\beta}$ on
$\mathcal{O}_{N,\beta}^{n}$ and Eq. 1b implies that $\rho$ and $\rho_{\beta}$
are compatible via the diagram

(1c)
$\textstyle{\mathcal{K}\times\mathcal{O}^{n}_{N}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\rho}$$\textstyle{\mathcal{O}^{n}_{N}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathcal{K}_{\beta}\times\mathcal{O}_{N,\beta}^{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\rho_{\beta}}$$\textstyle{\mathcal{O}_{N,\beta}^{n}.}$

As a first remark we note that $\mathcal{K}_{\beta}$ is smooth independent of
the characteristic of the base field $k$.

######  Lemma 1.4.

For each $\beta\geq 0$ the truncated contact group $\mathcal{K}_{\beta}$ is
smooth over $k$. Moreover, for any $f\in\mathcal{O}_{N,\beta}(k)$ the map
$(\rho_{\beta})_{f}:\mathcal{K}_{\beta}\to\mathcal{O}_{N,\beta}^{n}$ given by
$(M,\varphi)\mapsto M\cdot(f\circ\varphi)$ has locally closed image $o(f)$,
which is smooth when considered as a reduced subscheme of
$\mathcal{O}_{N,\beta}^{n}$ (we call $o(f)$ the _orbit_ of $f$).

###### Proof.

For the first assertion note that the underlying space of
$\mathcal{K}_{\beta}$ is
$\operatorname{GL}_{n}(\mathcal{O}_{N,\beta})\times\operatorname{Aut}\mathcal{O}_{N,\beta}$
and that we have open immersions
$\operatorname{GL}_{n}(\mathcal{O}_{N,\beta})\hookrightarrow{\mathbb{A}}^{n^{2}M}$
and $\operatorname{Aut}\mathcal{O}_{N,\beta}\hookrightarrow{\mathbb{A}}^{NM}$,
where $M:=\binom{N+\beta}{N}$. The second assertion then follows from [12,
Proposition 7.4]. ∎

The main idea behind the use of the contact group in the proof of Theorem A is
that two points of $X$ have isomorphic formal neighborhoods if and only if the
respective Taylor expansions of $f$ at those points lie in the same orbit of
$\mathcal{K}$. We want to review this classical argument in our setting.
First, let $\gamma:X\to\mathcal{O}_{N}^{n}$ be the morphism defined as
follows: for each $k$-algebra $R$ the map $\gamma(R)$ is given by

$a\in X(R)\subset R^{N}\mapsto f(\underline{x}+a)\in R[[\underline{x}]].$

In an analogous way we obtain morphisms
$\gamma_{\beta}:X\to\mathcal{O}_{N,\beta}^{n}$ for $\beta\geq 0$.

######  Lemma 1.5.

Let $x_{1},x_{2}\in X(k)$. Then $\widehat{X}_{x_{1}}\simeq\widehat{X}_{x_{2}}$
if and only if $\gamma(x_{2})\in o(\gamma(x_{1}))$.

###### Proof.

We may assume that $x_{1}=0$ and $x_{2}=a\in k^{N}$. Then

$\widehat{\mathcal{O}_{X,x_{2}}}\simeq
k[[\underline{x}]]/(f(\underline{x}+a)).$

The existence of an isomorphism
$\widehat{\mathcal{O}_{X,x_{1}}}\simeq\widehat{\mathcal{O}_{X,x_{2}}}$ is
equivalent to the existence of an isomorphism
$\varphi\in\operatorname{Aut}_{k}(k[[\underline{x}]])$ such that the following
equality of ideals holds:

$(\varphi(f(\underline{x})))=(f(\underline{x}+a)).$

To proceed we make use of a trick of Mather:

######  Lemma 1.6.

Let $A,B\in k^{n\times n}$. Then there exists $C\in k^{n\times n}$ such that
$C(1-AB)+B$ is invertible.

###### Proof.

Let $r=\operatorname{rk}(B)$ and choose a basis $\\{e_{i}\\}_{i}$ for $k^{n}$
such that $Be_{1},\ldots,Be_{r}$ are linearly independent and $Be_{i}=0$ for
$i>r$. Let $e^{\prime}_{r+1},\ldots,e^{\prime}_{n}$ be such that
$Be_{i},e^{\prime}_{j}$ form a basis. Then $C$ is the matrix representing the
linear map given by $e_{i}\mapsto 0$ for $i\leq r$ and $e_{i}\mapsto
e^{\prime}_{i}$ for $i>r$. ∎

Write $R=k[[\underline{x}]]$ and $\mathfrak{m}=(\underline{x})$. The above
equality of ideals implies the existence of $A,B\in R^{n\times n}$ with
$A\cdot f(\varphi(\underline{x}))=f(\underline{x}+a)$ and $B\cdot
f(\underline{x}+a)=f(\varphi(\underline{x}))$. Then, by Lemma 1.6, there
exists $C\in k^{n\times n}$ with $D=C(1-AB)+B\in R^{n\times n}$ invertible
modulo $\mathfrak{m}$, which implies that $D$ is invertible in $R^{n\times
n}$. Clearly, $D\cdot f(\underline{x}+a)=f(\varphi(\underline{x}))$. ∎

Note the contact group $\mathcal{K}$ is not of finite type and neither is the
scheme $\mathcal{O}_{N}^{n}$. In order to be able to apply Lemma 1.4 for the
action of the truncated contact group $\mathcal{K}_{\beta}$ we make use of a
variant of Artin’s celebrated approximation results, which is commonly
referred to as _Universal Strong Artin Approximation_.

######  Theorem 1.7 ([1, Theorem 6.1]).

Let $k$ be a field. For each tuple $(n,m,d,\alpha)$ of non-negative integers
there exists a $\beta\geq 0$ satisfying the following property: let
$\underline{x}=(x_{1},\ldots,x_{n})$ and $\underline{y}=(y_{1},\ldots,y_{m})$
be two sets of variables and $f=(f_{1},\ldots,f_{r})\in
k[\underline{x},\underline{y}]^{r}$ with $\deg(f_{i})\leq d$. Assume there
exist polynomials $\bar{y}=(\bar{y}_{1},\ldots,\bar{y}_{m})\in
k[\underline{x}]^{m}$ with

$f(\underline{x},\bar{y}(\underline{x}))\equiv 0\mod(\underline{x})^{\beta}.$

Then there exist algebraic power series $y=(y_{1},\ldots,y_{m})$ with
$f(\underline{x},y(\underline{x}))=0$ and

$\bar{y}\equiv y(\underline{x})\mod(\underline{x})^{\alpha}.$

######  Corollary 1.8.

Let $x_{1},x_{2}\in X(k)$. Then there exists a $\beta>0$ such that we have
$\gamma(x_{2})\in o(\gamma(x_{1}))$ if and only if $\gamma_{\beta}(x_{2})\in
o(\gamma_{\beta}(x_{1}))$.

###### Proof.

Assume $x_{1}=0$ and let $x_{2}$ be given by $a=(a_{1},\ldots,a_{n})\in
k^{n}$. Consider the system of equations in variables $M=(M_{ij})$ and
$\underline{y}=(y_{1},\ldots,y_{N})$ over $k[\underline{x}]$ given by

$M\cdot f(\underline{y})-f(\underline{x}+a)=0.$

The condition $\gamma_{\beta}(x_{2})\in o(\gamma_{\beta}(x_{1}))$ is
equivalent to the existence of
$(\bar{M}(\underline{x}),\bar{y}(\underline{x}))$ such that
$\det(\bar{M}(0))$, $\det(\frac{\partial\bar{y}_{i}}{\partial x_{j}}(0))\in
k^{*}$. Take $\alpha\gg 0$. By Theorem 1.7 there a $\beta>0$ such that, for
each solution $(\bar{M}(\underline{x}),\bar{y}(\underline{x}))$ of this system
module $(\underline{x})^{\beta}$, there exists a solution
$(M(\underline{x}),y(\underline{x}))$ with
$\bar{M}(\underline{x})-M(\underline{x}),\bar{y}(\underline{x})-y(\underline{x})\in(\underline{x})^{\alpha}$.
Thus, in particular $\det(M(0))$, $\det(\frac{\partial y_{i}}{\partial
x_{j}}(0))\in k^{*}$, which in turn implies that $\gamma(x_{2})\in
o(\gamma(x_{1}))$. The other direction follows from the diagram Eq. 1c. ∎

Thus we obtain the first assertation of Theorem A:

######  Proposition 1.9.

Let $X$ be a variety over an algebraically closed field $k$ and let $x\in
X(k)$. Then $\operatorname{Iso}(X,x)$ is locally closed as a subset of $X(k)$.

###### Proof.

Follows from Lemmas 1.4, 1.5 and 1.8. ∎

######  Remark 1.10.

Let us mention that the isosingularity loci $\operatorname{Iso}(X,x)$ do not
give a stratification of $X$ in general, since $X$ might have infinitely many
points with distinct singularities. Consider the classical example by Whitney
[14, Example 13.2], which is $X\subset{\mathbb{A}}^{3}$ defined by
$f=xy(x+y)(x+zy)$. For each point $x=(0,0,a)\in\operatorname{Sing}X$ the
associated tangent cone is a union of four planes, which have a well-defined
cross-ratio depending on $a$. As any formal isomorphism induces a linear
isomorphism of tangent cones we see that $\operatorname{Iso}(X,x)=\\{x\\}$.

Proposition 1.9 leads us the make the following definition:

######  Definition 1.11.

Let $X$ be a scheme of finite type over an algebraically closed field $k$. For
each $x\in X(k)$ we define $X^{(x)}$ to be the unique reduced subscheme of $X$
whose $k$-points equal $\operatorname{Iso}(X,x)$ and call it the
_isosingularity scheme_ associated to $x$.

To finish the proof of Theorem A we aim to show that $X^{(x)}$ is smooth. As
we will see in the next section, we cannot conclude directly using that the
orbit $o(\gamma(x))$ is smooth. Our strategy is therefore to use generic
smoothness to establish the existence of
$x^{\prime}\in\operatorname{Iso}(X,x)$ such that $X^{(x)}$ is smooth at
$x^{\prime}$ and then extend the isomorphism
$\widehat{X}_{x}\simeq\widehat{X}_{x^{\prime}}$ étale-locally. To that end,
recall that an _étale neighborhood_ $(U,y)$ of $x\in X(k)$ is an étale
morphism $u:U\to X$ and $y\in U(k)$ with $u(y)=x$. Artin’s approximation
results then imply the following corollary:

######  Lemma 1.12 ([1, Corollary 2.5]).

Let $x\in X(k)$ and $x^{\prime}\in\operatorname{Iso}(X,x)$, that is,
$\widehat{X}_{x}\simeq\widehat{X}_{x^{\prime}}$. Then there exists a common
étale neighborhood $(U,y)$ of $x$ and $x^{\prime}$, that is, a diagram of
étale morphisms

$\textstyle{U\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{u}$$\scriptstyle{u^{\prime}}$$\textstyle{X}$$\textstyle{X}$

and $y\in U(k)$ with $u(y)=x$ and $u^{\prime}(y)=x^{\prime}$.

######  Lemma 1.13.

Let $f:U\to X$ be étale and $y\in U(k)$ with $x=f(y)\in X(k)$. Then
$f^{-1}(\operatorname{Iso}(X,x))=\operatorname{Iso}(U,y)$ and the restriction
$U^{(y)}\to X^{(x)}$ is étale.

###### Proof.

The first assertion follows from the fact that, for $y^{\prime}\in U(k)$ and
$x^{\prime}=f(y^{\prime})$ the morphism $f$ induces an isomorphism on
completions $\widehat{U}_{y^{\prime}}\simeq\widehat{X}_{x^{\prime}}$. To see
the second claim, consider the fiber diagram

$\textstyle{U\times_{X}X^{(x)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X^{(x)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\textstyle{X.}$

As a base change of $f$ the morphism $U\times_{X}X^{(x)}\to X^{(x)}$ is étale
again and in particular, since $X^{(x)}$ is reduced, so is
$U\times_{X}X^{(x)}$. Thus $U^{(y)}\simeq U\times_{X}X^{(x)}$ and we are done.
∎

######  Proposition 1.14.

Let $X$ be a variety over an algebraically closed field $k$ and let $x\in
X(k)$. Then $X^{(x)}$ is smooth over $k$.

###### Proof.

By definition $X^{(x)}$ is geometrically reduced and thus the subset of
$k$-smooth points of $X^{(x)}$ is dense open (see [13, Tag 056V] ). Thus there
exists $x^{\prime}\in X^{(x)}(k)=\operatorname{Iso}(X,x)$ smooth over $k$. By
Lemma 1.12 there exists a common étale neighborhood $(U,y)$ of $x$ and
$x^{\prime}$. Thus, by Lemma 1.13, we have
$\widehat{(X^{(x)})}_{x}\simeq\widehat{(U^{(y)})}_{y}\simeq\widehat{(X^{(x^{\prime})})}_{x^{\prime}}$.
Clearly $X^{(x^{\prime})}\simeq X^{(x)}$, and thus $\widehat{(X^{(x)})}_{x}$
is formally smooth over $k$, which in turn implies that $X^{(x)}$ is smooth at
$x$. ∎

##  2\. The proof of Theorem B and separability of the orbit map

This section is devoted to the proof of Theorem B, which will involve studying
the orbit map $\mathcal{K}\to o(f)$. As both sides are non-Noetherian schemes
of infinite dimension, we first need to introduce the right notion of
smoothness in this setting.

######  Definition 2.1.

Let $k$ be a ring and $(R,\mathfrak{m})$ be a local $k$-algebra. We say that
$R$ is _formally smooth_ over $k$ if for every $k$-algebra $C$ with nilpotent
ideal $J\subset C$ and every diagram

$\textstyle{R\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\bar{\psi}}$$\scriptstyle{\psi}$$\textstyle{C/J}$$\textstyle{k\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{C\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

such that $\bar{\psi}(\mathfrak{m}^{n})=0$ in $C/J$ there exists a diagonal
arrow $\psi:R\to C$ making the diagram commute.

Note that this is equivalent to saying that $(R,\mathfrak{m})$ considered as a
topological ring with respect to its $\mathfrak{m}$-adic topology is formally
smooth in the sense of [7, (19.3.1)].

######  Lemma 2.2.

Let $(R,\mathfrak{m})$ and $(S,\mathfrak{n})$ be local $k$-algebras with
$R/\mathfrak{m}=S/\mathfrak{n}=k$.

  1. (1)

Assume $R=\varinjlim_{n}R_{n}$ with
$\\{(R_{n},\mathfrak{m}_{n})\\}_{n\in{\mathbb{N}}}$ a direct system of local
$k$-algebras smooth over $k$. Then $R$ is formally smooth over $k$.

  2. (2)

Assume $\varphi:R\to S$ is a local map and $R$, $S$ are formally smooth over
$k$. If the induced cotangent map
$T^{*}\varphi:\mathfrak{m}/\mathfrak{m}^{2}\to\mathfrak{n}/\mathfrak{n}^{2}$
is injective, then there exists a retraction $\widehat{S}\to\widehat{R}$ of
the completion map $\widehat{\varphi}:\widehat{R}\to\widehat{S}$.

Compare the second assertion with the fact that any submersion between smooth
manifolds allows for a local section.

###### Proof.

Let us start by proving (1). Since $R_{n}$ is smooth over $k$, it is in
particular formally smooth over $k$. By [7, (19.5.4)] this is equivalent to
the natural map

$\operatorname{Sym}_{k}(\mathfrak{m}_{n}/\mathfrak{m}_{n}^{2})\to\operatorname{gr}(R_{n})$

being a bijection. The colimit of these maps is given by

$\operatorname{Sym}_{k}(\mathfrak{m}/\mathfrak{m}^{2})\to\operatorname{gr}(R)$

and thus this map is a bijection, which, again by [7, (19.5.4)], implies that
$R$ is formally smooth over $k$.

To prove (2), let $x_{j}\in S$, $j\in J$, be elements whose images form a
basis for $\mathfrak{n}/\mathfrak{n}^{2}$ and such that for $I\subset J$ the
images of $x_{i}$, $i\in I$, form a basis for the subspace
$\mathfrak{m}/\mathfrak{m}^{2}$. Then the bijection
$\operatorname{Sym}_{k}(\mathfrak{m}/\mathfrak{m}^{2})\simeq\operatorname{gr}(R)$
from before induces an isomorphism

$k[[x_{i}\mid i\in I]]:=\varprojlim_{n}k[x_{i}\mid i\in I]/(x_{i}\mid i\in
I)^{n}\to\widehat{R}$

and similarly for $\widehat{S}$. In particular, the map $\widehat{\varphi}$ is
given by the inclusion

$k[[x_{i}\mid i\in I]]\hookrightarrow k[[x_{j}\mid j\in J]],$

which has a obvious retraction defined by $x_{j}\mapsto 0$ for $j\in
J\setminus I$. ∎

Let us now go back to the situation of Theorem B, that is, $X$ is a variety
over an algebraically closed field $k$ and for $x\in X(k)$ we let $X^{(x)}$ be
the associated isosingularity scheme. We keep the notation of the last
section. Our main result will establish the existence of “enough” regular
derivations on $\widehat{\mathcal{O}_{X,x}}$. Recall that a derivation
$d\in\operatorname{Der}_{k}(k[[\underline{x}]])$ is called _regular_ if there
exists $g\in k[[\underline{x}]]$ with $d(g)\in k[[\underline{x}]]^{*}$.

######  Lemma 2.3.

Assume that there exists $\beta_{0}>0$ such that the orbit map
$\mathcal{K}_{\beta}\to o(f_{\beta})$ is separable for all
$\beta\geq\beta_{0}$. Then, for every tangent vector $a\in T_{x}X^{(x)}$ there
exists a regular derivation
$d_{a}\in\operatorname{Der}_{k}(k[[\underline{x}]])$ satisfying
$d_{a}(f)\subset(f)$ and $d_{a}(x)=a$.

###### Proof.

Write $Z_{\beta}:=o(f_{\beta})$ and let $\beta\geq\beta_{0}$. By Section 1,
$\mathcal{K}_{\beta}$ and $Z_{\beta}$ are nonsingular varieties over an
algebraically closed field and thus the orbit map $\mathcal{K}_{\beta}\to
Z_{\beta}$ is generically smooth. Since it is
$\mathcal{K}_{\beta}$-equivariant (and the action of $\mathcal{K}_{\beta}$ on
both sides is obviously transitive) this implies that it is smooth everywhere.
In particular, the tangent map $T_{1}\mathcal{K}_{\beta}\to
T_{f_{\beta}}Z_{\beta}$ is surjective for all $\beta\geq\beta_{0}$. Setting
$Z:=o(f)\subset\mathcal{O}^{n}$, we get that $T_{1}\mathcal{K}\to T_{f}Z$ is
surjective. As both $\mathcal{K}$ and $Z$ are colimits of schemes smooth over
$k$, by Lemma 2.2 the morphism of formal schemes

$\Phi:\widehat{\mathcal{K}}_{1}\to\widehat{Z}_{f}$

admits a section
$\widetilde{\Psi}:\widehat{Z}_{f}\to\widehat{\mathcal{K}}_{1}$. Write $\Psi$
for the composition of the map
$\gamma:\widehat{(X^{(x)})}_{x}\to\widehat{Z}_{f}$ with $\widetilde{\Psi}$;
this gives a factorization of $\gamma$ as

$\textstyle{\widehat{(X^{(x)})}_{x}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Psi}$$\textstyle{\widehat{\mathcal{K}}_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Phi}$$\textstyle{\widehat{Z}_{f}.}$

Let us analyze what this factorization means for the tangent map of $\gamma$.
We may assume for convenience’s sake that $x=0$. To proceed we consider the
functorial description of formal neighborhoods via _test rings_
$(A,\mathfrak{m})$, that is, $A$ is a local $k$-algebra with
$A/\mathfrak{m}=k$ and $\mathfrak{m}^{n}=0$ for some $n$. Let
$a=(a_{1},\ldots,a_{N})$ be an $A$-point of $\widehat{(X^{(x)})}_{x}$, that
is, $a_{i}\in\mathfrak{m}$ and $f(a_{1},\ldots,a_{N})=0$. The map $\Psi(A)$ is
given by

$a\mapsto(M(a),\varphi(a)),\>M(a)\in\operatorname{GL}_{n}(A[[\underline{x}]]),\varphi(a)\in\operatorname{Aut}_{k}(A[[\underline{x}]]),$

where $M(a)\equiv 1\mod\mathfrak{m}$ and
$\varphi(a)\equiv\underline{x}\mod\mathfrak{m}$. Composing with $\Phi(A)$
gives $\gamma(A)$ and thus the identity

(2a) $f(\underline{x}+a)=M(a)\cdot f(\varphi(a)).$

To compute $T_{0}\gamma$ we take $A=k[\varepsilon]/(\varepsilon^{2})$ and let
$a=\widetilde{a}\varepsilon$ with $\widetilde{a}\in k^{N}$. Taking Taylor
expansions on both sides of (2a) gives

$f(\underline{x})+\frac{\partial f}{\partial
x}(\underline{x})\cdot\widetilde{a}\varepsilon=(1+\widetilde{M}(\widetilde{a})\varepsilon)(f(\underline{x})+\frac{\partial
f}{\partial\underline{x}}(\underline{x})\cdot\widetilde{\varphi}(\widetilde{a})\varepsilon),$

with $\widetilde{M}(\widetilde{a})\in k[[\underline{x}]]^{n\times n}$ and
$\widetilde{\varphi}(\widetilde{a})\in k[[\underline{x}]]^{n}$. Simplifying
yields

(2b) $\frac{\partial f}{\partial
x}(\underline{x})\cdot(\widetilde{a}-\widetilde{\varphi}(\widetilde{a}))=\widetilde{M}(\widetilde{a})\cdot
f(\underline{x}).$

Define
$d:=\frac{\partial}{\partial\underline{x}}\cdot(\widetilde{a}-\widetilde{\varphi}(\widetilde{a}))\in\operatorname{Der}_{k}(k[[\underline{x}]])$.
As
$\underline{x}+\widetilde{\varphi}(\widetilde{a})\in\operatorname{Aut}_{k}(k[[\underline{x}]])$,
it follows that $d(0)=\widetilde{a}$ and by (2b) we have $d(f)\subset(f)$. ∎

Now the proof of Theorem B follows from Lemma 2.3 together with the following
variant of the classical Nagata–Zariski–Lipman criterion:

######  Theorem 2.4.

Assume that $k$ is of characteristic $0$ and $X$ is a variety over $k$. Let
$X^{\prime}\subset X$ be a subvariety which is smooth of dimension $m$ at a
point $x\in X^{\prime}(k)$. Assume that for a choice of local coordinates
$x^{\prime}_{1},\ldots,x^{\prime}_{m}$ for $X^{\prime}$ at $x$ the associated
derivations $dx^{\prime}_{1},\ldots,dx^{\prime}_{m}$ lift to derivations on
$X$. Then

$\widehat{X}_{x}\simeq\widehat{(X^{\prime})}_{x}\times\widehat{Y}_{y},$

for some variety $Y$ and $y\in Y(k)$.

###### Proof.

See for example [11, Theorem 30.1]. ∎

###### Proof of Theorem B.

Assume $\operatorname{char}k=0$, then the orbit map $\mathcal{K}_{\beta}\to
o(f_{\beta})$ is separable since it is dominant. Thus Lemmas 2.3 and 2.4
together imply that

$\widehat{X}_{x}\simeq\widehat{(X^{(x)})}_{x}\times\widehat{Y}_{y},$

for some variety $Y$ and $y\in Y(k)$. Using Lemma 2.5 below it follows that
$\widehat{Y}_{q}$ itself has no smooth factors. ∎

######  Lemma 2.5.

Let $X$ be a scheme of finite type over an algebraically closed field $k$ and
let $x\in X(k)$. Assume that
$\widehat{X}_{x}\simeq\widehat{Y}_{y}\times\widehat{({\mathbb{A}}^{m})}_{0}$.
Then $\dim_{x}X^{(x)}\geq m$.

###### Proof.

By Lemma 1.12 we can find a common étale neighborhood $U$ for $x\in X$ and
$y^{\prime}=(y,0)\in Y\times{\mathbb{A}}^{m}$. Clearly
$\operatorname{Iso}(Y\times{\mathbb{A}}^{m},y^{\prime})\supset\\{y\\}\times{\mathbb{A}}^{m}$
and thus we are done using Lemma 1.13. ∎

We now want to discuss the existence of a decomposition as in Theorem B for
$k$ of positive characteristic. As the following example shows, this fails in
general.

######  Example 2.6.

Let $k$ be of characteristic $p>0$ and $X$ be the Whitney umbrella given by
$x^{p}+y^{p}z$ in ${\mathbb{A}}^{3}_{k}$. We claim that $\widehat{X}_{0}$ is
isomorphic to $\widehat{X}_{x}$, where $x=(0,0,t)$ for some $t\neq 0$. As $k$
is algebraically closed, there exists $s\in k$ with $s^{p}=t$. Consider now
the change of coordinates $\varphi$ given by

$x\mapsto x+ys,\>y\mapsto y,\>z\mapsto z.$

Then $\varphi(x^{p}+y^{p}z)=x^{p}+y^{p}(z+t)$ and thus
$\widehat{X}_{0}\simeq\widehat{X}_{x}$. In particular, we have that
$\operatorname{Iso}(X,0)$ is just the $z$-axis.

We claim that $\widehat{X}_{0}$ has no smooth factors and sketch the argument
here. By an extension of Theorem 2.4 (see for example [11, Exercise 30.1]) it
is sufficient to show that there does not exist a regular continuous
_Hasse–Schmidt derivation_
$D\in\operatorname{Der}_{k}^{\infty}(\widehat{\mathcal{O}_{X,0}})$. That is,
there does not exist a map
$D:\widehat{\mathcal{O}_{X,0}}\to\widehat{\mathcal{O}_{X,0}}[[t]]$ of
$\widehat{\mathcal{O}_{X,0}}$-algebras which is continuous for the respective
adic topologies and such that there exists an element
$g\in\widehat{\mathcal{O}_{X,0}}$ with $g(0)=0$ and $D(g)$ invertible. To that
avail, suppose such a map $D$ is given by

$D(x)=\sum_{i\geq 0}\widetilde{x}_{i}t^{i},\>D(y)=\sum_{i\geq
0}\widetilde{y}_{i}t^{i},\>D(z)=\sum_{i\geq 0}\widetilde{z}_{i}t^{i},$

satisfying $\widetilde{x}_{0}=x$ and so on. Applying $D$ to the equation
$x^{p}+y^{p}z=0$ yields a system of equations for
$\widetilde{x}_{i},\widetilde{y}_{i},\widetilde{z}_{i}$. For simplicity we
will give them explicitly only in the case $p=2$:

$\displaystyle y^{2}\widetilde{z}_{1}$ $\displaystyle=0$
$\displaystyle\widetilde{x}_{1}^{2}+y^{2}\widetilde{z}_{2}+\widetilde{y}_{1}^{2}z$
$\displaystyle=0$ $\displaystyle\ldots$

From the first equation it follows that $\widetilde{z}_{1}=0$ and from the
second that $\widetilde{x}_{1}(0)=0$. Now suppose that $\widetilde{y}_{1}$ is
invertible. Then the second equation gives

$z=-\frac{y^{2}\widetilde{z}_{2}+\widetilde{x}_{1}^{2}}{\widetilde{y}_{1}^{2}}.$

Note that the right hand side has order $\geq 2$, which gives a contradiction.
Thus it follows that for any $g\in\widehat{\mathcal{O}_{X,0}}$ with $g(0)=0$
we have that $D(g)$ is not invertible.

One of the main assumptions in the proof of Theorem B was the separability of
the orbit map $\mathcal{K}_{\beta}\to o(f_{\beta})$ for $\beta\gg 0$. As
observed already in [6, Example 2.9], this fails in positive characteristics
for general isolated singularities. The example provided there was the cusp
singularity $f=y^{2}+x^{3}$ for $\operatorname{char}(k)=2$. While obviously
not applicable to the case of isolated singularities, Lemma 2.3 can be used to
construct related examples where the separability of the orbit map fails.

######  Example 2.7.

Let $k$ be algebraically closed with $\operatorname{char}k=2$ and consider the
deformation $\widetilde{f}=x^{2}+y^{3}+zy^{2}\in k[x,y,z]$ of the cusp
singularity $f=x^{2}+y^{3}$. Set $X=V(\widetilde{f})\subset{\mathbb{A}}^{3}$;
we claim that $X^{(0)}=V(x,y)\simeq{\mathbb{A}}^{1}$. If $t\neq 0$ and
$x=(0,0,t)$, then an isomorphism between $\widehat{X}_{0}$ and
$\widehat{X}_{x}$ is given by the map

$x\mapsto x+ys,\>y\mapsto y,\>z\mapsto z,$

where $s\in k$ with $s^{2}=t$. However, there does not exist
$d\in\operatorname{Der}_{k}(k[[x,y,z]])$ satisfying
$d(\widetilde{f})\subset(\widetilde{f})$ and $d(0)=(0,0,1)$, as can be
verified with an argument similar to the one in Example 2.6. Therefore, by
Lemma 2.3 the orbit map $\mathcal{K}_{\beta}\to o(\widetilde{f}_{\beta})$ is
inseparable for infinitely many $\beta>0$.

Note that the same argument also works for $f=x^{p}+y^{p}z$ and
$\operatorname{char}k=p$, as in Example 2.6.

As mentioned in the introduction, these examples prompt the question whether
inseparability of the orbit map is the main obstruction to extending Theorem B
to positive characteristics. We expect a further investigation into this
problem to shed more light on the formal structure of singularities for
$\operatorname{char}k=p$.

## References

  * [1] M. Artin  “Algebraic approximation of structures over complete local rings”  In _Inst. Hautes Études Sci. Publ. Math._ , 1969, pp. 23–58
  * [2] Robert Ephraim  “Isosingular loci and the Cartesian product structure of complex analytic singularities”  In _Trans. Amer. Math. Soc._ 241, 1978, pp. 357–371
  * [3] Raul Epure and Mathias Schulze  “Hypersurface singularities with monomial Jacobian ideal”, 2021  arXiv:2101.04069 [math.AG]
  * [4] Terence Gaffney and Herwig Hauser  “Characterizing singularities of varieties and of mappings”  In _Invent. Math._ 81.3, 1985, pp. 427–447
  * [5] Gert-Martin Greuel and Thuy Huong Pham  “Algorithms for group actions in arbitrary characteristic and a problem in singularity theory”  In _Appl. Algebra Engrg. Comm. Comput._ 31.2, 2020, pp. 87–100
  * [6] Gert-Martin Greuel and Thuy Huong Pham  “On finite determinacy for matrices of power series”  In _Math. Z._ 290.3-4, 2018, pp. 759–774
  * [7] A. Grothendieck  “Éléments de géométrie algébrique. IV. Étude locale des schémas et des morphismes de schémas. I”  In _Inst. Hautes Études Sci. Publ. Math._ , 1964, pp. 259
  * [8] H. Hauser and G. Müller  “The trivial locus of an analytic map germ”  In _Ann. Inst. Fourier_ 39.4, 1989, pp. 831–844
  * [9] Herwig Hauser and Gerd Müller  “Analytic curves in power series rings”  In _Algebraic geometry, Proceedings of the conference held in Berlin, March 9–15, 1988_ 76.1-2, 1990, pp. 197–201
  * [10] John N. Mather and Stephen S.. Yau  “Classification of isolated hypersurface singularities by their moduli algebras”  In _Invent. Math._ 69.2, 1982, pp. 243–251
  * [11] Hideyuki Matsumura  “Commutative ring theory” 8, Cambridge Studies in Advanced Mathematics  Cambridge University Press, Cambridge, 1989, pp. xiv+320
  * [12] J.. Milne  “Algebraic groups” 170, Cambridge Studies in Advanced Mathematics  Cambridge University Press, Cambridge, 2017, pp. xvi+644
  * [13] The Stacks Project Authors  “Stacks Project”, https://stacks.math.columbia.edu, 2020
  * [14] Hassler Whitney  “Local properties of analytic varieties”  In _Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse)_ Princeton Univ. Press, Princeton, N. J., 1965, pp. 205–244


# Pruning Convolutional Neural Networks for Image Instance Retrieval

###### Abstract

In this work, we focus on the problem of image instance retrieval with deep
descriptors extracted from pruned Convolutional Neural Networks (CNN). The
objective is to heavily prune convolutional edges while maintaining retrieval
performance. To this end, we introduce both data-independent and data-
dependent heuristics to prune convolutional edges, and evaluate their
performance across various compression rates with different deep descriptors
over several benchmark datasets. Further, we present an end-to-end framework
to fine-tune the pruned network, with a triplet loss function specially
designed for the retrieval task. We show that the combination of heuristic
pruning and fine-tuning offers $5\times$ compression rate without considerable
loss in retrieval performance.

Index Terms—  CNN, Pruning, Triplet Loss, Image Instance Retrieval, Pooling

##  1 Introduction

Image instance retrieval is the problem of retrieving images from a large
database that contain or depict similar objects to a target image.
Convolutional Neural Networks (CNN)-based descriptors [1, 2, 3, 4, 5] have
recently been used to generate compact image descriptors with high retrieval
performance, and are rapidly becoming the dominant approach for retrieval
problem. Their major drawback is the size of their models, running into
hundreds of megabytes.

Smaller networks are desirable for use in mobile and embedded applications,
where storage, transmission, and computational power is limited. For efficient
hardware implementations of deep neural networks, smaller networks reduce cost
and improve chip performance. Storing the entire network on-chip allows fast
access and reduce processing latency. There are also gains in distributed
training, where network latency bottlenecks the sharing of updated parameters,
and smaller networks significantly improve speed. Finally, emerging MPEG
standards like Compact Descriptors for Visual Search (CDVS) [6] and Compact
Descriptors for Video Analysis (CDVA) [7] require memory-efficient models for
streaming and hardware implementations.

Model compression strategies reduce the computational, memory, and bandwidth
costs; and pruning is a common first technique. Pruning algorithms reduce
network size by discarding edges or nodes, and can be heuristic or analytic
[8]. Modern pruning algorithms have thus far been evaluated on CNN performing
image classification with a softmax loss function; we investigate the
adaptation of these algorithms to image instance retrieval problem, and
present an empirical evaluation of their effectiveness.

###  1.1 Related Work

Image Instance Retrieval with CNN. Image retrieval systems generally construct
a _global image descriptor_ , a vector that represents the contents of an
image. Instead of descriptor extracted from fully-connected layer, state-of-
the-art use the intermediate output of CNN (e.g. convolutional layers) with
additional pooling operations to generate descriptors [1, 2, 3]. The
application of multi-scale and multi-rotation feature construction and pooling
further improves scale- and rotation-invariance [4, 9]. Very recently, pre-
trained CNNs for ImageNet classification are repurposed for the image
retrieval problem, by fine-tuning them with retrieval specific loss functions
such as triplet loss [10, 11, 12].

Network Pruning Heuristic pruning algorithms generally assign either nodes or
edges _salience_ scores and remove those with the lowest scores [8]. In early
neural network literature there was a considerable interest in developing such
algorithms. Heuristics include _Optimal Brain Damage_ by LeCun et al. [13];
derivative-based methods by Mozer and Smolensky [14], and Karnin [15]. Other
work removes nodes where the weights of incoming connections has the smallest
variance, but this has been mostly studied in the realm of fault tolerance
[16].

In current networks, a popular strategy is the removal of low-magnitude edges.
Han et al. [17] demonstrates this simple strategy on AlexNet, reducing the
number of free parameters by a factor of $9\times$ by pruning alone without
any loss in image classification performance. Their reported results heavily
prune edges from fully-connected layers ($\sim$89% are pruned); on
convolutional layers alone, 37% of convolutional edges are dropped. Thus, the
majority of the savings comes from the fully-connected layers, which contain
96% of the parameters of the entire network.

There are also analytic algorithms compress networks layer-by-layer, replacing
the convolution matrix with a compressed representation. This compression is
achieved by removing redundancy in the function that each layer computes. This
approach has been vigorously explored in recent years, with work by Kim et al.
[18], Mariet and Sra [19], Lebedev et al. [20], and Denton et al. [21] each
with different redundancy reduction mechanisms.

###  1.2 Contributions

Compared to fully-connected layers that contain the most redundancy, heavily
pruning edges on convolutional layers is more challenging. In this work, we
focus on heuristic criteria to prune convolutional edges especially for image
instance retrieval. We make the following contributions:

  * •

We investigate both data-independent and data-dependent heuristics to prune
convolutional edges. We perform a thorough evaluation across various
compression rates and deep pooled descriptors over several benchmark datasets.
Results suggest that heuristic pruning is capable of reducing the network size
by $2\times$ without retrieval performance loss.

  * •

We introduce an end-to-end framework for fine-tuning pruned network, specially
tailored to image instance retrieval with a triplet loss function. Combining
pruning and rank-based fine-tuning can provide a factor of $5\times$
compression with minimal loss in retrieval performance.

##  2 Method

###  2.1 Pruning Convolutional Edges

We consider different heuristics to assign salience scores[8] to edges.
Consider an arbitrary layer in a neural network, $N_{i}$ is a random variable
following the activation of the $i^{\text{th}}$ node when presented with data
from a training set, $w_{i,j}$ is the weight of the edge connecting that node
to the $j^{\text{th}}$ node in the next layer, $\mathcal{L}$ is the value of
the loss function when run on some data. From existing literature, we consider
computing the following heuristics for each edge:

  1. 1.

$|w_{i,j}|$, the simplest heuristic, requiring no data. This was recently
popularized by Han et al. [17].

  2. 2.

$\frac{\text{d}\mathcal{L}}{\text{d}w_{i,j}}w_{i,j}$, which was recently used
by Molchanov et al. [22] to prune networks for transfer learning. This is
justified as the Taylor expansion of the function computing the difference in
loss function with and without the weight $w_{i,j}$, and is shown to be
applicable to transfer learning.

  3. 3.

$\langle|N_{i}|\rangle\cdot|w_{i,j}|$ Mean activation.

  4. 4.

$\text{Var}[N_{i}]\cdot w_{i,j}^{2}$ Variance of activation.

One may notice that heuristic 2 requires data with ground-truth labels to
compute the loss-function term
($\frac{\text{d}\mathcal{L}}{\text{d}w_{i,j}}$). Computing heuristic 3 and 4
requires data, but does not require that it have labels.

In order to prune the network to a fraction $t$ of its original size, we first
compute the salience score for each edge in the network. We then sort all
salience scores across all layers and select the threshold salience value,
$\tau$, such that $(1-t)$ of the salience scores are below this value. We then
remove all edges with salience scores less than $\tau$. Throughout our
experiments, we report the network size as the total fraction of edges
removed. We do not prune bias nodes or report them in the network size.

###  2.2 Convolutional Feature Pooling

In constructing the global image descriptor we append a pooling layer to the
pruned network. The pooling function employed is critical to the performance
of the model. In this work, we consider Square-root pooling (SQP) [23] and
Regional-Maximum Activations of Convolutions (R-MAC) [4] pooling functions.
Consider an arbitrary image $X$, with $C$ feature maps
$\\{\boldsymbol{x}_{1},...,\boldsymbol{x}_{C}\\}$ extracted from intermediate
layer, $\boldsymbol{x}_{c}$ is a feature map of width $W$ and height $H$.
Square-root pooling, $f_{2}(\cdot)$ is defined as

$f^{\text{SQP}}(\boldsymbol{x}_{c})=\sqrt{\frac{1}{W\cdot H}\sum^{W\cdot
H}_{i=1}x_{c,i}^{2}}.$ (1)

R-MAC [4] pooling is computed by first performing maximum pooling over regions
of interest (ROI), then average pooling.

$f^{\text{R-MAC}}(\boldsymbol{x}_{c})=\frac{1}{N_{\text{ROI}}}\sum^{N_{\text{ROI}}}_{i=1}\max_{j\in[1,S_{\text{ROI}}]}(x^{i}_{c,j}),$
(2)

where $S_{\text{ROI}}$ is the number of ROIs, and $\boldsymbol{x}^{i}_{c}$
denotes the $i^{th}$ ROI sampled from feature map $\boldsymbol{x}_{c}$, with
size $S_{\text{ROI}}\leq W\cdot H$.

###  2.3 Triplet-based Fine-tuning

To fine-tune remaining parameters in an end-to-end manner, we need to design a
loss function for the pruned network. Following existing work by Arandjelović
et al. [11], Gordo et al. [12], we define a triplet $(X^{q},X^{+},X^{-})$ that
contains the query image $X^{q}$, a positive matching image $X^{+}$ and a
negative, non-matching image $X^{-}$. The images are selected so that query
image $X^{q}$ is more similar to positive image $X^{+}$ than to the negative
image $X^{-}$. The triplet should meet the condition that
$K(X^{q},X^{+})>K(X^{q},X^{-})$, where $K$ is a function computing pairwise
image similarity.

Accordingly, we define the triplet loss as:

$L_{q,+,-}=\max\\{0,m+K(X^{q},X^{-})-K(X^{q},X^{+})\\},$ (3)

where $m$ is a positive margin parameter.

Following [2], we define the similarity measure $K$ as:

$K(X,Y)=\beta(X)\beta(Y)\sum^{C}_{c=1}k(f(\boldsymbol{x}_{c}),f(\boldsymbol{y}_{c})),$
(4)

where $f(.)$ denotes the pooling operation applied on feature maps,
$k(f(\boldsymbol{x}_{c}),f(\boldsymbol{y}_{c}))=<f(\boldsymbol{x}_{c}),f(\boldsymbol{y}_{c})>$
is the scalar product of the pooled features, $\beta(.)$ is a normalization
term computed by
$\beta(X)=\sqrt{\sum^{C}_{c=1}k(f(\boldsymbol{x}_{c}),f(\boldsymbol{x}_{c}))}$.

##  3 Experiments

We begin with a VGG-VeryDeep-16 network [24] pre-trained on ImageNet, and keep
only the layers from the input up to and including the last pooling layer
pool5. Convolutional layers are pruned using each of the four heuristics, then
fine-tuned for 20 epochs on the image retrieval task using the triplet loss
function discussed earlier. All pruning and fine-tuning, are implemented with
the MatConvNet library, with the 3D-Landmarks [25] dataset. Testing is
performed on the INRIA Holidays [26], Oxford5k [27] and Paris6k [28] datasets
which consist of outdoor scenes and buildings; and the UKbench [29] dataset
which features close-up shots of objects in indoor environments.

In all reported results, the accuracy metric for the Holidays, Oxford5k, and
Paris6k datasets is the mean average precision (MAP), and the metric for the
UKbench dataset is $4\times$recall@4. Note that we report results without
post-processing (e.g., PCA whitening) on pooled features.

$20$%$40$%$60$%$80$%$100$%$0$%$20$%$40$%$60$%$80$%$100$%Fraction of Network
RemainingMAPHolidays$20$%$40$%$60$%$80$%$100$%$0$%$20$%$40$%$60$%Fraction of
Network
RemainingMAPOxford5k$20$%$40$%$60$%$80$%$100$%$0$%$20$%$40$%$60$%$80$%Fraction
of Network
RemainingMAPParis6k$20$%$40$%$60$%$80$%$100$%$0$$1$$2$$3$$4$Fraction of
Network Remaining$4\times$recall@4UKbenchH. 1, SQPH. 2, SQPH. 3, SQPH. 4,
SQPH. 1, R-MACH. 2, R-MACH. 3, R-MACH. 4, R-MAC

Fig. 1: Performance of pruned networks by remaining network size across
different datasets. In each dataset, lines are colored by pruning heuristic
and dashed by pooling feature (solid lines use SQP pooling, dashed lines use
R-MAC). No fine-tuning was performed. We observe that Heuristic 1 consistently
performs better than the other heuristics, and the use of SQP features over
R-MAC improves performance.

###  3.1 Pooling Features

We first pruned the convolutional layers of VGG-VeryDeep-16 using the four
heuristics discussed earlier. Each network was pruned to five different sizes,
from 10% to 50% of the original network size. The performance of each pruned
network on each of the four datasets is presented in Figure 1.

From Figure 1, we observe that heuristic 1 (magnitude of edge) consistently
performs better than the other heuristics. In fact, until about 40% of the
edges are remaining, networks pruned with heuristic 1 perform not
significantly worse than unpruned networks. This corresponds to a $2.5\times$
savings in size for minimal computational and implementation effort.

Additionally, we observe that the accuracy graphs of networks seldom
intersect, and so heuristic 1 dominates the entire domain. This, along with
the advantage of requiring minimal computation and no data, suggests that
heuristic 1 is better suited to practical implementations than the other
heuristics proposed.

We also use the data in Figure 1 to compare the performance of SQP and R-MAC
features. Across three out of four datasets, SQP features perform better than
networks with R-MAC features pruned to the same size. From this, we observe
that SQP features are generally superior, providing around 2 percentage
points’ performance gain over R-MAC. Thus, we choose SQP for fine-tuning in
the subsequent sections.

H1H2H3H4$40$%$60$%$80$%$100$%+50-2-2MAPHolidaysH1H2H3H4+16+27+22+21Oxford5kH1H2H3H4+5+17+10+20Paris6kH1H2H3H41.62.43.24.0-.33-.11-.34-.25$4\times$recall@4UKbench

Fig. 2: Performance of 50% pruned networks on different heuristics, grouped by
dataset. The colored bar represents performance before fine-tuning, and the
clear bar represents the change in performance with fine-tuning for 20 epochs.
The number above each bar is the change in percentage points or value. We
observe that fine-tuning greatly improves the performance across Oxford5k and
Paris6k datasets, suggesting that it is an important step in our pruning
pipeline.

###  3.2 Fine-tuning

As established by Han et al. [17, 30], fine-tuning pruned networks can recover
image classification performance lost in pruning. To investigate this effect
for image instance retrieval, we fine-tuned networks pruned with each
heuristic, and then evaluated their performance. These networks were pruned to
50% of their original size, and evaluated with SQP. Figure 2 shows the
performance of these networks before and after fine-tuning.

We observe that in two of the four datasets, fine-tuning improves performance
significantly, regardless of the pruning heuristic. Even after $50\%$ pruning,
the mean average precision of these networks approaches $80\%$. Also, after
fine-tuning, heuristic 1 reports higher performance in all datasets. This
further supports our earlier recommendation of heuristic 1, and corroborates
the work of Han et al. [17, 30].

We note that fine-tuning decreases the $4\times$recall@4 score on the UKbench
dataset, regardless of heuristic used. This is likely because fine-tuning on
the building-centric 3D-Landmarks dataset transfers well to Oxford5k and
Paris6k, but poorly to the object-centric UKbench dataset.

$10$%$20$%$30$%$40$%$50$%$0$%$20$%$40$%$60$%$80$%$100$%Fraction of Network
RemainingMAPHolidaysOxford5kParis6kUKbench+FT+FT+FT+FT00.81.62.43.24.0$4\times$recall@4

Fig. 3: Performance (with SQP pooling) of networks pruned by heuristic 1,
before and after fine-tuning (FT). Pruning the network reduces performance
significantly, but fine-tuning can generally restore most of the performance.

###  3.3 Pruned Network Size

We now investigate the size of the network pruned and its effect on accuracy.
As per our earlier recommendation, we choose several networks pruned (to
different sizes) with heuristic 1, pooled with SQP, and fine-tuned. We
evaluate their performance on each of testing datasets before and after fine-
tuning, and present the results in Figure 3.

We note that networks pruned to $20\%$ of the initial model size exhibit poor
performance compared to networks pruned to $50\%$, but this gap in performance
diminishes upon fine-tuning. Fine-tuning allows us to improve compression rate
from a factor of $2\times$ to $5\times$ with minimal performance penalty.

This performance improvement does not extend to networks pruned to 10% of
their initial size. While these networks generally exhibit improvement in
performance, their performance does not reach the performance of networks
pruned to $50\%$ of their size. This discontinuity suggests that the pruning
algorithms are no longer able to exploit redundancy in the model, and further
pruning will worsen performance. The minimum model size without loss of
performance lies between $10-20\%$ of the original model size.

Further investigation in this threshold is warranted. We observe this
transition at around the same range in all datasets, suggesting that this is a
property of the network or the heuristic. Further experiments may show that
the heuristics perform differently at extremely small sizes and with little
redundancy.

c11c21c31c33c42c51c53$0$%$20$%$40$%$60$%$80$%$100$%Network LayerFraction layer
remaining50% Network Remaining20% Network Remaining10% Network Remaining

Fig. 4: Fraction of each layer remaining after different amounts of pruning
(with heuristic 1). We observe that the layers closest to the data are pruned
the least, a pattern that is consistent with all heuristics. This is likely
because our pruning leverages the increasing redundancy in higher layers.

###  3.4 Pruned Layer Sizes

We chart the size of each convolutional layer in the network in Figure 4 for
three different sizes when pruned with heuristic 1. As the network size
shrinks, layers further up the network lose convolutional edges
disproportionately more quickly. Even when the network is pruned to 10% of its
original size, the lowest layer still retains 95% of its edges, and the
highest layers retain only about 8% of their edges. This same trend is
observed across all heuristics.

##  4 Conclusions

Pruning edges on convolutional layers is a more challenging operation than on
fully-connected layers. In this work, we presented an end-to-end framework for
compressing CNN, specially tailored to efficiently pruning convolutional edges
with a triplet loss function. We present thorough evaluation across varied
pruning parameters and deep features on several datasets. Our experiments
suggest that pruning and fine-tuning can provide a factor of $2\times$ to
$5\times$ compression with minimal loss in performance.

##  5 References

## References

  * Babenko et al. [2014] A. Babenko, A. Slesarev, A. Chigorin, and V. Lempitsky, “Neural codes for image retrieval,” in _ECCV_ , 2014.
  * Babenko and Lempitsky [2015] A. Babenko and V. Lempitsky, “Aggregating local deep features for image retrieval,” in _ICCV_ , 2015.
  * Kalantidis et al. [2015] Y. Kalantidis, C. Mellina, and S. Osindero, “Cross-dimensional weighting for aggregated deep convolutional features,” in _arXiv:1512.04065_ , 2015.
  * Tolias et al. [2016] G. Tolias, R. Sicre, and H. Jégou, “Particular object retrieval with integral max-pooling of CNN activations,” in _ICLR_ , 2016.
  * Chandrasekhar et al. [2016] V. Chandrasekhar, J. Lin, O. Morère, H. Goh, and A. Veillard, “A practical guide to cnns and fisher vectors for image instance retrieval,” _Signal Processing_ , 2016.
  * Duan et al. [2016] L.-Y. Duan, V. Chandrasekhar, J. Chen, J. Lin, Z. Wang, T. Huang, B. Girod, and W. Gao, “Overview of the mpeg-cdvs standard,” _IEEE Transactions on Image Processing_ , vol. 25, no. 1, pp. 179–194, 2016.
  * Chandrasekhar et al. [2017] V. Chandrasekhar, J. Lin, Q. Liao, O. Morere, A. Veillard, L. Duan, and T. Poggio, “Compression of deep neural networks for image instance retrieval,” in _Data Compression Conference_ , 2017.
  * Reed [1993] R. Reed, “Pruning algorithms-a survey,” _IEEE transactions on Neural Networks_ , vol. 4, no. 5, pp. 740–747, 1993.
  * Morère et al. [2017] O. Morère, A. Veillard, J. Lin, J. Petta, V. Chandrasekhar, and T. Poggio, “Group invariant deep representations for image instance retrieval,” in _AAAI Spring Symposium Series_ , 2017.
  * Lin et al. [2016] J. Lin, O. Morère, J. Petta, V. Chandrasekhar, and A. Veillard, “Tiny descriptors for image retrieval with unsupervised triplet hashing,” in _Data Compression Conference_ , 2016.
  * Arandjelović et al. [2016] R. Arandjelović, P. Gronat, A. Torii, T. Pajdla, and J. Sivic, “NetVLAD: CNN architecture for weakly supervised place recognition,” in _CVPR_ , 2016\.
  * Gordo et al. [2016] A. Gordo, J. Almazán, J. Revaud, and D. Larlus, “Deep image retrieval: Learning global representations for image search,” in _ECCV_ , 2016.
  * LeCun et al. [1989] Y. LeCun, J. S. Denker, S. A. Solla, R. E. Howard, and L. D. Jackel, “Optimal brain damage,” in _NIPS_ , 1989.
  * Mozer and Smolensky [1989] M. C. Mozer and P. Smolensky, “Skeletonization: A technique for trimming the fat from a network via relevance assessment,” in _University of Colorado, Boulder_ , 1989.
  * Karnin [1990] E. D. Karnin, “A simple procedure for pruning back-propagation trained neural networks,” _IEEE Transactions on Neural Networks_ , vol. 1, no. 2, pp. 239–242, 1990.
  * Segee and Carter [1991] B. E. Segee and M. J. Carter, “Fault tolerance of pruned multilayer networks,” in _IJCNN_ , 1991.
  * Han et al. [2015] S. Han, J. Pool, J. Tran, and W. J. Dally, “Learning both weights and connections for efficient neural networks,” in _NIPS_ , 2015.
  * Kim et al. [2015] Y.-D. Kim, E. Park, S. Yoo, T. Choi, L. Yang, and D. Shin, “Compression of deep convolutional neural networks for fast and low power mobile applications,” in _arXiv:1511.06530_ , 2015.
  * Mariet and Sra [2016] Z. Mariet and S. Sra, “Diversity networks,” in _ICLR_ , 2016.
  * Lebedev et al. [2014] V. Lebedev, Y. Ganin, M. Rakhuba, I. V. Oseledets, and V. S. Lempitsky, “Speeding-up convolutional neural networks using fine-tuned cp-decomposition,” in _ICLR_ , 2014.
  * Denton et al. [2014] E. L. Denton, W. Zaremba, J. Bruna, Y. LeCun, and R. Fergus, “Exploiting linear structure within convolutional networks for efficient evaluation,” in _NIPS_ , 2014.
  * Molchanov et al. [2016] P. Molchanov, S. Tyree, T. Karras, T. Aila, and J. Kautz, “Pruning convolutional neural networks for resource efficient transfer learning,” in _arXiv:1611.06440_ , 2016.
  * Lin et al. [2017] J. Lin, V. Chandrasekhar, O. Morère, A. Veillard, and L. Yang, “Revisiting deep convolutional feature pooling for image instance retrieval,” in _submission_ , 2017.
  * Simonyan and Zisserman [2014] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” in _arXiv:1409.1556_ , 2014.
  * Radenović et al. [2016] F. Radenović, G. Tolias, and O. Chum, “CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples,” in _ECCV_ , 2016.
  * Jegou et al. [2008] H. Jegou, M. Douze, and C. Schmid, “Hamming embedding and weak geometric consistency for large scale image search,” in _ECCV_ , 2008.
  * Philbin et al. [2007] J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, “Object retrieval with large vocabularies and fast spatial matching,” in _CVPR_ , 2007.
  * Philbin et al. [2008] ——, “Lost in quantization: Improving particular object retrieval in large scale image databases,” in _CVPR_ , 2008.
  * Nistér and Stewénius [2006] D. Nistér and H. Stewénius, “Scalable recognition with a vocabulary tree,” in _CVPR_ , 2006.
  * Han et al. [2016] S. Han, H. Mao, and W. J. Dally, “Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding,” in _ICLR_ , 2016.


Note that, compared to $Q$-value Active Inference, here we do not have to make
any additional approximations, because $G$ only depends linearly on
$q(S^{\prime}|A)$.

Similarly to above, when optimizing with respect to $q(A)$ while keeping
$q(S)$ and $q(S^{\prime}|A)$ fixed, we obtain that $q^{\ast}(A)$ is a
Boltzmann distribution with energy $F_{\mathbf{S}}-G$ and prior $p_{0}(A)$.
Optimizing $q(S)$ while keeping $q(A)$ and $q(S^{\prime}|A)$ constant has the
same result as shown in (33a) because as before the only dependencies on
$q(S)$ are in $F_{\mathbf{S}}$. Finally, in order to read off the solution of
the optimization with respect to $q(S^{\prime}|A)$ while keeping $q(S)$ and
$q(A)$ constant, we can rewrite $F_{\mathbf{S}}-G$ as follows

$\displaystyle q^{\ast}(S^{\prime}|A)$
$\displaystyle=\mathop{\mathrm{argmax}}_{q(S^{\prime}|A)}\,F(q\|\phi)=\mathop{\mathrm{argmax}}_{q(S^{\prime}|A)}\big{(}F_{\mathbf{S}}(A)-G(A)\big{)}$
$\displaystyle=\mathop{\mathrm{argmax}}_{q(S^{\prime}|A)}\left\langle\log\frac{q(S^{\prime}|A)}{e^{\langle
T\rangle_{q(S)}+g(S^{\prime})}}\right\rangle_{q(S^{\prime}|A)}$

so that in total we obtain the set of equations

$\displaystyle q^{\ast}(S)$
$\displaystyle=\tfrac{1}{\mathcal{Z}}\,p_{0}(x|S)p_{0}(S)e^{\langle
T\rangle_{q(S^{\prime}|A)q(A)}}$ (34a) $\displaystyle q^{\ast}(S^{\prime}|A)$
$\displaystyle=\tfrac{1}{\mathcal{Z}(A)}\,e^{\langle
T\rangle_{q(S)}+g(S^{\prime})}$ (34b) $\displaystyle q^{\ast}(A)$
$\displaystyle=\tfrac{1}{\mathcal{Z}}\,p_{0}(A)e^{-F_{\mathbf{S}}(A)+G(A)},$
(34c)

where $\mathcal{Z}$ denotes the respective normalization constants, and again
$T=\log p_{0}(S^{\prime}|S,A)$.

It is noteworthy that recently another free energy approach similar to Active
Inference has been introduced that does not make use of variational free
energy, but of a different functional termed generalized free energy (Parr and
Friston, , 2019). Despite of the different functional form, this version uses
a reference function that is similar to the direct Active Inference approach,
where the desired distribution is also multiplied directy to the generative
model but with a renormalization that results in a modified generative model
over observations, states, and actions. Using this renormalized reference in a
variational free energy approach would result in trivial inference reproducing
the fixed prior $p_{0}(A)$, corresponding to Bayes’ conditioning the modified
generative model on the past analogous to perceptual Bayesian inference, e.g.,
$p(A|X)=p_{0}(A)$ in the case of the one-step example. In contrast, the
minimization of the free energy functional used in (Parr and Friston, , 2019)
does not correspond to a Bayesian inference process, which is why we do not
further discuss it here.

####  A.1.3 Direct Active Inference (variational Control as Inference)—Bethe
assumption

Here, we derive the update equations resulting from the minimization of the
variational free energy for the reference (25a) under a Bethe approximation,
which therefore is a more precise variational formulation of Control as
Inference as the mean-field approximation of the previous section. In fact, it
turns out that such equations are equivalent to Belief propagation (Yedidia et
al., , 2001), a well-known inference method that produces exact marginals in
tree-like graphs (Pearl, , 1988), such as the probabilistic models considered
in the article and in the Active Inference literature.

Analogous to the previous section, without any specific restrictions on $q$ we
can write the total free energy for the one-step example from Section 5.2 with
the reference (25a) as

$\displaystyle F(q\|\phi)$
$\displaystyle=\underbrace{\left\langle\log\frac{q(X^{\prime},S,S^{\prime}|A)}{p_{0}(R\hskip
1.0pt{=}\hskip 2.0pt1,X\hskip 1.0pt{=}\hskip
2.0ptx,X^{\prime},S,S^{\prime}|A)}\right\rangle_{q}}_{\eqqcolon\,\langle
F(A)\rangle_{q(A)}}$ $\displaystyle\quad+\,D_{\mathrm{KL}}(q(A)\|p_{0}(A))$

from which it immediately follows that minimizing with respect to $q(A)$,
while considering $q(X^{\prime},S,S^{\prime}|A)$ constant, results in a
Boltzmann distribution with energy $F(A)$ and prior $p_{0}(A)$. $F(A)$ is the
variational free energy of $q(X^{\prime},S,S^{\prime}|A)$ with respect to the
reference $p_{0}(R\hskip 1.0pt{=}\hskip 2.0pt1,X\hskip 1.0pt{=}\hskip
2.0ptx,X^{\prime},S,S^{\prime}|A)$ given by

$\underbrace{p_{0}(x|S)p_{0}(S)}_{\eqqcolon
f_{1}(S)}\underbrace{p_{0}(S^{\prime}|S,A)}_{\eqqcolon
f_{2}(S,S^{\prime})}\underbrace{p_{0}(X^{\prime}|S^{\prime})}_{\eqqcolon
f_{3}(S^{\prime},X^{\prime})}\underbrace{p_{\mathrm{des}}(X^{\prime})}_{\eqqcolon
f_{4}(X^{\prime})}\,.$

Thus, minimizing $F(A)$ with respect to $q(X^{\prime},S,S^{\prime}|A)$ without
any restrictions or simplifications results in the exact Bayes’ posterior
$p(X^{\prime},S,S^{\prime}|A,R=1,X=x)$

$\frac{1}{\mathcal{Z}(A)}\,f_{1}(S)\,f_{2}(S,S^{\prime})\,f_{3}(S^{\prime},X^{\prime})\,f_{4}(X^{\prime})\,,$

where $\mathcal{Z}(A)$ denotes the corresponding normalization< constant. The
problem that we want to solve is to find an approximation to this Bayes’
posterior that is more precise than the mean-field approximation of the
previous section but requires less involved computations than the
determination of $\mathcal{Z}(A)$. While one attempt is to partition the full
graph into smaller graphs and apply a naive mean-field approximation inside of
each subgraph, known as a structured mean-field approximation (Saul and
Jordan, , 1996), the Bethe approximation follows a slightly different
approach. It is the simplest version of the cluster variation methods often
attributed to Kikuchi (Kikuchi, , 1951), a family of region-based free energy
approximations (Yedidia et al., , 2005), where one keeps beliefs over
different sections of the factor graph. Specifically, in the Bethe assumption,
the regions consist of each factor and its neighbouring nodes, which can also
be seen as allowing pair-wise interactions. Following the systematic treatment
in (Yedidia et al., , 2005), the Bethe approximation for our example consists
of seven belief functions, one for each factor, $b_{1},\dots,b_{4}$, and one
for each variable, $b_{S}$, $b_{S^{\prime}}$, and $b_{X^{\prime}}$,

$q(S,S^{\prime},X^{\prime}|A)=\frac{b_{1}(S)b_{2}(S,S^{\prime})b_{3}(S^{\prime},X^{\prime})b_{4}(X^{\prime})}{b_{S}(S)b_{S^{\prime}}(S^{\prime})b_{X^{\prime}}(X^{\prime})}$
(35)

where the marginals of the factor beliefs are required to be consistent with
the single-variable beliefs. Thus, the variational free energy $F(A)$ can be
written as

$F(A)=\sum_{k=1}^{4}\left\langle\log\frac{b_{k}}{f_{k}}\right\rangle_{b_{k}}-\sum_{Y\in\\{S,S^{\prime},X^{\prime}\\}}\langle\log
b_{Y}\rangle_{b_{Y}}$

which has to be minimized under the consistency and normalization contraints,
leading to the Lagrangian

$\displaystyle F(A)$
$\displaystyle+\sum_{s}\lambda_{1}(s)\big{(}b_{S}(s)-b_{1}(s)\big{)}$
$\displaystyle+\sum_{s}\lambda_{2S}(s)\left(b_{S}(s)-\sum_{s^{\prime}}b_{2}(s,s^{\prime})\right)$
$\displaystyle+\sum_{s^{\prime}}\lambda_{2S^{\prime}}(s^{\prime})\left(b_{S^{\prime}}(s^{\prime})-\sum_{s}b_{2}(s,s^{\prime})\right)$
$\displaystyle+\sum_{s^{\prime}}\lambda_{3S^{\prime}}(s^{\prime})\left(b_{S^{\prime}}(s^{\prime})-\sum_{x^{\prime}}b_{3}(s^{\prime},x^{\prime})\right)$
$\displaystyle+\sum_{x^{\prime}}\lambda_{3X^{\prime}}(x^{\prime})\left(b_{X^{\prime}}(x^{\prime})-\sum_{s^{\prime}}b_{3}(s^{\prime},x^{\prime})\right)$
$\displaystyle+\sum_{x^{\prime}}\lambda_{4}(x^{\prime})\big{(}b_{X^{\prime}}(x^{\prime})-b_{4}(x^{\prime})\big{)}$
$\displaystyle+\sum_{k=1}^{4}\gamma_{k}\left(\sum
b_{k}-1\right)+\sum_{Y\in\\{S,S^{\prime},X^{\prime}\\}}\gamma_{Y}\left(\sum
b_{Y}-1\right)$

where the Lagrange multipliers for the consistency constraints are denoted by
$\lambda$ and the Lagrange multipliers for the normalization constraints by
$\gamma$. The equations for the beliefs at the stationary points (zeroes of
the derivatives of the Lagrangian) are

$\displaystyle b_{1}(s)$ $\displaystyle\ \propto\
f_{1}(s)\,e^{\lambda_{1}(s)}\,,$ $\displaystyle b_{2}(s,s^{\prime})$
$\displaystyle\ \propto\
f_{2}(s,s^{\prime})\,e^{\lambda_{2S}(s)}\,e^{\lambda_{2S^{\prime}}(s^{\prime})}\,,$
$\displaystyle b_{3}(s^{\prime},x^{\prime})$ $\displaystyle\ \propto\
f_{3}(s^{\prime},x^{\prime})\,e^{\lambda_{3S^{\prime}}(s^{\prime})}\,e^{\lambda_{3X^{\prime}}(x^{\prime})}\,,$
$\displaystyle b_{4}(x^{\prime})$ $\displaystyle\ \propto\
f_{4}(x^{\prime})\,e^{\lambda_{4}(x^{\prime})}\,,$ $\displaystyle b_{S}(s)$
$\displaystyle\ \propto\ e^{\lambda_{1}(s)}\,e^{\lambda_{2S}(s)}\,,$
$\displaystyle b_{S^{\prime}}(s^{\prime})$ $\displaystyle\ \propto\
e^{\lambda_{2S^{\prime}}(s^{\prime})}\,e^{\lambda_{3S^{\prime}}(s^{\prime})}\,,$
$\displaystyle b_{X^{\prime}}(x^{\prime})$ $\displaystyle\ \propto\
e^{\lambda_{3X^{\prime}}(x^{\prime})}\,e^{\lambda_{4}(x^{\prime})}\,,$

where the proportionality sign $\propto$ means that the left-hand side results
from normalizing the right hand-side to obtain a probability distribution. By
writing $m_{l}\coloneqq e^{\lambda_{l}}$ for all
$l\in\\{1,2S,2S^{\prime},3S^{\prime},3X^{\prime},4\\}$, we obtain from the
stationarity conditions and the consistency constraints

$\displaystyle m_{2S}(s)\ $ $\displaystyle\propto\ f_{1}(s)$ (36a)
$\displaystyle m_{1}(s)\ $ $\displaystyle\propto\
\sum\nolimits_{s^{\prime}}f_{2}(s,s^{\prime})\,m_{2S^{\prime}}(s^{\prime})$
(36b) $\displaystyle m_{3S^{\prime}}(s^{\prime})\ $ $\displaystyle\propto\
\sum\nolimits_{s}f_{2}(s,s^{\prime})\,m_{2S}(s)$ (36c) $\displaystyle
m_{2S^{\prime}}(s^{\prime})\ $ $\displaystyle\propto\
\sum\nolimits_{x^{\prime}}f_{3}(s^{\prime},x^{\prime})\,m_{3X^{\prime}}(x^{\prime})$
(36d) $\displaystyle m_{4}(x^{\prime})\ $ $\displaystyle \propto\
\sum\nolimits_{s^{\prime}}f_{3}(s^{\prime},x^{\prime})\,m_{3S^{\prime}}(s^{\prime})$
(36e) $\displaystyle m_{3X^{\prime}}(x^{\prime})\ $ $\displaystyle\propto\
f_{4}(x^{\prime})\,.$ (36f)

The update equations for the beliefs in (35) can be obtained by iterating the
equations in (36) and using the stationarity conditions that express the
beliefs in terms of the $m_{l}$. Note that the quantities denoted by $m_{l}$
are usually interpreted as local messages that are sent between the nodes and
factors of the underlying graphical model (Yedidia et al., , 2005), e.g.,
$m_{3S^{\prime}}$ is considered a message sent from node $S^{\prime}$ to
factor $3$, which can be used to determine the message $m_{4}$ from factor $3$
to node $X^{\prime}$ by weighing with $f_{3}$ and summing over $S^{\prime}$,
etc. By this identification, variational inference under the Bethe
approximation is equivalent to belief propagation. While in (36) there is at
most one message that is multiplied to the factor $f_{k}$ before the sum is
taken, in more complex factor graphs, where more than 2 nodes are connected to
a factor, the messages coming in to a factor from the neighboring nodes are
multiplied before they are summed to calculate the outgoing message, which is
why this type of message-passing is also known as the sum-product algorithm.

###  A.2 Details on the example in Fig 8

Here, we are giving additional details on Figure 8 in the article. We consider
the simple example of three possible observations, $x_{1},x_{2},x_{3}$, a
desired distribution $p_{\mathrm{des}}(X^{\prime})=(1/3,1/6,1/2)$, two actions
$a$ with predictive distributions $p(X^{\prime}|A\hskip 1.0pt{=}\hskip
2.0pt1)\hskip 2.0pt{=}\hskip 2.0pt(1,0,0)$ and $p(X^{\prime}|A\hskip
1.0pt{=}\hskip 2.0pt2)\hskip 2.0pt{=}\hskip 2.0pt(0,1/2,1/2)$, and a constant
prior $p_{0}(A)=(1/2,1/2)$. We can consider $p(X^{\prime}|A)$ as a result of
marginalizing the generative model
$p_{0}(X^{\prime},S^{\prime},A)=p_{0}(X^{\prime}|S^{\prime})p_{0}(S^{\prime}|A)p_{0}(A)$
with state distributions $p(S^{\prime}|A\hskip 1.0pt{=}\hskip 2.0pt1)\hskip
2.0pt{=}\hskip 2.0pt(1,0,0)$ and $p(S^{\prime}|A\hskip 1.0pt{=}\hskip
2.0pt2)\hskip 2.0pt{=}\hskip 2.0pt(0,1/2,1/2)$ and an emission probability
$p_{0}(X^{\prime}|S^{\prime})$ that is chosen such that the given
$p(X^{\prime}|A)$ equals
$p(X^{\prime}|A)=\sum_{s^{\prime}}p_{0}(X^{\prime}|s^{\prime})p_{0}(s^{\prime}|A)$.
Suitable emission probabilities have for example the form
$p_{0}(X^{\prime}\hskip 1.0pt{=}\hskip 2.0ptx_{i}|S^{\prime}\hskip
1.0pt{=}\hskip 2.0pts_{j})=M_{ij}(t)$, where

$M(t)=\left(\begin{array}[]{ccc}1&0&0\\\ 0&t&1{-}t\\\
0&1{-}t&t\end{array}\right)$

for all $t\in[0,1]$. Note that the resulting average entropies $\langle
H(p_{0}(S^{\prime}|A\hskip 1.0pt{=}\hskip
2.0pt2))\rangle_{p_{0}(S^{\prime}|A=2)}$ are in the range $[0,1]$ bit for
$A=2$ (always zero for $A=1$), where the extreme values are assumed at
$t\in\\{0,1\\}$ (0 bit) and $t=1/2$ (1 bit).

Furthermore, for the application of Active Inference in Figure 8, we have
considered an exact version of the value function, $Q\hskip 1.0pt{=}\hskip
2.0ptQ_{\mathrm{exact}}$, where the trial distribution $q(S^{\prime}|A)$ is
replaced by the exact predictive distribution $p_{0}(S^{\prime}|A)$. In this
“exact” interpretation, the corresponding action distributions $p(A)\propto
p_{0}(A)e^{Q_{\mathrm{exact}}(A)}$ could then be viewed as defining the ideal
behaviour that is approximated by the variational free energy minimization. In
the Active Inference literature, $p(A)\propto p_{0}(A)e^{Q(A)}$ is considered
a “prior”, because it is viewed as part of the generative model and thus is
part the input to the variational inference process. However, by considering
$Q$ an approximation of $Q_{\mathrm{exact}}$ these distributions can be viewed
as defining the ideal behavior that is approximated by the trial distributions
during free energy minimization and are therefore more in line with the
“posteriors” in other decision-making models (even though the value function
$Q(A)$—and therefore $p(A)$—is presupposed, in constrast to being the result
of some principle).

###  A.3 Surprise minimization

The (informational) surprise or surprisal of a given element $x$ with respect
to a probability distribution $p_{0}(X)$ is defined as $S_{0}\coloneqq{-}\log
p_{0}(x)$, i.e. it is simply a strictly decreasing function of probability
such that outcomes $x$ with low probability have high surprise and outcomes
$x$ with high probability have low surprise. A common statement found in the
literature (Parr and Friston, , 2017) is that variational free energy is an
upper bound on surprise and thus minimizing free energy also minimizes
surprise. This idea originates from the special case of greedy inference with
latent variables, where, for fixed data $x$, the goal is to maximize the
likelihood $p_{\theta}(x)=\sum_{z}p_{\theta}(x,z)$ with respect to a parameter
$\theta$. If the marginalization over the latent variable $Z$ is too hard to
carry out directly, then one might take advantage of the bound

$F(q(Z)\|p_{\theta}(x,Z))\geq-\log p_{\theta}(x)\eqqcolon S_{\theta},$ (37)

i.e. that the variational free energy of $q(Z)$ is an upper bound on the
surprise $S_{\theta}$, which might therefore be reduced by minimizing its
upper bound with respect to $\theta$ as a proxy. In the variational Bayes’
approach to the above inference problem, where $\theta$ is treated as a random
variable $\Theta$, minimization with respect to $\theta$ is replaced by the
minimization with respect to $q(\Theta)$. In this case, the analogous bound to
(37) is

$F(q(Z|\Theta)q(\Theta)\|p_{0}(x,Z,\Theta))\geq-\log\sum_{z}e^{\langle\log
p_{0}(x,z,\Theta)\rangle_{q(\Theta)}},$

where the right-hand side is the minimum of the left-hand side with respect to
$q(Z|\Theta)$. In this sense, variational free energy is generally not a bound
on the surprise $S_{\Theta}$ anymore, but on a log-sum-exp version of it
instead. Nonetheless, also in this Bayesian approach, variational free energy
is an upper bound on the surprise $S_{0}$,

$F(q(Z|\theta)q(\theta)\|p_{0}(x,Z,\Theta))\geq-\log p_{0}(x)=S_{0},$ (38)

where the right-hand side is the minimum of the left-hand side with respect to
both $q(Z|\theta)$ and $q(\theta)$. However, in contrast to (37), there is no
variable left in $S_{0}$ over which one could minimize. Therefore, saying that
minimizing free energy also minimizes surprise (Parr and Friston, , 2017), is
generally only true in the sense that minimizing free energy minimizes an
upper bound on surprise, however surprise itself is not minimized. Instead,
the important fact about (38) is that equality is achieved by the Bayes’
posteriors $q(Z|\Theta)=p_{0}(Z|\Theta,x)$ and $q(\Theta)=p_{0}(\Theta|x)$ as
discussed in Section 3.2.1.

###  A.4 Separation of model and state variables

In $Q$-value Active Inference, action and perception do not optimize the same
variational free energy but two different free energy expressions. This is
motivated from the separation of model variables $M$ and state variables in
standard variational Bayesian inference, where the full free energy can be
split up into a sum of a state free energy $F_{M}$ averaged over models $M$
and a KL term that is independent of state distributions. Optimizing the full
free energy can then be done separately by alternatingly doing perceptual
inference by optimizing $F_{M}$ for each model $M$ and optimizing the full
free energy to find the model distribution $q(M)$. In Active Inference, where
actions $A$ might be thought of analogous to models $M$ in Bayesian inference,
the full free energy is analogously split up into a sum of a state free energy
$F_{A}$ averaged over actions $A$ and a KL term which—in contrast to standard
Bayesian inference—does depend on state distributions. However, Active
Inference essentially ignores this extra $q$-dependency by following the
analogous optimization scheme to Bayesian inference: one alternatingly
optimizes $F_{A}$ with respect to state distributions and then the full free
energy with respect to the action distributions $q(A)$. In particular, this
separation into state and action free energies is not a consequence of
optimizing the full variational free energy, but a deliberate choice made by
Active Inference.

In the following, we discuss in more detail how this separation follows from
optimizing the full free energy in standard Bayesian inference and highlight
how $Q$-value Active Inference adopts the same optimization scheme but by
giving up the optimization of a single variational free energy.

####  A.4.1 Bayesian inference

Consider the case of multiple probabilistic models $p_{m}(X,Z)$ that are
indexed by a label $m$, where each $p_{m}$ describes a different probabilistic
relationship between data $X$ and hidden states $Z$. Given data $X=x$, one
could find the best $m$ by selecting the model with the largest marginal
likelihood $p_{m}(x)=\sum_{z}p_{m}(x,z)$. A popular method to accomplish this
is the basic EM algorithm Dempster et al.,  (1977), where $m$ is optimized
greedily while $Z$ is inferred using Bayesian inference for a given $m$
(either exact or approximate). In a purely Bayesian treatment, one also
assumes a prior distribution over models $p_{0}(M)$, so that the full joint
over data $X$, hidden states $Z$, and models $M$ becomes

$p_{0}(X,Z,M)\coloneqq p_{M}(X,Z)p_{0}(M)\eqqcolon p_{0}(X,Z|M)\,p_{0}(M)\,.$

The Bayes’ posterior $p(M|X)$ can then simply be determined from the Bayes’
posterior $p(Z,M|X)$ through marginalization over $Z$. As discussed in the
article (Section 3.2), if direct Bayesian inference is infeasable then a
variational formulation might be useful, where trial distributions $q(Z,M)$
over the unknown variables $M$ and $Z$ are fitted to the reference
$\phi(Z,M)\coloneqq p_{0}(x,Z,M)$ by minimizing the variational free energy

$F(q\|\phi)=\left\langle\log\frac{q(Z,M)}{p_{0}(x,Z,M)}\right\rangle_{q(Z,M)}\,.$

By writing $q$ and $p_{0}$ in their factorized forms

$\displaystyle q(Z,M)$ $\displaystyle=q(Z|M)q(M),$ $\displaystyle
p_{0}(X,Z,M)$ $\displaystyle=p_{0}(X,Z|M)p_{0}(M)\,,$

the variational free energy can be decomposed as

$\displaystyle F(q\|\phi)$
$\displaystyle=\left\langle\log\frac{q(Z|M)q(M)}{p_{0}(x,Z|M)p_{0}(M)}\right\rangle_{q}$
$\displaystyle=\Big{\langle}\underbrace{\Big{\langle}\log\frac{q(Z|M)}{p_{0}(x,Z|M)}\Big{\rangle}_{q(Z|M)}}_{\eqqcolon
F_{M}}\Big{\rangle}_{q(M)}$
$\displaystyle\quad+\Big{\langle}\log\frac{q(M)}{p_{0}(M)}\Big{\rangle}_{q(M)}$
$\displaystyle=\langle F_{M}\rangle_{q(M)}+D_{\mathrm{KL}}(q(M)\|p_{0}(M))\,.$
(39)

Notably, the minimization of $F$ with respect to $q$ splits up into the
minimization of the free energy over states

$F_{M}=F\big{(}q(Z|M)\big{\|}p_{0}(x,Z|M)\big{)}$ (40)

with respect to $q(Z|M)$, and the minimization of (39) with respect to $q(M)$.
In particular, the inference over models and states, $(M,Z)$, separates into
inference over hidden states for each model, which determines $F_{M}$ for each
$M$, and inference over $M$.

####  A.4.2 Active Inference

In $Q$-value Active Inference, action selection is treated similarly to model
selection in Bayesian inference discussed in the previous section. However,
the KL term in (39) also depends on trial distributions over states, which
means that a separation into action and state variables analogous to the
separation in model selection is not possible when considering the problem of
action and perception as the minimization of a single free energy functional,
which is usually the conceptual starting point in the Active Inference
literature Friston,  (2010, 2018).

More precisely, as discussed in Section 5, the reference function $\phi$ that
enters the variational free energy in $Q$-value Active Inference is
constructed from a given probabilistic model $p_{0}$ and a value function $Q$
by replacing the fixed prior $p_{0}(A)$ over actions with the modified
distribution
$\tilde{p}_{0}(A)\coloneqq\frac{1}{\mathcal{Z}}\,p_{0}(A)e^{Q(A)}$. As can be
seen exemplarily in the one-step case in Equation (26), the value function $Q$
depends on trial distributions $q$ over hidden states and therefore
$\tilde{p}_{0}(A)$ depends on $q$ as well. Despite this dependency, the total
free energy $F(q\|\phi)$ can still be written as

$\displaystyle F(q\|\phi)$
$\displaystyle=\left\langle\log\frac{q(X^{\prime},\mathbf{S}|A)q(A)}{p_{0}(x,X^{\prime},\mathbf{S}|A)\tilde{p}_{0}(A)}\right\rangle_{q}$
$\displaystyle=\langle
F_{A}\rangle_{q(A)}+D_{\mathrm{KL}}\big{(}q(A)\|\tilde{p}_{0}(A)\big{)}$ (41)

with

$F_{A}\coloneqq
F\big{(}q(X^{\prime},\mathbf{S}|A)\big{\|}p_{0}(x,X^{\prime},\mathbf{S}|A)\big{)}\,.$
(42)

in the case of the one-step example of Section 5.2. Equations (41) and (42)
are analogous to Equations (39) and (40), respectively. However, when
optimizing the full free energy $F(q\|\phi)$ with respect to the factor
$q(X^{\prime},\mathbf{S}|A)$, one would have to consider both terms in the
decomposition (41), since, unlike $p_{0}(M)$ in the previous section, here
$\tilde{p}_{0}(A)$ does depend on trial distributions over states (the factor
$q(S^{\prime}|A)$). It should be noted that this dependency is non-linear and
non-local, and therefore a closed-form solution cannot be derived (cf. $(ii)$
in Section 5.3).

In Active Inference, this complication is avoided by simply ignoring the
$q$-dependency of $Q$ when deriving the update equations, or, put differently,
one optimizes two different free energies for perception and action: one first
optimizes $F_{A}$ with respect to state distributions for each action $A$ and
then one optimizes the full free energy (41) with respect to $q(A)$. This is
in analogy to Bayesian model selection of the previous section, where this
separation was a consequence of the minimization of the full free energy.
However, here, due to the extra dependency of $\tilde{p}_{0}(A)$ on $q$, it is
not a consequence but a choice made by Active Inference. This means that one
no longer does variational inference over the combined set of states and
actions, but variational inference over states with free energy $F_{A}$ and
variational inference over actions with free energy (41). In particular, there
is not a single free energy that is optimized by both perception and action,
but two different ones.

##  Appendix S Supplementary Material

The following ancillary files are provided as supplementary material:

###  S.1 Notebook: Comparison of different formulations of Active Inference

A detailed comparison of the different formulations of Active Inference found
in the literature (2013-2018), including their mean-field and exact solutions
in the general case of arbitrary many time steps.

###  S.2 Notebook: Grid world simulations

We provide implementations of the models discussed in this article in a grid
world environment, both as a rendered html file as well as a jupyter notebook
that is available on github.