An introduction to information retrieval. Manning_ Raghavan (2009) (811397), страница 53
Текст из файла (страница 53)
2005). Chapter 6of Grossman and Frieder (2004) is a good introduction to structured text retrieval from a database perspective. The proposed standard for XQuery isavailable at http://www.w3.org/TR/xquery/ including an extension for full-textqueries (Amer-Yahia et al. 2006): http://www.w3.org/TR/xquery-full-text/. Workthat has looked at combining the relational database and the unstructuredinformation retrieval approaches includes (Fuhr and Rölleke 1997), (Navarroand Baeza-Yates 1997), (Cohen 1998), and (Chaudhuri et al. 2006).10.7Exercises?Exercise 10.4Find a reasonably sized XML document collection (or a collection using a markup language different from XML like HTML) on the web and download it.
Jon Bosak’s XMLedition of Shakespeare and of various religious works at http://www.ibiblio.org/bosak/ orthe first 10,000 documents of the Wikipedia are good choices. Create three CAS topicsOnline edition (c) 2009 Cambridge UP21810 XML retrievalof the type shown in Figure 10.3 that you would expect to do better than analogousCO topics.
Explain why an XML retrieval system would be able to exploit the XMLstructure of the documents to achieve better retrieval results on the topics than anunstructured retrieval system.Exercise 10.5For the collection and the topics in Exercise 10.4, (i) are there pairs of elements e1 ande2 , with e2 a subelement of e1 such that both answer one of the topics? Find one caseeach where (ii) e1 (iii) e2 is the better answer to the query.Exercise 10.6Implement the (i) S IM M ERGE (ii) S IM N O M ERGE algorithm in Section 10.3 and run itfor the collection and the topics in Exercise 10.4.
(iii) Evaluate the results by assigningbinary relevance judgments to the first five documents of the three retrieved lists foreach algorithm. Which algorithm performs better?Exercise 10.7Are all of the elements in Exercise 10.4 appropriate to be returned as hits to a user orare there elements (as in the example <b>definitely</b> on page 203) that youwould exclude?Exercise 10.8We discussed the tradeoff between accuracy of results and dimensionality of the vector space on page 207.
Give an example of an information need that we can answercorrectly if we index all lexicalized subtrees, but cannot answer if we only index structural terms.Exercise 10.9If we index all structural terms, what is the size of the index as a function of text size?Exercise 10.10If we index all lexicalized subtrees, what is the size of the index as a function of textsize?Exercise 10.11Give an example of a query-document pair for which S IM N O M ERGE(q, d) is largerthan 1.0.Online edition (c) 2009 Cambridge UPDRAFT! © April 1, 2009 Cambridge University Press.
Feedback welcome.11219Probabilistic informationretrievalDuring the discussion of relevance feedback in Section 9.1.2, we observedthat if we have some known relevant and nonrelevant documents, then wecan straightforwardly start to estimate the probability of a term t appearingin a relevant document P(t| R = 1), and that this could be the basis of aclassifier that decides whether documents are relevant or not. In this chapter,we more systematically introduce this probabilistic approach to IR, whichprovides a different formal basis for a retrieval model and results in differenttechniques for setting term weights.Users start with information needs, which they translate into query representations.
Similarly, there are documents, which are converted into documentrepresentations (the latter differing at least by how text is tokenized, but perhaps containing fundamentally less information, as when a non-positionalindex is used). Based on these two representations, a system tries to determine how well documents satisfy information needs. In the Boolean orvector space models of IR, matching is done in a formally defined but semantically imprecise calculus of index terms. Given only a query, an IR systemhas an uncertain understanding of the information need.
Given the queryand document representations, a system has an uncertain guess of whethera document has content relevant to the information need. Probability theoryprovides a principled foundation for such reasoning under uncertainty. Thischapter provides one answer as to how to exploit this foundation to estimatehow likely it is that a document is relevant to an information need.There is more than one possible retrieval model which has a probabilisticbasis.
Here, we will introduce probability theory and the Probability Ranking Principle (Sections 11.1–11.2), and then concentrate on the Binary Independence Model (Section 11.3), which is the original and still most influentialprobabilistic retrieval model. Finally, we will introduce related but extendedmethods which use term counts, including the empirically successful OkapiBM25 weighting scheme, and Bayesian Network models for IR (Section 11.4).In Chapter 12, we then present the alternative probabilistic language model-Online edition (c) 2009 Cambridge UP22011 Probabilistic information retrievaling approach to IR, which has been developed with considerable success inrecent years.11.1RANDOM VARIABLECHAIN RULE(11.1)Review of basic probability theoryWe hope that the reader has seen a little basic probability theory previously.We will give a very quick review; some references for further reading appearat the end of the chapter.
A variable A represents an event (a subset of thespace of possible outcomes). Equivalently, we can represent the subset via arandom variable, which is a function from outcomes to real numbers; the subset is the domain over which the random variable A has a particular value.Often we will not know with certainty whether an event is true in the world.We can ask the probability of the event 0 ≤ P( A) ≤ 1. For two events A andB, the joint event of both events occurring is described by the joint probability P( A, B). The conditional probability P( A| B) expresses the probability ofevent A given that event B occurred. The fundamental relationship betweenjoint and conditional probabilities is given by the chain rule:P( A, B) = P( A ∩ B) = P( A| B) P( B) = P( B| A) P( A)Without making any assumptions, the probability of a joint event equals theprobability of one of the events multiplied by the probability of the otherevent conditioned on knowing the first event happened.Writing P( A) for the complement of an event, we similarly have:(11.2)PARTITION RULE(11.3)B AYES ’ R ULE(11.4)PRIOR PROBABILITYPOSTERIORPROBABILITYP( A, B) = P( B| A) P( A)Probability theory also has a partition rule, which says that if an event B canbe divided into an exhaustive set of disjoint subcases, then the probability ofB is the sum of the probabilities of the subcases.
A special case of this rulegives that:P( B) = P( A, B) + P( A, B)From these we can derive Bayes’ Rule for inverting conditional probabilities:#"P( B| A)P( B| A) P( A)P( A)=P( A| B) =P( B)∑ X ∈{ A,A} P( B| X ) P( X )This equation can also be thought of as a way of updating probabilities. Westart off with an initial estimate of how likely the event A is when we donot have any other information; this is the prior probability P( A). Bayes’ rulelets us derive a posterior probability P( A| B) after having seen the evidence B,Online edition (c) 2009 Cambridge UP22111.2 The Probability Ranking PrincipleODDSbased on the likelihood of B occurring in the two cases that A does or does nothold.1Finally, it is often useful to talk about the odds of an event, which providea kind of multiplier for how probabilities change:P( A)P( A)=1 − P( A)P( A)(11.5)Odds:11.2The Probability Ranking Principle11.2.1P ROBABILITYR ANKING P RINCIPLE1/0 LOSSB AYES O PTIMALD ECISION R ULEO( A) =The 1/0 loss caseWe assume a ranked retrieval setup as in Section 6.3, where there is a collection of documents, the user issues a query, and an ordered list of documentsis returned.
We also assume a binary notion of relevance as in Chapter 8. Fora query q and a document d in the collection, let Rd,q be an indicator randomvariable that says whether d is relevant with respect to a given query q. Thatis, it takes on a value of 1 when the document is relevant and 0 otherwise. Incontext we will often write just R for Rd,q .Using a probabilistic model, the obvious order in which to present documents to the user is to rank documents by their estimated probability ofrelevance with respect to the information need: P( R = 1|d, q).
This is the basis of the Probability Ranking Principle (PRP) (van Rijsbergen 1979, 113–114):“If a reference retrieval system’s response to each request is a rankingof the documents in the collection in order of decreasing probabilityof relevance to the user who submitted the request, 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, theoverall effectiveness of the system to its user will be the best that isobtainable on the basis of those data.”In the simplest case of the PRP, there are no retrieval costs or other utilityconcerns that would differentially weight actions or errors.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
