Introduction to Information Retrieval

1 Online edition (c) 2009 Cambridge UPDRAFT! April 1, 2009 Cambridge University Press. Feedback classification and NaiveBayesThus far, this book has mainly discussed the process ofad hoc Retrieval , whereusers have transient Information needs that they try to address by posingone or more queries to a search engine. However, many users have ongoinginformation needs. For example, you might need to track developments inmulticore computer chips. One way of doing this is to issue the querymulti-coreANDcomputerANDchipagainst an index of recent newswire articles eachmorning. In this and the following two chapters we examine the question:How can this repetitive task be automated? To this end, many systems sup-portstanding queries. A standing query is like any other query except that itS TANDI NG Q UERYis periodically executed on a collection to which new documents are incre-mentally added over your standing query is justmulticoreANDcomputerANDchip, you will tendto miss many relevant new articles which use other terms suchasmulticoreprocessors.

2 To achieve good recall, standing queries thus have to be refinedover time and can gradually become quite complex. In this example, using aBoolean search engine with stemming, you might end up with a query like(multicoreORmulti-core)AND(chipORpro cessorORmicroprocessor).To capture the generality and scope of the problem space to which stand-ing queries belong, we now introduce the general notion of aclassificationC LAS S I FI C ATION problem. Given a set ofclasses, we seek to determine which class(es) a givenobject belongs to. In the example, the standing query servesto divide newnewswire articles into the two classes:documents about multicore computer chipsanddocuments not about multicore computer chips. We refer to this astwo-classclassification. Classification using standing queries is also calledroutingorRO UT I NGfilteringand will be discussed further in (page335).

3 FI LT ERI NGA class need not be as narrowly focused as the standing querymulticorecomputer chips. Often, a class is a more general subject area more general classes are usually referred to astopics, and the classifica-tion task is then calledtext classification,text categorization,topic classification,T EXT C LAS S I FI C ATION ortopic spotting. An example forChinaappears in Standingqueries and topics differ in their degree of specificity, butthe methods forOnline edition (c) 2009 Cambridge UP25413 Text classification and Naive Bayessolving routing, filtering, and text classification are essentially the same. Wetherefore include routing and filtering under the rubric of text classificationin this and the following notion of classification is very general and has many applications withinand beyond Information Retrieval (IR).

4 For instance, in computer vision, aclassifier may be used to divide images into classes such aslandscape,por-trait, andneither. We focus here on examples from Information Retrieval suchas: Several of the preprocessing steps necessary for indexingas discussed inChapter2: detecting a document s encoding (ASCII, Unicode UTF-8 etc;page20); word segmentation (Is the white space between two lettersaword boundary or not? page 24 ) ; truecasing (page30); and identifyingthe language of a document (page46). The automatic detection of spam pages (which then are not included inthe search engine index). The automatic detection of sexually explicit content (which is included insearch results only if the user turns an option such as SafeSearch off). Sentiment detectionor the automatic classification of a movie or productS ENT I MENT DET EC T I ONreview as positive or negative.

5 An example application is a user search-ing for negative reviews before buying a camera to make sure it has noundesirable features or quality problems. Personalemail sorting. A user may have folders liketalk announcements,EMAI L S O RT I NGelectronic bills,email from family and friends, and so on, and may want aclassifier to classify each incoming email and automatically move it to theappropriate folder. It is easier to find messages in sorted folders than ina very large inbox. The most common case of this application is a spamfolder that holds all suspected spam messages. Topic-specific search enginesrestrict searches toVERT I C AL S EARC HENG I NEa particular topic. For example, the querycomputer scienceon a verticalsearch engine for the topicChinawill return a list of Chinese computerscience departments with higher precision and recall than the querycom-puter science Chinaon a general purpose search engine.

6 This is because thevertical search engine does not include web pages in its index that containthe termchinain a different sense ( , referring to a hard white ceramic),but does include relevant pages even if they do not explicitly mention thetermChina. Finally, the ranking function in ad hoc Information Retrieval can also bebased on a document classifier as we will explain in (page341).Online edition (c) 2009 Cambridge UP255 This list shows the general importance of classification in IR. Most retrievalsystems today contain multiple components that use some form of classification task we will use as an example in this book is text computer is not essential for classification. Many classification taskshave traditionally been solved manually. Books in a libraryare assignedLibrary of Congress categories by a librarian.

7 But manual classification isexpensive to scale. Themulticore computer chipsexample illustrates one al-ternative approach: classification by the use of standing queries which canbe thought of asrules most commonly written by hand. As in our exam-RULES I N T EXTC LAS S I FI C ATIONple(multicoreORmulti-core)AND(chipO RprocessorORmicroprocessor), rules aresometimes equivalent to Boolean rule captures a certain combination of keywords that indicates a rules have good scaling properties, but creating and maintain-ing them over time is labor intensive. A technically skilledperson ( , adomain expert who is good at writing regular expressions) can create rulesets that will rival or exceed the accuracy of the automatically generated clas-sifiers we will discuss shortly; however, it can be hard to findsomeone withthis specialized from manual classification and hand-crafted rules, there is a thirdapproach to text classification, namely, machine learning-based text classifi-cation.

8 It is the approach that we focus on in the next severalchapters. Inmachine learning, the set of rules or, more generally, the decision criterion ofthe text classifier, is learned automatically from trainingdata. This approachis also calledstatistical text classificationif the learning method is TAT I S T ICAL T EXTC LAS S I FI C ATIONIn statistical text classification, we require a number of good example docu-ments (or training documents) for each class. The need for manual classifi-cation is not eliminated because the training documents come from a personwho has labeled them wherelabelingrefers to the process of annotatingLABELI NGeach document with its class. But labeling is arguably an easier task thanwriting rules. Almost anybody can look at a document and decide whetheror not it is related to China.

9 Sometimes such labeling is already implicitlypart of an existing workflow. For instance, you may go throughthe newsarticles returned by a standing query each morning and give relevance feed-back (cf. Chapter9) by moving the relevant articles to a special folder begin this chapter with a general Introduction to the textclassificationproblem including a formal definition ( ); we then cover NaiveBayes, a particularly simple and effective classification method ( ). All of the classification algorithms we study represent documents inhigh-dimensional spaces. To improve the efficiency of thesealgorithms, itis generally desirable to reduce the dimensionality of these spaces; to thisend, a technique known asfeature selectionis commonly applied in text clas-Online edition (c) 2009 Cambridge UP25613 Text classification and Naive Bayessification as discussed in evaluation of textclassification.

10 In the following chapters, Chapters14and15, we look at twoother families of classification methods, vector space classifiers and supportvector The text classification problemIn text classification, we are given a descriptiond Xof a document, whereXis thedocument space; and a fixed set ofclassesC={c1,c2, .. ,cJ}. ClassesDO C UMENT S PAC EC LAS Sare also calledcategoriesorlabels. Typically, the document spaceXis sometype of high-dimensional space, and the classes are human defined for theneeds of an application, as in the examplesChinaanddocuments that talkabout multicore computer chipsabove. We are given atraining setDof labeledT RAI NI NG S ETdocumentshd,ci,wherehd,ci X C. For example:hd,ci=hBeijing joins the World Trade Organization,Chinaifor the one-sentence documentBeijing joins the World Trade Organizationandthe class (or label) alearning methodorlearning algorithm, we then wish to learn a clas-LEARNI NG MET HO Dsifier orclassification function that maps documents to classes:C LAS S I FI ER :X C( )This type of learning is calledsupervised learningbecause a supervisor (theS UPERVI S ED LEARNI NGhuman who defines the classes and labels training documents)serves as ateacher directing the learning process.