『IR 信息检索入门必看』#3 向量空间模型（简明）

访问博客查看 本文 最新内容，排版更美观ヾ(•ω•`)o 如有错误欢迎指出~

IR 信息检索系列笔记：

回忆前两个模型，我们发现统计语言模型在布尔模型上，做出了最佳匹配和排序结果的改进。但是，仍然没有考虑到「词项的权重」。

在向量空间模型中，我们容易联想到用向量来表示文档和查询，再通过计算余弦来得到两个向量的距离，从而得到相似性度量。

那么，如何选取向量空间 basis vector (基向量)？如何将目标转化为向量？如何为各个维度选取 magnitide (幅值)，从而考虑权重？如何在高维空间计算向量距离？

向量空间模型 | Vector Space Model

通常地，我们选择用 linearly independent (线性独立) 或 orthogonal (正交) 的基向量来张成向量空间，这样可以使得维度最少。那么，如何选取基向量？

这是一个特征选择问题，在 IR 中，通常有两种方式：

  1. Core concept (核心概念) 的思想：把词语的类型分类，按照其在不同分类上的「倾斜程度」决定向量的值，可以使维度尽量少。但是，由于语义上的多样性，很难实现。目前有 WordNet, HowNet, HNC 等模型。

  2. 把出现过的 term 都当作是一个基向量，并假设所有的基向量都是相互正交、相互独立的。这样将会得到一个维度不断增长的向量空间（随着词典表扩大）。

以下我们采用第二种方式。一个 Doc 或 Query 的向量表示就是：所有出现在文档中的 term 的向量之和。

词项权重 | Term Weighting

当一个 term 在文档中不断出现时，在这个方向上的向量幅值就会很大。这样比起布尔模型的 0/1 二值，更能反映了这个 term 的重要性。这便是决定权重的 tf (term frequency，词项频率) 方法。

然而，原始的 tf 值会面临这样一个严重的问题：即在和查询进行相关度计算时，所有 term 都被认为是同等重要的。

实际上，某些 term 对于相关度计算来说几乎没有或很少有区分能力。一个很直接的想法就是给包含在较多文档中的词项赋予较低的权重。为此，引入变量 df (document frequency，文档集频率)，即有多少文档包含了该 term。df 值越大，说明该 term 越不重要。

为了计算的方便，将其标准化得到 idf (inverse document frequency，逆文档频率)：

idf_t=\log \left( \frac{N}{df_t} \right)
观察该式发现，idf 虽然可以使得在较多文档中的词项权值降低，但与 tf 相反的是，这样做的缺点是：对那些极少出现的词极度敏感。

为此，我们将二者结合在一起，诞生了 tf·idf 方法——在文本处理领域中使用最广泛的数值权重计算方法。方法基于的思想和构造的统计量都很简单，但是在实际中却表现了很好的性能。

在 VSM 中，我们会将词项的 tf·idf 存储在词典表（词项-文档）矩阵中，作为向量的幅值，用于后续的计算。

相似度计算 | Similarity

当我们已经把文档表示成 R^{v} 上的向量，从而可以计算文档与文档之间的相似度（根据向量内积或者余弦夹角）。

设 D_1 和 D_2 表示 VSM 中的两个向量：
\begin{aligned} &D_{1}=D_{1}\left(w_{11}, w_{12}, \ldots, w_{1 n}\right) \\ &D_{2}=D_{2}\left(w_{21}, w_{22}, \ldots, w_{2 n}\right) \end{aligned}
可以借助于 N 维空间中两个向量之间的某种距离来表示文档之间的相似度，常用的方法是使用向量之间的內积来计算：
\operatorname{Sim}\left(D_{1}, D_{2}\right)=\sum_{k=1}^{n} w_{1 k} \times w_{2 k}
考虑到向量的归一化，则可以使用两个向量的余弦值来表示相似系数：
\operatorname{Sim}\left(D_{1}, D_{2}\right)=\cos \theta=\frac{\sum_{k=1}^{n} w_{1 k} \times w_{2 k}}{\sqrt{\sum_{k=1}^{n} w_{1 k}^{2} \sum_{k=1}^{n} w_{2 k}^{2}}}
要注意，这里使用向量内积，是基于对所有向量相互独立、相互正交的假设，否则计算内积也就失去了意义。对于相关的基向量，应该评估 Term 之间的相关度 T_{i,j}，再把向量当成多项式计算，最后代入 T_{i,j}。

此外，在其他的考虑权重的模型中，如 Lucene，在计算相似度时引入了更多的因子，如 tf·idf，boost_t，overlap(q,d) 等，对应用情形、平滑度加以考量。

VSM 实际应用

在 IR 中应用 VSM 模型时，相似度在检索结果中有两种体现：

  1. Threshold (阈值)：对于每个查询，只在相似度大于一定阈值的文档中检索，如 Sim > 0.50 的文档中，减少查询范围。
  2. Ranking：对于每个查询，返回相似度排名 Top n 的文档，以相似度排序。

而 VSM 模型也有着致命的缺点：

  • 对于大的文档集（10w+ term），向量维度太多导致难以存储和计算。

  • 一篇文档的词数（1k+ term）远低于总的词数——高维稀疏矩阵。

  • 词项之间的相关性，导致了大量冗余的基向量。

潜层语义索引 | Latent Semantic Indexing

潜层语义索引，也被称为 LSA (Latent Semantic Analysis，潜在语义分析)，是针对向量空间的「高维稀疏」问题提出的解决方法，利用线性代数中的奇异值分解降低维度（去除噪音），同时尽量减少信息的损失。

奇异值分解 | Singular Value Decomposition

参考：https://www.cnblogs.com/pinard/p/6251584.html

对于一个 t\times d 矩阵 A，可以分解为下面三个矩阵：
A_{t\times d}=U_{t\times t}\varSigma _{t\times d}V^T_{d\times d}
其中 U 和 V 都是酉矩阵，即满足 U^TU=I, V^TV=I。\varSigma 一个 t\times d 矩阵，除了主对角线上的元素以外全为 0，主对角线上的每个元素都称为奇异值。

利用酉矩阵性质得：
A=U\Sigma V^T \Rightarrow A^T=V\Sigma^T U^T \Rightarrow A^TA = V\Sigma^T U^TU\Sigma V^T = V\Sigma^2V^T
可以看出 A^TA 的特征向量组成的矩阵，就是我们 SVD 中的 V^T_{d\times d} 矩阵。进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方。

利用以上原理，我们可以得出 SVD 分解步骤：

  1. 假设词典矩阵为 A，首先求出 AA^T，会得到一个 t\times t 的方阵。
  2. 既然是方阵，就可以进行特征值分解，得到 t 个特征值和对应的特征向量。
  3. 将特征值按方差大小排序，用所有的列向量张成一个 t\times t 的矩阵 U_{t\times t}。
  4. 同理可以用 A^TA 求出 d\times d 的矩阵 V^T_{d\times d}。
  5. 利用前面求出的特征值，开方后得到 \varSigma _{t\times d}。

利用 SVD 降维

对于奇异值，它跟我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列。通常，奇异值的衰减得特别快，在很多情况下，前 10% 甚至 1% 的奇异值之和就占了全部的奇异值之和的 99% 以上的比例。

也就是说，我们也可以用最大的 k 个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说：
A_{t\times d}=U_{t\times t}\varSigma _{t\times d}V^T_{d\times d}\approx U_{t\times k}\varSigma _{k\times k}V^T_{k\times d}
其中 k 要比 t 小很多，也就是一个大的矩阵可以用三个小的矩阵，此时存储空间可以大量节省。通常 k 的值即为我们假设的主题数。

SVD 分解后，U_{il} 对应第 i 个词和第 l 个词义的相关度。V_{jm} 对应第 j 个文档和第 m 个主题的相关度。\Sigma_{lm} 对应第 l 个词义和第 m 个主题的相关度。

这样我们通过一次 SVD，就可以得到词和词义的相关度，词义和主题的相关度，以及文档和主题的相关度。

LSI 的使用

通过计算后，我们关注新的矩阵 V^T_{k\times d} ，所有的文档已经简化成了和 k 个主题的相关度。假设此时的查询为 Q=q_1q_2\cdots q_t，其中 q 取 0 或 1，则
Q_{1\times k}=Q_{1\times t}U_{t\times k}\varSigma _{k\times k}
可将 t 维的查询转化成 k 维的「与主题的相关度」，此时就可以与文档进行相似度计算了。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,456评论 5赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,370评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,337评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,583评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,596评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,572评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,936评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,595评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,850评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,601评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,685评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,371评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,951评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,934评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,167评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 43,636评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,411评论 2赞 342

推荐阅读更多精彩内容