Hatena::ブログ(Diary)

ぱたへね

2016-07-31

☆2週連続☆秋のTECH祭☆

https://8728448618be8a1ddef07dfbb4.doorkeeper.jp/events/upcoming

8/27、9/3の両日でイベントがあります。

8/27は発表者ですが、9/3はお客として楽しむ予定。

現場のエンジニアアカデミックの交流も目的の一つなので、学生のみなさんもどんどん来て欲しいです。

2016-01-02

GDG神戸へ行ってきたーーーー

佐藤さんと少し話した件のまとめ。

Deep Learingの学習をするときに、勾配法ではなく全探索法が使えないかというお題

勾配法よりも全検索の方がHW(ハードウェア)向けで良いよと発表しておきながら、そこはあまり考えたことが無かった。まず、勾配法のHW化については多分上手く行かない。勾配法が汎用的なアルゴリズムであり、以前そういう物が無いか調べてみたが良いのが見つからなかった。誰でも思いつくことだから、そのままHW化しても上手く動かないのだと思う。

動き検出以外での全探索法は上手く行く可能性が高い。動き検出には、ピクセルという非常に直感的で分かりやすい1の単位があったが、Deep Leaningでは何を1に持ってくるかが良く分からないし、正解は無いと思うのでこのへんでいいやってポイントを探さないといけない。動き検出と同レベルで高速化をやるとしたら僕の知識だともう大きくひねらないと駄目だ。動き検出の登場人物は、2つの画像と動きベクトル。画像を扱うDeep Learningの場合は、1つの画像と、NNのWeight(学習結果)、出力層の出力の3つ。

動き検出 Deep Leaning
入力画像 1 既知 既知
動きベクトル/Weight 知りたい 知りたい
入力画像2/出力 既知 既知

やりたいことは合っているが、動きベクトルとNNのWeightは次元数が違う。動きベクトルは2次元(x, y)なので探索範囲を全部振るのは現実的だが、NNのWightはNNを構成するユニットの数だけ振るのは組合せが爆発する。組合せ爆発をHWでやってしまうのか、別の手を考えた方が良いのか、そこを考えるのは楽しそうだ。

http://qiita.com/t_Signull/items/f776aecb4909b7c5c116

ここに書いてあるようにどこかを0と1に制限できるとHW実装と相性が良く、確率に関しても同じように2値(0, 1)、4値くらい(00,01,10,11)にまで落とせるとうれしい。

ゆっくり取り組む時間が欲しい。

2015-12-07

[] Lisp in Small Pieces Exercise 1.6 list

list関数を実装しなさいという問題。これは簡単。

evaluateにlistの分岐を追加

         [(list) (let ([args (evlis (cdr e) env)])
                    (make-list args))]

リストを作る関数

;; list exer 1.6
(define make-list
  (lambda (args)
    (if (eq? args '())
        '()
        (cons (car args) (make-list (cdr args))))))

2015-12-04

[] Lisp in Small Pieces Exercise 1.5 boolean

(defprimitive < < 2)

今の実装だと、<が素のschemeの#t, #f を返すので、俺実装系のTrue、Falseを返すようにしなさい。

俺実装系では真偽値として#t, #fではなくt, fを使うようにすると、こう書けます。

(definitial t #t)
(definitial f #f)

(defprimitive >  (lambda (x y) (if (> x y) 't 'f))  2)
(defprimitive <  (lambda (x y) (if (< x y) 't 'f))  2)

あとはevaluateの中に手を入れる必要があるのですが、戻り値のt、fを一回lookupしたら#t, #fになるので、やっつけ実装ですがこうしたら動きました。

          [(if) (if (lookup (evaluate (cadr e) env) env)

2015-12-03

[] Lisp in Small Pieces Exercise 1.4 shallow binding

Stackを使ったshallow bindingを実装しなさいという問題。

とりあえず実装してみたのですが、練習問題にしてはヘビーでした。

https://github.com/natsutan/Lisp_in_Small_Pieces/blob/master/chap1/exer1.4.scm

shallow bindingとは

1.6.2 Deep or Shallow Implementationはすっ飛ばしたので、戻って整理しなおしました。

環境が一つの連想リストで表現されているとき、変数の値を検索するコスト(lookup関数のコスト)はリストの長さに対して線形に増えます。これがdeep binidingと呼ばれる実装方法です。一方、環境とは独立して、変数単位で値を保存する方法がshallow bindingです。この場合、間接参照に基づくアクセスになるので、変数の値を検索するコストが一定になります。

hashの操作

なぜかGaucheには、この練習問題を解くためにあるような関数hash-table-push! hash-table-pop! があります。まずは使い方の整理をします。

変数を格納するテーブルを定義して、xを5、yを10に代入します。

(define table (make-hash-table))
(hash-table-push! table 'x 5)
(hash-table-push! table 'y 10)

ここでxの値を取り出してみると、5だけが入ったリストが帰ってきます。

(ref table 'x)
gosh> (5)

この状態でxに4を代入すると、refを使って(4 5)というリストが帰ってきます。carを取ると最新のxの値が取得できます。

(hash-table-push! table 'x 4)
(ref table 'x)
gosh> (4 5)

再帰っぽくxの値を小さくしていきます。

(hash-table-push! table 'x 3)
(hash-table-push! table 'x 2)
(hash-table-push! table 'x 1)
(ref table 'x)
gosh> (1 2 3 4 5)

hash-table-pop!を使うと、リストの先頭から値を取り出し削除します。

(hash-table-pop! table 'x)
gosh> 1
(ref table 'x)
gosh> (2 3 4 5)

後3回値を取り出します。

(hash-table-pop! table 'x)
(hash-table-pop! table 'x)
(hash-table-pop! table 'x)
(ref table 'x)
gosh> (5)

push、popでちょうどスタックになっています。これを使って shallow binding を実装しました。

ソース説明

まずは変数を格納するハッシュテーブルの定義

(define *variable-table* (make-hash-table))

evaluateの中でシンボルを評価するところは、refとcarで値を取り出せます。アクセスのコストは一定に見えますが、ハッシュの検索(ref)が入っています。carのコストは一定なので、変数の参照はハッシュの検索コストに依存します。ハッシュの検索コストについては、この本では説明が無かったです。

  [(symbol? e) (car (ref *variable-table* e))]

変数の更新(set!)は、今の値をpopして、新しい値のpushでOKです。

  [(set!) (let ([id (cadr e)]
                        [value (evaluate (caddr e) env)])
                    (hash-table-pop! *variable-table* id)
                    (hash-table-push! *variable-table* id value)
                    value)]

関数を作るところがこうなりました。

s.make-functionが作っているclosureの中身を見ると、eprogn body '() が関数を呼び出しているところです。関数呼び出しの前に、引数をhash-table-push!を使ってpushしていき、関数呼出し後に、hash-table-pop!で引数の値を元に戻していきます。

(define (s.make-function variables body env)
  (lambda (values)
    (map (lambda (var val) (hash-table-push! *variable-table* var val)) variables values)
    (let ((result (eprogn body '())))
      (dolist (val variables)
              (hash-table-pop! *variable-table* val))
      result)))

実行結果

(chap1-scheme-bat '((+ 3 5)))
YUKI.N> 8

 (chap1-scheme-bat
  '((set! pow (lambda (x) (* x x)))
   (pow 5)))
YUKI.N> #<closure (s.make-function s.make-function)>
YUKI.N> 25

 (chap1-scheme-bat
  '((set! fact
          (lambda (x)
            (if (= x 1)
                1
                (* (fact (- x 1)) x))))
    (fact 5)))

YUKI.N> #<closure (s.make-function s.make-function)>
YUKI.N> 120

それっぽくは動いてます。

メリット、デメリット

Deep bindingのほうが環境の扱いが楽です。例えば環境を切り替えないといけない場合でも、evaluateの引数を変えるだけで対応できます。

shallow bindingは変数の検索が速そうに見えるけども、一概にそうとも言えない気がします。

Deep bindingの場合でも、関数の引数で束縛される変数はリストの先頭に来るので、実際の検索時間はそれほど遅くはならないです。。リストの後ろのほうの変数を参照しにいく時に検索時間が線形で効いてくるデメリットが発生します。shallow bindingの場合は、関数の呼び出しと復帰時にハッシュテーブルの更新が入るので、関数呼び出しのたびにコストがかかります。少なくとも、おもちゃの処理系ではshallow bindingを使うメリットは感じられませんでした。

実用的なアプリケーションの場合はどうなるのかは気になります。

まとめ

1.6.2 Deep or Shallow Implementationの最後から

Remember, finally, that deep binding and shallow binding are merely implementation techniques that have nothing to do with the semantics of binding

というわけで、あまり気にせず先に進むことにします。