Systems and methods for profiling conversions of online events

Embodiments are directed at determining a conversion rate and a latency distribution for an online campaign. The conversion rate indicates a ratio of an overall number of converted impressions to the number of previously provided impressions. The converted impressions are a subset of the set of previously provided impressions. One method includes receiving conversions from the campaign and determining an observed latency for the conversions. Each conversion is uniquely associated with one of the converted impressions. The observed latencies are based on a temporal difference between the conversion and the associated converted impression. The method simultaneously determines each of the conversion rate and parameters of the latency distribution. The latency distribution indicates a temporal distribution of the observed latencies. Determining the conversion rate and parameters of the distribution is based on employing a constraint or relationship between the conversion rate and the distribution and an interior point or Newton-Raphson method.

TECHNICAL FIELD

The present disclosure relates generally to online advertising. More specifically, and without limitation, the present disclosure relates to systems and methods for determining a profile for conversions of online events.

BACKGROUND

Online marketers are interested in providing impressions, such as messages, advertisements, and/or other content, on websites to promote their products or services. Influenced by an impression, a user may take an action, such as purchasing one or more items or services associated with the impression. An impression is said to be converted when a user takes such an action and the action can be reasonably inferred to occur, at least somewhat, in response to the user being provided and viewing the impression.

Typically, only a fraction of provided impressions are ever converted. This fraction is estimated as a conversion rate. Furthermore, of the converted impressions, the temporal difference between providing the impression to the user and the user taking action to convert the impression may vary significantly from impression to impression. This temporal difference for a particular converted impression is referred to as the conversion's latency. Similar to other random variables, converted impressions may be distributed within a latency distribution.

When controlling an online campaign, online marketers may desire to track various campaign performance metrics, such as cost per impression, cost per action, cost per click, cost per conversion, and the like. More specifically, when contemplating the rate and cost of providing impressions, online marketers are interested in modeling the conversion profiles (i.e., a conversion rate and a latency distribution) for the campaign. That is, when deciding whether to provide an impression to a user, online marketers are interested in tracking the proportion of provided impressions that will be converted and, the temporal profile of the conversions.

SUMMARY

In accordance with various embodiments of the present disclosure, a computer-implemented method is provided for determining a conversion profile for an online campaign. The conversion profile may include a conversion rate and a latency distribution for the campaign. The conversion rate for the campaign may indicate a ratio of a size (e.g., a number or volume) of overall converted impressions to a size of a set of previously provided impressions. In some embodiments, the conversion rate indicates the ratio of the size of expected converted impressions to a size of a set of previously provided impressions. The converted impressions are a subset of the set of previously provided impressions. The method may include receiving conversions from the campaign and determining an observed latency for the conversions. Each conversion is uniquely associated with one of the converted impressions. The observed latencies are based on a temporal difference between the conversion and the associated converted impression. That is, the observed latency is the difference in the time that the conversion occurred to the time that the impression was provided to a user.

The method simultaneously determines each of the conversion rate and one or more parameters of the latency distribution. The latency distribution indicates a temporal distribution of the observed latencies. In some embodiments, the conversions are provided (e.g., uploaded) to a conversion module, such as conversion module216ofFIG. 2, after the conversions are observed. Thus, in these embodiments, the latency distribution incorporates both the uploaded and observed latencies of the conversions. Determining the conversion rate and the parameters of the latency distribution is based on at least one of the conversions, the set of previously provided impressions, the observed latencies, the converted impressions, and/or the parameters of the latency distribution. As discussed throughout, a constraint or relationship between the conversion rate and the latency distribution is employed to determine the conversion rate and the parameters of the latency distribution.

The method may further include generating and/or updating a correlation map between the conversions and the converted impressions. For at each conversion that was observed at least within a look-back window, the correlation map may indicate the associated converted impression and the observed latency. In some embodiments, the latency distribution is a Pareto distribution and the parameters of the latency distribution include at least a shape parameter and a scale parameter of the Pareto distribution.

In various embodiments, determining the conversion rate and the parameters of the latency distribution includes employing a maximum likelihood estimation (MLE) based on the observed latencies. The conversion rate and the parameters of the distribution maybe estimated independently.

The conversion rate may be based on a total number of observed conversions, a number of impressions that have been provided outside of a current look-back window, and a number of impressions that have been provided within the current look-back window. In some embodiments, an interior point method is iteratively employed. That is, the interior point method is employed to iteratively update values for the conversion rate and the parameters of the latency distribution based on previously determined values for the conversion rate and the parameters of the latency distribution. In other embodiments, a Newton-Raphson iterative method is employed to iteratively update the values for the conversion rate and the parameters of the latency distribution.

DETAILED DESCRIPTION OF THE EMBODIMENTS

The various embodiments herein are directed towards methods and systems for determining the conversion profiles for online events. More specifically, the embodiments are directed towards simultaneously and iteratively determining each of a conversion rate and a latency distribution for the conversions of online impressions. That is, the embodiments are directed towards the determination of the proportion of provided impressions that are converted and the statistical distribution that is most likely to be consistent with the observed latencies of the converted impressions.

Previous conventional approaches for modeling the conversion profile of a campaign have estimated a conversion rate or a latency distribution separately. However, as discussed below, conventional approaches have not simultaneously determined each of the conversion rate and the latency distribution, based on an explicit correlation (or relationship) between them, as the embodiments herein do. Furthermore, some of the conventional approaches have assumed unrealistic families of statistical distributions, whereas the embodiments herein are not specific to any particular statistical distribution. That is, the embodiments herein may be applied to any number of statistical distributions. Additionally, some conventional approaches fail to consider volatility in the volume (per unit time) of provided impressions, which may result in biased estimations of the conversion profile. The embodiments herein explicitly account for any variation in the impression volume, and thus do not result in biased determinations of the conversion profile.

In general, internet “advertisers” and/or “marketers” (hereinafter used interchangeably to refer to a party that pays to provide content via a website or other forum provided via a computer communication network) often create “online campaigns” (or simply “campaigns”) that include numerous content, such as advertisements designed to be placed on websites during a specified period of time. For example, a party, such as a marketer or advertiser, may design a “banner ad” or other such content associated with a product or service offered by the company. The party may wish to have the content placed on websites to promote the product or service.

Each instance that content is provided to a user may hereinafter be referred to as an “impression.” An impression may be associated with one or more items and/or services. For example, an impression may be advertising, or otherwise targeting an item or a service, as promoted by the marketer. The number of impressions provided per unit time in a campaign may be referred to as the “impression volume” of the campaign. As used herein, and as discussed below, the terms “online market,” “marketplace,” “market,” “advertising networks,” or “marketing networks” are used interchangeably to refer to an environment, ecosystem, or platform where advertisers or marketers provide impressions to users.

Once provided to a user, the user may take a particular “action,” in response to viewing or listening to the provided impression. Such actions include, but are not otherwise limited to completing an online form to request additional information with regard to the product or service associated with a particular impression. Another exemplary action includes when the user purchases a product or service associated with a particular impression. When the user performs such an action, and when the action can be reasonably inferred to have occurred, at least somewhat, in response to the user being provided and viewing the impression, the impression is said to be “converted.” The terms “conversion” or “conversion event” may be used interchangeably to refer to the user performing one or more predetermined actions, in response to being provided an impression. Such predetermined actions may include, but are not otherwise limited to a click, a purchase, a request for additional information, viewing and/or listening to content associated with the impression, or the like.

Within an online campaign, the ratio of the number of impressions that are converted to the total number of impressions that are provided is referred to the “conversion rate.” For instance, when reviewing campaign data offline, if 1000 impressions are provided to users in an online campaign and 100 conversions are observed, the conversion rate of the campaign may be estimated at 10%. The conversion rate may be related to the cumulative distribution function (cdf) of the latency distribution, as shown in equation430ofFIG. 4B. The number of conversions observed per unit time in a campaign may be referred to as the “conversion volume” of the campaign.

The time between providing the impression and the occurrence of the conversion may be referred to as the “latency” of the conversion. The latency of conversions typically varies, as a random variable, from conversion to conversion. For instance, of the fraction of impressions that are converted, some impressions may be converted in a short duration of time, while other impressions are converted within a longer duration of time. In the various embodiments, the conversions of a campaign may be temporally distributed within a “latency distribution.” Accordingly, the latency of a conversion may be a random variable characterized by a statistical distribution.

At least due to temporal “smearing-out” of conversions, the determination of the conversion rate is more involved than simply the ratio of the conversion volume to the impression volume. For instance, volatility in the conversion volume does not perfectly correlate with volatility in the impression volume due to the temporal distribution of latencies of the conversions. Thus, conventional approaches for estimating a conversion rate based on such a ratio may result in biased estimations.

As discussed throughout, the conversion rate and the latency distribution are correlated, related, and/or coupled. Although various previously available conventional approaches have estimated at least one of the conversion rate or the latency distribution, such conventional approaches determine them separately and do not consider the relationship (or correlation) between them. When the determination is considered separately, as conventional approaches do, the determination of the conversion rate and the determination of the latency distribution may be significantly inaccurate due to not considering the relationship between them. In contrast to such conventional approaches, the various embodiments herein explicitly account for the relationship between the conversion rate and the latency distribution. That is, the determined value of the conversion rate is constrained by the determined latency distribution, and vice-versa.

As discussed below, conventional approaches that separately consider an estimation of the conversion rate and the latency distribution may significantly decrease a marketer's ability to control a campaign in a manner that is consistent with a desired goal, such as a desired cost per impression, cost per click, cost per conversion, or the like. That is, a marketer, employing a conventional approach, may ineffectively deploy financial resources and/or may experience loss of important opportunities to impress users and realize rewards associated with the impressions.

Other previous conventional approaches have employed Bayesian frameworks and/or assumed that the latency distribution is readily modeled via a Gamma distribution. The assumption of a Gamma distribution may be specifically problematic due to the “long tail” (or “heavy tail”) of the actual latency distribution. In further contrast to these conventional approaches, the various embodiments are readily adaptable to any number of different statistical distributions, i.e., the embodiments do not assume a particular statistical distribution, such as a Gamma distribution, to determine a latency distribution. Furthermore, the embodiments do not assume a Bayesian framework.

Furthermore, some embodiments may employ an explicit constraint (or relationship) between the conversion ratio and the latency distribution in service of a Lagrange multiplier method within the maximal likelihood estimation (MLE) framework to determine the conversion rate and the latency distribution. During an iterative and simultaneous determination of each of the conversion rate and the latency distribution, each of a current estimate of the conversion rate and a current estimate of the latency distribution is employed to update each of the estimate of the conversion rate and the estimate of the latency distribution. Such iterative updates to the estimates are continued until convergence is achieved. Thus, the relationship between the conversion rate and the latency distribution is explicitly considered in the various embodiments; and the current estimations for each are used as feedback to iteratively update the estimations. Although the embodiments may be applied to any number of statistical distributions, some embodiments assume a Pareto distribution.

Exemplary Advertising System and Environment

FIG. 1depicts an illustrative advertising system100, in accordance with embodiments of the present disclosure. As shown inFIG. 1, advertising system100may include one or more advertisers102, publishers104, ad servers106, and campaign control systems108, that are in communication with one another through a network, such as the Internet110. The number and orientation of the computing components inFIG. 1is provided for purposes of illustration only. Any other number and orientation of components is possible. For example, one or more of advertisers102, publishers104, ad servers106, and campaign control systems108may be combined or co-located and/or communicate directly with one another, instead of over Internet110. The components ofFIG. 1may include any type or configuration of computers and/or servers, such as, for example, a server cluster, a server farm, load balancing servers, distributed servers, etc. In addition, each component may include one or more processors, memories or other data storage devices (i.e., computer-readable storage media), such as hard drives, NOR or NAND flash memory devices, or Read Only Memory (ROM) devices, etc., communications devices, and/or other types of computing elements.

Advertisers102represent computing components associated with entities having online advertisements (e.g., banner ads, pop-ups, etc.) that the entities desire to deliver to online consumers. Advertisers102may interact with publishers104, ad servers106, and/or campaign control systems108through the Internet110. Thus, advertisers102may be able to communicate advertising information, such as ad information, targeting information, consumer information, budget information, bidding information, etc., to other entities in system100.

Publishers104represent computing components associated with entities having inventories of available online advertising space. For example, publishers104may include computing components associated with online content providers, search engines, e-mail programs, web-based applications, or any computing component or program having online user traffic. Publishers104may interact with advertisers102, ad servers106, and/or campaign control systems108via the Internet110. Thus, publishers104may be able to communicate inventory information, such as site information, demographic information, cost information, etc., to other computing components in system100.

Ad servers106may include servers or clusters of servers configured to process advertising information from advertisers102and/or inventory information from publishers104, either directly or indirectly. In certain embodiments, ad servers106may be remote web servers that receive advertising information from advertisers102and serve ads to be placed by publishers104. Ad servers106may be configured to serve ads across various domains of publishers104, for example, based on advertising information provided by advertisers102. Ad servers106may also be configured to serve ads based on contextual targeting of web sites, search results, and/or user profile information. In some embodiments, ad servers106may be configured to serve ads based on control signals generated by campaign control systems108.

Various embodiments of campaign control systems, such as but not limited to campaign control systems108, are discussed in conjunction with at least campaign control system208ofFIG. 2. Campaign control systems108may include computing systems configured to receive information from computing components in system100, process the information, and generate advertising control signals to be sent to other computing components in system100, according to the illustrative methods described herein. Campaign control systems108may include any type or combination of computing systems, such as clustered computing machines and/or servers, including virtual computing machines and/or virtual servers. Campaign control systems108may include, for example, implementations of Adlearn Open Platforms (AOP) control systems offered by America Online (AOL) of New York, N.Y. In some embodiments, campaign control systems108may include an assembly of hardware, including a memory112, a central processing unit (“CPU”), and/or a user interface116. Memory112may include any type of RAM or ROM embodied in a physical, computer-readable storage medium, such as magnetic storage including floppy disk, hard disk, or magnetic tape; semiconductor storage such as solid state disk (SSD) or flash memory; optical disc storage; or magneto-optical disc storage. CPU114may include one or more processors for processing data according to instructions stored in the memory, for example to perform the methods and processes discussed in detail herein. The functions of the processor may be provided by a single dedicated processor or by a plurality of processors. Moreover, the processor may include, without limitation, digital signal processor (DSP) hardware, or any other hardware capable of executing software. User interface116may include any type or combination of input/output devices, such as a display monitor, graphical user interface, touch-screen or pad, keyboard, and/or mouse. In other embodiments, campaign control systems108may include virtual representations of hardware operating, for example, on a virtualization server.

Exemplary Campaign Control System

FIG. 2depicts an illustrative online advertising or marketing environment200for determining a conversion profile of an online advertising or marketing campaign202operating in an online advertiser or marketing network204. Advertising network204may include a network or collection of one or more advertisers102, one or more publishers104, ad servers106, campaign control systems108, or other components of system100ofFIG. 1. Elements of advertising network204may operate to receive impression requests associated with one or more advertising inventories, e.g., from publishers104such as websites or other computing components with an inventory of online marketing space. Advertising network204may also group impression requests for various advertising campaigns, e.g., according to impressions to be “targeted” based on a combination of attributes defined by the marketing requests. Advertising network204may also accept bids (e.g., from one or more campaign control systems208) on the impression requests and process the bids to serve ads to the impression requests.

Any number or type of advertising campaigns202may be operated within advertising network204, across various ad servers and domains associated with the Internet. Online advertising environment200may be implemented by one or more of the advertisers102, publishers104, ad servers106, and/or campaign control systems108described inFIG. 1. For example, online advertiser environment200may represent the interaction of one or more campaign control systems208with one or more computing components in system100.

In one embodiment, online advertising environment200may include one or more instances of campaign control system208. Campaign control system208may include, or be similar to at least one of campaign control systems108ofFIG. 1. Campaign control system208may comprise computers or servers connected to the Internet. Such computers or servers may be configured as described with respect to campaign control system108, as depicted byFIG. 1, or in any other suitable configuration. Alternatively, campaign control system208may be implemented by software modules executed by CPUs114of campaign control system208. Campaign control system208may be embodied entirely in hardware, entirely in software, or in any combination of hardware and software implemented across any number of computing devices.

Campaign control system208may be provided with a set of configuration parameters210, which may be adjustably set by a user. For instance, the set of configuration parameters may include, but are not otherwise limited to a look-back window length (L), a data-sampling interval (Δt), an offset in latency (δ), one or more statistical distribution scale parameters (e.g., Tmin), one or more initial statistical distribution parameters (e.g., θ0), one or more convergence parameters (e.g., ε), and the like. The set of configuration parameters210may be implemented by one or more campaign control systems, including but not limited to campaign control system208.

In one embodiment, campaign control system208may be a control system configured to, in response to receiving an impression request, provide impressions to campaign202and receive conversions from campaign202. More specifically, impression module214may be enabled to receive impression requests from campaign202, and in response, provide impressions to campaign202. In various embodiments, impression module214provides campaign202impressions at an impression volume based on at least one of a determined conversion rate, a determined latency distribution, and/or an impression request. Conversion module216is enabled to receive conversions from campaign202. Conversion module216and/or profile module218is enabled to generate a correlation map between the provided impressions and the received conversions. Furthermore, conversion module216and/or profile module218is enabled to generate/update various signals based on the provided impressions, received conversions, correlation map, and the configuration parameters. Profile module218is enabled to iteratively determine a latency distribution and a conversion rate based on the provided impressions, the received conversions, the correlation map, and one or more of configuration parameters210.

Exemplary Impression Volumes and Exemplary Conversion Volumes

FIG. 3Adepicts historical latency distributions for various real online campaigns. Histogram310ofFIG. 3Ashows the latency distribution (in hours) for the conversions within a first campaign. Likewise, histogram320shows the latency distribution for the conversions within a second campaign. Histogram330shows the latency distribution for the conversions within a third campaign. As shown inFIG. 3A, the nature of a latency distribution typically varies with the tactics and strategies employed, as well as the nature of the provided impressions and the conversion actions associated with the impressions and the campaign.

For instance, a latency distribution for a campaign that is providing impressions where the conversion action is a click, may have a lower mean latency, i.e., if the user is going to convert the impression via a click, the conversion may typically occur within minutes to hours. For campaigns that are interested in providing impressions where the conversion action is a as purchase of a relatively high-cost item, the conversion may occur within hours to days after being provided the impression. For instance, the latency distribution of the first campaign (histogram310) has a lower mean latency than the latency distribution of the second campaign (histogram320). The latency distribution of other campaigns, such as the third campaign (histogram330) may include multimodal structures.

FIG. 3Bdepicts an exemplary impression volume time dependency and an exemplary conversion volume time dependency for an online campaign, in accordance with embodiments of the present disclosure. Plot340shows the impression volume, as a function of time, for an online campaign that provides impressions for about 30 days (˜720 hours). Plot350shows the corresponding conversion volume for the same campaign. The hashed vertical lines342and352(in plots340and350respectively) reflect the t˜720 hour mark where the impression volume is terminated and/or reduced, i.e., the campaign ceases to provide impressions at t˜720 hours.

Plot340shows that the exemplary (but non-limiting) campaign approximately periodically varies the impression volume, with a period of ˜24 hour. That is, plot340shows significant temporal volatility in the impression volume. An initial transient period of the campaign occurs between t˜0 hours and t˜100 hours (demarcated by the hashed vertical line356in plot350). During the initial transient period, the conversion volume increases due to the latency distribution of initially provided impressions. In conventional approaches for determining a conversion rate and/or a latency distribution and when a marketer is observing the conversion volume during such an initial transient period (e.g., at t˜25 hours), the online marketer may not be able to discriminate whether the low conversion volume is due to a low conversion rate or a relatively long mean latency, i.e., a mean latency >25 hours.

A terminal transient period of the campaign occurs between t˜720 hours and t˜820 hours (demarcated between vertical hashed line352and vertical solid line354of plot350). That is, a terminal transient period begins once providing the impressions is terminated. During the terminal transient period, the conversion volume decreases due to the latency of the impressions provided near the end of the campaign. As shown in plot350, beyond t˜820 hours, very few conversions are observed. Thus, for this exemplary campaign, most of the conversions have a latency of less than 100 hours. Accordingly, as discussed below, a look-back window length of ˜100 hours may be appropriate for this campaign.

As shown in plot350, between the initial and terminal transient periods (i.e., the “steady-state” portion of the campaign), the variation in the conversion volume is primarily affected by the temporal volatility in the impression volume and the “smearing-out” of conversions due to the conversion latency distribution. The order of magnitude of the conversion rate may be estimated by observing plots340and350during the “steady-state” portion of the campaign as approximately (˜10{circumflex over ( )}2/10{circumflex over ( )}5) or ˜0.1%. However, in contrast to the various embodiments herein, such an estimation may be biased due to the volatility in the impression volume and the latency distribution. Furthermore, during the transient periods of the campaign, the ratio of the conversion volume to the impression volume cannot be employed to estimate the conversion rate.

That is, in conventional campaign approaches for determining conversion rates and a latency distribution, the marketer may not know whether the relatively low conversion volume is due to a low conversion rate or a long latency during the transient periods. Furthermore, the marketer may not be able to determine whether an observation is within the initial transient period, or the “steady-state” portion of the online campaign until a significant amount of time has passed in the campaign.

When using conventional approaches, by the time that a marketer is able to at least estimate an approximate conversion rate and mean latency (via the slope of the conversion volume in the initial transient period), significant financial resources may have been ineffectively deployed, and/or a significant number of opportunities to capitalize may have been lost. For instance, if a marketer assumes that the low conversion volume is due to a low conversion rate, the marketer may increase the impression volume to drive up the conversion volume. However, if the conversions are distributed within a broad conversion distribution, the marketer may be wasting financial resources by increasing the impression volume. Conversely, if the marketer assumes that the low conversion volume is due to a high mean latency and assumes the conversion volume will increase in the future due to the long latency of conversions, the marketer may lose out in opportunities to provide impressions to users that would otherwise be likely to convert the impressions. In contrast to such conventional approaches, the embodiments herein explicitly employ a constraints between the conversion rate and the latency distribution, while monitoring variances in the impression volume and the conversion volume to simultaneously determine the conversion rate and the latency distribution.

Determining the Conversion Rate and the Latency Distribution of an Online Campaign

FIG. 4Adepicts an illustrative process flow for determining the conversion rate and the latency distribution of an online campaign, in accordance with various embodiments of the present disclosure. Various campaign control systems, such as but not limited to campaign control system108ofFIG. 1and/or campaign control system208ofFIG. 2may employ, implement, execute, and/or carry out at least a portion of the process400ofFIG. 4.

Process400begins, after a start block, at block402where one or more configuration parameters are received. For instance, configuration parameters210ofFIG. 2may be received by at least one of impression module214, conversion module216, or profile module218of campaign control system208. Such received configuration parameters may include at least one of, but are not otherwise limited to a look-back window length (L), a data-sampling interval (Δt), an offset in latency (δ), one or more initial statistical distribution scale parameters (e.g., Tmin), one or more initial statistical distribution parameters (e.g., θ0), one or more convergence parameters (e.g., e), and the like. The values for the configuration parameters may be provided by a user. Such configuration parameters received at block402are discussed throughout.

At block404, provided impressions to a campaign are received. For instance, impression module214may provide campaign202one or more impressions, in response to receiving an impression request. In various embodiments, the time evolution of process400, as well as other processes discussed herein may be discretized via a received configuration parameter such as a data-sampling interval (Δt). In some embodiments, the data-sampling interval is approximately 15 mins. The discretized time slices (or time samples) of the various processes may be indexed via time index k=0, 1, 2, 3, . . . . At the kth time slice, t=k·Δt. Thus, each iteration around the loop of process400may correspond to a particular time slice indexed via the time index k.

At block404(and/or block412), an impression volume (n1(k)) of impressions may be provided to a campaign, where n1(k) is the number of impressions provided between the (k−1)th and kth time slices, i.e., within the time interval: [k−1, k]Δt. Plot340ofFIG. 3Bshows a plot of n1(k) for each time slice between the time interval: [0, 720 hours]. In the various embodiment, an impression that is provided in between the time interval [k−1, k]Δt may be referred to as “sourced” in the kth time slice.

At block406, zero or more conversions are received. For instance, conversion module216may receive zero or more conversions from campaign202. More specifically, a conversion volume of conversions is received at each time slice at block406. Plot350ofFIG. 3Bshows a plot the received conversion volume for each time slice between the time interval [0, 720 hours]. A conversion received in the time interval [k−1, k]Δt may be referred to as observed at or during the kth time slice.

At block408, a correlation map between the provided impressions and the received conversions is generated and/or updated. A correlation map may be a correlation table, list, or the like. The correlation map be encoded in structure or non-structured data. Profile module218or another component of campaign control system208such as but not limited to conversion module216, may be enabled to generate and/or update the correlation map. More specifically, at block408, for at least a portion of the conversions received (or observed) at the kth time slice, a correspondence is generated with a previously provided impression. That is, the previously provided impression that is most likely to have resulted in the conversion is identified and associated, correlated, and/or paired with the received conversion.

Thus, the correlation map indicates a unique correspondence, association, and/or pairing between at least a portion of the conversions received at block406and one of the impressions previously provided via block404. That is, a received conversion may be mapped to a previously provided impression. More specifically, for at least a portion of the received conversions, the correlation map may include one or more entries that indicates the time slice associated with the observation (or receiving) of the conversion, the associated/corresponding impression, and the time slice associated with the sourcing (or providing) of the associated/corresponding impression. The correlation map may include an indication of a latency (τ) for at least a portion of the conversions. The latency may be determined via the temporal difference between the time slice associated with the observation of the conversion and the time slice associated with the sourcing of the impression associated with the conversion. As discussed throughout, the conversions may be indexed via the index i, such that τirefers to the latency of the ith observed conversion. Thus, the correlation map may index the time slices via a first index (e.g., k) and index the conversions via a second index (e.g., i). In at least one embodiment, the correlation map includes an entry that indicates the time slice associated with the sourcing of each impression. Note that only a fraction of the provided impressions are associated with a conversion because the conversion rate of a campaign is typically less than 1.0.

In the various embodiments, a look-back window is employed. The look-back window length (L) may be a configuration parameter received at block402. The look-back window length terminates the search space of previously provided impressions to associate with each conversion. Thus, as discussed throughout, an appropriately configured look-back window may enable a computationally efficient determination of the conversion rate and the latency distribution. A look-back window effectively cuts off a relatively insignificant tail-portion of the latency distribution. For the relatively few conversions included in the tail-portion (as defined by L) of a latency distribution, the correlation map may not include associated entries. Thus, the tail-portion of a latency distribution may be defined as Δt·k>L. In some embodiments, conversions with a latency greater than the L are observed and included in the correlation map, but are not associated with a previous impression. Histograms of latency distributions (such as histograms110,120, and130ofFIG. 3B) may include

LΔ⁢T+1
discrete bins. A visual inspection of plot350ofFIG. 3Bshows that L˜100 (the temporal difference between vertical lines352and354) is an appropriate configuration for the look-back window of the campaign plotted inFIG. 3B.

At block410, the correlation map is employed to generate and/or update one or more signals based on the provided impressions, received conversions, the correlation map, and/or one or more of the configuration parameters. At least one of the conversion module216of the profile module218of a campaign control system208may be enabled to generate/update various signals. The generated/updated signals may include one or more input signals. The various signals discussed herein may be time-dependent signals that are temporally discretized via the time index k. One such input signal includes n1(k), as discussed above. At block410, another signal (nE(k)) may be determined via the correlation map, where nE(k) is the total number of conversions that are associated/correlated with an impression sourced at the kth time slice. Based on nE(k) and the correlation map, signal (nE(k1, k2)) is determined, where nE(k1, k2) is the number of conversions observed at the k2time slice and associated with an impression sourced at the k1time slice (k1≤k2).

An uncensored conversion input signal (nUE(k)) may be determined/update at block410based on nE(k1, k2) and the correlation map. The uncensored conversion input signal may encode an uncensored conversion vector (of dimensionality

LΔ⁢⁢t.
Because the uncensored conversion input signal encodes a vector, the uncensored conversion input signal (as well as other signals discussed herein) may be referred to a vector signals.

In some embodiments, signal (nEtot(k1, k2)) may be generated and/or updated at block410, where nEtot(k1, k2) encodes the total number of conversions sourced to the time interval [k1−1, k1]Δt and observed until k2time slice, i.e., nEtot(k1, k2)=Σk′=k1k2nE(k1, k′). For various embodiments, signal (N(k)) may be generated and/or updated at block410, where N(k) encodes the total number of conversions observed between the time interval [0, k·Δt], i.e., N(k)=Σk1=0kΣk2=k1knE(k1, k2)Σk′=0k2nEtot(k′, k). In at least one embodiment, some of the signals generated/updated at block410, such as but not limited to the signal N(k), may be internal states of profile module218. Other signals representing internal states of a profile module, such as but not limited to N(k), Φ(k), Ψ(k), ηi(k), α(k), and β(k), as discussed below may be generated/updated via a state-machine component of the profile module, such as but not limited to state-machine component520of profile module518ofFIG. 5A. Pseudo-code shown inFIG. 5Bshows one exemplary embodiment of a calculation of such internal states. In various embodiments, at least one or more of the signals discussed in conjunction with block410is generated and/or updated at block412.

At block412, the latency distribution and the conversion rate (p0(k)) for the campaign are iteratively and simultaneously determined. In various embodiments, the determination of the latency distribution and the conversion rate is based on one or more signals discussed in conjunction with block410, the correlation map, and/or one or more of the configuration parameters. The determination of the latency distribution and the conversion rate may be based on the provided impressions and/or the received conversions. In various embodiments, a parameterized statistical distribution is employed to model the latency distribution of the campaign. Thus, determining the latency distribution is equivalent to determining one or more distribution parameters of the statistical distribution. In some embodiments, a parameterized Pareto distribution is employed to model the latency distribution of the campaign. However, it should be understood that other embodiments are not so limited. That is, the various embodiments may employ any number of other parameterized statistical distributions, using the equivalent and/or similar methodologies as those discussed below.

A probability density function (pdf) of a parameterized truncated Pareto distribution is represented as

The distribution parameters include a scale parameter (Tmin), which is the minimum observational value of a latency (τ), a maximum observational value (Tmax) of a latency, and a shape parameter (θ), where 0<Tmin≤τ≤Tmax, θ>0. The cumulative distribution function (cdf) of the parameterized truncated Pareto distribution is represented as

In some of the various embodiments Tminis updated to be the minimum observed latency but in one embodiment Tmin=Δt. In some of the various embodiments, Tmax=L+Δt, due to the look-back window. In at least one embodiment, Tminis a configuration parameter, such as one of the configuration parameters included in configuration parameters210ofFIG. 2. In the non-limiting embodiments employing the above truncated Pareto distribution, determining the latency distribution is equivalent to determining θ(k). For each time slice, a maximum likelihood estimation (MLE) approach is employed to simultaneously determine p0(k) and θ(k). An MLE provides a method for determining optimized values of parameters that parameterize a probability distribution based on observations of the random variables of the probability distribution. In one non-limiting embodiment, a vector of observations ({circumflex over (τ)}) of a random variable is assumed to be distributed via a pdf (Pr(τ|{circumflex over (θ)})) parameterized by a vector of parameters ({circumflex over (θ)}). Note that Pr(τ|{circumflex over (θ)}) represents any number of parameterized pdfs, such as but not limited to the Pareto pdf ƒ(τ|θ). An MLE enables the determination of the most-likely (or optimized) values for each of the parameters based on the observations of the random variable via the optimization of the following expression,

arg⁢⁢maxθ^⁢∏i⁢Pr(τi|θ^),
where the index i represents the components of the vector of observations. That is, τirepresents the latency for the ith observed conversion (included in the correlation map). In the various embodiments employing a pdf that is parameterized by a single parameter, such as but not limited to the Pareto distribution, such that {circumflex over (θ)}→θ. Furthermore, because the following relationship holds, a logarithmic MLE may be performed.

The total number of conversions that are sourced at time slice k, that are expected to be eventually observed is p0·n1(k1). The fractional portion of conversions sourced at time slice k1and observed at time slice k2is F((k2−ki+1)Δt|θ), where F(τi|θ) is the corresponding cdf for the pdf Pr(τi|θ). Thus, the total number of unobserved conversions at k2that are sourced to k1(nEuo(k1, k2)) may be determined as
nEuo(k1,k2)=p0·n1(k1)(1−F((k2−ki+1)Δt|θ)).

Employing the above relationship in an algebraic manipulation of the logarithmic MLE results in

Thus, determining the latency distribution may include determining the shape parameter (θ) that optimizes the above expression. Note that the above expression requires and evaluation of the (unknown) conversion rate because nEuo(k1, k2) is explicitly dependent on the conversion rate. To simultaneously determine the conversion rate and the latency distribution, the conversion rate may be constrained via a relationship (or correlation) between the observed conversions, conversions occurring prior to the look-back window, and the portion of impressions that have had the opportunity to convert. More specifically, at the kth time slice,

The left-hand side of the above expression represents the total number of conversions observed up to kth time slice, i.e., N(k). The first term on the right-hand side of the above expression represents the number of impressions that have been converted prior to the look-back window associated with the kth time slice. The second term on the right-hand side of the above expression represents the number of impressions (within the look-back window) that have been converted, based on the latency distribution. Thus, the above expression indicates a constraint (i.e., an explicit relationship) between the conversion rate and the latency distribution. Note that nE(k1, k2) and n1(k1) are signals that may be generated and/or updated at block410.

Lagrange multipliers may be employed to optimize a function that is subject to one or more constraints. For instance, in an exemplary but non-limiting two-dimensional example, a Lagrange multiplier may be employed to optimize (maximize or minimize) a function ƒ(θ, p0) subject to the constraint g(θ, p0)=c. Point (θ′, p′0, λ′) is a stationary point of the Lagrangian expression:(θ, p0, λ)=ƒ(θ, p0)−λ·(g(θ, p0)−c), where λ is a Lagrange multiplier, such that ƒ(θ′, p0,) is optimized. Thus, optimizing ƒ(θ, p0) includes finding a stationary point of(θ, p0, λ).

Using the above expressions,

A stationary point of(θ, p0, λ) may be determined based on the simultaneous solution of the following three equations:

That is, optimizing ƒ(θ, p0) may be accomplished by finding the points where the gradient of(θ, p0, λ) at least approximately vanishes. By determining the stationary point (θ′, p′0, λ′) that simultaneously satisfies the above three equations results in simultaneously determining the conversion rate for the kth time slice (p0(k)=p0′) and the latency distribution for the kth time slice, via θ(k)=θ′.

As noted above, in at least one non-limiting embodiment, the truncated Pareto distribution is employed as the parameterized probability distribution. In such an embodiment, the above three equations may be algebraically manipulated to determine the optimized values for each of: θ, p0, and λ. More specifically,FIG. 4Bshows three equations for the determination of θ, p0, and λ when the Pareto statistical distribution is employed. Equations420,430, and440are written in terms of signals n1(k), nEtot(k1, k), and N(k), where τiis the latency for the ith observed conversion. Note that there is no closed form solution for θ in equation440. Because θ, p0, and Δ are non-linearly coupled via equations420,430, and440, iterative numerical methods may be employed to determine simultaneous solutions for θ, p0, and λ. Various embodiments for determining simultaneous solutions for θ, p0, and λ, via equations420,430, and440are discussed in conjunction withFIGS. 5A-6B. However, briefly, at block412, optimized values for each of θ, p0, and λ may be determined via various numerical techniques and/or methods. By determining optimized values for θ and p0, each of the conversion rate and the latency distribution is determined.

At block414, additionally provided impressions are received. The additional received impression may be based on the determined/updated latency distribution and conversion rate. That is, controlling of the campaign may be updated and adjusted based of the determination of the latency distribution and the conversion rate, such that additional impressions are provided and received. For instance, the controlling of bidding on additional impressions may be updated and/or adjusted, where the updating of the controlling of the bidding is based on the determination of the latency distribution and the conversion rate. More specifically, the bidding process and/or strategy for additional impressions may be updated based on the determination of the latency distribution and the conversion rate. Process400may increment k, i.e., k→k+1, and return to block406to receive additional conversions.

Exemplary Profile Module for a Pareto Distribution

FIG. 5Ashows an exemplary profile module518for a Pareto distribution. Profile module518may be employed in a campaign control system, such as but not limited to campaign control system108ofFIG. 1and/or campaign control system208ofFIG. 2. For instance, profile module208may include similar components, features, and/or functionalities as profile module518. Profile module518is enabled to simultaneously determine the conversion rate and the latency distribution for a campaign, via the various methods discussed herein, by employing a Pareto distribution. It should be understood that other similar profile modules may be enabled to simultaneously determine the conversion rate and the latency distribution of a campaign by employing other parameterized statistical distributions via similar methodologies, i.e., profile module518is an exemplary, but non-limiting, embodiment.

Profile module518includes a state-machine component520, a latency and conversion component522, and a delay524. State-machine component520may receive one or more configuration parameters, such as at least a portion of configuration parameters210ofFIG. 2. For instance, as shown inFIG. 5A, state-machine components520may receive at least look-back window length (L), data-sampling interval (Δt), and an offset in latency (δ). The offset in latency configuration parameter may be employed to avoid numerical difficulties, such as calculating a logarithm of values near zero. Similarly, latency and conversion component522may receive one or more configuration parameters. In addition to the look-back window length, the data-sampling interval, and the offset in latency configuration parameters, latency and conversion component522may receive an initial shape parameter (θ0), and a convergence threshold (ε), each of which may be received from configuration parameters210.

State-machine component520receives input signals, such as but not limited to at least a portion of the signals generated and/or updated at block410ofFIG. 4A. As shown inFIG. 5A, state-machine component520receives at least input signals n1(k) andnUE(k). State-machine component520determines and stores values for various internal states based on the input signals, previous values of the internal states, and the received configuration parameters.

As shown inFIG. 5A, the determined/updated internal states include: N(k), Φ(k), Ψ(k), η(k), α(k), and β(k). A delay524provides a temporal delay of approximately Δt so that the internal states, which are stored via state-machine component520, are employed as feedback for the next time slice, as shown via the feedback loop inFIG. 5A.

The determination and/or updating of the internal states is shown explicitly in the pseudo-code ofFIG. 5B. However, briefly, as discussed above N(k) encodes the total number of conversions observed between the time interval [0, k·Δt]. Φ(k) is a vector of size

LΔ⁢⁢t⁢)
component encodes the number of conversions sourced to (k−i) time slice. Ψ(k) is a vector of size

LΔ⁢⁢t⁢)
component encodes the number of impressions sourced to (k−i) time slice. η(k) encodes the sum of the natural logarithm of all of the latencies until time kΔt. α(k) represents the number of all conversions observed until kΔt and sourced to beyond the look-back window associated with the kth time slice, i.e., prior to time kΔt−L. β(k) represents the number of all the provided impressions sourced to beyond the look-back window associated with the kth time slice, i.e., prior till time kΔt−L. Pseudo-code ofFIG. 5Bshows the determination of each of the internal states based on the input signals and the various received configuration parameters.

As shown inFIG. 5A, each of the determined/updated internal states is outputted by state-machine component520and provided to delay524, and as input to latency and conversion component522. Latency and conversion component522determines/updates and outputs the latency distribution (as parameterized via θ(k)) and conversions rate (p0(k)) based on the inputted internal states and the configuration parameters. Latency and conversion component522iteratively determines values for Δ, p0, and θ of equations420,430, and440ofFIG. 4Bvia computational and/or numerical methods. One non-limiting embodiment of such a numerical method includes employing various interior point, Newton-Raphson, and/or barrier methods to simultaneously solve equations420,430, and440. A Newton-Raphson method may include a Newton method for finding successive approximations for the root of a function, e.g., an iterative methodology for determining estimates or approximations for the roots of multivariate functions based on derivatives of the function. In various embodiments, an interior point method is employed, while in other embodiments a Newton-Raphson method is employed.

FIG. 6Ashows pseudo-code implementing an interior point method to simultaneously and iteratively determine θ(k) and p0(k) via equations420,430, and440. The embodiment shown in the pseudo-code inFIG. 6Ais non-limiting, and other numerical methods may be employed to numerically simultaneously solve equations420,430, and440. InFIG. 6A, an objective function is determined based on equation440. The objective function is represented as a function of the internal states, configuration parameters, and a current estimate of θ(k), and shown in equation642ofFIG. 6B. The gradient of the objective function, represented as a function of the internal states, configuration parameters, and a current estimate of θ(k), is shown in equation640ofFIG. 6B.

As shown in the pseudo-code ofFIG. 6A, a current value of the function and a current value of the gradient (each based on a current estimate of θ(k), i.e., θ0), is iteratively determined. The current value of the function and the gradient are provided to an interior points method that updates the current estimate of θ(k). The iterations are continued until convergence is achieved (as defined via the convergence threshold configuration parameter) is achieved. That is, θ0is iteratively updated, via the interior points method, until the error between current and updated θ0of the objective function adequately vanishes. Upon convergence, θ(k) is set to the final value of θ0and p0(k) is determined based on θ(k) via equation630ofFIG. 6B.

FIG. 6Bshows explicit formulations of the objective function and it's gradient. Equation614defines Tmaxbased on configuration parameters, while equations616and618define latent values employed to determine the value of the objective function and its gradient. Equations620and630recasts equations420and430respectively based on the internal states of profile module518ofFIG. 5A. Equations640and642show the explicit computations for the gradient of the objective function and the value of the objective function, based on the internal states, configurations parameters, and a current estimate of θ(k).

Exemplary Computing Platform

With reference toFIG. 7, computing device700includes a bus710that directly or indirectly couples the following devices: memory712, one or more processors714, one or more presentation components716, input/output (I/O) ports718, I/O components720, and an illustrative power supply722. Bus710represents what may be one or more buses (such as an address bus, data bus, or combination thereof). Although depicted inFIG. 7, for the sake of clarity, as delineated boxes that depict groups of devices without overlap between these groups of devices, in reality this delineation is not so clear cut and a device may well fall within multiple ones of these depicted boxes. For example, one may consider a display to be one of the one or more presentation components716while also being one of the I/O components720. As another example, processors have memory integrated therewith in the form of cache; however, there is no overlap between the one or more processors714and the memory712. A person having ordinary skill in the art will readily recognize that such is the nature of the art, and it is reiterated that the diagram ofFIG. 7merely depicts an illustrative computing device that can be used in connection with one or more embodiments of the present invention. It should also be noticed that distinction is not made between such categories as “workstation,” “server,” “laptop,” “hand-held device,” etc., as all such devices are contemplated to be within the scope of computing device700ofFIG. 7and any other reference to “computing device,” unless the context clearly indicates otherwise.

Memory712includes computer-storage media in the form of volatile and/or nonvolatile memory. The memory may be removable, non-removable, or a combination thereof. Typical hardware devices may include, for example, solid-state memory, hard drives, optical-disc drives, etc. Computing device700includes one or more processors714that read data from various entities such as memory712or I/O components720. Presentation component(s)716present data indications to a user or other device. Illustrative presentation components include a display device, speaker, printing component, vibrating component, etc.

Various operations have been described as multiple discrete operations, in turn, in a manner that is most helpful in understanding the illustrative embodiments; however, the order of description should not be construed as to imply that these operations are necessarily order dependent. In particular, these operations need not be performed in the order of presentation. Further, descriptions of operations as separate operations should not be construed as requiring that the operations be necessarily performed independently and/or by separate entities. Descriptions of entities and/or modules as separate modules should likewise not be construed as requiring that the modules be separate and/or perform separate operations. In various embodiments, illustrated and/or described operations, entities, data, and/or modules may be merged, broken into further sub-parts, and/or omitted.