読者です 読者をやめる 読者になる 読者になる

kentsu tech Lab

何かその時の興味でいろいろする人。最近はScala使ってる。LinuxとアルゴリズムとOSSが大好き。

確率的解析と乱択アルゴリズム

アルゴリズム 数学

確率的解析と乱択アルゴリズム

確率論と計算機における問題解決の手法として
確率的解析と乱択アルゴリズムについて解説していく。
ここでは以下の問題を考える。

雇用問題

問題:
あなたは秘書を雇おうとしている。
その際にあなたは代理店を利用することにした。
その代理店は毎日1人、秘書を送ってくる。
あなたはその候補者と面談し、採用するかどうか選択する。
しかし、面談するのにあなたは費用を払う必要がある。
それに加え実際に候補者を雇うには更に費用がかかる。
そこであなたは現在の秘書よりも候補者が優れている場合すぐにでも雇う。
しかし、いくら費用がかかるか見積もりたい。
かかる費用を求めなさい。

この問題における重要点

この問題の解として、候補者を逐一比較していき数値的に高ければ雇う。
といったアルゴリズムが考えられる。
またこの問題では実行時間どうこうより
計算によって算出される費用に重点が置かれるため一般的な計算量の解析とは異なりコスト解析を行う必要がある。

このアルゴリズムにおける面談コスト(C_i)は雇用コスト(C_h)より小さい。
それを踏まえてn人の候補者からm人雇用した場合
このアルゴリズムのコストはO(nC_i+mC_h)となる。
しかしn人の面談は必ず行わなければならないので、nC_iは変化しない。
よって、この問題では雇用コストC_hの解析に集中するべきである。

最悪の場合

この問題における最悪の場合は、面談した全ての候補者を雇用するときである。
つまり候補者の能力値が昇順になっているときである。
この時の雇用コストはO(nC_h)となる。

確率的解析 ~Probabilistic Analysis~

上記の問題の様に確率を用いる問題の解析を「確率的解析」という。
確率的解析とは実行時間解析の手法ではない。
上記の問題における雇用コストを解析する手法である。
確率的解析を適用するには、入力分布に関する知識を用いるか
その分布自体を仮定してしまう必要がある。
それが完了すれば実行時間の平均を計算してアルゴリズムを解析する。
平均は入力可能な分布の上でとること、つまり全ての可能な入力に対する平均を算出する。

入力分布は慎重に決める必要がある。
というのも、問題において入力集合に対してある分布をとることで効率のよいアルゴリズムを設計するためである。
しかし妥当な入力分布が存在しない場合ある。
そのようなときには確率的解析を用いることができない。

今回の雇用問題の場合、候補者はランダムに出現し二人の候補者を比較できると仮定できる。
この仮定より、以下を満たす全順序が存在する仮定する。

{ \displaystyle
集合Xにおいて関係 \le が全順序付けられるなら、Xの任意の元a,b,cに対して \\
1)a \le b かつ b \le a ならば a=b(反対称律) \\
2)a \le b かつ b \le c ならば a \le c(推移律) \\
3)a \le b または b \le aのいずれかが成立する(完全律) \\
}

ここまで示した仮定により、候補者全員を1からnまでの数でただ一通りにランク付け出来る。
それを求める関数をrank(i)とし候補iのランクを表し、大きいほど能力値が高いとする。
よって候補者がランダムに出現することと、ランクから作られるn!通りの置換のうち
任意の一つに一致する事象はどれも等確率である。
またはランクリストは一様ランダム置換と言える。

確率的解析における乱択アルゴリズム

確率的解析を用いるには入力分布に関する知識が必須となる。(上記)
しかし、入力分布がわからない場合も多く、たとえ分布がはっきりとわかっていたとしても
必ずアルゴリズムとしてモデルに出来るとは限らない。
そこでアルゴリズムの振る舞いをランダムにしてアルゴリズム設計の道具としてランダム性を使うことが出来る。
ただこのままでは最初に挙げた問題の解決法としては使えないので
問題を以下のように変更する。

代理店が候補者リストを事前に送ってくる。
そのリストから私達が毎日面談するものを決める。

こうすることでランダムな順序で送られてくる候補者に
ランダムな順序を強制する。

乱択アルゴリズム

ここまで長々と書いてきたが乱択アルゴリズムとは何か?
多少変更した上記の問題に対して、解決方がランダム性を使うものとする。
こういった場合に、アルゴリズムの振る舞いは入力データと乱数生成器の2つで決まる。
そのように乱数を使用するアルゴリズム乱択アルゴリズムという。
ただし計算機で用いる乱数生成器は、統計的にランダムに「見える」値を返す
決定アルゴリズムを用いた擬似乱数生成器によって実現されることが多い。

指標確率変数

雇用問題やその他乱択アルゴリズムを用いるであろう多数のアルゴリズム解析に指標確率変数を用いる。
これは確率と綿密な関係にある期待値をお互いに変換する便利な道具のようなものである。
標本空間Sと事象Aが与えられている時、Aに関する指標確率変数を

{\displaystyle
\begin{eqnarray}
I\{A\} = \left\{ \begin{array}{11}
1 & Aが発生する時 \\
0 & Aが発生しない時
\end{array}\right.
\end{eqnarray}
}

と定義する。

例1

一枚のコインをコイントスして表がでる回数の期待値を求めてみる。
標本空間はS=\{H,T\}とし、コインには裏表しかないので確率Pr\{H\} = Pr\{T\}=1/2となる。
今回は表が出る回数の期待値なので、事象H(表が出るとき)に対して指標確率変数X_Hを定義できる
ここでは上記の指標確率変数にしたがって、表が出るなら1、裏がでるなら0とする。

{\displaystyle
\begin{eqnarray}
X_H=I\{H\}
= \left\{ \begin{array}{11}
1 & Hが発生する時 \\
0 & Hが発生しない時(Tが発生する時)
\end{array}\right.
\end{eqnarray}
}

この様にこの問題(コイントスで表が出る回数の期待値を求める)に対して指標確率変数を定義した。
この場合の期待値をEとして、指標確率変数X_Hを用いて期待値を計算する。

{
\displaystyle
\begin{equation}
E \left[ X_H \right] \\ = E\left[ I\left\{ H \right\} \right] \\ = 1*Pr \left\{H \right\}+1*Pr \left\{T \right\} \\ = 1*(1/2)+0*(1/2) = 1/2
\end{equation}
}

よって1枚のコインをコイントスした時、表がでる回数の期待値は1/2となる。
今回のコイントス問題の様に単純な問題だと指標確率変数を用いるのは面倒に感じるかも知れないが
これが一回のコイントスではなく一般のn \in \mathbb{N}回に対してだと圧倒的に便利になる。
その例を次に示す。

例2

例1で考察した問題に対して一回のコイントスではなく一般のn \in \mathbb{N}に対して考察してみる。
ここでi番目の指標確率変数をX_iとする。この時0 \le i \le nn,i \in \mathbb{N}とする。
例1で示した様に指標確率変数の和で表せるので、全体の確率変数Xは次の様に表せる。

{\displaystyle
\begin{equation}
X = \sum_{i = 1}^{n} X_i
\end{equation}
}

上の式に対して両辺で期待値を取ると

{\displaystyle
\begin{equation}
E \left[ X \right]  \\ 
= E \left[ \sum_{i = 1}^{n} X_i \right] \\
= \sum_{i = 1}^{n} E \left[ X_i \right] \\
X_i = 1/2より \\
= \sum_{i = 1}^{n} 1/2 \\
= n/2

\end{equation}
}

となることがわかる。
これで一般の自然数nに対して期待値を指標確率変数を用いて表現することができた。
なぜ指標確率変数がすぐれた解析技術として使えるかというと、期待値が線形性を持つからである
またこの例で指した様に、指標確率変数を用いる事で大幅に計算を単純化することができる。

雇用問題への応用

候補者は上記の例同様n人いるのでX_ii人目の指標確率変数となる。
それではi人目の指標確率変数を以下のように定義する。

{ \displaystyle
\begin{eqnarray}
X_i = \left\{ \begin{array}{11}
1 & 候補者iが雇用される時 \\
0 & 候補者iが雇用されない時 \\
\end{array} \right.
\end{eqnarray}
}

また確率変数Xは次の様に定義できる。

{\displaystyle
X = X_1 + X_2 + X_3 + ... + X_n
}

更にi人目が最初の候補者からi-1人目までの候補者の中で最も優れている確率は1/iなので
上記の例2よりこの問題の期待値は次の様に表せる。

{\displaystyle
\begin{equation}
E \left[ X \right]  \\ 
= E \left[ \sum_{i = 1}^{n} X_i \right] \\
= \sum_{i = 1}^{n} E \left[ X_i \right] \\
X_i = 1/iより \\
= \sum_{i = 1}^{n} 1/i \\
= \log n +O(1)

\end{equation}
}

乱択アルゴリズムの適用

雇用問題やコイントスの問題のような入力全ての置換が等しい確率で成立するという過程が成り立つような問題では
確率的解析が乱択アルゴリズムを用いた開発の指針となる。
具体的にはアルゴリズムが実行される前に候補者の順番をランダムに並び変え
強制的に全ての置換の出現確率を等しくするようにする。

確率的解析と乱択アルゴリズムの違い

上記の記述より、候補者がランダムに出現しようと期待値は変化しない
決定的なアルゴリズム、つまり解が一意に決まるものと比べて
乱択アルゴリズムは入力時ではなく、アルゴリズム内で入力分布のランダム化が発生する。
そのため、特定の入力に対して情報の更新が何回起こるかわからない。
しかし、以前の実行と今回の実行でランダム化が同じである確率はとても低い。
よって、特定の入力があったとき、その入力に対して常に最悪の処理を引き起こすことがない
乱択アルゴリズムが最悪の処理を実行してしまうのは単に運が悪かったからというだけである。

ここまでの解説で雇用問題に乱択アルゴリズムを適用するのに必要なことは
単に入力配列のランダム化である。
これで乱択アルゴリズムが適用できる。

またこの他にも、以下のような問題にも適用できる。


追加問題

N個の箱がある。
箱を開けるまでわからないが半分は当たりになっている。
あたりを見つけよう。

この場合、最悪のケース。先頭から探索するとして
当たりが全て箱の後ろ半分に偏っていた場合O(n/2)かかってしまう。
しかし、その箱の列をランダム化すると
開ける箱の個数に対する期待値は2以下なので、すぐに発見することができる。

最後に

ここまでざっくりと乱択アルゴリズムと確率的解析について解説した
そのうち実際に乱択アルゴリズムを適用したソースコードでも載せようと思う。