Learn.xtl

1⍝│ Learn: classic machine learning: k-means, k nearest neighbors, PCA, logistic regression
2⍝│
3⍝│ Import it with an alias of your choice: "ml:" u_se< "Learn".
4⍝│ Put libs/Learn/src on XETAL_PATH ("just path"); the reference is libs/Learn/docs.
5⍝│ Names with l: are exported; h: names are private to this file.
6⍝│
7⍝│ After APLearn's list (k-means, kNN, PCA, logistic regression), each
8⍝│ a fit and a predict: the data X is a matrix, one example per row;
9⍝│ labels count from 1. Every model is whole-array arithmetic, and an
10⍝│ iterative fit is a step repeated by p_ower.
11
12"nn:" u̲se< "NN"
13
14⍝━━ Helpers (private)
15
16⍝│ The squared distance between every row of A (n x d) and every row of B (k x d): n x k.
17ʰd̲ist ← { A B → (('+ r̲/₂ A × A) '+ t̲able '+ r̲/₂ B × B) − 2.0 × A '+ '× i̲nner o̲\ B }
18
19⍝│ X with a column of 1s on the right (for a bias row).
20ʰo̲nes ← { X → X c̲at₂ ((t̲ally X) c̲at 1) r̲eshape 1.0 }
21
22⍝━━ k-means: clusters by their centers
23
24⍝│ C a̲ssign X: the nearest of the centers C (one per row) for each row of X, from 1.
25⍝│ >> "ml:" u_se< "Learn"
26⍝│ >> (2 2 r_eshape 0.0 0.0 10.0 10.0) ml:a_ssign 3 2 r_eshape 1.0 0.0 9.0 9.0 0.0 2.0
27⍝│ 1 2 1
28ˡa̲ssign ← { C X → ⁿⁿa̲rgmax n̲eg X ʰd̲ist C }
29
30⍝│ X k̲step C: one step of k-means (Lloyd's): each center moved to
31⍝│ the mean of the rows of X nearest it; a center no row is nearest
32⍝│ stays where it is. Repeat it with p_ower.
33⍝│ >> "ml:" u_se< "Learn"
34⍝│ >> X := 4 2 r_eshape 0.0 0.0 0.0 2.0 10.0 10.0 10.0 12.0
35⍝│ >> X ml:k_step 2 2 r_eshape 1.0 1.0 9.0 9.0
36⍝│  0.0  1.0
37⍝│ 10.0 11.0
38ˡk̲step ← { X C →
39  O ← (t̲ally C) ⁿⁿo̲neHot C ˡa̲ssign X
40  n ← ('+ r̲/₁ O) 'l̲eft t̲able o̲ffsets 2 s̲elect s̲hape X
41  (((o̲\ O) '+ '× i̲nner X) + C × f̲loat n = 0.0) ÷ 1.0 m̲ax n
42}
43
44⍝│ C i̲nertia X: the sum of each row's squared distance to its nearest center.
45ˡi̲nertia ← { C X → '+ r̲/ 'm̲in r̲/₂ X ʰd̲ist C }
46
47⍝│ k f̲arthest X: k starting centers, chosen without chance: the
48⍝│ first row, then each time the row farthest from the centers so far.
49ˡf̲arthest ← { k X →
50  d ← 2 s̲elect s̲hape X
51  (k − 1) '{ C → C c̲at₁ (1 c̲at d) r̲eshape (ⁿⁿa̲rgmax 'm̲in r̲/₂ X ʰd̲ist C) s̲elect X } p̲ower 1 t̲ake X
52}
53
54⍝│ (k, n) k̲means X: k centers after n steps from the farthest-first start.
55ˡk̲means ← { (k, n) X → n '{ C → X ˡk̲step C } p̲ower k ˡf̲arthest X }
56
57⍝━━ k nearest neighbors: a vote
58
59⍝│ (k, X, y) k̲nn Q: for each row of Q, the label most of its k
60⍝│ nearest rows of X have (y: X's labels, from 1); on a tie the
61⍝│ smallest label. The neighbors are found nearest first, each shifted
62⍝│ beyond the rest once taken (X_eTaL has no grade along a row yet); the
63⍝│ shift is finite, 1 + the largest distance, so it runs in 32-bit
64⍝│ floats too.
65⍝│ >> "ml:" u_se< "Learn"
66⍝│ >> X := 4 1 r_eshape 0.0 1.0 10.0 11.0
67⍝│ >> (3, X, 1 1 2 2) ml:k_nn 2 1 r_eshape 0.5 10.5
68⍝│ 1 2
69ˡk̲nn ← { (k, X, y) Q →
70  c ← 'm̲ax r̲/ y
71  D ← Q ʰd̲ist X
72  (_, V) ← k '{ (d, v) →
73    j ← ⁿⁿa̲rgmax n̲eg d
74    (d + (1.0 + 'm̲ax r̲/ r̲avel d) × f̲loat j '= t̲able r̲ange t̲ally X, v + c ⁿⁿo̲neHot j s̲elect y)
75  } p̲ower (D, ((t̲ally Q) c̲at c) r̲eshape 0.0)
76  ⁿⁿa̲rgmax V
77}
78
79⍝━━ PCA: the directions of most variance
80
81⍝│ n p̲ca X: the mean of X's rows, the first n principal directions
82⍝│ (a column each, unit length) and the variance along each: (mu, V,
83⍝│ ev). Power iteration on the covariance, each direction then taken
84⍝│ out of it (deflation); a direction's sign makes its items sum
85⍝│ positive.
86ˡp̲ca ← { n X →
87  d ← 2 s̲elect s̲hape X
88  mu ← ('+ r̲/₁ X) ÷ f̲loat t̲ally X
89  Z ← X − (s̲hape X) r̲eshape mu
90  S0 ← ((o̲\ Z) '+ '× i̲nner Z) ÷ f̲loat t̲ally X
91  u0 ← 1.0 + 0.1 × f̲loat o̲ffsets d
92  (_, V, ev, _) ← n '{ (S, V, ev, i) →
93    v ← 200 '{ u → w ← S '+ '× i̲nner u◆ w ÷ ('+ r̲/ w × w) ^ 0.5 } p̲ower u0
94    v1 ← v × 1.0 − 2.0 × f̲loat 0.0 > '+ r̲/ v
95    lam ← '+ r̲/ v1 × S '+ '× i̲nner v1
96    (S − lam × v1 '× t̲able v1, V + v1 '× t̲able f̲loat i = r̲ange n, ev + lam × f̲loat i = r̲ange n, i + 1)
97  } p̲ower (S0, (d c̲at n) r̲eshape 0.0, n r̲eshape 0.0, 1)
98  (mu, V, ev)
99}
100
101⍝│ (mu, V, ev) p̲roject X: each row of X in the principal directions: n columns.
102ˡp̲roject ← { (mu, V, _) X → (X − (s̲hape X) r̲eshape mu) '+ '× i̲nner V }
103
104⍝━━ Logistic regression: classes by a softmax
105
106⍝│ (n, lr) l̲ogistic (X, y): the weights of a softmax over X's
107⍝│ columns (a row per column, the bias the last row; one column per
108⍝│ label), after n steps of gradient descent on the cross-entropy at
109⍝│ rate lr, from zeros.
110ˡl̲ogistic ← { (n, lr) (X, y) →
111  Y ← ('m̲ax r̲/ y) ⁿⁿo̲neHot y
112  G ← o̲\ ʰo̲nes X
113  n '{ W → W − lr × (G '+ '× i̲nner (ⁿⁿs̲oftmax X ⁿⁿd̲ense W) − Y) ÷ f̲loat t̲ally X } p̲ower ((1 + 2 s̲elect s̲hape X) c̲at 2 s̲elect s̲hape Y) r̲eshape 0.0
114}
115
116⍝│ W p̲redict X: the label (from 1) the weights W give each row of X.
117ˡp̲redict ← { W X → ⁿⁿa̲rgmax ⁿⁿs̲oftmax X ⁿⁿd̲ense W }