« November 2007 | Main | January 2008 »

2007.12.22

WEB+DB PRESSに記事書きました

今月号のWEB+DB PRESS(Vol. 42)でアルゴリズム・データ構造についての記事を書きました。 [出版社ページ]

結構専門的なことも書いていいとのことだったので、私が好きな範囲で自由に書かせてもらいました。
書いたのは

・連想配列(の使い方じゃなく実装)
 ・Trie
 ・Double Array
 ・Tx/Bep
・簡単な圧縮
 ・連長配列
 ・Front Coding
 ・可変長バイト符号
 ・PFOR符号(Monet DBで使われている符号法で日本で紹介するのは初?現時点で最速)
・簡潔データ構造
 ・Rank/Select辞書
 ・LOUDS
・Suffix Arrays
・BW変換とその応用

ページ数が限られていたので、できるだけ簡単な紹介程度で雰囲気を味わってもらう感じぐらいです。
(いくつかは動くコードもついてます)

今月号のWEB+DBは気合入っていて、他にも
ニコニコ動画特集、Senna特集とかあって面白いです。

美味しい部分だけ切り取って平易に解説するのは難しいですね。あえて厳密に書かないようにしたのですが、それで余計にわかりづらくなってしまったりとかあったかも。教科書とか書く人はすごいですね。

| | Comments (84) | TrackBack (2)

2007.12.15

nips 2007 tutorial

nips 2007(行ってないけど)のtutorialが例年のようにweb上から見れるようになってます [link]
たぶんそのうちvideoも公開されるのでしょう。
面白いもの揃いですが、とりあえず目についたのは次の二つかな

Learning Using Many Examples
非常に大量の訓練用データが使える場合の学習はどうすればいいのという話。結論から言うとStochastic Gradient Descent(確率的勾配降下法)が理論的にも、実践的にも優れている。
パーセプトロンスタイルの学習(Online Passive Agressive Algorithm [pdf])とか、Online Exponentiated Gradient Algorithm[pdf]とか、どんどんオンライン型学習(データまとめて見ないで、一個ずつ見てすぐパラメータ更新する)手法の優位性がどんどん示されてきてます。実装もどんどん楽になります。

Deep Belief Nets
最近の学習モデルは隠れ層(観測できない層)が無いか、多くても1層の場合が殆どだけど、旧来のニューラルネットワークのように非常に深い層を使って学習する手法が、最近多くのタスクで今の最新手法を超える高性能を挙げはじめてます。
#隠れ層の数が1つでも、それ以上でも表現できる能力は等価であることは示されているが、特徴間に高次の相関があるような有限個の訓練データを使って学習できるかということになると、多層の方がモデルを遥かにコンパクトに表現できるので、多層の方がいい。
これは学習手法の発展があったことが大きく(1層ずつgreedyに学習させてから全体をcontrastive divergenceで学習しなおす)、従来では想定できなかったような大量のパラメータ、層数で学習、推定ができるようになってて、文書の関連度合の高速なhashingとか、従来想定されていない用途にも使われるようになってます。[link]

| | Comments (0) | TrackBack (0)

2007.12.12

SSEとかWaveletとか

研究とか仕事以外にもいろいろ興味がわくもので。

研究とも関係しているのですが、この間まではSSEの使い方と性能について調べてました。SSEはマルチメディア向けの命令が多く、フーリエ変換や動画予測など特定のアルゴリズムに特化したような命令が多く、他のアルゴリズムとかに応用しようと思うとあんまりないけど(SSE4のpopcntはとてもほしいけど)。

で今までは使うのはアセンブラで書かないとだめなんだろうなと思っていたのですが、gcc拡張でいろいろ使えるようになっていて(oxyさんのを見てね)、さらにはまって、IA-32アーキテクチャー 最適化リファレンスマニュアルを読みなおしてみたりとか。

あとはフーリエ変換とかウェーブレット変換も勉強しなおしてます。Telence Taoさんという何でもやってしまうスーパーな人が私の研究領域にもかぶってきて、その人のブログを読んでいるうちに興味がわきました。wavelet変換とかは、昔も流行りだってことで「よくわかる」という本だけ買って分かった気になって良く分かっていなかったのですが、読み直して、当時よりはちょっとは基礎体力がついたので昔分からなかったことががんがん分かるのが気持ちいい。最新の話はお腹いっぱいですが・・


--
機械学習の新しいバイブル本の一つとなるであろうbishop本の日本語訳 (amazon)が出るそうです。監訳、翻訳人が豪華です。日本語版の実物は読んでないけど、いろいろな人がお勧めしてるし、お勧めできるでしょう。

#私は英語版読んじゃったけど、研究室でも買うだろうから、追加の部分とか読んでみよかな。

| | Comments (56) | TrackBack (0)

« November 2007 | Main | January 2008 »