互联网搜索与排序

向量空间模型(VSM)

  • 将查询字符串表达为带权重的tf-idf向量(查询向量)
  • 类似,将文档字符串表达为带权重tf-idf向量(文档向量)
  • 计算查询查询向量和文档向量的余弦相似度
  • 将文档按照其与查询的相似度分值从大到小进行排序
  • 返回前K个(e.g.,K=10)文档并展示给用户

tf-idf

衡量某一个词在文档中的重要性

  • tf(w,d):term frequency 词w在d中出现的次数,tf值越大,w在文档d中越重要。
  • df(w): document frequency 整个数据集中,包含w文档的个数,df越大,w越不重要。
  • idf(w): inverse document frequency \(idf = log \frac{N}{df}\) 其中N为文档集的个数
  • tf-idf(w,d) = tf(w,d)*idf(w)

BM25(Best match 25)

\[ BM25 = \sum_{i \in q} \log\frac{N}{df_i} \cdot \frac{(k_1+1)tf_i}{k_1((1-b)+b\frac{dl}{avdl})+tf_i} \]

  • avgdl:集合中平均文档长度
  • \(k_1\):控制因\(tf\)的增大最终排序值的速度
    • k1=0:二值模型,只反映词是否出现,不考虑出现次数
    • k1无穷大:反映真正的tf值
  • b:控制文档长度归一化程度
    • b=0:不考虑文档长度对最终分值的影响
    • b=1:考虑文档长度平均文档长度的相对值
  • 经验值:k1=1.2~2,b=0.75

在上述公式中,文档长度定义为\(dl = \sum_{i\in V}tf_i\),文档长度归一化部分为\((1-b)+b\frac{dl}{avdl}, 0\leq b \leq 1\)\(b=0\)时,不进行归一化,当\(b=1\)时,全文档进行归一化。


排序评价指标

P@K(Precision at K)

  • 设置一个排序位置K
  • 前K个位置相关文档所占的比例
  • 忽略K位置之后的所有值

MAP(Mean average precision)

  • 只考虑出现过相关文档的位置

DCG(Discounted Cumulative Gain)

  • Gain: 文档对用户Gain与其查询相关度有关,\(2^{label}-1\),其中\(label\)取值如bad(0),fair(1),good(3),excellent(7),perfect(15)等,也就是说Gain是一个指数函数,效果越好影响越大。
  • Discounted Cumulative Gain:由于返回结果有一个排序,因此根据所在排序还需要一定的打折\(\frac{1}{log_2(rank+1)}\)

比较二者那么 CG@N \(CG=r_1+r_2+...+r_n\) NCG@N \(NCG= \frac{r_1}{\log(1+1)} + \frac{r_2}{\log(1+2)}+...+\frac{r_n}{\log(1+n)}\)

NDCG(Normalized DCG)

利用最优排序对DCG@N进行归一化处理,其中最优排序为按照用户标注对文档进行排序。其中\(IDCG_p\)为理想情况下最大的\(DCG\)值。 \[ nDCG_p = \frac{DCG_p}{IDCG_p} \]

Pair-wise排序学习:区分文档间的差异

核心思想:模型只需要区分同一个查询内部标注为不同相关度文档间的差异

排序支持向量机(ranking SVM)

  • Ranking SVM 训练
    • 构造训练数据集合\(\{\phi(q_k,d_{ki})-\phi(q_k,d_{kj}),+1\}\)
    • 训练二值分类SVM,得到打分函数\(f(q,d)=<w,\phi(q,d)>\)
  • Ranking SVM 在线应用
    • 给定一个查询q和检索出的文档集合\(C=\{d_i\}\)
    • \(f(q,d)\)对每一个C中的文档进行打分
    • 将C中的文档按照\(f(q,d)\)从大到小排序

优点 * 只关注文档间的差异性,解决了查询的差异化问题 * 实际应用效果良好

缺点 * N个文档有\(O(N^2)\)文档有序对,复杂度高 * 没有考虑浏览特性 * 违背分类训练数据独立同分布假设


语言排序模型

词袋假设\(P(w_1,w_2,...w_m)=P(w_1)P(w_2)...P(w_m)\) 估计每一个词的出现概率\(P(w)=\frac{#w}{all\,words}\),其中\(\sum_{w\in V}P(w)=1\)

语言模型中的马尔科夫假设,\(P(w_n|w_{n-1},w_{n-2},...,w_1)=P(w_n|w_{n-1})\) \(P(w_1,w_2,...,w_m)=P(w_1)P(w_2|w_1)P(w_3|w_2)...P(w_m|w_{m-1})\) 给定一个训练文档集合,统计给个一个词之后,其他词出现的概率\(P(w_i|w_j)=\frac{#(w_jw_i)}{#w_j}\) 举例来说\(\sum_{w_i\in V}P(w_i|'is')=1\)

数据稀疏问题

对于0概率问题采用平滑化方法

LM for IR

  • 定义生成模型的细节
  • 估计模型参数\(P(w|d)\)
  • 平滑化,防止零概率
  • 将文档对应的生成模型应用于查询,计算生成概率
  • 按照生成概率将文档排序,取topN展现给用户

给定查询\(q\)和文档\(d\),对文档的打分为\(P(d|q)\)根据贝叶斯公式 \[ P(d|q) = \frac{P(q|d)P(d)}{P(q)} \] 对于独立假设来说\(P(q|d)=P(q_1q_2,....q_m|d)=\Pi_{i=1}^MP(q_i|d)\)

举例: \(q\) 中国_科学院_大学 \(d\) 科学院_大学_计算机_学院

\(P(q|d)=P(中国|d)P(科学院|d)P(大学|d)=0*0.25*0.25=0\)

Dirichlet 平滑 与混合平滑

D={d1,d2}, Query q: Michael Jackson

d1: Jackson was one of the most talented entertainers of all time(11) d2: Michael Jackson anointed himself King of Pop(7) \(P(q|d_1)=\frac{0}{11}*\frac{1}{11}=0,P(q|d_2)=\frac{1}{7}*\frac{1}{7}=\frac{1}{49},P(Michael|C)=\frac{1}{18},P(Jackson|C)=\frac{2}{18}\)

混合模型\(\lambda=0.5\) \(P_{mix}(q|d_1)=(\frac{0}{11}*\frac{1}{2}+\frac{1}{18}*\frac{1}{2})*(\frac{1}{11}*\frac{1}{2}+\frac{2}{18}*\frac{1}{2})\) \(P_{mix}(q|d_2)=(\frac{1}{7}*\frac{1}{2}+\frac{1}{18}*\frac{1}{2})*(\frac{1}{7}*\frac{1}{2}+\frac{2}{18}*\frac{1}{2})\) 狄里克莱平滑\(\mu = 5\) \(P_{dir}(q|d_1)=(\frac{0+\frac{5}{18}}{11+5})(\frac{1+5*\frac{2}{18}}{11+5})\) \(P_{dir}(q|d_2)=(\frac{1+\frac{5}{18}}{7+5})(\frac{1+5*\frac{2}{18}}{7+5})\)