Kdd 2021 読み会(clustering for private interest-based advertising & learning a logistic model from aggregated data)

KDD 2021読み会(https://connpass.com/event/223966/)で使用したスライドです．
近年のユーザープライバシー保護の流れから、ターゲティング広告事業者は従来の広告配信機構の変化を要請されている。 これらの流れに対する取り組みとして、プラットフォーマー側からはGoogleのFederated Learning of Cohorts(FLoC) APIに関する論文を、配信事業者側からはCriteoの集計データを用いた予測モデルアプローチをそれぞれ紹介する。

Transcript

1. KDD読み会
 AI事業本部 Dynalyst 金子 雄祐
 1
2. 自己紹介 2 名前: 金子 雄祐(29) 職業: AI事業本部 Dynalyst データサイエンスチームリーダー 経歴: 2018: 東京大学大学院経済学研究科統計学コース卒 (修士) 2018年: CyberAgent 新卒入社 2019年: Dynalyst異動 やってるタスク: 予測モデル開発, クリエイティブ評価&最適化改善, チームマネジメント paper: Kenshi Abe, Yusuke Kaneko: “Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games” AAMAS 2021 twitter: @coldstart_p 
 kaggle:
 @ykaneko1992

3. 発表の流れ
 • 近年のプライバシー保護とターゲティング広告の流れ
 • プラットフォーマー側の取り組み
 ◦ "Clustering for Private Interest-based Advertising"(Google)
 • 広告配信事業者側の取り組み
 ◦ " Learning a logistic model from aggregated data"(Criteo)
 3
4. 近年のプライバシー保護とターゲ ティング広告の流れ
 4
5. AppTrackingTransparencyフレームワーク 5 Apple公式サイトより
 
 iOS 14.5より AppTrackingTransparency(ATT) フレーム ワークが適用
 
 App内でのユーザー識別子の利用をオプ トイン式に変更する取り組み 
 
 

6. プライバシー保護とターゲティング広告 6 • 近年，Web上におけるプライバシー保護 は非常に重要な問題 
 ◦ (是非は置いておくとして)ユーザー行動のトラッキングをベースにしたビジネスモデルは変化や適応を 余儀なくされている
 • 色々な出来事(3rd party cookie規制 → IDFA規制の流れ) 
 ◦ 2018年5月 : 欧州でGDPR制定 
 ◦ 2020年1月 : アメリカでCCPA(カリフォルニア州消費者プライバシー法)制定 
 ◦ 2021年4月 : iOS14.5, ATTリリース 
 • 上記の変更に置いてターゲティング広告配信事業者(DSP/SSP)が困難になること 
 ◦ 広告効果の適切な計測
 ▪ 広告をclickした後のユーザー行動計測が困難に 
 ◦ 効果的なターゲティング広告 配信
 ▪ そもそも識別子が流れてこないのでターゲティングもなにもない 

7. Google, Appleの動き 7 • デバイス提供を行うプラットフォーマー(Apple, Google) 
 ◦ Apple 
 ▪ ATTフレームワークの提供など，先進的にプライバシー保護を促進 
 ◦ Google
 ▪ Appleに追随しつつも，DSP/SSP事業者にはまだ優しい対応 
 ▪ Chromeでの22年までの3rd party クッキー廃止 
 ▪ 代替的に, プライバシー配慮を行う広告プラットフォーム， プライバシーサンドボックスフレーム ワークの提案
 • Googleのほうが広告事業者としての色が強いので，両社の対応の違いが(多分)出ている 

8. FLoC 8 • Federated Learning of Cohorts(FLoC) はプライバシーサンドボックスの仕様の一つ 
 • 結局何をやるのか?
 ◦ MLで利用者のインターネット利用動向をデバイス上で分析 
 ◦ これらのユーザーを類似性で分類 
 ◦ 上記の分類ごとにクラスタIDを割り振り広告配信に活用するためにDSPやSSPに提供 
 • 上記FLoCの業界の評判は，正直，非常に よろしくない
 ◦ FLoCがブラックボックス過ぎる
 ◦ クラスタIDをデポジットしておけば 個人識別が可能になる可能性がある 
 ◦ 第三者の広告配信事業者は Googleのエコシステムに入らざるを得なくなる 
 • なので，いずれ撤回されるだろう...というのが(KDD前の金子の)なんとなくの見立てだった 

9. FLoCの論文を公開 9 • KDD2021で初めてFLoCの仕様に関する論文が公開された 
 • (多分)PR目的なのだろうが，少なくとも完全なブラックボックスではなくなった 

10. DSP側の動き 10 • 配信事業者(DSP)も色々な選択を迫られている 
 • 大きな流れとしては以下? 
 ◦ Googleのプライバシーサンドボックスに乗っかる 
 ◦ 代替的な識別IDを第3者事業者合同で立ち上げる 
 • 正直あまり業界の流れがfixされたとは言い難い 
 • Q :「Googleのプライバシーサンドボックスに乗った場合，予測モデルはどう作ればいいのか? 」
 ◦ 要するに，aggregatedなデータしか得られなくなるので従来の予測モデルが機能しなくなる 
 ◦ これに応える論文がCriteoからAdKDD 2021で提案 
 ◦ こちらの論文も紹介 

11. Clustering for Private Interest-based Advertising
 11
12. Intro 12 • インタレストベース広告(IBA)は広告主がユーザーの関心に基づいた広告表示を可能にするシステム 
 • 市場効率を高める強力な広告である一方で，これを可能にするにはアドテク企業は個々のユーザーの詳 細なインタレストプロファイルを構築する必要がある 
 ◦ 52社の広告会社が収集した情報は，ユーザーの閲覧履歴の 平均91%を復元できるとの調査も 
 • 細かいパーソナライゼーションが必要かどうか再度問い直し， ユーザープライバシーを保証しながら競争力 のあるパフォーマンスを実現する広告メカニズムの提示 を目的とする
 ◦ 要するにCookieを使用せずにIBAを実現することを目指す 
 • FLoC APIの提案
 ◦ ideaは，ユーザーをk個の匿名グループに分類し個人ごとではなくグループごとにプロファイルを作成 できるようにするというもの 
 ◦ これが現在のユーザープロファイル作成のフレームワークを置換するのに十分かは非自明 

13. FLoC API 13 • FLoC APIで生成されるコホートIDは以下の性質を持つべき 
 ◦ コホートIDは複数のユーザーで共有されるため，単独で使用した場合はウェブサイト間でユーザーを 再識別することはできない 
 ◦ IDは，全く同じ関心事を共有する多数のユーザーで構成される 
 • 要するにコホートID割当は単なるクラスタリング問題と解釈可能だが，以下の制約を持つ 
 ◦ 𝐾-anonymity : 各コホートIDは少なくとも 𝑘人のユーザーが共有しなければならない 
 ◦ Local computation：コホートIDはできれば監査が容易な方法でブラウザ内で計算する必要がある 
 ◦ Central server trust : (正直要領を得ない記述だったが)現状の規制がかかっていない各種事業者が それぞれユーザープロファイルを持ってるのは少なくとも良くないよねという話 

14. Algorithm 14 • FLoC APIのクラスタリングアルゴリズムを設計する際には，実装のしやすさ，解釈のしやすさ，デバッグのし やすさを考慮する必要がある 
 • これら以下の3つからなるが，簡単な順に説明する 
 ◦ SimHash
 ◦ SortingLSH
 ◦ Graph-based clustering method 

15. SimHash 15 • SimHashはLocality Sensitive Hashing (LSH)ファミリーのアルゴリズムの一種 
 ◦ 当初は重複している文書を素早く識別することを目的に開発された 
 ◦ 𝑑次元ベクトル𝑥を入力とし，pビットのベクトル 𝐻𝑝 (𝑥)∈{0, 1}𝑝を出力するが，これを 𝑥のハッシュと呼ぶ
 • ハッシュベクトルの𝑖番目の座標は以下のルールで求められる 
 ◦ ただし，w i はunit-normの確率ベクトル 

16. SimHash 16 • SimHashは似たようなベクトルは似ていないベクトルよりも同じコホートIDにハッシュ化される可能性が高い という特性を持つ
 ◦ より正確には𝑥 1 と𝑥 2 が2つのベクトルである場合， 𝑥 1 と𝑥 2 が同じ𝑝ビットのコホートidにマッピングされる確 率は以下式のように与えられる 
 ◦ ただし，θはx 1 とx 2 の間の角度を意味する 
 • 要するに，x 1 とx 2 の間の角度が小さかったり，コサイン類似度が高くなると同じクラスタに入りやすくなる式 

17. SimHash 17 • SimHashを使う主な利点は あるユーザーのID計算が他のユーザーの情報に依存しない こと
 ◦ ベクトル𝑥が与えられれば，そのコホートidは他のユーザーの情報を知らなくてもクライアントで計算可 能
 • また，コホートIDを計算するために中央でデータを収集する必要もない 
 ◦ 中央サーバーがユーザーの閲覧履歴を保存することなくクラスタリングが可能になる 
 • SimHashの主な欠点は、最小のクラスタサイズを強制することができないこと 
 ◦ この問題は各コホートのサイズを追跡する匿名性の高いサーバーを用意することで解決できる 
 ◦ このサーバーはコホートの規模が十分でない場合APIがコホートIDを返すのをブロックすることが可能 

18. SortingLSH 18 • SimHashアルゴリズムを定義するビット数 𝑝の選択は非常に重要 
 ◦ 低すぎるとコホートが大きくなり，異種のユーザーが同じコホートに属する可能性が高くなる 
 ◦ 高すぎると𝑘-匿名性の要件に違反する 
 • 𝑝の選択の難しさは，SimHashで生成されるコホートのサイズが非常に不均一であるという事実によってさら に悪化する
 • SortingLSHは，この問題を解決しk-匿名性を確保すると同時にSimHashの品質を向上させる手法 
 ◦ コホートのサイズを均一化することで達成される 
 ◦ SimHashクラスタを後処理して 𝑘-anonymityを確保することを行う 

19. SortingLSH 19 • ℎ 𝑖 =𝐻 𝑝 (𝑥 𝑖 )を，SimHashがユーザ 𝑖に対して生成したpビットのハッシュを表すとする 
 • SortingLSHは，ユーザーをSimHashでグループ化してコホートを割り当てるのではなく以下のようにコホート を生成する
 ◦ (1) ℎ 1 , .. ... , ℎ 𝑛 を辞書的順序でソートして，ハッシュℎ (1) , … ,ℎ (n) のソートされたリストを得る 
 ◦ (2) ソートされたハッシュを，少なくともk人のユーザーを含む連続した区間に分割してコホートに割り 当てる
 • order付けのステップは，この順番で連続したハッシュがほとんど類似したSimHash値を持つユーザーに対 応することを保証し，区間のサイズ制約はコホートが常に少なくともk人のユーザーを持つことを保証する 
 • intervalの選択問題に関しては，PrefixLSHというアルゴリズムを使用している 

20. Graph-based clustering methods 20 • グラフベースのクラスタリングアルゴリズムを使用している 
 • (時間制約上)詳しくは触れないが，以下の3ステップがある 
 ◦ (1) graph construction : ユーザー間のコサイン類似度で重み付けしたグラフを作成 
 ◦ (2) graph clustering : Affinity hierarchical clusteringとMETISという2つのアルゴリズムを使用，比較 評価する
 ◦ (3) post-processing : Llyod’s clustering improvement roundsなどの種々の後処理を実行 

21. EVALUATION ON PUBLIC DATASETS 21 • Movielens 25Mと Million song datasetという2つのデータセットを使って評価している 
 • クラスタリングアルゴリズムの品質を評価するために，類似したユーザーをグループ化する能力を測定する 
 ◦ “平均的な”コサイン類似度を用いてこれを評価する 
 • 各アルゴリズムのプライバシー特性を評価するために，以下の匿名性指標，anon-quantileをもちいる 
 ◦ ただし，U(k)は少なくとも 𝑘のサイズのコホートに含まれるユーザー数 
 ◦ つまり，𝛼 fractionのユーザーが 𝑘-anonymousであるコホートに属するような最大の 𝑘

22. EVALUATION ON PUBLIC DATASETS 22 • 結果は左図
 • 正直これだけ見せられても...という感じはする 
 • anon-quantileが離れてもそこそこの平均的なコサイン類似 度は保たれていそう 

23. Learning a logistic model from aggregated data
 23
24. Learning a logistic model from aggregated data 24 • AdKDDのpaper
 • 著者はCriteo所属

25. Learning from aggregated data 25 • 従来得られているデータは左のTable 1のようなデータ 
 • 個人Idによる識別が不可能になると，例えばTable 2のような 集計データしか得られなくなる 
 • このようなデータしか得られなくなった時に，既存の予測モデ ル(CTR予測など)は機能しなくなる 
 • どのようなモデルを使えばいいのか? 

26. Formalizing the aggregated data 26 • そもそも集約データの問題はどう定式化できるか? 
 • 特徴量とラベルがi.i.d.に(x i, y i )で与えられるとする 
 • xを{0;1}DにマッピングするQuadratic kernel Kが与えられたとする 
 • この時，集計データは以下の式で表現できる 

27. アプローチ 27 • 以下のようなアプローチを取る 
 • Modeling
 ◦ 特徴量XとラベルYの 結合分布に関するパラメトリックモデルを選ぶ 
 ◦ P θ (X = x, Y = y)
 • Training
 ◦ 尤度最大化を達成するθを選ぶ 
 ◦ Argmax θ P θ (S = s, C =c)
 • Predict
 ◦ 上記で得られたθから，以下の条件律から予測を行う 
 ◦ P θ (Y = 1 | X = x) = P θ (X = x, Y = 1) / ( P θ (X = x, Y = 1) + P θ (X = x, Y = 0))

28. Markov Random Field 28 • Modelingの時に，以下のパラメトリックモデルを使用する 
 ◦ P μ, θ (X = x, Y = y) = exp(K(x)・μ + y・K(x)・θ) / Z μ, θ 
 ◦ ただし， Z μ, θ は正規化のための定数 
 • 上記のモデルは，Markov Random Field の一種と解釈できる 
 • この時，Predictは以下の式で可能になる 
 ◦ P μ, θ (Y=y | X=x) = σ(K(x)・θ) 
 ◦ Zもμも関係なく，カーネルKが存在する場合のロジスティック回帰と解釈可能 
 • Trainingは対数尤度のgradientの式が簡単に得られるので，MCMCなどで推定 

29. Experiments 29 • CriteoのPublic dataset(上)とCriteo AdKDD challenge(下)のデータセットで実験 
 • featureは10 ~ 20とかそこらへん 
 • 精度はそこそこ出るけどやっぱ重い... 

30. 課題 30 • 最適化重すぎ
 ◦ ギブスサンプラーがやっぱ重いとのこと 
 • Validationどうする? 
 ◦ 集約されてないデータでCVやってるのが現状 
 ◦ 集計データでどうやってCVかけるの? 

31. まとめ/雑感 31 • 近年のプライバシー保護の流れから出てきた広告事業者の取り組みに関連した論文を2本紹介 
 • FLoCが採用されていくかは正直わからない 
 ◦ プライバシー保護の名目でどんどんプラットフォーマー側の力が強くなっていく 
 ◦ 事前に感じていたブラックボックス感は大分なくなったが... 
 • DSP側もかなり厳しい対応が必要になっていきそう 
 ◦ paperの定式化自体は面白いし鮮やか 
 ◦ ただ実務的に本当にMarkov Random Fieldとか回すの? というと... 
 • 今後広告事業の風景がどうなっていくかはわからないが，時事的な流れを切り取ったpaperとしては一定の 面白さがある