kernel methods

Artur Chakhvadze (@norpadon) · 8h: This trivial thing is probably one of the most important memes in all of machine learning btw All of the kernel methods are based on this simple trick > QUOTED: John Carmack (@ID_AA_Carmack) · 8h > I'm a little disappointed with myself that the high school algebra identity didn't occur to me right away. > > [Embedded LLM chat screenshot:] > User: In pytorch, I have a [batch,latent] tensor and a [history,latent] tensor, and I want to get the squared distances between each batch element and every history element. I currently do this by: > ```python > delta = all_keys.unsqueeze(0) - q.unsqueeze(1) > distances = torch.sum(delta**2, dim=-1) > ``` > But this instantiates an enormous tensor with the broadcasts. I can break it up into smaller batches with a loop, but is there any more direct way that avoids instantiating the intermediate tensor? > > [Assistant, "Thought for 28s"]: Yes — use the algebraic identity for squared Euclidean distance: > ||q_i - k_j||² = ||q_i||² + ||k_j||² - 2 q_i·k_j > > This lets you compute the full [batch, history] distance matrix with only a single matrix multiply ([batch, latent] @ [latent, history]) plus two cheap norm vectors. No [batch, history, latent] intermediate tensor is ever materialized. > ```python > q_norms = q.pow(2).sum(dim=-1, keepdim=True) # [batch, 1] > k_norms = all_keys.pow(2).sum(dim=-1).unsqueeze(0) # [1, history] > # or equivalently: > # k_norms = all_keys.pow(2).sum(dim=-1, keepdim=True).T > cross_terms = q @ all_keys.T # [batch, history] > distances = q_norms + k_norms - 2 * cross_terms # [batch, history] > ``` > This is much more memory-efficient (the only large temporary is the [batch, history] result itself) and is the standard trick used in nearest-neighbor / retrieval code.