こんにちは。VASILYに入社して、オシャレぶるようになったと周りにイジられているデータサイエンティストの金田です。
VASILYでは、プッシュ通知の開封数を上げるために様々な施策を行っていますが、その一つとして、多腕バンディット問題を応用し、複数の異なるタイトル文の配信比率を動的に最適化することで、開封数を高めるといった取り組みを行っています。今回は、なぜプッシュ通知配信の最適化に多腕バンディット問題を応用したのか、アルゴリズム選定にあたりどのようなポイントを考慮したか、また実用にあたってどのような問題に直面し、それをどう克服したのか、といった点について紹介したいと思います。
プッシュ配信最適化の背景
iQONでは、新着の雑誌記事やコンテストのお知らせをユーザーへ通知するため、１日に数回プッシュ通知を配信しています。プッシュ通知は、どのようなタイトル文を配信するかによって、開封率が大きく異なってきますが、プッシュ配信最適化の取り組みを行う以前は、担当者がそれまでの定性的な知見を基にしてタイトル文を作成し、全てのユーザーに同じタイトル文を一斉に配信するといった運用をしていました。
そのため、日々のプッシュ通知の開封率にバラツキがあったり、また仮に、開封率が高かったとしても比較対象がなく、他の条件を一定にするという"実験"の条件を満たしていないために、なぜそのプッシュ文言の開封率が高かったのか、といった定性的な知見が蓄積されにくいという課題がありました。
従来、インターネットにおける広告やコンテンツの改善にあたっては、一般的にA/Bテストと呼ばれる手法を用いて、無作為に文言やクリエイティブの出し分けを行い、仮説検定を実施して実績の高かった方だけを採用するといった施策を行うことが多いかと思います。
しかしながら、広告やコンテンツと違い、プッシュ通知のタイトル文は賞味期限が短く、その日限りしか使えないことが多いため、仮にどのタイトル文の開封率が高いかという結果がわかっても、その結果を次に活かすことができません。そのため、プッシュ配信の最適化を行うにあたって、多腕バンディット問題に目をつけました。
多腕バンディット問題とは？
多腕バンディット問題に関しては、既に日本語でも広告やコンテンツの最適化への応用が様々なブログ等で紹介されていますが、機械学習の強化学習の手法の一つです。
問題の設定としては、当たり確率の異なる複数のスロットマシンがあり、手持ちのお金が限られているという状況を想定します。また、マシンは１回ごとに変更ができ、アームを引くごとに当たりかハズレかの結果が確率的に得られるとします。このような条件下で、スロットマシンから得られる報酬を最大化するために当たりやすいマシンの見極め（探索）と、当たりやすいマシンにお金を掛けること（活用）をどううまくバランスをとったらよいかという問題になります。
直感的には、各々のスロットマシンに少しずつお金を掛けていき、その過程で他よりも当たりやすそうなスロットマシンがあれば、そこへ他のマシンよりも多めにお金を掛けていくことで、報酬を最大化させるといったイメージになります。
今回は、多腕バンディット問題をプッシュ通知の配信に応用して、開封数をリアルタイムに取得し、開封率が高そうなタイトル文へ配信比率を寄せることで、開封数を増やすことができるのではと考えました。
システム構成
従って、多腕バンディットを適用するためには、配信途中にタイトル文の比率を変えていく必要があるため、リアルタイムに開封数を取得する必要があります。そのため、VASILYではプッシュ通知の配信に下図のシステム構成をとっています。具体的には、プッシュ通知を配信後、デバイスからの開封情報をAPIサーバーで受け、Fluentdを介してGoogle BigQueryへストリームインサートで送っています。そして、配信サーバーからBigQueryへクエリを発行することで、リアルタイムに開封数を取得しています。この仕組みによって、タイトル文の配信比率を動的に変更しています。
また、Tableauサーバーを活用することで、配信結果が自動的にレポートに反映されるような仕組みも作っているため、エンジニアの手を介すことなく、担当者が結果を参照できるようになっています。
プッシュ通知配信に係る問題とその解決策
しかしながら、実際にプッシュ通知の配信に多腕バンディットを適用しようとした場合、通常の多腕バンディット問題とはいくつか問題設定が異なる点があり、実装にあたりいくつか試行錯誤がありました。ここでは、その問題と解決策について説明します。
ステップごとの一括送信
相違点の一つは、アームを一回ずつ引くのではなく、結果をまとめて計算する必要があることでした。なぜなら、VASILYのプッシュ通知配信の仕組みでは、プッシュ通知を何ステップかに分け、まとめて送信をする仕組みになっているためです。例えば、仮に10万通の通知を送信するのであれば、20時半から1万通づつ、5分間隔で10ステップに分けて送信するといった仕組みになっています。
アルゴリズムの実装にあたっては、O'Reillyから出ている下記の書籍を参考にしましたが、通常の多腕バンディット問題では一回づつスロットマシンのアームを引くことを前提としていてるため、実装にあたっては、新たにbulk_update() という一括で更新ができるメソッドを独自に追加することで対応しました。また実装はRubyで行い、Gemパッケージとして導入できるようにしました。
なお、今回ご紹介したRubyでの実装は、GemとしてGitHub上で公開をしていますので、要望、質問、プルリクなどありましたら歓迎いたします。
https://github.com/vasilyjp/multi_armed_bandit
報酬の遅延
また、多腕バンディット問題とのもう一つの違いは、報酬が遅れて支払われるということでした。プッシュ通知の配信の場合、実際にプッシュ通知を送信してから、それが開封されるまでにタイムラグがあります。
そのため、あまり最初の方から配信比率が大きく変化するようにパラメーターを設定してしまうと、配信数が安定せず、１ステップごとに配信比率が大きく振れてしまうということがわかりました。下の図は、ステップごとの配信数の割合を色分けして表したものですが、左側のグラフでは１ステップごとに配信比率が大きく変化してしまっていることが分かるかと思います。
従って、最初の方のステップでは、探索の方に比重を多くし、ステップが増えるに従って、探索の割合を減らし、活用の方に比重が移るようにステップごとのパラメータを調整しました。それにより、配信比率が安定し、適切に開封率の多いタイトル文の配信比率が高くなるようになりました。
アルゴリズムの選定
多腕バンディット問題のアルゴリズムにはいくつか種類がありますが、上記に記載した通り、実装にあたっては、
- 一括で報酬のアップデートができる
- 配信ステップごとにパラメータを変更できる
- 設定すべきパラメーター数が少ない
といった条件を満たすことが重要であったため、ε-Greedy と Softmax というの二つのアルゴリズムを候補としました。
この二つのアルゴリズムの大きな違いは、どのアームが成果が高いか"探索"を行う際に、アームを等確率で引くか（ε-Greedy）、過去の期待値に応じて、期待値の高いアームを引く確率を高くするか（Softmax）に大きな違いがあります。
両方のアルゴリズムを実際に運用してみた結果、Softmaxの方が、他よりも特に開封率の低いタイトル文があった場合に、早い段階でそのタイトル文に振り分けられる配信数を減らせることから、最終的にはSoftmax アルゴリズムを採用することにしました。
結果と今後の課題
上記の取り組みの結果、プッシュ配信のタイトル文の配信比率を動的に最適化することで、全ての文言を等配分で配信した場合に比べて、平均して約5％開封数をリフトさせることに成功しました。
また同一の条件で、複数のタイトル文を配信し、その結果を簡単に検証できるようになったため、タイトル文にモデル名を入れた方がよいのか？「〜なコーデ５選」といった具合に数字を入れた方がよいのか？といったタイトル文を作成する上での定性的な仮説の検証が容易になり、PDCAを早く回せるようになりました。
今後は、年齢やユーザーの嗜好といったコンテキスト情報を入れることで、更なる最適化を実現したいと考えています。また、広告やコンテンツの出し分けといったプッシュ通知の配信以外にも多腕バンディットアルゴリズムを適用し、さらにユーザーに感動体験を与えられるようなサービスにしてきたいと思っています。
最後に
VASILYのデータサイエンスチームでは、これ以外にも、トピックモデルという文章分類に使われる手法をユーザーのLikeデータに適用し、ユーザーの隠れた嗜好を推定してレコメンドに応用するといったことや、ユーザーの口コミをネットワーク分析によって明らかにすることで、ファッションに関する情報伝播がどのような構造になっているのか解明するといったことを行っています。
また、ここには書ききれないこともたくさんありますので、こういった取り組みに少しでも興味があるという方がいれば、ぜひ一度VASILYに遊びに来てください。VASILYでは一緒に働ける優秀なデータサイエンティストを募集しています。一緒に「ファッション×ビックデータ」という未開の分野を一緒に開拓していきましょう！
