# Simply Trainable Nearest Neighbour Machine Translation with GPU Inference

Hossam Amer*<EMAIL_ADDRESS>Abdelrahman Abouelenin*
<EMAIL_ADDRESS>Mohamed Maher<EMAIL_ADDRESS>Evram Nairouz
<EMAIL_ADDRESS>Mohamed Afify<EMAIL_ADDRESS>Hany Awadallah
<EMAIL_ADDRESS>
###### Abstract

Nearest neighbor machine translation is a successful approach for fast domain
adaption, which interpolates the pre-trained transformers with domain-specific
token-level k-nearest-neighbor (kNN) retrieval without retraining. Despite kNN
MT’s success, searching large reference corpus and fixed interpolation between
the kNN and pre-trained model led to computational complexity and translation
quality challenges. Among other papers, Dai et al., (2023) proposed methods to
obtain a small number of reference samples dynamically for which they
introduced a distance-aware interpolation method using an equation that
includes free parameters. This paper proposes a simply trainable nearest
neighbor machine translation and carry out inference experiments on GPU.
Similar to Dai et al., (2023), we first adaptively construct a small datastore
for each input sentence. Second, we train a single-layer network for the
interpolation coefficient between the knnMT and pre-trained result to
automatically interpolate in different domains. Experimental results on
different domains show that our proposed method either improves or sometimes
maintain the translation quality of methods in Dai et al., (2023) while being
automatic. In addition, our GPU inference results demonstrate that knnMT can
be integrated into GPUs with a drop of only 5% in terms of speed.

##  1 Introduction

Neural Machine Translation (NMT) has been showing an increasing trend of
translation quality owing to the ongoing development of deep neural network
models Vaswani et al., (2017); Kim et al., (2021). However, the quality of
these models is limited as soon as the domain of the input test sentences is
different than the training data. ††* equal contribution To handle this out-
of-domain problem, k-nearest neighbor machine translation (kNN-MT) has proven
to be successful in many studies Khandelwal et al., (2021); Zheng et al., 021a
; Zheng et al., 021b ; Jiang et al., (2021); Wang et al., (2022); Meng et al.,
(2022), and thus piqued much attention in the community of machine
translation. At the core of kNN-MT, a kNN classifier over an external
datastore is built based on cached decoder representations and corresponding
target tokens. This classifier is utilized to augment the given NMT model
without finetuning leading to improved predictions, especially for domain
adaption. Augmenting the NMT model is done via interpolating between the
output probability distribution of the NMT model and the kNN classifier output
probability distribution.

Despite kNN-MT’s noticeable success in alleviating the domain adaption
problem, vanilla kNN-MT proposed in Khandelwal et al., (2021) mainly suffers
two challenges slowing down kNN-MT’s deployment. First, vanilla kNN-MT
requires large datastore sizes resulting in massive storage and expensive
latency overheads during inference. For example, Khandelwal et al., (2021)
showed that kNN-MT is two orders of magnitude slower than the base NMT system
in a generation speed when retrieving 64 keys from a datastore containing
billions of records. Second, the interpolation between the NMT model and the
kNN classifier is fixed for all sentences in the test sets and manually tuned
to improve translation quality.

Techniques in the literature have been proposed to overcome kNN-MT’s
challenges. For example, Meng et al., (2022) designed Fast kNN-MT where a
subset of the large datastore is created for each source sentence by searching
for the nearest token-level neighbors of the source tokens and mapping them to
the corresponding target tokens. Building on Meng et al., (2022), Dai et al.,
(2023) proposed a simple and scalable kNN-MT that leverages current efficient
text retrieval mechanisms, such as BM25 Robertson et al., (2009), to obtain a
small number of reference samples that have high semantic similarities with
the input sentence, and then dynamically construct a tiny datastore by
forwarding the samples to the pre-trained model. Dai et al., (2023)
successfully introduced a simple distance-aware interpolation equation to
adaptively incorporate kNN retrieval results into the NMT model. However, this
simple equation required manual tuning. Along the same line, Jiang et al.,
(2022) proposed a trainable interpolation method but with six-layer neural
network. To the best of our knowledge, these papers did not integrate kNN-MT
into GPU inference to observe the trade-off between accuracy and speed
results.

This paper proposes a simply trainable nearest neighbor machine translation
via a single-layer neural network and demonstrates kNN feasibility with GPU
inference. Similar to Dai et al., (2023), we reduce the large datastore size
by extracting online a small number of reference samples that have high
semantic similarities with the input test sentence using the efficient BM25
retrieval algorithm (Robertson et al., (2009)). Based on these insights, we
propose a simply trainable single-layer neural network that adaptively
interpolates the NMT and knnMT probability distributions per domain in an
average of 40 minutes of a single GPU training time. Last but not least, we
integrate kNN-MT into FasterTransformer, a highly optimized NMT GPU inference
implementation offered by NVIDIA, and observe its speed and accuracy
performance on a sparsely activated large-scale MoE. Experimental results show
the translation quality effectiveness of our adaptive and automatic
interpolation technique and insignificant speed drop of knnMT on GPU.
Contributions of this paper are listed below:

  * •

Propose and develop an adaptive and trainable single-layer neural network for
knnMT interpolation that trains in 40 minutes. (Section 3).

  * •

Experimental results show that the proposed method improves the results of Sk-
MT in some domains while maintaining the result in some other domains (Section
4.2).

  * •

Integrate knnMT interpolation with GPU inference and introduce the speed-to-
accuracy trade-off results. (Section 4.3).

This remainder of this paper is organized as follows: Section 2 introduces
knnMT and summarizes Sk-MT paving the road to the proposed method in Section
3. Section 3 provides the experimental results while finally concluding in
Section 5.

##  2 Background: kNN-MT

###  2.1 Vanilla-kNN

In vanilla-kNN, a datastore is created to convert a bilingual sentence into a
set of key-value pairs. These keys and values are defined in Equation 1.

$K,V=F(x,y_{<t}),y_{t}$ (1)

where (x, y) $\in$ (X, Y) define the reference corpus for which the pretrained
NMT model generates the context representation $F(x,y_{<t}$ at each time step
$t$. Then we collect the output hidden state $F(x,y_{<t})$ as key and $y_{t}$
as value to construct the whole datastore $(K,V)$.

At inference time, the current context representation $F(x,\hat{y}_{<t})$ at
decoding step $t$, as well as the already generated words, are leveraged to
generate a retrieval distribution $P_{knn}(y_{t}|y_{<t},x)$ over the entire
vocabulary:

$P_{knn}(y_{t}|x,\hat{y}_{<t})\\\ \propto\sum_{(h_{i},v_{i})\in
N_{t}}I_{y_{t}=v_{i}}exp(\frac{-L_{2}(hi,F(x,\hat{y}_{<t}))}{T})$ (2)

where L2 is the Euclidean distance between the current context embedding and
the embedding of a token from the data store. In vanilla KNN-MT, a predefined
interpolation weight $\lambda$ is fixed as a hyperparameter. This weight
interpolates between the probability distribution computed from KNN and the
probability distribution generated from the pretrained NMT model (see Equation
3).

$P(y_{t}|x,\hat{y}_{<t})=\lambda*P_{mt}(y_{t}|x,\hat{y}_{<t})\\\
+(1-\lambda)*P_{knn}(y_{t}|x,\hat{y}_{<t})$ (3)

###  2.2 SK-MT

In SK-MT Dai et al., (2023), Elasticsearch is used for semantic retrieval
components to create a sentence adaptive datastore instead of a static and
extensive datastore used in Vanilla kNN-MT. In specific, Elasticsearch does
two main operations: Index & Search; storing parallel sentences in indexes
format, and then retrieving 32 sentences per input sentence with the highest
relevance score from the training corpus.

Also, SK-MT provided a successful way of setting the interpolation coefficient
in Equation 4.

$\lambda=Relu(1-\frac{d_{0}}{T})$ (4)

where $d_{0}$ is the top-1 L2 distance during the nearest neighbor search, $T$
is the temperature parameter and is typically fixed.

##  3 Single-Layer Trainable Interpolation

Even though SK-MT introduced a simple solution that derives the interpolation
weight from the distance, a fixed parameter $T$ for all datasets is tuned to
produce the best results and $T=100$ is recommended. A fixed temperature may
not be optimal for all domains and datasets. For example, Table 1 shows the
BLEU score from the Koran dataset when varying $T$ from 100 to 500 with a step
size of 100. As seen in the table, $T=300$ increases the BLEU score providing
evidence that the temperature value can vary with the dataset and does not
have to be the recommended SK-MT $T=100$. This observation motivates a simple
and trainable method to adaptively find the temperature parameter for each
dataset.

Temperature (T) | BLEU
---|---
100 | 15.5
200 | 15.9
300 | 16.1
400 | 15.9
500 | 15.5
Table 1: Koran Temperature Variation

The proposed simple neural network consists of a single layer trained to
predict the interpolation weight given the distance of the retrieved kNN
candidates. This is in contrast to other adaptive interpolation methods e.g.
Jiang et al., (2022) that use more layers and learnable parameters. We use the
development set of each domain to optimize our single-layer network.

Our training objective is designed to provide better translation quality.
Knowing the ground truth token, we can choose the best interpolation weight
that produces the best probability distribution that we can get from the
interpolation between $P_{mt}$ and $P_{knn}$. Thus, our final objective is to
create a sharper final probability distribution toward our ground truth token.

1 $len\leftarrow length(y)$;

2 $t\leftarrow 0$;

3 while  _$t\neq len$_ do

4 $gt\leftarrow$ ground truth Index;

5 generate $Pknn(y_{<t},x)$;

6 generate $Pmt(y_{<t},x)$;

7 if  _$Pknn(gt|y_{ <t},x)\geq Pmt(gt|y_{<t},x)$_ then

8 $label=1$;

// favoring Pknn

9

10 else

11 $label=0$;

12

13 $\lambda_{pred}=Sigmoid(W\cdot D_{0}+B)$;

14 $loss\leftarrow CrossEntropy(\lambda_{pred},label)$;

15 update $W,B$;

16 $t=t+1$;

17

Algorithm 1 Training Interpolation Layer

As shown in Algorithm 1, our training procedure is divided into two stages at
each decoding step. The first stage examines the probability of the ground
truth token in both distributions $P_{knn}$ and $P_{mt}$. If the probability
of the ground truth token $P_{knn}$ is higher then we set the label to 1
otherwise we set the label to 0. The second stage trains our single-layer
network using binary loss.

Table 2: Translation quality of the proposed method versus other methods at Beam=5 and K=2. Domain |  BLEU |  WMT22-COMET-da
---|---|---
|  NMT |  SK-MT |  Trainable |  NMT |  SK-MT |  Trainable
IT |  38 | 45.5  |  46.1 | 83.0  |  85.0 |  85.0
Law |  49.6 | 62.8  |  62.7 | 86.7  |  88.3 |  88.0
Koran |  12.2 | 15.5  |  16.4 | 69.1  |  70.0 |  70.6
e-commerce |  52.5 | 58.1  |  58.5 | 90.7  |  90.9 |  90.9
finance |  48.6 | 53.3  |  53.3 | 70.6  |  94.2 |  93.9
Medical |  42.7 | 57.1  |  57.2 | 83.9  |  85.2 |  85.0
medpharma |  41.6 | 47.4  |  48.1 | 92.2  |  92.0 |  92.5
AVERAGE |  40.8 | 48.5  |  48.9 | 82.4  |  86.5 |  86.6
Table 3: GPU Inference Results on ZCode M3 Model. |  beam=1, batch=1 |  beam=2, batch=20
---|---|---
Domain |  BLEU |  Speed Drop (%) |  BLEU |  Speed Drop (%)
| NMT  |  knn-MT |  | NMT  |  knn-MT |
IT | 37.6  |  43.8 | 4.9  | 37.4  |  43.7 | 6.5
Medical | 45.6  |  55.6 | 5.0  | 45.8  |  56.3 | 9.1
Law | 54.1  |  61.8 | 5.8  | 54.1  |  62.2 | 5.5
AVERAGE |  45.7 |  53.7 |  5.2 |  45.7 |  54.0 |  7.0

##  4 Experimental Results

###  4.1 Experimental Setup

Input stimuli and Datasets: We test our methodology in 2 language directions:
German-English (deen), and English-Czech (encs). For deen, we employ the
multi-domain dataset as the baseline Khandelwal et al., (2021) in addition to
an e-commerce domain. For encs, we utilize two other domains: finance and
medpharma. Our evaluation metrics are the SacreBLEU Post, (2018) and COMET-22
(wmt22-COMET-da) Rei et al., (2022), a reference-based metric that combines
direct assessments (DA), sentence-level scores, and word-level tags from
Multidimensional Quality Metrics (MQM) error annotations.

Models: Three transformer models are used in our experiments. The first two of
the three are used to measure the translation quality; these two are
constructed from 12 encoder layers and 12 decoder layers with 512 hidden
dimensions and 2048 feedforward layer hidden dimensions with 8 multi-head
attention heads. The third transformer is the ZCode M3 model reviewed and
presented in Kim et al., (2021). ZCode M3 is constructed from 24 encoder
layers and 12 decoder layers with 1024 hidden dimensions and 4096 feedforward
layer hidden dimensions with 16 multi-head attention heads. The ZCode M3 has
32 experts, 5B parameters, and 128,000 vocab size.

Baselines: The model without knnMT is one baseline. To compare to other
methods on our inhouse transformers, we utilize the SK-MT method that uses a
distance-aware adapter Dai et al., (2023). In Dai et al., (2023), the authors
compared with other methods and showed success so we use Dai et al., (2023) as
a transitive proxy to compare with other methods.

GPU Inference Hardware and Environment: Inference and speed evaluation
experiments are carried out on a single NVIDIA Tesla V100 GPU. Our inference
environment is the highly optimized FasterTransformer from NVIDIA. Without
loss of generality, we fix interpolation to
$\lambda=Relu(1-\frac{d_{0}}{100})$ and measure the speed.

###  4.2 Trainable kNN Retrieval Results

Table 2 shows the translation quality performance comparison between the
proposed trainable method and other baselines. As shown in the table, our
proposed trainable method improves the NMT baseline translation quality by a
large margin. In addition, the proposed method improves or sometimes maintains
the overall translation quality relative to SK-MT on average in terms of the
BLEU and COMET scores. In some domains like IT and Koran, the proposed method
improves the SK-MT performance. This result demonstrates the ability to at
least maintain the performance of SK-MT while using a single-layer neural
network. Also, these results overall show the adaptability of the proposed
method to different datasets. For Medical and medpharma, SK-MT outperforms our
proposed method because the datastore built by the dev set does not have any
semantic similarity to the training set leading to imbalanced binary labeling,
whereas the test does not have this imbalanced binary labeling. To overcome
this challenge, we suggest that we add weights to the binary cross-entropy
training loss function. With this weighted loss function, our trainable method
achieves 57.2 BLEU, 85 COMET in Medical, and 48.1 BLEU, 92.5 COMET in
medphrama. These results increase our average results to 48.9 BLEU, and 86.6
COMET, respectively.

Turning to the translation quality in terms of COMET, we observe that SK-MT
still either maintain or improve the quality in the majority of the domains.
We also notice that the improvements in BLEU scores do not fully transfer to
COMET. We believe that this is due to the fact that COMET is trained on
general domain data, therefore it’s less sensitive to domain terminology and
more focused on coherence and fluency. For example, e-commerce has an
improvement of roughly 6 BLEU points relative to NMT, while the improvement is
0.3 COMET score points.

###  4.3 GPU Inference Results

Table 3 depicts the speed results of ZCode M3 inference and corresponding BLEU
scores in three domains under test namely, IT, Medical, and Law. The kNN-MT
results for beam=1, batch=1 setting on the large scale MoE improves the NMT
baseline with a large margin while dropping the speed by only 5.2% on average.
Similarly, kNN-MT has an improved translation quality with only a drop of 7%
relative to NMT as beam and batch increase to 2 and 20, respectively. These
results show the potential of deploying the knnMT domain adaption approach in
such a large-scale model as ZCode M3.

##  5 Conclusion

This paper proposes a simply single-layer trainable nearest-neighbor machine
translation and carries out experiments on large-scale models to demonstrate
kNN feasibility with GPU Inference. Experimental results show the translation
quality effectiveness of our adaptive and automatic interpolation technique
relative to other methods in literature, the training simplicity in 40 mins on
single-GPU, and insignificant speed drop of knnMT on GPU inference.

## References

  * Dai et al., (2023) Dai, Y., Zhang, Z., Liu, Q., Cui, Q., Li, W., Du, Y., and Xu, T. (2023).  Simple and scalable nearest neighbor machine translation.  In The Eleventh International Conference on Learning Representations (ICLR).
  * Jiang et al., (2022) Jiang, H., Lu, Z., Meng, F., Zhou, C., Zhou, J., Huang, D., and Su, J. (2022).  Towards robust k-nearest-neighbor machine translation.  In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 5468–5477, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Jiang et al., (2021) Jiang, Q., Wang, M., Cao, J., Cheng, S., Huang, S., and Li, L. (2021).  Learning kernel-smoothed machine translation with retrieved examples.  In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 7280–7290, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Khandelwal et al., (2021) Khandelwal, U., Fan, A., Jurafsky, D., Zettlemoyer, L., and Lewis, M. (2021).  Nearest neighbor machine translation.  In International Conference on Learning Representations (ICLR).
  * Kim et al., (2021) Kim, Y. J., Awan, A. A., Muzio, A., Salinas, A. F. C., Lu, L., Hendy, A., Rajbhandari, S., He, Y., and Awadalla, H. H. (2021).  Scalable and efficient moe training for multitask multilingual models.  arXiv preprint arXiv:2109.10465.
  * Meng et al., (2022) Meng, Y., Li, X., Zheng, X., Wu, F., Sun, X., Zhang, T., and Li, J. (2022).  Fast nearest neighbor machine translation.  In Findings of the Association for Computational Linguistics: ACL 2022, pages 555–565, Dublin, Ireland. Association for Computational Linguistics.
  * Post, (2018) Post, M. (2018).  A call for clarity in reporting BLEU scores.  In Bojar, O., Chatterjee, R., Federmann, C., Fishel, M., Graham, Y., Haddow, B., Huck, M., Yepes, A. J., Koehn, P., Monz, C., Negri, M., Névéol, A., Neves, M., Post, M., Specia, L., Turchi, M., and Verspoor, K., editors, Proceedings of the Third Conference on Machine Translation: Research Papers, pages 186–191, Brussels, Belgium. Association for Computational Linguistics.
  * Rei et al., (2022) Rei, R., De Souza, J. G., Alves, D., Zerva, C., Farinha, A. C., Glushkova, T., Lavie, A., Coheur, L., and Martins, A. F. (2022).  Comet-22: Unbabel-ist 2022 submission for the metrics shared task.  In Proceedings of the Seventh Conference on Machine Translation (WMT), pages 578–585.
  * Robertson et al., (2009) Robertson, S., Zaragoza, H., et al. (2009).  The probabilistic relevance framework: Bm25 and beyond.  Foundations and Trends® in Information Retrieval, 3(4):333–389.
  * Vaswani et al., (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. (2017).  Attention is all you need.
  * Wang et al., (2022) Wang, D., Fan, K., Chen, B., and Xiong, D. (2022).  Efficient cluster-based $k$-nearest-neighbor machine translation.  In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2175–2187, Dublin, Ireland. Association for Computational Linguistics.
  * (12) Zheng, X., Zhang, Z., Guo, J., Huang, S., Chen, B., Luo, W., and Chen, J. (2021a).  Adaptive nearest neighbor machine translation.  In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers), pages 368–374, Online. Association for Computational Linguistics.
  * (13) Zheng, X., Zhang, Z., Huang, S., Chen, B., Xie, J., Luo, W., and Chen, J. (2021b).  Non-parametric unsupervised domain adaptation for neural machine translation.  In Findings of the Association for Computational Linguistics: EMNLP 2021, pages 4234–4241, Punta Cana, Dominican Republic. Association for Computational Linguistics.


# Graphene: A Context-Preserving Open Information Extraction System

Matthias Cetto1, Christina Niklaus1, André Freitas2 Siegfried Handschuh1
1 Faculty of Computer Science and Mathematics, University of Passau
{matthias.cetto, christina.niklaus<EMAIL_ADDRESS>
2 School of Computer Science, University of Manchester
<EMAIL_ADDRESS>

###### Abstract

We introduce Graphene, an Open IE system whose goal is to generate accurate,
meaningful and complete propositions that may facilitate a variety of
downstream semantic applications. For this purpose, we transform syntactically
complex input sentences into clean, compact structures in the form of core
facts and accompanying contexts, while identifying the rhetorical relations
that hold between them in order to maintain their semantic relationship. In
that way, we preserve the context of the relational tuples extracted from a
source sentence, generating a novel lightweight semantic representation for
Open IE that enhances the expressiveness of the extracted propositions.

##  1 Introduction

00footnotetext:  This work is licenced under a Creative Commons Attribution
4.0 International Licence. Licence details:
http://creativecommons.org/licenses/by/4.0/

Information Extraction (IE) is the task of turning the unstructured
information expressed in natural language (NL) text into a structured
representation in the form of relational tuples consisting of a set of
arguments and a phrase denoting a semantic relation between them:
$\langle$arg1; rel; arg2$\rangle$. Unlike traditional IE methods, Open IE is
not limited to a small set of target relations known in advance, but rather
extracts all types of relations found in a text. In that way, it facilitates
the domain-independent discovery of relations extracted from text and scales
to large, heterogeneous corpora such as the Web. Since its introduction by ?),
a large body of work on the task of Open IE has been described. By analyzing
the output of state-of-the-art systems (e.g., [Mausam et al. (2012, Del Corro
and Gemulla (2013, Angeli et al. (2015]), we observed three common
shortcomings.

First, relations often span over long nested structures or are presented in a
non-canonical form that cannot be easily captured by a small set of extraction
patterns. Therefore, such relations are commonly missed by state-of-the-art
approaches. Second, current Open IE systems tend to extract propositions with
long argument phrases that can be further decomposed into meaningful
propositions, with each of them representing a separate fact. Overly specific
constituents that mix multiple - potentially semantically unrelated -
propositions are difficult to handle for downstream applications, such as
question answering (QA) or textual entailment tasks. Instead, such approaches
benefit from extractions that are as compact as possible. Third, state-of-the-
art Open IE systems lack the expressiveness needed to properly represent
complex assertions, resulting in incomplete, uninformative or incoherent
propositions that have no meaningful interpretation or miss critical
information asserted in the input sentence.

To overcome these limitations, we developed an Open IE framework called
”Graphene” that transforms syntactically complex NL sentences into clean,
compact structures that present a canonical form which facilitates the
extraction of accurate, meaningful and complete propositions. The
contributions of our work are two-fold. First, to remove the complexity of
determining intricate predicate-argument structures with variable arity from
syntactically complex input sentences, we propose a two-layered transformation
process consisting of a clausal and phrasal disembedding layer. It removes
clauses and phrases that convey no central information from the input and
converts them into independent context sentences, thereby reducing the source
sentence to its main information. In that way, the input is transformed into a
novel hierarchical representation in the form of core facts and accompanying
contexts. Second, we identify the rhetorical relations by which core sentences
and their associated contexts are connected in order to preserve their
semantic relationship. These two innovations enable us to enrich extracted
relational tuples of the form $\langle$arg1; rel; arg2$\rangle$ with
contextual information that further specifies the tuple and to establish
semantic links between them, resulting in a novel lightweight semantic
representation for Open IE that provides highly informative extractions and
thus supports their interpretability in downstream applications. The source
code is available at https://github.com/Lambda-3/Graphene.

##  2 The System in a Nutshell

Graphene makes use of a two-layered transformation stage consisting of a
clausal and phrasal disembedding layer, which is followed by a final relation
extraction (RE) stage. It takes a text document as an input and returns a set
of semantically typed and interconnected relational tuples. The workflow of
our approach is displayed in Figure 1.

Input-Document

[…] Although the Treasury will announce details of the November refunding on
Monday, the funding will be delayed if Congress and President Bush fail to
increase the Treasury’s borrowing capacity. […]

$\rightarrow$ Transformation StageDOCUMENT-ROOTCoordination
ContrastThe Treasury will
announce details of
the November refunding.TEMPORAL(on Monday)Subordination
ConditionThe funding
will be delayed.Coordination
ListCongress fail to
increase the Treasury’s
borrowing capacity.President Bush fail to
increase the Treasury’s
borrowing capacity. $\rightarrow$ Relation Extraction The Treasury will
announce details […] TEMPORAL(on Monday) The funding will be delayed. Congress
fail to increase […] President Bush fail to increase […] $\langle$The
Treasury; will announce; details […]$\rangle$ TEMPORAL(on Monday) $\langle$The
funding; will be delayed; $\rangle$ $\langle$Congress; fail; to increase
[…]$\rangle$ $\langle$President Bush; fail; to increase […]$\rangle$
ContrastConditionConditionList

Figure 1: Extraction workflow for an example sentence.

###  2.1 Transformation Stage

During the transformation process, source sentences that present a complex
linguistic structure are converted into a hierarchical representation of core
facts and associated contexts that are connected by rhetorical relations
capturing their semantic relationship similar to Rhetorical Structure Theory
(RST) [Mann and Thompson (1988]. These compact, syntactically sound structures
ease the problem of recognizing predicate-argument relations that are
contained in the input without losing their semantic dependencies.

#### Clausal Disembedding.

In the clausal disembedding layer, we split up complex multi-clause sentences
that are composed of coordinated and subordinated clauses, relative clauses,
or attributions into simpler, stand-alone sentences that contain one clause
each. This is done in a recursive fashion so that we obtain a hierarchical
structure of the transformation process comparable to the diagrams used in
RST. As opposed to RST, however, the transformation process is carried out in
a top-down fashion, starting with the input document and using a set of hand-
crafted syntactic rule patterns that define how to split up, transform and
recurse on complex syntactic patterns111The complete rule set can be found
online:
https://github.com/Lambda-3/Graphene/blob/master/wiki/supplementary/syntactic-
simplification-patterns.pdf. Each split will create two or more simplified
sentences that are connected with information about (1) their constituency
type depicting their semantic relevance (coordinate or subordinate) and (2)
the rhetorical relation that holds between them. The constituency type infers
the concept of nuclearity from RST, where coordinate sentences (which we call
core sentences) represent nucleus spans that embody the central part of
information, while subordinate sentences (context sentences) represent
satellite spans that provide background information on the nucleus. The
classification of the rhetorical relations is based on both syntactic and
lexical features. While former are manifested in the phrasal composition of a
sentence’s phrasal parse tree, latter rely on a set of manually defined cue
phrases. In this way, a hierarchical tree representation of the recursive
transformation process for the whole document is constructed which we denote
as discourse tree. Its leaf nodes represent the simplified sentences that were
generated during the clausal disembedding layer.

#### Phrasal Disembedding.

After recursively dividing multi-clause sentences into stand-alone sentences
that contain one clause each, they are further simplified on a phrasal level.
For this purpose, sentences are processed separately and transformed into
simpler structures by extracting the following phrasal components from the
input: prepositional phrases, participial phrases, adjectival/adverbial
phrases, appositive phrases, lead noun phrases, coordinations of verb phrases,
enumerations of noun phrases and purposes. This task is assisted by the
sentence simplification system described in ?).

###  2.2 Relation Extraction

After the transformation stage, RE is performed by using the simplified
sentences as an input. The framework is designed to accept any type of RE
implementation which is able to extract relational tuples from single
sentences. The identified rhetorical relations from the transformation stage
are then mapped to the corresponding relational tuples in the form of simple
and linked contextual arguments (see Section 3). As a result, different
approaches for RE can be complemented with contextual information that further
specifies the extracted relational tuples. In that way, a new layer of
semantics is added to the task of RE that can be used in other NLP tasks (see
Section 6).

##  3 Output Format

In order to represent contextual relations between propositions, the default
representation of a relational tuple of the form $\langle$arg1; rel;
arg2$\rangle$ needs to be extended. Therefore, we present a novel lightweight
semantic representation for Open IE that is both machine processable and human
readable. It extends a binary subject-predicate-object tuple
$t\leftarrow(rel,arg_{subj},arg_{obj})$ with: a unique identifier $id$;
information about the contextual hierarchy, the so-called context-layer $cl$;
and two sets of semantically classified contextual arguments $C_{S}$ (simple
contextual arguments) and $C_{L}$ (linked contextual arguments), yielding the
final representation of $(id,cl,t,C_{S},C_{L})$ tuples. The context-layer $cl$
encodes the contextual hierarchy of core and contextual facts. Propositions
with a context-layer of $0$ carry the core information of a sentence, whereas
propositions with a context-layer of $cl>0$ provide contextual information
about propositions with a context-layer of $cl-1$. Both types of contextual
arguments $C_{S}$ and $C_{L}$ provide (semantically classified) contextual
information about the statement expressed in $t$. Whereas a simple contextual
argument $c_{S}\in C_{S},c_{S}\leftarrow(s,r)$ contains a textual expression
$s$ that is classified by the semantic relation $r$, a linked contextual
argument $c_{L}\in C_{L},c_{L}\leftarrow(id(z),r)$ refers to the content
expressed in another proposition $z$.

To facilitate the inspection of the extracted propositions, a human-readable
format, called RDF-NL, is generated by Graphene (see Figure 2). In this
format, propositions are grouped by sentences in which they occur and are
represented by tab-separated strings for the identifier $id$, context-layer
$cl$ and the core extraction that is represented by the binary relational
tuple $t\leftarrow(rel,arg_{subj},arg_{obj})$: subject argument $arg_{subj}$,
relation name $r$ and object argument $arg_{obj}$. Contextual arguments
($C_{S}$ and $C_{L}$) are indicated by an extra indentation level to their
parent tuples. The representation of a contextual argument consists of a type
string and a tab-separated content. The type string encodes both the context
type (S for a simple contextual argument $c_{S}\in C_{S}$ and L for a linked
contextual argument $c_{L}\in C_{L}$) and the classified semantic relation
(e.g. Cause, Purpose), if present. The content of a simple contextual argument
is the textual expression, whereas the content of a linked contextual argument
is the identifier of the target proposition.

Although the Treasury will announce details of the November refunding on
Monday, the funding will be delayed if Congress and President Bush fail to
increase the Treasury’s borrowing capacity. #1 0 the Treasury will announce
details of the November refunding S:TEMPORAL on Monday L:CONTRAST #2 #2 0 the
funding will be delayed L:CONTRAST #1 L:CONDITION #3 L:CONDITION #4 #3 1
Congress fail to increase the Treasury ’s borrowing capacity #4 1 president
Bush fail to increase the Treasury ’s borrowing capacity

Figure 2: Proposed representation format (RDF-NL) - human readable
representation.

Besides, the framework can materialize its relations into a graph serialized
under the N-Triples222https://www.w3.org/TR/n-triples specification of the
Resource Description Framework (RDF) standard. In that way, the consumption of
the extracted relations by downstream applications is facilitated. A detailed
description as well as some examples of the machine-readable RDF format are
available online333https://github.com/Lambda-3/Graphene/blob/master/wiki/RDF-
Format.md.

##  4 Usage

Graphene can be either used as a Java API, imported as a Maven dependency, or
as a service which we provide through a command line interface or a REST-like
web service that can be deployed via docker. A demonstration video is
available online444https://asciinema.org/a/bvhgIP8ZEgDwtmRPFctHyxALu?speed=3.

##  5 Benchmarking

Figure 3: Performance of Graphene.

We evaluated the performance of our Open IE system Graphene using the
benchmark framework proposed in ?), which is based on a QA-Semantic Role
Labeling corpus with more than 10,000 extractions over 3,200 sentences from
Wikipedia and the Wall Street Journal555available under
https://github.com/gabrielStanovsky/oie-benchmark. This benchmark allowed us
to compare our framework with a set of state-of-the-art Open IE approaches in
recall and precision (see Figure 3). With a score of 50.1% in average
precision, Graphene achieves the best performance of all the systems in
extracting accurate tuples. Considering recall, our framework (27.2%) is able
to compete with the best-performing baseline approaches (32.5% and 33.0%). The
interested reader can refer to ?) for more details.

##  6 Application Scenarios of the Lightweight Semantic Open IE representation

The resulting lightweight semantic representation of the source text in the
form of a two-layered hierarchy of semantically-linked relational tuples can
be used to facilitate a variety of artificial intelligence tasks, such as
building QA systems, creating text summarization applications or supporting
semantic inferences.

For example, QA systems could build upon the semantically typed and
interconnected relational tuples produced by our Open IE system Graphene to
investigate the dependencies between extracted propositions (such as
causalities, attributions and local or temporal contexts) and map specific
question types to the corresponding semantic relationships when querying the
underlying data. Based on the example given in Figure 2, one can imagine the
following user query:

Under which circumstances will the funding be delayed?

Here, the system could infer from the interrogative expression ”Under which
circumstances?” to search for propositions that are linked to the extraction
stating that $\langle$the funding; will be delayed; $\emptyset$$\rangle$ by a
conditional (CONDITION) relation. Accordingly, in this scenario the system is
expected to return propositions #3 and #4 of Figure 2.

##  7 Conclusion

We presented Graphene, an Open IE system that transforms sentences which
present a complex linguistic structure into a novel hierarchical
representation in the form of core facts and accompanying contexts which are
connected by rhetorical relations capturing their semantic relationship. In
that way, the input text is turned into clean, compact structures that show a
canonical form, thus facilitating the extraction of accurate, meaningful and
complete propositions based on a novel lightweight semantic representation
consisting of a set of semantically typed and interconnected relational
tuples. In the future, we aim to port this idea to languages other than
English.

## References

  * [Angeli et al. (2015]  Gabor Angeli, Melvin Jose Johnson Premkumar, and Christopher D. Manning.  2015\.  Leveraging linguistic structure for open domain information extraction.  In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 344–354. ACL.
  * [Banko et al. (2007]  Michele Banko, Michael J. Cafarella, Stephen Soderland, Matt Broadhead, and Oren Etzioni.  2007\.  Open information extraction from the web.  In Proceedings of the 20th International Joint Conference on Artifical Intelligence, pages 2670–2676. Morgan Kaufmann Publishers Inc.
  * [Cetto et al. (2018]  Matthias Cetto, Christina Niklaus, André Freitas, and Siegfried Handschuh.  2018\.  Graphene: Semantically-linked propositions in open information extraction.  In Prooceedings of COLING 2018. To appear.
  * [Del Corro and Gemulla (2013]  Luciano Del Corro and Rainer Gemulla.  2013\.  Clausie: Clause-based open information extraction.  In Proceedings of the 22Nd International Conference on World Wide Web, pages 355–366. ACM.
  * [Mann and Thompson (1988]  William C Mann and Sandra A Thompson.  1988\.  Rhetorical structure theory: Toward a functional theory of text organization.  Text-Interdisciplinary Journal for the Study of Discourse, 8(3):243–281.
  * [Mausam et al. (2012]  Mausam, Michael Schmitz, Stephen Soderland, Robert Bart, and Oren Etzioni.  2012\.  Open language learning for information extraction.  In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 523–534. ACL.
  * [Niklaus et al. (2016]  Christina Niklaus, Bernhard Bermeitinger, Siegfried Handschuh, and André Freitas.  2016\.  A sentence simplification system for improving relation extraction.  In Proceedings of COLING 2016: System Demonstrations.
  * [Stanovsky and Dagan (2016]  Gabriel Stanovsky and Ido Dagan.  2016\.  Creating a large benchmark for open information extraction.  In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing (EMNLP). ACL.