System and method to answer a question5884302Abstract A database-processing method and system for answering a natural-language question by a computer system with a database. In one embodiment, the system analyzes the grammatical structure of the question. In the analysis, the system scans the question to extract each word in the question; then based on a pre-defined context-free grammatical structure, the question is parsed into its grammatical components using one or more grammatically rules and the database. After parsing the question, the system transforms the components into one or more instructions, using one or more semantic rules and the database. The instructions, when executed, at least access data from the database for generating the answer to the natural-language question. In another embodiment, the system compares the natural-language question with questions stored in the database; each question in the database has its corresponding answer. If there is a match, the system retrieves the answer to the corresponding matched question and presents the answer to the student. Claims I claim: Description BACKGROUND
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
Each topic-related table combines data related to a topic in a specific format. As an example, one table includes all the data related to the Presidents of the United States, and another includes all the data related to the First Ladies of the United States. The table may be two-dimensional, and include a number of columns and rows. All the data in a column or a row typically have one or more common characteristics. For example, one row includes data that identify all the bills passed by the Presidents. For a two-dimensional table, data in a row can have one characteristic, and data in a column can have another characteristic. For example, data in one column identify the heights of the Presidents, and data in a row identify data related to one specific President; the following describes an example of data along the row:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
There is also a table-structure dictionary, which defines how the topic-related tables arrange their data. This dictionary is typically not considered as a part of the database. It does not contain topic-related data, but it contains structures of the topic-related tables in the database. Many database management systems automatically generate the table-structure dictionary based on the programming statements defining the topic-related tables, such as the CREATE clauses in SQL-like languages. As an example, the table-structure dictionary defines the structure of the data in the above President table by indicating that the first entry represents the name of the president, the second the position, and so on. Thus, the dictionary can contain the name of the table (the table name), the name of the table's attributes (attribute names), and their corresponding data types. A word in the question may need one or both of the semantic tables. The topic-independent semantic table 118B defines whether a word stands for an algorithm or data in a topic-related table. Such a table may be defined as follows:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
Words with similar meaning are grouped together and are represented by one of those words as the synonym for that group of words. If a word does not have other words with similar meaning, the synonym is the word itself. Many words do not point to an algorithm. They correspond to data in topic-related tables. The topic-dependent semantic table 118A identifies the semantic meaning of those words through matching them to data in topic-related tables. For example, the adjective "first" applying to the President's table may operate on the data under the inauguration date attribute; on the other hand, the adjective "first" applying to the First Ladies' table may operate on the data under the date of death attribute. Such a topic-dependent table 118A may be defined as follows:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
In one embodiment, the grammatical analyzer 102, the grammatical rules 104 and the grammatical table 114 are in a client computer. The programming-steps generator 108, the semantic rules 110, the semantic tables 118 and the table-structure dictionary are in a middleware apparatus, which can be a Web server. The programming-steps executor 112 with the topic-related tables are in a back-end server, which can be a database server. One embodiment includes a computer-readable medium that encodes with a data structure including the semantic tables 118. Another embodiment includes a computer-readable medium that encodes with a data structure including the semantic tables 118 and topic-related tables 116. Yet another embodiment includes a computer-readable medium that encodes with a data structure including the semantic tables 118 and the grammatical table 114. Yet a further embodiment includes a computer-readable medium that encodes with a data structure including the grammatical table 114, the topic-related tables 116 and the semantic tables 118. FIG. 3 shows a set 200 of steps to implement one embodiment of the present invention. A natural-language question is entered into the system 100. The system analyzes (Step 202) the grammatical structure of the question so as to parse it into its grammatical components, based on a pre-defined context-free grammatical structure. This task uses a set of grammatical rules 104 and the grammatical table 114. Then, the system transforms (Step 206) at least one component into one or more instructions using a set of semantic rules 110 with one or both of the semantic tables 118. Then, the one or more steps are executed (Step 208) to access and process data from one or more topic-related tables so as to generate an answer to the question. In another embodiment, the programming-steps generator 108 transforms all the grammatical components of the question into instructions using semantic rules 110 with one or both of the semantic tables. Then the executor 112 executes all the steps to access and process data from one or more topic-related tables for generating an answer to the question. Grammatical Structure Analyzer In one embodiment, the analyzer 102 scans the question to extract each word in the question. Then the analyzer 102 maps each extracted word to the grammatical table 114 for identifying its grammatical meaning. For example, the word "Clinton" is identified by the grammatical table to be a proper noun; and the word "sum" is a noun. After establishing the grammatical meaning of each word, the analyzer 102 uses a set of grammatical rules to establish the grammatical components of the question based on the pre-defined context-free grammatical structure. For a number of words, their grammatical meanings depend on their adjacent words. In one embodiment, the analyzer 102 combines each word with its contiguous words to determine its grammatical component. For example, if the word is "with," in analyzing its grammatical meaning, the analyzer 102 identifies its contiguous words. If its contiguous words are "respect to," then the three words are combined together and are considered as one preposition. Thus, to determine grammatical meaning of a word, the analyzer identifies that word, and then a number of words following it, such as two words following it. The analyzer 102 analyzes the identified words as a unit. If the analyzer 102 cannot identify the grammatical meaning of that sequence of words, the analyzer 102 removes the last word from the sequence, and analyzes them again. The process repeats until either a grammatical meaning is found, or there is no more word. Any time when the analyzer 106 has identified a grammatical meaning, that word or sequence of words would be considered as one unit. In one embodiment, the pre-defined context-free grammatical structure is shown in FIG. 4 and is as follows:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
The pre-defined structure is only one example to illustrate the present invention. Other context-free grammatical structures are applicable also. Generating different context-free grammatical structures should be obvious to those skilled in the art. In the present invention, a word or a set of words that can fit into the structure of a meta-symbol is a grammatical component. For example, the phrase "with respect to x" is a grammatical component, whose grammatical meaning is a prepositional-noun-phrase. In the present invention, grammatical rules and the pre-defined grammatical structures are linked. Once the rules are set, the structures are determined. Similarly, once the structures are determined, a set of rules can be found. For example, based on the pre-defined structures, one grammatical rule is that "a group-of-nouns preceding a prepositional-noun-phrase is a noun-phrase." The grammatical table defines the grammatical meaning of each word. In one embodiment, the table is a part of the grammatical rules. In another embodiment, all the grammatical rules that define the grammatical meaning of each word are separated from the rest of the grammatical rules, and are grouped together to establish the grammatical table 114. A number of examples on analyzing a question for parsing it into its grammatical components based on the pre-defined grammatical structure are: 1. What is the derivative of sin(x+4) with respect to x? Starting from the right hand side, (x) is a noun so (x) is a group-of-nouns so (x) is a noun-phrase so (with respect to x) is a prepositional-noun-phrase (sin(x+4)) is a noun so (sin(x+4)) is a group-of-nouns so (sin(x+4) with respect to x) is a <group-of-nouns><prepositional-noun-phrase> so (sin(x+4) with respect to x) is a noun-phrase so (of sin(x+4) with respect to x) is a prepositional-noun-phrase (derivative) is a noun (the) is a modify-article so (the derivative) is a group-of-nouns so (the derivative of sin(x+4) with respect to x) is a <group-of-nouns><prepositional-noun-phrase> (is) is an aux-verb (what) is an i-pronoun Thus, the question is of the structure <i-pronoun><aux-verb><group-of-nouns><prepositional-noun-phrase>. 2. Why is delta used in step 4 of the proof? Starting from the right: (proof) is a noun (the) is a modify-article so (the proof is a group-of-nouns so (the proof is a noun-phrase so (of the proof) is a prepositional-noun-phrase (4) is a noun (step) is a noun so (step 4) is a group-of-nouns so (step 4 of the proof) is a <group-of-nouns><prepositional-noun-phrase> so (step 4 of the proof) is s noun-phrase so (in step 4 of the proof) is a prepositional-noun-phrase (used) is a verb as defined by the grammatical table so (used in step 4 of the proof) is a verb-phrase (delta) is a noun so (delta) is a group-of-nouns so (delta) is a noun-phrase (is) is an aux-verb (Why) is an i-pronoun Thus, again the question is of the structure <i-pronoun><aux-verb><noun-phrase><verb-phrase>. 3. Why did President Nixon resign? Starting from the right-hand side (resign) is a verb so (resign) is a verb-phrase (Nixon) is a noun (President) is a noun (President Nixon) is a one-or-more-nouns so (President Nixon) is a noun-phrase (did) is an aux-verb (Why) is an i-pronoun Thus, the question is of the structure <i-pronoun><aux-verb><noun-phrase><verb-phrase> Many questions cannot be parsed based on the pre-defined context-free grammatical structure. In this disclosure, these questions are considered as ambiguous questions, and will be analyzed through methods explained later in this disclosure. If there are more than one such pre-defined context-free grammatical structure stored in the system, the question entered will be parsed based on each structure individually. The question only has to be successfully parsed based on one such structure. If the question cannot be parsed based on all the pre-defined context-free grammatical structures, the question will be considered as an ambiguous question. Programming-steps Generator The programming-steps generator 108 transforms at least one grammatical component of the question using a set of semantic rules and one or both of the semantic table to generate a set of instructions. The semantic rules and the semantic tables depend on the pre-defined context-free grammatical structure, which the parsing process bases on. In one embodiment, the semantic rules are also embedded in the semantic tables. In a general sense, the generator 108 directs different grammatical components in the question to algorithms or to data in the topic-related tables. To help explain the present invention, a number of functions are created as shown in the following: Keys-Of(Table) This function extracts all the key attributes in the identified table. Attributes-Of(Table) This function extracts all the attribute names in the identified table. Attribute-Names({adjective}, Table) This function identifies one or more attributes when the {adjective} is applied to the table. Attribute-Names({noun}, Table) This function identifies one or more attributes when the {noun} is applied to the table. Attribute-Name({i-pronoun}, Table) This function identifies the attribute when the {i-pronoun} is applied to the table. Tables-Of({proper noun}) This function identifies one or more tables that contain the {proper noun} as a key value. It can be derived by the following program:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
Synonym({word}) This function identifies the synonym corresponding to the word. The synonym can be found in the topic-independent-semantic table. Methods to create the above functions should be obvious to those skilled in the art of programming. Based on a number of semantic rules, the programming-steps generator 108 generates instructions based on the grammatical components in the question. The following shows examples of different instructions generated to illustrate the present inventions. The instructions generated are either in a SQL-like, a LISP-like or a C-like language though other programming languages are equally applicable. A Proper Noun A grammatical component in the question can be a proper noun, which implies that it has a grammatical meaning of a proper noun. One set of semantic rules is that the programming-steps generator 108 transforms the proper noun into instructions to select one or more topic-related tables, and then transforms other grammatical components in the question into instructions to select and to operate on data in the tables for answering the question. Using the topic-dependent semantic table 118A, the programming-steps generator 108 first retrieves all tables where the proper noun is an attribute. Then, as shown in the topic-dependent semantic table, all key attributes in those tables are identified, and each of them is matched to the proper noun. The table of any key attribute that matches the proper noun is selected for additional operation by the remaining grammatical components in the question. A proper noun may consist of more than one word, such as the "Bills of Right." A proper noun can be a lower-case word, such as "moon." In one example, the corresponding instructions are as follows:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
Common Nouns One grammatical component in the question can be a common noun. The programming-steps generator 108 might transform the common noun into instructions to select a topic-related table, an attribute name, a synonym of an attribute name, the data under an attribute, or an algorithm. As shown in FIG. 5A, if the noun is the name of a topic-related table as shown by the topic-dependent semantic table 118A, then the programming-steps generator transforms the noun into instructions to select (Step 252) that topic-related table, and transforms (Step 254) other components in the question to identify data in the table and to operate on them, if necessary. If the noun denotes an attribute name or a synonym of an attribute name, again as shown by the topic-dependent semantic table 118A, the programming-steps generator searches and identifies the attribute based on the noun. The instruction generated can be, for example, modifying a SELECT clause as follows:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
After all of the relevant attributes have been identified, data in them are retrieved for further processing by other parts of the question to generate an answer. If the noun denotes the data under an attribute, the programming-steps generator identifies the data, with its corresponding attribute and table. The instructions generated can be, for example, (1) identifying each table in the function Tables-Of({noun}); (2) for each table identified, the function Attribute-Names({noun}, Table) returns the corresponding attributes containing the {noun} in that table; and (3) the remaining parts of the question operate on information under each attribute to generate the answer to the question. One set of instructions achieving such objectives is as follows:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
As shown in FIG. 5B, the programming-steps generator might identify the algorithm (Step 262) corresponding to the noun; the algorithm is then applied (Step 264) to data selected by grammatical components in the question other than the common noun. For example the noun "sum" indicates accumulating results; the noun "count" indicates computing the cardinality of the results; and the noun "product" in mathematics indicates multiplying results. The topic-independent semantic table 118B can point to locations to get the algorithm. A Group of Nouns If the question includes a group of nouns linked together, such as X1 X2 X3 . . . Xn, then X1 to Xn-1 can modify the final noun Xn, which is known as the primary noun. In other words, the programming-steps generator operates on the primary noun as a common noun, or a proper noun, whichever it may be, and the remaining nouns X1 to Xn-1 further operate on data/table(s) selected by the primary noun. Non-Auxiliary Verbs One grammatical component can be a non-auxiliary verb. It relates to one or more events or an action, which has a number of attributes; and it might have words with similar meaning. One approach is to identify the verbs with similar meaning. Then other components in the question identify data in the attributes of the identified verbs for answering the question. A verb can be related to many different events. As an example, the verb is "nominate": one event can be President Bush being nominated to be the President, and another event can be President Clinton being nominated to be the President. However, an event is related to a verb. The attributes of the event can have a subject-agent, which is the agent performing the event, such as the party nominating the president. Typically, the preceding noun phrase before the verb identifies the subject-agent. The event can have an object-agent if the verb is a transitive verb, which is the agent acted upon by the event, such as the president being nominated. Each event has a duration that is between a starting and an ending time. For example, if the event is "walk" its duration starts with the sole of a foot changing its position from touching the ground to not touching the ground, and then ends with the sole back to touching the ground again. Non-auxiliary verbs are grouped together in an event table, which is a topic-related table, with the topic being events. The following is an example of an event in the table:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
The subject-agent, object.sub.-- agent etc. are attributes related to the verb.sub.-- word, which is associated with an event. There might be non-auxiliary verbs with similar meaning as the non-auxiliary verb in the question. These verbs can be identified by the synonym in the topic-independent semantic table. As an example, the verbs of breathe and inhale have similar meaning. As shown in FIG. 6, the programming-steps generator 108 transforms the non-auxiliary verb in the question into one or more instructions, which select (Step 300) one or more verbs with their attributes in the event table. The one or more verbs have similar meaning as the non-auxiliary verb. Then other components in the question identify data (Step 302) in the attributes for answering the question. The selected verbs can be put into a temporary table or a view (a database terminology) as follows:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
The attributes of the selected verbs are also identified. Then, the programming-steps generator 108 generates additional instructions based on other components in the question to identify data (Step 302) in the selected attributes for answering the question. Events might be related. Two events may form a sequential relationship, where one event follows another event, such as eat and drink. Two events may form a consequential relationship, such as braking and stopping, with the braking event causing the stopping event. Many small events may make up a big event, with the big event containing the small events; this leads to containment relationships. Also, events may be related because they involve the same subject-agent; and events may be related because they involve the same object-agent. An event-relationship table describes relationships among events. It can have the following format:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
Interrogative Pronouns Based on the interrogative pronoun in the question, the programming-steps generator 108 generates one or more instructions to select one or more attributes in one or more tables. Those tables have been selected by grammatical components in the question other than the interrogative pronoun. The function Attribute-Name({i-pronoun}, Table) generates the attribute name corresponding to the {i-pronoun}. One way to generate a SQL-like instruction corresponding to the {i-pronoun} is to modify a SELECT clause: SELECT Attribute-Name({i-pronoun}, Table) FROM Table Determiners Examples of a set of semantic rules on determiners are: If the determiner is "a" or "an," select any result from the previous query. If the determiner is "some," select more than one result from the previous query. If the previous query yields only one result, that result will be selected. If the determiner is "all," select all result from the previous query. If the determiner is "the," modify the following SELECT function with DISTINCT, as will be shown by examples below. Auxiliary Verbs An auxiliary verb together with either its immediate noun phrase or a non-auxiliary verb determine whether the answer should be singular or plural. Adjectives One grammatical component of the question can be an adjective. As shown in FIG. 7, based on the adjective, the programming-steps generator either identifies the value of an attribute, or identifies an algorithm. The grammatical components in the question other than the adjective have already selected one or more topic-related tables. As shown by the topic-independent semantic table, the adjective may identify (Step 350) an attribute. The function Attribute-Names({adjective}, table) can retrieve the attribute in the table previously selected. The corresponding instruction can be:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
As an example, the noun phrase is "a red apple." The noun "apple" can be associated with a table known as FRUIT, and the Attribute-Names(red, FRUIT) yield the attribute "color." The adjective "red" is interpreted: WHERE color="red." If there is a sequence of such adjectives, all of them can apply to the same table. The WHERE clause would be a conjunction of the adjectives, such as:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
An adjective can refer to an algorithm, as identified by the topic-independent semantic table. Grammatical components in the question other than the component that is the adjective have selected one or more topic-related tables. As shown in the topic-independent semantic table, the adjective identifies (Step 352) one or more attributes in those tables. Then the algorithm operates (Step 354) on one or more data in those attributes. As an example, the adjective is "first." The topic-independent semantic table indicates that the adjective is an algorithm sorting a list of data in ascending order; the table also identifies the data in one or more attributes in one or more topic-related tables. For each attribute identified, after sorting its data, the first value will be the result. For example, the question is "Who is the first President?" The table identified is the President table. The attribute whose data are to be sorted is the "date" attribute, which identifies the time each President was elected. The instruction corresponding to the adjective "first" can be as follows:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
The symbol ASC denotes ascending. Similarly, if the adjective is "last," then the attribute whose data are ordered is the same, but the data are sorted in a descending manner. The corresponding instruction can be as follows:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
The symbol DESC denotes descending. Another example on adjective is the word, "immediate." Its interpretation depends on the word it modifies. In one example, if the word modified is "action," the word "immediate" has the same effect as the word, "first;" if the word modified is "cause," the word "immediate" has the same effect as the word "last." There can be a sequence of adjectives. Then, the above analysis is applied in the same order as the occurrence of the adjectives. Preposition One grammatical component can be a preposition. A preposition can modify its previous noun phrase or verb, such as by operating on them through an algorithm identified in the topic-independent semantic table. Under some situations, with one or more tables selected by at least one grammatical component in the question other than the component that is the preposition, the algorithm identified operates on data or values in the one or more selected tables. Under some other situations, for example, due to the prepositions `of` and `in`, the programming-steps generator processes the grammatical component succeeding the preposition before the grammatical component preceding. For another example, the preposition `before` can modify the WHERE clause with a comparison on time: {time of preceding event}<{time of succeeding event} Programming-Steps Executor The executor 112 executes at least one set of instructions generated from one grammatical component to at least access data from the database to generate an answer for the question, if there is one. In one embodiment, after the programming-steps generator 108 generates a set of instructions, the programming-steps executor 112 executes them. The set may be generated from one grammatical component. This process repeats until all sets are generated and executed to answer the question. For at least one set of instructions, the executor 112 accesses data from one or more topic-related tables identified by the instructions. In another embodiment, all the instructions are generated; then the program executor 112 runs the instructions, which include accessing data from one or more topic-related tables identified by the instructions, and processing those data for generating the answer to the natural-language question. In the appendix there are a number of examples of instructions illustrating the present invention. They are generated to answer different types of grammatically-context-free questions. Ambiguous Questions In the present invention, the grammatical structure analyzer 102 may decide that the natural-language question cannot be parsed into grammatical components based on the pre-defined context-free grammatical structure. For example, the grammatical components of the question cannot fit into the pre-defined structure. Then the question is considered ambiguous, and an answer cannot be generated. Ambiguity may be due to a number of reasons. For example, the question may contain words with non-unique grammatical meaning, the question may contain words not in the grammatical table, or the grammatical structure of the question is different from the pre-defined grammatical structure. FIG. 8 shows different approaches to resolve the ambiguity. The grammatical structure analyzer can decide that a word can be of more than one grammatical meaning, such as it can be a noun and a verb. In one embodiment, the analyzer produces (Step 402) an answer for each meaning and ignores those meaning with no answer. In another embodiment, the analyzer asks (Step 400) the user to identify the correct grammatical meaning. For example, the question is: "When was the Persian Gulf war?" The word "war" can be a noun or a verb. In one embodiment, the analyzer asks the user whether the word "war" is a noun or a verb. Based on the user's response, the question is analyzed. In another embodiment, the analyzer generates answers to both the question that treats the word "war" as a verb, and the question that treats the word "war" as a noun. Both answers, if available, are presented to the user. If the grammatical structure analyzer decides that the question contains one or more words not in the grammatical table, in one embodiment, the analyzer removes (Step 404) the unrecognized word and processes the remaining words in the question. In another embodiment, the analyzer asks (Step 406) the user for a different word. The analyzer might assume that the word is mis-spelled, and ask the user to correct it; the analyzer might replace (Step 408) the un-recognized word with a word in the grammatical table most similar to or with minimum number of different characters from the unrecognized word. The analyzer then presents (step 410) the matched word to the user to ask if that is the right word. A list of matched words may be presented for the user to select. For example, the question is: "What exactly are the Bills of Right?" The word "exactly" is an adverb and is not in the grammatical table. The word is dropped, and the question, satisfying the grammatical structure, is analyzed. In another example, the question is: "What is the Bill of Right?" Here, the "Bill of Right" should be the "Bills of Right." The analyzer can ask the user to spell the "Bill of Right" again; or the analyzer can find the term closest in spelling to the un-recognized term, and identify the term to be the "Bills of Right". The identified word is presented to the user to ask if that is the right spelling. In the present invention, the grammatical structure of the question entered may be different from the one or more pre-defined context-free grammatical structures in the system. In one embodiment, a non-essential grammatical component is missing from the question. A grammatical component is non-essential if that grammatical component can be removed from the question without changing the answer to the question. For example, an auxiliary verb in certain condition can be non-essential. One approach to solve this problem is to ignore (Step 412) the missing grammatical component in generating the answer to the question. Another approach is to add the missing non-essential grammatical component back into the question, and present to the user asking if that is correct. For example, the question is: "When President Nixon resign?" An auxiliary verb is expected after the word "When"; such a word is entered into the question, which is then submitted to the user for approval. In another embodiment, the user is suggested to re-enter (Step 414) the question with advice as to the appropriate question structure. One advice is to ask the user to re-enter the question based on the pre-defined structure, such as using one of the i-pronouns in the pre-defined grammatical structure. This can be done, for example, by citing a list of acceptable i-pronouns, and a list of model questions using the i-pronouns as examples. Another advice is to identify nouns and non-auxiliary verbs, if any, in the question, and to ask the user which of the identified word or words he wants to know more about. Then it would be up to the user to select the one he wants. In a further embodiment, the identified word or words are fit into alternative grammatical structures, and the user is asked to select one structure out of the list of suggested structures. As an example, the question is: "Do you know when President Nixon resign?" Assume that such a question does not fit the pre-defined grammatical structure. The user is suggested to re-enter the question using one of the following i-pronouns: What, when, where, why and who. In another embodiment, the noun and the auxiliary verb are identified, and they are "President Nixon resign." The user is asked, "You want to know about `President Nixon resign?"` In yet another embodiment, the identified words are fit into the following question formats, and it would be up the user to select one, for example: What does President Nixon resign? When does President Nixon resign? Where does President Nixon resign? Why does President nixon resign? Who does President Nixon resign? As another example, the question is: "Is there a reason why President Clinton sent troops to Bosnia?" Assume that the question does not fit the pre-defined grammatical structure. In one embodiment, the user is suggested to re-enter the question using one of the i-pronouns in the pre-defined grammatical structure. In another embodiment, the nouns and the non-auxiliary verbs, "President Clinton", "troops" "send" and "Bosnia" are identified. Then the user is asked to select one or more of the following questions: Do you want to know about President Clinton? Do you want to know about troops? Do you want to know about Bosnia? Also, the system 100 can present suggestions to the user on ways to rephrase the original question based on the noun and the non-auxiliary verbs. It would then be up to the user to select the one he wants. In certain situation, the present invention does not have any answer. As an example, the grammatical table does not have some essential terms X in the question. Then, the present invention can return the following message: Sorry, I do not know anything about X. You may want to check with your instructor. If you wish, I will inform your instructor your question. {Click here to inform your teacher} If the user clicks at the designated area, his last question will be automatically sent as an electronic mail to an instructor who can answer the user directly. This instructor may be previously selected by the user, or the guardian of the user. Questions Matching Engine The above embodiments can answer an infinite number of questions. FIG. 9 illustrates another embodiment 500 of the present invention, which provides answers to a finite number of questions, but requires fewer steps to generate answers as compared to the embodiment shown in FIG. 1. Also, the embodiment 500 can answer non-naturals language questions, and grammatically-context-dependent questions. In this embodiment 500, the database 106 includes a questions table, which contains many questions, each with its corresponding answer. A question matching engine 529 compares the question entered with questions in the database. An answer retriever 539 retrieves the answer to the question in the database that matches the entered question. A presenter then presents the answer to the user. FIG. 10 shows one set of steps 550 for the present embodiment. The question matching engine 529 compares (Step 552) the entered question with questions in the database 106. If there is a match with any one of them, the answer retriever 639 retrieves (Step 54) the answer corresponding to the matched question, and the presenter presents (Step 556) the answer to the student. If no question in the table matches the input question, the embodiment 500 might use one of the approaches discussed in the ambiguous questions section to answer the question. In another embodiment, the question entered is a natural-language question. The matching engine 529 compares the grammatical components of the natural language question with components of the questions in the database 106. A further embodiment includes an essential-components extractor, which extracts essential components from the natural-language question entered. Only essential components are compared with the pre-stored questions, which have essential components. If there is a match, the answer to the corresponding matched question is retrieved and is presented to the student. As an example, an auxiliary verb is a non-essential components. The extractor strips off the auxiliary verb from the question to allow the matching engine 529 to compare the rest of the components. In yet another embodiment, the question entered is a grammatically context-free question. The embodiment 100 shown in FIG. 1 can be combined with the embodiment 500 shown in FIG. 9. The question entered is first analyzed by the embodiment 100 shown in FIG. 1. If the question cannot be parsed into its grammatical components based on the pre-defined structure, then the question is passed to the embodiment 500 shown in FIG. 9. If that embodiment cannot find a match in the questions table, the question will be considered as an ambiguous question to be resolved by approaches discussed in the ambiguous questions section. Other embodiments of the invention will be apparent to those skilled in the art from a consideration of this specification or practice of the invention disclosed herein. It is intended that the specification and examples be considered as exemplary only, with the true scope and spirit of the invention being indicated by the following claims. Appendix The following shows examples of instructions automatically generated to answer different types of grammatically-context-free questions using the embodiment shown in FIG. 1. 1. Who is the first President?
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
2. What are the Bills of Right?
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
3. Where is the capital of Texas? There are two nouns in this question: capital and Texas. In one embodiment, each noun is associated with a topic-related table. The preposition "of" indicates that the table associated with Texas should take precedence over the capital table. This question can have two different answers. The answer can be the geographic location as shown on a map, or the answer can be the city Austin. One embodiment generates the following instructions, with x denoting Austin, and y denoting geographic location:
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
4. What is the immediate cause of the Civil War? In this example, the word "immediate" when linked with the noun "cause" is equivalent in meaning to the word "last."
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
5. Why did President Nixon resign? Events about "President Nixon resign" are extracted into a local table T. Then the causes of all such events are identified.
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
The following examples 6-9 depend on tables, such as the President tables, generated above. 6. Who is the third President?
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
These instructions assume Tables-Of(President) contains only one table, and Attribute-Names(`third`, PRESIDENT) yields only a single attribute. 7. Who is the President after John Kennedy?
__________________________________________________________________________
CREATE TABLE Grammatical (
word Character string NOT NULL, // the word
grammatical-meaning
Character string NOT NULL, //e.g. "Examiner"
// has "noun" as its grammatical meaning
__________________________________________________________________________
8. When did President Lyndon Johnson die? SELECT Death.sub.-- Date FROM PRESIDENT WHERE Name LIKE "Lyndon Johnson"; 9. When was President Nixon born? SELECT Birth.sub.-- Date FROM PRESIDENT WHERE Name LIKE "Nixon" A number of mathematical examples are shown in the following using the programming language Lisp. Some examples might use mathematical software packages. For mathematics problems, there can be an additional topic-related table, known as the mathematics table. The mathematics table might include high-level attributes, such as fraction, ratio, derivative, theorem, complex-number, matrix etc. Each of these high-level attributes can have a definition attribute describing the mathematical concept; a reference attribute identifying the study material covering the concept; and an algorithm attribute, if there is one. In another embodiment, the algorithm attribute references a mathematical software package. A high-level attribute can be a theorem, such as the Mean Value Theorem. In its corresponding definition attribute, there will be an explanation for that theorem. Note that, in this example, the algorithm attribute is not in the topic-dependent semantic table. Most mathematical questions are `what-is` questions. If a question is of the form `What is X?`, where X is a mathematical term, the system generates the following instruction: SELECT definition FROM T mathematics table WHERE T.name=X; If the question is `What is X <prepositional-noun-phrase>?`, the <prepositional-noun-phrase> modifies the term X. The system retrieves X and applies the operations to the terms indicated by the prepositions. 10. What is the ratio between 7 and 8? From the mathematics table, the attribute "ratio" is identified. Its algorithm attribute operates on two terms, as specified in the prepositional-phrase "between 7 and 8." For example: (ratio 7 8) 11. What is the derivative of sin(x 2+4) with respect to x? Again, the question is of the structure: "What is X <prepositional-noun-phrase>?" X is "the derivative," and the noun-phrase is "sin(x+4) with respect to x." The algorithm specified by the "derivative attribute" in the mathematics table has two operants, u and v, with the first operant, u, being the noun immediately after the preposition. In this example, u is equal to sin(x 2+4), and the second operant is v. The system can invoke a mathematics software package to solve the differentiation, d(sin(x+4))/dx. One LISP representation is as follows: (derivative `x`(sin (+(* x x) 4))) 12. What is the product of {matrix-1} and {matrix-2}? The LISP representation is as follows: (matrix-mul <matrix-1><matrix-2>) 13. What is the sum of the product of 3 and 4, and the ratio of 7 and 8? The LISP representation is as follows: (+(* 3 4)(ratio 7 8)) Not all mathematics questions are `What-is` questions. The user may not understand certain steps in a derivation he is studying on the screen. Such questions are typically `Why-is` questions. In one embodiment, the system identifies the study material, as in the current screen or the last screen he has been focusing on. Nouns used in the question are mostly from those study material. By associating the question with the study material and accessing a database of explanation terms in the study material, the system can generate an answer to the question. 14. Why is delta used in step 4 of the proof? The structure of the question is: Why is <noun phrase><verb phrase>. The system (a) Identify the verb in the verb phrase to be the word "used." (b) Identify one or more sets of events algorithm corresponding to the word "used" in the mathematics table. The sets of algorithm are applicable to the structures of X using Y. (c) Identify X to be (delta). (d) Identify Y to be (in step 4 of the proof). (e) Identify the i-pronoun and the aux-verb as "Why is." (f) Select the set of algorithm for explaining the relationship between X and Y. In this case, the set selected explains why X used Y. (g) The algorithm searches for delta in step 4 of the proof in the materials just presented to the user. After identifying the proof, step 4 and delta, the system explains the step 4 of the proof with special focus on delta.
|
Same subclass Same class Consider this |
||||||||||