Yi LIU-Affinity Rank.ppt

Affinity Rank Yi Liu, Benyu Zhang, Zheng Chen MSRA Outline Motivation Related Work Model Algorithm Evaluation Conclusion Future work Search for Useful Information Example –  “Spielberg” Search Example – “Spielberg” Search (Cont.) Motivation Existing problem in IR applications Similar search results dominate in top one/two pages Users feel tired to similar results of same topic Users cannot find what they need in those similar results Situations where problem are/will be intensified Highly repetitive corpus, e.g. Newsgroup News archive Specialized website Generalized or short query Diversity Informativeness Diversity The coverage of different topics of a group of documents Informativeness To what extent a document can represent its topic locality (high informativeness: inclusive) Why? Traditional IR evaluation measure Maximize relevance between query results Most important results To end-users relevant + important ≠ desirable A way out Increase diversity in top results Increase the informativeness of each single results Basic Idea Build similarity-based link map Link analysis ? Affinity Rank indicating the informativeness of each document Rank adjustment Only the most informative of each topic can rank high Re-rank with Affinity Rank More diversified top results More informative top results Related Work – link analysis Explicit PageRank (Page et al. 1998) HITS (Kleinberg, 1998) Implicit DirectHit () Small Web Search (Xue et al. 2003) Related Work – Clustering Our proposed IR framework Link Construction Similarity to directed link Directed graph Threshold Save storage space Reduce noise brought by overwhelmingly large amount of weak-similarity-links Assumption Observation : relation among documents varies Some are similar, others are not Similarity varies Link Analysis Link map ? adjacency matrix Row Normalize Based on two assumptions Principal eigenvector ? rank score Implementation: Power Method “Random Transform” Model A transforming