Many semantic search tool evaluations have reported a user preference for free natural language as a query input approach as opposed to controlled or view-based inputs. Although the exibility o ered by this approach is a signi cant advantage, it can also be a major di culty. Allowing users complete freedom in the choice of terms increases the di culty for the search tools to match terms with the underlying data. This causes either a mismatch which a ects precision, or a missing match which a ects recall. In this paper, we present an empirical investigation on the use of named entity recognition, word sense disambiguation, and ontology-based heuristics in an approach attempting to bridge this gap between user terms and ontology concepts, properties and entities. We use the dataset provided by the Question Answering over Linked Data (QALD-2) workshop in our analysis and tests.
In its broadest sense, Semantic Search describes the process of matching
document content with user intent. Semantic search tools adopt di erent query input
approaches, ranging from natural language (`free' NL [
An additional di culty is Named Entity (NE) recognition and
disambiguation. NE recognition approaches include parsing and then matching to resources
in the ontology; directly recognising and disambiguating using a state of the art
(SOA) NE recogniser [
In this paper, we present a free-NL semantic search approach that bridges the gap between the sense of the user query terms and the underlying ontology's concepts and properties. We use an extended-Lesk WSD approach (Section 2) and a NE recogniser (Section 3.1) together with a set of advanced string similarity algorithms and ontology-based heuristics to match query terms to ontology concepts and properties (Section 3.3). Section 4 presents the evaluation of our approach using the dataset provided by the Question Answering over Linked Data (QALD-2) workshop2. 2
Disambiguating polysemous words in user queries is of paramount importance
to understand user intent and provide correct results. Indeed, identifying the
intended sense of a polysemous word is a necessity for query expansion which is
often used by search tools to bridge the gap between user terms and ontological
concepts and properties. Some search approaches consider all the senses of a
polysemous word and use their related terms for query expansion [
2 http://greententacle.techfak.uni-bielefeld.de/~cunger/qald/index.php?x= challenge&q=2
Knowledge-based WSD approaches use dictionaries and lexicons such as
WordNet to perform WSD and are often considered a middle ground between
supervised and unsupervised approaches. Although graph-based approaches have
been gaining more attention recently for their high performance [
WordNet is the predominant resource used in such knowledge-based WSD
approaches; however, it has been argued that its ne granularity is the main
problem for achieving high performance in WSD [
Following [
Users exhibit a general preference for short NL queries, consisting of keywords
or phrases, as opposed to full sentences and a random query structure with no
speci c order for the query terms [
Named entities are recognised using AlchemyAPI4 which had the best NE
recognition performance in a recent evaluation of SOA recognisers [
For example, for the question \In which country does the Nile start?", the term Nile has di erent matches in BabelNet. These matches include: { http://dbpedia.org/resource/Nile (singer) { http://dbpedia.org/resource/Nile (TV series) { http://dbpedia.org/resource/Nile (band) { http://dbpedia.org/resource/Nile
Although one could select the last URI as an exact match to the query term, syntactic matching alone can not guarantee the intended meaning of the term, which is better identi ed using the query context. Using our WSD approach, we would select the correct match for Nile as a river since more overlapping terms are found between this sense and the query (such as geography, area, culture and continent ) than the other senses. 3.2
The second step is to parse the NL query, which is done using the Stanford
parser [
Equivalent output is also generated when using keywords or phrases. At the end of this step, any proper nouns identi ed by the parser and which were not recognised by AlchemyAPI as NEs are disambiguated as described in Section 2 and added to the set of recognised entities. This ensures that, for the example used above: In which country does the Nile start the algorithm does not miss the entity Nile because it was not recognised by AlchemyAPI.
The terms generated from the second step (Section 3.2) are then matched to
concepts and properties in the ontologies being used. Noun phrases, nouns and
adjectives are matched with both concepts and properties, while verbs are only
matched with properties. After gathering all candidate ontology matches that are
syntactically similar to a query term, these are then ordered using two string
similarity algorithms: Jaro-Winkler [
If a query term produces no matches, its lemma is used for matching. If no matches were found, derivationally related forms of the query term are then used. For example, the property creator in the question Which television shows were created by Walt Disney? is only found after getting these forms for the term create. After this, if no matches are found, the query term is then disambiguated using our WSD approach and terms related to the identi ed synset are gathered. These terms are used to nd matches in the ontology, based on both their level in the taxonomy (the nearest, the better) and in order of their contribution to the WSD as shown by the results of our experiments. Thus, synonyms are used rst, then semantic relations (the appropriate ones), followed by hyponyms, and nally hypernyms. For nouns, no semantic relations are used, while for verbs, see also is used and nally, for adjectives, attribute and similar to are used in that order. Indeed, the attribute relation is very useful for adjectives since, for example, the property height is identi ed as an attribute for the adjective tall, which allows answering the question \How tall is ...?". The query term is marked as not found if no matches were found after all expansion terms have been used. Note that we do not match superlatives or comparatives to ontology concepts or properties; they are used in the next step to generate the appropriate triples.
After all terms have gone through the matching process, the query can be interpreted in terms of a set of ontology concepts, properties and instances that need to be linked together. The structure of the ontology (taxonomy of classes and domain and range information of properties) in addition to BabelNet are used in this step, as will be explained next.
Three-Terms Rule Firstly, each three consecutive terms are matched (using the information about their relative positions as explained in Section 3.2) against a set of templates. The intuition is to nd a subject with a speci ed relation to a given object. Then, the ontology matches associated with each term are used to generate one or more candidate triples. For instance, the question Which television shows were created by Walt Disney? which can also be given as keywords television show, create, Walt Disney matches the template concept-property-instance and generates the following triples: ?television_show <dbo:creator> <res:Walt_Disney>. ?television_show <dbp:creator> <res:Walt_Disney>. ?television_show <dbo:creativeDirector> <res:Walt_Disney>.
Triples generated from the same query term are ordered according to the similarity of the matches found in them with respect to this term. In this example, the two properties dbo:creator and dbp:creator are ordered before dbo:creativeDirector5 since they have a higher similarity score with the query term create. Similar questions that would be matched to this template include airports located in California, and actors born in Germany. The other templates capture the di erent ordering that can be found in the query such as instance-property-concept in the question Was Natalie Portman born in the United States? or property-concept-instance in the question birthdays of actors of television show Charmed. Note that in the last example, since we identify the type of the instance Charmed as `television show', we exclude the latter during triples generation making it: birthdays of actors of Charmed.
Two-Terms Rule Some user queries contain fewer than three pieces of information, thus preventing the application of the Three-Terms Rule. This can happen in three situations: 1) no match between the derived terms and any three-term template; 2) the template did not generate candidate triples; or 3) there are fewer than three derived terms.
For example, the second situations occurs in the second part of the question In which lms directed by Garry Marshall was Julia Roberts starring? in which the terms Garry Marshall, Julia Roberts and starring would be matched to an existing template but without generating candidate triples. The requirement that the domain of the property (in this case: Film) must be the type of one of the instances was not met. In these scenarios, we follow the same process of template matching and triples generation for each pair of consecutive terms. For instance, the question area code of Berlin generates the triples: <res:Berlin> <dbp:areaCode> ?area_code. <res:Berlin> <dbo:areaCode> ?area_code.
Comparatives As explained earlier, superlatives and comparatives are not
matched to ontology terms but used here to generate the appropriate triples.
For comparatives, there are four di erent scenarios that we found from our
analysis of the queries in datasets used by di erent semantic search evalutions (e.g.,
Mooney dataset [
to: <http://dbpedia.org/property/> 6 http://greententacle.techfak.uni-bielefeld.de/~cunger/qald/ a comparative is used with a numeric datatype property such as the property numberOfEmployees in the question phrase more than 500000 employees. This information is known from the range of the property. In this case the following triples are generated: ?company <dbp:numEmployees> ?employee. ?company <dbp:numberOfEmployees> ?employee.
These triples are ordered according to their similarity with the original query term (employee) and a choice is made between using the best match or all matches depending on the priority of the algorithm (i.e., whether to favour precision or recall). The chosen triples are then added to the following ones: ?company a <dboCompany>.
FILTER ( ?employee > 500000)
The second scenario is when a comparative is used with a concept as in the example places with more than 2 caves. Here, we want to generate the same triples that would be generated for places with caves and add the aggregate restriction: GROUP BY ?place HAVING (COUNT(?cave) > 2).
In the third scenario, the comparative is used with an object property which, similarly, requires an aggregate restriction. In the example countries with more than 2 o cial languages, the following restriction is added to the normal triples generated between country and o cial language.
GROUP BY ?country HAVING (COUNT(?official_language) > 2)
The fourth and most challenging scenario can be illustrated by the question
Which mountains are higher than the Nanga Parbat?. The di culty here is to
identify the property referred to by the comparative term (which is `elevation'
in this example) to get its value for the given instance and then do a
comparison with this value. While [
Indeed, it is more challenging to identify this link between the term and the appropriate property for more generic comparatives like larger in the query cities larger than Cairo. Several interpretations arise, including area of the city, its population or density. The ability to resolve this scenario is future work. Superlatives For superlatives, we identi ed two di erent scenarios. Either it is used with a numeric datatype property such as in the example city with largest population, or with a concept as in what is the highest mountain. In the rst scenario, the normal triples between the concept city and property population are generated, in addition to an ORDER BY clause together with a LIMIT to return the rst result.
The second scenario is more challenging and similar to the last comparative scenario explained above and is indeed tackled using the same technique. All numeric datatype properties of the concept are identi ed and the most relevant one (identi ed by our WSD approach) is used in the query. Again, in this example, the term highest is successfully mapped to the property elevation.
The nal stage involves generating the SPARQL query by integrating the triples generated from the previous stages. Information about the query term position is used to order the sets of triples originating from di erent query terms. Furthermore, for triples originating from the same query term, care is taken to ensure they are executed in the appropriate order until an answer is found (when higher precision is preferred and thus not all matches are used).
For example, in the question Which software has been developed by organizations founded in California?, the terms in the rst part | software, developed, organizations | generate the following triples: ?software <dbp:developer> ?organisation. ?software a <dbo:Software>. ?organisation a <dbo:Organisation>.
And the terms in the second part | organizations, founded, California | generate the following triples: ?organisation <dbp:foundation> <res:California>. ?organisation a <dbo:Organisation>.
To produce the nal query, duplicates are removed while merging the triples and the SELECT and WHERE clauses are added in addition to any aggregate restrictions or solution modi ers required. 4
This section presents a comparative evaluation of our approach using the
DBpedia test data provided by the 2nd Open Challenge on Question Answering over
Linked Data (QALD-2). Results were produced by QALD-2 evaluation tool7.
7 http://greententacle.techfak.uni-bielefeld.de/~cunger/qald/index.php?x=
evaltool&q=2
Table 1 shows the performance in terms of precision, recall and f-measure, in
addition to coverage (number of answered questions, out of 100) and the number
of correct answers (de ned as P=R=(F1)=1.0). Our approach (SenseAware)
is compared with QALD-2 participants [
After excluding out-of-scope questions (as de ned by the organizers) and any containing references to concepts and properties in ontologies other than DBpedia since they are not yet indexed by our approach, we had 75 questions left. The 21 questions { out of 75 { that our approach couldn't provide an answer for fall into the following categories: 1. No matches were found for one or more query terms after query expansion. 2. Matches were found for all query terms but question type is out-of-scope. 3. Question requires higher level of reasoning than is currently provided.
Examples of the rst category are: What did Bruce Carver die from? and Who owns Aldi?, in which the terms die and owns should be mapped to the properties deathcause and keyPerson, respectively. Questions that are not yet addressed are mainly the ones which require identifying the right property to use depending on the answer type. An example is When was the Battle of Gettysburg? which requires using the property date. Another example is In which lms did Julia Roberts as well as Richard Gere play?. Here, our approach could not relate the concept films with Richard Gere. Although, it is designed to maximise the chance of linking concepts, properties and instances in the query, without being a ected with the sentence structure, this version cannot yet link a term ( lms) that is being successfully related to other terms (Julia Roberts ) to an additional term (Richard Gere). However, it can still solve complex questions that require relating terms that are not consecutively positioned (e.g., lms and Julia Roberts ) in the question In which lms directed by Garry Marshall was Julia Roberts starring?. Finally, examples of questions in the third category are Is Frank Herbert still alive? which requires understanding that the expression still alive means not nding a value for the death date of the person.
In designing an approach to answer user questions, it is usually di cult to decide
whether to favour precision or recall, since it is well known that an increase in
one commonly causes a decrease in the other. In fact, which to favour depends
not only on the users but on their speci c information need at some point. We
experienced this while designing our approach since we had to decide on the
following choices to be in favour of precision or recall:
Query Relaxation Consider the question Give me all actors starring in Last
Action Hero. This question explicitly de nes the type of entities requested as
actors which justi es querying the dataset for only this type. Hence, we would
add the triple: ?actor a <dbo:Actor> to restrict the results generated from:
res:Last Action Hero dbp:starring ?actor to only these who are actors.
However, the current quality of Linked Data would be a major problem with
this choice, since not all entities are typed [
In this paper, we have presented a NL semantic search approach to answer
user queries expressed in their own terms and format. The main steps of the
approach are recognising and disambiguating named entities in the query;
parsing and matching the rest of the query to ontology concepts and properties;
and, nally, generating triples from these matches and integrating them to form
the nal SPARQL query. Using BabelNet in our WSD approach allowed high
performance disambiguation of polysemous query terms and therefore, when
required, produced highly relevant terms for query expansion. Together with a set
of SOA string similarity algorithms and ltering techniques to produce
accurate mappings for query terms, we have shown that our approach's performance
is competitive (especially in the number of questions answered correctly: 76%)
when evaluated using the QALD-2 dataset. We have also discussed challenges
facing our approach (which are in common with many NL approaches). Query
terms that are very di cult to be matched to the ontology or queries
requiring advanced reasoning would, indeed, require a `user in the loop' to assist the
system in addressing these challenges. This agrees with our recommendation [
Elbedweihy et al.