Kaggleコンペティション「Santa 2024 - The Perplexity Permutation Puzzle」において、DeNAのデータサイエンティストである長沢の所属チームが1514チーム中1位に入り、金メダルと賞金を獲得しました。

SantaはKaggleでは年末年始恒例のコンペティションで、典型的な機械学習ではなく、巡回セールスマン問題やスケジューリング問題など、最適化の有名問題をアレンジしたものが出題されます。今年の「The Perplexity Permutation Puzzle」では、クリスマス関連の物語の単語がシャッフルされた状態で提示され、それらの並び順を変えることで文全体のパープレキシティを最小化するという課題が出題されました。パープレキシティはテキストの文脈理解に長けた大規模言語モデル「Gemma 2 9B」によって計算され、参加者は単語列の並び替え方を工夫してスコアの改善に挑みました。

長沢のチームは、反復局所探索法(ILS)の枠組みを用い、単語列の近傍を深さ優先探索しながら貪欲に解を改善し、局所解に陥った場合には「kick (perturbation)」によって新たな探索を行う、というプロセスを繰り返しました。さらに、Gemmaによる正確なスコア評価が計算負荷の高い処理であることに対しては、軽量なニューラルネットワークを用いてスコアが悪化しそうな近傍候補を事前にスクリーニングし、計算効率を大幅に改善するアプローチを取りました。解法の詳細はこちらをご覧ください。

長沢コメント「スコア計算がブラックボックスに近く工夫の余地が一見少ないようでしたが、その中でも有効な方針を見つけ出し、良い結果に繋げられたことを嬉しく思います。」

DeNAとその関連企業を含めたDeNA Galaxyでは、最適化などの機械学習から見た周辺技術を組み合わせて活用することも多く、技術の幅を広げることにも力を入れています。