# Tropical Decision Boundaries for Neural Networks Are Robust Against
Adversarial Attacks

Kurt Pasque, Christopher Teska, Ruriko Yoshida,
Keiji Miura, and Jefferson Huang

###### Abstract

We introduce a simple, easy to implement, and computationally efficient
tropical convolutional neural network architecture that is robust against
adversarial attacks. We exploit the tropical nature of piece-wise linear
neural networks by embedding the data in the _tropical projective torus_ in a
single hidden layer which can be added to any model. We study the geometry of
its decision boundary theoretically and show its robustness against
adversarial attacks on image datasets using computational experiments.

##  1 Introduction

Artificial Neural Networks have demonstrated exceptional capability in the
fields of computer vision, natural language processing, and genetics. However,
they have similarly demonstrated a concerning vulnerability to adversarial
attacks Huang et al. (2017); Papernot et al. (2018). As neural networks become
prevalent in critical applications such as autonomous driving, healthcare, and
cybersecurity, the development of adversarial defense methodologies will
become central to the reliability and ultimate success of those efforts (for
example, see Madry et al. (2018); Kotyan and Vargas (2022); Carlini and Wagner
(2017a); Croce et al. (2019); Croce and Hein (2020) and references within).
Significant work in adversarial defense has focused on robust optimization for
adversarial training (for example, see Qian et al. (2022)). This approach
involves a minimax game where the attacker attempts to maximize a loss
function while a defender attempts to minimize this loss. This methodology
degrades the performance of the network on clean inputs relative to the clean
model Tu et al. (2019) while increasing computational complexity.

Accumulating evidence supports the robustness of “low-rank” models against
adversarial attacks in image recognition Yang et al. (2019); Phan et al.
(2022); Wang et al. (2023). There, the low-rank models were realized by
different methods: matrix completion Yang et al. (2019), model compression
Phan et al. (2022) or tensor SVD Wang et al. (2023), suggesting that the low-
rankness seems to be the universal key for adversarial robustness. Then, it is
expected that the tropical metric based on the tropical geometry Maclagan and
Sturmfels (2015); Joswig (2022), that tends to favor a sparse structure in
machine learning Yoshida et al. (2023a); Miura and Yoshida (2023); Aliatimis
et al. (2023); Yoshida et al. (2023b), may also be effective for adversarial
robustness.

Tropical geometry has been applied to describing the geometry of deep neural
networks with piecewise linear activation functions, such as two of the most
popular and widely used activators: rectified linear units (ReLUs) and maxout
units. In Glorot et al. (2011) Glorot et al. showed that neural networks with
ReLUs work very well and outperform neural networks with traditional choices
of activation functions using empirical studies. Later, Zhang et al. showed
that the decision boundary of a deep neural network with ReLU activation
functions is a tropical rational function with the max-plus algebra Zhang et
al. (2018). Goodfellow et al. Goodfellow et al. (2013a) introduced maxout
networks, deep feed-forward neural networks with maxout units whose activation
is the maximum of arbitrarily many input neurons. In Charisopoulos and Maragos
(2018) Charisopoulos and Maragos showed that the maxout activation function
fits input data by a tropical polynomial in terms of the max-plus algebra.
Although this body of work has clearly shown that deep neural networks with
ReLU and maxout activators can be understood as operations in terms of
tropical geometry with the max-plus algebra, they only handled the neural
networks whose input domain is in the Euclidean space.

Another strain of works utilized tropical geometry more natively and enabled
to handle the deep neural networks whose input domain is in the tropical
projective torus. In 2023, Yoshida et al. in Yoshida et al. (2023b) proposed
tropical neural networks, which embeds the input vector in the tropical
projective torus with tropical activation functions. A tropical neural network
is a generalization of the tropical logistic regression model proposed by
Aliatimis et al. Aliatimis et al. (2023) and a tropical activation function
fits data with the tropical Laplace distribution centered around a tropical
Fermat-Weber point within the same class. Although these works truly employed
the tropical metric of the input space, they only used it to embed general
input vectors, which is not necessarily an image, into the first hidden layer.

In this paper, we introduce a simple, easy to implement, and efficient
convolution neural network (CNN) robust against adversarial attacks using
tropical embedding layers. One idea to construct a decision boundary with a
low-rank nature for image classification is to exploit tropical operations in
the output layers. Therefore, we propose a tropical decision boundary in the
last layer which is a native operation over the tropical projective torus in
terms of the max-plus algebra. This approach results in well defined decision
boundaries and robustness to adversarial attack with a minimal increase in
computational complexity relative to standard piecewise-linear neural
networks. Especially we show that adversarial attacks developed by Carlini &
Wagner in Carlini and Wagner (2017b) may not be able to reach the optimal
attack against our novel convolution neural networks with tropical embedded
last layer due to the discrete nature of the geometry of its decision
boundary.

This paper is organized as follows.: We begin with a primer on tropical
geometry then develop a tropical decision boundary and a tropical convolution
for deep neural networks. We provide a theoretical analysis of the geometry of
the tropical decision boundaries and how they are learned. Finally, we
demonstrate the robustness of the proposed tropical decision boundaries
against adversarial attacks in computational experiments.

We summarize our contributions as follows:

  * •

We propose a tropical decision boundary and tropical CNN.

  * •

We describe the decision boundary via tropical balls.

  * •

We demonstrate robustness against adversarial attacks via some theoretical
properties and experimental computations.

##  2 Basics in Tropical Geometry and Tropical Bisectors

Here we consider the tropical projective torus

$\mathbb{R}^{d}/\mathbb{R}{\bf 1}:=\left\\{x\in\mathbb{R}^{d}\mid
x:=(x_{1},x_{2},\ldots,x_{d})=(x_{1}+c,x_{2}+c,\ldots,x_{d}+c),\,\forall
c\in\mathbb{R}\right\\},$

where ${\bf 1}=(1,\ldots,1)\in\mathbb{R}^{d}$. Note that for any
$x=(x_{1},x_{2},\ldots,x_{d})\in\mathbb{R}^{d}/\mathbb{R}{\bf 1}$,

$x=(x_{1},x_{2},\ldots,x_{d})=(0,x_{2}-x_{1},\ldots,x_{d}-x_{1})\in\mathbb{R}^{d}/\mathbb{R}{\bf
1},$

which means that the tropical projective torus $\mathbb{R}^{d}/\mathbb{R}{\bf
1}$ is isomorphic to $\mathbb{R}^{d-1}$.

######  Definition 1 (Tropical Arithmetic Operations).

The tropical semiring $(\,\mathbb{R}\cup\\{-\infty\\},\oplus,\odot)\,$ with
the max-plus algebra is a semiring with the tropical arithmetic operations of
addition and multiplication defined as:

$a\oplus b:=\max\\{a,b\\},~{}~{}~{}~{}a\odot b:=a+b$

for any $a,b\in\mathbb{R}\cup\\{-\infty\\}$. Note that $-\infty$ is the
identity element for the tropical addition operation $\oplus$, and $0$ is the
identity element for the tropical multiplication operation $\odot$.

######  Definition 2 (Tropical Metric).

The tropical metric is defined for any
$x=(x_{1},\ldots,x_{d}),y=(y_{1},\ldots,y_{d})\in\mathbb{R}^{d}/\mathbb{R}{\bf
1}$ as

$d_{\rm
tr}(x,y)=\max_{i\in\\{1,\ldots,d\\}}\\{x_{i}-y_{i}\\}-\min_{i\in\\{1,\ldots,d\\}}\\{x_{i}-y_{i}\\}.$

######  Remark 3.

The tropical metric $d_{\rm tr}$ is a well-defined metric over the tropical
projective torus $\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ Monod et al. (2019).

######  Definition 4 (Tropical Ball).

A tropical ball $B_{x}(r)$ centered at $x\in\mathbb{R}^{d}/\mathbb{R}{\bf 1}$
with radius $r>0$ under the tropical metric $d_{\rm tr}$ is defined as

$B_{x}(r)=\left\\{y\in\mathbb{R}^{d}/\mathbb{R}{\bf 1}:d_{\rm tr}(x,y)\leq
r\right\\}.$

######  Remark 5.

Any tropical ball $B_{x}(r)\subset\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ can be
viewed as a classical polytope in $\mathbb{R}^{d-1}$; see Theorem 12.

######  Definition 6 (Tropical Bisector).

Suppose $S\subset\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ is a finite set. Then the
tropical bisector of $\mathcal{S}$ is defined as

$bis(S):=\left\\{x\in\mathbb{R}^{d}/\mathbb{R}{\bf 1}\mid d_{\rm
tr}(x,a)=d_{\rm tr}(x,b),\,\mbox{ for }a,b\in{S}\right\\}.$

For a finite set $S\subset\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ and any
$a_{1},\ldots,a_{k}\in S$, define

$bis(F_{i_{1}},\ldots,F_{i_{l}})(\\{a_{1},\ldots,a_{k}\\})=bis(\\{a_{1},\ldots,a_{k}\\})\cap(a_{1}+F_{1_{1}})\cap\ldots\cap(a_{k}+F_{k_{l}})$

where each $F_{i_{j}}$ is a full dimensional cone in the face fan of the
tropical ball with respect to the max-plus algebra, which is also a classical
polytope, and $a_{i}+F_{i_{j}}$ is a polyhedron which is a full dimensional
cone $F_{i_{j}}$ is translated so that its unique vertex is $a_{i}$ for
$i=1,\ldots k$.

######  Definition 7 (Definition 1 in Criado et al. (2022)).

Suppose $S\subset\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ is a finite set. Then the
set $S$ is in weak general position with respect to a tropical ball $B_{x}(r)$
if no pair of points lies in a hyperplane parallel to a facet of $B_{x}(r)$.

For every subset $a_{1},\ldots,a_{k}\in S$ and for each neighborhood $U_{i}$
around $a_{i}$, if

$bis(F_{i_{1}},\ldots,F_{i_{l}})(\\{a_{1},\ldots,a_{k}\\})=\emptyset\Longleftrightarrow
bis(F_{i_{1}+,\ldots,F_{i_{l}}})(\\{a^{\prime}_{1},\ldots,a^{\prime}_{k}\\})=\emptyset$

for $a^{\prime}_{1},\ldots,a^{\prime}_{k}$ with $a^{\prime}_{i}\in U_{i}$,
then we say the set $S$ is in general position with respect to a tropical ball
$B_{x}(r)$.

######  Example 8.

Let $d=3$. Consider points
$x=(0,0,0),\,y=(0,w,0)\in\mathbb{R}^{3}/\mathbb{R}{\bf 1}$ in Figure 4. Then
when $w=1$ and $w=0$, $x$ and $y$ are not in weak general position, which
means that they are not in general position. When $w=-1$, $x$ and $y$ are in
weak general position, but not in general position.

##  3 Tropical Convolutional Neural Networks

###  3.1 Tropical Embedding Layer

######  Definition 9 (Tropical Embedding Layer).

A tropical embedding layer takes a vector
$x\in\mathbb{R}^{d}/\mathbb{R}\mathbf{1}$ as input, and the activation of the
$j$-th neuron in the embedding layer is

$z_{j}=\max_{i}(x_{i}+w^{(1)}_{ji})-\min_{i}(x_{i}+w^{(1)}_{ji})=d_{\rm
tr}(-{\bf w}^{(1)}_{j},x).$ (1)

######  Remark 10.

Tropical embedding layers were originally developed in order to embed
phylogenetic trees into a Euclidean space Yoshida et al. (2023b). But, as this
paper shows, we found them to be effective for increasing the robustness of
CNNs for image data.

###  3.2 Structure of a Tropical Convolutional Neural Network

Suppose $f^{L-1}:\mathbb{R}^{n_{1}\times n_{2}\times
n_{3}}\to\mathbb{R}^{d}/\mathbb{R}^{1}$ is the map of a classification
convolutional neural network. Then $f^{L-1}(x)$, with input data
$x\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}$ of $k$ classes, is the output
of the network. We then embed the output of $f^{L-1}(x)$ into the tropical
projective torus with (1).

$f_{j}^{L}(x)=\max_{i}\\{f_{i}^{L-1}(x)+w_{ji}^{L}\\}-\min_{i}\\{f_{ji}^{L-1}(x)+w_{ji}^{L}\\}\\\
=d_{tr}(-w_{j}^{L},x)\ j\in{1,\dots,k}$

We show in the following section that the weights, $W^{L}$, train towards
Fermat-Weber points associated with the $k$ classes. See Barnhill et al.
(2024) for details on Fermat-Weber points and using gradient descent to find
them.

Each dimension of the output $f^{L}(x)\in\mathbb{R}^{k}$ is the tropical
distance between the input and Fermat-Weber points of each class. We then
classify the input with a softmin function:

$\max_{j\in{1,\ldots,k}}\frac{{e^{-d_{tr}(-w_{j},x)}}}{\sum_{i=1}^{k}e^{-d_{tr}(-w_{i},x)}}.$

######  Remark 11.

Using Theorem B in Zhou (2020) combined with Theorem 12 in Yoshida et al.
(2023b), a tropical CNN is an universal approximator of any function
$f:\mathbb{R}^{d}\to\mathbb{R}$.

##  4 Definition and Analysis of Tropical Decision Boundaries

###  4.1 Decision Boundary of a ReLU Neural Network

Zhang et al. in Zhang et al. (2018) explicitly described the decision boundary
of feedforward neural networks with ReLU activations using tools from tropical
geometry. We briefly summarize their work here. First, consider the output
$\nu(x)$ of the first layer of a neural network with the ReLU activations,

$\nu(x)=\max\\{Ax+b,t\\}$

where $A\in\mathbb{Z}^{p\times d}$, $b\in\mathbb{R}^{p}$, and
$t\in(\mathbb{R}\cup\\{-\infty\\})^{p}$. Let

$A=A_{+}-A_{-}$

where $A_{+},A_{-}\in\mathbb{Z}^{p\times d}_{\geq 0}$ respectively denote the
positive and negative parts of $A$. Zhang et al. Zhang et al. (2018) noticed
that $\nu(x)$ can be written as

$\nu(x)=\max\\{Ax+b,t\\}=\max\\{A_{+}x+b,A_{-}x+t\\}-A_{-}x,$

which is a tropical rational function, i.e., a difference of tropical
polynomials. It follows by induction that a neural network with $L-1$ ReLU
layers can be written as a tropical rational function. Using this fact, they
showed its decision boundary is contained in the tropical hypersurface (the
solution set) of a tropical polynomial and computed a tight upper bound on the
number of line segments in the associated piecewise-linear decision boundary.
Specifically, Zhang et al. used zonotopes, which are polytopes computed from
the Minkowski sum of a set of vectors, to describe the tropical hypersurface
of a tropical polynomial.

###  4.2 Decision Boundary of a Tropical Neural Network

Suppose that we have a sample
$\mathcal{S}=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}$ where
$y_{i}\in\\{1,\ldots,C\\}$ and
$x_{i}\in\mathbb{R}^{d}/\mathbb{R}^{\mathbf{1}}$ for $i=1,\ldots,n$. Here we
consider a tropical neural network with a tropical embedding layer of
$k_{1}+k_{2}+\ldots+k_{C}$ neurons, where
$k_{1},k_{2},\ldots,k_{C}\in\mathbb{N}:=\\{1,2,\ldots\\}$. We denote its true
optimal weight matrix by $W^{*}\in\mathbb{R}^{(k_{1}+\dots+k_{c})\times d}$
where the weights $w^{*}_{j,1},\ldots,w^{*}_{j,k_{j}}\in\mathbb{R}^{1\times
d}$ are rows mapping inputs to neurons $z_{j,1},\ldots,z_{j,k_{j}}$ associated
with class $Y=j$. Then note that the tropical neural network classifies the
observation $x_{i}$ as

$Y_{i}=j\mbox{ if }\operatorname*{arg\,min}_{w^{*}\in W^{*}}d_{\rm
tr}(x_{i},-w^{*})\in\\{w^{*}_{j,1},\ldots,w^{*}_{j,k_{j}}\\},$

Therefore the decision boundary of this tropical neural network is

$\mathcal{B}:=\left\\{x\in\mathbb{R}^{d}/\mathbb{R}{\bf 1}\middle|d_{\rm
tr}(x,-w^{*}_{j,l_{j}})=d_{\rm
tr}(x,-w^{*}_{j^{\prime},l_{j^{\prime}}}),j\not=j^{\prime},l_{j}\in[k_{j}],l_{j^{\prime}}\in[k_{j^{\prime}}]\right\\}$

where
$[k_{j}]:=\\{1,\ldots,k_{j}\\},\,[k_{j^{\prime}}]:=\\{1,\ldots,k_{j^{\prime}}\\}$.
Let $x_{0}\in\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ be on the decision boundary.
Then there exist $q\in[k_{i}]$ and $q^{\prime}\in[k_{j}]$ for
$i,j\in\\{1,\ldots,C\\}$ such that

$r:=d_{\rm tr}(x_{0},-w^{*}_{i,q})=d_{\rm tr}(x_{0},-w^{*}_{j,q^{\prime}}).$

Then note that

$x_{0}\in\left(\partial B_{-w^{*}_{i,q}}(r)\right)\cap\left(\partial
B_{-w^{*}_{j,q^{\prime}}}(r)\right),$

where $\partial B_{x}(r)$ is the boundary of the tropical ball $B_{x}(r)$.

######  Theorem 12 (Section 3.1.1 in Barnhill et al. (2023)).

A tropical ball $B_{x}(r)$ is a polytrope, which is a tropical simplex (and
hence a tropical polytope) that is also a classical polytope.

Since tropical balls $B_{-w^{*}_{i,q}}(r)$ and $B_{-w^{*}_{j,q^{\prime}}}(r)$
are classical polytopes and Proposition 2.14 in (Brandenburg et al., 2023)
shows explicit hyperplane representations (sets of defining inequalities for
each tropical ball) of them. Some of the segments of the decision boundary are
defined by one or more linear equations which define at least two of the
tropical balls $B_{-w^{*}_{i,1}}(r),\ldots,B_{-w^{*}_{i,k_{i}}}(r)$ and
$B_{-w^{*}_{j,1}}(r),\ldots,B_{-w^{*}_{j,k_{j}}}(r)$. Therefore we have the
following theorem:

######  Theorem 13.

The decision boundary, $\mathcal{B}$, is defined by a subset of the equations
defining tropical balls $B_{-w^{*}_{i,1}}(r),\ldots,B_{-w^{*}_{i,k_{i}}}(r)$
and $B_{-w^{*}_{j,1}}(r),\ldots,B_{-w^{*}_{j,k_{j}}}(r)$ for
$i,j\in\\{1,\ldots,C\\}$.

######  Example 14.

We consider $\mathbb{R}^{3}/\mathbb{R}{\bf 1}$ and $C=2$. Suppose we have
$w^{*}_{1,1}=(5,-5,0),\,w^{*}_{2,1}=(-5,5,0)$. Then the contour plot and heat
map plot are shown in Figure 1. In this case, from Example 3.7 in Barnhill et
al. (2023), we can find the sets of inequalities to define
$B_{-w^{*}_{1,1}}(r)$ and $B_{-w^{*}_{2,1}}(r)$ as follows:

$B_{-w^{*}_{1,1}}(r)=\left\\{x\in\mathbb{R}^{3}/\mathbb{R}{\bf
1}\middle|\begin{array}[]{ccc}x_{3}&=&0,\\\ x_{1}&\geq&5-r,\\\
x_{1}&\leq&-5+r,\\\ x_{2}&\geq&5-r,\\\ x_{2}&\leq&-5+r,\\\
x_{1}-x_{2}&\leq&10+r,\\\ x_{1}-x_{2}&\geq&10-r\end{array}\right\\},$

and

$B_{-w^{*}_{2,1}}(r)=\left\\{x\in\mathbb{R}^{3}/\mathbb{R}{\bf
1}\middle|\begin{array}[]{ccc}x_{3}&=&0,\\\ x_{1}&\geq&-5-r,\\\
x_{1}&\leq&5+r,\\\ x_{2}&\geq&-5-r,\\\ x_{2}&\leq&5+r,\\\
x_{1}-x_{2}&\leq&-10+r,\\\ x_{1}-x_{2}&\geq&-10-r\end{array}\right\\}.$

In this case, the decision boundary consists of the points where for
$r=\frac{d_{\rm tr}(-w^{*}_{1,1},-w^{*}_{2,1})}{2}=\frac{d_{\rm
tr}((5,-5,0),(-5,5,0))}{2}=10$ the equation $x_{1}-x_{2}=10-r$, which defines
the boundary of $B_{-w^{*}_{1,1}}(r)$, and the equation $x_{1}-x_{2}=-10+r$,
which defines the boundary of $B_{-w^{*}_{2,1}}(r)$, meet. Thus, the decision
boundary $\mathcal{B}$ is defined as

$\mathcal{B}=\left\\{x\in\mathbb{R}^{3}/\mathbb{R}{\bf
1}\middle|x_{1}=x_{2},\,x_{3}=0\right\\}.$

Figure 1: Here we have $w^{*}_{1,1}=(5,-5,0),\,w^{*}_{2,1}=(-5,5,0)$. (LEFT)
Heat-map plot for distance from optimal weights in Example 14. The white line
is the decision boundary. (RIGHT) Contour plot of Example 14. As you can see
tropical balls $B_{-w^{*}_{1,1}}(r)=B_{(5,-5)}(r)$ and
$B_{-w^{*}_{2,1}}(r)=B_{(-5,5)}(r)$ for $r>0$.

######  Example 15.

We consider $\mathbb{R}^{3}/\mathbb{R}{\bf 1}$ and $C=2$. Suppose we have
$k_{1}=k_{2}=2$ and
$w^{*}_{1,1}=(-2,-7,0),\,w^{*}_{1,2}=(-8,-3,0),\,w^{*}_{2,1}=(6,1,0),\,w^{*}_{2,2}=(0,5,0)$.
Then the contour plot and heat map plot are shown in Figure 2. Similarly to
Example 14, we can compute the system of linear inequalities for each tropical
ball. Then the decision boundary for this example is a piece-wise linear line
defined by

$\mathcal{B}=\left\\{x\in\mathbb{R}^{3}/\mathbb{R}{\bf
1}\middle|\begin{array}[]{rl}x_{1}+x_{2}=1&\mbox{ if
}x_{1}\leq\frac{1}{2},\,x_{2}\geq\frac{1}{2},\\\ x_{2}=\frac{1}{2}&\mbox{ if
}\frac{1}{2}\leq x_{1}\leq\frac{5}{2},\\\ x_{1}+x_{2}=3&\mbox{ if
}x_{1}\geq\frac{5}{2},\,x_{2}\leq\frac{1}{2}\\\ \end{array}\right\\}.$

Figure 2: Here we have
$w^{*}_{1,1}=(-2,-7,0),\,w^{*}_{1,2}=(-8,-3,0),\,w^{*}_{2,1}=(6,1,0),\,w^{*}_{2,2}=(0,5,0)$.
(LEFT) Heat-map plot for distance from optimal weights in Example 14. The
white line is the decision boundary. (RIGHT) Contour plot of Example 15. As
you can see tropical balls
$B_{-w^{*}_{1,1}}(r)=B_{(2,7)}(r),B_{-w^{*}_{1,2}}(r)=B_{(8,3)}(r)$ and
$B_{-w^{*}_{2,1}}(r)=B_{(-6,-1)}(r),B_{-w^{*}_{2,2}}(r)=B_{(0,-5)}(r)$ for
$r>0$.

Suppose we have one neuron, i.e., $k_{1}=k_{2}=\ldots=k_{C}=1$, for each class
$c=1,\ldots,C$ for the response variable such as Example 14. Then we have the
following lemma.

######  Lemma 16.

Let $w^{*}_{c,1}$ be the optimal weight or a kernel for the neuron $z_{c}$ in
the tropical embedding layer for $c=1,\ldots,C$, and let
$S:=\\{w^{*}_{1,1},\ldots,w^{*}_{C,1}\\}$. Then the decision boundary of the
tropical neural network is the tropical bisector $bis(S)$ defined in
Definition 6.

###### Proof.

This is trivial from Definition 6. ∎

######  Theorem 17 (Proposition 4 in Criado et al. (2022)).

Suppose we have $C\geq 2$, and $k_{1}=\ldots=k_{C}=1$. If the optimal weights
$w^{*}_{t,1}:=(w^{*1}_{t,1},\ldots,w^{*d}_{t,1}),\,w^{*}_{t^{\prime},1}:=(w^{*1}_{t^{\prime},1},\ldots,w^{*d}_{t^{\prime},1})\in\mathbb{R}^{d}/\mathbb{R}{\bf
1}$ for $t,t^{\prime}\in\\{1,\ldots,C\\}$ and for each neuron (or kernel) in
the tropical embedding layer are in weak general position, then the decision
boundary of a tropical neural network is defined by the homogeneous max-
tropical Laurent polynomial such that

$\max\left(\max_{i,j\in\\{1,\ldots,d\\}}(x_{i}-w^{*i}_{t,1}-x_{j}+w^{*j}_{t,1}),\max_{k,l\in\\{1,\ldots,d\\}}(x_{k}-w^{*k}_{t^{\prime},1}-x_{l}+w^{*l}_{t^{\prime},1})\right).$
(2)

In addition, the decision boundary is contained in a max-tropical hypersurface
of degree $d$.

Note that if $k_{1}=k_{2}=1$ and if $w^{*}_{1,1}$ and $w^{*}_{2,1}$ are in
weak general position, then we can apply Theorem 17 to compute the decision
boundary of a tropical neural network. First, we enumerate the maximal cells
of the tropical hypersurface defined by the equation in (2) where one of

$x_{i}-w^{*i}_{1,1}-x_{j}+w^{*j}_{1,1}\mbox{ for }i,j\in\\{1,\ldots,d\\}$

and one of

$x_{k}-w^{*k}_{2,1}-x_{j}+w^{*l}_{2,1}\mbox{ for }k,l\in\\{1,\ldots,d\\}$

attain maxima. The time complexity of this algorithm is $\Omega(d^{4})$ which
is tight by Corollary 8 in Criado et al. (2022).

######  Theorem 18.

Suppose we have $C=2$ and $k_{1},k_{2}\geq 1$. Then the decision boundary of
the tropical neural network defined by $w^{*}_{1,1},\ldots w^{*}_{1,k_{1}}$
and $w^{*}_{2,1},\ldots w^{*}_{2,k_{2}}$ does not contain full-dimensional
cells if and only if any pair of $w^{*}_{1,i}$ and $w^{*}_{2,j}$ for
$i\in\\{1,\ldots,k_{1}\\}$ and $j\in\\{1,\ldots,k_{2}\\}$ is in weak general
position.

###### Proof.

This is trivial from Proposition 2 in Criado et al. (2022). ∎

Similarly we have the following theorem for $C\geq 2$ and
$k_{1}=\ldots=k_{C}=1$.

######  Theorem 19.

Suppose we have $C\geq 2$ and $k_{1}=\ldots=k_{C}=1$. Then the decision
boundary of the tropical neural network defined by $w^{*}_{1,1},\ldots
w^{*}_{C,1}$ does not contain full-dimensional cells if and only if any pair
of $w^{*}_{i,1}$ and $w^{*}_{j,1}$ for $i,j\in\\{1,\ldots,C\\}$ is in weak
general position.

###### Proof.

This is trivial from Proposition 2 in Criado et al. (2022). ∎

######  Example 20.

Consider $w^{*}_{1,1}=(5,-5,0)$ and $w^{*}_{2,1}=(-5,5,0)$ from Example 15.
Here $w^{*}_{1,1}$ and $w^{*}_{2,1}$ are in weak general position. Thus, by
Theorem 18, the decision boundary has dimension less than $d-1=2$. In this
case it has dimension $1$.

######  Example 21.

Suppose we have $C=2$ and $k_{1}=k_{2}=1$. Consider $w^{*}_{1,1}=(5,5,0)$ and
$w^{*}_{2,1}=(-7,-7,0)$ which are not in weak general position since they are
on the hyperplane $x_{1}=x_{2}$. Figure 3 shows contour plots of two tropical
Laplacian distributions. In this case $w^{*}_{1,1}$ and $w^{*}_{2,1}$ are not
in weak general position and the decision boundary has full dimensional, i.e.,
dimension $2$, region(s) by Theorem 18. In this case we have the region

$\mathcal{B}=\left\\{x\in\mathbb{R}^{3}/\mathbb{R}{\bf
1}\middle|\begin{array}[]{rcl}x_{1}&\leq&-7\\\ x_{2}&\geq&5\\\
x_{1}+x_{2}&=&-2\\\ x_{1}&\geq&5\\\ x_{2}&\leq&-7\\\ \end{array}\right\\}.$

Figure 3: Here we have $w^{*}_{1,1}=(5,5,0),\,w^{*}_{2,1}=(-7,-7,0)$. (LEFT)
Heat-map plot for distance from optimal weights in Example 21. (RIGHT) Contour
plot of Example 21.

It is possible to classify all the possible configurations of two points in
the planar case or in $\mathbb{R}^{3}/\mathbb{R}{\bf 1}$. By scaling and
parallel translation, you can set the coordinates of the two points to
$w^{*}_{1,1}=(0,0,0)$ and $w^{*}_{2,1}=(1,w,0)$ without loss of generality.
The configurations are classified exhaustively as in the following lemma with
Figure 4.

Figure 4: The bisectors between $w^{*}_{1,1}=(0,0,0)$ and
$w^{*}_{2,1}=(1,w,0)$ for various $w$ are represented by red. The lightgray
lines represent the hyperplanes for $w^{*}_{1,1}$ and $w^{*}_{2,1}$. Note that
$w=1$ and $w=0$ are not in weakly general positions (i. e.
$w^{*}_{2,1}-w^{*}_{1,1}$ is parallel to a facet of a tropical unit ball) and,
therefore, not in general positions (i. e. small perturbations change which
sectors the bisector is in). $w=-1$ is in weakly general positions but not in
general positions.

######  Lemma 22.

Suppose we have a binary response variable, i.e., $C=2$, and $k_{1}=k_{2}=1$.
Let $w^{*}_{1,1}=(0,0,0)$ and $w^{*}_{2,1}=(1,w,0)$ in
$\mathbb{R}^{3}/\mathbb{R}{\bf 1}$. Then, for $1<w$, the bisector representing
the decision boundary for the two points is $x_{2}=w/2$. For $0<w<1$, it is
$x_{1}=1/2$. For $-1<w<0$, it is

$x_{2}=\left\\{\begin{array}[]{ll}x_{1}-1&(x_{1}<0)\\\
2x_{1}-1&(0<x_{1}<1/2+w/2)\\\ x_{1}-1/2+w/2&(1/2+w/2<x_{1}<1/2-w/2)\\\
2x_{1}-1+w&(1/2-w/2<x_{1}<1)\\\ x_{1}+w&(1<x_{1})\end{array}\right.$

For $w=-1$, it is $x_{2}=x_{1}-1$. (Note that it is low dimensional and this
straight line can also be obtained by setting $w=-1$ in the above and below
equations for $-1<w<0$ and $w<-1$. This contrasts with the full-dimensional
bisectors for $w=1$ and $w=0$ as in Figure 4.) For $w<-1$, it is

$x_{2}=\left\\{\begin{array}[]{ll}x_{1}-1&(x_{1}<-1-w)\\\
1/2x_{1}+w/2-1/2&(-1-w<x_{1}<0)\\\ x_{1}+w/2-1/2&(0<x_{1}<1)\\\
1/2x_{1}+w/2&(1<x_{1}<-w)\\\ x_{1}+w&(-w<x_{1})\end{array}\right.$

###### Proof.

Direct calculations. ∎

In the above example, $w=1$ and $w=0$ are not in weakly general positions (i.
e. $w^{*}_{2,1}-w^{*}_{1,1}$ is parallel to a facet of a unit ball) and,
therefore, not in general positions (i. e. small perturbations change which
sectors the bisector is in). $w=-1$ is in weakly general position but not in
general position. As shown before, not being in a weakly general position
results in full-dimensional bisectors. In fact, perturbing $w$ from $1$ or $0$
drastically changes the positions of bisectors or which sectors the bisector
exists.

Intuitively, this drastic change is required to connect the horizontal
bisector for $w>1$ and the vertical bisector for $0<w<1$ via the full-
dimensional bisector for $w=1$. Similarly, the vertical bisector for $0<w<1$
and the diagonal bisector for $-1<w<0$ are connected via the ful-dimensional
bisector for $w=0$. Thus, the structural stability follows from being or not
being in general positions. Not being in a general position, by definition,
leads to the sensitivity of the bisector positions to small perturbations.

Interestingly, $w=-1$ is in a weakly general position but not in a general
position. Perturbing $w$ from $-1$ somehow changes the positions of bisectors
or which sectors the bisector is in, but the vulnerability is rather mild. The
positions of the bisector do switch but the overall shape of the bisector is
more or less similar. In fact, it consists of five line segments when $w$ is
close to $-1$ while it is just a single straight line when $w=-1$.

In the example shown in Figure 4 and Lemma 22, it may be illuminating to
illustrate with some simplification how the sector boundary is modified during
transfer learning from the viewpoint of Fisher information.

######  Lemma 23.

Suppose that the three-dimensional feature $x$ is embedded into the last layer
as $(d_{\rm tr}(x,w_{1}),d_{\rm tr}(x,w_{2}))$, where we only learn a single
parameter $w$ in the weights $w_{1}=(0,0,0)$ and $w_{2}=(1,w,0)$, whose true
value is $w^{*}=2$. Furthermore, suppose that the output of the neural
network, that represents the probability for $y=1$ as a softmax, is given by
$\hat{y}=\frac{1}{1+e^{d_{\rm tr}(x,w_{2})-d_{\rm tr}(x,w_{1})}}$ and there
are only two possibilities for explaining variables: $x=(0,-1,0)$ for $y\simeq
0$ and $x=(1,3,0)$ for $y\simeq 1$. Then the Fisher information for the log-
likelihood function (= negative loss), $l=y\log\hat{y}+(1-y)\log(1-\hat{y})$,
is $I=0.1$. That is,
$\textrm{Var}[\hat{w}_{MLE}]\simeq\frac{1}{nI}=\frac{10}{n}$ where $n$ is the
number of observations.

###### Proof.

By direct calculation under $w^{*}=2$, we have $\Delta:=d_{\rm
tr}(x,w_{2})-d_{\rm tr}(x,w_{1})=w\simeq 2$ for $x=(0,-1,0)$ and
$\Delta=-w\simeq-2$ for $x=(1,3,0)$. Thus, $\frac{\partial\Delta}{\partial
w}=\pm 1$. Then, $I:=\textrm{E}[(\frac{\partial
l}{\partial\hat{y}}\frac{\partial\hat{y}}{\partial\Delta}\frac{\partial\Delta}{\partial
w})^{2}]=\textrm{E}[\\{\frac{y}{\hat{y}}-\frac{1-y}{1-\hat{y}}\\}^{2}\\{\hat{y}(1-\hat{y})\\}^{2}]=\textrm{E}[(y-\hat{y})^{2}]=p(y=1)(1-\hat{y})^{2}+p(y=0)(-\hat{y})^{2}=\hat{y}(1-\hat{y})^{2}+(1-\hat{y})(-\hat{y})^{2}=\hat{y}(1-\hat{y})=0.1$.
The final numerical value is common for $x=(0,-1,0)$ and $x=(1,3,0)$ due to
their symmetry in position. ∎

######  Remark 24.

In this example, we considered a two-point distribution for $x$. However, the
value of Fisher information does not necessarily strongly depend on the
distribution of $x$. For example, we can consider a single-point distribution
(= delta function) in which $x$ is always $(0.5,1,0)$. As $\hat{y}=0.5$ there,
we have $I=0.25$, which is obviously the maximum of $I=\hat{y}(1-\hat{y})$.

In general if we have all observations in the sample
$\mathcal{S}\subset\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ are all in the weak
general position, then we have the following theorem from Criado et al.
(2021).

######  Definition 25.

Suppose we have a set $S\subset\mathbb{R}^{d}/\mathbb{R}{\bf
1}\cong\mathbb{R}^{d-1}$. $S$ is star convex with center
$x_{0}\in\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ if for any point $x\in S$ the
ordinary line segment $[x_{0},x]$ is contained in $S$.

######  Theorem 26 (Theorem 6 in Criado et al. (2021)).

If all observations in the sample
$\mathcal{S}\subset\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ are in weak general
position, then each tropical Voronoi region of $\mathcal{S}$ is the star
convex union of finitely many (possibly unbounded) semi-polytropes.

Many researchers study the geometry of a polytrope, which is both classically
convex and tropically convex (for example, Tran (2017); Joswig (2021); Tran
(2022)). It is well-known that a polytrope is a tropical simplex in
$\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ and their hyperplane representations on
polytropes Tran (2017). Tran in Tran (2017) showed the hyperplane-
representation of a polytrope $\mathcal{P}$ can be constructed from an
associated Kleene Star weight $d\times d$ matrix, $\mathbf{m^{*}}$ such that

$\mathcal{P}=\\{\mathbf{y}\in\mathbb{R}^{d}\;|\;y_{j}-y_{i}\leq-
m_{ij},y_{1}=0,m_{ij}\in\mathbf{m^{*}},i\neq j\\},$ (3)

where $m_{ij}$ is the $(i,j)$-th entry in $\mathbf{m^{*}}$.

######  Theorem 27.

The decision boundary of the tropical CNN is union of hyperplanes defined by
inequalities in (3).

######  Definition 28 (Tropical Fermat-Weber point).

A tropical Fermat-Weber point $x^{*}$ of a sample $\mathcal{S}=\\{p_{1},\ldots
p_{n}\\}\subset\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ with respect to the tropical
metric $d_{\rm tr}$ over the tropical projective torus
$\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ is defined by

$x^{*}=\operatorname*{arg\,min}_{x}\sum_{i=1}^{n}{d}_{\rm tr}(x,p_{i}).$ (4)

Let $w_{c}\in\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ be a tropical Fermat-Weber
point for a class $c\in[C]:=\\{1,\ldots,C\\}$ and we assume that each
observation $X:=(X_{1},\ldots,X_{d})$ for each class $c\in[C]$ is distributed
according to the Gaussian distribution around $w_{c}$ with the covariant
matrix $\sigma I_{d}$, where $\sigma>0$ and $I_{d}$ is the $d\times d$
identify matrix.

Therefore we have the following theorems:

######  Theorem 29.

The distribution of the tropical distance from $d_{\rm tr}(w_{c},X)$ is

$F(t)=P(d_{\rm tr}(w_{c},X)\leq t)=d\int_{-\infty}^{\infty}[G(\sigma
t+x)-G(x)]^{d-1}G^{\prime}(x)dx$

for $t>0$ where

$G(x)=\int_{-\infty}^{x}G^{\prime}(t)dt,\mbox{ and
}G^{\prime}(t)=\frac{\exp(-\frac{t^{2}}{2})}{\sqrt{2\pi}}.$

###### Proof.

Without loss of generality we set
$w_{c}:=(w_{c}^{1},\ldots,w_{c}^{d})=(0,\ldots,0)$. Then we have

$d_{\rm tr}(0,X)=\max X_{i}-\min X_{i}.$

This is the distribution of the range of $d$ i.i.d. normal random variables
with mean $0$ and standard deviation $\sigma>0$. Then we use the result from
Bland et al. (1966). ∎

######  Theorem 30.

Let

$E(l,d)=\frac{\sigma
d!}{(l-1)!(d-l)!}\int_{-\infty}^{\infty}x(1-\Phi(x))^{l-1}(\Phi)^{d-l}\phi(x)dx.$

Let $w^{(c)}$ be a tropical Fermat-Weber point. Then we have

$\displaystyle P(d_{\rm tr}(w_{c},X)\geq r)$ $\displaystyle\leq$
$\displaystyle\frac{E(d,d)-E(1,d)}{r}$

for some distance $r>0$.

###### Proof.

Without loss of generality we set
$w_{c}:=(w_{c}^{1},\ldots,w_{c}^{d})=(0,\ldots,0)$. By Harter (1961), we have
the expectation of $l$th ordered statistic of $d$ many i.i.d. standard normal
random variables is

$E^{\prime}(l,d)=\frac{d!}{(l-1)!(d-l)!}\int_{-\infty}^{\infty}x(1-\Phi(x))^{l-1}(\Phi)^{d-l}\phi(x)dx.$

So the expectation of $l$th ordered statistic of $d$ many i.i.d. normal random
variables around $0$ with its standard deviation $\sigma$ is

$E(l,d)=\frac{\sigma
d!}{(l-1)!(d-l)!}\int_{-\infty}^{\infty}x(1-\Phi(x))^{l-1}(\Phi)^{d-l}\phi(x)dx.$

Thus we have

$d_{\rm tr}(0,X)=\max X_{i}-\min X_{i}=E(d,d)-E(1,d).$

Then by Markov inequality we have

$\displaystyle P(d_{\rm tr}(0,X)\geq r)$ $\displaystyle\leq$
$\displaystyle\frac{E(d,d)-E(1,d)}{r}$

for $r>0$. ∎

######  Remark 31.

Barnhill et al. in Barnhill et al. (2024) showed that a tropical Fermat-Weber
point is very stable by Theorem 3 and it is robust against outlier(s).

##  5 Computational Experiments

Our experiment is to show that using a tropical layer as the final layer of a
standard, convolutional neural network can result in a model that is as
accurate as baseline models, requires no additional parameters, trains in a
similar time, and retains more prediction power when predicting adversarially
perturbed input data when compared to baseline models. Our experiment was
completed in Python using Tensorflow and high performance computing
resources.Our method begins by training tropical CNN models and other
benchmark models to predict labels on the training sets of three benchmark
image datasets: MNIST LeCun et al. (2010), SVHN Netzer et al. (2011), and
CIFAR-10 Krizhevsky (2009). Following training, we attacked the test set of
data using well-known techniques with varying norm constraints. To evaluate
our model’s robust characteristics, we compare our tropical CNN’s test set
error percentage against the test set error percentage of other baseline
models. To ensure comparisons are appropriately made, models for each dataset
have the same base model, and only differ in the final layer they use or in
the regularization technique employed. Benchmark models are both clean and
adversarially trained Madry et al. (2019) Goodfellow et al. (2015) ReLU and
Maxout Goodfellow et al. (2013b) models and the Maximum Margin Regularizer -
Universal (MMR) adapted from Croce and Hein (2020). Further details on model
construction, tropical layer implementation, attack hyperparameters, and
computation times are in Appendix A.

For the CIFAR-10 dataset, we use a ResNet50 model He et al. (2015) as our base
model111MMR was not evaluated for CIFAR-10 as re-creating the MMR-Universal
regularizer for a model as large as ResNet50 exceeded our computational budget
for the research. For MNIST and SVHN, we use a more simple convolutional
neural network with three convolution layers and one fully connected layer.
More details on the simple base model is outlined in Appendix Table 4.

To evaluate robustness, we utilized the following attacks

  * •

_SLIDE_. $\ell_{1}$ attack defined in Tramèr and Boneh (2019).

  * •

_PGD_. $\ell_{2}$ and $\ell_{\infty}$ Projected Gradient Descent from Madry et
al. (2019). For $\ell_{2}$, we use common Tensorflow methods to implement. For
$\ell_{\infty}$, we use the implementation in the CleverHans GitHub repository
Papernot et al. (2018).

  * •

_CW_. The $\ell_{2}$ Carlini and Wagner attack defined in Carlini and Wagner
(2017a) using the implementation from the CleverHans repository.

  * •

_SPSA_. Gradient-free $\ell_{\infty}$ attack utilizing CleverHans
implementation of SPSA from Uesato et al. (2018).

###  5.1 Results

The results from our experiment are in Table 1, 2, and 3 for our models
trained on the MNIST, SVHN, and CIFAR-10 datasets, respectively. In MNIST and
CIFAR in particular, our tropical CNN outperformed the ReLU and maxout models
against all attacks when trained normally. More is said on the adversarially
trained models in the Discussion. Another standout result from each of these
tables is that the CW attack, a powerful attack, routinely performed worse on
the tropical CNN, compared to the other models. We describe some possibilities
as to why it is unable to find an adversarial example in Appendix 5.4.

$\ell_{1}$ ($\epsilon=5.6$) $\ell_{2}$ ($\epsilon=2.8$) $\ell_{\infty}$
($\epsilon=0.1$) Model Clean SLIDE PGD CW (mean $\ell_{2}$)* PGD SPSA ReLU
0.99 % 20.93 % 36.39 % 99.25 % (2.28) 16.44 % 30.33 % Maxout 0.81 56.74 92.37
99.41 (2.22) 39.78 29.45 Tropical 0.71 15.01 27.59 5.97 (1.48) 8.74 3.91
ReLU+AT† 0.61 9.81 15.34 99.55 (3.89) 3.19 2.94 Maxout+AT 0.87 22.69 28.08
99.26 (3.71) 3.91 3.51 Tropical+AT 0.66 11.15 12.37 22.38 (3.25) 3.21 2.77 MMR
0.66 0.69 0.74 99.46 (5.59) 0.78 12.54 * The mean $\ell_{2}$ distortion for
the test set for adversarial examples found. If test error for $CW<100\%$,
then mean computed only on adversarial examples the CW algorithm was able to
find. Higher distortion indicates it is more difficult to find adversarial
examples for the model. † +AT indicates the model was trained with examples
that had been perturbed using the $\ell_{\infty}$ PGD attack as described in
Section 5.5

Table 1: MNIST results. Values reported are error percentage on the test set.

$\ell_{1}$ ($\epsilon=1.74$) $\ell_{2}$ ($\epsilon=0.87$) $\ell_{\infty}$
($\epsilon=\frac{4}{255}$) Model Clean SLIDE PGD CW (mean $\ell_{2}$) PGD SPSA
ReLU 9.96 % 43.42 % 66.85 % 94.92 % (0.63) 61.88 % 85.67 % Maxout 10.54 67.01
96.52 94.38 (0.47) 95.88 92.51 Tropical 10.56 42.04 75.17 42.20 (0.82) 68.65
36.33 ReLU+AT 9.41 29.76 42.77 95.05 (0.97) 35.74 28.60 Maxout+AT 8.66 29.50
43.14 95.31 (0.92) 35.25 30.21 Tropical+AT 11.09 32.84 44.02 93.75 (0.94)
37.20 31.04 MMR 12.69 27.81 31.82 93.76 (1.02) 31.46 75.51

Table 2: SVHN results. Values reported are error percentage on the test set.

$\ell_{1}$ ($\epsilon=1.74$) $\ell_{2}$ ($\epsilon=0.87$) $\ell_{\infty}$
($\epsilon=\frac{4}{255}$) Model Clean SLIDE PGD CW (mean $\ell_{2}$) PGD SPSA
ReLU 29.61 % 54.51 % 88.60 % 85.48 % (0.55) 86.72 % 83.79 % Maxout 27.74 54.48
97.92 86.32 (0.53) 95.31 85.53 Tropical 29.13 51.81 73.39 60.1 (0.87) 71.54
59.86 ReLU+AT 32.01 42.30 67.46 85.31 (1.15) 65.08 55.16 Maxout+AT 32.47 42.58
67.54 85.23 (1.14) 64.98 56.03 Tropical+AT 31.69 42.57 67.08 66.35 (1.04)
64.67 54.84

Table 3: CIFAR-10 results. Values reported are error percentage on the test
set.

###  5.2 Decision Boundaries Visualized

######  Example 32.

Let us consider a tropical CNN with the same base model as the MNIST and SVHN
models, except the layer before our tropical layer contains only three
neurons. Despite this reduction in neurons, a very accurate model can be
trained on the 10 classes of the MNIST dataset ($97.5\%$ test accuracy). We
then took the trained weights of our tropical layer (10 neurons with three
weights each), projected them onto the three dimensional tropical projective
torus $\mathbb{R}^{3}/\mathbb{R}{\bf 1}$, which is isomorphic to the two
dimensional Euclidean space $\mathbb{R}^{2}$, by subtracting all weights by
the middle weight, and computed a contour plot that shows tropical distances
to the nearest class of the 10 classes. Following this, we fed a subset of
training data from each class into the model in order to capture the outputs
at our three-neuron layer. We then projected the outputs of the training data
at this layer onto the tropical projective torus in the same manner. From
this, we can compute the decision boundary of our network as they relate to
the weights in our tropical layer. Figure 5(a) and 5(b) show a two dimensional
representation of our neural network decision boundaries in the tropical
projective torus as well as where the training data falls relative to the
tropical weights, providing an intuitive visual of the tropical decision
boundary described in Section 4. We provide a ReLU CNN analog to this tropical
CNN example in Appendix B.

(a) Heat-map plot for distance from trained weights with samples of input data
as they are fed into the tropical logit layer.

(b) Voronoi cell plot for distance from trained weights with samples of input
data as they are fed into the tropical logit layer.

Figure 5: Decision boundaries MNIST-trained example.

###  5.3 Discussion

For CIFAR-10 and MNIST datasets, the test error for the tropical model more
closely matched the robust models across all attacks, while it maintained
parity with standard models on SVHN. However, outside of the class of PGD
attacks (ie CW and SPSA), the tropical model still more closely resembled the
robust models in test error on SVHN.

Across attacks and data sets, the AT effect of straitening of decision
boundaries appears to negate the effect of the tropical embedding layer on the
decision boundary discussed in this paper Moosavi-Dezfooli et al. (2018).
Notably, the CW attack was able to find more adversarial examples on a
tropical model with AT than a tropical model without AT, although at a greater
mean $\ell_{2}$.

The elegance of our tropical CNN is that we are able to achieve robust
characteristics and maintain a high level of accuracy, while remaining
computationally efficient and without increasing model size. This is
especially desirable since state-of-the-art techniques for ensuring robustness
in neural networks are prohibitively expensive in terms of computational
budget or in terms of accuracy lost on unperturbed data. Our tropical model is
able to maintain a parity with benchmark models in terms of accuracy, without
noticeably increasing computation time or number of model parameters. Precise
training times and parameter counts are details in A.4. The MMR models, for
instance, showed outstanding results in terms of robust characteristics, but
took roughly two orders of magnitude longer to train than the tropical model,
whereas our tropical model trains in nearly the same time as the ReLU model
for every dataset evaluated. The differences in attack results in Table 1
between the MMR and tropical models is stark as the MMR model far outperformed
on all attacks except for the CW and SPSA attack, but the idea that we can
achieve robust properties in a neural network with a simple change to how 1
layer connects, without damaging computational efficiency in a material way,
is an novel way to apply the properties of tropical geometry in neural
networks.

One can imagine that the computational complexity of our tropical model would
increase as the dimensionality of the tropical layer itself increases given we
have $max$ and a $min$ operations in our formulation, but embedding the
tropical layer as the last layer keeps the dimensionality relatively low and
depends only on the number of classes the model is trying to predict and the
number of neurons in the layer preceding the final layer. The training times
observed in A.4 show that the models in our experiment experienced no adverse
training time impact, especially when compared the ReLU counterpart of the
exact same construction.

###  5.4 Adversarial Attacks on Classifiers

Here we consider classifiers that can be viewed as functions
$f:\mathbb{R}^{d}\times\Theta\rightarrow[C]$, where $d\in\\{1,2,\dots\\}$ is
the number of input features, $\Theta$ is a (finite-dimensional) space of
feasible model parameters (e.g., the weights and biases of a neural network),
and $[C]:=\\{1,\ldots,C\\}$ for $C\in\\{2,3,\ldots,\\}$ is a finite set of
class labels. Given $\theta\in\Theta$, an input with features
$x\in\mathbb{R}^{d}$ is predicted to be of class $f(x,\theta)\in[C]$. The
model parameter $\theta$ is typically chosen with the aid of a finite set
$D\subset\mathbb{R}^{d}\times[C]$ of $n=|D|$ training examples. More
precisely, let $L(\hat{y},y)$ denote the loss incurred when the predicted
class is $\hat{y}\in[C]$ and the true class is $y\in[C]$. The model parameter
$\theta$ is typically “fitted” to the training dataset $D$ by solving the
following optimization problem:

minimize $\displaystyle\quad\frac{1}{n}\sum_{(x,y)\in
D}L\left(f(x,\theta),y\right)$ subject to $\displaystyle\quad\theta\in\Theta$

where $n$ is the number of observations in the training dataset $D$.

Classifier neural networks take input pairs $(x,y)$, $x\in\mathbb{R}^{d}$ and
$y\in{K}$, and fit a set of parameters $\Theta$ on a function
$f(x;\Theta):(x_{1},...,x_{d})\xrightarrow{}(x_{1},...,x_{k})$ to minimize an
expected loss function $L(f(x,\Theta),y)$. Then the problem can be formulated
as an optimization problem:

$min_{\Theta}\ L(f(x;\Theta),y)$

Fixing $\theta\in\Theta$ (e.g., supposing that the model has been fitted), an
adversarial attack consists of adding perturbations to certain inputs
$x\in\mathbb{R}^{d}$, with the aim of forcing the fitted model to mis-classify
these inputs. For example, if the aim is to force the model to mis-classify
the input $x$, whose true class is $y\in[C]$, the perturbation
$\delta\in\mathbb{R}^{d}$ is selected by solving the following optimization
problem, where $\Delta$ is the set of feasible perturbations:

maximize $\displaystyle\quad L\left(f(x+\delta,\theta),y\right)$ subject to
$\displaystyle\quad\delta\in\Delta$

The feasible region $\Delta$ is often taken to be an $\epsilon-$ball with
respect to a specified norm $\|\cdot\|$ on $\mathbb{R}^{d}$ (e.g., an
$\ell_{p}$ norm); see e.g., Madry et al. (2019). Alternatively, the adversary
seeks to force misclassification, analogous to maximizing the expected value
of $L$, without changing the true class of the input. The attackers problem is
constrained to some budget $\epsilon$, the maximum perturbation with respect
to some ${\left\|.\right\|}_{p}$ which maintains perceptual similarity
Goodfellow et al. (2015). Then, the attackers problem can be formulated as:

$\max_{\delta}\ L(f(x+\delta;\Theta),y)\ s.t.\
{\left\|\delta\right\|}_{p}\leq\epsilon$

We will consider three well-known approaches for generating adversarial
attacks. The first, Projected Gradient Descent (PGD), consists of iteratively
perturbing a clean input in the direction of the gradient of the mapping
$\delta\mapsto L\left(f(x+\delta,\theta),y\right)$; see e.g., Madry et al.
(2019). Specifically, starting with an initial perturbation $\delta_{0}$,
setting $t=0$, and for $x\in\mathbb{R}^{d}$ letting
$\Pi_{\Delta}[x]:=\operatorname*{arg\,min}_{\delta\in\Delta}\|x-\delta\|$
denote the projection of $x$ onto $\Delta$, PGD generates a sequence of
perturbations $\delta_{t}$ where

$\delta_{t+1}=\Pi_{\Delta}\left[\delta_{t}+\alpha\nabla
L\left(f(x+\delta_{t},\theta\right),y)\right],\qquad t=0,1,\dots$

using a given step size $\alpha$.

$x^{t+1}=\Pi_{S}(x_{0})(x_{t}+\alpha\nabla_{x}L(f(x,\Theta),y)$

Where $\Pi_{S}(x_{0})$ is the projection onto the set
$S(x_{0})=\\{x\in\mathbb{R}^{d}\ |\ {\left\|x-x_{0}\right\|}_{p}<\epsilon\\}$
The second approach, due to Carlini & Wagner Carlini and Wagner (2017b), is
based on solving an optimization problem to find the smallest perturbation
(with respect to a given $\ell_{p}$ norm) that will cause the input $x$ to be
mis-classified as being from a target class $\tau$. Specifically, letting
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a function such that
$f(x+\delta)\leq 0$ if and only if $x+\delta$ is classified as being from
class $\tau$, and letting $c$ be a positive constant, the optimization problem
is to

minimize $\displaystyle\quad\|\delta\|_{p}+c\cdot f(x+\delta)$ subject to
$\displaystyle\quad x+\delta\ \ \text{is a valid input}$

Here, “valid input” can mean, for example, that $x+\delta$ is an image with
valid pixel values (e.g., on $[0,1]$). Carlini & Wagner Carlini and Wagner
(2017b) experimented with various objective functions $f$ and constants $c$ in
order to develop tailored $\ell_{2}$, $\ell_{0}$, and $\ell_{\infty}$ attacks
able to defeat (at the time) state-of-the-art defenses. The following example
may explain the possible reason why tropical CNN is robust against CW.

######  Example 33.

We consider the perturbation $\delta$ of a feature
$x\in\mathbb{R}^{3}/\mathbb{R}{\bf 1}$ by Carlini & Wagner (CW) attack in the
same setting as in Figure 4 and Lemma 22, where the bisector between
$w^{*}_{1,1}=(0,0,0)$ and $w^{*}_{2,1}=(1,w,0)$ is the decision boundary.
Without loss of generality, we assume that $x$ belongs to the class for
$w^{*}_{1,1}$. For simplicity, we consider there is no hidden layer (=logistic
regression). Then the perturbation $\delta$ to make $x^{\prime}:=x+\delta$
look like $w^{*}_{1,1}$ is given by solving the following optimization:

$\min_{x^{\prime}}\quad-d_{\rm tr}(w^{*}_{2,1},x^{\prime})+d_{\rm
tr}(w^{*}_{1,1},x^{\prime})+cd_{\rm tr}(x,x^{\prime}).$

This is because we share the term $d_{\rm tr}(w^{*}_{1,1},x)$ in the loss
function of the tropical CNN and the constraint function of CW. We define a
gradient flow for the distance function as in Figure 6 (left). (This is
basically the gradient of the distance function except at the boundary, on
which we selected one natural flow from the subgradient.) The gradient flow
when $w=0.5$ and $c=0$ is illustrated in Figure 6 (right). The gradient flow
is rather inefficient and it can be even $0$ in the green regions. Note that
the small term proportional to $c$ that attracts $x^{\prime}$ to $x$ should be
added further. Then if $x$ is in one of the green regions, $x^{\prime}$ just
goes back to $x$. This result may support the idea that tropical CW attack is
rather inefficient.

Figure 6: The gradient flow of the distant function from the origin (left) and
the gradient flow for the CW attack with $c=0$ (right). The dotted line
($x=0.5$) represents the decision boundary. The gradient flow is zero at the
green regions.

Carlini and Wagner’s (C&W) attack bypasses the loss function and maximizes the
difference between the logits associated with the input class, $Z(x)_{i}$, and
alternative adversary class, $Z(x)_{t}$ Carlini and Wagner (2017b):

$\min_{x,t}\ Z(x)_{i}-Z(x)_{t}$ $s.t.{\left\|x-x_{0}\right\|}_{p}<\epsilon$

Finally, we consider a “gradient-free” method called Simultaneous Perturbation
Stochastic Approximation (SPSA) Spall (2003), which was used by Uesato et al.
Uesato et al. (2018) to generate adversarial attacks.

The final method, collectively known as gradient-free, attacks models defended
by obfuscating the loss function gradient Uesato et al. (2018), Athalye et al.
(2018). There are a variety of gradient-free attacks with different
approaches, but in general, they are less powerful than the gradient based
approaches listed previously. In this paper, we use the SPSA attack Uesato et
al. (2018) which takes stochastic sample perturbations within an $\epsilon>0$
ball of $x_{0}$ and estimates loss gradient based off their difference.

Possible reason why tropical CNN is robust against CW: We assume that
$c\in[C]$ is the correct class for an observation
$x_{c}\in\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ in the dataset such that the true
response for an observation $x_{c}$ is $c\in[C]$ and
$\hat{w}^{(c)}\in\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ is the estimated weight for
the class $c\in[C]$. Suppose
$\hat{w}^{(c^{\prime})}\in\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ is the estimated
weight for the class $c^{\prime}\in[C]$ such that $c^{\prime}\not=c$. We would
like to note that a tropical geodesic between two points is not unique (for
example, Example 5.21 in Joswig (2022)). In fact the set of all possible
tropical geodesics between two points forms a tropical polytrope, which is a
classical polytope and tropical polytope in the tropical projective torus. Let
$P(\hat{w}^{(c)},\hat{w}^{(c^{\prime})})$ be the set of all tropical geodesics
between $\hat{w}^{(c)}$ and $\hat{w}^{(c)}$, which is a polytrope containing
$\hat{w}^{(c)}$ and $\hat{w}^{(c^{\prime})}$. Also note that the decision
boundary $\mathcal{B}(\hat{w}^{(c)},\hat{w}^{(c^{\prime})})$ defined by
$\hat{w}^{(c)}$ and $\hat{w}^{(c^{\prime})}$ dissects
$P(\hat{w}^{(c)},\hat{w}^{(c^{\prime})})$ such that

$r_{c,c^{\prime}}:=d_{\rm
tr}(\hat{w}^{(c)},\mathcal{B}(\hat{w}^{(c)},\hat{w}^{(c^{\prime})}))=d_{\rm
tr}(\hat{w}^{(c^{\prime})},\mathcal{B}(\hat{w}^{(c)},\hat{w}^{(c^{\prime})}))$

and

$\mathcal{B}(\hat{w}^{(c)},\hat{w}^{(c^{\prime})})\cap
P(\hat{w}^{(c)},\hat{w}^{(c^{\prime})})\not=\emptyset.$

We consider a case which the perturbation by Carlini & Wagner (CW) attack
$x+\delta\in\mathbb{R}^{d}/\mathbb{R}{\bf 1}$ is near the decision boundary
$\mathcal{B}(\hat{w}^{(c)},\hat{w}^{(c^{\prime})})$ defined by $\hat{w}^{(c)}$
and $\hat{w}^{(c^{\prime})}$. This means that $x+\delta\in
P(\hat{w}^{(c)},\hat{w}^{(c^{\prime})})$. We also assume that $x\in P$ without
loss of generality since if $x\not\in P(\hat{w}^{(c)},\hat{w}^{(c^{\prime})})$
then for some iterations $t$, the perturbation by CW attack $x:=x+\delta_{t}$
is closer to the decision boundary, i.e., $x:=x+\delta_{t}\in P$.

Without loss of generality, we assume that $\hat{w}^{(c)}=0$. Here we have

$\displaystyle\text{minimize in }\delta$ $\displaystyle\quad d_{\rm
tr}(0,x+\delta)$ (5) subject to $\displaystyle\quad d_{\rm tr}(0,x+\delta)\geq
r_{c,c^{\prime}}.$

Let

$y=d_{\rm tr}(0,x+\delta).$

######  Definition 34 (sectors for hyperplane $H_{\omega}$).

The $k$-th open sector for the max-tropical hyperplane $H^{\max}_{\omega}$ is
$G^{\max}_{\omega}(k)=\\{x|x_{k}+\omega_{k}>x_{i}+\omega_{i}\textrm{ for
}1\leq i(\neq k)\leq d\\}$. The $l$-th open sector for the min-tropical
hyperplane $H^{\min}_{\omega}$ is
$G^{\min}_{\omega}(l)=\\{x|x_{l}+\omega_{l}<x_{i}+\omega_{i}\textrm{ for
}1\leq i(\neq l)\leq d\\}$. The $k$-th closed sector for the max-tropical
hyperplane $H^{\max}_{\omega}$ is
$\overline{G^{\max}_{\omega}}(k)=\\{x|x_{k}+\omega_{k}\geq
x_{i}+\omega_{i}\textrm{ for }1\leq i(\neq k)\leq d\\}$. The $l$-th closed
sector for the min-tropical hyperplane $H^{\min}_{\omega}$ is
$\overline{G^{\min}_{\omega}}(l)=\\{x|x_{l}+\omega_{l}\leq
x_{i}+\omega_{i}\textrm{ for }1\leq i(\neq l)\leq d\\}$.

######  Lemma 35 (Lemma 17 in FW point paper).

For $x\in G^{\max}_{\omega}(k)\cap G^{\min}_{\omega}(l)$, $d_{\rm
tr}(0,x+\omega)=x_{k}+\omega_{k}-x_{l}-\omega_{l}$ and its gradient is given
as $\frac{\partial d_{\rm
tr}(0,x+\omega)}{\partial\omega_{i}}=\delta_{ik}-\delta_{il}$, where
$\delta_{ij}$ is the Kronecker’s delta such that

$\delta_{ij}=\begin{cases}1&\mbox{if }i=j\\\ 0&\mbox{otherwise.}\end{cases}$

######  Lemma 36 (Lemma 29 in Barnhill and Sabol et al.).

The gradient given in Lemma 35 changes when and only when $w$ cross the sector
boundary defined by the tropical min and max hyperplanes of $x$.

######  Remark 37.

Since the problem in (5) is a special case of the problem in Barnhill et al.
(2024). By Theorem 2 in Barnhill et al. (2024), the gradient in Lemma 35
achieves its minimum. Barnhill and Sabol et al. discussed that when we have a
lower dimensional set of optimal solutions pass through the set by Lemma 36.
We observed this behaviors in our experiments.

###  5.5 Defenses Against Adversarial Attacks

The adversarial training (AT) defense, initially proposed in Goodfellow et al.
(2015), consists of training a model on both clean and perturbed inputs. Madry
et al. Madry et al. (2019) used Projected Gradient Descent (PGD) on the loss
function to generate a ’best’ first-order attack, and continued to train the
model until it classified the adversarial inputs correctly. Incorporating
these attacks in training effectively results in a more linear decision
boundary in the neighborhood of natural inputs Moosavi-Dezfooli et al. (2018).
By reducing the curvature of the decision boundary, the classifier becomes
less vulnerable to ’shortcut’ attacks that use the loss gradient to perturb
across the closest decision boundary.

Regularization-based defenses take a more direct approach to achieve a similar
effect. Often, they penalize small distances between observations and decision
boundaries, effectively pushing the closest segments away and straightening
the loss function. This is achieved by incorporating a $\ell_{p}$
$\epsilon$-ball into the defenders problem either by minimizing the loss
within an $\epsilon$-ball of the input as in Wong and Kolter (2018), or by
directly widening the linear region around training inputs with respect to
some $\ell_{p}$ norm Croce et al. (2019), Croce and Hein (2020).

With some exceptions Croce and Hein (2020), robust models are robust only to
the specific norm on which they were trained Tramèr and Boneh (2019), and
require significant computational resources to train, either through iterative
training as in AT or through calculation of the regularization term. In this
paper we show simultaneous robustness against attacks based on $\ell_{1}$,
$\ell_{2}$, and $\ell_{\infty}$ norms, using less computational time than
adversarial training.

##  6 Conclusion

Motivated by the low-rank nature of image classification, we apply tools from
tropical geometry with the max-plus algebra over the tropical semiring to
CNNs, and introduce a tropical CNN. We also demonstrate that this novel CNN is
robust against white box adversarial attacks via computational experiments on
image datasets. We show that it is especially robust against CW attacks.

In this paper we focus on image datasets. Deep neural networks have also been
applied to text analysis (for example, Suissa et al. (2023)). For text,
researchers apply tools from linguistics that were originally developed for
genetics and genomics. Yoshida et al. in Yoshida et al. (2023b) applied neural
networks with tropical embedded layer to phylogenomics. Therefore it would be
interesting to apply tropical CNNs to datasets for text analysis and mining.

Theorem 30 assumes Gaussian data about $w_{c}$. However, 5(a) suggests that
the convolutional and ReLU layers prior to the embedding layer generate
features that do not have a symmetric distribution about $w_{c}$, indicating
the possibility of a tighter upper bound on $P(d_{\rm tr}(w_{c},X)\geq r)$.

From the computational results in Section 5.1 on tropical CNNs with
adversarial training, we observe that adversarial training makes the
robustness of tropical CNNs similar to the robustness of CNNs with ReLU
activators with adversarial training (i.e., adversarial training makes
tropical CNNs less robust against adversarial attacks). These results suggest
that the adversarial training effect Moosavi-Dezfooli et al. (2018) may be
negating the effect of the tropical embedding layer. It is interesting to
investigate the geometry of the effects of adversarial training to tropical
CNNs.

## Acknowledgement

RY is partially supported by the National Science Foundation (Grant No.
DMS-1929348). KM is partially supported by JSPS KAKENHI Grant Numbers
JP22K19816 and JP22H02364.

## References

  * Huang et al. [2017] Sandy H. Huang, Nicolas Papernot, Ian J. Goodfellow, Yan Duan, and Pieter Abbeel.  Adversarial attacks on neural network policies.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings_ , pages dblp computer science bibliography, https://dblp.org. OpenReview.net, 2017\.  URL https://openreview.net/forum?id=ryvlRyBKl.
  * Papernot et al. [2018] Nicolas Papernot, Fartash Faghri, Nicholas Carlini, Ian Goodfellow, Reuben Feinman, Alexey Kurakin, Cihang Xie, Yash Sharma, Tom Brown, Aurko Roy, Alexander Matyasko, Vahid Behzadan, Karen Hambardzumyan, Zhishuai Zhang, Yi-Lin Juang, Zhi Li, Ryan Sheatsley, Abhibhav Garg, Jonathan Uesato, Willi Gierke, Yinpeng Dong, David Berthelot, Paul Hendricks, Jonas Rauber, and Rujun Long.  Technical report on the cleverhans v2.1.0 adversarial examples library.  _arXiv preprint arXiv:1610.00768_ , 2018.
  * Madry et al. [2018] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In _International Conference on Learning Representations_ , page https://openreview.net/forum?id=rJzIBfZAb, 2018.
  * Kotyan and Vargas [2022] S Kotyan and DV Vargas.  Adversarial robustness assessment: Why in evaluation both $l_{0}$ and $l_{\infty}$ attacks are necessary.  _PLoS One_ , 14(17(4)):e0265723, 2022.  doi: 10.1371/journal.pone.0265723.
  * Carlini and Wagner [2017a] Nicholas Carlini and David Wagner.  Towards evaluating the robustness of neural networks, 2017a.
  * Croce et al. [2019] Francesco Croce, Maksym Andriushchenko, and Matthias Hein.  Provable robustness of relu networks via maximization of linear regions.  _AISTATS 2019_ , 2019.
  * Croce and Hein [2020] Francesco Croce and Matthias Hein.  Provable robustness against all adversarial $l_{p}$-perturbations for $p\geq 1$, 2020.
  * Qian et al. [2022] Zhuang Qian, Kaizhu Huang, Qiu-Feng Wang, and Xu-Yao Zhang.  A survey of robust adversarial training in pattern recognition: Fundamental, theory, and methodologies.  _Pattern Recognition_ , 131:108889, 2022.  ISSN 0031-3203.  doi: https://doi.org/10.1016/j.patcog.2022.108889.  URL https://www.sciencedirect.com/science/article/pii/S0031320322003703.
  * Tu et al. [2019] Zhuozhuo Tu, Jingwei Zhang, and Dacheng Tao.  Theoretical analysis of adversarial learning: a minimax approach.  In _Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , page 11, Red Hook, NY, USA, 2019. Curran Associates Inc.
  * Yang et al. [2019] Yuzhe Yang, Guo Zhang, Dina Katabi, and Zhi Xu.  ME-Net: Towards effective adversarial robustness with matrix estimation.  In _Proceedings of the 36th International Conference on Machine Learning (ICML)_ , page https://arxiv.org/abs/1905.11971, 2019.
  * Phan et al. [2022] Huy Phan, Miao Yin, Yang Sui, Bo Yuan, and Saman A. Zonouz.  Cstar: Towards compact and structured deep neural networks with adversarial robustness.  _CoRR_ , abs/2212.01957, 2022.  URL https://doi.org/10.48550/arXiv.2212.01957.
  * Wang et al. [2023] Andong Wang, Chao Li, Mingyuan Bai, Zhong Jin, Guoxu Zhou, and Qibin Zhao.  Transformed low-rank parameterization can help robust generalization for tensor neural networks.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , page https://openreview.net/forum?id=rih3hsSWx8, 2023.
  * Maclagan and Sturmfels [2015] D. Maclagan and B. Sturmfels.  _Introduction to Tropical Geometry_ , volume 161 of _Graduate Studies in Mathematics_.  Graduate Studies in Mathematics, 161, American Mathematical Society, Providence, RI, 2015.
  * Joswig [2022] Michael Joswig.  _Essentials of tropical combinatorics_.  Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2022.
  * Yoshida et al. [2023a] Ruriko Yoshida, Misaki Takamori, Hideyuki Matsumoto, and Keiji Miura.  Tropical support vector machines: Evaluations and extension to function spaces.  _Neural Networks_ , 157:77–89, 2023a.  ISSN 0893-6080.
  * Miura and Yoshida [2023] K. Miura and R. Yoshida.  Plücker coordinates of the best-fit stiefel tropical linear space to a mixture of gaussian distributions.  _Info. Geo._ , 6:171–201, 2023.
  * Aliatimis et al. [2023] Georgios Aliatimis, Ruriko Yoshida, Burak Boyaci, and James A. Grant.  Tropical logistic regression model on space of phylogenetic trees, 2023\.  Available at https://arxiv.org/abs/2306.08796.
  * Yoshida et al. [2023b] Ruriko Yoshida, Georgios Aliatimis, and Keiji Miura.  Tropical neural networks and its applications to classifying phylogenetic trees, 2023b.  Available at https://arxiv.org/abs/2309.13410.
  * Glorot et al. [2011] Xavier Glorot, Antoine Bordes, and Yoshua Bengio.  Deep sparse rectifier neural networks.  In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , volume 15 of _Proceedings of Machine Learning Research_ , pages 315–323, Fort Lauderdale, FL, USA, 11–13 Apr 2011\. PMLR.  URL https://proceedings.mlr.press/v15/glorot11a.html.
  * Zhang et al. [2018] Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim.  Tropical geometry of deep neural networks.  In _International Conference on Machine Learning_ , pages 5824–5832. PMLR, 2018.
  * Goodfellow et al. [2013a] Ian Goodfellow, David Warde-Farley, Mehdi Mirza, Aaron Courville, and Yoshua Bengio.  Maxout networks.  In Sanjoy Dasgupta and David McAllester, editors, _Proceedings of the 30th International Conference on Machine Learning_ , volume 28 of _Proceedings of Machine Learning Research_ , pages 1319–1327, Atlanta, Georgia, USA, 17–19 Jun 2013a. PMLR.  URL https://proceedings.mlr.press/v28/goodfellow13.html.
  * Charisopoulos and Maragos [2018] Vasileios Charisopoulos and Petros Maragos.  A tropical approach to neural networks with piecewise linear activations.  _ArXiv_ , abs/1805.08749, 2018.  URL https://api.semanticscholar.org/CorpusID:46895499.
  * Carlini and Wagner [2017b] Nicholas Carlini and David Wagner.  Towards evaluating the robustness of neural networks.  In _2017 IEEE Symposium on Security and Privacy (SP)_ , pages 39–57, 2017b.  doi: 10.1109/SP.2017.49.
  * Monod et al. [2019] A. Monod, B. Lin, Q. Kang, and R. Yoshida.  Tropical foundations for probability & statistics on phylogenetic tree space, 2019.
  * Criado et al. [2022] F. Criado, M. Joswig, and F. Santos.  Tropical bisectors and voronoi diagrams.  _Found Comput Math_ , 22:1923–1960, 2022.  https://doi.org/10.1007/s10208-021-09538-4.
  * Barnhill et al. [2024] D. Barnhill, J. Sobal, R. Yoshida, and K. Miura.  Tropical fermat-weber polytopes, 2024.  In progress.
  * Zhou [2020] Ding-Xuan Zhou.  Universality of deep convolutional neural networks.  _Applied and Computational Harmonic Analysis_ , 48(2):787–794, 2020.  ISSN 1063-5203.  doi: https://doi.org/10.1016/j.acha.2019.06.004.  URL https://www.sciencedirect.com/science/article/pii/S1063520318302045.
  * Barnhill et al. [2023] D. Barnhill, R. Yoshida, and K. Miura.  Maximum inscribed and minimum enclosing tropical balls of tropical polytopes and applications to volume estimation and uniform sampling, 2023.  Available at https://arxiv.org/abs/2303.02539.
  * Brandenburg et al. [2023] Marie-Charlotte Brandenburg, Sophia Elia, and Leon Zhang.  Multivariate volume, ehrhart, and $h^{*}$-polynomials of polytropes.  _J. Symb. Comput._ , 114(C):209–230, jan 2023\.  ISSN 0747-7171.  doi: 10.1016/j.jsc.2022.04.011.  URL https://doi.org/10.1016/j.jsc.2022.04.011.
  * Criado et al. [2021] Francisco Criado, Michael Joswig, and Francisco Santos.  Tropical bisectors and voronoi diagrams.  _Foundations of Computational Mathematics_ , 22(6):1923–1960, September 2021.  ISSN 1615-3383.  doi: 10.1007/s10208-021-09538-4.  URL http://dx.doi.org/10.1007/s10208-021-09538-4.
  * Tran [2017] Ngoc Mai Tran.  Enumerating polytropes.  _Journal of Combinatorial Theory, Series A_ , 151:1–22, 2017.  ISSN 0097-3165.  doi: https://doi.org/10.1016/j.jcta.2017.03.011.  URL https://www.sciencedirect.com/science/article/pii/S0097316517300389.
  * Joswig [2021] Michael Joswig.  _Essentials of Tropical Combinatorics_.  Springer, New York, NY, 2021.
  * Tran [2022] Ngoc M Tran.  The tropical geometry of causal inference for extremes, 2022.  URL https://arxiv.org/abs/2207.10227.
  * Bland et al. [1966] R. P. Bland, R. D. Gilbert, C. H. Kapadia, and D. B. Owen.  On the distributions of the range and mean range for samples from a normal distribution.  _Biometrika_ , 53(1/2):245–248, 1966.  ISSN 00063444.  URL http://www.jstor.org/stable/2334072.
  * Harter [1961] H. Leon Harter.  Expected values of normal order statistics.  _Biometrika_ , 48(1/2):151–165, 1961.
  * LeCun et al. [2010] Yann LeCun, Corinna Cortes, and CJ Burges.  Mnist handwritten digit database, 2010.
  * Netzer et al. [2011] Yuval Netzer, Tao Wang, Adam Coates, A. Bissacco, Bo Wu, and A. Ng.  Reading digits in natural images with unsupervised feature learning.  In _Advances in Neural Information Processing Systems (NIPS)_ , page https://api.semanticscholar.org/CorpusID:16852518, 2011.
  * Krizhevsky [2009] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, University of Toronto, 2009.
  * Madry et al. [2019] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks, 2019.
  * Goodfellow et al. [2015] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples, 2015.
  * Goodfellow et al. [2013b] Ian J. Goodfellow, David Warde-Farley, Mehdi Mirza, Aaron Courville, and Yoshua Bengio.  Maxout networks, 2013b.
  * He et al. [2015] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition, 2015.
  * Tramèr and Boneh [2019] Florian Tramèr and Dan Boneh.  Adversarial training and robustness for multiple perturbations, 2019.
  * Uesato et al. [2018] Jonathan Uesato, Brendan O’Donoghue, Aaron van den Oord, and Pushmeet Kohli.  Adversarial risk and the dangers of evaluating against weak attacks, 2018\.
  * Moosavi-Dezfooli et al. [2018] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard.  Robustness via curvature regularization, and vice versa, 2018.
  * Spall [2003] James C. Spall.  _Introduction to Stochastic Search and Optimization_.  John Wiley & Sons, Inc, 2003.
  * Athalye et al. [2018] Anish Athalye, Nicholas Carlini, and David Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples, 2018.
  * Wong and Kolter [2018] Eric Wong and J. Zico Kolter.  Provable defenses against adversarial examples via the convex outer adversarial polytope, 2018.
  * Suissa et al. [2023] Omri Suissa, Avshalom Elmalech, and Maayan Zhitomirsky-Geffet.  Text analysis using deep neural networks in digital humanities and information science, 2023.  Available at arxiv.org/abs/2307.16217.

##  Appendix A Additional Computational Results

Here we capture the details of our implementation of a tropical CNN experiment
that was briefly details in Section 5.

###  A.1 Model Construction

Table 4 shows the neural network construction of our base model used to train
models on the MNIST and SVHN datasets.

Table 4: Base Model for MNIST and SVHN experiments. Layer | Activation | Key Parameters
---|---|---
Convolution | ReLU | 64, 3x3 windows, 1x1 strides
Max Pooling |  | 2x2 windows, non-intersecting
Convolution | ReLU | 64, 3x3 windows, 1x1 strides
Max Pooling |  | 2x2 windows, non-intersecting
Convolution | ReLU | 64, 3x3 windows, 1x1 strides
Flatten |  | Flatten feature map
Fully connected | ReLU | 64 neurons

The models used in our experiment we refer to as Tropical, ReLU, Maxout, and
MMR. The Tropical model is defined as adding 1 tropical embedding layer to the
base model as defined in Equation 1, which produces the logits used for
classification instead of a typical, fully-connected layer. Our logit logic
differs from a typical full-connected layer because the minimum value is
considered the correct class and not the maximum value. The value’s in our
case are the tropical distance from the output of the base model to the
weights of final layer, and thus we want to minimize this distance. To account
for this in our experiment we take $z=50-d_{\rm tr}(x,w)$, where $z$ is our
logits, $x$ the output from the base model, and $w$ the trained weights of the
final layer. By taking the negative of the distance values ($d_{\rm
tr}(x,w)$), this allows us to keep the logic that the maximum value is correct
class and adding an arbitrary amount22250 in our case because $d_{\rm
tr}(x,w)$ was typically observed between 5 and 30. In practice, one could take
the negative of the output without adding this arbitrary amount. only served
to prevent any logic issues among our attack algorithms in dealing with
negative numbers. For the ReLU model we connect a typical, fully-connected
layer to the base model in order to produce logits for classification. For the
Maxout models, we connect the layers outlined in Table 5 to the base model.
This implements the maxout units as defined in Goodfellow et al. [2013b],
which appears to show similar construction as our tropical model given the
logits are produced by subtracting 2 values, but we will show through our
experiment results that our model and the maxout model behave very
differently. The MMR model is identical to the ReLU model, but uses the MMR-
Universal regularizer defined in Croce and Hein [2020] and adapted to our
model. The MMR-Universal regularizer attempts ”enforce robustness wrt
$\ell_{1}$\- and $\ell_{\infty}$-perturbations and show how that leads to the
first provably robust models wrt any $\ell_{p}$-norm for $p\geq 1$” Croce and
Hein [2020]. For the Tropical, ReLU, and Maxout models, we also train and
evaluate models that are trained using adversarial examples as defined in
Section 5.5.

Table 5: Maxout Model Layer | Activation | Key Parameters
---|---|---
Fully connected 1 | ReLU | 10*100 neurons,connected to base
Fully connected 2 | ReLU | 10*100 neurons,connected to base
Dropout |  | 0.5 dropout rate
Maxout 1 | Maxout | 10 units, max from FC1
Maxout 2 | Maxout | 10 units, max from FC2
Final Layer | Maxout 1 - Maxout 2 |

For the MNIST and SVHN dataset, we compared the tropical model’s performance
against attacks to the ReLU, Maxout, and MMR models. However, for CIFAR-10 we
just compare to the ReLU and Maxout models, as re-creating the MMR-Universal
regularizer for a model as large as ResNet50 exceeded our computational budget
for the research.

###  A.2 Tropical Layer in Tensorflow

We built our models in Tensorflow utilizing the functional API framework. To
build a tropical CNN using this framework, we need to create a Layer class.
Below is the python code used to build the layer:

⬇

1class TropEmbedMaxMin(Layer):

2 ’’’

3 Custom TensorFlow layer implementing Tropical Embedding for max-min
distances.

4 ’’’

5

6 def __init__(self, units=2, initializer_w=initializers.random_normal,
lam=0.0, axis_for_reduction=2, **kwargs):

7 ’’’

8 Initializes the TropEmbedMaxMin layer.

9

10 Parameters

11 \----------

12 units : int, optional

13 Number of output units (default is 2).

14 initializer_w : initializer function, optional

15 Weight initializer function (default is random_normal).

16 lam : float, optional

17 Regularization parameter (default is 0.0).

18 axis_for_reduction : int, optional

19 Axis for reduction in distance calculation (default is 2).

20 **kwargs : dict

21 Additional keyword arguments.

22 ’’’

23 super(TropEmbedMaxMin, self).__init__(**kwargs)

24 self.units = units

25 self.initializer_w = initializer_w

26 self.lam = lam

27 self.axis_for_reduction = axis_for_reduction

28

29 def build(self, input_shape):

30 input_dim = input_shape[-1] # Extract the last dimension from input_shape

31 self.w = self.add_weight(name=’tropical_fw’,

32 shape=(self.units, input_dim),

33 initializer=self.initializer_w,

34 regularizer=TropRegIncreaseDistance(lam=self.lam),

35 trainable=True)

36 self.bias = self.add_weight(name=’bias’,

37 shape=(self.units,),

38 initializer="zeros",

39 trainable=True)

40 super(TropEmbedMaxMin, self).build(input_shape)

41

42 def call(self, x):

43 ’’’

44 Performs the forward pass of the TropEmbedMaxMin layer.

45

46 Parameters

47 \----------

48 x : tensorflow tensor object

49 Input tensor.

50

51 Returns

52 \-------

53 trop_distance : tensorflow tensor object

54 Output tensor after applying Tropical Embedding for max-min distances.

55 ’’’

56 x_reshaped = reshape(x, [-1, 1, self.w.shape[-1]]) # Reshape input data

57 x_for_broadcast = repeat_elements(x_reshaped, self.units, 1) # Repeat input
for broadcasting

58 result_addition = x_for_broadcast + self.w # Calculate addition of input
and weights

59 trop_distance = reduce_max(result_addition, axis=(self.axis_for_reduction))
- reduce_min(result_addition, axis=(self.axis_for_reduction)) + self.bias #
Calculate tropical distances with bias

60 return trop_distance

Listing 1: Tropical Layer Class in Tensorflow

###  A.3 Attack Hyperparameters

All attacks used, except for CW, require a norm constraint
hyperparameter333The specified values of all $\epsilon$ values outlined here
are chosen considering that the images in these datasets are normalized such
that pixel values lie within the range [0,1]., $\epsilon$. The CW algorithm
attempts to find adversarial examples while minimizing the $\ell_{2}$
perturbation, but does not constrain the perturbation in the $\ell_{2}$-ball,
so we do not define an $\epsilon$ for it. Given this, for all our
$\ell_{\infty}$, we use common $\epsilon^{\prime}s$ given the dataset. For
MNIST, we use $\epsilon_{\infty}=0.1$, for SVHN and CIFAR-10 we use
$\epsilon_{\infty}=\frac{4}{255}$. For all datasets we compute the $\ell_{2}$
constraint ($\epsilon_{2}$) as $\epsilon_{2}=\sqrt{\epsilon_{\infty}^{2}*n}$
where $n$ is the number of input elements/pixels. For MNIST,
$\epsilon_{2}=2.8$, and for SVHN and CIFAR-10, $\epsilon_{2}=0.87$. For all
datasets we compute the $\ell_{1}$ constraint ($\epsilon_{1}$) as
$\epsilon_{1}=\epsilon_{2}*2$. For MNIST, $\epsilon_{1}=5.6$, and for SVHN and
CIFAR-10, $\epsilon_{1}=1.74$. The $\epsilon_{2}$ and $\epsilon_{1}$
constraints provided were chosen because they achieved similar attack
performance to the $\ell_{\infty}$ attacks.

Beyond the $\epsilon$ constraint choices, we outline the other key
hyperparameters for each attack used in the experiment:

  * •

Sparse $\ell_{1}$ Descent (SLIDE):

    * -

steps = 100

    * -

$\epsilon$ = MNIST: 5.6, SVHN/CIFAR: 1.74

    * -

step size = 0.01

    * -

percentile = 99

  * •

$\ell_{2}$ and $\ell_{\infty}$ Projected Gradient Descent (PGD):

    * -

steps = 100

    * -

$\ell_{2}$ $\epsilon$ = MNIST: 2.8, SVHN/CIFAR: 0.87

    * -

$\ell_{\infty}$ $\epsilon$ = MNIST: 0.1, SVHN/CIFAR: $\frac{4}{255}$

    * -

step size = 0.01

    * -

random start within epsilon ball = True

  * •

Carlini and Wagner (CW):

    * -

abort early = True

    * -

max iterations per binary search step = 1000

    * -

number of binary search steps = 10

    * -

confidence = 0

    * -

initial constant = 10

    * -

learning rate = 0.1

  * •

Simultaneous Perturbation Stochastic Approximation (SPSA)

    * -

$\epsilon$ = MNIST: 0.1, SVHN/CIFAR: $\frac{4}{255}$

    * -

number of iterations = 100

    * -

learning rate = 0.01

    * -

delta = 0.01

    * -

spsa samples = 128

    * -

spsa iters = 1

    * -

early stop loss threshold = 0.0

###  A.4 Model Complexity and Computation Times

We defined our model structure in Appendix Section A.1, including the base
models used as well as each model’s structure connected to the base model. To
get a sense of the size of each model in terms of trainable parameter, Table 6
shows the raw count of trainable parameters as reported using the Tensorflow
”summary()” method.

Table 6: Trainable Parameters | MNIST | SVHN | CIFAR
---|---|---|---
ReLU | 112,074 | 141,898 | 23,666,378
Maxout | 241,424 | 271,248 | 23,795,728
Tropical | 112,074 | 141,898 | 23,666,378
MMR | 112,074 | 141,898 | -

The experiment computation (training models and attacking models) was
completed using high performance computing (HPC) resources. Each model except
for the MMR SVHN model were trained for 100 epochs. In order to get a sense of
the computational burden imposed by adding our tropical layer, we captured
computational times across the runs. Please note that the compute resources
utilized were not optimized and not the exact same across each model. Much of
the resource allocation was done by trial-and-error. That said, we will try to
give the best apples-to-apples comparison below of computation times, given
the models that used the same resources. Table 7 shows the training times in
seconds for the models that did not employ any adversarial or robust training
techniques. Each model was scheduled to run on the HPC cluster with 4 GPU’s
and 10 CPU’s, but the SVHN model trained with 0 GPU’s and 10 CPU’s. Each
column used the same resources.

Table 7: Computation time in seconds. Each column used the same GPU/CPU compute resources. | MNIST | SVHN | CIFAR
---|---|---|---
ReLU | 253 sec | 4,318 sec | 2,445 sec
Maxout | 265 | 4,467 | 2,412
Tropical | 268 | 4,267 | 2,409

Table 8 shows the training time in seconds for the models trained using he
adversarial training method of training on perturbed examples using
$\ell_{\infty}$ PGD. Each model was trained with 8 GPU’s and 30 CPU’s.

Table 8: Computation time in seconds. Each column used the same GPU/CPU compute resources. | MNIST | SVHN | CIFAR
---|---|---|---
ReLU+AT | 5,323 sec | 6,738 sec | 54,855 sec
Maxout+AT | 6,012 | 7,511 | 54,978
Tropical+AT | 5,870 | 7,214 | 54,791

Table 9 shows the training times for the 2 MMR models built. Recall that the
ResNet-50 base model used for the other CIFAR-10 models was infeasible for the
project computational resources we had and thus was not constructed. The
training of both models occurred with 0 GPU’s and 30 CPU’s and had to be done
in batches of 32 examples. The research team struggled to find the correct HPC
configuration to train the model with GPU’s as the MMR model requires high
dimension matrix computations and the memory and batch size configuration
could not be found to be able to run on the GPU’s available to us, thus 30
CPU’s ended up being optimal in terms of training time on strictly CPU
resources.

Table 9: Computation time in seconds. 30 CPU cores were used to train the MMR model. | MNIST | SVHN (only 15 epochs completed) | CIFAR
---|---|---|---
MMR | 97,380 sec | 261,900 sec | -

The tables should show ample evidence that our model, given the same
resources, achieves nearly computational time parity with its ReLU and maxout
counterpart and is notably less expensive than powerful techniques such as
employing the MMR-Universal regularizer. Due to the operations that take place
(max and min) within our tropical layer, one can expect computation time to be
higher if the problem were higher dimension. Particularly, in our case we were
building models to classify 10 classes. Should the class number be higher, or
the layer preceding the logit layer be higher, this might strain the
computational time parity observed in our experiment.

##  Appendix B Decision Boundaries of ReLU Neural Networks

Expanding on the decision boundary toy problem articulated in Example 32, we
can build an analogous visual of the Voronoi cells that define the boundary
for a ReLU activated model of the exact same construction as our tropical
model above, the only difference being we use a normal, affine fully-connected
layer to produce our logits. Because the projection from $\mathbb{R}^{3}$ to
$\mathbb{R}^{2}$ is not applicable in the ReLU model, we must visualize in
$\mathbb{R}^{2}$. Figure 7 shows three “slices” of $\mathbb{R}^{3}$.

Figure 7: Voronoi diagram for MNIST-trained example ReLU model.