« L1正則化について | Main | 透過的データ圧縮 »

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)とかも乱拓の力を存分に発揮してるものの一つです。

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

|

« L1正則化について | Main | 透過的データ圧縮 »

Comments

Evilな入力に対抗するために乱数を使うというのは、「オンラインアルゴリズム、ストリームアルゴリズム」にも出てきましたね。

Posted by: Gus | 2008.08.22 at 07:51 AM

そうですねぇ。実用的にはそちらの頑健性向上の方も大きいのでしょうねぇ。サービスとかだと悪意のある入力だらけだから、中身をブラックボックス化する必要はあるでしょね。

Posted by: oka | 2008.08.22 at 12:22 PM

Hey there! This is kind of off topic but I need some guidance from an established blog. Is it hard to set up your own blog? I'm not very techincal but I can figure things out pretty quick. I'm thinking about making my own but I'm not sure where to begin. Do you have any points or suggestions? Cheers

Posted by: Bubble Guppies | 2014.06.14 at 08:08 PM

This can expand your worldview and give you valuable insight about other cultures. All you need to do is to kind and add the words 'kiss' prior to the word 'You - Tube' in your You - Tube URL. If you have a video that you shot candidly, you need to use your best judgment.

Posted by: buying youtube views | 2014.06.24 at 08:00 AM

Good answers in return of this query with firm arguments and describing the whole thing concerning that.

Posted by: Sniper Elite 3 Gratuitement | 2014.08.23 at 06:55 AM

I constantly spent my half an hour to read this website's articles or reviews daily along with a cup of coffee.

Posted by: Forge Of Empires Hack | 2014.12.05 at 05:42 AM

Hi there! I just wanted to ask if you ever have any trouble with hackers? My last blog (wordpress) was hacked and I ended up losing months of hard work due to no backup. Do you have any solutions to stop hackers?

Posted by: UberStrike Hack | 2014.12.05 at 08:34 AM

Wow! This blog looks just like my old one! It's on a entirely different subject but it has pretty much the same page layout and design. Great choice of colors!

Posted by: Top Eleven Hack | 2014.12.05 at 06:30 PM

S currency Wikinut com website such as ClickBank that supply info-products, e-courses plus software that sniffs out make money online online" influencers" --folks likely to spend it? Second, they want to end their pain and support their education and something extra for entertainment. Even if you decide to also find that Google enforces over Adsense, it may be. Then copy and make money online the possibilities of working online from home. Don't for a post, people will not have any trouble making your site, an advertising document as a source of valuable territory.

Posted by: Google Sniper 2.0 review | 2014.12.08 at 05:50 PM

Its like you read my mind! You seem to grasp so much about this, such as you wrote the e book in it or something. I think that you just could do with some percent to pressure the message home a little bit, but other than that, that is wonderful blog. An excellent read. I'll definitely be back.

Posted by: clash of lords 2 hack | 2014.12.18 at 03:48 PM

That's like telling Sony close up shop.... its not gonna happen.

Posted by: league of legends riot points hack 2014 | 2015.02.08 at 11:47 AM

Then come back a few weeks later and do it again until you automatically react, especially after some time has gone by. We can say that advertisements appear everywhere in our modern society. They extend and thus change the airfoil shape of the wings, reducing the pressure at the top and increasing the lift.

Posted by: bitly.com | 2015.02.11 at 06:43 PM

Howdy! I know this is somewhat off topic but I was wondering if you knew where I could locate a captcha plugin for my comment form? I'm using the same blog platform as yours and I'm having difficulty finding one? Thanks a lot!

Posted by: Ripped Muscle X | 2015.03.14 at 04:24 AM

Anonymous.

Posted by: league of legends riot points generator no survey 2014 | 2015.03.17 at 03:58 PM

If you desire to get a good deal from this post then you have to apply these strategies to your won web site.

Posted by: Ripped Muscle X | 2015.03.20 at 04:57 AM

Hi to every one, it's truly a nice for me to go to see this site, it contains precious Information.

Posted by: six pack workout | 2015.03.20 at 03:06 PM

Excellent website you have here but I was curious about if you knew of any message boards that cover the same topics discussed here? I'd really like to be a part of community where I can get opinions from other knowledgeable individuals that share the same interest. If you have any recommendations, please let me know. Many thanks!

Posted by: Warren | 2015.03.21 at 02:58 AM

It's amazing to go to see this website and reading the views of all mates concerning this post, while I am alsxo zealous of getting familiarity.

Posted by: Crowd Banc | 2015.04.20 at 07:39 AM

Appreciate the recommendation. Will try it out.

Posted by: Legal Advice | 2015.04.20 at 10:57 AM

Way cool! Some extremely valid points! I appreciate you writing this write-up and alseo the rest of the website is extremely good.

Posted by: therightwayworks.com | 2015.04.21 at 03:20 AM

Wow! Finally I got a blog from where I can truly obtain useful facts regarding my study and knowledge.

Posted by: racing Game | 2015.04.21 at 04:12 AM

Simply wiish to say your article is as astonishing. The clearness on your submit is just great and that i can assume you're a professional in this subject. Well with your permission allow me tto clutrch your feed to keep updated with forthcoming post. Thanks one million andd please carry on the rewarding work.

Posted by: Website Design | 2015.04.21 at 05:17 AM

Whhen someone writes an article he/she retains the image off a user in his/her brain that hhow a user can be aware of it. So that's why this post is great. Thanks!

Posted by: http://www.corridorrecovery.com | 2015.04.21 at 07:41 AM

I'm excited to discover this site. I wanted to thank you for your time just for this wonderful read!! I definitely liked every little bit of it and I have you book-marked to check out new stuff in your site.

Posted by: lol free rp | 2015.04.22 at 09:41 PM

I like it when individuals come together and shjare thoughts. Great blog, stick with it!

Posted by: healthy diet | 2015.05.15 at 09:59 AM

I think this is among the most vital information for me. And i'm glad reading your article. But should remark on few general things, The web site style is wonderful, the articles is really excellent : D. Good job, cheers

Posted by: astuce clash of clans gemmes illimites | 2015.07.28 at 05:20 AM

Have fun enjoying Top Eleven, and turn out to be the number one player with our Prime Eleven Hack Device.

Posted by: top eleven hack tool 2015 | 2015.08.04 at 06:05 AM

Pretty component of content. I just stumbled upon your blog and in accession capital to assert that I get actually loved account your weblog posts. Anyway I will be subscribing for your augment and even I success you get entry to persistently fast.

Posted by: Fort Lauderdale Escort | 2015.08.21 at 03:16 PM

I visited multiple web pages except the audio quality for audio songs present at this web page is truly wonderful.

Posted by: astuce clash of clans | 2015.09.01 at 03:43 PM

The other day, while I was at work, my cousin stole my apple ipad and tested to see if it can survive a 40 foot drop, just so she can be a youtube sensation. My iPad is now broken and she has 83 views. I know this is completely off topic but I had to share it with someone!

Posted by: FORT LAUDERDALE | 2015.09.04 at 06:29 AM

With havin so much written content do you ever run into any issues of plagorism or copyright infringement? My website has a lot of unique content I've either authored myself or outsourced but it appears a lot of it is popping it up all over the internet without my authorization. Do you know any methods to help stop content from being stolen? I'd truly appreciate it.

Posted by: Breakdance.jp | 2015.09.21 at 09:22 AM

I loved as much as you will receive carried out right here. The sketch is tasteful, your authored material stylish. nonetheless, you command get got an edginess over that you wish be delivering the following. unwell unquestionably come more formerly again as exactly the same nearly a lot often inside case you shield this hike.

Posted by: q | 2015.09.23 at 10:03 AM

I would like to thank you for the efforts you've put in penning this site. I am hoping to check out the same high-grade blog posts by you later on as well. In fact, your creative writing abilities has motivated me to get my very own site now ;)

Posted by: game of war fire age astuces | 2015.09.24 at 10:00 AM

Had downside with ports on emails, referred to as helpline immeaditly answered, no waiting, downside defined, resolution agreed and access granted, drawback solved.

Posted by: https://youtu.be/ | 2015.09.25 at 04:41 AM

certainly like your website however you need to take a look at the spelling on quite a few of your posts. Several of them are rife with spelling issues and I in finding it very bothersome to inform the truth however I'll certainly come back again.

Posted by: star wars battlefront triggerbot | 2015.10.05 at 02:19 PM

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/3041/42236365

Listed below are links to weblogs that reference 乱択アルゴリズム:

« L1正則化について | Main | 透過的データ圧縮 »