Visualizing Data using t-SNE
概
t-sne是一个非常经典的可视化方法.
主要内容
我们希望, 将高维数据\(\mathcal{X}=\{x_1,x_2,\ldots,x_n\}\)映射到一个低维空间\(\mathcal{Y}=\{y_1,y_2,\ldots, y_n\}\), 同时保留相关性(这里的相关性就不局限于PCA在意的线性相关性了).
Stochastic Neighbor Embedding
利用核密度估计, 估计原空间中各点条件概率:
p_{j|i} = \frac{\exp(-\|x_i-x_j\|^2/2\sigma_i^2)}{\sum_{k\not=i}\exp(-\|x_i-x_k\|^2/2\sigma_i^2)},
\]
显然\(p_{j|i}\)衡量了俩个点的一个相关关系.
而在低维空间中, 我们用类似的方法估计:
q_{j|i} = \frac{\exp(-\|y_i-y_j\|^2)}{\sum_{k\not=i} \exp(-\|y_i-y_k\|^2)}.
\]
一个很自然的问题是, (1)有\(\sigma\)为什么(2)没有, 这是因为\(y\)是\(x\)的一个映射, 你加个\(\sigma\)也就是rescale一下这个映射而已(应该是在低维取相同的\(\sigma\)的情况下).
另外一个问题是, \(\sigma\)是如何估计的, 对于每个\(\sigma_i\), 都有一组概率\(P_i\), 定义一个perplexity:
Perp(P_i)=2^{H(P_i)},
\]
其中\(H(P_i)\)表示香农熵. 根据(4)利用二分法搜索, 通常选择5-50. (why?)
实际上, 我们还没有找到\(y\), 为了保证映射前后相关性一致, 利用KL-散度(非对称)来度量
C=\sum_i KL(P_i\|Q_i) = \sum_i \sum_j p_{j|i} \log \frac{p_{j|i}}{q_{j|i}}.
\]
需要注意的是, 因为考虑的是俩俩的相关性, 所以假设\(p_{i|i}=q_{i|i}=0\), 说实话感觉好扯啊, 为啥不假设为1(因为概率和为1, 公式不好调整?).
显然(3)是关于\((y_1,\ldots,y_n)\)的一个函数, 可以用梯度下降方法去最小化使得分布近似, 梯度为
\frac{\delta C}{\delta y_i} = 2\sum_j (p_{j|i}-q_{j|i} + p_{i|j}-q_{i|j})(y_i-y_j).
\]
说实话, 我证明的结果有出入因为\(\sum_{i}p_{j|i}\)好像不等于1吧.
最后迭代公式用了momentum
\mathcal{Y}^{(t)}=\mathcal{Y}^{(t)} + \eta \frac{\delta C}{\delta \mathcal{y}} +\alpha (t) (\mathcal{Y}^{(t-1)} - \mathcal{Y}^{(t-2)}).
\]
t-SNE
由于crowding problem (好像是指高维数据映射到低维数据发生重叠). 为了解决这种问题, 作者采用了俩个处理, 第一, 在联合分布上求解
\]
其中(为了保证\(p_{ij}\)不会太小)
\]
或者像公式(10)中的那样根据对称SNE的估计?
q_{ij} = \frac{(1+\|y_i-y_j\|^2)^{-1}}{\sum_{k\not= l} (1+\|y_k-y_l\|^2)^{-1}}.
\]
\(q\)采取这种估计方式(单自由度t分布而非高斯形式), 论文的解释是t分布的拖尾效果比高斯的强, 这会导致高维空间中距离较大的点在低维空间中的映射也会保持一个较大的距离, 从而能够缓解 crowding problem.
此时的梯度为
\frac{\delta C}{\delta y_i} = 4\sum_{j} (p_{ij}-q_{ij})(y_{i}-y_j)(1+\|y_i-y_j\|^2)^{-1}.
\]
只需要考虑\(-\sum_{ij}p_{ij}\log q_{ij}\)关于\(y_c\)的导数即可,
\]
其中
\]
\]
可以综合为
\]
和
\]
在结合最开始有一个\(-\)就可以得到最后的结果了.
最新文章
- Windows下为MySQL做定时备份
- Clion cmake 一个简单的 C++ 程序
- Jquery获取iframe子/父窗口中的标签
- 常州培训 day2 解题报告
- 【转】PLSQL developer 连接不上64位Oracle 的解决方法
- codeforces 675A A. Infinite Sequence(水题)
- hdu 4474 Yet Another Multiple Problem
- 记录使用Hibernate查询bean中字段和数据库列类型不匹配问题
- 谁在唱衰PC?说出你的理由
- Dell-R730 【Pxe+dhcp+ftp+tftp+Kickstart+CentOs6.6】
- python基础(7)-函数&;命名空间&;作用域&;闭包
- MYSQL增加tmp_table_size 的操作
- POJ 3660 Cow Contest. (传递闭包)【Floyd】
- [LintCode/LeetCode]——两数和、三数和、四数和
- BZOJ 1444 [Jsoi2009]有趣的游戏 (AC自动机 + 概率DP + Gauss)
- ASP.NET MVC:模块化/插件式架构实现(转载)
- 4G厂商版《出师表》
- css实现椭圆
- FD.io社区中国行暨未来网络技术沙龙·南京站 会议小结
- Elasticsearch 数据搜索篇