Kit.xtl

1⍝│ Kit: the experiment kit's data sets, each with a known structure and
2⍝│ made from its own seed: flat (Gaussian clusters), directional
3⍝│ (classes that differ by direction, not length) and hierarchical (a
4⍝│ tree, its distances along the tree, a class per branch, and a plain
5⍝│ layout of it in the plane); and the seeded numbers they are made of.
6⍝│ Import it with an alias of your choice: "kt:" u_se< "Kit".
7⍝│ Put libs/Kit/src on XETAL_PATH ("just path"); the reference is libs/Kit/docs.
8⍝│ Names with l: are exported; those under h: are private to this file.
9⍝│
10⍝│ A data set is (X, y): X a matrix, one point per row; y its labels,
11⍝│ 1 to k. Every set is a function of its seed and its sizes alone (not
12⍝│ of the run's seed, nor of what was drawn before it), so two demos
13⍝│ asking for the same set get the same numbers: the seed is a whole
14⍝│ number, and the generator is Park and Miller's (1988) multiplier
15⍝│ 16807 modulo 2^31 - 1, written out here until X_eTaL-libraries'
16⍝│ Random takes a seed of its own (docs/xetal-libraries-asks.md, GL8).
17⍝│ The comparisons this repository makes are between geometries on the
18⍝│ same data: what these functions give is held equal across them.
19
20"mf:" u̲se< "Manifold"
21"gr:" u̲se< "Graphs"
22
23⍝━━ Seeded numbers
24
25⍝│ u̲niform (seed, n): n Floats in [0, 1), each a function of the
26⍝│ seed and its place: the Park-Miller sequence x -> 16807 x mod
27⍝│ (2^31 - 1) started from 1 + |seed| mod (2^31 - 2) (so seed 0 is a
28⍝│ seed like any other and no seed is the sequence's fixed point 0),
29⍝│ divided by 2^31 - 1. The same seed gives the same numbers in any
30⍝│ run.
31⍝│ >> "kt:" u_se< "Kit"
32⍝│ >> kt:u_niform (42, 3)
33⍝│ 0.00033653387815530127 0.6561248901561484 0.4910288543864288
34ˡu̲niform ← { (seed, n) →
35  m ← 2147483647
36  start ← 1 + (a̲bs seed) m̲od m − 1
37  (v, _) ← n '{ (v, x) → y ← (16807 × x) m̲od m◆ (v c̲at y, y) } p̲ower (0 r̲eshape 0, start)
38  (f̲loat v) ÷ f̲loat m
39}
40
41⍝│ n̲ormal (seed, n): n Floats from the standard normal distribution
42⍝│ (mean 0, standard deviation 1), by Box and Muller from 2n uniform
43⍝│ numbers of the seed.
44⍝│ >> "kt:" u_se< "Kit"
45⍝│ >> kt:n_ormal (42, 2)
46⍝│ -0.025904525013204074 -0.2561352551643429
47ˡn̲ormal ← { (seed, n) →
48  u ← ˡu̲niform (seed, 2 × n)
49  a ← n t̲ake u
50  b ← n d̲rop u
51  (s̲qrt -2.0 × l̲og 1.0 − a) × c̲os 6.283185307179586 × b
52}
53
54⍝│ n̲ormals (seed, rows, cols): a rows by cols matrix of standard
55⍝│ normal numbers of the seed.
56ʰn̲ormals ← { (seed, rows, cols) → (rows c̲at cols) r̲eshape ˡn̲ormal (seed, rows × cols) }
57
58⍝━━ Flat clusters
59
60⍝│ f̲lat (seed, k, n, d, spread): k Gaussian clusters of n points
61⍝│ each in d dimensions: the k centers are standard normal numbers of
62⍝│ the seed scaled by 4 (so clusters sit a few units apart), and each
63⍝│ point is its center plus spread times a standard normal vector;
64⍝│ (X, y), X of k n rows and y the cluster of each row, 1 to k, in
65⍝│ order. The structure is flat: straight-line distance is the right
66⍝│ one, and a point's nearest neighbors are mostly its own cluster
67⍝│ when spread is well under the centers' spacing.
68⍝│ >> "kt:" u_se< "Kit"
69⍝│ >> (X, y) := kt:f_lat (1, 2, 2, 2, 0.1)
70⍝│ >> y
71⍝│ 1 1 2 2
72⍝│ >> s_hape X
73⍝│ 4 2
74ˡf̲lat ← { (seed, k, n, d, spread) →
75  C ← 4.0 × ʰn̲ormals (seed, k, d)
76  N ← ʰn̲ormals (seed + 1, k × n, d)
77  y ← n ʰe̲ach r̲ange k
78  X ← ((f̲loat spread) × N) + y s̲elect C
79  (X, y)
80}
81
82⍝│ n e̲ach v: every item of v repeated n times, in order (a general
83⍝│ word, written out until GL2 lands).
84ʰe̲ach ← { n v → r̲avel o̲\ (n c̲at t̲ally v) r̲eshape v }
85
86⍝━━ Directions
87
88⍝│ d̲irections (seed, k, n, cone): k classes of n points in three
89⍝│ dimensions that differ by direction and not by length: each class
90⍝│ has a direction (a seeded standard normal vector put onto the unit
91⍝│ sphere) and each point is that direction plus cone times a
92⍝│ standard normal vector, put back onto the sphere, then scaled by a
93⍝│ length drawn between 0.5 and 2 (uniform), so the lengths carry
94⍝│ nothing about the class; (X, y). The structure is directional: the
95⍝│ angle between points is the right distance, and their straight-line
96⍝│ distance mixes in the lengths.
97⍝│ >> "kt:" u_se< "Kit"
98⍝│ >> (X, y) := kt:d_irections (7, 2, 2, 0.1)
99⍝│ >> y
100⍝│ 1 1 2 2
101⍝│ >> s_hape X
102⍝│ 4 3
103ˡd̲irections ← { (seed, k, n, cone) →
104  D ← ᵐᶠs̲phereProject ʰn̲ormals (seed, k, 3)
105  N ← ʰn̲ormals (seed + 1, k × n, 3)
106  y ← n ʰe̲ach r̲ange k
107  U ← ᵐᶠs̲phereProject ((f̲loat cone) × N) + y s̲elect D
108  lengths ← 0.5 + 1.5 × ˡu̲niform (seed + 2, k × n)
109  (lengths ʰs̲caleRows U, y)
110}
111
112⍝│ s v s̲caleRows M: each row of M scaled by the matching item of s.
113ʰs̲caleRows ← { s M → M × s 'l̲eft t̲able o̲ffsets 2 s̲elect s̲hape M }
114
115⍝━━ A tree
116
117⍝│ t̲ree (depth, branching): the edges of a rooted tree in which
118⍝│ every node but the leaves has branching children and every leaf
119⍝│ is depth edges from the root: node 1 is the root and the nodes
120⍝│ are numbered level by level, so node i's children are the nodes
121⍝│ branching (i - 1) + 2 up to branching i + 1. The edges as Graphs
122⍝│ takes them: two rows, from (the parent) over to (the child). Depth
123⍝│ 4 and branching 2 give 31 nodes and 30 edges.
124⍝│ >> "kt:" u_se< "Kit"
125⍝│ >> kt:t_ree (2, 2)
126⍝│ 1 1 2 2 3 3
127⍝│ 2 3 4 5 6 7
128ˡt̲ree ← { (depth, branching) →
129  n ← ʰn̲odes (depth, branching)
130  child ← 1 d̲rop r̲ange n
131  parent ← 1 + (child − 2) d̲iv branching
132  (2 c̲at n − 1) r̲eshape parent c̲at child
133}
134
135⍝│ The number of nodes of the tree: 1 + b + b^2 + ... + b^depth.
136ʰn̲odes ← { (depth, branching) → '+ r̲/ branching ^ (r̲ange depth + 1) − 1 }
137
138⍝│ t̲reeDistances (depth, branching): the distance between every two
139⍝│ nodes of the tree along it (the number of edges on the one path
140⍝│ between them), by Graphs' shortest paths over the tree's edges
141⍝│ taken both ways: an n by n matrix of Floats, 0 on the diagonal,
142⍝│ 2 depth at most (leaf to leaf through the root).
143⍝│ >> "kt:" u_se< "Kit"
144⍝│ >> kt:t_reeDistances (1, 2)
145⍝│ 0.0 1.0 1.0
146⍝│ 1.0 0.0 2.0
147⍝│ 1.0 2.0 0.0
148ˡt̲reeDistances ← { (depth, branching) →
149  n ← ʰn̲odes (depth, branching)
150  e ← ˡt̲ree (depth, branching)
151  w ← n ᵍʳw̲eighted e c̲at (n − 1) r̲eshape 1
152  ᵍʳs̲hortest ᵍʳu̲ndirected w
153}
154
155⍝│ t̲reeClasses (depth, branching): the class of each node, its
156⍝│ branch: the child of the root it descends from, 1 to branching;
157⍝│ the root itself, which is under no branch, is given class 1 (and
158⍝│ a classifier is excused it: it is alone). So the hierarchical
159⍝│ set's labels, one per node.
160⍝│ >> "kt:" u_se< "Kit"
161⍝│ >> kt:t_reeClasses (2, 2)
162⍝│ 1 1 2 1 1 2 2
163ˡt̲reeClasses ← { (depth, branching) →
164  n ← ʰn̲odes (depth, branching)
165  parent ← f̲irst ˡt̲ree (depth, branching)
166  up ← depth '{ v → '{ c → parent ʰu̲p c } e̲ach v } p̲ower r̲ange n           ⍝ each node's ancestor just under the root (the root stays)
167  1 m̲ax up − 1
168}
169
170⍝│ parent u̲p c: the parent of node c, unless that is the root (or c
171⍝│ is), in which case c: one step up the tree that stops under the root.
172ʰu̲p ← { parent c → c = 1 ? 1◆ p ← (c − 1) s̲elect parent◆ p = 1 ? c◆ p }
173
174⍝│ t̲reeLayout (depth, branching): a plain picture of the tree in
175⍝│ the plane, one row (x, y) per node: the root at the origin, each
176⍝│ level a circle of radius its depth, the nodes of a level spread
177⍝│ evenly round it in their order, so that each subtree is a wedge
178⍝│ (the two children of the root at the top and the bottom, their x
179⍝│ cos of a quarter turn, 0 up to the machine's rounding). It is a
180⍝│ layout, not an embedding that keeps the tree's distances:
181⍝│ the straight-line distance between two nodes of this picture is a
182⍝│ poor copy of their distance along the tree (two leaves of
183⍝│ neighboring branches are near in the picture and 2 depth apart
184⍝│ in the tree), which is what the baseline measures.
185⍝│ >> "kt:" u_se< "Kit"
186⍝│ >> kt:t_reeLayout (1, 2)
187⍝│                                 0.0  0.0
188⍝│  0.00000000000000006123233995736766  1.0
189⍝│ -0.00000000000000018369701987210297 -1.0
190ˡt̲reeLayout ← { (depth, branching) →
191  n ← ʰn̲odes (depth, branching)
192  level ← 1 s̲elect ˡt̲reeDistances (depth, branching)              ⍝ each node's distance from the root
193  before ← '{ L → '+ r̲/ 0 c̲at branching ^ (r̲ange L) − 1 } e̲ach f̲loor level          ⍝ nodes on the levels above
194  on ← f̲loat branching ^ f̲loor level                                 ⍝ nodes on the node's level
195  pos ← (f̲loat (r̲ange n) − before) − 0.5                             ⍝ its place round the circle, from 0.5
196  angle ← 6.283185307179586 × pos ÷ on
197  o̲\ (2 c̲at n) r̲eshape (0.0 + level × c̲os angle) c̲at 0.0 + level × s̲in angle
198}