LostMemories

小野市の依頼演奏に出発する日の（夜中の）１時くらいから、研究用のプログラムを走らせてました。それはこのブログにも書いた通りです。が、１日で終わると読んでたプログラムが２日間経った今でも終わりません＾＾；なんでじゃー。

ログの時間を見てみると、１つのタスクを終了させるのに３時間かかっている模様。で、やらせているタスクの数は16個・・・。合計48時間。ちょうど２日。普通に計算間違いかもしれません＾＾；１日経てば速くする方法も思いついてて、実装方法も見当がつくんですが、実行中のプログラムが終了しないことにはどうしようもないんですけど。ま、あと数時間で終了する予定なので、もうしばらくの辛抱です。２日もPCがフル回転してたら、相当消耗しそう。

同じPCで開発と計算をするときの一番の不便な点は音楽が聴けないこと！そりゃCDなんてかけた日には、音が飛びまくり、巻き戻ししまくり。そりゃCPUが追いついてないのは理解できるんですが、１秒再生、0.5秒巻き戻しって相当イライラします。これは早いとこLANケーブルを買ってきて、サブマシンで処理するしかないですね。

研究対策というわけでもないんですが、プログラムを走らせてる最中、作業用のマシンのレスポンスが悪くなるのが嫌なんで、家に余ってるPCを計算用のマシンにしようと思ってます。

スペックは今使ってるやつの1/3くらい^^;お世辞に言っても処理を助けてくれるような代物ではありません。ですが、今後計算をさせることも増えてくるので、共同でやれば少しは早く済むかもと思ってます。とりあえずLANケーブルさえあれば簡単に通信はできるので、OS入れればすぐにでも稼働できそうな感じ。

問題は電気代。さすがに最大3000Wは行かないのでブレーカーは落ちないはずですが、長時間走らせると多少は響いてきそう。

今日、ある３行に含まれる６文字程度のプログラムミスのせいで、半日かけてやった計算が無駄だったことが分かりました。正直かなりへこみます。

プログラムはほとんどの場合、規模が大きくなればなるほどバグが含まれやすくなります。Javaの場合だと、クラスの相互関係などが複雑になればなるほどやっかいなバグになりやすいです。そんなわけで、講義なんかではクラス間の結合が極力疎になるように設計しなさいって言われるんですが・・・。

いや、今回はそんなんが原因じゃなくて、ちゃんとあってるかテストしてなかったのが一番の問題。論理的にしっかり追っていれば初めから分かる問題だっただけに、やや悔やまれます。

今日はPAAとSAXについて調べていました。インターネット上で探しても、英語の説明しか出てこないんで結構困ります。

なので、助手のO先生に講義をしていただいて概要をつかんでみました。PAA(Piecewise Aggregate Approximation)は、ある時系列データを特定の長さに分割して、その分割した区間で１つの値を出していくというアルゴリズム。たとえば、長さが100の時系列を10個に区切るとすると、最終的には10個のPAA変換されたデータ列ができます。こういう意味で、次元の削減(Dimension Reduction)ができるってわけですね。なるほど〜。

時系列データで「次元」というと、データの数のことを指すっぽいです。今までは、ベクトルみたいに、それぞれ独立したデータ列のようなイメージだったので、今日は１つ勉強になりました。

で、SAX(Symbolic Aggregate Approximation)は、PAAで変換した値を記号に変換していく部分が付け加わります。変換する基準は、正規分布（ガウス分布）に従うとして、記号数で確率分布を分割。そこにPAA変換した値と比較して記号を割り当てます。

SAXを使えば、PAAの利点とともに、距離計算の時に利点があります。同様にSAX変換したデータと距離を計算すると、実際のデータよりも必ず小さい値が出ることが証明されています。なので、距離が離れたデータは計算から除外したい場合に、SAX表現されたデータで求めた距離でその閾値を超えているなら、明らかに計算から除外できます。ここは、なかなか使いやすそうです。

実際にSAXを使うときは、単純にPAAしてから記号を割り当てるだけでなく、データをスライディングさせながら記号を割り当てるので、次元数自体はあまり減ることないそうです。

続きを読む

昨日の中間発表でつっこまれた用語の混同を直すために、ここにメモしておこうと思います。今後もこんな感じで研究に関することをまとめておけば、いざというときに役に立つかも。

まず、動的計画法(Dynamic Programing)とは、オペレーションズリサーチのなかの計画問題を解くために用いられる手法で、高校の数学などで習った線形計画法の兄弟みたいなものです。（兄弟だからといって、解き方が似ているというわけではないです。）全ての部分問題をちょうど一回解き、それぞれ答えを表に格納して、同じ問題を複数回解かないようにします。この部分問題の解から最終的な問題の解を発見します。

これに対して、分割統治法(Divide and Conquer)は最終的な問題に対して再帰的な構造を見つけ出し、小さな問題に分割してから、部分問題の解を利用して最終的な問題の解を求めるって手法のようです。

分割統治法はBottomUp的な手法なのに対して、分割統治法はTopDown的な手法と考えてよいでしょう。

群馬大学の情報系の学科の講義ホームページを参照してみると、もう少しいろいろと詳しい話を調べることができます。

さて、PAAの次は連続DPの実装です。連続DP(=continuous Dynamic Programing)ってのは、時系列データの時間軸の伸縮を許したパターンマッチのことなんです。これを使って、予兆があると思われるデータと正常データを比較します。

論文だけではなんとなくしか内容が分からなかったのですが、助手の先生に聞いたらものすごく分かりやすく教えてくれて助かりました。具体的な実装方法についてのヒントももらったので、計算部を４時間程度で済みました。あとは、適当なテンプレートを見つけて、ひたすら計算です。

次に課題となるのが、このテンプレートとなる部分の切り出し。とりあえず、どれが予兆っぽいのか分からないので、ひたすらパターンを作って演算させようかと思ってます。まずは４つから。そして徐々に伸ばして行きたいと思ってます。計算時間を短縮するための工夫も考えてますが、まずは構想を練ってからですね。

昨日・今日と１泊２日でゼミ合宿に行ってきました。合宿といっても、基本的には研究室のメンバーの親睦を深めるための旅行といった感じです。毎年、海沿いに行ってるということなので、今年は白浜に行くことになりました。

当日は10時に大学に集合。それから３時間くらいかけて目的地へ。昼食もはさみつつ、お昼過ぎには白浜に到着です。海とか温泉が売りの場所なんですが、シーズンがややはずれ気味ということもあり、あまり観光客は来てないみたいでした。

特にすることもないので浜辺へ。ここの砂がめちゃめちゃ白くて、ほんとにすごい！夕日が徐々に沈んでいくところはけっこう感動します。ぜひカップルで行ってほしいところです。

夕食も終わっておふろに。温泉につかれてすごく気分が良かったです。硫黄のにおいがちょっときつかったんですが、それもまた一興。温泉が注ぎ込まれる音だけを聞きながら、いろいろと考えていました。

で、今回一番の難所だったのが飲み会・・・。予想はできてたんですが、毎回のことながら場は紛糾。もう、研究室で飲み会をすると必ずこうなるんで嫌になります。一回でいいからゆっくり飲ませてください。てか、ゆっくり話させてください。そんなささやかな希望も持てない飲み会に、なにも意味を見出せません。

２日目は、紀伊半島の最南端の地を見てきました。運転されてたO先生は結構つかれてた模様。おつかれさまです。その後、４時間かかって神戸の地へ。振り返ってみると、飲み会のマイナス分と、その他のプラス分が相殺されたような感じ。場所はよかったんだけどな〜。毎回言われてるけど、彼の酒癖どうにかならないんかなぁ。普段すごくプログラムはできるだけに、この致命的な欠点がプラス面を吹き飛ばしてるのがすごい残念。

今日は、昨日のバイトの疲れでお昼くらいまで寝てました。どこで体調を崩したのか、かなり体がだるい状態です。

というわけで、２時くらいから大学に行ってプログラムを組んでました。昨日の時点で、明らかに非効率的な場所があったので、その場所を改良してました。それまでは、PAA変換するまでに、データを一旦正規分布のどのあたりに位置してるのかを計算してたんですが、境界線の位置を前もって計算しておけばデータを変換しなくてもよくなることに気づいたので、１時間くらいでパッパと実装。実行してみて、かなりの処理スピードの向上を実感できました。

これからは、スレッドのつながり部分をどうやって同期を取るか。システムプログラムで理論は習っているものの、使ったことがないので、今から調べます。

今日は１日中暇だったので、買い出し行ったり、服を買ったりしてました。やっぱり、まったりした生活はいいねぇ。

で、夜は相変わらずプログラム。昔からに気になっていたJUnitなるものを使ってみました。単体テストというわけではないようなのですが、まだよく使い道が分かってません。メソッドの分岐を全て網羅するようなプログラムを書くのは案外面倒だって分かりました。でも、そのおかげでバグも発見できたんでOKとしましょう。

今はひたすらPAAのプログラムを組んでます。多次元に対応するようなやつってことで、わりと面倒なことをしないといけなさそう。基本的には１組のデータに対して同じようなことを次元数だけやってやればいいんですが、問題はその後。ここから、どんな感じで集計していったらいいのかがやばそうです。

あと、Javaで正規分布のグラフの面積を求めようと思ったんですが、ライブラリが発見できずにしょうがなく自前で用意。数式は難しそうなんですが、問題を分割したらそうでもなかった。後は、積分の効率をいかに高くするか。毎回計算するのも時間がかかりそうなんですが、今まで計算してたのをCollectionとかにため込んでおくのもどうなんだろう。あまりにたくさん要素があると、検索時間もかかりそうだし、メモリ領域も食うし。このあたりは、簡単にテストしてそこそこいいプログラムを目指します。

決して「デトロイト」の事を指しているわけではありません。デトロイトもDTWというんですが・・・。

僕の言ってるDTWは、Dynamic Time Warpingのことです。これは、ある複数の時系列データを比較するときに、時間軸を調節して、類似点を見つけるためにあります。

単純に考えると、時系列データがどの程度異なるかを調べるためにはユークリッド距離を用います。ある時刻においての差分を積分していくと、時系列データがどれだけ異なるかが判別できます。ですが、これでは不十分な場合もあります。

例えば、ある人が同じ台詞をしゃべっているかどうかを調べるシステムを作るとしましょう。ユークリッド距離の場合、まったく同じスピードで同じ内容をしゃべらないと一致することはありません。これでは、役に立つシステムとはいえませんね。調べたい内容は台詞が同じかどうかであって、スピードも同じである必要はありません。このようなときにDTW距離を採用することで解決します。

そんなわけで、今研究でDTWを使うことになりました。よく使われているとはいえ、初めてなんでやや不安も。

2012/06/14 追記
DTWを行うプログラムをsourceforgeに公開しています。研究でも利用していたので、そこそこ動作するはずです。もし不具合があればご連絡ください。時間があるときに・・・対応したいと思います。
http://sourceforge.jp/projects/sticktools/