ランダマイゼーションとは?

Weblio 辞書 > 学問 > OR事典 > ランダマイゼーションの意味・解説 

ランダマイゼーション

読み方らんだまいぜーしょん
【英】:randomization

概要

ランダマイゼーションは, アルゴリズム中にランダム要素導入し, それにより最悪場合とらわれない簡単で実際に速いアルゴリズム構成しようという手法である. ランダマイゼーションすることによって得られるアルゴリズムランダム化アルゴリズムと呼ぶ. ランダマイゼーションは, アルゴリズム対す入力確率分布仮定して計算時間平均的評価するとかいうのではない. 代表的手法に, ランダム抽出法, ランダム添加法などがある.

詳説

 ランダマイゼーション(randomization)は, アルゴリズム中にランダム要素導入し, それにより最悪場合とらわれない簡単で実際に速いアルゴリズム構成しようという手法である. ランダマイザーションすることによって得られるアルゴリズムランダム化アルゴリズムとよぶ. メタヒューリスティックスのシミュレーティッド・アニーリングから素数判定ランダム化数論アルゴリズムまで幅広く用いられている. ランダマイゼーションは, アルゴリズム対す入力なんらかの確率分布仮定して計算時間平均的評価するとかいうのではない. 教科書も既にあり, [2] は全般的アルゴリズムについて, [3] は計算幾何アルゴリズムについて詳しい.

 本項では, 計算幾何問題対するランダマイゼーションの代表的手法についてまとめる. 代表的手法としては次の2つのものがあり, 以下その説明をする.

ランダム抽出(random sampling) ランダムに選ぶことにより全体反映した部分集合定め, その抽出し部分集合情報フル活用するもの

ランダム添加法(randomized incremental method) アルゴリズム構成のもっとも簡単なパラダイムである逐次添加法において, 添加順をランダム化する方法で, 添加法の実用性を示すものでもある.

(a) ランダム抽出 ランダム抽出法目指すところは, 部分全体を表すということである. そうできると, 部分計算するだけで情報ある程度得られるという計算量観点からの利点がある.

 代表的な例で, 平面上のn\, 個の点の集合S\, \epsilon\, -近似T\, 考える. 任意の\epsilon\ge0\, に対して, S\, 部分集合T\, \epsilon\, 近似である}とは, 任意の半平h\, に対して次式が成り立つことをいう.


\left| {|S\cap h|\over|S|}-{|T\cap h|\over |T|}\right|
\le\epsilon\,


 任意の\epsilon\, に対して, T=S\, とすればそれは\epsilon\, 近似になっているから, このような\epsilon\, 近似存在保証されるので, T\, サイズどこまで小さくできるかがポイントである. ランダム抽出理論適用すると, 次の定理成り立つ( [1] 参照).

定理. 任意の\epsilon,\ \delta>0\, に対して, 点集合S\, から少なくとも


m\ge{16\over\epsilon^2}\left(3\ln{48\over\epsilon^2}+\ln{4\over\delta}\right)\,


なるm\, 点をランダムかつ独立に選んで得られる集合T\, は, 少なくとも1-\delta\, 確率S\, \epsilon\, -近似である.

 この定理より, 任意の\epsilon>0\, に対して, \delta\, を1に近付けても, ある確率\epsilon\, 近似が単純なサンプリング求められということがわかる. 確率が正ならその事象存在するので, ほぼ定理サイズ\epsilon\, -近似存在定理導かれる.  このように\epsilon\, -近似全体点数に関係のない点数部分集合で, 半平面に含まれる点数に関する近似与えており, 部分によって全体表現できている. このようなランダム抽出に関する定理は, アルゴリズム構成面で自然と分割統治に使えて有用である. さらに理論観点からは, 各ニューロンが単純な線形しきい値関数である場合ニューラルネットでの学習能力と関係している.

(b) ランダム添加 ランダム添加法も有用な方法である. これは, アルゴリズム設計パラダイム1つである逐次添加法 (incremental method)をもとにするものである. 従来逐次添加法は, n\, 要素問題を解くときに, 最初定数個(例えば2,3)の要素部分問題対する解から始めて, i\, 個の要素部分問題の解があるとき, i+1\, 番目の要素をそこに加えてi+1\, 個の要素部分問題対する解をつくり, これをn\, 全体対する解が得られるまで繰り返す方法である. このとき, i\, 個の要素部分問題対する解がわかっていれば, 通常それに1個加えi+1\, 個の部分問題対する解は, ゼロからそのi+1\, 個の問題を解くのに比べて, はるかに効率よく求めることができるということが, 高速アルゴリズムを得るために役立つ. たとえば, 挿入ソートなどは, この典型例である.

 ランダム添加法では, ランダマイゼーションにより要素ランダム順に並べ, その順に逐次添加を行なっていく. それによって, 最悪場合考えたとき, 単に与えられた順で添加していくと, たいてい逐次添加法にとっては都合の悪い順番存在し, その場合の計算量最悪計算時間となってしまうことが多いのに対し, ランダマイゼーションによってそれを避けることができる. これは, 入力なんらかの分布仮定して平均計算時間評価するのと近く, ただ複雑な問題では入力分布として妥当なものを考えることが難しいので, 作為的入力分布仮定するより, アルゴリズムの中でランダマイゼーションした方がより汎用的成果が得られる. また, ランダマイゼーションアルゴリズムといっても, もし, 入力分布に関して, そう悪い例が出てこなさそうであれば, 実際には単に与えられた順で添加をしていけばよいのである. このランダム添加法は, 低次元線形計画凸包構成など幅広く適用されている.



参考文献

[1] 今井浩, 今井子, 『計算幾何学』, 共立出版, 1994.

[2] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

[3] K. Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms, Prentice-Hall, 1994.

「OR事典」の他の用語
計算幾何:  ポリマトロイド  マッチング  ラゲールボロノイ図  ランダマイゼーション  レベル  ロバスト化技術  位相優先法


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

ランダマイゼーションのお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング



ランダマイゼーションのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2018 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2018 Weblio RSS