{'fraction_non_alphanumeric': 0.043872234387978555, 'fraction_numerical': 0.02076568753303632, 'mean_word_length': 4.539104976997073, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Detecting Semantic Relations between Named Entities in Text Using Contextual Features

This paper proposes a supervised learning method for detecting a semantic relation between a given pair of named entities, which may be located in different sentences. The method employs newly introduced contextual features based on centering theory as well as conventional syntactic and word-based features. These features are organized as a tree structure and are fed into a boosting-based classification algorithm. Experimental results show the proposed method outperformed prior methods, and increased precision and recall by 4.4% and 6.7%.


Introduction
Statistical and machine learning NLP techniques are now so advanced that named entity (NE) taggers are in practical use. Researchers are now focusing on extracting semantic relations between NEs, such as "George Bush (person)" is "president (relation)" of "the United States (location)", because they provide important information used in information retrieval, question answering, and summarization.
We represent a semantic relation between two NEs with a tuple [NE 1 , NE 2 , Relation Label]. Our final goal is to extract tuples from a text. For example, the tuple [George Bush (person), the U.S. (location), president (Relation Label)] would be extracted from the sentence "George Bush is the president of the U.S.". There are two tasks in extracting tuples from text. One is detecting whether or not a given pair of NEs are semantically related (relation detection), and the other is determining the relation label (relation characterization).
In this paper, we address the task of relation detection. So far, various supervised learning approaches have been explored in this field (Culotta and Sorensen, 2004;Zelenko et al., 2003). They use two kinds of features: syntactic ones and wordbased ones, for example, the path of the given pair of NEs in the parse tree and the word n-gram between NEs (Kambhatla, 2004).
These methods have two problems which we consider in this paper. One is that they target only intrasentential relation detection in which NE pairs are located in the same sentence, in spite of the fact that about 35% of NE pairs with semantic relations are inter-sentential (See Section 3.1). The other is that the methods can not detect semantic relations correctly when NE pairs located in a parallel sentence arise from a predication ellipsis. In the following Japanese example 1 , the syntactic feature, which is the path of two NEs in the dependency structure, of the pair with a semantic relation ("Ken 11 " and "Tokyo 12 ") is the same as the feature of the pair with no semantic relation ("Ken 11 " and "New York 14 ").
(Ken11 was born15 in Tokyo12, Tom13 in New York14.) To solve the above problems, we propose a supervised learning method using contextual features.
The rest of this paper is organized as follows. Section 2 describes the proposed method. We report the results of our experiments in Section 3 and conclude the paper in Section 4.

Relation Detection
The proposed method employs contextual features based on centering theory (Grosz et al., 1983) as well as conventional syntactic and word-based features. These features are organized as a tree structure and are fed into a boosting-based classification algorithm. The method consists of three parts: preprocessing (POS tagging, NE tagging, and parsing), feature extraction (contextual, syntactic, and wordbased features), and classification.
In this section, we describe the underlying idea of contextual features and how contextual features are used for detecting semantic relations.

Contextual Features
When a pair of NEs with a semantic relation appears in different sentences, the antecedent NE must be contextually easily referred to in the sentence with the following NE. In the following Japanese example, the pair "Ken 22 " and "amerika 32 (the U.S.)" have a semantic relation "wataru 33 (go)", because "Ken 22 " is contextually referred to in the sentence with "amerika 32 " (In fact, the zero pronoun φ i refers to "Ken 22 "). Meanwhile, the pair "Naomi 25 " and "amerika 32 " has no semantic relation, because the sentence with "amerika 32 " does not refer to "Naomi 25 ".
(S-2) asu 21 , Ken 22 -wa Osaka 23 -o otozure 24 Naomi 25 -to au 26 . (Ken22 is going to visit24 Osaka23 to see26 Tom 34 -to ryoko 35 suru. (Then31, (hei) will go33 to the U.S.32 to travel35 with Tom34.) Furthermore, when a pair of NEs with a semantic relation appears in a parallel sentence arise from predication ellipsis, the antecedent NE is contextually easily referred to in the phrase with the following NE. In the example of "(S-1)", the pair "Ken 11 " and "Tokyo 12 " have a semantic relation "umareta 15 (was born)". Meanwhile, the pair "Ken 11 " and "New York 14 " has no semantic relation. Therefore, using whether the antecedent NE is referred to in the context with the following NE as features of a given pair of NEs would improve relation detection performance. In this paper, we use centering theory (Kameyama, 1986) to determine how easily a noun phrase can be referred to in the following context.

Centering Theory
Centering theory is an empirical sorting rule used to identify the antecedents of (zero) pronouns. When there is a (zero) pronoun in the text, noun phrases that are in the previous context of the pronoun are sorted in order of likelihood of being the antecedent. The sorting algorithm has two steps. First, from the beginning of the text until the pronoun appears, noun phrases are stacked depending on case markers such as particles. In the above example, noun phrases, "asu 21 ", "Ken 22 ", "Osaka 23 " and "Naomi 25 ", which are in the previous context of the zero pronoun φ i , are stacked and then the information shown in Figure 1 is acquired. Second, the stacked information is sorted by the following rules.
1. The priority of case markers is as follows: "wa > ga > ni > o > others" 2. The priority of stack structure is as follows: last-in first-out, in the same case marker For example, Figure 1 is sorted by the above rules and then the order, 1: "Ken 22 ", 2: "Osaka 23 ", 3: "Naomi 25 ", 4: "asu 21 ", is assigned. In this way, using centering theory would show that the antecedent of the zero pronoun φ i is "Ken 22 ".

Applying Centering Theory
When detecting a semantic relation between a given pair of NEs, we use centering theory to determine how easily the antecedent NE can be referred to in the context with the following NE. Note that we do not explicitly execute anaphora resolutions here.
Applied centering theory to relation detection is as follows. First, from the beginning of the text until the following NE appears, noun phrases are stacked depending on case markers, and the stacked information is sorted by the above rules (Section 2.2). Then, if the top noun phrase in the sorted order is identical to the antecedent NE, the antecedent NE is "positive" when being referred to in the context with the following NE.
When the pair of NEs, "Ken 22 " and "amerika 32 ", is given in the above example, the noun phrases, "asu 21 ", "Ken 22 ", "Osaka 23 " and "Naomi 25 ", which are in the previous context of the following NE "amerika 32 ", are stacked (Figure 1). Then they are sorted by the above sorting rules and the order, 1: "Ken 22 ", 2: "Osaka 23 ", 3: "Naomi 25 ", 4: "asu 21 ", is acquired. Here, because the top noun phrase in the sorted order is identical to the antecedent NE, the antecedent NE "Ken 22 " is "positive" when be-158 ing referred to in the context with the following NE "amerika 32 ". Whether or not the antecedent NE is referred to in the context with the following NE is used as a feature. We call this feature Centering Top (CT).

Using Stack Structure
The sorting algorithm using centering theory tends to rank highly thoes words that easily become subjects. However, for relation detection, it is necessary to consider both NEs that easily become subjects, such as person and organization, and NEs that do not easily become subjects, such as location and time. We use the stack described in Section 2.3 as a structural feature for relation detection. We call this feature Centering Structure (CS). For example, the stacked information shown in Figure 1 is assumed to be structure information, as shown in Figure 2. The method of converting from a stack (Figure 1) into a structure (Figure 2) is described as follows. First, the following NE, "amerika 32 ", becomes the root node because Figure 1 is stacked information until the following NE appears. Then, the stacked information is converted to Figure 2 depending on the case markers. We use the path of the given pair of NEs in the structure as a feature. For example, "amerika 32 → wa:Ken 22 " 2 is used as the feature of the given pair "Ken 22 " and "amerika 32 ".

Classification Algorithm
There are several structure-based learning algorithms proposed so far (Collins and Duffy, 2001;Suzuki et al., 2003;Kudo and Matsumoto, 2004). The experiments tested Kudo and Matsumoto's boosting-based algorithm using sub trees as features, which is implemented as the BACT system.
In relation detection, given a set of training examples each of which represents contextual, syntactic, and word-based features of a pair of NEs as a tree labeled as either having semantic relations or not, the BACT system learns that a set of rules are effective in classifying. Then, given a test instance, which represents contextual, syntactic, and word-2 "A → B" means A has a dependency relation to B.  based features of a pair of NEs as a tree, the BACT system classifies using a set of learned rules.

Experiments
We experimented with texts from Japanese newspapers and weblogs to test the proposed method. The following four models were compared: 1. WD : Pairs of NEs within n words are detected as pairs with semantic relation. 2. STR : Supervised learning method using syntactic 3 and word-based features, the path of the pairs of NEs in the parse tree and the word ngram between pairs of NEs (Kambhatla, 2004) 3. STR-CT : STR with the centering top feature explained in Section 2.3. 4. STR-CS : STR with the centering structure feature explained in Section 2.4.

Setting
We used 1451 texts from Japanese newspapers and weblogs, whose semantic relations between person and location had been annotated by humans for the experiments 4 . There were 5110 pairs with semantic relations out of 236,142 pairs in the annotated text. We conducted ten-fold cross-validation over 236,142 pairs of NEs so that sets of pairs from a single text were not divided into the training and test sets.
We also divided pairs of NEs into two types: (A) intra-sentential and (B) inter-sentential. The reason for dividing them is so that syntactic structure features would be effective in type (A) and contextual features would be effective in type (B). Another reason is that the percentage of pairs with semantic relations out of the total pairs in the annotated text differ significantly between types, as shown in Table 1.
In the experiments, all features were automatically acquired using a Japanese morphological and dependency structure analyzer.

Results
To improve relation detection performance, we investigated the effect of the proposed method using contextual features. Table 2 shows results for Type (A), Type (B), and (A)+(B). We also plotted recallprecision curves 5 , altering threshold parameters, as shown in Figure 3. The comparison between STR and STR-CT and between STR and STR-CS in Figure 3 indicates that the proposed method effectively contributed to relation detection. In addition, the results for Type (A): intra-sentential, and (B): inter-sentential, in Table  2 indicate that the proposed method contributed to both Type (A), improving precision by about 4.5% and recall by about 5.4% and Type (B), improving precision by about 12.6% and recall by about 17.0%.

Error Analysis
Over 70% of the errors are covered by two major problems left in relation detection. Parallel sentence: The proposed method solves problems, which result from when a parallel sentence arises from predication ellipsis. However, there are several types of parallel sentence that differ from the one we explained. (For example, Ken and Tom was born in Osaka and New York, respectively.) 5 Precision = # of correctly detected pairs / # of detected pairs Recall = # of correctly detected pairs / # of pairs with semantic relations Definite anaphora: Definite noun phrase, such as "Shusho (the Prime Minister)" and "Shacho (the President)", can be anaphors. We should consider them in centering theory, but it is difficult to find them in Japanese .

Conclusion
In this paper, we propose a supervised learning method using words, syntactic structures, and contextual features based on centering theory, to improve both inter-sentential and inter-sentential relation detection. The experiments demonstrated that the proposed method increased precision by 4.4%, up to 73.7%, and increased recall by 6.7%, up to 56.8%, and thus contributed to relation detection.
In future work, we plan to solve the problems relating to parallel sentence and definite anaphora, and address the task of relation characterization.