System and Method for Universal Translating From Natural Language Questions to Structured Queries

• US 20130226846A1
• Filed: 02/25/2013
• Published: 08/29/2013
• Est. Priority Date: 02/24/2012
• Status: Active Grant

• Current Assignee: Rsvp Technologies Inc.
• Original Assignee: Di Wang, Ming Li, Yang Tang
• Inventors: Li, Ming, Tang, Yang, Wang, Di
• Granted Patent: US 9,183,511 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 40/186 Templates
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

A computer implemented question answering (QA) system and method is provided that automatically finds one or more accurate and concise answers for a natural language question. An automated training routine is provided that includes learning a proper mapping from the natural language question to one or more structured queries by discovering and summarizing parallel semantics between a knowledge base and pairs of a natural language question and its answer. The system and method generate as output concise texts answering the natural language question intended by a user.

Claims

1. A computer implemented question answering method, comprising:

(a) receiving or accessing a natural language question;

(b) recognizing one or more entity surfaces in the natural language question, and generating one or more corresponding template surface queries;

(c) constructing one or more structured queries based on one or more trained models for queried templates and entities;

(d) finding and selecting one or more answer phrases using constructed structured queries on a knowledge base; and

(e) composing, or initiating the composition, of output based on the one or more answer phrases.

2. The method of claim 1, wherein the method provides concise answers to natural language questions using a structured knowledge database.

3. The method of claim 1, wherein the constructing one or more structured queries from trained models and entities comprises:

(a) creating a basic graph pattern (BGP) with one or more trained relationship paths and entities;

(b) optionally performing Boolean algebra on multiple BGP'"'"'s to better describe the question intent; and

(c) applying context-free grammar (CFG) on template surfaces to build nesting queries.

4. The method of claim 1, wherein the step of selecting one or more answer phrases using constructed structured queries comprises:

(a) employing a ranking scheme considering following factors;

(i) popularity of the templates surface;

(ii) popularity of entities;

(iii) probability of relation path corresponding to the template; and

(iv) the depth of the nesting structured queries.

5. A computer system for automatically learning mappings from a natural language question to a structured query, comprising:

(a) one or more computer systems, linked to a question answering system, the question answering system including;

(i) a named entity recognizer for detecting one or more entity surfaces in input text so as to link a text phrase to a knowledge concept;

(ii) a training utility for searching and organizing one or more mappings from a template surface to one or more relationship paths; and

(iii) a training post-processing utility for normalizing and optimizing trained mapping distributions for one or more templates.

6. The computer system of claim 5, wherein question answering system permits concise answers to natural language questions using a structured knowledge database.

7. The system of claim 5, wherein the named entity recognize when executed:

(a) extracts entity surfaces from one or more webpage links to each knowledge concept;

(b) builds a prefix-tree based dictionary on extracted entity surfaces to link knowledge concepts; and

(c) searches inputted text with a surface dictionary to identity one or more potential knowledge concepts.

8. The system of claim 5, wherein the post-processing utility when executed:

(a) performs morphological normalization on template surfaces;

(b) merges predicate distributions of templates sharing major semantic mappings that are proximate to one another based on term frequency inverse document frequency distance; and

(c) applies matrix de-noising and correlation analysis techniques such as PCA and LSI on trained relationship path distributions for templates.

9. A computer system for automatically learning mappings from a natural language question to a structured query so as to enable obtaining an answer from a structured knowledge base based on the natural language question, comprising:

(a) one or more computer systems, linked to a question answering system, the question answering system including or being linked to a set of structured query templates, wherein the question answering system when executed;

(i) analyzes one or more natural language queries to generate one or more entity surfaces by accessing a named entity recognition (NER) utility;

(ii) matches the one or more entity surfaces to one or more of the templates by applying NER to the one or more templates and applying a matching operation;

(iii) estimates predicates by determining a relationship path distribution between the entity surfaces and the matched templates;

(iv) constructs one or more basic graph patterns (BGPs); and

(v) generates a structured query based on the natural language query based on the one or more BGPs.

10. A computer system of claim 9, comprising an NER module that both analyzes the natural language queries and trains the templates.

11. The computer system of claim 9, wherein the question answering system when executed automatically learns mapping rules, patterns or statistics so as to define one or more relationship paths between a question, an associated answer, and the knowledge base.

12. The computer system of claim 9, wherein two or more templates are merged, thereby merging the predicate distributions associated with the templates, by determining that the two or more templates are related.

13. The computer system of claim 12, wherein the question answering system applies a term frequency inverse document frequency operation in order to determine whether the two or more templates are related.

14. The computer system of claim 9, wherein the question answering system generates two or more structured queries, and these are ranked using one or more ranking operations.

15. The computer system of claim 14, wherein the ranking of the structured queries is based on ranking score calculated for each structured query based on one or more of:

(a) popularity of associated templates surfaces;

(b) popularity of associated entity surfaces;

(c) probability of applicable relation paths corresponding to the templates; and

(d) depth of the nesting structured queries.

16. The computer system of claim 15, wherein the question answering system applies a predetermined threshold which if exceeded, the structured queries are used to return the answer phrase, otherwise the computer system generates further results.