誤謬発見効率の良い検索方法

質問

誤謬発見効率の良い検索方法

　下記条件の下で、数列Xについて、誤謬要素発見に要する時間の期待値が最も少ない検索方法を教えてください。もしくは、勉強の糸口となるような情報(該当する分野、本など)を教えてください。

1. 要素数nの規則性のない数列X(x_1, x_2, ..., x_n)がある。
2. 1個以上の要素が誤っていることは分かっている。以下、この要素を誤謬要素と呼ぶことにする。
3. 全ての誤謬要素を特定するのが目標である。但し、誤謬要素はそれほど多くなく、存在個数の確率分布は、平均値n/20程度のポアソン分布に従うと考える。
4. i番目からj番目までの連続した要素について、誤謬要素の有無について判定する関数F[i, j]を持つ。
5. 関数Fを用いる以外の方法では、誤謬要素を発見できない。
6. 関数Fを一度実行するのに必要な時間は、a(定数)である。

　現在やっている方法は、直感的に効率が良さそうな以下の方法です。しかし、私としてはより速い方法を行い、且つそれが効率が良いという点について理論的な確証を得たいと考えています。
　F[1,n/2], F[n/2+1, n]を行い、誤謬要素がある方について、更に検索範囲を半分にして関数Fで判定する。

補足
　以下に示されていない状況で、補足情報が必要な場合は、質問者に補足要求する前に、回答者が場合分けしてお答えください。場合分けが8通り以上に及ぶ場合は、質問状況を絞りますので、補足要求してください。

回答No.4

alice_44 · ベストアンサー

前段について：

ポアソン分布の典型的な応用は、待ち行列で一定時間内に到着する新規顧客の人数ですが、
このとき、顧客になりえる人間の範囲は、モデル化されずにボヤかされています。
今回のように n 個の全データという範囲が明白だと、二項分布以外を仮定したとき、
個々のデータが誤謬であるか否かが独立でないことが問題になってきます。
二分探索や、それを拡張した No.1 のような、分割統治による探索の効率を計算するとき、
分割された各区分内での誤謬の発生確率が、相関を持ってしまうのです。
このため、期待値の計算は、ほとんど現実的でなくなります。

後段について：
誤謬の発生数を二項分布と仮定するならば、個々のデータが誤謬であるか否かは独立ですから、
前述の問題は起こりません。No.1 に従って、少し計算してみましょう。

nm 個のデータを n 個づつ m グループに分割し、1 グループづつ誤謬の検索をします。
k 個目に調べたグループで初めて誤謬を発見する確率は、
これ以前のグループに属する n(k-1) 個のデータが誤謬でない確立 (1 - 1/20)^{n(k-1)} と
第 k グループの n 個のデータの中に少なくとも 1 個の誤謬がある確率 { 1 - (1 - 1/20)^n }
の積で p_k = (1 - 1/20)^{n(k-1)}・{ 1 - (1 - 1/20)^n } です。

検索に要する時間の期待値は、
E = Σ[k=1…m] (a k) p_k = a{ 1 - (m+1)r^m + mr^(m+1) }/(1-r) ただし r = (19/20)^n。
nm 一定の条件下に E を最小にする n, m を求めればよいのですが、
E/a = { 1 - (19/20)^(nm) }/{ 1 - (19/20)^n } + { nm(19/20)^(nm) }/n と整理できますから、
∂E/∂n = 0 を変形して、
F(n) = √{ F(nm) }・(20/19)^(nm/4) ただし F(x) = sinh(x log√(20/19)) / (x log√(20/19))。
これを近似的に満たす自然数 n を見つけることになります。計算するのは辛そうですが。

お礼

ありがとうございます。
かなり複雑なので時間がかかりましたが、とても参考になりました。

回答No.3

alice_44

ポアソン分布ってのが、謎ですね。
全部で n 個のデータ中で、エラーの個数が
ポアソン分布に従うとすれば、
n≒∞ で近似している訳で、
二分探索の効率を評価することなど
できない話になります。
標本の大きさが、分布関数のバラメータとして
現れませんから。

No.2 にあるように、エラーの発生数を
二項分布で近似するのなら、分割統治の効率を
論じることができるのですが…
ポアソン分布では、個々のデータがエラーか否かが
独立ですらないのですから。

お礼

ありがとうございます。

実は、前段の意図が全くわかりません。要素はたくさんあるので、
とりあえずnを無限大で近似しても良いかと思ったのですが、
それ自体に問題があるという意味でしょうか。

後段については、
「No.2 にあるように、エラーの発生数を
二項分布で近似するのなら、分割統治の効率を
論じることができるのですが…」
とのことであれば、エラーの発生数を2項分布で近似して
(つまり私の質問を必要最低限修正したうえで)
効率を論じてみていただけますでしょうか。

回答No.2

Tacosan

大雑把にいうと個々の要素が誤謬要素である確率は 1/20 くらいと思っていいのかな?
もしそうだとすると, 最初から二分探索するのはあまり効率的ではないと思います. つまり「F[1,n/2], F[n/2+1, n]を行い、誤謬要素がある方について、更に検索範囲を半分にして関数Fで判定する。」としましょう. このとき, n がある程度大きければ「どちらにも誤謬要素が含まれる」可能性が高く, したがってその次には F[1, n/4], F[n/4+1, n/2], F[n/2+1, 3n/f], F[3n/4+1, n] のすべてを調べることになりがちです. とすれば, 最初から 4つに分けておけば最初の判定 (F の 2回の呼び出し) を省略できるはずです.
これをもっと進めると, たとえば「最初に F[1, 20], F[21, 40], ... のように判定し, 誤謬要素がある部分のみ二分探索する」ようにすると誤謬要素を含まない部分が出てくるので速くなるんじゃないでしょうか. もちろん 20 が適切かどうかはわかりません.

お礼

もし、その考え方を推し進めるのであれば、ご回答になった全部、
「もちろん 20 が適切かどうかはわかりません」というところまでは、
質問者がすでに到達しています。

一体いくつ程度に分割するのがよいのかという質問であるとお考えください。

補足

> 個々の要素が誤謬要素である確率は 1/20 くらいと思っていいのかな
まさにその通りとお考えください。No.3の御回答を見る限りではポアソン分布などと
言い出さずに、このように記載すればよかったと考えている次第です。

おっしゃる通り、確かに実績としては、「どちらにも誤謬要素が含まれる」ことがままあります。
結局、4分割試験を4回しています。
一方で、nが少ない時(20－30程度のこともある)は、経験則としては、いきなり細分化して調べるのは
どう見ても面倒です。

回答No.1

alice_44

条件 1. と 4. が矛盾していることを
どう説明しますか？

お礼

ありがとうございます。矛盾はしておりません。
恐らく、質問文解釈を勘違いされているものと推察されます。
もちろん、勘違いの理由は貴方とは限らず、私の記述に分かりにくい点があるのかもしれません。
そこで、いかなる理由で矛盾と考えるのか、説明願いますでしょうか。