互联网广告的最优化投放方案研究外文翻译资料

 2023-01-11 10:14:59

互联网广告的最优化投放方案研究

摘要:网络广告的精准投放是一个很复杂的过程，很多广告主不知道怎样来优化他们的投资回报率。广告图片等作为广告的载体，每一张图片都承载着广告蕴含的商业目的。在本文中，我们研究的问题，广告主有效地在网上进行广告投放。特别是我们专注于制定最佳的应对策略，变成一个优化问题。广告主有一组关键词和一些关于接受广告者的随机信息，即在成本与情景的概率分布，点击组合。

我们可以通过提出的第一个已知的非平凡的聚对数近似方法来研究这个问题。我们发现这个问题的实际利益的一些特殊情况下，如与SCE -条件或多项式的固定数量的大小与成本相关的参数，它是可以在多项式时间内可解或改进的近似比。随机优化方案预算优化完善技术结构，并建立技术模型。

一、引言

本文主要研究如何分配互联网广告的预算问题已经如何进行精准化的互联网广告投放。在搜索过程中，用户在得到搜索结果的同时，也会看到一部分广告。这些广告很大程度上是由关键词导向对你进行投放的。其中广告展现的很重要的一种模式就是竞价展现。我们面临的问题就是如何解决广告主的问题。即使是很小的广告有很多关键词，必须弄清楚如何为每个这些关键词竞价推广预算。这是一个非常重要的任务，并且是支持广告主进行一个单独的广告投放计划的基础。广告主都有自己的投放渠道，重要的是如何安排这些广告渠道的合理分配。同样，作为行动指导，广告主必须决定如何控制他们的广告预算。在所有这些情况下，因此，广告商有各种各样的“目标”，希望将他们的预算用在刀刃上。

考虑到广告投放所需的预算和广告载体背后承载的各种关键词，他们想要展现自己的广告，如何出价，如何控制预算，这是一个问题。这其实是个复杂的过程，所以很多广告主会进行模拟投放。对于每个关键词，会有很多不同的广告主对其进行竞争，挑战性就在于如何建立一系列有效的参数。一个基本的和被广泛接受的广告上应该不断追求更好的策略，也就是固定其他广告策略和选择最佳的策略为一体的响应。一个看似简单的去策略却能极大地提升广告商对其预算的使用效率。例如，在预算的情况下，对单一关键词进行重复竞价购买，对这个关键词的占有程度就很很高。

为了帮助广告主实现最佳响应策略，搜索引擎为每个关键词提供推荐出价。这个功能能够帮助客户直观的了解当前的关键词竞争强度。这项功能还能教会广告商寻找最佳响应的投标策略。构建竞价策略是关键，而接下来本文通过构建一个不确定性延伸机构的工作的模型来研究，看接下来的文章。

在现实中，投标和点击的功能是不固定的，是随机的未知的相关性和不确定性变量的查询（因此，点击和预算花费联系在一个关键词上）。每一天，关键词的相关数据每天都会发生变化。因此，必须考虑这些随机变量的一个特定的随机模型，并最大限度地发挥预期的点击次数。这种方法是一句随机性的情况向进行的变量分析。

1组织方式

为了方便读者理解，我们的组织模式为如下。

bull;首先，我们先构建一个随机优化模型，从最简单的一个开始，连同一些评论和说明有关模型。在本节的最后一个小节中，我们修正了一些符号上的均匀性，为读者方便。

bull;其次，我们总结本文获得的结果，对于读者的利益，我们组的结果分为两大类，即一组处理的原机型没有重新计算复杂问题以及一套应对变化和特殊情况下的额外结果，主要成果在文章定义的模型。其他的部分，应对我们的结果和精确的陈述证明自己的技术细节。对于复杂的证明，我们在进行实验之前提供的证明步骤的只是非正式的概述。这些部分内容需要进一步进行组织。

bull;然后。我们会二次讨论此问题，并对文本进行修订。

bull;然后。我们再证明聚对数近似算法SSBO和多SSBO问题（主要结果（R1））。

bull;其次。证明我们逼近硬度结果为SSBO和多SSBO问题（主要结果（R2））。

随机预算优化2场景模型

我们讨论的模拟场景并使用spon-舍雷德search.5的语言，我们使用后缀SSBO（场景随机预算优化）的首字母缩写的各种不同版本的我们的问题相关的问题。为了读者理解方便，我们首先开始与仅涉及场景模型的一个稍微简单的版本。我们称这个版本为“统一费用”，以下是它的案例介绍。

2．1单槽案例：

“统一费用”基本模型，以下假设：

bull;有广告坑位。

bull;我们有一组n个关键字K1，K2，...，Kn的与具有成本关键字KJ每点击的DJ（正整数）。

bull;我们有一个正整数，B表示预算的广告客户。

bull;其次，其中第1个场景的特点是以下参数的集合： - εI的概率（?mi= 1εI= 1）。 - A“点击矢量”（AI，1，AI，2，艾，N。），其中每个AI，Jge;0是一个整数。每一个AI，都有相对应赋予 的含义。这个方案可以被认为是取样模型在各种时间点消费者的随机浏览，6 x1，X2，...，XN，响应的第j个关键字，以最大化适当的总收益。所讨论的制剂的一个重要的方面是，如果预算不是限制性的，则回报对应于预期的点击的总数，但如果预算原来进行限制为任何情形则回报缩放的预期总数点击通过分数，该预算将证明基于以上的直觉，我们精确的目标是最大化总期望收益在所有情况下，即，?mi= 1的模型方法，见效。我们的结论可以很容易地采用到其他互联网广告渠道，如显示广告和行为靶子。这可以由搜索引擎的广告商提供，或者所使用的搜索引擎的投标代表广告客户。同样，广告商和其他搜索引擎优化也可以使用趋势和搜索引擎提供的其他数据“推断”情景间接。 。基本假设是，在方案中，查询和关键字充分混合，当预算用完，广告活动暂停期间按照当前完成的。查询和关键字充分混合，不仅是因为广告限制进行传播出符合条件的广告活动在一个场景的时期，因为从数以百万计的用户流的聚集也。参见为理由的具体细节。

选择变量的性质：

积分版本（国际-SSBO）：XJisin;{0,1}对于所有j。这相当于情况下基于随机材料时，无论是广告商选择，还是支付的所有点击的关键字，广告商的策略都是是确定性的。

分数版本（统一-裂缝-SSBO）：0le;XJle;1对于所有j。这可以被认为是一种策略，其中广告商将这些数字作为关系和竞价的关键字，基于这些关系，因此唯一的制胜（和支付）的点击和展示的一部分随机的方式每个关键字。如果该确定的策略是难以计算，并提供质量差的溶液，然后将随机化的策略是更理想的。

其中讨论除了场景模式，至少有两个可能的模式为随机预算优化。在比例模型只有一个的点击中，保持点击次数不同的关键字相同的相对比例，而在独立的关键字模型中的每个关键字都有自己的概率分布当日总数全局随机变量。然而，所有这些模型中本方案为基础的模式可能是现实的最自然的模型中的一个，并提供一个适当的中间地带之间复杂的任意联合概率分布和所有关键字的单个分配。接下来，我们假设没有一般性的1 = D1le;d2le;...le;dn损失。

2.2单槽案例：一般模型

在的问题SSBO成本每次点击值可以在一定范围的情况略有不同更现实的版本，由于在估计其小的误差。这可以通过引入拉伸参数（小整数）8 1le;kappa;= O（聚（日志（M N）））进行建模。现在，DJ代表的基本费用，每次点击的关键字KJ，而实际成本每点击在第i个方案中的关键字KJ记为CI，J，与CI，Jisin;[DJ，DJkappa; ]0.9然后，（1）可以简单地通过在替换的DJ更新。

在整个文件中，符号聚（a）表示多项式的一个，也就是对一些积极常数c。

例如，在拉伸参数kappa;允许我们的情况下进行建模，实际成本可

从周围1 kappa;DJ平均概率分布绘制发生2的概率微乎其微

范围内的平均值的plusmn;1-kappa;的DJ。注意，这仅仅是一个例子。

概率分布为每次点击的实际成本，除了它的长度kappa;的区间内变化的变化量。

E [payoff] =?nB（εIJ = 1 AI，J DJ XJ

if?nadxxle;BJ = I，JĴĴ

NJ = 1 AI，J XJ），以下，我们在这两个问题之间区分问题的基础。

或者，第i个场景由ci的方程，J。我们指的是这种一般情况下INT-SSBO和压裂SSBO，分别在整数和小数版本进行;注意，制服SSBO问题从相应SSBO问题通过设置kappa;= 1获得。

结果与证明技术小结

左场景模型作为主要开放问题的计算复杂性的问题，表明两者的整数和小数这个问题的版本后，甚至对于单个槽的情况下，是个难题。并指出，没有非平凡可近似结果众所周知。虽然之前的结果问题充分利用了背包问题的见解，一些潜在的回报与每个关键字相关联，在直接应用这些技术，我们的模型遇到一个主要困难是每一个关键字，回报是非常不同的，从一个场景到另一个场景又是另一回事。

结果3.1摘要

我们提供在本文中所获得的结果的一个略粗摘要;精确的边界是在相应的技术部分是证明的结果才可用。

主要结果（R1）（近似算法）：我们提供了在运行的算法近线性

时间和实现以下近似比率：13

bull;分钟{O（M），O（kappa;日志DN）} - 近似为INT-SSBO和压裂SSBO和，

bull;分钟{O（M），O（skappa;loglog2（M N））} - 近似INT-MULTI-SSBO和FRAC-MULTI-SSBO，其中?= MAXJ，K DJ，K。 （R 2）（近似硬度为单和多时隙例）：我们表明，除非ZPP = NP，存在的INT-SSBO和FRAC-SSBO的实例，其中n的关键字和m = n时的每个具有相等概率的情况，如任何多项式时间算法为解决这些问题，必须具有以下（为任何常数0 lt;εlt;1）中的任一项的近似值的比例：bull;（M1-ε）（（N1 -ε）），或kappa;= O。

（LOG1kappa;-εDN）。

这几乎是一致的（R1）的上限。因此，我们不能以一般的im-证明绑定（R1）的逼近。因为SSBO问题是多SSBO问题特例对于s = 1时，近似的硬度范围为SSBO可以扩展到多SSBO，亲人们提供形式（M1-ε），的下界（N1-ε ），或（登录kappa;·LOG1-εDN）的实例有n个关键字，M = N的情况和s插槽。我们还表明，INT-MULTI-SSBO为MAX-SNP硬对于s = 2即使当kappa;= 1和CJ中，k = 1对于所有的j和k。

其它结果除了主要结果，我们还证明了一些涉及变化和我们的问题的特殊情况的其他结果。

固定参数易处理性问题：对于实际某些参数范围，我们表明，这些优化问题可以有效解决。如果M或NS是固定的，FRAC-MULTI-SSBO与delta;对于一个绝对错误的多项式时间解决任何固定delta;gt; 0。如果还出价多项式的大小，INT-MULTI- SSBO还设有一个多项式时间的解决方案delta;为任何固定delta;gt; 0的绝对错误。

半定规划基础的方法限制：下限

在（R2）具有εlt;1，因而离开这个下限之间一个“非常小”的差距

在（R 1）所描述的上界。很自然地问，如果差距可能被淘汰;

例如，我们可以设计一个近似算法的特殊情况为kappa;= 1

其近似比例，比方说，O（M）或（DN）。

以提供一个具体的证明，这样的多项式时间近似算法

但是，我们仍然观察到自然半定规划

因为它具有米的大型完整性间隙=（DN）2 logDN

双SSBO问题：最后，在某些情况下，双随机预算优化问题可能会很有意思，在这里我们给出预期的点击num-误码率的目标，并且目标是最小化而达到目标所花费的预期预算。我们提出了一些具体和近似结果这个问题的双通道版本。

4 SBO的问题与二分二次整数程序

在本节中，我们展示了如何重新制定各种SBO问题，二分二次整数规划（QIP）。这些重新拟订被大量使用在后文证明。二分二次程序是一个二次方案，其中有义变量的二部划分，使得每一个术语涉及在从每个分区最多一个变量。这样的二次规划的采用plusmn;1值的变量一个著名的例子是所谓的格罗腾迪克的不平等[1]。然而，如将在后面示出，我们的二次方案的不同之处，从该不均衡性质显著。

6其他结论

改进算法SSBO和多SSBO特殊情况

通过“内delta;的附加误差”引理10个词组，也就是说，如果我们的解决方案将返回x的目标值时，最佳值是y，则| X - gamma;|le;delta;。

（一）（场景固定数目）如果M是固定的，FRAC-MULTI-SSBO承认与delta;的任何固定delta;gt; 0，INT- SSBO承认的伪多项式时间为O的绝对误差的伪多项式时间解（ 1） - 近似和INT-MULTI- SSBO承认伪多项式时间O（LOG2 N）。

（二）（固定的关键字的数量）如纳秒是固定的，然后FRAC-MULTI-SSBO承认与delta;的绝对值误差的伪多项式时间解为任何固定delta;gt; 0。

（三）干扰素= O（log）INT-MULTI-SSBO- MITS一个多项式时间精确解。

（D）（固定场景和多项式投标数量）如果M是固定的，所有的数字，即最大值{马克西，J，K { J，K}的最大尺寸，马克西{}，马克西{ 1}，εIMAXI，J，K {CI，J，K}，至多为聚，然后INT-MULTI-SSBO承认与delta;的绝对值误差多项式时间解为任何固定delta;gt; 0。

证明（a）及（b）我们证明（a）部分如下（证明（b）部分相似）。请考虑压裂-MULTI-SSBO问题;让Y =max1le;ile;m，1le;jle;n，1le;kle;s{苡仁，J，K}。

命题4设alpha;* =（alpha;*，alpha;*，...，alpha;*）和x * =（X *，...，X *，X *，...，* * *12米1,1- 1，s2,1

X2，S，...，XN，1，...，XN，S）是E值的最优解解向量[回报*] =?malpha;*（?n?s义，J，KX *）。假设我们逼近lt;

剩余内容已隐藏，支付完成后下载完整资料

Stochastic Budget Optimization in Internet Advertising Bhaskar DasGupta · S. Muthukrishnan

Received: 4 October 2010 / Accepted: 21 January 2012 / Published online: 8 February 2012 copy; Springer Science Business Media, LLC 2012

Abstract Internet advertising is a sophisticated game in which the many advertisers “play” to optimize their return on investment. There are many “targets” for the adver- tisements, and each “target” has a collection of games with a potentially different set of players involved. In this paper, we study the problem of how advertisers allocate their budget across these “targets”. In particular, we focus on formulating their best response strategy as an optimization problem. Advertisers have a set of keywords (“targets”) and some stochastic information about the future, namely a probability distribution over scenarios of cost vs click combinations. This summarizes the poten- tial states of the world assuming that the strategies of other players are fixed. Then, the best response can be abstracted as stochastic budget optimization problems to fig- ure out how to spread a given budget across these keywords to maximize the expected number of clicks.

We present the first known non-trivial poly-logarithmic approximation for these problems as well as the first known hardness results of getting better than logarith- mic approximation ratios in the various parameters involved. We also identify several special cases of these problems of practical interest, such as with fixed number of sce- narios or with polynomial-sized parameters related to cost, which are solvable either in polynomial time or with improved approximation ratios. Stochastic budget opti- mization with scenarios has sophisticated technical structure. Our approximation and hardness results come from relating these problems to a special type of (0/1, bipar- tite) quadratic programs inherent in them. Our research answers some open problems raised by the authors (in Algorithmica, 58(4):1022–1044, 2010).

B. DasGupta (?)
Department of Computer Science, University of Illinois at Chicago, Chicago, IL 60607, USA e-mail: dasgupta@cs.uic.edu

S. Muthukrishnan
Department of Computer Science, Rutgers University, Piscataway, NJ 08854, USA e-mail: muthu@cs.rutgers.edu

Algorithmica (2013) 65:634–661 635 Keywords Internet advertising · Scenario model · Stochastic budget optimization

1 Introduction

This paper deals with the problem of how advertisers allocate their budget in Internet advertising. In sponsored search, users who pose queries to internet search engines are not only provided search results, but also a small set of text ads. These ads are chosen from a set of campaigns set up by advertisers based on the keywords in the search query. A lot of focus has been on how these ads are chosen and priced, which is via an auction that is by now well known [2, 10, 20].1 Our focus is instead on the problem faced by advertisers. Even small advertisers have many keywords, a budget in mind and must figure out how to spread this budget on bids for each of these keywords. This is a highly nontrivial task, and the basis for a separate industry to support advertisers. A similar problem arises with “display ads” where advertisers have websites where their ads will be shown and need to split their budget for the ad campaign across the sites to be most effective. Likewise, in behavioral targeting, advertisers have to decide how to spread their budget across behavior groups. In all these cases, therefore, advertisers have various “targets” and wish to split their budget across them to optimize their ad campaigns.

Consider the sponsored search example and fix an advertiser A. They have many keywords that they would like to target for their ads. How should they bid for each, given some overall budget they can spend? There is a sophisticated underlying game in which the many advertisers “play” to optimize their return on investment simul- taneously. For each keyword and for each instance of auction triggered by this key- word, there is potentially a different set of competing advertisers involved. Building effective strategies is challenging amidst so many parameters. A fundamental and widely accepted proposal is for the advertiser A to pursue a best response strategy, i.e., fix the strategies of other advertisers and pick the best strategy as onersquo;s response. Besides being a simple and easy strategy to understand and hence suitable for exper- imentation by advertisers, best response has desirable properties. For example, in the absence of budgets and for single repeated auctions, special type of best response by every player leads to the VCG outcome [5, 6, 10, 20].

In order to help the advertisers implement this best response strategy, search en- gines provide them with expected bid versus clicks function for each keyword.2 As- suming that the rest of the world is fixed, these functions provide an estimate of the expected number of clicks an advertiser would obtain by bidding a certain value on that keyword. These functions can also be “learned” by an advertiser to some extent by systematically trying out various bids. Finding advertiserrsquo;s best response bidding strategy then becomes an optimization problem where the goal is to maximize the ex- pected number of clicks assuming access to these functions. The resulting problems

1Likewise, there was a lot of work on bidding strategies [4, 11, 19, 23]. This paper extends that body of work by considering a richer model of uncertainty; see subsequent paragraphs.

A more general approach is to acknowledge that, in reality, the bids vs clicks functions are not fixed, but rather random variables with unknown correlations and uncertainties: number of queries (an

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[287263]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章