Survey Of Natural Language Interfaces To Ontologies

Introduction

The Semantic web is a group of methods and technologies to allow machines to understand the meaning - or “semantics" - of information on the World Wide Web. This concept was coined in the arisal of the Web 2.0, when experts of the field tried to see where the web technology will go in the future. The way to represent this information is through ontologies, which are a formal representation of the knowledge by a set of concepts within a domain and the relationships between those concepts. As the W3C started developing the formats for the semantic web, like the Resource Description Framework (RDF) in 2004, or the Web Ontology Language (OWL), efforts to store human knowledge in a machine-understandable format have increased, and thus different methods to interact with this knowledge have arisen. In this survey paper, we present systems that serve as a natural language interface to these knowledge bases, trying to tie the need of end-users to access these information with its availability through the Semantic Web.

As of today, the majority of information stored in ontologies is only accessible through complex query language operations, such as the ones defined by SPARQL or other ontology query languages. In order to have this information available to users without knowledge about these query languages, we need a simpler, more “humane" approach to query them, as it has happened in the web with the advent of keyword-based search engines. Since in the field of the semantic web, semantic information about the stored knowledge is on the hands of the interface engine, it makes sense to develop a natural language interface exploiting this semantic metadata to extract the meaning of the questions presented to the system. In this way, an useful answer to the end user can be presented with minimum effort on his side, by only having to use the same language he does to communicate with others. This natural language interfaces are as useful in a traditional context (textual queries through a computer) as they can be in one were voice is used as a major interface to the system (using a speech-to text translation), as the increasingly popular mobile devices like smartphones and tablets are starting to be.

The systems presented in this paper are related to the natural language interfaces to databases that have been developed in previous years. CHAT-80 [Warren:1982:EEA:972942.972944] was a system developed in the early eighties that transformed English questions into Prolog expressions, which were evaluated against the Prolog database; and that served as the basis of other NLIDB systems like MASQUE [Ritchie93masque/sql--an]. Later on, TEAM [Grosz:1987:TED:25672.25674] was developed as a NLIDB system with portability in mind, so that it could be easily configurable by database administrations to act as an interface to their database. Many other similar systems were developed in the eighties, like ASK [Thompson:1983:IAS:974194.974198], JANUS [Weischedel89ahybrid], or DATALOG [Hafner:1985:PSS:3914.3982], each having its particularities and solving different problems in the field, but the interest in this systems fell by the middle of the nineties, as the databases became more complex and so its information not being as useful in a direct way to end users. However, the basis of their development was used as inspiration for the systems introduced in this paper, as can be seen in the references made to some of them in these articles.

The conferences where these papers have been presented, and where this field is currently discussed, are the International Semantic Web Conference (ISWC), the Annual Meeting of the Association for Computational Linguistics, the Conference on Intelligent Text Processing and Computational Linguistics, the International Conference on Language Resources and Evaluation (LREC), the Extended Semantic Web Conference (ESWC), the Semantics, Knowledge and Grids Conference (SKG), the International Symposium on Natural Language Processing, and the International Conference on Natural Language Processing and Knowledge Engineering.

In this paper, we intend to summarise the current state of the natural language interface systems to consult ontologies. We first introduce some terminology to acquaint the reader to the jargon of the field; afterwards, we present the research challenges existing on the field, and the different ways each paper tries to solve them, analysing their approach taking into account the translation type, the user feedback and the learning process used; following this, we explain the guidelines we will follow to classify and analyse each paper, and present the summary of each of the eleven studied papers according to this system; and finally, we extract the conclusions that arise from the study of these, trying to show where will this field lead us in the future.

Terminology

We introduce some terminology of this field to help the understanding of the survey:

Natural Language: A human written or spoken language, as opposed to a computer language. Due to its natural evolution and general use, it lacks the definition and unambiguousness of computer languages.

Ontology: a formal representation of the knowledge of a set of concepts within a domain and the relationships between those concepts. It is used to reason about the properties of that domain, and may be used to describe the domain. They are used in artificial intelligence, the Semantic Web, systems engineering, software engineering, and more fields. They are formed by classes, atributes of these classes, relations between classes, and instances of these classes; and they follow a triplet structure: subject-predicate-object (explained below). The more common ontology languages used to describe them are OWL, RDF and F-Logic. Some known ontologies are Dublin Core, DOLCE, Wordnet, or CIDOC CRM.

SPARQL: SPARQL stands for SPARQL Protocol and RDF Query Language, it is an RDF query language to query ontologies in RDF. A query consists of triple patterns, conjunctions, disjunctions, and optional patterns. Example for question: “What are all the country capitals in Africa?":

PREFIX abc: <http://example.com/exampleOntology#> SELECT ?capital ?country WHERE ?x abc:cityname ?capital ;      abc:isCapitalOf ?y .   ?y abc:countryname ?country ;      abc:isInContinent abc:Africa .

Triplet: A triple is the basic element of an ontology, consisting of a subject, a predicate, and an object, such as “Bob is 35" or “Bob knows Fred".

RDF: The Resource Description Framework , a metadata data model used to describe ontologies. The predominant query language for RDF graphs is SPARQL.

WordNet: lexical database for the English language, which groups English words into sets of synonyms called synsets, to support automatic text analysis and artificial intelligence applications. As of 2006, the database contains 155,287 words organized in 117,659 synsets for a total of 206,941 word-sense pairs.

Research challenges

The main goal of all of these papers is creating a natural language interface for accessing knowledge stored in ontologies. This is desired because even though the resources of the semantic web are growing each day, the way to access them as an end user keeps being complicated, having to learn a query language such as SPARQL or RDQL. By creating a way to query these ontologies with natural language, all this knowledge is made accessible to end users.

Since we would want access to an arbitrary number of different knowledge bases, a domain-independent system is needed, because having to develop or adapt a system for any ontology is not feasible. Most of the papers selected solve this problem by integrating the ontology domain information in an automatic way, apart from Aqualog, that has to be configured manually in a minimal way by the configuration files, and Orakel, that uses the Frame Mapper tool to ask the user about the mapping of verbs with relations in the ontology.

The way to accomplish this translation is different in each paper, but they share common characteristics and thus they can be grouped by their Translation type: Grammatical: ACE, Aqualog, Ginseng and Orakel use grammars with general rules and domain-dependent rules from the ontology to parse and convert the question into a ontology language query. The intermediate representation of the query is usually a tree, where the words in it are related to the concepts in the ontology. Heuristic: Querix, NLP-Reduce, Nokia NQ, QuestIO, FREyA, Panto and NLION use different heuristic methods to match the concepts in the question to the ones in the ontology. These methods normally consist of concept matching using the ontology concepts augmentated with synsets in a single or multipass scheme.

Since the translation of the natural language question into an ontology query may not always be perfect, some systems have implemented disambiguation schemes via user interaction, like QuestIO, where the possible matchings are ranked and then presented to the user, or Aqualog or FREyA, were individual concept matchings are asked to the user if they are not unambiguous. Ginseng is a special case in this topic, because its interface consists of text entry via guided input, and so it resolved ambiguity by not letting the user input questions that will not be answered in an unambiguous way.

Learning from the user disambiguations to help answering future queries is also interesting in these systems, in order to overcome the non exact mappings between user questions and ontology queries due to the natural language implied complexity, self reference and ambiguity. This is implemented in FREyA and Aqualog, using the disambiguated terms by the user and taking the context into account to disambiguate future queries in an automatic way; which makes the system's performance better as more questions are processed. Orakel also enables a user-assisted learning process, where non answered queries can be logged and the concepts not correctly matched shown to the lexicon builder to extend the lexicon to cover these terms.

Finally, another way to control the user's input to ensure that an answer will be found, is by restricting the input language to a set smaller than the full English language. The ACE system does this by using the Attempto Controlled English language as its input, which is a variation of English were there are no ambiguities in the relation between subjects and objects in the sentences. Another way of doing it by guiding the user's input to avoid ambiguity, like Ginseng uses, as explained above.

Classification of the papers

Taking into account was has been explained in part 3, we will classify the papers by the characteristics that arise from that development, which are the following ones:

Translation type: The query issued by the user needs to be interpreted in terms of the onbtology concepts and translated to a formal query that can be executed on the ontology. This translation may be performed using a natural language grammar to translate the user query into an ontology query, or by using heuristic matching to match ontology concepts to concepts in the question. Intermediate representation: The intermediate representation used for the query while in the translation process. This structure gives us information about the translation process. Examples range from trees, set of triples, graphs, or set of concepts. Domain knowledge: The information about the domain that the ontology covers has to integrated in the system to correctly understand the users' queries. This domain knowledge can be used in the system in a manual way, like it was done in the first systems; manually but assisted by the user, like in the Orakel system; or in an automatic way. The manual way has a greater cost associated with it, which is the time and knowledge the integrator invests on it, but may lead to better results; while the automatic way is faster and cheaper, but can lead to imprecisions if not well done, and it depends on the semantic richness of the ontology. User feedback: The systems can interact with the user in the process of the translation of the query or while presenting the result, for various reasons. Some systems use user feedback for disambiguation of concepts in the questions, or refinement of the answers given multiple choices, and this user feedback can also be further used for learning. Learning: The user feedback can be used to make the system learn from previous queries, refining its answers based on the context of the question. Here we state the type of learning that the system uses, if available. Input language: The input language of the system, the one the user uses to write the query. It can be full English, or a controlled version of it, or even a guided input approach that limits the vocabulary.

We will summarise the systems by giving the basics of its architecture, and by showing its interesting features that differentiate them from the rest. We also show how they were evaluated, giving details on the tests used (questions, precision and recall), and finally we show a table with all this data for easy comparison. The papers are presented in chronological order, to get a grasp of the evolution of the topic.

Reviews of the papers

Querying Ontologies: A Controlled English Interface for End-Users

Translation type: Grammatical, rules extracted from the ontology's vocabulary and general rules Intermediate representation: Discourse Representation Structure → rules based representation Domain knowledge: manual User feedback?: no Learning?: no Input language: Attempto Controlled English

System architecture

The ACE [Bernstein05queryingontologies] paper, by Abraham Bernstein, Esther Kaufmann and others, introduces us to a controlled english interface to ontologies using the Attempto Controlled English (ACE) language [fuchsnua99ace3Mal]. This system works by parsing the query with the Attempto Parsing Engine, which converts it into a discourse representation structure; rewriting it with the Rewriting Grammar, (generated from rules of the domain model and general purpose rules), which produces a triplet-style PQL-Query; and finally querying the ontology with the afforemented query.

Features

This system has two interesting parts, which are explained below:

Attempto Controlled English The Attempto Controlled English is a controlled natural language and a subset of the English language. It is specified by a set of construction rules, which allow users to build simple, composite sentences, and queries, and interpretation rules, which eliminate syntactic and semantic ambiguities.

The queries done to the system are translated into a discourse representation structure by the Attempto Parsing Engine, that is implemented in Prolog as a Definite Clause Grammar. The DRSs consist of discourse referents, and conditions for them. Here is an example of one translation:

Rewriting grammar The Rewriting grammar converts the DRs into PQL queries using two types of rewriting rules, ontology-model specific keyword rules, and general vocabulary rules. These rules are stated in the following way:

Ontology-Model Specific Keyword Rules: These rules apply if one of the keywords of the ontology (or a synonym) appears in the DRS. If it does, then it is translated into a part of a PQL query. For example, if the ontology has a property called HAS-PORT, having the query “Which process has a port" will fire one of this rules giving the PQL query “?process <#has-port> ?port".

General Vocabulary rules: The parts of the DSR not handled by the ontology specific rules are processed by the general vocabulary ones. These rules fire depending on if the query is a simple or complex sentence, of its complement or adjunt clauses, and so on. The full rule tree of the grammar can be seen here, relating to the query “Which service shows the menus of the campus restaurants over the internet?"

After these rules are applied, some post processing is done to simplify the query, via the post processing rules.

Testing

This system was tested by 20 end-users, which were asked to phrase ACE queries (after receiving a short document explaining it). 30 queries were generated, and when ran in the system (after slight manual ACE corrections), they achieved a precision of 100% and a recall of 90%. The authors also compared the system with an SQL based one by making the end-users rephrase the queries in both languages, and found out that overall, people preferred ACE over SQL; and also tried more complex questions, receiving satisfactory answers, which speaks of the potential of the system.

Aqualog

Translation type: grammatical, using JAPE grammars and the RSS Intermediate representation: triple-based data model Domain knowledge: yes, automatic and manual in the configuration files User feedback?: Yes, for disambiguation Learning?: Yes, from the users' clarification Input language: English

System architecture

AquaLog [Lopez05aqualog:an], by Vanessa Lopez, Michele Pasin and Enrico Motta, is a portable question-answering system which takes queries expressed in natural language and an ontology as input, and returns answers drawn from one or more knowledge bases. Its architecture goes as follows:

A query made by the user is transformed by the Linguistic Component to a set of triples, using GATE [Cun02b] libraries and other semantic modules, like the JAPE grammars. It is then processed by the Relation Similarity service (RSS), which converts it to a query to the ontology(es) using the Class Similarity Service, string pattern libraries, the WordNet thesaurus, and other RSS modules. This ontology query is processed by the knowledge base and it is finally presented to the user as the answer to his question. All this process is being helped by the user's feedback in case of ambiguity, which is further used to expand the vocabulary by learning from it.

Features

The Linguistic Component and the Relation Similarity Service (RSS) are the two central components of AquaLog, and together with the Leaning Mechanism, they form the defining characteristics of this system. We present these features below.

Linguistic Component The Linguistic Component’s task is to translate from NL to the triple format used to query the ontology. This component first uses the GATE processing resources for tokenizing, splitting, POS tagging, and VP chunking the query. Afterwards, a set of JAPE grammars (offered by GATE) are used to identify the intermediate representation that need to be used from 14 question types. This component is prepared to work with basic queries, basic queries with clauses (queries with modifiers, which have to be disambiguated using the ontology or user feedback), and combination of queries (which can be conjunctions or conditional queries). Some query→triple pairing can be seen as an example in img5:

Relation Similarity Service The RSS is used to process the triples generated by the Linguistic Component: it tries to make sense of the input query by looking at the structure of the ontology and the information stored in the target ontology(es), as well as using string similarity matching, generic lexical resources such as WordNet, and a domain-dependent lexicon obtained through the use of a Learning Mechanism. This process is interactive, because the user is asked whenever an unsolved ambiguity arises. The relation and concept names are mapped from the ontology using the Class Similarity Service, which is based on several string distance metrics using an external API from Carnegie Mellon University [Cohen2003].

Learning Mechanism

When an user is asked about an ambiguity that has arisen in the processing of their query, its answer is recorded in a database together with a series of constraints (the arguments of the question, the name of the ontology and the user information) that will determine its reuse within similar contexts. These answers are later used in following user questions if they adapt to the current context, which is calculated by generalization algorithms depending on the topic of the question and the user asking it.

Testing

Aqualog has been thoroughly tested, and can be evaluated by the reader here: http://aqualog.open.ac.uk:8080/aqualog2/index.html, or by downloading the source code from their repository: http://technologies.kmi.open.ac.uk/aqualog/aqualog_libraries.html.

In their tests they found five kinds of failures that a query may find: Linguistic failures, when the NLP component is unable to generate the intermediate representation; Data model failure, when the NL query is too complicated for the intermediate representation; RSS failure, when the Relation Similarity Service is unable to map an intermediate representation to the correct ontology-compliant logical expression; Conceptual failure, when the ontology does not cover the query, and Service failure, when there is a lack of appropriate services defined over the ontology.

From the 69 questions they used to test the system, here are the results they found:

They also tested the learning mechanism by running the same questions with and without this component, and over several iterations. Here are the results:

Ginseng

Translation type: partially dynamically generated multi-level grammar Intermediate representation: grammar tree Domain knowledge: yes, for the grammar rules and vocabulary User feedback?: yes, guided input Learning?: no Input language: English, guided input

System architecture

Ginseng [Bernstein05queryingthe], by Abraham Bernstein, Esther Kaufmann and Christian Kaiser, is a guided input natural language search engine for the Semantic Web. It works trough a simple querying grammar which is dynamically extended based on the ontology structure, and then used to parse the queries. These queries are incrementally parsed in order to propose possible continuations of the query. Here is a visual example of the query input process:

The only vocabulary is the one defined by the loaded ontologies, complemented with synonyms. The guided way of inputting a query is similar to the autocomplete features is CLIs.

Once a query is fully entered the system uses additional query construction information to translate it into a RDF Data Query Language (RDQL) (http://www.w3.org/Submission/2004/SUBM-RDQL-20040109/) query and then executes it. Therefore, the Ginseng system has three parts: a partially dynamically generated multi-level grammar, an incremental parser, and an ontology-access layer. The last one is done using the Jena system (http://jena.sourceforge.net/). The other two parts are explained below:

Features

Partially dynamically generated multi-level grammar When an ontology is loaded, its dependent rules are generated to extend the static part of the grammar, which contains the ontology-independent rules specifying general sentence structures. These grammar rules are divided in two parts, the static ones, which provide the basic sentence structures and phrases for questions, be them yes/no, cardinality, conjunctive or disjunctive ones; and the dynamic ones, which are generated from the ontologies by parsing the classes, instances, objects and data properties. Here is an example of one of the grammars generated by Ginseng, where the terminals of the rules are the entries suggested in the guided input process, and the information following the | signs is the one used to create the RDQL queries:

Incremental parser The grammar rules presented above are used by the incremental parser in two ways: they specify the complete set of parsable sentences, which can be used to provide the user with alternatives during entry and prevent incorrect entries, and they provide the information on how to construct the RDQL queries. Therefore, the incremental parser works in the guided input section, and also in the query generation part.

Testing

To test the Ginseng system the developers ran all the 880 queries from the geographical Mooney knowledge base, and found that, out of the 40% of the queries that could be executed without modification had a precision of 92.8% and a recall of 98.4%. They were only able to test 40% of the questions due to the guided approach of the query entering system, which restricts the input domain. They also ran usability tests comparing Ginseng and SQL with IT students, and found that Ginseng was quicker and easier to use than SQL.

Querix

Translation type: with heuristic patterns on the syntax tree Intermediate representation: syntax tree, triples Domain knowledge: yes, in the matching center User feedback?: yes, final disambiguation Learning?: no Input language: English

System architecture

Querix [Kaufmann06querix:a], by Esther Kaufmann, Abraham Bernstein and Renato Zumstein, is a domain-independent natural language interface that uses clarification dialogs to query ontologies. The system consists of seven parts: a user interface, an ontology manager, a query analyzer, a matching center, a query generator, a dialog component, and an ontology access layer. These parts are presented in the “features" section below.

Features

Ontology Manager: enhances the resources of the ontology with synonyms from WordNet.

Query Analyzer This part of the system uses the Stanford Parser [klein03fast] to build a syntax tree of the query, which is then used to build a query skeleton using these categories: Noun (N), Verb (V), Preposition (P), Wh-Word (Q), and Conjunction (C). These skeleton is also augmentated with synonyms from WordNet.

Matching Center It is the core component, it tries to match the skeleton with the ontology triples in a three step process: 1. Matches against a small set of heuristic patterns, so that it identifies subject-property-object patterns of a query. They overlap in their first or last word category to enable the joining of the triples in step 3. 2. Searches for all matches between the synonym-enhanced nouns and verbs of the input query with the resources and their synonyms in the ontology. 3. Matches the triple patterns from step 1 and the resources from step 2, taking into account the domain and range information of the ontology.

Query generator: It composes a ranked list of SPARQL queries from the joined triples. using the cost function of the matching steps.

Dialog component: If two SPARQL queries have the same cost, this component asks the user for the answer he wants with a dialog box.

Ontology access layer: To execute the generated SPARQL query, Querix uses Jena as ontology access layer and the Pellet reasoner. It then presents the answer to the user.

Testing

The Querix system was tested with 215 of the 879 queries of the Mooney database, being this subset the syntactic representation of the total. Of these questions, after removing 21 of them due to problems in the parsing, its semantics, or mistakes in the ontology, a precision of 87,11% and a recall of 86,08% was obtained. This shows, according to the authors, that Querix, even though depending on the quality of the vocabulary of the ontology, shows good results while having the advantage of being completely portable.

NLP-Reduce

Translation type: “naïve", matching triples with words recursively Intermediate representation: triples Domain knowledge: yes, for the query generator User feedback?: no Learning?: no Input language: no

System architecture

NLP-Reduce [Kaufmann_Bernstein_Fischer_2007] by Esther Kaufmann, Abraham Bernstein and Lorenz Fischer, is a naive but domain-independent natural language interface for querying Semantic Web knowledge bases (KBs). It consists of five main parts: a user interface, a lexicon, an input query processor, a SPARQL query generator, and an ontology access layer. All of them except the query generator are pretty straightforward: the lexicon uses WordNet for synonyms of the ontology terms and the Porter Stemmer for stemming them; and the input query processor removes stop words and punctuation marks. The main part of the system is the query generator, which is explained below:

Features

Query Generator The query generator matches the query words to the synonym-enhanced triples stored in the lexicon and generates SPARQL queries for the matches. It does this on a four step process: 1. Searches for triples in the lexicon in which at least one of the query words occurs within the label of an object property. It then ranks the found triples favoring those that cover more words and those that have words which stems show a better agreement with the query words over others. 2. Searches for properties in the lexicon that can be joined with the triples found in step 1 by the remaining query words taking domain and range information into consideration. Then they are combined with the result of step 1. 3. Searches for all datatype property values that match the remaining words of the query. 4. Generates the corresponding SPARQL query for the join of the retrieved triples that achieved the highest scores in steps 1 to 3. It also removes semantically equivalent duplicates and passes the SPARQL query to the ontology access layer.

Testing

NLP-Reduce was tested with two Mooney knowledge bases: 251 questions of the restaurant KB, 192 answered (94,6%), 67,7% precision, 69,6% recall 879 questions of the geography KB, 308 answered (66%), 70,7% precision, 76,4% recall The precision an recall were calculated in an strict matter, where if the answer was not exactly what should be, scored 0%. They arrive to conclusions similar to the ones of the Querix paper.

Nokia NQ

Translation type: multipass refinement using language tags Intermediate representation: Abstract and concrete (subgraph) semantic interpretation Domain knowledge: yes, for the semantic tagging User feedback?: no Learning?: no Input language: English

System architecture

The Nokia NQ [Ran07naturallanguage] system was developed by Alexander Ran and Raimondas Lencevicius with an interest in using language based interaction on mobile devices, and so it was optimized to increase portability, limit computational complexity of the language components and maximally automate the process of integration between language systems and databases. The system processes a natural language question in five stages: semantic tagging, parsing, abstract semantic interpretation, concrete semantic interpretation and heuristic ranking.

Features

Semantic tagging It performs two functions: value tagging: marks tokens in the question that correspond to values in the database, and includes recognition of expressions for regular ordered value types such as numbers, time, and date.

Category tagging Identifies potential references to database entities such as classes and properties, using “language tags”, which are linguistic labels attached to the database elements to generate information about terms that might be used to refer to the database items.

Parsing The parser has no domain dependency. It parses the question and process it so that taggings that do not produce a parse are rejected; alternative parses are ranked (if a probabilistic model is available); and the focus of the question and most probable attachment of the phrases are identified.

Abstract semantic interpretation With the information added by the semantic tagging and parsing of the question, an abstract meaning representation is generated using binary infix predicates. This representation does not use the same property names as the database, so it requires further interpretation by processing the “semantically related" entities: if we see the ontology as a graph, for two nodes n1 and n2 of it, they are semantically related over selected class and predicate domain D if there exists a path of predicates from D that connects these nodes.

Concrete semantic interpretation This section of the system converts the abstract meaning representation to a formal database query by adding information about the organization of the database. It does this by generating a set of possible concrete semantic interpretations gotten through searching the database graph identified by the abstract meaning representation.

Heuristic ranking Finally, the set of subgraphs is ranked in terms of suitability as a concrete semantic interpretation of the question. It is done in a domain independent way via: the semantic relatedness rule (introduced before); the active voice rule, where the language tags describing a relation are required to be used with active voice of verbs; and taking into account the weight of retrieved subgraphs, which negatively correlate with their appropriateness as semantic interpretation of the question.

Testing

The NQ system was tested over different semantic repositories, including personal information databases, intranet corporate phonebooks, the CIA World Factbook, and a job search repository. The most extensive experiment was in this last one, where 200 questions were executed against the system and returned precision and recall close to 100%.

ORAKEL

Translation type: Grammatical, using Logical Description Grammars Intermediate representation: LDG trees Domain knowledge: manual, with the FrameMapper tool User feedback?: no Learning?: manual using feedback from wrong questions and FrameMapper Input language: English

System architecture

Orakel [Cimiano07orakel:a], by Philipp Cimiano, Peter Haase and others, is a natural language interface to knowledge bases, using a lexicon built by hand for the ontology in use, and using an inference engine to provide answers not included in the KB but that can be inferred from them. The system architecture is the following one:

In the case of an end user, he asks a question that is semantically interpreted by the Query Interpreter, which parses it and constructs the query in a first order logic logical form, using the domain-independent lexicon (from the DOLCE ontology [DOLCE2003]) and the one provided by user input from the FrameMapper. This form is then converted to the knowledge base query language by the Query converter, using a Prolog description of it. Finally, the answer generation component evaluates the query with the KB and returns the answer to the user. In the case of the lexicon engineer, he uses the FrameMapper interface to the KB, which supports him in specifying by graphical means the mapping from language to relational predicates defined in the knowledge base. This interaction generates the domain lexicon specific for the application in question.

Features

Query Interpreter ORAKEL uses Logical Description Grammars (LDG) as the basis of their system. which are trees consisting of nodes labeled with syntactic information. The nodes of these trees can be marked negatively if they correspond to arguments which need to be inserted, or positively if they denote variables to be inserted as an argument. The operation applied to these trees consists of identifying positively with negatively marked nodes with each other within one or across trees. The nodes are matched if their feature value pairs match, which are the head, genus, function and type. The verbs are then represented by subcategorization frames, which is the verb and the arguments needed for it; the names, pronouns and prepositions correspond to elementary trees, and the adverbs and adjectives to trees with them in one leaf and their corresponding matching category in the other. The parser used identifies positively and negatively marked nodes respecting: the syntactic category of nodes, feature values, ontological constraints, surface word order, and syntactic dominance relations. It is an Early-type bottom-up parser using top-down information, the full pseudocode of it can be seen in the paper. Finally, the logical formula of the input question is constructed using lambda calculus, with an extended compositional operator. Their implementation can be seen at www.cimiano.de/orakel. For treating inference, inferencing rules can also be added to the ontology to infer implicit relations, like stating that a river x flows through a location z if x flows through y and y is located in z : ForAll x, z flow_through(x, z) <- Exists y flow_through(x, y) AND location(y, z).

Query Converter The first order logic query obtained by the query interpreter is translated into the logical language of the database using a translation component specified declaratively in Prolog. Therefore, a query can be converted into different query languages (F-Logic for the Ontobroker system, SPARQL for OWL)depending on the translator, as long as the query language provides extra-logical predicates for counting and for numerical comparisons, and its reasonably expressive.

FrameMapper Part of the domain-dependent lexicon is generated automatically by reading all the concepts and instances of the ontology and generating grammar trees representing them using their labels. The other part is generated by the user with the FrameMapper tool, by mapping verbs, adjectives and relational nouns to corresponding relations specified in the domain ontology. This is done by instantiating subcategorization frames and mapping these to domain-specific relations in the ontology. Examples of these mappings can be seen below:

location(pcomp(of): x) -> locatedIn(x: location, y: location) live(subj: x,pobj(in): y) -> inhabitants(y: state/city, x: integer) capital(pcomp(of): x) -> capital(x: city, y: state) pass(subj: x, pobj(through): y) -> flow through(x: river, y: city) pass(subj: x, pobj(through): y) -> located at highway(y: city, x: highway) border(subj: x, obj: y) -> borders(x: location, y: location) adj(big,bigger,biggest,positive) -> inhabitants(city,integer)

These mappings are crucial to ORAKEL, since it does not use simple heuristics based on matches between relation names and verbs or nouns like other systems, opting for the user input for these mappings instead.

Testing

To evaluate the system, the authors provided three different tests: 1. Test with a geography KB, using a lexicon built by the author, and other two lexicons built by end-users (in two iterations, using the failed questions for feedback). A total of 454 questions were asked to the system by end-users, with a precision of about 82% and a recall of about 48%. The question types were also analysed, and they found that the system had a coverage of 93%, and that they could add the question types not covered to the system. 2. Runtime evaluation, depending on the length of the question. The time taken for answering a query went from 0,01s for 3 word questions to a max of 0,56s for 13 word questions. Therefore it was concluded that ORAKEL can answer questions in real time. 3. Real-world application of the system, by adding a natural language interface to BT's digital library described by the PROTON ontology (http://proton.semanticweb.org/), which was much bigger than the one used in the previous experiment. The lexicon was created using FrameMapper in 6 hours, and after three iterations, the questions asked by end users got a precision of 73% and a recall of 61%.

Panto

Translation type: NPs to QueryTripes to OntoTriples Intermediate representation: QueryTriples and OntoTriples Domain knowledge: in the lexicon User feedback?: no Learning?: no

Input language: English

System architecture

Panto [Wang07panto], by Chong Wang, Miao Xiong and others, is a Portable nAtural laNguage inTerface to Ontologies. Its system architecture is the following one:

It consists of two parts, the Ontology processing, where the lexicon is built (composed of the ontology entities (classes, properties and instances), general dictionaries (using WordNet synsets), and user defined synonyms); and the Query Processing, which translates natural language questions into SPARQL queries. This is done by parsing the question with the Stanford parser, and then sending the parse tree to the core processing engine of the system, the Translator. Here is where the parsed queries are converted into SPARQL, and will be explained in more detail below.

Features

Translator The translator works on the basis that nominal phrases (phrases consisting of a subject, verb, and object) can be translated into triples that follow the ontology structure. The full translation process can be visualized here:

1. QueryTriple Extractor This section extracts the nominal-phrase pairs of the parse tree to form QueryTriples. It does it in the following steps: First, since the nominal phrases (NPs) can be nested, it identifies the baseNPs of the query, and then identifies and propagates the related NPs following the rules stated by Michael Collins [Collins]. Second, it links the BaseNPs with one another where there is modification relationship to form BaseNP pairs. The two BaseNPs in such a pair, together with the words which syntactically connect them, form a QueryTriple. Finally, it specifies the internal structure for QueryTriple, separating its subject and object into a structure such as [pre-modifier . head noun . post-modifier].

2. OntoTriple Extractor Here the QueryTriples are mapped to the OntoTriples that correspond in the ontology. It does this by mapping the QueryTriples subjects and objects to entities of the ontology using the lexicon using semantic (synonyms) and morphological (string metrics or heuristic rules) matching; and then uses this information to match each QueryTriple to one or more OntoTriples (triples that are compatible with some statements in the ontology), depending on its type.

3. Target and Modifier Extractor The parameters for the SELECT part of the SPARQL query are extracted here, by finding the wh-word or an imperative verb of the question (“list", “give me", etc), and using the nouns in the same or the directly followed constituent as targets. The FILTER part, if necessary, is also produced here, by processing the modifier indicators, which are negating, superlative, comparative or conjunctive/disjunctive words in the query.

4. SPARQL Generator Here the targets extracted in the previous phase are related to the OntoEntities and OntoTriples for the SELECT; the OntoTriples are directly interpreted as triple patterns for the WHERE clause, making instance and property entities as URIs in the ontology, and class entities or RDF Literal Type entities as variables; and the FILTER clause is created using the information from step 3 depending on the indicator type. With all the SPARQL query parts created, the query is finished.

Testing

The authors tested Panto with the Mooney database with 877 geographical questions and 238 restaurant ones. They got a precision of 88,05% and 85,86%, and a recall of 90,87% and 96,94%, which gives an average precision of 85,58% and an average recall of 92,16%. They also note that Panto's coverage is about the same as Aqualog's, and that all the questions from the Mooney database were accepted by the system.

QuestIO

Translation type: matching concepts with relations in the ontology Intermediate representation: ranked relations and key concepts Domain knowledge: in the initialization process User feedback?: no Learning?: no Input language: English

System architecture

QuestIO [Damljanovic08k.:a]: Question-based Interface to Ontologies, is a system for querying ontologies using unconstrained language-based queries, and it is domain independent, easily embeddable and requires no end-user training. The system architecture for answering a query is shown below:

Each user query is interpreted using the Query Interpreter in the User Interface. It is then analysed by two components: the Key Concept Identification Tool (KCIT) identifies key concepts inside the query, which refer to mentions of ontology resources such as instances, classes, properties or property values. The Context Collector collects all words from the query that are not recognised by KCIT, but could be useful in the process of generating the formal query, which are prepositions, to be used when analysing the direction of a supposed relation between the two concepts; keyphrases like, for example “What are", “What is" or “How many"; and chunks, which are any part of a query that is between two identified key concepts, used later in the relation ranking process. It is then processed by the query analyzer, explained in the features section, and a SeRQL query is created dynamically. The answer retrieved by running the query is then shown to the user.

Features

Automatic domain knowledge extraction When the system is initialized, it preprocess the ontology resources (classes, instances, properties and property values) and extract any human-understandable lexicalisations. They are then analysed by the OntoRoot Application, which tokenizes them, and assigns parts-of-speech and lemma information to each one to form a gazetter.

Query Analyser

Filtering concepts: When identifying key concepts, more than one annotation can appear over the same token or a set of tokens, which needs to be disambiguated: this is done by giving priority to the longest matching annotations. This rule is based on the assumption that longer names usually refer to the more specific concepts or instances whereas shorter ones usually refer to more generic terms.

Identifying relations between key concepts: The system retrieves and analyses potential relations between identified key concepts, based on the defined relations in the ontology. To retrieve these relations it uses the ontology-based reasoning provided by the reasoning component

Ranking potential relations: Retrieved relations are then scored using a combination of three factors: the similarity of the relation’s name with the part of the query; the specificity score, calculated in relation to the position of the property in comparison to other existing properties in the ontology hierarchy; and the distance score, which reflects the position of the domain and range classes of the property inside the ontology hierarchy.

Testing

The creators of QuestIO compare it to Aqualog running 22 questions on both systems and stating which ones were correct, correct after reformulation, partially correct, and wrong:

They also tested the portability and scalability of the system by checking it with two overlapping knowledge bases of different sizes, where one has about 40 times more resources than the other. The questions asked had the same answer in both, since one is a subset of the other. The results in initialization time and execution time of different queries can be seen below:

NLION

Translation type: Semantic Relation Tagging Intermediate representation: list of PCE and PPE tress Domain knowledge: in the SRT User feedback?: no Learning?: no Input language: English

System architecture

NLION [RamachandranK09] by Vivek Anandan Ramachandran and Ilango Krishnamurthi, is a Natural Language Interface for querying ONtologies, and uses semantic relation tagging (SRT) to convert NL queries to SPARQL. The architecture of the system is as follows:

When the user submits a query in the form of NL to the system, it accepts and it expands it using spell checks, stemming, and words merging, Then, SRT is performed on it, and the result is passed to the SPARQL generator, which is then processed by the ontology engine and its output displayed to the user. The interesting part of this system is the Semantic Relation Tagging, which is explained below:

Features

Semantic Relation Tagging and Structure Recognition Each word in the query is tagged by NLION with a label indicating if it is a possible concept (PCE), possible property (PPE), both or none. These labeled concepts are then structured in a set of trees and manipulated to form the triples in the SPARQL query with the following transformations: Concept Tagging: if two PCEs refer to the same concept, they are reformulated into a root-child relation. PCE Fixing: the trees with PCEs on their roots are considered for further processing Value Tagging: if there are PPEs talking about the same property, they are reformulated so that the main property is on the root PPE Fixing: the PPE is reformulated to the same word that is referred in ontology, depending on its matching with each PCE. Ambiguity resolving: the duplicated and ambiguous PCEs and PPEs are removed so that only one of each remains.

These PCEs and PPEs in tree form are finally used to construct the SPARQL query following this template:

Testing

NLION was tested with a sample ontology using 67 concepts and 36 relations, and 125 simple sentences. They found that 61,60% of the queries where translated correctly by the system, and explained its moderate success because the SPARQL generated by NLION contains concepts and relations not present in the DDO.

FREyA

Translation type: Mapping of query to POCs, POCs-OCs, query Intermediate representation: POCs and OCs Domain knowledge: in the identification of ontology concepts User feedback?: yes Learning?: yes Input language: English

System architecture

Features

FREyA [freya]: Feedback, Refinement and Extended Vocabulary Aggregation, is a natural language interface to ontologies with learning from user feedback, based on QuestIO, introduced before, by Danica Damljanovic, Milan Agatonovic and Hamish Cunningham. Its architecture is broken down in three steps: Identification and verification of ontology concepts, Generating SPARQL, and Identification of the answer type and presenting the results to the user.

Features

Identification of Ontology Concepts This process is shown in the image below:

The Potential Ontology Concepts (POC) are derived from the syntactic parse tree (generated by the Stanford parser) using several heuristic rules, and refer to question terms which could be linked to an ontology concept. Then they are attemptedly mapped to Ontology Concepts (OC) automatically, by comparing the text span with the ontology labels; or manually, by asking the user to choose between suggestions generated from the closest OC, and ranked with Monge Elkan (http://www.dcs.shef.ac.uk/ sam/stringmetrics.html#monge) metrics and the Soundex (http://en.wikipedia/wiki/Soundex) algorithm.

Generating SPARQL The SPARQL query is generated as a set of OCs, by inserting potential joker elements in between OCs (for example if the first two are a property and a class, a joker class is added before them), and then generating the set of triples from them, taking into account the domain and range of the properties. With this, the SPARQL query is created by combining the triples based on the OC type, and adding the relevant parts to the SELECT and WHERE clauses.

Answer Type Identification To identify the answer type of the question, the output of the syntactic parsing is combined with the ontology-based lookup coupled with several heuristic rules [DBLP:conf/lrec/DamljanovicAC10]. It is also presented as a graph (with the JIT library (www.thejit.org)), with the answer type in the center, and the answer on the nearest cycle:

Learning The system's learning approach is inspired Reinforcement Learning (RL) Each suggestion has its initial ranking. Each time the suggestion is selected by the user, it receives a reward of +1 while all alternative ones receive -1. The system then learns to place the correct suggestion at the top for any similar questions, which are identified by a combination of a POC and the closest OC.

Testing

The authors evaluate FREyA's correctness, ranked suggestions, and learning mechanism with 250 questions from the Mooney DB. The correctness was measured as the precision and recall of the system, which are both 92,4% (taking into account that a question may be correct after 0, 1 or 2 clarification dialogs presented to a user). The ranking algorithm was tested with the Mean Reciprocal Rank, which is the average of the reciprocal ranks (multiplicative inverse of the correct rank) of results for a sample of queries. This was calculated to be 0,81. The learning mechanism was tested by selecting 103 questions which required 1 clarification dialog, and doing training with them: they then improved the initial ranking by 6%.

Comparison table

Here we compare the systems previously reviewed based on the classification stated by section 5.

Conclusions

The main goal of the papers reviewed in these survey was to implement a natural language interface to knowledge bases that had most of the coverage of the traditional query languages, but with a much easier way of use, focused on end users with no knowledge of query languages. As it can be seen by the testing procedures that where followed by the authors, several of these papers arrived to the conclusion that these natural interfaces to knowledge bases are indeed both easier and quicker to use than the query languages previously used like SPARQL, which need previous knowledge by the user and also information about the ontology concepts and relations. Even more, taking into account that the majority of the papers got a pretty good (more than 80% precision and recall) performance when translating user questions, it can be stated that the main goals of the papers have been accomplished.

Taking into account the characteristics studied in this paper, we can see that these systems have evolved from manual knowledge acquisition to an automatic one, to ease up the adaptation to new knowledge bases, since they give results as good as the ones that do it manually. We can also see that systems using heuristic translation with ranking work as well as the ones using grammatical translation, so that both ways are acceptable. The language used to interact with the system has evolved from a controlled one into full compliance with the English language, and systems like Orakel try to separate the parser module from the system to make it adaptable to other languages. Finally, the use of user refinement and learning contribute to a better performance of the system as it is more used, so it is a good thing to implement to increase the correctness of returned answers.

Even tough the authors of the papers presented here have accomplished a lot, there is still room for improvement. Most of these papers do not resolve problems with quantifies (how many x, number of x, is x longer than y) and queries with temporal components, like dates or relative pointers like “3 months ago", problems that are mentioned and treated in papers like [resolving]. Another interesting feature that are being studied is being able to join the information from several KBs, like the Aqualog successor, PowerAqua [DBLP:conf/esws/LopezMU06] is trying to achieve. In this way, the system might be able to answer questions by combining information from several ontologies, and so broadening the knowledge contained within to more than what each ontology offers.

Apart from these enhancements, the field of natural language interfaces to ontologies seems to be broadly covered by the systems presented in this survey, so it can be speculated that future work in the field will aim at refining the precision and recall, using user feedback to further improve the system through learning, solving the missing language constructs like counting or temporal semantics, and integrating information from several knowledge sources.

References

• [Navigli_ontologyenrichment] Roberto Navigli and Paola Velardi. Ontology Enrichment Through Automatic Semantic Annotation of On-Line Glossaries.
• [Omelayenko01learningof] Borys Omelayenko. Learning of Ontologies for the Web: the Analysis of Existent Approaches. 2001.
• [Choi:2006:SOM:1168092.1168097] Choi, Namyoun and Song, Il-Yeol and Han, Hyoil. A survey on ontology mapping. 2006.
• [Wache01ontology-basedintegration] H. Wache and T. Vögele and U. Visser and H. Stuckenschmidt and G. Schuster and H. Neumann and S. Hübner. Ontology-Based Integration of Information - A Survey of Existing Approaches. 2001.
• [Faatz02ontologyenrichment] Andreas Faatz and Ralf Steinmetz. Ontology Enrichment with Texts from the WWW. 2002.
• [freya] Danica Damljanovic and Milan Agatonovic and Hamish Cunningham. Natural Language Interfaces to Ontologies: Combining Syntactic Analysis and Ontology based Lookup through the User Interaction.
• [isaviz] Emmanuel Pietriga. IsaViz: A Visual Authoring Tool for RDF.
• [cantabria] Hernández Carrascal, Francisca. Ontología del patrimonio de Cantabria. 2008.
• [freeling] Lluís Padró and Miquel Collado and Samuel Reese and Marina Lloberes and Irene Castellón.. FreeLing 2.1: Five Years of Open-Source Language Processing Tools.
• [Vossen:1998:EMD:314515] EuroWordNet: a multilingual database with lexical semantic networks. 1998.
• [doerr03approach] M. Doerr. The CIDOC conceptual reference module: an ontological approach to semantic interoperability of metadata.
• [resolving] Shamima Mithun and Leila Kosseim and Volker Haarslev. Resolving Quantifier and Number Restriction to Question OWL Ontologies. 2007.
• [DOLCE2003] Claudio Masolo and Stefano Borgo and Aldo Gangemi and Nicola Guarino and Alessandro Oltramari. WonderWeb Deliverable D18 Ontology Library (final).
• [DBLP:conf/lrec/DamljanovicAC10] Danica Damljanovic and Milan Agatonovic and Hamish Cunningham. Identification of the Question Focus: Combining Syntactic Analysis and Ontology-based Lookup through the User Interaction. 2010.
• [DBLP:conf/lrec/2010] Proceedings of the International Conference on Language Resources and Evaluation, LREC 2010, 17-23 May 2010, Valletta, Malta. 2010.
• [Collins] Collins, Michael. Head-Driven Statistical Models for Natural Language Parsing. 2003.
• [fuchsnua99ace3Mal] Norbert E. Fuchs and Uta Schwertel and Rolf Schwitter. Attempto Controlled English (ACE) Language Manual, Version 3.0. 1999.
• [klein03fast] Dan Klein and Christopher D. Manning. Fast Exact Inference with a Factored Model for Natural Language Parsing.
• [Cohen2003] Cohen, William W. and Ravikumar, Pradeep and Fienberg, Stephen E.. A Comparison of String Distance Metrics for Name-Matching Tasks.. 2003.
• [Cun02b] H. Cunningham and D. Maynard and K. Bontcheva and V. Tablan. GATE: A framework and graphical development environment for robust NLP tools and applications.
• [Kaufmann_Bernstein_Fischer_2007] Kaufmann, Esther and Bernstein, Abraham and Fischer, Lorenz. NLP-Reduce: A “naïve” but Domain-independent Natural Language Interface for Querying Ontologies. 2007.
• [Bernstein05queryingontologies] Abraham Bernstein and Esther Kaufmann and Anne Göhring and Christoph Kiefer. Querying ontologies: A controlled english interface for end-users. 2005.
• [Lopez05aqualog:an] Vanessa Lopez and Michele Pasin and Enrico Motta. AquaLog: An Ontology-portable Question Answering System for the Semantic Web. 2005.
• [Bernstein05queryingthe] Abraham Bernstein and Esther Kaufmann and Christian Kaiser. Querying the semantic web with ginseng: A guided input natural language search engine. 2005.
• [Kaufmann06querix:a] Esther Kaufmann and Abraham Bernstein and Renato Zumstein. Querix: A Natural Language Interface to Query Ontologies Based on Clarification Dialogs. 2006.
• [DBLP:conf/esws/LopezMU06] Vanessa Lopez and Enrico Motta and Victoria Uren. PowerAqua: Fishing the Semantic Web..
• [Ran07naturallanguage] Alexander Ran and Raimondas Lencevicius. Natural Language Query System for RDF Repositories. 2007.
• [Cimiano07orakel:a] Philipp Cimiano and Peter Haase and Jörg Heizmann and Matthias Mantel. Orakel: A portable natural language interface to knowledge bases. 2007.
• [Wang07panto] Chong Wang and Miao Xiong and Qi Zhou and Yong Yu. PANTO -- a portable natural language interface to ontologies. 2007.
• [Damljanovic08k.:a] Danica Damljanovic and Valentin Tablan and Kalina Bontcheva. K.: A text-based query interface to owl ontologies. 2008.
• [RamachandranK09] Vivek Anandan Ramachandran and Ilango Krishnamurthi. NLION: Natural Language Interface for querying ONtologies..
• [Warren:1982:EEA:972942.972944] Warren, David H. D. and Pereira, Fernando C. N.. An efficient easily adaptable system for interpreting natural language queries. 1982.
• [Ritchie93masque/sql--an] Androutsopoulos Ritchie and I. Androutsopoulos and G. Ritchie and P. Thanisch. Masque/sql-- An Efficient and Portable Natural Language Query Interface for Relational Databases. 1993.
• [Grosz:1987:TED:25672.25674] Grosz, Barbara J. and Appelt, Douglas E. and Martin, Paul A. and Pereira, Fernando C. N.. TEAM: an experiment in the design of transportable natural-language interfaces. 1987.
• [Thompson:1983:IAS:974194.974198] Thompson, Bozena H. and Thompson, Frederick B.. Introducing ask, a simple knowledgeable system. 1983.
• [Weischedel89ahybrid] Ralph M. Weischedel. A Hybrid Approach to Representation in the Janus Natural Language Processor. 1989.
• [Hafner:1985:PSS:3914.3982] Hafner, Carole D. and Godden, Kurt. Portability of syntax and semantics in DATALOG. 1985.