RankDCG: Rank-Ordering Evaluation Measure

RankDCG: Rank-Ordering Evaluation Measure Denys Katerenchuk, Andrew Rosenberg The Graduate Center, New York, USA 365 Fifth Avenue, Room 4319, New York, NY 10016 CUNY Queens College, New York, USA 65-30 Kissena Boulevard, Room A-202, Flushing, NY 11367 dkaterenchuk@gradcenter.cuny.edu, andrew@cs.qc.cuny.edu Abstract Ranking is used for a wide array of problems, most notably information retrieval (search). Kendall’s τ, Average Precision, and nDCG are a few popular approaches to the evaluation of ranking. When dealing with problems such as user ranking or recommendation systems, all these measures suffer from various problems, including the inability to deal with elements of the same rank, inconsistent and ambiguous lower bound scores, and an inappropriate cost function. We propose a new measure, a modification of the popular nDCG algorithm, named rankDCG, that addresses these problems. We provide a number of criteria for any effective ranking algorithm and show that only rankDCG satisfies them all. Results are presented on constructed and real data sets. We release a publicly available rankDCG evaluation package. Keywords: RankDCG, Rank Measure, Ranking, Ordering, Evaluation 1. Introduction Every algorithm needs to be assessed to determine its per- formance. No single measure can be applied to all prob- lems. If we consider a single area of computer science natural language processing (NLP), each problem requires specific evaluation. For example, for a simple classifica- tion task, accuracy is an intuitive and useful measure (Du- mais et al., 1998; Katerenchuk et al., 2014). For named entity recognition and other “detection” tasks with a rela- tively small percent of relevant items (Tjong Kim Sang and De Meulder, 2003; Katerenchuk and Rosenberg, 2014), F- measure (Rijsbergen, 1979) is best suited. Correlation mea- sures such as Pearson’s r (Pearson, 1895) and Spearman’s ρ (Spearman, 1904) are used to find relationships between entities (Strapparava and Mihalcea, 2008; Schuller et al., ). Kendall’s τ (Kendall, 1938), Average Precision (AP) (Zhu, 2004), Mean Average Precision (MAP) and Discounted Cu- mulative Gain (DCG) (J¨arvelin and Kek¨al¨ainen, 2002) are all used in information retrieval (IR) and ranking type of problems (Lapata, 2006; Philbin et al., 2007; J¨arvelin and Kek¨al¨ainen, 2000). Despite a large number of different ranking measures, there are still problems that cannot be appropriately evaluated. One particular problem is to rank discrete value elements with multiple ties of the same rank and a skewed rank dis- tribution. This type often arises in a number of ranking problems such as information retrieval or search. While some measures address parts of this problem, none exists to solve them all. In this paper, we propose a new measure to deal with rank- ordering problems. We start with defining the problem and criteria that need to be satisfied in section 2. In Section 3 we give a short survey of available evaluation measures. In Section 4. we propose rankDCG, an improved evaluation measure and evaluate its performance in Section 5. We sum up our findings and conclude our work in Section 6. 2. Ordering The problem of ordering is well known. It involves tasks such as internet …

Content truncated to 500 words