2011 TCO Marathon Match Round3 : StringCompressionの反省
前回書いた記事の続きというか補足というか。
何かまた思いついたら追加で書くかもしれない。
具体的な補足と反省
候補文字列列挙のやり方
ここはかなりクリティカルに効いてくる部分だと思う。そしてこの部分のやり方はあまり賢くなかった。特に、エラー率が高くてかつ下から2番目の文字列が数字を1個しか含まないときに精度が落ちてしまうのだけど、この出現率が1/4と高すぎるのが問題。パラメータ調整云々よりここで色んなやり方を試す方が良かったと思う。
圧縮のやり方
これに関してはそんなに悪かったとは思っていない。たしかに計算量の大きさに見合う成果が合ったのかどうかは分からないけど(事実スロット数が大きくなるほどスコアは落ちる)、完全に圧縮してしまうとその圧縮がどの位確からしいかわからなくなるし。おまけに圧縮の閾値を厳しくすると候補の列挙の精度が下がるし。
エラー率が極めて高いときのランダム解の発見
たくさん文字使った方が解像度高くなって得点上がりそう、という理屈は後付けで理解したんだけどあれほど上がるとは思わなかった。最初はS[1]=2..2,S[2]=3..3,S[N]=a..aとして最後に最適化していたんだけど、それと比べると3割以上変わった気がする。もっと具体的に言うとseed3のスコアは終了12時間前まで0.08に届いていなかった。
この事実に他の人はもっと早いうちに気がついていたような印象を受ける。どうやって気がついたのか気になる所。それとも論理的に考えて自明だったんだろうか。
最下流の文字が必ず始めの方に出現するという事実
何人かの人が指摘していたし、理屈も理解しているけどどういう風にその事実が活かせるのかわからない。エラー率高いときはほとんど全ての文字が置き換わることも珍しくないし。エラー率低いときには役に立つかもだけど、どうせエラー率低いときなんてどんな方法ででも復元できるんだからあまり美味しくない気がする。
TLE対策について
今回はTLE対策をシビアにやっていたせいで結果発表までヒヤヒヤだった(最終結果を見たら全部間に合っていた)。28.2秒まで探索して29.2秒まで評価してその後単純なパターン試して最適化してリターン、という形式だったけどもう少し安全側に振っておくべきだった。制限時間が30秒もあるんだから、28秒も29秒も大差ないしあと1秒ぐらい縮めても良かった気がする。制限時間10秒だと9と8はだいぶ違うけど…。
統計的な手法
他の参加者の採った手法を見ていると最尤推定とかそういう単語が当然のように出ているので、やはりもっと真面目に統計的な手法を取り入れるようにしないとこれ以上のレベルでは厳しい気もする。
というか、パラメータ探索にかかる時間とか安心感がだいぶ違う。
バイオインフォの手法
どう見てもこれはアラインメントの問題。コンテスト終了後、実際にバイオインフォやってる知人に聞いたらタンパク質のアラインメントとかまさにそのものだったらしい。自分が最初にやるべきだったのはバイオインフォの入門書を読むことだったのだろう。
メタ的な補足と反省
テスターまわり
今回もテスターは自作した。ソース直接いじってパラメータ調整がしやすかったし、元の文字列がどれだけ置換されずに残っているかとか分かりやすく出力できた。
計算機まわり
今回は制限時間30秒と長かったので計算機を回してる時間が必然的に長くなった。パラメータ調整をスロット数毎、エラー率毎(0.0~0.16, 0.16~0.64, 0.64~2.56の3通りに縮約)に各100ケースずつ回した。でも計算重くてエディタのレスポンスが悪くなったり時間かかりすぎたり色々アレだったので対応策も少しは考えておく必要がある。
ForumでPsyhoさんが言ってたけど、Amazon EC2とかの導入もアリかもしれない。有料、というのがネックだけど。
敗北と反省
BeautifulCrosswordは今でも悔しい位の負けっぷりだったけど、あのときの屈辱が2度と同じ失敗はすまいという意識に繋がったような。
問題の変更
問題が変更されてしばらくの間、変更前のアルゴリズムを引きずってた。結果的に上位者の解法を見ると変更前のでも工夫すれば上手くいったらしい。でもそれはあくまで結果論で、本来はもっと早めに気分を切り替えなければいけなかったような気もする。
