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: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c(j) = 2}
• Poor: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c(j) = 1}

Example query: {abc}

discounting factor is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 31 = 2^5 - 1}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 31}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 31 = 31 \cdot 1}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 31}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 = \frac{31}{31}}
2	http://www.abcteach.com	Fair: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3 = 2^2 - 1}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 34 = 31 + 3}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 32.9 = 31 + 3 \cdot 0.63}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 40.5}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.81 = \frac{32.9}{40.5}}
3	http://abcnews.go.com/sections	Excellent: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 15 = 2^4 - 1}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 49 = 31 + 3 + 15}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 40.4 = 32.9 + 15 \cdot 0.50}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 48.0}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.84 = \frac{40.4}{48.0}}
4	http://www.abc.net.au/	Excellent: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 15}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 64 = 31 + 3 + 15 + 15}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 46.9 = 40.4 + 15 \cdot 0.43}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 54.5}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.86 = \frac{46.9}{54.5}}
5	http://abcnews.go.com/	Excellent: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 15}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 79 = 31 + 3 + 15 + 15 + 15}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 52.7 = 46.9 + 15 \cdot 0.39}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 60.4}	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.87 = \frac{52.7}{60.4}}