降维与度量学习

第10章 降维与度量学习

• Page225: k近邻

  k近邻是常用的监督学习方法，主要是用某种距离度量方法来找出与测试样本最靠近的k个点，根据这k位邻居的信息来预测其分类。是“懒惰学习”。

• Page225: 急切学习

  这种学习方法在训练阶段就对样本进行学习处理。

• Page225: 平均法

  将这k个样本的实值的平均值作为预测的输出。

• Page225: 最近邻分类器

  k=1，即是最近邻分类器。

• Page226: 密采样

  训练样本的采样密度足够大，保证任意小的距离内都能找到一个训练样本，即为“密采样”。

• Page227: 多维缩放

  多维缩放是指多维空间的样本转换到低维空间上，能够继续保持其距离。

• Page227: 降维

  通过数学变换将高维空间投射到低维子空间。

• Page227: 维数约简

  即降维。

• Page227: 维数灾难(247)

  即高维情况下带来的距离计算量大、样本稀疏等问题，比如随着维度增加，计算量会呈指数增长的趋势。

• Page229: PCA

  PCA(Principal Component Analysis，即主成分分析)，可从最近重构性和最大可分性来思考PCA。

  最近重构性则是希望样本点到超平面的距离足够小，优化目标是$\min_W -tr(W^TXX^TW)$ $s.t. W^TW=I$

  最大可分性则是希望样本点在该超平面的投影尽可能分开，优化目标是$\max_W tr(W^TXX^TW)$ $s.t. W^TW=I$

  PCA的步骤是对所有样本进行中心化，然后计算协方差矩阵，再对协方差矩阵做特征值分解，然后取最大的d'个特征值所对应的特征向量。

• Page229: 线性降维

  基于线性变换来进行降维的方法。

• Page229: 主成分分析

  同PCA。

• Page231: 奇异值分解(402)

  任意的实矩阵都可以进行分解，如$A\in \mathbb{R}^{m\times n}$可以分解为$A=U\Sigma V^T$,其中U是m×m阶酉矩阵；Σ是半正定m×n阶对角矩阵；而$V^T$，即V的共轭转置，是n×n阶酉矩阵。$u_i$称为A的左奇异值，$v_i$称为A的右奇异值。Σ对角线上的元素为A的奇异值。矩阵A的秩是非零奇异值的个数。

• Page232: 本真低维空间

  对原始低维空间和降维后的低维空间进行区分，称原始采样的低维空间为本真低维空间。

• Page232: 非线性降维

  非线性降维即是采用非线性变换的方法对数据进行降维，常用的是基于核技巧对线性降维方法进行核化。

• Page232: 核化线性降维

  对线性降维方法进行核化，以保持其原本的低维结构。

• Page232: 核主成分分析

  Kernelized PCA，在高维特征空间将数据投影到由d维的W确定的超平面上，z是x在高维空间上的像，假设$z_i=\phi (x_i)$，引入核函数$\kappa (x_i,x_j)=\phi(x_i)^T\phi(x_j)$，进一步用矩阵K替代，进而计算出投影矩阵。主要作用是将线性不可分的数据，映射到高维后进行划分。

• Page234: 本真距离

  即为在原始空间上的距离。

• Page234: 测地线距离

  测地线距离是两点之间的本真距离。

• Page234: 等度量映射

  等度量映射认为高维空间的直线距离不能很好地衡量其距离，所以等度量映射试图让“流形”距离在降维后仍能很好保持。

• Page234: 流形学习

  流形是在局部与欧式空间同胚的空间，所以局部可以利用欧氏距离来计算。

• Page235: 局部线性嵌入

  保持邻域内样本的线性关系的一种方法。

• Page237: 度量学习

  通过学习，得到合适的距离度量方法。

• Page238: 近邻成分分析

  NCA(Neighbourhood Component Analysis，即近邻成分分析)是和KNN关联的距离度量方法，在原数据集上进行NCA距离测量，并且完成降维，然后使用KNN在低维空间上对数据进行分类。NCA主要是随机选择近邻，然后通过LOO(Leave one out)的交换检验结果来求马氏距离的变换矩阵。通过优化目标可以得到最大化正确率的距离度量矩阵。

• Page239: 必连约束(307)

  样本必属于一个簇。

• Page239: 勿连约束

  样本必不属于同一个簇。

• Page240: 半监督聚类(307)

  半监督聚类的先验知识主要是样本相似度约束条件，将必连关系和勿连关系作为学习任务优化目标的约束。约束条件主要是基于约束和基于距离。前者主要是依靠用户提供的约束来实现监督指导作用，后者主要是自适应距离度量。

• Page240: 多视图学习

  多视图学习可以看成是从多个角度去学习，比如对同一个事物用多种方法去提取其特征，就能得到其多模态的特征，然后再对多模态特征进行学习。

• Page240: 流形假设(294)

  流行假设是指在很小的一个领域内的样本具有相似的特性，则其标签也相似。

• Page240: 流形正则化

  在正则化项加入与流形相关的项。