described above that there is a new combinatorial equivalence $\phi^{\prime}$
from the stellar subdivision of $\mbox{lk}({\bf 0})$ to the stellar
subdivision of $\mbox{lk}(p)$, for which
$\phi^{\prime}(p_{i}^{\pm})=q_{i}^{\pm}$ and
$\phi^{\prime}(r_{i}^{\pm})=\phi(p_{i}^{\pm})$ (where $\phi$ is the
combinatorial equivalence before the given elementary starring operation).
Moreover, with respect to $\phi^{\prime}$, the sign of $F-F(p)$ agrees by
construction with the sign of $F_{\tiny reg}$ at the new vertex introduced
during the elementary starring and at the old nearby vertex.

After performing the above elementary starring in the order described, one
therefore has combinatorially equivalent stellar subdivisions
$\mbox{lk}^{\prime}(p)$ and $\mbox{lk}^{\prime}({\bf 0})$ for which the sign
of $F-F(p)$ agrees with the sign of $F_{\tiny reg}$ for all vertices. It
follows that $p$ is PL regular.

Since the possibilities listed in the statement of the proposition for partial
orientations on the $1$–dimensional cofaces of $p$ are exhaustive and mutually
exclusive, the classification of points is complete. ∎

##  7\. Stable H-complexity, coarse H-complexity, and bounds

In this section we use Theorem 1 to define stable and coarse versions of the
topological complexity of a finite PL map
$F:\mathbb{R}^{n}\rightarrow\mathbb{R}$. These invariants of the PL map should
be easier to compute than the more refined invariants defined in Section 4.
Moreover, we conjecture that they give lower bounds. For completeness, we also
mention some additional upper bounds on the global $H$–complexity that we
believe are very far from being sharp.

###  7.1. Stable and coarse H-complexity

In the following, let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a finite PL
function. We have in mind that $F$ is a ReLU neural network function. Recall
that every finite PL function has finitely many nontransversal thresholds.

######  Definition 7.1.

Let $M\in\mathbb{R}^{>0}$ satisfy the property that all nontransversal
thresholds of $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ are contained in the
interval $(-M,M)$. Then we refer to the rank of

  * •

$H_{*}(F_{\leq-M})$ (resp., $H_{*}(F_{\leq+M})$) as the negative (resp.,
positive) stable sublevel H-complexity;

  * •

$H_{*}(F_{\geq-M})$ (resp., $H_{*}(F_{\geq+M})$) as the negative (resp.,
positive) stable superlevel H-complexity;

  * •

$H_{*}(F_{\leq M},F_{\leq-M})$ as the coarse bounded sublevel $H$–complexity;

  * •

$H_{*}(F_{\geq-M},F_{\geq M})$ as the coarse bounded superlevel
$H$–complexity;

of $F$.

Note that since all nontransversal thresholds are in the interval $(-M,M)$,
Theorem 1 ensures that all of the above are independent of $M$. Moreover, the
long exact sequence on relative homology (cf. [10]) relates the terms in the
triple $H_{*}(F_{\leq-M}),H_{*}(F_{\leq M}),$ and $H_{*}(F_{\leq
M},F_{\leq-M})$ (resp., $H_{*}(F_{\geq M})$, $H_{*}(F_{\geq-M})$,
$H_{*}(F_{\geq-M},F_{\geq M})$).

######  Theorem 8.

Let $n_{\pm}$ denote the number of connected components of $F_{\leq\pm M}$ and
let $n^{\pm}$ denote the number of connected components of $F_{\geq\pm M}$. We
have the following lower bounds:

  1. (i)

$|n_{-}-n_{+}|$ is a lower bound for the coarse bounded sublevel
$H$–complexity

  2. (ii)

$|n^{+}-n^{-}|$ is a lower bound for the coarse bounded superlevel
$H$–complexity

###### Proof.

Note that multiplying the function $F$ by $-1$ exchanges the roles of both
$\pm M$ and the coarse bounded sublevel/superlevel $H$–complexity. Therefore,
statements (i) and (ii) are equivalent, and it is enough to give a proof of
(i).

For (i), we consider the long exact sequence on the pair (cf. [10]) coming
from the inclusion $F_{\leq-M}\subseteq F_{\leq M}$:

$\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
6.75pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ldots\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
6.65971pt\raise 6.1111pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\hbox{\hbox{\kern 0.0pt\raise-1.75pt\hbox{$\scriptstyle{f}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 16.75pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
16.75pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{{H}_{1}(F_{\leq
M},F_{\leq-M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
85.40558pt\raise 5.1875pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.8264pt\hbox{$\scriptstyle{g}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 95.20053pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
95.20053pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{{H}_{0}(F_{\leq-M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
150.98831pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
150.98831pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{{H}_{0}(F_{\leq
M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
194.89287pt\raise 5.43056pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.43056pt\hbox{$\scriptstyle{h}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 204.90942pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
204.90942pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{{H}_{0}(F_{\leq
M},F_{\leq-M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
283.35995pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
283.35995pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{0}$}}}}}}}\ignorespaces}}}}\ignorespaces.$

Note that $n_{\pm}=\mbox{rk}({H}_{0}(F_{\leq\pm M}))$ and
$\mbox{rk}(H_{0}(F_{\leq M},F_{\leq-M}))$ is a lower bound for the rank of the
$-$ semi-infinite global $H$–complexity. Since the alternating sum of the
ranks of the terms in an exact sequence is $0$, we can truncate:

$\textstyle{0\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{H}_{0}(F_{\leq-M})/\mbox{im}(g)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{H}_{0}(F_{\leq
M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{H}_{0}(F_{\leq
M},F_{\leq-M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$

to see that $n_{+}-n_{-}\leq\mbox{rk}(H_{0}(F_{\leq
M},F_{\leq-M}))\leq\mbox{rk}(H_{*}(F_{\leq M},F_{\leq-M}))$.

By truncating earlier:

$\textstyle{0\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{H}_{1}(F_{\leq
M},F_{\leq-M})/\mbox{im}(f)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{H}_{0}(F_{\leq-M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{H}_{0}(F_{\leq
M})/\mbox{ker}(h)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$

we obtain $n_{-}-n_{+}\leq\mbox{rk}(H_{1}(F_{\leq
M},F_{\leq-M}))\leq\mbox{rk}(H_{*}(F_{\leq M},F_{\leq-M}))$, so we conclude
that $|n_{-}-n_{+}|\leq\mbox{rk}(H_{*}(F_{\leq M},F_{\leq-M}))$, as desired. ∎

The following conjecture, which we will explore in future work, motivates our
choice of the terminology coarse.

######  Conjecture 7.2.

The coarse bounded sublevel $H$–complexity (resp., the coarse bounded
superlevel $H$–complexity) of $F$ is a lower bound for the global
$H$–complexity of $F$.

We close this section with a brief investigation of the coarse bounded
$H$–complexity for shallow networks, focusing on the case of input dimension
$2$, where we prove a sharp upper bound in the generic, transversal case.

######  Proposition 7.3.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a finite PL function, all of
whose nontransversal thresholds are contained in the interval $(-M,M)$. The
inclusions $i_{M}:F_{=M}\rightarrow F_{\geq M}$ and $i_{-M}:F_{=-M}\rightarrow
F_{\leq-M}$ induce isomorphisms on homology.

###### Proof.

We will give the proof for the statement about the inclusion $i_{M}$. The
proof for the statement about $i_{-M}$ is analogous.

Theorem 1 tells us that for every $N>M$, the inclusion $F_{=M}\rightarrow
F_{\in[M,N]}$ is a homotopy equivalence and hence induces an isomorphism on
homology. This tells us that $H_{*}(F_{\in[M,N]},F_{=M})\cong 0$. But by
excision we also have isomorphisms on the homology of the pairs

$H_{*}(F_{\geq M},F_{=M})\cong H_{*}(F_{\in[M,N]},F_{=M}),$

which tells us that the inclusion map $i_{M}:F_{=M}\rightarrow F_{\geq M}$ in
the long exact sequence on the relative homology of the pair, $(F_{\geq
M},F_{=M})$, induces an isomorphism on homology, as desired. ∎

######  Lemma 7.4.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}\rightarrow\mathbb{R}$ be a
generic, transversal, shallow ReLU neural network function with $m>n-1$. There
are $2{m\choose n-1}$ unbounded $1$–cells in $\mathcal{C}(F)$ and

$2\cdot\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}{m\choose 2k+1}$

unbounded $n$–cells.

###### Proof.

Since $F$ has a single hidden layer, $\mathcal{C}(F)=\mathcal{C}(\mathcal{A})$
for a generic arrangement of $m$ hyperplanes in $\mathbb{R}^{n}$. There are
${m\choose n-1}$ $1$–dimensional flats, and because the polyhedral complex is
pointed when $m>n-1$, every $1$–cell has at least one $0$–cell in its
boundary, so there are $2$ unbounded $1$–cells contained in every
$1$–dimensional flat. The expression for the number of unbounded $n$–cells
comes from Zaslavsky’s theorem (cf. [13, Thm. 2.5]), which tells us that for a
generic arrangement of $m$ hyperplanes in $\mathbb{R}^{n}$, there are
$\sum_{k=0}^{n}{m\choose k}$ regions and $\sum_{k=0}^{n}(-1)^{k}{m\choose k}$
bounded regions. The difference,
$2\cdot\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}{m\choose 2k+1}$, is
the number of unbounded regions. ∎

Let $\mathcal{C}$ be a pointed polyhedral decomposition of $\mathbb{R}^{n}$.
We will call two unbounded $1$–cells $C\neq C^{\prime}$ adjacent if there
exists an unbounded $2$–cell in $\mathcal{C}$ with facets $C,C^{\prime}$.

Now suppose $\mathcal{C}$ carries a partial orientation for which the
unbounded $1$–cell $C$ is oriented towards (resp., away from, resp.,
unoriented with respect to) its unique boundary vertex. The oriented path
component of $C$ is the maximal set of unbounded $1$–cells containing $C$ that
is both closed under adjacency and contains only unbounded $1$–cells whose
partial orientation matches that of $C$.

######  Proposition 7.5.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}\rightarrow\mathbb{R}$ be a
generic, transversal ReLU neural network function with $m>n$ whose
nontransversal thresholds are all in the interval $(-M,M)$. If
$H_{*}(F_{\leq-M})$ and $H_{*}(F_{\geq M})$ are both supported in degree $0$
and every path component of $F_{\leq M}$ meets $F_{\leq-M}$, then the coarse
bounded sublevel $H$–complexity (resp., coarse bounded superlevel
$H$–complexity) is concentrated in degree $1$ and is one less than the number
of oriented path components of $-$ (resp., $+$) unbounded $1$–cells.

###### Proof.

We will give the proof of the statement about the coarse bounded sublevel
$H$–complexity. The proof of the statement about the coarse bounded superlevel
$H$–complexity is analogous.

Note first that since $F$ is generic and $m>n$, every path component of
$F_{\leq-M}$ contains unbounded $1$–cells. Moreover, since $H_{*}(F_{\leq-M})$
is supported in degree $0$, there is a one-to-one correspondence between path
components of $F_{\leq-M}$ and oriented path components of “$-$”-unbounded
$1$–cells.

Now consider the Mayer-Vietoris sequence applied to $F_{\leq M}\cup F_{\geq
M}=\mathbb{R}^{n}$. Noting that $F_{=M}=F_{\leq M}\cap F_{\geq M}$,
Proposition 7.3 then tells us that $H_{*}(F_{\leq M})\cong
H_{*}(\mathbb{R}^{n})$ has the homology of a point.

Since $H_{*}(F_{\leq-M})$ and $H_{*}(F_{\leq M})$ are concentrated in degree
$0$, the long exact sequence of the pair $(F_{\leq M},F_{\leq-M})$ is $0$
outside of the following range:

$\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
32.22527pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise
0.0pt\hbox{$\textstyle{H_{1}(F_{\leq
M},F_{\leq-M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
33.46928pt\raise 6.1111pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 56.22527pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
56.22527pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
1.0pt\raise
0.0pt\hbox{$\textstyle{H_{0}(F_{\leq-M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
104.75142pt\raise 5.1875pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.8264pt\hbox{$\scriptstyle{g}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 122.01305pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
122.01305pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
1.0pt\raise 0.0pt\hbox{$\textstyle{H_{0}(F_{\leq
M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
175.04996pt\raise 5.43056pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.43056pt\hbox{$\scriptstyle{h}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 185.93416pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
185.93416pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
1.0pt\raise 0.0pt\hbox{$\textstyle{H_{0}(F_{\leq
M},F_{\leq-M})}$}}}}}}}\ignorespaces}}}}\ignorespaces.$

Since every path component of $F_{\leq M}$ meets $F_{\leq-M}$, the map $h$
induced by the inclusion map $F_{\leq-M}\rightarrow F_{\leq M}$ is surjective,
so $H_{0}(F_{\leq M},F_{\leq-M})\cong 0$, and the coarse bounded sublevel
$H$–complexity is concentrated in degree $1$. Since the alternating sum of the
ranks of the terms in a long exact sequence is $0$, we conclude that the
coarse bounded sublevel $H$–complexity is
$\mbox{rk}(H_{0}(F_{\leq-M}))-\mbox{rk}(H_{0}(F_{\leq M}))$, which is one less
than the number of oriented path components of “$-$” unbounded $1$–cells, as
desired.

∎

######  Remark 7.6.

It is not in general true that if all nontransversal thresholds of a ReLU
neural network function $F:\mathbb{R}^{n_{0}}\rightarrow\mathbb{R}$ are in are
in the interval $(-M,M)$, then $H_{*}(F_{\leq-M})$ and $H_{*}(F{\geq M})$ are
both supported in degree $0$.

We construct a ReLU neural network function $F:\mathbb{R}^{3}\to\mathbb{R}$
that demonstrates this.

First, fix any ReLU neural network $f$ with layer maps $f_{i}$

$f:\mathbb{R}^{2}\xrightarrow{f_{1}=\sigma\circ
A_{1}}\mathbb{R}^{n_{1}}\xrightarrow{f_{2}=\sigma\circ
A_{2}}\mathbb{R}^{n_{2}}\ldots\xrightarrow{}\mathbb{R}^{1}$

and threshold $t_{1}\in\mathbb{R}$ such that $f^{-1}([t_{1},\infty))$ is a
topological annulus. Define a new layer map
$\hat{f}_{1}:\mathbb{R}^{3}\to\mathbb{R}^{n_{1}}\times\mathbb{R}\cong\mathbb{R}^{n_{1}+1}$
so that

$\hat{f}_{1}(x_{1},x_{2},x_{3})=(f_{1}(x_{1},x_{2}),\sigma(x_{3}))$

for all $(x_{1},x_{2},x_{3})\in\mathbb{R}^{3}$. (If the matrix associated to
$f_{1}$ is

$A_{1}=\begin{bmatrix}w_{1,1}&w_{1,2}&b_{1}\\\ \vdots\\\
w_{n_{1},1}&w_{n_{1},2}&b_{n_{1}}\end{bmatrix}$

then the matrix

$\hat{A}_{1}=\begin{bmatrix}w_{1,1}&w_{1,2}&0&b_{1}\\\ \vdots\\\
w_{n_{1},1}&w_{n_{1},2}&0&b_{n_{1}}\\\ 0&0&1&0\\\ \end{bmatrix}$

determines such a map $\hat{f}_{1}$. ) Define another new layer map
$\hat{f}_{2}:\mathbb{R}^{n_{1}+1}\to\mathbb{R}^{n_{2}}$ so that

$\hat{f}_{2}(x_{1},\ldots,x_{n_{1}+1})=f_{2}(x_{1},\ldots,x_{n}),$

which can be accomplished by setting all weights associated to the $x_{n}$
coordinate to be $0$. Then the neural network map $F$ obtained by replacing
$f_{1}$ and $f_{2}$ by $\hat{f}_{1}$ and $\hat{f}_{2}$, respectively, has the
property that

$F_{\geq t}=f_{\geq t}\times\mathbb{R}.$

Furthermore, the canonical polyhedral complex $\mathcal{C}(F)$ is the
intersection complex of $\widehat{\mathcal{C}}(f)$ and the complex consisting
of the hyperplane $x_{3}=0$ and the two associated half spaces, where

$\widehat{\mathcal{C}}(f)\coloneqq\\{C\times\mathbb{R}\mid
C\in\mathcal{C}(f)\\}.$

By construction, the only $0$-cells of $\mathcal{C}$ are contained in the
plane $x_{3}=0$, and for any $M>0$, the sets $F_{\leq-M}$ and $F_{\geq M}$ are
both homotopic to $S^{1}\times\mathbb{R}$, and hence have nontrivial first
homology groups.

Of course, the map $F$ constructed as above is not generic, since the matrix
associated to $\hat{f}_{2}$ is singular (it has a row of all $0$s). However,
the same map $\mathbb{R}^{3}\to\mathbb{R}$ is obtainable as a generic neural
network map by performing a slightly more complicated set of modifications to
$f$.

######  Proposition 7.7.

Let $F:\mathbb{R}^{2}\rightarrow\mathbb{R}^{m}\rightarrow\mathbb{R}$ be a
generic, transversal ReLU neural network function. The coarse bounded sublevel
and superlevel $H$–complexities are both tightlybounded above by $m-2$.

###### Proof.

Since $F$ is shallow, $\mathcal{C}(F)=\mathcal{C}(\mathcal{A})$ for the
arrangement of $m$ hyperplanes associated to the first layer map. Since $F$ is
generic, $\mathcal{A}$ is generic. So Lemma 7.4 tells us that there are $2m$
unbounded regions separated by $2m$ unbounded $1$–cells.

Moreover, the boundary of a sufficiently large closed ball will intersect all
$2m$ unbounded regions and their $2m$ separating unbounded $1$–cells. Endow
the boundary of such a ball with a distinguished marked point in the interior
of one of the regions. By relabeling the hyperplanes in $\mathcal{A}$ if
necessary, we may assume without loss of generality that the unbounded
$1$–cells we meet as we traverse the boundary of the closed ball in the
clockwise direction are in $H_{1},H_{2},\ldots,H_{m},$ then again
$H_{1},H_{2},\ldots,H_{m}$. Accordingly, as we traverse the boundary of the
closed ball clockwise, we will label the edges
$e_{1},\ldots,e_{m},e_{1}^{\prime},\ldots,e_{m}^{\prime}$. See Figure 8.

Figure 8. The unbounded $1$–cells of the polyhedral complex
$\mathcal{C}(\mathcal{A})$ associated to an arrangement of $m$ hyperplanes in
$\mathbb{R}^{2}$ are in two-to-one correspondence with the $m$ hyperplanes.
Accordingly, we label the edges
$e_{1},\ldots,e_{m},e_{1}^{\prime},\ldots,e_{m}^{\prime}$ as we clockwise-
traverse the boundary of a sufficiently large ball enclosing all $0$–cells.

Now note that for a given choice of co-orientations on the set $\mathcal{A}$
(and assuming that the hyperplanes are indexed as indicated above), the
ternary labelings assigned to the unbounded $1$–cells are completely
determined by the ternary labeling on the chosen marked region.

We will first give a construction that achieves the stated upper bound on the
semi-infinite global $H$–complexity. Then we will prove that we cannot do any
better.

Choose the all $+$ ternary labeling on the marked region. Then the assignment
of ternary labelings to the edges $e_{1},\ldots,e_{m}$ is as follows:

$\displaystyle e_{1}$ $\displaystyle\rightarrow$
$\displaystyle(0,+,\ldots,+),$ $\displaystyle e_{2}$
$\displaystyle\rightarrow$ $\displaystyle(-,0,+,\ldots,+),$ $\displaystyle
e_{3}$ $\displaystyle\rightarrow$ $\displaystyle(-,-,0,+,\ldots,+),$
$\displaystyle\ldots$ $\displaystyle e_{m}$ $\displaystyle\rightarrow$
$\displaystyle(-\ldots,-,0).$

Note also that the ternary labeling on $e_{i}^{\prime}$ has the opposite sign
in all positions to the ternary labeling on $e_{i}$, so the labelings on
$e_{1}^{\prime},\ldots,e_{m}^{\prime}$ are:

$\displaystyle e_{1}^{\prime}$ $\displaystyle\rightarrow$
$\displaystyle(0,-,\ldots,-),$ $\displaystyle e_{2}^{\prime}$
$\displaystyle\rightarrow$ $\displaystyle(+,0,-,\ldots,-),$ $\displaystyle
e_{3}^{\prime}$ $\displaystyle\rightarrow$ $\displaystyle(+,+,0,-,\ldots,-),$
$\displaystyle\ldots$ $\displaystyle e_{m}$ $\displaystyle\rightarrow$
$\displaystyle(+\ldots,+,0).$

If we then choose a weight vector $\vec{w}^{(2)}=[w_{1},\ldots,w_{m}]$ for the
second layer map for which

  * •

$w_{1}=-1$,

  * •

$|w_{i}|=2$ for all $2\leq i\leq m-1$,

  * •

$\mbox{sgn}(w_{i})=-1^{i}$ for all $2\leq i\leq m-1$, and

  * •

$w_{m}=-1^{m},$

then it follows that $e_{m},e_{1}^{\prime}$ are unoriented, and the sign of
the $\nabla F$ orientation on the other unbounded $1$–cells
$e_{i},e_{i}^{\prime}$ are $-$ (resp., $+$) oriented if $i\equiv 0\mod 2$
(resp., $i\equiv 1\mod 2$).

We therefore see that the number of negatively-oriented path components is
$m-1$. To alternatively obtain a $\nabla F$ orientation on the unbounded
$1$–cells with $m-1$ positively-oriented path components, we can simply
reverse all signs on $\vec{w}^{(2)}$.

We now claim that we cannot achieve a higher $-$ (resp., $+$) infinite global
$H$–complexity. To see this, note that if we choose any other ternary tuple
$\vec{\theta}$ for the marked region, there will be at least one $i$ for which
$\mbox{sgn}(\theta_{i})\neq\mbox{sgn}(\theta_{i+1})$. Since the ternary labels
on opposite unbounded $1$–cells have opposite sign, we may assume without loss
of generality–by switching the roles of $e_{i}$ and $e_{i}^{\prime}$ if
necessary–that $e_{i}=+$ and $e_{i+1}=-$.

Now let $\vec{\theta}=(\vec{\eta},+,-,\vec{\omega})$ represent the ternary
tuple assigned to the region immediately preceding $e_{i}$, so that the
labelings on $e_{i}$ then $e_{i+1}$ are $(\vec{\eta},0,-,\vec{\omega})$ then
$(\vec{\eta},-,0,\vec{\omega})$. It follows that the $\nabla F$ orientations
on $e_{i}$ and $e_{i+1}$ must be the same, regardless of the choice of
$\vec{w}^{(2)}$.

There are then two cases to consider: either $e_{i}$ and $e_{i+1}$ are both
unoriented, or they are both oriented.

If $e_{i}$ and $e_{i+1}$ are both unoriented, then the maximum possible number
of alternations of orientation as one traverses the unbounded $1$–cells (where
the three possible assignments are negative, positive and unoriented) is
$2(m-1)$, as in the construction above. Since one of the path components is
unoriented, the maximal number of negative-oriented (resp., positive-oriented)
path components is at most $m-1$.

If $e_{i}$ and $e_{i+1}$ are both oriented (necessarily with the same
orientation), we see that of the remaining $2(m-1)$ unbounded $1$–cells there
can be at most $2(m-1)-1$ alternations of sign and hence at most $2m-2$
alternations in sign among all of the unbounded $1$–cells because of parity.
We again conclude that there are at most $m-1$ negative (resp., positive) path
components of unbounded $1$–cells.

Since $H_{*}(F_{\leq-M})$ and $H_{*}(F_{\geq M})$ are both supported in degree
$0$ for sufficiently large $M$, an application of Proposition 7.5 then yields
the desired conclusion. ∎

###  7.2. Upper bounds on global H-complexity

It does not follow immediately from the definitions that stable sublevel and
superlevel $H$–complexity and local $H$–complexity are finite for a finite PL
map $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$, since they are defined in terms
of singular homology, and the spaces under consideration are noncompact.
However, Theorems 3 and 4 tell us that we have homotopy-equivalent compact
models for these spaces, and hence all homological invariants described
throughout this work can be computed via simplicial homology using finite
simplicial complexes. We will leave more precise statements and algorithms to
the sequel and content ourselves here with an immediate bound and a
conjecture. Note that the class of ReLU neural network functions (of arbitrary
complexity) is precisely the class of finite PL functions
$F:\mathbb{R}^{n}\rightarrow\mathbb{R}$.

We have the following immediate corollary of Theorem 4:

######  Corollary 7.8 (Corollary of Theorem 4).

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a finite PL map with associated
polyhedral decomposition $\mathcal{C}$. The number of homotopy equivalence
classes of sublevel sets of $F$ is bounded above by one more than the number
of flat cells of $F$. If $\mathcal{C}$ is pointed, the latter is bounded above
by the number of $0$–cells of $F$.

######  Remark 7.9.

One might naïvely assume that the the the number of homotopy-equivalence
classes of sublevel sets of $F$ is also bounded above by the global
$H$–complexity of $F$. This is unfortunately false because of the existence of
nontrivial integer homology cobordisms in many dimensions, which implies that
the homotopy equivalence class of a sublevel set can change across a connected
component of flat cells $K$, even if the local $H$–complexity at $K$ is $0$.
See, e.g., [7].

We make the following natural conjecture:

######  Conjecture 7.10.

Let $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a ReLU neural network map with
canonical polyhedral decomposition, $\mathcal{C}(F)$. With probability $1$,
the total $H$–complexity of $F$ is less than or equal to the number of
$0$–cells of $\mathcal{C}(F)$.

Note that it is not hard, using the techniques introduced in Section 8, to
construct examples of PL maps with a single $0$–cell with high local
complexity. The belief expressed in the conjecture above is that this behavior
is highly atypical, and for ReLU neural network functions the local
$H$–complexity of any connected component of flat cells is bounded above by
the number of $0$–cells contained in the cell.

######  Remark 7.11.

We conjecture that for any reasonable class of finite PL functions, a $0$–cell
is far more likely to be PL regular than PL critical. We make this statement
precise for $0$–cells of shallow generic, transversal ReLU neural networks in
the sequel.

##  8\. Local $H$–complexity can be arbitrarily large

In this section, we present examples illustrating the phenomenon that the
local $H$–complexity of a ReLU neural network can be arbitrarily large.

We begin by establishing a few constraints on the $\nabla F$-orientations of
the $1$–complex of $\mathcal{C}(F)$.

######  Lemma 8.1.

Let $F:\mathbb{R}^{n}\to\mathbb{R}$ be a ReLU neural network. Suppose $C$ is a
flat, top-dimensional cell of $\mathcal{C}(F)$ and let $C^{\prime}$ be a top-
dimensional cell of $\mathcal{C}(F)$ such that $C\cap C^{\prime}$ is a mutual
facet $D$. Then any pair $E_{1},E_{2}$ of edges of $C^{\prime}$ with one
vertex in $C$ satisfy the condition that $E_{1}$ and $E_{2}$ have the same
induced orientation by $F$ (that is, they are both oriented outwards or both
oriented inwards).

###### Proof.

Let $x_{1}$ and $x_{2}$ be points on $E_{1}$ and $E_{2}$ which are not
vertices of $\mathcal{C}(F)$. Now, $x_{1},x_{2}$ are points in $C^{\prime}$
which are not in $C$. Suppose $F(x_{1})>F(C)$. Then we must also have
$F(x_{2})>F(C)$. Supposing otherwise leads to a contradiction: If
$F(x_{2})=F(C)$ then $C^{\prime}$ has a facet with $F(C^{\prime})=F(C)$ and a
point $x_{2}$ with $F(x_{2})=F(C)$, so as $F$ is affine, $F(C^{\prime})$ must
be constant. This contradicts the assumption that $F(x_{1})>F(C)$. Similarly,
if $F(x_{2})<F(C)$ then by the intermediate value theorem there is a point $x$
on the line segment between $x_{1}$ and $x_{2}$ satisfying $F(x)=F(C)$. As
$C^{\prime}$ is convex, $x\in C^{\prime}$. As $F(C^{\prime})$ is constant on
$D$ and on a point $x$ not in $D$ then $F$ must be constant on $C^{\prime}$,
again a contradiction. This means that if $F(x_{1})>F(C)$ then $F(x_{2})>F(C)$
as well, and $E_{1}$ and $E_{2}$ have the same induced orientation.The same
argument applies if $F(x_{1})<F(C)$.

Lastly, if $F(x_{1})=F(C)$, as seen before, $C^{\prime}$ must also be a flat
cell, and so both edges are assigned no orientation.
∎

######  Lemma 8.2.

Suppose $F_{1}:\mathbb{R}^{n}\to\mathbb{R}^{m}$, is a generic layer map which
realizes an $n$-dimensional flat cell $C$. Let $\mathcal{E}$ be the set of
equivalence classes of edges of $\mathcal{C}$ with one vertex in $C$, under
the equivalence that $[E_{1}]=[E_{2}]$ if and only if $E_{1}$ and $E_{2}$ are
both edges of the same $n$-cell $C^{\prime}$ with $D=C^{\prime}\cap C$ being a
mutual facet.
Let $s:\mathcal{E}\to\\{-1,1\\}$ be any function. Then it is possible to
select an affine map $G_{s}:\mathbb{R}^{m}\to\mathbb{R}$ in such a way that if
$E$ is an edge in $\mathcal{C}$ with one vertex in $C$, the neural network
$F_{s}=G_{s}\circ F_{1}$ satisfies the condition that $F_{s}(E\backslash C)>0$
if and only if $s([E])=1$ and $F_{s}(E\backslash C)<0$ if and only if
$s([E])=-1$.

###### Proof.

If $F:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is a generic layer map with a top-
dimensional flat cell, we have established in Lemma 3.13 that
$C=H_{1}^{-}\cap...\cap H_{m}^{-}$. Without loss of generality, we treat $C$
as if it has $m$ facets given by $H_{i}\cap C$; if it has fewer than $m$
facets, and if hyperplane $H_{i}$ is a hyperplane in the arrangement
$\mathcal{A}_{1}$ associated to $F_{1}$ which is not a supporting hyperplane
of $C$, then all cells in the star of $C$ are contained in $H_{i}^{-}$ and are
sent to zero in coordinate $i$ under $F_{1}$. We could therefore construct a
layer $F_{1}^{\prime}$ with all output coordinates of the affine map $A_{1}$
corresponding to nonsupporting hyperplanes of $C$ set equal to zero, by
setting their weights equal to zero. This new layer is equal to $F_{1}$ on all
points in cells in the star of $C$. If $G:\mathbb{R}^{m}\to\mathbb{R}$ is an
affine second layer, its restriction to the nonzero input coordinates
completely determines the induced orientations on edges incident to $C$ in
both $F_{1}$ and $F_{1}^{\prime}$, so we may define $G^{\prime}$ on this
subspace and choose an arbitrary affine extension of $G^{\prime}$ to
$\textrm{R}^{m}$ for the result. We note that by deleting the zero coordinates
of $\textrm{R}^{m}$ we obtain a smaller network with the dimension of the
hidden layer equal to the number of facets of $C$ with equivalent orientations
on edges incident to $C$.

Now under these assumptions, $C=H_{1}^{-}\cap...\cap H_{m}^{-}$ is sent to the
origin by $F_{1}$ and it has $m$ facets given by $H_{i}\cap C$ for
$i\in\\{1,...,m\\}$.

If $m<n$ then we are done as there there are no vertices and therefore no
edges in $\mathcal{C}(F)$ which have a vertex in $C$ to be assigned
orientations, so consider the case that $m\geq n$. The equivalence classes
used to define $\mathcal{E}$ are well-defined. Letting $\vec{r_{i}}$ be a
length-$m$ string with a single $1$ in position $i$ and $-1$ elsewhere, we see
immediately $R_{\vec{r_{i}}}$, which is a nonempty $n$-cell given by
$H_{1}^{-}\cap...\cap H_{i}^{+}\cap...\cap H_{m}^{-}$, shares a facet with $C$
given by $H_{i}\cap C$. Additionally, every region which shares a facet with
$C$ is equal to $R_{\vec{r_{i}}}$ for some $i$ as the facets of $C$ are
precisely $H_{i}\cap C$. No edge representing an element of $\mathcal{E}$
belongs to both $R_{\vec{r_{i}}}$ and $R_{\vec{r_{j}}}$ for $i\neq j$ because
any point in $R_{\vec{r_{i}}}\cap R_{\vec{r_{j}}}$ must be in $R_{\vec{-1}}$.

Furthermore, every edge $E$ incident to $C$ is an edge of $R_{\vec{r_{i}}}$
for some $i$. Suppose $E$ is incident to $C$. Then it has a vertex $v$ given
by $E\cap C$. By the genericity of $A_{1}$, $v$ is contained in $n$ of the
hyperplanes $H_{1},...H_{m}$. To be a vertex of $C$, it must additionally have
a $-1$ ternary coding relative to the $m-n$ remaining hyperplanes. As the
remaining $m-n$ hyperplanes do not meet $v$, $E$ also has a $-1$ labeling with
respect to the remaining $m-n$ hyperplanes, and is contained in $n-1$ of the
$n$ hyperplanes which intersect to form $v$. Let $H_{i}$ be the hyperplane
containing $v$ but not $E$. If $E$ was contained in $H_{i}^{-}$, then $E$
would be an edge of $C$ and not incident to $C$. So, $E$ is contained in
$H_{i}^{+}$. So, we may identify $E$ as being an edge contained in the closure
of $H_{i}^{+}\cap\left(\bigcap_{j\neq i}H_{j}^{-}\right)$, and so $E$ is an
edge of $R_{\vec{r_{i}}}$.

Next we note that $R_{\vec{r_{i}}}$, is sent, by the map $F_{1}$, to
coordinates on the $i$th positive axis in $\mathbb{R}^{m}$. For each
$i\in\\{1,...,m\\}$, select $E_{i}$ to be an edge of $R_{\vec{r_{i}}}$ with
exactly one vertex in $C$. Note that $\mathcal{E}=\\{[E_{i}]\\}_{1\leq i\leq
m}$. As $E_{i}$ is an edge of $R_{\vec{r_{i}}}$, we have that $E_{i}\subseteq
H_{j}^{-}$ for all $j\neq i$. If $x\in E_{i}$ then
$F_{1}(x)$=$(0,0,...,c,...,0)$ where $c$ is a positive real number in
coordinate $i$. That is, $x=c\vec{e_{i}}$, where $\vec{e_{i}}$ is the $i$th
standard unit coordinate vector in $\mathbb{R}^{m}$.

We now show that by selecting $G_{s}:\mathbb{R}^{m}\to\mathbb{R}$
appropriately, we may induce the desired orientation on the edges $E_{i}$. We
may use $s$ to define $\vec{s}\in\mathbb{R}^{m}$ by

$\vec{s}=\sum_{i=1}^{m}s([E_{i}])\vec{e}_{i}.$

Define $G_{s}:\mathbb{R}^{m}\to\mathbb{R}$ by
$G_{s}(\vec{x})=\vec{x}\cdot\vec{s}$, without a ReLU activation, as this is
the final layer of the neural network we are defining.

Define $F_{s}$ to be the two-layer neural network given by $G_{s}\circ F_{1}$.
Note that $F_{s}(C)=0$ identically as $F_{1}(C)$ is the origin, which is
preserved by $G_{s}$. For $x_{i}\in E_{i}$, we note that if
$F_{s}(x_{i})>F_{s}(C)=0$ the induced orientation on $E_{i}$ is “outwards”,
and if $F_{s}(x_{i})<F_{s}(C)=0$ the induced orientation on $E_{i}$ is
“inwards”. With $F_{s}$ defined in this way, we do indeed achieve these
orientations:

$\displaystyle F_{s}(\vec{x}_{i})$
$\displaystyle=c(\vec{e_{i}}\cdot\vec{s_{i}})$ $\displaystyle=s([E_{i}])c$

As $c$ was a positive real number then if $s([E_{i}])=-1$ then indeed
$s([E_{i}])c<0=F_{s}(C)$ and if $s([E_{i}])=1$ then $s([E_{i}])c>0=F_{s}(C)$
as desired. ∎

Figure 9. If $F_{1}$ is as pictured, then selecting $\vec{s}=(1,1,1)$ yields
$G:\mathbb{R}^{3}\to\mathbb{R}$ given by taking the inner product with
$\vec{s}$. We may select $\vec{s}$ to be in any octant, with each octant
giving a different combination of induced orientations on the pairs of colored
edges.

######  Lemma 8.3.

For each $n\in\mathbb{N}$, there is a shallow ReLU neural network
$F:\mathbb{R}^{2}\to\mathbb{R}^{2n+2}\to\mathbb{R}$, such that
$\mathcal{C}(F)$ contains a flat cell $C$ with local complexity $n$.

###### Proof.

Define $F_{1}:\mathbb{R}^{2}\to\mathbb{R}^{2n+2}$ using the affine map $A_{1}$
with weights and biases given for $j\in\\{1,\ldots,2n+2\\}$:

$\left(w_{j}^{(1)}\;|\;b_{j}^{(1)}\right)=\left(\sin\left(\frac{\pi
j}{n+1}\right),\cos\left(\frac{\pi j}{n+1}\right)\Big{|}-1\right)$

Then define $G:\mathbb{R}^{2n+2}\to\mathbb{R}$ with

$\left(w^{(2)}\;\big{|}\;b^{(2)}\right)=\left(-1,1,-1,...,1,-1|\;0\right).$

Let $F=G\circ F_{1}$.

We observe we may identify $H_{j}$ with the line tangent to the point on the
unit circle at angle $\pi j/(n+1)$, co-oriented ‘outward’ (away from the
origin). Let $C$ be the flat $(2n+2)-$gon containing the origin, which
satisfies $F(C)=0$. We may let $N(C)$ be a disc of radius $r$ centered at the
origin, where $1<r<\left(\cos\left(\frac{\pi}{n+1}\right)\right)^{-1}$. Note
that $N(C)$ contains no other vertices of $\mathcal{C}(F)$ except those of
$C$.

Now consider $R_{j}$, the region given by

$R_{j}=N(C)\cap H_{j}^{+}\cap\left(\bigcap_{i\neq j}H_{i}^{-}\right)$

If $j$ is even, $F(R_{j})>0$. Likewise, if $j$ is odd, $F(R_{j})<0$. As a
result, for small $\epsilon>0$, $F^{-1}(-\infty,-\epsilon]\cap N(C)$ has $n+1$
connected components whereas $F^{-1}(-\infty,\epsilon]\cap N(C)$ is connected.
Since attaching a PL handle may remove at most one connected component, at
least $n$ handles must be attached to $F^{-1}(-\infty,-\epsilon]\cap N(C)$ to
obtain a PL manifold homeomorphic to $F^{-1}(-\infty,\epsilon]\cap N(C)$.
Thus, the local complexity of $C$ is at least $n$.

Finally, it is sufficient to add $n$ handles, as pictured below in the case
when $n=2$.

∎

Figure 10. Example when $n=2$. Top Left: the polyhedral complex
$\mathcal{C}(F)$ with $C$, $R_{1}$ and $H_{1}$ distinguished. The circle
bounds $N(C)$. $F$ is strictly positive in the pink cells, and strictly
negative in the blue cells. Top Right: The sublevel set
$F^{-1}(-\infty,-\epsilon]$ is shaded. Bottom Left: The sublevel set
$F^{-1}(-\infty,\epsilon]$ is shaded. Bottom Right: Two handles are attached
to $F^{-1}(-\infty,-\epsilon]\cap N(C)$ yielding a polyhedral complex which is
PL homeomorphic to $F^{-1}(-\infty,-\epsilon]\cap N(C)$.

######  Lemma 8.4.

The closure $K$ of the flat cell $C$ given in the previous lemma has local
$H_{1}$-complexity $n$, and its local $H_{i}$-complexity is zero for all
$i\neq 1$.

###### Proof.

We compute $H_{*}(F_{\leq 0},F_{\leq 0}\setminus K)$ We note by excision (cf.
[10]) that we may instead compute

$H_{*}(F_{\leq 0}\cap N(C),(F_{\leq 0}\setminus C)\cap N(C))$

Since $(F_{\leq 0}\setminus K)\cap N(C)$ is homotopy equivalent to $n+1$
points and $F_{\leq 0}\cap N(C)$ is homotopy equivalent to a point, applying
the long exact sequence for reduced homology gives us trivial relative
homology in all degrees except degree 1, where it induces an isomorphism

$H_{1}(F_{\leq 0}\cap N(C),(F_{\leq 0}\setminus K)\cap
N(C))\cong\tilde{H}_{0}((F_{\leq 0}\setminus K)\cap N(C))$

Thus, ${H}_{1}(F_{\leq 0},F_{\leq 0}\setminus K)\cong\mathbb{Z}^{n}$.

∎

## References

  * [1] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee.  Understanding deep neural networks with rectified linear units.  In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
  * [2] Thomas Banchoff.  Critical points and curvature for embedded polyhedra.  J. Differential Geometry, 1:245–256, 1967.
  * [3] Monica Bianchini and Franco Scarselli.  On the complexity of neural network classifiers: A comparison between shallow and deep architectures.  IEEE Trans. Neural Networks Learn. Syst., 25(8):1553–1565, 2014\.
  * [4] J. Elisenda Grigsby and Kathryn Lindsey.  On transversality of bent hyperplane arrangements and the topological expressiveness of ReLU neural networks.  Preprint: http://arxiv.org/abs/2008.09052, To appear: Siam Journal on Applied Algebra and Geometry, 2022.
  * [5] Branko Grünbaum.  Convex polytopes, volume 221 of Graduate Texts in Mathematics.  Springer-Verlag, New York, second edition, 2003.  Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler.
  * [6] Romain Grunert.  Piecewise Linear Morse Theory.  PhD thesis, Freie Universität Berlin, 2016.  https://refubium.fu-berlin.de/handle/fub188/12531.
  * [7] Romain Grunert, Wolfgang Kühnel, and Günter Rote.  PL Morse theory in low dimensions.  Preprint: https://arxiv.org/pdf/1912.05054.pdf, 2019.
  * [8] William H. Guss and Ruslan Salakhutdinov.  On characterizing the capacity of neural networks using algebraic topology.  CoRR, abs/1802.04443, 2018.
  * [9] Boris Hanin and David Rolnick.  Deep ReLU networks have surprisingly few activation patterns.  CoRR, abs/1906.00904, 2019.
  * [10] Allen Hatcher.  Algebraic topology.  Cambridge University Press, Cambridge, 2002.
  * [11] C. P. Rourke and B. J. Sanderson.  Introduction to piecewise-linear topology.  Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 69. Springer-Verlag, New York-Heidelberg, 1972.
  * [12] Alexander Schrijver.  Theory of linear and integer programming.  Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd., Chichester, 1986.  A Wiley-Interscience Publication.
  * [13] Richard P. Stanley.  An introduction to hyperplane arrangements.  In Geometric combinatorics, volume 13 of IAS/Park City Math. Ser., pages 389–496. Amer. Math. Soc., Providence, RI, 2007.
  * [14] Günter M. Ziegler.  Lectures on polytopes, volume 152 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1995.
  * [15] Afra Zomorodian and Gunnar Carlsson.  Computing persistent homology.  Discrete Comput. Geom., 33(2):249–274, 2005.


# DecideNet: Counting Varying Density Crowds
Through Attention Guided Detection and Density Estimation

Jiang Liu1, Chenqiang Gao2, Deyu Meng3, Alexander G. Hauptmann1
1Carnegie Mellon University
2Chongqing University of Posts and Telecommunications 3Xi’an Jiaotong
University
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In real-world crowd counting applications, the crowd densities vary greatly in
spatial and temporal domains. A detection based counting method will estimate
crowds accurately in low density scenes, while its reliability in congested
areas is downgraded. A regression based approach, on the other hand, captures
the general density information in crowded regions. Without knowing the
location of each person, it tends to overestimate the count in low density
areas. Thus, exclusively using either one of them is not sufficient to handle
all kinds of scenes with varying densities. To address this issue, a novel
end-to-end crowd counting framework, named DecideNet (DEteCtIon and Density
Estimation Network) is proposed. It can adaptively decide the appropriate
counting mode for different locations on the image based on its real density
conditions. DecideNet starts with estimating the crowd density by generating
detection and regression based density maps separately. To capture inevitable
variation in densities, it incorporates an attention module, meant to
adaptively assess the reliability of the two types of estimations. The final
crowd counts are obtained with the guidance of the attention module to adopt
suitable estimations from the two kinds of density maps. Experimental results
show that our method achieves state-of-the-art performance on three
challenging crowd counting datasets.

##  1 Introduction

The crowd counting task in the computer vision community aims at obtaining
number of individuals appearing in specific scenes. It is the essential
building block for high-level crowd analysis, including crowd monitoring [3],
scene understanding [41] and public safety management [5].

Figure 1: Ablation studies of detection and regression based crowd counting on
the ShanghaiTech PartB (SHB) dataset [42]. Detection reliability decreases
along with the increased crowd density, resulting in _underestimated_ counts
in those areas. Counts from density estimation tend to be _overestimated_ in
scenes with low densities. (a) Visualization of the detection results on a
image from a Faster R-CNN [25] detector. (b) The density map on the same image
from a CNN regression network [28]. (c) The median object detection scores
from the detector used in (a) versus the ground-truth counts. (d) The
predictions from the network used in (b) versus the true crowd counts.

Various methods have been proposed to tackle this problem. They could
generally be classified into detection and regression based approaches. The
detection based methods [8, 18, 34, 10, 43, 13] employ object detectors to
localize the position for each person. The number of detections is then
treated as the crowd count. Early works [8, 34, 10] employ low-level features
as region descriptors, followed by a classifier for classification. Benefiting
from the recent progress in object detection using deep neural networks [14,
25, 24, 12], in ideal images with relatively large individual sizes and sparse
crowd densities, detection based counting could surpass human performance.
Different from crowd counting by detection, regression based methods [19, 23,
40, 28, 42, 2] obtain the crowd count without explicitly detecting and
localizing each individual. Preliminary works directly learn the mapping
between features of image patches to crowd counts [19, 23, 40]. Recent
regression based works improve the performance with Convolutional Neural
Network (CNN) [2, 28, 42, 21, 22] to output density maps of image patches.
Integrating over the map will give the count for the patch. Regression based
methods usually work well in crowded patches since they can capture the
general density information by benefiting from the rich context in local
patches.

In real-world counting applications, the crowd density varies enormously in
spatial and temporal domains. In the spatial aspect, even in a same image, the
density in some regions may be much higher than those of others. In some
background regions, there may even be no person present. Meanwhile, it is also
natural for the crowd volume to change along with time: a business street may
have very high crowd volumes during the workdays, while the weekends
counterparts are much lower. Intuitively, here comes a question: _can crowd
counting exclusively based on either regression or detection be enough to
simultaneously handle high and low density scenes?_

To answer this question, we study the performance of two types of approaches
on the ShanghaiTech PartB (SHB) dataset [42] collected from real street scenes
with great variation in crowd densities. The result is illustrated in Figure
1. Figure 1(a) gives the detections from a fine-tuned Faster R-CNN head
detector on a specific image: with the distance to the camera increasing, the
crowd density and the number of missed detections rises. Figure 1(c) shows the
relationship between median detection scores and ground-truth counts for
10,000 image patches with sizes of $256\times 128$. It is clear that the score
drops rapidly with the rise of the ground-truth count. We may therefore find
that the reliability of detection based counting, reflected by the detection
score, is highly correlated to the crowd density. In scenes with sparse
crowds, the estimations are reliable, and the detection scores are also higher
than those of congested scenes. On the other hand, in crowded scenes, the
corresponding object sizes tend to be very small. Detection in these scenes is
less reliable, leading to low detection scores and recall rates. Consequently,
the predicted crowd counts will be _underestimated_ ; while the regression
based counting methods could perform better on these occasions. Figure 1(b)
provides the crowd density map visualization on the same image in (a),
outputted by a 5-layer CNN based regression network with similar structure
employed in [28]. We find that the estimations in remote congested areas are
quite reasonable. However, in background regions near the camera viewpoint,
there exist false alarm hot spots on the pavement. The relationship between
ground-truth counts and corresponding predictions is plotted in Figure 1(d).
Note that the prediction dots for patches with lower ground-truth counts are
mostly above the dashed line. This indicates that prediction counts in these
scenes are mostly larger than the ground-truth. Hence, being not aware of the
location of each individual, and directly applying the regression based
approaches to low density scenes may lead to _overestimated_ results.

Based on the above ablation analysis, we may find that the detection and
regression based counting approaches have their different strengths on
different crowd densities. The regression based method is preferred for
congested scenes. Without localization information for each person, applying
them to low density scenes tends to overestimate counts. The detection based
approach could localize and count each person precisely on these occasions
since they are expected settings for object detectors. However, its
reliability degenerates in crowded scenes due to small target sizes and
occlusion.

Therefore, we may find that a conventional crowd counting method which only
relies on either detection or regression is limited when handling real scenes
with unavoidable density variations. An ideal counting method, on the other
hand, should have an _adaptive_ ability to choose the appropriate counting
mode according to the crowd density: in low density scenes, it is expected to
count by localizing as an object detector; whereas in congested scenes, it
should behave in a regression manner. Motivated by this understanding, we
propose a novel crowd counting framework named as _DecideNet_ (_DE_ te _C_ t
_I_ on and _D_ ensity _E_ stimation _Network_), as shown in Figure 2. To the
best of our knowledge, _DecideNet_ is the first framework, which is capable of
perceiving the crowd density for each pixel in a scene and adaptively deciding
the relative weights for detection and regression based estimations.

In detail, for a given scene, the _DecideNet_ first estimates two kinds of
crowd densities maps by detecting individuals and regressing pixel-wise
densities, respectively. To capture the subtle variation in crowd densities,
an attention module _QualityNet_ is proposed to assess the reliability of two
types of density maps with the additional supervision of detection scores. The
final count is obtained under guidance from _QualityNet_ to allocate adaptive
attention weights for the two density maps. Parameters in our proposed
_DecideNet_ are end-to-end learnable by minimizing a joint loss function.

In summary, we make the following contributions:

  * •

We find that real-world crowd counting occasions are frequently faced with
great density variations. While existing estimation methods, which either rely
exclusively on detection or regression, are unable to provide precise
estimations along the whole density range.

  * •

Based on the complementary property of two types of crowd counting methods, we
design a novel framework _DecideNet_ , which can capture this variation and
estimate optimal counts by assigning adaptive weights for both detection and
regression based estimations.

  * •

Experimental results reveal that our method achieves state-of-the-art
performance on public datasets with varying crowd densities.

##  2 Related works

#### Crowd counting by detection.

Early works addressing the crowd counting problem major follow the counting by
detection framework. Region proposal generators [9, 33] are firstly used to
propose potential regions that include persons. Low-level features [8, 18, 27,
34] are then used for feature representation. Different binary classifiers
including Naive Bayes [4], Random Forest [23] and their variations [40, 11]
are trained with these features. The crowd count is the number of positive
samples outputted by the classifier on a test image. Global detection scores
are employed to estimate crowd densities and utilized for object tracking in
[26]. Recent approaches seek the end-to-end crowd counting solution by CNN
based object detectors [14, 25, 24, 7] and greatly improve the counting
accuracy. Though detection based crowd counting is successful for scenes with
low crowd density, its performance on highly congested environments is still
problematic. On these occasions, usually only partial of the whole objects are
visible, posing great challenge to object detectors for localization.
Therefore, part and shape based models are introduced in [10, 20, 39], where
ensembles of classifiers are built for specific body parts and regions.
Although these methods mitigate the issue in some degree, counting in evident
crowded scenes still remains challenging, since objects in those areas are too
small to be detected.

#### Crowd counting by regression.

Different from counting by detection, counting by regression estimates crowd
counts without knowing the location of each person. Preliminary works employ
edge and texture features such as HOG and LBP to learn the mapping from image
patterns to corresponding crowd counts [19, 23, 40]. Multi-source information
is utilized [15] to regress the crowd counts in extreme dense crowd images. An
end-to-end CNN model adopted from AlexNet is constructed [36] recently for
counting in extreme crowd scenes. Later, instead of direct regressing the
count, the spatial information of crowds are taken into consideration by
regressing the CNN feature maps as crowd density maps [41] . Observing that
the densities and appearances of image patches are of large variations, a
multi-column CNN architecture is developed for density map regression [42].
Three CNN columns with different receptive fields are explicitly constructed
for counting crowds with robustness to density and appearance changes. Similar
frameworks are also developed in [22], where a Hydra-CNN architecture is
designed to estimate crowd densities in a variety of scenes. Better
performance can be obtained by further exploiting switching structures [31,
28, 17] or contextual correlations using LSTM [29]. Though counting by
regression is reliable in crowded settings, without object location
information, their predictions for low density crowds tend to be
overestimated. The soundness of such kind of methods relies on the statistical
stability of data, while in such scenarios the instance number is too small to
help explore the its intrinsic statistical principle.

Figure 2: The architecture of our proposed _DecideNet_. Image patches are sent
to the _RegNet_ and _DetNet_ blocks for two types of density maps
$D_{i}^{reg}$ and $D_{i}^{det}$ estimation. The final density map
$D_{i}^{final}$ is outputted by the _QualityNet_ , which adaptively decides
the attention weight between two density maps for each pixel. Three blocks are
jointly learned on the training data.

##  3 Crowd Counting by DecideNet

###  3.1 Problem formulation

Our solution formulates the crowd counting task as a density map estimation
problem. It requires $N$ training images $I_{1},I_{2},\cdots,I_{N}$ as inputs.
For a specific image $I_{i}$, a collection of $c_{i}$ 2D points
$\textbf{P}_{i}^{gt}=\\{P_{1},P_{2},\cdots,P_{c_{i}}\\}$ is provided by the
dataset [6, 41, 42], indicating the ground-truth head positions in the image
$I_{i}$. The ground-truth crowd density map $D^{gt}_{i}$ of $I_{i}$ is
generated by convolving annotated points with a Gaussian kernel
$\mathcal{N}^{gt}(p|\mu,\sigma^{2})$ [22]. Therefore, the density at a
specific pixel $p$ of $I_{i}$ could be obtained by considering the effects
from all the Gaussian functions centered by annotation points, i.e.,

$\forall p\in
I_{i},D^{gt}_{i}(p|I_{i})=\sum_{P\in\textbf{P}_{i}^{gt}}\mathcal{N}^{gt}(p|\mu=P,\sigma^{2}).$
(1)

Summing over the density values of all pixels over the entire image $I_{i}$,
the total person count $c_{i}$ of $I_{i}$ can be acquired: $\sum_{p\in
I_{i}}D^{gt}_{i}(p|I_{i})=c_{i}$. For a counting model parameterized by
$\varOmega$, its objective is to learn a non-linear mapping for $I_{i}$,
whereas the difference between the prediction density map
$D_{i}^{out}(p|I_{i})$ and the ground-truth $D^{gt}_{i}(p|I_{i})$ is
minimized.

Traditional crowd counting by density estimation methods regress density maps
by minimizing the pixel-wise Euclidean loss to the ground-truth [36, 2, 42,
22]. However, as we have analyzed in introduction, counting by purely
regression would result in the _overestimation_ problem on occasions with low
crowd densities. Oppositely, counting by detection works comparably better in
those scenes, since low crowd density is the expecting environment to an
object detector.

In practical applications, the crowd density varies both spatially and
temporally. Hence, deciding the crowd counts exclusively based on either
regression or detection is insufficient. _DecideNet_ is motivated by their
complementary property to address this problem. As shown in Figure 2, instead
of counting people either by merely regressing density maps, or applying an
object detector over the whole image, _DecideNet_ simultaneously estimates
crowd counting with both detection and regression modules. Later, an attention
block is utilized to decide which estimation result should be adopted for a
specific pixel. Three CNN blocks are included in our framework: the _RegNet_ ,
the _DetNet_ and the _QualityNet_ , parameterized by
$\varOmega=(\varOmega_{det},\varOmega_{reg},\varOmega_{qua})$. The parameters
for three CNN blocks could be jointly learned on the training set.

###  3.2 The RegNet block

Figure 3: The _RegNet_ block consisting of 5 fully convolutional layers. It
outputs the crowd density map $D_{i}^{reg}$ of each pixel in image patches
without predicting the head locations.

The _RegNet_ block counts crowds in the absence of localizing each individual.
Without knowing the specific location of each head in the input image patch,
it directly estimates the crowd density for all the pixels in $I_{i}$ with a
fully convolutional network:

$\mathcal{F}^{reg}(I_{i}|\varOmega_{reg})=D_{i}^{reg}(p|\varOmega_{reg},I_{i}).$
(2)

As shown in Figure 3, the _RegNet_ block consists of 5 convolutional layers.
Because it is designed to capture the general crowd density information,
larger filters’ receptive fields will grasp more contextual details, which is
more beneficial for modeling the density maps. Therefore, in our implemented
_RegNet_ block, the “conv1” layer has 20 filters with a $7\times 7$ kernel
size. $40$ filters with a $5\times 5$ kernel size are set as the “conv2”
layer. In order to capture scale and orientation invariant person density
features, the “conv1” and “conv2” layers are followed by two $2\times 2$ max-
pooling layers. The “conv3” and “conv4” layers both have $5\times 5$ filter
sizes with 20 and 10 filters, respectively. Since the density estimation
result could be viewed as a CNN feature map with only one channel, we add a
“conv5” layer with only one filter and a “$1\times 1$” filter size. This layer
is responsible to return the regression based crowd density map $D_{i}^{reg}$,
in which value on each pixel represents the estimated count at that point. A
ReLU unit is applied after the “conv5” layer ensuring that the output density
map will not contain negative values.

###  3.3 The DetNet block

Figure 4: The proposed _DetNet_ block is built upon the Faster R-CNN network.
A Gaussian convolutional layer is plugged after the bounding box outputs to
generate the detection based crowd density map $D_{i}^{det}$.

To handle varying perspectives, crowd densities and appearances, existing
density estimation methods [41, 42, 28, 17] consist of several CNN structures
like the _RegNet_ block. However, without the prior knowledge about the exact
position of each person in the image patches, the network purely decides the
crowd density based on the raw image pixels. This regression methodology may
be accurate in image patches with relatively large crowd densities, while it
tends to overestimate the crowd counts in sparse or even “no-person”
(background) scenes. In our proposed _DecideNet_ architecture, the _DetNet_ is
designed to address this issue by generating the “location aware” detection
based density map $D_{i}^{det}$. The motivation is intuitive and simple:
sparse and non-crowded image patches are expected settings for present CNN
based object detectors. Therefore, compared to use regression networks to
count on these patches, using the prior knowledge from outputs of object
detectors should substantially relieve the overestimation problem.

The _DetNet_ block, illustrated in Figure 4 is built based on the above
assumption. It could be viewed as an extension of the Faster-RCNN network [14]
for head detection on the basis of the ResNet-101 architecture. To be
specific, we design a Gaussian convolutional layer and plug it after the
bounding box outputs of the original Faster-RCNN network. The Gaussian
convolutional layer employs a constant Gaussian function
$\mathcal{N}^{det}(p|\mu=P,\sigma^{2})$, to convolve over the centers of
detected bounding boxes $\textbf{P}_{i}^{det}$ on the original image patch.
The detection based density map $D_{i}^{det}$ is obtained by this layer, i.e.,

$D^{det}_{i}(p|\varOmega_{det},I_{i})=\sum_{P\in\textbf{P}_{i}^{det}}\mathcal{N}^{det}(p|\mu=P,\sigma^{2}).$
(3)

Since the pixel values of $D_{i}^{det}$ are obtained by considering the impact
from the points in detection output $\textbf{P}_{i}^{det}$, $D_{i}^{det}$ is a
“location aware” density map. Compared to $D_{i}^{reg}$ from the output of
$RegNet$, responses of $D_{i}^{det}$ are more concentrated on specific head
locations. The difference between them is obvious in $D_{i}^{reg}$ of Figure 3
and $D_{i}^{det}$ of Figure 4.

###  3.4 Quality-aware density estimation

Figure 5: The _QualityNet_ block: stacking two density maps and the original
image $I_{i}$ as input, it outputs a probabilistic attention map
$K_{i}(p|\varOmega_{qua},I_{i})$. The final density estimation $D_{i}^{final}$
is jointly determined by $K_{i}$, $D_{i}^{reg}$ and $D_{i}^{det}$.

Herein, we have described the details about obtaining two kinds of density
maps: $D_{i}^{reg}$ and $D_{i}^{det}$ for a given image $I_{i}$. The detection
based map $D_{i}^{det}$ employs object detection results for density
estimation. Therefore, it could count persons precisely in sparse density
scenes by localizing their head positions. However, counting via $D_{i}^{det}$
is not accurate on crowded occasions due to the low detection confidence
resulted from the small object size and occlusion. On the contrary, the
regression based map $D_{i}^{reg}$, which is unaware of individual locations,
is the preferred estimation for these scenes: the full convolutional network
is capable of capturing rich context crowd density information. Intuitively,
one may think that fusing $D_{i}^{reg}$ and $D_{i}^{det}$ by applying average
or max pooling [37] may obtain better results on varying density crowds.
Nevertheless, even in the same scene, the density may differ significantly in
different parts or time intervals. Therefore, the importance between
$D_{i}^{det}$ and $D_{i}^{reg}$ also changes correspondingly for instant pixel
values in $I_{i}$. In _DecideNet_ , we propose an attention block _QualityNet_
, shown in Figure 5 to model the selection process for optimal counting
estimations. It captures the different importance weight of two density maps
by dynamically assessing the qualities of them for each pixel.

For a given $I_{i}$, the _QualityNet_ block firstly upsamples $D^{det}_{i}$
and $D_{i}^{reg}$ to the same size of $I_{i}$. Then $D^{det}_{i}$,
$D_{i}^{reg}$ and $I_{i}$ are stacked together as the _QualityNet_ input with
5 channels. Four fully convolutional layers and a pixel-wise sigmoid layer is
followed to output a probabilistic attention map
$K_{i}(p|\varOmega_{qua},I_{i})$. We define the specific value of
$K_{i}(p|\varOmega_{qua},I_{i})$ at the pixel $p$ reflects the importance of
the detection based density map $D_{i}^{det}$, compared to the regression
counterpart $D_{i}^{reg}$. As a result, the _QualityNet_ block could decide
the relative _reliability_ (i.e., the quality) between $D_{i}^{det}$ and
$D_{i}^{reg}$. A higher $K_{i}(p|\varOmega_{qua},I_{i})$ at pixel $p$ means a
higher attention we should rely on the detection, rather than the regression
density estimation for $p$. Hence, we could further define the final density
map estimation $D^{final}_{i}(p|I_{i})$ as a weighted sum between two density
maps $D_{i}^{reg}$ and $D_{i}^{det}$, guided by the attention map $K_{i}$:

$\begin{split}D^{final}_{i}(p|I_{i})=&K_{i}(p|\varOmega_{qua},I_{i})\odot
D^{det}_{i}(p|\varOmega_{det},I_{i})+\\\
&(\textbf{J}-K_{i}(p|\varOmega_{qua},I_{i}))\odot
D_{i}^{reg}(p|\varOmega_{reg},I_{i}),\end{split}$ (4)

whereas $\odot$ is the Hadamard product for two matrices and the J is an all-
one-matrix with the same size of $K_{i}$.

##  4 Model Learning

Parameters of _DecideNet_ $\varOmega$ consist of three parts:
$\varOmega_{reg}$, $\varOmega_{det}$ and $\varOmega_{qua}$. Hence, we
generalize the training process as a multi-task learning problem. The overall
loss function $L_{decide}$, is given by Eq. (5):

$L_{decide}=L_{reg}+L_{det}+L_{qua},$ (5)

whereas the $L_{reg}$, $L_{det}$ and $L_{qua}$ are the losses for _RegNet_ ,
_DetNet_ and _QualityNet_ , respectively. $L_{decide}$ could be optimized via
Stochastic Gradient Descent with annotated training data. In each iteration,
gradients for $L_{reg}$, $L_{det}$ and $L_{qua}$ are alternatively calculated
and employed to update corresponding parameters. To be specific, for the loss
of the _RegNet_ component, we employ the pixel-wise mean square error as the
loss function. That is:

$L_{reg}=\dfrac{1}{N}\sum_{i}\sum_{p\in
I_{i}}\left[D_{i}^{reg}(p|\varOmega_{reg},I_{i})-D^{gt}_{i}(p|I_{i})\right]^{2},$
(6)

whereas $N$ is the total number of training images.

For the $DetNet$ block, different from the regression counterpart, the
responses on the density map $D_{i}^{det}$ mostly concentrate on the detected
head centers. Directly minimizing the difference between $D_{i}^{det}$ and
$D^{gt}_{i}$ involves in overwhelmed negative pixel samples, i.e., background
pixels without head detections. Hence, instead of using the pixel-wise
Euclidean loss as error measurement, we employ the bounding boxes as
supervision. In this way, optimizing $\varOmega_{det}$ is equivalent to
minimizing the classification and localization error in the original Faster
R-CNN [25]:

$\begin{split}L_{det}=\dfrac{1}{N}\sum_{i}\left[L_{cls}(\textbf{P}_{i}^{det},\textbf{P}_{i}^{gt}|\varOmega_{det})+L_{loc}(\textbf{P}_{i}^{det},\textbf{P}_{i}^{gt}|\varOmega_{det})\right].\end{split}$
(7)

Due to the fact that only the centers of individuals’ heads are provided as
the annotation on crowd density estimation datasets, we manually label the
bounding boxes on partial of the training set points. Later, we employ the
average width and height of them for the bounding box supervision in Eq. (7).

The loss function $L_{qua}$ for the attention module _QualityNet_ should
measure two kinds of errors. One is the difference between the final crowd
density map $D_{i}^{final}$ and the ground-truth density map $D_{i}^{gt}$.
This error is similar to that we have defined in $L_{reg}$. The second error
measures the quality of the output probabilistic map $K_{i}$ in _QualityNet_.
Recall that $K_{i}(p|\varOmega_{qua},I_{i})$ is the confidence of how reliable
the detection result is at pixel $p$ in the image $I_{i}$. As we analyzed in
Figure 1(c), this confidence could be reflected by the object detection score
$S^{det}(p|I_{i})$ at $p$. Therefore, we employ the Euclidean distances
between the probabilistic attention map $K_{i}$ and object detection score map
$S^{det}$ as the second error component in $L_{qua}$. From another
perspective, this error could be considered as a regularization term over the
_QualityNet_ parameters $\varOmega_{qua}$, by incorporating detection scores
as prior information. In experiment evaluation, we will show that this
regularization is indispensably beneficial to the performance of our proposed
$DecideNet$ architecture. Since the object detection qualities are brought
into this loss function, we name it as the “quality-aware” loss. The final
formulation of this loss $L_{qua}$ is defined as following:

$\displaystyle L_{qua}=$ $\displaystyle\dfrac{1}{N}\sum_{i}\sum_{p\in
I_{i}}\left\\{\left[D_{i}^{final}(p|\varOmega_{qua},I_{i})-D^{gt}_{i}(p|I_{i})\right]^{2}+\right.$
$\displaystyle\left.{}\lambda\lVert
K_{i}(p|\varOmega_{qua},I_{i})-S^{det}(p|I_{i})\rVert^{2}\Big{.}\right\\},$
(8)

where $\lambda$ is the hyper-parameter to balance the importance between two
errors.

##  5 Experimental Results

###  5.1 Evaluation settings

Our proposed method is evaluated on three major crowd counting datasets [6,
41, 42] collected from real-world surveillance cameras. For all datasets,
_DecideNet_ is optimized with 40k steps of iterations. We set the initial
learning rate at 0.005 and cut it by half in each 10k steps. Then the best
model is selected over the validation data. Instead of sending the whole image
to _DecideNet_ during training, we follow the strategy used in [28, 2, 22] to
crop images into $4\times 3$ patches. In this way, the number of samples for
training the regression network is boosted. Each patch is then augmented by
random vertical and horizontal flipping with a probability of $0.5$. We also
add uniform noise ranging in $[-5,5]$ on each pixel in the patch with a
probability of $0.5$ for data augmentation. To optimize the parameters for the
_RegNet_ and the _QualityNet_ , the ground-truth density maps are obtained by
applying the Gaussian kernel $\mathcal{N}^{gt}(p|\mu,\sigma^{2})$ with
$\sigma=4.0$ and a window size of 15. In each iteration, the object detection
score map $S^{det}(p|I_{i})$ is acquired by evaluating $I_{i}$ on the
_DetNet_. For each pixel $p$ in the detected bounding boxes, the value of
$S^{det}(p|I_{i})$ is filled with corresponding detection score. For the rest
of pixels which are not included in any bounding boxes, they are filled with a
default value set at 0.1. The score map is downsampled to the same size of
$K_{i}$ in order to calculate the “quality-aware” loss $L_{qua}$. We follow
the convention of existing works [32, 41, 23] to use the mean absolute error
(MAE) and mean squared error (MSE) as the evaluation metric. The MAE metric
reveals the accuracy of the algorithm for crowd estimation, while the MSE
metric indicates the robustness of estimation.

###  5.2 The Mall dataset

The Mall dataset [6] contains 2000 frames, collected in a shopping mall. Each
frame has a fixed resolution of $320\times 240$. We follow the pre-defined
settings to use the first 800 frames as the training set and the rest 1200
frames as the test set. The validation set is selected randomly from 100
images in the training set. We compare our _DecideNet_ with both detection
based approaches: SquareChn Detector [1], R-FCN [7], Faster R-CNN [25]; and
regression based approaches: Count Forest [23], Exemplary Density [38],
Boosting CNN [35], MoCNN [17], Weighted VLAD [30]. The evaluation results are
exhibited in Table 1.

Method | MAE | MSE
---|---|---
SquareChn Detector [1] | 20.55 | 439.1
R-FCN [7] | 6.02 | 5.46
Faster R-CNN [25] | 5.91 | 6.60
Count Forest [23] | 4.40 | 2.40
Exemplary Density [38] | 1.82 | 2.74
Boosting CNN [35] | 2.01 | N/A
MoCNN [17] | 2.75 | 13.40
Weighted VLAD [30] | 2.41 | 9.12
_DecideNet_ | 1.52 | 1.90
Table 1: Comparison results of different methods on the Mall dataset. The MAE
and MSE error of our proposed _DecideNet_ is significant lower than other
approaches.

From Table 1, we can observe the detection based approaches [1, 7, 25]
generally perform worse than the regression counterparts. Even the most recent
CNN based object detectors [7, 25] still have a large performance gap to the
CNN based regression approaches [35, 17, 30]. Our proposed _DecideNet_ obtains
the minimum error on both MAE and MSE metrics. Compared to the best approach
“Boosting CNN”, which based on regression, _DecideNet_ reveals 0.49 point
improvement on MAE metric. This is achieved without using the ensemble scheme
employed by the “MoCNN” and “Boosting CNN” methods. Moreover, the MSE metric
of the _DecideNet_ is merely 1.90. This is significantly lower than other
state-of-the-art methods, which either use detection or regression approach.
This gain rationally results from our density estimations formulated from both
detection and regression results.

###  5.3 The ShanghaiTech PartB dataset

Method | MAE | MSE
---|---|---
R-FCN [7] | 52.35 | 70.12
Faster R-CNN [25] | 44.51 | 53.22
Cross-scene [41] | 32.00 | 49.80
M-CNN [42] | 26.40 | 41.30
FCN [21] | 23.76 | 33.12
Switching-CNN [28] | 21.60 | 33.40
CP-CNN [31] | 20.1 | 30.1
_DecideNet_ | 21.53 | 31.98
_DecideNet+R3_ | 20.75 | 29.42
Table 2: Comparison results of different methods on the ShanghaiTech PartB
dataset.

We also perform the evaluation experiments on the ShanghaiTech PartB (SHB)
[42] crowd counting dataset, which is among the largest datasets captured in
real outdoor scenes. It consists of 716 images taken from business streets in
Shanghai, in which 400 of them are pre-defined training set and the rest are
the test set. Compared to the Mall dataset, it poses very diverse scene and
perspective types over greatly changing crowd densities. We use 50 randomly
selected images in the training set for validation. Since the resolution of
each image is $768\times 1024$, the patches are cropped from the original
image with a size of $256\times 256$ during training. Our evaluation result
and the comparison to other state-of-the-art methods are shown in Table 2. Due
to the large variation in density and object size on the SHB dataset, the
detection based approaches [7, 25] perform worse than the others relying on
regression. Specifically, the ensemble and fusion strategy is employed by the
M-CNN [42], Switching-CNN [28], CP-CNN [31] in Table 2. Compared to the Mall
dataset, the challenging SHB dataset leads to much higher MAE and MSE on all
the methods. Even though, our proposed method (_DecideNet_ ; _DecideNet+R3_ ,
which trained with an additional R3 stream in Switching-CNN) is very
competitive to existing approaches.

###  5.4 The WorldExpo’10 dataset

The WorldExpo’10 dataset [41] includes 1132 annotated video sequences
collected from 103 different scenes in the World Expo 2010 event. There are a
total number of 3980 frames with sizes normalized to $576\times 720$. The
patch size we used for training is $144\times 144$. The training set consists
of 3380 frames and the rests are used for testing. Since the Region Of
Interest (ROI) are provided for test scenes (S1-S5), we follow the fashion of
previous method [32] to only count persons within the ROI area. We use the
same metric, namely MAE, suggested by the author [41] for evaluation. The
results of our proposed approach on each test scene and the comparisons to
other methods are listed in Table 3.

Method | MAE
---|---
S1 | S2 | S3 | S4 | S5 | Ave
Cross-scene [41] | 2.00 | 29.50 | 9.70 | 9.30 | 3.10 | 12.90
M-CNN [42] | 3.40 | 20.60 | 12.90 | 13.00 | 8.10 | 11.60
Local&Global [29] | 7.80 | 15.40 | 15.30 | 25.60 | 4.10 | 11.70
CNN-pixel [16] | 2.90 | 18.60 | 14.10 | 24.60 | 6.90 | 13.40
Switching-CNN [28] | 4.40 | 15.70 | 10.00 | 11.00 | 5.90 | 9.40
_DecideNet_ | 2.00 | 13.14 | 8.90 | 17.40 | 4.75 | 9.23
Table 3: Comparison results of different methods on 5 scenes in the
WorldExpo’10 dataset.

From Table 3, we can notice that our proposed approach achieves an average MAE
at 9.23 across all 5 scenes. This is the best performance among those obtained
by all compared methods, revealing 0.17 improvement on the second best
“Switching-CNN” approach. It is not that significant, because our error on S4
is a little bit higher. The reason may lie on the fact that people in S4
majorly gather in crowds at remote areas, posing great challenge for the
$DetNet$ to output meaningful estimations. Therefore, the estimation on S4 are
mostly relied on the outputs from $RegNet$. While without the ensemble
regression structure, using the $RegNet$ only may not be able to exhibit the
superior counting precision. We can also notice that the prediction counts of
different state-of-the-art methods alter considerably on the 5 scenes,
revealing different approaches have their own strengths to specific scenes.
However, _DecideNet_ obtains three minimum MAE errors when compared to other
approaches. This indicates _DecideNet_ having a good generalization ability
and prediction robustness on different scenes.

Method | MAE | MSE
---|---|---
Mall | SHB | Mall | SHB
_RegNet_ only | 3.37 | 42.85 | 4.22 | 63.63
_DetNet_ only | 4.50 | 44.90 | 5.60 | 73.18
_RegNet_ +_DetNet_ (Late Fusion) | 3.93 | 38.63 | 4.96 | 65.27
_RegNet_ +_DetNet_ +_QualityNet_ | 1.83 | 24.93 | 2.27 | 41.86
_RegNet_ +_DetNet_ +_QualityNet_ (quality-aware loss) | 1.52 | 21.53 | 1.90 | 31.98
Table 4: Qualitative results of different _DecideNet_ components on the Mall
and SHB dataset.

###  5.5 Effects of different components in DecideNet

To analyze effects of each components of the proposed _DecideNet_ , we conduct
ablation studies on the Mall and SHB dataset. The qualitative results are
listed in Table 4, which shows several interesting observations. First, using
the estimations exclusively from either the _RegNet_ (“ _RegNet_ only”), or
_DetNet_ (“ _DetNet_ only”) only obtains fair results on both datasets. The
estimations from the _RegNet_ have lower error than the detection
counterparts. This is possibly due to the fact that most of the image regions
are with high crowd density on both datasets. Further, late fusion by
averaging two classes of density maps (“ _RegNet_ +_DetNet_ (Late Fusion)”)
exhibits improvements than “ _RegNet_ only” and “ _DetNet_ only” on that SHB
dataset. While on the Mall dataset, it only achieves a mediocre result between
two kinds of density estimations. This indicates that direct late fusion is
not robust enough to obtain better results across all kinds of datasets.
Second, with _DecideNet_ , even training without the object detection scores
regularization (“ _RegNet_ +_DetNet_ +_QualityNet_ ”), we obtain significant
MAE and MSE decrease as compared with those obtained by the previous methods.
Compared to late fusion, it almost decreases the MAE by half on two datasets,
revealing the power of the attention mechanism. Last but not least, adopting
the “quality-aware” loss during training (“ _RegNet_ +_DetNet_ +_QualityNet_
(quality-aware loss)”), the MAE and MSE errors are further reduced on two
datasets. In particular, the MSE decreases from 41.86 to 31.98 on SHB dataset:
this shows that the loss can substantially increase the prediction stability
on challenging datasets with great variations.

Figure 6: Prediction and the ground-truth crowd counts on the test sets of the
Mall (left) and SHB (right) datasets.

In Figure 6, we show the relationships between different crowd count
predictions and the ground-truth crowd counts on the test sets of two
datasets. Note that the horizontal axes “image id” are sorted in ascending
order by the number of ground-truth crowd counts. Clearly, when the numbers of
ground-truth crowd count are small, the regression based results from the
_RegNet_ overestimate the estimations: the blue lines are above the ground-
truth red lines in the first half part of the horizontal axis in both figures.
On the opposite, the detection based result curves (the green lines) fit the
red lines well at that region on two datasets. However, when the numbers of
ground-truth count increase, the estimations of the detection based density
map become considerably lower than the red lines, particularly after the
second half parts of the horizontal axis. The blue lines fit the ground-truth
lines best in the middle part of the horizontal axes. This verifies our
observation that regression based estimations are more suitable for high
crowded patches. Directly applying the late fusion (the purple curves) helps
to a certain extent, while its predicted counts are not stable along all
images. At last, the cyan lines, which represent _DecideNet_ outputs, indicate
the smallest differences to the ground-truth curves along all parts of the
horizontal axes. That is, the _DecideNet_ trained with “quality-aware” loss
exhibits the best estimation results for all kinds of crowd densities on two
datasets.

###  5.6 Visualization on density maps

To better understand what is learned in our proposed model, we visualize three
categories of crowd density maps in the SHB dataset from three blocks:
_RegNet_ , _DetNet_ and _QuialityNet_ in Figure 7 (best viewed in color).

Figure 7: The visualization results of three types of density maps on the SHB
dataset (best viewed in color).

We can discover that the outputs of regression based density maps
$D_{i}^{reg}$ (on the most left column) exhibit diffused density estimations
along the image regions. For the remote areas with highly congested crowds,
such predictions from the _RegNet_ are reliable. However, when it comes to the
nearby regions with lower crowd density, the results are not satisfactory:
some single person bodies are erroneously predicted with very high density.
The prediction counts of the $D_{i}^{reg}$ are also larger than the ground-
truth (GT) counts, implying the occurrence of overestimation issue. Compared
to $D_{i}^{reg}$, the detection based density maps $D_{i}^{det}$ (the middle
column) are very different: the predicted peak regions are concentrated on the
center of heads. This is resulted from the fact that these maps are generated
from outputs of head detectors. We can further observe that the detection
based density results are pretty good in nearby low density regions of the
given image, while not all the heads are marked with high prediction peaks in
the remote areas. The underestimated predicted counts of $D_{i}^{det}$ also
reflect this phenomenon. With the attention information from the _QualityNet_
, final density maps in the right column reveal very good characteristics: in
the nearby region, the estimation prefers the detection results. Persons in
those areas share very similar estimation patterns with $D_{i}^{det}$.
Oppositely, in remote and congested regions, instead of the “concentrated dot”
patterns, the density maps are diffused. _DecideNet_ considers the regression
based results $D_{i}^{reg}$ are more reliable for those cases. This confirms
that the _QualityNet_ block is able to assess the reliability of the
corresponding density map value for a specific pixel.

##  6 Conclusion

In this paper, a novel end-to-end crowd counting architecture named
_DecideNet_ has been proposed. It is motivated by the complementary
performance of detection and regression based counting methods under
situations with varying crowd densities. To the best of our knowledge,
_DecideNet_ is the first framework to estimate crowd counts via adaptively
adopting detection and regression based count estimations under the guidance
from the attention mechanism. We evaluate the framework on three challenging
crowd counting benchmarks collected from real-world scenes with high variation
in crowd densities. Experimental results confirm that our method obtains the
state-of-the-art performance on three public datasets.

##  7 Acknowledgment

Jiang Liu and Alexander Hauptmann are supported by the Intelligence Advanced
Research Projects Activity (IARPA) via Department of Interior/Interior
Business Center (DOI/IBC) contract number D17PC00340. The U.S. Government is
authorized to reproduce and distribute reprints for Governmental purposes
notwithstanding any copyright annotation/herein. The views and conclusions
contained herein are those of the authors and should not be interpreted as
necessarily representing the official policies or endorsements, either
expressed or implied, of IARPA, DOI/IBC, or the U.S. Government. Chenqiang Gao
and Deyu Meng are supported by the China NSFC projects with No.61571071,
No.61661166011, No.61721002.

## References

  * [1] R. Benenson, M. Omran, J. H. Hosang, and B. Schiele.  Ten years of pedestrian detection, what have we learned?  CoRR, abs/1411.4304, 2014.
  * [2] L. Boominathan, S. S. Kruthiventi, and R. V. Babu.  Crowdnet: a deep convolutional network for dense crowd counting.  In ACM MM, 2016.
  * [3] A. B. Chan, Z.-S. J. Liang, and N. Vasconcelos.  Privacy preserving crowd monitoring: Counting people without people models or tracking.  In CVPR, 2008.
  * [4] A. B. Chan and N. Vasconcelos.  Bayesian poisson regression for crowd counting.  In ICCV, 2009.
  * [5] J. Chen, J. Liang, H. Lu, S.-I. Yu, and A. Hauptmann.  Videos from the 2013 boston marathon: An event reconstruction dataset for synchronization and localization.  2016\.
  * [6] K. Chen, C. C. Loy, S. Gong, and T. Xiang.  Feature mining for localised crowd counting.  In BMVC, 2012.
  * [7] J. Dai, Y. Li, K. He, and J. Sun.  R-fcn: Object detection via region-based fully convolutional networks.  In NIPS, 2016.
  * [8] N. Dalal and B. Triggs.  Histograms of oriented gradients for human detection.  In CVPR, 2005.
  * [9] P. Dollar, C. Wojek, B. Schiele, and P. Perona.  Pedestrian detection: An evaluation of the state of the art.  TPAMI, 2012.
  * [10] P. F. Felzenszwalb, R. B. Girshick, D. McAllester, and D. Ramanan.  Object detection with discriminatively trained part-based models.  TPAMI, 2010.
  * [11] J. Gall, A. Yao, N. Razavi, L. Van Gool, and V. Lempitsky.  Hough forests for object detection, tracking, and action recognition.  TPAMI, 2011.
  * [12] C. Gao, P. Li, Y. Zhang, J. Liu, and L. Wang.  People counting based on head detection combining adaboost and cnn in crowded surveillance environment.  Neurocomputing, 2016.
  * [13] W. Ge and R. T. Collins.  Marked point processes for crowd counting.  In CVPR, 2009.
  * [14] R. Girshick.  Fast r-cnn.  In ICCV, 2015.
  * [15] H. Idrees, I. Saleemi, C. Seibert, and M. Shah.  Multi-source multi-scale counting in extremely dense crowd images.  In CVPR, 2013.
  * [16] D. Kang, Z. Ma, and A. B. Chan.  Beyond counting: Comparisons of density maps for crowd analysis tasks-counting, detection, and tracking.  arXiv preprint arXiv:1705.10118, 2017.
  * [17] S. Kumagai, K. Hotta, and T. Kurita.  Mixture of counting cnns: Adaptive integration of cnns specialized to specific appearance for crowd counting.  arXiv preprint arXiv:1703.09393, 2017.
  * [18] B. Leibe, E. Seemann, and B. Schiele.  Pedestrian detection in crowded scenes.  In CVPR, volume 1, pages 878–885. IEEE, 2005.
  * [19] V. Lempitsky and A. Zisserman.  Learning to count objects in images.  In NIPS, 2010.
  * [20] S.-F. Lin, J.-Y. Chen, and H.-X. Chao.  Estimation of number of people in crowded scenes using perspective transformation.  IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2001.
  * [21] M. Marsden, K. McGuiness, S. Little, and N. E. O’Connor.  Fully convolutional crowd counting on highly congested scenes.  arXiv preprint arXiv:1612.00220, 2016.
  * [22] D. Onoro-Rubio and R. J. López-Sastre.  Towards perspective-free object counting with deep learning.  In ECCV, 2016.
  * [23] V.-Q. Pham, T. Kozakaya, O. Yamaguchi, and R. Okada.  Count forest: Co-voting uncertain number of targets using random forest for crowd density estimation.  In ICCV, 2015.
  * [24] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi.  You only look once: Unified, real-time object detection.  In CVPR, 2016.
  * [25] S. Ren, K. He, R. Girshick, and J. Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In NIPS, 2015.
  * [26] M. Rodriguez, I. Laptev, J. Sivic, and J.-Y. Audibert.  Density-aware person detection and tracking in crowds.  In ICCV, 2011.
  * [27] P. Sabzmeydani and G. Mori.  Detecting pedestrians by learning shapelet features.  In CVPR, 2007.
  * [28] D. B. Sam, S. Surya, and R. V. Babu.  Switching convolutional neural network for crowd counting.  In CVPR, 2017.
  * [29] C. Shang, H. Ai, and B. Bai.  End-to-end crowd counting via joint learning local and global count.  In ICIP, 2016.
  * [30] B. Sheng, C. Shen, G. Lin, J. Li, W. Yang, and C. Sun.  Crowd counting via weighted vlad on dense attribute feature maps.  TCVST, 2016.
  * [31] V. A. Sindagi and V. M. Patel.  Generating high-quality crowd density maps using contextual pyramid cnns.  In ICCV, 2017.
  * [32] V. A. Sindagi and V. M. Patel.  A survey of recent advances in cnn-based single image crowd counting and density estimation.  Pattern Recognition Letters, 2017.
  * [33] J. R. Uijlings, K. E. Van De Sande, T. Gevers, and A. W. Smeulders.  Selective search for object recognition.  IJCV, 2013.
  * [34] P. Viola, M. J. Jones, and D. Snow.  Detecting pedestrians using patterns of motion and appearance.  In ICCV, 2003.
  * [35] E. Walach and L. Wolf.  Learning to count with cnn boosting.  In ECCV, 2016.
  * [36] C. Wang, H. Zhang, L. Yang, S. Liu, and X. Cao.  Deep people counting in extremely dense crowds.  In ACM MM, 2015.
  * [37] L. Wang, C. Gao, J. Liu, and D. Meng.  A novel learning-based frame pooling method for event detection.  Signal Processing, 2017.
  * [38] Y. Wang and Y. Zou.  Fast visual object counting via example-based density estimation.  In ICIP, 2016.
  * [39] B. Wu and R. Nevatia.  Detection and tracking of multiple, partially occluded humans by bayesian combination of edgelet based part detectors.  IIJCV, 2007.
  * [40] B. Xu and G. Qiu.  Crowd density estimation based on rich features and random projection forest.  In WACV, 2016.
  * [41] C. Zhang, H. Li, X. Wang, and X. Yang.  Cross-scene crowd counting via deep convolutional neural networks.  In ICCV, 2015.
  * [42] Y. Zhang, D. Zhou, S. Chen, S. Gao, and Y. Ma.  Single-image crowd counting via multi-column convolutional neural network.  In CVPR, 2016.
  * [43] T. Zhao, R. Nevatia, and B. Wu.  Segmentation and tracking of multiple humans in crowded environments.  ITPAMI, 2008.