Predicting behavior using features derived from statistical information

• US 10,482,482 B2
• Filed: 05/13/2013
• Issued: 11/19/2019
• Est. Priority Date: 05/13/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Bilenko, Mikhail, Gilad-Bachrach, Ran, Meek, Christopher A., Royzner, Mikhail
• Primary Examiner(s): Misiaszek, Amber A
• Assistant Examiner(s): Byrd, Uche
• Application Number:
  US13/892,311
• Publication Number:
  US 20140337096A1
• Time in Patent Office: 2,381 Days
• Field of Search: 705 711- 742
• 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 utilizing a reduced-dimensionality feature space prediction model to present user-selectable content in an online environment based on a prediction of a future user behavior within the online environment, by way of the prediction model that utilizes a feature vector as an input, the method comprising:

receiving a master dataset that includes a plurality of training examples, each training example in the plurality of training examples comprising;

an event that comprises a plurality of characteristics and a user'"'"'s decision within a circumstance to click on an object or not click on the object,

wherein the event is associated with aspect variables that describe the characteristics of the event,

wherein the aspect variables associated with the event comprise user-related aspect variables, content-related aspect variables, and context-related aspect variables, and

wherein each aspect variable is associated with a set of one or more possible aspect values,

corresponding aspect values, and

a label associated with the event, wherein the label identifies whether the user clicked on the object or declined to click on the object;

for a particular aspect of the event, producing plural partitions within the aspect values that correspond to the particular aspect, based on a partitioning strategy that includes grouping the aspect values into plural subsets of aspect values such that each partition is associated with a respective subset of aspect values, wherein the partitioning strategy comprises assessing a frequency at which each aspect value occurs within the master dataset and grouping together aspect values that have similar frequency of occurrence values;

for each of the respective partitions,

identifying plural subsets of data within the master dataset that pertain to the respective plural partitions, and

generating an instance of statistical information based on the respective corresponding subset of data, wherein the plural instances of statistical information correspond respectively to feature information that reflects a distribution of labels in the subsets of data, and wherein individual statistical measures within the feature information respectively constitute features which describe one or more events, wherein each feature corresponds to a plurality of aspect values, thereby providing a reduced dimensionality of a feature space that is utilized to train the prediction model;

generating the prediction model based on the feature information and a set of training examples, wherein the prediction model utilizes as input the feature vector comprising a set of the features that describe an event for which a prediction of the future user behavior is made;

storing the prediction model in a data store;

receiving input information associated with a new event comprising an online environment that displays user-selectable items to a user;

utilizing the prediction model to predict that the user will select a particular user-selectable item, based on features that correspond to the new event; and

based on having predicted that the user will select the particular user-selectable item, causing the particular user-selectable item to be presented to the user.

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 the 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 results in a minimum loss of predictive accuracy.

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

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 having

embodied thereon computer-usable instructions which, when executed by one or more processing devices, perform a method for utilizing a reduced-dimensionality feature space prediction model to present user-selectable content in an online environment based on a prediction of a future user behavior within the online environment, the method comprising:

receiving a master dataset that provides plural training examples;

producing plural bins based on a partitioning strategy;

identifying plural subsets of data within the master dataset that pertain to the respective plural bins for a single aspect variable, wherein each subset of data corresponds to a respective bin, and wherein each subset of data comprises a respective set of aspect values for the aspect variable;

for each bin, generating a respective instance of statistical information based on the subset of data in the bin, wherein the respective instance of statistical information corresponds to the bin, wherein each instance of statistical information is utilized as a feature to train a prediction model, wherein each feature corresponds to a plurality of aspect values for the single aspect variable, thereby providing a reduced dimensionality of a feature vector that is utilized to train a prediction model;

training the prediction model, which predicts a future user behavior, based on the feature information and a set of training examples;

receiving input information that describes a new event, the new event comprising an online environment that displays user-selectable items to a user,

wherein the new event is associated with aspect variables that describe characteristics of the new event, and wherein each aspect variable is associated with a set of one or more possible aspect values;

identifying aspect values associated with the new event;

determining which of the instances of statistical information are associated with the identified aspect values, wherein the determined instances of statistical information constitute features that correspond to the new event;

utilizing the prediction model to predict that the user will select a particular user-selectable item, based on the features that correspond to the new event; and

based on the prediction that the user will select the particular user-selectable item, causing the particular user-selectable item to be presented to the user.

14. The computer readable storage medium of claim 13, the method further comprising expressing the feature information as a lookup data structure, each entry in the lookup data structure corresponding to a particular bin and a corresponding instance of statistical information.

15. The computer readable storage medium of claim 13, wherein said identifying and generating are 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 bins that satisfy a prescribed predictive accuracy objective.

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

18. A system for utilizing a reduced-dimensionality feature space prediction model to present user-selectable content in an online environment based on a prediction of a future user behavior within the online environment, comprising:

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

wherein an event comprises a plurality of characteristics and a user'"'"'s decision within a circumstance to click on an object or not click on the object,

wherein the event is associated with aspect variables that describe the characteristics of the event,

wherein the event is associated with a label that identifies whether the user clicked on the object or declined to click on the object,

wherein each aspect variable is associated with instances of statistical information that represent respective partitions of aspect values associated with the aspect variable;

and each lookup data structure identifies;

plural partitions associated with the particular aspect; and

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

a feature lookup module comprising one or more processors configured to;

receive input information that describes a new event, wherein the new event comprises an opportunity to predict whether a current user will click on a particular object in an online environment;

based on the input information that describes the new event, identify one or more aspect values associated with the new event; and

identify, using said at least one lookup data structure, statistical information that is associated with the new event, based on a correspondence between said one or more aspect values and the statistical information, to produce identified statistical information, wherein instances of the identified statistical information correspond respectively to features that describe the new event, wherein each feature corresponds to a plurality of aspect values, thereby providing a reduced dimensionality of a feature space that is utilized to train the prediction model;

a prediction generation module comprising one or more processors configured to generate a prediction, for the new event, of whether the user will click on the particular object in the online environment, based on an input feature vector comprising the features that describe the new event; and

an action taking module comprising one or more processors configured to cause content to be presented to the online environment, wherein the content is determined and presented based on the prediction of whether the user will click on the particular object in the online environment.

19. The system 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 system 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.