« July 2008 | Main | September 2008 »

2008.08.22

乱択アルゴリズム

「乱択アルゴリズム」が共立出版から出ているので読んでいます

乱択アルゴリズム(wikipedia)(ランダマイズドアルゴリズムの方が一般的かもしれない)はアルゴリズムの中に(擬似)乱数が含まれており、動作が決定的ではなく、乱数に依存して動きます。
有名な例では、クイックソートのアルゴリズム中にピボットを選択するところがあるのですが、そこを決定的に最初や真ん中の値ではなく、適当に乱数でランダムに選んだ場合がそれに当たります。

クイックソートは最悪計算量が要素数がnの時、O(n^2)かかってしまう問題点がありますが、ランダムにピボットを選んだ場合、かなり高い確率でO(nlogn)で動作することが言えます。もっとはっきりいうと、比較の回数がαnlogn(αは5よりちょっと大きいぐらい)より大きくなる確率は1/(n^2)以下だということが言えます。つまりnが大きい場合は殆ど間違いなくO(nlogn)で動き、最悪値を避けようと真面目に中央値を求める必要はありません(ただ、係数は減るので実際は真面目に求めてもいいが)

これは、学部の頃習った時に少し混乱しました。もし、入力列もランダムにくるのであれば、乱数を使わず、決定的に選んだ場合(たとえばクイックソートのピボットを常に先頭を選ぶ)と乱数を選んだ場合の平均計算量(ここでは入力で平均をとってる)は同じになるはずです。なぜ、乱数を使うのかと。

で、悩みましたが、今では次のように理解しています(本にもかいてありました。)

一つ目は、決定的なアルゴリズムの場合は非常に少数の入力に対し、必ず悪く動作し(もしくは誤った答えを出す)、それ以外の入力に対してはうまく動作する。確率的なアルゴリズムの場合は全ての入力に対し、非常に少ない確率で悪く動作し、殆どはうまく動作する。

しかし、入力の方は悪意があればいくらでも操作できますし、完全にランダムということは実際のところなかなかいえません。例えばクイックソートに対し昇順の入力を与えることは結構あるかもしれません(なんか他の操作の出力だったりして)。それに対し確率的アルゴリズムの場合は擬似乱数がよければ、かならず均すことができます。

二つ目は、一定確率しか当たらないものも、アルゴリズムを繰り返し適用することで成功確率を増幅することができます。例えば片側誤りアルゴリズム(真の答えがYESの時は必ずYESと答え、真の答えがNOの時は確率p>0でNOと答える)がある時、乱数を用いてk回適用し、一度でもNOという答えが出ればNO、全てがYESならばYESとすれば、成功確率は1-(1-p)^kに増幅されます。高速な素性判定法であるRabin-Mille法や、BloomFilterなどがこれにあたります。

参照を定数時間で行なうことができるハッシュアルゴリズムのCuckoo Hash(日本語だとRadium Softwareさんところに説明がある, )も乱択アルゴリズムで構築します。これはキー kを登録する際に、二種類の違うハッシュ関数を用いてハッシュ値 h1(k), h2(k)を用意し、二部グラフ中のh1(k)、h2(k)のどちらかがあいていないかを調べ、もしあいているならそこに、あいていないなら、二部グラフに沿ってキーを一個ずつずらしてそこに登録します。でも、偶然、最悪閉路ができてずらせない場合、または閉路ができなくても、ずらす個数がlog n を超えちゃう場合があると困るのですが、この時は思い切って今のデータ構造を破棄して、ハッシュに使っていた乱数を変えて登録したキーを全部登録しなおします。このようなことが起きる確率も小さいことが示されています。(殆ど定数個数の避難場所を用意しておけば作り直さなくても大丈夫であることもしめされてます )pdf)

これの動的なキー追加じゃなく、キー集合が与えられている静的な場合のバージョンが、最小完全ハッシュライブラリのbepで使われてます 説明資料(pdf)

更にうれしいことに、乱択にすることにより、面倒な実装を非常にシンプルにすることもできます。機械学習などで使われる最適化も、少数のサンプルをランダムにとってきて、それらだけから勾配を求めて降る確率的勾配降下法(Stochastic Gradient Descent)が理論的にも実用的にも非常に強力であることもわかってきました。実装も今までなんだったのかとがっかりするほど簡単です(sgd)。

もちろんマルコフ連鎖モンテカルロ法(MCMC)とかも乱拓の力を存分に発揮してるものの一つです。

私自身適当なので、乱択とかは好きです。

| | Comments (35) | TrackBack (0)

2008.08.07

L1正則化について

先日L1正則化についての話をしてきました。 [ppt] [pdf]

ちょっと専門的な話ですが、L1正則化はパラメータ推定のときにパラメータw∈R^m に対し|w|_1 = |w_1| + |w_2| + ...+|w_m| のペナルティをかけるもので、機械学習だけでなく、compressed sensingやらいろいろな分野で出てくる手法です。

L1正則化を使うと、殆どのパラメータが0になりコンパクトな学習結果モデルが得られる上に、ノイズが大きい場合にはそれらを無視することができます(L2の場合はrepresenter theoremより、重みベクトルは訓練ベクトルの線形和としてしか表せないので、要らない素性の重みを0にするようなことは難しくなります)

さて、上の発表で話した中で今面白いのはL1-ball projectionという技術です。
"Efficient Projections onto the L1-Ball for Learning in High Dimensions", ICML 2008, J. Duchi, et. al. [pdf]

これはベクトルv∈R^mが与えられたら、w* = argmin_w |w-v|_2 , |v|_1 <= zを探す(|a|_nはnノルム)、つまり半径zのL1上の球で一番vに近い点を探すというものです。これができるとL1付の最適化もできます(|v|_1 < z の制約はラグランジュの未定乗数法でα(z - |v|_1) = -α|v|_1 + const.という効果)

この最適化は式を変形させていくと、現在のパラメータv_iを定数θ分だけ0に近づけて、もし符号が変わったら0にクリップするのが最適だということがわかります(θはその時のvに依存する)。式で書くと
w_i = sign(v_i) max(|v_i|-θ,0)
sign(v_i)はv_iの符号

つまりL1-ball projectionは各パラメータから定数の値をひくdiscountで実現できます
ということはL1正則化も結局のところ、discountによるスムージングということになります。
(L2-ball projectionだと、引くのではなく一定の値で割ることになる)

考えてみると当たり前のようなきもするけど、はっきりいわれるとすっきりしますね。

上の論文ではこのL1projectionを非常に効率的に行なう方法を提案しています(パラメータ数がmの時、平均O(m)時間、さらにアップデートで少数のパラメータしか変更しなくて続けてprojectionする場合は、変更があったパラメータ数がm'のときO(m' + log m)ぐらいでできるアルゴリズムも提案しされてます)。

実装も簡単そう。やってみるか。

| | Comments (96) | TrackBack (0)

2008.08.04

機械学習による自然言語処理チュートリアル

自然言語処理のときに使う機械学習手法のテクニックをざーっと2時間程度で紹介してほしいとのことだったので今日話してきました。基本的に、そんなに頑張らなくても効果が大きいものを中心に説明(特にパーセプトロンとか)を説明してます。
紹介した手法はパーセプトロン、最大エントロピー、正則化、多クラス分類、系列分類(CRF, Structured Perceptron)などなどです。どれも一かじりする感じで網羅的に見る方を優先してます。個々の詳しい話はそれぞれの文献や実装などを当たってみてください。

スライド [ppt] [pdf]

ここで話しているのは線形識別モデルの教師有り学習が中心で教師無し学習(クラスタリングなど)など他の自然言語処理を支える技術は省いてます。

こういうのを使って(使わなくてもいいけど)どんどんアプリケーション作らないといかんね。

| | Comments (39) | TrackBack (0)

« July 2008 | Main | September 2008 »