论文题目: Stochastic Optimization of Sorting Networks via Continuous Relaxations
论文地址: https://openreview.net/forum?id=H1eSS3CcKX
论文发表于: ICLR 2019
论文所属单位: Stanford

论文大体内容：
本文主要提出了NeuralSort模型，通过引入松弛，对置换矩阵变换为单峰行随机矩阵来解决sorting问题，使之前不能end2end训练（不可微分）的模型也能进行梯度下降优化。

Motivation：
Sorting问题不可微分，引入松弛来克服这个问题。

Contribution：
①提出NeuralSort模型，克服不可end2end训练问题；
②应用NeuralSort模型到排列问题中（采用Plackett-Luce (PL) 分布）；
③该模型在3个任务中取得收益；

1. Sorting问题可以理解为去获取置换矩阵，其中置换矩阵的定义如下（行是样本，列是序，如第5个样本排名第6，那么P[5, 6] = 1，其它P[5, *] = 0），由于不是连续值，所以该问题不可微分/求导，不能进行end2end梯度下降优化。

2. 定义
s是input vector，如[9,1,5,2]；
z是一个排列index，如[1,4,2,3]；
Zn是n!个z，所有的排列可能；
P是置换矩阵；
z=sort(s)操作是获取s的排列z，也是本文想要创造的算子；

Deterministic Sort
3. Plackett-Luce (PL) 分布下计算某个序列表的概率采用链式乘法

4. 单峰行随机矩阵

5. 将sort算子松弛后，可以计算出最大的k个元素和，那么第k个元素值=sum(topK) - sum(top(K-1))。

证明过程

6. 根据上面的最大的k个元素和计算公式，可以推导得到置换矩阵各个位置的值如下，再通过tf.nn.softmax_cross_entropy_with_logits_v2()来计算loss。

证明过程

7. kNN的算法逻辑：
①距离一般使用欧式距离或者曼哈顿距离等；
②每个query node需要跟已有的所有节点进行计算距离，才能选出k个最近的节点来确定label；
③如果k取最大值，那么就是直接划分query node为最多数量的类别；
④可以用kd树优化计算速度；
kNN对于分类是次优的，因为需要设定k。而其实可以引入NN的方式来计算每个node的embedding，用于kNN计算，但问题是引入NN后无法做到end2end学习，采用本文提出的方法就可以克服这个问题。

Stochastic Sort
8. 相比Deterministic Sort，Stochastic Sort就是增加了随机采样的过程，主要是为了解决推断排列时含有的不确定性，比如含有隐含node的结构（不能直观得出排列）。
P.S. 实际代码里面是 s=s-log(-log(g)) 。

实验
9. 使用本文提出的NeuralSort进行了3个实验来验证有效性：
①手写数字的排序；
②手写数字的中位数识别；
③kNN的end2end版本；

10. Dataset
①large-MNIST dataset：通过对单个数字的拼接，形成多位数的数字；

11. Baseline
①The vanilla row-stochastic (RS) baseline：n个图像的embedding concat起来，输入到MLP中；
②The Sinkhorn and GumbelSinkhorn baselines：use the Sinkhorn operator to map the stacked CNN representations for the n objects into a doubly-stochastic matrix.

12. 实验结果
①手写数字的排序任务，n越大效果越差，相比baseline有明显收益；

 
②手写数字的中位数识别任务，MSE相比baseline领先一个数量级；

 
③kNN任务，不用kNN效果最好，用了kNN是end2end版本的最好；

 

参考资料
[1] kNN论文 https://www.jmlr.org/papers/volume10/weinberger09a/weinberger09a.pdf
[2] github代码 https://github.com/ermongroup/neuralsort

以上均为个人见解，因本人水平有限，如发现有所错漏，敬请指出，谢谢！