outdoorコンペ振り返り

はじめに

2021/05/12~08/04の期間、kaggleで開催されていたGoogle Smartphone Decimeter Challenge (通称: outdoorコンペ)に参加しました。途中までは一人で参加していましたがなかなかにタフなコンペだと感じてきたので残り1ヶ月を切った頃にkyoukuntaroさんとチームマージし、810チーム中18位で銀メダルという結果となりました。 f:id:kutohonn:20210807223842p:plain

この記事ではコンペの概要と私たちの取り組み、そして重要であった点について書いてみようと思います。またこのコンペはindoorコンペとタスクが似ているためこの記事でもいくつか参照しています。indoorコンペの参加記録については以下の記事に書いてますので興味があればご参照ください。 kutohonn.hatenablog.com

コンペ概要

このコンペは、複数の機種のAndroid端末を下記のように車に設置して走行し、得られたデータをもとにして位置推定を行うというものです。車の後ろ側に高性能の受信アンテナが設置されておりそのアンテナから得られる位置がground truthとなります。屋外ということでGNSS(GPSなどの衛星測位システムの総称)による位置推定が一般的な手法となりますが、スマホに内蔵されている受信機はそこまで性能が高くないため、そこをなんらかの方法で補正するアプローチが求められていました。

このコンペの特殊なところとしては純粋に機械学習で位置を推定するアプローチはほぼ機能しなかった点です。代わりにルールベースの処理が多く取られていました。ただその処理の中で必要な情報を抽出するために機械学習を部分的に利用する取り組みを私たちのチーム含め取り組んでいるチームもあり、工夫によっては機械学習アプローチも有効に働き、それを自分で定式化するという点がおもしろいところだと感じました。また後述しますが上位に行くためにはホストから提供されている推定位置のベースラインを改良することも重要だったのですがこれがドメイン知識を要するもので非常にタフな部分でもありました。

評価指標

ground truthと予測値の座標から距離誤差を計算し、その50パーセンタイル誤差と95パーセンタイル誤差の平均値を各走行エリア・スマホごとに計算し平均するというものでした。95パーセンタイル誤差が評価指標に含まれているので単純な距離誤差による評価と比べて誤差が大きいところの影響を受けやすい指標であったといえます。

提供データ

推定位置のbaselineデータ

ホストが基本的な手法を元に計算した推定位置のbaselineデータがtrain/testで共有されていました。このbaselineに対して後処理をかけることによるスコア改善をほとんどの参加者が行なっていたと思います。baselineの作成方法は文章では共有されていましたがコードは共有されていませんでした。この絶対位置推定のbaselineモデルを元に推定手法に改良を加えるには、baselineをまず再現しそれに改良を加えていくことが必要となるのですがこれがなかなか難しく私たちのチームはかなり苦労しました。

加工済みデータ(derived.csv)

後述するAndroid生データにはGNSSの生データが記録されていましたが変数が非常に多く、扱いが難しいものであったためホスト側である程度扱いやすいところまで加工を加えたデータが提供されていました。

Android生データ(GnssLog.txt)

Android端末で記録された加速度・ジャイロなどのIMUデータやGNSSの生データが含まれたtxtファイルです。IMUデータはこのコンペの前に行われていた屋内位置推定コンペであるindoorコンペでもスコアアップに使われていたので、同様の方法で使えるのでは？と思いましたがスマホの機種や測定時期によってデータそのものがなかったり、車載ということもありノイズが多く簡単に扱うことはできない印象でした。GNSSの生データは上位陣の多くが使っていた印象ですがドメイン知識は必須で扱うのに労力を要するものであったと感じています。

取り組み

ここでは主に私の取り組みを時系列でまとめてみようと思います。

ルールベース後処理その①

まずはホストから与えられていたbaselineの推定位置を可視化してみることにしました。可視化を行う中で以下の点に気づきました。

①明らかにおかしな箇所に点がある
②同時刻の複数スマホの位置にズレがある
③推定位置の軌跡が滑らかでない箇所が多く存在

①に対しては前後の時間と距離から速度を算出しその速度が45m/s以上超えたものは外れ値とみなし線形補間することで対処しました。公開notebookでも前後の距離の2σ値を使って外れ値処理を行うnotebookが共有されていました。

②スマホごとに推定位置を可視化すると以下の図のように同じ車に搭載されておりかつ測定時刻も同じため本来同じ位置かあるいはとても近い位置に存在するはずの端末同士の位置にズレがありました。 f:id:kutohonn:20210808221610p:plain そこでアンサンブルの要領で同時刻の場合、各スマホの平均を推定値とすることでスコアが向上しました。また時刻に0.x秒スケールのズレがスマホごとに存在しているエリアもあったので、その場合は時刻と位置を線形補間して平均をとるようにしました。こちらも公開notebookがあったので多くの方が取り組まれていました。この処理により0.5以上のスコアアップにつながったと思います。スマホごとに性能差があるのでは？ということでEDAを行いそれに基づいて加重平均を取ったりもしてみましたが改善しなかったため単純な算術平均を取りました。

③に対してはKalman Smootherを用いた平滑化処理のnotebookが公開されていたのでそれをそのまま用いました。この処理も1.0くらいのスコアアップにつながるものでした。

上記処理は公開notebookも公開されていたので多くの参加者が取り組んでおり、特に独自性はなかったと思います。

相対位置推定

後処理による改善と並行して、indoorコンペで重要であった相対位置推定が今回も鍵になると考え、IMUデータを用いて機械学習で相対位置を推定することに取り組みました。しかしいくつかのモデルやデータ形式で試してみましたが良い予測ができてるようには見えなかったのとindoorコンペで相対位置予測の素晴らしい解法をあげてくれていた方が相対位置推定がうまく言っていないとのdiscussionをあげていたことから一旦保留としました。

ルールベース後処理その②

改めてbaselineの推定結果を地図上で可視化していると以下のことに気づきました。

①停止してそうなところで推定結果に誤差が大きくなっている f:id:kutohonn:20210808225854p:plain ②建物や木などの遮蔽物が多いエリアでは誤差が非常に大きくなっている f:id:kutohonn:20210808225846p:plain

GNSSによる位置推定ではいくつかの誤差が原因で正確な位置推定が困難になってしまうのですがその一つがマルチパス誤差です。これは建物や木などの遮蔽物があったり電波が水面などに反射することで測定結果に誤差が生まれる現象です。上記の誤差もこのマルチパスが原因と考えられていました。そこでマルチパスの対処方法を文献などで調べたのですがあまり良い方法がわからなかったので機械学習と後処理で対処することにしました。

①に対しては車が止まっていることを判定できれば、止まっている時の測定値を平均したりすれば良さそうと思ったので車の速度を機械学習で推定してみることにしました。速度を計算するとなるとIMUデータの加速度などが使えそうですが止まってるかがおおよそ分かればよく正確に速度を計算しなくても良いのでは？と考えたので位置のlag特徴量とその集約特徴量で試してみました。するとこれだけでもそれなりに予測ができていたので計算された速度が0.95m/s以下で2s以上連続している場合、平均を取ることにしました。後からIMUの使用も試してみましたがあまりスコアには差がなかったのでIMUデータは使用しませんでした。

②はdiscussionでも話題になっておりその走行エリアのコレクション名からSJC、downtown、Bermuda Triangleなどと呼ばれていました。このエリアに対してはindoorコンペでも使われていたSnap2Gridという方法で位置補正を行いました。この手法では基準点を事前に用意する必要があり、与えられているground truthデータを基準点として扱うのが良さそうですが、中にはground truthにはない道路をtestデータでは走行してる箇所もあったのでOpen Street Mapからtestデータ近傍の道路を検出し、そこからgridを生成することを試しました。しかしながらスコアは改善しなかったので最終的にはground truthのみ使用しました。このOpen Street Mapを用いたgrid生成に関してはnotebookとして公開しました。

Road detection and creating grid points | Kaggle

ルールベース後処理その③(残り7週間)

これまでの結果から後処理が有効に働いていることは明白だったのでまだやれることがあるのではと後処理を色々試してみました。しかしこの部分に時間を費やしすぎたなぁというのが個人的な反省点です。

前で説明したSnap2Gridは誤差の大きいdowntownエリアのみに適用していました。しかし他のエリアもよくみてみると道路から推定位置が少し外れているところも見られました。しかしそのエリア全体にSnap2GridをかけてしまうとCVは悪化してしまうことから異常がありそうなところだけを抽出してSnap2Gridを適用できないかと考えました。このために以下の方法を取りました。
①Open Street Map(OSM)の道路属性情報で分類・判定.
②trainで誤差が大きいポイント周辺を推定困難エリアとみなす.

まず①についてですがOSMの道路データにはhighwayというカラム名のものが付与されていました。これは道路種を示すもので以下のような分類がされています。

https://wiki.openstreetmap.org/wiki/JA:Key:highway f:id:kutohonn:20210808230924p:plain この情報を使って例えば推定位置が特定の道路種(例えばresidential;住居道路)に属している場合はSnap2Gridを適用するというのを複数のパターンで試しました。良いアイデアかなと思ったのですがCVはなかなか上がらず断念しました。

②については以下の手順で推定困難エリアを定義しました。

baselineに一連の後処理をかける
ground truthとの距離誤差が5m以上の点のみ抽出
shapelyという地理空間データ用のライブラリを使って各点のbufferを取りpolygon化する
このpolygon化された領域を推定困難エリアと定義しSnap2Gridを適用する

実際に定義された推定困難エリアがこちらのようなものです。 f:id:kutohonn:20210808231428p:plain 多くは橋や高速道路のインターチェンジが対応していました。この箇所に対してSnap2Gridを適用することでCV,LBともに若干スコアが上がりました。この辺りでLB scoreは4.8と銀圏内ではありましたが残り１ヶ月を切っており、自分一人では金圏は難しそうと判断しチームマージをしました。

@kyoukuntaro さんとチームマージしました〜！
4切り目指して頑張ります！https://t.co/6a58S0DLmd pic.twitter.com/zkXPJuLlMb
— きょうへい (@kuto_bopro) 2021年7月9日

IMUデータによる位置補正モデル(残り4週間)

この時期にIMUデータを用いて位置を補正する機械学習アプローチがnotebookで公開されていました。

Predict Next Point with the IMU data | Kaggle

この手法に線形補間でデータを倍に水増しし、さらに新たな特徴量を追加して誤差の大きいdowntownエリアを対象に学習、予測することでスコアを0.2改善することができました。この方法を応用して相対位置を推定することもできるのではと考え実装したのですが結果が芳しくなかったので断念しました。

baselineの再現(残り3週間)

これより少し前からdiscussionでは上位者はGNSSの生データや補足データセットを使ってbaselineの絶対位置を改良しているようなことが示唆されていました。

www.kaggle.com

これらのdiscussionの情報をもとに方針を切り替え、絶対位置推定モデルの改善に取り組むことにしました。具体的には以下に取り組みました。

①補足データであるOSRデータを用いて衛星位置を修正する

②baselineを再現し工夫を加えることでbaselineを改善する

①に関して衛星位置は元々derivedファイルに与えられていましたが、データの説明欄に衛星位置には~1mくらいの誤差があるとの情報がありました。そこでまずこのレポジトリで提供されているjsonファイルをデコードし、GNSSからの受信情報(エフェメリスデータ)を取得しました。その後このPDFの情報をもとにオイラー方程式などを活用し衛星位置を推定しました。GNSSにはアメリカのGPSやヨーロッパのGALILEO、ロシアのGLONASSなど数種類のの衛星測位システムがありましたが、この方法で推定するとGPSとGALILEOのみしか妥当な衛星位置が推定できませんでした。原因はわかりませんでしたが時間もなかったので使用可能なGPSとGALILEOのみ衛星位置を修正してみることにしました。この修正した衛星位置は後述のbaselineの再現時に使用しましたが大きくスコアには影響していませんでした。ただしbaselineのブレンド時には効果がありそうだったので採用することにしました。

②については主に運営から提供されていたこのdiscussionとそれをもとにbaselineの再現を試みたnotebookを元にbaselineの再現に取り組みました。チームメイトにも協力を仰ぎ、実装を行ったのですがなかなかbaseline相当の絶対位置推定ができず残り1週間となってしまいました。このままではまずいと感じ、現時点でのコードを公開しdiscussionでアドバイスを仰ぎました。すると何名かの方からコメントをいただき、使用する衛生や最小2乗法の重みを見直し改良することによってなんとかbaseline相当のスコアの絶対位置推定モデルを得ることができました。またチームメイトのアイデアで衛星の角度が低い場合、遮蔽物の影響を受けやすいためノイズになるのでは？という仮説のもと、角度が閾値以下のものは取り除くことでCVは0.2とかなり向上したのですがLBは0.1悪化してしまい、リスクが高いということで導入はしませんでした。もっと改良を加えたかったのですが残り2日と時間もなかったので2パターンの方法で絶対位置推定を行い、与えられていたbaselineとブレンドすることによって絶対位置推定結果を改善することができました。これにより最終スコアがPublic LB:4.3(30位)でコンペを終えました。

重要であったポイント

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

後処理

ここが一番取り組みやすい部分で多くの参加者がコンペ当初からここに力を入れていたと思います。基本的には推定位置を地図上に可視化し異常がありそうなところを目視で見つけそれに対処するための後処理をルールベースや機械学習で考えるというものでした。上位陣の結果を見るとこの部分だけでも銀圏上位に行けていたようです。また上位陣はDoppler ShiftやAccumulated Delta Rangeと呼ばれるGNSS生データに存在している変数を使うことで車両速度をかなり正確に推定し、その速度値をKalman Smootherに観測値として与えたり最適化の変数として与えることで大きくスコアを改善していた印象です。

絶対位置の推定

ここが上位陣との分かれ目であり1番重要であった気もします。ホスト提供の絶対位置はやはりそこまで良いものではなかったようで、上位陣はここの部分でかなりスコアを改善されていました。 GNSS生データやderivedデータを用いてノイズとなっている衛星をマスクしたり、衛星ごとに重みを変えたりすることでbaselineのスコアを0.5以上改善していました。また衛星の角度が低い場合マスクするというアプローチでスコア改善をしてる方もいました。僕らもここでスコアアップを狙ったのですがもう少し早めに取り組むべきだったというのが終わってから感じたことです。

相対位置の推定

私たちはうまく相対位置を算出することができなかったのですが、一部チームでは相対位置を機械学習で算出し、indoorコンペの時のように絶対位置と相対位置のコスト最小化でスコアを改善しているチームもいました。

その他、様々なアプローチがありましたがまだ全ては追えていないので後からまた見返したいと思います。

感想

これまでに参加したコンペの中で1番ドメインの勉強をしたコンペでした。全くわからないところから論文や書籍、英語ドキュメント、スライドなど様々な情報源から少しずつ理解を進め、進捗が少なくとても苦しい時期もありました。とても苦しかったですが短期間でもゼロから現在の状態までいける(まだまだ浅い知識ではありますが)という自信を得ることができました。これは今後、ほかのことにチャレンジする上でとても良い経験になったと思います。

またこのコンペを通してNotebook Expert, Discussion Expert,Competition Masterに昇格できました。 f:id:kutohonn:20210809100219j:plain 特にCompetition Masterは目標の一つであったのでとても嬉しかったです。DiscussionやNotebookに関しても毎コンペ少しずつ取り組むようにしていて、情報共有することによるメリットも個人的には感じているのでこれからも引き続き取り組んでいきたいと思います。長ったらしい文章になってしまいましたが読んでいただきありがとうございました。