今回は、データサイエンスグループ（いわゆるKaggler枠）のマネージャーである原田慧が担当します。私のバックグラウンドは数学で、博士号取得後、データ分析関連の仕事に従事してきました。データ分析コンペには2011年から取り組んでいますが、「Kaggle」ではなかなか良い成果が出せず、Kaggle Masterになったのは2017年になってからのことでした。その原動力はKaggleで毎年年末に開催される数理最適化のコンペティションです。今回はその数理最適化コンペ、いわゆる「サンタコンペ」について紹介します。
サンタコンペとは
サンタコンペという通称の由来は、毎年年末に開催され、お題がサンタクロースやトナカイにひも付いているためです。
通常のKaggleのコンペでは、与えられた人や商品に関する多数のデータに対して予測値を付与することになります。データは学習用データと評価用データに分かれ、学習用データには正解が与えられます。参加者は学習用データを使ってモデルを学習し、評価用データの予測値を提出します。
一方のサンタコンペでは、予測対象となるデータはなく、全てのデータとルールが与えられた上で、その中でなるべく最適に近い行動、状態を作って提出します。
通常のコンペとサンタコンペの違い
日頃のKaggleコンペとは全く違うサンタコンペですが、私はもともと数学の出身で、現実味がある問題を数字の羅列で捉えて計算するだけでも楽しく、また年末は日頃の忙しさから解放されてまとまった時間をかけて集中できるということもあって熱心に取り組んでいます。
年末年始に、ノートPCの発熱が高温になるほどの計算をさせながら初詣に行って、帰ってきて計算結果を確認したり、寒い中チームメイトとコワーキングスペースに集まったり、楽しい思い出があります。
これまでのサンタコンペ
これまで私が参加した過去4回分についてお話しします。
2015～2016年のコンペは、「巡回セールスマン問題」の派生系でした。より正確に言えば、「multiple traveling repairman problem」という問題に近かったと思います。具体的には、北極から大量のサンタが世界各地にプレゼントを運んで帰っていくとき、トナカイの疲労がなるべく小さくなるような配送計画を立てるという問題でした。
いかがでしょうか？ 大量のサンタとか何を言っているのだと思うかもしれませんが、何だか楽しそうに見えてきませんか？ それぞれのためにサンタとトナカイを行かせるというのも立派な解です。無駄が多いので近い配送先をくっつけて同じソリで運べば、少し効率が良くなります。でもやり過ぎると、ソリが重くなって一部のトナカイの疲労が増え過ぎてしまいます。こんな風にバランスを取りながら、限られた時間の中で全体最適な解を探していく問題です。
当時は最適化についてほとんど何も分からないながら、チームメンバーの解法を組み合わせると少しずつ順位が上がっていき、とても楽しく銀メダルを獲得しました。
2016～2017年はいつもと異なり、ランダム性のあるコンペでした。さまざまな重さのプレゼントを、なるべくたくさん袋に詰める。ただし一定の重さを越えた袋は重量がゼロになるというものでした。与えられるプレゼントの重さはランダム（正確に言うと、ある確率分布に従って生成された値であることだけ与えられる）なので、一見すると運の良い人が有利に見えるのですが、実はそうではなく、リーダーボードから得られる情報を最大限に活用することがポイントでした。
チーム内でいろいろな仮説を立てては検証し、期限までに判断、実践、投稿して、その結果を解釈するといった頭の休まる暇のないコンペでした。最後の数分まで順位が変動しましたが、締め切り時点で11位（最終的には失格が出て10位）に入って、ギリギリで金メダルを獲得、念願のKaggle Masterになることができました。暫定結果が出る午前9時に混雑した電車の中で一人静かにガッツポーズしました。
2017～2018年のコンペは、プレゼントと子どもたちのマッチング問題でした。子どもたちは欲しいプレゼントがあり、サンタ側にもプレゼントごとに渡したい子どもたちがいて、双方の満足度の合計を最大化するという問題です。
ここまでなら典型的なマッチング問題ですが、追加で双子には同じプレゼントを渡さなければならないという制約があります。この年は、当初の問題が簡単過ぎて、市販のソルバ（分析ツール）などで本当の最適値が出てしまうという事件がありました。
こうなると早く提出した人が上位になるルールです。私も最適値を出しましたが、早さの関係で銀メダル圏の1番上でした。期間を1カ月近く残したまま、1位はもちろん、全ての賞金の行方、金メダル獲得者も決まって動かないという異常事態です。議論の末、問題の複雑さを増す形で再開となりました。
再開された問題は、市販のソルバで直ちに解けるものではなくなったのですが、自分で問題を置き換えられるような人にはあまり影響がない範囲でした。やはり数日で最適値を出す参加者が出てきて、スピード勝負となりました。私は再開を見越して復習していたかいあって、また数学の応用で効率良く最適化をすることができたこともあって、3位に入り賞金を獲得しました。
2018～2019年のコンペは巡回セールスマン問題に特殊なペナルティが追加されたものでした。約20万個の都市が与えられ、それらを巡回させる経路のうち10、20、30…番目の道は10％のペナルティが追加、ただし出発側の都市の番号が素数であれば免除、という問題です。都市の座標は平面座標で与えられ、うまく経路を描くとトナカイの絵ができるようになっています。
最近のサンタコンペであるこの年は、巡回セールスマン問題の強力なソルバの使い方が公開されたと思ったら、今度はそのソルバの作者でもあるトップ研究者が参戦するというハイレベルな戦いでした。
コンペ後半には掲示板で有力な解法がシェアされてしまい、一部の上位層を除いては、いかに掲示板の情報にキャッチアップして改良を加えるか、という苦しい戦いとなりました。私はラストスパートでなんとか銀メダルを獲得しましたが、ソロで参加して金メダルを獲得するという当初の目標からすると悔しい結果となりました。
