[DL輪読会]TV Advertisement Scheduling by Learning Expert

DEEP LEARNING JP [DL Papers] “TV Advertisement Scheduling by Learning Expert” Matsuo Lab, Ryo Okada http://deeplearning.jp/ 1

• http://deeplearning.jp/

書誌情報 • タイトル – TV Advertisement Scheduling by Learning Expert • 著者 – Yasuhisa Suzuki, Wemer Wee and Itaru Nishioka – NEC Corporation • KDD 2019 2

概要 • 広告主からの曖昧な条件や固有ルールがあり、自動化が難しい領域 とされてきたTV広告のスケジュールの最適配置の自動化に取り組ん だ論文。 • 熟練者の意思決定プロセスを真似るため、逆最適化やクラスタリン グを利用した意図学習を利用したデータ・ドリブンアプローチを提 案。 3

既存研究 • TV広告スケジュールの最適配置問題を扱った事例 – 数理的プログラミングで広告スケジュール生成 • 広告主のリクエストの競合を解消を図る（USのNational Broadcasting Companyにて活 用） 広告収益を最大化 • – 課題 • 様々な広告主や放送局自体の要望を考慮できていない。 • （すべてのリクエストが揃った段階でスケジュール再生するのではなく）リクエストが 届いた段階で１つずつ対応する必要がある。 • 逆最適化（Inverse Optimization） 専門家の行動から意思決定タスクを改善できる可能性から、多くの分野 （online setting, imperfect observations, multi-objective setting）で利用されてきた • 逆強化学習（Inverse Reinforcement Learning） – IOに比べ、確率分布に基づくため尤度最大化や最尤推定の問題として扱える （準最適な動作をノイズとして説明できる） – MaxEnt IRLアプローチは熟練者の行動履歴から目的を復元するタスクにて SOTA（本論文でもIOを拡張させるアプローチとしてこの手法を採用） 4 •

TV広告スケジュールの最適配置問題 ①広告リクエスト届く ②スケジュール作成 ③交渉 ④完成 要件に基づいた自動生成 本論文での対応方法 要件に基づいた自動生成 数理最適化（先行研究あり） TV放送局と広告主との交渉の負担の軽減 逆最適化による熟練者の意図学習 コールドスタート問題（新しい会社や商品の広 告リクエストの対応） クラスタリングして置いた中から類似グループ を見つけて対応 5

定式化
•

広告主と放送局の両者の観点
– 広告主
• ブランドイメージ
• GRP（total gross rating
point）を最大化したい

– 放送局
• スロット（広告枠）を効率的に
使って多くの広告を受け入れ、
収益を増やしたい

•

上記の要件を反映させた目的関
数を定義したい

•

テレビ広告iに対する目的関数
–

•

%
%
𝐽! = 𝜃!,#$
𝜙#$ 𝑥! + 𝜃!,&'$
𝜙&'$ (𝑥! )

最適問題
–
–

•

•

max 𝜃!% 𝜙(𝑥! )

(% ∈ *,+ &%

•

s.t. 𝑥! ∈ 𝑋(𝑢! )

前提
–

𝑥!,# ： 決定変数. スロットjに広告iが配置
される場合 𝑥!,# = 1. それ以外0.
スケジュール全体は列ベクトル𝑥! ∈ 0,1 $!
で表現(全ての𝑥!,# が含まれ、𝑛! はiの契約期
間のスロットの総数).

–

𝑢! ：制約事項

–

•

テレビ放送局の特徴𝜙!"
– スケジューリング実施後の全てのスロットの
残り総秒数
– スケジューリング実施後の最も高いスロット
の残り秒数
広告主の特徴𝜙#$"
– それぞれの時間スロットから得られる総GRP
– 平日の間得られた総GRP
– それぞれのスロットタイプに対して得られる
総GRP
– 各時間ランクで取得された総GRP
制約
– スロットの残り秒数は負にならない
– GRPは求められるものより少なくなってはな
らない
– テレビ広告の時間制約は可能なら満たす

この最適問題を解くことによってスケジュールは得られるが、様々な広告主やブランドにして柔軟
に対応できない
->熟練者の過去の行動から意図を捉え、𝜃 ! を得られるようなIOを利用する（提案手法）

6

Solution Overview • 構築したシステム – Learning component • – • • 似た放送ポリシースケジュールでグループ化 するためにクラスタリングを実施. クラスタ毎逆最適化をし、目的関数を学習。 入力 • 出力 – 広告リクエストデータ – 専門家のスケジュール – クラスタ – 目的関数 Scheduling component • • テレビ広告データを入力し、放送ポリシーや 性質に基づく適切なクラスタを選ぶ。クラス タごとに学習した目的を利用して最適化問題 を解き、広告に対する適切なスケジュールを 取得する。 入力 • 出力 – テレビ広告 – スケジュール 7

クラスタリング • 番組特性や視聴者ターゲット層な どの情報は構造化されておらず取 得しづらい • 熟練者が作成した過去のスケ ジュールから特徴量抽出して利用。 • テレビ広告の放送ポリシーは段階 的なマナーによって作られるため、 階層的クラスタリング （Agglomerative Hierarchical Clustering）を使用 – 例：商品の性質に基づいてターゲット 視聴者が決められ、ターゲット視聴者 の好みによって優先プログラムを決め る。 8

逆最適化（Inverse Optimization） • • クラスタリング後、クラスタ毎目的関数を学習するため、 逆最適化を実施 最大エントロピーの原理に基づく確率的逆最適化 （MaxEnt IO）を利用（本論文の独自性） • • 以下のような尤度最大化問題として扱う max 𝑝(𝑋% |𝜃% ) # • • 尤度関数はMaxEnt IRLにて用いられる以下分布 & 𝑝 𝑥! 𝜃% = '(" ) exp(𝜃%* 𝜙(𝑥! )) • • • • • • ""∈ℝ $ – " 𝑍 𝜃% = ∑& & ∈((* ) exp(𝜃%, 𝜙(𝑥- )) % % 勾配 ∇ log 𝑝 𝑥! |𝜃% = 𝜙(𝑥! )-𝔼+(,.,|"") 𝜙(𝑥!, ) 第２項はサンプルベース手法で近似可能(MaxEnt IRLにて 証明). iに対する条件をもとに生成されたスケジュール の特徴量で近似される ∇ log 𝑝 𝑥! |𝜃% ≈ 𝜙 𝑥! − 𝜙(𝑥!/ ) パラメータ更新は以下のとおり , 𝜃%012 = 𝜃%345 + 𝛼 ∑7 !6&(𝜙 𝑥! − 𝜙(𝑥! )) 9

アルゴリズム全体 10

Experiments • データ – – – – 2019/07~2019/12の日本の放送局のデータを使用 広告の総数：3260 train70%（約2300広告）, test30%（約1000広告） Trainデータはlearning component, testデータはシステム全体の評価に使 用。 11

クラスタリング結果・考察 • 大きなクラスタDはTable1を見ると 様々な商品があり、特定の強い放送戦 略がないことを示している • 小規模、中規模のクラスタは大規模の クラスタに比べて特定の放送戦略があ り、Dより優先されうる。 – Aは単一の商品（ソーダ） – Cはアルコール類 12

MaxEnt IOに関する結果・考察 • 目的関数の学習をヒートマップに可視 化（House cleaning product） • 2 p.mと6p.mのスロットが高め。主婦 や退職者をターゲットに放送している • 朝も高め。家族と朝食を取りながらテ レビを見る層をターゲットにしている。 13

⽣成されたスケジュールの結果・考察 • 以下３つの配置戦略において熟練者 スケジュールとの乖離を比較 – OR1, 残り秒数の最大 – OR2, GRP超過の最小化 – MaxEnt IO • MaxEnt IOは乖離が最も少なく、熟 練者のスケジュールに近い。 14

まとめ • TV広告最適配置の自動化に対するデータドリブンアプローチを提案。 • 逆最適化を拡張し、熟練者の作成するスケジュールを模倣することを 目的に熟練者の意図を学習する。 • 日本のテレビ局の実際のデータを使用して提案システムの有効性を確 認。 • Future work – 自然言語処理を用いたクラスタアサインの自動化 – 提案システムのオンライン実装の評価 15

THANK YOU. 16