オーバーフィッティング回想録

はじめに

この記事は以下の競技プログラミングイベントの一環として書かれました。

Competitive Programming Advent Calendar 2014
http://partake.in/events/9b53847a-3a97-4aac-b754-5e681c3c7197

前置き

マラソンマッチでシステムテストの後に順位が落ちた。
……そんな経験はありませんか？

それは一般的に過学習やオーバーフィッティングと呼ばれます。

私事ですが、最近、暫定1位からのシステムテスト転落があまりに多くありました。

2014年6月4日: 2014 TCO Marathon Round 2 "RectanglesAndHoles"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15982
終了時暫定1位→システムテスト後5位に転落

2014年6月28日: EPA Cyano Modeling Challenge "CyanoHABsPredictor"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15995
終了時暫定1位→システムテスト後5位に転落

2014年7月2日: OmegaDetector
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=16001
終了時暫定1位→システムテスト後2位に転落

2014年10月27日: Design of Experiments "OptimalDrug"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=16168
終了時暫定1位→システムテスト後11位に転落

『ちょwww コルンさんwwwww システムテスト無視してプレイしてるでしょ！？』
『また、暫定だけ1位ねwwww』
『システムテストで落ちて良いなら、誰でも暫定1位ぐらい取れるわwwww』

そんな声が聞こえてきそうなぐらいの連続転落なので、少し振り返ろうと思います。

そもそもマラソンレッドコーダーとオーバーフィッティングとは、切っても切れない関係にあります。

オーバーフィッティングとは

まずは導入として、私にとって最初のマラソンマッチにまで振り返ります。

2011年4月5日: Contest: Marathon Match 68 "BeautifulCrossword"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=14495

暫定2位、システムテスト後2位で、転落はありませんでした。

しかし、上位5人の暫定スコアとシステムテストスコアの推移に注目して下さい。
暫定テストでは100テストケースなのに対して、システムテストでは1000テストケースですので、単純計算で10倍するだけで、ほぼ同じぐらいのスコア基準となります。

wleiteさん、EmKさん、ainu7さんの3人は、ご存知（？）、3人とも有名なマラソンレッドコーダーです。
スコア変動を見ると、66.67→668.77、65.73→658.76、64.44→645.08と、3人が3人とも、システムテストで10倍よりも少しだけ良いスコアになっています。

対して（私含めて）イエローコーダーの2人ですが、66.50→664.73、64.64→645.36という具合で2人とも10倍よりも少しだけ悪いスコアになっています。

これは実は偶然ではなく、必然です。
システムテストによって上がることはほぼ無くて、システムテストによって落ちることだけが、オーバーフィッティングが原因で時々あります。

レッドコーダーは、オーバーフィッティングを避ける手段を持っています。

原因を探ると、この時私は初参加でしたので、自前のローカル環境にて100テストケースぐらいでテストを行っていました。
このコンテストが終わった後すぐに、chokudaiさんから、ローカル環境で確認する際は、300テストケースぐらいを使っていることを教えて頂きました。

それ以降、私は基本的には、ローカル環境では1000テストケースを目安に使う様にしています。

実はマラソンマッチで良くあるヒューリスティクス系の出題では、オーバーフィッティングによる順位の変動は微々たるもので、最終順位の変動のみを見るのなら、100人ぐらい参加しているコンテストの場合で、多く変動した時でも3位落下ぐらいの変動に収まることが多いです。
そのぐらいの差しか出ないのは、ヒューリスティクス系の出題のほとんどが、LocalTests、TestExamples、FullSubmit、SystemTestsの４つで取り扱う問題が、本質的に同じであることが原因です。

それでも、FullSubmit結果を見ながら方針を選んでしまうと、パラメータ側だけに限らず、アルゴリズムそのものに、オーバーフィッティング要素が紛れ込んでいきます。
その結果が、3位程度の落下へと繋がります。

オーバーフィッティングの可能性がある環境下では、どちらに舵取りして良いのか分からない状態になりますので、それを取り除くことで、どちらに舵取りすれば良いのかが分かる様になり、結果的に最終順位（及び暫定順位も！）を大きく伸ばすことができます。
微細な差であっても、10000テストケースもテストしてハッキリと差が見えていれば、本当に些細であっても、偶然ではないことが分かります。

実際には標準偏差など統計手段を用いることで、もうちょっと具体的なことが言える様で、この辺ainu7さんが良く話題に出しています。

私はあまり詳しくないのですが、たとえば標準偏差が100のとき、100テストケース平均の標準偏差は10ぐらいで、10000テストケース平均の標準偏差は1ぐらいになるのかな？？ と思っています。（テストケース数の平方根で割ることができる？）
ただこの話には、テストケースごとの最適解スコアの標準偏差の話と、同じテストケースに対するソルバの使用乱数列による獲得スコアの標準偏差の話が混じっているので、実際にはそこまで単純な話ではなく、後者を真面目に求める手間がとても大きいので、1000テストケース以上である程度の差が出てれば、感覚で判断して有用な変更だったと結論付ける様にしています。

この辺、詳しい人いましたら、ぜひご指摘ご指導頂きたい所です。

それでも起こるオーバーフィッティング

さて、それじゃあ1000テストケースぐらい用いるのだから、オーバーフィッティングとはもう無縁ですね、さよならグッバイ。
……残念ながら、そうもいきません。

さよならグッバイ、オーバーフィッティング……で済むのなら、なぜ私は今年に入って4度も、暫定1位から転落しているのでしょうか？

前フリがだいたい終わりましたので、ここから本編です。
それでも引っかかるオーバーフィッティングの脅威について、ここからコンテスト別で説明していこうと思います。

レアケース

非常に間抜けな転落をしたのが、TCO14MR2でした。

2014年6月4日: 2014 TCO Marathon Round 2 "RectanglesAndHoles"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15982
終了時暫定1位→システムテスト後5位に転落

落ちた原因は、セグメンテーションフォルトでした。
発生確率は８０テストケースに１テストケース前後だった様です。

２文字書き換えれば（あるいは妥当な値じゃなくて良いのなら、１文字書き加えれば）システムテスト後もおそらく1位でした……というのは置いておいて、これもまた実力ではあります。
現に、私のローカル環境のテストではやはり1000テストケースぐらいテストしていて、セグメンテーションフォルトが大量に出ていました。
ただ、採点機構を自動化していたため、警告に気付きませんでした。
最終日の最終サブミットのみでしか出て来なかったエラー要素だったため、疲れていたこともあり、完全に見逃しました。
（最終サブミットの１つ手前のサブミットのままだったら２位ですね……１位が取りたかったので、その選択肢は無いのですが）

セグメンテーションフォルトが出るとデータベースに突っ込まれる値がnullになるのですが、全体スコア算出の際にnullを除いて計算していたことが原因でした。

と、TCO14MR2に限って言えば間抜けな話なので二度と繰り返すはずもないという話で決着するのですが、実はそう簡単に片付けて良い話でもありません。

同類の問題がTCO12MR2の際にもありました。
セグメンテーションフォルトではなかったものの、不確定反復問題だったため、無難な選択をしてみても、実際に蓋を開けてみたら不運が重なって早期ゲームオーバーになることがありました。
パーフェクトゲームを目指せる問題でしたので、99.5〜100%の点数を狙う中、時折0〜50%付近を取ってしまうテストケースが存在するというのは、とても大きな痛手となります。
この時は確か、ローカルテスト上で20000テストケースぐらい走らせて10件程度の0〜50%テストケースが存在しました。
この時のSystemTestsは3000テストケースだったので、1.5件程度の0〜50%テストケースが存在するはずですが、実際には3件発生しました。

ちなみに1位の人でも1件、2位の人でも3件、発生しています。

上位陣はほぼ理想点で横並びになった後、稀に存在する０点テストケースの数で順位が決まる……この０点テストケースの割合は工夫に依って減らせるものの完全に０にすることは難しく、SystemTestsに使用されるテストケース数が充分に多くないため、運ゲーになる場合があります。
こういうケースでは、FullSubmitによる暫定順位に大きなノイズが加わっている場合があります。また、SystemTestsも運次第です。開けてみなければ結果は分かりません。

高速化

実は、オーバーフィッティングしなければならない要素があります。
その１つが、高速化です。

Javaだと同じプログラムが異なるOS上で動きます。
C++でも、Javaほどではないにせよ、ある程度の環境で同じ様に動作します。

しかしながら、まったく同じではありません。
動作速度が異なります。

CPU、メモリバス速度、コンパイラバージョン、OSコア等の要因によって、動作速度が変わってきます。

そんなもの、良いCPUを積めば速くなるだけだろう？

その通りなのですけれども、違うんです。それだけじゃない。

CPUによって、得意とする命令、不得手とする命令が、異なります。

単純にどの命令も均一に速くなるだけでしたら、ローカルで高速化を施し、あとは本番環境で動かすだけです。
ところが、ローカル環境と得手／不得手が異なる場合、ローカル環境で高速化を施すこと自体が悪いオーバーフィッティングになります。

では、しなければならないオーバーフィッティングとは何でしょうか？

簡単です。本番環境にオーバーフィッティングさせることです。

これをやっているかどうかは、ExampleTests数を見れば分かります。
明らかに初心者じゃない人が、明らかに不自然な短い間隔で20連投以上していたなら、きっとそれは、本番環境のマシンの特性を調べています。
ただ、ExampleTestsの問題固有の速度計測になる場合がありますので、そういう場合は特定の問題を埋め込んで、埋め込んだ問題を計算させて時間を測定し、最後にダミー回答を返したりする場合もあります。
（入力値が大き過ぎる場合は、これが出来ない場合もあります）

配布データの延長線上に本番データが無い

さて、これまではオーバーフィッティングとは言っていたものの、機械学習以外のコンテストの場合が多かったのですが、ここでは機械学習系のコンテストを取り上げます。
ヒューリスティクス系のコンテストではオーバーフィッティングによって順位が落ちても３位以内であることが多い旨を書きましたが、機械学習系の場合はオーバーフィッティングによって１位→最下位があり得ます。

むしろここが本題と言ってよいでしょう。

オーバーフィッティングの避け方については、他の専門記事等に譲ることにします。
マラソンマッチアドベントカレンダー内でも、機械学習系の記事を載せる予定の方々がいる様ですので、そちらに譲ります。

ともかく、本記事はそういうガチのオーバーフィッティング回避テクニックに関してではなく、コンテスト特有の部分に焦点を当てたいと思っています。

ある意味で破綻していますが、程度の差こそあれ、賞金ありのコンテストでは配布データの延長線上に本番データが無いことがあります。

多くのコンテストでは、配布データとExampleTestsとは同じなのですが、FullSubmitとSystemTestsに使われるデータは異なります。

異なるだけであり、本質的には同じ……であるなら問題ないのですが、本質的に異なることが多々あります。

2014年6月28日: EPA Cyano Modeling Challenge "CyanoHABsPredictor"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15995
終了時暫定1位→システムテスト後5位に転落

上記は、周期問題であるにも関わらず、配布されたデータ（およびExampleTests）の学習期間は１年分のみでした。
FullSubmitではそれが１年半分ぐらいになり、SystemTestsではそれが２年分ぐらいになります。
SystemTestsでは有効そうな手法が、ExampleTestsでは使えず、FullSubmit以降でしか有用性の検証が行えませんでした。
実際それが有効だったから5位までしか転落せずに済んだのだと思いますが、ともかく、FullSubmitでオーバーフィッティングするしか検証方法がないコンテストというものが、稀にあります。
（この手法を使う前の順位が暫定6位ぐらいだったので、もろもろの要素から考えると、この手法を使わなかった場合の順位は8位以下だったものと思います）

このように、FullSubmit以降でなければ存在しない要素が事前に分かっている場合は、FullSubmitスコアのみを見て学習させていかなければならない場合があります。
この場合、あえてオーバーフィッティングを選ぶ選択肢があります。
もちろん、暫定１位に躍り出ても、最終順位は落ちる可能性が高くなります。
でも、その要素を使わなかった場合の順位はもっと悪い可能性が高く、FullSubmitスコアで調整することを意図的に選ぶ場合があり得ます。

次の問題に行ってみましょう。

2014年10月27日: Design of Experiments "OptimalDrug"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=16168
終了時暫定1位→システムテスト後11位に転落

この問題、配布されたデータはテストデータ生成器で、FullSubmitおよびSystemTestsはリアルデータでした。
……もはや延長線上どころの騒ぎではありません。

CyanoHABsPredictorの際に、SystemTestでまで効果があった要素が、LocalTestsで検証不可能だったという、運営への不信感があります。

また、更に昔……MM73 OrdinalTraitAssociationMappingというコンテストでは、FullSubmitで故意にオーバーフィッティングしなければ4位以上に入れなかった問題もありました。

2011年7月27日： Marathon Match 73 "OrdinalTraitAssociationMapping"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=14584

流石にMM73の様なことはもう二度と繰り返されないと思いたいのですが、TopCoderMarathonMatchの機械学習系の問題の質は、不信感だらけでどれぐらいアテにして良いのか良く分からない状態です。
（※ 逆に、ヒューリスティクス系の問題の質は、どれも安定して高いです）

さて、OptimalDrugに話題を戻します。

結論から書きます。この問題は、他のTopCoder機械学習系の問題と比較して、問題の質は高い方だった様です。
様です、というのは、少なくとも参加者の中には、ただの１人も、リアルデータにのみ有効な要素を見つけ出す事ができた人がいませんでした。
すべての参加者は、非リアルデータに存在していた要素によって、最終順位が決まりました。

この根拠は、膨大な量の非リアルデータ（シードを変えればいくらでも公式のデータ生成器によって生成可能）を使って、Psyhoさんが実験を行い、その結果を掲示板に書き込んでいます。

Some stats about the system tests
http://apps.topcoder.com/forums/?module=Thread&threadID=836129&start=0

この結果を見ると、実際のSystemTestsによる順位と、公式のデータ生成器による順位との間に、強過ぎる相関があることが見て取れます。
非常に妥当な順位であったことが分かります。

このように、配られたデータが非リアルデータであり、実際のシステムテストがリアルデータで行われるとしても、非リアルデータでの検証で充分な場合もあり得るということです。

ただ、私の把握している範囲でも、配られた非リアルデータとFullSubmitでのリアルデータの間には、あり得ないデータ特性の差異がありました。
単純に誰も辿り着けなかっただけで、やはりFullSubmitでなければ検証できない要素があった可能性も、否定自体は出来ません。

追記：
この記事の公開後にyowaさんに指摘されたのですが、Psyhoさんの掲示板への書き込みデータは、非リアルデータでの全員分のシミュレーション結果ではなく、システムテスト結果点数を用いてのブートストラップらしいです。

少し極端な例で説明すると、たとえばシステムテストが3つしかなかったとします。3つをAとBとCだとします。実際のシステムテストではABCの３つのテストが行われたのですが、もしかすると出題に偏りがあり、AABとかACCとかいう出題だった可能性もある、という理論のもと、沢山シミュレーションします。
その結果として、各競技者が、何位の確率が何％で……というのが出てきます。

ここでは極端な例として３つしかシステムテストがなかった場合を示しましたが、システムテストが多ければ多いほど、このシミュレーションは妥当な結果を出します。
Psyhoさんの出した結果がSystemTestsによる順位と相関が強過ぎたのは当然の話で、PsyhoさんはSystemTestsの順位が揺らぐ確率がどのぐらいあったのかを知りたかった、ということの様です。

というわけですので、残念ながら、このコンテストにおいても配布データはアテにならなかった様で、FullSubmitのオーバーフィッティングを目指した路線は、どうやら間違いだったと断定はできない様です。

そこに賞金がある限り、使える手段はなんでも使って、SystemTests１位を狙うのがコンテストです。
オーバーフィッティングとは仲良く付き合って行かざるを得ません。

（※ただ、OptimalDrugに限って言えば、妥当であってはならないデータ特性を採用してしまいましたので、反省が残ります。もう少し運営を信頼すべきでした）

システムテストの偏り

SystemTestsの件数をチェックしましょう。
それが40件ぐらいしかないのだとすると、運ゲー度が増します。

2014年7月2日: OmegaDetector
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=16001
終了時暫定1位→システムテスト後2位に転落

上記の出題は、バーコードの画像認識ゲームでした。

画像認識であることもあり、問題の性質上、スコアの標準偏差は高い状態にあります。
しかし、FullSubmitが100件、SystemTestsが222件ある、そう安心していました。

2日半程度しか参加していないコンテストなのでそこまでこだわりは強くないのですが、試合終了後しばらくしてから一応見直しをしました。

まず、Test Case 33〜39ですが、Psyhoさんが0点を連発している傍ら、僕は2300点前後を連発しています。
Test Case 49〜53ですが、Psyhoさんが0点を連発している傍ら、僕は1400点前後を連発しています。
そしてTest Case 177〜184ですが、Psyhoさんが1400点前後もしくは2300点前後を連発している傍ら、僕は0点を連発しています。

お気付きでしょうか？　0点を取るテストケースの偏りが、偶然では片付かないほど偏っているのです。

ひとまず、どれだけデータに偏りがあろうとも、そこまで含めてのコンテストなので、それも実力のうちです。
それは間違いないのですが、本記事の目的はオーバーフィッティングを回想し、同じ轍を踏まないことです。

おそらく8問程度はほぼ同じ画像……下手すると16問ぐらいほぼ同じ画像だった可能性があります。
全部で200問以上あるんだから8〜16問程度似た画像でも問題ない？　果たしてそうでしょうか？
テストケース間の相関が高い時、同じ解法プログラムでのスコアの標準偏差は高くなります。
つまり、順位はひっくり返り易くなります。
あるいは、FullSubmitによる暫定順位の時点で、偶然ひっくり返ったランキングが出易くなります。

そして、SystemTestsに8件のほぼ同じ画像があったとした時、その内訳を気にするべきです。

以下は問題文だか、あるいは問題文と同等の価値を持つ、掲示板への主催者サイドの書き込みです。

「ダウンロード可能な学習データ10件は、人の手によって、慎重に選ばれました」

学習データはランダムにではなく、人の手によって、意図を持って選ばれています。

こうして考えた時、内訳は果たして以下のどれだったのでしょうか？

A. 学習データ0件、FullSubmit0件、SystemTests8件
B. 学習データ0件、FullSubmit4件、SystemTests8件
C. 学習データ1件、FullSubmit0件、SystemTests8件
D. 学習データ1件、FullSubmit4件、SystemTests8件

思うに、少なくともCまたはDです。
なぜなら、SystemTestsに8件以上も含まれている系統画像があったら、１つは配布学習データに加えると判断するのは妥当です。
更に私の提出したプログラムは、与えられた学習データのとある１つの画像に対してだけ、0点を出します。

意図的に選ばれたとする出題者発言から、私は、それが最も極端な例であると推理しました。
最も極端な例であれば、他の例は基本的にはそこまでは極端ではないので、読み取れないでも問題ありません。

しかしながら、極端な例であれば、ほとんど同じ……少しだけ撮る角度や明るさを変えた画像が、SystemTestsにおいて複数用意されている……そういう可能性を、考える必要がありました。

次回からは、その可能性を考慮に入れて取り組むことになりそうです。

採点バグ

最後になりますが、マラソンマッチの採点サーバーにはバグがある場合がある様です。
毎回あるバグなのかどうかは分かりません。むしろ１回しか出会った事がありません。

採点処理は単純ではないため、毎回別の採点プログラムを使用している可能性があり、問題固有のバグだった可能性が高いです。

2014年8月21日: ChildStuntedness
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=16065
終了時暫定53位→システムテスト後59位に転落
（ただし59位は最下位であり、0点の順位。32人が0点で最下位）

0点落ちには著名レッドコーダーのwleiteさんも居るため、簡易的に説明する際にはこれを免罪符に挙げますが、実は問題はこれではありません。
0点の原因は、正直良く分かりません。wleiteさんに関してはTLEの可能性が高く、私にもTLEの可能性はあります。

TLE自体は仕様であり、TLEで0点は別に構わないのです。

問題は以下の２つの示す暫定スコアの差異です。

順位表：
http://community.topcoder.com/longcontest/stats/?&sr=51&nr=50&module=ViewOverview&rd=16065

サブミット履歴：
http://community.topcoder.com/longcontest/?module=ViewSubmissionHistory&rd=16065&pm=13367&cr=22689976

最新サブミットである5サブミット目が0.00点であるにも関わらず、暫定スコアは128,828.09点のままでした。

当時の状況としては、以下でした。

FullSubmitを送信
→Queue Statusからはすぐに取り除かれる
→しかしメールで結果が来ない
→ちょうど24時間ぴったり経った頃に、メールが届く
→しかしメールの内容は、送ってもいないExampleTests

私のメールボックスには、ExampleTest13の結果メールが3通分あります。
（1通目はExampleTest13、2通目はFullSubmit4の24時間後、3通目はFullSubmit5の24時間後）

それで、こんな面白い状況を放っておくわけにもいかない……と思い、そのままゲームを離脱、レッドコーダーからイエローコーダー転落と相成りました。
（レーティング変動のキャップが150だと思い込んでいて、0点提出してもレッドからは落ちないと思い込んでいたのが、安易に好奇心に負けた理由です）

話をはしょって勉強会でちょっとその話をした所、「TopCoderへと異議申し立て、直談判とかしないんですか？」とかいうことを言われましたが、するはずがありません。
レーティングなんてどうでもよくて、僕は上記状況における好奇心に負けました。
なので、0点であること、その点数によって最下位であること、また最下位であるからレーティングがキャップまで落ちることは、とても正当なことです。
どこにも異議申し立てを行う要素などあるはずがありません。
レーティングを大切にする場合のこれに対する正しい対処は、試合が終わる前に、メールまたは掲示板に、この旨を主催者側へと連絡すれば良いのです。
明らかなトラブルで、問題自体に触れない内容なので、この場合はおそらく掲示板への書き込みで問題ないと思います。

しかし僕は、それをしませんでした。好奇心に負けたのです。
対処しないでほしかった。
このまま終局した時に、3サブミット目がアクティブとしてシステムテストに使われるのか、それともやはり最終サブミットである5サブミット目がシステムテストに使われるのか、それを知りたかった。
結果、知識欲は満たされました。
だからこれはこれで良い。

ただ、落ちる前の私のレーティングでさえ、某所から苦情が来ます。
colunさんのあのレーティングは詐欺だ、と。（※リップサービスの可能性はあります）
確かにTCO予選だけ出場してればもっと上がりそうだなと思います。予想としてはちゃんと時間を取った上でのヒューリスティクス系の問題に限って言うなら2500前後は難しくないでしょう。
ただ、レーティング付きの賞金ありコンテストが開かれれば登録して調査のためにサブミットしてみることもあるでしょうし、途中で投げ出せば0点のまま終わることもあるでしょう。

レーティング付きの賞金ありコンテストが存在し、かつ仕事の合間に賞金狙いで参加している以上は、それは仕方がないことです。（今回紹介した暫定１位転落で、不本意だったのはTCO14MR2のみです）
その辺まで含めて、実力であり、今のレーティングは正当なものなのかもしれません。

ただまぁ、流石にイエローコーダー落ちは落ち過ぎなので、これはそのうちどうにかしたいと思っています。

また、投げ出さずとも、機械学習系のコンテストはヒューリスティクス系ほどには強くないです。それらが同じレーティングとして評価されるという点は若干不自然に思っています。
師匠（大学院の某教授）からは、ヒューリスティクスも機械学習も本質的に違うはずがないから、単に勉強不足なだけだろうとお叱りを受けたりもしています。
その辺の検証も含めて、たとえレーティングが下がっても、今後機械学習系のコンテストには積極的に参加していく予定です。

終わりに

今回はあまり需要のない所をアドベントカレンダー記事にしたかもしれません。

ただ、なんとなく普段のツイッターで、需要のある所は定期的につぶやき続けている様な気がしますので、今回は地味な内容を取り上げてみました。

今回のイベントにと誘って頂いたtomerunさんに感謝しつつ、本記事を締めくくろうと思います。