動機
この講義は2年くらいまえから気になっていて、Machine Learningの次くらいに受けようかなと思っていたのが大分遅くなってしまいました。僕は大学でコンピュータサイエンスとかプログラミングを習ってないので、大学のコンピュータサイエンスの講義に憧れがあるんですよね。
そんなこんなでお仕事でもエッジのDeep Learningをやるようになりました。量子化された状態で係数をいじって再学習するのを浮動小数点演算を使わずにやろうとすると、それって離散最適化だよねって気がついて、そこから根性出してやってみました。
どんな講義
- 熱血先生の熱い授業
- 最先端のトピック
- 異常に難しい課題
この辺が、僕が憧れるハイレベルな大学の講義そのもので良かったです。多分、東大とか京大とかMITとかはこんな講義しているはずです。
僕が卒業した東京理科大学でも熱血先生はいましたが、ちゃんと授業を聞いていれば単位はもらえたし、単位もらうために自分で論文を探してきて読んで理解しないと駄目って事は無かったです。はい。
最後までやってみてある程度のプログラミング技術と経験は必要かなと感じました。（情報系以外の学部生だと正直きついと思う）
- グラフやツリーのデータ構造を書けて、適当に操作できる。可視化ツールを自分で作れる。
- レアケース用の入力データを自分で作ってちゃんと処理できるか確認できる。
- アルゴリムに乱数を使うときはシードを固定してデバッグするとか、そういう実践的なテクを知っている。
- nが大きくなったときにメモリ不足で落ちるような、アルゴリズムと関係の無い障害も乗り越えられる。
- 最後力業で解けそうなとき、ピンポイントで処理速度をチューニングできる
- 英語の論文を読んでアルゴリズムを実装できる。上手く性能がでなくても泣かない。
くらいの力は欲しいです。
基本的には長い動画を見て、自分で離散最適化を解くソルバーを書きます。解くといっても全部最適解は最初から無理で、それなりの時間で近似解を求める実装になります。だいたい週末の課題が6問あって、先生の言うとおりに実装しても1問目くらいしか解けないのが困ったところ。制約ソルバーのアーキテクチャが聞けるという素晴らしい体験をしましたが、その通りに実装してもn=10000くらいの問題を解くのは無理だと思う。
講義のレビューを見ても「今まで受けたオンライン講義の中で一番難しい」とか「動画がクソ長い（loooooooooong)」とか、散々書かれていますが、☆5つだったりすので最後までやった人は楽しんでやってたと思います。個人的には動画が長いよりも、動画の内容が課題を解くのに役に立たないのがなんとかして欲しい。
ちなみに、Courseraには他にも人気の離散最適化のコースがあります。
三国志のアニメが目立つこちらの講義は、MiniZincという制約ソルバーを使って離散最適化を解く講義です。問題をどのようにソルバーに落とし込むかという講義です。講義のアニメが面白いのですが、僕の目的とは違ったので途中で解約しました。単純にソルバー使って問題解きたい人はこちらの講義をお勧めです。
プログラミング環境
最初は自分のVAIO＋Rustでやってましたが、出張中のホテルでやりたくなって途中から会社支給のPCにしました。win10、i5、メモリ8Gの人権があるかどうかギリのラインです。人権以前にRust環境（正確にはVSのリンカー）が入れられなくてPythonで解きました。終わってみれば、そんなにハイパワーな環境は要らなかったです。
Rustはこういうアルゴリズムを試行錯誤するにはものすごく向いていない言語で、アルゴリズムが固まってからRustで清書しないと駄目という事を実感しました。例えば、ナップサック問題で入力が整数なのでi32としていろいろ書いた後、リラクゼーションという整数を実数に拡張してプルーニングの効率をあげる仕組みを入れようとすると、ほぼ全ての場所を書き換えて回るのが辛かったです。ただ、絶対負にならないと思っていた値が負になった瞬間に落ちてくれたので、しっかりしたプログラムを書くには良い言語だと思います。Rustに関しては、もっと経験値を上げたいところ。
内容
ナップサック問題
week1はチュートリアルなので、先生のコスプレを楽しんでいればOK。普通の人はweek2のナップサック問題で心が折れると思う。
ナップサックに荷物を入れる入れないをツリー構造にして、再帰的に解を探し行く方法を教えた後にこういう例がでてきます。探索空間でずっと左ばっかりやって駄目だったら、一個右にいって後は左ばっかり選んでも良いよってのりなんですが、あれこれ単純に再帰で書くの難しくね？って思っていろいろ考えるわけです。
で練習問題は、n=1000とn=10000があってそもそもこのやり方だと全然計算が終わらない。普通にDP使っても駄目。ここで改めて最適解を求めたら駄目で、適当な点数を稼げる近似解が必要と理解するも、なかなか近似解の情報って無いんですよね。ちょうどその時に、この本を入手して事なきを得ましたが、この本がなかったらこの講義はweek2で挫折していたでしょう。
彩色問題
ここで、汎用的な制約ソルバーの話がでます。
多分、これを信じて汎用ソルバーを実装すると、それだけですごい時間食いそうな気がします。講義では4色とか決まった色を割り当てるアルゴリズムはそれっぽく教えてくれるのですが、課題は最小の色数を探す問題なのでこれまた講義が役に立ちませんでした。ちなみにこの問題の有効な解き方（Local Search）は後の週で詳しく教わります。
巡回セールスマン
ここが最大の壁でした。ただ、巡回セールスマンについては、厳密解が求めにくいこともあり、Webで近似解の情報を集めることができたのは良かったです。クロスした経路をまっすぐにしたり、ちょっと手を加えると値が小さくなるのがうれしかったのですが、課題の都市数が多すぎて小手先の最適化では歯が立たなかったです。
乱数を使ったアルゴリズムに入れる前に、greedyの出力をある程度整形してあげると効果が上がるのですが、整形しすぎると同じような局所解になってしまうのが面白かったです。ほどほどの状態で乱数を投入するのが良かったです。本来はここでシミュレーテッドアニーリングとかタブーサーチとか遺伝アルゴリズムを使って欲しそうな講義でしたが、基本的に講義のアルゴリズムは課題を解くときに信じないことにしていているので気合いで乗り切りました。
全体を通してずるをしたくなったのが唯一この週です。乱択アルゴリズを採用したので、暇な会議中にずーっとソルバーを回していると、たまに最適解っぽいのを出すんですよね。そうなると、自分が書いたソルバー自体は解く能力があるんだから、そのまま正解だしてもよくねと思ってしまいました。講義の最初に、答えだけ出力するのは駄目よって言われていて、外部のソルバー使って解いてもOKなのに、なんで答えだけはNGなんと思っていたのが、こういうことなんだなと。
人生で一度くらいは巡回セールスマンソルバー書いても良いと思います。
工場配置問題
講義ではシンプレックス法の説明がありました。多分、この本読んだ方が分かりやすいです。 https://www.amazon.co.jp/dp/4320017862
ほどほどに手こずって解きました。結局シンプレックス法は使わなかったし、人生で一度くらいはシンプレックス法書いた方が良いと思いました。
最終問題
最後の問題はあーなるほどーと思える問題でした。（内緒）
感想
SICPやCourseraのMLコースでも感じたのですが、途中まで泣きそうな課題を出しながら、最後の最後は急に難易度が下がるのはそういう物なんですかね。
greedyアルゴリズムが最強。いろんな指針でgreedy回したり、iterated greedyやるだけでもずいぶん点数かせげました。頭が良い人が考えるgreedyは、下手なアルゴリズムよりも良い成果と近似保証もあり侮れないなと思いました。
世の中にある汎用ソルバーはすごい。自分で実装したら数時間かかるものが秒で答え返してくる。
巡回セールスマンソルバーを書くという人生の実績を解除したので、また次の講義に挑みたいです。すごく楽しかったです。
