Information Extraction over Structured Data:
Question Answering with Freebase

In answering our example query a person might take into consideration multiple constraints. With regards to the question, we know we are looking for the name of a person based on the following:

• •

  the dependency relation nsubj(what, name) and prep_of(name, brother) indicates that the question seeks the information of a name;⁴⁴We use the Stanford collapsed dependency form.

• •

  the dependency relation prep_of(name, brother) indicates that the name is about a brother (but we do not know whether it is a person name yet);

• •

  the dependency relation nn(brother, bieber) and the facts that, (i) Bieber is a person and (ii) a person’s brother should also be a person, indicate that the name is about a person.

This motivates the design of dependency-based features. We show one example in Figure 1(a), left side. The following linguistic information is of interest:

• •

  question word (qword), such as what/who/how many. We use a list of 9 common qwords. ⁵⁵who, when, what, where, how, which, why, whom, whose.

• •

  question focus (qfocus), a cue of expected answer types, such as name/money/time. We keep our analysis simple and do not use a question classifier, but simply extract the noun dependent of qword as qfocus.

• •

  question verb (qverb), such as is/play/take, extracted from the main verb of the question. Question verbs are also good hints of answer types. For instance, play is likely to be followed by an instrument, a movie or a sports team.

• •

  question topic (qtopic). The topic of the question helps us find relevant Freebase pages. We simply apply a named entity recognizer to find the question topic. Note that there can be more than one topic in the question.

Then we convert the dependency parse into a more generic question graph, in the following steps:

1. 1.

   if a node was tagged with a question feature, then replace this node with its question feature, e.g., what $\to$ qword=what;

2. 2.

   (special case) if a qtopic node was tagged as a named entity, then replace this node with its its named entity form, e.g., bieber $\to$ qtopic=person;

3. 3.

   drop any leaf node that is a determiner, preposition or punctuation.

The converted graph is shown in Figure 1(a), right side. We call this a question feature graph, with every node and relation a potential feature for this question. Then features are extracted in the following form: with $s$ the source and $t$ the target node, for every edge $e\left(s,t\right)$ in the graph, extract $s$, $t$, $s\mid t$ and $s\mid e\mid t$ as features. For the edge, prep_of(qfocus=name, brother), this would mean the following features: qfocus=name, brother, qfocus=name$\mathrm{\mid }$brother, and qfocus=name$\mathrm{\mid }$prep_of$\mathrm{\mid }$brother.

We show with examples why these features make sense later in $\mathrm{\S }$6 Table 6. Furthermore, the reason that we have kept some lexical features, such as brother, is that we hope to learn from training a high correlation between brother and some Freebase relations and properties (such as sibling and male) if we do not possess an external resource to help us identify such a correlation.

Given a topic, we selectively roll out the Freebase graph by choosing those nodes within a few hops of relationship to the topic node, and form a topic graph. Besides incoming and/or outgoing relationships, nodes also have properties: a string that describes the attribute of a node, for instance, node type, gender or height (for a person). One major difference between relations and properties is that both arguments of a relation are nodes, while only one argument of a property is a node, the other a string. Arguments of relations are usually interconnected, e.g., London can be the place_of_birth for Justin Bieber, or capital_of the UK. Arguments of properties are attributes that are only “attached” to certain nodes and have no outgoing edges. Figure 1(b) shows an example.

Both relationship and property of a node are important to identifying the answer. They connect the nodes with the question and describe some unique characteristics. For instance, without the properties type:person and gender:male, we would not have known the node Jaxon Bieber represents a male person. These properties, along with the sibling relationship to the topic node, are important cues for answering the question. Thus for the Freebase graph, we use relations (with directions) and properties as features for each node.

Additionally, we have analyzed how Freebase relations map back to the question. Some of the mapping can be simply detected as paraphrasing or lexical overlap. For example, the person.parents relationship helps answering questions about parenthood. However, most Freebase relations are framed in a way that is not commonly addressed in natural language questions. For instance, for common celebrity gossip questions like who cheated on celebrity A, it is hard for a system to find the Freebase relation celebrity.infidelity.participant as the target relation if it had not observed this pattern in training.

Thus assuming there is an alignment model that is able to tell how likely one relation maps to the original question, we add extra alignment-based features for the incoming and outgoing relation of each node. Specifically, for each relation $rel$ in a topic graph, we compute $P(rel\mid question)$ to rank the relations. Finally the ranking (e.g., top 1/2/5/10/100 and beyond) of each relation is used as features instead of a pure probability. We describe such an alignment model in $\mathrm{\S }$ 5.

We combine question features and Freebase features (per node) by doing a pairwise concatenation. In this way we hope to capture the association between question patterns and answer nodes. For instance, in a loglinear model setting, we expect to learn a high feature weight for features like:

qfocus=money$\mathrm{|}$node_type=currency

and a very low weight for:

qfocus=money$\mathrm{|}$node_type=person.

This combination greatly enlarges the total number of features, but owing to progress in large-scale machine learning such feature spaces are less of a concern than they once were (concrete numbers in $\mathrm{\S }$ 6 Model Tuning).

The objective is to find the most likely relation a question prompts. For instance, for the question who is the father of King George VI, the most likely relation we look for is people.person.parents. To put it more formally, given a question $Q$ of a word vector $𝐰$, we want to find out the relation $R$ that maximizes the probability $P(R\mid Q)$.

More interestingly, for the question who is the father of the Periodic Table, the actual relation that encodes its original meaning is law.invention.inventor, rather than people.person.parents. This simple example points out that every part of the question could change what the question inquires eventually. Thus we need to count for each word $w$ in $Q$. Due to the bias and incompleteness of any data source, we approximate the true probability of $P$ with $\tilde{P}$ under our specific model. For the simplicity of computation, we assume conditional independence between words and apply Naive Bayes:

where $\tilde{P}\left(R\right)$ is the prior probability of a relation $R$ and $\tilde{P}(w\mid R)$ is the conditional probability of word $w$ given $R$.

It is possible that we do not observe a certain relation $R$ when computing the above equation. In this case we back off to the “sub-relations”: a relation $R$ is a concatenation of a series of sub-relations $R=𝐫=r_1.r_2.r_3.\mathrm{\dots }$. For instance, the sub-relations of people.person.parents are people, person, and parents. Again, we assume conditional independence between sub-relations and apply Naive Bayes:

One other reason that we estimated $\tilde{P}(w\mid r)$ and $\tilde{P}\left(r\right)$ for sub-relations is that Freebase relations share some common structures in between them. For instance, both people.person.parents and fictional_universe.fictional_character.parents indicate the parent relationship but the latter is much less commonly annotated. We hope that the shared sub-relation, parents, can help better estimate for the less annotated. Note that the backoff model would have a much smaller value than the original, due to double multiplication ${\prod }_r{\prod }_w$. In practice we normalize it by the sub-relations size to keep it at the same scale with $\tilde{P}(R\mid Q)$.

Finally, to estimate the prior and conditional probability, we need a massive data collection.

The ClueWeb09⁶⁶http://lemurproject.org/clueweb09/ dataset is a collection of 1 billion webpages (5TB compressed in raw html) in 10 languages by Carnegie Mellon University in 2009. FACC1, the Freebase Annotation of the ClueWeb Corpus version 1 [15], contains index and offset of Freebase entities within the English portion of ClueWeb. Out of all 500 million English documents, 340 million were automatically annotated with at least one entity, with an average of 15 entity mentions per document. The precision and recall of annotation were estimated at $80-85\mathrm{\%}$ and $70-85\mathrm{\%}$ [32].

Given these two resources, for each binary Freebase relation, we can find a collection of sentences each of which contains both of its arguments, then simply learn how words in these sentences are associated with this relation, i.e., $\tilde{P}(w\mid R)$ and $\tilde{P}(w\mid r)$. By counting how many times each relation $R$ was annotated, we can estimate $\tilde{P}\left(R\right)$ and $\tilde{P}\left(r\right)$. The learning task can be framed in the following short steps:

1. 1.

   We split each html document by sentences [21] using NLTK [3] and extracted those with at least two Freebase entities which has at least one direct established relation according to Freebase.

2. 2.

   The extraction formed two parallel corpora, one with “relation - sentence” pairs (for estimating $\tilde{P}(w\mid R)$ and $\tilde{P}\left(R\right)$) and the other with “subrelations - sentence” pairs (for $\tilde{P}(w\mid r)$ and $\tilde{P}\left(r\right)$). Each corpus has 1.2 billion pairs.

3. 3.

   The tricky part was to align these 1.2 billion pairs. Since the relations on one side of these pairs are not natural sentences, we ran the most simple IBM alignment Model 1 [5] to estimate the translation probability with GIZA++ [30]. To speed up, the 1.2 billion pairs were split into 100 even chunks. We ran 5 iterations of EM on each one and finally aligned the 1.2 billion pairs from both directions. To symmetrize the alignment, common MT heuristics intersection, union, grow-diag-final, and grow-diag-final-and [22] were separately applied and evaluated later.

4. 4.

   Treating the aligned pairs as observation, the co-occurrence matrix between aligning relations and words was computed. There were 10,484 relations and sub-relations in all, and we kept the top 20,000 words.

5. 5.

   From the co-occurrence matrix we computed $\tilde{P}(w\mid R)$, $\tilde{P}\left(R\right)$, $\tilde{P}(w\mid r)$ and $\tilde{P}\left(r\right)$.

Hand-checking the learned probabilities shows both success, failure and some bias. For instance, for the film.actor.film relation (mapping from film names to actor names), the top words given by $\tilde{P}(w\mid R)$ are won, star, among, show. For the film.film.directed_by relation, some important stop words that could indicate this relation, such as by and with, rank directly after director and direct. However, due to significant popular interest in certain news categories, and the resultant catering by websites to those information desires, then for example we also learned a heavily correlated connection between Jennifer Aniston and celebrity.infidelity.victim, and between some other you-know-who names and celebrity.infidelity.participant.

We next formally evaluate how the learned mapping help predict relations from words.

Both ClueWeb and its Freebase annotation has a bias. Thus we were firstly interested in the coverage of mined relation mappings. As a comparison, we used a dataset of relation mapping contributed by Berant et al. (2013) and Lin and Etzioni (2012). The idea is very similar: they intersected Freebase relations with predicates in (arg1, predicate, arg2) triples extracted from ReVerb to learn the mapping between Freebase relations and triple predicates. Note the scale difference: although ReVerb was also extracted from ClueWeb09, there were only 15 million triples to intersect with the relations, while we had 1.2 billion alignment pairs. We call this dataset ReverbMapping and ours CluewebMapping.

The evaluation dataset, WebQuestions, was also contributed by Berant et al. (2013). It contains 3778 training and 2032 test questions collected from the Google Suggest service. All questions were annotated with answers from Freebase. Some questions have more than one answer, such as what to see near sedona arizona?.

We evaluated on the training set in two aspects: coverage and prediction performance. We define answer node as the node that is the answer and answer relation as the relation from the answer node to its direct parent. Then we computed how much and how well the answer relation was triggered by ReverbMapping and CluewebMapping. Thus for the question, who is the father of King George VI, we ask two questions: does the mapping, 1. (coverage) contain the answer relation people.person.parents? 2. (precision) predict the answer relation from the question?

Table 1 shows the coverage of CluewebMapping, which covers $93.0\mathrm{\%}$ of all answer relations. Among them, we were able to learn the rule mapping using more than 10 thousand relation-sentence pairs for each of the $89.5\mathrm{\%}$ of all answer relations. In contrast, ReverbMapping covers $89.7\mathrm{\%}$ of the answer relations.

Next we evaluated the prediction performance, using the evaluation metrics of information retrieval. For each question, we extracted all relations in its corresponding topic graph, and ranked each relation with whether it is the answer relation. For instance, for the previous example question, we want to rank the relation people.person.parents as number 1. We computed standard MAP (Mean Average Precision) and MRR (Mean Reciprocal Rank), shown in Table 2(a). As a simple baseline, “word overlap” counts the overlap between relations and the question. CluewebMapping ranks each relation by $\tilde{P}(R\mid Q)$. ReverbMapping does the same, except that we took a uniform distribution on $\tilde{P}(w\mid R)$ and $\tilde{P}\left(R\right)$ since the contributed dataset did not include co-occurrence counts to estimate these probabilities.⁷⁷The way we used ReverbMapping was not how Berant et al. (2013) originally used it: they employed a discriminative log-linear model to judge relations and that might yield better performance. As a fair comparison, ranking of CluewebMapping under uniform distribution is also included in Table 2(a). Note that the median rank from CluewebMapping is only 12, indicating that half of all answer relations are ranked in the top 12.

Table 2(b) further shows the percentage of answer relations with respect to their ranking. CluewebMapping successfully ranked $19\mathrm{\%}$ of answer relations as top 1. A sample of these includes person.place_of_birth, location.containedby, country.currency_used, regular_tv_appearance.actor, etc. These percentage numbers are good clue for feature design: for instance, we may be confident in a relation if it is ranked top 5 or 10 by CluewebMapping.

To conclude, we found that CluewebMapping provides satisfying coverage on the 3778 training questions: only $7\mathrm{\%}$ were missing, despite the biased nature of web data. Also, CluewebMapping gives reasonably good precision on its prediction, despite the noisy nature of web data. We move on to fully evaluate the final QA $F_1$.