最終テストのスコアは2.917T、暫定テストのスコアは97.1Bでした。
問題
基本方針: 正規分布で近似して Maximum Likelihood Estimation
M = 2 のケースは複雑なので、まずは M = 1 のケースを考えることにします。また、D については D = 1000 と固定されていると仮定しておくことにします。
水平方向の辺について、行毎のパラメータが30個、辺毎のパラメータが30*29=870個あり、同様に垂直方向の辺について、列毎のパラメータが30個、辺毎のパラメータが870個あります。パスの長さはこれら1800個のパラメータの線形和として書けることに着目して、次のような確率モデルを考えます。
まず、1800個のパラメータはそれぞれ一様分布に従って生成されますが、これを扱いやすくするために、平均・分散が同じ正規分布で生成されることにするという近似をします。また、各クエリの結果についても、真のパスの長さを中心とする正規分布で生成されることにするという近似をします。すると negative log-likelihood が
- 各パラメータについて [パラメータの値とパラメータの期待値の差の二乗 / パラメータの分散]
- 各クエリについて、[クエリ結果と真のパスの長さの差の二乗 / クエリ結果の分散]
の和として書けます。これを最小化するようにパラメータを決めます。真のパスの長さはわからないので、線形モデルによる予測値で置き換えることにします。すると、これは Ridge 正則化有りの線形回帰と等価であることがわかります。これは機械学習で一般的なモデルですから、解くことができそうです。
Ridge 正則化有りの線形回帰の解き方
Ridge 正則化有りの線形回帰の解は closed form がある（英語版 Wikipedia: Ridge regression）のですが、これには逆行列の計算が必要なため、計算量がパラメータ数について三乗になってしまってこの問題では現実的ではありません。
そこで、最急降下法で解くことにします。色々なケースについてうまく行く学習率の設定は容易でないため、直線探索を使って更新量を決めることにします。私の場合は、ベクトルの更新量のノルムの最小値をあらかじめ決めておいて、それを二倍にすることを繰り返し、コストの改善量が最大になる値を採用するという方法でやりました。
コンテスト終了後の他の方の議論によると、共役勾配法を使うのが良い方法だったようです。
ここまでを実装することで95.4Bを獲得することができました。
注意: 途中経過の得点については、自分の実装ノートを基に復元しているので、不正確な場合があります。
M = 2 の扱い: 線形関数による近似
ここまで M = 1 を仮定してきが、M = 2 の場合を扱うことを考えます。
M = 2 では区間の境界という扱いにくいパラメータがあるため、線形関数で近似することにします。つまり、例えば水平方向の辺については、\( r \) 行目の左側の区間の辺の長さの「基本値」は \( H_{r, 0} \)、右側の区間の辺の長さの基本値は \( H_{r, 1} \) となるのですが、これを左側から \( k \) 番目の基本値は \( H_{r, 0} + (k / 28) H_{r, 1} \) であるというように近似します。M = 1 の場合は \( H_{r, 0} = H_{r, 1} )\ の場合であるとみなすことができるので、とりあえずすべてのケースを M = 2 として扱うことにします。
ここまでを実装することで95.8Bを獲得することができました。
M = 1 と M = 2 の分類
先ほどはすべてのケースを M = 2 として扱いましたが、M = 1 の場合は自由度が減るので、M = 1 と判断できればより正確に推定することが可能なはずです。
そこで、300ターンが経過した時点で \( (H_{r, 0} - H_{r, 1})^2 \) と \( (V_{c, 0} - V_{c, 1})^2 \) の平均値を調べ、これが一定の値未満ならば M = 1、以上ならば M = 2 と分類することにしました。300ターンというターン数や分類の閾値は実験の結果から決めました。
これを実装することで M = 1 の場合のスコアが上がり、95.9Bを獲得することができました。
コンテスト期間終盤には、\( (H_{r, 0} - H_{r, 1})^2 \) と \( (V_{c, 0} - V_{c, 1})^2 \) の平均値がとても小さいまたは大きい場合には、100ターン経過時点でも十分正確に判断できることがわかったので、そのようなロジックも追加しました。
強化学習の考え方:Exploration に対する報酬
ここまで開発してきたプログラムによる辺の長さの予測値と真の値の差を調べてみると、ある行または列がほとんど選ばれなかった場合に差が大きくなることがわかりました。特に、ある行の基本値が2000などとても小さい場合であったとしても、初期のフェーズにほとんど使われなかった場合、基本値の期待値の5000とみなされてしまってその行がパスに使われず、基本値が2000であることを知るチャンスが最後まで失われてしまっているケースがあることに気付きました。
この問題は強化学習の問題であると捉えることができ、Exploration vs Exploitation のバランスを取ることが重要なのです。情報を集めることが重要な序盤においては、その時点のパラメータ推定に基づく最短路よりも、まだ使っていない行または列を使う方が、最終的にはパラメータ推定が上がってスコアも上がる場合も多いのです。このアイデアを実現するために、各行・列において選んだ辺の個数が \( k \leq 15 \) であるとき、その行・列の辺を使うことに対して \( 3000 (15 - k)^2 / 15^2 \) の報酬を与える、つまりグラフにおける辺の長さを報酬分短くする、というロジックを実装しました。
このようにすると、まだ使っていない行・列の基本値は報酬によって2000になります。すると、まだ使っていない行・列を使うために、大幅に遠回りになるパスが選ばれるという副作用によって序盤のスコアが大幅に下がることがわかりました。Exploration が大事とはいえ、パスに含まれる辺の個数が増えないような範囲で Exploration するのが良いと考え、序盤はすべての辺の長さに一定値を足すことで辺の個数が最小でないようなパスは選ばれにくいようにしました。具体的には、報酬を含めたグラフの辺の長さの平均値が5000になるように、すべての辺の長さに一定値を足すようにしました。
ここまでを実装することで96.9Bを獲得することができました。
M = 2 の場合の区間の境界を推定する
これまでのところ、M = 2 の場合に区間の境界を推定することなく、線形関数で近似してきました。問題設定に忠実に、区間の境界を推定し、それぞれの区間では基本値は定数であるというようにモデル化することを考えます。
以下、水平方向の行について考察します。垂直方向の列についても同様です。
境界の初期値は中央であるとして、そこから右または左に1ずつ動かしていく方針を考えます。境界の左のインデックスが \( x - 1 \)、右のインデックスが \( x \) であるとします。また、\( H_{r, 0} < H_{r, 1} \)、つまり右側の区間の基本値が高いと仮定します。
上の図に注目してください。真の境界が現在の境界より右にある場合は、境界の右側、つまりインデックス\( x \)において真の基本値が現在の基本値の推定値より小さくなるので、その分のギャップが\( \delta_{r, p} \)に反映されるとすると\( \delta_{r, p} < 0 \)となりそうです。この考察に基づくと、\( \delta_{r, p} < 0 \)である場合は、境界を右に動かして良さそうです。逆に、\( \delta_{r, p - 1} > 0 \) である場合は、境界を左に動かしても良さそうです。この直観に基づいて境界を1ずつ動かすことにします。両方の条件が成り立つ場合はどちらに動かすかを乱数で決めることにします。
このヒューリスティックでは真の境界まで動かすことができない場合も多いのですが、\( H_{r, 0} \)と\( H_{r, 1} \)の差が大きい場合はそれなりにうまく行くようです。そして、そのような場合こそが境界の推定が重要な場合なのです。
ここまでを実装することで97.1Bを獲得することができました。
より高得点な方々の記事
AHC003の2.926T解法+経緯 by 1位の eivour さん
Twitter 投稿 by 2位の yosss さん
.gif)
0 件のコメント:
コメントを投稿