This paper presents methods for extraction of semantic relations between words. The methods rely on the k-nearest neighbor algorithms and two semantic similarity measures to extract relations from the abstracts of Wikipedia articles. We analyze the proposed methods and evaluate their performance. Precision of the extraction with the best method achieves 83%. We also present an open source system which effectively implements the described algorithms.
There exist many types of semantic relations between words (concepts) – synonymy,
metonymy, antonymy, association, etc. In the context of this work, semantic relations
are synonyms, hypernyms, and co-hypernyms (words with a common hypernym).
These relations are successfully used in various NLP applications, such as word sense
disambiguation [
A popular approach to relation extraction is based on the lexico-syntactic patterns
[
The approach described in this work fills this gap, and focuses on the application
of Wikipedia-based similarity measures to semantic relation extraction. The goal of
the method proposed in this article is to discover a set of relations between a set of
input concepts (e. g. terms of a given domain). In this work, we deal with linguistic
concepts, such as words or multiword expressions (not to be confused with a similar
notion from the Formal Concept Analysis [
In Section 2, we introduce our approach to semantic relation extraction. First, we describe the data and how they are preprocessed in Section 2.1. Next, we discuss the algorithms of semantic relation extraction (Section 2.2) and the used measures of semantic similarity (Section 2.3). Finally, we present key details of the extraction system Serelex (Section 2.4). In Section 3, the experimental results are presented and discussed. Section 4 deals with the related work and Section 5 wraps up with a conclusion and a description of the future research. 2 2.1
Input data of the method is a set of definitions for each input concept . We use the data available from the DBPedia.org to build a set of definitions of English terms (multi-word expressions are not included)2. For each input concept a pair is built, where concept is an exact title of a Wikipedia article, and definition is a text of the first paragraph of this article. The experiments described in this work were conducted on a subset of articles with titles containing no numbers and special symbols. We collected 327.167 Wikipedia articles according to this principle. For the goals of our experiments, we prepared two datasets containing 775 words (824Кb) and 327.167 words (237Мb) respectively3.
Articles were preprocessed as follows. First, we removed all markup tags and
special characters. Second, we performed lemmatization and part-of-speech tagging with
the TreeTagger [
axiom; in#IN#in traditional#JJ#traditional logic#NN#logic ,#,#, an#DT#an axiom#NN#axiom or#CC#or postulate#NN#postulate is#VBZ#be a#DT#a proposition#NN#proposition that#WDT#that is#VBZ#be not#RB#not proved#VVN#prove or#CC#or demonstrated#VVN#demonstrate but#CC#but considered#VVN#consider to#TO#to be#VB#be either#RB#either self-evident#JJ#self-evident ,#,#, or#CC#or subject#JJ#subject to#TO#to necessary#JJ#necessary decision#NN#decision .#SENT#.
Senlar [
Algorithms of semantic relation extraction discussed in this article, are based on the
component analysis [
The first algorithm calculates semantic relations with the KNN algorithm, the second relies on the MKNN (Mutual KNN) algorithm. The only meta-parameter of the algorithms is the number of nearest neighbors . The algorithms are presented in Fig.1.
The algorithms first calculate pairwise similarities between all the input terms (lines 1-12). The array of the nearest neighbors Rmatrix contains nearest neighbors of each term. We keep the number of elements in each row of Rmatrix equals which let us minimize the memory footprint. The last stage for the KNN is simply to print the nearest neighbor concepts for each concept. In contrast to KNN, MKNN establishes a relation only if a pair of words are mutual neighbors (lines 1321). Therefore, MKNN filters out those relations extracted by KNN which are not mutually related.
Complexity of the developed algorithms is a function of the number of input concepts | |. Time complexity is | | and space complexity is | | , where is the number of nearest neighbors. Function similarity (line 6) in the algorithms KNN and MKNN calculates a pairwise semantic similarity of two concepts , from their definitions . The larger the value of semantic similarity, the closer the “sense” of the concepts. Two similarity functions are considered here. The first is the gloss overlap of the definitions of the concepts : ( ) |
| | | | |
Here the numerator is the number of the common words in the definitions; | | is the number of words in the definition . The second measure is the cosine between vectors of definitions representing concepts : ∑ ( ) ‖ ‖ ‖ ‖ √∑ √∑
Here is the frequency of the lemma in the definition . The both similarity measures use the lemmas (e. g., animals#NNS#animal), and do not use stopwords found in the definitions. For the both of similarity measures only matches of the nouns (NN, NNS, NP), verbs (VV, VVN, VVP), and adjectives (JJ) are considered.
The system is a console application implemented in C++ and available for Windows and Linux platforms (32/64 bits). It consists of the definition class, global parameters class, component analysis class, and several additional classes and functions (see Fig.2). The main functions of the program are: loading files of stopwords and input concepts ; loading the file with definitions taking into account the stopwords; calculation of the pairwise semantic similarities between the input concepts ; building the list of the semantic relations .
In order to achieve high performance of the system, we map each word to a numerical identifier. This procedure significantly reduces running time of the program. The system extensively uses the Standard Template Library (STL) and the Boost library4. The source code and the binaries of the Serelex are available under the conditions of the LGPLv3 license at https://github.com/AlexanderPanchenko/Serelex. We investigated the algorithms KNN and MKNN with the two measures described above and with various numbers of nearest neighbors (see Fig. 3). As one may expect, the number of extracted relations linearly depends on the number of nearest neighbors both for KNN and MKNN. The number of extracted relations depends little on the similarity measure type. The key difference between the two measures is that Cosine takes into account frequencies, while Gloss Overlap does not. The little
difference in the results is likely to be due to the fact that the definitions are short. Thus, frequency information does not contribute a lot to the result.
The algorithm KNN extracts more relations than the MKNN for the same value of . It happens because the MKNN filters out pairs of concepts which are not mutual nearest neighbors. According to our experiments, MKNN filters around 50-70% of the relations extracted by KNN, depending on the number of the concepts | | and the value of .
We estimated the precision of the extraction between a set of 775 concepts for both algorithms with . In order to measure the precision, we manually labeled the files with the extracted relations. The precision was calculated as the number of correctly extracted relations to the number of extracted relations. The results are presented in Table 1. The examples of extracted relations between a set of 775 concepts with algorithm MKNN ( ) and the gloss overlap similarity measure are presented below5:
Due to the huge number of extracted relations (see Fig. 3), it is hard to calculate
manually the extraction precision for all values of . We expect the precision to
decrease for values of . According to our preliminary experiments, we recommend
to use the number of the nearest neighbors . In future, we plan to use the
WordNet [
The performance of the developed system is rather high. For instance, the file with 775 definitions is processed for less than 3 seconds on a Linux server equipped with Intel(R) Xeon(R) CPU E5606@2.13GHz (the program does not use multithreading). The algorithm KNN used with the measure Gloss Overlap processes the file with the 327.167 definitions within 3 days 3 hours and 47 minutes. 5 The full list of the extracted relations with this configuration is available at http://cental.fltr.ucl.ac.be/team/~panchenko/def/results-775/overlap_mknn_2.csv
KNN
Cosine Gloss overlap Cosine Gloss overlap 4
Senlar [
WikiRelate! is the most similar system to ours. It was proposed by Strube and
Ponzetto in 2006 [
WikiRelate! achieves a correlation with human judgments of 0.59. However, since WikiRelate! does not extract relations, we cannot directly compare its performance with our results.
In [
We proposed and analyzed the method for semantic relation extraction from texts of Wikipedia with algorithms KNN and MKNN and two semantic similarity measures. The preliminary experiments showed that the best results (precision of 83%) are obtained with the method based on MKNN algorithm and Gloss Overlap similarity measure. We also presented an open source system, which efficiently implements the proposed method.
The developed method seems to be enough precise and computationally efficient
for the practical NLP applications. Currently, we are working on integration of the
extracted semantic relations in a text categorization system [
The method is able to calculate relations between a huge number of concepts, each of which is represented by a title of a Wikipedia article. Thus, it could be used to extract relations between 3.8 million of concepts in English Wikipedia and 17 million of concepts in other 282 languages of Wikipedia. The only language-dependent resources used in the method are stoplist, part-of-speech tagger, and lemmatizer. These resources are available for the most of the European languages for free. Finally, Serelex can extract relations from other sources of definitions, such as traditional dictionaries or Wiktionary, provided these data are provided in the proper format.
The main directions of our future research are: (1) using the developed method to extract relations in Russian, French, and German languages; (2) improving the precision of the extraction by clustering of the obtained semantic relations graph.
Yuri Philippovich, Adrien Dessy, Olga Morozova, Nicolas Danhier, and three anonymous reviewers provided comments and remarks, which considerably improved quality of the paper. Alexander Panchenko thanks Wallonie-Bruxelles International (WBI) foundation for the support.