AHC022の振り返り
Atcoder Heurstic Contest022に参加し最終順位は234位/961でした。 この記事ではコンテストの振り返りをして取り組んだことをまとめたいと思います。
問題設定
- L行L列のトーラスなグリッドワールドがある
- グリッドワールド上に出口セルがN個、グリッドワールド外にワームホールがN個存在しそれぞれ1対1で繋がっているが対応関係は不明
- 最初にグリッドワールドの各セルの温度を0-1000の整数で自由に設定できる。ただし隣接するセルの温度差に応じた配置コストが発生する。
- 任意のワームホールからグリッドワールドに移動し気温を観測する行動を最大10000回実施可能。ただし観測によるコストが発生する
- 観測する温度には指定された標準偏差Sのノイズが乗る。また温度は0-1000にクリップされる
- 目的は観測によって得た情報をもとにワームホールと出口セルの対応関係を当てること
問題詳細 atcoder.jp
直感的にはセルを正しく区別できるように温度差をつけてたくさん観測をすれば温度を正しく推定できそうですが そうすると配置コストと観測コストがかかるのでそこを抑えつつうまく推定を行う問題と言えます。
解法概要
解法の要約は以下です。
配置パート
- クリップの影響を受けにくくするためにベース温度を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
標準偏差であるsigmaを標本標準偏差で計算するとスコアが下がったのでこちらは既知である母標準偏差を使用しました。 ただし今考えると標準偏差が大きいケースでは温度クリップの影響を受けて正規分布を仮定できないのでそこはこの方法だとあまり良くなかったかもなと思います。
その他取り組み
異なる距離関数の使用 サンプリングデータのMAEや最適輸送に使用されるwasserstein距離などを分布の近さとしてエッジの重みに使ってみましたがスコアは改善しませんでした。また機械学習におけるアンサンブルの要領でそれぞれの距離関数でマッチングした結果をもとにvotingを行い最も多い候補を採用することも試しましたが特に改善はしませんでした。
MCMCで少数の標本から事後分布を推定
少ない観測で分布をいい感じに推定できればと思いMCMCを使って色々試していましたがスコア改善には繋がりませんでした。streamlitでweb visualizerを作成
手元での検証では100件のデータに対する最終スコア、平均エラー数、平均配置コスト、平均観測コストによって手法の良し悪しを判断していました。ただしスコアだけだとどこが悪いかの判断が難しいことから実行結果の可視化をするweb visualizerをstreamlitで作成しました。この可視化によってどこでミスをしているか、どのくらい誤差があるか、どこで配置コストがかかっているかなどを見ていました。
上位解法
上位解法を聞く中でなるほどなと思った内容をメモとして残しておきます。
