Coding Memorandum

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

スポンサーサイト

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

Samurai Coding

昨年,楽天カンファレンスでプログラミングコンテストを開催した早稲田大学 鷲崎研究室様からプログラミングコンテスト開催の連絡を頂きました。

今年はGREEをスポンサーとして開催されるようです。
   Samurai Coding

2011.12.16 問題配布開始
2012.1.22 決勝@GREE

インターナショナルな大会として,国内外問わず広く参加者を募るとのことです。

個人的には是非参加したいと思うのですが,決勝の日の都合が付かない可能性が高いのでどうしたものかなぁと思案中です。

DevQuiz 2011

今年もDevQuizに参加しました。スライドパズルはいい問題でした。去年よりも盛り上がっていたように思います。

スライドパズルの結果は 4969/5000 残り31問で時間切れ。壁の本当の難しさに気づくことが遅れてしまったのが敗因です。DevQuiz2011


以下,考えたこと等をメモしておきます。

  • 基本的な考え方は,盤面をノードとしたグラフの探索で良いはず。
  • ノード数は,6x6のボードで36! 不可能な盤面もあるので 36!/2 かも。どちらにしても広大な探索空間となることは間違いない。
  • いかに沢山の探索をこなせるかと,無駄な探索を排除できるかがカギになるはず。
  • とりあえず,参考文献をあたる。手元の「アルゴリズムクイックリファレンス」に,ずばりそのものスライドパズルが扱われている。
  • グラフの探索はA*で良さそうだ。
  • とりあえず,ヒューリスティック関数はマンハッタン距離(MD)で試してみる。h*=MD×2でサクサクと解ける(もちろん解けない問題も多くある)。
  • 他も調査。下記のサイトが参考になりそう。
        15パズル自動解答プログラムの作り方
  • 反復深化(IDDFS,IDA*)という考え方があるらしい。 前述の参考書にもキーワードはあった。
  • 反復深化は評価値の閾値を変えながら何度も探索を実行するものらしい。
    • (理解が浅いだけかもしれないが)反復の度に同じ探索をやり直すので非効率では?
    • 局面数が多いので,いかに探索数を減らす or 多種の探索を行うかが至上命題。
    • 直前反復での閾値の際の局面を保存しておいて,次の反復はそこから始めれば速いかも?
      => これって A* そのものと変わらない気が・・・
    • 反復深化は,BFS,A*ではキューに溜めている局面情報を毎回探索基点からの探索を繰り返すことでオンデマンドに求めているものと考えればよいらしい。
    • 探索空間が大きい場合にはあまり実用的ではないような気がするので,今回の問題への適用はパスする。
  • とはいっても,単純にA*を用いてはメモリが足りなくなるのは明らか。
  • A*において評価値が悪い局面は,後で評価される(プライオリティキューの上位に浮上する)可能性が低いように思う。
  • スライドパズルはどちらかといえばグリーディな感じで手順が決まりそうで,一旦極端に評価値の悪い局面を経由しての最短手順はあり得そうにない。
  • プライオリティキューに最大サイズを設け,溢れた局面(悪い局面)は捨て去ることとする。
  • 忘却型プライオリティキューは set (STL)で簡単に実装できる。(処理効率には目を瞑る)
  • MDでは,壁に囲まれる部位で不利な方にタイルを動かしても評価値が向上してしまう。
    => 各点間の最短パスを事前に計算しておいて,その距離を評価値として用いることとする。
  • 他に評価値はないか? => 実際にスライドパズルで遊ぶ。
  • 自分が置かれる行,列で他のコマと順序が入れ替わっているケースは余計に手数がかかる。例えば,「12435」のようなケース。
    => このときは評価値+2としよう。
  • ヒューリスティック関数が「h* < 実際の残り手数」であれば,最短性が保障される。しかしながら,可能性のある盤面を丁寧に探しに行ってしまうので,探索時間が多くかかる。逆に「h*>実際の残り手数」であれば,最短性を犠牲にして評価値の良い局面をグリーディ的に探しに行くので早く解を見つけられる。
    => 探索時間のかかる問題は評価関数の係数を増やして求めていくこととしよう。
  • ゴール状態から逆向きに探索した状態を列挙しておいて,それらをゴールとすると効率が良さそう。
  • ゴールまで16手程度であれば,メモリ上に局面状態を展開できる。
  • これで,4750問程度
  • 現状,局面の探索では1手前の局面へ戻ることだけを抑止している。解けてない問題は,どこかでループが発生しているのかもしれない。
    => 探索先の局面でプライオリティキューにある局面へは(再)訪問しないようにしてみる。
        (キューには2百万局面保存)
  • これで,4830問
  • 解けない問題をトレース出力。壁が通路となっている問題が解けていないようだ。
  • 通路の場合,そこに入るタイルを連ねて移動させなければならない。
  • 評価関数に,各タイルの相対距離を使ってみよう。隣合うタイルが近くにあるほど評価値がよくなる。
  • これで,4969問。ここで時間切れ。残り31問なのが悔しい。

提出版のソースは下記の通りです。

続きを読む

プログラミングコンテスト・ラッシュ

5,6月はプログラミングコンテストの数が多い!

しかしながら,私の方は1年越しの新居プロジェクトが大詰め(6/末引越し予定)を迎え,プログラミング関係は少し自重しなければならない状況にあります・・・

  • TCO Algorithm
    Qual1に参加して×。今年は早々に諦め・・・

  • MM70
    賞金に釣られて,ずっと机上で検討をしていましたが,結局コーディングの時間が取れそうにありません・・・

  • Code Jam
    Round1は,A不参加,Bは寝坊,Cで通過。Round2は23時開始なので,何とか時間が取れるかも。

  • TCO MM
    Round1はシード。Round2は何とか時間を捻出したい。

  • ICFPC
    一番の楽しみでしたが,今年は引越し直前で参加は難しそう・・・

これから夏・秋にかけて,色々行われることを期待します。GoogleのDevQuizや,楽天のコンテストは今年も開催されるようなら参加したい!

NTL MM1メモ

すっかり旬も過ぎてしまいましたが「NASA Tournament Lab Marathon Match1」について,考えたこと・調べたことのメモを記しておきます。

問題はこちら(要TopCoderID)。航空写真に車が写っているかの有無を判定する機械学習モノ。トレーニングデータは4000個用意されている。

以下に考えたこと等を記していきます。

  • 「物体認識」といえば最近のトレンドは局所特徴量のはず(もう古い?)。 Open CVにあるSIFT,SURFが有名。
  • SIFT,SURFは特定物体のマッチングで良く使われる。ARのマーカー検出の事例が有名。
  • SIFT,SURFには汎化能力はなさそう。
  • 車を見つけるには,エッジ抽出して長方形を検出すれば良いかも。=> 教師データを眺めると建物とかも長方形なので,エッジだけでなくテクスチャの情報も合わせる必要がありそうだ。
  • 物体認識系の論文・資料等の調査。 最新動向にキャッチアップ。
  • この資料によれば,局所領域のつながりを見る手法が優位のようだ。学習手法はBoostingが良いようだ。
  • Joint HOGとAdaBoostについて少し深く調査してみる。次の論文が参考になります。
         http://www.vision.cs.chubu.ac.jp/04/pdf/ITS07.pdf
  • 物体認識について,中部大学 藤吉教授/藤吉研究室の情報発信量がすごい。上記の他に下記の資料も大変参考になりました。
         http://www.vision.cs.chubu.ac.jp/joint_hog/pdf/HOG+Boosting_LN.pdf
         http://www.vision.cs.chubu.ac.jp/joint_hog/pdf/Joint+RAB.pdf
         http://www.vision.cs.chubu.ac.jp/vu/pdf/VU7-ObjectClassification.pdf
  • AdaBoostについては,下記サイトで各種情報を纏めてくださっています。
         http://d.hatena.ne.jp/ymuto109/20070823
  • HOG,Joint HOGを調べると,向きの変更(回転),スケールの変更に対して弱そうである。今回の問題は航空写真なので回転とスケーリングの要素が加わっており,これらを上手く扱うことが肝になる。
  • Joint HOGは局所特徴量の相対的な位置を学習しているが,これを拡張して相対的な角度も学習してあげれば回転に対してロバストにできそう。==> 上手く行ったら論文かけるかも。
  • しかしながら,スケールの変化に対しては良い解決案が浮かばない・・・
  • さらに調べを進めると,今回やろうとしていることは「一般物体認識」というものらしい。再度検索・・・
  • Bag of Featuresというものがピッタリと当てはまりそうだ。
         http://www.vision.cs.chubu.ac.jp/04/pdf/TS02.pdf
  • 発注していた参考書が届く。前々から読みたかった本でもあり,良い機会なので買いました。
         コンピュータビジョン最先端ガイド1
         コンピュータビジョン最先端ガイド2
         コンピュータビジョン最先端ガイド3
  • この本でもBag of Featuresが大きく取り上げられている。
  • Bag of Featuresについては,次の資料が参考になります。
         http://www.vision.cs.chubu.ac.jp/ssii08/ssii08-yanai.pdf
  • Bag of Featuresは,前述で汎化能力がないとしたSIFT,SURFを使って汎化能力を持たせることができる。SIFT,SURFは回転,スケールの変化に対してロバストであることから,今回の問題にピッタリの手法と思える。

  • Bag of Featuresの考えを使って実装してみる。局所特徴量にはSURF-128を使う。
  • 局所特徴量のクラスタリングにk-means法を使う。とても時間がかかる。終わりそうにない。
  • 最近傍計算の多さがネック。kd-treeを使うと早いらしいが,次元が多いときは効果が薄いらしい。次元が多いとは何次元ぐらいを指しているのだろうか?128次元はダメ?
  • 下記サイトで三角不等式を使って高速化する文献へのリンクを見つける
         http://ibisforest.org/index.php?k-means%E6%B3%95
  • 論文はこれ
         http://www.aaai.org/Papers/ICML/2003/ICML03-022.pdf
  • かなり早くなり,計算を終えられるようになった。

  • 機械学習にはSVMを使う。SVMは作りおきがある。以前のMarathon Matchで作ったモノだが,一度もSubmitされることなくお蔵入りになったモノだ。 ついに日の目をみるときが来た。
  • うぅむ・・・動かない・・・・・・引数のコメントが間違っているようだ。教師データの正解出力は0 or 1と記載しているが,正しくは-1 or 1のはず・・・・・・動いた!

  • コード完成。しかし,submitしても結果が返らない。キューにも入らない。エラーも表示されない。
  • ・・・悩むこと3,4日・・・
  • どうやらコンパイル後のバイナリサイズに制約があるらしい。1Mバイト以内だそうだ。
  • ローカル環境でのバイナリサイズは4MB越え。どうしよう・・・
  • SVMのサポートベクトル数は,学習ケース数と相関がある。学習ケース数を減らせばサイズが減るはずだ。
  • 試行錯誤。4000個を500個に減らせば1MBに収まる!
  • ランダムに500個を抽出。残り3500はテストケース。 結果的には,このことによってオーバートレーニングを抑止でき,好成績を残せたと見ています。
  • 残り2日間は,ひたすらランダムに組合せを変えて学習。
  • 最終日。チャンピオンデータを提出。

  • 入賞したこともあって,SURFって権利的に問題ないのかが急に気になり始める。SIFTがNGであることは色々なところで見かける。
  • とりあえず,TopCoderの方に相談。参加資格に問題がないか調べてくれるとのこと。
  • 待つこと1ヶ月。賞金の通知が来ました!明示的な回答はないのだけれど,問題はなかったと考えてよいようです。

The NASA Tournament Lab Marathon Match

Marathon Match 参戦中 ・・・(1/28-2/18)
航空写真での車の有無の判別問題。なかなか興味深い。


2/21 : System Test が終わって,現在 Top!
今回はSystem Testデータに対する物言い期間があるようで,順位が確定するのは48時間後以降のようです。


2/28 : Testデータ修正後の再テストの結果が出ました。見事に1位をキープしました!

訓練データで評価されるProvisionalスコアの高い人が軒並み落ちているので,オーバートレーニングとの折り合いをつける戦いだったのではないかなと思います。

私の方は,コンパイル後のバイナリサイズが1Mバイト以内でないといけないという謎の(記載のない)仕様にひっかかり,訓練データを10%程度までに減らす破目に合いましたが,結果としてはこれが功を奏したようです。

まとまった時間がとれたところで,今回の大会の内容を書いておきたいと思います。

前のページ 次のページ

FC2Ad

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