Class Note for CMPSCI 646 at UMass(15)
Class Note for CMPSCI 646 at UMass(15)
Popular in Course
Popular in Department
This 25 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 17 views.
Reviews for Class Note for CMPSCI 646 at UMass(15)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Information Retrieval Relevance Feedback Real and Assumed James Allan University of Massachusetts Amherst CMPSCI 646 Fall 2007 Copynghl JamesAllan First some intuition courtesy of Fernando Diaz Suppose you search for canine Copynghl JamesAllan Page 1 Score 10 m canine 10 dog 0 cat 0 Cnpyngh JamesAllan mmicun Calmquot Amomium Inc Score 5 Im canine 6 dog cat onpmma JamsAllan Page 2 Score 2 Im canine 2 dog 10 cat 2 capmme JamsAllan W cm xNHuNxmwu my mum 39 39 Score 0 HM L39u quwrm Amlrmlmn Im canine 0 dog 2 cat 10 mung onpmma JamsAllan Page 3 clogw 39 a 195 E MD Km I Score 0 I i canine 0 39 a dog 10 m cat 2 Copyright James Allan Embed in vector space model camne O 0 w j 5E x cat 0 N39 Copyright James Allan Page4 Retrieval with query canine tanine a t 0 d ca 0 Copyright James Allan Retrieval with query canine if Copyright James Allan Page 5 Retrieval with query canine canine Copyright James Allan Retrieval with query canine km Copyright James Allan Page 6 Relevance feedback canine relevant document U 0 5 I5 cat o 9 d09 Copyright James Allan Relevance feedback loanine new query canine dog relevant document 0 a O dog Copyright James Allan Page 7 Pseudorelevance feedback canine dog Copyright James Allan Big picture Relevance feedback 7 Adjust query with interaction User looks at returned list of documents and provides feedback aysxem returns a reVIseu rankeu n51 7 Can a better query be created automatically by analyzing relevant and nonrelevant documents Pseudorelevance feedback 7 Adjust query Without interaction Generate ranked list but do not present it Use information to create a new ranked list that is presented 7 Can a better query be created automatically by assuming that some documents are relevant Occurs in different models 7 Vector space is used most often we ll focus on it 7 Language modeling Excellent success with assumed relevance relevance models Less obviously good results for real feedback Copyright James Allan Page 8 Relevance Feedback in the Vector Space Goal Move new query closer to relevant documents Approach New query is a weighted average of original query and relevant and nonrelevant document vectors 1 2 07 1 QIQO Z Dj on and 3 are constants that represent the relative importance of positive and negative feedback Variations Different values of on and B Vector length number of terms added to the query Which documents are used for training all best uncertain etc Copyright James Allan Relevance Feedback in the Vector Space Example Original Query Relevance Feedback Formula 5 0 3 0 1 Q Q0DZ RDj D gRDj Document D1 Relevant 9 9 2 1 2 O 0 Document D2 Nonrelevant 1 O O O 2 a0500025 Q Q 05 D1 025 D2 5 0 3 0 1 052 1 2 0 0 025 1 0 0 0 2 575 050 400 00 05 Copyright James Allan Page 9 TREC Example The TREC Topic An Information Need Original TREC Topic ltnumgt Number 106 ltdomgt Domain Law and Government lttitlegt Topic US Control of Insider Trading ltdescgt Description Document Will report proposed or enacted changes to US laws and regulations designed to prevent insider trading ltcongt Concepts 1 insider trading 2 securities laW bill legislation regulation rule 3 Insider Trading Sanctions Act Insider Trading and Securities Fraud Enforcement Act 4 Securities and Exchange Commission SEC Commodity Futures Trading Commission CFTC National Association of Securities Dealers NASD ltfacgt Factors ltnatgt Nationality US Copynght James Allan TREC Example InQuery Adhoc Query Automaticallyprocessed query WSUM 10 lTerms from lttitlegt field 20 UW50 Control of Insider Trading 20 PHRASE USA Control 50 PHRASE Insider Trading l Terms from ltcongt field 20 PHRASE securities laW 20 bill 20 legislation 20 regulation 20 rule 20 3 Insider Trading Sanctions Act 20 3 Insider Trading and Securities Fraud Enforcement Act 20 3 Securities and Exchange Commission 20 SEC 20 3Commodity Futures Trading Commission 20 CFTC 20 3 National Association of Securities Dealers 20 NASD l Terms from ltdescgt field 10 proposed 10 enacted 10 changes 10 PHRASE USA laws 10 regulations 10 designed 10 prevent 20 NOTFOREIGNCOUNTRY Copynght James Allan Page 10 10 TREC Example Relevance Feedback Query Automatically modified query top 10 documents judged WSUM 1 3882349 UW50 control inside trade 2208832 SUM usa control 145571381 SUM inside trade 22084291 SUM secure law 22693285 bill 20984898 legislate 10354733 regulate 6540223 rule 1529766 OD3 inside trade sanction act 3290401 OD4 inside trade secure fraud enforcement act 48404 OD4 secure exchange commission 43578438 sec 094752 OD3 commodity future trade commission 1074666 cftc 2864415 OD4 national associate secure deal 21846081 nasd 0542252 propose 245709 enact 0988893 change 4354009 SUM usa law 0799089 design 1727937 prevent 0346877 NOT foreigncountry 4599784 drexel 2052418 fine 1845434 subcommittee 169074 surveillance 1597542 markey 1528179 senate 1186563 manipulate 1101982 pass 1060453 scandal 0921561 edward Relevance Feedback in the Vector Space Variations Term Selection None original query terms only All terms Most common terms Most highly weighted terms Weighting lde oc1 31 don t normalize by number ofjudged documents lde Dec Hi oc1 B a only the highest ranked nonrelevant documents don t normalize by number ofjudged documents Rocchio Choose 0c and B such that ocgtB and ocB1 1 NR D Z jENR 1 QIQ06 Z Dj Copyright James Allan j Page 11 11 Relevance Feedback in the Vector Space Common Choices Ide Dec Hi is effective when there are a fewjudged documents Rocchio oc075 025 is effective when there are manyjudged documents Expanding by all terms is best but selecting most common terms also works well 7 Depends somewhat on the retrieval model Coping With negatively weighted terms 7 Vector space does not allow negative weights for cosine similarity 7 Usually drop terms that end up negatively weighted 7 Can create a not like this vector consisting of negative terms Dif cult to balance issues correctly Copynghl James Allan Relevance Feedback Machine Learning Approaches An unstructured vector query is a linear discriminator 7 egWll 1WztzWatn The goal is to learn weights that separate the relevant documents from the nonrelevant documents Nonrelevant Re1evant documents documents lfthe documents are linearly separable a learning algorithm can be chosen that is guaranteed to converge to an optimal query lfthe documents are not linearly separable a learning algorithm can be chosen that minimizes the total amount of error Copynghl James Allan Page 12 12 Relevance Feedback Simple Methods for Adding Structure Basic Process Generate candidate operators Boolean Phrase proximity etc 7 algorithms exhaustive greedyselective Add some or all candidates to document representations Weight like other terms Effectiveness Extremely effective for proximity operators Boolean Copynghl JamesAllan Relevance Feedback Relevance Feedback could also modify document representation 7 document space modification 7 connectionist learning changing weights in network Assumptions 7 a person s relevance judgements are consistent 7 modifications for one person are meaningful for another Never shown to be effective consistently An old idea periodically resurfaces 7 recommender systems Dif cult to gure out how searchers should use it Copynghl JamesAllan Page 13 13 Relevance Feedback Summary Relevance feedback can be very effective Effectiveness depends on number ofjudged documents Signi cantly outperforms best human queries given enough judged documents Results can be unpredictable with less than five judged documents Not used often in production systems eg Web 7 consistent mediocre performance preferred to inconsistently goodgreat results 7 Stick with documents like this one variant An area of active research many open questions Copynghl JamesAllan Relevance Feedback Using it Relevance feedback is not widely used Few studies explore the user side of feedback 7 Don t necessarily answer that question but are still interesting JUrgen Koenemann and Nick Belkin looked at this 7 A case for interaction A Study of Interactive Information Retrieval Behavior and Effectiveness CHI 1996 User study of 64 users Presented with three styles of relevance feedback 7 Opaque relevance feedback is magic behind the scenes 7 Transparent same as opaque but users shown expansion terms 7 Penetrable user given chance to edit list of terms before rerun Copynghl JamesAllan Page 14 14 Base system used no feedback Rutgers INQUERV j Reet AH UNDO LAsT RUN QUERv Show seavch Toch Text Eth RU lNQUERV Entev next quevy tevm below and mt ltRETURNgt 4 Vou marked 0 document 3 I D l GM Plan to Recall 62 000 l988i89 cav Wlth Quad 4 Enqme Cwent Quew Ha 4 mm D 2 GM Fovd RecaH VethLe to ReDaw Detectwe Pavt 77 By Neal Temphn s automobllquot manufactuvquot D 3 lXLAZLA MOtOYX Honda Commence Cav Recall A Wall Stveetlouvnal New defecte D 4 FOYd and GM Recall Sevle Of PlckuD TYLACKE Coupe veca D 5 Geneval Motor covp RecaH T96000 cav Fov Detectwe Evake Total of 6747 document vemeved lump to rank iv Document l of 6747 GM Plan to Recall 4quot 62000 988789 cav mth Quad 4 E gme wsl9004T 3700 3 04T 390 WALL STREET JOURNAL 0 PAGE 52 DETROlT W Geneval Motov covb ald lt l vecang 62000 988789 model cav SqulDDed Wlth lt hlghrtech Quad 4 engme to x defectwe fuel hne lmked to 24 e glne ve GM ald the 988789 RontTac cvand Am OldeOblle cutLa Calal and Emck Skylavk cav SqulDDed WTth the T6rvalve fouvrcylmdev Quad 4 engme have fuel hne that could cvack ov ebavate om the e gme Although GM ha vecewed vebovt of 24 ve caued by leak atmbutable to the faulty fuel hne a bokeman ay the company know of no TnluvTe Yemltmg om the Tnchent GM old about 3T 2000 cav SqulDDed Wlth Quad 4 e gme m the 988789 model yeav ln anothev actToh GM ald lt l vecang about 3200 of lt T990 OldeOblle cutLa Calal and Emck Skylavk model to x erHme defect on thvee e glne the Qua 4 3 Brlltev v76 and 2 Srhtev fouv cyhndev GM Tn39t awave of any ve ov lmuvle velated to the fuel hne Dvoblem m thT 9voub of cav the bokeman aT AH YeDaW wm be done ee of chavge to ownev the comban Sepavately the U s ale avm of Volkwagen Ac39 AudT ubTdTavy ald lt l vecang L600 TQQOrmodel AudT 80 9 and coupe Quattvo Luxuvy cav to veDlace a defectwe bolt 77 the aembly that lock the teevmg when the cav T Davked The defectwe bolt could bveak caum9 the teevmg wheel to Copyright James Allan Allowing user access penetrable ResetAH UNDO LAST RU QUERv Show Search 39 Entev next quevy term below and mt ltRETURNgt Enter next quevy term below and hit ltRETURNgt cuvrem Query Ha 4 terms Current Query Ha 4 tennth aummobil manufaclm t automobw ma ufactuv cav defect defect recal recalquot GN 52 wt wst a system suggests to add these 9 stemmed DE accidv A 620 Dontlacquot GS COWe cala fault om camav39oquot of SE Cutlass gill lfeaquot imuv vetnrd can onmobTI ln V m TS T to Ue All 3 3 anyl u A Se Ubl and the e The t s UM x Copyright James Allan Page 15 15 Experimental procedure Two query construction approaches 7 First without relevance feedback 7 Second one of three RF approaches randomly assigned Task is to construct a good longterm query Evaluation is based on effectiveness of final query No difference between users on first task Copyright o James Allan Effectiveness with Feedback Kemeval Emma m mp so requiem Tm eeeee l nun m n m in amquot in 1xgpxmmumm n Candinan Precision at 30 documents Clear improvements from use of RF Opaque and transparent the same by design Penetrable best Only statistically significant difference is between penetrable and base Results comparable for precision at 100 documents Copyright o James Allan Page 16 16 Behavior with Feedback Task was to build a good query How man attem ts do people make For some reason transparent interface encouraged an extra iteration Penetrable interface took one less than normal Not clear what this means quotml afltnmumh Copyright JamesAllan Was Feedback Used by Searcher Where did words they chose come from Copied from lists provided by feedback 7 Added automatically by system Users typed short quenes Feedback added many terms Penetrable system encouraged fewer terms 7 But resulted in more effective queries faster Mean Number Kz Sources of Query Terms Relevance User Controlled Added Feedback User Copy by 2 Condition Typed from 2 RF RF SYS Topic 162 None 69 na 53 na 69 Opaque 109 na 109 359 468 Transparent 33 91 124 423 551 Penetrable 63 244 306 na 306 Topic 165 None 60 nfa 60 nfa 60 Opaque 33 nfa 33 205 243 Transparent 43 53 95 173 273 Penetrable 33 95 128 nfa 123 10233135 None 64 nja 64 nfa 64 Opaque 73 nfa 73 232 355 Transparent 38 72 109 303 412 Penetrable 43 169 217 nfa 217 Copyright JamesAllan Page 17 Subjective reactions Subjects liked the penetrable version Subjects in opaque condition expressed desire to see and control wnat happened Subjects comments that feedback made them lazy 7 Task of generating terms changed to task of selecting terms Copynghl James Allan Pseudorelevance feedback True relevance feedback is supervised 7 Feedback is done based on genuine user annotations What happens if we try to guess what is relevant I Assume many top ranked documents are relevant 7 Optionally find a collection of probably nonrelevant documents Modify query on that assumption Rerun that new query and show results to user What happens Pseudorelevance feedback 7 Blind relevance feedback 7 Local feedback Copynghl James Allan Page 18 18 History Attar and Fraenkel JACM 1977 7 Local Feedback in FullText Retrieval Systems 7 Small databases 75 US patents in electronics 7 queries Some work with 2500 documents in Hebrew 7 Showed clear gain from local dynamic feedback 7 Helped to weight candidate terms by proximity Idea seems to have been largely ignored for 16 years 7 In published results at least Copynghl JamesAllan History modern Rediscovered in TREC2 1993 Robertson Walker et al City University of London 7 OkapiatTREC2 Also done by UCLA and CMUClaritech Procedure 7 Used top 30 retrieved documents 7 Added as many terms as half the length of the query TR EC2 had very long queries 3050 words Example topic 112 funding biotechnology 7 Added phramaceut financ partner drug investor techno09139 company industri and develop Results 7 Average precision went from 373 to 407 7 Not huge but noticeable in an environment like TREC 7 NOTE 25 queries improved 18 got worse and 7 didn t change Copynghl JamesAllan Page 19 19 Example of impact Au uu Queries Evans and Leefens Design and Evaluation ufme CLARIT TRECVZ Systemquot Capynght JamsAllAn History continued Mdely adopted in TREC3 Okapi at TREC3quot Robertson et al 7 Added Ll to 40 terrns averaging around 20 additions Automatic query expansion using Smartquot Buckley et al 7 Massive expansion 500 terrns and to pnrasesi TREC2 Using PIRCSquot Kwok et al 7 Spreading activationtriggered by six toprranked documents 7 On average added ii new terrns UMass Amherst CllR s run still a holdout 7 Used a global type ofquery expansion lnFinder Attar and Fraenkel compared theirlucal feedbacktecnniquetu such an approach 7 By TREO5 nad local context analysis as a passageerocdsed Variatiol i on expansion Continues in TREC4 but new ranking function dominates r Tne Okapl trquot function appeared in TREOS Capynght JamsAllAn Page 20 20 Why in 1993 but not 1977 Attar and Fraenkel showed suggestive results But techniques generally went awry 7 Still did in 1993 but helped more than it hurt 7 Standard class project in some IR classes in 19805 didn t work well Nature of TREC collections different 7 More relevant documents per query increases chance of hit 7 Better retrieval algorithms also increases chance of hit 7 Longer documents so more term usage to help find good ones Still widely used 7 ln vector space model systems 7 Language modeling approaches incorporate similar ideas as part of smoothing technique 7 Also explicitly considered as part of relevance models Copynghl James Allan Local Context Analysis LCA Xu and Croft 1996 Assumed relevance feedback Observations 7 tXIsting techniques Improved queries on average 7 But some queries had serious drop in effectiveness 7 Top ranked documents were not always right 7 Often caused by match of a single query word 7 Not every word is useful to add to queries Inspired creation of LCA Major focus is on getting better terms nsion 7 Finding terms to consider 7 Selection of terms 7 Weighting of selected terms Copynghl James Allan Page 21 21 Finding candidate terms Run query to retrieve passages 7 Similar to most assumed relevance work 7 Passageretrieval unique to LCA at the time 7 Uses 300word passages Select expansion concepts from retrieved set Why passages 7 Minimizes spurious concepts that occur in lengthy documents Copynghl JamesAllan Selecting candidate terms Parse document collection Generate part of speech tagging 7 TheATWhasHVZ beenBEN reworkedVBN sinceCS itJPPS wasBEDZ introducedVBN inIN MONO meetJVB someDTI quot ButJCC theAT onIN muchAP ofIN theAT M Select only noun phrases 7 Shown to be critical in most retrieval systems 7 Generally particularly useful for expansion 7 Could easily be extended if useful Adjectivenoun phrases verbs 7 Note that tagging is automated so makes mistakes Copynghl JamesAllan Page 22 22 Weighting terms Want concepts that occur near query words The more query words they occur near the better Count cooccurrences in 300 a windows of text passages To avoid coincidental cooccurrence in a large document Uses the following adhoc function to weight concepts fcQ H 001codegreecwiidfwi wiEQ E 1 lm ortance of word codegreecw max new Cw 0 p no nwnc Emma N Measure cooccurrence ide min100910Nnw5 Floor the IDF component Slow its growth Copyright James Allan Using expanded query Developed using lnquery Incorporate using weighted sum vvelgnt original query and expanSIon query equally Qnew Wsum Qoriginal 10 Qlca Qlcawsum1010 c110 c210 C30 Variations Lower weight on each subsequent term More important the more terms that are added Weight original query equally with a single expansion concept Only works when query is not very reliable Copyright James Allan Page 23 23 Example of expansion concepts TREC query 213 As a result of DNA testing are more defendants being absolved or convicted of crimes Expansion concepts dnapattern dnatesting lifecodes dna test results dnalab dnaevidence dna test dna profile defenseattorneys challenging reIia bility bureauexpert lawyerpeter ne ufeld newyo rk citym urde rcase michael baird procedurestrack record dna la boratory oregon rape case markstorolow laboratorygeletin supermarketmerchandise thomas caskey procedureslifecode lifecodescorp testsrelia bility maine case ra pe conviction dnastrand Copyright lames Allan Does it work TREC3 and TREC4 adhoc queries With and without LCA expansion 1319350 CAI dm kPE 50 151195 Predsitm clmngt r 49 queries Recall baseline wrpusquery Recall baseline musquay 0 322 353 33 0 710 704 03 10 573 651 135 10 493 513 100 20 162 r17 185 20 450 116 30 391 468 193 30 377 134 lt10 327 400 221 40 326 194 50 275 346 253 50 274 267 60 226 284 252 I60 208 4037 70 180 230 273 70 136 133 81 133 1711 307 30 82 333 90 70 107 314 90 12 312 100 05 07 363 100 06 367 Average 316 370 170 average 286 137 TREC3 TREC4 Copyright lames Allan Page 24 24 Summary Relevance feedback Real or assumed Real relevance feedback Usually improves effectiveness significantly Not always stable with very few documents judged Difficult to incorporate into a usable system 7 Find similar is a simple instance that does appear Pseudorelevance feedback Also called blind relevance feedback or local feedback Or quasirelevance feedbackquot or Rocchiobased approaches effective but unstable LCA comparably effective maybe better but more stable Relevance models soon provide formal framework Copynghl JamesAllan Page 25 25
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'