# Rag 信息检索理论



## 1. 检索核心技术
现代检索系统主要采用两种搜索技术
1. 语义搜索(Semantic Search): 通过理解文档含义进行匹配
2. 关键词搜索(Keyword Search)

![Search Techniques](/images/rag/search.png)

搜索过程:
1. 两种搜索会返回一定数量的关联文档
2. 这些文档经过元数据过滤后合并，并排序

### 1.1 元数据过滤
通过文档元数据进行过滤，元数据包括:
1. 文档标题
2. 作者
3. 创建时间
4. 权限等

## 2. 关键词搜索
关键词搜索的最大优点是简单直接。缺点有很明显，其要求文档与关键词完全匹配，忽略了近义词；并且也忽略了文档的上下文信息。

关键词搜索中有两种常见的衡量关键词与文档相关性的算法:
1. TF-IDF
2. BM25


### 2.1 TF-IDF

TF-IDF 是信息检索和文本挖掘中非常常见的一种 **关键词加权方法**。用来衡量一个词语对于某个文档的重要性。

直觉上：

* 如果一个词在某篇文档中出现得多（高 **TF**），说明它和该文档关系大。
* 但如果这个词在所有文档里都很常见（低 **IDF**，比如“的”、“是”、“and”），它的区分度就低。

所以 TF-IDF 结合这两点来权衡词的重要性。

---

#### 公式

对于一个词 $t$，在文档 $d$ 里的权重：

$$
\text{TF-IDF}(t, d) = \text{TF}(t, d) \times \text{IDF}(t)
$$

* **TF (Term Frequency)** 词频
  表示词 $t$ 在文档 $d$ 中出现的次数（有时会归一化）。

  $$
  \text{TF}(t, d) = \frac{\text{词 } t \text{ 在 } d \text{ 中出现的次数}}{\text{文档 } d \text{ 的总词数}}
  $$

* **IDF (Inverse Document Frequency)** 逆文档频率
  表示某个词的普遍程度，越常见的词权重越低。

  $$
  \text{IDF}(t) = \log \frac{N}{1 + \text{DF}(t)}
  $$

  其中：

  * $N$ = 语料库中文档总数
  * $\text{DF}(t)$ = 包含词 $t$ 的文档数
  * 分母加 1 是为了避免除零。

#### 举例

假设有 3 篇文档：

* d1: "我 爱 北京 天安门"
* d2: "北京 是 中国 的 首都"
* d3: "我 在 中国 生活"

统计一下：

* 词 “北京” 在 d1 和 d2 出现过 → DF(北京)=2
* 词 “天安门” 只在 d1 出现过 → DF(天安门)=1

如果总文档数 N=3：

* IDF(北京) = log(3 / (1+2)) = log(1) = 0
* IDF(天安门) = log(3 / (1+1)) = log(1.5) ≈ 0.405

所以在 d1 里：

* TF(北京, d1) = 1/5 = 0.2，TF-IDF=0.2 \* 0 = 0
* TF(天安门, d1) = 1/5 = 0.2，TF-IDF=0.2 \* 0.405 ≈ 0.081

结论：
虽然“北京”出现了，但因为太常见（几乎所有文档都有），它的重要性就低；“天安门”稀有，所以更能代表 d1。

---


### 2.2 BM25
**BM25** 是 **TF-IDF 的改进版**。

BM25（Best Matching 25）是一种 **基于概率检索模型的文档相关性排序算法**。
它的目标是：给定一个查询词（query），衡量某篇文档与这个查询的匹配程度。

相比 TF-IDF：

* **TF-IDF** 直接用词频和逆文档频率相乘，没考虑文档长度问题。
* **BM25** 在 TF 和文档长度上做了更精细的归一化，因此在实际搜索引擎里效果更好。

---

#### 公式

对于查询 $Q$ 和文档 $D$，BM25 的得分为：

$$
\text{score}(D, Q) = \sum_{t \in Q} IDF(t) \cdot \frac{f(t, D) \cdot (k_1 + 1)}{f(t, D) + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)}
$$

其中：

* $t$：查询中的一个词
* $f(t, D)$：词 $t$ 在文档 $D$ 中的词频（term frequency）
* $|D|$：文档 $D$ 的长度（词数总数）
* $\text{avgdl}$：整个语料库的平均文档长度
* $k_1$：调节 TF 饱和度（常取 1.2 \~ 2.0）
* $b$：调节文档长度的影响（常取 0.75）
* $IDF(t)$：逆文档频率，常见定义为：

$$
IDF(t) = \log \frac{N - n_t + 0.5}{n_t + 0.5}
$$

* $N$：语料库中文档总数
* $n_t$：包含词 $t$ 的文档数

---

#### 与 TF-IDF 的对比

| 特性     | TF-IDF              | BM25                                       |
| ------ | ------------------- | ------------------------------------------ |
| TF 部分  | 词频线性增长              | 引入 $k_1$，避免过高词频无限放大（词频饱和处理）                  |
| 文档长度   | 未考虑                 | 引入 $b$，对长文档进行长度归一化                         |
| IDF 公式 | $\log \frac{N}{df}$ | $\log \frac{N - n_t + 0.5}{n_t + 0.5}$，更平滑 |
| 效果     | 基础但易过拟合             | 在搜索引擎中更准确、鲁棒性更强                            |

简言之：**BM25 是 TF-IDF 的升级版，更贴近实际语料分布。**

---

#### 举个例子

假设语料库有 1000 篇文档，查询是 `"北京 天安门"`：

* 文档 d1: `"我 爱 北京 天安门"`（短文档，两个词都出现）
* 文档 d2: `"北京 是 中国 的 首都"`（中等长度，只有一个词匹配）
* 文档 d3: `"我 在 中国 生活"`（没有匹配词）

BM25 会计算：

* d1 得分最高，因为匹配了两个词，且文档很短（短文档倾向于更相关）。
* d2 次之，因为只匹配了一个词。
* d3 得分为 0。

这就比 TF-IDF 更符合直觉。

---

#### 应用场景

* **Elasticsearch / OpenSearch / Lucene** 的默认文档排序算法就是 BM25。
* 常用于 **搜索引擎、问答系统、RAG 检索**。
* 在传统 IR（信息检索）任务里是非常强大的 baseline。


## 3. 语义搜索
语义搜索通过 embedding 模型将文本转换为向量，向量表示多维空间中词的位置，相似的词位置相近。

计算向量间的距离有多种方法:
1. 余弦相似度


### 3.1 余弦相似度（Cosine Similarity）

**定义**：
衡量两个向量夹角的余弦值，取值范围 $[-1, 1]$，值越大表示越相似。

$$
\text{cosine}(x, y) = \frac{x \cdot y}{\|x\| \cdot \|y\|}
$$

其中：

* $x \cdot y$：向量点积
* $\|x\|$、$\|y\|$：向量的模

**特点**：

* 只关心方向，不关心长度。
* 在文本处理中常用，因为我们关心的是词频分布的相似性，而不是绝对大小。

**例子**：

* 向量 $x=(1,2)$，$y=(2,4)$，虽然长度不同，但方向一样，余弦相似度=1（完全相似）。

---


### 3.2 嵌入模型实现原理
正向文本对，负向文本对，对比训练

## 4. 混合搜索
在信息检索（IR）或推荐系统中，我们经常会有多个不同的检索器 / 模型，它们各自会给查询返回一个排名列表（ranked list）。
但是不同模型的表现往往各有优缺点 —— 有的更擅长语义匹配，有的更擅长关键词精确匹配。
这时候我们需要一个方法 **把多个排名结果融合在一起**，得到一个综合排序，往往比单一模型更鲁棒。

混合搜索的核心是如何将不同搜索方式的结果进行融合，融合的核心有两个:
1. 融合算法选择，常见的是 RRF(倒数排名融合)
2. 融合权重设置

### 4.1 Reciprocal Rank Fusion
RRF 就是其中一种经典的、非常简单且有效的融合方法。


---

#### 算法原理

假设我们有多个检索器（系统） $S_1, S_2, \dots, S_k$，每个检索器都会返回一个排序列表。
RRF 的思路是：

* 如果某个文档在某个系统里排得靠前，它就应该得到更高的融合分数。
* 但是为了避免前几名被无限放大，采用了 **倒数函数** 来衰减排名分数。

公式如下：

$$
\text{RRF}(d) = \sum_{i=1}^k \frac{1}{k + \text{rank}_i(d)}
$$

其中：

* $\text{rank}_i(d)$ = 文档 $d$ 在系统 $i$ 中的排名（第 1 名就是 1）。
* $k$ = 一个平滑常数（常用 60），避免分母过小导致极端放大。
* 分数越高，最终排名越靠前。

---

#### 举个例子

假设我们有两个系统返回的前 5 名：

* 系统 A：

1. d1
2. d2
3. d3
4. d4
5. d5

* 系统 B：

1. d3
2. d2
3. d6
4. d1
5. d7

设 $k=60$，那么计算：

* d1: $\frac{1}{60+1} + \frac{1}{60+4}$
* d2: $\frac{1}{60+2} + \frac{1}{60+2}$
* d3: $\frac{1}{60+3} + \frac{1}{60+1}$
* d4: $\frac{1}{60+4}$
* d5: $\frac{1}{60+5}$
* d6: $\frac{1}{60+3}$
* d7: $\frac{1}{60+5}$

最终分数最高的可能是 d2 或 d3，因为它们在两个系统中都靠前。

---

#### 特点

* **优点**

  * 简单（不需要训练，不依赖参数调优，直接计算即可）。
  * 鲁棒（只要一个系统给某文档高排名，RRF 就会给它一定加权）。
  * 在 TREC 等信息检索评测中表现很好。
* **缺点**

  * 没有考虑文档的实际分数（**仅仅基于排名位置**）。
  * 融合后的效果依赖于候选系统的互补性。

---

#### 应用场景

* 多检索器结果融合（如 BM25 + 向量搜索）。
* 多模型结果合并（如不同 embedding 模型的 ANN 检索结果）。
* 搜索引擎、推荐系统中增强鲁棒性的方法。


## 5. 检索器质量评估
最常用的检索器质量指标有:
1. 准确率(Accuracy)
2. 召回率(Recall)
3. 平均准确率(Mean Average Precision)
4. 倒数排名(Reciprocal Rank)


好的 👍 我来帮你解释一下 **准确率（Accuracy）** 和 **召回率（Recall）**，它们都是常用的机器学习和信息检索评估指标，但关注点不一样。

---

### 5.1 准确率（Accuracy）

* **定义**：预测对的样本数 / 总样本数。
* 公式：

$$
\text{Accuracy} = \frac{TP + TN}{TP + TN + FP + FN}
$$

其中：

* **TP (True Positive)**：预测为正，实际也为正

* **TN (True Negative)**：预测为负，实际也为负

* **FP (False Positive)**：预测为正，但实际为负

* **FN (False Negative)**：预测为负，但实际为正

* **直观理解**：模型整体上有多少比例预测正确。

* **适用场景**：正负样本比较均衡时，Accuracy 很有意义。

* **问题**：如果样本极度不平衡（比如 99% 是负样本），即使模型全预测成负，Accuracy 也能很高，但没有实际价值。

---

### 5.2 召回率（Recall）

* **定义**：在所有实际为正的样本里，模型找回了多少。
* 公式：

$$
\text{Recall} = \frac{TP}{TP + FN}
$$

* **直观理解**：模型有多大能力不漏掉正样本。

* **例子**：在疾病检测中，Recall 高意味着 **几乎不会漏掉真正有病的人**。

* **适用场景**：在“不能漏”的任务中非常重要，比如医疗检测、搜索引擎召回阶段。

* **问题**：只看 Recall 可能会导致过多假阳性（FP 多）。

---


假设我们有 100 个样本，其中：

* 实际正样本 = 20
* 实际负样本 = 80

某个模型预测结果：

* TP = 15（找对了 15 个正样本）
* FN = 5（漏掉了 5 个正样本）
* FP = 10（误判了 10 个负样本为正）
* TN = 70

那么：

* Accuracy = (15 + 70) / 100 = **85%**
* Recall = 15 / (15 + 5) = **75%**

---

👉 总结：

* **Accuracy** 看整体正确率，适合样本均衡的情况。
* **Recall** 看“覆盖率”，在需要尽量不漏的场景特别重要。



好嘞 👍 我来帮你解释一下 **平均准确率（Mean Average Precision, MAP）** 和 **倒数排名（Reciprocal Rank, RR）**。

---

### 5.3 平均准确率（Mean Average Precision, MAP）

#### 背景

在 **信息检索（IR）** 和 **推荐系统** 中，我们经常关心：

* 系统返回的前几条结果里，相关文档的分布情况。
* 不仅要看相关文档有没有返回，还要看返回得是不是靠前。

MAP 就是用来衡量一个系统在多个查询上的综合表现。

---

#### 步骤解释

* **AP（Average Precision，平均精度）**：先对 **单个查询** 来计算。

  * 在检索结果中，每当遇到一个相关文档，就计算此时的 **Precision（精确率）**。
  * 把这些 Precision 取平均，就是这个查询的 AP。

  $$
  AP = \frac{1}{R} \sum_{k=1}^N P(k) \cdot rel(k)
  $$

  * $R$：该查询所有相关文档的个数
  * $P(k)$：前 k 个结果的精确率
  * $rel(k)$：第 k 个结果是否相关（1 表示相关，0 表示不相关）

* **MAP（Mean Average Precision）**：对多个查询，取 AP 的均值。

  $$
  MAP = \frac{1}{Q} \sum_{q=1}^Q AP(q)
  $$

  * $Q$：查询数

---

#### 举例

假设一个查询的返回结果前 5 个如下（R 表示相关，N 表示不相关）：

* \[R, N, R, R, N]

相关文档数 R = 3。

* 第 1 个（R）：Precision = 1/1 = 1
* 第 3 个（R）：Precision = 2/3 ≈ 0.67
* 第 4 个（R）：Precision = 3/4 = 0.75

AP = (1 + 0.67 + 0.75) / 3 ≈ **0.81**

如果有 10 个查询，MAP 就是这 10 个 AP 的平均值。

👉 MAP 越高，说明相关文档整体排序越靠前。

---

### 5.4 倒数排名（Reciprocal Rank, RR）

#### 定义

RR 衡量的是：
**第一个相关文档出现得有多靠前**。

公式：

$$
RR = \frac{1}{\text{rank}}
$$

其中 rank = 第一个相关文档在结果列表中的排名位置。

---

#### 例子

* 如果第一个相关文档在第 1 位：RR = 1/1 = 1
* 如果第一个相关文档在第 5 位：RR = 1/5 = 0.2
* 如果第一个相关文档在第 10 位：RR = 0.1

---

### 5.5 扩展：MRR（Mean Reciprocal Rank）

对多个查询，取 RR 的平均值，就是 **MRR**：

$$
MRR = \frac{1}{Q} \sum_{q=1}^Q \frac{1}{rank_q}
$$

👉 MRR 常用于 **问答系统（QA）** 或 **对话检索**，因为用户往往只关心第一个正确答案的位置。

---

* **MAP**：考虑所有相关文档的位置，衡量整体排序质量。
* **RR / MRR**：只看第一个相关文档的位置，更适合“只要找到第一个正确答案就行”的场景。

### 5.6 对比总结

好 👌 我整理了一个对比表格，把 **Accuracy / Recall / MAP / MRR** 这四个指标的定义、公式、特点和适用场景放在一起：

---

| 指标                                    | 定义                 | 公式                                           | 关注点           | 适用场景                   |
| ------------------------------------- | ------------------ | -------------------------------------------- | ------------- | ---------------------- |
| **Accuracy（准确率）**                     | 模型预测正确的比例          | $\dfrac{TP+TN}{TP+TN+FP+FN}$                 | 整体预测正确率       | 分类任务中，类别均衡时较有意义        |
| **Recall（召回率）**                       | 找回的正样本占所有正样本的比例    | $\dfrac{TP}{TP+FN}$                          | 有多少“正样本”被找回   | 医疗检测、搜索召回阶段（不能漏）       |
| **MAP（Mean Average Precision，平均准确率）** | 多个查询下，相关文档的排序质量    | $\dfrac{1}{Q}\sum_{q=1}^Q AP(q)$             | 综合考虑所有相关文档的位置 | 信息检索、推荐系统，评价整体排序效果     |
| **MRR（Mean Reciprocal Rank，平均倒数排名）**  | 多个查询下，第一个相关文档出现的位置 | $\dfrac{1}{Q}\sum_{q=1}^Q \dfrac{1}{rank_q}$ | 第一个相关结果是否靠前   | 问答系统、对话检索（用户只要第一个正确答案） |

---

👉 简单记忆：

* **Accuracy** = 看整体对不对
* **Recall** = 看正样本有没有漏
* **MAP** = 看所有相关文档排得靠不靠前
* **MRR** = 看第一个相关文档排得靠不靠前


## 6. 向量搜索算法
向量搜索方法有:
1. KNN
2. ANN

好的 👍 我来帮你解释一下 **KNN（K-Nearest Neighbors）** 和 **ANN（Approximate Nearest Neighbor）**，它们名字很像，但指代的内容和应用有点不一样。

---

### 6.1 KNN（K-Nearest Neighbors，K 最近邻算法）

* **是什么**
  一种 **监督学习算法**（分类/回归都可），也可以用作最近邻搜索。

* **思想**
  给定一个样本，找到它在特征空间里距离最近的 **K 个邻居**，然后：

  * 分类任务：看这 K 个邻居里多数的类别 → 投票决定预测类别。
  * 回归任务：取这 K 个邻居的平均值 → 作为预测值。

* **特点**

  * 简单直观，不需要训练过程（“懒惰学习”）。
  * 距离度量常用 **欧氏距离、曼哈顿距离、余弦相似度** 等。
  * 适合小规模数据，数据大时计算代价高（要计算与所有样本的距离）。

* **应用**

  * 小规模分类/回归问题。
  * 早期的推荐系统 / 文本分类任务。

---

### 6.2 ANN（Approximate Nearest Neighbor，近似最近邻搜索）

* **是什么**
  一类 **检索算法/数据结构**，目标是：在海量数据（尤其是高维向量）中，快速找到与查询向量最相似的若干个候选点。

  * 和 KNN 的“精确搜索”不同，ANN 允许一点点误差（近似），但换来速度大幅提升。

* **常见方法**

  * **树结构**：KD-Tree, Ball-Tree（低维效果好，高维退化）。
  * **哈希方法**：LSH（局部敏感哈希）。
  * **图索引**：HNSW（Hierarchical Navigable Small World，小世界图）。
  * **量化方法**：IVF+PQ（倒排文件+乘积量化，常用于向量数据库）。

* **应用**

  * 向量检索（文本向量、图像向量、音频向量）。
  * 推荐系统（Embedding 召回）。
  * 大规模检索系统（Elasticsearch、Milvus、Faiss、Weaviate 都用 ANN）。

---

| 对比项  | KNN                  | ANN                          |
| ---- | -------------------- | ---------------------------- |
| 全称   | K-Nearest Neighbors  | Approximate Nearest Neighbor |
| 本质   | 一种机器学习算法             | 一类检索/索引方法                    |
| 目的   | 分类或回归（预测标签/数值）       | 高效相似度搜索（找相似对象）               |
| 搜索方式 | 精确计算所有点的距离           | 近似搜索（允许小误差，换取速度）             |
| 复杂度  | O(N)（每次预测要计算所有样本的距离） | 远小于 O(N)，常接近 O(logN)         |
| 应用场景 | 小规模分类/回归             | 大规模向量检索、推荐、RAG 系统            |


### 6.3 HNSW
背景:

* 最近邻搜索在高维空间（embedding 向量，几百维）里非常困难，被称为 **维度灾难**。
* HNSW 通过 **分层图 + 小世界网络** 的思想，大大加快了搜索速度，同时保持很高的准确率。

HNSW = **分层图结构（Hierarchy）** + **小世界导航网络（NSW, Navigable Small World）**。

分层结构:
* 数据点被组织成多层图：

  * 最顶层点数少，图很稀疏。
  * 越往下，点数越多，图越密。
* 每个点被随机分配一个最高层数（服从指数分布，少数点进入高层，多数点只在底层）。

👉 类似“金字塔”结构。

小世界图（NSW）:

* 每一层内部，点之间通过边相连，形成一个 **小世界图**：

  * 任意点之间的平均最短路径很短（logN 级别）。
  * 局部连接保证精确性，全局长边保证跳跃能力。

---

#### 搜索过程（Query）

查询向量 q 的搜索步骤：

1. **从顶层开始**

   * 在顶层选一个入口点（通常是上次索引的点或随机点）。
   * 贪心搜索：从当前点出发，沿着与 q 更接近的邻居不断跳转，直到找不到更近的点。

2. **逐层向下**

   * 把在上一层找到的最近点，作为下一层的入口点。
   * 重复贪心搜索。

3. **到底层搜索**

   * 在最底层（数据最全），用更宽的搜索（例如保留候选队列 ef\_search）找到 K 个近邻。
   * 返回最终结果。

👉 搜索复杂度大约是 **O(logN)**，比线性扫描 O(N) 高效得多。

---

#### 插入过程（Index Building）

插入一个新向量 v：

1. **采样层数**

   * 根据随机分布决定 v 的最高层数 L。

2. **从顶层往下插入**

   * 从顶层开始，用和查询类似的方法，找到每一层 v 应该连接的邻居点。
   * 在该层建立边（通常选最近的 M 个点）。

3. **继续下一层**

   * 一直插入到底层，完成索引构建。

👉 插入是在线的，不需要重建整个索引。

---

#### 参数

HNSW 有几个关键参数：

* **M**：每个节点的最大邻居数（控制图的稠密度，通常 16\~48）。
* **efConstruction**：建图时的候选队列大小（越大图越准，但建图越慢）。
* **efSearch**：查询时的候选队列大小（越大准确率越高，速度越慢）。

---

#### 特点

✅ **优点**

* 高准确率（几乎接近精确 KNN）。
* 查询速度快（logN 级别）。
* 支持动态插入。

⚠️ **缺点**

* 内存占用较高（存图结构）。
* 不支持删除（一般通过重建索引解决）。
* 构建过程相对耗时。

---

#### 应用

* **向量数据库**（Milvus、Weaviate、Pinecone 等）。
* **语义搜索**（文本 embedding 检索）。
* **图像/音频/视频 相似检索**。
* **推荐系统**（embedding 召回阶段）。

---

👉 总结一句话：
**HNSW 通过“分层小世界图”来高效导航，使得在大规模高维数据里做相似度搜索，既快又准。**