这是一篇TIP2012的论文，讲的是流形和流形之间的距离，并将其应用哎人脸识别上，其中每个集合包含同一个类别的图片，覆盖各种变体。
通过建模每张图片为一个流行，我们把两个流形之间的距离记作MMD。因为一个图像集合可能有三种level，point，subspace和manifold，我们系统的研究了这三个level，并公式化一个通用的多水平MMD框架。具体恶言，我们通过收集一系列线性模型，表达了一个manifold。MMD问题同时转化成每一对的subspace之间的距离的整合。我们随后研究了一些MMD整合配置。
注：variation 这个单词不知道怎么翻译，不是方差，不是偏差。暂且把它当成变异。
- point: individual sample
- subspace: linear model spanned by a few samples
- manifold：nonlinear low-dimensional embedding spanned by a large number of samples
如下图所示：
另外关于线性代数的一些解释：
https://www.zhihu.com/question/28461358
Introduction and Related works
识别分成两类：
- 模型相关的参数化方法和模型无关的非参数化方法。前者倾向于把每个图片表达成参数化的分布函数，然后度量两个分布的相似度，使用KLD。比如高斯分布或高斯混合模型。他们通常需要解决困难的参数估计问题，并且在训练和新颖的测试数据集具有弱统计相关性的情况下可能具有较大的性能波动。
- 而非参数化的方法会对数据的分布的假设降低要求，尝试更灵活的方式建模图像集合。在以前的工作中，这种基于单个样本匹配的方法很少关注整个集合的全局自然数据变化，因此对离群值的影响更加敏感，而且它们的计算成本非常高，因为每当比较两个图像时都需要计算所有成对样本距离。
一个有利的趋势是使用子空间学习技术来全局建模集合数据的可变性。 这些方法尝试通过线性子空间或非线性流形表示图像集，然后进行设置 通过比较基于不同相似性度量的子空间或流形进行分类。
非参数方法可以大致分为两类：- 一组专注于如何定义集合相似性度量，这种方法，具有代表性的样本称作‘exemplars’。从图像集合中提取，作为局部模型。计算这些exemplars的相似度作为集合匹配。还有用主角作为两个线性子空间的相似度方法。为了捕捉数据的非线性，有人提出了一个主角的核版本。
- 另一组则更多地关注学习具有区分度的分类器，对于给定的相似函数。有人学习一个线性的可区分都的空间，致力于增大主角之间的分离。为了进一步定位复杂的数据分布，有人提出了一个提取局部的可区分的信息，使用局部线性模型表达。和主角类似，格拉斯曼距离作为subspace的距离进一步可区分都的学习。为了解决数据的非线性，使用格拉斯曼距离的核版本。
总之，两类方法分别是模型相关的参数化方法和模型独立的非参数方法，它们都有自己的优点，并且适用于不同的情况。 前者试图估计局限于数据的低维子空间的潜在密度分布，而后者通常旨在直接学习子空间。如果训练和测试数据共享相似的统计属性，则参数方法有望产生更好的结果。 对于更一般的集合分类任务，由于收集条件的不同，训练和测试阶段的模式可能会发生显着变化。 在这种情况下，非参数子空间学习方法更合适，因为它们在可能的数据变化空间上施加了统一的先验。 在实际应用中，应根据特定任务确定两种方法之间的选择。
在非参数方面，已经证明，在（仅）变化的照明条件下获取的面部图像集，本质上是一个低维的线性子空间。 而且，虽然涉及其他数据变化（例如姿势和表情），但该集合中的人脸图像将表现出明显的非线性。 因此，重要的是使用足够灵活的图像集表示来处理非线性。 假设每个集合中的图像位于非线性流形上，则可以基于一些相似性度量将FRIS任务转换为匹配不同流形的问题。 据我们所知，关于流形的一般相似性或距离度量的话题以前在文献中还没有得到足够的重视。 正是这一点激励了本文的工作。
概述
基于流形的局部线性特性，我们将流形表示为局部线性模型的集合，每个局部线性模型由一个子空间表示。 然后将MMD转换为每对子空间之间的局部距离的整合，该局部距离分别来自两个涉及的流形之一。与以前的版本相比，本文进行了三个主要扩展。
- 首先，以更有效，更灵活的方式改进了从流形构建局部线性模型的方法。
- 其次，我们提供了有关定义MMD的不同可能性的更详细的比较和讨论。
- 第三，进行了更广泛的实验以评估该方法并与其他最新算法进行比较。
关于点和子空间的距离已经在文献中进行了很好的研究。 而关于流形的距离的研究很少。
Distances Over Point and Subspace
定义点xi,yi, 子空间 Si, 流形 Mi.
Point to Point Distance（PPD）
最常用就是欧式距离：
Point to Subspace Distance (PSD)
通常是 L2-Hausdorff 距离：
事实上，x‘是x在S上的投影，同时也是x在S上最邻近的点，这通常被成为“Distance form feature space”
Subspace to Subspace Distance （SSD）
并没有统一的定义，最常用的还是主角分析，另外还有利用两个subspace中的DFFS之和。
众所周知，单个点xi扩张成一个特殊的线性子空间，也就说是tricial zero subspace L{0}，中心点在xi，0维度，在这种意义下，PPD和PSD都算是SSD的一种特殊情况。
Distances Over Manifold
我们的主要动机是由于局部线性在全局非线性流形上的任何地方都成立。因此，流形可以通过一系列的局部线性模型来建模，每一个线性模型均是为subspace。通常，流形可以看作是扩展的子空间，以解决更一般和复杂的数据变化。与流形相关的距离就是这些子空间上定义的距离。
形式上，我们表示一个流形M，Ci为第i个子空间，所有Ci的集合组成M：
其中m是局部线性子空间的数量。
Point to Manifold Distance (PMD)
找到M中最接近x的点，如下所示：
x”可以称作是x在流形上的投影。
Subspace to Manifold Distance (SMD）
可以通过在流形M中寻找最接近S的子空间来定义：
Manifold to Manifold Distance (MMD)
MMD转换为分别从其中一个涉及的流形对子空间对之间的距离进行求和：
d是加权项。可以认为是一种注意力。
已经证明这一点是子空间的特殊情况。 同样，在（3）中的公式下，子空间可以看作是流形的一种特例。 因此，三个模式级别形成一个层次结构，并且所有六个距离都可以在通用的多级别MMD框架中制定。
MANIFOLD–MANIFOLD DISTANCE （MMD）
从图3和公式6中，我们可以发现存在三个组成成分，MMD。
- local linear model construction
也就是说组成子空间 Ci Cj‘ - local model distance measure
the SSD d（Ci， Cj’） - global integration of local distance
权重fij的选择
local linear model construction
以前的局部方法需要很多先验，另外线性属性不会明确有用。
我们首先提出MLP maximal linear patch。流形上的MLP被定义为一个局部的线性patch，其中非线性度通过欧氏距离和测地线距离的偏差确定。为了构造MLP， 论文导出了一种单次顺序聚类方法，该方法只能产生预先指定的非线性度的MLP，并且可能会遇到集群不平衡的问题。 在本文中，我们进一步结合了MLP和层次聚类方法的优点。 由于在大多数情况下，聚类数量远小于数据样本的数量，因此在这里我们探索更有效的自上而下的分层划分聚类（HDC），而不是先前工作中使用的自下而上的HAC方式。由于簇（即MLP）的品质是根据非线性度来衡量，因此我们将丛集方法称为线性约束HDC（L-HDC）。
首先，通过k-NN图计算De和Dg距离，然很得到距离比：
这些矩阵全都是N N的。因为测地线距离不会小于欧氏距离，因此R>1恒成立。另一个矩阵H，大小k N，其中每一列H（：，j）表示数据点xj的最邻近k个点的索引。需要注意的是，作为计算De和Dg中时产生的副产品，H不需要额外的计算量。为了表示MLP的非线性都，我们定义下列的非线性分数函数：
L-HDC最终公式化为算法1：
基本过程时：
- 在第一个leve，所有样本全都作为一个簇
- 然后，对每个新的level。parent level的有着最大的非线性自由度的MLP会被分成两个更小的自由度。
- 最后，我们呢可以活得多个level的MLP，具有不同的自由度。
需要注意的时，step3的与之，控制着算法的结束，即最终的簇的数目m和他们的非线性自由度。一个大的与之暗示着较少的累但是较大的线性偏差，反之亦然。很明显，当阈值低于1时，可以生成完整的簇层级，因为β肯定大于1. 可以看到算法中的大多数步骤已经提前计算好了，尽管它包含一些迭代步数，但是仍然很有效。稍后会有详细的时间复杂度分析。
图4给出一组实例：
我们可以发现，samples和exemplar之间的偏差很小，只有线性偏差。因此，这个exemplar是靠谱的。
提取出来的簇随后通过线性子空间表达，最终得到local model是。使用PCA，对于每个举个Ci，我们定义exemplar为ei，对应的主成分主句Pi，特征向量的钱di个，然后组成一组正交的基。其中，di表示PCA子空间的维度。因为子空间是通过一组样本span的。ei和pi扮演者不同的角色来联合表达局部模型：前者表示数据样本本身，后者表示数据偏差。
Local Model Distance Measure
一旦建议好local model，我们可以使用SSD来度量他们的距离。直观上，合理和完整的SSD应该考虑主成分pi和exemplarei。如图5所示，
ei表示子空间的坐标（在全局数据空间），Pi表示子空间数据扩张的方向。然而，最常用的SSD，主角，只考虑了Pi因此仅仅反应了偏差模型的不同。我们把这种距离称为 “variation based measure”。相反，一些模型仅仅使用ei来计算局部模型距离，我们将这种方法成为 “exemplar based measure”. 很明显，这两种距离不够全面，为了协同合作这两个信息，有人做一个比较，使用correlation矩阵而不是covariance矩阵执行PCA。然而这个机制使得生成的subspace是mean和variance的混合版本，而不是我们文章中清晰的独立的。首先，回顾一下principal angels和以前的SSD定义，然后我们给出自己定义的SSD，完全由主角退出，无缝fuse variation和exemplar。
Principal Angles
记作两个子空间s1 s2，记作对应的exemplars为e1 e2，同时正交基P1和P2，其中d1和d2是特征空间的维度。两个子空间的主角0 < θ1 < θ2 < … < θr <=pi/2定义为子空间的任意两个向量的最小夹角：
其中r=min（d1，d2）在公式9中，u和v被称作第k个匹配的规范向量，第一项约束保证归一化，第二项是约束，保证每个子空间的规范向量正交。直观上，第一个匹配的规范向量对应着两个线性子空间的偏差最相似的模式。最大主角越小，表明两个子空间越小。
为了计算主角，一个稳定的算法，使用SVD，在这个方法中，P1P2通过SVD计算：
A为奇异构成的对角矩阵，Q1 Q2是两个正交的矩阵，奇异值是主角的余弦值，也就是规范向量关系
其中成对的规范向量是：
这样把P1 P2通过正交变换对齐，得到主轴U V
Previous Work on SSD
基于主轴，问多的SSD的方法比如MSM，仅仅使用最小的主轴角用来定义子空间的最大化关系：
相反，还有一个距离称作最小关系，使用最大的主轴角：
上述两个距离都告诉依赖主轴的分布，只有当特殊的情况下才算有效。还有另外的一个距离叫投影矩阵度量，使用所有的主轴角：
投影度量满足度量公里，还展示了上述两个距离的中间特征。
Proposed SSD Definition
14式子提供了一个合理的变化距离度量。为了推导一个更好的SSD，把样本的均值和变异都考虑在内，我们需要定义一个exemplar，然后结合投影度量。一个可能的选择可能是经典的PPD，但是不能直接结合1中的欧氏距离和14中的投影度量，因为他们呢来自不同的形式。因此，我们使用相关关系度量。如图5所示，两个exemplar e1和e2的相互关系是他们夹角的余弦值：定义exemplar距离：
使用14和15两个距离，我们可以复用相似的方式，得到一个SSD的正式定义：
因为不同的子空间对可能有着不同的主角，因此加上1/r用于归一化。当比较两种图像集合，这两种度量相辅相成。最后作者放出图6表明这种方法不仅仅是理论上有效，实验结果还很好。
Global Integration of local distance
现在，我们考虑MMD的最后组成，也就是说，选择公式6中的合适的dij。这有点像many-to-many的匹配问题。为了匹配两个集合是相同的类别，最有效的解决办法是找到相同的视角然后度量他们的相似度吗，而不是匹配两个流形的匹配的local model，不匹配的邻居对应该更需要关注。
给定两个流形：
我们首先定义治时期函数：
这里，N表示M2中的局部模型的最邻近索引，让母后我们可以获得所有局部模型对的集合A
A1和A2可能包含一些公共元素，尽管NN关系是非对称矩阵。为了标记简单，我们记作这些公共元素不同。因此A的基总是m+n。基于上述定义，如图7所示：
我们定义了几种：
Min NN
为了匹配两块流形的公共部分，一个简单但是直观的方法是测量他们最好匹配的local models，如图7a所示，这意味着需要计算集合A中的最小距离对：
然而这种方法可能不够稳定，同时很容易收到异常点的干扰，比如噪声。
Mean NN
为了结合更多的信息，一种简单的整合方法是简单的计算整体的距离，然后求平均。
然而，这种没有考虑全局的数据分布。更具体的吗，如图7b所示，当数据有较大的方差时，全都考虑显然不合理。
Mean NN‘s NN（N^4）
一个更直接的直觉是，一堆的距离越小，它的权重应该更大，这使得我们更关注更近距离的对。如图7c所示。
具体而言，略麻烦，还是看它举的例子吧：对于局部模型C1，它的NN和N4分别是C2’和C2.因此，（c1，c2‘）对儿的权重，如图红色虚线部分，将会被迁移到最邻近的对(红色实线部分)。我么可以看到，这个方法结合了上两种方法，因此，可以更加稳定，从事对于不同的NN对能自适应的调整权重，更加可靠。
Earth Mover’s Disatance
第四种方式是使用EMD，很多场合表现优异。两个流形M1 M2被表达两组，其中wc1 wc2分别表示簇的权重。wc/wc’被用来作为整个供应商的供应M1，消费者的能力是M2。使用归一化的值1/m 1/n. M1 M2之间的EMD距离为：
其中SSD dij=d（Ci Cj）称为地面距离，f冒号为最优流，通过以下的线性规划解决：
前两项约束保证供应商的运输能力，第二项是M2不能接收更多。第三项约束保证供应的流向是从M1到M2，不能反向。最后一项约束是total flow。
f帽子可以解释为两个流形之间的最佳批评日。因为有supply和consumption平和约束，EMD匹配会不可避免的放置一些权重在这些非NN local model对。如图7D所示。同样的问题适应到其他的EMD权重，例如单元权重。
Comparisons of the Four Options
以上四个方法中，第一个和第三个方法都比较强调NN对，在这种情况下，当Local model只有1个时，MMD变成了SMD。
对于计算复杂度，方法4时最好是的，假设两个流形的local model相同，则计算复杂度为：
相反，其他俩的时间复杂度为
除了上述四个方法外，还有其他的可选择的方法，比如，采取Max NN的方法，然后就变成了减少又名的Hausdorff问题，然而对人脸来说，上述四个方法更合适。
留言