the invention of t88

工作、資格取得、データ分析のことなど

kaggle「Google Smartphone Decimeter Challenge」に参加しました

8/5まで開催されていたkaggleの「Google Smartphone Decimeter Challenge」(通称outdoorコンペ)に参加していました。810チーム中7位ということで幸運にも金メダルを取ることができました。
f:id:take213uv:20210809063616p:plain

解法はディスカッションに投稿しましたが、ここではもう少し詳細に、ポエム成分を追加しながら、コンペを振り返りたいと思います。

コンペ概要

GPSに代表される、人工衛星による位置測位システムGNSSに関するコンペでした。車両に設置されたAndroidスマホのデータを元におおよそ1秒ごとの車両の位置を推定します。

f:id:take213uv:20210809154240p:plain
複数のスマホが車両に設置

舞台はシリコンバレーで一回のドライブごとデータがまとまっていました。
f:id:take213uv:20210809154838p:plain

一口にシリコンバレーといっても、高速道路は遮蔽物が少なく高精度に測位可能、ビルに囲まれた市街地は測位が難しいなど、エリアごと性質に違いが見られました。

f:id:take213uv:20210809155634p:plain:w400
高速道路
f:id:take213uv:20210809155655p:plain:w400
市街地

与えられたデータは、大別すると下記のとおりです。

  • ホストにて算出したベースライン
  • ベースライン算出の元となったGNSS関連のデータ
  • 加速度などのIMUセンサデータ

序盤はベースラインのデータに対して、異常値除去やスムージングなどの後処理を行うアプローチが検討されていきました。上位に食い込むためには、GNSS関連のデータへのアプローチが重要だったように思います。

解法

大きく分けると下記4つのアプローチをとりました。

  • ベースライン改善
  • 相対座標の推定
  • 異常値除去
  • 後処理

ベースライン改善

ホストが算出したベースラインは十分な精度とは言えず、改善の余地がありました。ベースライン算出のためのGNSS関連の元データを使って自力で再構成することで、ベースラインを改善することができました。こちらのnotebookをベースにベースラインの再構成を検討していきました。

位置算出に用いる人工衛星の選択

GNSSは、複数の人工衛星からの信号を元に位置測位を行います。ある条件下の人工衛星からの信号は誤差要因となる可能性があるため、これを除外することで位置測位精度が高まる可能性があります。 ホストのベースライン算出時もいくつか人工衛星を選択するフィルタ条件がありましたが、これに条件を追加しました。

具体的には、仰角(ElevationDegrees)によるフィルタ条件を追加しました。仰角が浅い人工衛星からの信号は大気遅延の影響や遮蔽物の影響を大きく受けます。 これらを除外するために仰角で閾値を設定し、閾値以下の人工衛星からの信号を使わないようにしました。その他信号のSN比などいくつかの変数を条件にしてoptunaでチューニングを回しました。

搬送波位相を用いた疑似距離のノイズ軽減

GNSSは人工衛星と受信機の距離を元にして位置測位を行いますが、この人工衛星と受信機の距離算出には2つの方法があります。 一つは信号が到達するまでにかかった時間を元に距離を算出する方法(コード測位)、もう一つは信号の位相を元に距離を算出する方法(搬送波測位)です。
前者はノイズが大きいが絶対距離が容易に算出可能という特徴があります。ベースライン算出にもこちらが用いられています。後者はノイズが小さいが絶対距離算出が難しいという特徴があります。

f:id:take213uv:20210809161225p:plain
距離のノイズの様子。オレンジの正値に対してコード測位(青)が大きくばらついているのに対して、搬送波測位(緑)はばらつきが小さい

搬送波測位で算出された距離は相対的な変化量であれば容易に使用できるので、コード測位で算出した絶対距離を、搬送波測位で算出した相対距離で補正を行います。具体的には、[元々のコード測位での絶対距離]と、[搬送波測位で算出された距離の変化量+一時点前の絶対距離]の重み付き平均を取る事でこの補正を行いました。 搬送波位相で算出された距離は、AccumulatedDeltaRangeMeters(ADR)という変数で格納されています。ADRは搬送波位相で算出された距離の差分の積算値なので、この差分を取ることで距離の変化量が得られます。ただ、遮蔽物などで信号を見失う等する(サイクルスリップ)とこの積算値がゼロリセットされるため差分値に大きな誤差が生じる点に注意が必要でした。AccumulatedDeltaRangeStateという変数がビットマップでサイクルスリップ、カウントリセットなどの状態を保持していました。この辺りのすべてのステータスは吟味出来なかったので、一番正常状態と想定されるstatus = 25の時のみ補正を行うようにしました。

f:id:take213uv:20210809191100p:plain
ADRの推移(積算値が頻繁に0リセットされる)

その他の公開notebookからの変更点

距離補正項の一つ、[IsrbM]は性質からして固定値であるべきと考え、中央値の定数で置き換えました。いくつかのエリアではこれにより顕著に精度が改善しました。

相対座標の推定

少し前に開催されていたindoorコンペでもそうだったように、outdoorコンペも相対座標による絶対座標の補正が有効では、と当初からdiscussionなどで議論されていました。indoorの時と同様、加速度センサなどのIMUセンサのデータが存在するため、これらのデータから相対座標を推定することができるのでは、と思われていました。しかし、indoorほどそれは容易ではなかったようです。indoorコンペに参加していないので詳しいことは分かりませんが、indoorの時は人間が持って歩いているため加速度センサなどに特徴的なパターンが生じるのに対して、今回は車両に固定されているため特に距離の推定が難しかったのではないかと思います。
このように相対距離を精度よく推定するのが中々難しいという課題がありました。これを解決する手段もGNSSにありました。

ドップラーシフトを用いた車両速度推定

人工衛星と車両の相対速度によって搬送波位相のシフト(ドップラーシフト)が発生します。このドップラーシフトから車両の速度が高精度に推定することができました。
人工衛星・車両の位置、人工衛星ー車両間の距離、人工衛星の速度、ドップラーシフト量がわかれば、車両の速度を推定することができます。
参考文献

人工衛星の位置・速度はGNSSの信号のなかに情報として含まれています。車両の位置、人工衛星-車両間の距離は、位置測位の算出結果によって得ることができます。なので位置測位を行ったのち、その結果を用いて再度車両速度を求めるための計算を行います。
ドップラーシフト量はPseudorangeRateMetersPerSecondとして格納されているのでこれを用います。PseudorangeRateUncertaintyMetersPerSecond を最小二乗法の重みとして用いました。

これによって得られた車両速度は非常に高精度であり、x, y, z成分で与えられるので、緯度経度それぞれの変化量も高精度に算出可能です。これは非常に有用でした。

車両速度+IMUでの相対位置推定モデル

ドップラーシフトから求めた車両速度と、そこから計算した相対位置は非常に高精度ですが、いくつかの時点で欠損が見られました。この欠損の補間のため、IMUセンサのデータも加え、相対位置推定モデルを作成しました。車両速度、各種IMUセンサのdiff、rolling系の特徴量を追加し、計500程度の特徴量を用いてLightGBMにて経度と緯度それぞれの変化量を予測しました。

f:id:take213uv:20210809222032p:plain
経度・緯度の相対座標の推定結果。鬼門だったSJCエリアでも高精度に推定できている

異常値除去

ホストのベースライン、および再構成したベースラインにはいくつか異常値が見られました。これを除去していきます。

瞬間移動の除去

時々、大きく座標がジャンプしている箇所がありました。これについては一つ前と一つ後の相対移動距離を算出し、そのどちらもが閾値を超える点を異常値として除去しました。この方法で明らかな異常値をいくつか除去できますが、異常値が連続して出現する場合や微妙な異常値には対応できず、後述する異常値除去が重要となりました。

ground truthを元にした異常値除去

いくつかのエリアはtrainとtestで走行経路が一致していました。そのため、trainの正解データ(ground truth)を元に異常値除去を行いました。各trainデータに対して、全てのground truthとの距離を算出し、最近接距離が閾値以上の点を異常値として除去しました。

相対座標から算出した基準点を元にした異常値除去

多くのエリアはtestがtrainでは登場していない経路を辿っていました。そのようなケースでは前述した、ground truthを元にした異常値除去が使えません。
この解決策として、相対座標から基準点を算出し、これを元にして異常値を抽出しました。相対座標は精度よく算出できているので、短い期間であれば積算値で妥当な絶対座標を求めていくことが可能です。各時刻の絶対座標を始点として前後60秒の時刻の絶対座標を始点の絶対座標+相対座標の積算値により算出しました。このウインドウをスライドさせていき、同様の処理を繰り返します。これによって、各時刻ごと、「どこかの絶対座標+相対座標の積算値」で算出された座標が60~120点程度得られます。この座標の精度は始点の絶対座標の精度に大きく依存し、場合によっては始点の絶対座標が除外したい外れ値となるケースがあります。ただ発生頻度は高くないので、各時刻で得られた60点以上のデータの5〜95%点のデータを取ることで外れ値を除外することができると考えました。これによって、各時刻ごとの基準データが生成されますので、この平均+2σを異常値判定の閾値として設定しました。全体的にばらつきが発生している点はσの値が高くなり閾値が甘くなる一方、ばらつきが少ない期間ではσが小さくなるため、閾値が厳しくなります。このように区間ごと動的に閾値が調整されることがメリットです。

f:id:take213uv:20210809224237p:plain
生成された基準点データ

閾値設定および補間の考え方

上記の異常値除去は閾値設定のパラメータがそれぞれ存在しますが、基本的にはCVスコアを元に算出し、補間には線形補間、または相対座標の積算により補間を行いました。どちらの補間方法とするかはエリアごと設定しました。異常値が連続して発生する市街地エリアは相対座標による補間、ほぼ一点だけ単独で発生するエリアは線形補間で良好な結果が得られました。おそらく基本的に車は直進しているので、単独点の補間は線形補間で十分だったと推測します。何れにせよ、欠損値は妥当な補間ができると踏んでいたので、異常値のオーバーキルはあまり気にしていませんでした。

後処理

得られた絶対座標のデータに対して、スムージングや補正など様々な後処理を加えていきます。ほかの方のソリューションを見ると非常に創意工夫が見られるパートですが、時間が足りずあまり力を掛けられませんでした。

停止期間の処理

こちらのnotebookでも触れたのですが、車両が停止している期間は座標の誤差が大きくなる傾向が見られました。

f:id:take213uv:20210809225040p:plain
実際は停止しているのに座標がばらついている

これについては、IMUセンサデータなどから停止状態を推定するモデルを作成し、停止状態と判定された区間の座標をその間の平均値で置換するという処理を行いました。データを見る限り、バラつき方にはそれぞれバイアスがあるように見えたので平均値での置換でよいのか、という疑念はあったのですが、結局代替案を検討する時間がありませんでした。

cost minimization

相対座標と絶対座標を用いて最適化を行います。こちらはindoorコンペで広く使われていたsaitoさんの神notebookを使わせていただきました。

weighted phones mean

一つの車両に複数台のスマホが設置されているケースが多いので、この複数台のスマホの推定座標の平均値を求めて最終的な推定値を算出します。これはコンペ序盤にこちらのnotebookで共有したもの*1です。最終的にはこれを改良し、スマホの機種ごと重み付けをできる形にしました。trainのデータを元に機種ごとの重み付けを調整しました。

その他

完全にそのまま流用したもの
カルマンスムーザ
position shift

エリアのグルーピング

前述のとおり、高速道路と市街地では大きく位置測位の精度が異なります。これらエリアの特性ごと処理やパラメータを調整することも重要でした。
エリアのグルーピングには、こちらのnotebookを参考にさせていただきました。このnotebookに、trainとの一致度の要素を追加して計5つのグループに分けました。各グループごとパラメータチューニングや処理の順序など調整しました。

解法のポイント

解法説明の文量から分かるようにGNSS関連のアプローチに中盤以降、多くの時間を割き、スコア向上につなげることができました。特に、ドップラーシフトによる相対座標算出を実現できたのが大きかったと思います。これによって、異常値除去やcost minimizationでのスコア向上につなげることができました。
また、相対座標を用いた異常値除去は終盤土壇場で取り入れたのですが、これも最後の一押しに有効でした。ground truthを元にした異常値除去が適用できるエリアはスコアが悪くインパクトも大きかったので、その他のエリアへの異常値除去に目が向いていなかったのですが、このdiscussionをきっかけに必要性を意識*2し、取り込みました。

コンペ期間の振り返り

twitterでのつぶやきを頼りにコンペ期間をどう過ごしたか振り返りたいと思います。

コンペ序盤、phones meanで金圏に。併せてnotebookを公開した。公開したnotebookを丸コピされたので圧を掛けて消したりした。

最終的にprivate1位だった、taroさんが圧倒的なスコアをたたき出した瞬間。

中盤以降は金圏ボーダーが主戦場だったのでだいぶ精神的にやられてくる。妻にはなんかずっとブツブツ言ってるよ、と指摘されたりした。

ハサウェイにはまる。

締め切り間際のチームマージによる加速に焦る。

コロナの影響で週末は子供を公園に連れていくことが多かったが、開放的な空間でも常にGNSSが脳裏にちらついていた。

大阪城公園の中にある豊國神社で必勝祈願。お賽銭に1000円投入した。

2位に突如として現れた専門家に焦る。indoorの時のようにスコア隠しが出たらどうしよう、と怯える。願いをチーム名に込める。


3.4Xに到達し、フィニッシュ。

おわりに

今回の結果でmasterに昇格することができました。
f:id:take213uv:20210810004334p:plain

ASHRAEコンペから本格的にkaggle参加して約2年。まさか自分がmasterに昇格する日が来るとは、しかもそれがソロ金で、というようにだいぶ驚いています。今後はいろいろな方とチームを組んで学ばせていただけたらよいなと思っていますので、皆さんよろしくお願いします。
とはいっても、この2か月あまり、かなりkaggle重視でやってきて、いろいろ他のことが疎かになっているので、まずはそのケアをするために暫くkaggleはお休みしようかなと思っています。(と言いながら次のコンペの出現を待つ日々)

*1:実はこの公開notebookの処理には若干問題があって、3台以上のスマホが存在するときにフルに効果を発揮しませんでした。恥ずかしながらコンペ終盤に気付きました。

*2:shimacosさんやdehokantaさんの言及により