前回の記事でソーシャルマーケティングの例であるオンライン広告問題の定義と劣モジュラ性の関連について説明しました。今回はオンライン広告問題において、どのようにインフルエンサーを見つけ、プロモーションを行っていくのかを紹介したいと思います。

Influence戦略：インフルエンサーへのアプローチ

Microsoft研究所のスライドで提案されている戦略は「Influence & Exploit Strategies」と呼ばれ、以下の２ステップからなります。

1. Influence：影響力のあるユーザーの集合Aに無料で商品を提供する。
2. Exploit：残りのユーザーをランダムに訪問し、最適価格を提示する。

これは記事冒頭の、以下の仮定に対応しています：

プロモーションは「無料キャンペーン」と「定価販売(2,000円)」の２フェーズに分ける。

「最適価格」というところを「定価」と読み替えていますが、このようにすると元の問題の特殊ケースとなります。
今回はExploit戦略については触れず、Influence戦略について説明をしていきます。

局所探索(local search)でキャンペーン対象を決定

そもそも、クライアントはなぜ「無料キャンペーン」という戦略をはじめに取りたがっているのでしょうか。
それは無料配布・口コミにより商品認知度を高めることで、後続の定価販売(2,000円)の際に、ユーザーの購入確率を高めるためと考えられます。

無料配布を行うことには、プラス、マイナス両方向の要因が存在します。

• ユーザーに商品を無料提供することは機会損失と考えられ、定価で買ってくれた場合に比べて2,000円分の利益を失う（マイナスの要因）
• 商品を提供したユーザーはハッシュタグ付ツイートによるプロモーションを行うので、フォロワーの購買確率を高めてくれる（プラスの要因）

ここで、キャンペーン対象にユーザーを一人追加することの、プラス要因とマイナス要因の差額を便益（Benefit）と定義します。

これから説明する局所探索とは、上述した便益が正である限り、ユーザーを一人ずつ無料キャンペーン対象に追加（または削除）するというものです。
今回は簡単のため、無料配布対象のユーザーは必ず商品を購入し、またハッシュタグ付のツイートをしてくれるものと仮定すると、局所探索の疑似コードは以下のようになります：

users = {}  # 広告の出稿対象であるn人のSNSユーザー
price = 2000  # 商品の定価


users['A'] = {  # ユーザーのフォロワーとフォロー先を格納する連想配列。ここではAのみ定義
  'followers':  ['B', 'I', 'G', 'E', 'F'],
  'followings': ['B', 'E']
}

# 他のユーザーのfollowers, followingsも同様に定義

# フォロー先ユーザーのキャンペーン対象者数によって決まる購入確率
purchase_prob = [0.005, 0.010, 0.0115, 0.0118, 0.01185, 0.0119]


def campaign_obj():  # 無料キャンペーン対象者を決める関数を実行
  target_users = []  # 対象ユーザー (返り値、最初は空)
  while True:  # 貪欲法によって便益が増加しなくなったら抜けるループ
    user_with_max_benefit = None  # 最大の便益を与えるユーザー
    max_benefit = 0.000  # 最大の便益値
    for i in set(users)-set(target_users):  # 新規キャンペーン対象としてiを取る
      revenue = 0.000  # iを無料キャンペーン対象に加えることで得られる期待利益額増分の総和
      # iのフォロワーjを取る
      for j in set(users[i]['followers'])-set(target_users):
        # target_usersにiを加えた集合
        new_target_users = set(target_users) | set(i)
        # jがフォローしているキャンペーン対象ターゲット（iを加える前）
        following_target_before = \
          set(target_users) & set(users[j]['followings'])
        # jがフォローしているキャンペーン対象ターゲット（iを加えた後）
        following_target_after = \
          new_target_users & set(users[j]['followings'])
        # iを加える前のjの購入確率
        prob_before = purchase_prob[len(following_target_before)]
        # iを加えた後のjの購入確率
        prob_after = purchase_prob[len(following_target_after)]
        # jの購入確率の増分
        prob_increase = prob_after - prob_before
        # jに関する期待利益額増分 = 定価 * jの購入確率の増分
        revenue += price * prob_increase
    # 機会損失額 = 定価 * 定価でも買ってくれた確率
    cost = price * purchase_prob(set(target_users))
    benefit = revenue - cost  # 便益は、利益から機会損失額を引いて求める

    if benefit > max_benefit:
      user_with_max_benefit = i  # ユーザーiをuser_with_max_benefitにセット
      max_benefit = benefit

    if max_benefit > 0:
      # target_usersにuser_with_max_benefitを加える
      target_users = set(target_users) | set(user_with_max_benefit)
    else:
      break

  return list(target_users)

ただしここでは簡略化のため、「ユーザーの追加」のみを考えた局所探索のコードを掲載しています。「ユーザーの削除」も考慮したコードは、for文の中身を少し書き換えることで実現できます。

局所探索の動きの図示

疑似コードだけでは分かりづらいので、局所探索の様子を図示してみましょう。
まず、手続きをステップ分けすると以下のようになります。

1. まだキャンペーン対象でないユーザーiを取り、ユーザーiを加えることによる便益を計算
2. 1.の計算を元に、最大便益をもたらすユーザーを特定
3. 最大便益が正であるならばユーザーを出力リストSに入れ、1.に戻る。0以下であるならば停止する

実際の局所探索のステップを例を用いて説明します。

上図には、ステップ1.の開始時として誰も無料キャンペーンの対象ではない状態と、その場合の定価販売開始時の購入確率を示しました。すべてのユーザーが0.50%という確率で購入してくれることが分かります。

上図はAさんを無料キャンペーン対象とする時の購入確率を示しています。AさんをフォローしているBさん、Eさん、Fさん、Gさんの購入確率が1.00%に高まっています。
一方で、Aさんには商品を無料配布してしまったので、定価販売の広告対象からは外れてしまいます。これによって得られる便益を計算してみましょう：

上式は、疑似コードで行われる計算と同じ内容を、一本の数式で表しています。一項目はAさんへの商品提供による、Aさんのフォロワーへの正の効果、二項目は機会損失による負の効果を表し、結果として得られる便益は期待値で40円相当であることが分かりました。

実は、最初に実行するステップ1.では必ず、フォロワー数最大のユーザーを加えた時に便益最大となります。差し当たり、Aさんを無料キャンペーンの対象に入れることとします。

そして、次に加えるユーザーとして、2番目のインフルエンサーだったBさんを加えた時の購入確率がこちらです。Aさん、Bさんの両方をフォローしているユーザーについて、購入確率が1.15%に増加していることが分かります。
購入確率の劣モジュラ性により、先ほどよりも上がり幅が小さくなっていることが分かります。

上式は、Bさんを加えることの便益がマイナスであることを示しています。フォロワーに与えるプラスの影響を、Bさんに商品を定価で売れないことの機会損失額が上回ってしまったのですね。
実は、Bさんのフォロワーの集合は、Aさんのフォロワーの集合（と、Aさん自身）によって含まれています。購買確率が劣モジュラ性を満たし、逓減性を持つことから、このようなBさんに無料配布するメリットは小さいのですね。

上図はユーザーの追加・削除を行う局所探索の結果を表しています。よりフォロワー数の多いBさんではなく、GさんやKさんといったユーザーが無料キャンペーン対象となっているところに、劣モジュラ性の特徴が現れています。

この状態から定価販売を始めることで、無料キャンペーンを行わずに広告を出稿した場合に比べ、期待される利益額が26円上昇するという結果が得られます。このアルゴリズムは、購入確率の関数が劣モジュラ性を満たす場合、最適解と比べて40%の期待利益額増加を保証してくれます。（上記の例では最適解を出力しています。）

今回はフォロワー数が高々5人というとても小さなネットワークでしたので少額の結果となりましたが、強力なインフルエンサーの居る現実に近いネットワークであれば、利益額が数万、数十万単位で変わってくることも考えられます。

より現実に近いモデリングを目指して - 劣モジュラ性の数学的定義を学ぶ

劣モジュラ性を満たす購入確率関数を持つソーシャルネットワークに対しては、局所探索アルゴリズムを用いることで効果的に商品の知名度を上げることが出来ると分かりました。ただ、今回のモデルはそのまま実用するには問題があります：

• 商品の原価や広告出稿費用を考えていない
• 無料キャンペーン対象のユーザーは必ず商品を購入し、ハッシュタグ付のツイートで宣伝してくれるという仮定をしていた

上記の前提を取り除くためには、モデルに対する理解と、いくらか確率に関する知識を必要とします。

本記事では、バイラルマーケティングにおける劣モジュラ性の応用について解説しました。このように、機械学習分野において劣モジュラ性は注目されており、コンピュータビジョンの分野でも使用されています。

今回はソーシャルマーケティングのシステム設計を例に取り、「フォロー先のハッシュタグ付ツイート人数によって購買確率が決まる」という単純な場合を考えてましたが、「購入確率に及ぼす効果が相手のフォロワー数によって変動する」とか、「女性のツイートの方が効果が大きい」といった細かい設定を付与したものも、劣モジュラ性を満たします。そのような、より現実に近いモデルを構築するには劣モジュラの数学的定義を知る必要がありますので、興味を持たれた方は以下の書籍などを参考に学習することをお勧めします。

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

尚、上記の疑似コードを、 Python で実装したものを、gist にアップしてあります。興味のある方は、そちらも、ご参照ください。

https://gist.github.com/msato-ok/40038aadf931c8cd28feceb2c0e2552e