Parsers

Discover CoBaLD parsers based on neural network that allows one to annotate tokenized text (*.conllu file) in CoBaLD format

Currently, we suggest two parsers for CoBaLD annotation: the base one – for the annotation according to the Base UD rules, and the enhanced one – for the annotation according to the Enhanced UD rules. The base parser predicts morphology, basic syntax and semantics. The enhanced parser additionally retrieves elided tokens and builds enhanced syntactic graph.

The parser is multi-task tagger. It is based on Anastasyev’s Joint Morpho-Syntactic Parser (a GramEval-2020 winner) and consists of Masked Language Model encoder paired with heads. The former transforms sentence tokens into contextual embeddings, while the latter sample tags upon these embeddings.
The base parser includes five heads: lemmatizer, joint part-of-speech and grammatical features classifier, syntax analyzer and two semantic classifiers.

Lemmatization classifier predicts lemmatization rules. Lemmatization rule is a sequence of three modifications that have to be applied to a word to obtain its lemma:

1. Cut N symbols from the prefix of the word,
2. Cut N symbols from the suffix,
3. Append a specific sequence of symbols to the suffix.

In order to transform elves into elf one need to leave the prefix intact, remove three symbols from the suffix, and add a new suffix ves. So, the lemmatization rule in this case looks like cut_prefix=0|cut_suffix=3|append_suffix=ves.

This rule-based approach reduces a seemingly generative task of lemmatization to a straightforward classification with a simpler optimization objective.

Part-of-speech and grammatical features can be predicted as two independent tags, but this naive strategy leaves room for compatibility errors. For example, a separate POS head may tag a token as a noun, whilst a standalone Feats classifier may predict a present tense for the token, which is incorrect tagging, because nouns don’t have time category.

To avoid such behavior, we use a single POS-&-Feats classifier that predicts joint part-of-speech and grammatical features tags. Note, that since POS and grammatical features are heavily correlated, the number of joint classes is much smaller than the Cartesian product of two tags, so the classification approach remains feasible.

Syntax analyzer is a biaffine dependency classifier that establishes basic syntactic connections between tokens in a sentence.

The classifier scores directed arcs between pairs of tokens using the bilinear transformation, and then applies a softmax to a scoring matrix S(arc) to model a probability distribution P over the arcs of each token:

P=softmax(S(arc)).

To build the arcs A of a dependency tree, we either greedily choose the most probable arc for each token while training:

Atrain=argmax(P),

…or use Chu-Liu-Edmonds algorithm to find a spanning arborescence of a maximum probability at the inference:

Atest=ChuLiuEdmonds(P).

Finally, we select the relations L towards the predicted arcs:

L=argmax(S(rel)[I(A)]),

where S(rel) is a tensor of relations scores and I(A) is indices of arcs.

The semantic classifiers simply predict deep slots and semantic classes.

All the heads (except for biaffine one) are multilayer perceptrons with ReLU activation.

Enhanced parser extends the base version in two ways. First, it additionally builds an enhanced syntactic graph of a sentence using enhanced syntax analyzer. Second, it predicts elided tokens (nulls).

In contrast to basic syntax, the enhanced dependency graph is not restricted to a DAG and can represent an arbitrary graph. To account for this, we use dependency graph parser that has proven effective in both the IWPT-2020 and IWPT-2021 tasks on Enhanced UD parsing.

The graph parser utilizes the same bilinear transformation the tree parser does, but models each arc probability independently using a multi-label approach with a binary cross-entropy loss (sigmoid) instead of multi-class cross-entropy loss (softmax) and selects all the confident arcs:

P=sigmoid(S(arc)),

A=[P>0.5].

This distributional relaxation allows the enhanced analyzer to predict multiple edges per token, accounting for the non-acyclic nature of enhanced syntactic graphs.

Training sentence contains null tokens, while the test one has nulls removed. The objective is to restore the original nulls given a test sentence.

Training sentence: [Quick, brown, #NULL, #NULL, fox, #NULL] Test sentence: [Quick, brown, fox]

We introduce a concept of counting mask that shows how many nulls follow a non-null token in the training sentence. The mask has a length of a test sentence, and value N at the position i means that the i-th non-null token is followed by N consecutive nulls.

The counting mask for the example above looks like [0, 2, 1], because there is no null after Quick, two nulls after brown and one null after fox.

Note, that the counting mask ignores the leading nulls, e.g. [#NULL, On, that, date], as there is no token to follow. To account for this issue, we prepend an auxiliary token to the beginning of a test sentence prior to mask construction.

Given the counting mask, ellipsis restoration becomes as simple as sequence labeling — we just add another head called null classifier that predicts the number of nulls to be inserted after a token. The pipeline gets split into two stages: first, the null classifier retrieves the elided tokens and adds them to an input sentence, then the refined sentence is parsed as usual:

During the training, sentences with and without nulls are passed through the encoder independently, so the tagging heads are always trained upon the well-formed sentences, and not the restored ones:

It is similar to a teacher forcing approach used in sequence generation, where a ground truth token is fed to a model instead of the previously predicted word to avoid error accumulation and speed up the training.

We jointly optimize the null classifier with the tagging heads by adding up the losses. The encoder aggregates the gradients from all classifiers and updates the weights once per training step.