Optimal Transport – Toán học của việc chuyển một đống cát sang một đống cát khác

21/08/2026 22 phút đọc mathematicsoptimal-transportwassersteinMachine Learningoptimization

Đặt vấn đề

Không có gì tự nhiên biến mất.

Một đống cát nằm bên trái sân không thể nhắm mắt một cái rồi bụp, xuất hiện thành một đống cát hình con vịt ở bên phải sân.

Muốn biến đống cát thứ nhất thành đống cát thứ hai, từng hạt cát phải đi đâu đó.

Có hạt đi 1 mét.

Có hạt đi 5 mét.

Có hạt xui xẻo bị xúc lên xe cút kít, chạy vòng qua cái cây, đi tận 20 mét chỉ vì người xúc cát hôm đó có một niềm tin kỳ lạ vào đường vòng.

Và mỗi mét di chuyển đều có giá.

Một kilogram cát đi 1 mét chắc chắn rẻ hơn một kilogram cát đi 100 mét.

Từ một câu hỏi nghe giống việc của công nhân công trường:

Phải chuyển cát như thế nào để tốn ít công nhất?

toán học sinh ra cả một lĩnh vực rất đẹp:

Optimal Transport – vận chuyển tối ưu.

Trực giác của Wasserstein Distance: khoảng cách giữa hai phân bố chính là lượng “công” tối thiểu cần bỏ ra để chuyển khối lượng của phân bố này thành phân bố kia.

Nghe thì có vẻ chỉ liên quan tới xe tải và đất đá.

Nhưng rồi người ta phát hiện ra một chuyện hơi ngáo:

ảnh cũng có thể xem như một đống vật chất.

xác suất cũng có thể xem như một đống vật chất.

embedding cũng có thể xem như một đám vật chất lơ lửng trong không gian nhiều chiều.

Và thế là bài toán chở đất thế kỷ XVIII bò thẳng vào Computer Vision, Machine Learning, Generative Model, NLP và Data Science.

Bài toán chính

Giả sử có hai làng.

Làng A có ba kho gạo:

Kho Lượng gạo
A1 30 tấn
A2 20 tấn
A3 50 tấn

Tổng cộng:

$$ 30 + 20 + 50 = 100 $$

tấn gạo.

Ở phía bên kia có ba cửa hàng cần nhận:

Cửa hàng Nhu cầu
B1 40 tấn
B2 10 tấn
B3 50 tấn

Cũng đúng 100 tấn.

Bây giờ vấn đề bắt đầu xuất hiện.

Kho A1 có thể chở gạo tới B1, B2 hoặc B3.

A2 cũng vậy.

A3 cũng vậy.

Nếu khoảng cách khác nhau thì giá vận chuyển cũng khác nhau.

Ví dụ:

$$ C = \begin{bmatrix} 1 & 4 & 7
2 & 3 & 5
6 & 4 & 1 \end{bmatrix} $$

Trong đó:

$$ C_{ij} $$

là chi phí vận chuyển một đơn vị hàng hóa từ kho $i$ đến cửa hàng $j$.

Chẳng hạn:

  • A1 → B1 có cost 1.
  • A1 → B3 có cost 7.
  • A3 → B3 chỉ có cost 1.

Nếu chúng ta ngu ngơ chở hết hàng từ A1 sang B3 trong khi B1 nằm ngay cạnh A1 thì toán học sẽ đứng bên đường nhìn chúng ta bằng ánh mắt khá thất vọng.

Mục tiêu của Optimal Transport là tìm:

Bao nhiêu hàng nên đi từ mỗi A sang mỗi B để toàn bộ nhu cầu được đáp ứng và tổng chi phí nhỏ nhất?

Từ đống cát đến phân bố xác suất

Đây là bước quan trọng nhất.

Ta tạm quên kho hàng.

Giả sử có một phân bố:

$$ \mu $$

và muốn biến nó thành:

$$ \nu $$

Ta có thể tưởng tượng $\mu$ là một đống cát màu vàng và $\nu$ là hình dạng mà chúng ta muốn đống cát đó trở thành.

Optimal Transport hỏi:

Từng phần khối lượng của $\mu$ nên được chuyển tới đâu trong $\nu$?

Nếu chuyển một lượng vật chất $m$ qua khoảng cách $d$, một cost rất tự nhiên là:

$$ cost = m \times d $$

Đưa 1 kg đi 10 mét có cost:

$$ 10 $$

Đưa 5 kg đi 10 mét:

$$ 50 $$

Không có ma thuật.

Không có teleport.

Chỉ có vật chất, khoảng cách và một hóa đơn vận chuyển đang âm thầm lớn lên.

Bài toán của Monge

Optimal Transport bắt đầu từ Gaspard Monge vào năm 1781.

Monge nghiên cứu một bài toán rất thực tế: di chuyển đất từ những nơi đang dư sang những nơi cần đắp đất sao cho tổng công sức nhỏ nhất.

Ta có một ánh xạ:

$$ T(x) $$

nghĩa là:

khối lượng nằm tại $x$ sẽ được đưa tới $T(x)$.

Bài toán Monge có dạng:

$$ \min_T \int c(x,T(x)),d\mu(x) $$

với điều kiện:

$$ T_{#}\mu = \nu $$

Ký hiệu trông hơi giống một con nhện bị rơi vào bàn phím, nhưng ý tưởng rất đơn giản.

Ta tìm một phép biến đổi $T$ sao cho:

  • toàn bộ phân bố ban đầu $\mu$ được biến thành $\nu$;
  • tổng chi phí di chuyển là nhỏ nhất.

Nếu:

$$ c(x,y)=|x-y| $$

thì chúng ta đang phạt theo khoảng cách.

Nếu:

$$ c(x,y)=|x-y|^2 $$

thì những chuyến đi xa bị phạt nặng hơn.

Nhưng bài toán của Monge có một hạn chế.

Một điểm $x$ chỉ được gửi tới một điểm $T(x)$.

Không được chia nhỏ.

Giống như có một xe tải chứa 10 tấn gạo nhưng luật kỳ quặc của vũ trụ nói:

Xe này chỉ được giao cho đúng một cửa hàng.

Trong thực tế, ta thường muốn 6 tấn đi cửa hàng A, 4 tấn đi cửa hàng B.

Và đó là lúc Kantorovich bước vào.

Kantorovich: thôi thì chia nhỏ đống cát đi

Leonid Kantorovich đưa ra một cách nhìn linh hoạt hơn.

Thay vì hỏi:

điểm $x$ phải đi tới đâu?

ta hỏi:

bao nhiêu vật chất từ $x$ nên đi tới mỗi $y$?

Ta sử dụng một transport plan:

$$ \gamma(x,y) $$

Nó mô tả lượng vật chất đi từ $x$ sang $y$.

Bài toán trở thành:

$$ \min_{\gamma} \int c(x,y)d\gamma(x,y) $$

với điều kiện hai marginal distribution của $\gamma$ phải bằng $\mu$ và $\nu$.

Nói bằng tiếng người:

  • không được tạo thêm cát;
  • không được làm cát biến mất;
  • cuối cùng phải tạo đúng đống cát mà ta muốn.

Đây chính là formulation được sử dụng rất nhiều trong Optimal Transport hiện đại. (Optimal Transport)

Optimal Transport dạng rời rạc

Trong Computer Science, chúng ta thường không có một đám mây xác suất liên tục đẹp như sách giáo khoa.

Ta có vector.

Giả sử:

$$ a = \begin{bmatrix} 0.5
0.5 \end{bmatrix} $$

và:

$$ b = \begin{bmatrix} 0.3
0.7 \end{bmatrix} $$

Ta cần tìm ma trận:

$$ P = \begin{bmatrix} P_{11} & P_{12}
P_{21} & P_{22} \end{bmatrix} $$

Trong đó:

$$ P_{ij} $$

là lượng mass được chuyển từ điểm $i$ của $a$ sang điểm $j$ của $b$.

Các hàng phải thỏa:

$$ P\mathbf{1}=a $$

và các cột phải thỏa:

$$ P^T\mathbf{1}=b $$

Nói cách khác:

khối lượng đi ra phải đúng bằng lượng đang có.

Khối lượng đi vào phải đúng bằng lượng cần nhận.

Bài toán là:

$$ \min_P \sum_{i,j}P_{ij}C_{ij} $$

hay viết gọn:

$$ \min_P \langle P,C\rangle $$

với:

$$ P_{ij}\ge 0 $$

Đây là một bài toán linear programming.

Nghe thì có vẻ đơn giản.

Và đúng.

Về mặt ý tưởng thì khá đơn giản.

Xong thuật toán, quá dễ.

Còn chuyện chạy nó trên vài triệu điểm dữ liệu thì toán học bắt đầu cười.

Một ví dụ nhỏ tới mức trẻ sáu tuổi cũng giải được

Giả sử có hai đống kẹo.

Ban đầu:

1A        B
2●●●      ●

Ta có:

$$ \mu=(3,1) $$

Nhưng muốn cuối cùng thành:

1A        B
2●        ●●●

tức:

$$ \nu=(1,3) $$

Ta phải chuyển:

$$ 2 $$

viên kẹo từ A sang B.

Giả sử A và B cách nhau 5 mét.

Chi phí:

$$ 2\times5=10 $$

Đó chính là trực giác của Optimal Transport.

Không hỏi hai vector khác nhau bao nhiêu.

Không chỉ nhìn:

$$ (3,1)-(1,3) $$

Mà hỏi:

phải thực sự di chuyển bao nhiêu vật chất, và đi bao xa, để biến cái này thành cái kia?

Đây là sự khác biệt rất quan trọng.

Wasserstein Distance

Từ Optimal Transport, ta có một họ khoảng cách nổi tiếng gọi là Wasserstein Distance.

Với $p\ge1$:

$$ W_p(\mu,\nu)

\left( \inf_{\gamma\in\Pi(\mu,\nu)} \int d(x,y)^p d\gamma(x,y) \right)^{1/p} $$

Đừng để công thức làm mình hoảng.

Nó chỉ đang nói:

  1. thử tất cả những cách hợp lệ để chuyển $\mu$ thành $\nu$;
  2. tính chi phí của từng cách;
  3. chọn cách rẻ nhất.

Với $p=1$:

$$ W_1 $$

có trực giác cực kỳ đẹp.

Nó gần với câu hỏi:

Cần bao nhiêu công để xúc đống đất này thành đống đất kia?

Vì vậy trong Computer Vision người ta còn gọi nó là:

Earth Mover’s Distance – khoảng cách của người xúc đất.

Vì sao không dùng Euclidean Distance cho khỏe?

Giả sử hai histogram:

1A:
2
30 0 0 1 0 0 0
4
5B:
6
70 0 0 0 1 0 0

Đỉnh của B chỉ dịch sang bên phải đúng một ô.

Về mặt hình học, hai phân bố rất giống nhau.

Chỉ cần bê toàn bộ mass đi một bước.

Optimal Transport hiểu điều đó.

Nhưng nếu dùng một số metric chỉ so sánh từng bin độc lập, chúng ta có thể mất thông tin rằng:

bin số 4 nằm ngay cạnh bin số 5.

Optimal Transport không chỉ nhìn bao nhiêu mass khác nhau.

Nó còn biết:

mass nằm ở đâu.

Đây chính là một trong những sức mạnh quan trọng của Wasserstein distance khi không gian nền có một metric có ý nghĩa. (Optimal Transport)

Một điểm khá kỳ quặc nhưng cực kỳ quan trọng

Giả sử có:

$$ \mu=\delta_0 $$

toàn bộ xác suất nằm tại 0.

Và:

$$ \nu=\delta_{100} $$

toàn bộ xác suất nằm tại 100.

Hai phân bố hoàn toàn không overlap.

Nếu chỉ nhìn phần giao nhau, chúng có vẻ xa nhau khủng khiếp theo một cách khá thiếu thông tin.

Nhưng Wasserstein nói rất rõ:

À, chỉ cần bê một đơn vị mass từ 0 tới 100.

Do đó:

$$ W_1(\delta_0,\delta_{100})=100 $$

Nếu target dịch từ 100 xuống 99:

$$ W_1(\delta_0,\delta_{99})=99 $$

Khoảng cách giảm một cách mượt mà.

Và tính chất tưởng như nhỏ này lại trở nên rất hữu ích trong Machine Learning.

Một phân bố thật sự là gì?

Đến đây có một cú lừa nhận thức khá thú vị.

Ta thường nghĩ distribution là một biểu đồ:

1      █
2    █ █
3  █ █ █
4█ █ █ █

Nhưng Optimal Transport không quan tâm đó có phải cát thật hay không.

Một distribution có thể là:

  • histogram màu của ảnh;
  • vị trí pixel;
  • phân bố từ trong một document;
  • một tập embedding;
  • một point cloud 3D;
  • tập tế bào trong dữ liệu sinh học;
  • xác suất mà một neural network sinh ra;
  • khách hàng phân bố trong không gian hành vi.

Chỉ cần ta định nghĩa được:

di chuyển từ điểm $i$ tới điểm $j$ tốn bao nhiêu?

thì Optimal Transport bắt đầu hoạt động.

Và đây mới là phần sâu nhất.

Optimal Transport thực ra không chỉ đo:

hai phân bố khác nhau bao nhiêu?

Nó hỏi một câu vật lý hơn:

cần bao nhiêu công để biến thế giới thứ nhất thành thế giới thứ hai?

Ví dụ: so sánh hai hình ảnh

Giả sử có một ảnh:

1⬛⬛⬛⬛⬛
2⬛⬛⬜⬛⬛
3⬛⬛⬛⬛⬛

và ảnh thứ hai:

1⬛⬛⬛⬛⬛
2⬛⬛⬛⬜⬛
3⬛⬛⬛⬛⬛

Chấm trắng chỉ dịch sang phải một pixel.

Nếu coi pixel trắng là mass:

1(x=2,y=1)

chuyển sang:

1(x=3,y=1)

thì transport cost chỉ bằng khoảng cách giữa hai pixel.

Optimal Transport hiểu:

Đây gần như cùng một thứ, chỉ bị dịch nhẹ.

Tư duy này từng khiến Earth Mover’s Distance trở thành một công cụ tự nhiên trong Computer Vision.

Ví dụ: hai document dùng từ hơi khác nhau

Giả sử document A:

1con mèo đang ngủ

Document B:

1con mèo đang nằm

Nếu chỉ dùng Bag-of-Words:

1ngủ != nằm

Hai từ khác nhau hoàn toàn.

Nhưng giả sử embedding của:

1ngủ

và:

1nằm

ở gần nhau.

Ta có thể định nghĩa:

$$ C_{ij}

|e_i-e_j| $$

trong đó $e_i$ và $e_j$ là embedding của hai từ.

Optimal Transport có thể chuyển một phần mass của từ ngủ sang từ nằm với cost nhỏ.

Đây chính là tinh thần đứng sau những phương pháp như Word Mover’s Distance.

Nó không hỏi:

hai document có bao nhiêu từ giống hệt nhau?

Mà hỏi:

cần di chuyển ý nghĩa của document này bao xa để biến thành document kia?

Một câu hỏi nghe hơi triết học.

Nhưng cuối cùng nó vẫn chỉ là một ma trận cost.

Vấn đề: Optimal Transport chính xác khá đắt

Giả sử mỗi phân bố có:

$$ n $$

điểm.

Transport plan chứa khoảng:

$$ n^2 $$

biến.

Nếu:

$$ n=1,000 $$

thì đã có:

$$ 1,000,000 $$

ô trong transport matrix.

Nếu:

$$ n=100,000 $$

thì về lý thuyết ma trận đầy đủ có:

$$ 10^{10} $$

ô.

Mười tỷ.

Lúc này chiếc xe tải chở cát tưởng tượng của chúng ta chưa kịp chạy thì RAM đã nằm xuống trước.

Optimal Transport cổ điển thường dẫn tới một bài toán linear programming và chi phí tính toán nhanh chóng trở thành trở ngại khi kích thước support lớn. Đây chính là một trong những động lực quan trọng dẫn tới các phương pháp OT xấp xỉ và regularized OT. (NeurIPS Papers)

Sinkhorn: cho đống cát một chút entropy

Năm 2013, Marco Cuturi giới thiệu một ý tưởng cực kỳ có ảnh hưởng trong Machine Learning:

thêm entropy regularization vào Optimal Transport. (NeurIPS Papers)

Thay vì giải:

$$ \min_P \langle P,C\rangle $$

ta giải gần dạng:

$$ \min_P \langle P,C\rangle

\varepsilon H(P) $$

trong đó:

$$ H(P)

-\sum_{i,j}P_{ij}\log P_{ij} $$

Entropy khuyến khích transport plan bớt cực đoan.

Nói theo kiểu đời thường:

Optimal Transport bình thường nói:

Hàng này tốt nhất đi đường này. Đi hết.

Entropy nói:

Bình tĩnh. Chia đều ra một chút cũng được.

Thoạt nhìn có vẻ chúng ta vừa phá bài toán.

Nhưng đổi lại, bài toán có cấu trúc cực kỳ thuận lợi.

Ta đặt:

$$ K_{ij}

e^{-C_{ij}/\varepsilon} $$

Transport plan có dạng:

$$ P = \mathrm{diag}(u) K \mathrm{diag}(v) $$

Và sau đó lặp:

$$ u

\frac{a}{Kv} $$

$$ v

\frac{b}{K^Tu} $$

Chỉ thế thôi.

Lặp qua lặp lại việc scale hàng và cột.

Đó là Sinkhorn iteration.

Nghe có vẻ đáng ngờ vì một bài toán linear programming to như con voi vừa biến thành vài phép nhân ma trận.

Nhưng đó chính là điều khiến entropic Optimal Transport trở nên đặc biệt hữu ích trong Machine Learning: phép tính có thể vectorize và chạy rất tốt trên GPU. Công trình của Cuturi cho thấy regularization này có thể làm việc tính OT nhanh hơn rất nhiều so với các solver transport cổ điển trong các thiết lập được thử nghiệm. (NeurIPS Papers)

Sinkhorn bằng Python

Một phiên bản cực kỳ tối giản:

 1import numpy as np
 2
 3def sinkhorn(a, b, C, epsilon=0.1, n_iter=100):
 4    K = np.exp(-C / epsilon)
 5
 6    u = np.ones_like(a)
 7    v = np.ones_like(b)
 8
 9    for _ in range(n_iter):
10        u = a / (K @ v)
11        v = b / (K.T @ u)
12
13    P = np.diag(u) @ K @ np.diag(v)
14
15    return P

Ví dụ:

 1a = np.array([0.5, 0.5])
 2b = np.array([0.3, 0.7])
 3
 4C = np.array([
 5    [0.0, 1.0],
 6    [1.0, 0.0]
 7])
 8
 9P = sinkhorn(a, b, C)
10
11print(P)

P[i, j] cho biết lượng mass được chuyển:

1i → j

Trong production chúng ta tất nhiên sẽ cần xử lý thêm:

  • numerical stability;
  • log-domain Sinkhorn;
  • convergence criterion;
  • batch processing;
  • GPU;
  • sparse structure;
  • lựa chọn $\varepsilon$.

Nhưng ý tưởng cốt lõi vẫn chỉ là vậy.

Một đống cát.

Một đống cát khác.

Một ma trận khoảng cách.

Rồi toán học ngồi tìm cách xúc.

Tham số epsilon thực sự làm gì?

Trong Sinkhorn ta có:

$$ \varepsilon $$

Nếu $\varepsilon$ nhỏ:

transport plan tiến gần hơn tới Optimal Transport không regularize.

Mass thường tập trung hơn.

Nhưng bài toán cũng khó tính số hơn.

Nếu $\varepsilon$ lớn:

transport plan mượt hơn.

Mass có thể được rải ra nhiều đường đi hơn.

Tính toán thường dễ hơn, nhưng kết quả lệch xa hơn khỏi OT gốc.

Có thể tưởng tượng $\varepsilon$ giống mức độ khó tính của ông quản lý vận tải.

Epsilon rất nhỏ

Ông nói:

Chỉ chọn những tuyến rẻ nhất. Không có tình cảm.

Epsilon lớn

Ông nói:

Tuyến này đắt thêm chút cũng được. Anh em chia hàng ra đi cho vui.

Trong thực tế đây là trade-off giữa:

  • độ chính xác với OT ban đầu;
  • numerical stability;
  • tốc độ hội tụ;
  • độ smooth.

Optimal Transport trong Machine Learning

Optimal Transport ngày nay xuất hiện ở rất nhiều nơi.

So sánh distribution

Đây là trường hợp trực tiếp nhất.

Cho:

$$ P_{data} $$

và:

$$ P_{model} $$

ta muốn đo chúng khác nhau bao nhiêu.

Thay vì chỉ hỏi hai density overlap bao nhiêu, Wasserstein Distance đo công cần thiết để biến distribution này thành distribution kia.

Generative Model

Wasserstein GAN là một ví dụ nổi tiếng về việc sử dụng hình học Wasserstein để xây dựng objective cho generative model.

Trực giác vẫn vậy.

Generator tạo ra một đám probability mass.

Data thật là một đám probability mass khác.

Training cố gắng kéo hai thế giới lại gần nhau.

Không phải bằng teleport.

Mà bằng khoảng cách của transport.

Domain adaptation

Giả sử dữ liệu train đến từ:

1camera A

nhưng production lại dùng:

1camera B

Feature distribution có thể lệch nhau.

Ta có:

$$ P_{source} $$

và:

$$ P_{target} $$

Optimal Transport có thể xây dựng coupling giữa chúng.

Hiểu đơn giản:

điểm nào trong thế giới source tương ứng gần nhất với điểm nào trong thế giới target?

Clustering và barycenter

Nếu trung bình hai số:

$$ 10 $$

và:

$$ 20 $$

ta được:

$$ 15 $$

Nhưng trung bình hai distribution thì sao?

Trong không gian Wasserstein, ta có khái niệm:

Wasserstein barycenter.

Ta tìm một distribution nằm “ở giữa” nhiều distribution khác theo geometry của transport.

Điều này hữu ích trong:

  • image processing;
  • statistics;
  • clustering;
  • shape analysis;
  • machine learning.

Differentiable sorting

Một thứ nghe khá bất ngờ:

sorting cũng có thể nhìn như một assignment problem.

Người ta đã dùng entropic Optimal Transport để tạo các approximation có khả năng differentiation cho ranking và sorting, từ đó đưa những thao tác vốn rời rạc này vào pipeline gradient-based. (NeurIPS Papers)

Optimal Transport cứ như một ông chú ban đầu chỉ nhận việc chở cát.

Rồi một ngày ta quay lại.

Ông đang:

1sort tensor trên GPU.

Không ai biết chuyện đã đi xa tới mức này từ lúc nào.

Optimal Transport đang đo khoảng cách giữa những thế giới

Có một cách nhìn mà mình khá thích.

Khoảng cách Euclid hỏi:

Điểm A cách điểm B bao xa?

Optimal Transport hỏi:

Cả thế giới A cần thay đổi bao nhiêu để trở thành thế giới B?

Một người đang đứng ở tọa độ:

$$ (1,2) $$

có thể dịch sang:

$$ (2,2) $$

Đó là geometry của điểm.

Nhưng một thành phố có:

  • hàng triệu người;
  • nhà cửa;
  • xe cộ;
  • hàng hóa;
  • dòng tiền;

muốn biến thành một thành phố khác thì không còn một điểm nào để đo nữa.

Ta cần nói về phân bố.

Và lúc đó geometry cũng phải trưởng thành theo.

Optimal Transport cung cấp một geometry cho probability distributions.

Đây là lý do khái niệm Wasserstein space lại sâu hơn rất nhiều so với câu chuyện xúc cát ban đầu.

Wasserstein space

Nếu mỗi distribution được xem như một “điểm”, ta có thể tạo một không gian mà:

1mỗi điểm = một distribution

và khoảng cách giữa hai điểm là:

$$ W_p(\mu,\nu) $$

Bỗng nhiên distribution có thể:

  • cách nhau;
  • di chuyển;
  • có đường đi;
  • có midpoint;
  • có barycenter.

Một distribution không còn là một biểu đồ chết nằm trên slide PowerPoint.

Nó trở thành một vật thể hình học.

Ta thậm chí có thể hỏi:

Con đường ngắn nhất từ distribution A tới distribution B là gì?

Với Wasserstein geometry, câu hỏi đó có ý nghĩa toán học.

Nếu A là một đám mây và B là một đám mây khác, ta có thể tưởng tượng từng hạt của đám mây đầu tiên trôi dần sang vị trí mới.

Không phải A biến mất rồi B xuất hiện.

Mà có một quá trình ở giữa.

Một lịch sử.

Một chuyển động.

Một con đường.

Một ví dụ cực nhỏ

Giả sử:

$$ \mu= \begin{bmatrix} 0.5
0.5 \end{bmatrix} $$

và:

$$ \nu= \begin{bmatrix} 1
0 \end{bmatrix} $$

Hai vị trí cách nhau:

$$ 10 $$

đơn vị.

Ban đầu:

1A       B
2
350%     50%

Cuối cùng:

1A       B
2
3100%     0%

Ta không phải di chuyển toàn bộ mass.

Chỉ cần chuyển:

$$ 0.5 $$

từ B sang A.

Do đó:

$$ W_1

0.5\times10

5 $$

Nếu khoảng cách tăng lên 100:

$$ W_1

0.5\times100

50 $$

Đây chính là linh hồn của Wasserstein Distance:

$$ \boxed{ \text{distance} \approx \text{mass moved} \times \text{distance moved} } $$

Trong bài toán tổng quát tất nhiên mọi thứ phức tạp hơn.

Nhưng nếu quên hết công thức của bài viết này, chỉ cần nhớ cái hộp trên là đủ.

Ưu điểm và hạn chế

Optimal Transport hấp dẫn vì nó đưa geometry của không gian dữ liệu vào việc so sánh distribution.

Một vài ưu điểm:

  • Có trực giác vật lý rất rõ.
  • Biết được các vị trí trong distribution gần hay xa nhau.
  • Có thể cho kết quả có ý nghĩa ngay cả khi hai distribution ít hoặc không overlap.
  • Transport plan cho ta không chỉ một con số distance mà còn một coupling giữa hai distribution.
  • Có nhiều ứng dụng trong Computer Vision, NLP, statistics và Machine Learning.

Nhưng không có bữa trưa miễn phí.

Các vấn đề thường gặp:

  • Exact Optimal Transport có thể rất đắt.
  • Cost matrix có thể cần $O(nm)$ bộ nhớ.
  • Kết quả phụ thuộc mạnh vào cách định nghĩa ground cost.
  • Trong không gian rất nhiều chiều, distance cũng có thể gặp vấn đề thống kê.
  • Entropic regularization như Sinkhorn chỉ là một phiên bản regularized, không hoàn toàn giống OT gốc.
  • Chọn $\varepsilon$ không hợp lý có thể làm transport plan quá mượt hoặc khó hội tụ.

Đặc biệt, câu hỏi:

Cost giữa hai điểm là gì?

không hề nhỏ.

Nếu ta định nghĩa cost ngu thì Optimal Transport sẽ rất ngoan ngoãn tối ưu một bài toán ngu cho chúng ta.

Máy tính không có nghĩa vụ cứu con người khỏi metric do chính con người nghĩ ra.

Một tư duy thú vị hơn về dữ liệu

Trong nhiều thuật toán truyền thống, dữ liệu được coi như những con số đứng yên.

Optimal Transport gợi ý một cách nghĩ khác.

Dữ liệu có thể là vật chất có thể di chuyển.

Probability không chỉ là một con số.

Nó là một lượng mass.

Một histogram không chỉ là một mảng:

1[0.1, 0.3, 0.4, 0.2]

Nó là bốn đống vật chất nằm tại bốn vị trí.

Muốn biến histogram này thành histogram khác, vật chất phải chảy.

Và ngay khi ta đặt câu hỏi:

nó phải chảy theo đường nào?

thì optimization xuất hiện.

Đặt thêm:

đường nào rẻ nhất?

Optimal Transport xuất hiện.

Đặt thêm:

khoảng cách tối thiểu đó có thể dùng làm metric không?

Wasserstein xuất hiện.

Đặt thêm:

nhưng giải linear programming chậm quá?

Sinkhorn xuất hiện.

Một chuỗi toán học dài hàng trăm năm đôi khi bắt đầu chỉ bằng một người đứng trước đống đất và nghĩ:

Có cách nào xúc cái này ít mệt hơn không?

Tổng kết

Optimal Transport giải một câu hỏi rất đơn giản:

Làm thế nào biến một phân bố thành một phân bố khác với tổng chi phí di chuyển thấp nhất?

Ý tưởng chính có thể tóm lại bằng:

$$ \text{Transport Cost}

\sum \text{mass} \times \text{distance} $$

Monge xem mỗi vị trí được chuyển tới một vị trí khác.

Kantorovich cho phép chia mass ra thành nhiều phần và mô tả việc vận chuyển bằng một transport plan.

Từ đó ta có Wasserstein Distance: một cách đo khoảng cách giữa các probability distribution dựa trên lượng công tối thiểu để biến distribution này thành distribution kia.

Và khi bài toán trở nên quá lớn, entropic regularization cùng Sinkhorn algorithm giúp tạo ra những phiên bản OT có khả năng tính toán hiệu quả hơn nhiều, mở đường cho hàng loạt ứng dụng trong Machine Learning. (NeurIPS Papers)

Nhưng phần mình thích nhất về Optimal Transport không nằm ở thuật toán.

Nó nằm ở cách nhìn.

Hai distribution không phải hai vật thể xa lạ phải đem ra so bằng một con số tùy tiện.

Ta có thể tưởng tượng một distribution chảy thành distribution kia.

Từng hạt probability rời vị trí cũ.

Băng qua không gian.

Trả một cái giá cho từng centimet toán học mà nó đi qua.

Và giữa vô số cách mà thế giới thứ nhất có thể biến thành thế giới thứ hai, Optimal Transport chỉ hỏi một câu:

Con đường nào ít tốn kém nhất?

Một câu hỏi về đống cát.

Nhưng cũng là một câu hỏi về geometry.

Về xác suất.

Về optimization.

Và, vì một lý do nào đó mà những nhà toán học thế kỷ XVIII chắc cũng chưa nghĩ ra, về những neural network đang chạy trên GPU hơn hai trăm năm sau.

Tham khảo

Số p-adic: Khi 1 và 1025 hóa ra lại đứng sát cạnh nhau
Octonion – Bát nguyên số: khi toán học bẻ gãy cả dấu ngoặc

Bình luận