小小林熬夜学编程

这个屌丝很懒，什么也没留下！

热门标签

基础知识点整理

作者：小小林熬夜学编程 | 2024-04-29 06:23:37

踩

基础知识点整理

1 什么是IR information retrieval

1.1 定义相关

1.1.1 结构相关
1.1.2 信息项

1.2 信息需求 information need

1.2.1 4阶段
1.2.2 查询query

1.3 IR作用功能

1.3.1 相关定义

1.3.1.1 具体
1.3.1.2 补充

1.3.2 相关性 Relevance

1.3.3 问答相关 Qustion Answering 非IR

1.3.4 信息提取 information extraction 非IR

2 有关查询

2.1 矩阵相关

term-document incidence matrix

2.2 索引 indexing

2.2.1 inverted index

大纲
具体
代码相关

2.3 查询优化

2.3.1 skip pointers

2.3.1.1 相关代码

3 预处理 processing

3.1 引言，开始流程

3.2 方法措施，提高效率

stopwords 停词

stemming 提取词干

相关代码，使用porter提取法

lemmatisation 词形还原

3.3 phrase query 短语查询

biword index 双字索引
positional index 位置索引

4 向量模型的使用 vector space

4.1 introduction

4.2 权重 term weighting

TF-IDF

计算方式

4.3 优点和缺点

4.4 步骤

5 BM25 模型

5.1 TF
5.2 IDF
5.3 综合结果
5.4 俩变种

6 Evaluation 评估

6.1 引言

小概念
例子

6.2 Precision/Recall 精确度和召回率

6.3 Single value metric 单值度量基于RelRet

P@n
R-precision
MAP

6.4 bpref

6.5 NDCG

6.6 结果

7 IR pipelines和现代IR

8 Fusion

‍

1 什么是IR information retrieval

1.1 定义相关

简单描述

efficiency和scalability是关键
利用query在网络上找到自己想要的内容
就是搜索自己想要的内容，包括查找关键字等

简单定义

Information Retrieval (IR) deals with the representation, storage, organization of, and access to information items.
The representation and organization of the information items should provide the user with easy access to the information in which he is interested.
简而言之就是对于数据的存储和访问

1.1.1 结构相关

非结构化
- 自然语言书写的自由格式的文本 free-form text 英语汉语等
- keyword query/concespt query
- 大多数文档是semi-structured，标题、内容
结构化
- 更多类似于表格性质，有题头，内容等区别
- 查询时利用表头来把内容都找到

1.1.2 信息项

information item：非结构化形式的内容，比如书籍文档或书写的材料等，在IR系统中，使用document来指代信息项，而且不仅仅包含文字内容，还有音频图片等

在本pdf中所有文档或document的表述都是有关信息项的

representation

为了方便进行query，所以有某种表示方式
利用数学相关内容加速搜索：原始文本太多会非常慢，数学计算很快，以向量、集合、位串等形式来表示文档

1.2 信息需求 information need

1.2.1 4阶段

the actual, but unexpressed need for information (visceral need): “a vague sort of dissatisfaction ... probably inexpressible in linguistic terms”. 本能需求，难以表达
the conscious within-brain description of the need (conscious need): “an ambiguous and rambling statement”. i.e. “I know what I’m looking for but I don’t know how to say it”. 有意识的需求，知道在找啥但是不好说
the formal statement of the question (formalised need) 正式需求，换言之就是设定好的搜索的问题，比如北京工业大学都柏林学院的哪个老师好
the question as presented to the information system (compromised need) 妥协需求，会因为要求查询到的内容的精准性和范围来不断改变

1.2.2 查询query

query是提供给IR系统的对于信息需求的表达，用于解释需要什么样的信息

Keyword-based query：提供一个关键字或关键字列表，最常见
Context query：上下文查询，有semantic价值，查询在文档中应该紧挨着出现的单词序列
Boolean query：布尔查询，和关键字搭配，利用AND OR NOT配合关键字进行查询 e.g. “information AND (retrieval OR extraction) NOT data”.
natural language query：自然语言查询

补充

上下文查询和关键字查询是信息检索和搜索引擎中的两种不同查询方式，它们的区别主要体现在以下几个方面：

查询依据 ：

上下文查询 ：依赖于查询的上下文环境，例如用户的搜索历史、个人偏好、地理位置、时间信息等。这种查询方式试图理解用户的查询意图，并据此提供更为准确和个性化的搜索结果。
关键字查询 ：基于用户输入的具体关键词进行搜索，搜索引擎会匹配数据库中的内容与这些关键词，返回最相关的结果。

查询目的 ：

上下文查询 ：更多地关注于提供与用户当前需求高度相关的信息，它试图理解查询背后的“为什么”，而不仅仅是“是什么”。
关键字查询 ：目的是找到与用户输入的关键词直接相关的信息，它侧重于关键词的匹配度。

查询结果 ：

上下文查询 ：可能会返回一系列多样化的结果，这些结果是根据用户可能的多种需求综合判断得出的。
关键字查询 ：通常返回与关键词直接相关的结果，这些结果可能不如上下文查询那样个性化。

技术实现 ：

上下文查询 ：需要更复杂的算法来分析用户的查询上下文，包括自然语言处理、用户行为分析等。
关键字查询 ：实现相对简单，主要是文本匹配和相关性排序算法。

用户交互 ：

上下文查询 ：可能需要用户在首次查询后进行一系列的交互来进一步明确需求。
关键字查询 ：用户输入关键词后，系统直接返回结果，用户交互通常较少。
在实际应用中，现代的搜索引擎和推荐系统往往结合了上下文查询和关键字查询的优点，以提供更加智能和用户友好的服务。

1.3 IR作用功能

1.3.1 相关定义

IR系统不告知相关内容，而是告诉existence和whereabouts，就是告诉存不存在相关内容，如果存在需要去哪找，就类似搜索引擎搜出来的实际上是一个个的超链接。用户如果想知道具体内容就需要点进去了解

1.3.1.1 具体

提供一个list of documents that are relevant with information need
不会直接展示具体信息内容
大多数的IR会排序list，更相关的在上面

1.3.1.2 补充

当今时代有 information overload，信息过载。信息量越来愈大不可能会被完全吸收，所以IR会帮助人找到最需要的内容

1.3.2 相关性 Relevance

如果document的内容非常符合用户需求，那么相关性就很高。然后用户根据超链接读取具体内容。理论上来说这是主观概念，取决于人的判断。query只是对于information need的表达

判断IR好不好就可以从relevance的程度上来决定，但是主体上还是由人判断，而且如果想智能一些的话需要机器学习等

1.3.3 问答相关 Qustion Answering 非IR

1.3.4 信息提取 information extraction 非IR

通过提供的非结构化文本来创建结构化数据

2 有关查询

比如要查询 a AND b NOT c，此时会先把有关ab的都找到，然后去除c。这样不好，非常慢，而且复数过去式等会影响查询

2.1 矩阵相关

term-document incidence matrix

然后可以得到关联向量incidence vector，然后进行与或运算从而找到合适的document，但是对于更大的文本来说非常麻烦，难以扩展，矩阵非常大而且很sparse稀疏

而且会出现ambiguous query模糊查询，因为一个词有多个意思，不知道具体想找啥

2.2 索引 indexing

2.2.1 inverted index

term：术语，就是所需的词

大纲

是一种数据结构，每个t都被反映到存在哪些doc中。docID是文档的唯一标识符。每一个列表是按照docID排序的
多数情况下索引大小写不敏感，从而可以确保不会错过相关doc

具体

先把文档里的terms都拆开，重复的也拆开，然后按照顺序排，一个term对应一个dicID，从上到下应该是以docID为次序
按照term按照abcd进行排序
进行字典化然后展示相关doc list，同时记住frequency，也就是list的长度
排序在倒排索引中非常重要，因为它允许快速查找和比较。字典中的词汇是按字母顺序排列的，这使得查找特定词汇变得高效。同样，倒排列表中的文档也是有序的，这有助于在执行查询时快速定位到包含特定词汇的文档。排序是合并过程中的关键，因为它允许我们通过简单的比较操作来确定哪些文档是两个词汇共同出现的。如果没有排序，我们需要对每个词汇的所有文档进行配对检查，这将大大降低效率。排序将提高效率
此时想找a AND b NOT c就可以直接通过ab的list里共同的部分，然后在c去掉c的list的内容，就可以了
AND是交集，OR是并集，NOT是包含a自身去掉a and b

代码相关

# 老师的
def mergeAND(list1, list2):
	i, j = 0 , 0
	merged = []
	while i < len(list1) and j < len(list2):
		if list1[i] < list2[j]:
			i += 1
		elif list1[i] > list2[j]:
			j += 1
		else:
			merged.append(list1[i])
			i += 1
			j += 1
	return merged

def mergeOR(list1, list2):
	i, j = 0, 0
	merged = []
	while i < len(list1) or j < len(list2):
		if i < len(list1) and j == len(list2):
			merged.append(list1[i])
			i += 1
		elif j < len(list2) and i == len(list1):
			merged.append(list2[j])
			j += 1
		elif  list1[i] < list2[j]:
			merged.append(list1[i])
			i += 1
		elif list2[j] < list1[i]:
			merged.append(list2[j])
			j += 1
		else:
			merged.append(list2[j])
			i += 1
			j += 1
	return merged

def mergeNOT(list1,list2):
	i, j = 0 , 0
	merged = []
	while i < len(list1) and j < len(list2):
		if list1[i] < list2[j]:
			merged.append(list1[i])
			i += 1
		elif list1[i] > list2[j]:
			j += 1
		else:
			i += 1
			j += 1
	while i < len(list1):
		merged.append( list1[i] )
		i += 1
	return merged
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# 自己的
def mergeAND(list1, list2):
    answer = []
    i = 0
    j = 0
    while i < len(list1) and j < len(list2):
        if list1[i] == list2[j]:
            answer.append(list1[i])
            i += 1
            j += 1
        elif list1[i] < list2[j]:
            i += 1
        else:
            j += 1
    return answer


# print(mergeAND(words_map["a"], words_map["aa"]))

def mergeOR(list1, list2):
    answer = set()
    i = 0
    j = 0
    while i < len(list1):
        answer.add(list1[i])
        i += 1
    while j < len(list2):
        answer.add(list2[j])
        j += 1
    answer = sorted(list(answer))
    # answer = set(list1) | set(list2)
    return answer


# print(mergeOR(words_map["a"], words_map["aa"]))

def mergeNOT(list1, list2):
    answer = mergeAND(list1, list2)
    for num in answer:
        list1.remove(num)
    # answer = list(set(list1) - set(list2))
    return list1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

2.3 查询优化

会有一个term列表，每个term屁股后面都跟着一个docID的list，就很像图的邻接表一样。一般来说要是找AND, OR啥的会先从小的list一个个遍历到大的list，是一位一位的向后找

2.3.1 skip pointers

在常规的list里，就和链表结构一样，前一个指向后一个，此时可以通过引用一种skip pointer来跳过一些没必要的节点从而节省时间

Tradeoff

注意权衡的使用，如果跳的多，跳跃跨度小，会让结果更准确，但是会有更多的跳跃次数；如果跳的少，跳跃跨度大，可能会错失一些正确的结果，但是耗时少。所以如何选择合适的跳跃幅度是很重要的

一般采取 $\sqrt{L}$ 的作为跳跃间距 L是list的长度

决定跳过指针的位置需要在跳过频率、跳过指针比较的成本以及I/O成本之间找到一个平衡点。在实际应用中，可能需要根据具体的数据集特性、硬件性能和查询模式来调整跳过指针的策略。此外，随着技术的发展，比如固态硬盘（SSD）的普及，I/O成本可能会降低，这可能会影响跳过指针策略的有效性。

2.3.1.1 相关代码

#!/usr/bin/env python3

import math
import timeit
from unittest import skip

# define a class called "SkipList"
class SkipList:
   def __init__( self, elements ):
      size = len(elements)
      self.start = None
      self.length = 0

      sorted_elements = sorted( elements, reverse=True )
      skip_frequency = round( math.sqrt( size ) )

      for elem in sorted_elements:
         self.start = SkipNode( elem, self.start )
         if self.length == 0:
            skip_to = self.start
         elif self.length % skip_frequency == 0:
            self.start.skip = skip_to
            skip_to = self.start
         self.length += 1
  
      if skip_to != self.start:
         self.start.skip = skip_to

# define the nodes that a SkipList will store
class SkipNode:
   def __init__( self, elem, next_node ):
      self.element = elem # element stored in this node
      self.next_node = next_node # reference to the next node in the list
      self.skip = None # skip pointer: None if it doesn't have a skip pointer, otherwise it's a reference to another node


def intersect( list1, list2 ):
   answer = [] # a list to store the answer (for now: we will return a SkipList at the end)
   p1 = list1.start # start the first reference (p1) at the beginning list 1
   p2 = list2.start # start the second reference (p2) at the beginning list 2

   # haven't reached the end of either list
   while p1 is not None and p2 is not None:
      # if p1 and p2 point to the equal elements, add it to the answer and move both pointers
      if p1.element == p2.element:
         answer.append( p1.element )
         p1 = p1.next_node
         p2 = p2.next_node
      # p1's element is smaller, so move p1
      elif p1.element < p2.element:
         p1 = p1.next_node
      # p2's element is smaller, so move p2
      else:
         p2 = p2.next_node
   return SkipList(answer)

def intersect_skip( list1, list2 ):
   answer = []
   p1 = list1.start
   p2 = list2.start

   while p1 is not None and p2 is not None:
      if p1.element == p2.element:
         answer.append( p1.element )
         p1 = p1.next_node
         p2 = p2.next_node
      elif p1.element < p2.element:
         if p1.skip is not None and p1.skip.element < p2.element:
            p1 = p1.skip
         else:
            p1 = p1.next_node
      else:
         if p2.skip is not None and p2.skip.emement < p1.element:
            p2 = p2.skip
         else:
            p2 = p2.next_node
   return SkipList(answer)

# good idea to define a function to print the contents of a skip list
# i've included an option to include printing details of where the skip pointers are (if include_skips is True)
def print_skip_list( skiplist, include_skips=False ):
   n = skiplist.start
   while n is not None:
      print( n.element, end=' ' )
      if include_skips and n.skip is not None:
         print( '(skip to {})'.format( n.skip.element ) )
      elif include_skips:
         print()
      n = n.next_node
   print()

# This is the code that will run when you execute this file with Python.   
if __name__=='__main__':
   list1 = SkipList( range( 0, 100000 ) )
   list2 = SkipList( [ 2, 3, 46, 70, 7222, 999999 ] )

   # check that the output is ok
   print( 'Output for intersect(...)' )
   print_skip_list( intersect( list1, list2 ) )

   print( 'Output for intersect_skip(...)' )
   print_skip_list( intersect_skip( list1, list2 ) )

   # measure the time to run the intersect(...) function
   time_taken = timeit.timeit( 'intersect( list1, list2 )', number = 10, globals = globals() )
   print( 'Execution took {:.4f} seconds'.format( time_taken ) )

   print('Execution took {:.4f} seconds'.format( timeit.timeit( 'intersect_skip( list1, list2 )', number = 10, globals=globals() ) ) )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

3 预处理 processing

之前的步骤

3.1 引言，开始流程

tokenization
1. 就是把完整的一段话的各个单词单独提出来，此时提出的每一个单词叫做一个token，但是不一定此时就是我们需要的term
2. 提取token的时候会根据不同的情况做出不同的操作，比如 *Finland‘s *，你此时就不知道是保留’s还是去掉‘还是只保留Finland， *New York *是两个词还是一个， *aaa-bb-ccc-dddd *是作为整体还是区分开，对于时间数字或者索引来说怎么处理等
3. 而且对于不同的语言来说如何区分也是不同的，英语是一种方法，法语是一种，汉语是一种等等。
4. 总的来说，分词的决策通常取决于你的应用场景和目标 。例如，如果你正在处理一个需要理解语法结构的任务，那么保持单词的完整性可能很重要。而如果你的任务是信息检索，那么可能需要更细粒度的分词。在实际应用中，你可能需要根据具体需求来调整分词策略，以达到最佳的处理效果。
normalization
1. 使用归一化，确定好一定的规则。比如全改为小写，记住一些特定的词语作为一个整体，去掉符号，比如U.S.A = USA, anti-circle=anticircle
thesauri soundex
1. 同义词可以作为一种，不同写法的单词也可以作为一种。car=automobile，color=colour。形成等价类
2. 当拼写错误的时候可以尝试根据发音来检索到合适的内容

3.2 方法措施，提高效率

stopwords 停词

是一些很常见的词语，比如a the of 等，而且不会影响内容含义等的单词，所以预处理的时候可以直接去掉避免影响

删除停词的时候同样需要tradeoff，不一定所有的停词都需要删除，比如to be or not to be，这里面的就不可以删除。解决方法包括先不全部删除，而是先判断意义再考虑删除
一般采取 Zipf's Law

stemming 提取词干

一个单词的不同时态，单复数等，其实指的是同一个单词，所以此时需要尽可能还原成一种词干再来提取
stemming是将这些terms变成common root的过程。stem不一定是真正的单词，而是便于管理的公共根
一般来说单词的后缀是不同的，所以stemming也叫suffix stripping 后缀剥离
但是一味的利用后缀剥离可能导致 overstemming 过度提取。它指的是在词干提取（stemming）过程中，从一个单词中移除后缀，但这个过程可能会导致不同的单词被错误地转换成相同的词干。这种情况通常发生在单词的后缀被移除后，原本不同的单词变得相同，这可能会影响文本分析的准确性。而且也可能造成homographs，因为一个单词会有多个意思，此时就需要在语境中判断了

lemmatisation 词形还原

是一种NLP技术，就是把一个单词转化成字典里的样子，比stemming慢，但是更精准更有效
需要判断词性，所以需要更多的文本分析，所以如何处理比stemming更复杂困难

3.3 phrase query 短语查询

biword index 双字索引

将文本中连续的词对作为短语进行索引。abcdefg -> ab,bc,cd,de,ef,fg。但是这样做虽然可能搜到我们提供的查询语句的内容，但是只是盲目的匹配到了目标短语，实际上内容含义不一定符合需求。而且所需内存很大，占用空间

positional index 位置索引

存储某个term被多少doc包含，在每个doc里的位置是多少

一般双字和位置搭档使用

4 向量模型的使用 vector space

4.1 introduction

之前提到的是布尔查询相关，只会看doc有没有包含所需的term，只有相关和不相关，而且没有部分匹配的概念，而且没有根据相关性进行ranking，所以不大好，接下来将介绍向量模型来优化

‍

集合中包含一组doc，每个doc有多个term。集合中的term实际上都是唯一的，都是从各doc里提取出来的，对于某个doc来说，自己的term是属于集合的一部分的。如果对于集合中的某个term，当前doc有，那么就是一个值，叫term weight（简单情况下是1），否则就是0。基于对应的向量的值可以得到相似度评分。就是某doc和查询语句的点乘除以模的积 -> sim(q,d)
注意事项就是全部小写，然后去掉停词后全部拉下来成为集合中的一份子，然后转换成向量，然后计算cosine值即可
原理很简单，cos越大说明夹角越小越相似，而cos的值就可以点乘除以模长来得到

4.2 权重 term weighting

TF-IDF

info

TF：是term frequency，术语频率。term在某一个doc出现的次数越多，则越相关

IDF：是逆文档频率。在越多的doc中出现的term越像停词，所以需要IDF来消除出现次数过多的情况

TF-IDF是TF和IDF的乘积，每个doc里的每个term都有这个值，是特定的

TF: 对于每一个doc，其中的每一个term都有自己的TF。同一个doc里出现次数更多的term更重要。是独有的，依赖于term在单个doc出现的频率

IDF： 出现在全部doc中次数更少的term更重要。对于整个集合来说，每个term都有自己的IDF。是公共的，依赖于term在所有doc中的分布情况

计算方式

t f_{i, j} = \frac{f r e q_{i, j}}{m a x f r e q_{j}}

$tf_{i,j}=\frac{freq_{i,j}}{maxfreq_{j}}$

i d f_{i} = l o g_{2} (\frac{N}{n_{i}})

$idf_i=log_2\left(\frac{N}{n_i}\right)$

分子是某个term出现的次数，分母是在此doc中所有的频率中最大的那一个

N是doc总数，ni是包含此term的doc的数量

warn

为什么要除以最大频率呢? 是为了确保长文档中的术语不会因为出现次数多而获得不合理的优势。如果只计算词频，那么在长文档中频繁出现的术语可能会比在短文档中偶尔出现的术语具有更高的权重，这可能导致检索结果的不准确性。通过除以最大频率，我们可以使词频在不同的文档之间达到一个平衡点，从而更准确地反映每个术语的重要性。最大频率是某个文档去除所有停词后的拥有最大相同词的数量 a a a b b c的就是3

如何计算还是类似上面的vector的做法，但是把01的值换成TF×IDF即可

4.3 优点和缺点

TF-IDF会让某doc中出现次数更多的term产生更大的影响；同时减少整体集合中出现次数过多的term的影响

加权方案可以提高检索性能；部分匹配会得到实现；cos会提供排序
term相对独立，损害性能

4.4 步骤

5 BM25 模型

BM

和TF-IDF流程很像，只不过一些计算上有区别。相对于TF-IDF表现更好。简称为best match。

其中的IDF和TF很类似，但是多了一个doc长度规范化，这个保证较长的doc在查询的时候不会获得不公平的优势

5.1 TF

在BM25模型中，如果一个词在文档中出现的频率很高，那么它的评分提升会逐渐饱和，也就是说，这个词的频繁出现不会带来评分上的显著优势。在评估文档与查询的相关性时，一个词在文档中出现的次数确实很重要，因为它表示了该词与文档内容的关联程度。然而，如果一个词在文档中过于常见，那么它可能是一个常用词或停用词，对区分文档内容的作用不大。因此，BM25通过调整TF的计算方式，使得高频词的评分提升逐渐饱和，从而更准确地评估文档与查询的相关性。

就是和普通的模型相比，从 $tf_{i,j}=\frac{freq_{i,j}}{maxfreq_{j}}$ 变成了 $tf_{i,j}=\frac{freq_{i,j}}{maxfreq_{j} + k}$ 。分母多了一个常数k，k可以保证最高词频的词的TF会趋于饱和而不是达到1
如果一个文档里对于某个查询匹配的内容越多，就越相关。比如有俩文档，k设1，一个是aaaaa，一个是aab，搜索的是ab，那么第一个的TF就是5/6，第二个是2/3 + 1/2，
就算你第一个文档包含查询的某部分超级多，那也不如其他的文档只包含一次更多部分的查询的评分高。奖励完全匹配
BM25评分函数会优先选择完全匹配查询的文档，而不是只部分匹配查询但查询词频相同的文档。这意味着，如果一个文档包含了查询中的所有词，即使这些词的出现频率不如另一个文档高，BM25也会认为这个文档更相关。完全匹配查询中所有词的文档更可能比只包含部分查询词的文档更相关。因此，BM25通过这种方式来调整搜索结果的相关性排序，使得更符合用户查询意图的文档得到更高的排名。
如果有一系列的doc，BM25会得出每个doc的长度从而算出平均长度，对于长度更长的doc来说会增加k的大小，长度的小的减小，但k>=1恒成立
但是不一定会根据长度来修改k的值，BM25系统同时有个b参数，b取值0-1，b越大则调整k的幅度越大，如果为0就不调整，k是一样的

5.2 IDF

由 $log_2\left(\frac{N}{n_{i}}\right)$ 变成了 $log_2\left(\frac{N-n_{i}+0.5}{n_{i}+0.5}\right)$
可以保证对于出现次数很多的term，其IDF会下降非常快甚至小于0，但是我们又不希望得到负权重，所以要么是把出现次数过多的词作为新的停词去掉，要么分子分母同时加上0.5保证不小于0

5.3 综合结果

s i m_{B M 25} (d_{j}, q) \sim \sum_{k_{i} \in d_{j} \land k_{i} \in q} \frac{f_{i, j} \times (1 + k)}{f_{i, j} + k ((1 - b) + \frac{b \times l e n (d_{j})}{a v g_d o c l e n})} \times l o g_{2} (\frac{N - n_{i} + 0.5}{n_{i} + 0.5})

$sim_{BM25}(d_{j},q)\sim\sum_{k_{i}\in d_{j}\wedge k_{i}\in q}\frac{f_{i,j}\times(1+k)}{f_{i,j}+k\left((1-b)+\frac{b\times len(d_{j})}{avg\_doclen}\right)}\times log_2\left(\frac{N-n_{i}+0.5}{n_{i}+0.5}\right)$

k一般取1，b取0.75

5.4 俩变种

BM25F：让doc不同位置有不同权重，比如标题，底部，正文的都不一样
BM25+：不会让过短的文章得分过高

6 Evaluation 评估

6.1 引言

Cranfield Paradigm

relevant docs是相关的文档，但是相不相关由主观决定，所以需要专家来判断系统的有效性，从而产生了standard text collections：标准语料库，标准查询，相关性判断

小概念

C：所有的docs. collection/corpus
Rel：相关的docs，由专家提供.relevant sets
Ret：检索出来的docs，IR提供. answer set/retrieved set

一般来说Ret的结果是ranked后的结果

例子

6.2 Precision/Recall 精确度和召回率

这是最基本最广泛的评估指标，是许多其他指标的基础
$P=\frac{RelRet}{{Ret}}$ , 就是交集除以IR的结果
$R=\frac{RelRet}{{Rel}}$ , 是交集除以专家的结果

对照上面的结果就是 P = 5/15，R = 5/10

The two metrics of precision and recall are often inversely related: as one
increases the other decreases.

Precision will be high whenever a system is good at avoiding non-relevant documents.

A system can achieve very high precision by retrieving very few documents.

Recall will be high whenever a system finds many relevant documents.

A system can achieve 100% recall simply by retrieving all the documents in the collection.

保证精度更重要目前，对于IR来说

虽然基础精确度是一个不考虑排名的指标，但大多数信息检索系统实际上返回的是排序后的列表，而不是无序的文档集合。因此，用户更有可能首先查看列表的顶部，这意味着排名靠前的结果的精确度尤为重要。

6.3 Single value metric 单值度量基于RelRet

P@n

简单来说就是对于前n个结果的精度的值，就是在前n个中，有多少是相关的。
对照上面的结果就是 P@1=1, P@3=2/3, P@10=4/10, P@15=5/15
性能受到Rel的值的影响更大，因为Rel越大，找出来的结果越多，查到的机会越大

R-precision

R-precision 是一个相对于查询相关文档集合大小的指标，它考虑了所有相关文档。
P@n 是一个固定的指标，它只考虑前 n 个文档，而不考虑查询相关文档集合的大小
R-precision 更能反映检索系统在整个相关文档集合上的性能，而 P@n 则更关注检索系统在最前面的几个结果上的性能

R-precision的结果和P@n挂钩，因为此时Rel一共有10个，所以R-precision=P@10, 如果有13个那就=P@13

MAP

是IR最常用的指标，Mean Average Precision 最小平均精度指标。对于list中前部的doc会有所奖励，增加对应的某种权重，对于排名靠后的doc的权重设计的较低

先计算AP，结果是所有相关的P的值之和/Rel的数量

MAP就是在多次查询后的各AP的平均结果

6.4 bpref

binary preference

由于资源限制和评估方法的局限性，我们通常只能对检索结果的一部分进行人工相关性判断，而不是对所有可能相关的文档进行判断。这种不完整的判断可能导致一些实际上相关的文档被遗漏。

上面的数据是基于完整的相关性判断的，但是对于更大的collection，完整的判断会越来越困难越来越不常见，会出现不完整的判断，这意味着存在一些doc是没有被判断相关性的，所以需要一种新方法来计算精度

作用体现在如果存在大量的未被判断相关性的doc，会有更稳定和精确的结果

由于上图里面的所有内容都是基于全部Rel都有所判断，但是要是有一个没有被判断，那么AP的结果会有改变。解决方法是忽略掉没有被判断的doc，只看被成功判断的doc。

如果要加强判断，可以采取bpref10，就是分母变成10+R，R不变

6.5 NDCG

Normalised Discounted Cumulated Gain
归一化贴现累计增益

由bpref可以知道doc可以被判断为rel和non-rel，但是rel也分为相关程度，NDCG的作用就是来分级的

rel-doc在list的前方；越rel的越靠前

和上面P@n那几个有类似的做法，只不过Rel里面的内容会有一个rank值表示相关程度

有一个G列表表示收益，各位置对应的值就是rank值
有一个CG列表表示累计收益，各位置对应的值就是自己的rank加上上一层的CG值。
${\begin{cases} G [1], & i = 1; \\ G [i] + C G [i - 1], & i > 1 \end{cases}$ $\begin{cases}G[1],&i=1;\\G[i]+CG[i-1],&i>1\end{cases}$ $CG [i] = {G [1], G [i] + CG [i - 1], i = 1; i > 1$ 但是有一个弊端，就是CG越累积肯定是越大的，所以越往后越大，但是后面那些相关性不大的因此收获更大的rank，不大好，所以要加一个新list DCG discounted cg
DCG的值就是改进后的，第一层的值是本身，以后的值都是自己的值除以log2i加上上一层的DCG。
${\begin{cases} G [1], & i = 1; \\ \frac{G [i]}{l o g_{2} i} + D C G [i - 1], & i > 1 \end{cases}$
DCG[i]={G[1],log2iG[i]+DCG[i−1],i=1;i>1
1. 考虑了两个因素：相关性(relevance)和排名(position)。DCG 越高，说明系统返回的结果越符合用户的需求。然而，DCG 的值依赖于查询和文档的数量，因此很难在不同查询之间进行比较。
2. 相关doc越多，收益越大，越早期的doc贡献越大
3. 但是不好比较，最好变成0-1的结果，所以NDCG应运而生
4. 但是变成NDCG前，有一个新指标IDCG即理想DCG
IDCG的值应该是根据Rel的rank从大到小往后排列，如果Rel的长度小于Ret的话，后面的就补0

6.6 结果

用于IR评估的collection包括：docs，标准query，标准query的相关性判断

7 IR pipelines和现代IR

一系列问题：

一词多义，如何解决
多次同义，如何找出我们需要的所有的内容
是否可以使用多个modal帮助我们建立良好的IR系统
如何保证IR的运行速度。很小的模型可以采用AI或大语言模型帮助我们，中等的可采用BM25，再大型的就只能boolean query了，因为最快...
经典信息检索管道 ：涵盖预处理、建立索引、排序等步骤。这种管道存在词汇不匹配、歧义、同义等问题。
经典管道的问题 ：仅考虑文档内容，没有利用网络链接结构、URL等信息。同时，也没有利用机器学习和深度学习等最新进展。
更复杂的IR管道 ：包括伪相关反馈、查询扩展、融合、学习排序等步骤，用于提高检索效果。
特征学习排序 ：介绍了一些特征，如文本特征、PageRank、URL深度等，用于学习排序模型。
神经网络语言模型 ：提及了BERT等模型，并介绍了其优势。然而，大语言模型的速度较慢。
ChatGPT等大语言模型 ：用于生成式回答，但存在缺乏知识、无法引用来源等问题，不太适合直接用于信息检索。
结论：经典IR管道存在局限，现代IR利用了更多技术来提高检索质量，但响应时间也是一个重要考量。
经典IR流程 ：接着，文档介绍了传统IR系统的基本流程，包括文档预处理（如分词、语言处理）、索引创建、查询处理和排名方法（例如BM25算法）。这个流程是一个线性的管道模型，每个阶段的输出成为下一个阶段的输入。
经典IR流程的问题 ：文档指出了传统IR流程存在的问题，如词汇不匹配、多义性和同义词问题。此外，还提出了对检索模型选择的疑问，是否应该使用单一模型还是多种模型的组合。
现代IR的挑战 ：讲义进一步讨论了传统IR流程未能充分利用现代技术，如机器学习、自然语言处理（NLP）和自然语言理解（NLU）的问题。特别提到了大型语言模型（LLMs）如BERT、T5和GPT-4在NLP、NLU和机器翻译任务中的巨大进步，但也指出了这些模型速度慢的问题。
更复杂的IR流程 ：为了解决上述问题，文档提出了一个更复杂的IR流程，包括伪相关反馈、查询扩展、融合和学习排名等技术。这些技术旨在通过不同的方法改进检索结果，提高相关文档的匹配概率。
PageRank和文档重要性 ：文档还介绍了PageRank算法，这是一种根据网页链接结构来衡量文档重要性的方法，由Google的创始人开发。如果一个内容越重要，那么会有更多的其他连接链接到此内容的链接，会让此内容被更多知道
学习排名 ：学习排名是一种利用机器学习技术对初步检索结果进行重排的方法，目标是将最相关的文档放在排名列表的顶部。这一过程会考虑比初始排名分数更多的信息，如文本特征、非文本特征、查询清晰度等。
神经语言模型 ：文档提到了基于Transformer的神经语言模型，如BERT，以及由OpenAI发布的ChatGPT。这些模型通过学习大量文本中词语和短语之间的模式和关系来进行文档理解。
ChatGPT的问题 ：尽管ChatGPT等大型语言模型在NLP任务中取得了巨大成功，但在信息检索领域，它们还存在一些问题，如不能提供确切的知识来源，输出可能是错误的，并且不能引用其信息来源。
结论：最后，讲义总结了传统IR流程在现代IR方面的局限性，并指出了提高检索质量的多种技术，但响应时间是关键，因为涉及的数据量巨大。

伪反馈： query drift是指在使用伪相关反馈（Pseudo-Relevance Feedback）时可能出现的问题。伪相关反馈是一种技术，它假设排名靠前的文档是相关的，并据此调整检索算法的权重，以期望找到更多与用户认为相关的文档相似的文档。然而，如果这个过程没有得到适当的控制，可能会导致查询的主题逐渐偏离用户最初的意图，从而使得检索结果与用户的实际需求不再匹配。Query drift（查询漂移）是一个信息检索领域的概念，它描述了在进行多次检索或者在检索过程中不断调整查询时，查询的语义和方向可能发生偏离的现象。这种偏离可能会导致检索结果不再与用户最初的信息需求紧密相关。例如，如果用户最初查询的是关于“苹果”（水果）的信息，但是系统根据伪相关反馈主要返回了关于“苹果公司”的信息，那么随着时间的推移和多次迭代，查询可能会逐渐漂移，最终主要返回与苹果公司相关的信息，而不是关于水果的信息。这就是query drift的一个例子。为了避免query drift，信息检索系统需要采用一些策略来确保查询的稳定性和准确性，例如限制迭代次数、引入用户反馈机制、使用更复杂的查询理解技术等。这样可以确保检索结果始终与用户的实际需求保持一致。

查询扩展：

查询扩展（Query Expansion）是信息检索（IR）中的一种技术，旨在通过增加与原始查询词相关的其他术语来提高检索系统的性能。这种方法的目的是扩大检索范围，以便更全面地覆盖用户的信息需求，并提高检索到相关文档的概率。

在文档中提到的查询扩展方法有以下几种：

使用手动构建的词典 ：例如WordNet，它是一个大型的英语词典数据库，可以用来找到与原始查询词同义或相关的术语。通过这种方式，查询可以被扩展为包含更多可能与用户需求相关的词汇。
自动生成的词典 ：通过从外部语料库（如网络爬取的数据或维基百科）中提取数据来构建词典。这种方法可以捕捉到更广泛和更新的词汇使用情况。
词嵌入 ：利用词嵌入技术（如word2vec、GloVe、ELMo和基于BERT的嵌入）将词语表示为向量。这些向量能够捕捉词语之间的语义关系，从而帮助找到与查询词在语义上相近的其他词汇。
查询日志挖掘 ：搜索引擎可以通过分析之前用户对于相同查询词的使用行为来挖掘相关术语。这种方法基于用户实际的搜索行为，可能更贴近用户的真实需求。
目标语料库基础的技术 ：基于正在搜索的文档集合，这类技术可以分为两类：
- 基于分布的方法 ：比较伪相关文档中术语的分布（频率）与整个语料库的分布。
- 基于关联的方法 ：根据术语与查询词的共现关系来选择相关术语。

查询扩展的好处在于能够提高检索系统的查全率（recall），即使用更广泛的词汇覆盖来捕获更多可能相关的文档。然而，这也可能导致查准率（precision）的下降，因为扩展的查询可能会检索到一些不相关的文档。因此，查询扩展需要谨慎使用，以确保在提高查全率的同时，不会过多地牺牲查准率。

Fusion：

由排名检索系统计算的分数 ：不同系统可能会为相同的文档分配不同的分数，融合时可以考虑这些分数的加权和。
文档在每个结果列表中的排名 ：除了分数，文档在不同系统中的排名位置也可以作为融合的依据。
基于过去表现的文档相关性概率 ：如果有历史数据表明某些文档类型或来源的文档更可能是相关的，这些信息也可以用于调整融合策略
由多个IR输入，但是只输出一个

8 Fusion

8.1 introduction

data fusion，collection fusion results aggregatio越来越流行

combining the outputs of multiple 不同的IR系统或算法，把他们的结果合并成一个排序结果集，在响应式查询的时候显示给用户。大家希望这种组合出来的结果集比单个结果集的质量更好，higher precision higher recall...

过程大概是用户输入查询，fusion引擎利用多个IR系统进行查询，然后再对结果进行整合输出

返回的结果列表是根据每个doc的分数排序的，和内容无关，得分是根据每个IR自己的逻辑来得到的。算法之间的主要区别在于它们在分配分数时考虑了哪些信息。

Metasearch：由自主的完整的搜索引擎返回的结果集的融合
Distributed IR：多个小IR设计成co-operate的，每个IR处理collection的不同子集
Internal Metasearch：许多算法对同一个collection进行搜索

8.2 overlap 语料重叠

开发fusion算法的时候要考虑到doc集合(corpora)有多少重叠，重叠的程度会让处理最终结果的时候有所影响。有三种类型

disjoint database 不相交的数据库。搜索的内容是独立的doc集合，互相之间没有共同文档。同一个doc不会被多个不同的IR返回。分布式IR采用这个实现。此形态的语料库被称作Collection Fusion
identical database 相同数据库。每个IR接收到的查询集合都是同一组doc，所以结果doc会出现在多个结果集里，同时出现在结果集里的doc会更被认为具有相关性Rel。Internal Metasearch更常用这个。这是重点方法，也被乘坐 *Data Fusion *
overlapping database 重叠数据库。这个是每个IR使用的doc集合有一定程度上的重叠，doc同样会出现在多个结果集中，但是重复出现的doc不一定是高度相关的。External Metasearch更多的涉及到这种。
1. 此算法的特点是对于出现在多个结果集中的doc会给出更高的分数。都没出现的doc会被认为是0，每个结果集出现的doc会被认为都相关，在一部分结果集出现，在另一部分没出现不好判断

8.2.1 三种效应

Skimming effect
1. 一般来说最相关的doc会出现在结果集的顶部附近，但是skimming认为在每个结果集中skim最重要的doc，然后fusion他们会有更好的表现。被多种fusion算法所使用。就是只用最顶部的一部分doc
Chorus effect
1. 如果多个IR都认为一个doc是相关的，那么chorus认为此doc在最终结果集中应该更靠前，但是适用程度取决于语料库的overlap程度。这是一个需要被考虑的重要因素，但是对于disjoint database来说就没有考虑性了
Dark Horse 黑马effect
1. 某个结果集和其他结果集的内容相差太大，从而失去可用性

8.2.2 三种融合技术

Rank-Based fusion：只检查每个doc在其结果集中占据的排名和位置
Score-Based fusion：根据IR给出的相关性分数来作为其相关性信心的度量
Segment-Based fusion：将结果集划分为文档组，而不是使用个别的排名或分数

8.3 Rank-Baesd 基于排名的融合技术

8.3.1 interleaving 交错法

采取round robin的方法从每个input set的顶部取出一个doc，然后把他加到fusion的结果集中，选择的文档是尚未包含在fusion结果集中的排名最高的doc，但是效率比较低，因为它假设每个不同的结果集的质量是相等的，但是好的结果集的结果可能会被削弱

8.3.2 Borda-Fuse

Borda-Fuse 是基于一个选举系统，当少数投票者（输入系统）为许多候选人（文档）投票时使用。
每个投票者按偏好顺序对一组候选人进行排名。
对于每个投票者，排名第一的候选人获得c点，排名第二的获得c-1点，以此类推。
如果候选人没有被投票者排名，投票者的剩余点数将平均分配给未排名的候选人。

8.3.4 Reciprocal Rank Fusion 倒数排名融合

倒数排名融合 是一种简单的基于排名的方法，在实践中已被证明是有效的。
对于要排名的文档集D和结果集R，每个文档的得分计算如下： $RRFscore(d\in D)=\sum_{r\in R}\frac{1}{k+r(d)}$
其中r(d)是文档d在结果集r中的排名，k是一个通过实验设定的常数（在这里是60）。

8.3.5 其他

交错法的一个变体是使用历史数据来估计哪个输入系统倾向于表现得更好。
然后使用加权的交错法，以便从更好的系统中获取更多的文档。
同样基于选举的方法是 Condorcet-Fuse 算法，这是Borda-Fuse算法的另一种选举基础方法。
还提出了Borda-Fuse的加权版本，其中每个输入系统的点数乘以某个权重。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/506356

基础知识点整理