Association learning for automated recommendations

• US 20040083232A1
• Filed: 12/16/2002
• Published: 04/29/2004
• Est. Priority Date: 10/25/2002
• Status: Abandoned Application

• Current Assignee: SAP AG (SAP SE)
• Original Assignee: SAP AG (SAP SE)
• Inventors: Kaiser, Matthias, Ronnewinkel, Christopher, Wu, Yuh-Cherng
• Application Number:
  US10/320,005
• Publication Number:
  US 20040083232A1
• Time in Patent Office: Days
• US Class Current: 707/104.1
• CPC Class Codes: G06F 16/332 Query formulation
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

A system is disclosed to provide associative learning and recommendations. The system includes a learning engine recommendation process that provides one or more recommendations based on user input, a learning engine initiation process that generates initial training data, and a learning engine training process that transforms initial training data and subsequent training data into entity-pair relationships. The system may include user interfaces that allow each user to request and receive recommendations and a confirmation process that captures and stores training data based on user feedback regarding recommendations.

Claims

1. A method comprising:

generating correlation data from initialization data representing relations between entities;

generating a directed graph from the correlation data;

providing one or more recommendations from the directed graph using a request as input;

storing training data in response to user activity; and

adapting the correlation data using the training data as input.

2. The method of claim 1 wherein generating the correlation data comprises:

forming an entity-pair from the initialization data;

computing a strength of association for the entity-pair; and

computing a normalized strength of association for the entity-pair, wherein the correlation data includes the normalized strength of association.

3. The method of claim 2 wherein computing a strength of association comprises calculating a frequency of occurrence for the entity-pair in the initialization data.

4. The method of claim 2 wherein computing the normalized strength of association comprises:

calculating a normalization constant by summing the strength of association for each entity-pair; and

calculating the normalized strength of association by dividing the strength of association by the normalization constant.

5. The method of claim 1 wherein generating the directed graph comprises:

generating nodes from the correlation data using entity-pairs as input; and

generating arcs connecting the nodes using normalized strengths between the entity-pairs as input.

6. The method of claim 1 wherein providing recommendations comprises:

receiving the request from a user;

accessing a first set of one or more nodes on the directed graph matching the request;

traversing one or more arcs connected to the first set of one or more nodes;

accessing a second set of one or more nodes connected to one or more arcs; and

recommending the second set of one or more nodes to the user.

7. The method of claim 6 wherein traversing one or more arcs connected to the first set of one or more nodes comprises:

obtaining an arc strength from an arc;

comparing the arc strength to a pre-defined value; and

determining whether to traverse the arc based on the comparison.

8. The method of claim 6 wherein providing one or more recommendations comprises applying spread activation to the first set of one or more nodes.

9. The method of claim 8 wherein applying spread activation comprises:

obtaining a level of activation from a database table;

obtaining a decay constant from a database table;

applying a spreading activation algorithm to the first set of one or more nodes.

10. The method of claim 1 further comprising:

displaying an interface prompting feedback from the user regarding the quality of the recommendations; and

determining whether to store the request and one or more recommendations in a database as the training data based upon the feedback.

11. The method of claim 1 further comprising:

observing selected actions by a user based on one or more recommendations; and

determining whether to store the request and the recommendations in a database as the training data based upon the selected actions.

12. The method of claim 1 wherein adapting correlation data comprises:

accessing the training data using access controls;

generating adaptation data from a learning rule using the training data as input; and

adapting the correlation data using the adaptation data as input.

13. The method of claim 12 wherein generating adaptation data from the learning rule comprises:

accessing a data set in the training data;

forming an entity-pair based on the co-occurrence of elements in the data set;

determining whether the entity-pair exists in the adaptation data; and

adding the entity-pair to the adaptation data if the entity-pair does not exist in the adaptation data.

14. The method of claim 12 wherein generating the adaptation data from the learning rule comprises:

accessing a first data set in the training data;

accessing a second data set in the training data corresponding to the initial set;

forming an entity-pair wherein a first entity is in the first data set, a second entity is in the second data set, and the first entity and the second entity in combination are not in either the first data set or second data set;

determining whether the entity-pair exists in the adaptation data; and

adding the entity-pair to the adaptation data if the entity-pair does not exist in the adaptation data.

15. The method of claim 12 wherein generating the adaptation data from the learning rule comprises:

accessing a sequenced data set in the training data;

forming an entity-pair which consists of a first and second entity from the sequenced data set wherein the second entity immediately follows the first entity;

determining whether the entity-pair exists in the adaptation data; and

adding the entity-pair to the adaptation data if the entity-pair does not exist in the adaptation data.

16. The method of claim 12 wherein adapting correlation data using the adaptation data as input comprises:

triggering a copy of the correlation data to a second correlation data;

adding entity-pairs from the adaptation data to the second correlation data;

calculating a strength of association for the entity pairs in the second correlation data;

calculating a normalized strength of association for the entity-pairs in the second correlation data; and

overlaying the correlation data with the second correlation data.

17. The method of claim 16 wherein adapting correlation data using the adaptation data as input further comprises determining whether a threshold amount of training data is collected.

18. The method of claim 16 wherein adapting correlation data using the adaptation data as input is performed asynchronously.

19. An article comprising a machine-readable medium storing machine-readable instructions that, when applied to the machine, cause the machine to:

generate correlation data from initialization data representing associations between entities;

generate a directed graph from the correlation data;

provide one or more recommendations from the directed graph using a request as input;

store training data in response to user activity; and

adapt the correlation data using the training data as input.

20. The article of claim 19 including instructions that, when applied to the machine, cause the machine to:

form an entity-pair from the initialization data;

compute a strength of association for the entity-pair; and

compute a normalized strength of association for the entity-pair, wherein the correlation data includes the normalized strength of association.

21. The article of claim 20 including instructions that, when applied to the machine, cause the machine to compute a strength of association by calculating a frequency of occurrence for the entity-pair in the initialization data.

22. The article of claim 20 including instructions that, when applied to the machine, cause the machine to:

calculate a normalization constant by summing the strength of association for each entity-pair; and

calculate the normalized strength of association by dividing the strength of association by the normalization constant.

23. The article of claim 19 including instructions that, when applied to the machine, cause the machine to:

generate nodes from the correlation data using entity-pairs as input; and

generate arcs connecting the nodes using normalized strengths between the entity-pairs as input.

24. The article of claim 19 including instructions that, when applied to the machine, cause the machine to:

access a first set of one or more nodes on the directed graph matching the request in response to receiving the request from a user;

traverse one or more arcs connected to the first set of one or more nodes;

access a second set of one or more nodes connected to one or more arcs; and

recommend the second set of one or more nodes to the user.

25. The article of claim 24 including instructions that, when applied to the machine, cause the machine to:

obtain an arc strength from an arc;

compare the arc strength to a pre-defined value; and

determine whether to traverse the arc based on the comparison.

26. The article of claim 24 including instructions that, when applied to the machine, cause the machine to apply spread activation to the first set of one or more nodes.

27. The article of claim 26 including instructions that, when applied to the machine, cause the machine to:

obtain a level of activation from a database table;

obtain a decay constant from a database table; and

apply a spreading activation algorithm to the first set of one or more nodes.

28. The article of claim 19 including instructions that, when applied to the machine, cause the machine to:

display an interface prompting feedback from the user regarding the quality of the recommendations; and

determine whether to store the request and one or more recommendations in a database as the training data based upon the feedback.

29. The article of claim 19 including instructions that, when applied to the machine, cause the machine to:

observe selected actions by a user based on one or more recommendations; and

determine whether to store the request and the recommendations in a database as the training data based upon the selected actions.

30. The article of claim 19 including instructions that, when applied to the machine, cause the machine to:

access the training data using access controls;

generate adaptation data from a learning rule using the training data as input; and

adapt the correlation data using the adaptation data as input.

31. The article of claim 30 including instructions that, when applied to the machine, cause the machine to:

access a data set in the training data;

form an entity-pair based on the co-occurrence of elements in the data set;

determine whether the entity-pair exists in the adaptation data; and

add the entity-pair to the adaptation data if the entity-pair does not exist in the adaptation data.

32. The article of claim 30 including instructions that, when applied to the machine, cause the machine to:

access a first data set in the training data;

access a second data set in the training data corresponding to the initial set;

form an entity-pair wherein a first entity is in the first data set, a second entity is in the second data set, and the first entity and the second entity in combination are not in either the first data set or second data set;

determine whether the entity-pair exists in the adaptation data; and

add the entity-pair to the adaptation data if the entity-pair does not exist in the adaptation data.

33. The article of claim 30 including instructions, that when applied to the machine, cause the machine to:

access a sequenced data set in the training data;

form an entity-pair which consists of a first and second entity from the sequenced data set wherein the second entity immediately follows the first entity;

determine whether the entity-pair exists in the adaptation data; and

add the entity-pair to the adaptation data if the entity-pair does not exist in the adaptation data.

34. The article of claim 30 including instructions that, when applied to the machine, cause the machine to:

trigger a copy of the correlation data to a second correlation data;

add entity-pairs from the adaptation data to the second correlation data;

calculate a strength of association for the entity-pairs in the second correlation data;

calculate a normalized strength of association for the entity-pairs in the second correlation data; and

overlay the correlation data with the second correlation data.

35. The article of claim 34 including instructions that, when applied to the machine, cause the machine to determine whether a threshold amount of training data is collected.

36. The article of claim 34 including instructions that, when applied to the machine, cause the machine to adapt correlation data using the adaptation data as input asynchronously.

37. A system comprising:

a computer network;

a directory coupled to the network, the directory storing correlation data, training data, and configuration data;

user interfaces coupled to the network to allow each user independently to request and receive recommendations; and

a service delivery device coupled to the network, the service delivery device including a processor and memory storing instructions that, in response to receiving a request for recommendations, cause the processor to;

generate the correlation data from initialization data representing associations between entities;

generate a directed graph from the correlation data;

provide one or more recommendations from the directed graph using a request as input;

store the training data in response to user activity; and

adapt the correlation data using the training data as input.

38. The system of claim 37 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

form an entity-pair from the initialization data;

compute a strength of association for the entity-pair; and

compute a normalized strength of association for the entity-pair, wherein the correlation data includes the normalized strength of association.

39. The system of claim 38 wherein the memory stores instructions that, in response to receiving the request, cause the processor to compute a strength of association by calculating a frequency of occurrence for the entity-pair in the initialization data.

40. The system of claim 38 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

calculate a normalization constant by summing the strength of association for each entity-pair; and

calculate the normalized strength of association by dividing the strength of association by the normalization constant.

41. The system of claim 37 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

generate nodes from the correlation data using entity-pairs as input; and

generate arcs connecting the nodes using normalized strengths between the entity-pairs as input.

42. The system of claim 37 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

access a first set of one or more nodes on the directed graph matching the request in response to receiving the request from a user;

traverse one or more arcs connected to the first set of one or more nodes;

access a second set of one or more nodes connected to one or more arcs; and

recommend the second set of one or more nodes to the user.

43. The system of claim 42 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

obtain an arc strength from an arc;

compare the arc strength to a pre-defined value; and

determine whether to traverse the arc based on the comparison.

44. The system of claim 42 wherein the memory stores instructions that, in response to receiving the request, cause the processor to apply spread activation to the first set of one or more nodes.

45. The system of claim 44 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

obtain a level of activation from a database table;

obtain a decay constant from a database table; and

apply a spreading activation algorithm to the first set of one or more nodes.

46. The system of claim 37 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

display an interface prompting feedback from the user regarding the quality of the recommendations; and

determine whether to store the request and one or more recommendations in a database as the training data based upon the feedback.

47. The system of claim 37 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

observe selected actions by a user based on one or more recommendations; and

determine whether to store the request and the recommendations in a database as the training data based upon the selected actions.

48. The system of claim 37 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

access the training data using access controls;

generate adaptation data from a learning rule using the training data as input; and

adapt the correlation data using the adaptation data as input.

49. The system of claim 48 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

access a data set in the training data;

form an entity-pair based on the co-occurrence of elements in the data set;

determine whether the entity-pair exists in the adaptation data; and

add the entity-pair to the adaptation data if the entity-pair does not exist in the adaptation data.

50. The system of claim 48 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

access a first data set in the training data;

access a second data set in the training data corresponding to the initial set;

form an entity-pair wherein a first entity is in the first data set, a second entity is in the second data set and the first entity and the second entity in combination are not in either the first data set or second data set;

determine whether the entity-pair exists in the adaptation data; and

add the entity-pair to the adaptation data if the entity-pair does not exist in the adaptation data.

51. The system of claim 48 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

access a sequenced data set in the training data;

form an entity-pair which consists of a first and second entity from the sequenced data set wherein the second entity immediately follows the first entity;

determine whether the entity-pair exists in the adaptation data; and

add the entity-pair to the adaptation data if the entity-pair does not exist in the adaptation data.

52. The system of claim 48 wherein the memory stores instructions that, in response to receiving the request, cause the processor to:

trigger a copy of the correlation data to a second correlation data;

add entity-pairs from the adaptation data to the second correlation data;

calculate a strength of association for the entity pairs in the second correlation data;

calculate a normalized strength of association for the entity-pairs in the second correlation data; and

overlay the correlation data with the second correlation data.

53. The system of claim 52 wherein the memory stores instructions that, in response to receiving the request, cause the processor to determine whether a threshold amount of training data is collected.

54. The system of claim 52 wherein the memory stores instructions that, in response to receiving the request, cause the processor to adapt correlation data using the adaptation data as input asynchronously.