ALDS1_6-B Partitionを解く話
クイックソートで使うPartitionを実装する．
特徴
・閾値で分けるだけなので全体はソートされない．
アルゴリズム
- Partition(A, l, r)
- threshold = A[r]
- i = l - 1
- for j = l to r - 1
- if A[j] <= threshold
- i = i + 1
- exchange(A[j], A[i])
- i++
- exchange(A[i], A[r])
- return i
計算量
最悪ケースではjが増えるたびに交換するので .
実装
gist6642213dcdfec5d8dbf6d23f0436e01b
感想
ALDS1_5_B Merge Sortを解く話
AOJのマージソートを実装する問題です．
特徴
・配列を1要素になるまで分割してくっつき直すときに比較．
アルゴリズム
Mergesort(array, left, right)
- 要素数が1ならソート済みなのでreturn．（実装では left + 1 < right)
- 配列を半分にする．
- 左半分をMergesortに渡す（実装では再帰を使う）．
- 右半分をMergesortに渡す（同じく再帰）．
- マージ．
計算量
マージがn回，分割が回なので計算量は
．
実装
分割した配列の末尾に番兵を配置するのに注意．
gist46eccdb4e29c4cc01cc448b894cf8814
感想
マージソートに対する僕のイメージは全結合していないニューラルネット．
- 入力層にこれからソートする配列を渡す．
- 層を進むにつれて配列は分割され次の層へ．
- 一番真ん中の層が配列が1要素数になるまで分割された状態．
- この後の層では比較とマージをする．
てな感じ．これで覚えておけばそらで書けるかな．
ALDS_1_1_A: Insertion Sortを解く話
挿入ソートを実装する．
特徴
- 未ソート部とソート済み部に分けてソート
- トランプの手札を並べ替える感じ
- 挿入ソートの改良版がシェルソート
アルゴリズム
これ．
二重ループの外側と内側の進む向きが違うので注意．
計算量
内側のループのたびに要素が移動する最悪のケースを考えると
最大次数の項以外は無視するので，挿入ソートの計算量は
実装
gist9bc97b8b935211285ee025a9312ee372
感想
直感的でわかりやすいアルゴリズムだと思う．
先日，友人と大富豪をやったときも手札の並べ替えに挿入ソートを意識していた．
「国際会議論文の読み方・書き方」を読んだ話
http://www.phontron.com/slides/neubig15nlptutorial.pdf
グラムニュービック先生が書いたチュートリアルスライドである．
とても良い．
最近は論文を読むときに，このスライド通りに書かれているか自分の頭の中でチェックしている．たまにチェック項目を忘れるので，全部のページを印刷したくらい気に入っている．
グラム先生はNLP分野の方で「自然言語処理の基本と技術」という本も書いている．
ちなみに一か月前くらいにこの本を読んだが，ビタビアルゴリズムが漢字変換にどう使われているのか等，なるほどなぁと思う部分が多かった本である．
「国際会議論文の読み方・書き方」は主にNLPの会議を例として説明が進む．
良い論文とは？，論文執筆のプロセス，論文の各章の役割と書き方，ダメ例，執筆後にやること，が書かれており「国際会議」に限った話ではなく，B4や修士など論文を書き始める人に役に立つはずだ．
特にこのスライドが良いと思った理由は，普段自分がわかりやすいなぁと感じる論文がこのスライド通りに書かれていることに気づいたからだ．
「問題の定式化」を明確に書いているか，いないかの違いはわかりやすさに大きな影響を与える．問題を定式化することで，読者は提案法がベストな解決手段なのか判断しやすくなるし，「こうゆう手法でも解けるのでは？」と読者に新しいアイディアを想起させやすくなると思う．
また，
完成された研究なんてない．書いてみよう！
この部分を読んで，問題点を見つけるための実験と，手法を評価するための実験は区別しなきゃなぁ，と自分は感じた．実験をすれば用いた手法の粗などすぐ見つかるし，ましてや修士レベルでは実験をする前から粗があるのが分かっている場合もあるだろう（もちろんダメ例であるが，実験をしない限り結果が出ないわけで修論が書けないのである）と思うのであった．
ちなみに参考文献にあるSimon先生の論文の書き方
も読んだ（Youtubeに講義ビデオもある）．
だいたいグラム先生と同じ主張をしているが，abstractの4文の内容が若干異なる．自分はSimon先生のほうがしっくりくるかなぁ．これも時間があったら感想を書こう．
「研究者を目指す普通の学生諸君に」を読んだ話
http://hflab.k.u-tokyo.ac.jp/staff/hori/essay/kenkyuu.html
を読んだ．
東京大学の堀先生という方のエッセイである．
博士課程の学生or目指している学生に向けた内容だが，修士の学生も読んでピンとくるものがあるだろう．
研究を（まじめに）する学生は人生や生活を送るうえでこれを心掛けるべきだ，的な十か条がそれらの詳細とともに書かれている．
全ての主張に説得力があり，「うむうむ」と頷きながら読んだが，
"つまらん研究をする人はつまらん人間"
という読んでて苦しくなる部分もあった．
もう自分はこの春就職してしまうので，修士に入ったときに読みたかったなぁと思う反面，ある程度の試行錯誤で研究をしてきて失敗もした学生（研究計画，スケジューリング，昼出勤徹夜，論文締め切り間際の後悔をしてきた学生）じゃないと共感できないかもしれない．
OpenCVでSlidingWindowする話
物体検出や顔検出とかで必要になるSlidingWindowのメモ
参考
上のサイトを見れば問題なかった．
StepSideを小さくするとちょっとずつパッチ切り取るようになる．
あとはこのパッチから特徴抽出とかして分類器にぶち込めばいいのかな？
gistd7ab974c883c2bc4bf3dd6e76d10486a
C++でdlibのSVMを動かした話
巷ではディープラーニングが流行っていますがdlibを使ってサポートベクトルマシーンをやってみる話です．
結論からいうと
- 凄い使いやすかった．
- いい感じに抽象化されている．
- パラメータの調整も何をやっているのか分かりやすい．
てな感じ．
この記事ではライブラリの導入から実際に動かすまでをつらつら書きます．
マシンのOSはWindows10です．
dlib C++ Library
ちょうど今研究でSVMを使って画像をちょこちょこする予定で，簡単に使える機械学習ライブラリを探していました．
機械学習のライブラリというとScikit-learnが有名ですが，僕はC++で書かなければいけなかったので他に探していたらdlibにたどり着きました．
公式を見てみると一通りの機械学習の手法がそろってる感じ．
畳み込みネットワークとかディープ系もあるみたいです．
あとデータはあるけど，どんな手法を使ったらいいのか分からない人のためにYes/Noクエストシートみたいなのがあるんですがこういうのは機械学習にそこまで詳しくない人にはいいですね．
ダウンロードからサンプル動くまで
公式の左下あたりに青い「Download dlib...」からダウンロード．
僕が使ったバージョンは19.2でした．
解凍してみるとCMakeListsがあったので「うげっ...」と思いましたが，手順をすでに詳しく書いてくれている人がいました．
というか公式に書いてある手順で全く問題なかった．
dlib C++ Library - How to compile
僕はVisualStudio2015だったので何も変更せずに成功しました．
ビルドは6分くらいかかりました．
そして，サンプルの中のsvm_exを動かしてみる．
動いた..
なにやら見える「cross validation..」の文字．交差検証をやってくれてるみたい．
それは分かるけど他の値がなんだかわからなかったのでソースコードを見てみる．
nuとかgammaのパラメータがいまいち分からない...そういえばOpenCVのSVMを動かしたときもよく分からなかった．
ちょっと調べてみると
このサイトがSVMのパラメータについてわかりやすかったです．
ただnu-SVMがまだもやっとしていたんですが
http://www.ism.ac.jp/~fukumizu/ISM_lecture_2006/svm-ism.pdf
この資料に書いてあった．nuは訓練データのうちいくつ誤分類を許すかを決める割合の上限値ってことかな？
交差検証の結果に2つ値があるけどソースコードのコメントによると真陽性/陽性と真陰性/陰性らしい (感度とかいうやつ？）．
値が0.99と0.99 だったり 0.3と0.3だったり，よく教科書にある「ハイパーパラメータの決め方が結果にも影響する」ってやつがよくわかります．
その他にサンプルを動かして分かったことは
- 陽性の確率も計算してくれる
- 学習した決定関数をdatファイルとして保存が可
- 決定関数に関与するサポートベクトルの数を精度を保ったまま減らす機能があるらしい
です．実際にこの機能を使って269個のサポートベクトルを10個に減らしても精度は下がってませんでした(むしろ上がってる？）．
まとめ
dlibを使ってSVMを動かしてみました．
僕が動かしたsvmは正確にはnu-svmみたいです．c-cvmも動かしたんですが凄い遅かった...なんでだろ？
OpenCVのSVMも使ったことがありますがdlibのほうが他人におすすめできる．理由はただOpenCVのsvmで沼にはまったから...
OpenCVは2系と3系でSVMの使い方が結構変わっていた（スマートポインタを使うようになってた）．
