Learning based on feedback for contextual personalized information retrieval

• US 7,827,125 B1
• Filed: 06/01/2007
• Issued: 11/02/2010
• Est. Priority Date: 06/01/2006
• Status: Active Grant

• Current Assignee: Monster Worldwide Incorporated (Randstad NV)
• Original Assignee: Trovix, Inc. (Randstad NV)
• Inventors: Rennison, Earl
• Primary Examiner(s): Holmes; Michael B.
• Assistant Examiner(s): Kim; David H
• Application Number:
  US11/757,088
• Time in Patent Office: 1,250 Days
• Field of Search: 707/600, 707/601, 707/602, 707/603, 707/734, 707/722, 707/733, 707/794, 706/14
• US Class Current: 706/14
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3332 Query translation
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/3335 Syntactic pre-processing, e.g. stopword elimination, stemming
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/906 Clustering; Classification
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Information retrieval systems face challenging problems with delivering highly relevant and highly inclusive search results in response to a user'"'"'s query. Contextual personalized information retrieval uses a set of integrated methodologies that can combine automatic concept extraction/matching from text, a powerful fuzzy search engine, and a collaborative user preference learning engine to provide accurate and personalized search results. The system can include constructing a search query to execute a search of a database parsing an input query from a user conducting the search of the database into sub-strings, and matching the sub-strings to concepts in a semantic concept network of a knowledge base. The system can further map the matched concepts to criteria and criteria values that specify a set of constraints on and scoring parameters for the matched concepts. Furthermore, the system can learn user preferences to construct one or more profiles for producing personalized search results.

Claims

1. A method for learning user preferences in a search of knowledge base to construct one or more profiles for producing personalized search results, the method comprising:

receiving feedback from the user regarding quality of search results presented to the user in a search of a knowledge base that is a semantic network of relationships among concepts and that provides an index of a plurality of documents, the feedback representing how well the search results match an input query provided by the user, the search results including one or more of the documents indexed by the knowledge base;

constructing the one or more profiles for the user, based on the feedback received, by determining an implicit feedback value, an explicit feedback value, and a negative feedback value for the search results for which feedback is received, wherein, for concepts associated with search criteria applied to retrieve the search results, feedback is received to create a source concept that is compared against a reference concept to form a set of source concept values and a set of reference concept values, and wherein the search results that receive feedback values are used to construct a model that includes profile weights computed from the feedback values by;

applying the implicit feedback value to the values in the set of source concept values but not in the set of reference concept values;

applying the explicit feedback value to the values in both the set of source concept values and the set of reference concept values; and

applying the negative feedback value to the values in the set of reference concept values but not in the set of source concept values;

modifying internal weights used for scoring search criteria applied in producing the search results presented to the user, the modifications made based on the profile weights in the constructed model;

generating implicit search criteria for the user based on the one or more profiles; and

applying the implicit search criteria and modified weights during a subsequent search of the knowledge base conducted by the user producing a subsequent set of search results that are personalized to the user.

2. The method of claim 1, wherein the input query is selected from a group consisting of:

a query for job descriptions and a query for resumes for job candidates.

3. The method of claim 1, wherein the user provides ratings for the search results presented using a system selected from the group consisting of:

a point system;

a five star rating system, a slider icon, and any combination of these.

4. The method of claim 1, wherein the feedback is implicit feedback.

5. The method of claim 1, wherein the input query is selected from a group consisting of:

an input string of text and a document.

6. The method of claim 1, further comprising:

learning user profiles and search profiles;

applying these to the search to modify ranking of the search results.

7. The method of claim 1, wherein at least one of the one or more profiles is a user profile that pertains to the user'"'"'s general preferences that are not specifically associated with a search, and wherein at least one of the one or more profiles is a search profile that pertains to a particular query or query type not specifically associated with the user.

8. The method of claim 7, further comprising combining the user profile and the search profile to create a biased profile, wherein weights in the search profile are biased by weights in the user profile using a biasing function.

9. The method of claim 8, wherein the biasing function is selected from a group consisting of:

a mean, a geometric mean, a generalized mean, a trimmed mean, a winsorized mean, and a median.

10. The method of claim 1, wherein the one or more profiles are arranged hierarchically to include parent profiles and child profiles, and the child profiles inherit profile weights from the parent profiles where profile values are not defined in the child profile.

11. The method of claim 1, wherein constructing the one or more profiles further comprises determining a feedback value tuple for each search result, the feedback value tuple including the implicit feedback value, the explicit feedback value, and the negative feedback value determined, each having a value between −

1.0 and 1.0.

12. The method of claim 1, wherein the profile weights are computed by a weight function selected from a group consisting of:

geometric mean;

weighted geometric mean, weighted average, and average.

13. The method of claim 1, wherein modifying the internal weights used for scoring search criteria further comprises redefining the internal weights to be a function of the internal weights used for scoring search criteria and the profiled weights.

14. The method of claim 13, wherein the function is selected from a group consisting of:

log frequency, log inverse frequency, linear frequency, fuzzy frequency, fuzzy inverse frequency, and any combination of these.

15. The method of claim 1, further comprising removing oldest feedback information when a forgetting rate threshold is reached.

16. The method of claim 1, further comprising defining simple profiled score criteria that are based on a single attribute or attribute path, and defining compound profiled score criteria that are based on a set of profiled score criteria, wherein the simple profiled score criteria are instantiated as simple profiled score criteria values and the compound profiled score criteria are instantiated as compound profiled score criteria values, the simple profiled score criteria values and the compound profiled score criteria values each being composed of sub-profiled score criteria.

17. The method of claim 16, wherein the simple profiled score criteria values and the compound profiled score criteria values can be defined by a tuple of values selected from a group consisting of:

a weight range, a weight, a requirement that can be required or desired, and any combination of these.

18. The method of claim 17, wherein the simple profiled score criteria values can use an attribute path from a target concept to select a set of values to evaluate, which is an evaluation set, and wherein the weight of the simple profiled score criteria value is a function of a total number of values in the evaluation set and a number of values in the evaluation set for which profile weights are described.

19. The method of claim 17, wherein the weight for the simple profiled score criteria value is computed using weight functions selected from a group consisting of:

log frequency and log inverse frequency.

20. The method of claim 17, wherein the weight of the compound profiled score criteria values is computed using weight functions selected from a group consisting of:

a geometric mean and a mean of the weights of the sub-profiled score criteria.

21. The method of claim 16, wherein a partial score of the simple profiled score criteria value is computed using a similarity measure between a first vector including active profile weights and a second vector corresponding to values referenced by a target concept, where dimensions of the first vector are defined by the values associated with the attribute path specified by the simple profiled score criteria and length of dimensions are defined by the profile weights, and where the dimensions of the second vector are defined by values associated with the attribute path specified by the simple profiled score criteria, and length of dimensions are 1.0.

22. The method of claim 16, wherein a partial score of a compound profiled score criteria value is computed by computing a score for each of the sub-profiled score criteria, and aggregating results using a score integration function.

23. The method of claim 1, further comprising:

analyzing concepts in each of the search results;

selecting concepts for which explicit user feedback is to be provided;

receiving the explicit user feedback regarding the selected concepts; and

applying the explicit user feedback to an explicit feedback value in the one or more profiles.

24. A system for learning user preferences in a search of knowledge base to construct one or more profiles for producing personalized search results, the system comprising:

at least one computer system;

a computer-readable storage medium storing software components for execution by the at least one computer system, the components comprising;

an adaptive and collaborative user profiling engine for;

receiving feedback from the user regarding quality of search results presented to the user in a search of a knowledge base that is a semantic network of relationships among concepts and that provides an index of a plurality of documents, the feedback representing how well the search results match an input query provided by the user, the search results including one or more of the documents indexed by the knowledge base;

constructing the one or more profiles for the user, based on the feedback received, by determining an implicit feedback value, an explicit feedback value, and a negative feedback value for the search results for which feedback is received, wherein, for concepts associated with search criteria applied to retrieve the search results, feedback is received to create a source concept that is compared against a reference concept to form a set of source concept values and a set of reference concept values, and wherein the search results that receive feedback values are used to construct a model that includes profile weights computed from the feedback values by;

applying the implicit feedback value to the values in the set of source concept values but not in the set of reference concept values;

applying the explicit feedback value to the values in both the set of source concept values and the set of reference concept values; and

applying the negative feedback value to the values in the set of reference concept values but not in the set of source concept values; and

a personalized search and match engine for;

modifying internal weights used for scoring search criteria applied in producing the search results presented to the user, the modifications made based on the profile weights in the constructed model;

generating implicit search criteria for the user based on the one or more profiles; and

applying the implicit search criteria and modified weights during a subsequent search of the knowledge base conducted by the user producing a subsequent set of search results that are personalized to the user.

25. The system of claim 24, wherein the input query is selected from a group consisting of:

a query for job descriptions and a query for resumes for job candidates.

26. The system of claim 24, wherein the feedback receiving module is adapted for receiving ratings from the user using a system selected from the group consisting of:

a point system;

a five star rating system, a slider icon, and any combination of these.

27. The system of claim 24, wherein the feedback is implicit feedback.

28. The system of claim 24, wherein at least one of the one or more profiles is a user profile that pertains to the user'"'"'s general preferences that are not specifically associated with a search, and wherein at least one of the one or more profiles is a search profile that pertains to a particular query or query type not specifically associated with the user.

29. The system of claim 28, further comprising combining the user profile and the search profile to create a biased profile, wherein weights in the search profile are biased by weights in the user profile using a biasing function selected from a group consisting of:

a mean, a geometric mean, a generalized mean, a trimmed mean, a winsorized mean, and a median.

30. The system of claim 24, wherein the one or more profiles are arranged hierarchically to include parent profiles and child profiles.

31. A computer program product having a computer-readable medium having computer program instructions recorded thereon for learning user preferences in a search of knowledge base to construct one or more profiles for producing personalized search results, the computer program instruction comprising instructions for:

receiving feedback from the user regarding quality of search results presented to the user in a search of a knowledge base that is a semantic network of relationships among concepts and that provides an index of a plurality of documents, the feedback representing how well the search results match an input query provided by the user, the search results including one or more of the documents indexed by the knowledge base;

constructing the one or more profiles for the user, based on the feedback received, by determining an implicit feedback value, an explicit feedback value, and a negative feedback value for the search results for which feedback is received, wherein, for concepts associated with search criteria applied to retrieve the search results, feedback is received to create a source concept that is compared against a reference concept to form a set of source concept values and a set of reference concept values, and wherein the search results that receive feedback values are used to construct a model that includes profile weights computed from the feedback values by;

applying the implicit feedback value to the values in the set of source concept values but not in the set of reference concept values;

applying the explicit feedback value to the values in both the set of source concept values and the set of reference concept values; and

applying the negative feedback value to the values in the set of reference concept values but not in the set of source concept values;

modifying internal weights used for scoring search criteria applied in producing the search results presented to the user, the modifications made based on the profile weights in the constructed model;

generating implicit search criteria for the user based on the one or more profiles; and

applying the implicit search criteria and modified weights during a subsequent search of the knowledge base conducted by the user producing a subsequent set of search results that are personalized to the user.

32. The computer program product of claim 31, wherein the input query is selected from a group consisting of:

a query for job descriptions and a query for resumes for job candidates.

33. The computer program product of claim 31, wherein at least one of the one or more profiles is a user profile that pertains to the user'"'"'s general preferences that are not specifically associated with a search, and wherein at least one of the one or more profiles is a search profile that pertains to a particular query or query type not specifically associated with the user.

34. The computer program product of claim 31, wherein the one or more profiles are arranged hierarchically.

35. The computer program product of claim 31, wherein modifying the internal weights used for scoring search criteria further comprises redefining the internal weights to be a function of the internal weights used for scoring search criteria and the profiled weights, the function is selected from a group consisting of:

log frequency, log inverse frequency, linear frequency, fuzzy frequency, fuzzy inverse frequency, and any combination of these.

36. A method for learning user preferences in a search of knowledge base to construct one or more profiles for producing personalized search results, the method comprising:

receiving feedback from the user regarding quality of search results presented to the user in a search of a knowledge base that is a semantic network of relationships among concepts and that provides an index of a plurality of documents, the feedback representing how well the search results match an input query provided by the user, the search results including one or more of the documents indexed by the knowledge base;

constructing the one or more profiles for the user based on the feedback received, where each of the search results that receive feedback values are used to construct a model that includes profile weights computed from the feedback values;

modifying internal weights used for scoring search criteria applied in producing the search results presented to the user, the modifications made based on the profile weights in the constructed model;

generating implicit search criteria for the user based on the one or more profiles by;

defining simple profiled score criteria that are based on a single attribute or attribute path, the simple profiled score criteria instantiated as simple profiled score criteria values;

wherein a partial score of the simple profiled score criteria value is computed using a similarity measure between a first vector including active profile weights and a second vector corresponding to values referenced by a target concept, where dimensions of the first and second vectors are defined by the values associated with the attribute path specified by the simple profiled score criteria, and wherein length of dimensions of the first vector are defined by the profile weights; and

applying the implicit search criteria and modified weights during a subsequent search of the knowledge base conducted by the user producing a subsequent set of search results that are personalized to the user.

37. The method of claim 36, wherein the input query is selected from a group consisting of:

a query for job descriptions and a query for resumes for job candidates.

38. The method of claim 36, wherein the user provides ratings for the search results presented using a system selected from the group consisting of:

a point system;

a five star rating system, a slider icon, and any combination of these.

39. The method of claim 36, wherein the feedback is implicit feedback.

40. The method of claim 36, wherein the input query is selected from a group consisting of:

an input string of text and a document.

41. The method of claim 36, further comprising:

learning user profiles and search profiles;

applying these to the search to modify ranking of the search results.

42. The method of claim 36, wherein at least one of the one or more profiles is a user profile that pertains to the user'"'"'s general preferences that are not specifically associated with a search, and wherein at least one of the one or more profiles is a search profile that pertains to a particular query or query type not specifically associated with the user.

43. The method of claim 42, further comprising combining the user profile and the search profile to create a biased profile, wherein weights in the search profile are biased by weights in the user profile using a biasing function.

44. The method of claim 43, wherein the biasing function is selected from a group consisting of:

a mean, a geometric mean, a generalized mean, a trimmed mean, a winsorized mean, and a median.

45. The method of claim 36, wherein the one or more profiles are arranged hierarchically to include parent profiles and child profiles, and the child profiles inherit profile weights from the parent profiles where profile values are not defined in the child profile.

46. The method of claim 36, wherein constructing the one or more profiles further comprises determining a feedback value tuple for each search result, the feedback value tuple including an implicit feedback value, an explicit feedback value, and a negative feedback value.

47. The method of claim 46, wherein, for concepts associated with the search criteria applied to retrieve each search result, feedback is received to create a source concept that is compared against a reference concept to form a set of source concept values and a set of reference concept values.

48. The method of claim 47, further comprising constructing the model by:

applying the implicit feedback value to all values in the set of source concept values but not in the set of reference concepts;

applying the explicit feedback value to all values in both the set of source concepts and the set of reference concepts; and

applying the negative feedback value to all values in the set of reference concepts but not in the set of source concepts.

49. The method of claim 36, wherein the profile weights are computed by a weight function selected from a group consisting of:

geometric mean;

weighted geometric mean, weighted average, and average.

50. The method of claim 36, wherein modifying the internal weights used for scoring search criteria further comprises redefining the internal weights to be a function of the internal weights used for scoring search criteria and the profiled weights.

51. The method of claim 50, wherein the function is selected from a group consisting of:

log frequency, log inverse frequency, linear frequency, fuzzy frequency, fuzzy inverse frequency, and any combination of these.

52. The method of claim 36, further comprising removing oldest feedback information when a forgetting rate threshold is reached.

53. The method of claim 36, further comprising defining compound profiled score criteria that are based on a set of profiled score criteria, wherein the compound profiled score criteria are instantiated as compound profiled score criteria values, the simple profiled score criteria values and the compound profiled score criteria values each being composed of sub-profiled score criteria.

54. The method of claim 53, wherein the simple profiled score criteria values and the compound profiled score criteria values can be defined by a tuple of values selected from a group consisting of:

a weight range, a weight, a requirement that can be required or desired, and any combination of these.

55. The method of claim 54, wherein the simple profiled score criteria values can use an attribute path from a target concept to select a set of values to evaluate, which is an evaluation set, and wherein the weight of the simple profiled score criteria value is a function of a total number of values in the evaluation set and a number of values in the evaluation set for which profile weights are described.

56. The method of claim 54, wherein the weight for the simple profiled score criteria value is computed using weight functions selected from a group consisting of:

log frequency and log inverse frequency.

57. The method of claim 54, wherein the weight of the compound profiled score criteria values is computed using weight functions selected from a group consisting of:

a geometric mean and a mean of the weights of the sub-profiled score criteria.

58. The method of claim 53, wherein a partial score of a compound profiled score criteria value is computed by computing a score for each of the sub-profiled score criteria, and aggregating results using a score integration function.

59. The method of claim 36, further comprising:

analyzing concepts in each of the search results;

selecting concepts for which explicit user feedback is to be provided;

receiving the explicit user feedback regarding the selected concepts; and

applying the explicit user feedback to an explicit feedback value in the one or more profiles.

60. A system for learning user preferences in a search of knowledge base to construct one or more profiles for producing personalized search results, the system comprising:

at least one computer system;

a computer-readable storage medium storing software components for execution by the at least one computer system, the components comprising;

an adaptive and collaborative user profiling engine for;

receiving feedback from the user regarding quality of search results presented to the user in a search of a knowledge base that is a semantic network of relationships among concepts and that provides an index of a plurality of documents, the feedback representing how well the search results match an input query provided by the user, the search results including one or more of the documents indexed by the knowledge base;

constructing the one or more profiles for the user, based on the feedback received, where each of the search results that receive feedback values are used to construct a model that includes profile weights computed from the feedback values; and

a personalized search and match engine for;

modifying internal weights used for scoring search criteria applied in producing the search results presented to the user, the modifications made based on the profile weights in the constructed model;

generating implicit search criteria for the user based on the one or more profiles by;

defining simple profiled score criteria that are based on a single attribute or attribute path, the simple profiled score criteria instantiated as simple profiled score criteria values;

wherein a partial score of the simple profiled score criteria value is computed using a similarity measure between a first vector including active profile weights and a second vector corresponding to values referenced by a target concept, where dimensions of the first and second vectors are defined by the values associated with the attribute path specified by the simple profiled score criteria, and wherein length of dimensions of the first vector are defined by the profile weights; and

applying the implicit search criteria and modified weights during a subsequent search of the knowledge base conducted by the user producing a subsequent set of search results that are personalized to the user.

61. The system of claim 60, wherein the input query is selected from a group consisting of:

a query for job descriptions and a query for resumes for job candidates.

62. The system of claim 60, wherein the feedback receiving module is adapted for receiving ratings from the user using a system selected from the group consisting of:

a point system;

a five star rating system, a slider icon, and any combination of these.

63. The system of claim 60, wherein the feedback is implicit feedback.

64. The system of claim 60, wherein at least one of the one or more profiles is a user profile that pertains to the user'"'"'s general preferences that are not specifically associated with a search, and wherein at least one of the one or more profiles is a search profile that pertains to a particular query or query type not specifically associated with the user.

65. The system of claim 64, further comprising combining the user profile and the search profile to create a biased profile, wherein weights in the search profile are biased by weights in the user profile using a biasing function selected from a group consisting of:

a mean, a geometric mean, a generalized mean, a trimmed mean, a winsorized mean, and a median.

66. The system of claim 60, wherein the one or more profiles are arranged hierarchically to include parent profiles and child profiles.

67. A computer program product having a computer-readable medium having computer program instructions recorded thereon for learning user preferences in a search of knowledge base to construct one or more profiles for producing personalized search results, the computer program instruction comprising instructions for:

receiving feedback from the user regarding quality of search results presented to the user in a search of a knowledge base that is a semantic network of relationships among concepts and that provides an index of a plurality of documents, the feedback representing how well the search results match an input query provided by the user, the search results including one or more of the documents indexed by the knowledge base;

constructing the one or more profiles for the user, based on the feedback received, where each of the search results that receive feedback values are used to construct a model that includes profile weights computed from the feedback values;

modifying internal weights used for scoring search criteria applied in producing the search results presented to the user, the modifications made based on the profile weights in the constructed model;

generating implicit search criteria for the user based on the one or more profiles by;

defining simple profiled score criteria that are based on a single attribute or attribute path, the simple profiled score criteria instantiated as simple profiled score criteria values;

wherein a partial score of the simple profiled score criteria value is computed using a similarity measure between a first vector including active profile weights and a second vector corresponding to values referenced by a target concept, where dimensions of the first and second vectors are defined by the values associated with the attribute path specified by the simple profiled score criteria, and wherein length of dimensions of the first vector are defined by the profile weights; and

applying the implicit search criteria and modified weights during a subsequent search of the knowledge base conducted by the user producing a subsequent set of search results that are personalized to the user.

68. The computer program product of claim 67, wherein the input query is selected from a group consisting of:

a query for job descriptions and a query for resumes for job candidates.

69. The computer program product of claim 67, wherein at least one of the one or more profiles is a user profile that pertains to the user'"'"'s general preferences that are not specifically associated with a search, and wherein at least one of the one or more profiles is a search profile that pertains to a particular query or query type not specifically associated with the user.

70. The computer program product of claim 67, wherein the one or more profiles are arranged hierarchically.

71. The computer program product of claim 67, wherein modifying the internal weights used for scoring search criteria further comprises redefining the internal weights to be a function of the internal weights used for scoring search criteria and the profiled weights, the function is selected from a group consisting of:

log frequency, log inverse frequency, linear frequency, fuzzy frequency, fuzzy inverse frequency, and any combination of these.