Optimal Transport (OT) Algorithms in Python: Comprehensive Coverage from Theory to Application

Optimal Transport (OT) Algorithms in Python: Comprehensive Coverage from Theory to Application

The optimal transport algorithm is becoming a new cornerstone in the field of machine learning, from image matching to gene alignment.

In today’s artificial intelligence landscape, the theory of Optimal Transport (OT) is quietly sparking an algorithmic revolution. From image matching in computer vision to word embedding alignment in natural language processing, and to cell type matching in bioinformatics, optimal transport provides a powerful mathematical framework for accurately measuring and transforming the relationships between different data distributions.

Optimal Transport: Three Centuries of Mathematical Wisdom

The origins of the optimal transport problem can be traced back to the 18th century when French mathematician Gaspard Monge proposed the “optimal transportation problem.” The core question can be vividly described as: given two piles of sand (distributions), how can we move the first pile into the shape of the second pile at minimum cost?

Modern mathematics abstracts this problem as follows: for two probability distributions α and β, and a cost matrix M, optimal transport seeks a transport plan P that minimizes the total cost of transporting from α to β. This minimum cost is known as the Wasserstein distance (also known as the earth mover’s distance), which has become a powerful tool for measuring distribution differences.

Python OT Ecosystem: Comparison of Two Core Libraries

In the Python ecosystem, optimal transport algorithms are primarily supported by two libraries:

  • • POT (Python Optimal Transport): A lightweight library based on NumPy, supporting a rich implementation of OT algorithms.
  • • GeomLoss: Built on PyTorch, supporting GPU acceleration and automatic differentiation.

Table: Comparison of POT and GeomLoss Features

Feature POT GeomLoss
Computation Backend NumPy (CPU) PyTorch (GPU support)
Installation Complexity ★☆☆☆☆ (Simple) ★★☆☆☆ (Moderate)
Learning Curve Gentle Steeper
Main Advantages Comprehensive algorithms, lightweight GPU acceleration, integration with deep learning
Applicable Scenarios Small to medium-sized data, research Large-scale data, deep learning integration

Installation and Environment Configuration

Installing these two libraries requires only simple pip commands:

# Install POT
pip install pot

# Install GeomLoss (requires PyTorch environment)
pip install geomloss

Considering compatibility issues with NumPy 2.0, the latest version of POT has been adapted through build system modifications and testing system adaptations to ensure smooth operation within the scientific computing ecosystem.

Core Practice: Four Steps to Solve the Optimal Transport Problem

1. Construct the Cost Matrix

The cost matrix M defines the cost of moving points from one distribution to points in another distribution. It is typically calculated using Euclidean distance or cosine distance:

import numpy as np
import ot

# Generate sample data: 100 vectors of dimension 512
np.random.seed(42)
a = np.random.randn(100, 512)
b = np.random.randn(100, 512)

# Calculate the Euclidean distance cost matrix
M_euclidean = ot.dist(a, b, metric='euclidean')

# Calculate the cosine distance cost matrix
M_cosine = ot.dist(a, b, metric='cosine')

2. Define Probability Distributions

In practical applications, we usually only have sample data and do not know the true distributions. The most common assumption is a uniform distribution:

# Create uniform distributions for sample sets a and b
alpha = ot.unif(len(a))  # [0.01, 0.01, ..., 0.01] for 100 samples
beta = ot.unif(len(b))

3. Solve the Optimal Transport Plan

Choose an exact or approximate method based on the problem size:

# Exact method - suitable for small-scale problems (n < 1000)
P_exact = ot.emd(alpha, beta, M_euclidean)

# Sinkhorn approximate method - suitable for large-scale problems
entropy_reg = 0.1  # Regularization coefficient
P_approx = ot.sinkhorn(alpha, beta, M_euclidean, reg=entropy_reg)

4. Calculate the Wasserstein Distance

The Wasserstein distance is a core metric for measuring distribution differences:

# 1-Wasserstein distance (earth mover's distance)
w1 = ot.emd2(alpha, beta, M_euclidean)

# 2-Wasserstein distance
M_squared = M_euclidean ** 2  # Squared cost matrix
w2 = np.sqrt(ot.emd2(alpha, beta, M_squared))

Practical Case: Cross-Domain Image Style Transfer

One of the most astonishing applications of optimal transport in computer vision is unsupervised domain adaptation— allowing models trained in a source domain (like real photos) to adapt to a target domain (like cartoon images).

import matplotlib.pyplot as plt
from ot.datasets import get_1D_gauss

# Create two different distributions: Gaussian mixtures
n_samples = 100
source = get_1D_gauss(n_samples, m=0, s=1)  # mean 0, std 1
target = get_1D_gauss(n_samples, m=4, s=0.5)  # mean 4, std 0.5

# Calculate the cost matrix (1D data)
M = ot.dist(source.reshape(-1, 1), target.reshape(-1, 1))

# Calculate the transport plan
P = ot.emd(ot.unif(n_samples), ot.unif(n_samples), M)

# Visualize the transport results
plt.figure(figsize=(10, 5))
plt.subplot(1, 2, 1)
plt.scatter(source, [0] * n_samples, label='Source Distribution')
plt.scatter(target, [1] * n_samples, label='Target Distribution')
plt.title('Distribution Before Transport')

plt.subplot(1, 2, 2)
for i in range(n_samples):
    for j in range(n_samples):
        if P[i, j] > 0.01:  # Only show significant transport paths
            plt.plot([source[i], target[j]], [0, 1], 'gray', alpha=P[i, j] * 10)
plt.scatter(source, [0] * n_samples)
plt.scatter(target, [1] * n_samples)
plt.title('Optimal Transport Plan')
plt.tight_layout()

This code demonstrates how to optimally transport the probability mass from the source distribution to the target distribution, forming a “soft alignment” between the two. In practical image style transfer, this method can align feature spaces across different domains, significantly enhancing model performance in the target domain.

Industrial Applications: When OT Meets Deep Learning

The GeomLoss library integrates optimal transport deeply with PyTorch, supporting GPU acceleration and automatic differentiation, allowing it to be directly embedded into deep learning models:

import torch
import geomloss

# Create batch data: 32 samples, each with 100 points, 128 dimensions
a = torch.randn(32, 100, 128, requires_grad=True).cuda()
b = torch.randn(32, 100, 128).cuda()

# Define Sinkhorn loss function
loss_fn = geomloss.SamplesLoss(
    loss='sinkhorn', p=2,  # Use 2-Wasserstein distance
    blur=0.05,  # Regularization parameter
    scaling=0.9,  # Multi-scale acceleration parameter
    backend='tensorized'  # Use tensorized computation backend
)

# Calculate batch loss
loss = loss_fn(a, b)

# Backpropagation
loss.backward()

This design allows the optimal transport loss function to be seamlessly integrated into the neural network training process, providing the model with geometrically sensitive supervision signals.

Performance Optimization: Solutions for Large-Scale Problems

Faced with massive data, traditional OT algorithms encounter challenges of cubic time complexity. The POT library offers various optimization solutions:

1. Sparse Matrix Acceleration

# Only calculate nearest neighbor costs (reduce computation by 90%)
M_sparse = ot.dist(a, b, metric='euclidean', sparse=True, k=10)

2. Stochastic Gradient Descent

# Use stochastic SGD approximation
P_sgd = ot.stochastic.sgd_entropic_regularized(
    alpha, beta, M_euclidean, reg=0.1,
    learning_rate=0.01, num_iter=10000)

3. Multi-Scale Computation

# Hierarchical computation of transport plans
P_multiscale = ot.emd2(alpha, beta, M_euclidean, multiscale=True)

Combining these optimization techniques, POT can handle OT problems with millions of samples. Meanwhile, GeomLoss can further enhance computation speed by 10-100 times through GPU parallelization.

Cutting-Edge Application Scenarios

Single-Cell RNA Sequencing Analysis

In the biomedical field, OT algorithms are used to align single-cell data from different sources:

import scanpy as sc
import ot

# Load single-cell data from two batches
adata1 = sc.read("batch1.h5ad")
adata2 = sc.read("batch2.h5ad")

# Calculate the transport plan between gene expression distributions
M = ot.dist(adata1.X.T, adata2.X.T, metric='cosine')
transport_plan = ot.emd(ot.unif(adata1.shape[1]), ot.unif(adata2.shape[1]), M)

# Apply the transport plan to correct batch effects
corrected_data = np.dot(adata1.X, transport_plan)

This method effectively eliminates technical variations, revealing true biological differences.

Reinforcement Learning Reward Shaping

In reinforcement learning, OT can be used for reward function design, guiding agent behavior:

# State distribution alignment: guide the agent's state distribution to approach the target distribution
def ot_reward(current_states, target_states):
    M = ot.dist(current_states, target_states)
    return -ot.emd2(ot.unif(len(current_states)), ot.unif(len(target_states)), M)

3D Point Cloud Registration

In autonomous driving and robotics, OT algorithms can achieve efficient point cloud registration:

# Point clouds A and B are both (n, 3) arrays
def align_point_clouds(A, B):
    # Calculate point-to-point cost matrix
    M = ot.dist(A, B)

    # Calculate optimal transport
    P = ot.emd(ot.unif(len(A)), ot.unif(len(B)), M)

    # Calculate transformation matrix
    transformation = np.linalg.lstsq(A, P @ B, rcond=None)[0]
    return transformation

Challenges and Future Directions

Despite the strong potential of OT algorithms, they still face three major challenges:

  1. 1. Computational Complexity: Even with approximate algorithms, ultra-large-scale problems remain tricky.
  2. 2. Curse of Dimensionality: The issue of distance metrics failing in high-dimensional spaces.
  3. 3. Dynamic Transport: Continuous transport problems over time series.

Noteworthy solutions include:

  • • Neural Optimal Transport: Using neural networks to parameterize transport plans.
  • • Sliced Wasserstein Distance: Reducing dimensionality through random projections.
  • • Unbalanced OT: Relaxing the constraint of probability mass conservation.

With advancements in GPU hardware and the emergence of algorithmic innovations, optimal transport is transitioning from theoretical mathematics to industrial applications, becoming a core component in the AI toolbox.

Conclusion: The Practical Path of Optimal Transport

  1. 1. Start Small: Use the POT library to understand OT principles on small datasets.
  2. 2. Tailor to Fit: Choose appropriate distance metrics (Euclidean, cosine, etc.) based on data characteristics.
  3. 3. Scale Decisions: Use exact algorithms for data sizes < 1k, and Sinkhorn approximations for > 1k.
  4. 4. Hardware Acceleration: Migrate data over ten thousand to GeomLoss + GPU environments.
  5. 5. Domain Adaptation: Explore OT variants in specific domains (e.g., biologically constrained OT for gene sequences).

The theory of optimal transport connects probability theory, optimization methods, and geometric intuition, providing a unified framework for handling complex relationships between distributions. As the Python ecosystem continues to improve, this once esoteric mathematical theory is becoming a daily tool for data scientists to solve real-world problems.

On the protein structures predicted by AlphaFold, the optimal transport algorithm precisely aligns evolutionary distances; in autonomous driving systems, it integrates multi-sensor data; in medical AI models, it bridges the gap between different hospital data distributions—optimal transport is quietly reshaping the boundaries of AI.

Recommended Reading:

  • • ipytest, a powerful Python library!
  • • Cornice, a severely underrated Python library!
  • • mf2util, a lightweight and easy-to-use Python library!
  • • Gitbib, an efficient management Python library!

Leave a Comment