Debian Codegraph @

test/include/srfi-194-zipf-test.scm

raw
1 ;
2 ; zipf-test.scm
3 ; Unit tests for the Zipf (zeta) distribution.
4 ;
5 ; Created by Linas Vepstas 10 July 2020
6 ; Nominated for inclusion in srfi-194
7
8 ; ------------------------------------------------------------------
9 ; Debug utility for gnuplot graphing.
10 ; You can use this to dump a vector to a tab-delimited file.
11 (define (vector-to-file vec filename)
12 (define (write-vec)
13 (for-each
14 (lambda (i)
15 (define index (+ i 1))
16 (define val (vector-ref vec i))
17 (display index)
18 (display " ")
19 (display val)
20 (newline))
21 (iota (vector-length vec))))
22 (with-output-to-file filename write-vec))
23
24 ; ------------------------------------------------------------------
25 ; Simple test harness for exploring paramter space.
26 ;
27 ; Take REPS samples from the zeta distribution (ZGEN NVOCAB ESS QUE)
28 ; Accumulate them into NVOCAB bins.
29 ; Normalize to unit probability (i.e. divide by NVOCAB)
30 ;
31 ; The resulting distribution should uniformly converge to C/(k+q)^s
32 ; for 1 <= k <= NVOCAB where C is a normalization constant.
33 ;
34 ; This compares the actual distribution to the expected convergent
35 ; and reports an error if it is not within TOL of the convergent.
36 ; i.e. it computes the Banach l_0 norm of (distribution-convergent)
37 ; TOL is to be given in units of standard deviations. So, for example,
38 ; setting TOL to 6 gives a six-sigma bandpass, allowsing the tests to
39 ; usually pass.
40 ;
41 (define (test-zipf ZGEN NVOCAB ESS QUE REPS TOL)
42
43 ; Bin-counter containing accumulated histogram.
44 (define bin-counts
45 (let ((bin-counts (make-vector NVOCAB 0)))
46 ; Accumulate samples into the histogram.
47 (generator-for-each
48 (lambda (SAMP)
49 (define offset (- SAMP 1))
50 (vector-set! bin-counts offset (+ 1 (vector-ref bin-counts offset))))
51 (gtake (ZGEN NVOCAB ESS QUE) REPS))
52 bin-counts))
53
54
55 ; Verify the distribution is within tolerance.
56 ; This is written out long-hand for easier debuggability.
57
58 ; Frequency is normalized to be 0.0 to 1.0
59 (define frequency (vector-map (lambda (n) (/ n REPS)) bin-counts))
60 (define probility (vector-map (lambda (n) (inexact n)) frequency))
61
62 ; Sequence 1..NVOCAB
63 (define seq
64 (vector-unfold (lambda (i x) (values x (+ x 1))) NVOCAB 1))
65
66 ; Sequence 1/(k+QUE)^ESS
67 (define inv-pow (vector-map
68 (lambda (k) (expt (+ k QUE) (- (inexact ESS)))) seq))
69
70 ; Hurwicz harmonic number sum_1..NVOCAB 1/(k+QUE)^ESS
71 (define hnorm
72 (vector-fold
73 (lambda (sum cnt) (+ sum cnt)) 0 inv-pow))
74
75 ; The expected distribution
76 (define expect
77 (vector-map (lambda (x) (/ x hnorm)) inv-pow))
78
79 ; Convert to floating point.
80 (define prexpect (vector-map (lambda (x) (inexact x)) expect))
81
82 ; The difference
83 (define diff (vector-map (lambda (x y) (- x y)) probility prexpect))
84
85 ; Re-weight the tail by k^{s/2}. This seems give a normal error
86 ; distribution. ... at least, for small q. Problems for large q
87 ; and with undersampling; so we hack around that.
88 (define err-dist
89 (if (< 10 QUE) diff
90 (vector-map (lambda (i x) (* x (expt (+ i 1) (* 0.5 ESS))))
91 (list->vector (iota (vector-length diff)))
92 diff)))
93
94 ; Normalize to unit root-mean-square.
95 (define rms (/ 1 (sqrt (* 2 3.141592653 REPS))))
96 (define norm-dist (vector-map (lambda (x) (/ x rms)) err-dist))
97
98 ; Maximum deviation from expected distribution (l_0 norm)
99 (define l0-norm
100 (vector-fold
101 (lambda (sum x) (if (< sum (abs x)) (abs x) sum)) 0 norm-dist))
102
103 ; The mean.
104 (define mean (/
105 (vector-fold (lambda (sum x) (+ sum x)) 0 norm-dist)
106 NVOCAB))
107
108 (define root-mean-square (sqrt (/
109 (vector-fold (lambda (sum x) (+ sum (* x x))) 0 norm-dist)
110 NVOCAB)))
111
112 ; The total counts in the bins should be equal to REPS
113 (test-assert
114 (equal? REPS
115 (vector-fold
116 (lambda (sum cnt) (+ sum cnt)) 0 bin-counts)))
117
118 ; Test for uniform convergence.
119 (test-assert (<= l0-norm TOL))
120
121 ; Should not random walk too far away.
122 ; Could tighten this with a proper theory of the error distribution.
123 (test-assert (< (abs mean) 3))
124 ; I don't understand the error distribution ....
125 ; (test-assert (and (< 0.4 root-mean-square) (< root-mean-square 1.5)))
126
127 (test-assert (<= l0-norm TOL))
128
129 ; Utility debug printing
130 ;(vector-to-file probility "probility.dat")
131 ;(vector-to-file prexpect "prexpect.dat")
132 ;(vector-to-file diff "diff.dat")
133 #f)
134
135 ; Explore the parameter space.
136 (define (zipf-test-group)
137
138 ; The unit test is computes something that is "almost" a standard
139 ; deviation for the error distribution. Except, maybe not quite,
140 ; I don't fully understand the theory. So most tests seem to come
141 ; in fine in well-under a six-sigma deviation, but some of the wilder
142 ; paramter choices misbehave, so six-sigma doesn't always work.
143 ; Also, when the number of bins is large, its easy to under-sample,
144 ; some bins end up empty and the std-dev is thrown off as a result.
145 ; Thus, the tolerance bounds below are hand-adjusted.
146 (define six-sigma 6.0)
147
148 (define hack-que 3.0)
149
150 ; Zoom into s->1
151 (test-zipf make-zipf-generator 30 1.1 0 1000 six-sigma)
152 (test-zipf make-zipf-generator 30 1.01 0 1000 six-sigma)
153 (test-zipf make-zipf-generator 30 1.001 0 1000 six-sigma)
154 (test-zipf make-zipf-generator 30 1.0001 0 1000 six-sigma)
155 (test-zipf make-zipf-generator 30 1.00001 0 1000 six-sigma)
156
157 (test-zipf make-zipf-generator 30 (+ 1 1e-6) 0 1000 six-sigma)
158 (test-zipf make-zipf-generator 30 (+ 1 1e-8) 0 1000 six-sigma)
159 (test-zipf make-zipf-generator 30 (+ 1 1e-10) 0 1000 six-sigma)
160 (test-zipf make-zipf-generator 30 (+ 1 1e-12) 0 1000 six-sigma)
161 (test-zipf make-zipf-generator 30 (+ 1 1e-14) 0 1000 six-sigma)
162 (test-zipf make-zipf-generator 30 1 0 1000 six-sigma)
163
164 ; Verify improving uniform convergence
165 (test-zipf make-zipf-generator 30 1 0 10000 six-sigma)
166 (test-zipf make-zipf-generator 30 1 0 100000 six-sigma)
167
168 ; Larger vocabulary
169 (test-zipf make-zipf-generator 300 1.1 0 10000 six-sigma)
170 (test-zipf make-zipf-generator 300 1.01 0 10000 six-sigma)
171 (test-zipf make-zipf-generator 300 1.001 0 10000 six-sigma)
172 (test-zipf make-zipf-generator 300 1.0001 0 10000 six-sigma)
173 (test-zipf make-zipf-generator 300 1.00001 0 10000 six-sigma)
174
175 ; Larger vocabulary. Take more samples....
176 (test-zipf make-zipf-generator 3701 1.1 0 40000 six-sigma)
177 (test-zipf make-zipf-generator 3701 1.01 0 40000 six-sigma)
178 (test-zipf make-zipf-generator 3701 1.001 0 40000 six-sigma)
179 (test-zipf make-zipf-generator 3701 1.0001 0 40000 six-sigma)
180 (test-zipf make-zipf-generator 3701 1.00001 0 40000 six-sigma)
181
182 ; Huge vocabulary; few samples. Many bins will be empty,
183 ; causing the std-dev to get large.
184 (test-zipf make-zipf-generator 43701 (+ 1 1e-6) 0 60000 9.5)
185 (test-zipf make-zipf-generator 43701 (+ 1 1e-7) 0 60000 9.5)
186 (test-zipf make-zipf-generator 43701 (+ 1 1e-9) 0 60000 9.5)
187 (test-zipf make-zipf-generator 43701 (+ 1 1e-12) 0 60000 9.5)
188 (test-zipf make-zipf-generator 43701 1 0 60000 9.5)
189
190 ; Large s, small range
191 (test-zipf make-zipf-generator 5 1.1 0 1000 six-sigma)
192 (test-zipf make-zipf-generator 5 2.01 0 1000 six-sigma)
193 (test-zipf make-zipf-generator 5 4.731 0 1000 six-sigma)
194 (test-zipf make-zipf-generator 5 9.09001 0 1000 six-sigma)
195 (test-zipf make-zipf-generator 5 13.45 0 1000 8.0)
196
197 ; Large s, larger range. Most histogram bins will be empty
198 ; so allow much larger error margins.
199 (test-zipf make-zipf-generator 130 1.5 0 30000 six-sigma)
200 (test-zipf make-zipf-generator 130 2.03 0 30000 9.0)
201 (test-zipf make-zipf-generator 130 4.5 0 30000 17.0); [SK] TOL loosened a bit
202 (test-zipf make-zipf-generator 130 6.66 0 30000 24.0)
203
204 ; Verify that accuracy improves with more samples.
205 (test-zipf make-zipf-generator 129 1.1 0 10000 six-sigma)
206 (test-zipf make-zipf-generator 129 1.01 0 10000 six-sigma)
207 (test-zipf make-zipf-generator 129 1.001 0 10000 six-sigma)
208 (test-zipf make-zipf-generator 129 1.0001 0 10000 six-sigma)
209 (test-zipf make-zipf-generator 129 1.00001 0 10000 six-sigma)
210
211 ; Non-zero Hurwicz parameter
212 (test-zipf make-zipf-generator 131 1.1 0.3 10000 six-sigma)
213 (test-zipf make-zipf-generator 131 1.1 1.3 10000 six-sigma)
214 (test-zipf make-zipf-generator 131 1.1 6.3 10000 six-sigma)
215 (test-zipf make-zipf-generator 131 1.1 20.23 10000 six-sigma)
216
217 ; Negative Hurwicz parameter. Must be greater than branch point at -0.5.
218 (test-zipf make-zipf-generator 81 1.1 -0.1 1000 six-sigma)
219 (test-zipf make-zipf-generator 81 1.1 -0.3 1000 six-sigma)
220 (test-zipf make-zipf-generator 81 1.1 -0.4 1000 six-sigma)
221 (test-zipf make-zipf-generator 81 1.1 -0.499 1000 six-sigma)
222
223 ; A walk into a stranger corner of the parameter space.
224 (test-zipf make-zipf-generator 131 1.1 41.483 10000 hack-que)
225 (test-zipf make-zipf-generator 131 2.1 41.483 10000 hack-que)
226 (test-zipf make-zipf-generator 131 6.1 41.483 10000 hack-que)
227 (test-zipf make-zipf-generator 131 16.1 41.483 10000 hack-que)
228 (test-zipf make-zipf-generator 131 46.1 41.483 10000 hack-que)
229 (test-zipf make-zipf-generator 131 96.1 41.483 10000 hack-que)
230
231 ; A still wilder corner of the parameter space.
232 (test-zipf make-zipf-generator 131 1.1 1841.4 10000 hack-que)
233 (test-zipf make-zipf-generator 131 1.1 1.75e6 10000 hack-que)
234 (test-zipf make-zipf-generator 131 2.1 1.75e6 10000 hack-que)
235 (test-zipf make-zipf-generator 131 12.1 1.75e6 10000 hack-que)
236 (test-zipf make-zipf-generator 131 42.1 1.75e6 10000 hack-que)
237
238 ; Lets try s less than 1
239 (test-zipf make-zipf-generator 35 0.9 0 1000 six-sigma)
240 (test-zipf make-zipf-generator 35 0.99 0 1000 six-sigma)
241 (test-zipf make-zipf-generator 35 0.999 0 1000 six-sigma)
242 (test-zipf make-zipf-generator 35 0.9999 0 1000 six-sigma)
243 (test-zipf make-zipf-generator 35 0.99999 0 1000 six-sigma)
244
245 ; Attempt to force an overflow
246 (test-zipf make-zipf-generator 437 (- 1 1e-6) 0 1000 six-sigma)
247 (test-zipf make-zipf-generator 437 (- 1 1e-7) 0 1000 six-sigma)
248 (test-zipf make-zipf-generator 437 (- 1 1e-9) 0 1000 six-sigma)
249 (test-zipf make-zipf-generator 437 (- 1 1e-12) 0 1000 six-sigma)
250
251 ; Almost flat distribution
252 (test-zipf make-zipf-generator 36 0.8 0 1000 six-sigma)
253 (test-zipf make-zipf-generator 36 0.5 0 1000 six-sigma)
254 (test-zipf make-zipf-generator 36 0.1 0 1000 six-sigma)
255
256 ; A visit to crazy-town -- increasing, not decreasing exponent
257 (test-zipf make-zipf-generator 36 0.0 0 1000 six-sigma)
258 (test-zipf make-zipf-generator 36 -0.1 0 1000 six-sigma)
259 (test-zipf make-zipf-generator 36 -1.0 0 1000 six-sigma)
260 (test-zipf make-zipf-generator 36 -3.0 0 1000 six-sigma)
261
262 ; More crazy with some Hurwicz on top.
263 (test-zipf make-zipf-generator 16 0.0 0.5 1000 six-sigma)
264 (test-zipf make-zipf-generator 16 -0.2 2.5 1000 six-sigma)
265 (test-zipf make-zipf-generator 16 -1.3 10 1000 six-sigma)
266 (test-zipf make-zipf-generator 16 -2.9 100 1000 six-sigma)
267
268 ; (test-end "srfi-194-zipf")
269 )