Giới Thiệu Về Vận Chuyển Tối Ưu (Optimal Transport)

Vận chuyển tối ưu có nguồn gốc từ các công trình nghiên cứu của Monge và Kantorovich ở thế kỷ 18 và thế kỷ 20 và có một vị thế rất quan trọng trong Toán học (Các bạn có thể tham khảo thêm nguồn gốc và ứng dụng bên Toán học của vận chuyển tối ưu trong sách của Villani [1]. Trong thời đại dữ liệu lớn và trí tuệ nhân tạo, sự liên hệ chặt chẽ giữa tối ưu (optimization) và học máy, khoa học dữ liệu đã đem đến một diện mạo rất mới cho vận chuyển tối ưu bên các ứng dụng trong học máy và khoa học dữ liệu. Các ứng dụng này bao gồm mô hình sản sinh dữ liệu (generative model) mà nổi bật là Wasserstein GAN và Wasserstein Autoencoder, các bài toán học không giám sát (unsupervised learning) mà nổi bật là phân nhóm (clustering) và giảm chiều (dimension reduction), các bài toán học chuyển giao (transfer learning) mà nổi bật là thích ứng miền (domain adaptation), và các bài toán phân phối tính toán (distributed computing). Mình sẽ đi vào từng ứng dụng cụ thể của vận chuyển tối ưu vào các blog tiếp theo. Đồng thời, mình cũng minh họa một ứng dụng của vận chuyển tối ưu trong bài toán color transfer trong Hình 1.

Trong phần đầu tiên của blog này, chúng ta sẽ thảo luận về khái niệm của vận chuyển tối ưu và những đột phá quan trọng về mặt tính toán dẫn đến cuộc cách mạng trong việc sử dụng vận chuyển tối ưu trong học máy và khoa học dữ liệu.

Định nghĩa vận chuyển tối ưu:

Giả sử chúng ta có 2 phân phối xác suất $P$ và $Q$ trong không gian $\Omega$ là tập con của $\mathbb{R}^{d}$. Khi này, ta định nghĩa vận chuyển tối ưu giữa $P$ và $Q$ (theo công thức của Kantorovich) như sau:

\[\begin{align} \text{OT}(P, Q) = \inf_{\pi \in \Pi(P, Q)} \int c(x, y) d\pi(x, y), (1) \end{align}\]

mà tại đây $\Pi(P, Q)$ là tập hợp những phân phối xác suất chung $\pi$ giữa $P$ và $Q$, tức là, các phân phối cận biên (marginal distribution) của $\pi$ lần lượt là $P$ và $Q$. Đồng thời, $c(x, y)$ có thể hiểu là một cost không âm để đo lường sự khác biệt giữa 2 điểm $x$ và $y$. Chẳng hạn, chúng ta có thể sử dụng khoảng cách Euclidean $c(x, y) = |x - y|$ với mọi $x$ và $y$.

Lưu ý rằng ở đây chúng ta sẽ không đi sâu về mặt Toán học của khái niệm vận chuyển tối ưu ở phương trình (1), chẳng hạn như liệu có tồn tại phân phối xác suất chung $\pi$ để giảm thiểu (minimize) bài toán ở phương trình (1) hay trong trường hợp nào sự phân kỳ (divergence) OT(.,.) là một khoảng cách hợp lệ trên không gian xác suất. Chúng ta sẽ cố gắng giảm thiểu các công thức Toán học nhiều nhất có thể trong blog này. Trong trường hợp các bạn quan tâm sâu hơn về mặt Toán học của vận chuyển tối ưu thì có thể tham khảo trong sách của Villani mà mình có đề cập phía trên.

Vậy lý do vì sao mà vận chuyển tối ưu (1) lại có ý nghĩa quan trọng trong học máy và khoa học dữ liệu? Trên thực tế, các phân phối xác suất mà chúng ta có được $P$ hoặc $Q$ thường ở dạng rời rạc (discrete probability measures) vì các phân phối xác suất này được định nghĩa từ những data mà chúng ta có, vốn chỉ là hữu hạn. Có một tính chất quan trọng rằng khi một trong $P$ và $Q$ là rời rạc thì các khoảng cách thông dụng khác để đo lường sự khác biệt giữa $P$ và $Q$ như Kullback-Leibler divergence (KL), squared Hellinger distance, or Total Variation distance, đều không cho kết quả tốt. Một cách bất ngờ, vận chuyển tối ưu (1) vẫn đo lường hiệu quả sự khác biệt giữa $P$ và $Q$ trong trường hợp này. Đây cũng là vấn đề nền tảng dẫn đến những khái niệm như Wasserstein GAN và Wasserstein Autoencoder trong bài toán mô hình sản sinh dữ liệu mà chúng ta sẽ thảo luận thêm sau này.

Sự hiệu quả của vận chuyển tối ưu đối với các khoảng cách thông dụng khác trong mọi trường hợp của $P$ và $Q$ có thể coi là một lý do quan trọng dẫn đến việc nó bắt đầu được quan tâm trong khoa học dữ liệu và học máy. Tuy nhiên, một lý do cốt lõi dẫn đến sự cách mạng của việc sử dụng vận chuyển tối ưu lại đến từ những đột phá về mặt tính toán của vận chuyển tối ưu. Vậy những đột phá này là gì?

Độ phức tạp tính toán của vận chuyển tối ưu:

Như mình đã đề cập ở phía trên, trong thực tế chúng ta chỉ quan tâm trường hợp khi $P$ và $Q$ là rời rạc. Điều này cũng xuất phát nhiều về mặt tính toán do việc tính vận chuyển tối ưu giữa $P$ và $Q$ khi một trong $P$ và $Q$ là phân phối liên tục là một bài toán NP-hard. Vì vậy, giờ đây chúng ta chỉ quan tâm trường hợp tính toán khi $P$ và $Q$ đều rời rạc và có nhiều nhất là $n$ điểm hỗ trợ (support points) (Các bạn đọc có thể coi $n$ ở đây là số lượng dữ liệu mà chúng ta có). Để cho thuận tiện về mặt trình bày, chúng ta sẽ giả sử $P(X = x_{i}) = a_{i}$ và $Q(Y = y_{j}) = b_{j}$ với mọi $1 \leq i, j \leq n$. Điều này nghĩa là $x_{1}, \ldots, x_{n}$ là các điểm hỗ trợ của $P$ với mật độ (mass) lần lượt là $a_{1}, \ldots, a_{n}$. Tương tự vậy, $y_{1}, \ldots, y_{n}$ là các điểm hỗ trợ của $Q$ với mật độ (mass) lần lượt là $b_{1}, \ldots, b_{n}$.

Khi này, bài toán tính toán vận chuyển tối ưu giữa $P$ và $Q$ có thể viết lại được như sau:

\[\begin{align} & \inf_{\pi \in \mathbb{R}_{+}^{n \times n}} \sum_{i, j = 1}^{n} C_{ij} \pi_{ij}, \\ \label{eq:linear_program_OT} \text{sao cho} \ & \sum_{i = 1}^{n} \pi_{ij} = b_{j} \ \text{với mọi} \ j \in \{1, \ldots, n\}, (2) \\ \nonumber & \sum_{j = 1}^{n} \pi_{ij} = a_{i} \ \text{với mọi} \ i \in \{1, \ldots, n\}. \nonumber \end{align}\]

Bài toán tối ưu (2) về cơ bản là bài toán quy hoạch tuyến tính (linear programming) và có thể giải hiệu quả bằng interior point methods. Tuy nhiên, những thuật toán hiệu quả nhất cũng chỉ cho chúng ta độ phức tạp tính toán là $\mathcal{O}(n^3)$. Nếu chúng ta chỉ cần có $n = 1000$ thôi, thì các bạn có thể thấy rằng các phương pháp này cũng đã rất đắt đỏ về mặt tính toán. Lưu ý rằng trong các bài toán dữ liệu lớn, số lượng dữ liệu chúng ta có thường là vài trăm nghìn đến vài triệu dữ liệu; vì vậy, chúng ta phải có một cách tiếp cận khác để ước lượng vận chuyển tối ưu hiệu quả hơn.

Bài toán chính quy hóa entropy vận chuyển tối ưu (entropic regularized optimal transport):

Vào năm 2011, trong bài báo đột phá của mình, [2] đã đề xuất một phương pháp xấp xỉ cho vận chuyển tối ưu thông qua việc chính quy hóa (regularize) bài toán vận chuyển tối ưu (1) bằng entropy của kế hoạch vận chuyển $\pi$. Cụ thể hơn, chúng ta có bài toán sau đây:

\[\begin{align} & \inf_{\pi \in \mathbb{R}^{n \times n}} \sum_{i, j = 1}^{n} C_{ij} \pi_{ij} + \eta \sum_{i, j = 1}^{n} \pi_{ij} \log(\pi_{ij}), (3) \\ \text{sao cho} \ & \sum_{i = 1}^{n} \pi_{ij} = b_{j} \ \text{với mọi} \ j \in \{1, \ldots, n\}, \\ \nonumber & \sum_{j = 1}^{n} \pi_{ij} = a_{i} \ \text{với mọi} \ i \in \{1, \ldots, n\}. \nonumber \end{align}\]

ở đây $\eta > 0$ là tham số chính quy. Đồng thời, khi $\pi_{ij} \leq 0$, thì chúng ta quy ước rằng $\log(\pi_{ij}) = -\infty$. Chúng ta đặt tên bài toán này thành chính quy hóa entropy vận chuyển tối ưu (entropic regularized optimal transport). Việc chính quy hóa giúp bài toán mới (3) trở thành một bài toán lồi mạnh (strongly convex). Đồng thời, hàm đối ngẫu (dual function) của bài toán (3) là một bài toán tối ưu lồi không giới hạn (unconstrained convex optimization). Đây là một tiền đề dẫn đến nhiều thuật toán cực kỳ hiệu quả để xấp xỉ giá trị của vận chuyện tối ưu ban đầu và có độ phức tạp thuật toán gần mức tối ưu $\mathcal{O}(n^2)$, vốn tốt hơn rất nhiều so với độ phức tạp $\mathcal{O}(n^3)$ của bài toán vận chuyển tối ưu ban đầu. Sự cải thiện về mặt tính toán là lý do chính mà vận chuyển tối ưu trở thành 1 công cụ hiệu quả trong các ứng dụng hiện tại bên học máy và khoa học dữ liệu. Mình sẽ đi vào chi tiết một số các thuật toán này và độ phức tạp của nó trong blog tiếp theo.

Tài liệu tham khảo

[1] Cédric Villani. Optimal transport: Old and New. Springer, 2008.

[2] M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In NeurIPS, pages2292–2300, 2013

[3] K. Nguyen, Q. Nguyen, N. Ho, T. Pham, H. Bui, D. Phung, T. Le. BoMb-OT: On Batch of Mini-batches Optimal Transport. Arxiv preprint Arxiv: 2102.05912, 2021.

Top