An introduction to information retrieval. Manning_ Raghavan (2009) (811397), страница 55
Текст из файла (страница 55)
The resulting quantity used for ranking iscalled the Retrieval Status Value (RSV) in this model:RSVd = logp t (1 − u t )p t (1 − u t )= ∑ logu (1 − p t )u t (1 − p t )t:x =q =1t:x =q =1 t∏ttttSo everything comes down to computing the RSV. Define ct :(11.18)ODDS RATIOct = logpt1 − utp t (1 − u t )= log+ logu t (1 − p t )(1 − p t )utThe ct terms are log odds ratios for the terms in the query. We have theodds of the term appearing if the document is relevant (pt /(1 − pt )) and theodds of the term appearing if the document is nonrelevant (ut /(1 − ut )).
Theodds ratio is the ratio of two such odds, and then we finally take the log of thatquantity. The value will be 0 if a term has equal odds of appearing in relevantand nonrelevant documents, and positive if it is more likely to appear inrelevant documents. The ct quantities function as term weights in the model,and the document score for a query is RSVd = ∑ xt =qt =1 ct . Operationally, wesum them in accumulators for query terms appearing in documents, just asfor the vector space model calculations discussed in Section 7.1 (page 135).We now turn to how we estimate these ct quantities for a particular collectionand query.Online edition (c) 2009 Cambridge UP22611 Probabilistic information retrieval11.3.2Probability estimates in theoryFor each term t, what would these ct numbers look like for the whole collection? (11.19) gives a contingency table of counts of documents in the collection, where dft is the number of documents that contain term t:(11.19)Term presentTerm absentdocumentsxt = 1xt = 0TotalrelevantsS−sSnonrelevantdft − s( N − dft ) − (S − s)N−STotaldftN − dftNUsing this, pt = s/S and ut = (dft − s)/( N − S) and(11.20)ct = K ( N, dft , S, s) = logs/(S − s)(dft − s)/(( N − dft ) − (S − s))To avoid the possibility of zeroes (such as if every or no relevant documenthas a particular term) it is fairly standard to add 12 to each of the quantitiesin the center 4 terms of (11.19), and then to adjust the marginal counts (thetotals) accordingly (so, the bottom right cell totals N + 2).
Then we have:(11.21)RELATIVE FREQUENCYMAXIMUM LIKELIHOODESTIMATEMLESMOOTHINGPSEUDOCOUNTSB AYESIAN PRIORĉt = K ( N, dft , S, s) = log(s + 21 )/(S − s + 12 )(dft − s + 21 )/( N − dft − S + s + 12 )Adding 12 in this way is a simple form of smoothing. For trials with categorical outcomes (such as noting the presence or absence of a term), oneway to estimate the probability of an event from data is simply to count thenumber of times an event occurred divided by the total number of trials.This is referred to as the relative frequency of the event.
Estimating the probability as the relative frequency is the maximum likelihood estimate (or MLE),because this value makes the observed data maximally likely. However, ifwe simply use the MLE, then the probability given to events we happened tosee is usually too high, whereas other events may be completely unseen andgiving them as a probability estimate their relative frequency of 0 is both anunderestimate, and normally breaks our models, since anything multipliedby 0 is 0. Simultaneously decreasing the estimated probability of seen eventsand increasing the probability of unseen events is referred to as smoothing.One simple way of smoothing is to add a number α to each of the observedcounts. These pseudocounts correspond to the use of a uniform distributionover the vocabulary as a Bayesian prior, following Equation (11.4).
We initially assume a uniform distribution over events, where the size of α denotesthe strength of our belief in uniformity, and we then update the probabilitybased on observed events. Since our belief in uniformity is weak, we useOnline edition (c) 2009 Cambridge UP11.3 The Binary Independence ModelMAXIMUM APOSTERIORIMAP11.3.3227α = 12 . This is a form of maximum a posteriori (MAP) estimation, where wechoose the most likely point value for probabilities based on the prior andthe observed evidence, following Equation (11.4). We will further discussmethods of smoothing estimated counts to give probability models in Section 12.2.2 (page 243); the simple method of adding 21 to each observed countwill do for now.Probability estimates in practiceUnder the assumption that relevant documents are a very small percentageof the collection, it is plausible to approximate statistics for nonrelevant documents by statistics from the whole collection.
Under this assumption, ut(the probability of term occurrence in nonrelevant documents for a query) isdft /N and(11.22)log[(1 − ut )/ut ] = log[( N − dft )/dft ] ≈ log N/dftIn other words, we can provide a theoretical justification for the most frequently used form of idf weighting, which we saw in Section 6.2.1.The approximation technique in Equation (11.22) cannot easily be extendedto relevant documents. The quantity pt can be estimated in various ways:1. We can use the frequency of term occurrence in known relevant documents (if we know some). This is the basis of probabilistic approaches torelevance feedback weighting in a feedback loop, discussed in the nextsubsection.2.
Croft and Harper (1979) proposed using a constant in their combinationmatch model. For instance, we might assume that pt is constant over allterms x t in the query and that pt = 0.5. This means that each term haseven odds of appearing in a relevant document, and so the pt and (1 − pt )factors cancel out in the expression for RSV. Such an estimate is weak, butdoesn’t disagree violently with our hopes for the search terms appearingin many but not all relevant documents. Combining this method with ourearlier approximation for ut , the document ranking is determined simplyby which query terms occur in documents scaled by their idf weighting.For short documents (titles or abstracts) in situations in which iterativesearching is undesirable, using this weighting term alone can be quitesatisfactory, although in many other circumstances we would like to dobetter.3. Greiff (1998) argues that the constant estimate of pt in the Croft and Harper(1979) model is theoretically problematic and not observed empirically: asmight be expected, pt is shown to rise with dft .
Based on his data analysis,a plausible proposal would be to use the estimate p t = 13 + 23 dft /N.Online edition (c) 2009 Cambridge UP22811 Probabilistic information retrievalIterative methods of estimation, which combine some of the above ideas,are discussed in the next subsection.11.3.4Probabilistic approaches to relevance feedbackWe can use (pseudo-)relevance feedback, perhaps in an iterative process ofestimation, to get a more accurate estimate of pt . The probabilistic approachto relevance feedback works as follows:1. Guess initial estimates of p t and ut . This can be done using the probabilityestimates of the previous section. For instance, we can assume that pt isconstant over all xt in the query, in particular, perhaps taking p t = 21 .2.
Use the current estimates of p t and ut to determine a best guess at the setof relevant documents R = {d : Rd,q = 1}. Use this model to retrieve a setof candidate relevant documents, which we present to the user.3. We interact with the user to refine the model of R. We do this by learning from the user relevance judgments for some subset of documents V.Based on relevance judgments, V is partitioned into two subsets: VR ={d ∈ V, Rd,q = 1} ⊂ R and VNR = {d ∈ V, Rd,q = 0}, which is disjointfrom R.(11.23)4.
We reestimate pt and ut on the basis of known relevant and nonrelevantdocuments. If the sets VR and VNR are large enough, we may be ableto estimate these quantities directly from these documents as maximumlikelihood estimates:pt = |VRt |/|VR|(where VRt is the set of documents in VR containing xt ). In practice,we usually need to smooth these estimates. We can do this by adding12 to both the count |VRt | and to the number of relevant documents notcontaining the term, giving:(11.24)(11.25)pt =|VRt | + 12|VR| + 1However, the set of documents judged by the user (V) is usually verysmall, and so the resulting statistical estimate is quite unreliable (noisy),even if the estimate is smoothed. So it is often better to combine the newinformation with the original guess in a process of Bayesian updating.
Inthis case we have:(k)|VRt | + κ pt( k +1 )pt=|VR| + κOnline edition (c) 2009 Cambridge UP22911.3 The Binary Independence Model(k)Here pt is the kth estimate for pt in an iterative updating process andis used as a Bayesian prior in the next iteration with a weighting of κ.Relating this equation back to Equation (11.4) requires a bit more probability theory than we have presented here (we need to use a beta distribution prior, conjugate to the Bernoulli random variable Xt ). But the formof the resulting equation is quite straightforward: rather than uniformlydistributing pseudocounts, we now distribute a total of κ pseudocountsaccording to the previous estimate, which acts as the prior distribution.In the absence of other evidence (and assuming that the user is perhapsindicating roughly 5 relevant or nonrelevant documents) then a valueof around κ = 5 is perhaps appropriate.
That is, the prior is stronglyweighted so that the estimate does not change too much from the evidence provided by a very small number of documents.5. Repeat the above process from step 2, generating a succession of approximations to R and hence p t , until the user is satisfied.It is also straightforward to derive a pseudo-relevance feedback version ofthis algorithm, where we simply pretend that VR = V. More briefly:1. Assume initial estimates for pt and ut as above.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
