librarylibs/Embed/src/Embed.xtl
Embed: word embeddings from counts: co-occurrence, PPMI, a fixed projection, cosine neighbors
Import it with an alias of your choice: "em:" u_se< "Embed". Put libs/Embed/src on XETAL_PATH ("just path"); the reference is libs/Embed/docs. Names with l: are exported; h: names are private to this file.
A corpus is a vector of word numbers (from 1), each sentence ended by a 0. A word's embedding is a row: which words occur near it, weighted by how much more often than chance (PPMI), then projected to fewer dimensions. Words used alike get rows that point alike.
Counting
ˡc̲ounts : Int -> Int -> Int
n c̲ounts k: how many times each of 1 .. n occurs in k, by sorting
(the keys in order, then the length of each run of equal keys).
"em:" u̲se< "Embed"
5 ᵉᵐc̲ounts 3 1 3 3 5 1 0 3 0 1
ˡc̲ounts ← { n k → s ← (g̲rade k) s̲elect k first ← 1 c̲at (1 d̲rop s) ≠ -1 d̲rop s at ← w̲here first runs ← ((1 d̲rop at) c̲at 1 + t̲ally s) − at ((first r̲eplicate s) i̲ndexOf r̲ange n) s̲elect runs c̲at 0 }
ˡc̲ooccur : (Int, Int) -> Int -> Int
(v, w) c̲ooccur ids: a v x v matrix of how often word i occurs
within w words of word j in the same sentence (both ways).
"em:" u̲se< "Embed"
(3, 1) ᵉᵐc̲ooccur 1 2 3 0 1 2 0 0 2 0 2 0 1 0 1 0
ˡc̲ooccur ← { (v, w) ids → sent ← '+ s̲\ ids = 0 pairs ← '{ d → a ← (n̲eg d) d̲rop ids b ← d d̲rop ids ok ← (((n̲eg d) d̲rop sent) = d d̲rop sent) ∧ (a > 0) ∧ b > 0 (ok r̲eplicate (v × a − 1) + b) c̲at ok r̲eplicate (v × b − 1) + a } m̲ap r̲ange w (v c̲at v) r̲eshape (v × v) ˡc̲ounts ˡˢr̲aze pairs }
Weighting and projecting
ˡp̲pmi : Num a => a -> Float
p̲pmi C: positive pointwise mutual information: the log of how
much more often each pair occurs than if the words were independent,
0 where less (or never; a word with no company has a row of 0s).
ˡp̲pmi ← { C → c ← f̲loat C r ← '+ r̲/₂ c 0.0 m̲ax l̲og 1e-300 m̲ax (c × '+ r̲/ r) ÷ 1e-300 m̲ax r '× t̲able r }
ˡp̲roject : Int -> Float -> Float
d p̲roject M: each row of M projected to d dimensions by a fixed
matrix of +1 and -1 over the square root of d (random indexing):
distances and angles between rows are roughly kept. The signs come
from a hash of each place, the same every run, no chance.
ˡp̲roject ← { d M → n ← 2 s̲elect s̲hape M h ← 43758.5453 × s̲in (12.9898 × f̲loat r̲ange n) '+ t̲able 78.233 × f̲loat r̲ange d M '+ '× i̲nner (1.0 − 2.0 × f̲loat (h − f̲loat f̲loor h) < 0.5) ÷ (f̲loat d) ^ 0.5 }
Neighbors
ˡu̲nit : Float -> Float
u̲nit E: each row scaled to length 1 (a row of 0s stays 0).
ˡu̲nit ← { E → len ← (1e-300 m̲ax '+ r̲/₂ E × E) ^ 0.5 E ÷ len 'l̲eft t̲able o̲ffsets 2 s̲elect s̲hape E }
ˡc̲osines : Float -> Int -> Float
E c̲osines i: the cosine of row i with every row of E.
ˡc̲osines ← { E i → (ˡu̲nit E) '+ '× i̲nner r̲avel i s̲elect ˡu̲nit E }
ˡn̲earest : (Float, Int) -> Int -> Int
(E, k) n̲earest i: the k rows of E most like row i (by cosine),
nearest first, row i itself left out.
"em:" u̲se< "Embed"
E ← 4 2 r̲eshape 1.0 0.0 0.9 0.1 0.0 1.0 0.7 0.7
(E, 2) ᵉᵐn̲earest 1 2 4
ˡn̲earest ← { (E, k) i → order ← g̲rade n̲eg E ˡc̲osines i k t̲ake (order ≠ i) r̲eplicate order }