为啥要做Proximity计算

先来看下信息检索/搜索引擎 的一般架构流程:

1. 对Doc进行分词,这些分词也叫做Term，然后离线做各种计算
2. 将这些Term灌入倒排索引中
3. 用户查询
4. 根据倒排召回命中Term的文档
5. 将文档根据各个Term算分排序

其实可以发现这里查的Term 都是bag-of-words的形式，并且第五步的算法也一般是在线的，所以基本不会做全文扫描之类的事情，那么这样的话问题就来了：

如果搜索“红色连衣裙”,则可能会出现下面的文档:
1.xxxx红色连衣裙xxxx
2.红色高跟鞋配连衣裙
很明显文档1的相关性比2要高，但是此时如果仅仅是bag-of-words模型就很难保证1的相关性分要比2高

所以一般的搜索引擎还有一个叫做Proximity Measures的特征计算，可以理解为计算文档里面出现的query Term的相近程度，为了保证可行性，降低计算的复杂度，一般也只会计算两个Term之间的Proximity分

使用距离度量

这种方式主要是计算Term之间距离作为Proximity得分，主要分两大类:

1. Span-based:使用时将全部的query term丢进去一起算距离
2. Distance aggregation:先算两两之间的距离，再聚集起来

假设现在有文档D = t1, t2, t1, t3, t5, t4, t2, t3, t4，基于D集合来讲讲各个距离的计算方式
Span-based

• Span:在文档中可以覆盖所有term的最小距离称为Span，需要包含所有重复的term
  比如$Q=t1,t2$这个查询的$Span=7$
• MinCover:在文档中可以覆盖所有term的最小距离称为MinCover,每个term至少被包含一次
  比如这里的$Q=t1,t2$查询的$MinCover=1$

Distance aggregation

这种方式计算的最近单元是计算一个term pair的最小距离，使用$Dis(t_i,t_j;D)$来表示

• MinDist(Minimum pair distance):计算所有pair的最小距离的最小值,
  $MinDist=min_{q_1,q_2 \in Q \cap D,q_1 \neq q_2} Dis(q_1,q_2;D)$
  比如$Q={t1,t2,t3}$，则$MinDist=min(1,2,3)=1$
• AveDist(Average pair distance):计算所有pair的最小距离的平均值，
  $AveDist=\frac{2}{n \cdot (n+1)}min_{q_1,q_2 \in Q \cap D,q_1 \neq q_2} Dis(q_1,q_2;D)$
  比如$Q={t1,t2,t3}$，则$AveDist=(1+2+3)/3=2$
• MaxDist(Maximum pair distance):与MinDist正好相反，它是求最大值
  $MinDist=max_{q_1,q_2 \in Q \cap D,q_1 \neq q_2} Dis(q_1,q_2;D)$
  比如$Q={t1,t2,t3}$，则$MaxDist=max(1,2,3)=3$

文献中实验表明:

1. Span-based为考虑到各个文档长度，以各自文档的长度最为归一化因子进行归一化之后效果要好一些
2. Distance aggregation系列一般比Span-based的效果要好
3. Distance aggregation中MinDist的效果最好

但是在一般使用过程中不会直接将距离作为Proximity的值，现将$\delta(Q,D)$作为查询词在各个文档的中的距离度量，$\delta(Q,D)$最小表明查询词与文档越相关，而在使用过程中一般以这个相关性越大最好，这将这个相关性记为:$\pi(Q,D)$，则使用下面的公式来转换:
$$\pi(Q,D)=log(\alpha + exp(- \delta(Q,D)))$$

$\alpha$可以作为调节因子

使用这种方式的度量最大的优点就是方便，但是单独用起来效果可能不怎么理解，并且波动性较大.~

引入BM25模型

主要对bi-term进行BM25得分的计算，这里BM25的计算方式可以按传统的进行，参考这个

关于bi-term的构建主要有两种方式:

1. 直接使用B-Gram:认为相邻两个term是有依赖的，所以可以直接使用B-Gram的方式来构建
2. 使用滑窗的方式:认为一个窗口里面的两两term有依赖，因此可以对他们进行两两组合，这个窗口大小一般会小于8

其实更好的应该是依存关系来构建这个bi-term，不过上述的几种方式构建出来的pair都会很大，所以还需要其他一些方式来剪枝

持续研究中~~~

参考

1. 2007-An Exploration of Proximity Measures in Information Retrieval
2. 2005-A Markov random field model for term dependencies
3. 2010-How good is a span of terms?: exploiting proximity to improve web retrieval

---

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。