OR+AI

ずーっと昔にAI学会に招待されて，OR vs AI というパネルをしたことがある．そのころは，AIは学会員は多いけど三流の研究者が集まっているという感じだっがが，最近では逆転している気がする．

AI全体だと，抽象論のみで機械が考えることができるかを真面目に考えている人たち，実学中心の企業の人たち，機械（深層）学習の人たちに別れていると思うが，三番目が最近伸びている．

これは，機械学習の理論（ORの人が参入しているのはこの分野だ）ではなく，ちゃんとした応用に役に立つ理論をやっている人たちが中心になっていると感じる．深層学習の基礎になる定理（ほとんどが役に立たない）より，役に立つための実験の裏付けがちゃんと成されている．

これをOR（というか最適化）に使わない手はない．たとえば，劣勾配法という古典的な最適化手法がある．応用では，Lagrange緩和と併用される．もともとは旧ソ連のShorたちの一派がさかんいやっていて，Held and KarpがTSPに応用して我々のコミュニティに知れ渡った．

理論としては，適当なステップサイズで無限回すると収束するというのがあるが，あまり役に立たない．下手をすると，Lagrange緩和の下界（大きいほうが良い）がマイナス無限大にぶっ飛ぶので，あまり実務には推奨しなかった．

同等のことがDantzig-Wolfeの分解法でできるので，数理最適化ソルバーをもとに使うことを薦めていたが，列生成をPythonとかで書くと遅い．CからAPIコールすればいいのだが，書ける人は少ない．また無料のソルバーは不安定だし，有料のは高い．その点，劣勾配法は無料だが，実務的にはマイナス無限大に発散するのは困る．

ベンチマーク問題例だけを対象としている研究者は事前にチューニングすれば良い．たとえば，ステップサイズの初期値は2で，反復ごとに1.05で割るとかいうおまじないが論文には書いてある．

実際問題では，どんな数値が入っているのかわからないので，こんな方法だと何が起きるかわからない．後輩の超一流の研究者が，実際問題をときたいという人に（親切にも）ソースコードをあげたら，全然収束しないと文句を言われたらしい．

劣勾配法を安定的に使いには，深層学習で得た実験的な知見を使うと良い．たとえば，学習率探察のために，学習率（ステップサイズのことだ）を２倍２倍にしながら目的関数値をプロットして，適当な（初期）学習率を得るというヒューリスティクスだ．

さらに，そこで得た最大学習率になるように徐々に増やして，それからcos関数に沿ってアニーリングし，同時に慣性項を徐々に減らして，cos関数に沿って増やすという方法を使う．これは，fit-one-cycle法といって，なぜかは分からないが深層学習だと超収束する．

ためしに，k-median法につかったら安定して動くようだ．ただし，最適化の場合には下界と上界も得られるので，その差（ギャップ）をたよりに，ステップサイズを調整すると更に良いようだ．深層学習で有効なAdamとかは下界がないために，適当に調整する方法なので，それよりは良い．

ただし，やはり対象がNP-hardなので難しい．それでもこれらのコミュニティは連携して，研究活動をする必要がある．特に，実験的な部分では有効だと思うのだが，ORコミュニティ（数学者が多い）は，機械学習コミュニティの数学的な背景の穴埋めで論文を書く傾向があるので，困ったものだ．