Gradient flows¶
A gradient flow moves the points of a source cloud, step by step, along the gradient of a loss, until they cover the target. It is the simplest way to see what a loss "pulls" on, and the core of many registration and generative modelling methods.
A Sinkhorn flow¶
We start from a blob and flow it onto a ring.
import math
import torch
from remblais import SamplesLoss
device = "cuda"
torch.manual_seed(0)
N, M = 1_000, 1_000
x = 0.1 * torch.randn(N, 2, device=device) + 0.5
t = 2 * math.pi * torch.rand(M, device=device)
y = 0.5 + 0.3 * torch.stack([t.cos(), t.sin()], dim=1)
a = torch.full((N,), 1 / N, device=device)
b = torch.full((M,), 1 / M, device=device)
loss = SamplesLoss("sinkhorn", p=2, blur=0.01, scaling=0.9)
At each step, the gradient with respect to x is divided by the weights a:
-grad / a is then the displacement each point should follow, independently
of the number of points.
lr = 1.0
x.requires_grad_()
for step in range(20):
L = loss(a, x, b, y)
[g] = torch.autograd.grad(L, [x])
with torch.no_grad():
x -= lr * g / a[:, None]
if step % 5 == 0:
print(f"step {step:2d}: loss = {L.item():.5f}")
With p=2 and a small blur, a step of lr = 1 moves each point almost
straight to its target: the loss collapses in a handful of steps. Smaller
steps give a smoother trajectory.
Comparing losses¶
The same loop works with any loss of remblais. Kernel norms are cheaper per step, but their gradients do not point straight at the target: they need more steps, and a step size suited to the blur (a Gaussian kernel with a small blur has steep gradients). The Sinkhorn divergence moves every point along a nearly straight line.
def flow(loss, lr, steps=10):
z = (0.1 * torch.randn(N, 2, device=device) + 0.5).requires_grad_()
for _ in range(steps):
[g] = torch.autograd.grad(loss(a, z, b, y), [z])
with torch.no_grad():
z -= lr * g / a[:, None]
return SamplesLoss("sinkhorn", blur=0.01)(a, z.detach(), b, y).item()
print("sinkhorn", flow(SamplesLoss("sinkhorn", blur=0.01), lr=0.5))
print("energy ", flow(SamplesLoss("energy"), lr=0.5))
print("gaussian", flow(SamplesLoss("gaussian", blur=0.1), lr=0.05))
The printed number is the Sinkhorn divergence that remains between the flowed cloud and the ring, after 10 steps: lower is better. The Sinkhorn flow ends well below the two kernel flows.
Tips¶
- Use
scaling=0.9(or more) in a flow: the gradient of the Sinkhorn divergence is more accurate when the loop converges further. - For large clouds on a GPU,
backend="online"or"multiscale"(in 2D and 3D) keeps the memory linear in the number of points. - With an optimizer such as
torch.optim.SGD, remember that the raw gradient scales with the weights: either divide bya, as above, or rescale the learning rate by N.