Extraction of semantic relations in noisy
user-generated law enforcement data
Marijn Schraagen

Floris Bex

Institute for Information and Computing Sciences
Utrecht University, The Netherlands
M.P.Schraagen@uu.nl

Institute for Information and Computing Sciences
Utrecht University, The Netherlands
F.J.Bex@uu.nl

Abstract—Relation extraction from text is a well-known andextensively studied topic in Natural Language Processing research. However, the implementation of relation extraction
approaches in real-world application scenarios raises various
methodological considerations which are often left implicit inexisting research. This paper explores these considerations using
a real-world dataset of user-generated police reports in Dutch.
The use of linguistic features based on dependency trees isinvestigated, including an ablation analysis of the importanceof individual features. The construction of negative examples formachine learning models is discussed, as well as the constructionof a baseline model. The methodological implications of usinga small dataset are discussed in terms of the design andperformance of a Long Short Term Memory network as well
as a Support Vector Machine. In general the models perform
well, however the definition of the classification task, and inparticular the construction of negative examples, are shown tohave a large impact on classification accuracy and subsequently
on the interpretation of the evaluation results.

I. I NTRODUCTION
Relation extraction, defined as finding instantiations ofspecific semantic relations between entities in text, has applications in various text processing tasks such as summarization, reasoning, and sentiment analysis. This paper addresses
methodological considerations for the relation extraction task
based on a case study of Dutch web form data in the legal
domain. Although relation extraction has been investigatedextensively in previous research, the implementation of thisresearch in a real application setting raises several considerations regarding the definition of the task and evaluation of theperformance. In this paper the following issues are discussed:
1) Section III: which task is addressed by a relation extraction approach? What are the prerequisites for thistask?
2) Sections IV,VII: are dependency tree features useful for
relation extraction in noisy user-generated data?
a) Is the performance of state-of-the-art tools for
Dutch on this type of data sufficient to extract
features from data?
b) Section VII-A1: which features are most useful forthis task?
Note: the term dependency tree features refers to thesequence of token-level features generated for a particular pair of tokens by computing the dependency tree forI would like to report fraud. I recently saw a bicycle forsale at an online trading platform and contacted advertiser
John Doe. Because he said that he lived in a different partof the country, we agreed that he would send the bicycle
to my home address in Amsterdam. I paid him in goodfaith but still have not received the bike. Mr. Doe does
not respond to my e-mails any more. I did some researchand saw that there is a second user called John Doe, butthat person claims to live in Amsterdam and uses anotheraccount number.

Fig. 1.
Example document from the crime report dataset with relation
annotations (adapted, translated and anonymized for presentation purposes).

a sentence and extracting the dependency path between
the tokens. This procedure and the dependency parser
used in the experiments are described in Section IV.
3) Section V: which methods can be used for realistic
negative sampling of relation examples?
4) Section VI: what is a good baseline for this task?
5) Section VII: how do standard machine learning algorithms behave for a small amount of data?
a) Which architecture can be used for different machine learning methods?
For the case study manual annotation has been performed on adataset for a single type of relation, i.e., residency (John lives
in Miami). An example document is shown in Figure 1. Using
the results of the current research, other types of relations canbe added in future work. The issues investigated in this paper
are centered around the specific nature of the dataset, i.e., unmoderated, user-generated, noisy, short texts, in Dutch, in thelegal domain. This research therefore explicitly does not aim
to provide a general comparison between relation extraction
methods, or to benchmark the performance of methodologicaladjustments using well-established datasets such as MUC or
ACE. Instead, the research aims to provide an overview ofissues and methodological aspects that need to be addressed
for the task of relation extraction on datasets containing thistype of data, and to provide a case study for this task using
well-known machine learning algorithms.

II. R ELATED WORK
The task of relation extraction has been studied extensively
as a subtask of information extraction. Early approaches
used domain-specific pattern matching [1], [2]. Facilitated byshared tasks such as MUC [3], ACE [4] and SemEval [5],domain-independent approaches have been developed using
statistical machine learning. Models have been trained using
shallow linguistic features such as suffixes, capitalization orsentence position of words [6] or POS features [7]. Basedon the assumption that semantic relations are correlated withsyntactic structure, various approaches are developed using
dependency relations as a feature. Different algorithms havebeen applied, such as Maximum Entropy models [8], Support
Vector Machines [9], [10], and more recently neural networkmodels using word embeddings, such as convolutional neural networks [11] and Long Short Term Memory networks[12], [13], [14]. Performance comparisons (in, e.g., [12] and[15]) show that, although neural network approaches generallyachieve high accuracy, the selection of features has a relatively
large influence on model accuracy compared to the selection of
the learning algorithm. Moreover, neural networks are assumed
to require a relatively large training set for convergencecompared to other machine learning algorithms [16], [17],[18], parameter settings for complex networks are non-trivial,
and computational cost may be prohibitive. Furthermore, using
word embedding features requires either a set of pre-trained
vectors for the target language, or an additional network layer
for training custom vectors within the dataset which may
increase the amount of data necessary for convergence. As oneof the goals of the current research, this issue is investigatedin more detail.
III. TASK DEFINITION
For supervised classification approaches a training set needs
to contain examples for all predefined classes. In commonlyused datasets generally several types of relations are annotated (e.g., SemEval 2010 contains 10 different relation types
such as cause–effect, component–whole, message–topic). Thismeans that a positive example for a particular relation can beused as negative example for other relations. However, in casethe dataset contains only examples of a single class (such as
the current case study, see Section IV), the relation extraction
task needs to be extended with a methodology to constructexplicit negative examples to provide as training data. The
task of constructing negative examples is non-trivial, giventhat the negative examples should be similar to the positive
examples in order to train a practically useful classifier, while
the negative examples should not be too similar, which would
prevent a classifier from finding a decision boundary. In
Section V methods for constructing negative examples are
discussed in detail.
A further issue relates to the general scope of the relation extraction task. Existing approaches generally consider
the task of classifying given pairs of entities. However, theselection of entity pairs from a document to present to theclassifier (i.e., the information retrieval aspect) is usually notalleen die persoon zegt in Amsterdam te wonen
but that person claims to live in Amsterdam
4. zegt[says]
3. persoon[person]

5. in
[in]

2. die[that]

6. Amsterdam[Amsterdam]

1. alleen[only]

7. te[to]
8. wonen[live]

Fig. 2. Dependency tree for a (partial) example sentence, containing theresidency relation (person,Amsterdam).

addressed by existing approaches. This issue can be irrelevant
for a number of reasons, e.g., the entities can be trivially
produced from a list (such as protein or drug names), or byan algorithm for named entity recognition, or given as a queryby a human user, or simply assumed to be given in a researchcontext. However, for real-world applications, entities may
not be known in advance and the identification of potential
entities may not be trivial, for example because the entities
are not necessarily named entities (e.g., the man lives near thecountry border). The task definition therefore changes fromclassifying predetermined pairs of entities to identifying andclassifying candidate relation pairs in non-annotated text. Notethat the retrieval aspect has been investigated in closely related
research areas such as temporal information processing [19].
Results from such tasks show that the retrieval aspect is indeed
a significant component of the task, with F1-scores ranging
from around 0.3 on raw text to around 0.5 when candidate
pairs are given.
The issue of identifying elements of a relation can be addressed by generating candidates from text. A model trained onthese candidates (and evaluated using classification accuracy
on a balanced test set) can be applied on a new document bygenerating all candidates in that document and classifying eachcandidate. The number of candidates can become very large,
which is both a practical issue as well as a theoretical problem
in selecting representative negative examples for training. A
restrictive heuristic can be applied to limit the number ofcandidates, as detailed in Section V. A further discussion of theuse of a selection heuristic for training examples is provided
in Section VIII.

translation
surfacelemma
full POS
main POS
named entity
chunk
direction

only
alleenalleenADV()
adverb
ADVP
→

that
die
die
PRON(sg,demonstr,nom)
pronounNP→

personpersoonpersoonN(sg,common,gendered)
noun
NP
→

says
zegt
zeggenV(pres,sg)
verb
VP
←

in
in
in
PREP(init)
preposition
PP←

Amsterdam
Amsterdam
Amsterdam
SPEC(name)speciallocation
NP
←

to
te
te
PREP(init)
preprosition
VP
←

live
wonen
wonen
V(inf)verb
VP←

TABLE IT OKEN FEATURES FOR THE EXAMPLE SENTENCE IN F IGURE 2.

alleen die persoon zegt in Amsterdam te wonen en geeft een ander rekeningnummer
only that person says in Amsterdam to live
and gives an other account number
advp {
np } vp pp np{ vp } conj vp {np}
but that person claims to live in Amsterdam and provides another account number
candidates N1 for dependency
path length 4 (11 in total)

only–says, that–in, that–and, person–Amsterdam, person–gives,
says–to, says–account number, in–live, in–gives, and–in, and–otherrelation marker
allowed chunk types
candidates N2 , window size 5(20 in total)

live (wonen)
NP, ADVP, ADJP, SBAR, unlabeledperson–Amsterdam, Amsterdam–person, person–an, an–person, ...,
other–account number, account number–otherFig. 3.

Example generation using methods N1 and N2 . A positive training example is shown in bold, all other pairs are negative examples.

IV. C ASE STUDY

V. D EVELOPMENT OF TRAINING DATA

A set of user-submitted crime reports in Dutch is used asa case study, as part of the project Intelligence Amplification
for Cybercrime [20]. Reports are generated from a web form
containing various specific fields (e.g., names, addresses, bankaccount numbers) and a free entry text field intended for a
description of the situation. All reports are in the domain
of internet fraud (e.g., an item is purchased online but notdelivered). The case study focuses on the automatic extractionof residency relations from the description text, since thisis often relevant for a police investigation. Using manual
annotation by a single annotator, a gold standard set of 2975
relation occurrences has been collected. Annotations consistof a part of a sentence containing a subject token, an object
token and all tokens in between (see Figure 1 for examples).
The Dutch dependency parser Frog [21] has been applied on
all documents to extract various linguistic features, including
dependency paths between relation elements. In Figure 2 andTable I the list of features is shown, as applied to an example
phrase representing a residency relation. These features areused to predict instances of residency relations in the corpus.
Note that the list of features includes both full Part-of-Speech
and main Part-of-Speech. The Frog parser uses the CGN tagset[22] which defines ten main tags, e.g., noun, verb, pronoun,
and a large set of (mostly morphosyntactic) properties foreach tag, e.g., singular, diminutive, past tense. In the current
experiments the POS tags are used both with and without theadditional properties, as main POS and full POS, respectively.

The dataset in the case study contains a single relation(i.e., residency), therefore explicit negative examples need tobe constructed. In order to create a representative training
set (i.e., to obtain a decision boundary in a trained model
which is close to the actual boundary of the positive class),
the negative examples need to be sufficiently similar to thepositive examples, while not being too similar to obscure thedecision boundary.
In the current experiments, two approaches for the construction of negative examples have been tested. In the first approach (N1 ) a training set is developed by pairing each positive
example with a random phrase for which the dependency pathhas the same length as the positive example. Negative examples are extracted from a random document in the corpus, i.e.,
positive and negative examples are not semantically related.
Moreover, syntactically the only similarity between examples
is the length of the dependency path, without restrictions on
parts-of-speech or surface form. In Figure 3 a number ofgenerated candidates is shown for an example sentence.
In the second approach (N2 ) a heuristic is designed to
extract candidate relation instances from the corpus. This
heuristic defines a relation marker token, a restricted set of
chunk types for relation elements, and the size of a window
around the relation marker where relation elements can belocated (see Figure 3 for an example). The relation marker
tokens as well as the chunk types have been determined man-ually1 based on analysis of the set of positive examples. This
heuristic produces a large number of candidates, of which, bydesign, a large majority is not an actual relation instance. Fromthese candidates a training set is developed using all positive
examples from the manually annotated dataset that satisfy theheuristic, and a random selection (of equal size) of negative
examples that satisfy the heuristic. Considering the sentence inFigure 3, for example, the pair person-Amsterdam is included
in set N2 as a positive example, while one or more of theother candidates (such as person-an or account number-other)
could be randomly selected as negative examples in set N2 .
Because the heuristic is restrictive, 28% of actual, annotatedpositive examples do not satisfy the criteria (e.g., when one of
the entities is part of a VP chunk) and are therefore excluded
from the training set in order to retain similarity between
positive and negative examples.
The currently used dataset contains manually annotatedpositive examples, allowing for supervised machine learning.
Because of the presence of these annotations, there is no needto generate positive examples automatically. However, notethat both methods for generating negative examples are also
capable of generating positive examples, either by randomly
extracting dependency sequences of length n (method N1 ) orby applying a more restrictive heuristic (method N2 ). Thisentails that these methods of generating training data, as well
as classifiers trained using this data, can be used to generateand classify candidate pairs of relation entities in unseen
data without annotations. As noted in Section III, this task
definition differs from previous approaches using data from,e.g., MUC or SemEval, that provide explicit candidate pairs forboth training and evaluation. Instead, the current methodology
is more similar to information retrieval tasks, where the goal is
to identify relevant units of information in a larger document
or corpus. In particular the approach using a linguistic heuristic(N2 ) shows similarity to information retrieval, because theheuristic restricts the set of candidates in such a way that also
a number of positive examples is excluded from the candidateset. This shift in task definition, and the implications for thecurrent approach, will be discussed in Section VIII.
VI. BASELINE
A typical pattern for residency relations consists of thesequence [person] lives in [location]. This pattern is used tocreate a baseline classifier which is intended as an indicationof the added value of machine learning models for this task.
The baseline pattern is a sequence of the following elements:
1) A noun phrase (as determined by the parser)2) 0–3 arbitrary tokens
3) Preposition in, from or at (Dutch: in, uit, te)4) A location-like token, either starting with an upper caseletter or appearing on a list of Dutch location names2 .
1 Marker tokens are defined using a regular expression for the word live,
allowing for spelling variants as well as grammatical variants (verb, adjective,
adverb). See Section VIII for a discussion on the use of marker tokens.
2 https://nl.wikipedia.org/wiki/Lijst van Nederlandse plaatsen

aux out

aux out

aux out

aux out

aux out

aux out

aux out

Sigmoid output layer
Dense Rectified Linear Unit layers (3)
LSTM

LSTM

LSTM

LSTM

LSTM

LSTM

LSTM

embeddinglayerembeddinglayer

one-hot
encoding

one-hot
encoding

one-hot
encoding

one-hot
encoding

one-hot
encoding

surfacesequence

lemma
sequencefull POS
sequence

main POS
sequence

named entity
sequence

chunk
sequence

direction
sequence

relation instanceFig. 4.

LSTM network architecture.

sequence length
input data typevocabulary size
surfacelemma
embedding layer
vector lengthmask zero
LSTM layer
units
merge
auxiliary output
type
activation
hidden layers
type
output units
activation
number of layers
output layer
type
activation
training
optimizer
loss function
all other parameters

21 tokens
integer (token indices)
4938
4151
512
true
32
concatenate
dense
sigmoid
dense
64
rectified linear unit
3
dense
sigmoidroot mean square propagation
binary cross entropy
Keras defaults

TABLE IIPARAMETER VALUES USED FOR THE LSTM MODEL .

Note that the definition of a pattern-matching baseline is necessarily arbitrary. However, the current baseline significantly
outperforms a fully random or fixed class assignment (which
would both produce an accuracy of 0.5 for a balanced twoclass dataset), indicating that this baseline indeed capturesa nontrivial amount of domain knowledge necessary for the
extraction of residency relations.
The baseline pattern could be extended to improve recall,for example by extending the subject element to other chunktypes or by allowing tokens between the preposition andthe location element. However, such extensions would create
an increasingly non-trivial pattern. The goal of the current
baseline is to show that the problem of extracting residency
relations from text is in fact non-trivial, and therefore amachine learning approach is appropriate for this problem.

classifierbaselinebaseline
L1
L2
L1
L2

VII. E XPERIMENTAL EVALUATION
To test the performance of complex machine learning models on small amounts of data, a Long Short Term Memory
network (Section VII-A) as well as a Support Vector Machine(Section VII-B) are evaluated on the crime report dataset.
A. Long Short Term Memory network
The performance of a Long Short Term Memory model(LSTM) is tested in a series of experiments. Note that this
implementation is not intended as a benchmark evaluation of
the model or as modification of network architectures from
related work. Instead, the experiments serve as a proof-ofconcept implementation of the issues discussed in previous
sections, i.e., approaches to feature extraction, construction oftraining examples and a baseline model for the application ofmachine learning on a small user-generated dataset.
The network setup is similar to [12], using parallel LSTM
layers for each of the seven features (see Figure 4). The surface
and lemma features are converted to an embedding representation, while the other features are represented using one-hot
encoding. The LSTM classifier is trained using the Keras
framework with TensorFlow backend (see https://keras.io),using parameter values as listed in Table II.
The results of training the LSTM network are listed inTable III. Two separate models L1 and L2 have been trainedon datasets N1 and N2 , respectively. For comparison, model
L1 is also tested using dataset N2 , as well as model L2 using
dataset N1 . The results show that the negative examples in set
N2 are more difficult to train than the example in set N1 . Thisis also indicated by cross-model performance.
In set N1 the negative examples have been randomly
selected from the corpus, with the length of the dependency
sequence as only constraint. As a consequence, in general thenegative examples are syntactically and semantically highly
different compared to the positive examples. These large
differences can be easily identified using a machine learningalgorithm, which is shown by the score of 0.99 for dataset
N1 in Table III. However, such a classifier is less capableof classifying more realistic examples correctly, as shown by
the performance of classifier L1 on set N2 . Therefore, dataset
N1 is considered non-representative for the relation extractiontask. On dataset N2 the LSTM model results in an accuracyof 0.95 (as highlighted in Table III). The implications of thisissue will be discussed further in Section VIII.
Given the small amount of data and the high accuracy
scores, an analysis of the errors is difficult to generalize.
However, manual inspection of the errors has shown thatmisclassified positive examples often contain a relatively more
complex syntactic structure, such as coordinating conjunctions (and he lived in Amsterdam) or complex noun phrases(the landlord of the apartment as advertised online lives in
London). Conversely, several misclassified negative examples
closely resemble a positive example (she is in Amsterdam)or consist of a partial residency relation (the woman fromthe advertisement lived). It is not always clear however why
a particular error is made. Increasing the sample size may

dataset
N1
N2
N1
N2
N2
N1

pos
0.36
0.50
0.99
0.92
0.99
0.93

neg
0.99
0.92
0.99
0.97
0.75
0.97

all
0.68
0.71
0.99
0.95
0.87
0.95

TABLE III
LSTM CLASSIFICATION ACCURACY USING 10- FOLD CROSS VALIDATION .

rank
1.

accuracy
0.961133583

2.

0.959109304

3.
4.

0.952631573
0.94777328

5.
6.

0.944534425
0.943522279

7.

0.943117426

8.

0.938259124

9.

0.93684211

10.

0.93663969

24.
63.
108.
114.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.

0.920850203
0.891902833
0.857894746
0.851012152
0.838663973
0.835222674
0.831376525
0.812955458
0.810526303
0.78259109
0.781578948
0.730364364
0.727327936
0.721255062

combination
full POS, main POS, named entity,
chunk type, direction
full POS, main POS, named entity,
chunk typefull POS, main POS, chunk type, direction
surface, lemma, full POS, main POS,
named entity, chunk type, direction
full POS, main POS, named entity, direction
surface, lemma, full POS, main POS,
chunk type, direction
surface, lemma, full POS, main POS,
named entity, chunk typesurface, lemma, full POS, main POS,
chunk typesurface, lemma, full POS, named entity,
chunk typesurface, lemma, full POS, named entity,
chunk type, direction
full POS, main POS
surface, lemma
full POS
surfacemain POS
lemma
full POS, named entity, direction
chunk type
named entity, direction
main POS, named entity, direction
main POS, chunk type, direction
named entity
direction
named entity, chunk type, direction

TABLE IVS ELECTION OF ABLATION RESULTS .

improve this type of analysis, both by reducing the number ofaccidental classification errors as well as by enabling a morerobust quantitative error analysis approach.
1) Feature ablation: As further analysis of the results anablation experiment has been performed with all combinationsof features (127 feature combinations in total for 7 features).
This experiment is performed using 10-fold cross-validationon the L2 , N2 setup, which is considered the most realistic
scenario. A selection of results is shown in Table IV.
The results show that the full POS feature is highly informative for relation classification. This feature is present in
the 10 highest scoring models (with accuracy values ranging
from 0.93–0.96), and it is also the feature that performs best in
isolation (accuracy 0.86). In contrast, the surface and lemma
features do not perform as well as expected. Even though thesefeatures occur in the highest scoring models, they are generally
complemented with a POS feature (full POS, main POS, or

B. Support Vector Machine
The LSTM model allows inputs to be presented to the
network as a sequence. This reduces the number of input
nodes required to represent sequence inputs, given that one
input can be used for the full sequence. In contrast, nonrecurrent models such as Support Vector Machines (SVMs)
need to process each element of an input sequence separately.
For longer sequences this leads to a very extensive input
layer, which means that both more parameters need to be
trained and the sparsity of the input increases. To address thisissue, the dimensionality of the input can be reduced during
preprocessing. For SVMs this can be achieved by defining
a custom kernel function that computes similarity between
input sequences (cf. [10]), reducing the dataset to a collectionof single-valued similarities between examples. In the current
experiments similarity is defined as the number of common
features for each pair of tokens forphrases,
P equal-lengthP
and 0 otherwise (i.e., sim(A, B) = i f ∈features Ai (f ) =Bi (f ) if||A|| = ||B||, else 0).
The dependency kernel is non-normalized, i.e., ranging from0 to L · F for path length L and number of features per
token F . As a consequence, the maximum score is higher
for longer paths, which may influence classification accuracy. Two normalization approaches have been tested, i.e.,
sim exp (A, B) = 1 − e−γsim(A,B) for various values of γ, andsim prop (A, B) = sim(A,B)||A||·F . Note that sim exp (see Figure 5)
effectively maps high similarity scores to 1 (i.e., path lengthis not taken into account, as in the original kernel), whereas
sim prop is a proportional scaling function.

1

=0.005=0.01
=0.02
=0.03
=0.04
=0.05
=0.1
=0.2

0.8

1-e sim(A,B)both). In isolation these features result in lower accuracy
compared to the POS features, showing differences for the
single features (full POS 0.86, main POS 0.85, surface 0.85,
lemma 0.84) and when combined ({full POS, main POS} 0.92,{surface, lemma} 0.89). A possible cause for this behavior is
the relative complexity of the surface and lemma features, witha large vocabulary size and an embedding layer, as opposedto the full POS feature (148 possible values) or the main POS
feature (14 possible values), both presented to the network in
one-hot encoding. Another possible cause is that vocabulary
items may be used in various configurations independent of
the presence of a relation, while the grammatical structure as
represented in a POS sequence is more directly correlated torelation occurrences.
Less useful features include direction and chunk type, whichis as expected given the coarse-grained nature of these features. The named entity feature can be useful, however thisis mostly observed in combination with other features. Thiscan be explained by the sparse nature of the named entity
feature, which indicates that the presence of the feature can beinformative, while the absence of the feature does not influence
the classification to a large degree.
Using all available features results in an accuracy of 0.95
(rank 4), which indicates that the full set of features is indeed
useful for the classification of relation instances.

0.6



0.4

0.2

0
0

10

20

30

40

50

sim(A,B)

Fig. 5.

Behavior of a SVM scaling function using various γ values.
classifierbaselinebaseline
S1
S2
S1
S2

dataset
N1
N2
N1
N2
N2
N1

pos
0.36
0.50
0.95
0.89
0.99
0.85

neg
0.99
0.92
0.95
0.89
0.52
0.93

all
0.68
0.71
0.95
0.89
0.76
0.89

TABLE VSVM CLASSIFICATION ACCURACY USING 10- FOLD CROSS VALIDATION .

The results of the experiments are listed in Table V. As
for the LSTM model, the baseline is compared to a Support
Vector Machine S1 trained using dataset N1 and a second
SVM S2 trained using the dataset N2 . Evaluation has been
performed both within and across datasets. Similar to the
LSTM results, the negative examples in set N2 are moredifficult to train (using the current dependency kernel). The
cross-model performance shows that the accuracy of model
S2 is similar on both sets, however model S1 is unable toclassify set N2 correctly (i.e., accuracy on negative examples
is at near chance level).
The influence of scaling for the SVM classifier is tested
using S2 , N2 . However, both exponential scaling and proportional scaling result in lower accuracy compared to theunscaled kernel.
VIII. D ISCUSSION
The results show that the LSTM model outperforms the
SVM model in all combinations of training and test data.
This indicates that the LSTM model, while being relatively
complex, is still capable of generalizing over a small dataset.
The performance of the SVM could be influenced by the model
itself, however the dimensionality reduction method using a
distance kernel may also explain the difference with the LSTM
model. Furthermore, scaling functions for dependency pathcomparisons are shown to negatively impact model accuracy.
Considering the training data, the results show that the
selection of negative examples has a large influence on model
performance. The examples in set N2 can be considered tobe more representative as relation candidates, therefore theaccuracy of the models using this dataset offer a more realistic
evaluation compared to the models trained on set N1 .
The word embeddings are trained within the network, using
dependency token sequences as input. Alternatively, existingembeddings for Dutch could have been used (e.g., [23]). However, pre-trained embeddings from a general domain are often
less useful for specific tasks (see, e.g., [24], [25], cf. also [12]on which the design of the LSTM in this paper is based). Given
the current results the non-pretrained embeddings work well,which was somewhat unexpected given the limited amountof data (around 30k tokens in total). Further interpretationof this conclusion should consider the results of the ablation
experiment (Section VII-A1), which shows that the embedding
features are outperformed by the POS features represented
with one-hot encoding. Nonetheless, the ablation results also
show that the embedding features trained on the current small
dataset do contribute positively to classification accuracy.
In the current research a heuristic is used to identify aset of potential training and test examples, from which theactual training and test data is sampled (see Section V). This
heuristic needs to be defined such that the resulting examples
are realistic potential candidates, without being too restrictive.
The precision of the heuristic is expected to be low (e.g., in
Figure 3 only one out of 20 candidates is a positive example),but the generated negative examples should still somewhat
resemble the positive examples. More importantly, the recall of
the heuristic should be high, in order to include as many valid
positive examples as possible in the training and test data. Thisbalance is difficult to achieve, the heuristic used in the current
case study for example includes only 72% of the positive
examples in the annotated corpus. The task definition thereforechanges, from identifying all relation occurrences in a text
to identifying relation occurrences that satisfy the heuristic.
This can be a significant restriction, such as in the case of
the heuristic used in the current research, which is defined interms of a small set of relation marker tokens and grammaticalchunk categories. However, the practical and methodologicalimplications of this issue are not trivially clear, and need to
be investigated in more detail in further research.
To summarize the contributions of the current paper, themethodological issues stated in Section I are addressed below.
1) Which task is addressed by a relation extraction approach? What are the prerequisites for this task?
Relation extraction can be defined as a classification task, i.e.,
to determine the type of relation between two given entities.
However, in many application scenarios the scope of the taskneeds to be extended to include a retrieval aspect, i.e., givena text, determine which tokens are candidate elements of asemantic relation, and determine the type of relation oncethe candidates have been identified. For this task definition amethodology for generating candidates needs to be developed.
In the current paper two approaches have been investigated,using various linguistically motivated criteria for selecting
relation candidates. In the current case study this approachhas been used to create negative examples for training aclassifier, which was necessary given that the annotated dataset

contains only a single type of relation. In case multiple types ofrelations are available it is not necessary to construct negative
examples. However, in order to extend the task definition fromclassification to retrieval, also in the case of multiple relation
types a candidate generation methodology is needed.
2) Are dependency tree features useful for relation extraction in noisy user-generated data?
Dependency tree features can be used successfully for this typeof data, even when performing strong dimension reduction.
a) Is the performance of state-of-the-art tools for
Dutch on this type of data sufficient to extract
features from data?
The statistical dependency parser Frog provides sufficiently robust linguistic features for this type of
data. The parser acts as a filter on various errors inuser-generated text, e.g., incomplete sentences, metacharacters introduced by copying fragments of e-mailconversations or website content, spelling errors orgrammatical errors. This type of data does introduce
errors in sentence splitting, lemmatization, POS tagging,dependency parsing, etc., however a statistical parser isgenerally capable of producing a reasonable linguistic
analysis. Combined with the data generalization performed by the classifier, this type of data does not
significantly impair classification accuracy. It should
be noted, however, that the phrases containing relation
examples are contain a relatively low amount of noise.
If an NLP task would be performed using different partsof the text, then data quality may prove to be a more
problematic issue.
b) Which features are most useful for this task?
The ablation experiments show that Part-of-Speech features are highly informative for the relation extractiontask. Vocabulary features (surface form and lemma)
contribute less to the overall task accuracy, however thismay be caused by the relatively small amount of training
data available for the embedding layers.
3) Which methods can be used for realistic negative sampling of relation examples?
Using a heuristic that imposes linguistic constraints on constructed negative examples creates a more complex classification problem, which is therefore more useful in practise.
However, the resulting accuracy score (0.95) still suggests thatthe set of negative examples should be restricted further. An
undesired side effect of such a restriction may be, however,that a larger number of actual positive examples will also be
excluded from training. Alternatively, the task of residency
relation extraction as defined in the case study might beinsufficiently complex itself. Related work on SemEval 2010
data (e.g., [12]) shows a maximum accuracy of around 0.85,
which suggests that the current task, while evidently nontrivial, is indeed less complex than the task presented bystandard datasets. This hypothesis could be tested by adding
more relation types, which is left for future work due to theadditional annotation effort required.

4) What is a good baseline for this task?
The baseline defined in Section VI shows that the task cannot
be fully solved by a simple pattern matching approach. Extending the pattern could improve baseline accuracy, however
the boundary between an extended pattern and a full rule-basedclassifier is not trivially clear.
5) How do standard machine learning algorithms behave
for a small amount of data?
Both the LSTM model and the SVM model perform well on
the relation extraction task. The LSTM model outperforms
the SVM model, however this may result from the dimension
reduction approach as applied in the design of the SVM.
a) Which architecture can be used for different machine learning methods?
For Long Short Term Memory networks, a separate
network layer for each feature type and a poolinglayer to combine the output of all feature layers isshown to result in high accuracy scores, consistent withresults from previous research [12]. For a Support Vector
Machine, using a dependency path similarity kernel
results in sufficiently high accuracy scores, consistent
with [10]. However, the LSTM model outperforms the
SVM approach. Note that accuracy (i.e., number ofexamples correctly classified relative to the total numberof examples) is used as an evaluation measure given thatthe classification task is binary and the classes in the test
set are perfectly balanced. In future work the method
could be evaluated against all possible token pairs ina given test document. In this case the test examples
would be highly imbalanced towards the negative class,which means that precision and recall should be used as
evaluation measures instead of accuracy.
The results of the current research provide a first step in theapplication of information extraction in the law enforcement
domain. Subsequent steps include annotation and classificationof additional relations (e.g., payment information or sending
and receiving goods) as well as semantically more complex
processing, e.g., the detection of a false identity from text,
i.e., whether the residency relation as extracted from the crime
report should be considered real. In future work these further
steps need to be investigated in more detail.
ACKNOWLEDGMENT
This research is part of the project Intelligence Amplification
for Cybercrime which has been funded by the Dutch National
Police Innovation Programme.
R EFERENCES[1] R. Schank, “Computer understanding of natural language,” Behavior
Research Methods & Instrumentation, vol. 10, no. 2, pp. 132–138, 1978.
[2] S. Lytinen and A. Gershman, “ATRANS: Automatic processing ofmoney transfer messages,” in Proceedings of AAAI-86, 1986, pp. 1089–
1093.
[3] R. Grishman and B. Sundheim, “Message understanding conference-6:
A brief history,” in COLING 1996: The 16th International Conference
on Computational Linguistics, vol. 1, 1996.

[4] G. Doddington, A. Mitchell, M. Przybocki, L. Ramshaw, S. Strassel,
and R. Weischedel, “The Automatic Content Extraction (ACE) programtasks, data, and evaluation,” in Proceedings of LREC 2004, 2004.
[5] I. Hendrickx, S. N. Kim, Z. Kozareva, P. Nakov, D. Ó Séaghdha, S. Padó,
M. Pennacchiotti, L. Romano, and S. Szpakowicz, “SemEval-2010
Task 8: Multi-way classification of semantic relations between pairs of
nominals,” in Proceedings of the NAACL HLT Workshop on Semantic
Evaluations: Recent Achievements and Future Directions, 2009, pp. 94–
99.
[6] D. Roth and W.-t. Yih, “A linear programming formulation for global
inference in natural language tasks,” in Proceedings of the Eighth
Conference on Computational Natural Language Learning (CoNLL2004) at HLT-NAACL, 2004.
[7] S. Ray and M. Craven, “Representing sentence structure in hidden
markov models for information extraction,” in Proceedings of the 17th
International Joint Conference on Artificial Intelligence, 2001, pp. 1273–
1279.
[8] N. Kambhatla, “Combining lexical, syntactic, and semantic features withmaximum entropy models for extracting relations,” in Proceedings of the
ACL 2004 Interactive Poster and Demonstration Sessions, 2004.
[9] A. Culotta and J. Sorensen, “Dependency tree kernels for relation extraction,” in Proceedings of the 42nd annual meeting of the Association
for Computational Linguistics, 2004.
[10] R. Bunescu and R. Mooney, “A shortest path dependency kernel for
relation extraction,” in Proceedings of HLT/EMNLP 2005, 2005, pp.
724–731.
[11] Y. Liu, F. Wei, S. Li, H. Ji, M. Zhou, and H. Wang, “A dependencybased neural network for relation classification,” in Proceedings of
ACL/IJCNLP 2015, 2015, pp. 285–290.
[12] Y. Xu, L. Mou, G. Li, Y. Chen, H. Peng, and Z. Jin, “Classifying relations via long short term memory networks along shortest dependency
paths,” in Proceedings of EMNLP 2015, 2015, pp. 1785–1794.
[13] M. Miwa and M. Bansal, “End-to-end relation extraction using LSTMs
on sequences and tree structures,” in Proceedings of ACL 2016, 2016,
pp. 1105–1116.
[14] N. Peng, H. Poon, C. Quirk, K. Toutanova, and W.-t. Yih, “Crosssentence n-ary relation extraction with Graph LSTMs,” in Proceedingsof ACL 2017, 2017, pp. 101–115.
[15] D. Zeng, K. Liu, S. Lai, G. Zhou, and J. Zhao, “Relation classification
via convolutional deep neural network,” in Proceedings of COLING
2014, 2014, pp. 2335–2344.
[16] H. Adel, B. Roth, and H. Schütze, “Comparing convolutional neuralnetworks to traditional models for slot filling,” in Proceedings of
NAACL-HLT 2016, 2016, pp. 828–838.
[17] H.-W. Ng, V. D. Nguyen, V. Vonikakis, and S. Winkler, “Deep learningfor emotion recognition on small datasets using transfer learning,” inProceedings of ICMI ’15, 2015, pp. 443–449.
[18] R. Balabin and E. Lomakina, “Support vector machine regression (LSSVM) – an alternative to artificial neural networks (ANNs) for the
analysis of quantum chemistry data?” Physical Chemistry Chemical
Physics, vol. 13, pp. 11 710–11 718, 2011.
[19] N. UzZaman, H. Llorens, L. Derczynski, J. Allen, M. Verhagen, andJ. Pustejovsky, “SemEval-2013 Task 1: TempEval-3: Evaluating time expressions, events, and temporal relations,” in Second Joint Conference on
Lexical and Computational Semantics (* SEM), Volume 2: Proceedingsof the Seventh International Workshop on Semantic Evaluation (SemEval
2013), vol. 2, 2013, pp. 1–9.
[20] F. Bex, J. Peters, and B. Testerink, “A.I. for online criminal complaints:from natural dialogues to structured scenarios,” in Proceedings of the
ECAI 2016 workshop on Artificial Intelligence for Justice, 2016, pp.
22–29.
[21] A. van den Bosch, B. Busser, S. Canisius, and W. Daelemans, “An
efficient memory-based morphosyntactic tagger and parser for Dutch,” in
Selected Papers of the 17th Computational Linguistics in the Netherlands
Meeting. Netherlands Graduate School of Linguistics, 2007, pp. 99–
114.
[22] CGN Consortium, “Spoken Dutch Corpus,” 2003.
[23] S. Tulkens, C. Emmery, and W. Daelemans, “Evaluating unsupervised
Dutch word embeddings as a linguistic resource,” in Proceedings of
LREC 2016, 2016, pp. 4130–4136.
[24] S. Lai, K. Liu, L. Xu, and J. Zhao, “How to generate a good wordembedding?” IEEE Intelligent Systems, vol. 31, no. 6, pp. 5–14, 2016.
[25] H. Zamani and W. B. Croft, “Relevance-based word embedding,” inProceedings of SIGIR ’17. ACM, 2017, pp. 505–514.