We present a question answering system (Xser) over Linked Data(DBpedia), converting users' natural language questions into structured queries. There are two challenges involved: recognizing users' query intention and mapping the involved semantic items against a given knowledge base (KB), which will be in turn assembled into a structured query. In this paper, we propose an e cient pipeline framework to model a user's query intention as a phrase level dependency DAG which is then instantiated according to a given KB to construct the nal structured query. We evaluate our approach on the QALD-4 test dataset and achieve an F-measure score of 0.72, an average precision of 0.72 and an average recall of 0.71 over 50 questions.
As very large structured knowledge bases have become available, e.g.,YAGO [10], DBpedia [16] and Freebase[15], answering natural language questions over structured knowledge facts has attracted increasing research e orts, in both natural language processing and information retrieval communities. Di erent from keyword based retrieval, the structure of query intentions embedde in a user's question can be represented by a set of predicate-argument structures, e.g., <subject, predicate, object > triples, and e ectively retrieved by a structured query engine from a given knowledge base. Generally, the main challenge of understanding the query intention in a structural form is to solve two tasks: recognizing the predicate-argument structures and then instantiating these structures regarding a given KB.
Intuitively, the two subtasks would be solved in a joint framework, e.g., [22] proposed a PCFG-based semantic parser to simultaneously learn the combination rules among words or phrases and the mappings to speci c KB components. However, given the size of existing KBs (usually thousands of predicates, millions of entities and billions of knowledge facts), it makes di cult to jointly train such a PCFG-based parser (the model of [22] takes several days to train with [which] [country] did [france] [colonise] variable category entity relation
PO
SC SP [which]v [country]c did [france]E [colonise]R phrase detecting
parsing instanting
PO
SC SP [which]v [country]c did [france]E [colonise]R ?x fb:location.country fb:en.france fb:colonise select ?x where { } ?x fb:object.type fb:location.country
fb:en.france fb:colonise ?x 3,000 sentences), and even more di cult to adapt to other KBs, let alone retrieving multiple KBs within one query, e.g., some queries in the QALD task[17] are mixed with predicates from both DBpedia and Yago. In contrast, we nd that recognizing the query intention structure is usually KB-independent. Take Figure 1 as an example, without grounding to a knowledge base, we can still guess that a location called france has some relationship, indicated by the verb \colonise", with some countries, (the queried objects), which can be learned directly without reliance on a speci ed KB. On the other hand, the task of mapping semantic phrases from the intention structures to items in a given KB and producing the nal structured queries is KB-dependent, since one has to solve these mappings according to the schema of a speci ed KB.
Given the observations above, we thus assume that the structure of a question's query intention can be learned independent from a speci c knowledge base, while grounding and converting a query intention into a structured query is dependent on a knowledge base. Our assumption will naturally lead to a pipeline paradigm to translating a natural language question into a structured query, which can then be directly retrieved by a structured database query engine, e.g., Virtuoso 1.
In this paper, we deal with the task of understanding natural language questions in a pipeline paradigm, involving mainly two steps: recognizing the query intention structure inherent in the natural language questions, and then instantiating the query intention structures by mapping the involved semantic items into existing KBs. In the rst phase, we build a phrase detector to detect possible 1 http://www.virtuoso.com semantic phrases, e.g., variables, entity phrases, category phrases and relation phrases. We then develop a semantic parser to predict the predicate-argument structures among phrases to represent the structure of query intentions. In the second phase, given the intention structures, we are then able to adopt a structured perceptron model to jointly solve the mappings between semantic phrases and KB items. By taking a two-phase format, our proposed model can bene t from the separation of KB related components and KB independent steps, and recognize the intention structures more e ciently while making the KB-related component exible, e.g., we can only retrain the second phase when adapting to new KBs, which is similar in sprite with [23], who rely on a CCG parser to produce an ontological-independent logical representation to express users' intention. We evaluate our model on the QALD-4, and achieve an F-measure score of 0.72, an average precision of 0.72 and an average recall of 0.71 over 50 questions. 2
We de ne the task of using a KB to answer natural language questions as follows: given a natural language question qNL and a knowledge base KB, our goal is to translate qNL into a structured query in certain structured query language, e.g., SPARQL, which consists of multiple triples: a conjunction of <subject, predicate, object> search conditions. 3
Recognizing the Structure of Query Intention Our framework rst employ a pipeline of phrase detection and phrasal semantic parsing to recognize the inherent structure of user's query intention, and then instantiates the query intention regarding speci c KBs. 3.1
Before recognizing the query intentions of questions, we rst detect phrases of interest from the questions that potentially correspond to semantic items. where a detected phrase is also assigned with a semantic label l 2 fentity; relation; category; variableg. For entity phrases, we need to recognize phrases that may correspond to entities of the KB. Similarity, relation phrases may correspond to KB's predicates, and category phrases may be mapped in KB's classes. This problem can be casted as a sequence labeling problem, where our goal is to build a tagger whose input is a sentence, for example:
V W ho has T om Cruise been married to
B none E B E I none R B R
I (here, we use B-I scheme for each phrase label: R-B represents the beginning of a relation phrase, R-I represents the continuation of a relation phrase). We use structured perceptron[3] to build our phrase tagger. Structured perceptron is an extension to the standard linear perceptron for structured prediction. Given a question instance x 2 X, which in our case is a sentence, the structured perceptron involves the following decoding problem which nds the best con guration z 2 Y , which in our case is a label sequence, according to the current model w: z = arg max w f (x; y0)
y02Y (x) where f (x; y0) represents the feature vector for instance x along with con guration y0. We observe that many phrases of a speci c semantic label may share similar POS tag sequence pattern and NER sequence pattern. For example, the POS tag sequences of relation phrases \the area of " and \the population in" are in the same pattern \DT NN IN ". Therefore, we use three types of features: lexical features, POS tag features and NER features. Table 1 summarizes the feature templates we used in the phrase detection. p = pos tag; n = ner tag; w = word; t = phrase type tag; i = current index 1 unigram of POS tag pi 2 bigram of POS tag pipi+1; pi 1pi 3 trigram of POS tag pipi+1pi+2; pi 1pipi+1; pi 2pi 1pi 4 unigram of NER tag ni 5 bigram of NER tag nini+1; ni 1ni 6 trigram of NER tag nini+1ni+2; ni 1nini+1; ni 2ni 1ni
As shown in Figure 1, query intention can be represented by dependencies between \country ", \france" and \colonise", forming a phrase DAG, we thus introduce a transition-based DAG parsing algorithm to perform a structural prediction process and reveal the inherent structures.
Phrase DAG In dependency grammar, structures are determined by the relationship between a head and its dependents, e.g., syntactic or morphological dependencies. Here, we propose to use predicate-argument dependencies to capture the query intention, that is, the arguments of a predicate are dependents of that predicate. Each predicate is either a unary predicate (which characterizes
SP PO
SP PO In [what]v [year]C did [harry potter and the goblet of fire]E
[win]R the [hugo award for best novel]E fb:time.month fb:time.day_of_year fb:time.event fb:time.year ...
fb:m.02hm249 fb:m.05q1cnk fb:m.0dplz5f fb:m.08vs8qm fb:m.031786 ...
fb:sports.sports_team.championships fb:award.award_winning_work.award s_won..award.award_honor.award ...
Phrase DAG
fb:m.04p4lvx
fb:m.04p3_v_
fb:m.0l_v4kd
fb:m.0gbwdzs
fb:m.0gbwgrp
fb:m.01yz0x
...
candidates for all phrases and the underlined are the gold-standard mappings.)
(
Current arcs:
(
Current arcs:
(
Current arcs:
(
Current arcs:
B A B A B A C A Input phrases Input phrases Input phrases Input phrases
C B C B C B D B Desired output A Initial state Stack
B Current arcs:
D C D C D C C
Input phrases A A C D D D D
B B
D
C
C
(
Stack
B
(
Stack C B
Current arcs:
(
Current arcs:
(
Stack C B Stack D C B Current arcs:
D D D A D A A C Input phrases
D Input phrases Input phrases Input phrases
B B B
C C
C Current arcs:
A
B
C
D D D D its only argument) or a binary predicate (which represents the semantic relation between its two arguments). Here, category phrases correspond to unary predicates, and relation phrases correspond to binary predicates.
We formulate the problem of recognizing the dependency structures in a phrase level: the detected phrases in a question form the nodes of the phrase dependency DAG, with four types, variable, entity, relation, and category nodes, where the former two are referred as content nodes in the following. We draw a directed edge from the head to its dependent, indicating the predicate-argument or argument-argument relationship. The Phrase DAG Parsing Note that, in our setup, one phrase can have more than one head, as in Figure 2, variable node what has two heads in the resulting dependency DAG. We thus use the framework proposed by [2], i.e., extending traditional arc-eager shift-reduce parsing with multiple heads to nd a DAG directly. Speci cally, given a question with sequence of phrases, our parser uses a stack of partial DAGs, a queue of incoming phrases, and a series of actions to build a dependency DAG. We assume that each input phrase has been assigned a POS-tag (conjunction of each token's POS-tag which composes of the input phrase) and a semantic label.
Our semantic parser uses four actions: SHIFT, REDUCE, ARCRIGHT and ARCLEFT (Table 2).
The SHIFT action follow the standard de nitions that just pushes the next
incoming phrase onto the stack, as shown in Figure 3 action(
The REDUCE action pops the stack top, as shown in gure 3 action(
The ARCRIGHT action adds a dependency edge from the stack top to the
rst phrase of the incoming queue, where the phrase on the stack is the head
and the phrase in the queue is the dependent (the stack and queue are left
untouched), as long as a left arc does not already exist between these two phrases,
as shown in Figure 3 action(
The ARCLEFT action adds a dependency edge from the rst phrase on the
queue to the stack top, where the phrase in the queue is the head and the phrase
on the stack is the dependent (again, the stack and queue are left untouched),
as long as a right arc does not already exist between the two phrases, as shown
in Figure 3 action(
Figure 3 shows an example of shift-reduce parsing process.
The decoding algorithm for phrase DAG parsing We apply the standard beam-search along with early-update to perform inexact decoding [9] during training. To formulate the decoding algorithm, we de ne a candidate item as a tuple hS; Q; F i, where S represents the stack with partial derivations that have been built, Q represents the queue of incoming phrases that have not been processed, and F is a boolean value that represents whether the candidate item has been nished. A candidate item is nished if and only if the queue is empty, and no more actions can be applied to a candidate item after it reaches the nished status. Given an input sentence x, we de ne the start item as the un nished item with an empty stack and the whole input sentence as the incoming phrases(line 2). A derivation is built from the start item by repeated applications of actions (SHIFT, REDUCE, ARCLEFT and ARCRIGHT) until the item is nished.
To apply beam-search, an agenda is used to hold the K-best partial (un nished) candidate items at each parsing step. A separate candidate output is used to record the current best nished item that has been found, since candidate items can be nished at di erent steps. Initially the agenda contains only the start item, and the candidate output is set to none(line 3). At each step during parsing, each candidate item from the agenda is extended in all possible ways by applying one action according to the current status(line 7), and a number of new candidate items are generated(line 8). If a newly generated candidate is nished, it is compared with the current candidate output. If the candidate output is none or the score of the newly generated candidate is higher than the score of the candidate output, the candidate output is replaced with the newly generated item(line 11); otherwise the newly generated item is discarded (line 14). If the newly generated candidate is un nished, it is appended to a list of newly generated partial candidates. After all candidate items from the agenda have been processed, the agenda is cleared(line 18) and the K-best items from the list are put on the agenda(line 19). Then the list is cleared and the parser moves on to the next step. This process repeats until the agenda is empty (which means that no new items have been generated in the previous step), and the candidate output is the nal derivation. Pseudocode for the decoding algorithm is shown in Algorithm 1. Features Features play an important role in transition-based parsing. Our parser takes three types of features: lexical, semantic and structure-related features. We summarize our feature templates in Table 3, where ST represents the top node in the stack, N0, N1, N2 represent the three incoming phrases from the incoming queue, subscript t indicates POS tags, subscript p indicates lexical surface forms and subscript s represent the semantic label of the phrase(entity,relation, category and variable).
Lexical features include features used in traditional word level dependency parsing with some modi cations: all co-occurrences are built on phrase nodes and the POS tag of a phrase is de ned as the concatenation of each token's POS tag in the phrase.
Note that ARCLEFT and ARCRIGHT actions are considered only when the top phrase of the stack and the next phrase are variable, entity or relation phrases.To guide the ARCLEFT and ARCRIGHT actions, we introduce semantic features indicating the semantic label of a phrase.
Recall that, our phrase semantic DAG parser allows one phrase to have multiple heads. Therefore, we modify the ARCLEFT and ARCRIGHT actions so that they can create new dependency arcs without removing the dependent from further consideration for being a dependent of other heads. We thus introduce new structure-related features to indicate whether an arc already exists between the top phrase on the stack and the next phrase on the queue. 4
Instantiating Query Intention Regarding Existing KBs After recognizing the structure of the user's query intention, our parser can output a KB-independent phrase dependency DAG, as shown in Figure 2. To covert the the query intention into structured queries, semantic items are grounded to a speci c KB, e.g., DBpedia. In experiment, we utilize di erent methods to maintain the candidate sets for di erent types of phrases.
For the entity phrase, we rst employ the wikipedia miner tool2 to map the phrase to wikipedia entities, and then generate the candidate set of DBpedia entities which share the same wikipedia ids with wikipedia entities.
For the relation and category phrase, we use the PATTY resource to construct a lexicon that maps phrases to predicates and categories of DBpedia.
Note that, a nice paradigm will be jointly resolving the mappings of all semantic items involved: labeling phrase nodes and the dependency relations with corresponding items in the given KB. Therefore, inspired by [21], we formulate this problem as a structured learning task, where we choose a candidate for each phrase and dependency relation, and nd a globally maximum con guration among multiple local candidates.
For the dependency relation candidates especially for that between two content phrases, we develop a function getDepRel to retrieve the possible dependency relation candidates which are coherent with the domain of the phrases in the question from the set of all KB predicates. 2 http://wikipedia-miner.cms.waikato.ac.nz/ Algorithm 2 The decoding algorithm to instantiate the query intention structures Require: Instance x =< (x1; x2; : : : ; xm); ; o > and the oracle output y if for training.
[ f?g: phrase candidates.
[ f?; SP; P O; SCg: dependency relation candidates.
Ensure: 1-best prediction z for x 1: Set beam ["] //empty con guration 2: for all i 1::m do 3: buf fz0 ljz0 2 B; l 2 [ f?gg //phrase labeling 4: B K-best(buf ) 5: if y1:(i 1) m+1 2= B then 6: return B[0] //for early update 7: end if 8: for all (xk; ) 2 do 9: /* search for dependent relation*/ 10: buf ; 11: for all z0 2 B do 12: buf buf [ fz0 ?g 13: if dep(i; k; ) 2 o then 14: //this dependency from phrase i to phrase k 15: //exists in the DAG structures 16: /*dependency relation labeling*/ 17: buf buf [ fz0 rjr 2 getDepRel( ; z0) [ SP [ P O [ SC[ ?g 18: end if 19: end for 20: B K-best(buf ) 21: if y1:i k 2= B then 22: return B[0] // for early update 23: end if 24: end for 25: end for 4.1
As shown in Figure 2, each phrase and dependency relation have multiple
candidates and the best con guration is consisted of the blue and underlined
candidates. However, it is intractable to perform exact search in our framework
because: (
To address this problem, we apply beam-search along with early-update strategy to perform inexact decoding. 4.2
Here we introduce the label sets for phrase node and dependency relation in the model. We use [ f?g to denote the phrase candidates, and ? indicates that the phrase node can not be mapped to an entity or a predicate of the KB. Similarly, [ fSP; P O; SC; ?g denotes the dependency relation candidates, where is the set of all KB predicates, SP and PO are the two labels representing the dependency relation between relation phrase and entity phrase, where SP indicates that the entity phrase is the subject of the relation phrase, and PO indicates the other way. SC is the label representing the dependency relation between content phrase and category phrase, where the category phrase characterized the content phrase. and ? means that this dependency relation can not be instantiated. 4.3
Let x =< (x1; x2; : : : ; xm); ; o > denote the sentence instance, where xi represents the i-th phrase in the sentence, = ff(xk; ci)gis=1gkm=1 is the set of KB item candidates for phrases where s denotes the size of candidates for xk, and o = ffdepl(i; j; ci)gid=1gl=1 is the set of KB predicate candidates for dependency n relations where i and j denotes the head and dependent index, d denotes the size of candidates for the dependency relation. We use
y = (t1; a1;1; : : : ; a1;m; : : : ; tm; am;1; : : : ; am;m) to denote the corresponding gold standard structure, where ti represents the KB item assignment for the phrase xi, and ai;k represents KB item assignment for the dependency relation between the head xi and dependent xk. Algorithm 2 describes the beam-search procedure with early-update. During each step with phrase i, there are two sub-steps: Phrase labeling We enumerate all possible KB item candidates for the current phrase(line 3). K-best partial con gurations are selected to the beam(line 4), assuming the beam size is K.
Dependency relation labeling After the phrase labeling step, we traverse all con gurations in the beam. Once a phrase candidate for xi is found in the beam, the decoder searches through the dependency relation candidates o to label each dependency relation where the current phrase as the head and xi as the dependent(line11-19). After labeling each dependency relation, we again score each partial assignment and select the K-best results to the beam(line 20).
Note that, the score of a con guration is indeed the sum of two scores from each sub-step. Therefore the resulting best con guration will jointly solve the phrase and dependency relation labeling. We use two types of features: local features and global features. Table 4 summarize these features.
After instantiating the query intention, our system outputs a phrasal semantic DAG regarding KB. We convert the DAG into structured queries, e.g., SPARQL, mainly by the rules shown in Figure 4, where e1 and e2 represent entity phrases, r denotes a relation phrase and c denotes a category phrase. The left is the graph pattern which may occur in the semantic DAG, and the right is the query triple converted from the pattern. Note that, multiple graph patterns may occur in a semantic DAG, as shown in Figure 3. The nal structured queries are the conjunction of query triples converted from DAG. 5.1
We use the Free917 dataset [6] as our training data, which contains 917 questions annotated with logical forms. Recall that, in our model, we require gold-standard phrase dependency DAGs of these questions as our training data, which we prepare as follows. For each question, we nd its variable, entity, category and relation phrases, manually annotate the question with phrase dependency DAG and map phrases and dependencies to Freebase semantic items.
The QALD-4 task for question answering over linked data consists of 50 test questions. We use these 50 questions as our test data and directly use the parser trained on Free917 to predict the query intention and instantiate the query intention regarding DBpedia. The following table gives the evaluation results with average precision, average recall and F-measure. It shows the number of question our system can answer, the number of right and partially right answers among them. We notice that in many cases our system can be further improved. For example, in the question from QALD4 \what is the bridge with the longest span", our system incorrectly detects \the longest span" as a category phrase, while this phrase is certainly a relation phrase. This detection error is propagated to phrasal semantic parsing. A necessary direction for our future step should be jointly solve phrase detection and phrasal semantic DAG parsing to avoid such errors. 6
In this paper, we propose a novel framework to translate natural language questions into structural queries, which can be e ectively retrieved by structured query engines and return the answers according a KB. The novelty of our framework lies in modeling the task in a KB-independent and KB-related pipeline paradigm, where we use phrasal semantic DAG to represent users' query intention, and develop a KB-independent shift-reduce DAG parser to capture the structure of the query intentions, which are then grounded to a given KB via joint mappings. This gives the advantages to analyze the questions independent from a KB and easily adapt to new KBs without much human involvement.
Currently, our model requires question-DAG pairs as the training data, though we do not need to annotate new data for every datasets or KBs, it is still promising to extend our model to train on question-answer pairs only, further saving human involvement. Secondly, in the pipeline of phrase detection and phrasal semantic parsing, error propagated from the upstream to downstream. A joint model with multiple perceptrons may help to eliminate the error propagation.