Help us understand the problem. What is going on with this article?

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

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以外のログが保存されている状態であれば、この手法ベースに実データで最適化してみたかったものです。残念です。

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

shima_x
分析とか雑用とかやってます
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away