tbf07-seat-optim.pdf

Transcript

1. 技術書典のサークル配置最適化 ver. tbf07 @shuhei_fujiwara last update: 2019-10-09 1
2. 自己紹介 藤原秀平 (FUJIWARA Shuhei) Twitter: @shuhei_fujiwara ▶ 技術書典運営スタッフ ▶ Google Developers Expert (Machine Learning) ▶ TensorFlow User Group Tokyo Organizer 2
3. 技術書典知っていますか? ▶ 技術書の同人誌即売会 ▶ 来場者数は約 1 万人!! 3
4. 解決したい課題 ▶ （技術書典 7 の場合）約 640 サークルがそれぞれどこの席に座るかを決めたい ▶ 近いジャンルのサークルが近くに集まってほしい こ40 こ01 け78 け41 け38 け39 け40 け01 く20 く01 き40 き01 か80 か41 か40 か01 お40 お01 え40 え01 う78 う41 う40 う03 う01 い30 い01 あ01 あ20 催事スペース 荷物作業スペース スポンサーブース 運営ブース 出⼝ ⼊⼝ 4
5. 得られた成果 ▶ 現在は自動生成された叩き台をもとに議論と調整を重ねて決定している ▶ 技術書典 4 (約 250 サークル) でも叩き台を作るのに 1 日 2 日かかるくらい 大変だった ▶ 現在は約 640 サークルでも近いレベルのものを 1 分程度で出せるように ▶ 技術書典 5 〜 7 で 1 年半使っている ▶ 実際に現場で最適化を使って得られた知見も多い ▶ 隠すことはあんまりないので、だいたい喋ります 5
6. どういう配置だと嬉しい? 最初の要件: 「似たジャンルのサークルは近くにいてほしい」 ▶ サークルの類似度を定義する必要がありそう ▶ 何をもってして近くと定義すれば良いか 6
7. Phase 0: サークル間の類似度
8. サークル間の類似度を定義する tag 1 tag 2 tag 3 · · · circle 1 数学 機械学習 R · · · circle 2 機械学習 数学 . . . . . . . . . . . . circle m Android IoT Kotlin · · · ▶ タグ集合同士の類似度なら上手いこと定義できそう ▶ タグはどこから持ってきたか? ▶ 技術書典 5: 運営が手作業で作っていた ▶ 技術書典 6: サークル側が自分で入力するシステムが実装された ▶ 技術書典 7: 表記揺れなどを修正・管理するシステムが実装された 7
9. 類似度の定義 タグの強さ r を次のように定義する: r(t) := 1 (1 + log nt)np t where nt := [Tag t を持つサークルの総数] サークル間類似度の定義 Ci , Cj をサークル i, j を表すタグ集合として s(Ci , Cj) := max t∈Ci∩Cj r(t) ▶ 珍しいタグが優遇されるように傾斜をつけた ▶ p は傾斜を調整するパラメータ（調整が辛いので本当は入れたくなかった） ▶ タグが多いサークルが有利にならないよう最大だけを見る 8
10. タグと類似度に関する残課題 珍しいタグの傾斜 ▶ 非常に重要だが調整するのが辛い ▶ 良し悪しを判断するには結果を出して議論するというプロセスが必要 ▶ 予め複数パターン用意しておくなどの対処になる 9
11. タグと類似度に関する残課題 タグそのものの問題 ▶ メイントピックではないタグに引きずられるパターンが非常に多い ▶「機械学習、クラウド」というタグのときに機械学習島とクラウド島の どちらに配置されるのがそのサークルにとって幸せか? ▶ 今のところ判断するには人間側の練度が必要 ▶ 何とか技術で解決したい部分 10
12. タグと類似度に関する残課題 タグ以外の情報を上手く使えると嬉しい ▶ 過去回のサークルチェック ▶ 同じ人がチェックしたサークルは似ている? ▶ 過去回のかんたん後払いでの購入履歴 ▶ 同じ人が購入したサークルは似ている? ▶ いずれも新規サークルは履歴がないというのが問題 ▶ 今のところ初参加サークルの割合はかなり大きい ▶ 初参加で配置が上手くいかないとすごく体験が悪い 11
13. サークル配置の基本アイデア
14. 各席同士の近さは定義するべきか? 真面目にやると泥沼 ▶ 隣と背中合わせはどっちがどれくらい近いの? ▶ 通路を挟んで向かい合わせは近いの? ▶「ちょっとレイアウト変更したから 10 分で回し直して」 こ40 こ01 け78 け41 け38 け39 け40 け01 く20 く01 き40 き01 か80 か41 か40 か01 お40 お01 え40 え01 う78 う41 う40 う03 う01 い30 い01 あ01 あ20 催事スペース 荷物作業スペース スポンサーブース 運営ブース 出⼝ ⼊⼝ 12
15. Phase 1: サークルをいくつかのブロックに分割 circle block circle A あ circle B う circle C う circle D あ . . . . . . あ size: 3 う size: 3 い size: 2 え size: 2 A B C D E F G H I J A D I B C E F J G H サークル A~J を部分集合に分割 あ size: 3 い size: 2 う size: 3 え size: 2 ▶ 左の感じの表が自動でできる ▶ 実用上は「あ」とかよりももう少し細かくブロックを分ける ▶ 各ブロック内での詳細な並びは別の問題として解く 13
16. Phase 2: 各ブロック内の詳細な配置 circle block seat circle A あ 1 circle B う 2 circle C う 1 circle D あ 3 . . . . . . . . . あ01 あ04 あ02 あ05 あ03 あ06 A D B E C F B E F A C D ブロック内での適切な配置を 決める ▶ 各ブロックごとに具体的な配置を決定する ▶ ここでは誰と隣り合っているかなど細かい条件を考慮する 14
17. FAQ: なぜ問題を 2 段階に分けたのか 要件変更に柔軟に対応する必要があった ▶ 定期的に会場が変更される ▶ 秋葉原通運会館 ==> 秋葉原 UDX ==> 池袋サンシャインシティ ▶ 実際に机を並べる詳細なレイアウトは直前まで決められない ▶ 同じ会場でも当選サークル数や導線計画など様々な要因が絡む ▶「今お誕生日席作った（配置会議当日） 」 ▶ ここの難しさを Phase 1 で吸収する戦略 ▶ これは実際めちゃくちゃ上手く働いた 15
18. FAQ: なぜ問題を 2 段階に分けたのか Phase 1 を挟むことで人間の意図を適度に反映させやすい ▶ たとえば「壁際一帯に同一ジャンルの大きいエリアができてほしい」など ▶ ブロックの切り方だけ人間が決められるくらいが丁度良かった ▶ End-to-end で解く形にするとどうしても難しいチューニングが発生する ▶ 配置の良し悪しの正確な判断は難しいのでチューニングが楽なモデリングに することが非常に重要 ▶「ここはチューニング可能なパラメータにしようぜ」は最悪の愚策 ▶ 技術書典 6 では最重要タグだけじゃなく top k を見る実装などもしたが チューニングが難しいので技術書典 7 では外した 16
19. FAQ: なぜ問題を 2 段階に分けたのか 実は「似たジャンルのサークルは近くにいて欲しい」には 2 種類の気持ちがある ▶ 買う人の視点 (Phase 1) ▶ ムラなくジャンルごとのエリアを形成したい ▶ ブロック単位で上手く分けられていれば OK ▶ サークル参加者の視点 (Phase 2) ▶ 隣が（特に珍しいジャンルで）同好の士だとすごく嬉しい 17
20. Phase 1: サークル分割問題
21. Phase 1: サークルをいくつかのブロックに分割 circle block circle A あ circle B う circle C う circle D あ . . . . . . あ size: 3 う size: 3 い size: 2 え size: 2 A B C D E F G H I J A D I B C E F J G H サークル A~J を部分集合に分割 あ size: 3 い size: 2 う size: 3 え size: 2 ▶ 左の感じの表が自動でできる ▶ 実用上は「あ」とかよりももう少し細かくブロックを分ける ▶ 各ブロック内での詳細な並びは別の問題として解く 18
22. Size-Constrained Minimum k-Cut サークルをブロックに分割する問題はサイズ制約付き最小カット 問題設定 ▶ ノード vi : サークル i に対応 ▶ sij : サークル i, j の類似度 ▶ これがそのまま vi , vj を結ぶ辺 eij の重みになる ▶ 一気に k ブロックに分けたい場合は k-Cut j i sij 19
23. 技術書典 7 における工夫 600 200 250 150 Figure 1: 技術書典 6 以前 600 400 200 250 150 Figure 2: 技術書典 7 ▶ 技術書典 6 以前はまとめてブロック分けをしていた ▶ 技術書典 7 では木構造を持たせて再帰的に分割 20
24. 人の知見を上手く入れ込みやすくなる 背中合せなので 実は遠い 通路なので参加者は まとめて買いたい 壁際が同じジャンルで揃えると 人が上手く流れる ▶ 大エリアで見ても小エリアで見てもまとまりがある状態になる 21
25. サークル分割問題のアルゴリズム 3 つくらい手法を検討して最終的に簡単なヒューリスティクスに着地 （没ネタは時間があれば紹介） 1. ランダムに実行可能解を生成 2. ランダムに 2 ブロックを選択 3. 各ブロックからランダムに 1 サークルずつ選択 4. 目的関数値が改善するならばサークルの座席交換を実行 5. 2–4 を適当な回数繰り返す 22
26. 余談: 整数計画をソルバーで解き切れるならそれが最善? + 上手くいかなかったときに定式化が悪いのか最適化手法が悪いのか 問題を切り分けられるとすごく嬉しい + ソルバーに投げ込めるとアルゴリズム実装上は（比較的）楽 − ソルバーの有無や良し悪しに強く依存する − 厳密解法だと計算時間が安定しないのは実用上かなり辛い ▶ 途中で打ち切ってもそれなりの解が得られる手法が安全 ? 実際に解の質がどの程度違うか今回は未確認 ▶ 配置作業をしていて稀に「ここは解法の甘さかな」と思う部分が見つかる程度 23
27. サークル分割問題の残課題 モデリング自体の完成度はかなり高くなってきたので 最適化手法の改善に手を付けたい ▶ サイズ制約付き最小カットに特化した効率的なアルゴリズム ▶ NP-hard であることまでは知られているがアルゴリズムの研究が少ない ▶ サイズ制約付き劣モジュラ関数最小化 ▶ カット関数は劣モなのでこの方向で良い研究があればそれでも良い ▶ 研究としてはいくつかあるがカット関数に対して上手くいった例が 見つからない ▶ 素直に今のアルゴリズムの延長線上で改良する線もある ▶ 交換する 2 サークルをランダムではなく上手に選ぶ ▶ 目的関数値への貢献が小さいものなど 24
28. おまけ: 開発のタイムライン（うろ覚え） ▶ 技術書典 5 の配置発表 1 週間前: ▶ サークル一覧を見て絶望し、自動化を検討し始める ▶ 1 〜 2 日目 ▶ 類似度の定義を考えて試し用データ作成 ▶ プロトタイプを作り始める ▶ 3 〜 4 日目 ▶ 4 種類のプロトタイプを実装して最も上手くいった結果を作業者に共有 ▶「意外と形になってるのでこれ叩き台で良いかも?」という話に 25
29. サークル順列問題
30. Phase 2: 各ブロック内の詳細な配置 circle block seat circle A あ 1 circle B う 2 circle C う 1 circle D あ 3 . . . . . . . . . あ01 あ04 あ02 あ05 あ03 あ06 A D B E C F B E F A C D ブロック内での適切な配置を 決める ▶ 各ブロックごとに具体的な配置を決定する ▶ ここでは誰と隣り合っているかなど細かい条件を考慮する 26
31. ブロック内のサークル順列問題 ここでの目標は類似したサークルが隣り合うこと ▶ 同一ブロック内のサークルは一直線上に 並ぶと仮定 ▶ この仮定が自然になるようにブロックを構成 ▶ 最長ハミルトン路を求める問題 1 3 2 4 s12 s23 s34 s12 s13 s24 27
32. サークル順列問題のアルゴリズム 実装上既存の TSP ソルバーに乗っかりたかったのでちょっと無理した 1. 符号を逆転させて定数を足すことで最短ハミルトン路問題に変換 2. 最も遠い 2 頂点 vi, vj を端点に固定 3. vi, vj を結ぶ辺 eij の重みを 0 に修正 4. このグラフに対して TSP を解く ▶ 重み 0 なので eij は必ず選ばれる 5. 得られた閉路から eij を除いて終了 28
33. 実装上の話 ▶ TSP ソルバーは Google OR-Tools を選択 ▶ 他にも良いソルバーがあるのは知っているが、解の質に困っている状態では なかったのでエンジニアリングのコストが最も少ないものを選んだ ▶ Python 以外への移行という意味ではソルバー依存をなくせると ちょっと嬉しい ▶ あくまで趣味的な話 29
34. サークル順列問題の残課題 ▶ アルゴリズムがソルバー事情に縛られてて明らかにイケてない ▶ 実用上は十分なので気持ちの問題っぽい ▶ 今のところブロックサイズは高々 50 くらいに分割しているので厳密解 得られないかなあ ▶ 分枝限定法くらいは書いてみたけど自前で雑にやっても遅いよね... ▶ ついでに頂点罰金法とかも試した（有限回での終了が保証できなくて解散） ▶ 小規模な最長（or 最短）ハミルトン路問題を解く良い手法知っている人が いたら教えてほしい 30
35. 人手による調整
36. ブロック間の調整 A D I B C E G H L F J K あ01--あ03 い01--い03 う01--う03 え01--え03 ブロックの位置を人手で入れ替える A D I B C E G H L F J K あ01--あ03 い01--い03 う01--う03 え01--え03 ▶ 同じサイズのブロック同士は位置を交換することができる ▶ ブロックのサイズをできる限り揃えて人間による調整の余地を残す ▶ 元々の「あ」〜「こ」のブロックをもう少し細かく分割 31
37. ブロック内の調整 ▶ タグだけでは分からない情報を考慮して細かい並び替え ▶ 申込み時のコメント・ Web ページ・過去の頒布物などをチェック ▶「この壁際一帯見ておくわ」みたいな感じでやってる ▶「このサークルメイントピックじゃない方のタグで引っ張られちゃってるね」 みたいなのがかなりある ▶「そもそもこのタグの組合せだとどこにいるのが幸せなのか?」議論 ▶「Ruby、機械学習」は Ruby 島と機械学習島どっち? 32
38. ジャンル以外の情報を考慮した最終調整 ▶ 頒布部数が多いサークルが並ぶと危険 ▶ 子連れなどの事情を考慮 ▶ 技術書典 7 では託児所があったので不要 ▶ 全体最適のために露骨に割りを食っているサークルがいないか ▶ etc... 技術書典 6 では自動配置の時点で一部制約を考慮していたが 各ジャンルを上手くまとめる時間 ≫ 最終調整にかかる時間 なので技術書典 7 ではひとまず自動化の範囲から外した 33
39. まとめ
40. 上手くいった要因 ▶ アルゴリズム実装者が実際の配置作業担当者でもある ▶ 正確には配置担当になった後に人手では無理だと悟って自動化した 34
41. 現実世界の壁 ▶ わかってはいたけど目的関数の設計は難しい ▶ 出てきた解の良し悪し（最適化的な意味ではなく実用上という意味）が すぐに判断できるかどうかで試行錯誤の速度が段違い ▶ 今回は作業者兼アルゴリズム実装者なので、出てきた解の良し悪しがある程度 わかるという意味で比較的好条件だったはず ▶ でもやっぱり正確な良し悪しは sfujiwara でも判断し切れない部分があって 議論しないとわからないので大変 ▶ 仕事でやるとお客さん連れてこないと判断できないとかで（以下略 ▶ 最適化に限らずソフトウェア開発全般の問題という気も...? 35
42. 付録: サークル分割問題の定式化色々
43. 2 次の整数計画問題としての定式化 若干センス無い気がするけど最初はこう捉えていた block 1 block 2 block 3 · · · block N circle 1 1 0 0 · · · 0 circle 2 0 0 1 · · · 0 circle 3 0 0 1 · · · 0 . . . . . . . . . . . . ... . . . circle M 0 1 0 · · · 0 min x m ∑ i m ∑ j n ∑ k sij xik xjk s.t. xik ∈ {0, 1} n ∑ k xik = 1 m ∑ i xik ≤ ck ▶ 同一ブロック内のサークル間類似度の総和を最大化 ▶ ↔ 離れ離れになるサークルの類似度総和（カット）の最小化 ▶ ブロック k には任意のサイズ ck を与えることができる 36
44. 技術書典 5 で試したこと 整数計画問題として解き切れないか? ▶ 目的関数が 2 次の整数計画は解き切るのが厳しいけれど 補助変数を導入すれば線形に落とせる ▶ やってみたら必要な補助変数が思ったより多くてダメ ▶ 2 分割を再帰的にやるとかも考えたけど厳しい ▶ 100 サークルを 2 分割くらいが限界っぽい 37
45. 技術書典 5 で試したこと 連続緩和して適当に丸めれば良くない? ▶ 基本的にサークルを細かくちぎるほど得をしてしまうので全然ダメ ▶ xi1 = xi2 = · · · xin = 1/n みたいな酷い緩和解が平気で出てくる 38
46. 技術書典 5 で試していないこと ▶ QUBO に落とせば量子コンピュータでいけるらしいぞ ▶ 知らんがな 39
47. 最小カットの素直な LP 定式化に制約を加える 技術書典 7 で検討したけど何を思ったかコード捨てたっぽい PC の奥底から発掘したのでこれからリベンジ ▶ 最大流の双対問題に整数制約とかサイズ制約を足す ▶ そこまで変数は多くないけど 50 サークルくらいで MIP ソルバー（CBC）が 音を上げた ▶ MIP ソルバーが苦手なタイプの問題なのか...? ▶ Gurobi とか CPLEX でもやりたいけどそんな金はない ▶ 制約を外すと完全単模なので光の速さで解けてムカつく ▶ もうちょいきちんと検討しても良い気はする ▶ 整数制約なしで解いて違反したところにちょっとずつ制約足していくとか...? 40