Identifying conceptual gaps in a knowledge base

• US 7,555,472 B2
• Filed: 09/02/2005
• Issued: 06/30/2009
• Est. Priority Date: 09/02/2005
• Status: Active Grant

• Current Assignee: Board of Trustees of The University of Illinois
• Original Assignee: Board of Trustees of The University of Illinois
• Inventors: Craig, Alan, Leetaru, Kalev
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US11/218,667
• Publication Number:
  US 20070094210A1
• Time in Patent Office: 1,397 Days
• Field of Search: None
• US Class Current: 706/50
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

A method and system for augmenting a corpus with documents on concepts not sufficiently covered within the corpus is provided. The augmentation system generates a corpus concept graph from the documents of a corpus. A corpus concept graph represents concepts of the documents as nodes and related concepts as links between nodes. To generate a corpus concept graph, the augmentation system identifies the concepts that are related within each document of the corpus and adds nodes and links to the corpus concept graph for related concepts. The augmentation system analyzes the corpus concept graph to determine whether the relatedness of concepts of the documents of the corpus is sufficient. If the relatedness of a pair of concepts is not sufficient, then the augmentation system attempts to identify documents not already in the corpus that are related to the concepts that are not sufficiently related.

Claims

1. A method in a computing system with a processor for augmenting a corpus of documents, the method comprising:

generating a corpus concept graph from the documents indicating connections between concepts of the documents of the corpus;

analyzing the corpus concept graph to determine whether connectedness of concepts of the documents of the corpus is sufficient; and

when the analysis indicates that the connectedness of some concepts is not sufficient, adding to the corpus documents relating to the concepts that do not have sufficient connectedness

wherein the generating, analyzing, and adding are performed by the processor.

2. The method of claim 1 wherein the generating of a corpus concept graph includes generating document concept graphs for the documents of the corpus indicating connections between concepts within a document and wherein the corpus concept graph is created from the document concept graphs.

3. The method of claim 2 wherein the generating of a document concept graph includes identifying concepts of the document and indicating strength of the connections between the concepts of the document.

4. The method of claim 3 wherein the identifying of concepts of a document includes identifying keywords of the documents.

5. The method of claim 3 wherein the connection strength of concepts is based on the distance between locations of the concepts within the document.

6. The method of claim 1 wherein the generating of the corpus concept graph includes adding to the corpus concept graph connections between concepts when the connection strength of concepts of the documents satisfies a document connection strength threshold.

7. The method of claim 1 wherein the analyzing of the corpus concept graph includes determining the conceptual distance between concepts of the corpus concept graph.

8. The method of claim 7 wherein the conceptual distance between concepts is based on the number of concepts between the concepts.

9. The method of claim 7 wherein the connectedness of concepts is not sufficient when the conceptual distance between the concepts does not satisfy a conceptual distance threshold.

10. The method of claim 1 wherein the adding to the corpus documents relating to the concepts that do not have sufficient connectedness includes generating queries based on the concepts, identifying documents that satisfy the queries, and adding an identified document to the corpus that would improve connectedness of the concepts.

11. The method of claim 1 wherein the analyzing of the corpus concept graph to determine whether connectedness of concepts of the documents of the corpus is sufficient is based only on conceptual distance and further includes analyzing the corpus concept graph to identify concepts whose connectedness, based on both conceptual distance and connection strength, does not satisfy a corpus connectedness threshold;

and when the analysis indicates that the connectedness of some concepts does not satisfy the corpus connectedness threshold, adding to the corpus documents relating to the concepts that do not satisfy the corpus connectedness threshold.

12. The method of claim 1 wherein the connectedness is based only on conceptual distance and after adding to the corpus documents relating to the concepts that do not have sufficient conceptual distance, adding to the corpus documents relating to concepts that do not have sufficient connectedness based on both conceptual distance and connection strength.

13. A method in a computing device with a processor for identifying gaps in a knowledge base, the method comprising:

generating a concept graph representing concepts of the knowledge base that connects concepts that are related as indicated by the knowledge base;

analyzing the concept graph to determine whether connectedness between the concepts of the knowledge base is sufficient; and

indicating the concepts whose connectedness in the knowledge base is not sufficient

wherein the generating, analyzing, and indicating are performed by the processor.

14. The method of claim 13 wherein the knowledge base is generated from a person.

15. The method of claim 14 wherein the knowledge base is a document created by the person.

16. The method of claim 14 wherein the knowledge base is generated by the person answering questions.

17. The method of claim 14 wherein the indicating includes identifying documents relating to the concepts whose connectedness in the knowledge base is not sufficient and suggesting that the person read the identified documents.

18. The method of claim 13 wherein the knowledge base is a corpus of documents.

19. The method of claim 18 wherein the concept graph is generated from document concept graphs.

20. The method of claim 19 wherein the concept graph includes concepts of the document concept graphs with connections of the document concept graphs that satisfy a connection strength threshold.

21. The method of claim 20 wherein the connectedness is based only on the conceptual distance between concepts.

22. The method of claim 20 wherein the connectedness is based on both the conceptual distance and connection strength of concepts.

23. A method in a computing system with a processor for determining connectedness of concepts within a corpus of documents, the method comprising:

generating document concept graphs for the documents of the corpus indicating connections and strength of connections between concepts within a document; and

generating a corpus concept graph from the document concept graphs indicating connections and an aggregate strength of connections between concepts of the documents of the corpus

wherein the connectedness of the concepts of the corpus is based on the aggregate strength of connections between concepts and wherein the generating of the document concept graphs and the corpus concept graph are performed by the processor.

24. The method of claim 23 wherein the connectedness is further based on the conceptual distance between concepts of the corpus.

25. The method of claim 23 wherein the documents represent a knowledge base derived from one person.

26. The method of claim 23 wherein when the connectedness of concepts does not satisfy a connectedness threshold, indicating a gap in the connectedness of the concepts of the corpus.

27. A method in a computing system with a processor for generating a query, the method comprising:

providing a corpus concept graph indicating connections and strength of connections between concepts represented by the corpus concept graph;

receiving a query having an input concept;

identifying from the corpus concept graph a concept that is related to the input concept based on the connections and strength of the connections; and

augmenting the query with the identified concept

wherein the providing, receiving, identifying, and augmenting are performed by the processor.

28. The method of claim 27 including submitting the augmented query to a search engine to identify items related to the received query.

29. The method of claim 27 wherein the identifying of a concept is also based on the conceptual distance of the concept from the input concept.

30. The method of claim 27 wherein the corpus concept graph is generated from document concept graphs of documents of the corpus.

31. A computing device with a processor and memory for augmenting a corpus of documents, comprising:

a corpus store containing the corpus of documents;

a component having computer-executable instructions that generate a corpus concept graph from the documents of the corpus, the corpus concept graph indicating connections between concepts of the documents of the corpus;

a component having computer-executable instructions that determine whether connectedness of concepts of the documents of the corpus is sufficient based on analysis of the connections between concepts of the documents of the corpus as indicated by the corpus concept graph; and

a component having computer-executable instructions that, when it is determined that the connectedness of some concepts is not sufficient, adds to the corpus documents relating to the concepts that do not have sufficient connectedness

wherein the computer-executable instructions of the component are stored in the memory for execution by the processor.

32. The computing device of claim 31 wherein the instructions that generate a corpus concept graph include instructions that generate document concept graphs for the documents of the corpus indicating connections between concepts within a document by identifying concepts of the document and indicating strength of the connections between the concepts of the document and wherein the corpus concept graph is created from the document concept graphs.

33. The computing device of claim 32 wherein the connection strength of concepts is based on the distance between locations of the concepts within the document.

34. The computing device of claim 32 wherein the instructions that add to the corpus documents relating to the concepts that do not have sufficient connectedness include instructions that generate queries based on the concepts, identify documents that satisfy the queries, and add an identified document to the corpus that would improve connectedness of the concepts.

35. A computer-readable storage medium containing computer-executable instructions for identifying gaps in a knowledge base, by a method comprising:

generating a concept graph representing concepts of the knowledge base that connects concepts that are related as indicated by the knowledge base;

determining whether connectedness between the concepts of the knowledge base is sufficient to adequately represent the concepts of the knowledge base; and

indicating the concepts whose connectedness in the knowledge base is not sufficient and thereby identifying gaps in the knowledge base

wherein the instructions are executable by a processor of a computer.

36. The computer-readable storage medium of claim 35 wherein the indicating includes identifying documents relating to the concepts whose connectedness in the knowledge base is not sufficient and suggesting that the person read the identified documents.

37. The computer-readable storage medium of claim 35 wherein the knowledge base is a corpus of documents, the concept graph is generated from document concept graphs and includes concepts of the document concept graphs with connections of the document concept graphs that satisfy a connection strength threshold, and the connectedness is based on the conceptual distance and connection strength of concepts.