インターネット広告部門の現場でデータ分析をやらせていただいて、データ分析の側から、弊社の営業と協力して、広告主の課題を解決することを目指しています。
その中で、インターネット広告の出稿企業は、次のような課題を抱えている事が多くあります。
「自社サイト訪問ユーザーだけに広告出稿していたのでは、確かに広告効果は良い、しかし、新規ユーザーを獲得する事ができない。新規ユーザーを獲得したい。」
その場合、次のような考え方をします。
「自社サイトユーザーに似たユーザー、いわば見込み客、に広告を配信することにより、課題解決することを目指す。」
ここで大切なことは、自社サイトユーザーに類似したユーザーを見つけることです。前回の記事では、ユーザー間の類似性を定量化する方法を紹介しました。
ターゲティング広告の統計学的な基礎：ユーザーの類似性の定量化
しかし、ここでまた問題が発生します。
「ターゲティング軸はどれが良いのだろうか？性別かな？年齢かな？ページ訪問履歴かな？わからないorz」
類似性と一言で言っても、様々な類似性があることは前回記事でも紹介しました。GoogleやYahoo!、弊社関連企業のマイクロアドなどは、ターゲティング広告を販売していますが、そこで活用されているターゲティング手法は様々、つまり類似性の軸は様々のはずです。以下では、
「類似性の軸が様々あった場合に、目的変数（KPI）に対して効果的なターゲティングするための類似性の重み付けの方法」
を紹介します。以前私が、そのような方法論を考える職務にあった時に、考えていた方法で、面白そうな方法を1つ選びました。
※参考文献は文末に載せました。私がすべての論文を調べられていないため、文末の参考文献は網羅的でないことをご了承ください。詳細を知りたい方は、参考文献の論文の中の参考文献を参照してくださいorz
1.様々な類似性
複数の類似性がある場合は、複数のターゲティングができてしまうことを説明します。例として、サンプルユーザー5人のデータを考えます。
この時に、各類似性の可視化であるネットワーク構造は以下のようになります。
類似性の高いユーザーは、リンクで結びついています。類似性は必ずしも100％ではなく、微妙に似ている場合もあるので、リンクが持つ値は0～100％になります。
この場合、複数のネットワーク構造ができましたので、それに対応して、複数のターゲティングが可能になります。どちらのネットワークがターゲティングに効果的でしょうか？
効果的なターゲティングの考察
女性保険の企業の場合
・性別によるネットワークで、女性のクラスターに広告を配信すればよい。
不動産の企業の場合
・興味によるネットワークで、特に不動産クラスター、または車クラスター（車を買っている人は、家も欲しいかも）に広告を配信すればよい。
他の業種
・類似性の軸を掛け合わせる必要があるかもしれません。
上記例から分かるように、広告主にとって、ターゲティングに有効な類似性は様々です。
各広告主毎に、ターゲティングに有効な類似性が、何らかのアルゴリズムで自動的に決まれば嬉しいです。そこで、各ネットワークを適当な重みで重ねあわせて、各広告主に最適なターゲティングとなるようなネットワーク構造を作りたいと考えます。
以前、私がこれを実現する方法論を考えていて、その中で楽しそうな方法を以下で紹介します。
2.データの準備
以下、練習のために簡単な例を考えます。ユーザーが5人いて、性別、年齢、検索履歴、そして、KPIとなるクリック率（CTR）が分かっているとします。
この場合、クリック率の高いユーザーを分類するために、どのような重みで上記の類似性を考慮すればよいのかを考えます。ちなみに、性別が、クリック率に影響を及ぼしているようなデータを作為的に作っています。
参考までに、前回の記事（ターゲティング広告の統計学的な基礎：ユーザーの類似性の定量化）の方法を使って、上記データで各類似性の類似性の表（行列）を計算すると以下の通りです。
準備は整いましたので、このデータから、類似性の重み付けの最適化（ネットワーク構造の最適化）の方法論を紹介します。
3.変分型のラベル伝搬法の理論
紹介する方法は、ラベル伝搬法という方法です。この方法では、変分原理という美しい方法が用いられています。実際に、以下の簡単な原理からできています。煎じ詰めるとこの式一発です。
作用関数（コスト関数）
この式一発なので、深く理解したいと思います。
各変数
y
・目的変数で、各ユーザーのクリック率です。y_1ならばユーザー1のクリック率10％です。
f
・スコアと呼ばれ、各ユーザーのクリック率の潜在的な数値を表します。（分かりにくいかもしれませんが、事実は10％なのだけれど、真実の値があるとすると、fになるとしています。）
R
・各類似性の表（行列）の加重和（下記、①準備を参照）
3つのベータ
・理論の中の自由変数（ここを決めるのは実は大変ですが、あまり気にしないでください。）
各項
右辺第1項
・事実のクリック率と、真実のクリック率の誤差（二乗誤差）
右辺第2項
・スコアの二乗和（正則化項）
右辺第3項
・リンクで繋がったスコアの二乗誤差に、リンクの値（類似性の値）を重み付けした量
最後の式で、Sを偏微分していますが、これにより、Sが一番小さくなるようなfとアルファを探しましょうというのが、この理論の要求です。
Sを最小化するとなぜ、ターゲティングの最適化（ネットワーク構造の最適化）になるかという事を説明します。各項を最小化することの意味は次の通りです。
変分原理での各項の意味
第1項
・事実と真実のクリック率が同じであれ
第2項
・真実のクリック率が（必要以上に）大きくなり過ぎるな
第3項
・特に大きい類似性で結びついているユーザー同士のスコアは同じであれ
この変分原理により、ネットワーク構造を様々変化させた上で、類似性の高いユーザーは近くに位置するような構造になります。ターゲティングとは、似た者同士を集める方法ですから、この考え方がマッチするように思います。
この式を変分して、うにゃうにゃ解いていくと、『この式を解くことはイコール、以下のアルゴリズムに沿って、計算を行うことである』ということが論文で示されています。ちなみに、解く過程で、t分布が出ているところから、論文のタイトルの”Robust”が由来しています。
アルゴリズム
※グラフラプラシアンについて、私は聞いたこともなかったのですが、この中に出ているdiag記号は、ベクトルを、行列に変換する、ただし、行列の対角成分にベクトルの成分を並べる演算子です。yでゼロの成分がありますが、クリック率が未知のユーザーについては、ゼロとしておきます。0.5でも大丈夫です。Gはクリック率既知の次元分の単位行列を、クリック率未知のユーザーの次元分だけ拡張した行列です。
次に、fとアルファの計算ルールは次の通りです。
これで準備ができたので、以下のアルゴリズムを走らせて、アルファが一定値に収束すれば完了です。
さて、このアルゴリズムを上記の5ユーザーデータに当てはめてみます。
4.サンプルデータでの結果
結果は、アルゴリズムを1回、2回と繰り返していくと、2回目でアルファが収束して、重要な類似性の軸が判明します。
そもそものデータは、性別がクリック率に影響を及ぼしているように、作為的に作ったので、そのことが、アルゴリズムで突き止められている事が分かります。
5.結果の可視化
数値だけでは分かりにくいと思いますので、初期のネットワーク構造と最適化後のネットワーク構造をそれぞれ図示します（手書きですみませんorz）。類似性が高いほど、近くにユーザーが位置するように書いています。
初期の類似性ネットワークは、クリック率が高いユーザーがばらばらに位置していて、適切なターゲティングになっていません。つまり、ユーザー1が自社サイト訪問ユーザーならば、次は、誰に広告配信すればよいかがいまいち分かりません。2なのか3なのか微妙なところです。
一方、最適化後の類似性ネットワークは、クリック率が高いユーザーがクラスタリングされて密集して、適切なターゲティングになっています。つまり、ユーザー1が自社サイト訪問ユーザーならば、類似性の高い（近い）ユーザーに広告配信する事で、高いクリック率が期待できます。
このネットワーク構造の変化は、いわば最適化により秩序を獲得したわけですが、ネットワーク構造に以下のようなエントロピーという量を定義できます（こういう定義は学術的にある？）
2つのネットワーク構造でそれぞれエントロピーを計算すると、最適化されたネットワーク構造ではエントロピーが低くなり、これは秩序を獲得したことを示しています。
確かに、最適化アルゴリズムを走らせることにより、類似性のネットワーク構造が秩序を獲得して、より適切なターゲティングができるようになっていそうだということが分かります。
6.補足
アルゴリズムの途中で、逆行列が出てきましたが、計算量の観点から不都合なこともあります。その場合は、以下のように行列のテイラー展開を利用して、逆行列が出ないようにすることができます。
この場合、無限に足し算するわけにはいきませんから、適当な次数で計算を止めて近似計算します。近似計算したときの解は、以下のようになっていて、（このようなとても小さなサンプル数の場合ですが）まあまあな近似になっている事が分かります。
この計算の際に、行列同士の掛け算をしないように注意が必要です。まず、Gy（行列×ベクトル）を計算する。次に、B(Gy)（行列×ベクトル）のような感じです。
7.まとめ
今回は、複数の類似性の軸がある場合に、各軸に対する重み付けを最適化する方法を紹介しました。今回紹介したのは、多少おしゃれな方法で理論的にも美しいのですが、実装となると様々な困難があると思います。類似性に適当な重み付けをして、k-means、又はルールベースのクラスタリングでいいのではないかという意見もあると思います。全くその通りだと思います。
現実のシステムとして実装する場合は、2つの欲求と理性が交錯します。
1.データアナリストとして理論的に高度な分析をやってみたい欲求
2.シンプルで説明のできる方法を使わなければいけないという理性
高度な手法を使ったり、画期的な手法を使ってビジネスができれば嬉しいですが、そこは柔軟な対応が必要と考えています
しかし、サイジニア社のように複雑ネットワークを活用してレコメンドバナーを配信している企業もありますので、高度な理論もアイデア一つでビジネスに活かせるのではないかという希望を、個人的には持っています。
サイジニア社 デクワス（世界初の複雑ネットワーク技術に基づくレコメンデーション）
この例もありますし、例えば、機械学習を研究されていた方などは、今では様々な業界から引っ張りだこかもしれせんが、インターネット広告の世界でも需要は沢山ありますので、興味のある方は是非インターネット広告業界へ参入してください。
以上
終わり
参考文献
本記事で紹介した理論の元ネタ
[KKS]
※以下の論文は、一例で、網羅的になっていないことをご了承ください。学術的に、正式な論文を書く時は、もっと参考文献を精査する必要があります。
ラベル伝搬法を提唱した論文
[RAK]
ラベル伝搬法を変分原理で活用した論文
[BC]
[ZPD]
[TSS]
日本語で読めるラベル伝搬法の論文
リンク予測のための半教師付き学習法
ラプラシアンラベル伝搬による検索クリックスルーログからの意味カテゴリ獲得
ウェブ検索ログを用いたラベル伝搬による意味カテゴリ獲得