# Encoding Syntactic Constituency Paths for Frame-Semantic Parsing with Graph
Convolutional Networks

Emanuele Bastianelli, Andrea Vanzo, and Oliver Lemon
Interaction Lab, MACS, Heriot-Watt University, Edinburgh, UK
{e.bastianelli, a.vanzo<EMAIL_ADDRESS>

###### Abstract

We study the problem of integrating syntactic information from constituency
trees into a neural model in Frame-semantic parsing sub-tasks, namely Target
Identification (TI), Frame Identification (FI), and Semantic Role Labeling
(SRL). We use a Graph Convolutional Network to learn specific representations
of constituents, such that each constituent is profiled as the production
grammar rule it corresponds to. We leverage these representations to build
syntactic features for each word in a sentence, computed as the sum of all the
constituents on the path between a word and a task-specific node in the tree,
e.g. the target predicate for SRL. Our approach improves state-of-the-art
results on the TI and SRL of ~$1\%$ and ~3.5% points, respectively (+2.5$\%$
additional points are gained with BERT as input), when tested on FrameNet 1.5,
while yielding comparable results on the CoNLL05 dataset to other syntax-aware
systems.

##  1 Introduction

In this paper we focus on the problem of integrating syntactic features in a
neural architecture for the Frame-Semantic parsing Das et al. (2014) process.
Frame-semantic parsing is the task of extracting full semantic frame
structures from text, as defined by Frame Semantics theory Fillmore (1985).
From a theoretical perspective, Frame-Semantic parsing can be decomposed into
three sub-tasks: 1) Target Identification (TI) – identifying target words
acting as lexical units; 2) Frame Identification (FI) – disambiguating each
target into a possible frame; and 3) Semantic Role Labeling (SRL) – extracting
all the possible frame elements for a given frame.

Early neural approaches have focused in this regard on the integration of
features extracted from dependency trees, both for the FI and SRL tasks
Hermann et al. (2014); Kshirsagar et al. (2015); Swayamdipta et al. (2017),
with positive results. Amongst all, SRL is the task that has received more
attention when investigating methods for injecting syntax into neural models,
mostly due to the strict correlation between syntax and argument structures
Punyakanok et al. (2008). Several solutions have been proposed, setting new
baselines over general Frame-semantic parsing and specific SRL corpora. These
include the use of dependency path embeddings Roth and Lapata (2016), the
application of Graph Convolutional Networks (GCNs) to learn representations of
the dependency graphs Marcheggiani and Titov (2017), or restricting the set of
candidate arguments using pruning algorithms He et al. (2018b). Multi-task
learning has been also applied, either directly supervising attention to learn
dependency parsing Strubell et al. (2018) for both TI and SRL, or to
implicitly bias learned encoded representations when jointly training a
simplified syntactic dependency parser Swayamdipta et al. (2018), or a
semantic dependency parser for both FI and SRL Peng et al. (2018).

Although effective, these approaches have focused on exploiting syntactic
dependencies rather than constituency information, partly because dependencies
are more suited to be encoded as features or learned through attention
mechanisms. Semantic roles are technically provided over syntactic
constituents, which directly cast argument boundaries over word sequences.
This is demonstrated also by earlier work on SRL, which relied on constituency
derived features Gildea and Jurafsky (2002); Xue and Palmer (2004); Punyakanok
et al. (2008). It follows that using constituency information should be
beneficial, especially because reconstructing argument boundaries through
dependencies would require an unbounded number of hops among words, making the
problem hard to model in neural architectures Marcheggiani and Titov (2019).
Following this idea, two recent approaches have attempted to rely on such
constituency information to improve SRL performance. Wang et al. (2019) use
linearised representations of constituency trees in different learning
settings, either by extracting salient features, by multi-task learning, or by
combining both approaches in an auto-encoding fashion. Marcheggiani and Titov
(2019), instead, train a GCN with the SRL objective to learn constituent
representations, which are then infused into words through the same GCN via
the message-passing operation Scarselli et al. (2009).

In this paper, we foster the same idea of relying on constituency information
for every sub-task of Frame-semantic parsing, namely TI, FI, and SRL. We train
a GCN to learn specific constituency representations, which are used in turn
to compute syntactic paths between constituency nodes. Our approach is similar
to that of Marcheggiani and Titov (2019), although it significantly differs
in: i) the initialisation and topology of the underlying graph; ii) the lower
number of required parameters; and iii) the way that syntactic information is
infused in every word representation, i.e. computing node-to-node syntactic
paths. We show that our approach improves the state-of-the-art over the main
Frame-semantic parsing benchmark, i.e. the FrameNet corpus Baker et al.
(1998), on the single TI and SRL tasks, and on FI in a joint-learning setting.
Moreover, we demonstrate the generality of the approach by testing the same
network on the CoNLL 2005 dataset Carreras and Màrquez (2005).

##  2 Learning Constituent Representations with Graph Convolutional Networks

In this work, we take inspiration from the seminal work on SRL by Gildea and
Jurafsky (2002) to design constituent-based features. In their work, Gildea
and Jurafsky found discriminant features for a given constituent of a tree to
be the path between the target predicate and the constituent itself. Based on
the same concept, our idea is to use the path connecting each token with a
task-specific reference node as a feature in a sequence labelling setting. For
example, following Figure 1, the path
$\uparrow$vbd$\uparrow$vp$\downarrow$np$\downarrow$jj between the predicate
had and the word little may provide information to discriminate little as the
beginning of a potential argument span in SRL.

Figure 1: Constituency path between the target predicate had and the word
little. At the bottom, the IOB tagging of the corresponding argument spans.

In order to encode a full constituent path as a feature, node representations
have to be learned to properly enrich token encodings inside the network. To
this end, we train a GCN Kipf and Welling (2017), which operates over a graph
representing the constituency tree, learning node (constituent)
representations through convolutional steps. According to the message-passing
approach, the representation of a constituent is updated with all the
representations of the neighbouring nodes at each step. Formally, at the
$(l+1)$-th step, the network evaluates the representation

$H^{(l+1)}=LN(\sigma(AH^{(l)}W^{(l)}+b^{(l)})),$

where $LN$ is a layer normalisation, $\sigma$ is the ReLU activation function,
$A\in[0,1]^{N\times N}$ is the adjacency matrix of the graph corresponding to
a tree, $H^{(l)}\in\mathds{R}^{N\times D}$ is the matrix of activations of the
$l$-th layer, while $W^{(l)}\in\mathds{R}^{D\times E}$ and
$b^{(l)}\in\mathds{R}^{D\times 1}$ are layer-specific trainable weight matrix
and bias. $N$ is the number of nodes in the tree, while $D$ and $E$ are
respectively the input and output dimensionality of the $l$-th layer.
$H^{(0)}=X$ correspond to the matrix of input representations. We initialise
$X$ with trainable embeddings associated with each constituent type, which are
learned together with the other representations. The GCN is trained using
signal from the task-specific objective function.

Each father-children relation of a constituency tree represents the production
rule of a constituency grammar. We propose to rely on this structural
relationship to better profile node representations in our network. To this
end, we arrange the graph representing the tree, encoded through $A$, only
with edges directed from children to father, so that each constituent is
specifically profiled according to the production rule it corresponds to.
Self-loops are also added to feed each constituent with its own
representation. Given the constituent encodings $c_{1},...,c_{N}$ composing
the rows of the output matrix $H^{(l)}$, a path feature $p_{i,j}$ between the
nodes $i$ and $j$ is evaluated as

$p_{i,j}=\sum_{k\in\mathcal{P}_{i,j}}c_{k},$ (1)

where $\mathcal{P}_{i,j}$ is set of indexes of nodes connecting the shortest
path between $i$ and $j$. Figure 2 summarises the whole process of learning
constituent representations and evaluating path features $p_{i,j}$.

Figure 2: Process of learning constituent encodings and evaluating path
features $\mathbf{p}_{2}$ from the node had over the tree in Figure 1. Detail
of feature evaluation for the word little.

##  3 Integrating Constituency Features in Neural Frame-Semantic Parsing

The process of extracting frame-semantic structures from text typically
involves three tasks. Target words evoking frames, i.e. possible lexical
units, are identified in a sentence during the Target Identification (TI)
task. Frame Identification (FI) aims to classify each lexical unit $l$ into a
possible frame $f$. For each retrieved $l$ and $f$, SRL is performed to
identify and classify the set of related arguments. In this paper, we want to
assess whether our approach of encoding constituency information is beneficial
for each of these sub-tasks.

In order to pair textual information with the constituency path encodings out
of our GCN, we evaluate two encoded sequences $\mathbf{a}=a_{1},...,a_{n}$ and
$\mathbf{b}=b_{1},...,b_{n}$ through the encoding block showed in Figure 3,
which computes:

$\displaystyle\mathbf{a}=LN(BiLSTM(\mathbf{e}\oplus\mathbf{p}_{root})+\mathbf{e}),$
$\displaystyle\mathbf{b}=LN(BiLSTM(\mathbf{e}\oplus\mathbf{p}_{l})+\mathbf{e}),$
(2)

where $LN$ is a normalization layer, $BiLSTM$ is a bi-directional LSTM encoder
Schuster and Paliwal (1997) and $\mathbf{e}=e_{1},...,e_{n}$ is the sequence
of input textual embeddings of a sentence. Residual connections are applied
here to $\mathbf{e}$ to allow the gradient to flow when fine-tuning them. The
sequences $\mathbf{p_{root}}=p_{1,{root}},...,p_{n,{root}}$ and
$\mathbf{p_{l}}=p_{1,l},...,p_{n,l}$ are sequences of token-wise constituency
path features, evaluated as in Equation 1, where the reference node $j$ has
been set as the root of the tree and a predicate target word corresponding to
the lexical unit $l$.111We use the first word for multi-token targets. To be
consistent with (1), when using the $p_{i,j}$ notation, the positional index
$i$ of a word in the input text will correspond to its node index in the
tree.222Since we do not consider the word level in the tree, we create a
correspondence between POS-tags and words in term of indexes. Therefore the
encoded sequences $\mathbf{a}$ and $\mathbf{b}$ contain the root-centred path
features and the predicate-centered path features, respectively. The TI and FI
tasks rely only on the first one, whereas SRL makes use of both the
representations, as explained in the following.

Figure 3: The two encoding backbones. The textual embeddings are fed with the
token sequence, while the GCN receives the corresponding syntactic tree as
input.

###  3.1 Target Identification

The TI task is shaped as a sequence labelling task using the IOBC labelling
scheme, where the label C is used to deal with discontinued spans. Given the
input sequence $\mathbf{x}=x_{1},...,x_{n}$, a Conditional Random Field (CRF)
layer Lafferty et al. (2001) is applied to obtain the sequence of possible
target spans $\mathbf{t}=t_{1},...,t_{n}$, with $t_{i}\in\\{\text{{B-Lu},
{I-Lu}, {C-Lu}, {O}}\\}$. For example, the sentence “I\O tried\B-LU
setting\B-LU things\O down\C-LU” has two lexical units: tried and setting
down. The CRF thus models the conditional probability333From now on, we drop
the condition on the learned parameters in the probability for the sake of
readability.

$P(\mathbf{t}|\mathbf{x})=\frac{1}{Z}\text{exp}(\sum_{i=1}^{n}E_{x_{i},t_{i}}+\sum_{i=0}^{n}T_{t_{i},t_{i+1}})$

where emission scores $E_{x_{i},t_{i}}$ are computed from the syntactic-
augmented encodings $a_{1},...,a_{n}$, and transitions $T_{t_{i},t_{i+1}}$ are
learned during training. The most likely label sequence is computed through
Viterbi decoding at test time. Given a batch of $D$ sentences, the network is
trained by minimising the loss
$\mathcal{L}_{TI}=-\frac{1}{D}\sum_{i=1}^{D}\text{log}P(\mathbf{t}_{i}|\mathbf{x}_{i})$.

###  3.2 Frame Identification

Frame Identification is treated as a multi-classification problem over the
targets, i.e. lexical units, identified during the TI. We model the
probability of a lexical unit $l$ evoking a frame $f$ as

$P(f|l)\propto\text{exp}(W^{(3)}\>\sigma(W^{(2)}\;\sigma(W^{(1)}\;t^{l}))),$

where $\sigma$ is the Leaky-ReLU activation function Maas et al. (2013), and
$t^{l}$ is an encoded representation of $l$ defined as

$t^{l}=\sum_{m\in\mathcal{T}^{l}}a_{m}.$ (3)

with $\mathcal{T}^{l}$ the set of word indexes of the target span for the
lexical unit $l$, and $a_{m}$ are encodings from the sequence in Equation 2.
The FI is trained by minimising the average cross-entropy loss

$\mathcal{L}_{FI}=-\frac{1}{D}\sum_{i=1}^{D}\frac{1}{|\mathcal{T}_{i}|}\sum_{l\in\mathcal{T}_{i}}\text{log}P(f|l),$

where $\mathcal{T}_{i}$ is the set of gold targets for the $i$-th example. A
mask obtained from the FrameNet ontology is applied to penalise frames that
are not evoked by the identified lexical unit.

###  3.3 Semantic Role Labeling

Semantic Role Labeling can be operationally decomposed into Argument
Identification (AI) and Argument Classification (AC). SRL has been recently
tackled with two main approaches. On the one hand, AI is bypassed by computing
all the possible sentence subsequences, and then classifying each subsequence
against the set $\mathcal{A}^{f}\cup{\varnothing}$ of possible frame elements
for a given frame $f\in\mathcal{F}$, where $\varnothing$ is the no-frame-
element label Yang and Mitchell (2017). This approach may lead to limiting the
maximum length of the computed subsequences, leaving out some wide-covering
arguments. On the other hand, AI and AC have been tackled together as an IOB-
based sequence labelling task, where the label space has been defined as
$\\{\\{\texttt{B},\texttt{I}\\}\times\mathcal{A}^{\mathcal{F}}\\}\cup\\{\texttt{O}\\}$
Strubell et al. (2018). When it comes to datasets like FrameNet, where
$|\mathcal{A}^{\mathcal{F}}|=\text{725}$, the number of parameters increases
drastically, especially when bilinear matrix operations are applied to score
tokens against predicates, where the sole bilinear layer can reach up to ~95M
parameters.

To overcome this issue, we treat the AI and AC as two separate tasks, making
the number of parameters drop from 95M to ~3M444These numbers indeed are
proportional to the dimensionality of the inputs. However, their ratio would
be the same. . We use a hierarchy of two CRFs, one for each task (see Fig. 4).
The first extracts the argument span from a sentence representation using a
bilinear operation. The second, instead, operates over the resulting sequence
of spans, assigning a frame element label to each of them. This second CRF
helps in contextualising frame elements with each other.

Figure 4: AI and AC sub-networks on the right and on the left, respectively.

#### Argument Identification (AI)

For a frame $f$ and related lexical unit $l$, the AI task is modelled as the
conditional probability $P(\mathbf{s}|\mathbf{x},l,f)$, where
$\mathbf{s}=s_{1},...,s_{n}$ is a sequence of label in the IOB2 notation, i.e.
$s_{i}\in\\{\text{{B}, {I}, {O}}\\}$, denoting the argument spans. Similarly
as in Section 3.1, we employ a CRF to model the conditional probability, with
the difference that emission scores are computed through a bilinear operation
between tokens and predicate representations, in order to capture interactions
between each token $x_{i}$ and the current pair $(l,f)$. Given $l$, $f$ and
the encoding of the $i$-th token $b_{i}$ from Eq. 2, we compute per-frame IOB2
token emissions through the bilinear operation

$\displaystyle
pr^{(l,f)\top}\;U\;pb_{i},\;\>pr^{(l,f)}=tanh(V^{(1)}z^{(l,f)}),$ (4)
$\displaystyle pb_{i}=tanh(V^{(2)}b_{i}),$

with $z^{(l,f)}=e^{l}\oplus t^{l}\oplus e^{f}$, and $V^{(1)},V^{(2)}$ are
trainable weight matrices. Here, $e^{l}$ and $e^{f}$ are lexical unit and
frame learned embeddings, while $t^{l}$ is the target representation evaluated
in Equation 3.

#### Argument Classification (AC)

Given a sequence of argument spans $\mathbf{s}^{f}$555We drop the $l$
subscript for the sake of readability. for a frame and lexical unit $(l,f)$
from the AI step, the AC is modelled as the conditional probability
$P(\mathbf{a}|\mathbf{x},l,f,\mathbf{s}^{f})$, where
$\mathbf{a}=a_{1},...,a_{u}$ is a sequence of frame element labels, with each
$a_{w}\in\mathcal{A}^{f}$ being an frame element label associated with the
$w$-th argument span from $\mathbf{s}^{f}$. Single vector representations
$r_{w}$ for each span are computed as

$r_{w}=\sum_{m\in\mathcal{S}^{f}_{w}}b_{m},$

where $\mathcal{S}^{f}_{w}$ is the subset of word indexes of the $w$-th
argument span, extracted from $\mathbf{s}^{f}$. Each vector in the sequence
$r_{1},...,r_{u}$ is then concatenated with the predicate representation
$z^{(l,f)}$ from Equation 3.3, and projected through $q_{w}=tanh(Yr_{w}\oplus
z^{(l,f)})$. $P(\mathbf{a}|\mathbf{x},l,f,\mathbf{s}^{f})$ is evaluated with a
CRF Layer which computes emission probabilities over the inputs
$q_{1},...,.q_{u}$. The SRL is trained by optimising the loss
$\mathcal{L}_{SRL}$ given by

$\displaystyle-\frac{1}{D}\sum_{i=1}^{D}\frac{1}{|\mathcal{F}_{i}|}\sum_{(l,f,\mathbf{s})\in\mathcal{F}_{i}}\Big{[}$
$\displaystyle\text{log}P(\mathbf{s}|\mathbf{x}_{i},l,f)+$
$\displaystyle\text{log}P(\mathbf{a}|\mathbf{x}_{i},l,f,\mathbf{s}^{f})\Big{]},$

where $\mathcal{F}_{i}=\\{\langle
l_{1},f_{1},\mathbf{s}_{1}\rangle,...,\langle
l_{q},f_{q},\mathbf{s}_{q}\rangle\\}$ is the set of gold frame annotations for
the $i$-th example. At inference time, Viterbi decoding is applied for both
the AI and AC tasks to evaluate the most probable tag and frame element label
sequences. A theory-based mask extracted from the FrameNet ontology is applied
to the emission matrix to penalise frame element labels that are not
associated with the current frame.

##  4 Experimental Evaluation

This section reports the evaluation procedure and results obtained by the
proposed model on the different tasks with respect to existing approaches.

###  4.1 Experimental Setup

Constituency path features in our architectures are validated firstly on
FrameNet 1.5 (FN15) Baker et al. (1998), and on CoNLL-2005 (CN05) Carreras and
Màrquez (2005) to verify the generality of the approach. For both datasets, we
apply the original data split as in Das et al. (2014) for FN15, and as in
Carreras and Màrquez (2005) on CN05. Results are obtained through the official
evaluation of the SemEval07 shared task for frame-semantic parsing Baker et
al. (2007) (FN15) and the CoNLL-2005 shared task for Semantic Role Labeling
(CN05).666https://www.cs.upc.edu/~srlconll/soft.html

The model is implemented using PyTorch Paszke et al. (2017) and AllenNLP
Gardner et al. (2017), and trained on RTX 2080Ti GPUs. The best
hyperparameters are obtained tuning the model on the development set, via grid
search using early stopping. We concatenate POS tag embeddings to input text
embeddings, obtained using spaCy Honnibal and Montani (2017) for FN15, or
directly from gold annotations for CN05. Constituent trees are obtained
through the Berkeley Neural Parser Kitaev and Klein (2018), using the English
pre-trained model on FN15; for CN05 we generate the syntactic trees of the
development and test sets using the model obtained on the CN05 training set.
For the GCN, only $l=2$ layers have been used, to make each constituent take
representations only from its children and grandchildren. We use the Adam
optimizer Kingma and Ba (2014) with weight decay fix (BERTAdam), with an
initial learning rate of $2\times 10^{-5}$, which is decreased once no
improvements are observed for 5 epochs. We regularise the model using dropout
on encoders and feed-forward layers, while L2 regularisation is used on the
CRFs’ transition matrices and bilinear weight matrix.777All the code,
experimental setup, data and parameter configurations for all the experiments
available at www.Anon.

We test different configurations of textual embeddings (OURS-*), disabling or
enabling the GCN features (*-GCN). For example, in OURS-ELMo we use ELMo
Peters et al. (2018) as input layer, without syntax features. We also include
a joint learning setting (OURS-BERT-GCN-JL), where the three tasks are jointly
optimised by summing the losses
($\mathcal{L}=\mathcal{L}_{\text{TI}}+\mathcal{L}_{\text{FI}}+\mathcal{L}_{\text{SRL}}$)
and BERT Devlin et al. (2019) is used as input layer.

###  4.2 FrameNet 1.5 Results

In this section, we report the evaluation on FN15 for each tasks presented in
Section 3.

#### Target Identification

Model | P | R | F1
---|---|---|---
Das et al. (2014) | $37.5$ | $57.5$ | $45.4$
Swayamdipta et al. (2017) | $-$ | $-$ | $73.2$
OURS-ELMo | $69.84$ | 78.88 | $74.08$
OURS-ELMo-GCN | 70.08 | $78.72$ | 74.15
OURS-BERT | $71.71$ | $78.51$ | $74.96$
OURS-BERT-GCN | $70.66$ | 84.12 | 76.80
OURS-BERT-GCN-JL | 72.59 | $79.43$ | $75.86$
Table 1: Precision, Recall and F1 of the Target Identification task.

Table 1 shows the results of TI. In addition to neural state-of-the-art
systems, we also report the rule-based baseline computed on the FN15 test set
followingDas et al. (2014). The proposed architecture outperforms existing
approaches in the literature, improving the state-of-the-art model in
Swayamdipta et al. (2017) by ~$1\%$ of F1 on comparable inputs, and an
additional $2.65\%$ points are gained when using BERT. The syntax encoding
contribution seems to be evident across the different input layers, with a
more consistent improvement ($1.84\%$) on BERT. Joint learning here acts as a
regulariser, improving the Precision with respect to the single task setting.
The model exposes good generalisation capabilities, correctly identifying
$46.47\%$ of the 402 out-of-vocabulary targets contained in the test set.

However, the final performance of TI is not easy to assess, mostly due to the
well-known issue of the FN1.5 test set of missing a considerable amount of
unannotated targets Yang and Mitchell (2017).

#### Frame Identification

Model | Acc
---|---
Das et al. (2014) | $83.6$
Hermann et al. (2014) | $88.4$
Hartmann et al. (2017) | $87.6$
Yang and Mitchell (2017) | $88.2$
Peng et al. (2018) | $89.9$
OURS-ELMo | $88.89$
OURS-ELMo-GCN | $88.82$
OURS-BERT | $89.90$
OURS-BERT-GCN | $89.83$
OURS-BERT-GCN-JL | 90.10
Table 2: Frame Identification results using gold targets, in terms of
Accuracy.

In Table 2 we report the results of FI using gold targets. All the
configurations are comparable with results in literature, while OURS-BERT-GCN-
JL outperforms the state-of-the-art model from Peng et al. (2018) by $0.2$,
suggesting that jointly learning the whole frame-semantic parsing process
provides shared representations that result beneficial for the FI. However,
this result is in line with Peng et al. (2018), where multi-task learning is
used to exploit the contribution of a purely syntactic task. Overall, our
features do not seem to provide a direct contribution for FI when trained in a
single-task fashion.

#### Semantic Role Labeling

Model | P | R | F1
---|---|---|---
Das et al. (2014)† | $65.6$ | $53.8$ | $59.1$
Kshirsagar et al. (2015)† | $66.0$ | $60.4$ | $63.1$
Yang and Mitchell (2017)† | $70.2$ | $60.2$ | $65.5$
Swayamdipta et al. (2018) | $69.2$ | $69.0$ | $69.1$
Marcheggiani and Titov (2019) | $69.8$ | $68.8$ | $69.3$
OURS-ELMo | $63.89$ | $67.36$ | $65.58$
OURS-ELMo-GCN | 72.02 | 73.70 | 72.85
OURS-BERT | $71.19$ | $74.26$ | $72.69$
OURS-BERT-GCN | $74.23$ | 76.94 | 75.56
OURS-BERT-GCN-JL | 74.56 | $74.43$ | $74.50$
Table 3: Semantic Role Labeling results with gold targets and frames.

SRL results are shown in Table 3. The proposed model obtains state-of-the-art
results, outperforming all the existing approaches on SRL with gold targets
and frames, with an improvement of $3.55\%$ over Marcheggiani and Titov (2019)
in comparable settings, and gaining additional $2.71$ points when applying
BERT. SRL is the task where syntax encodings provide the largest contribution,
especially when paired with the ELMo contextual embeddings. In this setting,
GCNs allow to gain up to $7.27\%$ of F1. This behaviour is mainly due to the
nature of the SRL task. In fact, as already reported in Section 1, argument
boundaries are defined by the syntactic constituents spanning sub-trees. Such
relationships seem to be well captured by our constituency path features.
However, when using BERT as input layer, such a large improvement is not
observed (i.e. “only” $2.87\%$). This is due to the deeper contextual
representations provided by BERT, whose Transformer-based architecture already
captures meaningful representations of the sentence’s syntactic structure. In
fact, it BERT’s ability of specialising some of its attention heads to recover
short-range syntactic dependencies has been observed Htut et al. (2019);
Jawahar et al. (2019); Hewitt and Manning (2019); here we show that pairing
this information to explicit constituent encoding allows to produce richer
representations. Jointly learning the tasks does not result in learning better
shared representations for SRL, although the higher Precision suggests a
regularisation benefit of such a learning pattern.

###  4.3 Impact of syntax: ablation study

We finally run an ablation study on FN15, in order to show the clear
contribution of constituency path features when changing different input
textual embeddings. For this analysis, we select SRL, because it seems to be
the task benefitting the most from the syntactic features.

| SRL |
---|---|---
Input | No-Gcn | Gcn | gain
GloVe | $49.13$ | $68.23$ | $+19.1$
ELMo | $65.58$ | $72.85$ | $+7.27$
BERT | $72.69$ | $75.56$ | $+2.87$
Table 4: Ablation on the use of constituency features with different input
layers for the SRL on FN15.

Table 4 reports the results of this ablation. It is interesting to see how the
contribution of constituency feature encodings decreases as richer and more
complex word embeddings are introduced. In fact, contextual embeddings like
ELMo and BERT already encode some sort of dependency relations. However,
results show that our constituency features complement such syntactic
information. The contribution of syntax is strongly evident especially when
using GloVe non-contextual embeddings, bringing the model $1$ point from the
previous state-of-the-art Marcheggiani and Titov (2019), which uses contextual
embeddings, with an absolute improvement of $19.1\%$.

###  4.4 CoNLL-2005 Results

In the following, we report the experiment on CN05, performed to assess the
ability of the proposed model to scale to similar problems. We use the
hyperparameters obtained on FN15, and tune the best epoch on the CN05
development set.

#### Target Identification/Predicate Detection

Model | P | R | F1
---|---|---|---
WSJ Test |  |  |
He et al. (2017) | $94.5$ | $98.5$ | $96.4$
Strubell et al. (2018) | $98.9$ | $97.9$ | $98.4$
OURS-GloVe | $98.39$ | $99.01$ | $98.70$
OURS-GloVe-GCN | $98.64$ | $98.88$ | $98.76$
Brown Test |  |  |
He et al. (2017) | $89.3$ | $95.7$ | $92.4$
Strubell et al. (2018) | $95.5$ | $91.9$ | $93.7$
OURS-GloVe | $90.15$ | $95.65$ | $92.82$
OURS-GloVe-GCN | $90.55$ | $92.91$ | $91.71$
Table 5: Predicate detection results on the CN05 dataset.

Table 5 shows the results of Target Identification (or Predicate Detection).
For fairness, we report results of our model without contextual embeddings,
since other approaches in the literature rely on these input layers. The
proposed model obtains state-of-the-art results for in-domain examples,
whereas it seems to suffer from overfitting when applied to out-of-domain
data.

#### Semantic Role Labeling

We report the results of our approach for SRL on CoNLL-2005. For such
analysis, we use BERT as input layer, best-performing on FN15.

Model | P | R | F1
---|---|---|---
WSJ Test |  |  |
He et al. (2018a) | $84.2$ | $83.7$ | $83.9$
Tan et al. (2018) | $84.5$ | $85.2$ | $84.8$
Li et al. (2019) | $87.9$ | $87.5$ | $87.7$
Strubell et al. (2018)† | $86.02$ | $86.05$ | $86.04$
Ouchi et al. (2018) | $88.2$ | $87.0$ | $87.6$
Wang et al. (2019) | $-$ | $-$ | $88.2$
Marcheggiani and Titov (2019) | $87.7$ | $88.1$ | $87.9$
OURS-BERT | $87.01$ | $87.36$ | $87.18$
OURS-BERT-GCN | $87.46$ | $87.87$ | $87.66$
Brown Test |  |  |
He et al. (2018a) | $74.2$ | $73.1$ | $73.7$
Tan et al. (2018) | $73.5$ | $74.6$ | $74.1$
Li et al. (2019) | $80.6$ | $80.4$ | $80.5$
Strubell et al. (2018)† | $76.7$ | $76.4$ | $76.5$
Ouchi et al. (2018) | $76.0$ | $70.4$ | $73.1$
Wang et al. (2019) | $-$ | $-$ | $79.3$
Marcheggiani and Titov (2019) | $80.5$ | $80.7$ | $80.6$
OURS-BERT | $78.76$ | $79.56$ | $79.16$
OURS-BERT-GCN | $80.44$ | $81.21$ | $80.82$
Table 6: SRL results with gold predicates on the CN05 dataset. $\dagger$
models do not use contextual embeddings.

Table 6 shows the results of such experiments. Although our model does not
overcome state-of-the-art results, it shows its competitiveness. Both on the
in-domain (WSJ) and out-domain (Brown) test sets, syntactic encodings provide
an important contribution, consistently improving the performance of the
network. The smaller gap between the syntactic and non-syntactic one with
respect to results over FN15 may be partially due to the different (and
higher) complexity of the CN05 constituency trees. In fact, when looking at
the constituent vocabulary, we observe that the small amount of available
constituents in FN15 (74) is not even comparable to the vocabulary size of
CN05 constituents (1170).

##  5 Related Work

#### Graph Neural Networks to encode syntax

The structural information conveyed by syntactic trees has been encoded in
neural models through Graph Neural Networks (GNNs) Scarselli et al. (2009) in
several text processing applications. The Syntactic GCN framework has been
applied to incorporate syntactic Bastings et al. (2017) and semantic
Marcheggiani et al. (2018) structures by applying GCN to Neural Machine
Translation. On the same task, Beck et al. (2018) build a graph-to-sequence
encoder using a Gated GNN Li et al. (2016), which accounts for the whole
dependency structures by adding dependency labels as additional nodes to the
graph. Syntax encoding has been investigated also in the context of the Event
Extraction task, that is the extraction of specified classes of events from
texts. Nguyen and Grishman (2018) apply the Syntactic GCN framework to inject
dependency information to characterise event detection. Liu et al. (2018),
instead, leverage syntactic dependency shortcuts to build local sub-graph
representations of each node, encoded through an Attention-based GCN. Graph
convolutions have also been applied to learn syntactic and semantic embeddings
Vashishth et al. (2019) in an unsupervised fashion, which are shown to provide
advantages when integrated in other tasks. Finally, Li et al. (2018) propose a
Segment Graph Convolutional and Recurrent NN, which operates over word
embedding and syntactic dependencies, to classify relations from clinical
notes.

#### Syntax-aware neural models for Frame-semantic parsing

Identifying solutions to model syntax in neural models to improve Frame-
semantic parsing related tasks has been a main concern in the community in the
last five years. These have ranged from manual feature engineering Hermann et
al. (2014); Kshirsagar et al. (2015); Swayamdipta et al. (2017), to learning
dependency path embeddings Roth and Lapata (2016), to encoding syntactic
dependency structures via GCNs Marcheggiani and Titov (2017). Learning
syntactic Strubell et al. (2018) or semantic Peng et al. (2018) dependency
parsing as auxiliary tasks in a multi-task learning settings has found
successful application, especially when the sub-task outputs were directly
injected as features.

Only two approaches have tackled the problem of integrating constituency
information. Wang et al. (2019) propose to linearise the constituency tree
using the model from Gómez-Rodríguez and Vilares (2018), and apply a
combination of learning techniques to improve sequence labelling performance.
Marcheggiani and Titov (2019), instead, apply a GCN over the constituency tree
to learn constituent boundaries to be injected in word sequence
representations. In this work, we also apply a GCN, although our primary aim
is to directly learn constituent representations. Whereas Marcheggiani and
Titov start from an empty tree updated only with word embedding features, we
initialise it with constituent specific embeddings. Moreover, we rely on a
directed graph to profile constituent representations as the grammar rules
they correspond to. This configuration allows us to learn a more compact
model, with a single matrix of parameters for each layer, against the six
weight matrices required by their approach.888Please refer to Marcheggiani and
Titov (2019) for details. Finally, we inject syntactic representations into
words by explicitly computing constituency path features.

##  6 Conclusions

In this work, we investigated the integration of structural information from a
constituent tree in a neural model for Frame-semantic parsing. Constituent
representations are learned through a GCN, and used to build constituency path
features to be added to every word representation in a sequence. We tested our
approach on all the Frame-semantic parsing sub-tasks, namely Target
Identification, Frame Identification, and Semantic Role Labeling, showing that
such features contribute mainly on the TI and the SRL tasks.

Constituency path features can be applied to other sequence labelling based
tasks, e.g. Named-Entity Recognition. Moreover, other modifications of GCNs
have to be tested in this same framework, e.g. to assess whether Attention-
based GCN may learn more refined constituent representations. Finally, these
representations may be used in a node-classification approach, inspired by
seminal works Gildea and Jurafsky (2002), in an attempt to move away from the
well-used sequence labelling model of recent years.

## References

  * Baker et al. (2007) Collin Baker, Michael Ellsworth, and Katrin Erk. 2007.  SemEval-2007 task 19: Frame semantic structure extraction.  In _Proceedings of the Fourth International Workshop on Semantic Evaluations (SemEval-2007)_ , pages 99–104, Prague, Czech Republic. Association for Computational Linguistics.
  * Baker et al. (1998) Collin F. Baker, Charles J. Fillmore, and John B. Lowe. 1998.  The Berkeley FrameNet project.  In _36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, Volume 1_ , pages 86–90, Montreal, Quebec, Canada. Association for Computational Linguistics.
  * Bastings et al. (2017) Joost Bastings, Ivan Titov, Wilker Aziz, Diego Marcheggiani, and Khalil Sima’an. 2017.  Graph convolutional encoders for syntax-aware neural machine translation.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 1957–1967, Copenhagen, Denmark. Association for Computational Linguistics.
  * Beck et al. (2018) Daniel Beck, Gholamreza Haffari, and Trevor Cohn. 2018.  Graph-to-sequence learning using gated graph neural networks.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 273–283, Melbourne, Australia. Association for Computational Linguistics.
  * Carreras and Màrquez (2005) Xavier Carreras and Lluís Màrquez. 2005.  Introduction to the CoNLL-2005 shared task: Semantic role labeling.  In _Proceedings of the Ninth Conference on Computational Natural Language Learning (CoNLL-2005)_ , pages 152–164, Ann Arbor, Michigan. Association for Computational Linguistics.
  * Das et al. (2014) Dipanjan Das, Desai Chen, André F. T. Martins, Nathan Schneider, and Noah A. Smith. 2014.  Frame-semantic parsing.  _Comput. Linguist._ , 40(1):9–56.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Fillmore (1985) Charles J. Fillmore. 1985.  Frames and the semantics of understanding.  _Quaderni di Semantica_ , 6(2):222–254.
  * Gardner et al. (2017) Matt Gardner, Joel Grus, Mark Neumann, Oyvind Tafjord, Pradeep Dasigi, Nelson F. Liu, Matthew Peters, Michael Schmitz, and Luke S. Zettlemoyer. 2017\.  Allennlp: A deep semantic natural language processing platform.
  * Gildea and Jurafsky (2002) Daniel Gildea and Daniel Jurafsky. 2002.  Automatic labeling of semantic roles.  _Comput. Linguist._ , 28(3):245–288.
  * Gómez-Rodríguez and Vilares (2018) Carlos Gómez-Rodríguez and David Vilares. 2018.  Constituent parsing as sequence labeling.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 1314–1324, Brussels, Belgium. Association for Computational Linguistics.
  * Hartmann et al. (2017) Silvana Hartmann, Ilia Kuznetsov, Teresa Martin, and Iryna Gurevych. 2017.  Out-of-domain FrameNet semantic role labeling.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers_ , pages 471–482, Valencia, Spain. Association for Computational Linguistics.
  * He et al. (2018a) Luheng He, Kenton Lee, Omer Levy, and Luke Zettlemoyer. 2018a.  Jointly predicting predicates and arguments in neural semantic role labeling.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 364–369, Melbourne, Australia. Association for Computational Linguistics.
  * He et al. (2017) Luheng He, Kenton Lee, Mike Lewis, and Luke Zettlemoyer. 2017.  Deep semantic role labeling: What works and what’s next.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 473–483, Vancouver, Canada. Association for Computational Linguistics.
  * He et al. (2018b) Shexia He, Zuchao Li, Hai Zhao, and Hongxiao Bai. 2018b.  Syntax for semantic role labeling, to be, or not to be.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2061–2071, Melbourne, Australia. Association for Computational Linguistics.
  * Hermann et al. (2014) Karl Moritz Hermann, Dipanjan Das, Jason Weston, and Kuzman Ganchev. 2014.  Semantic frame identification with distributed word representations.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1448–1458, Baltimore, Maryland. Association for Computational Linguistics.
  * Hewitt and Manning (2019) John Hewitt and Christopher D Manning. 2019.  A structural probe for finding syntax in word representations.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4129–4138.
  * Honnibal and Montani (2017) Matthew Honnibal and Ines Montani. 2017.  spaCy 2: Natural language understanding with Bloom embeddings, convolutional neural networks and incremental parsing.  To appear.
  * Htut et al. (2019) Phu Mon Htut, Jason Phang, Shikha Bordia, and Samuel R Bowman. 2019.  Do attention heads in bert track syntactic dependencies?  _arXiv preprint arXiv:1911.12246_.
  * Jawahar et al. (2019) Ganesh Jawahar, Benoît Sagot, and Djamé Seddah. 2019.  What does BERT learn about the structure of language? In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3651–3657, Florence, Italy. Association for Computational Linguistics.
  * Kingma and Ba (2014) Diederik P. Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  Cite arxiv:1412.6980Comment: Published as a conference paper at the 3rd International Conference for Learning Representations, San Diego, 2015.
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-Supervised Classification with Graph Convolutional Networks.  In _Proceedings of the 5th International Conference on Learning Representations_ , ICLR ’17.
  * Kitaev and Klein (2018) Nikita Kitaev and Dan Klein. 2018.  Constituency parsing with a self-attentive encoder.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , Melbourne, Australia. Association for Computational Linguistics.
  * Kshirsagar et al. (2015) Meghana Kshirsagar, Sam Thomson, Nathan Schneider, Jaime Carbonell, Noah A. Smith, and Chris Dyer. 2015.  Frame-semantic role labeling with heterogeneous annotations.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 218–224, Beijing, China. Association for Computational Linguistics.
  * Lafferty et al. (2001) John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001.  Conditional random fields: Probabilistic models for segmenting and labeling sequence data.  In _Proceedings of the Eighteenth International Conference on Machine Learning_ , ICML ’01, pages 282–289, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
  * Li et al. (2018) Yifu Li, Ran Jin, and Yuan Luo. 2018.  Classifying relations in clinical narratives using segment graph convolutional and recurrent neural networks (Seg-GCRNs).  _Journal of the American Medical Informatics Association_ , 26(3):262–268.
  * Li et al. (2016) Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard S. Zemel. 2016.  Gated graph sequence neural networks.  In _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_.
  * Li et al. (2019) Zuchao Li, Shexia He, Hai Zhao, Yiqing Zhang, Zhuosheng Zhang, Xi Zhou, and Xiang Zhou. 2019.  Dependency or span, end-to-end uniform semantic role labeling.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 6730–6737.
  * Liu et al. (2018) Xiao Liu, Zhunchen Luo, and Heyan Huang. 2018.  Jointly multiple events extraction via attention-based graph information aggregation.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 1247–1256, Brussels, Belgium. Association for Computational Linguistics.
  * Maas et al. (2013) Andrew L. Maas, Awni Y. Hannun, and Andrew Y. Ng. 2013.  Rectifier nonlinearities improve neural network acoustic models.  In _in ICML Workshop on Deep Learning for Audio, Speech and Language Processing_.
  * Marcheggiani et al. (2018) Diego Marcheggiani, Joost Bastings, and Ivan Titov. 2018.  Exploiting semantics in neural machine translation with graph convolutional networks.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 486–492, New Orleans, Louisiana. Association for Computational Linguistics.
  * Marcheggiani and Titov (2017) Diego Marcheggiani and Ivan Titov. 2017.  Encoding sentences with graph convolutional networks for semantic role labeling.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 1506–1515, Copenhagen, Denmark. Association for Computational Linguistics.
  * Marcheggiani and Titov (2019) Diego Marcheggiani and Ivan Titov. 2019.  Graph convolutions over constituent trees for syntax-aware semantic role labeling.  _CoRR_ , abs/1909.09814.
  * Nguyen and Grishman (2018) Thien Huu Nguyen and Ralph Grishman. 2018.  Graph convolutional networks with argument-aware pooling for event detection.  In _32nd AAAI Conference on Artificial Intelligence, AAAI 2018_ , 32nd AAAI Conference on Artificial Intelligence, AAAI 2018, pages 5900–5907. AAAI press.  32nd AAAI Conference on Artificial Intelligence, AAAI 2018 ; Conference date: 02-02-2018 Through 07-02-2018.
  * Ouchi et al. (2018) Hiroki Ouchi, Hiroyuki Shindo, and Yuji Matsumoto. 2018.  A span selection model for semantic role labeling.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 1630–1642, Brussels, Belgium. Association for Computational Linguistics.
  * Paszke et al. (2017) Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017.  Automatic differentiation in PyTorch.  In _NeurIPS Autodiff Workshop_.
  * Peng et al. (2018) Hao Peng, Sam Thomson, Swabha Swayamdipta, and Noah A. Smith. 2018.  Learning joint semantic parsers from disjoint data.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1492–1502, New Orleans, Louisiana. Association for Computational Linguistics.
  * Peters et al. (2018) Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018.  Deep Contextualized Word Representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 2227–2237. Association for Computational Linguistics.
  * Punyakanok et al. (2008) Vasin Punyakanok, Dan Roth, and Wen-tau Yih. 2008.  The importance of syntactic parsing and inference in semantic role labeling.  _Computational Linguistics_ , 34(2):257–287.
  * Roth and Lapata (2016) Michael Roth and Mirella Lapata. 2016.  Neural semantic role labeling with dependency path embeddings.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1192–1202, Berlin, Germany. Association for Computational Linguistics.
  * Scarselli et al. (2009) Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. 2009.  The graph neural network model.  _Trans. Neur. Netw._ , 20(1):61–80.
  * Schuster and Paliwal (1997) M. Schuster and K.K. Paliwal. 1997.  Bidirectional recurrent neural networks.  _Trans. Sig. Proc._ , 45(11):2673–2681.
  * Strubell et al. (2018) Emma Strubell, Patrick Verga, Daniel Andor, David Weiss, and Andrew McCallum. 2018\.  Linguistically-informed self-attention for semantic role labeling.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 5027–5038, Brussels, Belgium. Association for Computational Linguistics.
  * Swayamdipta et al. (2017) Swabha Swayamdipta, Sam Thomson, Chris Dyer, and Noah A. Smith. 2017.  Frame-semantic parsing with softmax-margin segmental rnns and a syntactic scaffold.  _CoRR_ , abs/1706.09528.
  * Swayamdipta et al. (2018) Swabha Swayamdipta, Sam Thomson, Kenton Lee, Luke Zettlemoyer, Chris Dyer, and Noah A. Smith. 2018.  Syntactic scaffolds for semantic structures.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3772–3782, Brussels, Belgium. Association for Computational Linguistics.
  * Tan et al. (2018) Zhixing Tan, Mingxuan Wang, Jun Xie, Yidong Chen, and Xiaodong Shi. 2018.  Deep semantic role labeling with self-attention.  In _Thirty-Second AAAI Conference on Artificial Intelligence_.
  * Vashishth et al. (2019) Shikhar Vashishth, Manik Bhandari, Prateek Yadav, Piyush Rai, Chiranjib Bhattacharyya, and Partha Talukdar. 2019.  Incorporating syntactic and semantic information in word embeddings using graph convolutional networks.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3308–3318, Florence, Italy. Association for Computational Linguistics.
  * Wang et al. (2019) Yufei Wang, Mark Johnson, Stephen Wan, Yifang Sun, and Wei Wang. 2019.  How to best use syntax in semantic role labelling.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 5338–5343, Florence, Italy. Association for Computational Linguistics.
  * Xue and Palmer (2004) Nianwen Xue and Martha Palmer. 2004.  Calibrating features for semantic role labeling.  In _Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing_ , pages 88–94, Barcelona, Spain. Association for Computational Linguistics.
  * Yang and Mitchell (2017) Bishan Yang and Tom Mitchell. 2017.  A joint sequential and relational model for frame-semantic parsing.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 1247–1256, Copenhagen, Denmark. Association for Computational Linguistics.


# Approximation Algorithms for Smallest Intersecting Balls

Jiaqi Zheng Department of Computer Science, National University of Singapore.
Tiow-Seng Tan11footnotemark: 1

###### Abstract

We study a general smallest intersecting ball problem and its soft-margin
variant in high-dimensional Euclidean spaces, which only require the input
objects to be compact and convex. These two problems link and unify a series
of fundamental problems in computational geometry and machine learning,
including smallest enclosing ball, polytope distance, intersection radius,
$\ell_{1}$-loss support vector machine, $\ell_{1}$-loss support vector data
description, and so on. Two general approximation algorithms are presented
respectively, and implementation details are given for specific inputs of
convex polytopes, reduced polytopes, axis-aligned bounding boxes, balls, and
ellipsoids. For most of these inputs, our algorithms are the first results in
high-dimensional spaces, and also the first approximation methods. To achieve
this, we develop a novel framework for approximating zero-sum games in
Euclidean Jordan algebra systems, which may be useful in its own right.

##  1 Introduction

##  2 Preliminaries

##  3 Approximate a zero-sum game

##  4 Smallest intersecting balls

##  5 A soft-margin variant

##  6 Discussion

## References

  * Allen-Zhu et al. [2016] Zeyuan Allen-Zhu, Zhenyu Liao, and Yang Yuan.  Optimization Algorithms for Faster Computational Geometry.  In _43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)_ , volume 55, pages 53:1–53:6, 2016.
  * Arashloo [2022] Shervin Rahimzadeh Arashloo.  $\ell_{p}$-norm support vector data description.  _Pattern Recognition_ , 132:108930, 2022.
  * Arora et al. [2012] Sanjeev Arora, Elad Hazan, and Satyen Kale.  The multiplicative weights update method: a meta-algorithm and applications.  _Theory of computing_ , 8(1):121–164, 2012.
  * Beck [2014] Amir Beck.  _Introduction to Nonlinear Optimization_.  Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014.
  * Bennett and Bredensteiner [2000] Kristin P. Bennett and Erin J. Bredensteiner.  Duality and geometry in SVM classifiers.  In _Proceedings of the Seventeenth International Conference on Machine Learning_ , pages 57–64, 2000.
  * Bhattacharya et al. [1991] Binay K. Bhattacharya, Sreesh Jadhav, Asish Mukhopadhayay, and Jean-Marc Robert.  Optimal algorithms for some smallest intersection radius problems.  In _Proceedings of the Seventh Annual Symposium on Computational Geometry_ , SCG ’91, pages 81–88, New York, NY, USA, 1991.
  * Bădoiu and Clarkson [2003] Mihai Bădoiu and Kenneth L. Clarkson.  Smaller core-sets for balls.  In _SODA_ , volume 3, pages 801–802, 2003.
  * Bădoiu and Clarkson [2008] Mihai Bădoiu and Kenneth L. Clarkson.  Optimal core-sets for balls.  _Computational Geometry_ , 40(1):14–22, 2008.
  * Canyakmaz et al. [2023] Ilayda Canyakmaz, Wayne Lin, Georgios Piliouras, and Antonios Varvitsiotis.  Multiplicative updates for online convex optimization over symmetric cones.  _arXiv preprint arXiv:2307.03136_ , 2023.
  * Chang et al. [2013] Wei-Cheng Chang, Ching-Pei Lee, and Chih-Jen Lin.  A revisit to support vector data description.  _Dept. Comput. Sci., Nat. Taiwan Univ., Taipei, Taiwan, Tech. Rep_ , 2013.
  * Clarkson [2010] Kenneth L. Clarkson.  Coresets, sparse greedy approximation, and the frank-wolfe algorithm.  _ACM Transactions on Algorithms (TALG)_ , 6(4):1–30, 2010.
  * Clarkson et al. [2012] Kenneth L. Clarkson, Elad Hazan, and David P. Woodruff.  Sublinear optimization for machine learning.  _J. ACM_ , 59(5), 2012.
  * Cohen et al. [2016] Michael B Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford.  Geometric median in nearly linear time.  In _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ , pages 9–21, 2016.
  * Cormen et al. [2022] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein.  _Introduction to Algorithms, Fourth Edition_.  MIT Press, 2022.
  * Crisp and Burges [1999] David Crisp and Christopher J. C. Burges.  A geometric interpretation of $\nu$-SVM classifiers.  In S. Solla, T. Leen, and K. Müller, editors, _Advances in Neural Information Processing Systems_ , volume 12. MIT Press, 1999.
  * Dax [2006] Achiya Dax.  The distance between two convex sets.  _Linear Algebra and its Applications_ , 416(1):184–213, 2006.
  * Dyer [1984] Martin E. Dyer.  Linear time algorithms for two-and three-variable linear programs.  _SIAM Journal on Computing_ , 13(1):31–45, 1984.
  * Faraut and Korányi [1994] Jacques Faraut and Adam Korányi.  _Analysis on Symmetric Cones_.  Oxford mathematical monographs. Clarendon Press, 1994.
  * Gärtner and Jaggi [2009] Bernd Gärtner and Martin Jaggi.  Coresets for polytope distance.  In _Proceedings of the twenty-fifth annual symposium on Computational geometry_ , pages 33–42, 2009.
  * Gärtner and Schönherr [2000] Bernd Gärtner and Sven Schönherr.  An efficient, exact, and generic quadratic programming solver for geometric optimization.  In _Proceedings of the sixteenth annual symposium on Computational geometry_ , pages 110–118, 2000.
  * Hazan et al. [2011] Elad Hazan, Tomer Koren, and Nati Srebro.  Beating sgd: Learning svms in sublinear time.  _Advances in Neural Information Processing Systems_ , 24, 2011.
  * Jadhav et al. [1996] Shreesh Jadhav, Asish Mukhopadhyay, and Binay Bhattacharya.  An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons.  _Journal of Algorithms_ , 20(2):244–267, 1996.
  * John [1948] Fritz John.  Extremum problems with inequalities as subsidiary conditions.  In _Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948_ , pages 187–204. Interscience Publishers, New York, 1948.
  * Kumar et al. [2003] Piyush Kumar, Joseph SB Mitchell, and E Alper Yildirim.  Approximate minimum enclosing balls in high dimensions using core-sets.  _Journal of Experimental Algorithmics (JEA)_ , 8:1–1, 2003.
  * Lanckriet et al. [2002] Gert RG Lanckriet, Laurent El Ghaoui, Chiranjib Bhattacharyya, and Michael I Jordan.  A robust minimax approach to classification.  _Journal of Machine Learning Research_ , 3(Dec):555–582, 2002.
  * Löffler and van Kreveld [2010] Maarten Löffler and Marc van Kreveld.  Largest bounding box, smallest diameter, and related problems on imprecise points.  _Computational Geometry_ , 43(4):419–433, 2010.
  * Marshall and Olkin [1960] Albert W Marshall and Ingram Olkin.  Multivariate chebyshev inequalities.  _The Annals of Mathematical Statistics_ , pages 1001–1014, 1960.
  * Megiddo [1983] Nimrod Megiddo.  Linear-time algorithms for linear programming in $\mathbb{R}^{3}$ and related problems.  _SIAM journal on computing_ , 12(4):759–776, 1983.
  * Nam et al. [2012] Nguyen Mau Nam, Nguyen Thai An, and Juan Salinas.  Applications of convex analysis to the smallest intersecting ball problem.  _Journal of Convex Analysis_ , 19:497–518, 2012.
  * Orlitzky [2022] Michael Orlitzky.  _Euclidean Jordan algebras_.  2022\.
  * Rudin [1976] W. Rudin.  _Principles of Mathematical Analysis, Third Edition_.  International series in pure and applied mathematics. McGraw-Hill, 1976.
  * Shenmaier [2015] Vladimir Shenmaier.  Complexity and approximation of the smallest k-enclosing ball problem.  _European Journal of Combinatorics_ , 48:81–87, 2015.
  * Shivaswamy et al. [2006] Pannagadatta K Shivaswamy, Chiranjib Bhattacharyya, and Alexander J Smola.  Second order cone programming approaches for handling missing and uncertain data.  _Journal of Machine Learning Research_ , pages 1283–1314, 2006.
  * Sion [1958] Maurice Sion.  On general minimax theorems.  _Pacific J. Math._ , 8:171–176, 1958.
  * Son and Afshani [2015] Wanbin Son and Peyman Afshani.  Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls.  In _Theory and Applications of Models of Computation_ , pages 189–199, 2015.
  * Tao et al. [2022] Jiyuan Tao, GQ Wang, and L Kong.  The Araki-Lieb-Thirring inequality and the Golden-Thompson inequality in Euclidean Jordan algebras.  _Linear and Multilinear Algebra_ , 70(19):4228–4243, 2022.
  * Tapolcai et al. [2020] János Tapolcai, Lajos Rónyai, Balázs Vass, and László Gyimóthi.  Fast Enumeration of Regional Link Failures Caused by Disasters With Limited Size.  _IEEE/ACM Transactions on Networking_ , 28(6):2421–2434, 2020.
  * Trafalis and Alwazzi [2010] Theodore B Trafalis and Samir A Alwazzi.  Support vector machine classification with noisy data: a second order cone programming approach.  _International Journal of General Systems_ , 39(7):757–781, 2010.
  * Vandenberghe [2016] Lieven Vandenberghe.  Symmetric cones.  Lecture notes, Electrical and Computer Engineering Department, UCLA, Spring, 2016.
  * Vandenberghe and Boyd [1996] Lieven Vandenberghe and Stephen Boyd.  Semidefinite programming.  _SIAM review_ , 38(1):49–95, 1996.
  * Yildirim [2008] E Alper Yildirim.  Two algorithms for the minimum enclosing ball problem.  _SIAM Journal on Optimization_ , 19(3):1368–1391, 2008.
  * Zhou et al. [2005] Guanglu Zhou, Kim-Chuan Toh, and Jie Sun.  Efficient algorithms for the smallest enclosing ball problem.  _Computational Optimization and Applications_ , 30:147–160, 2005.


# Augmented Memory Computing: Dynamically Augmented SRAM Storage for Data
Intensive Applications

Haripriya Sheshadri*, Shwetha Vijayakumar*, Ajey Jacob, Akhilesh Jaiswal The
authors are with the Information Sciences Institute, University of Southern
California, Los Angeles, CA-90007, USA(* These authors contributed equally)

###### Abstract

The emergence of various data-intensive applications like artificial
intelligence, machine learning etc., has highlighted the energy and throughput
bottlenecks inherent in existing computing systems. Memory storage is a major
component for such data intensive computational platforms. Consequently,
memory-centric research investigations to improve the overall energy-
efficiency and throughput of a given computing chip is being actively pursued.
Exploration of novel memory technologies for high-density on-chip memories and
in-memory computing are the key examples of such memory-centric approaches. In
this paper, we propose a novel memory-centric scheme based on CMOS SRAM. Our
proposal aims at dynamically increasing the on-chip memory storage capacity of
SRAM arrays on-demand. The proposed scheme called - Augmented Memory Computing
allows an SRAM cell to operate in two different modes 1) the Normal mode and
2) the Augmented mode. In the Normal mode of operation, the SRAM cell
functions like a standard 6 transistor (6T) SRAM cell, storing one bit of data
in static format. While in the Augmented mode, each SRAM cell can store $>$1
bit of data (in a dynamic fashion). Specifically, we propose two novel SRAM
cells - an 8 transistor (8T) dual bit storage augmented cell and a 7
transistor (7T) ternary bit storage augmented cell. The proposed 8T dual bit
SRAM cell when operated in the Augmented mode, can store a static bit of data
while also, simultaneously, storing another bit in a dynamic form. Thus, when
operated in Augmented mode, the 8T SRAM cell can store two bits of data - one
SRAM-like data and one DRAM-like data, thereby increasing or augmenting the
memory storage capacity. On the other hand, the proposed 7T ternary bit
storage augmented cell can either store a single SRAM data in Normal mode or
can be configured to operate in Augmented mode, wherein it can store ternary
data (3 levels (0,0), (0,1), (1,0)) in a dynamic manner. Thus, based on the
mode of operation, the proposed augmented memory bit-cells can either store
one static bit of data or $>$1 bit of data in a dynamic format. We show the
feasibility of our proposed bit-cells through extensive simulations at
Globalfoundries 22nm FDX node. It is worth mentioning, the novel scheme of
augmented memory bit-cells can be seamlessly combined with existing in-memory
computing approaches for added energy and throughput benefits.

###### Index Terms:

Memory-centric approaches, Augmented Memory Computing, Augmented bit-cells,
In-memory computing, SRAM, dual bit storage, ternary bit-storage, data
intensive applications.

##  I Introduction

Over decades the advances in hardware computing platforms have been driven by
the remarkable scalability of the Metal-Oxide-Semiconductor Field Effect
Transistors (MOSFETs) in accordance with Moore’s Law [1]. Despite consistent
improvement in power-performance-area (PPA) metrics, recent trends in data-
intensive applications have pushed the state-of-the-art in hardware computing
platforms to its limits [2]. Existing hardware solutions suffer from energy
and throughput bottlenecks due to frequent data movement between multiple
levels of the memory hierarchy and between memory-units and processing-cores
[3]. To mitigate such bottlenecks various memory-centric approaches are being
extensively explored by the research community. These include exploration of
novel high-density emerging memory technologies [4, 5] and use of emerging
computing approaches like in-memory and near-memory computing [6, 7]. In this
paper, we propose a novel memory-centric paradigm - Augmented Memory Computing
(AMC) for the acceleration of data-intensive applications like artificial
intelligence and machine learning.

It is well-known that the 6 transistor SRAM cell is the most widely used on-
chip memory system due to its high robustness and fast read-write speed [8,
9]. However, a major drawback of SRAM is the associated high area overhead,
limiting the amount of on-chip memory storage. Consequently, off-chip memory
systems are used as high-density storage at the expense of speed and energy
consumption. In fact, the data communication overhead associated with the
movement of data from off-chip to on-chip memory forms a major source of
energy consumption and compute latency [10]. Toward that end, AMC aims at
increasing the on-chip storage on demand, thereby dynamically augmenting
storage capacity for SRAM arrays that can cater to data intensive
applications.

We present a family of novel SRAM bit-cells using two different bit-cell
topology - 1) The proposed 8 transistor (8T) augmented SRAM cell includes two
additional transistors as compared to a 6T cell, wherein the 8T augmented bit-
cell can simultaneously store an SRAM-like and a DRAM-like data based on the
applied voltages 2) Similarly, the proposed 7T augmented bit-cell can store a
ternary data (-1,0,+1) per bit-cell in a dynamic format as opposed to storing
a binary data (0,1) as in a conventional 6T SRAM cell. Note, both the proposed
augmented bit-cells can function like normal SRAM cells with comparative read-
write margins and speed. As such, our proposed bit-cells can be operated in
two distinct modes. In the Normal mode these bit-cells function like
conventional 6T bit-cell storing a binary data, while in Augmented mode, the
bit-cells can store more data (either two bits for the 8T augmented cell, and
ternary bits for the 7T augmented cell), thereby dynamically increasing the
memory storage capacity.

Figure 1: 8T dual bit storage augmented bit-cell. The cell can store a SRAM-
like and a DRAM-like date, simultaneously, in the augmented mode.

It is worth mentioning, in comparison to in-memory computing, AMC does not
rely on complicated approximate analog computing and hence is more robust.
This does not imply that AMC cannot be used in conjunction with in-memory
computing. As discussed in section IV, AMC can be combined with existing in-
memory computing approaches for improved energy-efficiency and throughput [6,
11, 12]. In summary, although AMC is conceptually independent of in-memory
computing paradigms, yet it can be easily combined with existing in-memory
processing schemes. Thus, AMC presents a novel approach for memory-centric
computing, along with other existing memory-centric approaches (like in-
memory/near-memory computing). The key contributions of the paper are
mentioned below:

Figure 2: (Left) 6 transistor SRAM cell read SNM using SRAM bit-cell from
Globalfoundries 22nm library. (Right) The read SNM for the proposed 8
transistor augmented bit-cell. As seen the read SNM for the proposed bit-cells
is similar to the library SRAM bit-cell, thereby demonstrating the asymmetry
in the SRAM circuit does not drastically alter the cell stability.

  1. 1.

We propose a novel memory-centric compute paradigm called Augmented Memory
Computing, wherein the storage capacity of on-chip SRAM based memory can be
increased dynamically for data intensive computations.

  2. 2.

We specifically propose two distinct bit-cells. The proposed 8T augmented bit-
cell can store two bits of data, simultaneously, (an SRAM-like and a DRAM-like
data), while the proposed 7T augmented bit-cell can store ternary data
(+1,0.-1) in a dynamic fashion.

  3. 3.

The proposed augmented bit-cells can be used either in Normal mode or
Augmented mode. Furthermore, our proposed 8T augmented bit-cell shows better
voltage scalability as compared to 6T SRAM cell in Normal mode, similarly the
7T augmented bit-cell allows fine-grained power gating compared to 6T bit-cell
in Normal mode.

  4. 4.

We present detailed circuit simulations reporting energy, speed metrics along
with variation analysis at Globalfoundries 22FDX (22nm FD-SOI). [13] node

The rest of the paper is organized as follows. In section II, we present the 8
transistor augmented bit-cell. We first discuss the Normal mode of operation
followed by the dual bit storage Augmented mode of operation. Section III
presents a 7 transistor augmented bit-cell, that can store a ternary bit
within each bit-cell in the Augmented mode of operation. Section IV presents
simulation results and discussions regarding the use of augmented bit-cells in
conjunction with in-memory computing. Finally, section V concludes the paper.

##  II 8T Dual Storage Augmented Bit-Cell

As mentioned earlier, augmented bit-cells can increase their storage capacity
dynamically while also functioning like conventional SRAM bit-cells in the
Normal mode. For a dual bit augmented storage, we add two additional
transistors to the 6T SRAM cell, as shown in Fig. 1. This bit-cell can operate
in two distinct modes - the Normal mode and the Augmented mode. The SRAM cell
can be configured in the Normal or Augmented mode at a sub-array level
granularity.

###  II-A Normal Mode

For the Normal mode of operation, both the wordlines WL1 and WL2 are
activated, simultaneously, during the read and write operations. The resulting
SRAM read and write operations are similar to the 6T cell, except that the
SRAM is asymmetric due to the presence of an additional access transistor (M3)
on the BLB side of the 8T SRAM cell. As shown in Fig. 2, using 1000 Monte-
Carlo simulations at GF 22FDX node, we observe almost no change in static
noise margins, compared to the 6T bit-cell. Thus, the asymmetric nature of the
8T bit-cell leads to minimal alteration of static noise margins and hence the
cell stability. Additionally, the SL line and the BLR line are kept at 0V
during the Normal mode of operation. This ensures no current flows through
transistor M4, irrespective of the voltage at its gate at the node Vz. In
summary, the 8T bit-cell shown in Fig. 1 can be operated similar in
functionality to the conventional 6T SRAM cell when both WL1 and WL2 are
simultaneously activated. This also implies that a conventional differential
sense-amplifier can be used to sense the data stored in the SRAM cell.

Advantageously, the presented 8T bit-cell can be used to improve cell-
stability and achieve lower operating voltages compared to the 6T bit-cell
using the well-known pulsed wordline activation scheme [14]. This can be
achieved by using transistor M4 as a de-coupled read port. For improved
stability, WL1 is activated first using a short duration pulse, keeping WL2
OFF. This would ensure node Vz is charged or discharged based on the data
stored at node Vy. Essentially, by pulsed activation of the wordline WL1, we
are copying the SRAM data into the node Vz. Since the pulse duration of the
signal on WL1 would be much smaller than conventional 6T SRAM the possibility
of read disturb is minimal [14]. After the pulsed activation of WL1, the SL is
pulled to $V_{DD}$. Subsequently, a large signal inverter-based sensing can
detect the voltage change on BLB. Thus, the proposed 8T bit-cell can be used
in conjunction with a pulsed WL scheme to improve cell-stability.

Figure 3: Figure showing the sensing scheme for the SRAM and DRAM data in the
augmented 8T bit-cell. The SRAM data can be sensed through the differential
bit-lines BL and BLB, while the DRAM data can be sensed using single ended
large signal inverter based sensing. Note, a FILO scheme ensures the DRAM data
is not disturbed inadvertently.

###  II-B Augmented Mode

In the augmented mode, the 8T bit-cell stores two bits of data,
simultaneously. The SRAM-like static data is stored in the cross-coupled
inverter pair as complementary voltages on nodes Vx and Vy, similar to the
conventional 6T SRAM storage; while the two transistors M3 and M4 store a
DRAM-like data on the dynamic node Vz. In fact, transistors M3 and M4 form a 2
transistor embedded DRAM cell, which can be written by activating WL2, and can
be read through transistor M4 using lines SL and BLR. For the DRAM write
operation, line WL2 is pulled high and data is written into the DRAM node Vz
through the line BLB. Note, due to the presence of an NMOS only access
transistor M3, we use voltage boosting on WL2 for writing a high value at the
dynamic node Vz. During the write operation, the SL lines are all kept at 0V
and the BLR lines are also discharged to 0V. For the DRAM read operation, the
corresponding SL line is pulled high and a voltage accumulation on the
initially discharged line BLR is sensed to read the DRAM data. Note, all
unselected SL lines are kept at 0V. The DRAM data can be read by using a large
signal inverter based sensing as shown in Fig. 3. The compact inverter based
sensing ensures minimal sensing circuit overhead. In summary, the transistors
M3, M4 along with lines SL and BLR constitute an embedded DRAM cell within the
8T SRAM cell, such that it can store an independent data in a dynamic fashion,
while simultaneously a static data is stored in the SRAM cell.

Interestingly, while transistors M3, M4 and node Vz store a DRAM-like data,
the SRAM data is stored on nodes Vx and Vy which can be read and written by
simultaneously activating worldines WL1 and WL2. The SRAM data can be read
using a latch based differential current or voltage sense amplifier, as shown
in Fig. 3. It is important to note that the DRAM data stored on node Vz will
be destroyed during the read or write operation of the SRAM data since the
DRAM node Vz is in the SRAM read/write path. However, this issue can be
circumvented by relying on the data access pattern for specific end
applications. For example, in a deep learning network nodes Vx and Vy can
store weights while the corresponding node Vz streams input activations. In
other words, by ensuring a first-in last-out (FILO) scheme for the combined
SRAM-like and DRAM-like bit we can store two bits simultaneously in the 8T
bit-cell without inadvertently destroying the DRAM data. Given the regular
memory access pattern for data intensive applications like artificial
intelligence and machine learning, it is easy to enforce such a FILO scheme.

Thanks to the excellent leakage control of the 22nm GF FD-SOI technology, we
have achieved 25$\mu$s retention time at 85C with a small (-100mV negative
voltage) on wordlines WL2 during hold mode of the memory array. Timing
waveforms with Monte-Carlo simulations are shown in Fig. 4, exhibiting the
retention waveform at a temperature of 85 degrees Celsius. The retention time
is defined here as the time until the peripheral circuit can reliably sense
the data stored on the dynamic node Vz.

Figure 4: Figure depicting leakage of data stored on the dynamic node as a
function of time for the DRAM-like bit storage in the 8T augmented cell at
85C.

##  III 7T Ternary Storage Augmented Bit-Cell

It is well-known that a 6 transistor SRAM cell can store one digital bit in a
static format. SRAM being a differential memory, both the bit and the
complement of the bit are stored in the same cell. Our proposed 7T augmented
SRAM cell can either be configured to store one static SRAM bit (Two Levels:
Normal mode of operation) or one dynamic ternary bit (Three Levels: Augmented
mode of operation). Note, ternary bits have three levels usually represented
as (-1, 0, +1).

Ternary memory storage is becoming increasingly popular due to the recent
algorithmic advances in Ternary Neural Networks (TNNs). TNNs are being
extensively explored [15, 16], since they provide both lower memory
requirement as well as improved accuracy for deep learning networks.
Traditionally, since 6T SRAM cell can only store a binary data, two 6T cells
are required to store one ternary data [17]. As such, our proposed 7T Ternary
augmented cell can be configured to increase the on-chip SRAM storage density
for ternary weights for TNN accelerators. Note, the proposed 7T Ternary
augmented cell stores ternary data in a dynamic format as opposed to the
conventional 6T SRAM, which stores static binary data.

###  III-A Normal Mode

The 7T Ternary augmented cell is shown in Fig. 5. It consists of 6T SRAM cell
with one additional PMOS transistor per bit-cell connecting the cross-coupled
inverters to VDD. For the Normal mode of operation, the PMOS M6 is kept ON,
and the augmented cell functions similar to a normal SRAM cell. It is worth
mentioning, that similar 7T cells with a header PMOS have been used in
previous literature to enable fine-grained power gating [18]. In the
traditional use-case, when the PMOS transistor M6 is switched OFF, the cross-
coupled inverters are disconnected from the power supply and the SRAM cell
enters power-gated mode, thereby drastically reducing the cell leakage. In
summary, the normal mode of operation of the 7T augmented cell is similar to a
gated VDD SRAM cell [18]. When PMOS M6 is ON, the cell stores one static data,
when PMOS M6 is OFF, the cell is disconnected from VDD and is in power gated
mode.

Figure 5: 7T augmented ternary bit-cell in Normal mode. During the normal mode
of operation M6 is ON, thereby the 7T cell acts like a conventional 6T SRAM
cell.

###  III-B Augmented Mode

During the Augmented mode, transistor M6 is switched OFF. As seen in Fig. 6,
the cross-coupled inverters are disconnected from VDD, and the SRAM can no
longer store data and its complement in static format. With PMOS M6 OFF, since
the cross-coupled inverters are no longer connected to VDD, the positive
feedback behavior of the cross-coupled inverters are weakened. We exploit this
weakened feedback between the nodes Q and QB to store three different data
patterns on nodes (Q,QB) in a dynamic fashion. Specifically, with the PMOS M6
OFF, (Q,QB) can dynamically store one among three different data patterns $-$
(1,0), (0,1) and (0,0). This three level storage allows us to store a ternary
bit in the 7T SRAM cell, wherein (1,0), (0,1) and (0,0) can be conceptually
mapped to ternary levels of (-1,+1, 0), respectively.

Figure 6: 7T augmented cell showing parasitic capacitances at nodes Q and QB
that act like dynamic nodes to store the ternary data (0,1), (1,0) or (0,0) in
a DRAM-like fashion during augmented mode of operation.

The storage of different voltage levels on nodes Q and QB can be understood as
follows. Let us consider the case of storing the data (0,1) in the SRAM cell
during the Augmented mode (i.e. when PMOS M6 is OFF). Keeping PMOS M6 OFF, the
WL is activated, BL and BLB are pulled high or low based on the data to be
stored in the SRAM cell. Note, since the SRAM cell is not connected to VDD,
the cross-coupled inverter does not have a positive feedback mechanism to
write a robust ‘1’ into the cell. This is because the access transistors
consisting of NMOS devices suffer a threshold voltage (VT) drop when passing a
high value. Consequently, we use voltage boosting, wherein the WL is pulled to
1.25V to ensure a strong ‘1’ is written into the SRAM cell. The write
waveforms for storing data (0,1) is shown in Fig. 7. Note, with PMOS M6 OFF,
when Q and QB stores (0,1), the DRAM-like capacitors $C_{A}$ and $C_{B}$
(formed due to parasitic gate and diffusion capacitances) are charged and
discharged, respectively (see Fig. 6). As a result, transistors M1 and M2 are
ON and M0 and M3 are OFF. By symmetry, the waveforms of Fig. 7 also represent
write operation for data (1,0) with appropriate voltages being applied on BL
and BLB.

As expected, due to absence of a VDD connection, over a certain duration of
time, the dynamic nodes Q and QB leak, destroying the data stored in the
augmented cell. Thereby, with respect to (0,1) data, the retention time can be
defined as the time up to which the data Q and QB can be robustly sensed by
the peripheral sensing circuit. A similar argument for retention time can also
be made for data (1,0). Figure showing the leakage of voltages on nodes Q and
QB that dictates the retention time for data (0,1)/(1,0) is depicted in Fig.
8.

Now let us consider storing data (0,0) in the augmented 7T cell. For writing
the data (0,0), both Q and QB are discharged by activating the WL and pulling
BL and BLB to 0V. This in turn switches OFF NMOS transistors M2 and M3.
Although the PMOSes M0 and M1 are ON, nodes Q and QB are disconnected from VDD
due to the OFF transistor M6. As a result, nodes Q and QB are not connected to
VDD. The capacitors $C_{A}$ and $C_{B}$ act as dynamic floating nodes that are
neither connected to GND nor to VDD. Thus, the dynamic nodes Q and QB store
the data (0,0) when BL and BLB are pulled low and WL is high. The write
waveforms for data (0,0) is shown in Fig. 9. Note, in a conventional 6T SRAM
cell, storage of (0,0) is not possible due to the existence of strong positive
feedback between the two cross-coupled inverters. The strong positive feedback
forces Q and QB to always be the complement of each other. By disconnecting
the VDD using PMOS M6, we significantly weaken the feedback connection and
store (0,0) on nodes (Q,QB) on the dynamic capacitors $C_{A}$ and $C_{B}$. In
summary, when PMOS M6 is switched OFF, the 7T cell can either store (1,0),
(0,1), or (0,0) in a dynamic manner. Note, as expected the data (0,0) stored
on dynamic nodes Q and QB leak with time. However, the resulting retention
time is higher than the case of (0,1) and (1,0). Consequently, the (0,0) data
storage does not decide the overall retention of the 7T augmented cell, it is
rather limited by the retention time of data (0,1)/(1,0) as shown in Fig. 8.

Figure 7: Waveforms showing the writing of data (0,1) / data (1,0) into the
augmented 7T SRAM cell when PMOS M6 is OFF. Figure 8: Data retention time for
data (0,1) / data (1,0) at 85C. The retention time improves with decreasing
temperature. Figure 9: The writing of data (0,0) in the 7T augmented cell. In
absence of positive feedback, WL can be activated and BL and BLB can be pulled
low to write data (0,0). Figure 10: (a) For Normal mode of operation a
differential sense amplifier can be used for sensing (b) For the case of
Augmented mode two inverters along with a digital logic circuit is employed to
sense ternary data (0,1), (1,0) and (0,0). Figure 11: Read waveform for data
(0,1) at the end of retention time at 85C.

Let us now consider the readout of data (0,1), (1,0) and (0,0). For a (0,1) or
(1,0) readout, one of the NMOS transistors M2 or M3 is ON depending on the
data stored in the bit-cell. When WL is made ON by pulling it to VDD, the pre-
charged BL or BLB discharges depending on which among NMOS transistors M2 or
M3 is ON. Thus, by sensing the discharge on BL and BLB, the peripheral circuit
can conclude if the data stored in the augmented 7T cell is (0,1) and (1,0),
respectively. In its simplest form, the readout circuit consists of large-
signal inverter-based sensing, as shown in Fig. 10 (b). On the other hand, for
the data (0,0), both the NMOS transistors are OFF and both BL and BLB do not
see a significant discharge except for leakage currents. As such, no
significant voltage discharge either on BL or BLB indicates storage of data
(0,0). In summary, a discharging BL indicates data (0,1), a discharging BLB
indicates storage of data (1,0), and no significant discharge either on BL or
BLB indicates data (0,0). The logic circuit shown in Fig 10(b) takes the
voltage output from the sensing inverters as input digital signal and converts
it into (0,1), (1,0), or (0,0) representing the data stored in the 7T SRAM
cell. Read waveforms for reading the data (0,1) is shown in Fig. 11. By
symmetry, the waveforms also represent the readout of data (1,0). Note, in the
case of (0, 0), both BL and BLB would not show any significant discharge
during the read operation, as such, the waveforms for (0, 0) read are not
shown explicitly in the figure. It is worth mentioning, during Normal SRAM
operation i.e. when PMOS transistor M6 is ON the 7T SRAM cell functions like a
standard 6T cell that can be sensed using standard differential sensing
amplifier. In addition, one could also use two differential sense amplifiers,
one on each BL and BLB for small signal single ended sensing instead of large
signal sensing that uses inverters. Although, such differential sensing during
augmented mode has speed benefits, it suffers from area overhead drawback.

##  IV Results and Discussions

As discussed earlier, the proposed augmented bit-cells can be operated in two
modes - the Normal mode and the Augmented mode. In essence, augmented cells
rely on dynamic storage within the SRAM cells to increase the memory storage
capacity. Due to such dynamic nature of storage, retention time is the key
metric for augmented bit-cells. Furthermore, the retention time shows a strong
dependence on temperature and makes our proposed cells interesting for cryo-
computing applications [19]. Table I-II mentions the retention time for
various temperatures. The retention time is a strong function of temperature
and are in similar range as reported in previous works on embedded-DRAM cells
[20]. The retention time can be improved using circuit based design knobs like
body biasing [21] etc. In addition, based on the end application requirement,
a hardware-algorithm co-design approach can be used to allow relaxed retention
times by leveraging the resiliency of the end application, for example, the
resilient nature of a deep learning network can be used to extend the
retention time of the augmented bit-cells using error-aware training of the
neural network.

In Table III-IV we have enumerated read, write energy associated with the
augmented cells in Normal and Augmented modes along with leakage power
consumption. For the sake of comparison, we have also mentioned the energy and
delay numbers for conventional 6T SRAM cell at 22nm Globalfoundries FDX
technology. All the energy and power numbers are reported for operation at a
temperature of 85C. For the 8T augmented cell, the read, write energy and
leakage power increases as compared to a 6T cell. This increase can be
attributed to more number of transistors in the augmented cell, that add both
parasitic capacitance and leakage energy consumption. Also, it was observed
due to the use of single ended sensing for the DRAM part of the 8T augmented
cell the read energy increases by 2.7x compared to the 6T cell. For the 7T
augmented cell, the energy metrics are comparable to the 6T SRAM cell for
Normal mode of operation. The reduced write energy can be attributed to the
OFF PMOS header transistor in the augmented mode making write operation easier
and reducing cell leakage for unselected rows. Table V-VI report the read and
write time for the augmented mode operation. Note, due to the presence of BL
and BLB the read delay for 7T bit-cell is lesser as compared to the 8T bit-
cell. The delay number for 8T bit-cell is for the DRAM-like bit, the SRAM-like
bit storage has similar read, write dealy as a normal 6T SRAM cell.

Let us now highlight some key discussions with respect to the augmented memory
bit-cells. As detailed in the manuscript, augmented memory bit-cells bring in
a novel approach to dynamically increase the memory storage capacity. As such,
the augmented bit-cells help to alleviate the issues associated with limited
on-chip storage. On the other hand, in-memory computing is another well-known
approach being extensively investigated by the research community [7, 11, 22].
Below are the key points we would like to highlight about augmented memory
with respect to in-memory computing.

AMC aims at dynamically increasing on-chip storage capacity through modified
SRAM bit-cells. It is important to note that, use of augmented mode does not
incur any approximation in data storage or computed data. The sole difference
between normal SRAM and augmented storage is the dynamic nature of data and
does not effect the accuracy of computations. This is in contrast to in-memory
computing paradigms, wherein multiple rows are activated and computations are
achieved through approximation of the accumulated signal on the bit-lines.
Thus, AMC paradigm is more amenable to traditional memory verification and
design flow than in-memory paradigms.

TABLE I: Summary of Retention time for 8T SRAM augmented bit-cell Temperature | VWL1 | VWL2 | Retention time
---|---|---|---
85°C | -0.1V | 0V |  25 $\mu$s
25°C | 0V | 0V |  250 $\mu$s
25°C | -0.1V | 0V | milli-sec
TABLE II: Summary of Retention Time for 7T SRAM augmented bit-cell Temperature | VWL | Retention time
---|---|---
85°C | 0V |  4 $\mu$s
25°C | 0V | >50 $\mu$s
TABLE III: Power/Energy consumption of 8T SRAM augmented cell Temperature | Region | 6T SRAM | 8T SRAM
---|---|---|---
85°C | Hold | 0.448 uW | 0.603 uW
85°C | Read | 1.83 fJ | 3.37 fJ
85°C | Write | 2.07 fJ | 8.32 fJ
TABLE IV: Power/Energy consumption of 7T SRAM augmented cell Temperature | Operation | 6T SRAM | 7T-Normal | 7T-AMC
---|---|---|---|---
85°C | Hold | 0.448 uW | 0.430 uW | 0.59 uW
85°C | Read | 1.83 fJ | 3.53 fJ | 3.12 fJ
85°C | Write | 2.07 fJ | 2.02 fJ | 0.99 fJ

Interestingly, augmented memory computing can be combined with in-memory
computing techniques for additional benefits. Both analog and digital in-
memory computing techniques have been presented in various previous works for
static (SRAM) [22] and dynamic (DRAM) bit-cells [23]. These in-memory
techniques can be easily applied to the AMC bit-cells (specifically the 8T
dual bit AMC cell) while operating in augmented computing mode. For example,
the 8T dual bit-cell can be configured to store one SRAM-like and one DRAM-
like data. During read operation multiple wordlines can be activated and
digital or analog in-memory computing can be achieved while the 8T cell is
operating in augmented memory mode. The FILO readout for 8T augmented bit-cell
could still be enforced while performing in-memory computing operations to
ensure the DRAM data is not inadvertently destroyed while accessing the SRAM
data. Further, algorithm hardware co-design can be invoked to leverage trade-
off between retention time, power consumption and end application accuracy
[24, 25]. Augmented bit-cells thus provide multiple operational mode - 1) the
Normal mode, 2) only Augmented computing mode, 3) only in-memory computing
mode, and 4) Augmented + in-memory/near-memory computing mode.

TABLE V: Summary of Read and Write Delay for 8T SRAM augmented cell Write Delay | Read Delay
---|---
1 ns |  15 ns
TABLE VI: Summary of Read and Write Delay for 7T SRAM augmented cell | Write Delay | Read Delay
---|---|---
Data (0,0) |  0.4 ns |  0.4 ns
Data (0,1)/(1,0) |  0.5 ns |  1.5 ns

##  V Conclusion

On-chip memory capacity is a key factor for many data intensive applications.
In this paper, for the first time, we propose novel augmented memory bit-cells
that can operate like conventional SRAM cells during normal mode of operation
and can dynamically increase their storage capacity in the augmented mode of
operations. We specifically present a 8 transistor SRAM cell that can store
one SRAM-like and one DRAM-like bit, simultaneously, within the memory bit-
cell. Similarly, our proposed 7 transistor SRAM bit-cell can store a ternary
bit (three levels) in a dynamic fashion during the augmented mode of
operation. Advantageously, the presented augmented bit-cells are amenable to
in-memory compute paradigm that can provide added energy and throughput
benefits. The functionality of the presented bit-cells has been confirmed by
extensive simulations at Globalfoundries 22nm FD-SOI technology node. In
summary, the concept of augmented memory bit-cells brings in a new dimension
to accelerate data intensive application by dynamically augmenting the on-chip
memory storage capacity.

## Acknowledgement

We thank Globalfoundries for providing the PDK and support for 22nm FDX
technology.

## References

  * [1] J. Shalf, “The future of computing beyond moore’s law,” _Philosophical Transactions of the Royal Society A_ , vol. 378, no. 2166, p. 20190061, 2020.
  * [2] D. Gil and W. M. Green, “1.4 the future of computing: Bits+ neurons+ qubits,” in _2020 IEEE International Solid-State Circuits Conference-(ISSCC)_. IEEE, 2020, pp. 30–39.
  * [3] N. R. Mahapatra and B. Venkatrao, “The processor-memory bottleneck: problems and solutions,” _Crossroads_ , vol. 5, no. 3es, p. 2, 1999.
  * [4] Y.-D. Chih, Y.-C. Shih, C.-F. Lee, Y.-A. Chang, P.-H. Lee, H.-J. Lin, Y.-L. Chen, C.-P. Lo, M.-C. Shih, K.-H. Shen _et al._ , “13.3 a 22nm 32mb embedded stt-mram with 10ns read speed, 1m cycle write endurance, 10 years retention at 150° c and high immunity to magnetic field interference,” in _2020 IEEE International Solid-State Circuits Conference-(ISSCC)_. IEEE, 2020, pp. 222–224.
  * [5] H.-S. P. Wong, S. Raoux, S. Kim, J. Liang, J. P. Reifenberg, B. Rajendran, M. Asheghi, and K. E. Goodson, “Phase change memory,” _Proceedings of the IEEE_ , vol. 98, no. 12, pp. 2201–2227, 2010.
  * [6] A. Agrawal, A. Jaiswal, C. Lee, and K. Roy, “X-sram: Enabling in-memory boolean computations in cmos static random access memories,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 65, no. 12, pp. 4219–4232, 2018.
  * [7] A. Sebastian, M. Le Gallo, R. Khaddam-Aljameh, and E. Eleftheriou, “Memory devices and applications for in-memory computing,” _Nature nanotechnology_ , vol. 15, no. 7, pp. 529–544, 2020.
  * [8] J. P. Kulkarni, A. Malavasi, C. Augustine, C. Tokunaga, J. Tschanz, M. Khellah, and V. De, “Low swing and column multiplexed bitline techniques for low-vmin, noise-tolerant, high-density, 1r1w 8t-bitcell sram in 10nm finfet cmos,” in _2020 IEEE Symposium on VLSI Circuits_. IEEE, 2020, pp. 1–2.
  * [9] T. Song, J. Jung, W. Rim, H. Kim, Y. Kim, C. Park, J. Do, S. Park, S. Cho, H. Jung _et al._ , “A 7nm finfet sram using euv lithography with dual write-driver-assist circuitry for low-voltage applications,” in _2018 IEEE International Solid-State Circuits Conference-(ISSCC)_. IEEE, 2018, pp. 198–200.
  * [10] H. Ahmad, T. Arif, M. A. Hanif, R. Hafiz, and M. Shafique, “Superslash: A unified design space exploration and model compression methodology for design of deep learning accelerators with reduced off-chip memory access volume,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 39, no. 11, pp. 4191–4204, 2020.
  * [11] A. Jaiswal, I. Chakraborty, A. Agrawal, and K. Roy, “8t SRAM cell as a multi-bit dot product engine for beyond von-neumann computing,” _arXiv preprint arXiv:1802.08601_ , 2018.
  * [12] X. Si, W.-S. Khwa, J.-J. Chen, J.-F. Li, X. Sun, R. Liu, S. Yu, H. Yamauchi, Q. Li, and M.-F. Chang, “A dual-split 6t sram-based computing-in-memory unit-macro with fully parallel product-sum operation for binarized dnn edge processors,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 66, no. 11, pp. 4172–4185, 2019.
  * [13] “Globalfoundries 22fdx: 22nm fd-soi technology,” _[Online] http://www.hpl.hp.com/research/cacti/_.
  * [14] M. Khellah, Y. Ye, N. Kim, D. Somasekhar, G. Pandya, A. Farhang, K. Zhang, C. Webb, and V. De, “Wordline & bitline pulsing schemes for improving sram cell stability in low-vcc 65nm cmos designs,” in _2006 Symposium on VLSI Circuits, 2006. Digest of Technical Papers._ IEEE, 2006, pp. 9–10.
  * [15] H. Alemdar, V. Leroy, A. Prost-Boucle, and F. Pétrot, “Ternary neural networks for resource-efficient ai applications,” in _2017 international joint conference on neural networks (IJCNN)_. IEEE, 2017, pp. 2547–2554.
  * [16] N. Mellempudi, A. Kundu, D. Mudigere, D. Das, B. Kaul, and P. Dubey, “Ternary neural networks with fine-grained quantization,” _arXiv preprint arXiv:1705.01462_ , 2017.
  * [17] S. Jain, S. K. Gupta, and A. Raghunathan, “Tim-dnn: Ternary in-memory accelerator for deep neural networks,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 28, no. 7, pp. 1567–1577, 2020.
  * [18] M. Powell, S.-H. Yang, B. Falsafi, K. Roy, and T. Vijaykumar, “Gated-vdd: A circuit technique to reduce leakage in deep-submicron cache memories,” in _Proceedings of the 2000 international symposium on Low power electronics and design_ , 2000, pp. 90–95.
  * [19] H. Chiang, T. Chen, J. Wang, S. Mukhopadhyay, W. Lee, C. Chen, W. Khwa, B. Pulicherla, P. Liao, K. Su _et al._ , “Cold cmos as a power-performance-reliability booster for advanced finfets,” in _2020 IEEE Symposium on VLSI Technology_. IEEE, 2020, pp. 1–2.
  * [20] R. Giterman, A. Fish, A. Burg, and A. Teman, “A 4-transistor nmos-only logic-compatible gain-cell embedded dram with over 1.6-ms retention time at 700 mv in 28-nm fd-soi,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 65, no. 4, pp. 1245–1256, 2017.
  * [21] J. Narinx, R. Giterman, A. Bonetti, N. Frigerio, C. Aprile, A. Burg, and Y. Leblebici, “A 24 kb single-well mixed 3t gain-cell edram with body-bias in 28 nm fd-soi for refresh-free dsp applications,” in _2019 IEEE Asian Solid-State Circuits Conference (A-SSCC)_. IEEE, 2019, pp. 219–222.
  * [22] A. Agrawal, A. Jaiswal, C. Lee, and K. Roy, “X-SRAM: Enabling in-memory boolean computations in CMOS static random access memories,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , pp. 1–14, 2018.
  * [23] M. F. Ali, A. Jaiswal, and K. Roy, “In-memory low-cost bit-serial addition using commodity dram technology,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 67, no. 1, pp. 155–165, 2019.
  * [24] J. Liu, B. Jaiyen, R. Veras, and O. Mutlu, “Raidr: Retention-aware intelligent dram refresh,” _ACM SIGARCH Computer Architecture News_ , vol. 40, no. 3, pp. 1–12, 2012.
  * [25] R. Giterman, A. Bonetti, A. Burg, and A. Teman, “Gc-edram with body-bias compensated readout and error detection in 28-nm fd-soi,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 66, no. 12, pp. 2042–2046, 2019.