机器学习

1、低维嵌入

事实上，在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”。缓解维数灾难的一个重要途径是降维，即通过某种数学变换将原始高维属性空间转变为一个低维的“子空间”，在这个子空间中样本密度大幅度提高，计算距离也变得更加容易。

2、多维放缩（MDS-multiple dimensional scaling）

若要求原始空间样本之间的距离在低维空间中得以保持，就得到一种典型的降维方法MDS。

假定 $m$ 个样本在原始空间的距离矩阵为 $D \in \mathbb{R}^{m \times m}$ ,其第 $i$ 行 $j$ 列的元素 $Dist_{ij}$ 为样本 $\mathbf{x}_i$ 到 $\mathbf{x}_j$ 的距离。我们的目标是获得样本在低维 $d^\prime$ 维空间的表示 $\mathbf{Z} \in \mathbb{R}^{d^\prime \times m},d^\prime \le d$ ，且任意两个样本在 $d^\prime$ 维空间的欧氏距离等于原始空间的欧式距离，即 $||z_i - z_j|| = Dist_{ij}$ 。其中

$\mathbf{Z} = \left[ \begin{matrix} z_{11} & z_{12} & z_{13} & \cdots & z_{1m}\\ z_{21} & z_{22} & z_{23} & \cdots & z_{2m} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ z_{d^\prime1} & z_{d^\prime2} & z_{d^\prime3} & \cdots & z_{d^\prime m} \end{matrix} \right] = \left[ \begin{matrix} \mathbf{z_1} & \mathbf{z_2} & \mathbf{z_3} & \cdots & \mathbf{z_m} \end{matrix} \right] \\$

$\mathbf{z_i} = \left[ \begin{matrix} z_{1i} \\ z_{2i} \\ \vdots \\ z_{d^\prime i} \end{matrix} \right]$
表明第i个样本在 $d^\prime$ 空间的坐标

令 $\mathbf{B} = \mathbf{Z}^{\mathrm{T}}\mathbf{Z} \in \mathbb{R}^{m \times m}$ ,其中 $\mathbf{B}$ 为降维后样本的内积矩阵， $b_{ij} = \mathbf{z}_i^\mathrm{T}\mathbf{z_j}$ ,有

$\mathbf{B} = \left[ \begin{matrix} \mathbf{z_1^{\mathrm{T}}} \\ \mathbf{z_2^{\mathrm{T}}} \\ \vdots \\ \mathbf{z_m^{\mathrm{T}}} \\ \end{matrix} \right] \left[ \begin{matrix} \mathbf{z_1} & \mathbf{z_2} & \mathbf{z_3} & \cdots & \mathbf{z_m} \end{matrix} \right] = \left[ \begin{matrix} \mathbf{z_1}^\mathrm{T}\mathbf{z_1} & \mathbf{z_1}^\mathrm{T}\mathbf{z_2} & \mathbf{z_1}^\mathrm{T}\mathbf{z_3} & \cdots & \mathbf{z_1}^\mathrm{T}\mathbf{z_m} \\ \mathbf{z_2}^\mathrm{T}\mathbf{z_1} & \mathbf{z_2}^\mathrm{T}\mathbf{z_2} & \mathbf{z_2}^\mathrm{T}\mathbf{z_3} & \cdots & \mathbf{z_2}^\mathrm{T}\mathbf{z_m} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \mathbf{z_m}^\mathrm{T}\mathbf{z_1} & \mathbf{z_m}^\mathrm{T}\mathbf{z_2} & \mathbf{z_m}^\mathrm{T}\mathbf{z_3} & \cdots & \mathbf{z_m}^\mathrm{T}\mathbf{z_m} \end{matrix} \right] = \left[ \begin{matrix} b_{11} & b_{12} & b_{13} & \cdots & b_{1m} \\ b_{21} & b_{22} & b_{23} & \cdots & b_{2m} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ b_{m1} & b_{m2} & b_{m3} & \cdots & b_{mm} \\ \end{matrix} \right] \\ Dist_{ij}^2 = ||\mathbf{z_i} - \mathbf{z_j}||^2 = (\mathbf{z_i} - \mathbf{z_j})^2 = ||\mathbf{z_i}||^2 + ||\mathbf{z_j}||^2 - 2\mathbf{z_i}^\mathrm{T}\mathbf{z_j} = b_{ii} + b_{jj} -2b_{ij}$

为了便于讨论，令降维后的样本 $\mathbf{Z}$ 被中心化，那么就可以得到 $\mathbf{B}$ 的行于列之和均为零，即 $\sum^{m}_{i=1}b_{ij} = \sum_{j=1}^{m}b_{ij} = 0$ 。易知道：
$Dist_{\cdot j}^2 = \sum_{i=1}^m Dist_{ij}^2 = \sum_{i=1}^m b_{ii} + b_{jj} -2b_{ij} = \sum_{i=1}^m b_{ii} + b_{jj} -2 \sum_{i=1}^mb_{ij} = tr(\mathbf{B}) + mb_{jj} \\$
$Dist_{i\cdot}^2 =\sum_{j=1}^m Dist_{ij}^2 = \sum_{j=1}^m b_{ii} + b_{jj} -2b_{ij} = \sum_{j=1}^m b_{ii} + b_{jj} -2 \sum_{j=1}^mb_{ij} = tr(\mathbf{B}) + mb_{ii} \\$
$Dist_{\cdot \cdot}^2 =\sum_{i=1}^{m}\sum_{j=1}^{m}Dist_{ij}^2 = \sum_{i=1}^{m} tr(\mathbf{B})+mb_{ii} = m\times tr(\mathbf{B}) + m \times tr(\mathbf{B}) = 2m\times tr(\mathbf{B})$
其中 $tr(\cdot)$ 表示矩阵的迹， $tr(\mathbf{B}) = \sum_{i=1}^{m} b_{ii}$ .则
$b_{ij} = - \frac{1}{2} ( \frac{Dist_{\cdot \cdot}^2}{m^2} - \frac{Dist_{i\cdot}^2}{m} - \frac{Dist_{\cdot j}^2}{m} + Dist_{ij}^2 ) = - \frac{1}{2} [\frac{2}{m}tr(\mathbf{B})-\frac{1}{m}tr(\mathbf{B})-b_{ii} -\frac{1}{m}tr(\mathbf{B})-b_{jj} + b_{ii} + b_{jj} -2b_{ij} ]$
因为所有的 $Dist_{ij}$ 都是已知的，那么 $Dist_{\cdot\cdot}^2,Dist_{i\cdot}^2,Dist_{\cdot j}^2$ 都可以算出来，那么就可以根据原空间的距离矩阵 $\mathbf{D}$ 求取 $d^\prime$ 维空间的内积矩阵 $\mathbf{B}$ 。

接下来对 $\mathbf{B}$ 做特征分解就可以啦， $\mathbf{B} = \mathbf{V\Lambda V^{\mathrm{T}}}$ ,其中 $\Lambda = diag(\lambda_1,\lambda_2,\cdots,\lambda_d)$ 为特征值构成的对角矩阵， $\lambda_1 \ge \lambda_2 \ge \cdots \lambda_d$ , $\mathbf{V}$ 为特征向量矩阵，假定其中有 $d^\star$ 个非零特征值，它们构成对角矩阵 $\Lambda_\star = diag(\lambda_1,\lambda_2,\cdots,\lambda_{d^\star})$ ，令 $\mathbf{V_\star}$ 表示相应的特征向量矩阵，则 $\mathbf{Z}$ 可表示为
$\mathbf{Z} = \Lambda_{\star}^{\frac{1}{2}}\mathbf{V_\star^{\mathrm{T}}} \in \mathbb{R}^{d^\star \times m}$
在现实应用中为了有效的降维，往往不需要降维后的空间距离与原空间相同，大致相近即可，此时可取 $d^{\prime}(d^{\prime} \ll d)$ 个最大特征值构成的对角矩阵 $\widetilde{\Lambda} = diag(\lambda_1,\lambda_2,\cdots,\lambda_{d^{\prime}})$ ,令 $\widetilde{\mathbf{V}}$ 表示相应的特征向量矩阵，则 $\mathbf{B}$ 可以表示为
$\mathbf{Z} = \widetilde{\Lambda}^{\frac{1}{2}}\widetilde{\mathbf{V}}^{\mathrm{T}} \in \mathbb{R}^{d^\prime \times m}$

最后编辑于：2019.11.03 00:26:56

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 226,828评论 6赞 526
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 97,669评论 3赞 412
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 174,467评论 0赞 373
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 62,238评论 1赞 306
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 71,039评论 6赞 405
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 54,561评论 1赞 319
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 42,658评论 3赞 433
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 41,806评论 0赞 285
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 48,316评论 1赞 329
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 40,293评论 3赞 353
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 42,443评论 1赞 364
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 37,998评论 5赞 355
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 43,698评论 3赞 342
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 34,097评论 0赞 25
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 35,333评论 1赞 281
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 51,012评论 3赞 385
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 47,434评论 2赞 370

机器学习

1、低维嵌入

2、多维放缩（MDS-multiple dimensional scaling）

推荐阅读更多精彩内容