随机索引算法论文笔记 An Introduction to Random Indexing

Posted on In

Sahlgren M. An Introduction to Random Indexing[C]// Methods & Applications of Semantic Indexing Workshop at International Conference on Terminology & Knowledge Engineering. 2005:194–201.

论文信息

文章作者为 Sahlgren M

论文概述

本文主要内容分为了 4 段，分别为：

  • The word space methodology
  • Problems and solutions
  • Random Indexing
  • Results

文章从文本空间讲起，简述了使用向量表示词的作用。接着以 LSA 加上 SVD 降维为例，简单说明了传统词向量表示算法的一些局限性（向量维度依然过大，计算代价大等），引出了 Random Indexing 算法。

Random Indexing

文中描述： • First, each context (e.g. each document or each word) in the data is assigned a unique and randomly generated representation called an index vector. These index vectors are sparse, high-dimensional, and ternary, which means that their dimensionality (d) is on the order of thousands, and that they consist of a small number of randomly distributed +1s and -1s, with the rest of the elements of the vectors set to 0. • Then, context vectors are produced by scanning through the text, and each time a word occurs in a context (e.g. in a document, or within a sliding context window), that context's d-dimensional index vector is added to the context vector for the word in question. Words are thus represented by d-dimensional context vectors that are effectively the sum of the words' contexts.

结合下面的论文提到的解释理解 Random Indexing algorithm。

论文 2 -- 熊玮, 白越, 刘爱国,等. 基于改进RI方法的文本聚类[J]. 南昌大学学报(理科版), 2016, 40(5):426-430.

第一步：生成随机索引向量

为正文、单词生成随机索引向量。这些随机索引向量是稀疏、高维的。随机索引向量的值可以为 (-1, +1, 0) 三种。大多数的向量值都为 0，只有少数向量值为 -1 和 +1。在论文 2 中提到随机索引向量可以使用二元组 $ (d,) \(表示。 其中，\)d$ 为向量维度，\(\epsilon\)为不同索引向量元素数量参数。对于所有文本来说，它们向量空间中出现的 -1 与 +1 的数量是相同的，在 \(d\) 确定后由 \(\epsilon\) 决定它们出现的数量。 令文本集全集为 \(W\)，文本集的子集（单词）为$j W,j {1,2,3,...,n} $，此时生成的随机索引向量为 $ R{_j} = (r_1^j,r_2^j,r_3^j,...,r_d^j ) $，其中 \(r\nu_{h^j} \in \{+1,-1,0\}, h \in \{1,2,3,...,d\}\)。\(\epsilon\)的取值远小于\(d\)。总体来说，+1 与 -1 分别占随机索引向量总维度的概率为 \(\frac{\epsilon /2}{d}\)，显然有 \[\frac{\epsilon /2}{d} + \frac{d - \epsilon}{d} + \frac{\epsilon /2}{d} = 1\]

第二步：生成文本向量

根据滑动窗口包含的上下文生成上下文向量，接着根据上下文向量计算文本向量。 在论文 2 中，这一步又分为了两步： #### 生成特征词汇的上下文向量 设滑动窗口大小为 2L，则窗口范围为 [-L, L]。记特征词 \(\omega_j\) 在文本 \(d_i\) 中的上下文向量为 \(c^i_j\)，则其表达式为：

\[c^i_j = \sum^{k = L}_{k = -L}Rv_{j+k} * \omega f(\omega_{j+k})\]

其中 \(Rv_{j+k}\) 表示特征词 \(\omega_j\) 在窗口范围内共现词 \(\omega_{j+k}\) 对应的随机索引向量； \(\omega f(\omega_{j+k})\) 为特征词 \(\omega_j\) 在窗口范围上下文中共现特征词 \(\omega_{j+k}\) 在文本 \(d_i\) 中的加权权重。论文 2 中采用了 tf-idf 加权计算算法。论文 2 此时引用了 > Gorman J, Curran J R. Random Indexing using Statistical Weight Functions[C]// EMNLP 2007, Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, 22-23 July 2006, Sydney, Australia. DBLP, 2006:457-464.

根据 tf-idf 加权算法，可以得到 \(\omega f(\omega_{j+k})\) 的表达式：

\[\omega f(\omega_{j+k}) = \frac{f(\omega,\omega')}{n(\omega')} = \frac{n(\omega,\omega')}{n(\omega) * n(\omega')}\]

其中 \(n(\omega)\) 表示特征词汇 \(\omega\) 在上下文中出现的数量，\(n(\omega,\omega')\) 表示上下文中 \(\omega\) 与 \(\omega'\) 共同出现的数量。

最终，某个特征词汇 \(\omega_j\) 在滑动窗口上下文中的上下文向量表示为

\[ C_j = \sum^{n}_{i=1} c^i_j\]

生成文本向量

  • 计算文本集中所有特征词汇上下文向量的平均值

\[\tau = \frac{\sum^n_{i=1}\sum^{z_i}_{j=1}Cj}{m}\]

其中 \(z_i\) 表示文档 \(d_i\) 中特征词汇总数，m 表示文 本集中所有不同特征词汇的总数量，n 表示文本集的文本总数量。

  • 生成文档 \(d_i\) 的文本向量

\[V_i =\frac{\sum^{z_i}_{j=1}C_j}{z_i} - \tau\]

Result

文章最后总结了一些经典数据集与实验应用 RI 算法之后准确率大多有所上升。论文 2 中最终总结了 RI 算法的优缺点。

Advantages

  • 计算量小
  • 容易实现
  • 处理效率高
  • 潜在语义表现好，利用了上下文信息表示特征词的词向量，容易解决同义词、近义词等问题
  • 降维性能好

Disadvantages

  • 随机向量元素 (-1, +1, 0) 的随机性可能导致在计算特征词上下文向量时发生相加消减的情况，导致潜在语义信息丢失
  • 论文 2 中选用的 tf-idf 计算出的加权值过小（此条仅对全文特征向量计算而言）

总结

了解了 Random Indexing algorithm 的基本原理及应用。之后有精力希望能将 RI 算法的代码实现，并将其与其它词向量表示算法进行对比。