Skip to main content

信息检索笔记

· 8 min read
Ferdinand Su

谢谢🐙老师，希望他不要挂我

图 2

2 信息检索模型​

Boolean Model​

  • 线性扫描
  • Term-Doc关联矩阵

BM优缺点​

  • 最常用：简单、易理解，方便控制

  • 相当有效的实现方法

  • 不支持部分匹配

  • 难以对输出排序

  • 难以进行自动的相关反馈

VSM​

  • 假设索引项不相关，文档和查询是同一类东西
  • 词袋模型：不考虑词的顺序

TF-IDF​

wt,d=(1+log⁡tft,d)⋅log⁡Ndftw_{t,d}=(1+\log tf_{t,d})\cdot \log \frac{N}{df_t}

Similarities​

@Include Similarities={DotProduct,Cosine}

Jaccard​
JaccardSim(D,Q)=D⋅QD2+Q2−D⋅QJaccardSim(D,Q)=\frac{D\cdot Q}{D^2+Q^2-D\cdot Q}

VSM原理​

doc/query to vec

VSM优缺点​

  • 易实现

  • 引入词项权重

  • 能进行相似度的度量

  • 独立词项假设

  • 缺乏语义和语法信息

  • 仅是一个检索模型

  • 假设文档和查询是同一类东西

概率模型与语言模型​

@IIgnorable🌑

3 信息检索评价​

评价动机​

基本指标​

@Include ClassifierBase={Precision,Recall,F-Measure}

单值概括​

MAP​

查询集合中，每个查询平均准确率(不同召回率点上的平均准确率)的均值

R-Precision​

查询q结果中，第R个位置的准确率（R为相关文档总数）

准确率直方图​

多个查询的R-Precision

Precision@N​

第N个位置上的准确率

RR & MRR​

  • RR=结果中第一个相关文档出现位置的倒数
  • MRR=平均的RR

Bpref​

如果对于查询，已知R个相关结果，n是前R篇不相关文档集合的子集

Bpref=1R∑r(1−∣排在r之前的n∣R)Bpref=\frac{1}{R}\sum_{r}(1-\frac{|排在r之前的n|}{R})

NDCG​

CGn={G1,i=1CGi−1+Gi,i>1DCGn={CGi,i<b(通常为2)DCGi−1+Gilog⁡bi,i≥bCG_n=\begin{cases} G_1,& i=1\\ CG_{i-1}+G_i,&i>1 \end{cases}\\ DCG_n=\begin{cases} CG_i,& i\lt b(通常为2)\\ DCG_{i-1}+\frac{G_i}{\log_b i},&i\ge b \end{cases}\\

IDCGIDCG:通过GiG_i排序的理想情况下，计算的DCGDCG

NDCGn=DCGnIDCGnNDCG_n=\frac{DCG_n}{IDCG_n}

一致性检验的判定​

  • 判定人之间的一致性：Kappa指标κ=P(A)−P(E)1−P(E)\kappa=\frac{P(A)-P(E)}{1-P(E)}
  • P(A)P(A)观察到的一致性判断比例：expected.Zip(actual).Where(i1=i2).Count()/total.Count()expected.Zip(actual).Where(i1=i2).Count()/total.Count()
  • P(E)P(E)随机情况下期望的一致性判断比例：expected.Zip(actual).Sum(i1∗i2)/total.Count()∗total.Count()expected.Zip(actual).Sum(i1*i2)/total.Count()*total.Count()
  • 23≤κ≤1\frac{2}{3}\le\kappa\le 1时，判定结果可接受
图 1

4 文本操作​

文本处理​

  • 断词（英文）
  • 异文合并
    • 提取词干，形态还原（英文）：查表，词缀删除，后继变化数
    • 繁简转化

文本特性​

@IIgnorable🌑

5 相关反馈和查询扩展​

相关反馈​

  • 显式：有用户直接参与
  • 隐式：没有

@IIgnorable🌑

查询扩展​

引入同义词/近义词参与查询

6 索引与检索​

⭐倒排索引的基本思想​

面向单词，由词汇表和词汇出现的文档与位置

Dictionary<word,{docId,index}>

索引的压缩​

  • Unary Code：小整数xx编码为x-1个前导1和一个结尾0
  • Elias-γ\gamma Code：N=⌊log⁡2x⌋,K=x−2NN=\lfloor\log_2 x\rfloor,K=x-2^N，NN用UnaryCode编码，然后K使用N位二进制
  • Elias-δ\delta Code：与Elias-γ\gamma Code相似，但是将N+1N+1继续按照Elias-γ\gamma Code分解，然后与K之间用0分隔
  • Golomb Code：@I

签名文档的原理​

  • 基于哈希的面向单词的索引结构
  • 线性复杂度
  • 可用于过滤
  • 去除False Drops需要昂贵的开销

@IIgnorable🌑后缀树与后缀数组​

  • 解决倒排索引面对大词汇量的效率下降问题
  • 后缀树：后缀Trie
  • 后缀数组：比后缀树慢一点，是指向T的所有后缀的数组，其中后缀已经按照字典序排序

顺序检索的集中基本方法​

@Include AlgorithmBase

Horspool​

维护索引表dd，d[c]d[c]是从模式末端到PP中cc最后一次出现的距离

如模式BARBER可以得到如下索引表

ccABER?
d[c]d[c]42136

KMP​

维护最长前缀匹配模式

BM​

好后缀和坏字符：Horspool+反向KMP

7 Web检索​

爬虫​

@IIgnorable🌑

PageRank​

  • 应用于整个网络
  • 通过权威性对网页排序

Hilltop​

只计算来自具有相同主题的相关文档链接对于搜索者的价值更大

HITS​

考虑了不同链接的重要性

  • PageRank是离线算法 S是即时算法
    • Hub贡献度/Authority权威度
  • 迭代收敛
  • 互指的hub和authority

Shingle网页去重​

shingle为文档中一段连续的文字，可以利用它计算文本相似度、去重

8 分类和聚类​

聚类​

层次聚类​

  • 初始化每个文档为一个簇
  • 每次合并距离最近的两个簇

K均值聚类​

迭代，根据样例与当前类别均值的相似度来重新划分类别

特征选择​

  • 文档频率DF
  • TF-IDF
  • 信息增益
  • 互信息
  • 卡方检验

文本分类​

  • 朴素贝叶斯
  • 决策树
  • KNN

分类评价​

  • Macro F1：针对每一个类的指标的算术平均值
  • Micro F1：针对每一个文档的指标的算术平均值

9 自动文摘​

@IIgnorable🌑

抽取式文摘​

  • 句子长度
  • 句子位置
  • 句子是否包含标题词
  • 句子关键词打分
  • 句子-标题相似度
  • TF-IDF

评价：句子重合率

10 问答技术​

允许用户以自然语言方式询问，系统提供准确、简洁的答案

@Include IRLabs

12 信息抽取​

事件抽取技术​

  • 事件：发生在某个时间点/段、某个特定地域范围内，由一个或多个角色参与的一个或多个动作组成的事情或者状态的改变
  • 从无结构文本抽取结构化信息，并储存于数据库中
  • 触发词

事理图谱​

  • 描述事件之间的演化规律与模式
  • 有向无环图，节点为事件，有向边表示事件关系
  • 研究对象为谓词性时间，知识为事理逻辑关系与概率转移信息
  • 事件为抽象事件

13 信息推荐​

  • 使用其他用户的行为预测当前用户偏好
  • 协同过滤：用户-词项矩阵

@IIgnorable🌑

后边全是英文PPT，我直接开摆