KDD2017に参加してきました

はじめに

こんにちは。AIシステム部研究開発グループの春日です。当グループではCV/NLP/RLといった技術領域を中心に研究開発を行い、実際のサービスへの活用を行っております。近年では会社として次の柱とすべくオートモーティブ事業へも注力しており、ここで活用される機械学習技術も当グループで開発を担っています。そこで、KDDというデータマイニング分野でのトップカンファレンスを聴講しにいき、オートモーティブ事業関連で活用されている技術についてキャッチアップしてきました。今回はその内容についてお伝えしていきたいと思います。

KDDとは

KDDの正式名称は「International Conference on Knowledge Discovery and Data Mining」です。今回は23回目の開催であり、1990年代にデータマイニングという研究分野が明確に確立されてから現在も盛んに研究発表がなされています。開催期間は8/13-17の5日間でした。初日はTutorial Day、2日目がWorkshop Dayという特定のテーマに沿った発表です。3-5日目がMain KDD Conferenceで、採択率約10%で採択された優秀な論文が発表されます。

開催場所

開催場所は、カナダ・ハリファックス (Halifax, Nova Scotia - Canada) です。日本からだと直行便がなく、最短で約17時間はかかる場所です。小さい町ですが港町として栄えており、非常に過ごしやすい場所でした。

kdd-image7.png

[ 会場のHalifax World Trade and Convention Centre]

さすが、港町というだけあって平然とロブスターが大量に叩き売りされています。

kdd-image8.png

[ロブスターの陳列]

近年のデータサイエンスブームの波を受けたこともあり、過去最多の1143本が投稿され、Main Conferenceに採択されたのは100本、Posterに採択されたのは116本でした。

セッションの様子

投稿された論文のうちMain Conferenceに採択されると口頭での発表ができます。カテゴリごとに複数の会場があり、各会場とも300人程度のキャパシティがあります。人気なところは立ち見になることもあります。Google社の講演 TFX: A TensorFlow-Based Production-Scale Machine Learning Platform (Denis Baylor et al.) は大変盛況でした。

kdd-image19.jpg

[Main Conferenceでの発表の様子(KDD2017での講演より)]

一方で、Posterに採択されると、19:00-22:00の夜の時間帯で会場に自身の研究内容をポスターで展示し、参加者からの質疑応答に応える形式で発表がされます。

kdd-image12.jpg

[Poster発表会場の様子(KDD2017でのポスター展示より)]

注目の論文

今回KDDに参加した中で、オートモーティブドメインにおいて注目すべき論文を取り上げて紹介します。

  • The Simpler The Better: A Unified Approach to Predicting Original Taxi Demands on Large-Scale Online Platforms (DiDi Chuxing)

こちらは中国の配車最大手「DiDi Chuning」による論文 The Simpler The Better: A Unified Approach to Predicting Original Taxi Demands on Large-Scale Online Platforms (Yongxin Tong et al.) です。DiDiはUber Chinaを350億ドルで買収したことで一大ニュースとなった有力企業です。そのDiDiが主力事業としているタクシー配車におけるタクシー需要のオンライン予測システムに関する論文です。UOTD(Unit Original Taxi Demand)とは、下図で示すようにそれぞれのPOIや時間ごとのタクシーの需要を意味します。ここでは1時間ごとのZhongguancun Software Parkにおけるタクシー需要の予測値を示しています。

kdd-image18.png

[タクシー需要のオンライン予測 [1]]

特徴的なのが、DeepLearningを代表とする複雑なネットワークモデルを用いて予測するのではなく、以下の式で示すような単純な線形回帰モデルで予測している点です。これにシンプルな正則化項を加えただけのモデルです。

kdd-image9.png

[需要予測に用いているモデル [1]]

ただし、特徴量は合計で2億次元以上という非常に大規模なものを用いています。これには、時間や天気、POIといった様々な特徴を組み合わせたものも含みます。

kdd-image10.png

[大規模な特徴量構成 [1]]

このようなモデルを用いている背景にはビジネス観点があります。それは法規制等の環境の変化に伴って、新たな特徴が加わるごとに、モデル自体を見直すのは非常に高コストであるからという考えです。DeepLearningのようなモデルは、入力が変化する度にハイパーパラメーターチューニングに非常に時間やリソースがかかってしまうため、モデルは線形回帰と固定して特徴量だけ再設計することで、新たな予測をするということです。サービスから得られた実データを用いた実験では、NNやGBRTといった手法より高精度で予測できています。 近年では、AI = DeepLearning という認識が広まりつつあるのですが、ビジネスへの活用という観点ではこのような古典的かつシンプルな線形回帰で十分なバリューを発揮するという意味で非常に面白い論文です。

[1] The Simpler The Better: A Unified Approach to Predicting Original Taxi Demands on Large-Scale Online Platforms (Yongxin Tong et al.)

  • A Taxi Order Dispatch Model based On Combinatorial Optimization (DiDi Chuxing)

同じくDiDiによる論文ですが、こちらはタクシー配車におけるDispatchを扱ったものです A Taxi Order Dispatch Model based On Combinatorial Optimization [Lingyu Zhang et al.] 。Dispatchとはタクシードライバーと顧客の配車オーダーの割当を意味し、これをどのように最適化するかという問題です。まず前提として、顧客が配車オーダーを出した段階で、ドライバーにリクエストが送信されます。ドライバーはそれを承諾するか拒否するかという行動をとることができます。よって、どのオーダーをどのドライバーに割り当てれば承諾の成功確率(=SR)を最も高くできるかを考えなくてはなりません。単純には、配車オーダーがあった地点から最も近い地点のドライバーを割り当てるといった方法が考えられます。

kdd-image15.png

[オーダーとドライバーの位置関係の例 [2]]

DiDiの提案手法では、まずドライバーの承諾確率をモデル化します:pij=p(y=1|oi,dj) oiはオーダーに関連するETAやPOIのカテゴリーといった特徴量、djはドライバーに関連する過去の承諾率や営業エリアといった特徴量です。さらに曜日や時間といった特徴も加えて、承諾確率pijをモデル化します。ここではLogistic Regressionが用いられています。 この承諾確率を用いてSRの平均を最大化するオーダーとドライバーの割当の組み合わせを以下に式に従って最適化します。

kdd-image16.png

[Order Dispatch Problem [2]]

この際、Hill-climbing Algorithmを用いて最適解を求めます。北京市内の実データに適用実験した結果、SRがベースラインモデルの80%から84%に向上したということです。

kdd-image17.png

[実験結果 [2]]

DiDiは自社にどんどん蓄積される豊富なデータを用いて、より効率的なモデルの独自開発を行っており、今後も注目すべき企業だといえます。 [2] A Taxi Order Dispatch Model based On Combinatorial Optimization [Lingyu Zhang et al.]

  • Planning Bike Paths based on Sharing-Bikes' Trajectories (Microsoft Research)

こちらは最近日本進出でも話題となったMobikeのデータを用いた自転車専用レーンの設計計画に関するMicrosoft Researchの論文 Planning Bike Paths based on Sharing-Bikes' Trajectories [Jie Bao et al.]

kdd-image14.png

[Mobikeユーザーの走行軌跡データ(KDD2017での講演より)]

中国では大気汚染や交通渋滞の解消のためにシェアバイクが急速に普及しています。しかし、自転車専用レーンが整備されていないため、安全性が不十分という問題があります。そこで、予算という制約のもとで、いかに効率的に専用レーンを建設すべきかが今回の目的です。 各ユーザーの走行軌跡に対して建設した専用レーンのスコアをscore(,)=ssegs()s.ls.lと定義します。これを合計したスコアTscore(,)を最大化するように専用レーンを建設する計画を立てます。 方法はシンプルで、①開始点を抽出する ②Greedy Network Expansionによって道路リンクを繋いでいく というステップで最終的に建設する道路ネットワークを抽出・可視化します。 ①の開始点の抽出ですが、単純には最も頻繁に使われる上位数点を用いるといったことが考えられます。そうすると、頻繁に通る道はたいてい近い場所にあることが多いので、かなり近い範囲で開始点が定まってしまうことが問題です。そこでSpatial Clusteringを行うことで、空間的な広がりも考慮しながら開始点を定めるというところが本手法のコアです。これによって、下図で示すように、地図上で広がりのある道路ネットワークを可視化できていることがわかります。 ②のGreedy Network Expansionでは、①で決めた開始点を繋ぐように貪欲に道路リンクを探索していきます。もちろん予算という制約があるので、出来る限りの開始点を繋げるように道路リンクを広げていきます。

kdd-image11.png

[Spatial Clusteringを用いた結果 [3]]

[3] Planning Bike Paths based on Sharing-Bikes' Trajectories [Jie Bao et al.]

KDD Cup 2017

最後に KDD Cup というデータ分析コンテストについて共有します。KDD Cup では提供されたデータセットに対して課題が設定され、その課題におけるモデルの精度を競うコンペティションです。世界的にも権威と歴史がある大会で、トップクラスのデータサイエンティストが競い合います。今回のテーマは、''Highway Tollgates Traffic Flow Prediction" でした。課題設定は2つあり、①Travel Time Prediction ②Volume Prediction です。ここでは、①Travel Time Predictionについて取り上げます。

kdd-image13.png

[Highway Tollgates Traffic Flow Prediction [5]]

このタスクは交差点から料金所の旅行時間を予測するというものです。例えば上図でいうと、IntersectionAからTollgate2の区間での車両の通過時間を意味します。用いるデータセットは各区間の車両軌跡データ・該当エリアの天気・道路ネットワークです。評価指標は移動時間予測タスクにおける一般的な指標であるMAPE(Mean Absolute Precentage Error) です。優勝チームであるTeam Convolutionは、MAPE=0.1748でした。このチームが優勝したポイントはモデル・特徴・データという3つのレベルでのアンサンブル学習にあります。モデルレベルではXGBoostやMultilayer Perceptron等のモデルを用いたアンサンブル学習とします。特徴レベルでは異なる減衰係数やスムージング係数等を用いて算出した特徴量を組み合わせたものをアンサンブル学習させます。データレベルでは異なる滑走窓の値や分割数でのデータによりアンサンブル学習させます。このように3つのレベルでたくさんアンサンブル学習させることにより汎化性能を上げ、MAPE = 0.1748という精度を得られています。かなりテクニカルではありますが、基本的には複雑なモデルを用いずに、BoostingやMLPといった古き良き古典的なモデルを用いている点が面白いです。実際のビジネスの場でも最新の複雑なモデルではなく、広く一般的に使われているモデルを用いる場面も多々あります。

[5] KDD Cup 2017

全体の感想

KDDという学会は扱う分野がかなり幅広いのですが、今回は主にオートモーティブ事業関連について取り上げました。他にもClusteringやGraphなどの理論寄りに関する研究から、Medical DataやRecommendationといった実務寄りの研究まで多様な研究が発表されていました。ご興味ある方はこちらのAccepted Paperからご覧下さい ( http://www.kdd.org/kdd2017/accepted-papers ) 今回の学会参加を通して、最先端のオートモーティブ事業で取り組まれている技術についてキャッチアップできたことはもちろん、参加者の方々とのネットワーキングができたことも大変刺激的で良い勉強になりました。 DeNAでは国際学会派遣制度というものがあり、私のような新卒1年目でも積極的に学会に参加することができます。こういった制度を活用してスキルアップできる環境は素晴らしいと思います。一緒に働いてみたいと思われた方は是非ご一報下さい!

ツイート
シェア
あとで読む
ブックマーク
送る
メールで送る