text:
# Tropical Geometry and Neural Networks

Algebraic geometry is not a subject that often arises in conversations around data science and machine learning. However, recent work in the field of tropical geometry (a subset of algebraic geometry) suggests that this subject might be able give some insights into the types of functions representable by neural networks (as well as give some upper bounds on the complexity of functions representable by neural nets of fixed width and depth).

As a former academic mathematician and current data scientist, I’m always somewhat surprised (but excited!) when there end up being direct connections between what I studied during my PhD and the work that I’m doing now. Because my research was in the fields of algebraic geometry and commutative algebra (neither of which is especially renowned for its connections to the real world), the opportunities to spot these links are few and far between.

That’s why the paper Tropical Geometry of Deep Neural Networks by Zhang, Naitzat, and Lim caught my eye – in this paper, the authors give an equivalence between the functions that can be learned by deep neural networks with ReLU activation functions (a powerful but somewhat hard-to-interpret class of functions) and a class of mathematical objects known as tropical rational functions, which come from a subfield of algebraic geometry known as tropical geometry. Furthermore, the authors give some indication of how understanding the tropical geometry side of the picture could give insights into the neural networks side. While this subfield isn’t directly related to the math I worked on during my PhD, it is close enough that I was very intrigued by this paper – the most exciting situations in mathematics are those where two ideas from seemingly different areas turn out to be intimately related.

My goal for this blog post is to give enough of an idea of what algebraic and tropical geometry are about that the interested reader would feel comfortable trying to learn more, as well as sketching some of the ideas of the Zhang, Naitzat, and Lim paper.

## Algebraic Geometry

The basic idea of algebraic geometry is one that most people who have taken some math have encountered, even if they didn’t know that it was algebraic geometry at the time – given a polynomial equation (like, say, $y=x^2$), we can graph it as a function:

The main idea of algebraic geometry is that there is a very strong link between the algebraic side (the polynomial equation $y = x^2$) and the geometric side (the curve plotted in the above image), and that understanding one side of this well can give insights into the other side.

Let’s look at two more equations and their plots:

On the left is the curve $y^2 = x^3$, and on the right is the familiar circle $(x-1)^2 + y^2 = 1$, which can be rewritten as $y^2 = -x^2 – 2x$.

Just as an example of the kind of investigation one can do, we could ask the geometric question ‘given a curve, how many times can a straight line intersect it?’. Below are the same graphs with a ‘maximally intersecting’ line drawn as well.

So for the graphs of $y=x^2$ and $y^2 = -x^2 -2x$, the answer to this geometric question is $2$, while for $y^2 = x^3$, the answer is $3$. It turns out that this geometric question has an algebraic answer: it is just the degree of the polynomial (the largest power appearing on a variable). Similarly, the fact that $y=x^2$ and $y^2 = -x^2-2x$ are both ‘smooth’ at the point $(0,0)$, while $y^2=x^3$ has a ‘cusp’ at that point, is related to the lowest degree appearing in the polynomials – for the first two it is 1, while for $y^2=x^3$ it is 2.

Obviously they relationships go much deeper than those discussed above, but this is just meant to give the flavor of the kinds of problems studied in algebraic geometry.

For the interested reader, a great introduction to the basics of algebraic geometry is An Invitation to Algebraic Geometry by Smith et al.

## Tropical Geometry

The basic idea of tropical geometry is to study the same kinds of questions as in standard algebraic geometry, but change what we mean when we talk about ‘polynomial equations’. In the tropical setting, we allow inputs to be from the standard real numbers plus $-infty$ (which should be thought of as shorthand for ‘a number that is less than any other number’). We then define tropical addition (denoted $oplus$) as $a oplus b = max(a,b)$, and tropical multiplication (denoted $odot$) as $a odot b = a+b$. Then a tropical polynomial is just like a standard polynomial, where usual addition and multiplication have been replaced by $oplus$ and $odot$.

For example, the tropical polynomial $1 oplus y^{odot 2} oplus (5odot x^{odot 3})$ can be rewritten in more standard notation as $max(1, 2y, 3x+5)$. The upshot of this is that now all ‘polynomial functions’ appearing in the tropical setting are maximums over collections of linear functions, which are often much more tractable to work with than usual polynomials. The true power of tropical geometry is in situations where information from this ostensibly easier-to-work-with setup can be used to answer questions about the corresponding mathematical objects in the more standard setting of algebraic geometry.

In analogy to plotting the graphs where a polynomial equation holds in the standard setting (as we did above), in the tropical setting we can plot the boundaries where the function changes between the linear terms appearing (i.e. where two of the linear terms are equal). For example, our tropical polynomial $1 oplus y^{odot 2} oplus (5odot x^{odot 3})$ is plotted below:

Note that a tropical polynomial $F$ is piecewise linear. Thus we get a partition of its domain into regions on which $F$ can be written as a single linear function. In the example above, these are the three cells split up by the lines. On the lower left rectangular region, our function equals $1$. On the top region, the function equals $2y$, and on the righthand region the function equals $3x+5$. The number of such regions is denoted by $mathcal{N}(F)$, and Zhang et al. indicate that this can be thought of as a ‘measure of complexity’ for the function $F$ – basically the more regions necessary to describe $F$, the more complicated $F$ is.

We need one more notion from tropical geometry to talk about the paper – in analogy with rational functions ($frac{f(x)}{g(x)}$ where $f$ and $g$ are polynomials) in standard algebraic geometry, we can consider tropical rational functions $f(x) oslash g(x) = f(x)-g(x)$ where $f$ and $g$ are tropical polynomials. These end up being the objects that Zhang et al. show are equivalent to the functions learnable by neural networks with ReLU activation functions (with some additional mild assumptions).

For a general introduction to what tropical geometry is all about, we recommend the article What is…Tropical Geometry by Katz, along with the references therein.

## Tropical Geometry of Deep Neural Networks

Now we can get to the good stuff. Zhang et al. restrict their attention to the following setup for neural networks:

• A neural network is an alternating composition of affine functions (the preactivation functions) and activation functions of the form $max(x,t)$, where ReLU is the special case where $t=0$.
• We can restrict attention to the cases where weight matrices in the activation functions are integer-valued. The idea here is that real-valued weight matrices can be arbitrarily approximated by rational-valued weight matrices, and then clearing denominators gives integer-valued weight matrices.

Then in this setting they prove that functions represented by neural networks are exactly the tropical rational functions! To do this, they proceed roughly as follows:

• First, they start with a function represented by a neural network. The first preactivation function is affine, and the first activation function is just a maximum of the output of the preactivation function and some number. We can explicitly write this as a tropical rational function.
• They then proceed inductively – given that the first $l$ layers of the neural network can be represented by a tropical rational map, they give an explicit description of the $(l+1)$st layer as a tropical rational map in terms of the weights at the $(l+1)$st layer and the tropical polynomials describing the first $l$ layers.
• For the other direction, they start by showing that tropical monomials (i.e. tropical polynomials with a single additive term) have an explicit description as a neural network in their setting, and then show that given such a description, one can derive neural network descriptions for sums and differences of tropical monomials, which then yields such a description for all tropical rational maps.

Finally, they give some applications of tropical algebraic geometry to the understanding of neural networks. The main theorem here is that the number of regions on which the tropical rational function $F$ representing a neural network is linear ($mathcal{N}(F)$) has an explicit upper bound in terms of width and depth of the neural network – in particular, it grows exponentially with the depth and linearly with the width of the neural network. Again, this can be thought of as a description of the complexity available to a neural network of fixed depth and width, with this description coming from tropical geometry!

The authors remark that this is only scratching the surface of the potential of applying tropical geometric methods to the study of neural networks. Hopefully this is the start of a long and fruitful collaboration between the two subjects.

## You might also enjoy

##### Off Grid CTO: Starlink in Action

Exciting news up here at the off grid cabin location, we now have actual real high speed internet! With Starlink service we have a true high speed connection, and it even uses less power than the Viasat installation did.

##### Investing In AI Doesn’t Need To Be A Leap Of Faith: How To Track Your AI ROI

Many enterprise leaders have taken a “Field of Dreams” approach to AI ROI — “If we build it, profits will come.” While it’s one thing to take that approach for smaller pilot projects, it’s another thing when you’re consistently being asked to fund initiatives with seven-figure price tags.

##### Are You Flying Blind in the AI Arms Race?

Few are able to answer basic questions such as “What’s the ROI of our AI investments?” or “What’s the exposure to our AI compliance risks?”

Get the Latest News in Your Inbox

##### ModelOp releases ModelOp Center 3.0, adding significant new capabilities for governing and scaling AI in the enterprise

Leading ModelOps platform now includes solutions for Executive Visibility for AI, modernizing Model Risk Management and AI Orchestration


text:
Patching Array

07/18/2016 Greedy

Question

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:

nums = [1, 3], n = 6

Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4. Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3]. Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6]. So we only need 1 patch.

Example 2:

nums = [1, 5, 10], n = 20

Return 2.

The two patches can be [2, 4].

Example 3:

nums = [1, 2, 2], n = 5

Return 0.

Solution

Result: Accepted Time: 4 ms

Here should be some explanations.

    int minPatches(int* nums, int numsSize, int n)
{
int ret = 0,ptr = 0;
unsigned int range = 0,limit = n;
while(range < limit)
{
if(ptr == numsSize || range + 1 < nums[ptr])
++ret,range = (range << 1) | 1;
else
range += nums[ptr++];
}
return ret;
}
// if you can reach [1,n] ,then you patch n+1 ,you get [1,2n+1].

Complexity Analytics

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

format: plain


text:
# Interpret logistic regression output with multiple categorical & continious variables

I'm trying to analyze some data obtained from a survey asking employers about their difficulty in hiring certain occupations (80 total occupations). But I'm uncertain about the interpretation of my results.

Dependent Variable: 0 = not difficult 1 = difficult.

Independent Variables:

1. occupation group (occ.group 1 to 9 different groups) grouped the occupations to cut down on the total number of options
2. area (0 = urban 1 = rural)
3. hourly wage of the occupation (hr.wage continuous, numeric).

The data is structured as such:

   empnum response    soc     occ.group  area    hr.wage
1  123450        1    1         1          1        70.20
2  543210        0    1         1          0        50.10
3  111111        0    1         1          1        71.10
4  222222        1    2         2          1        60.23
5  333333        1    2         4          0        100.57
6  4444444       0    80        9          1        60.18

Model is as follows:

logit1 <- glm(response~occ.group+area+hr.wage, family=binomial, data=health.sub)

Coefficients:
Estimate Std. Error  z value  Pr(>|z|)
(Intercept)     0.184978   0.466055    0.397   0.69144
occ.group2     -0.243524   0.528233   -0.461   0.64479
occ.group3      0.281285   0.407879    0.690   0.49043
occ.group4     -0.063578   0.510229   -0.125   0.90084
occ.group5     -0.039797   0.403032   -0.099   0.92134
occ.group6      0.419655   0.475109    0.883   0.37708
occ.group7     -0.898869   0.652530   -1.378   0.16835
occ.group8    -15.015216 394.6834     -0.038   0.96965
occ.group9     -0.370350   0.405532   -0.913   0.36111
area1           0.008863   0.129376    0.069   0.94538
hr.wage         0.010475   0.004028    2.600   0.00931   **
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

(Dispersion parameter for binomial family taken to be 1)

Null deviance: 1679.4  on 1259  degrees of freedom
Residual deviance: 1638.5  on 1249  degrees of freedom
AIC: 1660.5

Number of Fisher Scoring iterations: 13

I'm trying to get an idea if my interpretations are correct.

1. Because occ.group2 coeff is negative it would have lower odds of being difficult to hire than occ.group1 (reference group)

odds are exp(-0.2353) = .79
probability = .4414

2. An employer with occupation in occ.group2 and area1 = -0.243524 + 0.008863 = exp(-0.234661) = 0.79 odds of difficult. Would that be compared to to occ.group1 (reference group) in the same area1 or would it be area0. I guess I'm having a hard time interpreting the reference group with two categorical variables.

3. Employer with occupation in occ.group2 and area0? Would I add the coefficient for occ.group2 (-0.243524) and the intercept (-0.243524)? That doesn't seem right, but not sure how to deal with multiple reference groups. What about an employer with occ.group1 and area0?

4. Would the odds of an employer with occupation in group2 and area1 with a 1 dollar increase in hr.wage = -0.243524 + 0.008863 + 0.010475 = exp(-0.224186) = odds of .799 compared to employer with occupation group1 in area1 with 1 dollar hr.wage increase?

Thanks for the explanations and clarification @EdM.

I also had a question about doing deviation/effects coding of the occ.group categorical predictor, because I'm not convinced that comparisons between the occ.group is meaningful due to their major differences. I've read that effects coding makes it possible to compare each group to the overall mean response. But again, I'm not sure I'm fully understanding how to interpret the results.

I've used the contr.sum and contrasts commands in R to apply effects coding to the occ.group variable and end up with this output.

contr.sum(5)
contrasts(health.sub\$occ.group) = contr.sum(5)
Call:
glm(formula = response ~ occ.group + area + hr.wage, family = binomial,
data = health.sub)

Deviance Residuals:
Min       1Q   Median       3Q      Max
-1.7637  -1.2172   0.8009   1.0462   1.1513
Coefficients:
#UPDATED devication/effects coded model based on @EdM 's comment.
#occ.group8 dropped due to limited responses
#Other occ.group's were reorganized to more appropriate categories 1-5
Estimate   Std. Error z value  Pr(>|z|)
(Intercept)   0.546408   0.147042   3.716   0.000202 ***
occ.group1   -0.265066   0.139886  -1.895   0.058109 .
occ.group2   -0.507674   0.110791  -4.582   0.0000046 ***
occ.group3    0.186679   0.154514   1.208   0.226981
occ.group4    0.347765   0.128618   2.704   0.006854 **
area1         0.003353   0.129615   0.026   0.979365
hr.wage       0.002139   0.003228   0.663   0.507424
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
(Dispersion parameter for binomial family taken to be 1)
Null deviance: 1679.4  on 1259  degrees of freedom
Residual deviance: 1635.1  on 1253  degrees of freedom
AIC: 1649.1
Number of Fisher Scoring iterations: 4

/#UPDATED values to reflect @EdM response.

How would I go about interpreting the odds for an employer with occ.group2 and area0 with an hr.wage = 50.00 given the effects coding?

I believe the odds would be calculated as 0.5464 +(-0.5077) + (0.5464 - 0.0034) + (0.0021*50.00)) = exp(0.6937) = odds of 2.001. Which is in comparison to the mean of the mean occ.group logits rather than any specific reference group.

• I don't often use sum contrasts. This page shows how to interpret them in R output. Note that you have a big problem with occ.group8 that you should solve before you go farther; as it stands that group leads to a situation far from having residual errors independent of the variable values, as required for interpreting p values properly, and this is harming your whole model. I suspect a data coding error.
– EdM
Sep 24 '15 at 0:35
• Thanks for the reference @EdM that was useful. If I'm understanding correctly the intercept would be the mean of the mean logits and occ.group5 coefficient would be the intercept minus all the other occ.group coefficients. I think i've updated the effects coding example to the proper interpretation, although I'm not 100% sure the area0 component is handled properly.
– AKP
Sep 25 '15 at 1:08
• You used sum contrasts for occ.group but you kept treatment contrasts for area; wage is expressed as difference from 0. So the intercept in your second model represents the case for the mean of occ.group values, at area0 and wage = 0. Your terms accounting for occ.group2 and wage in calculating odds are correct, but there should be no term for area0 as that is included in the intercept. If you went to sum contrasts for area, you would then find a coefficient reported for area0 but not for area1, as I understand the way the contrasts are handled.
– EdM
Sep 25 '15 at 14:24
• Seems relatively intuitive in hindsight. And, you know, having it plainly spelled out never hurts. I think I'll stick with the deviation/effects coding, but work on better groupings. There also seems to be some strong arguments for adding some interaction terms, so I'll try to wrap my ahead around interpreting those. Thanks again @EdM. And I ran sum contrasts on area and it gives a coefficient for area1 not area0. Which I assume is because the sum contrasts are 1, -1 for a dichotomous var. So to get area0 you'd subtract the area1 coefficient from the intercept.
– AKP
Sep 25 '15 at 23:37

So for your question 2 the reference is occ.group1 and area0, as it is for all comparisons given the way you have labeled the levels of the variables. occ.group1 and area0 as in your question 3 is the reference group with odds calculated from the intercept for a 0 wage, but you need to specify an hourly wage to get the odds for a non-zero wage.
Your interpretation in question 4 seems to be a bit off. If the areas and wages are the same for the two groups then the only difference to consider in the specified comparison is the coefficient for occ.group2 versus the occ.group1 reference.


text:
Next: Exercises Up: Addition of Angular Momentum Previous: Angular Momentum in the

# Two Spin One-Half Particles

Consider a system consisting of two spin one-half particles. Suppose that the system does not possess any orbital angular momentum. Let and be the spin angular momentum operators of the first and second particles, respectively, and let
 (839)

be the total spin angular momentum operator. By analogy with the previous analysis, we conclude that it is possible to simultaneously measure either , , , and , or , , , , and . Let the quantum numbers associated with measurements of , , , , , and be , , , , , and , respectively. In other words, if the spinor is a simultaneous eigenstate of , , , and , then
 (840) (841) (842) (843) (844)

Likewise, if the spinor is a simultaneous eigenstate of , , , and , then
 (845) (846) (847) (848)

Of course, since both particles have spin one-half, , and . Furthermore, by analogy with previous analysis,
 (849)

Now, we saw, in the previous section, that when spin is added to spin one-half then the possible values of the total angular momentum quantum number are . By analogy, when spin one-half is added to spin one-half then the possible values of the total spin quantum number are . In other words, when two spin one-half particles are combined, we either obtain a state with overall spin , or a state with overall spin . To be more exact, there are three possible states (corresponding to , 0, 1), and one possible state (corresponding to ). The three states are generally known as the triplet states, whereas the state is known as the singlet state.

Table 4: Clebsch-Gordon coefficients for adding spin one-half to spin one-half. Only non-zero coefficients are shown.

The Clebsch-Gordon coefficients for adding spin one-half to spin one-half can easily be inferred from Table 2 (with ), and are listed in Table 4. It follows from this table that the three triplet states are:

 (850) (851) (852)

where is shorthand for , etc. Likewise, the singlet state is written:
 (853)

Subsections

Next: Exercises Up: Addition of Angular Momentum Previous: Angular Momentum in the
Richard Fitzpatrick 2010-07-20