Barnes-Hut 模式下的梯度与成本(KL 散度)计算
BarnesHutGradient
00 Remarks
t-SNE 的梯度可以拆成吸引(正)与排斥(负)两个部分:
dC/dy_i = 4 [ sum_j p_ij qu_ij (y_i - y_j) - (1/Z) sum_j qu_ij^2 * (y_i - y_j) ]
其中 qu_ij = 1 / (1 + ||y_i - y_j||^2),Z = sum_{k != l} qu_kl。
第一部分只涉及稀疏概率矩阵中的 O(N·k) 个近邻对,直接按行遍历即可; 第二部分涉及全部 N² 个点对,改用 SPTree 做远场近似。
并行策略: 1) 远场斥力按点分派,每个点只写自己的 negF 行,无写冲突;配分函数 Z 用线程本地累加器归约。 2) 近场引力按行分派,CSR 格式保证第 i 行的条目连续且与其他行不重叠,同样无写冲突; KL 成本用线程本地累加器归约。
01 Syntax
Microsoft.VisualBasic.MachineLearning.tSNE.BarnesHutGradient
02 Methods
| Name | Overloads | Summary |
|---|---|---|
| Evaluate | 1 | 计算 Barnes-Hut 近似梯度与 KL 成本,结果写入 tSNE.mGrad 与 tSNE.mCost |
03 Members
Evaluate(tSNE,
Double())计算 Barnes-Hut 近似梯度与 KL 成本,结果写入 tSNE.mGrad 与 tSNE.mCost
Parameters
| Name | Type | Description |
|---|---|---|
tSNE | tSNE | - |
Y | Double() | 当前的低维嵌入,行主序一维数组,长度为 N * dim |