ソーシャルマーケティングシステムを単純なアルゴリズムで実装する - 劣モジュラ最適化と貪欲法

ソーシャルマーケティングシステムの設計と機械学習

FacebookやTwitterなどのソーシャルメディアは、情報の拡散を劇的に早めました。国際情勢からゴシップ、専門的な情報から個人の日常生活に至るまで、あらゆる情報が流れ込み、ユーザーの手によって評価・拡散されています。その爆発的な拡散速度に魅力を感じる主体が多いせいか、ソーシャルメディアを介してプロモーションを打つという意思決定が随分とメジャーになりました。

バイラルマーケティング(viral marketing)という言葉があるようです。口コミを利用して、新商品などの情報を拡散していきユーザーを獲得するマーケティング手法のことで、バイラルはvirus、つまりウイルスを語源とする言葉です。

情報拡散をめざす上では、誰に広告を出稿するかという問題があります。その対象や順序によって、広告の効果が断然ちがってくるのは想像に難くありません。そこで、広告出稿対象を機械学習で選定するシステムなどあるのかなと調べてみたところ、面白そうな文献を見つけました。

以降ではマイクロソフト研究所のVahab Mirrokni氏が行った研究報告、「Online Advertisement and Submodular Maximization」に登場する「オンライン広告問題」を単純化したものを紹介し、それを解くプログラミング技法を紹介していきます。
http://research.microsoft.com/en-us/um/beijing/events/theoryWorkshop08/Mirrokni.pdf

この文献は、広告システム設計者の立場で、商品プロモーションによるクライアントの売上最大化を目指しています。文献を翻案すると、ざっくりとした要件は以下のように定義できます。

出稿対象アカウントを選定し、対象者のタイムラインに商品購入のプロモーションツイートを表示
プロモーションは「無料キャンペーン」と「定価販売(2,000円)」の２フェーズに分ける。
- 無料キャンペーンについては一括プロモーションをかける
商品購入者にはハッシュタグ付のツイートを促す
- 今回は簡単化のため、購入者全員がツイートしてくれるものとする
広告の出稿費用はかからないが、各ユーザーには一回しか広告を出せない

劣モジュラ最適化と離散数学

"Submodular Maximization"という報告の題目には、「劣モジュラ最大化」という訳語があるようです。

劣モジュラ最大化は、より広く"discrete optimization"（離散最適化問題）に分類されるようなので、まず離散最適化問題がどんなものかを理解する必要がありました。

離散最適化問題は、「1、2、3…」と数えられる対象があって、そこから最適な組合せを見つける問題のことです。バイラルマーケティングにおいて情報を広めるのは人ですが、人は1人、2人…というのが最小単位ですから、「誰に広告を出すか」という選択は離散的なものになるのです。なお、離散の対義語は「連続」で、義務教育で学ぶ数学の関数はほとんどが連続関数です（ex. 2次関数、三角関数）。離散量と連続量の簡単な例としては、以下が挙げられます。

シーン	離散量の例	連続量の例
Webサイト分析	ユーザーが閲覧したページ数	ページあたりの滞在時間
身体測定	反復横跳びの回数	50m走の記録
食事量	食べたトマトの数	飲んだ味噌汁の量

連続量も、現実には離散化してサンプリングすることがほとんどですが、解析上は実数全体を取るものとして扱い、微分積分などを駆使してモデリングを行います。

離散最適化問題を解くには、離散数学の知識が必要です。この記事はその入門に適するよう、集合や組合せに関する基本的な知識のみで読めるように書きました。また、離散数学は配列やキュー、スタック、ヒープといったデータ構造とも関係する概念ですので、エンジニアが接する数学としてはお勧めです。劣モジュラ性や、この記事で紹介する貪欲法は、概念を理解すればすぐコードに落とし込み、最適化を手軽に行うことが出来る分野です。
早速、始めてみましょう。

グラフ - 離散最適化の必需品

TwitterやFacebookなどのソーシャルネットワークにおけるユーザー同士のつながりは、グラフを用いて表すことができます。

ここでグラフとは、下図のような頂点(vertex)と枝(edge)からなる抽象的概念であり、データ構造の一種です。データを図示するためのグラフとは異なるので注意してください。

図1: 無向グラフの例

上図では、7人からなる小さなFacebookネットワークを図示しました。頂点は人を表し、枝は友達であることを表します。

図2: 隣接リストと無向グラフ

Dさんに着目して考えてみましょう。DさんはBさん,Cさん,Eさん,Fさんと友達です。しかし、Gさんとは友達ではありません。

グラフをデータとして保持する方法の一つは、上図にある隣接リスト(adjacent list)を記憶させることです。配列などで各頂点の隣接頂点を覚えさせておけば、とりあえずデータとして保持することは出来ますね（高速化のためにはさらなる工夫が必要ですが）。

また、Twitterのフォロー関係のように、情報が一方向にのみ流れる場合も考えられます。そのような状況は有向グラフ(directed graph)を用いて表すことができます。

図3: 有向グラフの例

オンライン広告問題を定義し、解く

それでは、クライアントの売上最大化問題を定義し、プログラミングによって解く方法を考えてみましょう。
まず、ユーザーのハッシュタグ付ツイートは、フォロワーに対する商品認知度を高める効果があると仮定します。

図4: 情報の流れを表すグラフ

このことを、グラフを用いて考えてみましょう。ここでは枝が情報の流れを表すとし、有向グラフを用います（Twitterのフォロー・フォロワー関係とは、枝の向きが逆であることに注意してください）。
なお、双方向に情報が流れている二者については、便宜的に矢印の無い枝一本で表します。
上図のGさんに着目すると、Dさん、Eさん、Hさんの３人に情報を流していますが、AさんやLさんには流していません。

このようなネットワークの中には多数のユーザーに影響を与える情報提供者、いわゆるインフルエンサーがいる可能性があり、利益最大化のためにはそのようなユーザーにアプローチするのが有効と考えられます。

誰がインフルエンサーなのか - 出次数(outdegree)

上図では、AさんやBさんがインフルエンサーであることが直感的に分かりますね。
ここで、その直感を頂点の出次数(outdegree)によって根拠付けることができます。頂点 $ A $ の出次数 $ o(A) $ とは、その頂点から出て行く枝の本数のことです。
これはTwitterのネットワークで言えば、フォロワー数に対応する概念だと解釈することが出来ます。（ここで枝は情報の流れる方向を図示するため、通常のフォロー・フォロワーのイメージとは逆向きであることに注意してください）
グラフ中の出次数の大きな頂点を探すと、 $ o(A)=5 $, $ o(B)=4 $ であり、他のどの頂点 $ X $ についても $ o(X)<4 $ が成り立ちますから、Aさんが最大のインフルエンサー、Bさんが2番目のインフルエンサーと言えそうです。

商品のプロモーション対象をシステム上で最適化する

ではここで、「システム設計者」という立場に戻ります。
クライアントの利益最大化のためには、インフルエンサーに積極的にプロモーションをかけ、多数のユーザーにハッシュタグ付ツイートを拡散してもらうのが良さそうです。しかし、その事実をどうやってシステムに反映すれば良いでしょうか。

ここで問題を特徴付ける重要な仮定を置きます。広告の配信先となるユーザーについては、それぞれの商品認知度に基づき、広告を配信した際の購買確率が計算出来るとします。
これをどうやって計算するかはまた別の（統計的な）問題となりえますが、ひとまず数値は与えられるものとします。

図5: 購買確率に与える影響

上図ではDさんの購買確率に着目しています。ここでは単純化のため、Dさんの購買確率は、彼がフォローしているAさん・Bさん・Cさんが商品に関するハッシュタグ付のツイートをした事があるか否かで決まるものとします。
上図では、Dさんがフォローしている人のうち、ハッシュタグ付ツイートをした事のある人数が増えていく毎に、Dさんの購買確率が大きくなることを示しています。ここに、本記事の主題である劣モジュラ性が隠れています。

購買確率の劣モジュラ性 - 最適化と相性の良い関数型

上図では、周りの誰も商品についてツイートしていない時、Dさんの購買確率は0.50%でした。
1人がツイートしていると1.00%、2人だと1.15%、3人だと1.18%…と上昇しています。
ここで、購買確率の増加幅に注目してみましょう。
t人がツイートしている時の購買確率を $ p_t% $ で表すと、増加幅は以下のようになります。

$ p_1-p_0=0.50% $
$ p_2-p_1=0.15% $
$ p_3-p_2=0.03% $

だんだんと、増加幅が小さくなっていますね。このような性質を逓減性といいますが、人数について逓減性を持つものは、劣モジュラ性を満たす関数の典型例なのです。

劣モジュラ性の数学的な定義は、以下の書籍などを参考にしてください。今回はごく特殊なケースのみを取り上げます。

「劣モジュラ最適化と機械学習」：河原吉伸、永野清仁

逓減性を持つ関数は日常のいろいろなところに見られます。例えば宝くじの４等（50,000円）が当たった時の嬉しさは、預金1,000万円の人と、預金3万円の人を比べたら、後者の人の方が大きいと考えらえます。収入に対して感じる「嬉しさ」は、逓減性を持つということですね。

商品認知度についても、逓減性を満たすのは自然な仮定と言えます。例えば書籍について、周りに「よかった」と勧めてきた人数が0人の場合と、1人の場合とでは大きな隔たりがあります。1人と2人でもだいぶ違うと言えるでしょう。しかし、10人と11人とでは、さほど差がないと感じるのではないでしょうか。

購入確率は、実績値に基づき統計的に決めるのがベストですが、まずは逓減性を満たす仮の値を入れておくだけでも、後述のシステムを動かす事が可能です。

劣モジュラ性と貪欲法 - シンプルな近似アルゴリズム

上図では12人しかいない世界を仮定したので、無料キャンペーン対象の全組み合わせは $ 2^{12}=4096 $ 通りしかありません。しかし、 $ 2^{20}=1048576 $ , $ 2^{50}≒1100 $ 兆というように、組み合わせ数は爆発的に増加します。この中で、どれが最適なキャンペーン対象の組み合わせかを計算するのは容易ではありません。

日本国内では、2015年12月時点で約3,500万人のアクティブユーザーがいると発表されました。となると、Twitter上の全組み合わせであれば、 $ 2^{35,000,000} $ 通りとなります。これだけの組み合わせを計算することは不可能でしょう。

ここで、近似的に良い組み合わせを見つけても、その組み合わせの質は悪いのではないか？と考えるかもしれません。しかし、目的関数が劣モジュラ性を満たしていれば、貪欲法というシンプルなアルゴリズムを用いるだけで、一定水準以上で解の質を保証するということが知られています。

例えば、「3,500万人のユーザーから最適な組み合わせを選ぶことで、100万円の利益が期待出来る」という状況があったとします。このような場合、最適な組み合わせは上述の事情によって「神のみぞ知る」組み合わせであり、人間が見つけ出すことは至難の業です。ですから、そのような組み合わせを見つけるのは諦めて、「100万円の利益が期待出来る組み合わせが存在するなら、少なくとも80万円の利益を期待出来る組み合わせを見つけてくる」といったことを目指します。このような保証のあるアルゴリズムを近似アルゴリズムと呼びます。
今回の例では、購買確率が劣モジュラ性を満たしていることにより、アルゴリズムに一定の性能保証が与えられます。

では、インフルエンサーをどのように発見し、プロモーションを行っていくのでしょうか？次回はインフルエンサーを発見するアルゴリズムやプロモーションの詳細を紹介いたします。

オンライン広告をどのようにプロモーションする？ - 劣モジュラ性と局所探索で解決