Ranking Metric
评估排序效果时，经常用到几个指标，简单记录之。
AUC
将排序效看做一个二分类问题，计算一系列false positive rate和true positive rate，绘制ROC区间，然后计算曲线下面积得到AUC，细节参考ROC分析。
MAP
MAP: Mean average precision. 即计算average precision的均值。
首先计算Precision@k，含义是前k个排序结果中，真实相关的比例。然后取不同的k值，计算average precision；最后在多个排序结果上平均。其中$l_k$是indicator function，当前位置文档相关记为1，否则为0。
NDCG
Discounted cumulative gain (DCG) is a measure of ranking quality. In information retrieval, it is often used to measure effectiveness of web search engine.
简单讲就是计算前k个位置上累计的gain。其计算基于如下两个假设
- Highly relevant documents are more useful if appearing earlier in search result.
- Highly relevant documents are more useful than marginally relevant documents which are better than non-relevant documents.
一个排序列表，每个item有一相关性得分，计算其得分，并用位置discount（位置越靠后，gain的discount越重，因为假设相关item排前面更有用）。
最后需要将DCG归一化，做法是获取Ideal DCG(IDCG)，然后除以它即可。计算例子见参考文档。
