# Enriching Knowledge Base by Parse Tree Pattern and Semantic Filter
## 4 Pattern Generation  
### Generation of Pattern Candidates  
The first step of knowledge base enrichment is to harvest pattern candidates for each relation in the seed knowledge base. As an expression of patterns, current successful systems such as BOA and NELL utilize the lexical information in a sentence. This lexical pattern consists of intervening words between two entities within a seed triple and is assumed to deliver the meaning of the relation of the seed triple. However, this assumption is often untrue. There could be very many sentences on the web that produce irrelevant patterns. In order to overcome the problem of lexical patterns, we adopt dependency information within a sentence in harvesting pattern candidates. Dependency information provides the relations between predicates and their arguments in a sentence. As a way to utilize dependency information of a sentence as a pattern, our pattern is represented as a subtree of the parse tree of the sentence. A natural language parser is required to transform a sentence into a parse tree. We adopt the Stanford dependency parser [34] as a parser. Since prepositions and conjunctions are functional words, it is better to represent them as dependencies rather than as tree nodes. The Stanford dependency parser provides a collapsed representation of parse trees that represents functional words as dependencies. Thus, we use the collapsed representation for parse trees. Parse tree pattern candidates are generated by Algorithm 1. Assume that a seed triple \(\langle e_{1},r,e_{2}\rangle\) and a sentence \(s\) which contains \(e_{1}\) and \(e_{2}\) are given as an input. The sentence \(s\) is parsed into a parse tree \(t\) by a dependency parser. Then, the nodes in the parse tree that correspond to \(e_{1}\) and \(e_{2}\) are identified first, and let \(n_{1}\) and \(n_{2}\) be the corresponding nodes. Once \(n_{1}\) and \(n_{2}\) are identified, the pattern candidate \(p\) for the relation \(r\) is generated by a function \(\textit{subtree\_extract}\). This function returns, from \(t\), the smallest subtree subsumed by \(n_{1}\), \(n_{2}\), and their lowest-common-ancestor, where the lowest-common-ancestor becomes the root node of the subtree. For instance, let us consider the dependency parse tree of a sentence \"_[PERSON] is a daughter of [PERSON] and [PERSON]_\" Figure 2a is the parse tree of the sentence. When a seed triple is \(\langle\textit{[PERSON]},\textit{childOf},\textit{[PERSON]}\rangle\), \(n_{1}\) and \(n_{2}\) are the node of '_[PERSON]_' and '_[PERSON]_', respectively. In the parse tree, the lowest-common-ancestor node of \(n_{1}\) and \(n_{2}\) is the node of '_daughter_'. Thus, the pattern for the relation \(\textit{childOf}\) from this sentence is the smallest subtree  
Figure 1: Overall structure of the proposed knowledge enrichment. composed by \(n_{1}\), \(n_{2}\), and their lowest-common-ancestor given in Figure 2b. As another example, assume that a seed triple \(\langle\mathit{[PERSON]},\mathit{spouseOf},\mathit{[PERSON]}\rangle\) is given. A parse tree in Figure 2c is generated as a pattern from the same sentence. Note that the word _'daughter'_ appears in the pattern, even though it is not located between _'[PERSON]'_ and _'[PERSON]'_ in the sentence. ```
Input :an seed triple \(\langle e_{1},r,e_{2}\rangle\), a sentence \(s\) Output :a pattern candidate \(p\) \(t\gets parser(s)\) \(n_{1}\gets t(e_{1})\) \(n_{2}\gets t(e_{2})\) \(p\gets subtree\_extract(t,n_{1},n_{2})\) Return \(p\)
```  
**Algorithm 1**Pattern Candidate Generator  
The pattern candidates generated are not always correct. This is because the pattern candidates are generated by matching only entities. For instance, assume a new sentence _\"[PERSON] works for [PERSON]'s company, SCINet.\"_ The parse tree of this sentence is drawn in Figure 3a. Since both entities of a seed triple \(\langle\mathit{[PERSON]},\mathit{childOf},\mathit{[PERSON]}\rangle\) match this sentence, a new pattern candidate is generated from the parse tree as shown in Figure 3b.