• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of combinatorial optimization >A quadratic lower bound for Rocchio's similarity-based relevance feedback algorithm with a fixed query updating factor
【24h】

A quadratic lower bound for Rocchio's similarity-based relevance feedback algorithm with a fixed query updating factor

机译：具有固定查询更新因子的Rocchio基于相似度的相关性反馈算法的二次下界

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Rocchio's similarity-based relevance feedback algorithm, one of the most important query reformation methods in information retrieval, is essentially an adaptive supervised learning algorithm from examples. In practice, Rocchio's algorithm often uses a fixed query updating factor. When this is the case, we strengthen the linear Omega(n) lower bound obtained by Chen and Zhu (Inf. Retr. 5:61-86, 2002) and prove that Rocchio's algorithm makes Omega(k(n-k)) mistakes in searching for a collection of documents represented by a monotone disjunction of k relevant features over the n-dimensional binary vector space {0,1} (n) , when the inner product similarity measure is used. A quadratic lower bound is obtained when k is linearly proportional to n. We also prove an O(k(n-k)(3)) upper bound for Rocchio's algorithm with the inner product similarity measure in searching for such a collection of documents with a constant query updating factor and a zero classification threshold.
机译：Rocchio基于相似度的相关性反馈算法是信息检索中最重要的查询重构方法之一，本质上是一种基于示例的自适应监督学习算法。实际上，Rocchio的算法通常使用固定的查询更新因子。在这种情况下，我们加强了Chen和Zhu（Inf。Retr。5：61-86，2002）获得的线性Omega（n）下界，并证明Rocchio的算法在搜索中犯了Omega（k（nk））错误。当使用内积相似性度量时，对于在n维二元向量空间{0,1}（n）上由k个相关特征的单调析取表示的文档集合。当k与n线性成比例时，可获得二次下界。我们还证明了Rocchio算法的O（k（n-k）（3））上限，具有内积相似性度量，可用于搜索具有恒定查询更新因子和零分类阈值的此类文档集合。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号