View on GitHub

memo

Audience Expansion for Online Social Network Advertising

Audience Expansion for Online Social Network Advertising

LinkedInのAudience Expansionについて。 campaignは、advertiserの広告のことである。

LikedInでは、advertiserがreachしたい属性(location, age, skill, etc)を指定して、広告を出すことができる。 例えば、userのskillにData Miningを持つuserと指定した時には、Big DataやData Analysisなどを持つuserを対象にできると良い。 こういったkeywordや関連属性を全て網羅して指定することは、多くのadvertiserにとっては難しい。 LinkedInでは、Audience Expansionと呼ぶ手法を開発し、advertiserが指定した属性を自動的に拡張する方法を開発した。 Audience Expansionは以下の2つの要素からなる。

記載はないが、元々advertiserの指定した属性だけで会員に広告を出していたが、それだとメジャーなワードに一致する一部の会員が、広告の割当ができてなかったのかもしれない。 例えば、”Data Mining”とskillにある人に集中し、”Big Data Analysis”とskillに記載している人には広告の割当ができてなかった。 4億人の会員のimpressionの在庫を捌くことが主な目的でCTRとかは特に気にしてなさそう。

Introduction

Internet Adの3要素は以下のように関係している。

LinkedInでは以下の2種類の広告がある

userの属性(title, skill、働いている企業、LinkedIn group, etc）が多すぎてadvertiserが適切にtargetingできていないので、Audience Expansionを作った。 例えば、skillにOnline Advertisingをもつuserにtargetingした場合、自動でskillにInteractive Marketingと記載のあるuserにもreachできるようになる。

他のadvertising platformも同様の機能をもっているが、この手法は、conversion orientedである。 つまり、Advertiserが事前に指定したreachしたいuserを下に、そのuserのlistを拡張することができる。 Advertiserの中には、自身のmarketing部門に基いて、targetingを行いたい場合もあるため、この機能は基本的には無効であり、userは明示的にこの機能をONにすることで利用可能になる。

論文の成果は以下。

実際のproductionとして使っており、かなり(impressionは)良くなったらしい。

3.System

LinkedInのAudience Exapansion systemの概観。

3.1 Overview

LinkedInの広告の形態。 1ページに複数の広告枠がある。

advertiserはがcampaignを作る時、広告のformatを指定する。 また、予算を指定し、targetingを行う。 bidは、CPMかCPCで行う。 targetingは、以下が指定可能。 また各項目は、否定も設定可能。

例えば、locationがUSAかCanadaでCaliforniaでなく、ageは18-24か25-34で、seniorityがunpaid、trainingでないといった指定が可能。

(location == "USA" OR location == "Canada")
AND
(location != "California")
AND
(age == "18-24" OR age == "25-34")
AND
(seniority != "unpaid")
AND
(seniority != "training")

targetを決めるとbidの概算がadveritiserに表示されるとともに、Audience Expansionを使うどうかのオプションが表示される。

広告の掲載は、LinkdedInの会員がサイトに訪問した時に、空いている広告枠があれば開始される。 処理の大まかな流れは以下

Audience Expansionは2段階ある。

  1. 会員のprofileを取得する時に、会員情報を拡張
    • camplaign-agnostic
    • offlineのbatch処理
  2. 直接targetに指定されなかった会員に対して、targetに似ている会員も広告のtargetに含める
    • campaign-aware
    • offlineのbatch処理

3.2 Campaign-Agnositc Expansion

campaign-agnosticは Smilar-X algorithmに基づく。 Xは、profileの属性(company, LinkedIn Gropu, skill, job title, etc)が入る。 例えば、similar-Skillsの場合、Data Miningと指定したら、Big Data, Machine Learningといったものも会員の属性として加える。 Similar-X algorithmは後で解説するように、similarityをlogistic regreesionでscoreとして出力するmodelである。 この手法は、精度は悪いが、会員の情報のみからできるという点で、優れている。

3.3 Campaign-Aware Expansion

targetで指定された属性を会員へのlabelとみなす。 labelとみなすことで、labelに近いもの探す分類問題として考えることができる。

  1. offline match
    • targetで指定された会員をHadoop jobで列挙する
  2. Filter campaign
    • 似ている会員にtargetを拡張しても、有用でない広告をのぞく
    • 例えば、targetがそもそも広すぎるもの、targetを拡張せずとも指定予算をすぐに使い切ってしまうものなど
  3. expand audiences to similar profile
    • similar-profiles algorithmによって似ている会員に拡張する
  4. filter expansion
    • 得られた似ている会員から、もともとのtargetの否定条件を満たすもの、性別やlocationの条件に一致しないものを除く

最終的な出力は、campaign idとaudience idを紐付けてkey-value storeに保存される。

3.4 Hybrid Expansion

campaign-agnosticとcampaign-awareは補完的なので、組わせて使う。

4. Modeling

4.1 Feature Exgraction

Table1がLinkedInから抽出された特徴。

4.1.2 The Model

各、会社や会員をentityとして扱い、entityをmulti-fielded documentとみなして、field間の類似度をVector Space Modelで計算する。 類似度の計算はcosain類似度とする。

\[s(f_{i, s}, f_{j, t}) := \frac{ \langle V(f_{i, s}), V(f_{j, t}) \rangle }{ \|V(f_{i, s})\| \|V(f_{j, t})\| }\]

ここで、\(V(f_{i, s})\)はfiledのvector表現である。 これを用いて2つのentity間の類似度を次のように測る。

\[\mathcal{E}_{i, j} := \{ (f_{s}, f_{t}) \in V_{i, j} \mid (f_{s}, f_{t}) \in \mathcal{T} \times \mathcal{T} \vee (f_{s}, f_{t}) \in \mathcal{I} \times \mathcal{I} \}\]

このEdge \(\mathcal{E}_{i,j}\)を順序付けたものを\(E_{i,j} = ((f_{s}^{1}, f_{t}^{1}), \ldots, (f_{s}^{N}, f_{t}^{N}))\)とする。 Edgeから定まる類似度ベクトルを以下で定義する。

\[\mathbf{s}_{i, j} := ( s(f_{s}^{1}, f_{t}^{1}), \ldots, s(f_{s}^{N}, f_{t}^{N}) )\]

更に、各filedに重み$\mathbf{w}$を加えたものを最終的なentity $i$とentity$j$の類似度ベクトルとして定義する。

\[S(i, j) := \langle \mathbf{w}, \mathbf{s}_{i, j} \rangle\]

主に$\mathbf{w}$は、userのentityへの過去の行動ログから学習する。 例えば、2つの会社(entity $i$とentity $j$)が過去に同じように広告のtargetにされていれば重みを増やし、逆にtargetから外されていれば、重みを減らす。 このmodelに対して、elastic net regularizationによるlogsitc regressionで学習する。

4.1.3 Perosnolization

単純なSimilar-Xは、personalizationに弱い。 Company AとCompany Bがあったとする。 AとBはSimilar-Comaniesで似ているとする。 Bで働く会員の属性に、Aも加えられる。 つまり、Bで働く人は、Aをtargetとしてる広告のtargetにもなる。

これは、advertiserにとってもA, Bで働く人にとってもpersonalizeされていない。 personalizeするために、各userについてuserの好むentityと好まないentityの2値を学習する方法をとっている。 会員が好むentityの中で、上位$k_{x}$個($x$は各属性)取得する？ ちょっと詳細が読み取れない。

companyを例にすると、userとcompanyの特徴量を4.1.1.と同様に取得し、例えば、userがcompanyをfollowしていれば好む、unfollowしていれば好まないにする。 これをtraning dataとして、logistic regressionで学習する。

4.1.4 Similar-Profiles

Similar-Profilesは、会員のprofileに対するSimilar-X algorithとも言える。 LinkedInでは4億以上の会員に対してこれを行っている。 問題としては、この組み合わせだから4億の2乗である。

この大きなデータの中で、高いcosine類似度をもつ組を見つけるために、、Locality Sensitve Hashing (LSH) techniqueを使っている。 全ての会員は、$n$個のclusterにmapされ、そのclusterの中でのNearest Neighbor searchを行っている。

4.2 A Note on Implementation

campaign-awareでは、まずSimilar-Profilesに基づいて、もともとの広告のtargetを満たす会員を見つける。 この会員の上位層が、audience expansionの候補となる。 一人の会員にたくさんの広告が対象となることを防ぐために、全てのcampaignを拡張せずに、ある閾値以下のcampaingだけを拡張する。 これを達成するために、heuristicにmember-campaign fitness $F$という値を計算している。

\[\begin{equation} F(m, c) := \frac{ \sum_{m^{\prime} \in T(c)} S(m, m^{\prime}) }{ \sqrt{| T(c) |} } \end{equation}\]

$F(m, c)$がある値以下のものだけが、Audience Expansionの対称となる。 この閾値の直感的意味は、すでに元々のtargetに似ている会員については拡張をしないということである。 割ってnormalizeしているのは、campaign間でこの値を比較するためで、 分母でrootをとっているのは、best practiceである。

4.3 Other Considerations

4.3.1 Campaign Selection

全てのcampignでAudience Exapamnsionはしない.

このcampaignの選定はheuristicなruleに基いて行っている。 offlineのworkflow時に、この判断を行い、不要と判断した場合は、Audience Expansionは行わない。 このruleは以下の直感的な要請を満たすようにしている。

予算の推定は以下のように行っている。 campaignは、dailyの予算をオプションで指定でき、全体の予算を超えると、その後のauctionには参加できない。 そのため、予算を超えそうなことが予測された場合は、ad serverで pacing algorithmによって、randomにauctionからcampaignを除外するということを行う。 期間の中で、$M$回のauctionがあっても、参加可能なauctionが$N$回であれば、$N$回になるように、参加を制限する。

また、逆にAudience ExpansionをONにしていないcampaignであっても、期間の終わりごろに$r:= N/M$が1より少ないときは、Audience Expansionによっって、targetを増やす。

4.3.2 Post-Expansion Filters

Audience Expansionで対象となった会員に対して、元々のtarget条件に基いてfilterをかける。 特に、性別やlocationが指定してあった場合は、それらはskillなどより、強い条件とみなしてこの条件を満たさないものを除く。

拡張した会員の中で、costの高い会員は除く処理も行っている。 ここで、costの高い会員とは、会員の属性が他の会員より明らかになっている会員で、属性に関する情報の少ない会員より、より高いbidをつけられると予想できる。 これを、簡単な回帰モデルで以下のように予測している。

\[Y := \log \mathrm{Bid} = X\beta _ \epsilon, \quad \epsilon \sim \mathrm{N}(0, \sigma^{2})\]

である。 ここで、$X$は会員の属性である。 このモデルで拡張した会員のcostを算出し、上位$p$ %は対象から覗いている。

4.3.3 Online/Offline Sync

campaign-awareはofflineで行われる。 そのため、advertiserがcampaignのtargetをonlineで変更した場合に、以前のtargetに基づくAudience Expansionではadvertiserのtargetと齟齬が生じる。 齟齬がおきないように、advertiserのcampaignの設定とAudience Expansionのoffline処理にそれぞれtimestampをつけ、campaignのtimestampの方が古いかどうかを確認している。

5 Experiments

5.1 Paarameter Setting

Tabl2にあるように、Hyper parameterが多い。 hyper parameterの決定A/B testで決めている。

5.2 Similar-Profiles in Campaign-Aware Expansion

5.3 Online A/B Test

user idに基いて、実験対象を以下のようにわける。

以下を比較

Audience Expansionで、impressionが増えるのは当たり前なので、Dwell TImeやCPC, CTRが変わらずにどれだけimpressionを増やせるかが大事。

Reference