In this paper, we present a QA system enabling NL questions against Linked Data, designed and adopted by the Tor Vergata University AI group in the QALD-3 evaluation. The system integrates lexical semantic modeling and statistical inference within a complex architecture that decomposes the NL interpretation task into a cascade of three different stages: (1) The selection of key ontological information from the question (i.e. predicate, arguments and properties), (2) the location of such salient information in the ontology through the joint disambiguation of the different candidates and (3) the compilation of the final SPARQL query. This architecture characterizes a novel approach for the task and exploits a graphical model (i.e. an Hidden Markov Model) to select the proper ontological triples according to the graph nature of RDF. In particular, for each query an HMM model is produced whose Viterbi solution is the comprehensive joint disambiguation across the sentence elements. The combination of these approaches achieved interesting results in the QALD competition. The RTV is in fact within the group of participants performing slightly below the best system, but with smaller requirements and on significantly poorer input information.
Language is the most powerful media for acquiring, communicating and sharing knowledge. It has been optimized through centuries of use, successes and failures. Although the Web of Data claims for machine readable standards, natural language is still the preferred query language for naive users, early adopters and even experts in some knowledge domains. Question answering is thus the crucial bottleneck for a truly and universal adoption of Open Linked Data as a knowledge sharing paradigm and practice.
In general, approaches for question answering range between rule-based (and strongly
deductive) systems, whose expressivity is harmonic with the knowledge representation
standards in the Web and whose precision is optimal, to shallow, basically lexicalist
approaches very close to the bag-of-words practices in document retrieval processes.
In the first family of systems, we could mention at least Swoogle [
An interesting vocabulary-independent approach is attempted in [
In line with the latter, in this paper we present a novel contribution to the above research line which combines symbolic reasoning over the semantic constraints on the underlying Open Data repository and statistical inference. This latter is useful to manage the ambiguity introduced by natural language within a complex process for the interpretation of the question, that integrates distributional semantic models of lexical information and probabilistic inference. In this way, we aim at solving at least two problems. The first one is the localization and retrieval of ontological elements evoked by a question without relying on strict hypothesis on the resource vocabulary. Second, we jointly solve the different ambiguities arising in the interpretation by integrating question grammatical structures and ontology information. The idea is to map the different inferences into a generative graphical model, i.e. an Hidden Markov Model of the question. It works as a bridge between the linguistic and the RDF structures, i.e the syntactic dependency graph of the question on the one side and the full paths in the RDF graph, on the other. The rest of the paper is organized as follow: Section 2 presents an overview of the systems architecture and introduces the HMM notions. Section 3.1 discusses in more detail the modeling of the input question through a Hidden Markov Model, and the resulting RDF sub-graph obtained. The process of mapping the HMM output into the SPARL Template is discussed in Section 3.4. Finally, in Section 4, a first analysis of the QALD-3 results are discussed with some final considerations. 2
The overall architecture of the RTV1 system is shown in Figure 1 where the core components of the system are within the main box and interacts with auxiliary preexisting modules and resources. The treatment of a sentence as carried out by the core system
can be summarized as follows. First an analysis of the syntactic (dependency) graph is carried out where proper nouns related to DBpedia resources are detected and classified in the so-called HMM initialization stage. In the HMM all the observations about key entities or classes are selected from the question, as they refer to ontological elements, i.e. mentions to entities, literals and relations (or properties). In the HMM modeling stage, the states, emissions and transitions of the Markov chain are defined. States corresponds to the RDF elements retrieved by a question fragment from DBpedia: these elements may correspond to resources, classes or relations. The HMM best sequence of states is computed in the decoding module, here a disambiguation process is imposed exploiting the combination of statistical and ontological constraints obtaining a state sequence which can be mapped into a RDF sub graph.
The process, triggered by a grammatical analysis of the input question, foresees three main components deal with the initialization, modeling and decoding of the HMM and a final stage to compile the resulting SPARQL query. A detailed description of such modules is given in Section 3.
Besides a syntactic parser, i.e. Chaos [
Our objective is the modeling the interpretation of the natural language query q into the ontology domain D through the following set of HMM random variables: – The observation set L = fl1; :::; lmg, in our case the observation set is computed over the set of symbols of the sentence q, – the set of States O = fo1; :::; ong, that models the ontological resources 2 D candidate to be a suitable interpretation for the observation set L, – the emission matrix E : L O ! [0; 1] models the probability that an observation l evokes the state o, i.e., the corresponding ontological resource, – the transition matrix T : O O ! [0; 1] models the transition probability from the state oi the the state oj , these probability model the reachability of the state oj from the state oi. They help explaining the semantics of relationships between hidden states, i.e. inferential steps that correspond to the transversal of RDF graphs along specific paths.
Both emissions and transition probabilities are estimated on the fly, i.e. against the incoming sentence, just before applying the traditional decoding algorithms (i.e. Viterbi) to the resulting HMM. The outcome of the decoding stage is a full RDF path, that corresponds to one interpretation of classes (such as Person), instances as well as relations. In the next subsections each step of the HMM modeling is discussed.
The sentence segmentation for the generation of the observation set L is driven by the syntactical structure of the sentence q. The HMM initialization process proceeds by selecting the root of the dependency graph and navigating all the syntactic relations, by thus enumerating the entire set of predicate expressions (e.g. die in the sentence 2 http://lucene.apache.org/core/ 3 Short texts are usually expressed by the vector that is the linear combination of vectors corresponding to the involved words. in Figure 2) as well as their direct arguments (such as Where and Abraham Lincoln). The generated set of HMM observations is thus bipartite into two sets: nodes (that corresponds to nodes or literals in the RDF graph) and relations (i.e. links in the RDF graph), alternating in the Markov chain.
The resulting sets of nodes and links gives rise to one chain with the precedence assigned to the focus of the question (i.e. the place introduced by Where) used as initial node). The resulting observation chain for the sentence Where did Abraham Lincoln die? is shown at the bottom of Fig. 2 in which Where corresponds to the first node and the rest of the chain links together the other different nodes and relations. Notice how relations (e.g. die) alternate with elements but all of them align into a sequence. Moreover, proper nouns (e.g. Abraham Lincoln) are specifically treated as the Chaos parser lexicon has been enriched in the experiments with the catalogue derived from the values of the field label in DBpedia elements.
The analysis of the sentence ends when all grammatically relevant elements (basically nouns, verbs and adjective) give rise to an observation in the targeted Markov chain.
During the HMM initialization, key elements in the sentence are detected and their associated ontological elements are located in the ontology. Key elements correspond to linguistic expressions defined as observations. In this way, a sequence corresponding to a Markov chain is generated. In the interpretation process targeted here, the HMM is designed as a generative model of the question. The model provides statistical evidence about the way a question is generated as a request against RDF resources that form a graph. In order to fully define the HMM, we still need to make the set of observations L correspond to states O, and determine the corresponding transition and emission probabilities. The following modeling choices must be carried out: – How to map linguistic expressions, such as proper nouns (e.g. Where, Abraham Lincoln) or predicate structures (e.g. die), to ontological elements such as DBpedia instances (e.g. possibly ambiguous Wikipedia pages) or relations such as deathDate – How to model the notion of emissions E, that characterize the relationship between hidden states and observable linguistic structures – How to model the notion of transitions T that help explaining the semantics of relationships between hidden states, i.e. inferential steps that correspond to the transversal of RDF graphs along specific paths
In this work, we mapped DBpedia resources, classes as well as relations or properties into HMM states: they justify (as emissions) the observable linguistic structures, i.e. key entities of the question. While observations correspond to an open set of linguistic symbols W , by relying on a large scale semantic lexicon developed through corpus analysis, we will be able to map them into ontology element set D. Transitions corresponds to links between RDF elements and have a clear ontological status determined by DBpedia. Notice how probabilities equal to 0 can be used to constraint the semantics of a transition and model DBpedia links. On the other hand, more plausible interpretations receive higher probabilities, according to the context of the question.
connects a linguistic expression l to an ontological element o and its probability in the HMM is
p(ljo)
The population of the state space and the estimation of p(ljo) is defined through an
information retrieval process. First, the linguistic expression l related to a fragment
of the dependency graph is generated. Ontological elements o for different linguistic
expressions l are also different, and they must be precisely located in the ontology:
– when instances are involved (as proper nouns are detected in the question), first the
query is executed against a search engine devoted to index the different DBpedia
instances; the index is built over the long abstracts of the resource made available
by DBpedia. The query corresponds to the expression l itself (e.g. Abraham
Lincoln) and a number of resources (in which l is more or less explicitly mentioned)
are retrieved. As linguistic expressions are represented in vectors (as in [
5 Notice that if a DBpedia relation corresponds to a complex linguistic expressions, i.e. writtenBy), the distributional analysis can be carried out for the entire pattern (i.e. written by) as it occurs in the corpus. In all cases thus gives rise to a unique vector for the entire pattern. binations. Technically, the estimate for the emission probability for a generic reli is: p^(ljoi) = Poj 2TiRS j where l is the linguistic expression for a relation, oj belongs to the target relationship set T RS and are cosine estimates of the lexical similarity between l and oj . No smoothing factor is here applied, so that poorly similar relationship in T RS can be retrieved from l and no external relation (or literal relational expression) is admitted for l. – When no relationship can be found at the previous stage, the system must deal with complex linguistic relational expressions, denoted by cl. A further attempt is carried out to map these expressions to the relations and properties of individuals extending their linguistic processing. As the target ontological relation in this case is unknown (i.e. the set of DBpedia properties are out of the closed dictionary of relationships delivered with DBpedia 6, parsing is carried out over such an complex cl, in order to extract its linguistic head, denoted by hcl. The vector hcl corresponding to hcl is selected from the word space used as a representative of the multiword expression. Similarly to the previous step, it is used as a query to retrieve the involved ontological relationships from the target relationship set T RS. All relations or properties closer than a given threshold to h are added to the set of as potential states for the underlying observation (i.e. cl). Also in this case, the probability estimate is: p^(cljoi) = p^(hcljoi) = Poj 2TiRS j where cl is the complex linguistic expression, oj still belongs to the target relationship set T RS and j are the cosine estimates of the lexical similarity between the expression head hcl and oj . Again, no smoothing is here applied.
At the end of the above phase the entire lattice structure is built, where columns (i.e. states) are fullfilled and emission and transition probabilities are estimated. The vector space treatment of the probabilities is discussed in the next section.
Probability Estimation in the HMM and distributional lexical similarity As we
defined in the previous section, a word space is derived for representing: (1) the lexicon
for individual words as they are used in the DBpedia corpus; (2) the ontological classes
and entities through the linguistic expressions corresponding to their labels; (3) the
ontological relations and properties as they appear in the DBpedia closed dictionary; (4)
unknown ontological relations, occurring in a specific target relation set, i.e. originating
by the RDF triples regarding one or more key entities retrieved for a question, but
missing from the DBpedia relationship catalogues. In all this case, an ontological element oi
is made corresponding to a word vector, hereafter denoted by oi: for example spouse
correspond to the vector spouse. In this work we use the distributional behavior of the
word as an hint on the relationship semantics, and this distinguishes our HMM based
approach either from the work by [
We captured the distributional behavior of words in a word space similarly to [
l oi klkkoik The application of the above semantic relatedness measure to the transitions in an example sentence is shown in Fig. 3: only states that have a not null semantic similarity with an observation are given a numerical score, where scores are mapped in probabilities as in Sect. 3.2.
In QALD-2103, we applied the above method to the DBpedia corpus, made of all the textual descriptions associated with more than 3.77 million of entities in version 3.8. More specifically, to build the matrix M , POS tagging is first applied to build rows with pairs hlemma, ::POSi, or lemma :: P OS in brief. The contexts around these items are the columns of M and co-occurrences are computed within windows of size [ 5; +5] around the items l. This allows to better capture syntactic properties of individual l. The most frequent 20,000 lemmas (i.e. l) are selected along with their 20k contexts (i.e. features w). The entries of M are the point-wise mutual information between them as computed in the entire corpus. The SVD reduction is then applied to M, with a dimensionality cut of k = 250. 3.3
In Fig. 3 the lattice corresponding to the sentence Where did Abraham Lincoln die? is shown. Emission probabilities are shown as nodes scores, while the different set of states for the three individual observations are reported. Transition probabilities are not made explicit. Their treatment is very basic in the current system. First we select transitions that are compatible with the range constraints of the DBpedia data: only transitions whose relations (or properties) are semantically compatible with the links in the DBpedia RDF graph receive a non zero probabilities. The graph is strongly simplified in this way although a fully connected HMM is obtained in most of the cases. Then the probability of the transitions are normalized through a maximum entropy perspective: if n nodes o1; :::; on are reachable from a given state o^t, as they satisfy all semantic constraints, then the transition probability p(oijo^t) = 1=n for each i = 1; :::; n. In this way, every consistent transition is equally likely for the system.
The decoding stage, often called Viterbi [
In view of increasing robustness, also a form of smoothing is applied as in [
In this module the resulting SPARQL query is generated starting from the RDF path obtained from Viterbi. Here, in order to obtain a consistent SPARQL query, the resulting RDF path is validated wrt the domain and range constraints imposed by the relational object in the RDF graph. For instance,for the HMM trellis in Figure 3 the resulting graph is ?x dbo:deathPlace res:Abraham Lincoln . While the single elements are a correct interpretation for the NL input question, the resulting graph has the argument constraint order reversed for dbo:deathPlace. Here the correct order for the graph is computed, and the SPARQL query is built selecting the right query form. For the QALD evaluation we exploited the input feature answertype to select the right SPARQL form. 4
The RTV system has demonstrated a non-trivial performance, as reported in Table 1.
Its third place is mainly due to its poor coverage of the set of sentences with a good
balance between precision an recall. Given that, except for the named entity dictionary
made available to the parser, the system does not rely on any resource specific
dictionary, technique or heuristics this result is very promising. The method is fully portable
as language processing and a general parsing technology, i.e. Chaos [
The adopted model appears very promising especially for its portability across other domains as well as other languages. On the one side emission probabilities model the plausibility of interpretations (i.e. resources, relations or properties) as semantically related to observed syntactic structures (i.e. proper nouns but also verbs or nominal compounds). On the other side transition probabilities model the semantic relatedness across individual structures retrieved through distributional lexical semantic metrics. Finally, the Viterbi decoding guarantees a straight joint disambiguation process that acts on the global level of the sentence, and robustly accounts for individual interpretations interacting against the underlying syntactic structures.
A specific error analysis aiming at assessing the contribution of the individual stages in the processing chain has been carried out. In about 70 partially (or mistakenly) processed sentences, we observed that missing relations in the HMM is the major source of error (about 50%). In these cases the system was unable to lexically translate the underlying relation (e.g. admittancedate ): these were made available by the involved resources but it was not possible to properly locate it in the question (basically, unresolved anaphoric references or implicit arguments). An example is the case of a prepositional phrase such as ”(... book) by Kerouac (...)” that elliptically refers to the predicate ”writing a book”. Given the absence of an explicit lexical reference to the predicate ”writing”, no retrieval of the proper relation writtenBy could be obtained, so that the HMM was inconsistently generated.
In a lower percentage of errors (below 20%), the mistake is generated by the Viterbi decoding phase, that fails to properly disambiguate the entities (i.e. select the proper state sequence) even if a well formed and consistent trellis was available: the output path produced by Viterbi was including wrong resources, thus preventing to compile the correct SPARQL query. In a small number of cases, the output of Viterbi is not properly connected to any resource (as the smoothing foreseen for a literal interpretation of a symbol in the sentence is selected for too many observations), and no semantic constraint was available to build the SPARQL query. These queries were simply rejected.
In future work, we will optimize parameters (e.g. the acceptance threshold imposed to the probability attached to the ”best” Viterbi path) as these have not been studied in enough detail. Moreover, the current initialization of the HMM, basically dependent on the dependency graph, makes use of no semantics, e.g. no access to the DBpedia resources is done during the HMM initialization stage. We hypothesize here large improvement for methods that directly exploit ontological resources to initialize the HMM: this would allow to improve the treatment of relations as well as to early prune inconsistent interpretations. In the QUALD meeting, while we assume to bring a larger experimental evidence, and a quantitative discussion about the main weaknesses mentioned above, we will report of the system application on RDF data different from the QUALD data, in order to better generalize the system assessment.