NotebookLMを使って、真剣にベイズ推定の問題を解いてみた【2.ランダムな占い】

はじめに

そもそものきっかけは、ベイズ推定とは何？という程度の知識レベルで、AtcoderのAH030を解こうとすると、適当なロジックで試行錯誤して、時間を浪費したところで大してスコアも伸びずギブアップするだけなので、ゼロから手を動かして知識を得たい。

一方で、従来型の独学での自習は限度があるので、NotebookLMを使うとどのようなメリットがあるのか試してみようかと思いました。

• NotebookLMを初めて使っての気づき 【NotebookLM編】
• AHC030に関する気づき
  • 1.機械的にjavaへ移植
  • 2.ランダムな占い【この記事】
  • 3.相互情報量を最大化する占い
  • 4.事後確率とgiveup改良
  • 5.数を絞ったランダムなプール
  • 6.なんちゃってテキスト変換ツールでcppソースをjavaソースに変換
  • 7.java完成版

とっても参考になる題材はこちら→AHC典型解法シリーズ第3弾「ベイズ推定」

M=2において、プールサイズが最大となるテストデータ

問題文から、N=20が最大値で、油田の面積(d)が最小4のため、2x2の形がmax_i, max_jが共に1となり、left_topの座標が縦横共に0から18まで指定できるので、(19×19)×(19×19)=130,321通りとなります。

ホントにその数になるのか、まず手作業で入力データを作ります。

20 2 0.01
4 0 0 0 1 1 0 1 1
4 0 0 0 1 1 0 1 1
0 0
18 18
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
：
（適当に正規分布の乱数を800行）

① 04_all_pool_random_divination.java

ランダムな占いで実行してみますが、デバッグ用に仕込みを入れます。

M=2しか対応していないので、seed0から99のバッチ実行のために、対応していない場合は冒頭で終了させます。（スコア0となる）

        if (input.m != 2) System.exit(0);

long startTimeはあちこちで使いたいので、最終行にstatic変数として移動。
デバッグ出力用に、起動してからのミリ秒を4桁数値の文字列を作れるようにします。

    static String now() {
    	return String.format("%04d:", System.currentTimeMillis()-startTime);
    }
    static long startTime = System.currentTimeMillis();

whileでループしてますが、ターン数が欲しいので、変数t=0からループします。

for (int t=0; true; t++) {

冒頭にpool.size()と、各ターンにpool.get(0).pxIfRを出力します。

            System.err.println(now()+t+" pool.get(0).pxIfR="+pool.get(0).pxIfR);

実行するとクエリが35件しか出ませんが、今はデバッグ出力があるので、内訳が見えます。

0051: pool.size()=130321
0088:0 pool.get(0).pxIfR=7.673360394717659E-6
0193:1 pool.get(0).pxIfR=4.9632872855075336E-5
0238:2 pool.get(0).pxIfR=1.7614041235043389E-4
：
2616:32 pool.get(0).pxIfR=0.09734594967055978
2725:33 pool.get(0).pxIfR=0.1039300549575216
2833:34 pool.get(0).pxIfR=0.08912393859176292

極端な入力データですが、1ターンあたり100ミリ秒で、3秒制限で30クエリは当たり前で、無理ぽいです。

giveupの実装

giveupが空なので、もう一度javaに翻訳を依頼したら、今度はgiveup実装（とmine実装）が入っていて、なぜ？という感じです。
中身を比べてみると、古い方がList<Pair<Integer, Integer>> coordinates;で、新しい方がList<int[]> coordinatesなので、新しい方に乗り換えることにします。

先ほどのデバッグ出力などを反映します。
区別するため、giveupの冒頭にもログを出しておきます。

2532:23 pool.get(0).pxIfR=0.042346688059822904
2667:24 pool.get(0).pxIfR=0.04580833649225044
2803:25 pool.get(0).pxIfR=0.04581430599597274
2804:giveup
Score = 398844423

ようやく無理な場合にもスコアが出るようになりました。

ソースレビュー

先頭からソースコードを読みます。

一番違和感があったのが、むかしはint[] volume;だったものがbyte[] volume;になっていて、totalの最大値は400だから、オーバーフローするよな・・・ということで、また極端なテストデータを作る。
※javaはScannerが改行も区別せずに解析するので、本来1行のところが11行に分かれてます

20 2 0.01
200
0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 
1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 
2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 
3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 3 11 3 12 3 13 3 14 3 15 3 16 3 17 3 18 3 19 
4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 4 11 4 12 4 13 4 14 4 15 4 16 4 17 4 18 4 19 
5 0 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 5 11 5 12 5 13 5 14 5 15 5 16 5 17 5 18 5 19 
6 0 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 6 11 6 12 6 13 6 14 6 15 6 16 6 17 6 18 6 19 
7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7 11 7 12 7 13 7 14 7 15 7 16 7 17 7 18 7 19 
8 0 8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8 8 9 8 10 8 11 8 12 8 13 8 14 8 15 8 16 8 17 8 18 8 19 
9 0 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 9 10 9 11 9 12 9 13 9 14 9 15 9 16 9 17 9 18 9 19 
200
0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 
1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 
2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 
3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 3 11 3 12 3 13 3 14 3 15 3 16 3 17 3 18 3 19 
4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 4 11 4 12 4 13 4 14 4 15 4 16 4 17 4 18 4 19 
5 0 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 5 11 5 12 5 13 5 14 5 15 5 16 5 17 5 18 5 19 
6 0 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 6 11 6 12 6 13 6 14 6 15 6 16 6 17 6 18 6 19 
7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7 11 7 12 7 13 7 14 7 15 7 16 7 17 7 18 7 19 
8 0 8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8 8 9 8 10 8 11 8 12 8 13 8 14 8 15 8 16 8 17 8 18 8 19 
9 0 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 9 10 9 11 9 12 9 13 9 14 9 15 9 16 9 17 9 18 9 19 
0 0
10 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
：
（適当に正規分布の乱数を800行）

State.addQueryのos.topLeftQueryVolumes.get(topLeft).add(c);する部分にチェックを入れて強制終了して、クエリ条件を0.5から0.9にして実行すると、見事に落ちる。

04_all_pool_random_divination.cppをjavaに翻訳して。ただし、整数はbyteやByteを使わずに、intやIntegerを使ってください。

これで作ったら、今度は収束しない。えー。
何がデグレードしているのか思いきや、乱数の発生。

        public double random() { return (next() & 0xFFFFFFFFFFFFFFFFL) * (1.0 / 18446744073709551615.0); }

この乱数、割る数(符号なし64ビット最大数)が多すぎて、-0.5から0.5の乱数が出てくるので、r<0.5の条件でクエリを出すと、毎回すべてを選ぶクエリが出て、まったく尤度が収束しない。

04_all_pool_random_divination.cppをjavaに翻訳して。ただし、整数はbyteやByteを使わずに、intやIntegerを使ってください。前回のソースは対数尤度が更新されなくなっています。

今度は動くと思ったら、seed25がクエリを使い切って、ペナルティスコアで終わる。
乱数が63ビット最大数で割ったやつ。

        public double random() {
            return (double)(next() & 0x7FFFFFFFFFFFFFFFL) / Long.MAX_VALUE;
        }

むかし動いていたと思うソースを見ると、

        public double random() { return (next() >>> 11) * 0x1.0p-53; }

こんなことで結果が左右されるのか。
ホントに運任せなんだなと実感。

なお、totalが400となる全部埋まっているやつ。
クエリを使い切るが、トップと2番手をログに出すと、

1518:798 pxIfR[0]=0.50 pxIfR[1]=0.50
1522:799 pxIfR[0]=0.50 pxIfR[1]=0.50
1526:800 pxIfR[0]=0.50 pxIfR[1]=0.50
Score = 1000000000

こうなって終わらないケースもあるのね。

• 油田Aが上、油田Bが下
• 油田Bが上、油田Aが下
  のレイアウトは異なるが、クエリのビットパターンは同じなのね。

乱数による違い

1st: (double)(next() & 0x7FFFFFFFFFFFFFFFL) / Long.MAX_VALUE;
2nd: (next() >>> 11) * 0x1.0p-53;
3rd: Random.nextDouble();
4th: cpp版

seed	N	M	eps	total	1st	2nd	3rd	4th
0	15	2	0.01	38	1,445,937	1,327,125	1,127,426	866,481
2	13	2	0.07	68	2,006,971	2,417,617	5,070,120	2,170,685
3	19	2	0.08	114	3,136,378	2,541,408	3,196,577	2,237,383
8	11	2	0.13	46	6,615,826	4,553,827	5,406,208	11,219,032
9	14	2	0.17	41	11,740,962	13,396,970	12,744,716	17,157,175
20	10	2	0.08	41	2,210,574	2,991,399	1,858,524	2,684,369
21	13	2	0.15	50	6,560,863	7,980,229	14,009,250	10,730,681
25	13	2	0.2	27	1,000,000,000	13,247,220	15,233,752	104,569,930
27	12	2	0.2	56	13,724,556	14,047,888	9,278,628	21,683,423
38	13	2	0.06	95	2,360,609	541,775	1,434,019	1,761,736
42	19	2	0.04	148	2,347,763	1,653,203	1,194,401	1,334,046
45	15	2	0.07	83	2,750,846	2,185,951	3,470,842	2,540,834
61	15	2	0.12	52	9,608,072	9,569,245	5,292,366	10,925,874
65	14	2	0.03	62	1,958,057	1,325,300	1,521,813	1,300,246
68	20	2	0.19	190	6,012,882	12,978,748	10,247,067	10,099,656
85	10	2	0.09	50	4,634,583	3,281,698	3,715,208	4,904,346
88	15	2	0.04	68	1,820,944	2,185,951	1,874,357	2,790,980
90	12	2	0.15	49	7,580,820	6,560,898	14,811,889	7,001,686
93	10	2	0.05	23	5,620,020	6,292,704	9,131,199	4,608,564
94	16	2	0.03	105	1,261,828	892,833	2,982,593	1,234,386

eps=0.2はホントに運次第。
どれがよいという話ではなく、ソースを作り直すたびに、動作が変わり、本体がデグレードしていないかチェックばかりしていたが、Xorshiftを常に貼り付けるか、javaのRandomに置き換えるか、決めておいた方がよい。

ソース置き場

• 03 ランダムな占い