# Provably Stable Interpretable Encodings of Context Free Grammars in RNNs
with a Differentiable Stack

John Stogin
Independent Researcher
State College Area
Pennsylvania 16801 USA
<EMAIL_ADDRESS>
&Ankur Mali 11footnotemark: 1
Information Sciences and Technology
The Pennsylvania State University
University Park 16802 USA
<EMAIL_ADDRESS>
&C Lee Giles
Information Sciences and Technology
The Pennsylvania State University
University Park 16802 USA
<EMAIL_ADDRESS>
Equal contribution

###### Abstract

Given a collection of strings belonging to a context free grammar (CFG) and
another collection of strings not belonging to the CFG, how might one infer
the grammar? This is the problem of grammatical inference. Since CFGs are the
languages recognized by pushdown automata (PDA), it suffices to determine the
state transition rules and stack action rules of the corresponding PDA. An
approach would be to train a recurrent neural network (RNN) to classify the
sample data and attempt to extract these PDA rules. But neural networks are
not a priori aware of the structure of a PDA and would likely require many
samples to infer this structure. Furthermore, extracting the PDA rules from
the RNN is nontrivial. We build a RNN specifically structured like a PDA,
where weights correspond directly to the PDA rules. This requires a stack
architecture that is somehow differentiable (to enable gradient-based
learning) and stable (an unstable stack will show deteriorating performance
with longer strings). We propose a stack architecture that is differentiable
and that provably exhibits orbital stability. Using this stack, we construct a
neural network that provably approximates a PDA for strings of arbitrary
length. Moreover, our model and method of proof can easily be generalized to
other state machines, such as a Turing Machine.

##  1 Introduction

Recurrent neural networks (RNNs) are powerful stateful models that capture
temporal dependencies in sequential data. They have been widely used in
solving complex tasks, such as machine translation [34, 4, 63], language
modeling [46, 62], multimodal language modelling [35, 53] and speech
recognition [23]. In theory, first order RNNs with the desired weights and
infinite precision have been shown to be as powerful as a pushdown automaton
(PDA) [37, 38, 15] and can be considered to be computationally universal
models [58, 59, 7]. However, a higher order model (eg. with second order
weights) offers further representational capability – [50, 30, 6] proved that
any deterministic finite state automaton (DFA) can be stably constructed in a
$2$nd order, or tensor RNN. (A deterministic finite state automaton is a PDA
without a stack.) Another research direction focuses on non-sequential
structure based on self-attention known as the transformer [65]. Empirically,
the transformer has emerged as a new workhorse for solving natural language
processing tasks. However despite empirical success, recent findings have
shown that such models are theoretically incapable of recognizing context free
languages [71, 27], and thus are limited in terms of interpretation and
computation capabilities.

In this work, we examine the computational capabilities, interpretability, and
stability of tensor RNNs augmented with external memory from a theoretical
perspective. We ask whether RNN models with higher order weights entirely
based on a differentiable stack are theoretically capable of modeling
hierarchical structures involving unbounded recursion. While theoretical work
has investigated the power of RNNs and transformers [54], these results are
based on two key assumptions: infinite precision and infinite computation
time. Such assumptions do not hold true in the real world setting and are thus
limited in practical scenarios [68, 43, 45, 44]. In a step towards bridging
the gap between theoretical and empirical findings, we provide the first
theoretical proof on stability of memory augmented RNNs with finite precision.
We also show that under finite constraints our model is capable of
approximating any class of context free languages for strings whose lengths
satisfy correspondingly finite constraints. Beside these constraints, deep
learning models also lack interpretability, thus restricting their
application. In general two major paradigms have been explored in the
literature to tackle the interpretability issue:

Interpretable models by extraction or visualization: In this family of models,
the learned model behaves somewhat like a black box, and additional heuristics
or techniques are used to explain or extract insights from the model. This
approach does not restrict the model, allowing for greater flexibility and
expressive power, but likely requires a larger training dataset to learn
structure that may already be known to the modeller.

Intepretable models by design: In this family of models the notion of
interpretability is considered while designing the architecture. New
components may be added to existing architecture to force the model to work
within the interpretable regime [66, 18, 49] and possibly incorporate prior
knowledge. This approach trades model flexibility for more efficient learning
of a smaller class of models [43].

In this work, we propose an architecture which is interpretable by design.
When a grammar is known, our model can encode a minimal PDA. On the other hand
when a grammar is unknown [20] our model can be interpreted to extract the
corresponding state machine and therefore the corresponding grammar. To our
knowledge none of the prior work is focused on showing stability for models
that are interpretable by design [67, 51, 12, 31]. To this end our
contributions are:

  * •

We introduce a vector representation for a PDA.

  * •

We prove orbital stability of an interpretable, differentiable stack model
with finite precision and a configurable memory footprint.

  * •

We prove that RNNs coupled with this stack can arbitrarily approximate any PDA
in the sense that the neuron values remain close to the ideal vector
representation of the PDA.

  * •

We use an approach that can be easily extended for other state machines, such
as a Turing Machine.

##  2 Related Work

Historically, grammatical inference [22] has been at the core of language
learnability and could be considered to be fundamental in understanding
important properties of natural languages. A summary of the theoretical work
in formal languages and grammatical inference can be found in [11].
Applications of formal language work have led to methods for predicting and
understanding sequences in diverse areas, such as financial time series,
genetics and bioinformatics, and software data exchange [19, 69, 13]. Many
neural network models take the form of a first order (in weights) recurrent
neural network (RNN) and have been taught to learn context free and context-
sensitive counter languages [17, 9, 5, 64, 70, 56, 48, 66, 8, 36, 8, 67].
However, from a theoretical perspective, RNNs augmented with an external
memory have historically been shown to be more capable of recognizing context
free languages (CFLs), such as with a discrete stack [10, 55, 61], or, more
recently, with various differentiable memory structures [33, 26, 24, 39, 73,
28, 72, 25, 40, 41, 3, 42]. Despite positive results, prior work on CFLs was
unable to achieve perfect generalization on data beyond the training dataset,
highlighting a troubling difficulty in preserving long term memory. It was
previously shown that was caused by the instability of the internal
representations of learned states of RNNs learning deterministic finite state
automata (DFA)[50], which should be the same for states in a stack RNN
learning a PDA since a PDA is DFA controlling a stack. Early work primarily
focused on constructing DFA in recurrent networks with hard-limiting neurons
[1, 30, 47], sigmoidal [52, 21, 51, 50] and radial-basis functions [2, 16].
The importance and equivalence of differentiable memory over a discrete stack
while learning is still unclear [33, 42]. Recently, [44, 45, 37] theoretically
studied several types of RNNs and analyzed them to understand various classes
of languages accepted by them under finite precision. [44] showed the
computational power of RNNs, which is related in understanding various classes
of formal language accepted by RNNs in real world and finite precision
settings. Even more recently, and more closely related to our work, [37]
showed that arbitrary-precision RNNs are capable of emulating PDA, and can
therefore recognize all deterministic context-free languages. While they focus
on using infinite-precision edge weights to show that gate recurrent units are
as powerful as PDA, our proof uses finite-precision weights.111In [37], the
“stack memory” lies in the extended precision of the edge weights. Our “stack
memory” lies on additional neurons. Furthermore, our model is easily
interpretable: given the model, it is clear how to read the weights to
determine the state transition rules and stack action rules. Finally, our
approach can easily be generalized to other state machines, such as Turing
Machines, since the neural architecture directly relates to the state machine
architecture.

##  3 Neural Network with Stack Memory

A pushdown automaton (PDA) is a deterministic finite state automaton (DFA)
that controls a stack. Formally, a DFA is defined as a 5-tuple, while a PDA is
defined as a 7-tuple, the extra two elements corresponding to the stack. For
the reader’s convenience, a review of the DFA, including its formal
definition, is provided in Appendix A and a review of the PDA, including its
formal definition, is provided in Appendix B. Also for the reader’s
convenience, a list of common symbols and notation is provided in Appendix D
and an example context free grammar (CFG) and its corresponding PDA is
examined in Appendix E.

This section is the heart of the paper. In §3.1, we define the differentiable
stack, and then in §3.2, we use it to define the neural network pushdown
automaton (nnPDA). Finally, in §3.3, we prove that the nnPDA stably
approximates the PDA, with some less important details of the proof provided
in Appendix C. The reader may wish to refer to Appendix B for a definition of
the PDA and to see how it relates to the model presented here.

We will use the logistic sigmoid function

$h_{H}(x)=\frac{1}{1+e^{-Hx}}$

as an activation function. Note that $h_{H}(0)=\frac{1}{2}$ and $h_{H}(x)$
decreases to $0$ as $Hx\rightarrow-\infty$ and increases to $1$ as
$Hx\rightarrow\infty$. The scalar $H$ is a sensitivity parameter. In practice,
we will often show that $x$ is bounded away from $0$, and then assume $H$ to
be a positive constant sufficiently large so that $h_{H}(x)$ is as close as
desired to either $0$ or $1$, depending on the sign of the input $x$. (See
Lemma C.1.)

###  3.1 The differentiable stack

Here we define a differentiable stack memory [61, 26, 33].

######  Definition 3.1.

_(Differentiable stack)_ For a stack alphabet of size $m_{2}$, a
differentiable stack $K$ is a vector-valued sequence

$K=\\{K_{0},K_{1},...\\},\hskip 36.135ptK_{i}\in[0,1]^{m_{2}},$

with the additional requirement that there exists an integer $s$, called the
_stack size_ , such that

$K_{i}=\vec{0}\hskip 18.06749pt\text{ for all }\hskip 18.06749pti\geq s.$

The relation between this stack definition and the more traditional definition
of a stack is described in Appendix B.1. In particular, the vectors $K_{i}$ in
this definition closely resemble the idealized one-hot vectors $\bar{K}_{i}$
introduced in Definition B.4.

Traditionally, a stack can be modified by push and pop operations. Here, we
introduce a single differentiable stack operator that, for particular
parameter values, can closely resemble either push or pop.

######  Definition 3.2.

_(Differentiable stack operator)_ For scalars $p_{+}$ and $p_{-}$ and vector
$C\in[0,1]^{n}$, we define the stack operator $\pi(p_{+},p_{-},C)$ as follows.

$((\pi(p_{+},p_{-},C)K)_{i\geq
1})_{j}=h_{H}\left(p_{+}(K_{i-1})_{j}+p_{-}(K_{i+1})_{j}+(1-p_{+}-p_{-})(K_{i})_{j}-\frac{1}{2}\right),$
$((\pi(p_{+},p_{-},C)K)_{i=0})_{j}=h_{H}\left(p_{+}C_{j}+p_{-}(K_{1})_{j}+(1-p_{+}-p_{-})(K_{0})_{j}-\frac{1}{2}\right).$

This is visualized in Figure 1. Note that the operator $\pi(0,1,C)$ is an
approximate pop operator, the operator $\pi(0,0,C)$ is an approximate identity
operator, and the operator $\pi(1,0,C)$ is an approximate push operator that
approximately pushes the vector $C$ onto the stack.

In Appendix B.1, a similar idealized operator
$\bar{\pi}(\bar{p}_{+},\bar{p}_{-},\bar{C})$ is defined, for which
$\bar{\pi}(0,1,\bar{C})$ is exactly a pop operator, the operator
$\bar{\pi}(0,0,C)$ is the identity operator, and the operator
$\bar{\pi}(1,0,\bar{C})$ is exactly a push operator that pushes the vector
$\bar{C}$ onto the stack. (See Definition B.5.) The relation between these two
operators is formalized by the following proposition, which serves as a
theoretical justification for $\pi(p_{+},p_{-},C)$.

######  Proposition 3.3.

_( $\pi(\cdot,\cdot,\cdot)$ approximates $\bar{\pi}(\cdot,\cdot,\cdot)$)_

Let $K$ be a stack according to Definition 3.1 and let $\bar{K}$ be an
idealized stack according to Definition B.4, and suppose that

$\sup_{i}||K_{i}-\bar{K}_{i}||_{L^{\infty}}\leq\epsilon$

for some $\epsilon>0$.

Let $\pi(p_{+},p_{-},C)$ be an operator according to Definition 3.2 and
$\bar{\pi}(\bar{p}_{+},\bar{p}_{-},\bar{C})$ be an idealized operator
according to Definition B.5. Suppose furthermore that, in addition to
belonging to the domains of their respective operators, the quantities
$p_{+}$, $p_{-}$, $C$, $\bar{p}_{+}$, $\bar{p}_{-}$, and $\bar{C}$ satisfy

$|p_{+}-\bar{p}_{+}|\leq\epsilon$ $|p_{-}-\bar{p}_{-}|\leq\epsilon$
$||C-\bar{C}||_{L^{\infty}}\leq\epsilon.$

If $\epsilon$ is sufficiently small, then $H$ can be chosen sufficiently
large, depending only on $\epsilon$, so that

$\sup_{i}||(\pi(p_{+},p_{-},C)K)_{i}-(\bar{\pi}(\bar{p}_{+},\bar{p}_{-},\bar{C})\bar{K})_{i}||_{L^{\infty}}\leq\epsilon.$

The proof of this proposition is provided in Appendix C.

Figure 1: Differentiable Stack Operation Visualization of the operator
$\pi(p_{+},p_{-},C)$ with $p_{+}=0.7$ and $p_{-}=0.2$. First, a linear
combination of the adjacent stack vectors is computed, then $h_{H}$ is applied
to each component. The stack alphabet size is $m_{2}=4$. The stack size is
$s=5$ before the operator is applied and $s=6$ afterward. As long as
$p_{+}>0$, the stack size will increase by $1$.

In tensor products that will be used momentarily, if any factor is the zero
vector $\vec{0}$, the entire expression becomes zero. Therefore, instead of
using the top of the stack $K_{0}$ directly, we will instead use the stack
reading vector $R$, which has one additional component that is approximately
$1$ when $K_{0}$ is approximately $\vec{0}$.

######  Definition 3.4.

_(Stack Reading)_ Given the top vector of the stack $K_{0}$ with dimension
$m_{2}$, we define the stack reading vector $R$ to be a vector of dimenion
$m_{2}+1$ with components

$R_{i}=\left\\{\begin{array}[]{ll}(K_{0})_{i}&0\leq i<m_{2}\\\
1-||K_{0}||_{L^{\infty}}&i=m_{2}.\end{array}\right.$

These two vectors are equivalent in the following sense.

######  Lemma 3.5.

Given a top-of-stack vector $K_{0}$ and an idealized top-of-stack vector
$\bar{K}_{0}$, let $R$ and $\bar{R}$ be the corresponding stack reading vector
and idealized stack reading vector. Then

$||K_{0}-\bar{K}_{0}||_{L^{\infty}}=||R-\bar{R}||_{L^{\infty}}.$

The proof of this lemma is provided in Appendix C.

###  3.2 The nnPDA

For the reader’s convenience, in §B.2 the PDA is formally defined (Definition
B.7) and a vector representation is derived (Definition B.9). Our goal is to
approximate the PDA vector representation using a recurrent neural network
architecture, which we will denote as a _neural network pushdown automaton_ ,
or nnPDA.

Figure 2: Neural network pushdown automaton architecture The nnPDA takes the
$(t+1)$th input character represented by $I^{t+1}$ as well as the state
represented by $Q^{t}$ and a reading $R^{t}$ of the top of the stack
determined from $K^{t}_{0}$. By applying the weights
$W_{Q},W_{C},W_{p_{+}},W_{p_{-}}$, it computes and outputs the new state
represented by $Q^{t+1}$ as well as the parameters for the stack action,
represented by $C^{t+1}$, $p_{+}^{t+1}$, and $p_{-}^{t+1}$. The stack is then
updated by applying the operator $\pi(C^{t+1},p_{+}^{t+1},p_{-}^{t+1})$. This
completes one cycle.

######  Definition 3.6.

_(nnPDA)_ At any time $t$, the full state of a neural network pushdown
automaton is represented by the pair

$(Q^{t},K^{t}),$

where $Q^{t}\in[0,1]^{n}$ is a vector encoding the state and $K^{t}$ is a
differentiable stack according to Definition 3.1.

The next state pair $(Q^{t+1},K^{t+1})$ is given by the dynamic relations

$\displaystyle Q^{t+1}{}_{i}$ $\displaystyle=h_{H}\left((W_{Q}^{t+1}\cdot
Q^{t})_{i}-\frac{1}{2}\right)$ (1) $\displaystyle K^{t+1}$
$\displaystyle=\pi^{t+1}K^{t},$ (2)

where the transition matrix $W_{Q}^{t+1}$ and operator $\pi^{t+1}$ are defined
as follows.

Letting $I^{t+1}$ be a one-hot encoding of the $(t+1)$th input character, the
transition matrix $W_{Q}^{t+1}$ is given in component form by

$(W_{Q}^{t+1})_{i}{}^{j}=\sum_{k,l}(W_{Q})_{i}{}^{jkl}R^{t}{}_{l}I^{t+1}{}_{k},$

where the components $(W_{Q})_{i}{}^{jkl}$ are chosen to represent the
transition rules as in Definition B.9,222Actually, it suffices to use weights
that are close to the ideal weights in Definition B.9. We keep them the same
in this paper to avoid unnecessary complication. and the stack reading $R^{t}$
is determined from $K_{0}^{t}$ as described by Definition 3.4.

The operator $\pi^{t+1}$ is given by

$\pi^{t+1}=\pi(p_{+}^{t+1},p_{-}^{t+1},C^{t+1}),$

where the parameters $p_{\pm}^{t+1}$ and vector $C^{t+1}$ are

$p_{\pm}^{t+1}=\sum_{j,k,l}(W_{p_{\pm}})^{jkl}R^{t}{}_{l}I^{t+1}{}_{k}Q^{t}{}_{j}$
$C^{t+1}{}_{i}=\sum_{j,k,l}(W_{C})_{i}{}^{jkl}{}R^{t}{}_{l}I^{t+1}{}_{k}Q^{t}{}_{j}$

where the components $(W_{p_{+}})^{jkl}$, $(W_{p_{-}})^{jkl}$, and
$(W_{C})_{i}{}^{jkl}$ are chosen to represent the stack action rules as in
Definition B.9.

###  3.3 Proof of stability of the nnPDA

The main result of this paper is the following theorem, which states that the
nnPDA remains close to the idealized PDA.

######  Theorem 3.7.

Let $I^{t}$ be an arbitrary time-indexed sequence encoding a character string,
let $(Q^{t},K^{t})$ be a state-and-stack sequence governed by equations (1-2)
in Definition 3.6 for some scalar $H$, and let $(\bar{Q}^{t},\bar{K}^{t})$ be
an idealized state-and-stack sequence governed by equations (4-5) in
Definition B.9.

For any $\epsilon>0$ sufficiently small, if $H$ is sufficiently large
(depending on $\epsilon$) and

$(Q^{t=0},K^{t=0})=(\bar{Q}^{t=0},\bar{K}^{t=0}),$

then for all $t\geq 0$,

$||Q^{t}-\bar{Q}^{t}||_{L^{\infty}}\leq\epsilon$

and

$\sup_{i}||K_{i}^{t}-\bar{K}_{i}^{t}||_{L^{\infty}}\leq\epsilon.$

To prove this theorem, we will instead state and prove the following
proposition, which examines a single time step. The theorem then follows by
induction on $t$.

######  Proposition 3.8.

Let $(Q^{t},K^{t})$ be a state-and-stack sequence governed by equations (1-2)
in Definition 3.6 for some scalar $H$, and let $(\bar{Q}^{t},\bar{K}^{t})$ be
an idealized state-and-stack sequence governed by equations (4-5) in
Definition B.9.

For any $\epsilon>0$ sufficiently small, if $H$ is sufficiently large and

$||Q^{t}-\bar{Q}^{t}||_{L^{\infty}}\leq\epsilon$
$\sup_{i}||K_{i}^{t}-\bar{K}_{i}^{t}||_{L^{\infty}}\leq\epsilon,$

then

$||Q^{t+1}-\bar{Q}^{t+1}||_{L^{\infty}}\leq\epsilon$
$\sup_{i}||K_{i}^{t+1}-\bar{K}_{i}^{t+1}||_{L^{\infty}}\leq\epsilon.$

###### Proof.

First, we will show that

$||Q^{t+1}-\bar{Q}^{t+1}||_{L^{\infty}}\leq\epsilon.$

Note that

$Q^{t+1}{}_{i}=h_{H}\left(V_{i}-\frac{1}{2}\right),$

where

$V_{i}=\sum_{j,k,l}(W_{Q})_{i}{}^{jkl}R^{t}{}_{l}I^{t+1}{}_{k}Q^{t}{}_{j},$

And

$\bar{Q}^{t+1}{}_{i}=\bar{V}_{i},$

where

$\bar{V}_{i}=\sum_{j,k,l}(W_{Q})_{i}{}^{jkl}\bar{R}^{t}{}_{l}I^{t+1}{}_{k}\bar{Q}^{t}{}_{j}.$

Observe that

$V=\bar{V}+err,$

where

$\displaystyle err$ $\displaystyle=err_{1}+err_{2}$ $\displaystyle err_{1}$
$\displaystyle=\sum_{j,k,l}(W_{Q})_{i}{}^{jkl}\bar{R}^{t}{}_{l}I^{t+1}{}_{k}\left[Q^{t}{}_{j}-\bar{Q}^{t}{}_{j}\right]$
$\displaystyle err_{2}$
$\displaystyle=\sum_{j,k,l}(W_{Q})_{i}{}^{jkl}\left[R^{t}{}_{l}-\bar{R}^{t}{}_{l}\right]I^{t+1}{}_{k}Q^{t}{}_{j}.$

The factors in square brackets are each at most size $\epsilon$,333The
difference $R-\bar{R}$ relates to the difference $K_{0}-\bar{K}_{0}$ by Lemma
3.5. while the remaining factors are at most size $1$. It follows that for
some constant $C>0$,

$||V-\bar{V}||_{L^{\infty}}\leq C\epsilon.$

By Lemma C.1, we may conclude that if $\epsilon$ is sufficiently small and $H$
is sufficiently large (depending on $\epsilon$), then

$||Q^{t+1}-\bar{Q}^{t+1}||_{L^{\infty}}\leq\epsilon.$

By similar arguments, we may also prove that, with possibly additional
constraints on $H$,

$|p_{+}^{t+1}-\bar{p}_{+}^{t+1}|\leq\epsilon$
$|p_{-}^{t+1}-\bar{p}_{-}^{t+1}|\leq\epsilon$
$||C^{t+1}-\bar{C}^{t+1}||_{L^{\infty}}\leq\epsilon.$

Given these estimates, by Proposition 3.3, it follows that

$\sup_{i}||(\pi(p_{+}^{t+1},p_{-}^{t+1},C^{t+1})K^{t})_{i}-(\bar{\pi}(\bar{p}_{+}^{t+1},\bar{p}_{-}^{t+1},\bar{C}^{t+1})\bar{K}^{t})_{i}||_{L^{\infty}}\leq\epsilon,$

which means

$\sup_{i}||K_{i}^{t+1}-\bar{K}_{i}^{t+1}||_{L^{\infty}}\leq\epsilon.$

∎

##  4 Discussion and Complexity

The operations performed by our tensor nnPDA directly map to PDA state
transitions, making the PDA encoding straightforward. For a state machine with
$n$ states, an input alphabet of size $m_{1}$, a stack alphabet of size
$m_{2}$, and a stack with maximum capacity $s$, our algorithm can construct a
sparse recurrent network with $O(n)$ state neurons,
$O(m_{1}m_{2}n(m_{1}+m_{2}+n))$ weights and a stack memory footprint of size
$O(sm_{2})$, such that the PDA and constructed networks accept and correctly
classify a similar context free language. The model and stability argument we
present can be easily generalized to the case where a PDA is embedded into
other recurrent networks and also to a universal state machine, such as a
Turing Machine.

##  5 Conclusion

We defined a vectorized stack and a parametrized stack operator that behaves
similarly to a stack push or pop operation for particular choices of the
parameters. We used these to construct a neural network pushdown automaton
(nnPDA) and proved that it is stable: For suitable choices of weights, the
nnPDA will closely resemble a pushdown automaton (PDA) for arbitrarily long
strings. The sense in which the nnPDA and PDA are “close“ is formalized by
also representing the PDA as a set of vectors (this is done in Appendix B) and
taking a vector difference.

Prior work [10, 52, 41] has shown that initializing a network with prior
knowledge can yield improved generalization while training. In such cases, the
weights of the network which are not programmed (ie. weights that have prior
values equal to zero) are instead initialized to small random values while
significant weights must be chosen carefully. The addition of random weights
is important for learning, but also acts as noise that could potentially cause
an instability, motivating a need for models that are known to be stable, such
as the model presented in this paper. It would be an interesting question to
investigate whether RNNs with memory and finitie precision and with lower
tensorial order are still capable of approximating any PDA. An affirmative
answer to this question would yield a more computationally efficient model,
while a negative answer might provide insight into subclasses of computational
languages accepted by RNNs.

##  6 Potential broader impact of this research

Recently, neural network research and its applications have received renewed
interest encouraged by advances in representation learning and significantly
improved problem solving. Despite recent breakthroughs and successes, we are
still struggling to fully design and deploy deep neural networks that can be
ethically [32] used in various domains. This work is a step towards building
trustworthy artificial intelligence systems [14, 32] for the social good [57].
Here we introduce an interpretable recurrent neural network augmented with
differentiable memory. Our model is capable of approximating any pushdown
automaton, and thus can efficiently recognize context-free languages and by
extension recursively enumerable languages. Due to its interpretable design
with provable stability, our model is trustworthy and ensures that its outputs
have the desired result when the rules are specified by the user. We believe
this research will lead towards better decision making in domains that have
high-risk factors and as such would be beneficial for society [60]. Finally,
this work helps in understanding the computational capability of recurrent
neural networks under the important and practical computational constraint of
finite precision and provides a vector-based framework for showing
mathematical stability.

## References

  * [1] Alon, N., Dewdney, A., and Ott, T. J. Efficient simulation of finite automata by neural nets.  Journal of the ACM (JACM) 38, 2 (1991), 495–514.
  * [2] Alquézar, R., and Sanfeliu, A. An algebraic framework to represent finite state machines in single-layer recurrent neural networks.  Neural Computation 7, 5 (1995), 931–949.
  * [3] Arabshahi, F., Lu, Z., Singh, S., and Anandkumar, A. Memory augmented recursive neural networks, 2019.
  * [4] Bahdanau, D., Cho, K., and Bengio, Y. Neural machine translation by jointly learning to align and translate.  In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings (2015).
  * [5] Bodén, M., and Wiles, J. Context-free and context-sensitive dynamics in recurrent neural networks.  Connection Science 12, 3-4 (2000), 197–210.
  * [6] Carrasco, R. C., Forcada, M. L., Valdés-Munoz, M. A., and Ñeco, R. P. Stable encoding of finite-state machines in discrete-time recurrent neural nets with sigmoid units.  Neural Computation 12, 9 (2000), 2129–2174.
  * [7] Chen, Y., Gilroy, S., Maletti, A., May, J., and Knight, K. Recurrent neural networks as weighted language recognizers.  arXiv preprint arXiv:1711.05408 (2017).
  * [8] Cleeremans, A., Servan-Schreiber, D., and McClelland, J. L. Finite state automata and simple recurrent networks.  Neural computation 1, 3 (1989), 372–381.
  * [9] Das, S., Giles, C. L., and Sun, G.-Z. Learning context-free grammars: Capabilities and limitations of a recurrent neural network with an external stack memory.  In Proceedings of The Fourteenth Annual Conference of Cognitive Science Society. Indiana University (1992), p. 14.
  * [10] Das, S., Giles, C. L., and Sun, G.-Z. Using prior knowledge in a nnpda to learn context-free languages.  In Advances in neural information processing systems (1993), pp. 65–72.
  * [11] De la Higuera, C. Grammatical inference: learning automata and grammars.  Cambridge University Press, 2010.
  * [12] Du, M., Liu, N., Yang, F., Ji, S., and Hu, X. On attribution of recurrent neural network predictions via additive decomposition.  In The World Wide Web Conference (2019), pp. 383–393.
  * [13] Exler, M., Moser, M., Pichler, J., Fleck, G., and Dorninger, B. Grammatical inference from data exchange files: An experiment on engineering software.  In 2018 IEEE 25th International Conference on Software Analysis, Evolution and Reengineering (SANER) (2018), IEEE, pp. 557–561.
  * [14] Floridi, L. Establishing the rules for building trustworthy ai.  Nature Machine Intelligence 1, 6 (2019), 261–262.
  * [15] Frasconi, P., and Gori, M. Computational capabilities of local-feedback recurrent networks acting as finite-state machines.  IEEE Transactions on Neural Networks 7, 6 (1996), 1521–1525.
  * [16] Frasconi, P., Gori, M., and Soda, G. Injecting nondeterministic finite state automata into recurrent neural networks.  Relat6rio Tecnico. DSHIT15192, Dipartimento di Sistemi e Informatica, Firenze, Italy (1992).
  * [17] Gers, F. A., and Schmidhuber, E. Lstm recurrent networks learn simple context-free and context-sensitive languages.  IEEE Transactions on Neural Networks 12, 6 (Nov 2001), 1333–1340.
  * [18] Gers, F. A., and Schmidhuber, J. Recurrent nets that time and count.  In Proceedings of the IEEE-INNS-ENNS International Joint Conference on Neural Networks. IJCNN 2000. Neural Computing: New Challenges and Perspectives for the New Millennium (2000), vol. 3, IEEE, pp. 189–194.
  * [19] Giles, C. L., Lawrence, S., and Tsoi, A. C. Noisy time series prediction using recurrent neural networks and grammatical inference.  Machine learning 44, 1-2 (2001), 161–183.
  * [20] Giles, C. L., Miller, C. B., Chen, D., Sun, G. Z., Chen, H. H., and Lee, Y. C. Extracting and learning an unknown grammar with recurrent neural networks.  In Advances in Neural Information Processing Systems 4, J. E. Moody, S. J. Hanson, and R. P. Lippmann, Eds. Morgan-Kaufmann, 1992, pp. 317–324.
  * [21] Giles, C. L., and Omlin, C. W. Extraction, insertion and refinement of symbolic rules in dynamically driven recurrent neural networks.  Connection Science 5, 3-4 (1993), 307–337.
  * [22] Gold, E. M. Language identification in the limit.  Information and control 10, 5 (1967), 447–474.
  * [23] Graves, A., Mohamed, A., and Hinton, G. E. Speech recognition with deep recurrent neural networks.  In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2013, Vancouver, BC, Canada, May 26-31, 2013 (2013), pp. 6645–6649.
  * [24] Graves, A., Wayne, G., and Danihelka, I. Neural turing machines.  arXiv preprint arXiv:1410.5401 (2014).
  * [25] Graves, A., Wayne, G., Reynolds, M., Harley, T., Danihelka, I., Grabska-Barwińska, A., Colmenarejo, S. G., Grefenstette, E., Ramalho, T., Agapiou, J., et al. Hybrid computing using a neural network with dynamic external memory.  Nature 538, 7626 (2016), 471.
  * [26] Grefenstette, E., Hermann, K. M., Suleyman, M., and Blunsom, P. Learning to transduce with unbounded memory.  In Advances in neural information processing systems (2015), pp. 1828–1836.
  * [27] Hahn, M. Theoretical limitations of self-attention in neural sequence models.  Transactions of the Association for Computational Linguistics 8 (2020), 156–171.
  * [28] Hao, Y., Merrill, W., Angluin, D., Frank, R., Amsel, N., Benz, A., and Mendelsohn, S. Context-free transductions with neural stacks.  arXiv preprint arXiv:1809.02836 (2018).
  * [29] Hopcroft, J. E., Motwani, R., and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation (3rd Edition).  Pearson, 2006.
  * [30] Horne, B. G., and Hush, D. R. Bounds on the complexity of recurrent neural network implementations of finite state machines.  In Advances in neural information processing systems (1994), pp. 359–366.
  * [31] Jacobsson, H. Rule extraction from recurrent neural networks: Ataxonomy and review.  Neural Computation 17, 6 (2005), 1223–1263.
  * [32] Jobin, A., Ienca, M., and Vayena, E. The global landscape of ai ethics guidelines.  Nature Machine Intelligence 1, 9 (2019), 389–399.
  * [33] Joulin, A., and Mikolov, T. Inferring algorithmic patterns with stack-augmented recurrent nets.  In Advances in neural information processing systems (2015), pp. 190–198.
  * [34] Kalchbrenner, N., and Blunsom, P. Recurrent continuous translation models.  In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, EMNLP 2013, 18-21 October 2013, Grand Hyatt Seattle, Seattle, Washington, USA, A meeting of SIGDAT, a Special Interest Group of the ACL (2013), pp. 1700–1709.
  * [35] Kiros, R., Salakhutdinov, R., and Zemel, R. Multimodal neural language models.  In International conference on machine learning (2014), pp. 595–603.
  * [36] Kolen, J. F. Recurrent networks: State machines or iterated function systems.  In Proceedings of the 1993 Connectionist Models Summer School (1994), Hillsdale NJ, pp. 203–210.
  * [37] Korsky, S. A., and Berwick, R. C. On the computational power of rnns.  CoRR abs/1906.06349 (2019).
  * [38] Kremer, S. C. On the computational power of elman-style recurrent networks.  IEEE Transactions on neural networks 6, 4 (1995), 1000–1004.
  * [39] Kurach, K., Andrychowicz, M., and Sutskever, I. Neural random-access machines.  arXiv preprint arXiv:1511.06392 (2015).
  * [40] Le, H., Tran, T., and Venkatesh, S. Neural stored-program memory.  arXiv preprint arXiv:1906.08862 (2019).
  * [41] Mali, A., Ororbia, A., and Giles, C. L. The neural state pushdown automata, 2019.
  * [42] Mali, A., Ororbia, A., Kifer, D., and Giles, C. L. Recognizing long grammatical sequences using recurrent networks augmented with an external differentiable stack, 2020.
  * [43] Marzouk, R., and de la Higuera, C. Distance and equivalence between finite state machines and recurrent neural networks: Computational results, 2020.
  * [44] Merrill, W. Sequential neural networks as automata.  CoRR abs/1906.01615 (2019).
  * [45] Merrill, W., Weiss, G., Goldberg, Y., Schwartz, R., Smith, N. A., and Yahav, E. A formal hierarchy of rnn architectures.  arXiv preprint arXiv:2004.08500 (2020).
  * [46] Mikolov, T., Karafiát, M., Burget, L., Cernocký, J., and Khudanpur, S. Recurrent neural network based language model.  In INTERSPEECH 2010, 11th Annual Conference of the International Speech Communication Association, Makuhari, Chiba, Japan, September 26-30, 2010 (2010), pp. 1045–1048.
  * [47] Minsky, M. L. Computation.  Prentice-Hall Englewood Cliffs, 1967.
  * [48] Nam, H., Kim, S., and Jung, K. Number sequence prediction problems for evaluating computational powers of neural networks.  In Proceedings of the AAAI Conference on Artificial Intelligence (2019), vol. 33, pp. 4626–4633.
  * [49] Oliva, C., and Lago-Fernández, L. F. On the interpretation of recurrent neural networks as finite state machines.  In International Conference on Artificial Neural Networks (2019), Springer, pp. 312–323.
  * [50] Omlin, C. W., and Giles, C. L. Constructing deterministic finite-state automata in recurrent neural networks.  Journal of the ACM (JACM) 43, 6 (1996), 937–972.
  * [51] Omlin, C. W., and Giles, C. L. Extraction of rules from discrete-time recurrent neural networks.  Neural networks 9, 1 (1996), 41–52.
  * [52] Omlin, C. W., and Giles, C. L. Stable encoding of large finite-state automata in recurrent neural networks with sigmoid discriminants.  Neural Computation 8, 4 (1996), 675–696.
  * [53] Ororbia, A., Mali, A., Kelly, M., and Reitter, D. Like a baby: Visually situated neural language acquisition.  In Proceedings of the 57th Conference of the Association for Computational Linguistics (2019), pp. 5127–5136.
  * [54] Pérez, J., Marinković, J., and Barceló, P. On the turing completeness of modern neural network architectures.  arXiv preprint arXiv:1901.03429 (2019).
  * [55] Pollack, J. B. Recursive distributed representations.  Artificial Intelligence 46, 1-2 (1990), 77–105.
  * [56] Sennhauser, L., and Berwick, R. C. Evaluating the ability of lstms to learn context-free grammars.  arXiv preprint arXiv:1811.02611 (2018).
  * [57] Shi, Z. R., Wang, C., and Fang, F. Artificial intelligence for social good: A survey.  arXiv preprint arXiv:2001.01818 (2020).
  * [58] Siegelmann, H. T., and Sontag, E. D. Analog computation via neural networks.  Theor. Comput. Sci. 131, 2 (1994), 331–360.
  * [59] Siegelmann, H. T., and Sontag, E. D. On the computational power of neural nets.  J. Comput. Syst. Sci. 50, 1 (1995), 132–150.
  * [60] Smuha, N. A. The eu approach to ethics guidelines for trustworthy artificial intelligence.  CRi-Computer Law Review International (2019).
  * [61] Sun, G.-Z., Giles, C. L., and Chen, H.-H. The neural network pushdown automaton: Architecture, dynamics and training.  In International School on Neural Networks, Initiated by IIASS and EMFCSC (1997), Springer, pp. 296–345.
  * [62] Sundermeyer, M., Schlüter, R., and Ney, H. LSTM neural networks for language modeling.  In INTERSPEECH 2012, 13th Annual Conference of the International Speech Communication Association, Portland, Oregon, USA, September 9-13, 2012 (2012), pp. 194–197.
  * [63] Sutskever, I., Vinyals, O., and Le, Q. V. Sequence to sequence learning with neural networks.  In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada (2014), pp. 3104–3112.
  * [64] Tabor, W. Fractal encoding of context-free grammars in connectionist networks.  Expert Systems 17, 1 (2000), 41–56.
  * [65] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Attention is all you need.  In Advances in neural information processing systems (2017), pp. 5998–6008.
  * [66] Wang, C., and Niepert, M. State-regularized recurrent neural networks, 2019.
  * [67] Weiss, G., Goldberg, Y., and Yahav, E. Extracting automata from recurrent neural networks using queries and counterexamples.  arXiv preprint arXiv:1711.09576 (2017).
  * [68] Weiss, G., Goldberg, Y., and Yahav, E. On the practical computational power of finite precision rnns for language recognition.  In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, ACL 2018, Melbourne, Australia, July 15-20, 2018, Volume 2: Short Papers (2018), pp. 740–745.
  * [69] Wieczorek, W., and Unold, O. Use of a novel grammatical inference approach in classification of amyloidogenic hexapeptides.  Computational and mathematical methods in medicine 2016 (2016).
  * [70] Wiles, J., and Elman, J. Learning to count without a counter: A case study of dynamics and activation landscapes in recurrent networks.  In Proceedings of the seventeenth annual conference of the cognitive science society (1995), no. s 482, Erlbaum Hillsdale, NJ, p. 487.
  * [71] Yang, B., Wang, L., Wong, D. F., Chao, L. S., and Tu, Z. Assessing the ability of self-attention networks to learn word order.  arXiv preprint arXiv:1906.00592 (2019).
  * [72] Yogatama, D., Miao, Y., Melis, G., Ling, W., Kuncoro, A., Dyer, C., and Blunsom, P. Memory architectures in recurrent neural network language models.  In International Conference on Learning Representations (2018).
  * [73] Zeng, Z., Goodman, R. M., and Smyth, P. Discrete recurrent neural networks for grammatical inference.  IEEE Transactions on Neural Networks 5, 2 (1994), 320–330.

##  Appendix A Vector Representation of a Deterministic Finite State Automaton

It is often easier to understand a PDA by first understanding the simpler DFA,
or deterministic finite state automaton. We review the DFA here, beginning
with a common definition of a finite-state automaton. [29]

######  Definition A.1.

_(DFA, classical version)_ A finite-state automaton is a quintuple
$(Q,\Sigma,\delta,q_{0},F)$, where $Q=\\{q_{1},...,q_{n}\\}$ is a finite set
of states, $\Sigma=\\{\mathfrak{a}_{1},...,\mathfrak{a}_{m}\\}$ is a finite
alphabet, $\delta:Q\times\Sigma\rightarrow Q$ is the state transition
function, and $q_{0}\in Q$ is a start state, $F\subset Q$ is a set of
acceptable final states.

A string of characters $\mathfrak{a}^{1}...\mathfrak{a}^{l}$ can be fed to the
DFA, which in turn changes state according to the following rules.

$q^{t=0}=q_{0}$ $q^{t+1}=\delta(q^{t},\mathfrak{a}^{t+1}).$

As we are mainly interested in dynamics, we will work in the context of an
arbitrary string. The following simplified definition focuses on the dynamics
of the DFA.

######  Definition A.2.

_(DFA, dynamic version)_ At any time $t$, the state of a finite-state
automaton is

$q^{t}\in\\{q_{1},...,q_{n}\\}.$

The next state $q^{t+1}$ is given by the dynamic relation

$q^{t+1}=\delta^{t+1}(q^{t}),$

where $\delta^{t+1}(q)=\delta(q,\mathfrak{a}^{t+1})$.

To easily generalize to a neural network, we will further modify the above
definition to obtain a vector representation of the DFA.

######  Definition A.3.

_(DFA, vectorized dynamic version)_ At any time $t$, the state of a
deterministic finite-state automaton is represented by the state vector444The
use of the bar in $\bar{Q}^{t}$ is in preparation for neural networks. As
neural networks are the main focus of this paper, we will generally use
$Q^{t}$ to represent the state vector for a neural network and $\bar{Q}^{t}$
to represent the idealized state vector introduced here.

$\bar{Q}^{t}\in\\{0,1\\}^{n},$

whose components $\bar{Q}^{t}{}_{i}$ are

$\bar{Q}^{t}{}_{i}=\left\\{\begin{array}[]{ll}1&q_{i}=q^{t}\\\ 0&q_{i}\neq
q^{t}.\end{array}\right.$

The next state vector $\bar{Q}^{t+1}$ is given by the dynamic relation

$\bar{Q}^{t+1}=W^{t+1}\cdot\bar{Q}^{t},$

where the transition matrix $W^{t+1}$, determined by the transition tensor $W$
and the input vector $I^{t+1}$, is

$W^{t+1}=W\cdot I^{t+1}.$

The input vector $I^{t+1}\in\\{0,1\\}^{m}$ has components

$I^{t+1}{}_{j}=\left\\{\begin{array}[]{ll}1&\mathfrak{a}_{j}=\mathfrak{a}^{t+1}\\\
0&\mathfrak{a}_{j}\neq\mathfrak{a}^{t+1},\end{array}\right.$

and the transition tensor $W$ has components

$W_{i}{}^{jk}=\left\\{\begin{array}[]{ll}1&q_{i}=\delta(q_{j},\mathfrak{a}_{k})\\\
0&q_{i}\neq\delta(q_{j},\mathfrak{a}_{k}).\end{array}\right.$

In component form, the dynamic relation can be rewritten as

$\bar{Q}^{t+1}{}_{i}=\sum_{jk}W_{i}{}^{jk}I^{t+1}{}_{k}\bar{Q}^{t}{}_{j}.$ (3)

The reader may wish to check that all three definitions are consistent with
each other. The first definition is popular in the literature, but the third
is most analogous to a neural network.

##  Appendix B Vector Representation of a Pushdown Automaton

Here we review the PDA, or pushdown automaton, which is a DFA with a stack. In
§B.1, we define a stack, and then in §B.2, we use the stack to define a PDA.
§B.2 is analogous to §A.

###  B.1 The stack

We begin by reviewing the stack.

######  Definition B.1.

_(Stack, classical version)_ A stack is a pair $(\Gamma,e)$, where
$\Gamma=\\{\mathfrak{b}_{1},...,\mathfrak{b}_{m_{2}}\\}$ is the stack alphabet
and $e$ is the error character.

At any given time, a stack holds a (possibly empty) string of characters. That
is, its state can be represented by the following definition.

######  Definition B.2.

Let $\Gamma^{*}$ represent the set of strings constructed by the following
rules.

  * •

$\epsilon\in\Gamma^{*}$,

  * •

$\mathfrak{c}S\in\Gamma^{*}$ for all $\mathfrak{c}\in\Gamma$ and
$S\in\Gamma^{*}$.

Here, $\epsilon$ represents the empty string.

There are a few stack operators, which manipulate the character string held by
the stack.

######  Definition B.3.

_(Stack operators, classical version)_ Define the set of stack operators

$op(\Gamma)=\\{\pi_{-},\pi_{0},\pi_{+}(\mathfrak{b}_{1}),...,\pi_{+}(\mathfrak{b}_{m_{2}}))\\},$

where $\pi_{-}$ represents a pop operation, $\pi_{0}$ is the identity
operation, and $\pi_{+}$ is a family of push operators indexed by $\Gamma$.
They act on strings in $\Gamma^{*}$ according to the following rules.

$\pi_{-}\epsilon=\epsilon$ $\pi_{-}\mathfrak{c}S=S$ $\pi_{0}S=S$
$\pi_{+}(\mathfrak{c})S=\mathfrak{c}S.$

Finally, define the read function $r$ according to the following rules.

$r(\epsilon)=e$ $r(\mathfrak{c}S)=\mathfrak{c}.$

To easily generalize to a neural network, we will modify the above stack
definition to obtain a vector representation.

######  Definition B.4.

_(Stack, vectorized version)_

Let

$\mathcal{B}_{(m_{2})}=\\{(1,0,...,0),(0,1,0,...,0),...,(0,...,0,1)\\}$

be the canonical basis of $\mathbb{R}^{m_{2}}$.

A stack $\bar{K}$ is a vector-valued sequence

$\bar{K}=\\{\bar{K}_{0},\bar{K}_{1},...\\},\hskip
36.135pt\bar{K}_{i}\in\mathcal{B}_{(m_{2})}\cup\\{\vec{0}\\},$

with the additional requirement that there exists an integer $s$, called the
_stack size_ , such that

$\bar{K}_{i}\in\mathcal{B}_{(m_{2})}\hskip 36.135pti<s$

and

$\bar{K}_{i}=\vec{0}\hskip 36.135pts\leq i.$

The vector-valued sequence $\bar{K}$ can be determined from a stack state
$k\in\Gamma^{*}$ by setting $\bar{K}_{i}$ to be the one-hot encoding of the
$i$th character $r((\pi_{-})^{i}k)$ of $k$, using $\vec{0}$ to represent $e$.

For the vectorized stack, we group all the stack operators into a single
parametrized operator as defined here.

######  Definition B.5.

_(Parametrized stack operator)_ For any scalar pair

$(\bar{p}_{+},\bar{p}_{-})\in\\{(1,0),(0,1),(0,0)\\}$

and vector

$\bar{C}\in\mathcal{B}_{(m_{2})},$

define the stack operator $\bar{\pi}(\bar{p}_{+},\bar{p}_{-},\bar{C})$ by how
it acts on the stack $\bar{K}$ according to the following relations.

$(\bar{\pi}(\bar{p}_{+},\bar{p}_{-},\bar{C})\bar{K})_{i\geq
1}=\bar{p}_{+}\bar{K}_{i-1}+\bar{p}_{-}\bar{K}_{i+1}+(1-\bar{p}_{+}-\bar{p}_{-})\bar{K}_{i}$
$(\bar{\pi}(\bar{p}_{+},\bar{p}_{-},\bar{C})\bar{K})_{0}=\bar{p}_{+}\bar{C}+\bar{p}_{-}\bar{K}_{1}+(1-\bar{p}_{+}-\bar{p}_{-})\bar{K}_{0}$

It is worth verifying that according to the above definition, the operator
$\bar{\pi}(1,0,\bar{C})$ pushes the vector $\bar{C}$ onto the stack, the
operator $\bar{\pi}(0,1,\bar{C})$ pops the stack, and the operator
$\bar{\pi}(0,0,\bar{C})$ is the identity operator.

In tensor products that will be used momentarily, if any factor is zero, the
entire expression becomes zero. Therefore, instead of using the top of the
stack $\bar{K}$ directly, we will instead use the stack reading vector
$\bar{R}$, which has one additional component that is $1$ when
$\bar{K}_{0}=\vec{0}$ and $0$ otherwise.

######  Definition B.6.

_(Stack Reading)_ Given the top vector of the stack $\bar{K}_{0}$ with
dimension $m_{2}$, we define the stack reading vector $\bar{R}$ to be a vector
of dimension $m_{2}+1$, with components

$\bar{R}_{i}=\left\\{\begin{array}[]{ll}(\bar{K}_{0})_{i}&0\leq i<m_{2}\\\
1-||\bar{K}_{0}||_{L^{\infty}}&i=m_{2}.\end{array}\right.$

###  B.2 A Pushdown Automata (PDA)

The following definition of a PDA closely resembles Hopcroft’s definition.
[29]555There is a minor discrepancy in that Hopcroft’s definition allows for
an additional operation that corresponds to one pop followed by two push
operations. This is mainly provided for convenience and is not an essential
part of the definition.

######  Definition B.7.

_(PDA, classical version)_ A pushdown automaton is a 7-tuple
$(Q,\Sigma,\Gamma,\delta,q_{0},e,F)$, where $Q=\\{q_{1},...,q_{n}\\}$ is a
finite set of states, $\Sigma=\\{\mathfrak{a}_{1},...,\mathfrak{a}_{m_{1}}\\}$
is the finite input alphabet,
$\Gamma=\\{\mathfrak{b}_{1},...,\mathfrak{b}_{m_{2}}\\}$ is the finite stack
alphabet, $\delta:Q\times\Sigma\times\Gamma\rightarrow Q\times op(\Gamma)$ is
the transition function with $op(\Gamma)$ being the set of stack operators
from Definition B.3, $q_{0}\in Q$ is the start state, $e$ is the stack error
character, and $F\subset Q$ is a set of acceptable final states.

Let $\delta_{Q}:Q\times\Sigma\times\Gamma\rightarrow Q$ and
$\delta_{op}:Q\times\Sigma\times\Gamma\rightarrow op(\Gamma)$ represent the
first and second part of the transition function $\delta$. Let $q\in Q$ and
$k\in\Gamma^{*}$. A string of characters $\mathfrak{a}^{1}...\mathfrak{a}^{l}$
can be fed to the PDA, which changes state and stack state according to the
following rules.

$q^{t=0}=q_{0}$ $k^{t=0}=\epsilon$
$q^{t+1}=\delta_{Q}(q^{t},\mathfrak{a}^{t+1},r(k^{t}))$
$k^{t+1}=\delta_{op}(q^{t},\mathfrak{a}^{t+1},r(k^{t}))k^{t}.$

As we are mainly interested in dynamics, we will work in with an arbitrary
string. The following simplified definition focuses on the dynamics of the
PDA.

######  Definition B.8.

_(PDA, dynamic version)_ At any time $t$, the state of a pushdown automaton is

$(q^{t},k^{t})\in\\{q_{1},...,q_{n}\\}\times\Gamma^{*}.$

The next state $(q^{t+1},k^{t+1})$ is given by the dynamic relations

$q^{t+1}=\delta_{Q}^{t+1}(q^{t},k^{t})$
$k^{t+1}=\delta_{op}^{t+1}(q^{t},k^{t})k^{t},$

where $\delta_{Q}^{t+1}(q,k)=\delta_{Q}(q,\mathfrak{a}^{t+1},r(k))$ and
$\delta_{op}^{t+1}(q,k)=\delta_{K}(q,\mathfrak{a}^{t+1},r(k))$.

To easily generalize to a neural network, we will further modify the above
definition to obtain a vector representation of the PDA.

######  Definition B.9.

_(PDA, vectorized dynamic version)_ At any time $t$, the state of a pushdown
automaton is represented by the pair

$(\bar{Q}^{t},\bar{K}^{t}),$

where $\bar{Q}^{t}$ is a one-hot vector encoding the state $q^{t}$ as in
Definition A.3 and $\bar{K}^{t}$ is a vector encoding of the stack $k^{t}$
according to Definition B.4.

The next state pair $(\bar{Q}^{t+1},\bar{K}^{t+1})$ is given by the dynamic
relations

$\displaystyle\bar{Q}^{t+1}$ $\displaystyle=W_{Q}^{t+1}\cdot\bar{Q}^{t}$ (4)
$\displaystyle\bar{K}^{t+1}$ $\displaystyle=\bar{\pi}^{t+1}\bar{K}^{t},$ (5)

where the transition matrix $W_{Q}^{t+1}$ and operator $\bar{\pi}^{t+1}$ are
defined as follows.

The transition matrix $W_{Q}^{t+1}$ is given in component form by

$(W_{Q}^{t+1})_{i}{}^{j}=\sum_{k,l}(W_{Q})_{i}{}^{jkl}\bar{R}^{t}{}_{l}I^{t+1}{}_{k},$

where the components $(W_{Q})_{i}{}^{jkl}$ are chosen to represent the
transition function $\delta_{Q}$ as in Definition A.3 and the stack reading
$\bar{R}^{t}$ is determined from $\bar{K}_{0}^{t}$ as described by Definition
B.6.

The operator $\bar{\pi}^{t+1}$ is given by

$\bar{\pi}^{t+1}=\bar{\pi}(\bar{p}_{+}^{t+1},\bar{p}_{-}^{t+1},\bar{C}^{t+1}),$

where the parameters $\bar{p}_{\pm}^{t+1}$ and vector $\bar{C}^{t+1}$ are

$\bar{p}_{\pm}^{t+1}=\sum_{j,k,l}(W_{p_{\pm}})^{jkl}\bar{R}^{t}{}_{l}I^{t+1}{}_{k}\bar{Q}^{t}{}_{j}$
$\bar{C}^{t+1}{}_{i}=\sum_{j,k,l}(W_{C})_{i}{}^{jkl}\bar{R}^{t}{}_{l}I^{t+1}{}_{k}\bar{Q}^{t}{}_{j}$

where the components $(W_{p_{+}})^{jkl}$, $(W_{p_{-}})^{jkl}$, and
$(W_{C})_{i}{}^{jkl}$ are chosen to represent the transition function
$\delta_{op}$ the same way the components of $W_{Q}$ are chosen.

The reader may wish to check that all three PDA definitions are consistent
with each other, given appropriate choices for the tensors $W_{Q}$,
$W_{p_{+}}$, $W_{p_{-}}$, and $W_{C}$. An example choice of tensor weights is
provided in Appendix E.

##  Appendix C Supporting Proofs

Here, we provide proofs of some claims in §3. We begin by proving Lemma 3.5,
which relates the difference $K_{0}-\bar{K}_{0}$ to the difference
$R-\bar{R}$. Next, we prove Lemma C.1, which encapsulates the key stability
properties of the activation function $h_{H}(x)$ and Lemma C.2, which is used
to relate expressions in the definitions for the operators $\pi$ and
$\bar{\pi}$. Finally, we use both Lemmas C.1 and C.2 to prove Proposition 3.3,
which explains how the operator $\pi$ acts similarly to $\bar{\pi}$.

###### Proof.

(of Lemma 3.5)

We must prove that

$||K_{0}-\bar{K}_{0}||_{L^{\infty}}=||R-\bar{R}||_{L^{\infty}}.$

Since it is clear that

$||K_{0}-\bar{K}_{0}||_{L^{\infty}}\leq||R-\bar{R}||_{L^{\infty}},$

it will suffice to show

$||R-\bar{R}||_{L^{\infty}}\leq||K_{0}-\bar{K}_{0}||_{L^{\infty}},$

which only requires us to confirm that

$|R_{m_{2}}-\bar{R}_{m_{2}}|\leq||K_{0}-\bar{K}_{0}||_{L^{\infty}}.$

We do this by examining two cases, depending on whether $\bar{R}_{m_{2}}=1$ or
$\bar{R}_{m_{2}}=0$.

If $\bar{R}_{m_{2}}=1$, then $\bar{K}_{0}=\vec{0}$, so

$|R_{m_{2}}-\bar{R}_{m_{2}}|=|(1-||K_{0}||_{L^{\infty}})-1|=||K_{0}||_{L^{\infty}}=||K_{0}-\vec{0}||_{L^{\infty}}=||K_{0}-\bar{K}_{0}||_{L^{\infty}}.$

If instead $\bar{R}_{m_{2}}=0$, then there is some index $\hat{i}<m_{2}$ for
which $\bar{R}_{\hat{i}}=(\bar{K}_{0})_{\hat{i}}=1$. We have

$|R_{m_{2}}-\bar{R}_{m_{2}}|=|R_{m_{2}}|=1-||K_{0}||_{L^{\infty}}\leq
1-(K_{0})_{\hat{i}}=(\bar{K}_{0})_{\hat{i}}-(K_{0})_{\hat{i}}\leq||K_{0}-\bar{K}_{0}||_{L^{\infty}}.$

∎

######  Lemma C.1.

Let $\bar{V}$ be a vector with components $\bar{V}_{i}\in\\{0,1\\}$ and let
$V$ be a vector satisfying

$||V-\bar{V}||_{L^{\infty}}\leq\epsilon_{0}$

for some $\epsilon_{0}<\frac{1}{2}$.

Then for all sufficiently small $\epsilon>0$, for all $H$ sufficiently large
depending on $\epsilon_{0}$ and $\epsilon$,

$\max_{i}\left|\bar{V}_{i}-h_{H}\left(V_{i}-\frac{1}{2}\right)\right|\leq\epsilon.$

###### Proof.

Since $\epsilon_{0}<\frac{1}{2}$, choose $H$ sufficiently large so that

$h_{H}\left(-\left(\frac{1}{2}-\epsilon_{0}\right)\right)=1-h_{H}\left(\frac{1}{2}-\epsilon_{0}\right)\leq\epsilon.$

Note that

$\left|\bar{V}_{i}-h_{H}\left(V_{i}-\frac{1}{2}\right)\right|=\left|\bar{V}_{i}-h_{H}\left(\bar{V}_{i}-\frac{1}{2}+(V_{i}-\bar{V}_{i})\right)\right|.$

Pick an arbitrary index $i$. If $\bar{V}_{i}=1$,

$\left|\bar{V}_{i}-h_{H}\left(V_{i}-\frac{1}{2}\right)\right|=1-h_{H}\left(\frac{1}{2}+(V_{i}-\bar{V}_{i})\right)\leq
1-h_{H}\left(\frac{1}{2}-\epsilon_{0}\right)\leq\epsilon.$

If instead $\bar{V}_{i}=0$,

$\left|\bar{V}_{i}-h_{H}\left(V_{i}-\frac{1}{2}\right)\right|=h_{H}\left(-\frac{1}{2}+(V_{i}-\bar{V}_{i})\right)\leq
h_{H}\left(-\left(\frac{1}{2}-\epsilon_{0}\right)\right)\leq\epsilon.$

∎

######  Lemma C.2.

Let $X,\bar{X},Y,\bar{Y},Z,\bar{Z}$ be vectors and let $x,\bar{x},y,\bar{y}$
be scalars. Suppose that all scalars and all vector components lie in the
range $[0,1]$. Suppose furthermore that

$||X-\bar{X}||_{L^{\infty}}\leq\epsilon$
$||Y-\bar{Y}||_{L^{\infty}}\leq\epsilon$
$||Z-\bar{Z}||_{L^{\infty}}\leq\epsilon$ $|x-\bar{x}|\leq\epsilon$
$|y-\bar{y}|\leq\epsilon.$

Then

$xX+yY+(1-x-y)Z=\bar{x}\bar{X}+\bar{y}\bar{Y}+(1-\bar{x}-\bar{y})\bar{Z}+err,$

and

$||err||_{L^{\infty}}\leq 7\epsilon.$

###### Proof.

Let

$\displaystyle err$ $\displaystyle=err_{X}+err_{Y}+err_{Z}$ $\displaystyle
err_{X}$ $\displaystyle=xX-\bar{x}\bar{X}$ $\displaystyle err_{Y}$
$\displaystyle=yY-\bar{y}\bar{Y}$ $\displaystyle err_{Z}$
$\displaystyle=(1-x-y)Z-(1-\bar{x}-\bar{y})\bar{Z}.$

It suffices to estimate each of these error terms individually.

$\displaystyle||err_{X}||_{L^{\infty}}$
$\displaystyle=||xX-\bar{x}\bar{X}||_{L^{\infty}}$
$\displaystyle=||(x-\bar{x})\bar{X}+x(X-\bar{X})||_{L^{\infty}}$
$\displaystyle\leq|x-\bar{x}|||\bar{X}||_{L^{\infty}}+|x|||X-\bar{X}||_{L^{\infty}}$
$\displaystyle\leq\epsilon||\bar{X}||_{L^{\infty}}+|x|\epsilon$
$\displaystyle\leq 2\epsilon.$

By an analogous calculation, we also conclude

$||err_{Y}||_{L^{\infty}}\leq 2\epsilon.$

And

$\displaystyle||err_{Z}||_{L^{\infty}}$
$\displaystyle=||(1-x-y)Z-(1-\bar{x}-\bar{y})\bar{Z}||_{L^{\infty}}$
$\displaystyle=||(\bar{x}-x)\bar{Z}+(\bar{y}-y)\bar{Z}+(1-x-y)(Z-\bar{Z})||_{L^{\infty}}$
$\displaystyle\leq|\bar{x}-x|||\bar{Z}||_{L^{\infty}}+|\bar{y}-y|||\bar{Z}||_{L^{\infty}}+|1-x-y|||Z-\bar{Z}||_{L^{\infty}}$
$\displaystyle\leq\epsilon||\bar{Z}||_{L^{\infty}}+\epsilon||\bar{Z}||_{L^{\infty}}+|1-x-y|\epsilon$
$\displaystyle\leq 3\epsilon$

Finally,

$||err||_{L^{\infty}}\leq||err_{X}||_{L^{\infty}}+||err_{Y}||_{L^{\infty}}+||err_{Z}||_{L^{\infty}}\leq
2\epsilon+2\epsilon+3\epsilon=7\epsilon.$

∎

With these lemmas, we can prove Proposition 3.3.

###### Proof.

(of Proposition 3.3)

Given the assumptions, we will prove that for each $i$,

$||(\pi(p_{+},p_{-},C)K)_{i}-(\bar{\pi}(\bar{p}_{+},\bar{p}_{-},\bar{C})\bar{K})_{i}||_{L^{\infty}}\leq\epsilon.$

Let us examine the general case $i>0$, from which the special case $i=0$ (top
of the stack) will follow.

Fix $i>0$ and let

$V=p_{+}K_{i-1}+p_{-}K_{i+1}+(1-p_{+}-p_{-})K_{i},$
$\bar{V}=\bar{p}_{+}\bar{K}_{i-1}+\bar{p}_{-}\bar{K}_{i+1}+(1-\bar{p}_{+}-\bar{p}_{-})\bar{K}_{i}.$

Note that

$((\pi(p_{+},p_{-},C)K)_{i})_{j}=h_{H}\left(V_{j}-\frac{1}{2}\right)$

and

$(\bar{\pi}(\bar{p}_{+},\bar{p}_{-},\bar{C})\bar{K})_{i}=\bar{V}.$

By Lemma C.1, provided $\epsilon<\frac{1}{14}$, it suffices to show that

$||V-\bar{V}||_{L^{\infty}}\leq 7\epsilon.$

This follows directly from Lemma C.2 with $x=p_{+}$, $X=K_{i-1}$, $y=p_{-}$,
$Y=K_{i+1}$, $Z=K_{i}$ and the corresponding choices for the barred
quantities.

The special case $i=0$ (top of the stack) can be proved the same way by
replacing $K_{i-1}$ with $C$, $K_{i+1}$ with $K_{1}$, and $K_{i}$ with
$K_{0}$. ∎

##  Appendix D List of Symbols

  * $\mathfrak{a},\mathfrak{b},\mathfrak{c}$

Characters belonging to an alphabet.

  * $\mathcal{B}_{(n)}$

The canonical basis of $\mathbb{R}^{n}$:

$\mathcal{B}_{(n)}=\\{(1,0,...,0),(0,1,0,...,0),...,(0,...,0,1)\\}$

  * $C$

A vector representing a character to be pushed onto the differentiable stack
(or, in some contexts, a large positive constant.

  * $\delta$

The transition function of a PDA.

  * $h_{H}(x)$

The sigmoid function:

$h_{H}(x)=\frac{1}{1+e^{-Hx}}$

  * $I^{t}$

A vector representing the input character at time $t$.

  * $K$

A differentiable stack, represented by a sequence of vectors whose components
have values in $[0,1]$.

  * $\bar{K}$

A vectorized classical stack, or ideal stack, represented by a sequence of
vectors whose components are either $0$ or $1$.

  * $K^{t}$

A differentiable stack at time $t$.

  * $K_{i}$

The $i$th vector of a differentiable stack.

  * $K_{0}$

The top, or $0$th vector, of a differentiable stack.

  * $(K_{i})_{j}$

The $j$th component of the $i$th vector of a differentiable stack.

  * $R$

The stack reading, determined from $K_{0}$, with one extra component that
approximates $1$ when $K_{0}$ approximates $\vec{0}$

  * $p_{+}$

A stack push parameter

  * $p_{-}$

A stack pop parameter

  * $\pi(p_{+},p_{-},C)$

The differentiable stack operator

  * $Q$

A vector representing the state of an nnPDA

  * $\bar{Q}$

A vector representing the state of a PDA

  * $Q^{t}$

The state of an nnPDA at time $t$

  * $q$

The state of a PDA

  * $W_{Q}$

The tensor, or neural weights, used to compute the state $Q^{t+1}$ from
$Q^{t}$, $I^{t}$, and $K^{t}_{0}$

  * $W_{p_{\pm}},W_{C}$

The tensors used to compute $p_{+}^{t+1}$, $p_{-}^{t+1}$, and $C^{t+1}$ (see
$W_{Q}$)

  * $(W_{Q})_{i}{}^{jkl}$

The components of the tensor $W_{Q}$

##  Appendix E An Example CFG

For illustrative purposes, we give an example here of a vectorized PDA for the
grammer of balanced parentheses. The goal is to classify strings with
characters ‘(’ and ‘)’ based on whether they close properly. So for example,
the strings $``()"$, $``(())"$, and $``(()())"$ are valid, while the strings
$``)"$, $``(()"$, and $``(()))"$ are invalid. To avoid confusion, we’ll use
$\mathfrak{l}$ to represent the left parenthesis ‘(’ and $\mathfrak{r}$ to
represent the right parenthesis ‘)’, and introduce $\mathfrak{e}$ to represent
the end of the string. With these representations, the example valid strings
are represented by $\mathfrak{l}\mathfrak{r}\mathfrak{e}$,
$\mathfrak{l}\mathfrak{l}\mathfrak{r}\mathfrak{r}\mathfrak{e}$, and
$\mathfrak{l}\mathfrak{l}\mathfrak{r}\mathfrak{l}\mathfrak{r}\mathfrak{r}\mathfrak{e}$,
while the example invalid strings are represented by
$\mathfrak{r}\mathfrak{e}$,
$\mathfrak{l}\mathfrak{l}\mathfrak{r}\mathfrak{e}$, and
$\mathfrak{l}\mathfrak{l}\mathfrak{r}\mathfrak{r}\mathfrak{r}\mathfrak{e}$.

For tensors $W$ with indices $j$, $k$, and $l$, the $j$ index is paired with
state input. Our PDA will have $n=2$ states representing either acceptable
$\smiley$ or rejected $\frownie$. We will represent these with two dimensional
vectors the following way.

$\smiley\rightarrow\begin{pmatrix}1\\\ 0\end{pmatrix}\hskip
36.135pt\frownie\rightarrow\begin{pmatrix}0\\\ 1\end{pmatrix}$

For tensors $W$ with indices $j$, $k$, and $l$, the $k$ index is paired with
the input character. Since the input character alphabet has size $m_{1}=3$, we
will represent the input characters as vectors the following way.

$\mathfrak{l}\rightarrow\begin{pmatrix}1\\\ 0\\\ 0\end{pmatrix}\hskip
36.135pt\mathfrak{r}\rightarrow\begin{pmatrix}0\\\ 1\\\ 0\end{pmatrix}\hskip
36.135pt\mathfrak{e}\rightarrow\begin{pmatrix}0\\\ 0\\\ 1\end{pmatrix}$

Finally, for tensors $W$ with indices $j$, $k$, and $l$, the $l$ index is
paired with the stack reading vector. Our stack alphabet has size $m_{2}=1$ as
a single character must be pushed each time $\mathfrak{l}$ is encountered and
popped each time $\mathfrak{r}$ is encountered. Although the stack vector has
dimension $m_{2}=1$, the reading from stack has dimension $m_{2}+1=2$, with
the additional dimension representing an empty stack reading. The possible
stack reading vectors are as follows.

$nonempty=\begin{pmatrix}1\\\ 0\end{pmatrix}\hskip
36.135ptempty=\begin{pmatrix}0\\\ 1\end{pmatrix}$

###  E.1 State Transition Rules

Given a stack reading and input character, which fix $l$ and $k$ indices
respectively, the $i$ and $j$ components of the transition tensor
$(W_{Q})_{i}{}^{jkl}$ can be interpreted as entries in an adjacency matrix
that acts on the input state vector to give the output state vector.

If $\mathfrak{l}$ is encountered, we should not change state. Thus,

$(W_{Q})_{i}{}^{j00}=(W_{Q})_{i}{}^{j01}=\begin{pmatrix}1&0\\\
0&1\end{pmatrix}.$

If $\mathfrak{r}$ is encountered, then we should not change state unless the
stack is empty, in which case we should change from $\smiley$ to $\frownie$.
Thus,

$(W_{Q})_{i}{}^{j10}=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}\hskip
36.135pt(W_{Q})_{i}{}^{j11}=\begin{pmatrix}0&0\\\ 1&1\end{pmatrix}.$

Finally, if $\mathfrak{e}$ is encountered, then we should not change state
unless the stack is non-empty, in which case we should change from $\smiley$
to $\frownie$. Thus,

$(W_{Q})_{i}{}^{j20}=\begin{pmatrix}0&0\\\ 1&1\end{pmatrix}\hskip
36.135pt(W_{Q})_{i}{}^{j21}=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}.$

###  E.2 Stack Action Rules

The only case where we push is when encountering $\mathfrak{l}$. Thus,

$(W_{p_{+}})^{jkl}=\left\\{\begin{array}[]{ll}1&k=0\\\
0&otherwise\end{array}\right.$

The only case where we pop is when encountering $\mathfrak{r}$. Thus,

$(W_{p_{-}})^{jkl}=\left\\{\begin{array}[]{ll}1&k=1\\\
0&otherwise\end{array}\right.$

It does not matter what happens to the stack when encountering $\mathfrak{e}$,
so for simplicity we may set

$(W_{p_{+}})^{j2l}=(W_{p_{-}})^{j2l}=0.$

Finally, there is only one character in the stack alphabet, so for simplicity
we may set

$(W_{C})_{i}{}^{jkl}=1.$

Alternatively, if we only which to specify a character when pushing, we may
instead set

$(W_{C})_{i}{}^{jkl}=\left\\{\begin{array}[]{ll}1&k=0\\\
0&otherwise.\end{array}\right.$

Either way, the index $i$ must take the value $0$ as the stack alphabet has
size $m_{2}=1$.


.pdfpng.pngconvert #1

# ContactNet: Geometric-Based Deep Learning Model for Predicting Protein-
Protein Interactions

Matan Halfon
School of Computer Science and Engineering
The Hebrew University of Jerusalem
Jerusalem, Israel
<EMAIL_ADDRESS>
Tomer Cohen
School of Computer Science and Engineering
The Hebrew University of Jerusalem
Jerusalem, Israel
<EMAIL_ADDRESS>
Raanan Fattal
School of Computer Science and Engineering
The Hebrew University of Jerusalem
Jerusalem, Israel
<EMAIL_ADDRESS>
Dina Schneidman-Duhovny
School of Computer Science and Engineering
The Hebrew University of Jerusalem
Jerusalem, Israel
<EMAIL_ADDRESS>

###### Abstract

Deep learning approaches achieved significant progress in predicting protein
structures. These methods are often applied to protein-protein interactions
(PPIs) yet require Multiple Sequence Alignment (MSA) which is unavailable for
various interactions, such as antibody-antigen. Computational docking methods
are capable of sampling accurate complex models, but also produce thousands of
invalid configurations. The design of scoring functions for identifying
accurate models is a long-standing challenge. We develop a novel attention-
based Graph Neural Network (GNN), ContactNet, for classifying PPI models
obtained from docking algorithms into accurate and incorrect ones. When
trained on docked antigen and modeled antibody structures, ContactNet doubles
the accuracy of current state-of-the-art scoring functions, achieving accurate
models among its Top-10 at 43% of the test cases. When applied to unbound
antibodies, its Top-10 accuracy increases to 65%. This performance is achieved
without MSA and the approach is applicable to other types of interactions,
such as host-pathogens or general PPIs.

##  1 Introduction

Experimental methods for structure determination of macromolecular complexes,
such as X-ray crystallography and cryo- Electron Microscopy, can not be
applied in a high-throughput manner [4]. Recent progress in deep learning
models for protein folding also enabled modeling of protein-protein complexes
with high accuracy [2, 9, 14]. However, these methods rely on a co-
evolutionary signal from MSA which is not available for many complexes, such
as antibody-antigen, leading to inaccurate predictions [31]. Computational
docking methods for modeling PPIs, while applicable on a larger scale, still
suffer from low accuracy [18]. Docking usually involves two parts: sampling
and scoring. Sampling methods, such as Fast Fourier Transform (FFT) or
geometry-based approaches [24, 11, 15], usually sample accurate models for the
“rigid” docking cases, where there are no significant conformational changes
between the bound and unbound structures. However, the scoring presents a
major challenge in identifying a few accurate models among the thousands that
are generated by the sampling methods.

Much effort has been devoted in developing scoring functions for assessing
docked complexes [5, 1, 23]. Despite this effort, the accuracy remains fairly
low: state-of-the-art scoring functions rank correct models among its Top-10
models in 10% to 40% of the cases for unbound docking [12], depending on the
dataset and the scoring function. The accuracy drops significantly, below 15%,
when the comparative models are used for docking [26]. Recently, there has
been progress in designing scoring functions using deep learning models,
including 3D convolutional [29] and hierarchical rotation-equivariant networks
[8]. However, they were not able to surpass traditional scoring functions,
such as ZRANK [22] and SOAP-PP [7]. Graph representation and GNN models are a
well-suited for protein structures and protein-protein interactions resulting
in some success in scoring tasks [6, 30]. Here, we describe a new GNN-based
model, ContactNet, which is specifically designed to model biological protein-
protein recognition interfaces consisting of short interacting linear
fragments with the appropriate invariances. The model detects and analyzes
contacting patches in protein-protein interfaces to resolve the docked model
validity. Specifically, the network consists of the following processing
stages. First, it encodes an embedding of both the structural (geometric) and
chemical properties of each residue in each input protein. The geometry is
introduced by a variant of graph attention mechanism that limits the
interaction to spatially neighboring amino acids. Second, the inter-protein
distance matrix is used for detecting potentially interacting linear segments,
which are also analyzed and encoded into low-dimensional contact descriptor
vectors. Finally, a sequence of encoding-transformer layers integrates the
information gathered from all the interacting linear segments to score input
docked models. ContactNet was trained and tested on antibody-antigen data and
achieved highly accurate classifications of antibody-antigen models generated
by docking, where it nearly doubled the success rate of state-of-the-art
methods. Specifically, it detected an accurate model among the Top-10 best
scoring for $\sim$43% of the test set, compared to $\sim$22% by current
methods.

##  2 Methods

###  2.1 ContactNet architecture

ContactNet starts by extracting low-level features at the level of neighboring
amino acids in each protein and uses them to analyze larger scale contact
regions and resolve their global interaction across the interface between the
two proteins. This processing pipeline is performed by a sequence of three
modules (Fig. 1):

Figure 1:  ContactNet architecture. A Single protein embedding module. This
module uses sequence, secondary structure, solvent accessibility, and the
$C\alpha-C\alpha$ protein distance matrix. The network learns a new
representation of physico-chemical features using an encoder transformer. B
Contacts embedding module. This module extracts the most contacting and
possibly interacting linear segments from the single protein embedding stage
and encodes them into interaction descriptors. C Interaction transformer
module. The transformer module is trained to classify the entire interaction
interfaces based on these embedded contact descriptors.

Single-protein embedding module  This module uses the chemical properties of
each amino acid in each protein along with its neighboring amino acids and
contextualizes this information in an embedded representation. We implement
this module using a distance aware graph attention layer [27] where $C\alpha$
atoms are the nodes and the edges correspond to amino acids in close proximity
($C\alpha-C\alpha$ distance < 16Å). Specifically, we calculate the attention
weight between two residues as $w_{ij}=softmax(<k_{i},q_{j}>/d_{ij})$ where
$k_{i}=MLP(r_{i})$ and $q_{j}=MLP(r_{j})$ for residue $i$, and obtain a
context-aware representation by $e_{i}=\sum_{0}^{N}w_{i,j}v_{j}$. allows us to
introduce an inductive bias that decouples non-neighboring residues. The
embedded representation is computed for each protein in the complex separately
and is denoted by $e^{receptor}_{i}$ and $e^{ligand}_{i}$.

Contacts embedding module The association between the proteins (binding or
not) is mainly determined by the type of interaction between localized linear
segments. Typically, there are around 6 peptide segments in an average
interface of 1,000Å2 with most of the segments up to 13 amino acids in length
[21, 19]. We carefully design our network architecture to induce its inference
according to these structural considerations.

The inter-protein distogram $D_{ij}$ (distance matrix of the receptor-ligand
complex bipartite-graph) is a fairly sparse, and its non-trivial elements
correspond to contacts between the two proteins. Consequently, we focus our
classification on the neighboring segments that are identified using a non-
maximum-suppression algorithm over the inter-protein distogram matrix
$D_{ij}$. We then extract short linear segments around these amino acids (10
amino acids in each chain direction) from their embedded single-protein
representation, i.e., $[e^{receptor}_{i-L},...,e^{receptor}_{i+L}]$ and
$[e^{ligand}_{j-L},...,e^{ligand}_{j+L}]$, where the length of these segments
is 2L+1. To allow the network to account for the interaction between every
pair of amino acids in the two segments, we generate an interaction descriptor
(Fig. 1B) by tiling each segment along with the other and concatenating the
two, as given by $E_{i,j}(s,t)=[e^{receptor}_{i+s};e^{ligand}_{j+t}]$ [28].
Thus, the spatial coordinates $s,t$ of the resulting 3D tensor,
$E_{i,j}(s,t)$, correspond to different pairs of amino acids, and its third
coordinate parametrizes their embedded representation. By feeding each
$E_{i,j}(s,t)$ through a 2D convolutional network, containing multiple pooling
operators, we allow the model to analyze multiple sub-segments at different
scales and lengths and produce a low-dimensional encoding vector $c_{ij}$ for
each i,j contact. This process is applied over the top 8 non-overlapping
interacting segment pairs detected from the inter-protein distogram Dij.

Interaction transformer module The resulting contact descriptor vectors
$c_{ij}$ are then passed, as separate tokens, to a classification transformer
network (along with a special classification token). This global operator
allows the model to integrate data from all the contacting segments to derive
a final prediction of the validity of the complex. This module is capable of
learning general non-linear relations between the contacts while being
invariant to their order. The resulting classification token is then passed
through an MLP to produce the final prediction.

##  3 Results

Prediction protocol for antigen-antibody complexes. We trained and tested
ContactNet on 875 antibody-antigen structures from the AbDb dataset (see A.1).
The antibodies were modeled ab initio using AlphaFold2-multimer-v1 (AFM) [9]
to simulate real-life scenario where only antibody sequences are available.
Overall, five models were obtained for most of the antibodies. Docking was run
on the antigen and five antibody AFM models using the antibody-antigen
PatchDock protocol (see A.5, Fig. 2). Docking models were re-ranked using
SOAP-PP statistical potential [7] and the top 3000 were assessed by
ContactNet. Finally, we clustered the docking models among the five antibody
AFM models using interface clustering [5] with an RMSD threshold of 5Å.

Figure 2: Prediction protocol for antigen-antibody complexes. The antibody
sequence is modeled via AFM to obtain five modeled structures that are docked
using PatchDock. The top docking models ranked by SOAP-PP score are
reevaluated by ContactNet. Finally, the docking models from the five AFM
antibody models are clustered to reduce redundancy.

ContactNet performance. Overall, due to the sampling protocol (antibody
modeling and docking), acceptable or higher accuracy docking models according
to CAPRI criteria (see A.2) were obtained for 88% of the complexes (out of 85
in the test set), which is the upper bound for our success rate (Fig. 4A).
Most of the correct models produced by docking were of acceptable and medium
accuracy, with high accuracy models sampled rarely. We compared ContactNet to
SOAP-PP statistical potential which defines the state-of-the-art on several
benchmarks and to the five antibody-antigen complex models obtained from the
AFM, as it was shown to outperform state-of-the-art docking methods on several
benchmarks [9, 31].

Figure 3: Performance of ContactNet, AFM, and SOAP-PP on the modeled
antibodies test set. A. Success rate for TopN predictions for ContactNet
(blue), AFM (green), and SOAP-PP (orange). The red line indicates the upper
bound for ContactNet and SOAP-PP due to missing acceptable or higher accuracy
models.B. Top5 models of each method divided into high, medium, and acceptable
accuracy. C. Success rate for topN predictions on the unbound test set for
ContactNet, AFM, and SOAP-PP. D. Success rate for topN in predicting epitopes
for ContactNet, AFM, and SOAP-PP.

We find that ContactNet almost tripled the Top-1 success rate (see A.2)
compared to AFM and SOAP-PP (Table 1, Fig. 4A) for modeled antibodies. The
Top-5 success rate was also significantly higher compared to both AFM and
SOAP-PP. AFM had a better performance compared to SOAP-PP on our modeled
antibodies dataset. Most of the hits selected by ContactNet in the Top-5 were
of medium and acceptable accuracy (67% and 33%), while most of AFM models were
of high accuracy (Fig. 4B). This can be explained by the low number of high-
accuracy models sampled by the docking algorithms.

When tested on 32 unbound antibody-antigen complexes from Benchmark 5.0 [13],
ContactNet achieved a higher performance with a success rate of 68% and 75%
for Top-1 and Top-5 docking models, respectively (Fig. 4C). In contrast, SOAP-
PP had a success rate of 20% and 35% and AFM had a success rate of 20% and
40%, for Top-1 and Top-5 respectively. The use of unbound antibodies should
not affect AFM performance because only the sequence was used as an input.

We also tested ContactNet for epitope prediction using interface assessment
criteria (see A.3) [16]. ContactNet reached a success rate of 50% and 70% for
Top-1 and Top-10 docking models, respectively (Fig. 4D). In contrast, SOAP-PP
had a success rate of 25% (Top-1) and 50% (Top-10) and AFM had a success rate
of 38% (Top-1) and 42% (Top-5).

##  4 Conclusions

We present a novel deep learning architecture to address the problem of
scoring antibody-antigen docking models. We train ContactNet for antibody-
antigen complexes which present significant challenges, including the need to
model antibodies and the lack of MSA that facilitates AFM prediction.
ContactNet has significantly higher accuracy compared to state-of-the-art
methods.

Several key factors contribute to the high performance of ContactNet. First,
the compact 2D distogram representation for the protein and for the antibody-
antigen interface makes the method invariant to transformations. Second, the
network architecture is designed to simulate the biological process of
protein-protein association where the interface contacts are formed by small
complementary patches on the surfaces of the two proteins. The use of a
problem-tailored architecture enables us to derive meaningful information out
of the limited amount of data and create meaningful inductive bias. Finally,
the residue level protein representation not only enables efficient training
of the model using less GPU memory and runtime but also makes the network less
sensitive to the differences between bound and unbound structures which often
have different side-chain orientations.

## References

  * Andrusier et al. [2007] Nelly Andrusier, Ruth Nussinov, and Haim J Wolfson.  Firedock: fast interaction refinement in molecular docking.  _Proteins: Structure, Function, and Bioinformatics_ , 69(1):139–159, 2007.
  * Baek et al. [2021] Minkyung Baek, Frank DiMaio, Ivan Anishchenko, Justas Dauparas, Sergey Ovchinnikov, Gyu Rie Lee, Jue Wang, Qian Cong, Lisa N Kinch, R Dustin Schaeffer, et al.  Accurate prediction of protein structures and interactions using a three-track neural network.  _Science_ , 373(6557):871–876, 2021.
  * Biewald [2020] Lukas Biewald.  Experiment tracking with weights and biases, 2020.  URL https://www.wandb.com/.  Software available from wandb.com.
  * Cheng [2015] Yifan Cheng.  Single-particle cryo-em at crystallographic resolution.  _Cell_ , 161(3):450–457, 2015.
  * Comeau et al. [2004] Stephen R Comeau, David W Gatchell, Sandor Vajda, and Carlos J Camacho.  Cluspro: a fully automated algorithm for protein–protein docking.  _Nucleic acids research_ , 32(suppl_2):W96–W99, 2004.
  * Dai and Bailey-Kellogg [2021] Bowen Dai and Chris Bailey-Kellogg.  Protein interaction interface region prediction by geometric deep learning.  _Bioinformatics_ , 37(17):2580–2588, 2021.
  * Dong et al. [2013] Guang Qiang Dong, Hao Fan, Dina Schneidman-Duhovny, Ben Webb, and Andrej Sali.  Optimized atomic statistical potentials: assessment of protein interfaces and loops.  _Bioinformatics_ , 29(24):3158–3166, 2013.
  * Eismann et al. [2021] Stephan Eismann, Raphael JL Townshend, Nathaniel Thomas, Milind Jagota, Bowen Jing, and Ron O Dror.  Hierarchical, rotation-equivariant neural networks to select structural models of protein complexes.  _Proteins: Structure, Function, and Bioinformatics_ , 89(5):493–501, 2021.
  * Evans et al. [2021] Richard Evans, Michael O’Neill, Alexander Pritzel, Natasha Antropova, Andrew W Senior, Timothy Green, Augustin Žídek, Russell Bates, Sam Blackwell, Jason Yim, et al.  Protein complex prediction with alphafold-multimer.  _BioRxiv_ , 2021.
  * Ferdous and Martin [2018] Saba Ferdous and Andrew CR Martin.  Abdb: antibody structure database—a database of pdb-derived antibody structures.  _Database_ , 2018, 2018.
  * Gray et al. [2003] Jeffrey J Gray, Stewart Moughon, Chu Wang, Ora Schueler-Furman, Brian Kuhlman, Carol A Rohl, and David Baker.  Protein–protein docking with simultaneous optimization of rigid-body displacement and side-chain conformations.  _Journal of molecular biology_ , 331(1):281–299, 2003.
  * Guest et al. [2021] Johnathan D Guest, Thom Vreven, Jing Zhou, Iain Moal, Jeliazko R Jeliazkov, Jeffrey J Gray, Zhiping Weng, and Brian G Pierce.  An expanded benchmark for antibody-antigen docking and affinity prediction reveals insights into antibody recognition determinants.  _Structure_ , 29(6):606–621, 2021.
  * Hwang et al. [2010] Howook Hwang, Thom Vreven, Joël Janin, and Zhiping Weng.  Protein–protein docking benchmark version 4.0.  _Proteins: Structure, Function, and Bioinformatics_ , 78(15):3111–3114, 2010.
  * Jumper et al. [2021] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Žídek, Anna Potapenko, et al.  Highly accurate protein structure prediction with alphafold.  _Nature_ , 596(7873):583–589, 2021.
  * Kozakov et al. [2006] Dima Kozakov, Ryan Brenke, Stephen R Comeau, and Sandor Vajda.  Piper: an fft-based protein docking program with pairwise potentials.  _Proteins: Structure, Function, and Bioinformatics_ , 65(2):392–406, 2006.
  * Lensink and Wodak [2010] Marc F Lensink and Shoshana J Wodak.  Blind predictions of protein interfaces by docking calculations in capri.  _Proteins: Structure, Function, and Bioinformatics_ , 78(15):3085–3095, 2010.
  * Lensink et al. [2007] Marc F Lensink, Raúl Méndez, and Shoshana J Wodak.  Docking and scoring protein complexes: Capri 3rd edition.  _Proteins: Structure, Function, and Bioinformatics_ , 69(4):704–718, 2007.
  * Lensink et al. [2018] Marc F Lensink, Sameer Velankar, Minkyung Baek, Lim Heo, Chaok Seok, and Shoshana J Wodak.  The challenge of modeling protein assemblies: the casp12-capri experiment.  _Proteins: Structure, Function, and Bioinformatics_ , 86:257–273, 2018.
  * London et al. [2010] Nir London, Barak Raveh, Dana Movshovitz-Attias, and Ora Schueler-Furman.  Can self-inhibitory peptides be derived from the interfaces of globular protein–protein interactions?  _Proteins: Structure, Function, and Bioinformatics_ , 78(15):3140–3149, 2010.
  * Méndez et al. [2005] Raúl Méndez, Raphaël Leplae, Marc F Lensink, and Shoshana J Wodak.  Assessment of capri predictions in rounds 3–5 shows progress in docking procedures.  _Proteins: Structure, Function, and Bioinformatics_ , 60(2):150–169, 2005.
  * Pal et al. [2007] Arumay Pal, Pinak Chakrabarti, Ranjit Bahadur, Francis Rodier, and Joël Janin.  Peptide segments in protein-protein interfaces.  _Journal of Biosciences_ , 32(1):101–111, 2007\.
  * Pierce and Weng [2007] Brian Pierce and Zhiping Weng.  Zrank: Reranking protein docking predictions with an optimized energy function.  _Proteins: Structure, Function, and Bioinformatics_ , 67(4):1078–1086, 2007.  doi: https://doi.org/10.1002/prot.21373.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/prot.21373.
  * Renaud et al. [2021] Nicolas Renaud, Cunliang Geng, Sonja Georgievska, Francesco Ambrosetti, Lars Ridder, Dario F Marzella, Manon F Réau, Alexandre MJJ Bonvin, and Li C Xue.  Deeprank: a deep learning framework for data mining 3d protein-protein interfaces.  _Nature communications_ , 12(1):1–8, 2021.
  * Ritchie and Kemp [2000] David W Ritchie and Graham JL Kemp.  Protein docking using spherical polar fourier correlations.  _Proteins: Structure, Function, and Bioinformatics_ , 39(2):178–194, 2000.
  * Schneidman-Duhovny et al. [2005] Dina Schneidman-Duhovny, Yuval Inbar, Ruth Nussinov, and Haim J Wolfson.  Patchdock and symmdock: servers for rigid and symmetric docking.  _Nucleic acids research_ , 33(suppl_2):W363–W367, 2005.
  * Singh et al. [2020] Amar Singh, Taras Dauzhenka, Petras J Kundrotas, Michael JE Sternberg, and Ilya A Vakser.  Application of docking methodologies to modeled proteins.  _Proteins: Structure, Function, and Bioinformatics_ , 88(9):1180–1188, 2020.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Wang et al. [2017] Sheng Wang, Siqi Sun, Zhen Li, Renyu Zhang, and Jinbo Xu.  Accurate de novo prediction of protein contact map by ultra-deep learning model.  _PLoS computational biology_ , 13(1):e1005324, 2017.
  * Wang et al. [2020] Xiao Wang, Genki Terashi, Charles W Christoffer, Mengmeng Zhu, and Daisuke Kihara.  Protein docking model evaluation by 3d deep convolutional neural networks.  _Bioinformatics_ , 36(7):2113–2118, 2020.
  * Wang et al. [2021] Xiao Wang, Sean T Flannery, and Daisuke Kihara.  Protein docking model evaluation by graph neural networks.  _Frontiers in Molecular Biosciences_ , page 402, 2021.
  * Yin et al. [2022] Rui Yin, Brandon Y Feng, Amitabh Varshney, and Brian G Pierce.  Benchmarking alphafold for protein complex modeling reveals accuracy determinants.  _Protein Science_ , 31(8):e4379, 2022.

##  Appendix A Appendix

###  A.1 Dataset preparation

A dataset of $\sim$1,800 antibody-antigen complexes from the AbDb was used
[10]. Complexes with antigens larger than 700 or smaller than 20 amino acids
were discarded, resulting in 1,214 complexes. Because this is a dataset of
bound complex structures, we produced noisy unbound-like models for antibodies
by modeling the antibodies via AFM, thus exposing the docking and the training
to modeled structures. The complexes were divided into train and test using
97% sequence identity cut-off for antibody sequences, The final train set
included 790 complexes, with 85 additional complexes that were used for
validation. The complexes were divided into train and test using 97% sequence
identity cut-off for antibody sequences.

We have also validated our method using 32 unbound antibody-antigen complexes
from the docking Benchmark 5.0 [13] by training a model that excludes all
these complexes. This set contains unbound structures that enable us to test
our method using more accurate antibody structures.

###  A.2 Assessment criteria

Each complex model is assessed for accuracy based on root mean square
deviation (RMSD) from the correct structure, as used at CAPRI [20, 17]. A
docking model is considered acceptable if the ligand $C\alpha$ RMSD after
superposition of the receptors is < 10 Å or the interface $C\alpha$ RMSD is <
4 Å. A docking model is of medium accuracy if ligand $C\alpha$ RMSD is < 5 Å
or interface $C\alpha$ RMSD is < 2 Å. The success rate is the percentage of
benchmark cases with at least one medium or acceptable accuracy model in the
TopN predictions.

###  A.3 Epitope prediction assessment

Antigen interface assessment is performed using Recall and Precision criteria
from CAPRI [16]. Recall is the fraction of correctly predicted complex
interface residues in the model and Precision is the fraction of residues in
the model interface that are the actual complex interface residues. Interface
residue is a residue whose solvent accessible area is lower in the complex (or
model) than in the individual components. A predicted interface is considered
correct if Recall and Precision are at least 0.5. Here, we calculated the
Recall and Precision for the antigen only to estimate the accuracy of epitope
identification.

###  A.4 Training

ContactNet was trained end-to-end to predict binary classification based on
the assumption that the distribution of correct and incorrect complexes is
separable while optimizing the cross-entropy loss. We trained the model with
the WADAM optimizer with a learning rate of 1e-4 that decays 100 times while
training using the cosine decay as a learning rate scheduler with a weight of
5e-3 for the decay factor. The batch size contained 52 docking models,
randomly selected from different complexes for better generalization. One
epoch was defined as 2,000 batches with 100,000 docking models per epoch. The
network was trained for 160 epochs. The major challenge in the training
process was the unbalanced nature of the data. Specifically, there were
hundreds of thousands of negative complexes compared to a small number of
positive ones. To cope with this challenge each batch is composed of 25% of
the positive, acceptable accuracy docking models and 75% of the negative,
incorrect ones. We used the W&B platform for experiment tracking [3] . and
trained the model on a single GPU 2080RTX for 20 hours.

###  A.5 Sampling antibody-antigen complexes

The antibodies were docked to antigens using the antibody-antigen docking
protocol of PatchDock. PatchDock is an efficient geometric rigid docking
method that maximizes shape complementarity [25].Here we used a higher
sampling precision to generate a higher fraction of “positives”, eg.
acceptable accuracy models, for training, typically generating 100,000 docking
models. These models were scored and re-ranked using SOAP-PP statistical
potential [7]. For training, we used 2,500 top-scoring models along with up to
50 positives irrespective of their ranking. For validation, we have used 2,500
top-scoring docking models based on SOAP-PP ranking.

###  A.6 Scoring function

To visualize the discrimination properties of the two scoring functions and
the AFM, we examined the test set funnel plots . We found that ContactNet is
highly selective, classifying most of the docking models as strictly negative
(score = 0.0).When positives are correctly identified (Fig. S1, PDB 1KIP). In
contrast, the funnels of SOAP-PP have a wider spread of docking models across
the range of score values (y-axis). In some cases, ContactNet fails to
identify accurate complexes (Fig. S1, PDB 1IAI). However, even when it fails,
the epitope is often correctly predicted, but the antibody orientation is
incorrect (Fig. S1, PDB 1IAI).

Figure 4: Figure 1S. Funnels for scoring functions. A. ContactNet, AFM, and
SOAP-PP funnels as a function of interface RMSD for the three cases from the
test set (1KIP, 5EZO, and 5IAI). Each dot corresponds to a docking model.
Acceptable accuracy models are shown in red. B. The top scoring models for
each scoring function (ContactNet - blue, AFM - green, SOAP-PP- orange) are
shown at the bottom (overlaid on the gray X-ray structure).