作业信息检索lecture1-intro

1、Lecture 1: Boolean retrievalContentConcept of IRBasic Inverted IndexBoolean Query and ProcessingMore to be DiscussedInformation RetrievalInformation Retrieval (IR) is finding material (usually documents) of an unstructured nature (usually text) that satisfies an information need from within large co

2、llections (usually stored on computers).3Unstructured (text) vs. structured (database) data in 19964Unstructured (text) vs. structured (database) data in 20095Unstructured data in 1680Which plays of Shakespeare contain the words Brutus AND Caesar but NOT Calpurnia?One could grep all of Shakespeares

3、plays for Brutus and Caesar, then strip out lines containing Calpurnia?Why is that not the answer?Slow (for large corpora)NOT Calpurnia is non-trivialOther operations (e.g., find the word Romans near countrymen) not feasibleRanked retrieval (best documents to return)Later lectures6Sec. 1.1Term-docum

4、ent incidence1 if play contains word, 0 otherwiseBrutus AND Caesar BUT NOT CalpurniaSec. 1.1Incidence vectorsSo we have a 0/1 vector for each term.To answer query: take the vectors for Brutus, Caesar and Calpurnia (complemented) bitwise AND.110100 AND 110111 AND 101111 = 100100. 8Sec. 1.1Basic assum

5、ptions of Information RetrievalCollection: Fixed set of documentsGoal: Retrieve documents with information that is relevant to the users information need and helps the user complete a task9Sec. 1.1The classic search modelCorpusTASK Info NeedQuery Verbal formResultsSEARCHENGINEQueryRefinement Get rid

6、 of mice in a politically correct wayInfo about removing micewithout killing them How do I trap mice alive?mouse trapMisconception?Mistranslation?Misformulation?How good are the retrieved docs?Precision : Fraction of retrieved docs that are relevant to users information needRecall : Fraction of rele

7、vant docs in collection that are retrievedMore precise definitions and measurements to follow in later lectures11Sec. 1.1Bigger collectionsConsider N = 1 million documents, each with about 1000 words.Avg 6 bytes/word including spaces/punctuation 6GB of data in the documents.Say there are M = 500K di

8、stinct terms among these.12Sec. 1.1Cant build the matrix500K x 1M matrix has half-a-trillion 0s and 1s.But it has no more than one billion 1s.matrix is extremely sparse.Whats a better representation?We only record the 1 positions.13Why?Sec. 1.1Inverted indexFor each term t, we must store a list of a

9、ll documents that contain t.Identify each by a docID, a document serial numberCan we use fixed-size arrays for this?14BrutusCalpurniaCaesar124561657132124113145173231What happens if the word Caesar is added to document 14? Sec. 1.217454101Inverted indexWe need variable-size postings listsOn disk, a

10、continuous run of postings is normal and bestIn memory, can use linked lists or variable length arraysSome tradeoffs in size/ease of insertion15DictionaryPostingsSorted by docID (more later on why).PostingSec. 1.2BrutusCalpurniaCaesar12456165713212411314517323117454101TokenizerToken streamFriendsRom

11、ansCountrymenInverted index constructionLinguistic modulesModified tokensfriendromancountrymanIndexerInverted indexfriendromancountryman24213161More onthese later.Documents tobe indexedFriends, Romans, countrymen.Sec. 1.2Indexer steps: Token sequenceSequence of (Modified token, Document ID) pairs.I

12、did enact JuliusCaesar I was killed i the Capitol; Brutus killed me.Doc 1So let it be withCaesar. The nobleBrutus hath told youCaesar was ambitiousDoc 2Sec. 1.2Indexer steps: SortSort by termsAnd then docID Core indexing stepSec. 1.2Indexer steps: Dictionary & PostingsMultiple term entries in a sing

13、le document are merged.Split into Dictionary and PostingsDoc. frequency information is added.Why frequency?Will discuss later.Sec. 1.2Where do we pay in storage?20PointersTerms and countsLater in the course:How do we index efficiently?How much storage do we need?Sec. 1.2Lists of docIDsThe index we j

14、ust builtHow do we process a query?Later - what kinds of queries can we process?21Todays focusSec. 1.3Query processing: ANDConsider processing the query:Brutus AND CaesarLocate Brutus in the Dictionary;Retrieve its postings.Locate Caesar in the Dictionary;Retrieve its postings.“Merge” the two postin

15、gs:2212834248163264123581321BrutusCaesarSec. 1.3The mergeWalk through the two postings simultaneously, in time linear in the total number of postings entries233412824816326412358132112834248163264123581321BrutusCaesar28If list lengths are x and y, merge takes O(x+y) operations.Crucial: postings sort

16、ed by docID.Sec. 1.3Intersecting two postings lists(a “merge” algorithm)24Boolean queries: Exact matchThe Boolean retrieval model is being able to ask a query that is a Boolean expression:Boolean Queries use AND, OR and NOT to join query termsViews each document as a set of wordsIs precise: document

17、 matches condition or not.Perhaps the simplest model to build an IR system onPrimary commercial retrieval tool for 3 decades. Many search systems you still use are Boolean:Email, library catalog, Mac OS X Spotlight25Sec. 1.3Example: WestLaw Largest commercial (paying subscribers) legal search servic

18、e (started 1975; ranking added 1992)Tens of terabytes of data; 700,000 usersMajority of users still use boolean queriesExample query:What is the statute of limitations in cases involving the federal tort claims act?LIMIT! /3 STATUTE ACTION /S FEDERAL /2 TORT /3 CLAIM/3 = within 3 words, /S = in same

19、 sentence26Sec. 1.4Example: WestLaw Another example query:Requirements for disabled people to be able to access a workplacedisabl! /p access! /s work-site work-place (employment /3 place)Note that SPACE is disjunction, not conjunction!Long, precise queries; proximity operators; incrementally develop

20、ed; not like web searchMany professional searchers still like Boolean searchYou know exactly what you are gettingBut that doesnt mean it actually works better.Sec. 1.4Boolean queries: More general mergesExercise: Adapt the merge for the queries:Brutus AND NOT CaesarBrutus OR NOT CaesarCan we still r

21、un through the merge in time O(x+y)?What can we achieve?28Sec. 1.3MergingWhat about an arbitrary Boolean formula?(Brutus OR Caesar) AND NOT(Antony OR Cleopatra)Can we always merge in “linear” time?Linear in what?Can we do better?29Sec. 1.3Query optimizationWhat is the best order for query processing

22、?Consider a query that is an AND of n terms.For each of the n terms, get its postings, then AND them together.BrutusCaesarCalpurnia123581621342481632641281316Query: Brutus AND Calpurnia AND Caesar30Sec. 1.3Query optimization exampleProcess in order of increasing freq:start with smallest set, then ke

23、ep cutting further.31This is why we keptdocument freq. in dictionaryExecute the query as (Calpurnia AND Brutus) AND Caesar.Sec. 1.3BrutusCaesarCalpurnia123581621342481632641281316More general optimizatione.g., (madding OR crowd) AND (ignoble OR strife)Get doc. freq.s for all terms.Estimate the size

24、of each OR by the sum of its doc. freq.s (conservative).Process in increasing order of OR sizes.32Sec. 1.3Whats ahead in IR?Beyond term searchWhat about phrases?Stanford UniversityProximity: Find Gates NEAR Microsoft.Need index to capture position information in docs.Zones in documents: Find documen

25、ts with (author = Ullman) AND (text contains automata).33Evidence accumulation1 vs. 0 occurrence of a search term2 vs. 1 occurrence3 vs. 2 occurrences, etc.Usually more seems betterNeed term frequency information in docs34Ranking search resultsBoolean queries give inclusion or exclusion of docs.Ofte

26、n we want to rank/group resultsNeed to measure proximity from query to each doc.Need to decide whether docs presented to user are singletons, or a group of docs covering various aspects of the query.35IR vs. databases:Structured vs unstructured dataStructured data tends to refer to information in “t

27、ables”36EmployeeManagerSalarySmithJones50000ChangSmith6000050000IvySmithTypically allows numerical range and exact match(for text) queries, e.g.,Salary 60000 AND Manager = Smith.Unstructured dataTypically refers to free-form textAllowsKeyword queries including operatorsMore sophisticated “concept” q

28、ueries, e.g.,find all web pages dealing with drug abuseClassic model for searching text documents37Semi-structured dataIn fact almost no data is “unstructured”E.g., this slide has distinctly identified zones such as the Title and BulletsFacilitates “semi-structured” search such asTitle contains data AND Bullets contain search to say nothing of lingu