We present a question answering system (CASIA@V2) over Linked Data (DBpedia), which translates natural language questions into structured queries automatically. Existing systems usually adopt a pipeline framework, which contains four major steps: 1) Decomposing the question and detecting candidate phrases; 2) mapping the detected phrases into semantic items of Linked Data; 3) grouping the mapped semantic items into semantic triples; and 4) generating the rightful SPARQL query. We present a jointly learning framework using Markov Logic Network(MLN) for phrase detection, phrases mapping to semantic items and semantic items grouping. We formulate the knowledge for resolving the ambiguities in three steps of QALD as first-order logic clauses in a MLN. We evaluate our approach on QALD-4 test dataset and achieve an F-measure score of 0.36, an average precision of 0.32 and an average recall of 0.40 over 50 questions.
With the rapid development of the Web of Data, there are many RDF datasets
published as Linked Data [
Question answering over Linked Data [
Lopez et al. [
This paper proposes a novel algorithm based on a learning framework, Markov
Logic Network (MLN) [
We evaluate our approach on QALD-4 test dataset and achieve an F-measure score of 0.36, an average precision of 0.32 and an average recall of 0.40 over 50 questions. 2
The current version of our QA system is not designed to answer the questions which contain numbers, date comparisons and aggregation operations such as group by or order by. We also do not consider the questions which contain filter condition. Figure 1 prefixes in semantic items indicate the source of its vocabularies, dbr indicate entity and dbo indicate class and property defined in the DBpedia ontology (http://wiki.dbpedia.org/Ontology39). 1 shows the architecture of our system to translate a question into a formal SPARQL query.
At first, sequence of tokens(phrase) are detected that probably indicate semantic items, such as software, developed by and California. This step detects full potentially phrases, and leaves the decision for phrases selecting in later steps.
Next, the phrases are mapping to semantic items. Phrases can denote entities, classes and properties. For example, the phrase software can denote class dbo:Software and property dbo:developer, and the phrase developed by can denote entity dbr:videogamedeveloper, class dbo:BritishRoyalty and property dbo:developer. This step purely constructs a candidate space for every possible mapping, and leaves the decision for select which semantic items in the next step.
Then, we should make the decisions for choosing phrases, mapping the chosen phrases to suitable semantic items and determine the relations of selected semantic item. We formulate the joint decisions as an generalized inference task. We employ rich features and constraints (including hard and soft constraints) to infer the joint decisions using a MLN.
Finally, with the inference results, the last step constructs a semantic item query graph, and generates an executable SPARQL query with the question type.
We will give a detailed description of each component and give a step by step explanation with the following example, Figure 2 shows the intermediate results of every steps:
Which software has been developed by organizations founded in California, USA?. Which software has been developed by organizations founded in California, USA? software
California developed by 1) Phrase detection. Sequences of tokens (phrases) that probably indicate semantic items are detected. To this end, we do not use named entity recognizer (NER) because of its low coverage. 2 To avoid missing useful phrases, we retain all n-grams as candidate phrases, and then use some rules to filter them. The rules include: the length of tokens span must be less than 4 (excepting all contiguous tokens are capitalizations); the POS tag of the start token must be jj, nn, rb and vb; all contiguous capitalization tokens must not be split, and so on. For instance, software, developed by, organizations, founded in and California are detected in the example.
2) Mapping phrase to semantic item. After phrases are detected, each phrase may
be mapped to the semantic items in KB (entities, classes and properties). For
example, software is mapped to dbo:Software, dbo:developer, etc.; California is mapped to
2 We perform testing in two commonly used question corpus (QALD-3 Training data
and free917) using Stanford CRF-based NER
tool(http://nlp.stanford.edu/software/CRFNER.shtml). The results demonstrate that merely 51.5% and 23.8% right NEs can be
recognized, respectively.
dbr:California, dbr:California (wine), etc. We use different techniques and resources
to map phrases to different types of semantic items. For mapping phrases to entities,
considering the entities in DBpeida are curated from Wikipeida, we employ anchors,
redirections and disambiguations information from Wikipedia. For mapping phrases
to classes, considering that classes have lexical variation, especially synonyms, e.g.,
dbo:Film could be mapped from film, movie and show, we use word2vec tool3 to convert
every word (phrase) into a vector and compute the similarity between the phrase and
the class in KB. The similarity scoring methods are introduced in Section 3.2. Then,
the top-N most similar classes for each phrase are returned. For mapping phrases to
properties, we employ the resources from PATTY [
tion and mapping-phrase-to-semantic-item. This step consists in the resolution of these ambiguities and determine the relations among the mapped semantic items. It is the core contribution of this paper, which performs disambiguation in a unified manner. First, feature extraction is performed to prepare rich features from the question and the knowledge base. Next, the disambiguation is performed in a joint fashion with a Markov Logic Network (MLN). The detailed information will be presented in the next Section.
4) SPARQL generation. Based on the inference results, we construct a query graph. The vertex contains the following information: the phrase, token span indexs of the phrase, the mapped semantic item and its type. The edge indicates the relation between two semantic items. For example, we use 1 2 to indicate that the first argument of an item matches the second argument of another item4. The right bottom in Figure 2 shows an example of it. The relation in the query graph is paired data merely, but the SPARQL queries need the grouped triples of semantic items. Thus, we convert a query graph into multiple joined semantic triples. Three interconnected semantic items, which must ensure the middle item is a property, are converted into a semantic triple. For example, the query graph Vdbo:Book[Class] 1 2 dbo:author[Property] 1 1 ! ! dbr:Danielle Steel[Entity]W is converted into h?x rdf:type dbo:Book, dbr:Danielle dbo:author ?xi, and Vdbo:populationTotal[Property] 1 2 dbo:capital[Property] 1 1 dbr:Australia[Entity]W5 ! ! is converted into h?x1 dbo:populationTotal ?answer, ?x1 dbo:capital dbr:Australiai. If the query graph only contains one vertex which indicates a class ClassURI, we generate h ?x rdf:type ClassURIi. If the query graph contains two connected vertexes, we append a variable to bind the missing match argument of the semantic item.
The final SPARQL query is constructed by joining the semantic item triples and combining them with the corresponding SPARQL template. We divide the questions into three types: Yes/No, Number and Normal. Yes/No questions use the ASK WHERE 3 https://code.google.com/p/word2vec/ 4 The other marks will be introduced in Section 3.1. 5 corresponding the question “How many people live in the capital of Australia?” template. With respect to number questions, we use SELECT COUNT(?url) WHERE template, if it cannot obtain a fitting SPARQL query(the query result are not a number), we then use normal question template to generate a query again. Normal questions use the SELECT ?url WHERE template. For instance, we construct the SPARQL query SELECT(?url) WHEREf ?url rdf:type dbo:Software. ?url dbo:developer ?x1. ?x1 rdf:type dbo:Company. ?x1 dbo:foundationPlace dbr:California.g toward the example. 3
In this section, we will first briefly describe Markov Logic Networks. Then, we present the predicates(features) and the first-order logic formulas for joint inference. 3.1
Markov logic networks combine Markov networks with first-order logic in
probabilistic framework[
An MLN M is consists of several weighted formulas f( i; wi)gi, where i is a first order formula and wi is the penalty(the formula’s weight). These weighted formulas define a probability distribution over sets of possible worlds. Let y denote a possible world, then p(y) is defined as follows: p(y) =
0
X ( i;wi)2M wi
X c2Cn i
1 fc i (y)A ; (1) (2) (3) where each c is a binding of free variables in i to constants; fc i is a binary feature function that returns 1 if the ground formula we get through replacing the free variables in i with the constants in c under the given possible world y is true, and 0 otherwise; Cn i is the set of all possible bindings for the free variables in i. Z is a normalization constant. The Markov Network corresponds to this distribution, where nodes represent ground atoms and factors represent ground formulas.
Let us illustrate how MLN determine the relation of semantic items mapped by phrases. The following formulas indicates that if two semantic items have some dependency path tags6, then they have some type of relations with some weights. ( 1; w1) : depP athT ag(a; b; \pobj") ^ (a 6= b) ( 2; w2) : depP athT ag(a; b; \pobj") ^ (a 6= b) ) relation(a; b; \2 1"): ) relation(a; b; \1 1"): 6 Actually, the dependency path tags are extracted from the phrases which mapped to semantic items. Here is simplified to illustrate how MLN works. Here, a and b are variables which represent any semantic item, depPathTag and relation are an observed predicate and a hidden predicate, respectively. The values of observed predicates are known from feature extraction, and the values of hidden predicates are infered. The values of two weights w1 and w2 affect the decision of choosing relation types between two semantic items.
There are a lot of methods to inference and learn the weights for MLN[
In MLN, we design several predicates to resolve the ambiguities in phrase detection, mapping phrases to semantic items and semantic items grouping. Specifically, we design a hidden predicate hasPhrase(i) to indicate that the ith candidate phrase has been chosen, predicate hasResouce(i,j) to indicate that the ith phrase is mapped to the jth semantic item, and predicate hasRelation(j,k,rr) to indicate that the jth semantic item and the kth semantic item can be grouped together with the relation type rr. Note that we define four relation types between two semantic items: 1 1, 1 2, 2 1 and 2 2. Here, the relation type t s means the tth argument of the first semantic item corresponds to the sth argument of the second semantic item. The detailed illustration is shown in Table 1.
Moreover, we define a set of observed predicates to describe the properties of phrases, semantic items, relations between phrases and relations between semantic items. The observed predicates and descriptions are shown in Table 2.
Previous methods usually designed some heuristic patterns to group semantic items, which employ the human-designed syntactic path between two phrases to determine the relations between any two phrases. In contrast, we collect all the tokens in the dependency path between two phrases as possible patterns. The predicate phraseDepTag and hasMeanWord are designed to indicate the possible patterns. Note that if these tokens only contain POS tags dtjinjwdtjtojccjexjposjwp or stop words, the predicate hasMeanWord is false, otherwise is true. In this way, our system is expected to cover more language expressions and answer more questions. Moreover, the SPARQL endpoint is used 7 http://alchemy.cs.washington.edu 8 http://hazy.cs.wisc.edu/hazy/tuffy/ 9 http://code.google.com/p/thebeast to verify the type compatibility of two semantic items and whether or not one triple pattern can obtain query results.
The predicate hasRelatedness needs to computes the coherence score between two
semantic items. Following Yahya et al. [
The predicate priorMatchScore assigns a score prior to mapping a phrase to a semantic item. We use different ways to compute this scores for different semantic item types. For entities, we use a normalized score based on the frequencies of a phrase referring to a entity. For classes and properties, we use different methods. At first, we define three similarity score metrics as follows: a) s1: Levenshtein distance score between the labels of semantic item and phrase; b) s2: word embedding score, which is the similarity between two phrases, is the maximum value of the cosine of words between two phrases; c) s3: instance overlap score, which is computed using the Jaccard coefficient of instance overlap as a similarity score. The prior scores for mapping phrases to classes and properties are s1 + (1 )s2 and s1 + s2 + (1 )s3, respectively. The parameters are set with empirical values10. 3.3
We use two kinds of formulas for jointly decisions: Boolean and Weighted formulas. Boolean formulas are hard constraints which must be satisfied with the entire ground atoms in final inference results. Weighted formulas are soft constraints which could be violated with some penalties. 1) Boolean Formulas (Hard Constraints) Table 3 lists the boolean formulas used in this work. The “ ” notation indicates an arbitrary constant. The “jj” notation expresses the number of true grounded atoms in the formula. These formulas express the following constraints: hf1: if a phrase is chosen, then it must have a mapped semantic item; hf2: if a semantic item is chosen, then its mapped phrase must be chosen; 10 Set to 0.6 for class, set and to 0.3 and 0.3 for property, respectively. hf3: a phrase can map to one semantic item at most; hf4: if the phrase is not chosen, then its mapping semantic item should not be chosen; hf5: if a semantic item is chosen, then it should have one relation with other semantic items at least; hf6: two semantic items have one relation at most; hf7: if a relation for two semantic items is chosen, then they must be chosen; hf8: each two chosen phrases must not overlap; hf9, hf10, hf11, hf11: the semantic item with type Entity and Class should not have second argument matching with others; hf12: The chosen relation for two sematic items must be type-compatible. 2) Weighted Formulas (Soft Constraints) Table 4 lists the weighted formulas used in this work. The “+” notation in the formulas indicates that each constant of the logic variable should be weighted separately. Those formulas express the following properties in joint decisions: sf1, sf2: The larger the score of phrase mapping to semantic item, the more likely the corresponding phrase and semantic item should been chosen; sf3: there are some associations between POS tags of phase and types of mapped semantic item; sf4, sf5, sf6: there are some associations between the dependency tags in the dependency pattern path of two phases and the types of relation of two mapped semantic items; sh7: the larger the relatedness of two semantic items, the more likely they have a relation; sf8: if the triple pattern has query results, those semantic items should have corresponding relations. 4
Stanford dependency parser [
Our system could learn the effectiveness patterns. We show the weights of the learned patterns corresponding with formula sf3 in MLN, as shown in Table 5. From the table, we can see that nn is mapped to Entity more likely than Class and Property, and vb is most likely mapped to Property. It proves that our model can learn the effective and reasonable patterns for QALD.
Among the factors that affect performance most are: 1) training set consisting of 110 questions is limited, we found some weights of grounded formula are zero; 2) the parameters are used for computing prior score mapping phrase to semantic item are difficult to tune, because we use different method to entities, classes and properties; 3) lack of global constraints, such as, it is hard to count the number of unmapped tokens in question. 5
In this paper, we present a question answering system over Linked Data which translates the natural language questions into the standard RDF data queries (SPARQL). We present a jointly learning framework for phrase detection, phrases mapping to semantic items and semantic items grouping. The novelty of our method lies in that we make joint inference and pattern learning for all subtasks in QALD by using first-order logic. Our benchmark results demonstrate the effectiveness of the proposed method.