Text-based inference chaining

BACKGROUND

0001The present disclosure generally relates to information retrieval, and more specifically, automated systems that provide answers to questions or inquiries.

0002Generally, there are many types of information retrieval and question answering systems, including expert or knowledge-based (KB) systems, document or text search/retrieval systems and question answering (QA) systems.

0003Expert or knowledge-based systems take in a formal query or map natural language to a formal query and then produce a precise answer and a proof justifying the answer based on a set of formal rules encoded by humans.

0004Document or text search systems are not designed to deliver and justify precise answers. Rather they produce snippets or documents that contain key words or search terms entered by a user, for example, via a computing system interface, e.g., a web-browser. There is no expectation that the results provide a solution or answer. Text search systems are based on the prevailing and implicit assumption that all valid results to a query are documents or snippets that contain the keywords from the query.

0005QA systems provide a type of information retrieval. Given a collection of documents (such as the World Wide Web or a local collection), a QA system may retrieve answers to questions posed in natural language. QA is regarded as requiring more complex natural language processing (NLP) techniques than other types of information retrieval, such as document retrieval, and QA is sometimes regarded as the next step beyond search engines.

0006Traditional QA systems deliver precise answers, unlike document search systems, but do not produce paths of justifications like expert systems. Their justifications are “one-step” meaning that they provide an answer by finding one or more passages that alone suggest that proposed or candidate answer is correct.

0007It would be highly desirable to provide a system and method that can answer complex inquiries that search systems, classic expert/KB systems and simpler QA systems can not handle.

SUMMARY

0008Embodiments of the invention provide a method, system and computer program product that can answer complex inquiries that search systems, classic expert/KB systems and simpler QA systems can not handle.

0009In one aspect, there is provided a system, method and computer program product for inferring answers to inquiries. The method comprises: receiving an input inquiry; decomposing the input inquiry to obtain one or more factors, the factors forming initial nodes of an inference graph; iteratively constructing the inference graph over content one or more from content sources, wherein at each iteration, a processing device performs discovering solutions to the input inquiry by connecting factors to solutions via one or more relations, each relation in an inference graph being justified by one or more passages from the content, the inference graph connecting factors to the solutions over one or more paths having one or more edges representing the relations; and, providing a solution to the inquiry from the inference graph, wherein a programmed processor device is configured to perform one or more the receiving, decomposing and the iteratively constructing the inference graph to provide the solution.

0010In a further aspect, a method of inferring answers to inquiries comprises: receiving an input inquiry; decomposing the input inquiry to obtain one or more factors; decomposing the input inquiry into query terms, and using the query terms to obtain one or more candidate answers for the input inquiry; iteratively constructing using a programmed processor device coupled to a content storage source having content, a first inference graph using the factors as initial nodes of the first inference graph, a constructed first inference graph connecting factors to one or more nodes that lead to an answer for the inquiry over one or more paths having one or more edges representing the relations; simultaneously iteratively constructing, using the programmed processor device and the content source, a second inference graph using the one or more candidate answers as initial nodes of the second inference graph, the second inference graph connecting candidate answers to one or more nodes that connect to the one or more factors of the inquiry over one or more paths having one or more edges representing relations; and, generating, during the simultaneous iterative constructing, a final inference graph by joining the first inference graph to the second inference graph, the final inference graph having a joined node representing a solution to the input inquiry.

0011In a further aspect, a system for inferring answers to inquiries comprises: one or more content sources providing content; a processor device for coupling to the content sources and configured to: receive an input inquiry; decompose the input inquiry to obtain one or more factors, the factors forming initial nodes of an inference graph; iteratively construct the inference graph over content one or more from content sources, wherein at each iteration, the processing device discovers solutions to the input inquiry by connecting factors to solutions via one or more relations, each relation in an inference graph being justified by one or more passages from the content, the inference graph connecting factors to the solutions over one or more paths having one or more edges representing the relations; and, provide a solution to the inquiry from the constructed inference graph.

0012In a further aspect, there is provided a system for inferring answers to inquiries comprising: one or more content sources providing content; a programmed processor device for coupling to the content sources and configured to: receive an input inquiry; decompose the input inquiry to obtain one or more factors; and, decompose the input inquiry into query terms, and using the query terms to obtain one or more candidate answers for the input inquiry; iteratively construct a first inference graph using the factors as initial nodes of the first inference graph, a constructed first inference graph connecting factors to one or more nodes that lead to an answer for the inquiry over one or more paths having one or more edges representing the relations; simultaneously iteratively construct a second inference graph using the one or more candidate answers as initial nodes of the second inference graph, the second inference graph connecting candidate answers to one or more nodes that connect to the one or more factors of the inquiry over one or more paths having one or more edges representing relations; and, generate, during the simultaneous iterative constructing, a final inference graph by joining the first inference graph to the second inference graph, the final inference graph having a joined node representing a solution to the input inquiry.

0013A computer program product is provided for performing operations. The computer program product includes a storage medium readable by a processing circuit and storing instructions run by the processing circuit for running methods. The methods are the same as listed above.

BRIEF DESCRIPTION OF THE DRAWINGS

0014The objects, features and advantages of the invention are understood within the context of the Detailed Description, as set forth below. The Detailed Description is understood within the context of the accompanying drawings, which form a material part of this disclosure, wherein:

0015<figref idref="DRAWINGS">FIG. 1A</figref> illustrates conceptually an inference graph, generated and used by an embodiment of the inference chaining system and method including an interconnection of nodes by arcs or graph edges;

0016<figref idref="DRAWINGS">FIG. 1B</figref> shows an illustrative example of a generated inference graph in which a relation is represented by the edge between nodes;

0017<figref idref="DRAWINGS">FIG. 2</figref> illustrates a high level schematic of a system and method employing text-based inference chaining system and method;

0018<figref idref="DRAWINGS">FIGS. 3A-3B</figref> illustrate a text-based inference chaining methodology performed by the text-based inference chaining system of the embodiments described herein;

0019<figref idref="DRAWINGS">FIG. 4</figref> illustrates a high level schematic of the text-based inference chaining system and method employing one or more computing devices that perform an iterative process;

0020<figref idref="DRAWINGS">FIG. 5</figref> illustrates a further embodiment of the text-based inference chaining system and method <b>100</b>′ including additional relation injection components;

0021<figref idref="DRAWINGS">FIG. 6</figref> illustrates a further embodiment of the text-based inference chaining system and method <b>100</b>″ including a node filtering component;

0022<figref idref="DRAWINGS">FIG. 7</figref> illustrates an example of a multi-step inference graph generation given an input question;

0023<figref idref="DRAWINGS">FIG. 8</figref> illustrates an embodiment of the factor analysis component of the text-based inference chaining system and method;

0024<figref idref="DRAWINGS">FIG. 9</figref> illustrates a further detailed embodiment of the Question Generation component implementing Relation Injection component to generate natural language questions from an input Inquiry;

0025<figref idref="DRAWINGS">FIG. 10</figref> shows an implementation of a reasoner component receiving as input an inference graph with some events;

0026<figref idref="DRAWINGS">FIGS. 10A-10F</figref> shows an example implementation of a reasoner component processes for a medical domain inquiry example;

0027<figref idref="DRAWINGS">FIG. 11</figref> shows a depth controller processes to analyze a current updated inference graph at each iteration, and decide if the graph should be considered final and the process should halt;

0028<figref idref="DRAWINGS">FIG. 12</figref> is the text-based inference chaining system and method employing a bi-directional graph generation inquiry solution strategy;

0029<figref idref="DRAWINGS">FIG. 13</figref> illustrates a factor-directed or forward-directed inference graph generation iterative process which functions identically as programmed text-based inference chaining system and method;

0030<figref idref="DRAWINGS">FIG. 14</figref> illustrates a hypothesis-directed inference graph generation iterative process implementing a candidate answer generator to produce initial nodes in a backward inference graph;

0031<figref idref="DRAWINGS">FIG. 15</figref> illustrates the implementation of an inference graph joiner process to merge nodes and/or join respective generated forward and backward-directed graphs;

0032<figref idref="DRAWINGS">FIG. 16</figref> depicts an example node joiner process for combining the bi-directionally generated inference graphs by looking for relations between end-point nodes of the forward-directed graph and a node in the backward-directed graph;

0033<figref idref="DRAWINGS">FIGS. 17A-17B</figref> illustrate one example implementation of an Inference Graph generator according to the embodiments described herein;

0034<figref idref="DRAWINGS">FIG. 18</figref> shows a further embodiment of the inference chaining system and method including a parallel, simultaneous implementation of PQA Systems;

0035<figref idref="DRAWINGS">FIG. 19</figref> shows a system diagram depicting a high-level logical architecture and methodology of an embodiment of each PQA system of <figref idref="DRAWINGS">FIG. 18</figref>.

0036<figref idref="DRAWINGS">FIG. 20</figref> illustrates an exemplary hardware configuration of a computing system <b>401</b> in which the present system and method may be employed.

DETAILED DESCRIPTION

0037The present disclosure is directed to an automated reasoning system and, particularly an inference graph generator system and methodology for automated answering of complex inquiries that is fundamentally different from all prior expert systems, knowledge-based systems, or automated reasoning systems.

0038In one aspect, inference graph generator system and methodology may function entirely over unstructured content (e.g. text), and, unlike prior systems, does not require the manual encoding of domain knowledge in the form of formal rules (if-then), axioms or procedures of any kind. Rather the system and methods discover paths from the inquiry to answers by discovering, assessing and assembling justifications from as-is natural language content. Such content is written for humans by humans, never requiring a knowledge engineer to formalize knowledge for the computer. Thus this makes the system and method a powerful reasoning system.

0039The inference graph generator system and methodology operates by providing an explanation of a precise answer based on inference graph that provides a multi-step path from elements in the query to answers or solutions.

0040The inference graph generator system and methodology discovers and justifies a multi-step path from the query to precise answers by iteratively leveraging a probabilistic text-based QA system component and a general probabilistic reasoner component. The present system and method combines these components to produce justified inference graphs over natural language content.

0041More particularly, as described in greater detail herein below, in one embodiment, the inference graph generator system and methodology combines probabilistic QA to discover answers and justifications with Bayesian-type inference to propagate confidence to build inferences graphs that justify multi-step paths from factors to answers.

0042As will be referred to herein, the following definitions are provided:

0043A Natural Language Inquiry is a statement or question in unrestricted natural language (e.g. English) that describes a problem, case or scenario in search of an answer or solution. One example is a simple question in search of a simple answer like “This man sailed across the Atlantic to India and discovered America.” or “Who sailed across the Atlantic . . . . ?” A further example includes a complex description of problems like a patient's history where a diagnosis, treatment or other result is sought after. For example: A 40-year-old female has pain on and off after eating fatty food. She has pain in the epigastric region and sometimes on the right side of her abdomen. After assessing the patient you order ultrasound of the gallbladder. The ultrasound shows presence of gallstones (choledocholithiasis) but no evidence of cholecystitis. The patient goes for an elective cholecystectomy. Pathological examination of the gallbladder showed 3 mixed types of gallstones. The gallbladder mucosa is expected to reveal what change?

0044A Factor is a logically independent element of an inquiry. One example is: “sailed across the Atlantic” “discovered America”, “Patient is 40 years old”, “has pain on and off after eating fatty food.

0045A Relation is a named association between two concepts. For general examples: A “indicates” B, A “causes” B, A “treats” B, A “activates” B, A “discovered” B. The concepts are considered the “arguments” or “end points” of the relation. Concepts are represented by named entities (Washington) or simply phrases (chain smoking) For domain-specific examples (in predicate argument form): author of (Bramstoker, Dracula), president of (Obama, US), causes (smoking, lung cancer), treats (aspirin, stroke)).

0046A Question is a single sentence or phrase in natural language (e.g., English) or a formal language (e.g., First order logic) that intends to ask for the end point(s) of an relation or to ask whether or not a relation between two concepts is true. One example is:

0000“What does aspirin treat?”/treat(aspirin, X) <br /> “Does Aspirin treat Strokes?”/treat(aspirin, strokes)).

0047A Statement is a natural language expression, a structured relation, or a semi-structured relation. Statements are often used to represent factors and may come from structured or unstructured content. Some non-limiting examples:

0048Patient's hemoglobin concentration is 9 g/dL

0049“low hemoglobin concentration” (Patient)

0050Has Condition(Patient, anemia)

0051The patient's mother was diagnosed with breast cancer at the age of 35

0052An Answer or Solution is an element of text—A word, number, phrase, sentence, passage or document. An answer is thought to be correct or partially correct with respect to a question or inquiry if a human considers it useful response to the question or inquiry. In the case of a simple question or relation, the answer is typically the sought-after end-point of the relation, e.g., “Who discovered America in 1492?” The answer is the missing concept, X in the relation “X discovered America”.

0053Unstructured Content is textual data (e.g., books, journals, web pages, documents etc) and is typically used as a source for answers and as a source for justifications of those answers. Is further used to justify or evidence the answer to a question or more specifically the truth of a relation (note: it can consider non-text to determine this). More generally, unstructured content may refer to a combination of text, speech and images.

0054Structured Content is any database or knowledgebase where data is encoded as structured relations. A relational database is typical as is a logical-based knowledgebase.

0055Content is any combination of unstructured and structured content.

0056Passage is a sequence of natural language text—one or more phrases, sentences or paragraphs. These are usually made of up 1-5 sentences.

0057Justifying Passage is a passage thought to explain or justify why an answer may be correct to a given question.

0058Confidence is an indication of the degree to which a relation is believed true, e.g., a measure of certainty or probability that a relation is true. It is usually represented as a number. It may but does not necessarily have to represent a probability.

0059An Inference Graph is any graph represented by a set of nodes connected by edges, where the nodes represent statements and the arcs represent relations between statements. Each relation may be associated with a confidence, and each concept in a relation may be associated with a confidence. Each edge is associated with a set of passages providing a justification for why that relation may be true. Each passage justifying an edge may be associated with a confidence indicating how likely the passage justifies the relation. An inference graph is used to represent relation paths between factors in an inquiry and possible answer to that inquiry. An inference graph is multi-step if it contains more than one edge in a path from a set of factors to an answer. In one embodiment, graph nodes, edges/attributes (confidences), statements and relations may be represented in software, as Java objects. Confidences, strengths, and probabilities are attached to them for processing by various computer systems.

0060A PQA System (Probabilistic QA System) is any system or method that produces answers to questions and may associate those answers with confidences indicating the likelihood the answers are correct, and that may associate answers with a passage-based justification that are intended to explain to humans why the answer is likely correct.

0061<figref idref="DRAWINGS">FIG. 1A</figref> illustrates conceptually an inference graph, generated and used by the programmed inference chaining system and method of the present invention. As shown, inference graph <b>75</b> includes an interconnection of nodes <b>78</b><i>a</i>, <b>78</b><i>b</i>, <b>78</b><i>c </i>by arches or graph edges <b>80</b>. In the inference graph <b>75</b> of <figref idref="DRAWINGS">FIG. 3</figref>, nodes <b>78</b><i>a</i>, <b>78</b><i>b </i>are interconnected by an edge <b>80</b> representing a relation. As shown, each edge or relation <b>80</b> includes a set of annotations <b>85</b>, the set including one or more associated justifying passages.

0062<figref idref="DRAWINGS">FIG. 1B</figref> shows an illustrative example of a generated inference graph <b>88</b> in which a full statement is implied in all nodes, i.e., “Patient has High Blood Sugar” as implied from node <b>79</b><i>a</i>, and “Patient has Diabetes” as implied from node <b>79</b><i>b</i>, etc. The relation represented by the edge between nodes <b>79</b><i>a</i>, <b>79</b><i>b </i>includes a causal relation, i.e., a patient having High Blood Sugar may cause a Diabetes issue in node <b>79</b><i>b. </i>

0063<figref idref="DRAWINGS">FIG. 2</figref> illustrates a high level schematic of a system and method employing text-based inference chaining system and method <b>100</b>. In one aspect, text-based inference chaining system and method <b>100</b> receives a natural language inquiry <b>101</b>, retrieves/accesses unstructured content <b>105</b>, and generates an inference graph <b>110</b>. Particularly, natural language query <b>101</b> is an “inquiry” which is more broadly defined than a typical question. The inquiry may be rich series of statements or sentences that are true about a solution or answer. The inquiry may or may not contain a direct question. Text-based inference chaining system and method <b>100</b> employs the PQA system and a reasoner to discover how one can get from factors in the original inquiry to possible answers through a path of relations justified by different elements (e.g., passages) from the content <b>105</b>. An inference graph <b>110</b> is generated that is analogous to multi-step “proof” for traditional expert system. It does not require a “rule-base” on the content typically provided in text-based QA systems. The inference graph <b>110</b> shows how one can get from elements (i.e., factors) in the original inquiry to possible answers through a multi-step path of relations each justified by different passages from the content. It is understood that the inference chaining system and method <b>100</b> may include an implementation having a different combinations of embodiments as will be described herein with respect to <figref idref="DRAWINGS">FIGS. 4</figref>, <b>5</b>, <b>6</b>.

0064<figref idref="DRAWINGS">FIG. 4</figref> illustrates a high level schematic of the text-based inference engine <b>100</b>. The text-based inference chaining system and method <b>100</b> is a computer system employing one or more computing devices that perform an iterative process <b>99</b> that generates a final inference graph <b>110</b>F given an input inquiry <b>101</b>, a set(s) of factors, and determined relations. The text-based inference chaining system and method <b>100</b> first implements a factor analysis component <b>104</b> implementing programmed processes to extract factors <b>106</b> from the input inquiry <b>101</b>. Factor analysis component <b>104</b> is described in greater detail herein with respect to <figref idref="DRAWINGS">FIG. 8</figref>. Programmed processes further generate an initial inference graph <b>110</b>I using factors extracted from the inquiry. This initial inference graph <b>110</b>I may only include factors <b>106</b> extracted from the inquiry as initial end-points or nodes. This initial inference graph <b>110</b>I may be stored as data in a storage device <b>107</b>. As will be described in greater detail, iterative processes <b>99</b> further discover relations to a new set of concepts from the factors <b>106</b> that may lead to answers or solutions.

0065In one aspect, the text-based inference chaining system and method <b>100</b> provides a system and method that discovers and justifies answers to inquiries by constructing inference graphs over content connecting factors to answers such that each relation in an inference graph is justified by one or more passages from the content and where the inference graph may connect factors to answers over a path containing one or more edges (i.e., multi-step inference graph).

0066At the start of the iteration(s), from the generated initial inference graph <b>110</b>I (or a generated updated inference graph <b>110</b>U to be extended in a subsequent iteration), a question generator <b>112</b> implements a programmed process to first generate questions for the PQA system <b>115</b> to answer. As revised inference graphs are generated at each iteration, new questions may be generated for PQA system to answer. Particularly, at each iteration for every new end-point of every new relation in the inference graph, the question generator <b>112</b> formulates one or more questions for the PQA system to answer. Question generator component <b>112</b> is described in greater detail herein with respect to <figref idref="DRAWINGS">FIG. 9</figref>. Parallel implemented PQA system <b>115</b> receives the formulated questions based on the prior inference graph, e.g., graph <b>110</b>P. Based on number of independent questions generated, one or more PQA systems may be called in parallel to discover new relations that answer the questions. The PQA system is a type of natural language question-answering system that takes in a NL question and returns a set of possible answers, a confidence score for each answer indicating a probability the answer is correct, and a set of justifying passages for each answer extracted from the body of content that provides evidence for why the answer may be correct. In one embodiment, IBM DeepQA system may be implemented as the PQA system <b>115</b>. For a description of IBM DeepQA refer to the description of <figref idref="DRAWINGS">FIG. 19</figref>. Other possible QA systems that may be implemented as possible embodiments for the PQA system are Javellin (CMU), Ephera (CMU and Open-Source), SMART (MIT), Wolfram Alpha (Wolfram). These each attempt to produce precise answers to natural language questions but vary in their ability to produce confidence scores and justifying passages.

0067The PQA system <b>115</b> performs processes to obtain or discover new relations <b>116</b> that answer the questions from the structured or unstructured content <b>105</b>. The discovered new relations <b>116</b> additionally include confidences and may be stored as data in a storage device <b>117</b> which may be or include the storage device <b>107</b>.

0068As further shown in <figref idref="DRAWINGS">FIG. 4</figref>, in a current iteration, a graph extender component <b>118</b> implements programmed processes to receive the stored new relations and confidences data <b>117</b> and extends the previous inference graph <b>110</b>P generated in the immediately prior iteration (e.g., which is <b>110</b>I at the first iteration) based on the new relations and confidences data <b>117</b>. Particularly, graph extender <b>118</b> receives the new relations and confidences <b>117</b> and processes the new relations by merging them into the previous inference graph <b>110</b>P to result in a new extended inference graph <b>110</b>E shown as output from the graph extender <b>118</b> and may be stored as data in a storage device <b>107</b>.

0069More particularly, the graph extender <b>118</b> takes as input the previous inference graph <b>110</b>P and a set of new relations <b>116</b> discovered by the PQA component and outputs a new inference graph <b>110</b>E that includes the new relations. It performs this by merging nodes in the input inference graphs with nodes in the new relations and adding them to the graph. An example follows:

Input: Inference Graph: A→B→C

Input: New Relations: C1→D

Output: A→B→(C/C1)→D

0070where C and C1 where merged (considered the same node). The computed confidence on C/C1→D is the same confidence produced by the PQA <b>115</b> system's answer to the question about C that produced C1→D.

0071In one embodiment, merging nodes may be implemented using some form of “specialization”. For example, if C was “diabetes”, and D was “blindness”, the question generated was “What causes blindness?” and the PQA system produces and relation “diabetes mellitus causes blindness” then the graph extender <b>118</b> would merge “diabetes” with “diabetes mellitus”. In this case the embodiment may only merge nodes if they were identical or if answer was a connected to a more specific concept. Thus, “diabetes” would merge with “diabetes” or with “diabetes mellitus”. At this point, confidences are not re-propagated over the extended graph <b>110</b>E as this is performed by the reasoner component <b>150</b>.

0072As shown in <figref idref="DRAWINGS">FIG. 4</figref>, the reasoner component <b>150</b> performs programmed processes to propagate computed confidences across the relations to output an updated (for the current iteration) inference graph <b>110</b>U assured of a particular confidence level across the relations. That is, as part of the reasoner process, additional pruning may be performed as certain relation confidences generated by the PQA system may drop below a set threshold. It may also merge relations based on similarity metrics.

0073The reasoner component <b>150</b> is described in greater detail herein with respect to <figref idref="DRAWINGS">FIGS. 10 to 10D</figref>. In one embodiment, the reasoner component <b>150</b> receives as input: (1) a set of relations between inference graph nodes, (2) factors, and (3) candidate solutions or answers; and outputs a probability for each node in the inference graph. The reasoner component <b>150</b> may also optionally output an explanation of why the answer was correct. An algorithm that has these inputs and outputs can function as a reasoned component <b>150</b> as further described below with respect to <figref idref="DRAWINGS">FIGS. 10 to 10D</figref>.

0074Returning to <figref idref="DRAWINGS">FIG. 4</figref>, a depth controller component <b>175</b> performs processes to receive the new updated inference graph <b>110</b>U, and determine a need to halt the iteration based on the specified depth or other criteria. The depth controller component <b>175</b> provides the ability for the inference chaining system and method to iteratively extend the initial inference graph formed from the original factors output by factor Analysis. This iterative process will continue to grow the graph unless it is stopped and the depth controller component <b>175</b> provides the ability to halt the iterative process based on a specified depth or other criteria.

0075The depth controller component <b>175</b> is described in greater detail in <figref idref="DRAWINGS">FIG. 11</figref>. At each iteration, the depth controller component <b>175</b> performs a method to analyze the current updated inference graph <b>110</b>U, and decide if the graph should be considered final and the process halted. The depth controller may be implemented in a variety of ways. For example, the depth controller may look for a pre-determined depth represented by an integer considered the “Depth Threshold” (DT) value, for example, determining if the current iteration has a DT value of 2. In this example, once a graph has extended two steps (relations) from the original factors the iteration will stop and the graph is output as final. Another embodiment may consider a “Confidence Threshold” (CT) value, for example, determining there is a node in graph <b>110</b>U that has confidence >=CT. In this example, the depth controller <b>175</b> would halt the iteration and output the graph <b>110</b>U as a final inference graph <b>110</b>F if it contained any node that was associated with a confidence higher than a given CT value. Any combination of depth and confidence threshold may be used in an embodiment of the depth Controller <b>175</b>. For example the system may halt and output the final graph if the depth controller detects if the graph has reached a certain depth or if it contains a high-confidence node—which ever comes first.

0076Returning to <figref idref="DRAWINGS">FIG. 4</figref>, if a need to halt the iteration is determined, the updated inference graph <b>110</b>U is output as the final inference graph <b>110</b>F and stored in a storage device <b>107</b>. At that point final inference graph <b>110</b>F will include a set of nodes and relations <b>126</b> that satisfy the depth or confidence criterion. Otherwise, the updated inference graph <b>110</b>U is to be extended and is provided as input to question generator component <b>112</b> as a new inference graph of nodes and relations for the next iteration <b>99</b>.

0077<figref idref="DRAWINGS">FIG. 5</figref> illustrates a further embodiment of the text-based inference chaining system and method <b>100</b>′ including additional relation injection components. In order to make the inference chaining system and method more modular and extensible a relation type injection component <b>130</b> may be introduced that separates the logic of forming a natural language question for the PQA system from the relation types used to seed those questions. The relation type injection component <b>130</b> determines what relation type or types <b>135</b> should be asked for given a particular node.

0078Generally, the relation type injection component <b>130</b> receives the initial inference graph <b>110</b>I, and considers the inquiry and the set of initial factors <b>106</b> to determine a set of seed relations or relation types <b>135</b> for use by the question generation component <b>112</b>. The question generation component <b>112</b> is parameterized to allow for the independent provision of a set of relation types <b>135</b>. These are then used as seeds for generating questions for the PQA system <b>115</b>.

0079<figref idref="DRAWINGS">FIG. 6</figref> illustrates a further embodiment of the text-based inference chaining system and method <b>100</b>″ including a node filtering component <b>140</b> for selecting statements and removing them from further consideration in the generation of the inference graph to improve the efficiency of the process. Generally, the node filtering component <b>140</b> receives the new relations and confidences <b>126</b> and the previous inference graph <b>110</b>P data content. As many proposed relations with varying confidences are output by the PQA system <b>115</b>, the node filtering component <b>140</b> implements processes to remove some of the new nodes (i.e., new relation end-points) from consideration based on a variety of pruning algorithms. A simple pruning algorithm may involve providing a confidence threshold cut-off. In this embodiment, a subset of the new nodes <b>142</b> would be used to extend the inference graph <b>110</b>P by graph extender component <b>118</b>.

0080<figref idref="DRAWINGS">FIG. 3A</figref> illustrates a text-based inference chaining methodology <b>1000</b> performed by the text-based inference chaining system <b>100</b>, <b>100</b>′, <b>100</b>″ of <figref idref="DRAWINGS">FIGS. 4-6</figref>. As shown at a first step <b>1003</b>, there is performed: receiving, at the inference-based chaining system, an input inquiry; decomposing the input inquiry to obtain one or more factors using NLP text analysis, factor identifying and factor weighing; and, forming initial nodes of an inference graph. Then, at <b>1005</b>, processes are performed to iteratively construct the inference graph over one or more content sources, wherein at each iteration, the computer-implemented, text-based inference chaining system discovers answers to the input inquiry by connecting factors to the answers via one or more relations, each relation in the inference graph being justified by one or more passages from the content sources. The inference chaining processes connecting factors to said solutions in the inference graph over one or more paths having one or more edges representing the inferred relations. Finally, at <b>1010</b>, text-based inference chaining method provides a solution having the highest confidence (as represented by a computed probability value) to the inquiry from the inference graph.

0081<figref idref="DRAWINGS">FIG. 3B</figref> is a detailed flow chart illustrating the inference graph generation step <b>1005</b> of <figref idref="DRAWINGS">FIG. 3A</figref>. As shown in <figref idref="DRAWINGS">FIG. 3B</figref>, at <b>1050</b>, the text-based inference chaining methodology <b>1000</b> performed by the text-based inference chaining system <b>100</b>, <b>100</b>′, <b>100</b>″ of <figref idref="DRAWINGS">FIGS. 4-6</figref> enters an iterative loop, where at a first step <b>1055</b> there is performed the generating of one or more questions based on one or more current nodes in the graph. In the first iteration, the initial nodes represent the factors from the original input inquiry. Although not shown, relations injection techniques may be performed to determine what relation type or types should be asked for given node. Then, at <b>1060</b>, there is performed searching in one or more content sources (e.g., the Internet) to identify one or more relations leading to new solutions. It is understood that based on number of independent questions generated, one or more QA systems may be called in parallel to discover new relations that answer the questions. These new answers extend the current inference graph by representing them as new additional nodes in the inference graph, with each new additional node connected via an edge representing the relation, and each relation having an associated justifying passage at an associated probability or confidence level. It is further understood that the node filtering component may be further implemented to remove some of the new nodes (new relation end-points) from consideration based on a variety of pruning algorithms. Then, at <b>1065</b>, there is performed inferring, from the associated confidence levels, by the reasoner component, a confidence level at each node of the extended inference graph to provide an updated inference graph. Then at <b>1070</b>, the inference chaining system determines whether the updated inference graph meets a criteria for terminating the iteration. This is performed by the system depth controller element <b>117</b> described in greater detail herein above with respect to <figref idref="DRAWINGS">FIG. 11</figref>. At <b>1070</b>, if it is determined that the termination criteria has not yet been met (both the DT and CT levels have not been met or exceeded), then the process proceeds back to <b>1055</b>, where the steps of questions generating, searching, confidence inferring and termination criteria determining steps with the new additional nodes being current nodes of the inference graph are repeated in a next iteration, otherwise, the iterations terminate

0082<figref idref="DRAWINGS">FIG. 7</figref> illustrates an example of a multi-step inference graph <b>90</b> generation performed by a text-based inference chaining system and method as described above. For example, in a medical domain inquiry regarding Parkinson's disease, an initial inference graph <b>110</b>I may contain a node “resting tremor” among other nodes. The PQA system for question “what causes resting tremor” may returned many possible answers with associated confidences. For example, Parkinson's Disease (32%), Dystonia (8%), . . . , Multiple system atrophy (3%). Assuming, for this example, that “multiple system atrophy” was not an argument to any relation found for any of the other factors. Then, its overall confidence value determined by the reasoner component would be very low. Alternatively, the node filtering component would assign a very low priority score to the “Multiple system atrophy” node (relative to more likely nodes such as Parkinson's Disease) and it could be pruned (removed from further consideration when extending the inference graph).

0083As shown in <figref idref="DRAWINGS">FIG. 7</figref>, there is input a question <b>92</b> in a medical domain: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0084">A 63-year-old patient is sent to the neurologist with a clinical picture of resting tremor that began 2 years ago. At first it was only on the left hand, but now it compromises the whole arm. At physical exam, the patient has an unexpressive face and difficulty in walking, and a continuous movement of the tip of the first digit over the tip of the second digit of the left hand is seen at rest. What part of his nervous system is most likely affected?</li></ul></li></ul>

0085As shown, the following factors <b>94</b> generated by the inference chaining system and method may include the following:

008663-year-old

0087Resting tremor began 2 years ago

0088. . . in the left hand but now the whole arm

0089Unexpressive face

0090Difficulty in walking

0091Continuous movement in the left hand

0092In a first iteration of the inference chaining method, factors <b>94</b> obtained from the input query may be found associated with (i.e., relate to) inferred nodes <b>95</b>, e.g., Parkinson's Disease <b>95</b>A, or Athetosis <b>95</b>B. From inferred node <b>95</b>B, further answers <b>95</b>C, <b>95</b>D may be inferred from additional relations obtained in a further iteration of the inference chaining method. For each of the factors found for the medical domain example, a respective relation that associates the factor to an answer is created and represented as an edge in the inference graph. For example, for each of the following factors <b>94</b>A in the medical domain example relating to an inferred answer Parkinson's Disease:

009363-year-old

0094Resting tremor began 2 years ago

0095. . . Unexpressive face

0000the following relations corresponding to respective justifying passages represented by respective inference graph edges of the inference graph found at a first inference chaining iteration are listed below.

0096Edge: <b>96</b>A indicates Parkinson's Disease by a discovered example justifying passage: “The mean age of onset of Parkinson's Disease is around 60 years.”

0097Edge: <b>96</b>B: indicates Parkinson's Disease by a discovered example justifying passage: “Resting tremor is characteristic of Parkinson's Disease.”

0098Edge: <b>96</b>C indicates Parkinson's Disease by a discovered example justifying passage: “Parkinson's disease: A slowly progressive neurologic disease that is characterized by a fixed inexpressive face . . . ”

0099Further in the medical domain example, in a first iteration of the inference chaining method, factors <b>94</b>B may each be found associated with (i.e., relate to) a node <b>95</b>B, e.g., Athetosis. For example, for each of the following factors <b>94</b>B in the medical domain example relating to answer Athetosis:

0100Difficulty in walking

0101Continuous movement in the left hand

0000the following relations corresponding to respective justifying passages with representative respective inference graph edges are listed below.

0102Edge: <b>96</b>D indicates Athetosis by a discovered example justifying passage: “Patients suffering from athetosis often have trouble in daily activities such as eating, walking, and dressing”

0103Edge: <b>96</b>E indicating Athetosis by a discovered example justifying passage: “Athetosis is defined as a slow, continuous, involuntary writhing movement that prevents the individual from maintaining a stable posture.”

0104As shown in the graph of <figref idref="DRAWINGS">FIG. 7</figref>, the thickness of the relation (node graph edge) indicates a confidence level in the answer (e.g., a probability), and the strength of the associated relation. For the medical domain example, the inferred node Parkinson's Disease <b>95</b>A relates most strongly to the factor “Resting tremor began 2 years ago,” as indicated by the thickness of edge <b>96</b>B as compared to relation strengths represented by edges <b>96</b>A and <b>96</b>C.

0105Further in the medical domain example of <figref idref="DRAWINGS">FIG. 7</figref>, in a second or subsequent iteration of the inference chaining method described herein, from each of the inferred nodes <b>95</b>A and <b>95</b>B, a further inferred nodes may be generated from additional relations obtained by the inference chaining method.

0106For example, inferred node <b>95</b>B Athetosis becomes a new factor from which new questions are generated and new relations <b>97</b>A and <b>97</b>B inferred from PQA/reasoner implementation leading to new inferred nodes, Basal Ganglia <b>95</b>C and Striatum <b>95</b>D. The following are relations represented by respective inference graph edges based on the newly discovered nodes <b>95</b>C, <b>95</b>D:

0107Edge: <b>97</b>A indicating Basal Ganglia <b>95</b>C by a discovered example justifying passage: “Athetosis is a symptom primarily caused by the marbling, or degeneration of the basal ganglia. In one embodiment, this discovered relation may have resulted from injecting a “caused by” or “affects” relation in a relation injection process.

0108Edge: <b>97</b>B indicating Striatum <b>95</b>D by a discovered example justifying passage: “Lesions to the brain, particularly to the corpus striatum, are most often the direct cause of the symptoms of athetosis. In one embodiment, this discovered relation may have resulted from injecting a “caused by” relation in a relation injection process.

0109The thickness of node graph edges <b>97</b>A, <b>97</b>B indicates a confidence level in the answer (e.g., a probability), and the strength of the associated relation.

0110Further in the medical domain example of <figref idref="DRAWINGS">FIG. 7</figref>, in a further iteration of the inference chaining method, inferred nodes (or factors) <b>95</b>A, <b>95</b>C and <b>95</b>D may each be further found associated with (i.e., relate to) new inferred nodes <b>98</b>A-<b>98</b>E corresponding to candidate answers (new nodes) Cerebellum <b>98</b>A, Lenticular nuclei <b>98</b>B, Caudate nucleus <b>98</b>C, Substantia nigra <b>98</b>D and Pons <b>98</b>E. In the inference chaining method, as shown in <figref idref="DRAWINGS">FIG. 7</figref>, inferred nodes <b>95</b>A (Parkinson's Disease), <b>95</b>C (Basal Ganglia) and <b>95</b>D (Striatum) each are found to strongly relate to the inferred new node <b>98</b>D (Substantia nigra) by following relations represented by respective inference graph edges:

0111Edge: <b>93</b>A indicating Substantia nigra by example justifying passage: “Parkinson's disease is a neurodegenerative disease characterized, in part, by the death of dopaminergic neurons in the pars compacta of the substantia nigra.” This relation may have been discovered by injecting a “caused by” relation in a relation injection process.

0112Edge: <b>93</b>B indicating Substantia nigra by example justifying passage: “The pars reticulata of the substantia nigra is an important processing center in the basal ganglia.” This relation may have been discovered by injecting an “contains” relation in a relation injection process.

0113Edge: <b>93</b>C indicating Substantia nigra by example justifying passage: “Many of the substantia nigra's effects are mediated through the striatum.” This relation may have been discovered by injecting an “associated with” relation in a relation injection process.

0114Although not shown, it is assumed that from these inferred nodes <b>95</b> of the medical domain example of <figref idref="DRAWINGS">FIG. 7</figref> there may be further indicated candidate answers <b>98</b>A-<b>98</b>C and <b>98</b>E by further respective edges and justifying passages (not shown).

0115As shown, the substantial thickness of edges <b>93</b>A and <b>93</b>B relating to the candidate answer, Substantia nigra <b>98</b>D, indicate corresponding associated scores having a higher confidence. Furthermore, the answer node Substantia nigra <b>98</b>D is shown having a substantially thicker border compared to the other candidate answers <b>98</b> because the overall confidence score for Substantia nigra <b>98</b>D is higher than the other candidate answers. As such, Substantia nigra <b>96</b>D would be the most likely candidate answer to the question <b>92</b> as reflected by the check mark.

0116<figref idref="DRAWINGS">FIG. 8</figref> illustrates an embodiment of the factor analysis component <b>104</b> of the text-based inference chaining system and method of <figref idref="DRAWINGS">FIGS. 4-6</figref> that cooperatively performs processes to generate from a natural language inquiry a set of factors that represents the initial nodes of an inference graph. The factor analysis component <b>104</b> includes a text analysis component <b>204</b> which may include a known system and program such as MetaMap that receives natural language text/inquiry input and analyzes the input with a stack <b>210</b> of natural language processor (NLP) components. For more details on MetaMap refer to Alan R. Aronson and Francois-Michel Lang, “An overview of MetaMap: Historical Perspective and Recent Advances,” <i>J. Am. Med. Inform. Assoc., </i>2010, incorporated herein by reference. MetaMap is available at http://metamap.nlm.nih.gov/.

0117The NLP stack <b>210</b> components include, but are not limited to, relationship classification <b>210</b>A, entity classification <b>210</b>B, parsing <b>210</b>C, sentence boundary detection <b>210</b>D, and tokenization <b>210</b>E processes. In other embodiments, the NLP stack <b>210</b> can be implemented by IBM's LanguageWare®, Slot Grammer as described in Michael C. McCord, “Using Slot Grammer,” IBM Research Report 2010, Stanford University's Parser as described in Marie-Catherine de Marneffe, et. al., “Generating Typed Dependency Parses from Phrase Structure Parses,” LREC 2006, or other such technology components.

0118Factor identification component <b>208</b> implements processes for selecting factors and may include a process that selects all the entities classified as symptoms, lab-tests or conditions by the NLP Stack <b>210</b>. Factor weighting component <b>212</b> may implement such techniques as inverse document frequency (IDF) for producing weights for each of the factors.

0119Factor analysis component <b>104</b> identifies segments of the input inquiry text as “factors”. This may be terms, phrases or even entire sentences from the original input. A very simple implementation of factor identification, for example in the case of USMLE (United States Medical Licensing Examination® (see http://www.usmle.org/) questions, are that the actual sentences in the case are each a factor.

0120In one embodiment, the factor identification takes as input a natural language inquiry and produces as initial inference graph containing one or more nodes—these nodes are referred to as the factors. A factor is a statement that is asserted to be true in the natural language inquiry. For example, in the medical domain, the inquiry may provide several observations about a patient and then ask a specific question about that patient, as in: <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0000"><ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0121">A 63-year-old patient is sent to the neurologist with a clinical picture of resting tremor that began 2 years ago. At first it was only on the left hand, but now it compromises the whole arm. At physical exam, the patient has an unexpressive face and difficulty in walking, and a continuous movement of the tip of the first digit over the tip of the second digit of the left hand is seen at rest. What part of his nervous system is most likely affected?</li></ul></li></ul>

0122The factor analysis component <b>104</b>, may choose to generate factors at various levels of granularity. That is, it is possible for the text-based inference chaining system and method to use more than one factor identification component <b>208</b>. The level of granularity is programmable so that: (1) questions can be subsequently generated for the PQA system from each factor because the quality of the PQA system's answers may depend on the size and amount of information content in the question; and (2) the resulting inference graph could be used to explain to a user what factors were indicative of different candidate answers. For example, if the factors are very coarse grained this may have limited utility.

0123In one example, factor analysis implementation might produce just one factor that contains all of the information in the inquiry. However, this level of granularity provides two problems, (1) the PQA may not be as effective on a question that is generated from such a coarse-grained factor, and (2) even if a good answer can be produced, the resulting inference graph may not explain what part of the inquiry was most important in determining the decision, which is useful information for the user.

0124In a further factor analysis implementation example, the inquiry is divided by the sentences. In the above-identified medical domain example, the factor analysis component would produce three separate factors (initial nodes in the inference graph), with the following statements: <ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0000"><ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0125">1) A 63-year-old patient is sent to the neurologist with a clinical picture of resting tremor that began 2 years ago.</li><li id="ul0006-0002" num="0126">2) At first it was only on the left hand, but now it compromises the whole arm.</li><li id="ul0006-0003" num="0127">3) At physical exam, the patient has an unexpressive face and difficulty in walking, and a continuous movement of the tip of the first digit over the tip of the second digit of the left hand is seen at rest.</li></ul></li></ul>

0128To produce more fine-grained factors, natural language processing (NLP) components such as parsers, entity recognizers, relation detectors, and co-reference resolvers could be used. One use case for a co-reference resolver is in the example of second factor 2) above, where it would be important to know that the word “it” refers to the “tremor”. Named entity recognizers are implemented to identify mentions of important domain concepts, such as symptoms in the medical domain. Relation detectors, often based on the parser output, can be used to identify if those concepts are attributed to the patient. A factor analysis component <b>104</b> implementation based on such NLP analysis might then produce factors such as: <ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0000"><ul id="ul0008" list-style="none"><li id="ul0008-0001" num="0129">1) Patient is 63-years old</li><li id="ul0008-0002" num="0130">2) Patient has resting tremor</li><li id="ul0008-0003" num="0131">3) Tremor began 2 years ago</li><li id="ul0008-0004" num="0132">4) Tremor was only on the left hand, but now it compromises the whole arm</li><li id="ul0008-0005" num="0133">5) Patient has unexpressive face</li><li id="ul0008-0006" num="0134">6) Patient has difficulty in walking</li><li id="ul0008-0007" num="0135">7) Continuous movement of the tip of the first digit over the tip of the second digit of the left hand is seen at rest.</li></ul></li></ul>

0136As further shown, the factor weighting component <b>212</b> is useful as some factors may be more important than others in finding and scoring an answer. Various techniques are possible for initializing the confidence weighting in each factor. For example, the factor with the must unique terms relative to the domain may be given a higher weight than other factors. Known techniques including inverse document frequency (IDF) can be used for producing weights for each of the factors. As shown, the resulting set of factors <b>215</b> is generated after the factor analysis process is complete, each factor representing the initial nodes <b>106</b> in an initial inference graph <b>1101</b>.

0137Inference chaining systems <b>100</b>, <b>100</b>′, <b>100</b>″ of respective <figref idref="DRAWINGS">FIGS. 4-6</figref> for producing inference graphs over content to answer inquiries each use a probabilistic QA system <b>115</b> for discovering relations, and a parameterized question generation component <b>112</b> that generates questions that may be based on a one or mores independently generated relation types from a relation type injection component <b>130</b> for providing seed logical relations for generating questions for the PQA system <b>115</b>.

0138<figref idref="DRAWINGS">FIG. 9</figref> illustrates a further detailed embodiment <b>300</b> of the question generation component <b>112</b> of the text-based inference chaining system implementing a relation injection component <b>130</b> to generate natural language questions <b>315</b> from the input inquiry <b>101</b>.

0139Question generation component <b>112</b> takes as input a node <b>106</b> from an initial inference graph <b>1101</b> and produces as output one or more natural language questions <b>315</b>, formatted in a manner suitable for processing by the PQA system <b>115</b> in order to elicit responses that will be used to assert new relations into the inference graph.

0140In one embodiment, the question generation component <b>112</b> performs processes to produce questions that only ask for one kind of relation. For example, the “causes” relation. A simple implementation could just produce questions of the form “What causes: X?” where X is the text of the inference graph node <b>106</b>. Thus, from the above described medical domain example, given the initial graph node <b>106</b><ul id="ul0009" list-style="none"><li id="ul0009-0001" num="0000"><ul id="ul0010" list-style="none"><li id="ul0010-0001" num="0141">Patient has resting tremor</li></ul></li></ul>

0142Question Generation component <b>112</b> may generate the question: <ul id="ul0011" list-style="none"><li id="ul0011-0001" num="0000"><ul id="ul0012" list-style="none"><li id="ul0012-0001" num="0143">What causes: Patient has resting tremor?</li></ul></li></ul>

0144Another embodiment might produce more straightforward and grammatical questions, for example by applying question generation patterns or templates <b>125</b>. An example of such a pattern could represent that the reference to a patient can be eliminated and in the above medical domain example produce the question: <ul id="ul0013" list-style="none"><li id="ul0013-0001" num="0000"><ul id="ul0014" list-style="none"><li id="ul0014-0001" num="0145">What causes resting tremor?</li></ul></li></ul>

0146Depending on the PQA system <b>115</b>, asking this question may result in improved answers. Question generation component <b>112</b> further implements programmed processes for producing questions that ask for many different kinds of relations (e.g., “causes”, “indicates”, “is associated with”, “treats”).

0147As further shown in <figref idref="DRAWINGS">FIG. 9</figref>, relation type injection component <b>130</b> separates the logic of forming a natural language question for the PQA system <b>115</b> from the relation types used to seed those questions. Relation type injection component <b>130</b> implements processes to decide what relation type or types should be asked for a given graph node <b>106</b>. Relation type injection component <b>130</b> may decide on the relation type by determining the type of the inference graph node <b>106</b> and possibly the target type that the natural language inquiry is asking for, for example, a disease, a location, an organ, a treatment, a drug, etc. For example, given an inference graph node <b>106</b> “Parkinson's Disease”, and with knowledge that the inquiry asked for a treatment, the injection component would generate the question “What treats Parkinson's Disease?”, rather than “What causes Parkinson's Disease.”

0148The question generation component <b>112</b> then in its general form combines relation types <b>136</b> with question templates or patterns <b>125</b>. For example, relation types <b>136</b> “causes”, “indicates” or “treats” can be applied to question templates <b>125</b> such as: <ul id="ul0015" list-style="none"><li id="ul0015-0001" num="0000"><ul id="ul0016" list-style="none"><li id="ul0016-0001" num="0149">What <relation> <factor>?</li><li id="ul0016-0002" num="0150">What <inverse-relation> <factor>?</li></ul></li></ul>

0151To get corresponding questions such as, for example <ul id="ul0017" list-style="none"><li id="ul0017-0001" num="0000"><ul id="ul0018" list-style="none"><li id="ul0018-0001" num="0152">What causes <factor>?</li><li id="ul0018-0002" num="0153">What is caused by <factor>? <br /> where depending on the node in the inference graph, the process may decide to substitute <factor> with the node phrase, for example: </li><li id="ul0018-0003" num="0154">“resting tremor” <br /> would produce the question: </li><li id="ul0018-0004" num="0155">What causes a resting tremor? <br /> and </li><li id="ul0018-0005" num="0156">What indicates a resting tremor?</li></ul></li></ul>

0157As mentioned above in connection with <figref idref="DRAWINGS">FIG. 4-6</figref>, an example implementation of the reasoner component <b>150</b> is now described in greater detail herein below with respect to FIGS. <b>10</b> and <b>10</b>A-<b>10</b>D.

0158<figref idref="DRAWINGS">FIG. 10</figref> shows an implementation of the reasoner component <b>150</b> receiving as input an inference graph, such as extended inference graph <b>110</b>E, with one or more statements identified as candidate endpoint nodes <b>151</b>. Reasoner performs processes to generate from said input an output probability (or confidence level) for each statement at a node <b>151</b>, for subsequent merging or reading back into the inference graph forming updated graph <b>110</b>U.

0159In one embodiment, a method for computing probabilities at a node may include counting the number of paths to each node, and normalizing to make a number between 0 and 1 for each node.

0160In a further embodiment, as shown as processes <b>153</b> and <b>155</b>, a Bayesian network is generated from the inference graph. As shown in <figref idref="DRAWINGS">FIG. 10</figref>, the reasoning employed as programmed processes has two steps described below.

0161Assimilation includes processes <b>153</b> to convert the set of relations into a valid Bayesian network having no cycles. Processes may be optionally performed to optimize the graph for inference by removing redundant paths. It is understood that a valid Bayesian network may have a different structure. For the example, as depicted in <figref idref="DRAWINGS">FIG. 10</figref>, a cycle has been resolved by removal of relation <b>152</b> from the input inference graph <b>110</b>E.

0162Given the assimilated graph, inference includes processes <b>155</b> that are implemented to use belief propagation to infer the probabilities of unknown nodes (i.e., candidates) from probabilities of known nodes (i.e. factors). <figref idref="DRAWINGS">FIG. 10</figref> shows the example nodes <b>151</b><i>a, </i><b>151</b><i>b </i>from the input inference graph, where node <b>151</b><i>a </i>is shown having a thicker border representing an event assertion having a greater computed confidence (higher probability) than the confidence value computed for additional event assertion of candidate node <b>151</b><i>b</i>. One technique for performing belief propagation can be found in a reference to Yedida J. S., Freeman, W. T., et. al. “Understanding Belief Propagation and Its Generalizations”, <i>Exploring Artificial Intelligence in the New Millennium</i>, Chap. 8, pp. 239-236, January 2003 (Science and Technology Books) incorporated by reference herein.

0163In the reasoner component <b>150</b>, inferred probabilities are then read back into the input inference graph, e.g., inference graph <b>110</b>E, as shown at <b>157</b> by copying the number (probability value) computed from the Bayesian Network to the corresponding node in the inference graph which gets passed to the merging process <b>156</b> with unmodified structure.

0164In one embodiment, the reasoned component <b>150</b> does not return the assimilated Bayesian network. It leaves the input inference graph unchanged except for the computed (inferred) event probabilities as output inference graph <b>110</b>U at <b>159</b>. It is further understood that explanations may be generated by describing the edges along the strongest path (most belief propagated) from known factors to the chosen candidate, e.g., node <b>151</b><i>a. </i>

0165In <figref idref="DRAWINGS">FIG. 10A</figref>, for the medical domain example, the reasoner component <b>150</b> receives data representing an example inference graph <b>161</b> including a set of relations R, whereby the inference graph includes (1) a relation R1 indicating Tremor indicates Parkinson's; (2) a relation R2 indicating Parkinson's causes tremor; and (3) a relation R3 that indicates Parkinson's indicates substantia nigra. Inference chaining may find a set of relations from a factor “termor” to produce candidate answers such as Basal ganglia (not shown) and a candidate answer Pons <b>163</b> as shown in <figref idref="DRAWINGS">FIG. 10A</figref>.

0166More generally, with reference to <figref idref="DRAWINGS">FIGS. 4-6</figref>, the data structures input and output by the reasoner component <b>150</b> are as follows. The input is an object called an “inference question,” which includes: (1) a collection of relations, where a relation has a head node, a tail node, a type, and a strength; (2) a collection of nodes identified as factors, with assigned probabilities; and (3) a collection of nodes identified as candidates, whose probability is not necessarily known. The reasoner component <b>150</b> output includes a probability for each node in the graph, including candidates. The reasoner component <b>150</b> may optionally output an explanation for why each candidate received the probability that it did.

0167The reasoner component <b>150</b> is programmed to assign a probability to all nodes, not just candidates, because the question generation component <b>112</b> may give higher priority to some non-candidate nodes based on their propagated probability. One particular implementation includes a Bayesian network but the reasoner component may implement other techniques.

0168For example, the Bayesian network may be used for training the probabilistic QA system as follows. Asserting the correct answer as set to probability 1, and disasserting the incorrect answers as set to probability 0. Then propagate belief through the graph. Edges that pass positive messages can be used as positive training examples, and edges that pass negative messages can be used as negative training examples.

0169As the inference graph <b>161</b> of <figref idref="DRAWINGS">FIG. 10A</figref> may not form a valid Bayesian network because relations R1 and R2 form a cycle, then as part of the assimilation component of the reasoning processes performed, the reasoner component <b>150</b> implements processes to convert the inference graph to a valid Bayesian network, for instance, by dropping the weakest link in each cycle. As shown in <figref idref="DRAWINGS">FIG. 10B</figref>, edges “E1” and “E2” are edges in the corresponding Bayesian network <b>164</b> corresponding to the inference graph <b>161</b> shown in <figref idref="DRAWINGS">FIG. 10A</figref>. In a first reasoner inference, factors are assigned their known probabilities resulting in a Bayes net <b>165</b> shown in <figref idref="DRAWINGS">FIG. 10C</figref>. For illustrative purposes, the factor “tremor” <b>168</b> is shown as having a probability as indicated by a thickness of the node border, In a second reasoner inference, beliefs are propagated through the graph resulting in Bayes net <b>167</b> shown in <figref idref="DRAWINGS">FIG. 10C</figref> with each node having an assigned probability based on the propagated beliefs. Then, as shown in <figref idref="DRAWINGS">FIG. 10E</figref>, the probabilities generated from Bayes network <b>167</b> are read back to populate the corresponding nodes in the original inference graph <b>161</b> of <figref idref="DRAWINGS">FIG. 10A</figref> now showing the reasoned probabilities by respective border thicknesses.

0170<figref idref="DRAWINGS">FIG. 10F</figref> shows that the inference graph <b>161</b> may be but one part of a complex network <b>160</b> of interconnected nodes and edges.

0171In <figref idref="DRAWINGS">FIGS. 10C-10F</figref>, for illustrative purposes, the thickness of a border <b>168</b> of a node is used to indicate how probable that event is. Likewise, the thickness of an edge <b>169</b> represents the strength of the strongest message that is passed along that edge. For example, a thicker node border <b>168</b> of candidate node <b>162</b> as compared to border <b>168</b> of candidate node <b>163</b> indicates a more probable candidate. In <figref idref="DRAWINGS">FIG. 10D</figref>, nodes <b>106</b><i>a</i>, <b>106</b><i>b</i>, <b>106</b><i>c </i>represent factors (events whose probability is known) while nodes <b>162</b>, <b>163</b>, and nodes <b>164</b> represent candidate answers, or nodes, i.e., answers which play a role in answering the question. Other nodes of the graph are also shown.

0172Although not shown in the visualization <b>160</b> in <figref idref="DRAWINGS">FIG. 10E</figref> of the medical domain example, probabilities underlying graph nodes are numbers of values between 0 and 1 representing the event probability and message strength. For this there is further displayed an answer probabilities table <b>199</b> representing the outputs of the updated graph. From the reasoner component's <b>160</b> perspective, they are the probabilities of each answer after the graph has been assimilated and propagated, normalized so that they sum to one. These outputs <b>199</b> represent the output of the text-based inference chaining system for the medical domain example with the indicating the better candidate answers.

0173Thus, text-based inference chaining system <b>100</b>, <b>100</b>′, <b>100</b>″ of <figref idref="DRAWINGS">FIGS. 4-6</figref>, provides an inference graph generator system and method for producing inference graphs over unstructured content to answer inquiries using a probabilistic QA system for discovering relations. Further, as will be described with respect to <figref idref="DRAWINGS">FIG. 12</figref> below, the text-based inference chaining system <b>100</b>, <b>100</b>′, <b>100</b>″ of <figref idref="DRAWINGS">FIGS. 4-6</figref>, or the various combinations thereof, may be programmed to employ a bi-directional graph generation inquiry solution strategy.

0174As shown in <figref idref="DRAWINGS">FIG. 12</figref>, a system and method may produce inference graphs by independently, and optionally in parallel (simultaneously), performing forward inference from factors extracted from the inquiry and backward inference from hypothetical answers produces by a hypotheses, or candidate answer, generator.

0175<figref idref="DRAWINGS">FIG. 12</figref> shows a text-based inference chaining system and method employing a bi-directional graph generation inquiry solution strategy. From the initial input inquiry <b>101</b>, the chaining system <b>100</b> performs factor-directed processes <b>400</b> that generate a final forward inference graph <b>110</b>FF. Either in parallel or concurrent in time, the chaining system <b>100</b> performs hypothesis-directed processes <b>500</b> that generate a final backward inference graph <b>110</b>FB having possible solutions indicated inference graph as end-point nodes <b>514</b>. That is, in one embodiment, to better manage graph generation from the factors and reduce the time it takes to find paths to possible solutions, the process includes generating a forward-directed graph from the factors and backward-directed graph from candidate answers <b>515</b> looking for a bridge, i.e., a meeting point, where a relation can be found joining end-points of each graph, and then joining the graphs. A programmed inference graph joiner component <b>600</b> looks for a bridge that joins the graphs, producing final inference graph <b>610</b>.

0176<figref idref="DRAWINGS">FIG. 13</figref> illustrates the factor-directed or forward-directed inference graph generation iterative process <b>400</b> which functions as programmed text-based inference chaining system <b>100</b>, <b>100</b>′, <b>100</b>″ of <figref idref="DRAWINGS">FIGS. 4-6</figref>, or combinations thereof. In this embodiment, an initial or original forward inference graph <b>110</b>IF is constructed that includes factors <b>406</b> extracted from an initial input inquiry <b>101</b> as initial nodes of the initial inference graph <b>110</b>IF. At each iteration, the previous forward inference graph is labeled <b>110</b>PF (or, in a first iteration of processing, the initial forward inference graph is <b>110</b>IF), and, at each iteration, an extended forward inference graph <b>110</b>EF is generated by graph extender <b>118</b>; and an updated forward inference graph <b>110</b>UF is generated with nodes having confidence values by the reasoned component <b>150</b>. The depth controller component <b>175</b> will halt the iteration and output the updated inference graph <b>110</b>UF as the final forward inference graph <b>110</b>FF at a specified depth or when at least one discovered relation accumulates confidence over a given threshold. Otherwise, the updated inference graph <b>110</b>UF becomes the current inference graph as a new input to the question generation component <b>112</b> and the cycle <b>99</b> iterates. The final forward inference graph <b>110</b>FF includes the factors identified from the inquiry and new nodes that were inferred from those factors with confidence values. For the medical domain example, from factor identification processing and after forward directed graph generation, the final inference graph may include the following example inferred nodes with confidence values: <ul id="ul0019" list-style="none"><li id="ul0019-0001" num="0000"><ul id="ul0020" list-style="none"><li id="ul0020-0001" num="0177">Patient has Parkinson's Disease: 0.8</li><li id="ul0020-0002" num="0178">Patient has Dystonia: 0.15</li><li id="ul0020-0003" num="0179">Patient has Athetosis: 0.03</li></ul></li></ul>

0180<figref idref="DRAWINGS">FIG. 14</figref> illustrates the hypothesis-directed inference graph generation iterative process <b>500</b> which functions similarly as programmed text-based inference chaining systems <b>100</b>, <b>100</b>′, <b>100</b>″ of <figref idref="DRAWINGS">FIGS. 4-6</figref>, or combinations thereof, however, implements a candidate answer generator <b>504</b> to produce the initial nodes in constructing the backward inference graph <b>110</b>IB. In this embodiment, an initial backward inference graph is labeled <b>110</b>IB, a current backward inference graph is <b>110</b>PB, and the extended backward inference graph <b>110</b>EB are generated by graph extender <b>118</b>, and a new revised inference graph <b>110</b>UB (after a first iteration of processing, for example) is generated by the reasoner component <b>150</b>. In this embodiment of process <b>500</b>, the candidate answer generator <b>504</b> performs programmed processes to receive and analyze the input inquiry <b>101</b>. The candidate answer generator <b>125</b> uses different techniques to produce many possible (candidate) answers or solutions that represent different “hypotheses” each of which become initial nodes <b>506</b> in a backwards inference graph <b>110</b>IB, and each of which, the system may be connected to some subset of factors in the final output bi-directional inference graph. Further, the depth controller <b>175</b> will halt the iteration and output the new inference graph as the final backward graph <b>110</b>FB at a specified depth. Otherwise the new inference graph, e.g., graph <b>110</b>UB, becomes the new input to the question generation component <b>112</b> and the cycle <b>99</b> iterates.

0181In backward-directed graph generation, processes are implemented to access a candidate answer generator <b>504</b> that receives the inquiry and conducts a search using known methods to produce possible answers (e.g., parts of the nervous system) based on the inquiry. For the above-described medical domain example (See <figref idref="DRAWINGS">FIG. 10D</figref>), example candidate answers generated may include: (1) Substantia nigra, (2) Caudate nucleus, (3) Lenticular nuclei, (4) Cerebellum and (5) Pons.

0182In backward-directed graph generation, components of the text-based chaining system <b>100</b>, <b>100</b>′, <b>100</b>″ of <figref idref="DRAWINGS">FIGS. 4-6</figref>, or combinations thereof, extend this graph. In particular question generation component <b>112</b> generates natural language questions suitable for input to the PQA system, such as: <ul id="ul0021" list-style="none"><li id="ul0021-0001" num="0000"><ul id="ul0022" list-style="none"><li id="ul0022-0001" num="0183">What causes Substnatia Nigra to be affected?</li><li id="ul0022-0002" num="0184">What causes Caudate nucleus to be affected?</li></ul></li></ul>

0185The PQA system component <b>115</b> is invoked to produce answers to these questions. For example, Parkinson's Disease causes Substantia Nigra to be affected. The graph extender component <b>118</b> adds these as edges to the backward-directed graph. Multiple Iterations may be performed to form longer paths in the inference graph.

0186In one embodiment, the candidate answer generator may be implemented using the same methods used in IBM's DeepQA system for candidate answer generation such as described below with respect to <figref idref="DRAWINGS">FIG. 19</figref>. Generally, candidate answer generation implements processes that break the input query into query terms, the query terms having searchable components. Then, a search engine built into or accessed by the QA system performs conducting a first search of the content using one of more of the searchable components to obtain documents including candidate answers. The documents may be analyzed to generate a set of candidate answers. Then, a further search may be conducted in the content using the candidate answers and the searchable components of the query terms to obtain one or more supporting passages, the supporting passages having at least one of said candidate answers and at least one of said searchable components of the query terms. A confidence level of these candidate answers may be determined using a scoring technique as known in the art for scoring the supporting passages.

0187<figref idref="DRAWINGS">FIG. 15</figref> illustrates the implementation of an inference graph joiner process <b>600</b> to merge nodes or join respective forward- and backward-directed graphs obtained by programmed inference chaining engines as described in <figref idref="DRAWINGS">FIG. 13</figref> and <figref idref="DRAWINGS">FIG. 14</figref>. In this embodiment, like elements in <figref idref="DRAWINGS">FIG. 15</figref> function identically as the inference chaining system and various embodiments described herein with respect to <figref idref="DRAWINGS">FIGS. 4-6</figref>, <b>13</b>, <b>14</b>, to provide a system and method for producing a single integrated output inference graph through a parallel (i.e., simultaneous) bi-directional graph generation running forward or factor-directed graph generation, and backward or hypothesis-directed inference graph generation processes. The method uses a depth controller to limit the generation of both paths if the nodes do not meet and an inference graph joiner process <b>600</b> to force the discovery of relations that may join the answers to factors in the inquiry. Inference graph joiner process <b>600</b> is implemented by a computer system that receives as an input both the nodes and relations data representing the final forward inference graph <b>110</b>FF and the final backward graph <b>110</b>FB.

0188The inference graph joiner process <b>600</b> joins two paths from factors through intermediate nodes to possible answers, and specifically in connecting forward generated inferences graphs with backward generated inference graphs. A first and optional step in graph joining is node merging at node merging element <b>665</b>. Node merger <b>665</b> implements programmed processes to analyze different concepts end-points within bi-directionally generated graphs and probabilistically determine if they refer to the same logical statements (concepts).

0189If any two different nodes in the graph are probabilistically determined with enough certainty that they do refer to the same concept, then they are merged into a single node reducing the number of paths in the graph. Node merging may further automatically connect/join two graphs (bi-directionally generated or not). This happens when the nodes that merged were from distinct graphs that the system was trying to join. The implicit question being answered by the node merger is “Do these two nodes refer to the same logical statement?” Thus, no explicit question is required to be asked to the PQA system to join the nodes as how it is done by the node joiner. If it is probabilistically determined that they do refer to the same concepts with enough certainty then they are merged into a single node reducing the number of extraneous or noisy paths in the graph that would dilute the confidence propagation. This may be performed using any number of term matching or co-reference techniques that look at syntactic, semantic or contextual similarity using techniques as known in the art. The MetaMap program referred to herein above is one example system that may be implemented in the medical domain. Given two terms, MetaMap may be used to determine if they refer to the same medical concept. In general, any “domain dictionary” that identifies synonymous terms for a given domain can be used in this way. As other medical domain examples, Diabetes may be merged with Diabetes Mellitus or Cold with Cold Virus or High Blood Pressure with Hypertension. Node joining performance will improve if it connects the merged node into another graph rather than connect them separately.

0190After invoking optional node merger <b>665</b>, node joiner element <b>675</b> implements programmed processes to detect relation end-points that are not on a path connecting a factor to an answer and attempt to discover a link between them (the factor and answer) using a part of the system.

0191Particularly, joiner process <b>675</b> receives both bi-directionally generated graphs and searches for two disconnected nodes (one from each graph) that may be connected by a relation. For example, one backward directed graph node is “Diabetes” and the other node is “Blindness”. The node joiner generates questions that may link two nodes. For example: <ul id="ul0023" list-style="none"><li id="ul0023-0001" num="0000"><ul id="ul0024" list-style="none"><li id="ul0024-0001" num="0192">Does Diabetes cause Blindness?</li></ul></li></ul>

0193As shown in <figref idref="DRAWINGS">FIG. 15</figref>, a determination is made as to whether the PQA system component <b>115</b> answers with sufficient confidence that a new relation is asserted connecting the nodes and a new path built. The graphs are then joined. In one embodiment, the node joiner may employ connecting all leaf nodes in the two graphs and then rank the paths based on the propagated confidences. It may select only some pairs of nodes based on their types.

0194With respect to inference graph joiner process <b>600</b> of <figref idref="DRAWINGS">FIG. 15</figref>, there are two cases to consider in any implementation: 1) the forward and backward inference graphs may naturally intersect; or 2) forward and backward inference graphs do not intersect.

0195For the medical domain example, it is the case that the forward-directed and backward-directed inference graphs naturally intersect. In this example, the forward-directed graph includes end-point “Parkinson's Disease” with high confidence, and the backward-directed graph includes the relation Parkinson's Disease causes Substantia Nigra to be affected, so when the graphs are combined there is a path leading from the initial factors to the candidate answer, and the iterative process terminates.

0196<figref idref="DRAWINGS">FIG. 16</figref> depicts an example node joiner process attempted to combine the bi-directionally generated inference graphs by looking for relations between end-point nodes <b>514</b> of the forward-directed graph, e.g., graph <b>110</b>FF and a node in the backward-directed graph, e.g., <b>110</b>FB. In one embodiment, this is performed by asking “yes”/“no” or multiple-choice questions to the PQA system component <b>115</b>. In one embodiment, <figref idref="DRAWINGS">FIG. 16</figref> shows a relation <b>516</b> produced by inference graph joiner process <b>600</b> that joins a node <b>524</b> of the final forward inference graph <b>110</b>FF and a node <b>526</b> of the final backward inference graph <b>110</b>FB. This relation <b>516</b> is shown thicker, e.g., as compared with the thickness of another discovered relation <b>517</b>, indicating the computing of a highest confidence level of the identified relation(s) and a corresponding justifying passage supporting joining the endpoint nodes <b>524</b> and <b>526</b> of the final inference graph. The node <b>526</b> is indicated with thicker border indicating a highest computed probability of a correct solution or answer, for example, as compared to end-point node <b>525</b> which may be joined as a result of finding another discovered relation <b>517</b> of weaker confidence level.

0197For the medical domain example described herein, programmed joiner process may provide example “Yes/No” questions that are generated by the question generation component for processing in the PQA system component <b>115</b>. Examples are shown below. <ul id="ul0025" list-style="none"><li id="ul0025-0001" num="0000"><ul id="ul0026" list-style="none"><li id="ul0026-0001" num="0198">Does Parkinson's Disease cause Substantia nigra to be affected?</li><li id="ul0026-0002" num="0199">Does Parkinson's Disease cause Caudate nucleus to be affected? . . . .</li></ul></li></ul>

0200For the medical domain example described herein, example multiple-choice questions that are generated for processing in the PQA system component <b>115</b> may include: <ul id="ul0027" list-style="none"><li id="ul0027-0001" num="0000"><ul id="ul0028" list-style="none"><li id="ul0028-0001" num="0201">Parkinson's Disease causes which of the following to be affected: (Substantia nigra, Caudate nucleus, Lenticular nuclei, Cerebellum, Pons)</li></ul></li></ul>

0202<figref idref="DRAWINGS">FIGS. 17A-17B</figref> illustrate one example of inference graph computation according to the embodiments described herein. From an input inquiry <b>601</b>: <ul id="ul0029" list-style="none"><li id="ul0029-0001" num="0000"><ul id="ul0030" list-style="none"><li id="ul0030-0001" num="0203">ON HEARING OF THE DISCOVERY OF GEORGE MALLORY'S BODY, THIS EXPLORER TOLD REPORTERS HE STILL THINKS HE WAS FIRST. <br /> and processing using one or more of the text analysis, factor identification and factor weighting components of the factor analysis component <b>200</b> of <figref idref="DRAWINGS">FIG. 8</figref> will obtain the following factors <b>606</b>A, <b>606</b>B as follows: </li><li id="ul0030-0002" num="0204"><b>606</b>A: GEORGE MALLORY from “DISCOVERY OF GEORGE MALLORY'S BODY”</li><li id="ul0030-0003" num="0205"><b>606</b>B: FIRST EXPLORER from THIS EXPLORER TOLD REPORTERS HE STILL THINKS HE WAS FIRST <br /> with emphasis indicating the initial nodes (factors) generated from the query. These will be simultaneously processed along parallel processing paths <b>605</b>A, <b>605</b>B, supported by the computing system described herein. In particular, using respective question generation components <b>612</b>A, <b>612</b>B. The question generation process <b>612</b>A, <b>612</b>B generates respective questions <b>613</b>A, <b>613</b>B. </li><li id="ul0030-0004" num="0206"><b>613</b>A: This is associated with George Mallory</li><li id="ul0030-0005" num="0207"><b>613</b>B: This is associated with First Explorer</li></ul></li></ul>

0208Via parallel implementations of the PQA systems <b>615</b>A, <b>615</b>B, the following justifying passages <b>620</b>A, <b>620</b>B are obtained from the searched (structured+unstructured) content. <ul id="ul0031" list-style="none"><li id="ul0031-0001" num="0000"><ul id="ul0032" list-style="none"><li id="ul0032-0001" num="0209"><b>620</b>A: George Herbert Leigh Mallory (18 Jun. 1886-8/9 Jun. 1924) was an English mountaineer who took part in the first three British expeditions to Mount Everest in the early 1920s.</li><li id="ul0032-0002" num="0210"><b>620</b>B: A mountaineering expert will today claim that Sir Edmund Hillary was not the first man to scale Everest—and that it was in fact conquered three decades before by the British climber George Mallory.</li><li id="ul0032-0003" num="0211"><b>620</b>C: Sir Edmund Hillary was a mountain climber and Antarctic explorer who, with the Tibetan mountaineer Tenzing Norgay, was the first to reach the summit of Mount Everest.</li></ul></li></ul>

0212Resulting from implementation of the reasoner component <b>150</b> processes for propagating confidences, the following candidate answers <b>622</b>A, <b>622</b>B are generated: <ul id="ul0033" list-style="none"><li id="ul0033-0001" num="0000"><ul id="ul0034" list-style="none"><li id="ul0034-0001" num="0213"><b>622</b>A: Mount Everest and</li><li id="ul0034-0002" num="0214"><b>622</b>B: Edmund Hillary</li></ul></li></ul>

0215The increased thickness of the border for answer Edmund Hillary <b>622</b>B indicates the relative increased confidence (score) associated with a higher confidence value as computed by the reasoner component <b>150</b> from which it is determinable as the best answer.

0216<figref idref="DRAWINGS">FIG. 17A</figref> further shows the resulting generated inference graph <b>610</b>A generated during a single iteration of parallel processing path <b>605</b>A having initial node (factor <b>606</b>A) associated or related with a candidate answer Mount Everest <b>622</b>A (as supported by justifying passage). Likewise, parallel processing path <b>605</b>B results in generating inference graph <b>610</b>B having initial node (factor <b>606</b>B) associated or related with Edmund Hillary as candidate answer <b>622</b>B having the highest computed confidence as indicated by thickest border.

0217<figref idref="DRAWINGS">FIGS. 17A</figref>, <b>17</b>B further show the node joiner process <b>675</b> which performs a join of the parallel formed inference graphs <b>610</b>A, <b>610</b>B. The inference graph join process first determines the generated candidate answers, and having determined them, determines whether these lead to a single correct answer.

0218The joining is being used to determine how confidence flows between two possible answers (e.g., Mt. Everest and Edmund Hillary) discovered from different factors in the question (as the factor Edmund Hillary was also a candidate answer from the first factor discovered from the annotating passage connected to that link).

0219In the method shown in <figref idref="DRAWINGS">FIG. 17A</figref>, generated candidate answers may be treated as factors from which a question may be generated for PQA processing. For example, by joining inference graphs <b>610</b>A, <b>610</b>B, the answers Mt. Everest and Sir Edmund Hillary become factors from which a question may be generated by question generator component <b>112</b> to ascertain their relation and the confidence strength of the association: an example question <b>672</b> is generated: <ul id="ul0035" list-style="none"><li id="ul0035-0001" num="0000"><ul id="ul0036" list-style="none"><li id="ul0036-0001" num="0220">Is Mount Everest associated with Edmund Hillary?</li></ul></li></ul>

0221Using processing by the PQA system component <b>115</b>, it is readily determined that there is an association between the answers Mt. Everest and Sir Edmund Hillary as indicated by the “yes” answer <b>678</b> in the joiner <b>675</b>. Thus, for example, the following justifying passage <b>620</b>D is obtained from the searched (structured+unstructured) content: <ul id="ul0037" list-style="none"><li id="ul0037-0001" num="0000"><ul id="ul0038" list-style="none"><li id="ul0038-0001" num="0222">On 29 May 1953, Hillary and Tenzing Norgay became the first climbers confirmed as having reached the summit of Mount Everest.</li></ul></li></ul>

0223Having established the relationship between answers Mt. Everest and Sir Edmund Hillary as indicated, the final inference graph of <figref idref="DRAWINGS">FIG. 17B</figref> will show a relation between the formed answers and a corresponding confidence as supported by the found justifying passage <b>620</b>D.

0224<figref idref="DRAWINGS">FIG. 18</figref> shows a further embodiment of the inference chaining system including a parallel implementation of PQA systems. <figref idref="DRAWINGS">FIG. 18</figref> includes a system and method for generating inference graphs for discovering and justifying answers to inquiries according to the embodiments described herein. A parallel PQA service <b>350</b> implementing in parallel probabilistic QA systems <b>355</b>A, <b>355</b>B, . . . , <b>355</b>N, allow for scalable and efficient execution of the generative process on a computer system. Thus, it is seen from <figref idref="DRAWINGS">FIG. 18</figref>, the output <b>317</b> of question generation component <b>112</b> is generated as plural queries (questions) each respective query serviced by a respective PQA system <b>355</b>A, <b>355</b>B, . . . , <b>355</b>N of the parallel array of PQA systems to provide for improved latency.

0225<figref idref="DRAWINGS">FIG. 19</figref> shows a system diagram depicting a high-level logical architecture and methodology of an embodiment of each PQA system <b>355</b>. As shown in <figref idref="DRAWINGS">FIG. 19</figref>, the architecture <b>355</b> includes a query analysis module <b>320</b> implementing functions for receiving and analyzing an input text query or question <b>319</b>. In an embodiment depicted, the question generation component of a text-based programmed inference chaining system as described herein, generates the query <b>319</b>, e.g., from factors. A candidate answer generation module <b>330</b> is provided to implement a search for candidate answers by traversing structured, semi structured and unstructured sources, e.g., content contained in a primary sources module <b>311</b> and/or in an answer source knowledge base module <b>321</b> containing, for example, collections of relations and lists extracted from primary sources. All the sources of information can be locally stored or distributed over a network, including a public network, e.g., Internet, or World-Wide-Web. The candidate answer generation module <b>330</b> generates a plurality of output data structures containing candidate answers based upon the analysis of retrieved data. In <figref idref="DRAWINGS">FIG. 19</figref>, one embodiment is depicted that includes an evidence gathering module <b>370</b> interfacing with the primary sources <b>311</b> and knowledge base <b>321</b> for concurrently analyzing the evidence based on passages having candidate answers, and scoring each of the candidate answers as parallel processing operations as described in commonly-owned, co-pending U.S. patent application Ser. Nos. 12/152,411 and 12/126,642, for example, the whole disclosures of each of which are incorporated by reference as if fully set forth herein.

0226In one embodiment, the architecture may be employed utilizing a common analysis system (CAS) candidate answer structures, and implementing supporting passage retrieval operations. For this processing, the evidence gathering module <b>370</b> implements supporting passage retrieval operations and the candidate answer scoring in separate processing modules for concurrently analyzing the passages and scoring each of the candidate answers as parallel processing operations. The knowledge base <b>321</b> includes content, e.g., one or more databases of structured or semi-structured sources (pre-computed or otherwise) and may include collections of relations (e.g., Typed Lists). In an example implementation, the answer source knowledge base may comprise a database stored in a memory storage system, e.g., a hard drive. An answer ranking module <b>360</b> provides functionality for ranking candidate answers, i.e., compute a confidence value, and determining a response <b>399</b> that is returned to the engine along with respective confidences for potentially extending the inference graph with nodes and relations. The response may be an answer, or an elaboration of a prior answer, or a request for clarification in response to a question—when a high quality answer to the question is not found.

0227In one embodiment, the system shown in <figref idref="DRAWINGS">FIG. 19</figref>, to employ one or more modules for enabling I/O communication between a user or computer system and the system <b>10</b> according to, but not limited to, the modalities of text, audio, video, gesture, tactile input and output etc. Thus, in one embodiment, both an input query and a generated query response may be provided in accordance with one or more of multiple modalities including text, audio, image, video, tactile or gesture.

0228<figref idref="DRAWINGS">FIG. 20</figref> illustrates an exemplary hardware configuration of a computing system <b>401</b> in which the present system and method may be employed. The hardware configuration preferably has at least one processor or central processing unit (CPU) <b>411</b>. The CPUs <b>411</b> are interconnected via a system bus <b>412</b> to a random access memory (RAM) <b>414</b>, read-only memory (ROM) <b>416</b>, input/output (I/O) adapter <b>418</b> (for connecting peripheral devices such as disk units <b>421</b> and tape drives <b>440</b> to the bus <b>412</b>), user interface adapter <b>422</b> (for connecting a keyboard <b>424</b>, mouse <b>426</b>, speaker <b>428</b>, microphone <b>432</b>, and/or other user interface device to the bus <b>412</b>), a communication adapter <b>434</b> for connecting the system <b>400</b> to a data processing network, the Internet, an Intranet, a local area network (LAN), etc., and a display adapter <b>436</b> for connecting the bus <b>412</b> to a display device <b>438</b> and/or printer <b>439</b> (e.g., a digital printer of the like).

0229As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon.

0230Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with a system, apparatus, or device running an instruction.

0231A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with a system, apparatus, or device running an instruction.

0232Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.

0233Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may run entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).

0234Thus, in one embodiment, the system and method for efficient passage retrieval may be performed with data structures native to various programming languages such as Java and C++.

0235Aspects of the present invention are described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which run via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.

0236The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which run on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

0237The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more operable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be run substantially concurrently, or the blocks may sometimes be run in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.

0238The embodiments described above are illustrative examples and it should not be construed that the present invention is limited to these particular embodiments. Thus, various changes and modifications may be effected by one skilled in the art without departing from the spirit or scope of the invention as defined in the appended claims.