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

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,\epsilon) $表示。
其中,$d$ 为向量维度,$\epsilon$为不同索引向量元素数量参数。对于所有文本来说,它们向量空间中出现的 -1 与 +1 的数量是相同的,在 $d$ 确定后由 $\epsilon$ 决定它们出现的数量。
令文本集全集为 $W$,文本集的子集(单词)为$\omega _j \in W,j \in {1,2,3,…,n} $,此时生成的随机索引向量为 $ R_{\nu_j} = (r\nu_1^j,r\nu_2^j,r\nu_3^j,…,r\nu_d^j ) $,其中 $r\nu_{h^j} \in {+1,-1,0}, h \in {1,2,3,…,d}$。$\epsilon$的取值远小于$d$。总体来说,+1 与 -1 分别占随机索引向量总维度的概率为 $\frac{\epsilon /2}{d}$,显然有

第二步:生成文本向量

根据滑动窗口包含的上下文生成上下文向量,接着根据上下文向量计算文本向量。
在论文 2 中,这一步又分为了两步:

生成特征词汇的上下文向量

设滑动窗口大小为 2L,则窗口范围为 [-L, L]。记特征词 $\omega_j$ 在文本 $d_i$ 中的上下文向量为 $c^i_j$,则其表达式为:

其中 $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})$ 的表达式:

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

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

生成文本向量

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

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

  • 生成文档 $d_i$ 的文本向量

Result

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

Advantages

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

Disadvantages

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

总结

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