AHC022の振り返り

Atcoder Heurstic Contest022に参加し最終順位は234位/961でした。 この記事ではコンテストの振り返りをして取り組んだことをまとめたいと思います。

問題設定

• L行L列のトーラスなグリッドワールドがある
• グリッドワールド上に出口セルがN個、グリッドワールド外にワームホールがN個存在しそれぞれ1対1で繋がっているが対応関係は不明
• 最初にグリッドワールドの各セルの温度を0-1000の整数で自由に設定できる。ただし隣接するセルの温度差に応じた配置コストが発生する。
• 任意のワームホールからグリッドワールドに移動し気温を観測する行動を最大10000回実施可能。ただし観測によるコストが発生する
• 観測する温度には指定された標準偏差Sのノイズが乗る。また温度は0-1000にクリップされる
• 目的は観測によって得た情報をもとにワームホールと出口セルの対応関係を当てること

問題詳細 atcoder.jp

直感的にはセルを正しく区別できるように温度差をつけてたくさん観測をすれば温度を正しく推定できそうですが そうすると配置コストと観測コストがかかるのでそこを抑えつつうまく推定を行う問題と言えます。

解法概要

解法の要約は以下です。

seed=0のビジュアライザの可視化結果

配置パート

• クリップの影響を受けにくくするためにベース温度を500度に設定
• 出口セルの近傍9マスを500度+-一様分布によるランダムノイズとして温度を設定する
• 温度設定の一様分布の温度幅は標準偏差ごとにoptunaによるパラメータチューニングで決定する
• 対象セル以外はコストを減らすために近傍セルの平均をとりスムージングする

推定パート

• 全ての出口セルの近傍9マスを指定回数観測する
• 出口セルとワームホールを二部グラフとみなし最小重み完全マッチングで割り当てを決定する
• 二部グラフのエッジの重みは「ワームホールの観測データの確率分布」と「温度クリップを考慮した出口セルの真の確率分布」のKLダイバージェンスを使用
• 観測回数は標準偏差ごとにoptunaによるパラメータチューニングで決定する

取り組みの詳細

評価指標のトレードオフの理解

評価指標は以下の式で表されます。

記号	説明
W	エラー数
	配置コスト
	観測コスト

評価指標中の変数としてエラー数と配置コスト、観測コストの3つがあります。ただこの式を見ただけではどの指標を改善すればどれだけスコアが上がるかが分からなかったので、トレードオフを理解するために適当なデータを用意しスコアのシミュレーションを行いました。 エラー数、配置コスト、観測コストの3つのトレードオフを見たいので以下のように極端なケースでの比較を行いました。

①エラー数と配置コストのトレードオフを見るために配置コストを最も大きいランダムケースと最も小さいゼロケースで比較
②エラー数と観測コストのトレードオフを見るために観測1回ケースと観測10000回ケースで比較

分析の結果、平均エラー数が30件以上ある場合はどれだけ配置コストや観測コストを節約してもスコアが上がらないことがわかりました。この分析をした2日目時点ではエラー数がまだ平均40件ほどあったのでそこからは基本的にエラー数を減らすことに注力しました。

温度配置

出口セルを区別するために温度配置を決定するパートです。 元々baselineのコードとして与えられていたのは一番左の出口セルのみ温度を順番に1度ずつ上げていくというものでした。 これをランダムに温度配置をしたりグラデーションをつけてコストを減らすみたいな配置を試しました。

そこからさらに色々試行錯誤した結果、出口セルの周囲のみbase温度+-一様分布のノイズを加えるという形に落ち着きました。これは出口セルごとに異なる温度配置パターンをつけるのが目的です。base温度はクリップされる影響を小さくしたかったので500度としています。

与えられる標準偏差によって必要な温度差が変わるので標準偏差ごとにデータを100件生成し、optunaで最終スコアが最大となる一様分布幅を決定しました。この方針が大体中盤に固まりました。 (左が標準偏差S=1 右が標準偏差S=900)

また近傍以外の温度は観測を実施しないため何度でも良いです。そこで配置コストを減らすために周囲4マスの平均を取り温度をスムージングする後処理を実施しました。

観測

ワームホールから出口セルに移動し気温を観測することで情報を集めるパートです。 まずはエラー数を減少させることに注力したかったので観測回数は最大である10000回行い、観測したいセルに対して観測回数が均等になるようにして観測を行なっていました。(ex:セル数100件,近傍9マスを観測する場合10000//(100*9)=11件/セル) その後エラー数がある程度減ってきたタイミングで観測コストを節約するために標準偏差ごとに観測数を変えるようにoptunaを使いパラメータチューニングを行いました。ここはあまり工夫したポイントはないです。

推定

観測結果をもとに出口セルとワームホールの対応関係を推定するパートです。 序盤は観測によって得られた近傍9マスの期待値と出口セルの近傍9マスの真の温度のRMSEが最小となる両者の組み合わせを対応関係として選んでいました。ただしこの方法だと同じ出口セルが複数回選ばれ1対1の対応関係を得ることができないケースが存在します。そこで出口セルとワームホールを二部グラフとみなしRMSEをエッジの重みとした最小重み完全マッチング問題として解くことで1対1の対応関係が得られるようにしました。実装はnetworkxのモジュールを使用し以下の様な感じで実装しました。

# Solver classのmethod
def get_matching_results(self, cost_matrix):
    G = nx.Graph()
    G.add_nodes_from(range(self.N), bipartite=0)
    G.add_nodes_from(range(self.N, 2*self.N), bipartite=1)
    edges = []
    for i in range(self.N):
        for j in range(self.N, 2*self.N):
            weight = np.nanmean(cost_matrix[i, j%self.N])
            edges.append((i, j, weight))
    G.add_weighted_edges_from(edges)
    matching_results = bipartite.minimum_weight_full_matching(G)
    return matching_results

エッジの重み

元々観測によって得られた期待値とセル温度の真値のRMSEをエッジの重みとして利用していました。サンプルサイズが十分にある場合は標本平均は母平均に近づくので考え方としては良いのですが、観測される気温は0から1000でclipされてしまうため特に標準偏差が大きいケースでは以下に示すように標本分布の期待値が母平均(真の温度)とは一致しなくなります。

そこで真値の温度をそのまま使用するのではなくclipされた場合の期待値を使用する様にしました。方法としては以下のコードのようにサンプリング後にclipして平均を取ったものを真の期待値として扱いました。

# muがセルの真の温度 Sが標準偏差
# サンプリングしてclipすることでclipされた正規分布の平均と標準偏差を求める
sampled_data = np.random.normal(mu, S, 100000)
clipped_data = np.clip(sampled_data, 0, 1000)
clipped_mu = np.mean(clipped_data)
clipped_std = np.std(clipped_data)

加えて元々は分布の期待値のrmseでエッジの重みを計算していましたが、2つの確率分布がどれだけ似ているかを表現したかったので2つの確率分布のKLダイバージェンスをエッジの重みとして扱いました。 正規分布のKLダイバージェンスは平均と標準偏差から求めることができる様なので以下のように実装しました。

def get_kl_divergence(mu1, mu2, sigma1, sigma2):
    return np.log(sigma2/sigma1) + (sigma1**2 + (mu1-mu2)**2)/(2*sigma2**2) - 1/2

qiita.com

標準偏差であるsigmaを標本標準偏差で計算するとスコアが下がったのでこちらは既知である母標準偏差を使用しました。 ただし今考えると標準偏差が大きいケースでは温度クリップの影響を受けて正規分布を仮定できないのでそこはこの方法だとあまり良くなかったかもなと思います。

その他取り組み

• 異なる距離関数の使用 サンプリングデータのMAEや最適輸送に使用されるwasserstein距離などを分布の近さとしてエッジの重みに使ってみましたがスコアは改善しませんでした。また機械学習におけるアンサンブルの要領でそれぞれの距離関数でマッチングした結果をもとにvotingを行い最も多い候補を採用することも試しましたが特に改善はしませんでした。

• MCMCで少数の標本から事後分布を推定
  少ない観測で分布をいい感じに推定できればと思いMCMCを使って色々試していましたがスコア改善には繋がりませんでした。

• streamlitでweb visualizerを作成
  手元での検証では100件のデータに対する最終スコア、平均エラー数、平均配置コスト、平均観測コストによって手法の良し悪しを判断していました。ただしスコアだけだとどこが悪いかの判断が難しいことから実行結果の可視化をするweb visualizerをstreamlitで作成しました。この可視化によってどこでミスをしているか、どのくらい誤差があるか、どこで配置コストがかかっているかなどを見ていました。

上位解法

上位解法を聞く中でなるほどなと思った内容をメモとして残しておきます。

• 1点のみ高温にして相対移動をした時に温度が低いか高いかでセルの位置を判定する
• 隣接セルの温度差を滑らかにするために近傍4マスの平均を取る処理を無限回実施する
• サンプルから得た尤度を正規化し対応確率を推定
• 正規分布の区間推定を利用し真値-観測値の誤差が生じる確率をもとに対応確率を推定
• ワームホールと出口セルの対応関係を表す確率行列を縦横正規化することで同一のマッチングが発生しない様にする
• 確率の正規化の際にp = p / (1.0-p)という処理を加え確率に差がつきやすい様にする

togetter.com

シミュレーションコンペで強化学習を始める時のTips

はじめに

この記事はKaggle Advent Calender 2021の17日目の記事です。この記事はKaggleで開催されるシミュレーションコンペに、強化学習アプローチで取り組もうと思った時に役立つ情報をまとめたものです。強化学習に初めて取り組む方を基本的には想定しており内容もそちらに合わせています。

初めに自己紹介させていただくと、私はkutoというアカウントでKaggleに取り組んでおり、今年Kaggle Masterになることができました。過去に２つのシミュレーションコンペに参加し強化学習アプローチで取り組みました。過去のコンペ参加の振り返りは以下に書いてますので興味があればご覧ください。 kutohonn.hatenablog.com kutohonn.hatenablog.com

これらの経験を通して得た強化学習の知見を共有できればと思います。なおここでいうシミュレーションコンペとはゲームAIコンペを想定しており、ヒューリスティック・最適化要素の強いコンペ(ex;サンタコンペ)はここでは想定していないことをご了承ください。またこの記事では強化学習アルゴリズムの説明などはおこないません。

目次

シミュレーションコンペの基本知識

チュートリアル

シミュレーションコンペにまだ参加されたことがなく、勘所がいまいち分からないという方はまず初めにこちらのnotebookを読まれることをお勧めします。 www.kaggle.com こちらはkaggle days championship finalのワークショップでkaggle Grand Masterのdott氏が講演してくださったものです。ConnectXというシンプルなゲームを題材にルールベース、ゲーム木アルゴリズム、教師あり学習(模倣学習)、そして強化学習というシミュレーションコンペでとりうるアプローチを順序立てて説明してくださっており雰囲気が掴めると思います。

必要となる計算資源

シミュレーションコンペに強化学習で取り組もうと思った時に大きなハードルとなるのがこの点だと思います。 まず前提として、通常の機械学習と比べると強化学習は明示的に教師データを与えて学習するわけでないため学習効率が非常に悪いです。機械学習だと大抵の場合数時間で1つの学習が終わると思うのですが、強化学習の場合は一定の水準まで学習するのにも日単位の時間がかかることが多いです。この問題に対する1つのアプローチとして後述の分散強化学習というものがあるのですが、そのためには特にCPUの数が重要となります。参考までに今年開催されたHungry Geeseコンペで1stだったチームは、1GPUと64CPUで３週間+1GPUと288CPUで4日学習させていたようです。

このように聞くと計算資源のない人が強化学習で勝つのは難しいのではと思われるかもしれません。ただ先日終了したLuxAI Challengeというコンペで1stだったチームは2GPU+8CPUという強化学習では決して十分とは言えない計算資源で素晴らしい成果を残されました。以降のTipsでは計算資源が少ない状態で戦う方法についても説明しようと思います。

評価方法

通常のコンペはコンペごとの評価指標が設定されており、PublicデータとPrivateデータに対する推論結果を規定の指標で評価しスコアを算出します。一方、シミュレーションコンペの場合はコンペごとの評価指標というものはなく、代わりに他の参加者が提出したsubmissionとの対戦結果から評価されます。対戦相手は自分と同等のスコア帯の人とランダムに当たるようになっています。ただし提出してすぐは自分のsubmissionがどれくらいのスコア帯かというのが分かりません。そこでKaggleでは、序盤は対戦相手のスコア帯の幅を大きくとってたくさん対戦させ、徐々に対戦相手のスコア帯の幅を小さく減衰させることで適切なスコアに収束させる仕組みをとっています。 これは妥当な評価方法であるとは思いますが、一方で序盤の対戦結果のスコアへの影響が大きく、同じsubmissionでも順位が+-30程度変動することもあるのでそこには注意が必要です。

submission形式

シミュレーションコンペではagentという関数を持った.pyファイルをsubmissionすることでスコアが評価されます。この提出形式はコンペによって仕様が異なりますが大抵の場合コンペごとにsubmissionのテンプレートが共有されているのでそちらを参考にすれば良いと思います。

# agent.py

def agent(observation, configuration):
    # observation(ゲームの状態)からaction(とる行動)を算出する処理(ex;モデルの推論)
    return action

一例として直近で行われていたLuxAIコンペでは独自の処理を上記のようにagent.pyのagent関数内に記述し、
①ホストが用意したそのほかのスクリプト
②agent.py
③(使う場合は)学習済みモデル
を圧縮ファイルとして提出するという方式でした。

強化学習の概要

ここでは用語の説明も兼ねて強化学習の基本的な概要について多くの方がイメージしやすいサッカーゲームを例にして説明したいと思います。

環境(Environment)

環境とはゲームルールなども含むゲームエンジンのようなもので、 この環境から現在のゲーム状態を受け取って後述するAgentを動かし対戦したり学習させたりします。

エージェント(Agent)

プレイヤーが操作する対象のことです。サッカーゲームではアクティブプレイヤーがこれに該当します。

状態(State)

選手の位置や向き、ボールの位置、速度などのゲームの状態を表すもので、環境から出力されます。 状態の形式は画像であったりベクトルであったりと様々です。この状態をAgentに入力として渡します。ちなみに強化学習ではこの状態の価値を計算することがあります。状態の価値とは現在のゲーム状態がプレイヤーにとってどの程度有利かあるいは不利かを表すものと思ってください。この状態の価値を強化学習では状態価値(State Value)あるいは単に価値(Value)といったりします。

行動(Action)

行動はAgentへの操作のことで右に走る、パスを出すなどが行動に当たります。 強化学習ではこの行動を学習・推論することになります。 Agentが状態を入力として行動を出力し、環境がAgentの行動を入力とするとゲーム状態が遷移して新しい状態が環境から出力される、というサイクルにより対戦が行われます。ちなみにある状態における行動確率を方策(Policy)といったりします。最適なPolicyを得るのが強化学習の目的でもあります。

報酬(Reward)

機械学習でいう目的関数に該当するもので、最大化したいものを自分で設定します。 報酬として考えられる例を以下に示します。

報酬	説明
勝敗	勝ったら+1, 負けたら-1
得点	１点入れたら+1, 取られたら-1
ゴールまでの距離	相手ゴールに10m近づくたびに+0.1

報酬に関しては次の項目でもう少し詳しく触れようと思います。 　　

強化学習に取り組む際のTips

ここでは強化学習に取り組む際に最初にすべきことや工夫の余地がある点をまとめています。

1. 模倣学習(Imitation Learning)

シミュレーションコンペのアプローチとして模倣学習というものがあります。 模倣学習とは名前の通り行動を模倣するように学習する教師あり学習です。 シミュレーションコンペでは参加者が提出したAgentの対戦ログがMeta Kaggleに格納されるようになっています。 ここから上位チームの対戦ログを取得し、状態を特徴量、行動を正解ラベルとして教師あり学習をすることで上位チームの方策を模倣することができます。もちろん完全に模倣することはできないのですがこれだけでも良いAgentが作れるケースが多いです。模倣学習にはGBDTやNNが使われるケースがありますがここではNNによる模倣学習を想定しています。 個人的には強化学習に取り組む前にまず模倣学習に取り組むのが良いと考えています。そのように考える理由は以下の3つです。

• 初手で取り組みやすい 模倣学習は通常の教師あり学習と同じなので、シミュレーションコンペが初めての方にも取り組みやすいアプローチだと思います。また強化学習はKaggle Notebookで実施されることは少ないので共有されているコードが少ない一方、模倣学習はnotebookで完結することもあり過去コンペで有益なnotebookが共有されています。そちらを参考にするとスムーズに取り組むことができると思います。

• 事前学習モデルとして強化学習への転移学習が可能
  強化学習はそこそこ強いAgentを作るのにもかなりの学習コストを要します。一方模倣学習は数時間の学習でそこそこ強いAgentを作ることができるので、模倣学習で学習したネットワークを強化学習モデルに引き継ぎfine-tuningすることで序盤の学習を省略することができます。こうすることにより学習効率の悪い強化学習の欠点を補うことができます。ただしfine-tuning時にうまくAgentの方策を引き継げず弱体化する場合もあるのでその場合は強化学習のハイパーパラメータを調整するor何らかの工夫が必要かもしれません。

• モデル・データの試行錯誤がしやすい 強化学習は学習効率が悪いのでモデルがうまく学習できているかの評価にも時間がかかってしまいます。そのため新しい特徴量やモデルのアーキテクチャを選定するための試行錯誤をするのが難しいです。一方模倣学習は数時間で学習を終えることができるため試行錯誤しやすく、模倣学習で有用な特徴量やアーキテクチャは強化学習でも有用であると考えられます。なので模倣学習で試行錯誤をして、強化学習を実施するというフローをとれるのが模倣学習から取り組む利点だと思います。

関連するリンク

• Simulations Episode Scraper Match Downloader
  Meta Kaggleにある参加者の対戦ログから上位チームのデータを取得する方法についてのnotebookです。 模倣学習や後述する対戦結果のEDAを行う際に有用です。

• Lux AI with Imitation Learning | Kaggle
  Lux AIで共有された模倣学習のnobteookです。非常に綺麗に整理されたコードで模倣学習に取り組む際に参考になると思います。

2. 強化学習フレームワークを使用する

強化学習の実装は結構複雑なので、既存の強化学習フレームワークを使用するのが良いと思います。ただし最新の強化学習アルゴリズムが実装されていない場合もあるのでそれらを利用する際は論文実装を参照する必要がありそうです。 以下で私が知っている範囲で主要なフレームワークを紹介します。

Stable baselines

github.com

• 知名度の高いフレームワーク
• TensorFlow versionとPyTorch versionの両方がある
• 自由度もそれなりにある
• ログをとるのが簡単でwandbなども対応。
• 分散強化学習も可能

HandyRL

github.com

• DeNAが作成した分散強化学習フレームワーク
• 環境クラスを用意し、configファイルを記述することで動かすことができる
• 分散強化学習が簡単に実施可能
• Kaggleでの実績が豊富

PFRL

github.com

• PFNが作成したPyTorch用の強化学習フレームワーク
• 主要なアルゴリズムが用意されており拡張性もある
• マインクラフトの強化学習コンペでベースラインとして使用されている(参考)

RLLib(Ray)

github.com

• PyTorch, Tensorflowに対応
• 分散強化学習, Multi-Agent, 模倣学習など多様な機能
• configファイルを用意して動かす

3. 分散強化学習を行う

Agentを強くするためには対戦数が重要なので分散環境で並列に学習ができる分散強化学習を採用するのが良いと思います。強化学習の有名なアルゴリズムとしてDQN(Deep Q Network)がありますが、通常のDQNは分散学習ができないので分散学習に対応したものを使うことで学習効率を上げることができます。過去の上位解法(Football2nd, HungryGeese1st, LuxAI1st)を見るとIMPALAという分散強化学習手法を利用しているケースをよく見かけるためこちらを初手で考えてみるのも良いと思います。 ただし分散強化学習はCPU数が多いほど効果を発揮するのでKaggle環境やColab環境で行う際は注意が必要です。

4. 報酬設計

報酬設計は強化学習において非常に重要なポイントです。
先ほどのサッカーゲームを例に説明します。 報酬は通常勝敗などのシンプルなものが良いとされています。 ただし勝敗を報酬とするとまだ何も学習していないAgentはゴールまでたどり着くことが難しく、学習初期は報酬を得ることができず学習が進まないことが考えられます。そのような時に補助的な形で「ボールと相手ゴールまでの距離」などを報酬として追加してやることでボールを相手ゴールに近づければ良いことを学習することができます。ただし「ボールと相手ゴールまでの距離」のようにゲームの目的とは異なる報酬はAgentにとって欲しい行動を誘発するのに重要ですが、Agentの学習が進んでいくとノイズとなり学習を阻害することがあります。この例で言うと本来はゴールをすることが目的なのに遠い位置からボールをとりあえず相手ゴールの向かった大きく蹴ったり、パスをせずにゴールに向かってずっと走ったりなどです。

こういったことからAgentが弱い段階では補助的に即時報酬を与え、そこそこ強いAgentができたらシンプルな報酬に切り替えるというのが1つの報酬の戦略と言えそうです。また学習を安定させるために報酬をclipingするケースもあります。reward clipingで調べると関連する情報が見つかると思います。

5. 学習する行動を工夫

Agentが取ることのできる行動は通常ゲーム環境で予め設定されています。ただし戦略上あまり必要のない行動であれば省略したり、行動空間を階層化することで学習効率を高めることができます。例えば過去にFootballコンペの6位解法では17個あるAgentの行動のうち、8方向の移動行動(4方向と斜め４方向)を1つの移動行動として扱い、移動行動が選ばれたら次にどの方向かを決定するという行動空間を階層化させるアプローチをとっていました。逆に行動を細分化するアプローチも考えられます。LuxAIコンペの1位解法ではTransfer Actionという元から与えられている1つの行動を扱う資源の種類(3種類)や方角(4方向)で細分化し3×4=12個の行動として扱うようにしていました。 このようにAgentが学習する行動をどのように扱うかというのも工夫する点となります。

関連するリンク

• A way to boost your learning
  LuxAIで使われていた移動行動を学習させるための工夫に関するdiscussionです。 移動行動を1つの行動にまとめて学習するというもので模倣学習、強化学習で使えるようです。ゲームAIコンペの場合離散的な移動行動を扱う場合が多いのでこの手法はこれから出てくるシミュレーションコンペでも使えるかもしれません。

6. モデルのアーキテクチャを工夫

ここは基本的に機械学習と同じと考えていただいて構いません。ただし強化学習でpretrained modelや大規模モデルを使うケースは私が知る範囲ではほとんどなくResNetベースのモデルがよく使われている印象です。

7. 入力特徴量を工夫

こちらも基本的に機械学習と同じと考えていただいて構いません。 ゲーム状態を十分に表現できる形式であれば良いと思います。 基本的にはNNで特徴抽出するので凝った特徴量を作る必要はないと思いますが、過去コンペでは特徴量エンジニアリングにより学習効率をあげてスコアが伸びた事例もあるようです。 また強化学習にはstackという過去の状態を現在の状態に重ねてそれをモデルに入力する手法も存在しています。(DQNの論文とかに使われています。)

8. ハイパーパラメータのチューニング

強化学習は学習が不安定であるためタスクに応じてアルゴリズムのパラメータチューニングが必要なケースがあります。上位チームはモデルの挙動を考え、適切なパラメータになるように実験してチューニングしている印象です。とはいえパラメータのチューニングは強化学習アルゴリズムの知識が必要となるため、初心者がいきなりここに取り組むのは難しいと思います。なのでデフォルト値でとりあえずは試してみて、どうしても学習がうまくいっていない様子であればチューニングするというのが1つの手だと思います。

関連するリンク

• PPO Hyperparameters and Ranges. Proximal Policy Optimization (PPO) is… | by AurelianTactics | aureliantactics | Medium
• PPO/best-practices-ppo.md at master · EmbersArc/PPO · GitHub

強化学習アルゴリズムの一つであるPPO(Proximal Policy Optimization)のハイパーパラメータをチューニングする際のエッセンスがまとめられた記事です。

9. 対戦回数を増やす

強化学習は対戦型ゲームAIの場合対戦を行うことで良い方策をAgentが学んでいきます。強化学習は学習のパラメータが正しく設定されている場合は対戦を多く積み重ねることがAgentの性能向上に直結します。 対戦回数を増やすには以下のような方法があります。

• 計算資源を用意し分散環境で並列に対戦させる
• 対戦相手の推論を高速化させる
• 検証用の対戦の頻度・回数を減らす

1つ目は前述のように分散強化学習を使う方法です。
2つ目は学習に必要なデータを生成するための対戦時に、対戦相手の推論速度が学習速度のボトルネックとなるケースがあるので、そのような時は例えば対戦相手がPyTorchやTensorflowなどの深層学習ライブラリを使用したものであればjitやonnxruntimeを使用して推論を高速化させることで時間当たりの対戦回数を増やすことができます。
3つ目については強化学習の場合、学習のための対戦とは別に現在のモデルがどの程度育ったかを評価するために評価用の環境で特定の対戦相手と戦わせます。(機械学習で言うところのvalidationに該当)この対戦の勝率などをチェックして学習がうまくいっているかなどをチェックするのですがこの対戦自体は学習には利用されずあくまで評価用であるためこの頻度を少なくする、または1回当たりの対戦回数を減らすことで学習にリソースを割くというものです。ただし評価のための対戦もモデルが正しく学習されているかのモニタリングのためには重要なのでここは自分の状況を見て判断するのが良いと思います。

10. 対戦相手の調整

強化学習では対戦相手を誰にするかも重要です。 単一のAgentを対戦相手として学習するとその相手にだけ過学習してしまい多様なAgentと対戦するLBではスコアが伸びなくなってしまうため、複数の多様なAgentを用意する必要があります。 以下のような対戦相手を用意して複数の敵と対戦することで汎用的に強いAgentを作ることができるようになります。

• 公開notebookのAgent
• ゲームエンジンに用意されているAgent(ない場合もある)
• 自分と同じAgent(自己対戦, self-playと呼ばれる)
• 過去の自分のAgent

self-playは過去コンペの上位解法でもよく使われており、同じレベル帯の相手と対戦でき、現状の自分より強くなるポテンシャルを持っているので 有用な場合が多いです。ただしself-playの場合、自分と敵が同じ戦略のため方策の更新がサイクルしてしまい学習が進まないケースもあるようです。その場合はハイパーパラメータや学習方法を見直す必要もありそうです。

11. ログをとる

強化学習は機械学習と比べて学習が不安定なため複数の評価指標をモニタリングすると改善策が取りやすいです。 一番わかりやすい指標として対戦時の報酬や勝率がありこれらをモニタリングすることでAgentの学習が順調に進んでいるかを確認することができます。またそのほかにも学習時のLossや状態価値などモニタリングすべき指標は複数存在しており、それらを観察することで現状の学習方法の問題点などを見つけることにつながります。これらの指標はフレームワークであらかじめ記録されるものもあればそうでないものもあるので適宜自身で実装する必要があります。
(指標のモニタリングの一例)

12. 対戦結果のEDA&対戦の様子を見る

これは強化学習に限った話ではなくシミュレーションコンペで重要な点だと思います。 他のコンペと違い、シミュレーションコンペでは提出後に対戦というアウトプットがあるのでその結果を注意深く観察することで、上位チームがどういう戦略をとっているかを理解することにつながると思います。 対戦の様子はLBの右側にある再生ボタンを押すと対象チームのBest ScoreのAgentの過去の対戦結果を動画で見ることができます。

またそれ以外の対戦結果はKaggle DatasetのMeta Kaggleに全参加者の対戦ログがjson形式で格納されているのでそのデータを取得しEDAをすることで上位チームや自分のAgentの分析が可能です。

13. モンテカルロ木探索(MCTS)

モンテカルロ木探索とは効率的にゲーム状態を探索して有効な手を決定する探索アルゴリズムです。 Alpha Zeroで使われていることで有名でKaggleでもHungry GeeseやLuxAIの上位解法で利用されています。モンテカルロ木探索は模倣学習や強化学習の出力と組み合わせて使用されるケースが多い印象です。

関連するリンク
- 10th Place Solution
Hungry Geese10位のsazumaさんのnotebookです。模倣学習とモンテカルロ木探索(MCTS)によるアプローチがとても綺麗なコードでまとまっている貴重なnotebookだと思います。 - 8th place solution: Deep Neural Networks & Tree Search Lux AI 8位のsaitoさんの解法です。MCTSをC++で実装し探索の高速化を図ったことで探索数を増やすことができスコアを伸ばすことができたようです。

おわりに

Kaggleで強化学習に取り組む際に役立つ情報をまとめてみました。私は2度シミュレーションコンペに参加していますがシミュレーションコンペ、そして強化学習はとても面白いです！ なかなかとっつきづらい領域ではありますがこの記事がシミュレーションコンペや強化学習に関心を持つきっかけになると嬉しいです。 読んでいただきありがとうございました。

LuxAIコンペの振り返り

はじめに

12/6に終了したLuxAI Challengeコンペの振り返り記事です。 最終結果は12/21に出る予定で現在の順位は37位です。 この記事ではコンペの概要と私の取り組みをまとめたいと思います。

Lux AI | Kaggle

ゲームの概要

LuxはゲームAIコンペティション用に立ち上げられたオリジナルゲームです。公式サイトは以下で、複雑な戦略性と魅力的なデザインが特徴のゲームでした。今回のkaggleでのコンペがLux AI Challenge Season1という立ち位置であるため今後もkaggle上で行われる可能性がありそうです。 www.lux-ai.org

ルール

ゲームルールはかなり複雑なのですが要約するとポイントは以下の３つです。

1. プレイヤーはマップ上のUnitやCitytileを操作して資源を集めたり新たなUnit, Citytileを生み出す
2. 昼と夜のターンが今後に現れ、夜のターンに十分な資源を持っていないUnitやCityは消滅する
3. 最後に残っているCitytile数が大きいチームが勝ち

実際にプレイしている様子はこちらなどで確認できます。
https://www.kaggle.com/c/lux-ai-2021/leaderboard?dialog=episodes-episode-34126914

行動対象

前述したようにこのゲームではUnitとCitytileと呼ばれるものを行動させてゲームを進めていきます。

Unit

Unitがメインで操作する対象になります。資源の近くに移動することで資源を獲得したりこのゲームの目的であるCitytileを建設したりします。デザインがかわいいですね。

Action	説明
Center Move	現在の位置に止まる(何もしない)
North Move	北へ動く
West Move	西へ動く
South Move	南へ動く
East Move	東へ動く
Build City	Cityを建設する
Transfer	保有資源を隣のUnitへ渡す
Pillage	セルを壊す

TransferやPillageは利用するとより多様な戦略をとることができますが今回説明する内容の中ではあまり出てこないので無視していただいても構いません。またUnitにはCart(荷車)という種類もあるのですがこちらも同じ理由でこの記事では説明は省略します。

Citytile

Citytileの行動はUnitの数を増やしたり上位資源を獲得するためのポイントを貯めたりで、行動の選択肢は少なめです。

Action	説明
Build Unit	Unitを１体生み出す
Research	上位資源を採取するために必要な研究ポイントを貯める

補足するとマップ上に存在する資源にはwood, coal, uraniumの3種類があります。 uraniumなどの上位資源の方がを採取した時の利益が多いが、それらを採取するためにはresearch pointを貯める必要があるため、そのResearch ActionをCitytileが担っています。

資源	資源名	資源名
	wood	初めから採取可能
	coal	research point > 50で採取可能。woodより資源効率が良い。
	uranium	research point > 200で採取可能。coalより資源効率が良い。

このコンペの難しいところ

①複雑なルール
ここまで情報をかなり絞ってルールついて説明してきましたがそれでもルールが複雑であることがわかると思います。 このゲームを複雑にしている要因として以下のようなポイントがあります。

• cooldownの概念
  

UnitやCitytileは毎ターン行動ができるわけではなく行動後はcooldownのためにしばらく何もできないターンが存在します。 これによりどの行動をどのタイミングでするかというところに戦略性が生まれてきます。また行動可能な時にあえて何もしない選択を取り行動を温存するという戦略も考えられます。

• 夜の概念
  

前述の通り、このゲームでは昼と夜のターンが交互に現れ、夜のターンになると資源を十分に持っていないUnitやCitytileは消えてしまいます。 これを避けるためにマップ上の資源を相手のチームよりも効率的に採取することが重要となります。ただし資源効率の良いcoalやuraniumを採取するためにはResearch Actionをしないと採取自体が不可能であるため、Unit, Citytileを増やし資源を採取することとResearchのバランスをうまく取る必要があります。よく取られていた戦略として、序盤は消滅するのを前提に大量にUnitやCitytileを生み出してResearchを行うことで上位資源を早いターンで採取できるようにする戦略が多かった印象です。

②マルチエージェント
こちらがこのコンペを複雑にしている大きな要因だと思います。このコンペはターンによって操作するUnit・Citytileの数が大きく変動します。初めのターンではUnitは1体しかいませんが、ゲーム中盤になると多い時では50体ものUnitを操作する必要がありました。このように行動対象が複数かつ可変であることで以下のような点が課題となりました。

• 探索空間が膨大
  強化学習や探索系のアルゴリズム(ex; モンテカルロ木探索)を行う際にはゲーム状態の探索を行う必要がありますが、Unit・Citytileが複数存在しそれぞれの行動によってゲームの状況は変化するので探索空間が非常に大きくなってしまいます。

• 推論時間がかかる
  このコンペでは模倣学習(教師あり学習)や強化学習などのモデルによる推論によって行動を決定するアプローチをとっていた方が多いと思うのですが、自チームのUnit・Citytileの行動を全て１つずつ推論するとそれだけ推論に時間を要してしまいます。

• 自チームの協力行動
  複数のUnit・Citytileを一度に操作できるということは、Unit同士が協力して行動することでより良い戦略が生まれそうです。そのためには自チームの他のUnitがどう動くのかというところも含めて戦略を立てる必要があり、これが重要な点であったのではないかと考えています。

取り組み

私はこのコンペで強化学習アプローチをとることを参加前から決めていました。理由は以下の3つです。
①これまでkaggleで行われたゲームAIコンペの多くで強化学習が上位解法となっている
②昨年度参加したfootballコンペで学んだ強化学習の知見を活かしたい
③技術的に面白い

前回参加したfootballコンペでは以下の学びを得ました。

• 強化学習は学習効率が悪くまともなagentを作るのに多大な時間&コストを要する
• 過学習を避けるために複数の敵と対戦させる必要がある　　
• 報酬は極力シンプルに

特に１つ目の学習コストが高いという点はかなりネックな部分で、それなりに複雑なゲームで強化学習を用いて一からagentを作ろうとすると、数十~数百のcpuを用意して数十時間~数日対戦させる必要があります。そうなるとコストが高いだけでなく、試行錯誤も容易ではないことから一から強化学習を行うのは厳しいと判断しました。そこで以下の方針を取りました。

• 模倣学習でそれなりに良いAgentの行動を学習しそれをpretrained modelとして強化学習を実施する
• うまく学習が進む特徴量やモデルのアーキテクチャを模倣学習で試行錯誤する

模倣学習とはエキスパートのゲームログ(今回の場合kaggle上での各チームの対戦ログ)を用いてその行動を模倣する教師あり学習のことです。模倣学習も過去コンペで用いられる有効なアプローチであったためこれを使ってそれなりに良い行動方策を事前学習した後に強化学習を行うことで学習コストを大幅に下げることができると考えました。また模倣学習で学習がうまくいく特徴量やモデルアーキテクチャはそのまま強化学習でも有用だと考え、模倣学習時にこれらの試行錯誤を行うようにしました。

模倣学習の取り組み

模倣学習ではコンペ序盤にsazumaさんという方が模倣学習のnotebookを公開してくれました。

この手法は行動が比較的シンプルに決定できるCItytileの方はルールベースで決定し、Unitの方はゲームの状態と対象Unitの状態を19chのマップとして特徴量化し、特に重要な行動である４方向のMove行動とBuild City行動に絞って模倣学習を行うというものでした。この手法は非常によく働いており公開当初は銀圏の上位に食い込むほどのものでした。そこで私もこのモデルをベースに模倣学習を実施していました。

しかしこの手法には課題もありました。１つは学習・推論の時間がかかるという点です。このモデルではインプットに行動を決定したい対象のユニットの状態を表すチャネルを特徴量として与え、アウトプットとして対象ユニットの行動を返すように分類モデルを作成しているため、Unitの数だけ学習・推論を行う必要がありました。またUnitを独立して扱っているので協働した行動の学習が難しいというのも考えられます。

上記のような課題を解決する方法としてコンペ終了の１ヶ月ほど前にnosoundによるUNetを用いた模倣学習アプローチががdiscussionで共有されました。

このアプローチは元々Unit単位で行なっていた模倣学習をUNetを用いたセグメンテーションタスクのような形で解くことでMap単位で全てのUnitをまとめて学習・推論を行えるという非常に画期的なものでした。コードは公開されなかったもののdisucssionやコメントで丁寧に情報共有されていたことから私もこのアプローチに切り替えることにしました。 また共有されている情報や過去コンペの会報なども参考にし、UNetモデルに以下の工夫を加えました。

• データサンプリング
  ゲームの説明で述べたようにこのゲームではcooldownという概念があり、行動後はしばらく行動できないターンが存在するため、「何も行動しない」という選択を学習することも重要でした。この何もしない行動はUnitのCenter Actionに該当するのですが、Center Actionは対戦ログには明示的に記録されていないケースが多かったため、ラベルを自分で作成する必要がありました。またラベルを自分で作成してもそのまま学習しようとするとCenter Actionのサンプルサイズは他のラベルの3-10倍以上あり、データが不均衡になるという問題がありました。そこでCenter Actionを他のラベルのサンプルサイズの平均値と同じになるようにアンダーサンプリングすることで対処しました。 もう一つターンごとに行動させるUnitの数に偏りがあり、それも問題になる可能性があったためターンごとのデータ数の偏りを減らすために、各ターン最大4つのUnitの行動のみを学習するようにサンプリングを行いました。

• 移動行動の階層化
  こちらはUNetの情報を公開してくれたnosoundが共有してくれたTipsで、 上記の模倣学習で扱っているような特徴量マップとモデルの場合、4つのMove Actionを1つのMove Actionとして階層的に計算することができるというものです。 特徴量マップを90度回転させればNorth ActionはWest Actionとみなすことができることを利用し、 推論対象が元々Center Action, 4 Move Action, Build City Actionの6つであった場合、4Move Actionの代わりにNorth Actionのみを定義し、モデルに入力する特徴量マップを90度ずつ4回、回転させて4つのbatchとして入力しoutputを算出します。こうすると3ch × 4 のoutputが取得でき、4つのCenter Actionと4つのBuild Actionはoutputの平均をとることで、最終的に本来欲しかった6つの行動のoutputが取得できるというものです。 このTipsは非常に効果的で50くらいのスコアアップを達成できました。実装がやや面倒ではありますが離散的な移動行動を持つ他のシミュレーションコンペでも有用なアプローチだと思います。

• TTA
  Hangry Geeseの4th place solutionではTTAとしてflip系を追加することでロバスト性を高めスコアが向上したという説明があったことから追加しました。スコアの向上はあまり確認されなかったのですが、マイナスの影響は少ないと判断しとりあえず追加しておくことにしました。

以上が模倣学習の私の取り組みです。この模倣学習モデルをもとに強化学習に取り組みました。が最終的なベストAgentは上記の模倣学習アプローチとなりました。

強化学習の取り組み

前述のように模倣学習モデルを事前学習モデルとして扱い、強化学習を実施しました。 強化学習のフレームワークであるStable baslines3を今回は使用し、アルゴリズムにはPPOを選択しました。 使用した計算資源は手元のローカルマシンです。(GPU: RTX3080×1, メモリ64GB,cpu数＝24) 本来強化学習で強いAgentを作ろうとするとこのようなスペックでは特にcpuが不足なのですが、模倣学習である程度事前学習を行なっているのでこのスペックでも十分に戦えるのではと考えました。 主な取り組みは以下です。

• ハイパラチューニング
  模倣学習を事前学習モデルとして強化学習を行うとこれまでの行動を忘れたかのように急激に弱くなる現象が起きました。 そこで方策が大きく変更されないようにこちらで紹介しているPostを参考に、PPOのハイパラを変更しました。これにより序盤で行動がおかしくなる現象に対処しました。これはシンプルなモデルではよく働いたのですがUNetモデルで強化学習をするとハイパラを調整しても学習がうまくいかない現象が起きました。この原因はよくわかっていません。 brown: デフォルトパラメータ(bad)
  red: clip_range=0.1 / targe_kl=0.003(good)

• 複数の対戦相手の作成
  過去の強化学習コンペから単一の対戦相手だと過学習することがわかっていたので、複数の上位チームのデータによる模倣学習Agentとself-play(自己対戦)を以下の配分で学習することにしました。

割合	対戦相手
0.25	self-play (現在のモデル)
0.15	self-play (過去のモデルからランダムサンプリング)
0.2	1stチームの模倣学習v1 (LB score is 1550)
0.2	1stチームの模倣学習v2 (LB score is 1450)
0.2	2ndチームの模倣学習 (LB score is 1450)

• 推論の高速化
  前回の強化学習コンペから対戦回数を増やすことが強いAgentを作るために大事だと考えました。対戦相手として模倣学習やself-playのAgentを使っていたのですが、通常のpytorchモデルだと推論に時間がかかり時間あたりの対戦回数が少ない問題がありました。そこで今回はonnxruntimeを使用して対戦相手の推論を高速化しました。

• 学習するパラメータの制限
  事前学習モデルである程度モデルの学習ができていることから全てのパラメータを学習するのは非効率だと考え、policy network(模倣学習で学習したnetwork)の最終層とvalue network(状態価値を評価するnetwork)のみを学習するようにしました。

• シンプルな報酬設計
  報酬は今回の目的である最終的に残ったCitytile数を報酬とする方法と勝敗を報酬とする方法を軸に実験を行いました。 この方法の場合ゲームが終了するまで報酬を得ることができないので各ターンごとに得ることのできる即時報酬(例えば現在のターンのCitytile数)を用いることもできるのですが、即時報酬はAgentの行動を誘導する補助的なものであり、ある程度強くなったAgentには逆にノイズになる可能性もありました。今回の場合は模倣学習である程度良い方策がすでに得られていたので補助的な即時報酬は不要と考え上記のようなシンプルな報酬を使用することにしました。

上記のような取り組みを行ったのですが、最終的には強化学習を適用していない模倣学習モデルがベストAgentとなりました。強化学習にはかなり時間をかけて取り組んだのでこの結果はとても悔しかったです。

感想

強化学習自体は最終的にはうまくいかなかったのですが、時間をかけて取り組むことで強化学習に対する理解はかなり深まったと思います。 今度面白そうなゲームAIのコンペが来たらまた参加したいと思います。

私の解法

www.kaggle.com

outdoorコンペ振り返り

はじめに

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

この記事ではコンペの概要と私たちの取り組み、そして重要であった点について書いてみようと思います。 またこのコンペは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が共有されていました。

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

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

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

相対位置推定

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

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

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

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

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 この情報を使って例えば推定位置が特定の道路種(例えばresidential;住居道路)に属している場合はSnap2Gridを適用するというのを複数のパターンで試しました。良いアイデアかなと思ったのですがCVはなかなか上がらず断念しました。

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

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

実際に定義された推定困難エリアがこちらのようなものです。 多くは橋や高速道路のインターチェンジが対応していました。この箇所に対して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

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に昇格できました。 特にCompetition Masterは目標の一つであったのでとても嬉しかったです。DiscussionやNotebookに関しても毎コンペ少しずつ取り組むようにしていて、情報共有することによるメリットも個人的には感じているのでこれからも引き続き取り組んでいきたいと思います。 長ったらしい文章になってしまいましたが読んでいただきありがとうございました。

解法

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

18th place solution

www.kaggle.com

speakerdeck.com

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

鳥蛙コンペの振り返り

はじめに

2020年の12月から2月にかけてkaggleでRainforest Connection Species Audio Detectionというコンペが開催されており、最終的に5位を取ることができました。この記事ではコンペの概要や取り組みを記録しておこうと思います。

コンペとタスク

コンペ概要

今回のコンペは熱帯雨林で録音された音声から24種の匿名の鳴き声を検出・分類するというものでした。データはtrain/testともに音声ファイル(60s)１つにつき、複数種の鳴き声が存在するためmultilabelで学習・予測を行う必要がありました。

音声認識について

今回のタスクに似たコンペとしてDCASEという環境音認識のコンペがあり、こちらに音声認識の概要がわかりやすく書かれています。 engineering.linecorp.com

評価指標

今回の評価指標はLRAPという予測値のrankingに基づく指標にクラスごとのラベル数で重み付けされたLWLRAPが使用されていました。こちらは2019年に開催されたFreesound Audio Tagging 2019でも使用されており音声認識のタスクで使われる指標のようです。

評価指標の説明に関してはこちらのdiscussionがとても参考になりました。

鳥コンペとの違い

似たようなコンペとして2020年8~9月にkaggleでCornel Birdcall Identification(通称: 鳥コンペ)が行われていました。こちらも鳥の鳴き声を分類するタスクで今回紹介する鳥蛙コンペと非常に似た趣旨のコンペでした。 鳥コンペと異なる点としては以下のような項目が挙げられます。

	鳥コンペ	今回
評価指標	micro averaged F1 score	LWLRAP
ラベル付け	weak label	strong label
クラス数	264	24
クラス名	あり	なし(匿名)
予測	5s単位で予測	60s単位で予測
その他	nocall(鳥が鳴いていないこと)の予測が必要	FPデータあり(後述)

補足するとweak labelとは音声ファイル単位でラベルが付けられているもので、strong labelとは音声内のどこで鳴いているかという時間情報も加わったより詳細なラベルとなります。

課題(本コンペの特徴)

今回のコンペで個人的に重要なポイントと考えたのは以下の３点です。

1. train/testでアノテーション方法が異なる

本コンペではtrainとtestでアノテーション方法が異なることが知らされていました。 アノテーション方法について整理したdiscussionでまとめられていたのが以下の図です。

trainデータはrudimentary detection algorithumによって検知された音声の箇所を専門家によって正例か負例かに分類することでtrainデータのアノテーションを行っている一方で、testデータはアルゴリズムを介さずに専門家が音声とスペクトログラム画像を確認することでアノテーションがされています。この違いによりtrain/testでラベルの分布が大きく異なる可能性が考えられました。

2. missing labelが多い

課題１に関連して、こちらのdiscussionで紹介されているように今回のtrainデータには鳴き声があるがラベルがついていない, missing labelが存在していました。 下の図で赤色で示しているのが与えられているラベルですが、モデルで予測すると、青色で示すようにラベルがついているところ以外でも実際は鳴き声があることがわかります。(図は上記discussionより引用)

上記のように同じ種のラベルが欠損しているのであればそこまで問題ではありませんが、鳴いているのにラベル付けされていないクラスがある場合、学習に支障をきたすことが考えられます。 実際、trainデータのラベルを確認すると1132件の音声のうち複数の種のラベルが1つの音声についていたのはわずか27件のみでした。

コンペ終盤に出たdiscussionによるとtestデータは1つの音声に平均して4~5種の鳴き声が含まれているという示唆があったことから、trainデータはtestデータに比べて圧倒的にラベルの数が少ないことが課題であり、これに対処する必要がありました。

3. FPデータの扱い

今回は通常のラベルに加えてFalse Positive(FP)ラベルも与えられていました。これはどういうラベルなのかというと、課題1で説明したアルゴリズムによって鳴いている(Positive)と判定された種のうち、専門家によって「判定が正しい(Positive)」と判定されたものをTrue Positive(TP)データ、「判定が正しくない(False)」と判定されたものをFalse Positive(FP)データとして与えられていました。 TPデータはそのままラベルとして使うことができますが、FPデータは「種Aは鳴いていない」という情報しかないためそのまま使うのは難しいものでした。ただTPデータの音声は約1000件でFPデータの音声は約3000件あったのでFPデータをどのように使うかというのが一つのポイントであったと考えています。

解法

上記の課題を踏まえて私たちのアプローチを紹介しようと思います。 最も重要だと考えるポイントは以下の３つです。

• 3stageによる学習
• 訓練データに対するpseudo labelingによりmissing labelを補完
• custom lossにより曖昧なラベルはlossを計算しないようにする

今回のコンペでは後述するpseudo labelingとcustom lossによるoverfitを防ぐために3 stageで学習を行いました。以下私のモデルを例に説明していきます。

stage1

CV:0.81 LB:0.84

• EfficientNet-b2
• SED model (clipwiseでloss計算と予測を行う)
• 5fold StratifiedKFold
• 30 epoch
• LSEP Loss
• TPデータのみ使用
• 画像サイズ(height,width)=(244, 400)
• batchsize 16
• Adam
• learning_rate=1e-3
• CosineAnnealingLR(max_T=10)
• augmentationなし
• 10s単位で学習・予測

stage1では鳥コンペや本コンペで有効とされていたSound Event Detection(SED)モデルを使用しました。SEDについては鳥コンペのnotebookや本コンペのdiscussionがとても参考になります。

stage1では特別なことは行っていませんが１点だけ。多くの参加者がBCELossとFocalLossを用いていましたがここではLSEPLossを使用しました。 LSEP LossはFreesoundコンペの3rd solutionでも使用されていた損失関数で、今回のコンペのようなrankingに基づく評価指標の場合、BCELoss のような分類用の損失関数よりもより良い精度が出ると上記discussionで説明されていました。実際に使用したところBCELossと比べてLB scoreが0.01とかなりアップしました。

stage1の目的は後のstage2,3で使うpretrained modelを作ることです。コンペ前半はstage1のモデルを強化することに取り組んでいましたがなかなかスコアが伸びませんでした。

stage2

CV: 0.734 LB:0.896

• stage1とほとんど同じ構成
• stage1のモデルをpretrained modelとして使用
• 5 epoch
• FPデータをTPデータと同じ数だけsamplingして学習に使用
• FocalLossベースのカスタム損失関数

stage2の目的は２つあります。1つはstage1のmodelに追加学習する形で精度を向上させること、もう1つは精度が向上したstage2のモデルを利用してTP・FPデータに対して予測を行い、pseudo label(擬似ラベル)を作成することです。精度を向上させるためにstage2ではFPデータの追加とcustom lossを導入を行いました。この追加学習によりLB scoreが＋0.05とかなり向上しました。

custom lossについて

本コンペの課題としてmissing labelがありました。missing labelがあるということはTPデータで0(負例)としてラベル付けされているクラスの中にも実際は1(正例)のクラスが含まれているということです。そこでラベルを以下の３つに分けることにしました。

1: TPラベル(鳴いている)
0: 曖昧なラベル(正例が混じっているかもしれない)
-1: FPラベル(鳴いていない)

例)
label = [0, 0, 1, 0,...., -1, -1]

この３つのラベルのうち0ラベルは曖昧なラベルとして扱い、loss計算時に省くようにlossを設計しました。 FPデータは間違われやすいけど専門家によって鳴いていないと判定された非常に有益な情報なのでそれを0ラベルと違うことがわかるよう-1としてラベル付けし、loss計算の時には0(鳴いていないもの)として計算しています。このようにFPデータを扱うことで本コンペの課題の１つであるFPデータの利用に対処しました。

これにより明確にラベル付けされているところだけ学習され、曖昧な箇所は学習されないようになりスコアの向上に寄与しました。ちなみにこの損失関数でstage1のように1から学習することも試しましたが学習効率が悪く、スコアも低下したことからstageを分けて5 epochだけ追加学習するアプローチを取りました。

実装は以下です。stage1で使ったLSEPLossは以下のような実装が困難だったのでFocalLossをベースにカスタムしました。BCELossよりFocalLossの方が効いたのでFocalLossを採用しました。

class FocalLoss(nn.Module):
    def __init__(self,  gamma=2.0, alpha=1.0):
        super().__init__()
        self.posi_loss = nn.BCEWithLogitsLoss(reduction='none')
        self.nega_loss = nn.BCEWithLogitsLoss(reduction='none')
        self.zero_loss = nn.BCEWithLogitsLoss(reduction='none')
        self.gamma = gamma
        self.alpha = alpha
        # self.zero_smoothing = 0.45

    def forward(self, input, target):
        # mask
        posi_mask = (target == 1).float()
        nega_mask = (target == -1).float()  # (n_batch, n_class)
        zero_mask = (target == 0).float()  # ambiguous label
      
        posi_y = torch.ones(input.shape).to('cuda')
        nega_y = torch.zeros(input.shape).to('cuda')
        zero_y = torch.full(input.shape, self.zero_smoothing_label).to('cuda')   # use smoothing label

        posi_loss = self.posi_loss(input, posi_y)
        nega_loss = self.nega_loss(input, nega_y)
        zero_loss = self.zero_loss(input, zero_y)
        
        probas = input.sigmoid()
        focal_pw = (1. - probas)**self.gamma
        focal_nw = probas**self.gamma
        posi_loss = (posi_loss * posi_mask * focal_pw).sum()
        nega_loss = (nega_loss * nega_mask).sum()
        zero_loss = (zero_loss * zero_mask).sum()  # stage2ではこれをlossに加えない
        
        return posi_loss, nega_loss, zero_loss

訓練データに対するpseudo labelingについて

上記の方法で学習したstage2モデルを使ってtrainデータ(TP/FP全て)に対して予測を行いpseudo labelを作成しました。目的はtrainデータに欠けているラベル(missing label)を補填するためです。 ラベル付けは以下のように行いました。

threshold = 0.5として
1: 0.5 <= 予測値
0: 予測値 < 0.5

これを新たなラベルとして追加しstage3で使用します。これによりmissing labelに対処しました。 0ラベルには正例のラベルが含まれている可能性もあることからあくまで曖昧なラベルとして扱います。

stage3

CV:0.954 / LB:0.950

• stage2とほとんど同じ構成
• original label+pseudo labelで学習
• stage1のモデルをpretrained modelとして使用
• 5epoch
• FPデータをTPデータと同じ数だけsamplingして学習
• Focallossベースのカスタム損失関数
• last layer mixup (+0.007)
• 曖昧なラベルに対してlabel smoothingをかける(0 -> 0.45としてlossを計算) (+0.009)

stage3が最終的なモデルになります。pseudo labelを新たなラベルとして加えることによって課題の１つであったmissing labelに対処しました。これによりLB scoreが0.04向上しました。またニューラルネットワークの最終層でmixupも有効でした。注意点としてstage2で使っているcustom lossは過学習に陥りやすかったのでstage3ではstage2のモデルではなく、stage1のモデルをpretrained modelとして学習しています。以上がモデルの全体像になります。

CV

今回は課題１で述べたようにtrainとtestでラベルの分布が大きく異なっておりvalidationが難しいコンペだったように思います。 私たちのチームでは以下の５指標を確認しながらサブミットを行っていました。

• pseudo labelありのLWLRAP
• pseudo labelなしのLWLRAP
• Recall
• Precision
• AUC

ただどの指標もLBと相関が十分にとれているとは言えませんでした。なのでPublic/Private LBに大きな差はないという仮定のもと、基本的にはtrust LBでモデルを改善していきました。 shake対策としては多様性の多いモデル(ViT, WaveNet, ResNet18)でpseudo labelと予測のアンサンブルを行いlabel及び予測がロバストになるようにしました。 結果としてはPublic/Privateで大きな差異はなく8th -> 5thにshakeupしてコンペ終了を迎えることができました。CVの良い方法についてはこれからdiscussionを読んで勉強したいと思います。

その他うまくいかなかったこと

• mean-teacher
• Conformer
• testデータに対するpseudo labeling
• 通常のmixup
• noise追加/除去
• TTA
• SAM optimizer

おわりに

今回最終的に初の金メダルを取ることできました。自分より格上の人とチームを組めたことで上位陣の戦い方や考え方を学ぶとてもいい機会になったと思います。一緒にチームを組んでくれた2人にはとても感謝しています。またコンペ序盤から有益な情報を共有してくださったaraiさんやshinmuraさんからも勉強させていただきました。これからはコンペの順位はもちろんのこと、コミニュティへの貢献も意識して取り組んでいきたいと感じたコンペでした。

参考

コンペのGitHubレポジトリはこちらです。 (branchごとに分けてやっていたのでごちゃごちゃしてしまった。) github.com

PyTorch-Lightningでの再現性

はじめに

PyTorchで再現性を持たせたい場合、lightningのseed_everything関数や以下のような自作関数を使うケースが多いと思います。

def set_seed(seed: int = 42):
    random.seed(seed)
    np.random.seed(seed)
    os.environ["PYTHONHASHSEED"] = str(seed)
    torch.manual_seed(seed)
    torch.cuda.manual_seed(seed)
    torch.backends.cudnn.deterministic = True
    torch.backends.cudnn.benchmark = False

以前まではこれでseedを固定できていたのですが、PyTorch-Lightningに切り替えた場合、同じコードを実行してもlossや予測値がブレる現象が起きたのでその原因と対策を記録しておきます。

結論

pytorch_lightning.Trainerクラスの引数でdeterministic=Trueとする。

pytorch_lightning.Trainerはデフォルトではdeterministic=Falseとなっています。 これにより上記関数でtorch.backends.cudnn.deterministic = Trueと設定していてもTrainerによりFalseに上書きされていました。 厳密な再現性を望まない場合は不要な設定かもしれませんが、比較実験を行う場合はこの設定をしておく必要があるかと思います。 pytorch-lightning.readthedocs.io

その他

今回はlightning周りで再現性がとれない現象が起きていましたが、Pytorch側に問題がある場合は公式の以下のリンクをまず確認した方が良さそうです。

pytorch.org