NGOC MAI TRAN, RESEARCH STATEMENT My research lies at the

NGOC MAI TRAN, RESEARCH STATEMENT
HTTP://MA.UTEXAS.EDU/USERS/NTRAN
My research lies at the intersection of stochastic geometry, tropical geometry and discrete
optimization. I have written nine papers in total on these topics. In each of the following
sections, I will explain some of my main results, provide their contexts, and propose main
research directions.
1. Linear programming and tropical geometry
Linear programs are optimization problems with linear objective functions and constraints.
They are essential to operations research, engineering and convex optimization. Solutions
to linear programs are often described solely in terms of algorithms. I focus on discovering
more mathematical, structured descriptions of solutions to linear programs.
1.1. Background. In tropical geometry, one does arithmetic over the min-plus or max-plus
semiring (R, ⊕, ), where a ⊕ b = max(a, b) (resp. min(a, b)), a b = a + b. Many linear
programs only involve the min-plus or max-plus operations. Formulated over the tropical
semiring, such programs often turn into a tropical polynomial, allowing elegant mathematical
descriptions of the solution set.
Left image: the shortest path tree of Seattle area for bicycle
travel. The shortest path problem is the staple example of
a linear program with an elegant tropical solution.
Source: http://graphserver.sourceforge.net/gallery.html
The all-pairs shortest path problem is as follows. Given a cost matrix [cij ] ∈ Rn×n
≥0 with
2
cii = 0, for each pair (i, j) ∈ [n] , find the length of shortest paths from i to j. For a fixed
pair (i, j), this is a linear program whose dual is
(D)
maximize b y
subject to yi − yj ≤ cij
for decision variable y ∈ Rn , and b ∈ Rn , bk = 0 for k = i, j, bi = −1 and bj = 1. This
program admits a dynamic programming solution. In fact, it often features in undergraduate
optimization textbooks for this reason. Over the min-plus semiring, the solution has a
beautiful description.
Lemma. [4, §4] Define c∗ = nk=1 c k . Then c∗ij is the length of shortest paths from i to j.
The columns of c∗ are precisely the eigenvectors of c. Furthermore, the tropical eigenspace
of c, denoted P ol(c), is precisely the constraint set of the dual program (D).
1
Ngoc Mai Tran
http://ma.utexas.edu/users/ntran
A tropical polytope that is also an ordinary polytope is called a polytrope. Amongst other
places, they arise as bounded cells in affine Coxeter arrangement, Bruhat-Tit buildings, and
as building blocks of tropical polytopes. All polytropes equal to P ol(c), the constraint set
of (D), for some cost matrix c [6, 16]. This explains the central role of the shortest path
problem to tropical spectral theory.
1.2. Contributions: combinatorial types of polytropes. Over a series of papers [13],
[15], [16], I pioneered the investigation on the combinatorial structure of polytropes. In [13],
Sturmfels and I considered tropical eigenvectors of generic matrices with non-zero tropical
eigenvalue. We defined their combinatorial types, and showed that these are in bijection with
connected functions on [n]. I continued this work in [15], where I completely characterized
collections of shortest paths trees which can occur together in a tropical eigenspace. I
proved that each collection of tree defines a cone, and together they form a fan partition Fn
of Rn(n−1) .
In [16], I used Gr¨obner bases to enumerate polytropes up to combinatorial equivalence.
This is a major advancement in understanding polytropes. Previous purely computational
approaches to classifying polytropes such as that in [6] can only produce results up to dimension 4. I showed that combinatorial types of polytropes precisely correspond to the
Gr¨obner fan GF n of the linear program (D), which refines the fan Fn . While GF n is rather
large, its structure is essentially captured in a much smaller hyperplane arrangement. I gave
an explicit description of this arrangement, and thus successfully classified polytropes in
dimension 5. I am continuing work on higher dimensions using commutative algebra.
Figure 1. Five types of maximal polytropes in projective dimension 3 computed by Joswig and Kutlas using the software polymake. In fact, there are
six such types. In [16] I provided a proof using Gr¨obner bases, and enumerate
analogous objects in projective dimension 4. Image taken from [6]
1.3. Future work: What class of linear programs can tropical geometry solve?
Only a few linear programs have known tropical descriptions. An example is the tropical
determinant, which precisely solves the bipartite matching problem. As another example,
Backerman [3] most recently showed that a theorem concerning Riemann-Roch theory on
tropical curves is equivalent to the strong duality of max-flow and min-cut. Such results hint
towards deep connections between linear programs and other areas of tropical geometry.
Given a linear program whose description only involves min and plus operations, how to
formulate this program as a tropical question? To understand the power of tropical geometry,
it is crucial to answer this question.
2
Ngoc Mai Tran
http://ma.utexas.edu/users/ntran
2. Discrete optimization in neural networks
Neuroscientists have long viewed the brain as a computation machine, capable of encoding
information and decoding under noise. Computation models with neural networks have
strong influence and wide applications in machine learning. In many established discrete
neural codes such as the Hopfield network, coding is a discrete optimization problem. In this
discrete setup, I work to discover how our neurons are connected, and how they collectively
code and decode under noise. I am most interested in groups of neuron exhibiting highly
symmetric patterns of firing, as demonstrated in my published and on-going work below.
2.1. Contribution: robust sub-exponential storage in binary Hopfield networks.
The binary Hopfield network is an auto-associative computational model of neural memory
storage and retrieval. This model is able to store collections of randomly generated patterns
as robust stable-points of the network dynamics. However, known algorithms have produced
networks with linear capacity, and it has been a long standing open problem whether robust
exponential storage was possible.
With Hillar and Koepsell [5], I considered Hopfield networks which store a large number
of symmetric patterns, namely, all cliques of size
one
√ k in a graph on 2k nodes. By having
2k
k
4
neuron for each edge, this creates k ∼ 4 / k linear programs, each has ∼ k variables
with ∼ k 2 constraints.
a)
clique
b) hidden clique
c)
Our Hopfield network in [5] stores
cliques as stable-points of the network dynamic, and thus can be used
to solve the hidden clique problem.
In neuroscience interpretations, the
clique is a memory, and the noisified
clique could be a sensory input which
triggers the memory.
clique
+ noise =
one network update
I utilized the action of the
symmetric group on the neuron labels and successfully reduced
 
12
1
1
the problem to a linear
program
in three variables and three constraints. Thus we explicitly

13 
 0 
 0 
14
constructed
simple
networks
on n neurons with asymptotically optimal tolerance for error,
b)
2
3
 
15  0√
while capable of storing23∼21 n stable-points. This is a vast improvement over linear storage
 1 
 
capabilities of previous 24
and an important step towards the exponential storage
 1 
25networks,
 
 1 
34
 
5
4
conjecture.
35  1 
45
1
2.2. Ongoing work: Decoding the grid cell code. Initial models of neural computations
produce neural codes which have asymptotically zero information rate. By Shannon’s fundamental theorem, there exist discrete codes that allow asymptotically zero error probability
at asymptotically nonzero information rate. Only very recently (2012), two neuroscientists,
Sreenivasan and Fiete, proposed the first error-correcting neural code which is ”good” in
Shannon’s sense [12]. The discrete version of this model amounts to a Chinese Remainder
computation. Most importantly, this model is supported by experimental data.
While the Sreenivsan-Fiete encodes a lot of information, how the brain decodes it remains
a mystery. With Fiete, we are building a binary Hopfield network decoder using a mixture
of machine learning and number theory.
3
Ngoc Mai Tran
http://ma.utexas.edu/users/ntran
2.3. Future work: Learning neural network topology. ‘Mapping the brain’, as we
may call it, is a challenging topic with a vibrant research community. Related problems
include mapping social networks based on emails, messages or phone calls. For message
passing in social networks, one can assume that a compiled email joins an email queue at
the server, and then gets processed and delivered. Thus, using queuing theory, one can infer
the connections of a given person. Inspired by this observation, I propose to learn neural
network topologies using existing neural computation models, such as the Hopfield network.
Assuming that a given group of neurons form a Hopfield network, we know the message
passing algorithm, and thus can infer the connections of each neuron. I am very interested
in testing this approach to real neural data.
3. Stochastic geometry
Stochastic geometry is the study of random geometric structures with a spatial configuration. I have two main intertwined research agenda: stochastic tropical geometry, and
random partitions with machine learning applications.
3.1. Contribution: size-biased permutation of a finite sequence with i.i.d terms.
Particularly interesting families of exchangeable infinite random partitions arise from sizebiased sampling. Here a sequence x = (x1 , x2 , . . .) is sampled proportional to size and
without replacement, resulting in a random reordering of terms. Perman, Pitman and Yor
(PPY) [8] developed theory for size-biased sampling from ranked jumps of a subordinator.
Their work is foundational to combinatorial stochastic processes, Bayesian clustering and
topic modeling.
With Pitman [9], I considered size-biased permutation of a sequence (X1 , . . . , Xn ) where
Xi are i.i.d random variables. We derived exact and asymptotic distribution such size-biased
permutations using two separate methods: subordinators and induced order statistics. By
going back and forth between these two approaches, we tied up loose threads in the literature,
and arrived at more general results with simplified proofs.
3.2. Future work: random partitions in higher dimensions. Combinatorial, generative description of random infinite partitions is an important component to the Pitman-Yor
work. Finding random partitions in higher dimensions with this property remains largely
open. Recently, Roy and Teh [10] proposed the Mondrian process, an iterative process for
generating random planar tessellations with rectangles. Associated with a realization of the
Mondrian tessellation is a Mondrian tree, thus a Mondrian process generates random trees.
Roy and Teh used this process to define a new, competitive way to generate random forests,
with applications to classification in machine learning.
(a) A Mondrian tessellation. From [7]
(b) A stable iteration tessellation. From [11]
4
Ngoc Mai Tran
http://ma.utexas.edu/users/ntran
I noted that the Mondrian tessellation (left) is a special case of the stable iteration tessellation model (right), which attracted much attention in the last 10 years. Together with
Roy and Teh, I am working on using stochastic geometric tools to build Mondrian trees
for clustering with minimal number of nodes. Such results would answer the fundamental
question in machine learning of finding interpretable and powerful classification trees with
strong theoretical foundations.
3.3. Contribution and Ongoing work: Stochastic tropical geometry. This field,
founded by myself and Francois Baccelli, is the marriage of stochastic geometry and tropical
geometry. First-class citizens in stochastic geometry are random geometric objects. Firstclass citizens in tropical geometry are algebraic varieties and polytopes with arithmetic done
in the tropical semiring (R, ⊕, ). Stochastic tropical geometry, therefore, is the study of
functionals and intersections of random tropical varieties, hypersurfaces and polytopes.
Tropical varieties and hypersurfaces are the central objects of study in tropical algebraic
geometry. This is a successful young field bridging combinatorics and algebraic geometry,
with important connections to mirror symmetry, Berkovich spaces, abstract curves and phylogenetics. Typical varieties, hypersurfaces and polytopes have common properties. By
considering these varieties at random, we gain insights into the global structure of tropical
varieties as a collection of sets. This is a prime motivation of stochastic tropical geometry.
Left image: a random tessellation of
the plane by tropical triangles, or in
other words, a realization of a stationary tropical hyperplane process
in R2 . This process the topic of our
investigation in [1].
Bacceli and I initiated this subject in [2], where we considered zeros of random tropical
polynomials. We showed that if a tropical polynomial has coefficients independent and
identically distributed according to some distribution F , then its number of zeros satisfies
a central limit theorem. The scaling is governed by how fast F decays near 0. This can
be seen as a local universality result for zeros of random tropical polynomials, analogous
to the result of Tao and Vu for classical polynomials [14]. Our proof draws on connections
between random partitions, renewal theory and random polytopes. In forthcoming work,
we are looking at stationary tropical hyperplane processes, and zeros of systems of tropical
polynomials.
5
Ngoc Mai Tran
http://ma.utexas.edu/users/ntran
References
[1] F. Baccelli and N. M. Tran. Stationary tropcial hyperplane process. preprint, 2014.
[2] F. Baccelli and N. M. Tran. Zeros of random tropical polynomials, random polytopes and stick-breaking.
arXiv preprint arXiv:1403.7829, 2014.
[3] S. Backman. Riemann-roch theory for graph orientations. arXiv preprint arXiv:1401.3309, 2014.
[4] P Butkoviˇc. Max-linear Systems: Theory and Algorithms. Springer, 2010.
[5] C. Hillar, N. M. Tran, and K. Koepsell. Robust exponential binary pattern storage in hopfield networks.
arXiv preprint arXiv:1206.2081, 2012.
[6] M. Joswig and K. Kulas. Tropical and ordinary convexity combined. Adv. Geom., 10(2):333–352, 2010.
[7] W. Nagel and V. Weiss. Crack stit tessellations: characterization of stationary random tessellations
stable with respect to iteration. Advances in applied probability, pages 859–883, 2005.
[8] M. Perman, J. Pitman, and M. Yor. Size-biased sampling of poisson point processes and excursions.
Probability Theory and Related Fields, 92(1):21–39, 1992.
[9] J. Pitman and N. M. Tran. Size-biased permutation of a finite sequence with independent and identically
distributed terms. To appear in Bernoulli, 2012.
[10] D. M. Roy and Y. W. Teh. The Mondrian process. In NIPS, pages 1377–1384, 2008.
[11] T. Schreiber and C. Th¨
ale. Limit theorems for iteration stable tessellations. The Annals of Probability,
41(3B):2261–2278, 2013.
[12] S. Sreenivasan and I. Fiete. Grid cells generate an analog error-correcting code for singularly precise
neural computation. Nature neuroscience, 14(10):1330–1337, 2011.
[13] B. Sturmfels and N. M. Tran. Combinatorial types of tropical eigenvectors. Bulletin of the London
Mathematical Society, 54:27–36, 2013.
[14] T. Tao and V. Vu. Local universality of zeroes of random polynomials. arXiv preprint arXiv:1307.4357v2,
2013.
[15] N. M. Tran. Polytropes and tropical eigenspaces: Cones of linearity. To Appear in Discrete & Computational Geometry, 2012.
[16] N. M. Tran. Enumerating polytropes. arXiv preprint arXiv:1310.2012, 2013.
6

Download Report