夏休み実験室
動的なリスタートは本当に有効なのだろうか？ 自分がやってきた種々の実験結果からはLubyリスタートとの差は（有意）にあるように思うが、 一方でせいぜい定数倍の差のようにも思える。 パラメータを増やせば増やすほど手が届かない部分が増えてしまうので、もうそろそろ色々カウンターを突っ込んだりするくらいならLubyでいいのではいう方向にかなり傾いている。 そもそもGlucose流のLBDのEMAを元にしたforce restartが有効であるためには学習節のよさは独立分布ではないことが前提なんだけど、これは本当なんだだろうか？ どこかで評価してあっただろうか？ 手っ取り早くブランチ切って自分でやってみた。
- 実験対象: UUF250 100問
- EMA補正を掛けた Slpr-0.6.2 で rst-lbd-len を色々変えて、学習節が追加されるたびに(LBDのEMA, 新学習節のLBD)を出力。
# 2021 branchを使用
$ parallel 'splrl-lbd {}' ::: uuf250*.cnf
$ cargo run --bin ??? < uuf*.csv > LBDn.csv # 新学習節LBDの分布を平均値に置き換え
$ 適当にプロット
まずUU250に対するデフォルト設定において、矛盾発生の決定レベルに対するLBDをプロットすると以下のようになる。
矛盾発生決定レベルとLBDの間には相関はほぼない。 どのような発展においてもそれなりによい学習節が生成されることを考慮しなければならない。 下図はそのヒートマップである。実際には大きな決定レベルは出現頻度が少ない。 極端に高いレベルを避けるよりも持続する高レベルを避けることが重要となるのだろう。
次にEMAの長さを24（デフォルト）,5, 3と変えて、LBDのEMAに対する新規学習節のLBDをプロットしてみたのが以下の図。
決定レベルと違い、極めて強い相関が得られたことからLBDのEMAはよい未来予測になっていると言える。 さらに長さを長くする方がより良い結果が得られる頃から同じような長さの節がしばらく生成されるという傾向があると言えよう。
同じデータを平均値ではなくヒートマップで可視化してみた。 上図が矛盾発生ごとにリスタートを掛けて全く連続性を排除したもので、下図はリスタートをしなかったものである。
後者の方がより小さいLBDが生成されている。実際に実際実行時間も後者の方が圧倒的に短い。 無作為な探索空間の選択よりもLBD値を使った戦略の方が、LBDの小さな領域に長く滞在できていると思われる。
両者はリスタートに関して両極端な戦略になっている。 なぜ、no-restartの方がもう一つの極端なanytine-restart戦略より圧倒的によいのだろうか。 activityのメカニズムから矛盾解消の対象になった変数は再び選択されやすく、したがってassertされるまで集中的に選択されることが期待される。 一方、anytime restartは（バックトラックと比べて網羅的再構築なので）対象が逸脱しやすく、activityの恩恵を十分に得ることができないからだろう。 初期状態はともかく、矛盾はそれなりに十分に深く調べて（assertを見つける努力をして）からリスタートすべきである。
ということで、ヒートマップにおいてno-restart の方が良い結果を示しているのは、assertがより速く求解が進むことで、より簡単な問題を長い間、対象にできていたからではないだろうか。
結論
- 探索空間はLBDで分類できるクラスタから構成されている。
- より良いクラスタを選ぶことは実行速度の改善につながる。
- LBDのEMAはクラスタを選ぶためのよい尺度となっている。少なくともランダム選択よりはよい。
- 突発的な大きなLBDを持つ節を避けるのではなく、平均EMAが大きなグループ（クラスタ）に突入している時に（できれば早期に）脱出できるというのがGlucose流の動的リスタートの持つ効果である。
本文を書いたことで後ろに回されてしまったイントロとベルリンの壁
論文書くのは仕事じゃない。しかし一年に一度くらいは開発ではなくて、文章をまとめる一ヶ月があってもいいかもね。そもそも今年もCompetitionに出しそびれたし。それに夏といえば、宿題やるのが日本の文化。 9月1日提出に間に合うようになんかしよう。爆音で音楽聴きながらlatex的なことをしよう。
2020-07-24
- 旧題: Restart as A Multi-Armed Bandid Problem
- 新題: Lives of Clauses
2020-07-27
0.4.2がいい結果を出しそうなので、それをリリースしてから、なぜ0.4.2がいいのかを説明できるようなものにしよう。 "Lives of Clauses"はいいタイトル。
2020-08-12
Splr-0.4.2のリリースがずるずると延びてしまっていまだにとりかかれてない。。。。 うーん、自分で言い出したくせに8月31日の1日でやっつけることになるのか。 コロナのせいにできるような言い訳を考えておこう。。。
2020-08-24
あと数日でSplr-0.4.2 改め Splr-0.5.0 がリリースできる。 そして、もう数日しか夏休みは残ってないんですけどどうしましょう。
2020-09-01
今年の夏休みは9月下旬にはじまるという話を聞いたので、まだ手をつけない。
2021-01-13
そろそろ手が付けられそうになってきたので、テーマ案を考える。
- 案1: 学習節の一生
- 案2: 意外に影響が大きいvivicationの効果測定
ずっと案1のつもりだったけど、今日急に案2もいいかもと思い出した。 どちらにしろ今週中には始めよう。 夏休みの宿題を1月に始めるという意味で非常事態を宣言するのだ。
2021-01-14
Splr-0.6.0 リリースした。夏休み開始。
2021-01-18
0.6.0はリリースしたけどどうせなら0.6.2をリリースしてから開始しよう。明日の予定。テーマはマルコフ性。