--- layout: default title: Supplementary Material for Time-aware Evaluation of Cumulative Citation Recommendation Systems section: Work --- Time-aware Evaluation of Cumulative Citation Recommendation Systems =================================================================== Laura Dietz, Jeffrey Dalton, Krisztian Balog Proceedings of SIGIR 2013 Workshop on Time-aware Information Access, TAIA 2013 [View Paper](taia2013-cameraready.pdf) - [Link to GitHub](http://github.com/laura-dietz/taia-stream-eval/) Abstract -------- The goal of stream filtering systems is to identify relevant items over time. However, systems are often evaluated in a time-agnostic fashion, where results are evaluated as a batch. This work introduces a time-aware evaluation paradigm to study time-dependent characteristics of system effectiveness, such as performance degeneration over time. A particular challenge is posed by bursts in the volume of relevant documents in the ground truth, caused by specific events and trends. We introduce burst-aware weighting to arrive at a time-aware comparison across systems. As a motivating application, we re-evaluate the submissions to the TREC 2012 Knowledge Base acceleration track. Our evaluation paradigm is able to consistently distinguish teams by performance. We confirm that choices of time-granularity and burst-aware weighting schemes affect the results. Cite As ------- @inproceedings{Dietz-TAIA2013, author = {Dietz, Laura and Dalton, Jeffrey and Balog, Krisztian}, booktitle = {Proceedings of SIGIR 2013 Workshop on Time-aware Information Access (TAIA 2013)}, title = {Time-aware Evaluation of Cumulative Citation Recommendation Systems}, year = {2013} } Clone from github: git://github.com/laura-dietz/taia-stream-eval.git The repository contains both code and derived plots and tables Python Implementation ---------------------- Code runs best with Python 2.7.4, matplotlib 1.2.1, numpy 1.7.1 You need to run several stages: 1. aggregate the official judgments with `python collapse-truth-judgment.py` (notice: you need to change the file) 2. for all run-files, measure performance per slice, for instance with `python measure-slice.py -f FILE --intervalType week --judgmentLevel 1` for weekly slices and relevant+central 3. now you can create different plot and tables as described below total-stats.py: uniform and burst-aware aggregation, produced tables with team, run, all, week, day perf-over-time.py: plot performance over time for each time with uniform weighting weights-over-time.py: burst-aware weights per time interval sidebyside-singleentity.py: for given entity compare two runs with uniform and burst-aware weighting For more details see [run-stream-eval.sh](http://github.com/laura-dietz/taia-stream-eval/blob/master/code/run-stream-eval.sh). Run it with `bash run-stream-eval.sh ` where judgmentLevel 1 defines the true documents as central+relevant and 2 as only central. Burst-aware Weighting --------------------- The uniform weighting represents average of measures across all slices. This is useful for diagnosing system degeneration over time. However, for some user tasks some slices might be more important than others. In this scenario, we evaluate by a weighted average of measures. A wide range of weighting schemes are possible, here we focus on a usage scenario in which it is more important to predict bursty slices correctly. We capture this with weights P(i|q) = #R(i,q) / sum_j( #R(j,q) ) where `#R(i,q)` refers to the number of relevant documents in slice `i` for query entity `q`, `i` and `j` refer to slice indices `I` For comparison, uniform weights are computed by P(i|q) = 1 / I For systems with constant performance over time, both weightings yield the same results. The intuition is that weighted aggregation takes some of the weights from one slice and moves it to another. In the performance plots over time below, we display just the measured performance per slice, `P(r=1|d_i,q,i)`, where the overall performance follows as the area under the curve. For the weighted performance plots, the measured performance per slice is re-weighted so that the area under the curve yields yields the over all performance as area under the curve. This means that plotted values are computed by plotValue = P(r=1|d_i,q,i) * P(i|q) * I Notice that this may result in values larger than one, if slices in important bursts have near optimal performance. This is because some weight mass is "stolen" from other slices. The resulting total performance is unaffected by this, it is never larger than one. Resulting Plots and Tables -------------------------- The resulting plots and tables are found in the github for relevant + central: [data/cr/](http://github.com/laura-dietz/taia-stream-eval/tree/master/data/cr) central only: [data c](http://github.com/laura-dietz/taia-stream-eval/tree/master/data/c) This section explains the directory structure under each of the data directories on the example of analysis with relevant+central (cr). Notice that in order to see examples for "central" (instead of relevant+central) you need to switch to directory c (not cr) AND use files named "central" instead of "relevant+central". We define informal variables: - `$intervalType` is one of "day", "week", "all" - `$metric` is one of "MAP", "Prec@R", "nDCG@R", "correctedAUC" -- see blow for details - `$entity` is one of the official TREC KBA 2012 query entities - `$team` and `$run` refers to official KBA participants and their officially submitted runs respectively - slices (also refered to as intervals) are represented by their lower bounds in epoch ticks or days in the evaluation time range. ### aggregation_weights To provide some intuition on the effects that our burst-aware weighting scheme has on the results, we provide plots of these weights over time. plot the entity's burst-wareness weights over time [Example: Burst-awareness weights for Mario_Garnero](http://github.com/laura-dietz/taia-stream-eval/blob/master/data/cr/aggregation_weights/Mario_Garnero__weights__day_weights_teams_over_time_relevant%2Bcentral_WEIGHTED.pdf?raw=true) ./aggregation_weights/$entity__weights__$intervalType_weights_teams_over_time_relevant+central_WEIGHTED.pdf aggregate burst-awareness weights across entities [Burst-awareness weights across entities](http://github.com/laura-dietz/taia-stream-eval/blob/master/data/cr/aggregation_weights/all_weights__day_weights_teams_over_time_relevant%2Bcentral_WEIGHTED.pdf?raw=true) ./aggregation_weights/all_weights__$intervalType_weights_teams_over_time_relevant+central_WEIGHTED.pdf data that generated the plots as tab separated files Columns are 'entityListName', 'intervalLowerBound', 'treat_unjudged_docs_as','judgmentLevel','metric','mean','stdev','intervalType' [Burst-awareness weights as table]( http://github.com/laura-dietz/taia-stream-eval/blob/master/data/cr/overall_stats/MAP_total_stats_relevant%2Bcentral_WEIGHTED.tsv) ./aggregation_weights/_weights_over_time_relevant+central.tsv ### overall_stats After choosing a metric and weighting scheme, each system is associated with one performance number. run performance (across all entities) either with uniform weighting or burst-aware weighting; columns are team, run, all, week, day [Example: Overall results using MAP and uniform weighting](https://github.com/laura-dietz/taia-stream-eval/blob/master/data/cr/overall_stats/MAP_total_stats_relevant%2Bcentral_UNIFORM.tsv) [Example: Overall results using MAP and burst-aware weighting](http://github.com/laura-dietz/taia-stream-eval/blob/master/data/cr/overall_stats/MAP_total_stats_relevant%2Bcentral_Weighted.tsv) ./overall_stats/$metric_total_stats_relevant+central_${UNIFORM|WEIGHTED}.tsv ### entity_stats run performance per entity either with uniform weighting or burst-aware weighting; columns are team, run, all, week, day [Example: Results on entity Mario_Garnero using MAP and uniform weighting](http://github.com/laura-dietz/taia-stream-eval/blob/master/data/cr/entity_stats/MAP_entity_stats_Mario_Garnero_relevant%2Bcentral_UNIFORM.tsv) [Example: Results on entity Mario_Garnero using MAP and burst-aware weighting](http://github.com/laura-dietz/taia-stream-eval/blob/master/data/cr/entity_stats/MAP_entity_stats_Mario_Garnero_relevant%2Bcentral_WEIGHTED.tsv) ./entity_stats/$metric_entity_stats_$entity_relevant+central_${UNIFORM|WEIGHTED}.tsv ### perf-over-time To analyze the performance over time, we provide plots for uniform and weighted system performance. For comparison we also provide plots for the intervalType 'all', which only consists of one data point, depicted by a line over the evaluation time range. plots performance of all teams over time with uniform weighting [Example: Results over weekly slices using MAP and uniform weighting](http://github.com/laura-dietz/taia-stream-eval/blob/master/data/cr/perf-over-time/overview_week_MAP_teams_over_time_relevant%2Bcentral_UNIFORM.pdf?raw=true) ./perf-over-time/overview_$intervalType_$metric_teams_over_time_relevant+central_UNIFORM.pdf performance plots for for all intervalTypes in one plot [Example: Results over different slice granularities using MAP and uniform weighting](http://github.com/laura-dietz/taia-stream-eval/blob/master/data/cr/perf-over-time/overview_MAP_teams_over_time_relevant%2Bcentral_UNIFORM.pdf?raw=true) ./perf-over-time/overview_$metric_teams_over_time_relevant+central_UNIFORM.pdf plots performance for a single team [Example: Results of team UvA over weekly slices using MAP and uniform weighting](http://github.com/laura-dietz/taia-stream-eval/blob/master/data/cr/perf-over-time/UvA_week_MAP_teams_over_time_relevant%2Bcentral_UNIFORM.pdf?raw=true) ./perf-over-time/$team_$intervalType_$metric_teams_over_time_relevant+central_UNIFORM.pdf ### sidebyside The side-by-side comparison gives insight of how two teams differ over time, and during bursts on a per-entity level. [Example: Uniform and burst-aware comparison of teams uiucGSLIS and UvA using MAP on entity Mario_Garnero](http://github.com/laura-dietz/taia-stream-eval/blob/master/data/cr/sidebyside/uiucGSLIS_gslis_adaptive-vs-UvA_UvAIncLearnHigh_sidebyside_MAP_Mario_Garnero.pdf?raw=true) [Example: Uniform and burst-aware comparison of teams uiucGSLIS and UvA using MAP on entity James_McCartney](http://github.com/laura-dietz/taia-stream-eval/blob/master/data/cr/sidebyside/uiucGSLIS_gslis_adaptive-vs-UvA_UvAIncLearnHigh_sidebyside_MAP_James_McCartney.pdf?raw=true) ./sidebyside/$team1-$run1-vs-$team2-$run2_sidebyside_$metric$_$entity.pdf Metrics ------- ### MAP Compute Mean average precision following this algorithm: - for every rank p that yields a positive document: --- compute precision at p - take the average of all computed precisions ### Prec@R Compute R-Precision (Precision at a rank that represents the number of relevant documents). ### nDCG@R Compute NDCG@R, where R is the number of relevant documents Normalized Discounted Cumulative Gain: DCG / DCG(ideal ranking) Compute Discounted Cumulative Gain which is computed by - for every rank p that yields a positive document: --- 1/log(p+2) - sum over all values ### correctedAUC Area under the Receiver-Operator curve. This is a fast implementation that follows the trajectory of the ROC curve and needs only a single pass through the data. Start in lower-right corner, for a pos document go up, for neg document go right. This implementation assumes that the ranking is complete. The original AUC measure is rescaled to [-1, +1] to better match the perturbation level. ### numPosPredictions The total number of correct predictions per slice - this measure is intended for debugging. Robustness of Metrics against varying ground truth --------------------------------------------------- For this analysis it is important that the metrics are robust towards changing ground truth to yield measures that are comparable by slice. Changing ground truth refers to both differing number of relevant documents and differing number of entries per slice. We confirm this robustness of the measures above by a simple experiment. For a given set of ground truths and ranking lengths, we permute x% of positive entries with a negative entry. We call x is the permutation level, which is to be recovered. See [Comparison of Metrics](metric-comparison.pdf) for the results. The x-axis is an approximation to the perturbation level, we test 10%, 25% and 50% perturbation. The y-axis represents the measured performance, averaged across 1000 randomized rankings. The groups of points refer to different ground truths, in number of true positive and true negative elements left to right: (100,100),(50,50),(5,5),(20,180),(10,90),(1,9) - First three points vary ranking length with balanced classes, last three points represent skewed class distribution with increasing ranking lengths. The black line represents the ideal error level (as 1.0 - perturbation level), which is to be recovered. Obviously, numPosPredictions does not correlate with the perturbation level, and is left out of this comparison.