サンタコンペで二度全完した話

Kaggle Tokyo Meetup #4での発表資料

Transcript

1. サンタコンペで二度全完した （のに優勝出来なかった）話 Kaggle Tokyo Meetup #4 2018/05/12 岩田 陽一 (wata) https://github.com/wata-orz/santa17
2. 内容 1. 自己紹介 2. 問題概要 3. 解法概略 4. タイムライン 5. 解法詳細 2
3. 3 自己紹介  東大情報科学科→情報理工(2016年3月博士卒)  国立情報学研究所 助教  離散アルゴリズムの研究をしている  機械学習は初心者 世界 1 位 (2010) 世界 2 位 (2011) 世界 3 位 (2009) 3回優勝 (2013,2015,2016) 競プロ： wata Twitter: @wata_orz ICFPC Masterになりたい…
4. Kaggle Santa  年末年始に毎年開催されている最適化系コンペ  機械学習要素は（ほぼ）ない  去年に続いて二度目の参加  賞金  1位: $8,000、2位: $6,000、3位: $3,000  一番長い期間トップ賞: $8,000 4
5. 問題概要 5 1,000種類×1,000個 1,000,000人 サンタと子供の幸福度関数, が与えられるので、幸福度の和 σ , + σ (, ) が出来るだけ大きい割当 : 子供→プレゼント を求めよ。  , ≔ サンタが子供にプレゼントを配る幸福度  , ≔ 子供がプレゼントを貰ったときの幸福度 , はスパースで非零要素がそれぞれ106個、107個 1+1+3+4+1+2=12 1 1 0 0 0 0 1 1 3 0 0 4 1 2 0 2
6. 問題概要 6 ただし、1,000,000人の子供のうち4,000人は双子で、双子には同 じプレゼントを配らないといけない。 1,000種類×1,000個 1,000,000人 1+1+1+1+3+2+2=11 1 1 0 0 0 0 1 1 3 0 0 4 1 2 0 2
7. 解法概略  双子制約がない場合は、最小費用流という有名アル ゴリズムで最適解が求まる。  双子制約があるので最小費用流では解けず、最適 解を求めるのは難しい…？ 実はそんなことはない！ その前に… 7
8. 私の研究の紹介  2-SATの充足可能性は線形時間で判定できる。 充足不能な場合、出来るだけ沢山の節を充足する問題 （Max 2-SAT）はNP困難なので解くのが難しい…？ 1 ∨ 2 ∧ 1 ∨ 2 ∧ 1 ∨ 3 ∧ 2 ∨ 3 1 = false, 2 = true, 3 = true で充足可能 8
9. 私の研究の紹介  2-SATの充足可能性は線形時間で判定できる。  充足不能な場合、出来るだけ沢山の節を充足する問 題（Max 2-SAT）はNP困難なので解くのが難しい…？ 1 ∨ 2 ∧ 1 ∨ 2 ∧ 1 ∨ 3 ∧ 2 ∨ 3 1 = false, 2 = true, 3 = true で４つの節を充足 9 ∧ 1 ∨ 3
10. 私の研究の紹介  2-SATの充足可能性は線形時間で判定できる。  充足不能な場合、出来るだけ沢山の節を充足する問 題（Max 2-SAT）はNP困難なので解くのが難しい…？ 簡単 激ムズ? 2-SAT ( = 0) Max 2-SAT ( > 0) 10 充足されない 節の数 ここらへん（小さい)はまだ簡単なのでは？ 私の結果 (SODA 2013)： 任意の定数に対し、個以外充足可能かは線形時間で解ける アルゴリズム: LP緩和を最大流で解いて分枝限定法
11. 解法概略  双子制約がない場合は、最小費用流という有名アル ゴリズムで最適解が求まる。  双子制約があるので最小費用流では解けず、最適 解を求めるのは難しい…？ 私の解法： 緩和問題（双子無視）を最小費用流で解いて分枝限定法 11 双子制約の数 サンタ問題はここらへん（106人のうち双子わずか4,000人）なので簡単なのでは？ = 0は簡単 （最小費用流） > 0だと最小費用流で解けないが…
12. タイムライン 12 Dec13 Jan13 開始 終了 Dec14 最適解を達成し １位確定 (１位$8,000＋最長トップ賞$8,000で$16,000)/2日＝日給$8,000
13. タイムライン 13 Dec13 Jan13 開始 終了 Dec14 最適解を達成し １位確定 Dec23 最適解が続出したため ルール変更で第二ラウンド  入力が大きくなった：子供の幸福度の非零が107 → 108個に  三つ子が出現：双子4,000人 → 三つ子5,001人、双子40,000人  スコアが単純な線形和から σ , 3 + σ , 3に  賞金が分割：１位賞金$8,000を第一ラウンド$2,000+第二ラウ ンド$6,000に分割、最長トップ賞も持ち越し
14. タイムライン 14 Dec13 Jan13 開始 終了 Dec14 最適解を達成し １位確定 Dec23 最適解が続出したため ルール変更で第二ラウンド Dec26 再び最適解を達成 ところが… 僅かな差でKomaki君に先を越されたorz 私：Dec26 01:52:43、 Komaki君：Dec26 01:19:03 まだ終了まで半分以上あるため、最長トップ賞も逃し、 ３４分差で賞金$9,500を失う 敗因：人間性を捧げなかった 自前の最小費用流実装が遅かった
15. 解法詳細 1. 最小費用流 2. 分枝限定法 3. 三乗和の解き方（第二ラウンド） 4. 高速化 15
16. 最小費用流 入力： 問題： 16 −() +() • 有向グラフ = (, ) • 各辺の容量 (≥ 0)と重み minimize ෍ s.t. σ ∈−() − σ ∈+() = 0 (∀ ∈ ) 0 ≤ ≤ ∀ ∈ 入る量＝出る量 を通して最大 まで流せる 単位量あたりコスト が かかる < 0な辺もある （流すと得をする）
17. 最小費用流  様々な最適化問題が、最小費用流に帰着して効率 的に解ける（競プロでは頻出）  https://www.slideshare.net/wata_orz/ss-91375739  アルゴリズム  最短路反復法  コストスケーリング法  ライブラリ  LEMON: http://lemon.cs.elte.hu/trac/lemon  Google OR-Tools: https://developers.google.com/optimization/ 私は自前のコストスケーリング法実装を使用した 17
18. 最小費用流への帰着 18 1 1 0 0 0 0 1 1 3 0 0 4 1 2 0 2 容量2 容量1 容量1 コスト = −幸福度 −4 −1 −1 0 −3 −3 −4 0 → → → という閉路が プレゼント を子供 に渡すことに対応
19. 分枝限定法  解ける問題（e.g. 最小費用流）＋邪魔な制約（e.g. 双子制約） に対し、邪魔な制約を無視した緩和問題を考える。  緩和問題の解 ≥ 元の問題の解（最大化の場合）が成り立つ ので、探索の枝刈りに使える。 19 1. 緩和問題を解く 2. if 既に発見した解 ≥ 緩和解 then return 3. if 緩和解が緩和した制約を満たす then 解を更新 4. else 満たされていない制約を一つ選び、満たすよう に再帰的に分岐して探索する
20. 分岐の方法 異なるプレゼント, を受け取った双子を一組選び、プレゼント を渡す場合と、プレゼントを渡さない場合で分岐 20 1 2 −4 −1 −1 0 −3 −3 −4 0 1 2 −4 −1 −1 0 −3 −3 1 2 −1 0 −3 −3 −4 0 1を渡す 1を渡さない 1以外からの辺を消す 1からの辺を消す 双子制約が満たされていない
21. 三乗和の解き方  第二ラウンドでは、目的関数が幸福度の線形でなく、 σ , 3 + σ , 3となった  の非零が106個に対し、の非零が108個もあるの で、σ , の方が圧倒的に大きく出来る → を無視してのみを最大化すれば、ほぼ最適 21 これ以上の最適化はKaggleのスコアボードの有 効桁数を超え、「not an improvement」と言われ るが、ちゃんと最適化しないとダメだった 真の最適解は十分大きい数に対して、 + を最大化すれば得られる
22. 高速化１・２ 1. 双子の幸福度は、個別のものでなく、平均を用いる  同じ値にすることで、最小費用流が同じプレゼント を割り当てやすくなる 2. 重み0の辺は除去する  プレゼントが余った場合はナップサック問題を解い て詰め込む 22 4 0 1 4 1 3 0 3 2.5 2 2.5 2 1 3 3
23. 高速化３ 3. 分枝限定法において、分岐後の最小費用流の計算 は、増大路計算により( log )時間で出来る 23 1 2 a b c d −4 −1 −1 0 −3 −3 −4 0 1 2 a b c d 4 −1 1 0 3 −3 4 0 残余グラフ 使った辺の 向きと重みを反転 からへの増大路＝残余グラフでのからへのパス
24. 高速化３ 3. 分枝限定法において、分岐後の最小費用流の計算 は、増大路計算により( log )時間で出来る 24 1 2 a b c d −4 −1 −1 0 −3 −3 −4 0 1 2 a b c d −4 −1 −1 0 −3 −3 1以外からの辺を消して 最小費用流を計算 → 1 への最短増大路 （ → 2 → → 1） に沿って押し戻す 1 2 a b c d −4 −1 −1 0 −3 −3 −4 辺1bを使う 1 2 a b c d −4 −1 −1 0 −3 −3 −4 1以外からの使われ ていない辺を消す
25. 高速化４ 4. 分岐の方法は、（双子、プレゼント）を全通り試して 緩和解が（ソートして辞書順比較で）一番小さくなる ものを選ぶ。  緩和解が既に見つけた解以下なったら枝刈り出来るので、 探索の出来るだけ浅いところで緩和解を小さくしたい 既にスコア10の解を得ているときに、 双子にプレゼントを渡す→ 緩和解9 即座に枝刈りされる 双子にプレゼントを渡さない → 緩和解12 双子にプレゼントを渡す→ 緩和解11 双子にプレゼントを渡さない → 緩和解11 25
26. 高速化５ 5. 最適解で絶対に使われる・使われない辺を除去しグ ラフを小さくする  = 0 → 1 にした際の緩和解が、既知の解以下に なったら、 = 0で固定してよい  = 1 → 0 も同様 一回の判定に( log )かかるので、全部の辺を調べると 2 log 。 = 108なので無理 26
27. 高速化５  = 0 → 1にすると、最小費用流のコストは からへの最短増大路 + 増加する  = 1 → 0 にすると、最小費用流のコストは からへの最短増大路 − 増加する  １辺ごとに最短増大路を計算すると108回の最短路計算が必 要だが、 (プレゼント)は1000種類しかないので、1000回の最 短路計算で出来る（それでもまだ若干重いが） 27 からへ押し戻す からへ別ルートで流す
28. 高速化５ 双対変数（ポテンシャル）を用いると、一気に辺を削除 出来る（Reduced cost fixingと呼ばれるテク） 最小費用流の双対性 最小費用流が最適 ⇔ 残余グラフの全ての辺で ≤ + を満たすようなポテンシャル: → ℝが存在  からへの最短増大路の長さ ≥ − が成り立つ  先にこの下界で辺を減らしてから最短路計算をした 28 4 −1 1 0 3 −3 4 0 0 3 1 0 0 0 0 0 残余グラフ （使った辺の向き と重みを反転）
29. 実行時間など  全部通して1時間位  殆どの計算時間は一番最初の最小費用流計算  自前実装でなく、OR-Toolsとかの外部ライブラリを使えば、 だいぶ速くなるっぽい  あまりに遅いので、コンペ中は計算結果をファイルに保存 して、ソルバ改善→再実行時の再計算を無くした  が、のみ最適化から + 最適化に変えた際に計算し 直す必要が…→計算中にKomaki君が最適解達成orz  辺の削減効果  約108辺 → 約50万辺 29
30. 感想 30 全盛期のイチロー伝説： 全完は当たり前。一度のコンテストで二度全完することも。 サンタ以外のKaggleも参戦していきたい。 wata