Page 1
Information Retrieval and Map-Reduce Implementations Adopted from Jimmy Lin’s slides, which is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States
Page 2
Roadmap Introduction to information retrieval Basics of indexing and retrieval Inverted indexing in MapReduce Retrieval at scale
Page 3
First, nomenclature… Information retrieval (IR) ⚫ Focus on textual information (= text/document retrieval) ⚫ Other possibilities include image, video, music, … What do we search? ⚫ Generically, “collections” ⚫ Less-frequently used, “corpora” What do we find? ⚫ Generically, “documents” ⚫ Even though we may be referring to web pages, PDFs, PowerPoint slides, paragraphs, etc.
Page 4
Information Retrieval Cycle Source Selection Resource Query Formulation Query Search Results Selection Documents System discovery Vocabulary discovery Concept discovery Document discovery Examination Information source reselection Delivery
Page 5
The Central Problem in Search Author Searcher Concepts Concepts Query Terms Document Terms “tragic love story” “fateful star-crossed romance” Do these represent the same concepts?
Page 6
Abstract IR Architecture Query Documents online offline Representation Representation Function Function Query Representation Document Representation Comparison Index Function Hits
Page 7
How do we represent text? Remember: computers don’t “understand” anything! “Bag of words” ⚫ Treat all the words in a document as index terms ⚫ Assign a “weight” to each term based on “importance” (or, in simplest case, presence/absence of word) ⚫ Disregard order, structure, meaning, etc. of the words ⚫ Simple, yet effective! Assumptions ⚫ Term occurrence is independent ⚫ Document relevance is independent ⚫ “Words” are well-defined
Page 8
What’s a word? 天主教教宗若望保祿二世因感冒再度住進醫院。 這是他今年第二度因同樣的病因住院。 الناطق باسم - وقال مارك ريجيف إن شارون قبل - الخارجية اإلسرائيلية الدعوة وسيقوم للمرة األولى بزيارة تونس، التي كانت لفترة طويلة المقر 1982 الرسمي لمنظمة التحرير الفلسطينية بعد خروجها من لبنان عام. Выступая в Мещанском суде Москвы экс-глава ЮКОСа заявил не совершал ничего противозаконного, в чем обвиняет его генпрокуратура России. भारत सरकार ने आर्थिक सर्वेक्ष ण में वर्वत्तीय र्वर्ि 2005-06 में सात फ़ीसदी वर्वकास दर हाससल करने का आकलन ककया है और कर सुधार पर ज़ो र ददया है 日米連合で台頭中国に対処…アーミテージ前副長官提言 조재영 기자= 서울시는 25일 이명박 시장이 `행정중심복합도시'' 건설안 에 대해 `군대라도 동원해 막고싶은 심정''이라고 말했다는 일부 언론의 보도를 부인했다.
Page 9
Sample Document McDonald's slims down spuds “Bag of Words” Fast-food chain to reduce certain types of fat in its french fries with new cooking oil. NEW YORK (CNN/Money) - McDonald's Corp. is 14 × McDonalds cutting the amount of "bad" fat in its french fries nearly in half, the fast-food chain said Tuesday as 12 × fat it moves to make all its fried menu items healthier. But does that mean the popular shoestring fries 11 × fries won't taste the same? The company says no. "It's a win-win for our customers because they are 8 × new getting the same great french-fry taste along with an even healthier nutrition profile," said Mike Roberts, president of McDonald's USA. 7 × french But others are not so sure. McDonald's will not specifically discuss the kind of oil it plans to use, 6 × company, said, nutrition but at least one nutrition expert says playing with the formula could mean a different taste. Shares of Oak Brook, Ill.-based McDonald's 5 × food, oil, percent, (MCD: down $0.54 to $23.22, Research, reduce, taste, Tuesday Estimates) were lower Tuesday afternoon. It was unclear Tuesday whether competitors Burger King and Wendy's International (WEN: down … $0.80 to $34.91, Research, Estimates) would follow suit. Neither company could immediately be reached for comment. …
Page 10
Information retrieval models An IR model governs how a document and a query are represented and how the relevance of a document to a user query is defined. Main models: ⚫ Boolean model ⚫ Vector space model ⚫ Statistical language model ⚫ etc 10
Page 11
Boolean model Each document or query is treated as a “bag” of words or terms. Word sequence is not considered. Given a collection of documents D, let V = {t1, t2, ..., t|V|} be the set of distinctive words/terms in the collection. V is called the vocabulary. A weight wij > 0 is associated with each term ti of a document dj ∈ D. For a term that does not appear in document dj, wij = 0. dj = (w1j, w2j, ..., w|V|j), 11
Page 12
Boolean model (contd) Query terms are combined logically using the Boolean operators AND, OR, and NOT. ⚫ E.g., ((data AND mining) AND (NOT text)) Retrieval ⚫ Given a Boolean query, the system retrieves every document that makes the query logically true. ⚫ Called exact match. The retrieval results are usually quite poor because term frequency is not considered. 12
Page 13
Sec. 1.3 Boolean queries: Exact match • The Boolean retrieval model is being able to ask a query that is a Boolean expression: – 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. – Perhaps the simplest model to build an IR system on • Primary commercial retrieval tool for 3 decades. • Many search systems you still use are Boolean: – Email, library catalog, Mac OS X Spotlight 13
Page 14
Strengths and Weaknesses Strengths ⚫ Precise, if you know the right strategies ⚫ Precise, if you have an idea of what you’re looking for ⚫ Implementations are fast and efficient Weaknesses ⚫ Users must learn Boolean logic ⚫ Boolean logic insufficient to capture the richness of language ⚫ No control over size of result set: either too many hits or none ⚫ When do you stop reading? All documents in the result set are considered “equally good” ⚫ What about partial matches? Documents that “don’t quite match” the query may be useful also
Page 15
Vector Space Model t3 d2 d3 d1 θ φ t1 d5 t2 d4 Assumption: Documents that are “close together” in vector space “talk about” the same things Therefore, retrieve documents based on how close the document is to the query (i.e., similarity ~ “closeness”)
Page 16
Similarity Metric Use “angle” between the vectors: d d cos() = j k d d j k d d n w w sim(d ,d ) = j k = i=1 i, j i,k j k d d n n w2 w2 j k i, j i,k i=1 i=1 Or, more generally, inner products: sim(d ,d ) = d d = n w w j k j k i=1 i, j i,k
Page 17
Vector space model Documents are also treated as a “bag” of words or terms. Each document is represented as a vector. However, the term weights are no longer 0 or 1. Each term weight is computed based on some variations of TF or TF-IDF scheme. 17
Page 18
Term Weighting Term weights consist of two components ⚫ Local: how important is the term in this document? ⚫ Global: how important is the term in the collection? Here’s the intuition: ⚫ Terms that appear often in a document should get high weights ⚫ Terms that appear in many documents should get low weights How do we capture this mathematically? ⚫ Term frequency (local) ⚫ Inverse document frequency (global)
Page 19
TF.IDF Term Weighting N w = tf log i, j i, j n i w weight assigned to term i in document j i, j tf number of occurrence of term i in document j i, j N number of documents in entire collection n number of documents with term i i
Page 20
Retrieval in vector space model Query q is represented in the same way or slightly differently. Relevance of di to q: Compare the similarity of query q and document di. Cosine similarity (the cosine of the angle between the two vectors) Cosine is also commonly used in text clustering 20
Showing the first 20 pages. Download the document to see it all.
Comments (0)
No comments yet. Be the first!