• 阅读更多
• 0. 动机
  • ( ͡❛ ▿ ͡❛)堆沙子
  • ＼( ｀▽´)／堆雪人

阅读更多

• 从Wasserstein距离、对偶理论到WGAN｜苏剑林
• PhD.Herrmann的科普blog
• Williams教授的科普blog (He wrote a lot on PCA)
• Chizat教授的最优传输课程21Spring
• Villani的网站
• Github仓库Awesome Optimal Transport

PhD.泽楠的科普

• 庞加莱球
• 机器学习帖子

• modelai的blog 检索关键词Introduction to Optimal Transport insite:github.io或最优传输 insite:github.io

教材Computational Optimal Transport

0. 动机

( ͡❛ ▿ ͡❛)堆沙子

面朝大海，阳光猛烈，站在海滩上，你面对着刚用铲子堆好的一堆沙，乱七八糟的一坨，你想着该怎么把它给堆成你想要的城堡形状，同时你不想费太大力气————毕竟谁会想因为堆沙子而晒伤呢？

简单来说，你正在面临一场“最省力的沙雕挑战”：如何用最小的动作，最大限度地让沙堆变成你想要的模样。每一撮沙子的位置都非常重要。如果你把沙子推得太远，或者推错了地方，你就要花费更多的力气重新调整。

于是，你开始琢磨，如何用最少的推沙子动作，将第一堆沙子移动到正确的位置，让它最终变成你想要的形状。每次你用手或铲子推一小撮沙子，从一个位置移到另一个位置，都会耗费你一定的精力。而你的目标，就是找到那条最省力的路径，把所有的沙子都恰到好处地推到该去的地方。

＼( ｀▽´)／堆雪人

又是一年扫雪季，这次你又被抽中来扫雪（“今年高一扫，明年高二扫”），寒风刺骨，你又忘带了手套，你只想赶紧把这块的雪铲到对面…… 教学楼前铲起一堆雪，慢慢挪到对面，一扔，啊哈，一个小雪堆。

重复、机械的劳作，在这个过程中你忽然有了灵感，有没有一种方式，能让你用最少的推雪动作，就把这堆雪恰到好处地移动到正确的位置？

假设用概率测度\(\mu\)表示原始的雪堆，目标雪堆位置为概率测度\(\nu\)，测度定义在度量空间\(\mathcal{X}\)上，其中空间每个点代表雪堆上的一个位置，我们想找到一个映射\(T:\mathcal{X}\to\mathcal{X}\)，使得雪堆\(\mu\)变为（谁知道呢）雪人\(\nu\)所需的体力消耗最小。

更进一步地，定义一个运输成本函数\(c(x, y)\)，它表示将一小块雪从位置\(x\) 移动到位置\(y\) 所需的体力。我们的目标是最小化以下总运输成本：

\[\begin{equation} \min_{T} \int_{\mathcal{X}} c(x, T(x)) \, d\mu(x) \end{equation}\]

同时\(T\)必须满足雪的质量守恒，即\(T\)将雪堆\(\mu\)的质量都推移到了雪人\(\nu\)上。

另一个例子：物流系统

设有一个电子商务平台，其物流系统中存在 \(N\) 个仓库，每个仓库 \(x_n\) (\(n = 1, 2, \dots, N\)) 储存有 \(m_n\) 台电子书阅读器。同时，该平台有 \(M\) 个客户 \(y_k\) (\(k = 1, 2, \dots, M\)) 下单购买了 \(h_k\) 台电子书阅读器。仓库 \(x_n\) 与客户 \(y_k\) 之间的运输成本 \(c(x_n, y_k)\) 被定义为其距离的函数。

那么如何设定一种货物分配方式，能够使得从仓库到客户的总运输成本达到最小呢？我们尝试构造传输矩阵 \(\Gamma\)，其中 \(\Gamma_{nk}\) 表示从第 \(n\) 个仓库发运到第 \(k\) 个客户的电子书阅读器数量。

为了满足物流需求，该传输矩阵需要满足以下约束条件：

1. 库存约束：每个仓库发出的阅读器总数不能超过其库存，即 \(\sum_{k=1}^{M} \Gamma_{nk} = m_n, \quad \forall n = 1, 2, \dots, N\)

2. 需求约束：每个客户收到的阅读器总数必须满足其需求量，即 \(\sum_{n=1}^{N} \Gamma_{nk} = h_k, \quad \forall k = 1, 2, \dots, M\)

3. 非负性约束：每个元素 \(\Gamma_{nk}\) 均应为非负，即 \(\Gamma_{nk} \geq 0, \quad \forall n, k\)

形式化为目标为最小化总运输成本的线性规划问题：

\[\begin{equation*} \min_{\Gamma} \sum_{n=1}^{N} \sum_{k=1}^{M} c(x_n, y_k) \Gamma_{nk} \end{equation*}\]

在满足上述约束条件的前提下，求解最优传输矩阵 \(\Gamma\)。