【2019 MLEインターンシップ】機械学習で旅行をプランニングする

ブレインパッドでは毎年学生向けのインターンシップを開催しています。今年も、昨年に続いて「機械学習エンジニア(Machine Learning Engineer, MLE)コース」を実施し、今回は3名がインターンシップに参加しました。その取り組みと成果をご紹介します!

こんにちは、アナリティクスサービス本部AIプラクティス部の伊藤です。
今回は、今年の8月末から9月にかけて実施した機械学習エンジニアコースのインターンシップの内容についてお伝えします。

はじめに

今年は「機械学習による旅行プランニング」というテーマで1か月間のインターンシップを実施しました。京都と名古屋から、3名の方がインターンシップに参加しました。3名とも大学院で情報科学や機械学習を学んでいる優秀な方々です。

今回のテーマである「機械学習による旅行プランニング」は、具体的には、以下の3つのお題から構成されます。

  1. 宿泊先レコメンド: 旅行サイトのユーザーに対して、その閲覧履歴や検索履歴を分析して適切な宿泊先をレコメンドする。
  2. 周遊プランニング: 宿泊先周辺の観光スポットを外部サイトから抽出して、それらの最適な訪問順序をプランニングする。
  3. 寄り道先ランキング: 周遊プランの観光スポット周辺で、最適な寄り道スポットをランキングして提示する。

旅行サイトのユーザーアクセス情報は、当社のレコメンドエンジン Rtoaster (アールトースター)のトラッキングログから抽出・加工したデータマートを使用します。また、宿泊先周辺の観光スポット情報は、観光サイトやグルメサイトをスクレイピングして収集した観光スポットのデータ(店舗や施設の位置座標、ジャンル、クチコミ)を使うことにしました。

今年からサポート体制を充実させました。インターンシップの進行を見守るシニアメンバー(私を含む)に加えて、エンジニアリング力に自信のある若手メンバーをサポートメンバーに加えました。経験と時間を要するアクセスログの前処理(ユーザーIDの一意化、ノイズ除去)、スクレイピングデータのデータベース化(位置情報、ジャンル情報、レイティング情報)等の作業は、あらかじめサポートスタッフが行います。

採用するアルゴリズムには、最先端の手法を取り込むことにしました。宿泊先レコメンドには、行列分解による機械学習手法として定評のある Factorization Machine に深層学習による特徴量抽出を加えた DeepFM を採用します。周遊プランニングには、組合せ最適化問題の動的な解法として深層強化学習を採用します。深層強化学習については、折しも、私を含むブレインパッド有志による書籍が8月に出版されたばかりでしたので、この書籍とその付属コードを参考にすることにしました。寄り道先のランキングは、グルメサイトのお店評価(レイティング、星の数)をベースに改良を加えることにしました。

インターンの紹介と取り組みテーマ

今回、インターンに応募していただいた3名には、上記3つのテーマにそれぞれ取り組んでいただきます。以下、テーマ順にインターンのメンバーを紹介します。

懇親会にて(前列左から、恒川さん、佐藤さん、藤原さん)

宿泊先レコメンドには、恒川 充さんが取り組みます。
恒川さんは、修士課程で医療データを用いた発病予測について研究しています。宿泊先レコメンドは、ユーザーのサイトアクセス情報から宿泊先を予測する問題であり、研究テーマとの親和性もあることから、このテーマを選びました。

周遊プランニングには、藤原 大悟さんが取り組みます。
藤原さんは、修士課程で非線形物理学を使ったニューラルネットワークの研究を行っています。周遊プランニングで用いる深層強化学習は、周遊ルートを動的に生成しながら最適なルートを学習していくので、力学系の振る舞いと似ているところがあります。今回は、最適なプランニングとは何か、という問題設定から取り組むことにしました。

寄り道先ランキングには、佐藤 嵩晟さんが取り組みます。
佐藤さんは、修士課程でベイズ最適化を用いた材料研究を行っています。寄り道先ランキングでは、ベイズ統計の知識と経験を活かして、グルメサイトの評価データをもとに信頼性を考慮した評価スコアの開発を試みます。

インターンシップの進め方

ここでは、読者の皆さんにインターンシップの雰囲気をお伝えすべく、インターンシップの全日程を振り返ってみます。

初日は、午前中に入館証の受け渡しなどの事務的な手続きやパソコンの設定などを完了して、ウェルカムランチに向かいました。
ブレインパッドは東京都港区の白金台に位置しております。会社を出て5分ほども歩いた先にある、プラチナ通り沿いのアメリカンスタイルのレストランでランチコースを堪能しました。機械学習エンジニアやデータサイエンティストの若手やシニアも参加して、にぎやかな雰囲気で会話も弾みました。

ちなみに、地方から参加した学生のインターンシップ期間中の滞在先ですが、例年、会社から滞在費をサポートしております。地方の学生の方にも安心してインターンシップにご参加いただけるようにバックアップしております。

会社の周辺地図

2日目からは、朝会を実施しました。
朝10:30から1時間を割いて、インターン生各自が前日の成果やその日の取り組み内容を説明します。課題解決にあたってサポートメンバーに相談したい場合は、別途、ブレストの時間を設定してその日のうちに解決するようにしました。

ブレストの様子

ブレストの進行に当たっては、所定の会議時間において、何らかのアウトプットを出すことを意識して議論を進めました。ホワイトボード使って課題を書き出し、整理しながら実行可能な解決策へと着地させていきます。

お昼の時間は、外で食べる以外にも、社員が利用している仕出し弁当や、フリースペースにある自販機などで済ませることもできます。

食事の風景

午後は、引き続き課題に取り組んだり、ブレストの時間を設けて課題を整理したり、解決策を検討したりします。業務スペースに隣接して、ブレストのためのオープンスペース(テーブルとソファーが並んでいます)や会議室があり、活発に議論できる環境が用意されています。
今回のインターンシップでは、サポートメンバーを巻き込んで頻繁にブレストを行い、アイデアを交換しながら課題を解決していきました。

4週間の大まかなスケジュールは以下の通りです。
第1週目:各自が取り組む課題の決定
第2週目:課題の明確化とアプローチを検討、具体的な手法にまで落とし込み
2週目では、そこまでの成果を中間報告にまとめて簡単な報告会を行い、後半のアルゴリズム実装で克服すべき課題を洗い出しました。
第3週目:アルゴリズム実装を進めつつ課題解決に取り組み
第4週目:実装したモデルの最終チューニングと報告書作成

最終報告会

インターン3名と当社塩澤取締役(左から佐藤さん、藤原さん、塩澤取締役、恒川さん)

インターンシップ最終日に最終報告会を開催しました。ここでは、最終報告の内容を各人のテーマごとに詳しく紹介します。

宿泊先のレコメンド(恒川さん)

恒川さんは、深層学習を活用したレコメンドアルゴリズムの実装に取り組みました。具体的には、行列分解を活用したレコメンド手法として定評のある Factorization Machine と深層学習を組合せた DeepFM という手法を用いました。

ここで少し手法を説明します。
Factorization Machine は、ユーザーごとに商品アイテムの評価値を予測するモデルです。通常の回帰式では、評価値全体のバイアスに、ユーザごとのバイアスや商品アイテムごとのバイアスを加えた値として予測値を定義します。しかし、このような線形モデルでは、ユーザーと商品アイテムの交互作用が取り込まれません。そこで、Factorization Machine では、ユーザーと商品アイテムを共通の特徴空間(k 次元)のベクトルとして表現して、これら特徴ベクトルの内積として交互作用項を定義します(以下の予測式を参照)。

Factorization Machine の予測式

ここで、特徴ベクトル  {\bf v}_i は、ユーザーまたは商品アイテムの特徴ベクトルを表します。また、 x_i はユーザーおよび商品アイテムの one-hot 表現を含む履歴ベクトルを表します。このうち特徴ベクトル  {\bf v}_i は、ユーザーを行、商品アイテムを列、購買の有無(または回数)を値とする行列データから、行列分解近似によって得られます。


Factorization Machine の学習用データ

DeepFMでは、特徴ベクトルを行列分解を使わずに、ユーザーや商品アイテムの one-hot 表現から特徴空間への埋め込み変換行列として直接に学習します。さらに、特徴ベクトル間の交互作用についても、Factorization Machine 由来の項以外に、ニューラルネットワークの隠れ層による出力を合わせて予測式を定義しています(下図を参照)。

DeepFMの構成図*1

今回、この DeepFM を、旅行サイトのトラッキングデータに適用しました。この場合、商品アイテムはホテルや旅館などの宿泊先に対応します。まず最初に、トラッキングログを集計・加工してデータマートを作成する必要があります。
ここで、問題が生じます。旅行サイトでは、ユーザーの投げた検索クエリに応じて、同じページ上に複数の宿泊先がランキング表示されます。殆んどのユーザーは、このランキング表示ページだけで用が足りてしまうため、リンク先にある宿泊先の個別ページの閲覧数が減ってしまいます。その結果、ユーザーと特定の宿泊先が共起する履歴ベクトルを作成できないことが解かりました。
そこで今回は、商品アイテムの one-hot 表現に加えて、ユーザーの検索クエリから得られる、興味を持っているであろう商品アイテム属性(エリアや金額など)を抽出して特徴量とすることにしました。目的変数は、ユーザーが実際にその宿泊先を予約したか否かの2値変数としました。

DeepFM は、サポートメンバーに手伝ってもらって元論文をもとに Keras で実装しました。上記の工夫をして作成したデータマートを入力データとして学習したモデルを、テスト用データで評価したところ、ROC曲線の面積で 0.59 となり、交互作用を変数として取り込んだロジスティック回帰と同程度のモデルが学習できました。

周遊プランニング(藤原さん)

藤原さんは、深層強化学習を使った周遊プランの探索アルゴリズムの実装に取り組みました。
宿泊先周辺の観光スポットから制限時間内で周遊できるスポット群を抽出するとともに、それらの最適な訪問順序もプランニングします。基本的には、巡回セールスマン問題と同じですが、制限時間内で同じジャンル(レストラン、カフェ、博物館などのカテゴリ)が連続しないように周遊できるプランを生成することを目指します。

周遊プラン

探索を行うエージェントは、再帰型ニューラルネットワークに attention mechanism よる pointing 機能を追加した Pointer Network(下図)と呼ばれる深層学習モデルとして実装します。
このネットワークは、複数の地点の座標データを読み取って特徴量に変換するエンコーダ部分(図の左側)と、その特徴量と直前の訪問地点を受け取って、attention mechanism を使って次の訪問地点を指し示すデコーダ部分(図の右側)とから成り立ちます。
デコーダは、その時点までの訪問履歴を考慮して次の時点の訪問先を決定するので、エージェントの行動選択の方策(policy)を担っていると言えます。強化学習の枠組みでは、方策にもとづく一連の行動選択により得られた巡回ルートが、目的に適っているかどうかを報酬としてエージェントにフィードバックすることで最適な方策を学習します。

Pointer Network*2

単純な巡回セールスマン問題の場合、巡回ルートが最短距離であることが望ましいので、経路長  \times(-1) を報酬として定義すればよいのですが、今回の問題設定ではそう簡単には行きません。巡回ルートが満たすべき条件として、

  1. 訪問した観光スポットのクチコミ評価点の合計(満足度)を大きくする
  2. 巡回路に沿って同じカテゴリの観光スポットが連続しないように選ぶ
  3. 制限時間に達したら周遊を終了する(必ずしも出発地点に戻ってこなくてもよい)

といった制約条件を満たす必要があります。藤原さんは、報酬定義を工夫することで、これらの制約条件を考量できるようにしました。
最初の条件については、訪問した観光スポットのクチコミ評価点の合計を報酬に加えました。
2番目の条件は、観光スポット間の類似度を計算して、前後するスポット間類似度を巡回路について合計した値 \times(-1) を報酬に加えることにしました(下式)。
3番目の終了条件は、周遊時間が制限時間 T を超えると生じるペナルティ(負の報酬)として報酬に取り込まれています。

報酬の定義式

観光スポット間の類似度は、下図のように観光スポットのカテゴリ付与データを行列とみなし、これを非負行列分解して得られる特徴ベクトル間のコサイン類似度として計算しました。

非負値行列分解による特徴ベクトル

エージェントの実装には、先に紹介した書籍の付録コードを活用して、報酬定義と終了条件を変更することで効率よく実装できました。
行列分解による類似度計算は Python で直接に実装しました。こうして実装されたエージェントを、グルメサイトからスクレーピングした観光スポットデータを用いて学習しました。さらに、学習済みエージェントを使って、草津温泉を出発点とする周遊ルートを探索した結果、以下の周遊プランが得られました。

草津温泉の周遊プラン

周遊プランの訪問順に訪問先ジャンルをたどると、登山 \rightarrow レストラン \rightarrow 公園 \rightarrow 温泉の順に異なるジャンルが並んでいることが確認できます。

寄り道先のランキング(佐藤さん)

佐藤さんは、旅先での予定変更により寄り道する場合に、適切な訪問先を抽出するロジックの開発に取り組みました。
具体的には、予定していた訪問先が休業だったり、次の目的地に行くまでに空き時間が生じた場合に、制限時間内で立ち寄れる観光スポットを抽出します。ただし、満足度の高い観光スポットを抽出したいので、クチコミ評価をもとに評価スコアを計算して用いることにします。

まず、一定時間で立ち寄れるという地理的条件から、寄り道先の候補となる観光スポットを絞り込みます。
これは、現在の訪問地点と次の目的地の2点からの距離の和が一定(例えば、20km)未満の圏内にある観光スポットに絞ります。近似的に直線距離で考えれば、これは現在地と次の目的地の2点を焦点とする楕円エリア内部に限定されます。
ちなみに、寄り道ではなく、予定していた次の目的地が休業だった場合に代わりの訪問先を見つける問題は、現在地と次の次の目的地の間で寄り道先を見つける問題に帰着します。

寄り道先選択の問題設定

さて、上述のように地理的条件で絞り込まれた候補スポットから、満足度の高い寄り道先を選ぶ方法として、グルメサイトのクチコミ評価(レイティング)を用いることを考えます。しかし、レイティングの単純な平均値を使うと、クチコミ数が少ない場合、レイティングのサンプル平均値の分散が大きくなり信頼性が低くなります。そこで、クチコミ評価の分布をベイズ事後分布(下図)とみなして、その平均値と分散とから信頼性を考慮した評価スコアを定義することにしました。

ベイズ事後分布

あらかじめ、レイティングが小さいスポットは、満足度が低いとみなして候補から除外します。今回は、その条件としてレイティング事後分布の95%信頼区間の下限が3.0超となるスポットに限定しました。
その上で、事後分布平均値  \hat{m} を事後分布の標準偏差 \hat{\sigma} の指数関数で割った値を評価スコアと定義しました(下図)。つまり、\hat{m} が高くても、分散 \hat{\sigma}^2 が大きければ不確実性が大きいので、\exp({\hat{\sigma}}) で割り算して過大評価しないように修正しています。
この評価スコアは、スコア上位には、信頼性が高くて評価も高いお店が並ぶのはもちろんですが、スコア下位には、信頼性は低いがある程度評価されているお店(穴場スポット)が並んでいることが確認できました。

寄り道先スコアの定義

上述のアルゴリズムにしたがって、実際に寄り道先を抽出する実験を行いました。
淡路島の観光を想定して、現在地を南あわじ市にある「元気の森ホール」、目的地を「淡路ファームパーク」としました。両地点からの距離合計が 20 km 圏内において、評価スコアの高い7箇所を抽出できました。そのうち、最も短時間で寄り道できるスポットとして海鮮料理のお店が抽出できています(下図)。

寄り道先の抽出結果

懇親会


最終報告会の終了後に、インターン生をはじめ、役員やメンター、インターンに関わった社員などが集まり懇親会を実施しました。分析や実装でサポートしてくれた若手メンバーも参加して賑やかな懇親会になりました。
余興として、今回実装したレコメンドアルゴリズムにより提示された旅行プランから、実際に行ってみたい旅行プランを選ぶことにしました。上述の草津温泉と淡路島の2つの旅行プランの間で意見が割れたので、最終的に塩澤取締役が選んだ草津温泉の旅行プランに決定しました。
実際に、このプランで旅行してみた感想は、後日ご紹介できるかもしれません。

懇親会に集まったメンバー

懇親会で周遊プランを説明

まとめ

例年通り、インターンシップの4週間は、長いようであっという間でした。インターン生の3名にとっては、問題の具体化も含めて難しい課題でしたが、各自の得意な点を活かして面白い結果を出すことができたと思います。
恒川さんは、トラッキングデータの少ない情報から、基礎集計による知見をもとに適切な特徴量を設計することができました。
藤原さんは、強化学習の報酬設計に、訪問先のレーティングだけでなく訪問先ジャンルの多様性や時間制限などを取り込むことで、満足度の高い周遊ルートを探索できることを示してくれました。
佐藤さんは、寄り道スポットのクチコミ数と信頼性を紐づけて、ベイズ事後分布をもとにシンプルながら効果的な指標を提案することができました。

このように、MLEインターンシップでは、所与のテーマに対して、課題の具体化から、アプローチの選定、アルゴリズムの実装と検証までを一通り体験できる機会を提供しています。このインターンシップを通して機械学習エンジニアとしての働き方の一端でも体験していただければ幸いです。来年も実施する予定ですので、興味のある学生の方は、是非チャレンジしてください。


当社では、新卒採用・中途採用ともに、営業やコンサルタントなどのビジネス職、エンジニア、データサイエンティストを積極的に採用しています。
www.brainpad.co.jp

*1:H. Guo, R. Tang, Y. Ye, Z. Li, X. He, "DeepFM: A Factorization-Machine based Neural Network for CTR Prediction", https://arxiv.org/abs/1703.04247

*2:I. Bello, H. Pham, Q.V. Le, M. Norouzi, S. Bengio, "NEURAL COMBINATORIAL OPTIMIZATION WITH REINFORCEMENT LEARNING", https://arxiv.org/abs/1611.09940