Geodesic search and retrieval system and method of semi-structured databases

• US 8,155,949 B1
• Filed: 10/01/2008
• Issued: 04/10/2012
• Est. Priority Date: 10/01/2008
• Status: Active Grant

• Current Assignee: the united states of america as represented by the secretary of the navy
• Original Assignee: the united states of america as represented by the secretary of the navy
• Inventors: Rubin, Stuart H
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Borsetti, Greg
• Application Number:
  US12/243,049
• Time in Patent Office: 1,287 Days
• Field of Search: 704/9, 706/1, 706/47, 706/55, 706 59- 61
• US Class Current: 704/9
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries

Abstract

A knowledge-based decision support system that allows for communication and learning to occur using natural language is presented. The system has a capability to automatically extract features from the natural language using symmetric reductions and random search. The iterative generalization of the rule base and checking of the resultant base against a case base from which the generalizations are induced is also provided. The decision support system can be used to search semi-structured databases and automatically learns new knowledge and search control knowledge where it is most needed based on the pattern of previous rule firings.

Claims

1. A method of geodesic search for a semi-structured database and retrieval of relevant information therefrom based on a natural language query, comprising the steps of:

parsing the natural language query to identify domain-specific semantic features of the natural language query;

mapping the features to their semantic normalization stored in a symmetric reduction table;

mapping the semantic normalization to rules in a knowledge base;

retrieving information from the semi-structured database tagged with the semantic normalization based on the rules;

measuring a degree of success of the step of retrieving;

evolutionarily decomposing features stored in the symmetric reduction table that co-occur with rules that are improperly matched to retrieved information as determined by the step of measuring;

reducing an arbitrary feature space derived from the step of parsing to a more salient feature space to reduce inclusion of extraneous features wherein the step of reducing comprises the steps of;

comparing a context of the features parsed from the natural language query to cases stored in a case base to determine a metric match therefor;

assigning a relative weighting factor to the features;

calculating a score based on the metric match and the relative weighting factors; and

selecting a case having the highest score for retrieving information from the semi-structured database; and

replacing an existing rule in a case with a generated rule associated with a case when the total number of predictions “

a” and

the ratio “

b”

of the number of correct predictions divided by “

a”

are both non-decreasing.

2. The method of claim 1, further comprising the step of recursively disambiguating the natural language query when at least one feature is unknown.

3. The method of claim 1, further comprising the step of randomly searching the symmetric reduction table during the step of parsing to improve feature identification.

4. The method of claim 1, wherein the semi-structured database stores active and passive information and wherein the step of retrieving information comprises the step of retrieving passive information from the semi-structured database.

5. The method of claim 4, wherein the step of retrieving information comprises the step of retrieving active information for computing information.

6. The method of claim 1, wherein the step of reduction comprises the step of iteratively randomizing a case by a maximum of 2ⁿ candidate rules to transform the case base into a most-general rule base.

7. The method of claim 6, further comprising the step of selecting a case for randomization with dynamic probability of selection skewed in favor of those rules which are most frequently fired.

8. The method of claim 7, further comprising the steps of assigning a head rule at the logical top of the rule base a probability of being selected of 2r/r(r+1), where r is the total number of rules in the knowledge base, assigning a logical next rule a probability of being selected of 2(r−

1)/r(r+1), and continuing to assign each successive rule a probability of being selected such that a logical last rule has a probability of being selected as 2/r(r+1).

9. The method of claim 8, wherein the step of selecting comprises the step of calculating a 3-2-1 skew.

10. The method of claim 1, wherein the step of reducing comprises the steps of:

running in parallel on separate threads the steps of;

comparing a context of the features parsed from the natural language query to cases stored in a case base to determine a metric match therefore, assigning a relative weighting factor to the features, calculating a score based on the metric match and the relative weighting factors, and selecting a case having the highest score to be used in the step of retrieving information from the semi-structured database; and

iteratively randomizing a case by a maximum of 2ⁿ candidate rules to transform the case base into a most-general rule base.

11. A non-transitory computer readable medium having stored thereon computer executable instructions for performing the method of claim 1.

12. The method of claim 1, wherein the step of reducting comprises the steps of:

moving a rule to a logical head of the knowledge base when the step of measuring indicates that the rule was correctly fired;

moving a case associated with the rule moved in the step of moving to a logical head of the case base to facilitate its selection upon further queries.

13. The method of claim 12, further comprising the step of allowing least-frequently used rules and their associated cases to be logically moved to the bottom of the knowledge base and the case base to reduce a likelihood of selection upon further queries.