# Improved bounds for cross-Sperner systems

Natalie Behague11footnotemark: 1 Department of Mathematics and Statistics,
University of Victoria.
E-mail: {nbehague,akuperus,nmorrison,ashnawright} @uvic.ca.Research supported
by a PIMS Postdoctoral Fellowship Akina Kuperus11footnotemark: 1 Research
supported by NSERC CGS-M. Natasha Morrison11footnotemark: 1 Research supported
by NSERC Discovery Grant RGPIN-2021-02511 and NSERC Early Career Supplement
DGECR-2021-00047 Ashna Wright11footnotemark: 1 Research supported by NSERC
USRA.

###### Abstract

A collection of families
$(\mathcal{F}_{1},\mathcal{F}_{2},\cdots,\mathcal{F}_{k})\in\mathcal{P}([n])^{k}$
is _cross-Sperner_ if there is no pair $i\not=j$ for which some
$F_{i}\in\mathcal{F}_{i}$ is comparable to some $F_{j}\in\mathcal{F}_{j}$. Two
natural measures of the ‘size’ of such a family are the sum
$\sum_{i=1}^{k}|\mathcal{F}_{i}|$ and the product
$\prod_{i=1}^{k}|\mathcal{F}_{i}|$. We prove new upper and lower bounds on
both of these measures for general $n$ and $k\geq 2$ which improve
considerably on the previous best bounds. In particular, we construct a rich
family of counterexamples to a conjecture of Gerbner, Lemons, Palmer, Patkós,
and Szécsi from 2011.

##  1 Introduction

A family $\mathcal{F}\subseteq\mathcal{P}([n])$ is an _antichain_ (also known
as a _Sperner_ family) if for all distinct $F,G\in\mathcal{F}$, neither
$F\subseteq G$ nor $G\subseteq F$ (i.e. $F$ and $G$ are _incomparable_). One
of the principal results in extremal combinatorics is Sperner’s theorem [22],
which states that the largest size of an antichain in $\mathcal{P}([n])$ is
$\binom{n}{\left\lfloor n/2\right\rfloor}$. This can be seen to be tight by
taking a ‘middle layer’, that is $\mathcal{F}=\binom{[n]}{\left\lfloor
n/2\right\rfloor}$ or $\mathcal{F}=\binom{[n]}{\lceil n/2\rceil}$.

It is natural to consider a generalisation of Sperner’s theorem to multiple
families of sets. For $k\geq 2$, say that a collection of non-empty families
$(\mathcal{F}_{1},\mathcal{F}_{2},\cdots,\mathcal{F}_{k})\in\mathcal{P}([n])^{k}$,
is _cross-Sperner_ if for all $i\not=j$, the sets $F_{i}$ and $F_{j}$ are
incomparable for any $F_{i}\in\mathcal{F}_{i}$ and $F_{j}\in\mathcal{F}_{j}$.
(We may also write that
$(\mathcal{F}_{1},\mathcal{F}_{2},\cdots,\mathcal{F}_{k})$ is _cross-Sperner
in_ $\mathcal{P}([n])$.) The study of such objects goes back to the 1970s when
Seymour [21] deduced from a result of Kleitman [14] that a cross-Sperner pair
$(\mathcal{F},\mathcal{G})$ in $\mathcal{P}([n])$ satisfies

$|\mathcal{F}|^{1/2}+|\mathcal{G}|^{1/2}\leq 2^{n/2},$ (1.1)

hence resolving a related conjecture of Hilton (see [3]). Equality is obtained
in Seymour’s bound precisely when the minimal sets of $\mathcal{F}$ are
pairwise disjoint from the minimal sets intersecting each set of
$\mathcal{G}$. A broad spectrum of research concerning discrete objects with
‘Sperner-like’ properties have since emerged (see, for example, [1, 2, 4, 5,
7, 10, 11, 12, 13, 19, 23]). Many related results concern families satisfying
both Sperner-type properties, and additional properties such as conditions on
intersections (see, for example [6, 15, 17, 18, 20]).

Let $\mathcal{F}=(\mathcal{F}_{1},\mathcal{F}_{2},\cdots,\mathcal{F}_{k})$ be
cross-Sperner in $\mathcal{P}([n])$. There are several natural measures of the
‘size’ of such a family. These include the sum
$\sum_{i=1}^{k}|\mathcal{F}_{i}|$ and the product
$\prod_{i=1}^{k}|\mathcal{F}_{i}|$. The general study of these quantities was
initiated by Gerbner, Lemons, Palmer, Patkós, and Szécsi [8], who essentially
proved best possible bounds on cross-Sperner _pairs_ of families.

Concerning the product, they gave a direct proof that a cross-Sperner pair
$(\mathcal{F},\mathcal{G})$ in $\mathcal{P}([n])$ satisfies

$|\mathcal{F}|\cdot|\mathcal{G}|\leq 2^{2n-4}.$ (1.2)

To see that this bound is tight, consider $\mathcal{F}=\\{F\subseteq[n]:1\in
F,n\not\in F\\}$ and $\mathcal{G}=\\{G\subseteq[n]:1\not\in G,n\in G\\}$. It
is straightforward to see that the bound in (1.2) can also be obtained as a
direct consequence of (1.1) via the AM–GM inequality111Observe that
$2\left(|\mathcal{F}||\mathcal{G}|\right)^{1/4}\leq|\mathcal{F}|^{1/2}+|\mathcal{G}|^{1/2}\leq
2^{n/2}$. .

First, let us focus on product bounds for $k\geq 3$. It is convenient to
define

$\pi(n,k):=\max\left\\{\prod_{i=1}^{k}|\mathcal{F}_{i}|:(\mathcal{F}_{1},\mathcal{F}_{2},\cdots,\mathcal{F}_{k})\text{
is cross-Sperner in }\mathcal{P}([n])\right\\}.$

In [8], it was observed that (1.1) can be used to obtain the upper bound
$\pi(n,k)\leq 2^{k(n-2)}$. For $k>4$, an improved bound of
$\pi(n,k)\leq\left(\frac{2^{n}}{k}\right)^{k}$ can be obtained by a simple
application of the AM-GM inequality.222Similarly to above, we have
$\left(\prod_{i=1}^{k}|\mathcal{F}_{i}|\right)^{\frac{1}{k}}\leq\frac{\sum_{i=1}^{k}|\mathcal{F}_{i}|}{k}\leq\frac{2^{n}}{k}$.
Gerbner, Lemons Palmer, Patkós, and Szécsi [8] conjectured that $\pi(n,k)\leq
2^{k(n-\ell^{*})}$, where $\ell^{*}=\ell^{*}(k)$ is the least positive integer
such that $\binom{\ell^{*}}{\left\lfloor\ell^{*}/2\right\rfloor}\geq k$. They
described a construction which provides a matching lower bound to their
conjecture. Let $A_{1},\ldots,A_{k}$ be an antichain in $\mathcal{P}([l])$ and
let $(\mathcal{F}_{1},\ldots,\mathcal{F}_{k})\in\mathcal{P}([n])$ be defined
by $\mathcal{F}_{i}:=\\{F\in[n]:F\cap[\ell]=A_{i}\\}$.

Our first theorem strongly disproves this conjecture.

theoremprodl Let $n$ and $k\geq 2$ be integers. For $n$ sufficiently large,

$\left(\frac{2^{n}}{ek}\right)^{k}\leq\pi(n,k).$

A crude application of Stirling’s approximation yields that
$\ell^{*}(k)=\omega(\log k)$. So in particular, there is a function $g(k)$
tending to infinity with $k$ such that $2^{k(n-\ell^{*})}=O\left(2^{kn}(k\cdot
g(k))^{-k}\right)$. Therefore our lower bound is exponentially larger than the
conjectured $2^{k(n-\ell^{*})}$.

We also improve the previous best known upper bound by a factor of $2^{k}$.
theoremprodu Let $n$ and $k\geq 2$ be integers. Then

$\pi(n,k)\leq\left(\frac{2^{n}}{k^{2}}\right)^{k}\left\lfloor\frac{k}{2}\right\rfloor^{\left\lfloor
k/2\right\rfloor}\left\lceil\frac{k}{2}\right\rceil^{\left\lceil
k/2\right\rceil}$

Regarding bounds on the sum, in [8] it is shown that for $n$ sufficiently
large, a cross-Sperner pair in $\mathcal{P}([n])$ satisfies

$|\mathcal{F}|+|\mathcal{G}|\leq 2^{n}-2^{\left\lceil
n/2\right\rceil}-2^{\left\lfloor n/2\right\rfloor}+2.$ (1.3)

This is tight, which can be seen by taking
$\mathcal{F}=\\{1,2,\ldots,\left\lfloor n/2\right\rfloor\\}$ and letting
$\mathcal{G}$ be all subsets of $[n]$ that are not comparable to $F$. Gerbner,
Lemons Palmer, Patkós, and Szécsi [8] also asked about bounds for the sum for
general $k$. Analogously to in the product case, define

$\sigma(n,k):=\max\left\\{\sum_{i=1}^{k}|\mathcal{F}_{i}|:(\mathcal{F}_{1},\mathcal{F}_{2},\cdots,\mathcal{F}_{k})\text{
is cross-Sperner in }\mathcal{P}([n])\right\\}.$

In our next theorem, we determine upper and lower bounds on $\sigma(n,k)$.

######  Theorem 1.4.

Let $n,k$ be integers with $n\geq 2k$. Then

$2^{n}-\frac{3}{\sqrt{2}}\sqrt{2^{n}k}+2(k-1)~{}\leq~{}\sigma(n,k)~{}\leq~{}2^{n}-2\sqrt{2^{n}(k-1)}+2(k-1).$

When $k$ is a power of 2 and $n-\log_{2}{k}$ is even, we can further improve
the lower bound to $2^{n}-2\sqrt{2^{n}k}+2(k-1)$, which is extremely close to
the upper bound.

In order to prove Theorem 1 and the upper bound in Theorem 1.4, we exploit a
connection between $\sigma(n,k)$ and the _comparability number_ of a set
(given in Section 2). In doing so, we recover a simple proof of (1.3) (see
Theorem 2.4) that holds for _all_ $n$ (recall the result of [8] holds for
large $n$).

The article is structured as follows. We introduce the comparability number in
Section 2 and provide a lower bound (Theorem 2.3) that will be used in the
proofs of Theorems 1 and 1.4. In Section 3 we prove Theorems 1 and 1 bounding
the product. In Section 4 we prove Theorem 1.4 bounding the sum. We conclude
in section 5 with some discussion and open questions.

##  2 Minimizing Comparability

Given a family $\mathcal{F}\subseteq\mathcal{P}([n])$ define the
_comparability number of_ $\mathcal{F}$ to be

$c(n,\mathcal{F}):=|\\{X\subseteq[n]:X\text{ is comparable to some
}A\in\mathcal{F}\\}|.$

When the setting is clear from context, we may write $c(\mathcal{F})$ for
$c(n,\mathcal{F})$. Define

$c(n,m)=\min\\{c(n,\mathcal{F}):\mathcal{F}\subseteq\mathcal{P}([n]),|\mathcal{F}|=m\\}.$

As noted in [8], there is a direct relationship between $\sigma(n,2)$ and
$c(n,m)$. Observe that if $(\mathcal{F},\mathcal{G})$ is cross-Sperner in
$\mathcal{P}([n])$, we have

$|\mathcal{F}|+|\mathcal{G}|\leq|\mathcal{F}|+2^{n}-c(n,|\mathcal{F}|),$

as any set incomparable to every member of $\mathcal{F}$ can be added to
$\mathcal{G}$. We will use analogous ideas in Section 4 to provide upper
bounds on $\sigma(n,k)$ for $k\geq 3$.

Our goal in this section is to find a lower bound on $c(n,m)$. We begin by
showing that families that minimize comparability are ‘convex’.

######  Lemma 2.1.

Let $\mathcal{F}\subseteq\mathcal{P}([n])$. Let
$\mathcal{F}^{\prime}:=\mathcal{F}\cup\\{Z\in\mathcal{P}([n]):X\subseteq
Z\subseteq Y,\text{ where }X,Y\in\mathcal{F}\\}$. Then
$c(\mathcal{F}^{\prime})=c(\mathcal{F})$.

###### Proof of Lemma 2.1.

Let $Z$ be a set such that $X\subseteq Z\subseteq Y$, for some
$X,Y\in\mathcal{F}$. Observe that any set in $\mathcal{P}([n])$ that is
comparable to $Z$ is either comparable to $X$ or to $Y$. So $c(\mathcal{F}\cup
Z)=c(\mathcal{F})$. Repeatedly applying this observation gives the result. ∎

Theorem 2.3 can now be deduced from the Harris-Kleitman inequality. Recall
that a family $\mathcal{U}\subseteq\mathcal{P}([n])$ is an _upset_ if for all
$X\in\mathcal{U}$, if $X\subseteq Y$, then $Y\in\mathcal{U}$. A family
$\mathcal{D}\subseteq\mathcal{P}([n])$ is a _downset_ if for all
$X\in\mathcal{D}$, if $Y\subseteq X$, then $Y\in\mathcal{D}$.

######  Lemma 2.2 (Harris-Kleitman Inequality [14]).

Let $\mathcal{U}\subseteq\mathcal{P}([n])$ be an upset and
$\mathcal{D}\subseteq\mathcal{P}([n])$ be a downset. Then

$\frac{|\mathcal{U}\cap\mathcal{D}|}{2^{n}}\leq\frac{|\mathcal{U|}}{2^{n}}\cdot\frac{|\mathcal{D}|}{2^{n}}.$

We will apply Lemma 2.2 to prove a lower bound on $c(n,m)$. For convenience,
for a family $\mathcal{F}\subseteq\mathcal{P}([n])$, define

$\mathcal{U}_{\mathcal{F}}=\\{X\in\mathcal{P}([n]):F\subseteq X\text{ for some
}F\in\mathcal{F}\\}$

and

$\mathcal{D}_{\mathcal{F}}=\\{X\in\mathcal{P}([n]):X\subseteq F\text{ for some
}F\in\mathcal{F}\\}.$

######  Theorem 2.3.

For $1\leq m\leq 2^{n}$,

$c(n,m)\geq 2^{n/2+1}\sqrt{m}-m.$

###### Proof.

Let $\mathcal{F}\subseteq\mathcal{P}([n])$ be such that $|\mathcal{F}|=m$ and
$c(\mathcal{F})=c(n,m)$. We may assume $\mathcal{F}$ is convex. If not, by
Lemma 2.1 we may add sets to make it convex and then remove minimal or maximal
elements to obtain $\mathcal{F}^{\prime}$ such that
$|\mathcal{F}^{\prime}|=|\mathcal{F}|$ and $c(\mathcal{F}^{\prime})\leq
c(\mathcal{F})$. Note that
$c(\mathcal{F})=|\mathcal{U}_{\mathcal{F}}|+|\mathcal{D}_{\mathcal{F}}|-|\mathcal{U}_{\mathcal{F}}\cap\mathcal{D}_{\mathcal{F}}|$.
Since $\mathcal{F}$ is convex,
$|\mathcal{F}|=|\mathcal{U}_{\mathcal{F}}\cap\mathcal{D}_{\mathcal{F}}|=m$.
Using the AM-GM inequality we get

$c(\mathcal{F})\geq
2\sqrt{|\mathcal{U}_{\mathcal{F}}||\mathcal{D}_{\mathcal{F}}|}-m.$

Since $\mathcal{U}_{\mathcal{F}}$ is an upset and $\mathcal{D}_{\mathcal{F}}$
is a downset, we apply Lemma 2.2 to get

$c(\mathcal{F})\geq 2\sqrt{2^{n}m}-m=2^{\frac{n}{2}+1}\sqrt{m}-m,$

as required. ∎

It is now a simple consequence of Theorem 2.3 to see that (1.3) holds for all
$n$.

######  Theorem 2.4.

Let $(\mathcal{F},\mathcal{G})$ be cross-Sperner in $\mathcal{P}([n])$. Then

$|\mathcal{F}|+|\mathcal{G}|\leq 2^{n}-2^{\left\lfloor
n/2\right\rfloor}-2^{\left\lceil n/2\right\rceil}+2.$

###### Proof.

Let $(\mathcal{F},\mathcal{G})\in\mathcal{P}([n])^{2}$ be a cross-Sperner
pair. Suppose $|\mathcal{F}|=m$. Since $\mathcal{F},\mathcal{G}\neq\emptyset$,
$1\leq m\leq 2^{n}-1$. Moreover, we may assume without loss of generality that
$|\mathcal{F}|\leq|\mathcal{G}|$. We know $|\mathcal{F}||\mathcal{G}|\leq
2^{2n-4}$ by (1.2), which implies that $m\leq 2^{n-2}$.

Then,
$c(\mathcal{F})\geq|\mathcal{U}_{\mathcal{F}}|+|\mathcal{D}_{\mathcal{F}}|-m$
and $|\mathcal{G}|\leq
2^{n}-c(\mathcal{F})\leq|\mathcal{U}_{\mathcal{F}}|-|\mathcal{D}_{\mathcal{F}}|+m$.
Thus

$|\mathcal{F}|+|\mathcal{G}|\leq
2^{n}-|\mathcal{U}_{\mathcal{F}}|-|\mathcal{D}_{\mathcal{F}}|+2m.$ (2.5)

We have the following two cases.

######  Case 1:

Suppose $m=1$. Since $\mathcal{F}$ only consists of one set, say $F$, we have
$\mathcal{U}_{\mathcal{F}}=2^{n-|F|}$ and $\mathcal{D}_{\mathcal{F}}=2^{|F|}$.
So $|\mathcal{U}_{\mathcal{F}}||\mathcal{D}_{\mathcal{F}}|=2^{n}$, which, by
AM-GM gives $|\mathcal{U}_{\mathcal{F}}|+|\mathcal{D}_{\mathcal{F}}|\geq
2^{n/2+1}\geq 2^{\left\lfloor n/2\right\rfloor}+2^{\left\lceil
n/2\right\rceil}$. So (2.5) yields

$|\mathcal{F}|+|\mathcal{G}|\leq 2^{n}-2^{\left\lfloor
n/2\right\rfloor}-2^{\left\lceil n/2\right\rceil}+2,$

as required. This completes the case $m=1$.

######  Case 2:

Now suppose $m\geq 2$. By Theorem 2.3,
$|\mathcal{U}_{\mathcal{F}}|+|\mathcal{D}_{\mathcal{F}}|\geq
2^{\frac{n}{2}+1}\sqrt{m}$, so Equation (2.5) gives

$|\mathcal{F}|+|\mathcal{G}|\leq 2^{n}-2^{\frac{n}{2}+1}\sqrt{m}+2m.$

By differentiation with respect to $m$ we see that the expression on the
right-hand side is decreasing in the range $2\leq m\leq 2^{n-2}$. It is
therefore maximized at $m=2$, where we have

$2^{n}-2^{\frac{n}{2}+1}\sqrt{m}+2m=2^{n}-2^{\frac{n+3}{2}}+4.$

Note that for all $n\geq 2$,

$2^{\frac{n+3}{2}}-4\geq 2^{\left\lfloor n/2\right\rfloor}+2^{\left\lceil
n/2\right\rceil}-2.$

This implies that $2^{n}-2^{\left\lfloor n/2\right\rfloor}-2^{\left\lceil
n/2\right\rceil}+2\geq 2^{n}-2^{\frac{n}{2}+1}\sqrt{m}+2m$ for all $2\leq
m\leq 2^{n-2}$ and $n\geq 2$. This completes the case $m\geq 2$.

We conclude that $|\mathcal{F}|+|\mathcal{G}|\leq 2^{n}-2^{\left\lfloor
n/2\right\rfloor}-2^{\left\lceil n/2\right\rceil}+2$, as desired. ∎

##  3 Bounding $\pi(n,k)$

The goal of this section is to prove Theorems 1 and 1.

###  3.1 Lower Bound on $\pi(n,k)$

Theorem 1 follows directly from the following (slightly stronger) statement.

######  Lemma 3.1.

Let $n,k$ be integers with $k\geq 2$ and $n>k\log_{2}{k}+k$. Then

$\pi(n,k)\geq\left(\left(\frac{1}{k}-\frac{1}{2^{\left\lfloor
n/k\right\rfloor}}\right)\left(1-\frac{1}{k}\right)^{k-1}\right)^{k}2^{kn}$

###### Proof.

Partition $[n]$ into $k$ parts $A_{1},A_{2},\cdots,A_{k}$ each of size
$\left\lfloor\frac{n}{k}\right\rfloor$ or
$\left\lceil\frac{n}{k}\right\rceil$. For each $1\leq i\leq k$, take
$\mathcal{X}_{i}$ to be an initial segment of colex in $\mathcal{P}(A_{i})$
such that $|\mathcal{X}_{i}|=\lambda_{i}2^{|A_{i}|}$ for some
$0<\lambda_{i}<1$. Set
$\mathcal{Y}_{i}:=\mathcal{P}(A_{i})\setminus\mathcal{X}_{i}$. Now we
construct a cross-Sperner system
$(\mathcal{F}_{1},\mathcal{F}_{2},\cdots,\mathcal{F}_{k})$. Define

$\displaystyle\mathcal{F}_{i}:=\\{F\in\mathcal{P}([n]):F\cap
A_{i}\in\mathcal{X}_{i},F\cap A_{j}\in\mathcal{Y}_{j}\text{ for all }j\neq
i\\}.$

Refer to Example 3.4 for an example of this construction.

To see that $(\mathcal{F}_{1},\mathcal{F}_{2},\cdots,\mathcal{F}_{k})$ is
cross-Sperner in $\mathcal{P}([n])$, consider $S\in\mathcal{F}_{i}$ and
$T\in\mathcal{F}_{j}$. We must show that $S$ and $T$ are incomparable. If
$S\subseteq T$. Then $S\cap A_{j}\subseteq T\cap A_{j}$, so there is some
$Y\in\mathcal{Y}_{j}$ and $X\in\mathcal{X}_{j}$ such that $Y\subseteq X$, a
contradiction. Analogously, we see that $T$ cannot be a subset of $S$. Hence
$(\mathcal{F}_{1},\mathcal{F}_{2},\cdots,\mathcal{F}_{k})$ is cross-Sperner as
required.

Observe that

$|\mathcal{F}_{i}|=|\mathcal{X}_{i}|\prod_{j\neq i}|\mathcal{Y}_{j}|,$

and so

$\pi(n,k)\geq\prod_{i=1}^{k}|\mathcal{F}_{i}|=\prod_{i=1}^{k}\left(|\mathcal{X}_{i}|\prod_{j\neq
i}|\mathcal{Y}_{j}|\right).$

To complete the proof of Lemma 3.1 it remains to optimise the sizes of the
$\lambda_{i}$. We have

$|\mathcal{F}_{i}|=\lambda_{i}2^{|A_{i}|}\prod_{j\neq
i}(1-\lambda_{j})2^{|A_{j}|}=\lambda_{i}2^{|A_{1}|+|A_{2}|+\cdots|A_{k}|}\prod_{j\neq
i}(1-\lambda_{j})=\lambda_{i}2^{n}\prod_{j\neq i}(1-\lambda_{j}).$

So

$\prod_{i=1}^{k}|\mathcal{F}_{i}|=\left(\prod_{i=1}^{k}\lambda_{i}(1-\lambda_{i})^{k-1}\right)2^{kn}$
(3.2)

For each $1\leq k\leq i$, set
$\lambda_{i}=\frac{1}{2^{|A_{i}|}}\left\lfloor\frac{2^{|A_{i}|}}{k}\right\rfloor$.
We have

$\frac{1}{k}-\frac{1}{2^{\left\lfloor
n/k\right\rfloor}}\leq\frac{1}{k}-\frac{1}{2^{|A_{i}|}}\leq\lambda_{i}\leq\frac{1}{k}.$

For $n>k\log_{2}{k}+k$ we have $2^{-\left\lfloor n/k\right\rfloor}\leq
2^{-(n/k-1)}<\frac{1}{k}$ and so $\lambda_{i}$ is not zero. Therefore, with
this choice of $\lambda_{i}$ we get

$\prod_{i=1}^{k}|\mathcal{F}_{i}|\geq\left(\left(\frac{1}{k}-\frac{1}{2^{\left\lfloor
n/k\right\rfloor}}\right)\left(1-\frac{1}{k}\right)^{k-1}\right)^{k}2^{kn},$

as required. ∎

######  Remark 3.3:

Note that if $k$ is a power of $2$, in the proof of Lemma 3.1 we have
$\lambda_{i}=\frac{1}{k}$ for all $1\leq i\leq k$. Therefore in this case we
can eliminate the $-\frac{1}{2^{\left\lfloor n/k\right\rfloor}}$ term.

For clarity, we provide an example of the construction given in Lemma 3.1.

######  Example 3.4.

Let $n=6$ and $k=3$. Partition $[6]$ into

$A_{1}=\\{1,2\\},A_{2}=\\{3,4\\},A_{3}=\\{5,6\\}.$

Then let

$\displaystyle\mathcal{X}_{1}=\\{\emptyset,\\{1\\}\\}$
$\displaystyle\mathcal{X}_{2}=\\{\emptyset,\\{3\\}\\}$
$\displaystyle\mathcal{X}_{3}=\\{\emptyset,\\{5\\}\\}.$

So

$\displaystyle\mathcal{Y}_{1}=\\{\\{2\\},\\{1,2\\}\\}$
$\displaystyle\mathcal{Y}_{2}=\\{\\{4\\},\\{3,4\\}\\}$
$\displaystyle\mathcal{Y}_{3}=\\{\\{6\\},\\{5,6\\}\\}.$

Then we construct our cross-Sperner system to be

$\displaystyle\mathcal{F}_{1}=\\{\\{4,6\\},\\{4,5,6\\},\\{3,4,6\\},\\{3,4,5,6\\},\\{1,4,6\\},\\{1,4,5,6\\},\\{1,3,4,6\\},\\{1,3,4,5,6\\}\\}$
$\displaystyle\mathcal{F}_{2}=\\{\\{2,6\\},\\{2,5,6\\},\\{2,3,6\\},\\{2,3,5,6\\},\\{1,2,6\\},\\{1,2,5,6\\},\\{1,2,3,6\\},\\{1,2,3,5,6\\}\\}$
$\displaystyle\mathcal{F}_{3}=\\{\\{2,4\\},\\{2,4,5\\},\\{2,3,4\\},\\{2,3,4,5\\},\\{1,2,4\\},\\{1,2,4,5\\},\\{1,2,3,4\\},\\{1,2,3,4,5\\}\\}.$

We now deduce Theorem 1 (restated below for convenience) from Lemma 3.1. *

###### Proof.

Take $n$ sufficiently large so that

$\frac{1}{2^{\left\lfloor
n/k\right\rfloor}}\leq\frac{1}{k}-\frac{1}{ek}\left(1+\frac{1}{k-1}\right)^{k-1}=\frac{1}{ek}\left(e-\left(1+\frac{1}{k-1}\right)^{k-1}\right).$

This is possible as $\left(1+\frac{1}{k-1}\right)^{k-1}$ tends to $e$ from
below. Substituting this into Lemma 3.1, we see that

$\pi(n,k)\geq\left(\frac{1}{ek}\left(1+\frac{1}{k-1}\right)^{k-1}\left(1-\frac{1}{k}\right)^{k-1}\right)^{k}2^{kn}=\left(\frac{1}{ek}\right)^{k}2^{kn}.$

∎

###  3.2 Upper Bound on $\pi(n,k)$

The goal of this subsection is to prove Theorem 1, restated below for
convenience. *

We will use the following observation.

######  Lemma 3.5.

Let $1\leq j<k$ and let
$(\mathcal{F}_{1},\mathcal{F}_{2},\ldots,\mathcal{F}_{k})\subseteq\mathcal{P}([n])^{k}$
be cross-Sperner. Then
$\left(\bigcup_{i=1}^{j}\mathcal{F}_{i},\bigcup_{i=j+1}^{k}\mathcal{F}_{i}\right)$
is cross-Sperner in $\mathcal{P}([n])$.

###### Proof.

Suppose for contradiction that
$\left(\bigcup_{i=1}^{j}\mathcal{F}_{i},\bigcup_{i=j+1}^{k}\mathcal{F}_{i}\right)$
is not cross-Sperner. Then there exists some
$X\in\bigcup_{i=1}^{j}\mathcal{F}_{i}$ and
$Y\in\bigcup_{i=j+1}^{k}\mathcal{F}_{i}$ such that $X\subseteq Y$ or
$Y\subseteq X$. Since $X\in\mathcal{F}_{i}$ for some $1\leq i\leq j$, and
$Y\in\mathcal{F}_{t}$ for some $j+1\leq t\leq k$ we deduce that
$(\mathcal{F}_{1},\mathcal{F}_{2},\ldots,\mathcal{F}_{k})$ is not cross-
Sperner, a contradiction. ∎

We now use Lemma 3.5, along with Theorem 2.3, to give an upper bound on
$\pi(n,k)$.

###### Proof of Theorem 1.

Suppose $(\mathcal{F}_{1},\mathcal{F}_{2},\cdots,\mathcal{F}_{k})$ is cross-
Sperner in $\mathcal{P}([n])$. Let $a=\left\lfloor
k/2\right\rfloor,b=\left\lceil k/2\right\rceil$, and observe that $a+b=k$. Let
$\mathcal{G}=\cup_{i=1}^{a}\mathcal{F}_{i}$ and
$\mathcal{H}=\cup_{a+1}^{k}\mathcal{F}_{i}$. Notice that
$(\mathcal{G},\mathcal{H})\subseteq\mathcal{P}([n])^{2}$ is cross-Sperner by
Lemma 3.5, so if $|\mathcal{G}|=m$, then $|\mathcal{H}|\leq 2^{n}-c(n,m)$.
Moreover, $\prod_{i=1}^{a}|\mathcal{F}_{i}|\leq\left(\frac{m}{a}\right)^{a}$
and
$\prod_{j=a+1}^{k}|\mathcal{F}_{j}|\leq\left(\frac{2^{n}-2^{n/2+1}\sqrt{m}+m}{b}\right)^{b}$
since each product is maximized when the families are of equal sizes. Thus,

$\prod_{i=1}^{k}|\mathcal{F}_{i}|=\prod_{i=1}^{a}|\mathcal{F}_{i}|\prod_{j=a+1}^{k}|\mathcal{F}_{j}|\leq\left(\frac{m}{a}\right)^{a}\left(\frac{2^{n}-2^{n/2+1}\sqrt{m}+m}{b}\right)^{b}:=h(m).$
(3.6)

To find an upper bound on the left hand side of (3.6), we differentiate with
respect to $m$ to find the value of $m$ that maximises the right hand side.

$\frac{d}{dm}h(m)=\left(\frac{m}{a}\right)^{a}\left(\frac{(2^{n/2}-\sqrt{m})^{2}}{b}\right)^{b}(a(\sqrt{m}-2^{n/2})+b\sqrt{m})(m^{3/2}-m2^{n/2})^{-1}.$

Setting this equal to zero yields
$m\in\\{0,2^{n},\frac{a^{2}2^{n}}{k^{2}}\\}$. A simple calculation shows that
(3.6) is maximized when $m=\frac{a^{2}2^{n}}{k^{2}}$. Thus

$\prod_{i=1}^{k}|\mathcal{F}_{i}|\leq\left(\frac{2^{n}}{k^{2}}\right)^{k}a^{a}b^{b}=\left(\frac{2^{n}}{k^{2}}\right)^{k}\left\lfloor\frac{k}{2}\right\rfloor^{\left\lfloor
k/2\right\rfloor}\left\lceil\frac{k}{2}\right\rceil^{\left\lceil
k/2\right\rceil},$

as required. ∎

Note that for $k$ even, the upper bound given by Theorem 1 is
$\left(\frac{2^{n}}{2k}\right)^{k}.$ For $k$ odd, it is not hard to check that
the upper bound is less than
$\left(1+\frac{1}{k}\right)\left(\frac{2^{n}}{2k}\right)^{k}.$

##  4 Bounding $\sigma(n,k)$

The goal of this section is to prove Theorem 1.4.

###  4.1 Lower Bound on $\sigma(n,k)$

For our proof of the lower bound in Theorem 1.4 we need the following counting
lemma.

######  Lemma 4.1.

Let $\mathcal{A}:=\\{F_{1},F_{2},\cdots F_{k-1}\\}$ be an antichain in
$\mathcal{P}([n])$ where $F_{i}:=\\{i\\}\cup\\{n-\ell+1,\ldots,n\\}$. Then
$c(\mathcal{A})=k2^{\ell}+2^{n-\ell}\left(1-\frac{1}{2^{k-1}}\right)-(k-1).$

###### Proof.

For each $i$, let $\mathcal{S}_{i}$ be the collection of sets comparable to
$F_{i}$. For ease of notation, let $G:=\\{n-\ell+1,\ldots,n\\}$ Observe that

$|\mathcal{S}_{i}|=|\mathcal{U}_{F_{i}}\cup\mathcal{D}_{F_{i}}|=2^{\ell+1}+2^{n-\ell-1}-1,$
(4.2)

since $|F_{i}|=\ell+1$ and
$\mathcal{U}_{F_{i}}\cap\mathcal{D}_{F_{i}}=\\{F_{i}\\}$.

Note that for each $i>1$, we have

$\mathcal{D}_{F_{i}}\setminus\bigcup_{i<j}\mathcal{D}_{F_{j}}=\mathcal{D}_{F_{i}}\setminus\mathcal{D}_{F_{1}}=\\{\\{i\\}\cup
Y:Y\subsetneq G\\}.$ (4.3)

Similarly, observe that for each $i>1$, we have

$\mathcal{U}_{F_{i}}\setminus\bigcup_{j<i}\mathcal{U}_{F_{i}}=\\{Z\subseteq[n]:Z\supseteq
F_{i},Z\cap\\{1,\ldots,i-1\\}=\emptyset\\}.$ (4.4)

So now putting together (4.2) (to bound $|\mathcal{S}_{1}|$), (4.3), and
(4.4), we obtain

$\displaystyle\left|\bigcup_{i=1}^{k-1}\mathcal{S}_{i}\right|$
$\displaystyle=|\mathcal{S}_{1}|+\sum_{i=2}^{k-1}\left|\mathcal{D}_{F_{i}}\setminus\bigcup_{i<j}\mathcal{D}_{F_{j}}\right|+\sum_{i=2}^{k-1}\left|\mathcal{U}_{F_{i}}\setminus\bigcup_{i<j}\mathcal{U}_{F_{j}}\right|-(k-2)$
$\displaystyle=2^{\ell+1}+2^{n-\ell-1}-1+(k-2)2^{\ell}+\left(\sum_{i=2}^{k-1}2^{n-\ell-i}\right)-(k-2).$

The final term occurs as the sets $F_{i}$ are counted both in their downset
and their upset. Simplifying we get

$c(\mathcal{A})=k2^{\ell}+2^{n-\ell}\left(1-\frac{1}{2^{k-1}}\right)-(k-1).$

∎

We now prove the lower bound given in Theorem 1.4. We actually prove a
slightly stronger statement.

######  Lemma 4.5.

Let $n,k\in\mathbb{N}$ where $n\geq 2k-1-\log_{2}{k}\geq 1$. Then

$\sigma(n,k)\geq
2^{n}-\frac{3}{\sqrt{2}}\left(1-\frac{1}{2^{k-1}}\right)^{\frac{1}{2}}\sqrt{2^{n}k}+2(k-1).$

###### Proof.

Let $a$ be an integer with the same partity as $n$ to be specified later. Let
$G:=\\{n-\frac{n-a}{2}+1,\ldots,n\\}$. Let $\mathcal{A}=\\{F_{1},F_{2},\cdots
F_{k-1}\\}$ be an antichain in $\mathcal{P}([n])$, where $F_{i}=G\cup\\{i\\}$.
This is possible as long as $n-\frac{n-a}{2}\geq k-1$, that is, $n\geq
2(k-1)-a$.

By Lemma 4.1 (setting $\ell=\frac{n-a}{2}$), we obtain

$c(\mathcal{A})=k2^{\frac{n-a}{2}}+2^{\frac{n+a}{2}}\left(1-\frac{1}{2^{k-1}}\right)-(k-1).$

Define $\mathcal{F}_{i}:=\\{F_{i}\\}$ for $1\leq i\leq k-1$ and
$\mathcal{F}_{k}:=\\{Z\subseteq[n]:Z\text{ incomparable to }F_{i}\text{ for
all }1\leq i\leq k-1\\}$. By construction,
$(\mathcal{F}_{1},\ldots,\mathcal{F}_{k})$ is cross-Sperner in
$\mathcal{P}([n])$. We have

$\displaystyle\sum_{i=1}^{k}|\mathcal{F}_{i}|$
$\displaystyle=(k-1)+2^{n}-c(\mathcal{A})$
$\displaystyle=2^{n}-\sqrt{2^{n}}\left(\frac{k}{\sqrt{2^{a}}}+\left(1-\frac{1}{2^{k-1}}\right)\sqrt{2^{a}}\right)+2(k-1).$
(4.6)

Differentiating this expression with respect to $a$ gives

$-\frac{\ln{2}}{2}\sqrt{2^{n}}\left(-\frac{k}{\sqrt{2^{a}}}+\left(1-\frac{1}{2^{k-1}}\right)\sqrt{2^{a}}\right).$

Thus we can see that if there were no restrictions on $a$ the maximum value of
(4.1) would be achieved when $2^{a}=k\frac{2^{k-1}}{2^{k-1}-1}$; that is,
$a={\log_{2}(k)+\log_{2}{\left(\frac{2^{k-1}}{2^{k-1}-1}\right)}}$. However,
we require $a$ to be an integer with the same parity as $n$. Set $a$ to be the
unique such integer such that

$-1<a-{\log_{2}(k)-\log_{2}{\left(\frac{2^{k-1}}{2^{k-1}-1}\right)}}\leq 1$

and let $c=a-{\log_{2}(k)-\log_{2}{\left(\frac{2^{k-1}}{2^{k-1}-1}\right)}}$.
Note that $n\geq 2k-1-\log_{2}{k}\geq 1$ by hypothesis. This ensures that
$n\geq 2(k-1)-a$ for any such value of $a$. We have

$\displaystyle\sum_{i=1}^{k}|\mathcal{F}_{i}|$
$\displaystyle=2^{n}-\sqrt{2^{n}}\left(\frac{k}{\sqrt{2^{a}}}+\left(1-\frac{1}{2^{k-1}}\right)\sqrt{2^{a}}\right)+2(k-1)$
$\displaystyle=2^{n}-\sqrt{2^{n}k}\left(1-\frac{1}{2^{k-1}}\right)^{1/2}\left(\frac{1}{\sqrt{2^{c}}}+\sqrt{2^{c}}\right)+2(k-1)$
(4.7)
$\displaystyle=2^{n}-\sqrt{2^{n}k}\left(1-\frac{1}{2^{k-1}}\right)^{1/2}\left(\frac{3}{\sqrt{2}}\right)+2(k-1)$

where the last inequality follows from the fact that the bracketed expression
in (4.1) is maximised when $c=1$ for $c$ in the range $-1<c\leq 1$. ∎

For certain values of $k$ we can prove a stronger lower bound which
essentially matches the upper bound given in Lemma 4.9.

######  Corollary 4.8.

Let $n,k\in\mathbb{N}$ and suppose that $k=2^{a}$ where $a$ has the same
parity as $n$ and $n\geq 2(k-1)-a$. Then

$\sigma(n,k)\geq 2^{n}-2\sqrt{2^{n}k}\left(1-\frac{1}{2^{k}}\right)+2(k-1).$

###### Proof.

Apply the proof of Lemma 4.5 with $a=\log_{2}{k}$. ∎

###  4.2 Upper Bound on $\sigma(n,k)$

######  Lemma 4.9.

For $k\geq 2$ and $n$ such that $2^{n}\geq(k-1)(1+\sqrt{k-1})^{2}$,

$\sigma(n,k)\leq 2^{n}-2\sqrt{2^{n}(k-1)}+2(k-1).$

###### Proof.

Suppose $(\mathcal{F}_{1},\mathcal{F}_{2},\cdots,\mathcal{F}_{k})$ is cross-
Sperner in $\mathcal{P}([n])$. We may and will assume that
$|\mathcal{F}_{1}|\leq|\mathcal{F}_{2}|\leq\cdots\leq|\mathcal{F}_{k}|$.
Define $\mathcal{G}:=\cup_{i=1}^{k-1}\mathcal{F}_{i}$. Let $m=|\mathcal{G}|$
and observe that, as each family is non-empty, we have $m\geq k-1$.

Note that $|\mathcal{F}_{k}|\leq 2^{n}-c(n,m)\leq
2^{n}-2^{n/2+1}\sqrt{m}+m=\left(\sqrt{2^{n}}-\sqrt{m}\right)^{2}$. Since the
families are ordered by increasing size, $|\mathcal{F}_{k}|\geq\frac{m}{k-1}$.
Putting this together gives

$\frac{m}{k-1}\leq|\mathcal{F}_{k}|\leq\left(\sqrt{2^{n}}-\sqrt{m}\right)^{2}.$

Rearranging, we obtain

$\sqrt{m}\leq\sqrt{2^{n}}\left(\frac{\sqrt{k-1}}{1+\sqrt{k-1}}\right).$ (4.10)

Now consider the sum

$\sum_{i=1}^{k}|\mathcal{F}_{i}|=|\mathcal{G}|+|\mathcal{F}_{k}|\leq
m+\left(\sqrt{2^{n}}-\sqrt{m}\right)^{2}.$ (4.11)

Let $x=\tfrac{1}{2}\sqrt{2^{n}}-\sqrt{m}$. Substituting this into expression
(4.11) above gives

$\left(\tfrac{1}{2}\sqrt{2^{n}}-x\right)^{2}+\left(\tfrac{1}{2}\sqrt{2^{n}}+x\right)^{2}=2^{n-1}+2x^{2}$

and it is clear that (4.11) is maximised when
$|x|=|\tfrac{1}{2}\sqrt{2^{n}}-\sqrt{m}|$ is as large as possible. Combining
$m\geq k-1$ with (4.10) gives
$\sqrt{k-1}\leq\sqrt{m}\leq\sqrt{2^{n}}\left(\frac{\sqrt{k-1}}{1+\sqrt{k-1}}\right)$,
we need only find which of these end values is further from
$\tfrac{1}{2}\sqrt{2^{n}}$.

If we have $2^{n}\geq(k-1)(1+\sqrt{k-1})^{2}$ then

$\tfrac{1}{2}\sqrt{2^{n}}-\sqrt{k-1}>\tfrac{1}{2}\sqrt{2^{n}}-\frac{\sqrt{2^{n}}}{1+\sqrt{k-1}}=\sqrt{2^{n}}\left(\frac{\sqrt{k-1}}{1+\sqrt{k-1}}\right)-\tfrac{1}{2}\sqrt{2^{n}}$

and thus expression (4.11) is maximised when $m=k-1$. Substituting $m=k-1$
into (4.11) gives

$\displaystyle\sum_{i=1}^{k}|\mathcal{F}_{i}|$
$\displaystyle\leq(k-1)+\left(\sqrt{2^{n}}-\sqrt{k-1}\right)^{2}$
$\displaystyle=2^{n}-2\sqrt{2^{n}(k-1)}+2(k-1).$

∎

###### Proof of Theorem 1.4.

Lemmas 4.5 and 4.9 together give Theorem 1.4. Observe that
$2^{2k}\geq{(k-1)(1+\sqrt{k-1})^{2}}$ for $k\geq 2$ so the conditions of Lemma
4.9 hold. ∎

##  5 Closing remarks

In Section 3 we provide upper and lower bounds on $\pi(n,k)$ in Theorems 1 and
1. Comparing these bounds shows that they differ by a factor of
$\left(\frac{e}{2}\right)^{k}$ for $k$ even and less than
$\left(1+\frac{1}{k}\right)\left(\frac{e}{2}\right)^{k}$ for $k$ odd. It would
be interesting to tighten this gap. We believe that (for large $n$) the bound
given in Lemma 3.1 ought to be essentially best possible.

######  Conjecture 5.1.

Let $k\geq 2$ be fixed and $n$ be sufficiently large with respect to $k$. Then

$\pi(n,k)=(1+o(1))\left(\frac{(k-1)^{k-1}}{k^{k}}2^{n}\right)^{k}.$

Our lower bound on $\pi(n,k)$ holds in the case $n>k\log_{2}{k}+k$. For small
fixed values of $n$ and $k$, we also have some bounds for $\pi(n,k)$, see
[16]. In particular, we have $f(4,3)=9$, $f(5,3)\geq 81$ $f(6,3)\geq 810$ and
$f(5,4)\geq 108$.

Note added before submission: In the final stages of preparation of this
article, we noticed a recent paper of Gowty, Horsley, and Mammoliti [9],
concerning the comparability number. They give a very different proof of
Theorem 2.3 (see Corollary 1.2 of [9]) and use it as we do to deduce Theorem
2.4. They also provide some very interesting further analysis of the
comparability number and sets that minimise $c(n,m)$.

## References

  * [1] J. Balogh and R. A. Krueger.  A sharp threshold for a random version of Sperner’s theorem.  _arXiv:2205.11630_ , 2022.
  * [2] J. Balogh, R. Mycroft, and A. Treglown.  A random version of Sperner’s theorem.  J. Combin. Theory Ser. A, 128:104–110, 2014.
  * [3] A. Brace and D. E. Daykin.  Sperner type theorems for finite sets.  In Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pages 18–37. Inst. Math. Appl., Southend-on-Sea, 1972.
  * [4] M. Collares and R. Morris.  Maximum-size antichains in random set-systems.  Random Structures Algorithms, 49(2):308–321, 2016.
  * [5] K. Engel.  Sperner theory, volume 65 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, 1997.
  * [6] Z. Füredi.  Cross-intersecting families of finite sets.  J. Combin. Theory Ser. A, 72(2):332–339, 1995.
  * [7] D. Gerbner, B. Keszegh, N. Lemons, C. Palmer, D. Pálvölgyi, and B. Patkós.  Saturating Sperner families.  Graphs Combin., 29(5):1355–1364, 2013.
  * [8] D. Gerbner, N. Lemons, C. Palmer, B. Patkós, and V. Szécsi.  Cross-Sperner families.  Studia Sci. Math. Hungar., 49(1):44–51, 2012.
  * [9] A. Gowty, D. Horsley, and A. Mammoliti.  Minimising the total number of subsets and supersets.  _arXiv:2212.13112_ , 2022.
  * [10] J. R. Griggs, T. Kalinowski, U. Leck, I. T. Roberts, and M. Schmitz.  Maximal antichains of subsets II: Constructions.  _arXiv:2106.02230_ , 2021.
  * [11] J. R. Griggs, T. Kalinowski, U. Leck, I. T. Roberts, and M. Schmitz.  The saturation spectrum for antichains of subsets.  _arXiv:2106.02226_ , 2021.
  * [12] M. Grüttmüller, S. Hartmann, T. Kalinowski, U. Leck, and I. T. Roberts.  Maximal flat antichains of minimum weight.  Electron. J. Combin., 16(1):Research Paper 69, 19, 2009.
  * [13] J. R. Johnson, I. Leader, and P. A. Russell.  Set systems containing many maximal chains.  Combin. Probab. Comput., 24(3):480–485, 2015.
  * [14] D. J. Kleitman.  Families of non-disjoint subsets.  J. Combinatorial Theory, 1:153–155, 1966.
  * [15] D. J. Kleitman.  On a conjecture of Milner on $k$-graphs with non-disjoint edges.  J. Combinatorial Theory, 5:153–156, 1968.
  * [16] A. Kuperus.  Cross-Sperner systems (Masters thesis). University of Victoria.  In preparation.
  * [17] J. Liu and C. Zhao.  On a conjecture of Hilton.  Australas. J. Combin., 24:265–274, 2001.
  * [18] M. Matsumoto and N. Tokushige.  The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families.  J. Combin. Theory Ser. A, 52(1):90–97, 1989.
  * [19] D. Osthus.  Maximum antichains in random subsets of a finite set.  J. Combin. Theory Ser. A, 90(2):336–346, 2000.
  * [20] L. Pyber.  A new generalization of the Erdős-Ko-Rado theorem.  J. Combin. Theory Ser. A, 43(1):85–90, 1986.
  * [21] P. D. Seymour.  On incomparable collections of sets.  Mathematika, 20:208–209, 1973.
  * [22] E. Sperner.  Ein Satz über Untermengen einer endlichen Menge.  Math. Z., 27(1):544–548, 1928.
  * [23] D. B. West.  Extremal problems in partially ordered sets.  In Ordered sets (Banff, Alta., 1981), volume 83 of NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., pages 473–521. Reidel, Dordrecht-Boston, Mass., 1982.


11institutetext: CWI, Machine Learning Group, Amsterdam, The Netherlands
11email<EMAIL_ADDRESS>22institutetext: Rijksuniversiteit
Groningen, Groningen, The Netherlands33institutetext: University of Amsterdam,
Amsterdam, The Netherlands

# Efficient Uncertainty Estimation in Spiking Neural Networks via MC-dropout

Tao Sun 11 Bojian Yin 11 Sander Bohté(✉) 11 2 2 3 3

###### Abstract

Spiking neural networks (SNNs) have gained attention as models of sparse and
event-driven communication of biological neurons, and as such have shown
increasing promise for energy-efficient applications in neuromorphic hardware.
As with classical artificial neural networks (ANNs), predictive uncertainties
are important for decision making in high-stakes applications, such as
autonomous vehicles, medical diagnosis, and high frequency trading. Yet,
discussion of uncertainty estimation in SNNs is limited, and approaches for
uncertainty estimation in artificial neural networks (ANNs) are not directly
applicable to SNNs. Here, we propose an efficient Monte Carlo(MC)-dropout
based approach for uncertainty estimation in SNNs. Our approach exploits the
time-step mechanism of SNNs to enable MC-dropout in a computationally
efficient manner, without introducing significant overheads during training
and inference while demonstrating high accuracy and uncertainty quality.

###### Keywords:

Spiking Neural Network Uncertainty Estimation MC-dropout.

##  1 Introduction

Inspired by the brain’s event-driven and sparse communication, spiking neural
networks (SNNs) are enabling applications with high energy-efficiency in the
form of neuromorphic computing [21]. Analogous to biological neurons, spiking
neurons in SNNs communicate using discrete spikes, and time stepping is
typically used to account for the evolution of these neurons’ internal state
as a response to impinging and emitted spikes. With recent advances in
architectures and training methods, SNNs now achieve performance comparable to
their artificial neural network (ANN) counterparts in many tasks [25, 26, 3].

To employ SNNs in the real-world however, accurate predictions have to be
paired with high-quality uncertainty estimation to enable decision-making in
high-stakes applications such as autonomous vehicles, medical diagnosis, and
high frequency trading [4]: uncertain predictions in these applications may
need to be reviewed by human experts for final decisions. In ANNs, predictive
uncertainties in classification models are commonly represented by predictive
distributions [13]. While evidence suggests that the brain performs a form of
Bayesian inference based on uncertainty representations [18], the literature
on uncertainty in SNNs is relatively limited and primarily concentrates on the
sampling of probabilistic distributions, typically from a neuroscience
perspective [20, 12].

Approaches for uncertainty estimation in classical deep learning models can be
divided into two groups: deterministic methods and Bayesian methods [6]. With
a deterministic method, a model learned from training data is essentially a
point estimate of the model’s parameters. In a deterministic deep network,
each predictive distribution is estimated by a single forward propagation
followed by the softmax function. Yet, although it is feasible to infer
uncertainty with deterministic methods, these methods are known to be prone to
output overconfident estimation [13, 6]. In contrast, a Bayesian network
learns the posterior distribution of parameters in the network rather than
depending on a single setting of parameters. The probability outputs of a
Bayesian method can be analytically obtained by marginalizing the likelihood
of the input with the estimated posterior distribution; this however is
generally an intractable problem. To tackle this issue, many approximation
methods and non-Bayesian methods have been introduced [6]. Example of these
methods like Monte-Carlo-dropout (MC-dropout) [5] and deep ensembles [13]
achieve excellent performance in terms of uncertainty estimation quality,
either by repeatedly carrying out inference for each sample in perturbed
versions of the network, or by training a collection of networks and then
carrying out inference in each network.

(a) Inference with MC-dropout

(b) Inference in AOT-SNN

Figure 1: (a) In ANNs, MC-dropout is performed by averaging results for a
predefined number ($M$) of forward passes through a dropout-enabled network.
(b) In AOT-SNNs, inference at each time step is taken as functionally
equivalent to a forward pass in the MC-dropout method. As the SNN network
evaluation requires $M$ time-steps already, only one effective forward pass is
needed.

Here, we propose an efficient uncertainty estimation approach for SNNs by
exploiting their time-step mechanism. Specifically, we apply continual MC-
dropout in SNNs by taking their outputs averaged over time steps as predictive
distributions, where we train SNNs with a loss function that also involves
their time steps: Average-Over-Time-SNNs (AOT-SNNs, Figure 1). In AOT-SNNs, we
take inference of each time step as functionally equivalent to a forward pass
in the standard MC-dropout method. Since only one forward pass is needed in
inference, the computational overhead for AOT-SNNs is significantly reduced
relative to the MC-dropout method while still allowing effective uncertainty
estimation. We compare the performance of AOT-SNNs with more standard SNNs, as
well as with SNNs using the classical MC-dropout approach and SNN ensembles,
across multiple classification tasks. We demonstrate that for identical
network architectures, AOT-SNNs achieve a significant gain over more standard
SNNs in both accuracy and uncertainty quality while being much more
computationally efficient.

##  2 Background

###  2.1 Problem Setup

We assume a training dataset $\mathcal{D}$ that consists of $\mathcal{N}$
i.i.d data points
$\mathcal{D}=\\{\mathbf{X},\mathbf{Y}\\}=\\{\mathbf{x}_{n},y_{n}\\}_{n=1}^{N}$,
where $\mathbf{x}_{n}\in\mathbb{R}^{d}$ and the true label
$y_{n}\in\\{1,\ldots,K\\}$. Given a sample $\mathbf{x}_{n}$, a neural network
outputs the probabilistic predictive distribution
$p_{\omega}(y_{n}|\mathbf{x}_{n})$, where $\omega$ is the parameters of the
network.

A number of non-Bayesian methods achieving excellent performance in term of
uncertainty estimation have been proposed, among which are deep ensembles [13]
and post-hoc calibration methods [10]. Deep ensembles are considered a “gold
standard” for uncertainty estimation [24], while a set of models are trained
with a proper scoring rule as the loss function. At inference time, the output
of all models are then combined to obtain a predictive distribution. Post-hoc
calibration methods, such as temperature scaling [10], involve the re-
calibration of probabilities using a validation dataset and achieve excellent
calibration performance in the i.i.d test dataset.

###  2.2 Bayesian Neural Networks and MC-Dropout Approximation

In a Bayesian neural network, the predictive distribution for a sample
$\mathbf{x}$ is given by:

$\displaystyle p(y|\mathbf{x},\mathcal{D})$ $\displaystyle=\int
p(y|\mathbf{x},\omega)p(\omega|\mathcal{D})d\omega.$ (1)

The posterior distribution, $p(\omega|\mathcal{D})$ or
$p(\omega|\mathbf{X},\mathbf{Y})$, of the parameters $\omega$ can be computed
by applying Bayes’ theorem

$p(\omega|\mathbf{X},\mathbf{Y})=\frac{p(\mathbf{Y}|\mathbf{X},\omega)p(\omega)}{p(\mathbf{Y}|\mathbf{X})}.$
(2)

Due to the intractability of the normalizer in (2), the posterior distribution
$p(\omega|\mathcal{D})$ and the predictive distribution
$p(y|\mathbf{x},\mathcal{D}))$ usually cannot be evaluated analytically. A
variety of approximation methods have been introduced to tackle this issue
[14, 9]. One such approximation is the MC-dropout method, which is often taken
as a baseline model in uncertainty estimation [13, 17] due to its feasibility
and relatively good performance.

Dropout [22] is a simple but effective technique used in deep learning models
to prevent overfitting. In the MC-dropout method, dropout is applied before
each weight layer of a neural network in both training and testing. The
predictive distribution calculation with the MC-dropout method is performed by
averaging results over a predefined number of forward passes through a
dropout-enabled network. Gal & Gharamani [5] showed that neural networks with
such configuration can be viewed as an approximation to a Bayesian method in
the form of deep Gaussian processes [2].

Either MC-dropout models or deep ensembles involves multiple forward
propagation passes in inference. As a result, when naviely applied to SNNs,
the computational and energy costs becomes relatively high due to the
necessity of repeatedly running SNNs for multiple times during inference.

###  2.3 Source and Quality of Predictive Uncertainty

The only source of predictive uncertainty of deterministic methods is from the
noisy data. Uncertainty in a Bayesian method comes from both data and defects
of the model itself [6]: uncertainty caused by data is referred to as data
uncertainty, while uncertainty caused by defects of the model itself is
referred to as model uncertainty.

The quality of predictive uncertainties can be measured from two aspects [13].
The first concerns uncertainty quality on in-distribution data, where test
data and training data share the same distribution. The second aspect
evaluates generalization of uncertainty on domain-shifted data. While certain
post-hoc calibration methods may generate accurate predictive probabilities
for i.i.d data, their effectiveness in predicting uncertainty for domain-
shifted data is not ensured [17]. For both aspects, model calibration is
examined as the indication of uncertainty quality [17]. For classification
tasks, accuracy and calibration are two evaluation measures that are mutually
orthogonal [13]. Accuracy, defined as the ratio of corrected classified
examples to total number of examples, measures how often a model correctly
classifies; calibration measures the quality of predictive probability
distributions [13] and indicates the extent to which the probability of a
predicted class label reflects the real correct likelihood. A class of metrics
to measure calibration is referred to as proper scoring rules [8], which
include the Brier score (BS) and negative log-likelihood (NLL); another
calibration metrics is the Expected Calibration Error (ECE) [10], which is a
scalar summary statistic of calibration that approximates miscalibration.
Although the definition ECE is intuitive and thus widely used, it is not a
perfect metric for calibration because optimal ECE values can be generated by
trivial solutions [17]; see the Appendix for details on proper scoring rules
and ECE.

###  2.4 SNN

SNNs typically work with the same types of network topologies as ANNs, but
computation in SNNs is distinct. SNNs use stateful and binary-valued spiking
neurons, rather than the stateless and analog valued neurons of ANNs. As a
result, unlike synchronous computation in ANNs, inference in SNNs is in a
iterative form through multiple time steps $t=0,1,...,T$: in each time step
$t$, the membrane potential of a spiking neuron $U(t)$ is affected by the
impinging spikes from connecting neurons emitted at time step $t-1$, and the
past potential $U(t-1)$. Once the membrane potential $U(t)$ reaches a
threshold $\theta$, the neuron itself emits a spike. Such sparse and
asynchronous communications between connected neurons is key to enabling SNNs
to achieve high energy-efficiency.

####  2.4.1 LIF Neurons

Various spiking neuron models exist, ranging in complexity from the detailed
Hodgkin-Huxley model to the simplified Leaky-Integrated-and-Fire (LIF) neuron
model [7]. The latter is widely used in SNNs, as it is interpretable and
computationally efficient. Resembling an RC circuit, the LIF neural model is
represented as:

$\tau\frac{dU}{dt}=-U+RI.$ (3)

where $I$ and $R$ are the current and input resistance, and $\tau$ is the time
constant of the circuit. The discrete approximation of (3) can be written as:

$u^{t}_{i}=\lambda u^{t-1}_{i}+\sum_{j}w_{ij}s^{t}_{j}-s_{i}^{t-1}\theta,$ (4)
$s^{t}_{i}=\left\\{\begin{array}[]{lr}1,&\text{if }u^{t}_{i}>\theta\\\
0,&\text{otherwise}\end{array}\right.$ (5)

where $u_{i}$ is the membrane potential of a neuron $i$, $\lambda$ denotes the
leaky constant ($<1$) for the membrane potential, $w_{ij}$ represents the
weight connecting the neuron $i$ and its pre-synaptic neuron $j$, and $s_{i}$
indicates whether a neuron spikes.

With the introduction of surrogate gradient methods [16, 25] and learnable LIF
neurons [25, 3], both trainability and performance of SNNs have been improved
dramatically.

##  3 Methods

Here, we present our proposed AOT-SNNs. We first explain how we efficiently
apply MC-dropout to SNNs, and then introduce the loss function used in AOT-
SNNs, which is based on the mean output values over time steps. Lastly, we
explain the network architecture we use to demonstrate AOT-SNNs in practice.

###  3.1 Efficient MC-dropout in SNNs

As noted, the standard MC-dropout method runs a test sample multiple times in
a model with dropout enabled, and takes the output of these forward passes as
the final predictive distribution. Thus applied, the MC-dropout method
achieves satisfactory performance in predictive uncertainty in ANNs.

In principle, thus defined MC-dropout can be applied directly to SNNs, as MC-
dropout SNN. This, however, can result in inefficient inference, mainly due to
the time-step mechanism in SNNs. As each neuron’s activation in an SNN is a
continuous process over time, an SNN typically has to be run for multiple time
steps to perform inference. Naively performing inference of a single sample in
an SNN with MC-dropout would mean running multiple forward passes of a sample
through a network where each individual pass entails the evaluation of
multiple time steps. This will obviously be computationally expensive.

As an alternative, we propose to leverage SNN time-step mechanism by enabling
MC-dropout in AOT-SNNs during a single evaluation. Specifically, we compute
predictive distributions in a dropout-enabled AOT-SNN by averaging outputs of
its multiple time steps. In this view, each time step in an AOT-SNN is weakly
equivalent to a forward pass in the standard MC-dropout method. This approach
requires only one forward pass during inference and thus significantly lowers
computational costs.

###  3.2 Loss Function

Loss functions in many current high-performing SNN learning algorithms [25, 3,
19, 27] are computed based on the output values of last time step, and we will
refer such loss functions as last-time-step loss, resulting in Last-Time-Step-
SNNs (LTS-SNNs). The last-time-step loss is written as:

$\qquad L=l(T)$ (6)

where $l(t)$ is the loss function computed on the output values of the time
step $t$. Since the last-time-step loss is not compatible with the proposed
uncertainty estimation approach in AOT-SNNs, we introduce the average-over-
time loss, which calculates its output by averaging over multiple time steps:

$L=\frac{1}{T}\sum_{t=1}^{T}l(t).$ (7)

By combining the average-over-time loss with MC-dropout, we expect that the
quality of uncertainty estimation for our approach will be improved,
particularly in comparison to LTS-SNNs trained by the last-time-step loss, as
AOT pushes SNNs to correctly classify as much as possible at every time step,
while LTS-SNNs do not.

For $l(t)$, either negative log-likelihood (NLL) loss or the mean squared
error (MSE) loss [3] can be used. Here, we use the MSE loss, as we find that
in practise the NLL loss causes practice a disconnect between NLL and
accuracy, which is an indication of miscalibration [10].

###  3.3 Network Architecture

We use AOT-SNNs with a network architecture very similar to the high-
performing PLIF networks in [3]. These networks are composed of a spiking
encoder network and a classifier network. The spiking encoder network consists
of multiple downsampling modules. Each downsampling module has a certain
number of convolution blocks and a pooling layer ($kernel\,size=2,stride=2$).
The convolution block is composed of a convolution layer
($kernel\,size=3,stride=1,padding=1$), a batch normalization layer, and a
spiking neuron layer.

Our classifier network is slightly modified from [3] and includes a fully-
connected layer, a spiking neuron layer, another fully-connected layer, which
is then followed by a readout integrator layer. Unlike the original PLIF
networks that classify using relatively coarse summed rate-coding collected
from a population of output neurons, probabilities of AOT-SNNs are computed
based on the membrane potentials of readout integrator neurons as in [25].
This modification enable AOT-SNNs to achieve better uncertainty estimation
performance compared to corresponding standard PLIF networks while obtaining
similar accuracy. In the spiking neuron layers, PLIF neurons [3] are used,
where the time constants $\tau$ are learned and shared by neurons within the
same layer. Note that dropout is applied to the neurons’ output spikes, and
input data is directly injected into the network as current into the input
neurons.

##  4 Experiments

We performed a series of experiments to compare AOT-SNNs to LTS-SNNs, as well
as MC-dropout SNNs and also with the ‘gold standard’ of SNN ensembles, across
multiple classification tasks. As a proof of concept, we first applied this
approach to the MNIST dataset. Second, we experiment on the CIFAR-10 dataset
to compare our models with corresponding LTS-SNNs. Additionally, we reported
and analyzed results on the CIFAR-100 dataset. Furthermore, we carried out an
ablation study where we characterized the uncertainty properties of AOT-SNNs
with regard to dropout rates and dropout types.

###  4.1 Experimental Setup

In our experiments, LTS-SNNs used the same layer structure as their
corresponding AOT-SNNs. However, they differ in that LTS-SNNs used the
predictive distribution output by the last time step and were trained with the
last-time-step loss. Note that dropout is not enabled during inference in LTS-
SNNs. Enabling dropout would lead to notably weak performance for LTS-SNNs,
similar to that of ANNs. All the MC-dropout SNNs and SNN ensembles are based
on their corresponding LTS-SNNs.

The Adam optimizer was used, with a cosine annealing learning rate scheduler,
whose initial learning rate is 0.001 and $T_{max}$ is 64. The default dropout
rate used is 0.5. For the MINIST dataset, we used a batch size of 150, while
the batch sizes were 60 for CIFAR-10 and 15 for CIFAR-100. The number of
epochs used for each dataset were 200 (MNIST), 300 (CIFAR-10), and 300
(CIFAR-100).

###  4.2 MNIST

Table 1: Performance comparisons between the AOT-SNN and its corresponding LTS-SNN on the MNIST dataset (mean$\pm$std across 5 trials). The numbers after the model names represent time steps. Model |  Accuracy (%) $\uparrow$ |  BS $\downarrow$ |  NLL $\downarrow$ |  ECE $\downarrow$
---|---|---|---|---
AOT-SNN (8) |  99.54$\pm$0.030 |  7.0e-4$\pm$4.3e-5 |  0.0144$\pm$7.6e-4 |  0.0012$\pm$3.4e-4
LTS-SNN (8) | 99.37$\pm$0.080 | 1.0e-3$\pm$1.0e-4 | 0.021$\pm$0.0025 | 0.004$\pm$0.0011
Figure 2: Uncertainty performance for each time step of the AOT-SNN model and
its corresponding LTS-SNN on the MNIST dataset. The results of metrics are
averaged over the entire test dataset.

The spiking encoder network for the MNIST dataset has two downsampling
modules, each of which includes only one convolution block. In Table 1, we
compared the AOT-SNN and its corresponding LTS-SNN, both using best performing
models that have eight time steps to evaluate samples. The results demonstrate
that the AOT-SNN outperforms the LTS-SNN in both accuracy and the predictive
uncertainty metrics, including Brier score, NLL, and ECE. For each time step
of the two models, we illustrated the performance of Brier score and ECE,
averaged over the entire test dataset (figure 2). Note that the mean values of
these two metrics over the previous time steps were used for each time step of
the AOT-SNN. The graph illustrates that during the initial three time
intervals, the AOT-SNN’s performance lags behind the LTS-SNN. However,
performance of the AOT-SNN demonstrates a significant improvement over the
LTS-SNN in both two uncertainty metrics from the fourth time step to the final
one. This improvement could be attributed to the updates of AOT-SNNs compared
to LTS-SNNs, where we average the outputs of dropout-enabled time steps and
take them as the final output.

###  4.3 CIFAR-10 and CIFAR-100

The architectures of AOT-SNNs for the CIFAR-10 and CIFAR-100 dataset are
similar. They apply the same spiking encoder network, which has two
downsampling modules, each with three convolution blocks. Their classifier
networks differ only in the last fully-connected layer due to their different
number of ground truth classes.

Table 2: Comparison on the CIFAR-10 dataset between AOT-SNNs, LTS-SNNs, MC-dropout models, and deep ensembles (mean$\pm$ std across 5 trials). The digits enclosed in brackets following the model names indicate the number of SNN time steps and the number of forward passes or models used in inference. Model |  Accuracy (%) $\uparrow$ |  BS $\downarrow$ |  NLL $\downarrow$ |  ECE $\downarrow$
---|---|---|---|---
AOT-SNN (4, 1) |  90.2$\pm$0.26 |  0.0153$\pm$0.00030 |  0.38$\pm$0.012 |  0.040$\pm$0.0031
AOT-SNN (8, 1) |  90.8$\pm$0.23 |  0.0144$\pm$0.00040 |  0.37$\pm$0.022 |  0.043$\pm$0.0041
LTS-SNN (4, 1) |  88.9$\pm$0.71 |  0.017$\pm$0.0011 |  0.43$\pm$0.028 |  0.058$\pm$0.0044
LTS-SNN (8, 1) |  88.5$\pm$0.60 |  0.0181$\pm$0.00081 |  0.47$\pm$0.013 |  0.067$\pm$0.0034
MC-dropout SNN (4, 5) |  90.53$\pm$0.37 |  0.0140$\pm$0.00041 |  0.32$\pm$0.001 |  0.026$\pm$0.0030
MC-dropout SNN (8, 5) |  90.43$\pm$0.37 |  0.0145$\pm$0.00053 |  0.35$\pm$0.013 |  0.037 $\pm$0.0014
SNN Ensembles (4, 5) | 90.9 | 0.0134 | 0.2919 | 0.012
SNN Ensembles (8, 5) | 90.8 | 0.0135 | 0.2967 | 0.016
Table 3: In-distribution performance comparisons between AOT-SNNs and LTS-SNNs on CIFAR10 (mean$\pm$std across 5 trials). Model | Time steps |  Accuracy (%) $\uparrow$ |  BS $\downarrow$ |  NLL $\downarrow$ |  ECE $\downarrow$
---|---|---|---|---|---
AOT-SNN | 2 |  89.4$\pm$0.18 |  0.0168$\pm$0.00014 |  0.417$\pm$0.0061 |  0.047$\pm$0.0023
AOT-SNN | 3 |  89.7$\pm$0.26 |  0.0160$\pm$0.00027 |  0.40$\pm$0.021 |  0.044$\pm$0.0042
AOT-SNN | 4 |  90.2$\pm$0.26 |  0.0153$\pm$0.00030 |  0.38$\pm$0.012 |  0.040$\pm$0.0031
AOT-SNN | 5 |  90.4$\pm$0.07 |  0.0150$\pm$0.00024 |  0.39$\pm$0.026 |  0.043$\pm$0.0036
AOT-SNN | 6 |  90.5$\pm$0.16 |  0.0149$\pm$0.00028 |  0.38$\pm$0.017 |  0.043$\pm$0.0030
AOT-SNN | 7 |  90.2$\pm$0.34 |  0.0151$\pm$0.00043 |  0.37$\pm$0.012 |  0.043$\pm$0.0019
AOT-SNN | 8 |  90.8$\pm$0.23 |  0.0144$\pm$0.00040 |  0.37$\pm$0.022 |  0.043$\pm$0.0041
AOT-SNN | 9 |  90.5$\pm$0.55 |  0.0147$\pm$0.00073 |  0.37$\pm$0.024 |  0.044$\pm$0.0041
AOT-SNN | 10 |  90.7$\pm$0.41 |  0.0146$\pm$0.00062 |  0.37$\pm$0.024 |  0.044$\pm$0.0052
LTS-SNN | 1 |  88.2$\pm$0.47 |  0.017$\pm$0.00068 |  0.36$\pm$0.013 |  0.0138$\pm$0.0034
LTS-SNN | 2 |  88.6$\pm$0.40 |  0.0180$\pm$0.00031 |  0.46$\pm$0.0085 |  0.067$\pm$0.0055
LTS-SNN | 3 |  88.0$\pm$0.56 |  0.0184$\pm$0.00076 |  0.44$\pm$0.023 |  0.060$\pm$0.0030
LTS-SNN | 4 |  88.9$\pm$0.71 |  0.017$\pm$0.0011 |  0.43$\pm$0.028 |  0.058$\pm$0.0044
LTS-SNN | 5 |  88.4$\pm$0.27 |  0.0181$\pm$0.00047 |  0.46$\pm$0.016 |  0.063$\pm$0.0031
LTS-SNN | 7 |  88.3$\pm$1.12 |  0.018$\pm$0.0014 |  0.48$\pm$0.026 |  0.068$\pm$0.0062
LTS-SNN | 8 |  88.5$\pm$0.60 |  0.0181$\pm$0.00081 |  0.47$\pm$0.013 |  0.067$\pm$0.0034
LTS-SNN | 9 |  88.0$\pm$0.52 |  0.0189$\pm$0.00082 |  0.49$\pm$0.025 |  0.069$\pm$0.0036
LTS-SNN | 10 |  88.0$\pm$0.91 |  0.019$\pm$0.0015 |  0.49$\pm$0.046 |  0.069$\pm$0.0062

####  4.3.1 CIFAR-10 held-out test dataset.

Table 2 presents a comparison of AOT-SNNs to LTS-SNNs, MC-dropout SNNs, and
SNN ensembles. While each MC-dropout SNN ran five forward passes, each SNN
ensemble consisted of five models. We show results for 4 and 8 time steps,
corresponding to respective best performing duration (see also Table 3). AOT-
SNNs exhibit superior performance compared to LTS-SNNs, and achieve comparable
accuracy to SNN ensembles while yielding slightly lower results on BS and NLL,
only underperforming on ECE. In comparison to the the MC-dropout SNNs, AOT-
SNNs do deliver superior accuracy and performed almost as well as BS and NLL,
with only a slight loss in ECE.

Table 3 presents the results of AOT-SNNs and LTS-SNNs with time steps smaller
or equal to 10. With each model trained five times, the table lists the mean
and standard deviation for all the metrics. In this exhaustive comparison, we
see that that AOT-SNNs significantly outperform LTS-SNNs, with all models with
more than 3 time steps achieving significantly better accuracy and Brier
score, with best results for 8 time steps. Moreover, almost all AOT-SNNs
achieve better NLL and ECE, except for the model with a single time step
(which however has considerably lower accuracy). This is in line with the
finding for MNIST in the Figure 2.

####  4.3.2 CIFAR-100.

Comparing the AOT-SNN with time step eight with its corresponding LTS-SNN for
CIFAR-100 (Table 4), we similarly find that AOT-SNNs achieve significantly
better results than the LTS-SNN, in both accuracy and predictive uncertainty
quality.

Table 4: Performance comparisons between the AOT-SNN and the corresponding LTS-SNN on the CIFAR-100 dataset. Model | Time steps |  Accuracy (%) $\uparrow$ |  BS $\downarrow$ |  NLL $\downarrow$ |  ECE $\downarrow$
---|---|---|---|---|---
AOT-SNN | 8 | 65.15 | 0.005028 | 1.6749 | 0.1352
LTS-SNN | 8 | 62.32 | 0.005333 | 1.7325 | 0.1665

####  4.3.3 CIFAR-10-C: domain-shifted test dataset.

Figure 3: Comparisons of the AOT-SNN model, its corresponding LTS-SNN, and the
post-hoc calibrated version of the LTS-SNN on each severity level of
CIFAR-10-C.

As mentioned earlier, the quality of predictive uncertainties need to be
measured on both in-distribution held-out data and domain-shifted data. We
evaluated AOT-SNNs on the CIFAR-10-C dataset [11], a domain-shifted test
dataset of CIFAR-10. The CIFAR-10-C dataset is designed to evaluate the
robustness of image classification models against common corruptions. It
contains 19 corruption types that are created by applying a combination of 5
severity levels to the original CIFAR-10 test set. The CIFAR-10-C dataset is
commonly used as a benchmark to evaluate the uncertainty estimation in domain-
shifted settings [17]. We compared the performance of the AOT-SNN with eight
time steps, its corresponding LTS-SNN, and the temperature scaling method that
re-calibrates probabilities output by the LTS-SNN on all the severity levels
of CIFAR-10-C (Figure 3). The results show that the AOT-SNN outperform the
LTS-SNN in all severity levels. Furthermore, in severity levels one to four,
the AOT-SNN achieve better performance than the post-hoc calibrated results,
while in level five, the AOT-SNN has comparable performance. Together, this
shows that AOT-SNNs improve uncertainty estimation over both LTS-SNNs and the
temperature scaling method also in domain-shifted settings.

#### Ablation study.

We further considered the impact of dropout rates and dropout types on the
quality of uncertainty estimates of AOT-SNNs.

##### Dropout type.

We replaced the dropout in the LTS-SNN and our best-performing model, both of
which have eight time steps, with DropConnect [23]. Instead of dropping the
spikes like the regular dropout, DropConnect randomly drops the weights in
each layer before the PLIF neuron layer. As shown in Table 5, despite the
slightly better performance of the LTS-SNN-DC compared to the corresponding
dropout-based models (LTS-SNN), the AOT-SNN-DC outperform LTS-SNN-DC in terms
of both accuracy and uncertainty quality (both models in the table have a
dropout rate of 0.5). The observation suggests that DropConnect may fulfill
the same function as regular dropout in AOT-SNNs.

Table 5: Performance comparisons between the AOT-SNN with DropConnect and its corresponding LTS-SNN on the CIFAR-10 dataset. The numbers after the model names represent time steps. Model |  Accuracy (%) $\uparrow$ |  BS $\downarrow$ |  NLL $\downarrow$ |  ECE $\downarrow$
---|---|---|---|---
AOT-SNN (8) |  90.8$\pm$0.23 |  0.0144$\pm$0.00040 |  0.37$\pm$0.022 |  0.043$\pm$0.0041
AOT-SNN-DC (8) |  90.5$\pm$0.37 |  0.0140$\pm$0.00041 |  0.32$\pm$0.010 |  0.026$\pm$0.0030
LTS-SNN (8) |  88.5$\pm$0.60 |  0.0181$\pm$0.00081 |  0.47$\pm$0.013 |  0.067$\pm$0.0034
LTS-SNN-DC (8) |  90.2$\pm$0.25 |  0.0161$\pm$0.00036 |  0.47$\pm$0.035 |  0.065$\pm$0.0041
Figure 4: The impact of dropout rate on performance of AOT-SNNs on the
CIFAR-10 dataset. Dropout rates are ranging from 0.1 to 0.9 in increments of
0.1.

##### Dropout rate.

To investigate the impact of dropout rate on performance, we tested AOT-SNNs
with dropout rates ranging from 0.1 to 0.9 in increments of 0.1. These
experiments were based on our best-performing model of eight time steps and
trained on the CIFAR-10 dataset separately for each amount of dropout. The
accuracy and Brier score were plotted in Figure 4. The trends in accuracy,
Brier score are consistent, with models having dropout rates lower than 0.5
producing flat results, followed by a decline in performance.

##  5 Conclusion

We proposed a novel and efficient approach for uncertainty estimation in
spiking neural networks SNNs based on the MC-dropout method combined with an
appropriate choice of loss-function. Our approach exploits the time-step
mechanism of SNNs to enable MC-dropout in a computationally efficient manner,
without introducing significant overheads during training and inference. We
demonstrated that our proposed approach can be computationally efficient and
performant in uncertainty quality at the same time. Future work could
investigate the potential of our approach in more applications, such as speech
processing and medical imaging.

#### Acknowledgments

TS is supported by NWO-NWA grant NWA.1292.19.298. SB is supported by the
European Union (grant agreement 7202070 “HBP”).

## Appendix

#### Proper Scoring Rules.

A scoring rule $S(\mathbf{p},y)$ assigns a value for a predictive distribution
$\mathbf{p}$ and one of the labels $y$. A scoring function
$s(\mathbf{p},\mathbf{q})$ is defined as the expected score of
$S(\mathbf{p},y)$ under the distribution $q$

$s(\mathbf{p},\mathbf{q})=\sum_{y=1}^{K}q_{y}S(\mathbf{p},y).$ (8)

If a scoring rule satisfies
$s(\mathbf{p},\mathbf{q})<=s(\mathbf{q},\mathbf{q})$, it is called a proper
scoring rule. If $s(\mathbf{p},\mathbf{q})=s(\mathbf{q},\mathbf{q})$ implies
$\mathbf{q}=\mathbf{p}$, this scoring rule is a strictly proper scoring rule.
When evaluating quality of probabilities, an optimal score output by a proper
scoring rule indicates a perfect prediction [17]. In contrast, trivial
solutions could generate optimal values for an improper scoring rule [17, 8].

The two most commonly used proper scoring rules are Brier score [1] and NLL.
Brier score is the squared $L_{2}$ norm of the difference between $\mathbf{p}$
and one-hot encoding of the true label $y$. NLL is defined as
$S(\mathbf{p},y)=-\mathrm{log}p(y|\mathbf{x})$ with $y$ being the true label
of the sample $\mathbf{x}$. Among these two rules, the Brier score is more
recommendable because NLL can unacceptably over-emphasize small differences
between small probabilities [17]. Note that proper scoring rules are often
used as loss functions to train neural networks. [13, 8].

#### ECE.

The ECE is a scalar summary statistic of calibration that approximates
miscalibration [15, 10]. To calculate ECE, the predicted probabilities,
$\hat{y}_{n}=\mathrm{argmax}_{y}\mathbf{p}(y|\mathbf{x_{n}})$, of test
instances are grouped into $M$ equal-interval bins. The ECE is defined as

$ECE=\sum_{m=1}^{M}f_{m}|o_{m}-e_{m}|,$ (9)

where $o_{m}$ is the fraction of corrected classified instances in the
$m^{th}$ bin, $e_{m}$ the average of all the predicted probabilities in the
$m^{th}$ bin, and $f_{m}$ the fraction of all the test instances falling into
the $m^{th}$ bin. The ECE is not a proper scoring rule and thus optimum ECEs
could come from trivial solutions.

## References

  * [1] Brier, G.W., et al.: Verification of forecasts expressed in terms of probability. Monthly weather review 78(1), 1–3 (1950)
  * [2] Damianou, A., Lawrence, N.D.: Deep gaussian processes. In: Artificial intelligence and statistics. pp. 207–215. PMLR (2013)
  * [3] Fang, W., Yu, Z., Chen, Y., Masquelier, T., Huang, T., Tian, Y.: Incorporating learnable membrane time constant to enhance learning of spiking neural networks. In: CVPR. pp. 2661–2671 (2021)
  * [4] Gal, Y.: Uncertainty in Deep Learning. Ph.D. thesis, Department of Engineering, University of Cambridge (2016)
  * [5] Gal, Y., Ghahramani, Z.: Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In: ICML. pp. 1050–1059. PMLR (2016)
  * [6] Gawlikowski, J., Tassi, C.R.N., Ali, M., Lee, J., Humt, M., Feng, J., Kruspe, A., Triebel, R., Jung, P., Roscher, R., et al.: A survey of uncertainty in deep neural networks. arXiv preprint arXiv:2107.03342 (2021)
  * [7] Gerstner, W., Kistler, W.M.: Spiking Neuron Models: Single Neurons, Populations, Plasticity. Cambridge University Press (Aug 2002)
  * [8] Gneiting, T., Raftery, A.E.: Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association 102(477), 359–378 (2007)
  * [9] Graves, A.: Practical variational inference for neural networks. NIPS 24 (2011)
  * [10] Guo, C., Pleiss, G., Sun, Y., Weinberger, K.Q.: On calibration of modern neural networks. In: ICML. pp. 1321–1330. PMLR (2017)
  * [11] Hendrycks, D., Dietterich, T.: Benchmarking neural network robustness to common corruptions and perturbations. In: ICLR (2019), https://openreview.net/forum?id=HJz6tiCqYm
  * [12] Jang, H., Simeone, O.: Multisample online learning for probabilistic spiking neural networks. IEEE Trans Neural Netw Learn Syst 33(5), 2034–2044 (May 2022)
  * [13] Lakshminarayanan, B., Pritzel, A., Blundell, C.: Simple and scalable predictive uncertainty estimation using deep ensembles. NIPS 30 (2017)
  * [14] Mackay, D.J.C.: Bayesian methods for adaptive models. Ph.D. thesis, California Institute of Technology (1992)
  * [15] Naeini, M.P., Cooper, G., Hauskrecht, M.: Obtaining well calibrated probabilities using bayesian binning. In: AAAI (2015)
  * [16] Neftci, E.O., Mostafa, H., Zenke, F.: Surrogate gradient learning in spiking neural networks: Bringing the power of gradient-based optimization to spiking neural networks. IEEE Signal Processing Magazine 36(6), 51–63 (2019)
  * [17] Ovadia, Y., Fertig, E., Ren, J., Nado, Z., Sculley, D., Nowozin, S., Dillon, J., Lakshminarayanan, B., Snoek, J.: Can you trust your model’s uncertainty? evaluating predictive uncertainty under dataset shift. NIPS 32 (2019)
  * [18] Pouget, A., Beck, J.M., Ma, W.J., Latham, P.E.: Probabilistic brains: knowns and unknowns. Nature neuroscience 16(9), 1170–1178 (2013)
  * [19] Rathi, N., Srinivasan, G., Panda, P., Roy, K.: Enabling deep spiking neural networks with hybrid conversion and spike timing dependent backpropagation. In: ICML (2020), https://openreview.net/forum?id=B1xSperKvH
  * [20] Savin, C., Deneve, S.: Spatio-temporal representations of uncertainty in spiking neural networks. Adv. Neural Inf. Process. Syst. (2014)
  * [21] Schuman, C.D., Kulkarni, S.R., Parsa, M., Mitchell, J.P., Date, P., Kay, B.: Opportunities for neuromorphic computing algorithms and applications. Nature Computational Science 2(1), 10–19 (2022)
  * [22] Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., Salakhutdinov, R.: Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research 15(1), 1929–1958 (2014)
  * [23] Wan, L., Zeiler, M., Zhang, S., Le Cun, Y., Fergus, R.: Regularization of neural networks using dropconnect. In: ICML. pp. 1058–1066. PMLR (2013)
  * [24] Wilson, A.G., Izmailov, P.: Bayesian deep learning and a probabilistic perspective of generalization. NIPS 33, 4697–4708 (2020)
  * [25] Yin, B., Corradi, F., Bohté, S.M.: Accurate and efficient time-domain classification with adaptive spiking recurrent neural networks. Nature Machine Intelligence 3(10), 905–913 (2021)
  * [26] Yin, B., Corradi, F., Bohté, S.M.: Accurate online training of dynamical spiking neural networks through forward propagation through time. Nature Machine Intelligence (2023, to appear)
  * [27] Yue, Y., Baltes, M., Abujahar, N., Sun, T., Smith, C.D., Bihl, T., Liu, J.: Hybrid spiking neural network fine-tuning for hippocampus segmentation. arXiv preprint arXiv:2302.07328 (2023)