In the paper Deep Networks with Large Output Spaces, Vijayanarasimhan et al. describe their approach to approximating the dot product between a neural network's output layer's parameter vector and input activations with winner-take-all hashing. I'm trying to grasp the main idea described in the following paragraph:
Our main idea is to approximate the dot product between the output layer’s parameter vector and the input activations using hashing. We first compute binary hash codes for the parameter vectors, $W$, of a layer’s output nodes and store the indices of the nodes in locations corresponding to the hash codes within hash tables. During inference, given an input activation vector, $x$, we compute the hash codes of the vector and retrieve the set of output nodes $O_k$ that are closest to the input vector in the hash space. Following this we compute the actual dot product between $x$ and the parameter vectors of $O_k$ and set all other values to zero.
I understand that only the most relevant vectors are being retrieved from the hash thus allowing less dot products. Yet the details are still unclear to me.
- Why are indices of nodes stored?
- Why are said indices stored in locations corresponding to the hash codes within hash tables?
- If the binary hash codes are first computed for the the parameter vectors $W$, why is the hash of the activation vector $x$ computed during inference? How do these relate?
- Given the previous step, a set of output nodes $O_k$ is retrieved. Aren't the relevant weight vectors in $W$ what should be retrieved?
Adding a reference to the paper which introduced the WTA hash The Power of Comparative Reasoning