[C++]deep learningのC++11実装を良い感じにした+解説文つけた

以前CNN(畳み込みニューラルネット)の実装を公開して放置していたら、じわじわstarが溜まってきた。(みんなCaffe使ったほうがいいんじゃ…)と思いつつも、少し前からコードを整理して少し良い感じにしたので、改めて宣伝。

github.com

良い感じなところ

  • ヘッダをincludeするだけでOK、外部依存なし
    • 並列化したい場合だけintel TBBが必要
  • 最近の流行を含め、最小限のパーツは揃っている
    • 活性化関数はtanh/sigmoid/softmax/relu/leaky-reluなど
    • ソルバーはSGD/adagrad/RMSPropなど
    • 詳しくはreadme
  • そこそこ速い
    • GPUには勝てないが、MNIST程度のタスクなら10分程度で終わる
  • コードが(比較的)少ない
    • 全部で3000行程度

こんな感じに、C++のコードでモデルを定義して学習します。

// 損失関数とソルバーを先に指定
network<mse, adagrad> net;

// レイヤーを上から順に積む
net << convolutional_layer<tan_h>(32, 32, 5, 1, 6) // 32x32in, conv5x5, 1-6 f-maps
    << average_pooling_layer<relu>(28, 28, 6, 2) // 28x28in, 6 f-maps, pool2x2
    << fully_connected_layer<relu>(14 * 14 * 6, 120)
    << fully_connected_layer<softmax>(120, 10);

// 学習データのロード
std::vector<label_t> train_labels;
std::vector<vec_t> train_images;
parse_mnist_labels("train-labels.idx1-ubyte", &train_labels);
parse_mnist_images("train-images.idx3-ubyte", &train_images);

// 学習 (50-epoch, 30-minibatch)
net.train(train_images, train_labels, 30, 50);

// 重みを保存
std::ofstream ofs("weights");
ofs << net;

ふつうにPC上で使う分にはCaffeやChainerをお勧めしますが、tiny-cnnはコードが小さいので、「なんらかのコードを読むことで、deep learningへの理解を深めたい」という方の役には立てるかもしれません。実装も黒魔術的な事はやらずに、なるべく素直に書いているつもり。というわけで、簡単なニューラルネットの解説+実装の解説もwiki上に公開しました。

実装ノート · nyanp/tiny-cnn Wiki · GitHub

PRMLとか深層学習本よりも初歩的な内容にとどまっていますので、より詳しくはこれらの本を読みましょう。

パターン認識と機械学習 上

パターン認識と機械学習 上

深層学習 (機械学習プロフェッショナルシリーズ)

深層学習 (機械学習プロフェッショナルシリーズ)

内容の問題点、間違いについてはissuesまで投稿お待ちしてます。

子供が生まれた

3月に1人目の子供が生まれた。

里帰り出産していた妻がGWに戻ってきたので、3人暮らしを始めて3週間ほど経ったところ。子供の成長はほんとうに早く、こちらが笑うとつられて笑ってくれるようになったり、怖い夢を見て泣くようになったり、眠いときに目を手でかく仕草が身に付いてきたりと、一日ごとに新たな成長を見せてくれる。継続的デリバリーという感じがする。

子供が笑ってくれると、他のすべてがどうでもよくなるほど嬉しい。一日一日がかけがえのない時間という実感をもっている。

f:id:nyanp:20150506112102j:plain

ドメイン駆動設計読書会、第4回のメモ

【限定募集:第1回の申込者のみ、参加登録可能】第4回ドメイン駆動設計読書会@大阪 - ドメイン駆動設計読書会@大阪 | Doorkeeper

第1章後半~第2章アタマあたりまで読んできた。この勉強会、ペースは非常にゆっくりだけど、ユビキタス言語ってどういう意味なのかとか、「厳密なモデル」が言う厳密さってどういうモノなんだよとか突っ込んでて面白い。ドメイン駆動開発というドメインについてワイワイやりながら一緒に考えてる感じがする。以下はメモなので参加した人以外には伝わらないと思うけど、これもドキュメントで全部表現するんじゃなくてコミュニケーションでモデルを深めていくDDDっぽい雰囲気がある(適当)。

第1章

隠された概念を引き出す(p.18)

  • オーバーブッキングポリシーの計算を外出ししている。→すぐに分かるものかどうか?
  • 原則:意図を適切な粒度で表現する。
  • 図1.10のモデルは業務知識が可視化されていることがポイント。要件定義とコードの間でトレーサビリティを確保すると分かりやすくなる。

深いモデル(p.20)

  • ここ重要!!一番重要by久保さん
  • 業務知識が無いと、開発者が一生懸命考えてもブレークスルーで船荷証券というモデルは出てこない!プロの視点が欠けている
  • (そもそも業務知識が無いとアーキテクチャが完成しないというのは正しいあり方なのか)
  • PCO(経営管理用語:Policy-Control-Operation) という考え方がある。船荷証券というのは業務のエキスパートが分析を行った段階で、Control層に出てくるもの
    • 駐車場のモデリング*1において、業務レベルで考えると素朴なモデル(車、ゲート…)にとどまる。管理レベルで考えると深いモデル(スペースと時間)に至ることができる。
  • DDD本自体には、モデリングのやり方それ自体は16章「責務のレイヤ(p.456)」まで出てこない。
  • よくいるユーザー「現状のやり方を変えたくないが、問題を解決したい」
    • ユーザー自身PCO的な考え方を持っているわけではない。ユーザーにメリットがあるのなら、一緒に整理してあげる
    • 実務的には上から攻めると通りやすい(下の実務者ほど、今のやり方を変えたくない傾向)
  • コンサルタント:各業種のモデルのテンプレートを持っていたりする。(用語集、モデルの元ネタになる)
  • 深いモデルに至るのに数カ月もかかるのはなぜ?
    • 開発者が対話する顧客も末端だったりする(=業務レベルの知識しかない)。
    • コンサルタントだと、より顧客の上層とコミュニケーションをとることになるので、管理レベルでモデルを考えやすいのかも

第2章

ユビキタス言語

  • DB定義なんかでシノニム、ホモニム(言語と意味のn対1,1対n関係)が起きることがある
  • ここで言っているのは単に用語集作ろう、ではない。辞書があれば言語がしゃべれるわけではない。単に言葉をそろえましょう、というだけの話ではない。
  • ユビキタス言語を会話に使うことで、DSLのセマンティクスをテストしている -「厳密に」とは?…ユビキタス言語の属性、操作だけDSLが構成できる、ユースケースがすべて説明しきれる位の厳密さ
  • すべてのコードでモデルと厳密に結びつけるのはコストかかる。ドメイン層とそうでないものを区別する
    • たとえばdomainパッケージ以下はすべてユビキタス言語で使うとか
  • パッケージ境界とモデル境界が一致しないことはよくある
    • コンテキストをまたがったモデル
    • コンテキストマップをつくる。→実装上ではインターフェースのような型の仕組みを使う。異なるモデルそれぞれで継承する、型ツリーをつくる
  • 会話は日本語だけど、コードは英語が多い。どうする?
    • モデルを表現するソースコードやDB定義に日本語を使ってもよい。英語表現が難しいドメインもある
    • ツールや言語上の制約に対する折衷案として、英語の接頭辞を付けるとか、ローマ字を使うのもあり
    • でも実際カラム名がローマ字になっていたりすると違和感ある
      • 一貫性大事。一貫していれば違和感消える

例2.1 貨物輸送プログラム(p.27)

  • 太字がモデルの語彙
  • 経路仕様をあえてモデルとして登場させるのは、素朴な(現実のモノをクラスに写像するような)OOPとは一線を画している。モデルの意図を明確にしようとしている
  • 経路仕様クラス…ビジネスルールの検証をやっているモデル。実装上はステートレス
  • 「経路仕様」はユーザがもともとメンタルモデルに持っていたのか、モデルとして見出したのか?
    • この例を見ると、開発者が新しいモデルを考え出した。
    • 開発者は「仕様パターン」のようなメタモデルを持っていたことで、経路仕様というモデルを思いつけた。

声に出してモデリングする(p.30)

  • 自然言語の文法に乗せてはいるが、よりDSLに近くなっている。
    • 経路選択サービスは、経路仕様を満たしている輸送日程を見つける。」→ユビキタス言語で表現しきっている。
    • 表現できてないなら、モデルが不十分

[C++]C++でeval(), それWandboxでできます

C++でevalできないなんて誰が言ったのか。C++,JavaScript,C#,perl,python,ruby,mruby,Erlang,haskellぜんぶC++から簡単にevalできます。

書いたもの

https://github.com/nyanp/frisbee
200行弱で書けてしまった。コンパイルにはboost,実行にはcurlが必要。evalしたい言語の環境は不要。

サンプル

#include <iostream>
#include "frisbee.h"

using namespace std;
using namespace frisbee;

int main(void)
{
  try {
    // eval
    // 受けたい型で特殊化する。コンパイルエラーなら例外
    cout << eval<string>("C++", "#include <iostream>\n int main(){ std::cout <<\"C++\"<< std::endl; }");
    cout << eval<string>("C#", "class Test { static void Main(string[] args){System.Console.WriteLine(\"C#\");}}");
    cout << eval<string>("haskell", "fib = 1:1:zipWith (+) fib (tail fib)\nmain = do print $ take 5 $ fib");
    cout << eval<string>("perl", "print (1..10)");
    cout << eval<int>("ruby", "$,=\" \"; p (1..10).inject(0) {|sum, i| sum + i }");

    // コンパイル通るかどうかチェック
    auto result = compile("C++", "#include <iostream>");
    if (result.is_error())
        cout << result.compiler_error(); // コンパイルエラーを表示

    // compile from file
    result = compile_fromfile("C++", "foo.cpp");
  }
  catch (const exception& e)
  {
    cout << e.what();
  }
}

しくみ

  • おもむろに犬小屋ことWandboxにコードを投げる
  • 返ってきたらpicojsonでパース
  • lexical_castして返す

殆ど自分では何もやっていない感じ。犬にひたすら投げて返ってくるのを待つだけです。Wandbox APIは以下。

wandbox/kennel/API.rst at master · melpon/wandbox · GitHub

負荷を気にしつつ、用法用量を守って正しく投げましょう。

ドメイン駆動設計本の読書会に参加してきた

エリック・エヴァンスのDDD本、大阪で読書会が開催されているというので行ってきた。

【限定募集:第1回の申込者のみ、参加登録可能】第2回ドメイン駆動設計読書会@大阪 - ドメイン駆動設計読書会@大阪 | Doorkeeper

勉強会はまだ1章途中、自分で読んだのもまだ4割くらいだけど、得るものが多い本&勉強会だと思う(主催の@kuma_nanaさんありがとうございます)。

エリック・エヴァンスのドメイン駆動設計 (IT Architects’Archive ソフトウェア開発の実践)

エリック・エヴァンスのドメイン駆動設計 (IT Architects’Archive ソフトウェア開発の実践)

ざっくりに言うと、ドメイン(ユーザーの問題領域)のことを深く考えてソフトウェア作っていきましょうという本。これとこれを実践すればDDDだとか、こういう図を描けばDDDだぞみたいな事よりも、根本にある考え方と、それを実現するためのパターン集といった趣。読む前は○×駆動が世の中沢山あるなあと思っていたけど、TDDとかMDDと相反するものではなくて、むしろ一緒に組み合わせて効果を発揮する感じ。考え方については序文に(たぶん)大事なことが書いてある。

根本的には、DDDを駆動している原則は次の3つだけです。

  • コアドメインに集中すること。
  • ドメインの実践者とソフトウェアの実践者による創造的な共同作業を通じて、モデルを探求すること。
  • 明示的な境界づけられたコンテキストの内部で、ユビキタス言語を語ること。

ドメインに対する知識をモデルに落とし込み、プロジェクトに関わるドメインエキスパート*1やらプログラマやらがモデルを継続的に洗練させていく。モデルや実装、コミュニケーションやドキュメントに使われる用語はすべて統一して(=ユビキタス言語)、誤解が生じないようにする。会話やコードに苦しい面が現れたなら、よりよい表現を探求しなければいけなくて、それはよりよいモデルを探求していることに繋がる。モデルと実装の言葉を強制的にそろえることで、プログラマがみんなモデルのことを考えることを強いられる(?)というのが面白いと感じた。ドメイン層のコードをリファクタリングするのはモデルのリファクタリングに等しいし、逆によりよいモデルを見つけ出したのならコードにも反映させる必要がある。

当たり前のことを当たり前にやる

1章に入る前のところで、コメディ番組の撮影に関するエピソードが出てくる。あるシーンの撮影が上手くいかなくて何度も撮り直し、ようやく面白い映像が撮れたんだけど、画面に一瞬ゴミが映りこんだのを理由に編集者が別の全然面白くないテイクを採用しちゃいましたという話。同じ節で、技術力のある開発者はドメインを学んだりモデリングするのを他人任せにして、複雑なフレームワークに取り組んでみたりコンピュータ科学っぽい問題を解くことに集中したがるという話があった。この辺はドメイン駆動設計をやる/やらない以前の問題で、手段と目的(=ユーザーに価値を届ける)を間違えちゃ駄目でしょという当たり前の話だと感じた。「ドメイン駆動設計を実践する」というと難しい響きだけど、その背後にある「ドメインの事をしっかり考えて仕事する」、というのはソフトウェアに限らず当然やるべき事だろうと思う。

とはいえ本質的に複雑なソフトウェアに立ち向かう時には、当たり前のことを当たり前にやるのがすごく難しい。それを何とかやっつけるための仕組みとしてドメイン駆動設計が提案されているんだろうなというのが今の所の感想。

たとえばウォーターフォールだと、まずアナリストがドメインを分析して分析モデルを作り、後から開発者が設計を行うみたいな事をやる。分析モデルは実装の都合のことを考えないので、開発者から見ると「絵に描いた餅」みたいに見えることがある。結局開発者で別の抽象化を考えてしまったりで、分析モデルに組み込まれていたドメインの知識が失われていってしまう。逆に、実装をしていく中でよりよいモデルが見つかっても、分析モデルに反映されることもない。
(話が逸れるけど、以前モデリングに関する講習を受けて、分析モデルは実装の都合考えてないけどここからどうやって実装するんですかと質問したら、分析モデルは分析したら捨てますって答えが講師から返ってきて驚いたことがある。食材をひたすら煮込みに煮込んでから、出汁の出た煮汁を全部捨てて残りを食うイギリス料理のコピペを反射的に思い出した覚えがある。どうでもいい。)

一方アジャイルっぽいやり方で継続的にリファクタリングしていくにしても、どういうドメインモデルが表現されているのかを無視してコードに手を加えていくと、無駄に複雑になっていってしまう。部分部分を見るとおしゃれに設計されているように見えるんだけど、全体としてどういう価値を届けるソフトウェアなのか分からなくなってしまったり、変更に強いコードを書いているつもりでいて、実際に変更があった時にはなんだか沢山書き変えなきゃいけない、柔軟性を持たせた筈の部分が重荷になっているとかいう事態になりかねないようにも思う。ここらへんを全部プログラマのセンスの問題に帰着させるよりは、ドメインモデルをみんなで磨いていく中で良い設計を見出していくドメイン駆動の考え方のほうがしっくり来る。

設計が、あるいは設計の中心となる部分が、ドメインモデルに紐づいていないならば、そのモデルにほとんど価値はなく、ソフトウェアが正確であるかどうかも疑わしい。同じように、モデルと設計された機能との紐づけが複雑だと理解するのが難しく、実際には設計が変更された時に紐づけを維持できなくなる。分析と設計の間に致命的な亀裂が生じるため、それぞれの作業で得られる洞察は互いに活かされることがないのだ。

どう実践するか

ドメイン駆動設計は考え方っぽい本なので実践が伴わないと「ふーん」で終わる感がとても強い。「理論と実践の両輪が大事」という言葉が読書会の中でも出てきていた。じゃあ自分の組織でどう取り入れていくのか、考えているけどまだ答えは出ていない。新しい考え方○○を取り入れようとした人が、本人の理解も不十分なまま周りを巻き込んだために上手く行かず、「○○はウチでは使えないね」みたいな偏見だけを社内に残したみたいな状態は最悪なので、それは避けたい。最初は500行くらいの規模のコードで小さく実践すれば良いのでは、という話も出てきていたので、まずは小さく始めたいなという感じ。

*1:ユーザーの業務領域に対する知識と判断責任を持つ人。必ずしもユーザーである必要は無いという話が読書会の中でも出ていた

ウィンドウサイズに依存しないMin-Max Filterの実装

背景

1次元のデータ列に対して、近傍Wでの最大値/最小値を求めたい。たとえばW=3で以下のようなmin3,max3を計算したい。

input:  9,2,8,3,1,3,2,0
max3:     9,8,8,3,3,3
min3:     2,2,1,1,1,0

画像処理では膨張収縮、オープンクローズフィルタなんかによく使われている。とても基本的な信号処理だけど、naiveに実装するとデータ数N、窓サイズWに対してO(NW)の時間がかかる。

/**
 * naive implementations of min-max filter
 */
template<typename InputIter, typename OutputIter>
void minmax_filter(InputIter first, InputIter last, size_t w,
                   OutputIter min_values, OutputIter max_values)
{
    typedef typename std::iterator_traits<InputIter>::value_type value_t;
    size_t size = std::distance(first, last);

    for (size_t i = 0; i < size - w + 1; i++, ++first, ++min_values, ++max_values) {
        value_t min_value, max_value;
        min_value = max_value = *first;

        for (size_t j = 1; j < w; j++) {
            min_value = std::min(min_value, first[j]);
            max_value = std::max(max_value, first[j]);
        }
        *min_values = min_value;
        *max_values = max_value;
    }
}

うまく実装するとこれをO(N)に落とせるとか、min/maxを得るための比較回数の下限は1.5N回であるとかが分かっているようで、今回は比較回数3N回でシンプルに実装できるものを書いてみた。

実装

参考にしたのはこれ。2006年の論文。
Streaming maximum-minimum filter using no more than three comparisons per element
論文自体に30行くらいのC++コードが添付されているのでありがたい。google codeにも筆者がコードを公開している。
maxminfilters - Fast maximum-minimum filters implemented in C++ - Google Project Hosting

ただし上のコード、Streaming Filterと言いながらランダムアクセスしていたり、double型に限定していたりするので、もうちょっとSTL likeに書き直してみたのが以下。ほぼ論文の疑似コードそのまんま。

nyanp/fast-minmax · GitHub

/**
 * 1D Maximum-Minimum filters
 *
 * it implements fast min-max filter algorithms described in following paper:
 * D. Lemire, "Streaming maximum-minimum filter using no more than three
 * comparisons per element", Nordic Journal of Computing 13 (4) (2006) 328-339.
 *
 * @param first, last            [in]  forward iterators defining the input range
 *                                     [first, last) to process
 * @param w                      [in]  window size of the filter
 * @param min_values, max_values [out] output iterator defining the beginning
 *                                     of the destination range. output size is
 *                                     distance(first, last) - w + 1.
 */
template<typename InputIter, typename OutputIter>
void minmax_filter(InputIter first, InputIter last, size_t w,
                   OutputIter min_values, OutputIter max_values)
{
    typedef typename std::iterator_traits<InputIter>::value_type value_t;
    typedef typename std::iterator_traits<InputIter>::reference ref_t;
    std::deque<std::pair<size_t, ref_t> > U, L;

    U.emplace_back(0, *first);
    L.emplace_back(0, *first);
    value_t prev = *first++;
    size_t i;

    for (i = 1; first != last; ++i, ++first) {
        if (i >= w) {
            *min_values++ = L.front().second;
            *max_values++ = U.front().second;
        }

        if (*first > prev) {
            U.pop_back();
            while (!U.empty() && *first > U.back().second)
                U.pop_back();
        } else {
            L.pop_back();
            while (!L.empty() && *first < L.back().second) 
                L.pop_back();
        }
        U.emplace_back(i, *first);
        L.emplace_back(i, *first);

        if (i == w + U.front().first)
            U.pop_front();
        else if (i == w + L.front().first)
            L.pop_front();

        prev = *first;
    }

    if (i >= w) {
        *max_values = U.front().second;
        *min_values = L.front().second;
    }
}

ベンチマーク

100万要素のdoubleに対するmin/maxを窓サイズ変えながら計測してみる。計測コードはこんな感じ。

void benchmark() {
    vector<double> v;

    std::mt19937 engine;
    std::uniform_real_distribution<> dist;

    for (int i = 0; i < 1000000; i++) {
        v.push_back(dist(engine));
    }

    vector<double> minV, maxV;
    minV.resize(1000000);
    maxV.resize(1000000);

    for (int w = 5; w < 100; w += 5) {
        auto start = chrono::high_resolution_clock::now();
        minmax_filter(v.begin(), v.end(), w, &minV[0], &maxV[0]); 
        auto end = chrono::high_resolution_clock::now();

        auto diff = end - start;
        cout << w << ":" << chrono::duration_cast<chrono::milliseconds>(diff).count() << endl;
    }
}
window-size naive(ms) fast-1(ms) fast-2(ms)
5 12 63 62
10 31 68 66
20 63 66 66
30 91 67 71
40 125 66 68
50 155 65 67

fast-1が今回の実装、fast-2は論文筆者の実装。計測はVS2013 /O2で実施。

window-sizeが小さいうちはnaiveなほうが高速。どちらの実装もまだ最適化の余地がありそうだけど*1、今回の実装ではW=20あたりで逆転している。いろんなWが想定されるケースだと、Wに応じてアルゴリズムを切り替えたりすると良さそう。

所感

1次元のMin/Maxみたいな超基本的っぽいアルゴリズムでも、まだまだ改善されているんだなーと小学生みたいな感想。

*1:naiveなほうはSIMD使うとか、fastなほうはdequeのアロケータを入れ替えるとか

寝付けない時にやってること

なんだか寝付けない時に昔から実践している方法がある。

  • 全身の力を抜く
  • 頭の中に黒い球体をイメージする
  • 沸いてくる考え、言葉をその球体にすっと吸い込ませる。これを繰り返す

ブラックホール的なものに考えを吸い込ませて、何も考えてない状態をつくる。いつの間にか考えが沸いてしまっていることもあるけど、「あ、なんか考えちゃってんな」と自覚したタイミングで吸い込ませればよい。そうするといつもすぐに眠ることができる。

個人的に眠りを妨げるような思考パターンは

  • 思考の連鎖
  • 寝なければいけないという焦り、脅迫観念

だと感じていて、この方法だと前者に関してはもちろん効果があるし*1、後者に関しても「何も考えないなら、例え寝てなくても寝てるようなもんじゃないのか」→「じゃあ無理に寝なくても、考えないだけでもいいか」みたいな見方もできるので焦らなくてよい。眠る眠らないという生理現象のタイミングを自分で制御することはできないけど、「何も考えないようにする」という行為はある程度controllableだと思うので、まずはその状態を目指せばいい。
で、これが自分以外にも効くのかどうか。眠りに関して専門家でも何でもないので良く分からないのだけど、眠りに対するモデルの持ち方が自分と異なる人には効かないのかもしれない。

小川が流れている情景を思い浮かべます。
どんな川でも結構です。
小川のほとりに座って、ゆったりと流れる川面を見つめているイメージです。
次に、その小川に葉っぱが流れている情景を思い浮かべます。
何枚でも構いません。
この情景が思い浮かんだら、次に自分の心に目を向けます。
感情や物といったいろいろな思考が湧き起こるでしょう。その湧き上がってきた思考をすっと葉っぱに乗せて川に流してしまいます。

http://www9.nhk.or.jp/gatten/archives/P20120111.html

これは目的が寝ることではないんだけど、これ読んで何だか似ていると思ったので書いてみたのでした。

*1:羊が1匹…というアレも、数字のインクリメントみたいな単純操作に脳のリソースを割くことで、連鎖的にいろいろ考えるのを防いでくれるのかもしれない