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.

source · imports ls: work/libs/Lists/src/Lists.xtl

Counting

ˡc̲ounts : Int -> Int -> Int

function · line 21

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
}
Used in: ˡc̲ooccur

ˡc̲ooccur : (Int, Int) -> Int -> Int

function · line 36

(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
}
Used in: C, C

Weighting and projecting

ˡp̲pmi : Num a => a -> Float

function · line 52

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
}
Used in: P, P

ˡp̲roject : Int -> Float -> Float

function · line 62

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
}
Used in: E

Neighbors

ˡu̲nit : Float -> Float

function · line 71

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
}
Used in: ˡc̲osines, E

ˡc̲osines : Float -> Int -> Float

function · line 77

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 }
Used in: ˡn̲earest

ˡn̲earest : (Float, Int) -> Int -> Int

function · line 85

(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
}