information retrieval lecture

60 %
40 %
Information about information retrieval lecture

Published on December 29, 2007

Author: BeatRoot


15-505 Internet Search Technologies:  15-505 Internet Search Technologies Lecture 5: Information Retrieval Kamal Nigam Slides adapted from Chris Manning, Prabhakar Raghavan, and Hinrich Schütze at Information Retrieval in 1650:  Information Retrieval in 1650 Which plays of Shakespeare contain the words Brutus AND Caesar but NOT Calpurnia? One could grep all of Shakespeare’s plays for Brutus and Caesar, then strip out lines containing Calpurnia? Slow (for large corpora) NOT Calpurnia is non-trivial Other operations (e.g., find the word Romans near countrymen) not feasible Ranked retrieval (best documents to return) Term-document incidence:  Term-document incidence 1 if play contains word, 0 otherwise Brutus AND Caesar but NOT Calpurnia Incidence vectors:  Incidence vectors So we have a 0/1 vector for each term. To answer query: take the rows for Brutus, Caesar and Calpurnia (complemented)  bitwise AND. 110100 AND 110111 AND 101111 = 100100. Answers to query:  Answers to query Antony and Cleopatra, Act III, Scene ii Agrippa [Aside to DOMITIUS ENOBARBUS]: Why, Enobarbus, When Antony found Julius Caesar dead, He cried almost to roaring; and he wept When at Philippi he found Brutus slain. Hamlet, Act III, Scene ii Lord Polonius: I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me. Search index construction:  Search index construction Documents to be indexed. Friends, Romans, countrymen. Tokenization:  Tokenization Documents to be indexed. Friends, Romans, countrymen. Tokenization:  Tokenization Input: “Friends, Romans and Countrymen” Output: Tokens Friends Romans and Countrymen Each token is candidate for an index entry, after further processing But what are valid tokens to emit? Tokenization: tricky cases:  Tokenization: tricky cases Finland’s  Finland? Finlands? Finland’s? Hewlett-Packard  Hewlett and Packard as one or two tokens? the hold-him-back-and-drag-him-away-maneuver ? Numbers: unique token for every number? L'ensemble  one token or two? L ? L’ ? Le ? German noun compounds are not segmented Lebensversicherungsgesellschaftsangestellter ‘life insurance company employee’ Chinese and Japanese have no spaces between words: 莎拉波娃现在居住在美国东南部的佛罗里达。 Normalization:  Normalization Documents to be indexed. Friends, Romans, countrymen. Normalization:  Normalization Need to “normalize” terms in indexed text as well as query terms into the same form We want to match U.S.A. and USA We most commonly implicitly define equivalence classes of terms e.g., by deleting periods in a term Alternative is to do asymmetric expansion: Enter: window Search: window, windows Enter: windows Search: Windows, windows Enter: Windows Search: Windows Potentially more powerful, but less efficient Case folding:  Case folding Reduce all letters to lower case exception: upper case (in mid-sentence?) e.g., General Motors Fed vs. fed SAIL vs. sail Often best to lower case everything, since users will use lowercase regardless of ‘correct’ capitalization… Makes some queries hard: “The Gap” – clothing store Stop words:  Stop words With a stop list, you exclude from dictionary entirely the commonest words. Intuition: They have little semantic content: the, a, and, to, be They take a lot of space: ~30% of postings for top 30 But the trend is away from doing this: Good compression lets the space for stopwords be very small Good query optimization techniques mean you pay little at query time for including stop words. You need them for: Phrase queries: “King of Denmark” Various song titles, etc.: “Let it be”, “To be or not to be” “Relational” queries: “flights to London” Stemming:  Stemming Reduce terms to their “roots” before indexing “Stemming” suggest crude affix chopping language dependent e.g., automate(s), automatic, automation all reduced to automat. for example compressed and compression are both accepted as equivalent to compress. for exampl compress and compress ar both accept as equival to compress Porter’s algorithm:  Porter’s algorithm Commonest algorithm for stemming English Results suggest at least as good as other stemming options Conventions + 5 phases of reductions phases applied sequentially each phase consists of a set of commands sample convention: Of the rules in a compound command, select the one that applies to the longest suffix. ies  i ational  ate tional  tion Normalization: other languages:  Normalization: other languages Accents: résumé vs. resume. Most important criterion: How are your users like to write their queries for these words? Even in languages with common accents, users often may not type them German: Tuebingen vs. Tübingen Should be equivalent Normalizations:  Normalizations Full morphological analysis – at most modest benefits for retrieval Do stemming and other normalizations help? Often very mixed results: really help recall for some queries but harm precision on others Indexing:  Indexing Documents to be indexed. Friends, Romans, countrymen. Big(ger) corpora:  Big(ger) corpora Consider N = 1M documents, each with about 1K terms. ~6 bytes/term including spaces/punctuation 6GB of data in the documents. Say there are m = 500K distinct terms among these. 500K x 1M matrix has half-a-trillion 0’s and 1’s. But it has no more than one billion 1’s. matrix is extremely sparse. What’s a better representation? We only record the 1 positions. Why? Inverted index:  Inverted index For each term T, we must store a list of all documents that contain T. Do we use an array or a list for this? Brutus Calpurnia Caesar 13 16 What happens if the word Caesar is added to document 14? Inverted index:  Inverted index Linked lists generally preferred to arrays Dynamic space allocation Insertion of terms into documents easy Space overhead of pointers 2 4 8 16 32 64 128 2 3 5 8 13 21 34 13 16 1 Sorted by docID (more later on why). Posting Indexer steps:  Sequence of (Modified token, Document ID) pairs. I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me. Doc 1 So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious Doc 2 Indexer steps Slide23:  Sort by terms. Core indexing step. Indexer steps Slide24:  Multiple term entries in a single document are merged. Frequency information is added. Why frequency? Will discuss later. Indexer steps Slide25:  The result is split into a Dictionary file and a Postings file. Slide26:  Where do we pay in storage? Pointers Terms Retrieval:  Retrieval Query processing:  Query processing We’ve just build something cool. How do we use it? Query processing: AND:  Query processing: AND Consider processing the query: Brutus AND Caesar Locate Brutus in the Dictionary; Retrieve its postings. Locate Caesar in the Dictionary; Retrieve its postings. “Merge” the two postings: 128 34 Brutus Caesar The merge:  The merge Walk through the two postings simultaneously, in time linear in the total number of postings entries 128 34 2 If the list lengths are x and y, the merge takes O(x+y) operations. Crucial: postings sorted by docID. Boolean queries: Exact match:  Boolean queries: Exact match Boolean Queries are queries using AND, OR and NOT to join query terms Views each document as a set of words Is precise: document matches condition or not. Primary commercial retrieval tool for 3 decades. Professional searchers (e.g., lawyers) still like Boolean queries: You know exactly what you’re getting. Boolean queries: More general merges:  Boolean queries: More general merges Exercise: Adapt the merge for the queries: Brutus AND NOT Caesar Brutus OR NOT Caesar Can we still run through the merge in time O(x+y) or what can we achieve? Merging:  Merging What about an arbitrary Boolean formula? (Brutus OR Caesar) AND NOT (Antony OR Cleopatra) Can we always merge in “linear” time? Linear in what? Query optimization:  Query optimization What is the best order for query processing? Consider a query that is an AND of t terms. For each of the t terms, get its postings, then AND them together. Brutus Calpurnia Caesar 13 16 Query: Brutus AND Calpurnia AND Caesar Query optimization example:  Query optimization example Process in order of increasing freq: start with smallest set, then keep cutting further. This is why we kept freq in dictionary Execute the query as (Caesar AND Brutus) AND Calpurnia. Phrase queries:  Phrase queries Phrase queries:  Phrase queries Want to answer queries such as “carnegie mellon” – as a phrase Thus the sentence “I got money from the Mellon bank in Carnegie” is not a match. The concept of phrase queries has proven easily understood by users; about 10% of web queries are phrase queries No longer suffices to store only <term : docs> entries Positional indexes:  Positional indexes Store, for each term, entries of the form: <number of docs containing term; doc1: position1, position2 … ; doc2: position1, position2 … ; etc.> Positional index example:  Positional index example Can compress position values/offsets Nevertheless, this expands postings storage substantially <be: 993427; 1: 7, 18, 33, 72, 86, 231; 2: 3, 149; 4: 17, 191, 291, 430, 434; 5: 363, 367, …> Which of docs 1,2,4,5 could contain “to be or not to be”? Processing a phrase query:  Processing a phrase query Extract inverted index entries for each distinct term: to, be, or, not. Merge their doc:position lists to enumerate all positions with “to be or not to be”. to: 2:1,17,74,222,551; 4:8,16,190,429,433; 7:13,23,191; ... be: 1:17,19; 4:17,191,291,430,434; 5:14,19,101; ... Same general method for proximity searches Positional index size:  Positional index size You can compress position values/offsets Still, a positional index expands postings storage substantially Standardly used because of the power and usefulness of phrase and proximity queries … whether used explicitly or implicitly in a ranking retrieval system. Rules of thumb:  Rules of thumb A positional index is 2–4 as large as a non-positional index Positional index size 35–50% of volume of original text Caveat: all of this holds for “English-like” languages Scoring and Ranking:  Scoring and Ranking Scoring:  Scoring Thus far, our queries have all been Boolean Docs either match or not Good for expert users with precise understanding of their needs and the corpus Applications can consume 1000’s of results Not good for (the majority of) users with poor Boolean formulation of their needs Most users don’t want to wade through 1000’s of results – cf. use of web search engines Scoring:  Scoring We wish to return in order the documents most likely to be useful to the searcher How can we rank order the docs in the corpus with respect to a query? Assign a score – say in [0,1] for each doc on each query Assume no spammers “adversarial IR” makes life complicated Incidence matrices:  Incidence matrices Recall: Document is binary vector X in {0,1}v Query is a binary vector Y Score: Overlap measure: Example:  Example On the query ides of march, Shakespeare’s Julius Caesar has a score of 3 All other Shakespeare plays have a score of 2 (because they contain march) or 1 Thus in a rank order, Julius Caesar would come out tops Overlap matching:  Overlap matching What’s wrong with the overlap measure? It doesn’t consider: Term frequency in document Term scarcity in collection (document mention frequency) of is more common than ides or march Length of documents (And queries: score not normalized) Scoring: density-based:  Scoring: density-based Thus far: overlap of terms/phrases in a doc Next: if a document talks about a topic more, then it is a better match Document relevant if it has a lot of the terms This leads to the idea of term weighting. Scoring: Term weighting:  Scoring: Term weighting Term-document count matrices:  Term-document count matrices Consider the number of occurrences of a term in a document: Bag of words model Document is a vector in ℕv: a column below Bag of words view of a doc:  Bag of words view of a doc Thus the doc John is quicker than Mary. is indistinguishable from the doc Mary is quicker than John. Term frequency tf:  Term frequency tf Idea: Score by summing all occurrences of query words in doc Long docs are favored because they’re more likely to contain query terms Can fix this to some extent by normalizing for document length But is raw tf the right measure? Note: in IR frequency means unnormalized count Counts vs. frequencies:  Counts vs. frequencies Consider again the ides of march query. Julius Caesar has 5 occurrences of ides No other play has ides march occurs in over a dozen All the plays contain lots of of By this scoring measure, the top-scoring play is likely to be the one with the most ofs Weighting term frequency: tf:  Weighting term frequency: tf What is the relative importance of 0 vs. 1 occurrence of a term in a doc 1 vs. 2 occurrences 2 vs. 3 occurrences … Unclear: while it seems that more is better, a lot isn’t proportionally better than a few Can just use raw tf Another option commonly used in practice: Note: in IR frequency means unnormalized count Score computation:  Score computation Score for a query q = sum over terms t in q: [Note: 0 if no query terms in document] Can use wf instead of tf in the above Still doesn’t consider term scarcity in collection (ides is rarer than of) Weighting should depend on the term overall:  Weighting should depend on the term overall Which of these tells you more about a doc? 10 occurrences of ides? 10 occurrences of of? Attenuate the weight of a common term But what is “common”? Consider collection frequency (cf ) The total number of occurrences of the term in the entire collection of documents Document frequency:  Document frequency But document frequency (df ) may be better: df = number of docs in the corpus containing the term Word cf df ferrari 10422 17 insurance 10440 3997 Document/collection frequency weighting is only possible in known (static) collection. So how do we make use of df ? tf x idf term weights:  tf x idf term weights tf x idf measure combines: term frequency (tf ) or wf, some measure of term density in a doc inverse document frequency (idf ) measure of informativeness of a term: its rarity across the whole corpus The most commonly used version is: Summary: tf x idf (or tf.idf):  Summary: tf x idf (or tf.idf) Assign a tf.idf weight to each term i in each document d Increases with the number of occurrences within a doc Increases with the rarity of the term across the whole corpus What is the wt of a term that occurs in all of the docs? Real-valued term-document matrices:  Real-valued term-document matrices Function (scaling) of count of a word in a document: Bag of words model Each is a vector in ℝv Here log-scaled tf.idf Note can be >1! Scoring: similarity:  Scoring: similarity Documents as vectors:  Documents as vectors Each doc j can now be viewed as a vector of wfidf values, one component for each term So we have a vector space terms are axes docs live in this space even with stemming, this is huge-dimensional (The corpus of documents gives us a matrix, which we could also view as a vector space in which words live – transposable data) Why turn docs into vectors?:  Why turn docs into vectors? You can also turn queries into (short) vectors With q a vector, find d vectors (docs) “near” it. Intuition:  Intuition Postulate: Text that is “close together” in the vector space talk about similar things. t1 d2 q d3 d4 d5 t3 t2 First cut at similarity:  First cut at similarity Idea: Distance between d1 and d2 is the length of the vector |d1 – d2|. Euclidean distance Why is this not a great idea? We still haven’t dealt with the issue of length normalization Short documents would be more similar to each other by virtue of length, not topic However, we can implicitly normalize by looking at angles instead Cosine similarity:  Cosine similarity Distance between vectors d1 and d2 captured by the cosine of the angle x between them. Note – this is similarity, not distance Cosine similarity:  Cosine similarity A vector can be normalized (given a length of 1) by dividing each of its components by its length – here we use the L2 norm This maps vectors onto the unit sphere: Then, Longer documents don’t get more weight Cosine similarity:  Cosine similarity Cosine of angle between two vectors The denominator involves the lengths of the vectors. Normalization Normalized vectors:  Normalized vectors For normalized vectors, the cosine is simply the dot product: Queries in the vector space model:  Queries in the vector space model Central idea: the query as a vector: We regard the query as short document We return the documents ranked by the closeness of their vectors to the query, also represented as a vector. Note that dq is very sparse! What did we learn today?:  What did we learn today? Length-normalized TFIDF-weighted/positional inverted index to compute cosine similarities Say it three times fast Store, for each term, entries of the form: <number of docs containing term; Doc1/tfidf: position1, position2 … ; Doc2/tfidf: position1, position2 … ; ...> Compute boolean matched documents with dot product scores together, and present them ranked to user Following up on today’s lecture:  Following up on today’s lecture Free online textbook: Good in-depth classes at CMU: 15-493 & 11-741 Taught by Jamie Callan and Yiming Yang

Add a comment

Related presentations

Related pages

Information Retrieval Lecture 7 - Evaluation in ...

Information Retrieval Lecture 7 - Evaluation in Information Retrieval Seminar fu r Sprachwissenschaft International Studies in Computational Linguistics
Read more

Information Retrieval Lecture 1 - Introduction

Information Retrieval Lecture 1 - Introduction Seminar fu r Sprachwissenschaft International Studies in Computational Linguistics Wintersemester 2007
Read more

Lectures :: Information Retrieval - Database Technology ...

In der heutigen digitalen Informationswelt werden zunehmend immer mehr Daten in den unterschiedlichsten Datenbanken bzw. Dateisystems gespeichert.
Read more

Information Retrieval - Lecture, Summer 2006

Information Retrieval (IR) deals with information search in purely structured data like e.g. fulltexts or multimedia databases. Popular ...
Read more

Information Retrieval - Lecture, Summer 20010

Besides the slides and the lecture notes, the following books and lecture notes are recommended: R. Baeza-Yates, B. Ribeiro-Neto: Modern Information ...
Read more

Information Retrieval - Lecture, Summer 2014

University of Duisburg, Information Systems. ... Targeted audience. Angewandte Informatik Master with 3+1 hours per week and 6 credit points
Read more

Lecture “Information Retrieval and Web Search Engines ...

This lecture provides an introduction to the fields of information retrieval and web search. We will discuss how relevant information can be found in very ...
Read more

Introduction to Information Retrieval | Coursera

Take free online classes from 80+ top universities and organizations. Coursera is a social entrepreneurship company partnering with Stanford University ...
Read more

CS276: Information Retrieval and Web Search

CS 276 / LING 286: Information Retrieval and Web Search. Lecture: 3 units, Tu/Th 4:15-5:30 at NVIDIA Auditorium (available online through SCPD) Staff e ...
Read more

Lectures :: Information Retrieval - Database Technology ...

Forschungskolleg Datenbanken (Master/Diplom) Forschungspraktikum DB-Systemarchitektur. Forschungspraktikum DB-Anwendungen
Read more