10-605 · Randomized algorithms 2 · product quantization

Reconstructing a paper with product quantization

Each paper is a TF-IDF vector x over its title words and its authors. Product quantization splits x into m subvectors x(1),…,x(m) and encodes each one separately by its nearest match in a codebook. Here the codebook for subspace z is every paper in the dataset D, restricted to subspace z. So a query q is reconstructed as c = c(1)…c(m), stitched together from up to m different papers. Compare that with the best single paper in D.

 
 
 

Query q

PQ reconstruction c

Best single paper in D — the nearest whole x, i.e. m = 1

Subspace by subspace

zq(z): q's words in subspace znearest x(z) in D, and the paper it comes from‖q(z) − c(z)‖²

Over all queries in Q

random split into m subspaces title | authors split (m = 2)

Mean squared reconstruction error ‖q − c‖², the quantity PQ minimizes, over every query (hover a point for the mean cosine too). m = 1 is the best single paper. Each extra subspace lets the reconstruction borrow from one more paper, so it fits q better, but the code grows to m·⌈log₂|D|⌉ bits and there are |D|m possible reconstructions. Click a point to switch to that m.

Algorithm

Index:
  split the vocabulary into m sets S1,…,Sm         title words | authors, or at random
  for each paper x in D: x(z) = the entries of x for words in Sz
Encode q:
  for z = 1,…,m:
    jz = argminx in D ‖q(z) − x(z)‖²              the code is (j1,…,jm)
    c(z) = D[jz](z)
  c = c(1) … c(m)                            ‖q − c‖² = Σz ‖q(z) − c(z)‖²