Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

TopCoder Marathon Match AgentMatching

Marathon Match AgentMatching に参戦しました。

Event Calenderにも予定がなく,急に始まったこのMarathon Matchでしたが,折りしも夏休みに入ったところであり,また今回の問題は機械学習ということで学生のころの研究分野でしたので,何とかなるかもと淡い期待を持ちつつ参加することにしました。(賞金付きというのも魅力的でしたが)

しかしながら,コトはそんなに上手く運ばず,結構な時間をかけながら紆余曲折の末,何とかそれなりのスコアに到達できたというところで終わりました・・・

本問題の解法として,まずは機械学習ということでニューラルネットかID3(C45) かというのが頭に浮かんでいました。教師データが離散値であるのでID3で行けるのではと思い,試してみました。
ID3についてはWikipediaを参照してみてください。(そんなにメジャーなものではないと思っていたので,項目があることに驚きでした)
    http://ja.wikipedia.org/wiki/ID3

この方法での 結果はほとんどスコアが伸びず,ある程度手を入れてみたものの,わりと早めに見切りを付けることとなりました。教師データにノイズが乗っていることからも難しいだろうなとの予測もありましたので。
 

続いてはサポートベクターマシンにトライしてみました。サポートベクターマシンは,ここ最近よく目にするようになって,一度はさわってみたいなと思っていたので丁度良い機会でした。非線形の分類ができて,ノイズにも(ある程度)対応するとのことでしたので,結構の良い結果を得られるのではと期待を持って取り組んでみました。
サポートベクターマシンについては実装に関する資料がほとんどなく(理論の解説は多く見受けられますが),インプリにはかなり苦労させられました。この知見については,別記事でご紹介できればと思っています。

しかしながら,こちらの結果も芳しくなく,しかもID3よりも悪いという想定外の結果となってしまいました。誤差の許容パラメータが厳しすぎると学習が収束せず,緩くすると全て「真」(あるいは「偽」)となってしまい,収拾がつかない状況に。
このような結果を受け,今回の学習データは矛盾するデータが多く,分類するという考え方がそぐわないのだろうとの考えに至りました。
 

残り時間も少なくなり,残り2日しかない中で確率ベースのアルゴリズムを考えてみました。
学習データの重要そうな項目について,その各項目の値ごとに「真」となる確率を求めておきます。テストデータに対しては,各値ごとに「真」となる確率を引きだし,その確率値の重み付き和を求め,出力としてみました。(重みはシミュレーションで学習させる)

これが(やっつけアルゴリズムでありながら)意外なことに上手く行き,何とか満足できる位置までスコアアップしました。
もっと早くこれに到達できていれば,もう少し上位を狙えたような気がします。
 

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://msirocoder.blog35.fc2.com/tb.php/33-06304b6d
この記事にトラックバックする(FC2ブログユーザー)

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。