INTRODUCTION

OKgraph: Unsupervised Structured Data Extraction from Plain Text (Extended Abstract)

Maurizio Atzori∗

atzori@unica.it 0

Simone Balloccu

s.balloccu@studenti.unica.it 1

Andrea Bellanti

a.bellanti@studenti.unica.it 2

Emanuele Mameli

e.mameli@studenti.unica.it 3

Stefano Raimondo Usai

s.usai16@studenti.unica.it 4 0 Department of Math/CS, University of Cagliari , Italy 1 Department of Math/CS, University of Cagliari , Italy 2 Department of Math/CS, University of Cagliari , Italy 3 Department of Math/CS, University of Cagliari , Italy 4 Department of Math/CS, University of Cagliari , Italy

In this report we introduce OKgraph, a software library for (open) Knowledge Graph extraction from free text. Named after a two-year project where we studied and developed unsupervised algorithms addressing tasks related to taxonomy learning, the library contains NLP tools powered by these results.

INTRODUCTION

As introduced in [1], OKgraph has been a two-year project funded by Regione Autonoma della Sardegna focused on investigating the fundamental relationship between unstructured data (natural language text) and structured data (graphs representing knowledge), eventually leading to an autonomous way of inferring the latter from the former. In this short abstract we introduce the main outcome of our research, a library named after the project that learns meaningful graph triples autonomously from scratch, that is, from non-annotated free text such as Wikipedia. We followed a statistical approach, focusing on a number of subtasks described next.

THE LIBRARY

OKgraph is a python3 library that performs unsupervised naturallanguage understanding (NLU). It currently addresses the following tasks: • Set Expansion (or co-hyponyms discovery): given one or a short set of words, continues this set with a list of other "same-type" words (co-hyponyms) • Relation Expansion: given one or a short set of word pairs, continues this set with a list of pairs having the same implicit relation of the given pairs ∗contact author. Supported in part by Sardegna Ricerche (CRP 120) and MIUR PRIN project HOPE - High quality Open data Publishing and Enrichment. • Set Labeling (or hypernym discovery): given one or a short set of words, returns a list of short strings (labels) describing the given set (its type or hypernym) • Relation Labeling: given one or a short set of word pairs, returns a list of short strings (labels) describing the relation in the given set.

Being unsupervised, it only takes a free (untagged) text corpus as input, in any space-separated language. Scriptio-continua corpora and languages needs third-party tokenization techniques. 3

SET EXPANSION

Given a small set of words it will expand it with “same type" words: {Italy, France, Germany}

↓ {Spain, Denmark, Belдium...} In terms of graphs and taxonomy, the set expansion task is intended to get co-hyponyms (i.e., node siblings) from an initial set. It is crucial in graph construction, as it basically provides list of sametype nodes. We focused on singleton expansion [2], that expanding a set with cardinality 1, exploiting word embeddings similarity, and transitivity and symmetry of the same-as relation, that is: ( 1 ) Simmetric: given two co-hyponyms, their vectors should be simmetrically near. ( 2 ) Transitive: given three co-hyponyms transitivity should hold. For example given (Italy, Germany, Spain) if Italy is near Germany and Spain, then Germany must be near Spain. On the opposite given (Italy, Rome, Germany) we find that Rome breaks the bond with Germany.

The Set Expansion algorithms were evaluated by using 10-words sets belonging to a fixed number of categories; the testset was manually tagged and we obtained a significant improvement w.r.t. standard word2vec similarity:

Method NNS DEPTH 2WC

T5M At the time of writing OKgraph is the only library which is known to perform singleton expansion. We are also studying the problem of finding optimal vectors for hypernyms whose neighbours represents all hyponyms, using the powell optimization method with promising results. 4

RELATION EXPANSION

Given one or a set of word pairs will expand it with a list of pairs having the same implicit relation: {(Italy, Rome), (Germany, Berlin)}

↓ {(Spain, Madrid), (France, Paris)...}

This task is needed to extract edges connecting nodes in the ifnal knowledge graph. We exploit set expansion results over the two diferent dimensions of the pairs, and also linearity of word embeddings, computing the centroid of (Rome −Italy) and (Berlin − Germany), representing the vector direction of the edge “being capital of". 5

SET LABELING (HYPERNYM DISCOVERY)

The Set Labeling task is currently under testing and will be introduced in the library shortly. Given one or a set of words, returns a list of short strings (labels) describing the given set: {apple, pear , pineapple } → { f ruit , f ood ...} ( 1 ) This task allows the system to autonomously learn the taxonomy from the text. This translates into a possible enhancement of the other tasks. Again, we exploit word embeddings with the following heuristics: ( 1 ) Given a certain set S of words, and a set of potential labels, the hypernyms should have a very low variance, in terms of cosine similarity, with S.

( 2 ) Hypernyms should also be more frequent than co-hyponyms. We evaluated our unsupervised approach using the SemEval 2018 Task 9[3] benchmark, outperforming all others unsupervised algorithms and some supervised ones on all of the general-purpose corpora (1A, 1B, 1C). The following table shows the evaluation results on 1A corpus for the given task:

Method

CRIM r1

CRIM r2

MSCG-SANITY r1 vanillaTaxoEmbed (baseline)

NLP HZ MSCG-SANITY r2 300-sparsians r1 OKgraph Set Labeling 300-sparsians r2 MFH (baseline)

SJTU BCMI

Team 13

Apollo r2 apsyn (baseline) r1 balapinc (baseline) r1

Apollo r1 slqs (baseline) superv.

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ 6

RELATION LABELING

Given one or a short set of word pairs, returns a list of short strings (labels) describing the relation in the given set: {(Italy, Rome), (France, Paris)}

↓ {(capital, soccer team...)}

This task is important to automatically label edges in a graph. The desired relationships cannot be obtained by the use of classic means provided by the NLP and a classical text analysis would lead to a high number of false positives. To obtain an efective Relation Labeling algorithm, diferent statistical and linguistic knowledge have been used: ( 1 ) Relative frequency: given a sentence that contains the two entities of interest ("window"), the whole text frequency serves stopwords removal, and windows frequency helps labels discovery. ( 2 ) Windows parameterization: too large windows introduces noise, the opposite situation lead to information loss. ( 3 ) Window dynamisation: adoption of a variable distance between windows leads to better results.

The Relation Labeling algorithm works both on single and multiple pairs, through a logarithmic ranking that made it possible to evaluate the system on a manually tagged testset.

In order to evaluate the algorithm performance we used a set of 20 pairs for a fixed number of categories and evaluated the P@K for each one. The following table shows our evaluation results: