计算机视觉论文笔记五：Maximal Linear Embedding for Dimensionality Reduction

红太狼 2022-05-25 14:27 150阅读 0赞

版权论文作者所有，本笔记仅用作学术交流,主要是做个笔记。这篇论文写的很友好，很清楚，你脑子里出现了什么疑问，下一句就是答案。而且是工科思维，很多实现细节作者也会提到，整篇论文几乎就是有不能更详细注释的代码！！我的鸽，被校友的论文圈粉了。我也要向着这种方向思考，写作。

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 33, NO. 9, SEPTEMBER 2011

Ruiping Wang, Member, IEEE, Shiguang Shan, Member, IEEE, Xilin Chen, Senior Member, IEEE, Jie Chen, Member, IEEE, and Wen Gao, Fellow, IEEE

# abstract： #

本文做的是流型降维，看Introduction。共两步：

*  locally linear patch, Maximal Linear Patch (MLP) to maximize the local neighborhood in which linearity holds.
 *  MLPs aligned into a global coordinate space, which is achieved by applying MDS to some randomly selected landmarks.called Landmarks-based Global Alignment(LGA)

# Introduction： #

流型降维，在保持原有数据的一些相关性特征（比方说测地线距离，局部关系）的基础上降低维度。一张图：

![70][]

三维的图(b)特征点，可以看作是卷起来的白纸，然后你给他铺开，纸上彩色点的纸上距离没变，但是降低成2维得了。因为我看过相关资料。这些就够了，感兴趣：

https://www.zhihu.com/question/24015486

https://blog.csdn.net/bbbeoy/article/details/78002756

以下两个特点需要注意，LGA方法来实现第二步，测地线距离和全局特征都保存了下来，而且作者认为是全局最优，3提到了一个mapping function，后面会讲：

![70 1][]

# 3  第一步MLPs（最大线性包）的嵌入 #

##  ##

## 3.1  MLPs的生成 ##

很自然的想法，弧度大的不认为能压成一个平面，小的可以。

所以AB这条弧线集合可以不断的被分解成更小的集合。于是我们采用聚类。

![70 2][]

具体算法如下：

x是高维向量，最后要给他们不重不漏的分到P个集合里。原则就是集合内的测地线与欧氏距离之比大于某个阈值，该集合分裂成两个。

![70 3][]

R表示两个数据点之间的测地线距离与欧氏距离的比值。也就是集合内求个平均值。

![70 4][]

一开始只有一个包，然后排序，从最大包的开始审，称之为parent包。先扔出去两个包（伪代码中的3.1-3.2），于是该数据增加了左右两个包，然后只要parent包不空就一直扔。

空了再去取个最大的。算法写的很清楚。

再说这个阈值，经验来讲取平均值，可以看下取几个值，然后选择拐点处的，因为拐点之后就稳定了。

![70 5][]

另外文中提到一个边缘处的节点的聚类问题，就是图c的黑色节点，如果是平滑的，那么不知道如何分，所以用软分类：

![70 6][]

以上都是随便来一组点都可以做的，本质就是聚类。

## 3.2 建立局部线性模型 ##

之后开始PCA降维了。注意PCA的目的是使得数据方差最大，所以是数据相关的，也就是说，一个包有一个降维矩阵。

![70 7][]

那么也就是有P个Mi。但是每个降维主成分矩阵的低维d，应该保持一致。

![70 8][]

## 3.3   Landmarks-Based Global Alignment全局联合 ##

将MLPs联合起来成为全局的模型，需要找到能够代表MLPs的参数。用什么来表示MLPs。

对于每一个MLP，本论文建模用降维的公式(4)中的均值mean+一些在MLPs中的参数点，一共有多少个patch，就有多少套mean+参数点：

*  final embedding space learned by the MDS analysis of the sample means and some samples along the principal axes of the MLPs
 *  name these means and sampled points landmarks  
    
 *  we need only the mean and one sample along each principal axis:d + 1 landmarks  
    
 *  the training sample nearest to the mean, hereinafter we call it centroid, is used instead of the mean landmark.  
    
 *  the other landmarks need not be sampled along the principal axes. Instead, they can be randomly selected, if only their amount for each MLP is a little greater than d to ensure stability

以上都是理想状态，实际上实验不用这些东西，简而言之上面基本废话。这也是工科方法，有个理论，真正用的还是实现效果好的，实现方便的。不谈实现的理论都是耍流氓。

![70 9][]

是的你没看错，大牛们随机取了几个点。。。。不过由于我们事先PCA降维过，所以要用d维Z：

![70 10][]

然后还记得那个mean吗，不妨把他永远放在第一个位置，

![70 11][]

好了我已经把输入收拾好了，接下来就是MLPs联合称global的算法 。

[70]: /images/20220525/b38977e9baa841b39daf922e753f239d.png
[70 1]: /images/20220525/c7eafea8543c493fb335600846cd030d.png
[70 2]: /images/20220525/93f032cc864a449ab05a152f7834c6a0.png
[70 3]: /images/20220525/e753934555da4b6dba542f8903e24677.png
[70 4]: /images/20220525/40f172c6d2b044529e20158bbc5036a2.png
[70 5]: /images/20220525/5cbc4404eb8e4f80aec98356c3fbde9b.png
[70 6]: /images/20220525/df923b0d4a4644f596f89a6180267b6e.png
[70 7]: /images/20220525/44a7f78612d3464ebbf3adbb471acde7.png
[70 8]: /images/20220525/6b0d49b3e09447c59a47dffea7fa8489.png
[70 9]: /images/20220525/41cbcb4c1e2742758c8c32de34badf3d.png
[70 10]: /images/20220525/50856007229741eebeff300574eec45a.png
[70 11]: /images/20220525/70b227af2c134491820c13c66898e075.png