Santaコンペ + 焼きなまし法入門

ラクスパ鶴見Kaggler会のLT発表資料です。

Transcript

1. Santaコンペ + 焼きなまし法入門 ラクスパ鶴見 Kaggler会 Ryota
2. Kaggle Winner Presentation Template • Ryota(神野 亮太) • 労働始めました • 大学卒業後からこれまで ◦ 業務委託しながらKaggleをする生活 2023/42025/3 ◦ 就活, インターン, 旅行, etc. 2025/42025/9 ◦ 労働 2025/10現在) 2 自己紹介
3. Kaggle Winner Presentation Template Santaコンペに入門してみませんか？ • 焼きなまし法入門 • Santa2024の概要 + 自身の解法 3 今日話すこと ヒューリスティック未経験でも意外といけるかも？
4. Kaggle Winner Presentation Template Santaコンペ • 毎年クリスマスシーズンに開かれるヒューリスティックコ ンペ ヒューリスティックとは？ • 最適化問題を解くための手法 • 最適解ではないが, “十分に良いˮ解を現実的な計算量 で得るための近似手法 • 厳密解を現実的な計算量で求めることができない場合 に使用する 4 Santaコンペ概要
5. Kaggle Winner Presentation Template メリット • Shakeが存在しない • ヒューリスティックを学べる • (ハイスコア公開Notebookの存在) デメリット • AHC勢が強すぎる • MLコンペではない 5 Santaコンペ メリデメ AHC勢めっちゃ強い...
6. Kaggle Winner Presentation Template • ヒューリスティック未経験 + 2,3週間参加 • 巨人の肩(公開Notebook, Discussion)に乗っかり ながらも金メダル獲得 • (少なくとも2024年は) 焼きなまし法を理解しておけ ば戦えた 6 Santaコンペ 2024 shakeがないことで心の平穏が保たれる
7. Kaggle Winner Presentation Template • 焼きなまし法 + その派生手法しか知りません • 焼きなまし法が使える年限定の Santaコンペ入門資 料だと思ってもらえれば幸いです 7 お断り ちなみに2025年も焼きなまし法らしいですよ👀
8. Kaggle Winner Presentation Template 局所探索法 下記のような手法の総称 (焼きなまし法もここに含まれる ) 1. 初期解(暫定的にベストな解 , ランダム解)を用意する 2. その解の近傍解を作成する 3. 近傍解のスコアが条件を満たせば , その解に遷移する 4. 23を繰り返す 近傍解の例 • 巡回セールスマン問題の経路を 2辺入れ替える 8 焼きなまし法とは https://orsj.org/wp-content/corsj/or52-9/or52_9_538.pdf
9. Kaggle Winner Presentation Template 山登り法 Hill Climbing) • 最もベーシックな局所探索法 • 近傍解のスコアが改善した場合のみ遷移を許す • 局所最適解にハマると抜け出せない 9 焼きなまし法とは https://speakerdeck.com/umepon/local-search-and-metaheu ristics-for-combinatorial-optimization-problems?slide=9
10. Kaggle Winner Presentation Template 10 焼きなまし法とは 焼きなまし法 Simulated Annealing) • 山登り法を拡張した手法 • 近傍解のスコアが改善しなかった場合でも一定確率で遷移する • 局所最適解にハマりづらい 遷移確率 (※ 上記は最大化問題の場合, 最小化問題の場合は分子がpre_score - new_scoreとなる) • スコアが改善する場合 , pは1となり必ず遷移する • スコアが悪化した場合 , パラメータT温度)に依存して一定確率で遷移する • Tが大きいほど遷移する確率が高くなる
11. Kaggle Winner Presentation Template 11 焼きなまし法とは 冷却スケジューリング • 焼きなまし法では探索が進むにつれ , 温度Tを小さな値にしていく • どのようにTを下げていくかを冷却スケジューリングという 代表的な冷却スケジューリング • 線形冷却(→ Santa2024で自分が使用したのはこれ ) • 幾何(指数)冷却
12. Kaggle Winner Presentation Template 12 焼きなまし法 : 疑似コード https://www.kaggle.com/code/utm529fg/eng-tutorial-5-simulated-annealing 初期解の作成 探索イテレーションを回す 近傍解の生成と評価 遷移確率の算出 遷移確率に基づき近傍解へ遷移 温度の更新
13. Kaggle Winner Presentation Template 概要 • 単語列が6つ与えられる • 単語数 : 10, 20, 20, 30, 50, 100 • 各単語列のˮ最適ˮな並びを見つける ◦ 100!  9.33  10^157 • LLMGemma 2 9Bに単語列を入力したときの Perplexityを最小化する並びを最適とする Perplexity • LLMが最も高い確率を与える単語列を作れば良い 13 Santa 2024 : 概要 クリスマスっぽいワードがいっぱい 文章としてのつながりはなさそう
14. Kaggle Winner Presentation Template 14 Santa 2024 : 参加時点の状況 • 1,2,3番目のsampleは最適解であろうとされる解が公開されていた ◦ 1番目は全探索ができる 10!3,628,800ため厳密解 ◦ → 解くべきsampleは4,5,6のみ • 4,5,6番目のsampleも上位陣のDiscussionにより事実上の最適解のスコアが判明していた ◦ → (駆け引きである可能性はありつつ ...) どのsampleをどこまで改善するべきかわかっている • 単語列をアルファベット順に sortするだけのアプローチが結構いいスコアが出る ◦ → なんとなくの改善の方向性がわかる • ハイスコアNotebookも公開されている ◦ LB上)最適解 = 246.81784 ◦ 公開NB ≒ 250 ◦ sort ≒ 280 ◦ → 良い初期解が与えられている
15. Kaggle Winner Presentation Template 改善方針 • 公開NB同様に焼きなまし法を使用 • 筋の良い近傍解の作成 • 局所最適解に陥らないための sampleごとの工夫 • 冷却スケジューリングは公開 NBで使用されていた線形冷却をそのまま使用 15 Santa 2024 : 自分の解法11th place solution)
16. Kaggle Winner Presentation Template 筋の良い近傍解とは？ • 近い解同士の目的関数の値 (スコア)が近いほど良い • 解が近いとは, ある解から近傍解まで少ない近傍遷移で到達できること (と理解している) • つまり, 近傍遷移毎にスコアがブレるような近傍遷移は良くない 16 Santa 2024 : 自分の解法11th place solution)
17. Kaggle Winner Presentation Template 公開NBで主に採用されていた近傍遷移 • random swap : ランダムに単語ペアを選択し , 入れ替え • partial permutation : 部分単語列の全探索 17 Santa 2024 : 自分の解法11th place solution) 自分が採用した近傍遷移 • random insert : ランダムに単語を選択し , ランダムな位置に挿入 • distance-based probabilistic insert : ランダムに単語を選択し , 距離が近い位置ほど高い確率で挿入 • variable-length random insert : ランダムな部分単語列を選択し , ランダムな位置に挿入 • alphabetical insert : ランダムに単語を選択し , アルファベットが同じ単語のいずれかの前後に挿入 • partial permutation : 部分単語列の前探索 → 上記を確率的に組み合わせる swapをinsertに変えるのが重要だった
18. Kaggle Winner Presentation Template なぜswapよりもinsertの方が良かったのか • swap ◦ A, B, C, D, E → A, D, C, B, E ◦ 隣接する単語ペアを全て破壊 • insert ◦ A, B, C, D, E → A, C, D, B, E ◦ 隣接する単語ペアのうち CDは保存されている 元の単語列をなるべく保存した方がスコアの変化が少なく , この問題における筋の良い近傍遷移となる 18 Santa 2024 : 自分の解法11th place solution)
19. Kaggle Winner Presentation Template 局所最適解に陥らないための工夫 [sample 4 • 先頭単語の固定 ◦ “sleighˮという単語が先頭の文字列がスコアが良くなりやすかった (局所最適解) ◦ 先頭単語を固定して探索を行うことで局所最適解を脱出 (固定する先頭単語は全探索 ) ◦ 結果的に, “magiˮという単語を先頭に置くのが良かった [sample 6 • 名詞のアルファベットブロックの数を探索する ◦ sample 6のˮ良いˮ解の形状 ▪ [冠詞, 前置詞, 代名詞] + [名詞のアルファベット順 ] x N ◦ Nの数を探索するN1,2,3,4 ▪ N2が最もスコアが良かった 19 Santa 2024 : 自分の解法11th place solution)
20. Kaggle Winner Presentation Template まとめ • 筋の良い近傍解の生成が一番重要 (これだけで大体30位) • 冷却スケジューリングも大事らしいが今回は特に考える必要はなかった • 最後の一押しは, 局所最適解から抜け出すための問題固有の工夫 20 Santa 2024 : 自分の解法11th place solution)
21. Kaggle Winner Presentation Template すみません、まとめていません！！！ 気になった方はDiscussionを読んでください！！！ 21 Santa 2024 : 上位解法 URL : https://www.kaggle.com/competitions/santa-2024/discussion?sort=votes
22. Kaggle Winner Presentation Template 22 終わりに
23. Kaggle Winner Presentation Template 23