Question? Leave a message!




Probabilistic Approach to Retrieval

Probabilistic Approach to Retrieval
Introduction to Information Retrieval Introduction to Information Retrieval Probabilistic Information Retrieval 1Introduction to Information Retrieval Overview ❶ Probabilistic Approach to Retrieval ❷ Basic Probability Theory ❸ Probability Ranking Principle ❹ Appraisal & Extensions 2Introduction to Information Retrieval Outline ❶ Probabilistic Approach to Retrieval ❷ Basic Probability Theory ❸ Probability Ranking Principle ❹ Appraisal & Extensions 3Introduction to Information Retrieval Probabilistic Approach to Retrieval  Given a user information need (represented as a query) and a collection of documents (transformed into document representations), a system must determine how well the documents satisfy the query  Boolean or vector space models of IR: query-document matching done in a formally defined but semantically imprecise calculus of index terms  An IR system has an uncertain understanding of the user query , and makes an uncertain guess of whether a document satisfies the query  Probability theory provides a principled foundation for such reasoning under uncertainty  Probabilistic models exploit this foundation to estimate how likely it is that a document is relevant to a query 4 4Introduction to Information Retrieval Probabilistic IR Models at a Glance  Classical probabilistic retrieval model  Probability ranking principle  Binary Independence Model, BestMatch25 (Okapi)  Bayesian networks for text retrieval  Language model approach to IR  Important recent work, competitive performance Probabilistic methods are one of the oldest but also one of the currently hottest topics in IR 5 5Introduction to Information Retrieval Outline ❶ Probabilistic Approach to Retrieval ❷ Basic Probability Theory ❸ Probability Ranking Principle ❹ Appraisal & Extensions 6Introduction to Information Retrieval Basic Probability Theory  For events A and B  Joint probability P(A, B) of both events occurring  Conditional probability P(AB) of event A occurring given that event B has occurred  Chain rule gives fundamental relationship between joint and conditional probabilities:  Similarly for the complement of an event :  Partition rule: if B can be divided into an exhaustive set of disjoint subcases, then P(B) is the sum of the probabilities of the subcases. A special case of this rule gives: 7 7Introduction to Information Retrieval Basic Probability Theory Bayes’ Rule for inverting conditional probabilities: Can be thought of as a way of updating probabilities:  Start off with prior probability P(A) (initial estimate of how likely event A is in the absence of any other information)  Derive a posterior probability P(AB) after having seen the evidence B, based on the likelihood of B occurring in the two cases that A does or does not hold Odds of an event provide a kind of multiplier for how probabilities change: Odds: 8 8Introduction to Information Retrieval Outline ❶ Probabilistic Approach to Retrieval ❷ Basic Probability Theory ❸ Probability Ranking Principle ❹ Appraisal & Extensions 9Introduction to Information Retrieval The Document Ranking Problem  Ranked retrieval setup: given a collection of documents, the user issues a query, and an ordered list of documents is returned  Assume binary notion of relevance: R is a random d,q dichotomous variable, such that  R = 1 if document d is relevant w.r.t query q d,q  R = 0 otherwise d,q  Probabilistic ranking orders documents decreasingly by their estimated probability of relevance w.r.t. query: P(R = 1d, q) 10 10Introduction to Information Retrieval Probability Ranking Principle (PRP)  PRP in brief  If the retrieved documents (w.r.t a query) are ranked decreasingly on their probability of relevance, then the effectiveness of the system will be the best that is obtainable  PRP in full  If the IR+ system’s response to each query+ is a ranking of the documents ... in order of decreasing probability of relevance to the query, where the probabilities are estimated as accurately as possible on the basis of whatever data have been made available to the system for this purpose, the overall effectiveness of the system to its user will be the best that is obtainable on the basis of those data 11 11Introduction to Information Retrieval Binary Independence Model (BIM)  Traditionally used with the PRP Assumptions:  ‘Binary’ (equivalent to Boolean): documents and queries represented as binary term incidence vectors   E.g., document d represented by vector x = (x , . . . , x ), where 1 M x = 1 if term t occurs in d and x = 0 otherwise t t  Different documents may have the same vector representation  ‘Independence’: no association between terms (not true, but practically works - ‘naive’ assumption of Naive Bayes models) 12 12Introduction to Information Retrieval Binary Independence Model To make a probabilistic retrieval strategy precise, need to estimate how terms in documents contribute to relevance  Find measurable statistics (term frequency, document frequency, document length) that affect judgments about document relevance  Combine these statistics to estimate the probability of document relevance  Order documents by decreasing estimated probability of relevance P(Rd, q)  Assume that the relevance of each document is independent of the relevance of other documents (not true, in practice allows duplicate results) 13 13Introduction to Information Retrieval Binary Independence Model is modelled using term incidence vectors as  and : : probability that if a relevant or nonrelevant document is retrieved, then that document’s representation is  Statistics about the actual document collection are used to estimate these probabilities 14 14Introduction to Information Retrieval Binary Independence Model is modelled using term incidence vectors as  and : prior probability of retrieving a relevant or nonrelevant document for a query q  Estimate and from percentage of relevant documents in the collection  Since a document is either relevant or nonrelevant to a query, we must have that: 15 15Introduction to Information Retrieval Deriving a Ranking Function for Query Terms  Given a query q, ranking documents by is modeled under BIM as ranking them by  Easier: rank documents by their odds of relevance (gives same ranking & we can ignore the common denominator)  is a constant for a given query - can be ignored 16 16Introduction to Information Retrieval Deriving a Ranking Function for Query Terms It is at this point that we make the Naive Bayes conditional independence assumption that the presence or absence of a word in a document is independent of the presence or absence of any other word (given the query): So: 17 17Introduction to Information Retrieval Deriving a Ranking Function for Query Terms Since each x is either 0 or 1, we can separate the terms to give: t  Let be the probability of a term appearing in relevant document  Let be the probability of a term appearing in a nonrelevant document Visualise as contingency table: 18 18Introduction to Information Retrieval Deriving a Ranking Function for Query Terms Additional simplifying assumption: terms not occurring in the query are equally likely to occur in relevant and nonrelevant documents  If q = 0, then p = u t t t Now we need only to consider terms in the products that appear in the query:  The left product is over query terms found in the document and the right product is over query terms not found in the document 19 19Introduction to Information Retrieval Deriving a Ranking Function for Query Terms Including the query terms found in the document into the right product, but simultaneously dividing through by them in the left product, gives:  The left product is still over query terms found in the document, but the right product is now over all query terms, hence constant for a particular query and can be ignored. The only quantity that needs to be estimated to rank documents w.r.t a query is the left product  Hence the Retrieval Status Value (RSV) in this model: 20 20Introduction to Information Retrieval Deriving a Ranking Function for Query Terms So everything comes down to computing the RSV . We can equally rank documents using the log odds ratios for the terms in the query c : t  The odds ratio is the ratio of two odds: (i) the odds of the term appearing if the document is relevant (p /(1 − p )), and (ii) the odds t t of the term appearing if the document is nonrelevant (u /(1 − u )) t t  c = 0 if a term has equal odds of appearing in relevant and t nonrelevant documents, and ct is positive if it is more likely to appear in relevant documents  c functions as a term weight, so that t Operationally, we sum ct quantities in accumulators for query terms appearing in documents, just as for the vector space model calculations 21 21Introduction to Information Retrieval Deriving a Ranking Function for Query Terms For each term t in a query, estimate c in the whole collection t using a contingency table of counts of documents in the collection, where df t is the number of documents that contain term t: To avoid the possibility of zeroes (such as if every or no relevant document has a particular term) there are different ways to apply smoothing 22 22Introduction to Information Retrieval Exercise  Query: Obama health plan  Doc1: Obama rejects allegations about his own bad health  Doc2: The plan is to visit Obama  Doc3: Obama raises concerns with US health plan reforms Estimate the probability that the above documents are relevant to the query. Use a contingency table. These are the only three documents in the collection 23 23Introduction to Information Retrieval Probability Estimates in Practice  Assuming that relevant documents are a very small percentage of the collection, approximate statistics for nonrelevant documents by statistics from the whole collection  Hence, u (the probability of term occurrence in nonrelevant t documents for a query) is df /N and t log(1 − u )/u = log(N − df )/df ≈ log N/df t t t t t  The above approximation cannot easily be extended to relevant documents 24 24Introduction to Information Retrieval Prabability Estimates in Practice Statistics of relevant documents (p ) can be estimated in various t ways: ❶ Use the frequency of term occurrence in known relevant documents (if known). This is the basis of probabilistic approaches to relevance feedback weighting in a feedback loop ❷ Set as constant. E.g., assume that pt is constant over all terms x in t the query and that p = 0.5 t  Each term is equally likely to occur in a relevant document, and so the pt and (1 − p ) factors cancel out in the expression for RSV t  Weak estimate, but doesn’t disagree violently with expectation that query terms appear in many but not all relevant documents  Combining this method with the earlier approximation for u , the t document ranking is determined simply by which query terms occur in documents scaled by their idf weighting  For short documents (titles or abstracts) in one-pass retrieval situations, this estimate can be quite satisfactory 25Introduction to Information Retrieval Outline ❶ Probabilistic Approach to Retrieval ❷ Basic Probability Theory ❸ Probability Ranking Principle ❹ Appraisal & Extensions 26Introduction to Information Retrieval An Appraisal of Probabilistic Models  Among the oldest formal models in IR  Maron & Kuhns, 1960: Since an IR system cannot predict with certainty which document is relevant, we should deal with probabilities  Assumptions for getting reasonable approximations of the needed probabilities (in the BIM):  Boolean representation of documents/queries/relevance  Term independence  Out-of-query terms do not affect retrieval  Document relevance values are independent 27Introduction to Information Retrieval An Appraisal of Probabilistic Models  The difference between ‘vector space’ and ‘probabilistic’ IR is not that great:  In either case you build an information retrieval scheme in the exact same way.  Difference: for probabilistic IR, at the end, you score queries not by cosine similarity and tf-idf in a vector space, but by a slightly different formula motivated by probability theory 28Introduction to Information Retrieval Okari BM25: A Nonbinary Model  The BIM was originally designed for short catalog records of fairly consistent length, and it works reasonably in these contexts  For modern full-text search collections, a model should pay attention to term frequency and document length  BestMatch25 (a.k.a BM25 or Okapi) is sensitive to these quantities  From 1994 until today, BM25 is one of the most widely used and robust retrieval models 29Introduction to Information Retrieval Okari BM25: A Nonbinary Model  The simplest score for document d is just idf weighting of the query terms present in the document:  Improve this formula by factoring in the term frequency and document length:  tf : term frequency in document d td  L (Lave): length of document d (average document length in the d whole collection)  k : tuning parameter controlling the document term frequency 1 scaling  b: tuning parameter controlling the scaling by document length 30Introduction to Information Retrieval Okari BM25: A Nonbinary Model  If the query is long, we might also use similar weighting for query terms  tf : term frequency in the query q tq  k : tuning parameter controlling term frequency scaling of the 3 query  No length normalisation of queries (because retrieval is being done with respect to a single fixed query)  The above tuning parameters should ideally be set to optimize performance on a development test collection. In the absence of such optimisation, experiments have shown reasonable values are to set k and k to a value between 1.2 and 2 and b = 0.75 1 3 31Introduction to Information Retrieval Recap  Probabilistically grounded approach to IR  Probability Ranking Principle  Models: BIM, BM25  Assumptions 32Introduction to Information Retrieval Resources  TheChapter 11 of IIR  Resources athttp://ifnlp.org/ir 33
Website URL
Comment