Natural language analyzing apparatus and method

Abstract

A natural language (NL) analyzing system is provided with the capability to analyze NL expressions and to resolve ambiguities and present them to the user for verification of correct interpretation. A conceptual model of the system, relevant to the application in which the invention is implemented, is created (customizing the system) by the user, and is stored as a conceptual schema. The schema is built of logical facts representing entities (concepts) and relationships between entities, forming a description of the universe of discourse or object system in question. The entities of the schema have at least one external connection, namely to natural language terms in a vocabulary. The schema itself is completely language independent, though the components of it may have "names" expressed in a natural language such as English. There may be a second connection to the entities, namely where the system is used in a query system for relational data bases. In this case the entities of the schema represent objects in the data base, and thus there is a connection between the entities and those objects of the data base. The actual analysis of NL expressions is performed by a natural language engine (NLE) in cooperation with an analysis grammar and the schema. The analysis results in an intermediate, language-independent logic form representation of the input, which is paraphrased back to NL for verification. If the input is a query, there is a translation into a query language such as SQL.

Claims

We claim:

1. A natural language analyzing apparatus comprising:

a data base store comprising a data base containing tables;

a grammar store comprising a grammar for a natural language comprising a set of language dependent syntax rules for the natural language, at least one syntax rule having one or more associated semantic routines;

a vocabulary store comprising a vocabulary containing terms of the natural language, definitions of the terms, and morphological information about the terms;

a conceptual model store comprising a conceptual model having (i) a set of language independent records of information defining entities, each entity having a connection to at least one term in the vocabulary, at least one entity having a connection to the data base tables, and each term in the vocabulary being defined by at least one entity, and (ii) a set of records identifying relationships between different entities;

means for inputting a series of words based in the natural language;

parsing means for generating one or more syntactically valid parse trees for the input series of words based on the vocabulary and the syntax rules, and for building, for each parse tree, an executable set of semantic routines based on one or more semantic routines associated with one or more of the syntax rules used to generate the parse tree;

generator means for executing the set of semantic routines generated by the parser to create a language independent representation of the input series of words, wherein executing the semantic routine comprises checking groups of one or more words in the parse trees against the conceptual model for conceptual validity;

output means for producing, from said language independent representation of the input series of words, a natural language output series of words in the same language as the input series of words, said output series of words representing a paraphrase of the input series of words;

confirmation means for requesting confirmation of the conceptual accuracy of the output series of words with reject to the input series of words and for receiving a confirmation from the user if the user determines that the output series of words conceptually matches the input series of words; and

query generator means responsive to the confirmation for producing a data base query from the language independent representation.

2. An apparatus as claimed in claim 1, wherein the data base is a relational data base.

3. The apparatus as claimed in claim 2, further comprising means responsive to the query generating means for producing a response to the data base query.

4. An apparatus as claimed in claim 3, comprising means for storing a previous query, and means for storing for the previous query a corresponding answer set, said answer set comprising a query statement, a specification of how much of the data in the data base tables is to be presented to a user of the apparatus, and information on a mode of presentation of the data.

5. A method of querying an information store comprising the steps of:

generating a computer-readable input representing an input series of words in a natural language;

parsing an input expression to generate one or more syntactically valid parse trees for the input series of words based on a vocabulary containing terms of the natural language, definitions of the terms, and morphological information about the terms, and based on syntax rules of a grammar for the natural language, at least one syntax rule having one or more associated semantic routines;

building, for each parse tree, an executable set of semantic routines based on the one or more semantic routines associates with the at least one syntax rules having one or more associated semantic routines and used to generate the parse tree;

executing the executable set of semantic routines to create a language independent representation of the input series of words based on a conceptual model having (i) a set of language independent records of information defining entities, each entity having a connection to at least one term in the vocabulary, at least one entity having a connection to a data base table, and each term in the vocabulary being defined by at least one entity, and (ii) a set of records identifying relationships between different entities, wherein executing the semantic routine comprises checking groups of one or more words in the parse trees against the conceptual model for conceptual validity;

producing, from said language independent representation of the input series of words, a natural language output series of words in the same language as the input series of words, said output series of words representing a paraphrase of the input series of words;

requesting confirmation of the conceptual accuracy of the output series of words with respect to the input series of words, and producing a confirmation if the output series of words is conceptually correct; and

if the confirmation is produced, producing, in response to the confirmation, a data base query from the language independent representation.

6. The method as claimed in claim 5, further comprising querying a data base with the data base query.

7. A method as claimed in claim 6, wherein if an answer cannot directly be retrieved from-the data base tables in one single query statement, temporary tables are created and filed with data, said temporary tables being queried for a final answer.

8. A method as claimed in claim 7, wherein the data is ordered by ascending or descending value; of the data.

9. A method as claimed in claim 8, wherein only a selected portion of the data is presented to a user of the method.

10. A method as claimed in claim 9, wherein an answer set comprising an instruction to create and fill the temporary tables, together with the query and a range of data to be selected from the temporary tables, is stored in a log for later use.

11. A method as claimed in claim 10, wherein the stored answer set is copied into an input field of a query panel of a query program.

Description

BACKGROUND OF THE INVENTION

The present invention relates in general to the use of natural language for communication with computers, and in particular to querying data bases, e.g. relational data bases, or to translation between two natural languages of application specific texts.

There is a widely recognized demand in the computer world for user friendly interfaces for computers. Numerous attempts have been made in order to achieve this with various results.

The simplest way of creating programs that are possible to use without having particular skills is to design menu based systems where the user selects functions from a panel with several options.

Another way is to make use of screens with symbols ("icons") and letting the user select from the screen by pointing at the selected symbol with a light-pen, or by moving a cursor by means of a so called "mouse", pointing at the desired symbol, and then pressing a button for activating the function.

These methods have severe limitations in many applications where great flexibility in selection is desired, since such systems must be predefined, and unexpected or new desires require programming of the system again.

The need for flexibility is especially important for data retrieval from data bases. In order to make searches in data bases, often complex query languages must be used, requiring high skill. If reports are to be created from the retrieved data, further processing must be carried out. In addition, several successive queries may have to be entered before the end result is arrived at.

An example of a query language is SQL (Structured Query Language; IBM program no. 5748-XXJ). This is widely used but due to its complexity it is not possible for the average user to learn it satisfactorily, instead there are specialists available for creating SQL query strings that can be implemented as commands for searches of a routine nature. The specialist must be consulted every time a new kind of query is to be made.

There have been numerous attempts to remedy such deficiencies by trying to create interfaces to data bases which can interpret a query formulated in natural language. However, practically every such attempt has been based on key word identification in the input query strings. This inevitably leads to ambiguities in the interpretation in many cases.

Rather recently, research in the artificial intelligence area has led to systems where lexical, syntactical, and semantic analysis has been performed on input strings, utilizing grammars and dictionaries, mainly for pure translation purposes. It seems as if these systems are successful only to a certain extent, in that there is a relatively high rate of misinterpretations, resulting in incorrect translations. This frequently leads to the requirement of editing the result.

United Kingdom Patent Application 2,096,374 (Marconi Company) discloses a translating device for the automatic translation of one language into another. It comprises word and syntax analysis means, and the translation is performed in two steps by first translating the input sentence into an intermediate language, preferably artificial, and then translating the intermediate language into the target language.

European Patent Application EP-0168814 (NEC Corporation) discloses a language processing dictionary for bidirectionally retrieving morphemic and semantic expressions. It comprises a retrieving arrangement which is operable like a digital computer, and the dictionary itself is comprised of elementary dictionaries, namely a morphemic, a semantic and a conceptual dictionary. Each morphemic and conceptual item in the corresponding dictionaries are associated with pointers to a set of syntactical dictionary items. The syntactical items are associated with two pointers to a set of morphemic and a set of conceptual items.

U.S. Pat. No. 4,688,195 (Thompson et al, assigned to Texas Instruments) discloses a natural language interface generating system. It generates a natural language menu interface which provides a menu selection technique particularly suitable for the unskilled user.

However, none of the above listed patents fully address the problem solved by the present invention, although they do present alternative technical solutions to certain features.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide a device and a method by means of which a user can formulate input expressions in a selected natural language in reasonably random fashion, which expressions are interpreted lexically, syntactically, and semantically by means of dictionaries and analysis grammars, and which are disambiguated and transformed into an intermediate representation form.

This intermediate representation form can then be used for creating queries in a specific query language (such as SQL for a relational data base) and/or for paraphrasing or "play-back" of the input for verification of the correctness of the machine's interpretation of the input expression or query. For this purpose there is provided a natural language generator including a generation grammar.

If the generation grammar is for another natural language than that of the analysis grammar, the latter function can also be used for pure translation into another language.

According to the invention, a natural language analyzing apparatus, has means for inputting sentences or expressions in natural language. Analysis grammar means analyzes the natural language in question. A vocabulary module contains definitions of terms of the natural language in question. Parsing means identifies the input sentence or expression as being grammatical and generates one or more parses, if there is one or more possible interpretations of the expression, in cooperation with the analysis grammar means and the vocabulary module.

The invention also has a conceptual schema stored in the system. The conceptual schema contains entities (el, . . . en) and relationships between the entities so as to form a description of a relevant universe of discourse. The entities and relationships of the universe of discourse are linked to corresponding natural language terms (t1) in the vocabulary.

Generator means comprise callable semantic routines for generating an intermediate representation of the natural language input. As a result, the semantic routines access the conceptual schema for checking that the input expression is valid in the relevant universe of discourse.

An important feature of the invention is the conceptual schema connected to natural language terms in a vocabulary. The schema is completely language independent, and contains only concepts (entities) and relations between concepts.

By using such a schema, which is a model of a relevant so called `Universe of Discourse` (or object system, which is a collection of abstract or concrete things and information about these things, to which the natural language expression to be analyzed, is relevant), it is possible to obtain complete resolution of ambiguities, as long as the input expression is in reasonable agreement with the Universe of Discourse. This has not been possible previously.

Since the schema is language independent there is a great advantage in that it is very easy to change analysis grammar and vocabulary, and thus to switch between different natural languages. In fact grammars and dictionaries can be supplied as `plug-in` modules.

In a preferred embodiment of the invention the schema is also connected to the contents of a relational data base. That is, each concept of the schema may or may not have a unique connection to a table containing objects relating to that concept.

Thus, the schema constitutes a link between natural language and the data base. If thus the input expression is a query to the data base, the analysis will produce an interpretation of the query which then is translated into the query language for that data base (e.g. SQL).

In another embodiment, queries are paraphrased, i.e. if a query is ambiguous, two or more paraphrases are presented to the user, for him to select the correct one. Thereby one achieves that a 100% correct query is made to the data base.

In a further embodiment the paraphrasing function is used for pure translation. Thereby a generation grammar and a vocabulary for a second language is used when paraphrasing the input expression. In this case there is no use of a data base in the sense of the previously mentioned embodiment.

BRIEF DESCRIPTION OF THE DRAWING

FIG. 1 is a conceptual overview of a system comprising the natural language analyzing device according to the present invention, as implemented for querying a relational data base.

FIG. 2A is a schematic illustration of a simple example of a conceptual schema, modelling the data base contents, and which can be used with the invention.

FIG. 2B is a simplified illustration of how parts of the schema of FIG. 2A is linked to tables in a data base and to natural language terms in a vocabulary.

FIG. 3A is an example of a parse tree (or syntax tree) created during parsing.

FIG. 3B is a graphic illustration of a semantic tree built by the parser.

FIG. 4 is an illustration of the screen of the graphic interface of the Customizing Tool.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

With reference now to FIG. 1, the general layout and design of a system for querying a data base comprising the invention will be given.

A data base query system incorporating the invention thus has a query interface 1 comprising input means 2 that can have any suitable form for transforming character strings into digital signals, e.g. a keyboard of standard type. It is also conceivable that the input query is made by speech, in which case the input means would comprise a microphone and sound analyzing means.

There may also be present a display means 3 for presenting results of queries, results of parsing (paraphrased queries, to be described later), and also for displaying, e.g. help panels.

The core of the system is the natural language engine NLE 4. It comprises a natural language analyzer 5 which includes a parser and which is used for the actual syntax analysis. The analyzer 5 makes use of base dictionary 6 and application dictionary 7 and an analysis grammar 8 to perform the actual parsing of the input (to be described in more detail later).

The system further comprises a data base (DB) and a data base manager 9. It will not be described in detail since one skilled in the art readily recognizes the necessary design of such a device.

An essential feature of the invention is a model of the data base in the form of a conceptual schema (base conceptual model 10 and application conceptual Model 11), which may be created by the user.

The concept of a conceptual schema is described in the literature in the field of artificial intelligence, (see e.g. "Konceptuell Modellering" by J. Bubenko et al).

Briefly, a conceptual model consists of

1) `Entities`, which are any concrete or abstract thing/things of interest;

2) `Relationships` which are associations between entities;

3) `Terms` which are natural language expressions that refers to entities;

4) `Database Representations` which are mappings of entities into the database; and

5) `Database Information` comprising `Referential Integrity` and `Key`.

As many entities as the user finds necessary may be defined, and the system will automatically suggest that every table in the data base is associated with an entity.

Entities of the model may be connected or linked to each other by one or several relationships. In general relationships fall into the following categories:

    ______________________________________
               `is an instance of`
               `identifies`
               `is named`
               `is a subtype of`
               `is counted by`
               `is measured by`
               `possesses`
               `subject`
               `direct object`
               `dative object`
               `preposition`
               `adverbial of place`
               `adverbial of time`
               .
               .
               .
               (etc)
    ______________________________________

    ______________________________________
    Entity        Relationship Entity
    ______________________________________
    continent (CNTNNT)
                  `is identified by`
                               continent id (ID)
    country (CNTRY)
                  `possesses`  capital (CPTL)
    producer (PRDCR)
                  `is subtype of`
                               country (CNTRY)
    export (EXPORT)
                  `has object` product (PRDCT)
    ______________________________________
     (in this last example the entity EXPORT has no link to a table in the dat
     base).

    ______________________________________
    possesses(e2, e1).
    possesses(e2, e5).
    possesses(e5, e2).
    nom(e6, e3).   (e6 has-subject e8)
    acc(e6, e8).   (e6 has-object e8)
    subtype(e3, e2).
    subtype(e4, e10).
    subtype(e5, e7).
    identifies(e4, e5).
                   (e4 identifies e5)
    identifies(e10, e7).
    name(e11, e7).
    lp(e2, e5).    ("location of place"; e2 is-in e5)
    ______________________________________

    ______________________________________
    (e1) --->    `capital` (t1) noun, plural:
                 `capitals`, pronoun: `it`
    (e2) --->    `country` (t2) noun, plural:
                 `countries`, prounoun: `it`
    (e7) --->    `continent` (t3) noun, plural:
                 `continents`, pronoun: `it`
    (e8) --->    `product` (t4) noun, plural:
                 `products`, pronoun: `it`
    (e6) --->    `export` (t5) verb, forms:
                 `exports`, `exported`, `exported`,
                 `exporting`
    (e6) --->    `produce` (t6) verb, forms:
                 `produces`, `produced`, `produced`,
                 `producing`
    ______________________________________

    __________________________________________________________________________
    <SENT:1:FPE-COMMAND(1,2)><-<SC:TYP=AZ,+IMP,+CMD,(SYST=1).sub.--
    !(SYST=2)<>NP:+ACC>
    <SCT:1,+ES,+CN:FPE-NOM(2,1)><-<VC:TYP=NZ,+CNA,COL=COL(2).sub.--
    DS,-PPE,-IMP,-PAS,((-SG)&(-SG(2)))!((-PL(2)))><NP:+NOM.sub.--
    REL,-WPRO>;
    __________________________________________________________________________

    ______________________________________
             quest(p01,
              two(p02,
              nom(p03,
               wque(p04, `who`),
               acc(p05,
               npquan(p06, `all`
                nomen(p07, `product`)),
               verb(p08, `export`)))))).
    ______________________________________

    ______________________________________
              query(
               report,
               set(y1,
               all(y2,
                instance(e8, y2) ->
                exist(y3,
                instance(e6, y3) &
                acc(y3,y2) &
                nom(y3,yl))))).
    ______________________________________

    ______________________________________
              query(
               report,
               set(y1,
               all(y2,
                instance(e8, y2) ->
                exist(y3,
                instance(e6, y3) &
                instance(e3, yl) &
                acc(y3,y2) &
                nom(y3,yl))))).
    ______________________________________

    ______________________________________
    query(
     report,
     set(y1,
     relation(table.co(cntry=y1)) &
     all(y2,
      relation(table.export(prdct=y2)) -->
      relation(table.export(prdcr=y2,cntry=y1)))))
    ______________________________________

    ______________________________________
    CREATE TABLE t1 (cntry , card)
    INSERT INTO t1 (cntry , card)
     SELECT x1.cntry, COUNT( DISTINCT x1.prdct )
     FROM table.export x1 GROUP BY x1.cntry
    SELECT DISTINCT x1.cntry
     FROM table.co x1,t1 x3
     WHERE x1.cntry = x3.cntry
     AND x3.card = (
     SELECT COUNT( DISTINCT x2.prdct )
     FROM table.export x2)
    NIL
    REPORT
    ______________________________________

    ______________________________________
    `List the capitals of the countries`
    Semantic tree:
     command(
      p85,
      gener(
      p37,
      `liste`)`
      npdef(
      p75,
      `die`,
      attgen(
       p64,
       nomen(
       p62,
       `capital`),
       prep(
       p61,
       npdef(
        p58,
        `die`,
        nomen(
        p53,
        `country`)),
       `pp`,
       gener(
        p47,
        `of`)))))
    CLF:
      query(report,0,
      set(y1,
      instance(capital,y1) &
      exist(y2,
       instance(country,y2) &
       possesses(y2,y1))))
    DBLF:
    query(report,0 set(y2,
     relation((table.co(capital = y1, country = y2))))))
    SQL:
    SELECT DISTINCT x1.capital,x1.country FROM table.co x1
    ______________________________________

    ______________________________________
    `what does England export`
    CLF:
    query(report,0 set(y1,
     instance(product,y1) &   exist(y2,
      instance(provider,y2) &
      name(y2,`great britain`) &
      exist(y3,
      instance(export,y3) &
      nom(y3,y2) &
      acc(y3,y1)))))
    DBLF:
    query(report,0 set(y1,
     relation(table.exportbase(country = `great.sub.--
        britain`,product = y1))))
    SQL:
    SELECT DISTINCT x1.product
     FROM table.exportbase x1
     WHERE x1.country = `great britain`
    ______________________________________

    ______________________________________
    `What are the populations of the ec-countries`
    CLF:
    query(report,0 set(y2,
     instance(population,y2) &
     exist(y3,
      instance(ec-country,y3) &
      possesses(y3,y2))))
    DBLF:
    query(report,0 set(y2,
     set(y3,
      relation(table.co(population = y2)) &
      relation(table.orgbase(countxy = y3,.sub.--
        organization = `EC`)))))
    SQL:
    SELECT DISTINCT x1.population,x2.country
     FROM table.co x1,table.orgbase x2
     WHERE x2.organization = `EC`
     AND x2.country = x1.country
    ______________________________________

• Inventors
  Hedin, Erik B.; Jonsson, Gregor I.; Olsson, Lars E.; Sanamrad, Mohammad A.; Westling, Sven O. G.;
• Assignee
  International Business Machines Corporation (Armonk, NY)
• Published
  Jan-31-1995
• Current US Classes:
  706/11
  706/934
  707/4
• Application #
  996353
• International Classes
  G06F 015/40
• Field of Search
  364/419 364/DIG. 395/600 395/12 395/500 395/575 395/934
• Examiner
  Black; Thomas G.
• Agent
  Schechter; Marc D., Tassinari, Jr.; Robert P.
• US Patent References:
  4688195
  4706212
  4821230
  4914590
  4931935
  5091876
  5197005
  5237502