piu lentoの日々 (piu lento days)

最初に断ると、正確には「(Linuxなどの)疑似乱数生成器(PRNG)の一様性の問題」だ。乱数自体の話は いろいろあるだろうけど、それではない。

前の稿に書いたように、乱数で画像の表示順序をランダムにしようとしたら、全然一様でなくて、偏りが大きくて  ばっさり棄てた。頻度の最多と最少の比が2以上もあるのでは、全く使えない。 (実験結果を最後に書く)

単に試行回数が少ないせいなのかと思ったが、階級(分類)数約30に対して1000回実施しても偏りは解消しなかった(約1.8)ので、永久に解消しないように思う。

ある掲示板で見たのだが、僕と類似の質問に対して、統計あるいは数学のプロらしき人が、「そんな試行回数じゃ全然足りない。文句を言う前に統計を勉強しろ」みたいな偉そうなことを書いていた。そういう連中は10万回とかが最低レベルで、基本は「無限の回数」なのだろうが、そんな前提では全く実用にならない!

そもそも、一様な乱数なら、なぜ試行開始から しばらく または ずっと 偏りが生ずるのだろうか? 階級数は少ない(= 狭い)ので偏る理由がない。確かに確率論的には ばらつくこともあり得るが、階級の数より充分大きい(例: 30倍)回数でも依然として偏ったままなのはおかしい。確率論での「充分大きい」は1000倍とか1万倍なのだろうか?

不思議なのは、それを使っているであろう多くのアプリケーションが問題ないことだ。僕の使い方が悪いのか、偶然問題が起こらないのか、そういうものなのか、実際には問題があるけど隠れているのかのどれかは分からない。

 

以下、細かい話である。

上に書いた、乱数のバラつき(階級数29の場合、最多と最少頻度の比が大きい)が気になったので、Linux、特にPHPで使える乱数機能を いろいろ試してみた。

なお、試行回数は階級数(29)の20倍の580回とした。また、頻度の集計には、Stack overflowの"How to generate a random number from a uniform distribution in php?"の回答1に書かれていたものを使った。

以下に、試した方法ごとの最多と最少頻度の比を示す。なお、実行するたびに比は変動するので、2回実施した。

1回目

• PHP: rand: 5.6※
• PHP: mt_rand:2.7※
• PHP: random_int: 2.4
• PHP: statsパッケージのstats_rand_gen_iuniform: 2.8
• /dev/urandom (4バイト読み出し): 4.7 (処理に誤りがあったので取り消し。やり直した値はPSを参照のこと。)
• opensslコマンド(openssl rand 4)＊: 3.0 (処理に誤りがあったので取り消し。やり直した値はPSを参照のこと。)
• shufコマンド(shuf -rn 1 -i 0-MAX): 2.5
• Python: numpy.random.uniform＊: 6.7
• rand+僕の改良案2＠: 2.3

2回目

• PHP: rand: 2.6
• PHP: mt_rand: 2.6
• PHP: random_int: 2.7
• PHP: statsパッケージのstats_rand_gen_iuniform: 2.8
• /dev/urandom: 3.1 (処理に誤りがあったので取り消し。やり直した値はPSを参照のこと。)
• opensslコマンド: rand: 2.8 (処理に誤りがあったので取り消し。やり直した値はPSを参照のこと。)
• shufコマンド: 2.6
• Python: numpy.random.uniform: 4
• rand+僕の改良案2: 4.1

メモ

• ※ ドキュメントではrandとmt_randは同じものなので、差が出るのはおかしい。mt_randをrandのあとに実行した関係があるのだろうか。実際、2回目はrandとmt_randの比は近かった。
• ＊ Pythonのnumpy.random.uniformは/dev/randomを使っているのか、随分時間が掛かった。opensslのrandも遅かった。
• ＠ randの出す値の密度や間隔と実際の値域のそれが異なることが悪いのかと思い、階級数より充分大きな範囲の乱数から縮小するようにしてみた。要するに、浮動小数点の乱数(0〜1)を任意の範囲の整数にする手順にしてみた。また、結果の整数の乱数を出すのに、以下の2とおりを試した。
  • 案1: mod(剰余)
  • 案2: 除算

 

結局、比較的少ない試行回数ではPHPのrandom_intとshufコマンドが一番一様そう(2.6付近)で、その次はstats_rand_gen_iuniform(2.8)となった。stats_rand_gen_iuniformは安定しているところが良さそうだ。

randやmt_randは悪くないが、変動が大きそうだ。opensslのrandは良くはないが、比較的安定している。なお、Pythonのnumpy.random.uniformや/dev/urandomは今一つだった(後者は使い方が悪いのかも知れない → opensslとともに整数化の処理に誤りがあったので値を取り消した。: 9/15 10:26)。

(9/15 9:03) numpy.random.uniformについては、参考にしたページにある分布のグラフは ほぼ平坦で、これなら許せる(と期待して試した)。その試行回数は10000回(個)なので、階級数(そこでは10)の1000倍くらい試行しないと一様にならないのかも知れない。この、どれだけ繰り返せば充分かというのは、どうすれば分かるのだろうか? また、本質的に そうできない用途では どうするのだろうか?

(9/15 9:12) と書いたあとにグラフを良く見たら、上の例で生成している乱数(グラフの横軸)は整数でなく浮動小数点数だった! 僕は整数に丸めて評価したので、その辺りに問題があるのかも知れない。丸めについては僕も気になっていて、上述の改善案で試行錯誤したけどうまく行かなかった。

グラフを目で見た時と同様に、積分して整数にすればうまく行くだろうか? 面倒なことだ・・・ ← 丸めるのは積分(個数を求める場合)でなく単なる整数化(例: 四捨五入)で良いから、問題なかったはず。

いずれにしても、僕にはまったく許容できない偏りである。

そういう問題または仕様あるいは注意事項があるなら、ドキュメントに書くべきだと思うが、まったく見たことがない。せいぜい"cryptographically secure"かどうかだけだ。

僕に言わせれば、こんなに偏るものがsecureとは思えない。まあ、見るところが違うのだろうけど。

 

(9/16 13:59) 元々の用途(このブログの「時替わりギャラリー」)に対する うまい対処方法(workaround)を思い付いた。: 画像を替えるのに乱数(PHPのrand)を使うが、それで次に表示する画像の番号を直接決めるのでなく、乱数と現在の画像の番号を加えたもの(と画像数の剰余(mod))を次の画像の番号にするのだ。現在の画像番号をn、全画像数をNとすると、次の画像番号n'は以下の式で得られる。

n'= (n + rand(1, N-2)) % N

rand: 整数の乱数: 引数: 最小値, 最大値
%: 剰余

これなら、仮に乱数に出やすい値xがあっても、今の画像からx枚目の画像が出やすくなるだけで、いつも同じ数種類の値(しかも、それらが画像数と「いい関係」にある)が出るのでない限り、特定の画像が出やすくなることは起こりにくいと考えられる。

が、実は そうでもないというオチはないか?: 少なくともrandは今の画像の番号は分からないので、特定の画像が出やすくなるような値は出せないはずだ。あるとすれば、周期的に同じような値が出ること(上の「いい関係」)だろうか? 考えると難しい(面倒だ)。

↓

(9/17 16:28) ところが、そうは問屋が卸さなかった。表示される画像をチェックしていたら、やっぱり良く出るものがあった。想像だが、上のように乱数に何かを加えたものも元の乱数と同じ性質であり、その元の乱数に良く出る値があるなら良く出るスキップ数となり、そのスキップ数と全画像数の関係(割り切れるか)にも よるだろうが、結局同じ画像が良く出るのではないだろうか。

結局、ギャラリー内の画像の順序のとおりに表示するように戻した。

↓

(9/18 12:22) その後、擬似的な乱数としてページのアクセス時刻(正確には この処理を開始する時の時刻, μs単位)を使ってみたが、不思議なことに やっぱり一様でなく、良く出る値(→ 良く出る画像)と全然出ない値が生じた。

例えば、(回数は多くないが、)71回(約4時間分)のアクセスでは、最高に出た値の頻度は最小(1回)の5倍だった。出ない値は2個で、全体の平均は2.6回だった。

アクセス時刻(の階級数での剰余)がある時刻に集中するとは考えられないので この原因も謎だが、出ない3個(各1回と想像)が出やすいところに回って、平均の2.6+2 → 5回になったのかも知れない。

画像数(= 階級数)が29個と、10の倍数でないなのが関係していることも疑った。: アクセスはランダムな時刻に来るが、その時刻を階級(各画像)に振り分ける時に偏りが生ずるのではないか? ただ、時刻は100μs単位(0-99)のように区切っては いないので、剰余が偏りを生むとは思えない。

が、頻度分布を見ると、後半の12から25までの頻度が比較的多いのが気になる。その幅は13で、100と29の剰余に合う。また、頻度の高い区間が始まる12は13-1だ。単なる偶然とは思うが不思議だ。

だから、これは たまたまアクセス時刻が偏ったためで、回数を多くすれ(長時間、数日?見れ)ば均等になるのだろう。が、僕には、起動後数時間経っても偏りが直らないのは許容できないので、この方法もボツにした。

 

PS. Pythonのページに関する追記から、試行回数を増やして一様性を比較してみたら、どうやら、階級数x500回以上試行すれば、僕が満足できる一様性(最多/最少が概ね1.2 → ばらつき20%以内)に できそうなことが分かった。 (9/15 10:37)

試行回数と各方式での最多と最少頻度の比を示す。

29階級x20回= 580回: 2.5辺り (Pythonは3辺り、opensslは5辺り)

• PHP: rand: 2.38
• PHP: random_int: 2.64
• /dev/urandom: 2.42
• shuf: 2.31
• openssl rand: 4.5
• Python numpy.random.uniform: 4.83 2.9

29階級x500回= 14500回: 1.3辺り (random_intとshufとPythonは1.2辺り)

• PHP: rand: 1.26
• PHP: random_int: 1.19
• /dev/urandom: 1.26
• shuf: 1.21
• openssl rand: 1.31
• Python numpy.random.uniform: 2.07 1.2

29階級x1000回= 29000回: 1.1辺り (random_intとshufは1.15辺り、Pythonは1.2辺り)

• PHP: rand: 1.11
• PHP: random_int: 1.15
• /dev/urandom: 1.11
• shuf: 1.24
• openssl rand: 1.11
• Python: numpy.random.uniform: 2.26 1.19

本文で懸念したように、/dev/urandomとopenssl randの使い方(整数化の方法)に誤りがあったので修正した。

また、Pythonの一様性が悪いのは、使い方が良くないせいかも知れない。 ← (9/15 13:42) Pythonのnumpy.random.uniformの出力に想定外の問題があった。: 生成する乱数の最小, 最大値での頻度が他のものの半分くらいになっていた(乱数を表示する時の丸めの問題かも知れない)。 → 仮対処として、生成する範囲を広く取って数を多目に生成して範囲内のものだけを使うようにしたら、一様性は改善された。 → 上を更新した。

それから、Pythonの1回の実行でその系統全部の乱数を生成するようにしたら、実行速度は速くなった。

結局、試行(繰り返し)回数を随分増やせば一様になることが確認できた。実際に使う時にはそうできないことがあるが、その場合は「シャフル」のように あらかじめ一様な分布を作っておくとか、分布が一様になるように調整(取捨選択)するのだろうか?

あと、この問題は「システムの起動後しばらくは(乱数が今一つなので)安全でない」ということには ならないのだろうか? (この辺りは全くの素人なので、単なる思いつきである。)

 

(9/15 10:37 若干修正, 10:37 PSを追加, 16:22 題を明確化; 9/16 13:59 対処方法を追記, 22:42 題を変更; 9/17 16:28, 9/18 12:22 乱数を諦めた件とその後の試行を追記)

前々回のPSに書いた、このブログのロゴ画像を「時替わり」で いろいろ出すのが意外に気に入ったので(+そこでも書いたように、ERNIE-ViLG Demoで描いた画像が気に入ったのも大きい)、それを改良した。

例によって やることは難しくないのだが、実装には結構手こずった。欲張るせいもあるが、老化で頭が回らなくなっているのだろうか?

以下のようにしたかった。

• ロゴとして特別に選んだ・作った画像でなく、ブログの投稿に使った画像全体(あるいは新規も)から、気に入ったものを随時選んで出し、あるいは「引っ込め」たい。
  • → 表示する画像を特別なディレクトリにアップロードするとか、それ用の名前にするとか、注釈(キャプション)を特別なファイルに入れるとかせず、WPの仕組みだけで実現して操作を楽にしたい。
  • かといって、前に書いたように、複数画像の対象への一括設定/解除やキャプションの一括更新ができないとかの馬鹿らしい・面倒なこともしたくない。

一方、表示候補の画像を検索するために対象に「マーク」を付けたいのだが、標準のWPだと画像にはタグなどが付けられないという問題がある。

それらが付けられるのは、投稿などだけ。

WPのカスタムフィールドを使えば実装できそうだが、使い勝手が良くない。そこで、プラグインで何とかできないか探したところ、Media Library Assistant(以下、MLA)というものが見付かった。※ 本来は、WPのギャラリー(複数画像をまとめて出す部品: この投稿の一番下にあるもの)を高機能にするものだが、上記のような、画像など(attachment)にタグなどを付ける機能を持っている。

※これは ものすごく高機能で、僕の用途には もったいないくらいで、とても使いこなせない。今回も、本来の用法でないために却って苦労したｗ

なお、単にランダムに画像を出すだけなら いろいろあるのだが、特に、タグなどで出す候補を指定できるものは なかった。

次のような処理にした。

• ギャラリーに表示する候補画像(画像以外、動画なども可能なはず)一覧を抽出できるように、MLAのattachment tag(Att. tag(画像: 右端の列))にギャラリー名(今回は"my_gallery"とした)を設定する。
  • こうすることで、ギャラリーに登録された画像を一覧することができる。
• 画像のキャプションはWPのTitle(画像: サムネイルの右の列)に設定する。
  • カスタムフィールドなどでも可能だが、使い勝手(特に一括更新)を考慮して そうした。
• ページの表示時は以下の処理を行う。 (注: 変更あり。最後に書く。: 9/14 8:42)
  1. 表示する画像情報がキャッシュされているか調べる。
  2. キャッシュされている場合、
     1. キャッシュから取得した画像情報からURLとキャプションを取得する。
  3. キャッシュされていない場合、
     1. ギャラリーの全画像数を取得する。
     2. 乱数で その中の1枚を選ぶ。
     3. 選んだ画像のURLとキャプションを取得する。
     4. そのURLとキャプションをキャッシュに格納する(今回は生存時間(TTL)は20分とした)。
  4. 画像のURLとキャプションをページの右上に表示する。

なお、前の版では、表示する画像をページ表示部とは別のプログラムで検索・選択していたが、今回はページ表示部だけで完結している。一長一短だが、こちらのほうが保守性は良い。

それから、やはり前に書いたが、表示する画像をページを表示するたびに検索するのは重そうなので、画像の生存時間(TTL)分キャッシュしておいて、その間は検索しないようにした。

キャッシュにはPHPのAPCuを使った。最初はファイルを使ったが、排他制御が厄介なのでAPCuにした。APCuにはTTL経過後にエントリがなくなる機能があるので、生存時間の実装がとても容易だった。

が、APCuにも排他制御の問題(複数のプロセスが同時にキャッシュを更新する場合)はあって、(この用途では必要ではないが、)一応実装した。apcu_entry()という関数を使った。

複数プロセスで同時に※キャッシュに書き込もうとした場合は、(当然ながら)先の情報を採用し、後から書き込むプロセスは、それまでに選んだものを破棄して先に書き込まれた情報を使う(すげ替える)ようにした。破棄した分の処理が無駄になって効率が悪いが、正しい方法は すぐには分からないので、とりあえず こうした。

※実際には同時でなく、どちらかが先になる。マルチプロセッサ/コアの場合は難しいが、OSが ちゃんと処理しているのだろう。

いろいろ苦労して(また疲れて)、動くようになった。結果は このページの右上のとおり(見るたびに変わっているはず)。

と、一言で終わってしまうが、いくら苦労したって、ちゃんと動けば それで終わりだｗ

 

(9/13 20:31, 9/14 8:42) 表示する画像の選択方法について

上述のように、当初は乱数で選ぶようにしていたが、様子を見ていたら、(PSにも書いたように、)ばらつき・偏りが大きいことが分かった。具体的には、頻繁に出る画像と なかなか出ないものがあった。気になって調べてみたら、最高/最低頻度の比が10前後と随分大きかった。

乱数の作り方・使い方に問題があるかと思って改良してみたが、余り改善できなかった。それから、通常の生成関数方法(PHPのrand())以外に いろいろ試したら※頻度比は2-3程度になったが、全く気に入らなかった。

僕としては全部の画像を平等に出したいので、特定のものが頻繁に出るのは全く許容できない。もし、特別気に入っているものを頻繁に出したいなら、そういう処理にする。

そういう用途では、音楽プレーヤーのような「シャフル」がいいのだろう。(処理が複雑になるのを別とすれば、)画像数が少なければ問題ないが、多くなった場合には一覧を作るのに時間が掛かりそうだ。

※試した内容や結果などの詳細は別の稿に書きたい。(→ 書いた) ただ、どの方法も「元」は同じ処理のようなのか、(下にも書いたが、)何万回も試行(実行)しないとだめなのか、頻度比に大きな違いはなかった。= 「効果なし」だった。

どうやら試行(実行)回数が少ないとばらつきが出るようだが、1000回以上でも頻度比が2では使い物にならないと感じた。

それで、実際の使い方に立ち戻って考えてみた。: ページを見る方にとっては、ページの変わる順番がどうであろうと、(一定時間経過後に)見るたびに変わればいいので、ライブラリ(ギャラリー)に格納された順番に表示するようにした。 → 最初はギャラリーの最初の画像を、切り替わりの時間になったら次に、最後まで行ったら最初に戻るようにした。

切り替わり時間(20分)ごとにリロードして表示されている画像の内容またはURLを記録するのを数十回も続けるのを2周以上※するような奇特熱心な読者にはバレるが、さすがにそういう方は居ないので大丈夫だ。

※計算したら、一周で約10時間掛かる・・・ → 実際にやるなら、スクリプトなどが良さそうだｗ

なんて余計なことを書かなければ いいのに、技術者なので つい書くｗ

変更後の処理は以下である。

1. 現在表示されている画像の情報がキャッシュされているか調べる。
2. キャッシュされている場合、
   1. キャッシュに格納した時刻から、現在表示されている画像の表示(経過)時間を求める。
   2. 画像の表示時間が切り替え時間(今回は20分)を超えている場合、
      1. キャッシュから取得した画像情報から現在表示されている画像の番号を取得する。
      2. 取得した番号+1の画像を選択する。
         • ただし、ギャラリー中の画像数以上になったら0(最初)にする。
   3. そうでない場合は、以降は実行しないで終わる。
3. キャッシュされていない場合、
   1. ギャラリー中の最初の画像(番号= 0)を選択する。
4. 選択した画像のURLとキャプションを取得する。
   • 画像の番号を指定してギャラリーから取り出す。
5. そのURLとキャプションと画像番号をキャッシュに格納する(生存時間(TTL)は無限)。
6. 画像のURLとキャプションをページの右上に表示する。

この変更のため、最後に表示した(現在表示されている)画像の番号も画像情報のキャッシュに保存するようにした。また、最後に表示した画像が分からなくなっては困るので、そのキャッシュの生存時間(TTL)を無限にし、画像を切り替えるタイミングは自分で計算するようにした。

この場合も複数プロセスでのキャッシュに対する同時アクセスは起こるが、どのプロセスの次の画像も同じ番号になるはずなので、構わず上書きするようにした。

 

PS. 本題には関係ないが、前の版もそうだったが、乱数が一様でないような感じがする。前の版は中央辺りに頻度の高いものがあり、その隣は頻度が他の1/2くらいと低かった。

今回は、まだサンプル数が少ないものの、全く出ない値(≒ 画像)がある。特に、最小と最大が出ていないのは、プログラムに誤りがあるのかも知れない。。。

(9/14 9:05) その後、やっぱり我慢ならないので、本文に追記したとおり、乱数は止めた。