10-605 / 10-805

Machine Learning from Large Datasets

Recap: the course so far

• Tool: Scalable computation on clusters
• MapReduce, Spark and iteration, Spark workflows
• Tool: Learning as optimization
• MLE for binomials, linear regression, logistic regression, k-means clustering
• Tools: exact solutions, gradient descent (batch, parallel, stochastic), EM and EM-like methods (for k-means)
• “Craft” of ML
• Tool: feature extraction / augmentation/ kernels
• Tool: regularization and sparsity hyperparameter tuning
• Tool: the hash trick and efficient SGD
• Tool: distributed ML – interaction with sparsity, AllReduce
• Tool: Randomized algorithms
• Bloom filter (a randomized set)
• Count-Min sketch (a randomized mapping x 🡪R+ )
• Today: locality sensitive hashing (LSH)

2

LOCALITY SENSITIVE HASHING (LSH)

LSH

• Bloom Filter and CountMin sketches
• weak signal (of x ∊ S, or a[x] ≥ c) is boosted by repetition
• Locality Sensitive Hashing (LSH)
• weak signal of similarity of two things
• SimHash: sign(r.dot(x1)) = sign(r.dot(x2)) for random projection r
• x1, x2 vectors
• MinHash: min(h(w): w∊S1) = min(h(w ): w∊S2) for a random hash h
• S1, S2 sets of tokens
• Start with LSH for SimHash (random projections)

​

​

LSH: key ideas

• Goal:
• map feature vector x to bit vector bx
• ensure that bx preserves “similarity”

​

Random Projections

Random projections

u

-u

2γ

Random projections

Consider two points.

​

If they are close their projections will probably be close

Random projections

Consider two points.

​

If they are distant their projections will probably be distant …

When will the projections be close?

​

Random projections

r can also make two distant points “close”

​

when do the signs agree?

​

Random projections

x1

x2

r

sign(r.dot(x1)) < 0

sign(r.dot(x2)) > 0

Random projections

x1

x2

r

sign(r.dot(x1)) > 0

sign(r.dot(x1)) > 0

Random projections

x1

x2

r

sign(r.dot(x1)) < 0

sign(r.dot(x2)) > 0

sign(r.dot(x1)) ! sign(r.dot(x2))

possible angles for 𝜃 of ⟂r

𝜃 ⩽ cos(x1,x2)

Random projections

x1

x2

r

sign(r.dot(x1)) > 0

sign(r.dot(x2)) < 0

sign(r.dot(x1)) != sign(r.dot(x2))

possible angles for ⟂r

cos(x1,x2)

… or rotate r by 180 degrees

LSH: key ideas

Pr[sign(r.dot(x1)) ≠ sign(r.dot(x2)] = cos(x1,x2)

SimHash(x) = sign(r.dot(x)) where r is random projection

LSH and SimHash

• Bloom Filter and CountMin sketches
• weak randomized signal (x ∊ S, or a[x] ≥ c) is boosted by repetition
• Locality Sensitive Hashing (LSH)
• weak signal of similarity of two points
• SimHash: sign(r.dot(x1)) = sign(r.dot(x2)) for random projection r

​

​

LSH: key ideas: SimHash

• Goal:
• map feature vector x to bit vector bx
• ensure that bx preserves “similarity”
• Basic idea: use random projections of x
• Repeat many times:
• Pick a random hyperplane r by picking random weights for each feature (say from a Gaussian)
• Compute the inner product of r with x
• Record if x is “close to” r (r.dot(x)>=0)
• the next bit in bx
• Theory says that if x’ and x have small cosine distance then bx and bx’ will have small Hamming distance

​

[Slides: Ben van Durme]

[Slides: Ben van Durme]

[Slides: Ben van Durme]

[Slides: Ben van Durme]

Hamming similarity for the bit vector approximates cosine similarity

“Collisions are your friend” – they indicate similarity

SimHash and MinHash

MinHash and Jaccard similarity

• Cosine is a useful similarity measure for vectors
• A useful similarity measure for sets is:

Jaccard(S, T) = |S ∩ T | / |S ∪ T|

​

S = {william, w, cohen, carnegie, mellon}

T = {william, cohen, carnegie, mellon, univ}

S ∩ T = {william, cohen, carnegie, mellon}

S ∪ T = {william, w, cohen, carnegie, mellon, univ}

Jaccard(S, T) = 4/6 = 0.667

​

MinHash and Jaccard similarity

• A useful similarity measure for sets:

Jaccard(S, T) = |S ∩ T | / |S ∪ T|

SimHash(x) = sign(r.dot(x)) where r is random projection

MinHash(S) = min(h(w) for w in S) where h is random hash

Claim: Pr(MinHash(S) = MinHash(T)) = Jaccard(S, T)

​

where probability is taken over random choice of h

Pr[sign(r.dot(x’)) ≠ sign(r.dot(x)] = cos(x,x’) where prob is over choice of r

MinHash(S) = MinHash(T) = h(‘carnegie’)

MinHash(S) = MinHash(T) 🡺 h_min ∊ (S ∩ T)

​

but h_min could be anything from (S ∪ T)

h(w) is an integer

h(w1), …., h(wn) for random h is a random permutation of tokens

S = {william, w, cohen, carnegie, mellon, univ}

T = {william, cohen, carnegie, mellon}

h(william)

h(w)

h(carnegie)

h(mellon)

h(univ)

h(cohen)

MinHash(S) = MinHash(T) = h(‘w’) ∊ (S ∪ T) but not (S ∩ T)

Claim: Pr(MinHash(S) = MinHash(T)) = Jaccard(S, T)

where probability is taken over random choice of h

MinHash and Jaccard similarity

A minhash signature for S is vector k_S=k₁,…,k_M

​

k_i= min(h_i(w) for w in S)

​

It approximates Jaccard similarity, like SimHash vectors approximate cosine similarity

The number of hashes M can smaller than |S|

The range of h_i can also be small: O(|S|)

LSH applications

• Compact storage of data
• size(x) ≫ size(bx)
• and we can still compute similarities
• LSH also can be used for fast approximate nearest neighbor!

From MinHash Signatures to Approximate Nearest Neighbors

MinHash LSH and approximate k-NN

• Goal: given q find all x with sim(q, x) > s₀
• We have M hashes in signatures k(x)

k_i(q) = min(h_i(w) for w in q)

• Can we use x’ for which k₁(x)=k₁(q) ?
• Very noisy, because this is a weak signal
• Can we use x for which k(x)=k(q) ?
• Maybe: these x’s should be similar to q
• But Pr(x’ is missed) = 1 - sim(q, x)^M
• … so we will miss many similar values

MinHash LSH and approximate k-NN

• Goal: given q find all x with sim(q, x) > s₀
• We have M hashes

k_i(q) = min(h_i(w) for w in q)

• Idea: group M=b*r hashes into b bands with r signals in each band
• Take x as a candidate neighbor if it matches q on all signals in any band.
• Pr(x is missed) = (1 – sim(q, x)^r )^b

MinHash LSH and approximate k-NN

• Goal: given q find all x with sim(q, x) > s₀
• We have M hashes

k_i(q) = min(h_i(w) for w in q)

• Pr(x is missed) = (1 – sim(q, x)^r )^b

sim(x,q)

MinHash LSH and approximate k-NN

• Goal: given q find all x with sim(q, x) > s₀
• We have M hashes

k_i(q) = min(h_i(w) for w in q)

• Ideas:
• replace k with concat(k, k’) where k’ is a random permutation of k
• now the signature is longer
• group into 2b*r hashes into 2b bands with r signals in each band
• more bands 🡺 more recall
• length-r bands are unlikely to be duplicated

​

More on Nearest Neighbors

SimHash LSH for k-NN search

• Problem: given a bit vector q find the closest bit vector, h, in a collection
• We could look at all buckets with Hamming distance 0, then 1, then 2, … but there are 2^k buckets of distance k
• Multi-index hashing for SimHash
• start out with a long code h
• break it into m equal-size bitstrings h⁽¹⁾, …, h^(m)
• claim: if HammingDist(h,g) > r, then for some z, HammingDist(h^(z),g ^(z)) > ceil(r/m)

​

• Example if m=4:
• h and g differ in 3 bits 🡺 at least one of the four “bands” has HammingDist(h^(z),g ^(z)) >= 1
• h and g differ in 7 bits 🡺 … >= 2

​

​

​

​

​

like bands

• Old: look at bands with Hamming distance 0 to g, then 1, … 🡺 2ⁿ
• New: look at bands w Hamming distance 0 to g^(z), then 1 … 🡺 m*2^n/m

​

• Fast in practice!

k-means for k-NN search

k-means and k-NN

1. Find centroid i closest to qx
2. Find element x in cluster i closest to qx

​

Not guaranteed to find the closest neighbor

You can make guarantees using the triangle inequality if you precompute distances between x and its centroid and check multiple centroids

J-means for k-NN search

• Does J-means help you find points close to qx?
• After you have learned the j clusters of n objects
• Find centroid i closest to qx
• O(J) distance computations
• Find element x in cluster i closest to qx
• O(N/J) distance computations
• Overall comparison
• if J=sqrt(N): O(J) + O(N/J) beats O(N)

​

• If this isn’t enough you can try running J-means internally in each cluster and so on
• Build a tree of depth d
• O(d J ) * O(N / J^d)

​

Vector quantization

• We can use the same data structure to either
• find approximate k-NN’s to qx
• map qx to a centroid that is similar
• centroid is an approximate encoding of the near neighbor x
• With a hierarchical clustering and millions of centroids this will be a good approximation of qx
• but it is compact to describe (as a path through the J-means tree)
• so J-means also compresses a set of vectors, like LSH

​

Product quantization for k-NN search

• Another trick:
• split x into m equal-size vectors x⁽¹⁾, …, x^(m)
• build a J-means indices for each of the m sets of subvectors
• to “encode” qx find closest centroids to qx⁽¹⁾, …, qx^(m)
• call them c⁽¹⁾, …, c^(m)
• call the concatenation c
• there are J^m possible c’s
• The larger space of encodings means PQ can be very accurate
• Theory says that the encoding loss is lower for qx,c pairs that are highly similar
• there are the important ones

​

​

​

​

​

like bands

Product quantization for k-NN search

A Recent Survey

2024

Extension/Application:�Online LSH and Pooling

46

47

2010

LSH algorithm

• Naïve algorithm:
• Initialization:
• For i=1 to outputBits:
• For each feature f:
• Draw r(f,i) ~ Normal(0,1)
• Given an instance x
• For i=1 to outputBits:

LSH[i] =

sum(x[f ]*r[i,f ] for f with non-zero weight in x) > 0 ? 1 : 0

• Return the bit-vector LSH

​

​

​

48

LSH algorithm

• But: storing the k classifiers is expensive in high dimensions
• For each of 256 bits, a dense vector of weights for every feature in the vocabulary
• Storing seeds and random number generators:
• Possible but somewhat fragile

​

49

LSH: “pooling” (van Durme)

• Alternative algorithm:
• Initialization:
• Create a pool:
• Pick a random seed s
• For i=1 to poolSize:
• Draw pool[i] ~ Normal(0,1)
• For i=1 to outputBits:
• Devise a random hash function hash(i,f):
• Given an instance x
• For i=1 to outputBits:

LSH[i] = sum(

x[f] * pool[hash(i, f ) % poolSize] for f in x) > 0 ?

1 : 0

• Return the bit-vector LSH

​

50

51

LSH: key ideas: pooling

• Advantages:
• with pooling, this is a compact re-encoding of the data
• you don’t need to store the r’s, just the pool
• no worries about saving/reusing the particular hash functions you used

​

​

52

Locality Sensitive Hashing (LSH) in an On-line Setting

53

Recap: using a Count-Min Sketch

x appears near y

Turney, 2002 used two seeds, “excellent” and “poor”

In general, SO(w) can be written in terms of logs of products of counters for w, with and without seeds

LSH: key ideas: online computation

• This SO trick is based on another common task: distributional clustering
• for a word w, v(w) is sparse vector of words that co-occur with w
• cluster the v(w)’s

​

​

55

…guards at Pentonville prison in North London discovered that an escape attempt…

​

An American Werewolf in London is to be remade by the son of the original director…

​

…UK pop up shop on Monmouth Street in London today and on Friday the brand…

​

v(London): Pentonville, prison, in, North, …. and, on Friday

​

LSH: key ideas: online computation

• Common task: distributional clustering
• for a word w, v(w) is sparse vector of words that co-occur with w
• cluster the v(w)’s – or here, compute similarities

​

​

56

is similar to:

is similar to:

is similar to:

LSH: key ideas: online computation

• Common task: distributional clustering
• for a word w, v(w) is sparse vector of words that co-occur with w
• cluster the v(w)’s

​

​

57

v(w) is very similar to a word embedding (eg, from word2vec or GloVE)

Levy, Omer, Yoav Goldberg, and Ido Dagan. "Improving distributional similarity with lessons learned from word embeddings." Transactions of the Association for Computational Linguistics 3 (2015): 211-225.

LSH: key ideas: online computation

• Construct LSH(v(w)) for each word w in the corpus
• stream through the corpus once
• use minimal amount of memory
• ideally no more than size of output

​

​

58

…guards at Pentonville prison in North London discovered that an escape attempt…

​

An American Werewolf in London is to be remade by the son of the original director…

​

…UK pop up shop on Monmouth Street in London today and on Friday the brand…

​

v(London): Pentonville, prison, in, North, …. and, on Friday

LSH(v(London)): 0101101010111011101

LSH(v(Monmouth)): 0111101000110010111

…

​

59

v is context vector; d is vocab size

r_i is i-th random projection

h_i(v) i-th bit of LSH encoding

because context vector is sum of mention contexts

threshold later on

60

j-th hash of f_i

weight of f_i in r_j

compress H[w][j] to bits

Comments

• Tricks in this paper
• saving calls to random() with pooling
• computing word distribution vectors incrementally
• and at each increment compress, via random projection, to d real numbers
• thresholding the random projections to a bit

Experiment

• Corpus: 700M+ tokens, 1.1M distinct bigrams
• For each, build a feature vector of words that co-occur near it, using on-line LSH
• Check results with 50,000 actual vectors

62

Experiment

63

64

16

32

64

128

256