第十九讲多维标度法dataobjectdataasvectorembeddingembeddingmodel0.0560.00S0-0.060.04580嵌入embedding/标度scaling：将对象表示成向量
第十九讲 多维标度法 embedding/scaling 嵌入embedding/标度scaling: 将对象表示成向量
n个物体/对象(object)的相似度矩阵S，单向谱配列方法以n个实数Recap（即Laplace矩阵L=D一S的最小非O特征向量）表示n个物体，该特征向量称为物体的embedding嵌入/scaling标度/encoding编码单向谱配列：n个物体的相似度矩阵S=（si)，d=S1,D = diag(d), 记Laplacian矩阵L = D - S,min=sij(xi -x;)2 =minxTLx, s.t. Ilxl = 1, x 1 1最优解为L的最小非o特征根对应的特征向量xmin，其n个分量是n个物体（标量、因子水平等）的实数表示embedding)：特征向量xmin分量的次序代表了n个物体的邻近和顺序关系。例1.食品评价例子：5个指标的相关系数矩阵如下，当作相似系数矩阵Taste Goodbuy FlavorSnackEnergyTaste10.020.960.420.01)Energy0.0210.130.710.85GoodbuyS=GoodbuySnackTasteFlavorFlavor0.960.1310.500.110.420.710.500.79Snack110.010.850.110.79EnergyTasteFlavorSnack GoodbuyEnergy-0.449-0.6000.1310.4580.480特征向量L=D-Sembedding2
2 𝑛个物体/对象(object)的相似度矩阵𝑆，单向谱配列方法以𝑛个实数 （即Laplace矩阵𝐿 = 𝐷 − 𝑆的最小非0特征向量）表示𝑛个物体，该 特征向量称为物体的embedding嵌入/scaling标度/encoding编码 Recap 单向谱配列: 𝑛个物体的相似度矩阵𝑆 = (𝑠𝑖𝑗)， 𝐝 = 𝑆𝟙， 𝐷 = diag(𝐝), 记Laplacian矩阵𝐿 = 𝐷 − 𝑆, min1 2 σ s𝑖𝑗(𝑥𝑖 − 𝑥𝑗) 2 = min𝐱 ⊤𝐿𝐱 ，s.t. 𝐱 = 1，𝐱 ⊥ 𝟙 最优解为𝐿的最小非0特征根对应的特征向量𝐱min，其𝑛个分 量是𝑛个物体（标量、因子水平等）的实数表示(embedding)， 特征向量𝐱min分量的次序代表了𝑛个物体的邻近和顺序关系。 0.01 0.85 0.11 0.79 1 0.42 0.71 0.50 1 0.79 0.96 0.13 1 0.50 0.11 0.02 1 0.13 0.71 0.85 1 0.02 0.96 0.42 0.01 Energy Snack Flavor Goodbuy Taste Taste Goodbuy Flavor Snack Energy 𝑆 = 例1.食品评价例子：5个指标的相关系数矩阵如下，当作相似系数矩阵 𝐿 = 𝐷 − 𝑆 特征向量 embedding Taste Flavor Snack Goodbuy Energy −0.600 −0.449 0.131 0.458 0.480
单向配列（seriation)问题基于相似度矩阵求解研究对象的一维欧氏表示，并排序。但一维表示信息不够丰富。多维标度法考虑将n个物体映射到k维向量,X1,,XnERk，能否将单向谱配列的优化目标函数拓展为 silx - x,;l ? silxi - x;ll2 =, sij((xi1 - xj1)2 + .. + (xik - xjk)2)=sij(xi1 -xj1)2 + +sij(xik -Xjk)2X = (X1,.,Xn)T= x()LX(1) + .. +x(k) LX(k) = tr(XTLX)= (X(1),. X(k)如果限制X列正交，那么最优解是L的最小k个非o特征根的特征向量。但从保距或保内积的角度来看，该限制过于严苛，如下图例1（续）Taste和flavor在L的二o维特征向量表示下相距很远，这858显然不合理。3402e4624.13
3 单向配列(seriation)问题基于相似度矩阵求解研究对象的一维欧 氏表示，并排序。但一维表示信息不够丰富。 多维标度法考虑将𝑛个物体映射到𝑘维向量, 𝐱1, . , 𝐱𝑛 ∈ 𝑅 𝑘 , 能否将单 向谱配列的优化目标函数拓展为 1 2 σ s𝑖𝑗 𝐱𝑖 − 𝐱𝑗 2 ？ 1 2 σ s𝑖𝑗 𝐱𝑖 − 𝐱𝑗 2 = 1 2 σ s𝑖𝑗 (𝑥𝑖1 − 𝑥𝑗1) 2 + ⋯ + (𝑥𝑖𝑘 − 𝑥𝑗𝑘) 2 = 1 2 σ s𝑖𝑗(𝑥𝑖1 − 𝑥𝑗1) 2 + ⋯ + 1 2 σ s𝑖𝑗(𝑥𝑖𝑘 − 𝑥𝑗𝑘) 2 = 𝐱(1) ⊤ 𝐿𝐱(1) + ⋯ +𝐱(𝑘) ⊤ 𝐿𝐱(𝑘) = 𝑡𝑟(𝑋 ⊤𝐿𝑋) 如果限制𝑋列正交，那么最优解是 𝐿 的最小𝑘个非0特征根的特征 向量。但从保距或保内积的角度来看，该限制过于严苛, 如下图 例1（续）Taste和 flavor 在 𝐿 的二 维特征向量表示下相距很远，这 显然不合理。 𝑋 = (𝐱1, . , 𝐱𝑛) ⊤ = (𝐱 1 , . , 𝐱(𝑘))
标度/嵌入/编码/低维表示Scaling主观评价或非数值变量的量化方式称为标度方法embedding(scaling）。高维欧氏向量的压缩重新表示也可称为标度或嵌入（embedding)方法。多维标度法（MDS，multidimensionalscaling）在尽量保持之间相近程度信息的前提下，用欧氏向量表示研究对象（object）。这里object可以是物体样本个体、变量或其他任何感兴趣的研究对象。多维标度法用多个实数即向量表示每个研究个体。单向配列将研究对象/物体用实数表达出来，可称为1维标度法。实际上PCA、SVD、CCA、CA等方法都是某种意义上的标度或嵌入方法不同的是这些方法基于数据矩阵X，而MDS基于（主观）相似度矩阵或距离矩阵对感兴趣的对象（object）进行嵌入表示，这里的object可以是个体，也可以是变量。如果将主观相似度矩阵可以理解成XX或XTX，那么MDS与PCA/SVD等方法类似下面首先回顾一下这些传统方法
4 标度/嵌入/编码/低维表示 主观评价或非数值变量的量化方式称为标度方法 (scaling) 。高维欧氏向量的压缩重新表示也可称 为标度或嵌入 (embedding)方法。 多维标度法（MDS，multidimensional scaling）在 尽量保持之间相近程度信息的前提下，用欧氏向量 表示研究对象（object）。这里object可以是物体、 样本个体、变量或其他任何感兴趣的研究对象。 Scaling embedding 多维标度法用多个实数即向量表示每个研究个体。单向配列将研究对 象/物体用实数表达出来，可称为1维标度法。 实际上PCA、SVD、CCA、CA等方法都是某种意义上的标度或嵌入方法， 不同的是这些方法基于数据矩阵𝑋，而MDS基于（主观）相似度矩阵 或距离矩阵对感兴趣的对象（object）进行嵌入表示，这里的object可 以是个体，也可以是变量。如果将主观相似度矩阵可以理解成𝑋𝑋 ⊤或 𝑋 ⊤𝑋，那么MDS与PCA/SVD等方法类似。 下面首先回顾一下这些传统方法
PCA/假设中心化的数据矩阵Xnxp（行：样本个体，列：变量）。FAX的行向量表达了每个个体，X的列向量表达了每个变量，这是个体或变量的原始嵌入/欧氏表示。PCA：如果希望得到个体的低维的/更有效的表示，我们将变量个数p压缩，以更短长度k<p的行向量表示个体一如何得到有用的压缩?整合变量（X的列）之间的相关性/相似性，提取XX前k个最重要的特征向量（载荷，这实际上是变量的嵌入/压缩表示）作用在X的行向量上得到主成分，即个体的低维嵌入（这实际上是XX的特征向量），上述过程得到了个体的低维嵌入（主成分），同时也得到了变量的低维嵌入（载荷）。这种对偶性正是SVD,biplot是这种对偶性的体现。具体地，利用方差矩阵（或XTX）的特征向量矩阵V压缩变量/变换数据，得到样本个体的新的表示：主成分Y=XV（注意Y的列向量是XXT的特征向量），其第行的前若于个分量（主成分）是第个个体的压缩表示/嵌入。换言之，PCA利用变量（X的列）之间的方差矩阵（即变量的相似度矩阵）的特征向量V对数据进行主成分变换，得到个体（×的行）的主成分表示（即个体相似度矩阵XXT的特征向量）。根据对称性，从行的特征也可到列的刻画/嵌入。FA：模型表示PCA，潜变量~主成分5
5 假设中心化的数据矩阵𝑋𝑛×𝑝（行：样本个体，列：变量）。 𝑋的行向量表达了每个个体，𝑋的列向量表达了每个变量，这是个 体或变量的原始嵌入/欧氏表示。 PCA：如果希望得到个体的低维的/更有效的表示, 我们将变量个数 𝑝 压缩, 以更短长度 𝑘 < 𝑝 的行向量表示个体 – 如何得到有用的压 缩? 整合变量(X的列)之间的相关性/相似性, 提取𝑋 ⊤𝑋前 𝑘 个最重要的特 征向量(载荷, 这实际上是变量的嵌入/压缩表示),作用在X的行向量 上得到主成分,即个体的低维嵌入(这实际上是𝑋 𝑋 ⊤的特征向量). 上 述过程得到了个体的低维嵌入(主成分),同时也得到了变量的低维嵌 入(载荷) 。这种对偶性正是SVD,biplot是这种对偶性的体现。 PCA/ FA 具体地, 利用方差矩阵（或𝑋 ⊤𝑋）的特征向量矩阵𝑉压缩变量/变换数据，得到 样本个体的新的表示：主成分𝑌 = 𝑋𝑉（注意𝑌的列向量是𝑋𝑋⊤的特征向量）， 其第𝑖行的前若干个分量（主成分）是第𝑖个个体的压缩表示/嵌入。换言之， PCA利用变量（X的列）之间的方差矩阵（即变量的相似度矩阵）的特征向量 𝑉对数据进行主成分变换，得到个体（X的行）的主成分表示（即个体相似度 矩阵𝑋𝑋⊤的特征向量）。根据对称性，从行的特征也可到列的刻画/嵌入。 FA：模型表示PCA, 潜变量≈主成分
变量的变量的个体的个体的相相似度表示VD表示UD似度XTXXXTVY=XV=UD特征特征主成向量向量分变换对偶性：利用列特征得到行（个体）的嵌入表示，利用行特征得到列（变量）的嵌入表示，这正是SVD所表达的行列之间的对偶性。总之，变量之间的相似度矩阵XTX的特征向量V（其实是VD）的前k列是变量的k维嵌入/标度；个体之间的相似度矩阵XXT的特征向量U其实是VD）的前k列是个体的k维嵌入/标度，6
6 𝑋 ⊤𝑋 𝑉 变量的 表示𝑉𝐷 𝑌 = 𝑋𝑉 = 𝑈𝐷 主成 分变 换 变量的 相似度 个体的 表示U𝐷 𝑋 𝑋 ⊤ 个体的相 似度 特征 向量 特征 向量 对偶性：利用列特征得到行（个体）的嵌入表示，利用行特征得到 列（变量）的嵌入表示，这正是 SVD所表达的行列之间的对偶性。 总之，变量之间的相似度矩阵𝑋 ⊤𝑋的特征向量𝑉（其实是𝑉𝐷） 的前𝑘列是变量的𝑘维嵌入/标度；个体之间的相似度矩阵𝑋𝑋⊤的 特征向量𝑈其实是𝑉𝐷）的前𝑘列是个体的𝑘维嵌入/标度
SVD: X = UDVT:SVD以XXT的特征向量U重新表示个体：主成分（个体的表示/嵌入）Y=XV=UD以XTX的特征向量重新表示变量：主样本(变量的表示/嵌入)Z =VD =XTUX = UDVT ~ Uk DkVT, k < rank(X)UkDk：个体的低维嵌入DkVEUk~XVkDk：变量的低维嵌入kxknxkkxpnxpU:列基V:行基D：权/奇异值
7 SVD：𝑋 = 𝑈𝐷𝑉 ⊤: • 以 𝑋𝑋⊤的特征向量𝑈重新表示个体： 主成分(个体的表示/嵌入) 𝑌 = 𝑋𝑉 = 𝑈𝐷 • 以𝑋 ⊤𝑋的特征向量重新表示变量： 主样本(变量的表示/嵌入) 𝑍 = 𝑉𝐷 = 𝑋 ⊤𝑈. SVD 权 奇异值 行基 列基 : / : : D V U 𝑋 = 𝑈𝐷𝑉 ⊤ ≈ 𝑈𝑘 𝐷𝑘𝑉𝑘 ⊤ , 𝑘 < 𝑟𝑎𝑛𝑘(𝑋) 𝑋 𝑛 × 𝑝 𝑈𝑘 𝑛 × 𝑘 𝑉𝑘 ⊤ 𝑘 × 𝑝 ≈ 𝐷𝑘 𝑘 × 𝑘 𝑈𝑘𝐷𝑘: 个体的低维嵌入 V𝑘𝐷𝑘: 变量的低维嵌入
典则相关分析CCA和对应分析CA都是PCA或SVD的拓展或应用，CCA/CA都可看作是嵌入/标度方法：口CCA：变量分成两部分，类似于PCA，利用协方差矩阵的特征向量分别组合压缩两部分变量，以XXT的特征向量重新表示个体，尽量保持协方差。口cA：两个因子变量以one-hot嵌入表示，利用列联表/协方差的SVD，以XTX的特征向量重新表示/嵌入变量（X的列）尽量保持Contigency。注意CCA与CA的区别：CCA压缩变量嵌入表示个体，CA压缩个体嵌入表示变量。当只有两个因子的时候CA与CCA是对偶问题。8
8 典则相关分析CCA和对应分析CA都是PCA或SVD的拓展或应用， 都可看作是嵌入/标度方法： CCA/CA 注意CCA与CA的区别：CCA压缩变量嵌入表示个体，CA 压缩个体嵌入表示变量。当只有两个因子的时候,CA与 CCA是对偶问题。 CCA：变量分成两部分，类似于PCA，利用协方差矩阵的特 征向量分别组合压缩两部分变量，以𝑋𝑋⊤的特征向量重新 表示个体，尽量保持协方差。 CA: 两个因子变量以one-hot嵌入表示，利用列联表/协方 差的SVD，以 𝑋 ⊤𝑋 的特征向量重新表示/嵌入变量(X的列）， 尽量保持Contigency
机器学习文本处理(NLP:natural languageprocessing)中word2vec单词的向量化表示方法word2vec与CA几乎相同：*首先将单词(word)用欧氏向量表示，通常用one-hot嵌入方法（哑变量）表示，即只有一个1，且与全是0的向量表示每个单词。结合词汇的关联性/相似性和用词环境，进一步利用TRd数据变换、压缩、降维技术得到保留相近性的更好wordembedding的向量表示。词汇关联性One-hotcat变换One-hotembedding长度=字典总字数0.1-1.20.7-0.5Short/informativeembedding9
9 机器学习文本处理(NLP: natural language processing)中 单词的向量化表示方法word2vec与CA几乎相同： 首先将单词(word)用欧氏向量表示，通常用one-hot 嵌入方法（哑变量）表示，即只有一个1，且与全是 0的向量表示每个单词。 结合词汇的关联性/相似性和用词环境，进一步利用 数据变换、压缩、降维技术得到保留相近性的更好 的向量表示。 cat 0 0 ⋯ 1 0 0.1 -1.2 ⋯ 0.7 -0.5 One-hot embedding 长度=字典总字数 One-hot 变换 Short/informative embedding word2vec 词汇关联性
多维标度法MDS下面介绍基于(主观)相似度系数矩阵或距离矩阵的多维标度法MDS，这类问题没有原始数据矩阵X，可以看作是由相似度矩阵/距离矩阵出发，反解其X矩阵的方法主要介绍cMDS（ClassicalMDS，经典多维标度法，保持相似度，也称为主坐标分析方法（principalcoordinatesanalysisPCoA））；mMDS（metricMDS，度量型多维标度法，保持距离）和非度量型MDS。给定一个nxn相似度矩阵S=（s.），给定正整数k≤n，cMDS方法求解CMDS优化目标X..,eR,X=-(x....x)极小化Stress函数:(*)Stress=E(s,-x,x,)=S-XXT I/IS理解成XXT，X是数据矩阵10
10 （ ） 极小化 函数： 给定一个 相似度矩阵 ，给定正整数 方法求解 ( ) || || . * ,., , ( ,., ) , Stress ( ) , cMDS 2 , 2 1 1 F i j ij i j n k n ij Stress s S XX R X n n S s k n T T T x x x x x x cMDS优 化目标 下面介绍基于(主观)相似度系数矩阵或距离矩阵的多维标度法 MDS, 这类问题没有原始数据矩阵𝑋, 可以看作是由相似度矩阵/ 距离矩阵出发, 反解其𝑋矩阵的方法. 𝑆理解成𝑋𝑋⊤ ，𝑋是数据矩阵 主要介绍cMDS (Classical MDS，经典多维标度法，保持 相似度，也称为主坐标分析方法 (principal coordinates analysis, PCoA) ) ；mMDS (metric MDS，度量型多维标 度法 ，保持距离)和非度量型MDS 。 多维标度法MDS