こんにちは。アドテク事業でエンジニアをしている星野です。
主に広告配信・運用システムの開発を担当しています。

今回は、以前紹介いたしました弊社広告配信システムにおける広告配信最適化の取り組みについての記事の続きになります。

はじめに

私が担当している広告配信システムでは、主に純広告を扱っています。
純広告とは、特定のメディアの広告枠を買い取って掲載する広告のことです。メディアから買い取った広告枠の掲載期間におけるインプレッション数（表示回数）を広告在庫と呼びます。
純広告では、この広告在庫を効果的に消費してクライアント様の商品を購入してもらうなどの目的を達成（コンバージョン）する必要があります。
広告配信システムでは、効果の良い広告クリエイティブ（バナーなどの表示物）を模索したり、広告枠ごとのフリークエンシー（配信頻度）を考慮した広告配信の最適化を行なっています。

前回までのあらすじ

広告配信最適化の一環として、広告クリエイティブごとに配信量の調整を行っています。配信量の調整方法について現行システムでは以下の3通りのいずれかを行なっていました。

均等配信（広告クリエイティブの効果によって運用者が手動で調整を行う場合もある）
Thompson samplingを用いてクリック数が最大になるように配信
運用者による運用のシステム的な再現（均等配信→コンバージョン（CV）がついた広告クリエイティブの配信量を増やす）

しかし、これらの調整方法では、一部の広告クリエイティブに偏った配信が行われるまたは、ほとんど偏らず均等なままの配信量となっていました。そのため、運用者を介してさらに手動での調整が行われてしまっていました。

本記事では、これまでの自動調整システムの課題を解消した自動調整システムを提案・実装した内容を紹介いたします。

広告配信量調整アルゴリズムの選定

前回記事の改善案の項目でも触れていますが、純広告というのはメディアの広告枠（例えばトップページの一部など）を一定期間使用し続けるため、同一ユーザーへのフリークエンシーが多くなったりします。そのため、同じ広告を配信し続けてもあまり効果的ではありません。
広告配信システムの運用者は、広告クリエイティブのフリークエンシーを減らすために広告枠の配信ボリュームに合わせて複数の広告クリエイティブを入稿しています。また、各広告クリエイティブの広告効果に合わせて、それぞれの配信量を調整しています。

今までの広告配信量調整アルゴリズムは、運用者の手を完全に離れておらず手動での調整も混ざっていました。新しい広告配信量調整アルゴリズムでは、運用者がほとんど手をつけなくてもいいようなアルゴリズムを考えたいと思います。

シミュレーション

広告配信量の調整アルゴリズムも多腕バンディット問題が応用できます。

こちらの書籍を参考にシミュレーションを行いました。

ウェブ最適化ではじめる機械学習 ―A/Bテスト、メタヒューリスティクス、バンディットアルゴリズムからベイズ最適化まで

作者:飯塚修平
オライリー・ジャパン

Amazon

シミュレーションに使用したコードです。

import numpy as np
np.random.seed(0)

n_arms = 7
cl_reward = 1
cv_reward = 300

class Env(object):
  thetas = [0.0037, 0.0053, 0.0072, 0.0104, 0.0031, 0.0077, 0.0074]
  conversion = [0.012, 0.053, 0.022, 0.0001, 0.081, 0.027, 0.034]

  def react(arm):
    reward = cl_reward if np.random.random() < Env.thetas[arm] else 0
    # 低確率でCVが発生する
    if reward > 0 and np.random.random() < Env.conversion[arm]:
      reward += cv_reward
    return reward

  def opt():
    ctvr = [Env.thetas[l] * Env.conversion[l] for l in range(n_arms)]
    return np.argmax(ctvr)


def sim(Agent, N=100, T=100000, r=100, **kwargs):
  selected_arms = [[0 for _ in range(T)] for _ in range(N)]
  earned_rewards = [[0 for _ in range(T)] for _ in range(N)]
  earned_cvs = [[0 for _ in range(T)] for _ in range(N)]
  tmp_arms = [0 for _ in range(r)] 
  tmp_rewards = [0 for _ in range(r)] 

  for n in range(N):
    agent = Agent(**kwargs)
    for t in range(T):
      arm = agent.get_arm()
      reward = Env.react(arm)

      # 報酬はバッチでまとめて受け取る
      tmp_arms[t % r] = arm
      tmp_rewards[t % r] = reward
      if (t > r - 1) and (t % r == 0):
        for i in range(r):
          agent.sample(tmp_arms[i], tmp_rewards[i])

      selected_arms[n][t] = arm
      earned_rewards[n][t] = reward
      if reward == cl_reward + cv_reward:
        earned_cvs[n][t] += 1

  return np.array(selected_arms), np.array(earned_rewards), np.array(earned_cvs)

何か所か書籍のコード例から変更しています。

armsを7本にして確率はそれぞれCTR（Click Through Rate）を参考にした数値に
クリック後さらに低確率でCVが発生してさらに報酬をもらえるように
報酬の受け取りはバッチを想定して、一定配信後にまとめて受け取るように
CVの報酬はクリックの300倍貰えるように

報酬をクリックとCVの2段階に分けたのは、クリック発生時ではなくCV発生時に売り上げが発生する広告を再現したかったためです。

ε-greedy

まずバンディットアルゴリズムで一般的なε-greedyです。CTR、CVRが小さいので探索率epsilonは少し大きめにしました。

class EpsilonGreedyAgent(object):
  def __init__(self, epsilon=0.3):
    self.epsilon = epsilon
    self.counts = np.zeros(n_arms)
    self.values = np.zeros(n_arms)

  def get_arm(self):
    if np.random.random() < self.epsilon:
      arm = np.random.randint(n_arms)
    else:
      arm = np.argmax(self.values)

    return arm

  def sample(self, arm, reward):
    self.counts[arm] += 1
    self.values[arm] = (
        (self.counts[arm] - 1) * self.values[arm] + reward
    ) / self.counts[arm]

あとは書籍に倣ってOracle（CTVRが一番高い広告を配信し続けた場合の理論値）とRandom（均等配信）とε-greedyの獲得CVで比較してみます。

横軸が配信回数で縦軸がCV数です。
Oracleが理論上の最大効率になります。Oracleに近い方策ほど良い方策と解釈します。 ε-greedyは序盤少し負けてますが均等配信よりもCVを獲得できていそうです。

その他のアルゴリズム

同様に、UCB（Upper Confidence Bound）やThompson samplingとオリジナル（運用者による運用の再現したアルゴリズム）のクラスも実装し比較しました。

UCB以外はだんごですね。

新規自動調整アルゴリズム

今回は、比較的実装が容易なε-greedyを採用しました。シミュレーション上でもわずかに上昇を続けており、実際の広告配信ではインプレッションがさらに多くなることを加味すると十分にポテンシャルがあると判断しました。
シミュレーションで一番よかったUCBは、配信システムの都合上実装が難しくなりそうだったため採用を見送りました。また、広告グループ内の広告クリエイティブは定期的に入れ替えられていることから、温度パラメータがある方策は扱わないことにしました。

広告配信量最適化でやりたいことは、CVにつながらない広告クリエイティブの配信量を下げてCVされやすい広告クリエイティブの配信量を上げることです。運用者と協議した結果、新規自動調整アルゴリズムは以下のようになりました。

クリックを1、CVは広告グループ内のクリエイティブの平均クリック数2日分くらいとして各広告クリエイティブの報酬を計算する
コンバージョン率（CVR）が広告グループの平均を下回る広告クリエイティブの報酬を半額にする
報酬の多いN個の広告クリエイティブを活用グループとする
探索率εで広告グループ全体からランダムに広告クリエイティブを配信
活用率1-εで活用グループの広告クリエイティブからランダムに選んで配信

1によって、序盤はクリック率（CTR）の高い広告クリエイティブを優先して配信、時間が経つにつれてCVされやすい広告クリエイティブの報酬が高くなるのが狙いです。
2は、クリックばかりされてCVにつながらない広告クリエイティブの評価を下げて配信されにくくする狙いがあります。
3以降について、本広告配信システムではフリークエンシーが高めのため、報酬順に配信比率を割り振るのではなく、上位複数の広告クリエイティブでまとめて配信を分け合うことで各広告クリエイティブのフリークエンシーを下げて枯れにくくしようとしています。

このような自動調整アルゴリズムを実装し、半年ほど運用を行いました。

まとめ

運用当初からパラメータの微調整は行ないながらも安定して運用できています。配信量の調整において運用者の手動介入も減り、運用者の負担の軽減を行えました。
これからは、運用者の負担軽減だけでなく、CVをより多く獲得できるようにアルゴリズムを改良していけたらと思います。

以上、広告運用改善に向き合うエンジニアの取り組みでした。

Devlog by Reazon Holdings

続・広告運用改善に向き合うエンジニアの取り組み