読者です 読者をやめる 読者になる 読者になる

/home/cympfh/

はてなブログはクソなのでやめます => https://hackmd.io/s/SyQBwu6Kg#

Rust Advent Calendar 2016 - 11日目

この記事は Rust Advent Calendar 2016 - Qiita 11日目のために書かれました.

qiita.com

requirements

box シンタックス及びパターン (box_syntax box_patterns) を使いたいので、 rustc 1.15.0-nightly 処理系を用います.

rustlearn

色々ありました. 色々あって 12/11 の記事を18日の夜に書いています. 予告では 「rustlearnで遊びます」 としていました. 12/10 の方が Rust による機械学習フレームワークである rusty-machine を紹介していたので、その流れで同じく機械学習フレームワークの rustlearn を紹介するつもりでした.

機械学習がしたいです (あるいは他の解決方法がわかりません). しかし世の中の機械学習フレームワークはとかく、猫も杓子も Python です. 場合に依っては恐ろしいことに Python2 で書かれたものもあります. 恐ろしいですね. Python が大好きな人間が世の中に大勢いらっしゃるのは承知ですが、できれば Rust のような、型安全でメモリ安全な言語で書きたいです. その点で leaf は本当に残念です. ディープラーニングフレームワークはどうせ大体、コアな部分は C言語でそして CUDA なので、Python なのはガワの部分だけなので速度は関係なくて、あとは書きやすければなんでもいいんでしょう. だからってなんでPythonなのかはしらんが.

rusty-machine ではディープラーニングをすることは出来ませんが、それ以外の有名どこの機械学習な分類器やクラスタリング手法が多く実装が揃っていてメンテナンスもされてるようなので、有用なフレームワークの一つ (ほとんど唯一つある内の一つ).

個人的にはとにかくRust で機械学習がしたい (他にすることがない) のですが、とにかくフレームワークが全然無いのでこんなものを紹介するつもりでした.

github.com

個人で作られてるものなので、あんまりメンテナンスが期待できないですが.

rustlearn も rusty-machine と同様に、ディープナントカ以外の定番の手法の実装をもりもり盛り込んだフレームワークという感じです. ただ、こちらには Factorization machines (FMs) という良さ気な予測器の実装が入ってます. というわけでこれを使った例を示してアドベントカレンダーにするつもりだったのですが、あんまり良い例と気力がないのと興味が巨大数に移ってしまったのがあって、アドベントカレンダーへの投稿を拒絶して早一週間...

予習事項

まずはこれを読んで下さい.

comic.pixiv.net

今回触れるのはこの中の 002 に出てくる B関数です.

B関数

B関数は次のような関数です

  •  B: (N, N) \to N
  •  B(0, n) = f(n)
    •  f は適当な簡単な関数. ここでは「寿司 虚空編」と同様に  f(n) = n + 1 とする
  •  B(m, 0) = B(m-1, 1)
  •  B(m, n) = B(m-1, B(m, n-1))

コンピュータ科学に馴染みのある人に取っては、アッカーマン関数の亜種程度に見えると思います. 私はそう思っています.

B関数の計算

「寿司 虚空編」の 002 では例として  B(3,3) を計算するのに無茶苦茶導出が長い、という説明が為されています. 実際にプログラムシてみたいと思います.

式の定義

計算の対象は式です. 式を記述する必要があります. そのために記述出来る式を定義します.

扱うべき式は、値 (i32) と足し算と関数 B です. 足し算は2つの値の和と求めるような二項関数だとします B は定義から二項関数です.

次は式の定義です.

#[derive(Clone, Debug)]
enum Expression {
    Value(i32),
    Add(Box<Expression>, Box<Expression>),
    B(Box<Expression>, Box<Expression>),
}

use Expression::{Value, Add, B};

これを用いて具体的な式を定義してみます. Debug を導いてもらってるので {:?} でフォーマット出力ができます.

let e = Value(1);
println!("{:?}", e);
// => Value(1)

let f = B(box Add(box e.clone(), box e.clone()), box Value(2));
println!("{:?}", f);
// => B(Add(Value(1), Value(1)), Value(2))

式の計算

式を計算する手続き eval を書いてみたいと思います. 何をやってるかはソースコードが語っているので日本語での説明は蛇足だと思います.

fn eval(e: &Expression) -> i32 {
    match *e {
        Value(x) => x,
        Add(box ref x, box ref y) => eval(&x) + eval(&y),
        B(box ref e1, box ref e2) => {
            let m = eval(e1);
            let n = eval(e2);
            if m == 0 {
                f(n)
            } else if n == 0 {
                eval(&B(box Value(m - 1), box Value(1)))
            } else {
                eval(&B(box Value(m - 1), box B(box Value(m), box Value(n - 1))))
            }
        }
    }
}
let e = B(box Value(3), box Value(3));
let result = eval(&e);
println!("=> {}", result);
// => 61

 B(3,3)=61 なので合ってます. 「寿司 虚空編」 002 では「こんだけやって61か!」と呆れられています.

さてしかし、この eval には味わい深さがありません. 「こんだけやって」の「こんだけ」を知らないからです.

「こんだけ」の出力

式の簡約を小さな単位でステップ実行して毎回出力させる. 具体的には次のルールを実装した手続きをステップとします.

  1. 構成性原理に従って外側から再帰的に式を読む
  2. 読んだ式が Value(_) なら、何もしない
    • 何もしない、とは、読んだ式を置き換えない、そのままにしておくこと
    • 「簡約できなかった」「失敗した」というニュアンス
  3. 読んだ式が Add(Value(m), Value(n)) なら数 m n からAdd を具体的に計算して式を計算結果で置き換える
    • これは確かに式を置き換えるので「簡約に成功した」
  4. 読んだ式が上以外の Add(e1, e2) なら、e1 e2 の簡約して置き換える
    • ただし、e1e2 もどちらも簡約されなかった (式の置き換えが行われなかった) 場合は、Add(e1, e2) の簡約も失敗する
  5. 読んだ式が B(Value(m), Value(n)) なら数 m n からB を具体的に計算して式を計算結果で置き換える
    • これは確かに式を置き換えるので「簡約に成功した」
  6. 読んだ式が上以外の B(e1, e2) なら、e1 e2 の簡約して置き換える
    • ただし、e1e2 もどちらも簡約されなかった (式の置き換えが行われなかった) 場合は、B(e1, e2) の簡約も失敗する

Add のルールと B のルールは同じなので、やや冗長.

例えば B(B(0,1), 2)B(2, 2) に展開される ( f(n)=n+1).

簡約という操作は所詮、式というデータの置換にほかならない. マクロ展開を連想してしまう (C言語とかのマクロじゃなくて、Lisp で使えるような本物のマクロのこと).

Rust には本物のマクロがあるので、なんとかマクロで表現できないか調べてたが特に無さそう. つまり、マクロなデータを標準出力する方法と、1ステップだけマクロを展開する手続きというのが無い.

以上のルールを実装したのが次の expand 手続き.

fn expand(e: &Expression) -> Option<Expression> {
    match *e {
        Value(x) => None,
        Add(box ref e1, box ref e2) => {
            match (expand(&e1), expand(&e2)) {
                (Some(Value(m)), Some(Value(n))) => Some(Value(m + n)),
                (Some(f1), Some(f2)) => Some(Add(box f1, box f2)),
                (Some(f1), None) => Some(Add(box f1, box (*e2).clone())),
                (None, Some(f2)) => Some(Add(box (*e1).clone(), box f2)),
                _ => None
            }
        },
        B(box Value(x), box Value(y)) => {
            if x == 0 {
                Some(Value(f(y)))
            } else if y == 0 {
                Some(B(box Value(x - 1), box Value(1)))
            } else {
                Some(B(box Value(x - 1), box B(box Value(x), box Value(y - 1))))
            }
        },
        B(box ref e1, box ref e2) => {
            match (expand(&e1), expand(&e2)) {
                (Some(f1), Some(f2)) => Some(B(box f1, box f2)),
                (Some(f1), None) => Some(B(box f1, box (*e2).clone())),
                (None, Some(f2)) => Some(B(box (*e1).clone(), box f2)),
                _ => None
            }
        }
    }
}

B(3,3) がやばいのは分かってるのでまず B(1,1) で実験

let mut e = B(box Value(1), box Value(1));
while let Some(f) = expand(&e) {
    println!("=> {:?}", &f);
    e = f;
};

出力は以下の通り.

B(Value(1), Value(1))
=> B(Value(0), B(Value(1), Value(0)))
=> B(Value(0), B(Value(0), Value(1)))
=> B(Value(0), Value(2))
=> Value(3)

まあ、こんなもんでしょう.

次は一つ大きくして B(2, 2) を試してみます.

B(Value(2), Value(2))
=> B(Value(1), B(Value(2), Value(1)))
=> B(Value(1), B(Value(1), B(Value(2), Value(0))))
=> B(Value(1), B(Value(1), B(Value(1), Value(1))))
=> B(Value(1), B(Value(1), B(Value(0), B(Value(1), Value(0)))))
=> B(Value(1), B(Value(1), B(Value(0), B(Value(0), Value(1)))))
=> B(Value(1), B(Value(1), B(Value(0), Value(2))))
=> B(Value(1), B(Value(1), Value(3)))
=> B(Value(1), B(Value(0), B(Value(1), Value(2))))
=> B(Value(1), B(Value(0), B(Value(0), B(Value(1), Value(1)))))
=> B(Value(1), B(Value(0), B(Value(0), B(Value(0), B(Value(1), Value(0))))))
=> B(Value(1), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(1))))))
=> B(Value(1), B(Value(0), B(Value(0), B(Value(0), Value(2)))))
=> B(Value(1), B(Value(0), B(Value(0), Value(3))))
=> B(Value(1), B(Value(0), Value(4)))
=> B(Value(1), Value(5))
=> B(Value(0), B(Value(1), Value(4)))
=> B(Value(0), B(Value(0), B(Value(1), Value(3))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(1), Value(2)))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(1), Value(1))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(1), Value(0)))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(1)))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(2))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(3)))))
=> B(Value(0), B(Value(0), B(Value(0), Value(4))))
=> B(Value(0), B(Value(0), Value(5)))
=> B(Value(0), Value(6))
=> Value(7)

そこそこ計算が大きくなりました.

ではいよいよ B(3, 3) で実行します.

$ ./run.exe | head -n 30
B(Value(3), Value(3))
=> B(Value(2), B(Value(3), Value(2)))
=> B(Value(2), B(Value(2), B(Value(3), Value(1))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(3), Value(0)))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(2), Value(1)))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(1), B(Value(2), Value(0))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(1), B(Value(1), Value(1))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(1), B(Value(0), B(Value(1), Value(0)))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(1), B(Value(0), B(Value(0), Value(1)))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(1), B(Value(0), Value(2))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(1), Value(3)))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), B(Value(1), Value(2))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), B(Value(0), B(Value(1), Value(1)))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), B(Value(0), B(Value(0), B(Value(1), Value(0))))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(1))))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), B(Value(0), B(Value(0), Value(2)))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), B(Value(0), Value(3))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), Value(4)))))
=> B(Value(2), B(Value(2), B(Value(2), Value(5))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(2), Value(4)))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(2), Value(3))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(2), Value(2)))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(2), Value(1))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(2), Value(0)))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), Value(1)))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(0), B(Value(1), Value(0))))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(0), B(Value(0), Value(1))))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(0), Value(2)))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), Value(3))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(0), B(Value(1), Value(2)))))))))


$ ./run.exe | tail
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(52))))))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(53)))))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(54))))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(55)))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(56))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(57)))))
=> B(Value(0), B(Value(0), B(Value(0), Value(58))))
=> B(Value(0), B(Value(0), Value(59)))
=> B(Value(0), Value(60))
=> Value(61)

$ ./run.exe | wc -l
2433

お疲れ様です. こんだけやって 61 でした.