carbuncleの日記

■かかずにはいられなかった

昨日川上ともこさんが昨日亡くなられたそうだ。川上さんは声優の方でリアルタイムでいろいろな役をやられていたのを見ていたので（ミトとかウテナとか式（空の境界）とか）訃報をネットニュースで見て何か書かずにはいられなかった。

本当にお悔やみ申し上げます。

■「1995年4月ぼくは彼女に出会ったんだ」

今日は俺の42型プラズマが火を噴いた。というのも空の境界のブルーレイボックスが届いたからだ。もちろん？DVD版も持っているわけだが、まぁしかし、最高だ。いやもうネットに公開されていた4章まで（どうやら5章まであったようだが）を読んだのが本当に懐かしい。あれから何年ですか、正直泣けてくる。ちなみに、式役の坂本真綾さんはエスカフローネ時代から歌声が大好きで今でも聞きまくっているわけだが、この空の境界では癖のない中性的なところがマッチしていたと思う。

で、いつ魔法使いの夜はでるんだろう？

■[機械学習]隠れマルコフモデル

この連休はBaum-Welch法による隠れマルコフモデル(HMM)の学習を実装してみた。学生時代に強化学習を勉強はしていたものの社会人になってPRML本に出会うまでまともに統計的な学習を学習していなかった中、やっとHMMにまで到達できた（PRML本を完遂したわけもなく、まだまだ勉強しないといけないけど）。もちろん、すでに強者方がPRML本読書会をしていたり、今回の話題であるHMMを実装していたりするのでネットの世界的には旬を過ぎているだろうけれども。。。

てことでこのアルゴリズムのポイント？的なところと、一応実装したという代物に対する今後の課題をメモしておく。なお、実装したのはPRML本に式が書いている出力確率を正規分布にした場合。データは間欠泉データのような正規分布を2次元平面上に3つ用意し、分布をマルコフモデルで選択し、選択した分布からサンプリングするという流れで生成した。

ポイント？

まず、Baum-Welch法は結局はEMアルゴリズムであり、基本的な方針はEステップにてKL距離を最小化すべく潜在変数の事後分布を求め、Mステップにて各パラメータを最大化（更新）する。

　ただし、独立な混合な正規分布をEMアルゴリズムで学習する際とちがって、HMMではEステップが厄介となる。PRML本にならってZを潜在変数、Xを観測変数、θをパラメータとすると、Eステップで求めたいのはP(Z|X,θ)。ところが、Zは系列の前後で関係があるので、ある時刻nに関してのZの事後分布はP(Zn|X,θ)と、P(Zn, Zn-1|X,θ)というのを準備する必要がある（ことはMステップのためにQ関数を偏微分していくなかでわかる（のだと思う））。その上、ある瞬間のZnやZn-1の分布には、過去のXだけでなく未来のXも関わってくる。

　そこで、Baum-Welch法（フォワード・バックワード法）では、ある時刻nの分布を求めるために、時刻0から前向きに計算する項(α)と時刻N(最後)から後ろ向きに計算する項(β)に分けて、うまいこと（P(Zn|...) = ??? * P(Zn-1| ...)みたいな）再帰的な式に変換することで簡単に計算できるようにしている（この感じはベルマンの方程式をTD誤差で遂次更新するのに似ている）。

　ただし、上述を実装する上で注意すべき点がある。それは、えらく計算した結果が小さくなるということ(指数的に0へ近づく)。もちろん、PRML本でも別に節があって説明されているわけだけれども、まぁ気にせず実装してかっぽりはまってしまった。解決策は、各時刻ごとにスケーリング（正規化）しておけばよい。

　Mステップは、ちょっとパラメータ数が多いけれど、独立な正規分布とほとんど同じ感じに計算できる。あとは、くるくる回せばいつの間にか収束して幸せ。

課題

　今回は、はじめてのおつかい的な感じでHMMを理解・実装することを目標とした。理解と実装それぞれで課題が残っている。

　まず、理解という点では、そんなに難しいものではないと思うけど予測分布やビタビは勉強しておかないと。あとは、カルマンフィルタなどとの関連や違い、変分法（まだ勉強中）をパラメータの部分に使ったVB版のBaum-Welchなんかもいつかは勉強したい。。あとは、趣味で未だ継続しているロボットへの応用方法を検討しないといけない。

　次に実装という点では、今回実装したのがHMM版の間欠泉データという感じでやったけれども、どうにもパラメータの初期値が観測値と離れると容易にNaNとなってしまう（数値にはすべてdouble型を使用）。きっと正規分布の中心から離れすぎて0に近づきすぎてるんだと思うけど、対応策を練らないといけない。独立な正規分布をEMアルゴリズムで学習する際、初期値はk-meansで求めるとかいうけど、そんな感じで速度的にはもちろん、妥当な初期値を設定するようにしないと。また、EMアルゴリズムなので、分散が極端に小さくなるのを監視する機構を追加する必要があるのかもしれない。とくにモデルの潜在変数が観測対象の本来持つ潜在変数の数に比べ多いと結構やばい気がする。この辺は実験しながら体で覚える必要がありそう。

※観測値を順番に線で結んでいます。

■連続して

日記を書いてみよう。今日のテーマはバブルソートです。え！？というくらい初歩の初歩たるソートアルゴリズムです。

が、なんとまぁScheme(Lisp)脳のない自分では2時間かけてやっとこさ動くものを作るのが限界でしたｗｗｗ。しかも絶対エレガントとは程遠そうなコード（beginとset!が多く手続き言語っぽい）。今後少しずつ頭を慣らそうと思う。

ところで、やってはないけどクイックソートのほうが自然に記述できる気がするなぁ。

以下、しょぼいコード。

(define A '(19 3 4 34 349 13 12))

(define local-swap 
  (lambda (r-ls s-ls )
    (if (eq? (cdr r-ls) ())
	(append! s-ls r-ls)
      (let (( cur (car r-ls))
	    (next (cadr r-ls))
	    (r-ls (cddr r-ls)))
	(if (< cur next)
	    (begin
	      (set! r-ls (cons next r-ls))
	      (set! s-ls (append s-ls (cons cur '())))
	      (print s-ls))
	  (begin
	    (set! r-ls (cons cur r-ls))
	    (set! s-ls (append! s-ls (cons next '())))
	    (print s-ls)))
	(local-swap r-ls s-ls)))))

(define bubble-sort
  (lambda (data-list)
    (let ((inner-bubble-sort 
	   (lambda (ls next)
	     (if (eq? next ())
		 ls
	       (begin
		 (set! ls (local-swap ls ()))
		 (inner-bubble-sort ls (cdr next)))))))
      (inner-bubble-sort data-list (cdr data-list)))))

(bubble-sort A)

実行結果はこんな感じ。呼び出し一回につき、一番大きな数字が一番後ろに持って行かれているのがわかると思います。

(3)
(3 4)
(3 4 19)
(3 4 19 34)
(3 4 19 34 13)
(3 4 19 34 13 12)
(3)
(3 4)
(3 4 19)
(3 4 19 13)
(3 4 19 13 12)
(3 4 19 13 12 34)
(3)
(3 4)
(3 4 13)
(3 4 13 12)
(3 4 13 12 19)
(3 4 13 12 19 34)
(3)
(3 4)
(3 4 12)
(3 4 12 13)
(3 4 12 13 19)
(3 4 12 13 19 34)
(3)
(3 4)
(3 4 12)
(3 4 12 13)
(3 4 12 13 19)
(3 4 12 13 19 34)
(3)
(3 4)
(3 4 12)
(3 4 12 13)
(3 4 12 13 19)
(3 4 12 13 19 34)
(3 4 12 13 19 34 349)

ところで書いていて感じたのが、appendってリスト処理においてはコストのかかる遅い処理なんだろうかということ。あんまりコストを意識してかけてないのはさらにさらに先の話。

すぐ追記：

bubble-sortの繰り返し条件が怪しい気がする。手続きっぽく素直にリストの長さ分ループするか、変化しなかったことをチェックするほうがよい気がしてきた。今日は眠いので、明日以降に気が向いたら考えようと思う。。。

さらに追記：

リストの長さ分ループしてみた。

(define A '(19 3 4 34 349 13 12))

(define local-swap 
  (lambda (r-ls s-ls )
    (if (eq? (cdr r-ls) ())
	(append! s-ls r-ls)
      (let ((cur (car r-ls))
	    (next (cadr r-ls))
	    (r-ls (cddr r-ls)))
	(if (< cur next)
	    (begin
	      (set! r-ls (cons next r-ls))
	      (set! s-ls (append s-ls (cons cur '())))
	      (print s-ls))
	  (begin
	    (set! r-ls (cons cur r-ls))
	    (set! s-ls (append! s-ls (cons next '())))
	    (print s-ls)))
	(local-swap r-ls s-ls)))))


(define bubble-sort
  (lambda (data-list)
    (letrec ((inner-bubble-sort
	   (lambda (ls cnt)
	     (if (> cnt 0)
		 (inner-bubble-sort 
		  (local-swap ls ()) (- cnt 1))
	       ls))))
      (inner-bubble-sort data-list (length data-list)))))

(bubble-sort A)

■久しぶりに

ちょっと前に大学の時の先輩に全然日記を書いてないといわれてしまったのを今日を思い出したｗ

てことで久しぶりに書いてみよう。

■とある

魔術の。。。ではなくて、、、科学の。。。でもなくて、とある飛空士への恋歌の4巻を読んだ。やっぱ空中戦の描写が引き込まれる。今回は、前回までのリアルな戦闘から脇役からヒーロー・ヒロインまで覚醒のオンパレード（チョイネタバレ？）で一変している面はあれ、先が先がどんどん気になって、会社の最寄駅で買ったその足で、電車に乗り、降りて歩いて寮まで携帯のLEDで照らしたりもしながら読んでしまった。

ところで、とある飛空士も大好きなんだけど、大好きなんだけど、犬村さんレヴィアタンの恋人も出してください。

■ふもっ

ついに終わりました。終わってしまいました。フルメタルパニック。もうどんだけまたせるんだと思っていたが、いやぁよかった。昔読んだなぁと思うひとはぜひ読むべき。もう読んだ後友達と1時間半も電話で熱く語り合ってしまった（汗

まだ短編とかサイドストーリは出してくれそうな気がするので余韻を楽しむ機会はありそうだなぁ。

■マクロ

Schemeのマクロです。Schemeの文法自体は学生の頃にほんの少しだけ勉強したことがあったんだけど、lisp系言語の真髄であるマクロについては全く勉強してなかった。ということで、（それ自体もマクロである）define-macroでちょっぴり勉強してみた。

今回のお題はwhen句。when句はご存じのとおり、条件(test)が合致した場合、その後ろの式(body)の要素（式）を順番に評価し、最後の要素（式）の評価結果を返す文。マクロは基本的には以下のように書ける。

(define-macro my-when
	      (lambda (test . body)
		(list 'if test (cons 'begin body))))

ここで、クオートがちょいちょい中に入っている。これがwhenより複雑なマクロになると煩雑になって大変らしい。そこで、バッククオート（クァスィクオート：quasiquote）を使うとよいらしい。バッククオートに渡される式を構成する要素（式）は基本的にはすべてクオートされる。クオートしたくない場合はunquoteもしくはその略記法である「,」を先頭に記載する。なお、クオートしたくない対象がリストの場合、unquote-splicingもしくはその略記法である「,@」を先頭に記載する。以上を踏まえて書き換えると次のようになる。

(define-macro my-when
	      (lambda (test . body)
		`(if ,test (begin ,@body))))

ちなみに、xyzzy上でgaucheを使えるようにしてくれるアドオンを導入してがんばってたわけなんですが、一番苦労したのはVisual Studioに慣れきった手でコーディングする作業だったというのは情けない話です。。。

っていってもなかなかschmeやlispで大きなコードを書くタイミングがなく、仕事（ガチガチのハードを持つ装置のデータ管理ソフト）や趣味（ロボット）ではどうしてもC++とかC#とかという選択肢をとらざるを得ない/とってしまうので身につかない。

■PS3

PCのDVDドライブを買いにいって間違えてPS3を買ってしまった。初代と比べてホント小さいのに驚き。

■0の0乗

0の0乗は1、、、と思いがちだが、0とするほうがシックリくる場合もあるってことをwikipediaを読んで知った。

■久しぶりに

つくチャレ向けのプログラムの中で強化学習を使ってみた。経路計画の部分で。それなりに大きな状態空間にただのQ学習を実装したら、最近購入したPCでも結構時間はかかるし、思いのほか最適化できていなかったしとダメダメだった。まぁ状態空間を適切に絞って、TD（λ）あたりで書き直す必要がありそうだ。てか、そもそも最適化自体は別の方法もありそう。普通どうすんのかな。まぁしかしGPSでとった参照軌道を沿って走るだけにはしたくない。

■括弧ワールド

最近仕事ではC++/CLIばかりを使っており、趣味ではC#ばかりを使っているのでプログラミングが完全に手段化してきてしまっている。まぁその奥に目的があって手段としてのプログラムというのは重要だけれども、やっぱり目的としてのプログラムを作るようなことをしたいなと思う。こんなときいつも思い浮かぶのがLispやSchemeなのだけれども、いざSchemeを書こうと思っても全然やることが思いつかない。今進めているロボットのコードではCとC#がベストな気がするし。何かLisp/Scheme最強っていうかんじのアプリネタはないものだろうか。

■順列（２）

自分メモ続き。C#で書くとこうなる。再帰を使うともう少しすっきりするだろう。

    class PermutationGenerator {
        private Stack<int[]> dataStack ;
        private Stack<int> posStack;
        public PermutationGenerator() {
            dataStack = new Stack<int[]>();
            posStack = new Stack<int>();
        }
        public void Generate(int[] basePermutation) {
            dataStack.Push(basePermutation);
            posStack.Push(0);
            while(posStack.Count>0) {
                int[] curData = dataStack.Pop();
                int curPos = posStack.Pop();
                if (curPos == basePermutation.Length) {
                    Print(curData);
                    continue;
                }
                for (int i = curPos; i < basePermutation.Length; ++i) {
                    int newPermutation = (int)curData.Clone();
                    Swap(newPermutation, curPos, i);
                    dataStack.Push(newPermutation);
                    posStack.Push(curPos + 1);
                }
            }
        }
        static void Swap(int[] permutation, int i, int j) {
            int temp = permutation[i];
            permutation[i] = permutation[j];
            permutation[j] = temp;
        }
        static void Print(int[] permutation) {
            for (int i = 0; i < permutation.Length; ++i) {
                System.Console.Write(permutation[i]);
            }
            System.Console.WriteLine();
        }
    }

■順列

順列を列挙する手順のメモ書き（自分用擬似コード）。

var EndPos := 3
Push(0)
Push({1,2,3,4})
Loop:
  if  StackSize=0 
  then 
    goto END
  var pos := Pop()  
  var data := Pop()
  if pos = EndPos 
  then 
    Output(data)
    goto Loop  
  for each var i in [pos to EndPos]
     var newData := Clone(data)
     Swap(data, pos, i)
     Push(pos+1)
     Push(newData)
End:

■[つくチャレ]試走会

8月1日は、今回初参加のつくチャレ（※１）の試走会ということで、つくばのエキスポセンター付近でデータ収集してきた。朝は曇っていて涼しいくらいだったけれども、昼から暑くなって来て汗だく状態だった。ちなみに今は日焼けがひりひり状態。

やっぱり「つくば」x「ロボット」ということで懐かしい人たちにも出会え楽しかった。試走会後の説明会でも旗振りの油田先生も変わらずノリノリで説明しているようだった。にしても、一般人が歩きまわる一般道でロボットを動かすチャンスは、大学構内といった箱庭ででしかできない研究者の人にとってはありがたいものだろう（まぁ自分はそもそも大学を卒業してから”研究”ができていないが（※２））。

ところで、産総研のRTミドルをやってる中の人がいた。個人的に、人工知能ちっくなアルゴリズムの話と、リアルタイム制約のあるミドルウェアに興味があるので、後者に関してこの人たちのロボットやその説明から面白いことが得られるといいなぁと思う。前者は、今止まっているBishop本とか論文を読み進める必要があるなぁ。

てことで、次回実験に向けて取って来たデータの解析をすすめなければ。

※１　つくばチャレンジの略。詳細はGoogle先生へ。

※２　研究の定義はいろいろでしょうが、あくまで自分の中では、研究＝だれもやっていない新規性のあるテーマをやって、公けの何か（論文など）に出力するという定義です。