Paper
Exploiting Transitivity for Learning Person Re-identification Models on a Budget
作者：Sourya Roy，其相关课题组自我介绍
Motivation
以下为个人解读的角度
- 如果对于一个大图来说它的最小图就是三个顶点构成的图。
- 对于一个三个顶点的小图，如果已知两个边的关系，并且这两个边的关系中至少有一个正样本的话，那么这个小图两两之间的关系就可识别。例如，图中若已知
与
为正样本，
为负样本，那么
- 但是如果一个三个顶点的小图，已知的两个边的关系都是负样本。那么这个小图的第三条边的关系就无法通过前面这两个边来推断了。例如，图中已知
也为负样本，那么
（下标表示摄像头，上标表示摄像头的下的第几个人。） - 也就是关系在特定条件下是可传播的，这可以大大减少打标工作量。
- 但是随便选一些子图是无法保证最大地利用图里面的可以传播关系的子图的信息。
- 因为
1.如果图中都是一个已知关系的封闭三角形小图，那么其实没什么关系好传播的了，所以需要选一些不封闭的子图——无三角形图（Triangle-free graph）；
2.而且在图的子图中，有两个关系都是负样本的这些概率太高了。这样的子图也是无法传播关系的。
（但是这一点本文没有很好的解决办法，只是在实验中提了一下。而且觉得作者的理念是，只要把正样本的关系都尽可能地传播了，那么剩下不能传播的关系其实很多都是负样本的关系，那如果其实拿去训练与测试的时候，影响也不大。
所以个人认为一个值得探讨的问题就是，如果你把能传播的关系都传播了，剩下的三角形两个边都是负样本的关系，我们直接把第三条边也传播为负样本的关系，这样对我们的训练与测试影响会多大呢？从人工的标注与测试的效果两个方面综合来说，这是不是一个trade-off的办法呢？） - 所以，作者认为找到一个较好的无三角形图（Triangle-free graph），可以传播关系，也可以帮助我们减少很多工作量，因为他可以传播关系。打标过程选择一个好的子图，是有潜力把关系传播到整个大图的。
TLNR
为了更好地传播关系，作者先把图片抽取特征计算两两之间的相似度，然后在此基础上提出两个办法：
- 贪婪的算法：把这些边排序，每次选择相似度最大的边，并且这些边不能组成一个三角形。这样取B条边进行人工打标，之后关系传播到整个大图。
-
算法(Max-Cut的思想)：由于对图的边一大刀切过去后，得到的是一个无三角形图，但是Max-Cut是NP-hard的，所以采用
-Max-Cut的办法。具体做法就是，先对top-B条边和所有顶点组成图，再采用图的
总之，作者认为为了更好地传播关系 一个无三角形子图+最大概率为正样本的边
一个无三角形子图+相似度最大的边
名词解释(可先跳过)
- 无三角形图（Triangle-free graph）：如果在无向图中，没有三个顶点能组成三角形，这样的图称为无三角形图。
- 最大割(Max-Cut)：把图中点分为两部分V1和V2，使得V1和V2之间的连边值最大。
算法介绍
- 贪婪算法（虽然作者把这个算法放在第二位介绍）
这里的B为人工打标的数量限制；这里的Extract-Max(Q)就是每次在图中去除相似度最高的边。第6步为每次都检查是否构成个无三角形图。
时间复杂度分析：第４步需要，第6步如果没设计一个好的结构来查询的话，需要
，那么总体需要
，但是设计一个好结构的话，总体可以降为
甚至
（排序时间，可以在循坏外面先排好）
-
首先，作者说这个想法来源于观察到如果对一个图切一刀，那么这一刀切过的边组成的图就便组成了一个无三角形图。这刚好是作者想要的，现在就是要这些边的权重和最大，即Max-Cut。然而Max-Cut是NP-hard，所以采用确定的算法。
同样，这里的B为人工打标的数量限制，然后先取top-B条相似度最高的组成一个图（那没有组成一个图的话，可能这条边就放弃重选？）。
之后对这个图用算法便取得又可以组成非三角形图，然后权重和又比较大的图。并且对于这个权重和较大，作者还给出简略证明这个权重和是比
最优最大的权重和要大的。具体请看论文。
时间复杂度分析：第2步排序时间为，第４步为
，总时间复杂度为
。
- 小结一下：以上两个算法都想要每条边的权重较大，是因为相似度比较大，是正样本的概率更大。所以从这个角度来讲，可能贪婪的算法虽然时间复杂度较高，但是应该效果更好。不过从后面的实验结果来看，其实二者的效果都差不多，侧面说明了什么问题呢？（个人思考中。。）
Experiments
- 对于实验的大图的每个点（即每个人）抽取29600维的LOMO特征。
LOMO(Local Maximal Occurrence Feature)为2015年提出的传统抽特征的方式。在光照(illumination)问题上采用了一个Retinex算子解决，对多角度(multi-viewpoint)的问题采用了滑窗口的方式水平抽取特征，之后对一个水平上的特征取响应度最大的，然后还针对多尺寸的问题，把图片缩小一定比例后同样进行上面的特征抽取。
- 对于实验的度量学习，即把特征映射到同一个更加容易区分的空间上，采用的是KISS的方法。
KISSME(Keep It Simple and Straight Metric)为2014年提出的，主要是让模型自动学习映射的参数。
- 对于实验的相似度度量，采用的是欧式距离。
Baseline方法就是取相似度top-B的边，人工打标，然后传播关系。
两个细节：
(1) 在选择无三角形图的时候，因为极有可能选择的两条边最后人工打标之后关系都是负，这样关系就不能传达到第三条边了。所以作者在选择的时候只是选择，实验中
为0.7。然后到最后把剩下的
的边全部加入。
所以其实选的的子图，只是一个不太严格的无三角形图。
(2) 百分比的计算公式，在实验中会提及，如下：
表示正样本，即同一个人。
数据集
WARD，RAiD，Market-1501。由于除了Market-1501外，其他数据集比较小，所以我们这里就只关注Market-1501的表现效果，其他数据集的实验效果读者请前往paper。
WARD：2012年发布。包括3个摄像头，训练加测试总共70个人，图片数总共4786张。
RAiD：2014年发布。包括４个摄像头，训练加测试总共43个人，图片数总共6920张。
Market-1501：2015年发布。包括6个摄像头，训练加测试总共1501个人，图片数总共32,668张。
- 实验效果
-
先重点关注由这样的标注方法，训练集的关系可以传播到什么程度。也就是标注量会自动增加多少实验。
Greedy即为贪婪的算法；即为上面的
重点关注最后一列，即Market数据集：
(1) 仔细一看，会发现Baseline打了8%的数据量然后关系传播，已经把正样本对数量“发掘”了79.2%(好厉害，不知道这样选择8%的打标量包括了多少正样本数量)，但是总体的关系却传的不是很全，35.9%。也就是Baseline的办法负样本的关系是比较难传播。为什么正样本传的比较厉害，负样本没怎么传？？值得思考一下
(2) 猜测是，只简单粗暴地去取分类器得到的相似度最高的那几项，那么这些边在人工打标后是正样本的概率都比较高。那么有比较多的三角形两条边都是正的？？还是说8%的打标量其实里面包括了较高的正样本比例呢？？
(3) 贪婪的算法和
(4) 从上面我们知道，作者的理念是尽可能的挖掘正样本对，也就是尽可能取相似度最大的边来人工打标后传播，而贪婪的理念正好满足无三角形图和正样本概率尽可能大这两个要求，所以从效果来看，其传播的方位也是最广的。在三个数据集上都取得了最好的效果。 作者还做了如果要几乎把所有的正样本关系都通过关系传播“挖掘”出来的话，需要打标的数据量。
(1) 对于Market数据集，需要20%的数据量。我们这里与上面进行对比，会发现从8%的打标量升到20%的打标量，正样本关系其实提升的并不是很大，2％，但是总体打标量会提高一些，
7%-10%。所以其实这个打标过程，可能超过一定阈值的话，就是一直在标注负样本的关系了。
(2) 这对大型数据集标注来说，算是一个福音。超过一定阈值，发现关系传播的不大的话，其实可以简单粗暴的把剩下的关系都标为负样本的关系吧～
- 作者还进行训练和测试实验。用打了一部分标签的训练集数据，经过关系传播后，然后拿去训练，之后的测试效果与带标签的原始训练集进行训练后的测试效果进行比较。(这样比较主要就是来证明这样打标，这样传播后的效果其实不会很差吧？)，如下图：
图a为采用8% labels的效果，主要看rank-1，发现本文提的两个算法的效果与Full set的效果差不多，33%。Baseline会差一些。
图b为采用3% labels的效果，rank-1差2％，Baseline差
3％。
图c为打标数量和效果的图。会发现是存在转折点和慢慢饱和区的，跟上面我们的理解类似。
疑惑：但是我们不知道作者对于那些传播后还不能确定的关系是怎么设定的呢？是直接把剩下的关系设为负样本，然后投入训练吗？
然后作者也比较了本文提出的两种算法的实际时间：
贪婪算法是比较慢的。
Conclusion
- 这篇文章主要就是提出的一个解决打标的问题，问题新颖的，很吸眼球。
- 那个label的自动增量的实验，感觉是全文的亮点和重点，作者只是在最后一页简单写了一下实验效果，感觉好像欠缺点什么，可能前面背景和符号介绍太多了。
- 最后的label的自动增量的效果很神奇，不知道能不能从数学上证明这件事情？
- 如果采用深度学习的分类器，这样的选择是不是会更好一些？
