# Universal Dependency Parsing with a
General Transition-Based DAG Parser

Daniel Hershcovich1,2

&Omri Abend2
1The Edmond and Lily Safra Center for Brain Sciences
2School of Computer Science and Engineering
Hebrew University of Jerusalem
<EMAIL_ADDRESS>
&Ari Rappoport2

###### Abstract

This paper presents our experiments with applying TUPA to the CoNLL 2018 UD
shared task. TUPA is a general neural transition-based DAG parser, which we
use to present the first experiments on recovering enhanced dependencies as
part of the general parsing task. TUPA was designed for parsing UCCA, a cross-
linguistic semantic annotation scheme, exhibiting reentrancy, discontinuity
and non-terminal nodes. By converting UD trees and graphs to a UCCA-like DAG
format, we train TUPA almost without modification on the UD parsing task. The
generic nature of our approach lends itself naturally to multitask learning.
Our code is available at https://github.com/CoNLL-UD-2018/HUJI.

##  1 Introduction

In this paper, we present the HUJI submission to the CoNLL 2018 shared task on
Universal Dependency parsing Zeman et al. (2018). We focus only on parsing,
using the baseline system, UDPipe 1.2 Straka et al. (2016); Straka and
Straková (2017) for tokenization, sentence splitting, part-of-speech tagging
and morphological tagging.

Our system is based on TUPA (Hershcovich et al., 2017, 2018, see §3), a
transition-based UCCA parser. UCCA (Universal Conceptual Cognitive Annotation;
Abend and Rappoport, 2013) is a cross-linguistic semantic annotation scheme,
representing events, participants, attributes and relations in a directed
acyclic graph (DAG) structure. UCCA allows reentrancy to support argument
sharing, discontinuity (corresponding to non-projectivity in dependency
formalisms) and non-terminal nodes (as opposed to dependencies, which are bi-
lexical). To parse Universal Dependencies Nivre et al. (2016) using TUPA, we
employ a bidirectional conversion protocol to represent UD trees and graphs in
a UCCA-like unified DAG format (§2).

#### Enhanced dependencies.

Our method treats enhanced
dependencies111http://universaldependencies.org/u/overview/enhanced-
syntax.html as part of the dependency graph, providing the first approach, to
our knowledge, for supervised learning of enhanced UD parsing. Due to the
scarcity of enhanced dependencies in UD treebanks, previous approaches
Schuster and Manning (2016); Reddy et al. (2017) have attempted to recover
them using language-specific rules. Our approach attempts to learn them from
data: while only a few UD treebanks contain any enhanced dependencies, similar
structures are an integral part of UCCA and its annotated corpora (realized as
reentrancy by remote edges; see §2), and TUPA supports them as a standard
feature.

As their annotation in UD is not yet widespread and standardized, enhanced
dependencies are not included in the evaluation metrics for UD parsing, and so
TUPA’s ability to parse them is not reflected in the official shared task
scores. However, we believe these enhancements, representing case information,
elided predicates, and shared arguments due to conjunction, control, raising
and relative clauses, provide richer information to downstream semantic
applications, making UD better suited for text understanding. We propose an
evaluation metric specific to enhanced dependencies, enhanced LAS (§5.1), and
use it to evaluate our method.

We$A$were$F$made$D$to$F$feel$P$very$D$welcome$S$.$U$$A$$A$

(a) Example UCCA graph.

We were made to feel very welcome .
nsubj:passnsubj:xsubjnsubj:xsubjaux:passrootmarkxcompadvmodxcomppunct (b)
Example UD graph.

Wensubjwereauxmadeheadtomarkfeelheadveryadvmodwelcomehead.punctxcompxcompheadnsubjnsubj

Figure 1: UD graph after conversion to unified DAG format.

Figure 2: (a) Example UCCA annotation for the sentence “We were made to feel
very welcome.”, containing a control verb, made. The dashed A edge is a remote
edge. (b) Bilexical graph annotating the same sentence in UD
(``reviews-077034-0002| from ``UD_English-EWT|). Enhanced dependencies appear
below the sentence. (c) The same UD graph, after conversion to the unified DAG
format. Intermediate non-terminals and head edges are introduced, to get a
UCCA-like structure.

1 We we PRON PRP Case=Nom|Number=Plur|Person=1|PronType=Prs 3 nsubj:pass
3:nsubj:pass|5:nsubj:xsubj|7:nsubj:xsubj _

Figure 3: Example line from CoNLL-U file with two enhanced dependencies:
``5:nsubj:xsubj| and ``7:nsubj:xsubj|.

he went straight to work and finished the job efficiently and promptly !
nsubjnsubjrootadvmodmarkadvclccconjdetobjadvmodccconjadvmodpunct

Figure 4: UD graph from ``reviews-341397-0003| (``UD_English-EWT|), containing
conjoined predicates and arguments.

I wish all happy holidays , and moreso , E9.1 peace on earth .
nsubjrootiobjamodobjpunctpunctccccorphanadvmodpunctpunctconjobjcasenmodpunct

Figure 5: ``newsgroup-
groups.google.com_GuildWars_086f0f64ab633ab3_ENG_20041111_173500-0051|
(``UD_English-EWT|), containing a null node (E9.1) and case information
(nmod:on).

He had a robe that was made back in the ’60s .
nsubjrootdetobjnsubj:passnsubj:passrefaux:passacl:relcladvmodcasedetoblpunct
(a) UD.

Hehadadetrobeheadobjheadthatwasauxmadeheadheadbackheadincasethedet’60shead.punctobladvmodaclnsubjheadnsubjnsubjref

Figure 6: UD converted to unified DAG format.

Figure 7: (a) ``reviews-255261-0007| (``UD_English-EWT|), containing a
relative clause, and (b) the same graph after conversion to the unified DAG
format. The cycle is removed due to the non-terminal nodes introduced in the
conversion.

##  2 Unified DAG Format

To apply TUPA to UD parsing, we convert UD trees and graphs into a unified DAG
format Hershcovich et al. (2018). The format consists of a rooted DAG, where
the tokens are the terminal nodes.222Our conversion code supports full
conversion between UCCA and UD, among other representation schemes, and is
publicly available at
http://github.com/danielhers/semstr/tree/master/semstr/conversion. Edges are
labeled (but not nodes), and are divided into primary and remote edges, where
the primary edges form a tree (all nodes have at most one primary parent, and
the root has none). Remote edges (denoted as dashed edges in Figure 2) enable
reentrancy, and thus form a DAG together with primary edges. Figure 2 shows an
example UCCA graph, and a UD graph (containing two enhanced dependencies)
before and after conversion. Both annotate the same sentence from the English
Web Treebank Silveira et al.
(2014)333https://catalog.ldc.upenn.edu/LDC2012T13.

#### Conversion protocol.

To convert UD into the unified DAG format, we add a pre-terminal for each
token, and attach the pre-terminals according to the original dependency
edges: traversing the tree from the root down, for each head token we create a
non-terminal parent with the edge label head, and add the node’s dependents as
children of the created non-terminal node (see Figure 1). This creates a
constituency-like structure, which is supported by TUPA’s transition set (see
§3.1).

Although the enhanced dependency graph is not necessarily a supergraph of the
basic dependency tree, the graph we convert to the unified DAG format is their
union: any enhanced dependnecies that are distinct from the basic dependency
of a node (by having a different head or universal dependency relation) are
converted to remote edges in the unified DAG format.

To convert graphs in the unified DAG format back into dependency graphs, we
collapse all head edges, determining for each terminal what is the highest
non-terminal headed by it, and then attaching the terminals to each other
according to the edges among their headed non-terminals.

#### Input format.

Enhanced dependencies are encoded in the 9th column of the CoNLL-U format, by
an additional head index, followed by a colon and dependency relation.
Multiple enhanced dependencies for the same node are separated by pipes.
Figure 3 demonstrates this format. Note that if the basic dependency is
repeated in the enhanced graph (`3:nsubj:pass` in the example), we do not
treat it as an enhanced dependency, so that the converted graph will only
contain each edge once. In addition to the UD relations defined in the basic
representations, enhanced dependencies may contain the relation `ref`, used
for relative clauses. In addition, they may contain more specific relation
subtypes, and optionally also case information.

#### Language-specific extensions and case information.

Dependencies may contain language-specific relation subtypes, encoded as a
suffix separated from the universal relation by a colon. These extensions are
ignored by the parsing evaluation metrics, so for example, the subtyped
relation `nsubj:pass` (Figure 1(b)) is considered the same as the universal
relation `nsubj` for evaluation purposes. In the enhanced dependencies, these
suffixes may also contain case information, which may be represented by the
lemma of an adposition. For example, the “peace” $\to$ “earth” dependency in
Figure 5 is augmented as `nmod:on` in the enhanced graph (not shown in the
figure because it shares the universal relation with the basic dependency).

In the conversion process, we strip any language-specific extensions from both
basic and enhanced dependencies, leaving only the universal relations.
Consequently, case information that might be encoded in the enhanced
dependencies is lost, and we do not handle it in our current system.

#### Ellipsis and null nodes.

In addition to enhanced dependencies, the enhanced UD representation adds null
nodes to represented elided predicates. These, too, are ignored in the
standard evaluation. An example is shown in Figure 5, where an elided “wish”
is represented by the node E9.1. The elided predicate’s dependents are
attached to its argument “peace” in the basic representation, and the argument
itself is attached as an `orphan`. In the enhanced representation, all
arguments are attached to the null node as if the elided predicate was
present.

While UCCA supports empty nodes without surface realization in the form of
implicit units, previous work on UCCA parsing has removed these from the
graphs. We do the same for UD parsing, dropping null nodes and their
associated dependencies upon conversion to the unified DAG format. We leave
parsing elided predicates for future work.

#### Propagation of conjuncts.

Enhanced dependencies contain dependencies between conjoined predicates and
their arguments, and between predicates and their conjoined arguments or
modifiers. While these relations can often be inferred from the basic
dependencies, in many cases they require semantic knowledge to parse
correctly. For example, in Figure 4, the enhanced dependencies represent the
shared subject (“he”) among the conjoined predicates (“went” and “finished”),
and the conjoined modifiers (“efficiently” and “promptly”) for the second
predicate (“finished”). However, there are no enhanced dependencies between
the first predicate and the second predicate’s modifiers (e.g. “went” $\to$
“efficiently”), as semantically only the subject is shared and not the
modifiers.

#### Relative clauses.

Finally, enhanced graphs attach predicates of relative clauses directly to the
antecedent modified by the relative clause, adding a `ref` dependency between
the antecedent and the relative pronoun. An example is shown in Figure 6(a).
While these graphs may contain cycles (“robe” $\leftrightarrow$ “made” in the
example), they are removed upon conversion to the unified DAG format by the
introduction of non-terminal nodes (see Figure 6).

##  3 General Transition-based DAG Parser

We now turn to describing TUPA Hershcovich et al. (2017, 2018), a general
transition-based parser Nivre (2003). TUPA uses an extended set of transitions
and features that supports reentrancies, discontinuities and non-terminal
nodes. The parser state is composed of a buffer $B$ of tokens and nodes to be
processed, a stack $S$ of nodes currently being processed, and a graph
$G=(V,E,\ell)$ of constructed nodes and edges, where $V$ is the set of _nodes_
, $E$ is the set of _edges_ , and $\ell:E\to L$ is the _label_ function, $L$
being the set of possible labels. Some states are marked as terminal, meaning
that $G$ is the final output. A classifier is used at each step to select the
next transition based on features encoding the parser’s current state. During
training, an oracle creates training instances for the classifier, based on
gold-standard annotations.

Before Transition Transition After Transition Condition Stack Buffer Nodes
Edges Stack Buffer Nodes Edges Terminal? $S$ $x\;|\;B$ $V$ $E$ Shift $S\;|\;x$
$B$ $V$ $E$ $-$ $S\;|\;x$ $B$ $V$ $E$ Reduce $S$ $B$ $V$ $E$ $-$ $S\;|\;x$ $B$
$V$ $E$ NodeX $S\;|\;x$ $y\;|\;B$ $V\cup\\{y\\}$ $E\cup\\{(y,x)_{X}\\}$ $-$
$x\neq\mathrm{root}$ $S\;|\;y,x$ $B$ $V$ $E$ Left-EdgeX $S\;|\;y,x$ $B$ $V$
$E\cup\\{(x,y)_{X}\\}$ $-$ $\left\\{\begin{array}[]{l}x\not\in w_{1:n},\\\
y\neq\mathrm{root},\\\ y\not\leadsto_{G}x\end{array}\right.$ $S\;|\;x,y$ $B$
$V$ $E$ Right-EdgeX $S\;|\;x,y$ $B$ $V$ $E\cup\\{(x,y)_{X}\\}$ $-$ $S\;|\;y,x$
$B$ $V$ $E$ Left-RemoteX $S\;|\;y,x$ $B$ $V$ $E\cup\\{(x,y)_{X}^{*}\\}$ $-$
$S\;|\;x,y$ $B$ $V$ $E$ Right-RemoteX $S\;|\;x,y$ $B$ $V$
$E\cup\\{(x,y)_{X}^{*}\\}$ $-$ $S\;|\;x,y$ $B$ $V$ $E$ Swap $S\;|\;y$
$x\;|\;B$ $V$ $E$ $-$ $\mathrm{i}(x)<\mathrm{i}(y)$ $[\mathrm{root}]$
$\emptyset$ $V$ $E$ Finish $\emptyset$ $\emptyset$ $V$ $E$ $+$

Figure 8:  The transition set of TUPA. We write the stack with its top to the
right and the buffer with its head to the left. $(\cdot,\cdot)_{X}$ denotes a
primary $X$-labeled edge, and $(\cdot,\cdot)_{X}^{*}$ a remote $X$-labeled
edge. $\mathrm{i}(x)$ is the swap index (see §3.3). In addition to the
specified conditions, the prospective child in an Edge transition must not
already have a primary parent.

###  3.1 Transition Set

Given a sequence of tokens $w_{1},\ldots,w_{n}$, we predict a rooted graph $G$
whose terminals are the tokens. Parsing starts with the root node on the
stack, and the input tokens in the buffer.

The TUPA transition set, shown in Figure 8, includes the standard Shift and
Reduce operations, NodeX for creating a new non-terminal node and an
$X$-labeled edge, Left-EdgeX and Right-EdgeX to create a new primary
$X$-labeled edge, Left-RemoteX and Right-RemoteX to create a new remote
$X$-labeled edge, Swap to handle discontinuous nodes, and Finish to mark the
state as terminal.

The RemoteX transitions are not required for parsing trees, but as we treat
the problem as general DAG parsing due to the inclusion of enhanced
dependencies, we include these transitions.

Parser state$S$made$B$to feel very wel…$G$Wensubjwereauxhead

ClassifierBiLSTMEmbeddingsWewerewelcome.…MLPtransitionsoftmax

Figure 9: Illustration of the TUPA model, adapted from Hershcovich et al.
(2018). Top: parser state (stack, buffer and intermediate graph). Bottom:
BiLTSM architecture. Vector representation for the input tokens is computed by
two layers of bidirectional LSTMs. The vectors for specific tokens are
concatenated with embedding and numeric features from the parser state (for
existing edge labels, number of children, etc.), and fed into the MLP for
selecting the next transition.

###  3.2 Transition Classifier

To predict the next transition at each step, TUPA uses a BiLSTM with feature
embeddings as inputs, followed by an MLP and a softmax layer for
classification. The model is illustrated in Figure 9. Inference is performed
greedily, and training is done with an oracle that yields the set of all
optimal transitions at a given state (those that lead to a state from which
the gold graph is still reachable). Out of this set, the actual transition
performed in training is the one with the highest score given by the
classifier, which is trained to maximize the sum of log-likelihoods of all
optimal transitions at each step.

#### Features.

We use vector embeddings representing the words, lemmas, coarse (universal)
POS tags and fine-grained POS tags, provided by UDPipe 1.2 during test. For
training, we use the gold-annotated lemmas and POS tags. In addition, we use
one-character prefix, three-character suffix, shape (capturing orthographic
features, e.g., “Xxxx”) and named entity type, provided by
spaCy;444http://spacy.io punctuation and gap type features Maier and Lichte
(2016), and previously predicted edge labels and parser actions. These
embeddings are initialized randomly, except for the word embeddings, which are
initialized with the 250K most frequent word vectors from fastText for each
language Bojanowski et al. (2017),555http://fasttext.cc pre-trained over
Wikipedia and updated during training. We do not use word embeddings for
languages without pre-trained fastText vectors (Ancient Greek, North Sami and
Old French).

To the feature embeddings, we concatenate numeric features representing the
node height, number of (remote) parents and children, and the ratio between
the number of terminals to total number of nodes in the graph $G$.

Table 1 lists all feature used for the classifier. Numeric features are taken
as they are, whereas categorical features are mapped to real-valued embedding
vectors. For each non-terminal node, we select a head terminal for feature
extraction, by traversing down the graph according to a priority order on edge
labels (otherwise selecting the leftmost child). The priority order is:

    parataxis, conj, advcl, xcomp

Nodes |
---|---
$s_{0}$ | wmtuepT#^$xhqyPCIEMN
$s_{1}$ | wmtueT#^$xhyN
$s_{2}$ | wmtueT#^$xhy
$s_{3}$ | wmtueT#^$xhyN
$b_{0}$ | wmtuT#^$hPCIEMN
$b_{1},b_{2},b_{3}$ | wmtuT#^$
$s_{0}l,s_{0}r,s_{1}l,s_{1}r,$ $s_{0}ll,s_{0}lr,s_{0}rl,s_{0}rr,$ $s_{1}ll,s_{1}lr,s_{1}rl,s_{1}rr$ | wme#^$
$s_{0}L,s_{0}R,s_{1}L,$ $s_{1}R,b_{0}L,b_{0}R$ | wme#^$
Edges |
$s_{0}\to s_{1},s_{0}\to b_{0},$ $s_{1}\to s_{0},b_{0}\to s_{0}$ | x
$s_{0}\to b_{0},b_{0}\to s_{0}$ | e
Past actions |
$a_{0},a_{1}$ | eA
Global | node ratio
Table 1: Transition classifier features.
$s_{i}$: stack node $i$ from the top. $b_{i}$: buffer node $i$.
$xl$, $xr$ ($xL$, $xR$): $x$’s leftmost and rightmost children (parents). w:
head terminal text. m: lemma. u: coarse (universal) POS tag. t: fine-grained
POS tag. h: node’s height. e: label of its first incoming edge. p: any
separator punctuation between $s_{0}$ and $s_{1}$. q: count of any separator
punctuation between $s_{0}$ and $s_{1}$. x: numeric value of gap type Maier
and Lichte (2016). y: sum of gap lengths. P, C, I, E, and M: number of
parents, children, implicit children, remote children, and remote parents. N:
numeric value of the head terminal’s named entity IOB indicator. T: named
entity type. #: word shape (capturing orthographic features, e.g. "Xxxx" or
"dd"). ^: one-character prefix. $: three-character suffix.
$x\to y$ refers to the existing edge from $x$ to $y$. x is an indicator
feature, taking the value of 1 if the edge exists or 0 otherwise, e refers to
the edge label, and $a_{i}$ to the transition taken $i+1$ steps ago.
A refers to the action type (e.g. shift/right-edge/node), and e to the edge
label created by the action.
node ratio is the ratio between non-terminals and terminals Hershcovich et al.
(2017).

###  3.3 Constraints

During training and parsing, we apply constraints on the parser state to limit
the possible transitions to valid ones.

A generic constraint implemented in TUPA is that stack nodes that have been
swapped should not be swapped again Hershcovich et al. (2018). To implement
this constraint, we define a swap index for each node, assigned when the node
is created. At initialization, only the root node and terminals exist. We
assign the root a swap index of 0, and for each terminal, its position in the
text (starting at 1). Whenever a node is created as a result of a Node
transition, its swap index is the arithmetic mean of the swap indices of the
stack top and buffer head.

In addition, we enforce UD-specific constraints, resulting from the nature of
the converted DAG format: every non-terminal node must have a single outgoing
`head` edge: once it has one, it may not get another, and until it does, the
node may not be reduced.

##  4 Training details

The model is implemented using DyNet v2.0.3 Neubig et al.
(2017).666http://dynet.io Unless otherwise noted, we use the default values
provided by the package. We use the same hyperparameters as used in previous
experiments on UCCA parsing Hershcovich et al. (2018), without any
hyperparameter tuning on UD treebanks.

Hyperparameter | Value |
---|---|---
Pre-trained word dim. | 300 |
Lemma dim. | 200 |
Coarse (universal) POS tag dim. | 20 |
Fine-grained POS tag dim. | 20 |
Named entity dim. | 3 |
Punctuation dim. | 1 |
Shape dim. | 3 |
Prefix dim. | 2 |
Suffix dim. | 3 |
Action dim. | 3 |
Edge label dim. | 20 |
MLP layers | 2 |
MLP dimensions | 50 |
BiLSTM layers | 2 |
BiLSTM dimensions | 500 |
Table 2: Hyperparameter settings.

###  4.1 Hyperparameters

We use dropout Srivastava et al. (2014) between MLP layers, and recurrent
dropout Gal and Ghahramani (2016) between BiLSTM layers, both with $p=0.4$. We
also use word, lemma, coarse- and fine-grained POS tag dropout with
$\alpha=0.2$ Kiperwasser and Goldberg (2016): in training, the embedding for a
feature value $w$ is replaced with a zero vector with a probability of
$\frac{\alpha}{\\#(w)+\alpha}$, where $\\#(w)$ is the number of occurrences of
$w$ observed. In addition, we use node dropout Hershcovich et al. (2018): with
a probability of 0.1 at each step, all features associated with a single node
in the parser state are replaced with zero vectors. For optimization we use a
minibatch size of 100, decaying all weights by $10^{-5}$ at each update, and
train with stochastic gradient descent for $50$ epochs with a learning rate of
0.1, followed by AMSGrad Sashank J. Reddi (2018) for $250$ epochs with
$\alpha=0.001,\beta_{1}=0.9$ and $\beta_{2}=0.999$. We found this training
strategy better than using only one of the optimization methods, similar to
findings by Keskar and Socher (2017). We select the epoch with the best LAS-F1
on the development set. Other hyperparameter settings are listed in Table 2.

###  4.2 Small Treebanks

For corpora with less than 100 training sentences, we use $750$ epochs of
AMSGrad instead of $250$. For corpora with no development set, we use 10-fold
cross-validation on the training set, each time splitting it to 80% training,
10% development and 10% validation. We perform the normal training procedure
on the training and development subsets, and then select the model from the
fold with the best LAS-F1 on the corresponding validation set.

###  4.3 Multilingual Model

For the purpose of parsing languages with no training data, we use a
delexicalized multilingual model, trained on the shuffled training sets from
all corpora, with no word, lemma, fine-grained tag, prefix and suffix
features. We train this model for two epochs using stochastic gradient descent
with a learning rate of $0.1$ (we only trained this many epochs due to time
constraints).

###  4.4 Out-of-domain Evaluation

For test treebanks without corresponding training data, but with training data
in the same language, during testing we use the model trained on the largest
training treebank in the same language.

##  5 Results

Official evaluation was done on the TIRA online platform Potthast et al.
(2014). Our system (named “HUJI”) ranked 24th in the LAS-F1 ranking (with an
average of 53.69 over all test treebanks), 23rd by MLAS (average of 44.6) and
21st by BLEX (average of 48.05). Since our system only performs dependency
parsing and not other pipeline tasks, we henceforth focus on LAS-F1 Nivre and
Fang (2017) for evaluation.

After the official evaluation period ended, we discovered several bugs in the
conversion between the CoNLL-U format and the unified DAG format, which is
used by TUPA for training and is output by it (see §2). We did not re-train
TUPA on the training treebanks after fixing these bugs, but we did re-evaluate
the already trained models on all test treebanks, and used the fixed code for
converting their output to CoNLL-U. This yielded an unofficial average test
LAS-F1 of 58.48, an improvement of 4.79 points over the official average
score. In particular, for two test sets, `ar_padt` and `gl_ctg`, TUPA got a
zero score in the official evaluation due to a bug with the treatment of
multi-token words. These went up to 61.9 and 71.42, respectively. We also
evaluated the trained TUPA models on all available development treebanks after
fixing the bugs.

Table 3 presents the averaged scores on the shared task test sets, and Figure
10 the (official and unofficial) LAS-F1 scores obtained by TUPA on each of the
test and development treebanks.

| TUPA (official) | TUPA (unofficial) | UDPipe (baseline)
---|---|---|---
All treebanks | 53.69 | 58.48 | 65.80
Big treebanks | 62.07 | 67.36 | 74.14
PUD treebanks | 56.35 | 56.82 | 66.63
Small treebanks | 36.74 | 41.19 | 55.01
Low-resource | 8.53 | 12.68 | 17.17
Table 3: Aggregated test LAS-F1 scores for our system (TUPA) and the baseline
system (UDPipe 1.2).

af_afriboomsgrc_perseusgrc_proielar_padthy_armtdpeu_bdtbr_kebbg_btbbxr_bdtca_ancorahr_setcs_caccs_fictreecs_pdtcs_pudda_ddtnl_alpinonl_lassysmallen_ewten_gumen_linesen_pudet_edtfo_oftfi_ftbfi_pudfi_tdtfr_gsd

$71.78$

$1.92$

$1.89$

$0$

$7.59$

$56.63$

$7.29$

$75.03$

$8.17$

$77.52$

$75.77$

$74.3$

$70.87$

$72.03$

$68.5$

$66.77$

$69.92$

$66.2$

$72$

$66.05$

$67.34$

$74.12$

$67.45$

$15.44$

$72.35$

$68.47$

$66.19$

$74.97$

$71.85$

$52.97$

$61.3$

$61.9$

$22.78$

$56.82$

$10.18$

$75.05$

$8.42$

$77.53$

$75.85$

$73.92$

$70.81$

$71.87$

$68.37$

$66.84$

$70.22$

$67.45$

$72.1$

$66.05$

$67.4$

$74.4$

$67.58$

$23.39$

$72.36$

$68.47$

$66.34$

$74.98$

$72.65$

$52.31$

$62.12$

$62.33$

$57.85$

$75.14$

$77.65$

$75.24$

$75.44$

$71.57$

$72.72$

$66.64$

$71.52$

$60.16$

$72.44$

$67.87$

$68.22$

$69.86$

$72.13$

$65.45$

$80.42$

Test (official)Test (unofficial)Development

fr_sequoiafr_spokengl_ctggl_treegalde_gsdgot_proielel_gdthe_htbhi_hdtbhu_szegedzh_gsdid_gsdga_idtit_isdtit_postwitaja_gsdja_modernkk_ktbko_gsdko_kaistkmr_mgla_ittbla_perseusla_proiellv_lvtbpcm_nscsme_giella

$77.72$

$60.65$

$0$

$58.66$

$65.24$

$57.69$

$75.49$

$54.02$

$84.54$

$50.62$

$50.7$

$70.74$

$53.3$

$85.89$

$62.56$

$57.36$

$8.26$

$7.95$

$58.6$

$69.15$

$12.89$

$73.85$

$30.35$

$52.96$

$55.19$

$2.15$

$6.69$

$77.74$

$60.66$

$71.42$

$48.58$

$65.32$

$57.71$

$75.49$

$54.04$

$84.62$

$50.67$

$50.75$

$70.85$

$53.5$

$85.92$

$62.56$

$59.56$

$10.04$

$12.12$

$58.72$

$69.16$

$13.01$

$74.02$

$30.62$

$52.97$

$55.13$

$8.99$

$31.46$

$77.95$

$58.74$

$71.79$

$68.3$

$57.84$

$74.59$

$56.94$

$84.16$

$53.01$

$48.79$

$70.35$

$85.48$

$62.15$

$63.26$

$53.83$

$70.34$

$69.17$

$54.04$

$56.92$

no_bokmaalno_nynorskno_nynorskliafro_srcmfcu_proielfa_serajipl_lfgpl_szpt_bosquero_rrtru_syntagrusru_taigasr_setsk_snksl_ssjsl_sstes_ancorasv_linessv_pudsv_talbankenth_pudtr_imstuk_iuhsb_ufalur_udtbug_udtvi_vtb

$80.85$

$70.58$

$34.93$

$2.88$

$61.3$

$75.72$

$76.58$

$71.68$

$74.34$

$78.99$

$69.2$

$33.17$

$70.73$

$71.97$

$68.31$

$40.09$

$75.74$

$68.02$

$62.38$

$70.27$

$0.36$

$43.82$

$71.24$

$14.91$

$72.27$

$45.63$

$36.48$

$80.98$

$70.81$

$35.13$

$75.04$

$61.33$

$75.77$

$76.61$

$71.71$

$74.35$

$79.05$

$69.21$

$48.92$

$70.77$

$71.93$

$68.32$

$40.13$

$75.74$

$68.11$

$62.81$

$70.66$

$0.23$

$43.93$

$71.39$

$15.01$

$72.5$

$45.67$

$36.5$

$81.84$

$70.84$

$74.36$

$61$

$75.96$

$78.13$

$72.31$

$76.4$

$79.33$

$68.24$

$72.32$

$72.31$

$69.28$

$75.33$

$68.28$

$68.28$

$44.33$

$73.8$

$72.71$

$46.2$

$39.44$

Figure 10: TUPA’s LAS-F1 per treebank: official and unofficial test scores,
and development scores (where available).

###  5.1 Evaluation on Enhanced Dependencies

Since the official evaluation ignores enhanced dependencies, we evaluate them
separately using a modified version of the shared task evaluation
script777https://github.com/CoNLL-
UD-2018/HUJI/blob/master/tupa/scripts/conll18_ud_eval.py. We calculate the
enhanced LAS, identical to the standard LAS except that the set of
dependencies in both gold and predicted graphs are the enhanced dependencies
instead of the basic dependencies: ignoring null nodes and any enhanced
dependency sharing a head with a basic one, we align the words in the gold
graph and the system’s graph as in the standard LAS, and define

$P=\frac{\\#\mathrm{correct}}{\\#\mathrm{system}},R=\frac{\\#\mathrm{correct}}{\\#\mathrm{gold}},F1=2\cdot\frac{P\cdot
R}{P+R}.$

Table 4 lists the enhanced LAS precision, recall and F1 score on the test
treebanks with any enhanced dependencies, as well as the percentage of
enhanced dependencies in each test treebank, calculated as
$100\cdot\frac{\\#\mathrm{enhanced}}{\\#\mathrm{enhanced}+\\#\mathrm{words}}$.

Just as remote edges in UCCA parsing are more challenging than primary edges
Hershcovich et al. (2017), parsing enhanced dependencies is a harder task than
standard UD parsing, as the scores demonstrate. However, TUPA learns them
successfully, getting as much as 56.55 enhanced LAS-F1 (on the Polish LFG test
set).

| Enhanced LAS | % Enhanced
---|---|---
Treebank | P | R | F1
ar_padt | 28.51 | 16.24 | 20.69 | 5.30
cs_cac | 54.94 | 35.69 | 43.27 | 7.57
cs_fictree | 48.78 | 18.53 | 26.85 | 4.30
cs_pdt | 49.46 | 26.47 | 34.48 | 4.61
nl_alpino | 56.04 | 50.81 | 53.30 | 4.80
nl_lassysmall | 49.71 | 51.30 | 50.49 | 4.13
en_ewt | 57.36 | 52.05 | 54.58 | 4.36
en_pud | 58.99 | 50.00 | 54.13 | 5.14
fi_tdt | 40.20 | 31.37 | 35.24 | 7.34
lv_lvtb | 31.76 | 18.70 | 23.54 | 4.12
pl_lfg | 59.19 | 54.13 | 56.55 | 2.61
sk_snk | 37.28 | 21.61 | 27.36 | 3.91
sv_pud | 45.40 | 39.58 | 42.29 | 6.36
sv_talbanken | 50.15 | 43.20 | 46.42 | 6.89
Table 4: TUPA’s enhanced LAS precision, recall and F1 per test treebank with
any enhanced dependencies, and percentage of enhanced dependencies in test
treebank.

###  5.2 Ablation Experiments

The TUPA transition classifier for some of the languages uses named entity
features calculated by spaCy.888https://spacy.io/api/annotation For German,
Spanish, Portuguese, French, Italian, Dutch and Russian, the spaCy named
entity recognizer was trained on Wikipedia Nothman et al. (2013). However, the
English model was trained on
OntoNotes999https://catalog.ldc.upenn.edu/LDC2013T19, which is in fact not
among the additional resources allowed by the shared task organizers. To get a
fair evaluation and to quantify the contribution of the NER features, we re-
trained TUPA on the English EWT (`en_ewt`) training set with the same
hyperparameters as in our submitted model, just without these features. As
Table 5 shows, removing the NER features ($-$NER) only slightly hurts the
performance, by 0.28 LAS-F1 points on the test treebank, and 0.63 on the
development treebank.

As further ablation experiments, we tried removing POS features, pre-trained
word embeddings, and remote edges (the latter enabling TUPA to parse enhanced
dependencies). Removing the POS features does hurt performance to a larger
degree, by 2.87 LAS-F1 points on the test set, while removing the pre-trained
word embeddings even slightly improves the performance. Removing remote edges
and transitions from TUPA causes a very small decrease in LAS-F1, and of
course enhanced dependencies can then no longer be produced at all.

| LAS-F1 | Enhanced LAS-F1
---|---|---
Model | Test | Dev | Test | Dev
Original | 72.10 | 72.44 | 54.58 | 57.13
$-$NER | 71.82 | 71.81 | 55.31 | 54.65
$-$POS | 69.23 | 69.54 | 53.78 | 49.12
$-$Embed. | 72.33 | 72.55 | 56.26 | 54.54
$-$Remote | 72.08 | 72.32 | 0.00 | 0.00
Table 5: Ablation LAS-F1 and Enhanced LAS-F1 on the English EWT development
and test set. NER: named entity features. POS: part-of-speech tag features
(both universal and fine-grained). Embed.: external pre-trained word
embeddings (fastText). Remote: remote edges and transitions in TUPA.

##  6 Conclusion

We have presented the HUJI submission to the CoNLL 2018 shared task on parsing
Universal Dependencies, based on TUPA, a general transition-based DAG parser.
Using a simple conversion protocol to convert UD into a unified DAG format,
training TUPA as-is on the UD treebanks yields results close to the UDPipe
baseline for most treebanks in the standard evaluation. While other systems
ignore enhanced dependencies, TUPA learns to produce them too as part of the
general dependency parsing process. We believe that with hyperparameter tuning
and more careful handling of cross-lingual and cross-domain parsing, TUPA can
be competitive on the standard metrics too.

Furthermore, the generic nature of our parser, which supports many
representation schemes, as well as domains and languages, will allow improving
performance by multitask learning (cf. Hershcovich et al., 2018), which we
plan to explore in future work.

## Acknowledgments

This work was supported by the Israel Science Foundation (grant no. 929/17)
and by the HUJI Cyber Security Research Center in conjunction with the Israel
National Cyber Bureau in the Prime Minister’s Office.

## References

  * Abend and Rappoport (2013) Omri Abend and Ari Rappoport. 2013.  Universal Conceptual Cognitive Annotation (UCCA).  In _Proc. of ACL_ , pages 228–238.
  * Bojanowski et al. (2017) Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017.  Enriching word vectors with subword information.  _TACL_ , 5:135–146.
  * Gal and Ghahramani (2016) Yarin Gal and Zoubin Ghahramani. 2016.  A Theoretically Grounded Application of Dropout in Recurrent Neural Networks.  In D D Lee, M Sugiyama, U V Luxburg, I Guyon, and R Garnett, editors, _Advances in Neural Information Processing Systems 29_ , pages 1019–1027. Curran Associates, Inc.
  * Hershcovich et al. (2017) Daniel Hershcovich, Omri Abend, and Ari Rappoport. 2017.  A transition-based directed acyclic graph parser for UCCA.  In _Proc. of ACL_ , pages 1127–1138.
  * Hershcovich et al. (2018) Daniel Hershcovich, Omri Abend, and Ari Rappoport. 2018.  Multitask parsing across semantic representations.  In _Proc. of ACL_ , pages 373–385.
  * Keskar and Socher (2017) Nitish Shirish Keskar and Richard Socher. 2017.  Improving generalization performance by switching from Adam to SGD.  _CoRR_ , abs/1712.07628.
  * Kiperwasser and Goldberg (2016) Eliyahu Kiperwasser and Yoav Goldberg. 2016.  Simple and accurate dependency parsing using bidirectional LSTM feature representations.  _TACL_ , 4:313–327.
  * Maier and Lichte (2016) Wolfgang Maier and Timm Lichte. 2016.  Discontinuous parsing with continuous trees.  In _Proc. of Workshop on Discontinuous Structures in NLP_ , pages 47–57.
  * Neubig et al. (2017) Graham Neubig, Chris Dyer, Yoav Goldberg, Austin Matthews, Waleed Ammar, Antonios Anastasopoulos, Miguel Ballesteros, David Chiang, Daniel Clothiaux, Trevor Cohn, Kevin Duh, Manaal Faruqui, Cynthia Gan, Dan Garrette, Yangfeng Ji, Lingpeng Kong, Adhiguna Kuncoro, Gaurav Kumar, Chaitanya Malaviya, Paul Michel, Yusuke Oda, Matthew Richardson, Naomi Saphra, Swabha Swayamdipta, and Pengcheng Yin. 2017.  DyNet: The dynamic neural network toolkit.  _CoRR_ , abs/1701.03980.
  * Nivre (2003) Joakim Nivre. 2003.  An efficient algorithm for projective dependency parsing.  In _Proc. of IWPT_ , pages 149–160.
  * Nivre and Fang (2017) Joakim Nivre and Chiao-Ting Fang. 2017.  Universal dependency evaluation.  In _Proceedings of the NoDaLiDa 2017 Workshop on Universal Dependencies (UDW 2017)_ , pages 86–95.
  * Nivre et al. (2016) Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajic, Christopher D. Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, Reut Tsarfaty, and Daniel Zeman. 2016.  Universal dependencies v1: A multilingual treebank collection.  In _Proc. of LREC_.
  * Nothman et al. (2013) Joel Nothman, Nicky Ringland, Will Radford, Tara Murphy, and James R Curran. 2013\.  Learning multilingual named entity recognition from wikipedia.  _Artificial Intelligence_ , 194:151–175.
  * Potthast et al. (2014) Martin Potthast, Tim Gollub, Francisco Rangel, Paolo Rosso, Efstathios Stamatatos, and Benno Stein. 2014.  Improving the reproducibility of PAN’s shared tasks: Plagiarism detection, author identification, and author profiling.  In _Information Access Evaluation meets Multilinguality, Multimodality, and Visualization. 5th International Conference of the CLEF Initiative (CLEF 14)_ , pages 268–299, Berlin Heidelberg New York. Springer.
  * Reddy et al. (2017) Siva Reddy, Oscar Täckström, Slav Petrov, Mark Steedman, and Mirella Lapata. 2017.  Universal semantic parsing.  pages 89–101.
  * Sashank J. Reddi (2018) Sanjiv Kumar Sashank J. Reddi, Satyen Kale. 2018.  On the convergence of Adam and beyond.  _ICLR_.
  * Schuster and Manning (2016) Sebastian Schuster and Christopher D. Manning. 2016.  Enhanced English Universal Dependencies: An improved representation for natural language understanding tasks.  In _Proc. of LREC_. ELRA.
  * Silveira et al. (2014) Natalia Silveira, Timothy Dozat, Marie-Catherine de Marneffe, Samuel Bowman, Miriam Connor, John Bauer, and Chris Manning. 2014.  A gold standard dependency corpus for English.  In _Proc. of LREC_.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: A simple way to prevent neural networks from overfitting.  _Journal of Machine Learning Research_ , 15:1929–1958.
  * Straka et al. (2016) Milan Straka, Jan Hajič, and Jana Straková. 2016.  UDPipe: trainable pipeline for processing CoNLL-U files performing tokenization, morphological analysis, POS tagging and parsing.  In _Proceedings of the 10th International Conference on Language Resources and Evaluation (LREC 2016)_ , Portorož, Slovenia. European Language Resources Association.
  * Straka and Straková (2017) Milan Straka and Jana Straková. 2017.  Tokenizing, pos tagging, lemmatizing and parsing ud 2.0 with udpipe.  In _Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies_ , pages 88–99, Vancouver, Canada. Association for Computational Linguistics.
  * Zeman et al. (2018) Daniel Zeman, Filip Ginter, Jan Hajič, Joakim Nivre, Martin Popel, and Milan Straka. 2018.  CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies.  In _Proceedings of the CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies_ , Brussels, Belgium. Association for Computational Linguistics.


# Notes on Refactoring Exponential Macros in Common Lisp
Or: Multiple @Body Considered Harmful

Michael Wessel<EMAIL_ADDRESS>SRI International333 Ravenswood
AvenueMenlo ParkCaliforniaUSACA 94025

###### Abstract.

I recently consulted for a very big Common Lisp project having more than one
million lines of code (including comments). Let’s call it “System X” in the
following. System X suffered from extremely long compilation times; i.e., a
full recompile took about 33:17 minutes on a 3.1 GHz MacBook Pro Intel Core i7
with SSD and 16 GBs of RAM, using ACL 10.1. It turns out that a number of
macros were causing an exponential code blowup. With these macros refactored,
the system then recompiled in 5:30 minutes — a speedup by a factor of
$\approx$ 6\. In this experience report, I will first illuminate the problem,
and then demonstrate two potential solutions in terms of macro refactoring
techniques. These techniques can be applied in related scenarios.

Common Lisp, Macros, Exponential Code Blowup, Macro Refactoring, Very Large
Lisp Systems

††conference: ; ††booktitle: ;

##  1\. Introduction

Macros and the ability to program language extensions in the language _itself_
is one of the most beloved and powerful features of many members of the Lisp
family, and especially in Common Lisp (Steele, 1990), which has been coined a
_programmable programming language_ by John Foderaro. The availability of the
full programming language at macro expansion / compile time makes Common Lisp
an ideal implementation platform for Domain Specific Languages (Wessel, 2022;
Michael Wessel, 2008), and always has been (i.e., Lisp was an early target
platform for object-oriented programming concepts (Bobrow et al., 1986)).
Unlike macros in most other programming languages, Common Lisp allows macros
to be defined in the same language. Thanks to its _homoiconicity_ , it offers
a unified “programs as data” representation and allows the construction,
manipulation, and most importantly, _computation_ of macro expansions in the
language _itself._ The full power of the language is always available – not
only at runtime, but also at _macro-expansion (“compile”) time_ (Graham, 1996,
1994; Norvig, 1992).

As always, with great power comes great responsibility: macros can be a
double-edged sword. This is especially true in languages like Common Lisp,
where the main development mode is not the traditional “edit — full recompile
– debug” cycle, but an interactive, dynamic one, based on incremental
redefinition, evaluation, and compilation. Unintended consequences of changes
to the code base, especially macros, can sometimes be left unnoticed for a
longer time period if full recompiles of the system are delayed. This holds
true especially in larger projects with bigger teams. Once compilation times
exceed half an hour, full recompilation is avoided by the developers during
daily development, and a build system will usually be entrusted to deliver new
base images overnight, containing the changes of multiple developers. Of
course, regressions will be recorded and monitored on a daily basis. But even
if _build times_ and _the size of the fast load (FASL) files_ are reported by
the build system, it might not be entirely clear which changes increased the
build time — after all, the build system might just have had a bad night and
was busy performing backups as well, and so on and so forth.

Consequently, tracing back unintended system behavior to (no longer so recent)
changes to the code base can become more difficult. For this reason,
incremental compilation of Common Lisp code can become a drawback. I advise
that developers should not only check for unintended changes in semantics and
functional characteristics of the system caused by their code changes, but
also to the non-functional characteristics (e.g., FASL sizes and build time).
And especially for macros.

Figure 1. Macro with exponential macro expansion

Figure 2. Macro with linear macro expansion

I recently had the opportunity to work on “System X”, which is a very large,
multiple decades in-the-making Common Lisp system with over one million lines
of code. System X suffered from extremely long compilation times: a full
compile required 33:17 minutes on a 3.1 GHz MacBook Pro Intel Core i7 using an
SSD and 16 GBs of RAM, using ACL 10.1. It turned out that _three badly
engineered macros_ were causing an exponential code blowup. With these macros
refactored, a full recompile is possible in 5:30 minutes — a speedup by a
factor of $\approx$ 6.

In this experience report, I will first illuminate the problem, and then
demonstrate two possible solutions in terms of macro refactorings. The
effectiveness of the refactoring methods is not only demonstrated by the 6
fold reduction in compilation time, but also in terms of FASL size reductions.
The used methodology can be applied in related scenarios. I conclude with some
advice.

##  2\. The Problem

The problems of System X are easily illustrated with a few synthetic examples.
Consider the context-establishing with-bad macro in Figure 1. Like many with-
macros, it utilizes a _special variable_ (here, *a*) with dynamic scope to
control the runtime behavior beyond its lexical scope. In the example, the
binding of the dynamic variable *a* determines if with-bad macro’s expansion
prints x or (1+ x).

This macro serves to illustrate the problem of _exponential macro expansion_.
Frequently, with- macros are nested, which can obscure the magnitude of such
problems from developers. For example, the macro might be part of a framework
for website HTML generation and, as such, contain macros such as with-head,
with-body, with-table, and so on. Not only will complex web pages contain many
deeply nested occurrences of these macros, but it might also be the case that
certain common design elements of such pages (common headers, footers, and
navigation menus) have been aggregated into even higher-level macros, which
are then being used in other macros, and so forth.

It should be noted that Common Lisp does not contain a macroexpand-all
recursive macroexpansion facility; only macroexpand-1 is offered. This
provides a single level of macro expansion. However, third-party solutions are
available. I used one of these packages to diagnose the problems in System X
(Baringer, 2023a, b).

Considering the macroexpansion of blowup containing four nested with-bad
occurrences in Figure 1, we can clearly see that it is exponential in the size
of the original definition, due to the duplicated ,@body forms. In general,
given a nesting depth of $n$, the size of the expanded macro code is $2^{n}$.
I even spotted with- macros with more than two ,@body forms “in the wild”; in
general, a with- macro with $m$ ,@body forms will expand to size $m^{n}$ if
nested $n$ times. This should clearly be avoided.

Sometimes, such an _exponential macro_ is easy to fix. In the case of Figure
1, it suffices to move the ,@body form into a local function definition (flet)
and call the local function in the two places at runtime rather than
duplicating the code. The expansion size of the resulting with-good macro
shown in Figure 2 is now linear in the nesting depth rather than exponential.

Unfortunately, exponential macros are not always easily fixed. For example,
say the macro argument x in with-good was used to establish lexical bindings
for use _within_ the ,@body instead of just being an “input parameter” to the
macro. In this case, a (let ((,x ...)) ... ,@body) would be used within the
macro to establish a corresponding lexical scope for ,x. Moreover, the
concrete binding to ,x might depend on complex runtime and compile time
conditions. In particular, the value of ,x might depend on the runtime value
of *a*, which is unknown at compile time / macroexpansion time, and hence,
cannot be anticipated by means of code rewritings / transformations. It is
thus important that the correct lexical contexts are established, for example,
via the local function’s lambdalist.

Of such “more difficult” nature was the exponential macro that I had to
refactor in System X. Instead of revealing the details of this macro I will
use the synthetic example from Figure 3 in the following. This macro has a
similar complexity and serves to illustrate the problems and possible
solutions.

Figure 3. The anti-pattern of an exponential with- macro as found in System X

The idea behind with-bad-recording is to establish a context of dynamic scope
for keeping track of “instructions” that are being recorded onto a stack;
these instructions can be entries to a log file, an output recording
presentation history, etc. The “hidden” special variable *recording-stack*
(with dynamic scope) is used to keep track of the values on the stack. This
special variable is not supposed to be visible to the user’s code (it is
“internal”); instead, accessor functions (or macros) such as (do-something-
and-record x) are used to work with it.

Moreover, for whatever reason, clients of with-bad-recording also like to know
whether the current invocation is toplevel, or already part of a “nested”
invocation at runtime; hence, a variable nested-p can be passed in which is
then bound to nil or t, respectively. To decide this, another special variable
*within-recording* had been (maybe redundantly) introduced by the original
author of the macro. Again, this is an “internal” special variable which
should not be visible to the user code, hence, nested-p is supplied. A use
case is shown in test-bad-recording. Note that the runtime value of n-p (i.e.,
,nested-p in the macro) is not knowable from the lexical definition, as test-
bad-recording might occur nested within another with-bad-recording context at
runtime. The use case shows that the stack holds (3 2 1) in the end.

Figure 4. Replacing multiple ,@body with local function calls broke the macro
— see the compiler warning

Clearly, this macro now has the potential for an exponential macro expansion,
and test-bad-recording already suffers from this blowup. Can we fix this macro
in the same way as in Figure 2?

##  3\. First Solution — Refactoring with FLET

Figure 5. Using local function variables to establish lexical context — note
that the dynamic context is still established by the original branching
structure

The first solution is a generalization of the idea we already discussed in
Section 2 — we replaced each ,@body by a call to a single local function
containing a single ,@body. We can use FLET or LABELS for that.

A naive attempt of fixing with-bad-recording is shown in Figure 4. This macro
is now clearly broken, as ,@body refers to ,nested-p = n-p, which is not
visible in the outer flet \- hence the compiler warning that this variable is
now unbound. The obvious solution is hence to make ,nested-p = n-p an argument
of the local function so that the required lexical variables for ,@body are
established by the local function. This is shown in Figure 5.

A further complication is introduced if the lexical variable is modified in
one of the branches — consider the variation with-bad-recording-v2 shown in
Figure 6, where nested-p is replaced by control-p. The value of control-p
influences the output, and it might be set from either within the user-
supplied ,@body code, or from within the macro itself. Refactoring such a
macro then becomes less mechanical, and more care is needed to ensure that the
right lexical environments are established.

Figure 6. If lexical variables that are arguments to the macro are modified,
such as control-p, then refactoring becomes more involved

In particular, we realize that the value of control-p must be changed from
_within_ the local function so that the call (process-recordings-v2
,control-p) will get the value of ,control-p from the correct lexical scope. A
possible solution is shown in Figure 6; the branch-p argument is used to
inform the local function about the invocation context, and, based on its
value, the local function has to accommodate, or “emulate”, the different
runtime behaviors from the macro’s original branches. This might not always be
possible, but is rather trivial in this case.111Please note that we are
ignoring potential differences in the returned value of these macros for now;
usually, with- macros do not return values, but this is a convention and not a
strict requirement.

Figure 7. Accommodating different macro branches in one function with the
branch-p argument

This wraps up the discussion of the first refactoring strategy. In a nutshell,
the original branching structure establishing different lexical and dynamic
scopes is maintained. A common ,@body form must be found which is able to
reproduce the original runtime behaviors, and it is placed within a local
function. The required lexical contexts are established by the local function
and removed from the original branching structure. Additional control
parameters such as branch-p are used to select branch-specific runtime
behavior. In particular, we maintain the branching structure of the original
macro in order to establish the right bindings for the special variables, and
to set up the correct lexical contexts by calling the local function
accordingly.

A potential drawback of the refactoring pattern just discussed is the
introduction of additional local functions and the additional runtime overhead
of additional function calls.222It might be possible to declare these local
functions as inline though.

More severely, the (full) macro expansion of the refactored macro now
obfuscates the original structure of the macro — it is “inside out” because we
employed _functional composition_ to implement _program sequencing;_ as can be
seen in Figure 2, (princ 6) now textually precedes (princ 3), contrary to the
original definition. In particular, the ,@body’s of the local functions are
now “detached” from the original branching structure, making the macro
expansion more difficult to understand.

If these are serious concerns, the following alternative refactoring strategy
can be applied.

##  4\. Second Solution — Refactoring with PROGV

In the following, we are _not_ using a local function that can be called from
different branches of the rewritten macro. Instead we are trying to unify the
original branching structure establishing different lexical and dynamic
contexts into _one_ common structure. It turns out that establishing the right
(conditional) bindings for the special variables is the biggest obstacle, and
we will be using progv for this purpose.

The following set of steps can be understood as a semantics-preserving code
rewriting procedure / transformer. We will apply the following to the with-
bad-recording macro to tame the exponential beast and rewrite it into a linear
macro:

Step 1:

Macroexpand / rewrite all branching special forms (unless, when, cond, …) into
ifs (in our examples, this is already the case, so the step doesn’t apply):

    (if <condition>
         (let ( <binding 11> ... <binding 1n> )
             ,@body)
       (let ( <binding 21>  ... <binding 2m> )
           ,@body))

Step 2:

Ensure that all lets in all branches refer to the same variables, and in the
same order. If <binding ij> = (,var val) and var is a macro argument, then all
branches already must contain a valid (,var val) binding. Otherwise, var would
be unbound in (some branches of) ,@body (e.g., the macro was already defective
in the first place).

If var is a special variable instead, i.e., *var*, then, in case the branch
_did not_ contain a <binding> = (*var* val), we introduce a “dummy” binding
<binding> = (*var* *var*) for now. The idea is to express that we _intend_ to
_not_ alter the binding of *var* dynamically. Note that this is
_unproblematic_ where *var* is used as a “read only” variable, but problematic
in cases such as with-bad-recording, where *recording- stack* is modified; see
below for the solution.

Hence, we now have the same number $k$ of (var val) bindings in each let, with
potentially (not necessarily) different val’s; note that $max(n,m)\leq k\leq
n+m$:

    (if <condition>
         (let ( (<var1 val11>) ... (<vark val1k>) )
             ,@body)
      (let ( (<var1 val21>)  ... (<vark val2k>) )
          ,@body))

Step 3:

Next, we remove the different branches, establish all the bindings in a single
let, and recover the effects of the <condition> by establishing different
bindings within the let binding forms itself. Since we removed the different
branches from the surrounding code by factoring in / moving the condition
_into_ the let lambda lists, we have also eliminated the multiple ,@body
occurrences:

    (let ( ( <var1> (if <condition> <val11> <val21>) )
              ...
              ( <vark> (if <condition> <val1k> <val2k>) ))
      ,@body)

Step 4:

So far so good — there is one problem though: this only works for dynamically
scoped variables that are used in a “read only” fashion. As already mentioned,
we have introduced a “dummy” binding <binding> = ( *recording-stack*
*recording-stack* ) to express that we wish to leave the binding of
*recording-stack* _untouched._ But we changed it by establishing a new binding
frame — we “shadowed” the previously established binding. With let/let*, there
is no solution to this.

The effect is illustrated in Figure 8 — the refactored macro is clearly broken
now, as illustrated with the example call (test-recording-v4). Instead of
returning (3 2 1) like in the original, we are now only getting the first
value that was pushed onto the stack: (1).

Figure 8. Shadowing *recording-stack* broke the macro

However, the code rewritings have brought us onto the right track. We only
need to avoid shadowing in cases were we do not wish to alter a dynamic
variable. Fortunately, there is a solution to this in Common Lisp, and one has
to congratulate the designers of Common Lisp for anticipating such a scenario:
progv can do the job as follows:

     (progv
       (when alters-*var*
           (list ’*var*))
       (list val)

If alters-*var* = T, the form is equivalent to (progv ’(*var*) (list val))
hence establishing a new binding for *var*. Otherwise, if alters-*var* = NIL,
then the form is equivalent to (progv nil (list val)), leaving *var*
unchanged.

Hence, the final step involves “splitting up” the single let (or let*), and
reestablishing the “problematic” special bindings via progv instead, in the
manner just described. Since this step is hard to templatize, let’s look at
the final rewritten example macro in Figure 9 instead. As can be seen from the
test invocation, it behaves correctly, and its expansion is clearly linear.

Figure 9. The rewritten linear with- macro — thanks to progv

Even though context establishing macros are usually not used for their return
values, it is nevertheless advisable to accommodate for such, and so we did in
Figure 9. Inspecting all use cases of the macro in the source code of a very
large system such as System X to identify such use cases is more time
consuming than to cater for such cases correctly from the beginning. Hence,
the rewritten macro in Figure 9 also returns the same values as the original
(utilizing multiple-value-list and values).

##  5\. Effectiveness of the Techniques

We counted the number of macro function invocations (“macro expansion calls”)
that occurred during a full recompilation of System X and compared the results
between the original and the PROGV refactored versions.333Obviously, the FLET-
based technique will yield the same results.

For the original version, we counted $12816+2431+2432=17679$ calls for our
three critical exponential macros. Compared to $882+530+531=1466$ invocations
for the refactored version, with a ratio of $17679/1466=12.05$. Referring to
the $m^{n}$ notation from Section 2, we have $m=2$ (two ,@body’s), and can
hence assume an average nesting depth of about $log_{2}12.05\approx 3.6=n$.

Figure 10. A macro that cannot be refactored using the discussed techniques

The biggest FASL size reduction was observed for a file that shrank from 53
MBs to only 2 MBs — a factor of 26.5! Since $log_{2}26.5\approx 4.7$ we can
assume a more deeply nested use of the exponential macros there.

These are rough estimates, but the numbers speak a clear language: for large
Lisp systems, the impact of even moderately deeply nested (i.e., $3\leq n\leq
5$) exponential macros can be catastrophic in terms of compilation time and
FASL sizes.

##  6\. Limitations of the Techniques

Whereas these refactoring patterns should cover a large region of exponential
with- cases in practice, they are far from offering a complete solution. An
example of a macro that _cannot_ be refactored with the so-far discussed
techniques is shown in Figure 10. Essentially, the problem is that the _else_
branch establishes a lexical context for ,control-p, but the _then_ branch
doesn’t, and that it is impossible to know at compile time which branch will
be active. A solution akin to progv would be needed, but for _lexical_
variables.

##  7\. Conclusion

I presented techniques for refactoring exponential macros into linear ones.
From my experience with System X, I learned that three (not overly carefully
designed) macros can suffice to severely (i.e., exponentially) affect
compilation time and FASL size.

It is not entirely fair to blame the original designers of these macros for
causing so much trouble in the later life of System X. Each project starts
small, and the macros were originally doing fine. Only later in System X’s
life cycle did the effects of exponential macro expansion degrade its
compilation time (and corresponding FASL file sizes) drastically. Incremental
development and compilation, over-night build systems, multiple developers,
and a focus on _functional_ rather than _non-functional_ system
characteristics were all factors that contributed to code that grew like a
malignant cancer. The power of Common Lisp macros can be a double-edged sword
and needs to be handled with diligence and delicacy. Fortunately, Common Lisp
is also powerful enough to offer a cure to these problems, as we tried to
illustrate in this Experience Report. We hope that our experience will help
other developers to avoid such situations in their own projects.

Could some of this rewriting process be automated? For sure, compilers could
warn about potentially expensive macro expansions, or try to identify
exponential expansion. A macroexpand-all as part of a Common Lisp IDE would
certainly help as well. Interestingly, the code rewriting techniques described
in Sections 3 and 4 seems straight-forward enough that it _might be possible_
to automate, at least for certain macro patterns (but might be undecidable in
general). This could be interesting future research, and I would appreciate
any pointers and feedback from the Lisp community — surely, this problem is
not new, yet I wasn’t able to find papers that would cover this topic. I hope
that this report will fill this gap, and also raise awareness in Common Lisp
developers for such issues.

###### Acknowledgements.

First and foremost, I would like to thank the Principial Investigator (PI) of
Project X for allowing me to consult for System X, and for triggering the
investigation of long compilation times in System X. This PI also read a Draft
and suggested to substantiate the findings with hard numerical evidence. This
led to the addition of Section 5. Next, I wish to thank the anonymous
reviewers for pointing out omissions in the original Draft that made the
transition from the local function call-based solution (as illustrated with
the with-good macro) to the progv-based solution seem unmotivated. As pointed
out by the reviewers, the original Draft did mention the technique, but
erroneously gave the impression that it could not be applied to accommodate
for lexical variables. This is now demonstrated in Section 3, which was
missing from the original Draft. I like to thank all reviewers for their
comments and time. In my humble opinion, both refactoring methods have their
own strengths and weaknesses, and I mentioned some of them at the end of
Section 3. This work was funded by the National Institute of Allergy and
Infectious Diseases of the National Institutes of Health under award number
R01AI160719. The content is solely the responsibility of the authors and does
not necessarily represent the official views of the National Institutes of
Health. The NIH did not play any role in the design of the study; nor in
collection, analysis, or interpretation of data; nor in writing the
manuscript.

## References

  * (1)
  * Baringer (2023a) Marco Baringer. Accessed: 2-26-2023a.  ARNESI Library.  https://bese.common-lisp.dev/arnesi.html
  * Baringer (2023b) Marco Baringer. Accessed: 2-26-2023b.  ARNESI Library.  https://quickref.common-lisp.net/arnesi.html
  * Bobrow et al. (1986) Daniel G. Bobrow, Kenneth Kahn, Gregor Kiczales, Larry Masinter, Mark Stefik, and Frank Zdybel. 1986\.  CommonLoops: Merging Lisp and Object-Oriented Programming. In _Conference Proceedings on Object-Oriented Programming Systems, Languages and Applications_ (Portland, Oregon, USA) _(OOPSLA ’86)_. Association for Computing Machinery, New York, NY, USA, 17–29.  https://doi.org/10.1145/28697.28700
  * Graham (1994) P. Graham. 1994\.  _On Lisp_.  Prentice-Hall.
  * Graham (1996) P. Graham. 1996\.  _ANSI Common Lisp_.  Prentice-Hall.
  * Michael Wessel (2008) Ralf Möller Michael Wessel. 2008\.  Software Abstractions for Description Logic Systems. In _Proceedings of the 5th European Lisp Workshop (ELW’08)_.  {http://www.european-lisp-workshop.org/archives/08.wessel.pdf}
  * Norvig (1992) P. Norvig. 1992\.  _Artificial Intelligence Programming: Case Studies in Common Lisp_.  Morgan Kaufmann.
  * Steele (1990) Guy L. Steele, Jr. 1990\.  _Common Lisp – The Language, Second Edition_.  Digital Press.
  * Wessel (2022) Michael Wessel. 2022\.  An Ontology-Based Dialogue Management Framework for Virtual Personal Assistants in Common Lisp. In _European Lisp Symposium ’23 (ELS’23)_.  {https://doi.org/10.5281/zenodo.6335631}


# On the Accuracy of Hotelling-Type Tensor Deflation:
A Random Tensor Analysis

###### Abstract

Leveraging on recent advances in random tensor theory, we consider in this
paper a rank-$r$ asymmetric spiked tensor model of the form
$\sum_{i=1}^{r}\beta_{i}{\mathcal{A}}_{i}+{\mathcal{W}}$ where $\beta_{i}\geq
0$ and the ${\mathcal{A}}_{i}$’s are rank-one tensors such that
$\langle{\mathcal{A}}_{i},{\mathcal{A}}_{j}\rangle\in[0,1]$ for $i\neq j$,
based on which we provide an asymptotic study of Hotelling-type tensor
deflation in the large dimensional regime. Specifically, our analysis
characterizes the singular values and alignments at each step of the deflation
procedure, for asymptotically large tensor dimensions. This can be used to
construct consistent estimators of different quantities involved in the
underlying problem, such as the signal-to-noise ratios $\beta_{i}$ or the
alignments between the different signal components
$\langle{\mathcal{A}}_{i},{\mathcal{A}}_{j}\rangle$.

Index Terms— Random Tensor Theory, Hotelling Deflation, Low-rank Tensor
Decomposition, Parameter Estimation.

##  1 INTRODUCTION

The analysis of random tensors has attracted significant attention in the last
decade since the introduction of the concept of tensor PCA, which generalizes
principal component analysis to high-order arrays. The first model introduced
in [1] is the so-called spiked tensor model of the form
$\beta{\bm{x}}^{\otimes d}+{\mathcal{W}}/\sqrt{n}$ where
${\bm{x}}\in{\mathbb{R}}^{n}$ is some high-dimensional unit vector referred to
as a spike, ${\mathcal{W}}$ is a symmetric random tensor of order $d$ having
standard Gaussian entries and $\beta\geq 0$ is a parameter controlling the
signal-to-noise ratio.

Follow-up results have improved the understanding of the behavior of the
spiked model and allowed to identify theoretical and/or algorithmic guarantees
in terms of efficient signal recovery. In particular, several works [2, 3, 4,
5, 6] have focused on the asymptotic (large dimensional) regime $n\to\infty$.
We briefly summarize their main findings as follows: for $d\geq 3$, it has
been shown that there exists a statistical threshold $\beta_{stat}=O(1)$ below
which it is information-theoretically impossible to recover or even detect the
spike, while above $\beta_{stat}$ recovery is theoretically possible finding a
critical point of the square loss. Moreover, the asymptotic alignment
$\langle{\bm{x}},{\bm{u}}\rangle$ between ${\bm{x}}$ and a critical point
${\bm{u}}$ is given in terms of $\beta$. Besides, since almost all tensor
problems, e.g. finding the critical points, are NP-hard [7], many researchers
were interested in exhibiting an algorithmic threshold for $\beta$ above which
recovery could be possible with a polynomial-time algorithm. The authors in
[1] introduced a method for estimating ${\bm{x}}$ based on tensor unfolding
and showed that spike recovery is possible above the algorithmic threshold
$\beta_{algo}=O(n^{\frac{d-2}{4}})$.

These ideas were further generalized to the asymmetric spiked tensor model of
the form
$\beta{\bm{x}}_{1}\otimes\cdots\otimes{\bm{x}}_{d}+{\mathcal{W}}/\sqrt{\sum_{i}n_{i}}$,
where ${\bm{x}}_{i}\in{\mathbb{R}}^{n_{i}}$ are unit vectors and
${\mathcal{W}}$ is a random tensor with standard Gaussian i.i.d. entries. In
particular, [8] provided an analysis of the unfolding method for asymmetric
tensors and determined the algorithmic threshold to be
$\beta_{algo}=O(n^{\frac{d-2}{4}})$ when $n_{i}=n$ for all $i$, while [9]
showed the existence of a statistical threshold $\beta_{s}=O(1)$ above which a
local solution ${\bm{u}}_{i}$ of the MLE aligns with the signal, and further
quantified the asymptotic alignments
$\langle{\bm{x}}_{i},{\bm{u}}_{i}\rangle$.

### Contribution:

In this paper, we address the extension of these ideas to a more general
setting, namely asymmetric _low-rank_ spiked tensors of the form
$\sum_{i=1}^{r}\beta_{i}{\bm{x}}_{i,1}\otimes\cdots\otimes{\bm{x}}_{i,d}+{\mathcal{W}}/\sqrt{\sum_{i}n_{i}}$
where ${\bm{x}}_{i,j}\in{\mathbb{R}}^{n_{j}}$ are unit vectors. Specifically,
we consider the study of a simple deflation procedure, first introduced by
Hotelling in the context of matrix principal component analysis [10] and still
used in modern applications such as the recent AlphaTensor model [11], which
consists in iterated rank-one approximations followed by subtraction of the
estimated rank-one component.

We focus on the case where the spike components are not orthogonal to each
other. While the orthogonal case (i.e.
$\langle{\bm{x}}_{i,k},{\bm{x}}_{j,k}\rangle=0$ for all $i\neq j$) trivially
boils down to the rank-one model studied in [5, 9], in the considered setting,
i.e. $\langle{\bm{x}}_{i,k},{\bm{x}}_{j,k}\rangle\in(0,1)$ for $i\neq j$, the
behavior of the deflation method is more complex, as depicted in Figure 1 in
the simplified case ${\bm{x}}_{i,1}=\dots={\bm{x}}_{i,d}={\bm{x}}_{i}$ for
$i=1,2$.

Fig. 1: Result of tensor deflation applied to a noisy rank-two spiked model
$\beta_{1}{\bm{x}}_{1}^{\otimes 3}+\beta_{2}{\bm{x}}_{2}^{\otimes
3}+{\mathcal{W}}/\sqrt{n}$. The first row corresponds to the first deflation
step (yielding ${\bm{u}}_{1}$) while the second row corresponds to the second
deflation step (yielding ${\bm{u}}_{2}$). The plots depict the alignments
$\langle{\bm{x}}_{i},{\bm{u}}_{j}\rangle$ in terms of $\beta_{1}$ for a fixed
$\beta_{2}$. In the orthogonal case
$\langle{\bm{x}}_{1},{\bm{x}}_{2}\rangle=0$ (left column), deflation is shown
to successfully identify the strongest and second strongest components, i.e.
${\bm{u}}_{1}$ aligns with ${\bm{x}}_{1}$ and ${\bm{u}}_{2}$ aligns with
${\bm{x}}_{2}$ when $\beta_{1}>\beta_{2}$, while ${\bm{u}}_{1}$ aligns with
${\bm{x}}_{2}$ and ${\bm{u}}_{2}$ aligns with ${\bm{x}}_{1}$ when
$\beta_{1}<\beta_{2}$. For the correlated setting, on the other hand (right
column, $\langle{\bm{x}}_{1},{\bm{x}}_{2}\rangle=0.4$), the alignment of
$({\bm{u}}_{1},{\bm{u}}_{2})$ with $({\bm{x}}_{1},{\bm{x}}_{2})$ is imperfect
in the region where $\beta_{1}\approx\beta_{2}$.

In this work, we characterize this behavior by estimating the alignments
$\langle{\bm{x}}_{i,k},{\bm{u}}_{j,k}\rangle$ in the asymmetric case, in the
high-dimensional regime when $n_{i}\to\infty$, using the random matrix
approach developed in [9]. Furthermore, as a by-product of this analysis, we
introduce a method to consistently estimate the underlying SNRs $\beta_{i}$
and the alignments $\langle{\bm{x}}_{i,k},{\bm{x}}_{j,k}\rangle$ and
$\langle{\bm{x}}_{i,k},{\bm{u}}_{j,k}\rangle$ from the quantities computed at
each step of the deflation procedure.

### Notations:

Scalars are denoted by lowercase letters. Vectors are denote by bold lowercase
letters. Tensors are denoted as ${\mathcal{A}},{\mathcal{B}},{\mathcal{C}}$.
$T_{i_{1}\ldots i_{d}}$ denotes the entry $(i_{1},\ldots,i_{d})$ of tensor
${\mathcal{T}}$. The inner product between two order-$d$ tensors
${\mathcal{A}}$ and ${\mathcal{B}}$ is denoted
$\langle{\mathcal{A}},{\mathcal{B}}\rangle=\sum_{i_{1},\ldots,i_{d}}A_{i_{1}\ldots
i_{d}}B_{i_{1}\ldots i_{d}}$. The $\ell_{2}$-norm of ${\mathcal{A}}$ is
$\|{\mathcal{A}}\|=\sqrt{\langle{\mathcal{A}},{\mathcal{A}}\rangle}$. For any
vectors ${\bm{u}}_{1},\dots,{\bm{u}}_{d}$, contractions of a tensor
${\mathcal{A}}$ are denoted by
${\mathcal{A}}({\bm{u}}_{1},\dots,{\bm{u}}_{d})=\sum A_{i_{1}\ldots
i_{d}}u_{1i_{1}}\dots u_{di_{d}}$. The notation
$\|{\mathcal{A}}\|_{op}=\operatorname{sup}_{\|{\bm{u}}_{i}\|=1}|{\mathcal{A}}({\bm{u}}_{1},\dots,{\bm{u}}_{d})|$
stands for the spectral norm. $[n]$ denotes the set $\\{1,\ldots,n\\}$.

##  2 MODEL AND MAIN RESULTS

We start by describing formally our considered model. Let $r\geq 1$ and $d\geq
3$, we consider the following rank-$r$ order-$d$ spiked tensor model

$\displaystyle{\mathcal{T}}_{1}=\sum_{i=1}^{r}\beta_{i}{\bm{x}}_{i,1}\otimes\cdots\otimes{\bm{x}}_{i,d}+\frac{1}{\sqrt{n}}\mathcal{{\mathcal{W}}}$
(1)

where $W_{i_{1}\ldots i_{d}}\sim{\mathcal{N}}(0,1)$ i.i.d.,
${\bm{x}}_{i,j}\in{\mathbb{R}}^{n_{j}}$ are unit vectors,
$n=\sum_{i=1}^{d}n_{i}$ and $\beta_{i}\geq 0$.

### Tensor deflation model:

In order to recover the underlying signal components (i.e. the terms
$\beta_{i}{\bm{x}}_{i,1}\otimes\cdots\otimes{\bm{x}}_{i,d}$), Hotelling
deflation consists in successive rank-one approximations followed by
subtraction of the rank-1 estimate. This can be implemented by computing
${\mathcal{T}}_{2},{\mathcal{T}}_{3},\dots$ sequentially through

$\displaystyle{\mathcal{T}}_{i+1}={\mathcal{T}}_{i}-\hat{\lambda}_{i}\hat{\bm{u}}_{i,1}\otimes\cdots\otimes\hat{\bm{u}}_{i,d}\quad\mathrm{for}\quad
i\in[r]$ (2)

where
$\hat{\lambda}_{i}\hat{\bm{u}}_{i,1}\otimes\cdots\otimes\hat{\bm{u}}_{i,d}$ is
a critical point of the loss
$\big{\|}{\mathcal{T}}_{i}-\lambda_{i}{\bm{u}}_{i,1}\otimes\cdots\otimes{\bm{u}}_{i,d}\big{\|}_{F}^{2}$
which corresponds to the rank-one approximation of ${\mathcal{T}}_{i}$ [12].
The critical points satisfy the Karush-Kuhn-Tucker conditions derived from the
Lagrangian of the latter objective, i.e.

$\displaystyle{\mathcal{T}}_{i}(\hat{\bm{u}}_{i,1},\ldots,\hat{\bm{u}}_{i,j-1},\cdot,\hat{\bm{u}}_{i,j+1},\ldots,\hat{\bm{u}}_{i,d})=\hat{\lambda}_{i}\hat{\bm{u}}_{i,j}$
(3)

with $\|{\bm{u}}_{i,j}\|=1$, for all $j\in[d]$. In the following, we aim at
computing the limits of $\hat{\lambda}_{i}$ and
$\langle{\bm{x}}_{i,k},\hat{\bm{u}}_{j,k}\rangle$ for $i,j\in[r]$ and
$k\in[d]$ when the dimensions $n_{i}$ grow large. For notational convenience,
in the sequel the notation $\lim Q$ stands for the limit of the quantity $Q$
when $n_{i}\to\infty$.

### Sketch of the analytical approach:

We follow the approach developed in [9], whereby each tensor
${\mathcal{T}}_{i}$ is associated to a structured random matrix
${\bm{\Phi}}_{d}({\mathcal{T}}_{i},\hat{\bm{u}}_{i,1},\ldots,\hat{\bm{u}}_{i,d})\in{\mathbb{R}}^{n\times
n}$ where the mapping ${\bm{\Phi}}_{d}$ is defined in [9, Section 5]. Then,
the characterization of the limits of $\hat{\lambda}_{i}$ and the alignments
$\langle{\bm{x}}_{i,k},\hat{\bm{u}}_{j,k}\rangle$ when $n_{i}\to\infty$ boils
down to the computation of the Stieltjes transform of the limiting spectral
measure of
${\bm{\Phi}}_{d}({\mathcal{T}}_{i},\hat{\bm{u}}_{i,1},\ldots,\hat{\bm{u}}_{i,d})$.
Hence, we need the following definition and technical assumptions.

######  Definition 2.1.

Let $\mu$ be the probability measure with Stieltjes transform
$g(z)=\sum_{i=1}^{d}g_{i}(z)$ verifying $\Im[g(z)]>0$ for $\Im[z]>0$, where
$g_{i}(z)$ satisfies $g_{i}^{2}(z)-(g(z)+z)g_{i}(z)-c_{i}=0$, for
$z\notin{\mathcal{S}}(\mu)$ and ${\mathcal{S}}(\mu)$ stands for the support of
$\mu$.

######  Assumption 2.2.

We assume that as $n_{i}\to\infty$, $r=O(1)$ and denote
$c_{i}=\lim\frac{n_{i}}{\sum_{j=1}^{d}n_{j}}$. We further assume that there
exists a sequence of critical points such that
$\hat{\lambda}_{i}\xrightarrow[]{\text{a.s.}}\lambda_{i}$,
$|\langle{\bm{x}}_{i,k},\hat{\bm{u}}_{j,k}\rangle|\xrightarrow[]{\text{a.s.}}\rho_{ijk}$
and
$|\langle\hat{\bm{u}}_{i,k},\hat{\bm{u}}_{j,k}\rangle|\xrightarrow[]{\text{a.s.}}\eta_{ijk}$
such that $\lambda_{i}\notin{\mathcal{S}}(\mu)$ and $\rho_{ijk}>0$.

We therefore have the following result111The proof of Theorem 2.3 follows
similar arguments as in [9] and requires some additional arguments for
controlling the statistical dependencies between the $\hat{\bm{u}}_{i,j}$’s
and the noise ${\mathcal{W}}$. which characterizes the limiting spectral
measure of
${\bm{\Phi}}_{d}({\mathcal{T}}_{i},\hat{\bm{u}}_{i,1},\ldots,\hat{\bm{u}}_{i,d})$.

######  Theorem 2.3.

Under Assumption 2.2, the empirical spectral measure of
${\bm{\Phi}}_{d}({\mathcal{T}}_{i},\hat{\bm{u}}_{i,1},\ldots,\hat{\bm{u}}_{i,d})$
converges to the deterministic measure $\mu$ defined in Definition 2.1.

As shown in [9], in the case $c_{i}=\frac{1}{d}$ for all $i\in[d]$, the
measure $\mu$ describes a semi-circle or Wigner-type law of compact support
${\mathcal{S}}(\mu)=[-2\sqrt{\frac{d-1}{d}},2\sqrt{\frac{d-1}{d}}]$, the
Stieltjes transform of which writes explicitly as

$\displaystyle g(z)=\frac{-zd+d\sqrt{z^{2}-\frac{4(d-1)}{d}}}{2(d-1)},\quad
z\notin{\mathcal{S}}(\mu)$ (4)

### Limiting spectral norms and alignments:

We introduce the quantities
$\alpha_{ijk}=\lim|\langle{\bm{x}}_{i,k},{\bm{x}}_{j,k}\rangle|,\,f(z)=z+g(z),\,h_{i}(z)=-\frac{c_{i}}{g_{i}(z)}$
that shall be used subsequently. The main result brought by this paper
describes the asymptotic singular values and alignments obtained after each
tensor deflation step as stated by the following theorem.

######  Theorem 2.4.

Assume that Assumption 2.2 holds. Then, $\lambda_{i}$, $\rho_{ijk}$ and
$\eta_{ijk}$ satisfy the following system of equations

$\displaystyle\begin{dcases}f(\lambda_{j})+\sum_{i=1}^{j-1}\lambda_{i}\prod_{k=1}^{d}\eta_{ijk}-\sum_{i=1}^{r}\beta_{i}\prod_{k=1}^{d}\rho_{ijk}=0\text{\
, $1\leq j\leq r$}\\\
h_{\ell}(\lambda_{j})\rho_{kj\ell}+\sum_{i=1}^{j-1}\lambda_{i}\rho_{ki\ell}\prod_{m\neq\ell}^{d}\eta_{ijm}-\sum_{i=1}^{r}\beta_{i}\alpha_{ik\ell}\prod_{m\neq\ell}^{d}\rho_{ijm}=0\\\
\text{ $1\leq\ell\leq d,1\leq j,k\leq r$}\\\
h_{\ell}(\lambda_{j})\eta_{kj\ell}+g_{\ell}(\lambda_{k})\prod_{m\neq\ell}^{d}\eta_{kjm}+\sum_{i=1}^{j-1}\lambda_{i}\eta_{ik\ell}\prod_{m\neq\ell}^{d}\eta_{ijm}+\ldots\\\
-\sum_{i=1}^{r}\beta_{i}\rho_{ik\ell}\prod_{m\neq\ell}^{d}\rho_{ijm}=0\text{,\
$1\leq\ell\leq d,1\leq j<k\leq r$}\\\ \end{dcases}$

###### Sketch of the proof.

We use similar arguments as in [9]. We first show that
$\mathrm{Var}[\hat{\lambda}_{j}]=O(n^{-1})$ and use a concentration argument
to show that $\hat{\lambda}_{j}$ concentrates around its expectation.
Simlarly, the same property holds for the alignments. Then, we evaluate the
expectation of the scalar product between (3) and ${\bm{x}}_{i}$ or
$\hat{\bm{u}}_{i}$ using Stein’s
Lemma222$\mathbb{E}[Wf(W)]=\mathbb{E}[f^{\prime}(W)]$ for
$W\sim\mathcal{N}(0,1)$.. ∎

Fig. 2: Phase diagram of the two spikes model in (5). First row corresponds to
$\beta_{2}=1$ and second row for $\beta_{2}=2$. The first column depicts
$\lambda_{1}$ varying $\beta_{1}$ and $\alpha$, while the remaining columns
depict the asymptotic alignments between the ${\bm{x}}_{i}$’s and
$\hat{\bm{u}}_{1}$. The figures were obtained by solving the first three
equations in (6). Fig. 3: Illustration of
$\langle{\bm{x}}_{i},\hat{\bm{u}}_{j}\rangle$ for $(i,j)\in\\{1,2\\}$,
$\langle\hat{\bm{u}}_{1},\hat{\bm{u}}_{2}\rangle$, $\hat{\lambda}_{1}$ and
$\hat{\lambda}_{2}$ vs. their limits for $\beta_{2}=10$ and
$\alpha=\langle{\bm{x}}_{1},{\bm{x}}_{2}\rangle=0.7$ of the two spikes tensor
model in (5). (a) shows the alignments between the signal components and the
first singular vectors corresponding to the best rank-one approximation of
${\mathcal{T}}_{1}$. (b) shows the alignments with the second singular vectors
computed after deflation. (c) depicts the singular values. (d) shows the
alignments between the singular vectors computed at each step of the deflation
procedure. Simulations were performed on a tensor of dimensions $(50,50,50)$.

Fig. 4: Estimation of the $\beta_{i}$’s by solving the system
$\psi(\hat{\bm{\lambda}},\cdot,\cdot)=\bm{0}$ given $\hat{\lambda}_{1}$,
$\hat{\lambda}_{2}$ and
$\hat{\eta}=\langle\hat{\bm{u}}_{1},\hat{\bm{u}}_{2}\rangle$ estimated from a
two steps deflation on a tensor distributed as in (5). First row corresponds
to $n_{i}=30$ and second row to $n_{i}=100$.

### Particular case of a rank-2, order-3 tensor:

For the sake of clarity, let us consider the example of a rank-$2$ order-$3$
spiked tensor with $n_{1}=n_{2}=n_{3}$, thus

$\displaystyle{\mathcal{T}}_{1}=\sum_{i=1}^{2}\beta_{i}{\bm{x}}_{i,1}\otimes{\bm{x}}_{i,2}\otimes{\bm{x}}_{i,3}+\frac{1}{\sqrt{n}}{\mathcal{W}}$
(5)

Furthermore, we assume that for all $i\neq j$ and each $k\in[3]$,
$\lim|\langle{\bm{x}}_{i,k},{\bm{x}}_{j,k}\rangle|=\alpha\in[0,1]$. In this
case, since all the dimensions $n_{i}$ are equal, the limits of
$|\langle{\bm{x}}_{i,k},\hat{\bm{u}}_{j,k}\rangle|$ and of
$|\langle\hat{\bm{u}}_{1,k},\hat{\bm{u}}_{2,k}\rangle|$ are both independent
from $k$ by symmetry. Therefore, we drop their dependence on $k$ in our
notations. Hence, the system of equations in Theorem 2.4 reduces to seven
equations, detailed in the following corollary.

######  Corollary 2.5.

Denote $\rho_{ij}=\lim|\langle{\bm{x}}_{i,k},\hat{\bm{u}}_{j,k}\rangle|$ for
$i,j\in[2]$ and
$\eta=\lim|\langle\hat{\bm{u}}_{1,k},\hat{\bm{u}}_{2,k}\rangle|$ and suppose
that Assumption 2.2 holds, then $\lambda_{i}$, $\rho_{ij}$ and $\eta$ satisfy
$\psi({\bm{\lambda}},{\bm{\beta}},{\bm{\rho}})=\bm{0}$ with
${\bm{\lambda}}=(\lambda_{1},\lambda_{2},\eta)$,
${\bm{\rho}}=(\rho_{11},\rho_{12},\rho_{21},\rho_{22})$,
${\bm{\beta}}=(\beta_{1},\beta_{2},\alpha)$ and

$\psi({\bm{\lambda}},{\bm{\beta}},{\bm{\rho}})=\left(\begin{array}[]{c}f(\lambda_{1})-\beta_{1}\rho_{11}^{3}-\beta_{2}\rho_{21}^{3}\\\
h(\lambda_{1})\rho_{11}-\beta_{1}\rho_{11}^{2}-\beta_{2}\alpha\rho_{21}^{2}\\\
h(\lambda_{1})\rho_{21}-\beta_{1}\alpha\rho_{11}^{2}-\beta_{2}\rho_{21}^{2}\\\
f(\lambda_{2})+\lambda_{1}\eta^{3}-\beta_{1}\rho_{12}^{3}-\beta_{2}\rho_{22}^{3}\\\
h(\lambda_{2})\rho_{12}+\lambda_{1}\rho_{11}\eta^{2}-\beta_{1}\rho_{12}^{2}-\beta_{2}\alpha\rho_{22}^{2}\\\
h(\lambda_{2})\rho_{22}+\lambda_{1}\rho_{21}\eta^{2}-\beta_{1}\alpha\rho_{12}^{2}-\beta_{2}\rho_{22}^{2}\\\
h(\lambda_{2})\eta+q(\lambda_{1})\eta^{2}-\beta_{1}\rho_{11}\rho_{12}^{2}-\beta_{2}\rho_{21}\rho_{22}^{2}\end{array}\right)$
(6)

where $h(z)=\frac{-1}{g(z)}$ and $q(z)=z+\frac{g(z)}{3}$ with $g(z)$ given by
(4) for $d=3$ and we recall that $f(z)=z+g(z)$.

Fixing ${\bm{\beta}}=(\beta_{1},\beta_{2},\alpha)$, one can solve
$\psi({\bm{\lambda}},{\bm{\beta}},{\bm{\rho}})=\bm{0}$ in
$({\bm{\lambda}},{\bm{\rho}})$ while ensuring that $0\leq\eta,\rho_{ij}\leq 1$
and $\lambda_{1},\lambda_{2}>2\sqrt{\frac{2}{3}}$. This provides a fixed point
equation satisfied by the asymptotic limits of the spectral norms
$\hat{\lambda}_{i}$ and the alignments
$\langle{\bm{x}}_{i,k},\hat{\bm{u}}_{j,k}\rangle$ and
$\langle\hat{\bm{u}}_{1,k},\hat{\bm{u}}_{2,k}\rangle$.

Note that the first three equations in (6) only involve $\lambda_{1}$,
$\rho_{11}$ and $\rho_{21}$ and are decoupled from the last four equations.
Therefore, solving them allows to obtain the phase diagram related to the
dominant singular mode $(\hat{\lambda}_{1},\hat{\bm{u}}_{1})$, depicted in
Figure 2. It shows that when $\beta_{2}$ is not large enough (e.g.
$\beta_{2}=1$, top row), there exists a region (varying $\beta_{1}$ and
$\alpha$) where it is information-theoretically impossible to detect a signal,
while outside this region estimation becomes possible with the MLE (in that
case, the estimated $\hat{\bm{u}}_{1}$ is shown to be correlated with both
${\bm{x}}_{1}$ and ${\bm{x}}_{2}$). For $\beta_{2}$ sufficiently large (e.g.
$\beta_{2}=2$, bottom row of Figure 2), signal detection is always possible
and the singular vector $\hat{\bm{u}}_{1}$ presents a higher alignment with
the signal components having the highest SNR $\beta_{i}$ (see the two columns
on the right).

Moreover, we illustrate in Figure 3 the matching between
$\hat{\bm{\lambda}}=(\hat{\lambda}_{1},\hat{\lambda}_{2},\hat{\eta})$,
$\hat{\bm{\rho}}=(\hat{\rho}_{11},\hat{\rho}_{12},\hat{\rho}_{21},\hat{\rho}_{22})$
(where the rank-one approximations are performed using tensor power iteration
initialized by tensor SVD [13]) and their asymptotic limits
${\bm{\lambda}},{\bm{\rho}}$. Note that, for some $\beta_{1}$, the equation
$\psi(\cdot,{\bm{\beta}},\cdot)=\bm{0}$ has two distinct solutions. These two
solutions correspond to two different sequences of critical points. However,
in practice, the chosen initialization favor one sequence of critical points
as can be seen in Figure 3.

##  3 Consistent SNR estimation

Having set the relationship between the $\beta_{i}$’s and the limits of the
different spectral norms and alignments in our problem, one can exploit this
mapping to design a consistent estimator of the underlying SNRs $\beta_{i}$’s.
Indeed, $\hat{\bm{\lambda}}$ can directly be estimated from $\hat{\bm{u}}_{i}$
obtained with the deflation.

Then we denote $\hat{\bm{\beta}}$ and $\hat{\bm{\rho}}$ the estimates of
${\bm{\beta}}$ and ${\bm{\rho}}$ as the vectors satisfying
$\psi(\hat{\bm{\lambda}},\hat{\bm{\beta}},\hat{\bm{\rho}})=\bm{0}$ with $\psi$
defined in (6). The additional condtions required for the existence and the
uniqueness of such solution is not studied in the present paper and shall be
considered in an extended version. In our simulations, we find one solution
for $\psi(\hat{\bm{\lambda}},\cdot,\cdot)=\bm{0}$ if
$\hat{\lambda}_{1},\hat{\lambda}_{2}>2\sqrt{2/3}$. We illustrate the result of
such estimation in Figure 4 where we see that
$(\hat{\beta}_{1},\hat{\beta}_{2})$ consistently estimate
$(\max(\beta_{1},\beta_{2}),\min(\beta_{1},\beta_{2}))$, while the naive
estimator
$(\hat{\beta}_{1},\hat{\beta}_{2})=(\hat{\lambda}_{1},\hat{\lambda}_{2})$
exhibits a large error in the non-orthogonal case ($\alpha=0.5$, second
column). Moreover, as the dimensions of the tensor increase, Fig. 4 shows
(comparing first and second row) that the estimation is consistent. This
consistency can be related to a classical concentration phenomenon [14].

##  4 Conclusion

We have provided an analysis of a tensor deflation method in the high-
dimensional regime and assuming a low-rank spiked tensor model with correlated
signal components. Our analysis allows precise description of the asymptotic
behavior of such models and provides consistent estimation of its parameters
as shown in the last part of the paper. This paves a new way for analysis of
more sophisticated tensor decomposition methods and the understanding of more
general tensor models through random tensor theory.

## References

  * [1] Emile Richard and Andrea Montanari,  “A statistical model for tensor PCA,”  Advances in neural information processing systems, vol. 27, 2014\.
  * [2] Amelia Perry, Alexander S Wein, and Afonso S Bandeira,  “Statistical limits of spiked tensor models,”  in Annales de l’Institut Henri Poincaré, Probabilités et Statistiques. Institut Henri Poincaré, 2020, vol. 56, pp. 230–264.
  * [3] Thibault Lesieur, Léo Miolane, Marc Lelarge, Florent Krzakala, and Lenka Zdeborová,  “Statistical and computational phase transitions in spiked tensor estimation,”  in 2017 IEEE International Symposium on Information Theory (ISIT). IEEE, 2017, pp. 511–515.
  * [4] Aukosh Jagannath, Patrick Lopatto, and Leo Miolane,  “Statistical thresholds for tensor PCA,”  The Annals of Applied Probability, vol. 30, no. 4, pp. 1910–1933, 2020.
  * [5] Wei-Kuo Chen, Madeline Handschy, and Gilad Lerman,  “Phase transition in random tensors with multiple independent spikes,”  The Annals of Applied Probability, vol. 31, no. 4, pp. 1868–1913, 2021.
  * [6] José Henrique de Morais Goulart, Romain Couillet, and Pierre Comon,  “A random matrix perspective on random tensors,”  arXiv preprint arXiv:2108.00774, 2021.
  * [7] Christopher J Hillar and Lek-Heng Lim,  “Most tensor problems are NP-hard,”  Journal of the ACM (JACM), vol. 60, no. 6, pp. 1–39, 2013.
  * [8] Gérard Ben Arous, Daniel Zhengyu Huang, and Jiaoyang Huang,  “Long random matrices and tensor unfolding,”  arXiv preprint arXiv:2110.10210, 2021.
  * [9] Mohamed El Amine Seddik, Maxime Guillaud, and Romain Couillet,  “When random tensors meet random matrices,”  arXiv preprint arXiv:2112.12348, 2021.
  * [10] Harold Hotelling,  “Analysis of a complex of statistical variables into principal components,”  Journal of Educational Psychology, vol. 24, no. 6, pp. 417–441, Sept. 1933.
  * [11] Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J R Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, et al.,  “Discovering faster matrix multiplication algorithms with reinforcement learning,”  Nature, vol. 610, no. 7930, pp. 47–53, 2022.
  * [12] Lek-Heng Lim,  “Singular values and eigenvalues of tensors: a variational approach,”  in Proc. IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), 2005, pp. 129–132.
  * [13] Arnab Auddy and Ming Yuan,  “On estimating rank-one spiked tensors in the presence of heavy tailed errors,”  IEEE Transactions on Information Theory, 2022.
  * [14] Florent Benaych-Georges, Alice Guionnet, and Mylène Maida,  “Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices,”  Electronic Journal of Probability, vol. 16, pp. 1621–1662, 2011\.