PREDICTING BEHAVIOR USING FEATURES DERIVED FROM STATISTICAL INFORMATION

• US 20140337096A1
• Filed: 05/13/2013
• Published: 11/13/2014
• Est. Priority Date: 05/13/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bilenko, Mikhail, Gilad-Bachrach, Ran, Meek, Christopher A., Royzner, Mikhail
• Granted Patent: US 10,482,482 B2
• Time in Patent Office: Days
• US Class Current: 705/7.31
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 10/067 Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/103 Workflow collaboration or project management
• CPC Class Codes: G06Q 10/105 Human resources
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities
• CPC Class Codes: G06Q 30/0235 constrained by time limit or expiration date
• CPC Class Codes: G06Q 30/0255 based on user history
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes

Abstract

A training system is described herein for generating a prediction model that relies on a feature space with reduced dimensionality. The training system performs this task by producing partitions, each of which corresponds to a subset of aspect values (where each aspect value, in turn, may correspond to one or more attribute values). The training system then produces instances of statistical information associated with the partitions. Each instance of statistical information therefore corresponds to feature information that applies to a plurality of aspect values, rather than a single aspect value. The training system then trains the prediction model based on the feature information. Also described herein is a prediction module that uses the prediction model to make predictions in various online contexts.

Claims

1. A method, performed by one or more computing devices, for generating a prediction model, comprising:

receiving a master dataset that provides plural training examples, each training example being associated with;

one or more aspects of an event, and corresponding one or more aspect values; and

a label associated with the event;

for a particular aspect, producing plural partitions based on a partitioning strategy, the plural partitions being associated with plural respective subsets of aspect values;

identifying plural subsets of data within the master dataset that pertain to the respective plural partitions, and generating plural instances of statistical information based on the respective subsets of data, the plural instances of statistical information corresponding to feature information that reflects a distribution of labels in the subsets of data;

generating a prediction model based on the feature information and a set of training examples; and

storing the prediction model in a data store.

2. The method of claim 1, further comprising repeating said producing the plural partitions, said identifying the plural subsets of data, and said generating the plural instances of statistical information for one or more other aspects.

3. The method of claim 1, wherein the particular aspect is associated with a single attribute.

4. The method of claim 3, wherein the single attribute corresponds to one of:

user-related information pertaining to a user who interacts with a system;

content-related information pertaining to content provided to the user; and

context-related information pertaining to a context in which the content is delivered to the user.

5. The method of claim 1, wherein the particular aspect is associated with a combination of two or more attributes.

6. The method of claim 1, wherein the partitioning strategy involves grouping aspects values based on a loss of predictive accuracy measure.

7. The method of claim 1, wherein the partitioning strategy involves grouping aspect values in a manner that that results in a minimum loss of predictive accuracy.

8. The method of claim 1, wherein the partitioning strategy involves one of:

grouping aspect values based on a frequency of occurrence measure;

grouping aspect values so that at least one partition includes aspect values that have a common component attribute value;

grouping aspect values using a clustering operation; and

grouping aspect values using a hashing operation.

9. The method of claim 1, wherein the prediction model generates a prediction that indicates a probability that a user will take a prescribed action with respect to a particular ad.

10. The method of claim 1, wherein the prediction model generates a prediction that indicates a probability that a user will take a prescribed action with respect to an item within search results.

11. The method of claim 1, further comprising:

deploying the prediction model in a prediction module, within a system;

using the prediction module to;

receive input information;

map the input information to associated feature information; and

generate a prediction based on the associated feature information.

12. The method of claim 11, further comprising:

collecting post-deployment data, each instance of the post-deployment data describing an event that occurs following deployment of the prediction model; and

using the post-deployment data, repeating one or more of;

said producing the plural partitions, said identifying the plural subsets of data, and said generating the plural instances of statistical information.

13. A computer readable storage medium for storing computer readable instructions, the computer readable instructions providing a training system when executed by one or more processing devices, the computer readable instructions comprising:

logic configured to receive a master dataset that provides plural training examples;

logic configured to produce plural partitions based on a partitioning strategy;

logic configured to;

identify plural subsets of data within the master dataset that pertain to the respective plural partitions; and

generate plural instances of statistical information based on the respective subsets of data, the plural instances of statistical information corresponding to feature information; and

logic configured to train a prediction model based on the feature information and a set of training examples.

14. The computer readable storage medium of claim 13, wherein said logic configured to identify and generate is configured to express the feature information as a lookup data structure, each entry in the lookup data structure corresponding to a particular partition and a corresponding instance of statistical information.

15. The computer readable storage medium of claim 13, wherein said logic configured to identify and generate is implemented as a plurality of processing resources which operate in parallel.

16. The computer readable storage medium of claim 13, wherein the partitioning strategy involves producing partitions that satisfy a prescribed predictive accuracy objective.

17. The computer readable storage medium of claim 16, wherein the partitions satisfy the prescribed predictive accuracy objective when the partitions produce a minimum loss of predictive accuracy.

18. One or more computing devices for implementing a prediction module, comprising:

a data store that provides at least one lookup data structure, each lookup data structure being associated with a particular aspect of events, and each lookup data structure identifying;

plural partitions; and

plural instances of statistical information associated with the plural partitions, each instance of statistical information applying to a subset of aspect values;

a feature lookup module configured to;

receive input information associated with a new event;

identify one or more aspect values associated with the input information; and

identify, using said at least one lookup data structure, statistical information that is associated with the new event, based on said one or more aspect values, to produce identified statistical information; and

a prediction generation module configured to generate a prediction based on the identified statistical information.

19. The one or more computer devices of claim 18, wherein the prediction generation module is configured to generate a prediction that indicates a probability that a user will take a prescribed action with respect to a particular ad.

20. The one or more computer devices of claim 18, wherein the prediction generation module is configured to generate a prediction that indicates a probability that a user will take a prescribed action with respect to an item within search results.