TopCoder Marathon Match（機械学習・データマイニングもあるよ）

Machine Learning Advent Calendar 12/16の記事です。主催のnaoya_tさん、有難うございます。今回は、機械学習やデータマイニングを実際楽しみながら使えるTopCoder Marathon Matchの紹介をしようと思います。

TopCoder Marathon Matchとは

TopCoder (http://community.topcoder.com/tc) は、 インターネット上で、世界の人とプログラミングなどで競い合うコミュニティです。TopCoderというと、75分間でアルゴリズムに関するプログラミングを作れるかで対決する、Algorithm Single Round Matchが有名なのですが、他にもMarathon Matchというのがあります。Marathon Matchは、長期間で行われ、問題は多岐にわたり、機械学習やデータマイニングを題材にした問題が出題されることがあります。

Marathon Matchの基本ルール

（マッチによって、ルールが異なることもあります。）

• 問題は英語で出題されます。

• 使える言語・ライブラリ

  • オンライン（提出し実行する）使える言語は、C++、Java、C#、Visual Basic、Pythonです。外部のライブラリもライセンスの種類によっては使えます。
  • オフラインで行う機械学習用には、何の言語を使っても構いません。
  • オンラインではメモリ・コードのサイズ・計算時間に制限があります。マッチによって異なります。

• スコア関数というのがあります。結果の良さを表すスコアを求められます。例えば、(実際の値 - 予測値)の差が小さいほど高得点といったかんじです。 スコア＝「出題者側が最も重視するところ」といえ、このスコアが高い方が優勝となります。

TopCoderの登録方法

http://community.topcoder.com/tc のページ右上の"Register Now"から登録できます。登録の方法はpokutuna氏のページが分かりやすいと思います。 http://pokutuna.hatenablog.com/entry/20080720/1216514672

参加方法

1. イベントカレンダーで、開催日を確認します。 http://community.topcoder.com/tc?module=Static&d1=calendar&d2=thisMonth （Events -> Event Calendarで行けます）
   マラソンマッチは突然現れることが最近は多いです。TopCoderのトップページや、送られてくるメールでも、開催の確認をすることができます。

2. マラソンマッチが開催されたら、登録します。Algorithm -> Marathon Match -> Active Contestsで行けます。 http://community.topcoder.com/longcontest/?module=ViewActiveContests
   今は開催されているコンテストがないですが、あるときは問題が現れるのでregisterボタンを押して登録します。

3. 自分の解答ができたら、submitボタンを押して提出します。 自分のコードと、Test ExampleとSubmitの2種類のボタンが現れます。

   • Test Exampleは、少ないケースでの結果を知ることができます。
   • Submitが本提出になります。より多くのケースでの結果と、仮順位も知ることができます。

4. コンテストが終わると、より多いケースでスコアが求められます。数日で、最終結果がでます。

どんなコンテストがあるのか？

2012年にあったマラソンマッチです。データマイニング系の問題は以下のとおりです。

• USPTO Algorithm Challenge
  米国特許商標局の主催マッチ。特許の図の画像と特許の文書とを解析して、書かれている番号を自動的に取得するプログラムを書く問題です。 トレーニングデータも用意されてます。画像処理（文字認識）と文書解析の、機械学習の総合的能力が問われる問題でした。ランダムで2人組のチームを組むという変わったルールで行われました。

• NASA NTL Marathon Match 1 VehicleRecognition
  NASAが主催のマッチ。衛星写真で車かどうかを判別する問題でした。完全に画像処理の問題。日本人参加者のmsiroさんがSVMを使って優勝しました。msiroさんのブログはこちら http://msirocoder.blog35.fc2.com/blog-entry-67.html

• Soybean Marathon Match
  大豆の種別や畑などのトレーニングデータから、大豆の良しあしを判別する判別分析の問題や、収穫量を与える回帰分析っぽい問題が出題されました。

• Soteria Serious Injury Prediction
  保険会社からの出題。職場に関するさまざまなデータから、今年の職場でケガが起きる件数を予測する問題です。SVMや決定木っぽい解法が上位に多かったのですが、優勝した方は、とても単純な回帰式（2年前の職場のケガ数でほとんど決まる）で、優勝しました。

• HMS Challenge #1 MinorityVariants
  ハーバード大学メディカルスクールからの出題。遺伝子のデータの読み間違いを、判別する問題。機械学習が力が発揮できそうな問題でしたが、実際にはある遺伝子に関する情報に、重要な法則性があることがあり、ほぼ100%当てれるという結果に…。

データマイニング以外にも、GPGPUを使った問題、本当に数学的な難問、圧縮解凍の問題、パズル系の問題、完成しているコードを高速化させる問題など、問題は種類は多岐にわたります。

全体的な流れ

文章だけ書いても伝わらないと思うので、全体的な流れだけを、とてもざっくりと。

• HMS Challenge #4 BostonRiskPrediction
  ハーバード大学メディカルスクールからの出題。ボストン市内の住人データ・地理データ・2011年の1月～8月までの緊急コールのデータなどが与えられるので、そこから2011年9月～12月の間に、何月何日に、どこで、何件緊急コールがかかってくるかを予測する問題です。

ボストン市内の膨大なデータがトレーニングデータとして与えられます。これは地域別の人種割合データ・土地の値段・場所などのグラフです。

実際に1月～8月まで緊急コールが去年かかってきた場所をプロットしたもの。20万件近くかかってきていて、ボストン市内の形がそのままでてます。実際のデータなので、本格的ですが、たまに誤入力もあり、データクレンジングも必要です。

コードを書いて提出します。自分の場合はVisual Studioでコードを書いて、ブラウザ上に提出しています。Submissionを押すと本提出です。

仮のスコアと順位ができます。Marathon Matchの過去の戦績によりレーティングがつくので燃えます。特に赤い色のはレッドコーダーと呼ばれ、恐ろしく強いです。

こんなのの繰り返しで、最終日まで競います。

参加するメリット

• 実際に、自分が行っているがデータマイニングや機械学習の手法が有効なのか、世界の人との競争で確かめることができます。

• マッチ終了後に、他の人のコードが見れます。同じ問題でも、いろいろなアプローチがみられます。時には機械学習を使ってないベタな手法が勝つこともあり、逆に機械学習が圧勝することもあります。どちらの場合もとても勉強になります。

• 成績上位だと、賞金がでます。1位だと$5000、5位でも$500ぐらいもらえます。まだまだデータマイニング系のマッチは、他のTopCoderの部門と比べるとレベルが高いとはいえないので、チャンスです！

というわけで、機械学習を作ったり使ったりしてる方で、気になった方は、ぜひ参加してみてください！