A Quadratic Lower Bound for Rocchios Similarity-Based Relevance Feedback Algorithm

摘要：

It is shown in 4 that Rocchios similarity-based relevance feedback algorithm makes Ω(n) mistakes in searching for a collection of documents represented by a monotone disjunction of at most k relevant features (or terms) over the n-dimensional binary vector space 0,1n. In practice, Rocchios algorithm often uses a fixed query updating factor and a fixed classification threshold. When this is the case, we strengthen the work in 4 in this paper and prove that Rocchios algorithm makes Ω(k(n-k)) mistakes in searching for the same collection of documents over the binary vector space 0,1n. A quadratic lower bound is obtained when k is proportional to n. An O(k(n-k)2) upper bound is also obtained.

作者: Zhixiang Chen Bin Fu

作者单位: Department of Computer Science, University of Texas-Pan American Edinburg, TX 78541, USA Department of Computer Science, University of New Orleans New Orleans, LA 70148, USA Research Instit

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 955-964

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）