Coding Memorandum

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

スポンサーサイト

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

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ヶ月。賞金の通知が来ました!明示的な回答はないのだけれど,問題はなかったと考えてよいようです。

コメント

コメントの投稿


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

トラックバック

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

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