Neural Combinatorial Optimization with Reinforcement Learning
Euclidean TSPをやって、100頂点程度までなら最適解を出せた、という研究
この先行研究は1990年代とかでかなり古いっぽい。
入力は、2次元平面上の点の座標で、出力は
のpermutation.
RLで、policy を学習するっぽい。
条件付き確率で分解する。
ただしは先頭
個のpermutationを指す。
グラフの頂点数が違う場合にでも対応できるように、pointer networkというものを使っているっぽい。
とりあえずQiitaの記事があったけど、入力サイズが可変なときに対応できるらしい。
https://qiita.com/ymym3412/items/c84e6254de89c9952c55
意味不明なのでとりあえずここで終了
感想
policy based RLであることは我々の手法と同じだがさすがに時代が違いすぎてやっていることが違いすぎるのであんまり関係なさそう
結果も100頂点なのは小さすぎる
Learning Combinatorial Optimization Algorithms over Graphs
https://papers.nips.cc/paper/7214-learning-combinatorial-optimization-algorithms-over-graphs.pdf
NeurIPS 2019でもしゃべていたのでついにちゃんと読んだ
はじめに
界隈はこの論文を最強だと思っているらしい。多分グラフ機械学習で離散最適化やっている界隈は全員これを知っている。これを倒せば知名度上がりそう
先行研究との差分
この論文が先行研究としているのはこれ。
まだ詳しく読んでいないが、policy gradientをtrainingに使っているらしく、それよりもDQNがいいよという流れで出てきたっぽい。 DQNはoff-policyで、experience replyができるため、policy gradientよりもsample efficientだと言っている。
トレーニング時にグラフのembeddingを更新していくのはこの研究の、先行研究に対する強みっぽい？（先行研究では最適解をembedしているらしい）
自分たちの手法との共通点・差分
共通点
action
actionは頂点のselection
reward
normalizeしていないのでまあ差分でもあるがMCTSしないので別にnormalizeしなくていい
差分
state, transition
stateの定義をグラフ、ではなく、actionで選んだ頂点の(ordered) sequenceとしている。グラフ自体は学習の中で不変。自分たちの手法だと、(少なくともMISについては)グラフをだんだん小さくしていたが、この手法だと最後に選んだ頂点に新しくラベルをつけていく遷移をするだけ。
Q-Learning
そんなに異常Q-Learningをしていなかった。
アルゴリズム中のBatchサイズやは解く問題によってかなり調整しているっぽい。
embedding
GNNよりも一般的なフレームワークに見える。4-hopしか見ていないのでかなり浅い。パラメータはたくさんある。自分たちのGNNだと1-dimensionalなembeddingをしていたような気がするが、とくにweightedグラフに弱すぎるし次元を増やした方がいい気がする。こちらの論文では64次元
グラフも前処理としてkNNをとっている。
感想
自分で実装し直したほうがいい気がする。仮に精度出なかったら工夫したであろうところにきづけるだろうし
Unit-Length Embedding of Binary Trees on a Square Grid
を読んだ。
先行研究のミスを指摘していてワロタ。
概要
二分木をsquare gridに埋め込めるかどうかはNP-Complete
最大次数に注目すると、最大次数2のグラフはサイクルまたはパスグラフなので、埋め込みは自明に可能
最大次数を3に許容すると二分木となるが、この場合不可能であることが示されたのでギャップになっている
証明のテクは、正方形サイズの二分木で、一意な埋め込みがあるものを見つけ、あとはおなじみのlogic engineで証明する
このグラフはU-Treeと呼ばれ、一意な埋め込みをもつっぽい。
あとは、extended skeletonをこれで置き換えて構築し（そのままでは次数４の頂点があるのでうまく置き換える）、似たようなことをやる
これはいつものskeleton
感想
最大次数を3まで許容してしまうと二分木が許されるのがやばい。二分木は、ルートからの距離に比例してノード数が指数的に増えるが、一般の次元グリッドは、ある点からのマンハッタン距離に対してノード数は多項式なので、明らかに任意の二分木を埋め込むことは不可能。
直感的には、どんなに対しても、ある程度のサイズの二分木が存在して、一位に埋め込むことができそうで、あとは似たようにlogic engineを修正すれば埋め込みのNP-Completenessを示すことができそう。これはsquareグリッドに限らず、任意のパターンでおｋ
かなり汎用的なテクでびっくりしてしまう。
これ論文になるん？
ICMLに向けてやりたいこととか
解く問題を増やす
- Maximum Independent Set
- Maximum Clique
- Maximum Cut
- TSP
- Minimum Feedback Vertex Set (?)
まあ他にもいろいろ
実装を改善する
もっと演算を速くしたいですね
S2V-DQNと比較することにする
なんか他によくできる点がないか考えるか
Finding Near-Optimal Independent Sets at Scale
Yoichi Iwataに教えてもらった、MIS最強系の論文。Exactなアルゴリズムではないが、最適解がわかっているデータセットで軒並み最適解を出していて強い。
Kernelに遺伝的アルゴリズムを使用することを再帰的に行うアルゴリズム
Evolutionary Algorithm
- 良さそうなIndependent Setの集合をいくつか見つける。
- グラフの2-way-partitionを見つける。つまりseparatorを見つける
- separateされた2要素を混ぜ合わせたものもIndependent Setになっている。これをmaximalにして、さらにARWアルゴリズムによって局所最適にする
これらを繰り返し、閾値以上の連続失敗で打ち切り
Kernelize
Akiba & Iwataのやつ。
- Pendant degree 1のやつを確定させ、隣接のものを削除
- degree 2-Folding 次数2の頂点があって、その隣接2頂点間に辺がないなら、foldできる
- LP LPで解の上限を計算する。LPを解かなくても2部グラフのmaximum matchingで代用できる
- Unconfined 忘れた
- Twin なんだっけ
- Alternative 初耳
- Packing Akiba & Iwataのやつやな
Algorithm
select の部分が次数をみているだけの適当っぽいので、ここを良くする、というアイデアはあるが、普通にクソ遅そう
研究がまた先行研究とかぶった話
まあ別に初めてではないのであれなんですが
今回はちゃんと1~2週間ぐらい網羅的にサーベイして、完全にかぶっていないことを確認したつもりだったんですが、
先行研究のciteが2とかだった上に、問題の英語名が特殊で、自分の検索ワードと全然マッチしなくて、
しかもその先行研究の先行研究は、分野外（ハードウェア系）の最適化問題で現れた問題で、完全に界隈外の学会だったので
まったく気づきませんでした。
30年ほど昔の研究でした。
GNNの研究をしていると最近の論文しかないため、論文をサーチすれば何ができていて何ができていないかは比較的簡単に分かるのですが
離散最適化など、何十年にも渡って研究されているトピックの場合、あまり世に広まっていない論文だと
全然気づかないこともあるみたいですね。
反省として、こういうときは論文ではなく教科書を先にサーベイすべきです。
東大の図書館、実は本郷にきてから初めて利用したのですが
教科書が無限にあってすごい（それはそう）
ところで、担当してもらっていた先生から励ましの言葉をもらいました
Finding a paper working in your problem is not a bad news at all. It is a process of shaping your topic to the latest one. I am sure that the ideas you have got so far will be applied to solve some research problem soon.
これまでわりと一人で研究をしてきたのでこういう言葉を初めてかけてもらった気がします。
涙がでちゃって、あーやっぱ悔しかったんだなあと客観的に思ってしまいました。
一人ってよくないですね。
ツイッターで言語不明瞭をしちゃうし。
ちなみにこのトピックですが、一応先行研究との差集合は存在するのでそれで続けるという方針はあるのですが
いま客観的にみても、メインの主張がすでに言われているので、まったく同じ分野だとあまりインパクトあることは言えないかなあ
という気持ちになっています。
まあ人生の記録としてブログに
not-all-equal-3sat系証明のテクニック
グリッドグラフの描画とか、horizontalとverticalしか使っちゃだめ系描画など、一般に「自由度が相対的に制限される」ようなセッティングにおける可能性判定の証明に使える気がする。
証明のテクは、「必ずこの配置しかありえない」ような配置を組み合わせ、これから追加できる要素の配置を一通りに制限する。
not-all-equal-3satのインスタンスを目的のアルゴリズム(NP-Completeであると証明したいもの)を使って解くことを考える。
not-all-equal-3satの本質は、各clauseについて、すべてをtrueにしてはいけないということで、上述したような、配置が固定されるオブジェクトをうまく組み合わせ、個の隙間に要素を敷き詰めるような設定を作る。これで、もし目的のアルゴリズムで敷き詰めが可能かどうか判定できるならnot-all-equal-3satが解けてしまう、という流れにする。
