kaggle「Foursquare - Location Matching」に参加しました
kaggleの「Foursquare - Location Matching」にshunya iidaさんと参加しました。1083チーム中46位でした*1。
日本人kagglerが沢山参加していて盛り上がっている＆NLPの経験を積みたい、ということでH&Mコンペが終わった後、5月中旬から参加しました。 ユニークな題材かつ、テキストの特徴量化や各種高速化・メモリ節約の工夫を学ぶことができて個人的にはとても良コンペでした*2。とくにユニークな手法を構築できたわけではなく、既出の各種アプローチを適用しただけですが、個人的な備忘録として解法や工夫をまとめたいと思います*3。
コンペ内容
位置情報のプラットフォーマである「Foursquare」のデータが題材です。データには、各レコードごと店舗や施設の名前・住所・座標・カテゴリ・URL・電話番号が含まれています。このレコードから各店舗・施設を識別するPOI(Point Of Interest)が同一な組み合わせをマッチングさせるのがコンペの目的です。同一のPOIであっても、各情報は、座標が少し違ったり、名前や住所の表記が異なっていたり、欠損があったりと、情報に揺らぎがありました。これらの揺らぎの中で各ペア間の類似性を評価し、マッチング判定をするコンペでした。
解法
ベースライン
中盤からの参加ということもあり、PENGUIN46さんの公開Notebook (Foursquare - LightGBM Baseline)をベースラインとして使用させていただきました。
＜ベースラインのアプローチ＞
- マッチング候補を抽出する1st stage、同一POIかどうかの２値分類モデルの2nd stageという構成
- マッチング候補の探索範囲をtestと合わせるため、学習データをPOIでGroupKFoldして２分割した上で1st stageに掛ける
- 基本的にマッチングするのは同一のcountryなので、1st stageの処理は国別に行う
- kNNで各レコードごと座標の近傍点を10ずつ抽出しマッチングの候補とする
- マッチしたレコード同士の各文字列の編集距離、kNN時点で算出した座標間距離を特徴量に同一POIかどうかの２値分類モデルをLightGBMで構築
- マッチしたペアの逆向きを補完するpost process（A-Bがマッチ判定されているがB-Aが漏れているときにB-Aを復元する）
アプローチの基本コンセプト、編集距離の並列化・cythonによる高速化など非常に参考になりました。基本的にはこのノートブックを改良していきました。
1st stageの改善
1st stageで抽出する近傍点を10から増やしていけばマッチペアの取りこぼしは無くなっていきますが、線形的にデータ数は増え、メモリ負荷・処理時間も増加していくことになります。コードコンペのためどちらも有限であり、一定以上に到達するとサブが回らなくなってしまいます。サブが回る範囲のデータ数の中で、如何に効率よくマッチングペアを拾えるかというのが重要でした。
単一の算出方法で近傍点の数を増やしていくと段々外ればかり引いていくことになり、効率が良くありません。そこで複数の算出方法を組み合わせる形を検討しました。具体的には、nameのtfidf類似度を加え、距離15 + name tfidf類似度15で1stのマッチング候補抽出を行いました。
2nd stageの改善
元々の特徴量に加えて下記のような特徴量を加えました。
- categoriesの一致率
- tfidfの類似度(name, categories)
- BERT(distilbert-base-multilingual-cased)事前学習モデルのembeddingの類似度(name, categories)
LGBMの特徴量重要度
tfidfの設定
1st, 2ndともにtfidfの類似度の寄与が非常に大きかったので、この部分を特出しで。
tfidfのfitはcountryごと行いました。また、最初は容量的なことを考えてSVDで圧縮をしていたのですが、実際はtfidfの結果はスパースマトリクスで保持されるため容量の負荷は大きくありませんでした。スコア的にも無圧縮の方が良かったのでこちらを採用。
またtfidfのパラメータも色々とiidaさんが検討してくれていて、最終的にはngram_range=(3,3)、analyzer="char_wb"の設定に。こちらもスコア向上に寄与しました。
CV
CVはPOIのgroupKFold２分割で行いました。推論用のモデル構築は、POIのgroupKFold２分割でそれぞれ1st算出・concatしたデータを作り、2ndを目的変数でのStratifiedKFold (n_fold=5)で行いました*4。
kaggle環境での推論に関する工夫
コードコンペなのでkaggle環境で推論を行う必要があり、RAMと実行時間に非常に厳しい制約がありました。この制約内で推論を行うために色々と試行錯誤しました。
%%pythonで1st / 2ndを分離
マジックコマンドの%%pythonを1st stageの処理部に記載することで、独立したプロセスとして実行されます。2nd実行時は1stの処理で変にメモリが掴まれていることもなく、クリーンな状態で実行でき、メモリ問題が良化しました。
2ndのバッチ処理化
test全体で推論処理を回すとメモリエラーが発生しました。推論処理はcountryで閉じた形なので、countryのgroupKFold (n_fold=5)でループを回しました。
ForestInference
推論はforestinferenceを使いました。LGBなどのモデルを使って簡単にGPUで推論できます。わりとpopularなようですが初めて使いました。とても便利。
BERT embベクトルをdictで保持
BERTのembeddingベクトルを類似度計算に使いますが、全てベクトルで展開してしまうとメモリ的にきつい。ということで、各文字列のユニークlistに対してベクトル算出し、その結果をdictで保持しました。ペア間の類似度を計算するときにはループを回して逐次的に取り出して使います。
類似度の計算方法
元々、sklearnのcosine_similarityを使ってましたが、numpyで普通に計算した方が早かったのでこちらに変更。
cumlでkNN
cumlのkNNを使うことで処理が高速化*5。
重複ペアの削除
A-Bのペアがあったときに、B-Aのレコードを削除しました。A-Bがマッチング判定されれば後処理によってB-Aが復元されるため結果には影響せず、大きくデータ量を減らすことができました*6。
試したけどうまくいかなかった
1stのtfidf name類似度近傍抽出に距離しきい値設定
nameは似てるけどすごく遠い候補を削除する。cvでは効いたがLBで悪影響あり、不採用
2nd特徴量に1st抽出時のrankを追加
cvでは効いたがLBで効かず...
nameのカウントエンコーディング
チェーン店とそうでないものでは類似度の価値も違うと思い、nameの希少度をカウントエンコーディングで表現。cvでは効いたが（略）
いろいろなembedding
- S-BERT
- universal sentence encoder
- BERTのファインチューニング(時間も経験も足りず)
参考にした記事
shopeeに関する記事をかなり参考にさせていただきました。
naotaka1128.hatenadiary.jp lab.mo-t.com Shopee - 2nd Place Solutionと上位解法まとめ - Speaker Deck
まとめ
楽しかったけどリークがあって残念だった（小並感）
