Query OperationsRecap: Unranked retrieval evaluation: Precision and RecallEvaluation of large search enginesThis lectureRelevance FeedbackRelevance FeedbackRelevance feedbackRelevance Feedback: ExampleResults for Initial QuerySlide 10Results after Relevance FeedbackInitial query/resultsExpanded query after relevance feedbackResults for expanded queryKey concept: CentroidRocchio AlgorithmThe Theoretically Best QueryRocchio 1971 Algorithm (SMART)Subtleties to noteRelevance feedback on initial queryRelevance Feedback in vector spacesPositive vs Negative FeedbackRelevance Feedback: AssumptionsViolation of A1Violation of A2Relevance Feedback: ProblemsEvaluation of relevance feedback strategiesEvaluation of relevance feedbackEvaluation: CaveatExcite Relevance FeedbackPseudo relevance feedbackRelevance Feedback :SummaryOther Uses of Relevance FeedbackIndirect relevance feedbackQuery ExpansionQuery ExpansionQuery assist : ExampleQuery expansion: ExampleQuery assist: ExampleHow do we augment the user query?Example of manual thesaurusThesaurus-based query expansionAutomatic Thesaurus GenerationCo-occurrence ThesaurusAutomatic Thesaurus Generation ExampleAutomatic Thesaurus Generation DiscussionQuery assistPrasad L11QueryOps 1Query OperationsAdapted from Lectures by Prabhakar Raghavan (Yahoo, Stanford) and Christopher Manning (Stanford)2Recap: Unranked retrieval evaluation:Precision and RecallPrecision: fraction of retrieved docs that are relevant = P(relevant|retrieved)Recall : fraction of relevant docs that are retrieved = P(retrieved|relevant)Precision P = tp/(tp + fp)Recall R = tp/(tp + fn)Relevant NonrelevantRetrieved tp fpNot Retrieved fn tnPrasadEvaluation of large search enginesSearch engines have test collections of queries and hand-ranked resultsRecall is difficult to measure on the webSearch engines often use precision at top k, e.g., k = 10. . . or measures that reward you more for getting rank 1 right than for getting rank 10 right.NDCG (Normalized Cumulative Discounted Gain)Search engines also use non-relevance-based measures.Clickthrough on first resultNot very reliable if you look at a single clickthrough … but pretty reliable in the aggregate.Studies of user behavior in the labA/B testing3L11QueryOpsThis lectureImproving resultsFor high recall. E.g., searching for aircraft doesn’t match with plane; nor thermodynamic with heatFor gleaning user intent from queries The complete landscapeGlobal methodsQuery expansionThesauriAutomatic thesaurus generationLocal methodsRelevance feedbackPseudo relevance feedbackPrasad 4L11QueryOps5Relevance FeedbackRelevance FeedbackIdea: it may be difficult to formulate a good query when you don’t know the collection well, or cannot express it, but can judge relevance of a result. So iterate …User feedback on relevance of docs in initial set of resultsUser issues a (short, simple) queryThe user marks some results as relevant or non-relevant.The system computes a better representation of the information need based on feedback.Relevance feedback can go through one or more iterations.Prasad 6L11QueryOpsRelevance feedbackWe will use ad hoc retrieval to refer to regular retrieval without relevance feedback.We now look at examples of relevance feedback that highlight different aspects.Prasad 7L11QueryOpsRelevance Feedback: ExampleImage search engine http://nayana.ece.ucsb.edu/imsearch/imsearch.htmlResults for Initial Query9.1.1Prasad 9L11QueryOpsRelevance Feedback9.1.1Results after Relevance Feedback9.1.1Prasad 11L11QueryOpsInitial query/resultsInitial query: New space satellite applications1. 0.539, 08/13/91, NASA Hasn’t Scrapped Imaging Spectrometer2. 0.533, 07/09/91, NASA Scratches Environment Gear From Satellite Plan3. 0.528, 04/04/90, Science Panel Backs NASA Satellite Plan, But Urges Launches of Smaller Probes4. 0.526, 09/09/91, A NASA Satellite Project Accomplishes Incredible Feat: Staying Within Budget5. 0.525, 07/24/90, Scientist Who Exposed Global Warming Proposes Satellites for Climate Research6. 0.524, 08/22/90, Report Provides Support for the Critics Of Using Big Satellites to Study Climate7. 0.516, 04/13/87, Arianespace Receives Satellite Launch Pact From Telesat Canada8. 0.509, 12/02/87, Telecommunications Tale of Two CompaniesUser then marks relevant documents with “+”.+++9.1.1Prasad 12L11QueryOpsExpanded query after relevance feedback2.074 new 15.106 space30.816 satellite 5.660 application5.991 nasa 5.196 eos4.196 launch 3.972 aster3.516 instrument 3.446 arianespace3.004 bundespost 2.806 ss2.790 rocket 2.053 scientist2.003 broadcast 1.172 earth0.836 oil 0.646 measure9.1.1Prasad 13L11QueryOpsResults for expanded query1. 0.513, 07/09/91, NASA Scratches Environment Gear From Satellite Plan2. 0.500, 08/13/91, NASA Hasn’t Scrapped Imaging Spectrometer3. 0.493, 08/07/89, When the Pentagon Launches a Secret Satellite, Space Sleuths Do Some Spy Work of Their Own4. 0.493, 07/31/89, NASA Uses ‘Warm’ Superconductors For Fast Circuit5. 0.492, 12/02/87, Telecommunications Tale of Two Companies6. 0.491, 07/09/91, Soviets May Adapt Parts of SS-20 Missile For Commercial Use7. 0.490, 07/12/88, Gaping Gap: Pentagon Lags in Race To Match the Soviets In Rocket Launchers8. 0.490, 06/14/90, Rescue of Satellite By Space Agency To Cost $90 Million2189.1.1Prasad 14L11QueryOpsKey concept: CentroidThe centroid is the center of mass of a set of pointsRecall that we represent documents as points in a high-dimensional spaceDefinition: Centroidwhere C is a set of documents.CddCC||1)(9.1.1Prasad 15L11QueryOpsRocchio AlgorithmThe Rocchio algorithm uses the vector space model to pick a relevance fed-back queryRocchio seeks the query qopt that maximizesTries to separate docs marked relevant and non-relevantProblem: we don’t know the truly relevant docs))](,cos())(,[cos(maxargnrrqoptCqCqqrjrjCdjnrCdjroptdCdCq119.1.1Prasad 16L11QueryOpsThe Theoretically Best Query xxxxoooOptimal queryx non-relevant documentso relevant documentsoooxxxxxxxxxxxxxx9.1.1Rocchio 1971 Algorithm (SMART)Used in practice:Dr = set of known relevant doc vectorsDnr = set of known irrelevant doc vectorsDifferent from Cr and Cnrqm = modified query vector; q0 = original query vector; α,β,γ: weights
View Full Document