We present an algorithm which takes as input a finite set $X$ of automorphisms of a simplicial tree, and outputs a generating set $X'$ of $\gen{X}$ such that either $\gen{X}$ is purely hyperbolic and $X'$ is a free basis of $\gen{X}$, or $X'$ contains a non-trivial elliptic element. As a special case, the algorithm decides whether a finitely generated group acting on a locally finite tree is discrete and free. This algorithm, which is based on  Nielsen's reduction method, works by repeatedly applying Nielsen transformations to $X$ to minimise the generators of $X'$ with respect to a given pre-well-ordering. We use this algorithm to solve the constructive membership problem for finitely generated purely hyperbolic automorphism groups of trees. We provide a Magma implementation of these algorithms, and report its performance.

§ INTRODUCTION

There is a rich theory of groups acting on geometric spaces. Of interest are groups which are discrete and free; examples are Schottky subgroups of $\PSL_2(\R)$ and $\PSL_2(\C)$ acting on hyperbolic space [1, 14], and of $\PSL_2(K)$ for a non-archimedean local field $K$ acting on the Bruhat-Tits tree [11, 15]. For a topological group $G$ acting on such a space, some natural problems are the following:

* Decide whether $G$ is discrete and free, and if so find a free basis for $G$.

* The constructive membership problem. Suppose $G$ is a subgroup of a group $H$. Given $g \in H$, decide whether $g \in G$, and if so write $g$ as a word in a specified generating set of $G$.

The first problem was solved for 2-generator subgroups of $\PSL_2(\R)$ by Purzitsky [16].
The second problem was solved for discrete free 2-generator subgroups of $\PSL_2(\R)$ by Eick, Kirschmer, and Leedham-Green [5], and was later generalised to discrete 2-generator subgroups of $\PSL_2(\R)$ by Kirschmer and Rüther [10]. For larger numbers of generators, the problems remain open.

Conder [4] solved (1) for 2- and 3-generator groups of automorphisms of locally finite trees, and conjectures an algorithm for every finite number of generators <cit.>. In this paper, we solve (1) for all finitely generated groups of automorphisms of locally finite trees. More generally, we provide an algorithm to decide whether a finitely generated group of automorphisms of a simplicial tree is purely hyperbolic (that is, every vertex has trivial stabiliser). We also solve (2) for finitely generated purely hyperbolic subgroups of automorphism groups of trees.

The standard approach to these problems, as done in [4, 5, 7], uses the interactions between translation axes and translation lengths of the generators. This is difficult to generalise to higher numbers of generators, since the number of possible interactions grows rapidly.

In Section <ref> we prove the following theorem:

Let $T$ be a simplicial tree. Let $X$ be a finite subset of $\Aut(T)$ generating a group $G$. There exists an algorithm that, given $X$, outputs a basis $X'$ of $G$ that either contains an elliptic element or is a free basis for $G$.

We use an analogue of Nielsen's method of finding a free basis for a finitely generated subgroup of a free group <cit.>. We define a strongly  basis, and show that if $G$ is purely hyperbolic (in particular, if $T$ is locally finite and $G$ is discrete and free), then a strongly basis exists. This provides an algorithmic version of a theorem of Weidmann [18] which, while non-constructive, uses similar methods to show that such a basis  exists.

As a consequence, we obtain the following:

Let $T$ be a locally finite simplicial tree. Let $X$ be a finite subset of $\Aut(T)$ generating a group $G$. There exists an algorithm that, given $X$, decides whether $G$ is discrete and free.

In Section <ref> we prove that if $G$ is purely hyperbolic, then it has a unique strongly basis.
In Section <ref> we associate to $G$ a fundamental domain $\Gamma(G)$, and provide an algorithm that takes as input a vertex $v$ of $T$ and outputs the unique $g \in G$ such that $gv\in \Gamma(G)$. With this we prove the following:
Every finitely generated purely hyperbolic subgroup of $\Aut(T)$ has solvable constructive membership problem.

In Section <ref>, we discuss our implementation of these algorithms in Magma [2] for finitely generated subgroups of $\PGL_2(K)$ acting on the Bruhat-Tits tree where $K$ is a $p$-adic field, and report its performance.

§.§ Related work

The application of Nielsen reduction to trees is not new. Weidmann [18] uses similar methods to prove results relating to finitely generated groups acting on trees. In particular, he provides conditions under which a finite set of automorphisms of a tree generates an amalgamated product where each factor is either free or has a global fixed point <cit.>.

In another generalisation, Kapovich and Weidmann [9] prove that a finite generating set of a group $G$ acting on a $\delta$-thin hyperbolic space is Nielsen equivalent to a generating set of $G$ that is either a free basis for $G$ or contains a generator of “small" translation length.

Both results provide a non-constructive version of Theorem <ref> as a special case. The method works by iteratively replacing a generator with an element of $G$ that can be obtained via Nielsen transformations and is smaller with respect to a given pre-order, until no further replacements are possible. However, the methods in these papers are non-constructive, as they do not provide a bound on the word length of such an element. We show that if such a replacement exists, then one exists with word length 2. This allows us to obtain a practical algorithm to find a free basis, and to solve the constructive membership problem.

There is also a generalisation of Nielsen's methods to groups with a length function, as detailed by Hoare [8] and by Lyndon and Schupp <cit.>. Depending on the axioms chosen, $\Aut(T)$ can be endowed with a length function. However, to our knowledge none of the results on length functions specialise to the results in this paper.

§ NIELSEN REDUCTION

For the remainder of this paper we fix the following notation:

* $T$ is a simplicial tree with vertex set $V(T)$. We identify $T$ with its geometric realisation, so that a point $w \in T$ may be a vertex or lie on an edge.

* $X$ is a finite subset of $\Aut(T)$ generating a group $G$ equipped with the compact-open topology [6].

* $\vo$ is a distinguished vertex of $T$. It may be chosen arbitrarily, but once chosen it remains fixed.

* If $u$ and $w$ are vertices of $T$, then $[u, w]$ is the unique path (without backtracking) from $u$ to $w$. We identify this path with the corresponding line segment in the geometric realisation of $T$.

* Given a path $p$ on $T$ and $C \subseteq T$, if $p \cap C$ is the geometric realisation of a subpath $q$ of $p$, then we identify $p \cap C$ with $q$.

* If $p$ is a path or a walk (that is, a path with possible backtracking) on $T$, then $\abs{p}$ is the length of $p$. For a walk, this is the number of terms in the corresponding sequence of edges.

* $X^- = \Set{g^{-1} \given g \in X}$ and $X^\pm = X \cup X^-$.

* Given $g \in G$, define $\abs{g} = d(\vo, g\vo)$, where $d$ is the graph distance on $T$.

* Given $g \in G$, the translation length of $g$ is $l(g) = \min\Set{d(w, gw) \given w \in T}$.
The minimum translation set of $g$ is $\Min(g) = \Set{w \in T \given d(w, gw) = l(g)}$.

Recall that $g$ is elliptic if $l(g) = 0$, and hyperbolic if $l(g) > 0$. Elliptic elements are typically distinguished from inversions which invert an edge [6]. By our definition, inversions are elliptic: If $g$ inverts an edge $e$, then $l(g) = 0$ and $\Min(g)$ is the midpoint of $e$. If all nontrivial elements of $G$ are hyperbolic, then $G$ is purely hyperbolic.

This section closely follows Nielsen's proof of his Subgroup Theorem, which states that a finitely generated subgroup of a free group is free <cit.>. In particular, Nielsen uses cancellation of words in a free group; we use cancellation of paths on a tree. The use of conditions N1, N2, and N3 (see Definition <ref>), and the pre-well-ordering defined on $G$ (see Definition <ref>), remains essentially the same. In our case, an added complication is the possible existence of elliptic elements.

If $g, h \in G$, then $\delta(g, h) = (\abs{g} + \abs{h} - \abs{g^{-1}h}$)/2.

Note that $\delta(g, h) = \delta(h, g)$, but $\delta(g, h) \neq \delta(g^{-1}, h^{-1})$ in general.

For all $g, h \in G$, $\delta(g, h) = \abs{[\vo, g\vo] \cap [\vo, h\vo]}$.

Let $w$ be the vertex of $T$ such that $[\vo, g\vo] \cap [\vo, h\vo] = [\vo, w]$. Now $[g\vo, h\vo] = [g\vo, w] \cup [w, h\vo]$; see Figure <ref>. We deduce that

\begin{align*}
\delta(g, h) &= (d(\vo, g\vo) + d(\vo, h\vo) - d(\vo, g^{-1}h\vo))/2 \\
&= (d(\vo, g\vo) + d(\vo, h\vo) - d(g\vo, h\vo))/2 \\
&= (d(\vo, g\vo) + d(\vo, h\vo) - d(w, g\vo) - d(w, h\vo))/2 \\
&= d(\vo, w) \\
&= \abs{[\vo, g\vo] \cap [\vo, h\vo]}. \qedhere
\end{align*}

$\delta(g, h)$ is the length of $[\vo, g\vo] \cap [\vo, h\vo]$

For all $g \in G$, $l(g) = \abs{g^2}-\abs{g} = \abs{g} - 2\delta(g^{-1}, g)$.

By <cit.>, the midpoint of $[\vo, g\vo]$ lies in $\Min(g)$. Let $w = \proj_{\Min(g)}(\vo)$. Now,

\begin{align*}
d(\vo, g^2\vo) &= d(\vo, w) + d(w, g^2w) + d(g^2w, g^2\vo) \\
&= d(\vo, w) + 2d(w, gw) + d(g\vo, gw) \\
&= d(\vo, g\vo) + l(g).
\end{align*}

This proves the first equality; the second follows from Definition <ref>.

Let $g = a_1 a_2 \dots a_n$ be a reduced word in $X$. Each $a_i$ may be identified with the path $p_i = [b_{i}\vo, b_{i} a_i \vo]$, where $b_i = a_1 \dots a_{i-1}$. We say that $p_i$ is the path of $a_i$ in $g$.
Note that a walk from $\vo$ to $g\vo$ is formed by the concatenation of the $p_i$, each of which is isometric to $[\vo, a_i\vo]$. If a subpath $q$ of $p_i$ of nonzero length is disjoint from the interior of $[\vo, g\vo]$, then it is cancelled in $g$. If $q$ is contained in $[\vo, g\vo]$, then it is uncancelled in $g$.

If $x, y \in X^\pm$, then $[\vo, x\vo] \cup [x\vo, xy\vo] = [\vo, xy\vo] \cup p$, where $p = [\vo, x\vo] \cap [x\vo, xy\vo]$ is a (possibly empty) path of length $\delta(x^{-1}, y)$.

By Proposition <ref>, $\delta(x^{-1}, y) = \abs{[\vo, x^{-1}\vo] \cap [\vo, y\vo]} = \abs{[\vo, x\vo] \cap [x\vo, xy\vo]}$. We see from Figure <ref> that $[\vo, x\vo] \cup [x\vo, xy\vo] = [\vo, xy\vo] \cup p$.

The path $p$ is cancelled in $xy$, while $[\vo, w]$ and $[w, xy\vo]$ are uncancelled

Following the notation of  <cit.>, $X$ is Nielsen-reduced (or  for short) if it has no non-trivial elliptic elements and the following are satisfied:

N1. $X \cap X^- = \varnothing$.

N2. For all $x, y \in X^{\pm}$, if $x \neq y^{-1}$, then $\abs{xy} \geq \max\{\abs{x}, \abs{y}\}$.

N3. For all $x, y, z \in X^{\pm}$, if $x \neq y^{-1}$ and $y \neq z^{-1}$, then $\abs{xyz} > \abs{x} + \abs{z} - \abs{y}$.

We use a stronger definition of N1 than <cit.>; that definition allows both $x$ and $x^{-1}$ to be in $X$.

Let $x, y, z \in X^\pm$. Let $p = [\vo, x\vo] \cap [x\vo, xy\vo]$ and $q = [x\vo, xy\vo] \cap [xy\vo, xyz\vo]$.
Let $\Delta = \abs{y} - \delta(x^{-1}, y) - \delta(y^{-1}, z)$. If $\Delta > 0$, then $p$ and $q$ do not intersect and $d(p, q) = \Delta$.
If $\Delta \leq 0$, then $p \cap q$ is a path of length $-\Delta$.

Let $\phi$ be the isometric embedding of $[x\vo, xy\vo]$ into $\R$ such that $\phi(x\vo) = 0$ and $\phi(xy\vo) = \abs{y}$. We identify the image of a path under $\phi$ with the image of the points it contains. By Proposition <ref>, $\phi(p) = [0, \delta(x^{-1}, y)]$ and $\phi(q) = [\abs{y}-\delta(y^{-1}, z), \abs{y}]$. The result follows by computing either $d(\phi(p), \phi(q))$ or the length of $\phi(p) \cap \phi(q)$.

We define a similar set of conditions to N2 and N3 on $X$:

N2$'$. For all $x, y \in X^{\pm}$, if $x \neq y^{-1}$, then $\delta(x^{-1}, y) \leq \min\{\abs{x}/2, \abs{y}/2\}$.

N3$'$. For all $x, y, z \in X^{\pm}$, if $x \neq y^{-1}$ and $y \neq z^{-1}$, then $\delta(x^{-1}, y) + \delta(y^{-1}, z) < \abs{y}$.

* $\textup{N2}$ is equivalent to $\textup{N2}'$.

* If $\textup{N2}$ holds, then $\textup{N3}$ is equivalent to $\textup{N3}'$.

Let $x, y, z \in X^{\pm}$.

* Observe that $\delta(x^{-1}, y) = (\abs{x} + \abs{y} - \abs{xy})/2 \leq \min\{\abs{x}/2, \abs{y}/2\}$ if and only if $\abs{xy} \ge \max\{\abs{x}, \abs{y}\}$. See Figure <ref> (a).

* Let $\Delta = \abs{y} - \delta(x^{-1}, y) - \delta(y^{-1}, z)$. By N2$'$, $\Delta \geq 0$. By Lemma <ref>, we have the situation in Figure <ref> (b): Namely, $\abs{xyz} = \abs{x} + \abs{z} - \abs{y} + \Delta$. Thus N3 holds if and only if $\Delta > 0$, which in turn is true if and only if N3$'$ holds.

N2$'$: At least half of the paths of both $x$ and $y$ are uncancelled in $xy$

N3$'$: The path of $y$ has a subpath of length $\Delta$ uncancelled in $xyz$

Examples of conditions N2$'$ and N3$'$

The conditions N2$'$ and N3$'$ can be interpreted geometrically: N2$'$ states that at least half of the path of $x$ (similarly $y$) must be uncancelled in $xy$; N3$'$ states that there must be a subpath of the path of $y$ uncancelled in $xyz$.

A Nielsen transformation of $X$ is a composition of the following operations:

* Remove some $g \in X$, where both $g$ and $g^{-1}$ are in $X$.

* Replace some $g \in X$ with $g^{-1}$.

* Replace some $g \in X$ by $g^{\e_1} h^{\e_2}$ or $h^{e_2} g^{e_1}$, where $h \in X \setminus \{g\}$ and $\e_1, \e_2 \in \{1, -1\}$.

This definition of a Nielsen transformation is equivalent to the usual definition (as seen in <cit.>), but is more useful for this paper.

We sometimes refer to a replacement of $g$ by $h$ where $g \in X^{\pm}$. This denotes either a replacement of $g$ by $h$ or of $g^{-1}$ by $h^{-1}$, depending on whether $g$ or $g^{-1}$ is in $X$. Note that if $X'$ is obtained from $X$ via a Nielsen transformation, then $\gen{X'} = \gen{X}$.

The following lemma demonstrates a local-to-global phenomenon that can be similarly observed in Nielsen's algorithm: A path cancelled in a word $g$ in an set is isometric to a path cancelled in a subword of length 2. This allows us to express $\abs{g}$ in terms of the lengths of cancellations between consecutive terms.

Suppose $X$ is . Let $g = a_1 a_2 \dots a_n$ be a reduced word in $X$. Define $g_i = a_1 \dots a_i$.

* If $n \geq 2$, then $[\vo, g_{n-2}\vo] \cap [g_{n-1}\vo, g\vo] = \varnothing$.

* If $n \geq 2$, then $[\vo, g_{n-1} \vo] \cap [g_{n-1} \vo, g\vo] = [g_{n-2} \vo, g_{n-1} \vo] \cap [g_{n-1} \vo, g\vo]$, and in particular $\delta(g_{n-1}^{-1}, a_n) = \delta(a_{n-1}^{-1}, a_n)$.

* $\abs{g} = \sum\limits_{i = 1}^n \abs{a_i} - 2\sum\limits_{i = 1}^{n-1} \delta(a_i^{-1}, a_{i+1})$.

We proceed by induction on $n$. The cases $n \leq 2$ are trivial. Suppose $n>2$, as shown in Figure <ref>. By (2) and N3$'$,

\[
\abs{a_{n-1}} - \delta(g_{n-2}^{-1}, a_{n-1}) - \delta(a_{n-1}^{-1}, a_n) = \abs{a_{n-1}} - \delta(a_{n-2}^{-1}, a_{n-1}) - \delta(a_{n-1}^{-1}, a_n) > 0.
\]
By Lemma <ref>,

\[
[\vo, a_{n-2}\vo] \cap [a_{n-2}a_{n-1}\vo, a_{n-2}a_{n-1}a_n\vo] = \varnothing.
\]

If $n=3$, then this proves (1). If $n>3$, then by the induction hypothesis on (2),

\begin{align*}
&[\vo, g_{n-2}\vo] \cap [g_{n-2}\vo, g_{n-1}\vo] \cap [g_{n-1}\vo, g\vo] \\
&= [g_{n-3}\vo, g_{n-2}\vo] \cap [g_{n-2}\vo, g_{n-1}\vo] \cap [g_{n-1}\vo, g\vo] \\ &= \varnothing.
\end{align*}

We therefore have the situation shown in Figure <ref>, proving (1) and (2). By Definition <ref>,

\[
\abs{g} = \abs{g_{n-1}} + \abs{a_n} - 2\delta(g_{n-1}^{-1}, a_n) = \abs{g_{n-1}} + \abs{a_n} - 2\delta(a_{n-1}^{-1}, a_n),
\]

from which (3) follows by induction.

The path of $g = a_1 \dots a_n$.

From this we obtain a key result:

If $X$ is , then $G$ is purely hyperbolic, and $X$ is a free basis for $G$.

Let $g = a_1 \dots a_n$ be a non-trivial reduced word in $X$. Since $X$ contains no elliptic elements, we may assume that $n>1$. Define $a_0 = a_n$ and $a_1 = a_{n+1}$. By Lemma <ref> (3) and N3$'$,

\begin{align*}
\abs{g^2} - \abs{g}
&= \sum\limits_{i=1}^n \abs{a_i} - 2\sum\limits_{i=1}^{n-1} \delta(a_i^{-1}, a_{i+1}) - 2\delta(a_n^{-1}, a_1) \\
&= \sum\limits_{i=1}^n \left(\abs{a_i} - \delta(a_{i-1}^{-1}, a_{i}) - \delta(a_i^{-1}, a_{i+1})\right) \\
&> 0.
\end{align*}

By Lemma <ref>, $g$ is hyperbolic and therefore represents a non-trivial element of $G$. By <cit.>, $X$ is a free basis for $G$.

In the remainder of this section we describe and prove the correctness of the reduction algorithm that obtains an set. A straightforward approach to such an algorithm is to apply Nielsen transformations to $X$, replacing $x$ with $xy$ such that $\abs{xy} < \abs{x}$ when possible. However, a “tie-breaker” is needed when $\abs{x} = \abs{xy}$, in particular when $X$ satisfies N2 but violates N3. To this end, we construct a pre-order on $G$ such that for every word $xyz$ in $X^\pm$ in which the path of $y$ is fully cancelled, either the replacement of $x$ by $xy$ or of $z$ by $yz$ will reduce the respective generator under this pre-order.

If $g \in G$, then the initial half of $g$ is the subpath $\half(g)$ of $[\vo, g\vo]$ with initial vertex $\vo$ of length $\floor*{\abs{g}/2}$.

Let $x, y \in X$. If $\delta(x^{-1}, y) \leq \min\{\abs{x}/2, \abs{y}/2\}$ and $\abs{xy} = \abs{x}$, then $\half(x) = \half(xy)$.

Let $w$ be a vertex of $T$ such that $[w, x\vo] = [\vo, x\vo] \cap [x\vo, xy\vo]$, as in Figure <ref>. Then

\[
d(\vo, w) = \abs{x} - \delta(x^{-1}, y) \ge \abs{x}/2 = \abs{xy}/2,
\]

so $\half(x) = \half(xy) \subseteq [\vo, w]$.

The initial half of $x$ and $xy$

Let $P$ be the set of paths in $T$ with initial vertex $\vo$, let $P_0 = \{(\vo)\}$, and for each $i \in \N$ let $P_i$ be the set of paths in $P$ of length $i$. We choose a lexicographic well-ordering $\ltp$ on $P$, via the following construction:
Let $<_0$ be the trivial ordering on $P_0$. Let $v_1 = w_1 = \vo$. For each $i \in \N$, choose a well-ordering $<_i$ on $P_i$ such that $(v_1, \dots, v_{i+1}) <_i (w_1, \dots, w_{i+1})$ if $(v_1, \dots, v_{j+1}) <_j (w_1, \dots, w_{j+1})$ for some $j < i$.

For $p, q \in P$, define $p \ltp q$ if either $\abs{p} < \abs{q}$, or $\abs{p} = \abs{q}$ and $p <_{\abs{p}} q$.

Let $p = (v_1, \dots, v_{i+1})$ and $q = (w_1, \dots, w_{i+1})$ be distinct elements of $P_i$. The ordering of $p$ and $q$ is determined by the choice of ordering of $(v_1, \dots, v_j)$ and $(w_1, \dots, w_j)$, where $j$ is minimal such that $v_j \neq w_j$. This in turn may be constructed from a choice of ordering of $(v_{j-1}, v_j)$ and $(w_{j-1}, w_j) = (v_{j-1}, w_j)$. We conclude the following: If for all vertices $w$ of $T$ we know a well-ordering of the edges incident to $w$, then we can determine $<_i$. This provides a method to implement the well-orderings.

Let $\nset{P} = \Set{A \subseteq P \given \abs{A} = 2}$.

* Define a well-ordering $\prec$ on $\nset{P}$ such that $A \prec B$ if and only if

\[
\min\limits_{<}\left((A \cup B) \setminus (A \cap B)\right) \in A.
\]

* Define a partial order $\prec$ on $G$ such that $g \prec h$ if and only if $\abs{g} = \abs{h}$ and $\{\half(g), \half(g^{-1})\} \prec \{\half(h), \half(h^{-1})\}$.

* Define a pre-order $\leqg$ on $G$ such that $g \leqg h$ if and only if $\{\half(g), \half(g^{-1})\} \preceq \{\half(h), \half(h^{-1})\}$.

Note that $g \ltg h$ if and only if either $\abs{g} < \abs{h}$ or $g \prec h$. Also, $g$ and $h$ are in the same connected component of $\leqg$ if and only if $\{g\vo, g^{-1}\vo\} = \{h\vo, h^{-1}\vo\}$. Hence the induced ordering on the connected components of $\leqg$ is isomorphic to the ordering $\prec$ on $\nset{P}$. Therefore $\leqg$ is a pre-well-ordering of $G$.

Suppose $X$ satisfies . If there exists $x, y, z \in X^\pm$ such that $y \notin \{x^{-1}, z^{-1}\}$ and $\abs{xyz} \leq \abs{x} + \abs{z} - \abs{y}$, then $\delta(x^{-1}, y) = \delta(y^{-1}, z) = \abs{y}/2$.

Since $X$ violates N3, it violates N3$'$; in particular, $\delta(x^{-1}, y) + \delta(y^{-1}, z) \geq \abs{y}$. In addition, by N2$'$, $\max\{\delta(x^{-1}, y), \delta(y^{-1}, z)\} \leq \abs{y}/2$.
Therefore $\delta(x^{-1}, y) = \delta(y^{-1}, z) = \abs{y}/2$.

Algorithm <ref> takes as input $X$, and outputs a basis $X'$ of $G$ that is either or contains a non-trivial elliptic element; it thereby establishes Theorem <ref>.
Finite subset $X$ of $\Aut(T)$
$(\mathit{flag}, X')$ where $\gen{X'} = \gen{X} = G$, $\mathit{flag} = \tt{True}$ if $G$ is purely hyperbolic and $X'$ is a free basis of $G$, and $\mathit{flag} = \tt{False}$ if $X'$ contains an elliptic element
$X' \gets X$

there exists non-trivial elliptic $x \in X'$
$(\texttt{False}, X')$

there exists $x \in X' \cap X'^{-1}$
$X' \gets X' \setminus \{x\}$
there exists $x, y \in X'^\pm$ such that $x \neq y^{-1}$ and $xy \ltg x$
$X' \gets X' \setminus \{x, x^{-1}\} \cup \{xy\}$

$(\texttt{True}, X')$

Decide whether a finitely generated subgroup of $\Aut(T)$ is purely hyperbolic

A type 2 transformation $x \mapsto x'$

Let $X_i$ be the value of $X'$ during the $i$-th iteration of the loop. If $X_i$ has a non-trivial elliptic element, then we terminate. Suppose $X_i$ has no non-trivial elliptic elements.

* If $X_i$ violates N1, then there is some $x \in X_i \cap X_i^{-1}$. In this case, we assign $X_{i+1} = X_i \setminus \{x\}$.

* If $X_i$ satisfies N1 and violates N2, then there is some $x, y \in X_i^{\pm}$ with $x \neq y^{-1}$ such that $\abs{xy} < \abs{x}$ (as in Figure <ref>). Since $x$ is hyperbolic, by Proposition <ref> $x \neq y$, so we replace $x$ by $xy$.

* Suppose $X_i$ satisfies N1 and N2, and violates N3. Let $x, y, z \in X_i^{\pm}$ be such that $y \notin \{x^{-1}, z^{-1}\}$ and $\abs{xyz} \leq \abs{x} + \abs{z} - \abs{y}$. Define

\[
p = [\vo, y\vo] \cap [\vo, x^{-1}\vo],
\qquad q = [\vo, y^{-1}\vo] \cap [\vo, z\vo],
\]

so that $\abs{p} = \delta(x^{-1}, y)$ and $\abs{q} = \delta(y^{-1}, z)$, as in Figure <ref>. Note that the right diagram is isometric to the left diagram via multiplication by $y^{-1}$, and contains an isometric copy of Figure <ref>. By Lemma <ref> and N2$'$,

\[
\abs{p}=\abs{q} = \abs{y}/2 \leq \min\left\{\floor*{\frac{\abs{x}}{2}}, \floor*{\frac{\abs{z}}{2}}\right\}.
\]

From Figure <ref> we see that $\abs{xy} = \abs{x}$ and $\abs{yz} = \abs{z}$.
Hence $xp = [\vo, x\vo] \cap [x\vo, xy\vo]$ and $xyq = [x\vo, xy\vo] \cap [xy\vo, xyz\vo]$ intersect at a unique point $w$.

Suppose $y=x$. Then $\abs{p} = \abs{x}/2$. By Proposition <ref>, $\abs{x^2} = 2\abs{x} - 2\abs{p} = \abs{x}$, hence $x$ is elliptic. Similarly, if $y=z$, then $z$ is elliptic. If $p = q$, then $x^{-1}w = (xy)^{-1}w$, so $y$ is elliptic. Thus we may assume that $y \notin \{x, z\}$ and $p \neq q$.

By Lemma <ref>, $\half(x) = \half(xy)$ and $\half(z^{-1}) = \half((yz)^{-1})$. Note also that $p$ is an initial segment of both $\half(x^{-1})$ and $\half(yz)$, and $q$ is an initial segment of both $\half((xy)^{-1})$ and $\half(z)$. If $q < p$, then $\half((xy)^{-1}) < \half(x^{-1})$ so $xy \prec x$, and we replace $x$ by $xy$, as in Figure <ref>. Similarly, if $p < q$, then $\half(yz) < \half(z)$ and $yz \prec z$, in which case we replace $z$ by $yz$.

A transformation performed in case 1, 2 or 3 is denoted type 1, 2 or 3 respectively. Case 1 reduces $\abs{X_i}$, so only finitely many transformations are type 1. Cases 2 and 3 reduce some element of $X_i$ with respect to $\ltg$, and does not increase $\abs{X_i}$. Therefore each generator may be replaced only finitely many times, so finitely many transformations can be types 2 and 3. By Proposition <ref>, we either find a non-trivial elliptic element of $G$, or a generating set $X'$ of $G$ that is and therefore a free basis for $G$.

The paths $p$ and $q$

A type 3 transformation $x \mapsto x'$

To prove Theorem <ref> we use a generalisation of Ihara's theorem <cit.>. This proves <cit.> independently of <cit.>.

Let $G$ be a subgroup of $\Aut(T)$.

* If $T$ is locally finite and $G$ is discrete and free, then $G$ is purely hyperbolic.

* If $G$ is purely hyperbolic, then $G$ is discrete and free.

(1) is proved in <cit.>. To prove (2): Freeness is given by the Bass-Serre Theorem <cit.>. Let $(g_i)_{i \in \N}$ be a sequence of elements of $G$ converging to $1$. Since the stabiliser of a vertex is an open neighbourhood of $1$, all but finitely many $g_i$ are trivial, hence $G$ is discrete.

Here is a counterexample to the converse of Proposition <ref> (2), showing the need for local finiteness in (1): Suppose $T$ is regular and $\vo$ has neighbourhood set $\Set{v_i \given i \in \Z}$. Let $g \in \Aut(T)$ be such that $g\vo = \vo$ and $gv_i = v_{i+1}$ for all $i \in \Z$. Now $g$ is elliptic, but $\gen{g}$ is discrete and free.

Suppose $T$ is locally finite. Then $G$ is discrete and free if and only if $G$ is purely hyperbolic, so Algorithm <ref> decides whether $G$ is discrete and free.

§ STRONG

For the rest of the paper we fix a choice of well-orderings $(<_i)_{i \in \N}$, and therefore the orderings in Definitions <ref> and <ref>.

A free basis $X$ for $G$ is strongly  (with respect to $\vo$ and $\leqg$) if $X$ satisfies N1 and:

N4. For all $x, y \in X^{\pm}$, if $x \neq y^{-1}$, then $x \ltg xy$.

We could equivalently write $y \ltg xy$, since $y \ltg xy$ if and only if $y^{-1} \ltg y^{-1}x^{-1}$.

Note that a free basis returned by Algorithm <ref> is strongly . In particular, if $X$ is strongly with respect to $\vo$ and $\leqg$, then it is with respect to $\vo$, since Algorithm <ref> finds an basis.

The following lemmas show that a word in a strongly set is bounded from below (with respect to $\leqg$) by its subwords.

Suppose $X$ is strongly . Let $g = a_1 \dots a_n$ be a reduced word in $X$. For all $1 \leq i \leq j \leq n$, $\abs{g} \geq \abs{a_i \dots a_j}$.

The case $n=1$ is trivial. We may assume $i = 1$ and $j = n-1$: Applying this case to $g^{-1} = a_n^{-1}\dots a_1^{-1}$ proves the case $i=2$ and $j=n$, from which the rest follows by transitivity.

Define $h = a_1\dots a_{n-1}$. By Lemma <ref> (2) and N2$'$,

\[
\abs{g} = \abs{h} + \abs{a_n} - 2\delta(h^{-1}, a_n) = \abs{h} + \abs{a_n} - 2\delta(a_{n-1}^{-1}, a_n) \geq \abs{h}. \qedhere
\]

Suppose $X$ is strongly . Let $g = a_1 \dots a_n$ be a reduced word in $X$. For all $1 \leq i < n$, $\half(a_1 \dots a_i) \subseteq \half(g)$.

By transitivity, we assume $i = n-1$.
Let $h = a_1 \dots a_{n-1}$. By Lemma <ref> (2),

\[
\abs{[\vo, h \vo] \cap [\vo, g\vo]} = \abs{h} - \delta(h^{-1}, a_{n})
= \abs{h} - \delta(a_{n-1}^{-1}, a_{n}).
\]

By N2$'$ and Lemma <ref>,

\[
\abs{h} - \delta(a_{n-1}^{-1}, a_{n}) \geq \abs{h} - \frac{\abs{a_{n-1}}}{2}
\geq \frac{\abs{h}}{2}.
\]

Thus $\half(h) \subseteq [\vo, h \vo] \cap [\vo, g\vo] \subseteq [\vo, g\vo]$. Since $\abs{\half(h)} \leq \abs{\half(g)}$, we conclude that $\half(h) \subseteq \half(g)$.

Suppose $X$ is strongly . Let $g = a_1 \dots a_n$ be a reduced word in $X$. Let $h = a_1 \dots a_i$ for some $1 \leq i < n$. Suppose $\abs{h} = \abs{g} = s$.

* For all $i \leq j \leq n$, $\abs{a_1 \dots a_{j}} = s$.

* $\abs{a_n} \leq \abs{a_{n-1}}$, with strict inequality when $i < n-1$.

* For all $i < j \leq n$, $h \prec a_1 \dots a_j \preceq g$.

(1) follows directly from Lemma <ref>. We now prove (2). By Lemma <ref> (3),

\[
0 = \abs{a_1 \dots a_{n}} - \abs{a_1 \dots a_{n-1}} = \abs{a_n} - 2\delta(a_{n-1}^{-1}, a_n),
\]

so $\delta(a_{n-1}^{-1}, a_n) = \abs{a_n}/2$. By N2$'$, $\abs{a_n} \leq \abs{a_{n-1}}$.
If $i < n-1$ then, by similar reasoning,
\[
\delta(a_{n-2}^{-1}, a_{n-1}) = \abs{a_{n-1}}/2 \geq \delta(a_{n-1}^{-1}, a_n).
\]
By N3$'$,

\[
\abs{a_n} = 2\delta(a_{n-1}^{-1}, a_{n})\leq \delta(a_{n-2}^{-1}, a_{n-1}) + \delta(a_{n-1}^{-1}, a_{n}) < \abs{a_{n-1}}.
\]

Lastly we prove (3). By transitivity, we may assume $i = n-1$ and $j=n$. Let $w \in V(T)$ be such that $[\vo, w] = [\vo, h\vo] \cap [\vo, g\vo]$, as in Figure <ref>. By Lemma <ref> (2) and N2$'$,

\[
d(\vo, w) = \abs{h} - \delta(h^{-1}, a_n) = \abs{h} - \delta(a_{n-1}^{-1}, a_n) \geq \frac{\abs{h}}{2},
\]

so $\half(h) = \half(g)$. We now show that $\half(h^{-1}) < \half(g^{-1})$. By Lemma <ref>, $\half(a_{n-1}^{-1}) \subseteq \half(h^{-1})$ and $\half(a_n^{-1}) \subseteq \half(g^{-1})$. Additionally, by Definition <ref>,

\[
\abs{a_n a_{n-1}} = \abs{a_n} + \abs{a_{n-1}} - 2\delta(a_{n-1}^{-1}, a_n) = \abs{a_{n-1}}.
\]

By Lemma <ref>, $\half(a_{n-1}) = \half(a_{n-1}a_n)$. By N4, $a_{n-1} \prec a_{n-1}a_n$. Thus $\half(a_{n-1}^{-1}) \ltp \half((a_{n-1}a_n)^{-1})$. By Lemma <ref>, $\half((a_{n-1}a_n)^{-1}) \subseteq \half(g^{-1})$, hence $\half(h^{-1}) < \half(g^{-1})$. Therefore $h \prec g$.

The construction for Lemma <ref>

Let $X$ and $Y$ be finite generating sets of a purely hyperbolic subgroup of $\Aut(T)$. If $X$ and $Y$ are strongly (with respect to $\vo$ and $\ltg$), then $X^\pm = Y^\pm$.

We prove this by induction on $n = \max\Set{\abs{g} \given g \in X \cup Y}$. Define
\[
X_{<n} = \Set{g \in X \given \abs{g} < n},\qquad X_{n} = \Set{g \in X \given \abs{g} = n},
\]

and define $Y_{<n}$ and $Y_n$ similarly. By Lemma <ref>, given some $y \in Y_{<n}$, the reduced word for $y$ in $X$ cannot contain an element of $X_n^\pm$, and hence is a word in $X_{<n}$. Similarly, every $x \in X_{<n}$ can be written as a reduced word in $Y_{<n}$. It follows that $\gen{X_{<n}} = \gen{Y_{<n}}$. Note also that $X_{<n}$ and $Y_{<n}$ are strongly . If $n = 1$, then $X_{<n} = Y_{<n} = \varnothing$. Otherwise, by the induction hypothesis $X_{<n}^\pm = Y_{<n}^\pm$.

Let $x \in X_n$ have reduced word $y_1 \dots y_m$ in $Y$. Since $x$ is not represented by a word in $Y_{< n}$, there must be some $y_j \in Y^{\pm}_n$. Suppose for a contradiction that $y_k \in X_{< n}^\pm$ for some $k > j$. By Lemma <ref>, $\abs{y_j \dots y_k \dots y_m} = n$, hence it follows from Lemma <ref> (2) that $y_m \in X_{<n}^\pm$. But Lemma <ref> (3) implies that $x y_m^{-1} \prec x$, contradicting N4. Applying the same argument to $x^{-1}$, we find that $y_k \in Y_n$ for all $1 \leq k \leq m$. By applying Lemma <ref> (2) again to $x$, we conclude that $m \leq 2$.

Suppose $m=2$. Write $x = y y'$, where $y, y' \in Y_{n}^\pm$. Since the words of $y$ and $y'$ in $X_n$ have length at most 2, and $y y'$ reduces to an element of $X_n^\pm$, we may assume (up to inverting $x$) that $y = x'$ and $y' = x'^{-1} x$ for some $x' \in X_n^\pm$. By N4, $y y' = x \prec y'$, which is a contradiction. Therefore $m = 1$ and $x \in Y^\pm$. By symmetry, $X^\pm = Y^\pm$.

As a consequence, we can decide equality of purely hyperbolic subgroups of $\Aut(T)$.

Let $X$ and $Y$ be finite subsets of $\Aut(T)$ generating purely hyperbolic subgroups $G$ and $H$ respectively. There exists an algorithm to decide whether $G = H$.

We use Algorithm <ref> to find strongly free bases $X'$ and $Y'$ for $G$ and $H$ respectively. By Theorem <ref>, $G = H$ if and only if $X'^\pm = Y'^\pm$.

§ THE CONSTRUCTIVE MEMBERSHIP PROBLEM

In this section we present a solution to the constructive membership problem for finitely generated purely hyperbolic subgroups of $\Aut(T)$, by taking advantage of the properties of strongly bases.

Recall that we have fixed a tree $T$, a vertex $\vo$, a lexicographic well-ordering $\ltp$ on the set of paths on $T$ starting from $\vo$ as in Definition <ref>, and a finite subset $X$ of $\Aut(T)$ generating a group $G$.

Let $g\in G$ be hyperbolic. The translation axis of $g$ is $\Ax(g) = \Min(g)$.

Since $g$ acts on $\Ax(g)$ by translation, there is a natural direction associated with the action of $g$ on $\Ax(g)$ such that $g$ and $g^{-1}$ translate in opposite directions. Let $x$ and $y$ be distinct elements of $\Ax(g)$. If $gy$ and $x$ lie in the same connected component of $\Ax(g) \setminus \{y\}$, then $g$ translates $y$ towards $x$. Otherwise, $g$ translates $y$ away from $x$.

The Ping-Pong Lemma is a well-known tool for proving the freeness of a group. We use the following incarnation <cit.>:

Let $X$ be a finite set of hyperbolic automorphisms of $T$. Suppose that for each $g \in X$ there is an open segment $P_g \subseteq \Ax(g)$ of length $l(g)$ such that

\[
\bigcup_{\mathclap{h \in X \setminus \{g\}}}\; \proj_{\Ax(g)}(\Ax(h)) \subseteq P_g.
\]

Then the group $G$ generated by $X$ is free and $X$ is a free basis for $G$.

Given some hyperbolic $g \in \Aut(T)$, let $U^0_g$ be the half-open interval $(u^-_g, u^+_g]$ of $\Ax(g)$ with radius $l(g)/2$ centred at $\proj_{\Ax(g)}(\vo)$, such that $[\vo, u^+_g] < [\vo, u^-_g]$. Let $U^-_g$ and $U^+_g$ be the components of $\Ax(g) \setminus U^0_g$ such that $u^-_g \in U^-_g$. Define $U_g^\pm = U_g^+ \cup U_g^-$. Define $U^0_{g^{-1}} = U^0_g$, $u^+_{g^{-1}} = u^+_g$, and other values similarly. Note that $U_g^+$, $U_g^-$, $u_g^+$, and $u_g^-$ are independent of the direction along which $g$ translates $\Ax(g)$.

Let $g \in \Aut(T)$ be hyperbolic.

* There is a unique $u_g \in \{u_g^+, u_g^-\} \cap [\vo, g\vo]$. Furthermore, $\abs{g} = 2d(\vo, u_g)$.

* $[\vo, g\vo] \cap U_g^{\pm} \neq \varnothing$.

Let $a = \proj_{\Ax(g)}(\vo)$, as in Figure <ref>. We may write $[\vo, g\vo] = [\vo, a] \cup [a, ga] \cup [ga, g\vo]$.
Let $u_g$ be the midpoint of $[a, ga]$. Now $d(a, u_g) = d(u_g, a) = l(g)/2$, and $u_g$ is the unique point of $[a, ga]$ with this property. Hence $\{u_g^+, u_g^-\} \cap [\vo, g\vo] = \{u_g\}$. Also,

\[
\abs{g} = 2d(\vo, a) + 2d(a, u_g) = 2d(\vo, u_g),
\]
proving (1). Since $u_g$ lies in the boundary of $U_g^\pm$, it follows that $ga \in U_g^\pm$, proving (2).

The line segments  $U_g^-$, $U_g^0$, and $U_g^+$

Define $U = \bigcup_{g \in X} \{U^-_g, U^0_g, U^+_g\}$.
If $X$ has no elliptic elements and $\proj_{\Ax(g)}(\Ax(h)) \subseteq U^0_g$ for all $h \in X \setminus \{g\}$, then $U$ is the fundamental system of $X$.

It is clear that if $X$ admits a fundamental system, then $X$ satisfies the hypotheses of the Ping-Pong Lemma, and is therefore a free basis of $G$.

The following lemmas show how paths on $T$ interact with the translation axes of hyperbolic elements of $\Aut(T)$.

Let $w \in T$ and let $g \in \Aut(T)$ be hyperbolic. Define

\[
x = \proj_{\Ax(g)}(\vo), \quad y = \proj_{\Ax(g)}(w), \quad p = [\vo, w] \cap \Ax(g), \quad q = [\vo, gw] \cap \Ax(g).
\]

* If $p = \varnothing$, then $q = [x, gx]$ and $d(\vo, gw) > d(\vo, w) + l(g)$.

* If $p = [x, y]$ and $gy = x$, then $q \in \{\varnothing, \{x\}\}$ and $d(\vo, gw) \leq d(\vo, w) - l(g)$.

* If $p = [x, y]$ and either $x = y$ or $g$ translates $y$ away from $x$, then $q = [x, gy]$ and $d(\vo, gw) = d(\vo, w) + l(g)$.

* If $p = [x, y]$ where $x \notin \{y, gy\}$ and $g$ translates $y$ towards $x$, then $q = [x, gy]$ and $d(\vo, gw) = d(\vo, w) + \abs[\big]{d(x, y) - l(g)} - d(x, y)$.

$p = \varnothing$

$p = [x, g^{-1}x]$

$p = [x, y]$ and $g$ translates $y$ away from $x$

$p = [x, y]$ and $g$ translates $y$ towards $x$

The cases of Lemma <ref>

Let $P$ be the walk $[\vo, x] \oplus p \oplus [y, w]$, where $\oplus$ denotes concatenation. Let $Q$ be the walk $[\vo, x] \oplus q \oplus [gy, gw]$. We see that $\abs{Q} - \abs{P} = \abs{q} - \abs{p}$. Since $g$ translates $y$ along $\Ax(g)$ which is isometric to $\R$, we find that $\abs{q} = \abs[\big]{d(x, y) + a}$, where $a = l(g)$ if $g$ translates $y$ away from $x$, and $a = -l(g)$ if $g$ translates $y$ towards $x$. Therefore

\[
\abs{Q} = \abs{P} + \abs[\big]{d(x, y) + a} - d(x, y).
\]

Note that $\abs{P} \geq d(\vo, w)$ and $\abs{Q} \geq d(\vo, gw)$, with equality if and only if $P = [\vo, w]$ and $Q = [\vo, gw]$ respectively. Figure <ref> depicts each case. We achieve the formulae in cases (1)–(4) by the following substitutions:

* In case (1), $p = \varnothing$ so $P$ backtracks. Thus $\abs{P} > d(\vo, w)$, $Q = [\vo, gw]$, and $d(x, y) = 0$.

* In case (2), $q$ is either empty or a point. It follows that $\abs{Q} \geq d(\vo, gw)$, $P = [\vo, w]$, and $d(x, y ) = l(g) = -a$.

* In cases (3) and (4), $P = [\vo, w]$ and $Q = [\vo, gw]$. The cases are distinguished by whether $a$ is positive or negative.

Let $w \in T$ and let $g \in \Aut(T)$ be hyperbolic. Suppose $[\vo, w] \cap \Ax(g)$ is a path $[x, y]$ for some distinct $x$ and $y$, and that $g$ translates $y$ towards $x$.

* If $d(x, y) > l(g)/2$, then $d(\vo, w) > d(\vo, gw)$.

* If $d(x, y) = l(g)/2$, then $d(\vo, w) = d(\vo, gw)$.

* If $d(x, y) < l(g)/2$, then $d(\vo, w) < d(\vo, gw)$.

If $d(x, y) > l(g)$, then by Lemma <ref> (4),

\[
d(\vo, gw) = d(\vo, w) + \abs{d(x, y) - l(g)} - d(x, y) = d(\vo, w) - l(g) < d(\vo, w).
\]

If $d(x, y) = l(g)$, then by Lemma <ref> (2), $d(\vo, gw) < d(\vo, w)$.
If $d(x, y) < l(g)$, then by Lemma <ref> (4),

\[
d(\vo, gw) = d(\vo, w) + \abs{d(x, y) - l(g)} - d(x, y) = d(\vo, w) + l(g) - 2d(x, y).
\]

We see that $d(\vo, w) \leq d(\vo, gw)$ if and only if $d(x, y) \leq l(g)/2$, with equality when $d(x, y) = l(g)/2$.

Let $w \in T$ and let $g \in \Aut(T)$ be hyperbolic. The following are equivalent:

* $\proj_{\Ax(g)}(w) \in U_g^\pm$.

* $[\vo, w] \cap U_g^\pm \neq \varnothing$.

* $[\vo, g^\e w] < [\vo, w]$ for some $\e \in \{1, -1\}$.

(1) $\Rightarrow$ (2): Suppose $y = \proj_{\Ax(g)}(w) \in U_g^\pm$. Let $x = \proj_{\Ax(g)}(\vo)$. Since $x \in U_g^0$, $[\vo, x]$ and $[y, w]$ are disjoint, so $[\vo, w] = [\vo, x] \cup [x, y] \cup [y, w]$.

(2) $\Rightarrow$ (3): Suppose $[\vo, w] \cap U_g^\pm \neq \varnothing$. Then $[\vo, w] \cap \Ax(g)$ is a path $[x, y]$, where $x = \proj_{\Ax(g)}(\vo)$ and $y \in U_g^\pm$. It follows that $d(x, y) \geq l(g)/2$. We may assume that $g$ translates $y$ towards $x$. By Lemma <ref>, $d(\vo, gw) \leq d(\vo, w)$. If $d(\vo, gw) = d(\vo, w)$, then $d(x, y) = l(g)/2$, so $y = u_g^-$. Therefore $[\vo, gw] < [\vo, w]$.

(3) $\Rightarrow$ (1): Inverting $g$ if necessary, suppose $[\vo, gw] < [\vo, w]$. Now case (2) or (4) of Lemma <ref> must hold, that is $[\vo, w] \cap \Ax(g)$ is a path $[x, y]$ such that $g$ translates $y$ towards $x$. By Lemma <ref>, $d(x, y) \geq l(g)/2$. If $d(x, y) = l(g)/2$, then $y \in \{u_g^+, u_g^-\}$ and $[\vo, gy] < [\vo, y]$, so $y = u_g^-$. In either case, $\proj_{\Ax(g)}(w) = y \in U_g^\pm$.

Suppose $X$ contains no elliptic elements and satisfies . Then $X$ admits a fundamental system if and only if for all $g, h \in X^\pm$, if $g \neq h^{-1}$, then $[\vo, h\vo] < [\vo, gh\vo]$.

Suppose $[\vo, gh\vo] \leq [\vo, h\vo]$ for some $g, h \in X^\pm$ with $g \neq h^{-1}$. If $[\vo, gh\vo] = [\vo, h\vo]$, then $h^{-1}gh\vo = \vo$, so $g$ is elliptic. Hence $[\vo, gh\vo] < [\vo, h\vo]$. Let $a = \proj_{\Ax(g)}(h\vo)$. By Lemma <ref>, $a \in [\vo, h\vo] \cap U_g^\pm$. Let $b \in [\vo, h\vo] \cap U_h^\pm$. We see that either $a \in [\vo, b]$ or $b \in [\vo, a]$. By Lemma <ref>, either $\proj_{\Ax(g)}(b) \in U_g^\pm$ or $\proj_{\Ax(h)}(a) \in U_h^\pm$. Therefore $X$ does not admit a fundamental system.

Conversely, suppose $X$ does not admit a fundamental system. By Lemma <ref>, there exists distinct $g, h \in X$ and $a \in U_g^\pm$, $b \in U_h^\pm$ such that $a \in [\vo, b]$, for example as in Figure <ref>. Inverting $g$ and $h$ if necessary, let

\[
a' \in [\vo, b] \cap [\vo, g\vo] \cap U_g^{\pm}, \qquad b' \in [\vo, b] \cap [\vo, h\vo] \cap U_h^\pm.
\]

Both $a'$ and $b'$ must exist, since both $[\vo, b]$ and $[\vo, g\vo]$ intersect the boundary of $U_g^\pm$, and similarly for $h$.
We may assume (swapping $g$ and $h$ if necessary) that $a' \in [\vo, b']$. Then $a' \in [\vo, h\vo]$ so, by Lemma <ref>, $[\vo, g^\e h\vo] < [\vo, h\vo]$ for some $\e \in \{1, -1\}$.

One construction for Lemma <ref>

$X$ is strongly if and only if $X$ admits a fundamental system.

We may assume $X$ contains no elliptic elements and satisfies N1.
Suppose $X$ is strongly . Let $g, h \in X^\pm$ such that $g \neq h^{-1}$. By Lemma <ref>, it suffices to show that $[\vo, h\vo] < [\vo, gh\vo]$. This holds by definition if $\abs{h} < \abs{gh}$, so suppose otherwise. By N4, $\abs{h} = \abs{gh}$. We apply Lemma <ref> to $h^{-1}$ and $g^{-1}$. From N2$'$ and this application we conclude that $\half(h^{-1}) = \half(h^{-1}g^{-1})$. By N4, $\half(h) < \half(gh)$. Therefore $[\vo, h\vo] < [\vo, gh\vo]$.

Conversely, suppose $X$ is not strongly . If there exists $g, h \in X^{\pm}$ such that $g \neq h^{-1}$ and $\abs{gh} < \abs{h}$, then $[\vo, gh\vo] < [\vo, h\vo]$. Otherwise, suppose $X$ satisfies N2 and violates N4. Then there exists $g, h \in X^\pm$ such that $\abs{gh} = \abs{h}$ and $gh \prec h$. By a similar argument to the forward direction, $\half(gh) < \half(h)$, so $[\vo, gh\vo] < [\vo, h\vo]$. By Lemma <ref>, $X$ does not admit a fundamental system.

Every finitely generated purely hyperbolic subgroup of $\Aut(T)$ admits a unique fundamental system.

Existence follows from Algorithm <ref> and Theorem <ref>; uniqueness follows from Theorem <ref>.

A fundamental domain of $G$ is a subtree of $T$ containing exactly one vertex from every orbit of $G$ <cit.>.

Suppose $G$ admits a fundamental system $U$. Define $\Gamma(G)$ to be the subtree of $T$ with vertex set

\[
\Set{w \in V(T) \given \proj_{\Ax(g)}(w) \in U^0_g \text{ for all } g \in X}.
\]

We show that $\Gamma(G)$ is a fundamental domain of $G$; see Corollary <ref>.

Suppose $X$ is strongly . For each vertex $w$ of $T$ there is at most one $g \in X$ such that $\proj_{\Ax(g)}(w) \notin U^0_g$.

Let $g, h \in X$ be distinct. Let $a = \proj_{\Ax(g)}(w)$ and $b = \proj_{\Ax(h)}(w)$. Suppose $a \in U_g^\pm$ and $b \in U_h^\pm$. By Lemma <ref>, $a$ and $b$ are both in $[\vo, w]$, so either $a \in [\vo, b]$ or $b \in [\vo, a]$. By Lemma <ref> and Theorem <ref>, $X$ is not strongly .

Suppose $X$ is strongly . Let $w \in V(T)$. The following are equivalent:

* $w \in \Gamma(G)$.

* $[\vo, w] \ltp [\vo, xw]$ for all $x \in X^\pm$.

* $[\vo, w] \ltp [\vo, gw]$ for all $g \in G \setminus \{1\}$.

The equivalence of $(1)$ and $(2)$ is given directly by Lemma <ref>, and (3) $\Rightarrow$ (2) is trivial. We now prove $(2) \Rightarrow (3)$. Suppose $[\vo, w] \ltp [\vo, xw]$ for all $x \in X^\pm$, or equivalently $w \in \Gamma(G)$. Let $g = x_n^{\e_n} \dots x_1^{\e_1}$, where each $x_i \in X$, $\e_i \in \Z \setminus \{0\}$, and $x_i \neq x_{i+1}$. Let $h = x_{n-1}^{\e_{n-1}} \dots x_{1}^{\e_1}$ and if $n \geq 2$, then let $h' = x_{n-2}^{\e_{n-2}} \dots x_{1}^{\e_1}$. By transitivity, it suffices to show that $[\vo, hw] < [\vo, gw]$. We proceed by induction on $n$.

First we show that $\proj_{\Ax(x_n)}(hw) \in U_{x_n}^0$.
If $n=1$, then $h$ is trivial, so the statement holds by Lemma <ref>. Suppose $n > 1$.
Note that $U_{x_i}^0 \subseteq U_{x_i^{\e_i}}^0$ and $U_{x_i^{\e_i}}^\pm \subseteq U_{x_i}^\pm$ for all $i$, since $\Ax(x_i) = \Ax(x_i^{\e_i})$ and $U_{x_i^{\e_i}}^0$ has length $l(x_i^{\e_i}) \geq l(x_i)$.
Additionally, by the induction hypothesis $[\vo, h'w] < [\vo, hw]$. By Lemma <ref>,

\[
\proj_{\Ax(x_{n-1})}(hw) \in U_{x_{n-1}^{\e_{n-1}}}^\pm \subset U_{x_{n-1}}^\pm.
\]

By Lemma <ref>, $\proj_{\Ax(x_n)}(hw) \in U_{x_n}^0$, as desired.

It follows that $\proj_{\Ax(x_n)}(hw) \in U_{x_n^{\e_n}}^0$. By Lemma <ref>, $[\vo, hw] < [\vo, gw]$, completing the proof.

$\Gamma(G)$ has vertex set $\Set{w \in V(T) \given [\vo, w] \ltp [\vo, gw] \text{ for all } g \in G \setminus \{1\}}$. In particular, $\Gamma(G)$ is a fundamental domain of $G$.

Let $u \in V(T)$. There must be some unique $g \in G$ minimising $[\vo, gu]$, since $\ltp$ is a well-ordering. By Proposition <ref>, $gu$ is the unique element of $Gu$ in $\Gamma(G)$.

$\Gamma(G)$ is closely related to the Dirichlet fundamental domain <cit.>. However, a Dirichlet fundamental domain is not necessarily a fundamental domain, since it also contains each vertex $w$ of $T$ such that $\proj_{\Ax(g)}(w) = u_g^+$ for some $g \in X$.

Given $w \in V(T)$, Algorithm <ref> finds the unique $g \in G$ such that $gw \in \Gamma(G)$.
Finite strongly subset $X$ of $\Aut(T)$, $w \in V(T)$
The unique $g \in G=\gen{X}$ such that $gw \in \Gamma(G)$
$g \gets 1$
there exists $x \in X^{\pm}$ such that $[\vo, xgw] \ltp [\vo, gw]$
$g \gets xg$

Find $g \in G$ mapping vertex to fundamental domain

Let $a = \proj_{\Ax(g)}(w)$.
Suppose $w \notin \Gamma(G)$. By Proposition <ref>, there is some $x \in X^\pm$ such that $[\vo, xw] < [\vo, w]$. We thus obtain a sequence $w = w_0, w_1 \dots$, where $w_i = x_i w_{i-1}$ for some $x_i \in X^\pm$ and $[\vo, w_i] < [\vo, w_{i-1}]$ for each $i$. Eventually this sequence must terminate, so we find some $w_n = x_n \dots x_1 w$ such that $[\vo, w_n] < [\vo, xw_n]$ for all $x \in X^\pm$. By Proposition <ref>, $w_n \in \Gamma(G)$.

As a corollary, we obtain the following:

Let $g \in \Aut(T)$. We wish to decide whether $g \in G$, and if so write $g$ as a word in $X$.
We may assume $X$ is strongly , since by keeping track of the transformations involved in Algorithm <ref> we may write each word in a strongly basis of $G$ as a word in $X$.
Using Algorithm <ref>, we find the unique $h \in G$, and a reduced word of $h$ in $X$, such that $hg\vo \in \Gamma(G)$. It follows that $g \in G$ if and only if $g = h^{-1}$.

The proof of Theorem <ref> provides an alternative algorithm for Corollary <ref>: If $X$ and $Y$ are strongly , then $\gen{X} = \gen{Y}$ if and only if $x \in \gen{Y}$ and $y \in \gen{X}$ for all $x \in X$ and $y \in Y$. However, we included the first algorithm to show that deciding equality of these groups is easier than Theorem <ref> would imply.

§ IMPLEMENTATION AND PERFORMANCE

We implemented in Magma [2] our algorithms for $\PGL_2(K)$, where $K$ is a $p$-adic field, acting on the Bruhat-Tits tree [13]. This package implements Algorithms <ref>, <ref>, and the algorithms given in the proofs of Corollary <ref> and Theorem <ref>. In our implementation, $X$ is input as a sequence rather than a set, since this simplifies the code.

Table <ref> shows the runtime of Algorithm <ref>, and the average time per iteration of the loop, for different values of $\abs{X}$. The trials are run with randomly chosen elements of $\SL_2(\Q_5)$ with 1000 digits of precision, where each entry has valuation at most 10. Changing the choice of prime $p$ and the precision did not seem to significantly affect the runtime. The times shown are averaged over 1000 trials.

Increasing the maximum valuation of entries of the generators rapidly leads to the algorithm losing precision, so we do not run trials over a range of maximum valuations.

Tables <ref> and <ref> show runtimes of Algorithm <ref>. Recall that Algorithm <ref> takes as input a strongly subset of $\Aut(T)$ and a vertex of $T$. We record the average runtime over all pairings of 100 strongly generating sets and 100 vertices.
For Table <ref> we vary $\abs{X}$ and choose $w$ such that $d(w, \vo) = 100$, and for
Table <ref> we vary $d(w, \vo)$ and set $\abs{X} = 5$. The code used for these tests is provided in [13]. The trials were run using Magma V2.28-2 on a 2.6GHz machine.

$\abs{X}$     Average time (seconds)     Average time / iteration (seconds)

2     0.03     0.01

5     0.80     0.07

10     3.06     0.18

100     10.87     0.97

Runtimes of Algorithm <ref> for different numbers of generators

$\abs{X}$     Average time (seconds)

2     0.04

3     0.06

5     0.10

10     0.21

Runtimes of Algorithm <ref> for different numbers of generators

$d(w, \vo)$     Average time (seconds)

5     0.01

10     0.02

20     0.03

50     0.05

100     0.10

Runtimes of Algorithm <ref> for various distances of $w$ from $\vo$

[1]
A. F. Beardon.
The geometry of discrete groups, volume 91 of Graduate
Texts in Mathematics.
Springer-Verlag, New York, 1995.
Corrected reprint of the 1983 original.

[2]
W. Bosma, J. Cannon, and C. Playoust.
The Magma algebra system. I. The user language.
J. Symbolic Comput., 24(3-4):235–265, 1997.
Computational algebra and number theory (London, 1993).

[3]
M. J. Conder.
Discrete and free two-generated subgroups of $\rm SL_2$ over
non-archimedean local fields.
J. Algebra, 553:248–267, 2020.

[4]
M. J. Conder.
Discrete and free groups acting on locally finite trees.
J. Algebra, 597:162–189, 2022.

[5]
B. Eick, M. Kirschmer, and C. Leedham-Green.
The constructive membership problem for discrete free subgroups of
rank 2 of $\SL(2, \R)$.
LMS J. Comput. Math., 17(1):345–359, 2014.

[6]
A. Garrido, Y. Glasner, and S. Tornier.
Automorphism groups of trees: generalities and prescribed local
In New directions in locally compact groups, volume 447 of London Math. Soc. Lecture Note Ser., pages 92–116. Cambridge Univ. Press,
Cambridge, 2018.

[7]
J. Gilman.
Two-generator discrete subgroups of $\PSL(2,\R)$.
Mem. Amer. Math. Soc., 117(561):x+204, 1995.

[8]
A. H. M. Hoare.
Nielsen methods in groups with a length function.
Math. Scand., 48(2):153–164, 1981.

[9]
I. Kapovich and R. Weidmann.
Nielsen methods and groups acting on hyperbolic spaces.
Geom. Dedicata, 98:95–121, 2003.

[10]
M. Kirschmer and M. G. Rüther.
The constructive membership problem for discrete two-generator
subgroups of ${\rm SL}_2(\mathbb{R})$.
J. Algebra, 480:519–548, 2017.

[11]
A. Lubotzky.
Lattices in rank one Lie groups over local fields.
Geom. Funct. Anal., 1(4):406–431, 1991.

[12]
R. C. Lyndon and P. E. Schupp.
Combinatorial group theory.
Classics in Mathematics. Springer-Verlag, Berlin, 2001.
Reprint of the 1977 edition.

[13]
A. Markowitz.

[14]
B. Maskit.
Kleinian Groups.
Grundlehren der mathematischen Wissenschaften. Springer-Verlag,
Berlin, 1987.

[15]
D. Mumford.
An analytic construction of degenerating curves over complete local
Compositio Math., 24:129–174, 1972.

[16]
N. Purzitsky.
Two-generator discrete free products.
Math. Z., 126:209–223, 1972.

[17]
J.-P. Serre.
Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2003.
Translated from the French original by John Stillwell, Corrected 2nd
printing of the 1980 English translation.

[18]
R. Weidmann.
The Nielsen method for groups acting on trees.
Proc. London Math. Soc. (3), 85(1):93–118, 2002.


# Learning Context-Sensitive Convolutional Filters for Text Processing

Dinghan Shen1, Martin Renqiang Min2, Yitong Li1, Lawrence Carin1
1 Duke University 2 NEC Laboratories America
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Convolutional neural networks (CNNs) have recently emerged as a popular
building block for natural language processing (NLP). Despite their success,
most existing CNN models employed in NLP share the same learned (and static)
set of filters for all input sentences. In this paper, we consider an approach
of using a small _meta network_ to learn context-sensitive convolutional
filters for text processing. The role of meta network is to abstract the
contextual information of a sentence or document into a set of _input-aware_
filters. We further generalize this framework to model sentence pairs, where a
_bidirectional_ filter generation mechanism is introduced to encapsulate co-
dependent sentence representations. In our benchmarks on four different tasks,
including ontology classification, sentiment analysis, answer sentence
selection, and paraphrase identification, our proposed model, a modified CNN
with context-sensitive filters, consistently outperforms the standard CNN and
attention-based CNN baselines. By visualizing the learned _context-sensitive_
filters, we further validate and rationalize the effectiveness of proposed
framework.

##  1 Introduction

In the last few years, convolutional neural networks (CNNs) have demonstrated
remarkable progress in various natural language processing applications
Collobert et al. (2011), including sentence/document classification (Kim,
2014; Zhang et al., 2015; Wang et al., 2018), text sequence matching (Hu et
al., 2014; Yin et al., 2016; Shen et al., 2017), generic text representations
(Gan et al., 2016; Tang et al., 2018), language modeling (Dauphin et al.,
2017), machine translation (Gehring et al., 2017) and abstractive sentence
summarization (Gehring et al., 2017). CNNs are typically applied to tasks
where feature extraction and a corresponding supervised task are approached
jointly (LeCun et al., 1998). As an encoder network for text, CNNs typically
convolve a set of filters, of window size $n$, with an input-sentence
embedding matrix obtained via _word2vec_ (Mikolov et al., 2013) or Glove
(Pennington et al., 2014). Different filter sizes $n$ may be used within the
same model, exploiting meaningful semantic features from different $n$-gram
fragments.

The learned weights of CNN filters, in most cases, are assumed to be fixed
regardless of the input text. As a result, the rich contextual information
inherent in natural language sequences may not be fully captured. As
demonstrated in Cohen and Singer (1999), the context of a word tends to
greatly influence its contribution to the final supervised tasks. This
observation is consistent with the following intuition: when reading different
types of documents, _e.g._ , academic papers or newspaper articles, people
tend to adopt distinct strategies for better and more effective understanding,
leveraging the fact that the same words or phrases may have different meaning
or imply different things, depending on context.

Several research efforts have sought to incorporate _contextual information_
into CNNs to adaptively extract text representations. One common strategy is
the _attention mechanism_ , which is typically employed on top of a CNN (or
Long Short-Term Memory (LSTM)) layer to guide the extraction of semantic
features. For the embedding of a single sentence, Lin et al. (2017) proposed a
self-attentive model that attends to different parts of a sentence and
combines them into multiple vector representations. However, their model needs
considerably more parameters to achieve performance gains over traditional
CNNs. To match sentence pairs, Yin et al. (2016) introduced an attention-based
CNN model, which re-weights the convolution inputs or outputs, to extract
interdependent sentence representations. Wang et al. (2016); Wang and Jiang
(2017) explore a _compare and aggregate_ framework to directly capture the
word-by-word matching between two paired sentences. However, these approaches
suffer from the problem of high matching complexity, since a similarity matrix
between pairwise words needs to be computed, and thus it is computationally
inefficient or even prohibitive when applied to long sentences (Mou et al.,
2016).

In this paper, we propose a generic approach to learn _context-sensitive_
convolutional filters for natural language understanding. In contrast to
traditional CNNs, the convolution operation in our framework does not have a
fixed set of filters, and thus provides the network with stronger modeling
flexibility and capacity. Specifically, we introduce a _meta network_ to
generate a set of context-sensitive filters, conditioned on specific input
sentences; these filters are adaptively applied to either the same (Section
3.2) or different (Section 3.3) text sequences. In this manner, the learned
filters vary from sentence to sentence and allow for more fine-grained feature
abstraction.

Moreover, since the generated filters in our framework can adapt to different
conditional information available (labels or paired sentences), they can be
naturally generalized to model sentence pairs. In this regard, we propose a
novel _bidirectional_ filter generation mechanism to allow interactions
between sentence pairs while constructing _context-sensitive_ representations.

We investigate the effectiveness of our Adaptive Context-sensitive CNN (ACNN)
framework on several text processing tasks: ontology classification, sentiment
analysis, answer sentence selection and paraphrase identification. We show
that the proposed methods consistently outperforms the standard CNN and
attention-based CNN baselines. Our work provides a new perspective on how to
incorporate contextual information into text representations, which can be
combined with more sophisticated structures to achieve even better performance
in the future.

##  2 Related Work

Learning deep text representations has attracted much attention recently,
since they can potentially benefit a wide range of NLP applications (Collobert
et al., 2011; Kim, 2014; Wang et al., 2017a; Shen et al., 2018a; Tang and de
Sa, 2018; Zhang et al., 2018). CNNs have been extensively investigated as the
encoder networks of natural language. Our work is in line with previous
efforts on improving the adaptivity and flexibility of convolutional neural
networks (Jeon and Kim, 2017; De Brabandere et al., 2016). Jeon and Kim (2017)
proposed to enhance the transformation modeling capacity of CNNs by adaptively
learning the filter shapes through backpropagation. De Brabandere et al.
(2016) introduced an architecture to generate the future frames conditioned on
given image(s), by adapting the CNN filter weights to the motion within
previous video frames. Although CNNs have been widely adopted in a large
number of NLP applications, improving the adaptivity of vanilla CNN modules
has been considerably less studied. To the best of our knowledge, the work
reported in this paper is the first attempt to develop more flexible and
adjustable CNN architecture for modeling sentences.

Our use of a meta network to generate parameters for another network is
directly inspired by the recent success of hypernetworks for text-generation
tasks (Ha et al., 2017), and dynamic parameter-prediction for video-frame
generation (De Brabandere et al., 2016). In contrast to these works that focus
on generation problems, our model is based on context-sensitive CNN filters
and is aimed at abstracting more informative and predictive sentence features.
Most similar to our work, Liu et al. (2017) designed a meta network to
generate compositional functions over tree-structured neural networks for
encapsulating sentence features. However, their model is only suitable for
encoding individual sentences, while our framework can be readily generalized
to capture the interactions between sentence pairs. Moreover, our framework is
based on CNN models, which is advantageous due to fewer parameters and highly
parallelizable computations relative to sequential-based models.

##  3 Model

###  3.1 Basic CNN for text representations

The CNN architectures in (Kim, 2014; Collobert et al., 2011) are typically
utilized for extracting sentence representations, by a composition of a
convolutional layer and a _max-pooling_ operation over all resulting feature
maps. Let the words of a sentence of length $T$ (padded where necessary) be
${x}_{1}$, ${x}_{2}$, $...$ , ${x}_{T}$. The sentence can be represented as a
matrix $\boldsymbol{X}\in\mathbb{R}^{d\times T}$, where each column represents
a $d$-dimensional embedding of the corresponding word.

In the convolutional layer, a set of filters with weights
$\boldsymbol{W}\in\mathbb{R}^{K\times h\times d}$ is convolved with every
window of $h$ words within the sentence, _i.e._ ,
$\left\\{{x}_{1:h},{x}_{2:h+1},\ldotp\ldotp\ldotp,{x}_{T-h+1:T}\right\\}$,
where $K$ is the number of output feature maps (and filters). In this manner,
feature maps $\boldsymbol{p}$ for these $h$-gram text fragments are generated
as:

$\displaystyle\boldsymbol{p}_{i}=f(\boldsymbol{W}\times x_{i:i+h-1}+b)\,$ (1)

where $i=1,2,...,T-h+1$ and $\times$ denotes the convolution operator at the
$i$th shift location. Parameter $b\in\mathbb{R}^{K}$ is the bias term and
$f(\cdot)$ is a non-linear function, implemented as a rectified linear unit
(ReLU) in our experiments. The output feature maps of the convolutional layer,
_i.e._ , $\boldsymbol{p}\in\mathbb{R}^{K\times(T-h+1)}$ are then passed to the
pooling layer, which takes the maximum value in every row of $\boldsymbol{p}$,
forming a $K$-dimensional vector, $\boldsymbol{z}$. This operation attempts to
keep the most salient feature detected by every filter and discard the
information from less fundamental text fragments. Moreover, the _max-over-
time_ nature of the pooling operation (Collobert et al., 2011) guarantees that
the size of the obtained representation is independent of the sentence length.

Note that in basic CNN sentence encoders, filter weights are the same for
different inputs, which may be suboptimal for feature extraction (De
Brabandere et al., 2016), especially in the case where conditional information
is available.

###  3.2 Learning context-sensitive filters

The proposed architecture to learn context-sensitive filters is composed of
two principal modules: (_i_) a filter generation module, which produces a set
of filters conditioned on the input sentence; and (_ii_) an adaptive
convolution module, which applies the generated filters to an input sentence
(this sentence may be either the same as or different from the first input, as
discussed further in Section 3.3). The two modules are jointly differentiable,
and the overall architecture can be trained in an end-to-end manner. Since the
generated filters are sample-specific, our ACNN feature extractor for text
tends to have stronger predictive power than a basic CNN encoder. The general
ACNN framework is shown schematically in Figure 1.

Figure 1: The general ACNN framework. Notably, the input sentences to filter
generating module and convolution module could be different (see Section 3.3).

#### Filter generation module

Instead of utilizing fixed filter weights $\boldsymbol{W}$ for different
inputs (as (1)), our model generates a set of filters conditioned on the input
sentence $\boldsymbol{X}$. Given an input $\boldsymbol{X}$, the filter-
generation module can be implemented, in principle, as any deep
(differentiable) architecture. However, in order to handle input sentences of
variable length common in natural language, we design a generic filter
generation module to produce filters with a predefined size.

First, the input $\boldsymbol{X}$ is encapsulated into a fixed-length vector
(code) $\boldsymbol{z}$ with the dimension of $l$, via a basic CNN model,
where one convolutional layer is employed along with the pooling operation (as
described in Section 3.1). On top of this hidden representation
$\boldsymbol{z}$, a deconvolutional layer, which performs transposed
operations of convolutions Radford et al. (2016), is further applied to
produce a unique set of filters for $\boldsymbol{X}$ (as illustrated in Figure
1):

$\displaystyle\boldsymbol{z}=$ $\displaystyle\
\textbf{{CNN}}(\boldsymbol{X};\boldsymbol{\theta}_{e}),$ (2)
$\displaystyle\boldsymbol{f}=$ $\displaystyle\
\textbf{{DCNN}}(\boldsymbol{z};\boldsymbol{\theta}_{d})\,,$ (3)

where $\boldsymbol{\theta}_{e}$ and $\boldsymbol{\theta}_{d}$ are the learned
parameters in each layer of the filter-generating module, respectively.
Specifically, we convolve $\boldsymbol{z}$ with a filter of size ($f_{s}$,
$l$, $k_{x}$, $k_{y}$), where $f_{s}$ is the number of generated filters and
the kernel size is ($k_{x}$, ${k_{y}}$). The output will be a tensor of shape
(${f_{s}}$, ${k_{x}}$, ${k_{y}}$). Since the dimension of hidden
representation $\boldsymbol{z}$ is independent of input-sentence length, this
framework guarantees that the generated filters are of the same shape and size
for every sentence. Intuitively, the encoding part of filter generation module
abstracts the information from sentence $\boldsymbol{X}$ into
$\boldsymbol{z}$. Based on this representation, the deconvolutional up-
sampling layer determines a set of fixed-size, fine-grained filters
$\boldsymbol{f}$ for the specific input.

#### Adaptive convolution module

The adaptive convolution module takes as inputs the generated filters
$\boldsymbol{f}$ and an input sentence. This sentence and the input to the
filter-generation module may be identical (as in Figure 1) or different (as in
Figure 2). With the sample-specific filters, the input sentence is adaptively
encoded, again, via a basic CNN architecture as in Section 3.1, _i.e._ , one
convolutional and one pooling layer. Notably, there are no additional
parameters in the adaptive convolution module (no bias term is employed).

Our ACNN framework can be seen as a generalization of the basic CNN, which can
be represented as an ACNN by setting the outputs of the filter-generation
module to a constant, regardless of the contextual information from input
sentence(s). Because of the learning-to-learn (Thrun and Pratt, 2012) nature
of the proposed ACNN framework, it tends to have greater representational
power than the basic CNN.

###  3.3 Extension to text sequence matching

Considering the ability of our ACNN framework to generate context-sensitive
filters, it can be naturally generalized to the task of text sequence
matching. In this section, we will describe the proposed Adaptive Question
Answering (AdaQA) model in the context of answer sentence selection task. Note
that the corresponding model can be readily adapted to other sentence matching
problems as well (see Section 5.2).

Given a factual question $q$ (associated with a list of candidate answers
$\left\\{{a_{1},a_{2},\ldotp\ldotp\ldotp,a_{m}}\right\\}$ and their
corresponding labels
$\boldsymbol{y}=\left\\{{y_{1},y_{2},\ldotp\ldotp\ldotp,y_{m}}\right\\}$), the
goal of the model is to identify the correct answers from the set of
candidates. For $i$ = $1,2,\ldotp\ldotp\ldotp,m$, if $a_{i}$ correctly answers
$q$, then $y_{i}=1$, and otherwise $y_{i}=0$. Therefore, the task can be cast
as a classification problem where, given an unlabeled question-answer pair
$(q_{i},a_{i})$, we seek to predict the judgement $y_{i}$.

Figure 2: Schematic description of Adaptive Question Answering (AdaQA) model.

Conventionally, a question $q$ and an answer $a$ are independently encoded by
two basic CNNs to fixed-length vector representations, denoted
$\boldsymbol{h}_{q}$ and $\boldsymbol{h}_{a}$, respectively. They are then
directly employed to predict the judgement $\boldsymbol{y}$. This strategy
could be suboptimal, since no communication (information sharing) occurs
between the question-answer pair until the top prediction layer. Intuitively,
while the model is inferring the representation for a question, if the meaning
of the answer is taken into account, those features that are relevant for
final prediction are more likely to be extracted. So motivated, we propose an
adaptive CNN-based question-answer (AdaQA) model for this problem. The AdaQA
model can be divided into three modules: filter generation, adaptive
convolution, and matching modules, as depicted schematically in Figure 2.
Assume there is a question-answer pair to be matched, represented by word-
embedding matrices, _i.e._ $\boldsymbol{Q}\in\mathbb{R}^{T_{q}\times d}$ and
$\boldsymbol{A}\in\mathbb{R}^{T_{a}\times d}$, where $d$ is the embedding
dimension and $T_{q}$ and $T_{a}$ are respective sentence lengths. First, they
are passed to two filter-generation modules, to produce two sets of filters
that encapsulate features of the corresponding input sentences. Similar to the
setup in Section 3.2, we also employ a two-step process to produce the
filters. For a question $\boldsymbol{Q}$, the generating process is:

$\displaystyle\vspace{-8mm}\boldsymbol{z}_{q}=$ $\displaystyle\
\textbf{{CNN}}(\boldsymbol{Q};\boldsymbol{\theta}_{e}^{q}),$ (4)
$\displaystyle\boldsymbol{f}_{q}=$ $\displaystyle\
\textbf{{DCNN}}(\boldsymbol{z}_{q};\boldsymbol{\theta}_{d}^{q})\,\vspace{-8mm}$
(5)

where CNN and DCNN denote the basic CNN unit and deconvolution layer,
respectively, as discussed in Section 2.1. Parameters
$\boldsymbol{\theta}_{e}^{q}$ and $\boldsymbol{\theta}_{d}^{q}$ are to be
learned. The same process can be utilized to produce encodings
$\boldsymbol{z}_{a}$ and filters $\boldsymbol{f}_{a}$ for the answer input,
$\boldsymbol{A}$, with parameters $\boldsymbol{\theta}_{e}^{a}$ and
$\boldsymbol{\theta}_{d}^{a}$, respectively.

The two sets of filter weights are then passed to adaptive convolution
modules, along with $\boldsymbol{Q}$ and $\boldsymbol{A}$, to obtain the
extracted question and answer embeddings. That is, the question embedding is
convolved with the filters produced by the answer and _vise versa_
($\boldsymbol{\psi}_{q}$ and $\boldsymbol{\psi}_{a}$ are the bias terms to be
learned). The key idea is to abstract information from the answer (or
question) that is pertinent to the corresponding question (or answer).
Compared to a Siamese CNN architecture (Bromley et al., 1994), our model
selectively encapsulates the most important features for judgement prediction,
removing less vital information. We then employ the question and answer
representations $\boldsymbol{h}_{q}\in\mathbb{R}^{n_{h}}$,
$\boldsymbol{h}_{a}\in\mathbb{R}^{n_{h}}$ as inputs to the matching module
(where $n_{h}$ is the dimension of question/answer embeddings). Following Mou
et al. (2016), the matching function is defined as:

$\displaystyle\boldsymbol{t}=[\boldsymbol{h}_{q};\boldsymbol{h}_{a};\boldsymbol{h}_{q}-\boldsymbol{h}_{a};\boldsymbol{h}_{q}\odot\boldsymbol{h}_{a}]$
(6) $\displaystyle
p(\boldsymbol{y}=1|\boldsymbol{h}_{q},\boldsymbol{h}_{a})=\textbf{{MLP}}(\boldsymbol{t};\boldsymbol{\eta}^{\prime})$
(7)

where $-$ and $\odot$ denote an element-wise subtraction and element-wise
product, respectively. $[\boldsymbol{h}_{a};\boldsymbol{h}_{b}]$ indicates
that $\boldsymbol{h}_{a}$ and $\boldsymbol{h}_{b}$ are stacked as column
vectors. The resulting matching vector $\boldsymbol{t}\in\mathbb{R}^{4n_{h}}$
is then sent through an MLP layer (with sigmoid activation function and
parameters $\boldsymbol{\eta}^{\prime}$ to be learned) to model the desired
conditional distribution $p(y_{i}=1|\boldsymbol{h}_{q},\boldsymbol{h}_{a})$.

Notably, we share the weights of filter generating networks for both the
question and answer, so that the model adaptivity for answer selection can be
improved without an excessive increase in the number of parameters. All three
modules in AdaQA model are jointly trained end-to-end. Note that the AdaQA
model proposed can be readily adapted to other sentence matching tasks, such
as paraphrase identification (see Section 5.2).

###  3.4 Connections to attention mechanism

The adaptive _context-sensitive_ filter generation mechanism proposed here
bears close resemblance to attention mechanism Yin et al. (2016); Bahdanau et
al. (2015); Xiong et al. (2017) widely adopted in the NLP community, in the
sense that both methods intend to incorporate rich _contextual information_
into text representations. However, attention is typically operated on top of
the hidden units preprocessed by CNN or LSTM layers, and assigns different
weights to each unit according to a _context vector_. By contrast, in our
_context-sensitive_ filter generation mechanism, the contextual information is
inherently encoded into the convolutional filters, which directly interact
with the input sentence during the convolution encoding operation. Notably,
according to our experiments, the proposed filter generation module can be
readily combined with (standard) attention mechanisms to further enhance the
modeling expressiveness of CNN encoder.

##  4 Experimental Setup

#### Datasets

We investigate the effectiveness of the proposed ACNN framework on both
document classification and text sequence matching tasks. Specifically, we
consider two large-scale document classification datasets: Yelp Reviews
Polarity, and DBPedia ontology datasets (Zhang et al., 2015). For Yelp
reviews, we seek to predict a binary label (positive or negative) regarding
one review about a restaurant. DBpedia is extracted from Wikipedia by crowd-
sourcing and is categorized into 14 non-overlapping ontology classes,
including _Company_ , _Athlete_ , _Natural Place_ , _etc_. We sample 15$\%$ of
the training data as the validation set, to select hyperparameters for our
models and perform early stopping. For sentence matching, we evaluate the
AdaQA model on two datasets for open-domain question answering: WikiQA (Yang
et al., 2015) and SelQA (Jurczyk et al., 2016). Given a question, the task is
to rank the corresponding candidate answers, which, in the case of WikiQA, are
sentences extracted from the summary section of a related Wikipedia article.
To facilitate comparison with existing results (Yin et al., 2016; Yang et al.,
2015; Shen et al., 2018b), we truncate the candidate answers to a maximum
length of 40 tokens for all experiments on the WikiQA dataset. We also
consider the task of paraphrase identification with the Quora Question Pairs
dataset, with the same data splits as in Wang et al. (2017b). A summary of all
datasets is presented in Table 1.

Dataset | # train/ test | average #w | vocabulary
---|---|---|---
Yelp P. | 560k/ 38k | 138 | 25,709
DBpedia | 560k/ 70k | 56 | 21,666
WikiQA | 20,360/ 2,352 | 7/ 26 | 10,000
SelQA | 66,438/ 19,435 | 8/ 24 | 20,000
Quora | 390k/ 5,000 | 13/ 13 | 20,000
Table 1: Dataset statistics.

#### Training Details

For the document classification experiments, we randomly initialize the word
embeddings uniformly within $[-0.001,0.001]$ and update them during training.
For the generated filters, we set the window size as $h=5$, with $K=100$
feature maps (the dimension of $z$ is set as 100). For direct comparison, we
employ the same filter shape/size settings as in our basic CNN implementation.
A one-layer architecture is utilized for both the CNN baseline and the ACNN
model, since we did not observe significant performance gains with a
multilayer architecture. The minibatch size is set as 128, and a dropout rate
of 0.2 is utilized on the embedding layer. We observed that a larger dropout
rate (_e.g._ , 0.5) will hurt performance on document classifications and make
training significantly slower.

For the sentence matching tasks, we initialized the word embeddings with
50-dimensional Glove (Pennington et al., 2014) word vectors pretrained from
Wikipedia 2014 and Gigaword 5 (Pennington et al., 2014) for all model
variants. As for the filters, we set the window size as $h=5$, with $K=300$
feature maps. As described in Section 3.3, the vector $\boldsymbol{t}$, output
from the matching module, is fed to the prediction layer, implemented as a
one-layer MLP followed by the sigmoid function. We use Adam (Kingma and Ba,
2014) to train the models, with a learning rate of $3\times 10^{-4}$. Dropout
(Srivastava et al., 2014), with a rate of 0.5, is employed on the word
embedding layer. The hyperparameters are selected by choosing the best model
on the validation set. All models are implemented with TensorFlow Abadi et al.
(2016) and are trained using one NVIDIA GeForce GTX TITAN X GPU with 12GB
memory.

#### Baselines

For document classification, we consider several baseline models: ($i$) ngrams
(Zhang et al., 2015), a bag-of-means method based on TFIDF representations
built by choosing the 500,000 most frequent n-grams (up to 5-grams) from the
training set and use their corresponding counts as features; ($ii$)
small/large word CNN (Zhang et al., 2015): 6 layer word-based convolutional
networks, with 256/1024 features at each layer, denoted as small/large,
respectively; ($iii$) deep CNN (Conneau et al., 2016): deep convolutional
neural networks with 9/17/29 layers. To evaluate the effectiveness of proposed
AdaQA model, we compare it with several CNN-based sequence matching baselines,
including Vanilla CNN (Jurczyk et al., 2016; Santos et al., 2017), attentive
pooling networks (dos Santos et al., 2016), and ABCNN (Yin et al., 2016)
(where an attention mechanism is employed over the two sentence
representations).

#### Evaluation Metrics

For document categorization and paraphrase identification tasks, we employ the
percentage of correct predictions on the test set to evaluate and compare
different models. For the answer sentence selection task, mean average
precision (MAP) and mean reciprocal rank (MRR) are utilized as the
corresponding evaluation metrics.

Model | Yelp P. | DBpedia
---|---|---
_CNN-based Baseline Models_
ngrams∗ | 4.36 | 1.37
ngrams TFIDF∗ | 4.56 | 1.31
Small word CNN∗ | 5.54 | 1.85
Large word CNN∗ | 4.89 | 1.72
Self-attentive Embedding ‡ | 3.92 | 1.14
Deep CNN (9 layer)† | 4.88 | 1.35
Deep CNN (17 layer)† | 4.50 | 1.40
Deep CNN (29 layer)† | 4.28 | 1.29
_Our Implementations_
S-CNN | 14.48 | 22.35
S-ACNN | 6.41 | 5.16
M-CNN | 4.58 | 1.66
M-ACNN | 3.89 | 1.07
Table 2: Test error rates on document classification tasks (in percentages).
S-_model_ indicates that the _model_ has one single convolutional filter,
while M-_model_ indicates that the _model_ has multiple convolutional filters.
Results marked with $\ast$ are reported by Zhang et al. (2015), $\dagger$ are
reported by Conneau et al. (2016), and $\ddagger$ are reported by Lin et al.
(2017).

##  5 Experimental Results

###  5.1 Document Classification

To explicitly explore whether our ACNN model can leverage the input-aware
filter weights for better sentence representation, we perform a comparison
between the basic CNN and ACNN models with only a _single_ filter, which are
denoted as S-CNN, S-ACNN, respectively (this setting may not yield best
overall performance, since only a single filter is used, but it allows us to
isolate the impact of adaptivity). As illustrated in Table 2, S-ACNN
significantly outperforms S-CNN on both datasets, demonstrating the advantage
of the filter-generation module in our ACNN framework. As a result, with only
one convolutional filter and thus very limited modeling capacity, our S-ACNN
model tends to be much more expressive than the basic CNN model, due to the
flexibility of applying different filters to different sentences.

We further experiment on both ACNN and CNN models with _multiple_ filters. The
corresponding document categorization accuracies are presented in Table 2.
Although we only use one convolution layer for our ACNN model, it already
outperforms other CNN baseline methods with much deeper architectures.
Moreover, our method exhibits higher accuracy than n-grams, which is a very
strong baseline as shown in Zhang et al. (2015). We attribute the superior
performance of the ACNN framework to its stronger (adaptive) feature-
extraction ability. Moreover, our M-ACNN also achieves slightly better
performance than self-attentive sentence embeddings proposed in Lin et al.
(2017), which requires significant more parameters than our method.

#### Effect of number of filters

To further demonstrate that the performance gains in document categorization
experiments originates from the improved adaptivity of our ACNN framework, we
implement the basic CNN model with different numbers of filter sizes, ranging
from $1$ to $1000$. As illustrated in Figure 3(a), when the filter size is
larger than $100$, the test accuracy of the standard CNN model does not show
any noticeable improvement with more filters. More importantly, even with a
filter size of $1000$, the classification accuracy of the CNN is worse than
that of the ACNN model with the filter number restricted to $100$. Given these
observations, we believe that the boosted categorization accuracy does come
from the improved flexibility and thus better feature extraction of our ACNN
framework.

Model | MAP | MRR
---|---|---
_CNN-based Baseline Models_
bigram CNN + _Cnt_ ∗ | 0.6520 | 0.6652
Attentive Pooling Network | 0.6886 | 0.6957
ABCNN | 0.6921 | 0.7127
_Our Implementations_
CNN | 0.6752 | 0.6890
ACNN (self-adaptive) | 0.6897 | 0.7032
AdaQA (one-way) | 0.7005 | 0.7161
AdaQA (two-way) | 0.7107 | 0.7304
AdaQA (two-way) + att. | 0.7325 | 0.7428
Table 3: Results of our models on WikiQA dataset, compared with previous CNN-
based methods.

###  5.2 Answer Sentence Selection

To elucidate the role of different parts (modules) in our AdaQA model, we
implement several model variants for comparison: (_i_) a “vanilla” CNN model
that independently encodes two sentence representations for matching; (_ii_) a
self-adaptive ACNN-based model where the question/answer sentence generates
adaptive filters only to convolve with the input itself; (_iii_) a one-way
ACNN model where only the answer sentence representation is extracted with
adaptive filters, which are generated conditioned on the question; (_iv_) a
two-way AdaQA model as described in Section 2.4, where both sentences are
adaptively encoded, with filters generated conditioned on the other sequence;
(_v_) considering that the proposed filter generation mechanism is
complementary to the attention layer typically employed in sequence matching
tasks (see Section 3.4), we experiment with another model variant that
combines the proposed _context-sensitive_ filter generation mechanism with the
multi-perspective attention layer introduced in Wang et al. (2017b).

Model | MAP | MRR
---|---|---
_CNN-based Baseline Models_
CNN: _baseline_ ∗ | 0.8320 | 0.8420
CNN: _average + word_ ∗ | 0.8400 | 0.8494
CNN: _aver + emb_ ∗ | 0.8466 | 0.8568
CNN: _hinge_loss_ ‡ | 0.8758 | 0.8812
CNN-DAN‡ | 0.8655 | 0.8730
_Our Implementations_
CNN | 0.8644 | 0.8720
ACNN (self-adaptive) | 0.8739 | 0.8801
AdaQA (one-way) | 0.8823 | 0.8889
AdaQA (two-way) | 0.8914 | 0.8983
AdaQA (two-way) + att. | 0.9021 | 0.9103
Table 4: Results of our models on SelQA dataset, compared with previous CNN-based methods. Results marked with $\ast$ are from Jurczyk et al. (2016), and marked with $\ddagger$ are from Santos et al. (2017). |  |
---|---|---
(a) Effect of filter number |  (b) Different question types | (c) $t$-SNE visualization
Figure 3: Comprehensive study of the proposed ACNN framework, including (a)
the number of filters (Yelp dataset), and (b) performance _vs_ question types
(WikiQA dataset), and (c) $t$-SNE visualization of learned filter weights
(DBpedia dataset).

Tables 3 and 4 show experimental results of our models on WikiQA and SelQA
datasets, along with other state-of-the-art methods. Note that the self-
adaptive ACNN model variant, which generates filters only for the input itself
(without any interactions before the top matching module), slightly
outperforms the vanilla CNN Siamese model. Combined with the results in
document categorization experiments, we believe that our ACNN framework, in
its simplest form, can be utilized as a powerful feature extractor for
transforming natural language sentences into fixed-length vectors. More
importantly, our two-way AdaQA model exhibits superior results compared with
the one-way variant as well as other CNN-based baseline models on the WikiQA
dataset. This observation indicates that the _bidirectional_ filter generation
mechanism is strongly associated with the performance gains. While combined
with the multi-perspective attention layers, adopted after the ACNN encoding
layer, our two-way AdaQA model achieves even better performance. This suggests
that the proposed strategy is complementary, in terms of the incorporation of
rich contextual information, to the standard attention mechanism. The same
trend is also observed on the SelQA dataset (as shown in Table 4), which is a
much larger dataset than WikiQA.

Notably, our model yields significantly better results than an attentive
pooling network and ABCNN (attention-based CNN) baselines. We attribute the
improvement to two potential advantages of our AdaQA model: (_i_) for the two
previous baseline methods, the interaction between question and answer takes
place either before or after convolution. However, in our AdaQA model, the
communication between two sentences is inherent in the convolution operation,
and thus can provide the abstracted features with more flexibility; (_ii_) the
_bidirectional_ filter generation mechanism in our AdaQA model generates co-
dependent representations for the question and candidate answer, which could
enable the model to recover from initial local maxima corresponding to
incorrect predictions Xiong et al. (2017).

Model | Accuracy
---|---
Siamese-CNN | 0.7960
Multi-Perspective-CNN | 0\. 8138
AdaQA (two-way) | 0.8516
AdaQA (two-way) + att. | 0.8794
Table 5: Results on the Quora Question Pairs dataset.

#### Paragraph Identification

Considering that the proposed AdaQA model can be readily generalized to other
text sequence matching problems, we further evaluate the proposed framework on
the paraphrase identification task with the Quora question pairs dataset. To
ensure a fair comparison, we employ the same data splits as in Wang et al.
(2017b). As illustrated in Table 5, our two-way AdaQA model again exhibits
superior performances compared with basic CNN models (as reported in Wang et
al. (2017b)).

###  5.3 Discussion

#### Reasoning ability

To associate the improved answer sentence selection results with the reasoning
capabilities of our AdaQA model, we further categorize the questions in the
WikiQA test set into 5 types containing: ‘What’, ‘Where’, ‘How’, ‘When’ or
‘Who’. We then calculate the MAP scores of the basic CNN and our AdaQA model
on different question types. Similar to the findings in Miao et al. (2016), we
observe that the ‘How’ question is the hardest to answer, with the lowest MAP
scores. However, our AdaQA model improves most over the basic CNN on the ‘How’
type question, see Figure 3(b). Further comparing our results with NASM in
Miao et al. (2016), our AdaQA model (with a MAP score of $0.579$) outperforms
their reported ‘How’ question MAP scores ($0.524$) by a large margin,
indicating that the adaptive convolutional filter-generation mechanism
improves the model’s ability to read and reason over natural language
sentences.

#### Filter visualization

To better understand what information has been encoded into our _context-
sensitive_ filters, we visualize one of the filters for sentences within the
test set (on the DBpedia dataset) with $t$-SNE. The corresponding results are
shown in Figure 3(c). It can be observed that the filters for documents with
the same label (ontology) are grouped into clusters, indicating that for
different types of document, ACNN has leveraged distinct convolutional filters
for better feature extraction.

##  6 Conclusions

We presented a _context-sensitive_ convolutional filter-generation mechanism,
introducing a meta network to adaptively produce a set of input-aware filters.
In this manner, the filter weights vary from sample to sample, providing the
CNN encoder network with more modeling flexibility and capacity. This
framework is further generalized to model question-answer sentence pairs,
leveraging a two-way feature abstraction process. We evaluate our models on
several document-categorization and sentence matching benchmarks, and they
consistently outperform the standard CNN and attention-based CNN baselines,
demonstrating the effectiveness of our framework.

#### Acknowledgments

This research was supported in part by DARPA, DOE, NIH, ONR and NSF.

## References

  * Abadi et al. (2016) Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. 2016\.  Tensorflow: A system for large-scale machine learning.  In _OSDI_ , volume 16, pages 265–283.
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015.  Neural machine translation by jointly learning to align and translate.  _ICLR_.
  * Bromley et al. (1994) Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. 1994.  Signature verification using a” siamese” time delay neural network.  In _NIPS_ , pages 737–744.
  * Cohen and Singer (1999) William W Cohen and Yoram Singer. 1999.  Context-sensitive learning methods for text categorization.  _TOIS_ , 17(2):141–173.
  * Collobert et al. (2011) Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa. 2011.  Natural language processing (almost) from scratch.  _JMLR_ , 12(Aug):2493–2537.
  * Conneau et al. (2016) Alexis Conneau, Holger Schwenk, Loïc Barrault, and Yann Lecun. 2016.  Very deep convolutional networks for text classification.  _EACL_.
  * Dauphin et al. (2017) Yann N Dauphin, Angela Fan, Michael Auli, and David Grangier. 2017.  Language modeling with gated convolutional networks.  _ICML_.
  * De Brabandere et al. (2016) Bert De Brabandere, Xu Jia, Tinne Tuytelaars, and Luc Van Gool. 2016.  Dynamic filter networks.  In _NIPS_.
  * Gan et al. (2016) Zhe Gan, Yunchen Pu, Ricardo Henao, Chunyuan Li, Xiaodong He, and Lawrence Carin. 2016.  Learning generic sentence representations using convolutional neural networks.  _arXiv preprint arXiv:1611.07897_.
  * Gehring et al. (2017) Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin. 2017\.  Convolutional sequence to sequence learning.  _ICML_.
  * Ha et al. (2017) David Ha, Andrew Dai, and Quoc V Le. 2017.  Hypernetworks.  _ICLR_.
  * Hu et al. (2014) Baotian Hu, Zhengdong Lu, Hang Li, and Qingcai Chen. 2014.  Convolutional neural network architectures for matching natural language sentences.  In _NIPS_ , pages 2042–2050.
  * Jeon and Kim (2017) Yunho Jeon and Junmo Kim. 2017.  Active convolution: Learning the shape of convolution for image classification.  _CVPR_.
  * Jurczyk et al. (2016) Tomasz Jurczyk, Michael Zhai, and Jinho D Choi. 2016.  Selqa: A new benchmark for selection-based question answering.  In _ICTAI_ , pages 820–827. IEEE.
  * Kim (2014) Yoon Kim. 2014.  Convolutional neural networks for sentence classification.  _EMNLP_.
  * Kingma and Ba (2014) Diederik Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * LeCun et al. (1998) Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324.
  * Lin et al. (2017) Zhouhan Lin, Minwei Feng, Cicero Nogueira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio. 2017.  A structured self-attentive sentence embedding.  _ICLR_.
  * Liu et al. (2017) Pengfei Liu, Xipeng Qiu, and Xuanjing Huang. 2017.  Dynamic compositional neural networks over tree structure.  _IJCAI_.
  * Miao et al. (2016) Yishu Miao, Lei Yu, and Phil Blunsom. 2016.  Neural variational inference for text processing.  In _ICML_ , pages 1727–1736.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013.  Distributed representations of words and phrases and their compositionality.  In _NIPS_ , pages 3111–3119.
  * Mou et al. (2016) Lili Mou, Rui Men, Ge Li, Yan Xu, Lu Zhang, Rui Yan, and Zhi Jin. 2016.  Natural language inference by tree-based convolution and heuristic matching.  _ACL_.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014.  Glove: Global vectors for word representation.  In _EMNLP_ , pages 1532–1543.
  * Radford et al. (2016) Alec Radford, Luke Metz, and Soumith Chintala. 2016.  Unsupervised representation learning with deep convolutional generative adversarial networks.  _ICLR_.
  * dos Santos et al. (2016) Cıcero Nogueira dos Santos, Ming Tan, Bing Xiang, and Bowen Zhou. 2016.  Attentive pooling networks.  _CoRR, abs/1602.03609_.
  * Santos et al. (2017) Cicero Nogueira dos Santos, Kahini Wadhawan, and Bowen Zhou. 2017.  Learning loss functions for semi-supervised learning via discriminative adversarial networks.  _arXiv preprint arXiv:1707.02198_.
  * Shen et al. (2018a) Dinghan Shen, Qinliang Su, Paidamoyo Chapfuwa, Wenlin Wang, Guoyin Wang, Lawrence Carin, and Ricardo Henao. 2018a.  Nash: Toward end-to-end neural architecture for generative semantic hashing.  In _ACL_.
  * Shen et al. (2018b) Dinghan Shen, Guoyin Wang, Wenlin Wang, Martin Renqiang Min, Qinliang Su, Yizhe Zhang, Chunyuan Li, Ricardo Henao, and Lawrence Carin. 2018b.  Baseline needs more love: On simple word-embedding-based models and associated pooling mechanisms.  In _ACL_.
  * Shen et al. (2017) Dinghan Shen, Yizhe Zhang, Ricardo Henao, Qinliang Su, and Lawrence Carin. 2017\.  Deconvolutional latent-variable model for text sequence matching.  _arXiv preprint arXiv:1709.07109_.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey E Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: a simple way to prevent neural networks from overfitting.  _JMLR_ , 15(1):1929–1958.
  * Tang et al. (2018) Shuai Tang, Hailin Jin, Chen Fang, Zhaowen Wang, and Virginia Sa. 2018.  Speeding up context-based sentence representation learning with non-autoregressive convolutional decoding.  In _Proceedings of The Third Workshop on Representation Learning for NLP_ , pages 69–78.
  * Tang and de Sa (2018) Shuai Tang and Virginia R de Sa. 2018.  Multi-view sentence representation learning.  _arXiv preprint arXiv:1805.07443_.
  * Thrun and Pratt (2012) Sebastian Thrun and Lorien Pratt. 2012.  _Learning to learn_.  Springer Science & Business Media.
  * Wang et al. (2018) Guoyin Wang, Chunyuan Li, Wenlin Wang, Yizhe Zhang, Dinghan Shen, Xinyuan Zhang, Ricardo Henao, and Lawrence Carin. 2018.  Joint embedding of words and labels for text classification.  _arXiv preprint arXiv:1805.04174_.
  * Wang and Jiang (2017) Shuohang Wang and Jing Jiang. 2017.  A compare-aggregate model for matching text sequences.  _ICLR_.
  * Wang et al. (2017a) Wenlin Wang, Zhe Gan, Wenqi Wang, Dinghan Shen, Jiaji Huang, Wei Ping, Sanjeev Satheesh, and Lawrence Carin. 2017a.  Topic compositional neural language model.  _arXiv preprint arXiv:1712.09783_.
  * Wang et al. (2017b) Zhiguo Wang, Wael Hamza, and Radu Florian. 2017b.  Bilateral multi-perspective matching for natural language sentences.  _IJCAI_.
  * Wang et al. (2016) Zhiguo Wang, Haitao Mi, and Abraham Ittycheriah. 2016.  Sentence similarity learning by lexical decomposition and composition.  _COLING_.
  * Xiong et al. (2017) Caiming Xiong, Victor Zhong, and Richard Socher. 2017.  Dynamic coattention networks for question answering.  _ICLR_.
  * Yang et al. (2015) Yi Yang, Wen-tau Yih, and Christopher Meek. 2015.  Wikiqa: A challenge dataset for open-domain question answering.  In _EMNLP_ , pages 2013–2018.
  * Yin et al. (2016) Wenpeng Yin, Hinrich Schütze, Bing Xiang, and Bowen Zhou. 2016.  Abcnn: Attention-based convolutional neural network for modeling sentence pairs.  _TACL_.
  * Zhang et al. (2015) Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015.  Character-level convolutional networks for text classification.  In _NIPS_ , pages 649–657.
  * Zhang et al. (2018) Xinyuan Zhang, Yitong Li, Dinghan Shen, and Lawrence Carin. 2018.  Diffusion maps for textual network embedding.  _arXiv preprint arXiv:1805.09906_.