This work tackles the problem of characterizing and understanding the decision boundaries of neural networks with piecewise linear non-linearity activations. We use tropical geometry, a new development in the area of algebraic geometry, to provide a characterization of the decision boundaries of a simple neural network of the form (Affine, ReLU, Affine). Specifically, we show that the decision boundaries are a subset of a tropical hypersurface, which is intimately related to a polytope formed by the convex hull of two zonotopes. The generators of the zonotopes are precise functions of the neural network parameters. We utilize this geometric characterization to shed lights on new perspectives of three tasks. In doing so, we propose a new tropical perspective for the lottery ticket hypothesis, where we see the effect of different initializations on the tropical geometric representation of the decision boundaries. Also, we leverage this characterization as a new set of tropical regularizers, which deal directly with the decision boundaries of a network. We investigate the use of these regularizers in neural network pruning (removing network parameters that do not contribute to the tropical geometric representation of the decision boundaries) and in generating adversarial input attacks (with input perturbations explicitly perturbing the decision boundaries geometry to change the network prediction of the input).
1. Summary of the paper
This paper describes the decision boundaries of a certain class of
neural networks (piecewise linear, non-linear activation functions)
through the lens of tropical geometry.
An earlier result by Zhang et al. (2018) is extended to multi-class
classification problems (technically, only the result for a binary
classification is given in the main text, though).
Similar to this earlier work, the network is shown to be represented as
a tropical rational function. The dual subdivision of this function is
shown to be represented as the convex hull of two zonotopes.
This characterisation is used to explain different phenomena of neural
network training, viz. the 'lottery ticket hypothesis', network
pruning, and adversarial attacks.
2. Summary of the review
This is a highly interesting paper with a very relevant subject. I think
that the perspective of tropical geometry leads to valuable insights. My
background is *not* in tropical geometry, so this paper required several
passes to fully grasp.
I like the novel insights that this paper creates; it is very interesting
to observe known phenomena via tropical geometry. I appreciate the
thorough description of all concepts in this paper. This is to some
extent both 'boon and bane': on the one hand, the paper contains a lot
of information and concepts that need to be understood; on the other
hand, the experiments go *wide* but not *deep*. I suggest to accept the
paper, but to fully endorse it, I would recommend to work on the
following issues:
- Clarity & exposition: In some places, the paper could build intuition
  for non-experts (such as myself) better. This is closely tied to the
  second point.
- Focus: I would maybe pick *one* or *two* of the experimental areas and
  use the remaining space to explain all concepts in more detail, build
  some intuition, and provide a more in-depth setup. Nothing has to
  removed of course; it could still be put in the appendix.
This paper has the potential to be a very strong insightful contribution
to to our community; the authors are to be commended!
3. Detailed comments (clarity)
The paper describes its concepts well and has a high information
density. At times, there is the risk that readers are provided with too
much information in the main text, leaving the necessary intuition
somewhat lacking (unless they are already experts in the subject matter,
in which case a lot of the information can be skipped).
I realise that writing a paper based on methods that are not yet
well-established is no small feat; the authors are to be commended for
that!
Here are some suggestions from someone with a background in differential
topology:
- The introduction and contributions are somewhat repetitive; I would
  suggest merging the 'Contributions.' paragraph with the one preceding
  it
- Even though it *should* be a well-known definition, I would briefly
  explain that the semiring lacks an additive inverse
- Add an explanation of the tropical quotient to Definition 1; I find
  the current phrasing of Definition 3 to be confusing at first glance
- What are *upper faces*? Faces with a specific coordinate fixed?
- A definition of $\pi$ is required. It is my understanding that $\pi$
  is a projection function that 'drops' the last coordinate. Is this
  correct? If so, it should be briefly mentioned on p. 3; else, the
  discussion about the bias-free case on p. 4 cannot be understood.
- Theorem 2 lacks an 'intuitive' formulation; the results are stated in
  a terse mathematical fashion, but it would be helpful (also in light
  of the subsequent discussion) to briefly comment on their *meaning*.
  For example, the first result could be restated as 'the decision
  boundary is a subset of a tropical hypersurface of the polynomial
  $R(x)$'.
  The paragraph 'Theorem 2 bridges the gap...' could maybe also be moved
  to _precede_ the theorem statement.
- The paper refers to $\mathcal{T}(R(x))$ as a super-set, but in my
  understanding, it is a *level set* because Definition 4 uses an
  equality, not an inequality. Am I misunderstanding this? One potential
  misinterpretation of my part could be that superset refers to the fact
  that $\mathcal{B} \subseteq \mathcal{T}(R(x))$; so not a superset
  in the sense of level set analysis, but rather a superset in terms of
  set theory. If this is the case, maybe rephrase the sentence above to
  something like 'boundaries $\mathcal{B}$ through their superset
  $\mathcal{T}(R(x))$ according to the first statement of Theorem 2'.
- What does the colour map in Figure 2 depict? The number of iterations?
  Moreover, I find the polytope though to understand at first glance;
  how is it related to the decision boundaries that are shown in the
  leftmost figure?
- I would suggest to place Figure 1 after stating Theorem 2, since it is
  only referenced later on. Furthermore, the red structures are somewhat
  confusing. According to Theorem 2, the decision boundary is a subset
  of the hypersurface, right? What is the relation of the red structures
  in the convex hull visualisation? The caption states that they are
  normals, but as far as I can tell, this has not been formalised
  anywhere in the paper (it is used later on, though).
- To what extent is the existence of the functions described by Theorem 2
  unique? On p. 5, in Section 4, the paper alludes to *not* using the
  functional form of the network directly because it does not seem to be
  unique. I would like this to be explained a in more details, as
  I found the justification of why the dual subdivision is used quite
  hard to follow.
- In Section 4, how many experiments of the sort were performed? I find
  this a highly instructive view so I would love to see more experiments
  of this sort. Do these claims hold over multiple repetitions and for
  (slightly) larger architectures as well?
  Please also see my comments on Figure 2 above.
- The claim that orientations are preserved should be formalised.
  I immediately understand the intuition behind this concept, but
  if possible, I would like a quantification of this. Might it be
  possible to *measure* changes in orientation with respect to an
  original polytope? If so, it should be possible to provide more
  experiments about these effects and summarise them accordingly.
  Maybe it would also be interesting to investigate whether other
  initialisations can be compared in terms of their orientations?
- In Section 5, I would give a brief link to the appendix for the
  definition of a Minkowski sum.
- Section 5 has (in contrast to the other sections) a lot of details
  containing the experimental setup, but it is missing a description of
  the competitor methods. Adding to what I wrote above, I feel that the
  paper should rather pick *one* area in which experiments are
  performed; the pruning (together with the lottery ticket hypothesis
  explanation, which could be seen as a motivating example) strikes me
  as a good candidate for this.
  I really like this concept of tropical pruning, by the way---it is an
  elegant, principled description!
- The plots in Figure 4 should summarise multiple pruning runs, if
  possible. Why not show a standard deviation as well? Given the
  stochasticity of training, I would think this highly necessary.
- In Section 6, I find the comment on normals generating a superset to
  the decision boundaries hard to understand.
-  The perspective of perturbing the network such that the decision
   boundaries change is really interesting, but I am missing
   a 'take-away message' or a discussion of the insights. Currently,
   this section seems more like a feasibility study: it appears to be
   possible to use the tropical description to find new parameters that
   misclassify a given input. I would propose a discussion of the
   implications of these findings. 
- Concerning future extensions of this work, are there some promising
  results or directions for CNNs or GCNs? If so, it would strengthen
  the conclusion if they were mentioned.
4. Minor style issues
The paper is well-written. I found some minor style issues:
- 'piece-wise' --> 'piecewise' (occur multiple times)
- 'recently demonstrated' --> 'demonstrated'
- 'Thereafter, tropical hypersurfaces divide' --> 'Tropical hypersurfaces divide'
- 'If set $B$ --> 'Letting B'
- I am not sure if I would call adversarial attacks a 'nuisance'; maybe rather a 'problem'?
- Use '\operatorname' or '\mathrm' to typeset the loss in Eq. 5
5. Update after rebuttal
The authors addressed all my important comments; their efforts in rewriting and revising the paper in such a short time period are to be commended. I am very happy to raise my score.