System, method and computer program for facet analysis

• US 7,606,781 B2
• Filed: 10/18/2006
• Issued: 10/20/2009
• Est. Priority Date: 03/30/2005
• Status: Active Grant

• Current Assignee: Primal Fusion Inc.
• Original Assignee: Primal Fusion Inc.
• Inventors: Yao, Zhengrong, Sweeney, Peter
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US11/550,457
• Publication Number:
  US 20070136221A1
• Time in Patent Office: 1,098 Days
• Field of Search: 706/48
• US Class Current: 706/48
• CPC Class Codes: G06F 16/84 Mapping; Conversion
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

Automated facet analysis of input information selected from a domain of information in accordance with a source data structure is described. Facet analysis may proceed by discovering at least one of facets, facet attributes, and facet attribute hierarchies of the input information using pattern augmentation and statistical analyses to identify patterns of facet attribute relationships in the input information.

Claims

1. A computer implemented method for performing facet analysis of input information selected from a domain of information in accordance with a source data structure, the computer implemented method comprising:

accessing, or facilitating the accessing, by one or more computer processors, one or more pattern augmentations and one or more statistical analyses;

applying, or facilitating the application, by one or more computer processors, one or more of the pattern augmentations and one or more of the statistical analyses to the input information to identify patterns of facet attribute relationships; and

,

discovering, or facilitating the discover, by one or more computer processors, at least one of facets, facet attributes, and facet attribute hierarchies of the input information.

2. The computer implemented method of claim 1 comprising inferring the facet attribute relationships from concept definitions and concept relationships obtained from the input information thereby to build the facet attribute hierarchies, said concept definitions comprising attributes for defining said facets and facet attributes.

3. The computer implemented method of claim 2 comprising building the facet attribute hierarchy by adding facet attribute relationships incrementally.

4. The computer implemented method of claim 2 comprising determining potential facet attribute relationships from permutations of facet attribute relationships in concept definitions and concept relationships in the input information.

5. The computer implemented method of claim 4 comprising ordering the processing of the potential facet attribute relationships in accordance with a count of facet attributes in the concept definitions of a concept relationship pair.

6. The computer implemented method of claim 4 comprising aligning facet attribute relationships from the potential facet attribute relationships to reduce the number of potential facet attribute relationships to augment the patterns for statistical analyses.

7. The computer implemented method of claim 6 comprising aligning potential facet attribute relationships in accordance with at least one of:

(a) the presence of facet attributes shared across a pair of related concept definitions;

(b) the presence of the facet attribute relationship, directly or indirectly, in the facet attribute hierarchy; and

(c) an external lexicon.

8. The computer implemented method of claim 4 comprising, for each potential facet attribute relationship,

evaluating the likelihood that a respective potential facet attribute relationship holds true in the context of all concept relationships in which the respective potential facet attribute relationship presents;

and

making the respective potential facet attribute relationship a candidate facet attribute relationship for the facet attribute hierarchy in response to the evaluating.

9. The computer implemented method of claim 8 wherein said evaluating comprises determining a prevalence of the respective potential facet attribute relationship in the aggregate context of all concept relationships and wherein said making is responsive to said prevalence.

10. The computer implemented method of claim 8 wherein said evaluating comprises determining the presence of circular relationships among the potential facet attribute relationships and identifying respective potential facet attribute relationships that contradict the assumption of hierarchy and wherein said making is responsive to said identifying.

11. The computer implemented method of claim 8 comprising pruning one of the candidate facet attribute relationships if said one can be logically constructed using sets of other candidate facet attribute relationships.

12. The computer implemented method of claim 8 comprising assembling the candidate facet attribute relationships into a facet attribute polyhierarchy wherein that the set of candidate facet attribute relationships in the polyhierarchy is logically consistent in the aggregate.

13. The computer implemented method of claim 12 wherein said assembling uses the least number of polyhierarchical relationships necessary to create the logically consistent polyhierarchy.

14. The computer implemented method of claim 12 wherein said assembling orders a respective facet attribute in the polyhierarchy in response to a measure of a relative generality of each facet attribute.

15. The computer implemented method of claim 14 comprising determining a respective facet attribute'"'"'s generality using a generality of one or more concept definitions associated with the respective facet attribute.

16. The computer implemented method of claim 2 comprising defining the facet attribute hierarchy as a strict hierarchy by reconsidering the order of a facet attribute having multiple parents as an attribute of an ancestor of the multiple parents.

17. The computer implemented method of claim 16 comprising determining the facets from root nodes within the facet attribute hierarchy.

18. The computer implemented method of claim 2 comprising deriving from the input information the concept definitions and concept relationships wherein the concept definitions are defined in terms of attributes.

19. The computer implemented method of claim 18 comprising identifying structural markers in the input information and extracting attributes from the input information responsive to said structural markers.

20. The computer implemented method of claim 1 wherein the facet attributes are morphemes and the facet attribute relationships are morpheme relationships.

21. The computer implemented method of claim 20 comprising using the facets, facet attributes and facet attribute hierarchy to perform facet analysis on further input information selected from a second domain of information.

22. The computer implemented method of claim 1 comprising providing a faceted data set comprising the facets, facet attributes and facet attribute hierarchy.

23. The computer implemented method of claim 22 comprising providing the faceted data set for sharing among a plurality of domains with which to derive respective dimensional concept taxonomies for each domain.

24. The computer implemented method of claim 23 wherein the input information comprises one or more of information of any of the domains to be classified.

25. The computer implemented method of claim 22 comprising using the faceted data set for facet classification synthesis.

26. The computer implemented method of claim 1 comprising using a complex-adaptive system to enhance the pattern augmentation.

27. The computer implemented method of claim 26 wherein the complex-adaptive system feeds back further input information for reinforcing the facets, facet attributes and facet attribute hierarchies, said further input information derived from one or more of machine-based or user-based feedback loops.

28. A computer system for performing facet analysis of input information selected from a domain of information in accordance with a source data structure, comprising:

the computer system configured to discover, or facilitate the discovery of, by one or more computer processors, at least one of facets, facet attributes, and facet attribute hierarchies of the input information using pattern augmentation and statistical analyses to identify patterns of facet attribute relationships in the input information.

29. The computer system of claim 28 wherein instructions and data configure the computer system for inferring the facet attribute relationships from concept definitions and concept relationships obtained from the input information thereby to build the facet attribute hierarchies, said concept definitions comprising attributes for defining said facets and facet attributes.

30. The computer system of claim 29 wherein the instructions and data configure the computer system for building the facet attribute hierarchy by adding facet attribute relationships incrementally.

31. The computer system of claim 29 wherein the instructions and data configure the computer system for determining potential facet attribute relationships from permutations of facet attribute relationships in concept definitions and concept relationships in the input information.

32. The computer system of claim 31 wherein the instructions and data configure the computer system for ordering the processing of the potential facet attribute relationships in accordance with a count of facet attributes in the concept definitions of a concept relationship pair.

33. The computer system of claim 31 wherein the instructions and data configure the computer system for aligning facet attribute relationships from the potential facet attribute relationships to reduce the number of potential facet attribute relationships to augment the patterns for statistical analyses.

34. The computer system of claim 33 wherein the instructions and data configure the computer system for aligning potential facet attribute relationships in accordance with at least one of:

(a) the presence of facet attributes shared across a pair of related concept definitions;

(b) the presence of the facet attribute relationship, directly or indirectly, in the facet attribute hierarchy; and

(c) an external lexicon.

35. The computer system of claim 31 wherein the instructions and data configure the computer system for each potential facet attribute relationship,

evaluating the likelihood that a respective potential facet attribute relationship holds true in the context of all concept relationships in which the respective potential facet attribute relationship presents;

and

making the respective potential facet attribute relationship a candidate facet attribute relationship for the facet attribute hierarchy in response to the evaluating.

36. The computer system of claim 35 wherein said evaluating comprises determining a prevalence of the respective potential facet attribute relationship in the aggregate context of all concept relationships and wherein said making is responsive to said prevalence.

37. The computer system of claim 35 wherein said evaluating comprises determining the presence of circular relationships among the potential facet attribute relationships and identifying respective potential facet attribute relationships that contradict the assumption of hierarchy and wherein said making is responsive to said identifying.

38. The computer system of claim 35 wherein the instructions and data configure the computer system for pruning one of the candidate facet attribute relationships if said one can be logically constructed using sets of other candidate facet attribute relationships.

39. The computer system of claim 35 wherein the instructions and data configure the computer system for assembling the candidate facet attribute relationships into a facet attribute polyhierarchy wherein that the set of candidate facet attribute relationships in the polyhierarchy is logically consistent in the aggregate.

40. The computer system of claim 39 wherein said assembling uses the least number of polyhierarchical relationships necessary to create the logically consistent polyhierarchy.

41. The computer system of claim 39 wherein said assembling orders a respective facet attribute in the polyhierarchy in response to a measure of a relative generality of each facet attribute.

42. The computer system of claim 41 wherein the instructions and data configure the computer system for determining a respective facet attribute'"'"'s generality using a generality of one or more concept definitions associated with the respective facet attribute.

43. The computer system of claim 29 wherein the instructions and data configure the computer system for defining the facet attribute hierarchy as a strict hierarchy by reconsidering the order of a facet attribute having multiple parents as an attribute of an ancestor of the multiple parents.

44. The computer system of claim 43 wherein the instructions and data configure the computer system for determining the facets from root nodes within the facet attribute hierarchy.

45. The computer system of claim 29 wherein the instructions and data configure the computer system for deriving from the input information the concept definitions and concept relationships wherein the concept definitions are defined in terms of attributes.

46. The computer system of claim 45 wherein the instructions and data configure the computer system for identifying structural markers in the input information and extracting attributes from the input information responsive to said structural markers.

47. The computer system of claim 28 wherein the facet attributes are morphemes and the facet attribute relationships are morpheme relationships.

48. The computer system of claim 47 wherein the instructions and data configure the computer system for using the facets, facet attributes and facet attribute hierarchy to perform facet analysis on further input information selected from a second domain of information.

49. The computer system of claim 28 wherein the instructions and data configure the computer system for providing a faceted data set comprising the facets, facet attributes and facet attribute hierarchy.

50. The computer system of claim 49 wherein the instructions and data configure the computer system for providing the faceted data set for sharing among a plurality of domains with which to derive respective dimensional concept taxonomies for each domain.

51. The computer system of claim 50 wherein the input information comprises one or more of information of any of the domains to be classified.

52. The computer system of claim 49 wherein the instructions and data configure the computer system for using the faceted data set for facet classification synthesis.

53. The computer system of claim 28 wherein the instructions and data configure the computer system for using a complex-adaptive system to enhance the pattern augmentation.

54. The computer system of claim 53 wherein the complex-adaptive system feeds back further input information for reinforcing the facets, facet attributes and facet attribute hierarchies, said further input information derived from one or more of machine-based or user-based feedback loops.

55. A computer program product storing instructions and data to configure a computer system for performing facet analysis of input information selected from a domain of information in accordance with a source data structure, the computer program product comprising:

said instructions and data for configuring one or more computer processors to apply, or facilitate the application of, pattern augmentation and statistical analyses to the input information to identify patterns of facet attribute relationships in the input information and for configuring one or more processors to discover, or facilitate the discovery of, at least one of facets, facet attributes, and facet attribute hierarchies of the input information.

56. The computer program product of claim 55 wherein the instructions and data configure the computer system for inferring the facet attribute relationships from concept definitions and concept relationships obtained from the input information thereby to build the facet attribute hierarchies, said concept definitions comprising attributes for defining said facets and facet attributes.

57. The computer program product of claim 56 wherein the instructions and data configure the computer system for building the facet attribute hierarchy by adding facet attribute relationships incrementally.

58. The computer program product of claim 56 wherein the instructions and data configure the computer system for determining potential facet attribute relationships from permutations of facet attribute relationships in concept definitions and concept relationships in the input information.

59. The computer program product of claim 58 wherein the instructions and data configure the computer system for ordering the processing of the potential facet attribute relationships in accordance with a count of facet attributes in the concept definitions of a concept relationship pair.

60. The computer program product of claim 58 wherein the instructions and data configure the computer system for aligning facet attribute relationships from the potential facet attribute relationships to reduce the number of potential facet attribute relationships to augment the patterns for statistical analyses.

61. The computer program product of claim 60 wherein the instructions and data configure the computer system for aligning potential facet attribute relationships in accordance with at least one of:

(a) the presence of facet attributes shared across a pair of related concept definitions;

(b) the presence of the facet attribute relationship, directly or indirectly, in the facet attribute hierarchy; and

(c) an external lexicon.

62. The computer program product of claim 58 wherein the instructions and data configure the computer system for, for each potential facet attribute relationship,

evaluating the likelihood that a respective potential facet attribute relationship holds true in the context of all concept relationships in which the respective potential facet attribute relationship presents;

and

making the respective potential facet attribute relationship a candidate facet attribute relationship for the facet attribute hierarchy in response to the evaluating.

63. The computer program product of claim 62 wherein said evaluating comprises determining a prevalence of the respective potential facet attribute relationship in the aggregate context of all concept relationships and wherein said making is responsive to said prevalence.

64. The computer program product of claim 62 wherein said evaluating comprises determining the presence of circular relationships among the potential facet attribute relationships and identifying respective potential facet attribute relationships that contradict the assumption of hierarchy and wherein said making is responsive to said identifying.

65. The computer program product of claim 62 wherein the instructions and data configure the computer system for pruning one of the candidate facet attribute relationships if said one can be logically constructed using sets of other candidate facet attribute relationships.

66. The computer program product of claim 62 wherein the instructions and data configure the computer system for assembling the candidate facet attribute relationships into a facet attribute polyhierarchy wherein that the set of candidate facet attribute relationships in the polyhierarchy is logically consistent in the aggregate.

67. The computer program product of claim 66 wherein said assembling uses the least number of polyhierarchical relationships necessary to create the logically consistent polyhierarchy.

68. The computer program product of claim 66 wherein said assembling orders a respective facet attribute in the polyhierarchy in response to a measure of a relative generality of each facet attribute.

69. The computer program product of claim 68 wherein the instructions and data configure the computer system for determining a respective facet attribute'"'"'s generality using a generality of one or more concept definitions associated with the respective facet attribute.

70. The computer program product of claim 56 wherein the instructions and data configure the computer system for defining the facet attribute hierarchy as a strict hierarchy by reconsidering the order of a facet attribute having multiple parents as an attribute of an ancestor of the multiple parents.

71. The computer program product of claim 70 wherein the instructions and data configure the computer system for determining the facets from root nodes within the facet attribute hierarchy.

72. The computer program product of claim 56 wherein the instructions and data configure the computer system for deriving from the input information the concept definitions and concept relationships wherein the concept definitions are defined in terms of attributes.

73. The computer program product of claim 72 wherein the instructions and data configure the computer system for identifying structural markers in the input information and extracting attributes from the input information responsive to said structural markers.

74. The computer program product of claim 55 wherein the facet attributes are morphemes and the facet attribute relationships are morpheme relationships.

75. The computer program product of claim 74 wherein the instructions and data configure the computer system for using the facets, facet attributes and facet attribute hierarchy to perform facet analysis on further input information selected from a second domain of information.

76. The computer program product of claim 55 wherein the instructions and data configure the computer system for providing a faceted data set comprising the facets, facet attributes and facet attribute hierarchy.

77. The computer program product of claim 76 wherein the instructions and data configure the computer system for providing the faceted data set for sharing among a plurality of domains with which to derive respective dimensional concept taxonomies for each domain.

78. The computer program product of claim 77 wherein the input information comprises one or more of information of any of the domains to be classified.

79. The computer program product of claim 76 wherein the instructions and data configure the computer system for using the faceted data set for facet classification synthesis.

80. The computer program product of claim 55 wherein the instructions and data configure the computer system for using a complex-adaptive system to enhance the pattern augmentation.

81. The computer program product of claim 80 wherein the complex-adaptive system feeds back further input information for reinforcing the facets, facet attributes and facet attribute hierarchies, said further input information derived from one or more of machine-based or user-based feedback loops.