Indoorコンペ振り返り

はじめに

2021/01/28~05/18の期間、kaggleで開催されていたIndoor Location & Navigation (通称: Indoorコンペ)に参加しました。twitterで知り合った4人の方とチームを組み、1170チーム中16位をとることができたので振り返り記事を書こうと思います。なおこの記事では自分たちのソリューションではなく、どのような趣旨のコンペであったか、どういう取り組みが重要であったかに重きを置いて書こうと思います。

コンペ概要

屋内の位置推定コンペ。もう少し具体的にいうとユーザが持っているスマホ内蔵のセンサデータや屋内施設に設置されているwifi端末, bluetooth端末から受信するデータを用いて、ある時間におけるユーザの位置(x,y)と建物の階数(floor)を推定するというもの。

評価指標

今回予測するのは x,y, floorでありx,yはtargetとの距離の平均誤差で与えられており非常にわかりやすいもの。floorの方はtargetとの絶対値誤差で重みがp=15というように設定されているため、floorを間違えてしまうとスコアに大きく影響するというものでした。

提供データ

Android APIを使ってスマホから取得したデータがtxt形式で与えられていた。与えられるデータは大きく3つ。

• wifiデータ

  • スマホが受信した周囲のwifi端末の情報
  • wifiのSSID(ネットワーク名)、BSSID(端末のID)、RSSI(電波強度)など。

• センサデータ

  • 加速度、ジャイロ、回転、磁気などスマホで測定できるセンサ値。
  • 測定した時刻がそれぞれに紐づいている。
  • データ数が一番多い

• beaconデータ

  • スマホが受信した周囲のbluetooth端末の情報
  • wifiと似たようなデータ
  • ただしwifiよりデータ数が少なく推定精度も低いため今回のコンペではあまり使われていなかった印象

上記に加えて建物の構造を示すpngファイルやjsonファイルなどのメタデータも提供されていた。建物は24siteが予測対象だった。 wifi,センサ,beaconデータはpathごとにtxtファイル化されていた。pathというのは以下の図のような連続的な移動のまとまりのこと。以下の図はpathごとに色分けされている。

txtファイルのままでは扱いにくいのでデータセットを作成するところからのスタートで、コンペ当初はさまざまなデータセットが公開されてた。 floorの予測は99%の精度のnotebookが公開されるなど位置推定と比べるとそこまで難しいタスクではなく、x,yの予測をいかに行うかが重要であった。(ただし公開notebookは精度100%ではない&floorのミスはスコアには大きく影響するためfloor予測モデルを自分たちで作成するのも重要ではあった) 公開notebook及びソリューションを見るとwifiデータを使ってNNやlightGBMに与えて位置推定をするというのが本コンペの基本的なアプローチであった。

公開されていた後処理

本コンペはおそらく参加者全員が使っていた公開notebookの後処理が2つある。この2つを後処理として加えるだけで大きくスコアを改善することができた。 また上位陣の多くはこの処理を複数回繰り返すことでさらにスコアを伸ばしていた。（弊チームでは6回繰り返していた）

(1) Cost minimaization.

• 機械学習で予測した位置(絶対位置)とセンサデータから計算される相対位置を組み合わせ連続値の最適化問題を解くことによってより正確な予測にする手法。
• ホストのGitHubでセンサデータから相対位置を算出するコードが公開されており(精度はそこまで高くない)、この手法を紹介してくれた公式notebookではその相対位置を用いて最適化を行なっていた。
• 機械学習で予測される絶対位置もセンサデータから計算される相対位置も誤差を含んでいるがこの最適化問題を解くことで予測精度を高めることができ、コンペ終了後の解説ではカルマンフィルタ(スムーザ)と等価の処理を最適化によりおこなっていることが共有された。

(2) Snap to grid.

• trainデータのtargetであるx,yの点をgridとみなし、そのgridの近くに予測値がある場合、gridの座標を予測値とする(gridへ予測値をsnapする)というヒューリスティックな手法。
• train/testの多くが同じような位置に存在していたことから本コンペでは非常に強力な後処理手法だった。

重要であったポイント

終了後の解法を見て本コンペで特に重要であったポイントは3つあると感じた。

機械学習モデルによる位置推定

• ここが一番取り組みやすい部分で多くの参加者がコンペ当初からここに力を入れていたと思う。
• wifiデータセットの作成が重要で、予測対象の時刻とwifiの計測時刻の差分が大きいものはノイズとなるためそのデータを取り除くことが重要だった。(弊チームはこれだけで銀圏モデルができていた模様。)
• モデルはMLP, lightGBM, RNN, kNNなどが使われていた。NNの方が精度が良く多くの人がそちらを使っていた印象。
• 1位, 2位はweighted kNNを使っていたようで非常に強力なモデルであったみたい。ただ単純にモデルを適用というわけではなく色々工夫されていた。
• 上記例は全て回帰問題としてx,yを学習していたが、2位のチームはfloorを細かいセグメントにわけ分類問題として解く手法を行なっておりとても新鮮だった。
• 7位や9位のチームはpseudo labelingを行うことでスコアを大きく向上させていた。後処理やアンサンブルをしたものを使って繰り返しpseudo labelingを行うことでpseudo labelの精度をあげた結果スコアの大幅な向上につながったみたい。弊チームや2位チームもpseudo labelingを試していたが効果は薄かった。

  うちのチームもPLは殆ど効かなかったですね。何でだろう。。 https://t.co/VpNQkn3nZh

  — まます (@mamas16k) 2021年5月19日

相対位置推定

• 概要で述べたように本コンペではcost minimaizationの後処理が非常に強力であった。
• しかしそこで使用している相対位置は精度が高くなかったため、相対位置を何らかのモデルで推定することが重要であった。
• site, floorごとにパラメータを調整した歩行モデリング,RNNやMLPなどのNNモデルが利用されていた。
• 弊チームではsite,floorごとに線形回帰モデルでホストの相対位置を補正するアプローチをとっていた。(ただし上位陣がやっていた手法と比べると強力でなかったと思う)
• この相対位置の推定を行っていたのは金圏、銀圏の一部のチームだったと思う。

離散最適化

• 完全には把握できていないが解法を読む限り、これを行っていたのは入賞圏や一部の金圏チームのみだったと思う。
• そもそもの前提として本コンペはtrain,testの予測点がかぶっているケースが多くそれによりSnap to gridが大きな効果をもたらしていた。
• そのため予測値がどのgridに紐づくかがスコアに影響する。
• 例えば以下は後処理後の予測値を繋いだpathであるがオレンジ色のpathを右側をスタートとして見てみると、明らかにおかしなルートをとっていることがわかる。

• 2点目3点目は下の歩行通路に本来は来るべきだとこの可視化を見ると気づくことができる。これらをより正しい位置に修正するために通路に存在するgrid(train dataの点)とそれらを結ぶ経路をグラフとみなし最適化を行うことで予測値を修正することが重要だった
• この離散的な最適化問題を1位は複数の制約条件を加えたBeam Searchによる最適化、2位は複数の制約条件を加えたgreedy法による最適化,11 位は動的計画法による最適化を行なっていた。
• 今聞くと非常に納得感が強いがコンペ中はこの発想に全く至らなかった。

感想

このコンペはモデリングだけでなく後処理が非常に重要で、機械学習だけでなく数理最適化の技術やヒューリスティックな方法などさまざまな工夫が解法に見られたコンペで、解法を読んでいてとても面白かったです。 参加した感想としてこのコンペは考えないといけないことが非常に多く、一人では全然手が回らなかったなと思います。そういう意味で今回チームを組んだおかげでモチベーションも維持でき、やることを分担したおかげで銀圏に入ることができたと思っています。チームメイトにはとても感謝です。現在似たコンペとしてGoogle Smartphone Decimeter Challenge という屋外の位置推定を行うコンペ(通称:outdoorコンペ)も開催されているので今回学んだことを元に取り組んでみようかなとは思っています。 最後まで読んでいただきありがとうございました。

解法

参考までに僕たちのチームの解法をおいておきます。

16th place solution www.kaggle.com