• 作者:老汪软件技巧
  • 发表时间:2024-10-03 10:01
  • 浏览量:

Pacing是Facebook广告系统中花费预算的节奏的一个算法,Google Adwords里面有一个功能是设定预算和最高出价,Adwords就可以自动通过出价调节,让你在这个限定的预算下获取最多的点击,Pacing这个算法和Adwords的这个功能很类似,都是通过调节出价,让广告主获得最大的ROI。

目前预算控制Pacing算法有很多,这里主要说一下PID,有关强化学习Pacing算法待了解后更新。

1. 预算控制问题描述

随着信息技术的进步,互联网广告由于投放周期短、触达范围广、可精准投放等优点,近些年来得到了高速发展。在互联网广告系统中,广告主(企业/商家)通过购买供给方(媒体)提供的广告位,将广告传递给受众(消费者),进而达成广告主的商业目的。在上述过程中,针对同一广告位,往往会存在多个广告主竞争出价,最终出价高者以一定的成本,赢得广告位并获得展示机会。

然而在实际的广告投放系统中,会包含诸如广告主端的点击率预估模型、用户价值预估模型、竞价算法,媒体端的OCPA、OCPC出价模型,以及多方竞价、二价成交等不可控机制,最终的投放系统十分复杂,影响投放成本的因素过多,造成用户成交价与实际出价并不相等,实际投放成本难以契合广告主在投放初期所制定的预算。这时候就需要预算控制算法进行广告预算控制了。

在单一周期内,预算控制的目标为在既定时间单位内将预算以既定最优策略的方式分发,从长期来看,将多个周期联合起来看,预算系统的目标可以延伸为:

致力于将更长时间跨度、甚至于无穷时间的最优化控制问题,分解为若干个更短时间跨度,或者有限时间跨度的最优化控制问题,在满足有限时间跨度内预算核销准确性要求的基础上,在在长周期下仍然追求策略最优解。

2. PID原理理解

一个经典的PID算法如图所示,首先有一个输入,经过比例、积分、微分的调节得到一个输入,调节系统输出进入到实际的系统里又得到了一个输出。最后利用实际系统的输出来调整下一次的输入。

PID 方法通过误差信号控制被控量,PPP、III、DDD 分别表示比例、积分、微分误差。我们定义时刻 ttt 时,系统的输入为i(t)i(t)i(t),输出为o(t)o(t)o(t),误差量为err(t)=o∗(t)−o(t)err(t)=o^*(t)-o(t)err(t)=o∗(t)−o(t),在i(t)i(t)i(t)和o∗(t)o^*(t)o∗(t)满足一定的逻辑关系时,不妨视i(t)i(t)i(t)为o∗(t)o^*(t)o∗(t),此时 PID 方法的误差量可以表示为:

u(t)=kp(err(t)+1Ti∫err(t)dt+TDderr(t)dt)u(t)=k_p(err(t)+\frac1{T_i}\int err(t)dt+\frac{T_Dderr(t)}{dt})u(t)=kp​(err(t)+Ti​1​∫err(t)dt+dtTD​derr(t)​)

简化后可得:

U(t)=kp(err(t)+ki∫err(t)dt+kdderr(t)dt)\mathrm{U}(t)=k_p(err(t)+k_i\int err(t)dt+k_d\frac{derr(t)}{dt})U(t)=kp​(err(t)+ki​∫err(t)dt+kd​dtderr(t)​)

其中,

以上是连续形式的PID公式。而显示场景一般会有一个采样间隔,为离散化形式为,这时候需要对公式进行一定的修改。假设采样间隔为TTT,在第 kkk 个 TTT 时刻,有:

u(k)=kp(err(k)+TTi∑kerr(j)+TDT(err(k)−err(k−1)))u(k)=k_p(err(k)+\frac T{T_i}\sum^kerr(j)+\frac{T_D}T(err(k)-err(k-1)))u(k)=kp​(err(k)+Ti​T​∑k​err(j)+TTD​​(err(k)−err(k−1)))

简化表示为:

u(k)=Kp(err(k)+ki∑kerr(j)+kd(err(k)−err(k−1)))u(k)=K_p(err(k)+k_i\sum^kerr(j)+k_d(err(k)-err(k-1)))u(k)=Kp​(err(k)+ki​∑k​err(j)+kd​(err(k)−err(k−1)))

此外,PID还有一种增量形式。在t−1t-1t−1时刻,有:

u(k−1)=Kp(err(k−1)+ki∑k−1err(j)+kd(err(k−1)−err(k−2)))u(k-1)=K_p(err(k-1)+k_i\sum^{k-1}err(j)+k_d(err(k-1)-err(k-2)))u(k−1)=Kp​(err(k−1)+ki​∑k−1​err(j)+kd​(err(k−1)−err(k−2)))

差分有:

Δu(k)=kp(err(k)−err(k−1)+kierr(k)+kd(err(k)−2err(k−1)+err(k−2)))\Delta u(k)=k_p(err(k)-err(k-1)+k_ierr(k)+k_d(err(k)-2err(k-1)+err(k-2)))Δu(k)=kp​(err(k)−err(k−1)+ki​err(k)+kd​(err(k)−2err(k−1)+err(k−2)))

化简后有:

Δu(k)=Aerr(k)+Berr(k−1)+Cerr(k−2)\Delta u(k)= Aerr(k) + Berr(k-1) + Cerr(k-2)Δu(k)=Aerr(k)+Berr(k−1)+Cerr(k−2)

其中,

A=kp(1+ki+kd)A = k_p(1 + k_i + k_d)A=kp​(1+ki​+kd​)

B=kp(−1−2kd)B = k_p(-1-2k_d)B=kp​(−1−2kd​)

C=kpkdC = k_pk_dC=kp​kd​

一般的使用场景下,PID 方法可以快速稳定地消除误差,使系统输出达到目标值。接下来,对比例系数、积分系数、微分系数三部分进行进一步理解:

2.1 比例单元

比例项的输出u(t)与输入err(t)成正比,直接反映了当前值与目标值得误差信号,偏差一旦产生,立即向相反方向成比例的减小偏差。比例项反应迅速,能快减小偏差,但不能消除静差。

静差指的是在系统达到稳态的过程中,稳定输入值与目标的差距。仅使用比例项,由于实际输出值与目标值间差距逐渐减小,因而比例项的输出也逐渐减小,只有存在偏差时比例项才能产生输出,当误差为零时,比例项输出也为零,因此在由非稳态逐渐向稳态逼近的过程中,必然会存在静差。

此外,比例项的输出取决于误差及比例系数,比例系数越小,输出对误差的敏感度也越小,系统响应越慢。反之比例系数越大,控制作用也越强,系统响应会越快。但值得注意的是,过大会使系统产生较大超调和振荡,导致系统稳定性变差,下图演示了在其他参数相同的条件下,不同比例系数下系统振荡曲线:

2.2 积分单元

积分项主要用于消除静差,提高系统的误差度。积分控制作用的存在与偏差err(t)的存在时间有关,只要系统存在着偏差,积分环节就会不断起作用,对输入偏差进行积分,使控制器的输出及执行器的开度不断变化,产生控制作用以减小偏差。

在积分时间足够的情况下,可以完全消除静差,这时积分控制作用将维持不变。越小,积分速度越快,积分作用越强。积分作用太强会使系统超调加大,甚至使系统出现振荡。下图所示为其他参数相同的条件下,不同积分系数下的系统振荡曲线:

2.3 微分单元

微分环节的作用能反映偏差信号的变化趋势,并能在偏差信号值变得太大之前,在系统中引入一个有效的早期修正信号,从而加快系统的动作速度,减小调节时间。在偏差刚出现或变化的瞬间,不仅根据偏差量做出及时反应,还可以根据偏差量的变化速度提前给出较大的控制作用,将偏差消灭在萌芽状态,这样可以大大减小系统的动态偏差和调节时间,使系统的动态调节品质得以改善。

微分环节有助于系统减小超调,克服振荡,加快系统的响应速度,减小调节时间,从而改善了系统的动态性能,但微分时间常数过大,会使系统出现不稳定。下图所示为其他参数相同的条件下,不同微分系数下的系统振荡曲线:

2.4 PID实现

接下来来实现一个最最简单的PID仿真,以下定义了一个PID控制器:

class PIDContorller:
    def __init__(self, kp, ki, kd, dt, pre=0.0):
        self.kp = kp
        self.ki = ki
        self.kd = kd
        self.dt = dt
        self.pre = pre
        self.p = 0.0
        self.i = 0.0
        self.d = 0.0
    def calculate(self, bid_val, history_cost):
        """
        根据history cost 更新比例项、积分项和微分项
        :param bid_val: 广告主广告费用
        :param history_cost: 历史实际广告花费
        :return: 
        """
        pre_p = self.p
        self.p = bid_val - history_cost
        self.i = self.i + self.p * self.dt
        self.d = self.p - pre_p / self.dt
        self.pre = history_cost
        return self.i
    def update(self, bid_val):
        # err(t-1)
        pre_p = self.p
        # p: 比例项,当前时刻误差 err(t)
        self.p = bid_val - self.pre
        # i: 积分项,到t时刻总误差
        self.i = self.i + self.p * self.dt
        # d:微分项,err(t) - err(t-1)
        self.d = self.p - pre_p / self.dt
        # 根据PID,输出需要调整的费用
        diff = self.kp * self.p + self.ki * self.i + self.kd * self.d
        # 根据diff进行调整,输出今天的广告花费
        self.pre = self.pre + diff
        return self.pre
    def reset(self):
        '''
        多广告商场景下,每个广告商进行calculate和update之前需要reset下原参数
        '''
        self.pre = 0.0
        self.p = 0.0
        self.i = 0.0
        self.d = 0.0

此外还有一种增量形式,也很简单,只要对update函数进行一些小修改:

def update(self, total_exp):
    """
    根据历史数据更新 t + 1 时刻的 coef
    使用增量计算公式 Pout= Kp * [e(t) - e(t-1)] + Ki * e(t) + Kd * [e(t) - 2*e(t-1) +e(t-2)]
    :param total_exp: t 时刻的总流量
    :param coef: t 时刻线上的调节系数
    :return: t + 1 时刻调节系数 coef
    """
    pre_p = self.p
    self.p = self.bid_val - total_exp * self.pre_coef
    diff = self.kp * (self.p - pre_p) + self.ki * self.p + self.kd * (self.p - 2 * pre_p + self.p_pre)
    self.p_pre = pre_p
    cur = total_exp * self.pre_coef + diff
    self.pre_coef = cur / total_exp
    return self.pre_coef

此外,还有傅立叶滤波转换的方法,具体来讲就是:在计算微分项的时候,不直接采用当前时刻的误差err(t)进行计算,而是采用经过滤波之后的滤波值。

from scipy.fftpack import fft, ifft
def update(self, total_exp):
    """
    根据历史数据更新 t + 1 时刻的 coef
    :param total_exp: t 时刻的总流量
    :param coef: t 时刻线上的调节系数
    :return: t + 1 时刻调节系数 coef
    """
    pre_p = self.p
    self.p = self.bid_val - total_exp * self.pre_coef
    self.i = self.i + self.p * self.dt
    if len(self.stack) >= self.preiod:
        self.stack.pop(0)
    self.stack.append(self.p)
    if len(self.stack) < 2:
        self.d = self.p - pre_p
    else:
        fft_values = fft(self.stack)
        frequencies = np.fft.fftfreq(len(fft_values))
        filtered_fft = np.zeros_like(fft_values)
        dominant_frequencies_index = np.argmax(np.abs(fft_values))
        filtered_fft[dominant_frequencies_index] = fft_values[dominant_frequencies_index]
        filtered_fft[-dominant_frequencies_index] = fft_values[-dominant_frequencies_index]
        period_component = np.real(ifft(filtered_fft))
        self.d = period_component[-1]
    diff = self.kp * self.p + self.ki * self.i + self.kd * self.d
    self.p_pre = pre_p
    cur = total_exp * self.pre_coef + diff
    self.pre_coef = cur / total_exp
    return self.pre_coef

PID仿真的结果如图:

在这里设定了前七天的波动,从第1天开始进行了PID控制,最后使得总cost趋近于目标bid,且累积diff逐渐趋近于0。

pid参数如何选择呢,一般来说需要线下不断调试寻参,这里给出一种最简单的网格搜索方法:

class pid_grid_search:
    def __init__(self, dt, bid_val, bid2exp, history_day, tend_coef):
        self.dt = dt
        self.bid_val = bid_val
        self.bid2exp = bid2exp
        self.history_day = history_day
        self.tend_coef = tend_coef
    def pid_task(self, conf, data):
        kp, ki, kd, kv = conf
        pid = PIDContorller(kp, ki, kd, self.dt, self.bid2exp(self.bid_val), self.tend_coef)
        sum_diff, statis_list = self.run_pid_parallel(data, pid, kv)
        return (kp, ki, kd, kv), sum_diff, statis_list
    def grid_search(self, data, parallel=True):
        confs = self.pid_configs()
        if parallel:
            # 定义分布式计算
            executor = Parallel(n_jobs=cpu_count(), backend='multiprocessing')
            tasks = (delayed(self.pid_task)(conf, data) for conf in tqdm(confs))
            res = executor(tasks)
        else:
            res = [self.pid_task(conf, data) for conf in tqdm(confs)]
            res.sort(key=lambda x: abs(x[1]))
        return res
    def run_pid_parallel(self, data, pid, kv):
        # some process
        return sum_diff, [sum_diff_list, flow_list, cost_list, coef_list]
    def pid_configs(self):
        confs = list()
        p_params = np.arange(0, 1, 0.01)
        i_params = np.arange(0, 1, 0.01)
        d_params = np.arange(0, 1, 0.01)
        v_params = ['v1']
        for p in p_params:
            for i in i_params:
                for d in d_params:
                    for v in v_params:
                        confs.append([p, i, d, v])
        return confs

在工业界,PID还有许多变体,以适应线上真实场景。

参考文献附录:广告相关术语记录AdAOVARPUBidBounce RateB2B、B2C与B2WCACCPLCPACPCCPMCPSCPPCPVCPT

总结:

CTRCVReCPMLTVPVROIUVGMV广告计费