US 8,275,656 B2Granted

Maximum likelihood estimation under a covariance constraint for predictive modeling

AssigneeYahoo! Inc.

InventorOzgur Cetin

Life of this patent

Estimating the term…

Loading patent…

Abstract

Embodiments employ a maximum likelihood estimation (MLE) under a covariance matrix floor constraint to predict missing data from observed data. An MLE solution is obtained for approximately Gaussian distributions under the constraint that the covariance matrix is greater than or equal to a positive-definite matrix. In one embodiment, an offline model estimation is performed using an expectation-maximization (EM) approach to estimate various statistical parameters based on observed data. Then, in an online approach, parameters for various missing CTR data may be predicted based on the offline estimated statistical parameters. A non-limiting, non-exhaustive example using the constrained MLE approach is described for predicting missing click-through rate data useable in selecting an advertisement to display with a search query result.

Claims14

Dependent claims

A network device, comprising:

a transceiver to send and receive data over the network;
and
a processor that is operative to perform actions, including:
receiving a plurality of observed click-through rate data associated with a plurality of related advertisements;
receiving a related new advertisement for placement, the related new advertisement missing observed click-through rate data;
estimating statistical parameters about the plurality of related advertisements using the plurality of observed click-through rate data associated with the plurality of related advertisements, wherein the estimation of the statistical parameters is subject to a covariance constraint such that a lower bound for each covariance is a symmetric, positive-definite matrix;
using the estimated statistical parameters, predicting a statistical parameter for the missing click-through rate data for the related new advertisement;
receiving a search query;
and
employing the estimated and predicted statistical parameters to select an advertisement from the plurality of related advertisements and the related new advertisement;
and
providing a response to the search query with the selected advertisement.

9 more elements

A computer-readable storage device having computer-executable instructions stored thereon, the computer-executable instructions when installed onto a computing device enable the computing device to perform actions, comprising:

receiving a plurality of observed click-through rate data associated with a plurality of related advertisements;
receiving a related new advertisement, the related new advertisement missing observed click-through rate data;
generating a vector based on the plurality of observed click-through rate data, wherein the vector comprises components, including a component representing missing click-through rate data for the related new advertisement;
estimating statistical parameters about at least the observed click-through rate data using the generated vector, wherein the estimation of the statistical parameters is subject to a covariance constraint such that a lower bound for each covariance is a symmetric, positive-definite matrix;
using the estimated statistical parameters, predicting a statistical parameter for the missing click-through rate data for the related new advertisement;
receiving a search query;
and
employing the estimated and predicted statistical parameters to select an advertisement from the plurality of related advertisements and the new advertisement;
and
providing a response to the search query with the selected advertisement.

7 more elements

Dependencies are inferred from the claim text.