Kaggleスコアアップセミナー～数理最適化コンテスト Santa 編（2023/06/02）
10.4K Views
June 07, 23
スライド概要
Kaggleの数理最適化コンテスト「Santa 2022」に当社エンジニアが参加し、銀メダル獲得の結果、Kaggle Competitions Master の称号を獲得しました。
本ウェビナーでは、機械学習に限らないKaggleのコンペ問題として数理最適化があることについて紹介し、Kaggle特有の問題解決手法と、高速化手法を数理最適化にどう組み合せたかについて解説します。
当社技術ブログには書ききれなかった、改善手法の詳細についても説明します。
数理最適化を扱っている、企業の研究開発部門所属のエンジニア、大学研究室所属の学生にオススメの内容となっております。
・当社技術ブログ 記事： https://proc-cpuinfo.fixstars.com/2023/04/kaggle-santa-2022/
・フィックスターズのAI・深層学習向け技術支援： https://www.fixstars.com/ja/services/ai
フィックスターズは、コンピュータの性能を最大限に引き出すソフトウェア開発のスペシャリストです。車載、産業機器、金融、医療など、幅広い分野での開発経験があります。また、ディープラーニングや機械学習などの最先端技術にも力を入れています。 並列化や最適化技術を駆使して、マルチコアCPU、GPU、FPGA、量子アニーリングマシンなど、さまざまなハードウェアでソフトウェアを高速化するサービスを提供しています。さらに、長年の経験から培ったハードウェアの知識と最適化ノウハウを活かし、高精度で高性能なアルゴリズムの開発も行っています。 ・開催セミナー一覧：https://www.fixstars.com/ja/seminar ・技術ブログ ：https://proc-cpuinfo.fixstars.com/
関連スライド
各ページのテキスト
Kaggleスコアアップセミナー 数理最適化コンペ – Santa 2022 編 Copyright© Fixstars Group
本セミナーの位置づけ ● 当社エンジニアが、銀メダルと Kaggle Competitions Master の称号を獲得 ● Kaggle スコアアップセミナー：スコアアップに向けたヒントをお届け -- 過去開催 -画像系コンペ DFL- Bundesliga Data Shootout編 ● 本セミナーの題材：数理最適化コンペ「Santa 2022」 ● 概要・解法の解説と、ブログに書ききれなかった改善手法の詳細を説明 ● こんな方にお勧め ● 研究や開発で、数理最適化を扱っている方 ● 今後 Kaggle に挑戦し、スコアを上げていきたいと考えている方 Copyright© Fixstars Group 2
発表者紹介 冨田 明彦 飯塚 康太 ソリューションカンパニー 営業企画 ソリューション第二事業部 シニアエンジニア 2008年に入社。金融、医療業界において、 ソフトウェア高速化業務に携わる。その後、 新規事業企画、半導体業界の事業を担当し、 現職。 2019年入社。車載向け深層学習モデル開発に おけるMLOps、とくに各モデルのデプロイを 簡略化するツールの開発を担当している。 Kaggle Competitions Master Copyright© Fixstars Group 3
本日のAgenda ● フィックスターズのご紹介 ● コンペ概要 ● 解法紹介 ● まとめ ● Q&A / 告知 Copyright© Fixstars Group 4
フィックスターズの ご紹介 Copyright© Fixstars Group 5
フィックスターズの強み コンピュータの性能を最大限に引き出す、ソフトウェア高速化のエキスパート集団 ハードウェアの知見 アルゴリズム実装力 各産業・研究分野の知見 目的の製品に最適なハードウェアを見抜き、 その性能をフル活用するソフトウェアを開 発します。 ハードウェアの特徴と製品要求仕様に合わ せて、アルゴリズムを改良して高速化を実 現します。 開発したい製品に使える技術を見抜き、実 際に動作する実装までトータルにサポート します。 Copyright© Fixstars Group 6
サービス概要 お客様専任のエンジニアが直接ヒアリングを行い、高速化を実現するために乗り越えるべき 課題や問題を明確にしていきます。 高速化のワークフロー お客様 オリジナルソースコードのご提供 高速化したコード コンサルティング 高速化 サポート 先行技術調査 アルゴリズムの改良・開発 レポートやコードへのQ&A 性能評価・ボトルネックの特定 ハードウェアへの最適化 実製品への組込み支援 レポート作成 Copyright© Fixstars Group 7
サービス提供分野 半導体 産業機器 金融 自動車 ● NAND型フラッシュメモリ向けフ ァームウェア開発 ● 次世代AIチップの開発環境基盤 生命科学 ● Smart Factory実現への支援 ● マシンビジョンシステムの高速化 ● 自動運転の高性能化、実用化 ● ゲノム解析の高速化 ● 次世代パーソナルモビリティの 研究開発 ● 医用画像処理の高速化 Copyright© Fixstars Group ● デリバティブシステムの高速化 ● HFT(アルゴリズムトレード)の高速化 ● AI画像診断システムの研究開発 8
サービス領域 様々な領域でソフトウェア高速化サービスを提供しています。大量データの高速処理は、 お客様の製品競争力の源泉となっています。 組込み高速化 GPU向け高速化 AI・深層学習 画像処理・ アルゴリズム開発 FPGAを活用した システム開発 分散並列システム開発 量子コンピューティング 自動車向け フラッシュメモリ向け ソフトウェア開発 ファームウェア開発 Copyright© Fixstars Group 9
量子コンピューティング活用支援 多様なハードウェアでのソフトウェア高速化サービスに加え、 量子コンピュータ活用支援とシステム開発を提供しています。 お客様の課題 ご支援内容 量子コンピューティングが課題の解決に役立 つか、確信が持てない セミナー・トレーニング 量子コンピュータの研究動向や活用事例、実際の利用方法等 量子コンピューティングの検討をどう進めて いったら良いかわからない コンサルティング セットアップ支援、処理の分割や変換等のコンサル 作りたいアプリケーションがあるが、開発が 難しい クラウド実行環境のご提供 クラウド経由での量子コンピュータ利用サービスを提供 ソフトウェア高速化・開発支援サービス 量子コンピュータを組み合わせてシステムの高速化を実現 Copyright© Fixstars Group 10
Santa2022コンペ 解法紹介 Copyright© Fixstars Group 11
Santa2022コンペ解法紹介 ● 本発表ではKaggleコンペ Santa 2022 - The Christmas Card Conundrum の19位 （上位3％）解法を紹介します ● 弊社techブログやKaggle discussionにも解法を投稿していますが、単なる手法の説明だけ でなく各手法を採用するに至った背景や理由についても合わせて解説します ○ tech blog: https://proc-cpuinfo.fixstars.com/2023/04/kaggle-santa-2022/ ○ Kaggle notebook: https://www.kaggle.com/code/kotaiizuka/standard-configuration-below-74300 Copyright© Fixstars Group 12
アウトライン ● コンペ概要 ○ 問題設定 ○ 評価方法 ● 解法紹介 ○ ベースライン ○ 改善手法 ○ 上位解法 ● まとめ ○ コンペの取り組み方 Copyright© Fixstars Group 13
コンペ概要 Copyright© Fixstars Group 14
コンペ概要 ● タスク ○ 与えられた画像のすべての頂点を通る経路で、条件を満たす最もコストの小さいもの を求める 巡回セールスマン問題の類題 ● タイムライン (日本時間) ○ 2022/12/01: コンペ開始 ○ 2023/01/18: コンペ終了 ■ Kaggleでは標準的だがヒューリスティックコンテストとしては長い Copyright© Fixstars Group 15
動画: https://www.kaggle.com/code/kotaiizuka/santa2022-solutions-visualizer#sample-submission Copyright© Fixstars Group 16
制約条件(1/3)：アームの長さ ● 頂点だけでなくアーム全体の 配置を指定する必要がある ○ 端点は (0,0) ○ アームの長さは [64, 32, 16, 8, 4, 2, 1, 1] L∞ノルム 𝐿∞ 𝑥, 𝑦 = max( 𝑥 , 𝑦 ) Copyright© Fixstars Group 17
制約条件(2/3)：アームの移動距離 ● アームは1回の移動で各部分を最大で1動かすことができる ○ 例） OK NG Copyright© Fixstars Group NG 18
制約条件(2/3)：アームの移動距離 ● アームは1回の移動で各部分を最大で1動かすことができる ○ 例） OK OK Copyright© Fixstars Group NG 19
制約条件(2/3)：アームの移動距離 ● アームは1回の移動で各部分を最大で1動かすことができる ○ 問題） ① ② Copyright© Fixstars Group ③ 20
制約条件(2/3)：アームの移動距離 ● アームは1回の移動で各部分を最大で1動かすことができる ○ 解答） ① ③ ② OK NG OK Copyright© Fixstars Group 21
制約条件(3/3)：端点 ● アームの始点と終点は 右図の位置 ○ 右側 (x=64,y=0) に進んだあと 左側へ (x=-32,y=0), (x=-16,y=0), … と進んで (0,0) を指している状態 Copyright© Fixstars Group 22
評価方法 ● 移動コスト：1回の移動でアームの 𝑛 箇所が動くとき 𝑛 のコスト ○ 最大で 8 箇所動くので 8 のコストがかかる ● 色変化コスト：端点のRGB値（0～1）の差の合計 𝑑 に対して 3𝑑 のコスト ○ 最大で (0,0,0) から (1,1,1) に変わるので 9 のコストがかかる これらのコストの合計ができる限り小さくなるパスを求めたい ● 入力される画像は public LB と private LB で同じものを使う ○ 通常の機械学習コンペとは異なり shake up を考える必要がない Copyright© Fixstars Group 23
解法紹介 Copyright© Fixstars Group 24
解法紹介 ● ベースラインから改善を重ねてスコアを向上させた 最終1位とのスコア差 ベースライン 標準構成 100分割 4分割 手動置き換え 0.1 1 10 100 1000 10000 100000 submit bronze Copyright© Fixstars Group silver gold 25
ベースライン手法 ● コストをかければ任意の2点間を移動できるので、それをすべての頂点で くりかえす方法 ○ 始点と終点は (0, 0) なので、最初に左下へ移動してから上下に走査して、 最後に右上から中央に戻るパス → 次ページに動画 ○ notebook: https://www.kaggle.com/code/ryanholbrook/getting-started-with-santa2022/notebook ○ スコア: 166305.28453774838 Copyright© Fixstars Group 26
動画: https://www.kaggle.com/code/kotaiizuka/santa2022-solutions-visualizer#sample-submission Copyright© Fixstars Group 27
標準構成 ● 根元のアームを縦方向のみ、それ以外を横方向のみに移動させることにより 4分割された各領域は上下左右どの方向にも自由に動くことができる ○ これによって、アームの構成をまったく考えることなく、単にパスだけ構成すればよくなる ○ ベースラインと同様に、始点と終点のまわりは特別扱いが必要 → 次ページに動画 ○ discussion: https://www.kaggle.com/competitions/santa-2022/discussion/376306 ○ スコア: 81147.9279939281 ■ ベースラインに比べて理論値との差を1桁程度改善 Copyright© Fixstars Group 28
動画: https://www.kaggle.com/code/kotaiizuka/santa2022-solutions-visualizer#standard-configuration Copyright© Fixstars Group 29
100分割 ● 標準構成の4分割をベースにそれぞれのパスを最適化したいが、128x128 の 領域全体を一度に処理できるだろうか？ ○ 1.6万頂点の巡回セールスマン問題については、以前の Santa コンペでも使われている LKH-3 ソルバで対応できる ■ ○ http://akira.ruc.dk/~keld/research/LKH-3/ ただし、今回は離れた場所に移動できないという制約があり、対応が必要 ■ もっとも単純な対応方法として、上下左右のマスを除くすべての頂点への重みを 無限大としてコスト行列を作成することが考えられる Copyright© Fixstars Group 30
100分割 ● 単純なコスト行列の表現では、およそ1000頂点を超えると解が見つからない というエラーが返される ○ 原因は後で考察することにして、各領域が1000頂点以下になるように領域を細分すれば 問題が解けることが分かった ■ 4分割したそれぞれの領域をさらに25分割して、最適なパスを計算してつなぎ合わせる 実装をした → 次ページに動画 ○ スコア: 78570.1203104202 ■ 標準構成から2500点程度の改善 Copyright© Fixstars Group 31
動画: https://www.kaggle.com/code/kotaiizuka/santa2022-solutions-visualizer#divided-into-100-parts Copyright© Fixstars Group 32
4分割 ● 単純な実装で1000頂点を超えるとエラーになる問題を考察した ○ LKH-3 のオプションによるもの？ → 実行時間は変わるが解が見つかるかは変化しない ○ 近傍の設定が上下左右のみなのが良くない？ → 3x5の領域を近傍とみなすことができて、 それを適用すると1.6万頂点でも解けるようになった ■ ○ 近傍（今回で言えば接続できる頂点候補）が少なすぎると最適化に失敗することがある notebook: https://www.kaggle.com/code/kotaiizuka/standard-configuration-below74300 ○ スコア: 74253.5374372423 ■ 100分割に比べて4300点程度の改善で、最終1位から180点差程度 ■ 実行時間は4領域を合計して30分程度 ■ ここまでの改善で銀メダル圏内に入った Copyright© Fixstars Group 33
4分割 ● 標準構成で近傍の数が増やせることについて ○ ルールから「アームの各部分を一度に1ずつ動かすことができる」ので、縦方向に動く 根元のアームと、横方向に動く2番目以降のアームを同時に動かすことで斜めに移動ができる ○ さらに、xの値が偶数のときは2番目のアーム、奇数のときは3番目以降のアームを動かす というルールを追加すれば一度にまとめて横に2マスまで動ける 右上の方向に移動したい ときは、最初のアームで 縦方向に移動する Copyright© Fixstars Group 34
4分割 ● 標準構成で近傍の数が増やせることについて ○ ルールから「アームの各部分を一度に1ずつ動かすことができる」ので、縦方向に動く 根元のアームと、横方向に動く2番目以降のアームを同時に動かすことで斜めに移動ができる ○ さらに、xの値が偶数のときは2番目のアーム、奇数のときは3番目以降のアームを動かす というルールを追加すれば一度にまとめて横に2マスまで動ける 続いて2番目のアームを 横方向に移動する Copyright© Fixstars Group 35
4分割 ● 標準構成で近傍の数が増やせることについて ○ ルールから「アームの各部分を一度に1ずつ動かすことができる」ので、縦方向に動く 根元のアームと、横方向に動く2番目以降のアームを同時に動かすことで斜めに移動ができる ○ さらに、xの値が偶数のときは2番目のアーム、奇数のときは3番目以降のアームを動かす というルールを追加すれば一度にまとめて横に2マスまで動ける 最後に3番目のアームを 横方向に移動すると移動 できる。別のアームを 使っているので1回で 移動可能である Copyright© Fixstars Group 36
動画: https://www.kaggle.com/code/kotaiizuka/santa2022-solutions-visualizer#divided-into-4-parts Copyright© Fixstars Group 37
手動置き換え ● 4分割の構成でいくつか手掛かりを得た ① 少なくとも左右方向の自由度はもっと高くできる。たとえば、7本のパーツすべてで左右に 移動できる余力がある状態（たとえばすべて上方向）なら最大で一度に7マス横に移動 できる Copyright© Fixstars Group 38
手動置き換え ● 4分割の構成でいくつか手掛かりを得た ② 大きく移動するのが効果があるような場面は少ない、連続して現れることもほとんどない ▲4分割で最適化した結果。緑色・黄色の部分が高コスト Copyright© Fixstars Group 39
手動置き換え ● 4分割の構成でいくつか手掛かりを得た ③ 標準構成のように縦に1マスしか移動できないのは制約としてかなり大きい。横へ移動 できるマスの数を減らすことで縦にも横にも複数マス移動できるようになる ▲4分割と、近傍がより大きいパターンで最適化した結果。緑色・黄色の部分が高コスト Copyright© Fixstars Group 40
手動置き換え ● 4分割の構成でいくつか手掛かりを得た ④ 分割した部分以外に直線的なパターンは見られない。100分割から4分割にしたときのように 制約を減らして広い範囲を最適化するほうがスコアが良くなりそう → 分割せずに全体（6.5万頂点）を一度に最適化する方法を考える必要があるが、 標準構成のような全体で整合するアームの構成はなさそう → まずはパスに絞って最適化できるようにしたい Copyright© Fixstars Group 41
手動置き換え ● LKH-3 を改造して 6.5万頂点のパスを一度に構成できるようにした ○ 今まではコスト行列をテキストファイルとして入力していたが、全頂点のコスト行列は 大きすぎて書ききれないので、コスト関数を LKH-3 の内部に実装する形にした ○ 9マス以上離れたところには絶対に移動できないのでコスト無限大とし、一度に複数マス 動かすのはなるべく避けたいので与えられたコストにペナルティを追加した ■ 位置のコストは実際にアームが構成できるかにかかわらず最小値（ 𝑛 マス移動する なら 𝑛 ）として計算した Copyright© Fixstars Group 42
手動置き換え ● このパスに対応するアームを構成する方法を考えた ○ 各アームの状態に対して、その状態がどれくらい他の状態に遷移しやすいかを表すスコアを 導入した ■ アームの各部分は上下左右のうち2方向にしか移動できないので、8か所でそれぞれ バランスよく割り振られているほうが良い ■ アームの各部分が斜め45°の方向に向いている場合は縦横どちらにも動けるので、 なるべくこの状態を保ちたい ○ 2つのスコアは相反することもあるので手動で重みを調整して、評価対象のスコアとした Copyright© Fixstars Group 43
手動置き換え ● このパスに対応するアームを構成する方法を考えた ○ このスコアが高いほうに貪欲に遷移していって、行き詰まったら原因を考えることにした ■ 一つの方向にずっと移動する必要があって余力がなくなった場合は、少し戻ってから 2つのスコアの重みを変えて再び遷移させると先に進めた ■ 原点の周辺やフチの部分で詰まった場合は、パスそのものが良くなかったので コスト関数に制約を追加して LKH-3 を再実行した ● 数回試行して、パス全体に対応するアームが構成できた ○ スコア: 74087.0331328868 ■ 最終1位のスコアから 11.3 点差まで近づけた Copyright© Fixstars Group 44
動画: https://www.kaggle.com/code/kotaiizuka/santa2022-solutions-visualizer#my-final-submission Copyright© Fixstars Group 45
1位～4位の解法 ● 1位から4位はすべて同一スコアで、遺伝的アルゴリズム GA-EAX を利用 した探索を行っている ○ パスに対応するアームの構成の部分で、実際は複数頂点に依存するような複雑な制約を書く 必要があった。そのこと自体は把握していたが、私が採用した LKH-3 ではそれを直接実装 することができず、類似のやや厳しい条件を書かざるを得なかった。その分だけ最適化が 弱くなってしまった Copyright© Fixstars Group 46
まとめ Copyright© Fixstars Group 47
数理最適化コンペの取り組み方 1. （このタスクに限らず）tutorial notebook や discussion をよく読んで、 問題についてなるべく詳細に理解する ○ 今まで取り組んだことがある問題のどれに近いか？ 巡回セールスマン問題 ○ その問題との差分は？どのあたりが難しい要因になっている？ アームの構成 ○ 評価関数の特徴は？ 色変化のコストが重要、private LB が無い ○ tutorial の解法によるスコアはどれくらいか？ 16万点程度 ○ 見込める改善幅は？ すべてのピクセルの移動コストがあるので6.5万点を下回らない Copyright© Fixstars Group 48
数理最適化コンペの取り組み方 2. 簡単な場合に絞って問題が解けるか確認する ○ 問題の規模が小さい場合 数理最適化では全探索が効くことが多い ○ 制約条件をいくつか除いた場合 巡回セールスマン問題のソルバを使えば解ける ○ 制約条件をより強くした場合 標準構成にもとづいた簡易な解法があった 3. 条件を元に戻しても同じように適用できそうな方法を選択する ○ 巡回セールスマン問題をベースに分割統治する方法（100分割、4分割） ○ 標準構成のようにパスとアームを別々に構成する方法（手動置き換え） ○ アームの制約条件にあった適切なアルゴリズムを選択する（1位～4位の解法） Copyright© Fixstars Group 49
まとめ ● Kaggle Santaコンペを題材に、数理最適化コンペの解き方について 説明しました ● Kaggle には教師あり深層学習のコンペが多いですが、数理最適化や 強化学習などが題材のコンペもあります。これらは手法や評価がブラック ボックスになりにくく、考察したことが評価につながる可能性が比較的 高いので、メダルがほしいという方はぜひ取り組んでみてください！ Copyright© Fixstars Group 50
補足説明：LKH-3 のアルゴリズム 1. 巡回路Cから頂点pを選び、そこから出る辺pqを取り除く 2. 頂点qに近い頂点rを選び辺qrをつなぐ s 3. 頂点rから出る辺rsを取り除き、辺psをつないで巡回路を作る q r p 4. この巡回路のコストを計算する a. もし頂点q,r,sをうまく選んでコストが下がるなら、入れ替えたものを 新しい巡回路Cとして、頂点pをランダムに選びなおして1.に戻る b. コストが下がらない場合は、今まで作った各巡回路に対して、頂点sを 新しい頂点pとして1.に戻る Copyright© Fixstars Group s q p r 51
補足説明：GA-EAX のアルゴリズム 1. 巡回路 C, D を重ね合わせた多重グラフ G を作成する 2. G から C, D の辺を両方含むループ L を抜き出す 3. C から L∧C を取り除き L∧D を加える 4. （必要なら後処理を行って）巡回路 E を得る 5. C, D, E のうち良いものを選んで 1. から繰り返す C D G L Copyright© Fixstars Group C E 52
Thank you! お問い合わせ窓口 : [email protected] Copyright© Fixstars Group 53