IR学习笔记 #03 向量空间模型
本文最后更新于：2022年11月28日 下午
回忆前两个模型，我们发现统计语言模型在布尔模型上，做出了最佳匹配和排序结果的改进。但是，仍然没有考虑到「词项的权重」。
在向量空间模型中，我们容易联想到用向量来表示文档和查询，再通过计算余弦来得到两个向量的距离，从而得到相似性度量。
那么，如何选取向量空间 basis vector (基向量)？如何将目标转化为向量？如何为各个维度选取 magnitide (幅值)，从而考虑权重？如何在高维空间计算向量距离？
向量空间模型 | Vector Space Model
通常地，我们选择用 linearly independent (线性独立) 或 orthogonal (正交) 的基向量来张成向量空间，这样可以使得维度最少。那么，如何选取基向量？
这是一个特征选择问题，在 IR 中，通常有两种方式：
Core concept (核心概念) 的思想：把词语的类型分类，按照其在不同分类上的「倾斜程度」决定向量的值，可以使维度尽量少。但是，由于语义上的多样性，很难实现。目前有 WordNet, HowNet, HNC 等模型。
把出现过的 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 模型时，相似度在检索结果中有两种体现：
- Threshold (阈值)：对于每个查询，只在相似度大于一定阈值的文档中检索，如 Sim > 0.50 的文档中，减少查询范围。
- 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 分解步骤：
- 假设词典矩阵为 \(A\)，首先求出 \(AA^T\)，会得到一个 \(t\times t\) 的方阵。
- 既然是方阵，就可以进行特征值分解，得到 t 个特征值和对应的特征向量。
- 将特征值按方差大小排序，用所有的列向量张成一个 \(t\times t\) 的矩阵 \(U_{t\times t}\)。
- 同理可以用 \(A^TA\) 求出 \(d\times d\) 的矩阵 \(V^T_{d\times d}\)。
- 利用前面求出的特征值，开方后得到 \(\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 维的「与主题的相关度」，此时就可以与文档进行相似度计算了。