nips 2013
希望读完能知道sinkhorn怎么用到OT里的。
论文之外的补充知识来自https://vincentherrmann.github.io/blog/wasserstein/
Sinkhorn Knopp
Optimal Transport
EMD：earth mover’s distance。最简单易懂的最优传输例子，两个不一样的土堆，怎么才能在最小cost的情况下把其中一个移成另一个的样子。具体到数学知识里，离散的分布（类似histogram那种）更易于理解，如下图：
怎么用数学形式定义这个问题呢。先看这个式子：
1_d就是全为1的d维向量。简单的矩阵乘法可以看出，r和c也都是d维向量，r由P的每一行加和组成，c由P的每一列加和组成。于是我们可以定义这个场景：设d=3，有两个分布X和Y，其中的变量取[1, 2, 3]，分布分别为[0.1, 0.3, 0.6]=r和[0.4, 0.3, 0.3]=c，相当于有了U(r, c)。则会有很多d维P方阵可以得到这个U(r, c)，这个U(r, c)在OT问题里是有名字的，叫transport polytope。P里面的元素就是联合概率分布，即
。这个可能一时脑子会转不过来，其实也不难理解，比如上面提到的r=[0.1, 0.3, 0.6]，其中的0.1就是第一行求和，也就是X取所有可能值，Y取1时的概率，也就是p11+p12+p13。
然后作者又趁机扔了些别的定义。分别是entropy和KL散度，后文应该会用到。
在拥有联合概率分布后，引入cost矩阵M，M_ij就是把X分布i处的土挪到Y分布的j处。OT问题的定义的简单表现形式为：
<,>表示Frobenius inner product，对例子中的实矩阵就是相同位置元素相乘，相乘结果总体加和，在OT中就得到最终的cost。说得具体一些就是给定cost M，求r和c之间的最优传输距离。可能到这里有些晕，那个联合概率分布P是干什么的，为什么就开始做乘法了。思考一下，其实P中每个entry即p_ij代表的概率就是把X的i处的土堆挪到Y的j处的概率。每个概率与相应位置的cost相乘不就是需要在这个位置挪土消耗的最终cost嘛，个人感觉也可以看做把X分布i处的土挪了百分之多少，像下面这张图这样。也就是说，P是我们需要求得的，transport plan。
Sinkhorn Distances: Optimal Transport with Entropic Constraints
热身知识结束。回忆一下上文说到的entropy：
扔个别的论文里得出的前提条件：
，
这玩意我证不出来，无语。有机会再看出处文章。下面是根据上面的前提给出的一个凹集的定义，相当于给原来的transport polytope引入利用entropy相关推导出来的\alpha，给了个constraint：
于是给出了等了很久的sinkhorn distance的定义
这个定义有什么用呢：
也就是说这个sinkhorn distance就是我们要找的OT distance，只要这个\alpha足够大。接下来的问题就是如何求解这个距离，下面这张图重点在绿点，红点和蓝点，绿点是要求的精确结果，而加入\lambda的P就是接下来提出的算法可以求出来的东西。
Computing Regularized Transport with Sinkhorn’s Algorithm
看到这里就知道为什么叫sinkhorn了，因为求P是用的**Sinkhorn's fixed point iteration**，一个古早的针对矩阵的算法。暂且不论算法怎么运转的，先看又是怎么把问题套到这个算法上的。上面提到了sinkhorn distance的定义，下面说说怎么算它。用到了拉格朗日算子。<br /><br />到这里我已经yue了，于是跳过了所有理论部分直冲算法。<br /><br />算法很恶心，先看取N=1，也就是c就是一个向量的情况。<br /><br />是不是很sinkhorn-knopp！也就是说P_lambda能解，而且简简单单用sinkhorn就能解了，虽然中间乱七八糟证明我没有懂，但至少知道能怎么解决什么样的问题了，呜呜呜。
若有收获，就点个赞吧
0 人点赞
