线性投影可视化用于信息检索及相关实验分析

### 线性投影可视化用于信息检索及相关实验分析 在数据可视化和信息检索领域，有许多方法被提出来处理不同类型的数据和满足不同的需求。今天我们要介绍一种新的方法——线性邻域检索可视化器（LINNEA），它通过线性或基于核的投影进行可视化，在信息检索方面有着独特的优势。 #### 1. 基本概念与评估指标 在开始介绍LINNEA之前，我们需要了解一些基本概念。在数据可视化中，我们通常会关注数据点之间的邻域关系。这里引入了概率分布 \(p_{i,j}\) 和 \(q_{i,j}\)，其中 \(σ_i\) 是尺度参数，可以通过固定 \(p_{i,j}\) 的熵来设置。由于 \(p_{i,j}\) 和 \(q_{i,j}\) 是概率分布，我们自然会使用Kullback - Leibler散度来衡量检索到的分布与输入邻域的匹配程度。 - **Kullback - Leibler散度**： - \(D_{KL}(p_i, q_i) = \sum_{j\neq i} p_{i,j} \log(p_{i,j}/q_{i,j})\) 是召回率的推广。 - \(D_{KL}(q_i, p_i)\) 是精确率的推广。 - 最终的评估指标是将这些散度值在所有点 \(i\) 上取平均值。 #### 2. LINNEA方法 精确率和召回率的推广可以直接用作优化目标，但通常情况下，两者不能同时最大化，因此用户需要在它们之间进行权衡。基于这个权衡，可以定义一个单一的成本函数，并直接根据该成本函数优化可视化效果。 ##### 2.1 线性投影形式 LINNEA采用参数化的线性投影 \(y_i = Wx_i\)，其中 \(W \in R^{d\times d_0}\) 是投影矩阵。我们的目标是优化 \(W\)，使投影在可视化的信息检索任务中表现良好。 - **成本函数**： \[ E = \lambda \sum_{i} D_{KL}(p_i, q_i) + (1 - \lambda) \sum_{i} D_{KL}(q_i, p_i) = \sum_{i} \sum_{j\neq i} \left[ -\lambda p_{i,j} \log q_{i,j} + (1 - \lambda) q_{i,j} \log \frac{q_{i,j}}{p_{i,j}} \right] + const. \] 其中，权衡参数 \(\lambda\) 由用户设置，以反映精确率和召回率哪个更重要。 - **优化方法**： 我们使用共轭梯度算法来最小化 \(E\) 关于矩阵 \(W\) 的值。梯度 \(\frac{\partial E}{\partial W}\) 为： \[ \sum_{i,j\neq i} \left[ \lambda(p_{i,j} - q_{i,j}) + (1 - \lambda) q_{i,j} \left( D_{KL}(q_i, p_i) - \log \frac{q_{i,j}}{p_{i,j}} \right) \right] \frac{(y_i - y_j)(x_i - x_j)^T}{\sigma_i^2} \] 每个梯度步骤的计算复杂度为 \(O(N^2)\)。 - **优化细节**： - **初始化**：在本文中，我们简单地将 \(W\) 的元素初始化为 0 到 1 之间的均匀随机数。当然，也可以采用更复杂的初始化方法，例如将 \(W\) 初始化为主成分分析投影。 - **避免局部最优**： - 每次运行时，首先将邻域尺度设置为较大的值，然后在每个优化步骤后减小它们，直到达到最终尺度，之后使用最终尺度运行 40 个共轭梯度步骤。 - 从 10 个随机初始化点运行算法，并选择成本函数值最优的结果。 ##### 2.2 核版本 除