Evaluation measures (information retrieval)

Evaluation measures for an information retrieval system are used to assess how well the search results satisfied the user's query intent. Such metrics are often split into kinds: online metrics look at users' interactions with the search system, while offline metrics measure relevance, in other words how likely each result, or SERP page as a whole, is to meet the information needs of the user.

The mathematical symbols used in the formulas below mean:

$X\cap Y$ - Intersection - in this case, specifying the documents in both sets X and Y
$|X|$ - Cardinality - in this case, the number of documents in set X
$\int$ - Integral
$\sum$ - Summation
$\Delta$ - Symmetric difference

Online metrics

Online metrics are generally created from data mined from search logs. The metrics are often used to determine the success of an A/B test.

Session abandonment rate

Session abandonment rate is a ratio of search session which do not result in a click.

Click-through rate

Click-through rate (CTR) is the ratio of users who click on a specific link to the number of total users who view a page, email, or advertisement. It is commonly used to measure the success of an online advertising campaign for a particular website as well as the effectiveness of email campaigns.^[1]

Session success rate

Session success rate measures the ratio of user sessions that lead to a success. Defining "success" is often dependent on context, but for search a successful result is often measured using dwell time as a primary factor along with secondary user interaction, for instance, the user copying the result URL is considered a successful result, as is copy/pasting from the snippet.

Zero result rate

Zero result rate (ZRR) is the ratio of SERPs which returned with zero results. The metric either indicates a recall issue, or that the information being searched for is not in the index.

Offline metrics

Offline metrics are generally created from relevance judgment sessions where the judges score the quality of the search results. Both binary (relevant/non-relevant) and multi-level (e.g., relevance from 0 to 5) scales can be used to score each document returned in response to a query. In practice, queries may be ill-posed, and there may be different shades of relevance. For instance, there is ambiguity in the query "mars": the judge does not know if the user is searching for the planet Mars, the Mars chocolate bar, or the singer Bruno Mars.

Precision

Precision is the fraction of the documents retrieved that are relevant to the user's information need.

\mbox{precision}=\frac{|\{\mbox{relevant documents}\}\cap\{\mbox{retrieved documents}\}|}{|\{\mbox{retrieved documents}\}|}

In binary classification, precision is analogous to positive predictive value. Precision takes all retrieved documents into account. It can also be evaluated at a given cut-off rank, considering only the topmost results returned by the system. This measure is called precision at n or P@n.

Note that the meaning and usage of "precision" in the field of information retrieval differs from the definition of accuracy and precision within other branches of science and statistics.

Recall

Recall is the fraction of the documents that are relevant to the query that are successfully retrieved.

\mbox{recall}=\frac{|\{\mbox{relevant documents}\}\cap\{\mbox{retrieved documents}\}|}{|\{\mbox{relevant documents}\}|}

In binary classification, recall is often called sensitivity. So it can be looked at as the probability that a relevant document is retrieved by the query.

It is trivial to achieve recall of 100% by returning all documents in response to any query. Therefore, recall alone is not enough but one needs to measure the number of non-relevant documents also, for example by computing the precision.

Fall-out

The proportion of non-relevant documents that are retrieved, out of all non-relevant documents available:

\mbox{fall-out}=\frac{|\{\mbox{non-relevant documents}\}\cap\{\mbox{retrieved documents}\}|}{|\{\mbox{non-relevant documents}\}|}

In binary classification, fall-out is closely related to specificity and is equal to $(1-\mbox{specificity})$ . It can be looked at as the probability that a non-relevant document is retrieved by the query.

It is trivial to achieve fall-out of 0% by returning zero documents in response to any query.

F-score / F-measure

The weighted harmonic mean of precision and recall, the traditional F-measure or balanced F-score is:

F={\frac {2\cdot {\mathrm {precision}}\cdot {\mathrm {recall}}}{({\mathrm {precision}}+{\mathrm {recall}})}}

This is also known as the $F_{1}$ measure, because recall and precision are evenly weighted.

The general formula for non-negative real $\beta$ is:

F_\beta = \frac{(1 + \beta^2) \cdot (\mathrm{precision} \cdot \mathrm{recall})}{(\beta^2 \cdot \mathrm{precision} + \mathrm{recall})}\,

Two other commonly used F measures are the $F_{2}$ measure, which weights recall twice as much as precision, and the $F_{0.5}$ measure, which weights precision twice as much as recall.

The F-measure was derived by van Rijsbergen (1979) so that $F_{\beta }$ "measures the effectiveness of retrieval with respect to a user who attaches $\beta$ times as much importance to recall as precision". It is based on van Rijsbergen's effectiveness measure $E=1-{\frac {1}{{\frac {\alpha }{P}}+{\frac {1-\alpha }{R}}}}$ . Their relationship is:

F_{\beta }=1-E

where

\alpha ={\frac {1}{1+\beta ^{2}}}

F-measure can be a better single metric when compared to precision and recall; both precision and recall give different information that can complement each other when combined. If one of them excels more than the other, F-measure will reflect it.

Average precision

Precision and recall are single-value metrics based on the whole list of documents returned by the system. For systems that return a ranked sequence of documents, it is desirable to also consider the order in which the returned documents are presented. By computing a precision and recall at every position in the ranked sequence of documents, one can plot a precision-recall curve, plotting precision $p(r)$ as a function of recall $r$ . Average precision computes the average value of $p(r)$ over the interval from $r=0$ to $r=1$ :^[2]

\operatorname{AveP} = \int_0^1 p(r)dr

That is the area under the precision-recall curve. This integral is in practice replaced with a finite sum over every position in the ranked sequence of documents:

\operatorname{AveP} = \sum_{k=1}^n P(k) \Delta r(k)

where $k$ is the rank in the sequence of retrieved documents, $n$ is the number of retrieved documents, $P(k)$ is the precision at cut-off $k$ in the list, and $\Delta r(k)$ is the change in recall from items $k-1$ to $k$ .^[2]

This finite sum is equivalent to:

\operatorname{AveP} = \frac{\sum_{k=1}^n (P(k) \times \operatorname{rel}(k))}{\mbox{number of relevant documents}} \!

where $\operatorname{rel}(k)$ is an indicator function equaling 1 if the item at rank $k$ is a relevant document, zero otherwise.^[3] Note that the average is over all relevant documents and the relevant documents not retrieved get a precision score of zero.

Some authors choose to interpolate the $p(r)$ function to reduce the impact of "wiggles" in the curve.^[4]^[5] For example, the PASCAL Visual Object Classes challenge (a benchmark for computer vision object detection) computes average precision by averaging the precision over a set of evenly spaced recall levels {0, 0.1, 0.2, ... 1.0}:^[4]^[5]

\operatorname{AveP} = \frac{1}{11} \sum_{r \in \{0, 0.1, \ldots, 1.0\}} p_{\operatorname{interp}}(r)

where $p_{\operatorname{interp}}(r)$ is an interpolated precision that takes the maximum precision over all recalls greater than $r$ :

p_{\operatorname{interp}}(r) = \operatorname{max}_{\tilde{r}:\tilde{r} \geq r} p(\tilde{r})

An alternative is to derive an analytical $p(r)$ function by assuming a particular parametric distribution for the underlying decision values. For example, a binormal precision-recall curve can be obtained by assuming decision values in both classes to follow a Gaussian distribution.^[6]

Precision at K

For modern (Web-scale) information retrieval, recall is no longer a meaningful metric, as many queries have thousands of relevant documents, and few users will be interested in reading all of them. Precision at k documents (P@k) is still a useful metric (e.g., P@10 or "Precision at 10" corresponds to the number of relevant results on the first search results page), but fails to take into account the positions of the relevant documents among the top k. Another shortcoming is that on a query with fewer relevant results than k, even a perfect system will have a score less than 1.^[7] It is easier to score manually since only the top k results need to be examined to determine if they are relevant or not.

R-Precision

R-precision requires knowing all documents that are relevant to a query. The number of relevant documents, $R$ , is used as the cutoff for calculation, and this varies from query to query. For example, if there are 15 documents relevant to "red" in a corpus (R=15), R-precision for "red" looks at the top 15 documents returned, counts the number that are relevant $r$ turns that into a relevancy fraction: $r/R=r/15$ .^[8]

Precision is equal to recall at the R-th position.^[7]

Empirically, this measure is often highly correlated to mean average precision.^[7]

Mean average precision

Mean average precision for a set of queries is the mean of the average precision scores for each query.

\operatorname{MAP} = \frac{\sum_{q=1}^Q \operatorname{AveP(q)}}{Q} \!

where Q is the number of queries.

Discounted cumulative gain

DCG uses a graded relevance scale of documents from the result set to evaluate the usefulness, or gain, of a document based on its position in the result list. The premise of DCG is that highly relevant documents appearing lower in a search result list should be penalized as the graded relevance value is reduced logarithmically proportional to the position of the result.

The DCG accumulated at a particular rank position $p$ is defined as:

\mathrm{DCG_{p}} = rel_{1} + \sum_{i=2}^{p} \frac{rel_{i}}{\log_{2}i}.

Since result set may vary in size among different queries or systems, to compare performances the normalised version of DCG uses an ideal DCG. To this end, it sorts documents of a result list by relevance, producing an ideal DCG at position p ( $IDCG_p$ ), which normalizes the score:

\mathrm{nDCG_{p}} = \frac{DCG_{p}}{IDCG{p}}.

The nDCG values for all queries can be averaged to obtain a measure of the average performance of a ranking algorithm. Note that in a perfect ranking algorithm, the $DCG_p$ will be the same as the $IDCG_p$ producing an nDCG of 1.0. All nDCG calculations are then relative values on the interval 0.0 to 1.0 and so are cross-query comparable.

Other measures

Terminology and derivations
from a confusion matrix
condition positive (P) the number of real positive cases in the data condition negatives (N) the number of real negative cases in the data true positive (TP) eqv. with hit true negative (TN) eqv. with correct rejection false positive (FP) eqv. with false alarm, Type I error false negative (FN) eqv. with miss, Type II error sensitivity, recall, hit rate, or true positive rate (TPR) $\mathrm {TPR} ={\frac {\mathrm {TP} }{P}}={\frac {\mathrm {TP} }{\mathrm {TP} +\mathrm {FN} }}$ specificity or true negative rate (TNR) $\mathrm {TNR} ={\frac {\mathrm {TN} }{N}}={\frac {\mathrm {TN} }{\mathrm {TN} +\mathrm {FP} }}$ precision or positive predictive value (PPV) $\mathrm {PPV} ={\frac {\mathrm {TP} }{\mathrm {TP} +\mathrm {FP} }}$ negative predictive value (NPV) $\mathrm {NPV} ={\frac {\mathrm {TN} }{\mathrm {TN} +\mathrm {FN} }}$ miss rate or false negative rate (FNR) $\mathrm {FNR} ={\frac {\mathrm {FN} }{P}}={\frac {\mathrm {FN} }{\mathrm {FN} +\mathrm {TP} }}=1-\mathrm {TPR}$ fall-out or false positive rate (FPR) $\mathrm {FPR} ={\frac {\mathrm {FP} }{N}}={\frac {\mathrm {FP} }{\mathrm {FP} +\mathrm {TN} }}=1-\mathrm {TNR}$ false discovery rate (FDR) $\mathrm {FDR} ={\frac {\mathrm {FP} }{\mathrm {FP} +\mathrm {TP} }}=1-\mathrm {PPV}$ false omission rate (FOR) $\mathrm {FOR} ={\frac {\mathrm {FN} }{\mathrm {FN} +\mathrm {TN} }}=1-\mathrm {NPV}$ accuracy (ACC) $\mathrm {ACC} ={\frac {\mathrm {TP} +\mathrm {TN} }{P+N}}={\frac {\mathrm {TP} +\mathrm {TN} }{\mathrm {TP} +\mathrm {TN} +\mathrm {FP} +\mathrm {FN} }}$ F1 score is the harmonic mean of precision and sensitivity $F_{1}=2\cdot {\frac {\mathrm {PPV} \cdot \mathrm {TPR} }{\mathrm {PPV} +\mathrm {TPR} }}={\frac {2\mathrm {TP} }{2\mathrm {TP} +\mathrm {FP} +\mathrm {FN} }}$ Matthews correlation coefficient (MCC) $\mathrm {MCC} ={\frac {\mathrm {TP} \times \mathrm {TN} -\mathrm {FP} \times \mathrm {FN} }{\sqrt {(\mathrm {TP} +\mathrm {FP} )(\mathrm {TP} +\mathrm {FN} )(\mathrm {TN} +\mathrm {FP} )(\mathrm {TN} +\mathrm {FN} )}}}$ Informedness or Bookmaker Informedness (BM) $\mathrm {BM} =\mathrm {TPR} +\mathrm {TNR} -1$ Markedness (MK) $\mathrm {MK} =\mathrm {PPV} +\mathrm {NPV} -1$ Sources: Fawcett (2006), Powers (2011), and Ting (2011) ^[9] ^[10] ^[11]

Mean reciprocal rank
Spearman's rank correlation coefficient
bpref - a summation-based measure of how many relevant documents are ranked before irrelevant documents^[8]
GMAP - geometric mean of (per-topic) average precision^[8]
Measures based on marginal relevance and document diversity - see Relevance (information retrieval) § Problems and alternatives

Visualization

Visualizations of information retrieval performance include:

Graphs which chart precision on one axis and recall on the other^[8]
Histograms of average precision over various topics^[8]
Receiver operating characteristic (ROC curve)
Confusion matrix

Non-metrics

Top queries list

Top queries is noting the most common queries over a fixed amount of time. The top queries list assists in knowing the style of queries entered by users.

Non-relevance metrics

Queries per time

Measuring how many queries are performed on the search system per (month/day/hour/minute/sec) tracks the utilization of the search system. It can be used for diagnostics to indicate an unexpected spike in queries, or simply as a baseline when comparing with other metrics, like query latency. For example, a spike in query traffic, may be used to explain a spike in query latency.

References

↑ American Marketing Association Dictionary. http://www.marketingpower.com/_layouts/Dictionary.aspx.%5B%5D Retrieved 2012-11-02. The Marketing Accountability Standards Board (MASB) endorses this definition as part of its ongoing Common Language in Marketing Project.
1 2 Zhu, Mu (2004). "Recall, Precision and Average Precision" (PDF).
↑ Turpin, Andrew; Scholer, Falk (2006). "User performance versus precision measures for simple search tasks". Proceedings of the 29th Annual international ACM SIGIR Conference on Research and Development in information Retrieval (Seattle, WA, August 06–11, 2006). New York, NY: ACM: 11–18. ISBN 1-59593-369-7. doi:10.1145/1148170.1148176.
1 2 Everingham, Mark; Van Gool, Luc; Williams, Christopher K. I.; Winn, John; Zisserman, Andrew (June 2010). "The PASCAL Visual Object Classes (VOC) Challenge" (PDF). International Journal of Computer Vision. Springer. 88 (2): 303–338. doi:10.1007/s11263-009-0275-4. Retrieved 2011-08-29.
1 2 Manning, Christopher D.; Raghavan, Prabhakar; Schütze, Hinrich (2008). Introduction to Information Retrieval. Cambridge University Press.
↑ K.H. Brodersen, C.S. Ong, K.E. Stephan, J.M. Buhmann (2010). The binormal assumption on precision-recall curves Archived December 8, 2012, at the Wayback Machine.. Proceedings of the 20th International Conference on Pattern Recognition, 4263-4266.
1 2 3 Christopher D. Manning; Prabhakar Raghavan & Hinrich Schütze (2009). "Chapter 8: Evaluation in information retrieval" (PDF). Retrieved 2015-06-14. Part of Introduction to Information Retrieval
1 2 3 4 5 http://trec.nist.gov/pubs/trec15/appendices/CE.MEASURES06.pdf
↑ Fawcett, Tom (2006). "An Introduction to ROC Analysis" (PDF). Pattern Recognition Letters. 27 (8): 861–874. doi:10.1016/j.patrec.2005.10.010.
↑ Powers, David M W (2011). "Evaluation: From Precision, Recall and F-Measure to ROC, Informedness, Markedness & Correlation" (PDF). Journal of Machine Learning Technologies. 2 (1): 37–63.
↑ Ting, Kai Ming (2011). Encyclopedia of machine learning. Springer. ISBN 978-0-387-30164-8.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.