An introduction to information retrieval. Manning_ Raghavan (2009) (An introduction to information retrieval. Manning_ Raghavan (2009).pdf), страница 3

Feedback welcome.xxviiTable of NotationSymbolPageMeaningγp. 98γ codeγp. 256 Classification or clustering function: γ(d) is d’s classor clusterΓp. 256 Supervised learning method in Chapters 13 and 14:Γ(D ) is the classification function γ learned fromtraining set Dλp. 404 Eigenvalue~µ (.)p. 292 Centroid of a class (in Rocchio classification) or acluster (in K-means and centroid clustering)Φp. 114 Training exampleσp. 408 Singular valueΘ(·)p.

11ω, ωkp. 357 Cluster in clusteringΩp. 357 Clustering or set of clusters {ω1 , . . . , ωK }A tight bound on the complexity of an algorithmarg maxx f ( x ) p. 181 The value of x for which f reaches its maximumarg minx f ( x ) p. 181 The value of x for which f reaches its minimumc, c jp.

256 Class or category in classificationcftp. 89Cp. 256 Set {c1 , . . . , c J } of all classesCThe collection frequency of term t (the total numberof times the term appears in the document collection)p. 268 A random variable that takes as values members ofCOnline edition (c) 2009 Cambridge UPxxviiiTable of NotationCp.

403 Term-document matrixdp. 4Index of the dth document in the collection Ddp. 71A document~ ~qd,p. 181 Document vector, query vectorDp. 354 Set {d1 , . . . , d N } of all documentsDcp. 292 Set of documents that is in class cDp. 256 Set {hd1 , c1 i, . . .

, hd N , c N i} of all labeled documentsin Chapters 13–15dftp. 118 The document frequency of term t (the total numberof documents in the collection the term appears in)Hp. 99EntropyHMp. 101Mth harmonic numberI ( X; Y )p. 272 Mutual information of random variables X and Yidftp. 118 Inverse document frequency of term tJp. 256 Number of classeskp. 290 Top k items from a set, e.g., k nearest neighbors inkNN, top k retrieved documents, top k selected features from the vocabulary Vkp.

54Kp. 354 Number of clustersLdp. 233 Length of document d (in tokens)Lap. 262 Length of the test document (or application document) in tokensLavep. 70Average length of a document (in tokens)Mp. 5MaSize of the vocabulary (|V |)p. 262 Size of the vocabulary of the test document (or application document)Mavep. 78Mdp. 237 Language model for document dNp. 4Ncp. 259 Number of documents in class cN (ω )p. 298 Number of times the event ω occurredSequence of k charactersAverage size of the vocabulary in a document in thecollectionNumber of documents in the retrieval or trainingcollectionOnline edition (c) 2009 Cambridge UPxxixTable of NotationO(·)p. 11O(·)p.

221 The odds of an eventPp. 155 PrecisionP(·)p. 220 ProbabilityPp. 465 Transition probability matrixqp. 59Rp. 155 Recallsip. 58sip. 112 Boolean values for zone scoringsim(d1 , d2 )p. 121 Similarity score for documents d1 , d2Tp. 43Tctp. 259 Number of occurrences of word t in documents ofclass ctp. 4Index of the tth term in the vocabulary Vtp. 61A term in the vocabularytft,dp.

117 The term frequency of term t in document d (the total number of occurrences of t in d)Utp. 266 Random variable taking values 0 (term t is present)and 1 (t is not present)Vp. 208 Vocabulary of terms {t1 , . . . , t M } in a collection (a.k.a.the lexicon)~v(d)~ (d)Vp. 122 Length-normalized document vectorwft,dp. 125 Weight of term t in document dwp. 112 A weight, for example for zones or termsTA bound on the complexity of an algorithmA queryA stringTotal number of tokens in the document collectionp.

120 Vector of document d, not length-normalizedw~ ~x = b~ is the normal vector of the hyperp. 293 Hyperplane; wplane and wi component i of w~~xp. 222 Term incidence vector ~x = ( x1 , . . . , x M ); more generally: document feature representationXp. 266 Random variable taking values in V, the vocabulary(e.g., at a given position k in a document)Xp. 256 Document space in text classification| A|p. 61|S|Set cardinality: the number of members of set Ap. 404 Determinant of the square matrix SOnline edition (c) 2009 Cambridge UPxxxTable of Notation|si ||~x ||~x − ~y|p. 58Length in characters of string sip.

139 Length of vector ~xp. 131 Euclidean distance of ~x and ~y (which is the length of(~x − ~y))Online edition (c) 2009 Cambridge UPDRAFT! © April 1, 2009 Cambridge University Press. Feedback welcome.xxxiPrefaceAs recently as the 1990s, studies showed that most people preferred gettinginformation from other people rather than from information retrieval systems. Of course, in that time period, most people also used human travelagents to book their travel. However, during the last decade, relentless optimization of information retrieval effectiveness has driven web search enginesto new quality levels where most people are satisfied most of the time, andweb search has become a standard and often preferred source of informationfinding.

For example, the 2004 Pew Internet Survey (Fallows 2004) foundthat “92% of Internet users say the Internet is a good place to go for gettingeveryday information.” To the surprise of many, the field of information retrieval has moved from being a primarily academic discipline to being thebasis underlying most people’s preferred means of information access. Thisbook presents the scientific underpinnings of this field, at a level accessibleto graduate students as well as advanced undergraduates.Information retrieval did not begin with the Web. In response to variouschallenges of providing information access, the field of information retrievalevolved to give principled approaches to searching various forms of content.

The field began with scientific publications and library records, butsoon spread to other forms of content, particularly those of information professionals, such as journalists, lawyers, and doctors. Much of the scientificresearch on information retrieval has occurred in these contexts, and much ofthe continued practice of information retrieval deals with providing access tounstructured information in various corporate and governmental domains,and this work forms much of the foundation of our book.Nevertheless, in recent years, a principal driver of innovation has been theWorld Wide Web, unleashing publication at the scale of tens of millions ofcontent creators.

This explosion of published information would be mootif the information could not be found, annotated and analyzed so that eachuser can quickly find information that is both relevant and comprehensivefor their needs. By the late 1990s, many people felt that continuing to indexOnline edition (c) 2009 Cambridge UPxxxiiPrefacethe whole Web would rapidly become impossible, due to the Web’s exponential growth in size. But major scientific innovations, superb engineering,the rapidly declining price of computer hardware, and the rise of a commercial underpinning for web search have all conspired to power today’s majorsearch engines, which are able to provide high-quality results within subsecond response times for hundreds of millions of searches a day over billionsof web pages.Book organization and course developmentThis book is the result of a series of courses we have taught at Stanford University and at the University of Stuttgart, in a range of durations includinga single quarter, one semester and two quarters.

These courses were aimedat early-stage graduate students in computer science, but we have also hadenrollment from upper-class computer science undergraduates, as well asstudents from law, medical informatics, statistics, linguistics and various engineering disciplines. The key design principle for this book, therefore, wasto cover what we believe to be important in a one-term graduate course oninformation retrieval. An additional principle is to build each chapter aroundmaterial that we believe can be covered in a single lecture of 75 to 90 minutes.The first eight chapters of the book are devoted to the basics of information retrieval, and in particular the heart of search engines; we consider thismaterial to be core to any course on information retrieval.

Chapter 1 introduces inverted indexes, and shows how simple Boolean queries can beprocessed using such indexes. Chapter 2 builds on this introduction by detailing the manner in which documents are preprocessed before indexingand by discussing how inverted indexes are augmented in various ways forfunctionality and speed. Chapter 3 discusses search structures for dictionaries and how to process queries that have spelling errors and other imprecisematches to the vocabulary in the document collection being searched. Chapter 4 describes a number of algorithms for constructing the inverted indexfrom a text collection with particular attention to highly scalable and distributed algorithms that can be applied to very large collections. Chapter 5covers techniques for compressing dictionaries and inverted indexes.