---
title: [DL輪読会]TV Advertisement Scheduling by Learning Expert
tags:  #deep learning  
author: [Deep Learning JP](https://www.docswell.com/user/DeepLearning2023)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/PEXDLR9Y7X.jpg?width=480
description: 2020/03/27 Deep Learning JP:  http://deeplearning.jp/seminar-2/
published: March 27, 20
canonical: https://www.docswell.com/s/DeepLearning2023/K38LPM-dltv-advertisement-scheduling-by-learning-expert
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/PEXDLR9Y7X.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/3EKXLRP47D.jpg)

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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/L73538XDE5.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/87DD4M227G.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/VJPXMR1L78.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/2EVL9RY6JQ.jpg)

定式化
•
広告主と放送局の両者の観点
– 広告主
• ブランドイメージ
• GRP（total gross rating
point）を最大化したい
– 放送局
• スロット（広告枠）を効率的に
使って多くの広告を受け入れ、
収益を増やしたい
•
上記の要件を反映させた目的関
数を定義したい
•
テレビ広告iに対する目的関数
–
•
%
%
𝐽! = 𝜃!,#$
𝜙#$ 𝑥! + 𝜃!,&'$
𝜙&'$ (𝑥! )
最適問題
–
–
•
•
max 𝜃!% 𝜙(𝑥! )
(% ∈ *,+ &%
•
s.t. 𝑥! ∈ 𝑋(𝑢! )
前提
–
𝑥!,# ： 決定変数. スロットjに広告iが配置
される場合 𝑥!,# = 1. それ以外0.
スケジュール全体は列ベクトル𝑥! ∈ 0,1 $!
で表現(全ての𝑥!,# が含まれ、𝑛! はiの契約期
間のスロットの総数).
–
𝑢! ：制約事項
–
•
テレビ放送局の特徴𝜙!"
– スケジューリング実施後の全てのスロットの
残り総秒数
– スケジューリング実施後の最も高いスロット
の残り秒数
広告主の特徴𝜙#$"
– それぞれの時間スロットから得られる総GRP
– 平日の間得られた総GRP
– それぞれのスロットタイプに対して得られる
総GRP
– 各時間ランクで取得された総GRP
制約
– スロットの残り秒数は負にならない
– GRPは求められるものより少なくなってはな
らない
– テレビ広告の時間制約は可能なら満たす
この最適問題を解くことによってスケジュールは得られるが、様々な広告主やブランドにして柔軟
に対応できない
->熟練者の過去の行動から意図を捉え、𝜃 ! を得られるようなIOを利用する（提案手法）
6


# Page. 7

![Page Image](https://bcdn.docswell.com/page/57GXZM92EL.jpg)

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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/4EQ8LRW9JP.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/KJ42D81RE1.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/LE1MZ2GV7G.jpg)

アルゴリズム全体
10


# Page. 11

![Page Image](https://bcdn.docswell.com/page/GEW39RK3E2.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/47ZV9RZGE3.jpg)

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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/YJ65KRZQ7V.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/GJ5YP8W2J4.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/9E2G6KQ1ER.jpg)

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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/D7YV9NW47M.jpg)

THANK YOU.
16