Event Prediction Using Hierarchical Event Features

• US 20130006900A1
• Filed: 09/10/2012
• Published: 01/03/2013
• Est. Priority Date: 06/17/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Taylor, Michael J., Vinay, Vishwa, Shnitko, Yauhen
• Granted Patent: US 8,831,754 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Event prediction using hierarchical event features is described. In an embodiment a search engine monitors search results presented to users and whether users click on those search results. For example, features describing the search result events are universal resource locator prefix levels which are inherently hierarchically related. In an embodiment a graphical data structure is created and stored and used to represent the hierarchical relationships between features. An online training process is used in examples which enables knowledge to be propagated through the graphical data structure according to the hierarchical relations between features. In an example, the graphical data structure is used to predict whether a user will click on a search result and those predictions are used by the search engine to rank search results for future searches. In another example the events are advertisement impressions and the predictions are used by an online advertisement system.

Claims

1. A computer-implemented method comprising:

monitoring a stream of events occurring at an apparatus, each event being associated with a plurality of features describing the event, at least some of the plurality of features being related in a hierarchical manner;

creating a graphical data structure comprising variable nodes connected by edges, the plurality of features describing the event being represented by variable nodes and the variable nodes being connected such that sequences of connected variable nodes represent the hierarchical relations between features, each variable node being associated with statistics describing a probability distribution representing a latent event score;

arranging a training engine to update the statistics for at least one of the variable nodes on the basis of the monitoring; and

predicting an event using the graphical data structure.

2. The computer-implemented method of claim 1, wherein the statistics for the at least one of the variable nodes are updated by using a Bayesian machine learning process.

3. The computer-implemented method of claim 1, wherein the statistics for the at least one of the variable nodes are updated by propagating the latent event score along the sequences of variable nodes which represent the hierarchical relations.

4. The computer-implemented method of claim 1, wherein creating the graphical data structure comprises creating a tree-based graphical data structure comprising layers of parent and child variable nodes.

5. The computer-implemented method of claim 4, wherein arranging the training engine to update the statistics comprises enabling a child variable node to inherit a noisy version of the latent event score of a parent variable node.

6. The computer-implemented method of claim 4, wherein creating the graphical data structure further comprises forming a level noise variable node at each layer of variable nodes.

7. The computer-implemented method of claim 1, wherein creating the graphical data structure comprises incorporating factor nodes as computational units into the graphical data structure, each factor node having at least one associated computational message.

8. The computer-implemented method of claim 7, wherein the statistics for the at least one of the variable nodes are updated by using messaging passing that includes computing the computational messages and passing results of the computations to variable nodes in the graphical data structure.

11. The computer-implemented method of claim 1, wherein the plurality of features that are related in a hierarchical manner are uniform resource locator prefix levels.

12. The computer-implemented method of claim 1, wherein the stream of events comprises presentations of search results at a user interface and associated user inputs.

9. The computer-implemented method 1, wherein at least some of the plurality of features for one or more of the events are not hierarchically related and the graphical data structure is created such that the graphical data structure comprises an observation component including a plurality of variable nodes representing weights associated with the features that are not hierarchically related.

10. The computer-implemented method of claim 9, wherein the latent event scores act as a bias on an output of the observation component.

13. A system comprising:

one or more processors;

memory;

a monitor component maintained at least in part in the memory and executed at least in part by the one or more processors to monitor a stream of events occurring at the system, each event being associated with a plurality of features describing the event, at least some of the plurality of features being related in a hierarchical manner;

a graphical data component maintained at least in part in the memory and executed at least in part by the one or more processors to create a graphical data structure comprising layers of parent and child variable nodes connected by edges, weights associated with the features being represented by variable nodes and the variable nodes being connected such that sequences of connected variable nodes represent the hierarchical relations between features, each variable node being associated with statistics describing a probability distribution representing a latent event score;

a training engine maintained at least in part in the memory and executed at least in part by the one or more processors to update the statistics for at least one of the variable nodes on the basis of the monitoring; and

a prediction engine maintained at least in part in the memory and executed at least in part by the one or more processors to predict an event using the graphical data structure.

14. The system of claim 13, wherein the statistics for the at least one of the variable nodes are updated by enabling a child variable node to inherit a noisy version of the latent event score of a parent variable node of the child node.

15. The system of claim 14, wherein the noisy version is specified using the level noise variable node in the layer of the parent variable node.

16. The system of claim 13, wherein the graphical data structure further comprises a level noise variable node at each layer of variable nodes.

17. One or more computer storage media storing computer-readable instructions that, when executed, instruct one or more processors to perform operations comprising:

monitoring a stream of search and user input events, each event being associated with a plurality of features describing the event, at least some of the plurality of features being universal resource locator prefix levels of a document;

creating a graphical data structure comprising layers of parent and child variable nodes connected by edges, weights associated with the plurality of features being represented by variable nodes and at least some of the variable nodes being connected such that sequences of connected variable nodes represent the universal resource locator prefix levels of the document, each variable node being associated with statistics describing a probability distribution representing a latent event score;

updating the statistics for at least one of the variable nodes on the basis of the monitoring; and

predicting a user input event using the graphical data structure.

18. The one or more computer storage media of claim 17, wherein the statistics for the at least one of the variable nodes is updated by using a Bayesian machine learning process such that latent event score information is propagated along the sequences of variable nodes which represent the universal resource locator prefix levels of the document.

19. The one or more computer storage media of claim 17, wherein at least some of the features are content features of the document and the graphical data structure is stored such that weights associated with the content features are stored at content variable nodes.

20. The one or more computer storage media of claim 19, wherein the latent event scores are able to act as a bias on the content variable nodes.