2021年5月30日日曜日

AHC 003 A - Shortest Path Queries

最小二乗法による$H, V$の推定をベースにいろいろやった。辛うじて97%に達した。

M=1

とりあえず、$M=1$のケースしか来ないとして$H, V$を推定することを考える。報告されたパスの長さを$W$として、パスが行$i$を$r_i$回、列$j$を$c_j$回通るとする。このとき、$\sum_{i: 行}r_iH_i + \sum_{j: 列}c_jV_j$と$W$が近くなるように$(H_i), (V_j)$を選びたくて、これは最小二乗法(OLS)が使えそう。得点は正規化されているので$W$で割って、

$$ \Bigl (\frac{1}{W} \bigl(\sum_{i: 行}r(i)H_i + \sum_{j: 列}c(j)V_j \bigr) - 1 \Bigr)^2 $$

の総和を最小化することを目指す。OLSはクエリ数を$Q$、変数の数を$d$として${O}(Qd^2)$でできる。

  • パスの重みなし長さ$l$が大きいと、$\delta, \gamma$の平均の分散（≒誤差の分散）が小さくなっていくはずなので、パスごとの誤差の分散を揃えるために重み付き（式に$\sqrt l$を掛ける）にしてみた。直接のスコアにはほぼ影響しなかったけれど、後述の$M$の判定にかなりよい影響があったので残した。（ただ、そうなる理由がよくわからない。）
  • 特にクエリが少ないうちは多重共線性の問題があるので、OLSの行列の対角成分に微小な定数を足して正則にするやつ（リッジ回帰と呼ばれているもの）をした。
  • 毎回OLSすると遅すぎるし、クエリが一定数を超えるとだいたい収束しているようだったので、クエリを150個処理するまでは毎回OLSし、それ以降は25回に1回にした。
  • OLSは素朴な掃き出し法でやった。疎行列なのでもっと速い方法はあるらしいけれど、後半のOLSの頻度を上げてもほとんど得点に結びつかなかったので、コンテスト中は無視していた。

M=2

$M=2$の場合、$H, V$の値が行、列ごとに2種類あり、境界がわからないのでその推定もする必要がある。境界を決めつければ上と同様のやり方で$H, V$が推定できるので、その際のRMSEをスコアとして境界を探索する焼きなましは考えられる。ただ、素朴にやると1回のOLSが重すぎるという問題がある。そこで、ある一行$i$の境界を移動させたときのRMSEを最小化する問題を局所化して、$H_{i, 0}, H_{i, 1}$だけを推定する二変数の回帰と考えることにする。このOLSは${O}(クエリ数)$でできるので、焼きなましの遷移としては十分に速い。

  • 最初のうちは多項式回帰や3分割、4分割のOLSも試したが、普通にやると収束が遅すぎてうまく扱えなかった。

Mの分類

$M$は与えられていないので推定する必要がある。クエリを150回処理するまでは$M=1$を想定したOLSをして、その時点でのRMSEを見て一定より大きければ$M=2$、とするだけで96%程度の正解率があるようだった。ほかにも相関のある指標はいくつかあったけれど、正解率100%でも総スコアに大きな影響はなかったので追求しなかった。[1]

  • もう少し精密に、10回目、20回目、30回目、...で$M=2$である確率が（例えば）98%以上になったら$M=2$の処理に移行する、みたいな考え方もありそうだったが、そもそも移行を早めても得点が上がらない（$M=2$の入力に対しても、最初はむしろ$M=1$向けのモデルを適用したほうが効率がよい）ようだった。

OLS以降

クエリ数が増えると、個別の辺の重みもある程度は推定できそうと思った。推定した$(H_i), (V_j)$をベースに、RMSEをスコアとして各辺の重みを変更する山登りをすると、$M=1, 2$ともに点が伸びた。

  • 焼きなましで点が伸びなかったので、速度を重視して山登りにした。
  • 素朴にやるとオーバーフィットするので、正則化（各辺の重みの$H, V$との差についてのRMSEも山登りのスコアに足す）を加えたりしたが、十分にコントロールできている気がしない。
  • 通った回数の多い辺上位200個くらいを選んでOLS、も試したが山登りを超えられなかった。

振り返り

  • 統計の知識がなさすぎるので、問題を見たときにけっこう困った。ただ、最初の印象に反して、素朴な回帰と局所探索を調整しているだけでまあまあスコアが伸びていった。
  • Woodburyの恒等式でOLSの差分更新ができるらしい。確かにこういうものを探していた。
  • 通った回数の少ない辺や行・列を少しだけ楽観的に評価したり、（使う行・列は少ないほうが質の高い情報が得られるので）最初のうちは方向転換にペナルティをつけたりするという工夫で点を伸ばしている人がかなりいるようだった。どの情報を得るかという観点を後半になって忘れてしまったのは反省点。
    • 前半のことを思い出すと、通ったことのない行・列を優先して通るようにすると多重共線性の問題が大きくなってむしろスコアが下がってしまうので捨てて、それ以降ほとんど考えなかったんだよな。

  1. 0.03%程度の上昇は見込めたので影響が皆無なわけではなかったが、この辺の知識がなさすぎて後回しにした結果、結局やらなかった。 ↩︎

投稿者