For our participation to QALD-5, we developed a system for answering questions on a knowledge base. We proposed an unsupervised method for the semantic analysis of questions, that generates queries, based on graph transformations, in two steps. First step is independent of the knowledge base schema and makes use of very general constraints on the query structure that allows us to maintain semantic ambiguities in di erent graphs. Ambiguities are then solved globally at the nal step when querying the knowledge base.
More and more structured knowledge is made available on the Web, as with DBpedia [Auer et al., 2007], Freebase [Bollacker et al., 2008] or Yago2 [Ho art et al., 2011], allowing a user to nd answers related to some precise information need. To enable a user to have simple access to these bases, simple interfaces that support questions given in Natural Language (NL) are developed, which do not require a user to know how the knowledge is structured, i.e. the knowledge base schema, and to learn a formal language, e.g. SPARQL. A SPARQL query relies on a conjunction of triples that can be represented as a graph: nodes are entities and edges are typed relations. The two interrelated problems we are faced with when transforming a NL question into such a graph are: i) identifying entities, relations, entity classes and operators and ii) determining the structure of the query, i.e. how these entities and relations are related and how the operators apply. [Unger et al., 2012] and [Xu et al., 2014] make rst structural choices based on the knowledge base schema before knowledge base mapping, while [Yahya et al., 2013] and [He et al., 2014] solve all the ambiguities together.
We chose to develop an unsupervised method based on graph transformation that acts in two steps: rst, syntactic graphs are transformed for building all the structural valid syntactico-semantic representations of the question that maintain ambiguities related to the queried knowledge base schema and content. The second step consists in generating all the semantic graphs made of valid triples, determined according to the knowledge base schema and content, i.e. DBpedia, each leading to a SPARQL query. These ambiguities are solved at the last step, close to [Zou et al., 2014]. Each semantic graph is weighted according to scores attributed to triples, and the answer is the result of the top ranked query that applies.
The system, named SemGraphQA, was designed for answering DBpedia queries, and cannot answer hybrid ones. It obtained a F1 of 0.31 at QALD-5. 2
The aim of the system is to transform a question Q into semantic graphs GSQ, each corresponding to a possible meaning. The nodes of the graph are entities and the edges are relations. Every entity and relation has a relevance score, which is used to compute the score of the graph. This transformation involves di erent steps (Figure 1).
Question phrases are identi ed in order to link them to semantic items of the knowledge base: entities, types or relations (Figure 1a). Entity identi cation is performed by DBpedia Spotlight [Daiber et al., 2013], type identi cation is done using the type labels, and relation identi cation by a method we propose based on variations extracted from WordNet. To each possible semantic item a relevance score is given.
The syntactic analysis of the question by the Stanford Parser [Klein and Manning, 2003] produces a syntactic graph which is simpli ed and rewritten to generate a GSQy graph (Syntactic Graph of the Question) which has for nodes the words and for edges the syntactic relations. In that graph, the semantic nature of each word (entity or relation) is unknown (Figure 1b).
The GSQy graph is multiplied by assuming each word can be either entity or relation in order to keep the possible ambiguities, and then transformed and ltered in order to obtain the graphs GSQS which comply to structural constraints (Figure 1c). For example, if two relation-word are linked by a syntactic relation, it means there is an implicit entity and we add an entity-word between them. In the question Who is the daughter of Bill Clinton married to?, when daughter and married are considered as relation-word, they are linked directly, so we create an entity-word unknown between the two, which explicits the fact to have to nd the daughter of Bill Clinton to answer to the question.
The last step consists in generating the possible semantic graphs, noted GSQ, using the ambiguities of each node and edge obtained after the mapping phase. These graphs are constituted of triples consistent with the knowledge base (Figure 1d). These semantic graphs are sorted based on a relevance score and the corresponding queries are executed in descending order until at least one answer is returned.
The method we propose aims at never eliminating an interpretation that has a coherent semantic structure, i.e. a structure that can be instantiated in the queried data. The constraints on the graph structure are very general and not speci c to the schema of a given knowledge base. Thus, these constraints could also be used when searching information in texts. The constraints linked to the Who is the daughter of Bill Clinton married to? Entity
Relation
Class Legend
Paraphrases married
Who daughter
Bill Clinton married dep Who dbo:Person
dbo:child res:Bill Clinton dbp:spouse res:The Who dbp:daughter dbp:clinton dbo:partner Question nsubjpass daughter prep of
Bill Clinton res:Marriage Knowledge base (b) Simpli ed syntactic graph (a) Mapping Who
Bill Clinton married
daughter
Implicit entity (c) Syntactico-semantic graph GSQS res:Bill Clinton
res:Bill Clinton Triplet dbo:child x dbo:child x Triplet dbp:spouse
dbo:partner dbo:Person:?
dbo:Person:? (d) Semantic graph GSQ Marc Mezvinsky
Answer queried base are applied at the last step and the nal ltering is operated by the search in the knowledge base, based on nding an answer or not. 3
In order to map question terms to semantic components of the knowledge base (KB), i.e. entity, relation and class (cf. Fig. 1a), we determine a set of phrases that could be related to a semantic component according to its label. These phrases correspond to all n-grams, with n maximum 5, that contain a noun, a verb or an adjective, as each type of word may lead to a type of component. A reliability score is associated to each found component. 3.1
Entity mapping consists of recognizing an entity mention in a question, i.e. a word or a phrase that refers to an entity, linking it to a KB resource and determining its class. To this purpose, we make use of DBpedia Spotlight (DBS) [Daiber et al., 2013]. DBS determines possible entities, extracts their mention, associates them with a score, and classi es them according to the DBpedia ontology1 that contains a hierarchy of classes. We use the DBS score as the reliability score of an entity. It is based on a score computed during the indexing of the entities and contextual scores depending on the other question terms. As we do not want to choose between entities at a early stage, we keep all results provided by DBpedia Spotlight. 3.2
Some question phrases refer to classes, and not to entities. For example, in the question Which languages are spoken in Estonia?, languages corresponds to the class dbo:Language and in Which software has been developed by organizations founded in California? , organizations corresponds to the class dbo:Company and software to the class dbo:Software.
The identi cation of classes enables to further associate it with the domain or range of a relation. Target classes are those of DBpedia classes and Yago classes2. Their identi cation is based on a comparison of candidate n-grams to class labels. Recognized classes are considered as unknown entities that could be found when querying the KB.
Scores of recognized classes are based on the Jaccard distance of matching words to favour speci c classes. For example, the class StatesOfTheUnitedStates will obtain a greater score than States. Thus, the score Sclass for evaluating the reliability of a class is:
Sclass =
# words maximum number of words in a label (1) 1 http://mappings.dbpedia.org/server/ontology/classes/ 2 DBpedia includes classes of Yago [Ho art et al., 2011] We set maximum to 10. As DBpedia classes are less numerous than Yago classes (529 vs 379900), and more often present in the DBpedia triples, we set a parameter to 2 for DBpedia classes and 1 for Yago to lower Yago classes score.
A special case is due to interrogative words. They are processed separately and each interrogative word is mapped to a class, for example Who is mapped to dbo:Agent and Where is mapped to dbo:Place. 3.3
Identi cation of a relation consists of associating a mention extracted from the question to a KB relation. Each KB relation is associated with a label, which corresponds to a possible mention in texts. In order to maximize recall for relations, we depart from all candidate mentions, made of the di erent question n-grams, rather than pre- ltering them according to a classi cation into relation and non relation classes.
However, few relations are mentioned in questions using their KB label and several kinds of variation have to be considered: 1. The POS category of the word in the label is di erent from the POS category of the word in the mention. For example, in Who is Barack Obama married to ?, the verb married has to be related to the relation with a label made of the noun spouse. 2. Mentions of relation and labels are paraphrases or present a greater semantic distance. For example a mention can refer to an hyponym as in Figure 1a. 3. Labels and mentions are made of several words, i.e. n-gram with n greater than 1, and each of the words can present variations.
In order to overcome this lexical gap, we built a lexicon with variants acquired from WordNet [Fellbaum, 1998]. We selected the following relations in WordNet: { derivationally related forms: successor $ succeed { synonyms: author $ writer { hypernyms/hyponyms : relative $ sister
The algorithm for acquiring variants depart from a label. For each word, the network is recursively explored at a maximum depth d. We limit the depth in order to compute the most relevant variants. We experimentally xed d = 4.
Each variant is assigned a score based on the path length:
Sr =
1 path length between two terms (2) with the path length equal to the number of crossed hypernyms/hyponyms links.
We built a dictionary of variations for all the relations in DBpedia. These relations all have an English label, for example dbo:child, which indicates all the children of a person, has the label child and dbo:birthDate, which indicates the birthday of a person, has the label birth date. There is a total of 1,252,327 variations generated for 12,331 relations, with a mean of 102 variations by relations.
Each possible meaning of a question is represented by a set of triples (e1; R; e2), with e1 and e2 entities and R a relation, making a connected and weighted semantic graph GSQ. Entities are linked by a relation only if a syntactic relation exists between their mentions. Triples are those which have an instantiation in the KB.
An entity is described by four elds: mention, type, value and score. The elds mention and type can be empty. For example an interrogative word is an entity with only a type and a label. The value eld is an uri, a variable x when it is an implicit entity in the question, or ? when it is the entity to nd. The entity score is computed by the mapping process (cf Section 3.1), and has a value when an uri is found.
A relation has a label (in the knowledge base), a domain, a range and an identi er in the knowledge base (uri). For example the relation dbo:birthDate (http://dbpedia.org/ontology/birthDate) has the label birth date, the domain dbo:Person and the range xsd:date
In case of ambiguous question terms, that have been related to di erent elements of the knowledge base, several semantic graphs will be generated for representing the di erent meanings of the question. 4.2
Triples are generated from the syntactic dependency graph given by the Stanford parser [Klein and Manning, 2003]. This process is decomposed into two stages: the production of syntactically well-formed syntactico-semantic graphs GSQS , and the generation of semantically coherent semantic graphs GSQ.
The transformation of a syntactic graph into a GSQS graph is done by the following steps: 1. the syntactic graph is simpli ed to keep only the relevant dependency relations. The syntactic relations such as determiner, noun compound modi er, controlling subject, passive auxiliary, auxiliary, open clausal complement, controlling subject and copula are ltered. The remaining relations form a graph of words (see Figure 1b); 2. a word may refer to an entity or a relation. This entails several possible graph structures and several graphs are generated for every possibility with each term replaced by an entity word or a relation word node; 3. these graphs are then ltered by well-formedness criteria: each entity word must be linked to a relation word; if two relation word are linked, an entity word corresponding to an implicit entity is added; every relation word must be linked to two entity words; the graph must be connected (cf Figure 1c).
Once these GSQS graphs of words typed as relation or entity are generated, it is possible to generate the semantic graphs GSQ constituted of semantic triples: 1. every triple element is mapped to each semantic item found during the mapping step. It makes it possible to generate di erent semantic triples for each triple of a GSQS graph; 2. the semantic coherence of each triple is checked by keeping only the triples which have an instantiation in the knowledge base; 3. the Cartesian product between the remaining triple lists is computed to obtain the semantic graphs GSQ, which are the possible semantic representations of the question (cf Figure 1d).
Generating GSQS graphs before generating GSQ graphs enables to lter a subset of the graphs with structural criteria, without taking into account the mapping ambiguities on each node and edge, and hence produce less semantic graphs. 4.3
Once all the possible triples are known, it is possible to evaluate their consistency relative to semantic constraints provided by the KB schema. In KB triples, each of the two entities can be associated to a type, and relations are de ned by a domain and a range. Using this information, we can compute a compatibility score by giving a lower score to triples that are not compatible, i.e. the types of the joint entities do not t domain and range. Indeed we cannot simply dismiss the incompatible triples because the knowledge base may be inconsistent: some entities are linked by a relation without observing the domain or range constraints. For example, the answer to the question Who developed Minecraft? corresponds in DBpedia to the triple hres:Minecraft dbo:developer res:4J Studiosi. The domain of dbo:developer is dbo:UnitOfWork and the range is dbo:Agent. res:Minecraft has type dbo:VideoGame which is not compatible with dbo:UnitOfWork.
We de ne the compatibility between an entity e of type Ce and a domain D of type CD as: e is incompatible with D only if CD is not included in the set formed of Ce and of its supertypes and subtypes. There are three possibilities: compatibility, incompatibility and the case where the information is missing if the domain or entity types are unknown. For example the relation dbo:childOrganisation identi ed as a candidate relation for the mention daughter between Bill Clinton and his daughter (implicit entity mention for which the type is unknown) is incompatible because it has as range dbo:Organisation which is not compatible with the type dbo:President of Bill Clinton.
This compatibility veri cation makes it possible to compute a score Sc of compatibility of a triple:
Sc = Scd
Scr (3) with Scd and Scr the compatibility scores of the domain and range. They take the value in case of compatibility, in case of missing information and in case of incompatibility. A compatible domain, or range, must obtain a better score than missing information or incompatibility, so we take > > and we set = 1:0, = 0:75 et = 0:5. 4.4
Each semantic graph is assigned a weighting score S given by the formula: The SPARQL query may involve the use of operators. Thus, we developed a basic method to handle some cases. The following question types are identi ed: { count question : question starting by How many and that either needs a COUNT operator in the SPARQL query, or a relation usually containing word such as count or total in their label; { boolean question: question usually starting by Is or Are and that are answered using a ASK type of query; { factual question: all the other questions, that are answered by SELECT queries.
The question type is identi ed using a simple keyword matching. The same analysis is then done for all three kinds of questions, only the generation of the SPARQL query di ers a little to handle the di erence in the expected answer.
In several questions, binary operators are present. The operators can be for example more than, less than, the same as and are expressed in SPARQL queries as FILTER. We currently handle more than and less than operators by considering them as a special kind of relation. These relation are processed the same way as the knowledge base relation, until the transformation in SPARQL queries where they are represented as FILTER. For example the question Which caves have more than 3 entrances? is expressed by the query select distinct ?2 where fFILTER(?1 > 3). ?2 dbp:entranceCount ?1. ?2 rdf:type dbo:Cave.g
Some binary operators are not handled yet such as same-as operators, neither are unary operators represented in SPARQL as ORDER BY and LIMIT that correspond to superlative in the question such as "oldest child".
The results in Table 1 are obtained on the QALD-5 test question set. It is made of 60 questions, with 50 questions on DBpedia and 10 hybrid questions. Our system is evaluated on the 50 questions on DBpedia.
Xser
APEQ
QAnswer SemGraphQA
YodaQA
Among the 39 questions that the system does not answer correctly, there are overlapping errors in 26 questions: an entity is not found in 7 questions, a relation is not found in 25 questions and a type is not found in 4 questions. In the 13 remaining questions with errors, there are some issues such as the order operation (usually represented as a superlative in the question), and some binary operators such as same-as which are not handled by the system currently. An other error cause is an incorrect ranking of semantic graphs.
The main di culty relies in the identi cation of relations, due to the lexical distance between the relation mention and its label in the knowledge base, or to a relation wordings in the question that does not make use of a content word. 6
In the context of systems enabling to answer questions on knowledge bases on the Semantic Web, we developed SemGraphQA, a system based on graph transformations designed for handling structural and lexical ambiguities. It enables to postpone choices until the latest point while limiting the number of ambiguities to consistent ones with graph structure. The method we used is unsupervised and can be easily applied to knowledge base other than DBpedia. Moreover, the semantic representation generated is independent of the query language.
We plan to build a hybrid system on knowledge base and texts in order to take into account the information present in textual corpora using the same semantic representation generation method with an adaptation of the identi cation of semantic items.