Confusion on update rules of Ham about enjoy-hamburger HOT 1 CLOSED

Hi @emonhossainraihan ,

Thank you for expressing interest in our work! I appreciate your curiosity and would be happy to discuss the paper content further via email.

This is a differentiable form of K-means for solving Vector Quantization. The algorithm of VQ is not differentiable and not easy to execute in parallel. So we need to write it into the matrix form for running over GPUs. Actually, you could find various differentiable forms if you like.

Regarding the update rule for $C$, traditional K-means assigns the input token to the nearest base in the dictionary (minimizing distance or maximizing similarity), resulting in a one-hot r-by-1 vector. However, this operation is non-differentiable. As a solution, we replace the arg min of distance with a softmax of similarity. In high-dimensional spaces, cosine similarity often provides more meaningful information. The temperature parameter, T, serves as a constant to control the proximity between the differentiable solution and the exact one-hot solution.

As for the update rule for $D$, K-means typically averages all the tokens that belong to the same base to update it. In matrix language, we first compute the sum of all tokens belonging to each base ($XC^\top$). To find the average, we divide the sum by the number of tokens for each base. This can be achieved by calculating the sum of each column of the coefficient matrix $C$ ($C \in R^{r \times n}$) using ($C1_n$). The final step is to "normalize" the sum matrix by mapping the per-base token counting (r-by-1 vector) to a diagonal matrix and right-multiplying it with the base sum matrix $XC^\top$. (You do not need to do this matrix multiplication in code. But for clarity, we write it into the matrix form.) This process remains unchanged for the differentiable form.

Please feel free to reach out if you have you have further questions!

Best,
Zhengyang

from enjoy-hamburger.