# Merging discrete Morse vector fields:
a case of stubborn geometric parallelization

Douglas Lenseth and Boris Goldfarb  Department of Mathematics and Statistics,
State University of New York, Albany, NY 12222<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We address the basic question in discrete Morse theory of combining discrete
gradient fields that are partially defined on subsets of the given complex.
This is a well-posed question when the discrete gradient field $V$ is
generated using a fixed algorithm which has a local nature. One example is
ProcessLowerStars, a widely used algorithm for computing persistent homology
associated to a grey-scale image in 2D or 3D. While the algorithm for $V$ may
be inherently local, being computed within stars of vertices and so
embarrassingly parallelizable, in practical use it is natural to want to
distribute the computation over patches $P_{i}$, apply the chosen algorithm to
compute the fields $V_{i}$ associated to each patch, and then assemble the
ambient field $V$ from these. Simply merging the fields from the patches, even
when that makes sense, gives a wrong answer. We develop both very general
merging procedures and leaner versions designed for specific, easy to arrange
covering patterns.

###### 1991 Mathematics Subject Classification:

Primary 57Q70, 68Q85; secondary 68U05, 68W10, 68W15

###### Contents

  1. 1 Introduction
  2. 2 Discrete gradient vector fields
  3. 3 The parallelization theorems
  4. 4 Distributed ProcessLowerStars algorithm on a 2D digital image
  5. 5 Generalization to a hierarchical tree-like decomposition
  6. 6 Remarks on applications
  7. 7 Discussion

##  1\. Introduction

Discrete Morse theory [4] is a fairly new and powerful tool, created by Robin
Forman in the 1990s, that has many applications in many fields. One important
application of discrete Morse theory is to streamlining homology calculations.
It has been a very useful tool in topological data analysis, for example in
computing persistent homology.

More specifically, there are algorithms that take both 2D and 3D digital
grayscale images and create discrete Morse functions from their grayscale
function values defined on pixels or voxels. These images give rise to cubical
complexes, where the voxels or pixels are the 0-cells of the complex. One
algorithm, ProcessLowerStars from [12], takes all of the cells in the cubical
complex and puts them either singly in the set of critical cells, $C$, or as a
face-coface (of codimension 1) pair in the discrete vector field, $V$. The set
of critical cells and the discrete vector field are the defining features of a
discrete Morse function, and in turn the discrete Morse complex. In discrete
Morse theory, the discrete vector field determines the maps in the simplified
chain complex of the Morse complex that is created from the critical cells of
the discrete Morse function.

Given a general algorithm $\alpha$ applied to cells in a regular CW complex
$K$ which takes data from $k$-neighborhoods of cells in $K$ and uses that data
to either pair cells together in a list which is to become the discrete vector
field $V$ or place the cells singly in the list of critical cells $C$. The
basic question we address is how do we merge the vector fields in the
elementary situation where $K=U\cup W$, and $U$, $W$ are two subcomplexes to
which $\alpha$ is applied individually to get the discrete vector fields
$V(U)$ and $V(W)$? The goal is to reconstruct the correct vector field $V(K)$
that we would get on all of $K$. It turns out this is not straightforward, in
that $V(K)\neq V(U)\cup V(W)$, and so $\alpha$ is not embarassingly
parallelizable. Being able to do such a computation will involve looking at
where mistakes occur in naively merging the vector fields together as in the
right-hand side of the formula (or, in general, related vector fields) and
“crossing out” those mistakes.

What do we mean by an algorithm being embarassingly parallelizable? One can
take an example with operators in calculus to illustrate the difference
between embarrassingly and stubbornly parallelizable algorithms.
Differentiation is embarassingly parallelizable with respect to addition and
subtraction, i.e. $(f(x)\pm g(x))^{\prime}=f^{\prime}(x)\pm g^{\prime}(x)$.
But it is stubbornly parallelizable with respect to multiplication and
division, i.e. $(f(x)g(x))^{\prime}=f^{\prime}(x)g(x)+f(x)g^{\prime}(x)$,
which is a non-obvious replacement of the straightforward but incorrect
formula $(f(x)g(x))^{\prime}=f^{\prime}(x)g^{\prime}(x)$.

We will present the main parallelization theorem, Theorem 3.1, that will allow
us to do this merging for a general uniformly $k$-local algorithm $\alpha$.
Here $k$-local refers to the nature of the algorithm in that it makes the
classification decision about a cell or a pair by processing only the
information from $k$-neighborhoods of cells in a regular CW complex. This
turns out to be the common type of algorithms in practice. The authors don’t
know any $\alpha$ that builds discrete Morse fields or functions and doesn’t
have this property. We then make this merging process more efficient in
Corollary 3.3 by noting some geometric properties of the vector fields we get,
which leads to a merging that involves applying $\alpha$ on fewer
subcomplexes, i.e. a more efficient distributed computation. We then look at
the situation where the subcomplexes $U$ and $W$ are in antithetic position,
that is satisfying $(U\cap W)[k]=U[k]\cap W[k]$, where $k\geq 1$ and $U[k]$ is
the $k$-neighborhood of the subcomplex $U$. This special relative positioning
of the patches allows to further improve the efficiency by allowing to use
smaller auxiliary patches. This is spelled out in Corollary 3.5.

In the context of $\alpha$ being ProcessLowerStars, it turns out the rigid
structure of the cubical complexes that are formed from the images gives a
very efficient formula, related to but not exactly matching the formula for
the more general case. We will present a formula, in the 2D image case, that
allows us to take lists of discrete vector fields directly from two patches
and merge them together to get the discrete vector field of the union of the
two patches, under the condition that the two patches must have an overlap
that contains at least one $2$-cell. This is done in section 4 and is an
illustration of how the general formulas can be further tweaked to improve the
efficiency of the procedure.

Why do we want to parallelize this ProcessLowerStars algorithm? For one, if
one has a particularly large image with a lot of pixels or voxels, being able
to break the image up and apply the algorithm on each piece will reduce the
time cost compared to applying the algorithm on the whole image. It also may
be that an image may come to you in pieces, á la online machine learning. The
methods of this paper allow to process each piece as it arrives and either
gradually build the discrete field or put the whole field together as a final
quick step.

In an application to the explicit assembly strategy for the ProcessLowerStars
algorithm on a 2D image, we will assume that our computer has a hypothetical
limited constraint (i.e. restricted to processing at most a certain number of
pixels). In this situation we will have to break up the image so that the
number of pixels in each patch is less than the constraint of our computer.
These patches will be rectangular and will allow us to index our patches both
in the horizontal and vertical directions. We will apply the ProcessLowerStars
algorithm to each patch (and all intersections, in both the horizontal and
vertical direction, of adjacent patches). We create an algorithm that merges
the discrete vector field in each of the patches to obtain the discrete vector
field of the whole image, using the formula on two patches. In order to do
this, our algorithm will merge starting in the top left corner of the image
and move along each horizontal strip and their intersections. Once the
discrete vector field of every horizontal strip and their intersections is
found, the algorithm then moves vertically from top down to merge the discrete
vector fields of the horizontal strips two at a time again making use of the
formula that will be provided.

Finally we will look at another specific special geometric situation that
involves simplicial trees in section 5. This is done with two purposes. It is
known that finite products of trees contain coarse images of the most common
structures in geometry of finite asymptotic dimension. A sufficient partition
scheme in a product of trees will therefore provide a generic template to
approach most common regular cellular complexes. On the other hand, we will
find that a tree is an example that distinguishes the advantages of each of
the two main parallelization results of the paper.

We finish with a collection of remarks on applications of the results, the
literature, and directions for future work in sections 6 and 7.

##  2\. Discrete gradient vector fields

All complexes in this paper are regular CW complexes, in the sense that
characteristic maps of all cells are homeomorphisms onto the closures of cells
in the complex. We refer for the general background in discrete Morse theory
on regular CW complexes to [10].

######  Notation 2.1.

Suppose $K$ is a regular complex, and suppose $f$ is a discrete Morse function
on $K$. Then there are well-defined sets of critical cells $C(K,f)$ and the
discrete vector field that can be thought of as a set of pairs of regular
cells $V(K,f)$ or $V(K)$. When we use the notation $(\sigma\leq\tau)$ for a
pair in $V(K)$, we mean $\sigma$ is a codimension 1 face of $\tau$.

######  Definition 2.2.

We introduce the following relation among cells in $K$. Two cells $\sigma_{1}$
and $\sigma_{2}$ are adjacent if the closures of the two cells in $K$ have a
point in common. The star of a cell $\sigma$ is the smallest cellular
subcomplex of $K$ that contains all cells adjacent to $\sigma$. Given a
collection of cells $\mathcal{C}$ of $K$, let the star of $\mathcal{C}$ be the
smallest subcomplex that contains the stars of all of the cells in
$\mathcal{C}$. If $K^{\prime}$ is a subcomplex, we also call its star the
1-neighborhood of $K^{\prime}$ denoted $K^{\prime}[1]$. The star of a star is
the 2-neighborhood, etc. We will use the notation $K^{\prime}[n]$ for the
$n$-neighborhood of $K^{\prime}$. The $k$-border of a subcomplex $L$ of $K$
consists of those cells in $L$ whose $k$-neighborhoods are not contained
entirely in $L$.

We will assume that the lists $C(K,f)$ and $V(K,f)$ are results of applying an
algorithm $\alpha\colon K\mapsto V$ of the following nature.

######  Definition 2.3.

Given a face-coface pair of cells $(\sigma\leq\tau)$, the algorithm decides
whether the pair $(\sigma\leq\tau)$ is placed in the list $V(K)$ based on data
specific to $\alpha$ coming from some $k$-neighborhood $\sigma[k]$, for some
uniformly fixed number $k>0$. The result of the algorithm is a discrete vector
field $V_{\alpha}(K)$ which can be therefore realized as $V(K,f)$ for some
discrete Morse function $f$. We will say $\alpha$ with this property is
uniformly local or, more precisely, uniformly $k$-local.

In fact, in all applications that generate $V(K)$ the authors see in the
literature, it is always done using a uniformly $1$-local algorithm. This
isn’t surprising of course, as traditional smooth vector fields are generated
through differentiation procedures which are inherently local.

######  Example 2.4 (ProcessLowerStars is uniformly local).

An example of such algorithm is ProcessLowerStars which produces $V(K)$
starting with an arbitrary positive bounded function (a.k.a grayscale
function) on cells (pixels or voxels) of a 2D or 3D pixel grid $K$. Since the
algorithm qualifies $(\sigma\leq\tau)$ based on the values of a function on
vertices in $\sigma[1]$, this algorithm is uniformly $k$-local for $k=1$.

To be more specific, to make these images into a regular CW complex, we will
translate them to a cubical complexes by making the pixels or voxels
correspond to 0-cells of the cubical complex, $K$. This gives us a positive
bounded function, call it $g$, on a cubical complex, more specifically, a
cubulated plane or space. To apply the algorithm, it is ideal to have the
values of $g$ on all of the 0-cells be unique. If they are not, one can make
small changes (i.e., a linear ramp) to $g$ to ensure they are unique. Once
there are unique values of $g$, the algorithm inspects all of the cells in the
lower star of a 0-cell, $x$. The lower star of $x$, $L(x)$, contains all cells
$\sigma\in K$ in the cubical complex such that
$g(x)=\max\limits_{y\in\sigma}g(y)$. To give an ordering to higher dimensional
cells, a new function, $G$, is introduced, defined as follows: If $\sigma$
contains the vertices $\\{x,y_{1},\cdots,y_{n}\\}$, then
$G(\sigma)=\\{g(x),g(y_{i_{1}}),\cdots,g(y_{i_{n}})\\}$, where
$g(x)>g(y_{i_{1}})>\cdots>g(y_{i_{n}})$. This will allow us to impose the
lexicographical ordering on $G$ when performing this algorithm.

The algorithm, itself, will then take all of the cells of in $L(x)$ and either
possibly pair a cell, $\tau$ with a codimensional 1 face, $\sigma$ and place
them $(\sigma\leq\tau)$ in $V$ or take a cell, $\sigma$ and place it singly in
$C$ in the following way:

  * •

If $L(x)=\\{x\\}$, then $x\in C$. Otherwise, take the minimal (with respect to
$G$) $1$-cell, $\tau$, and $(x\leq\tau)\in V$. All other $1$-cells are added
to a queue called PQzero, since they have no remaining unpaired faces in
$L(x)$. All cofaces of codmension 1 of $\tau$ in $L(x)$ that have 1 unpaired
face in $L(x)$ are added to a different queue called PQone.

  * •

The algorithm then takes the minimal cell (with respect to $G$) that is in
PQone and either moves it to PQzero, if it has no unpaired faces remaining in
$L(x)$, or if it still has an unpaired face it gets paired with that face and
is put into $V$. Then you look at all cofaces of codimension 1 of both cells
that were just paired and put into $V$. If any of these cofaces have exactly
one unpaired face, they are added to the queue PQone.

  * •

Then, if PQzero is not empty, it takes the minimal cell (with respect to $G$),
call it $\delta$, and places it singly in $C$. Then all cofaces of codimension
1 of $\delta$ are inspected. If any these cofaces have exactly one unpaired
face, it is placed in PQone.

This will keep going until both PQzero and PQone are empty. Note that, in
particular $L(x)=x[1]$, using the notation defined above. The
ProcessLowerStars, in fact, only looks at $\sigma[1]$, where $\sigma$ is a
$0$-cell.

######  Example 2.5 (failure of naive merge).

We present a simple example with $V_{\alpha}(K)\neq V_{\alpha}(U)\cup
V_{\alpha}(W)$, where $\alpha$ is the ProcessLowerStars algorithm from [12]
and $U$ and $W$ are subcomplexes of $K$ such that $K=U\cup W$. Let $K$ be the
following 1-dimensional cubical complex with the function values, $f$, on the
$0$-cells.

1342 Figure 1. 1-D example of a failed merging of discrete vector fields.

First, we apply $\alpha$ to all of $K$. This gives
$V_{\alpha}(K)=\\{\\{3,31\\},\\{4,42\\}\\}$. Next, we will break up $K$ into
the following subcomplexes: $U=\\{1,3,4,31,43\\}$ and $W=\\{2,3,4,43,42\\}$ .
When we apply $\alpha$ to $U$, we get
$V_{\alpha}(U)=\\{\\{3,31\\},\\{4,43\\}\\}$. When we apply $\alpha$ to $W$, we
get $V_{\alpha}(W)=\\{\\{4,42\\}\\}$. Clearly, $V_{\alpha}(K)\neq
V_{\alpha}(U)\cup V_{\alpha}(W)$, so simply merging the lists from the
subcomplexes does not give us the correct discrete vector field for all of
$K$. In this particular instance, we get an extra pairing, the $\\{4,43\\}$
from $U$.

The failure of naive merging is made clearer using the following definition
and explanation. Let $\sigma_{C}[k]$ be the $k$-star of $\sigma$ viewed as a
cell within the subcomplex $C$ of $K$. This is an intrinsic to $C$
construction and so may differ from $\sigma[k]$, which is the same as
$\sigma_{K}[k]$, for some combinations of $\sigma$ and $k$. Since the
algorithm $\alpha$ takes as input the data from $\sigma_{C}[k]$, there are
cases when the discrepancy leads to different constructions of the vector
fields as Example 2.5 shows. This also points to some cases when this
discrepancy does not happen.

######  Proposition 2.6.

Suppose $K$ is a disjoint union of subcomplexes $C_{i}$, for $i$ from some
index set $I$. In other words, a connected subset of $K$ is contained entirely
within one and only one $C_{i}$. Then $V_{\alpha}(K)=\bigcup_{i\in
I}V_{\alpha}(C_{i})$.

###### Proof.

For every pair $(\sigma\leq\tau)$ its inclusion in $V_{\alpha}(C_{i})$ is
decided by $\alpha$ from the data within $\sigma_{C_{i}}[k]$. Since in our
case $\sigma_{C_{i}}[k]=\sigma_{K}[k]$, that decision is precisely the same
within $C_{i}$ as within $K$. ∎

This argument makes it clear that failure of the simple merge is caused by
possible discrepancies between $\sigma_{C}[k]$ and $\sigma_{K}[k]$ for cells
$\sigma$ in the $k$-border of $C$ (see Definition 2.2).

##  3\. The parallelization theorems

Suppose a complex $K$ is assigned a gradient vector field $V$ using an
algorithm $\alpha$. Suppose further that $U$ and $W$ are two subcomplexes of
$K$ that form a covering of $K$. In particular, there are vector fields
$V_{\alpha}(K)$, $V_{\alpha}(U[i])$, and $V_{\alpha}(W[i])$ for various values
of $i$.

######  Theorem 3.1.

If $\alpha$ is a uniformly $k$-local algorithm for some $k\geq 1$, then

$V_{\alpha}(K)=\left(V_{\alpha}(U[k])\cup V_{\alpha}(W[k])\right)\setminus\\\
(V_{\alpha}(U[k])\cup V_{\alpha}(W[k])\setminus V_{\alpha}(U[2k+1]\cap
W[2k+1]).$

In slightly different terms,

$V_{\alpha}(K)=\left(V_{\alpha}(U[k])\cup V_{\alpha}(W[k])\right)\setminus\\\
\left(V_{\alpha}(U[k])\setminus
V_{\alpha}(U[2k+1])\right)\setminus\left(V_{\alpha}(W[k])\setminus
V_{\alpha}(W[2k+1])\right).$

The informal idea is this. It will be elementary to check that $V_{\alpha}(K)$
is contained in $V_{\alpha}(U[k])\cup V_{\alpha}(W[k])$ using that the
algorithm $\alpha$ is uniformly $k$-local. Let’s refer to the difference as
“mistakes” in building $V_{\alpha}(K)$ from the union. We will see that for
the same reason, $V_{\alpha}(U[k])\setminus V_{\alpha}(U[2k+1])$ can be viewed
as all the mistakes made near the border of $U[k]$. This set is interpreted as
pairs of cells in $V_{\alpha}(U[k])$ that are not in $V_{\alpha}(K)$.
Similarly, $V_{\alpha}(W[k])\setminus V_{\alpha}(W[2k+1])$ is the set of
mistakes made near the border of $W[k]$. Since the cells near the borders of
the subcomplexes are far enough away in the adjacency relation chains, they do
not contain common adjacent cells. The local nature of the algorithm, again,
guarantees that no other mistakes are made away from the borders of $U[k]$ and
$W[k]$.

We now give a formal proof.

###### Proof.

If the pair $(\sigma\leq\tau)$ is contained in $V_{\alpha}(K)$, it was placed
in this list according to the algorithm $\alpha$. According to the assumption,
this placement is the outcome of inspection of data relevant to $\alpha$ in
$\sigma[k]$. If $\sigma$ and $\tau$ are cells of $U$ then $\sigma[k]$ is
contained in $U[k]$. Since $\alpha$ applied to $U[k]$ would use the exact same
data as $\sigma[k]=\sigma_{U[k]}[k]$, this proves that $(\sigma\leq\tau)$ is
in $V_{\alpha}(U[k])$. Repeating the argument for $W$ in place of $U$, this
gives the inclusion $V_{\alpha}(K)\subset V_{\alpha}(U[k])\cup
V_{\alpha}(W[k])$.

We now examine $(\sigma\leq\tau)$ in the difference

$M=V_{\alpha}(U[k])\cup V_{\alpha}(W[k])\setminus V_{\alpha}(K).$

Observe that whenever the cell $\sigma$ is outside of $W[k]$, it is contained
in $U$. This makes $\sigma_{K}[k]=\sigma_{U[k]}[k]$, so the outcome of the
decision $\alpha$ makes on inclusion of $(\sigma\leq\tau)$ in respectively
$V_{\alpha}(K)$ and $V_{\alpha}(U[k])$ is the same. This shows that such
$(\sigma\leq\tau)$ is disqualified from $M$ as it is excluded as part of
$V_{\alpha}(K)$. Our conclusion is that whenever $(\sigma\leq\tau)$ is in $M$,
$\sigma$ must be in $W[k]$. A symmetric argument proves that it also must also
be in $U[k]$.

The last paragraph proved that our pair of cells $\sigma$, $\tau$ is contained
in $U[k+1]\cap W[k+1]$. Therefore $\alpha$ uses the same data for placing
$(\sigma\leq\tau)$ in either $V_{\alpha}(U[2k+1]\cap W[2k+1])$ or
$V_{\alpha}(K)$. This allows us to rewrite

$M=V_{\alpha}(U[k])\cup V_{\alpha}(W[k])\setminus V_{\alpha}(U[2k+1]\cap
W[2k+1]).$

This gives the first formula.

Let $M_{U}=V_{\alpha}(U[k])\setminus V_{\alpha}(K)$ and
$M_{W}=V_{\alpha}(W[k])\setminus V_{\alpha}(K)$, so that $M=M_{U}\cup M_{W}$.
The same argument as above shows that

$M_{U}=V_{\alpha}(U[k])\setminus V_{\alpha}(U[2k+1]),$

and similarly

$M_{W}=V_{\alpha}(W[k])\setminus V_{\alpha}(W[2k+1]).$

Now

$V_{\alpha}(K)=V_{\alpha}(U[k])\cup V_{\alpha}(W[k])\setminus\left(M_{U}\cup
M_{W}\right)$

gives the second formula. ∎

######  Remark 3.2.

Our interest in this theorem is that it allows to express the global list
$V_{\alpha}(K)$ in terms of generally smaller partial lists
$V_{\alpha}(U[k])$, $V_{\alpha}(W[k])$, $V_{\alpha}(U[2k+1])$, and
$V_{\alpha}(W[2k+1])$.

The computation of these smaller lists can be further simplified by the
observation that the difference between $V_{\alpha}(U[k])$ and
$V_{\alpha}(U[2k+1])$ is contained in $V_{\alpha}(U[2k+1]\cap W[2k+1])$.

######  Corollary 3.3.

If $\alpha$ is a uniformly $k$-local algorithm for some $k\geq 1$, then

$V_{\alpha}(K)=\left(V_{\alpha}(U[k])\cup V_{\alpha}(W[k])\right)\setminus\\\
\left(V_{\alpha}(U[k]\cap W[k])\right)\setminus\left(V_{\alpha}(U[2k+1]\cap
W[2k+1])\right).$

###### Proof.

The formula from Theorem 3.1 is rewritten in terms of the intersection
$U[2k+1]\cap W[2k+1]$. Notice that the restriction to $V_{\alpha}(U[k]\cap
W[k])$ is justified because the $k$-borders of $U$ and $W$ and thus also $M$
are contained in $U[k]\cap W[k]$. ∎

We next implement the formula in this simple case of a two-set covering.

Algorithm 1 Two-set parallelization from Corollary 3.3

Inputs:

  * •

$k\geq 1$

  * •

$\alpha$ uniformly $k$-local algorithm

  * •

$K$ regular CW complex

  * •

$D$ data attached to cells in $K$, specific for use in $\alpha$

  * •

$U(1)$, $U(2)$ a covering of $K$ by subcomplexes given as subsets of $K$

Outputs:

  * •

$V=V_{\alpha}(K,D)$ discrete vector field

  * •

$C=C_{\alpha}(K,D)$ critical cells

for $i$ = $1$, $2$ do

  * •

build $U(i)[k]$

  * •

build $U(i)[2k+1]$

  * •

build $D|U(i)[k]$

  * •

evaluate $\alpha$: $U(i[k])$, $D|U(i)[k]\to A(i,k)$

#  preprocessing step to obtain discrete vector fields in enlargements of
patches

end for

build the union $V(1,2)=A(1,k)\cup A(2,k)$

build the intersection $U(1,2,k)=U(1)[k]\cap U(2)[k]$

build the intersection $U(1,2,2k+1)=U(1)[2k+1]\cap U(2)[2k+1]$

build $D|U(1,2,k)$

build $D|U(1,2,2k+1)$

evaluate $\alpha$: $U(1,2,k)$, $D|U(1,2,k)\to A(1,2,k)$

evaluate $\alpha$: $U(1,2,2k+1)$, $D|U(1,2,2k+1)\to A(1,2,2k+1)$

build the difference $D=A(1,2,k)\setminus A(1,2,2k+1)$

save the difference $V=V(1,2)\setminus D$

build $N$ as all cells employed in $V$

save the difference $C=K\setminus N$

There is a special geometric situation with a more direct identification of
intersections of enlargements.

######  Definition 3.4.

Two subcomplexes $U$ and $W$ of $K$ are said to be in antithetic position if
$(U\cap W)[n]=U[n]\cap W[n]$ for all $n\geq 0$.

We can now state the following consequence of Corollary 3.3.

######  Corollary 3.5.

Suppose $\alpha$ is an algorithm that is uniformly $k$-local for some $k\geq
1$ and suppose $U$, $W$ is an antithetic pair, then

$V_{\alpha}(K)=\left(V_{\alpha}U[k]\cup
V_{\alpha}W[k]\right)\setminus\large(V_{\alpha}(U\cap W)[k]\setminus
V_{\alpha}(U\cap W)[2k+1]\large).$

###### Proof.

The subcomplexes in Corollary 3.3 now have a description based entirely on the
enlargements of covering complexes and their intersections. ∎

######  Remark 3.6.

In general, building $S[n]$ in $K$ for a subcomplex $S$ and a number $n\geq 1$
requires building $x[n]$ for all $x$ in $S$ and taking the union. So the time
complexity of this operation is proportional to the size of $S$. Therefore,
depending on the geometry of $K$ and the choices of $U$ and $W$ the sizes of
the lists the computer needs to work though while building the enlargements
can be greatly reduced by working with the intersection $U\cap W$ and one
single enlarging procedure. This is particularly true when the size of the
intersection $U\cap W$ is significantly smaller than the sizes of $U$ and $W$.
In the case of simplicial trees which we address later in section 5, the size
of $U\cap W$ can be arranged to be an order of magnitude smaller than either
$U$ or $W$ in the Euclidean case and that order can be made arbitrarily
smaller in the case of a tree, depending on the valence of the tree.

In the rest of the section we illustrate in the specific context of the
algorithm ProcessLowerStars [12] that the general theorems can be improved on
in situations with specific $\alpha$ and specific geometry.

Suppose $K$ is a cubulated 2D rectangle $I\times J$ and $I=[a,d]$ for $d-a\geq
4$. Suppose $b$ and $c$ are integers nested in $a<b<c<d$. Then we have a
decomposition of $K$ as $U\cup W$ with $U=[a,c]\times J$ and $W=[b,d]\times
J$.

######  Theorem 3.7.

Applying ProcessLowerStars as $\alpha$ to the two sets $U$ and $W$ as above,
allows some savings in size of processed lists by using a more efficient
formula

$V_{\alpha}(K)=\left(V_{\alpha}(U)\cup V_{\alpha}(W)\right)\setminus
V_{\alpha}(U\cap W)\setminus V_{\alpha}(U\cap W)[1]).$

Notice that this theorem does not follow from any of the general theorems
before because no enlargement of the patches is required for the containment
$V_{\alpha}(K)\subset V_{\alpha}(U)\cup V_{\alpha}(W)$.

###### Proof.

The proof is based on a case-by-case analysis of ProcessLowerStars applied to
stars of vertices near $[b,c]\times J$. As before, we are merging two lists
$V_{\alpha}(U)$ and $V_{\alpha}(W)$. We know that in each complex there are
pairs that involve the vertices in $b\times J$ that may be included in non-
critical pairs in error. In a complementary fashion, the same can be said
about the critical cells in $C_{\alpha}(U)$ and $C_{\alpha}(W)$. We know the
errors can happen in this specific case of $\alpha$ because of a 2D
counterexample similar to Example 2.5. In much the same way the errors happen
at this boundary because that is where incomplete information about their
stars in $K$ is used within $U$ and $W$. Let’s call the pairs included in
error “mistakes”. We try to identify the mistakes in the merged list
$V_{\alpha}(U)\cup V_{\alpha}(W)$. Are they guaranteed to be inside
$V_{\alpha}(U\cap W)$? This turns out to be true in this case but is not
expected for general uniformly local $\alpha$ or more general geometric
decompositions. Next, suppose a pair in $V_{\alpha}(U)\cup V_{\alpha}(W)$ is a
mistake, then we know that it is not in $V_{\alpha}((U\cap W)[1])$ because now
both cells are in a star entirely contained in $V_{\alpha}((U\cap W)[1])$.
This guarantees that the difference $V_{\alpha}(U\cap W)\setminus
V_{\alpha}((U\cap W)[1])$ consists precisely of the mistakes in
$V_{\alpha}(U)\cup V_{\alpha}(W)$ and completes the proof. ∎

##  4\. Distributed ProcessLowerStars algorithm on a 2D digital image

We apply Theorem 3.7 to parallelize an algorithm of type $\alpha$ on grayscale
2D images, in particular the algorithm ProcessLowerStars from [12].

These digital images are modeled by cubical complexes with a grid-like
structure, which makes it a little easier to work with than other cubical
complexes, as we can index our patches with horizontal and vertical
components, which will be outlined more clearly in a little bit. Our formula
for merging the vector field together only makes use of two patches. In some
cases, in particular, with a picture with many pixels and a computer program
having a constraint on the number of pixels it can process with the algorithm,
it is very likely that one would end up with more than two patches. The grid-
like structure that these cubical complexes possess will allow us to apply our
formula to two pieces at a time. First, the image will be split up into
patches, which will partition the cubical complex. How many patches we end up
with will be determined by the number of pixels in the image and the
constraint we have on the number of pixels our computer program can process.
After taking the star of each of the patches in both the vertical and
horizontal directions separately, we will be left with new patches where there
will be overlap, both vertically and horizontally, between adjacent patches.
This will allow us to apply our formula.

After the partitioning into patches and taking the stars in both directions of
all the patches, we apply the ProcessLowerStars algorithm to each patch and
all of the overlaps of the adjacent patches, including the overlaps of the
overlaps. The algorithm will give the discrete vector field in each of the
patches and all of the overlaps of adjacent patches. We then start applying
our formula, starting in upper left hand side of the our complex, with the
first two starred patches. This will give the discrete vector field of the
union of these two starred patches. We then proceed by applying our formula to
this new bigger patch with the adjacent starred patch to its right. We
continue until we reach the end of this horizontal strip. We then move down
vertically to the next row of starred patches and go through the same
procedure. We do this for every horizontal strip of starred patches and obtain
the discrete vector field for each horizontal strip.

We then move to the overlaps of the horizontal strips and use the same
procedure as the horizontal strips themselves, starting from the left hand
side, applying our formula as we move to the right end of the strip. We will
eventually end up with the discrete vector field of the overlaps of the
horizontal strips. We will need the discrete vector field of the overlaps of
the horizontal strips in the next part of our algorithm when we start applying
our formula vertically

We now have the discrete vector field of all of the horizontal strips and
their overlaps, so we can now proceed applying our formula in the vertical
direction, starting with the top most horizontal strip and applying our
formula with the strip directly below it, making use of the discrete vector
field of the overlaps that we computed in the previous steps. We continue
downward until we have the discrete vector field of one big patch and the
horizontal strip below it, along with the discrete vector field of their
overlap. We apply our formula to these last two patches and end up with the
discrete vector field of the whole image.

We make this precise with a pseudo-code for the distributed ProcessLowerStars
algorithm. We assume that the constraint of our computer program in applying
the ProcessLowerStars algorithm on a digital image is $N$ pixels. Assume that
a digital image has $D$ pixels where $D>N$. We break the image up into $n$
disjoint patches such that $n>{D}/{N}$, where patch $P_{i,j}^{\\#}$ is a
subcomplex and corresponds to the patch in the $ith$ column and $jth$ row for
all $i=1,\cdots,m$ and $j=1,\cdots,\ell$ such that $m\cdot\ell=n$.

Let $P_{i,j}^{\\#}[a,b]$ be the subcomplex that is the $a$-neighborhood of
$P_{i,j}^{\\#}$ in the horizontal direction together with the $b$-neighborhood
of $P_{i,j}^{\\#}$ in the vertical direction. We take our disjoint
decomposition $P_{i,j}^{\\#}$ and enlarge each patch by $1$-neighborhood in
each direction and and call it $P_{i,j}$. This gives us
$P_{i,j}=P_{i,j}^{\\#}[1,1]$ where each patch now overlap and the overlaps
contain at least one 2-cell. Let

  1. (1)

$P_{i,j}^{*}=\displaystyle\bigcup_{k=1}^{i}P_{k,j}$ (the union of patches
moving across a horizontal strip)

  2. (2)

$(P_{i,j}\cap P_{i,j+1})^{*}=\displaystyle\bigcup_{k=1}^{i}(P_{k,j}\cap
P_{k,j+1})$ (the union of patches moving horizontally across the intersection
of patches that are vertically adjacent to each other, i.e. moving
horizontally along the intersection of strips)

  3. (3)

$(P_{i,j}[0,1]\cap
P_{i,j+1}[0,1])^{*}=\displaystyle\bigcup_{k=1}^{i}(P_{k,j}[0,1]\cap
P_{k,j+1}[0,1])$ (the union of patches moving horizontally across the
intersection of $1$-neighborhoods in the vertical direction of the patches
that are vertically adjacent to each other)

Figure 2. An illustration of the planar grid-like decomposition.

Figure 2 is used to illustrate this notation. The figure is intended to show a
part of the decomposition of the 2D plane centered on the middle patch denoted
$P_{i,j}$. The orange, green, and blue overlapping rows are the unions of such
patches across the values of the horizontal parameter $i$. One useful
observation is that there are only double overlaps of the rows so that there
is always at least $2\delta$ clearance between non-adjacent rows such as the
orange and the blue, for a fixed value of $\delta$. This guarantees that
$\delta$-enlargements of this covering of the plane by rows have the same
nerve as the rows themselves. The nerve is isomorphic to a triangulation of
the real line. The figure also shows the set $P_{i,j}^{*}$, which is shaded
red, and the union of intersections of patches $(P_{i,j}\cap P_{i,j+1})^{*}$.
It is clear that the finer covering of the plane by individual patches has the
same property as above: its $\delta$-enlargement has the same nerve as the
covering itself.

Algorithm 2 Distributed ProcessLowerStars on a 2D Digital Image

Inputs:

  * •

$D$ digital image pixels

  * •

$g$ grayscale values on pixels

Outputs:

  * •

$C$ critical cells

  * •

$V$ discrete vector field

Constraint:

  * •

Memory$=N$ Pixels

for all $i$ and $j$ do

Apply ProcessLowerStars algorithm to each of the following to obtain:

  * •

$P_{i,j}\rightarrow V_{i,j}$

  * •

$P_{i,j}\cap P_{i+1,j}\rightarrow V_{i,j}^{i+1}$

  * •

$P_{i,j}\cap P_{i,j+1}\rightarrow V_{i,j}^{j+1}$

  * •

$(P_{i,j}\cap P_{i,j+1})\cap(P_{i+1,j}\cap P_{i+1,j+1})\rightarrow
V_{i,j}^{\cap}$

  * •

$P_{i,j}^{*}[1,0]\cap P_{i+1,j}[1,0]\rightarrow V_{i,j}^{i+1}[1,0]$

  * •

$(P_{i,j}\cap P_{i,j+1})^{*}[1,0]\cap(P_{i+1,j}\cap
P_{i+1,j+1})[1,0]\rightarrow V_{i,j}^{\cap}[1,0]$

  * •

$P_{i,j}[0,1]\cap P_{i,j+1}[0,1]\rightarrow V_{i,j}^{j+1}[0,1]$

  * •

$(P_{i,j}[0,1]\cap P_{i,j+1}[0,1])\cap(P_{i+1,j}[0,1]\cap
P_{i+1,j+1}[0,1])\rightarrow V_{i,j}^{\cap}[0,1]$

  * •

$(P_{i,j}[0,1]\cap P_{i,j+1}[0,1])^{*}[1,0]\cap(P_{i+1,j}[0,1]\cap
P_{i+1,j+1}[0,1])[1,0]\rightarrow V_{i,j}^{\cap}[1,1]$

#  Preprocessing Step to obtain discrete vector field in all patches and their
overlaps

end for

for $j=1,\cdots,\ell$ do

for $i=1,\cdots,m-1$ do

Update: $V_{i+1,j}^{{}^{\prime}}=(V_{i,j}^{{}^{\prime}}\cup
V_{i+1,j})\setminus(V_{i,j}^{i+1}\setminus V_{i,j}^{i+1}[1,0])$#  Moving
horizontally along strips

end for

end for

for $j=1,\cdots,\ell$ do

for $i=1,\cdots,m-1$ do

Update: $(V_{i+1,j}^{j+1})^{{}^{\prime}}=((V_{i,j}^{j+1})^{{}^{\prime}}\cup
V_{i+1,j}^{j+1})\setminus(V_{i,j}^{\cap}\setminus V_{i,j}^{\cap}[1,0])$#
COMMENTMoving horizontally along intersection of strips

end for

end for

for $j=1,\cdots,\ell$ do

for $i=1,\cdots,m-1$ do

Update:
$(V_{i+1,j}^{j+1}[0,1])^{{}^{\prime}}=((V_{i,j}^{j+1}[0,1])^{{}^{\prime}}\cup
V_{i+1,j}^{j+1}[0,1])\setminus(V_{i,j}^{\cap}[1,0]\setminus
V_{i,j}^{\cap}[1,1])$# COMMENTMoving horizontally along intersection of strips
enlarged by 1 vertically

end for

end for

for $j=1,\cdots,\ell-1$ do

Update: $V_{j+1}^{{}^{\prime}}=(V_{m,j}^{{}^{\prime}}\cup
V_{m,j+1}^{{}^{\prime}})\setminus((V_{m,j}^{j+1})^{{}^{\prime}}\setminus(V_{m,j}^{j+1}[0,1])^{{}^{\prime}})$#
COMMENTMoving vertically down strips

end for

##  5\. Generalization to a hierarchical tree-like decomposition

Our main motivation for this work has been parallelization of the specific
algorithm ProcessLowerStars on 2D images that we have done in sections 3 and
4. This algorithm has been proven to work in cubical cellular complexes based
on standard cubical grids in 2D and 3D [12]. However, our theorems in section
3 have only general local constraints on the type of the algorithm and on the
geometry of the regular cellular complex. In this section we want to leverage
some geometric material from [5] and [1] to construct required antithetic
coverings for grids in $n$D for all $n$ and, more generally, any subcomplex of
a product of finite locally finite trees.

It is known from a result of Dranishnikov [3, 8] that all metric spaces which
satisfy a very weak and natural geometric condition called finite asymptotic
dimension (FAD) can be coarsely embedded in a finite product of locally finite
trees with uniform distortion. This allows us to give a useful antithetic
covering of any cellular complex which can be given an FAD metric with a
universal bound on the size of all cells.

As we observed before in Remark 3.6, the importance of the case of a tree or a
product of trees is also as an illustration of how crucial the improvements
can be in passage from using the most general Theorem 3.1 to using Corollary
3.5.

We saw in the previous section a worked-out example of use of antithetic
decompositions in the case of a cubical grid in 2D. Just as in that example,
it is most natural to decompose a multi-parameter geometry according to
projections to subsets in one chosen parameter. There should result an
inductively defined decomposition of the entire cubical complex. The general
kind of parameter for our purposes is tree-based, with partial order,
generalizing from the totally ordered real line.

A simplicial tree is a simplicial complex that is connected and has no cycles.
Recall also that a nerve of a collection of subsets of a given set is the
simplicial complex with vertices which are the subsets and simplices
corresponding to non-empty intersections of families of subsets.

######  Definition 5.1.

Suppose $\mathcal{U}$ is covering of a metric space. We will denote by
$\mathcal{U}[k]$ the covering by $k$-enlargements of members of $\mathcal{U}$
for a number $k\geq 0$. We will say that a covering $\mathcal{U}$ is a tree-
like decomposition with margin $k$ if $\mathcal{U}[k]$ is a simplicial tree.
Suppose each of the covering sets with the subspace metric also has a tree-
like decomposition with margin $k$. Then we say that the resulting covering by
smaller sets is a hierarchical tree-like decomposition with margin $k$ and
depth 2. Inductively, for a natural number $D$ one defines a hierarchical
tree-like decomposition with margin $k$ and depth $D$. We will refer to the
sets that appear in such hierarchical decomposition and are not unions of
other sets as primary sets.

The most useful hierarchical tree-like decomposition of depth $D$ can be
obtained for any subset of the product of $D$ simplicial trees. The simplest
case of this type of decomposition is when the trees are obtained as
triangulations of the real line, which generalizes 2D decompositions as in
Algorithm 2 to higher dimensions.

######  Definition 5.2.

Let $T$ be a simplicial tree where each edge is given length 1 with the global
metric induced as a path metric. We fix a vertex $v_{0}$. Given another vertex
$v$ in $T$, we define the “jet” subset $\operatorname{\mathit{J}}(v)=\\{t\in
T|v\in[v_{0},t)\\}$. Let $B(v,r)$ stand for the open metric ball of radius $r$
centered at $v$ and $S(v,r)$ stand for its boundary sphere. We also define the
subsets $\operatorname{\mathit{J}}(v,l)=\operatorname{\mathit{J}}(v)\cap
B(v,l)$ for a positive number $l$, and the differences
$\operatorname{\mathit{J}}(v;l_{1},l_{2})=\operatorname{\mathit{J}}(v,l_{2})\setminus
B(v,l_{1})\setminus S(v,l_{1})$, for $l_{2}>l_{1}>0$.

Given a number $r$ greater than 1, consider the collection of open subsets of
$T$ consisting of the ball $B(v_{0},2r)$ and the differences
$\operatorname{\mathit{J}}(v;r-1,3r)$ where the vertices $v$ vary over
$S(v_{0},(2n-1)r)$ for arbitrary natural numbers $n$. It is easy to see the
following properties.

  1. (1)

This collection of subsets $\mathcal{V}$ is a covering of $T$. Its nerve is
itself in general a forest of trees where the vertices can be indexed by
$v_{0}$ and the vertices $v\in S(v_{0},(2n-1)r)$. The edges are the pairs
$(v,v^{\prime})$ where $v^{\prime}\in\operatorname{\mathit{J}}(v,2(n+1)r)$.

  2. (2)

The diameter of each set in the covering is bounded by $6r$.

  3. (3)

The covering has a margin at least $r$, in the sense that the $r$-enlargement
is again a tree isomorphic to the one in (1).

Clearly, intersecting any subset $X$ of $T$ with the produced covering gives a
covering of $X$ with exactly the same three properties except possibly a
forest of trees instead of a single tree. This gives a hierarchical tree-like
decomposition of $X$ with margin $r$ and depth $1$.

Figure 3 is used to illustrate this notation. In this figure, $v_{0}$ is the
root of the tree. Notice that the vertices labeled $a_{1}$, $a_{2}$, $a_{3}$
are all at distance 3 from $v_{0}$. The blue, the orange, and the red subsets
can be described as the jet subsets $J(a_{i},1,4)$ for $1\leq i\leq 3$. They
overlap with the green subset which itself can be described as the jet subset
$J(b_{1},1,4)$. Notice that the bi-colored edges represent the overlaps
between the different colored subsets. This should illustrate the pattern of
jet generated covering sets and their overlaps in the whole tree. One more
feature that can be seen in this figure is that with this particular set of
choices of the vertices and the bounds $l_{1}$, $l_{2}$ there are only double
overlaps. There are no overlaps between jet subsets of higher multiplicities.
In other words, the nerve of such covering is 1-dimensional. Now it can be
easily seen in the picture that the cellular enlargement of all subsets by 1
unit still has a 1-dimensional nerve. The corresponding enlargements are
simply the jet subsets $J(a_{i},0,5)$, for $1\leq i\leq 3$, and
$J(b_{1},0,5)$. This illustrates how this procedure with the specific choices
we make produces a family of patches with margin 1.

Figure 3. An illustration of jet subsets
$\operatorname{\mathit{J}}(v;l_{1},l_{2})$ and margins in a tree.

For a product $\Pi$ of $D$ trees, one starts by performing this construction
in each of the factors, then takes the product of the covering families to
create a covering of $\Pi$. This is a hierarchical tree-like decomposition
with margin $r$ and depth $D$. Again, intersecting any subset $X$ of the
product with the covering subsets is a hierarchical tree-like decomposition of
$X$ with margin $r$ and depth $D$.

######  Remark 5.3.

Recall that a real tree in geometry is a geodesic metric space where every
triangle is a tripod. Divergence behavior of geodesics in a real tree allows
to generalize the above constructions in simplicial trees verbatim to real
trees and their products.

In the rest of this section, we show how to use a hierarchical tree-like
decomposition similar to Algorithm 2.

Suppose our complex $K$ is a subcomplex of $\Pi$ with the product cubical
structure. In each factor we assume the simplicial tree structure.
Distributing the computation, one simplifies the computation by applying an
algorithm to slices which are reduced in size compared to the total complex.

In our case this process will be performed inductively using the covering sets
$\mathcal{V}$ in each tree coordinate. This will guarantee that all slices
used in the computation form coverings with margin at least $r$. We remind the
reader that because of the assumptions both $\mathcal{V}$ and $\mathcal{V}[r]$
can be viewed themselves as vertices of forests of trees.

If $\pi_{i}$ is the projection onto the $i$-th coordinate, we have the slices
$S_{i,V}=\pi_{i}^{-1}(V)$ for all $V$ in $\mathcal{V}_{i}$. Since $\pi_{i}$ is
a 1-Lipschitz function, the slices form a covering of $K$ with margin at least
$r$. We think of $\mathcal{V}_{i}$ as analogues of the intervals in Algorithm
2, so the following terminology is natural.

######  Notation 5.4.

Given a vector $x$ with $i$-th coordinate a set $V_{i}$ from
$\mathcal{V}_{i}$, there are “hypercubes”

$C_{x}=S_{1,V_{1}}\cap S_{2,V_{2}}\cap\ldots\cap S_{D,V_{D}}.$

These hypercubes can serve as cells in a grid-like structure in $\Pi$. Note
that the empty set $\emptyset$ can be made a valid value for $V_{\ast}$. Let
$x$ be a vector as above with the property that if $\emptyset$ appears as a
value then all subsequent coordinates must be $\emptyset$. We will use $d(x)$
to denote the highest index for which the value is non-empty. Now the subsets
of indices

$X(s)=\\{x\in\prod\mathcal{V}_{i}\mid D-d(x)=s\\}$

and the corresponding coverings $\mathcal{C}(s)$ by $C_{x}$ for $x\in X(s)$
for increasing values of $s$ form the covering sets that generalize the
rectangles and strips from Algorithm 2. This is precisely the inductive
structure that was leveraged in the 2D plane in the case of each tree $T_{i}$
being a simplicial line covered by the intervals.

##  6\. Remarks on applications

There is now a large library of applications of discrete gradient fields
through its use to simplify computations in topological data analysis but also
direct applications to concrete problems. Our treatment of its parallelization
in this paper is very general. To our knowledge all useful gradient fields
that appear in the literature are uniformly local and so the methods of this
paper can be applied to them.

Just to give an example of gradient fields used for motion planning in
robotics, we mention a couple of recent papers of the second author. The
problem in motion planning is to create an algorithm for a path a robot would
take through the so-called Free Space of all allowable configurations, the
configurations of the robot that avoid all obstructions in the physical
environment. The Free Space is really a parameter space of feasible robot
positions. One approach to modeling it is to sample the Free Space and build
the corresponding simplicial approximation to it through some Vietoris-Rips
complex built on the sample as vertices [14]. There are several ways to
produce a discrete Morse function on a simplicial complex which restricts to
given values on the vertices, or essentially equivalently a gradient field,
some well very known such as [9]. All of them are uniformly local algorithms.
One way this can be used for practical motion planning is as follows. Convex
polyhedral obstructions usually produce convex polyhedral exclusion zones
complementary to the Free Space. One may chose a density estimator for the
sample in Free Space, with values at every sample point, which is then
possible to extend to a Morse function. It is argued in [15] that critical
marginal points can act as “lighthouses” in planning a small finite collection
of paths that provably contains an optimal path of smallest length which can
then be easily extracted.

There are two kinds of applications of our formula in this setting. The
construction of the vector field can be distributed by considering an
arbitrary or antithetic covering of the Free Space. This allows one to
construct the vector field that identifies the lighthouses in patches. There
is also the option of processing the data “as needed”, for example by
exploring an adjacent patch and the next lighthouse only when the robot
approaches its border.

##  7\. Discussion

There are plenty of comments in the literature that point out that by its
nature ProcessLowerStars is embarrassingly parallelizable, cf. Robins et al.
[12] itself and, for another example, section 2 of Guylassy et al. [7]. In the
same way other uniformly local algorithms $\alpha$ are embarrassingly
parallelizable. This perspective of parallelization is not that useful unless
$\alpha$ is very expensive to compute by itself. A more urgent need is the
type of distributed computation that builds partial vector fields on patches
and combines them together. Since discrete vector fields are analogues of
smooth vector fields, it’s not surprising that they are also very locally
defined and are not expensive to compute in each locality. These observations
justify our distributed computation in this paper as the useful perspective on
parallelization in this context.

Related to the point above, we wonder if there are useful discrete vector
fields that are not uniformly local or even those that are uniformly local for
$k\geq 2$ but not for $k=1$. The authors are not aware of any in the
literature. Just to mention another example of a broadly used algorithm, it’s
easy to see that ExtractRaw of King et al. [9] which is used to generate a
discrete vector field from values of a Morse function on 0-cells is uniformly
local for $k=1$. If we are correct then our method in the paper applies to all
known discrete vector fields.

Our future plans include extending Theorem 3.7 and Algorithm 2 to the 3D case
where ProcessLowerStars has been proven to work [12]. We will also address
similar custom efficiency improvements of general formulas for another
algorithm MorseReduce due to Mischaikow and Nanda [11]. This is a versatile
algorithm using discrete Morse theory as preprocessing tool for persistent
homology computations in topological data analysis. The striking feature of
MorseReduce is that it is dimension-independent and can be applied to very
general regular cellular complexes.

Our results apply to infinite complexes and infinite coverings of complexes.
This comment might seem to have no practical implications, however we can use
it to point out that our parallelization theorems allow a dynamic approach to
processing the data. As in the robotics application described in the preceding
section, one may not want to process all available patches at the same time
but rather proceed one patch at a time depending on the need of a dynamic
process such as planning a path. In this case there is a need to incorporate
the new patch into the pre-existing framework. There might be infinitely many
possible patches in the agnostic planning process. The theorems can be used to
extend the definition of the discrete vector field to each successive patch as
many times as needed.

Finally, we would like to contrast our theorems with comparable
parallelization algorithms [6] and [13]. We are grateful to the referee who
pointed out these algorithms to us. Both papers deal with discrete models
approximated by smooth gradient vector fields and geometrically parallelize
the computation of the associated Morse-Smale complexes. The goals of these
authors are very much akin to ours. In fact, we refer the reader to additional
motivation in Related Work sections in both papers. The main distinguishing
feature of our theorems from section 3 is their generality. They apply to any
uniformly local algorithm on any regular cellular complex of any dimension,
while the results of the referenced papers are more specific, geared toward
computation of Morse-Smale complexes associated to gradient flows on lower
dimensional manifolds. We don’t say these are special cases of the general
theorems. They are certainly leaner and more efficient algorithms for that
specific task, much like our Theorem 3.7 is not a special case of Theorem 3.1
and its corollaries.

## References

  * [1] G. Carlsson and B. Goldfarb, The integral $K$-theoretic Novikov conjecture for groups with finite asymptotic dimension, Invent. Math. 157 (2004), 405–418.
  * [2] O. Delgado-Friedrichs, V. Robins, and A. Sheppard, Skeletonization and partitioning of digital images using discrete Morse theory, IEEE Trans. Pattern Anal. Mach. Intell. 37 (2015), 654–666.
  * [3] A. Dranishnikov, On hypersphericity of manifolds with finite asymptotic dimension, Trans. Amer. Math. Soc. 355 (2003), 155–167.
  * [4] R. Forman, A user’s guide to discrete Morse theory, Sém. Lothar. Combin, 48, (2002), 35pp.
  * [5] B. Goldfarb, Singular persistent homology with geometrically parallelizable computation, Topol. Proc. 55 (2020), 273–294.
  * [6] A. Gyulassy, P.-T. Bremer, B. Hatmann and V. Pascucci, A Practical Approach to Morse-Smale Complex Computation: Scalability and Generality, in IEEE Trans. Vis. Comput. Graph. 6 (2008), 1619–1626.
  * [7] A. Gyulassy, P.-T. Bremer, and V. Pascucci, Computing Morse-Smale Complexes with Accurate Geometry, IEEE Trans. Vis. Comput. Graph. 18 (2012), 2014–2022.
  * [8] D. Kasprowski, Coarse embeddings into products of trees, to appear in Kyoto Journal of Mathematics, arXiv:1810.13361.
  * [9] H. King, K. Knudson, and N. Mramor, Generating discrete Morse functions from point data, Experimental Mathematics 14 (2005), 435–444.
  * [10] K.P. Knudson, Morse Theory: Smooth and Discrete, World Scientific, 2015.
  * [11] K. Mischaikow and V. Nanda, Morse Theory for Filtrations and Efficient Computation of Persistent Homology, Discr. Comput. Geom. 50 (2013), 330–353.
  * [12] V. Robins, P.J. Wood, and A. Sheppard, Theory and algorithms for constructing discrete Morse complexes from grayscale digital images, IEEE Trans. Pattern Anal. Mach. Intell. 33 (2011), 1646–1658.
  * [13] N. Shivashankar, Senthilnathan M, and V. Natarajan, Parallel Computation of 2D Morse-Smale Complexes, in IEEE Trans. Vis. Comput. Graph. 18 (2012), 1757–1770.
  * [14] A. Upadhyay, W. Wang, and C. Ekenna, Approximating cfree space topology by constructing Vietoris-Rips complex in Proceedings of 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2019), 2019, 2517–2523.
  * [15] A. Upadhyay, B. Goldfarb, and C. Ekenna, A topological approach to finding coarsely diverse paths, in Proceedings of 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2021).


# Dataset for the First Evaluation on Chinese Machine Reading Comprehension

###### Abstract

Machine Reading Comprehension (MRC) has become enormously popular recently and
has attracted a lot of attention. However, existing reading comprehension
datasets are mostly in English. To add diversity in reading comprehension
datasets, in this paper we propose a new Chinese reading comprehension dataset
for accelerating related research in the community. The proposed dataset
contains two different types: cloze-style reading comprehension and user query
reading comprehension, associated with large-scale training data as well as
human-annotated validation and hidden test set. Along with this dataset, we
also hosted the first Evaluation on Chinese Machine Reading Comprehension
(CMRC-2017) and successfully attracted tens of participants, which suggest the
potential impact of this dataset.

Keywords: Chinese Reading Comprehension, Question Answering, Evaluation

languageresourceLanguage Resources

Dataset for the First Evaluation on Chinese Machine Reading Comprehension

Yiming Cui†, Ting Liu‡, Zhipeng Chen†, Wentao Ma†, Shijin Wang† and Guoping
Hu†
---
†Joint Laboratory of HIT and iFLYTEK, iFLYTEK Research, Beijing, China
‡Research Center for Social Computing and Information Retrieval,
Harbin Institute of Technology, Harbin, China
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

Abstract content

##  1\. Introduction

Machine Reading Comprehension (MRC) has become enormously popular in recent
research, which aims to teach the machine to comprehend human languages and
answer the questions based on the reading materials. Among various reading
comprehension tasks, the cloze-style reaing comprehension is relatively easy
to follow due to its simplicity in definition, which requires the model to
fill an exact word into the query to form a coherent sentence according to the
document material. Several cloze-style reading comprehension datasets are
publicly available, such as CNN/Daily Mail [Hermann et al., 2015], Children’s
Book Test [Hill et al., 2015], People Daily and Children’s Fairy Tale [Cui et
al., 2016].

In this paper, we provide a new Chinese reading comprehension dataset111CMRC
2017 Public Datasets: https://github.com/ymcui/cmrc2017., which has the
following features

  * •

We provide a large-scale automatically generated Chinese cloze-style reading
comprehension dataset, which is gathered from children’s reading material.

  * •

Despite the automatic generation of training data, our evaluation datasets
(validation and test) are annotated manually, which is different from previous
works.

  * •

To add more diversity and for further investigation on transfer learning, we
also provide another evaluation datasets which is also annotated by human, but
the query is more natural than the cloze type.

We also host the 1st Evaluation on Chinese Machine Reading Comprehension
(CMRC2017), which has attracted over 30 participants and finally there were 17
participants submitted their evaluation systems for testing their reading
comprehension models on our newly developed dataset, suggesting its potential
impact. We hope the release of the dataset to the public will accelerate the
progress of Chinese research community on machine reading comprehension field.

We also provide four official baselines for the evaluations, including two
traditional baselines and two neural baselines. In this paper, we adopt two
widely used neural reading comprehension model: AS Reader [Kadlec et al.,
2016] and AoA Reader [Cui et al., 2017].

The rest of the paper will be organized as follows. In Section 2, we will
introduce the related works on the reading comprehension dataset, and then the
proposed dataset as well as our competitions will be illustrated in Section 3.
The baseline and participant system results will be given in Section 4 and we
will made a brief conclusion at the end of this paper.

|  | Cloze Track | User Query Track
---|---|---|---
| Train | Validation | Test | Validation | Test
# Query | 354,295 | 2,000 | 3,000 | 2,000 | 3,000
Max # tokens in docs | 486 | 481 | 484 | 481 | 486
Max # tokens in query | 184 | 72 | 106 | 21 | 29
Avg # tokens in docs | 324 | 321 | 307 | 310 | 290
Avg # tokens in query | 27 | 19 | 23 | 8 | 8
Vocabulary | 94,352
Table 1:  Statistics of the dataset for the 1st Evaluation on Chinese Machine
Reading Comprehension (CMRC-2017).

##  2\. Related Works

In this section, we will introduce several public cloze-style reading
comprehension dataset.

###  2.1. CNN/Daily Mail

Some news articles often come along with a short summary or brief
introduction. Inspired by this, Hermann et al. [Hermann et al., 2015] release
the first cloze-style reading comprehension dataset, called CNN/Daily
Mail222The pre-processed CNN and Daily Mail datasets are available at
http://cs.nyu.edu/~kcho/DMQA/. Firstly, they obtained large-scale CNN and
Daily Mail news data from online websites, including main body and its
summary. Then they regard the main body of the news as the Document. The Query
is generated by replacing a name entity word from the summary by a
placeholder, and the replaced named entity word becomes the Answer. Along with
the techniques illustrated above, after the initial data generation, they also
propose to anonymize all named entity tokens in the data to avoid the model
exploit world knowledge of specific entities, increasing the difficulties in
this dataset. However, as we have known that world knowledge is very important
when we do reading comprehension in reality, which makes this dataset much
artificial than real situation. Chen et al. [Chen et al., 2016] also showed
that the proposed anonymization in CNN/Daily Mail dataset is less useful, and
the current models [Kadlec et al., 2016, Chen et al., 2016] are nearly
reaching ceiling performance with the automatically generated dataset which
contains much errors, such as coreference errors, ambiguous questions etc.

###  2.2. Children’s Book Test

Another popular cloze-style reading comprehension dataset is the Children’s
Book Test (CBT)333Available at
http://www.thespermwhale.com/jaseweston/babi/CBTest.tgz proposed by Hill et
al. [Hill et al., 2015] which was built from the children’s book stories.
Though the CBT dataset also use an automatic way for data generation, there
are several differences to the CNN/Daily Mail dataset. They regard the first
20 consecutive sentences in a story as the Document and the following 21st
sentence as the Query where one token is replaced by a placeholder to indicate
the blank to fill in. Unlike the CNN/Daily Mail dataset, in CBT, the replaced
word are chosen from various types: Name Entity (NE), Common Nouns (CN), Verbs
(V) and Prepositions (P). The experimental results showed that, the verb and
preposition answers are not sensitive to the changes of document, so the
following works are mainly focusing on solving the NE and CN genres.

###  2.3. People Daily & Children’s Fairy Tale

The previously mentioned datasets are all in English. To add diversities to
the reading comprehension datasets, Cui et al. [Cui et al., 2016] proposed the
first Chinese cloze-style reading comprehension dataset: People Daily &
Children’s Fairy Tale, including People Daily news datasets and Children’s
Fairy Tale datasets. They also generate the data in an automatic manner, which
is similar to the previous datasets. They choose short articles (several
hundreds of words) as Document and remove a word from it, whose type is mostly
named entities and common nouns. Then the sentence that contains the removed
word will be regarded as Query. To add difficulties to the dataset, along with
the automatically generated evaluation sets (validation/test), they also
release a human-annotated evaluation set. The experimental results show that
the human-annotated evaluation set is significantly harder than the
automatically generated questions. The reason would be that the automatically
generated data is accordance with the training data which is also
automatically generated and they share many similar characteristics, which is
not the case when it comes to human-annotated data.

Figure 1:  Examples of the proposed datasets (the English translation is in
grey). The sentence ID is depicted at the beginning of each row. In the Cloze
Track, “XXXXX” represents the missing word.

##  3\. The Proposed Dataset

In this section, we will briefly introduce the evaluation tracks and then the
generation method of our dataset will be illustrated in detail.

###  3.1. The 1st Evaluation on Chinese Machine Reading Comprehension
(CMRC-2017)

The proposed dataset is typically used for the 1st Evaluation on Chinese
Machine Reading Comprehension (CMRC-2017)444CMRC 2017 Official Website:
http://www.hfl-tek.com/cmrc2017/index.html., which aims to provide a
communication platform to the Chinese communities in the related fields. In
this evaluation, we provide two tracks. We provide a shared training data for
both tracks and separated evaluation data.

  * •

Cloze Track: In this track, the participants are required to use the large-
scale training data to train their cloze system and evaluate on the cloze
evaluation track, where training and test set are exactly the same type.

  * •

User Query Track: This track is designed for using transfer learning or domain
adaptation to minimize the gap between cloze training data and user query
evaluation data, i.e. training and testing is fairly different.

Following Rajpurkar et al. [Rajpurkar et al., 2016], we preserve the test set
only visible to ourselves and require the participants submit their system in
order to provide a fair comparison among participants and avoid tuning
performance on the test set. The examples of Cloze and User Query Track are
given in Figure 1.

###  3.2. Definition of Cloze Task

The cloze-style reading comprehension can be described as a triple
$\langle\mathcal{D},\mathcal{Q},\mathcal{A}\rangle$, where $\mathcal{D}$
represents Document, $\mathcal{Q}$ represents Query and the $\mathcal{A}$
represents Answer. There is a restriction that the answer should be a single
word and should appear in the document, which was also adopted in [Hill et
al., 2015, Cui et al., 2016]. In our dataset, we mainly focus on answering
common nouns and named entities which require further comprehension of the
document.

###  3.3. Automatic Generation

Following Cui et al. [Cui et al., 2016], we also use similar way to generate
our training data automatically. Firstly we roughly collected 20,000 passages
from children’s reading materials which were crawled in-house. Briefly, we
choose an answer word in the document and treat the sentence containing answer
word as the query, where the answer is replaced by a placeholder “XXXXX”. The
detailed procedures can be illustrated as follows.

  * •

Pre-processing: For each sentence in the document, we do word segmentation,
POS tagging and dependency parsing using LTP toolkit [Che et al., 2010].

  * •

Dependency Extraction: Extract following dependencies: COO, SBV, VOB, HED,
FOB, IOB, POB555Full descriptions of abbreviations can be found at
http://www.ltp-cloud.com/intro/en/#dp_how., and only preserve the parts that
have dependencies.

  * •

Further Filtering: Only preserve SBV, VOB and restrict the related words not
to be pronouns and verbs.

  * •

Frequency Restriction: After calculating word frequencies, only word frequency
that greater than 2 is valid for generating question.

  * •

Question Restriction: Only five questions can be extracted within one passage.

###  3.4. Human Annotation

Apart from the automatically generated large-scale training data, we also
provide human-annotated validation and test data to improve the estimation
quality. The annotation procedure costs one month with 5 annotators and each
question is cross-validated by another annotator. The detailed procedure for
each type of dataset can be illustrated as follows.

####  3.4.1. Cloze-style Reading Comprehension

For the validation and test set in cloze data, we first randomly choose 5,000
paragraphs each for automatically generating questions using the techniques
mentioned above. Then we invite our resource team to manually select 2,000
questions based on the following rules.

  * •

Whether the question is appropriate and correct

  * •

Whether the question is hard for LMs to answer

  * •

Only select one question for each paragraph

####  3.4.2. User Query Reading Comprehension

Unlike the cloze dataset, we have no automatic question generation procedure
in this type. In the user query dataset, we asked our annotator to directly
raise questions according to the passage, which is much difficult and time-
consuming than just selecting automatically generated questions. We also
assign 5,000 paragraphs for question annotations in both validation and test
data. Following rules are applied in asking questions.

  * •

The paragraph should be read carefully and judged whether appropriate for
asking questions

  * •

No more than 5 questions for each passage

  * •

The answer should be better in the type of nouns, named entities to be fully
evaluated

  * •

Too long or too short paragraphs should be skipped

##  4\. Experiments

In this section, we will give several baseline systems for evaluating our
datasets as well as presenting several top-ranked systems in the competition.

|  | Single Model | Ensemble
---|---|---|---
Rank | System | Validation |  Test |  Validation |  Test
- | Baseline - Random Guess | 1.65 |  1.67 |  - |  -
- | Baseline - Top Frequency | 14.85 |  14.07 |  - |  -
- | Baseline - AS Reader (default settings) | 76.05 |  77.67 |  - |  -
- | Baseline - AoA Reader (default settings) | 77.20 |  78.63 |  - |  -
1 | 6ESTATES | 75.85 |  74.73 |  81.85 |  81.90
2 | Shanghai Jiao Tong Univeristy BCMI-NLP | 76.15 |  77.73 |  78.35 |  80.67
3 | XinkTech | 77.15 |  77.53 |  79.20 |  80.27
4 | East China Normal University (ECNU) | 77.95 |  77.40 |  79.45 |  79.70
5 | Ludong University | 74.75 |  75.07 |  77.05 |  77.07
6 | Wuhan University (WHU) | 78.20 |  76.53 |  - |  -
7 | Harbin Institute of Technology at Shenzhen (HITSZ) | 76.05 |  75.93 |  - |  -
8 | HuoYan Technology | 73.55 |  75.77 |  - |  -
9 | Wuhan University of Science and Technology (WUST) | 73.80 |  74.53 |  - |  -
10 | Beijing Information Science and Technology University | 70.05 |  70.20 |  - |  -
11 | Shanxi Univerisity (SXU-2) | 62.60 |  64.70 |  66.65 |  68.47
12 | Shenyang Aerospace University (SAU) | 63.15 |  65.80 |  - |  -
13 | Shanxi University (SXU-1) | 64.85 |  64.67 |  - |  -
14 | Zhengzhou Univerisity (ZZU) | 52.80 |  54.53 |  - |  -
Table 2:  Results on Cloze Track. The best baseline and participant systems
are depicted in bold face.

###  4.1. Baseline Systems

We set several baseline systems for testing basic performance of our datasets
and provide meaningful comparisons to the participant systems. In this paper,
we provide four baseline systems, including two simple ones and two neural
network models. The details of the baseline systems are illustrated as
follows.

  * •

Random Guess: In this baseline, we randomly choose one word in the document as
the answer.

  * •

Top Frequency: We choose the most frequent word in the document as the answer.

  * •

AS Reader: We implemented Attention Sum Reader (AS Reader) [Kadlec et al.,
2016] for modeling document and query and predicting the answer with the
Pointer Network [Vinyals et al., 2015], which is a popular framework for
cloze-style reading comprehension. Apart from setting embedding and hidden
layer size as 256, we did not change other hyper-parameters and experimental
setups as used in Kadlec et al. [Kadlec et al., 2016], nor we tuned the system
for further improvements.

  * •

AoA Reader: We also implemented Attention-over-Attention Reader (AoA Reader)
[Cui et al., 2017] which is the state-of-the-art model for cloze-style reading
comprehension. We follow hyper-parameter settings in AS Reader baseline
without further tuning.

In the User Query Track, as there is a gap between training and validation, we
follow [Liu et al., 2017] and regard this task as domain adaptation or
transfer learning problem. The neural baselines are built by the following
steps.

  * •

We first use the shared training data to build a general systems, and choose
the best performing model (in terms of cloze validation set) as baseline.

  * •

Use User Query validation data for further tuning the systems with 10-fold
cross-validations.

  * •

Increase dropout rate [Srivastava et al., 2014] to 0.5 for preventing over-
fitting issue.

All baseline systems are chosen according to the performance of the validation
set.

System | Validation |  Test
---|---|---
Baseline - Random Guess | 1.50 |  1.47
Baseline - Top Frequency | 10.65 |  8.73
Baseline - AS Reader | - |  49.03
Baseline - AoA Reader | - |  51.53
ECNU (Ensemble) | 90.45 |  69.53
ECNU (single model) | 85.55 |  65.77
Shanxi University (Team-3) | 47.80 |  49.07
Zhengzhou University | 31.10 |  32.53
Table 3:  Results on User Query Track. Due to the using of validation data, we
did not report its performance.

###  4.2. Participant Systems

The participant system results666Full CMRC 2017 Leaderboard: http://www.hfl-
tek.com/cmrc2017/leaderboard.html. are given in Table 2 and 3.

####  4.2.1. Cloze Track

As we can see that two neural baselines are competitive among participant
systems and AoA Reader successfully outperform AS Reader and all participant
systems in single model condition, which proves that it is a strong baseline
system even without further fine-tuning procedure. Also, the best performing
single model among participant systems failed to win in the ensemble
condition, which suggest that choosing right ensemble method is essential in
most of the competitions and should be carefully studied for further
performance improvements.

####  4.2.2. User Query Track

Not surprisingly, we only received three participant systems in User Query
Track, as it is much difficult than Cloze Track. As shown in Table 3, the test
set performance is significantly lower than that of Cloze Track, due to the
mismatch between training and test data. The baseline results give competitive
performance among three participants, while failed to outperform the best
single model by ECNU, which suggest that there is much room for tuning and
using more complex methods for domain adaptation.

##  5\. Conclusion

In this paper, we propose a new Chinese reading comprehension dataset for the
1st Evaluation on Chinese Machine Reading Comprehension (CMRC-2017),
consisting large-scale automatically generated training set and human-
annotated validation and test set. Many participants have verified their
algorithms on this dataset and tested on the hidden test set for final
evaluation. The experimental results show that the neural baselines are tough
to beat and there is still much room for using complicated transfer learning
method to better solve the User Query Task. We hope the release of the full
dataset (including hidden test set) could help the participants have a better
knowledge of their systems and encourage more researchers to do experiments
on.

##  6\. Acknowledgements

We would like to thank the anonymous reviewers for their thorough reviewing
and providing thoughtful comments to improve our paper. We thank the Sixteenth
China National Conference on Computational Linguistics (CCL 2017) and Nanjing
Normal University for providing space for evaluation workshop. Also we want to
thank our resource team for annotating and verifying evaluation data. This
work was supported by the National 863 Leading Technology Research Project via
grant 2015AA015409.

##  7\. Bibliographical References

## References

  * Che et al., 2010 Che, W., Li, Z., and Liu, T.  (2010).  Ltp: A chinese language technology platform.  In Proceedings of the 23rd International Conference on Computational Linguistics: Demonstrations, pages 13–16. Association for Computational Linguistics.
  * Chen et al., 2016 Chen, D., Bolton, J., and Manning, D. C.  (2016).  A thorough examination of the cnn/daily mail reading comprehension task.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2358–2367. Association for Computational Linguistics.
  * Cui et al., 2016 Cui, Y., Liu, T., Chen, Z., Wang, S., and Hu, G.  (2016).  Consensus attention-based neural networks for chinese reading comprehension.  In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pages 1777–1786. The COLING 2016 Organizing Committee.
  * Cui et al., 2017 Cui, Y., Chen, Z., Wei, S., Wang, S., Liu, T., and Hu, G.  (2017).  Attention-over-attention neural networks for reading comprehension.  In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 593–602. Association for Computational Linguistics.
  * Hermann et al., 2015 Hermann, K. M., Kocisky, T., Grefenstette, E., Espeholt, L., Kay, W., Suleyman, M., and Blunsom, P.  (2015).  Teaching machines to read and comprehend.  In Advances in Neural Information Processing Systems, pages 1684–1692.
  * Hill et al., 2015 Hill, F., Bordes, A., Chopra, S., and Weston, J.  (2015).  The goldilocks principle: Reading children’s books with explicit memory representations.  arXiv preprint arXiv:1511.02301.
  * Kadlec et al., 2016 Kadlec, R., Schmid, M., Bajgar, O., and Kleindienst, J.  (2016).  Text understanding with the attention sum reader network.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 908–918. Association for Computational Linguistics.
  * Liu et al., 2017 Liu, T., Cui, Y., Yin, Q., Zhang, W.-N., Wang, S., and Hu, G.  (2017).  Generating and exploiting large-scale pseudo training data for zero pronoun resolution.  In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 102–111. Association for Computational Linguistics.
  * Rajpurkar et al., 2016 Rajpurkar, P., Zhang, J., Lopyrev, K., and Liang, P.  (2016).  Squad: 100,000+ questions for machine comprehension of text.  In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2383–2392. Association for Computational Linguistics.
  * Srivastava et al., 2014 Srivastava, N., Hinton, G. E., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R.  (2014).  Dropout: a simple way to prevent neural networks from overfitting.  Journal of Machine Learning Research, 15(1):1929–1958.
  * Vinyals et al., 2015 Vinyals, O., Fortunato, M., and Jaitly, N.  (2015).  Pointer networks.  In Advances in Neural Information Processing Systems, pages 2692–2700.