AtCoder Heuristic Contest 003 "Shortest Path Queries"

参加しながら考えたこと試したことの源泉かけ流し。

最終的な方針は まとめ にまとめてあります。

問題概要

https://atcoder.jp/contests/ahc003/tasks/ahc003_a

辺の長さが未知の 30×30 頂点の無向グリッドグラフがあり、そのグラフに対し以下のクエリを 1,000 個処理する。

  • 2 つの頂点 s, t が与えられ、s から t へのパスを出力する。

各クエリを処理した後、フィードバックとしてそのパスの長さに 0.9 ~ 1.1 の乱数をかけ合わせた値が入力として与えられる。1,000 個のパスの長さの和をできるだけ最小化せよ。

各行/各列の辺の長さには相関がある。詳細は問題ページを参照。

1 日目

問題を読む。バンディット問題だ!!!!!!いわしバンディット問題大好き。

バンディッド問題はとりあえず UCB1 使えばいい感じになるんですよ、多分。 フィードバックから各辺の長さを推定しつつ、その辺の今までの試行回数が少ないほど長さを低めに見積もってパスを選ぶみたいな感じかな?

入力生成方法を読む。うーむ、なるほど、各行/各列毎に相関があるんだな。M=2 の場合はどこかで平均値が切り替わると。ひとまず M=2 と仮定した解法を書けば M=1 でもそんなに悪くなることはなさそうだな。

ひとまず次のような解法を試してみる。

  • M=2 と仮定する。
  • 各行/各列の平均値切り替わりポイントは中央 (x=15/y=15) と仮定し、その前後について分布の平均値を推定する。
  • 辺ごとのパタベーション δ, γ の値は 0 とみなす。ここまでパラメータ化すると多分過学習するんじゃないかな。オッカムの剃刀
  • パスを選ぶ際は、
    • s - t の長方形内にまだ試していない行/列があれば、その行/列を通る単純なパスを選ぶ。
    • そうでない場合、分布の平均値から今までの試行回数に依存する exploration 項を引いた値をその辺の長さとし、ダイクストラで最短パスを選ぶ。
      • n={今までにその辺を選んだ回数}、N={全ての辺の n の和}としたとき、explocation項=sqrt(log(N)/n)
    • フィードバックとして与えられる長さは均等に分割し、各行/列の分布の平均値に分配する。分布の平均値は今までに分配された値の平均値とする。

提出すると 92.3G。なるほど、スコア関数の定数なんだろうと思ってたけど、これ満点が 100G 点になるように調整されてるんだな。


よく考えたら、今は与えられたフィードバックの情報は返ってきた直後に分布の平均値に反映して終わりにしてるけど、後々活用することもできそうだ。

パスとそのフィードバック(長さ)の情報の履歴を記憶しておき、今の分布平均値の推定値から計算したそれらのパスの長さ推定値とズレが小さくなるよう、各ターンの終わりに山登りで少しずつ平均値を調整してみる。提出して 94.7G。このあたりで暫定 2 位が取れて喜ぶが、1 位が 95.5G くらい出してるのでまだのんびりする余裕はなさそうだ。

2 日目

パスとフィードバックの履歴と推定値とのズレを見ながらパラメータ調整する際、ズレの値として絶対値を使っていたのだが、この 2 乗の値を最小化するようにしてみたらスコアが伸びた。最小二乗法的なノリなのかな?提出して 95.3G。

3 日目

今は分布の平均値が切り替わるポイントを x=15/y=15 固定にしてるけど、ここに改善の余地がありそう。

山登りで平均値の調整をするフェーズで、ついでにこの境界線を前後させてみて改善したらそれを採用するようにしてみる。提出して 95.9G。


今は M=2 のモデルに基づき色々推定をしてるけど、やはり M=1 のケースはそれに特化したモデルで推定をした方が良いのかもしれない。

そこで、M=2 のモデルから境界線の概念を取り除いた M=1 用モデルも並行して学習するようにし、そちらのモデルの推定値の方がズレが小さい場合途中からそちらに切り替えるようにしてみた。96.0G。

4 日目

かなり伸び悩んできて色々試した(詳細は忘れた…)。最新のフィードバックの値を少し強めに平均値に反映するようにしてみたらスコアが少し伸びた。あとまだあまりやるべきではないがパラメータ調整もやった。96.1G。

5 日目

イデアも無いし、コードがぐっちゃぐちゃで触りにくくなってきたので、全部書き直すことにした。よくあるやつ。あまりちゃんとテストしながら書いているわけではないので、リファクタにより隠れてたバグが取れてスコア改善したりしないかな…。

6 日目

リファクタを進める。

7 日目

リファクタが終わった。多分バグがあったわけではないんだけど、平均値の持ち方を変えたりした影響かなんだかんだで 96.18G くらいになった。

8 日目

今まで分布平均値の推定にあれこれしてたけど、これだけだと限界を感じてきた。

例えば、ダイクストラで最短パスを求める際は分布の平均値を基に計算しているわけだけど、ここでも今まで得たパス+フィードバックの値を直接使うようにしてみたらどうだろう。ダイクストラ中パスの始点に来たときに、その時点の距離にフィードバック値を加えたものをパス終点の距離としキューに突っ込む感じ。お風呂でこれを思いついたときはこれは伸びるぞ…!と期待したが、実際はそこまで伸びず 96.23G。

ちなみにこのときのフィードバック値は等倍で使うとむしろスコアが悪化したため、1.11 倍した値を使用した。多分 0.9 倍で返ってきた値に依存してダメージを受けたんだと思う。

9 日目

もうやることないだろ…と思いつつ、順位表の自分の少し上がかなりスコア密になっていて、あと 0.1G 点伸ばせば順位が 50 位から 10 個くらい上がりそうなので、頑張ってアイデアを振り絞る。

実行時間が 1.8sec くらい余っていてもったいないのでこれを有効活用してあげたいのだが、山登りのイテレーション数を増やしてもスコア悪化するんだよなぁ…。うーん。

ダメもとで、モデル数増やしてみる?今は M=1 用と M=2 用のモデルの 2 つを並行して学習させて良い方を選んでるわけだけど、山登りパートはランダム性があるので例えば M=2 用として 10 個くらいのモデルを並列に学習させて一番ズレが小さいやつを選ぶということもできそう。


ダメだった、なんか伸びない…。一番良いモデルだけに依存すると過学習っぽいことになっちゃうのかな…。

じゃあ平均を取れば?ということで、M=2 用のモデル 10 個のパラメータの平均値を使って最短パスを計算する新しいモデルを作ってみた。各辺に対してそれぞれのモデルだと推定値いくらになるかを今までの方法で調べ、それらの値の平均値でダイクストラするイメージ。

これは有効だったみたいで、96.32G までは持っていけた。

ちなみに M=1 のモデルについては同様のことをしてもスコアは伸びなかった。まぁ M=2 モデルより単純だし伸びしろが無いのは頷ける。

最後にパラメータ調整をして締め。96.41G。

まとめ

暫定順位 / スコア

44 位 / 96,415,731,284

方針
  • M=1 用と M=2 用のモデルを用意してパスの出力及びフィードバックからの学習を行う。最初は M=1 用モデルの出力を利用し、M=2 用の方がフィードバックとのズレが小さいなら途中から出力を切り替える。
  • M=1 用のモデルは、各行/各列の辺の長さの分布の平均値をパラメータとして持つ。計 60 変数。
  • M=2 用のモデルは、各行/各列について前半部/後半部の分布の平均値と境界線の位置をパラメータとして持つ。計 180 変数。
  • 辺固有の乱数 δ, γ は 0 とみなす。
  • 各ターン、フィードバックを受け取った後、今までのパス及びその長さの履歴と今のモデルから推測されるそれぞれのパスの長さを比較し、その差の 2 乗の値の合計が小さくなる方向にモデルのパラメータを山登りで修正していく。
  • 出力するパスの決定はダイクストラで行う。各辺の長さは、推定した分布の平均値からそれまでにその辺を使用した回数に反比例して小さくなっていく値(UCB1 の第 2 項みたいなの)を引いたものを用いる。
  • M=2 用のモデルは 10 個同様のものを並列に学習させ、出力するパスを計算する際は、それらのモデルによる辺の長さの推定値の平均値を辺の長さとしダイクストラをする。これにより過学習が少し改善できる。