[0135] FIG. 18 is a flow diagram illustrating one exemplary implementation of blocks 1710-1720 of FIG. 17. Initially, a confidence interval relating to the odds of a good ad or bad ad may be determined (act 1800). Using a confidence interval technique enables more accurate and stable estimates when ad/query features k having lesser amounts of historical data are used. In one implementation, the confidence interval includes a lower value L.sub.i and an upper value U.sub.i and is based on the number of ad selections (n.sub.i) (e.g., a current value in “total number of ad selections” 1620 in data structure 1600 for ad/query feature k.sub.i) and total goodness/badness (j.sub.i) observed for the selected ad/query feature (e.g., a current total “good” predictive value 1630 or total “bad” predictive value 1640 in data structure 1600 for ad/query feature k.sub.i). For example, the confidence interval may be an 80% confidence interval [L.sub.i,U.sub.i] calculated in a conventional manner based on the number of ad selections (e.g., a current value in “total number of ad selections” 1620 in data structure 1600 for ad/query feature k.sub.i) and total goodness or badness observed (e.g., a current total “good” predictive value 1630 or total “bad” predictive value 1640 in data structure 1600 for ad/query feature k.sub.i). Following confidence interval calculation, it may then be determined whether the average self-excluding probability (P.sub.i(avg)) falls within the interval (act 1810). If so, it may be determined that the selected ad/query feature (k.sub.i) has no effect on the odds of a good ad or bad ad and its model parameter (m.sub.i) may be set to 1, effectively removing it from the estimated odds calculation (act 1820). However, if it is determined that P.sub.i(avg) falls outside of the confidence interval, then the model parameter (m.sub.i) for the selected ad/query feature k.sub.i may be set to the minimum adjustment necessary to bring the average self-excluding probability (P.sub.i(avg)) into the confidence interval (act 1830). This calculation may be expressed mathematically as: m.sub.i=[L.sub.i(1-P.sub.i(avg)))]/[P.sub.i(avg)(1-L.sub.i)]
[0136] Returning now to FIG. 17, once the model parameter m.sub.i for the selected ad/query feature k.sub.i is calculated, it may be determined whether additional ad/query features (e.g., of ad/query features 1610-1 through 1610-N of FIG. 16) remain to be processed (i.e., whether k.sub.i<k.sub.m, where m equals the total number of ad/query features in data structure 1600) (act 1730). If additional ad/query features remain to be processed, the counter variable i may be incremented (act 1740) and the process may return to act 1700 to process the next ad/query feature k.sub.i. Once model parameters for all ad/query features have been calculated or modified, the odds of a good ad or bad ad may be estimated using the equation q=q.sub.0m.sub.1m.sub.2m.sub.3 . . . m.sub.m (act 1750). The estimated odds of a good ad (e.g., ODDS(good ad|ad query feature)) may be stored in a “good” ad odds entry 1650 of data structure 1600 that corresponds to the ad/query feature 1610. The estimated odds of a bad ad (e.g., ODDS(bad ad|ad/query feature)) may be stored in “bad” ad odds entry 1660 of data structure 1600 that corresponds to the ad/query feature 1610.
[0137] In one implementation consistent with principles of the invention, the odds prediction model may be trained by processing log data as it arrives and accumulating the statistics mentioned above (e.g., ad selections, total goodness or badness, self-including probabilities, etc.). As additional ad selections occur, the confidence intervals associated with each ad/query feature may shrink and the parameter estimates may become more accurate. In an additional implementation, training may be accelerated by reprocessing old log data. When reprocessing log data, the estimated odds of a good ad or bad ad may be recalculated using the latest parameter or odds multiplier values. This allows the prediction model to converge more quickly.
EXEMPLARY AD QUALITY PREDICTION PROCESS
[0138] FIG. 19 is a flowchart of an exemplary process for predicting the quality of advertisements according to an implementation consistent with the principles of the invention. As one skilled in the art will appreciate, the process exemplified by FIG. 19 can be implemented in software and stored on a computer-readable memory, such as main memory 430, ROM 440, or storage device 450 of servers 320 or 330 or client 310, as appropriate.
[0139] The exemplary process may begin with the receipt of a search query from a user (block 1900). The user may issue the search query to server 320 for execution by search engine system 325. A set of ads that match the received search query may be obtained by search engine system 325 (block 1910). Search engine system 325 may execute a search, based on the received search query, to ascertain the set of ads, and other documents, that match the search query. For each ad of the set of ads, every ad/query feature that corresponds to the received search query and the ad may be determined (block 1920). The ad/query features for each search query and ad pair may include include an identifier associated with the advertiser (e.g., a visible uniform resource locator (URL) of the advertiser), a keyword that the ad targets, words in the search query issued by the user that ad did not target, and/or a word in the search query issued by the user that the advertisement did not target but which is similar to a word targeted by the advertisement. Other types of ad or query features, not described above, may be used consistent with principles of the invention. For example, any of the above-described ad/query features observed in combination (e.g., a pairing of two ad/query features) may be used as a single ad query/feature.
[0140] For each ad of the set of ads, stored ODDS.sub.1 (e.g., ODDS (good ad|ad/query feature) 1650, ODDS (bad ad|ad/query feature) 1660), for every one of the determined ad/query features i, may be retrieved from data structure 1600 (block 1930). As shown in FIG. 20, data structure 1600 may be indexed with ad/query features 2000 that correspond to the search query and the ad to retrieve one or more ODDS.sub.i 2010 associated with each ad/query feature. For example, as shown in FIG. 16, a “good” ad odds value 1650 corresponding to each ad/query feature 1610 may be retrieved. As another example, as shown in FIG. 16, a “bad” ad odds value 1660 corresponding to each ad/query feature 1610 may be retrieved.
[0141] For each ad of the set of ads, the retrieved ODDS.sub.i for each ad/query feature i may be multiplied together (block 1940) to produce a total ODDS value (ODDS.sub.t): ODDS.sub.t=ODDS.sub.1*ODDS.sub.1*ODDS.sub.2*ODDS.sub.3* . . . Eqn. (6) For example, the “good” ad odds values 1650 for each ad/query feature may be multiplied together to produce a total good ad odds value ODDS.sub.t.sub.–.sub.GOOD AD. As another example, the “bad” ad odds values 1660 for each ad/query feature may be multiplied together to produce a total bad ad odds value ODDS.sub.t.sub.–BAD AD. As shown in FIG. 20, the ODDS 2010 retrieved from data structure 1600 may be multiplied together to produce a total odds value ODDS.sub.t 2020.
[0142] For each ad of the set of ads, a quality parameter that may include a probability that the ad is good (P.sub.GOOD AD) and/or that the ad is bad (P.sub.BAD AD) may be determined (block 1950): P.sub.GOOD AD=ODDS.sub.t.sub.–.sub.GOOD AD) Eqn. (7) P.sub.BAD AD=ODDS.sub.–.sub.BAD AD/(1+ODDS.sub.t.sub.–.sub.BAD AD) Eqn. (8) As shown in FIG. 20, the total odds value ODDS.sub.t 1820, and equations (7) or (8) may be used to derive a quality parameter (P) 2030.
EXEMPLARY AD FILTERING, RANKING AND PROMOTION PROCESS
[0143] FIG. 21 is a flowchart of an exemplary process for filtering, ranking and/or promoting advertisements according to an implementation consistent with principles of the invention. As one skilled in the art will appreciate, the process exemplified by FIG. 21 can be implemented in software and stored on a computer-readable memory, such as main memory 430, ROM 440, or storage device 450 of servers 320 or 330 or client 310, as appropriate.
[0144] The exemplary process may begin with the determination of ads that are relevant to a search query (block 2100). A user may enter a search query in a search query document and the content of ads hosted by an ad publisher may be compared with the entered search query to determine which ads are relevant to the search query. For example, ads having content with the term “SUV” may be considered relevant to the search query “SUV.”
[0145] One or more quality parameters associated with the relevant ads may be obtained (block 2110). The quality parameter(s) may include, for example, the quality parameter(s) determined in block 1950 above. The quality parameter(s) may, however, include any other type of parameter that is indicative of a quality of an advertisement, other than a click-through-rate (CTR).
[0146] The ads determined to be relevant may be filtered based on the obtained quality parameter(s) (optional block 2120). Filtering may disable (e.g., de-select) selected ones of the relevant ads so that they will not be provided (i.e., not shown) to the user that issued the search query, or that accessed the content of the particular document or site. The relevant ads may be filtered based on the one or more quality parameters obtained in block 2110 above, or based on any other type of ad quality parameter, in addition to a CTR. The relevant ads may be filtered based on a functional combination of the obtained quality parameter(s) and other parameters (e.g., CTR). For example, the obtained quality parameter(s) (QP) may be multiplied by CTR (i.e., QP*CTR) to filter the relevant ads. CTR measures the fraction of ad impressions that result in ad clicks. For example, if one out of 100 ad impressions results in an ad click, then the CTR of that advertisement is 1/100, or 1%. CTR may be estimated, as described in co-pending U.S. application Ser. No. ______ (Attorney Docket No. 0026-0145), entitled “Accurately Estimating Advertisement Performance” and incorporated by reference herein. In one implementation, the quality parameter QP may include P.sub.GOOD AD determined in block 1950 above.
[0147] As an example, the functional combination P.sub.GOOD AD*CTR may be used as a disabling rule. For example, if P.sub.GOOD AD*CTR is low (e.g., less than a threshold value), then the ad will be disabled and, thus, not provided to the user. FIG. 22 illustrates an example of the filtering of multiple ads 2200-1 through 2200-N consistent with an aspect of the invention. For each ad 2200, a value 2210 for P.sub.GOOD AD*CTR may be determined and compared to a threshold value (T) 2220. Ads having values 2210 less than the threshold T 2220 may be disabled 2230, and ads having values 2210 equal to or greater than the threshold T 2220 may be provided 2240 (e.g., shown) to the user.