Introduction to Information Retrieval (Draft)

Class-tested and coherent, this groundbreaking new textbook teaches web-era information retrieval, including web search and the related areas of text classification and text clustering from basic concepts. Written from a computer science perspective by three leading experts in the field, it gives an up-to-date treatment of all aspects of the design and implementation of systems for gathering, indexing, and searching documents; methods for evaluating systems; and an introduction to the use of machine learning methods on text collections. All the important ideas are explained using examples and figures, making it perfect for introductory courses in information retrieval for advanced undergraduates and graduate students in computer science. Based on feedback from extensive classroom experience, the book has been carefully structured in order to make teaching more natural and effective. Although originally designed as the primary text for a graduate or advanced undergraduate course in information retrieval, the book will also create a buzz for researchers and professionals alike. List of Tables 15 List of Figures 19 Table of Notation 27 Preface 31 Boolean retrieval 38 An example information retrieval problem 40 A first take at building an inverted index 43 Processing Boolean queries 47 The extended Boolean model versus ranked retrieval 51 References and further reading 54 The term vocabulary and postings lists 56 Document delineation and character sequence decoding 56 Obtaining the character sequence in a document 56 Choosing a document unit 57 Determining the vocabulary of terms 59 Tokenization 59 Dropping common terms: stop words 64 Normalization (equivalence classing of terms) 65 Stemming and lemmatization 69 Faster postings list intersection via skip pointers 73 Positional postings and phrase queries 76 Biword indexes 76 Positional indexes 78 Combination schemes 80 References and further reading 82 Dictionaries and tolerant retrieval 86 Search structures for dictionaries 86 Wildcard queries 88 General wildcard queries 90 k-gram indexes for wildcard queries 91 Spelling correction 93 Implementing spelling correction 94 Forms of spelling correction 94 Edit distance 95 k-gram indexes for spelling correction 97 Context sensitive spelling correction 99 Phonetic correction 100 References and further reading 102 Index construction 104 Hardware basics 105 Blocked sort-based indexing 106 Single-pass in-memory indexing 110 Distributed indexing 111 Dynamic indexing 115 Other types of indexes 117 References and further reading 120 Index compression 122 Statistical properties of terms in information retrieval 123 Heaps' law: Estimating the number of terms 125 Zipf's law: Modeling the distribution of terms 126 Dictionary compression 127 Dictionary as a string 128 Blocked storage 129 Postings file compression 132 Variable byte codes 133 Gamma codes 135 References and further reading 142 Scoring, term weighting and the vector space model 146 Parametric and zone indexes 147 Weighted zone scoring 149 Learning weights 150 The optimal weight g 152 Term frequency and weighting 154 Inverse document frequency 154 Tf-idf weighting 155 The vector space model for scoring 157 Dot products 157 Queries as vectors 160 Computing vector scores 161 Variant tf-idf functions 163 Sublinear tf scaling 163 Maximum tf normalization 164 Document and query weighting schemes 165 Pivoted normalized document length 166 References and further reading 170 Computing scores in a complete search system 172 Efficient scoring and ranking 172 Inexact top K document retrieval 174 Index elimination 174 Champion lists 175 Static quality scores and ordering 175 Impact ordering 177 Cluster pruning 178 Components of an information retrieval system 180 Tiered indexes 180 Query-term proximity 181 Designing parsing and scoring functions 182 Putting it all together 183 Vector space scoring and query operator interaction 184 References and further reading 186 Evaluation in information retrieval 188 Information retrieval system evaluation 189 Standard test collections 190 Evaluation of unranked retrieval sets 191 Evaluation of ranked retrieval results 195 Assessing relevance 201 Critiques and justifications of the concept of relevance 203 A broader perspective: System quality and user utility 205 System issues 205 User utility 206 Refining a deployed system 207 Results snippets 207 References and further reading 210 Relevance feedback and query expansion 214 Relevance feedback and pseudo relevance feedback 215 The Rocchio algorithm for relevance feedback 215 Probabilistic relevance feedback 220 When does relevance feedback work? 220 Relevance feedback on the web 222 Evaluation of relevance feedback strategies 223 Pseudo relevance feedback 224 Indirect relevance feedback 224 Summary 225 Global methods for query reformulation 226 Vocabulary tools for query reformulation 226 Query expansion 226 Automatic thesaurus generation 229 References and further reading 230 XML retrieval 232 Basic XML concepts 234 Challenges in XML retrieval 238 A vector space model for XML retrieval 243 Evaluation of XML retrieval 247 Text-centric vs. data-centric XML retrieval 251 References and further reading 253 Exercises 254 Probabilistic information retrieval 256 Review of basic probability theory 257 The Probability Ranking Principle 258 The 1/0 loss case 258 The PRP with retrieval costs 259 The Binary Independence Model 259 Deriving a ranking function for query terms 261 Probability estimates in theory 263 Probability estimates in practice 264 Probabilistic approaches to relevance feedback 265 An appraisal and some extensions 267 An appraisal of probabilistic models 267 Tree-structured dependencies between terms 268 Okapi BM25: a non-binary model 269 Bayesian network approaches to IR 271 References and further reading 272 Language models for information retrieval 274 Language models 274 Finite automata and language models 274 Types of language models 277 Multinomial distributions over words 278 The query likelihood model 279 Using query likelihood language models in IR 279 Estimating the query generation probability 280 Ponte and Croft's Experiments 283 Language modeling versus other approaches in IR 285 Extended language modeling approaches 287 References and further reading 289 Text classification and Naive Bayes 290 The text classification problem 293 Naive Bayes text classification 295 Relation to multinomial unigram language model 299 The Bernoulli model 300 Properties of Naive Bayes 302 A variant of the multinomial model 307 Feature selection 308 Mutual information 309 Chi2 Feature selection 312 Frequency-based feature selection 314 Feature selection for multiple classifiers 315 Comparison of feature selection methods 315 Evaluation of text classification 316 References and further reading 323 Vector space classification 326 Document representations and measures of relatedness in vector spaces 328 Rocchio classification 329 k nearest neighbor 334 Time complexity and optimality of kNN 336 Linear versus nonlinear classifiers 338 Classification with more than two classes 343 The bias-variance tradeoff 345 References and further reading 351 Exercises 352 Support vector machines and machine learning on documents 356 Support vector machines: The linearly separable case 357 Extensions to the SVM model 364 Soft margin classification 364 Multiclass SVMs 367 Nonlinear SVMs 367 Experimental results 370 Issues in the classification of text documents 371 Choosing what kind of classifier to use 372 Improving classifier performance 374 Machine learning methods in ad hoc information retrieval 378 A simple example of machine-learned scoring 378 Result ranking by machine learning 381 References and further reading 383 Flat clustering 386 Clustering in information retrieval 387 Problem statement 391 Cardinality -- the number of clusters 392 Evaluation of clustering 393 K-means 397 Cluster cardinality in K-means 402 Model-based clustering 405 References and further reading 409 Exercises 411 Hierarchical clustering 414 Hierarchical agglomerative clustering 415 Single-link and complete-link clustering 419 Time complexity of HAC 422 Group-average agglomerative clustering 425 Centroid clustering 428 Optimality of HAC 430 Divisive clustering 432 Cluster labeling 433 Implementation notes 435 References and further reading 436 Exercises 438 Matrix decompositions and latent semantic indexing 440 Linear algebra review 440 Matrix decompositions 443 Term-document matrices and singular value decompositions 444 Low-rank approximations 447 Latent semantic indexing 449 References and further reading 454 Web search basics 458 Background and history 458 Web characteristics 460 The web graph 462 Spam 464 Advertising as the economic model 466 The search user experience 469 User query needs 469 Index size and estimation 470 Near-duplicates and shingling 474 References and further reading 478 Web crawling and indexes 480 Overview 480 Features a crawler must provide 480 Features a crawler should provide 481 Crawling 481 Crawler architecture 482 DNS resolution 486 The URL frontier 488 Distributing indexes 491 Connectivity servers 492 References and further reading 495 Link analysis 498 The Web as a graph 499 Anchor text and the web graph 499 PageRank 501 Markov chains 502 The PageRank computation 505 Topic-specific PageRank 508 Hubs and Authorities 511 Choosing the subset of the Web 514 References and further reading 517 Bibliography 520 Author Index 558 "Class-tested and coherent, this textbook teaches classical and web information retrieval, including web search and the related areas of text classification and text clustering from basic concepts. It gives an up-to-date treatment of all aspects of the design and implementation of systems for gathering, indexing, and searching documents; methods for evaluating systems; and an introduction to the use of machine learning methods on text collections. All the important ideas are explained using examples and figures, making it perfect for introductory courses in information retrieval for advanced undergraduates and graduate students in computer science. Based on feedback from extensive classroom experience, the book has been carefully structured in order to make teaching more natural and effective. Slides and additional exercises (with solutions for lecturers) are also available through the book's supporting website to help course instructors prepare their lectures."--Publisher's description