降纬与度量学习

k近邻学习

k近邻学习是一种常见的监督学习方法，给定测试样本，然后基于某种距离度量找出训练样本中与测试样本距离最近的k个样本。在预测结果时，既可以通过投票法选择k个样本中出现最多的类标记，也可以在回归任务中使用平均法计算输出标记的平均值，还可以基于距离远近进行加权平均或者加权投票。

给定测试样本x，若其最近邻样本为z，则该分类器的出错概率就是x与z类标记不同的概率： \[ P(err) = 1 - \sum_{c \in y} P(c|x)P(c|z) \]

低维嵌入

假设测试样本x附近任意小的\(\sigma\)距离范围内总能找到一个训练样本，即需要实现足够大的密度采样。然而这种情况在现实生活中却不容易实现，以\(\sigma=0.001\)为例，单个属性就需要1000个样本点平均分布在归一化后的属性取值范围内。但假如属性维度数目达到了20，样本就指数增长到(10³⁾20，这就是出现了所谓的维数灾难(curse of dimensionality)。

缓解这个问题的一个重要途径是实现降维，之所能降维，是因为往往与学习任务相关的属性仅仅是某个低维分布。若要求原始空间样本中样本之间的距离在低维空间得以保持，则要实现"多维缩放"(MDS——Multiple Dimensional Scaling)。

假设m个样本在原始空间的距离矩阵为\(D\in R^{m X m}\)，其第i行h列的元素\(dist_{ij}\)为样本\(x_i\)到\(x_j\)的距离。而我们的目标是获得样本在\(d'\)维空间的表示\(Z\in R^{d'Xm}\)，d'比d小，且任意两个样本在d'维空间中的欧式距离应该与原始空间相等或者近似于。

令\(B=Z^TZ \in R^{mXm}\)，且\(b_{ij}=z_i^Tz_j\)，则有： \[ dist_{ij}^2 = b_{ii} + b_{jj} - 2b_{ij} \] 令降维后的样本Z被中心化，即\(\sum_{i=1}^mz_i=0\)，矩阵B的行与列之和为0，则有： \[ \sum_{i=1}^m dist_{ij}^2 = tr(B) + mb_{jj} \\ \sum_{j=1}^m dist_{ij}^2 = tr(B) + mb_{ii} \\ \sum_{i=1}^m\sum_{j=1}^m dist_{ij}^2 = 2m \ tr(B) \] 其中，tr为矩阵的trace，\(tr(B) = \sum_{i=1}^m || z_i ||^2\)： \[ dist_{i.}^2 = \frac{1}{m}\sum_{j=1}^m dist_{ij}^2 \\ dist_{.j}^2 = \frac{1}{m}\sum_{i=1}^m dist_{ij}^2 \\ dist_{..}^2 = \frac{1}{m^2}\sum_{i=1}^m\sum_{j=1}^m dist_{ij}^2 \] 根据上式，可得： \[ b_{ij} = -\frac{1}{2}(dist_{ij}^2-dist_{i.}^2-dist_{.j}^2+dist_{..}^2) \] 由此可见，我们可以通过降维前后保持不变的距离矩阵D求取内积矩阵B。对矩阵B做特征值分解，取A为d‘个最大特征值所构成的对角矩阵，V为相应的特征向量矩阵。 \[ Z = A^{1/2}V^T \in R^{d'Xm} \] 一般来说，想要获得低维子空间，最简单是对原始高维空间进行线性变换，这就是线性降维方法。

主成分分析

主成分分析(Principal Component Analysis，简称PCA)是最常用的一种降维方法。简单来说，就是用一个超平面来对所有样本进行适当的表达，这个超平面应该具有的性质：

样本点到这个超平面的距离都足够近；
样本点在这个超平面的投影尽可能分开；

假设样本进行了中心化，即\(\sum_ix_i=0\)，再假定投影变换后的新坐标系为\({w_1,w_2,…,w_d}\)，其中\(w_i\)是标准正交基。假设降维之后样本点\(x_i\)在低维空间下的投影是\(z_i = {z_{i1},z_{i2},…,z_{id'}}\)。其中，\(z_{ij}=w_j^Tx_i\)，重构回来的投影带点为\(x_i=\sum_{j=1}^{d'}z_{ij}w_j\)。

考虑整个数据集，原样本点与重构后的投影点之间的距离： \[ \sum_{i=1}^m||\sum_{j=1}^{d'}z_{ij}w_j - x_i||^2_2 = \sum_{i=1}^mz_i^Tz_i-2\sum_{i=1}^mz_i^TW^Tx_i+const \varpropto - tr(W^T(\sum_{i=1}^mx_ix_i^T)W) \] 根据上面的属性要求，我们需要最小化上式： \[ min \ -tr(W^TXX^TW) \] 而为了使得所有样本点的投影尽可能分散，则最大化投影后样本点的方差 \(\sum_i W^Tx_ix_iW\)： \[ max \ tr(W^TXX^TW) \] 可见，两个优化目标等价，对其使用拉格朗日乘子法，得： \[ XX^Tw_i = \lambda_iw_i \] 然后对协方差矩阵\(XX^T\)进行特征值分解，将求得的特征值进行排序，再取前n个特征值对应的特征向量构成\(W^*=(w_1,w_2,…,w_n)\)。

核化线性降维

在现实任务中，需要实现非线性映射才能找到恰当的低维嵌入。非线性将维的一种常用方法是基于核技巧对线性将维方法进行"核化"。

假设我们将在高维特征空间中把数据投影到\(W=(w_1,w_2,..,w_d)\)确定的超平面上，根据上面的式子有： \[ (\sum_{i=1}^mz_iz_i^T)w_j = \lambda_jw_j \] 其中\(z_i\)是样本点\(x_i\)在高维特征空间中的像，因此有: \[ w_j = \frac{1}{\lambda_j}(\sum_{i=1}^mz_iz_i^T)w_j = \sum_{i=1}^m z_i \frac{z_i^Tw_j}{\lambda_j} = \sum_{i=1}^m z_i \alpha_i^j \] 假定\(z_i = \phi(x_i)\)，即原始属性空间中的样本点通过映射\(\phi\)产生。

因此前面的式子可以变换为 \[ (\sum_{i=1}^m \phi(x_i)\phi(x_i)^T) w_j= \lambda_jw_j \\ w_j = \sum_{i=1}^m \phi(x_i) \alpha_i^j \] 由于我们不知道\(\phi\)的具体形式，因此引入核函数： \[ k(x_i, x_j) = \phi(x_i)\phi(x_i)^T \] 将上面的式子化简后，得到： \[ K \alpha^j = \lambda_j\alpha^j \] 这里又变成了特征值分解的问题，取K最大的d'个特征值对应的特征向量即可。

流形学习

"流形"是在局部与欧氏空间同胚的空间，它在局部具有欧氏空间的性质，能用欧式距离来进行距离计算。若低维流形嵌入到高维空间中，其局部仍然具有欧氏空间的性质，因此可以在局部建立降维映射关系，并设法将局部关系推广到全局。

等度量映射

等度量映射(Isomap)的一个出发点：低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，可能会丢失某些信息。以下图为例：

如果使用传统的欧氏距离来作为距离尺度，显然会抛弃“数据的内部特征”，即假设一只虫子从一点到另一点，如果它不能脱离图中的曲面行走，那么红色曲线才是距离最短的路径。

如上图，低维嵌入流形上两点间的距离是"测地线"距离，要求得这个距离，可以对每个点基于欧氏距离找出其近邻点，然后就能建立一个近邻连接图。这样计算两点之间的测地线距离的问题，就变成了临接图上两点之间的最短路径问题。

构建近邻图也有两种做法：一种是指定近邻点个书，例如欧氏距离最近的k个点为近邻点；另一种则是指定距离阈值\(\epsilon\)，小于这个距离的点则认为是近邻点。

局部线性嵌入

与Isomap不同的是，局部线性嵌入LLE试图保持领域内样本之间的线性关系，如图：

假设样本点可以通过它的领域样本线性重构： \[ x_i = w_{ij}x_j+w_{ik}x_k+w_{il}x_; \] LLE希望上式的关系在低维空间中得以保持。

算法步骤；

LLE首先为每个样本找到其近邻下标集合\(Q_i\)，然后计算出样本点对\(x_i\)进行线性重构的系数\(w_i\)：

\[ min \sum_{i=1}^m || x_i - \sum_{j \in Q_i} w_{ij}x_j||^2_2 \\ \sum_{j \in Q_i} w_{ij} = 1 \]

令\(C_{jk} = (x_i-x_j)^T(x_i-x_j)\)，\(w_{ij}\)有闭式解： \[ w_{ij} = \frac{\sum_{k\in Q_i} C_{jk}^{-1}}{\sum_{l,s \in Q_i} C_{ls}^{-1}} \] LLE在低维空间中保持\(w_i\)不变，因此低维空间坐标\(z_i\)可通过以下求解： \[ min \sum_{i=1}^m || z_i - \sum_{j \in Q_i} w_{ij}z_j||^2_2 \\ M = (1-W)^T(1-W) \] 则上式可以重写为： \[ min \ tr(ZMZ^T) \\ ZZ^T = 1 \] 然后对改式通过特征值分解，M最小的k个特征值组成的矩阵即为\(Z^T\).

度量学习

在机器学习中，对高维数据进行降维的目的是找到一个合适的低维空间，而由于每个空间对应了在样本属性定义的一个距离度量。因此寻找合适的空间就是寻找一个合适的距离度量。

对两个d维的样本\(x_i, x_j\)，引入属性权重后的平方欧氏距离为： \[ dist_{wed}^2(x_i,x_j) = ||x_i-x_j||^2_2 = w_1\cdot dist_{ij,1}^2 + w_2\cdot dist_{ij,2}^2+...+w_d\cdot dist_{ij,d}^2 \\ =(x_i-x_j)^TW(x_i-x_j) \] 其中W=diag(w)是一个对角矩阵。

由于W的非对角矩阵为0，因此坐标轴是正交的，即属性之间无关，但现实生活中属性往往是相关的，因此可以将W替换为一个普通的半正定对称矩阵M。由此可得到马氏距离： \[ dist_{mat}^2(x_i,x_j) =(x_i-x_j)^TM(x_i-x_j)= ||x_i-x_j||^2_M \] 度量学习必须对M进行学习，而因为M是半正定对称矩阵，因此一定存在正交基P使得\(M=PP^T\)。

对M学习需要设置合适优化目标，不同度量学习方法针对不同的目标获得合适半正定对称距离度量矩阵M。