目录
1 前言
一个信息检索系统，可以抽象为给定一个查询query，检索出最能满足用户需求的item，也就是求对应概率
P
(
D
i
∣
Q
)
P(D_i| Q)
P(Di∣Q)最大的doc
D
i
D_i
Di。根据贝叶斯公式展开如下：
argmax
P
(
D
i
∣
Q
)
\operatorname{argmax \,}P(D_i|Q)
argmaxP(Di∣Q)
=
argmax
P
(
Q
∣
D
i
)
P
(
D
i
)
P
(
Q
)
=\operatorname{argmax \,} \frac{P(Q|D_i)P(D_i)}{P(Q)}
=argmaxP(Q)P(Q∣Di)P(Di)
=
argmax
P
(
Q
∣
D
i
)
P
(
D
i
)
=\operatorname{argmax \,}P(Q|D_i)P(D_i)
=argmaxP(Q∣Di)P(Di)
其中
P
(
D
i
)
P(D_i)
P(Di)表示的是文本
D
i
D_i
Di的重要程度，比如在电商场景，对应item的销量，评分质量等，
P
(
Q
∣
D
i
)
P(Q|D_i)
P(Q∣Di)表示item
D
i
D_i
Di能满足用户搜索query
Q
Q
Q的程度。接下来总结了一些常见的统计方法求query
Q
Q
Q与item
D
i
D_i
Di的相关性分值。
2 文本相关性技术
2.1 TFIDF
在信息检索系统中，term frequency-inverse document frequency (简称：TFIDF ）是常见的统计方法，用来计算一个term在文本的重要程度。tfidf经常用于信息检索，文本挖掘等应用。query
q
q
q和文本
d
d
d的TFIDF相关性计算公式如下：
T
F
-
I
D
F
(
q
,
d
)
=
∑
t
=
1
n
t
f
(
t
i
,
d
)
∗
i
d
f
(
t
i
,
D
)
TF\text{-}IDF(q, d) = \sum_{t=1}^n tf(t_i,d) * idf(t_i, D)
TF-IDF(q,d)=t=1∑ntf(ti,d)∗idf(ti,D)
其中
t
f
(
t
i
,
d
)
tf(t_i, d)
tf(ti,d)表示term
t
i
t_i
ti在文本
d
d
d的词频，
i
d
f
(
t
i
,
D
)
idf(t_i, D)
idf(ti,D)表示term
t
i
t_i
ti在整个文本集
∣
D
∣
|D|
∣D∣中的倒文本频率。对所有query中的term
t
i
t_i
ti在文本中的tfidf分值之和。其中
t
f
(
t
i
,
d
)
tf(t_i,d)
tf(ti,d)计算方式也是有多种，参考wikipedia总结的计算方式如下：
而
i
d
f
(
t
,
d
)
idf(t,d)
idf(t,d)计算方式主要有如下：
2.2 BM25
在信息检索系统中，BM25是搜索引擎中比较常见的评估query与文本相关性的排序算法。BM25全称叫做Okapi BM25，其中Okapi是一个信息检索系统，也是BM25算法最开始应用的检索系统，故命名为：Okapi BM25。如下是BM25算法对query
q
q
q与文本
d
d
d的相关性分值计算:
B
M
25
(
D
,
Q
)
=
∑
i
=
1
n
I
D
F
(
t
i
)
⋅
f
(
t
i
,
D
)
⋅
(
k
1
+
1
)
f
(
t
i
,
D
)
+
k
1
(
˙
1
−
b
+
b
⋅
∣
D
∣
a
v
g
d
l
)
BM25(D, Q) = \sum_{i=1}^nIDF(t_i) \cdot \frac{f(t_i, D) \cdot (k_1 + 1)}{f(t_i, D) + k_1 \dot (1-b + b \cdot \frac{|D|}{avgdl})}
BM25(D,Q)=i=1∑nIDF(ti)⋅f(ti,D)+k1(˙1−b+b⋅avgdl∣D∣)f(ti,D)⋅(k1+1)
其中
f
(
t
i
,
D
)
f(t_i, D)
f(ti,D)表示的是term
t
i
t_i
ti在文本
D
D
D中的词频tf，
∣
D
∣
|D|
∣D∣表示的是文本
D
D
D的词长度。avgdl表示的是在所有的文本集合中，文本的平均长度。
k
1
k_1
k1和
b
b
b是超参数，通常
k
1
∈
[
1.2
,
2.0
]
k_1 \in [1.2, 2.0]
k1∈[1.2,2.0]，
b
=
0.75
b=0.75
b=0.75。
I
D
F
(
t
i
)
IDF(t_i)
IDF(ti)是倒文本频率，通常计算如下：
I
D
F
(
t
i
)
=
I
n
(
N
−
n
(
t
i
)
+
0.5
n
(
t
i
)
+
0.5
+
1
)
IDF(t_i) = In(\frac{N - n(t_i) + 0.5}{n(t_i) + 0.5} + 1)
IDF(ti)=In(n(ti)+0.5N−n(ti)+0.5+1)
其中
N
N
N表示的是总文本数量，
n
(
t
i
)
n(t_i)
n(ti)表示包含term
t
i
t_i
ti的文本数。
2.3 KL
论文：Document Language Models, Query Models, and Risk Minimization for Information Retrieval 主要基于贝叶斯决策理论的统计概率模型来计算query与document的相关性，具体的细节可以详细阅读论文，在这里讲下怎么用KL度量query与document的相关性。KL度量query与document的计算公式如下：
K
L
(
Q
,
D
)
=
∑
w
p
(
w
∣
Q
)
log
p
(
w
∣
Q
)
p
(
w
∣
D
)
KL(Q, D) = \sum_w p(w|Q)\log\frac{p(w|Q)}{p(w|D)}
KL(Q,D)=w∑p(w∣Q)logp(w∣D)p(w∣Q)
其中
p
(
w
∣
Q
)
p(w|Q)
p(w∣Q)表示在query
Q
Q
Q中词
w
w
w的概率值，这个值可以通过语言模型或者任何其它方法计算得到，同理，
p
(
w
∣
D
)
p(w|D)
p(w∣D)表示词
w
w
w在文本
D
D
D的概率分值，若在query中的词概率分布和document的词概率分布越接近，KL分值越小，表明query与document相关性越大。我们把公式进一步变化，可以得到如下：
K
L
(
Q
,
D
)
=
∑
w
p
(
w
∣
Q
)
log
p
(
w
∣
Q
)
p
(
w
∣
D
)
KL(Q, D) = \sum_w p(w|Q)\log\frac{p(w|Q)}{p(w|D)}
KL(Q,D)=w∑p(w∣Q)logp(w∣D)p(w∣Q)
=
−
∑
w
p
(
w
∣
Q
)
log
p
(
w
∣
D
)
+
∑
w
p
(
w
∣
Q
)
log
p
(
w
∣
Q
)
= -\sum_wp(w|Q)\log p(w|D) + \sum_wp(w|Q)\log p(w|Q)
=−w∑p(w∣Q)logp(w∣D)+w∑p(w∣Q)logp(w∣Q)
=
C
E
(
Q
,
D
)
+
C
E
(
Q
,
Q
)
=
C
E
(
Q
,
D
)
+
c
= CE(Q, D) + CE(Q, Q) = CE(Q, D) + c
=CE(Q,D)+CE(Q,Q)=CE(Q,D)+c
从上面公式可以看到，两个分布的KL度量等同于两个分布的交叉熵加上一个常量值。
2.4 Term Weight
Term Weighting Approaches in Automatic Text Retrieval，该论文给出了一种基于term weight的query与document的相关性分值计算，计算公式如下：
similarity
(
Q
,
Q
)
=
∑
k
=
1
t
w
q
k
⋅
w
d
k
∑
k
=
1
t
(
w
q
k
)
2
⋅
∑
k
=
1
t
(
w
d
k
)
2
\text{similarity}(Q, Q) = \frac{\sum_{k=1}^tw_{qk}\cdot w_{dk}}{\sqrt{\sum_{k=1}^t{(w_{qk})}^2 \cdot \sum_{k=1}^t{(w_{dk})}^2}}
similarity(Q,Q)=∑k=1t(wqk)2⋅∑k=1t(wdk)2
∑k=1twqk⋅wdk
其中
w
q
k
w_{qk}
wqk表示的是词
w
k
w_k
wk在query中的词权重，而
w
d
k
w_{dk}
wdk表示的是词
w
k
w_k
wk在document中的词权重，上述公式就是对query中的词构成的词权重vector与document中的词构成的词权重vector求cos余弦值分值。
2.5 Proximity
该论文An Exploration of Proximity Measures in Information Retrieval 提出的一个思想是：在document中命中的query的terms之间距离对计算两者的相关性是有影响的，比如用户搜索词：“search engine”，召回的文本有如下两个：
document 1: " … search engine …"
document 2: “… search … engine …”
直观来说，document 1比document 2更相关，但是基于TF-IDF等算法就区分不出这种term之间的距离情况。所以通过将距离度量融入到BM25等计算文本相关性方案中，得到了基于距离(proximity)加强的检索公式：
R
1
(
Q
,
D
)
=
K
L
(
Q
,
D
)
+
π
(
Q
,
D
)
R_1( Q, D) = KL(Q, D) + \pi(Q, D)
R1(Q,D)=KL(Q,D)+π(Q,D)
R
2
(
Q
,
D
)
=
B
M
25
(
Q
,
D
)
+
π
(
Q
,
D
)
R_2(Q, D) = BM25(Q, D) + \pi(Q, D)
R2(Q,D)=BM25(Q,D)+π(Q,D)
其中
π
(
Q
,
D
)
\pi(Q, D)
π(Q,D)表示的距离计算分值，假设一个文本如下：
d
=
t
1
,
t
2
,
t
1
,
t
3
,
t
5
,
t
4
,
t
2
,
t
3
,
t
4
d = t_1, t_2, t_1, t_3, t_5, t_4, t_2, t_3, t_4
d=t1,t2,t1,t3,t5,t4,t2,t3,t4
搜索的query为
{
t
1
,
t
2
}
\{t_1, t_2\}
{t1,t2}，则距离分值的计算有如下几类：
- Span : Span表示文档中可以覆盖query的所有terms的最小距离，需要包含所有重复的term，述例子中，query在文本 d d d中的Span值为7。
- MinCover：表示的是文本中包含query中每个term至少一次的最短长度，上述例子中，MinCover的值为2
- MinDist: 表示的是所有query的terms pair对中在文档的最小距离，比如 query Q = t 1 , t 2 , t 3 Q={t_1, t_2, t_3} Q=t1,t2,t3，在文本 d d d的MinDist距离为1
- AveDist: 表示的是所有pair对的平均距离，比如 Q = t 1 , t 4 , t 5 Q={t_1, t_4, t_5} Q=t1,t4,t5在 d d d中的平均距离为：(1+2+3)/3 =2
-
MaxDist: 表示的是所有pair对的最大距离
可以通过不同的准则计算距离，得到距离后，我们的距离度量分值 π ( Q , D ) \pi(Q, D) π(Q,D)的计算公式可以如下：
π ( Q , D ) = log ( a + e x p ( − ϕ ( Q , D ) ) ) \pi(Q, D) = \log(a + exp(-\phi(Q, D))) π(Q,D)=log(a+exp(−ϕ(Q,D)))
其中 − ϕ ( Q , D ) -\phi(Q, D) −ϕ(Q,D)可以如上各种度量公式计算对应的距离。
2.6 Position Language Model
该论文Positional Language Models for Information Retrieval的主要思想是计算词在document的传播次数来构造一个基于位置的语言模型，不仅能够捕捉位置距离特征，而且能够实现一个"soft"的检索效果。
论文给出的基于position的语言模型PLM的计算公式如下：
p
(
w
∣
D
,
i
)
=
c
′
(
w
,
i
)
∑
w
′
∈
V
c
′
(
w
′
,
i
)
p(w|D, i) = \frac{c^{'}(w, i)}{\sum_{w^{'} \in V}c^{'}(w^{'}, i)}
p(w∣D,i)=∑w′∈Vc′(w′,i)c′(w,i)
其中
c
′
(
w
,
i
)
c^{'}(w, i)
c′(w,i)表示的是词
w
w
w从其他所有位置到位置
i
i
i的传播次数，计算公式如下：
c
′
(
w
,
i
)
=
∑
j
=
1
N
c
(
w
,
j
)
k
(
i
,
j
)
c^{'}(w, i) = \sum_{j=1}^N c(w,j)k(i,j)
c′(w,i)=j=1∑Nc(w,j)k(i,j)
其中
c
(
w
,
i
)
c(w, i)
c(w,i)表示的是词
w
w
w在document的第
i
i
i位置的次数，如果
w
w
w在位置
i
i
i有出现，值为1，否则为0。而
k
(
i
,
j
)
k(i,j)
k(i,j)表示的是从一个term在第
j
j
j位置上到第
i
i
i位置的传播次数。
有了上面的对document的每个词的PLM分值计算，我们就可以用KL检索模型来度量query与document的相关性：
S
(
Q
,
D
,
i
)
=
−
∑
w
∈
V
p
(
w
∣
Q
)
log
p
(
w
∣
Q
)
p
(
w
∣
D
,
i
)
S(Q, D, i) = -\sum_{w \in V}p(w|Q)\log\frac{p(w|Q)}{p(w|D, i)}
S(Q,D,i)=−w∈V∑p(w∣Q)logp(w∣D,i)p(w∣Q)
其中
p
(
w
∣
Q
)
p(w|Q)
p(w∣Q)是query的语言模型，这个分值的度量可以用已有的比如最大似然估计语言模型等。而PLM模型中
k
(
i
,
j
)
k(i, j)
k(i,j)的度量方式，论文中给出了如下几种方式：
-
Gaussian Kernel: 高斯核函数，计算公式如下：
k ( i , j ) = e x p [ − ( i − j ) 2 2 σ 2 ] k(i, j) = exp[\frac{-(i-j)^2}{2\sigma^2}] k(i,j)=exp[2σ2−(i−j)2] -
Triangle Kernel: 三角核函数，计算如下：
k ( i , j ) = { 1 − ∣ i − j ∣ σ i f ∣ i − j ∣ ≤ 0 0 otherwise k(i, j) =\begin{cases} 1 - \frac{|i -j|} {\sigma} \quad if \quad |i-j| \leq 0 \\ 0 \quad\quad\quad \text{otherwise} \end{cases} k(i,j)={1−σ∣i−j∣if∣i−j∣≤00otherwise -
Cosine (Hamming) kernel: 余弦核函数，计算公式如下：
k ( i , j ) = { 1 2 [ 1 + c o s ( ∣ i − j ∣ ⋅ π σ ) ] i f ∣ i − j ∣ ≤ σ 0 otherwise k(i, j) = \begin{cases} \frac{1}{2}[1+cos(\frac{|i-j|\cdot \pi}{\sigma})] \quad if \text{ } {|i-j|} \leq \sigma \\ 0 \quad\quad\quad \text{otherwise} \end{cases} k(i,j)={21[1+cos(σ∣i−j∣⋅π)]if ∣i−j∣≤σ0otherwise -
Circle kernel: 圆形核函数，计算公式如下：
k ( i , j ) = { 1 − ( ∣ i − j ∣ σ ) 2 i f ∣ i − j ∣ ≤ σ 0 0 otherwise k(i, j) = \begin{cases} \sqrt{1-(\frac{|i-j|}{\sigma})^2} \quad if \text{ } |i-j| \leq \sigma \\ 0 \quad\quad\quad 0 \quad \text{otherwise} \end{cases} k(i,j)={1−(σ∣i−j∣)2 if ∣i−j∣≤σ00otherwise -
Passage Kernel: 论文采取的文章核函数，计算公式如下：
k ( i , j ) = { 1 i f ∣ i − j ∣ ≤ σ 0 otherwise k(i, j) = \begin{cases} 1 \quad if \text{ } {|i-j|} \leq \sigma \\ 0 \quad\quad\quad \text{otherwise} \end{cases} k(i,j)={1if ∣i−j∣≤σ0otherwise
3 总结
上述介绍的方法，主要基于统计模型，通过计算query与document中每个词的权重或者概率构成的分布，基于KL， cosine余弦等方式计算query与document的相关性，而一个词的权重或者概率可以基于词频，倒文本频率，距离，语言模型等方法去计算求得。