Edited at

入札額最適化のシミュレーション

More than 5 years have passed since last update.


動機

広告の自動入札のアルゴリズムを考える仕事をしているのですが(もうすぐ過去形になりますがw)、

ログが全く貯められていない状況にあります。

そのため、しょうがなくデータを発生させてしょうがなくシミュレーションを行った次第です。


このブログに書いたこと


  • 多目的最適化の概要

  • 入札金額最適化の概要(外部資料に飛ばす)

  • 参考コード


多目的最適化の概要

多目的最適化とは、書籍には以下のように記載があります。


多目的最適化では複数の目的関数$\bf{f}$を最小化することを考える。理想的には全てのめ目的関数$f_1$,...,$f_k$を同時に最小化できればよいと思われるかもしれない。しかし、それではそもそも多目的最適化として解く必要はなかったということである。なぜならば、1つの目的関数を最小化すれば他の目的関数も同時に最小になっているということであるから。したがって、通常多目的最適化で取り扱うべき問題は、ある目的関数を小さくしようとすると他の目的関数が大きくなってしまうというように、目的関数$\bf{f}$の間にトレードオフの関係がある場合である。(数理最適化の実践ガイドp.110から引用)


つまり、「あちらを立てればこちらが立たず」な状況の中で、目的関数の値を最小に(最大に)しましょう、というものです。

基本的にはパレート解を見つけるということになります。手法としては様々あり、パレートフロントが凸な場合、非凸な場合で手法も異なってきます。

具体的な手法に関しては応用に役立つ50の最適化問題 (応用最適化シリーズ)が割りと参考になると思います。

ただ今回は高速に計算を行いたいのと、かなり細かいtime slotに対する最適化を行いたかったため、ヒューリスティックなやり方を採用しています。


入札金額最適化の概要

参考文献はこちらです。

Real time bid optimization with smooth budget delivery in online advertising, Lee+, Turn Inc.,'13 [PDF]

内容についてはslidshareを参照していただければと思います。

(ただ、これ、今見ると解釈部分が少し間違っていますね。。。気が向いたら修正しておきますw)

この論文を元にコードを作成しています。

ただ、データを発生させるのに手間がかかる部分などを省略しています。

冒頭にも書いたように、データが無いためユーザエージェントとビッドエージェントを立てて、擬似的に入札をするようにしています。

time slotは1分として、それぞれのtime slotでの予算の分配と入札金額最適化を行っていきます。


参考コード

以下、作成したコードを記載しました。

非エンジニアが書いていますのでツッコミどころは多いと思いますが、我慢して見てやってください。


ユーザエージェント

サイトを訪問してもらうユーザエージェントにサイトを作成します。

# coding: utf-8

import random

class Agent:
def __init__(self,num):
random.seed(num) # random seedの発生
self.ctr = random.uniform(0,1)

def get_ctr(self):
return self.ctr

def get_visiter_ctr(self, pred):
if random.uniform(0,1) > (1-pred):
return self.get_ctr()
else: return False

続いて、応札を行うエージェント(競合他社)を作成します。


入札エージェント

# coding: utf-8


import random
from math import ceil

class Agent:
def __init__(self,n):
random.seed(n) # random seedの発生
self.ctr = random.uniform(0,1)
self.maxprice = random.randint(40,90)

def get_maxprice(self):
return self.maxprice

def get_bid_price(self, ctr, pred):
price = self.maxprice*ctr*pred

if random.uniform(0,1) > 0.35 :
return ceil(price) + random.randint(0,5)
else:
return False

最適化部分のコードをいかに記載します。


予算および入札金額最適化

# coding:utf-8

#cython: boundscheck=False
#cython: wraparound=False

import pyximport; pyximport.install()

from math import sin, cos, pi, fmod, sqrt, floor
import random

import useragent
import bidagent

import numpy as np
cimport numpy as np
cimport cython

DTYPE = np.float64
INTTYPE = np.int64
ctypedef np.float64_t DTYPE_t
ctypedef np.int64_t INTTYPE_t

cdef extern from 'stdlib.h':
ctypedef unsigned long size_t
void *malloc(size_t size)
void free(void *prt)

class CreatePredict:
pi2 = 2*pi
#random.seed(3)
PHI = 2*pi/8 # 位相のずれを表現
# TBit = 10000000.0

def __init__(self, period, agent_num):
self.minbit = 1000*agent_num/1000
self.E = 1250*agent_num/1000

self.PERIOD = period
self.OMEGA = self.pi2/self.PERIOD
self.AGENT_NUM = agent_num

def getvalue(self,period):
"""
サイトに来る確率
sin(theta) = sin(OMEGA*t + phi)
T = 2*pai/OMEGA
60*60*24=86400sec
OMEGA = 2pai/86400
"""

cdef sec
cdef np.ndarray[np.double_t, ndim=1] tmp = np.zeros(period,dtype=np.double)
for sec in xrange(period):
tmp[sec] = self.E * ( sin(self.OMEGA*sec - self.PHI) + 1 ) + self.minbit
return tmp/self.AGENT_NUM # predの算出

cdef class ComputeBid:
cdef int time, day
gamma = 1.96 # 信頼区間の算出に使用(95%信頼区間を想定)
beta1=0.3
beta2=0.8

theta_bin = 100

cdef np.ndarray \
bid_num,win_num,cmsp_bag,theta,ctr_hist,mu,sigma
cdef int period, daybuget, gcpc, bidcap, bin_n
cdef double ctrbin, avgprice

def __init__(self,period,daybuget,gcpc,bidcap,ctrbin):
self.period = period
self.ctrbin = ctrbin

self.daybuget = daybuget
self.gcpc = gcpc
self.bidcap = bidcap

self.bid_num = np.zeros(period, dtype=np.int64)
self.theta = np.zeros(self.theta_bin, dtype=np.float64)

# ctrのhistグラムの格納
self.bin_n = int( float(1.0)/ctrbin )
self.ctr_hist = np.zeros((period,self.bin_n), dtype=np.int64)

self.mu = np.zeros(period, dtype=np.float64) # 入札閾値のtauの各slot毎の平均値
self.sigma = np.zeros(period, dtype=np.float64) #入札閾値のtauの各slot毎の分散
self.avgprice = 0.0

def __dealloc__(self):
pass

def output(self, file,user_agent_num,bid_agent_num,days):
cdef int t,n,i,c,b

# visit prediction の算出
pred_creater = CreatePredict(self.period, user_agent_num)

# user agentの発生
user_agent = [ useragent.Agent(n) for n in xrange(user_agent_num) ]

# bid agentの発生
bid_agent = [ bidagent.Agent(n) for n in xrange(bid_agent_num) ]

for t in xrange(self.period*days):
self.time = fmod(t,self.period)
if fmod(t,self.period)==0:
if self.day!=0: self.avgprice /= sum(self.win_num)
self.bid_num = np.zeros(self.period, dtype=np.int64)
self.win_num = np.zeros(self.period, dtype=np.int64)
self.cmsp_bag = np.zeros(self.period, dtype=np.float64)
self.day+=1

print "progress:",t

# visit predictionの算出
pred = pred_creater.getvalue(self.period)
# 各slotの予算配分の計算
slot_bag = self.calc_slot_bag(pred)

# 訪問者のctrを取得
ctr = []
bidp = []
visit = 0.0
dbidprice = {}
for i in xrange(user_agent_num):
ctr.append( user_agent[i].get_visiter_ctr(pred[self.time]) )

# 各agentの入札額の算出
if ctr[i] == False: continue
visit += 1.0

""" ctrのヒストグラムを作成 """
if self.day==1: self.get_hist(ctr[i])

maxprice = 0.0
for b in xrange(bid_agent_num):
price = bid_agent[b].get_bid_price(ctr[i], pred[self.time])
if price > maxprice:
maxprice = price
bidp.append(maxprice)

""" 応札回数のカウントと入札額の決定 """
# 応札価格設定に使用するpacing_rateを算出
if self.bid_num[self.time]==0:
pacing_rate = 0.0
else:
pacing_rate = self.bid_num[self.time]/float(visit)

# 応札価格の決定
bidprice = self.calc_bidprice(self.day, ctr[i], pacing_rate)
print 'price',bidprice

# 応札するかしないかの判断
if bidprice == False: continue

""" 算出された入札金額確認用の辞書作成 """
if str(floor(bidprice)) not in dbidprice: dbidprice[str(floor(bidprice))] = 1
else: dbidprice[str(floor(bidprice))] += 1

# 応札額がcapを超えていればcapの値とする
if bidprice>self.bidcap: bidprice = self.bidcap
# 応札するのであれば応札回数をインクリ
self.bid_num[self.time] += 1

# 入札に勝利したかの判定
if bidprice > maxprice:
# 応札するかどうかの判定
if slot_bag[self.time] - self.cmsp_bag[self.time] - bidprice > 0:
self.cmsp_bag[self.time] += bidprice
print 'cmsp=',self.cmsp_bag[self.time]
self.calc_theta(bidprice,maxprice)
self.win_num[self.time] += 1
# 1bid辺りの平均コストの計算
if self.day==1: self.avgprice += bidprice
print dbidprice
print np.float64(self.win_num)/self.bid_num
num1 = []
num2 = []
for i in xrange(self.period):
num1.append( str(slot_bag[i]) )
num2.append( str(self.cmsp_bag[i]) )
file.write(u'slot bags\n'+u','.join(num1)+u'\n')
file.write(u'comsumption bags\n'+u','.join(num2)+u'\n')

def get_hist(self,ctr):
""" ctrのヒストグラムを作成 """
cdef int bin
for bin in xrange(self.bin_n):
if bin*self.ctrbin<=ctr<(bin+1)*self.ctrbin:
self.ctr_hist[self.time,bin] += 1
break

def calc_bidprice(self, day, ctr, pacing_rate): #ctr[i]
cdef int i
tau = 0.0
if day<2:
if ctr>=0.2:
return random.randint(20,80)
else: return False
else:
if self.cmsp_bag[self.time]!=0.0:
# 予測impの算
imps = float(self.cmsp_bag[self.time])/self.avgprice
print 'imps',imps
# 予測応札数の算出
#win_rate = bid_num[self.time]/win_num[self.time]
bids = float(imps*self.bid_num[self.time])/self.win_num[self.time]
print 'bids',bids
# 予測リクエスト数の算出
print 'pacing_rate',pacing_rate
reqs = bids/pacing_rate
else:
reqs=0.0

print 'reqs',reqs
# 入札の閾値の取得
for i in xrange(len(self.ctr_hist[self.time,:])):
if sum(self.ctr_hist[self.time,-(i+1):]) - reqs >0.0:
tau = float((self.theta_bin-1)-i)/self.theta_bin
break

# 平均値の計算
if self.time == 0: t = self.period - 1
else: t = self.time-1 # ここでいうtはt-1とする
div_t = float(1)/(self.time+1)
self.mu[self.time] = self.mu[t]+ div_t*(tau-self.mu[t]) # muは現在のslotと過去のslot分の保存が必要かも
# 分散の計算
self.sigma[self.time] = div_t*t*self.sigma[t] \
+ div_t*(tau-self.mu[t])*(tau-self.mu[self.time])

# 暫定的な価格の決定
u = ctr*self.gcpc # Ui = AR*G(予測CTR×目標CPC)

# 応札率に応じて価格を決める
# beta1=0.3, beta2=0.8と設定する
price = self.get_price(pacing_rate,u)
print 'price1',price

# 応札するかの判定
return self.judge_bid(pacing_rate,price,tau)

def calc_theta(self,bidprice,secprice):
cdef int b
theta = float(secprice)/bidprice
for b in xrange(100):
if 0.01*b<=theta<=0.01*(b+1):
self.theta[b] += 1
break

def calc_slot_bag(self,pred):
s = sum(pred)
prop = np.array(pred, dtype=DTYPE)/s
return prop*self.daybuget

def get_price(self,pacing_rate,u):
price = 0.0
if pacing_rate<=self.beta1:
s_theta = sum(self.theta)
s = 0.0
for i in xrange(len(self.theta)):
s += self.theta[i]
if float(s)/s_theta>0.01:
return i*(float(3.0)/(2*self.theta_bin))*u #price = self.theta[i]*u
elif pacing_rate>=self.beta2: # pacing_rageの予測を行う必要があるかも
lo =1.0 + (self.bidcap/self.avgprice-1.0)/(1.0-self.beta2) \
*(pacing_rate-self.beta2)
return lo*u
else:
return u

def judge_bid(self, pacing_rate, price, tau):
term2 = self.gamma*self.sigma[self.time]/sqrt(self.day)
print 'tau',tau

if tau<self.mu[self.time]-term2: # 応札不採択上限
return False
elif tau>=self.mu[self.time]+term2: # 応札採択下限
return price
else:
if pacing_rate>random.uniform(0,1):
return price
else: return False

Cythonを使用する場合コンパイルが必要なため、一応setup.pyも記載しておきます。


setup.py

# coding: utf-8


from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext
import numpy as np

setup(
name="CPWOPTcritical",
cmdclass={"build_ext":build_ext},
ext_modules=[Extension("CySimulation",["CySimulation.pyx"])],
include_dirs=[np.get_include()]#ここでインクルードパスを指定
)

またCythonにしているため、main部分を分離しています。以下に記載します。


main

# coding: utf-8


#import pyximport; pyximport.install()
import io

if __name__=='__main__':
import CySimulation

period = 1440 # 1日のスロット数
daybuget = 1000000 # 1日の予算
goalcpc = 100 # 目標cpc
bidcap = 90 # 入札額キャップ
ctrbin = 0.01 # CTRヒストグラムのbinの大きさ
days = 2 # データ発生日数
user_agent_num = 600 # ユーザエージェント数
bid_agent_num = 100 # 入札エージェント数

bid = CySimulation.ComputeBid(period, daybuget, goalcpc, bidcap,ctrbin)

with io.open('sin_test','a') as f:
bid.output(f,user_agent_num,bid_agent_num,days)


実験結果

まあまあうまく行ってそうな感じだけど、データ発生手抜きした部分とか、過去データから予測する部分をサボった箇所で想定していたような値が出ていない感じがします。

設定がかなり細かいので、緻密に作成しないと十分な結果を得るのは難しそうです。


まとめ(感想)

かなりヒューリスティックなやり方ですが、CVR推定と合わせて50ms以内といった速度が求められる条件下では一番使えそうな手法(論文)だな、と思います。この仕事について、入札金額最適化について初めに読んだ論文が上で紹介した論文でした。他の論文もいくつか読んだのですが、この論文のインパクトが最も強かったです。

IPとtime stamp以外のログが保存されている状態であれば、この手法ベースに実データで最適化してみたかったものです。残念です。

おかしな部分がありましたら、お手数ですがご指摘いただけますと助かります。