# US 10,482,482 B2 · Predicting behavior using features derived from statistical information > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,482,482 B2 - Document ID: US10482482B2 - Status: Granted - Kind: B2 - Application number: 13/892,311 - Filed: 2013-05-13 - Published: 2014-11-13 - Granted: 2019-11-19 - Earliest claimed: 2013-05-13 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Corporation - Inventors: Mikhail Bilenko; Ran Gilad-Bachrach; Christopher A. Meek; Mikhail Royzner - Web page: https://patentgrep.com/patent/US10482482B2 ## CPC - G06Q 30/0202: Market predictions or forecasting for commercial activities - G06N 20/00: Machine learning - G06Q 10/06315: {Needs-based resource requirements planning or analysis} - G06Q 10/067: Enterprise or organisation modelling - G06Q 10/103: {Workflow collaboration or project management} - G06Q 10/105: Human resources - G06Q 30/00: Commerce - G06Q 30/02: Marketing; Price estimation or determination; Fundraising - G06Q 30/0235: constrained by time limit or expiration date - G06Q 30/0255: {based on user history} - G06Q 30/06: Buying, selling or leasing transactions - G06Q 40/00: Finance; Insurance; Tax strategies; Processing of corporate or income taxes - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) The method of claim 1, wherein the particular aspect is associated with a single attribute. ### Claim 4 (depends on 3) 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. ### Claim 5 (depends on 1) The method of claim 1, wherein the particular aspect is associated with a combination of two or more attributes. ### Claim 6 (depends on 1) The method of claim 1, wherein the partitioning strategy involves grouping aspects values based on a loss of predictive accuracy measure. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) 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. ### Claim 9 (depends on 1) 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. ### Claim 10 (depends on 1) 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. ### Claim 11 (depends on 1) 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. ### Claim 12 (depends on 11) 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. ### Claim 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. ### Claim 14 (depends on 13) 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. ### Claim 15 (depends on 13) 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. ### Claim 16 (depends on 13) The computer readable storage medium of claim 13, wherein the partitioning strategy involves producing bins that satisfy a prescribed predictive accuracy objective. ### Claim 17 (depends on 16) 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. ### Claim 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. ### Claim 19 (depends on 18) 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. ### Claim 20 (depends on 18) 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.