笔者自己的理解，无监督学习是挖掘数据自身的分布，找出一种低维的具有代表性或者某种性质的子空间（流形）。SOM是一种加约束的k-means，既可以看做是寻找具有代表性的特征点，也可以看做是寻找具有代表性的二维流形曲面。PCA是非常经典的最小化投影误差的子空间，也可以看做最大化投影方差的子空间。NMF则是基于假设最大化似然的同时，限制基向量非负。FA也是寻找某种子空间，目的是得到uncorrelated的基向量，并用变换矩阵近似实际观测值中的相关性。ICA同样是寻找子空间，但进一步要求基向量independent（此假设强于uncorrelated），不能用于高斯分布的数据，使得基向量不能随意旋转。MDS则是直接寻找保距的低维子空间，即子空间投影之间的距离尽可能与原空间相同。ISOMAP以及Local MDS是MDS的局部版本，旨在更好的保留数据的流形分布。
其中SOM是聚类算法，只能找到离散的特征点来近似数据分布；PCA、NMF、MDS、ISOMAP、Local MDS等则是寻找一个低维流形空间近似数据分布；FA以及ICA不仅可以得到线性子空间，而且还可以基于假设得到数据分布的概率密度。

---

Self-Organizing Map (SOM)

参考资料：https://youtu.be/w1XMiZg1m8Y

SOM可以看做是k-means的约束版本，即不同于k-means所有特征点之间毫无关联，SOM的特征点位于某个假象的方格上面，各个特征点之间基于方格上的距离存在不同程度的关联。
SOM的具体算法是先假象有一个方格（q1×q2），其中q1,q2任意指定，其选择决定了SOM的特征点数，共用q1∗q2个特征点（每个方格的交叉点）。每个特征点均位于观测的数据空间中Rp，有一个特征值。故不同于k-means只有一个位于观测空间Rp的特征值，SOM的特征点同时位于方格空间Rq1×q2中，存在一个方格空间坐标。特征点的方格坐标在学习的过程中是不变的，而特征值Rp在学习过程中不断改变，更加接近数据分布。方格坐标是SOM为特征点之间加入约束的方式，每次根据数据点更新特征值的时候，不仅仅更新特征值离数据点最近的特征点的特征值，而且同时更新在方格中与最近特征点较近的特征点的特征值。每次仅仅处理一个数据点，重复多次之后，得到的SOM中q1∗q2个特征点的特征值即表示了数据的空间分布，也可以将每个数据点分配给特征值离其最近的特征点，进行聚类分析。
基于不同的距离度量，更新时各个特征点的权重赋予，以及每次处理的数据点的多少 可以构造不同的SOM算法。每种算法都保证了SOM的保距性质，即观测空间中相近的数据点投影到方格空间中相近的特征点。

最简单的方法如下：

根据距离赋予特征点更新权重的方法如下：

batch版本如下：

Principle Component Analysis (PCA)

主成分分析法非常常见常用，以至于Ng认为它被过度滥用了。有很多种对PCA结论的解释，这里仅阐述两种：最小化投影误差，以及最大化投影方差。

首先，常见的数据预处理步骤包括数据平移（减均值），以及缩放（除以方差）。故以下分析中存在多解的情况，均以方便以上假设成立的情况下进行求解。

PCA寻找的是低维线性子空间，故存在一组正交基Vp×q，VTV=Iq，其中p为观测空间维度，q为子空间维度，有q<p。在未白化的数据中进行PCA，则是寻找一个平移过后的子空间，设平移向量为μ，即该向量集合中包括所有的{μ+Vb,∀b}。

任意向量x∈Rp在该空间中的投影为VVT(x−μ)+μ∈Rp。首先我们讨论最小化投影误差的情况：e=x−(VVT(x−μ)+μ)=(Ip−VVT)(x−μ) ，我们希望最小化训练集中的平方投影误差

对μ求导有μ=x¯

构造Xp×n使得X的第i列Xi=xi−x¯，从而

即最小化投影误差等价于最大化投影方差：令p=VVT(x−μ)+μ∈Rp，Ep=VVT(Ex−μ)+μ，Var(p)=E(p−Ep)T(p−Ep)=E[(x−x¯)TVVT(x−x¯)]，训练集的方差和为

进而最大化上诉公式，同时满足约束VTV=Iq，有

从而argmaxvar等价于求取XXT的特征向量，vj为前q个最大特征值对应的特征向量（这里使用了XXT对称矩阵的性质）。也可以理解为每次选取剩余误差空间中的方差最大方向作为基向量。

实际使用中不需要求取XXT=Σ的特征向量，仅需要对XT进行SVD分解，XTp×n=Un×pDp×pVTp×p，UTU=Ip且VTV=Ip。选取V中的前q列即可。

Principle Curve and Surface

参考资料：https://web.stanford.edu/~hastie/Papers/Principal_Curves.pdf

原论文中称Principal curves are smooth one-dimensional curves that pass through the middle of a p-dimensional data set, providing a nonlinear summary of the data. They are nonparametric, and their shape is suggested by the data。 笔者并不是很理解这个principle的存在，但是大概理解principle curve是对数据的总结，其形状和位置的信息量较大。

具体的定义如下：Principle Curve是观测空间Rp中的一条单维曲线，有f(λ)∈Rp，其中λ为标量，因为曲线是单维的。原论文中赋予λ的意义为f(λ)距离原点的弧长(arc-length)，同时指定f(λ)为平滑的，而这两个假设仅参与算法设计，并不限制principle curve的定义。对于指定曲线f(λ)，定义观测空间中任意一点x∈Rp的投影为λf(x)，为曲线上距离x最近的点，也称λ is responsible for x。因为曲线上的点由λ唯一指定，故求取的是投影的λ。当观测空间中的一条单维曲线f(λ)满足f(λ)=E(X|λf(X)=λ)，则称该曲线f(λ)为principle curve。即λ responsible for的所有点的均值等于f(λ)。

不考虑smooth限制，principle curve可以有无数条，这里仅考虑平滑的情况。我们采用迭代法求取principle curve，算法如下：

第一步先更改f^，使得曲线满足principle curve的定义；第二部更改λ^，即改变每个数据点的投影位置。初始值通常设为principle component，然后不断迭代求取。

而Principle Surface则是去求一个观测空间Rp中的二维曲面f(λ1,λ2)，定义十分类似，有(λ1(x),λ2(x))=λf(x)为任意数据点的投影。principle surface 为满足f(λ)=E(X|λf(X)=λ)的二维平滑曲面。高维曲面难以可视化，故罕见多于二维的Principle Surface。

Principle Surface与SOM得出的结果很类似，在使用特定平滑核函数的情况下Principle Surface和SOM的算法相同。Principle Surface为每个数据点求取一个投影点λ，而SOM则多个数据点共用一个特征点；Principle Surface是连续的，SOM是离散的。故两者在SOM特征点较多的情况下更相近。

Non-negative Matrix Factorization (NMF)

非负矩阵分解求取Xn×p=Wn×rHr×p，并限制X,W,H≥0。假设xij为均值等于[WH]ij的泊松分布即

通过满足W,H≥0限制条件下的最大似然求取W,H，没有简易解。通过类似于EM算法的方式构造辅助函数G(W,H,W′,H′)≤L(W,H)且G(W,H,W,H)=L(W,H)，即不断最大化Wt+1,Ht+1=argmaxW′,H′G(Wt,Ht,W′,H′)来最大化L(W,H)。

迭代算法如下：

限制非负的目的是为了更好的得到可解释性，但此分解仍然存在基向量任意旋转的问题，即WH=(WR)(RTH)对于任意RRT=Ir的方阵R成立，故可设W′=WR,H′=RTH。同时基向量即H未限制为正交，增加了基向量的可选择性。这些都妨碍了其基向量的解释性。

在人脸图像中应用VQ（类k-means）、PCA以及NMF得到的结果如下：

可以发现NMF更倾向于与对图像进行区块分解，而每张图片为各个部位的组合。值得注意的是PCA和NMF都具有基向量任意选取的问题（因为都是线性子空间的基向量选取，以及NMF还未限制正交），分析解释各个基向量是存在风险的。

Factor Analysis (FA)

关于FA的介绍请参考：CS229课程笔记13：Factor Analysis简介。

简单地说，FA为因子分解，即同样是求解子空间。但不同于PCA最小化投影误差和NMF限制基向量非负等，FA对基向量做出了假设。其假设X=AS+ϵ，其中S∼N(0,I)，ϵ∼N(0,Ψ)，其中Ψ为对角阵。即每个因子是不相干的（uncorrelated），X各个维度之间的相干性使用A来模拟，ϵ用于近似各个维度单独的未模拟误差。模型的参数有AAT+Ψ。可以通过EM算法最大似然求解。

Independent Component Analysis (ICA)

注意到FA中的基向量可以任意旋转，即ARRTAT=I for all RRT=I，主要是由于假设因子为高斯分布。此假设在大多数情况下不成立，仅仅是为方便计算而选取的简单分布。ICA则假设一种非高斯分布的因子分布，同时假设各个因子之间是independent的（强于uncorrelated假设）进行求解。ICA与PCA的比较如下图：

具体地，同样假设X=AS+ϵ, 等价于求解S=WX。使用KL散度量化相关性，即计算p(S)（实际分布）与∏qi=1p(si)（各个因子独立的联合分布）的KL散度：

其中H(S)=−∫g(s)logg(s)ds为概率分布g(s)的信息熵。

注意到高斯分布的信息熵最高，最小化上诉各维分布的信息熵和等价于最大化其与高斯分布信息熵的差：

其中Zj∼N(E(Sj),Var(Sj))。

为了方便求解，可以对上诉损失函数进行近似，得到快速ICA算法。

Multi-Dimensonal Scaling (MDS)

直接求取原空间x∈Rp在子空间的投影z∈Rk,k<p。使得投影之间的距离和原空间之间的距离尽可能相同。例如最简单的损失函数为：

一些变化的算法损失函数有：

使得算法相对更注重于保持距离较小的数据点之间的距离。

另外还可以注重保留数据点之间的相似性：

使用梯度下降法对z求解。

Non-linear Dimension Reduction

此部分算法假设高维空间中数据点都位于某个低维流形附近（这个假设通常是成立的，因为特征通常是某些实际控制量的非直接度量，考虑图像1024×1024个特征，但实际信息不多，在Harr空间中是sparse的），算法的目的是对流形展开，得到数据的低维表示。
注意到MDS中若使用常用的范数作为距离度量，会使得算法使用过多的高维空间中距离信息，而忽略了流形的信息，例子如下：

以下三个算法均是通过缩减数据视野的局部算法，期待得到更好的流形表示：
1. ISOMAP：是更改距离度量方法的保距降维方法。其使用的距离度量方法是首先构造关联图，将物理距离较小的各个点之间连接起来；然后任意两点之间的距离即为关联图中的最小路径长度。
2. Local linear Embedding：即不是保持距离相近，而是保持每个点与周围点之间的关系不变。具体做法如下：

3. Local MDS：主要注重保持较短的距离，对于较长的距离则权重较小，而且对其进行截断。具体算法如下：