CSCE 470 Lecture 8

« previous | Wednesday, September 11, 2013 | next »

Measuring Performance

Suppose we have labels on query-document pairs (from a trusted source)—relevant or not relevant—for 100 M documents.

Note: Relevance may not apply to individual users (or at all, in the case of marginal relevance and mirroring), but at least it's an approximation

We have two engines, "mine" and "yours", that we wish to test against our document set.

For one query (e.g. "bob"), suppose

• "mine" finds [ irrelevant, relevant, irrelevant, relevant, relevant ]
• "yours" finds [ relevant, relevant ]

From this, we can get two metrics:

• yours returned relevant results first (assume ordered search)
• mine returned more relevant results overall

But one query is not good enough. Let's run 10,000 queries. Suppose that in reality, "yours" actually works better than "mine" on average.

Remember that there are 4 ways to measure:

1. Precision
   • In the example query ("bob") above, "mine": $P=3/5$ were actually relevant; and "yours": $P=2/2$
   • Take into account ranking (to an extent): precision at $k$ → "mine": $P_{2}=1/2$, "yours": $P_{2}=2/2$
2. Recall
   • "mine": $R=3/50$, "yours": $R=2/50$
   • Suppose "mine" was "optimized" for recall and just returned all documents in the collection; now $R=50/50$
3. F-measure: $F={\frac {2PR}{P+R}}$
   • Note tension between precision and recall; it's possible for both to diverge by returning fewer or more documents
   • "mine": $F=1e-6$; "yours": $F=0.0769$
4. Normalized Discounted Cumulative Gain (NDCG)
   • Hottest measure right now
   • Sensitive to position of highest rated page
   • Log-discounting of results
   • Normalized for different lengths lists

NDCG

$NDCG_{n}=Z_{n}\,\sum _{j=1}^{n}{\frac {2^{c(j)}-1}{\log {\left(1+j\right)}}}\,\!$

• $j$ represents our result's rank
• $Z_{n}$ is normalization
• $\sum$ is a cumulation
• $2^{c(j)}-1$ is gain
• $\log {\left(1+j\right)}$ is Position discount

Let's define our gain label function $c(j)$ as follows:

• Perfect: $c(j)=5$
• Excellent: $c(j)=4$
• Average: $c(j)=3$
• Fair: $c(j)=2$
• Poor: $c(j)=1$

Example query: {abc}

discounting factor is ${\frac {\log {2}}{\log {\left(1+j\right)}}}$

Rank	URL	Gain	Cumulative Gain	Discounted Cumulative Gain	Max DCG	NDCG
1	http://abc.go.com/	Perfect: $31=2^{5}-1$	$31$	$31=31\cdot 1$	$31$	$1={\frac {31}{31}}$
2	http://www.abcteach.com	Fair: $3=2^{2}-1$	$34=31+3$	$32.9=31+3\cdot 0.63$	$40.5$	$0.81={\frac {32.9}{40.5}}$
3	http://abcnews.go.com/sections	Excellent: $15=2^{4}-1$	$49=31+3+15$	$40.4=32.9+15\cdot 0.50$	$48.0$	$0.84={\frac {40.4}{48.0}}$
4	http://www.abc.net.au/	Excellent: $15$	$64=31+3+15+15$	$46.9=40.4+15\cdot 0.43$	$54.5$	$0.86={\frac {46.9}{54.5}}$
5	http://abcnews.go.com/	Excellent: $15$	$79=31+3+15+15+15$	$52.7=46.9+15\cdot 0.39$	$60.4$	$0.87={\frac {52.7}{60.4}}$