System and method for learning answers to frequently asked questions from a semi-structured data source

A frequently-asked-question (FAQ)-based system receives question(s) from a user and generates answer(s) based on data about the question(s). In one embodiment, a method includes retrieving, from a memory, a global structure and candidate answers therein. The method can include computing a first, second, and third probability of a candidate answer based on a local structure of the candidate answer within the global structure, content of the candidate answer given content of a query and context of the candidate answer given the content of the query, respectively. The method can include providing a combined probability of the candidate answer based on the first probability, second probability, and third probability. The method can improve efficiency of a FAQ-based system by automating organization of semi-structured data in a database. Therefore, a human user does not need to manually generate the database when it is already generated in semi-structured form, a semi-structured HTML document.

BACKGROUND OF THE INVENTION

Question Answering (QA) systems receive a query (e.g., a question) from a user, either in text or voice form, and provide an answer to the user. QA systems generally are configured to provide answers for common questions in a given topic area.

SUMMARY OF THE INVENTION

In one embodiment, a method can include retrieving, from a memory, a global structure and candidate answers therein. The method can include computing a first probability of a candidate answer based on a local structure of the candidate answer within the global structure. The method can also include computing a second probability of the candidate answer based on content of the candidate answer given content of a query. The method can additionally include computing a third probability of the candidate answer based on context of the candidate answer given the content of the query. The method can further include providing a combined probability of the candidate answer as a function of the first probability, second probability, and third probability.

In another embodiment, the method can include weighting the first probability with a first weight, the second probability with a second weight, and the third probability with a third weight. The first weight, second weight, and third weight can be based on tuning data. The tuning data can indicate a relative importance the first probability, the second probability, and third probability in providing the combined probability.

In a further embodiment, the method can include accepting training data representing locations of the local structure of the candidate answer within the global structure corresponding to a respective query.

In another embodiment, the method can also include determining the context of the candidate answer by walking through the global structure starting at the structure of the answer to other structures within the global structure.

In yet another embodiment, the method can include accepting structures of candidate answers allowable and non-allowable within the global structure.

In an even further embodiment, the method can include determining a frequency of features in the global structure. The method may further include representing the frequency of features determined in an answer prior model.

In another embodiment, the method can include determining a similarity of content of the candidate answer and the query. The method can further include representing the similarity in an answer likelihood model.

In an even further embodiment, the method can include determining a relationship of the candidate answer to other candidate answers within the candidate answers. The method can also include representing the relationship in the answer context model.

In one embodiment, retrieving the global structure from the memory can further include (a) automatically retrieving input data with a particular structure and (b) generating the global structure based on the input data by parsing the particular structure.

In another embodiment, the method can include returning a candidate answer of the plurality of candidate answers with a highest combined probability to provide to a device that submitted the query.

In one embodiment, a system can include a structure generation module configured to retrieve, from a memory, a global structure and a plurality of candidate answers therein. The system can also include a computation module. The computation module can include a first computation unit configured to compute a first probability of a candidate answer based on a local structure of the candidate answer within the global structure, a second computation unit configured to compute a second probability of the candidate answer based on content of the candidate answer given content of a query, and a third computation unit configured to compute a third probability of the candidate answer based on context of the candidate answer given the content of the query. The system can further include a combination module configured to provide a combined probability for the candidate answer as a function of the first probability, second probability, and third probability.

DETAILED DESCRIPTION OF THE INVENTION

A description of example embodiments of the invention follows. The teachings of all patents, published applications and references cited herein are incorporated by reference in their entirety.

In question answering (QA) systems, field data sources can be categorized into three types:

(1) structured data sources, which organize structured questions and answers in a database. No extra work is needed to extract the questions and answers;

(2) semi-structured data sources, which embed semi-structured questions and answers in the data of some structure, such as XML or HTML. Some extra computing, such as applying heuristic rules, needs to be performed to extract the questions and answers; or

(3) un-structured data sources, which include text without any structure. Large amounts of computing, including passage retrieval, parsing, classification, etc., need be performed to extract answers.

Prodigy or FAQ applications are typical examples of using structured data. DeepQA or Watson by IBM™ are typical examples of using unstructured data. There is myriad data online embedded in HTML code, which is the most popular/common example of semi-structured data. Of course, not all HTML structured data can be categorized as semi-structured data. For example, if all an HTML document stores useful information in the bottom leaf node, then even though the page is structured using HTML, the information lacks structure or organization and is essentially the same as unstructured data. All of the information being within an organizational element, but being otherwise unorganized within that element, does not make the information semi-structured. Prior work has used data structures to extract questions/answers pairs to enhance QA applications based on heuristic rules, however, the rules are difficult to write and adapt to data sources of a different format. In one embodiment of the present invention, the presentation is a robust and effective data-driven method.

A web page can be organized by converting the HTML of the web page to a tree structure representation. For example, consider a web page that contains information about an application including what the application does, what the application does not do, and system requirements to install the application on different platforms. For example, the web page can answer the question “what is the system requirement for installing this application on my ipad2,” with the answer “OS 3.2 or later.” If the entire page is treated as a list of words, instead of as semi-structured data, this answer may not even be in the top list given the question because data on the web page unrelated to the system requirement makes it more difficult to find the correct answer without any guiding structure. Using the tree structure provides a clean path from a root node to a tree node (ignoring pure structural tree nodes):“system requirement”→“ipad2”

Employing the tree structure of web pages helps both document retrieval and information extraction. An embodiment of the method proposed herein assumes the data source (e.g., each document in the data) is organized as a tree, and the answer is embedded in one or more consecutive tree nodes. If the tree node has children, the children are included too. Therefore, groups of answers can be allowable or non-allowable.

Under this assumption, to identify an answer, the system identifies the starting tree node and the ending tree node among its right siblings. For a page, there are at most N*M*M possible answers, where N denotes the number of tree nodes in a page, and M denotes the maximum number of children of a tree. For each candidate answer, its probability of being chosen is a product of two components:
P(a-is-chosen)=p(a)p(a,d−a|q)

p(a) is an ‘answer prior model’ that represents the probability that a is an answer. For example, for the sequence of candidate tree nodes, if the sub-trees rooted at them are of the same structure, they are more likely to be an answer. This is described in more detail in relation toFIGS. 3A-C. p(a, d−a|q) denotes the probability that given query q, the document d can be used to extract the answer a. This probability can be further composed into:
p(a,d−a|q)=p(a|q)p(d−a|q)

p(a|q) an ‘answer likelihood model’ that represents a likelihood that a is an answer for query q. p(d−a|q) represents a likelihood that the rest of document provides enough evidence to answer query q. As described above, using the entire document can introduce noise to the model, so based on the tree structure, the scope can be narrowed based on the context close to the extracted answer a:
p(d−a|q)=p(context(a)|q)

This model is an ‘answer context model.’ To integrate all three components together (e.g., the answer prior model, the answer likelihood model, and the answer context model), the probability of choosing a candidate answer can be computed as the product of the three models:
P(a-is-chosen)=p(a)αp(a|q)βp(context(a)|q)θ

The three extra parameters (i.e., α, β, θ) are used to weigh the importance of the three models on the end probability. The weighing can either be performed manually or by using a statistical classifier (e.g., maxent). In one embodiment, the context model is more important than the answer model, which is more important than the answer likelihood model, and the weights can be adjusted to reflect the same, accordingly.

The implementation of a system under this framework therefore implements the three probability models. The rest of the application describes the models in detail with examples of implementations, although other implementations and embodiments are certainly possible.

Answer Prior Model

The answer prior model focuses on modeling the formation of the answer. For example, if the possible patterns for a valid answer is limited for one application, the system can count the frequency of each pattern in training data and answer prior model with a multinomial model. Generally, suppose the candidate answer is composed by tp, tp+1, . . . , tq, where tp−1and tq+1denote the tree node in the two boundaries. If tpis the first or tqis the last child of the parent tree node, then two dummy tree nodes represent the respective boundaries.

To model the transition probability, the system can employ a log linear model (or any statistical classifier that outputs probabilities), where multiple features can be used. For example, features can be:Are tiand of the same shape?Do ti−1and tihave the same depth?Do ti−1and tihave the same number of children?Do ti−1and tihave the same tag name? “<tr>”, for example, is a tag name used in HTML to indicate a table row.What is the tag name of the parent nodes of ti−1and ti?What is the tag name of ti−1?What is the tag name of ti?

This log-linear model can then be trained based on the transition instances in the training data. Positive samples can be fewer than negative samples, and some data selection/balancing is necessary to generate a well-behaved model.

Answer Context Model

The context for a candidate answer is first defined to model context probability for a candidate answer a=tp, tp+1, tq. The nodes tp−1and tq+1denote the tree node in the two boundaries. If tpis the first or tqis the last child of the parent tree node, then two dummy tree nodes represent the boundaries, respectively. The context can be:A parent of a;A path from the root to the parent of a;A first non-structural parent of a;A first uncle of a;Children of first uncle of a; and/ortp−1and tq+1.

For the candidate answer “OS 3.2 or later,” its contexts are the nodes representing the answer, the rows of titles related to the answer, and parent nodes.

More specifically, the following features can be extracted based on the defined context (text similarity is treated as a set of functions to be defined):Text similarity of q and the first non-structural parent of a;Text similarity of q and the path from the root to the parent of a;Text similarity of q and the first uncle of a;Text similarity of q and the children of a's first uncle;Text similarity of q and the pth to the qth children of a's first uncle;Text similarity of q and tp−1; and/orText similarity of q and tq+1.

With these features, a log-linear model can then be trained. Heuristics define the features and also work for applications of different data format. Also, the scope of the context can be gradually expanded until better results cannot be achieved.

Answer Likelihood Model

The answer likelihood model captures similarity between content of a candidate answer a and a given query q. It can be similarly modeled as the answer prior model, with a different set of features:KL-divergence of q and a,KL-divergence of a and q, andNumber of 2 gram/3 gram/4 gram/5 gram appearing in both a and q/number of total 2 gram/3 gram/4 gram/5 gram in a.

While in some cases, the query and answer may not overlap, when it does overlap, the answer likelihood model is helpful.

FIG. 1is a block diagram100illustrating an example embodiment of the present invention. A user102employs a training module104(e.g., a computer, other computing device, or input device) to train an FAQ-based system (not shown) based on semi-structured data. In one embodiment, the user's102can use data from a website, webpage, as the semi-structured data. Upon the user102loading the semi-structured data on the training module104, the user can select to train an FAQ-based system based on the semi-structured data. The training module104sends input data106to a server110in a network108. The server110uses the input data106to determine a probability of candidate answers112. The probability of candidate answers112is returned to the training module104. The probability112is used to train the FAQ-based system within the training module.

The FAQ-based system can be stored either on the training module104or on the server110. In addition, the training based on the input data can be performed locally on the training module104, instead of on the server110over the network108.

FIG. 2is a diagram200illustrating an example embodiment of a method of mapping queries to answers. A log of queries202(for training) includes both training queries204a-cand non-training queries208. The training queries204a-cand non-training queries208each represent a logged question from a previous use of an FAQ-based system or from a set of training data. Out of the set of training queries204a-cand non-training queries208, selected queries are mapped to an answer and location206a-c. In this example, training query204a-care mapped to an answer and location206a-c. Training query204ais mapped to an answer and location206a, training query204bis mapped to answer and location206b, and training query204cis mapped to answer and location206c. The location of the answer and location206a-ccan represent the location in the data structure (e.g., the semi-structured data or the global structure).

FIG. 3Ais a diagram300illustrating an example embodiment of a global structure302highlighting an allowable answer304. The global structure302, as described herein, is a representation of the semi-structured data inputted into the system. The global structure302includes a plurality of nodes, starting from a root node. The global structure302can have sets of allowable answers represented in its nodes. A set of allowable answers can be determined by the structure of the global structure302(e.g., the physical location of each nodes relative to each other) by employing the answer prior model. Likewise, the global structure302can include non-allowable answers that are identified by the structure of the global structure302.

In relation toFIG. 3A, an example of the allowable answer304is the root node of the global structure302. The root node or allowable answer304is allowable because it is the root node. The root node is an allowable group because the group has no other nodes to make the combination be non-allowable.

FIG. 3Bis a diagram310illustrating an example embodiment of the global structure302highlighting allowable answers314aand314b. Allowable answers314aand314bare an allowable group because they are brother and sister nodes. This means that the nodes are on the same level of the global structure302, and also not removed from one another within that level. They also share the same parent node.

FIG. 3Cis a diagram320illustrating an example embodiment of the global structure302highlighting allowable answers324aand324b. Allowable answers324aand324b, like allowable answers314aand314b, are allowable because they are brother and sister nodes sharing the same parent.

FIG. 4Ais a diagram400illustrating an example embodiment of a global structure302highlighting non-allowable answers404aand404b. A non-allowable group of answers is based on context of the group of answers. For example, the non-allowable answers404aand404bare non-allowable together as a group because one is a parent node to the other. A parental relationship among the nodes drastically reduces the likelihood that the nodes are both candidate answers to a given query. Therefore, non-allowable answers404aand404bare not likely to both be candidate answers to the same query.

FIG. 4Bis a diagram410illustrating an example embodiment of the global structure302highlighting another example of non-allowable answers414aand414b. The non-allowable answers414aand414bare unallowable because, even though they share a parent, they are far removed from each other along their particular level. An intervening node is between the non-allowable answers414aand414b. This is an example of a configuration of a non-allowable answer model.

However, depending on the source of the structured data and the format of the global structure302, in one embodiment, the non-allowable answer groups may not depend on their location within a given sibling level. In other words, in another embodiment, non-allowable answers414aand414bmay instead be allowable.

FIG. 4Cis a diagram420illustrating an example embodiment of global structure422highlighting non-allowable answers424aand424bwithin. Non-allowable answers424aand424bare non-allowable because they are on separate sides of the tree of the global structure422. The global structure422has a root node with two child nodes, each of whom has their own child node(s). From there, the non-allowable answer424ais a child of the first grandchild of the root node, where non-allowable answer424bis a child of the second grandchild of the root node. While the non-allowable answers424aand424bare on the same vertical distance from the root node, they have different parents and grandparents nodes, and, therefore, are non-allowable as a group.

FIG. 5is a block diagram illustrating an example embodiment of a system500of the present invention. The system500includes a memory502which can store semi-structured data503. A structure generation module504loads the semi-structured data503. The structure generation module504, based on the semi-structured data503, generates a global structure506(e.g., global structure302or global structure422). The structure generation module504sends the global structure506to a computation module508. Within the computation module508are a first computation unit510a, a second computation unit510b, and a third computation unit510c. Each respective computation unit510a-cloads the global structure506. The first computation unit510generates a first probability512awhich is based on a local structure of the candidate answer within the global structure of the plurality of candidate answers. The second probability is based on contents of the candidate answer given the query524(which is supplied to the computation module506). The third probability512cis based on the context of the candidate answer based on the query. Then, a computation module514generates a probability of the candidate answer516. The probability of the candidate answer516is based on a combination of the first probably512a, second probability512b, and third probably512c. The computation of module514acan weigh each probability512a-cbased on training data, or other user preferences in weighing each probability. Then, an answer module518receives the probability of the candidate answer516and returns an answer with a highest probability520.

In one embodiment, the system500also includes a query reception module526. The query reception module receives user input522, which can be training data or a user query. The query reception module then forwards the query524to the computation module506.

FIG. 6is a flow diagram600illustrating an example process employed by an example embodiment of the present invention. First, the system retrieves semi-structured data from a memory (602). Then, the system converts semi-structured data to a global structure (604). Then, the system receives a query from the user (606). Then, the system calculates probabilities of candidate answers based on global structure, the query, and context of the candidate answers (608). Then, the system returns candidate answers with a highest probability (610).

FIG. 7is a diagram illustrating an example embodiment of semi-structured data. In this example, the semi-structured data is presented to the user as a table700. The table700includes a title702(reading “operating system requirements”). The table700further includes row titles704(e.g., “system,” “operating system,” and “web browser”). The table700further includes a plurality of data rows706a-c. Data row706aincludes an “iPhone®” under system, “iOS™ 3.0 or later” under operating system, and “N/A” under web browser. Data row706bincludes “iPad® 2” under system, “iOS™ 2.2 or later” under operating system, and “N/A” under web browser. Data row706cincludes “Macintosh® (Apple®)” under system, “Mac OS X® version 10.4 or later” under operating system, and “Safari® 2.0, Safari® 3.0, or Firefox® 1.5 to 3.0” under web browser.

FIG. 8is a diagram800illustrating a global structure802of the table700illustrated inFIG. 7. In relation toFIG. 8, the global structure802includes a root node804, with a title node805. The title node805is a parent to a plurality of formatting nodes806. The formatting nodes806configure the format for the table. Each of the formatting nodes either initiates the table, or initiates a row of the table. Within each row of the table are row title nodes808, and arrows810a-c, respectively. The row title nodes808are shown as row titles704inFIG. 7, whereas the data rows810a-care shown as the data rows706a-cinFIG. 7.

FIG. 9illustrates a computer network or similar digital processing environment in which embodiments of the present invention may be implemented.

Client computer(s)/devices50and server computer(s)60provide processing, storage, and input/output devices executing application programs and the like. The client computer(s)/devices50can also be linked through communications network70to other computing devices, including other client devices/processes50and server computer(s)60. The communications network70can be part of a remote access network, a global network (e.g., the Internet), a worldwide collection of computers, Local area or Wide area networks, and gateways that currently use respective protocols (TCP/IP, Bluetooth, etc.) to communicate with one another. Other electronic device/computer network architectures are suitable.

FIG. 10is a diagram of an example internal structure of a computer (e.g., client processor/device50or server computers60) in the computer system ofFIG. 9. Each computer50,60contains a system bus79, where a bus is a set of hardware lines used for data transfer among the components of a computer or processing system. The system bus79is essentially a shared conduit that connects different elements of a computer system (e.g., processor, disk storage, memory, input/output ports, network ports, etc.) that enables the transfer of information between the elements. Attached to the system bus79is an I/O device interface82for connecting various input and output devices (e.g., keyboard, mouse, displays, printers, speakers, etc.) to the computer50,60. A network interface86allows the computer to connect to various other devices attached to a network (e.g., network70ofFIG. 9). Memory90provides volatile storage for computer software instructions92and data94used to implement an embodiment of the present invention (e.g., structure generation module, computation module, and combination module code detailed above). Disk storage95provides non-volatile storage for computer software instructions92and data94used to implement an embodiment of the present invention. A central processor unit84is also attached to the system bus79and provides for the execution of computer instructions.